改進(jìn)的SIFT鄰域投票圖像匹配算法

程德強(qiáng)，李騰騰+，郭 昕，白春夢(mèng)，徐 輝

(1.中國(guó)礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州 221116；2.內(nèi)蒙古智能煤炭有限責(zé)任公司，內(nèi)蒙古 準(zhǔn)格爾旗 017100)

0 引 言

圖像匹配[2-5]主要分為基于區(qū)域和基于特征的兩類方法[6]。與基于區(qū)域的方法相比，基于特征的方法具有更好的魯棒性，是當(dāng)前圖像匹配的主流方法。在實(shí)際應(yīng)用中，圖像的灰度變化、紋理細(xì)節(jié)和視角變換等都是基于特征匹配方法的不確定因素，導(dǎo)致常見的匹配算法包含大量的誤匹配點(diǎn)，因此匹配精度比較低。經(jīng)典的尺度不變特征變換(scale-invariant feature transform，SIFT)算法[7]對(duì)旋轉(zhuǎn)、透視變換、尺度變換和光照變化等保持不變，然而由于特征描述符維度過高造成計(jì)算復(fù)雜度增加，因此難以滿足實(shí)時(shí)的要求；快速魯棒特征(speed up robust features，SURF)算法[8]改進(jìn)了SIFT算法特征提取和描述的方式，用一種更為高效的方式完成特征的提取和描述，但SURF的實(shí)時(shí)性不高；顏雪軍等[9]提出了一種具有仿射不變性的SIFT描述符，將描述符歸一化為橢圓鄰域；黎劍兵等[10]提出了一種結(jié)合環(huán)狀區(qū)域劃分的特征描述子CLCGH，將鄰域劃分為環(huán)形同時(shí)在局部坐標(biāo)系上統(tǒng)計(jì)梯度方向；Dou等[11]提出了一種基于小波變換和SIFT相結(jié)合的魯棒圖像匹配算法，對(duì)圖像采用離散小波變換提取其低頻部分，然后利用Harris來檢測(cè)感興趣點(diǎn)。

然而，由于受傳感器設(shè)置和相機(jī)位置等因素的影響，圖像間存在較大的幾何差異和灰度變化，從而導(dǎo)致傳統(tǒng)算法匹配精度較低[12-14]，同時(shí)難以滿足實(shí)時(shí)性的要求。為此本文提出一種改進(jìn)SIFT特征描述符和鄰域投票相結(jié)合的算法，從特征描述符的生成和誤匹配點(diǎn)的剔除兩個(gè)方面進(jìn)行改進(jìn)，實(shí)現(xiàn)圖像特征點(diǎn)的精確匹配。實(shí)驗(yàn)結(jié)果表明，本文算法在在顯著提高匹配精確度的同時(shí)縮短了匹配的時(shí)間。

1 SIFT算法原理

SIFT算法的匹配性能較好，能夠?qū)D像的尺度變換、仿射變換、圖像模糊和光照變化保持很好的魯棒性。SIFT算法具體包括以下4個(gè)步驟。

1.1 尺度空間極值點(diǎn)檢測(cè)

為了檢測(cè)圖像尺度空間中穩(wěn)定的極值點(diǎn)，SIFT算法首先使用不同尺度的高斯核對(duì)圖像進(jìn)行卷積實(shí)現(xiàn)了圖像的尺度變換，Lindeberg等證明了高斯核是唯一實(shí)現(xiàn)尺度變換的變換核，并且是唯一的線性核[15]，圖像的尺度空間L(x,y,σ) 可以表示為

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

(1)

其中，(x,y) 表示二維圖像的像素坐標(biāo)，I(x,y) 為輸入圖像，σ為尺度因子，G(x,y,σ) 是尺度可變的高斯函數(shù)，定義如下

(2)

在此基礎(chǔ)上，SIFT通過建立高斯差分(difference of Gaussian，DoG)[16]金字塔來檢測(cè)尺度空間中的極值，兩個(gè)不同尺度高斯核相減得到DoG算子

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))*I(x,y)=
L(x,y,kσ)-L(x,y,σ)

(3)

式中：k為尺度參數(shù)。

在建立高斯差分尺度空間后，將每個(gè)像素點(diǎn)與其同一尺度的8個(gè)點(diǎn)和兩個(gè)相鄰尺度中的18個(gè)對(duì)應(yīng)點(diǎn)進(jìn)行比較，提取具有最大值或最小值的點(diǎn)作為候選特征點(diǎn)。

1.2 特征點(diǎn)定位

