王忠飛，張朋濤

(浙江工業(yè)大學 機械工程學院，浙江 杭州 310000)

0 引 言

通常，機器人通過獲取到的圖像的顏色和輪廓信息進行外界場景的靜態(tài)分析，但如果需要進行動態(tài)場景追蹤時，簡單的顏色和輪廓信息就無法勝任了，需要用到特征檢測。

尺度不變特征變換(SIFT)是LOWE[1]在1999年提出來的，利用SIFT所產(chǎn)生的特征點對旋轉(zhuǎn)、縮放以及亮度的變化有很強的魯棒性，有一定的抗視角變化和抗仿射變換的屬性，同時具有很高的可擴展性，但是由于SIFT的特征向量描述子具有128維，計算成本高、匹配實時性差，易產(chǎn)生錯配誤配；為了提高特征向量匹配速度，KE Y和SUKTHANKAR R[2-3]提出了PCA-SIFT算法，將SIFT的特征向量的維數(shù)從128減少到36，匹配速度提高3倍，但匹配精度下降；BAY H等人[4]提出的SURF，使用積分圖像代替了卷積積分，借助積分圖像，圖像與高斯二階微分模板的濾波轉(zhuǎn)化為對積分圖像的加減運算，并且將特征向量的維數(shù)降到了64維，運算速度提高了3倍左右。以上皆為提高特征提取時的實時性，卻很少提到提取到特征點后的匹配算法的優(yōu)化以及其中所出現(xiàn)的問題該如何解決。

本研究將采用降維的思路，把128維的SIFT特征向量映射到一維空間內(nèi)進行最近鄰的檢索，并通過實驗對該算法進行驗證。

1 SIFT特征點的提取

1.1 尺度空間極值提取

1983年WITKIN提出尺度空間理論，1984年KOENDERINK[5]在把這種理論擴展到二維圖像，并且證明了高斯卷積核是實現(xiàn)尺度變換的唯一變換核。二維圖像在不同尺度下的尺度空間表示可由圖像與高斯核卷積得到，即：

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

(1)

其中，高斯核為：

(2)

式中：I—圖像數(shù)據(jù)；L—圖像的尺度空間；(x,y)—目標圖像的像素坐標；σ—高斯正態(tài)分布的方差，在這里被稱為尺度空間因子，它的值越大表征圖像被平滑越大，對應(yīng)的尺度越大[6]。

Lowe使用尺度空間中的差分高斯(difference of gaussian,DOG)極值作為判斷的依據(jù)。DOG算子定義為兩個不同尺度的高斯核的差分，設(shè)k為兩個相鄰尺度間的比例因子，DOG算子的定義如下：

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

(3)

式中：I—圖像數(shù)據(jù);L—圖像的尺度空間;(x,y)—目標圖像的像素坐標;σ—高斯正態(tài)分布的方差。

已知高斯金字塔分為很多組，每組又分很多層，層與層之間有不同尺度的區(qū)別，下一組尺度為σ的圖像的最底層，是由上一組中尺度為2σ的圖像進行參數(shù)為2的降采樣所得到[7]。由于DOG金字塔出自于兩個不同尺度的高斯平滑圖像相減得到，雖然DOG需要在每層金字塔多做一次高斯操作(即為了得到S+2張DOG圖需要S+3張高斯模糊圖)，但通過減法取代高斯核的計算過程，顯著減少了運算次數(shù)，提高了運算效率[8]。

高斯金字塔與DOG金字塔如圖1所示。

圖1 高斯金字塔與DOG金字塔

可見，DOG金字塔比高斯金字塔每組多出一張圖像。完成金字塔的構(gòu)建后，即可開始檢測DOG的極值。極值的檢測如圖2所示。

圖2 DOG空間局部極值檢測

每個像素需要跟在同一尺度下的周圍鄰域8個像素和相鄰尺度相應(yīng)位置的9×2個像素比較，總共需要與26個像素進行比較，只有當被檢測點的DOG值大于或是小于該26個點的時侯才能將此點保存，并進行下一步的計算。

1.2 特征點定位

筆者使用擬合三維二次函數(shù)用以確定關(guān)鍵點的位置和尺度，粗略得到圖像的SIFT特征點集合X0。但還需要對數(shù)據(jù)做進一步的篩選。

刪除對噪音比較敏感的對比度比較低的點，將需判斷的特征點x的偏移量設(shè)為Δx，對比度為D(x)，對x的DOG函數(shù)進行泰勒展開為：

