基于DSP和模板匹配算法的實時圖像跟蹤處理系統(tǒng)的優(yōu)化設計

　　本文詳細介紹了基于高性能TigerSHARC DSP 處理模塊和模板匹配算法（templatematching）的實時圖像跟蹤處理系統(tǒng)的優(yōu)化設計方法；深入分析了SAD 操作中涉及到的地址對齊問題，提出了一種優(yōu)化的設計方案，將并處理效率提高20 倍，并在實際的實時圖像跟蹤系統(tǒng)中得到應用。

　　1. 引言

　　隨著電子技術的不斷進步，目前越來越多的實用數(shù)字圖像跟蹤系統(tǒng)采用高性能DSPCOST 模塊實現(xiàn)快速構(gòu)建實時處理原型［1］。在眾多型號的DSP 處理芯片中，TigerSHARC 系列DSP 處理器具有大的定點、浮點處理能力，成為目前世界上最快的浮點DSP 處理器，由于其具有強大的可擴展能力，TigerSHARC DSP 處理器也一直引領可擴展并行多DSP 實時處理系統(tǒng)的發(fā)展方向，被稱為“多DSP 系統(tǒng)實現(xiàn)的標準”［2］。同時，TigerSHARC DSP 處理器對字節(jié)數(shù)據(jù)的處理提供了良好的支持，例如，支持基于字節(jié)的SAD（SUM-ABS-Difference）操作，非常適合構(gòu)建實時圖像處理系統(tǒng)。但由于嚴重的地址對齊問題，需要對系統(tǒng)進行優(yōu)化設計，以實現(xiàn)在滿足嚴格的實時性要求的條件下，限制系統(tǒng)規(guī)模，降低系統(tǒng)成本。

　　2. 實用實時圖像跟蹤處理系統(tǒng)

　　2.1 實時圖像跟蹤處理系統(tǒng)組成

　　首先給出實用實時成像處理系統(tǒng)的結(jié)構(gòu)組成框圖，如圖1 所示，系統(tǒng)包括PMC 視頻采集模塊，TigerSHARC DSP 處理模塊（內(nèi)部集成4 片TigerSHARC DSP 處理器），cPCI 工控機主板，控制手柄和VGA 顯示器等。視頻采集板的輸入為PAL 制式黑白圖像信號，輸出768×288×8-bit 的數(shù)字圖像數(shù)據(jù)并通過TigerSHARC DSP 專用的LINK 接口以每場20 毫秒的間隔送至TigerSHARC DSP 處理模塊進行模板匹配（template matching）檢測算法。之后， DSP 處理模塊在原始圖像上疊加目標信息，通過cPCI 工控機主板傳送到VGA 顯示器進行顯示。國家 863 計劃：基于空天平臺的實時數(shù)據(jù)處理技術（2006AA701415）

　　2.2 模板匹配算法

　　模板匹配算法是在一幅圖像場景中檢測目標的基本算法，將已知的目標圖像模板在一幅未知圖像場景中滑動，并與對應的未知場景圖像塊進行比較，如果結(jié)果足夠接近，就將該圖像塊標識為目標。一般采用目標模板與未知場景圖像塊之間的各像素值的差異絕對值之和的形式來度量其接近程度。如下式所示， 其中各像素之間的運算操作定義為SAD（SUM-ABS-Difference），整個過程如圖2 所示。某目標模板T，為M×N 維的像素陣列，以像素為單位在未知圖像場景中沿水平方向和垂直方向依次滑動。每滑動一步，T 即與未知圖像場景中對應的待檢測像素矩陣S 進行如式1 所示的SAD 操作，并將所得結(jié)果D（i，j）作為接近程度的度量（Difference measure）存入度量矩陣D，其中，S 是與T 同樣大小的像素矩陣。

　　2.3 SAD 模板匹配中的地址對齊問題

　　TigerSHARC 處理器的ALU 提供了對SAD 操作的指令支持，如圖3a 所示。在一個時鐘周期（3.3ns/300MHz/ADSP-TS101S）內(nèi)，單個ALU 可以通過指令PR+=ABS（BRmd-BRnd）完成模板T 中8 個像素的SAD 操作，其中PR 為處理器ALU 中的64-bit 累加器，用于存儲SAD 操作中圖像字節(jié)數(shù)據(jù)的累加結(jié)果。BRmd 和BRnd 均為32-bit×2 的寄存器對，分別讀取T 和S 中的8 個對應像素字節(jié)數(shù)據(jù)。因為TigerSHARC DSP 處理器為雙核結(jié)構(gòu)，具有兩個ALU，所以，其單周期最多可以完成模板T 中16 個像素的SAD 操作。顯而易見，使TigerSHARC DSP 處理器的指令流水線中不間斷地執(zhí)行SAD 指令是獲得其峰值處理能力的必要條件，而其ALU 從內(nèi)存取操作數(shù)時產(chǎn)生的地址對齊問題則是制約處理效率提升的主要瓶頸。

