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

doi:10.3724/SP.J.1087.2013.01686

计算机应用 ›› 2013, Vol. 33 ›› Issue (06): 1686-1690.DOI: 10.3724/SP.J.1087.2013.01686

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

张官亮¹,²,邹焕新¹,卢春燕¹,赵键¹

1. 国防科学技术大学电子科学与工程学院,长沙 410073
2. 武警乌鲁木齐指挥学院教研部,乌鲁木齐 830049

收稿日期:2012-12-05 修回日期:2013-01-24 出版日期:2013-06-01 发布日期:2013-06-05
通讯作者: 邹焕新
作者简介:张官亮（1985-），男，陕西渭南人，硕士研究生，主要研究方向:图形与图像处理;邹焕新（1973-），男，广东梅州人，副教授，博士，主要研究方向:多源卫星信息融合处理、SAR图像解译、目标识别；卢春燕(1988-)，女（满族），辽宁凤城人，硕士研究生，主要研究方向:图形与图像处理；赵键（1978-），男，湖南临澧人，工程师，博士研究生，主要研究方向:计算机视觉、智能信息处理、遥感图像处理。

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

ZHANG Guanliang¹,²,ZOU Huanxin¹,LU Chunyan¹,ZHAO Jian¹

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-05 Published:2013-06-01
Contact: ZOU Huanxin

摘要/Abstract

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

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

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

中图分类号:

TP391

张官亮邹焕新卢春燕赵键. 基于拟Laplacian谱和点对拓扑特征的点模式匹配算法[J]. 计算机应用, 2013, 33(06): 1686-1690.

ZHANG Guanliang ZOU Huanxin LU Chunyan ZHAO Jian. Algorithm of point pattern matching based on quasi Laplacian spectrum and point pair topological characteristics[J]. Journal of Computer Applications, 2013, 33(06): 1686-1690.

参考文献

[1] MCKEON R T, FLYNN P J. Three-dimensional facial imaging using a Static Light Screen (SLS) and a dynamic subject［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010,59(4):774-783.

[2] JACKSON B P, GOSHTASBY A A. Registering aerial video images using the projective constraint ［J］. IEEE Transactions on Image Processing, 2010,19(3):795-804.

[3] FELZENSZWALB P F. Representation and detection of deformable shapes［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(2):208-220.

[4] LIU Z, SHEN H. Tracking objects using shape context matching［J］.Neurocomputing,2012, 83(4):47-55.

[5] FINN P W, KAVRAKI L E, LATOMBE J C. RAPID: Randomized pharmacophore identification for drug design ［J］. Computational Geometry,1998,10(4):263-272.

[6] AKUTSU T, KANAYA K, OHYAMA A, et al. Point matching under non-uniform distortions［J］. Discrete Applied Mathematics, 2003,127(1):5-21.

[7] MCAULEY J J,CAETANO T S,BARBOSA M S. Gragh rigidity cyclic belief propagation and point pattern matching ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(11): 2047-2054.

[8] BESL P J, MACKAY N D. A method for registration of 3D shapes［J］. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.

[9] SCOTT G L, LONGUET-HIGGINS H. An algorithm for associating the features of two images［J］.Proceedings: Biological Sciences, The Royal Society, 1991,244(1309): 21-26.

[10] SHAPIRO L S,BRADY J M．Feature-based correspondence: An eigenvector approach［J］.Image and Vision Computing,1992,10(5): 283-288.

[11] CARCASSONI M, HANCOCK E R. Spectral correspondence for point pattern matching［J］.Pattern Recognition, 2003,36(1):193-204.

[12] 赵键, 孙即祥, 李智勇.基于相对形状上下文和谱匹配方法点模式匹配算法［J］. 电子与信息学报, 2010,32(10):2287-2293.

[13] 唐俊,王年,梁栋,等.一种结合形状上下文分析的Laplace谱匹配算法［J］.系统仿真学报,2009,21(14): 4345-4350.

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

[15] LU C Y, ZOU H X, ZHAO J, et al. Point pattern matching algorithm based on point pair topological characteristics and probabilistic relaxation labeling[C]// Proceedings of 2012 International Conference on Electronic Information and Electrical Engineering. Amsterdam: Atlantis Press, 2012:98-102.

[16] LU C Y, ZOU H X, ZHAO J, et al. Point pattern matching algorithm based on point pair topological characteristics and spectral matching［J］. Journal of Electronics,2012, 29(3/4): 279-285.

[17] 刘瓒武.应用图论［M］.长沙：国防科技大学出版社,2006.

[18] CHUI H, RANGARAJAN A. A new point matching algorithm for non-rigid registration［J］. Computer Vision and Image Understanding, 2003,89(2):114-141.

[19] van DAM E R, HAEMERS W. Which graphs are determined by their spectrum? ［J］. Linear Algebra and its Applications，2003,373(1):241-272.

[20]LEE J H, WON C H. Topology preserving relaxation labeling for non-rigid point matching ［J］. IEEE Transaction on Pattern Analysis and Matching Intelligence, 2011, 33(2):427-432.

[21] 梁栋,朱明,唐俊,等. 基于局部相对形状上下文与Q-谱的点模式匹配算法［J］.电子学报,2012,40(4):636-641.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

[1]	韩丽, 刘书宁, 于冰, 徐圣斯, 唐棣. 基于最优最小生成树的三维模型形状优化方法[J]. 计算机应用, 2019, 39(3): 858-863.
[2]	彭磊, 杨秀云, 张裕飞, 李光耀. 基于全局与局部相似性测度的非刚性点集配准[J]. 计算机应用, 2019, 39(10): 3028-3033.
[3]	郭浩, 刘磊, 陈俊杰. 基于高阶最小生成树的脑网络分析及对阿兹海默氏症患者的分类[J]. 计算机应用, 2017, 37(11): 3339-3344.
[4]	王妍, 章婷婷, 宋知润, 王俊陆, 郭敬玉. 基于区域分簇的大规模无线传感器网络生命周期优化策略[J]. 计算机应用, 2015, 35(11): 3031-3037.
[5]	刘洪滨杜玲姬红利. 面向网关版权保护的抗几何攻击视频水印方法[J]. 计算机应用, 2013, 33(12): 3531-3535.
[6]	白雪任晓玲刘希玉. 基于粘贴和2-臂DNA模型的层次聚类算法[J]. 计算机应用, 2013, 33(02): 308-315.
[7]	张明才薛安荣王伟. 基于最小生成树的非均匀分簇路由算法[J]. 计算机应用, 2012, 32(03): 787-790.
[8]	刘青芳李月娥. 基于互信息的医学图像配准中改进的采样方法[J]. 计算机应用, 2010, 30(4): 947-949.
[9]	王小乐刘青宝陆昌辉陈文凯. 一种处理障碍约束的聚类算法[J]. 计算机应用, 2009, 29(2): 406-408.
[10]	张加万韩真毅张怡白玉超. 基于灰度特征的一致性弹性配准算法[J]. 计算机应用, 2009, 29(10): 2684-2686.
[11]	汪维清汪维华张明义. 基于有序双循环链表的低代价最短路径树快速算法[J]. 计算机应用, 2007, 27(8): 1980-1983.
[12]	夏薇，滕奇志，张轶琼，罗代升. 基于尺度空间分析和概率松弛的细胞图像分割算法[J]. 计算机应用, 2005, 25(08): 1801-1804.