王澤梁， 汪道寅， 汪麗華

(1.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院， 安徽 合肥 230009； 2.中國(guó)科學(xué)技術(shù)大學(xué)電子工程與信息科學(xué)系， 安徽 合肥 230027； 3.黃山學(xué)院信息工程學(xué)院， 安徽黃山 245041)

0 引 言

David Lowe提出的尺度不變特征SIFT算法具有尺度、旋轉(zhuǎn)、仿射和光照等不變性的特征[1].SIFT算法主要可分為3部分：特征檢測(cè)、特征描述和特征匹配.特征檢測(cè)是在圖像上對(duì)特征進(jìn)行提取，特征描述是對(duì)特征進(jìn)行表達(dá)，特征匹配則是對(duì)特征進(jìn)行配對(duì).Mikolajczyk和Schmid通過(guò)對(duì)比SIFT、PCA-SIFT、steerable filter、moment invariants等數(shù)十種特征描述后指出[2，3]，SIFT是目前最為有效的特征檢測(cè)算子.SIFT算法因其優(yōu)異的性能得到了相關(guān)領(lǐng)域?qū)W者的廣泛關(guān)注，陸續(xù)出現(xiàn)了一些變種算法，如Yan Ke在2004年提出的PCA-SIFT算法[4]、Mikolajczyk等在2005年提出的GLOH(Gradient Location Orientation Histogram)算法[3]、Bay在2006年提出的SURF(Speeded Up Robust Features)算法[5]、Guoshen Yu 和Jean在2009年提出的ASIFT算法[6]等.SIFT算法仍存在需要完善的地方，如檢測(cè)到的特征點(diǎn)不具有均勻性分布，檢測(cè)步長(zhǎng)不能進(jìn)行動(dòng)態(tài)調(diào)整等.針對(duì)以上問(wèn)題作者研究并提出了相應(yīng)的均勻性特征檢測(cè)和動(dòng)態(tài)步長(zhǎng)的設(shè)計(jì)方法，實(shí)驗(yàn)表明改進(jìn)算法能夠?qū)崿F(xiàn)更有效的圖像配準(zhǔn).

1 SIFT算子簡(jiǎn)介

1.1 檢測(cè)尺度空間的特征點(diǎn)

高斯卷積核是實(shí)現(xiàn)尺度變換唯一的線(xiàn)性變換核，一幅圖像在尺度空間中的表示為圖像和可變高斯核函數(shù)的卷積，LoG(Laplacian of Gaussian)算子表達(dá)式如下：

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

(1)

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

(2)

其中，因子k滿(mǎn)足k=21/S.將D(x,y,σ)在尺度空間中的極值點(diǎn)作為候選特征點(diǎn).

1.2 精確定位特征點(diǎn)的位置

通過(guò)擬和三維二次函數(shù)以精確確定特征點(diǎn)的位置和尺度，同時(shí)可去除低對(duì)比度的關(guān)鍵點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)，以增強(qiáng)匹配的穩(wěn)定性.差分金字塔DoG的泰勒展開(kāi)式如下：

(3)

其中，X=(x,y,σ)T為包含特征點(diǎn)位置和尺度信息的向量.由差分金字塔DoG的幅值大小及曲率來(lái)剔除低對(duì)比度點(diǎn)和邊緣響應(yīng)點(diǎn).

1.3 確定特征點(diǎn)的主方向

坐標(biāo)為(x,y)的關(guān)鍵點(diǎn)其梯度幅值和方向分別為：

(4)

θ(x,y)=tan-1((L(x,y+1)-L(x,y-1))/(L(x+1,y)-L(x-1,y)))

(5)

在以特征點(diǎn)為中心的鄰域窗口內(nèi)用梯度方向直方圖來(lái)統(tǒng)計(jì)鄰域像素的梯度方向.梯度方向在0°～360°，其中每10°在直方圖中表示一個(gè)柱，共36柱.梯度方向直方圖的峰值代表了該特征點(diǎn)處鄰域梯度的主方向，即作為該特征點(diǎn)的主方向.

1.4 生成特征描述符

以特征點(diǎn)為中心取16×16的窗口(特征點(diǎn)所在的行和列不取)，每個(gè)小格代表特征點(diǎn)鄰域所在尺度空間的一個(gè)像素，采用高斯加權(quán)(越靠近特征點(diǎn)的像素，梯度方向信息貢獻(xiàn)越大).在4×4的圖像小塊上計(jì)算8個(gè)方向的梯度方向直方圖，繪制每個(gè)梯度方向的累加值，形成一個(gè)種子點(diǎn).梯度方向直方圖統(tǒng)計(jì)公式[7]如下：

(6)

其中，ck為方向柱的中心，Δk為方向柱的寬度，(x,y)為子塊r(l,m)像素點(diǎn)的坐標(biāo).

一個(gè)特征點(diǎn)由4×4共16個(gè)種子點(diǎn)組成，特征描述子由所有子塊的梯度方向直方圖構(gòu)成：

