Journal of Computer Applications ›› 2013, Vol. 33 ›› Issue (06): 1686-1690.DOI: 10.3724/SP.J.1087.2013.01686

• Network and distributed techno • Previous Articles     Next Articles

Algorithm of point pattern matching based on quasi Laplacian spectrum and point pair topological characteristics

ZHANG Guanliang1,2,ZOU Huanxin1,LU Chunyan1,ZHAO Jian1   

  1. 1. College of Electronic Science and Engineering, National University of Defense Technology, Changsha Hunan 410073,China
    2. Department of Teaching and Research, Urumqi Command College of Armed Police Force, Urumqi Xinjiang 830049,China
  • Received:2012-12-05 Revised:2013-01-24 Online:2013-06-01 Published:2013-06-05
  • Contact: ZOU Huanxin

基于拟Laplacian谱和点对拓扑特征的点模式匹配算法

张官亮1,2,邹焕新1,卢春燕1,赵键1   

  1. 1. 国防科学技术大学 电子科学与工程学院,长沙 410073
    2. 武警乌鲁木齐指挥学院 教研部,乌鲁木齐 830049
  • 通讯作者: 邹焕新
  • 作者简介:张官亮(1985-),男,陕西渭南人,硕士研究生,主要研究方向:图形与图像处理;邹焕新(1973-),男,广东梅州人,副教授,博士,主要研究方向:多源卫星信息融合处理、SAR图像解译、目标识别;卢春燕(1988-),女(满族),辽宁凤城人,硕士研究生,主要研究方向:图形与图像处理;赵键(1978-),男,湖南临澧人,工程师,博士研究生,主要研究方向:计算机视觉、智能信息处理、遥感图像处理。

Abstract: Concerning the poor robustness of the state-of-art spectrum-based algorithms when the outliers and noises exist,a new and robust point pattern matching algorithm based on Quasi Laplacian spectrum and Point Pair Topological Characteristic (QL-PPTC) was proposed. In this paper, firstly, a signless Laplacian matrix was constructed by using the minimal spanning tree of weighted graph, and then the eigenvalues and eigenvectors obtained from the spectrum decomposition were used to represent the point’s feature, which made it possible to calculate the matching probability. Secondly, the similarity measurement of point pair topological characteristic was computed to define local compatibility between the point pairs, and then correct matching results were achieved by using the method of probabilistic relaxation. The contrast experimental results show that the proposed algorithm is robust when the outliers and noises exist in point matching.

Key words: Point Pattern Matching (PPM), Minimal Spanning Tree (MST), quasi Laplacian spectrum, similarity measurement, Point Pair Topological Characteristics (PPTC), probabilistic relaxation

摘要: 针对谱匹配方法对噪声和出格点的鲁棒性较差的问题,提出了一种基于拟Laplacian谱和点对拓扑特征的点模式匹配算法。首先,用赋权图的最小生成树构造无符号Laplacian矩阵,通过对矩阵谱分解得到的特征值和特征向量表示点的特征,进而计算点的初始匹配概率;其次,利用点对拓扑特征的相似性测度来定义点对间的局部相容性,然后借助概率松弛的方法更新由拟Laplacian谱得到的匹配概率,得出匹配结果。对比实验结果表明,该方法在处理存在噪声和出格点的点集匹配上具有较高的鲁棒性。

关键词: 点模式匹配, 最小生成树, 拟Laplacian谱, 相似性测度, 点对拓扑特征, 概率松弛

CLC Number: