基于FPGA的數(shù)字圖像匹配

杜振宇

（中北大學(xué)信息通信與工程學(xué)院 山西省太原市 030051）

0 引言

隨著當(dāng)代電子制造技術(shù)的快速發(fā)展，F(xiàn)PGA的制造工藝已經(jīng)達(dá)到了一個較高的水平，國際上的硅片面積已經(jīng)增長到厘米見方，管數(shù)達(dá)到十幾億甚至幾十億而布線寬度只有零點(diǎn)幾個微米，從而使得FPGA芯片的集成度達(dá)到了一個較高的程度。因而FPGA在電子領(lǐng)域方面的應(yīng)用可以說是越來越舉足輕重。

另外當(dāng)今世界上最先進(jìn)的計(jì)算機(jī)的CPU（20核CPU）所采用的制造工藝就是基于FPGA的技術(shù)的應(yīng)用。隨著科技的發(fā)展，人們對數(shù)字圖像技術(shù)的要求也越來越高，特別是數(shù)字圖像的匹配技術(shù)，由于FPGA的高速運(yùn)算，微型體積，較低功耗等諸多方面的優(yōu)點(diǎn)，使得FPGA在進(jìn)行圖像匹配中起著不可替代的作用。

1 BMP數(shù)字圖像綜述

對于數(shù)字圖像的匹配首先必須了解靜態(tài)圖片在計(jì)算機(jī)中的存儲形式，由于此處需要用到不失真的圖片，即此種類型的圖片要不失真地保存著圖片每個像素點(diǎn)的內(nèi)容，因而此處選用的是BMP格式的計(jì)算機(jī)靜態(tài)圖片。本文中只采用對BMP的灰階圖片進(jìn)行相關(guān)的存儲匹配運(yùn)算處理，而靜態(tài)灰階BMP圖像主要包括以下4個方面的內(nèi)容，它們分別是：

(a)位圖頭文件數(shù)據(jù)結(jié)構(gòu)，它包含BMP圖像文件的類型、顯示內(nèi)容等信息。

(b)位圖信息數(shù)據(jù)結(jié)構(gòu)，它包含有BMP圖像的寬、高、壓縮方法，以及定義顏色等信息。

(c)調(diào)色板，這個部分是可選的，由于是灰階圖像，因而調(diào)色板是8位的。

(d)位圖數(shù)據(jù)，這部分的內(nèi)容根據(jù)BMP位圖使用的位數(shù)不同而不同，此處使用的是8位。

對于數(shù)字圖像的匹配中主要用的信息是第二部分，即位圖的信息數(shù)據(jù)結(jié)構(gòu)，所以對于灰階的BMP圖像，必須對它的信息進(jìn)行提取，這里采用MATLAB軟件對BMP圖像中的位圖信息數(shù)據(jù)結(jié)構(gòu)進(jìn)行提取。

2 FPGA中ROM模塊的構(gòu)建

對于已經(jīng)被提取出來的BMP圖像中的位圖信息的數(shù)據(jù)結(jié)構(gòu)而言，其實(shí)可以看作是一個二維矩陣，假定原來的BMP圖像的分辨率為M×N，那么其可以被看作的矩陣的規(guī)格就是M行N列的二維矩陣。矩陣中的每一個元素對應(yīng)的就是BMP圖像中的每一個像素點(diǎn)。由于對BMP圖像采用的是256階的灰階處理，即采取從全白到全黑直接使用256個等級來表達(dá)每個像素點(diǎn)的灰度值，因而對應(yīng)的該矩陣的每個元素就是8位的二進(jìn)制數(shù)。所以，在FPGA中構(gòu)建的ROM的就必須可以剛好存儲下BMP圖像所對應(yīng)的矩陣，因而此ROM的相關(guān)參數(shù)分別為：

Number of words ：M×N ； Word size ： 8；然后將對應(yīng)的矩陣中的每個元素存儲在此ROM文件中。假定M=32 N=64 M×N=2048則所構(gòu)建的ROM模塊的設(shè)置如圖1所示。

圖1 ROM模塊設(shè)置

此處采用的是MIF文件來作為ROM是數(shù)據(jù)存儲文件，MIF文件是一個可以用來存儲二進(jìn)制數(shù)據(jù)的文件，此處可以用來存儲所需要的8位二進(jìn)制的數(shù)據(jù)圖像的文件。構(gòu)建ROM時可以將此文件加載內(nèi)嵌到相應(yīng)的ROM模塊中，這樣所構(gòu)建的ROM 模塊就存儲有數(shù)字圖像是每個像素點(diǎn)的灰度值的詳細(xì)信息了。ROM 模塊中的每一個存儲單元都對應(yīng)于數(shù)字圖像的每一個像素點(diǎn)的灰度值。

