基于SIFT的二進(jìn)制特征描述匹配算法

丁 健，許光宇

(安徽理工大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001)

圖像匹配技術(shù)因其目前在計算機(jī)視覺，模式識別等領(lǐng)域所擁有的學(xué)習(xí)價值和工業(yè)生產(chǎn)價值，近年來被廣泛應(yīng)用于遙感檢測[1]、人臉識別[2]、醫(yī)學(xué)圖像配準(zhǔn)[3]等諸多領(lǐng)域。但是其匹配過程中存在尺度、視角、照明等敏感的影響因素，導(dǎo)致研究難度加大。近年來，有關(guān)圖像匹配的算法研究成果顯著。針對尺度變化產(chǎn)生的問題，2004年Lowe等[4]提出了具有尺度變換不變性的描述符SIFT，該算子的優(yōu)勢體現(xiàn)在優(yōu)質(zhì)的平移，光照，尺度，仿射不變性，并且在有部分場景遮擋，噪聲，運(yùn)動等情況下依舊保持穩(wěn)定。傳統(tǒng)SIFT算法具有優(yōu)異的魯棒性，但是由于其特征描述符是高維的浮點數(shù)，并且用歐氏距離度量其特征向量之間相似性，這對計算效率和存儲性能方面帶來了不小的挑戰(zhàn)。Ke等[5]用PCA技術(shù)對SIFT生成的特征描述符進(jìn)行降維，在速度和節(jié)約存儲方面得到了提升，但是對尺度變化和噪聲敏感，根據(jù)文獻(xiàn)[6]的論述，該方法與SIFT相比并無優(yōu)勢；Bay等[7]提出SURF（speeded up robust features）算法，用 Haar小波近似梯度計算，積分圖像和箱式濾波器的運(yùn)用避免了SIFT的降采樣過程，大幅度提高了運(yùn)算效率，但是其對于旋轉(zhuǎn)變換敏感；zhou等[8]利用數(shù)據(jù)多維縮放（multidimensional scaling,MDS）同樣在SIFT特征描述符降維方面入手，滿足了原始空間中樣本之間的距離在低維空間中基本的一致性，但是其對距離矩陣的計算復(fù)雜性高，數(shù)據(jù)量大的情況下魯棒性差。以上算法很難做到在保證旋轉(zhuǎn)，仿射，尺度變換下的穩(wěn)定性的同時，提高運(yùn)算效率，降低存儲成本，近幾年對二進(jìn)制背景下的SIFT算法研究給我們提供了新的思路。Calonder等[9]提出的 BRIEF(binary robust independent elementary features)算法利用灰度大小關(guān)系生成二進(jìn)制碼串，但是其面對旋轉(zhuǎn)，尺度變換表現(xiàn)很差，抗噪能力弱。Rublee等[10]結(jié)合了 FAST算法和BRIEF算法，提出了ORB算法來解決旋轉(zhuǎn)不變性問題，但是其特征描述符的區(qū)分性弱，匹配效果一般。Ni等[11]則在SIFT基礎(chǔ)上，提供了一種基于描述符種子點內(nèi)部和外部梯度大小關(guān)系的二進(jìn)制編碼的新思路。

本文基于SIFT算法進(jìn)行改進(jìn)，關(guān)鍵點主方向采用一階中心矩估計，之后對描述符生成這一環(huán)節(jié)進(jìn)行改進(jìn)，通過子區(qū)域梯度分量大小關(guān)系編寫二進(jìn)制碼串，最后利用敏感哈希函數(shù)LSH（location sensitive hash）進(jìn)行特征分類匹配。實驗結(jié)果表明，較于傳統(tǒng)SIFT，其匹配準(zhǔn)度和速度都有不錯的提升。

1 傳統(tǒng)SIFT算法原理

尺度不變特征變換（SIFT）算法概括來說就是在不同層次尺度空間上定位特征點，之后提取出其尺度，位置，方向，生成區(qū)分性強(qiáng)的特征描述符進(jìn)行圖像匹配。Lowe把其過程分成四步：構(gòu)建尺度空間，尋找候選點；關(guān)鍵點的準(zhǔn)確定位；關(guān)鍵點的主方向確定；關(guān)鍵點的描述。

為了滿足不同尺度下的圖像特征變換，建立多層次的尺度空間，高斯卷積核作為支持尺度變換的唯一線性核我們用來在預(yù)處理階段對圖像做卷積處理，定義一副二維圖像I經(jīng)過高斯卷積處理后結(jié)果為：