由于在DoG金字塔中檢測(cè)到的是離散空間的極值點(diǎn)，而不是真正的極值點(diǎn)，我們必須拒絕對(duì)噪聲敏感或邊緣定位不穩(wěn)定的特征點(diǎn)。SIFT通過曲線擬合，在尺度空間中對(duì)DoG函數(shù)泰勒展開來準(zhǔn)確定位特征點(diǎn)的位置和尺度

(4)

其中，X=(x,y,σ)T，取D(X) 的導(dǎo)數(shù)，并將其設(shè)置為零。

1.3 特征點(diǎn)方向分配及特征描述符的生成

SIFT算法根據(jù)特征點(diǎn)鄰域的梯度分布，為每個(gè)特征點(diǎn)分配主方向，使其生成的特征描述符具有旋轉(zhuǎn)不變性。在特征點(diǎn)所在的尺度空間中，計(jì)算3σ鄰域內(nèi)每個(gè)像素的梯度和方向，任一特征點(diǎn)鄰域內(nèi)像素 (x,y) 的梯度大小m(x,y) 和方向θ(x,y) 定義如下

(5)

(6)

利用在0°-360°范圍內(nèi)取值的梯度直方圖來計(jì)算特征點(diǎn)鄰域像素的梯度和方向，將直方圖的峰值作為特征點(diǎn)的主方向，大于80%峰值的其它區(qū)間作為特征點(diǎn)主方向的輔助方向。通過以上操作，特征點(diǎn)包含了位置、尺度和方向3個(gè)信息。

將坐標(biāo)軸旋轉(zhuǎn)至與特征點(diǎn)的主方向平行，然后選擇以特征點(diǎn)為中心的16*16像素鄰域作為采樣窗口，在每個(gè) 4*4 窗口中計(jì)算8個(gè)方向的梯度方向直方圖，對(duì)每個(gè)梯度方向的累積值進(jìn)行繪制，從而生成具有8個(gè)數(shù)據(jù)的種子點(diǎn)。因此，每個(gè)特征點(diǎn)由4*4個(gè)種子點(diǎn)組成，每個(gè)種子點(diǎn)包含8維的特征向量，最終產(chǎn)生一個(gè)128維的特征描述符。為了減少光照的影響，需要對(duì)128維梯度數(shù)據(jù)進(jìn)行歸一化。

1.4 特征匹配

SIFT將歐式距離作為特征向量的相似性度量，并且若特征點(diǎn)最近鄰距離和次近鄰距之比小于某個(gè)閾值，則判定此特征點(diǎn)與其最近鄰的點(diǎn)正確匹配。最后通過隨機(jī)抽樣一致(random sample consensus，RANSAC)算法[17]剔除誤匹配點(diǎn)，完成特征點(diǎn)的匹配。

2 本文算法

2.1 算法流程

傳統(tǒng)SIFT算法特征描述符維度過高，易出現(xiàn)誤匹配的現(xiàn)象，同時(shí)難以滿足實(shí)時(shí)性的要求，為此本文提出了一種基于改進(jìn)SIFT特征描述符的鄰域投票圖像匹配算法，首先將參考圖像和待配準(zhǔn)圖像作預(yù)處理，分別提取各自的特征點(diǎn)，然后利用Sobel算子進(jìn)行梯度一致性計(jì)算，選擇8個(gè)仿射形式的同心圓鄰域生成64維的特征描述符，采用最近鄰比值法獲得初始匹配點(diǎn)，最后通過鄰域投票方法進(jìn)一步剔除誤匹配點(diǎn)，從而實(shí)現(xiàn)圖像的精確匹配，其流程如圖1所示。

圖1 算法流程

2.2 圖像去噪和極值點(diǎn)檢測(cè)

為減少在特征點(diǎn)檢測(cè)中易受噪聲影響的特征點(diǎn)，本文對(duì)參考圖像和待匹配圖像進(jìn)行均值濾波的預(yù)處理。同時(shí)利用DoG算子建立高斯金字塔，計(jì)算和篩選極值點(diǎn)，但傳統(tǒng)SIFT算法的DoG算子對(duì)灰度特性變化敏感，容易在灰度變化較大的極值點(diǎn)出現(xiàn)誤判。針對(duì)這個(gè)問題，本文采用極值點(diǎn)周圍8個(gè)相鄰像素的平均值代替原始極值點(diǎn)。

2.3 Sobel算子計(jì)算梯度

圖像的紋理細(xì)節(jié)差異、幾何畸變和灰度變化降低了SIFT特征描述符的魯棒性，而特征點(diǎn)鄰域的梯度幅度和方向決定特征描述符的生成。為了使描述符對(duì)圖像的變化有較強(qiáng)的魯棒性，我們?yōu)楦咚钩叨瓤臻g中的每個(gè)像素提出了新的梯度定義(包括幅度和方向)。

