基于SURF算法的仿射矩陣估計

董哲，王翾

(中國傳媒大學(xué)廣播電視數(shù)字化教育部工程研究中心，北京 100024)

1 簡介

無人機的導(dǎo)航和機器人的自我定位是當今研究的熱點。當無人機在低空海拔飛行的時候，因為地理原因，還有一些直接或者間接的干擾，導(dǎo)致使用GPS來定位受到了很大的限制。因此，當沒有GPS信號的時候，UAV需要時不時的使用慣性導(dǎo)航來確定自己的位置，而慣性導(dǎo)航則經(jīng)常使用陀螺儀和加速器。在一定的場合內(nèi)，UAV的可以通過視覺搜索算法來完成自我定位。有很多方法可以用來解決自我定位的問題。方法主要分成兩類:基于標志物的定位［7－8］和基于圖像的定位［9］。在特定的場合，人工的標志物和自然的標志物可以用來估算拍攝的位置，因為這些標志物很容易被識別。然而，在其他非特定的場合［1］，標志物很難被確定。這時，就需要利用拍攝圖像的特征［3］來估算自我的位置。

提取圖像特征以后就需要匹配。通過將輸入圖像與實時捕獲的圖像進行匹配，可以利用匹配得到兩幅圖像的仿射變換矩陣，進而從矩陣中來恢復(fù)UAV的位置。到目前為止，有著諸如Harries角點檢測［5］，Canny 邊緣檢測［2］，SIFT 算法［10］，SURF 算法［6］，等檢測圖像特征的方法.但是Harries角點檢測，Canny 邊緣檢測在對旋轉(zhuǎn)的圖像時效果并不算很好。所以，SIFT和SURF算法比較適合用來檢測圖像特征點和構(gòu)建描述子。而SURF算法又由于高魯棒性和利用積分圖能減少計算的復(fù)雜度成為了本文所使用的圖像特征檢測方法。由于圖像不理想等原因，不可避免的會有一些匹配不理想的特征點，這些不理想的特征點會導(dǎo)致仿射矩陣的估計存在比較大的誤差。為了減少這些誤差，就需要使用RANSAC［4］來有效的減少估算仿射矩陣時的誤差，事實證明，此方法的確有效。

流程步驟如圖1所示。

圖1

2 SURF

2.1 SURF 算法

在各個局部特征檢測算法中，SURF算法可以使用積分圖來減少運算的復(fù)雜度。積分圖可以用I(i，j)來表示，是從左上角到右下角所組成矩形之內(nèi)的像素的總和，積分圖表達式如等式1，其中p(i'，j')代表矩形內(nèi)部的像素值。

SURF算法的目的是為了尋找那些有局部特征的興趣點，SURF使用海森矩陣在構(gòu)建的多尺度空間內(nèi)去尋找特征點，SURF在構(gòu)建尺度空間的時候，保持原始圖像不變，通過改變?yōu)V波器的大小，得到尺度空間。

SURF算法使用非極大值抑制來最終確定興趣點。興趣點的描述子采用64維的向量來描述，比SIFT的128維少了一半，因此會大大的加速匹配的速度。

2.2 匹配模塊

圖像之間的匹配對估計仿射矩陣啟著關(guān)鍵性的作用，特征匹配就是對于輸入圖像的每一個興趣點的描述子，都能在匹配圖像的描述子向量空間中尋找最相似的描述子向量。在這里可以使用Laplacian標示符(海森矩陣的跡)完成一次快速的匹配，SURF在為興趣點構(gòu)建的描述子的時候，會為每一個特征點添加Laplacian標示符，只有相同Laplacian標示符的符號的特征點會被保留，符號不相同的會被拋棄，這樣可以大大的減少運算量。對于剩下的特征點，使用歐氏距離來計算，歐氏距離如公式2所示，計算待匹配圖像的所有興趣點的描述子與輸入圖像某一興趣點的描述子的的歐氏距離，如果最小距離與次小距離的比值小于某一閾值，則認為這兩個點是準匹配的，閾值太大會導(dǎo)致有效匹配點減少，閾值太小會導(dǎo)致錯誤的匹配增多，在這里將閾值設(shè)置為0.7較為合適。最后，如果輸入圖像的興趣點與帶匹配圖像的興趣點匹配相互對應(yīng)，那么就將這兩個點視為一對匹配點。

