黃宏圖 畢篤彥 侯志強(qiáng) 胡長(zhǎng)城 高山 查宇飛 庫濤

視頻目標(biāo)跟蹤是計(jì)算機(jī)視覺領(lǐng)域的關(guān)鍵問題和研究熱點(diǎn),是任何一個(gè)以視頻為輸入的實(shí)際應(yīng)用系統(tǒng)的關(guān)鍵技術(shù),是后續(xù)目標(biāo)識(shí)別、行為分析、視頻壓縮編碼和視頻理解等高級(jí)視頻處理任務(wù)的基礎(chǔ)[1].視頻目標(biāo)跟蹤的目的是在連續(xù)的圖像序列中標(biāo)記出特定目標(biāo),估計(jì)目標(biāo)的位置、尺度或區(qū)域,確定目標(biāo)的速度以及軌跡等運(yùn)動(dòng)信息.實(shí)際應(yīng)用中完整的視頻目標(biāo)跟蹤系統(tǒng)通常包括目標(biāo)的檢測(cè)、提取、識(shí)別和跟蹤4個(gè)環(huán)節(jié).一般為了研究方便,將其進(jìn)行一定簡(jiǎn)化,例如檢測(cè)、提取和識(shí)別通過人工方式完成,從而突出跟蹤環(huán)節(jié)算法的研究[2].

在民用領(lǐng)域,視頻目標(biāo)跟蹤在智能視頻監(jiān)控[3]、智能交通系統(tǒng)、人機(jī)交互、視覺導(dǎo)航、無人駕駛汽車[4]、醫(yī)學(xué)圖像分析、虛擬現(xiàn)實(shí)、運(yùn)動(dòng)分析、行為識(shí)別和視頻檢索等方面有較多應(yīng)用.在軍事領(lǐng)域,視頻目標(biāo)跟蹤已經(jīng)廣泛應(yīng)用于戰(zhàn)場(chǎng)偵察與監(jiān)視、景象匹配制導(dǎo)和無人機(jī)對(duì)地目標(biāo)跟蹤等領(lǐng)域[5].

近30多年來得益于計(jì)算機(jī)技術(shù)的發(fā)展,視頻目標(biāo)跟蹤研究已經(jīng)取得較大進(jìn)展[6].但是目前復(fù)雜環(huán)境下持續(xù)魯棒的視頻目標(biāo)跟蹤仍然比較困難,沒有哪個(gè)跟蹤算法能夠成功地應(yīng)用于所有的視頻跟蹤任務(wù),大多數(shù)算法在跟蹤一段時(shí)間之后,通常就會(huì)因?yàn)槟承┰騺G失目標(biāo)[7].魯棒視頻目標(biāo)跟蹤的難點(diǎn)在于隨著時(shí)間和空間的推移,目標(biāo)自身變化和外界場(chǎng)景變化的復(fù)雜性和難以預(yù)知性[8],例如從3D空間投影到2D平面時(shí)的信息損失、光照變化、尺度變化、遮擋、形變、運(yùn)動(dòng)模糊、快速運(yùn)動(dòng)、旋轉(zhuǎn)、復(fù)雜場(chǎng)景、低分辨率圖像、目標(biāo)移出視角、攝像機(jī)視角改變和噪聲等.從控制論觀點(diǎn)看,視頻目標(biāo)跟蹤是一個(gè)從輸入到輸出的單向開環(huán)系統(tǒng),由于沒有反饋輸入,很難確認(rèn)跟蹤的正確與否,隨著時(shí)間的推移,模型更新中誤差累積會(huì)產(chǎn)生漂移,最終因系統(tǒng)發(fā)散導(dǎo)致跟蹤失敗[9].此外某些算法的時(shí)間復(fù)雜度較高難以實(shí)現(xiàn)實(shí)時(shí)跟蹤[7].因此魯棒實(shí)時(shí)的視頻目標(biāo)跟蹤仍然是一項(xiàng)亟待解決的關(guān)鍵問題,具有重要的理論意義和實(shí)用價(jià)值.

在信號(hào)與信息處理領(lǐng)域,一直高度重視信號(hào)描述的“簡(jiǎn)單性”[10].從信息論角度看,如果信號(hào)是稀疏的,或具有某種結(jié)構(gòu),或可用某個(gè)確定的模型表示,這樣的信號(hào)稱之為“簡(jiǎn)單”信號(hào)[11].“簡(jiǎn)單性”是簡(jiǎn)單信號(hào)的固有特性,通常表現(xiàn)為稀疏性、低秩性和低熵性等.稀疏表示作為信號(hào)“簡(jiǎn)單性”的描述,是近幾年研究熱點(diǎn).生物學(xué)家研究發(fā)現(xiàn)[12?13]哺乳類動(dòng)物在長(zhǎng)期進(jìn)化過程中,視神經(jīng)形成了快速、準(zhǔn)確、低能耗地表示自然圖像的能力,關(guān)鍵在于哺乳動(dòng)物在感知視覺信息時(shí),大腦視皮層V1區(qū)中只有少量神經(jīng)元被激活,即視覺信息可以用少量神經(jīng)元進(jìn)行稀疏表示.

稀疏表示廣泛應(yīng)用于人臉識(shí)別[14]、圖像超分辨率重建、圖像去噪和恢復(fù)[15]、圖像分割、特征提取和融合[16]、圖像顯著性檢測(cè)[17]、背景建模和圖像分類[18]等計(jì)算機(jī)視覺領(lǐng)域[19].稀疏表示有助于獲取描述符的顯著模式,能夠在有限的樣本容量下,使所得模型參數(shù)呈現(xiàn)某種稀疏性,提高模型的可靠性和可解釋性,有利于采用模型對(duì)實(shí)際問題進(jìn)行解釋和指導(dǎo),并且重建性能好.受到基于稀疏表示的人臉識(shí)別[14]的影響,以及視頻連續(xù)性產(chǎn)生的圖像幀與幀之間的冗余性,2009年國際計(jì)算機(jī)視覺大會(huì)上,Mei等首次將稀疏表示應(yīng)用到視頻目標(biāo)跟蹤中[20],構(gòu)建由目標(biāo)模板和單位矩陣組成的冗余字典,核心思想是將候選目標(biāo)圖像表示為目標(biāo)圖像的稀疏線性組合,從稀疏角度得到目標(biāo)最緊致的表示.后續(xù)出現(xiàn)了大量基于稀疏表示的視頻目標(biāo)跟蹤算法[21],并取得了較好的跟蹤性能[22].其中基于灰度特征字典的稀疏表示跟蹤算法對(duì)遮擋和噪聲等具有一定的魯棒性,對(duì)于判別式跟蹤算法而言在稀疏表示下目標(biāo)和背景更加線性可分.但算法時(shí)間復(fù)雜度一般較高,難以實(shí)現(xiàn)實(shí)時(shí)跟蹤和算法快速優(yōu)化.由于算法時(shí)間復(fù)雜度與字典維數(shù)相關(guān),難以使用高維的魯棒特征,導(dǎo)致算法魯棒性低于某些算法.

文獻(xiàn)[21]按照稀疏表示的用途和階段不同將稀疏表示跟蹤算法分為基于稀疏表示的表觀建模和基于稀疏表示的目標(biāo)搜索兩類,其中表觀建模中將稀疏表示看成是對(duì)目標(biāo)建模表示的過程,目標(biāo)搜索中將稀疏表示的過程看成是目標(biāo)搜索的過程.本文在粒子濾波框架下將基于稀疏表示的視頻目標(biāo)跟蹤算法分為4個(gè)組成部分:字典構(gòu)建、稀疏模型的構(gòu)建及求解、觀測(cè)模型的構(gòu)建和模型更新.其中字典構(gòu)建是基礎(chǔ),因?yàn)楹罄m(xù)的一切處理都是在字典中原子張成的子空間內(nèi)進(jìn)行.稀疏模型的構(gòu)建及求解是核心,稀疏模型構(gòu)建是在重構(gòu)誤差和稀疏性先驗(yàn)之間尋求某種微妙的平衡,快速有效的模型求解算法是關(guān)鍵,因?yàn)檫@直接涉及跟蹤算法的處理速度.觀測(cè)模型構(gòu)建是根本,最終決定了目標(biāo)匹配的相似性度量函數(shù).模型更新是重點(diǎn),由于跟蹤過程目標(biāo)是不斷變化的,在跟蹤結(jié)果的基礎(chǔ)上適時(shí)地對(duì)模型進(jìn)行在線更新是魯棒跟蹤所必需的.下面分別對(duì)上述4個(gè)組成部分進(jìn)行分析.

1 字典構(gòu)建

基于稀疏表示的視頻目標(biāo)跟蹤算法本質(zhì)上是冗余字典下的稀疏逼近問題[23],在冗余字典下能更有效地找出隱含在輸入數(shù)據(jù)內(nèi)部的結(jié)構(gòu)與模式.目前信號(hào)在冗余字典下的稀疏表示研究集中在以下兩個(gè)方面:1)構(gòu)建適合某一類信號(hào)的冗余字典;2)設(shè)計(jì)快速有效的稀疏分解算法.如圖1所示,字典構(gòu)建包括特征選擇和字典組成兩個(gè)步驟.

