論文推薦|董楊：主成分分析的匹配點對提純方法

《測繪學報》

構建與學術的橋樑 拉近與權威的距離

測繪地理信息與導航高端論壇 ——《測繪學報》創刊60周年學術研討會通知（第一號）

董楊

, 范大昭

, 紀松, 雷蓉

信息工程大學, 河南 鄭州 450000

收稿日期：2016-05-24； 修回日期：2017-01-04

基金項目：國家自然科學基金（41401534）；地理信息工程國家重點實驗室開放基金（SKLGIE2013-M-3-1）

第一作者簡介： 董楊(1992-),男,碩士生,研究方向為數字攝影測量。

E-mail： [email protected]

摘要：傳統的匹配點對提純演算法通常需要尋找小部分點集作為初始輸入，再迭代求解出能夠滿足大多數點對約束要求的最優解，其提純結果易陷入局部極值，造成正確匹配點對的遺漏。針對這一問題，本文引入了主成分分析思想，將整體點集作為初始輸入，逐步剔除誤匹配點對，穩健求解，得到更為準確的全局最優解，降低正確匹配點對的遺漏率，達到較好的提純效果。試驗表明，本文方法在一定的原始誤匹配率下，能夠得到整體最優解，在剔除誤匹配點對的同時，能夠避免或減少正確匹配點對的遺漏。

關鍵詞： 影像匹配 主成分分析 奇異值分解 提純 RANSAC

The Purification Method of Matching Points Based on Principal Component Analysis

DONG Yang

, FAN Dazhao

, JI Song, LEI Rong

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

在影像匹配過程中，經常會存在一些誤匹配點對，這時可以通過匹配提純的方法對誤匹配點對進行剔除。一般的提純思路是尋找一個恰當的匹配點對約束模型，估計出正確的模型參數，利用約束模型進行匹配點對提純。在匹配點對約束模型中，通常使用變換約束矩陣作為估計模型，其一般包括平移變換、剛體變換、相似性變換、仿射變換、射影變換、極線幾何基本矩陣變換等。現行的變換約束矩陣模型已經能夠很好地進行匹配點對間的幾何約束，因此大多數學者更加傾向於模型參數估計方法的研究。

在模型參數估計中，常用的方法有穩健回歸估計和隨機參數估計等。對於穩健回歸估計方法，如M-估計[

-

]，其核心思想是採用迭代加權最小二乘估計回歸係數，但其僅能適應誤匹配率較小的情況。對於隨機參數估計方法，如LMedS(least median of squares)演算法[

-

]、MLESAC(maximum likelihood estimation sample and consensus)演算法[

]和RANSAC(random sample consensus)演算法[

]等，其核心思想是隨機選擇樣本子集，迭代挑選出最佳模型參數。其中，RANSAC演算法能夠在存在大量外點的數據中找到內點，因而得到廣泛應用並派生出一系列改進演算法[

-

]。改進的RANSAC方法主要從兩個方面進行了優化。一方面是速度優化，如P-RANSAC(preemptive RANSAC)[

-

]和R-RANSAC(randomized RANSAC)[

-

]等；一方面是提純率的優化，如M-RANSAC(multi RANSAC)[

]等。然而這些演算法都需要選擇一個合適的初始內點集，提純結果容易陷入局部最優解，造成部分正確匹配點對遺漏；在誤匹配率增大時，成功選擇內點集的試驗次數也急劇增大。除了以上的約束模型及參數估計方法，近期也有一些其他的研究成果[

-

]。文獻[

]提出通過統計模板的旋轉角度直方圖來剔除誤匹配，但其依賴角度區間的劃分，僅適用於對精度要求不高的情況；文獻[

]提出一致性函數(correspondence function)模型，通過學習匹配點對一致性函數來拒絕誤匹配；文獻[

]提出通過Hough變換求解模型參數來進行匹配點對提純，然而僅適用於模型參數較少的情況。由此，在匹配點對約束模型選定的情況下，本文對如何求解模型參數整體最優解，實現穩健匹配點對提純的問題進行了研究。主成分分析(principal components analysis，PCA)[

-

]是一種有效的多元統計方法，在信號處理、統計學等領域有重要應用。類似於信號處理過程中利用主成分分析方法進行雜訊去除，可將主成分分析思想引入匹配點對提純的過程，逐步剔除雜訊點，實現匹配點對的提純。為了方便闡述與試驗，文中以奇異值分解作為主成分分析的具體實現方法，並以此為基礎對提純方法進行了推導與論述。奇異值分解[

-

](singular value decomposition，SVD)是矩陣分析中正規矩陣酉對角化的推廣，是一種重要的主成分分析實現方法，能夠進行并行化計算[

-

]，可用於最小二乘求解[

-

]，已被廣泛應用於各個領域。

