侯建華，邊群星，項 俊

(中南民族大學(xué) 電子信息工程學(xué)院，武漢 430074)

基于在線學(xué)習(xí)判別性外觀模型的多目標(biāo)跟蹤算法

侯建華，邊群星，項 俊

(中南民族大學(xué) 電子信息工程學(xué)院，武漢 430074)

在基于檢測的跟蹤框架下，設(shè)計了一種在線學(xué)習(xí)的判別性外觀模型并應(yīng)用于多目標(biāo)跟蹤.對檢測器輸出的相鄰幀間檢測響應(yīng)做保守關(guān)聯(lián)，生成短小可靠的軌跡片；利用目標(biāo)軌跡時空域約束條件，從軌跡片中提取訓(xùn)練樣本及特征；采用Adaboost算法在線生成目標(biāo)外觀的判別性模型，計算軌跡片之間的外觀相似度；最后采用匈牙利算法，經(jīng)過多次迭代得到每個目標(biāo)的完整軌跡.對實(shí)驗結(jié)果做了定量和定性分析，結(jié)果表明:所設(shè)計的算法提高了跟蹤精度，在復(fù)雜場景下能夠較好地完成多目標(biāo)跟蹤任務(wù).

多目標(biāo)跟蹤；軌跡片；外觀模型；Adaboost算法

近十年來，隨著目標(biāo)檢測技術(shù)快速發(fā)展，基于檢測的跟蹤方法[1-6]已成為當(dāng)前多目標(biāo)跟蹤領(lǐng)域研究熱點(diǎn)；該方法將多目標(biāo)跟蹤問題轉(zhuǎn)化為數(shù)據(jù)關(guān)聯(lián)問題，利用目標(biāo)檢測響應(yīng)所包含的外觀、運(yùn)動、位置等信息設(shè)計關(guān)聯(lián)模型，以此度量跡片間的連接概率(即相似度)，實(shí)現(xiàn)軌跡片最優(yōu)關(guān)聯(lián).Huang等人[6]提出的多級關(guān)聯(lián)是一種比較流行的方法，該方法先通過初級關(guān)聯(lián)得到可靠而短小的軌跡片，再通過逐級關(guān)聯(lián)方式，計算軌跡片間的連接概率，應(yīng)用Hungarian算法[8]得到最優(yōu)關(guān)聯(lián)解，逐步將短小軌跡片關(guān)聯(lián)為長的目標(biāo)軌跡.但文獻(xiàn)[6]使用基于顏色直方圖的外觀相似度，其外觀模型簡單，對位置相近、外觀相似的易混淆目標(biāo)區(qū)分性較差，在跟蹤過程中容易產(chǎn)生目標(biāo)軌跡間隙、及身份標(biāo)識混淆.

針對上述問題，本文提出了一種基于在線學(xué)習(xí)判別性外觀模型的多目標(biāo)跟蹤算法：利用目標(biāo)軌跡時空域約束條件，從短小軌跡片中采集訓(xùn)練樣本，分別提取顏色及紋理特征；采用Adaboost在線學(xué)習(xí)算法[7]訓(xùn)練分類器，構(gòu)建目標(biāo)判別性外觀模型，計算軌跡片之間的外觀相似度；利用Hungarian算法[8]對軌跡片多次迭代關(guān)聯(lián)，最終得到可靠的目標(biāo)完整軌跡.實(shí)驗結(jié)果表明在擁擠、遮擋頻繁發(fā)生的背景復(fù)雜中，該算法可以較好地實(shí)現(xiàn)準(zhǔn)確穩(wěn)定的目標(biāo)跟蹤.

1 訓(xùn)練樣本采集

為提高算法的有效性，采用滑動窗[5]處理模式，在每一個滑動窗內(nèi)，從短小軌跡片中提取目標(biāo)正負(fù)樣本.

1.1 短小軌跡片

設(shè)R={ri}代表檢測器輸出的檢測響應(yīng)集，其中第i個響應(yīng)為ri=(xi，yi，si，ti),(xi,yi)、si、ti分別表示目標(biāo)的位置、大小、所在幀序號.定義相鄰兩幀間兩個響應(yīng)ri與rj的連接概率如下：

(1)

其中Aappr(rj|ri)表示兩個檢測響應(yīng)的外觀親密度模型(即連接概率).設(shè)第k幀、k+1幀分別有m、n個響應(yīng)，按照(1)式構(gòu)造m×n的連接概率矩陣P.

采用文獻(xiàn)[6]提出的雙閾值關(guān)聯(lián)策略，將相鄰幀間的檢測響應(yīng)做保守關(guān)聯(lián)，生成短小可靠的軌跡片(tracklet).雙閾值策略如下：如果Pscore(rj|ri)大于門限θ1，并且比矩陣P的第i行、第j列中其他元素都大于門限θ2，則認(rèn)為檢測響應(yīng)ri與rj是相互關(guān)聯(lián)的，即屬于同一目標(biāo).公式化描述為：

