基于改進SURF 算法的雙目視覺定位

韓 峰，李曉斌

(上海應用技術學院 電氣與電子工程學院，上海 201400)

為了滿足當今工業(yè)自動化不斷發(fā)展的需要，機器人應運成為了自動化進程中的寵兒，與之相關的機器人技術也得到了前所未有的發(fā)展和重視，機器人視覺定位作為其中的一個重要技術分支，其精準度的提高成為了研究人員們努力的目標和方向。雙目立體視覺定位因其具有較大的測量范圍和較高的測量精度，成為機器人視覺定位中最常用的一種方法。在雙目視覺定位中，對攝取的圖像上特征點的提取以及提取到的特征點之間能否正確匹配，這兩者決定著最終定位結果的精準度。SURF 算法是一種有效的特征點提取和匹配算法，它的高效率和高穩(wěn)定性能均超越了同類算法［1］，所以本文采用SURF 算法對攝取的圖像進行特征點的提取與匹配。由于SURF 算法本身存在的缺陷，在進行特征點匹配時容易產生特征點對的誤匹配現(xiàn)象，為了消除誤匹配，文中對SURF算法做了改進，加入了剔除誤匹配點對的RANSAC 算法。實驗結果表明，改進后的SURF 算法幾乎實現(xiàn)了零誤匹配，有效提高了雙目視覺定位的精準度。

1 SURF 算法

SURF 算法是由H.Bay 等人在SIFT 算法的基礎上，經過計算速度方面的改進，形成的一種快速特征提取與匹配算法［2］，該算法主要包括特征點的檢測、特征點的描述以及特征點的匹配三大部分。

1.1 特征點檢測

SURF 算法對特征點進行檢測時加入了Hessian 近似矩陣以及積分圖像［3］，這兩者的加入在一定程度上使計算速度得到了提高。積分圖像的定義如下:設X=(x，y)是所取圖像I(X)上的任意一個像素點，則積分圖像IΣ(X)就是取圖像的原點為左上頂點、點X=(x，y)為右下頂點所組成的矩形區(qū)域里面的所有像素累加之和

這樣，當把圖像轉換為積分圖像時，就可以在積分圖像內用一個簡單的公式來計算矩形區(qū)域里面的灰度值之和，即ε=A－B－C+D，其中的A，B，C，D 分別是矩形4 個角的頂點。

SURF 特征點檢測的依據(jù)是Hessian 近似矩陣行列式的局部極大值或者極小值所在位置。所取圖像I(X)中的任意一個點X=(x，y)在尺度大小為σ 上的Hessian 近似矩陣定義為

式中:Lxx(X，σ)表示的意思是高斯二階偏導在任意點X 處和所取圖像I(X)兩者之間的卷積，Lxy(X，σ)和Lyy(X，σ)具有相似的含義。為了提高整個過程的運算效率，Bay 等人將卷積結果用更簡單的Dxx、Dxy和Dyy來分別代替Lxx，Lxy，Lyy，于是得到了Hessian 近似矩陣的行列式，即

式中:w 是一個一般取值為0.9 的權重系數(shù)。按照上面計算Hessian 近似矩陣行列式的方法，對所攝取圖像上的任意點計算其響應并把結果保留下來，這樣就會得到大小各不相同的σ 下的響應結果。然后從所得到的結果中，再進行非最大值抑制操作，于是那些極值點就可以挑選出作為候選特征點。最后，為了確保所選的特征點是真正的特征點，利用文獻［4］中提出的3 維2 次函數(shù)擬合的方法，這種方法能夠有效地對特征點進行精確定位，從而獲取特征點的位置及不同大小尺度下的信息。

1.2 特征點描述

