基于SURF和RANSAC的改進目標識別算法

張龍，鄭燦

（河北工程大學 機械與裝備工程學院，河北 邯鄲 056038）

1 前言

工業機器人作為新興產業迅速發展并廣泛應用于制造業中，機器視覺技術使機器人具備更強的感知能力。目標識別、三維重建等作為機器視覺的一大分支，目前普遍應用在生活和工業領域。在工業生產中，機器人在抓取物體時，可能會受到遮擋、旋轉、傾斜、光照等因素干擾，影響目標識別和抓取準確率，為了實現機器人在復雜環境下能夠準確抓取，特征匹配和特征點篩選成為目標識別的關鍵環節。

近年普遍利用的特征匹配算法有SURF、SIFT和ORB算法。20世紀90年代，David Lowe提出SIFT算法，被普遍利用在圖像識別，圖像處理和三維重建等各個領域。SURF算法是對SIFT的優化，提出積分圖對海塞矩陣和盒子濾波器的使用，提升了運算效率。ORB算法雖然運算時間快，但不具有尺度不變性，在識別圖像穩定性方面較差。隨著機器視覺技術日益成熟，應用領域愈加廣泛，針對復雜圖像物體特征點過多，易出現誤匹配降低運算效率等情況，國內外學者提出了許多解決方法。Bay等提出了通過SURF算法用Fast-Hessian矩陣來提高檢測點的計算速度，但降低了匹配精度；施威格在保證特征點尺度不變性的前提下，提出了一種線性化的SURF特征識別分類器來改善特征點之間的差異，與原算法相比速度有所提高，但圖像調整范圍縮小了；陳天華為了提升識別精度，提出了雙向匹配方法，在反向選取閾值時需要不斷嘗試，若設置錯誤準確率反而會被降低；蔣凌志使用KMean聚類算法和RANSAC算法實現精確匹配，但該算法只適用于缺乏計算能力和資源的移動設備。

本文針對傳統SURF和RANSAC算法在圖像匹配中出現較多誤匹配點和迭代次數過多導致運算速度降低的問題，提出運用SURF算法獲取模板特征點，利用雙向歐式距離搜索相似度較高的對應點，通過海塞矩陣跡進行判斷，若兩個特征點矩陣跡正負號不同，表明變化方位相反，即使求出的歐氏距離為0也直接剔除，最后采用改進的RANSAC算法對已經匹配成功的像素點反向檢查，進行二次優化，縮短了參數的檢驗時間，同時，基于FLANN結合SURF算法，采用K-d樹存儲圖像中所有歐式距離匹配點，進行多層次劃分，尋找模板和目標圖像所有匹配對，自上而下依次篩選，最后通過勞氏算法求出最優化匹配點，實現物體的實時匹配。

2 SURF算法和RANSAC算法

2.1 特征點提取

SURF特征檢測算法通過Hessian矩陣進行二階微分計算，在離散空間內，尺度為σ的Hessian矩陣H(X,σ)在某像素點I(x,y)定義：

式中，Lxx(X,σ)為高斯二階偏導數在x處與I的卷積，Lyy(X,σ)，Lxx(X,σ)為g(σ)在y方向，x，y方向上與像素點I(x,y)的卷積，為了簡化計算，SURF算法中使用9×9的盒子模板來取代原來的高斯濾波與二階求導的過程，表達式為：

式中，ω為權值，一般取0.9。

對極值點進行如圖1所示的3×3×3非最大值抑制。為了實現亞像素級別定位，利用三維線性差值尋找亞像素特征點。

圖1 3×3×3非最大值抑制

2.2 主方向確定

以特征點為中心，6s(s為特征點尺度)為半徑，π/3角度大小的扇形區域為一個基本計量單位。統計計量單元的Haar小波特征，按照特征節點周圍與中心差異的明顯程度而賦不同權,最接近圓心處時權較大。對每個特征整體權重相加,累加值較大的扇形區域角平分線所在方位即為特征節點的主體方位,主位置選取方式如圖2所示。

圖2 主方向選取

2.3 特征點描述

主方向確定后，在邊長20s（s是尺度因子）的區域構建16個大小相等的子區域，統計16個區域中每個小區域25個像素的豎直和水平方向的haar小波特征，分別記為dy和dx，同時，計算dy和dx的累加絕對值，一共16×4=64維，進行歸一化處理后得出較好的效果，如圖3所示。

圖3 特征點描述

2.4 特征點匹配

計算2個n維向量特征點之間的歐氏距離，公式如下：

式中，n為特征向量維數，公式得出的值越小，說明特征點相似度越高，在特征點符合相似度要求時，同號匹配成功異號匹配失敗。根據公式（3）求解出模板圖上的特征點到目標圖中的特征點Xi的歐式最短距離為Dist(Xi,Yi)，同理，次短距離為Dist(Xi,Yi)。

將兩者進行比較：

再反向進行從目標圖到模板圖的匹配，最后將同時滿足兩個方向的匹配提取出來，將Xi,Yi作為歐式距離的特征點放入矩陣P1中，將次短距離特征點Xi,Yi’放入矩陣中P2，匹配特征點集為：

2.5 RANSAC原理

RANSAC的基本原理是：首先，在第一次匹配的結果中抽取部分匹配點，構造一個匹配點對的初級模型，將其余匹配點代入初始模型中進行運算，并將配對結果分成符合初始模型的與不符合初始模型的匹配點對，前者稱為有效數據，后者則稱為無效數據，而這些分離運算都是按照預先設置的閾值完成的。將所有失效數據全部去除，接著在所有有效數據內提取部分錯誤匹配對，形成新的模型，然后不斷分離所有有效數據，再繼續重復以上步驟，不斷迭代得到最優的預測模型。最后，再按照最優預測模型中的有效數據求取最新的參數模型，并利用該模型去除所有錯誤匹配對，優化匹配結果。

