DSP實現(xiàn)基于改進壓縮跟蹤算法的目標實時跟蹤

閆鈞華，姜惠華，楊 勇，謝天夏

（南京航空航天大學 航天學院，江蘇 南京210016）

DSP實現(xiàn)基于改進壓縮跟蹤算法的目標實時跟蹤

閆鈞華，姜惠華，楊 勇，謝天夏

（南京航空航天大學 航天學院，江蘇 南京210016）

為解決目標外形、姿態(tài)變化以及被遮擋的難點，對壓縮跟蹤算法進行改進：以Kalman預測位置為中心，采用由粗到精的搜索策略，快速準確地找到具有最大分類分數(shù)的目標位置；根據(jù)目標在每一幀最大分類分數(shù)的變化規(guī)律進行粗判定，再利用目標和模板的相似度進行精判定以判斷遮擋的開始；利用Kalman預測器預測目標被遮擋時的位置，利用基于MCD距離的模板匹配檢出脫離遮擋后的目標。使用浮點轉(zhuǎn)定點等策略將算法在DSP上優(yōu)化實現(xiàn)。實驗結(jié)果表明：跟蹤效果穩(wěn)定，在目標外形、姿態(tài)緩慢變化以及被遮擋時能準確地跟蹤目標。對640×480像素的視頻，跟蹤框為64×64像素時，被遮擋目標跟蹤速度達到38.5毫秒/幀，滿足實時性要求。

目標實時跟蹤；遮擋；壓縮跟蹤；定點DSP

視頻目標實時跟蹤在視覺導航、安防監(jiān)控等領(lǐng)域應用廣泛，具有重要的研究價值。在實際的各種場景中，目標跟蹤存在著光照變化、目標外形尺度變化，運動模糊、遮擋等難點［1］?；谂袥Q模型的算法是當前跟蹤算法的研究熱點［2-5］。判決模型將跟蹤視為背景與目標的二分類問題，如多示例學習跟蹤MIL［3］，壓縮跟蹤CT［4］。壓縮跟蹤算法利用稀疏的隨機測量矩陣提取目標特征，基于樸素貝葉斯分類器對提取的樣本進行分類，具有計算量少和跟蹤效果魯棒的優(yōu)勢，但在目標發(fā)生外形、姿態(tài)、尺度變化以及被遮擋時會出現(xiàn)漂移?，F(xiàn)有的壓縮跟蹤算法的改進主要集中于特征的優(yōu)化選擇和引入多尺度特征［6-8］。為解決跟蹤目標外形、姿態(tài)變化以及被遮擋的問題，本文對壓縮跟蹤算法提出如下改進：以Kalman預測位置為中心，采用由粗到精的搜索策略以提高搜索效率，設置粗精判定條件以高效準確地判斷遮擋的開始。

以DSP為核心的嵌入式跟蹤系統(tǒng)具備結(jié)構(gòu)緊湊、功耗低、移動性強的優(yōu)勢。受到DSP資源的限制，浮點運算多、計算量大的目標跟蹤算法實現(xiàn)困難［9］。在DSP上應用成熟的算法以相關(guān)跟蹤、質(zhì)心跟蹤、MeanShift跟蹤和粒子濾波跟蹤為主［9-11］。文中算法基于定點DSP實現(xiàn)，采用各項優(yōu)化策略，以充分利用DSP的硬件資源和軟件流水技術(shù)。

1 壓縮跟蹤算法

壓縮跟蹤算法利用公式v=Φx將一個高維圖像空間特征向量變換到一個低維的圖像空間特征向量。其中x∈Rm是高維圖像空間的特征向量，Φ∈Rn×m（n<

其中，ρ=m%4（取余），利用（1）式對高維圖像空間特征向量進行投影，得到一個低維的圖像空間特征向量。稀疏隨機投影得到的每一個特征實際上表現(xiàn)為原圖像特征以φij為權(quán)值的加權(quán)和。

