基于SIFT算子融合最大相異系數的自適應圖像匹配算法

陳 虹，肖 越，肖成龍，宋 好

(遼寧工程技術大學軟件學院，遼寧葫蘆島125105)

(*通信作者電子郵箱1150996133@qq．com)

0 引言

近年來，隨著計算機視覺領域的飛速發展，圖像匹配技術逐漸引起各界的廣泛關注。目前已在多個領域得到大量研究及應用，如工件識別［1］、醫學診斷［2］、計算機視覺［3］、自動跟蹤定位［4－5］、人臉識別［6－7］、圖像三維重建［8］等。

圖像匹配指兩幅圖像間的映射關系，即具有相同中心事物不同視點的兩幅圖像，將彼此在空間中同一位置的點聯系起來的過程。在實際操作中，待匹配的圖像往往獲取自不同環境，在尺度、亮暗、視角、噪聲等方面存在差異，因此給圖像匹配技術帶來了難度。從方法上來說，目前主要的圖像匹配方式分為基于灰度匹配的方法、基于特征提取的匹配方法兩類。基于灰度匹配的方法，例如序貫相似性檢測(Sequential Similarity Detection Algorithm，SSDA)、去均值歸一化互相關法NNPROD(average-removed normalized cross-correlation)等，基于灰度的匹配對圖像尺度、旋轉、亮暗、視角等變換較敏感。相比之下，基于特征提取的方法具有良好的尺度不變性。常見特征提取算法有尺度不變特征變換(Scale Invariant Feature Transform，SIFT)［9］、角點提取 Harris［10］、SURF(Speeded Up Robust Feature)［11－12］等。文獻［4］和文獻［12］通過對幾種代表性的局部特征進行多項實驗評估，結論顯示SIFT算法的魯棒性最佳。

文獻［13］將SIFT特征描述子結合全局信息，以達到降低誤匹配的目的，但計算量大，由于范圍固定的全局信息描述，導致計算結果受尺度變化影響較大。文獻［14］中提出通過差值運算將128維特征向量轉化為128維二值特征描述子，達到降維和提升運算速度的目的，但同時降低了匹配正確率。Zhou等［15］將SIFT中128維特征描述子轉化為256維緊湊的二值特征描述子，在匹配速度上稍有提升，但仍以降低匹配正確率為代價。以上文獻都在如何降低誤匹配、提升運算速度等方面進行了深入的探索，但不可避免地在提升運算速度過程中降低了匹配正確率。另外，文獻［16］指出SIFT算法選用單一的歐氏距離比的測度方法，導致SIFT算法在原圖像和目標圖像相似區域較多的情況下，會出現明顯的錯配和亂配的情況。

針對以上問題，本文提出一種基于SIFT算子融合最大相異系數的圖像匹配算法。綜合考慮，由于算法復雜度高導致效率降低、特征描述子降維運算導致的匹配正確率損失、圖像相似區域較多導致錯配亂配等問題，將特征向量相似性程度測量運算融合于SIFT圖像匹配中，在可以承受的時間范圍內，盡可能提升匹配正確率，同時不會過多地增加算法復雜度，并解決相似區域易出現錯配亂配問題。

1 相關工作

1．1 SIFT算法基本原理

尺度不變特征變換(SIFT)［9］是由哥倫比亞大學的Lowe提出的，用于提取圖像局部特征描述子，該算法對于圖像的平移、旋轉、仿射變換等情況均具有良好的穩定性與匹配能力，其基本思想是在尺度空間中提取位置、尺度和旋轉無關量。具體做法是根據尺度空間概念構建尺度空間，在尺度空間中尋找局部極值點，將局部極值點中的低響應點與邊緣響應點剔除，確定關鍵點的主方向，生成關鍵點的描述子，最后進行特征點的匹配。

SIFT圖像匹配算法主要包括3個步驟:

步驟1 特征點檢測。特征點檢測分為尺度空間極值檢測、關鍵點定位、關鍵點方向分配三步。

尺度空間極值檢測 不同尺度空間下的空間表示L(x，y，σ)，可由二維圖像 I(x，y) 與高斯核 G(x，y，σ) 的卷積得到，σ為空間尺度因子。

利用高斯差分(Difference of Gaussian，DoG)近似高斯拉普拉斯(Laplace of Gaussian，LoG)在構造的尺度空間中搜索穩定的關鍵點:

由此得到高斯金字塔，通過相鄰尺度圖像相減生成DoG金字塔并形成尺度空間。尺度空間中，如果一個點同周圍8個點以及相鄰上下層中2×9=18個點共26個點進行比較，該點均為最大或最小，該點即為局部極值點。

關鍵點定位 由于DoG值對噪聲和邊緣響應較敏感，因此DoG尺度空間中檢測到的極值點中包含較多低響應點，關鍵點需要進一步精確定位。利用Hessian矩陣計算主曲率設置閾值的方法，剔除邊緣響應點。

關鍵點方向分配 根據關鍵點附近鄰域的梯度方向分布信息，為每個關鍵點指定方向參數，梯度值的m(x，y)和θ(x，y)的計算如式(4)和式(5)所示:

其中:L為關鍵點所在的尺度空間值，m(x，y)是梯度的模值，θ(x，y) 表示點 (x，y) 處的方向值。

步驟2 特征點生成。實際計算過程中，以每個關鍵點為中心取16×16像素窗口，并在每個窗口中取4×4像素種子點來描述，每個種子點方向由8個方向梯度累加，故單個關鍵點就形成了128維的描述特征向量。

步驟3 特征點匹配。生成SIFT特征描述符向量后，采用最近鄰(Nearest Neighbor，NN)算法［9］進行特征點匹配，當查詢樣本與目標樣本最近鄰特征點歐氏距離與次近鄰特征點歐氏距離比值小于某一閾值時，認為該特征點對匹配成功，否則匹配失敗。根據Lowe的實驗，閾值設定為0．8。

1．2 研究現狀

針對傳統SIFT算法的改進研究已進行了多年，改進算法層出不窮。主要改進方法包括以下幾方面:融合其他經典圖像匹配算法優勢的改進、融合多方法的SIFT特征降維改進、基于特征點匹配方式的改進、增加精確匹配篩選等。文獻［17］中提出將角點檢測(Harris)的閾值準則與SIFT特征提取過程融合，對基于SIFT提取的尺度不變特征進行再次篩選，從而得到穩定性佳、可區分性強的特征點;傅衛平等［1］利用多分辨率小波變換(multiscale wavelet transform)，構建低頻信息參與匹配，將特征向量降維到32維，并利用積分圖像進行精確匹配篩選;文獻［18］采用分級放射狀分區的方法，同樣達到降維目的，并提出運用馬氏距離(Mahalanobis distance)雙向匹配方法取代原SIFT算法中歐氏距離匹配方法。本文分析當前研究現狀得出，基于原SIFT匹配效果并不理想，增加精確匹配篩選是必要的，并利用在特征點匹配階段融合有效方法，對特征點匹配方法進行改進，能夠達到提升特征點匹配效率、有效降低誤匹配的目的。

2 匹配算法改進

SIFT算法進行相似區域較多的圖像匹配時，某些點的鄰域信息非常相近，便會出現很明顯的錯配和亂配現象。為保證圖像匹配的準確性，需通過有效手段剔除誤配點對。文獻［19］中提到一般向量的相似性函數測度方法，故提出在歐氏距離比約束基礎上，增加向量相似性約束提升匹配率。

2．1 最大相異系數

原SIFT算法中采用與樣本圖像最近鄰特征點歐氏距離與次近鄰特征點歐氏距離比值小于0．8來提取匹配點，但并未考慮特征向量間的相關性，單一的向量分量可能會影響結果的準確性。

衡量兩個向量間的相似性方法有距離測度法和相似性函數法［19］。歐氏距離是最常見的距離測度法，通過衡量向量空間距離來表示向量間相似程度，距離越近向量越相似;相似性函數法通過函數的方法來表征向量間的相似程度，最大相異系數是相似性函數法中的一種，適用于比較未知向量與已知向量間的相似性。故在距離測度基礎上，增加空間向量相似性約束，通過自適應估計每組匹配圖像的最大相異系數，高于最優取值的匹配視作誤匹配，以此降低誤匹配個數。

具體做法:在對應目標圖像與查詢圖像間的某組特征描述符向量歐氏距離比小于0．8基礎上，進一步計算兩描述符向量的最大相異系數Zy［19］，最大相異系數 Zy取值范圍［0，∞)，Zy取值越小兩向量越接近，Zy=0兩向量完全相同。最大相異系數法通過加權平均過程，突出了差異較大元素對判決的影響力，而差異較小的元素則并不在判決中起到實質作用。x和y分別代表未知待比較向量與已知確定向量，如式(6)計算兩向量的相對誤差向量λ，將向量λ中各分量進行從大到小排列重組為:λ ={λi＞ λj，i≤j}，取出λ的前k個值得到ξ ={λ1，λ2，λ3，…，λk};最后，對ξ 向量進行加權平均得到最大相異系數Zy。

通過分析式(7)，計算128維特征描述符向量的最大相異系數需要確定符合計算要求的k值。既要保證選定的k值計算出的數值穩定，又要保證k值對應的最大相異系數足夠小，故選用繪制k-Zy圖像來分析最優k值選取問題。根據Zy數值越小向量越接近原則，從圖中得出Zy數值最小值穩定在k=125處，如圖1所示。通過分析k-Zy關系圖像發現，Zy在k=126處出現明顯躍升，k=125處取到曲線最小值。

圖1 最大相異系數隨k變化Fig．1 Change of Zywith k

2．2 最優最大相異系數自適應估計

待匹配的每組圖像各不相同，形成的向量集也就不同。由此提出對于每組匹配圖像進行最優最大相異系數自適應估計，利用最優Zy約束初篩匹配點集，進一步剔除誤匹配點。

為了檢驗實驗結果的正確性，需要引入匹配正確率的概念。利用隨機抽樣一致性算法(Random Sample Consensus，RANSAC)計算出圖像匹配過程中的“內點”和“外點”，從而得出正確的匹配率。通過RANSAC算法優化得到正確的匹配點數目記作N1，誤匹配點數目記作N2，匹配正確率P計算公式如式(8)［20］所示:

在執行RANSAC優化算法之前，先根據Lowe推薦的0．8歐氏距離比篩選根據最近鄰距離算法(NN)［9］得到的匹配點集，獲取初篩匹配點集 Si，并在 Zy∈［0．2，1．0］范圍內自適應估計最優最大相異系數Zb，從Si匹配點集中選取滿足特征點間最大相異系數值Zy＜Zb條件的匹配，如滿足便記作符合最優匹配條件，具體做法如下:

步驟 1 取 Zy∈［0．2，1．0］，以0．01 為步長，嘗試根據每個Zy來篩選Si中所有匹配點，并獲取篩選后匹配點集Sf，Sf滿足其中每組特征描述符向量的最大相異系數均小于等于Zy。

步驟2 對獲取的Sf執行RANSAC優化算法，根據優化結果得到正確匹配點數目N1，計算匹配正確率P。

步驟3 將 Zy∈［0．2，1．0］，以0．01為步長的80 個取值全部整合，繪制Zy-P，Zy-N1，Zy-Ms(N1×P)關系圖像如圖2所示(為在同一坐標系中顯示，將P×500顯示)，由圖2整合曲線圖可知，隨Zy取值的不斷變化，Ms的取值逐步增大。

圖2 Zy-Ms圖像Fig．2 Diagram of Zy-Ms

步驟4 利用三分法分析Zy-Ms折線圖，獲得最優Zy取值Zb，設置相鄰Ms計算差值小于1×10－5時，停止進一步精確取值操作。Ms取得穩定最大值對應的Zy值，作為最大相異系數最優值。

3 實驗結果及分析

3．1 實驗用圖

實驗平臺為 Windows 7操作系統、CPU 2．50 GHz、內存4 GB的PC機，編譯環境為 python2．7．5，并加入了開源庫OpenCV。本實驗采用Daniel Scharstein和Richard Szeliski立體匹配實驗所用的圖像［21］，選用 venus、sawtooth、map、poster四組圖像。

