改進(jìn)的AdaBoost-SVM算法用于無人機(jī)目標(biāo)跟蹤*

左奎軍 李艷軍 曹愈遠(yuǎn) 王宏宇

(南京航空航天大學(xué)民航學(xué)院 南京 211106)

0 引 言

隨著數(shù)據(jù)挖掘、深度學(xué)習(xí)等新興技術(shù)的發(fā)展，在計(jì)算機(jī)圖像處理方面的研究也有了突飛猛進(jìn)的進(jìn)步.其中目標(biāo)跟蹤尤其受到研究人員的關(guān)注[1].從傳統(tǒng)意義上的目標(biāo)跟蹤到如今使用機(jī)器學(xué)習(xí)、深度學(xué)習(xí)的方法進(jìn)行目標(biāo)跟蹤，在這一過程中孕育出了許多經(jīng)典的目標(biāo)跟蹤算法.一般說來，目標(biāo)跟蹤算法可分為兩種：生成式和判別式[2].生成式算法其本質(zhì)是一類尋優(yōu)問題它將與目標(biāo)模板匹配程度最高或重構(gòu)誤差最小的位置作為目標(biāo)位置的預(yù)測.侯躍恩[3]使用主元分析理論來對(duì)目標(biāo)模板進(jìn)行更新，從而提出了一種Gabor特征稀疏表示目標(biāo)跟蹤算法.為了解決由于外觀的快速變化導(dǎo)致目標(biāo)模板不能快速匹配的問題，Jepson等[4]提出了一種魯棒性自適應(yīng)的在線外觀模型.為了解決在目標(biāo)快速運(yùn)動(dòng)以及受到遮擋時(shí)Mean Shift算法跟蹤失敗的狀況，楊建偉[5]將MeanShift算法和卡爾曼濾波進(jìn)行結(jié)合，從而得到了一種新穎的目標(biāo)跟蹤算法，實(shí)現(xiàn)了對(duì)目標(biāo)的有效跟蹤.從另一個(gè)角度來看，判別式算法也可以當(dāng)成一種分類問題來處理，通過訓(xùn)練分類器，使之對(duì)跟蹤目標(biāo)和背景區(qū)域進(jìn)行有效的區(qū)分，從而實(shí)現(xiàn)良好的跟蹤效果.常用算法有：支持向量機(jī)(SVM)[6]、隨機(jī)森林[7]、AdaBoost算法[8]、稀疏表示算法[9]等.

雖然上述算法在一定程度上解決了目標(biāo)跟蹤上的部分難題，但是將其直接用于無人機(jī)視頻中的運(yùn)動(dòng)目標(biāo)檢測跟蹤仍存在一定的局限性[10].這是因?yàn)椋孩俅蠖鄶?shù)的算法是在理想的條件下進(jìn)行的，如相機(jī)靜止、目標(biāo)運(yùn)動(dòng)緩慢、背景簡單、目標(biāo)清晰等.但是，在實(shí)際情況中無人機(jī)與跟蹤目標(biāo)都是會(huì)移動(dòng)的，這在無形中增加了跟蹤的難度；②計(jì)算量大，難以保證實(shí)時(shí)性；③檢測跟蹤小目標(biāo)比較困難.雖然近幾年一些學(xué)者針對(duì)無人機(jī)的目標(biāo)跟蹤算法也進(jìn)行了大量的研究，但是大多數(shù)都是采用傳統(tǒng)的算法，而傳統(tǒng)算法在面對(duì)小目標(biāo)時(shí)，并不能有效的提取特征，因此，國內(nèi)外部分學(xué)者開始研究基于機(jī)器學(xué)習(xí)的目標(biāo)檢測與跟蹤算法.林曉林等[11]利用Harris 角點(diǎn)檢測與改進(jìn)的多cell、多block的HOG算法結(jié)合SVM對(duì)視頻幀中的小目標(biāo)進(jìn)行檢測，提出了基于機(jī)器學(xué)習(xí)的小目標(biāo)檢測與追蹤算法DT；Rozantsev等[12]使用了滑動(dòng)窗口與CNN方法相結(jié)合的方法來檢測小目標(biāo)；呂卓紋等[13]將Camshift與AdaBoost算法進(jìn)行結(jié)合，以紋理與顏色作為特征進(jìn)行提取，在復(fù)雜的跟蹤背景下取得了較好的跟蹤效果.但目前針對(duì)應(yīng)用于無人機(jī)目標(biāo)跟蹤上的基于機(jī)器學(xué)習(xí)的目標(biāo)跟蹤算法研究尚少，因此本文就此展開深入研究.

