基于二維熵的快速SIFT圖像匹配方法

馬海波， 張鵬程， 張 權(quán)， 楊冠儒， 王 娜， 桂志國

(1. 中北大學(xué) 生物醫(yī)學(xué)成像與影像大數(shù)據(jù)山西省重點實驗室， 山西 太原 030051； 2. 北京工業(yè)大學(xué) 信息與通信工程學(xué)院， 北京 100124)

0 引 言

圖像匹配作為數(shù)字圖像處理領(lǐng)域的主要內(nèi)容， 已被廣泛應(yīng)用于目標(biāo)跟蹤、 模式識別、 醫(yī)學(xué)智能診斷、 影像分析等諸多領(lǐng)域中[1]. 圖像匹配是指對一幅給定的圖像(參考圖像)的結(jié)構(gòu)、 灰度、 特征等進(jìn)行相似性和一致性分析， 在另一幅圖像(待匹配圖像)中尋找與之有相同特征信息的部分. 目前， 圖像匹配方法分為兩種： 一種是基于圖像灰度的匹配方法， 另一種是基于圖像特征的匹配方法. 而基于圖像特征信息的匹配更加穩(wěn)定， 所以基于特征點的匹配已成為近年來研究的熱點[2-4].

1999年， Lowe提出了一種基于尺度不變特征變換的匹配算法， 即SIFT算法， 并在2004年對該算法進(jìn)行了改進(jìn). SIFT算法不受圖像旋轉(zhuǎn)、 圖像縮放、 亮度變化的影響， 而且具有對視角變化、 仿射變化、 噪聲干擾也保持一定程度的穩(wěn)定性等優(yōu)點， 但存在匹配時間太長的問題[5-6]. 為了減少SIFT算法匹配時間， 大量學(xué)者做出相關(guān)研究并從不同角度提出了有效的改進(jìn)方法. Herbert Bay等[7]提出了SURF算法， 將傳統(tǒng)SIFT算法描述子的維度由128維降低到64維， 加快了圖像的匹配速度. Ke Y等[8]提出了PCA-SIFT算法， 通過對特征描述子降維， 從而提高特征匹配速度. 劉輝等[9]提出了結(jié)合Canny算子， 剔除影響匹配的偽特征點以減少計算量， 從而提高匹配速度. 張永等[10]提出了一種基于內(nèi)核投影的改進(jìn)SIFT算法， 使特征描述子維數(shù)降低， 從而降低匹配時間. 林強[11]結(jié)合Harris角點檢測的方法篩選特征點， 在速度上要快于傳統(tǒng)SIFT算法. 張鑫等[12]提出了在特征點匹配時引入粒子群算法尋找極值， 可以加快匹配速度.

本文提出的算法主要在特征點提取與特征點匹配階段進(jìn)行改進(jìn)， 采用結(jié)合圖像二維熵[13-15]的方法加快匹配速度. 在特征點提取階段計算特征點位置的二維熵， 剔除二維熵較大的特征點， 獲得穩(wěn)定的特征點. 在特征點匹配階段， 計算參考圖像中特征點與待匹配圖像中特征點的二維熵差值， 若該值較小， 則這兩點匹配； 若該值較大， 則這兩點不匹配， 忽略該待匹配特征點， 繼續(xù)在待匹配圖像中尋找匹配的特征點， 這樣可以減少匹配過程中歐氏距離的計算量. 相對于傳統(tǒng)SIFT算法， 本文算法在匹配速度上有一定的提升.

1 SIFT算法

1.1 特征點提取

1.1.1 尺度空間極值檢測

Lindeberg[16]通過實驗證明高斯卷積核是尺度變化的唯一線性核. 尺度空間可表示為圖像I(x,y)與高斯核函數(shù)G(x,y,σ)的卷積

L(x,y,σ)=G(x,y,σ)?I(x,y),

(1)

式中： ?表示卷積運算，σ為尺度空間因子. 高斯核函數(shù)的定義表達(dá)式為

(2)

為了使得到的特征點更有效， 可以采用差分高斯金字塔DoG， 它是通過高斯金字塔中相鄰尺度空間函數(shù)相減得到， 即

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))×

I(x,y)=L(x,y,kσ)-L(x,y,σ).

