基于改進的隨機森林TLD目標跟蹤方法

張　丹，陳興文，趙姝穎

(1.大連民族大學 工程教育學院，遼寧 大連 116605;2.東北大學 信息科學與工程學院，遼寧 沈陽 110819)

?

基于改進的隨機森林TLD目標跟蹤方法

張丹1，陳興文1，趙姝穎2

(1.大連民族大學 工程教育學院，遼寧 大連 116605;2.東北大學 信息科學與工程學院，遼寧 沈陽 110819)

摘要：針對TLD算法中采用的隨機森林分類器的決策樹閾值固定，不能根據目標特征隨時調整，影響分類精度和時間開銷的問題，引入極端隨機森林的思想，提出了基于改進的隨機森林TLD目標跟蹤方法。該方法用Gini系數度量樣本集合的混亂程度，通過比較Gini系數是否超過了給定閾值，判斷葉節點何時轉變成決策節點進行分裂；再結合TLD算法中的P-N學習框架和在線模型訓練更新樣本；最終基于改進的TLD算法完成目標跟蹤。將本文方法應用于多個視頻集進行目標跟蹤實驗，驗證了算法的有效性和穩定性。

關鍵詞：目標跟蹤；隨機森林；TLD；分裂閾值；在線學習

針對決策樹閾值固定，影響分類精度和實時性問題，引入極端隨機森林的思想，結合在線學習模型，提出了一種基于極端隨機森林的TLD改進算法，解決了分裂閾值不能根據目標特征隨時調整，影響跟蹤適應性的問題。

1TLD目標跟蹤算法

TLD 算法主要由三部分組成：跟蹤、在線學習和檢測，其三者相互作用，將得到的數據整合，最終確定下一幀中目標的位置。

TLD算法各變量互相作用關系如圖1。運動目標被一個短期的跟蹤器跟蹤。growingevent和pruningevent分析特征空間的軌跡，連續不斷的試圖擴展或是限制在線學習模型的特征。growingevent識別判斷目標樣本，使運動目標特征Lt不斷擴大；pruningevent識別Lt中錯誤樣本，并將它們去掉，growingevent和pruning共同進行，使得目標特征Lt→L*。

圖1　TLD算法相關量關系圖

TLD算法的檢測器主要是一個級聯分類器，其主要由方差濾波器、集成分類器及最近鄰分類器三部分組成，集成分類器主要由n個隨機蕨分類器構成的隨機森林組成，隨機蕨主要采用的是2bitBP特征，圖像區域輸入到集成分類器之后，獲得后驗概率。計算n個隨機蕨分類器的后驗概率，如果平均值大于閾值，則將該區域定為正樣本，否則為負樣本。

1.1.1 母本高不育系 W0176A選育。2003—2004年，用不同來源種質與0176A不育株廣泛測交，配制各類測交組合，F1自交。

極端隨機森林每棵決策樹的決策點分裂測試閾值是隨機選擇的，不是以某一特征進行設定，保證了樣本的豐富性，極端隨機森林分類器在分類精度和訓練時間開銷等方面的性能較好，但采用的不是bootstrap策略，直接采用原始的訓練樣本，只能支持離線的訓練方式，不支持增量學習[10]，本文充分利用極端隨機森林和TLD在線學習模型的特性，提出了一種基于改進的隨機森林TLD目標跟蹤方法。

2基于改進的隨機森林TLD方法

2.1改進的隨機森林方法

本文將深入討論和研究閾值參數選擇的問題。引入樣本混合比α，用于度量樣本集合各種類別樣本比例關系，α為葉節點上非數量最多的樣本相對于數量最多的樣本的比例。

假設在某一葉節點上存儲的樣本為K種，其中數量最多的類樣本標號為Lm，占全部樣本數量比例為pm，其余樣本所占比例為pi(i≠m,i=1,2,…K)，Lm樣本數量為n，其余類別的樣本數目相對Lm的比例為αi，非Lm的樣本相對Lm的比例為

(1)

則經實驗驗證該葉節點的分裂閾值參數為：

(2)

對葉節點分裂閾值參數討論如下：

分類閾值參數Δ會影響極端隨機森林方法的性能，合適的閾值可以保證算法具有高的分類正確率和較少的訓練時間。由前所述，分裂閾值的選擇與混合比α大小有關，本文中將α按照0,0.1,…1.0取值，對不同的α值下的分類錯誤率、葉節點數量和訓練時間分別進行統計，最終考核各個方面確定閾值參數Δ。

