具有局部自適應閾值的SIFT快速圖像匹配算法

汪崟， 蔣崢， 劉斌

（1.武漢科技大學 信息科學與工程學院， 湖北 武漢 430080；2.武漢科技大學 冶金自動化與檢測技術教育部工程研究中心， 湖北 武漢 430080）

1 引言

圖像匹配，也稱圖像配準或響應，旨在從兩個或多個圖像中識別并對應相同或相似的結構、內容［1］。近年來，隨著研究的不斷深入，圖像匹配技術被廣泛應用于位姿估計［2］、醫學圖像配準［3］、3D重建［4］、人臉識別［5-6］等諸多領域。一般情況下，圖像匹配過程會受到尺度、視角、照明等因素的影響［7］。如何快速且準確地對圖像進行匹配已逐漸成為圖像匹配的一個重要研究熱點。

在圖像匹配過程中，特征提取是最重要的一環。傳統圖像特征提取算法能夠解決某些特定場景、可人工定義和設計的圖像任務。由于該方法在特定場景中具有較好的效果、更強的可解釋性和更好的性能，因此仍然具有廣泛的應用價值。文獻［8］提出的具有尺度變換特征不變性的SIFT（Scale Invariant Features）算法屬于經典的傳統算法，被廣泛運用于圖像配準領域［9-10］。傳統SIFT算法具有較好的魯棒性，但是由于其特征描述符是高維的向量，并且利用歐氏距離度量其特征向量之間的相似性，對計算效率和存儲性能有很高要求。為了實現快速且準確的圖像配準，研究人員提出了諸多改進。文獻［11］提出了SURF（Speeded Up Robust Features）算法。該方法利用積分圖像和盒式濾波器構建金字塔，避免了SIFT的降采樣過程，提高了算法的運算速度，但是其對旋轉變化敏感。文獻［12］提出的ORB（Oriented FAST and Rotated BRIEF）算法解決了旋轉不變性問題，但是其特征描述符的區分性弱，匹配效果一般。文獻［13］提出了局部保持匹配方法，通過引入變換向量間的距離比值和角度乘積，構成新的距離損失度量函數進行閾值比較。該方法提高了SIFT算法的匹配精度，但是計算量很大。文獻［14］將幾何代數理論引入傳統SURF框架，計算基于幾何代數理論的Hessian矩陣定位興趣點，并在幾何代數空間中進行描述，有效提升了算法速度。文獻［15］提出的FAST（Features from Accelerated Segment Test）算法大幅降低了運算時間，能夠達到接近實時的運算效率，但是對尺度、旋轉等變化很敏感。為了提高復雜場景中合成孔徑雷達圖像的配準精度，文獻［16］利用FAST算法進行檢測，能檢測到足夠數量且穩定性和重復性好的角點，但是在光照變化明顯的情況下容易造成誤匹配。文獻［17］提出了一種SIFT與Canny邊緣檢測相結合的圖像匹配方法。首先通過SIFT檢測候選關鍵點，然后利用Canny算法去除作為錯誤候選點的邊緣點，最后將快速最近鄰算法應用于高維空間中的匹配點搜索。盡管該算法能夠有效提高圖像特征提取的精度和實時性，但是對于光照復雜、邊緣模糊的場景效果不佳。

針對已有算法在尺度、旋轉以及光照變化方面的諸多問題，為使不同場景下算法同時具備高精度和高速度，本文在SIFT算法的基礎上進行了如下改進：（1）對構建的高斯金字塔進行優化，通過縮減金字塔層數降低耗時的高斯模糊和降采樣次數；（2）在多尺度空間中，提出局部自適應閾值的FAST-SIFT方法在所有尺度上進行特征點檢測，提取出魯棒性更強的特征點；（3）設計了一種新的特征描述符，對原算法中的高維度描述符進行降維，并在特征匹配環節采用RANSAC算法剔除誤匹配。實驗結果表明，本文提出的方法可以縮短特征點檢測的運行時間且在復雜場景下的圖像匹配中具備更高的準確性和魯棒性。

