董 楊，范大昭，紀(jì) 松，雷 蓉

信息工程大學(xué)，河南 鄭州 450000

主成分分析的匹配點(diǎn)對(duì)提純方法

董 楊，范大昭，紀(jì) 松，雷 蓉

信息工程大學(xué)，河南 鄭州 450000

傳統(tǒng)的匹配點(diǎn)對(duì)提純算法通常需要尋找小部分點(diǎn)集作為初始輸入，再迭代求解出能夠滿足大多數(shù)點(diǎn)對(duì)約束要求的最優(yōu)解，其提純結(jié)果易陷入局部極值，造成正確匹配點(diǎn)對(duì)的遺漏。針對(duì)這一問(wèn)題，本文引入了主成分分析思想，將整體點(diǎn)集作為初始輸入，逐步剔除誤匹配點(diǎn)對(duì)，穩(wěn)健求解，得到更為準(zhǔn)確的全局最優(yōu)解，降低正確匹配點(diǎn)對(duì)的遺漏率，達(dá)到較好的提純效果。試驗(yàn)表明，本文方法在一定的原始誤匹配率下，能夠得到整體最優(yōu)解，在剔除誤匹配點(diǎn)對(duì)的同時(shí)，能夠避免或減少正確匹配點(diǎn)對(duì)的遺漏。

影像匹配；主成分分析；奇異值分解；提純；RANSAC

在影像匹配過(guò)程中，經(jīng)常會(huì)存在一些誤匹配點(diǎn)對(duì)，這時(shí)可以通過(guò)匹配提純的方法對(duì)誤匹配點(diǎn)對(duì)進(jìn)行剔除。一般的提純思路是尋找一個(gè)恰當(dāng)?shù)钠ヅ潼c(diǎn)對(duì)約束模型，估計(jì)出正確的模型參數(shù)，利用約束模型進(jìn)行匹配點(diǎn)對(duì)提純。在匹配點(diǎn)對(duì)約束模型中，通常使用變換約束矩陣作為估計(jì)模型，其一般包括平移變換、剛體變換、相似性變換、仿射變換、射影變換、極線幾何基本矩陣變換等?，F(xiàn)行的變換約束矩陣模型已經(jīng)能夠很好地進(jìn)行匹配點(diǎn)對(duì)間的幾何約束，因此大多數(shù)學(xué)者更加傾向于模型參數(shù)估計(jì)方法的研究。

在模型參數(shù)估計(jì)中，常用的方法有穩(wěn)健回歸估計(jì)和隨機(jī)參數(shù)估計(jì)等。對(duì)于穩(wěn)健回歸估計(jì)方法，如M-估計(jì)[1-2]，其核心思想是采用迭代加權(quán)最小二乘估計(jì)回歸系數(shù)，但其僅能適應(yīng)誤匹配率較小的情況。對(duì)于隨機(jī)參數(shù)估計(jì)方法，如LMedS(least median of squares)算法[3-4]、MLESAC(maximum likelihood estimation sample and consensus)算法[5]和RANSAC(random sample consensus)算法[6]等，其核心思想是隨機(jī)選擇樣本子集，迭代挑選出最佳模型參數(shù)。其中，RANSAC算法能夠在存在大量外點(diǎn)的數(shù)據(jù)中找到內(nèi)點(diǎn)，因而得到廣泛應(yīng)用并派生出一系列改進(jìn)算法[7-9]。改進(jìn)的RANSAC方法主要從兩個(gè)方面進(jìn)行了優(yōu)化。一方面是速度優(yōu)化，如P-RANSAC(preemptive RANSAC)[10-11]和R-RANSAC(randomized RANSAC)[12-13]等；一方面是提純率的優(yōu)化，如M-RANSAC(multi RANSAC)[7]等。然而這些算法都需要選擇一個(gè)合適的初始內(nèi)點(diǎn)集，提純結(jié)果容易陷入局部最優(yōu)解，造成部分正確匹配點(diǎn)對(duì)遺漏；在誤匹配率增大時(shí)，成功選擇內(nèi)點(diǎn)集的試驗(yàn)次數(shù)也急劇增大。除了以上的約束模型及參數(shù)估計(jì)方法，近期也有一些其他的研究成果[14-17]。文獻(xiàn)[14]提出通過(guò)統(tǒng)計(jì)模板的旋轉(zhuǎn)角度直方圖來(lái)剔除誤匹配，但其依賴角度區(qū)間的劃分，僅適用于對(duì)精度要求不高的情況；文獻(xiàn)[15]提出一致性函數(shù)(correspondence function)模型，通過(guò)學(xué)習(xí)匹配點(diǎn)對(duì)一致性函數(shù)來(lái)拒絕誤匹配；文獻(xiàn)[17]提出通過(guò)Hough變換求解模型參數(shù)來(lái)進(jìn)行匹配點(diǎn)對(duì)提純，然而僅適用于模型參數(shù)較少的情況。由此，在匹配點(diǎn)對(duì)約束模型選定的情況下，本文對(duì)如何求解模型參數(shù)整體最優(yōu)解，實(shí)現(xiàn)穩(wěn)健匹配點(diǎn)對(duì)提純的問(wèn)題進(jìn)行了研究。

