在線低秩表示的目標跟蹤算法

王海軍,葛紅娟,張圣燕

(1.南京航空航天大學民航學院,江蘇南京 210016; 2.濱州學院山東省高校航空信息技術重點實驗室,山東濱州 256603)

在線低秩表示的目標跟蹤算法

王海軍1,2,葛紅娟1,張圣燕2

(1.南京航空航天大學民航學院,江蘇南京 210016; 2.濱州學院山東省高校航空信息技術重點實驗室,山東濱州 256603)

針對傳統的基于生成模式的跟蹤方法對噪聲及遮擋問題比較敏感,導致跟蹤結果失敗的問題,提出了以前幾幀的跟蹤結果作為觀測矩陣,采用魯棒的主元成分分析模型求解觀測模型的低秩特征.當新的視頻流到來時,不是把所有的跟蹤結果矩陣作為觀測矩陣.并提出了新的增量魯棒的主元成分分析模型,采用增廣拉格朗日算法求解新矩陣的低秩特征,并以此低秩矩陣在貝葉斯框架下建立跟蹤模型,用恢復的低秩特征更新字典矩陣.將文中方法與其他6種跟蹤算法在8種跟蹤視頻上進行跟蹤對比.實驗結果表明,所提出的方法具有較低的像素中心位置誤差和較高的重疊率.

目標跟蹤;低秩特征;魯棒的主成分分析模型;字典矩陣

目標跟蹤是計算機視覺領域一項重要的研究課題,在視頻監控、交通流量控制、輔助駕駛系統、人機接口等方面得到了廣泛的應用.近年來,國內外許多學者提出了很多魯棒的目標跟蹤算法,取得了較好的跟蹤性能.目前,目標跟蹤算法主要分為兩種類型:判別模式[1-2]和生成模式[3-6].

判別模式將目標跟蹤看成把跟蹤目標從背景目標塊中分離出來的二值分類問題,這類方法的運算耗時少,可實現實時的目標跟蹤;生成模式將跟蹤問題看成是從候選樣本中選出與目標區域重構誤差最小的樣本作為跟蹤目標,可以實現魯棒的目標跟蹤,跟蹤精度較高,但是耗時大,難以實現實時跟蹤.文獻[5]提出了增量在線目標跟蹤算法,在粒子濾波框架下,通過增量主成分學習在線學習跟蹤目標的外觀模型,實現目標的跟蹤.文獻[3]將稀疏表示應用到目標跟蹤領域,并提出用瑣碎模板解決跟蹤過程中出現的遮擋問題,但是該方法用Lasso方法來求解l1范數最小化問題,導致計算量大,實時性低,且跟蹤目標的像素較低,難以充分利用跟蹤目標的特征信息.文獻[7]提出了用加速近似梯度算法代替Lasso方法來求解l1范數最小化問題,實現了快速跟蹤.文獻[8]提出了一種基于稀疏原型的在線目標跟蹤算法,該算法對跟蹤過程中出現的異常噪聲進行顯式處理,降低了l1算法的計算量,提高了跟蹤精度和速度.

雖然判別模式和生成模式都能夠對目標進行準確跟蹤,但是判別模式當跟蹤目標出現大面積的遮擋時,難以實現準確的跟蹤,且很難解決跟蹤過程中出現的尺度變化問題.而在生成模式中,大多數方法采用的字典矩陣是由已得到的跟蹤結果組成的,當跟蹤結果出現遮擋或漂移時,就會對后來的跟蹤產生漂移,引起跟蹤誤差.

為解決上述問題,筆者提出了一種基于增量低秩特征的目標跟蹤算法,在線地學習跟蹤目標的低秩特征,恢復跟蹤目標被遮擋的部分,并更新字典矩陣.同時,該方法能準確恢復跟蹤目標的全局子空間,解決了以往基于子空間跟蹤方法對噪聲不魯棒,以及跟蹤出現遮擋時跟蹤失敗的問題.

1　低秩特征

