姜明新， 王洪玉

（1.大連理工大學(xué)信息與通信工程學(xué)院，遼寧大連 116024；2.大連民族學(xué)院信息與通信工程學(xué)院，遼寧大連 116602）

基于特征分組的在線目標(biāo)跟蹤算法

姜明新＊1，2， 王洪玉1

（1.大連理工大學(xué)信息與通信工程學(xué)院，遼寧大連 116024；2.大連民族學(xué)院信息與通信工程學(xué)院，遼寧大連 116602）

在線目標(biāo)跟蹤是計(jì)算機(jī)視覺領(lǐng)域的一個(gè)具有挑戰(zhàn)性的問題.提出了一種基于特征分組的在線目標(biāo)跟蹤算法.首先，利用像素點(diǎn)在多幀的方差對(duì)模板庫中的目標(biāo)模板進(jìn)行特征分組.然后，利用主要特征圖像和次要特征圖像學(xué)習(xí)投影矩陣P，對(duì)樣本進(jìn)行投影.最后，利用最小誤差法得出當(dāng)前幀的跟蹤結(jié)果.與其他典型算法相比，該算法對(duì)目標(biāo)的異常變化具有很強(qiáng)的魯棒性.

在線目標(biāo)跟蹤；線性子空間學(xué)習(xí)；特征分組；模板更新

0 引 言

基于視頻的在線目標(biāo)跟蹤技術(shù)是計(jì)算機(jī)視覺領(lǐng)域的關(guān)鍵問題之一，在人機(jī)交互、視頻監(jiān)控、智能交通、行為識(shí)別等領(lǐng)域都有著廣泛的應(yīng)用.很多學(xué)者做了這方面的研究［1－3］，并且取得了一些進(jìn)展.然而，當(dāng)發(fā)生遮擋、旋轉(zhuǎn)、尺度變化、光照變化等異常變化時(shí)，目標(biāo)的外觀模型也會(huì)發(fā)生較大的變化，因此，如何建立一個(gè)魯棒性強(qiáng)的目標(biāo)跟蹤器就成為了一個(gè)具有挑戰(zhàn)性的問題.

想要建立一個(gè)魯棒性強(qiáng)的目標(biāo)跟蹤器，就要采用一個(gè)能夠在跟蹤過程中反映目標(biāo)變化的在線外觀模型.線性子空間學(xué)習(xí)是一種典型的降維和特征提取技術(shù)，在模式識(shí)別領(lǐng)域已經(jīng)得到了成功的應(yīng)用.近年來，利用線性子空間學(xué)習(xí)的方法進(jìn)行視頻目標(biāo)跟蹤已經(jīng)吸引了許多學(xué)者的注意［4－5］，其中文獻(xiàn)［4］提出的IVT（incremental visual tracking）跟蹤器比較有影響力，該算法對(duì)光照變化、尺度變化等的魯棒性較強(qiáng)，但是當(dāng)目標(biāo)發(fā)生部分遮擋時(shí)，跟蹤器的性能比較脆弱.文獻(xiàn)［5］提出了一種基于半監(jiān)督學(xué)習(xí)的在線跟蹤器，僅對(duì)第一幀采集的樣本賦予標(biāo)簽，其余幀的訓(xùn)練樣本看作是無標(biāo)簽的，該方法同樣在部分遮擋時(shí)會(huì)發(fā)生跟蹤失敗.

基于以上分析，本文提出一種基于特征分組的在線目標(biāo)跟蹤算法，對(duì)樣本中的像素進(jìn)行分組，利用分組后的結(jié)果計(jì)算映射矩陣.根據(jù)狀態(tài)轉(zhuǎn)移模型選取樣本，對(duì)樣本進(jìn)行映射，選取與上一幀跟蹤結(jié)果距離最短的作為本幀的跟蹤結(jié)果.

1 特征分組

首先，分析一下IVT跟蹤器［4］在目標(biāo)發(fā)生部分遮擋時(shí)魯棒性能差的原因.IVT跟蹤器是利用增量PCA算法對(duì)低維子空間的目標(biāo)模型進(jìn)行學(xué)習(xí)和更新，PCA的基本原理為

其中y為觀測(cè)向量，z為相應(yīng)的編碼向量，U為基向量，e為誤差向量.在PCA算法中，假設(shè)誤差向量e服從最小方差的高斯分布，因此，編碼向量z可以表示為z＝UTy，重建誤差則可以表示為.然而，當(dāng)目標(biāo)發(fā)生部分遮擋時(shí)，誤差向量e并不服從高斯分布，所以IVT跟蹤器在目標(biāo)發(fā)生部分遮擋時(shí)變得非常脆弱.

