基于SIFT的新特征提取匹配算法

楊福嘉，鄭麗穎

哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001

圖像匹配是針對(duì)不同視角、不同傳感器獲得的圖像，通過(guò)匹配算法，找出圖像之間紋理、特征、結(jié)構(gòu)等的相似性和一致性，進(jìn)而找出相似圖像。圖像匹配是圖像領(lǐng)域中的熱點(diǎn)問(wèn)題，高精度的圖像匹配能夠更好地處理圖像拼接、目標(biāo)跟蹤與識(shí)別等后續(xù)工作[1]。圖像匹配算法可以分為基于灰度的圖像匹配方法、基于變換域的圖像匹配方法和基于特征的圖像匹配方法這3大類(lèi)[2]。其中基于特征的匹配方法抗噪性較好，匹配精度高，對(duì)圖像中物體的旋轉(zhuǎn)和遮擋方面具有更好的魯棒性。選取合適的特征能夠在圖像的旋轉(zhuǎn)、平移、尺度變換、視角變化、光照變化等條件下具有不變性。由于其優(yōu)良的匹配性能，人們通常將基于特征的圖像匹配作為主要的研究方法。

近年來(lái)，SIFT由于其旋轉(zhuǎn)和尺度不變性、良好的光照適應(yīng)性，受到研究者廣泛關(guān)注[3]。楊世沛等[4]使用灰度均勻化和冗余分割樹(shù)技術(shù)建立成更均勻、更寬的SIFT直方圖，有效解決了光照變化過(guò)大時(shí)檢測(cè)性能降低的問(wèn)題。李彥等[5]使用SIFT算法，并通過(guò)數(shù)據(jù)庫(kù)中已有的車(chē)牌標(biāo)記來(lái)識(shí)別車(chē)牌漢字，并對(duì)其位置進(jìn)行定位，提高了車(chē)牌識(shí)別效率。Ramu等[6]使用SIFT與隨機(jī)樣本一致性進(jìn)行圖像偽造檢測(cè)，與現(xiàn)有的偽造檢測(cè)方法相比，它可以提取更準(zhǔn)確的結(jié)果。但是上述方法在提高準(zhǔn)確率與效率的同時(shí)，并沒(méi)有提高匹配所需的時(shí)間。主要原因是SIFT在構(gòu)造高斯差分（difference of Gaussian，DoG）算子過(guò)程中，會(huì)產(chǎn)生較多不穩(wěn)定的邊緣點(diǎn)[7?8]，而這些點(diǎn)在生成描述符時(shí)也要被一一計(jì)算。實(shí)驗(yàn)表明：SIFT特征點(diǎn)的提取時(shí)間占總時(shí)長(zhǎng)的30%左右[9]，從而導(dǎo)致匹配時(shí)間較長(zhǎng)，難以進(jìn)行實(shí)時(shí)性的應(yīng)用。角點(diǎn)是圖像領(lǐng)域中重要的局部特征。SCHMID[10]對(duì)多種角點(diǎn)算法進(jìn)行比較，結(jié)果表明在物體旋轉(zhuǎn)、平移和光照強(qiáng)度變化方面，Harris算法提取的角點(diǎn)特征是迄今為止穩(wěn)定性最好的。但是Harris方法的不足是不具備空間多尺度性，且提取特征的數(shù)量遠(yuǎn)不如SIFT特征點(diǎn)，導(dǎo)致匹配不精準(zhǔn)。

針對(duì)以上不足，對(duì)SIFT算法和Harris角點(diǎn)提取進(jìn)行改進(jìn)，提出一種新的圖像匹配算法。首先，對(duì)輸入圖像構(gòu)造高斯金字塔模型，在此模型中采用Harris角點(diǎn)提取特征，再使用Canny邊緣算子提取出更多有意義的特征點(diǎn)；然后，通過(guò)建立梯度直方圖的方法對(duì)上述特征點(diǎn)形成描述子；最后，采用歐式計(jì)算距離公式完成圖像之間的匹配。