其中：L(x,y,σ)表示圖像尺度空間；*表示圖像卷積；I(x,y)代表點(x,y)處的圖像；σ表示尺度空間因子，σ值越大圖像越模糊；G是尺度可變高斯函數(shù)：

在不同的尺度空間上建立高斯金字塔。對于一副已知二維圖像I來說，建立多個子八度（octave）圖像層，第一個octave尺寸為原始圖像，而后每個octave在上一個圖像層基礎(chǔ)上進(jìn)行降采樣，大小為上一個的1/4，從而形成多個圖像層。對每個octave的圖像做不同程度的高斯模糊。進(jìn)一步建立高斯差分尺度空間（DOG）有助于準(zhǔn)確定位特征點位置，具體為首先計算不同尺度下的高斯差分核，然后做圖像卷積處理。

其中：D(x,y,σ)是高斯差分尺度空間；k為尺度。

確定候選極值點的方法是與采樣點同階尺度的8個鄰近點和上下階尺度的各9個點，總共26個像素點進(jìn)行比較，如果是最大值或者是最小值時，可以初步判定為關(guān)鍵點。

使用三維二次函數(shù)對候選點進(jìn)行擬合以降低離散空間候選點可能存在的不準(zhǔn)確性，之后利用近似Harris角點檢測器[12]來去除邊緣響應(yīng)，以確保精確定位。尺度空間DOG函數(shù)的泰勒展開式

其中：X=(x,y,σ)T。

計算并統(tǒng)計關(guān)鍵點周圍鄰域各個方向上的梯度模值以形成直方圖確定關(guān)鍵點主方向。計算關(guān)鍵點鄰域的4×4個子區(qū)間內(nèi)規(guī)定的八個方向中每個方向上的梯度值，作為每個子區(qū)間權(quán)值。最后生成4×4×8=128維的特征描述子。圖一展示的是SIFT算法中主方向確定，子區(qū)域梯度模值計算，以及最終描述子生成的這三個步驟示意圖如圖1。

圖1 原SIFT

2 改進(jìn)的二進(jìn)制匹配算法

本節(jié)將詳細(xì)闡述一種改進(jìn)的SIFT描述符表示方法。沿用SIFT算法中構(gòu)造DOG尺度空間，比較獲得候選點，擬合函數(shù)精確確定關(guān)鍵點這幾步驟。較原SIFT，該方法在關(guān)鍵點主方向確定和描述符生成及最后的匹配策略上做了改進(jìn)。

2.1 關(guān)鍵點主方向的確定

傳統(tǒng)SIFT確定關(guān)鍵點主方向可概括為：以關(guān)鍵點為中心，鄰域3σ為半徑，以10°為間隔，分別計算0～360°區(qū)間內(nèi)36個子區(qū)間的梯度分布直方圖，計算出的最大值區(qū)間所代表的方向則是主方向。為了算法的嚴(yán)謹(jǐn)性，Lowe同時還保留了大于主方向峰值梯度80%的方向作為輔方向。這種方法無疑可以精確確定關(guān)鍵點主方向同時保證特征描述符的可區(qū)分性和魯棒性，但是其實時性低，抗噪聲能力較差，同時也需要很大的存儲空間。

本文算法的關(guān)鍵點主方向采用一階中心矩[13]來估計。幾何矩的概念由Hu[14]在1962年首次提出，Wong等[15]于1978年討論了離散情況下各階矩的計算方法。幾何矩因其計算效率高和良好的平移、旋轉(zhuǎn)和尺度不變性和較強(qiáng)的抗噪能力，被應(yīng)用于本文算法可以大幅度降低計算復(fù)雜度同時保證準(zhǔn)確性。

定義輸入圖像的原始(p+q)階矩為：

定義輸入圖像的質(zhì)心為：

由等式(6)得到輸入圖像的一階中心矩為：

其中：Cx和Cy分別表示質(zhì)心的橫縱坐標(biāo)。

相應(yīng)的一階矩為：

進(jìn)而得到關(guān)鍵點的主方向為：

相較于傳統(tǒng)SIFT算法，避免了在關(guān)鍵點像素鄰域重復(fù)計算目標(biāo)子區(qū)域梯度值的復(fù)雜過程。

2.2 改進(jìn)的描述符表示方法