1.1 對(duì)目標(biāo)模板進(jìn)行特征分組

假設(shè)目標(biāo)模板庫由n個(gè)目標(biāo)模板tj組成，可以用矩陣T＝（tij）＝（t1t2…tn）∈Rd×n表示.其中tj∈Rd，dn.當(dāng)前幀中跟蹤結(jié)果圖像塊用y表示，y∈Rd.在實(shí)驗(yàn)過程中，取前n幀的跟蹤結(jié)果作為目標(biāo)模板庫中的初始模板.本文取模板數(shù)目n＝10，目標(biāo)模板的大小為32×32，則d＝1 024.

接下來，將每個(gè)目標(biāo)模板圖像tj（j＝1，2，…，n）分解為主要特征圖像和次要特征圖像.用表示目標(biāo)模板庫中像素tij在n幀內(nèi)的均值表示第τ幀像素tij的值，則像素tij的方差為

設(shè)定閾值σ1，如果像素tij的方差σij＜σ1，則將該像素點(diǎn)放入主要特征圖像.對(duì)目標(biāo)模板進(jìn)行特征分組后的結(jié)果如圖1所示.

圖1 特征分組的結(jié)果Fig.1 Results of feature grouping

1.2 計(jì)算投影矩陣

特征分組后，目標(biāo)模板庫中的每個(gè)目標(biāo)模板tj可以表示為tj＝＋（j＝1，2，…，n），則目標(biāo)模板庫矩陣可以表示為T＝Ta＋Tb.現(xiàn)有的線性子空間學(xué)習(xí)算法都是只利用主要特征圖像Ta來學(xué)習(xí)投影矩陣P，忽略了次要特征Tb對(duì)投影方向的影響.鑒于以上考慮，在特征分組后，利用Ta和Tb來學(xué)習(xí)投影矩陣P.這樣得到的投影矩陣P能在很好地保留主特征圖像能量的同時(shí)抑制次要特征圖像的能量，進(jìn)而減弱次要特征對(duì)跟蹤結(jié)果的影響.計(jì)算投影矩陣P的具體過程如下：

顯然，通過特征值分解可以得到投影矩陣P.

假如散布矩陣Sb不存在，Sa則成為全部訓(xùn)練樣本的總體散布矩陣S，那么目標(biāo)方程（6）則簡化為

可以看出，方程（7）是PCA算法的目標(biāo)方程.

2 狀態(tài)轉(zhuǎn)移模型

選取目標(biāo)的運(yùn)動(dòng)仿射變換參數(shù)作為狀態(tài)變量xt＝（xtytθtstαtt），其中xt、yt分別表示目標(biāo)在第t幀x、y方向上的平移，θt表示目標(biāo)在第t幀的旋轉(zhuǎn)角度，st表示目標(biāo)在第t幀變化的尺度，αt表示目標(biāo)在第t幀變化的縱橫比，t表示目標(biāo)在第t幀的傾斜方向.

為不失一般性，假設(shè)狀態(tài)轉(zhuǎn)移模型服從高斯分布，即

3 算法的實(shí)現(xiàn)與模板庫的更新

為了更直觀地描述本文提出的基于特征分組的在線目標(biāo)跟蹤算法，如圖2所示畫出算法的流程圖.

由于前n幀目標(biāo)變化很小，可以利用最短距離法實(shí)現(xiàn)快速跟蹤，取前n幀的跟蹤結(jié)果作為目標(biāo)模板庫中的初始模板，利用初始模板庫計(jì)算投影矩陣P.在n＋1幀到來時(shí)，根據(jù)狀態(tài)轉(zhuǎn)移模型，在上一幀目標(biāo)跟蹤結(jié)果的周圍選取N個(gè)樣本.對(duì)每個(gè)樣本進(jìn)行投影，計(jì)算投影后的結(jié)果與上一幀跟蹤結(jié)果投影后的距離，取距離最小的樣本作為本幀的跟蹤結(jié)果.

圖2 跟蹤算法的流程圖Fig.2 The flowchart of tracking algorithm

