The Purification Method of Matching Points Based on Principal Component Analysis

doi:10.11947/j.AGCS.2017.20160250

Abstract

Abstract: The traditional purification method of matching points usually uses a small number of the points as initial input. Though it can meet most of the requirements of point constraints, the iterative purification solution is easy to fall into local extreme, which results in the missing of correct matching points. To solve this problem, we introduce the principal component analysis method to use the whole point set as initial input. And thorough mismatching points step eliminating and robust solving, more accurate global optimal solution, which intends to reduce the omission rate of correct matching points and thus reaches better purification effect, can be obtained. Experimental results show that this method can obtain the global optimal solution under a certain original false matching rate, and can decrease or avoid the omission of correct matching points.

Key words: image matching, principal components analysis, singular value decomposition, purification, random sample consensus

CLC Number:

P236

DONG Yang, FAN Dazhao, JI Song, LEI Rong. The Purification Method of Matching Points Based on Principal Component Analysis[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2): 228-236.

References

[1] HUBER P J. Robust Statistics[M]//LOVRIC M. International Encyclopedia of Statistical Science. Berlin:Springer, 2011.
[2] STEWART C V. Robust Parameter Estimation in Computer Vision[J]. SIAM Review, 1999, 41(3):513-537.
[3] HAWKINS D M. The Feasible Set Algorithm for Least Median of Squares Regression[J]. Computational Statistics & Data Analysis, 1993, 16(1):81-101.
[4] ROUSSEEUW P J. Least Median of Squares Regression[J]. Journal of the American Statistical Association, 1984, 79(388):871-880.
[5] TORR P H S, ZISSERMAN A. MLESAC:A New Robust Estimator with Application to Estimating Image Geometry[J]. Computer Vision and Image Understanding, 2000, 78(1):138-156.
[6] FISCHLER M A, BOLLES R C. Random Sample Consensus:A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J]. Communications of the ACM, 1981, 24(6):381-395.
[7] 王亚伟, 许廷发, 王吉晖. 改进的匹配点提纯算法mRANSAC[J]. 东南大学学报(自然科学版), 2013, 43(S1):163-167. WANG Yawei, XU Tingfa, WANG Jihui. Improved Matching Point Purification Algorithm mRANSAC[J]. Journal of Southeast University (Natural Science Edition), 2013, 43(S1):163-167.
[8] LOWE D G. Distinctive Image Features from Scale-invariant Keypoints[J]. International Journal of Computer Vision, 2004, 60(2):91-110.
[9] MOREL J M, YU Guoshen. ASIFT:A New Framework for Fully Affine Invariant Image Comparison[J]. SIAM Journal on Imaging Sciences, 2009, 2(2):438-469.
[10] NISTÉR D. Preemptive RANSAC for Live Structure and Motion Estimation[J]. Machine Vision and Applications, 2005, 16(5):321-329.
[11] CHUM O, MATAS J. Matching with PROSAC-progressive Sample Consensus[C]//Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego, CA:IEEE, 2005, 1:220-226.
[12] MATAS J,CHUM O.Randomized RANSAC[R]. Prague:Center for Machine Perception, Czech Technical University, 2001.
[13] CHUM O, MATAS J. Optimal Randomized RANSAC[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(8):1472-1482.
[14] 钟金荣, 杜奇才, 刘荧, 等. 特征提取和匹配的图像倾斜校正[J]. 中国图象图形学报, 2013, 18(7):738-745. ZHONG Jinrong, DU Qicai, LIU Ying, et al. Robust Method of Skew Correction Based on Feature Points Matching[J]. Journal of Image and Graphics, 2013, 18(7):738-745.
[15] LI Xiangru, HU Zhanyi. Rejecting Mismatches by Correspondence Function[J]. International Journal of Computer Vision, 2010, 89(1):1-17.
[16] PAUL V C H.Method and Means for Recognizing Complex Patterns:U.S., 3,069,654[P]. 1962-12-18.
[17] 谢亮, 陈姝, 张钧, 等. 利用Hough变换的匹配对提纯[J]. 中国图象图形学报, 2015, 20(8):1017-1025. XIE Liang, CHEN Shu, ZHANG Jun, et al. Purifying Algorithm for Rough Matched Pairs Using Hough Transform[J]. Journal of Image and Graphics, 2015, 20(8):1017-1025.
[18] GROTH D, HARTMANN S, KLIE S, et al. Principal Components Analysis[M]//REISFELD B, MAYENO A N. Computational Toxicology:Methods in Molecular Biology.[S.l.]:Humana Press, 2013, 930:527-547.
[19] 王俊淑, 江南, 张国明, 等. 融合光谱-空间信息的高光谱遥感影像增量分类算法[J]. 测绘学报, 2015, 44(9):1003-1013. DOI:10.11947/j.AGCS.2015.20140388. WANG Junshu, JIANG Nan, ZHANG Guoming, et al. Incremental Classification Algorithm of Hyperspectral Remote Sensing Images Based on Spectral-spatial Information[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(9):1003-1013. DOI:10.11947/j.AGCS.2015.20140388.
[20] 王文波, 赵攀, 张晓东. 利用经验模态分解和主成分分析的SAR图像相干斑抑制[J]. 测绘学报, 2012, 41(6):838-843. WANG Wenbo, ZHAO Pan, ZHANG Xiaodong. Research on SAR Image Speckle Reduction Using EMD and Principle Component Analysis[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6):838-843.
[21] DE LATHAUWER L, DE MOOR B, VANDEWALLE J. A Multilinear Singular Value Decomposition[J]. SIAM Journal on Matrix Analysis and Applications, 2000, 21(4):1253-1278.
[22] 林东方, 朱建军, 宋迎春, 等. 正则化的奇异值分解参数构造法[J]. 测绘学报, 2016, 45(8):883-889. DOI:10.11947/j.AGCS.2016.20150134. LIN Dongfang, ZHU Jianjun, SONG Yingchun, et al. Construction Method of Regularization by Singular Value Decomposition of Design Matrix[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(8):883-889. DOI:10.11947/j.AGCS.2016.20150134.
[23] 周伟, 戴宗友, 袁广林, 等. CPU-GPU协同计算的并行奇异值分解方法[J]. 计算机科学, 2015, 42(6A):549-552. ZHOU Wei, DAI Zongyou, YUAN Guanglin, et al. Parallelized Singular Value Decomposition Method with Collaborative Computing of CPU-GPU[J]. Computer Science, 2015, 42(6A):549-552.
[24] LAHABAR S, NARAYANAN P J. Singular Value Decomposition on GPU Using CUDA[C]//Proceedings of the 2009 IEEE International Symposium on Parallel & Distributed Processing. Rome:IEEE, 2009:1-10.
[25] GOULUB G H, REINSCH C. Singular Value Decomposition and Least Squares Solutions[J]. Numerische Mathematik, 1970, 14(5):403-420.
[26] 徐文华, 孙学栋. 奇异值分解求线性最小二乘解的理论分析[J]. 贵阳学院学报(自然科学版), 2010, 4(4):1-4. XU Wenhua, SUN Xuedong. A Theoretical Analysis of Linear Least Square Based on Singular Value Decomposition[J]. Journal of Guiyang College (Natural Sciences), 2010, 4(4):1-4.
[27] 吴春国, 梁艳春, 孙延风, 等. 关于SVD与PCA等价性的研究[J]. 计算机学报, 2004, 27(2):286-288. WU Chunguo, LIANG Yanchun, SUN Yanfeng, et al. On the Equivalence of SVD and PCA[J]. Chinese Journal of Computers, 2004, 27(2):286-288.
[28] 聂振国, 赵学智. PCA与SVD信号处理效果相似性与机理分析[J]. 振动与冲击, 2016, 35(2):12-17. NIE Zhenguo, ZHAO Xuezhi. Similarity of Signal Processing Effect between PCA and SVD and Its Mechanism Analysis[J]. Journal of Vibration and Shock, 2016, 35(2):12-17.
[29] 数据科学自媒体. 解码数据降维:主成分分析(PCA)和奇异值分解(SVD)[EB/OL]. (2015-10-23).[2016-01-20].http://www.wtoutiao.com/p/T5431a.html. Data Science We Media. Decoding Data Dimension Reduction:Principal Component Analysis (PCA) and the Singular Value Decomposition (SVD)[EB/OL]. (2015-10-23).[2016-01-20]. http://www.wtoutiao.com/p/T5431a.html.
[30] 钱征文, 程礼, 李应红. 利用奇异值分解的信号降噪方法[J]. 振动、测试与诊断, 2011, 31(4):459-463. QIAN Zhengwen, CHENG Li, LI Yinghong. Using Singular Value Decomposition of the Signal Noise Reduction Method[J]. Journal of Vibration, Measurement & Diagnosis, 2011, 31(4):459-463.
[31] 王建国, 李健, 刘颖源. 一种确定奇异值分解降噪有效秩阶次的改进方法[J]. 振动与冲击, 2014, 33(12):176-180. WANG Jianguo, LI Jian, LIU Yingyuan. An Improved Method for Determining Effective Order Rank of SVD Denoising[J]. Journal of Vibration and Shock, 2014, 33(12):176-180.
[32] VU V. A Simple SVD Algorithm for Finding Hidden Partitions[EB/OL]. (2014-04-07).[2016-01-30]. http://adsabs.harvard.edu/abs/2014arXiv1404.3917v.