王忠飛，張朋濤

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

0 引 言

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

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

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

1 SIFT特征點(diǎn)的提取

1.1 尺度空間極值提取

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

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

(1)

其中，高斯核為：

(2)

式中：I—圖像數(shù)據(jù)；L—圖像的尺度空間；(x,y)—目標(biāo)圖像的像素坐標(biāo)；σ—高斯正態(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)—目標(biāo)圖像的像素坐標(biāo);σ—高斯正態(tài)分布的方差。

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

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

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

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

圖2 DOG空間局部極值檢測

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

1.2 特征點(diǎn)定位

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

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

(4)

(5)

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

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

(6)

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

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

(7)

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

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

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

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

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

圖3 各方向梯度直方圖

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

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

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

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

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

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

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

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維歐式空間中的原點(diǎn)O(0,0,…0)作為參考點(diǎn)，計算出集合A2中所有的向量到原點(diǎn)的歐氏距離D(Vl,O)，并進(jìn)行升序或降序排列；保存起來在集合A3中，再計算出?Vi∈A1到原點(diǎn)O(0,0,…0)的歐氏距離d，根據(jù)設(shè)定的誤差檢索范圍e將查詢范圍確定在A3={Vl|Vl∈Rq,D(Vl,O)∈[d-e,d+e],i=1,2,…,l}中。再在集合A2中隨機(jī)選擇一個參考向量Vr，計算集合A2中所有的向量到參考向量Vr的夾角，并進(jìn)行升序或降序排列；保存起來在集合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,∈[θ-α,θ+α]}，在這個范圍，如果不存在特征向量，則認(rèn)為匹配失敗，無理想匹配點(diǎn)，如果存在且不止一個，此時分別計算它們之間的歐氏距離，找出最鄰近點(diǎn)，此時查詢出的最鄰近點(diǎn)的誤差在誤差范圍e以內(nèi)。

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

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

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

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

(4)輸入需要查詢的特征向量Vc，計算出其到原點(diǎn)的歐氏距離。由于在數(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)存在且不止一個，則分別計算出匹配向量與它們的歐氏距離，進(jìn)行單獨(dú)比較，歐式距離最小的特征向量，即可作為理想的正確特征向量保存，如果不存在則默認(rèn)要查詢的特征向量無正確的匹配向量。注意此時應(yīng)忽略查詢特征向量Vc本身計算出的夾角，無須比較。

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

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

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

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

3.1 性能評價標(biāo)準(zhǔn)

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

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

(3)計算速度。計算速度是指SIFT在進(jìn)行特征點(diǎn)的匹配時所耗費(fèi)的時間。

3.2 算法驗證

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

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

圖5 牛津大學(xué)VGG實驗室圖像測試

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

圖6 SIFT識別效果圖

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

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

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

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

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

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

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

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

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

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

3.3 結(jié)果分析

由圖(7～9)可看出：在查詢范圍參數(shù)不同的情況下，EVA算法和BBF算法的配準(zhǔn)率基本相同，正確匹配總數(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)進(jìn)行處理，然后通過比較查詢向量與所有向量之間的歐氏距離和夾角小于預(yù)先設(shè)定的某一閾值來進(jìn)行最鄰近查找，大大提高了特征點(diǎn)匹配效率。

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