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

(1. 中北大學(xué) 生物醫(yī)學(xué)成像與影像大數(shù)據(jù)山西省重點(diǎn)實(shí)驗(yàn)室， 山西 太原 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)定， 所以基于特征點(diǎn)的匹配已成為近年來研究的熱點(diǎn)[2-4].

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

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

1 SIFT算法

1.1 特征點(diǎn)提取

1.1.1 尺度空間極值檢測

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

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

(1)

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

(2)

為了使得到的特征點(diǎn)更有效， 可以采用差分高斯金字塔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)鍵點(diǎn)定位

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

(4)

1.1.3 關(guān)鍵點(diǎn)主方向計(jì)算

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

(5)

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

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

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

1.2 特征點(diǎn)匹配

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

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

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

2.1 算法原理

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

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

(6)

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

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

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

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

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

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

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

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

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

圖 4 特征點(diǎn)篩選圖Fig.4 Feature point screening diagram

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

3.1 特征點(diǎn)提取實(shí)驗(yàn)結(jié)果

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

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

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

表1 特征點(diǎn)提取兩種算法實(shí)驗(yàn)數(shù)據(jù)對比

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

3.2 特征點(diǎn)匹配實(shí)驗(yàn)結(jié)果

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

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

由表 2 數(shù)據(jù)可知， 當(dāng)最近鄰點(diǎn)與次近鄰點(diǎn)的比例閾值為0.6時(shí)， 改進(jìn)算法中誤匹配對減少2對， 匹配速度為傳統(tǒng)SIFT算法的1.6倍. 而當(dāng)閾值為0.65時(shí)， 誤匹配對數(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時(shí)匹配結(jié)果圖Fig.8 Matching result graph when the threshold is 0.6

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

表2 特征點(diǎn)匹配兩種算法實(shí)驗(yàn)數(shù)據(jù)對比

4 結(jié) 論

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