圖1 字典構(gòu)建方法Fig.1 The codebook construction method

1.1 特征選擇

受到基于稀疏表示的人臉識(shí)別的影響,以及灰度特征的簡(jiǎn)單性和有效性,大多數(shù)算法利用目標(biāo)的全局模板或局部圖像塊的灰度特征[24].但是灰度特征涉及像素點(diǎn)的對(duì)齊問題,一般是通過以下兩種方法實(shí)現(xiàn)像素點(diǎn)的對(duì)齊[25]:1)在目標(biāo)周圍進(jìn)行稠密采樣,使得字典中能夠盡可能地包括圖像的轉(zhuǎn)換形式;2)候選樣本的每列通過幾何轉(zhuǎn)換與字典中的目標(biāo)模板對(duì)齊.后續(xù)跟蹤算法引入了其他特征例如:紅外特征[26]、顏色直方圖、HOG(Histograms of oriented gradients)[27]、像素點(diǎn)梯度方向的正余弦[28]、SIFT(Scale-invariant feature transform)[29]和幾何模糊[30]等.文獻(xiàn)[31]直接將顏色直方圖、灰度、HOG和LBP(Local binary pattern)堆疊實(shí)現(xiàn)簡(jiǎn)單融合.文獻(xiàn)[32]將像素點(diǎn)的坐標(biāo)、灰度、梯度幅值和方向使用協(xié)方差矩陣進(jìn)行融合,在不同圖像上的區(qū)域協(xié)方差描述符獲得了一定的尺度和旋轉(zhuǎn)不變性.協(xié)方差矩陣將不同類型的特征進(jìn)行有效融合,利用了特征之間的空間特性、統(tǒng)計(jì)特性和特征之間的相關(guān)性且維數(shù)較小.雖然協(xié)方差矩陣位于黎曼流形上,但將其進(jìn)行對(duì)數(shù)轉(zhuǎn)換后可以在歐氏空間上進(jìn)行度量.多特征融合[33]的目的在于利用特征之間的互補(bǔ)性彌補(bǔ)單一特征的不足.由于特征維數(shù)直接決定了后續(xù)稀疏求解算法的復(fù)雜度,因此在特征選擇過程中必須考慮特征維數(shù)對(duì)算法求解速度的影響.

1.2 字典組成

字典組成的方法分為人工設(shè)計(jì)方法和機(jī)器學(xué)習(xí)方法.由于人工設(shè)計(jì)方法的簡(jiǎn)單性和有效性,大多數(shù)字典構(gòu)建方法直接使用預(yù)先指定的字典.基于機(jī)器學(xué)習(xí)的字典構(gòu)建方法大多需要大量的訓(xùn)練數(shù)據(jù).

如圖1所示,人工設(shè)計(jì)的方法按照字典的構(gòu)成可以分為:基于目標(biāo)特征的字典構(gòu)建方法、基于目標(biāo)特征和背景特征的字典構(gòu)建方法和基于候選目標(biāo)特征的字典構(gòu)建方法.

基于目標(biāo)特征的字典構(gòu)建方法大多利用目標(biāo)模板或者主成分分析(Principle component analysis,PCA)來構(gòu)建字典,為了處理遮擋和噪聲等異常,字典中一般還包括微模板[20,34?37](與字典中原子維數(shù)同樣大小的單位矩陣,以下統(tǒng)稱微模板).由于稀疏表示反映了候選目標(biāo)和字典中原子的線性相關(guān)性,為了保證稀疏表示的非負(fù)性引入了負(fù)微模板.后續(xù)算法為了減少字典中原子的個(gè)數(shù)提高算法效率,將負(fù)微模板和非負(fù)性約束去掉,利用目標(biāo)特征和正微模板構(gòu)建字典[38].文獻(xiàn)[39?42]使用局部圖像塊代替全局模板使得字典本身對(duì)于部分遮擋具有一定的魯棒性.

為了提高模型處理復(fù)雜背景的能力,文獻(xiàn)[43]同時(shí)利用目標(biāo)特征和背景特征構(gòu)建字典,使得字典本身具有判別性,進(jìn)而使得稀疏表示中包含有判別信息,從而使算法具有較強(qiáng)的區(qū)分目標(biāo)和背景的能力.

利用候選目標(biāo)特征構(gòu)建字典的方法[44?45]是將跟蹤問題看作識(shí)別問題,求解目標(biāo)在候選目標(biāo)組成字典下的稀疏表示,根據(jù)稀疏表示即可從候選目標(biāo)中確定目標(biāo)的位置,理論上只需要求解幾次稀疏表示,相比傳統(tǒng)方法大大減少了稀疏表示的求解次數(shù).

目前稀疏表示跟蹤算法中基于學(xué)習(xí)的字典構(gòu)建方法還比較少.字典學(xué)習(xí)[10]通過優(yōu)化相應(yīng)的目標(biāo)函數(shù),獲得能夠?qū)π盘?hào)進(jìn)行稀疏表示的字典,或從分析的角度看,通過優(yōu)化目標(biāo)函數(shù)使變換系數(shù)最稀疏.字典學(xué)習(xí)根據(jù)數(shù)據(jù)或信號(hào)本身來學(xué)習(xí)冗余字典,這類字典中的原子與訓(xùn)練集中的數(shù)據(jù)本身相適應(yīng).與基于解析方法的字典相比,通過學(xué)習(xí)獲得的字典原子數(shù)量更多,形態(tài)更豐富,能更好地與信號(hào)或圖像本身的數(shù)據(jù)結(jié)構(gòu)匹配,具有更稀疏的表示,比解析方法構(gòu)造的字典有更出色的性能.

綜合字典學(xué)習(xí)都采用系數(shù)更新和字典更新交替優(yōu)化的方式.字典學(xué)習(xí)算法的區(qū)別主要在于字典更新方式,而系數(shù)更新沒有本質(zhì)區(qū)別.固定字典更新稀疏表示是標(biāo)準(zhǔn)的稀疏編碼問題,理論上任何一種稀疏編碼方法都可以用于系數(shù)更新[46?47].固定稀疏表示更新字典則是字典學(xué)習(xí)算法最為關(guān)注的環(huán)節(jié).綜合字典學(xué)習(xí)試圖找到一組能夠反映信號(hào)本征空間的基,解析字典學(xué)習(xí)則是從對(duì)偶分析的角度考慮稀疏表示問題,試圖找到信號(hào)正交空間的基.上述兩種模型的訓(xùn)練樣本為特定的信號(hào)庫,盲字典學(xué)習(xí)的訓(xùn)練樣本是待重構(gòu)信號(hào)的測(cè)量值.上述三種模型均以范數(shù)描述信號(hào)的稀疏性,而基于信息復(fù)雜度的字典學(xué)習(xí)則是利用信息的復(fù)雜度描述信號(hào)的“簡(jiǎn)單性”.信號(hào)越稀疏,其復(fù)雜度越低,因此它仍然屬于廣義的稀疏表示模型.

2 稀疏模型的構(gòu)建及求解

稀疏模型的構(gòu)建是在重構(gòu)誤差一定的前提下,在稀疏性約束中加入一些目標(biāo)的先驗(yàn)信息,得到目標(biāo)更加緊湊的表示[48],從而提取出數(shù)據(jù)潛在的內(nèi)部結(jié)構(gòu).由于大多數(shù)基于稀疏表示的視頻目標(biāo)跟蹤算法是在粒子濾波框架下進(jìn)行,因此按照觀測(cè)模型將其分為生成式模型、判別式模型和混合式模型.

2.1 生成式模型

目前基于稀疏表示的視頻跟蹤算法大多為生成式算法,如圖2所示,生成式模型中根據(jù)目標(biāo)匹配相似性度量函數(shù)的不同,分為基于重構(gòu)誤差的生成式算法、基于稀疏表示系數(shù)的生成式算法和基于稀疏編碼直方圖的生成式算法.

基于重構(gòu)誤差的生成式算法一般是首先求解候選目標(biāo)在稀疏模型下的表示系數(shù),而后求解候選目標(biāo)基于目標(biāo)特征的重構(gòu)誤差,最后選擇重構(gòu)誤差最小的候選目標(biāo)作為跟蹤位置.如圖2所示,按照稀疏模型的不同分為L(zhǎng)1跟蹤算法、加權(quán)稀疏編碼跟蹤算法、基于結(jié)構(gòu)稀疏表示的跟蹤算法、基于非局部自相似正則化的稀疏表示跟蹤算法、多任務(wù)稀疏表示跟蹤算法和多任務(wù)多視角稀疏表示跟蹤算法.

圖2 基于稀疏表示的生成式模型Fig.2 The sparse representation-based generative model

