基于改進SIFT的圖像特征匹配算法

譚光興 張倫

摘 要：鑒于傳統尺度不變特征變換（scale invariant feature transform，SIFT）算法特征描述子維度過高、匹配時間長和誤匹配率較高的問題，提出一種改進SIFT的圖像特征匹配算法。首先，將SIFT特征點鄰域的方形區域改為十字形分區來簡化特征描述子，降低描述子的維度，減少匹配計算量;然后，在由歐式距離獲取初始匹配點對的基礎上，結合余弦相似度約束條件過濾偽匹配;最后，利用漸進一致采樣（progress sample consensus，PROSAC）算法進一步優化匹配結果，實現精準匹配。實驗結果表明，該算法在模糊、光照、仿射、尺度旋轉等變化條件下均顯著提高了正確匹配率，并縮短了匹配耗時，有效提升了在復雜場景下的匹配性能。

關鍵詞：尺度不變特征變換;特征描述子;歐氏距離;余弦相似度;漸進一致采樣

中圖分類號：TP391.41? ? ? ? ? ? DOI：10.16375/j.cnki.cn45-1395/t.2022.02.006

0? ? 引言

圖像匹配是圖像處理技術中的一項重要內容，是將兩幅或多幅圖像的某種性質進行對比，并通過一定的規則識別出圖像之間的相似部分。圖像匹配已被廣泛應用于圖像拼接[1]、同步定位與建圖（視覺SLAM，simultaneous localization and mapping）[2]和對象識別[3]等諸多領域。目前圖像匹配的方法主要分為兩大類：基于灰度的匹配方法和基于特征的匹配方法[4]。其中，利用圖像灰度進行匹配的方法操作簡單，匹配率較高，但計算量太大，匹配耗時較長，且對光照變化比較敏感。而利用圖像的特征信息進行匹配的方法以其速度較快、精度高和魯棒性好等特點成為近年來圖像匹配技術研究的熱點。

基于特征匹配的算法中，最具有代表性的是由Lowe[5]在2004年提出的傳統尺度不變特征變換（scale invariant feature transform，SIFT）算法。該算法不僅提取特征能力強，對圖像的旋轉、尺度變化、光照變化和噪聲等也具備較高的穩定性，但仍存在一些缺陷：特征描述子維數太大，導致計算復雜度高，時間成本大，對實時性的應用具有局限性。針對SIFT算法的不足，國內外許多學者做了相關改進。文獻[6]通過主成分分析法（principal component analysis，PCA）有效降低了SIFT算法的描述子維數，縮短了匹配時長，但會導致匹配率下降。文獻[7]提出了加速穩健特征（speeded up robust features，SURF）算法，該算法通過積分圖技術能夠快速檢測關鍵點和獲取描述子，運算速度明顯提升;不過，該算法在尺度旋轉變化下的匹配性能不如SIFT。文獻[8]提出的基于余弦距離匹配規則的SIFT特征匹配方法，提高了匹配精度，卻降低了速度。文獻[9]提出的Harris角點提取和SIFT特征描述相結合的匹配算法，刪除了冗余的特征點，提高了正確匹配率，但檢測特征點失去了尺度不變特征，導致該方法無法適用于尺度縮放太大的圖像。文獻[10]將SIFT算法特征點描述子的矩形改為圓形，提高了匹配精度與速度，但實時性有待 提高。

本文在SIFT算法的基礎上，通過建立十字形分區的特征描述子，將描述子的維數從128降低至64，減少匹配時的計算量，縮短匹配耗時。為提高匹配精度，在由歐式距離比值法得出的初始匹配點對上，使用特征向量之間的余弦相似閾值有效去除不可靠、不理想的匹配點，最后采用漸進一致采樣（progress sample consensus，PROSAC）算法進一步提純。

1? ? SIFT算法基本原理

1.1? ?極值點檢測

建立圖像尺度空間是檢測極值點的首要任務，一幅二維圖像的尺度空間[L（x， y， σ）]可由一個變化尺度的高斯函數[G（x， y， σ）]與原圖像[I（x， y）]卷積而來，如下所示：

