王海軍, 葛紅娟

(1. 南京航空航天大學(xué)民航學(xué)院, 江蘇 南京 211106; 2. 濱州學(xué)院山東省高校航空信息技術(shù)重點(diǎn)實(shí)驗(yàn)室, 山東 濱州 256603)

?

L0正則化增量正交投影非負(fù)矩陣分解的目標(biāo)跟蹤算法

王海軍1,2, 葛紅娟1

(1. 南京航空航天大學(xué)民航學(xué)院, 江蘇 南京 211106; 2. 濱州學(xué)院山東省高校航空信息技術(shù)重點(diǎn)實(shí)驗(yàn)室, 山東 濱州 256603)

針對(duì)傳統(tǒng)跟蹤算法不能在復(fù)雜場(chǎng)景下進(jìn)行有效跟蹤的問(wèn)題,提出一種基于L0正則化增量正交投影非負(fù)矩陣分解(incremental orthogonal projective non-negative matrix factorization,IOPNMF)的目標(biāo)跟蹤算法。在粒子濾波框架下采用IOPNMF算法在線(xiàn)獲得跟蹤目標(biāo)基于部分的表示以構(gòu)建模板矩陣,然后將每幀中的候選樣本建立基于模板矩陣的線(xiàn)性表示,對(duì)表示系數(shù)進(jìn)行L0正則化約束,并提出快速數(shù)值解法,同時(shí)引入粒子篩選機(jī)制,加快跟蹤速度。實(shí)驗(yàn)結(jié)果表明，新算法能夠解決跟蹤過(guò)程中出現(xiàn)的遮擋、光照變化、運(yùn)動(dòng)模糊等影響跟蹤性能的因素,具有較高的平均覆蓋率和較低的平均中心點(diǎn)誤差。

目標(biāo)跟蹤; L0正則化; 粒子篩選

0　引　言

目標(biāo)跟蹤是計(jì)算機(jī)視覺(jué)領(lǐng)域一項(xiàng)重要的研究課題,在交通流量控制、人機(jī)接口、視頻監(jiān)控等領(lǐng)域得到了廣泛的應(yīng)用。近年來(lái),國(guó)內(nèi)外學(xué)者對(duì)目標(biāo)跟蹤進(jìn)行了大量的研究工作,大致可以分為兩類(lèi):基于判別模型的目標(biāo)跟蹤[1-4]和基于生成模型的目標(biāo)跟蹤[5-7]。基于判別模型的方法將目標(biāo)跟蹤看成是一個(gè)二分類(lèi)問(wèn)題,將被跟蹤的目標(biāo)物體從眾多的背景中分離出來(lái)。基于生成模型的方法把目標(biāo)跟蹤看成是從候選樣本中尋找與目標(biāo)模板中最相似的區(qū)域。這類(lèi)方法由于跟蹤結(jié)果比較魯棒,得到了國(guó)內(nèi)外許多學(xué)者的關(guān)注。例如,文獻(xiàn)[8]提出增量視覺(jué)跟蹤(incremental visual tracking,IVT)算法,該方法將每個(gè)候選樣本用主成分分析(principal component analysis, PCA)基向量圖像的線(xiàn)性組合來(lái)表示,并采用增量主成分分析方法對(duì)PCA基向量進(jìn)行更新以適應(yīng)跟蹤目標(biāo)外觀(guān)的變化,取得了不錯(cuò)的跟蹤效果。文獻(xiàn)[9]將稀疏表示應(yīng)用到目標(biāo)跟蹤領(lǐng)域,提出L1最小化跟蹤算法,用目標(biāo)模板和正負(fù)瑣碎模板組成字典矩陣對(duì)候選樣本進(jìn)行線(xiàn)性表示,并對(duì)目標(biāo)模板進(jìn)行在線(xiàn)更新,獲得了較為精確的跟蹤結(jié)果。文獻(xiàn)[10]提出加速近似梯度算法(accelerated proximal gradient,APG)求解L1最小化問(wèn)題,從而實(shí)現(xiàn)快速的目標(biāo)跟蹤。文獻(xiàn)[11]提出基于稀疏原型的跟蹤算法,將候選樣本由正交基向量和瑣碎模板稀疏線(xiàn)性表示,同時(shí)提出考慮遮擋機(jī)制的觀(guān)測(cè)模型更新方式。文獻(xiàn)[12]提出基于增量正交映射非負(fù)矩陣分解的目標(biāo)跟蹤算法,能夠增量獲得目標(biāo)模板基于部分的表示,取得較好的跟蹤效果。

