一種改進(jìn)的快速壓縮跟蹤算法

潘 磊，束 鑫，祁云嵩

(江蘇科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院，江蘇鎮(zhèn)江212003)

目標(biāo)跟蹤，也稱視覺跟蹤，是計算機(jī)視覺領(lǐng)域的一個熱點問題，在視頻監(jiān)控、人機(jī)交互、視頻壓縮、行為分析等方面具有廣泛的應(yīng)用價值［1-2］.在跟蹤過程中，首先通過人工在視頻首幀選擇出目標(biāo)，其次對目標(biāo)進(jìn)行建模，然后利用預(yù)測或優(yōu)化算法估計目標(biāo)的下一幀位置，并對目標(biāo)模型進(jìn)行更新，從而進(jìn)入迭代過程.傳統(tǒng)的目標(biāo)跟蹤算法包括確定性方法和統(tǒng)計性方法，兩者的代表分別為Mean Shift和粒子濾波.確定性方法計算量小，實時性高，但準(zhǔn)確性相對較低;統(tǒng)計性方法計算量大，準(zhǔn)確性高，但實時性相對較低［3-4］.

近年來，目標(biāo)跟蹤算法得到了眾多的關(guān)注和研究.例如，文獻(xiàn)［5］中提出一種基于超像素的鑒別外觀模型，使用超像素中捕獲的結(jié)構(gòu)信息生成目標(biāo)特征，較好解決了目標(biāo)遮擋和漂移問題;文獻(xiàn)［6］中將目標(biāo)跟蹤表達(dá)為結(jié)構(gòu)化多任務(wù)稀疏學(xué)習(xí)問題，對目標(biāo)遮擋、光照變化、姿態(tài)變形等具有較好的效果，并有效降低了粒子濾波計算的復(fù)雜度;文獻(xiàn)［7］中將圖像分割與目標(biāo)跟蹤相結(jié)合，采用像素空間與顏色特征，同時解決了跟蹤與分割兩類問題;文獻(xiàn)［8］中提出一種基于壓縮感知的跟蹤算法，將目標(biāo)高維特征投影到低維空間，提高了跟蹤的實時性，并具有較高的準(zhǔn)確性.雖然研究取得了較快的進(jìn)展，但由于噪聲、遮擋、光照、運動等不利因素的影響，解決目標(biāo)跟蹤問題仍然存在許多困難.

1快速壓縮跟蹤算法

1.1 壓縮感知

不完備線性測量信號的重建與高維特征的降維一直是模式識別領(lǐng)域的基本研究方向.壓縮感知［9-14］是近年來出現(xiàn)的一種新型采樣理論，能夠在遠(yuǎn)遠(yuǎn)小于奈奎斯特采樣頻率的條件下還原初始信號，得到了學(xué)術(shù)界的廣泛關(guān)注.

高維信號采樣的過程可以由式(1)表示:

式中:x為K稀疏的n維原始信號;y為m維的采樣信號;Φ為m×n的觀測矩陣.根據(jù)壓縮感知理論，當(dāng)n?m時，如果Φ滿足有限等距性質(zhì)(restricted isometry property，RIP)，則采樣y可以有很高的概率重建信號x，均勻分布矩陣、隨機(jī)高斯矩陣、隨機(jī)貝努利矩陣等都是滿足有限等距性質(zhì)的矩陣，然而，這些矩陣包含的非零元素較多，運算量較大，實際計算時，經(jīng)常采用以下符合有限等距性質(zhì)且具有稀疏特征的矩陣，如式(2)所示.

1.2 快速壓縮跟蹤算法

通過上文描述可以看出，壓縮感知技術(shù)可以在降低信號維數(shù)的同時，基本保留原有信號的全部特性，從而能夠在不降低計算精度的前提下，大大提高運算的效率.文獻(xiàn)［8］中將壓縮感知思想引入目標(biāo)跟蹤領(lǐng)域，首先按照下式構(gòu)造各向異性的均值濾波器:

式中:w和h為目標(biāo)的寬和高，將濾波器與目標(biāo)進(jìn)行卷積后，生成目標(biāo)的高維特征，然后使用式(2)的觀測矩陣將目標(biāo)高維特征壓縮到低維空間，生成對應(yīng)的目標(biāo)低維特征，最后，通過貝葉斯分類器對各候選目標(biāo)進(jìn)行分類，選擇分類器輸出最大值所對應(yīng)的候選目標(biāo)作為下一幀中的目標(biāo)，并更新分類器.