基于目標(biāo)特征重構(gòu)誤差的生成式算法的典型代表是L1跟蹤算法[20,24],其算法框架如圖3所示.

圖3 L1跟蹤算法框架Fig.3 The L1tracker framework

L1跟蹤算法的稀疏表示模型為

為了提高L1跟蹤算法的速度,Bao等將加速最近梯度(Accelerated proximal gradient,APG)算法引入到稀疏模型的求解中,并對(duì)微模板系數(shù)附加范數(shù)約束[35]:

傳統(tǒng)的稀疏表示模型中重構(gòu)誤差通常使用1范數(shù)或者2范數(shù),分別對(duì)應(yīng)拉普拉斯誤差分布和高斯誤差分布.然而在實(shí)際中重構(gòu)誤差并不一定是理想的拉普拉斯分布或高斯分布,為了解決這個(gè)問題L1跟蹤算法使用微模板以較高的計(jì)算代價(jià)來解決遮擋或者噪聲等異常情況.Yan等[50]從重構(gòu)誤差的概率分布出發(fā),通過加權(quán)稀疏編碼誤差最小化來提高跟蹤算法的魯棒性,旨在解決超出拉普拉斯和高斯噪聲的異常,理論上使算法模型適用于更為一般的噪聲和異常.因此字典中并不需要微模板,減少了字典中原子個(gè)數(shù)一定程度上降低了算法復(fù)雜度.

基于PCA的重構(gòu)誤差生成式算法使用PCA代替目標(biāo)模板,主要原因有:1)L1跟蹤算法字典中只是利用目標(biāo)模板來處理目標(biāo)的變化,而目標(biāo)模板張成的子空間的表達(dá)能力是有限的,難以處理目標(biāo)較大的視角和姿態(tài)變化.2)字典一旦使用背景圖像或者嚴(yán)重遮擋的跟蹤結(jié)果更新后,L1跟蹤算法很容易失敗,而基于PCA的字典能夠最大限度地保留目標(biāo)的類內(nèi)方差,從而獲得目標(biāo)模板豐富的冗余結(jié)構(gòu)信息,利用歷史數(shù)據(jù)使用增量子空間學(xué)習(xí)得到目標(biāo)表示的時(shí)間相關(guān)性,由其張成的最優(yōu)子空間不僅對(duì)當(dāng)前目標(biāo),而且對(duì)歷史目標(biāo)都有較小的重構(gòu)誤差,因此本征模板集合相比目標(biāo)模板能夠提供更豐富的表達(dá).3)使用PCA代替目標(biāo)模板后,字典中的微模板能夠克服PCA對(duì)噪聲太敏感只能對(duì)一些類似高斯分布的數(shù)據(jù)有效的不足.

Wang等[51]利用PCA替換L1跟蹤算法中的目標(biāo)模板,同時(shí)利用了子空間對(duì)目標(biāo)變化的建模能力和稀疏表示對(duì)遮擋等異常的魯棒性.候選目標(biāo)可以使用PCA子空間線性表示其中字典U∈Rd×m由正交基向量組成,z為稀疏表示,e為重構(gòu)誤差.其稀疏表示通過下式求解:

其中,由于PCA基向量是正交的,因而對(duì)應(yīng)正交基向量的系數(shù)z是稠密,而對(duì)應(yīng)微模板的系數(shù)e是稀疏的,上述模型可以通過迭代優(yōu)化求解.

Pan等[52]在文獻(xiàn)[51]的基礎(chǔ)上從理論上證明當(dāng)字典為正交字典時(shí),使用范數(shù)約束表示目標(biāo)比范數(shù)約束更優(yōu).將算法模型修正為

Bai等[37]利用遮擋的連續(xù)空間分布考慮圖像的結(jié)構(gòu)信息提出了基于結(jié)構(gòu)稀疏表示的跟蹤算法,利用結(jié)構(gòu)單元子空間的線性組合表示目標(biāo).字典D=[U,I]∈Rd×(m+d)由本征模板和部分微模板集合I組成.由于部分遮擋通常具有連續(xù)的空間分布,將字典D分成(R+1)個(gè)長(zhǎng)度為m的組,d=Rm.D[v]∈Rd×m為D的第v組,顯然組內(nèi)的原子之間是相互正交,且字典的第1個(gè)組D[1]=U是由目標(biāo)模板經(jīng)過奇異值分解得到的主成分組成.為c的第v組.字典D和稀疏表示c的分組分別為

Lu等[54]考慮候選目標(biāo)的稀疏表示之間的相關(guān)性,在稀疏表示中引入了非局部自相似正則項(xiàng)(Non-local self-similarity regularized sparse coding,NLSSSC),利用最近鄰來編碼目標(biāo)中的結(jié)構(gòu)信息,提高了算法的判別力.Rd×n為n個(gè)候選目標(biāo),為字典,候選目標(biāo)的稀疏表示為.對(duì)非局部自相似正則項(xiàng)附加范數(shù)約束得到NLSSSC的目標(biāo)函數(shù)為

上述算法是基于子空間的結(jié)構(gòu)信息,而文獻(xiàn)[55]則是利用像素級(jí)遮擋的連續(xù)空間分布,提出了基于結(jié)構(gòu)稀疏學(xué)習(xí)的遮擋檢測(cè)跟蹤算法.候選目標(biāo)中所有像素構(gòu)成一組節(jié)點(diǎn)為V、邊為E的圖,邊存在于任意相鄰的兩個(gè)像素點(diǎn)之間.權(quán)重wml表示像素m和l之間的相關(guān)性,與其灰度值的相關(guān)性成正比,與其歐氏距離成反比.結(jié)構(gòu)稀疏表示的目標(biāo)函數(shù)為

其中,γ越大融合作用越大,wml作為融合權(quán)重懲罰使得高度相關(guān)的像素有較高的wml.上述模型引入松弛變量后采用近似擴(kuò)展拉格朗日乘數(shù)法(Inexact augmented lagrange multiplier,IALM)求解.

利用候選目標(biāo)稀疏表示之間的相關(guān)性的多任務(wù)稀疏表示跟蹤算法[56](Multi-task tracking,MTT)利用粒子空間位置的相關(guān)性產(chǎn)生的稀疏表示的相似性,對(duì)粒子的稀疏表示附加聯(lián)合稀疏性約束,即在每幀中盡可能使用較少的幾個(gè)相同原子來表示所有粒子,聯(lián)合稀疏性可以看作是全局的結(jié)構(gòu)正則化,能夠同時(shí)作用于所有粒子.n個(gè)候選目標(biāo)可由字典D線性表示:

其中,Z∈Rm×n為候選目標(biāo)的稀疏表示中對(duì)應(yīng)目標(biāo)模板的系數(shù)T,E∈Rd×n為對(duì)應(yīng)微模板的系數(shù),C=[ZT,ET]∈R(m+d)×n為候選目標(biāo)在當(dāng)前字典下的稀疏表示.

Zhang等在多任務(wù)跟蹤算法的基礎(chǔ)上,考慮粒子之間的結(jié)構(gòu)相關(guān)性和表示的空間平滑性,將候選目標(biāo)之間的空間位置關(guān)系引入到目標(biāo)函數(shù)中,從而將多任務(wù)跟蹤擴(kuò)展到結(jié)構(gòu)多任務(wù)跟蹤[57](Structured multi-task tracking,S-MTT).假定稀疏表示C是通過成對(duì)的相互作用而相關(guān).利用這些局部結(jié)構(gòu)先驗(yàn)對(duì)粒子的表示附加空間平滑性,即同一幀中空間位置比較近的粒子應(yīng)該具有相似的稀疏表示.定義對(duì)稱權(quán)重矩陣描述粒子i和的稀疏表示之間的相似性(分別為矩陣C的第i列和第列),其中,為粒子的中心坐標(biāo),i=1,2,···,n,為所有粒子之間距離的平均值.記為圖的度,L=A?W為圖的拉普拉斯,W表示圖中所有邊的權(quán)重.規(guī)范的圖平滑正則項(xiàng)為規(guī)范的稀疏表示中粒子間距離的加權(quán)和,每個(gè)距離項(xiàng)的權(quán)重反映了粒子之間相關(guān)性的強(qiáng)弱.圖正則項(xiàng)為,其中,為規(guī)范化的拉普拉斯矩陣.所以基于結(jié)構(gòu)的粒子稀疏表示可以通過直接附加圖正則項(xiàng)獲得:

其中,q=1,p∈{1,2,∞}.λ1和λ2分別用于平衡局部結(jié)構(gòu)正則項(xiàng)和全局結(jié)構(gòu)正則項(xiàng).當(dāng)λ1=0時(shí)為多任務(wù)跟蹤算法,當(dāng)λ1=0且p=1時(shí)為L(zhǎng)1跟蹤算法.S-MTT的目標(biāo)函數(shù)(10)由凸二次項(xiàng)和非平滑正則項(xiàng)組成,因此一般使用APG算法[58]求解.由于d?m,S-MTT和MTT算法的時(shí)間復(fù)雜度為 O(1/2),迭代次數(shù)為 O(1/2).