上述提到的算法都要對(duì)表示系數(shù)進(jìn)行稀疏求解,希望得到的表示系數(shù)中0的個(gè)數(shù)盡可能多,文獻(xiàn)[13]提出用L0正則化對(duì)系數(shù)進(jìn)行稀疏求解,但是L0正則化是不確定性多項(xiàng)式-難(non-deterministic polynomial-hard,NP-hard)問(wèn)題,許多學(xué)者使用L1正則化代替L0正則化進(jìn)行求解。但是L0正則化是對(duì)表示系數(shù)的硬約束,用L1正則化簡(jiǎn)單的代替L0正則化,會(huì)引起性能的下降。本文采用增量正交映射非負(fù)矩陣分解獲得模板矩陣的部分表示,并采用L0正則化對(duì)表示系數(shù)進(jìn)行約束,提出一種新的系數(shù)求解算法,同時(shí)對(duì)采樣粒子進(jìn)行篩選,減少了運(yùn)算復(fù)雜度,提高了跟蹤速度。

1　增量正交映射非負(fù)矩陣分解

非負(fù)矩陣分解[14](non-negative matrix factorization, NMF)假設(shè)高維非負(fù)矩陣Y=[y1,y2,…,yn]∈Rd×n(其中,yi為d維列向量,n為列向量的個(gè)數(shù))可以分解為兩個(gè)非負(fù)矩陣W∈Rd×k和H∈Rk×n的乘積(k

(1)

(2)

目標(biāo)函數(shù)Jr對(duì)Wr進(jìn)行求導(dǎo),即

(3)

(4)

(5)

2　L0正則化增量正交映射非負(fù)矩陣分解的目標(biāo)表示

2.1L1正則化的目標(biāo)表示

文獻(xiàn)[12]提出基于L1正則化增量正交映射非負(fù)矩陣分解的目標(biāo)跟蹤(object tracking via IOPNMF with L1 regularization,IOPNMFL1)算法,假設(shè)觀(guān)測(cè)目標(biāo)(候選樣本)可以近似由IOPNMF基向量矩陣和瑣碎模板組成的字典矩陣線(xiàn)性表示,即

(6)

式中,I代表觀(guān)測(cè)目標(biāo)(候選樣本)；W為IOPNMF基向量矩陣,且基向量矩陣之間相互正交,即WTW=E；z為對(duì)應(yīng)的表示系數(shù)；E代表單位矩陣,即瑣碎模板；e為大小任意且稀疏的誤差項(xiàng),可被看作是瑣碎模板對(duì)應(yīng)的表示系數(shù)。表示系數(shù)z和e可通過(guò)式(7)進(jìn)行求解:

(7)

式中,‖·‖2和‖·‖1分別表示L2范數(shù)和L1范數(shù);λ為正則化參數(shù)。IOPNMFL1算法雖然對(duì)異常噪聲進(jìn)行顯式處理,相比傳統(tǒng)的L1正則化算法提高了運(yùn)算速度,但是對(duì)表示系數(shù)z沒(méi)有進(jìn)行任何約束,仍然是不稀疏的,當(dāng)跟蹤視頻中出現(xiàn)遮擋時(shí),不加約束的表示系數(shù)z不能有效地去除遮擋。

2.2L0正則化的目標(biāo)表示

為了解決IOPNMFL1算法存在的問(wèn)題,對(duì)表示系數(shù)z進(jìn)行約束,進(jìn)行L0正則化,即式(7)修改為

(8)

式中，‖·‖0為L(zhǎng)0范數(shù)；γ為正則化參數(shù)。

2.3L0正則化的數(shù)值解法

式(8)中,表示系數(shù)z和e的求解可以分解為兩個(gè)子問(wèn)題：

(9)

(10)

式(9)中，ek+1的求解可通過(guò)軟閾值方法求解,即給定zk,ek+1=Sλ(I-Wzk),其中Sλ(x)=max(|x|-λ,0)sgn(x)為軟閾值函數(shù),sgn(·)為符號(hào)函數(shù)。

式(10)zk+1的求解,假定

(11)

式中，F(xiàn)是可微凸函數(shù),則其梯度為

(12)

考慮式(10)在qk+1處的二階近似,同時(shí)增加一個(gè)近似項(xiàng),則式(10)可近似為

(13)

式中，L為懲罰參數(shù)。

由文獻(xiàn)[15],可得式(13)的解為

(14)

求解式(8)求解的算法流程如下:

初始化z0=z-1=0,e0=e-1=0,t0=t-1=1

While不收斂或不終止do

步驟 1ek+1=Sλ(I-Wzk)

步驟 3

k←k+1

Endwhile

3　L0正則化增量正交映射非負(fù)矩陣分解的目標(biāo)跟蹤算法

(15)

式中,p(xt|xt-1)表示描述連續(xù)兩幀狀態(tài)轉(zhuǎn)換的運(yùn)動(dòng)模型;p(It|xt)表示在狀態(tài)變量xt條件下,觀(guān)測(cè)樣本屬于跟蹤目標(biāo)概率大小的觀(guān)測(cè)模型。

3.1運(yùn)動(dòng)模型

3.2觀(guān)測(cè)模型

用觀(guān)測(cè)模型來(lái)評(píng)估每個(gè)候選樣本屬于跟蹤目標(biāo)的可能性,即

(16)

式中,W為IOPNMF基向量矩陣;μ為IOPNMF子空間的均值;ξ為常參數(shù);上標(biāo)i表示第i個(gè)粒子；d(Ii;W,μ)為最小軟閾值均方距離,即

(17)

3.3粒子篩選

傳統(tǒng)算法是對(duì)所有粒子(通常選取粒子數(shù)目為600個(gè))進(jìn)行求解,但是這樣會(huì)導(dǎo)致計(jì)算量增加。為加快運(yùn)算速度,本文采用局部歸一化距離準(zhǔn)則[16]對(duì)候選粒子進(jìn)行L0正則化計(jì)算觀(guān)測(cè)模型之前進(jìn)行篩選,濾掉可能不是目標(biāo)的粒子,從而提高運(yùn)算速度。局部歸一化距離的定義為

(18)

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

仿真實(shí)驗(yàn)平臺(tái)為Windows8操作系統(tǒng),Inter(R)Core(TM)i7-5500UCPU@2.4GHz,8GB內(nèi)存,采用Matlab2014進(jìn)行軟件仿真。實(shí)驗(yàn)參數(shù)為:λ=0.2,γ=0.024,L=6。IOPNMF子空間的維數(shù)為16,每一幀中采樣粒子的數(shù)目為600,每個(gè)采樣粒子對(duì)應(yīng)的候選樣本縮放為32×32像素,每5幀對(duì)觀(guān)測(cè)模型進(jìn)行更新。本文提出的算法簡(jiǎn)寫(xiě)為IOPNMFL0,帶有篩選機(jī)制的算法簡(jiǎn)寫(xiě)為IOPNMFNEWL0。

為了驗(yàn)證本文所提算法的有效性,選用10個(gè)具有代表性的視頻與5種算法進(jìn)行對(duì)比,算法包括:IVT(incrementalvisualtracking)[8],MIL(multipleinstancelearning)[1],L1[9],Frag(fragments-basedtracking)[17],IOPNMFL1[12]。

4.1定性對(duì)比

嚴(yán)重遮擋:遮擋是影響跟蹤性能的重要因素,圖1(a)和圖1(b)視頻中目標(biāo)人物分別進(jìn)行由近到遠(yuǎn)以及由遠(yuǎn)到近地移動(dòng),不僅存在運(yùn)動(dòng)場(chǎng)景的光照變化,而且有旁邊其他相似移動(dòng)人物的遮擋,如圖1(a)視頻中第115幀,圖1(b)視頻中第200幀,目標(biāo)人物幾乎被完全遮擋。IOPNMFNEWL0、IOPNMFL0、IOPNMFL1由于采取IOPNMF分解獲得目標(biāo)人物基于部分的表示,同時(shí)用仿射變換建模跟蹤過(guò)程中的尺度變化,成功實(shí)現(xiàn)整個(gè)過(guò)程中目標(biāo)人物的跟蹤。MIL算法由于采用haar特征對(duì)跟蹤目標(biāo)進(jìn)行描述,容易受到周?chē)嗨颇繕?biāo)的干擾,所以當(dāng)出現(xiàn)遮擋時(shí),跟蹤結(jié)果都偏移到干擾人物上,導(dǎo)致跟蹤失敗。圖1(c)視頻中目標(biāo)人物頭部位置基本不變,但是存在來(lái)自目標(biāo)人物左邊、右邊以及下方書(shū)本的嚴(yán)重遮擋,且書(shū)本的顏色和目標(biāo)人物頭發(fā)顏色很相似,跟蹤過(guò)程非常容易受到干擾。從跟蹤結(jié)果來(lái)看,大部分方法整個(gè)過(guò)程都實(shí)現(xiàn)了成功跟蹤,但是IVT、L1、MIL、FRAG存在少量的偏移,跟蹤準(zhǔn)確性方面比IOPNMFNEWL0、IOPNMFL0、IOPNMFL1有所下降。

