基于线图Q-谱的点模式匹配算法

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

针对大多数谱方法不能够较好地处理不同大小点集匹配的问题,提出了一种基于线图Q-谱的点模式匹配算法.首先,对相关点集构造赋权完全图,再对每个点利用与其关联的前k条最短边来构造线图;然后,根据线图构造无符号Laplacian矩阵,对其进行谱分解,并利用谱分解所获得的特征值(Q-谱)来表示点的特征,通过这些特征计算点之间的匹配概率;最后,通过KM算法来寻找点集之间的最优匹配.实验结果表明,文中算法具有较高的匹配精度,可以处理不同大小点集的匹配问题.

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.