当前位置：文档之家 › 一种基于代数决策图的多值图像无损压缩方法

一种基于代数决策图的多值图像无损压缩方法

  • 格式：pdf
  • 大小：198.32 KB
  • 文档页数：4

第２６卷第２期　２００６年４月　桂林电子工业学院学报　

Ｊｏｕｒｎａｌ　ｏｆ　Ｇｕｌｌｌｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃ　Ｔｅｃｈｎｏｌｏｇｙ　Ｖｏ１．２６．Ｎｏ．２　Ａｐｒ．２００６　

一种基于代数决策图的多值图像无损压缩方法　

孙自广，古天龙　

（桂林电子科技大学计算机系，广西桂林５４１００４）　

摘要：代数决策图（ＡＤＤ）是布尔函数的一种简洁紧凑的符号描述方法。用ＡＤＤ对多值图像进行建模，可以有效　

降低数据冗余，然后对ＡＤＤ模型进行有效的编码，可以达到数据压缩的目的。实验结果显示本方法的压缩比高于　

游程编码、哈夫曼编码，较ＬＺ７７编码也有一定优势。　

关键词：图像压缩｝无损压缩；多值图像；ＡＤＤ　，　

中图分类号：ＴＰ３９１．４１　文献标识码：Ａ　文章编号：１００１—７４３７（２００６）０２．０１００—０４　

Ａｎ　ＡＤＤ・－ｂａｓｅｄ　ｌｏｓｓｌｅｓｓ　ｃｏｍｐｒｅｓｓｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｍｕｔｉｌ—－ｌｅｖｅｌ　ｉｍａｇｅｓ　

ＳＵＮ　Ｚｉ—ｇｕａｎｇ，ＧＵ　Ｔｉａｎ—ｌｏｎｇ　

（Ｄｅｐｔ．ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｇｕｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃ　Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕｉｌｉｎ　５４１００４，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ａｌｇｅｂｒａｉｃ　Ｄｅｃｉｓｉｏｎ　Ｄｉａｇｒａｍ（ＡＤＤ）ｉｓ　ａ　ｓｙｍｂｏｌｉｃ　ｍｅｔｈｏｄ　ｕｔｉｌｉｚｅｄ　ｔｏ　ｒｅｐｒｅｓｅｎｔ　Ｂｏｏｌｅａｎ　ｆｕｎｃｔｉｏｎ．Ｔｒｅａｔｉｎｇ　

ａ　ｍｕｌｔｉ—ｌｅｖｅｌ　ｉｍａｇｅ　ｗｉｔｈ　ＡＤＤ　ｃａｎ　ｃｏｎｓｉｄｅｒａｂｌｙ　ｒｅｄｕｃｅ　ｔｈｅ　ｒｅｄｕｎｄａｎｃｙ．Ｔｈｅ　ＡＤＤ　ｃａｎ　ｔｈｅｎ　ｂｅ　ｅｎｃｏｄｅｄ　ｅｆｆｉｃｉｅｎｔｌｙ　ｆｏｒ　

ｔｈｅ　ｉｍａｇｅ　ｔｏ　ｂｅ　ｃｏｍｐｒｅｓｓｅｄ．Ｒｅｓｕｌｔｓ　ｆｒｏｍ　ｅｘｐｅｒｉｍｅｎｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｄｉｓｃｕｓｓｉｏｎ　ｈａｓ　ａ　ｂｅｔｔｅｒ　ｃｏｍｐｒｅｓ—　

ｓｉｏｎ　ｒａｔｉｏ　ｔｈａｎ　ＲＬＥ　ｃｏｄｉｎｇ，Ｈｕｆｆｍａｎ　ｃｏｄｉｎｇ　ａｎｄ　ＬＺ７７．　

Ｋｅｙ　ｗｏｒｄｓ：ｉｍａｇｅ　ｃｏｍｐｒｅｓｓｉｏｎ；ｌｏｓｓｌｅｓｓ　ｃｏｍｐｒｅｓｓｉｏｎ；ｍｕｌｔｉ＊ｌｅｖｅｌ　ｉｍａｇｅ；ＡＤＤ　

图像数据的存储和传输都要求对数据进行有效　

的压缩，一些实际的应用要求这种压缩时无损的，如　

医学图像、遥感图像、图像存档等。对图像的无损压缩　

技术而言，通常是首先采取解相关处理，降低数据冗　

余，然后再进行编码。解相关的模型包括预测模型、上　

下文模型和变换模型，寻求有效表征图像的模型是无　

