視頻跟蹤算法在Davinci SOC上的實現(xiàn)與優(yōu)化

引言

目標跟蹤作為計算機視覺的一個極具挑戰(zhàn)性的研究任務，已被廣泛的應用在人機交互、智能監(jiān)控、醫(yī)學圖像處理等領域中。目標跟蹤的本質(zhì)是在圖像序列中識別出目標的同時對其進行精確定位。為了克服噪聲、遮擋、背景的改變等對目標識別帶來的困難，出現(xiàn)了很多的跟蹤算法。

因為目標跟蹤算法需要處理的數(shù)據(jù)量大、運算復雜，需要性能強大的處理器才能實時處理。我們選用TI推出的最新產(chǎn)品TMS320DM6446實現(xiàn)算法。TMS320DM6446是一款高度集成的片上系統(tǒng)，集成了可以運行頻率高達594MHz的C64x+ DSP核和297MHz的ARM926處理器核。另外它還集成了數(shù)字視頻所需的許多外部組件，如視頻加速器，網(wǎng)絡外設及高速外部存儲接口。本設計充分利用DM6446的強大運算能力，在DSP內(nèi)核上實時運行目標跟蹤算法。 設計還在ARM處理器上執(zhí)行多線程應用程序，負責視頻采集，顯示，網(wǎng)絡通信，外圍器件控制等工作。

算法介紹

本系統(tǒng)實現(xiàn)的視頻跟蹤算法可參考文獻[1]-[5]，整個算法分為基本算法和改進算法兩部分。本算法是一種基于模板匹配技術的跟蹤算法，即在手工選定或自動選定了待跟蹤目標后，提取目標的外觀信息作為模板，在后續(xù)的視頻序列中，將候選圖像區(qū)域與目標模板進行匹配，將最相似的圖像區(qū)域作為運動目標當前的位置。在本文中，采用結構相似度，即“歸一化互相關系數(shù)”作為候選區(qū)域與目標模板相似程度的度量標準，其計算公式如下所示：


上式中，f(m,n)和g(m,n)分別為目標模板和候選區(qū)域的灰度值矩陣，尺寸為MxN。uf和ug分別為目標模板和候選區(qū)域的灰度平均值，然后再求出f(m,n)和g(m,n)的協(xié)方差、f(m,n)的方差、g(m,n)的方差后，求出歸一化互相關系數(shù)。式(1)通過從灰度值矩陣中減去灰度均值，有效地消除了光照給跟蹤結果帶來的影響。而對于匹配圖像區(qū)域的搜索，為了達到減少匹配次數(shù)從而降低計算量的目的，我們借鑒了視頻壓縮領域中的三步搜索法(Three Step Search, TSS) 作為最匹配點的搜索算法[2]。

為了增加模板匹配視頻目標跟蹤算法的魯棒性，我們在基本算法的基礎上實現(xiàn)了改進算法的部分。改進算法具有自適應遮擋處理與模板漂移抑制的能力，能夠很好地解決前面提到模板匹配的視頻目標跟蹤算法需要解決的難題。具體來說，主要有如下四點改進：(1) 抑制漂移的帶掩蔽卡爾曼外觀濾波算法(Drift-Inhibitive Masked Kalman Appearance Filter, DIMKAF ) [1][3][4] ；(2) 內(nèi)容自適應漸進式遮擋分析算法(Content-Adaptive Progressive Occlusion Analysis, CAPOA)[1][5]；(3) 可變掩蔽模板匹配算法(Variant-Mask Template Matching, VMTM)[1][5]；(4) 局部最優(yōu)匹配鑒定算法(Local Best Match Authentication, LBMA)[1]。 改進后整個算法的流程圖如下所示：

圖 1 跟蹤算法主流程圖

算法在Davinci SOC上的實現(xiàn)

DSP平臺的選擇

DM6446采用ARM與DSP 雙核結構，其中ARM子系統(tǒng)搭載297 MHz主頻的ARM926 核，DSP部分則采用594 MHz的C64x+DSP核，外圍存儲均支持256 MB DDR2 RAM和各類存儲卡，另外使用了VPSS 子系統(tǒng)豐富的視頻前后處理功能，且都配備了完善的外設接口。目標跟蹤算法需要做大量運算，DM6446 DSP核強大的運算處理能力保證了算法的實時處理。同時DM6446的ARM核可以進行系統(tǒng)管理，數(shù)據(jù)讀寫，網(wǎng)絡傳輸?shù)忍幚怼?