圖1　不同算法在遮擋視頻中的跟蹤結(jié)果對(duì)比Fig.1　Comparision of tracking results on occluded videos by different algorithms

光照變化:光照變化嚴(yán)重影響算法的跟蹤性能。圖2(a)視頻中汽車(chē)由近處向遠(yuǎn)處行進(jìn),道路以及周?chē)h(huán)境與汽車(chē)本身的顏色非常接近,同時(shí)需要通過(guò)橋洞以及樹(shù)木的陰影區(qū)域,存在光照變化;圖2(b)視頻中,汽車(chē)在夜晚道路上行進(jìn),對(duì)面汽車(chē)遠(yuǎn)光燈以及道路兩旁樹(shù)木上的燈光嚴(yán)重影響算法對(duì)目標(biāo)汽車(chē)的跟蹤;圖2(c)視頻中,舞臺(tái)燈光照射白衣歌者,很難對(duì)白衣歌者與燈光進(jìn)行區(qū)分跟蹤,同時(shí)由于攝像機(jī)位置的變化,歌者的尺度也發(fā)生變化;圖2(d)視頻中,不僅存在光照變化,而且人物頭部還存在姿態(tài)變化。從跟蹤結(jié)果來(lái)看,Frag算法容易受光照變化影響,偏離跟蹤目標(biāo),如圖2(a)視頻中第250幀,圖2(b)視頻中第170幀、240幀,圖2(c)視頻中第290幀。MIL算法由于沒(méi)有考慮跟蹤目標(biāo)的尺度變換,所以跟蹤框雖然也基本上能夠?qū)崿F(xiàn)對(duì)目標(biāo)物體進(jìn)行跟蹤,但是跟蹤精度下降。L1算法在對(duì)模板矩陣更新時(shí),沒(méi)有考慮遮擋因素,導(dǎo)致視頻跟蹤過(guò)程中出現(xiàn)精度下降。

