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

1、    圖像匹配最大互相關(guān)算法的專用ASIC硬件實現(xiàn)方法研究        張遂南 黃士坦 時間:2009年01月19日     字 體: 大 中 小        關(guān)鍵詞:<"cblue" " target='_blank'>圖像匹配<"cblue" " targ

2、et='_blank'>最大<"cblue" " target='_blank'>圖像數(shù)據(jù)<"cblue" " target='_blank'>硬件實現(xiàn)<"cblue" " target='_blank'>實時性            ? 摘? 要: 探討一種專用ASIC<&q

3、uot;cblue" " title="硬件實現(xiàn)">硬件實現(xiàn)方法，這種方法將DSP的靈活性與ASIC的高效性相結(jié)合，構(gòu)造了單DSP+多ASIC的嵌入式計算機，對<"cblue" " title="圖像匹配">圖像匹配獲得了滿意的效果。并由此提出了更高性能的硬件實現(xiàn)結(jié)構(gòu)。? 關(guān)鍵詞: 圖像匹配? <"cblue" " title="最大">最大互相關(guān)? 硬件實現(xiàn)?圖像匹配是把從同一景物利用兩個不同的傳感器錄取下來的兩幅灰度圖像在

4、空間上進行對準，以確定兩幅圖像之間相對偏移的過程，通常是在已知的M×M個象素的光學或雷達基準圖中尋找N×N個象素的實時圖像的匹配位置。圖像匹配是計算機圖像科學的一種基本處理方法，在飛行器導航、目標跟蹤、資源分析、文字識別等領(lǐng)域中具有極其重要的作用。這些高科技領(lǐng)域往往要求極高的<"cblue" " title="實時性">實時性，而且要求運算速度要高達每秒幾億甚至10億次操作以上。圖像匹配的運算量非常大，如對較小的36×36的實時圖和150×150的基準圖，采用最大互相關(guān)算法進行全搜索圖像匹配，

5、它的運算量(約與(M-N+1)2×N2成正比)高達1714萬次乘法和1714萬次加法以上(不計對基準圖數(shù)據(jù)預處理運算次數(shù))。這些特點使一般的單CPU計算機結(jié)構(gòu)難以甚至無法滿足要求，特別是在航空航天等高惡劣環(huán)境的嵌入式應用中，更是無法滿足高可靠性要求，因而必須采用高速靈活的計算機結(jié)構(gòu)，才可能滿足上述的要求。圖像匹配一般可采用如下幾種方法實現(xiàn):軟件;高速DSP;面向算法的專用ASIC器件。軟件方法靈活，可大大降低計算量，但它必須以高速DSP硬件平臺為基礎，才可能滿足高實時性要求;高速DSP方法簡單靈活，能夠滿足高實時性要求，如TI公司的TMS320C6X系列高速DSP芯片，速度高達160

6、0MIPS4，單芯片就可實現(xiàn)高速實時處理系統(tǒng)。以這些高速DSP芯片組成的硬件結(jié)構(gòu)應是圖像匹配計算機首選的硬件實現(xiàn)結(jié)構(gòu)。但對應用于尖端科技的這些高速DSP芯片，西方發(fā)達國家對我國采取禁售策略，這使我國的某些科技領(lǐng)域受到很大的制約，因此在我國必須另辟途徑以避免禁售策略的制約。面向算法的專用ASIC器件方法，采用大量的并行功能單元，速度高、可以滿足嵌入式應用中的高速實時計算要求，而且結(jié)構(gòu)簡單、軟件編程簡單、硬件實現(xiàn)容易、體積小、成本低，特別適應我國國情。因此開發(fā)研究以專用ASIC組成的高速圖像匹配計算機硬件實現(xiàn)結(jié)構(gòu)具有重要的意義。從圖像匹配整個過程來看，雖然它具有非常大的運算量，但是它的運算主要為大

