改進人工魚群的ORB特征匹配算法

李思璇，胡志剛，2，王新征，付東遼，祖向陽

1.河南科技大學醫學與技術工程學院，河南 洛陽 471003

2.河南省智能康復醫療機器人工程研究中心，河南 洛陽 471003

在視覺SLAM（simultaneous localization and mapping）[1]中前端（視覺里程計）為后端優化提供了所需的信息，信息精度直接影響后端優化效果與建圖軌跡的準確性，精度較高的特征匹配方法有助于準確定位與地圖構建。ORB（oriented FAST and rotated BRIEF）[2]是在FAST與BRIEF基礎上改進的一種含有方向的二進制描述方法，雖然在匹配精度上略遜于SURF 與SIFT 算法，但在實時性方面有著巨大優勢，因此在視覺SLAM中得到廣泛應用。近年來眾多學者為提升ORB匹配精度進行大量研究。在特征檢測方面，文獻[3]針對亮度變化明顯場景提出一種ORB 局部像素自適應分類方法，對特征點精準提取后結合PROSAC 算法有效降低了不同光強度下的誤匹配率。文獻[4]使用樹狀存儲結構，對圖像節點分割成多個子區域，根據子區域特征點數量進行均勻提取，這種方法有效地解決了特征點聚集冗余的問題，具有優良的圖像匹配能力。還有通過將多種算法征檢測與ORB結合以改進自身不具備尺度不變性問題并得到了可靠度較高的匹配結果[5-7]。有研究人員進行圖像目標分類檢測將K-means 聚類算法與ORB 結合[8]解決傳統特征匹配不能多目標匹配的問題。文獻[9]通過圖像語義分割，提取目標圖標區域生成詞袋模型，使用SVM 提升了圖像分類性能。在后端優化方面，文獻[10]將人工魚群應用在粒優子集合優化，重新調整粒子的提議分布，使估測粒子更符合實際狀態分布，提高了機器人的位姿估計精度。文獻[11]在視覺SLAM路徑規劃中通過引入聚集因子β與迭代次數共同影響自適應因子改善了人工魚群收斂精度，同時添加權重評價因子計算了人工魚當前位置的適應度值，改進算法有效的避免陷入局部解的問題并提高了最佳路徑的規劃速度。在眾多目標分類中K-means 聚類算法在類之間區別較為明顯時具有良好的分類性能，但過于依賴隨機選取的初始值，容易造成結果不穩定。目前較為成熟的SVM 分類核函及參數基本上都是根據經驗值設定，考慮在未知環境中核函數及參數應當按照實際場景來確定，動態滿足核函數與參數的設定目前較為復雜。人工魚群算法作為一種群體智能優化算法[12]，在組合優化問題中得到廣泛的應用，它的優點在于對初始值的要求不高，前期快速較快，個體之間獨立存在且獲得的信息輕便簡潔，使得算法在設計改進中上更加靈活，操作性更高。

在總結以上方法后發現現存方法中或多或少存在著特征點檢測彈性不足，未考慮實際的情況對特征點數量以及區域檢測進行過多控制，雖然部分圖分類效果良好但應用在實際環境中實時性尚未達到一定標準。

考慮人工魚群適合求解精度要求不高的尋優問題與大量特征點之間無需零差別描述匹配相互耦合，且人工魚群的聚群、追尾、自由行為對特征點選取起到了快速分類的效果，縮小匹配范圍，加大了不同區域之間特征點的描述差異，故本文采用改進人工魚群與ORB 特征匹配算法結合提高特征匹配正確率。改進算法分成兩個部分：（1）對于FAST 角點邊緣敏感不足的情況，提出FAST-16的角點彈性檢測方法，根據不同情況彈性的選擇角點圓周位置進行像素值對比；（2）使用自適應的魚群參數對人工魚群進行行為分析，在圖像中規劃聚群區域、追尾區域、自由區域，對人工魚群（即特征點）更加靈活的分類，最后分別使用漢明距離的篩選方法與RANSAC 算法進行特征匹配并將正確匹配率進行對比。實驗結果表明，改進后的ORB 算法匹配精度大幅提升，同時滿足室內輪椅定位與建圖實時性的需求，為室內輪椅定位與建圖的準確性做良好的鋪墊工作。

