基于改進(jìn)霍夫森林框架的多目標(biāo)跟蹤算法

高慶吉　霍璐　牛國臣

摘要：針對單目視覺對多個(gè)相似的目標(biāo)跟蹤因遮擋等因素影響而失效的問題，提出一種基于改進(jìn)霍夫森林框架的多目標(biāo)跟蹤算法。在將多目標(biāo)跟蹤問題歸結(jié)為基于目標(biāo)檢測的軌跡關(guān)聯(lián)過程基礎(chǔ)上，通過引入在線學(xué)習(xí)霍夫森林框架將軌跡關(guān)聯(lián)計(jì)算轉(zhuǎn)化為最大后驗(yàn)概率（MAP）問題。通過在線采集多目標(biāo)樣本、提取目標(biāo)外觀和運(yùn)動特征構(gòu)建霍夫森林，進(jìn)行森林訓(xùn)練得到軌跡關(guān)聯(lián)概率，從而關(guān)聯(lián)多目標(biāo)軌跡；而引入低秩逼近Hankel矩陣進(jìn)行軌跡校驗(yàn)，修復(fù)了誤匹配的軌跡，改進(jìn)了在線更新訓(xùn)練樣本算法的效能。實(shí)驗(yàn)表明，軌跡誤匹配率顯著改善，能有效提高單目攝像機(jī)對多個(gè)相似目標(biāo)有遮擋情況下跟蹤的準(zhǔn)確性和魯棒性。

關(guān)鍵詞：多目標(biāo)跟蹤；在線學(xué)習(xí)；霍夫森林；軌跡關(guān)聯(lián)；Hankel矩陣；相似目標(biāo)

中圖分類號：TP391.41

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

0引言

近年來，基于視覺的多目標(biāo)識別和跟蹤成為研究熱點(diǎn)，但由于單攝像機(jī)視野受限，容易出現(xiàn)目標(biāo)偶爾移出視野或被遮擋等問題，且視距較遠(yuǎn)或目標(biāo)本身極為相似時(shí)跟蹤容易出錯，使得這方面研究尤為重要。目前廣泛采用的方法是使用高質(zhì)量的視覺目標(biāo)識別方法逐幀檢測目標(biāo)，然后用在線或者離線方式將檢測到的目標(biāo)信息關(guān)聯(lián)成軌跡以實(shí)現(xiàn)跟蹤，其軌跡關(guān)聯(lián)通常是基于外觀和位置相似度進(jìn)行[1-3]；另有采用多通道核相關(guān)濾波器進(jìn)行樣本訓(xùn)練的實(shí)時(shí)跟蹤算法[4-5]，對目標(biāo)尺寸和外觀變化具有很好魯棒性。然而，這些算法在目標(biāo)外觀相似度高、無先驗(yàn)運(yùn)動模型、目標(biāo)快速運(yùn)動等情況下失效率較高。

文獻(xiàn)[6]提出通過卡爾曼濾波或者粒子濾波預(yù)測目標(biāo)位置，關(guān)聯(lián)距離最近的目標(biāo)來實(shí)現(xiàn)多目標(biāo)跟蹤；但是該方法需要有先驗(yàn)的目標(biāo)運(yùn)動模型，而實(shí)際情況中很多時(shí)候目標(biāo)運(yùn)動模型是隨時(shí)變動或未知的，且當(dāng)多個(gè)目標(biāo)彼此很接近時(shí)這類算法很難對不同目標(biāo)進(jìn)行正確區(qū)分。文獻(xiàn)[7]使用在線學(xué)習(xí)框架進(jìn)行多目標(biāo)跟蹤，通過在線搜集樣本，并引入目標(biāo)外觀特征和運(yùn)動特征來構(gòu)建霍夫森林，使用統(tǒng)計(jì)的方法區(qū)分不同軌跡，并關(guān)聯(lián)成為長軌跡，以此進(jìn)行跟蹤；該方法運(yùn)算速度快，可在線實(shí)現(xiàn)，對目標(biāo)外觀變化有一定魯棒性，對目標(biāo)位置預(yù)測能力強(qiáng)，但在多相似目標(biāo)情況下跟蹤準(zhǔn)確度較差。文獻(xiàn)[8]提出一種基于潛在動態(tài)模型復(fù)雜度進(jìn)行軌跡關(guān)聯(lián)的方法，該方法無需先驗(yàn)運(yùn)動模型，可以有效地處理多相似目標(biāo)的運(yùn)動跟蹤；但計(jì)算復(fù)雜，且完全不考慮目標(biāo)外觀因素。