我們使用Spectrum Digital公司的DVEVM平臺進行算法仿真、原型制作和軟件優(yōu)化。DVEVM?還可實現(xiàn)視頻輸入／輸出連接、網(wǎng)絡接口、存儲器接口以及標準的子卡連接等。

系統(tǒng)軟件框架

整個系統(tǒng)的軟件框架如圖2如示。DM6446的ARM核運行基于Linux操作系統(tǒng)的應用程序，所用的外圍設備都由ARM負責控制。ARM端的HTTP服務器通過Linux網(wǎng)絡協(xié)議棧來處理HTTP請求，并發(fā)送壓縮視頻數(shù)據(jù)。視頻跟蹤的應用程序由五個POSIX線程組成，分別是視頻捕捉線程，視頻跟蹤線程，視頻壓縮線程，顯示線程，系統(tǒng)控制線程。視頻捕捉線程通過V4L2接口設備驅(qū)動從攝像頭讀取原始視頻數(shù)據(jù)。視頻跟蹤線程把視頻數(shù)據(jù)送到ARM和DSP的共享緩沖內(nèi)存，并通知DSP執(zhí)行跟蹤算法。壓縮線程負責控制DSP側(cè)的壓縮算法并從共享內(nèi)存中讀取壓縮數(shù)據(jù)。視頻顯示線程從視頻緩存中讀取視頻數(shù)據(jù)幀，并疊加目標跟蹤框，最后通過Frame Buffer設備驅(qū)動輸出顯示。系統(tǒng)控制線程負責響應遙控器和鼠標并執(zhí)行相應操作。

DM6446的DSP核上運行DSP/BIOS實時操作系統(tǒng)和目標檢測，跟蹤算法，視頻壓縮算法。所有的算法的接口都符合TI xDAIS標準，由Codec Engine調(diào)用。除了算法，DSP核上還集成了管理內(nèi)存和DMA的Framework Component。

ARM核和DSP核的通信由TI提供的Codec Engine軟件框架負責。Codec Engine是介于應用程序和具體算法之間的軟件模塊，其中的VISA API通過stub和skeleton訪問Engine SPI最終調(diào)用算法。ARM和DSP的所用共享緩沖內(nèi)存都是通過CMEM模塊在DDR中分配的，緩沖內(nèi)存地址連續(xù)且與DSP核Cache對齊。

圖 2 軟件結構圖

跟蹤算法在DSP上的優(yōu)化

為了充分發(fā)揮出Davinci SOC強大的視頻處理能力，滿足實時跟蹤的需要，我們通過算法優(yōu)化和編程優(yōu)化相結合的方法對Codec程序進行了大量的優(yōu)化。

算法優(yōu)化

算法優(yōu)化是指在不降低算法性能的情況下，采用等效算法來降低計算量，我們的工作主要集中在“歸一化互相關系數(shù)”的計算例程的簡化上。根據(jù)均值和方差的性質(zhì)，我們可以將(1)式化簡為：

上式與式(1)比較，減少了大量的加減法計算，而且將方差和協(xié)方差的計算轉(zhuǎn)化為大量的乘加運算，這為我們后面的編程優(yōu)化也提供了極大的便利。例如M=64, N=64時，加法次數(shù)從36864減少到12288。

編程優(yōu)化

編程優(yōu)化是在計算量不變的情況下，根據(jù)Davinci處理器DSP核心的特點，通過優(yōu)化存儲器的存取效率和提高程序的并行化程度來縮短程序運行所需要的指令周期數(shù)，以使程序運行得更快。我們的編程優(yōu)化工作主要包含使用dsplib、使用線性匯編、使用內(nèi)聯(lián)函數(shù)以及循環(huán)展開等五個方面，下面將一一加以介紹。

* dsplib的使用

在優(yōu)化過程中，我們還采用了CCS中提供的庫函數(shù)來對代碼進行優(yōu)化。CCS中針對c64x+ DSP提供了高度優(yōu)化的dsplib庫函數(shù)供用戶使用，這些庫函數(shù)提供了數(shù)字信號處理中常見的處理例程，而且由匯編語言寫成，具有極高效的代碼效率。特別是用于計算向量內(nèi)積的DSP_dotprod和DSP_vecsumsq函數(shù)正好滿足了我們的計算需求。在計算尺寸為32x32的“歸一化互相關系數(shù)”時，優(yōu)化后計算部分只需要271個DSP時鐘周期，而計算和部分只需要267個DSP時鐘周期，這大大提高了程序運行的速度。

* 線性匯編

