基于改進KD樹與RANSC算法的目標識別算法

岑麗

（中國航發控制系統研究所江蘇無錫214063）

無人機（Unmanned）Aerial Vehicle，UAV）作為無人機駕駛的航空飛行器，近年來不管在軍用，或者是民用上，都得到了廣泛的發展。而在此過程中，無人機的功能性或多或少會依賴于其搭載的攝像機，正是實時圖像的獲取使得無人機能完成各種任務，例如目標跟蹤、測繪測量和偵查打擊等[1]。攝像機只是充當了信息采集的工作，真正的處理工作其實是由計算機完成。因此，計算機視覺技術的應用正是無人機得到快速發展的一大要素。

在無人機的任務中，涉及到的計算機視覺技術，無外乎去除噪聲、目標識別、目標定位以及目標跟蹤等[2]，本文主要針對無人機上廣泛應用到的目標識別技術進行研究。

目標識別就是指從一副（或多副）圖像中找出與給定目標圖像相似的圖像區域的過程。通常將已知的目標圖像稱為模板圖像，將待查找圖像稱為目標圖像。由于在無人機任務過程中，算法必須能適應工作環境、光照、視野角度等對目標圖像的影響，基于以上考慮，本文論述的目標識別技術主要是依據特征點的識別。特征點具有比例尺度不變等諸多優勢[3]。特征點算法繁多，較為常用的有SIFT、SURF、Haar和 FAST等，其中 SIFT（Scale-Invariant Feature Transform）算法是由Lower等人提出的一種圖像比例不變特征提取方法，該方法是在尺度空間中搜尋極值來獲取特征點的位置、旋轉、尺度不變量，因此算法的魯棒性較強[4]。在完成特征點提取之后，需要進行的是模板圖像特征點與目標圖像特征點的識別匹配，以此找出目標所處區域，對于該過程，本文主要分為兩個步驟：粗匹配和精匹配[5]。其中粗匹配采用的是改進KD樹（K維搜索樹）匹配算法[6]，該算法具有匹配速度快的特點。在本階段將過濾到大部分噪聲特征點，但還無法做到特征點的一一對應，可能會出現一對多的匹配關系。精匹配采用的是RANSC（Random Sample Consensus，隨機抽樣一致）算法，該算法由Fischler和Bolles于1981年提出，在精匹配階段能剔除絕大部分誤匹配點。

1 SIFT特征點提取過程

定義L(x,y,σ)為圖像I(x,y)的尺度函數[7]：

其中*表示卷積，G(x,y,σ)表示一個尺度可變的高斯函數：

其中，(x,y)表示空間坐標；σ為尺度坐標，表示圖像的平滑程度。

在高斯差分DoG（Difference of Gaussian）尺度空間中尋找極值點，則有：

為了讓算子擁有旋轉不變性，設置方向參數為：

上式表示的分別是(x,y)處的梯度數值m(x,y)和角度方向θ(x,y)，其中L選用的是每個關鍵點各自所在的尺度[8]。

圖1表示的用SIFT算法生成的模板圖像與目標圖像的特征向量。

圖1 SIFT特征向量圖

2 改進KD樹粗匹配

2.1 KD樹

KD樹是一種二叉樹，是把二叉搜索樹推廣到多維數據的一種主存數據結構，由Bentley于1975年剔除[9]。其與二叉樹的不同之處在于，其節點表示的是K維空間中的一個點，且樹的每一層都是依據該層分辨器做出的分支決策。

原來的KD樹匹配算法，采樣的是最臨近點查找法，該算法采用深度優先啟發式搜索策略。首先需要定義超矩形（hyper-rectangle）hr與以目標點t為中心半徑為r的超球體相交，求出hr中與圓心最經的點P，點P由下式計算：

其中Pi和ti表示點P和目標點t在第i維上的取值分別表示超矩形在第i維上的最小值和最大值[10]。