特征點描述的前提是對特征點進行主方向標定。以特征點為圓心做一定大小的圓形鄰域，在鄰域內，用Haar 小波模板對圖像進行處理，使其得到x 和y 各自方向上的Haar 小波響應，再用一定大小角度的圓心角的扇形繞選定的特征點轉一周，計算出該扇形處在任意一個角度時，圖像上所有點的Haar 小波響應矢量之和，并從中找出長度值最大的那個，則它對應的這個方向就是該特征點的主方向。確定好主方向以后，就可以在主方向上構建描述向量了。以選定的特征點為中心，以一定的長度為邊長做一個正方形鄰域，將確定了的特征點的主方向設為正方形鄰域y 軸的方向。將正方形鄰域劃分成多個子區(qū)域，用dx和dy表示每個子區(qū)域內x 軸、y 軸方向的Haar小波響應，并分別對每個子域內的求和，就會得到一個4 維向量，在對特征點進行提取時將會得到描述子特征向量，然后再對該向量進行歸一化處理操作，這樣，SURF 描述符就得到了。

1.3 特征點的匹配

設PA是所攝取圖像A 上的任意一點，PB是攝取圖像B上的任意一點，它們的描述子向量分別設為DA和DB。DA(i)和DB(i)分別是它們的第i 個分量，則PA和PB之間的距離為

按照式(4)進行計算，把A 圖上某點PA(i)與B 圖中的所有點之間的距離都計算一遍，然后再根據(jù)Lowe 在文獻［5］中使用的最近鄰比次近鄰的方法進行匹配點的求取。

2 SURF 匹配算法的改進

在文獻［6］中對SURF 算法所做的改進方法是一種基于圖像的形態(tài)學處理基礎的方法，該方法是通過對攝取圖像中的目標物體進行形態(tài)學方面的處理，得到目標物體的邊緣輪廓區(qū)域，然后再以邊緣輪廓區(qū)域為基礎建立積分圖像，最后再進行SURF 算法圖像匹配。這種改進算法雖然在一定程度上能夠提高SURF 特征點提取的效率，但因為加入了平滑處理、邊緣檢測、膨脹處理以及進行閉運算等過程，還是會使整個過程所消耗的時間較長，并且由于該改進算法對識別特征點的敏感度不是特別高，在進行圖像匹配的過程中也會少許存在特征點誤匹配的現(xiàn)象。

針對SURF 匹配算法中存在的誤匹配點對比較難剔除的問題，本文采用了加入用于剔除誤匹配點對的RANSAC 算法對其進行了改進。RANSAC 是目前廣泛應用于剔除誤匹配點對的一種算法［7］。該算法的基本思想就是:對某個點集，給定一個幾何約束模型，把符合這個約束模型的點作為所要尋找的內點保留，反之，不符合該約束模型的點作為外點剔除。在本文利用的算法程序的實現(xiàn)當中，加入的RANSAC 算法是基于一個基本矩陣幾何約束模型的，該基本矩陣是對極幾何的一種代數(shù)表示表達形式［8］。

圖1 中展示的是對極幾何的原理圖。在三維視覺系統(tǒng)中，O 和O’表示兩攝像機光心的位置，I1和I2表示兩攝像機采集的圖像，M 是三維空間中的任意一點，m 和m’分別是點M 在左右兩圖像中的投影點，點M、O 和O'三點所在的平面就是極平面，極平面與兩左右圖像之間的交線記為l1(me)、l2(m’e’)，所形成的這兩條直線叫作極線。從上面展示的原理圖中可以知道，m 點一定在極線l1上，而m’點也一定在極線l2上，所以m 點的對應點一定在圖像l2中的極線l2上。不論M 點怎么改變，所形成的極線都會過極點e 和e’，這就是極限約束，它的代數(shù)表示形式就是基本矩陣。在求取該基本矩陣時，本文采用的方法是簡單有效的8 點算法［9］，為了使利用的8 點算法估計出的基本矩陣精準度更高，在選取8個匹配點對之前，文中對SURF 提取的匹配點對集合中的點進行了坐標歸一化處理。最后在剔除不滿足條件的匹配點對時，使用了Sampson 距離判據(jù)法［10］。

圖1 對極幾何的原理圖