由于在目標(biāo)跟蹤的過程中會(huì)發(fā)生遮擋、旋轉(zhuǎn)等異常變化，更新目標(biāo)模板庫具有十分重要的作用.從第n＋1幀開始，將本幀跟蹤結(jié)果投影后的主特征圖像與目標(biāo)模板庫中的后n－1個(gè)模板的主特征圖像放在一起，計(jì)算這n幀主特征圖像像素點(diǎn)的方差.如果方差小于閾值，則將該像素點(diǎn)分組到主要特征圖像，然后把新得到的主特征圖像更新到模板庫中，舍棄原模板庫中第1個(gè)主特征圖像.次要特征圖像也做相應(yīng)的處理，這樣就完成了一次模板庫的更新，利用更新后的模板庫重新計(jì)算映射矩陣，進(jìn)而完成映射矩陣的更新.

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

為了說明基于特征分組的在線目標(biāo)跟蹤算法的魯棒性，選取多組公共測(cè)試視頻作為實(shí)驗(yàn)視頻，鑒于篇幅限制，只列舉其中5組視頻的實(shí)驗(yàn)結(jié)果.選取的實(shí)驗(yàn)測(cè)試視頻中的運(yùn)動(dòng)目標(biāo)分別發(fā)生了遮擋、旋轉(zhuǎn)、光線變化、尺度變化等異常變化.本文算法的實(shí)現(xiàn)基于Windows操作系統(tǒng)，采用MATLAB作為軟件平臺(tái)，計(jì)算機(jī)配置為AMD Athlon（tm）X2DualCore QL－62 2.00GHz，1.74 GB內(nèi)存.

為了評(píng)估本算法的性能，選用6種目前最具有代表性的典型跟蹤算法進(jìn)行了實(shí)驗(yàn)結(jié)果的對(duì)比.6種典型算法分別為IVT Tracker［4］、L1 Tracker［6］、PN Tracker［7］、VTD Tracker［8］、MIL Tracker［9］和Frag Tracker［10］.

針對(duì)5組實(shí)驗(yàn)測(cè)試視頻，本文提出的算法與6種典型算法的跟蹤結(jié)果對(duì)比如圖3～6所示，其中紅色跟蹤框?yàn)楸疚奶岢鏊惴ǖ母櫧Y(jié)果，其余6種典型算法的跟蹤結(jié)果分別用下列顏色的跟蹤框進(jìn)行表征：L1Tracker對(duì)應(yīng)綠色跟蹤框，IVT Tracker對(duì)應(yīng)深藍(lán)色跟蹤框，PN Tracker對(duì)應(yīng)黑色跟蹤框，VTD Tracker對(duì)應(yīng)黃色跟蹤框，MIL Tracker對(duì)應(yīng)粉色跟蹤框，F(xiàn)rag Tracker對(duì)應(yīng)淺藍(lán)色跟蹤框（由于印刷所限文中用深淺色區(qū)分）.

測(cè)試視頻Car4和Singer1中影響目標(biāo)跟蹤的因素主要有光照變化和尺度變化；測(cè)試視頻Lemming中影響目標(biāo)跟蹤的因素主要有平面外旋轉(zhuǎn)、背景干擾和尺度變化；測(cè)試視頻Car11的主要問題是光照變化、尺度變化和背景干擾.從圖3～6的視頻目標(biāo)跟蹤的實(shí)驗(yàn)結(jié)果可以看出，本文提出的基于特征分組的在線目標(biāo)跟蹤算法在目標(biāo)發(fā)生遮擋、旋轉(zhuǎn)、光線變化、尺度變化等異常變化時(shí)，能夠穩(wěn)定地跟蹤目標(biāo)，與其他幾種典型算法相比，表現(xiàn)出更好的準(zhǔn)確性和魯棒性.

不同算法的跟蹤誤差曲線結(jié)果對(duì)比如圖7所示.從圖7可以看出，本文提出的基于特征分組的在線目標(biāo)跟蹤算法的跟蹤誤差低于其他6種典型算法，獲得了較高的目標(biāo)跟蹤準(zhǔn)確度.

圖3 測(cè)試視頻Car4的跟蹤結(jié)果對(duì)比Fig.3 The comparison of tracking results for test video Car4

圖4 測(cè)試視頻Lemming的跟蹤結(jié)果對(duì)比Fig.4 The comparison of tracking results for test video Lemming

圖5 測(cè)試視頻Singer1的跟蹤結(jié)果對(duì)比Fig.5 The comparison of tracking results for test video Singer1

圖6 測(cè)試視頻Car11的跟蹤結(jié)果對(duì)比Fig.6 The comparison of tracking results for test video Car11

圖7 測(cè)試視頻跟蹤誤差曲線結(jié)果對(duì)比Fig.7 The comparison of tracking error curves results for test videos

5 結(jié) 論