u=(hr(1,1),…,hr(l,m),…,hr(4,4))

(7)

因此，最終形成128維的SIFT特征向量即作為SIFT算法的特征描述符.

1.5 特征點(diǎn)之間的匹配

通過(guò)計(jì)算128維的特征描述符之間的Euclid 距離來(lái)度量2 個(gè)特征點(diǎn)之間的匹配程度.當(dāng)2 個(gè)特征描述符的Euclid 距離最小并且與次最小 Euclid 距離的比值小于給定的閾值0.8時(shí)，則這2個(gè)特征點(diǎn)滿(mǎn)足匹配關(guān)系.

圖1 歐氏距離比的概率密度分布

2 距離比閾值參數(shù)的自適應(yīng)方法

歐氏距離比|DA-DB|/|DA-DC|表示最近鄰歐氏距離和次近鄰歐氏距離之間的比值，當(dāng)該比值在一定的閾值t范圍內(nèi)時(shí)則認(rèn)為最近鄰歐氏距離所對(duì)應(yīng)的一對(duì)特征點(diǎn)是匹配特征點(diǎn).

David給出的距離比概率密度分布[1]如圖1所示，其中實(shí)線(xiàn)為正確匹配點(diǎn)的概率密度分布，虛線(xiàn)為錯(cuò)誤匹配點(diǎn)的概率密度分布.由圖1可以看到，David將距離比閾值參數(shù)設(shè)為0.8是合理的，此時(shí)雖然損失了5%的正確匹配點(diǎn)，但同時(shí)將減少90%的錯(cuò)誤匹配點(diǎn).然而圖1并不能反映所有圖像的歐氏距離比概率密度分布，也即這種固定閾值的方法并不是十分合理的方法.在對(duì)不同的圖像進(jìn)行試驗(yàn)時(shí)，閾值并不總能得到最佳效果，因此參數(shù)并不是對(duì)所有圖像均有效.一個(gè)有效的算法應(yīng)當(dāng)使得閾值參數(shù)具有盡可能高的魯棒性，能夠滿(mǎn)足不同情況需要.為此，應(yīng)對(duì)不同的圖像自適應(yīng)調(diào)整閾值，使特征點(diǎn)能夠更準(zhǔn)確地實(shí)現(xiàn)匹配.

圖2 參考圖像和待配準(zhǔn)圖像

圖3 參考圖像和待配準(zhǔn)圖像的特征點(diǎn)分布

圖4 重復(fù)率與距離比閾值迭代過(guò)程

為選擇一個(gè)最優(yōu)的歐氏距離比閾值參數(shù)，需要在算法實(shí)現(xiàn)中加入?yún)?shù)尋優(yōu)的過(guò)程，參數(shù)是否最優(yōu)通過(guò)重復(fù)率進(jìn)行衡量.重復(fù)率越大，表明匹配程度越高，歐氏距離比閾值的選取越合理；重復(fù)率越小，表明匹配程度越低，歐氏距離比閾值的選取越不合理，需要重新進(jìn)行選取.但是重復(fù)率與歐氏距離比閾值之間并不存在明確的函數(shù)關(guān)系式，這給尋優(yōu)過(guò)程帶來(lái)了麻煩.通過(guò)大量實(shí)驗(yàn)表明，歐氏距離比閾值的取值范圍在[0.4,0.8]之間比較合適.閾值取的太大，則表明匹配的要求太寬泛，錯(cuò)誤匹配的點(diǎn)將增多；閾值取的太小，則表明匹配的要求太嚴(yán)格，正確匹配的點(diǎn)將減少.目前已經(jīng)產(chǎn)生了很多的智能優(yōu)化方法，如參數(shù)少、計(jì)算簡(jiǎn)單的粒子群(Particle Swarm Optimization，PSO)算法，還有遺傳算法(Genetic Algorithm，GA)、蟻群算法(Ant Colony Algorithm，ACO)等.考慮到只對(duì)歐氏距離比閾值參數(shù)進(jìn)行尋優(yōu)且已知參數(shù)的優(yōu)化范圍，故不需要引入優(yōu)化方法，可以采用最為基礎(chǔ)的折半查找法進(jìn)行尋優(yōu)即可.具體過(guò)程如下：

(1)設(shè)待優(yōu)化參數(shù)的取值區(qū)間為[a,b]，區(qū)間的中間值為c，初始值a=0.4,b=0.8,c=0.6,l=0.2.計(jì)算a,b,c所對(duì)應(yīng)的重復(fù)率R(a)，R(b),R(c),M=max(R(a),R(b),R(c)).

(2)在c的左右生成兩點(diǎn)d=c-l*rand和e=c+l*rand，計(jì)算d,e所對(duì)應(yīng)的重復(fù)率R(d)和R(e)(其大小必須大于M，否則重新生成d,e)，比較兩者大小.

(3)若R(d)>R(e)，則M=R(e),l=l/2,a不變，b=c,c=c-l,返回步驟(2)；若R(d)