針對上述問題，對在線學(xué)習(xí)算法和關(guān)聯(lián)矩陣進(jìn)行深入研究，提出了改進(jìn)霍夫森林（Improved Hough Forest， I-HF）算法。該算法擬引入在線學(xué)習(xí)霍夫森林框架，對多目標(biāo)外觀和運(yùn)動模型進(jìn)行學(xué)習(xí)和跟蹤，利用低秩逼近Hankel矩陣方法對霍夫森林學(xué)習(xí)中的錯誤軌跡匹配進(jìn)行校驗(yàn)，并修復(fù)誤匹配軌跡，以此來更新學(xué)習(xí)模型，提高跟蹤精度，并提高對多相似目標(biāo)跟蹤的魯棒性。該算法有效提高了單攝像機(jī)對多相似目標(biāo)跟蹤及其遮擋情況的處理能力。

1改進(jìn)霍夫森林算法框架

霍夫森林[9]是隨機(jī)森林的一種改進(jìn)算法，由多棵互相獨(dú)立的決策樹組成，在樹的生長過程及訓(xùn)練樣本中加入外觀和位置偏移信息，并提出了兩種不確定性度量方法用于節(jié)點(diǎn)分裂。本文在此基礎(chǔ)上擬使用低秩Hankel矩陣方法對霍夫森林訓(xùn)練輸出的軌跡關(guān)聯(lián)進(jìn)行校驗(yàn)，并修復(fù)補(bǔ)全軌跡，更新霍夫森林以提高算法跟蹤準(zhǔn)確度。算法框圖如圖1所示，在線學(xué)習(xí)霍夫森林包括五部分：樣本采集、特征提取、森林學(xué)習(xí)、結(jié)果修復(fù)和訓(xùn)練樣本更新。在線采集多目標(biāo)樣本用于初始構(gòu)建霍夫森林，讀入下一幀視頻進(jìn)行森林訓(xùn)練得到軌跡關(guān)聯(lián)概率，后進(jìn)行軌跡校驗(yàn)，如關(guān)聯(lián)有誤則修復(fù)軌跡并重新采集樣本，更新霍夫森林，否則繼續(xù)下一幀目標(biāo)提取和森林訓(xùn)練，往復(fù)直至視頻終止。

1.1霍夫森林樣本采集

基于可靠的目標(biāo)檢測信息，將相鄰幀的多目標(biāo)信息進(jìn)行低層關(guān)聯(lián)[3]，形成短軌跡。樣本采集利用時(shí)間滑窗及軌跡的時(shí)空約束進(jìn)行。軌跡時(shí)空約束基于兩個(gè)假設(shè)[6]：1）同一軌跡線上檢測到的目標(biāo)是同一目標(biāo)；2）同一時(shí)間兩個(gè)不同軌跡上

的檢測屬于不同目標(biāo)。同一短軌跡鏈上的不同檢測目標(biāo)之間

為正關(guān)聯(lián)，樣本采集示意圖如圖2所示，（a）為連續(xù)十幀圖像檢測結(jié)果，進(jìn)行低層關(guān)聯(lián)后如（b）所示，同一軌跡鏈上的檢測目標(biāo)1與檢測目標(biāo)3屬于正關(guān)聯(lián)；鄰近或同一時(shí)間T不同軌跡上的關(guān)聯(lián)屬于負(fù)關(guān)聯(lián)，如檢測目標(biāo)3與檢測目標(biāo)5，檢測目標(biāo)1與檢測目標(biāo)7的關(guān)聯(lián)為負(fù)關(guān)聯(lián)，以此類推采集正負(fù)樣本如圖（c）所示，其中+1表示正樣本，-1表示負(fù)樣本。

1.2目標(biāo)特征提取

采樣后需要提取出樣本的外觀特征和運(yùn)動特征，以此作為霍夫森林的樣本輸入。這里使用文獻(xiàn)[10]提出的時(shí)空關(guān)聯(lián)方法進(jìn)行運(yùn)動特征提取，即假設(shè)相鄰兩幀間目標(biāo)的運(yùn)動為線性運(yùn)動，將檢測到的目標(biāo)全局位置與線性模型估計(jì)出的全局位置作差，以此來度量運(yùn)動軌跡間的一致性。在霍夫森林訓(xùn)練階段，運(yùn)動特征是由同一軌跡上不同時(shí)刻檢測目標(biāo)的位置補(bǔ)償來描述的；在霍夫森林測試階段，運(yùn)動特征由可能的匹配對間的位置補(bǔ)償來定義。