3 估算仿射矩陣

輸入圖像和帶匹配圖像通過匹配點計算出來的仿射矩陣包含著豐富的位置信息。仿射矩陣反映了輸入圖像通過平移，旋轉(zhuǎn)，縮放變成待匹配圖像的一種過程。輸入圖像與仿射矩陣的乘積就是待匹配圖像，所以，如何由輸入圖像和帶匹配圖像得到仿射矩陣就是我們要解決的問題。

3.1 仿射矩陣模型

假設(shè)(X，Y)是輸入圖像的興趣點的坐標，(x，y)與對應(yīng)興趣點的匹配點的坐標，對于每一個點，則仿射矩陣模型可以描述為

對于圖像的所有興趣點，仿射矩陣應(yīng)滿足下列等式

只需要三對點我們就可以求出一個仿射矩陣，因為匹配點有若干對，所以我們可以求出很多的仿射矩陣，而仿射矩陣彼此之間可能存在較為大的誤差，如何求出誤差最小的仿射矩陣就是以下要解決的問題。

3.2 估算仿射矩陣

利用圖像的匹配點來進行矩陣估算可以有以下選擇，線性方法和魯棒算法，圖像之間的匹配較為理想的時候，也就是對應(yīng)點的特征一致性比較強，那么線性算法［11］，比如最小二乘法是一個不錯的選擇，因為線性算法足夠快，計算效率也比較高，但是由于圖像的成像質(zhì)量不理想，拍攝的角度問題，以及光線的影響，以及匹配算法的不確定性，導(dǎo)致圖像之間的匹配準確率下降，造成了一定數(shù)量的錯誤的匹配點，使用這些錯誤的匹配點計算出來的仿射矩陣會與真實的仿射矩陣有比較大的誤差，由于線性算法對于噪聲和錯誤匹配非常敏感，導(dǎo)致估計出來的矩陣十分不理想，使用這樣的矩陣得到的位置信息也就會有比較大的偏差。要想在有著較多誤差的匹配點中來計算出相對準確的仿射矩陣，就要想法找到符合大多數(shù)匹配點的仿射矩陣，如果存在這樣一個矩陣，如果一定的興趣點能通過這個矩陣計算出來匹配點都與真正的匹配點在可控的誤差范圍內(nèi)，可以使用歐氏距離來評估，這樣每一個特征匹配可以求出一個歸一化的估計誤差，最終得到一個估計誤差向量［11］，根據(jù)估計誤差向量確定一個誤差閾值，估計誤差向量中低于這個閾值的對應(yīng)的特征匹配為合理的匹配。并且符合矩陣的興趣點多于不符合矩陣的興趣點的話，就可以認為這樣的仿射矩陣是合理的。不斷地尋找可以匹配更多興趣點的仿射矩陣，最后就可以確定下來一個相對準確的仿射矩陣了。這樣的算法叫做魯棒性算法，最常見的魯棒性算法是RANSAC算法。

此流程如圖2所示。

圖2

RANSAC算法的步驟如下所示。

步驟一:對輸入圖像和待匹配圖像完成配準，記錄下來匹配點的坐標

步驟二:估算仿射模型，選取三對興趣點來計算出來一個仿射矩陣

步驟三:對于輸入圖像的所有興趣點，使用仿射矩陣完成仿射變換，計算出對應(yīng)的坐標，計算這些坐標和已知興趣點匹配點的坐標的歐氏距離，得到歸一化后的誤差向量。

步驟四:判斷誤差向量和閾值之間的關(guān)系，由此確定是否保留這個仿射模型

步驟五:統(tǒng)計符合條件的興趣點的個數(shù)，如果足夠多，即認為仿射矩陣時合理的

