改進的AdaBoost-SVM算法用于無人機目標跟蹤*

左奎軍 李艷軍 曹愈遠 王宏宇

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

0 引 言

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

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

1 目標跟蹤的基本框架

目標跟蹤的基本框架見圖1.

圖1 目標跟蹤的基本框架

2 HOG特征提取

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

2) 計算圖像梯度 圖像像素點(x,y)的梯度為

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

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

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

3) 計算梯度方向直方圖：將圖像分割成多個像素為8×8的Cell單元格，然后以每40°為一個分隔點將Cell的梯度方向分成九個方向塊；按照梯度方向對Cell內的像素做加權投影，得到該Cell的梯度直方圖.

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

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

3 隨機投影

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

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

(1)

(2)

此時，對具有M個p維數據的集合Z，存在空間映射f:Rp→Rq，使得所有的u,v∈Z滿足

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

(1+ε)‖u-v‖2

(3)

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

4 基于AdaBoost的SVM分類器

4.1 AdaBoost算法

AdaBoost算法是Boosting算法的一種，是Freund等[14-15]根據在線分配算法提出的.該算法具有兩個優良特性：①隨著迭代次數的增加，訓練的錯誤率是逐漸減小的；②即使對數據進行多次訓練也不會出現過擬合的情況[16-17].

4.2 支持向量機

4.2.1支持向量機原理

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

4.2.2核函數

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

4.3 分類器設計

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

4.4 跟蹤算法的計算流程

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

輸入 第t+1幀圖像

步驟1對滿足Dy={z‖l(z)-lt‖<γ}的圖像塊進行取樣，式中lt為目標在第t幀時的跟蹤位置.

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

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

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

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

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

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

5 實驗結果與分析

5.1 目標跟蹤算法的定性評估

本文的目標跟蹤算法在Matlab 2016a軟件平臺下實現，在配置為Intel i5-2.66 GHz雙核CPU、內存為4GB的計算機上運行，速度為平均每秒2幀.使用了四個具有不同跟蹤難度的無人機拍攝視頻，視頻均來自UAV123公開數據庫，每個跟蹤視頻的特點見表1.

表1 圖像序列挑戰因素分析

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

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

5.2 目標跟蹤算法的定量評估

位置誤差和重疊率是衡量目標跟蹤效果的重要指標.位置誤差表示跟蹤目標框選區域的實際中心與預測中心的歐式距離；假設目標跟蹤的框選區域為γt，實際的框選區域為γα，則重疊率公式為S=|γt∩γα|/|γt∪γα|.其中:∩為兩區域的交集；∪為兩區域的并集；|·|為該區域內的像素數目.根據重疊率高于設定閾值的幀數占總幀數的比例可以繪制出成功率曲線圖，統計位置誤差低于設定閾值的幀數占總幀數的比例可以繪制出精度曲線圖.

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

圖3 不同算法在圖像序列上的綜合表現

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

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

5.3 隨機投影算法的驗證實驗

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

圖5 ORL數據庫人臉圖像

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

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

5.4 改進的AdaBoost-SVM分類器性能比較實驗

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

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

圖6 不同算法對Westontoynon liner數據集和Wine數據集的實驗結果

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

6 結 論

1) 提出的基于改進的AdaBoost-SVM算法能夠有效處理嚴重遮擋、姿態變化、光照變化、小目標檢測、運動模糊、背景雜亂等挑戰，實現了無人機目標跟蹤的精確性、魯棒性和穩定性.

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

3) 采用改進的AdaBoost-SVM算法對提取的圖像特征做分類處理，同時為了權衡σ值的取值大小對樣本分類的影響，將訓練每個弱分類的樣本集的標準差作為σ值.通過不同分類器對Westontoynon liner數據集以及Wine數據集的分類比較實驗可以看出，本文算法可以在更大程度上提高最終強分類器的分類精度和泛化性.

4) 通過一系列的驗證實驗可以發現，雖然本文算法在運動模糊、姿態變化、光照變化以及背景雜亂等嚴重干擾的場景下皆對目標進行了有效跟蹤.但從最終的跟蹤結果來看，當面對小目標以及嚴重遮擋時，本文算法的跟蹤精度以及成功率并不理想；因此，在以后的工作中，還需要對算法進行優化，進一步提高算法的追蹤性能.