主成分分析(principal components analysis，PCA)[18-20]是一種有效的多元統(tǒng)計(jì)方法，在信號(hào)處理、統(tǒng)計(jì)學(xué)等領(lǐng)域有重要應(yīng)用。類似于信號(hào)處理過(guò)程中利用主成分分析方法進(jìn)行噪聲去除，可將主成分分析思想引入匹配點(diǎn)對(duì)提純的過(guò)程，逐步剔除噪聲點(diǎn)，實(shí)現(xiàn)匹配點(diǎn)對(duì)的提純。為了方便闡述與試驗(yàn)，文中以奇異值分解作為主成分分析的具體實(shí)現(xiàn)方法，并以此為基礎(chǔ)對(duì)提純方法進(jìn)行了推導(dǎo)與論述。奇異值分解[21-22](singular value decomposition，SVD)是矩陣分析中正規(guī)矩陣酉對(duì)角化的推廣，是一種重要的主成分分析實(shí)現(xiàn)方法，能夠進(jìn)行并行化計(jì)算[23-24]，可用于最小二乘求解[25-26]，已被廣泛應(yīng)用于各個(gè)領(lǐng)域。

本文分析了奇異值分解中奇異值的對(duì)應(yīng)含義，并將其引用到匹配點(diǎn)對(duì)提純過(guò)程中。首先，用特定模型來(lái)描述匹配點(diǎn)對(duì)之間的變換關(guān)系，建立模型誤差方程；其次，對(duì)含有匹配點(diǎn)對(duì)信息的系數(shù)矩陣進(jìn)行奇異值分解，重構(gòu)大奇異值對(duì)應(yīng)的矩陣，得到差分矩陣；然后，剔除可能的誤匹配點(diǎn)對(duì)，構(gòu)造降階矩陣，進(jìn)行模型求解；最后，利用求解的模型參數(shù)，進(jìn)行匹配點(diǎn)對(duì)約束，達(dá)到匹配點(diǎn)對(duì)提純的目的。

1 匹配點(diǎn)對(duì)提純模型與算法

1.1 主成分分析與奇異值分解模型

經(jīng)典的主成分分析算法通過(guò)計(jì)算輸入數(shù)據(jù)的協(xié)方差矩陣及其特征向量來(lái)實(shí)現(xiàn)數(shù)據(jù)主成分的提取。當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，這一途徑的計(jì)算代價(jià)非常昂貴。而奇異值分解與主成分分析都是特征正交分解(proper orthogonal decomposition，POD)，具有等價(jià)性[27]，在實(shí)際應(yīng)用中處理效果相似[28]。奇異值分解無(wú)需計(jì)算協(xié)方差矩陣，無(wú)需進(jìn)行均值化處理，計(jì)算量少，能避免計(jì)算協(xié)方差矩陣的舍入誤差，相對(duì)誤差較小，因此計(jì)算主成分最優(yōu)的方法是使用奇異值分解[29]。