現(xiàn)將加入RANSAC 算法剔除SURF 誤匹配點對的整個改進算法的步驟總結如下:1)對利用原SURF 算法匹配出來的點對集合中的點進行坐標歸一化處理操作。2)從匹配點對集合中任意取出8 個匹配點對計算其基本矩陣。3)用Sampson 距離判據(jù)法，將符合條件的匹配點對作為內點記錄下來。4)重復2)、3)中的步驟n 次，并把每一次得到的符合條件的內點數(shù)記錄保存下來。5)從中挑選最大的內點數(shù)，并計算出該最大內點數(shù)對應的基本矩陣，再根據(jù)Sampson 距離判據(jù)法，把匹配點對集合中所有符合條件的點對找出，并把它們確定為最終的內點，而將不符合條件的匹配點對剔除掉。通過上面的5 個步驟，就可以完成加入了RANSAC 剔除誤匹配點對的改進SURF 算法。

利用原SURF 算法、經過圖像形態(tài)學處理改進后的SURF 算法以及加入了RANSAC 算法改進后的SURF 算法對圖像進行匹配，其對比結果如圖2、圖3、圖4 以及表1 所示。

圖2 原SURF 算法圖像匹配

圖3 經過圖像形態(tài)學處理改進后的SURF 算法圖像匹配

圖4 加入了RANSAC 算法改進后的SURF 算法圖像匹配

表1 SURF 及其改進后的匹配效果比較

從圖表中可以看出，加入RANSAC 算法后的SURF 算法，在對圖像進行匹配時，能有效剔除誤匹配點對，使匹配的正確率幾乎達到了100%，這就為后面雙目視覺定位中的圖像匹配提供了一個精準的算法環(huán)境。改進后的算法消耗的時間也比較少，都能夠滿足運算的實時性。

3 雙目立體視覺定位原理

雙目立體視覺定位的原理是，讓兩攝像機分別放在不同的位置，來獲取同一個目標物體存在有視覺差的兩幅圖像，然后利用視差原理［11］計算出目標物體的空間三維幾何信息，從而確定目標物體的空間位置。

圖5 是平行雙目立體視覺原理圖，兩攝像機投影中心點之間的距離是基線距，設為b。本文將兩攝像機鏡頭的光心所在的位置定為攝像機坐標系的原點。左右兩鏡頭的光心前f 處是左右兩成像平面，O1uv、O2uv 是兩圖像坐標系，它的縱橫坐標的方向與x 軸和y 軸方向一致，O1和O2是圖像坐標系的原點，p1(u1，v1)和p2(u2，v2)是任意空間點P 的左右圖像坐標點。兩攝像機的光心距離兩成像平面相同，則空間點P的左右兩圖像坐標的縱坐標Y 相同，即v1=v2，由幾何知識可以得到

式中:坐標(xc，yc，zc)是空間點P 在左攝像機坐標系中的坐標;b 為基線距;f 是焦距，則視差即為點P 在兩圖像中相應點的位置差

由此，空間點P 在左攝像機坐標系中的坐標可以計算得到為

圖5 平行雙目立體視覺原理圖

式中:zc=就是目標點P 的深度距離。在求取目標物體的三維坐標之前，要事先計算出攝像機的內外參數(shù)，然后再利用上面的公式就可以計算出目標物體的三維坐標，從而可以確定出該點的具體位置。

4 雙目視覺定位的實驗測定

實驗采用兩個型號為CM－323CDNP 的針孔攝像機，組成平行雙目視覺系統(tǒng)，兩攝像機的基線長為100 mm，CCD 芯片為1/3 in Sony CCD，靶面尺寸為寬4.8 mm×高3.6 mm，對角線的長度為6 mm，鏡頭的焦距f 為3.6 mm，獲取到的圖片大小為720×960 像素。

