基于多核DSP的圖像實(shí)時相關(guān)匹配研究*

宋 丹

(中國西南電子技術(shù)研究所，四川 成都 610036)

基于多核DSP的圖像實(shí)時相關(guān)匹配研究*

宋 丹

(中國西南電子技術(shù)研究所，四川 成都 610036)

針對目標(biāo)精確定位中圖像實(shí)時匹配性能的瓶頸問題，提出了一種基于TMS320C6678多核DSP的圖像實(shí)時相關(guān)匹配方法。該方法采用并行處理設(shè)計，將復(fù)雜耗時的互相關(guān)運(yùn)算分解并平均分配到多個核中同時進(jìn)行；采用算法優(yōu)化設(shè)計，將優(yōu)化的快速匹配算法與預(yù)處理、搜索策略控制等方法相結(jié)合，實(shí)現(xiàn)圖像的快速匹配。實(shí)驗結(jié)果表明，該方法在保證匹配準(zhǔn)確性的同時，還能顯著降低圖像相關(guān)匹配的計算時間，滿足實(shí)時處理要求。

相關(guān)匹配；實(shí)時；并行處理；多核DSP

0 引 言

圖像匹配技術(shù)是數(shù)字圖像處理的關(guān)鍵技術(shù)之一。它在飛機(jī)輔助導(dǎo)航、遠(yuǎn)程武器或精確制導(dǎo)武器系統(tǒng)如巡航導(dǎo)彈的末制導(dǎo)、光學(xué)與雷達(dá)圖像目標(biāo)搜索與定位等軍事領(lǐng)域具有重要的應(yīng)用價值[1]。

圖像匹配算法主要分為兩大類：一類是基于灰度相關(guān)的匹配，另一類是基于特征的匹配[2]。目前，運(yùn)用比較廣泛的是基于灰度相關(guān)的匹配算法，其抗噪聲能力強(qiáng)，在灰度及幾何畸變不大的情況下，匹配概率及精度較高，缺點(diǎn)是計算量大，匹配速度慢，抗灰度及幾何畸變能力較弱。以800×800大小的圖像與480×480大小的圖像相關(guān)匹配為例，僅計算互相關(guān)系數(shù)就需乘加運(yùn)算多達(dá)700億次，另外還需開方運(yùn)算20萬次。顯然，如此巨大的計算量很難實(shí)時處理實(shí)現(xiàn)，必須減少其計算量或提高處理速度。

并行處理技術(shù)是提高計算處理速度的有效途徑，其核心思想是將復(fù)雜的運(yùn)算分解并盡可能平均分配到多個處理單元中同時進(jìn)行。而并行處理結(jié)構(gòu)和并行處理算法則是實(shí)現(xiàn)并行性的基本方法[3]。隨著近年來芯片技術(shù)的發(fā)展，多核DSP越來越多的用于圖像的實(shí)時并行處理，其在單個芯片內(nèi)集成了多個高頻率內(nèi)核，多內(nèi)核通過高速總線共享內(nèi)部存儲器和芯片外設(shè)，從而獲得高性能的并行處理能力[4]

TI公司推出的TMS320C66x系列DSP為多核定點(diǎn)/浮點(diǎn)處理器，每個核的最高主頻可以達(dá)到1.25 GHz。其中，TMS320C6678號稱是業(yè)界性能最高、功耗最低的DSP[5]，其具有8個1.25 GHz DSP內(nèi)核，定點(diǎn)運(yùn)算能力高達(dá)320GMACS，浮點(diǎn)運(yùn)算能力高達(dá)160GFLOPS[6],非常適合于圖像實(shí)時處理這種需要超高性能以及并行運(yùn)算的應(yīng)用。

這篇文章基于TMS320C6678 DSP的特點(diǎn)開展了圖像實(shí)時相關(guān)匹配的研究，在TI 公司的TMDS EVM6678L DSP評估板上實(shí)時處理實(shí)現(xiàn)，并進(jìn)行了實(shí)驗驗證，給出了實(shí)驗結(jié)果。