损压缩研究的重要方向［１］　近年来，在逻辑电路综合　

领域发展起来的技术不仅成功应用于电路设计，而且　

逐渐应用到机器学习、图像处理、图像压缩、模式识别　

和数据挖掘等相关领域［　有序二叉决策图（ＯＢＤＤ—　

Ｏｒｄｅｒｅｄ　Ｂｉｎａｒｙ　Ｄｅｃｉｓｉｏｎ　Ｄｉａｇｒａｍ）是一种布尔函数　

的符号描述方法，在ＶＬＳＩ系统验证领域引入ＯＢＤＤ，　

极大地提高了电路验证的规模和复杂度。描述数字电　

路的布尔函数中包含有大量等价的子函数，通过ＯＢ—　

ＤＤ这种特殊的数据结构，可以共享那些等价的子函　

数，这样不仅减少了存储描述符号所需的空间同时也　

降低了针对这些描述符号的操作的运算时间。代数决　策图ＡＤＤ（Ａｌｇｅｂｒａｉｃ　Ｄｅｃｉｓｉｏｎ　Ｄｉａｇｒａｍ）是ＯＢＤＤ的　

扩展形式，可描述值域为整数域的伪布尔函数。用　

ＡＤＤ描述图像可以降低图像在空间中的冗余信息，　

然后对ＡＤＤ模型进行编码可以有效地压缩图像数　

据。　

１代数决策图ＡＤＤ　

一个ＡＤＤ就是表示一簇伪布尔函数　：｛０，１）　一　

ｚ（整数集合）的有一个直接根结点的有向无环图［　。　

所有的有限个结点被分为终端结点和非终端结点两　

类。在图中一般用圆圈表示非终端结点，用方框表示　

终端结点。每个终端结点都被标有ｚ中的一个元素，　

并且没有射出边。而每个非终端结点都有两条射出　

边，即。一边和和ｌ一边。ｏ一边是指非终端结点取值０　

后的分支，在图中一般用虚线表示。ｌ一边是指非终端　

结点取值１后的分支，在图中一般用实线表示。对于　

收稿日期ｒ　２ＯＯ５—１２—１Ｏ　

作者简介：孙自广（１９７８一）。男。河南濮阳人。硕士研究生，

主要从事符号技术、图像压缩等方面的研究　维普资讯 http://www.cqvip.com 第２期　孙自广等：一种基于代数决策图的多值图像无损压缩方法　１０１　

变量的一组赋值，所得到的函数值由根结点到一个终　

端结点的一条路径决定。这条路径所对应的分支由变　

量的这组赋值来决定，该分支的终端结点所标识的值　

就是变量在这组赋值下所对应的函数值。不同的变量　

序的选择对于ＡＤＤ的规模有着极大的影响，因此在　

求伪布尔函数的ＡＤＤ时，必须说明变量的顺序。图１　

（ａ）为伪布尔函数，＝ｚ。ｚ　＋２ｘ　ｚ。的完全二叉表示，　

图１（ｂ）为，在变量序兀：ｚ。＜ｚ　＜ｚ。＜ｚ　下的ＡＤＤ，由　

图１可见，表示伪布尔函数，的ＡＤＤ所需的结点明显　

小于表示该函数的完全二叉树，这表明ＡＤＤ的存储　

空间较小。　

（ａ）二叉树　

（ｂ）ＡＤＤ　

图１伪布尔函数，：　ｌ　２＋２ｘ３　４的ＡＤＤ表示　

ＡＤＤ极大地改善了伪布尔函数和有限域取值函　

数的描述能力，目前，ＡＤＤ数据结构在矩阵乘、最短　

路径计算、组合电路的时间分析、网络最大流　‘　等领　

域得到了广泛的应用。　

２图像的ＡＤＤ模型编码　

２．１图像的预处理　

从未压缩图像文件中提取图像像素值，然后存储　

在２维数组中。如果图像的长宽尺寸不是２的幂，调整　

尺寸大小为２的幂，增加的像素值设为０．假如一幅图　

像的大小为４８０×４８０像素，调整后的尺寸为５１２×　

５１２像素。　２．２图像的ＡＤＤ模型　

一幅图像可以看作一个矩阵。图２（ａ）是一幅简单　

的８×８图像，其对应的矩阵如图２（ｂ）所示，图３为生　

成的ＡＤＤ．如果图像的尺寸为ＮＸＭ，且Ⅳ和　都整　

数２的幂（Ⅳ＝２　，　＝２　），那么矩阵可以由　＋ｍ个　

布尔变量组成的伪布尔函数来描述［“　。图２中的例　