Hong等在多任務(wù)跟蹤的基礎(chǔ)上提出了多任務(wù)多視角聯(lián)合稀疏表示跟蹤算法[31].假定n個(gè)粒子每個(gè)由O個(gè)不同的特征表示,對(duì)于第o(o=1,2,···,O) 個(gè)特征,X(o)∈Rdo×n為n個(gè)特征向量組成的特征矩陣.第o個(gè)特征字典D(o)=[T(o),Ido]由m個(gè)目標(biāo)特征T(o)∈Rdo×m和對(duì)應(yīng)微模板Ido組成.通過多任務(wù)學(xué)習(xí)來獲得n個(gè)粒子的O個(gè)特征矩陣{X(1),X(2),···,X(O)}的稀疏表示{C(1),C(2),···,C(O)}.C(o)使得粒子在不同特征下具有不同的表示,每個(gè)特征下的稀疏表示的同一列為同一個(gè)樣本,因此同一個(gè)樣本在每個(gè)特征下的稀疏表示具有一定的相似性,所以能夠利用每個(gè)特征的獨(dú)立性并且獲得不同的統(tǒng)計(jì)特性.因此所有特征的稀疏表示可以水平方向堆疊起來分別構(gòu)成矩陣P和Q,每一個(gè)由所有特征下的稀疏表示系數(shù)組成.對(duì)于P的行組使用組Lasso約束來獲得所有候選目標(biāo)在所有特征上的共有特征,同樣的組Lasso約束作用于Q的列組來同時(shí)確定異常樣本.所以多任務(wù)多視角聯(lián)合稀疏表示的目標(biāo)函數(shù)為

多任務(wù)跟蹤算法利用粒子之間的自相似性一定程度上提高了跟蹤性能,但是當(dāng)候選目標(biāo)采樣區(qū)域較大時(shí)粒子之間的差異較大,通過多任務(wù)學(xué)習(xí)強(qiáng)制所有粒子共享同樣的結(jié)構(gòu)會(huì)降低跟蹤算法性能[59].即MTT跟蹤算法中利用粒子之間的相關(guān)性時(shí)沒有考慮粒子之間的差異性.所以魯棒多任務(wù)跟蹤算法[59]在求解稀疏表示時(shí)將稀疏表示系數(shù)矩陣分解成兩部分,考慮粒子的相似性對(duì)其中的一部分強(qiáng)加聯(lián)合稀疏正則項(xiàng),考慮粒子之間的差異性對(duì)另外一部分按照元素附加稀疏正則項(xiàng).魯棒多任務(wù)稀疏表示模型為

其中,候選目標(biāo)的稀疏表示為C=P+Q,其中,為矩陣P的第i行.對(duì)P附加聯(lián)合稀疏正則項(xiàng),對(duì)應(yīng)共享的結(jié)構(gòu).對(duì)Q按照元素附加稀疏正則項(xiàng),對(duì)應(yīng)非共享的特征.聯(lián)合稀疏性利用了粒子的相似性而按照元素附加的稀疏約束考慮了粒子之間的差異性.當(dāng)選擇合適的λ1使得P=0時(shí),算法為L(zhǎng)1跟蹤算法,當(dāng)選擇合適的λ2使得Q=0,算法為MTT跟蹤算法.對(duì)于P附加組稀疏正則項(xiàng),反映了粒子之間共享的共有結(jié)構(gòu),Q按照元素附加稀疏正則項(xiàng)反映了粒子之間的差異性,使得算法比L1跟蹤算法和MTT算法更加魯棒.上述模型可以基于加速梯度算法進(jìn)行求解.

為了提高多任務(wù)稀疏表示跟蹤算法的求解速度,文獻(xiàn)[60]提出了基于范數(shù)的多任務(wù)梯度最小化跟蹤算法.實(shí)驗(yàn)結(jié)果表明隨著字典中原子數(shù)量的增加,約束的重構(gòu)誤差基本一致,但是約束下的稀疏表示的求解時(shí)間增加很快,約束下的稀疏表示的求解時(shí)間增加較慢.隨著稀疏性正則項(xiàng)約束參數(shù)的變大,約束下的重構(gòu)誤差增加較快,約束下的重構(gòu)誤差先下降后保持不變,耗時(shí)方面約束下的求解時(shí)間先下降后增加,約束下的先增加而后基本保持不變,但是約束下的耗時(shí)始終低于約束下的耗時(shí).

由于稀疏表示本質(zhì)上是線性模型,稀疏表示反映了候選目標(biāo)和字典中原子之間的線性相關(guān)性,所以可以根據(jù)稀疏表示系數(shù)的大小即候選目標(biāo)和字典中原子的相關(guān)性的大小來確定目標(biāo)位置.Jia等提出了基于結(jié)構(gòu)局部稀疏表觀模型的跟蹤算法[39?40],這里的結(jié)構(gòu)實(shí)質(zhì)上指將相同空間位置上的圖像塊的稀疏表示作為候選目標(biāo)的特征,利用稀疏表示構(gòu)建觀測(cè)模型.由于每個(gè)圖像塊的位置固定,因此所有的局部圖像塊聯(lián)合起來能夠表示目標(biāo)完整的結(jié)構(gòu)信息.

文獻(xiàn)[30]利用跟蹤中運(yùn)動(dòng)平滑性建立下一幀相同位置圖像塊與當(dāng)前幀對(duì)應(yīng)位置圖像塊的相關(guān)性.候選目標(biāo)圖像塊特征與目標(biāo)對(duì)應(yīng)位置圖像塊特征之間的相關(guān)性使用部分置換矩陣Pk表示[30]:

其中,nk為目標(biāo)模板的數(shù)量,n為候選目標(biāo)的數(shù)量,k=1,2,···,K為單個(gè)目標(biāo)中提取的圖像塊個(gè)數(shù).式(13)三個(gè)約束項(xiàng)分別對(duì)應(yīng)每個(gè)目標(biāo)圖像塊對(duì)應(yīng)候選樣本中的一個(gè)圖像塊、每個(gè)樣本圖像塊最多對(duì)應(yīng)目標(biāo)圖像中的一個(gè)圖像塊和運(yùn)動(dòng)平滑性.為上式優(yōu)化后的部分置換矩陣,基于提取的特征F,則有,其中,是矩陣Pk的第i列,將第i個(gè)目標(biāo)模板和視頻中對(duì)應(yīng)圖像塊的特征堆疊起來構(gòu)成低秩矩陣Di,理想情況下秩為1,考慮到噪聲和遮擋優(yōu)化部分置換矩陣問題可以轉(zhuǎn)換為秩最小化問題:

上述模型中將秩使用矩陣的核范數(shù)代替,矩陣的零范數(shù)通過一范數(shù)代替后可以通過快速一階交替方向乘數(shù)法(Alternative direction method of multiplier,ADMM)求解.

Liu等將基于位置約束的稀疏表示和Meanshift結(jié)合提出了基于稀疏編碼直方圖的生成式算法[61?62].將候選目標(biāo)中所有的圖像塊在字典上的稀疏表示按照與目標(biāo)中心的距離使用核函數(shù)加權(quán)求和,歸一化后作為候選目標(biāo)在字典上的稀疏編碼直方圖.將稀疏編碼直方圖與所有圖像塊的重構(gòu)誤差進(jìn)行乘性結(jié)合作為目標(biāo)匹配的相似性度量函數(shù),利用了目標(biāo)與字典之間的相似性和目標(biāo)與字典基分布之間的相似性,最后采用Mean-shift迭代得到目標(biāo)的中心位置和尺度.相比粒子濾波框架下的稀疏表示跟蹤算法,將稀疏表示和均值漂移結(jié)合后經(jīng)過幾次迭代就可以獲得目標(biāo)的跟蹤位置,大大減少了稀疏表示的求解次數(shù).

2.2 判別式模型

稀疏表示的過程可以看作是二次特征提取的過程,因此稀疏表示本身可以作為目標(biāo)的特征,并且稀疏表示的特征更加線性可分.判別式模型根據(jù)目標(biāo)匹配相似性度量函數(shù)的不同可以分為基于分類器響應(yīng)的判別式算法[29,63]、基于稀疏表示差值的判別式算法[44]和多任務(wù)稀疏表示差值的判別式算法[64?65].

Wang等將稀疏表示和線性分類器結(jié)合提出了基于稀疏表示的判別式跟蹤算法[63],使用Logistic回歸來學(xué)習(xí)分類器,將分類器響應(yīng)作為目標(biāo)匹配的相似性度量.y為從候選目標(biāo)中提取的圖像塊的SIFT特征,基于彈性網(wǎng)[66]的稀疏表示模型為