本文通過對(duì)傳統(tǒng)的PCA算法的缺點(diǎn)進(jìn)行分析，提出了基于特征分組的在線目標(biāo)跟蹤算法，對(duì)樣本中的像素進(jìn)行分組，利用分組后的結(jié)果計(jì)算映射矩陣.根據(jù)狀態(tài)轉(zhuǎn)移模型選取樣本，對(duì)樣本進(jìn)行映射，選取與上一幀跟蹤結(jié)果距離最短的作為本幀的跟蹤結(jié)果.本文提出的跟蹤算法，在很大程度上簡化了計(jì)算的復(fù)雜度，提高了算法的準(zhǔn)確性.從實(shí)驗(yàn)結(jié)果可以看出，本文的算法在目標(biāo)發(fā)生遮擋、旋轉(zhuǎn)等各種變化時(shí)，依然可以準(zhǔn)確地跟蹤目標(biāo)，魯棒性能非常好.

［1］ 劉晨光，程丹松，劉家鋒，等.一種基于交互式粒子濾波器的視頻中多目標(biāo)跟蹤算法［J］.電子學(xué)報(bào)，2011，39（2）：260－267.

LIU Chen－guang，CHENG Dan－song，LIU Jiafeng，etal.Interactive particle filter based algorithm for tracking multiple objects in videos［J］.Acta Electronica Sinica，2011，39（2）：260－267.（in Chinese）

［2］Kristan M，Kovacic S，Leonardis A，etal.A twostage dynamic model for visual tracking［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2010，40（6）：1505－1520.

［3］ 馮 巍，胡 波，楊 成，等.基于貝葉斯理論的分布式多視角目標(biāo)跟蹤算法［J］.電子學(xué)報(bào)，2011，39（2）：315－321.

FENG Wei，HU Bo，YANG Cheng，etal.A distributed multi－view object tracking algorithm under the Bayesian framework［J］.Acta Electronica Sinica，2011，39（2）：315－321.（in Chinese）

［4］Ross D，Lim J，Lin R，etal.Incremental learning for robust visual tracking［J］.International Journal of Computer Vision，2008，77（1－3）：125－141.

［5］Grabner H，Leistner C，Bischof H.Semi－supervised on－line boosting for robust tracking［C］／／Computer Vision－ECCV 2008－10th European Conference on Computer Vision，ECCV 2008.Proceedings.Heidelberg：Springer Verlag，2008：234－247.

［6］MEI X，LING H B.Robust visual tracking and vehicle classification via sparse representation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（11）：2259－2272.

［7］Kalal Z，Matas J，Mikolajczyk K.P－N learning：Bootstrapping binary classifiers by structural constraints［C］／／Proceeding of the IEEE Conference on Computer Vision and Pattern Recognition，CVPR 2010.Piscataway：IEEE Computer Society，2010：49－56.

［8］Kwon J，Lee K M.Visual tracking decomposition［C］／／Proceeding of the IEEE Conference on Computer Vision and Pattern Recognition，CVPR 2010.Piscataway：IEEE Computer Society，2010：1269－1276.

［9］Babenko B，Belongie S，Yang M H.Visual tracking with online multiple instance learning［C］／／2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops，CVPR Workshops 2009.Piscataway：IEEE Computer Society，2009：983－990.

［10］Adam A，Rivlin E，Shimshoni I.Robust fragments based tracking using the integral histogram［C］／／Proceeding of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition，CVPR 2006.New York：IEEE Computer Society，2006：798－805.

Online object tracking algorithm based on feature grouping

JIANG Ming－xin＊1，2， WANG Hong－yu1

（1.School of Information and Communication Engineering，Dalian University of Technology，Dalian 116024，China；2.College of Information ＆Communication Engineering，Dalian Nationalities University，Dalian 116602，China）

Online object tracking is a challenging issue in computer vision.An online object tracking algorithm based on feature grouping is proposed.Firstly，the object templates in template base are grouped by computing the variance of the pixels in multiple frames.Then，the projection matrixPis learned based on the more discriminative image and the less discriminative image，and the samples are projected.Finally，tracking results of the current frame are performed by minimum error.Compared with other popular methods，the proposed method has strong robustness to abnormal changes.

online object tracking；linear subspace learning；feature grouping；template updating

TP391

A

1000－8608（2013）05－0755－05

2012－09－13；

2013－07－12.

國家自然科學(xué)基金資助項(xiàng)目（61172058）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目（DC10010103）；遼寧省教育廳資助項(xiàng)目（L2012476）.

姜明新＊（1979－），女，博士生，E－mail：jmx＠m(xù)ail.dlut.edu.cn；王洪玉（1969－），男，教授，博士生導(dǎo)師.