本文采用的實驗數據來自于標準目標跟蹤視頻數據，訓練次數設為50次，設置8棵樹，每棵樹有10個特征，得到的訓練圖如圖2。

所以綜合分類錯誤率、葉節點數量以及訓練時間等因素，選擇樣本混合比為0.2，這使得極端隨機森林既具有較高的分類正確率，又保證了葉節點的數量同時訓練時間也不長，此時分裂參數Δ=0.31。

(a) 分類錯誤率圖

(b) 產生葉節點數量圖

(c) 時間對比圖

2.2改進后的TLD跟蹤算法描述

(1)手動獲得目標區域，在第一幀確定目標邊界框，每個子窗口從9×9像素大小到整幅圖像大小隨機產生，將圖像塊作為樣本處理，記錄圖像塊邊界框，用于后面的評估；

(3)進入級聯分類器的第一級分類器方差分類器，檢測滑動窗口像素點的灰度值方差，濾掉一部分背景圖像；

(4)通過方差分類器的圖像塊進入隨機森林分類器，在這部分按照2.1節改進的隨機森林設置分類閾值訓練決策樹，基于各個決策樹是相互獨立的，計算各決策樹的后驗概率，決定是否接受滑動窗口，這個過程是離線進行的；

(5)采用最近鄰分類器更新樣本，將分類器與在線學習模塊growingevent和pruningevent相結合，使得極端隨機森林變成增量式，設定滑動窗口與在線模型的相關相似度閾值，growingevent將自身置信度高的樣本給特征空間進行增量學習分類，同時pruningevent根據自身樣本的置信度判斷特征空間中的不正確樣本，將其從特征空間中去掉，更新檢測器；

(6)在更新檢測的同時也更新跟蹤器，在目標框內均勻采樣，采用LK光流法跟蹤，并進行擴展誤差檢測，計算圖像塊的位置信息，估計目標框在當前幀中的位置，信息像素點也用于在線學習模塊的樣本信息，綜合跟蹤模塊、檢測模塊、在線學習模塊完成一個跟蹤過程。

3實驗結果及分析

實驗用計算機為CPUE5500，2.80GHz，2GB內存，在MatlabR2009a環境下運行。實驗數據來自標準目標跟蹤測試數據集，分別為Car、Face、Moto。

為了驗證算法的有效性，本文將改進方法和隨機森林算法進行對比，分別比較兩個算法的分類正確率、葉節點數量和訓練時間。兩種算法分別在數據集上運行50次，使用8棵樹，分裂閾值參數為0.31。得到的統計結果見表1。

表1　改進算法與隨機森林算法的比較結果

從表1中可以看出改進后的方法分類正確率與隨機森林的相差不大，略優于隨機森林；產生的葉節點數量多于隨機森林，訓練速度明顯快于隨機森林。通過以上實驗可以看出，改進算法在按照樣本混合比選定正確分裂閾值的情況下，結果優于隨機森林，所以本文將極端隨機森林加入TLD算法中，用于提高算法的速度以及精度。

Car、Face、Moto三個視頻集包含了目標跟蹤過程中的尺度變化、快速頻繁轉動、快速運動、目標相似、光照變化等情況，針對以上三個視頻集，將本文方法與TLD方法進行對比，處理結果如圖3-圖5。

從圖3-圖5中可以看出視頻初始幀的跟蹤兩種算法都較為準確，但到后續幀中，由于目標的快速轉動、遮擋、尺度變化等因素的干擾，原始方法出現了分類不精確的現象，跟蹤邊框出現了一定程度的偏移，而本文方法進行了較為準確的跟蹤。本文采用文獻[10]的評價方法，如果目標物體有25 %以上沒能被跟蹤，那么這幀數據被認為跟蹤錯誤，統計結果見表2。從表中可以看出，本文方法的跟蹤效果更準確，對于目標多種情況變化適應性更強，穩定性更好。

第6幀　　　　　　第236幀

第253 幀　　　　　 第669幀

第13幀　　　　　第43幀

第284　　　　　　第331幀

第12幀　　　　　　第26幀

第57幀　　　　　　　第92幀