實驗中發(fā)現(xiàn)，在各向異性均值濾波器的使用中，將模板內(nèi)的所有像素按照相同的重要性權(quán)值進(jìn)行計算;而實際中，往往是靠近模板中心點的像素應(yīng)該賦予更高的權(quán)值，遠(yuǎn)離模板中心點的像素賦予較低的權(quán)值，并且，當(dāng)濾波器的尺度超出一定的范圍時，濾波產(chǎn)生的新圖像已失去原始圖像的大部分信息，如圖1所示，此時，將這些新圖像作為目標(biāo)特征，效果并不顯著.

圖1 多尺度濾波效果Fig.1 Results of multi-scale filtering

2 改進(jìn)的快速壓縮跟蹤算法

2.1 利用多種多尺度濾波器生成目標(biāo)高維特征

由上文分析可以看出，單純使用各向異性均值濾波器產(chǎn)生目標(biāo)高維特征存在一定的缺陷，不僅降低了模板臨近中心點像素的權(quán)值，而且超過一定的尺度后，濾波產(chǎn)生的新圖像失去了原始目標(biāo)的大部分特征.針對以上問題，文中提出一種改進(jìn)的策略，在目標(biāo)高維特征生成過程中，不僅使用各向異性均值濾波器，同時增加圓形均值濾波器、中值濾波器、高斯濾波器、log濾波器對目標(biāo)進(jìn)行濾波，共同生成目標(biāo)高維特征，并且，在濾波過程中，各濾波器的尺度限制在原始目標(biāo)尺度的50%范圍內(nèi)，具體如式(4)所示:

式中:x為目標(biāo)高維特征;F為濾波器;i和j分別為濾波器的寬和高;w和h分別為目標(biāo)的寬和高;T為目標(biāo);符號“*”為卷積;符號“∪”為連接操作，用于將卷積后生成的新圖像連接起來生成目標(biāo)高維特征.

與文獻(xiàn)［8］中單純使用各向異性均值濾波器相比，改進(jìn)的方法使用了5種濾波器，考慮了對模板像素臨近中心點和遠(yuǎn)離點不同權(quán)值分配的衡量，能夠?qū)δ繕?biāo)特征進(jìn)行更加準(zhǔn)確和全面的描述.通過控制濾波器的尺度，各種濾波器單獨產(chǎn)生的濾波圖像數(shù)量變?yōu)槲墨I(xiàn)［9］中的25%，但由于采用了5種濾波器，濾波圖像的總數(shù)量，即目標(biāo)高維特征維數(shù)不降反升，超出了文獻(xiàn)［8］中數(shù)量的25%，因此更多的保留了原始圖像的信息.

2.2 基于壓縮感知理論生成目標(biāo)低維特征

得到目標(biāo)高維特征后，采用壓縮感知理論生成目標(biāo)低維特征.文獻(xiàn)［9］中證明，對于式(2)，采用ρ=能夠獲得較快的運算速度，且準(zhǔn)確性幾乎不會降低.然而，對目標(biāo)圖像經(jīng)過多尺度濾波后生成的高維特征，n的數(shù)量級可以達(dá)到106以上，此時觀測矩陣Φ中非零元的數(shù)量仍然較多.文中采用文獻(xiàn)［8］中的方法，令ρ=n/lg n，此時雖然準(zhǔn)確性會有所降低，但Φ中非零元的數(shù)量得到了指數(shù)級的下降，因此計算速度得到顯著提升.

當(dāng)n的數(shù)量級為10d時，Φ中非零元的數(shù)量約為md，即每行有d個非零元，實際計算時，只需記住這些非零元的位置和數(shù)值即可.因此，目標(biāo)低維特征y的生成速度是相當(dāng)快的.

2.3 目標(biāo)與候選目標(biāo)相似性度量

獲得目標(biāo)與候選目標(biāo)的低維特征后，下一步的工作就是采用相似性度量比較目標(biāo)與候選目標(biāo)之間的差異.文獻(xiàn)［8］中通過貝葉斯分類器進(jìn)行判斷，選擇分類器最大響應(yīng)值對應(yīng)的候選目標(biāo)作為下一幀的目標(biāo).然而，由于在高維特征構(gòu)造過程中各向異性均值濾波器存在缺陷，分類器的分類效果受到一定的影響.針對此問題，引入Bhattacharyya系數(shù)進(jìn)行改進(jìn).

首先，假設(shè)候選目標(biāo)為正負(fù)樣本的概率相同，采用貝葉斯分類器對候選目標(biāo)進(jìn)行分類計算，如式(5)所示.

式中:c+為正樣本;c－為負(fù)樣本.分類器的更新策略按照文獻(xiàn)［8］的方法進(jìn)行.

