圖像匹配最大互相關(guān)算法的專用ASIC硬件實(shí)現(xiàn)方式研究

1、歡迎訪問Freekaoyan論文站圖像匹配最大互相關(guān)算法的專用ASIC硬件實(shí)現(xiàn)方式研究歡迎訪問Freekaoyan論文站    歡迎訪問Freekaoyan論文站    摘要：探討一種專用ASIC硬件實(shí)現(xiàn)方法，這種方法將DSP的靈活性與ASIC的高效性相結(jié)合，構(gòu)造了單DSP+多ASIC的嵌入式計(jì)算機(jī)，對圖像匹配獲得了滿意的效果。并由此提出了更高性能的硬件實(shí)現(xiàn)結(jié)構(gòu)。     圖像匹配是把從同一景物利用兩個(gè)不同的傳感器錄取下來的兩幅灰度圖像在空間上進(jìn)行對準(zhǔn)，以確定兩幅圖像之間相對偏移的過程

2、，通常是在已知的MxM個(gè)象素的光學(xué)或雷達(dá)基準(zhǔn)圖中尋找NxN個(gè)象素的實(shí)時(shí)圖像的匹配位置。圖像匹配是計(jì)算機(jī)圖像科學(xué)的一種基本處理方法，在飛行器導(dǎo)航、目標(biāo)跟蹤、資源分析、文字識(shí)別等領(lǐng)域中具有極其重要的作用。這些高科技領(lǐng)域往往要求極高的實(shí)時(shí)性，而且要求運(yùn)算速度要高達(dá)每秒幾億甚至10億次操作以上。圖像匹配的運(yùn)算量非常大，如對較小的36x36的實(shí)時(shí)圖和150x150的基準(zhǔn)圖，采用最大互相關(guān)算法進(jìn)行全搜索圖像匹配，它的運(yùn)算量（約與（M-N+1）2xN2成正比）高達(dá)1714萬次乘法和1714萬次加法以上（不計(jì)對基準(zhǔn)圖數(shù)據(jù)預(yù)處理運(yùn)算次數(shù)）。這些特點(diǎn)使一般的基準(zhǔn)圖數(shù)據(jù)預(yù)處理運(yùn)算次數(shù)）。這些特點(diǎn)使一般的單CPU計(jì)算

3、機(jī)結(jié)構(gòu)難以甚至無法滿足要求，特別是在航空航天等高惡劣環(huán)境的嵌入式應(yīng)用中，更是無法滿足高可靠性要求，因而必須采用高速靈活的計(jì)算機(jī)結(jié)構(gòu)，才能可滿足上述的要求。    圖像匹配一般可采用如下幾種方式實(shí)現(xiàn)：軟件；高速DSP；面向算法的專用ASIC器件。軟件方法靈活，可大大降低計(jì)算量，但它必須以高速DSP硬件平臺(tái)為基礎(chǔ)，才可能滿足高實(shí)時(shí)性要求；高速DSP方法簡單靈活，能夠滿足高實(shí)時(shí)性要求，如TI公司的TMS320C6X系列高速DSP芯片，速度高達(dá)1600MIPS4，單片機(jī)就可實(shí)現(xiàn)高速實(shí)時(shí)處理系統(tǒng)。以這高速DSP芯片組成的硬件結(jié)構(gòu)應(yīng)是圖像匹配計(jì)算機(jī)首選的硬件實(shí)現(xiàn)結(jié)構(gòu)。但對應(yīng)用

4、于尖端科技的這些高速DSP芯片，西文發(fā)達(dá)國家對我國采取禁售策略，這使我國的某些科技領(lǐng)域受到很大的制約，因此在我國必須另辟途徑以避免禁售策略的制約。面向算法的專用ASIC器件方法，采用大量的并行功能單元，速度高、可以滿足嵌入式應(yīng)用中的高速實(shí)時(shí)計(jì)算要求，而且結(jié)構(gòu)簡單、軟件編程簡單、硬件實(shí)現(xiàn)容易、體積小、成本低，特別適應(yīng)我國國情。因此開發(fā)研究專用ASIC組成的高速圖像匹配計(jì)算機(jī)實(shí)現(xiàn)結(jié)構(gòu)具有重要的意義。    從圖像匹配整個(gè)過程來看，雖然它具有非常大的運(yùn)算量，但是它的運(yùn)算主要為大量重復(fù)進(jìn)行的乘法和加法運(yùn)算，這就使它具有高度并行性、簡單笥和重復(fù)性的特點(diǎn)。例如圖1（每一方格代