初始狀態(tài)下目標位置已知，選取正樣本（目標，y=1），負樣本（背景，y=0），對所有樣本計算其壓縮后的低維特征向量v=（v1，…，vn）T，構(gòu)建樸素貝葉斯分類器式（2）。樣本的低維特征向量的任意分量vi都近似看作正態(tài)分布，式（3）。其中：和分別為正樣本的均值與標準差，和分別為負樣本的均值與標準差。

跟蹤過程中，在以上一幀的跟蹤位置為中心，半徑為r的搜索域內(nèi)遍歷候選框，通過上述壓縮方法對每個候選框降維并得到低維的圖像空間特征向量，用樸素貝葉斯分類器進行分類，計算每個候選框的分類分數(shù)H（v），選取具有最大分數(shù)的候選框為當前幀的目標位置。之后選取正、負樣本，計算樣本的所有低維特征。利用式（4）來得到更新后的分類器參數(shù)和。 同理，求得分類器參數(shù)和。

式（4）中s為正樣本個數(shù)，λ（λ＞0）表示學習速率，λ越小表示更新速率越快，之前的目標特征遺忘越快。

2 基于改進壓縮跟蹤算法的目標實時跟蹤的DSP實現(xiàn)

2.1 改進的壓縮跟蹤算法

1）基于Kalman預測器的由粗到精的搜索策略

利用Kalman預測器預測下一幀圖像中目標位置，縮小整個圖像上目標跟蹤的搜索區(qū)域，減少計算量且提高準確度。在目標被遮擋時，輸出Kalman預測跟蹤框，估計目標運動軌跡。

xk為目標在k時刻的狀態(tài)變量，由目標中心位置在圖像水平與垂直方向上的位置和速度構(gòu)成，即［px，vx，py，vy］T。yk為目標在k時刻的觀測狀態(tài)，由目標中心位置在圖像水平與垂直方向上的觀測位置構(gòu)成，即［px，py］T。k時刻的Kalman狀態(tài)方程和觀測方程分別為：

式中，Ak-1，為狀態(tài)轉(zhuǎn)移矩陣，Ck為觀測矩陣，wk-1是k-1時刻狀態(tài)的隨機干擾，vk是k時刻的觀測噪聲。文中均采用互不相關(guān)零均值標準正態(tài)白噪聲序列，Qk與Rk分別為wk與vk的協(xié)方差矩陣，分別如下式所示：

式（6）中Δt表示連續(xù)兩幀圖像間的時間間隔。根據(jù)Kalman預測公式（7）可以預測下一幀目標狀態(tài)?（k+1|k）。

在當前幀，以上一幀得到的Kalman預測位置為中心，采用由粗到精的搜索策略尋找具有最大分類分數(shù)的目標位置，從而提高搜索效率。在以R1像素長度為半徑的搜索域內(nèi)，以Δ1像素長度為采樣步長采樣并計算其分類分數(shù)，確定其中最大分類分數(shù)的樣本位置作為粗跟蹤位置；同理，再以為中心，R2像素長度（R1＞R2）為搜索半徑，Δ2（Δ1＞Δ2）像素長度為采樣步長進行相同過程的計算獲取跟蹤位置P'k；同理，再以為中心，R3像素長度（R2＞R3）為搜索半徑，Δ3（Δ2＞Δ3）像素長度為采樣步長進行相同過程的計算得出當前幀的最終精跟蹤位置Pk。通過這種搜索策略需要計算的樣本數(shù)約為。與密集遍歷法相比，該策略可以在擴大了目標搜索范圍的同時計算更少的樣本，且跟蹤精度基本保持不變。

2）被遮擋目標的跟蹤

壓縮跟蹤算法對被輕微遮擋的目標和形變目標的跟蹤具有魯棒性，但是無法對被嚴重遮擋的目標進行持續(xù)跟蹤。如圖1所示，當目標開始進入被遮擋狀態(tài)，分類器最大分類分數(shù)會有一個明顯的逐幀減小過程。當目標被嚴重遮擋時，由最大分類分數(shù)定位的目標位置是錯誤的，這將導致分類器不斷學習到負樣本，遺忘目標的正樣本，導致不可恢復的跟蹤失敗。

圖1 Jogging序列中目標被遮擋狀態(tài)下壓縮跟蹤效果和最大分類分數(shù)變化示意圖

