丁 健，許光宇

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 原SIFT

2 改進的二進制匹配算法

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

2.1 關鍵點主方向的確定

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

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

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

定義輸入圖像的質心為：

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

其中：Cx和Cy分別表示質心的橫縱坐標。

相應的一階矩為：

進而得到關鍵點的主方向為：

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

2.2 改進的描述符表示方法

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

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

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

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

2.2.1 內部關系表述

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

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

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

新的128位的二進制特征向量為：

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

2.2.2 外部關系表述

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

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

則新的每個二進制特征向量S′j

新的128位的二進制特征向量

把這兩個128維的特征向量結合，得到一個新的128+128=256維的二進制特征向量：

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

2.3 關鍵點匹配

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

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

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

圖4 LSH和傳統(tǒng)哈?？蚣?/p>

3 實驗結果

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

3.1 算法耗時評估

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

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

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

3.2 匹配正確率評估

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

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

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

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

4 小結

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