子共需要６个变量，行坐标由ｚ　ｚ。ｚ。编码，列坐标由　

Ｙ２Ｙ１Ｙｏ编码，这里按照变量序：Ｙ２＜　ｌ＜　ｏ＜ｚ２＜ｚｌ＜　

ｚ。构建ＡＤＤ，生成的ＡＤＤ共有３０个结点，其中终端　

结点有５个。　

Ｏ　０　１　１　１　ｌ　０　０　Ｏ　２　２　２　２　２　２　０　１　２　３　３　３　３　２　ｌ　ｌ　２　３　４　４　３　２　ｌ　１　２　３　４　４　３　２　ｌ　ｌ　２　３　３　３　３　２　ｌ　Ｏ　２　２　２　２　２　２　０　０　０　ｌ　ｌ　ｌ　１　Ｏ　Ｏ　

（ａ）多值图像　（ｂ）矩阵　

图２图像例子　

图３图像对应的ＡＤＤ　

２．３　ＡＤＤ的编码　

为了对ＡＤＤ进行编码，可采取以下策略：自顶向　

下对ＡＤＤ内的结点按光栅格式进行编号（ｉｎ图４所　

示），可以用一张表静态链接表ＳＴ（表１所示）来表述　

该ＡＤＤ，在ＳＴ表中每一行表示一个结点，其中第１列　

表示当前结点的序号；第２列表示当前结点所处的层　

次；第３列和第４列分别表示当前结点ｌｏｗ和ｈｉｇｈ分　

支结点的序号，也可看作当前结点指向分支结点的两　

个指针。

　维普资讯 http://www.cqvip.com ｌＯ２　桂林电子工业学院学报　２００６年４月　

图４已编号的ＡＤＤ　

令　为ＡＤＤ的非终端结点数，Ｐ为ＡＤＤ总的层　

次数，ｍ＾为ＡＤＤ中第ｋ层的结点数（五∈｛０，ｌ，…，Ｐ　

—１））．对ｍ进行编码可以获得ＳＴ表的第ｌ列。对于　

ＳＴ表第２列，若ｍ　已经编码，在ｋ从０到Ｐ一２区间　

内，可重复ｍ　次层次数ｋ获得第２列的数据。对于图　

２由ｍ＾组成的数列为｛ｌ，２，４，４，８，６）．　

表１　ＡＤＤ的静态链接表　

结点编号　ｈｉｇｈ分支　

为高效编码ＳＴ表的两歹　指针数据，米用形如　

ｌｏｗｏｈｉｇｈｏｌｏｗ１ｈｉｇｈ１．．・ｌｏｗ　一ｌｈｉｇｈ　一１的序列形式，构　

建２　个指针组成的序列，在图３中的生成的序列为　

ｆｌ　２　３　４　５　６　７　８　９　１０　１０　９　８　７　１１　１２　１３　１４　１５　１６　１７　ｌ８　

回固固回１９圉圉２０　２１固固２２　２１　２３　２４　２２回回　

圉回固圉圉团固团团固）．　在这样的一个序列中，虽然在某些点是失序的，　

但基本上是升序排列。图３中的升序序列为｛１　２　３　４　５　

６　７　８　９　１Ｏ　１１　１２　１３　１４　１５　１６　１７　１８　１９　２Ｏ　２１　２２　２３　２４　

）．利用这样的升序模式可以有效的对指针序列进行　

编码。在对指针序列进行编码时，主要分３种指针：　

（１）有序指针ＯＰ：位于升序序列的指针，可以只　

用１个比特位来表示，取值为１．　

（２）终端指针ＴＰ：指向终端结点，第１个比特位　

为０表示失序结点，第２位为１表示终端结点，其后是　

对颜色值的编码。如果图像的颜色数较多，使用颜色　

表来存储颜色值，编码时使用索引值代替颜色值。　

（３）非终端失序结点ＮＴＤＰ：指针序列中失序的　

非终端结点，编码这些结点时需要３部分，第１部分是　

前２位为ｏ０表示指针类型，第２部分是当前有序结点　

和未编码失序结点所在层次差值的编码，经过对大量　

图像ＡＤＤ表示的分析，这部分用２比特位。第３部分　

是指向结点在其所在层次位置的编码，这部分用　

［１０ｇ　］比特位。　

３优化方法　

以上主要描述的是用ＡＤＤ模型压缩图像的策　

略。本节引入两种方法提高压缩效率。　

３．１格雷码　

在２．３中，图像的矩阵表示的坐标使用的是串行　

