程德強，李騰騰+，郭 昕，白春夢，徐 輝

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

0 引 言

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

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

1 SIFT算法原理

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

1.1 尺度空間極值點檢測

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

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

(1)

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

(2)

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

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

(3)

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

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

1.2 特征點定位

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

(4)

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

1.3 特征點方向分配及特征描述符的生成

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

(5)

(6)

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

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

1.4 特征匹配

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

2 本文算法

2.1 算法流程

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

圖1 算法流程

2.2 圖像去噪和極值點檢測

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

2.3 Sobel算子計算梯度

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

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

(7)

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

(8)

(9)

2.4 改進的特征描述符

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

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

圖2 方形區(qū)域

圖3 圓形區(qū)域

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

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

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

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

圖4 描述符的生成

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

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

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

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

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

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

(10)

Δθ=θi-θj

(11)

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

(4)將(3)中得到的任意兩個初始匹配點的距離值和主方向夾角差值按行向量分別進行歸一化處理，并計算參考圖像和待配準圖像每對匹配點的距離內(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) 分別表示參考圖像和待配準圖像的對應匹配點的像素坐標和主方向。

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

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

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

圖5 測試圖像

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

3.1 實驗結(jié)果

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

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

3.2 實驗分析

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

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

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

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

圖8 匹配時間對比結(jié)果

4 結(jié)束語

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