(4)

(5)

式中：X—篩選后的穩(wěn)定的SIFT特征點的集合。

由于邊緣梯度方向主曲率值較大，而邊緣方向曲率較小，可以將主曲率比值大于一定閾值的點將其剔除。通過一個2×2的Hessian矩陣可求出主曲率[9]，即：

(6)

式中：Dxx，Dxy，Dyy—候選點鄰域?qū)?yīng)位置的像素差分。

候選點的DOG函數(shù)D(x)的主曲率與2×2的Hessian矩陣特征值成正比，令α為H的最大特征值，β為H的最小特征值，且α=γβ，則D(x)主曲率的比值與γ成正比，有：

(7)

式中：Tr(H)—矩陣H的跡。

(γ+1)2/γ只與兩特征值有關(guān)，與特征值自身大小無關(guān)，當兩特征值相等時最小，且隨著γ增大而增大，再取一閥值，當γ大于閥值時認定為邊緣特征點刪除。

1.3 特征點方向參數(shù)賦予

為了使所得的特征點具有旋轉(zhuǎn)不變性，筆者利用關(guān)鍵點鄰域像素的梯度方向分布特性，可以為每個關(guān)鍵點指定方向參數(shù)。而后面定義的關(guān)鍵點描述特征符是相對于這個主方向的，因而可以實現(xiàn)匹配時圖像的旋轉(zhuǎn)無關(guān)性?？梢酝ㄟ^梯度直方圖統(tǒng)計法來確定關(guān)鍵點的方向，即統(tǒng)計以關(guān)鍵點為原點，利用所有在該區(qū)域內(nèi)的像素點的梯度形成一個方向直方圖。

各方向梯度直方圖如圖3所示。

圖3 各方向梯度直方圖

本研究在以特征點為中心的鄰域內(nèi)計算出各個方向的直方圖，計算出每個方向的幅值。梯度方向的直方圖的橫軸是梯度方向的角度，范圍為0～360°，直方圖每10°一個柱，共36個柱，縱軸是各個方向?qū)?yīng)的梯度幅值的和，選取直方圖中幅值和最大的點的方向作為主方向。

通過以上的計算已經(jīng)可以找到SIFT特征點的位置、尺度和方向信息。下面就需要使用一組向量來描述關(guān)鍵點也就是生成特征點描述子，這個描述符除了包含特征點，也含有其周圍對其有貢獻的像素點。描述子應(yīng)具有較高的獨立性，以保證匹配率。為了保證SIFT的旋轉(zhuǎn)不變性，首先需要使坐標軸的方向與關(guān)鍵點的方向保持一致，再在關(guān)鍵點周圍取8×8的區(qū)域。

特征點的特征向量構(gòu)造如圖4所示。

圖4 特征點的特征向量構(gòu)造

圖4中，左圖的中心點為關(guān)鍵點，周圍的方塊代表像素點，求取每個像素的梯度幅值與梯度方向，箭頭方向代表該像素的梯度方向，長度代表梯度幅值，圖中的圈代表高斯加權(quán)的范圍，越靠近關(guān)鍵點的像素梯度方向信息對結(jié)果影響越大，然后利用高斯窗口對其進行加權(quán)運算。

最后本研究在每個4×4的小塊上繪制8個方向的梯度直方圖，計算每個梯度方向幅值的和，構(gòu)成一個關(guān)鍵點的種子點。4個種子點初步構(gòu)成了一個完整的SIFT特征向量。這樣的特征向量描述子的構(gòu)造對于SIFT的特征向量匹配有比較好的魯棒性。在實際應(yīng)用中，為了加大特征向量的穩(wěn)定性，常常使用4×4共16個種子點來描述一個特征向量，因此，每個特征向量產(chǎn)生128個數(shù)據(jù)，最終形成128維的SIFT特征向量。

SIFT算法的特征點匹配本質(zhì)上就是高維向量的最近鄰搜索問題[10-11]，而最基本的高維搜索方法即為窮舉搜索法。窮舉搜索法可不受維數(shù)限制，并且始終能在所有可能解中得到最優(yōu)解[12]。但是對于128維的SIFT特征向量來說，由于提取出一幅圖片的特征向量通常在千個數(shù)量級上，使用窮舉搜索法進行特征點匹配的效率非常低、計算量大、時間長，不是最佳解決辦案。