1 目標(biāo)跟蹤的基本框架

目標(biāo)跟蹤的基本框架見圖1.

圖1 目標(biāo)跟蹤的基本框架

2 HOG特征提取

1) 圖像規(guī)范化 對(duì)γ進(jìn)行壓縮處理，I(x,y)=I(x,y)γ，這里γ取1/2，圖像經(jīng)過規(guī)范化后，可以有效降低圖像局部陰影和光照變化.

2) 計(jì)算圖像梯度 圖像像素點(diǎn)(x,y)的梯度為

Gx(x,y)=H(x+1,y)-H(x-1,y)

Gy(x,y)=H(x,y+1)-H(x,y-1)

在像素點(diǎn)(x,y)處，水平方向梯度表示為Gx(x,y)；垂直方向梯度表示為Gy(x,y);對(duì)應(yīng)的像素值表示為H(x,y)，從而在像素點(diǎn)(x,y)處對(duì)應(yīng)的梯度幅值以及梯度方向可以表示為

3) 計(jì)算梯度方向直方圖：將圖像分割成多個(gè)像素為8×8的Cell單元格，然后以每40°為一個(gè)分隔點(diǎn)將Cell的梯度方向分成九個(gè)方向塊；按照梯度方向?qū)ell內(nèi)的像素做加權(quán)投影，得到該Cell的梯度直方圖.

4) 塊內(nèi)歸一化梯度直方圖 首先，將多個(gè)臨近的Cell單元組合成一個(gè)(blocks)塊，然后將每個(gè)block內(nèi)的所有Cell特征向量串聯(lián)起來構(gòu)成HOG特征，最后在每個(gè)block內(nèi)進(jìn)行歸一化操作.

5) 生成HOG特征描述向量 將block之間重疊的HOG特征組合成一個(gè)高維向量，得到最終的特征向量.

3 隨機(jī)投影

由于提取的HOG特征向量維度較大，這就不可避免導(dǎo)致計(jì)算量的增加，若要解決這一問題，就必須要對(duì)數(shù)據(jù)做降維處理.由于隨機(jī)投影方法完全獨(dú)立于樣本數(shù)據(jù)，因此該方法是一種有效的數(shù)據(jù)降維手段.接下來給出隨機(jī)投影的定義.

設(shè)初始m維數(shù)據(jù)矩陣為Xm×n，k×m維隨機(jī)投影矩陣為R，數(shù)據(jù)矩陣X在隨機(jī)投影矩陣R的作用下，被投影到一個(gè)低維的子空間k內(nèi).將上述高維矩陣投影問題用數(shù)學(xué)公式為

(1)

(2)

此時(shí)，對(duì)具有M個(gè)p維數(shù)據(jù)的集合Z，存在空間映射f:Rp→Rq，使得所有的u,v∈Z滿足

(1-ε)‖u-v‖2≤‖f(u)-f(v)‖2≤

(1+ε)‖u-v‖2

(3)

Johnson-Lindenstrauss定理利用數(shù)學(xué)公式的推導(dǎo)對(duì)隨機(jī)投影的計(jì)算方法進(jìn)行了證明，并且這里需要指出，高維數(shù)據(jù)通過降維最終得到的維度為q的低維數(shù)據(jù)滿足q≥o(lnM/ε2).同時(shí)在對(duì)高維數(shù)據(jù)進(jìn)行降維處理時(shí)，投影矩陣的選擇在很大程度上決定了數(shù)據(jù)降維的好壞，經(jīng)常選取的矩陣有：經(jīng)典正交矩陣、Achiloptas矩陣、Li’s矩陣.為了減小實(shí)驗(yàn)誤差，文中使用經(jīng)典正交矩陣的方法計(jì)算出投影矩陣.