當(dāng)ROM模塊構(gòu)建好后，必須控制對ROM模塊中的每個數(shù)據(jù)進(jìn)行讀取，即編寫一個控制模塊，并且通過一定的讀取頻率，讀ROM模塊中的每個數(shù)據(jù)元素進(jìn)行讀取，由于所讀取出來的數(shù)據(jù)還必須輸送到下一個模塊加法器中做相應(yīng)的加法處理運(yùn)算，而且保證只有等到加法器中完成了對上一組數(shù)據(jù)的加法運(yùn)算以后，才可以將ROM模塊中的數(shù)據(jù)讀取出來，并且及時地送到加法器的輸入端口。

為了保證加法器有足夠的時間進(jìn)行加法運(yùn)算，此處設(shè)定的讀取數(shù)據(jù)所消耗的時間為10個時鐘。

圖2是所編寫的ROM模塊在ROM控制讀取模塊時下數(shù)據(jù)讀取出來的仿真結(jié)果，為了方便起見，此處構(gòu)建的ROM模塊的大小規(guī)格是16×8位的，對每個ROM的存儲單元所寫入的數(shù)據(jù)分別為：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

圖2 ROM模塊的讀取時序仿真

經(jīng)過分析可知，此處構(gòu)建的ROM模塊在ROM控制模塊的控制下可以有序地進(jìn)行順利的數(shù)據(jù)讀取。

ROM模塊的構(gòu)建時，要對匹配的圖像所需要的ROM和目標(biāo)圖像所需要的ROM分別進(jìn)行構(gòu)建。兩者進(jìn)行匹配運(yùn)算的流程如圖3所示。

圖中分別對應(yīng)的是ROM匹配運(yùn)算所進(jìn)行的第1次運(yùn)算，第2次運(yùn)算，第x次運(yùn)算，以及第y次運(yùn)算。其中存儲目標(biāo)圖像的ROM的規(guī)格大小為：m× n×8； 存儲待匹配的圖像的ROM的規(guī)格大小為：a× b×8，其中x＜a-m， y＞a-m，由圖知，當(dāng)經(jīng)過y次的匹配運(yùn)算以后（令最待匹配的圖像對應(yīng)的ROM模塊的最左上方的坐標(biāo)為原點(diǎn)坐標(biāo)），目標(biāo)圖像的起始坐標(biāo)為（y%(a-m), y/(a-m)）,終止坐標(biāo)為（y%(a-m)+m, y/(a-m)+n）,此時經(jīng)過y次的匹配運(yùn)算以后，目標(biāo)圖像所對應(yīng)的ROM模塊與待匹配的ROM模塊中需要進(jìn)行匹配運(yùn)算的存儲單元所對應(yīng)的地址是n+1段的離散區(qū)間段，這些離散的區(qū)間段所對應(yīng)的ROM 地址為：

其中 x的取值為 0 ，1，2，3, …, n。

對ROM離散的區(qū)間段的數(shù)據(jù)的讀取，可以通過編寫一個ROM地址的控制模塊，并且保證在這個控制模塊的控制下，控制模塊最終輸出的所有作為ROM模塊的地址輸入的信號滿足表達(dá)式：

并且要控制著x的取值，從而可以保證在ROM控制模塊的作用下，最終ROM 模塊的輸出端可以全部將這些離散區(qū)間段的存儲數(shù)據(jù)讀取并進(jìn)行輸出。

圖3 模塊匹配運(yùn)算簡圖

3 8位加法器的設(shè)計(jì)

基于BMP數(shù)字圖像的主要位圖信息的提取，ROM模塊的構(gòu)建以及控制ROM模塊中的存儲單元所對應(yīng)的存儲地址的控制輸出完成后，剩下的部分即是對兩個ROM模塊所輸出的存儲數(shù)據(jù)進(jìn)行匹配運(yùn)算，也就是減法運(yùn)算。而減法運(yùn)算其實(shí)可以通過求反變?yōu)榧臃ㄟ\(yùn)算，而求反又可以通過求補(bǔ)來進(jìn)行?；谶@種思路設(shè)計(jì)出的加法器其RTL級仿真結(jié)果如圖4所示。

通過對該加法器的RTL級的仿真結(jié)果可以知道，此加法器所占用的FPGA資源不多，因而該加法器的設(shè)計(jì)遵循了占用FPGA資源盡量少的優(yōu)勢，同時也可以保證該加法器在進(jìn)行加法運(yùn)算處理的時候能夠較少地出現(xiàn)延時，這對最終結(jié)果的分析以及對后續(xù)加法運(yùn)算提供一個良好的時序環(huán)境，在此時序環(huán)境下，加法運(yùn)算會順利進(jìn)行。

通過使用專門的電路仿真軟件，得到的仿真結(jié)果如圖5所示。

圖4 并行加法器的RTL結(jié)構(gòu)圖

圖5 加法器運(yùn)算仿真結(jié)果圖