5、表一8位灰度圖像數(shù)據(jù)）各對象素之間的計(jì)算以及各組子圖之間的計(jì)算均沒有結(jié)果的依賴性，這些特點(diǎn)使它非常適合于采用流水并行技術(shù)的ASIC電路。同時(shí)，圖像匹配理論和諸機(jī)并行結(jié)構(gòu)理論以及超大規(guī)模集成電路VLSI技術(shù)的飛速發(fā)展也為圖像匹配的專用硬件實(shí)現(xiàn)方法提供了理論和物質(zhì)基礎(chǔ)，使圖像匹配的高實(shí)時(shí)性能夠進(jìn)一步得到提高。1 圖像匹配最大互相關(guān)算法分析    基于灰度的圖像匹配算法有許多種，其中最基本的有最小絕對差算法、最小平方差算法，最小卷積算法、最大互相關(guān)算法、不變矩算法等十幾種。它們各有優(yōu)缺點(diǎn)，其中最大互相關(guān)算法具有去直流噪聲、匹配位置準(zhǔn)確等特點(diǎn)，因而成為圖像匹配采用的主要方

6、法。它的原始公式為：    由于原始公式中的變量X（i,j）,Y(i+u,j+v)為去均值后的圖像數(shù)據(jù)，不是原始圖像象素?cái)?shù)據(jù)，這樣的算法結(jié)構(gòu)有正有負(fù)、中間結(jié)果量多、計(jì)算量大、規(guī)律性差，不利于專用硬件實(shí)現(xiàn)3，因此必須對原始公式進(jìn)行變換。把（2）和（3）式代入原始公式（1）中，變換后的公式為：    由于在圖像匹配搜索過程中基準(zhǔn)圖是已知的，可預(yù)先對基準(zhǔn)圖子圖數(shù)據(jù)進(jìn)行均值和平方均值計(jì)算，然后預(yù)先裝配在相關(guān)計(jì)算機(jī)上。在圖像匹配過程中可不記其所需時(shí)間，因此圖像匹配所需時(shí)間主要為求實(shí)時(shí)圖數(shù)據(jù)和基準(zhǔn)子圖數(shù)據(jù)的卷積。這一結(jié)論也可通過實(shí)際圖像匹配運(yùn)算得

7、到。在TI公司TMS320C30DSP（33M）上，采用公式（4）對不同象素?cái)?shù)的實(shí)時(shí)圖和參考圖進(jìn)行全搜索圖像匹配，其運(yùn)算時(shí)間如表1所示（匯編程序、程序放置在片內(nèi)存儲(chǔ)器，數(shù)據(jù)片外零等待存儲(chǔ)器）。    從表1可看出，圖像匹配的最大互相關(guān)算法主要?dú)w結(jié)為卷積運(yùn)算，因此采用專用的硬件卷積電路必將大大加快圖像匹配運(yùn)算速度。表1 采用互相變換公式圖象匹配運(yùn)算周期數(shù)和時(shí)間項(xiàng)  目公式（4）公式(4)鄭項(xiàng)所占比例實(shí)時(shí)圖參考圖總運(yùn)算周期數(shù)卷積項(xiàng)周期數(shù)約需時(shí)間（ms）36×36128×1285144381051354910308199.83%64

8、5;64128×1288936299289308446536299.93%36×36150×1507742325277291458464599.83%64×64150×150160078800159994050960599.95%2 以TMS320C30和專用ASIC器件LS9501組成的圖像匹配計(jì)算機(jī)結(jié)構(gòu)介紹2.1 專用圖像匹配器件LS9501介紹    LS95012是西安微電子技術(shù)研究所根據(jù)圖像匹配的特點(diǎn)研制成功的一個(gè)高速20M二維具有3x3內(nèi)核的卷積器，它的主要功能是可同時(shí)對9對象素值實(shí)現(xiàn)乘加運(yùn)算，即實(shí)現(xiàn)：

