張　丹，陳興文，趙姝穎

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

?

基于改進(jìn)的隨機(jī)森林TLD目標(biāo)跟蹤方法

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

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

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

關(guān)鍵詞：目標(biāo)跟蹤；隨機(jī)森林；TLD；分裂閾值；在線學(xué)習(xí)

針對決策樹閾值固定，影響分類精度和實時性問題，引入極端隨機(jī)森林的思想，結(jié)合在線學(xué)習(xí)模型，提出了一種基于極端隨機(jī)森林的TLD改進(jìn)算法，解決了分裂閾值不能根據(jù)目標(biāo)特征隨時調(diào)整，影響跟蹤適應(yīng)性的問題。

1TLD目標(biāo)跟蹤算法

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

TLD算法各變量互相作用關(guān)系如圖1。運(yùn)動目標(biāo)被一個短期的跟蹤器跟蹤。growingevent和pruningevent分析特征空間的軌跡，連續(xù)不斷的試圖擴(kuò)展或是限制在線學(xué)習(xí)模型的特征。growingevent識別判斷目標(biāo)樣本，使運(yùn)動目標(biāo)特征Lt不斷擴(kuò)大；pruningevent識別Lt中錯誤樣本，并將它們?nèi)サ?，growingevent和pruning共同進(jìn)行，使得目標(biāo)特征Lt→L*。

圖1　TLD算法相關(guān)量關(guān)系圖

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

1.1.1 母本高不育系 W0176A選育。2003—2004年，用不同來源種質(zhì)與0176A不育株廣泛測交，配制各類測交組合，F(xiàn)1自交。

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

2基于改進(jìn)的隨機(jī)森林TLD方法

2.1改進(jìn)的隨機(jī)森林方法

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

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

(1)

則經(jīng)實驗驗證該葉節(jié)點(diǎn)的分裂閾值參數(shù)為：

(2)

對葉節(jié)點(diǎn)分裂閾值參數(shù)討論如下：

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

本文采用的實驗數(shù)據(jù)來自于標(biāo)準(zhǔn)目標(biāo)跟蹤視頻數(shù)據(jù)，訓(xùn)練次數(shù)設(shè)為50次，設(shè)置8棵樹，每棵樹有10個特征，得到的訓(xùn)練圖如圖2。

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

(a) 分類錯誤率圖

(b) 產(chǎn)生葉節(jié)點(diǎn)數(shù)量圖

(c) 時間對比圖

2.2改進(jìn)后的TLD跟蹤算法描述

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

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

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

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

(6)在更新檢測的同時也更新跟蹤器，在目標(biāo)框內(nèi)均勻采樣，采用LK光流法跟蹤，并進(jìn)行擴(kuò)展誤差檢測，計算圖像塊的位置信息，估計目標(biāo)框在當(dāng)前幀中的位置，信息像素點(diǎn)也用于在線學(xué)習(xí)模塊的樣本信息，綜合跟蹤模塊、檢測模塊、在線學(xué)習(xí)模塊完成一個跟蹤過程。

3實驗結(jié)果及分析

實驗用計算機(jī)為CPUE5500，2.80GHz，2GB內(nèi)存，在MatlabR2009a環(huán)境下運(yùn)行。實驗數(shù)據(jù)來自標(biāo)準(zhǔn)目標(biāo)跟蹤測試數(shù)據(jù)集，分別為Car、Face、Moto。

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

表1　改進(jìn)算法與隨機(jī)森林算法的比較結(jié)果

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

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

從圖3-圖5中可以看出視頻初始幀的跟蹤兩種算法都較為準(zhǔn)確，但到后續(xù)幀中，由于目標(biāo)的快速轉(zhuǎn)動、遮擋、尺度變化等因素的干擾，原始方法出現(xiàn)了分類不精確的現(xiàn)象，跟蹤邊框出現(xiàn)了一定程度的偏移，而本文方法進(jìn)行了較為準(zhǔn)確的跟蹤。本文采用文獻(xiàn)[10]的評價方法，如果目標(biāo)物體有25 %以上沒能被跟蹤，那么這幀數(shù)據(jù)被認(rèn)為跟蹤錯誤，統(tǒng)計結(jié)果見表2。從表中可以看出，本文方法的跟蹤效果更準(zhǔn)確，對于目標(biāo)多種情況變化適應(yīng)性更強(qiáng)，穩(wěn)定性更好。

第6幀　　　　　　第236幀

第253 幀　　　　　 第669幀

第13幀　　　　　第43幀

第284　　　　　　第331幀

第12幀　　　　　　第26幀

第57幀　　　　　　　第92幀

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

4結(jié)論

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

學(xué)習(xí)模型，構(gòu)成增量式極端隨機(jī)森林，用于TLD算法中，提出基于改進(jìn)的隨機(jī)森林TLD目標(biāo)跟蹤方法。實驗首先驗證了本文算法時間開銷低、分類準(zhǔn)確性高，其次進(jìn)行目標(biāo)跟蹤實驗，結(jié)果表明，本文方法對于復(fù)雜情況下的目標(biāo)跟蹤準(zhǔn)確，穩(wěn)定性強(qiáng)。但本文方法只進(jìn)行了單目跟蹤，還要進(jìn)一步處理，實現(xiàn)多目標(biāo)跟蹤。

參考文獻(xiàn)：

[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] 彭爽, 彭曉明. 基于高效多示例學(xué)習(xí)的目標(biāo)跟蹤[J]. 計算機(jī)應(yīng)用, 2015,35( 2) : 466 -469, 475.

[5] 李想，汪榮貴，楊娟. 基于示例選擇的目標(biāo)跟蹤改進(jìn)算法[J]. 計算機(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] 王愛平，萬國偉，程志全，等. 支持在線學(xué)習(xí)的增量式極端隨機(jī)森林分類器拳[J].軟件學(xué)報，2011,22(9):2059-2074.

(責(zé)任編輯王楠楠)

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

基金項目：中央高?；究蒲袠I(yè)務(wù)費(fèi)專項資金資助項目(DC201502060303，DC201501075)。

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

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

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：A