二进制码，如果变量　和　用格雷码进行编码有利于　

函数化简，可以得到更简洁的ＡＤＤ，进一步降低冗　

余。图２（ｂ）的坐标如果经过格雷码编码，可看作某逻　

辑函数的卡诺图。图５是对应的ＡＤＤ．这里采用的变　

囝５格雷码编码的ＡＤＤ　支一　。　¨Ｈ　ｕ。　。ｂ一　默一。　。。。。　

Ｏ　１　ｚ　３　４　５　６　７　８　９　维普资讯 http://www.cqvip.com

合集下载

大数据工程技术基础知识单选题100道及答案解析

大数据工程技术基础知识单选题100道及答案解析

大数据工程技术基础知识单选题100道及答案解析

1. 以下哪种技术不属于大数据采集技术？（ ）

A. 网络爬虫

B. 传感器

C. 关系型数据库

D. Flume

答案：C

解析：关系型数据库在传统数据处理中较为常见，对于大规模的非结构化和半结构化数据采集，其能力相对有限。网络爬虫、传感器和 Flume 都是常见的大数据采集技术。

2. 大数据的 4V 特征不包括（ ）

A. Volume（大量）

B. Variety（多样）

C. Velocity（高速）

D. Visibility（可见）

答案：D

解析：大数据的 4V 特征包括 Volume（大量）、Variety（多样）、Velocity（高速）和 Value（价值）。

3. Hadoop 生态系统中的分布式存储系统是（ ）

A. Hive

B. HBase

C. HDFS

D. MapReduce

答案：C

解析：HDFS（Hadoop Distributed File System）是 Hadoop 生态系统中的分布式存储系统。

4. 以下哪个不是 NoSQL 数据库？（ ）

A. MongoDB

B. MySQL

C. Cassandra

D. Redis

答案：B

解析：MySQL 是传统的关系型数据库，MongoDB、Cassandra 和 Redis 都属于 NoSQL 数据库。

5. 在大数据处理中，用于数据清洗的工具通常不包括（ ）

A. Excel

B. Apache Spark

C. Talend

D. Pentaho

答案：A

解析：Excel 在小规模数据处理中常用，但在大数据处理场景中，Apache Spark、Talend 和

Pentaho 等工具更为适用。

6. 数据仓库的主要作用是（ ）

A. 实时数据处理

B. 数据存储

C. 数据分析和决策支持

D. 数据采集

答案：C 解析：数据仓库主要用于数据分析和为决策提供支持。

机器人视觉系统与图像处理考核试卷

机器人视觉系统与图像处理考核试卷

机器人视觉系统与图像处理考核试卷

考生姓名：__________ 答题日期：_______ 得分：_________ 判卷人：_________

一、单项选择题（本题共20小题，每小题1分，共20分，在每小题给出的四个选项中，只有一项是符合题目要求的）

1. 下列哪种技术在机器人视觉系统中主要用于图像边缘检测？（ ）

A. 直方图均衡化

B. 拉普拉斯算子

C. 小波变换

D. 主成分分析

2. 在图像处理中，以下哪个概念描述的是图像中像素值的分布？（ ）

A. 直方图

B. 滤波器

C. 卷积

D. 四叉树

3. 关于图像的分辨率，以下哪个说法是正确的？（ ）

A. 分辨率越高，图像质量越差

B. 分辨率与图像显示的大小无关

C. 分辨率与图像的存储大小成正比

D. 分辨率是指图像中每英寸的像素点数

4. 下列哪种图像滤波器是非线性的？（ ）

A. 高斯滤波器

B. 中值滤波器

C. 平均滤波器

D. 梯度滤波器

5. 下列哪种方法不常用于图像增强？（ ）

A. 对比度拉伸

B. 灰度变换

C. 频率域滤波

D. 图像锐化

6. 在机器视觉中，下列哪种传感器不常用于获取图像信息？（ ）

A. 摄像头

B. 激光雷达

C. 红外传感器

D. 超声波传感器

7. 关于OpenCV库，以下哪个描述是正确的？（ ）

A. 它是一个用于机器学习的开源库

B. 它不支持多种编程语言接口

C. 它专门用于图像处理和计算机视觉

D. 它只能运行在Windows操作系统上

8. 在图像分割中，下列哪种方法是基于阈值的？（ ）

A. 区域生长

B. 水平集方法

C. 阈值分割 D. 边缘检测

9. 下列哪种图像格式不支持无损压缩？（ ）

A. PNG

B. JPEG

C. TIFF

D. GIF

