形状分析的新方法及其应用

论文摘要

形状分析是计算机视觉领域的一个重要的研究问题，已经在科学研究领域和工程技术方面有着非常广泛的应用，如目标识别、基于内容的图像检索、文字识别、医疗诊断等。本文通过对现有的形状分析方法的研究，提出了一些新的形状分析方法并分别在遥感图像识别和植物叶形检索中进行了应用。本文的主要工作有三个：(1)提出了一种组合拆分与合并技术的混合遗传算法求解两类多边形近似问题。(2)提出了一种不变的形状描述方法：内角链。(3)提出了一种用于形状检索的基于多级弦长函数的傅立叶描述子。多边形近似是一种重要的形状描述方法，但边界轮廓线的多边形近似的获取是一个非常复杂的问题。有两类多边形近似问题吸引大量研究者的关注，一个是在给定边数的情况下，求解近似误差最小的多边形，另一个是在给定容忍近似误差的情况下，求边数最少的多边形。传统的方法大多基于局部优化方法来进行求解，尽管求解速度很快，但求解质量严重依赖于始点或给定的初始解。一些基于全局优化的方法，如遗传算法、蚁群算法等虽然在一定程度上提高了求解的质量，但求解速度太慢，求解的质量也不太理想而且只能只能求解一类多边形近似问题。本文提出了一种新的能求解两类多边形近似问题的混合遗传算法。该方法针对现有的遗传算法全局优化能力强，但局部搜索能力差，以及在处理不可行解上的困难，采用染色体修复策略处理遗传操作所产生的不可行解，并将传统的拆分与合并技术应用于染色体的修复过程。采用这种方法，一个不可行解不仅能得到快速的修复而且在被修复的同时还能被推进到解空间中一个局部较优的位置。大量的实验结果和与近几年来的相关工作的比较证明了本文提出的方法的优越性。本文还将该方法应用于湖泊地图的多边形近似，并且与其他方法也进行了比较，实验结果表明本文提出的方法具有更好的近似效果和效率，具有实用价值。第二个主要的工作是提出了一种不变的形状描述方法：内角链(IAC)。其主要的思想是首先用一个等边多边形近似一个二维目标的轮廓线，然后用等边多边形的内角构成的内角链作为形状的描述子。两个形状的相似性通过比较他们的内角链来进行度量。本文给出了计算等边多边形近似和其内角链的方法。其主要贡献在于：(1)给出了一种不变的形状描述子，其不变性通过理论和实验都得到了证明。而且这种不变性不需要额外的归一操作来完成。通过对轮廓线的等边多边形近似和用内角链来表示等边多边形，IAC将一般的基于多边形近似这种本质上是二维的描述降维成了一维的描述。也就说一般需要两类特征如角度和边长来表示多边形，现在只需要单一的特征—内角来描述形状。其优点在于使我们摆脱了在计算形状相似度时，要考虑怎样去选择一个合适的权重来平衡不同类特征的贡献所带来的困扰。实验结果证明了IAC的优良的性能。我们还将IAC实际用于湖泊SAR图像的识别，取得了好的识别效果。第三个主要的工作是提出了一种新的傅立叶描述子：基于多级弦长函数的傅立叶描述子(MCLFD)。傅立叶描述子(FD)是一种非常重要的形状描述方法并有着广泛的应用。FD首先对一维轮廓线函数的进行傅立叶变换，用归一化的傅立叶系数作为形状的描述子。其主要优点在于(1)能消除形状信息中的噪声成份，(2)是一种紧致的描述子，(3)易于进行归一化。但南于傅立叶描述子是通过一维轮廓线函数的傅立叶变换得到的，所以其性能与导出它的轮廓线函数密切相关。现有的轮廓线函数存在的主要问题是：(1)要么能刻划形状的整体特征，但对形状的细节信息刻划不足。要么能刻划形状的细节信息，但对形状的整体特征描述不足。(2)一些轮廓线函数计算的复杂度较高而且很不稳定，不太适合实际应用。针对上述问题本文提出了一种新的轮廓线函数：多级弦长函数。多级弦长函数是通过等弧长的分割轮廓线获得的。它对形状的整体特征和细节信息都能进行很好的描述，而且计算非常简单。将多级弦长函数进行傅立叶变换所得到的傅立叶描述子(MCLFD)不仅对目标的平移、缩放、旋转不敏感，而且不依赖轮廓线的起始点。将该方法用1400个形状的测试集进行测试并与其它的傅立叶描述子进行比较。实验结果表明MCLFD要比其他性能最好的傅立叶描述子的平均查准率还要高出10％。本文还将基于多级弦长函数的傅立叶描述子应用于植物叶形的检索，所用的实例有100种植物叶形共1200个叶片，取得了较好的检索性能，而且性能要明显优于其它的傅立叶描述子。从而证明了我们提出的方法具有较高的实际应用价值。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 形状分析研究的内容
• 1.3 形状分析的应用领域
• 1.4 本文的主要贡献
• 1.5 本文的组织
• 2 形状分析方法综述
• 2.1 前言
• 2.2 基于轮廓线的数值型方法
• 2.3 基于轮廓线的非数值型方法
• 2.4 基于区域的数值型方法
• 2.5 基于区域的非数值型方法
• 2.6 本章小结
• 3 一种求解两类多边形近似问题的混合遗传算法
• 3.1 引言
• 3.2 问题描述
• 3.3 混合遗传算法（SMGA）
• 3.4 实验结果和讨论
• 3.5 实际应用
• 3.6 本章小结
• 4 一种不变的形状描述方法:内角链
• 4.1 前言
• 4.2 等边多边形近似
• 4.3 内角链
• 4.4 实验结果和讨论
• 4.5 应用于湖泊SAR图像的识别
• 4.6 本章小结
• 5 一种新的用于形状检索的傅立叶描述子
• 5.1 相关工作
• 5.2 多级弦长函数
• 5.3 多级弦长函数的离散傅立叶分析
• 5.4 实验结果和讨论
• 5.5 应用于植物叶形的检索
• 5.6 本章小结
• 6 总结和下一步的工作
• 6.1 总结
• 6.2 下一步的工作
• 参考文献
• 攻读博士学位期间以第一作者发表的论文
• 致谢