9、。LS9501的輸入是二維無符號(hào)8位的圖像數(shù)據(jù)，輸出是無符號(hào)20位卷結(jié)果和二維串行移位無符號(hào)8位的圖像數(shù)據(jù)。其內(nèi)部結(jié)構(gòu)采用流水線并行技術(shù)，主要的功能單元有寄存器組、快速乘法器、加法器和控制電路，如圖2所示。電路中設(shè)置的兩組寄存器A和B由9個(gè)8位的移位寄存器構(gòu)成，可存放9個(gè)圖像象素?cái)?shù)據(jù)。9個(gè)快速乘法器可保證在每一個(gè)時(shí)鐘內(nèi)同時(shí)進(jìn)行9對圖像數(shù)據(jù)相乘。其工作原理為：向A寄存器輸入9個(gè)實(shí)時(shí)圖象素?cái)?shù)據(jù)后，再向B寄存器輸入入九個(gè)基準(zhǔn)圖像素?cái)?shù)據(jù)，當(dāng)9對象素值輸入完后，經(jīng)過一定時(shí)間延遲，即可得到卷積結(jié)果。此后，如A寄存器的數(shù)據(jù)不變，B寄存器繼續(xù)輸入數(shù)據(jù)，則每輸入一個(gè)數(shù)據(jù)，即可獲得一個(gè)9個(gè)圖像象素?cái)?shù)據(jù)卷積結(jié)果。如

10、果將多個(gè)LS9501卷積器級(jí)連起來，可實(shí)現(xiàn)更多對象素?cái)?shù)據(jù)的卷積運(yùn)算。例如，將4個(gè)LS9501級(jí)連，可實(shí)現(xiàn)36對象素?cái)?shù)據(jù)的卷積，但要將4個(gè)卷積器的結(jié)果加起來，才能得到最后的結(jié)果。為此，西安微電子技術(shù)研究所研制了級(jí)連加法器LS9502，它的功能是在60ns內(nèi)將4LS9501的輸出結(jié)果求和。3 圖像匹配計(jì)算機(jī)結(jié)構(gòu)    將4個(gè)卷積器LS8501和級(jí)連加法器LS9501組合起來作為TMS320C30數(shù)字信號(hào)處理器的快速協(xié)處理器部件，可組成一種高速的單DSP+多ASIC系統(tǒng)結(jié)構(gòu)的嵌入式計(jì)算機(jī)，如圖3所示。其工作過程為：首先TMS320C30按一定次序把36個(gè)實(shí)時(shí)圖象素?cái)?shù)據(jù)從

11、實(shí)時(shí)圖存儲(chǔ)器中取出并輸入LS9501的A寄存器中，然后，從基準(zhǔn)圖存儲(chǔ)中將基準(zhǔn)圖像素?cái)?shù)據(jù)輸入B寄存器。輸入36個(gè)基準(zhǔn)圖像素?cái)?shù)據(jù)后，經(jīng)過一定時(shí)間延遲，即可讀出第一個(gè)36對圖像象素?cái)?shù)據(jù)卷積結(jié)果。此后即建立起流水，每輸入一個(gè)基準(zhǔn)圖數(shù)據(jù)可得到相應(yīng)36對圖像象素?cái)?shù)據(jù)卷積結(jié)果，直至對整個(gè)基準(zhǔn)圖匹配計(jì)算完。當(dāng)實(shí)時(shí)圖比較大時(shí)，可把實(shí)時(shí)圖分成若干子圖，然后對每一個(gè)子圖分別進(jìn)行卷積運(yùn)算，最后再把它們的結(jié)果加在一起。這樣，工作量最大的匹配計(jì)算任務(wù)由LS8501完成，TMS320C30將各個(gè)圖匹配結(jié)果進(jìn)行累加，求最大互相關(guān)值，并對卷器控制輸入8位灰度圖像數(shù)據(jù)。4 圖像匹配結(jié)果與討論   