1 人工魚群與ORB算法的基本原理

1.1 人工魚群的行為描述

人工魚群算法[13]是對魚類不同行為歸納總結得出的一種優化方法，將魚群行為描述分為如下四種并概述一些基本定義，其中X=(x1,x2,…,xn)表示當前人工魚的位置，Y=f(x)表示尋求的目標函數，di,j=||Xi-Yj||表示個體與個體之間的相互距離，Visual表示以人工魚為中心的感知半徑，W表示聚集程度。

（1）覓食行為：Xi在Visual圓周內選擇任意一點新狀態Xj，若Yi

（4）隨機行為：作為其他情況的補充，人工魚在不滿足任何行為的時候在Visual圓周任意更新位置。

全局性公示板用于保存人工魚的最佳狀態，每次行為迭代后都會檢索其自身狀態，若優于最佳狀態，則將全局公示板更正為當前狀態。

1.2 ORB特征匹配原理

1.2.1 FAST特征點檢測

圖像中任意兩點像素P1、P2，構建灰度差值函數M=|IP1-IP2|。設強差異的闕值為T，若M>T，則認為這2個點具有強差異。考慮圓心像素點周圍以3為半徑的16 個像素點，如果這16 個像素點中有連續的n個強差異像素點，那么它就是一個特征點，如圖1所示。

圖1 FAST檢測原理圖Fig.1 Detection schematic of FAST

為了使特征點帶有方向描述[4]，首先定義圖像塊的矩函數Mpq如式（1）所示：

式（2）表示的是以r為半徑的鄰域S內質心位置C：

連接圖像塊的幾何中心O與質新C，得到式（3）中θ為特征點的方向：

1.2.2 特征點描述

普通BRIEF不具有方向旋轉的性質，通過上文計算出方向向量使BRIEF 具有良好的旋轉不變性。通過選取角點周圍隨機選取n個點對進行比較，并用0 與1 組合成描述子。每個BRIEF 描述子是一個長度為n的二進制數值碼串，并構成點對集合S，使用鄰域方向θ和對應的旋轉矩陣Rθ，構建S的一個校正版本Sθ，如式（4）所示：

其中θ為主方向，在求得的新點對中使用相互關聯性最低的一組點對集合，得到含有方向的描述子。

1.2.3 特征點匹配

特征匹配作為視覺里程計中極為關鍵的部分，匹配的好壞程度將決定后續優化模型的工作量大小，目前常用的有暴力匹配法（brute-force matcher），它使用的方法是在原始圖像中選取一個包含描述子的特征點，然后按照一定的順序與目標圖像中的特征點進行描述距離的比較，最后與距離描述最近的點進行匹配，同時本文參考了文獻中工程上的篩選方法，通過篩選將描述距離小于最小距離特定倍數的特征點進行匹配。RANSAC 算法[14]是在兩幅圖像中找到最佳單應性矩陣H（homography matrix），它表示的是同一物體，在不同視角下的矩陣轉換關系。此種算法具有良好的剔除誤匹配能力，抗噪能力強，適用于大部分場景的特征匹配。

2 改進人工魚群的ORB特征匹配算法

使用改進人工魚群算法與ORB特征匹配結合需要大量豐富的圖像特征點以便于通過魚群行為更好的對特征信息分類，減小匹配范圍，提高正確匹配率。為了得到更多的特征點，需要對圖像明顯分界處更加合理靈活的檢測，改進FAST 算法并未通過增加或減小圓周半徑r來提高靈敏度，而是對特征點達到一定條件后，對圓周不同方向上彈性選取像素位置進行像素值對比，然后根據檢測結果結合改進人工魚群具有并行計算、收斂速度快的特點，通過對特征點3 種魚群行為分析，將其分類成多個類間描述差異較大的特征區域，最后利用RANSAC算法進行特征匹配。

2.1 改進FAST特征點檢測