1 多核并行處理設(shè)計

1.1 C6678 DSP簡介

TMS320C6678屬于TI公司的C66xDSP系列，采用Keystone多核體系結(jié)構(gòu)，內(nèi)部集成最新的C66x DSP內(nèi)核，其主要特性如下：

1)集成8個C66x內(nèi)核，每個內(nèi)核頻率可達(dá)1.25 GHz。

2)具有雙運(yùn)算模塊，能夠進(jìn)行定點(diǎn)和浮點(diǎn)運(yùn)算。

3)集成了大量片上存儲器資源，包括每個內(nèi)核32 KB L1程序和32 KB L1數(shù)據(jù)緩存、512 KB的可配置專用存儲器以及4 096 KB多核共享存儲器，還提供了運(yùn)行速率達(dá)1 600 MHz的64 bit DDR3存儲器接口。

4)集成了大量片上外設(shè)及高速接口，其中串行Rapid IO、PCIE接口適用于芯片級、板級的互連，能提供極高的傳輸速率。

1.2 并行處理框架

C6678擁有8個內(nèi)核，相當(dāng)于8個獨(dú)立的處理單元。為了實(shí)現(xiàn)并行處理，需要將復(fù)雜的運(yùn)算分解，并基于一定的規(guī)則合理分配到各個處理單元中同時進(jìn)行，一般有兩種主要的運(yùn)行方式[7]：

1)主從方式：即用一個處理單元(主核)完成處理的流程控制及任務(wù)分配，協(xié)調(diào)管理其它處理單元(從核)進(jìn)行相應(yīng)的處理運(yùn)算。

2)數(shù)據(jù)流方式：即流水線處理，各個核為流水線中的一環(huán)，由上級處理單元數(shù)據(jù)驅(qū)動，完成自身運(yùn)算后輸出到下級處理單元。

根據(jù)圖像數(shù)據(jù)塊的結(jié)構(gòu)特點(diǎn)，把大圖像分割成小數(shù)據(jù)塊并分配給各個核中處理是實(shí)現(xiàn)相關(guān)并行處理的可行方法，宜采用主從處理方式。而從數(shù)據(jù)接口考慮，數(shù)據(jù)輸入輸出與數(shù)據(jù)處理之間為串行結(jié)構(gòu)，則最好采用數(shù)據(jù)流方式。因此，這篇文章中基于C6678的圖像相關(guān)匹配并行處理采用主從方式和數(shù)據(jù)流方式的混合架構(gòu)，其架構(gòu)設(shè)計如圖1所示。

圖1 基于C6678的圖像并行處理架構(gòu)設(shè)計

由圖1可見，C6678中的8個處理單元分為3類，分別用作接口控制(接口單元)，任務(wù)管理控制(主處理單元)和圖像匹配處理運(yùn)算(從處理單元)。其中接口單元和主處理單元之間采用數(shù)據(jù)流方式處理，接口單元負(fù)責(zé)對外設(shè)命令或者中斷的響應(yīng)及數(shù)據(jù)接收，然后將圖像匹配處理所需的數(shù)據(jù)傳遞給主處理單元，啟動圖像匹配處理。主處理單元和從處理單元之間則采用主從方式，主處理單元接收到任務(wù)后(來自接口單元的數(shù)據(jù)和命令)，負(fù)責(zé)對任務(wù)分解管理，并調(diào)度從處理單元協(xié)同處理，共同完成。

1.3 任務(wù)管理

任務(wù)管理由主處理單元負(fù)責(zé)，其目的是采用一定的策略將復(fù)雜運(yùn)算分解成多個子任務(wù)，然后再合理管理調(diào)度從處理單元資源，并將子任務(wù)分配給從處理單元處理，最后收集各從處理單元的處理結(jié)果并綜合處理得出最終結(jié)果。其中的關(guān)鍵在于任務(wù)分解和資源調(diào)度，由DSP參與各種控制盒并行多任務(wù)的處理[8]。

