Journal of South China University of Technology (Natural Science Edition) ›› 2011, Vol. 39 ›› Issue (7): 102-108.doi: 10.3969/j.issn.1000-565X.2011.07.017

• Electronics, Communication & Automation Technology • Previous Articles     Next Articles

Point Pattern Matching Algorithm Based on Q-Spectrum of Line Graph

Zhu Ming1,2  Liang Dong1,2  Tang Jun1,2  Fan Yi-zheng2,3  Yan Pu1,2   

  1. 1. School of Electronics and Information Engineering,Anhui University,Hefei 230039,Anhui,China;2. Key Laboratory Intelligent Computing and Signal Processing of the Ministry of Education,Anhui University,Hefei 230039,Anhui,China; 3. School of Mathematical Sciences,Anhui University,Hefei 230039,Anhui,China
  • Received:2010-12-23 Revised:2011-03-17 Online:2011-07-25 Published:2011-06-03
  • Contact: 梁栋(1963-)，男，教授，博士生导师，主要从事计算机视觉、图像处理、模式识别研究．E-mail: dliang@ ahu．edu．cn E-mail:zhu_m@163.com
  • About author:朱明(1984-) ，男，博士生，主要从事计算机视觉、图像处理、模式识别研究．
  • Supported by:

    国家自然科学基金资助项目( 60772121， 11071002) ; 教育部科学技术研究重点项目( 210091) ; 高等学校博士学科点专项科研基金资助项目( 20103401110002) ; 安徽省优秀青年科技基金资助项目( 10040606Y33) ; 安徽省教育厅自然科学研究项目( KJ2011A008) ; 安徽大学创新团队支持计划项目( KJTD007A，KJTD001B)

PDF

935

Abstract:

As most spectrum-based algorithms cannot effectively deal with the matching of size-variable point sets,a point pattern matching algorithm based on the Q-spectrum of line graph is proposed. In this algorithm,first,a weighted complete graph is constructed for each point set,and a line graph is constructed for each point by using the incident first k shortest edges. Then,a spectral decomposition is performed for the signless Laplacian matrix
constructed with the line graph,and the eigenvalues ( Q-spectrum) obtained from the spectral decomposition are used to represent the features of the point,which make it possible to calculated the matching probability. Finally,the optimal matching of point sets is searched by using the KM algorithm. Experimental results show that the proposed algorithm is of high matching accuracy,and that it can deal with the matching of two point sets with different sizes.

Key words: pattern matching, line graph, signless Laplacian matrix, Q-spectrum, KM algorithm

CLC Number: