黃春鳳 劉守山 別治峰 許廣會

摘? 要： 針對加速穩(wěn)健特征（Speeded Up Robust Features，SURF）算法在三維重建中匹配準確率低的問題，提出基于SURF算法的改進算法。首先利用SURF算法提取特征點，通過近鄰搜索（Best Bin Fast，BBF）算法實現(xiàn)Kd?Tree快速查找最近鄰特征點，結(jié)合雙向唯一性匹配的方法完成圖像匹配，然后在視差約束下，利用視差梯度約束對初始特征匹配對進行預處理，篩選掉一些偏差較大的匹配對，最后采用隨機抽樣一致（Random Sample Consensus，RANSAC）算法對特征點二次優(yōu)化和去噪處理。將其他改進算法和提出的改進算法分別進行圖像匹配處理比較，分析算法的性能，得到提出的改進算法匹配成功率達96.3%。實驗結(jié)果證明提出的改進算法簡單快速，匹配精度高。

關鍵詞： 圖像匹配; 特征點提取; 雙向匹配; 視差梯度; 隨機抽樣一致; 匹配精度

中圖分類號： TN911.73?34; TP391.9? ? ? ? ? ? ? 文獻標識碼： A? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2020）10?0111?05

Application of improved SURF algorithm in image matching

HUANG Chunfeng， LIU Shoushan， BIE Zhifeng， XU Guanghui

（College of Electronic Information Engineering， Shandong University of Science and Technology， Qingdao 266590， China）

Abstract： An improved algorithm based on SURF algorithm is proposed to improve the matching accuracy of SURF （speeded up robust features） algorithm in three?dimensional reconstruction. The feature points are extracted by means of the SURF algorithm， Kd?Tree searches the nearest neighbor feature points quickly by means of BBF （best bin fast） algorithm， and then the image matching is completed in combination with the biuniqueness matching method. Under the disparity constraint， the initial feature matching pairs are preprocessed by means of the disparity gradient constraint， some matching pairs with large deviation are screened out， and the quadratic optimization and de?noising processing of feature points are carried out by means of RANSAC （random sample consensus） algorithm. The performance of other improved algorithms and the proposed improved algorithm were compared and analyzed respectively for image matching， from which the matching success rate of the proposed improved algorithm is 96.3%. The experimental results show that the proposed improved algorithm is simple， fast and has high matching accuracy.

Keywords： image matching; feature point extraction; bidirectional matching; disparity gradient; random sample consistency; matching precision

0? 引言

近年來，隨著科技的進步，雙目立體視覺[1]技術被廣泛應用，例如圖像檢索[2]、三維重建[3]、目標識別[4]、圖像配準[5]等。其中，特征點檢測與匹配作為雙目立體視覺技術中的關鍵一步，顯得尤為重要。常見的適用于特征匹配的算法中，較為成熟的有SIFT算法和SURF算法。SIFT算法[6]具有尺度不變性和旋轉(zhuǎn)不變性，圖像在尺度變化和旋轉(zhuǎn)變化的情況下匹配效果受影響很小，由于采用差分高斯金字塔[7?8]進行特征點[7，9]提取，所以算法運行時間相應增加，降低了運行速度。1999年David Lowe提出了SURF[10]算法，由于SURF算法采用積分圖像[11]、Harr小波變換[12]和近似Hessian矩陣[10]來提高速率，增加算法魯棒性，所以相比SIFT算法，SURF算法運行速率快，魯棒性強。但在求主方向過程中依賴局部梯度區(qū)域像素程度較大，匹配成功率并沒有達到理想的效果，匹配精確度偏低。

本文首先在SURF算法的基礎上通過BBF算法實現(xiàn)Kd?Tree快速查找最近鄰特征點，結(jié)合雙向唯一性匹配的方法完成圖像匹配，然后在RANSAC算法之前利用視差梯度[13]約束對提取的特征點預處理，剔除大部分錯誤特征點，減少RANSAC算法計算量，對匹配結(jié)果中仍存在的偏差較大的偽匹配點，最后利用RANSAC算法進行二次優(yōu)化和去噪處理。實驗結(jié)果證明，該方法簡單快速，圖像匹配成功率高。