[L（x， y， σ）=G（x， y， σ）?I（x， y）]? ?，? ? ? ? ? ? ?（1）

[G（x， y， σ）=12πσ2e-x2+y22σ2]? ，? ? ? ? ? ? ? ? （2）

式中：[（x， y）]為像素坐標，[σ]為尺度空間因子。

為了檢測穩定的關鍵點，需構建高斯差分金字塔[D（x， y， σ）]，其實質是2個相鄰尺度圖像的差，計算公式為：

[D（x， y， σ）=L（x， y， kσ）-L（x， y， σ）]? ，? ? ? ? ? （3）

式中：[k]為相鄰尺度因子的比值。

在高斯差分金字塔上，將每個像素點與上層、下層及同尺度層的鄰域共26個點進行比較，由此確保能夠檢測到支持尺度不變性的極值點。

1.2? ?關鍵點精準定位

尺度空間的各層之間并不連續，即上一步得到的極值點并不能代表關鍵點的真實尺度和位置。為了得到更準確的關鍵點，需要利用高斯差分金字塔函數在尺度空間的泰勒級數展開式進行插值查找，同時去除對比度低的關鍵點，展開式如式（4）所示：

[DX=D+?DT?XX+12XT?2D?X2X] ，? ? ? ? ?（4）

其中：[X=（x， y， σ）T]。由于提取關鍵點的過程會產生邊緣響應，根據邊緣響應點具有較大的主曲率比的特性，可借助主曲率比閾值過濾掉邊緣響應點。

1.3? ?關鍵點方向分配

經過1.1、1.2兩個步驟后，此時關鍵點還不具備方向。利用關鍵點鄰域像素的梯度方向特性，為每個關鍵點指定方向參數，使特征描述子具有旋轉不變性。對于窗口內每一個采樣點[L（x， y）]，其梯度值[m（x， y）]與方向[θ（x， y）]的計算公式為：

[m（x， y）=]

[（L（x+1， y）-L（x-1， y））2+（L（x， y+1）-L（x， y-1））2]，? ? ? ? ? （5）

[θ（x， y）=arctan[L（x， y+1）-L（x， y-1）L（x+1， y）-L（x-1， y）]].? （6）

用直方圖統計關鍵點一定鄰域內的梯度方向，而直方圖最高峰所對應的方向則作為關鍵點的主 方向。

1.4? ?特征描述子的生成

SIFT算法通過生成描述子向量來描述特征點，并用于后續的匹配環節。特征描述子的生成如圖1所示，首先，以特征點為中心選取周圍16×16網格的方形像素區域;其次，將4×4網格劃分為一個子區域;最后，在每個子區域計算得到8個方向（每45°取一個方向）的梯度累加值，則每個特征點均可生成4×4×8=128維的特征描述子。

1.5? ?特征點匹配

一旦獲取了特征點描述子，便能利用它們實現特征數據的對比，從而辨別特征點之間是否具有相似性。

一般可通過歐式距離進行判斷，特征點之間的距離越小，表示它們越相似。歐式距離的定義? ? ?式為：

[d（x， y）=||M， N||=i=1n（Mi-Ni）2].? ? ? ?（7）

SIFT算法利用描述子向量計算出參考特征點與所有待匹配特征點的歐氏距離，采用最近鄰比值法進行匹配：若最近鄰與次近鄰的距離比值小于設定閾值T，則特征點與最近鄰點相匹配。T的選取會影響初始匹配的效果，T太大，會存在較多的匹配數，但是誤匹配數也會相應增多;T過小，匹配效果會變好，而匹配數會減少。閾值T的選取范圍一般為0.4～0.8。

2? ? SIFT算法的改進

2.1? ?簡化特征描述子

原SIFT算法具有128維，是高維度的特征描述子且包含了冗余數據，導致其形成花費時間長，計算成本大，匹配計算復雜度高，因此，本文對描述子進行簡化，提高匹配效率。

