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

姜明新， 王洪玉

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

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

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

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

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

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

0 引 言

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

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

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

1 特征分組

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

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

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

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

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

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

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

1.2 計算投影矩陣

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

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

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

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

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

選取目標(biāo)的運動仿射變換參數(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 算法的實現(xiàn)與模板庫的更新

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

［1］ 劉晨光，程丹松，劉家鋒，等.一種基于交互式粒子濾波器的視頻中多目標(biāo)跟蹤算法［J］.電子學(xué)報，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é)報，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é)基金資助項目（61172058）；中央高?；究蒲袠I(yè)務(wù)費專項資金資助項目（DC10010103）；遼寧省教育廳資助項目（L2012476）.

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