試驗中，把籃球作為目標物體。將目標物體的模板圖像分別與雙目攝像機所拍攝獲取的左右圖像，用加入了RANSAC 算法改進后的SURF 算法進行匹配，匹配結果如圖6、圖7 所示。從匹配圖中采集目標物體上的各個匹配點的坐標，然后對這些坐標求取平均值，所得的平均值就可以估計為目標物體在左右圖像上的中心坐標點。再利用平行雙目視覺原理中的式(5)、式(6)就可以計算出該點的深度距離，從而實現(xiàn)了對目標物體的定位。此次實驗，求取的目標物體在左右圖像上的中心坐標點分別是:(1 067，370)、(1 155，370)，通過計算得出目標物體的深度距離為509 mm，實際測量的距離是500 mm。然后在不同的實測距離下分別用SURF 算法、經過圖像形態(tài)學處理改進的SURF 算法以及加入了RANSAC算法改進的SURF 算法進行多組實驗，所得的結果如表2 所示，整個實驗基于的仿真軟件是MATLAB R2010a。

從表2 列出的結果中可以看出，基于經加入剔除誤匹配點的RANSAC 算法改進后的SURF 算法的雙目視覺定位更準確。但由于在雙目視覺標定過程以及在求取攝像機內部參數(shù)時會存在一定的誤差，再加上用匹配點對坐標的平均值來估計目標物體中心點坐標時存在的誤差，所以計算結果會存在一定的偏差。

圖6 目標物體與左圖像的匹配

圖7 目標物體與右圖像的匹配

表2 基于SURF 及其改進后的測距結果 mm

5 結論

在雙目視覺定位中，圖像匹配是最核心，也是最關鍵的一步，特征點能否正確匹配，將直接影響著定位的準確度。SURF 算法作為一種在同類算法中，各方面優(yōu)勢都比較突出的算法，被廣泛應用于圖像特征點的提取與匹配中。SURF算法能夠對絕大部分的特征點進行正確匹配，但由于客觀因素的影響，它會對那些特征不明顯的極少數(shù)特征點對產生誤匹配，影響定位的準確度。為了達到消除誤匹配的目的，文中對SURF 算法進行了改進，在原來算法的基礎上加入了消除誤匹配的RANSAC 算法。實驗結果表明，改進后的SURF 算法幾乎實現(xiàn)了零誤匹配的效果，提高了雙目視覺定位的準確度。

［1］HERBERT B，TINNE T，LUC V G.SURF:speeded up robust features［C］//Proc. 9th European Conference on Computer Vision.Graz，Austria:ECCV Press，2006:404－417.

［2］HERBERT B，ANDREAS E，TINNE T，et al. Speeded－Up Robust Features(SURF)［J］.Computer Vision and Image Understanding，2008，110(3):346－359.

［3］VIOLA P，JONES M.Rapid object detection using a boosted cascade of simple［C］//Proc. 2001 IEEE Computer Soeiety Conference on Computer Vision and Pattern Recognition. Kauai Marriott，Hawaii:IEEE Press，2001:511－518.

［4］BROWN M，LOWE D G.Invariant features from interest point groups［C］//Proc. British Machine Vision Conference，Cardiff，Wales，BMVC.［S.l.］:IEEE Press，2002:656－665.

［5］LOWE D G.Distinctive image features from scale－invariant key points［J］.International Journal of Computer Vision，2004，60(2):91－110.

［6］劉丹丹，魏維.一種改進的車頭SURF 特征提取和匹配［J］.成都信息工程學院學報，2014(2):167－172.

［7］FISCHLER M A，BOLLES R C.Random sample consensus:a paradigm for model fitting with applications to image analysis and automated cartography［J］.Communications of the ACM，1981，24(6):381－395.

［8］RICHARD H，ANDREW Z. Multiple view geometry in computer［M］.2nd ed.New York:Cambridge University Press，2003.

［9］HARTLEY R I.Estimation of relative camera position for uncalibrated cameras［C］//Proc.the 2nd European Conference on Computer Vision.Santa Margherita Ligure，Italy:ECCV，1992:579－587.

［10］YAN L W，ZHEN J M.Automatc panorama image mosaic and ghost e1iminating［C］//Proc.IEEE International Conference on Multimedia and Expo.Hannover，Germany:ICME，2008:112－115.

［11］高文，陳熙霖.計算機視覺—算法與系統(tǒng)原理［M］.北京:清華大學出版社，1999.