1 SIFT 算法

SIFT算法被認(rèn)為是圖像匹配效果最好的方法之一，它對(duì)物體的尺度變化、剛體變換、光照強(qiáng)度和遮擋都具有較好的穩(wěn)定性。SIFT算法總共可分為4個(gè)階段：尺度空間構(gòu)建、特征點(diǎn)選擇、方向確定和特征點(diǎn)描述。尺度空間構(gòu)建的基本思想是在輸入的圖像模型中，通過(guò)高斯模糊函數(shù)連續(xù)地對(duì)尺度進(jìn)行參數(shù)變換，最終得到多尺度空間序列。圖像中某一尺度的空間函數(shù)L（x，y，σ）由可變參數(shù)的高斯函數(shù) G（x，y，σ）和原輸入圖像 I（x，y）卷積得出

高斯函數(shù)為：

式中：σ表示為尺度參數(shù)，σ越小，反應(yīng)的局部點(diǎn)越清晰；反之σ越大，圖像越模糊，越不能反應(yīng)出圖像的細(xì)節(jié)。

傳統(tǒng)的SIFT算法是通過(guò)建立DoG函數(shù)方法來(lái)提取特征點(diǎn)。每一個(gè)尺度對(duì)應(yīng)多幅圖像。在不同尺度參數(shù)組成的多個(gè)層數(shù)圖像中，高斯差分圖像由某一相同尺度層的相鄰圖像作差值得出。將得到的差分圖像與原圖像I（x，y）做卷積得到的DOG函數(shù)：

在得出DOG函數(shù)之后，計(jì)算不同尺度下的極值點(diǎn)。某一特征點(diǎn)通過(guò)周?chē)徲螯c(diǎn)的比較判斷該特征點(diǎn)是否為極值點(diǎn)，如圖1所示。其計(jì)算方法為確定某一尺度層的特征點(diǎn)，將它周?chē)瑢痈浇?個(gè)相鄰點(diǎn)和上下層相鄰尺度的2×9個(gè)像素點(diǎn)，共26個(gè)檢測(cè)點(diǎn)相比較，如果中心像素點(diǎn)是此鄰域像素點(diǎn)的最大值或最小值，則該點(diǎn)為極值點(diǎn)。

圖1 DOG 極值點(diǎn)檢測(cè)

通過(guò)以上計(jì)算得到的極值點(diǎn)并非都是穩(wěn)定特征點(diǎn)，需要一些限制條件來(lái)排除響應(yīng)較弱的極值點(diǎn)，篩選出精確、穩(wěn)定的特征點(diǎn)。

為使特征點(diǎn)具有旋轉(zhuǎn)不變性，采用高斯金字塔鄰域像素梯度的幅值和方向計(jì)算特征點(diǎn)的值，如式（1）與式（2）：

式中：L表示特征點(diǎn)所對(duì)應(yīng)的尺度空間；F（x，y）和H（x，y）為像素點(diǎn)的梯度幅值與方向。采用直方圖的方法分別記錄像素鄰域內(nèi)梯度的F和H，每個(gè)特征點(diǎn)的主方向?yàn)樵擖c(diǎn)直方圖最大峰值對(duì)應(yīng)方向；同時(shí)也統(tǒng)計(jì)該點(diǎn)附近大于其主方向峰值80%的方向，將其標(biāo)記為輔助方向，以增強(qiáng)魯棒性。

在特征點(diǎn)的4×4鄰域內(nèi)，分別記錄16個(gè)鄰域中每個(gè)鄰域內(nèi)8個(gè)方向的梯度信息，形成128維特征描述向量。考慮到光照強(qiáng)度變化對(duì)特征點(diǎn)的干擾，再將得到的128維描述向量進(jìn)行歸一化，形成最終描述符。

2 改進(jìn)的方法