魯棒的主元成分分析(Robust Principal Component Analysis,RPCA)[9]在計算機視覺領域得到了廣泛的應用,該方法假定觀測到的受污染數據矩陣Y∈Rm×n由低秩矩陣D和噪聲矩陣E構成,即Y=D+E,其中,D和E是未知的.為從污染矩陣Y中恢復低秩矩陣D,可用下面的數學模型來描述:

但是,式(1)假定觀測數據Y是從一個子空間提取來的,如果觀測數據Y是從多個子空間取樣來的樣本,若繼續采用式(1)來恢復低秩特征D,則將存在誤差.為了更準確地獲得低秩特征矩陣D,文獻[9]提出了更加一般化的秩最小化數學模型,即

但是式(1)和式(2)求得的干凈矩陣是在所有觀測數據組成一個污染矩陣Y的基礎上求得的,當有新的數據到來時,需要把新的數據和原有的觀測矩陣組成新的觀測矩陣,重新進行核最小化計算以求得低秩特征,這樣就大大降低了計算效率.為解決這個問題,在式(1)和式(2)的基礎上,提出了增量求解低秩特征的算法,并應用到目標跟蹤算法上,取得了較好的效果.

2　基于在線低秩特征的目標跟蹤算法

2.1在線低秩特征學習

當對一段視頻中的目標進行跟蹤時,首先用手選方法將前k幀中跟蹤目標提取出來,組成一個前k幀的標準跟蹤結果的矩陣.然后用

進行前k幀的低秩特征Dk計算,并采用文獻[9-11]的方法對Dk進行不足奇異值分解(Singular Value Decomposition,SVD)計算,即

其中,Uk為前k幀的子空間基底,Σk為半正定對角矩陣.

當有新的視頻幀時,即第k+1幀來臨時,如果采用原始方法,則需組成包括前k幀的觀測矩陣,重新進行計算式(3),計算效率大大降低.為了解決這個問題,采用式(2)在線計算低秩矩陣D.式(2)的求解是凸優化問題,為求解Z和E,文中采用增廣拉格朗日乘子(Augmented Lagrange Multiplier,ALM)算法[12].首先,把式(2)轉化為下面等價問題:

式(5)可通過Inexac ALM來求解,即

其中,Y1和Y2是拉格朗日乘子;μ＞0,是懲罰參數.使用In ALM解式(6)中的優化問題的算法如下:

輸入:一個觀測圖像塊(向量形式)Y,子空間基底U,這里令A=U,參數λ.

初始化:Z=J=0,E=0,Y1=0,Y2=0,μ=10-6,ρ=1.1,ε=10-8.

While不收斂do

End while.

求出新的Z后,則增量低秩特征D=UZ.

2.2運動模型

目標跟蹤可以看成是隱式馬爾科夫模型下的貝葉斯推理問題,假定已知前t幀的觀測數據Yt={y1,y2,…,yt},則t時刻的狀態變量xt可通過迭代求解獲得,即

其中,p(xt|xt-1)表示連續兩個狀態之間的運動模型;p(yt|xt)為似然函數或觀測模型;xt為仿射變換的6個參數,用來表征連續兩幀跟蹤目標的運動狀態.xt={zt,pt,θt,st,αt,φt},分別用來表示跟蹤目標的坐標位置、旋轉角度、尺度變化、寬高變化和斜交變化等.運動模型p(xt|xt-1)=N(xt|xt-1,Σ),其中Σ為狀態xt的6個參數的對角協方差矩陣.

2.3觀測模型

由式(3)可知,由前k幀視頻跟蹤結果組成矩陣可求出低秩特征,當有新的視頻流時,可通過式(4)求出新的視頻流的低秩特征,其中,i為第k+1幀的第i個樣本.因此,判斷第i個樣本是否為跟蹤目標,可通過如下觀測模型判斷:

式(8)為第t+1幀中第i個樣本為跟蹤目標的概率.當跟蹤目標出現遮擋時,采用文獻[8]中方法,引入一個掩模向量,來指示誤差向量E中的零元素與非零元素,即

當誤差向量Ei中第j個元素為0時,則;否則,.☉表示對應元素相乘.

2.4在線更新