　　如圖 3b 所示，SAD 指令執(zhí)行時前，兩個ALU 分別需要從內(nèi)存讀8 個字節(jié)目標模板數(shù)據(jù)和8 個字節(jié)待檢測場景圖像數(shù)據(jù)至內(nèi)部寄存器，且要求該數(shù)據(jù)存放首地址須為64-bit 對齊，否則會導致內(nèi)部總線訪問異常。T 與S 雖然是同樣大小的像素矩陣，但其大小一般遠大于16 個字節(jié)，在T 內(nèi)地數(shù)據(jù)地址是連續(xù)的，而S 作為從場景圖像中切割出的一部分，其地址通常不連續(xù)。同時，隨著T 在場景圖像中不斷以字節(jié)為單位逐行滑動，地址對齊問題所造成的效率損失會更加突出，勢必需要對非對齊的數(shù)據(jù)地址進行計算，零散字節(jié)數(shù)據(jù)的收集合并（bytes adjust and merging），以及非常復雜的多重循環(huán)控制。以單片TigerSHARC DSP 處理器對處理效率進行評估，經(jīng)編譯器優(yōu)化過后的ANSI C 程序，可以實現(xiàn)在100ms 左右完成一場背景圖像匹配任務。以此計算，至少需要將背景數(shù)據(jù)分為5 個部分，并分配至5 個TigerSHARC DSP 處理器中，才可以勉強達到20ms 實時性要求的下限，這樣，系統(tǒng)內(nèi)就不得不添加一個TigerSHARC DSP 處理模塊，這對于功耗、成本、重量、體積等指標都是不可接受的。因此，直接實現(xiàn)如式1 和圖3 所表示的計算過程是不可行的，必須考慮優(yōu)化的計算方案。

　　3. SAD 優(yōu)化設計方案

　　重新對圖2 中描述的SAD 過程進行分析，發(fā)現(xiàn)T 中的每一個字節(jié)像素在背景圖像中需要滑動的次數(shù)是一樣的，由于其每一次移動的計算結(jié)果都存入D 的對應位置，因此滑動次數(shù)與D 中的元素個數(shù)也是一樣的，且為一一對應。換句話說，D 中的某一個元素涉及到T中的全部字節(jié)像素的某一次滑動。則根據(jù)加法結(jié)合律，可由式1 得出優(yōu)化后的SAD 處理過程如下式所示。

　　猶如螞蟻搬家，可以先使T 中16 個字節(jié)像素數(shù)據(jù)在背景圖像上滑動，進行應有的SAD4操作，并將每一次滑動得到的結(jié)果存入D 中的對應位置，這時D 的累加和為中間結(jié)果；再使T 中的之后的16 個字節(jié)像素數(shù)據(jù)在背景圖像上完成滑動SAD 操作，并將此次的結(jié)果與前次保存在D 中的中間結(jié)果相加，再存入相應位置，以此類推，直至T 中的全部字節(jié)像素數(shù)據(jù)完成滑動，并更新D 中累加結(jié)果。根據(jù)上式可得優(yōu)化實現(xiàn)方案如圖6 所示，優(yōu)化方案與直接實現(xiàn)方案相比，并沒有減少SAD 操作的次數(shù)，但由于調(diào)整了算法執(zhí)行結(jié)構(gòu)，和運算次序，大大提升了訪問內(nèi)存數(shù)據(jù)的效率，簡化了實現(xiàn)流程，處理器指令流水線得到了較好的組織。對前述同樣的處理任務進行評估，優(yōu)化實現(xiàn)方案可以使用1 個TigerSHARC DSP 處理器在5ms 內(nèi)完成。因為在優(yōu)化實現(xiàn)方案中，T 內(nèi)的數(shù)據(jù)具有良好的可分性，采用2 個TigerSHARC DSP 處理器在2.6ms 內(nèi)便可完成。采用優(yōu)化實現(xiàn)方案不但可以很好的提升系統(tǒng)的實時性能，而且還可以減少一個TigerSHARC DSP 處理模塊，大大降低了系統(tǒng)的復雜度，體積，功耗和成本。同時還可以提供約15ms 的時間供壓縮，傳輸?shù)绕渌幚砣蝿辗峙洹?/p>

　　4. 結(jié)論

　　本文詳述了一種實用的實時數(shù)字圖像跟蹤系統(tǒng)的優(yōu)化設計方法，指出了地址對齊問題在處理系統(tǒng)優(yōu)化設計中的重要性，著重針對模板匹配處理算法進行了創(chuàng)新的優(yōu)化設計實現(xiàn)，滿足了系統(tǒng)整體對實時性、功耗、體積、成本等多方面的需求。該系統(tǒng)實現(xiàn)在實際工程中收到了良好的效果，實際系統(tǒng)組成如下圖所示。