其次，采用Bhattacharyya系數(shù)計算目標(biāo)與候選目標(biāo)之間的相似度，如式(6)所示.

式中，y為目標(biāo);y^為候選目標(biāo);p和q分別為y和y^的概率分布.

得到候選目標(biāo)的貝葉斯分類器輸出及其與目標(biāo)之間的Bhattacharyya相似度后，以兩者的乘積作為目標(biāo)與候選目標(biāo)之間最終的相似程度，并選擇最大值所對應(yīng)的候選目標(biāo)作為下一幀的目標(biāo)，如式(7)和式(8)所示.

2.4 算法流程

根據(jù)以上描述，得到改進(jìn)的快速壓縮跟蹤算法流程如下:①根據(jù)式(4)計算當(dāng)前幀目標(biāo)和下一幀對應(yīng)位置的δ鄰域范圍內(nèi)所有候選目標(biāo)的高維特征;②利用式(2)的觀測矩陣，通過式(1)將①中所有的高維特征投影到低維空間，得到對應(yīng)的低維特征;③根據(jù)式(5～7)計算候選目標(biāo)與目標(biāo)之間的相似度，并按照式(8)取相似度最大的候選目標(biāo)作為下一幀的目標(biāo);④更新分類器，進(jìn)入下一次迭代.

3 實驗結(jié)果與分析

實驗在Intel Core i5 M480CPU，4GB內(nèi)存的筆記本電腦進(jìn)行，采用Matlab 2013b編程，測試的6段視頻來源于 MILT視頻庫［15］和 LOT視頻庫［16］.采用 PASCAL 指標(biāo)［8，16-17］衡量跟蹤算法性能，如式(9)所示.

式中:TB為跟蹤算法目標(biāo)邊界框;GT為真實目標(biāo)邊界框.當(dāng)兩者完全重疊時，Pr取值為1，當(dāng)兩者完全不重疊時，Pr取值為0，一般當(dāng)Pr取值大于0.5時，認(rèn)為跟蹤成功.

改進(jìn)算法的實驗結(jié)果包括定性分析和定量分析兩個部分.圖2～5列舉了算法在部分視頻庫上跟蹤的定性結(jié)果.表1列舉了算法在視頻庫上跟蹤的定量結(jié)果以及與常用的 MILT［15］，TLD［18］和FCT［8］算法比較的結(jié)果.

由圖2～5可以看出，文中提出的改進(jìn)算法在光照、遮擋、運動、變形等不利因素的干擾下，能夠較準(zhǔn)確跟蹤各種目標(biāo).表1中，粗體顯示的數(shù)字表示對應(yīng)視頻中的跟蹤效果最好.從表1的對比可以看出，文中算法與常用跟蹤算法相比，在準(zhǔn)確率上具有一定的優(yōu)勢，在5段視頻的跟蹤上取得最高的準(zhǔn)確率;TLD算法在最后一個視頻中取得最高的準(zhǔn)確率.

圖2 David序列部分跟蹤結(jié)果Fig.2 Partial results of tracking David sequence

圖3 Football序列部分跟蹤結(jié)果Fig.3 Partial results of tracking Football sequence

圖4 Girl序列部分跟蹤結(jié)果Fig.4 Partial results of tracking Girl sequence

圖5 Faceocc序列部分跟蹤結(jié)果Fig.5 Partial results of tracking Faceocc sequence

表1 各算法PASCAL指標(biāo)Table 1 PASCAL index of each algorithm

經(jīng)分析發(fā)現(xiàn)，算法在目標(biāo)發(fā)生較大遮擋、運動和形變時，容易出現(xiàn)跟蹤錯誤的情況.例如，F(xiàn)ootball視頻中從287幀開始，跟蹤的目標(biāo)產(chǎn)生嚴(yán)重遮擋，且遮擋物體的特征與目標(biāo)的特征幾乎完全相似，于是產(chǎn)生跟蹤錯誤，跟蹤的目標(biāo)由原目標(biāo)轉(zhuǎn)移到了遮擋物體上，如圖6所示;Sylv視頻中從第896幀開始，跟蹤的目標(biāo)出現(xiàn)較大的運動和形變，跟蹤逐步出現(xiàn)誤差，直至929幀出現(xiàn)PASCAL指標(biāo)低于0.5的情況，然而，隨著運動與形變的逐漸減弱，從965幀開始PASCAL指標(biāo)逐步恢復(fù)到0.5以上，并重新準(zhǔn)確跟蹤目標(biāo)，如圖7所示.

圖6 Football視頻跟蹤錯誤的幀F(xiàn)ig.6 Falsely tracked frames in Football video