在實際特征點檢測中，FAST為了加快計算速度，在像素點以r為半徑的圓周上，全部像素點并未按照順時針方向比較，而是每間隔3個像素點取一個像素點與之進行對比（以3為半徑間隔3個位置，如位置1、5、7、9的像素點），若大于等于3 個同時屬于強差異的像素點則繼續檢測中間需要相連接的像素點。當至少連續9 個同時為強差異像素點則認為該點是特征點，雖然這種方法計算速度較快但同時由于用于依賴開始選擇固定的4個像素點，導致邊緣敏感不足，抗鋸齒能力不強。針對這種情況，改進后的FAST在選擇間隔為3的4個像素點中，若只存在2個同時屬于強差異的像素點則先考慮其他2 個非強差異像素點的邊緣與中心像素點是否存在強差異。如圖2（a）所示：若位置1 為非強差異像素點，則考慮位置1 的上下邊緣，若位置13 為非強差異像素點，則考慮位置13左右邊緣與中心像素強度差異關系，在這兩對邊緣中只要存在1 個強差異點即可認為滿足選擇的4個像素點中同時存在3個強差異像素點的初始要求，在邊緣檢測條件滿足后進行像素點的連續性檢測，到達至少9個像素點連續為強差異像素則認為它是一個特征點進行保留，反之則去除。圖2（b）為經過改進后的圓周檢測位置示例。

圖2 改進FAST檢測原理圖Fig.2 Detection schematic of improved FAST

確定角點后通過灰度質量心法計算出質心C與主方向θ，得到帶有方向的rBEIEF。改進FAST特征點檢測流程圖如圖3所示。

圖3 改進FAST特征點檢測流程圖Fig.3 Feature point detection flowchart of improved FAST

2.2 改進人工魚群的特征點選取

通常魚群聚集的地方往往是營養較為豐富的地方，基于此思想在特征點檢測中特征點較多的區域同樣圖像特征較為豐富，考慮K-means聚類方法[15]需要多次迭代并照顧全局每一個點，直到計算出一個或多個聚類中心，過于依賴初始點的位置，如圖4（a）所示，經過聚類算法的計算將圖像中的點分為上下兩類，距離聚類中心較遠的點同樣被考慮在計算范圍之內。本文通過上文改進的FAST提取，將當前特征點作為已收斂后的人工魚群，即圖像特征信息最優提取，通過改進人工魚群思想計算出一個或多個聚群區域，根據特征點相應的位置判斷其當前的狀態，對于未在聚群區域的特征點通過狀態判斷策略選擇保留或去除。每一個特征點位置對圖像整體計算影響較小，通過減小圖像特征區域外的相似描述提高匹配精度。圖4（b）為改進人工魚群的特征點分類原理圖。

圖4 分類類型示意圖Fig.4 Schematic diagram of classification types

下面是改進算法中包含的一些基本定義：SR（satisfactional research）代表區域認可度，FI（follow intensity）代表人工魚的追隨強度，Nmax為圖像中檢測到特征點的數量。

（3）自由狀態行為分析：如圖4（b）綠色點所示，不在聚群與追尾區域的人工魚將被認定為自由狀態Fd，考慮其不影響其他人工魚的條件下，將其去除。自由狀態的行為分析將圖像中某一局部區域單獨出現的特征點在不影響其他特征點聚類、描述圖像信息的情況下視為環境干擾產生的噪聲，故通過不同的行為分析后將其在圖像特征點中過濾消除。

2.3 特征點匹配

隨機一致性（random sample consensus，RANSAC）通過擬合參數模型高效的去除了大量誤匹配，該方法[16]可以在包含大量誤差超過閾值的數據集中分離出誤差在一定范圍內的優質參數。在實際情況中，RANSAC算法對于優質的模型會很快跳出迭代，節省大量計算時間。它的計算過程如下：

（1）從數據集合中，任意的抓取一定的參數生成擬合函數，并計算出最佳單應性矩陣H。

（2）設置一個誤差閾值T，計算其他未被選擇的點與模型的投影距離L，若L

（3）計算每個模型含有局內點的數量，通過迭代隨機生成的模型，直到局內點數目不再變化，并達到最大數量時停止采樣。

2.4 改進算法的總流程

改進算法的具體流程如圖5所示。

圖5 改進人工魚群的ORB特征匹配流程圖Fig.5 ORB feature matching flowchart of improved AFSA

首先針對特征點檢測能力不足的的情況，對FAST特征點圓周彈性位置的像素值進行對比然后提取特征點；接著通過改進人工魚，結合其速度快、輸入信息簡潔，算法設計方便等優點劃分特征區域，追尾區域，對特征點賦予不同狀態優化選取；最后使用RANSAC 算法計算出最佳擬合函數去除圖像中的誤匹配。