定義一個(gè)秩為r的m×n維矩陣A，則A的奇異值分解形式為

A=USVT

(1)

式中，U為m×m維正交矩陣；V為n×n維正交矩陣，S為m×n維對(duì)角陣。U的列向量ui稱為矩陣A的左奇異向量；V的列向量vi稱為矩陣A的右奇異向量；S的對(duì)角線元素σi稱為矩陣A的奇異值，且以遞減順序排列，即σ1≥σ2≥…≥σr。

由矩陣A的前t個(gè)奇異值重新組成對(duì)角陣St×t=diag[σ1,σ2,…,σt]，由奇異值對(duì)應(yīng)的左、右奇異向量重新組成矩陣Um×t=[u1,u2,…,ut]和Vt×n=[v1,v2,…,vt]，利用式(1)可重構(gòu)矩陣A，得到

(2)

對(duì)式(2)進(jìn)行化簡(jiǎn)可得

(3)

A′為A的近似矩陣，由矩陣A的主奇異值重構(gòu)而成，包含了矩陣A的主要信息。兩矩陣間的差分矩陣ΔA為

(4)

可以發(fā)現(xiàn)，A與A′間僅相差小奇異值對(duì)應(yīng)的部分。研究表明，大的奇異值對(duì)應(yīng)的重構(gòu)矩陣A′包含更多的主要信息，小的奇異值對(duì)應(yīng)的差分矩陣ΔA包含更多的噪聲信息[30-32]?；谶@種思想，ΔA則反映了矩陣A中噪聲信息的大體分布情況。因此，可依據(jù)差分矩陣ΔA進(jìn)行矩陣A中的噪聲剔除，得到更為合理的降階矩陣B，這也是本文主成分分析思想研究的關(guān)鍵。

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

隨著特征點(diǎn)提取與匹配技術(shù)的不斷發(fā)展，硬件計(jì)算能力的日益增長(zhǎng)，現(xiàn)行的匹配算法已使匹配精度達(dá)到一個(gè)較高的水平。但由于算法本身的缺陷，不可避免地存在一些誤匹配點(diǎn)對(duì)，這時(shí)就需要利用一些技術(shù)手段將其剔除。在此背景下，本文以“正確匹配點(diǎn)對(duì)占據(jù)匹配中的主要成分”為先驗(yàn)條件，結(jié)合現(xiàn)有的數(shù)據(jù)分析技術(shù)，嘗試在匹配點(diǎn)對(duì)提純中引入主成分分析思想，從而求解出較優(yōu)的提純結(jié)果。

為了具體說(shuō)明提純方法，下文以奇異值分解作為主成分分析的具體實(shí)現(xiàn)方法，以基本矩陣模型作為約束模型，對(duì)以上過(guò)程進(jìn)行詳細(xì)推導(dǎo)。

1.3 基于奇異值分解的匹配點(diǎn)對(duì)提純算法

匹配點(diǎn)對(duì)提純應(yīng)遵循兩個(gè)原則：一是正確匹配點(diǎn)對(duì)被剔除的概率應(yīng)盡量小，即“棄真”錯(cuò)誤少發(fā)生；二是誤匹配點(diǎn)對(duì)被接受的概率應(yīng)盡量小，即“取偽”錯(cuò)誤少發(fā)生。前者避免了提純算法過(guò)于嚴(yán)格，后者避免了提純算法過(guò)于寬松。兩者相互作用，

避免了提純結(jié)果陷入局部最優(yōu)解，確保了提純過(guò)程的穩(wěn)健性。匹配提純的實(shí)質(zhì)是匹配點(diǎn)對(duì)間模型參數(shù)的確定，選擇合適的模型以及適當(dāng)?shù)膮?shù)，使其滿足提純的兩個(gè)原則，即可實(shí)現(xiàn)匹配點(diǎn)對(duì)間的提純操作。這里使用基本矩陣模型進(jìn)行求解推導(dǎo)。

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

影像間匹配點(diǎn)對(duì)一般滿足極線幾何約束，即對(duì)應(yīng)匹配點(diǎn)應(yīng)在對(duì)應(yīng)極線上。這一約束可通過(guò)基本矩陣描述為