Sobel算子是一個(gè)離散微分算子[18]，它結(jié)合了高斯平滑和微分求導(dǎo)，對(duì)噪聲有平滑濾波的作用，同時(shí)受圖像變化的影響小，常常用來計(jì)算圖像的梯度。首先，我們通過Sobel算子計(jì)算高斯尺度空間圖像的梯度幅度

(7)

新的梯度幅度和方向被定義為

(8)

(9)

2.4 改進(jìn)的特征描述符

根據(jù)SIFT算法原理，在計(jì)算特征點(diǎn)的梯度值后，對(duì)每個(gè)特征點(diǎn)，通過直方圖在以特征點(diǎn)為中心的16*16鄰域窗口內(nèi)做梯度分布統(tǒng)計(jì)。鄰域中加入直方圖的每個(gè)特征點(diǎn)都由特征點(diǎn)梯度和高斯權(quán)重加權(quán)，距離特征點(diǎn)越近，對(duì)特征點(diǎn)影響越大。

為保持旋轉(zhuǎn)不變性，SIFT將坐標(biāo)軸旋轉(zhuǎn)至與主方向一致。由于SIFT生成描述符的區(qū)域?yàn)檎叫尉W(wǎng)格結(jié)構(gòu)，旋轉(zhuǎn)待配準(zhǔn)圖像區(qū)域中的像素使其主方向與參考圖像的主方向平行時(shí)，該區(qū)域中的部分像素不重疊，將會(huì)產(chǎn)生較大誤差。在SIFT算法實(shí)際操作中，采用比參考圖像更大的方形區(qū)域來旋轉(zhuǎn)，如圖2所示，但這種做法使得待旋轉(zhuǎn)圖像的像素增加，運(yùn)算時(shí)間也隨之增加。將正方形區(qū)域替換為圓形區(qū)域，即使主方向存在誤差，但旋轉(zhuǎn)后圖像區(qū)域中的像素與之前的像素重疊，如圖3所示。

圖2 方形區(qū)域

圖3 圓形區(qū)域

由于圓形具有旋轉(zhuǎn)不變的特性，因此本文利用圓形鄰域來構(gòu)建特征描述符，如圖4所示。主要步驟如下：

(1)將SIFT算法的16*16特征區(qū)域替換為圓形區(qū)域，統(tǒng)計(jì)鄰域像素的等級(jí)和梯度方向，以確定主方向和輔助方向；

(2)將圓形鄰域區(qū)域劃分成以1個(gè)半徑為單位的8個(gè)同心圓，即生成8個(gè)仿射形式的同心圓鄰域，每一個(gè)像素都是一個(gè)圓，圓的半徑的最大值是8個(gè)像素。8個(gè)環(huán)形區(qū)域中的像素與特征點(diǎn)的距離越遠(yuǎn)，像素的權(quán)重越小，在匹配階段被不同地處理；

(3)利用同心環(huán)梯度積累法表示特征點(diǎn)描述符，對(duì)每個(gè)圓周的8個(gè)方向進(jìn)行梯度累積計(jì)算，最終生成8*8 = 64維特征點(diǎn)描述符。為了減少光照變化的影響，將上述特征描述符分別進(jìn)行歸一化處理。

圖4 描述符的生成

2.5 基于鄰域投票方法的特征匹配

首先采用最近鄰距離比值法得到初始匹配點(diǎn)。灰度分布、圖像細(xì)節(jié)、幾何變換和噪聲干擾等都是圖像匹配的不確定性因素，采用最近距離比值法去除誤匹配的結(jié)果中可能存在大量不能正確匹配的點(diǎn)，需要增加新的約束來進(jìn)一步篩選匹配的點(diǎn)[19]。本文采用鄰域投票的方法剔除誤匹配點(diǎn)最終得到精確的匹配點(diǎn)。

在正確匹配點(diǎn)鄰域存在相似特征點(diǎn)的可能性很大，而在誤匹配點(diǎn)鄰域存在的可能性很小，甚至可能不存在正確的匹配點(diǎn)。鄰域投票方法對(duì)匹配點(diǎn)鄰域在局部主方向和距離上的分布做累積，分別設(shè)定方向閾值和距離閾值，判斷參考圖像和待配準(zhǔn)圖像對(duì)應(yīng)的匹配點(diǎn)的方向相關(guān)度和距離相關(guān)度是否在設(shè)定閾值范圍內(nèi)，若均小于設(shè)定閾值則認(rèn)為該匹配點(diǎn)為正確匹配點(diǎn)，反之則剔除該點(diǎn)。特征匹配具體過程如下：

