﻿ 主成分分析的匹配点对提纯方法
 文章快速检索 高级检索

The Purification Method of Matching Points Based on Principal Component Analysis
DONG Yang, FAN Dazhao, JI Song, LEI Rong
Information Engineering University, Zhengzhou 450000, China
Foundation support: The National Natural Science Foundation of China (No.41401534),State Key Laboratory of Geographic Information Engineering (No. SKLGIE2013-M-3-1)
First author: DONG Yang(1992—), male, postgraduate, majors in digital photogrammetry.E-mail: wenku34@163.com
Corresponding author: FAN Dazhao. E-mail:fdzcehui@163.com
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

1 匹配点对提纯模型与算法 1.1 主成分分析与奇异值分解模型

(1)

(2)

(3)

A′为A的近似矩阵，由矩阵A的主奇异值重构而成，包含了矩阵A的主要信息。两矩阵间的差分矩阵ΔA

(4)

1.2 主成分分析思想下的提纯模型

 图 1 主成分分析思想下的提纯流程 Fig. 1 The process of purification based on principal component analysis

1.3 基于奇异值分解的匹配点对提纯算法

(5)

(6)

(7)

(8)

 图 2 匹配点对提纯流程 Fig. 2 Matching points purification

2 试验及其结果分析

 图 3 匹配点对示意图 Fig. 3 Matching points diagram

 图 4 取值误差示意图 Fig. 4 Value of the error diagram

 图 5 经过本文方法提纯后，误点率由13.85%降到0 Fig. 5 The mismatch percentage is reduced from 13.85% to 0

 图 6 经过本文方法提纯后，误点率由33.33%降到0 Fig. 6 The mismatch percentage is reduced from 33.33% to 0

 图 7 经过本文方法提纯后，误点率由36.94%降到0 Fig. 7 The mismatch percentage is reduced from 36.94% to 0

 图 8 经过本文方法提纯后，误点率由50.00%降到0 Fig. 8 The mismatch percentage is reduced from 50% to 0

 图 9 经过本文方法提纯后，误点率由71.00%降到2.03% Fig. 9 The mismatch percentage is reduced from 71.00% to 2.03%

 图 10 经过本文方法提纯后，误点率由78.33%降到0.77% Fig. 10 The mismatch percentage is reduced from 78.33% to 0.77%

 编号 试验数据 时间/ms 迭代次数 总点数 误点率 /(%) 本文 方法 RANSAC 本文 方法 RANSAC 1 65 13.85 11 3 5 36 2 60 33.33 10 4 4 92 3 111 36.94 12 13 4 240 4 200 50.00 13 26 3 446 5 500 71.00 40 205 10 2000 6 6000 78.33 2170 1430 30 2000

 原始匹配点 RANSAC方法 本文方法 原始总 点数 原始误 点数 提纯总 点数 提纯误 点数 弃真率 /(%) 取假率 /(%) 提纯总 点数 提纯误 点数 弃真率 /(%) 取假率 /(%) 1000 100 848 0 6.13 0.00 900 0 0.00 0.00 1000 200 789 0 1.38 0.00 800 0 0.00 0.00 1000 300 689 0 1.57 0.00 700 0 0.00 0.00 1000 400 593 0 1.17 0.00 600 0 0.00 0.00 1000 500 500 0 0.00 0.00 500 0 0.00 0.00 1000 600 401 1 0.00 0.17 401 1 0.00 0.17 1000 700 295 0 1.67 0.00 300 0 0.00 0.00 1000 800 164 3 19.50 0.38 195 0 2.50 0.00 1000 850 115 4 26.00 0.47 154 4 0.00 0.47 1000 870 84 3 37.69 0.34 129 2 2.31 0.23 1000 880 77 3 38.33 0.34 0 0 100.00 0.00 1000 890 70 3 39.09 0.34 2 1 99.09 0.11 1000 900 68 6 38.00 0.67 1 1 100.00 0.11

 图 11 试验结果对比 Fig. 11 Comparison of experimental results

3 结 语

﻿

 [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. DOI:10.1137/S0036144598345802 [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. DOI:10.1080/01621459.1984.10477105 [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. DOI:10.1006/cviu.1999.0832 [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. DOI:10.1145/358669.358692 [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. DOI:10.1023/B:VISI.0000029664.99615.94 [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. DOI:10.1137/080732730 [10] NISTÉR D. Preemptive RANSAC for Live Structure and Motion Estimation[J]. Machine Vision and Applications, 2005, 16(5): 321–329. DOI:10.1007/s00138-005-0006-y [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. DOI:10.1109/TPAMI.2007.70787 [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. DOI:10.1007/s11263-010-0318-x [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. 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. DOI:10.1137/S0895479896305696 [22] 林东方, 朱建军, 宋迎春, 等. 正则化的奇异值分解参数构造法[J]. 测绘学报, 2016, 45(8): 883–889. 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. DOI:10.1007/BF02163027 [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.
http://dx.doi.org/10.11947/j.AGCS.2017.20160250

0

#### 文章信息

DONG Yang, FAN Dazhao, JI Song, LEI Rong

The Purification Method of Matching Points Based on Principal Component Analysis

Acta Geodaetica et Cartographica Sinica, 2017, 46(2): 228-236
http://dx.doi.org/10.11947/j.AGCS.2017.20160250