基于DSP和模板匹配算法的實時圖像跟蹤處理系統的優化設計

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

　　1. 引言

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

　　2. 實用實時圖像跟蹤處理系統

　　2.1 實時圖像跟蹤處理系統組成

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

　　2.2 模板匹配算法

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

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

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

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

　　3. SAD 優化設計方案

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

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