4 基于AdaBoost的SVM分類器

4.1 AdaBoost算法

AdaBoost算法是Boosting算法的一種，是Freund等[14-15]根據(jù)在線分配算法提出的.該算法具有兩個(gè)優(yōu)良特性：①隨著迭代次數(shù)的增加，訓(xùn)練的錯(cuò)誤率是逐漸減小的；②即使對(duì)數(shù)據(jù)進(jìn)行多次訓(xùn)練也不會(huì)出現(xiàn)過擬合的情況[16-17].

4.2 支持向量機(jī)

4.2.1支持向量機(jī)原理

通俗來講，支持向量機(jī)(SVM)是一種典型的二類分類模型，它要解決的問題是如何在一個(gè)n維空間里找到一個(gè)n-1維的超平面對(duì)數(shù)據(jù)進(jìn)行分類.SVM不光對(duì)線性問題能進(jìn)行很好的分類，對(duì)非線性問題也能取得較好的分類效果；同時(shí)SVM在很大程度上也克服了“維數(shù)災(zāi)難”和“過學(xué)習(xí)”等問題[18].

4.2.2核函數(shù)

當(dāng)在低維空間中遇到線性不可分的問題時(shí)，可以通過一個(gè)映射函數(shù)把樣本值映射到更高維的空間來求解.這里的映射函數(shù)即是核函數(shù).核函數(shù)的使用有效的避免了“維數(shù)災(zāi)難”的發(fā)生.常用的核函數(shù)有：Sigmoid核函數(shù)、字符串核函數(shù)、線性核函數(shù)和徑向基核函數(shù)等.由于徑向基核函數(shù)(RBF)能夠把原始數(shù)據(jù)映射到無窮維并且計(jì)算復(fù)雜度低，因此選用徑向基核函數(shù).

4.3 分類器設(shè)計(jì)

AdaBoost算法要想達(dá)到較好的分類效果，精度和差異性缺一不可[19].為了更好的對(duì)HOG特征進(jìn)行分類，將基于徑向基核函數(shù)的支持向量機(jī)(RBFSVM)作為AdaBoost的分量分類器.在使用上述方法對(duì)HOG特征進(jìn)行分類時(shí)，若所有弱分類器σ的取值相同，將會(huì)導(dǎo)致如下問題：若σ值過大，則AdaBoost的分類效果不佳；若σ值過小，則可能出現(xiàn)過擬合.綜上所述，若要進(jìn)一步提高弱分類的分類精度，合理選取σ值是關(guān)鍵，這里將訓(xùn)練每個(gè)弱分類器的樣本集的標(biāo)準(zhǔn)差作為參數(shù)σ，從而獲得了較高的分類精度.

4.4 跟蹤算法的計(jì)算流程

提出算法的計(jì)算流程，在提取到HOG 特征之后，應(yīng)用隨機(jī)投影算法對(duì)數(shù)據(jù)做降維處理，特征向量經(jīng)過降維后再輸入到改進(jìn)的AdaBoost-SVM分類器中進(jìn)行訓(xùn)練和分類.分類器以上一幀的目標(biāo)位置為參考，分別對(duì)正負(fù)樣本進(jìn)行采樣，采樣結(jié)束后得到的結(jié)果作為分類器的訓(xùn)練輸入，而分類器的輸出則是當(dāng)前幀的跟蹤結(jié)果.流程如下.

輸入 第t+1幀圖像

步驟1對(duì)滿足Dy={z‖l(z)-lt‖<γ}的圖像塊進(jìn)行取樣，式中l(wèi)t為目標(biāo)在第t幀時(shí)的跟蹤位置.

步驟2對(duì)步驟1中取樣圖像塊的HOG特征進(jìn)行提取，并對(duì)提取到的特征向量用隨機(jī)投影算法做降維處理.