圖7 Sylv視頻跟蹤錯誤的幀F(xiàn)ig.7 Falsely tracked frames in Sylv video

4 結(jié)論

根據(jù)快速壓縮跟蹤算法存在的問題，在目標(biāo)高維特征生成過程中，引入多種多尺度濾波器與原始目標(biāo)進(jìn)行卷積，不僅保留了目標(biāo)盡可能多的信息，并且通過限制濾波器尺度的范圍，避免了無效信息對算法的影響，同時，由于多種濾波器的使用，目標(biāo)有效信息的維數(shù)得到了一定的提高，為后續(xù)跟蹤的準(zhǔn)確進(jìn)行奠定了基礎(chǔ).按照壓縮感知理論，經(jīng)過觀測矩陣采樣后生成的目標(biāo)低維特征保留了目標(biāo)幾乎所有的信息，然后通過貝葉斯分類器輸出與Bhattacharyya系數(shù)乘積的形式，完成下一幀目標(biāo)位置的計算，在一定程度上抵消了分類器產(chǎn)生的誤差.下一步的工作，將圍繞高維特征模型展開，解決目前算法對較大遮擋、運動和形變敏感的缺點，這也是目標(biāo)跟蹤領(lǐng)域研究的主要困難之一.

References)

［1］ Li Xi，Hu Weiming，Shen Chunhua，et al.A survey of appearance models in visual object tracking［J］.ACM Transactions on Intelligent Systems and Technology，2013，4(4):58.

［2 ］ Guo Yanwen，Chen Ye，Tang Feng，et al.Object tracking using learned feature manifolds［J］.Computer Vision and Image Understanding，2014，118:128-139.

［3］ 王新紅，王晶，田敏，等.基于空間邊緣方向直方圖的Mean Shift跟蹤算法［J］.中國圖象圖形學(xué)報，2008，13(3):586-592.Wang Xinhong，Wang Jing，Tian Min，et al.Mean shift tracking algorithm based on spatial edge orientation histograms［J］.Journal of Image and Graphics，2008，13(3):586-592.(in Chinese)

［4］ 初紅霞，謝忠玉，王君祥，等.空間相關(guān)背景加權(quán)直方圖均值漂移目標(biāo)跟蹤［J］.控制與決策，2014，29(3):528-532.Chu Hongxia，Xie Zhongyu，Wang Junxiang，et al.Mean shift target tracking with spatiogram corrected background-weighted histogram［J］.Control and Decision，2014，29(3):528-532.(in Chinese)

［5］ Yang Fan，Lu Huchuan，Yang M H.Robust superpixel tracking［J］.IEEE Transactions on Image Processing，2014，23(4):1639-1651.

［6］ Zhang Tianzhu，Ghanem Bernard，Liu Si，et al.Robust visual tracking via structured multi-task sparse learning［J］.International Journal of Computer Vision，2013，101(2):367-383.

［7］ Papoutsakis K E，Argyros A A.Integrating tracking with fine object segmentation［J］.Image and Vision Computing，2013，31:771-785.

［8］ Zhang Kaihua，Zhang Lei，Yang M H.Fast compressive tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，36(10):2002-2015.

［9］ Li P，Hastie T J，Church K W.Very sparse random projections［C］∥Proceedings of the 12th International Conference on Knowledge Discovery and Data Mining，［S.l.］:ACM，2006:287-296.

［10］ Strohmer T.Measure what should be measured:progress and challenges in compressive sensing［J］.IEEE Signal Processing Letters，2012，19(12):887-893.

［11］ Qaisar S，Bilal R M，Iqbal W，et al.Compressive sensing:from theory to applications，a survey［J］.Journal of Communications and Networks，2013，15(5):443-456.

［12］ Engelberg S.Compressive sensing［J］.IEEE Instrumentation ＆ Measurement Magazine，2012，15(1):42-46.

［13］ Donoho D L.Compressed sensing［J］.IEEE Transactions on Information Theory，2006，52(4):1289-1306.

［14］ Friedland S，Li Q，Schonfeld D.Compressive sensing of sparse tensors［J］.IEEE Transactions on Image Processing，2014，23(10):4438-4447.

［15］ 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(8):1619-1632.

［16］ Shaul O，Aharon B H，Dan L，et al.Locally orderless tracking［J］.International Journal of Computer Vision，2014.

［17］ Everingham M，Gool L，Williams C，et al.The Pascal visual object classes(VOC)challenge［J］.International Journal of Computer Vision，2010，88(2):303-338.

［18］ Kalal Z，Mikolajczyk K，Matas J.Tracking learning detection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34(7):1409-1422.