1? SURF算法原理與分析

1.1? 提取特征點

Hessian[10]矩陣是SURF算法提取特征點的核心步驟，可以理解為一個多元函數(shù)在某一點處的二次偏導構(gòu)成的方陣，是泰勒展開式的矩陣形式。對于一個圖像中的點P=（x，y），尺度為[σ]的矩陣[H（X，σ）]定義為：

[H（X，σ）=Lxx（X，σ）Lxy（X，σ）Lxy（X，σ）Lyy（X，σ）] （1）

式中：[Lxx]指高斯濾波二階微分，即[?2y?2xg（σ）]與像素點P = （x，y）的卷積，其中[g（σ）=12πσ2e-x2+y22σ2];類似地，[Lxy]和[Lyy]表 示[g（σ）]在各個方向的二階微分與像素點P = （x，y）的卷積。

通過盒子濾波運算，進一步求得矩陣H的判別式：

[det（Happ）=LxxLxy-（0.9Lxy）2] （2）

1.2? 特征點描述

通過在圓形鄰域內(nèi)計算特征點的Harr小波響應確定特征點的主方向。把與主方向水平的Haar小波響應稱為[dx]，垂直方向的稱為[dy]。通過計算[dx]，[dy] ， [|dx|] ， [|dy|]得到每個子區(qū)域的4個特征向量，則四維描述向量[Vden=dx，dy，|dx|，|dy|]，計算所有的4×4個矩形區(qū)域塊，一共得到4×（4×4）=64維向量。

1.3? 特征點匹配

采用歐氏距離的方法進行特征點匹配，針對一幅圖像中的某一個特征點，在另一幅圖像中搜索出兩個距離它最近的特征點。在這兩個特征點中，如果最近的距離[r1]除以次近的距離[r2]小于設定的閾值[14]P，則表示這兩個特征點匹配度好，可以作為匹配點，否則拋棄。

1.4? SURF算法的圖像匹配結(jié)果分析

根據(jù)以上所述過程，利用SURF算法進行圖像匹配，匹配結(jié)果如圖1所示。從匹配結(jié)果來看，圖像中匹配對較多，并且含有大量錯誤匹配對，匹配正確率低。針對此種情況，本文對SURF算法做了一系列改進。

2? 改進的匹配算法

本文對SURF算法進行改進，基于改進的SURF算法系統(tǒng)框圖如圖2所示。

2.1? 雙向匹配算法

SURF算法配合雙向匹配算法完成圖像匹配，并初步篩選錯誤匹配點，匹配過程中需要處理的數(shù)據(jù)量巨大，Kd?Tree在維數(shù)較多的情況下，運行速率會大幅度降低，為了提高匹配速度，結(jié)合BBF算法實現(xiàn)Kd?Tree快速檢索符合條件的特征點，完成雙向SURF算法匹配。

假設有兩幅待匹配圖像，分別為圖像1、圖像2。采用雙向匹配的方法改進SURF算法，增加了匹配結(jié)果的可靠性，目的是使圖像1中的特征點唯一對應圖像2中某個特征點，同時圖像2中的特征點唯一對應圖像1中某個特征點。原始的SURF算法匹配過程是以兩幅圖像中的一幅作為基準圖像，在另一幅圖像中尋找其對應的特征點，完成圖像匹配。雙向匹配算法在此基礎上增加了相反方向的單向匹配過程。具體步驟是：首先把圖像1作為基準圖像，針對已經(jīng)提取的圖像1中的所有特征點，利用SURF算法中采用歐氏距離實現(xiàn)匹配的方法，通過BBF算法實現(xiàn)Kd?Tree快速檢索特征點，在圖像2中找到與之對應的特征點，匹配結(jié)果如圖3a）所示;然后把圖像2反過來作為基準圖像，通過相同的方法，在圖像1中找到與之對應的特征點，匹配結(jié)果如圖3b）所示。采用運行在SURF算法之后的雙向匹配算法初步消除SURF算法匹配結(jié)果中的部分歧義匹配點和偽匹配點，參照圖3，雙向匹配過后圖像中仍含有錯誤匹配點，需要進一步剔除。