其中每組圖像均來自于一段三維立體動圖，圖像在亮暗、視角、尺度等方面均存在變化，由于保持中心事物不變，導致目標圖像與查詢圖像存在大量相似區域。基于以上特性，選用該立體匹配圖像組能有效檢驗算法在相似區域較多情況下的匹配能力。本次實驗從每組立體圖像中選取兩張圖像，一張作為目標圖像img_train，一張作為查詢圖像img_query，在查詢圖像中尋找對應目標圖像的匹配，如圖3所示。

3．2 最佳最大相異系數求解實驗

針對2．2節介紹的最優最大相異系數求解方法，本文對venus、sawtooth、bull、poster四組圖像分別進行實驗，求出符合每組圖像的最大相異系數最優取值。匹配過程從查詢圖像到目標圖像，在進行RANSAC算法優化時，理論上至少含有7個點才可計算基礎矩陣，Zy取值應保證RANSAC優化算法基礎矩陣的計算生成，由此本實驗過程中設定備選Zy最小值為 0．2，最大值為 1．0。

根據改進算法，計算篩選后特征點集的匹配點數、正確匹配點數、匹配正確率，并與原SIFT算法進行比較。實驗結果表明單次匹配平均時間在1．236 s左右，保證高準確率的前提下匹配用時可以接受，匹配率方面提升10個百分點左右。實驗結果如表1所示，篩選后總體點數下降，獲取RANSAC優化后提取的正確匹配點數卻上升。證明最大相異系數對特征向量相似性篩選，在除去誤匹配方面確實起到了一定作用。

圖3 實驗用圖Fig．3 Image in experiment

表1 四組圖像的最優Zy求值結果Tab．1 Optimal Zyof four sets of images

3．3 相關算法比對分析

本文算法(算法1)思路來自計算向量間最大相異系數，衡量向量間的相似性程度，確定特征點是否匹配。文獻［16］(算法2)中提出了一種歐氏距離測度與余弦相似度相結合的匹配提取算法，將特征方向的一致性作為圖像匹配約束;文獻［20］(算法3)中提出通過自適應獲取最優歐氏距離比閾值，并通過雙向匹配剔除誤匹配點。以上所提兩種算法，其根本思路均是基于對SIFT特征描述子的操作，算法2將余弦相似度融合SIFT算子，從空間上約束特征點匹配;算法3通過對SIFT特征描述子的處理，獲取最大匹配點數，并通過擬合曲線的交點得到最優ratio取值。相比其他經典算法，上述兩種算法從算法設計角度看，與算法1出發點是相同的，更具有可比性。將上述算法，從匹配正確率、匹配點數、正確匹配點數、算法耗時幾方面進行綜合比較。算法比對結果如表2所示。從表2分析可知，本文算法較其余兩種算法，在匹配正確率方面表現良好，針對不同組測試圖像均能提取較多正確匹配。但從venus組圖像數據看，算法3匹配正確率較低，但提取出更多正確匹配點數。在算法耗時上，算法2耗時最少，本文算法耗時較算法2稍有增多，但明顯少于算法3。

表2 算法性能比對結果Tab．2 Comparison results of algorithms performance

綜合分析，本文算法較好地提升了匹配正確率，獲取了更多的正確匹配點數，同時算法耗時適中，有效改進了相似區域較多情況下的錯配亂配問題，降低了誤匹配率。缺點是在剔除誤匹配的過程中，針對不同圖像也有不同程度上正確匹配點數的損失。經過對比分析，本文算法整體表現良好，實驗結果基本滿足最初算法設計目的。

如圖4所示，對比優化前后的匹配圖像，大部分雜亂的誤匹配已被優化算法成功剔除。

圖4 優化前后匹配圖像對比Fig．4 Matched image comparison before and after optimization

4 結語

本文在基于SIFT特征算子的基礎上，提出融合最大相異系數的自適應匹配算法。在單一的歐氏距離比基礎上，添加向量相似性約束，將未知向量與已知向量比較過程中相似度測量考慮在內，對于相似區域較多容易出現錯配或亂配的情況進行了相應優化。本文所述方法可獲得較多的匹配點，并提升了正確匹配率。在實時性要求不高的系統中，利用本文方法可以保證良好的匹配正確率，剔除誤匹配點。