步驟3將步驟2中獲得的低維特征向量組輸入到改進(jìn)的AdaBoost-SVM分類器中進(jìn)行分類，得到第t+1幀圖像的目標(biāo)位置lt+1.

步驟4根據(jù)步驟3中得到的目標(biāo)位置lt+1對(duì)正負(fù)樣本集進(jìn)行采樣，正樣本集滿足：D?={z‖l(z)-lt+1‖}

步驟5對(duì)步驟4中采樣的正負(fù)樣本集提取HOG特征，并再次用隨機(jī)投影算法對(duì)獲得的特征向量做降維處理.

步驟6將步驟5中得到的特征向量組輸入到改進(jìn)的AdaBoost-SVM分類器中進(jìn)行訓(xùn)練.

輸出 跟蹤位置lt+1和分類器的更新參數(shù).

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

5.1 目標(biāo)跟蹤算法的定性評(píng)估

本文的目標(biāo)跟蹤算法在Matlab 2016a軟件平臺(tái)下實(shí)現(xiàn)，在配置為Intel i5-2.66 GHz雙核CPU、內(nèi)存為4GB的計(jì)算機(jī)上運(yùn)行，速度為平均每秒2幀.使用了四個(gè)具有不同跟蹤難度的無人機(jī)拍攝視頻，視頻均來自UAV123公開數(shù)據(jù)庫，每個(gè)跟蹤視頻的特點(diǎn)見表1.

表1 圖像序列挑戰(zhàn)因素分析

圖2為文中算法與其他算法在不同圖像序列上的跟蹤結(jié)果.由圖2可知，Bike1圖像序列面向的主要是姿態(tài)變化和嚴(yán)重遮擋的場景，跟蹤目標(biāo)在騎行過程中突然下車，然后快速推著車到了馬路的另一邊；并且跟蹤器面臨在騎行過程中具有相似跟蹤目標(biāo)的遮擋(第1 040和第1 231幀)問題，但從最終的跟蹤結(jié)果來看，本文算法取得了較好的跟蹤效果，其他算法都存在不同程度的目標(biāo)跟蹤丟失的情況；Bike2圖像序列主要是背景雜亂、小目標(biāo)的場景，跟蹤目標(biāo)特征點(diǎn)較少，跟蹤環(huán)境復(fù)雜，文中算法前期跟蹤良好，最后跟蹤效果欠佳，其他算法皆不能實(shí)現(xiàn)有效的跟蹤.MotorRolling圖像序列主要是光照變化、背景模糊的場景，摩托車手移動(dòng)迅速，并且場景中出現(xiàn)較強(qiáng)光照的干擾，文中算法對(duì)其進(jìn)行了準(zhǔn)確的跟蹤，MIL跟蹤器在一定程度上也對(duì)目標(biāo)進(jìn)行了有效的跟蹤；MountainBike圖像序列面向的主要是姿態(tài)變化、運(yùn)動(dòng)模糊的場景，摩托車手在跨越山谷的過程中運(yùn)動(dòng)速度快，并且在空中停留的時(shí)間內(nèi)姿態(tài)出現(xiàn)了較大變化，即使是在如此復(fù)雜的環(huán)境下，文中算法還是對(duì)其進(jìn)行了精確的跟蹤.

圖2 文中算法與其他算法在不同圖像序列上的跟蹤結(jié)果

5.2 目標(biāo)跟蹤算法的定量評(píng)估

位置誤差和重疊率是衡量目標(biāo)跟蹤效果的重要指標(biāo).位置誤差表示跟蹤目標(biāo)框選區(qū)域的實(shí)際中心與預(yù)測中心的歐式距離；假設(shè)目標(biāo)跟蹤的框選區(qū)域?yàn)棣胻，實(shí)際的框選區(qū)域?yàn)棣忙?，則重疊率公式為S=|γt∩γα|/|γt∪γα|.其中:∩為兩區(qū)域的交集；∪為兩區(qū)域的并集；|·|為該區(qū)域內(nèi)的像素?cái)?shù)目.根據(jù)重疊率高于設(shè)定閾值的幀數(shù)占總幀數(shù)的比例可以繪制出成功率曲線圖，統(tǒng)計(jì)位置誤差低于設(shè)定閾值的幀數(shù)占總幀數(shù)的比例可以繪制出精度曲線圖.