2軌跡修復(fù)

由于當(dāng)前訓(xùn)練樣本是基于前一階段狀態(tài)，則可能引入誤差，造成錯誤關(guān)聯(lián)軌跡，而在此基礎(chǔ)上繼續(xù)跟蹤，之后的目標(biāo)跟蹤都將出錯，就造成了軌跡漂移問題。為解決這一問題，需要對已匹配軌跡進(jìn)行軌跡校驗(yàn)和修復(fù)。本文采用Hankel矩陣方法來識別前一階段的鏈接錯誤，然后基于修正后的軌跡重新采集訓(xùn)練樣本。

在無噪聲情況下，Hankel矩陣的秩可以很好地反映一個(gè)模型的復(fù)雜度，但如有噪聲存在，則會大大增加矩陣的秩甚至始終滿秩，因此一個(gè)主要挑戰(zhàn)是必須估計(jì)噪聲的秩和不完備結(jié)構(gòu)矩陣的秩。根據(jù)文獻(xiàn)[11] 的Hankel矩陣秩最優(yōu)化可以精確地解決軌跡縫合問題；文獻(xiàn)[8]對其進(jìn)行了改進(jìn)，使用牛頓迭代法求解Hankel矩陣的低秩逼近，并引入數(shù)據(jù)失效指示矩陣來修復(fù)丟失軌跡數(shù)據(jù)?；诖耍疚氖褂肏ankel低秩逼近方法來校驗(yàn)已完成的軌跡匹配。

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

3.1實(shí)驗(yàn)數(shù)據(jù)和評價(jià)值指標(biāo)

為驗(yàn)證本文提出方法的可行性，實(shí)驗(yàn)采用兩個(gè)視頻進(jìn)行驗(yàn)證，第一個(gè)視頻來自國際空中機(jī)器人大賽第七代任務(wù)，第二個(gè)視頻是文獻(xiàn)[8]中用到的數(shù)據(jù)集。視頻中目標(biāo)有相似外形、遮擋、高速運(yùn)動等情況。為評價(jià)跟蹤性能，目標(biāo)特征采用文獻(xiàn)[12]標(biāo)記，算法參數(shù)設(shè)置為10棵最大深度為15的樹，每個(gè)最優(yōu)分裂進(jìn)行200次隨機(jī)分裂測試。實(shí)驗(yàn)平臺為Matlab，采用中心位置偏差（Center Position Error， CPE）來度量跟蹤算法精確度。計(jì)算公式如（11）：

基于以上兩個(gè)視頻，分別對比了本文提出的改進(jìn)霍夫森林（I-HF）算法和傳統(tǒng)霍夫森林（Hough Forest， HF）算法的CPE，結(jié)果如圖5、6所示。由圖5可知，視頻一中，在第200幀之前HF算法與I-HF算法得到中心位置偏差基本接近，表明兩算法進(jìn)度相近，而在第300幀之后，HF算法跟蹤偏差越來越大，而I-HF算法只存在較小偏差波動，但仍然能正確跟蹤目標(biāo)；由圖6可知，視頻二中，在第20幀、50幀、80幀左右HF跟蹤方法的位置偏差有較大波動，目標(biāo)軌跡關(guān)聯(lián)錯誤率較高，而I-HF由于引入了低秩Hankel矩陣方法進(jìn)行軌跡修復(fù)，位置偏差波動小。

基于以上兩個(gè)視頻，分別對比了本文的I-HF算法和文獻(xiàn)[10]提出的基于條件隨機(jī)場（Conditional Random Field， CRF）的跟蹤算法，結(jié)果如表3所示。觀察指標(biāo)MMR，視頻一中I-HF算法比基于CRF的跟蹤算法小1.4，視頻二中比基于CRF的跟蹤算法小6.3，兩實(shí)驗(yàn)中I-HF的平均軌跡誤匹配率僅為基于CRF的跟蹤算法的25.5%左右，可見在不同數(shù)據(jù)集中，I-HF的軌跡匹配性能都明顯優(yōu)于基于CRF的跟蹤算法。對比兩個(gè)視頻中同一算法數(shù)據(jù)發(fā)現(xiàn)，由于視頻二中目標(biāo)相似度更高，使得基于CRF的跟蹤算法軌跡誤匹配率MMR明顯增高，而I-HF在兩個(gè)視頻中表現(xiàn)則相對穩(wěn)定。觀察指標(biāo)FNR，視頻一中本文的I-HF算法FNR值上比CRF小0.37，視頻二中小0.1，表明I-HF漏跟蹤略率優(yōu)于基于CRF的跟蹤算法。兩算法FPR值相當(dāng)。