數據集改進方法(正確幀數/總幀數)TLD算法(正確幀數/總幀數)Carsequence504/600489/600Facesequence412/550389/550Motosequence92/10086/100

4結論

本文在隨機森林中引入樣本混合比α，選定分裂閾值，采用極端隨機森林進行分類，加入在線

學習模型，構成增量式極端隨機森林，用于TLD算法中，提出基于改進的隨機森林TLD目標跟蹤方法。實驗首先驗證了本文算法時間開銷低、分類準確性高，其次進行目標跟蹤實驗，結果表明，本文方法對于復雜情況下的目標跟蹤準確，穩定性強。但本文方法只進行了單目跟蹤，還要進一步處理，實現多目標跟蹤。

參考文獻：

[1] MARCO P,RADU T,TINNE T，et al.An Elastic Deformation Field Model for Object Detection and Tracking[J]. International Journal of Computer Vision, 2015, 111(2):137-152.

[2] REHMAN A,KIHARA K,MATSUMOTO A,et al. Attentive tracking of moving objects in real 3D space[J]. Vision Research,2015,109(part A):1-10.

[3] PERNICI F ,DEL BIMBO.A.Object Tracking by Oversampling Local Features[J]. Pattern Analysis and Machine Intelligence.2014,36(12):2538-2551.

[4] 彭爽, 彭曉明. 基于高效多示例學習的目標跟蹤[J]. 計算機應用, 2015,35( 2) : 466 -469, 475.

[5] 李想，汪榮貴，楊娟. 基于示例選擇的目標跟蹤改進算法[J]. 計算機工程,2015,41(1):150-157.

[6] KALAL Z, MATAS J, MIKOLAJCZYK K. Online learning of robust object detectors during unstable tracking [C]∥ Computer Vision Workshops (ICCV Workshops), 2009:1417-1424.

[7] KALAL Z, MIKOLAJCZYK K, MATAS J. Face-TLD: Tracking -Learning-Detection Applied to Faces[C]∥ International Conference on Image Processing, 2010:3789-3792.

[8] KALAL Z, MIKOLAJCZYK K, MATAS J. Forward-Backward Error: Automatic Detection of Tracking Failures [C]∥ International Conference on Pattern Recognition (ICPR 2010), 2010: 23-26.

[9] KALAL Z, MIKOLAJCZYK K, MATAS J. P-N Learning: Bootstrapping Binary Classifiers by Structural Constraints [C]. Computer Vision and Pattern Recognition (CVPR), 2010:49-56.

[10] 王愛平，萬國偉，程志全，等. 支持在線學習的增量式極端隨機森林分類器拳[J].軟件學報，2011,22(9):2059-2074.

(責任編輯王楠楠)

TLD Target Tracking Method based on Improved Random Forest

ZHANG Dan1, CHEN Xing-wen1, ZHAO Shu-ying2

(1.School of Engineering Education, Dalian Minzu University, Dalian Liaoning 116605, China;2.School of Information Science and Engineering, Northeastern University,Shenyang Liaoning 110819, China)

Abstract:The fixed threshold value of the random forest classifier can not be readily adapted to the target feature of TLD (Tracking Learning Detecting) algorithm, which affects classification accuracy and time overhead issues. Aiming at this problem, an idea of extreme random forest was introduced, and a TLD target tracking method based on improved random forest is proposed. This method used Gini coefficient to measure the degree of confusion of sample sets, by deciding the Gini coefficient whether exceeded a given threshold to judge when a leaf node changed into the decision node to split. Combining P-N learning framework and online model, samples were trained and updated. Finally, the target tracking was completed based on improved TLD algorithm. The proposed method was used in many video sets for target tracking to verify its effectiveness and stability.

Key words:target tracking; random forests; TLD; split threshold; online learning

收稿日期：2015-09-21；最后修回日期：2016-12-21

基金項目：中央高校基本科研業務費專項資金資助項目(DC201502060303，DC201501075)。

作者簡介：張丹(1987-)，女，遼寧葫蘆島人，工程師，主要從事圖像處理，機器視覺研究。通訊作者：陳興文(1969-)，男，遼寧錦州人，教授，主要從事圖像處理、模式識別研究，E-mail: mycxw@dlnu.edu.cn.

文章編號：2096-1383(2016)03-0255-05

中圖分類號：TP391

文獻標志碼：A