m′Fm=0

(5)

式中，m=(x,y,1)T、m′=(x′,y′,1)T分別為匹配點(diǎn)對(duì)齊次坐標(biāo)；F為基本矩陣。令F=(fij)，則式(5)可寫為如下形式

(x′x,x′y,x′,y′x,y′y,y′,x,y,1)f=0

(6)

式中，f=[f11f12f13f21f22f23f31f32f33]T。將式(6)作為模型，f作為待解參數(shù)，可進(jìn)行匹配點(diǎn)對(duì)的提純。給定n對(duì)匹配點(diǎn)對(duì)可以得到線性方程組

(7)

(8)

式中，Δaij為ΔA中的元素。以近似均方誤差作為閾值，對(duì)每一匹配點(diǎn)對(duì)誤差方程進(jìn)行篩選，得到約束后的匹配點(diǎn)對(duì)誤差方程，然后再次重新組成系數(shù)矩陣，得到降維矩陣B。對(duì)矩陣B再次進(jìn)行奇異值分解，求解f的最小二乘解，并進(jìn)行秩2約束，得到最終的模型參數(shù)解f。利用求解的參數(shù)及相應(yīng)的模型，對(duì)匹配點(diǎn)對(duì)進(jìn)行約束，得到提純點(diǎn)對(duì)。利用提純后的點(diǎn)對(duì)迭代進(jìn)行以上步驟，直到求解的模型參數(shù)f趨于穩(wěn)定。整個(gè)算法流程如圖2所示。

圖2 匹配點(diǎn)對(duì)提純流程Fig.2 Matching points purification

2 試驗(yàn)及其結(jié)果分析

上述算法中，重要的一步是計(jì)算重構(gòu)矩陣時(shí)奇異值個(gè)數(shù)t的確定。一個(gè)恰當(dāng)?shù)膖應(yīng)能使計(jì)算的重構(gòu)矩陣A′中的正確匹配點(diǎn)對(duì)部分，與原始矩陣A中對(duì)應(yīng)的正確匹配點(diǎn)對(duì)部分盡量相似，而對(duì)應(yīng)的誤匹配部分盡量相差較大。即ΔA中正確匹配點(diǎn)對(duì)的近似誤差值盡量小，而誤匹配點(diǎn)對(duì)的近似誤差值盡量大。

利用多幅影像進(jìn)行試驗(yàn)，這里選取某幅影像中的1000對(duì)正確匹配點(diǎn)對(duì)進(jìn)行說(shuō)明。如圖3所示，對(duì)前100對(duì)匹配點(diǎn)對(duì)加入隨機(jī)誤差，分別在t=1,2,…,8的條件下求解差分矩陣，計(jì)算每一匹配點(diǎn)對(duì)對(duì)應(yīng)的近似誤差，得到如圖4所示的結(jié)果。

圖4中橫軸表示匹配點(diǎn)對(duì)，縱軸表示對(duì)應(yīng)的近似誤差值，其中前100個(gè)為誤匹配點(diǎn)對(duì)，可以看出當(dāng)t值取5時(shí)，已經(jīng)能夠很好地區(qū)別正確匹配點(diǎn)對(duì)與誤匹配點(diǎn)對(duì)，當(dāng)t值增大時(shí)，雖然這種區(qū)別更加明顯，但計(jì)算量也隨之而增長(zhǎng)。在實(shí)際操作中取t=5。

在得到恰當(dāng)?shù)膖值后，為了進(jìn)一步驗(yàn)證本文算法的實(shí)際效果，對(duì)含有不同誤點(diǎn)率的影像匹配點(diǎn)對(duì)進(jìn)行了試驗(yàn)，截取其中6對(duì)試驗(yàn)影像，如圖5至圖10所示。其中，每幅圖中(a)圖表示原始像對(duì)圖，(b)圖表示加入誤匹配點(diǎn)對(duì)后的像對(duì)圖，(c)圖表示利用本文方法進(jìn)行點(diǎn)對(duì)提純后的像對(duì)圖。