綜上，實(shí)驗(yàn)結(jié)果表明I-HF算法比HF算法的跟蹤精度高，與基于CRF的跟蹤算法相比能有效提高多目標(biāo)跟蹤準(zhǔn)確度，對多相似目標(biāo)、遮擋等挑戰(zhàn)有良好的表現(xiàn)，具有較高魯棒性。

4結(jié)語

針對單目視覺對多個(gè)相似目標(biāo)的跟蹤問題，研究了基于改進(jìn)霍夫森林框架的算法。以多個(gè)相似目標(biāo)外觀和運(yùn)動信息的估計(jì)為基礎(chǔ)，首先計(jì)算軌跡間關(guān)聯(lián)度。針對霍夫森林框架跟蹤中目標(biāo)軌跡誤匹配現(xiàn)象，引入了低秩逼近Hankel矩陣改進(jìn)校驗(yàn)軌跡關(guān)聯(lián)準(zhǔn)確性，可降低檢測噪聲、平滑軌跡、并更新在線學(xué)習(xí)訓(xùn)練樣本。改進(jìn)算法跟蹤精度和準(zhǔn)確程度比傳統(tǒng)的基于霍夫森林框架算法有明顯提升，對多相似目標(biāo)遮擋、光照變化等情況有很好的魯棒性。

參考文獻(xiàn)：

[1]BENFOLD B， REID I. Stable multi-target tracking in real-time surveillance video [C]// CVPR 11： Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2011： 3457-3464.

[2]COLLINS R T. Multitarget data association with higher-order motion models [C]// CVPR 12： Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2012： 1744-1751.

[3]HUANG C， WU B， NEVATIA R. Robust object tracking by hierarchical association of detection responses [C]// ECCV 08： Proceedings of the 10th European Conference on Computer Vision， LNCS 5303. Berlin： Springer-Verlag， 2008： 788-801.

[4]胡昭華，邢衛(wèi)國，何軍，等.多通道核相關(guān)濾波的實(shí)時(shí)跟蹤方法[J].計(jì)算機(jī)應(yīng)用，2015，35（12）：3544-3549. （HU Z H， XING W G， HE J， et al. Real-time object tracking method based on multi-channel kernel correlation filter [J]. Journal of Computer Applications， 2015， 35（12）： 3544-3549.）

[5]余禮楊，范春曉，明悅.改進(jìn)的核相關(guān)濾波器目標(biāo)跟蹤算法[J].計(jì)算機(jī)應(yīng)用，2015，35（12）：3550-3554. （YU L Y， FAN C X， MING Y. Improved target tracking algorithm based on kernelized correlation filter [J]. Journal of Computer Applications， 2015， 35（12）： 3550-3554.）

[6]KUO C-H， HUANG C， NEVATIA R. Multi-target tracking by on-line learned discriminative appearance models [C]// CVPR 10： Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2010： 685-692.

[7]XIANG J， SANG N， HOU J. An online learned Hough forest model for multi-target tracking [C]// ICIP 2014： Proceedings of the 2014 IEEE International Conference on Image Processing. Piscataway， NJ： IEEE， 2014： 2398-2402.

[8]

DICLE C， CAMPS O I， SZNAIER M. The way they move： tracking multiple targets with similar appearance [C]// ICCV 13： Proceedings of the 2013 IEEE International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2013： 2304-2311

[9]GALL J， LEMPITSKY V. Class-specific Hough forests for object detection [C]// CVPR 2009： Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2009： 1022-1029.

[10]NEVATIA R. An online learned CRF model for multi-target tracking [C]// CVPR 12： Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2012：2034-2041.

[11]DING T， SZNAIER M， CAMPS O. Fast track matching and event detection [C]// CVPR 08： Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2008： 1-8.

[12]DOLLR P， WOJEK C， SCHIELE B， et al. Pedestrian detection： an evaluation of the state of the art [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（4）： 743-761.