2 算法描述

為提高SIFT特征匹配速度，本文提出一種基于歐氏距離和特征向量夾角的最近鄰搜索算法。該算法可描述為：設(shè)在q維歐式空間Rq中，存在2個高維向量集合A1={Vi|Vi∈Rq,i=1,2,…,n}和A2={Vl|Vl∈Rq,i=1,2,……,l}，在A1中的?Vi∈A1要在集合A2中搜索出其最鄰近的值。選取q維歐式空間中的原點O(0,0,…0)作為參考點，計算出集合A2中所有的向量到原點的歐氏距離D(Vl,O)，并進行升序或降序排列；保存起來在集合A3中，再計算出?Vi∈A1到原點O(0,0,…0)的歐氏距離d，根據(jù)設(shè)定的誤差檢索范圍e將查詢范圍確定在A3={Vl|Vl∈Rq,D(Vl,O)∈[d-e,d+e],i=1,2,…,l}中。再在集合A2中隨機選擇一個參考向量Vr，計算集合A2中所有的向量到參考向量Vr的夾角，并進行升序或降序排列；保存起來在集合A4中，根據(jù)集合A3和A4的索引值映射，在集合A4中將上述A3={Vl|Vl∈Rq,D(Vl,O)∈[d-e,d+e],i=1,2,…,l}范圍內(nèi)的值查詢出來，保存在集合A5中，利用余弦定理計算出需要查詢的特征向量Vi與選取的參考向量Vr之間的夾角θ，根據(jù)預(yù)先所選定的查詢范圍參數(shù)e計算出需要查詢向量的最大角度誤差α，確定最終檢索范圍A6={Vl|Vl∈A5,∈[θ-α,θ+α]}，在這個范圍，如果不存在特征向量，則認為匹配失敗，無理想匹配點，如果存在且不止一個，此時分別計算它們之間的歐氏距離，找出最鄰近點，此時查詢出的最鄰近點的誤差在誤差范圍e以內(nèi)。

這樣，只需要輸入一個參數(shù)，就可以快速查詢出期望的最理想的鄰近點作為匹配的特征向量。基于歐氏距離和向量夾角的最近鄰搜索算法的具體實現(xiàn)步驟為：

(1)在n維歐式空間Rn中，求出所有包含所有特征向量的集合Tn中的每一個特征向量相對于原點的歐氏距離，并保存在數(shù)組Ao中；

(2)在n維歐式空間Rn中，選擇一個參考向量Vr，利用余弦定理求出所有包含所有特征向量的集合Tn中的每一個特征向量相對于參考向量Vr的夾角，并保存在數(shù)組Aj中；

(3)對數(shù)組Ao和Aj中的值進行升序或是降序排列，由于同一個特征變量通過上面的兩次計算所得的索引值不同，故將兩者排序后的索引值做個映射保存在對象Om中，以備后面步驟中檢索；

(4)輸入需要查詢的特征向量Vc，計算出其到原點的歐氏距離。由于在數(shù)組Ao中存在已經(jīng)計算出的查詢向量Vc的歐氏距離值，故搜索到此值時返回其對應(yīng)的索引值index并保存在變量中；

(5)根據(jù)所選定的查詢范圍參數(shù)e確定的索引范圍[index-e,index+e];

(6)根據(jù)所選定的查詢范圍參數(shù)e計算出需要查詢向量的最大角度誤差α；

(7)利用余弦定理計算出需要查詢的特征向量Vc與(2)中選取的參考向量Vr的夾角θ；

(8)在限定的較小的索引空間內(nèi)，利用(3)中的映射對象Om查詢出該范圍內(nèi)所有特征向量與參考向量Vr的夾角；

(9)利用(7)中的角度誤差范圍搜索最鄰近值，如果在這個范圍內(nèi)存在且不止一個，則分別計算出匹配向量與它們的歐氏距離，進行單獨比較，歐式距離最小的特征向量，即可作為理想的正確特征向量保存，如果不存在則默認要查詢的特征向量無正確的匹配向量。注意此時應(yīng)忽略查詢特征向量Vc本身計算出的夾角，無須比較。

由此可見，該算法只需一次數(shù)據(jù)預(yù)處理，即可將海量的高維空間數(shù)據(jù)檢索簡化為一個在較小的一維空間范圍內(nèi)的檢索，從而提高SIFT特征點匹配的速度。