如何有效地判斷遮擋的開始、遮擋的結(jié)束及相應的處理方法，是被遮擋目標跟蹤的關(guān)鍵。建立目標的模板圖像T，按式（8）更新。

其中Tk為當前幀的模板圖像，S為當前幀跟蹤得到的目標圖像，Tk+1為下一幀的模板圖像。α為模板更新系數(shù)，本文取α=0.9。根據(jù)目標在被遮擋過程中最大分類分數(shù)的變化規(guī)律，進行遮擋粗判定。

設定一個閾值Hocc，當連續(xù)三幀的最大分類分數(shù)持續(xù)減小，且當前幀與其相隔的上一幀的最大分類分數(shù)減小量大于Hocc，認為目標可能開始被遮擋，圖3中虛線框所標位置為目標可能開始被遮擋的時刻。然后進行精判定，計算當前幀壓縮跟蹤得到的目標圖像S與當前幀的模板圖像T的MCD［12］距離D。

目標和模板圖像的大小為M×N像素。定義目標圖像與模板圖像的相似度為D/（MN），當相似度小于閾值η，判定目標外觀變化較大，已經(jīng)被遮擋。當判定目標已經(jīng)被遮擋后，停止更新分類器和模板，采用Kalman預測器的預測位置作為當前幀的目標跟蹤結(jié)果。利用模板圖像在當前跟蹤位置的鄰域內(nèi)進行基于MCD距離的相關(guān)匹配［6］檢測目標。當目標圖像與模板圖像相似度大于閾值η，匹配成功，判定目標已結(jié)束被遮擋狀態(tài)。

3）改進的壓縮跟蹤算法流程與仿真

改進的算法不需要每一幀都計算跟蹤結(jié)果與模板圖像的相似度，大大減少判斷遮擋帶來的計算量。目標被遮擋后，停止更新分類器和模板，利用基于MCD距離的匹配算法檢測目標是否結(jié)束被遮擋。改進的壓縮跟蹤算法流程如圖2所示。

選取MIL跟蹤算法，壓縮跟蹤算法和本文算法對具有典型遮擋過程的Jogging序列進行基于matlab平臺的目標跟蹤仿真比較，跟蹤誤差曲線如圖3所示。在Jogging序列中的目標未發(fā)生遮擋時，文中算法的跟蹤誤差整體小于其他兩種算法。在目標發(fā)生遮擋后，MIL算法和壓縮跟蹤算法持續(xù)學習到遮擋物的特征，從而導致跟蹤失敗。而文中算法檢測出了遮擋的發(fā)生，停止更新分類器和模板，利用模板匹配檢測出脫離遮擋的目標，實現(xiàn)了持續(xù)的跟蹤。

圖2 改進的壓縮跟蹤算法流程圖

圖3 Jogging序列的跟蹤誤差曲線圖

2.2 目標實時跟蹤的DSP實現(xiàn)

為了充分利用DSP的軟硬件資源以提高算法的運行效率，使用如下優(yōu)化策略。

1）浮點運算轉(zhuǎn)定點運算

由公式（2）（3）（4），算法中存在除法、取對數(shù)以及開方運算等浮點數(shù)學運算。在定點DSP上直接使用ANSIC中的運算語句進行浮點數(shù)運算，會消耗大量的時鐘周期［13］。為了在定點DSP上高效地進行浮點數(shù)運算，采用TI公司的IQmath庫，其實質(zhì)是將浮點數(shù)轉(zhuǎn)化成Q格式定點數(shù)計算。為了擴大用Q格式數(shù)所能表示浮點數(shù)的范圍，不可避免地需要折損精度。由于圖像積分特征的均值與方差數(shù)量級變化較大，如果采用高精度的Q值表示方法，容易導致數(shù)據(jù)溢出。綜合考慮數(shù)據(jù)范圍和精度，程序中選用全局Q值為8。在計算分類分數(shù)的子程序中，對結(jié)果的精度要求更高，因此采用局部Q值為10。采用IQmath庫中優(yōu)化過的_IQdiv（）、_IQlog（）以及_IQsqrt（）函數(shù)代替ANSIC中相應的數(shù)學函數(shù)以提高代碼運算速度。

