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

譚光興 張倫

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

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

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

0? ? 引言

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

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

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

1? ? SIFT算法基本原理

1.1? ?極值點檢測

建立圖像尺度空間是檢測極值點的首要任務(wù)，一幅二維圖像的尺度空間[L（x， y， σ）]可由一個變化尺度的高斯函數(shù)[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）]為像素坐標，[σ]為尺度空間因子。

為了檢測穩(wěn)定的關(guān)鍵點，需構(gòu)建高斯差分金字塔[D（x， y， σ）]，其實質(zhì)是2個相鄰尺度圖像的差，計算公式為：

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

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

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

1.2? ?關(guān)鍵點精準定位

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

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

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

1.3? ?關(guān)鍵點方向分配

經(jīng)過1.1、1.2兩個步驟后，此時關(guān)鍵點還不具備方向。利用關(guān)鍵點鄰域像素的梯度方向特性，為每個關(guān)鍵點指定方向參數(shù)，使特征描述子具有旋轉(zhuǎn)不變性。對于窗口內(nèi)每一個采樣點[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）

用直方圖統(tǒng)計關(guān)鍵點一定鄰域內(nèi)的梯度方向，而直方圖最高峰所對應(yīng)的方向則作為關(guān)鍵點的主 方向。

1.4? ?特征描述子的生成

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

1.5? ?特征點匹配

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

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

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

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

2? ? SIFT算法的改進

2.1? ?簡化特征描述子

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

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

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

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

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

2.2? ?余弦相似度過濾

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

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

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

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

2.3? ?PROSAC算法提純

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

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

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

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

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

算法終止條件為：

1）內(nèi)點數(shù)目大于閾值或者已至最大迭代次數(shù)。

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

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

3.1? ?測試圖像與實驗環(huán)境

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

3.2? ?匹配結(jié)果對比

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

對比2種算法的匹配效果可以看出，本文算法對于4組不同變化的圖像均能夠進行準確的匹配，并且匹配效果較SIFT算法更好，剔除了一些不理想的匹配點對?？梢姳疚牟捎檬中畏謪^(qū)取代SIFT特征描述子的矩形區(qū)域，使其特征描述能力更強;在歐氏距離粗匹配的基礎(chǔ)上，通過余弦相似度閾值有效去除了在匹配集中的偽匹配;最后利用PROSAC算法對過濾后的匹配效果再次進行優(yōu)化。

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

3.3? ?匹配性能對比

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

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

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

4? ? 結(jié)語

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

參考文獻

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

28（3）：83-87，96.

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

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

[4]? ? ?馮文斌，劉寶華.改進的SIFT算法圖像匹配研究[J].計算機工程與應(yīng)用，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].計算機工程與應(yīng)用，2015，51（6）：134-138.

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

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

[11]? ?張宇，劉雨東，計釗.向量相似度測度方法[J].聲學技術(shù)，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

（責任編輯：黎? ?婭）