3 實驗結果與分析

3.1 改進FAST算法的實驗結果

本文實驗環境為Ubuntu 16.04，CPU 為i7-4510U，Opencv2.4.13，為了驗證改進算法的有效性，選擇公開數據集中bikes場景、light場景、graffiti場景，公開數據集的地址為http：//www.robots.ox.ac.uk/～vgg/research/affine/，同時選取了實際場景，對改進FAST 算法前后進行了效果圖的比較。在實際測試中過高的閾值使判斷條件過于嚴格，導致少量的特征點無法準確描述圖像信息，過低的閾值會導致特征點聚集在圖像某一處，大量重疊。本文在實驗中將閾值設置為（Threshold=50），在提取階段階段進行了非極大值抑制，實驗結果如圖6所示。

圖6 改進FAST效果對比圖Fig.6 Effect comparison diagram of improved FAST

通過觀察，圖6（a）左二摩托車車頭與車尾有大量重疊的特征點，每輛摩托車車胎、遮陽棚、門框均少量特征點。從圖6（b）可以發現，經過改進后的算法使得車胎處、門框處存在較多的特征點符合實際圖像的輪廓邊界，并無聚集重疊的特征點。根據圖6（c）所示，圖像樹葉、建筑物入口上方處，特征點過于密集，樓梯邊緣處也沒有有效檢測到特征點。如圖6（d）所示，在樹葉與樓體中檢測到了較多且均勻分布的特征點，對樓梯邊緣、白色汽車車體邊界處進行了高質量的特征點提取，對圖6（c）中存在的問題進行了有效的改善。從圖6（e）中可以很明顯的看到，在整個圖像中明顯分界處并沒有符合理想的特征點，而經過改進后的算法在圖6（f）中精準的對圖像中存在邊界的地方進行了特征提取，對圖像輪廓進一步詳細的描述。在實際環境中，從圖6（g）與6（h）可以發現改進算法更加精準的將暖氣片之間縫隙作為特征點提取出來符合理論的設計原理，對右下角辦工桌的邊緣使用特征點勾繪出來滿足物品實際的邊緣形狀，并對桌面物品的外形又有著進一步的精準描繪。從圖6（i）與6（j）對比中可以看出，改進算法對圖像下方的辦公椅提取出較多的特征點，并且對圖像上方的燈管處提取出與實際情況一致的特征點。這是由于傳統FAST嚴格要求對比像素的圓周位置導致特征提取并不理想，通過算法改進前后效果表明改進ORB的FAST算法，可以靈活有效地對不同情況的像素位置及時調整，更加均勻精準的突出圖像中存在的特征點，對于特征點圓周位置彈性范圍的灰度值對比檢測，可以有效地克服特征點對邊緣檢測的不敏感。

3.2 改進ORB特征匹配算法的實驗結果

在3.1 節中對ORB 的FAST 算法進行了改進，并在公開數據集中驗證了改進算法的有效性。本實驗模擬室內環境共采集了80 組室內圖片進行特征點匹配，選擇其中40 組匹配效果較為良好圖片作為樣本，計算了不同特征匹配算法的平均正確匹配率并測試了算法的穩定性即標準差，結果如表1所示。

根據表1 可知，傳統ORB 平均正確匹配率較低，并且標準差達到3.1%，匹配結果極不穩定。通過使用篩選匹配或RANSAC 匹配策略與傳統ORB 結合，不需要額外消耗更多的匹配時間便可以將平均正確匹配率小幅度提升15.4%～29.5%，將標準差降低0.4%～0.8%，雖然改善了匹配效果與穩定性但并未達到理想正確匹配率。優化ORB算法與篩選匹配結合在匹配精度方面較傳統ORB 提高了39.2%，經過優化后的ORB 算法明顯比傳統ORB 匹配效果提升一個數量級并且降低了正確匹配率標準差至2.0%，但依然不滿足理想的正確匹配率。最后，通過改進人工魚群的ORB 優化算法與RANSAC匹配結合，在平均消耗時間上比優化ORB+篩選匹配多2.32 ms，在滿足實時檢測的要求下平均正確匹配率與標準差分別達到92.7%、1.3%，結果相對穩定，與傳統ORB 相比匹配精度提升了117%，標準差降低1.8%，符合理想的正確匹配率與穩定性。