(1)首先對(duì)參考圖像和待配準(zhǔn)圖像所有特征描述符做內(nèi)積運(yùn)算，求對(duì)應(yīng)反余弦值，對(duì)通過最近距離比值法確定的參考圖像和待配準(zhǔn)圖像的對(duì)應(yīng)匹配點(diǎn)根據(jù)匹配質(zhì)量進(jìn)行排序；

(2)對(duì)匹配點(diǎn)鄰域在局部主方向和距離上的分布做累積，分別設(shè)定方向閾值Tθ和距離閾值Td，經(jīng)過大量實(shí)驗(yàn)驗(yàn)證，當(dāng)Tθ設(shè)為0.3，Td設(shè)為0.4時(shí)，可以得到較多正確的匹配點(diǎn)；

(3)分別計(jì)算參考圖像和待配準(zhǔn)圖像同一圖像上任意兩個(gè)初始匹配點(diǎn)的距離值d和主方向夾角差值Δθ

(10)

Δθ=θi-θj

(11)

式中：i、j為同一幅圖像上任意兩個(gè)初始匹配點(diǎn)，(xi,yi,θi) 和 (xj,yj,θj) 表示i、j兩點(diǎn)的像素坐標(biāo)和主方向。

(4)將(3)中得到的任意兩個(gè)初始匹配點(diǎn)的距離值和主方向夾角差值按行向量分別進(jìn)行歸一化處理，并計(jì)算參考圖像和待配準(zhǔn)圖像每對(duì)匹配點(diǎn)的距離內(nèi)積值dot1和方向夾角內(nèi)積值dot2

dot1=dot(im1(xA,yA),im2(xa,ya))

(12)

dot2=dot(im1(θA),im2(θa))

(13)

式中： (xA,yA,θA) 和 (xa,ya,θa) 分別表示參考圖像和待配準(zhǔn)圖像的對(duì)應(yīng)匹配點(diǎn)的像素坐標(biāo)和主方向。

(5)根據(jù)(2)設(shè)定的參考閾值，比較(4)中匹配點(diǎn)的距離內(nèi)積值和方向夾角內(nèi)積值和參考閾值，若小于參考閾值則保留匹配點(diǎn)，反之則剔除該點(diǎn)。最終完成對(duì)參考圖像和待配準(zhǔn)圖像的精確匹配。

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

為驗(yàn)證本文算法的有效性，本文實(shí)驗(yàn)中的圖像全部來自牛津大學(xué)機(jī)器人實(shí)驗(yàn)室Mikolajczyk和Schmid[20]的數(shù)據(jù)集。這些數(shù)據(jù)集由具有不同幾何和光照變換以及不同場(chǎng)景類型的真實(shí)圖像組成。本文使用5組測(cè)試圖像，圖5(a)為相機(jī)視角發(fā)生了20°變化的Graffiti圖像，圖5(b)為發(fā)生了模糊變化的Bike圖像，圖5(c)為亮度和對(duì)比度發(fā)生了變化的Leurven圖像，圖5(d)為旋轉(zhuǎn)和尺度發(fā)生了變化的Boat圖像，圖5(e)為參考圖像5% 左右的UBC圖像。

圖5 測(cè)試圖像

本文對(duì)實(shí)驗(yàn)數(shù)據(jù)都進(jìn)行了預(yù)處理，所有算法均在Windows10環(huán)境下運(yùn)行，采用CPU為2.8 GHz、內(nèi)存為16 GB的計(jì)算機(jī)配置，編程環(huán)境為Matlab R2016。在本實(shí)驗(yàn)中，特征點(diǎn)最近鄰距離和次近鄰距離之比的閾值均設(shè)為0.7。

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

圖6為本文所提出方法在測(cè)試圖像上的匹配結(jié)果。可見本文方法能夠準(zhǔn)確地將參考圖像與測(cè)試圖像進(jìn)行匹配。本文對(duì)在提取的參考圖像和待配準(zhǔn)圖像的SIFT特征前，使用8個(gè)相鄰像素的平均值代替原始極值點(diǎn)，提高了特征點(diǎn)對(duì)灰度變化的靈敏度，克服了SIFT對(duì)灰度變化的不良影響，而Sobel算子對(duì)梯度的計(jì)算提高了特征的魯棒性，使用8個(gè)仿射形式的同心圓代替SIFT描述符的方形網(wǎng)格結(jié)構(gòu)，使描述符區(qū)分能力更強(qiáng)，增強(qiáng)了描述符的抗旋轉(zhuǎn)能力，同時(shí)降低了描述符的維度，將描述符歸一化，降低了描述符對(duì)仿射變換和光照的敏感性。所以由實(shí)驗(yàn)結(jié)果可以明顯看出，本文算法對(duì)圖像的仿射變換、模糊、光照變化、旋轉(zhuǎn)與縮放和JPEG壓縮都有較強(qiáng)的魯棒性，能較好地克服圖像幾何變換產(chǎn)生的偽匹配點(diǎn)，對(duì)復(fù)雜場(chǎng)景的圖像匹配有好的匹配性能。