其中,λ2>0保證了上述優(yōu)化問題是嚴(yán)格凸的.彈性網(wǎng)模型適用于字典中原子個(gè)數(shù)遠(yuǎn)大于原子維數(shù)的情況[67].Lasso模型利用的原子個(gè)數(shù)最多等于原子維數(shù),因此當(dāng)字典中原子個(gè)數(shù)遠(yuǎn)大于原子維數(shù)時(shí)使用Lasso模型是不合理的,而彈性網(wǎng)模型使得每個(gè)原子都可能被利用甚至所有的原子都能利用到.Lasso模型的正則項(xiàng)是凸的,而彈性網(wǎng)模型的正則項(xiàng)是嚴(yán)格凸的,能夠誘導(dǎo)出組效應(yīng)[68].

Zhuang等[44]利用候選目標(biāo)構(gòu)建字典,求解目標(biāo)模板和背景模板在字典下的稀疏表示,將樣本基于目標(biāo)的稀疏表示和基于背景的稀疏表示做差值構(gòu)建觀測(cè)模型.n個(gè)候選目標(biāo)為,模板集合由目標(biāo)模板和背景模板組成.為T中第i個(gè)模板基于X的稀疏表示,.由模板的重構(gòu)系數(shù)向量構(gòu)成矩陣,表示模板和候選目標(biāo)之間的相似性.為了保持相似候選目標(biāo)之間稀疏表示的相似性,引入Laplacian約束得到Laplacian多任務(wù)逆稀疏表示:

其中,L=A?B為L(zhǎng)aplacian矩陣.B是二值矩陣表示兩個(gè)候選目標(biāo)特征之間的相關(guān)性,如果位于的n0個(gè)最近鄰中,否則的度定義為,

Zhang等[65]基于時(shí)間上的連貫性而產(chǎn)生的目標(biāo)稀疏表示之間的相似性,將目標(biāo)跟蹤看作是連貫、稀疏和低秩問題.將候選目標(biāo)表示成字典D的線性組合X=DZ,其中,Z=為對(duì)應(yīng)候選目標(biāo)在字典上的稀疏表示.字典D=[Tpos,Tneg]由目標(biāo)模板Tpos和背景模板Tneg組成.由于目標(biāo)的表觀模型在短時(shí)間內(nèi)不會(huì)發(fā)生較大變化,因此利用時(shí)間連貫性跟蹤問題可以表示為

其中,||Z||?表示矩陣的核范數(shù),Z0的每列均為之前跟蹤結(jié)果的稀疏表示.||Z||1,1對(duì)于遮擋和噪聲具有較好的魯棒性.||Z?Z0||2,1產(chǎn)生(Z?Z0)列水平上的稀疏性,使得大多數(shù)候選目標(biāo)的稀疏表示與之前跟蹤結(jié)果的稀疏表示相似,同時(shí)允許少量候選目標(biāo)的稀疏表示與之前跟蹤結(jié)果的稀疏表示不同.||E||1,1確保模型對(duì)于稀疏重構(gòu)誤差的魯棒性,E的值和列的支撐是包含有信息的,當(dāng)E的值較大但為稀疏的列支撐時(shí)表示候選目標(biāo)中存在遮擋,當(dāng)E的值較大但為非稀疏的列支撐時(shí),表示候選目標(biāo)中包含較多背景信息.

在式(17)中當(dāng)λ1=λ3=0時(shí),算法為稀疏跟蹤算法(Sparse tracker,ST),與L1跟蹤算法相似.當(dāng)λ2=λ3=0時(shí),算法為低秩跟蹤算法(Low rank tracker,LRT),低秩性利用了候選目標(biāo)之間的相關(guān)性.當(dāng)且λ3=0時(shí),算法為低秩稀疏跟蹤算法[64](Low rank sparse tracker,LRST),LRST算法同時(shí)利用了候選目標(biāo)表示的稀疏性和低秩性.當(dāng)時(shí),算法為連貫低秩稀疏跟蹤算法(Consistent low rank sparse tracker,CLRST),CLRST算法將LRST算法使用時(shí)間連貫性進(jìn)行了推廣.引入等式約束和松弛變量將問題轉(zhuǎn)換后可以將式(17)通過近似擴(kuò)展拉格朗日乘數(shù)法求解.

多任務(wù)跟蹤算法MTT和連貫低秩稀疏跟蹤算法CLRST都利用了候選目標(biāo)之間的結(jié)構(gòu)信息,但是這種結(jié)構(gòu)的假設(shè)是不同的.MTT中通過使用||Z||2,1約束使得候選目標(biāo)由幾個(gè)相同的原子表示,使得Z的所有列彼此相似,間接地使表示矩陣Z的秩為1.CLRST算法將跟蹤置于低秩學(xué)習(xí)框架中約束目標(biāo)的表示位于低維子空間內(nèi),而不要求候選目標(biāo)使用同樣的原子表示,CLRST算法假定表示矩陣Z的秩較低(為1或大于1).MTT算法利用的是候選目標(biāo)之間的空間相關(guān)性產(chǎn)生的稀疏表示的相似性,而CLRST算法則是利用時(shí)間上的相關(guān)性產(chǎn)生的稀疏表示的相似性.

2.3 混合式模型

Zhong等[41?42]將基于重構(gòu)誤差的判別式模型和基于稀疏編碼直方圖的生成式模型進(jìn)行乘性結(jié)合提出了基于稀疏表示的混合式跟蹤算法.候選目標(biāo)基于目標(biāo)模板的稀疏重構(gòu)誤差為,基于背景模板的稀疏重構(gòu)誤差為,構(gòu)建的判別式模型的置信度為. 基于稀疏性的生成式模型為候選目標(biāo)中所有圖像塊基于目標(biāo)字典的稀疏表示按照空間位置依次連接起來構(gòu)成的稀疏編碼直方圖,并利用重構(gòu)誤差閾值將被遮擋圖像塊的稀疏表示置0,去除遮擋后的稀疏編碼直方圖為ρ,使用直方圖交叉函數(shù)來計(jì)算候選目標(biāo)ρ和模板ρ0之間的相似性.基于稀疏性的混合式模型為

其中,H給予正樣本較高的權(quán)重,因此H可以看作是F的權(quán)重.對(duì)于較難區(qū)分的目標(biāo),H≈1,此時(shí)F起主要作用,因此在混合式模型中生成式模型起著更為重要的作用.實(shí)驗(yàn)結(jié)果表明[41?42]大多數(shù)情況下混合式模型優(yōu)于單個(gè)的判別式模型和生成式模型.主要原因是判別式模型主要用來區(qū)分目標(biāo)和背景,不能夠有效處理遮擋,而基于局部特征的生成式模型能夠有效處理遮擋,而單獨(dú)的生成式模型不能夠有效處理復(fù)雜背景.混合式模型集成了二者的優(yōu)點(diǎn)使得算法的魯棒性較好.

3 模型更新

基于稀疏表示的跟蹤算法按照算法模型的不同更新的方案也不同.生成式模型中字典的組成不同,字典的在線更新方案也不盡相同.對(duì)于由目標(biāo)模板構(gòu)建的字典,L1跟蹤算法是通過計(jì)算跟蹤結(jié)果與字典中原子的相似度通過設(shè)定閾值來對(duì)原子進(jìn)行更新[24].由于跟蹤結(jié)果的正確與否不得而知,因此一旦將錯(cuò)誤的跟蹤結(jié)果更新到字典中,會(huì)導(dǎo)致模型退化.Zhang等[32]將字典中的模板分為固定模板、穩(wěn)定模板和變化模板.其中固定模板為第一幀中在人工標(biāo)定的基礎(chǔ)上提取的目標(biāo)模板,固定模板在跟蹤過程中保持不變.固定模板和穩(wěn)定模板主要用來阻止漂移,穩(wěn)定模板用來抓住跟蹤過程中目標(biāo)的穩(wěn)定特征,變化模板用來對(duì)目標(biāo)的變化作出響應(yīng),三種模板以不同的方式進(jìn)行更新.對(duì)于由PCA構(gòu)建的字典,則可以使用增量子空間學(xué)習(xí)算法實(shí)現(xiàn)PCA的在線更新[69],也可將其應(yīng)用于字典中模板的在線更新[39?40].文獻(xiàn)[70]將一階馬爾科夫鏈用于字典中原子的更新.

判別式模型的更新主要是在跟蹤結(jié)果的基礎(chǔ)上提取正負(fù)樣本對(duì)分類器進(jìn)行在線更新.由于跟蹤結(jié)果的正確與否是不可知的,因此在跟蹤結(jié)果的基礎(chǔ)上采集樣本的真實(shí)屬性也是未知的,所以分類器的更新過程更多的是半監(jiān)督訓(xùn)練和非監(jiān)督訓(xùn)練過程.Wang等[29]將候選目標(biāo)在初始分類器和新分類器上的響應(yīng)加權(quán)作為候選目標(biāo)的分類器響應(yīng),由于初始分類器是通過監(jiān)督訓(xùn)練得到的,可以一定程度上減輕分類器更新中的漂移.