本文分析了奇異值分解中奇異值的對應含義，並將其引用到匹配點對提純過程中。首先，用特定模型來描述匹配點對之間的變換關係，建立模型誤差方程；其次，對含有匹配點對信息的係數矩陣進行奇異值分解，重構大奇異值對應的矩陣，得到差分矩陣；然後，剔除可能的誤匹配點對，構造降階矩陣，進行模型求解；最後，利用求解的模型參數，進行匹配點對約束，達到匹配點對提純的目的。

1 匹配點對提純模型與演算法1.1 主成分分析與奇異值分解模型

經典的主成分分析演算法通過計算輸入數據的協方差矩陣及其特徵向量來實現數據主成分的提取。當數據規模較大時，這一途徑的計算代價非常昂貴。而奇異值分解與主成分分析都是特徵正交分解(proper orthogonal decomposition，POD)，具有等價性[

]，在實際應用中處理效果相似[

]。奇異值分解無需計算協方差矩陣，無需進行均值化處理，計算量少，能避免計算協方差矩陣的舍入誤差，相對誤差較小，因此計算主成分最優的方法是使用奇異值分解

式中,

為

×

維正交矩陣；

為

×

維正交矩陣,

為

×

維對角陣。

的列向量

稱為矩陣

的左奇異向量；

的列向量

稱為矩陣

的右奇異向量；

的對角線元素

12≥…≥

。由矩陣

的前

個奇異值重新組成對角陣

=diag[

12,…,

]，由奇異值對應的左、右奇異向量重新組成矩陣

12,…,

]和

1

]，利用式(1)可重構矩陣

，得到

對式(2)進行化簡可得

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

可以發現,

與

′間僅相差小奇異值對應的部分。研究表明，大的奇異值對應的重構矩陣

′包含更多的主要信息，小的奇異值對應的差分矩陣

包含更多的雜訊信息[

-

]。基於這種思想，

則反映了矩陣

中雜訊信息的大體分佈情況。因此，可依據差分矩陣

進行矩陣

中的雜訊剔除，得到更為合理的降階矩陣

，這也是本文主成分分析思想研究的關鍵。

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

隨著特徵點提取與匹配技術的不斷發展，硬體計算能力的日益增長，現行的匹配演算法已使匹配精度達到一個較高的水平。但由於演算法本身的缺陷，不可避免地存在一些誤匹配點對，這時就需要利用一些技術手段將其剔除。在此背景下，本文以「正確匹配點對佔據匹配中的主要成分」為先驗條件，結合現有的數據分析技術，嘗試在匹配點對提純中引入主成分分析思想，從而求解出較優的提純結果。

假設點集

＝

i=0，1，…,

中包含

個點，匹配點對間的約束模型為

。為了求解

的模型參數，可通過數據

，得到

個誤差方程。對所有誤差方程進行主成分分析，得到正確匹配點對對應的誤差方程，然後求解出模型參數，最後依據精準的模型進行匹配點對的約束提純。在此過程中使用整體點對信息進行參數求解，相比於RANSAC方法大大減少了迭代次數，避免了RANSAC方法隨機採樣造成的多次運行結果可能不一致的現象，從而增加了求解的穩定性。由於主成分分析是一個非精準的過程，以上過程需迭代進行，如

