论文部分内容阅读
将非对称逆布局模式表示模型用于图像的表示，研究了一种基于光栅扫描顺序搜索起始点，按面积最大值匹配矩形的不重叠分解方案的矩形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图像在图像运算方面非常有效。