3 實驗結果與分析

本文實驗均在Visual Studio 2017+opencv4.5.1環境下進行編譯，為了驗證傳統算法和改進算法在目標識別準確率和運算效率方面的差距，設計了兩種工件在不同條件下的匹配識別實驗。

實驗一：設計外形相似的一對螺絲刀目標識別實驗，傳統SURF算法與改進算法的工件識別效果如圖4所示。

圖4 工件識別效果圖

記錄數據，如表1所示。

表1 兩種算法識別數據統計

從實驗圖片和表1的數據可以看出，斜線為誤匹配，傳統算法明顯有較多的誤匹配點，識別物體特征點明顯少于改進算法，而本文改進算法無明顯錯誤匹配點，匹配對數增多，匹配準確率為100，沒有受到旁邊物體的干擾，成功識別目標工件。

實驗二：設計螺釘在物體干擾、遮擋、旋轉條件下的目標識別實驗。圖5（a）為傳統算法的特征匹配結果，特征點匹配較為雜亂，有較多誤匹配對，圖5（b）為改進算法后的特征匹配，匹配效果得到很大改善，誤匹配點基本被消除。

圖5 兩種算法圖像匹配

圖6、圖7為螺釘在物體干擾、遮擋、旋轉條件下兩種算法識別結果。

圖6 傳統算法在不同條件下的識別效果

圖7 改進算法在不同條件下的識別效果

在實驗過程中，記錄了傳統算法和改進算法在不同情況下模板與目標圖像中特征點數目、匹配對數及匹配用時，識別數據如表2所示。

表2 兩種算法識別數據統計

由識別效果和表格數據可知：當圖像有較多干擾時，計算耗時相對較長，圖像特征點可以正確識別匹配；目標被遮擋時，雖然識別出遮擋物特征點但并未與模板匹配；工件旋轉時，目標圖像因為擺放角度比例縮小，仍能準確匹配，體現出算法尺度不變性的優點。從匹配對數和計算耗時來看，與原始算法相比，改進算法在目標識別精度和運算時間方面均有提升，能更好地滿足圖像匹配需求。

4 基于FLANN結合SURF算法的相機實時匹配

4.1 圖像算法設計

快速最近鄰搜索包FLANN（fast library for approximate nearest neighbors）由Muja和Lowe于2009年提出，是對大數據集進行最近鄰搜索算法的集合，目前經常用于物體特征檢測，匹配算法流程如圖8所示。

圖8 算法流程圖

FLANN搜索算法分為兩組特征集，第一組為訓練集，第二組為查詢集，訓練匹配器來優化cv::FlannBasedMatcher的性能，Train類創建特征集索引樹并優化參數以提高匹配精度。在n維實數向量空間pn中所有數據點通過多層隨機k-d Tree（k-dimensional樹的簡稱）方法進行不重疊的多層次劃分，判斷劃分點和目標點的坐標關系，若目標點小于切分點坐標，則移動到K-d樹的左子結點，否則為右。在查詢集鄰域范圍內搜索出距離查詢集最近的歐式距離，自上而下逐層遞進搜索，設置閾值指定遞歸遍歷的次數，若搜索到其他層次劃分區域內有距離目標點更近的點，則移動到這一結點，以此點為基準繼續進行搜索，直到全部搜索完畢。

4.2 勞氏算法

為了解決圖像中有其他因素干擾，提出了一種比較最近距離和最近鄰距離的方法：隨機選擇第一幅圖像的關鍵點，歐氏距離找到第二幅圖像最近的前兩個關鍵點，最近距離/次近距離＜r，(0＜r＜1)，r為人為設定的閾值，在本文實驗中取值0.6。

4.3 實驗過程與結果

確定模板圖像為特征豐富表面有文字圖案的口香糖盒，分辨率為647×337，設計了口香糖盒在翻轉、傾斜、遮擋、替換4種條件下的目標識別實驗，識別結果如圖9所示。

圖9 不同條件下的實時匹配

計算不同情況圖像特征點數目和匹配對數，結果如表3所示。

在圖9（a）中模板圖像與目標圖像中翻轉的口香糖盒匹配正確率高，手指、水管等干擾物體并未匹配；（b）圖中傾斜的口香糖盒上面有圖畫和文字干擾，匹配點較少，但精度未下降；（c）圖中遮擋和上面文字同樣沒有干擾與模板圖像的特征匹配；（d）圖能明顯看出口香糖盒與牛奶包裝瓶沒有特征點對應。結合表3得出結論：基于FLANN結合SURF的改進算法可以實現目標物體準確識別，穩定性較高，可用于工業現場多目標實時檢測。

表3 改進算法識別數據統計

5 結語

本文在傳統目標識別算法依賴Hessian矩陣和單向歐氏距離匹配的基礎上，提出了RANSAC算法篩選外點，反向匹配優化數據點。通過實驗對比，改進算法減少了部分雜亂特征點數量，提高了目標識別的準確率，加快了原始程序運算速度；同時，根據FLANN算法進行多維kd樹特征點匹配，利用勞氏算法優化，實驗結果表明，改進算法增強了匹配效果，在干擾下仍有較強的魯棒性，能保證工件在復雜環境下的實時匹配。