所示。

為了具體說明提純方法，下文以奇異值分解作為主成分分析的具體實現方法，以基本矩陣模型作為約束模型，對以上過程進行詳細推導。

1.3 基於奇異值分解的匹配點對提純演算法

匹配點對提純應遵循兩個原則：一是正確匹配點對被剔除的概率應盡量小，即「棄真」錯誤少發生；二是誤匹配點對被接受的概率應盡量小，即「取偽」錯誤少發生。前者避免了提純演算法過於嚴格，後者避免了提純演算法過於寬鬆。兩者相互作用，避免了提純結果陷入局部最優解，確保了提純過程的穩健性。匹配提純的實質是匹配點對間模型參數的確定，選擇合適的模型以及適當的參數，使其滿足提純的兩個原則，即可實現匹配點對間的提純操作。這裡使用基本矩陣模型進行求解推導。

影像間匹配點對一般滿足極線幾何約束，即對應匹配點應在對應極線上。這一約束可通過基本矩陣描述為

式中，

=(

,1)T、

′=(

′,

′,1)T分別為匹配點對齊次坐標；

為基本矩陣。令

=(

ij)，則式(5)可寫為如下形式

式中，

=[

11

12

13

21

22

23

31

32

33。將式(6)作為模型,

作為待解參數，可進行匹配點對的提純。給定

對匹配點對可以得到線性方程組

式中,

為

×9維的係數陣。對

進行奇異值分解，利用前

個奇異值得到其對應的差分矩陣

，則每一匹配點對對應的近似誤差值為

，進一步得到近似均方誤差

式中，

為

中的元素。以近似均方誤差作為閾值，對每一匹配點對誤差方程進行篩選，得到約束后的匹配點對誤差方程，然後再次重新組成係數矩陣，得到降維矩陣

。對矩陣

再次進行奇異值分解，求解

的最小二乘解，並進行秩2約束，得到最終的模型參數解

。利用求解的參數及相應的模型，對匹配點對進行約束，得到提純點對。利用提純后的點對迭代進行以上步驟，直到求解的模型參數

趨於穩定。整個演算法流程如

所示。

2 試驗及其結果分析

上述演算法中，重要的一步是計算重構矩陣時奇異值個數t的確定。一個恰當的t應能使計算的重構矩陣A′中的正確匹配點對部分，與原始矩陣A中對應的正確匹配點對部分盡量相似，而對應的誤匹配部分盡量相差較大。即ΔA中正確匹配點對的近似誤差值盡量小，而誤匹配點對的近似誤差值盡量大。

利用多幅影像進行試驗，這裡選取某幅影像中的1000對正確匹配點對進行說明。如圖 3所示，對前100對匹配點對加入隨機誤差，分別在t=1,2,…,8的條件下求解差分矩陣，計算每一匹配點對對應的近似誤差，得到如圖 4所示的結果。

圖 4中橫軸表示匹配點對，縱軸表示對應的近似誤差值，其中前100個為誤匹配點對，可以看出當t值取5時，已經能夠很好地區別正確匹配點對與誤匹配點對，當t值增大時，雖然這種區別更加明顯，但計算量也隨之而增長。在實際操作中取t=5。

在得到恰當的t值后，為了進一步驗證本文演算法的實際效果，對含有不同誤點率的影像匹配點對進行了試驗，截取其中6對試驗影像，如圖 5至圖 10所示。其中，每幅圖中(a)圖表示原始像對圖，(b)圖表示加入誤匹配點對后的像對圖，(c)圖表示利用本文方法進行點對提純后的像對圖。

圖 5至圖 7為手機拍攝影像，圖 8至圖 9為普通相機拍攝影像，圖 10為航拍影像。可以看出，在不同場景中隨著誤匹配率的不斷提升，本文方法仍能保持著優良的提純率，反映了本文方法較好的穩健性。同時，為了比較本文演算法的效率與全局求解的優勢，將上述像對分別用經典RANSAC演算法進行處理，統計每次的運算耗時與實際迭代次數，統計如表 1所示。其中，設置RANSAC演算法迭代上限為2000次，本文演算法迭代上限為50次，編號1—編號6數據分別對應圖 5—圖 10。

表 1 對比結果信息Tab. 1 Comparison results table

表選項

表 1中時間欄為多次試驗的平均耗時。同時，本文認為試驗中處理時間差異在10 ms以內的兩種方法處於相同的耗時水平。由表 1可以看出不同情況下本文方法迭代次數皆遠小於RANSAC方法的迭代次數。由於全局求解的優勢，本文方法在數次迭代后便可得到最優解，而RANSAC方法由於隨機抽樣的特性，在大數據量與高誤點率的情況下，迭代次數驟然上升。試驗中編號為5和6的數據試驗結果表明RANSAC方法在此種情況下已達到迭代次數上限。同時，由表 1也可以看出在低誤點率情況下，本文方法與RANSAC方法時間消耗相當，在中誤點率的情況下，本文方法時間消耗少於RANSAC方法，而在高誤點率的情況下，本文方法耗時多於RANSAC方法。這種特性是由奇異值分解過程的耗時與迭代次數上限的設置共同造成的。單次奇異值分解的耗時大於單次隨機採樣求解的耗時，在低誤點率的情況下，RANSAC方法迭代次數多於本文方法，總體而言時間消耗相當；在中誤點率的情況下，RANSAC方法迭代次數驟然增加，而本文方法迭代次數增加緩慢，總體而言本文方法耗時相對較少；在高誤點率的極端情況下，由於RANSAC方法迭代次數已達到上限，而本文方法的迭代次數繼續增加，耗時相對較多。在實際應用中可通過奇異值分解演算法的并行求解與GPU加速縮短單次求解時間，優化整體耗時。

為了進一步驗證本文演算法與現有演算法間的性能優劣，取1000對正確匹配點對逐步加入隨機誤差，分別用經典RANSAC演算法和本文演算法對匹配點對進行提純，得到結果如表 2和圖 11所示。

表 2 對比結果信息Tab. 2 Comparison results table

試驗中，RANSAC演算法和本文演算法的最終閾值約束都設置為3。根據之前提到的兩個原則，定義棄真率的計算公式為

=

t1/

，

t1表示未能被提取出來的正確匹配點對個數，

表示總共的正確匹配點對個數；定義取假率的計算公式為

=

f1/

，

f1表示被提取出來的誤匹配點對的個數，

表示總共的誤匹配點對個數。圖11中橫軸表示原始匹配點對中的誤匹配率值，縱軸表示比率值。

中括弧內的數據表示誤匹配點對的個數。由

和

中數據可以發現，在不同的原始誤匹配率下，RANSAC方法始終帶有一定的棄真率，這是由求解的模型參數陷入局部極值造成的。而本文方法，在原始誤匹配率達到87%之前，都保持著較低的棄真率與取假率，尤其是在誤匹配率達到50%之前，有著理想的棄真率與取假率，具有穩健的模型參數解，相對優於RANSAC方法，符合預期結果。但在誤匹配率達到87%之後，本文方法的棄真率急劇上升，RANSAC方法棄真率則保持在38%左右。這是由於本文方法引入的主成分分特性所造成的，當誤匹配率極大時，正確信息被湮沒在雜訊信息之中造成了正確主成分提取失敗。但在實際應用過程中，原始誤匹配率達到80%的情況不易發生，本文方法在棄真率與取假率方面總體而言優於RANSAC方法。

3 結 語

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

【引文格式】董楊，范大昭，紀松，等。 主成分分析的匹配點對提純方法[J]. 測繪學報，2017，46(2)：228-236. DOI: 10.11947/j.AGCS.2017.20160250

權威 | 專業 | 學術 | 前沿

微信投稿郵箱 | [email protected]

歡迎加入《測繪學報》作者QQ群： 297834524