表1 匹配結果對比Table 1 Comparison of matching results

下面給出在實際環境中與公開數據集中配精度效果較好的四組圖片加以說明，第一組如圖7所示。其中圖（a）為初始圖像，圖（b）、（c）、（d）、（e）、（f）分別對應傳統ORB 特征匹配、傳統ORB+篩選特征匹配、傳統ORB+RANSAC匹配、優化ORB+篩選匹配、優化ORB+RANSAC匹配5種實驗的結果。

圖7 改進ORB特征匹配效果圖Fig.7 Feature matching effect diagram of improved ORB

從圖7（b）中可以觀察到由于傳統ORB使用暴力匹配法，圖像中存在大量誤匹配，使得匹配精度極低。在圖7（c）與7（d）中可以觀測到雖然使用了兩種不同的特征匹配策略，雖然在匹配精度上小幅度的改善了誤匹配率，但由于圖像特征點在提取的過程中并未提取出質量較高的特征點，并且是對全局相似特征點進行對比匹配，導致原始圖像左側的特征點在目標圖像上發生了誤匹配，產生并不理想的匹配效果。觀察圖7（e）與7（f）中可以發現，優化ORB 與RANSAC 匹配算法的結合正確匹配率高于ORB 與篩選匹配的結合，同時對于目標圖像缺少初始圖像左側的部分，并在該部分產生大量特征點，目的是檢測兩張圖像經過改進人工魚群劃分特征區域后，區域內的特征點是否會像去除的特征點一樣干擾匹配。通過實驗表明，RANSAC 匹配算法雖然會帶來迭代計算，由于優化ORB 算法通過劃分特征區域大大縮小了匹配范圍，彌補了RANSAC計算量大的劣勢，并且在特征區域內特征點之間不會產生強烈干擾，降低特征點由于隨機相似的特征描述引起的誤匹配。

如圖8所示，為樣本中兩組不同場景的傳統ORB特征匹配與改進算法的效果對比圖。圖（a）、（b）、（c）、（d）兩組實際效果對比圖選擇的場景分別是正常光線的室內、與光線較暗的走廊，通過效果對比圖可以看出經過改進人工魚群的ORB特征匹配算法在較亮或較暗的環境中都具有較好匹配效，圖（e）、（f）是選用公開數據集中的graffiti場景通過偏轉一定角度來進行特征匹配，從圖8（e）中可以看出偏轉后的圖像特征匹配較為混亂，具有較高的誤匹配率，使用改進的特征匹配算法通過對圖像的位置信息分類，縮小匹配范圍，有效地降低了誤匹配率，即使在圖片偏轉一定角度的情況下仍然具有一定的魯棒性，改進算法具有較高的穩定性與正確匹配率。

圖8 不同場景改進算法對比圖Fig.8 Comparison diagram of improved algorithms for different scenes

3.3 改進算法總結

根據實驗結果得出改進人工魚群的圖像信息分類擴大了不同特征區域特征點之間的描述差異，使得室內物品雜亂較多的情況下具有較好的分類匹配效果，同時針對室內環境光照強度的不同，具備較好穩定性以及良好特征匹配性能，降低了實際環境中誤匹配率。改進算法為室內環境中的輪椅導航與建圖提供了良好的前端信息，為后續工作關鍵幀的確定做好準備。

4 結論

本文針對室內輪椅定位與地圖構建中提高視覺里程計ORB特征匹配正確率的要求。首先根據不同條件對ORB中FAST彈性選取邊緣位置后進行像素值對比，經過檢測后提取出特征點并計算方向與描述子，然后通過改進人工魚群的ORB特征選取策略對特征點劃分特征區域并根據其位置賦予不同狀態，最后結合RANSAC匹配算法，對傳統ORB 算法進行了優化。通過改進前后的ORB 算法對公開數據集與實際場景實驗效果對比，結果表明改進FAST 算法可以在圖像邊緣處檢測到更多的特征點，基于人工魚群的ORB 算法平均正確匹配率可以達到92.7%，穩定性較高。該算法對于室內環境具較高的正確匹配率，環境適應能力強，為后續工作室內輪椅定位與地圖構建做好了充分準備。