基于改進(jìn)KD樹與RANSC算法的目標(biāo)識別算法

岑麗

（中國航發(fā)控制系統(tǒng)研究所江蘇無錫214063）

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

在無人機(jī)的任務(wù)中，涉及到的計(jì)算機(jī)視覺技術(shù)，無外乎去除噪聲、目標(biāo)識別、目標(biāo)定位以及目標(biāo)跟蹤等[2]，本文主要針對無人機(jī)上廣泛應(yīng)用到的目標(biāo)識別技術(shù)進(jìn)行研究。

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

1 SIFT特征點(diǎn)提取過程

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

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

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

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

為了讓算子擁有旋轉(zhuǎn)不變性，設(shè)置方向參數(shù)為：

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

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

圖1 SIFT特征向量圖

2 改進(jìn)KD樹粗匹配

2.1 KD樹

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

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

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

若p與t歐式距離小于半徑r，則兩者相交。此法需要首先比較目標(biāo)點(diǎn)與KD樹節(jié)點(diǎn)的距離，再根據(jù)目標(biāo)點(diǎn)在節(jié)點(diǎn)維數(shù)上取值來決定左右樹查找。

本法在樣本點(diǎn)維數(shù)過多時(shí)，容易對特征點(diǎn)進(jìn)行錯(cuò)分，導(dǎo)致無法匹配到最近的特征點(diǎn)。因此需要進(jìn)行算法該進(jìn)。

2.2 改進(jìn)的KD樹匹配算法

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

1）對分割維數(shù)按一定優(yōu)先級排序，排序標(biāo)準(zhǔn)是維數(shù)之間的相關(guān)性，這樣的做法可以使得對其他維數(shù)影響較大的排在前面。

2）當(dāng)發(fā)現(xiàn)某個(gè)維數(shù)下的樣本數(shù)過少是，則直接遍歷余下點(diǎn)。

根據(jù)樣本數(shù)據(jù)集特點(diǎn)，可對維數(shù)優(yōu)先級進(jìn)行分析，這里的優(yōu)先級是以樣本集中維數(shù)之間的相關(guān)性作為準(zhǔn)則的。實(shí)際應(yīng)用中，使用主成分分析做優(yōu)先級依據(jù)。

主成分分析[12]是對多變量數(shù)據(jù)進(jìn)行統(tǒng)計(jì)處理的一種數(shù)據(jù)線性投影的方法。它能夠?qū)⒏呔S空間樣本映射到低位主成分空間上，同時(shí)又能保留原有信息不丟失。

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

令

計(jì)算相關(guān)矩陣R=r(i,j)，

計(jì)算主成分奉獻(xiàn)率：

按照Ci得到數(shù)組D[n]，它根據(jù)主成分奉獻(xiàn)率從大到小存儲特征點(diǎn)維數(shù)。在得到D[n]后，構(gòu)造樹時(shí)，需要添加節(jié)點(diǎn)權(quán)值。首先需要按維數(shù)優(yōu)先級排序好的D[n]中的維數(shù)順序構(gòu)造KD樹。

建立好改進(jìn)的KD樹之后，統(tǒng)計(jì)出到達(dá)某葉子節(jié)點(diǎn)的樣本數(shù)占總樣本百分比，記為該節(jié)點(diǎn)的樣本節(jié)點(diǎn)權(quán)值q。然后對樹進(jìn)行后序遍歷，使得q=qr+ql，其中qr表示該節(jié)點(diǎn)右子樹概率，ql表示該節(jié)點(diǎn)左子樹概率。

在查找時(shí)，只需要增加節(jié)點(diǎn)權(quán)值的驗(yàn)證即可，即做閾值判斷。

下面兩張圖分別表示使用改進(jìn)KD樹匹配算法的匹配效果前后對比?？梢院苊黠@的看出使用改進(jìn)KD樹算法比改進(jìn)前的KD樹，產(chǎn)生更少的匹配點(diǎn)。盡管如此，由于某些應(yīng)用環(huán)境對目標(biāo)識別效果的要求較高，因此需要在改進(jìn)后的KD樹匹配算法下再進(jìn)行下一步的精匹配。

圖2 改進(jìn)前后KD樹匹配效果圖

3 RANSC精匹配

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

以經(jīng)過KD樹匹配的特征點(diǎn)作為樣本數(shù)據(jù)集。在考慮平移、旋轉(zhuǎn)和尺度變化的影響下，以模板圖像中兩角點(diǎn)間的距離與目標(biāo)圖像中對應(yīng)兩角點(diǎn)間的距離之比作為需要確定的數(shù)學(xué)模型[14-15]。

主要的精匹配過程如下：

1）在模板圖像和目標(biāo)圖像的粗匹配點(diǎn)中隨機(jī)選擇兩組特征點(diǎn)（Up1，Down1）和（Up2，Down2），并將兩個(gè)點(diǎn)組計(jì)入當(dāng)前模型的數(shù)據(jù)點(diǎn)集合this_consensus_set中；Up表示模板圖像特征點(diǎn)，Down表示目標(biāo)圖像特征點(diǎn)；

2）建立本次計(jì)算的模型參數(shù)Model=

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

4）若最終this_consensus_set的數(shù)據(jù)個(gè)數(shù)set_num超過閾值st，則進(jìn)入5）;否則，計(jì)算次數(shù)iterations加1，并返回步驟1）。

5）計(jì)算模型偏差this_error；

以this_consensus_set為計(jì)算集合，遍歷所有點(diǎn)組，計(jì)算每一點(diǎn)組與其他點(diǎn)組的偽模型值與當(dāng)前模型參數(shù)的偏差，并將所有偏差相加開方，即可得到this_error。

6）若 this_error小于模型偏差閾值 best_error，則認(rèn)為匹配完成，認(rèn)為this_consensus_set中的匹配點(diǎn)組即為最終的匹配結(jié)果。否則，計(jì)算次數(shù)iterations加1，并返回步驟1）。

圖3是在改進(jìn)KD樹粗匹配的基礎(chǔ)上再使用RANSC算法完成精匹配的結(jié)果，可以看出經(jīng)RANSC算法后，本次匹配剔除了所有的誤匹配點(diǎn)，匹配效果較好。同時(shí)仔細(xì)觀察可以發(fā)現(xiàn)，模板圖像在目標(biāo)圖像中有不僅存在尺度變化、同時(shí)還有旋轉(zhuǎn)變化，但算法的實(shí)現(xiàn)將二者的影響都成功消除了。

圖3 采用RANSC精匹配效果圖

4 結(jié)論

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

[1]黃敦華，朱青松.基于微小型四旋翼飛行器的目標(biāo)監(jiān)測與識別綜述[J].機(jī)電產(chǎn)品開發(fā)與創(chuàng)新，2011，24（6）：16-18.

[2]張志飛.小型無人直升機(jī)視覺定位與跟蹤系統(tǒng)的設(shè)計(jì)與研究[D].杭州：浙江大學(xué)，2013.

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

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

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

[6]王淵民.基于SIFT算法的圖像快速匹配系統(tǒng)設(shè)計(jì)[D].成都：成都理工大學(xué)，2014.

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

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

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

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

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

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

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

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

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

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

[17]汪立，蔣念平.基于改進(jìn)Harris角點(diǎn)檢測的視網(wǎng)膜圖像配準(zhǔn)[J].電子科技，2017（2）：119-122.

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

[17]汪立，蔣念平.基于改進(jìn)Harris角點(diǎn)檢測的視網(wǎng)膜圖像配準(zhǔn)[J].電子科技，2017（2）：119-122.