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

doi:10.3724/SP.J.1087.2013.01686

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

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

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

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

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

Abstract

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:

TP391

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.

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

References

[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.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	YANG Mengmeng, ZHANG Aihua. Fractal image compression based on gray-level co-occurrence matrix and simultaneous orthogonal matching pursuit [J]. Journal of Computer Applications, 2021, 41(5): 1445-1449.
[2]	HU Lihua, ZUO Weijian, NIE Yaoyao. Feature matching method based on weighted similarity measurement [J]. Journal of Computer Applications, 2021, 41(2): 511-516.
[3]	Yubin ZHOU, Hong XIAO, Tao WANG, Wenchao JIANG, Meng XIONG, Zhongtang HE. Health index construction and remaining useful life prediction of mechanical axis based on action cycle degradation similarity measurement [J]. Journal of Computer Applications, 2021, 41(11): 3192-3199.
[4]	LYU Yike, XU Kai, HUANG Zhenqiang. Trajectory similarity measurement method based on area division [J]. Journal of Computer Applications, 2020, 40(2): 578-583.
[5]	MA Weiping, LI Wenxin, SUN Jinchuan, CAO Pengxia. Binocular vision target positioning method based on coarse-fine stereo matching [J]. Journal of Computer Applications, 2020, 40(1): 227-232.
[6]	FU Lidong, HAO Wei, LI Dan, LI Fan. Community dividing algorithm based on similarity of common neighbor nodes [J]. Journal of Computer Applications, 2019, 39(7): 2024-2029.
[7]	ZHANG Yonglai, ZHOU Yaojian. Review of clustering algorithms [J]. Journal of Computer Applications, 2019, 39(7): 1869-1882.
[8]	PENG Lei, YANG Xiuyun, ZHANG Yufei, LI Guangyao. Non-rigid point set registration based on global and local similarity measurement [J]. Journal of Computer Applications, 2019, 39(10): 3028-3033.
[9]	CHANG Bingguo, ZANG Hongying. Time series classifier design based on piecewise dimensionality reduction and updated dynamic time warping [J]. Journal of Computer Applications, 2018, 38(7): 1910-1915.
[10]	XU Su, ZHOU Yingyue. Non-local means denoising algorithm based on image segmentation [J]. Journal of Computer Applications, 2017, 37(7): 2078-2083.
[11]	SHI Lukui, ZHANG Yanru, ZHANG Xin. Trajectory data clustering algorithm based on spatio-temporal pattern [J]. Journal of Computer Applications, 2017, 37(3): 854-859.
[12]	YANG Jiahui, LIU Fangai. Collaborative filtering algorithm based on Bhattacharyya coefficient and Jaccard coefficient [J]. Journal of Computer Applications, 2016, 36(7): 2006-2010.
[13]	WEI Zheng TANG Jin JIANG Bo LUO Bin. Graph context and its application in graph similarity measurement [J]. Journal of Computer Applications, 2013, 33(01): 44-48.
[14]	CHEN WEIBING. Matching Capabilities Comparisons of Similarity Measurements [J]. Journal of Computer Applications, 2010, 30(1): 98-100.
[15]	. Collaborative filtering recommendation algorithm based on Bayesian theory [J]. Journal of Computer Applications, 2009, 29(10): 2733-2735.