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

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

　　1. 引言

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

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

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

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

　　2.2 模板匹配算法

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

　　2.3 SAD 模板匹配中的地址對(duì)齊問(wèn)題

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

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

　　3. SAD 優(yōu)化設(shè)計(jì)方案

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

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

　　4. 結(jié)論

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