為更好地適應跟蹤過程中運動目標的變化,需要對子空間基底U進行更新,當時,t為一閾值,為誤差向量中非零元素的個數,l(Et)為誤差向量中元素的個數,則重新采用式(3)計算低秩特征,這時的視頻流矩陣由開始的前20幀跟蹤目標與最新10幀的跟蹤目標組成,這樣既保留了原始跟蹤目標的信息,又能適應跟蹤過程中目標的變化.

3　實驗結果

文中算法在Window 7操作系統、Pentium Dual-Core CPU、2 GB內存電腦平臺采用Matlab軟件進行仿真實驗.為了驗證文中方法的優越性,采用8個具有挑戰性的視頻與當前比較流行的6種算法進行比較.這些視頻為Occlusion1、Caviar1、Singer1、Car4、Car11、DavidIndoor、David Outdoor、Stone,分別具有光照變化、尺度變化、背景混亂、遮擋以及姿態變化等影響跟蹤效果的因素.6種算法分別為:Frag[13]、L1[3]、MIL[1]、PCA[5]、PN[14]、VTD[15]等.每組視頻第1幀跟蹤目標的位置手動標出,文中算法每種視頻跟蹤采用的粒子數目為600,其他方法的參數分別采用其具有最優性能的參數.

3.1定性比較

圖1(a)為Occlusion1視頻的跟蹤結果,圖中女孩頭部位置基本不發生變化,但是存在來自左邊、下方、右邊圖書的嚴重遮擋.從跟蹤結果看,大部分方法基本上都能對女孩頭部進行跟蹤,但是PCA和MIL算法存在偏移.VTD算法尺度變化的太大,導致跟蹤結果方框不能覆蓋女孩的頭部.文中算法采用了考慮遮擋的模型及在線更新機制,能夠準確跟蹤女孩的頭部位置.

圖1 不同視頻采用不同算法跟蹤結果對比圖

圖1(b)為Caviar1視頻的跟蹤結果.Caviar1視頻存在相似人物的遮擋,跟蹤目標人物本身也存在運動以及尺度變化,同時視頻場景中存在光照變化.Caviar1視頻中目標人物由近及遠逐漸移動,目標人物尺度逐漸變小,同時存在來自右邊人物的遮擋.文中算法由于采用基于低秩特征,同時引入遮擋機制以及仿射變換方法,所以當出現相似人物遮擋時,也能準確地對目標人物進行跟蹤,同時適應目標人物尺度的變化.MIL算法基于多示例的方法,當出現相似人物的干擾時,偏移目標人物比較大.

圖1(c)～(f)分別為Singer1、Car4、Car11和DavidIndoor視頻的跟蹤結果.Singer1視頻為穿白衣的歌者在強烈白光照射下演唱的視頻片段.該視頻中跟蹤目標存在嚴重的光照變化,同時由于攝像機的運動,使得跟蹤目標存在尺度變化.MIL和Frag算法沒有考慮尺度變化,所以不能準確對目標進行定位跟蹤.PN算法雖然考慮了尺度變化,但是不能跟上目標的變化速度.文中算法、VTD和PCA算法能夠較準確地對歌者目標進行跟蹤;在Car4視頻中,目標汽車和道路以及公路兩旁樹木的顏色較為相近,同時汽車過橋時,存在由亮到暗以及由暗到亮的光照變化.MIL和Frag算法沒有考慮尺度變化,出現了飄移現象.文中算法、PCA及L1算法較為準確地對目標汽車持續跟蹤;在Car11視頻中,目標汽車在夜晚的公路上快速行駛,存在來自對面汽車燈光嚴重的干擾.當汽車出現轉彎時,大部分算法都偏移到對面來的汽車燈光上,只有文中算法和PCA算法準確地對目標汽車進行了跟蹤;在DavidIndoor視頻中,目標人物從屋子黑暗角落走到明亮位置,同時伴有尺度變化和頭部旋轉.文中算法不僅能夠適應跟蹤目標的亮度變化,而且當目標人物存在角度變化時,也能較準確地進行跟蹤.MIL算法雖然也對目標人物進行成功跟蹤,但是不能隨著目標尺度大小的變化而變化.Frag算法對光照變化比較敏感,所以存在跟丟現象.