12、在上述圖像匹配計(jì)算機(jī)中，采用美國TI公司的TMS320C30（33M）DSP芯片主為處理器，4片關(guān)并行的LS9501和級(jí)連加法器LS9502組成圖像匹配協(xié)處理器，外部圖像存儲(chǔ)器讀寫為零等待狀態(tài)。根據(jù)組成的計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)，把36x36的實(shí)時(shí)圖分成36個(gè)4x9的子圖，然后計(jì)算每一子圖與相應(yīng)基準(zhǔn)圖子圖卷積，最后把各個(gè)子圖卷積結(jié)果累加在一起。通過編寫TMS320C30匯編程序，對不同大小實(shí)時(shí)圖和基準(zhǔn)圖進(jìn)行搜索（即匹配所有（M-N+1）2個(gè)子圖）最大互相差匹配運(yùn)算，運(yùn)算結(jié)果匹配位置正確。匹配運(yùn)算時(shí)間如表2所示（對基準(zhǔn)圖像素?cái)?shù)據(jù)預(yù)處理，不計(jì)運(yùn)算時(shí)間）。表2 實(shí)時(shí)圖和基準(zhǔn)圖匹配運(yùn)算時(shí)間圖像大小運(yùn)算時(shí)間/ms

13、實(shí)時(shí)較基準(zhǔn)圖由單DSP執(zhí)行由DSP+ABIC執(zhí)行36×36128×128308162336×36150×1504645946    從表2可看出，采用專用集成電路LS9501可大大加快圖像匹配運(yùn)算速度，而且編程比較簡單，實(shí)現(xiàn)容易，實(shí)測結(jié)果令人滿意的。    本研究為國家“九五”預(yù)研項(xiàng)目“高速數(shù)字信號(hào)處理機(jī)技術(shù)”的一部分，已通過國家驗(yàn)收，并已應(yīng)用于高速圖像相關(guān)計(jì)算機(jī)中。這一研究的成功使我們看到了打破西方禁售策略的一種簡單可行的方法。在實(shí)驗(yàn)中我們發(fā)現(xiàn)LS9501具有非常大的提高其實(shí)時(shí)性的潛力，現(xiàn)分析

14、如下：    在實(shí)驗(yàn)中發(fā)現(xiàn)，LS9501內(nèi)部圖像數(shù)據(jù)移位寄存器時(shí)鐘和3級(jí)加法器寄存器時(shí)鐘不為同一時(shí)鐘，這使得卷積模塊的并行效率大為降低。如果將其改進(jìn)為同一時(shí)鐘，那篤在圖3所示單機(jī)系統(tǒng)結(jié)構(gòu)中，對（36x36）實(shí)時(shí)圖與（128x128）或（150x150）基準(zhǔn)圖圖像匹配時(shí)間將分別為394ms和592ms，圖像匹配速度提高約1倍（軟件模擬）。另外在實(shí)驗(yàn)的單機(jī)系統(tǒng)結(jié)構(gòu)中，卷積模塊完全靠TMS320C30控制，其時(shí)鐘輸入依賴TMS320C30讀寫信號(hào)，而且TMS329C30對外部存儲(chǔ)器連續(xù)時(shí)讀寫信號(hào)不變化1，必須加NOP指令以使讀寫信號(hào)變化。這樣LS9501的性能沒有得到完全發(fā)揮，而且TMS320C30也不能處理其它任務(wù)，二者依賴性太大，相互制約，并行度和實(shí)時(shí)性難以得到提高。卷積模塊發(fā)展為智能卷積處理器，那么硬件結(jié)構(gòu)右發(fā)展為主從式雙機(jī)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)：主機(jī)為DSP，從機(jī)為卷積處理器。這種系統(tǒng)結(jié)構(gòu)可使DSP與卷積器的依賴 性降到最低，提高任務(wù)級(jí)并行性，也可最大限揮LS9501的性能，從而提高圖像匹配的速度。在不增加