圖5至圖7為手機(jī)拍攝影像，圖8至圖9為普通相機(jī)拍攝影像，圖10為航拍影像?？梢钥闯?，在不同場(chǎng)景中隨著誤匹配率的不斷提升，本文方法仍能保持著優(yōu)良的提純率，反映了本文方法較好的穩(wěn)健性。同時(shí)，為了比較本文算法的效率與全局求解的優(yōu)勢(shì)，將上述像對(duì)分別用經(jīng)典RANSAC算法進(jìn)行處理，統(tǒng)計(jì)每次的運(yùn)算耗時(shí)與實(shí)際迭代次數(shù)，統(tǒng)計(jì)如表1所示。其中，設(shè)置RANSAC算法迭代上限為2000次，本文算法迭代上限為50次，編號(hào)1—編號(hào)6數(shù)據(jù)分別對(duì)應(yīng)圖5—圖10。

表1 對(duì)比結(jié)果信息

表1中時(shí)間欄為多次試驗(yàn)的平均耗時(shí)。同時(shí)，本文認(rèn)為試驗(yàn)中處理時(shí)間差異在10 ms以內(nèi)的兩種方法處于相同的耗時(shí)水平。由表1可以看出不同情況下本文方法迭代次數(shù)皆遠(yuǎn)小于RANSAC方法的迭代次數(shù)。由于全局求解的優(yōu)勢(shì)，本文方法在數(shù)次迭代后便可得到最優(yōu)解，而RANSAC方法由于隨機(jī)抽樣的特性，在大數(shù)據(jù)量與高誤點(diǎn)率的情況下，迭代次數(shù)驟然上升。試驗(yàn)中編號(hào)為5和6的數(shù)據(jù)試驗(yàn)結(jié)果表明RANSAC方法在此種情況下已達(dá)到迭代次數(shù)上限。同時(shí)，由表1也可以看出在低誤點(diǎn)率情況下，本文方法與RANSAC方法時(shí)間消耗相當(dāng)，在中誤點(diǎn)率的情況下，本文方法時(shí)間消耗少于RANSAC方法，而在高誤點(diǎn)率的情況下，本文方法耗時(shí)多于RANSAC方法。這種特性是由奇異值分解過(guò)程的耗時(shí)與迭代次數(shù)上限的設(shè)置共同造成的。單次奇異值分解的耗時(shí)大于單次隨機(jī)采樣求解的耗時(shí)，在低誤點(diǎn)率的情況下，RANSAC方法迭代次數(shù)多于本文方法，總體而言時(shí)間消耗相當(dāng)；在中誤點(diǎn)率的情況下，RANSAC方法迭代次數(shù)驟然增加，而本文方法迭代次數(shù)增加緩慢，總體而言本文方法耗時(shí)相對(duì)較少；在高誤點(diǎn)率的極端情況下，由于RANSAC方法迭代次數(shù)已達(dá)到上限，而本文方法的迭代次數(shù)繼續(xù)增加，耗時(shí)相對(duì)較多。在實(shí)際應(yīng)用中可通過(guò)奇異值分解算法的并行求解與GPU加速縮短單次求解時(shí)間，優(yōu)化整體耗時(shí)。

為了進(jìn)一步驗(yàn)證本文算法與現(xiàn)有算法間的性能優(yōu)劣，取1000對(duì)正確匹配點(diǎn)對(duì)逐步加入隨機(jī)誤差，分別用經(jīng)典RANSAC算法和本文算法對(duì)匹配點(diǎn)對(duì)進(jìn)行提純，得到結(jié)果如表2和圖11所示。

圖3 匹配點(diǎn)對(duì)示意圖Fig.3 Matching points diagram

圖4 取值誤差示意圖Fig.4 Value of the error diagram

圖5 經(jīng)過(guò)本文方法提純后，誤點(diǎn)率由13.85%降到0Fig.5 The mismatch percentage is reduced from 13.85% to 0

圖6 經(jīng)過(guò)本文方法提純后，誤點(diǎn)率由33.33%降到0Fig.6 The mismatch percentage is reduced from 33.33% to 0