(2)

1.2 訓(xùn)練樣本提取策略

圖1 訓(xùn)練樣本采集示意圖Fig.1 The diagram of obtaining training samples

2 目標(biāo)外觀描述及特征表達(dá)

2.1 目標(biāo)外觀描述

為了構(gòu)建魯棒的外觀模型，采用顏色和紋理特征，提取標(biāo)準(zhǔn)的顏色直方圖、HOG特征、協(xié)方差矩陣，分別描述目標(biāo)外觀的顏色、形狀、紋理信息.

(1)顏色直方圖.采用RGB顏色空間，將每個通道設(shè)置為8Bins，將三個通道直方圖串聯(lián)起來，組成一個24維顏色直方圖向量fRGB.

(2)HOG特征.根據(jù)文獻(xiàn)[10]，把目標(biāo)區(qū)域劃分為4個單元、每單元分8個方向統(tǒng)計，得到32維HOG特征向量fHOG.

(3)紋理特征.采用基于協(xié)方差的紋理特征描述[11]，該方法對于圖像紋理和目標(biāo)分類有很好的性能.描述符C與協(xié)方差矩陣對應(yīng)：

(3)

(4)

其中，μ、n分別表示檢測響應(yīng)區(qū)域灰度均值、像素個數(shù)，zk表示第k個像素的一階導(dǎo)和二階導(dǎo).

綜合以上三種特征，單個檢測響應(yīng)ri(即目標(biāo))的外觀描述子表示為{fRGBi,fHOGi,Ci}；

(5)

2.2 特征表達(dá)

首先考察檢測響應(yīng)ri、rj間的相似性向量.對于顏色直方圖和HOG特征，采用歐式距離進(jìn)行，表示為ρ(fRGBi,fRGBj)、ρ(fHOGi,fHOGj).對于紋理特征，采用文獻(xiàn)[11]提出的相似性距離：

(6)

其中λk(Ci,Cj)是廣義特征值.

檢測響應(yīng)ri、rj的相似性向量表示為：

h(ri,rj)=[ρ(fRGBi,fRGBj),ρ(fHOGi,fHOGj),σ(Ci,Cj)].

(7)

(8)

為方便描述，以下將h(ri,rj)記為h(xi)，其中xi代表樣本(即一對檢測響應(yīng)).樣本特征向量構(gòu)成的集合記為F={h(xi)}.

3 在線學(xué)習(xí)

(9)

基于Adaboost算法的外觀模型學(xué)習(xí)過程見算法1.其中，(xi,yi)為樣本集第i個樣本，yi∈{+1,-1)}，+1代表來自同一目標(biāo)檢測響應(yīng)對組成的正樣本，-1代表來自不同目標(biāo)檢測響應(yīng)對組成的負(fù)樣本；N為特征庫F中特征的數(shù)量，T為選取的弱分類器個數(shù)，實(shí)驗中T取40.

算法1：外觀模型學(xué)習(xí)

1) Input：正樣本集：S+=(xi,yi=1)，負(fù)樣本集：S-=(xi,yi=-1)；

End for

Setαt=αn*;ht=hn*.

樣本權(quán)重更新：wi=wi·exp[-αiyihi(xi)] 歸一化wi

End for

此外，考慮到目標(biāo)外觀的變化，在每個時間滑動窗內(nèi)重新獲取新的樣本，在線更新強(qiáng)分類器H(即外觀判別性模型).

綜合以上三節(jié)內(nèi)容，圖2給出了一個時間滑動窗內(nèi)的多目標(biāo)跟蹤算法框圖.

2)利用時空域約束條件，從TL集中生成訓(xùn)練樣本，提取樣本和軌跡片特征；

3)訓(xùn)練樣本送至Adaboost分類器，在線學(xué)習(xí)強(qiáng)分類器H，得到判別性外觀模型；

4)強(qiáng)分類器H計算兩兩軌跡片之間的相似性H(Ai,Aj)，利用Hungarian算法實(shí)現(xiàn)軌跡片關(guān)聯(lián)；多次重復(fù)該步驟，得到該時間滑動窗內(nèi)的目標(biāo)軌跡.

通過移動時間滑動窗，重復(fù)上述步驟，最終得到視頻序列中多目標(biāo)的完整軌跡T={Tk}.

圖2 時間滑動窗內(nèi)多目標(biāo)跟蹤算法系統(tǒng)框架Fig.2 The system framework of muti-target tracking algorithm in time sliding window

4 實(shí)驗結(jié)果與分析