2.2? 改進的RANSAC算法優(yōu)化處理

2.2.1? RANSAC算法

通過RANSAC算法過濾誤匹配，首先要求出一個最佳單應矩陣，將此矩陣記作H，H矩陣如式（1）所示，大小為3×3。為了找到最佳參數(shù)矩陣，最佳參數(shù)矩陣是指滿足此矩陣的匹配點數(shù)量最多的矩陣，一般設定[h33=1]，目的是使矩陣歸一化。參數(shù)線性方程如下：

[sx′y′1=h11h12h13h21h22h23h31h32h33xy1] （3）

式中：坐標（x，y）表示目標圖像的角點位置;坐標（[x′]，[y′]）表示場景圖像的角點位置;s為尺度參數(shù)。

2.2.2? 基于視差梯度約束的RANSAC算法

引入視差梯度定義[14]，假如在一幅圖像中存在兩個相鄰的角點p，q，這兩個角點分別匹配于另一幅圖像中的角點[p′]，[q′]，如果它們是相匹配的，那么視差梯度[Gd]應該小于或者等于2。如果視差梯度大于2，那么就可以認為這兩個角點不是匹配角點。視差梯度的公式定義為：

[Gd=（p′-p）-（q′-q）（p′-p）+（q′-q）] （4）

式中：坐標[（p′，p）]和坐標[（q′，q）]是對應角點的圖像坐標向量;[m]示向量[m]的模。

綜合以上對視差梯度概念的理解和分析，改進的RANSAC算法流程如下所述：

1） 設定抽樣數(shù)量為M，根據(jù)置信概率公式[P=1-（（1-ε）m）M]，計算出抽樣數(shù)量M。其中[ε]代表數(shù)據(jù)錯誤率，m代表求解模型參數(shù)所需要的最小數(shù)據(jù)量，P指置信概率，一般取P=0.995。

2） 從所有匹配點中隨機抽取匹配點作為一個抽樣，每個抽樣中含有m個數(shù)據(jù)樣本。

3） 根據(jù)視差梯度定義，從所取匹配點中選出兩對匹配點計算其視差梯度，若計算結(jié)果顯示不匹配，則重新選擇抽樣樣本，重新進行步驟2）;若計算結(jié)果顯示匹配，則計算此抽樣的模型參數(shù)。

4） 把該模型參數(shù)代入模型以過濾偽匹配點，通過相同的方法篩選M中其余的抽樣樣本。

5） 比較每組抽樣得到的正確匹配點數(shù)量及誤差方差的大小，選出匹配點質(zhì)量最好的一組，以該組抽樣獲得的模型參數(shù)作為最佳模型參數(shù)，用最佳模型參數(shù)淘汰偽匹配點，得到正確率較高的匹配對，并用這些匹配對計算最終的模型參數(shù)。

3? 實驗結(jié)果分析與對比

本文所有實驗均在Visual Studio 2015_OpenCV 3.0軟件環(huán)境中編譯完成，本實驗所用圖片均為WAT2200雙目攝像頭拍攝，計算機安裝系統(tǒng)為Windows 10，型號為聯(lián)想Idea Pad Y485。為了證明本文提出的算法比原始SURF算法更加精確高效，將SURF算法與本文改進的算法在光照、旋轉(zhuǎn)等不同狀態(tài)下分別做了對比，實驗結(jié)果如圖4所示。