任務(wù)分解是一個系統(tǒng)性工作，需考慮分解后各子任務(wù)的相對獨(dú)立性。如果分解后的子任務(wù)相互之間關(guān)聯(lián)較大，將很難做到并行處理。對于圖像處理來說，將大圖像分解成相對較小的子圖像是一個簡單快捷并行之有效的任務(wù)分解方法。而針對圖像相關(guān)匹配處理，可將大匹配搜索區(qū)域分解成較小的子區(qū)域，這樣就將運(yùn)算量最大的相關(guān)系數(shù)運(yùn)算進(jìn)行了分解，如圖 2所示。在分解時，需要注意從處理單元的數(shù)量，盡可能將大圖像分割成從處理單元數(shù)的整數(shù)倍個數(shù)據(jù)塊，從而使子任務(wù)能平均分配到各從處理單元，這樣才能最大效率發(fā)揮并行處理能力。

圖2 圖像匹配任務(wù)分解

在該設(shè)計中，主處理單元采用循環(huán)查詢的方式進(jìn)行資源調(diào)度和任務(wù)分配。主處理單元不間斷的循環(huán)順序查詢6個從處理單元的狀態(tài)，若發(fā)現(xiàn)其空閑，則分配一個子任務(wù)給該從處理單元進(jìn)行處理，并等待其結(jié)果返回。每個從處理單元對于主處理單元，被設(shè)計標(biāo)識為3種狀態(tài)：空閑(未分配任務(wù))、數(shù)據(jù)發(fā)送(分配任務(wù))、結(jié)果等待(等待從處理單元處理，接收結(jié)果)。狀態(tài)轉(zhuǎn)換如圖 3所示。

圖3 從處理單元狀態(tài)轉(zhuǎn)換

1.4 核間通信

多核協(xié)同處理必然涉及到核之間的通信，包括數(shù)據(jù)通信和狀態(tài)通信。而其通信效率會影響到整個并行處理的運(yùn)行效率，因此核間通信也是并行處理的關(guān)鍵。

該設(shè)計采用共享存儲空間的方式來進(jìn)行核間通信，需要通信的兩個核之間分別設(shè)計數(shù)據(jù)存儲空間和狀態(tài)存儲空間。數(shù)據(jù)存儲空間用于存儲待處理的數(shù)據(jù)，由一個核寫入，一個核讀取，完成寫入或者讀取操作后，再將狀態(tài)信息寫入狀態(tài)存儲空間。各核仍采用查詢的方式獲取共享空間的數(shù)據(jù)和狀態(tài)。同時，為數(shù)據(jù)提高傳輸效率，核之間的數(shù)據(jù)交互設(shè)計為乒乓操作。

2 算法優(yōu)化設(shè)計

2.1 相關(guān)匹配算法簡介

采用應(yīng)用廣泛、成熟的歸一化互相關(guān)匹配算法，具體描述如下：

已知基準(zhǔn)圖Z尺寸為M×N，實(shí)時圖Y尺寸為m×n，實(shí)時圖Y在基準(zhǔn)圖Z中逐行逐列搜索匹配，在基準(zhǔn)圖上可依次形成(M-m+1)×(N-n+1)個子圖。每個子圖尺寸為m×n。則第k個子圖X與實(shí)時圖Y的相關(guān)系數(shù)：

(1)

式中，xij為子圖X中第i行、第j列像元的灰度值；yij為實(shí)時圖Y中第i行、第j列像元的灰度值。相關(guān)系數(shù)極大值對應(yīng)子圖在基準(zhǔn)圖上的位置即為最佳匹配位置[9]。