2 SIFT算法

SIFT算法是一種基于圖像尺度空間的局部特征描述子，它在多尺度空間下搜索特征點，通過計算其梯度信息和方向進行描述、匹配的算法。主要步驟如下：

（1） 尺度空間極值檢測。SIFT通過在圖像高斯尺度空間的差異進行局部極值檢測，如圖1所示。

圖1 差分金字塔的構建Fig.1 Construction of a differential pyramid

圖像的尺度空間L(x，y，σ)可定義為原始圖像I(x，y)與一個可變尺度的二維高斯函數G(x，y，σ)進行卷積運算的結果，其數學形式如式（1）所示：

其中：σ表示尺度空間因子，也叫模糊系數，σ值越大圖像越模糊；G是尺度可變高斯函數。

進一步將高斯金字塔中相鄰尺度的高斯圖像做差得到高斯差分金字塔，其數學形式如式（3）所示：

其中：D(x，y，σ)是高斯差分金字塔；k為尺度。

將差分金字塔中的每個像素與其同尺度的8個鄰域點以及上下相鄰尺度各9個鄰域點進行比較，判斷是否為極值點。

（2） 特征點精確定位。通過上述步驟檢測到的極值點是離散空間的極值點，并不是所求特征點，故需要進一步精確定位關鍵點的位置和尺度。

（3） 特征點主方向確定。為了使生成的描述符具備旋轉不變性，通過計算特征點的幅角和幅值的方式來給每個特征點分配一個主方向。對特征點所在的鄰域窗口內，計算每個像素點的幅值m(x，y)和幅角θ(x，y)，公式如式（3）、式（4）所示：

（4） 特征點描述。計算關鍵點鄰域的4×4個子區間內的8個方向上每個方向的梯度累計值，最后生成4×4×8=128維的特征向量。

3 局部自適應閾值的SIFT算法

本文所提出的算法流程圖如圖2所示。本文將從尺度空間構建、關鍵點檢測、特征描述向量生成以及圖像匹配4個方面詳細介紹所提出的算法。

圖2 所提方法流程圖Fig.2 Flowchart of the proposed method

3.1 高斯金字塔層數選擇

SIFT算法尺度空間通過高斯金字塔來實現。在構建高斯金字塔時，需要對原圖像不斷進行下采樣和高斯模糊，金字塔層數過多會導致圖像的特征信息丟失，造成尺度不變性冗余，加大了后續特征點檢測的時間損耗。為了驗證高斯金字塔的尺度冗余性，從UAV Image Mosaicking數據集中隨機采樣3組圖像進行實驗，實驗圖尺寸為512×767。高斯金字塔層數計算公式如式（5）所示：

其中，M和N分別是圖像的行、列數。經計算，采集的圖像集可構建O=6層高斯金字塔，對每一層的特征點檢測與耗時情況進行統計，結果如表1所示。

表1 不同層SIFT匹配結果Tab.1 SIFT matching results for different layers

從表1可知，隨著層數的不斷增高，在第5、6層時，提取到的特征點匹配對占比增量逐漸減小，而時間耗損一直存在。因此，通過縮減SIFT算子的尺度空間，即對高斯金字塔層數減少1～2層，可以顯著縮短特征檢測耗時，同時保證檢測到的特征點不會大量丟失。

3.2 局部自適應閾值的FAST-SIFT特征點檢測

在構建更高效的尺度空間后，需要進行特征點檢測。FAST算法通過以待檢測點為圓心的周圍鄰域內的像素點判斷檢測點是否為角點，判斷依據為一個固定的閾值。然而單一閾值方法在光照變換明顯等復雜環境下很難保證圖像中提取到的特征點的質量和數量，不利于后續算法的處理。

因此，本文提出一種帶有局部自適應閾值的FAST-SIFT特征點檢測方法。該方法通過計算待檢測點鄰域內像素的對比度來定義該區域的閾值，利用自適應閾值的FAST算法在SIFT尺度空間中進行特征檢測，使提取到的特征點不僅具備尺度不變性和方向性，且能夠在光照變化明顯的環境下實現有效的特征點檢測。所提出的局部自適應閾值TA定義為：