傳統(tǒng)SIFT生成4×4×8=128維特征向量，每個維度分量按照灰度值可表示成0～255間的整數(shù)，這意味著極端情況下有256128≈1.8×10308個不同的特征向量，這樣龐大的數(shù)據(jù)量雖然可以保證描述符很高的區(qū)分性，但是同時需要計算機(jī)很大的存儲空間。如果把每個維度分量按照某種準(zhǔn)則表示成二進(jìn)制形式，每個維度分量大小為2(0或者1)，那么同樣維度大小的特征向量甚至是更高維度的特征向量(假設(shè)為128維或者256維)，特征向量的數(shù)量可以壓縮為 2128≈3.4×1038個或者 2256≈1.158×1077個，可以看到這樣的數(shù)據(jù)量也能保證很高的區(qū)分性，并且可以有效節(jié)省存儲空間。本節(jié)以下內(nèi)容將詳細(xì)闡述生成一個256維的二進(jìn)制碼串特征描述符的具體過程。

首先，把圖像旋轉(zhuǎn)到關(guān)鍵點主方向上，不同于原始SIFT在關(guān)鍵點鄰域的16×16正方形區(qū)域內(nèi)計算每個大小為4×4的子區(qū)域的梯度值，本文以關(guān)鍵點為中心，半徑為16提取一塊圓形區(qū)域，并按照同樣大小等分成16個扇形區(qū)域，給每個扇形區(qū)域編號。以關(guān)鍵點主方向上方的扇形區(qū)域為起點，順時針編號分別為S1，S2，…，S16，如圖 2。S2 S1 S16 S15

圖2 用于計算梯度的扇形子區(qū)域

分別計算每個扇形區(qū)域內(nèi)像素八個方向的梯度值大小，隨后討論每個區(qū)域梯度值內(nèi)部大小關(guān)系和相鄰區(qū)域大小關(guān)系并生成二進(jìn)制向量：

2.2.1 內(nèi)部關(guān)系表述

內(nèi)部關(guān)系由每個扇形區(qū)域內(nèi)梯度值在8個主要方向上的大小差異所體現(xiàn)。我們將每個方向值順時針與下一個方向值進(jìn)行比較，每個直方圖得到8位二進(jìn)制值。由16個扇形區(qū)域，得到一個16×8=128位長的二進(jìn)制向量。

圖3是一個扇形區(qū)域內(nèi)八個方向梯度大小的表示。第j個子區(qū)域新生成的二進(jìn)制特征向量為Sj，第i個方向上的梯度直方圖的值為ki，對每個子區(qū)域第i個二進(jìn)制值定義為：

則每一扇形子區(qū)域塊的特征向量表示為：

新的128位的二進(jìn)制特征向量為：

圖3 扇形子區(qū)域八個方向梯度示例

2.2.2 外部關(guān)系表述

外部關(guān)系表示圓內(nèi)每個扇形區(qū)域?qū)?yīng)分量的梯度大小差異。我們順時針比較每個相鄰的扇形區(qū)域?qū)?yīng)梯度分量的大小，每兩個相鄰區(qū)域通過比較生成8位二進(jìn)制值。16次比較，得到一個16×8=128位長的二進(jìn)制向量。

與公式(10),(11)類似，有如下定義：

則新的每個二進(jìn)制特征向量S′j

新的128位的二進(jìn)制特征向量

把這兩個128維的特征向量結(jié)合，得到一個新的128+128=256維的二進(jìn)制特征向量：

與原始SIFT相比，節(jié)省約90%的存儲空間。

2.3 關(guān)鍵點匹配

傳統(tǒng)SIFT判斷兩幅圖像關(guān)鍵點是否匹配正確的方法是取圖像1的某個關(guān)鍵點，然后依次計算圖像2中每個特征點與圖像1中選定特征點的歐式距離，并且找到距離最小的兩個點，用最近距離除以次近距離，將結(jié)果和給定的閾值進(jìn)行比較(Lowe建議值為0.8)，如果小于既定閾值則可以初步判定該點對匹配成功。這樣的匹配方法很有可能出現(xiàn)誤匹配和漏匹配的問題，同時特征點對間歐式距離的計算十分復(fù)雜，對于這樣的情況，很多研究者提供了改善的方法，文獻(xiàn)[16]提出用準(zhǔn)歐式距離代替歐式距離計算關(guān)鍵點相似度；文獻(xiàn)[17]中ransac算法用于執(zhí)行幾何驗證，以進(jìn)一步準(zhǔn)確定位匹配點；文獻(xiàn)[18]使用兩種不同的匹配策略來糾正匹配結(jié)果中“一對多“和“一對一”這兩種錯誤的匹配形式。本文生成的特征描述符是基于二進(jìn)制的256位碼串，因此匹配過程用計算漢明距離代替了計算歐氏距離，從而降低計算復(fù)雜度。