由公式可知，計算相關(guān)系數(shù)的運(yùn)算量相當(dāng)巨大，乘加運(yùn)算次數(shù)與3×(M-m+1)×(N-n+1)×m×n成正比，開方運(yùn)算次數(shù)與2×(M-m+1)×(N-n+1)成正比，而開方運(yùn)算對于DSP來說又相當(dāng)復(fù)雜，需要耗費(fèi)大量處理時鐘周期。仍以計算800×800大小基準(zhǔn)圖與480×480大小實(shí)時圖的相關(guān)系數(shù)為例，約需乘加運(yùn)算700億次，開方運(yùn)算20萬次。即使采用上節(jié)中基于TMS320C6678多核DSP的并行處理設(shè)計，每核仍需承擔(dān)約120億次乘加運(yùn)算，4萬次開方運(yùn)算。再根據(jù)DSP處理能力進(jìn)行估算可知，完成這些運(yùn)算需耗時10秒左右，顯然還達(dá)不到實(shí)時處理的要求。因此，還需對算法加以優(yōu)化改進(jìn)，以減少運(yùn)算量及運(yùn)算復(fù)雜度。

2.2 相關(guān)系數(shù)計算公式變換

(2)

2.3 事先預(yù)處理

H(i,j)=∑∑X(i,j)2

(3)

如圖 4(a)所示，基準(zhǔn)圖像素灰度平方和積分圖像H中任意一點(diǎn)H(i,j)表示的是基準(zhǔn)圖X中陰影部分的所有像素灰度平方和。利用該積分圖像，對于任意大小的矩形區(qū)域，即任意基準(zhǔn)圖子圖，只需4個點(diǎn)進(jìn)行3次加法運(yùn)算就可以計算出該區(qū)域的像素灰度平方和。如圖 4(b) 所示，設(shè)陰影區(qū)域內(nèi)的像素灰度平方和為S，則：

S=H(i1,j1)-H(i1,j2)-H(i2,j1)+H(i2,j2)

(4)

圖4 基準(zhǔn)圖子圖像素灰度平方和計算

∑∑xijyij為基準(zhǔn)圖子圖與實(shí)時圖的灰度互相關(guān)值，這也需要每個子圖重新計算，且不能再優(yōu)化。

可見，經(jīng)過事先預(yù)處理優(yōu)化后，相關(guān)匹配的主要運(yùn)算量只剩∑∑xijyij，已大大減少。

2.4 搜索策略優(yōu)化

相關(guān)匹配的基本搜索策略是遍歷性搜索，即在搜索區(qū)域內(nèi)逐行逐列每個像素位置上計算相關(guān)系數(shù)值。因此，如果能改進(jìn)搜索策略，實(shí)現(xiàn)非遍歷性搜索，將大大減少相關(guān)匹配的運(yùn)算量。

3 實(shí)時處理實(shí)現(xiàn)

采用上述的多核并行處理設(shè)計和算法優(yōu)化設(shè)計方法，在C6678多核DSP中實(shí)時處理實(shí)現(xiàn)歸一化互相關(guān)圖像匹配。其中，Core0為主處理單元，負(fù)責(zé)圖像的分割和任務(wù)分配，Core2～Core7為從處理單元，根據(jù)主處理單元分配的任務(wù)完成相應(yīng)處理。

歸一化互相相關(guān)圖像匹配的主要運(yùn)算量在相關(guān)系數(shù)計算上，且相關(guān)系數(shù)計算彼此之間沒有關(guān)聯(lián)，因此可以將相關(guān)系數(shù)計算分解并分配給從處理單元協(xié)同處理；而圖像預(yù)處理(含金字塔分解)以及相關(guān)系數(shù)極大值計算需用到全部圖像數(shù)據(jù)，因此使用主處理單元單獨(dú)處理。處理流程如圖5所示。