圖3為文中算法與SCM，ASLA，VTD，CXT，VTS，CSK，TLD，LSK，MIT等10種算法在四個(gè)不同圖像序列上跟蹤效果的綜合表現(xiàn).由圖3a)可知，當(dāng)重疊閾值介于0～0.5時(shí)，本文算法相較于其它算法而言，對(duì)目標(biāo)的跟蹤成功率是最優(yōu)的；由圖3b)可知，當(dāng)位置誤差閾值介于10～50時(shí)，從跟蹤的精度來看，本文算法與其他算法相比也同樣有著優(yōu)異的性能表現(xiàn).總體來說，本文算法無論是在跟蹤的成功率上，還是在跟蹤的精度上都有著良好的性能表現(xiàn).

圖3 不同算法在圖像序列上的綜合表現(xiàn)

圖4為文中算法與TLD，CXT，OAB，MIL，CSK，RS-V，L1-APG，DFT，ASLA共10個(gè)算法在快速運(yùn)動(dòng)、背景雜亂、運(yùn)動(dòng)模糊、低清晰度四種場景下的跟蹤成功率對(duì)比圖.在圖4中每張圖的右上角方框中表示的是10種跟蹤器在不同場景下的AUC值(成功率曲線下的面積)，可以發(fā)現(xiàn)，在快速運(yùn)動(dòng)、運(yùn)動(dòng)模糊、低清晰度三種不同場景下，文中算法的AUC值分別為0.751,0.652,0.660，均高于其他跟蹤器的ACU值，說明本文算法在三種不同場景下跟蹤成功率最高，在背景雜亂的場景下，文中算法與ASLA算法的ACU值相差無幾，ASLA算法之所以在背景雜亂的環(huán)境下表現(xiàn)良好是因?yàn)樵撍惴ňC合稀疏表示與增量子空間學(xué)習(xí)的優(yōu)勢進(jìn)行模型的更新，能更好處理跟蹤漂移和背景雜亂現(xiàn)象.

圖4 四種不同場景下的成功率曲線

5.3 隨機(jī)投影算法的驗(yàn)證實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證隨機(jī)投影方法降維的有效性，本文用隨機(jī)投影法(random projection,RP)、主成分分析法(PCA)、均值取樣法(Down sample)、以及沒有經(jīng)過降維的圖像進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)使用的是劍橋大學(xué)人臉數(shù)據(jù)庫，見圖5.

圖5 ORL數(shù)據(jù)庫人臉圖像

該數(shù)據(jù)庫由400張灰度圖像組成，這些圖像包含了40個(gè)人的面部表情、臉部特征等基本信息，而且只保留每個(gè)人面部表情差異大的10張圖片.實(shí)驗(yàn)中將每人的前五張圖片組成一個(gè)模板集，每人的后五張圖片打亂順序組成一個(gè)測試集，觀察測試集中的圖像與模板集中的圖像匹配的成功率，分別對(duì)每種算法進(jìn)行20次實(shí)驗(yàn)，取平均值作為最終分類正確的結(jié)果，得到的結(jié)果見表2.由表2可知，未降維圖像的匹配準(zhǔn)確率是最高的，但是它的特征維度過高，從而導(dǎo)致處理時(shí)間過長；PCA和Downs sample方法雖然處理時(shí)間短，但是它們的準(zhǔn)確率都不足80%；綜上所述，在兼顧準(zhǔn)確率和實(shí)時(shí)性的前提下，本文選擇了隨機(jī)投影方法對(duì)高維數(shù)據(jù)做降維處理.

表2 不同降維方法性能比較

5.4 改進(jìn)的AdaBoost-SVM分類器性能比較實(shí)驗(yàn)

