張　丹，陳興文，趙姝穎

(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)

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

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

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

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

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

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

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

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

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

極端隨機(jī)森林每棵決策樹的決策點(diǎn)分裂測試閾值是隨機(jī)選擇的，不是以某一特征進(jìn)行設(shè)定，保證了樣本的豐富性，極端隨機(jī)森林分類器在分類精度和訓(xùn)練時(shí)間開銷等方面的性能較好，但采用的不是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ù)量最多的樣本相對(duì)于數(shù)量最多的樣本的比例。

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

(1)

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

(2)

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

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

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

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

(a) 分類錯(cuò)誤率圖

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

(c) 時(shí)間對(duì)比圖

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

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

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

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

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

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

3實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

從圖3-圖5中可以看出視頻初始幀的跟蹤兩種算法都較為準(zhǔn)確，但到后續(xù)幀中，由于目標(biāo)的快速轉(zhuǎn)動(dòng)、遮擋、尺度變化等因素的干擾，原始方法出現(xiàn)了分類不精確的現(xiàn)象，跟蹤邊框出現(xiàn)了一定程度的偏移，而本文方法進(jìn)行了較為準(zhǔn)確的跟蹤。本文采用文獻(xiàn)[10]的評(píng)價(jià)方法，如果目標(biāo)物體有25 %以上沒能被跟蹤，那么這幀數(shù)據(jù)被認(rèn)為跟蹤錯(cuò)誤，統(tǒng)計(jì)結(jié)果見表2。從表中可以看出，本文方法的跟蹤效果更準(zhǔn)確，對(duì)于目標(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)跟蹤方法。實(shí)驗(yàn)首先驗(yàn)證了本文算法時(shí)間開銷低、分類準(zhǔn)確性高，其次進(jìn)行目標(biāo)跟蹤實(shí)驗(yàn)，結(jié)果表明，本文方法對(duì)于復(fù)雜情況下的目標(biāo)跟蹤準(zhǔn)確，穩(wěn)定性強(qiáng)。但本文方法只進(jìn)行了單目跟蹤，還要進(jìn)一步處理，實(shí)現(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ì)算機(jī)應(yīng)用, 2015,35( 2) : 466 -469, 475.

[5] 李想，汪榮貴，楊娟. 基于示例選擇的目標(biāo)跟蹤改進(jìn)算法[J]. 計(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é)報(bào)，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

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

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

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

中圖分類號(hào)：TP391

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