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

王海軍, 葛紅娟

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

?

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

王海軍1,2, 葛紅娟1

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

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

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

0　引　言

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

上述提到的算法都要對表示系數(shù)進(jìn)行稀疏求解,希望得到的表示系數(shù)中0的個數(shù)盡可能多,文獻(xiàn)[13]提出用L0正則化對系數(shù)進(jìn)行稀疏求解,但是L0正則化是不確定性多項式-難(non-deterministic polynomial-hard,NP-hard)問題,許多學(xué)者使用L1正則化代替L0正則化進(jìn)行求解。但是L0正則化是對表示系數(shù)的硬約束,用L1正則化簡單的代替L0正則化,會引起性能的下降。本文采用增量正交映射非負(fù)矩陣分解獲得模板矩陣的部分表示,并采用L0正則化對表示系數(shù)進(jìn)行約束,提出一種新的系數(shù)求解算法,同時對采樣粒子進(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為列向量的個數(shù))可以分解為兩個非負(fù)矩陣W∈Rd×k和H∈Rk×n的乘積(k

(1)

(2)

目標(biāo)函數(shù)Jr對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è)觀測目標(biāo)(候選樣本)可以近似由IOPNMF基向量矩陣和瑣碎模板組成的字典矩陣線性表示,即

(6)

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

(7)

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

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

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

(8)

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

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

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

(9)

(10)

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

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

(11)

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

(12)

考慮式(10)在qk+1處的二階近似,同時增加一個近似項,則式(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)動模型;p(It|xt)表示在狀態(tài)變量xt條件下,觀測樣本屬于跟蹤目標(biāo)概率大小的觀測模型。

3.1運(yùn)動模型

3.2觀測模型

用觀測模型來評估每個候選樣本屬于跟蹤目標(biāo)的可能性,即

(16)

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

(17)

3.3粒子篩選

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

(18)

4　實驗結(jié)果

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

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

4.1定性對比

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

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

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

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

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

4.2定量對比

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

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

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

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

圖6　不同算法的中心點誤差對比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　不同算法的平均中心點誤差對比

5　結(jié)　論

提出一種基于L0正則化IOPNMF的目標(biāo)跟蹤算法。首先采用增量正交投影算法,在線獲得候選樣本基于部分的表示,然后粒子濾波的框架下,以IOPNMF基向量構(gòu)建跟蹤算法的觀測模型,對表示系數(shù)進(jìn)行L0正則化約束,提出快速數(shù)值解法。同時引入粒子篩選機(jī)制,加快跟蹤速度。實驗結(jié)果表明,本文算法算法具有較高的覆蓋率和較低的中心點誤差,能夠?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. (吳京輝, 唐林波, 趙保軍, 等. 基于視覺字典的在線多示例目標(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]. 中國科學(xué)院大學(xué)學(xué)報, 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)合專項計劃(ZR2015FL009)；濱州市科技發(fā)展計劃(2013ZC0103)；濱州學(xué)院科研基金(BZXYG1524)資助課題

TP 391

A

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

王海軍(1980-),男,講師,博士研究生,主要研究方向為目標(biāo)跟蹤。

E-mail:whjlym@163.com

葛紅娟(1966-),女,教授,博士,主要研究方向為電機(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