Core0為主處理單元，控制整個相關(guān)匹配的工作流程。接收到待處理的圖像數(shù)據(jù)后，首先對圖像進(jìn)行預(yù)處理，包括圖像濾波去噪，旋轉(zhuǎn)、幾何校正等，并對圖像進(jìn)行金字塔分解。然后，根據(jù)從處理單元資源(如從處理單元個數(shù)、從處理單元內(nèi)部存儲空間大小、數(shù)據(jù)交互緩存空間大小等)，將基準(zhǔn)圖(大圖)分解為從處理單元數(shù)整數(shù)倍個數(shù)據(jù)塊，并分配給從處理單元進(jìn)行處理。從處理單元接收到任務(wù)后，完成指定的相關(guān)系數(shù)計算后，將結(jié)果送回給Core0，由Core0綜合所有的相關(guān)系數(shù)形成相關(guān)面，并求得最高峰所在位置即為匹配位置。每一級金字塔都如此操作，直至在原始圖像中獲得最終的匹配結(jié)果。

圖5 相關(guān)匹配多核處理流程

4 實(shí)驗結(jié)果

使用800×800大小基準(zhǔn)圖，480×480大小實(shí)時圖共20余組光學(xué)圖像進(jìn)行實(shí)驗驗證，其中實(shí)時圖從基準(zhǔn)圖中裁剪，并經(jīng)過模糊、加噪等處理后獲得。實(shí)驗分別在PC(CPU 雙核3.2 GHz，內(nèi)存4 G，Matlab實(shí)現(xiàn))和DSP(TI公司的TMDS EVM6678L DSP評估板)上進(jìn)行，所用時間統(tǒng)計如表 1所示，而DSP實(shí)時匹配效果如圖6和圖7所示。

由表1統(tǒng)計結(jié)果可知，這篇文章提出的基于多核DSP的圖像實(shí)時相關(guān)匹配設(shè)計很好的解決了以往圖像相關(guān)匹配處理速度慢的問題，能夠滿足高實(shí)時處理要求。同時，圖 6和圖 7的匹配結(jié)果表明，該設(shè)計方法在降低處理時間的同時可以保證匹配的準(zhǔn)確性。

圖6 相關(guān)匹配實(shí)驗結(jié)果圖1

圖7 相關(guān)匹配實(shí)驗結(jié)果圖2

表1 相關(guān)匹配運(yùn)行時間比較

5 結(jié) 語

針對圖像相關(guān)匹配計算量大，匹配速度慢，難以實(shí)時處理實(shí)現(xiàn)的缺點(diǎn)，這篇文章基于多核DSP提出了一種圖像實(shí)時相關(guān)匹配方法。該方法采用了并行處理設(shè)計和算法優(yōu)化設(shè)計，提高了相關(guān)匹配的處理速度。實(shí)驗結(jié)果表明，較傳統(tǒng)相關(guān)匹配方法而言，該方法顯著降低了相關(guān)匹配的處理時間，能有效完成圖像相關(guān)匹配的實(shí)時處理，同時又保證了匹配的準(zhǔn)確性，可應(yīng)用于對處理有高實(shí)時性要求的軍事領(lǐng)域中，如精確制導(dǎo)武器系統(tǒng)、飛機(jī)輔助導(dǎo)航等。

[1] 楊小岡,繆棟,曹菲.一種實(shí)用的景象匹配仿真方法[J].系統(tǒng)仿真學(xué)報,2004,16(03):363-365. YANG Xiao-gang, MIAO Dong, CAO Fei. A Practical Scene Matching Simulation Method[J].Journal of System Simlation,2004,16(03):363-365.

[2] 劉瑩,曹劍中,許朝暉等.基于灰度相關(guān)的圖像匹配算法的改進(jìn)[J].應(yīng)用光學(xué),2007,28(05):536-539. LIU Ying,CAO Jian-zhong,XU Chao-hui,et al.Improvement of image matching algorithm based on gray correlation[J].Journal of Applied Optics,2007,28(05):536-539.

[3] 柴震海.圖像并行處理技術(shù)[J].紅外,2005(03):27-33. CHAI Zhen-hai. Parallel Image Processing Technology[J].Infrared,2005(03):27-33.