2）內(nèi)存管理的優(yōu)化

文中采用的DSP平臺DM6437的片上內(nèi)存由32 kB的一級程序緩存（L1P）、80 kB一級數(shù)據(jù)緩存（L1D）和128 kB的二級存儲器/緩存（L2 SRAM/cache）組成。程序代碼和數(shù)據(jù)必須經(jīng)過逐級搬移而被CPU訪問。L1P、L1D和L2的合理配置可以有效提升系統(tǒng)性能［14］。文中將L1P全部設為cache，將L1D設為64 kB的cache和16 kB的SRAM，將L2設為64 kB的RAM和64 kB的cache。為了便于內(nèi)存管理，將采樣得到的樣本集位置和特征，圖像積分圖等大數(shù)組定義為全局或靜態(tài)變量；將其中使用頻率最高的數(shù)組通過自定義段的方式存放在片上內(nèi)存的L1D SRAM中，其余大數(shù)組則定義在外部內(nèi)存DDR2中。使用16位short型變量代替32位int型變量定義樣本的位置坐標和尺寸，減少近一半的存儲空間。

3）采用VLIB函數(shù)

VLIB是TI提供的視頻算法庫，經(jīng)過深度優(yōu)化，運算效率很高［15］。計算樣本的壓縮后的低維特征，需要首先對整幅圖像做積分圖運算。使用TI的VLIB庫中的高效積分圖函數(shù)接口實現(xiàn)圖像積分圖運算。使用VLIB函數(shù)Kalman模塊函數(shù)實現(xiàn)Kalman預測的計算。

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

實驗基于DM6437S60 DSP開發(fā)平臺，處理核心是一款C64x+內(nèi)核的主頻達594 MHz的32位定點DSP。

圖4中運動目標的表觀外形姿態(tài)緩慢變化。由于算法蘊含了在線學習的思想，不斷學習到變化后的目標特征，對于目標外形和姿態(tài)的緩慢變化具有較高的魯棒性，始終能對目標準確地跟蹤。

圖5為目標被遮擋下的本文算法與原算法的跟蹤效果對比。黑色框和白色框分別為原算法和文中算法的跟蹤效果。文中算法在第114幀時判定出目標開始被遮擋，利用Kalman預測結(jié)果作為被遮擋時的跟蹤結(jié)果，在第141幀時檢測出目標開始脫離遮擋，并且在結(jié)束被遮擋后仍能繼續(xù)對目標進行持續(xù)的跟蹤。而原算法在目標開始被遮擋后，學習錯誤的樣本，跟蹤框持續(xù)固定在遮擋物上，導致跟蹤失敗。

利用DSP的片上定時器對程序運行時間進行統(tǒng)計，結(jié)果如表1所示。目標在被遮擋階段時加入了模板匹配檢測目標，程序處理時間會相應增加。在視頻圖像尺寸為640×480像素，跟蹤框尺寸為64×64像素時，在目標被遮擋下平均每幀處理時間為38.5毫秒，實現(xiàn)了對25幀/秒的視頻的實時處理。

圖4 改進的壓縮跟蹤算法對形變魔方的跟蹤效果（跟蹤框80×80像素，分別為第5，98，124，225，309幀）

表1 優(yōu)化后的改進的壓縮跟蹤算法程序在DSP上的運行時間

4 結(jié)束語

文中在定點DSP平臺上優(yōu)化實現(xiàn)了基于改進壓縮跟蹤算法的目標實時跟蹤，實驗結(jié)果表明：目標跟蹤效果穩(wěn)定，在目標外形、姿態(tài)緩慢變化以及被遮擋時能準確的跟蹤目標，滿足實時性要求。

［1］Wu Y，Lim J，Yang M H.Online object tracking:A benchmark［C］//Proceedings of the IEEE conference on computer vision and pattern recognition.2013:2411-2418.

［2］Grabner H，Grabner M，Bischof H.Real-Time tracking via On-line boosting［C］//BMVC.2006，1（5）:6.