圖7 經(jīng)過(guò)本文方法提純后，誤點(diǎn)率由36.94%降到0Fig.7 The mismatch percentage is reduced from 36.94% to 0

圖8 經(jīng)過(guò)本文方法提純后，誤點(diǎn)率由50.00%降到0Fig.8 The mismatch percentage is reduced from 50% to 0

圖9 經(jīng)過(guò)本文方法提純后，誤點(diǎn)率由71.00%降到2.03%Fig.9 The mismatch percentage is reduced from 71.00% to 2.03%

圖10 經(jīng)過(guò)本文方法提純后，誤點(diǎn)率由78.33%降到0.77%Fig.10 The mismatch percentage is reduced from 78.33% to 0.77%

圖11 試驗(yàn)結(jié)果對(duì)比Fig.11 Comparison of experimental results

試驗(yàn)中，RANSAC算法和本文算法的最終閾值約束都設(shè)置為3。根據(jù)之前提到的兩個(gè)原則，定義棄真率的計(jì)算公式為PT=nt1/nt，nt1表示未能被提取出來(lái)的正確匹配點(diǎn)對(duì)個(gè)數(shù)，nt表示總共的正確匹配點(diǎn)對(duì)個(gè)數(shù)；定義取假率的計(jì)算公式為PF=nf1/nf，nf1表示被提取出來(lái)的誤匹配點(diǎn)對(duì)的個(gè)數(shù)，nf表示總共的誤匹配點(diǎn)對(duì)個(gè)數(shù)。圖11中橫軸表示原始匹配點(diǎn)對(duì)中的誤匹配率值，縱軸表示比率值。表2中括號(hào)內(nèi)的數(shù)據(jù)表示誤匹配點(diǎn)對(duì)的個(gè)數(shù)。由表2和圖11中數(shù)據(jù)可以發(fā)現(xiàn)，在不同的原始誤匹配率下，RANSAC方法始終帶有一定的棄真率，這是由求解的模型參數(shù)陷入局部極值造成的。而本文方法，在原始誤匹配率達(dá)到87%之前，都保持著較低的棄真率與取假率，尤其是在誤匹配率達(dá)到50%之前，有著理想的棄真率與取假率，具有穩(wěn)健的模型參數(shù)解，相對(duì)優(yōu)于RANSAC方法，符合預(yù)期結(jié)果。但在誤匹配率達(dá)到87%之后，本文方法的棄真率急劇上升，RANSAC方法棄真率則保持在38%左右。這是由于本文方法引入的主成分分特性所造成的，當(dāng)誤匹配率極大時(shí)，正確信息被湮沒(méi)在噪聲信息之中造成了正確主成分提取失敗。但在實(shí)際應(yīng)用過(guò)程中，原始誤匹配率達(dá)到80%的情況不易發(fā)生，本文方法在棄真率與取假率方面總體而言優(yōu)于RANSAC方法。

表2 對(duì)比結(jié)果信息

3 結(jié) 語(yǔ)

經(jīng)典的RANSAC方法將隨機(jī)挑選的小部分點(diǎn)對(duì)作為輸入，計(jì)算模型參數(shù)，然后驗(yàn)證全部點(diǎn)對(duì)，留下能夠滿足大多數(shù)點(diǎn)對(duì)的模型參數(shù)作為結(jié)果，是一種“由小到大”的思想。本文方法首先將全部點(diǎn)對(duì)作為輸入，利用主成分分析思想，剔除可能的誤匹配點(diǎn)對(duì)，計(jì)算模型參數(shù)，然后驗(yàn)證全部點(diǎn)對(duì)，迭代求解出穩(wěn)健的模型參數(shù)，是一種“由大到小”的思想。RANSAC方法由于這種隨機(jī)抽選的特性，使得其容易陷入局部極大值，求解不出最優(yōu)的模型參數(shù)。針對(duì)這種不足，本文方法將整體匹配點(diǎn)對(duì)作為輸入，避免了局部極值的弊端，能夠求解出相對(duì)穩(wěn)定的模型參數(shù)。試驗(yàn)表明，在中、低原始誤匹配率的情況下，本文方法迭代次數(shù)較少，總體耗時(shí)較短，棄真率與取假率較低，相對(duì)優(yōu)于RANSAC方法；在高原始誤匹配率的極端情況下，本文方法相對(duì)劣于RANSAC方法。同時(shí)，本文在試驗(yàn)中推導(dǎo)并采用了奇異值分解模型和基本矩陣模型，在實(shí)際應(yīng)用中可根據(jù)情況更換模型。