(3)

1.1.2 關(guān)鍵點定位

利用DoG函數(shù)的二階泰勒展開式對局部極值進(jìn)行擬合， 從而精確定位出特征點的位置與尺度， DoG的泰勒展開式為

(4)

1.1.3 關(guān)鍵點主方向計算

為了保證圖像的旋轉(zhuǎn)不變性， 需要為每個特征點指定一個方向. 特征點鄰域像素梯度模值和方向計算表達(dá)式如下

(5)

式中：L為特征點的尺度， (x,y)表示特征點像素的具體位置. 將梯度方向直方圖的峰值方向定義為該特征點的方向.

1.1.4 關(guān)鍵點描述子構(gòu)造

以特征點為中心， 把它的鄰域范圍分成4×4的小區(qū)域， 共包含16個種子點， 每個種子點有8個方向的梯度信息， 將最終形成的128維描述子稱為SIFT描述子.

1.2 特征點匹配

在待匹配圖像中查找與參考圖像每個特征點最近鄰的兩個特征點， 如果最近的距離除以次近的距離小于某個固定的閾值， 則選取最近距離的這一對匹配點作為匹配對.

2 改進(jìn)的SIFT算法

傳統(tǒng)的SIFT算法構(gòu)造了128維特征描述子， 這在特征點匹配階段采用歐氏距離計算最近鄰和次近鄰距離時的計算量很大， 會消耗大量的匹配時間. 本文結(jié)合圖像的二維熵加快圖像的匹配速度.

2.1 算法原理

圖像的二維熵能夠突出反應(yīng)利用SIFT算法提取出來的特征點位置的灰度信息與其鄰域像素平均灰度的分布關(guān)系. 像素點二維熵越大， 則說明該點包含的內(nèi)容越多， 紋理信息越豐富. 在特征點提取階段， 關(guān)鍵是要提取出適量而穩(wěn)定的特征點， 如果特征點數(shù)量太多， 在匹配階段會消耗大量時間， 如果數(shù)量太少， 對匹配效果也會產(chǎn)生影響. 根據(jù)圖像二維熵與SIFT的基本原理， 二者都與圖像灰度值有緊密聯(lián)系， 由此可以通過控制特征點位置二維熵的閾值有效篩選出穩(wěn)定性高的特征點， 從而為特征點匹配節(jié)省時間. 在特征點匹配階段， 如果參考圖像與待匹配圖像兩個特征點的二維熵差值太大， 則這兩點一定不是正確匹配對. 因此利用圖像二維熵可以實現(xiàn)對偽特征點的剔除以及正確匹配對的尋找.

為了加快圖像的匹配速度， 本文對SIFT算法進(jìn)行改進(jìn). 首先計算利用SIFT算法初步提取出來特征點位置的二維熵大小， 其中圖像的二維熵定義如下

(6)

式中： (i,j)表示圖像中的某一個像素點的灰度值與其鄰域像素點平均灰度值組成的特征二元組， 其中i為某點像素的灰度值，j為其鄰域像素灰度的均值，f(i,j)為二元組(i,j)出現(xiàn)的次數(shù)，N為圖像的尺度.

通過分析SIFT算法尋找特征點與圖像二維熵的原理， 可知二者均與圖像的灰度值有著緊密的聯(lián)系， SIFT算法在提取特征點過程中比較同尺度及相鄰尺度鄰域內(nèi)的灰度值， 而二維熵值的計算是統(tǒng)計某點及其鄰域點像素平均灰度值出現(xiàn)的概率， 二者既緊密相連， 又有所不同， 所以將經(jīng)過SIFT算法提取出來的特征點再用二維熵進(jìn)行篩選會使得特征點更加穩(wěn)定.

如圖 1 所示， 白色圓圈表示1個SIFT特征點， 通過計算該特征點與周圍5×5鄰域像素點的灰度值， 發(fā)現(xiàn)灰度變化較小， 二維熵值為3.72. 圖 2 所示白色圓圈也是1個SIFT特征點， 此特征點位于雪地與公路的交界處， 計算該特征點5×5鄰域像素點的灰度值， 發(fā)現(xiàn)灰度值變化較大， 二維熵值為5.34. 由此可見， 某一特征點的二維熵越大， 特征點與鄰域像素灰度值相差越大， 即攜帶的信息越豐富， 特征點更穩(wěn)定.

