【作者】 朱明；

【导师】 梁栋；

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

【摘要】 点模式匹配是模式识别与计算机视觉领域的一个重要的基础性问题,研究成果可以广泛地应用于图像处理、目标识别与跟踪、计算化学、天文学等众多领域。由于待匹配点集间常常存在着较大的差异,使得点模式匹配存在着较高的复杂性,目前仍然是一个尚未完全得到解决的问题,多年来一直是诸多学者研究的热点。图模型是一种有效的结构信息表示方式,利用图模型来表示待匹配点集的结构特征,通过研究图模型的匹配来实现点模式匹配得到了越来越多的关注,也是目前点模式匹配问题的主要研究方向。本文通过构造不同的图模型,采用不同的图模型表示方式对不同情形下的点模式匹配问题进行了研究,主要内容与创新如下：1、提出了一种基于线图Q-谱的点模式匹配算法。首先,分别利用待匹配点集构造赋权完全图；其次,对每个点,利用与其相关联的前k条最短边来构造线图；然后,根据线图构造无符号Laplacian矩阵,并进行谱分解,应用无符号Laplacian矩阵的特征值(Q-谱)来表示点的特征,通过这些特征计算点之间的匹配概率；最后,通过KM算法来寻找点集之间的最优匹配,并将该最优匹配作为最终的匹配结果。该算法可以在平移、缩放、旋转等变换下获得较好的匹配效果,并且还能够处理不同大小点集的匹配问题。实验结果表明了该算法的有效性。2、提出了一种基于局部相对形状上下文与Q-谱的点模式匹配算法。首先,对每个点构造相应的线图,并对线图的无符号Laplacian矩阵进行谱分解；其次,利用分解所获得的特征值计算点的初始匹配概率；然后,通过定义局部相对形状上下文计算点的相似性距离；最后,将Q-谱方法与局部相对形状上下文结合进行概率松弛迭代获得最终的匹配结果。实验结果表明该算法具有较高的匹配精度,提高了Q-谱方法的性能。3、提出了一种基于QR分解的点模式匹配算法。首先,利用待匹配点集构造赋权完全图,并根据赋权完全图构造赋权邻接矩阵；然后,对所构造的赋权邻接矩阵进行QR分解,利用分解所得的正交矩阵进行点集匹配；为了进一步提高匹配的精度,提出了一种简单的通过比较点的前K个最相似邻点的对应关系进行误匹配检测的方法；最后,通过循环检测与匹配获得最终匹配结果。大量的实验结果表明该算法具有较高的匹配精度,并能够在较大仿射变换下获得较好的匹配效果。4、提出了一种基于有向图谱的点模式匹配算法。根据两幅图像所提取的特征点构造赋权完全图,在赋权完全图的基础上,提出一种边定向方法对其进行定向,从而获得有向图；根据有向图,构造反对称矩阵,并对其进行谱分解,利用获得的部分特征向量来表示点的特征,通过比较特征间的距离来实现匹配。从理论上证明了该算法能够处理仿射变换下的点模式匹配问题,模拟实验与真实图像实验证实了该算法的有效性。另外,作为有向图谱算法的一个应用,进行了遥感图像配准,获得了较好的效果。更多还原

【Abstract】 Point pattern matching(PPM) is an important and foundational issue in pattern recognition and computer vision. Its research result is widely used in many areas, such as imge processing, object recognition and tracking, computational Chemistry, astronomy, etc. However, high comlexity exists in PPM due to large difference between the two point sets to be matched. By now, PPM is still an open problem, which is a hot topic many researchers focus on.Graphical model is an effective fashion to express structural information. Many attentions are focused on the way to process the PPM problem with graphical models, which is also the main direction to deal with the PPM problem. We utilize several different graphical models and different graphical-model-denoted ways to deal with the PPM problem. The main contents and innovations are as follows:1. A point pattern matching algorithm based on Q-spectra of line graph is proposed. Firstly, a weighted completed graph is constructed for each point set; Secondly, a line graph is constructed for each point with the first k shortest edges, and then spectral decomposition is performed on the signless Laplacian matrix associated with the line graph. The eigenvalues(Q-spectra) obtained form the spectral decomposition are used to represent the point’s feature, and the matching probability is calculated; Finally, the optimal matching is found by KM algorithm as the final matching result. The proposed algorithm can obtain a better matching result under translation, zoom and rotation etc., and also can deal with the matching problem of the two point sets in different size. Experimental results show that the effectiveness of the proposed algorithm.2. An algorithm for point pattern matching is proposed, which combines local relative shape context and Q-spectra. Firstly, a line graph is constructed for each point, and the spectral decomposition is performed on the signless Laplacian matrix of line graph; Secondly, the eigenvalues obtained from the spectral decomposition are used to represent the point’s feature, and the initial matching probability is calculated; Thirdly, a descriptor named local relative shape context is defined to compute the similarity diatance between any two points; Finally, Q-spectra method is combined with local relative shape context via a probabilistic relaxation approach to get the matching result. Experimental results indicate that the proposed algorithm has a higher accuracy. 3. An algorithm based on QR decomposition (orthogonal-triangular decomposition) is described. Firstly, a weighted complete graph is constructed for each point set; Secondly, QR decomposition is performed on the weighted adjacent matrices associated with the two weighted complete graphs, then the orthogonal matrices obtained from QR decomposition are used to match the two point sets. Thirdly, in order to improve the matching accuracy, we propose a simple method for incorrect matches detecting relied on the correspondence of the first K similar neighbors of the matched pairs. Finally, the frame work of iterative detecting and matching is established to get the matching result. The proposed algorithm, when applied to a wide experimental data, has shown higher accuracy and can achieve a better matching result under large affine transformation.4. A point pattern matching algorithm based on the spectra of directed graphs is presented. Firstly, two weighted complete graphs are constructed with feature points extracted from the two images; Secondly, a method for edge orienting is proposed to transform each weighted complete graph to a directed graph; Thirdly, two skew-symmetric matrices associated with respective directed graphs are established; Fourthly, spectral decomposition is performed on the two skew-symmetric matrices to get a spectral representation of the feature points with half of the eigenvectors; The final matching result is obtained by comparing the spectral representation of each point. We theoretically analyze that our algorithm can well deal with the matching problem under affine transformation. The expreiments applied to synthetic data and real-world images show the effectiveness of our method. Moreover, as an application of this algorithm, we apply it to remote sensing image registration, the result is satisfying.更多还原