若p與t歐式距離小于半徑r，則兩者相交。此法需要首先比較目標點與KD樹節點的距離，再根據目標點在節點維數上取值來決定左右樹查找。

本法在樣本點維數過多時，容易對特征點進行錯分，導致無法匹配到最近的特征點。因此需要進行算法該進。

2.2 改進的KD樹匹配算法

基于識別精度的考量，對KD樹的匹配算法進行了如下改進[11]：

1）對分割維數按一定優先級排序，排序標準是維數之間的相關性，這樣的做法可以使得對其他維數影響較大的排在前面。

2）當發現某個維數下的樣本數過少是，則直接遍歷余下點。

根據樣本數據集特點，可對維數優先級進行分析，這里的優先級是以樣本集中維數之間的相關性作為準則的。實際應用中，使用主成分分析做優先級依據。

主成分分析[12]是對多變量數據進行統計處理的一種數據線性投影的方法。它能夠將高維空間樣本映射到低位主成分空間上，同時又能保留原有信息不丟失。

對于大小為M，以N維的梯度信息來描述特征點的樣本集E。通過以下步驟，計算出主成分奉獻率。

令

計算相關矩陣R=r(i,j)，

計算主成分奉獻率：

按照Ci得到數組D[n]，它根據主成分奉獻率從大到小存儲特征點維數。在得到D[n]后，構造樹時，需要添加節點權值。首先需要按維數優先級排序好的D[n]中的維數順序構造KD樹。

建立好改進的KD樹之后，統計出到達某葉子節點的樣本數占總樣本百分比，記為該節點的樣本節點權值q。然后對樹進行后序遍歷，使得q=qr+ql，其中qr表示該節點右子樹概率，ql表示該節點左子樹概率。

在查找時，只需要增加節點權值的驗證即可，即做閾值判斷。

下面兩張圖分別表示使用改進KD樹匹配算法的匹配效果前后對比。可以很明顯的看出使用改進KD樹算法比改進前的KD樹，產生更少的匹配點。盡管如此，由于某些應用環境對目標識別效果的要求較高，因此需要在改進后的KD樹匹配算法下再進行下一步的精匹配。

圖2 改進前后KD樹匹配效果圖

3 RANSC精匹配

RANSC算法是根據一組包含異常數據的樣本數據集，計算出數據的數學模型參數，得到有效樣本數據的算法。這種算法的基本假設是樣本中包含正確數據（適應模型的數據），也包含異常數據（不適應模型的數據）。而且給定一組正確的數據，存在可以計算出符合這些數據的模型參數的方法[13]。

以經過KD樹匹配的特征點作為樣本數據集。在考慮平移、旋轉和尺度變化的影響下，以模板圖像中兩角點間的距離與目標圖像中對應兩角點間的距離之比作為需要確定的數學模型[14-15]。

主要的精匹配過程如下：

1）在模板圖像和目標圖像的粗匹配點中隨機選擇兩組特征點（Up1，Down1）和（Up2，Down2），并將兩個點組計入當前模型的數據點集合this_consensus_set中；Up表示模板圖像特征點，Down表示目標圖像特征點；

2）建立本次計算的模型參數Model=

3）遍歷除了1）中選出的兩組點以外的其他點組，并計算每對點組 i（Upi，Downi）與 1）中兩個點組之間的偽模型值若Model1與Model2與Model之間的偏差同時小于模型閾值dt，則認為點組i匹配正確，計入當前模型的數據點集合this_consensus_set中。

4）若最終this_consensus_set的數據個數set_num超過閾值st，則進入5）;否則，計算次數iterations加1，并返回步驟1）。

5）計算模型偏差this_error；

以this_consensus_set為計算集合，遍歷所有點組，計算每一點組與其他點組的偽模型值與當前模型參數的偏差，并將所有偏差相加開方，即可得到this_error。

6）若 this_error小于模型偏差閾值 best_error，則認為匹配完成，認為this_consensus_set中的匹配點組即為最終的匹配結果。否則，計算次數iterations加1，并返回步驟1）。