其中：Ii是模板內像素的灰度；Ij是模板內以Ii為中心的4鄰域內像素灰度；Δδ=|Ii-Ij|，即模板內某一像素與其4鄰域內像素間的灰度差；Iaver為模板內像素灰度平均值；PΔδ(Ii，Ij)為相鄰像素間灰度差為Δδ的概率分布，則該模板區域對比度計算公式為；α為比例系數，代表閾值TA與圖像局部對比度的關系，經實驗得出α為3～4時，提取出的特征點數量更均衡。

圖3給出了光照明暗差異較大的場景圖，分別采用固定閾值和自適應閾值的FAST算法進行特征點檢測。由結果可知，采用固定閾值提取出的特征點數量較多，產生了特征點冗余、堆積現象，對算法性能影響很大；相比之下，通過局部自適應閾值的方法提取出的特征點分布更均勻，更具有可區分性，對算法運行效率有很大的提升。

圖3 改進FAST對比實驗。（a） 固定閾值（耗時t=4.5 s）；（b） 自適應閾值（α=2.5，耗時t=3.8 s）；（c） 自適應閾值（α=3.5，耗時t=1.6 s）；（d）自適應閾值（α=4.5，耗時t=0.9 s）。Fig.3 Improved FAST comparison experiment. （a） Fixed threshold （time consumption t=4.5 s）； （b） Adaptive threshold （α=2.5，time consuming t=3.8 s）；（c） Adaptive threshold （α=3.5，time consuming t=1.6 s）； （d） Adaptive threshold （α=4.5，time consuming t=0.9 s）.

所提出局部自適應閾值的FAST-SIFT特征點提取詳細步驟如下：

Step 1 在構建尺度空間后，采用局部自適應閾值的FAST算法在每個尺度進行特征點檢測，將檢測到的特征點作為初始特征點；

Step 2 在高斯差分金字塔中，對上一步篩選出的初始特征點與其8鄰域以及上、下尺度的18個點進行極值比較，以確保初始特征點為極大值或極小值；

Step 3 若初始特征點滿足上述條件，則將其認定為最終的特征點，否則，在以該初始特征點為中心的8鄰域范圍內搜索距離中心最近的極值點作為特征點，以此來保證特征點的數量；

Step 4 對提取出的特征點用SIFT描述符進行描述，生成相應特征向量。

3.3 特征向量降維

通過上述方法提取特征點后，需要對特征點所包含信息進行描述。SIFT算法采取特征點鄰域16×16的方形區域生成128維特征描述符，會造成區域誤差，同時高維度的特征向量在進行匹配時，需要的計算量很大，會嚴重影響匹配速度。為解決此問題，考慮圓形具有旋轉不變性，本文采用圓形窗口來生成特征描述符，在充分保留特征信息的同時，無需確定特征點的主方向。描述符設計如圖4所示，主要步驟如下：

圖4 改進的描述符Fig.4 Improved descriptor

Step 1 在特征點周圍20×20的鄰域內，以特征點為中心，取半徑為10的圓形區域。

Step 2 將圓形區域由內至外劃分為4個圓環子區域，由于特征點周圍的像素離特征點越近，對特征點描述符的影響也越大，故每個圓環子區域的步長分別取4，3，2，1。

Step 3 根據式（3）、（4）統計每個圓環區域內像素點8個方向上的梯度直方圖。

Step 4 對于每個圓環區域的像素點，根據計算出的每個像素點的幅角值確定其在8個方向的哪一個區間內，每個區間角度劃分為0°～45°，根據每個像素點所處位置，再利用高斯窗口進行加權處理，將不同像素點幅值進行累加，加權系數計算公式如式（7）所示：