[4] 張穎川.多核數(shù)字信號處理平臺的設(shè)計與實(shí)現(xiàn)[D].西安:西安電子科技大學(xué),2013. ZHANG Ying-chuan. Design and Implementation of Multi-core Digital Signal Processing Platform[D].Xi’an:University of Electronic Science and Technology of Xi’an,2013.

[5] 張慧娟.低功耗高性能多核DSP滿足高性能計算[J].EDA CHINA, 2012(02):16. ZHANG Hui-juan.Low Power and High Performance Multi-Core DSP Meet the High Performance Computing[J]. EDA CHINA, 2012(02):16.

[6] Texas Instruments.TMS320C6678 Multicore Fixed and Floating-Point Digital Signal Processor Data Manual[DB/OL].US: Texas Instruments,2011[2015.12.24].www.ti.com.

[7] 丁有源,汪安民.基于多任務(wù)并行處理的DSP軟硬件設(shè)計[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用,2012(05):43-45. DING You-yuan,WANG An-min.Software and Hardware Designs of DSP based on Multi-core Task Parallel Processing[J].Microcontrollers & Embedded Systems,2012(05):43-45.

[8] 易克非,胡慶鋒.基于DSP的實(shí)時多任務(wù)調(diào)度內(nèi)核設(shè)計[J].通信技術(shù),2011,44(06):135-137. YI Ke-fie,HU Qing-feng. Design of Real-Time Multi-Task Kernel for DSP[J].Communications Technology, 2011,44(06):135-137.

[9] 蔣運(yùn)輝.光學(xué)/SAR圖像的多DSP實(shí)時匹配系統(tǒng)的設(shè)計與實(shí)現(xiàn)[J].電子測量與儀器學(xué)報,2011,25(05):449-454. JIANG Yun-hui.Design and Implementation of Multi-DSPs’ Real-time Matching System based on Optical and SAR Images[J].Journal of Electronic Measurement and Instrument, 2011,25(05):449-454.

[10] 何芳芳,孫繼銀,劉小雷等.分層搜索在景象匹配中的應(yīng)用研究[J].現(xiàn)代防御技術(shù),2005,33(04):36-38,67. HE Fang-fang,SUN Ji-yin,LIU Xiao-lei,et al.Layered-searching for Scene Matching[J].Modern Defense Technology,2005,33(4):36-38,67.

[11] 曹菲,楊小岡,繆棟等.快速景象匹配算法控制策略[J].導(dǎo)彈與航天運(yùn)載技術(shù),2005(03):46-50. CAO Fei,YANG Xiao-gang,MIAO Dong,et al.Control Strategy of Fast Scene Matching Algorithm[J].Missiles and Space Vehicles,2005(03):46-50.

Image Real-Time Correlation Matching based on Multi-Cores DSP

SONG Dan

(Southwest China Institute of Electronic Technology, Chengdu Sichuan 610036, China)

Aiming at the bottleneck of image real-time performance matching in objective accurate positioning, an approach of image real-time correlation matching based on TMS320C6678 multi-cores DSP processor is proposed. The design of parallel processing is adopted in this appoach, thus to resolve the complicated and time-cosuming cross-correlation operation into several sections and equally assign them to multiple cores of DSP for simultaneous procesing. Meanwhile, the modified algorithm could speed up the image matching by combining fast optimized matching algorithm with pre-processing, searching strategy control etc. Experiment result shows that this algorithm could guarantee the matching accuracy while remarkably decrease the time of image correlation matching, so as to meet the demand of real-time process.

correlation matching; real-time; parallel processing; multi-cores DSP

date:2014-10-20；Revised date：2015-02-17

TN911.73

A

1002-0802(2015)04-0501-06

宋 丹(1981—)，男，工程師，主要研究方向為精確制導(dǎo)技術(shù)以及DSP實(shí)現(xiàn)。

10.3969/j.issn.1002-0802.2015.04.023

2014-10-20；

2015-02-17