圖6 本文算法匹配結(jié)果

3.2 實(shí)驗(yàn)分析

表1是本文所提出的算法、SIFT算法[4]、SIFT RANSAC[21]算法和文獻(xiàn)[22]對(duì)上文的5組測(cè)試圖像的匹配對(duì)比結(jié)果。通過對(duì)匹配算法的性能(正確匹配率和總匹配時(shí)間)進(jìn)行對(duì)比分析，進(jìn)一步驗(yàn)證本文算法的性能。從表1數(shù)據(jù)可以明顯看出：對(duì)于同一測(cè)試圖像，本文算法匹配率最高，匹配時(shí)間最少。由表1可知，對(duì)于測(cè)試圖像5種變換形式下的圖像匹配結(jié)果，本文算法的匹配準(zhǔn)確率明顯高于SIFT、SIFT RANSAC和文獻(xiàn)[22]的算法，匹配正確率均達(dá)到92%以上，穩(wěn)定性高，說明本文算法具有較好的魯棒性和抗干擾能力。本文算法使用8個(gè)仿射形式的同心圓代替SIFT描述符的方形網(wǎng)狀結(jié)構(gòu)，區(qū)分能力更強(qiáng)，可以更好地反映圖像的局部特征，而且增強(qiáng)了描述符的抗旋轉(zhuǎn)能力，把特征描述符的維數(shù)降低到64維，加快了匹配速度。同時(shí)將描述符歸一化，降低了描述符對(duì)仿射變換和光照的敏感性，用鄰域投票的方法剔除不滿足閾值范圍的誤匹配點(diǎn)，從而在正確匹配率大幅提高的同時(shí)增加了匹配速率。

圖7和圖8分別是3種算法的正確匹配率和匹配時(shí)間的對(duì)比結(jié)果，橫坐標(biāo)為圖5測(cè)試圖像的序號(hào)。由折線圖可以看出，本文算法的匹配性能優(yōu)于傳統(tǒng)的SIFT算法、SIFT RANSAC算法和文獻(xiàn)[22]的算法。在匹配精度高的情況下，減少了計(jì)算的復(fù)雜度，匹配速率大幅提高。本文所提出的算法由于改變了描述符的鄰域區(qū)域同時(shí)簡(jiǎn)化了描述符的維度，使得匹配速度大幅提升。由圖6、圖7可以看出，本文算法對(duì)圖像的仿射變換、模糊、光照變化、旋轉(zhuǎn)與縮放和JPG壓縮都有較強(qiáng)的魯棒性，能較好地克服圖像幾何變換產(chǎn)生的偽匹配點(diǎn)對(duì)，對(duì)復(fù)雜場(chǎng)景的圖像匹配有好的匹配性能，算法穩(wěn)定可靠，在增加正確匹配率的同時(shí)提升了匹配速率。

表1 圖像匹配對(duì)比結(jié)果

圖7 正確匹配率對(duì)比結(jié)果

圖8 匹配時(shí)間對(duì)比結(jié)果

4 結(jié)束語

本文提出了一種改進(jìn)SIFT和鄰域投票相結(jié)合的特征匹配方法，從描述符的生成和誤匹配點(diǎn)的剔除兩個(gè)方面進(jìn)行了改進(jìn)。利用8個(gè)相鄰像素的平均值代替原始極值點(diǎn)，Sobel算子進(jìn)行梯度計(jì)算，并結(jié)合8個(gè)仿射形式的同心圓鄰域生成64維描述符，通過最近鄰距離比值法和鄰域投票的方法剔除誤匹配點(diǎn)，完成圖像的精確匹配。實(shí)驗(yàn)結(jié)果表明，本文方法能夠在提高匹配精度的同時(shí)縮減匹配時(shí)間，而且可以有效處理復(fù)雜場(chǎng)景的圖像匹配問題。但是本文算法還有待改進(jìn)之處，對(duì)于特征點(diǎn)提取方面，如何快速有效地提取顯著的特征點(diǎn)，將是我們下一步研究的方向。