由上述的仿真結(jié)果可知：當(dāng)兩個加數(shù)分別為10和20時得出的結(jié)果為30，并只存在一個時鐘周期的延時，當(dāng)兩個加數(shù)都為255時，沒有發(fā)生所謂的溢出現(xiàn)象，得出了正確結(jié)果510，所以此加法器通過了功能仿真驗(yàn)證和時序仿真驗(yàn)證。

由于每一次經(jīng)過加法器的運(yùn)算輸出的最大結(jié)果為510，需要9位寄存器存儲，但由于每個像素點(diǎn)的灰度值都不可能出現(xiàn)負(fù)數(shù)，在結(jié)合每個像素點(diǎn)的灰度值的取值范圍以及我們所指的加法器的運(yùn)算結(jié)果實(shí)質(zhì)是兩個像素點(diǎn)灰度值的差值，而每個像素點(diǎn)之間的差值都不會超過255。因而每次加法器的運(yùn)算結(jié)果只需要一個8位的寄存器就可以存儲了。每完成一次目標(biāo)圖像的匹配運(yùn)算就產(chǎn)生了m× n個8位的二進(jìn)制數(shù)據(jù)結(jié)果。同時還需要將這些加法器所得的運(yùn)算結(jié)果進(jìn)行疊加運(yùn)算得出最終的目標(biāo)圖像與待匹配圖像的灰度差值的總值。而最終的這些差值的總值的個數(shù)將會是（a-m）×（b-n）。再通過比較這些差值的大小，從中選出最小的值，并同步計(jì)數(shù)出該差值最小出現(xiàn)時加法器所做的加法運(yùn)算的次數(shù)就可以得出該目標(biāo)圖像與待匹配圖像最匹配的模塊的坐標(biāo)值的位置,假定，該加法器所運(yùn)算的次數(shù)為k次時的數(shù)值差值最小，則可以得出該模塊最匹配的位置的坐標(biāo)分別為：

4 結(jié)果分析

首先通過相應(yīng)的軟件對BMP圖像進(jìn)行位圖詳細(xì)信息的提取，并將這些位圖信息保存于MIF文件中，再通過構(gòu)建相應(yīng)的ROM模塊，ROM 模塊通過加載MIF文件來實(shí)現(xiàn)對BMP圖像文件每個像素點(diǎn)灰度值的存儲。對此ROM模塊加載相應(yīng)的控制模塊控制其ROM模塊的輸出端連接到8位加法器的輸入端，從而使得加法器可以對每次由ROM模塊輸出的數(shù)據(jù)進(jìn)行相應(yīng)的必要的加法處理。同時，對加法器的每次運(yùn)算結(jié)果進(jìn)行存儲累加，直到完成一次目標(biāo)圖像與待匹配圖像的匹配運(yùn)算為止，同時對每次ROM模塊匹配所完成的結(jié)果進(jìn)行存儲，并通過比較器來最終得出的結(jié)果中數(shù)值最小的ROM模塊即可。此時通過確定加法器的運(yùn)算次數(shù)就可以得到該ROM模塊所對應(yīng)的圖像模塊對應(yīng)于待匹配圖像中所處的具體位置，也就是相對于待匹配圖像中的起點(diǎn)的坐標(biāo)值。

[1]李俊山,李旭.數(shù)字圖像處理[M].北京: 清華大學(xué)出版社,2006.

[2]藍(lán)章禮,李益才,李艾星.數(shù)字圖像處理與圖像通信[M].北京:清華大學(xué)出版社,2008.

[3]夏宇聞.基于verilog HDL的數(shù)字系統(tǒng)設(shè)計(jì)入門教程[M].北京:北京航空航天大學(xué)出版社,2008.

[4]David Taubman. High Performance Scalable Image Compreesion with EBCOT[J].IEEE Trans on Image Processing,July 2000,9(7):1158-1170.

[5]Landgrebe D.Hyperspectral Geological Remote Sensing : Evoluation of Analytical Techniques[J].International Journal of Remote Sensing,1996.

[6]葉后裕,張建忠.用 FPGA 設(shè)計(jì)計(jì)數(shù)器電路的關(guān)鍵路徑分析法[J].西安電子科技大學(xué)學(xué)報,1997,24(1):141-147.

[7]吳繼華.將低成本的FPGA用于視頻和圖像的處理[J].電子設(shè)計(jì)應(yīng)用 ,2007.

[8]張杰.基于FPGA的數(shù)字圖像處理[D].武漢:武漢科技大學(xué),2009.

[9]苗延盛,程佳,紀(jì)寧寧.基于FPGA的ITU656接口圖片顯示{EB/OL}.深圳天馬微電子股份有限公司,2009. http://wenku.baidu.com/view/05a4dbd86f1aff00bed51ebc.html.

[10]張靜亞.FPGA系統(tǒng)設(shè)計(jì)中硬件資源分配的分析與研究[J].信息化研究,2009.