10. 关于图像金字塔，以下哪个描述是错误的？（ ）

A. 它用于图像的多尺度表示

B. 金字塔的每一层图像都是前一层图像的放大版本

机器视觉基础知识题库单选题100道及答案解析

机器视觉基础知识题库单选题100道及答案解析

机器视觉基础知识题库单选题100道及答案解析

1. 机器视觉系统中，用于采集图像的设备通常是（ ）

A. 传感器 B. 相机 C. 镜头 D. 光源

答案：B

解析：相机是机器视觉系统中用于采集图像的主要设备。

2. 以下哪种光源在机器视觉中常用于检测物体表面的缺陷？（ ）

A. 环形光源 B. 条形光源 C. 同轴光源 D. 点光源

答案：C

解析：同轴光源能突出物体表面的不平整，常用于检测表面缺陷。

3. 机器视觉中，图像分辨率的单位通常是（ ）

A. dpi B. ppi C. lpi D. mpi

答案：B

解析：ppi（Pixels Per Inch）是图像分辨率的常用单位。

4. 图像的灰度级通常用（ ）来表示

A. 二进制数 B. 十进制数 C. 十六进制数 D. 八进制数

答案：A

解析：图像的灰度级一般用二进制数表示。

5. 机器视觉中，用于提取图像特征的算法属于（ ）

A. 图像增强 B. 图像分割 C. 图像识别 D. 图像压缩

答案：C

解析：图像识别的过程包括提取图像特征。

6. 以下哪种图像滤波算法可以有效去除椒盐噪声？（ ）

A. 中值滤波 B. 均值滤波 C. 高斯滤波 D. 双边滤波

答案：A

解析：中值滤波对椒盐噪声有较好的去除效果。

7. 在机器视觉中，边缘检测常用的算法是（ ）

A. Sobel 算子 B. Laplacian 算子 C. Canny 算子 D. 以上都是

答案：D

解析：Sobel 算子、Laplacian 算子和 Canny 算子都常用于边缘检测。

8. 机器视觉系统的精度主要取决于（ ）

A. 相机分辨率 B. 镜头精度 C. 图像处理算法 D. 以上都是

答案：D

解析：相机分辨率、镜头精度和图像处理算法都会影响机器视觉系统的精度。

9. 以下哪种颜色空间在机器视觉中常用于颜色检测？（ ）

2023-2024高一秋季学期信息技术期末测试

2023-2024高一秋季学期信息技术期末测试

2023-2024高一秋季学期信息技术期末测试

1. 一幅未经压缩的1024*512像素的BMP黑白图像，其存储容量约为（） [单选题]

*

A．64KB(正确答案)

B．128KB

C．512KB

D．1MB

答案解析：本题考查图像文件容量相关内容。BMP黑白图像，其1个像素所占位数为1。故该图像文件容量=像素*颜色深度/8=1024*512*1/（8*1024）=64KB，故本题答案是A选项。

2. 采集的音频文件最终以什么进制形式存储在计算机里（） [单选题] *

A．二进制(正确答案)

B．八进制

C．十进制

D．十六进制

答案解析：本题考查数字化编码相关内容。文本、图像、声音、视频等内容在计算机内都是以二进制形式存在。故本题答案是A选项。

3. 要把连续的音频信号存放在计算机中，必须将模拟声音数据转换为数字数据，正确的步骤是（） [单选题] *

A．采样、编码、量化 B．编码、采样、量化

C．量化、编码、采样

D．采样、量化、编码(正确答案)

答案解析：本题考查音频数字化相关内容。将声音的模拟信号转变成数字信号的过程通常需要3个步骤：采样、量化和编码。采样是在模拟信号的连续量中按一定的时间间隔取值得到一组离散的值。量化是指把采集到的离散模拟信号转化为能用有限位数的二进制数码表示的整数值。编码是将量化后的整数值按某种编码方案并结合数据压缩技术重组二进制码字最终产生能够还原为声音的数字信号集。故本题答案是D选项。

4. 存储一幅像素为30×30，颜色深度为8位的位图图像，其存储容量约为（）字节。 [单选题] *

A．9

B．240

C．7200

D．900(正确答案)

答案解析：本题考查位图图像存储容量。位图图像的存储容量可以通过以下公式计算：存储容量 = 图像宽度 × 图像高度 × 每像素位数 / 8。在这个问题中，图像尺寸为30×30像素，颜色深度为8位。因为每个像素占用8位，所以每个像素需要1字节来存储。计算得到存储容量为：30 × 30 × 8 / 8 = 900 字节。故答案为：D。