宋 丹
(中國(guó)西南電子技術(shù)研究所,四川 成都 610036)
基于多核DSP的圖像實(shí)時(shí)相關(guān)匹配研究*
宋 丹
(中國(guó)西南電子技術(shù)研究所,四川 成都 610036)
針對(duì)目標(biāo)精確定位中圖像實(shí)時(shí)匹配性能的瓶頸問(wèn)題,提出了一種基于TMS320C6678多核DSP的圖像實(shí)時(shí)相關(guān)匹配方法。該方法采用并行處理設(shè)計(jì),將復(fù)雜耗時(shí)的互相關(guān)運(yùn)算分解并平均分配到多個(gè)核中同時(shí)進(jìn)行;采用算法優(yōu)化設(shè)計(jì),將優(yōu)化的快速匹配算法與預(yù)處理、搜索策略控制等方法相結(jié)合,實(shí)現(xiàn)圖像的快速匹配。實(shí)驗(yàn)結(jié)果表明,該方法在保證匹配準(zhǔn)確性的同時(shí),還能顯著降低圖像相關(guān)匹配的計(jì)算時(shí)間,滿(mǎn)足實(shí)時(shí)處理要求。
相關(guān)匹配;實(shí)時(shí);并行處理;多核DSP
圖像匹配技術(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)用價(jià)值[1]。
圖像匹配算法主要分為兩大類(lèi):一類(lèi)是基于灰度相關(guān)的匹配,另一類(lèi)是基于特征的匹配[2]。目前,運(yùn)用比較廣泛的是基于灰度相關(guān)的匹配算法,其抗噪聲能力強(qiáng),在灰度及幾何畸變不大的情況下,匹配概率及精度較高,缺點(diǎn)是計(jì)算量大,匹配速度慢,抗灰度及幾何畸變能力較弱。以800×800大小的圖像與480×480大小的圖像相關(guān)匹配為例,僅計(jì)算互相關(guān)系數(shù)就需乘加運(yùn)算多達(dá)700億次,另外還需開(kāi)方運(yùn)算20萬(wàn)次。顯然,如此巨大的計(jì)算量很難實(shí)時(shí)處理實(shí)現(xiàn),必須減少其計(jì)算量或提高處理速度。
并行處理技術(shù)是提高計(jì)算處理速度的有效途徑,其核心思想是將復(fù)雜的運(yùn)算分解并盡可能平均分配到多個(gè)處理單元中同時(shí)進(jìn)行。而并行處理結(jié)構(gòu)和并行處理算法則是實(shí)現(xiàn)并行性的基本方法[3]。隨著近年來(lái)芯片技術(shù)的發(fā)展,多核DSP越來(lái)越多的用于圖像的實(shí)時(shí)并行處理,其在單個(gè)芯片內(nèi)集成了多個(gè)高頻率內(nèi)核,多內(nèi)核通過(guò)高速總線(xiàn)共享內(nèi)部存儲(chǔ)器和芯片外設(shè),從而獲得高性能的并行處理能力[4]
TI公司推出的TMS320C66x系列DSP為多核定點(diǎn)/浮點(diǎn)處理器,每個(gè)核的最高主頻可以達(dá)到1.25 GHz。其中,TMS320C6678號(hào)稱(chēng)是業(yè)界性能最高、功耗最低的DSP[5],其具有8個(gè)1.25 GHz DSP內(nèi)核,定點(diǎn)運(yùn)算能力高達(dá)320GMACS,浮點(diǎn)運(yùn)算能力高達(dá)160GFLOPS[6],非常適合于圖像實(shí)時(shí)處理這種需要超高性能以及并行運(yùn)算的應(yīng)用。
這篇文章基于TMS320C6678 DSP的特點(diǎn)開(kāi)展了圖像實(shí)時(shí)相關(guān)匹配的研究,在TI 公司的TMDS EVM6678L DSP評(píng)估板上實(shí)時(shí)處理實(shí)現(xiàn),并進(jìn)行了實(shí)驗(yàn)驗(yàn)證,給出了實(shí)驗(yàn)結(jié)果。
1.1 C6678 DSP簡(jiǎn)介
TMS320C6678屬于TI公司的C66xDSP系列,采用Keystone多核體系結(jié)構(gòu),內(nèi)部集成最新的C66x DSP內(nèi)核,其主要特性如下:
1)集成8個(gè)C66x內(nèi)核,每個(gè)內(nèi)核頻率可達(dá)1.25 GHz。
2)具有雙運(yùn)算模塊,能夠進(jìn)行定點(diǎn)和浮點(diǎn)運(yùn)算。
3)集成了大量片上存儲(chǔ)器資源,包括每個(gè)內(nèi)核32 KB L1程序和32 KB L1數(shù)據(jù)緩存、512 KB的可配置專(zhuān)用存儲(chǔ)器以及4 096 KB多核共享存儲(chǔ)器,還提供了運(yùn)行速率達(dá)1 600 MHz的64 bit DDR3存儲(chǔ)器接口。
4)集成了大量片上外設(shè)及高速接口,其中串行Rapid IO、PCIE接口適用于芯片級(jí)、板級(jí)的互連,能提供極高的傳輸速率。
1.2 并行處理框架
C6678擁有8個(gè)內(nèi)核,相當(dāng)于8個(gè)獨(dú)立的處理單元。為了實(shí)現(xiàn)并行處理,需要將復(fù)雜的運(yùn)算分解,并基于一定的規(guī)則合理分配到各個(gè)處理單元中同時(shí)進(jìn)行,一般有兩種主要的運(yùn)行方式[7]:
1)主從方式:即用一個(gè)處理單元(主核)完成處理的流程控制及任務(wù)分配,協(xié)調(diào)管理其它處理單元(從核)進(jìn)行相應(yīng)的處理運(yùn)算。
2)數(shù)據(jù)流方式:即流水線(xiàn)處理,各個(gè)核為流水線(xiàn)中的一環(huán),由上級(jí)處理單元數(shù)據(jù)驅(qū)動(dòng),完成自身運(yùn)算后輸出到下級(jí)處理單元。
根據(jù)圖像數(shù)據(jù)塊的結(jié)構(gòu)特點(diǎn),把大圖像分割成小數(shù)據(jù)塊并分配給各個(gè)核中處理是實(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è)計(jì)如圖1所示。
圖1 基于C6678的圖像并行處理架構(gòu)設(shè)計(jì)
由圖1可見(jiàn),C6678中的8個(gè)處理單元分為3類(lèi),分別用作接口控制(接口單元),任務(wù)管理控制(主處理單元)和圖像匹配處理運(yùn)算(從處理單元)。其中接口單元和主處理單元之間采用數(shù)據(jù)流方式處理,接口單元負(fù)責(zé)對(duì)外設(shè)命令或者中斷的響應(yīng)及數(shù)據(jù)接收,然后將圖像匹配處理所需的數(shù)據(jù)傳遞給主處理單元,啟動(dòng)圖像匹配處理。主處理單元和從處理單元之間則采用主從方式,主處理單元接收到任務(wù)后(來(lái)自接口單元的數(shù)據(jù)和命令),負(fù)責(zé)對(duì)任務(wù)分解管理,并調(diào)度從處理單元協(xié)同處理,共同完成。
1.3 任務(wù)管理
任務(wù)管理由主處理單元負(fù)責(zé),其目的是采用一定的策略將復(fù)雜運(yùn)算分解成多個(gè)子任務(wù),然后再合理管理調(diào)度從處理單元資源,并將子任務(wù)分配給從處理單元處理,最后收集各從處理單元的處理結(jié)果并綜合處理得出最終結(jié)果。其中的關(guān)鍵在于任務(wù)分解和資源調(diào)度,由DSP參與各種控制盒并行多任務(wù)的處理[8]。
任務(wù)分解是一個(gè)系統(tǒng)性工作,需考慮分解后各子任務(wù)的相對(duì)獨(dú)立性。如果分解后的子任務(wù)相互之間關(guān)聯(lián)較大,將很難做到并行處理。對(duì)于圖像處理來(lái)說(shuō),將大圖像分解成相對(duì)較小的子圖像是一個(gè)簡(jiǎn)單快捷并行之有效的任務(wù)分解方法。而針對(duì)圖像相關(guān)匹配處理,可將大匹配搜索區(qū)域分解成較小的子區(qū)域,這樣就將運(yùn)算量最大的相關(guān)系數(shù)運(yùn)算進(jìn)行了分解,如圖 2所示。在分解時(shí),需要注意從處理單元的數(shù)量,盡可能將大圖像分割成從處理單元數(shù)的整數(shù)倍個(gè)數(shù)據(jù)塊,從而使子任務(wù)能平均分配到各從處理單元,這樣才能最大效率發(fā)揮并行處理能力。
圖2 圖像匹配任務(wù)分解
在該設(shè)計(jì)中,主處理單元采用循環(huán)查詢(xún)的方式進(jìn)行資源調(diào)度和任務(wù)分配。主處理單元不間斷的循環(huán)順序查詢(xún)6個(gè)從處理單元的狀態(tài),若發(fā)現(xiàn)其空閑,則分配一個(gè)子任務(wù)給該從處理單元進(jìn)行處理,并等待其結(jié)果返回。每個(gè)從處理單元對(duì)于主處理單元,被設(shè)計(jì)標(biāo)識(shí)為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)通信。而其通信效率會(huì)影響到整個(gè)并行處理的運(yùn)行效率,因此核間通信也是并行處理的關(guān)鍵。
該設(shè)計(jì)采用共享存儲(chǔ)空間的方式來(lái)進(jìn)行核間通信,需要通信的兩個(gè)核之間分別設(shè)計(jì)數(shù)據(jù)存儲(chǔ)空間和狀態(tài)存儲(chǔ)空間。數(shù)據(jù)存儲(chǔ)空間用于存儲(chǔ)待處理的數(shù)據(jù),由一個(gè)核寫(xiě)入,一個(gè)核讀取,完成寫(xiě)入或者讀取操作后,再將狀態(tài)信息寫(xiě)入狀態(tài)存儲(chǔ)空間。各核仍采用查詢(xún)的方式獲取共享空間的數(shù)據(jù)和狀態(tài)。同時(shí),為數(shù)據(jù)提高傳輸效率,核之間的數(shù)據(jù)交互設(shè)計(jì)為乒乓操作。
2.1 相關(guān)匹配算法簡(jiǎn)介
采用應(yīng)用廣泛、成熟的歸一化互相關(guān)匹配算法,具體描述如下:
已知基準(zhǔn)圖Z尺寸為M×N,實(shí)時(shí)圖Y尺寸為m×n,實(shí)時(shí)圖Y在基準(zhǔn)圖Z中逐行逐列搜索匹配,在基準(zhǔn)圖上可依次形成(M-m+1)×(N-n+1)個(gè)子圖。每個(gè)子圖尺寸為m×n。則第k個(gè)子圖X與實(shí)時(shí)圖Y的相關(guān)系數(shù):
(1)
式中,xij為子圖X中第i行、第j列像元的灰度值;yij為實(shí)時(shí)圖Y中第i行、第j列像元的灰度值。相關(guān)系數(shù)極大值對(duì)應(yīng)子圖在基準(zhǔn)圖上的位置即為最佳匹配位置[9]。
由公式可知,計(jì)算相關(guān)系數(shù)的運(yùn)算量相當(dāng)巨大,乘加運(yùn)算次數(shù)與3×(M-m+1)×(N-n+1)×m×n成正比,開(kāi)方運(yùn)算次數(shù)與2×(M-m+1)×(N-n+1)成正比,而開(kāi)方運(yùn)算對(duì)于DSP來(lái)說(shuō)又相當(dāng)復(fù)雜,需要耗費(fèi)大量處理時(shí)鐘周期。仍以計(jì)算800×800大小基準(zhǔn)圖與480×480大小實(shí)時(shí)圖的相關(guān)系數(shù)為例,約需乘加運(yùn)算700億次,開(kāi)方運(yùn)算20萬(wàn)次。即使采用上節(jié)中基于TMS320C6678多核DSP的并行處理設(shè)計(jì),每核仍需承擔(dān)約120億次乘加運(yùn)算,4萬(wàn)次開(kāi)方運(yùn)算。再根據(jù)DSP處理能力進(jìn)行估算可知,完成這些運(yùn)算需耗時(shí)10秒左右,顯然還達(dá)不到實(shí)時(shí)處理的要求。因此,還需對(duì)算法加以?xún)?yōu)化改進(jìn),以減少運(yùn)算量及運(yùn)算復(fù)雜度。
2.2 相關(guān)系數(shù)計(jì)算公式變換
(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中陰影部分的所有像素灰度平方和。利用該積分圖像,對(duì)于任意大小的矩形區(qū)域,即任意基準(zhǔn)圖子圖,只需4個(gè)點(diǎn)進(jìn)行3次加法運(yùn)算就可以計(jì)算出該區(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)圖子圖像素灰度平方和計(jì)算
∑∑xijyij為基準(zhǔn)圖子圖與實(shí)時(shí)圖的灰度互相關(guān)值,這也需要每個(gè)子圖重新計(jì)算,且不能再優(yōu)化。
可見(jiàn),經(jīng)過(guò)事先預(yù)處理優(yōu)化后,相關(guān)匹配的主要運(yùn)算量只?!啤苮ijyij,已大大減少。
2.4 搜索策略?xún)?yōu)化
相關(guān)匹配的基本搜索策略是遍歷性搜索,即在搜索區(qū)域內(nèi)逐行逐列每個(gè)像素位置上計(jì)算相關(guān)系數(shù)值。因此,如果能改進(jìn)搜索策略,實(shí)現(xiàn)非遍歷性搜索,將大大減少相關(guān)匹配的運(yùn)算量。
采用上述的多核并行處理設(shè)計(jì)和算法優(yōu)化設(shè)計(jì)方法,在C6678多核DSP中實(shí)時(shí)處理實(shí)現(xiàn)歸一化互相關(guān)圖像匹配。其中,Core0為主處理單元,負(fù)責(zé)圖像的分割和任務(wù)分配,Core2~Core7為從處理單元,根據(jù)主處理單元分配的任務(wù)完成相應(yīng)處理。
歸一化互相相關(guān)圖像匹配的主要運(yùn)算量在相關(guān)系數(shù)計(jì)算上,且相關(guān)系數(shù)計(jì)算彼此之間沒(méi)有關(guān)聯(lián),因此可以將相關(guān)系數(shù)計(jì)算分解并分配給從處理單元協(xié)同處理;而圖像預(yù)處理(含金字塔分解)以及相關(guān)系數(shù)極大值計(jì)算需用到全部圖像數(shù)據(jù),因此使用主處理單元單獨(dú)處理。處理流程如圖5所示。
Core0為主處理單元,控制整個(gè)相關(guān)匹配的工作流程。接收到待處理的圖像數(shù)據(jù)后,首先對(duì)圖像進(jìn)行預(yù)處理,包括圖像濾波去噪,旋轉(zhuǎn)、幾何校正等,并對(duì)圖像進(jìn)行金字塔分解。然后,根據(jù)從處理單元資源(如從處理單元個(gè)數(shù)、從處理單元內(nèi)部存儲(chǔ)空間大小、數(shù)據(jù)交互緩存空間大小等),將基準(zhǔn)圖(大圖)分解為從處理單元數(shù)整數(shù)倍個(gè)數(shù)據(jù)塊,并分配給從處理單元進(jìn)行處理。從處理單元接收到任務(wù)后,完成指定的相關(guān)系數(shù)計(jì)算后,將結(jié)果送回給Core0,由Core0綜合所有的相關(guān)系數(shù)形成相關(guān)面,并求得最高峰所在位置即為匹配位置。每一級(jí)金字塔都如此操作,直至在原始圖像中獲得最終的匹配結(jié)果。
圖5 相關(guān)匹配多核處理流程
使用800×800大小基準(zhǔn)圖,480×480大小實(shí)時(shí)圖共20余組光學(xué)圖像進(jìn)行實(shí)驗(yàn)驗(yàn)證,其中實(shí)時(shí)圖從基準(zhǔn)圖中裁剪,并經(jīng)過(guò)模糊、加噪等處理后獲得。實(shí)驗(yàn)分別在PC(CPU 雙核3.2 GHz,內(nèi)存4 G,Matlab實(shí)現(xiàn))和DSP(TI公司的TMDS EVM6678L DSP評(píng)估板)上進(jìn)行,所用時(shí)間統(tǒng)計(jì)如表 1所示,而DSP實(shí)時(shí)匹配效果如圖6和圖7所示。
由表1統(tǒng)計(jì)結(jié)果可知,這篇文章提出的基于多核DSP的圖像實(shí)時(shí)相關(guān)匹配設(shè)計(jì)很好的解決了以往圖像相關(guān)匹配處理速度慢的問(wèn)題,能夠滿(mǎn)足高實(shí)時(shí)處理要求。同時(shí),圖 6和圖 7的匹配結(jié)果表明,該設(shè)計(jì)方法在降低處理時(shí)間的同時(shí)可以保證匹配的準(zhǔn)確性。
圖6 相關(guān)匹配實(shí)驗(yàn)結(jié)果圖1
圖7 相關(guān)匹配實(shí)驗(yàn)結(jié)果圖2
表1 相關(guān)匹配運(yùn)行時(shí)間比較
針對(duì)圖像相關(guān)匹配計(jì)算量大,匹配速度慢,難以實(shí)時(shí)處理實(shí)現(xiàn)的缺點(diǎn),這篇文章基于多核DSP提出了一種圖像實(shí)時(shí)相關(guān)匹配方法。該方法采用了并行處理設(shè)計(jì)和算法優(yōu)化設(shè)計(jì),提高了相關(guān)匹配的處理速度。實(shí)驗(yàn)結(jié)果表明,較傳統(tǒng)相關(guān)匹配方法而言,該方法顯著降低了相關(guān)匹配的處理時(shí)間,能有效完成圖像相關(guān)匹配的實(shí)時(shí)處理,同時(shí)又保證了匹配的準(zhǔn)確性,可應(yīng)用于對(duì)處理有高實(shí)時(shí)性要求的軍事領(lǐng)域中,如精確制導(dǎo)武器系統(tǒng)、飛機(jī)輔助導(dǎo)航等。
[1] 楊小岡,繆棟,曹菲.一種實(shí)用的景象匹配仿真方法[J].系統(tǒng)仿真學(xué)報(bào),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ù)字信號(hào)處理平臺(tái)的設(shè)計(jì)與實(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滿(mǎn)足高性能計(jì)算[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].單片機(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í)時(shí)多任務(wù)調(diào)度內(nèi)核設(shè)計(jì)[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í)時(shí)匹配系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].電子測(cè)量與儀器學(xué)報(bào),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—),男,工程師,主要研究方向?yàn)榫_制導(dǎo)技術(shù)以及DSP實(shí)現(xiàn)。
10.3969/j.issn.1002-0802.2015.04.023
2014-10-20;
2015-02-17