背景雜亂:圖3(a)、圖3(b)視頻中不僅存在背景雜亂,而且跟蹤目標(biāo)存在姿態(tài)變化以及周?chē)嗨莆矬w的干擾。IOPNMFNEWL0、IOPNMFL0由于對(duì)表示系數(shù)進(jìn)行L0約束,相比其他算法,跟蹤性能一直比較穩(wěn)定,能夠?qū)崿F(xiàn)準(zhǔn)確跟蹤。

運(yùn)動(dòng)模糊:圖4中face視頻不僅目標(biāo)人物存在劇烈運(yùn)動(dòng)導(dǎo)致目標(biāo)人物頭部模糊,而且攝像機(jī)也存在快速突然晃動(dòng),嚴(yán)重影響算法的跟蹤性能。實(shí)驗(yàn)結(jié)果可以看出，只有IOPNMFNEWL0、IOPNMFL0、IOPNMFL1能夠一直穩(wěn)定進(jìn)行跟蹤,其他算法都偏離目標(biāo),導(dǎo)致跟蹤失敗。

4.2定量對(duì)比

圖2　不同算法在光照變化視頻中的跟蹤結(jié)果對(duì)比Fig.2　Comparision of tracking results on videos with illumination change by different algorithms

圖3　不同算法在背景雜亂視頻中的跟蹤結(jié)果對(duì)比Fig.3　Comparision of tracking results on videos with background clutter by different algorithms