傳統(tǒng)的SIFT匹配通過(guò)建立高斯金字塔模型，對(duì)每個(gè)塔模型的相鄰層做差值得到近似極值點(diǎn)。但是通過(guò)這種方法求出的極值點(diǎn)包含很多不穩(wěn)定點(diǎn)和無(wú)用點(diǎn)，導(dǎo)致特征點(diǎn)描述與后續(xù)的匹配時(shí)間過(guò)長(zhǎng)。對(duì)此本文對(duì)以上的不足進(jìn)行改進(jìn)（如圖2所示）。

圖2 改進(jìn)的特征匹配算法

首先，將原輸入圖像與高斯模糊函數(shù)作卷積計(jì)算，通過(guò)改變高斯模糊函數(shù)中尺度參數(shù)的大小得到多尺度空間，對(duì)其進(jìn)行多尺度Harris角點(diǎn)提取，再使用Canny邊緣提取算法對(duì)Harris角點(diǎn)進(jìn)行修飾，提取出更多穩(wěn)定的特征點(diǎn)，將得出的2種特征點(diǎn)進(jìn)行融合，若有重合的特征點(diǎn)，對(duì)其進(jìn)行合并處理；然后，使用傳統(tǒng)SIFT算法中的描述子對(duì)特征點(diǎn)進(jìn)行描述；最后，采用歐氏距離計(jì)算方法對(duì)上述提取的特征點(diǎn)進(jìn)行特征點(diǎn)對(duì)的匹配，得到最終匹配結(jié)果。

2.1 多尺度 Harris 角點(diǎn)提取

傳統(tǒng)的Harris角點(diǎn)不具有空間尺度不變性。因此，本文引入高斯金字塔模型，將原輸入圖像I（x，y）與高斯模糊函數(shù) G（x，y，σ）作卷積計(jì)算，得到高斯尺度空間函數(shù) L（x，y，σ），然后進(jìn)行 Harris角點(diǎn)提取。對(duì)于大小為σ的尺度層，Harris角點(diǎn)的二階矩公式為：

式中：G（x，y，σ）為帶有尺度參數(shù) σ的高斯函數(shù)；Ix和 Iy分別是原圖像 I（x，y）中在 x方向和 y方向上的導(dǎo)數(shù)梯度值。分別求出二階矩M（x，y，σ）的行列式det M和跡trace M。在此基礎(chǔ)求出角點(diǎn)的響應(yīng)函數(shù)

式中K為常數(shù)，通常取0.04~0.06。

當(dāng)由公式求出的Q值小于本文設(shè)定閾值t時(shí)，就將Q值設(shè)為0。本文取K=0.05。最后，在3×3的鄰域內(nèi)進(jìn)行非極大抑制，計(jì)算出某一區(qū)域的局部最大值，并將其記錄為角點(diǎn)。

2.2 Canny 邊緣提取

經(jīng)典的Harris角點(diǎn)算法會(huì)出現(xiàn)特征點(diǎn)漏檢的不足，而且Harris提取出的特征點(diǎn)數(shù)量遠(yuǎn)不如SIFT算法。對(duì)此本文提出一種多尺度Harris角點(diǎn)與Canny邊緣提取相結(jié)合的算法，既對(duì)邊緣特征點(diǎn)進(jìn)行了改善；同時(shí)也增加了更多有用特征點(diǎn)，為改善特征匹配性能打下基礎(chǔ)。

采用以下公式分別對(duì)每個(gè)尺度層計(jì)算圖像的梯度大小和方向：

式中：E（E）代表梯度大??；D（θ）表示梯度方向；Ix和 Iy分別代表二維圖像 I（x，y）在 x方向和 y方向的梯度值。根據(jù)梯度計(jì)算結(jié)果對(duì)像素點(diǎn)進(jìn)行極大值抑制，通過(guò)設(shè)定上下界閾值判斷像素點(diǎn)是否為邊界點(diǎn)。將提取后的特征點(diǎn)與Harris提取的角點(diǎn)進(jìn)行融合，合并兩者重復(fù)提取的特征點(diǎn)，得到最終特征點(diǎn)結(jié)果。