簡化后描述子的具體劃分如圖2所示。與SIFT算法劃分的方形區域相比，首先，舍去了4個角落的4×4網格像素，主要依據是距離特征點越遠的像素對描述子的貢獻越小，在匹配環節中發揮的作用就越小，而整個描述子數據的權重分布又類似為高斯核，由此舍去了對特征描述子貢獻較低、影響匹配效果較小的部分像素信息。其次，將特征點周圍8×8的網格像素鄰域劃分成4個三角子區域[4]，并與SIFT算法保持一致，在每個三角子區域統計8個方向上的梯度累加值，得到4×8=32維的特征描述子。然后，將三角子區域的上下2個4×8的網格像素、左右2個8×4的網格像素共劃分為4個矩形子區域，同理統計每個矩形子區域內8個方向上的梯度累加值，得到4×8=32維的特征描述子。由于2種區域劃分的大小不同，形狀與方向也有差異，需要均衡這2種描述子的梯度值。同時為了滿足距離特征點越近作用越大的原則，需對這2種區域描述子的梯度值進行加權計算。最后，將這2種描述子進行拼接，獲得一個32+32=64維的特征描述子，可將原SIFT算法的描述子維數減少50%，節省了特征點描述的花費時長，有效降低了算法的計算復雜度與計算量，雖然丟棄了少量的特征信息，但提高了描述子的獨特性，使得同名特征點的匹配更加穩定。

若[R=（r1， r2， …， r64）]是某一特征點64維的特征描述子，為去除光照變化的影響，需要將其按式（8）進行歸一化處理：

[R=Ri=164r2i=（r1， r2， …， r64）].? ? ? ? ? （8）

再將歸一化后特征描述子中的最大值移至向量的第一個位置，可進一步確保旋轉不變性。具體操作為：通過循環左移整個向量元素的方式進行驗證，直到最大值處在當前向量的第一個位置。例如向量中的最大值為[r11]，則最終形成的特征描述子向量為[R=（r11， r12， …， r64， r1， …， r10）]。

2.2? ?余弦相似度過濾

SIFT算法通過單一的歐式距離匹配規則會存在大量的偽匹配點，導致較高的誤匹配率。這主要是因為歐氏距離只在向量的數值特征上體現出不同，因此，當圖像特征相似的區域較多時，多個特征向量之間的距離是近似相等的，此時因向量分量之間的相關性被忽視，體現單一特征的多個分量會干擾匹配結果，從而影響到匹配的精度。

衡量向量之間的相似性除了距離測度法還有相似性函數法[11]。向量間的余弦相似度就是常見的相似性函數，它在方向特征上體現出了向量之間的差異，若向量間的余弦相似度越大，表明這對向量在方向上就越接近。其余弦相似度[S（x， y）]表達式為：

[S（x， y）=x?y||x||×||y||=i=1nxiyii=1nx2ii=1ny2i].? ? ? ? ?（9）

為此，本文通過添加余弦相似度約束條件來減少偽匹配點對數。具體方法是：在特征點之間的歐式距離比值小于T的基礎上，再驗證特征向量之間的余弦相似度是否大于某一閾值，若大于某一閾值才能認定為匹配成功。為滿足誤匹配率較低而匹配點對數盡量多的要求，根據文獻[12]的建議，本文余弦相似度經驗閾值設定為0.93。

2.3? ?PROSAC算法提純

雖然通過余弦相似度約束條件對歐氏距離粗匹配的結果進行過濾后，改善了匹配效果，卻依然存在精度不夠的匹配點對，需采取相應算法進一步提純。目前常用的提純算法是隨機抽樣一致（random sample consensus，RANSAC）算法[13]，該算法的基本原理是：在匹配點對數據集的基礎上，不斷抽取數據并計算出模型參數，通過多次迭代，獲取一個最適合匹配點對集的估計模型。但RANSAC算法每次從整個數據集中隨機采樣的質量高低不等，導致得到模型的參數達不到最佳效果，同時計算時間與樣本量的平方成正比，不適合對大規模的數據集進行計算。而PROSAC算法[14]是對數據集按質量高低排序后再進行采樣，然后估計模型參數，與RANSAC算法相比，減少了迭代次數，使模型最佳參數較早出現，提升了效率。因此，本文采用PROSAC算法對余弦相似度閾值過濾后的匹配結果進一步優化，實現的步驟為：

