圖像匹配最大互相關(guān)算法的專(zhuān)用ASIC硬件實(shí)現方式研究
摘要:探討一種專(zhuān)用ASIC硬件實(shí)現方法,這種方法將DSP的靈活性與ASIC的高效性相結合,構造了單DSP+多ASIC的嵌入式計算機,對圖像匹配獲得了滿(mǎn)意的效果。并由此提出了更高性能的硬件實(shí)現結構。
本文引用地址:http://dyxdggzs.com/article/241610.htm關(guān)鍵詞:圖像匹配 最大互相關(guān) 硬件實(shí)現
圖像匹配是把從同一景物利用兩個(gè)不同的傳感器錄取下來(lái)的兩幅灰度圖像在空間上進(jìn)行對準,以確定兩幅圖像之間相對偏移的過(guò)程,通常是在已知的MxM個(gè)象素的光學(xué)或雷達基準圖中尋找NxN個(gè)象素的實(shí)時(shí)圖像的匹配位置。圖像匹配是計算機圖像科學(xué)的一種基本處理方法,在飛行器導航、目標跟蹤、資源分析、文字識別等領(lǐng)域中具有極其重要的作用。這些高科技領(lǐng)域往往要求極高的實(shí)時(shí)性,而且要求運算速度要高達每秒幾億甚至10億次操作以上。圖像匹配的運算量非常大,如對較小的36x36的實(shí)時(shí)圖和150x150的基準圖,采用最大互相關(guān)算法進(jìn)行全搜索圖像匹配,它的運算量(約與(M-N+1)2xN2成正比)高達1714萬(wàn)次乘法和1714萬(wàn)次加法以上(不計對基準圖數據預處理運算次數)。這些特點(diǎn)使一般的基準圖數據預處理運算次數)。這些特點(diǎn)使一般的單CPU計算機結構難以甚至無(wú)法滿(mǎn)足要求,特別是在航空航天等高惡劣環(huán)境的嵌入式應用中,更是無(wú)法滿(mǎn)足高可靠性要求,因而必須采用高速靈活的計算機結構,才能可滿(mǎn)足上述的要求。
圖像匹配一般可采用如下幾種方式實(shí)現:①軟件;②高速DSP;③面向算法的專(zhuān)用ASIC器件。軟件方法靈活,可大大降低計算量,但它必須以高速DSP硬件平臺為基礎,才可能滿(mǎn)足高實(shí)時(shí)性要求;高速DSP方法簡(jiǎn)單靈活,能夠滿(mǎn)足高實(shí)時(shí)性要求,如TI公司的TMS320C6X系列高速DSP芯片,速度高達1600MIPS[4],單片機就可實(shí)現高速實(shí)時(shí)處理系統。以這高速DSP芯片組成的硬件結構應是圖像匹配計算機首選的硬件實(shí)現結構。但對應用于尖端科技的這些高速DSP芯片,西文發(fā)達國家對我國采取禁售策略,這使我國的某些科技領(lǐng)域受到很大的制約,因此在我國必須另辟途徑以避免禁售策略的制約。面向算法的專(zhuān)用ASIC器件方法,采用大量的并行功能單元,速度高、可以滿(mǎn)足嵌入式應用中的高速實(shí)時(shí)計算要求,而且結構簡(jiǎn)單、軟件編程簡(jiǎn)單、硬件實(shí)現容易、體積小、成本低,特別適應我國國情。因此開(kāi)發(fā)研究專(zhuān)用ASIC組成的高速圖像匹配計算機實(shí)現結構具有重要的意義。
從圖像匹配整個(gè)過(guò)程來(lái)看,雖然它具有非常大的運算量,但是它的運算主要為大量重復進(jìn)行的乘法和加法運算,這就使它具有高度并行性、簡(jiǎn)單笥和重復性的特點(diǎn)。例如圖1(每一方格代表一8位灰度圖像數據)各對象素之間的計算以及各組子圖之間的計算均沒(méi)有結果的依賴(lài)性,這些特點(diǎn)使它非常適合于采用流水并行技術(shù)的ASIC電路。同時(shí),圖像匹配理論和諸機并行結構理論以及超大規模集成電路VLSI技術(shù)的飛速發(fā)展也為圖像匹配的專(zhuān)用硬件實(shí)現方法提供了理論和物質(zhì)基礎,使圖像匹配的高實(shí)時(shí)性能夠進(jìn)一步得到提高。
1 圖像匹配最大互相關(guān)算法分析
基于灰度的圖像匹配算法有許多種,其中最基本的有最小絕對差算法、最小平方差算法,最小卷積算法、最大互相關(guān)算法、不變矩算法等十幾種。它們各有優(yōu)缺點(diǎn),其中最大互相關(guān)算法具有去直流噪聲、匹配位置準確等特點(diǎn),因而成為圖像匹配采用的主要方法。它的原始公式為:
由于原始公式中的變量X(i,j),Y(i+u,j+v)為去均值后的圖像數據,不是原始圖像象素數據,這樣的算法結構有正有負、中間結果量多、計算量大、規律性差,不利于專(zhuān)用硬件實(shí)現[3],因此必須對原始公式進(jìn)行變換。把(2)和(3)式代入原始公式(1)中,變換后的公式為:
由于在圖像匹配搜索過(guò)程中基準圖是已知的,可預先對基準圖子圖數據進(jìn)行均值和平方均值計算,然后預先裝配在相關(guān)計算機上。在圖像匹配過(guò)程中可不記其所需時(shí)間,因此圖像匹配所需時(shí)間主要為求實(shí)時(shí)圖數據和基準子圖數據的卷積。這一結論也可通過(guò)實(shí)際圖像匹配運算得到。在TI公司TMS320C30DSP(33M)上,采用公式(4)對不同象素數的實(shí)時(shí)圖和參考圖進(jìn)行全搜索圖像匹配,其運算時(shí)間如表1所示(匯編程序、程序放置在片內存儲器,數據片外零等待存儲器)。
從表1可看出,圖像匹配的最大互相關(guān)算法主要歸結為卷積運算,因此采用專(zhuān)用的硬件卷積電路必將大大加快圖像匹配運算速度。
表1 采用互相變換公式圖象匹配運算周期數和時(shí)間
項 目 | 公式(4) | 公式(4)鄭項所占比例 | |||
實(shí)時(shí)圖 | 參考圖 | 總運算周期數 | 卷積項周期數 | 約需時(shí)間(ms) | |
36×36 | 128×128 | 51443810 | 51354910 | 3081 | 99.83% |
64×64 | 128×128 | 89362992 | 89308446 | 5362 | 99.93% |
36×36 | 150×150 | 77423252 | 77291458 | 4645 | 99.83% |
64×64 | 150×150 | 160078800 | 159994050 | 9605 | 99.95% |
2 以TMS320C30和專(zhuān)用ASIC器件LS9501組成的圖像匹配計算機結構介紹
2.1 專(zhuān)用圖像匹配器件LS9501介紹
LS9501[2]是西安微電子技術(shù)研究所根據圖像匹配的特點(diǎn)研制成功的一個(gè)高速[20M]二維具有3x3內核的卷積器,它的主要功能是可同時(shí)對9對象素值實(shí)現乘加運算,即實(shí)現:。LS9501的輸入是二維無(wú)符號8位的圖像數據,輸出是無(wú)符號20位卷結果和二維串行移位無(wú)符號8位的圖像數據。其內部結構采用流水線(xiàn)并行技術(shù),主要的功能單元有寄存器組、快速乘法器、加法器和控制電路,如圖2所示。電路中設置的兩組寄存器A和B由9個(gè)8位的移位寄存器構成,可存放9個(gè)圖像象素數據。9個(gè)快速乘法器可保證在每一個(gè)時(shí)鐘內同時(shí)進(jìn)行9對圖像數據相乘。其工作原理為:向A寄存器輸入9個(gè)實(shí)時(shí)圖象素數據后,再向B寄存器輸入入九個(gè)基準圖像素數據,當9對象素值輸入完后,經(jīng)過(guò)一定時(shí)間延遲,即可得到卷積結果。此后,如A寄存器的數據不變,B寄存器繼續輸入數據,則每輸入一個(gè)數據,即可獲得一個(gè)9個(gè)圖像象素數據卷積結果。如果將多個(gè)LS9501卷積器級連起來(lái),可實(shí)現更多對象素數據的卷積運算。
例如,將4個(gè)LS9501級連,可實(shí)現36對象素數據的卷積,但要將4個(gè)卷積器的結果加起來(lái),才能得到最后的結果。為此,西安微電子技術(shù)研究所研制了級連加法器LS9502,它的功能是在60ns內將4LS9501的輸出結果求和。
3 圖像匹配計算機結構
將4個(gè)卷積器LS8501和級連加法器LS9501組合起來(lái)作為T(mén)MS320C30數字信號處理器的快速協(xié)處理器部件,可組成一種高速的單DSP+多ASIC系統結構的嵌入式計算機,如圖3所示。其工作過(guò)程為:首先TMS320C30按一定次序把36個(gè)實(shí)時(shí)圖象素數據從實(shí)時(shí)圖存儲器中取出并輸入LS9501的A寄存器中,然后,從基準圖存儲中將基準圖像素數據輸入B寄存器。輸入36個(gè)基準圖像素數據后,經(jīng)過(guò)一定時(shí)間延遲,即可讀出第一個(gè)36對圖像象素數據卷積結果。此后即建立起流水,每輸入一個(gè)基準圖數據可得到相應36對圖像象素數據卷積結果,直至對整個(gè)基準圖匹配計算完。當實(shí)時(shí)圖比較大時(shí),可把實(shí)時(shí)圖分成若干子圖,然后對每一個(gè)子圖分別進(jìn)行卷積運算,最后再把它們的結果加在一起。這樣,工作量最大的匹配計算任務(wù)由LS8501完成,TMS320C30將各個(gè)圖匹配結果進(jìn)行累加,求最大互相關(guān)值,并對卷器控制輸入8位灰度圖像數據。
4 圖像匹配結果與討論
在上述圖像匹配計算機中,采用美國TI公司的TMS320C30(33M)DSP芯片主為處理器,4片關(guān)并行的LS9501和級連加法器LS9502組成圖像匹配協(xié)處理器,外部圖像存儲器讀寫(xiě)為零等待狀態(tài)。根據組成的計算機系統結構,把36x36的實(shí)時(shí)圖分成36個(gè)4x9的子圖,然后計算每一子圖與相應基準圖子圖卷積,最后把各個(gè)子圖卷積結果累加在一起。通過(guò)編寫(xiě)TMS320C30匯編程序,對不同大小實(shí)時(shí)圖和基準圖進(jìn)行搜索(即匹配所有(M-N+1)2個(gè)子圖)最大互相差匹配運算,運算結果匹配位置正確。匹配運算時(shí)間如表2所示(對基準圖像素數據預處理,不計運算時(shí)間)。
表2 實(shí)時(shí)圖和基準圖匹配運算時(shí)間
圖像大小 | 運算時(shí)間/ms | ||
實(shí)時(shí)較 | 基準圖 | 由單DSP執行 | 由DSP+ABIC執行 |
36×36 | 128×128 | 3081 | 623 |
36×36 | 150×150 | 4645 | 946 |
從表2可看出,采用專(zhuān)用集成電路LS9501可大大加快圖像匹配運算速度,而且編程比較簡(jiǎn)單,實(shí)現容易,實(shí)測結果令人滿(mǎn)意的。
本研究為國家“九五”預研項目“高速數字信號處理機技術(shù)”的一部分,已通過(guò)國家驗收,并已應用于高速圖像相關(guān)計算機中。這一研究的成功使我們看到了打破西方禁售策略的一種簡(jiǎn)單可行的方法。在實(shí)驗中我們發(fā)現LS9501具有非常大的提高其實(shí)時(shí)性的潛力,現分析如下:
在實(shí)驗中發(fā)現,LS9501內部圖像數據移位寄存器時(shí)鐘和3級加法器寄存器時(shí)鐘不為同一時(shí)鐘,這使得卷積模塊的并行效率大為降低。如果將其改進(jìn)為同一時(shí)鐘,那篤在圖3所示單機系統結構中,對(36x36)實(shí)時(shí)圖與(128x128)或(150x150)基準圖圖像匹配時(shí)間將分別為394ms和592ms,圖像匹配速度提高約1倍(軟件模擬)。另外在實(shí)驗的單機系統結構中,卷積模塊完全靠TMS320C30控制,其時(shí)鐘輸入依賴(lài)TMS320C30讀寫(xiě)信號,而且TMS329C30對外部存儲器連續時(shí)讀寫(xiě)信號不變化[1],必須加NOP指令以使讀寫(xiě)信號變化。這樣LS9501的性能沒(méi)有得到完全發(fā)揮,而且TMS320C30也不能處理其它任務(wù),二者依賴(lài)性太大,相互制約,并行度和實(shí)時(shí)性難以得到提高。卷積模塊發(fā)展為智能卷積處理器,那么硬件結構右發(fā)展為主從式雙機計算機系統結構:主機為DSP,從機為卷積處理器。這種系統結構可使DSP與卷積器的依賴(lài) 性降到最低,提高任務(wù)級并行性,也可最大限揮LS9501的性能,從而提高圖像匹配的速度。在不增加單芯片實(shí)現的卷積規模條件下,開(kāi)發(fā)更高速度的LS9501,同樣可提高圖像匹配的速度。不容質(zhì)疑,提高單芯片實(shí)現的卷積規模必將較大地提高圖像匹配的速度。
由實(shí)驗結構及以上分析可以預見(jiàn),圖像匹配最大互相關(guān)的專(zhuān)用ASIC實(shí)現方法是一個(gè)簡(jiǎn)單可行的方法,并具有很好的發(fā)展前景,完全可以開(kāi)發(fā)體積小、成本低、速度與TI公司C6000系列高性能DSP的速度相比美的卷積處理器。
評論