2.3 特征點(diǎn)描述和匹配

本文采用SIFT算法描述符。以上述提取之后的特征點(diǎn)為中心，在其附近4×4的鄰域小塊內(nèi)，每個(gè)小塊分別賦予8個(gè)方向向量，共生成128維特征向量。再將生成的特征描述向量進(jìn)行歸一化，以減少光強(qiáng)度變化帶來(lái)的影響。

為了得到2幅圖像間的對(duì)應(yīng)關(guān)系，本文采取BBF算法實(shí)現(xiàn)特征點(diǎn)對(duì)的匹配[3]。通過(guò)歐幾里得度量公式計(jì)算2個(gè)特征點(diǎn)的距離大小，再利用KD樹(shù)的性質(zhì)分別記錄距離最小值d1和次小值d2，將d1與d2的比值與設(shè)定閾值相比較，若d1/d2小于設(shè)定閾值，即視為匹配；否則視為不匹配。

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

采用3組對(duì)比實(shí)驗(yàn)分析本文提出的算法，如圖 3~5。實(shí)驗(yàn)環(huán)境為 Intel Core i5?4210 CPU, 2.9 GHz和內(nèi)存4 GB的Windows7 PC機(jī)。實(shí)驗(yàn)結(jié)果分別與經(jīng)典的SIFT和SURF[11]相比較，其中SIFT和SURF由VS2010的Opencv2.4.9實(shí)現(xiàn)，而本文算法在MATLAB 2014a中實(shí)現(xiàn)。實(shí)驗(yàn)圖像來(lái)自于 INRIA Holidays[12]，圖片分辨率均為 800×600。

圖3 圖像平移前后的匹配實(shí)驗(yàn)結(jié)果對(duì)比

圖4 圖像旋轉(zhuǎn)后匹配實(shí)驗(yàn)結(jié)果對(duì)比

圖5 圖像平移加旋轉(zhuǎn)后匹配實(shí)驗(yàn)結(jié)果對(duì)比

通過(guò)以上圖像對(duì)比分析，對(duì)實(shí)驗(yàn)結(jié)果數(shù)據(jù)進(jìn)行記錄與比較，對(duì)比結(jié)果如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)對(duì)比

其中，每幅圖像都由2張圖片組成，特征數(shù)量斜線(xiàn)前后的2個(gè)數(shù)字分別代表每幅圖圖左提取的特征點(diǎn)和圖右提取的特征點(diǎn)數(shù)量。上述結(jié)果表明：改進(jìn)算法的匹配正確率提高，速度明顯快于SIFT，時(shí)間基本與SURF算法持平。盡管文中算法提取的特征點(diǎn)數(shù)量減少了一些，但是減少的點(diǎn)多為邊緣不穩(wěn)定的點(diǎn)，而大部分有用的特征點(diǎn)被保留了下來(lái)，并且本文算法具有良好的魯棒性。

4 結(jié)論

本文針對(duì)SIFT會(huì)產(chǎn)生大量不穩(wěn)定邊緣點(diǎn)的不足，提出一種多尺度Harris角點(diǎn)與Canny邊緣提取結(jié)合的改進(jìn)算法。結(jié)果表明：1）使用Harris角點(diǎn)代替?zhèn)鹘y(tǒng)的SIFT提取特征點(diǎn)方法能夠有效地減少匹配時(shí)間；2）Harris角點(diǎn)與Canny邊緣提取的結(jié)合增加了特征點(diǎn)提取數(shù)量，同時(shí)也提高了匹配正確率。因此，本算法在保證有效減少不穩(wěn)定特征點(diǎn)的情況下，也提高了匹配精度和效率，更適用于圖像匹配的應(yīng)用。