圖1(f)和(h)為David Outdoor和Stone視頻.在David Outdoor視頻中,存在背景混亂、遮擋以及目標人物旋轉等干擾跟蹤效果的因素.從跟蹤結果來看,目標人物第1次經過樹木遮擋,且當目標人物旋轉時,只有文中算法準確地進行了跟蹤,其他算法都跟蹤失敗;Stone視頻存在嚴重的相似物體干擾,人物手部的顏色和目標石頭的顏色以及背景石頭的顏色非常相似,同時對目標石頭存在遮擋.圖1結果表明,文中算法對相似物體的干擾現象也有著非常魯棒的性能,其他算法則容易受到干擾,跟蹤失敗.

3.2定量比較

文中采用中心位置誤差(以像素為單位)和覆蓋率兩個指標對不同跟蹤算法的性能進行比較.中心位置誤差是指通過比較跟蹤算法的跟蹤方框的中心位置與人工手動標注的跟蹤目標的中心位置之間的歐式距離得到的.覆蓋率的含義,其中,表示第t幀中跟蹤目標以為中心的方框的覆蓋面積,表示第t幀中采用跟蹤算法得到的以為中心的跟蹤方框覆蓋面積.很明顯,OR值越大,表明跟蹤算法的性能越好.為跟蹤結果標準的中心位置,為采用跟蹤算法得到的中心位置.圖2給出了不同算法在各個幀的中心位置誤差圖,其中橫坐標為幀號,縱坐標為中心位置誤差.從圖2中可以看出,文中算法的中心位置誤差對給出的8種視頻是最低的.圖3給出了不同算法的覆蓋率對比,相比其他算法,文中算法的跟蹤目標覆蓋率較高,能實現魯棒的跟蹤.

3.3計算復雜度分析

假設觀測圖像樣本的維數為d,子空間基底U的秩為r,每一幀的迭代次數為n.根據文獻[10]可知,文中算法每一幀的計算復雜度為O(drn+nr2+r3),若整個視頻有F幀,則整個視頻的跟蹤復雜度為O((drn+nr2+r3)F).若采用標準RPCA算法進行視頻跟蹤,則迭代n次的復雜度為O(dtrn+nr2+r3),t為跟蹤的視頻幀數,完整視頻的跟蹤復雜度為O(d F2rn+Fnr2+Fr3),復雜度相對跟蹤視頻的幀數是呈二次平方增加的.

圖3　覆蓋率比較

4　結束語

文中提出了一種基于低秩特征的在線目標跟蹤算法,把固定幀的視頻看作是觀測矩陣,當有新的視頻流到來時,采用增廣拉格朗日算法增量地求出觀測矩陣的低秩特征,解決了傳統RPCA方法不能在線處理大數據的缺點.相比其他算法,文中算法充分利用跟蹤目標的全局子空間,并用低秩特征更新字典矩陣,解決了當跟蹤結果出現遮擋時,字典更新出現偏差的問題.通過與其他6種算法對比,文中算法能夠較好地克服視頻中出現的遮擋、尺度變化、光照變化等問題,具有較強的魯棒性.