圖4a）和圖4b）是雙目攝像頭采集的左右兩張待匹配圖像，圖5a）、圖5b），圖6a）、圖6b）和圖7a）、圖7b）分別為兩種算法在三種不同狀態(tài)下的匹配結(jié)果圖。為了避免其他外在因素使比較結(jié)果產(chǎn)生誤差，本文選用同一個物體拍攝的兩幅圖像進行不同程度的處理。待匹配圖像為校準圖像，所有匹配結(jié)果圖中橫線表示正確匹配對，斜線表示錯誤匹配對。圖5～圖7中，圖a）為SURF算法匹配結(jié)果圖，圖b）為本文算法匹配結(jié)果圖。

圖5a）、圖5b）是SURF算法和改進算法分別在正常狀態(tài)下圖像匹配的結(jié)果圖，SURF算法匹配結(jié)果中匹配對較多，并且含有大量錯誤匹配對;改進算法的匹配結(jié)果中基本不含錯誤匹配對，或者說沒有肉眼可見的錯誤匹配對，匹配精度高。圖6a）、圖6b）是兩種算法分別在光照條件下對圖像處理的結(jié)果圖（受光照影響，圖片顏色相對較淺），SURF算法受光照影響較小，匹配結(jié)果中仍然含有大量誤匹配;改進算法匹配結(jié)果依然準確，沒有發(fā)現(xiàn)受光照影響，魯棒性強。圖7a）、圖7b）為兩種算法分別在旋轉(zhuǎn)狀態(tài)下對圖像處理的結(jié)果圖，顯而易見，改進算法的匹配結(jié)果沒有受到圖像旋轉(zhuǎn)的影響，幾乎沒有發(fā)現(xiàn)偽匹配對。

從以上3組實驗結(jié)果可知，SURF算法的匹配結(jié)果中匹配對相對較多，含有大量錯誤匹配對，匹配精度低;本文所提出的算法在匹配過程中剔除了較多的錯誤匹配點，匹配成功率高，并且不受旋轉(zhuǎn)和光照因素的影響，魯棒性強，大大提高了圖像的匹配精準度。

在實驗過程中，記錄原始SURF算法和改進算法的運行時間和特征點個數(shù)，具體數(shù)據(jù)如表1和表2所示。表1記錄了兩種算法的正確匹配對數(shù)和錯誤匹配對數(shù)，表2記錄了兩種算法的正確率和運行時間。表1和表2表明，本文提出的算法在精確度方面優(yōu)于原始的SURF算法，提高了圖像的匹配正確率，運算速度并沒有明顯降低，基本和原始SURF算法相持平，因此，改進后的算法能更好地滿足圖像匹配需求。

使用SURF算法和改進算法分別在正常狀態(tài)、光照和旋轉(zhuǎn)條件下進行圖像匹配測試，平均閾值P=0.9，閾值測試如表3所示。

為了進一步驗證本文改進算法的可行性，將本文改進算法與其他改進的SURF算法作比較。采用FAST?SURF[15]算法、SURF?RANSAC算法和本文算法分別進行圖像匹配，三種算法匹配結(jié)果圖如圖8所示。

利用FAST?SURF算法進行圖像匹配時，首先通過FAST角點檢測算法[15]提取特征點，通過非最大值抑制篩選特征點，檢測到的特征點質(zhì)量相對較高，然后通過SURF算法實現(xiàn)圖像匹配，匹配結(jié)果較好。SURF?RANSAC算法在執(zhí)行時首先通過SURF算法完成圖像匹配，然后利用RANSAC算法剔除錯誤匹配對，實驗過程中含有較多特征點，增加了RANSAC算法的采樣次數(shù)，算法耗時稍長，匹配結(jié)果較好。

通過以上三種算法的匹配結(jié)果圖可知，F(xiàn)AST?SURF算法和SURF?RANSAC算法總體匹配結(jié)果較好，含有輕微的錯誤匹配，匹配成功率比本文提出的改進算法低，具體實驗數(shù)據(jù)如表4所示。