圖3是在改進KD樹粗匹配的基礎上再使用RANSC算法完成精匹配的結果，可以看出經RANSC算法后，本次匹配剔除了所有的誤匹配點，匹配效果較好。同時仔細觀察可以發現，模板圖像在目標圖像中有不僅存在尺度變化、同時還有旋轉變化，但算法的實現將二者的影響都成功消除了。

圖3 采用RANSC精匹配效果圖

4 結論

文中通過分析圖像識別算法在無人機上的應用環境，確定使用SIFT特征點作為基本算子，然后將識別過程分為粗匹配和精匹配兩個過程，其中的粗匹配擬采用KD樹匹配算法，但因其在實際使用中出現大量錯分情況，因此進行了算法改進，改進后的KD樹[16-17]匹配所產生的無匹配點明顯減少。為了能夠得到更好的匹配效果，在改進KD樹匹配后，采用RANSC精匹配算法，完成最后的匹配，通過實驗可以看出，采用基于改進KD樹和RANSC算法的匹配效果較好，誤匹配點基本剔除。

[1]黃敦華，朱青松.基于微小型四旋翼飛行器的目標監測與識別綜述[J].機電產品開發與創新，2011，24（6）：16-18.

[2]張志飛.小型無人直升機視覺定位與跟蹤系統的設計與研究[D].杭州：浙江大學，2013.

[3]息朝健，郭三學.基于簡化Forstner算子改進的SIFT無人機圖像識別算法[J].計算機應用于軟件，2012，29（5）：254-256.

[4]鄭剛.基于特征的圖像匹配算法研究[D].長沙：國防科學技術大學研究生院，2011.

[5]韋東興，陳曉云，徐榮聰.基于角點檢測的圖像形狀特征提取方法[J].計算機工程，2010，36（4）：220-222.

[6]王淵民.基于SIFT算法的圖像快速匹配系統設計[D].成都：成都理工大學，2014.

[7]湯伯超.基于SIFT算法的圖像特征描述方法研究[D].廣州：廣東工業大學，2012.

[8]朱瑋.基于視覺的四旋翼飛行器目標識別及跟蹤[D].南京：南京航空航天大學，2011.

[9]杜振鵬，李德華.基于KD-Tree搜索和SURF特征的圖像匹配算法研究[J].計算機與數學工程.2012，40（2）：96-98.

[10]楊晶東，楊敬輝，洪炳镕.移動機器人視覺圖像特征提取與匹配算法[J].計算機應用研究，2009，26（9）：3526-3529.

[11]熊云艷，毛宜軍，閔華清.有序的KD-tree在圖像特征匹配上的應用[J].化工自動化及儀表，2010，37（10）：84-87.

[12]馬莉，韓燮.主成分分析法（PCA）在SIFT匹配算法中的應用[J].電視技術，2012，36（1）：129-132.

[13]張勇，余建平，孫軍偉，等.基于Harris的角點匹配算法研究[J].計算機與現代化，2011（11）：78-81.

[14]楊健，李若楠，黃晨陽，等.基于局部顯著邊緣特征的快速圖像配準算法[J].計算機應用，2014，34（1）：149-153.

[15]劉如飛，盧秀山，劉冰，等.一種改進的無人機航攝影像快速拼接方法[J].測繪通報，2014（2）：46-49.

[16]鄒艷榮，鄭政.一種用于高頻超聲探頭的掃描電機及控制系統[J].電子科技，2016（10）：111-114.

[17]汪立，蔣念平.基于改進Harris角點檢測的視網膜圖像配準[J].電子科技，2017（2）：119-122.

[16]鄒艷榮，鄭政.一種用于高頻超聲探頭的掃描電機及控制系統[J].電子科技，2016（10）：111-114.

[17]汪立，蔣念平.基于改進Harris角點檢測的視網膜圖像配準[J].電子科技，2017（2）：119-122.