圖 1 二維熵較大SIFT特征點圖Fig.1 Two dimensional entropy larger SIFT feature point map

圖 2 二維熵較小SIFT特征點圖Fig.2 Two dimensional entropy smaller SIFT feature point map

通過統(tǒng)計圖像特征點個數(shù)與二維熵值大小關(guān)系， 得到圖 3 所示示意圖， 由圖像可知， 當(dāng)二維熵取值在[4,6]之間時特征點個數(shù)變化緩慢， 即此時特征點最穩(wěn)定.

圖 3 二維熵與SIFT特征點關(guān)系圖Fig.3 Two dimensional entropy and SIFT characteristic point diagram

由圖 3 可知選取合適的二維熵值對剔除不穩(wěn)

定的特征點有重要意義. 如圖 4 所示， 根據(jù)二維熵的定義分別計算參考圖像與待匹配圖像特征點位置二維熵的大小Q， 判斷其與閾值T1和T2的相對大小， 若T1≤Q≤T2， 則保留， 否則為不穩(wěn)定的特征點需要剔除. 通過遍歷計算圖像各像素點二維熵值大小， 得出大部分特征點二維熵取值在4～6 之間， 若取值小于4則難以剔除不穩(wěn)定特征點， 若大于6則得到特征點個數(shù)漸趨于0， 故本文取T1=4，T2=6， 可以有效剔除不穩(wěn)定特征點. 經(jīng)過此步， 可以剔除一部分不穩(wěn)定的特征點， 由于提取出來的特征點數(shù)量減少， 所以必定會為特征點的匹配節(jié)省大量時間.

圖 4 特征點篩選圖Fig.4 Feature point screening diagram

在特征點匹配階段， 位于兩幅圖像重疊區(qū)域中的同一特征點在參考圖像與待匹配圖像中的二維熵大小應(yīng)該相同， 但由于兩幅圖像可能是來自不同時間、 不同光照條件下拍攝得到， 二維熵值會有一定差異， 如果二者相差太大， 則一定不是匹配對. 如圖 5 所示， 在特征點匹配階段首先取參考圖像的特征點pt_A1， 計算其與待匹配圖像某個特征點pt_B1的二維熵之差， 通過計算參考圖像與待匹配圖像對應(yīng)匹配對二維熵之差， 得到差值在0.3左右， 若取閾值大于0.3會使初次得到的匹配點對數(shù)量增多， 加大歐氏距離計算量. 如果二維熵之差大于閾值T3(本文取0.3)， 則認(rèn)為pt_B1一定不是pt_A1的的匹配點， 繼續(xù)在待匹配圖像中查找滿足條件的所有特征點， 將滿足條件的點初步定為一對匹配對.

圖 5 匹配對篩選圖Fig.5 Matching pair filter diagram

假設(shè)待匹配圖像中共有m個特征點{Bi|i=1,2,…,m}， 而經(jīng)過此步找到pt_B3， pt_B8， pt_B10， pt_B12這4個滿足條件的特征點， 則在利用距離比法則尋找正確匹配對時只需計算4次128維的歐氏距離， 而傳統(tǒng)的SIFT算法則需計算L(4

2.2 算法實現(xiàn)步驟

綜上所述， 本文改進(jìn)的算法實現(xiàn)過程如下：

1) 利用式(6)計算參考圖像與待匹配圖像中特征點位置的二維熵大小， 剔除不在閾值范圍內(nèi)的點；

2) 計算參考圖像與待匹配圖像特征點位置二維熵之差， 如果差值太大， 則不是一對匹配對；

3) 利用歐氏距離公式求出參考圖像中的特征點在待匹配圖像中最近鄰和次近鄰距離對應(yīng)的特征點， 如果二者之比小于閾值， 則為一對匹配對.

3 實驗結(jié)果

為了驗證本文算法相對于傳統(tǒng)SIFT算法的優(yōu)越性， 本算法在Intel Corei7-4770 3.40 GHz的CPU， 8GB內(nèi)存的Windows7操作系統(tǒng)上利用Visual Studio結(jié)合OpenCV實現(xiàn).

