【作者】 夏晖；

【导师】 陈传波；

【作者基本信息】 华中科技大学 ， 计算机应用技术， 2009， 博士

【摘要】 将非对称逆布局模式表示模型用于图像的表示，研究了一种基于光栅扫描顺序搜索起始点，按面积最大值匹配矩形的不重叠分解方案的矩形NAM图像表示方法，给出了该矩形NAM图像表示方法的编码算法和解码算法并分析了算法的时空复杂度，接着给出了采用直接存储方法存储矩形NAM图像时的存储结构并分析了数据量，最后提出了存储方法的改进思路。二值矩形NAM图像表示的单值存储方法通过减少需要保存的子模式实例数和不保存子模式实例的v域的方式来减少数据量，全值存储方法通过不保存子模式实例的x、y域来减少数据量，理论证明与直接存储相比单值存储和全值存储方法能提高压缩比2倍左右。限制矩形大小的存储方法通过限制全值存储时的子模式实例的矩形大小来降低w、h域所需要的存储位数，从而达到提高压缩比的效果。限制矩形大小的存储方法需要根据图像复杂度来选择合适的最大矩形才能得到较好的压缩比。分类存储方法根据矩形大小对子模式实例进行分类，不同分类的子模式实例其w、h域用不同的存储位来保存，通过减少保存小尺寸矩形子模式实例所需要的数据量来达到提高压缩比的目的。实验数据表明分类存储方法能够有效提高单值存储的压缩比。将子模式实例作为一个整体进行Huffman编码的存储方法可以利用子模式实例之间的相关性提高压缩比。为了统一和减少编码单元，提出了规范子模式实例的存储方法，任何一个矩形可以由一个较小的基础矩形经过不大于三个基础运算而得到，基础矩形和基础操作代替原矩形作为Huffman编码单元。为了不存储Huffman编码树，提出了预定义码字的存储方法，并给出了一个通过对多幅有代表性的二值图像进行统计分析得出的预定义码字表。实验数据表明，与全值存储相比，子模式实例的Huffman编码存储方法、规范子模式实例的存储方法、预定义码字的存储方法压缩比都有显著的提高。灰度矩形NAM图像表示可分为直接表示和位平面分解表示两种。直接表示的灰度矩形NAM图像可以通过全值存储、限制矩形大小存储以及Huffman编码存储来提高压缩比。位平面分解表示的灰度矩形NAM图像存储时直接利用二值图像的存储方法。针对二进制码位平面分解的不足，提出了格雷码位平面分解方法，格雷码位平面的图像复杂度要低于二进制码位平面，可以获得更高的压缩比。实验数据表明，改进的二值矩形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图像表示的格式化方法利用五个队列来重建子模式实例之间的位置关系，使子模式实例之间的连通关系处理变得更容易。在对连通关系进行分类的基础上研究了子模式实例连通关系判断、连通关系搜索和连通关系遍历等基础操作，给出了各算法的时间复杂度分析。连通关系搜索算法的最坏情况复杂度为O(logN)，N为图像的边长；连通关系遍历算法的时间复杂度为O(N_q)，N_q为图像的子模式实例数。以子模式实例的连通关系处理算法为基础，分别研究了基于矩形NAM图像的二值图像轮廓提取、欧拉数计算、连通区域标记等图像运算，给出了具体的算法和分析，并将其与流行的基于其它图像表示的同类相关运算进行了比较。实验数据表明，采用矩形NAM表示的二值图像轮廓提取算法的执行时间是矩阵表示的0．31至0．86；矩形NAM表示的欧拉数计算执行时间是模板算法的0．11至0．63；矩形NAM表示的连通区域标记算法执行时间是矩阵表示的0．08至0．37，四元树表示的0．05至0．12。理论分析和试验结果表明，基于格式化存储结构的矩形NAM图像在图像运算方面非常有效。更多还原

【Abstract】 With the image representation based on Non-symmetry Anti-packing pattern representation Model(NAM), a rectangle NAM Image representation is presented, which searched start point based on raster order, matched rectangle according maximum 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 maximum 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 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 O(logN), N is the side length of image. The complexity of connectivity ergod is O(N_q), N_q is the number of sub-pattern instances.With 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 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.更多还原