最后，不斷地重復(fù)步驟二到步驟五，總是保留符合條件興趣點最多的一個，最終得到我們想要的仿射矩陣。

4 實驗結(jié)果與分析

輸入的參考圖像

待匹配的圖像

兩幅圖像之間真實的仿射變換矩陣是:

測試幾種閾值下的匹配結(jié)果

海森閾值 歐氏距離閾值 RANSAC閾值288 0.18 8.7

圖5

海森閾值 歐氏距離閾值 RANSAC閾值632 0.28 8.7

圖6

海森閾值 歐氏距離閾值 RANSAC閾值460 0.45 8.7

圖7

經(jīng)過多次實驗，得到了較為豐富的特征點和仿射矩陣

設(shè)真實的仿射矩陣為

計算出來的仿射矩陣

計算兩者之間的誤差距離

可見誤差距離相當小，當誤差距離比較大的時候，就需要使用不同的閾值多次計算，直到找到符合條件的誤差距離。

最后可以根據(jù)仿射矩陣恢復(fù)位置參數(shù)，根據(jù)仿射矩陣模型

得到了旋轉(zhuǎn)，縮放，和平移的位置參數(shù)，cosθ=0.8，λx=λy=0.5，x0=59，y0=18。

5 結(jié)論

在本文中，我們首先回顧了SURF匹配算法，我們使用SURF來計算兩幅圖像之間的位置關(guān)系，在計算仿射變換的時候主要會遇到兩個問題，提高匹配的準確度以及如何減少估算仿射矩陣的誤差，在這里使用了拉普拉斯算子預(yù)匹配以及相互確認匹配的驗證的方法來提高匹配的準確度，使用RANSAC算法來減少仿射矩陣的誤差，剔除匹配不準確的點，還要調(diào)整匹配過程中的各種閾值達到滿意的效果，如何較為精準的確定閾值是我們以后要解決的問題。實驗結(jié)果證明，我們計算出來的仿射矩陣誤差較小，能夠較為精準的恢復(fù)出兩幅圖像的位置關(guān)系。

［1］Robertson D，Cipolla R.An image－ based system forurban navigation［C］.BMVC，2004.

［2］Canny J.A computational approach to edge detection［J］.IEEE PAMI，1986，8(6).

［3］Murillo A C，Guerrero J J，Sagues C.SURF features for efficient robot localization with omnidirectional images［C］.IEEE International Conference on Robotics and Automation，2007:3901 －3907.

［4］Fischler M，Bolles R.Random sample consensus:a paradigm for model fitting with application to image analysis and automated cartography［J］.Commun ACM，1981，24(6):381 －395.

［5］Olague Gustavo，Hernandez，Benjamin.A new accurate and flexible model based multi－corner detector for measurement and recognition［J］.Pattern Recognition Letters，2005，26(1)，27 －41.

［6］Bay H，Ess A，Tuytelaars T，et al.Speeded －up robust features(SURF)［J］.Computer Vision and Image Understanding，2008，7(3):346 －359.

［7］Caballero F，Merino L，F(xiàn)erruz J，Ollero A.Vision －Based Odometry and SLAM for Medium and High Altitude Flying UAVs［J］.J of Intelligent and Robotic Systems，2009，54(1 －3):137 －161.

［8］Bryson M，Sukkarieh S.Building a Robust Implementation of Bearing－only Inertial SLAM for a UAV［J］.J of Field Robotics，2007，24(1 － 2):113－143.

［9］Tola E，Lepetit V，F(xiàn)ua P.DAISY:An efficient dense descriptor applied to wide baseline stereo［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(5):815 －830.

［10］Lowe D G.Object recognition from local scale －invariant features［C］.Proceedings of the Seventh IEEE International Conference on Computer Vision，Los Alamitos，CA，USA，1999:1150 －7.

［11］甄艷，劉學(xué)軍，王美珍 .一種改進 RANSAC的基礎(chǔ)矩陣估計方法［J］.測繪通報，2014，(4):39－43.