3.1 特征點提取實驗結(jié)果

圖 6 為傳統(tǒng)SIFT算法提取特征點結(jié)果圖， 圖 7 為改進(jìn)SIFT算法提取特征點結(jié)果圖.

對比圖 6 和圖 7實驗結(jié)果， 可知改進(jìn)后的算法特征點數(shù)目有所減少. 為了更加直觀體現(xiàn)改進(jìn)算法相對于傳統(tǒng)SIFT算法的優(yōu)越性， 對實驗重復(fù)進(jìn)行的5次取其平均值， 實驗得到的數(shù)據(jù)如表 1 所示.

圖 7 改進(jìn)SIFT算法實驗結(jié)果圖Fig.7 Improved SIFT algorithm result diagram

表1 特征點提取兩種算法實驗數(shù)據(jù)對比

由表 1 實驗數(shù)據(jù)可知， 改進(jìn)后的SIFT算法相對于傳統(tǒng)SIFT算法特征點數(shù)目有所減少， 參考圖像中可以剔除掉73個偽特征點， 而待匹配圖像中可以剔除掉82個偽特征點. 在特征點提取所用時間上， 可以分別節(jié)省600 ms和900 ms左右.

3.2 特征點匹配實驗結(jié)果

根據(jù)傳統(tǒng)SIFT特征點匹配原理中提出最近鄰點與次近鄰點的比例閾值為0.8， 針對本實驗， 選最近鄰點與次近鄰點的比例閾值分別為0.6 和 0.65 進(jìn)行實驗， 太大會使誤匹配對增多， 太小使得匹配點對太少直接影響后續(xù)圖像融合的魯棒性. 圖 8 為傳統(tǒng)SIFT算法和改進(jìn)SIFT算法在閾值為0.6時的匹配結(jié)果圖， 圖 9 為傳統(tǒng)SIFT算法和改進(jìn)SIFT算法在比例閾值為0.65時的匹配結(jié)果圖.

對比圖8與圖9可以發(fā)現(xiàn)改進(jìn)的SIFT算法相比傳統(tǒng)SIFT算法誤匹配對數(shù)目減少， 即改進(jìn)算法具有較強的魯棒性. 為了驗證改進(jìn)算法在匹配速度上的優(yōu)勢， 在不同比例閾值下， 重復(fù)進(jìn)行5次實驗取其平均值， 得到匹配所耗時間并統(tǒng)計誤匹配對個數(shù)， 實驗數(shù)據(jù)如表 2 所示.

由表 2 數(shù)據(jù)可知， 當(dāng)最近鄰點與次近鄰點的比例閾值為0.6時， 改進(jìn)算法中誤匹配對減少2對， 匹配速度為傳統(tǒng)SIFT算法的1.6倍. 而當(dāng)閾值為0.65時， 誤匹配對數(shù)目減少3對， 匹配速度為傳統(tǒng)SIFT算法的1.6倍. 由此可見， 隨著比例閾值的不同， 改進(jìn)SIFT算法誤匹配對數(shù)目相對傳統(tǒng)SIFT算法都有所減少， 而且匹配速度為傳統(tǒng)SIFT算法的1.6倍， 體現(xiàn)了本文改進(jìn)算法的優(yōu)越性， 即在保持傳統(tǒng)SIFT算法魯棒性的基礎(chǔ)上， 匹配速度有明顯的提升.

圖 8 閾值為0.6時匹配結(jié)果圖Fig.8 Matching result graph when the threshold is 0.6

圖 9 閾值為0.65時匹配結(jié)果圖Fig.9 Matching result graph when the threshold is 0.65

表2 特征點匹配兩種算法實驗數(shù)據(jù)對比

4 結(jié) 論

本文在傳統(tǒng)SIFT圖像匹配原理基礎(chǔ)上， 提出一種結(jié)合圖像二維熵的SIFT改進(jìn)算法. 實驗結(jié)果表明， 改進(jìn)算法能夠有效剔除不穩(wěn)定的特征點， 同時在特征點的匹配階段可以節(jié)省大量時間. 結(jié)合圖像二維熵的SIFT匹配算法與傳統(tǒng)SIFT算法相比， 具有更好的魯棒性與優(yōu)越性.