宋 丹

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

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

宋 丹

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

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

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

0 引 言

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

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

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

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

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

1 多核并行處理設計

1.1 C6678 DSP簡介

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

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

2)具有雙運算模塊，能夠進行定點和浮點運算。

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

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

1.2 并行處理框架

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

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

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

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

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

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

1.3 任務管理

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

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

圖2 圖像匹配任務分解

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

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

1.4 核間通信

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

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

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

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

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

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

(1)

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

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

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

(2)

2.3 事先預處理

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

(3)

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

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

(4)

圖4 基準圖子圖像素灰度平方和計算

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果

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

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

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

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

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

5 結(jié) 語

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

[1] 楊小岡,繆棟,曹菲.一種實用的景象匹配仿真方法[J].系統(tǒng)仿真學報,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].應用光學,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ù)字信號處理平臺的設計與實現(xiàn)[D].西安:西安電子科技大學,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] 丁有源,汪安民.基于多任務并行處理的DSP軟硬件設計[J].單片機與嵌入式系統(tǒ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的實時多任務調(diào)度內(nèi)核設計[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] 蔣運輝.光學/SAR圖像的多DSP實時匹配系統(tǒng)的設計與實現(xiàn)[J].電子測量與儀器學報,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] 何芳芳,孫繼銀,劉小雷等.分層搜索在景象匹配中的應用研究[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].導彈與航天運載技術(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—)，男，工程師，主要研究方向為精確制導技術(shù)以及DSP實現(xiàn)。

10.3969/j.issn.1002-0802.2015.04.023

2014-10-20；

2015-02-17