［3］Babenko B，Yang M H，Belongie S.Robust object tracking with onlinemultiple instance learning［J］.IEEE Transa-ctions on Pattern Analysis&Machine Intelligence，2011，33（8）:1619-1632.

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

［5］Zhang K，Zhang L，Yang M H.Real-time compressive tracking［C］//Computer Vision╞ECCV 2012.Springer Berlin Heidelberg，2012:864-877.

［6］石武禎，寧紀鋒，顏永豐.壓縮感知跟蹤中的特征選擇與目標模型更新［J］.中國圖象圖形學報，2014，19（006）:932-939.

［7］王松林，項欣光.基于壓縮感知的多特征加權(quán)目標跟蹤算法［J］.計算機應用研究，2014，31（3）:929-932.

［8］毛征，袁建建，吳珍榮，等.基于在線特征選擇的實時壓縮跟蹤［J］.光學精密工程，2014，22（3）:730-736.

［9］高文，朱明，劉劍，等.基于DSP+FPGA框架的實時目標跟蹤系統(tǒng)設計［J］.液晶與顯示，2014，29（4）:613-616.

［10］孫航，韓紅霞，郭勁，等.基于均值偏移快速算法的紅外目標跟蹤［J］.儀器儀表學報，2012，33（5）:1122-1127.

［11］夏軒，劉華平，許偉明，等.基于DSP的主動視覺系統(tǒng)［J］.機器人，2012，34（3）:354-362.

［12］任仙怡，廖云濤.一種新的相關(guān)跟蹤方法研究［J］.中國圖象圖形學報:A輯，2002，7（6）:553-557.

［13］黃丙勝，秦紅磊，叢麗.基于定點DSP的相對導航UKF算法優(yōu)化研究［J］.計算機工程與設計，2014（7）:2582-2586.

［14］劉項洋，許勇.快速DCT修剪在DSP上的內(nèi)存訪問優(yōu)化方法［J］.電子學報，2016，44（1）:227-232.

［15］李培平，楊進華，許新科.基于DSP的視頻信號邊緣提取算法實現(xiàn) ［J］.長春理工大學學報:自然科學版，2010，33（4）:101-103.

Realization on DSP-based real-time target tracking of im proved com pressive tracking algorithm

YAN Jun-hua，JIANG Hui-hua，YANG Yong，XIE Tian-xia
（College of Astronautics，Nanjing University of Aeronautics&Astronautics，Nanjing 210016，China）

To solve the problems of shape change，pose variation and occlusion in target tracking，Compressive Tracking algorithm is improved bywaysbelow：taking the Kalman predictor'soutputas the center ofsearch area，a coarse-to-fine search strategy is used to quickly and accurately find the target position with the maximum classification score.We first roughly determinewhether occlusion happens according to the regular pattern of variation of themaximum classification score ofeach frame.Then we determine whether occlusion happens exactly by computing the similarity between object and template.The Kalman predictoroffers the predicted location of the objectwhen occlusion happens.The judgmentof the end ofocclusion and re-detection of target is completed by templatematching based on the MCDmethod.Real-time target tracking is realized based on the improved CT algorithm in DSP with optimization tactics such as changing float-point computation to fixed point computation.Experiments show that the result of target tracking is stable.The target can be tracked accurately when slow shape change，slow pose variation and occlusion happen.When the input video's size is 640×480 pixels and the tracking rectangle'size is64×64 pixel，theoccluded target is tracked with the speed up to 38.5msper frame，whichmeets the real-time requirements.

real-time target tracking；occlusion；compressive tracking；fixed-point DSP

TN919.82

A

1674－6236（2016）20-0009-04

2016-03-09 稿件編號：201603121

國家自然科學基金資助（61471194）；航空電子系統(tǒng)綜合技術(shù)重點實驗室和航空科學基金聯(lián)合資助（20155552050）；中國航天科技集團公司航天科技創(chuàng)新基金資助

閆鈞華（1972—），女，陜西興平人，工學博士，副教授。研究方向：多源信息融合、目標檢測跟蹤與識別。