4 算法復(fù)雜度分析

基于稀疏表示的視頻目標(biāo)跟蹤的算法復(fù)雜度較高[21],對(duì)于字典D∈Rm×n,粒子數(shù)量為N,基于Lasso的稀疏表示求解的算法時(shí)間復(fù)雜度為O(Nm2n3/2),因此一般通過以下三種方法提高算法速度:1)減少有效候選目標(biāo)的數(shù)量;2)降低字典的維數(shù);3)提高每次稀疏表示的求解速度.

減少有效候選目標(biāo)的數(shù)量的目的是為了減少稀疏表示的求解次數(shù),粒子濾波框架下傳統(tǒng)算法的稀疏表示求解次數(shù)等于粒子的個(gè)數(shù).為了減少每次跟蹤過程中1范數(shù)最小化的求解次數(shù),Mei等引入最小平方誤差界,在計(jì)算稀疏表示之前通過線性最小平方重構(gòu)誤差剔除大量的非重要粒子,從而減少了稀疏表示的計(jì)算次數(shù)[34].文獻(xiàn)[44?45]利用候選目標(biāo)構(gòu)建字典,將跟蹤問題看作識(shí)別問題,僅需要求解幾個(gè)目標(biāo)模板在由候選目標(biāo)組成的字典上的稀疏表示,大大減少了稀疏表示的計(jì)算次數(shù).

由于稀疏表示求解的算法復(fù)雜度與字典的維數(shù)成正比,因此可以通過降低字典維數(shù)來提高算法求解速度.降低字典維數(shù)可以通過以下兩種方法實(shí)現(xiàn):1)降低原子的維數(shù);2)減少字典中原子的個(gè)數(shù).文獻(xiàn)[32]利用協(xié)方差矩陣在實(shí)現(xiàn)特征融合的同時(shí)降低了特征的維數(shù).由于目標(biāo)模板中通常包括一些非線性的背景特征,Liu等[38]通過樣本標(biāo)簽分布學(xué)習(xí),利用稀疏模型建立正負(fù)樣本和標(biāo)簽之間的映射關(guān)系,通過判別式特征選擇目標(biāo)模板中包含的背景特征被剔除,選擇更具有判別力的特征實(shí)現(xiàn)特征降維.Li等[43]利用滿足約束等距性的測(cè)量矩陣同時(shí)作用于字典和候選目標(biāo)的特征實(shí)現(xiàn)降維.基于樣本標(biāo)簽學(xué)習(xí)的特征選擇方法降維和基于約束等距性的特征降維雖然形式一樣,都是將高維特征降維至低維空間,但二者有本質(zhì)的區(qū)別.基于標(biāo)簽學(xué)習(xí)的特征選擇降維方法是從高維特征空間中選擇更具判別力的特征實(shí)現(xiàn)降維.而基于約束等距性的特征降維是利用滿足約束等距性的哈希矩陣將高維特征降維至低維空間,在降維過程中保持了原始高維數(shù)據(jù)的空間結(jié)構(gòu).

為了在跟蹤魯棒性和算法速度之間做出折中,很多算法不得不采用低維數(shù)的字典,而低維特征下難以對(duì)目標(biāo)進(jìn)行精確描述.對(duì)于基于稀疏表示的判別式跟蹤算法而言,低維字典嚴(yán)重限制了稀疏表示的判別力,降低了目標(biāo)和背景的可分性.文獻(xiàn)[71]提出了基于乘積稀疏表示的支持向量跟蹤算法,將原始稀疏編碼問題分解為兩個(gè)較小子字典上的稀疏編碼問題,不僅使得等效字典中原子個(gè)數(shù)大大增加,使得目標(biāo)能夠獲得更高維的稀疏表示,而且降低了稀疏性求解過程的計(jì)算量,使得目標(biāo)和背景在高維的稀疏表示下更加線性可分,提高了跟蹤算法的魯棒性.

L1跟蹤算法字典中加入微模板是為了處理遮擋和噪聲等異常,Yan等[50]將字典中微模板去除,從重構(gòu)誤差的概率分布出發(fā)提出了加權(quán)Lasso模型,使算法模型適用于更為一般的噪聲.另外基于局部特征構(gòu)建的字典本身對(duì)于遮擋具有一定的魯棒性也不需要微模板.同時(shí)利用目標(biāo)和背景構(gòu)建的字典中也不包括微模板.

提高每次1范數(shù)最小化的計(jì)算速度,Bao等將加速最近梯度算法[35]引入到稀疏模型求解中,加速最近梯度算法的有效性在于它的二次收斂性.Li等[43]使用正交匹配追蹤算法求解稀疏表示,顯然要比L1跟蹤算法中的內(nèi)點(diǎn)法[72]速度要快得多.

5 實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)數(shù)據(jù)分析

如表1所示,自2013年以來出現(xiàn)了多個(gè)視頻目標(biāo)跟蹤算法評(píng)估的基準(zhǔn)數(shù)據(jù)庫[7,22,73?76].其中VOT2013[73]、OTB50[7]、VOT2014[77]和OTB100[22]為GT(Groundtruth)全標(biāo)注的基準(zhǔn)數(shù)據(jù)庫.PTB中為附帶景深的RGB-D圖像[74],受到景深探測(cè)器景深探測(cè)范圍的限制,無法獲取大景深的視頻,公開的視頻數(shù)據(jù)中只給出5個(gè)視頻的GT,并且當(dāng)目標(biāo)被全遮擋時(shí)GT的標(biāo)注為空,需要在線提交跟蹤結(jié)果進(jìn)行評(píng)估.ALOV++中按照影響視頻目標(biāo)跟蹤的因素將視頻分成13類,GT是每隔5幀標(biāo)注一次[75].NUS-PRO中將視頻分成5類:人臉視頻、行人視頻、運(yùn)動(dòng)員視頻、剛體視頻和長(zhǎng)視頻,每類視頻又分成不同的子類,所有圖像大小均為1280×720,沒有公開GT,需要在線提交跟蹤結(jié)果進(jìn)行評(píng)估[76].

5.2 評(píng)估方法討論

不同于目標(biāo)檢測(cè)、圖像分類等計(jì)算機(jī)視覺領(lǐng)域,目前為止視頻目標(biāo)跟蹤還沒有統(tǒng)一的評(píng)估標(biāo)準(zhǔn)[78?80].

表1 視頻跟蹤評(píng)估基準(zhǔn)數(shù)據(jù)Table 1 Summary of some visual tracking evaluation benchmark datasets

中心誤差[78](Center error in pixel,CE)定義為算法標(biāo)定的目標(biāo)中心和人工標(biāo)定的目標(biāo)中心之間的歐氏距離(像素).由于中心誤差不能反映目標(biāo)的尺度變化,因此后續(xù)提出了標(biāo)準(zhǔn)化的中心誤差,即將中心誤差除以目標(biāo)的大小.雖然標(biāo)準(zhǔn)化中心誤差一定程度上能夠反映目標(biāo)的尺度變化,但是中心誤差的大小會(huì)隨著目標(biāo)大小成比例的變化,并且跟蹤失敗后中心誤差可能是隨機(jī)產(chǎn)生的任意值,并不能反映算法的真實(shí)性能.

基于PASCAL VOC中目標(biāo)檢測(cè)的評(píng)估標(biāo)準(zhǔn)[81],算法重疊率(Overlap rate,OR)能夠同時(shí)較好地反應(yīng)算法的跟蹤位置和目標(biāo)尺度,且重疊率的值有界.基于重疊率閾值的跟蹤成功率(Success rate,SR)定義為重疊率大于閾值的比例.

由于不同的跟蹤任務(wù)對(duì)于跟蹤精度的要求不同,Wu等[7]提出了精度曲線和成功曲線.精度曲線[7](Precision plot)是指算法中心誤差小于中心誤差閾值的比例隨中心誤差閾值的變化情況,通常選擇中心誤差閾值為20像素時(shí)的值作為算法的跟蹤精度.成功曲線[7](Success plot)是指跟蹤成功率隨重疊率閾值的變化情況.通常選擇重疊率閾值[81]為0.5,但是由于跟蹤精度的要求不同選擇重疊率閾值為0.5不具有代表性,Wu等[7]利用成功曲線下的面積(Success rate area under curve,SR-AUC)作為算法評(píng)估的依據(jù).當(dāng)重疊率閾值選擇的足夠多時(shí),算法的SR-AUC值等于在所有實(shí)驗(yàn)視頻上重疊率的均值[78].

傳統(tǒng)的評(píng)估方法是對(duì)算法在整個(gè)視頻上運(yùn)行一次的跟蹤結(jié)果進(jìn)行評(píng)估,這里稱之為單次通過評(píng)估OPE(One-pass evaluation).但有些算法對(duì)于初始化(初始位置和初始幀)非常敏感,不同的初始化導(dǎo)致跟蹤結(jié)果的差別很大,并且很多算法跟蹤失敗后沒有重新初始化,導(dǎo)致失敗后的跟蹤結(jié)果往往是隨機(jī)的,沒有太大的參考價(jià)值.所以文獻(xiàn)[7]提出了算法初始化魯棒性評(píng)估標(biāo)準(zhǔn):時(shí)間魯棒性評(píng)估(Temporal robustness evaluation,TRE)和空間魯棒性評(píng)估(Spatial robustness evaluation,SRE).

