基于NAM的图像集合运算算法及其实验研究

论文摘要

在非对称逆布局模式表示模型（Non-symmetry Anti-packing Pattern Representation Model, NAM）的基础上,提出了一种实现快速的图像集合运算的新方法,即在导航数组（Navigation Array, NA）辅助下的分裂组合法（Split and Combination Method, SCM）,并实现了基于NAM表示的交运算、差运算、并运算和补运算算法,取得了一些有价值的研究成果。为了解决基于NAM操作的块间位置关系问题,提出了一种新的辅助性措施,即导航数组。这种数据结构实现起来简单方便,可以使分散的块间关系重新恢复,因此可以在需要确定位置关系的算法中使用,如近邻寻找、周长计算、连通分量标记等算法中都可以使用这种结构来进行导航,快速找到相邻或有是相交的块,在本课题实现中取得了较好的效果。在研究基于NAM的图像集合运算问题中,提出了一种新的实现快速无重叠的图像集合运算算法,即分裂组合法。这种算法基于分裂的思想,在不断地分裂过程中,将所需要的部分保留下来,形成集合运算最终的结果。当然,这种运算还有另外一个好处,就是使得集合运算的实现具有很大的相似性,让程序结构更加清晰明了。为了与本课题的实验结果进行比较,还实现了线性四元树的编码解码算法以及基于紧凑四元树（Compact Improved Quadtree, Compact-IQ）的编码、解码和集合运算算法。在对给定的8幅二值图像的实验中,首先比较了基于NAM表示的结点数比线性四元树和紧凑四元树压缩了2.914和1.775倍,在与紧凑四元树的集合运算效率的比较中,基于NAM的集合运算算法普遍比基于紧凑四元树的集合运算算法运行效率要高,从加速比中表现得相当明显,关于交、差、并、补运算的平均加速比为1.877、4.034、2.140、2.892,实验证明,基于NAM表示的集合运算算法比基于紧凑四元树的集合算法的效率更高。理论分析和实验结果表明,导航数组辅助下的分裂组合法是一种有效解决基于NAM集合运算的新方法。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 研究目的和意义
• 1.3 国内外发展状况
• 1.4 本文主要研究内容
• 2 相关理论分析
• 2.1 图像的分层数据结构
• 2.2 紧凑四元树表示
• 2.3 非对称逆布局模式表示模型
• 2.4 本章小结
• 3 基于NAM 的图像集合运算算法
• 3.1 导航数组及其生成算法
• 3.2 交运算算法
• 3.3 差运算算法
• 3.4 并运算算法
• 3.5 补运算算法
• 3.6 本章小结
• 4 实验结果及分析
• 4.1 实验系统
• 4.2 实验数据
• 4.3 实验结果及分析
• 4.4 本章小结
• 5 总结与展望
• 5.1 全文总结
• 5.2 研究展望
• 致谢
• 参考文献