漢明距離的計算可以通過簡單的異或運(yùn)算完成，雖然其在計算機(jī)內(nèi)部計算效率非常高，但是當(dāng)數(shù)據(jù)量很大的場合，如果只是單純的線性的逐個匹配效率仍舊不高，文獻(xiàn)[19]分析了當(dāng)特征點對的數(shù)量持續(xù)增長時，二進(jìn)制向量的匹配速度比較傳統(tǒng)SIFT優(yōu)勢不明顯。

本文利用LSH進(jìn)行圖像快速匹配和查找。LSH算法最早由Indyk等[20]提出，不同于傳統(tǒng)哈希函數(shù)，其具有位置敏感度，具體表現(xiàn)在經(jīng)過LSH之后的離散點具有一定的概率能夠在某種程度上相似。本文LSH算法將256維的二進(jìn)制特征通過特定的Hash函數(shù)投影到各個Hash桶內(nèi)，LSH散列后，比較同一個Hash桶內(nèi)的特征向量就可以進(jìn)行特征匹配，從而降低了計算復(fù)雜度。圖4展示了傳統(tǒng)哈希和LSH的區(qū)別。

圖4 LSH和傳統(tǒng)哈希框架

3 實驗結(jié)果

本文實驗的硬件平臺是intel Core i7-8700處理器，主頻3.20 GHz，16 GB內(nèi)存，GTX 1050顯卡，windows操作系統(tǒng),利用Matlab2016a的平臺進(jìn)行仿真實驗。

3.1 算法耗時評估

為了計算方便，從Oxford數(shù)據(jù)集選取100張分辨率為300×240的圖像，分別統(tǒng)計本文算法和原始SIFT的耗時，然后再取平均值進(jìn)行比較，結(jié)果如表1。

本文算法在匹配耗時方面比SIFT快近56%，主要體現(xiàn)在主方向估計、描述符生成、圖像匹配三個步驟。對于某些沒有浮點計算優(yōu)化的處理器架構(gòu)而言，這種基于二進(jìn)制的算法優(yōu)勢會更加明顯。

表1 本文算法和原始SIFT耗時比較/ms

3.2 匹配正確率評估

本文采用牛津VGG集團(tuán)提供的仿射協(xié)變特征數(shù)據(jù)集（Mikolajczyk）來系統(tǒng)地評估本文提出的圖像匹配算法?？偣?個子數(shù)據(jù)集，每個子數(shù)據(jù)集中有6個圖像，所有這些圖像都來自一個原始圖像。如圖5，用第一張原始圖片和經(jīng)過不同程度變換的5張圖片進(jìn)行匹配實驗，對圖像在縮放+旋轉(zhuǎn)變換，圖像模糊，視點變換的情況下的匹配結(jié)果做出評估。每幅圖像特征點對匹配正確率k

其中：R表示的是正確匹配的特征點對；N是總的匹配特征點對數(shù)量。

圖5 實驗圖像的匹配對正確率示意圖

從實驗結(jié)果看，運(yùn)用本文算法在絕大多數(shù)情況下進(jìn)行匹配，匹配正確率相較傳統(tǒng)SIFT都得到了提升。除了在面對很大程度視點變換的情況下（如圖5(c)所示）匹配正確率較傳統(tǒng)SIFT有所降低，但是在圖5(c)的前兩副圖像的視點變換下性能依舊不弱于傳統(tǒng)SIFT。

4 小結(jié)

本文針對傳統(tǒng)SIFT算法計算復(fù)雜性高、存儲需求大的缺點并有效利用其區(qū)分性強(qiáng)、效率高的優(yōu)點提出了一種改進(jìn)SIFT的二進(jìn)制特征描述匹配算法。在SIFT的尺度空間理論基礎(chǔ)上，二進(jìn)制量化生成的特征向量，并運(yùn)用位置敏感哈希函數(shù)以漢明距離代替歐式距離比較描述符，計算相似性。結(jié)果表明，該算法在面對視點變換、光照、縮放+旋轉(zhuǎn)變換，圖像模糊和JPEG壓縮情況下的匹配準(zhǔn)確率和效率都一定程度上優(yōu)于傳統(tǒng)SIFT。