其中：(x，y)和(x0，y0)為所求像素點和中心像素點在待描述區域的坐標位置，σ為所在尺度，s為所求像素點坐標所在圓環位置步長，r為所求像素點坐標所在圓環半徑。通過考慮所求像素點所在區域圓環的步長s與半徑r的比值，描述了該點所在圓環區域相對中心特征點區域的位置，進一步細化不同位置像素點對中心特征點的影響權重。

Step 5 通過上述步驟，最終得到4×8=32維的特征描述符。為了減小由于光照變化對匹配效果的影響，需要采用歸一化對特征向量進行處理，得到最后的特征描述符向量進行匹配。

3.4 特征點匹配

本文通過計算特征向量之間最近絕對值距離與次近絕對值距離的比值作為匹配依據，即遍歷計算出待匹配圖像中每個特征點描述符與參考圖像中所有特征描述符的歐式距離，找到與某一特征點距離最近和次近的特征點。當最近距離值與次近距離值之比小于閾值時，則定義為正確的匹配點對。為了進一步提高匹配準確度并去除誤匹配，本文采用RANSAC算法對特征點進行提純。

4 實驗結果與分析

實驗硬件平臺為Intel Core i5-10500H處理器，2.50 GHz主頻，16 GB內存，RTX 2060顯卡，Windows操作系統。利用Matlab2020a的平臺進行仿真實驗。實驗使用的數據集分別為：

（1） Hpatches數據集［18］。該數據集包含多組亮度變化對比圖和視點變化對比圖，用于測試算法在亮度變化和視點變化情況下的匹配性能。

（2） 牛津大學Mikolajczyk數據集［19］。該數據集包含多組旋轉、尺度變化對比圖，用于測試算法在旋轉、尺度變化情況下的匹配性能。

4.1 描述符降維有效性分析

為了驗證本文設計的降維方法在提升匹配效率的同時能否保證匹配準確率，實驗對比了傳統SIFT算法、PCA-SIFT［20］算法以及傳統SIFT算法結合本文降維法的匹配性能。從Hpatches數據集中選取8組圖像對進行實驗，結果如圖5、圖6所示。

圖5 各算法的執行時間對比Fig.5 Comparison of the execution time of each algorithm

圖6 各算法的特征點匹配準確率Fig.6 Feature point matching accuracy of each algorithm

圖5顯示的是3種算法對圖像進行特征點檢測所需時間的對比?？梢钥闯?，SIFT算法的執行時間最長，PCA-SIFT次之，本文采用圓形窗口進行特征點描述，生成32維特征向量，算法執行時間明顯優于另外兩種算法。

圖6的柱狀圖顯示了3種對比算法對圖像進行特征點匹配后得到的匹配準確率。由圖6可知，SIFT算法的匹配準確率最低，在第5、7組匹配率只有約60%；PCA-SIFT通過主成分分析法在4組數據圖上實現的降維特征描述更具鑒別力，所以表現較好，但該方法通過將特征描述符投影到較低維的子空間降低特征描述符的維數，可能會導致一些原始信息的丟失，所以在剩下幾組數據圖上，本文降維方法表現效果更好。

由圖5、6可知，結合本文降維方法的SIFT算法在執行時間和匹配準確率上均優于傳統的SIFT算法。與PCA-SIFT相比，雖然本文方法只有4組數據在匹配準確率上占優勢，但是在執行時間上均優于PCA-SIFT算法?？傮w上本文所設計的降維方法更具優勢，在提升匹配效率的同時能保證匹配準確率。

4.2 算法性能比較結果分析

為了驗證本文提出的具有局部自適應閾值的SIFT算法的性能，從兩種數據集中選取8組圖像進行實驗，對比SIFT［8］、ORB［12］、GA-SURF［14］、Canny-SIFT［17］以及Pyramid-ORB［21］算法。圖7給出了部分用于測試的圖像，其中一組各算法的匹配結果如圖8所示。進一步統計各類算法的匹配準確率和耗時性，結果如圖9所示。

圖7 部分用于測試的圖像對。 （a） 光照變化； （b） 視點變化； （c） 旋轉、尺度變化。Fig.7 Part of the image pairs used for test. （a） Lighting transformation； （b） Viewpoint transformation；（c） Rotation and scale transformation.