Step 1? 將過濾后的匹配點對按照距離進行升序排序。

Step 2? 選取前n個樣本數據，并隨機刪除m個，估計出模型參數。

Step 3? 利用該模型對所有的匹配點對計算出誤差，誤差小于閾值的匹配點對視為內點，同時記錄內點的數目;反之則視為外點并剔除。

Step 4? 重復Step 2、Step 3，繼續迭代，直到滿足終止條件時，輸出模型與匹配結果。

算法終止條件為：

1）內點數目大于閾值或者已至最大迭代次數。

2）K次取樣后，內點數并沒有明顯變化，或者模型對匹配點計算出的誤差之和沒有變小。

3? ? 實驗結果與分析

3.1? ?測試圖像與實驗環境

為驗證本文算法的匹配性能并使實驗結果更具有說服力，實驗測試圖像選自牛津大學機器人實驗室標準數據集中的4組圖像，如圖3所示，包括了發生模糊變化、光照變化、仿射變化和尺度旋轉變化的圖像，其中各圖像的分辨率均調整為800×640。實驗的硬件平臺為Intel（R） Core（TM） i5-9400F CPU，頻率為2.9 GHz，內存為8 G。編程平臺為PyCharm2019，算法使用Python代碼在操作系統為64位的Windows10環境下實現。

3.2? ?匹配結果對比

將本文算法與SIFT算法在圖像模糊、光照、仿射以及尺度旋轉變化下分別進行了4組實驗。2種算法在4組測試圖像上的匹配效果對比如圖4所示，表1為2種算法的匹配結果對比。

對比2種算法的匹配效果可以看出，本文算法對于4組不同變化的圖像均能夠進行準確的匹配，并且匹配效果較SIFT算法更好，剔除了一些不理想的匹配點對。可見本文采用十字形分區取代SIFT特征描述子的矩形區域，使其特征描述能力更強;在歐氏距離粗匹配的基礎上，通過余弦相似度閾值有效去除了在匹配集中的偽匹配;最后利用PROSAC算法對過濾后的匹配效果再次進行優化。

根據表1的數據可知，相比SIFT算法，本文算法減少了匹配總數，誤匹配數也明顯減少，主要是由于建立十字形分區描述子的同時引入余弦相似匹配規則，增強了匹配的抗干擾能力，限制了不可靠特征點之間的匹配能力。實驗結果表明，本文算法針對圖像的模糊、光照變化、仿射變換和尺度旋轉等復雜變化均具有較強的適應能力，充分反映了對于復雜場景下的圖像，本文提出的算法依然能夠實現精準匹配。

3.3? ?匹配性能對比

將正確匹配率與匹配時間視為衡量算法匹配性能優劣的標準。本文算法和SIFT算法的匹配性能對比如圖5所示，橫坐標均為4組測試圖像，正確匹配率=（匹配總數-誤匹配數）/匹配總數×100%。

如圖5（a）所示，本文算法對4組不同變化的測試圖像均能夠得到明顯高于SIFT算法的正確匹配率，表明本文算法提高了在圖像復雜變化下的穩定性。這說明對特征描述子的改進有效增強了對特征點描述的獨特性，提高了待匹配中相同特征點的描述子相似性程度。之后又增加了余弦相似度匹配約束條件，剔除了向量方向差異過大的偽匹配。同時本文算法對4組不同變化的測試圖像均能達到90%以上的正確匹配率，其中對光照和仿射變化的匹配率提高程度較大，這表明對描述子進行歸一化以及考慮到特征向量之間的相關性后，降低了對光照和仿射變化的敏感性，從而顯著提高了匹配精度。

如圖5（b）所示，本文算法對4組測試圖像的匹配時間均低于SIFT 算法。這表明本文提出的算法由于改變了描述子的鄰域區域，使得特征向量維數大幅度減少，計算復雜度極大程度降低，有效節省了運算時間，提高了匹配速率;另外由于匹配數相對減少，匹配花費時長也隨之縮短。因此，本文算法不僅顯著提高了匹配精度，還有效縮短了匹配耗時，表明本文算法的匹配性能優于SIFT算法。

4? ? 結語