圖4　不同算法在運(yùn)動(dòng)模糊視頻中的跟蹤結(jié)果對(duì)比(Face)Fig.4　Comparision of tracking results on videos with motion blur by different algorithms (Face)

圖5　不同算法的覆蓋率對(duì)比Fig.5　Comparison of overlap rate by different algorithms

圖6　不同算法的中心點(diǎn)誤差對(duì)比Fig.6　Comparision of center point error by different algorithms

跟蹤算法IVTL1MILFRAGIOPNMFL1IOPNMFL0IOPNMFNEWL0caviar10.270.270.250.680.880.910.90caviar20.450.810.250.550.660.770.72occlusion0.840.870.590.890.920.920.92car40.920.840.340.220.890.900.90car110.800.430.170.080.840.830.84singer10.660.700.330.340.770.850.85davidindoor0.710.620.440.190.700.770.74davidoutdoor0.510.340.400.390.760.760.75

續(xù)表1

表2　不同算法的平均中心點(diǎn)誤差對(duì)比

5　結(jié)　論

提出一種基于L0正則化IOPNMF的目標(biāo)跟蹤算法。首先采用增量正交投影算法,在線(xiàn)獲得候選樣本基于部分的表示,然后粒子濾波的框架下,以IOPNMF基向量構(gòu)建跟蹤算法的觀(guān)測(cè)模型,對(duì)表示系數(shù)進(jìn)行L0正則化約束,提出快速數(shù)值解法。同時(shí)引入粒子篩選機(jī)制,加快跟蹤速度。實(shí)驗(yàn)結(jié)果表明,本文算法算法具有較高的覆蓋率和較低的中心點(diǎn)誤差,能夠?qū)崿F(xiàn)魯棒的跟蹤。

[1] Babenko B, Yang M H, Belongie S. Robust visual tracking with online multiple instance learning[J].IEEETrans.onPatternAnalysisandMachineIntelligence, 2011, 33(8): 1619-1632.

[2] Zhang K H, Zhang L, Yang M H. Fast compressive tracking[J].IEEETrans.onPatternAnalysisandMachineIntelligence, 2014, 36(10): 2002-2015.

[3] Zhang K H, Zhang L, Yang M H, et al. Robust object tracking via adaptive feature selection[J].IEEETrans.onCircuitsandSystemsforVideoTechnology, 2013, 23(11): 1957-1967.

[4] Wu J H, Tang L B, Zhao B J, et al. Visual dictionary and online multi-instance learning based object tracking[J].SystemsEnginee-ringandElectronics, 2015, 37(2): 425-435. (吳京輝, 唐林波, 趙保軍, 等. 基于視覺(jué)字典的在線(xiàn)多示例目標(biāo)跟蹤[J]. 系統(tǒng)工程與電子技術(shù), 2015, 37(2): 425-435.)

[5] Wang H J, Zhang S Y. Algorithm of object-tracking based on collaborative representation[J].JournalofUniversityofChineseAcademyofSciences, 2016, 33(1): 135-143. (王海軍, 張圣燕. 基于協(xié)同表示的目標(biāo)跟蹤算法[J]. 中國(guó)科學(xué)院大學(xué)學(xué)報(bào), 2016, 33(1): 135-143.)