(4)當(dāng)兩次M的差值小于0.01或者達(dá)到最大搜索次數(shù)50時(shí)，算法終止.

上述過(guò)程中，若出現(xiàn)M為1的值，則算法立即終止，不需要再繼續(xù)搜索，對(duì)應(yīng)的距離比閾值作為所求參數(shù).由于匹配運(yùn)算占SIFT算法中的運(yùn)算比例很小，所以以上尋優(yōu)不會(huì)給SIFT算法帶來(lái)太大的運(yùn)算負(fù)擔(dān).

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

3.1 匹配圖像的選取

實(shí)驗(yàn)以典型的Lena圖像為例，圖2(a)以131×131大小的Lena圖像作為參考圖像，圖2(b)為圖2(a)旋轉(zhuǎn)30°后形成的大小為179×179的待配準(zhǔn)圖像.

3.2 特征的檢測(cè)和描述

參考圖像共檢測(cè)到126個(gè)特征點(diǎn)，待配準(zhǔn)圖像共檢測(cè)到162個(gè)特征點(diǎn)，檢測(cè)結(jié)果如圖3所示.對(duì)檢測(cè)到的特征點(diǎn)生成特征描述子時(shí)，描述子的位置和特征點(diǎn)的位置一致.

圖5 距離比閾值與重復(fù)率的關(guān)系曲線(xiàn)

3.3 距離比閾值參數(shù)自適應(yīng)

圖4給出了歐氏距離比閾值參數(shù)的尋優(yōu)過(guò)程.其中，圖4(a)代表重復(fù)率的迭代過(guò)程，圖4(b)代表距離比閾值參數(shù)的迭代過(guò)程.通過(guò)前面的尋優(yōu)算法，距離比閾值參數(shù)和重復(fù)率不斷尋優(yōu)，直到最大重復(fù)率和最優(yōu)距離比閾值.算法共進(jìn)行了13步迭代，重復(fù)率最終取0.981 1，距離比閾值參數(shù)最終取0.464 1.由圖4可以看到，距離比閾值參數(shù)通過(guò)不斷迭代、折半縮小區(qū)間的方法最終得到了所需要的取值.

通過(guò)距離比閾值參數(shù)的尋優(yōu)，得到了該圖像下的最佳距離比閾值參數(shù)，距離比閾值與重復(fù)率的關(guān)系如圖5所示.由于算法利用了折半查找思想，在閾值區(qū)間已知的情況下能夠較快地找到最優(yōu)參數(shù)，因此不會(huì)帶來(lái)大的運(yùn)算量.

距離比閾值參數(shù)對(duì)不同的圖像其值的選取是不同的，并且具有不同的分布，所以應(yīng)該針對(duì)不同的圖像進(jìn)行選擇.距離比閾值參數(shù)有時(shí)的取值并不是某個(gè)特定值，而是在一定區(qū)間取值均可，如上圖所示.

4 結(jié)束語(yǔ)

尺度不變特征SIFT算法因其穩(wěn)定性、獨(dú)特性和多量性等優(yōu)點(diǎn)，對(duì)圖像處理領(lǐng)域發(fā)揮著越來(lái)越重要的作用.本文在SIFT算法的匹配階段對(duì)距離比閾值進(jìn)行自適應(yīng)動(dòng)態(tài)調(diào)整，使其滿(mǎn)足不同圖像的需要.實(shí)驗(yàn)表明，基于折半查找法思想的尋優(yōu)能夠找到最優(yōu)的距離比閾值，同時(shí)不會(huì)產(chǎn)生太大的運(yùn)算量.后續(xù)工作將對(duì)不同類(lèi)型的圖像進(jìn)行更多實(shí)驗(yàn)和比較、設(shè)計(jì)更有效的特征描述子，并將算法應(yīng)用到實(shí)際當(dāng)中去.

參考文獻(xiàn)

[1] DAVID L G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[2] Mikonaiczyk K, Schmid C. A performance evaluation of local descriptors[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10):1 615-1 630.

[3] Mikolajczyk K, Schmid C. A performance evaluation of local descriptors[J]. IEEE Trans. Pattern Analysis and Machine Intelligence, 2005, 27(10):1 615-1 630.

[4] Ke Y, Sukthankar R. PCA-SIFT: A More Distinctive Representation for Local Image Descriptors[C]. Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition, Washington, DC, USA, 2004: 511-517.

[5] Bay H, Tuytelaars T, Gool L V. SURF: Speeded up Robust Features[C]. European Conference on Computer Vision, Springer-Verlag, Berlin, Heidelberg, 2006: 404-417.

[6] Morel J M, Yu G S. ASIFT: A new framework for fully affine invariant image comparison[J]. Society for Industrial and applied Mathematics Journal on Image Sciences, 2009, 2(2): 438-469.

[7] Mikolajczyk K, Schmid C. Scale and affine invariant interest point detectors[J]. International Journal of Computer Vision, 2004, 60(1): 63-86.