針對SIFT算法的高維度描述子所帶來的計算量大、匹配速度慢等問題，提出了采用十字形分區取代SIFT特征點鄰域方形描述區域的方法，使得特征向量維度大幅度減少，提升了運算速度，提高了特征描述子的獨特性與匹配效率。根據歐式距離進行初始匹配，隨后引入匹配點應滿足余弦相似的規則來剔除偽匹配，最后利用PROSAC算法進一步提高匹配精度。實驗結果表明，該算法在模糊、光照、仿射和尺度旋轉等變化下均具有較強的適應能力，提高正確匹配率的同時壓縮了匹配時間，有效提升了在復雜場景下的匹配性能。但在如何快速檢測穩定特征點方面還需進一步研究。

參考文獻

[1]? ? ?馬兆敏，吳健玥，胡波，等.田間圖像拼接中重復信息量對拼接效果的影響[J].廣西科技大學學報，2017，

28（3）：83-87，96.

[2]? ? ?陳慶偉，李民東，羅川，等.視覺SLAM中圖像特征點提取與匹配算法研究[J]. 現代制造工程，2019（10）：135-139，134.

[3]? ? ?薛圣利，蔡啟仲，楊海林，等.基于OpenCV的火車票識別算法[J].廣西科技大學學報，2016，27（2）：46-51.

[4]? ? ?馮文斌，劉寶華.改進的SIFT算法圖像匹配研究[J].計算機工程與應用，2018，54（3）：200-205，232.

[5]? ? ?LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[6]? ? ?KE Y，SUKTHANKAR R.PCA-SIFT：a more distinctive representation for local image descriptors[C]//Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington DC：IEEE，2004：506-513.

[7]? ? ?BAY H，ESS A，TUYTELAARS T，et al.Speeded-up robust features（SURF）[J].Computer Vision and Image Understanding，2008，110（3）：346-359.

[8]? ? ?許鋼，林園勝，江娟娟，等.改進型SIFT立體匹配算法研究[J].計算機工程與應用，2015，51（6）：134-138.

[9]? ? ?尚明姝，王克朝.一種改進的Harris與SIFT算子結合的圖像配準算法[J].微電子學與計算機，2018，35（6）：132-134，140.

[10]? ?程德強，李騰騰，郭昕，等.改進的SIFT鄰域投票圖像匹配算法[J].計算機工程與設計，2020，41（1）：162-168.

[11]? ?張宇，劉雨東，計釗.向量相似度測度方法[J].聲學技術，2009，28（4）：532-536.

[12]? ?白廷柱，侯喜報.基于SIFT算子的圖像匹配算法研究[J].北京理工大學學報，2013，33（6）：622-627.

[13]? ?FISCHLER M A，BOLLES R C.Random sample consensus：a paradigm for model fitting with applications to image analysis and automated cartography[J].Communication of the ACM，1981，24（6）：381-395.

[14] CHUM O，MATAS J.Matching with PROSAC-progressive sample consensus[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition（ICCV）.Beijing：IEEE，2005：220-226.

Image feature matching algorithm based on improved SIFT

TAN Guangxing，ZHANG Lun

（School of Electrical， Electronic and Computer Science， Guangxi University of Science and Technology，

Liuzhou 545616， China）

Abstract： An improved SIFT （Scale Invariant Feature Transform） image feature matching algorithm is proposed aiming at the high dimensionality of feature descriptor， long matching time， and high? ? ? ? ?mismatching rate. Firstly， the square area of the SIFT feature points neighborhood is changed into? cross-shaped partition to reduce the dimensionality of the descriptor and amount of matching? ? ? ? ? ? ?calculation. Then， Euclidean distance is used to obtain the initial matching， and filter out mismatch by adding the constraint condition of cosine similarity. Finally， progress sample consensus （PROSAC） is used for further purification and accurate matching. Experimental results show that the algorithm not only improves the correct matching rate significantly， but also shortens the matching time under changes of blur， illumination， affine， scale rotation， and effectively improves the matching performance in complex scenes.

Key words： scale invariant feature transform; feature descriptor; Euclidean distance; cosine similarity; progress sample consensus

（責任編輯：黎? ?婭）