[6] Ma B, Hu H W, Shen J B, et al. Linearization to nonlinear learning for visual tracking[C]∥Proc.oftheIEEEInternationalConferenceonComputerVision, 2015: 4400-4407.

[7] Ma B, Shen J, Liu Y, et al. Visual tracking using strong classifier and structrual local sparse descriptors[J].IEEETrans.onMultimedia, 2015, 17(10): 1818-1828.

[8] Ross D, Lim J, Lin R S, et al. Incremental learning for robust visual tracking[J].InternationalJournalofComputerVision, 2008, 77(1): 125-141.

[9] Xue M, Ling H B. Robust visual tracking using L1 minimization[C]∥Proc.oftheIEEEInternationalConferenceonComputerVision, 2009: 1436-1443.

[10] Bao C L, Wu Y, Ling H B, et al. Real time robust L1 tracker using accelerated proximal gradient approach[C]∥Proc.oftheIEEEConferenceonComputerVisionandPatternRecognition, 2012: 1830-1837.

[11] Wang D, Lu H C, Yang M H. Online object tracking with sparse prototypes[J].IEEETrans.onImageProcessing, 2013, 22(1): 314-325.

[12] Wang D, Lu H C. On-line learning parts-based representation via incremental orthogonal projective non-negative matrix factorization[J].SignalProcessing, 2013, 93(6): 1608-1623.

[13] Dohoho D L. Compressed sensing[J].IEEETrans.onInformationTheory, 2006, 52(4): 1289-1306.

[14] Lee D, Seung H. Learning the parts of objects by non-negative matrix factorization[J].Nature, 1999(401): 788-791.

[15] Liu R S, Bai S S, Su Z X, et al. Robust visual tracking via L0 regularized local low-rank feature learning[J].JournalofElectronicImaging, 2015, 24(3): 033012.

[16] Wang D, Lu H C, Bo C J. Visual tracking via weighted local cosine similarity[J].IEEETrans.onSystems,Man,andCyberneticsPartB, 2015, 45(9): 1838-1850.

[17] Adam A, Rivlin E. Robust fragments-based tracking using the integral histogram[C]∥Proc.oftheIEEEConferenceonComputerVisionandPatternRecognition, 2006: 798-805.

Object tracking via incremental orthogonal projective non-negative matrix factorization with L0 regularization

WANG Hai-jun1,2, GE Hong-juan1

(1. College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 211106,China;2.KeyLaboratoryofAviationInformationTechnologyinUniversityofShandong,BinzhouUniversity,Binzhou256603,China)

In order to solve the problem of tracking failure in complex scenes by traditional object tracking algorithms, a new object tracking algorithm based on incremental orthogonal projective non-negative matrix factorization (IOPNMF) with L0 regularization is presented. In the framework of the particle filter, template matrix is obtained on the part-based representation of the tracked object by the IOPNMF algorithm. The candidates in each frame are linearly representated by the template matrix. The representation coefficients are constrained by the L0 regularization while a fast numerical solution is proposed. At the same time, the particle selection mechanism is introduced to speed up the tracking speed. Experimental results show that the proposed algorithm can effectively overcome the influence of occlusion, illumination change, and motion blur, with higher average overlap rate and lower average center point error.

object tracking; L0 regularization; particle selection

2016-03-17；

2016-07-01；網(wǎng)絡(luò)優(yōu)先出版日期：2016-08-05。

山東省自然科學(xué)基金高校、科研單位聯(lián)合專(zhuān)項(xiàng)計(jì)劃(ZR2015FL009)；濱州市科技發(fā)展計(jì)劃(2013ZC0103)；濱州學(xué)院科研基金(BZXYG1524)資助課題

TP 391

A

10.3969/j.issn.1001-506X.2016.10.29

王海軍(1980-),男,講師,博士研究生,主要研究方向?yàn)槟繕?biāo)跟蹤。

E-mail:whjlym@163.com

葛紅娟(1966-),女,教授,博士,主要研究方向?yàn)殡姍C(jī)與電器、交通信息工程及控制。

E-mail:allenge@nuaa.edu.cn

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160805.1524.004.html