【作者】 潘鸿飞；

【导师】 陈军宁； 梁栋；

【作者基本信息】 安徽大学 ， 电路与系统， 2011， 博士

【摘要】 形状识别与聚类是人工智能、数据检索、计算机视觉和模式识别等领域的基础性研究课题。该课题的研究方向主要是在无先验(已知)类别标准的条件下,以形状的有关特征作为判断依据,实现聚类。而相关特征的选取及其结构分析,一直是形状识别与聚类问题的重点和难点。近年来,通过提取形状特征,以动态规划、谱图理论、中轴变换、数据降维等为手段,研究形状的结构特征的方法,日益受到众多学者的关注,成为相关研究领域的热点。本文在形状结构特征提取、分析以及形状的识别和聚类方面做了较为系统的研究,主要研究内容和创新之处有以下四个方面：1、提出一种基于编辑距离与动态规划的形状识别与检索算法。首先,利用中轴变换提取形状的骨架特征；然后,将该骨架特征点以字符串的形式表示,利用编辑距离算法,比较字符串间的距离；最后,运用动态规划实现形状的识别与检索。该算法利用骨架特征,较好地处理了形状的非刚体形变的问题。而从空间特征到字符串特征的转换,则为解决特征比较问题提供了新的思路,同时也有利于增强算法的鲁棒性。比较实验说明该算法对非刚体形变有较好的识别效果。2、提出了一种基于谱图理论的形状描述、识别与聚类算法。该算法主要研究两个方面的问题：(1)通过提取形状的骨架特征点和图谱分析,以特征值描述形状的结构特征；(2)运用主成分分析,将上述特征值投影到低维空间中,利用该方法实现了形状的聚类。算法以特征点间的空间关系和角度关系为基础,综合应用各种结构信息,增强了算法的鲁棒性。针对公共数据集的仿真实验说明了该聚类算法对具有较大形变的形状仍有较好的聚类效果。3、提出了一种利用Laplace谱特征与多维尺度法相结合的形状识别与聚类算法。首先,提取形状的轮廓点作为特征点,并构造Laplace矩阵；然后,以Laplace矩阵的特征值来刻画图的结构信息；最后,利用多维尺度法,将由各类形状的轮廓点构成的序列图投影至低维空间,在该空间内分析形状的分布情况,实现聚类。在上述算法中,形状的特征由一组向量表示,向量的维数越大,越能充分地反映其结构的特征,但却不利于聚类结果的比较。为了解决该问题,引入了数据降维的方法,实现了三维空间中形状聚类结果的可视化。对比实验的结果说明了该算法有较好的聚类效果。4、提出一种将Laplace矩阵的谱与随机游走模型相结合,用以表示图结构特征的形状聚类算法。针对形状的不同空间结构特征,通过对轮廓点所构完全图的Laplace矩阵的特征值以及图的随机游走模型概率性质的分析,建立了描述轮廓点空间结构特征的数学模型。以此模型为基础,定义状态向量,实现了形状的识别与聚类。随机游走模型可从概率统计的角度分析图的结构特征,增强了数据分析的稳定性。对比实验说明了提出的数学模型能较好地反映形状的空间结构,而在此基础上定义的状态向量则为形状聚类提供了稳定而有效的判断依据。更多还原

【Abstract】 Shape recognition and clustering are the key point in artificial intelligence, computer vision and pattern recognition. One of the most commonly encountered problems in shape clustering is how to select the feature without any given information. In recent years, dynamic programming, spectral graph theory, medial axis transform and data dimensionality reduction have received a lot of attention.This dissertation mainly discusses feature extraction, shape recognition and clustering. The main and pioneering works of this paper are as follows:1. An important task in pattern recognition is to cluster the given shapes. The proposed algorithm focuses on the shape recognition and retrieval. The algorithm first extracts the skeletal features using the medial axis transform. Then, the features are transformed into a string of symbols with the similarity among those symbols computed based on the edit distance. Finally, the shapes are identified using dynamic programming. Two public data sets are applied to verifying that the present approach is better than the compared approaches.2. Spectral graph theory has been exploited widely for the purpose of shape representation, matching and clustering. The proposed algorithm focuses on two problems:Firstly, we use skeletal feature points and spectrum to build up the mathematic model of the shape. Secondly, we embed shapes into a low dimensional space by analyzing the mathematic characteristic of the given models. Meanwhile, the simulation of clustering is achieved by studying the distribution of shapes in this space. Experiments on the public data sets illustrate that the presented algorithm is feasible for shape clustering.3. The spectrum of a graph has been widely used to characterize the properties of a graph and extract information from its structure. In this paper, we investigate the performance of Laplacian spectrum and multidimensional scaling (MDS) as shape recognition and clustering. Firstly, we extract boundary points to characterize the shape and to construct the Laplacian matrix. Secondly, the structural information of graph is described by using the eigenvalues of the Laplacian matrix. Finally, the given shapes are projected onto a low-dimensional space by performing MDS. Meanwhile, the clustering is achieved via analyzing the distribution of shapes. Comparative experiments on the public data sets demonstrate the validation of the proposed algorithm.4. Shape recognition and clustering are the key point in artificial intelligence and pattern recognition. By utilizing singular value decomposition (SVD) of Laplacian matrix and random walk model, mathematical model of shape structural feature is constructed. Based on this model and the public data sets, shape clustering is achieved by using state-vector. Moreover, the experimental results illustrate that the performance of proposed approach is better than that of other compared algorithms.更多还原