基于SURF和RANSAC的改進(jìn)目標(biāo)識別算法

張龍，鄭燦

（河北工程大學(xué) 機(jī)械與裝備工程學(xué)院，河北 邯鄲 056038）

1 前言

工業(yè)機(jī)器人作為新興產(chǎn)業(yè)迅速發(fā)展并廣泛應(yīng)用于制造業(yè)中，機(jī)器視覺技術(shù)使機(jī)器人具備更強(qiáng)的感知能力。目標(biāo)識別、三維重建等作為機(jī)器視覺的一大分支，目前普遍應(yīng)用在生活和工業(yè)領(lǐng)域。在工業(yè)生產(chǎn)中，機(jī)器人在抓取物體時，可能會受到遮擋、旋轉(zhuǎn)、傾斜、光照等因素干擾，影響目標(biāo)識別和抓取準(zhǔn)確率，為了實(shí)現(xiàn)機(jī)器人在復(fù)雜環(huán)境下能夠準(zhǔn)確抓取，特征匹配和特征點(diǎn)篩選成為目標(biāo)識別的關(guān)鍵環(huán)節(jié)。

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

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

2 SURF算法和RANSAC算法

2.1 特征點(diǎn)提取

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

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

式中，ω為權(quán)值，一般取0.9。

對極值點(diǎn)進(jìn)行如圖1所示的3×3×3非最大值抑制。為了實(shí)現(xiàn)亞像素級別定位，利用三維線性差值尋找亞像素特征點(diǎn)。

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

2.2 主方向確定

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

圖2 主方向選取

2.3 特征點(diǎn)描述

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

圖3 特征點(diǎn)描述

2.4 特征點(diǎn)匹配

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

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

將兩者進(jìn)行比較：

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

2.5 RANSAC原理

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

3 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)均在Visual Studio 2017+opencv4.5.1環(huán)境下進(jìn)行編譯，為了驗(yàn)證傳統(tǒng)算法和改進(jìn)算法在目標(biāo)識別準(zhǔn)確率和運(yùn)算效率方面的差距，設(shè)計了兩種工件在不同條件下的匹配識別實(shí)驗(yàn)。

實(shí)驗(yàn)一：設(shè)計外形相似的一對螺絲刀目標(biāo)識別實(shí)驗(yàn)，傳統(tǒng)SURF算法與改進(jìn)算法的工件識別效果如圖4所示。

圖4 工件識別效果圖

記錄數(shù)據(jù)，如表1所示。

表1 兩種算法識別數(shù)據(jù)統(tǒng)計

從實(shí)驗(yàn)圖片和表1的數(shù)據(jù)可以看出，斜線為誤匹配，傳統(tǒng)算法明顯有較多的誤匹配點(diǎn)，識別物體特征點(diǎn)明顯少于改進(jìn)算法，而本文改進(jìn)算法無明顯錯誤匹配點(diǎn)，匹配對數(shù)增多，匹配準(zhǔn)確率為100，沒有受到旁邊物體的干擾，成功識別目標(biāo)工件。

實(shí)驗(yàn)二：設(shè)計螺釘在物體干擾、遮擋、旋轉(zhuǎn)條件下的目標(biāo)識別實(shí)驗(yàn)。圖5（a）為傳統(tǒng)算法的特征匹配結(jié)果，特征點(diǎn)匹配較為雜亂，有較多誤匹配對，圖5（b）為改進(jìn)算法后的特征匹配，匹配效果得到很大改善，誤匹配點(diǎn)基本被消除。

圖5 兩種算法圖像匹配

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

圖6 傳統(tǒng)算法在不同條件下的識別效果

圖7 改進(jìn)算法在不同條件下的識別效果

在實(shí)驗(yàn)過程中，記錄了傳統(tǒng)算法和改進(jìn)算法在不同情況下模板與目標(biāo)圖像中特征點(diǎn)數(shù)目、匹配對數(shù)及匹配用時，識別數(shù)據(jù)如表2所示。

表2 兩種算法識別數(shù)據(jù)統(tǒng)計

由識別效果和表格數(shù)據(jù)可知：當(dāng)圖像有較多干擾時，計算耗時相對較長，圖像特征點(diǎn)可以正確識別匹配；目標(biāo)被遮擋時，雖然識別出遮擋物特征點(diǎn)但并未與模板匹配；工件旋轉(zhuǎn)時，目標(biāo)圖像因?yàn)閿[放角度比例縮小，仍能準(zhǔn)確匹配，體現(xiàn)出算法尺度不變性的優(yōu)點(diǎn)。從匹配對數(shù)和計算耗時來看，與原始算法相比，改進(jìn)算法在目標(biāo)識別精度和運(yùn)算時間方面均有提升，能更好地滿足圖像匹配需求。

4 基于FLANN結(jié)合SURF算法的相機(jī)實(shí)時匹配

4.1 圖像算法設(shè)計

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

圖8 算法流程圖

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

4.2 勞氏算法

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

4.3 實(shí)驗(yàn)過程與結(jié)果

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

圖9 不同條件下的實(shí)時匹配

計算不同情況圖像特征點(diǎn)數(shù)目和匹配對數(shù)，結(jié)果如表3所示。

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

表3 改進(jìn)算法識別數(shù)據(jù)統(tǒng)計

5 結(jié)語

本文在傳統(tǒng)目標(biāo)識別算法依賴Hessian矩陣和單向歐氏距離匹配的基礎(chǔ)上，提出了RANSAC算法篩選外點(diǎn)，反向匹配優(yōu)化數(shù)據(jù)點(diǎn)。通過實(shí)驗(yàn)對比，改進(jìn)算法減少了部分雜亂特征點(diǎn)數(shù)量，提高了目標(biāo)識別的準(zhǔn)確率，加快了原始程序運(yùn)算速度；同時，根據(jù)FLANN算法進(jìn)行多維kd樹特征點(diǎn)匹配，利用勞氏算法優(yōu)化，實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法增強(qiáng)了匹配效果，在干擾下仍有較強(qiáng)的魯棒性，能保證工件在復(fù)雜環(huán)境下的實(shí)時匹配。