7、量重復進行的乘法和加法運算，這就使它具有高度并行性、簡單性和重復性的特點。例如圖1(每一方格代表一8位灰度<"cblue" " title="圖像數(shù)據(jù)">圖像數(shù)據(jù))各對象素之間的計算以及各組子圖之間的計算均沒有結(jié)果的依賴性，這些特點使它非常適合于采用流水并行技術(shù)的ASIC電路。同時，圖像匹配理論和計算機并行結(jié)構(gòu)理論以及超大規(guī)模集成電路VLSI技術(shù)的飛速發(fā)展也為圖像匹配的專用硬件實現(xiàn)方法提供了理論和物質(zhì)基礎，使圖像匹配的高實時性能夠進一步得到提高。?1 圖像匹配最大互相關(guān)算法分析基于灰度的圖像匹配算法有許多種，其中最基本的有最小絕對差

8、算法、最小平方差算法、最小卷積算法、最大互相關(guān)算法、不變矩算法等十幾種。它們各有優(yōu)缺點，其中最大互相關(guān)算法具有去直流噪聲、匹配位置準確等特點，因而成為圖像匹配采用的主要方法。它的原始公式為:由于原始公式中的變量X(i，j)，Y(i+u，j+v)為去均值后的圖像數(shù)據(jù)，不是原始圖像象素數(shù)據(jù)，這樣的算法結(jié)構(gòu)數(shù)據(jù)有正有負、中間結(jié)果量多、計算量大、規(guī)律性差，不利于專用硬件實現(xiàn)3，因此必須對原始公式進行變換。把(2)和(3)式代入原始公式(1)中，變換后的公式為:由于在圖像匹配搜索過程中基準圖是已知的，可預先對基準圖子圖數(shù)據(jù)進行均值和平方均值計算，然后預先裝配在相關(guān)計算機上。在圖像匹配過程中可不記其所需時

9、間，因此圖像匹配所需時間主要為求實時圖數(shù)據(jù)和基準子圖數(shù)據(jù)的卷積。這一結(jié)論也可通過實際圖像匹配運算得到。在TI公司TMS320C30DSP(33M)上， 采用公式(4)對不同象素數(shù)的實時圖和參考圖進行全搜索圖像匹配，其運算時間如表1所示(匯編程序、程序放置在片內(nèi)存儲器，數(shù)據(jù)放置在片外零等待存儲器)。從表1可看出，圖像匹配的最大互相關(guān)算法主要歸結(jié)為卷積運算，因此采用專用的硬件卷積電路必將大大加快圖像匹配運算速度。?2 以TMS320C30和專用ASIC器件LS9501組成的圖像匹配計算機結(jié)構(gòu)介紹2.1 專用圖像匹配器件LS9501介紹LS95012是西安微電子技術(shù)研究所根據(jù)圖像匹配的特點研制成功的

10、一個高速(20M)二維具有3×3內(nèi)核的卷積器，它的主要功能是可同時對9對象素值實現(xiàn)乘加運算， 即實現(xiàn):LS9501的輸入是二維無符號8位的圖像數(shù)據(jù)，輸出是無符號20位卷積結(jié)果和二維串行移位無符號8位的圖像數(shù)據(jù)。其內(nèi)部結(jié)構(gòu)采用流水線并行技術(shù)，主要的功能單元有寄存器組、快速乘法器、加法器和控制電路，如圖2所示。電路中設置的兩組寄存器A和B由9個8位的移位寄存器構(gòu)成，可存放9個圖像象素數(shù)據(jù)。9個快速乘法器可保證在每一個時鐘內(nèi)同時進行9對圖像數(shù)據(jù)相乘。其工作原理為:向A寄存器輸入9個實時圖象素數(shù)據(jù)后，再向B寄存器輸入九個基準圖像素數(shù)據(jù)，當9對象素值輸入完后，經(jīng)過一定時間延遲，即可得到卷積結(jié)果

11、。此后，如A寄存器的數(shù)據(jù)不變，B寄存器繼續(xù)輸入數(shù)據(jù)，則每輸入一個數(shù)據(jù)，即可獲得一個9個圖像象素數(shù)據(jù)卷積結(jié)果。如果將多個LS9501卷積器級連起來，可實現(xiàn)更多對象素數(shù)據(jù)的卷積運算。例如，將4個LS9501級連，可實現(xiàn)36對象素數(shù)據(jù)的卷積，但要將4個卷積器的結(jié)果加起來，才能得到最后的結(jié)果。為此，西安微電子技術(shù)研究所研制了級連加法器LS9502，它的功能是在60ns內(nèi)將4個LS9501的輸出結(jié)果求和。?3 圖像匹配計算機結(jié)構(gòu)將4個卷積器LS9501和級連加法器LS9502組合起來作為TMS320C30數(shù)字信號處理器的快速協(xié)處理器部件，可組成一種高速的單DSP+多ASIC系統(tǒng)結(jié)構(gòu)的嵌入式計算機，如圖3

12、所示。其工作過程為:首先TMS320C30按一定次序把36個實時圖象素數(shù)據(jù)從實時圖存儲器中取出并輸入LS9501的A寄存器中，然后，從基準圖存儲器中將基準圖像素數(shù)據(jù)輸入B寄存器。輸入36個基準圖像素數(shù)據(jù)后，經(jīng)過一定時間延遲，即可讀出第一個36對圖像象素數(shù)據(jù)卷積結(jié)果。此后即建立起流水，每輸入一個基準圖數(shù)據(jù)可得到相應36對圖像象素數(shù)據(jù)卷積結(jié)果，直至對整個基準圖匹配計算完。當實時圖比較大時，可把實時圖分成若干子圖，然后對每一個子圖分別進行卷積運算，最后再把它們的結(jié)果加在一起。這樣，工作量最大的匹配計算任務由LS9501完成，TMS320C30將各子圖匹配結(jié)果進行累加，求最大互相關(guān)值，并對卷積器控制輸

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

14、算時間)。?從表2可看出，采用專用集成電路LS9501可大大加快圖像匹配運算速度，而且編程比較簡單，實現(xiàn)容易，實測結(jié)果是令人滿意的。? 本研究為國家“九五”預研項目“高速數(shù)字信號處理機技術(shù)”的一部分，已通過國家驗收，并已應用于高速圖像相關(guān)計算機中。這一研究的成功使我們看到了打破西方禁售策略的一種簡單可行的方法。在實驗中我們發(fā)現(xiàn)LS9501具有非常大的提高其實時性的潛力，現(xiàn)分析如下:在實驗中發(fā)現(xiàn)，LS9501內(nèi)部圖像數(shù)據(jù)移位寄存器時鐘和3級加法器寄存器時鐘不為同一時鐘，這使得卷積模塊的并行效率大為降低。如果將其改進為同一時鐘，那么在圖3所示單機系統(tǒng)結(jié)構(gòu)中，對(36×36)實時圖與(12

15、8×128)或(150×150)基準圖圖像匹配時間將分別為394ms和592ms，圖像匹配速度提高約1倍(軟件模擬)。另外在實驗的單機系統(tǒng)結(jié)構(gòu)中，卷積模塊完全靠TMS320C30控制，其時鐘輸入依賴TMS320C30讀寫信號，而且TMS320C30對外部存儲器連讀時讀寫信號不變化1，必須加NOP指令以使讀寫信號變化。這樣LS9501的性能沒有得到完全發(fā)揮，而且TMS320C30也不能處理其它任務，二者依賴性太大，相互制約，并行度和實時性難以得到提高。卷積模塊發(fā)展為智能卷積處理器，那么硬件結(jié)構(gòu)可發(fā)展為主從式雙機計算機系統(tǒng)結(jié)構(gòu):主機為DSP，從機為卷積處理器。這種系統(tǒng)結(jié)構(gòu)可使DSP與卷積器的依賴性降到最低，提高任務級并行性，也可最大發(fā)揮LS9501的性能，從而提高圖像匹配的速度。在不增加單芯片實現(xiàn)的卷積規(guī)模條件下，開發(fā)更高速度的LS9501，同樣可提高圖像匹配的速度。不容質(zhì)疑，提高單芯片實現(xiàn)的卷積規(guī)模必將較大地提高圖像匹配的速度。由實驗結(jié)構(gòu)及以上分析可以預見，圖像匹配最大互相關(guān)的專用ASIC實現(xiàn)方法是一個簡單可行的方法，并具有很好的發(fā)展前景，完全可以開發(fā)體積小、成本低、速度與TI公司C60