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

【作者】 王斌；

【导师】 陈雁秋；

【作者基本信息】 复旦大学 ， 计算机应用技术， 2006， 博士

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

【Abstract】 Shape analysis is an important topic in computer vision and has won wide applications such as object recognition, content based image retrieval, OCR, medical diagnosis and so on. In this paper, several novel shape analysis methods are proposed and are applied in recognition of remotely-sensed image and plant-shape retrieval. The main work of this paper are as follows: (1) A hybrid genetic algorithm combined with split and merge technique is proposed to solve two types of polygonal approximation problems. (2) An invariant shape representation, interior angle chain, is proposed. (3) A novel Fourier descriptors derived from multi-level chord length function is proposed for shape retrieval.Polygonal approximation is an important shape representation method. However, acquiring a polygonal approximation of a boundary contour is a difficult task. There are two polygonal approximation problems which have attracted many researcher’s attention. One is that given a digital curve, approximate it by a polygon with a given number of sides so that the approximation error is minimized. Another one is that given a digital curve, approximate it by a polygon with the minimum number of sides so that the approximation error does not exceed a given tolerance error. Traditional methods such as split and merge technique for polygonal approximation problem has a fast computational speed, but the quality of solution depend heavily on the starting point or the given initial solution. Although many global search technique based method such as genetic algorithm, ant colony optimization algorithm and so on can improve the quality of solution in some extent, the computational speel is very slower and the quality of solution is still not ideal and they can solve only one type of polygonal approximation problem. In this paper, a hybrid genetic algorithm is proposed for two types of polygonal approximation problems. Consider the difficulty of disposing the infeasible solution and the poor local search ability, we proposed a chromosome repairing scheme combined with traditional split and merge technique to dispose the infeasible solution. The advantage of this scheme is that an infeasible solution can not only be repaired but can also be pushed into a local optimal location in solution space. Experimental results and comparisons with other relative work show the superiority of our method. The proposed method has also been successfully applied to the polygonal approximation of contour of the lake in map.The second work is that an invariant shape representation, Interior angle chain (IAC), is proposed. The main idea is that an object’s contour is firstly approximated by a equilateral polygon, the interior angle chain of the equilateral polygon is then calculated todescribe the shape.The similarity between two shapes can be measured by their IACs. The main contributions of our work are as follows. (1) An invariant shape representation is proposed and its invariance has been proved in theory. It is noted that the invariance doesn’t require additional normalizing against the shape descriptor. (2) IAC reduces the number of dimension of the shape descriptor. The experimental results show its superior performance. IAC has also been applied to lake recognition in SAR images and all shown good results.The third work is that a novel Fourier descriptors derived from multi-level chord length function is proposed. Fourier descriptors is an important shape representation method and has won wide applications. Its main advantages are as follows: (1) it can remove the noise of the shape representation. (2) it is an impact descriptor. (3) it is very easy to be normalized to achieve invariance to scaling, translation, rotation. However, Fourier descriptors is affected by the contour function which is derived from. While the contour function exists the disadvantage of not considering all the shape information including the global shape information and the detail information for characterizing the shape. Considering the above problem, we proposed a novel contour function, multi-level contour function, which is obtain by equal-arc-length partitioning the contour. The contour function can not only characterize the global information but also consider the detail information. Its computation is also very simple. We derive the fourier descriptors from the multi-level contour function for achieving invariance to translation, scale, rotation and starting point. We use a large benchmark containing 1400 shapes to test the performance of MCLFD. The experimental shows that the average precision of MCLFD achieves 10 percentage higher that the other Fourier descriptors. We also applied it to the plant shape retrieval and the all results show that MCLFD is a promising shape descriptor.更多还原