實(shí)驗采用TUD數(shù)據(jù)庫(包含TUD-Stadtmitte、TUD-Crossing兩個視頻序列)和PET2009數(shù)據(jù)庫中的S2L1視頻序列，跟蹤目標(biāo)為行人.

采用文獻(xiàn)[3,12]定義的標(biāo)準(zhǔn)來評估本文跟蹤算法的性能，包含多個評估指標(biāo)，如表1所示(“↑”表示其值越大、對應(yīng)跟蹤效果越好；“↓”表示其值越小、對應(yīng)跟蹤效果越好).

為了保證算法評價的公平性，檢測結(jié)果(即跟蹤算法的輸入)均來自文獻(xiàn)[14,15]，其中TUD數(shù)據(jù)庫采用DPM檢測器，PET2009數(shù)據(jù)庫采用HOG+SVM檢測器.參與比較的算法包括文獻(xiàn)[13,14]中的兩種方法.

表1 多目標(biāo)跟蹤性能指標(biāo)Tab.1 Multi-target tracking performance index

表2、表3分別給出了在TUD數(shù)據(jù)庫、PET2009數(shù)據(jù)庫上的實(shí)驗結(jié)果.實(shí)驗中的3個視頻序列均具有背景復(fù)雜、目標(biāo)間頻繁發(fā)生遮擋的特點(diǎn).由表2、表3可知，本文算法在多個性能指標(biāo)上都優(yōu)于文獻(xiàn)[13,14]算法，例如在FAF、Frag、IDS指標(biāo)上，本文算法的優(yōu)勢明顯.

表2 在TUD數(shù)據(jù)庫上的實(shí)驗結(jié)果比較Tab.2 Comparison results on TUD dataset

表3 在PET2009數(shù)據(jù)庫上的實(shí)驗結(jié)果比較Tab.3 Comparison results on PET2009 dataset

圖3給出了本文算法在TUD-Stadtmitte上的跟蹤效果圖.其中第7024幀中目標(biāo)4、5(圖中向上箭頭)并肩行走，在第7051幀目標(biāo)6、7(圖中向下箭頭)相反方向朝目標(biāo)4、5走來，被目標(biāo)4、5嚴(yán)重遮擋，本文算法可處理此遮擋問題、實(shí)現(xiàn)對目標(biāo)的正確跟蹤；另外，4號目標(biāo)從第7024幀到7068幀行走過程中，背景變化較大，本文算法也可以很好地克服.

圖3 TUD-Stadtmitte跟蹤蹤的結(jié)果Fig.3 Tracking results on TUD-Stadtmitte

圖4是本文算法在TUD-Crossing上的跟蹤效果圖.該視頻序列中由車輛運(yùn)動導(dǎo)致背景干擾嚴(yán)重.第38幀目標(biāo)2、5、6、9至左向右行走(圖中向上箭頭)，其中目標(biāo)5、9并肩行走，被從右往左迎面行走的目標(biāo)8(圖中向下箭頭)依次遮擋，到第85幀遮擋結(jié)束；目標(biāo)身份沒有發(fā)生混淆(見第85幀5、6、9、8)，始終保持對目標(biāo)的穩(wěn)定跟蹤.

圖4 TUD-Crossing跟蹤的結(jié)果Fig.4 Tracking results on TUD-Crossing

圖5是本文算法在PET2009中S2L1視頻序列上的跟蹤效果圖.攝像機(jī)由上向下拍攝，視頻場景中目標(biāo)之間身體形態(tài)和外觀相似、相互遮擋，且場景中心存在路燈桿對行人的遮擋發(fā)生.在第104幀中目標(biāo)1、7和10(圖中向上箭頭)之間發(fā)生嚴(yán)重遮擋，目標(biāo)4和5肩并肩行走(圖中向上箭頭)；到137幀時目標(biāo)1和7，4和5均被準(zhǔn)確跟蹤；在528幀到566幀中，目標(biāo)28和29肩并肩行走、相互發(fā)生遮擋(圖中向下箭頭)，本文算法始終保持對其準(zhǔn)確穩(wěn)定的跟蹤.圖5表明本文算法對位置相近、外觀相似的目標(biāo)具有較好的鑒別能力.

5 結(jié)語

本文設(shè)計并實(shí)現(xiàn)了一種基于在線學(xué)習(xí)判別性外觀模的多目標(biāo)跟蹤算法，該算法以時間滑動窗為基本關(guān)聯(lián)單位，首先通過初級關(guān)聯(lián)生成短小可靠的軌跡片；利用目標(biāo)軌跡時空域約束條件從中提取訓(xùn)練樣本及特征；采用Adaboost算法在線生成目標(biāo)外觀的判別性模型，計算軌跡片之間的外觀相似度；最后采用匈牙利算法、經(jīng)過多次迭代得到每個目標(biāo)的完整軌跡.實(shí)驗結(jié)果表明，針對復(fù)雜場景中的背景干擾、目標(biāo)遮擋、位置相近、外觀相似的易混淆目標(biāo)等，該算法均具有較好的處理能力.然而，本文算法未考慮長時間多目標(biāo)之間的遮擋，后期可以引入多個目標(biāo)間的遮擋處理機(jī)制，進(jìn)一步提高跟蹤性能.