為了更加精確的驗(yàn)證改進(jìn)算法的分類性能，下面將本文算法與固定核函數(shù)的AdaBoost-SVM以及徑向基核函數(shù)的支持向量機(jī)(RBFSVM)進(jìn)行分類實(shí)驗(yàn)對(duì)比.實(shí)驗(yàn)使用的是Westontoynon liner數(shù)據(jù)集以及Wine數(shù)據(jù)集.

各分類器在對(duì)Westontoynon liner數(shù)據(jù)集進(jìn)行分類時(shí)，分別取50，15，200，300，500作為訓(xùn)練樣本集的大小，另外在數(shù)據(jù)集中隨機(jī)取128個(gè)樣本作為測試樣本集；其中AdaBoost-SVM的核函數(shù)參數(shù)σ取值為12；每種算法皆做3次實(shí)驗(yàn)，取3次實(shí)驗(yàn)的平均值作為最終結(jié)果，實(shí)驗(yàn)結(jié)果見圖6a).

圖6 不同算法對(duì)Westontoynon liner數(shù)據(jù)集和Wine數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

各分類器在對(duì)Wine數(shù)據(jù)集進(jìn)行分類時(shí)，分別取50,80,100,130,150作為訓(xùn)練樣本集的大小，另外在數(shù)據(jù)集中隨機(jī)抽取79個(gè)樣本作為測試樣本集.其中AdaBoost-SVM的核函數(shù)參數(shù)σ分別取2，6，12；每種算法做3次測試，取3次實(shí)驗(yàn)的平均值作為最終結(jié)果，實(shí)驗(yàn)結(jié)果見圖6b).通過對(duì)圖6兩幅圖的對(duì)比分析可知，AdaBoost-SVM相對(duì)于SVM來說，分類精度并沒有明顯改善，而本文提出的改進(jìn)的AdaBoost-SVM則明顯提高了分類精度.

6 結(jié) 論

1) 提出的基于改進(jìn)的AdaBoost-SVM算法能夠有效處理嚴(yán)重遮擋、姿態(tài)變化、光照變化、小目標(biāo)檢測、運(yùn)動(dòng)模糊、背景雜亂等挑戰(zhàn)，實(shí)現(xiàn)了無人機(jī)目標(biāo)跟蹤的精確性、魯棒性和穩(wěn)定性.

2) 解決了HOG特征維數(shù)高，訓(xùn)練時(shí)間長的缺陷，采用了一種隨機(jī)映射的數(shù)據(jù)降維方法，可以在不丟失信息的前提下有效地對(duì)數(shù)據(jù)進(jìn)行降維，從而極大地減少了在線訓(xùn)練器的計(jì)算量，保證了算法的實(shí)時(shí)性.

3) 采用改進(jìn)的AdaBoost-SVM算法對(duì)提取的圖像特征做分類處理，同時(shí)為了權(quán)衡σ值的取值大小對(duì)樣本分類的影響，將訓(xùn)練每個(gè)弱分類的樣本集的標(biāo)準(zhǔn)差作為σ值.通過不同分類器對(duì)Westontoynon liner數(shù)據(jù)集以及Wine數(shù)據(jù)集的分類比較實(shí)驗(yàn)可以看出，本文算法可以在更大程度上提高最終強(qiáng)分類器的分類精度和泛化性.

4) 通過一系列的驗(yàn)證實(shí)驗(yàn)可以發(fā)現(xiàn)，雖然本文算法在運(yùn)動(dòng)模糊、姿態(tài)變化、光照變化以及背景雜亂等嚴(yán)重干擾的場景下皆對(duì)目標(biāo)進(jìn)行了有效跟蹤.但從最終的跟蹤結(jié)果來看，當(dāng)面對(duì)小目標(biāo)以及嚴(yán)重遮擋時(shí)，本文算法的跟蹤精度以及成功率并不理想；因此，在以后的工作中，還需要對(duì)算法進(jìn)行優(yōu)化，進(jìn)一步提高算法的追蹤性能.