[1]BABENKO B,YANG M H,BELONGIE S.Robust Object Tracking with Online Multiple Instance Learning[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(B):1619-1632.

[2]黃宏圖,葛淵,張繼,等.仿射變換在壓縮感知跟蹤中的應用[J].西安電子科技大學學報,2015,42(2):162-205. HUANG Hongtu,GE Yuan,ZHANG Ji,et al.Application of Affine Transform in Compressed Sensing Tracking[J]. Journal of Xidian University,2015,42(2):162-205.

[3]XUE M,LING H B.Robust Visual Tracking Using L1 Minimization[C]//Proceedings of the IEEE Computer Society Conference on Computer Vision.Piscataway:IEEE,2009:1436-1443.

[4]賀文驊,劉志鏡,屈鑒銘.利用超像素混合投票的在線目標跟蹤算法[J].西安電子科技大學學報,2015,42(3): 61-66. HE Wenhua,LIU Zhijing,QU Jianming.Online Visual Tracking Method Based on Superpixel Hybrid Voting[J]. Journal of Xidian University,2015,42(3):61-66.

[5]ROSS D,LIM J,LIN R S,et al.Incremental Learning for Robust Visual Tracking[J].International Journal of Computer Vision,2008,77(1/2/3):125-141.

[6]王海軍,張圣燕.基于L2范數和增量正交投影非負矩陣分解的目標跟蹤算法[J].黑龍江大學自然科學學報,2015,32 (2):262-269. WANG Haijun,ZHANG Shengyan.Object Tracking Algorithm via L2 Norm and Incremental Orthogonal Projective Non-negative Matrix Factorization[J].Journal of Natrual Science of Heilongjiang University,2015,32(2):262-269.

[7]BAO C L,WU Y,LING H B,et al.Real Time Robust L1 Tracker Using Accelerated Proximal Gradient Approach[C]//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington: IEEE,2012:1830-1837.

[8]WANG D,LU H C,YANG M H.Online Object Tracking with Sparse Prototypes[J].IEEE Transactions on Image Processing,2013,22(1):314-325.

[9]CANDèS E,LI X D,MA Y,et al.Robust Principal Component Analysis?[J].Journal of the ACM,2011,58(3): 1-37.

[10]LIU G,LIN Z,YAN S,et al.Robust Recovery of Subspace Structures by Low-rank Representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(1):171-184.

[11]ZHANG C C,LIU R S,QIU T S,et al.Robust Visual Tracking via Incremental Low-rank Features Learning[J]. Neurocomputing,2014,131:237-247.

[12]LIN Z C,LIU R S,SU Z X.Linearized Alternating Direction Method with Adaptive Penalty for Low-rank Representation[C]//Advances in Neural Information Processing Systems:24.New York:NIPS,2011:612-620.

[13]ADAM A,RIVLIN E.Robust Fragments-based Tracking Using the Integral Histogram[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Piscataway:IEEE,2006:798-805.

[14]ZDENEK K,MATAS J,MIKOLAJCZYK K.P-N Learning:Bootstrapping Binary Classifiers by Structural Constraints [C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Piscataway:IEEE,2010: 49-56.

[15]KWON J,LEE K M.Visual Tracking Decomposition[C]//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Piscataway:IEEE,2010:1269-1276.

(編輯:齊淑娟)

Object tracking via online low rank representation

WANG Haijun1,2,GE Hongjuan1,ZH ANG Shengyan2
(1.College of Civil Aviation,Nanjing Univ.of Aeronautics and Astronautics,Nanjing 210016,China; 2.Key Lab.of Aviation Information Technology in Univ.of Shandong,Binzhou Univ.,Binzhou 256603,China)

Object tracking is an active research topic in computer vision.The traditional tracking methods based on the generative model are sensitive to noise and occlusion,which leads to the failure of tracking results.In order to solve this problem,the tracking results of the first few frames are used as the observation matrix,and the low rank features of the observation model are solved by the the RPCA model. When the new video streams come,a new incremental RPCA is proposed to compute the new observation matrix by the augmented Lagrangian algorithm.The tracking model is established in the Bayesian framework,and the dictionary matrix is updated with the low rank feature.We have tested the proposed algorithm and six state-of-the-art approaches on eight publicly available sequences.Experimental results show that the proposed method has a lower pixel center position error and a higher overlap ratio.

object tracking;low rank feature;RPCA model;dictionary matrix

TP391

A

1001-2400(2016)05-0098-07

10.3969/j.issn.1001-2400.2016.05.018

2015-09-07 網絡出版時間:2015-12-10

山東省自然科學基金資助項目(ZR2015FL009);濱州市科技發展計劃資助項目(2013ZC0103);濱州學院科研基金資助項目(BZXYG1524)

王海軍(1980-),男,南京航空航天大學博士研究生,E-mail:whjlym@163.com.

網絡出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.036.html