圖5 PET2009中S2L1視頻序列跟蹤的結(jié)果Fig.5 Tracking results of S2L1 video sequence in PET2009.

[1] Yang B, Nevatia R.Multi-target tracking by online learning a CRF model of appearance and motion patterns [J].International Journal of Computer Vision, 2014, 2(107):203-217.

[2] Yang B, Nevatia R.Online learned discriminative part-based appearance models for multi-human tracking [C]// ECCV.Proceedings of European Conference on Computer Vision.Firenze: ECCV, 2012:1-14.

[3] Yang B，Nevatia R.Multi-target tracking by online learning of non-linear motion patterns and robust appearance models [C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.Washington D C: CVPR, 2012:1918-1925.

[4] Yang B, Huang C, Nevatia R.Learning affinities and dependencies for multi-target tracking using a CRF model[C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.Piscataway: CVPR, 2011: 1233-1240.

[5] 黃 奇, 項 俊, 侯建華,等.聯(lián)合特征融合和判別性外觀模型的多目標(biāo)跟蹤 [J].中國圖象圖形學(xué)報, 2015, 20 (9): 1188-1198.

[6] Huang C, Wu B, Nevatia R.Robust object tracking by hierarchical association of detection responses [C]// ECCV.Proceedings of European Conference on Computer Vision.Marseille: ECCV, 2008: 788-801.

[7] Schapire R E, Singer Y.Improved Boosting Algorithms Using Confidence-rated Predictions [J].Machine Learning, 1999, 37 (3):297-336.

[8] Kuhn H W.The Hungarian method for the assignment problem [J].Naval Research Logistics Quarterly, 1955, 2(1):83-97.

[9] Anton M, Stefan R, Konrad S.Stefan R, Konrad Schindler.Continuous Energy Minimization for Multitarget Tracking [J].IEEE Transactions on Pattern Analysis and Machine Interlligence, 2014, 36(1):58-72.

[10] Dalal N, Triggs B.Histograms of oriented gradients for human detection [C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.San Diego: CVPR, 2005: 886-893.

[11] Tuzel O, Porikli F, Meer P.Region covariance: A fast descriptor for detection and classification [C]//ECCV.Proceedings of European Conference on Computer Vision.Graz: ECCV, 2006: 589-600.

[12] Li Y, Huang C, Nevatia R.Learning to associate: HybridBoosted multi-target tracker for crowded scene [C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.Piscataway: CVPR, 2009:2953-2960.

[13] Andriyenko A, Schindler K , Roth S.Discrete-continuous optimization for multi-target tracking [C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.Washington D C: CVPR, 2012:1926-1933.

[14] Andriyenko A, Schindler K.Multi-target tracking by continuous energy minimization [C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.Piscataway: CVPR, 2011:1265-1272.

[15] Yang B, Nevatia R.An online learned CRF model for multi-target tracking[C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.Washington D C:CVPR, 2012:2034-2041.

Multi-Object Tracking Algorithm Based on Online Learned Discriminative Appearance Model

HouJianhua,BianQunxing,XiangJun

(College of Electronic Information Engineering, South-Central University for Nationalities, Wuhan 430074)

An online learned discriminative appearance models is designed for multi-object tracking (MOT) under the tracking by detection framework.Firstly, by low level association strategy, short yet reliable tracklets are generated among detection responses which are produced by a pre-trained detector.Then, the training samples are collected by using spatial-temporal constraints of target trajectory, and features are extracted for representation of the appearance model.We adopt online Adaboost algorithm to train the discriminative appearance model, by which the appearance similarity between tracklets can be calculated.Finally, the Hungarian algorithm is used via several iterations to obtain the complete trajectory for each target.Experiments are conducted quantitatively and qualitatively.The results show that the proposed method has improved the tracking accuracy, and has satisfactory performance in complex scene.

multi-object tracking;tracklets;appearance model;Adaboost algorithm

2017-01-16

侯建華( 1964-)，男，教授，博士，研究方向: 計算機(jī)視覺、模式識別，E-mail: hou8781@126.com

國家自然科學(xué)基金資助項目( 61671484);中南民族大學(xué)中央高校基本科研業(yè)務(wù)費(fèi)專項資金( CZW15013)

TP391.41

A

1672-4321(2017)01-0081-06