首页 矩形NAM图像表示模型的存储与运算方法研究(可编辑)

矩形NAM图像表示模型的存储与运算方法研究(可编辑)

举报
开通vip

矩形NAM图像表示模型的存储与运算方法研究(可编辑)矩形NAM图像表示模型的存储与运算方法研究(可编辑) 矩形NAM图像表示模型的存储与运算方法研究 华中科技大学 博士学位论文 矩形NAM图像表示模型的存储与运算方法研究 姓名:夏晖 申请学位级别:博士 专业:计算机应用技术 指导教师:陈传波 20090425华 中 科 技 大 学 博 士 学 位 论 文 摘 要 将非对称逆布局模式表示模型用于图像的表示,研究了一种基于光栅扫描顺序 搜索起始点,按面积最大值匹配矩形的不重叠分解方案的矩形 NAM图像表示方法, 给出了该矩形 NAM 图像表示方...

矩形NAM图像表示模型的存储与运算方法研究(可编辑)
矩形NAM图像表示模型的存储与运算方法研究(可编辑) 矩形NAM图像表示模型的存储与运算方法研究 华中科技大学 博士学位论文 矩形NAM图像表示模型的存储与运算方法研究 姓名:夏晖 申请学位级别:博士 专业:计算机应用技术 指导教师:陈传波 20090425华 中 科 技 大 学 博 士 学 位 论 文 摘 要 将非对称逆布局模式表示模型用于图像的表示,研究了一种基于光栅扫描顺序 搜索起始点,按面积最大值匹配矩形的不重叠分解MATCH_ word word文档格式规范word作业纸小票打印word模板word简历模板免费word简历 _1711642053983_0的矩形 NAM图像表示方法, 给出了该矩形 NAM 图像表示方法的编码算法和解码算法并 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 了算法的时空复杂 度,接着给出了采用直接存储方法存储矩形 NAM 图像时的存储结构并分析了数据 量,最后提出了存储方法的改进思路。 二值矩形 NAM 图像表示的单值存储方法通过减少需要保存的子模式实例数 和 不保存子模式实例的 v域的方式来减少数据量,全值存储方法通过不保存子模式实 例的 x、y 域来减少数据量,理论证明与直接存储相比单值存储和全值存储方法能 提高压缩比 2倍左右。 限制矩形大小的存储方法通过限制全值存储时的子模式实例的矩形大小来降低 w、h 域所需要的存储位数,从而达到提高压缩比的效果。限制矩形大小的存储方 法需要根据图像复杂度来选择合适的最大矩形才能得到较好的压缩比。 分类存储方法根据矩形大小对子模式实例进行分类,不同分类的子模式实例其 w、h 域用不同的存储位来保存,通过减少保存小尺寸矩形子模式实例所需要的数 据量来达到提高压缩比的目的。实验数据表明分类存储方法能够有效提高单值存储 的压缩比。 将子模式实例作为一个整体进行 Huffman编码的存储方法可以利用子模式实例 之间的相关性提高压缩比。为了统一和减少编码单元,提出了 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 子模式实例的存 储方法,任何一个矩形可以由一个较小的基础矩形经过不大于三个基础运算而得 到,基础矩形和基础操作代替原矩形作为 Huffman编码单元。为了不存储 Huffman 编码树,提出了预定义码字的存储方法,并给出了一个通过对多幅有代表性的二值 图像进行统计分析得出的预定义码字表。实验数据表明,与全值存储相比,子模式 实例的 Huffman编码存储方法、规范子模式实例的存储方法、预定义码字的存储方 法压缩比都有显著的提高。 灰度矩形 NAM 图像表示可分为直接表示和位平面分解表示两种。直接表示的 灰度矩形 NAM图像可以通过全值存储、限制矩形大小存储以及 Huffman编码存储 来提高压缩比。位平面分解表示的灰度矩形 NAM 图像存储时直接利用二值图像的 I华 中 科 技 大 学 博 士 学 位 论 文 存储方法。针对二进制码位平面分解的不足,提出了格雷码位平面分解方法,格雷 码位平面的图像复杂度要低于二进制码位平面,可以获得更高的压缩比。 实验数据表明,改进的二值矩形 NAM图像的压缩比是四元树的 5.45到 9.70倍、 行程编码的 2.16至 5.09倍、 CCITT G3标准的 1.42至 2.82倍、 CCITT G4标准的 0.55 至 0.87倍;改进的灰度矩形 NAM图像的压缩比是行程编码的 1.01到 1.72倍,GIF 编码的 0.95到 1.18倍。这些结果表明经过改进的矩形 NAM图像表示的存储方法是 一个高效的存储方法,适用于二值图像和灰度图像的无损压缩。 矩形 NAM 图像表示的格式化方法利用五个队列来重建子模式实例之间的位置 关系,使子模式实例之间的连通关系处理变得更容易。在对连通关系进行分类的基 础上研究了子模式实例连通关系判断、连通关系搜索和连通关系遍历等基础操作, 给出了各算法的时间复杂度分析。连通关系搜索算法的最坏情况复杂度为 OlogN, N为图像的边长;连通关系遍历算法的时间复杂度为 ON ,N 为图像的子模式实 q q 例数。 以子模式实例的连通关系处理算法为基础,分别研究了基于矩形 NAM 图像的 二值图像轮廓提取、欧拉数计算、连通区域标记等图像运算,给出了具体的算法和 分析,并将其与流行的基于其它图像表示的同类相关运算进行了比较。实验数据表 明,采用矩形 NAM表示的二值图像轮廓提取算法的执行时间是矩阵表示的 0.31至 0.86;矩形 NAM表示的欧拉数计算执行时间是模板算法的 0.11至 0.63;矩形 NAM 表示的连通区域标记算法执行时间是矩阵表示的 0.08 至 0.37,四元树表示的 0.05 至 0.12。理论分析和试验结果表明,基于格式化存储结构的矩形 NAM图像在图像 运算方面非常有效。 关键词: 无损压缩 Huffman编码 位平面分解 格雷码 轮廓提取 欧拉数 连通区域标记 II华 中 科 技 大 学 博 士 学 位 论 文 Abstract With the image representation based on Non-symmetry Anti-packing pattern representation ModelNAM, a rectangle NAM Image representation is presented, which searched start point based on raster order, matched rectangle according imum area and decomposed image non-overlapping. Its coding and decoding algorithms are presented and analyzed, then the storage structure of direct storage method is given and data amount is analyzed, finally improvement idea of direct storage method is presented. Single value storage method of binary rectangle NAM image representation can reduce data amount by reducing the number of sub-pattern instance and not saving the v field of sub-pattern instance. Full value storage method reduce data amount by not saving the x, y fields of sub-pattern instance. The compression ratios of Single value storage method and full value storage method are both near 2 times of that of direct storage method. Limited rectangle storage method decreased the bits of the w, h fields by limiting the rectangle size of sub-pattern instance of full value storage method. The limited rectangle storage method need choose appropriate imum rectangle according the complexity of the image. Classified storage method classified sub-pattern instances by their size, then saving the w, h fields with different bits when the class is different. Less sub-pattern instance needed fewer bits. With experimental data, the compression ratio of classified storage method is bigger than that of single value storage. Huffman code of sub-pattern instance can improve compression ratio by reducing the relativity of sub-pattern instance. Its coding unit is the sub-pattern instance. For unifying and decreasing the coding unit, a standard sub-pattern instance storage method is presented. Any rectangle can compounded by a base rectangle and base operations less then three. The base rectangles and operations are new coding unit. For not saving Huffman coding tree, a storage method based on predefined code is presented and a predefined code table is given. With experimental data, the compression ratios of Huffman III华 中 科 技 大 学 博 士 学 位 论 文 code of sub-pattern instance, Huffman code of standard sub-pattern instance and predefined code storage method are all much bigger than that of full value storage method. Gray scale NAM image representation has two representations, direct representation and bit plane decompose representation. The direct represented gray scale NAM image can improve compression ratio by full value storage, limited rectangle storage and Huffman code storage. The bit plane decompose represented gray scale NAM image can use the storage method of binary NAM image directly. Aim at the shortage of bit plane decompose based on binary code, a new bit plane decompose base on Gray code is presented. The complexity of bit plane based on Gray code is less than that based on binary code, so its compression ratio is higher than that based on binary code. With the experimental data, the compression ratio of improved binary NAM image is 5.45 to 9.70 times of that of quadtree, 2.16 to 5.09 times of that of run length code, 1.42 to 2.82 times of that of CCITT G3, and 0.55 to 0.87 times of that of CCITT G4. The compression ratio of improved gray scale NAM image is 1.01 to 1.72 times of that of run length code, 0.95 to 1.18 times of that of GIF image format. As discussed above, the improved storage method of rectangle NAM image is a high performance storage method. It can be used for lossless compression of binary and gray scale image. The formatted method of rectangle NAM image representation reconstructed the ubiety of sub-pattern instance with five queues. It made connectivity operation between sub-pattern instances easier. With the class of connectivity between sub-pattern instances, the based operations of connectivity such as verdict, search and ergod are researched. The complexity of connectivity search at the worst situation is OlogN, N is the side length of image. The complexity of connectivity ergod is ON , N is the number of sub-pattern q q instancesWith the connectivity operation of sub-pattern instance, contour extraction, Euler number computing and connected component labeling of binary rectangle NAM image are researched. With the experimental data, operation time of contour extraction of binary image represented by rectangle NAM is 0.31 to 0.86 times of that of image represented by matrix, operation time of Euler number computing of binary rectangle NAM image is 0.11 to 0.63 times of that of the pattern algorithm, operation time of connected component IV华 中 科 技 大 学 博 士 学 位 论 文 labeling of binary image represented by rectangle NAM is 0.08 to 0.37 times of that of image represented by matrix, 0.05 to 0.12 times of that of image represented by quadtree. Either from theoretical or from experiment, the formatted storage of rectangle NAM image is good at image operation. Key words:Lossless compressionHuffman codeBit-plane decompositionGray code Contour extractionEuler numberConnected component labeling V独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知,除文中已经标明引用的内容外,本论文不包含任何其 他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和 集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人 承担。 学位论文作者签名: 日期: 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借 阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进 行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密?,在年解密后适用本授权书。 本论文属于 不保密?。 (请在以上方框内打“?”) 学位论文作者签名: 指导教师签名: 日期: 年月日 日期: 年月日华 中 科 技 大 学 博 士 学 位 论 文 1 绪论 本章首先介绍本研究的背景、目的和意义,接着简要介绍了跟本论文研究对象 和研究内容相关的国内外发展状况,最后给出本论文的主要研究内容。 1.1 研究背景 图像表示方法的研究由来已久,但是仍然是科学界和工业界非常重视的热门研 究课题。图像表示方法有很多,根据其目的大致可以分为三类:第一类是传统的二 维数组表示方法,它具有直观,算法容易设计等优点,但是所需数据量大是它的缺 点;第二类是专为减少数据量而设计的图像表示方法,这类图像表示方法虽然能得 到很大的压缩比,但是一般不能直接进行图像运算,而且为了追求高压缩比 还会有 [1] 意损失部分图像信息,JPEG图像格式 就是其中的代表;第三类图像表示方法是一 [2-4] 种分层的图像表示方法 ,它既能够减少数据量也能够直接进行一些图像运算,而 [5] 且其基于像素块的运算方式一般能够得到比较快的运算速度,四元树 是这类方法 的典型代表。由于更少的数据量和更快速的运算是图像表示方法所追求的目标,因 [6- 此既紧凑又便于做各种图像处理运算的第三类图像表示方法一直受到人们的关注 8] 。 以四元树为代表的图像分层表示方法在对图像进行分层表示的时候强调分割的 [9] 对称性 ,虽然这样做能够使图像的表示结构便于进行运算,但是由于过于强调对 称性,限制了图像分割的自由度,从而影响的图像的表示效率。基于非对称逆布局 Non-symmetry Anti-packing pattern representation Model, NAM 模式表示模型( )的图 像表示方法采用了一种非对称的图像分割方法,这种分割方法不再强调分割的对称 [10] 性,具有极大的分割自由度,其表示效率要高于四元树 。 [11] 基于 NAM的图像表示方法其表示结果跟所采用的子模式集有关 ,子模式集 的不同使得相应的 NAM 图像表示的存储方法和图像操作都有很大差别。目前关于 NAM 图像表示方法的研究主要集中在两个方面:一是通过研究不同子模式集合的 NAM 图像表示方法来达到提高图像的表示效率的目标;二是研究如何利用 NAM 图像进行运算。本研究以基础的基于矩形子模式的 NAM图像表示方法为研究对象, 提出了改进其存储效率和运算速度的思路和方法,为研究基于其它子模式集的 NAM 1华 中 科 技 大 学 博 士 学 位 论 文 图像表示方法提供了参考。 本文的研究得到了国家高技术研究发展计划“NAM模式表示与识别方法及其 2006AA04Z211 在机器人信息数据库和网站建设中的应用”(项目编号: )的资助。 1.2 研究目的和意义 随着计算机硬件技术水平的提高,越来越大的存储设备和越来越快处理器使得 计算机可以更加有效地进行数字图像处理。但是传统的基于像素矩阵表示的图像中 [12] 冗余信息很多,需要占用大量的存储空间,因此表示效率不高 。针对像素矩阵表 示的图像中存在的冗余信息种类的不同,研究人员提出了很多可以提高表示效率的 [13-15] 图像表示方法 ,虽然这些图像表示方法的表示效率相对像素矩阵表示来说有了 很大的提高,但是人们对既精简又快捷的图像表示方法的研究依然没有停止。 基于 NAM 的图像表示方法拥有的分割的非对称性和子模式集合的开放性,使 其在表示图像方面有很大的自由度,在减少图像表示所需的数据量和提高图像处理 速度方面有很大的潜力,值得深入研究。本研究的目的是以基于矩形子模式的 NAM 图像表示方法为研究对象,深入研究其存储结构和运算方法,提出改进的存储方法, 使矩形 NAM 图像既拥有高压缩比又可以快速进行图像处理和操作。本研究的意义 在于从 NAM图像表示的最根本特性出发,提出的改进的矩形 NAM图像表示的存 NAM 储方法不仅可以达到高效存储和高速运算的目的,还可以为深入研究适合 图 像表示的存储方法以及运算方法提供指导,总的说来,本研究既具有理论上的指导 意义又具有实践上的应用价值。 1.3 国内外发展状况 1.3.1 图像表示方法 传统的数字图像可以用一个二维矩阵来表示,矩阵中的每个元素表示对应位置 [12] 的像素点的颜色值 。这种表示方法非常直观,但由于没有考虑图像的二维相关性, 其表示效率不高。二维矩阵表示的图像在进行图像处理的时候一般采用“点? 点” 的处理方式,因此需要相对较长的处理时间。 针对图像的矩阵表示方法存在的问题,为了减少数据量和提高处理速度,许多 2华 中 科 技 大 学 博 士 学 位 论 文 新的图像表示方法被开发出来。行程编码、边界链码和图像分层结构是其中被广泛 采用的几种表示方法。 [16] 行程编码的提出其主要目的是减少数据量 。它具有简单、直观的特点,其基 本思想是将连续出现的符号串用一个符号值和该符号连续出现的次数来表示,从而 减少直接表示该连续的符号串所需要的数据量。自从 Treuhaft第一次实现了行程编 [17] [18-19] 码系统以来 ,许多研究人员对行程编码方法进行了优化 。由于行程编码的结 构是一维的,其减少的信息冗余也是一维相关的,而图像中的信息冗余是二维相关 的,因此用行程编码表示图像的时候存在着一定的缺陷,其表示效率相对不高。在 许多实用的图像压缩算法中,都是将行程编码方法与其他的编码方法结合来 进行图 [20] 像压缩 。 边界链码也是一种一维的图像表示方法,它沿图像边界像素以 8邻接方式移动, 其移动方向共有 8个:北、东北、东、东南、南、西南、西和西北,每个方向被编 码为 0到 7中的一个数字,因此边界链码可以看作具有特定方向和长度的直线的序 [21] 列 。边界链码编码的对象是图像区域的边界,它能很好地表现区域的轮廓,便于 [22-23] [24] 信息的识别和理解,因此它较广泛的应用于几何性质判断 ,手写识别 和图像 [25] 注册 等领域中。因为边界链码没有描述图像区域内部的信息,很多涉及到图像区 [26] 域的一些基本运算变得难以实现 。 与行程编码和边界链码的一维结构不同,图像分层结构考虑了图像的二维相关 性,因此它在空间上更具紧凑性。由于分层结构在图像运算时通常采用的是“块? [27-28] 块”的运算方式 ,与“点?点”的运算方式相比,这种运算方式有更快的速度, [29-30] 许多图像处理运算都可在分层结构的基础上快速实现 。 四元树是目前研究得最多的一个采用分层结构的图像表示方法,四元树的建立 [31-32] 过程是对图像数据进行递归分割的过程 。首先将图像分割成相同大小 4 个子图 NW NE SW SE 像块,分别用 、 、 、 来表示,然后对每一子图像块进行同样的分割, 当得到的子图像块中的像素的灰度级相等的时候,该子图像块就不在分割。全部分 割过程结束以后可以得到一个四元树,树的根节点表示整个图像,数的叶子节点表 示同一灰度级的子图像块,非叶子节点表示被分割的子图像块。 [33] A. Klinger 首先提出了二值图像的四元树表示方法 ,随后,Hunter 等人对这 3华 中 科 技 大 学 博 士 学 位 论 文 [34-35] [36] 一方法作了进一步的研究 ,H. Samet给出了基于指针的四元树存储结构 ,早 [37-38] 期的四元树表示都是基于指针的四元树结构 。在这种结构中,每个节点用一个 [39] 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 来表示,每个记录包含有一个数据域和五个指针域 。由于这种结构非常浪费 存储空间,不少研究人员对此结构进行了进一步的研究。研究集中在如何减少数据 量上,其主要思想是对叶子节点的类型进行扩充,树中不再保存单一像素的叶子节 点,代替它的是 16种像素块,每个像素块由 4个不再分割的像素构成。这种方法 [40-41] 可以减少四元树的一个层次的节点数 。 为了进一步减少存储空间,Gargantini 提出了线性四元树的表示方法。这种表 示方法不采用指针的形式来存储四元树,它只对图像中的黑色叶子节点进行编码, [42] 编码的依据是该叶子节点的路径 。与四元树的指针结构相比,线性四元树一般可 [43] 66% 节省 的存储空间,与其它编码方法结合还可节省更多的存储空间 。线性四元 树的建立是四元树表示方法一个重大突破,随之而来的很多关于四元树的研究就集 [44] 中在线性四元树上。一部分研究仍然以改进其存储效率为目的 ,还有一部分则主 [45-47] 要研究如何利用线性四元树进行图像处理运算 ,也有部分研究是关于四元树表 [48] 示与其他表示方法的转换,如四元树到光栅图像的转换 。 1.3.2 图像压缩技术 图像表示方法的研究目的在于提高图像的表示效率和运算速度,运算速度主要 由图像表示方法固有的表示结构来决定,而图像的表示效率的提高则需要对图像表 示数据进行压缩,去掉其中的冗余信息。 [49] 图像压缩技术利用了图像数据固有的冗余性和不相干性 ,冗余就是指多余 的、可有可无的信息,不相干就是不重要的、去掉以后不会有太大影响的信息。根 据去掉信息的类型的不同,图像压缩分为有损和无损两种,无损压缩去掉的只是冗 [50] 余的信息,有损压缩去掉的不仅是冗余信息,还去掉了部分不相干的信息 。无损 压缩后的图像解压缩时可以精确还原原始图像,而有损压缩则会损失原始图像的部 分信息,因此有损压缩通常能够得到较高的压缩比。对于一般的普通图像往往采用 有损压缩方法来得到更高的压缩比,而对于非常重要和昂贵的图像则需要采用无损 的压缩方法。 图像压缩有很多有名的方法。虽然它们都是通过去掉原始图像中的冗余信息来 4华 中 科 技 大 学 博 士 学 位 论 文 压缩数据,但是它们所采用的基本原理却不尽相同。下面简要介绍几种常用的图像 压缩方法。 (1)统计方法 统计方法的基本原理是对编码对象出现的概率进行统计,根据概率的不同分别给 予不同长短的代码,这样可以使平均码长达到较低值,从而得到较高的编码效率。如 何构造出好的变长编码方法一直是统计方法的研究重点。 香农-费诺(Shannon-Fano)编码是出现的较早的一个变长编码方法,很容易实 现,它首先将编码对象按照概率从小到大进行排序,然后把它分成两个部分,两部 分的概率和要求相等或者近似相等,这两个部分的编码分别以 0和 1作为开头,然 后对每个部分再按同样的方法进行划分,直到不可分为止,最终可以得到每个对象 的编码。 霍夫曼编码是统计方法中最通用一种编码方法,它的应用非常广泛,它可以直 接用于数据压缩,也可以与其它数据压缩方法进行结合。霍夫曼编码首先根据编码 对象的概率构造一个编码树,然后利用该编码树来生成各对象的编码。自从 [51] D.Huffman提出该方法后 ,霍夫曼编码就成为了数据压缩中广泛研究的主 题。 Hirschberg和 Seiminki通过用一个 2n长的数组来计算 n个符号的字母表的码长的方 [52-53] 法解决当字母表过大时,霍夫曼编码树难易创建的问题 。采用动态霍夫曼编码 (也称自适应霍夫曼编码)可以解决静态霍夫曼编码需要额外保存编码的信息的问 [54-55] 题 。将霍夫曼编码和香农-费诺编码二者结合进行编码(HSF 编码),具有最小 冗余度及码字值按概率大小有序的特点,可以减少翻译表的大小,从而缩短编码、 [56-57] 解码时间 。 霍夫曼方法与香农-费诺方法都只在编码符号概率等于 2的负整数次幂时才能得 到最佳结果。算术编码通过给整个输入流分配码字,而不是给各符号分别分配码字 [58] 的方法克服了这个问题 。算术编码的步骤是首先把当前区间定义为[0, 1,然后依 次取出输入流中的符号,对于每一个取出的符号,根据其概率将当前区间分割为长 度正比于概率的子区间,定义其中的一个子区间为新的当前区间,处理完全部字符 以后,输出能唯一确定当前区间的任何数字。算术编码从原理上来说是一个非常有 [59] 效的压缩方法,它能把符号串压缩到其理论极限 。 (2)字典方法 LZ编码是由 Lempel和 Ziv最早提出的基于字典方法的无损压缩技术,最早的 5华 中 科 技 大 学 博 士 学 位 论 文 [60] LZ编码通常叫做 LZ77编码,它采用的是一种滑动窗的技术 。LZ编码提出以后 立刻就吸引了很多研究者对其进行改进。Storer和 Szymanski开发的 LZSS方法利 用循环队列作为前向缓存器,对分查找树作为搜索缓存器,并且用两个字段的标识 [61] 取代 3 个字段的标识 。LZ78 方法采用一个保存了先前所遇到的字符串的字典来 [62] 代替搜索缓存器、前向缓存器和滑动窗口 。Edward Fiala和 Daniel Greene开发的 [63] LZFG方法将 LZ77和 LZ78进行了混合 。 Ross Williams开发的 LZRW1方法是 LZ77 [64] 的一个简单而快速的变形,它利用 hash表一步找到匹配串 。Ross Williams随后把 字典编码与预测相结合,同时借鉴 LZRW1开发出了 LZRW4方法,这也是 LZ77的 一种变形。 LZW方法是 LZ78的一个非常流行的改进方法,它获得了专利保护,是一种广 [65] 泛使用的方法,其主要特点是 LZW标识中只包含一个指向字典的指针 。LZW算 [66-68] 法的发表引起了数据压缩界的强烈反响,影响了许多人致力于实现和改进它 。 值得注意的是 GIF图像文件格式就是利用 LZW的变形方法对图像数据进行压缩的, 很多流行的数据压缩程序也是基于字典方法的,如 Zip、Arc、Arj等。 (3)预测编码 预测编码是最早采用的图像编码技术之一,主要用于序列图像的压缩编码。预 [69-70] 则编码分为帧内预测编码 和帧间预测编码,其中帧间预测编码利用的是图像序 列相继两帧之间的相关性,去掉的是图像序列时间轴上的冗余信息。 帧间预测编码主要用到了运动补偿,运动估计算法运动补偿的基础。块匹配算 [71] [72] 法 和像素递归算法 是常用的运动估计算法。其中块匹配算被各种运动图像编码 国际标准所采用,具有运算复杂度低和便于实现的特点。目前对运动估计的研究主 [73] [72, 74] 要集中在匹配准则 、搜索方法 等方面,其目标是在平衡匹配精度与搜索速度 之间矛盾的前提下不断提高匹配精度和搜索速度。 (4)变换编码 变换编码的原理是通过映射变换是把图像中各个像素从一个空间变换到另一个 空间,如果选择的映射变换比较合理,变换后产生的系数就会比原系数有效, 其编 [75] 码所需要的数据量就会少很多,从而使图像得到压缩 。变换编码中应用最广泛的 是正交变换编码,它将用空间域表示的图像变换到由正交矢量构成的变换域中,并 对变换后的信号压缩编码。图像经过正交变换后通常可以把散布在各个原坐标系中 较分散的图像数据集中到新坐标系的少数坐标轴上,使数据压缩具有可能性。 6华 中 科 技 大 学 博 士 学 位 论 文 [76] K-L 变换是以图像的统计特性为基础的正交变换 ,它首先将数据本身的相关 矩阵进行对角化,然后利用对角化的结果构成变换。从理论上来讲 K-L变换能完全 消除子像素块内像素间的线性相关性,因此是最优的正交变换。由于 K-L变换的基 向量与编码对象的统计特性有关,是不固定的,而且构造 K-L变换矩阵运算量很大, 因此一般不采用 K-L变换作为实用变换方法,而仅将其作为其它变换方法比较的标 [77] 准 。 Fourier变换是众所周知的一种正交变换,应用于图像编码已经有近 40年的历 [78] 史了,其计算量大的缺点影响了它在图像处理中的应用 。因为离散傅立叶变换DFT 具有快速算法 FFT,而且二维 DFT可由两次一维 DFT实现,所以二维 DFT也拥有 [79] 相应的快速算法 。 离散余弦变换DCT是图像处理中另外一种常用的正交变换。DCT 的变换矩阵 基向量近似于 Toeplitz矩阵的特征向量且与图像内容无关,而 Toeplitz矩阵反映了 [80] 图像信号的相关性,因此 DCT 常被认为是图像压缩中的最佳准变换 。由于二维 DCT变换可以用两次一维 DCT实现、其反变换也可以由两次一维反变换实现,因 [81-82] [83] 此可以大大减小运算量,提高运算速度 。DCT变换特性接近于 K-L变换 ,经 DCT变换后,大部分系数为零,由于只需要对不为零的系数进行编码,因此以达到 [84] 数据压缩的目的 。DCT的应用十分广泛,在很多图像压缩的标准中得到了采用。 早期的基于小波变换的图像压缩方法的核心问题是如何对变换后的小波系数矩 阵进行量化,以及如何对量化后的符号流进行编码,这些问题都可以归结到子带编 码的框架之下,相关的研究大部分集中在小波的频率压缩特性、空域压缩特性以及 系数分布相似性等三个方面。比较有代表性的方法有嵌入式零树小波 [85] EZWEmbedded Zero-tree Wavelet算法 、 SPIHTSet Partitioning in Hierarchical Trees [86] [87-88] 算法 、以及空频域量化 SFQSpace-Frequency Quantization算法 等。 由于传统的小波变换涉及浮点运算,其计算效率低,不利于硬件实现,因而限 制了小波压缩变换的应用。设计整数小波变换 IWTInteger Wavelet Transform成为 [89] 新一轮的研究焦点 。Sweldens等人率先开展了这一研究工作,提出一种不 依赖于 [90-92] Fourier变换的新的双正交小波构造方法?提升方法Lifting Scheme 。Calderbank 等人进一步证明了利用提升方法可直接完成从整数集到整数集的小波变换,并运用 [93] 于图像压缩 。 (5)其他压缩方法 7华 中 科 技 大 学 博 士 学 位 论 文 1988年,Barnsley提出了迭代函数系统IFS的概念,是分形第一次应用于图像 [94] 压缩 。分形压缩的最主要的原理是拼贴定理和不动点理论,它可以利用一组仿射 变换来表示图像的自相似结构,保存这组仿射变换因子就可以通过运算恢复原始图 像,而保存这些因子所需要的数据量要远小于原始数据量,因此分形编码有很好的 压缩效果。分形编码最大的障碍在于如何寻找任意一幅自然图像的分形仿射变换的 [95] 问题 。最初的方法是手工调整或人机交互的半自动方式,编码过程十分艰难。A. E. Jacquin提出了分割迭代函数系统(PIFS)的方法,该方法将图像划分成小块,利用 [96-97] 像素块与图像之间的相似性进行编码 ,解决了自动编码的问题。Y. Fisher 提出 [98] 了基于四叉树分割的编码方法,使编码速度得以进一步提高 ,Monro 提出的编码 [99] 方法不需要进行搜索,分形编码速度速度进一步提高 。由于很多图像本身的分形 特点并不明显,因此限制了分形编码方法的使用范围和压缩效果。 模型基编码属于第二代编码,它的主要原理是通过对图像中的内容进行分析, 获得描述图像中物体的各种特征参数,根据这些特征参数,利用图像合成技术可以 重建图像中的内容,因此存储时只需要存储这些参数。由于特征参数的数据量要远 [100] 小于原始图像数据量,因此能得到非常高的压缩比 。 (6)静态图像压缩标准 ITU(CCITT)二值图像压缩标准 T.4(G3)和 T.6(G4)主要用于传真图像的 压缩。其中 G3算法将一维行程编码与 Huffman编码进行结合。G4采用了二维编码 方法,也称 MMR算法,它是基于二维行程的 MR算法,与 G3相比提高了压缩比, 减少了误差检测的内容。 JBIG是由 ISO和 ITU联合委员会提出和开发的一种二值图像压缩标准,JBIG 扩大了先验区域,编码时采用算术编码。由于采用了自适应的技术,JBIG的编码效 率要比 G3和 G4高。 JBIG2 标准是新的二值图像压缩标准,它有以下特点:压缩性能大大提高;可 以辨认出文本区域、半调区域和普通区域并分别进行压缩;拥有有损和无损两种压 缩方式;支持质量渐进压缩和内容渐进压缩;支持多页文件压缩;拥有灵活的格式, 能很容易的与其他的文件格式结合;支持快速解压缩。JBIG2 标准只是描述了压缩 的原理和压缩文件的格式,并未对编码器进行描述,任何能生成 JBIG2压缩文件的 编码器都是有效的 JBIG2编码器。 JPEG 是联合摄影专家组为单帧彩色图像的压缩标准而制定的,其核心算法为 8华 中 科 技 大 学 博 士 学 位 论 文 离散余弦变换DCT。JPEG具有以下特点:在图像质量很好的时候具有高压缩比; 支持多参数控制压缩比和图像质量;对任何类型的连续色调图像都能很好压缩;支 持顺序模式、渐进模式、无损模式和分级模式进行压缩。 JPEG 2000 也是由联合摄影专家组负责制定的,它采用小波变换为主的多解析 编码方式。JPEG2000有以下特点:比 JPEG的压缩比高;支持有损和无损压缩;支 持渐进传输,可以按照先轮廓后细节的方式传输图像,让图像由朦胧到清晰显示; 支持感兴趣区域(ROI)特性,结合了数据接收方的主观意愿,实现了交互式的压 缩;较强的抗误码能力。 1.3.3 非对称逆布局模式表示模型 非对称逆布局模式表示模型NAM要研究的问题是 Packing 问题的一个反问 题。具体可以描述为:给定一个模式和 N个预先定义的子模式,根据提供的子模式 实例化出一组具体的子模式实例,用这些子模式实例的组合来表示给定的模 式。 非对称是相对与当前许多对称模式表示方法而言的,例如,在四元树表示方法 [36] 中,一个正方形图像被重复地分割为四个相同的子正方形图像块 ,四元树表示方 法不仅强调中每个节点对应的区域是对称的,而且区域的分割方法也是对称的。 NAM 表示方法不对子模式实例和子模式实例的布局做对称性的限制,是一个开放的,自 由度高的模式表示模型,因而具有更高的表示灵活性,能得到更好的表示效率。 [10] 非对称逆布局模式表示模型的形式化描述如下 。 设原模式为 Γ,给定的子模式集合 PP , P , „, P ,其中每个子模式都是由若 1 2 t 干个结构参数来表示的,且参数的顺序是固定的,因此 P中的第 i个子模式可以用 P A , A , „, A 来表示,mi是子模式 P的结构参数个数。NAM编码过程就不断 i 1 2 mi i 的从 P中选择子模式,实例化出具体的子模式实例,然后用这些子模式实例的组合 来表示原模式的过程。实例化得到的子模式实例除了包含具体的结构参数值,还包 含子模式实例的值(在图像模式中,该值就是像素块的颜色值),所以子模式 P的 i 实例可以用 p v, a | aa , a , „, a 来表示,其中 v就是子模式实例的值,a ~a i 1 2 mi 1 mi 分别是结构参数 A ~A 的具体值,因此 NAM编码过程可以表示为: 1 mi n Γ' p , p v,a | a a ,a ,,a 1-1 ? i i 1 2 mi i 1 9华 中 科 技 大 学 博 士 学 位 论 文 对于 NAM 的研究目前主要集中在图像处理领域,研究的主要方向有两个,一 是研究具体的 NAM图像表示方法,二是研究如何利用 NAM图像进行运算。具体 NAM 图像表示方法的研究也有两个侧重点,一是研究不同子模式集合的 NAM 图 [11] 像表示方法 。这样的研究有基于矩形子模式的,基于三角形子模式的,基于梯形 子模式的,以及基于矩形、三角形子模式集合的。研究表明,所提供的子模式集合 自由度高的表示方法其表示效率也高,比如,基于矩形、三角形子模式集合的图像 表示方法其表示效率就要比单纯的基于矩形子模式或三角形子模式的表示方法的表 NAM 示效率高。 图像表示方法的另外一个研究侧重点在于对多值图像的表示方法 的研究。灰度图像和彩色图像都是多值图像,相关研究给出了直接表示的多值图像 [101-103] NAM 的 图像表示方法以及基于位平面分解表示的多值图像的表示方法 。这些 表示方法都有各自的特点,就表示效率而言都高于强调对称性的四元树表示方法。 NAM 对 图像的运算研究目前主要是基于矩形子模式的,相关的研究有图像几何性 质的计算,近邻寻找、钜计算等,研究表明,基于 NAM 图像表示方法的在进行这 些运算时其效率要高于四元树表示的图像。除了上述两种研究方向外,还有对特定 的图像的 NAM表示进行的研究, C. B. Chen等人将 NAM应用于医学图像的表示中, [104] 提高了图像的表示效率 。 1.4 本文的主要研究内容 本文以矩形 NAM 图像为研究对象,研究其存储方法和运算方法。具体来说, 本文研究以下几个问题。 (1)在非对称逆布局模式表示模型的基础上,提出基于矩形子模式的图像表 示方法,给出具体的编码、解码算法以及其存储结构,并分析该存储结构,提出改 进的思路。 (2)对二值矩形 NAM图像表示的存储方法进行改进,针对存储结构的特点, 提出单值存储、全值存储、限制矩形大小、分类存储、子模式实例的 Huffman编码 等改进的存储方法,并给出各种方法的存储结构、编码解码算法以及数据量分析。 对二值矩形 NAM图像表示的 Huffman编码方法进行深入研究,针对静态编码的不 足提出改进的规范子模式实例的方法和预定义码字的 Huffman编码方法,比较并分 析这几种方法。 10华 中 科 技 大 学 博 士 学 位 论 文 (3)借鉴二值图像的存储方法,从直接表示和基于位平面分解表示的两个方
本文档为【矩形NAM图像表示模型的存储与运算方法研究(可编辑)】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_594905
暂无简介~
格式:doc
大小:64KB
软件:Word
页数:0
分类:工学
上传时间:2017-11-13
浏览量:25