時(shí)間魯棒性評(píng)估是指從不同的初始幀開始將跟蹤算法進(jìn)行多次評(píng)估,將多次評(píng)估的結(jié)果進(jìn)行平均得到TRE.

空間魯棒性評(píng)估是通過移動(dòng)初始幀GT的位置,縮放GT窗口的大小來評(píng)估算法對(duì)初始化誤差的敏感性.移動(dòng)GT的位置是將目標(biāo)的中心位置向上、下、左、右、左上、右上、左下、右下分別移動(dòng)對(duì)應(yīng)維度的10%,其中向上下左右移動(dòng)時(shí),GT的尺度不變;向左上、右上、左下、右下移動(dòng)時(shí)寬度和高度分別增加對(duì)應(yīng)維度的10%.縮放GT窗口是指GT的中心位置不變,將GT的寬度和高度分別變?yōu)樵瓉韺挾群透叨鹊?0%、90%、110%、120%.空間魯棒性評(píng)估是上述12個(gè)評(píng)估的均值.文獻(xiàn)[7]的實(shí)驗(yàn)結(jié)果表明同一算法的平均TRE一般高于OPE,這主要是由于跟蹤算法一般在較短的視頻上的跟蹤效果較好,這也說明誤差累積產(chǎn)生的漂移是導(dǎo)致跟蹤失敗的重要原因.平均的SRE一般低于OPE,這主要是由于SRE中不精確的初始化導(dǎo)致后續(xù)跟蹤漂移較快,這也說明了目標(biāo)精確初始化的重要性.

由于跟蹤失敗之后算法跟蹤結(jié)果往往是隨機(jī)產(chǎn)生的,導(dǎo)致失敗后的跟蹤結(jié)果沒有太大的參考價(jià)值,并且沒有人為干預(yù)時(shí)算法一般很難再跟蹤上目標(biāo).等價(jià)于算法的評(píng)估過程中僅使用了視頻的一部分,并沒有充分利用整個(gè)視頻數(shù)據(jù).并且一個(gè)視頻中可能包含多個(gè)挑戰(zhàn)因素,算法可能對(duì)于視頻中的某個(gè)因素是魯棒的,而對(duì)于另外的因素是不魯棒的.因此VOT2014中提出了新的魯棒性評(píng)估標(biāo)準(zhǔn)[77].在跟蹤過程中當(dāng)重疊率小于閾值時(shí)對(duì)目標(biāo)進(jìn)行重新初始化,將重新初始化的次數(shù)作為算法魯棒性的評(píng)估標(biāo)準(zhǔn),重新初始化的次數(shù)越少說明算法的魯棒性越好,反之說明算法的魯棒性越差.但是由于實(shí)際跟蹤中導(dǎo)致跟蹤失敗的原因可能是多個(gè)因素共同作用的結(jié)果,上述方法難以對(duì)單一挑戰(zhàn)因素進(jìn)行有效剝離.

處理速度是視頻目標(biāo)跟蹤算法需要考慮的重要因素,按照實(shí)時(shí)性的要求算法處理速度需要達(dá)到每秒20幀以上,即單幀處理時(shí)間小于50ms.由于視頻圖像的分辨率不同,跟蹤目標(biāo)區(qū)域的大小不同,以及算法實(shí)現(xiàn)環(huán)境不同,這些都會(huì)影響到算法的處理速度,因此算法的實(shí)時(shí)性評(píng)估需要綜合考慮多方面因素.

由上述分析可知,盡管目前跟蹤算法的評(píng)估標(biāo)準(zhǔn)較多,但是核心的評(píng)估標(biāo)準(zhǔn)還是基于GT的中心誤差和重疊率.因此本文主要選取中心誤差和重疊率的均值和標(biāo)準(zhǔn)差、跟蹤成功曲線、跟蹤精度曲線、跟蹤成功率和算法單幀平均處理時(shí)間作為評(píng)估標(biāo)準(zhǔn).

5.3 實(shí)驗(yàn)結(jié)果與分析

將現(xiàn)有公開代碼的基于稀疏表示的跟蹤算法總結(jié)如表2所示.實(shí)驗(yàn)在Intel(R)Core(TM)i7-3770CPU@3.40GHz,內(nèi)存16.0GB的64位計(jì)算機(jī)上通過Matlab(R2014a)軟件實(shí)現(xiàn).測(cè)試視頻為OTB50上的50個(gè)視頻[7],共計(jì)29507幀.實(shí)驗(yàn)中算法均采用相同的初始位置,算法中的參數(shù)均采用源代碼中的默認(rèn)參數(shù).算法中如果涉及粒子濾波框架下的仿射變換模型,則采用相同的仿射變換標(biāo)準(zhǔn)差和粒子個(gè)數(shù).為了獲得客觀的比較結(jié)果,將算法在測(cè)試視頻上的5次實(shí)驗(yàn)結(jié)果的平均值作為最終的實(shí)驗(yàn)結(jié)果.需要指出的是由于實(shí)驗(yàn)中目標(biāo)的初始位置、參數(shù)設(shè)置、粒子個(gè)數(shù)、實(shí)現(xiàn)環(huán)境和硬件平臺(tái)等與相關(guān)文獻(xiàn)中可能有所不同,以及算法本身含有的某些隨機(jī)因素,某些實(shí)驗(yàn)結(jié)果和算法速度與相關(guān)文獻(xiàn)中給出的結(jié)果有出入,但是從大量實(shí)驗(yàn)結(jié)果的比較中得出的算法總體性能與相關(guān)文獻(xiàn)一致.

上述基于稀疏表示的跟蹤算法在OTB50上的跟蹤精度[7]隨中心誤差閾值的變化曲線如圖4所示,其中右下角為對(duì)應(yīng)算法在中心誤差閾值為20像素時(shí)的跟蹤精度,MDNet為文獻(xiàn)[82]提出算法,DLSSVM 為文獻(xiàn)[83]提出算法,CFNet-conv5為文獻(xiàn)[84]提出算法.

上述基于稀疏表示的跟蹤算法在OTB50上的跟蹤成功率隨重疊率閾值的變化曲線[7]如圖5所示,其中右上角為對(duì)應(yīng)算法成功率曲線下的面積.

當(dāng)跟蹤成功率的重疊率閾值設(shè)為0.5時(shí)[81],上述算法在OTB50上的跟蹤成功率如表3所示.

表4給出上述基于稀疏表示的視頻目標(biāo)跟蹤算法在OTB50上的單幀平均處理時(shí)間,其中實(shí)現(xiàn)環(huán)境中“M”表示使用Matlab編程實(shí)現(xiàn),“MC”表示使用Matlab和C/C++ 混合編程實(shí)現(xiàn),“E”表示使用可執(zhí)行的二值代碼實(shí)現(xiàn).從表4中可以看出,目前Matlab環(huán)境下大多數(shù)基于稀疏表示的視頻目標(biāo)跟蹤算法還難以實(shí)現(xiàn)實(shí)時(shí)跟蹤.這主要是由于此類算法大多是在粒子濾波框架下進(jìn)行,粒子數(shù)量是直接影響算法速度的主要因素,另外稀疏表示求解的算法時(shí)間復(fù)雜度較高也是影響算法速度的重要原因.

表2 算法簡(jiǎn)稱和論文代碼地址Table 2 The sparse trackers abbreviation,paper and codes URL

表2 算法簡(jiǎn)稱和論文代碼地址Table 2 The sparse trackers abbreviation,paper and codes URL

算法論文題目和代碼地址Robust visual tracking using l1 mimization.In ICCV,2009.http://www.dabi.temple.edu/～hbling/publication-selected.htm LSK Robust tracking using local sparse appearance model and k-selection.In CVPR,2011.http://www.uky.edu/～lya227/spt.html L1APG Real time robust l1 tracker using accelerated proximal gradient approach.In CVPR,2012.http://www.dabi.temple.edu/～hbling/publication-selected.htm ASLA Visual tracking via adaptive structural local sparse appearance model.In CVPR,2012.http://ice.dlut.edu.cn/lu/publications.html SCM Robust object tracking via sparsity-based collaborative model.In CVPR,2012.http://ice.dlut.edu.cn/lu/publications.html MTT Robust visual tracking via multi-task sparse learning.In CVPR,2012.http://faculty.ucmerced.edu/mhyang/pubs.html LRT Low-rank sparse learning for robust visual tracking.In ECCV,2012.http://faculty.ucmerced.edu/mhyang/pubs.html CT Real-time compressive tracking.In ECCV,2012.http://www4.comp.polyu.edu.hk/～cslzhang/papers.htm DLSR Online discriminative object tracking with local sparse representation.In WACV,2012.http://faculty.ucmerced.edu/mhyang/pubs.html SRPCA Online object tracking with sparse prototypes.In TIP,2013.http://ice.dlut.edu.cn/lu/publications.html DSSM Visual trcking via discriminative sparse similiarity map.In TIP,2014.http://ice.dlut.edu.cn/lu/publications.html SST Structural sparse tracking.In CVPR,2015.http://nlpr-web.ia.ac.cn/mmc/homepage/tzzhang/index.html CST In defense of sparse tracking:Circulant sparse tracker.In CVPR,2016 http://nlpr-web.ia.ac.cn/mmc/homepage/tzzhang/index.html L1

