王海軍, 葛紅娟

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

?

L0正則化增量正交投影非負矩陣分解的目標跟蹤算法

王海軍1,2, 葛紅娟1

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

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

目標跟蹤; L0正則化; 粒子篩選

0　引　言

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

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

1　增量正交映射非負矩陣分解

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

(1)

(2)

目標函數(shù)Jr對Wr進行求導,即

(3)

(4)

(5)

2　L0正則化增量正交映射非負矩陣分解的目標表示

2.1L1正則化的目標表示

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

(6)

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

(7)

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

2.2L0正則化的目標表示

為了解決IOPNMFL1算法存在的問題,對表示系數(shù)z進行約束,進行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ù)。

由文獻[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正則化增量正交映射非負矩陣分解的目標跟蹤算法

(15)

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

3.1運動模型

3.2觀測模型

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

(16)

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

(17)

3.3粒子篩選

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

(18)

4　實驗結果

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

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

4.1定性對比

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

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

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

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

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

4.2定量對比

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

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

圖4　不同算法在運動模糊視頻中的跟蹤結果對比(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　結　論

提出一種基于L0正則化IOPNMF的目標跟蹤算法。首先采用增量正交投影算法,在線獲得候選樣本基于部分的表示,然后粒子濾波的框架下,以IOPNMF基向量構建跟蹤算法的觀測模型,對表示系數(shù)進行L0正則化約束,提出快速數(shù)值解法。同時引入粒子篩選機制,加快跟蹤速度。實驗結果表明,本文算法算法具有較高的覆蓋率和較低的中心點誤差,能夠?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. (吳京輝, 唐林波, 趙保軍, 等. 基于視覺字典的在線多示例目標跟蹤[J]. 系統(tǒng)工程與電子技術, 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é)同表示的目標跟蹤算法[J]. 中國科學院大學學報, 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)絡優(yōu)先出版日期：2016-08-05。

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

TP 391

A

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

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

E-mail:whjlym@163.com

葛紅娟(1966-),女,教授,博士,主要研究方向為電機與電器、交通信息工程及控制。

E-mail:allenge@nuaa.edu.cn

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