圖9為三種算法在光照和旋轉(zhuǎn)變化狀態(tài)下的匹配正確率情況，可以看出三種改進算法在光照和旋轉(zhuǎn)變化狀態(tài)下匹配成功率都具有較強的魯棒性，本文改進的算法匹配成功率高于其他兩種改進算法。

4? 結(jié)? 語

本文實現(xiàn)了一種雙向SURF算法，并結(jié)合改進的基于視差梯度約束的RANSAC算法剔除錯誤匹配對，使用改進的RANSAC算法加快原始RANSAC算法的運行速度，針對SURF算法匹配正確率低的問題做了深入改進。通過實驗仿真與其他改進的SURF算法比較證明了該算法簡單高效，大大提高了SURF算法的匹配精準度，彌補了SURF算法存在的匹配精度低的缺陷，具備一定的實用性。

參考文獻

[1] ZHAO Sizeng， KANG Fei， LI Junjie. Displacement monitoring for slope stability evaluation based on binocular vision systems [J]. Optik， 2018： 171.

[2] Han Lina. Research on image fast retrieval application based on Bayesian network in hybrid space [C]// Proceedings of 2018 International Conference on Big Data and Artificial Intelligence. Beijing： ACM， 2018： 4.

[3] ZAVALA J P， GONZALEZ G， CASTILLO E， et al. Three?dimensional reconstruction of objects obtained by two orthogonal cameras [J]. IEEE Latin America transactions， 2015， 13（9）： 3162?3168.

[4] 鄒浩，林赟，洪文.基于多角度合成SAR圖像的目標識別性能分析[J].中國科學院大學學報，2019（2）：226?234.

[5] 趙杰，徐曉瑩，劉敬，等.變參數(shù)active demons算法下的多通道彌散張量圖像配準[J].中國圖象圖形學報，2019，24（1）：103?114.

[6] LOWE D G. Distinctive image features from scale?invariant key?points [J]. International journal of computer vision， 2004， 60（2）： 91?110.

[7] WANG M， YANG K Y， HUA X S， et al. Towards a relevant and diverse search of social images [J]. IEEE transaction on multimedia， 2010， 12（8）： 829?842.

[8] LOWE D G. Object recognition from local scale ?invariant features [C]// International Conference on Computer Vision. Corfu， Greece： IEEE， 1999： 1150?1157.

[9] ATEFEH Goshvarpour， ATAOLLAH Abbasi， ATEKE Goshvarpour. An accurate emotion recognition system using ECG and GSR signals and matching pursuit method [J]. Biomedical journal， 2018， 40（6）： 355.

[10] BAY H， ESS A， TUYTELAARS T， et al. Speed?up robust features （SURF） [J]. Computer vision and image understanding， 2008， 110（3）： 346?359.

[11] VOURVOULAKIS J， KALOMIROS J， LYGOURAS J. FPGA accelerator for real?time SIFT matching with RANSAC support [J]. Microprocessors & microsystems， 2017， 49： 105?116.

[12] 李穎桃，續(xù)欣瑩，謝珺，等.一種基于鄰域粗糙集特征選擇的圖像分類方法[J].現(xiàn)代電子技術，2019，42（8）：97?101.

[13] XU Wei， ZHANG Maojun， XIONG Zhihui， et al. Feature point matching based on bidirectional maximal correlation and parallactic restriction [J]. Computer engineering and applications， 2008， 44（28）： 155?157.

[14] 張杰，張末含，李述特，等.基于圖像處理的橡膠樹割痕提取與死皮識別[J].計算機應用與軟件，2019，36（1）：259?262.

[15] 陳智翔，吳黎明，高世平.基于FAST?SURF算法的移動增強現(xiàn)實跟蹤技術[J].計算機與現(xiàn)代化，2013（9）：105?108.