圖8 各算法匹配結果Fig.8 Matching results of each algorithm

圖9 算法匹配性能分析。 （a） 各算法匹配準確率； （b） 各算法執行時間。Fig.9 Algorithm matching performance analysis. （a） Matching accuracy of each algorithm； （b） Execution time of each algorithm.

由圖9可知，在具有光照、視點以及旋轉和尺度變換的圖像匹配中，ORB算法的匹配準確率最低，Pyramid-ORB算法次之，Canny-SIFT算法略優于傳統SIFT算法和GA-SURF算法。本文方法通過自適應閾值FAST算法在多尺度空間下提取更穩定的特征點，對待匹配圖片的旋轉、尺度以及光照變換具有較強魯棒性，在匹配準確率方面效果顯著，優于其他幾種算法。在匹配耗時方面，SIFT算法消耗的時間最多；Canny-SIFT算法通過從候選點中篩選出錯誤的邊緣點，減少了匹配點對，匹配耗時比傳統SIFT少；Pyramid-ORB算法通過構建高斯金字塔來克服旋轉和尺度變化，算法耗時高于ORB算法。本文方法通過采用圓形窗口將SIFT特征描述符降到32維，極大提升了特征點匹配效率，匹配耗時略少于ORB算法，但明顯優于其他4種算法。

4.3 算法穩定性分析

4.3.1 尺度、旋轉不變性對比

為了檢驗本文方法對圖像旋轉和尺度變換時的匹配準確率，從Hpatches數據集中選取待檢測圖，將圖像尺度縮放1.5倍并順時針旋轉30°，如圖10所示。

圖10 用于尺度、旋轉不變性測試的圖像對。Fig.10 Image pairs for scale， rotational invariance test.

表2統計了各算法在圖像發生旋轉、尺度變換情況下的匹配耗時和準確率。從表2可知，在圖像發生旋轉和尺度變換時，本文方法提取到的特征點具有很好的穩定性，依然能保持較高的匹配準確率。為了進一步對本文方法的旋轉性進行驗證，對不同旋轉角度下各算法的匹配情況進行了記錄。由圖11可知，隨著旋轉角度的不斷增大，本文方法依然具有較強的穩健性，算法的匹配準確率保持在91%以上。

表2 圖像旋轉、尺度變換后的比較結果Tab.2 Comparison results after image rotation and scale transformation

圖11 圖像旋轉變換的實驗結果Fig.11 Experiment results of image rotation transformation

4.3.2 亮度變換對比

光照強度變化在實際情況中比較普遍，是影響圖像匹配的重要因素之一。為了驗證本文方法在圖像光照強度變換情況下的匹配性能，進一步通過手動設置實驗圖由暗到亮進行對比實驗，結果如圖12所示，可以看出本文方法對光照變換具有良好的魯棒性，正確匹配率均在93%以上。

圖12 光照強度變換的實驗結果Fig.12 Experimental results of light intensity transformation

5 結論

針對SIFT算法的計算復雜性高、存在誤匹配點的問題，本文在傳統SIFT算法基礎上提出了一種具有局部自適應閾值的SIFT快速圖像匹配算法。在SIFT尺度空間理論基礎上，通過縮減高斯金字塔層數消除算子的尺度不變冗余性能，在保持匹配性能情況下，顯著提高了特征點檢測效率；利用局部自適應閾值的FAST算法與SIFT算法的極值比較相結合提取特征點，并使用圓形窗口描述32維特征向量代替SIFT算法的128維高維向量。與其他幾種算法進行對比，實驗結果表明，本文方法在特征提取速度、準確率方面效果更好。在尺度、旋轉以及光照等變換下提取的特征點具有更好的穩定性，能得到較高的正確匹配率。在旋轉角度較大的情況下，本文方法的正確匹配率較SIFT提高約23%，算法耗時減少了45.7%，能更好地運用于實時場景中。