[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] 王亞偉, 許廷發(fā), 王吉暉. 改進(jìn)的匹配點(diǎn)提純算法mRANSAC[J]. 東南大學(xué)學(xué)報(bào)(自然科學(xué)版), 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]. 中國(guó)圖象圖形學(xué)報(bào), 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變換的匹配對(duì)提純[J]. 中國(guó)圖象圖形學(xué)報(bào), 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] 王俊淑, 江南, 張國(guó)明, 等. 融合光譜-空間信息的高光譜遙感影像增量分類算法[J]. 測(cè)繪學(xué)報(bào), 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] 王文波, 趙攀, 張曉東. 利用經(jīng)驗(yàn)?zāi)B(tài)分解和主成分分析的SAR圖像相干斑抑制[J]. 測(cè)繪學(xué)報(bào), 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] 林東方, 朱建軍, 宋迎春, 等. 正則化的奇異值分解參數(shù)構(gòu)造法[J]. 測(cè)繪學(xué)報(bào), 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協(xié)同計(jì)算的并行奇異值分解方法[J]. 計(jì)算機(jī)科學(xué), 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] 徐文華, 孫學(xué)棟. 奇異值分解求線性最小二乘解的理論分析[J]. 貴陽(yáng)學(xué)院學(xué)報(bào)(自然科學(xué)版), 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] 吳春國(guó), 梁艷春, 孫延風(fēng), 等. 關(guān)于SVD與PCA等價(jià)性的研究[J]. 計(jì)算機(jī)學(xué)報(bào), 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] 聶振國(guó), 趙學(xué)智. PCA與SVD信號(hào)處理效果相似性與機(jī)理分析[J]. 振動(dòng)與沖擊, 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] 數(shù)據(jù)科學(xué)自媒體. 解碼數(shù)據(jù)降維: 主成分分析(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] 錢征文, 程禮, 李應(yīng)紅. 利用奇異值分解的信號(hào)降噪方法[J]. 振動(dòng)、測(cè)試與診斷, 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] 王建國(guó), 李健, 劉穎源. 一種確定奇異值分解降噪有效秩階次的改進(jìn)方法[J]. 振動(dòng)與沖擊, 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.

(責(zé)任編輯：張艷玲)

The Purification Method of Matching Points Based on Principal Component Analysis

DONG Yang，F(xiàn)AN Dazhao，JI Song，LEI Rong

Information Engineering University，Zhengzhou 450000，China

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.

image matching; principal components analysis; singular value decomposition; purification; random sample consensus

The National Natural Science Foundation of China (No.41401534); State Key Laboratory of Geographic Information Engineering (No. SKLGIE2013-M-3-1)

DONG Yang(1992—)，male，postgraduate，majors in digital photogrammetry.

FAN Dazhao

董楊，范大昭，紀(jì)松,等.主成分分析的匹配點(diǎn)對(duì)提純方法[J].測(cè)繪學(xué)報(bào)，2017,46(2)：228-236.

10.11947/j.AGCS.2017.20160250. DONG Yang，F(xiàn)AN Dazhao，JI Song，et al.The Purification Method of Matching Points Based on Principal Component Analysis[J]. Acta Geodaetica et Cartographica Sinica,2017,46(2):228-236. DOI:10.11947/j.AGCS.2017.20160250.

P236

A

1001-1595(2017)02-0228-09

國(guó)家自然科學(xué)基金(41401534)；地理信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金(SKLGIE2013-M-3-1)

2016-05-24

董楊(1992—)，男，碩士生，研究方向?yàn)閿?shù)字?jǐn)z影測(cè)量。

E-mail： wenku34@163.com

范大昭

E-mail： fdzcehui@163.com

修回日期： 2017-01-04