3 算法驗證與結(jié)果分析

為驗證基于歐氏距離和特征向量夾角的最近鄰搜索算法(使用EVA表示該算法)的有效性，本文選取了BBF算法作為比較，驗證改進的SIFT匹配算法(即基于歐氏距離和特征向量夾角的最近鄰搜索算法)的有效性和優(yōu)越性。

實驗所采用的算法為Rob Hess維護的SIFT算法庫。實驗用的樣張來自與牛津大學VGG實驗室的Affine Covariant Features圖像測試庫。

3.1 性能評價標準

(1)正確匹配總數(shù)。正確匹配指的匹配對中的兩個特征點之間的歐氏距離小于給定的閾值，并且兩個特征點對應(yīng)在不同圖片空間中的相同物理位置，本文中描述的正確匹配總數(shù)為在進行Ransac算法剔除誤匹配點后的匹配點對數(shù)；

(2)配準率。配準率=1-錯誤率，可以表述為：

(3)計算速度。計算速度是指SIFT在進行特征點的匹配時所耗費的時間。

3.2 算法驗證

本研究對兩種算法中的一些參數(shù)進行預(yù)置和說明。針對最近鄰與次近鄰的比值，經(jīng)過對大量任意存在尺度、旋轉(zhuǎn)和亮度變化的兩幅圖片進行匹配結(jié)果，本文預(yù)置為0.5且全程不變。在EVA算法中歐氏距離計算時所需要的參考點均采用高維空間中的原點，在進行向量夾角計算時需要的參考向量均采用Vr={1,2,3,…,128}。在BBF算法中，除了搜索最近鄰個數(shù)的閾值變化以外，其他的參數(shù)均保持不變，全部保持默認參數(shù)。實驗中選取查詢范圍參數(shù)0～0.5 mm，每次變化的步長為0.05 mm。

牛津大學VGG實驗室圖像測試如圖5所示。

圖5 牛津大學VGG實驗室圖像測試

SIFT識別效果圖如圖6所示。

圖6 SIFT識別效果圖

本研究對兩幅圖片做經(jīng)典SIFT特征識別，檢測出的尺度不變性特征點的個數(shù)為2 909個，耗時362 s。在不進行誤配點剔除的情況下，能看到有很多誤配點，但好在基數(shù)大，在進行誤配點剔除后，仍能得到很多有效的配對點。

本研究取查詢范圍參數(shù)0～0.5 mm，以0.05 mm為步長進行比較，分別計算統(tǒng)計出運算后的正確匹配總數(shù)、配準率和計算時間。

查詢范圍參數(shù)與配準率之間的關(guān)系如圖7所示。

圖7 查詢范圍參數(shù)與配準率之間的關(guān)系

查詢范圍參數(shù)與正確匹配總數(shù)之間的關(guān)系如圖8所示。

圖8 查詢范圍參數(shù)與正確匹配總數(shù)之間關(guān)系

查詢范圍參數(shù)與匹配耗時之間的關(guān)系如圖9所示。

圖9 查詢范圍參數(shù)與匹配耗時之間的關(guān)系

算法特征點匹配耗時對比結(jié)果如表1所示。

表1 BBF與EVA算法匹配耗時對比

3.3 結(jié)果分析

由圖(7～9)可看出：在查詢范圍參數(shù)不同的情況下，EVA算法和BBF算法的配準率基本相同，正確匹配總數(shù)方面EVA算法比BBF算法高出很多，但隨著查詢范圍參數(shù)的不斷增大，差距不斷縮??；在各段查詢范圍參數(shù)中的耗時BBF算法比EVA算法高出許多，EVA算法穩(wěn)定保持小幅增長，計算耗時基本保持在50 s以內(nèi)。表1數(shù)據(jù)表明：EVA算法的計算效率比BBF算法平均提高了2.5倍左右。

4 結(jié)束語

本文提出的算法通過歐氏距離和向量夾角的計算，將高維空間的數(shù)據(jù)簡化到一維空間內(nèi)進行處理，然后通過比較查詢向量與所有向量之間的歐氏距離和夾角小于預(yù)先設(shè)定的某一閾值來進行最鄰近查找，大大提高了特征點匹配效率。

本文提出的基于歐氏距離和特征向量夾角的最近鄰搜索算法在提高SIFT特征點匹配效率上優(yōu)勢明顯，具有一定的使用價值。