對于uf和ug的計算，如果使用for循環(huán)實現(xiàn)，將會大大拖累整個“歸一化互相關系數(shù)”計算例程的執(zhí)行效率。我們用手工編寫線性匯編代碼的方式實現(xiàn)了dspsum函數(shù)，利用C64x + DSP中的8個并行計算單元，在每個DSP時鐘周期內(nèi)同時進行4個16位加16位的加法操作，對于尺寸為32x32的求和計算而言，該函數(shù)只需要258個DSP時鐘周期。

* 內(nèi)聯(lián)函數(shù)的使用

C64x+編譯器提供的內(nèi)聯(lián)函數(shù)可快速優(yōu)化C代碼。內(nèi)聯(lián)函數(shù)是直接映射為內(nèi)聯(lián)的C64x+指令的特殊函數(shù)，內(nèi)聯(lián)函數(shù)用前下滑線(_)來表示，使用時同調(diào)用普通函數(shù)一樣使用它。我們在優(yōu)化過程中，使用了許多內(nèi)聯(lián)函數(shù)，如_round()等，大大提高了代碼的執(zhí)行效率。

* 循環(huán)展開

由于for技術循環(huán)需要打斷C64x+ DSP內(nèi)部的軟件流水線，而頻繁的for循環(huán)會大大降低DSP的處理效率，所以我們在優(yōu)化過程中，將部分for循環(huán)進行了展開，以代碼增加為代價提高了代碼的執(zhí)行效率。通過上述方法，可將代碼的處理效率提高3-5倍。

測試結果

為了獲得視頻跟蹤算法Codec運行所需要的DSP時鐘周期數(shù)，進而估計出優(yōu)化后的算法代碼是否已經(jīng)滿足實時跟蹤的需要，我們使用CCStudio v3.3對同一測試序列，同一起始目標位置，不同大小模板的情況進行了離線仿真。

表 1 視頻跟蹤算法優(yōu)化結果


表 2 DSP負載測試


結論

我們在基于雙核DM6446的系統(tǒng)平臺上，利用改進后的跟蹤算法實現(xiàn)了智能目標跟蹤系統(tǒng)。DM6446 ARM核上的Linux操作系統(tǒng)上的多線程程序負責視頻采集、視頻顯示、算法控制、外圍設備處理等任務。通過在TI Codec Engine軟件架構下擴展目標跟蹤算法的接口，我們成功在DM6446的DSP核上運行了跟蹤算法。經(jīng)過算法優(yōu)化和編程優(yōu)化，系統(tǒng)可以對采集輸入的25fps，720×480分辨率視頻中的128×128大小的目標進行實時跟蹤。實驗結果表明，該算法可以成功跟蹤目標，并具有較強的魯棒性。該技術將會在智能視頻監(jiān)控、智能用戶接口、基于對象的視頻壓縮、巡航導彈末端制導和輔助駕駛等領域有廣泛應用前景。

參考文獻：

1.Jiyan Pan, Bo Hu, and Jian Q. Zhang, "Robust and Accurate Object Tracking under Various Types of Occlusions," to appear in IEEE Transactions on Circuits and Systems for Video Technology (CSVT).
2.Michael H. Fischer, and Jiyan Pan, "A Novel Visual Tracking Algorithm based on Adaptive Three-Step Search, Hybrid Correlation, and Adaptive Template Renewal," Stanford Undergraduate Research Journal, vol. 5, pp. 54-60, spring 2006.
3.Jiyan Pan, Bo Hu, and Jian Q. Zhang, "Drift-Inhibitive Object Tracking Algorithm," submitted to Chinese Journal of Electronics (in Chinese).
4.Jiyan Pan, and Bo Hu, "Robust Object Tracking against Template Drift," to appear in Proc. IEEE Int. Conf. on Image Processing, San Antonio, Texas, September 2007.
5.Jiyan Pan, and Bo Hu, "Robust Occlusion Handling in Object Tracking," Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 1-8, Minneapolis, Minnesota, June 2007.
6.SPRU187L: TMS320C6000 Optimizing Compiler User’s Guide
7.SPRU198G: TMS320C6000 Programmer’s Guide
8.SPRU862A: TMS320C64x+ DSP Cache User‘s Guide
9.SPRUED6B: Codec Engine Algorithm Creator User’s Guide
10.SPRUE67: Codec Engine Application Developer’s Guide
11.SPRUED5: Codec Engine Server Integrator‘s Guide
12.SPRUEC8: xDAIS-DM (Digital Media) User Guide