表3 算法跟蹤成功率(%)比較Table 3 The trackers success rate(%)comparison

表3 算法跟蹤成功率(%)比較Table 3 The trackers success rate(%)comparison

算法 ASLA SCM CST SST LRT LSK MTT DSSM CT L1APG L1 DLSR SRPCA成功率 70.69 68.96 68.20 59.30 59.02 56.09 54.98 45.80 42.29 41.61 35.56 34.22 25.83

表4 算法單幀平均處理時(shí)間比較(ms)Table 4 The comparison of trackers average processing time(ms)

表4 算法單幀平均處理時(shí)間比較(ms)Table 4 The comparison of trackers average processing time(ms)

算法 ASLA SCM CST SST LRT LSK MTT DSSM CT L1APG L1 DLSR SRPCA實(shí)現(xiàn)環(huán)境 MC MC M M M ME M M MC MC MC MC MC時(shí)間 241 7846 454 450 3152 382 2279 586 12 79 397 23030 249

圖4 算法跟蹤精度隨中心誤差閾值的變化曲線Fig.4 The trackers tracking precision versus center error threshold

表5給出上述基于稀疏表示的跟蹤算法的模型組成和其在OTB50上的重疊率的統(tǒng)計(jì)特征比較.

從上述實(shí)驗(yàn)結(jié)果和算法模型的分析比較可以看出,特征字典上大多數(shù)算法直接使用灰度特征構(gòu)建字典,從算法重疊率的比較可以看出基于局部灰度特征構(gòu)建的字典明顯優(yōu)于基于全局灰度構(gòu)建的字典,這主要是由于局部圖像塊對(duì)于遮擋和局部表觀變化具有一定的魯棒性,所有圖像塊組合起來又能夠表示目標(biāo)完整的結(jié)構(gòu)信息,而全局灰度特征顯然不具有上述優(yōu)勢(shì).

運(yùn)動(dòng)模型上仿射運(yùn)動(dòng)能夠精確描述目標(biāo)的尺度變化和旋轉(zhuǎn),所以大多數(shù)基于稀疏表示的跟蹤算法采用仿射運(yùn)動(dòng)模型.搜索方案上粒子濾波和稠密采樣能夠有效避免陷入局部最優(yōu)但計(jì)算量較大,直接表現(xiàn)為算法的單幀處理時(shí)間較高,均值漂移效率較高但是容易陷入局部最優(yōu),導(dǎo)致跟蹤性能下降.

圖5 算法跟蹤成功率隨重疊率閾值的變化曲線Fig.5 The trackers success rate versus overlap rate threshold

從重疊率的統(tǒng)計(jì)特征比較可以看出ASLA算法和SCM 算法取得了較好的跟蹤性能,遠(yuǎn)高于其他基于稀疏表示的跟蹤算法.并且文獻(xiàn)[7]的實(shí)驗(yàn)結(jié)果表明,與其他非稀疏表示跟蹤算法的橫向比較中,ASLA算法和SCM算法的跟蹤性能也較為優(yōu)異.這主要是由于ASLA算法和SCM算法均采用了結(jié)構(gòu)化的分塊稀疏表示機(jī)制,同時(shí)利用了目標(biāo)的局部表觀和空間結(jié)構(gòu)信息.因此在稀疏表示跟蹤算法中分塊稀疏表示和空間結(jié)構(gòu)信息對(duì)于魯棒視頻目標(biāo)跟蹤是至關(guān)重要的.

6 結(jié)論與展望

伴隨著稀疏表示理論的不斷發(fā)展,基于稀疏表示的視頻目標(biāo)跟蹤研究也取得了較大進(jìn)展.但是對(duì)于復(fù)雜環(huán)境下的持續(xù)魯棒跟蹤問題,仍然存在一些亟待解決的問題.在上述研究的基礎(chǔ)上,作者認(rèn)為以下幾個(gè)方面是值得繼續(xù)研究的方向.

表5 基于稀疏表示的視頻跟蹤算法模型和重疊率比較Table 5 The comparison of the sparse representation-based trackers model and overlap rate mean and std

表5 基于稀疏表示的視頻跟蹤算法模型和重疊率比較Table 5 The comparison of the sparse representation-based trackers model and overlap rate mean and std

算法簡(jiǎn)稱 特征字典 運(yùn)動(dòng)模型 搜索方案 匹配模式 模型更新 重疊率均值 重疊率標(biāo)準(zhǔn)差A(yù)SLA 局部灰度 仿射運(yùn)動(dòng) 粒子濾波 生成式 增量學(xué)習(xí) 0.5860 0.3225 SCM 局部灰度 仿射運(yùn)動(dòng) 粒子濾波 混合式 模板替換 0.5562 0.3436 CST HOG 仿射運(yùn)動(dòng) 粒子濾波 生成式 模板替換 0.5480 0.3063 LRT 全局灰度 仿射運(yùn)動(dòng) 粒子濾波 判別式 模板替換 0.4841 0.3247 SST 局部灰度 仿射運(yùn)動(dòng) 粒子濾波 生成式 模板替換 0.4840 0.3187 LSK 局部灰度 相似性變換 均值漂移 生成式 加權(quán)更新 0.4801 0.3379 MTT 全局灰度 仿射運(yùn)動(dòng) 粒子濾波 生成式 模板替換 0.4623 0.3411 CT 擴(kuò)展類haar 平移運(yùn)動(dòng) 稠密采樣 判別式 Bayes更新 0.3909 0.2850 DSSM 全局灰度 仿射運(yùn)動(dòng) 粒子濾波 判別式 模板替換 0.3818 0.3520 L1APG 全局灰度 仿射運(yùn)動(dòng) 粒子濾波 生成式 模板替換 0.3660 0.3565 DLSR 局部灰度 仿射運(yùn)動(dòng) 粒子濾波 判別式 SVM更新 0.3116 0.3414 L1 全局灰度 仿射運(yùn)動(dòng) 粒子濾波 生成式 模板替換 0.3068 0.3687 SRPCA 全局PCA 仿射運(yùn)動(dòng) 粒子濾波 生成式 增量學(xué)習(xí) 0.2412 0.3321

1)上述稀疏表示模型中的正則項(xiàng)只考慮了信號(hào)的稀疏性,沒有考慮圖像本身的特性[85].圖像作為二維信號(hào),具有很強(qiáng)的空間相關(guān)性,表現(xiàn)為局部光滑特性.因此針對(duì)圖像的重構(gòu),基于圖像離散梯度稀疏性的最小全變分模型更適合二維圖像重構(gòu),且重構(gòu)結(jié)果精確魯棒.所以最小全變分模型框架下的稀疏表示跟蹤算法是重要的研究方向.

2)由于基于稀疏表示的視頻跟蹤中字典和目標(biāo)特征是不斷變化的,也就是構(gòu)成子空間的支撐集和待重構(gòu)信號(hào)是不斷變化的,因此基于稀疏表示的跟蹤算法本質(zhì)上是動(dòng)態(tài)稀疏表示問題[86],也就是目標(biāo)特征是具有動(dòng)態(tài)特性的時(shí)變稀疏信號(hào).而上述模型中為了研究問題的方便均將其看做靜態(tài)稀疏信號(hào)的重構(gòu)問題,所以動(dòng)態(tài)稀疏表示下的跟蹤算法也是值得研究的重要問題.

3)由上述研究現(xiàn)狀可以看出稀疏表示跟蹤算法仍然難以實(shí)現(xiàn)實(shí)時(shí)跟蹤,除了算法優(yōu)化外,研究新的域下的稀疏表示的快速求解[87?88]是提高算法速度的關(guān)鍵,也是面向?qū)嶋H應(yīng)用的重要問題.

4)目前稀疏表示跟蹤算法的字典構(gòu)建主要是人工設(shè)計(jì)完成,基于學(xué)習(xí)的字典構(gòu)建方法還比較少.深度學(xué)習(xí)在視頻目標(biāo)跟蹤中展現(xiàn)出的強(qiáng)大優(yōu)勢(shì)[82,84],尤其是在對(duì)目標(biāo)特征提取和表示方面,因此基于深度學(xué)習(xí)的字典構(gòu)建方案也是提高稀疏表示跟蹤算法魯棒性的重要方向.