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

doi:10.3969/j.issn.1000-565X.2011.07.017

华南理工大学学报（自然科学版） ›› 2011, Vol. 39 ›› Issue (7): 102-108.doi: 10.3969/j.issn.1000-565X.2011.07.017

• 电子、通信与自动控制 • 上一篇下一篇

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

朱明^1,2梁栋^1,2†唐俊^1,2范益政^2,3颜普^1,2

1．安徽大学电子信息工程学院，安徽合肥 230039;2．安徽大学计算智能与信号处理教育部重点实验室，安徽合肥 230039; 3．安徽大学数学科学学院，安徽合肥 230039

收稿日期:2010-12-23 修回日期:2011-03-17 出版日期:2011-07-25 发布日期:2011-06-03
通信作者: 梁栋(1963-)，男，教授，博士生导师，主要从事计算机视觉、图像处理、模式识别研究．E-mail: dliang@ahu．edu．cn E-mail:zhu_m@163.com
作者简介:朱明(1984-) ，男，博士生，主要从事计算机视觉、图像处理、模式识别研究．
基金资助:
国家自然科学基金资助项目( 60772121， 11071002) ; 教育部科学技术研究重点项目( 210091) ; 高等学校博士学科点专项科研基金资助项目( 20103401110002) ; 安徽省优秀青年科技基金资助项目( 10040606Y33) ; 安徽省教育厅自然科学研究项目( KJ2011A008) ; 安徽大学创新团队支持计划项目( KJTD007A，KJTD001B)

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

Zhu Ming^1,2Liang Dong^1,2Tang Jun^1,2Fan Yi-zheng^2,3Yan Pu^1,2

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)

摘要/Abstract

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

关键词: 模式匹配, 线图, 无符号Laplacian 矩阵, Q-谱, KM 算法

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

中图分类号:

Tp391

朱明梁栋唐俊范益政颜普. 基于线图Q-谱的点模式匹配算法[J]. 华南理工大学学报（自然科学版）, 2011, 39(7): 102-108.

Zhu Ming Liang Dong Tang Jun Fan Yi-zheng Yan Pu. Point Pattern Matching Algorithm Based on Q-Spectrum of Line Graph[J]. Journal of South China University of Technology (Natural Science Edition), 2011, 39(7): 102-108.

[1]	林培群陈丽甜雷永巍. 基于K近邻模式匹配的地铁客流量短时预测[J]. 华南理工大学学报（自然科学版）, 2018, 46(1): 50-57.
[2]	朱明梁栋范益政张艳颜普. 基于谱特征的图像匹配算法[J]. 华南理工大学学报（自然科学版）, 2015, 43(9): 60-66.
[3]	李拥军敖道敢. 一种快速模式近似匹配算法[J]. 华南理工大学学报(自然科学版), 2012, 40(6): 103-108.
[4]	徐克付齐德昱郑伟平钱正平. 一种基于Bloom Filter的正则表达式集合快速搜索算法[J]. 华南理工大学学报（自然科学版）, 2009, 37(4): 37-41.
[5]	徐克付齐德昱钱正平向军郑伟平. 一种网络分组内容线速动态检测方法[J]. 华南理工大学学报（自然科学版）, 2008, 36(9): 15-19.
[6]	梁俊斌徐建闽. 基于感应线圆的骑线车辆检测方法[J]. 华南理工大学学报（自然科学版）, 2007, 35(7): 20-24.
[7]	刘有延侯志林姚源卫旷卫民傅秀军. 本征模式匹配理论在经典波传播中的应用[J]. 华南理工大学学报（自然科学版）, 2007, 35(10): 214-220.
[8]	刘勇曾敏刚唐东平. 基于ERP系统的制造业库存分析方法[J]. 华南理工大学学报(自然科学版), 2004, 32(3): 66-69.

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

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

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

本文评价