基于FPGA的數字圖像匹配

杜振宇

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

0 引言

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

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

1 BMP數字圖像綜述

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

(a)位圖頭文件數據結構，它包含BMP圖像文件的類型、顯示內容等信息。

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

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

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

對于數字圖像的匹配中主要用的信息是第二部分，即位圖的信息數據結構，所以對于灰階的BMP圖像，必須對它的信息進行提取，這里采用MATLAB軟件對BMP圖像中的位圖信息數據結構進行提取。

2 FPGA中ROM模塊的構建

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

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

圖1 ROM模塊設置

此處采用的是MIF文件來作為ROM是數據存儲文件，MIF文件是一個可以用來存儲二進制數據的文件，此處可以用來存儲所需要的8位二進制的數據圖像的文件。構建ROM時可以將此文件加載內嵌到相應的ROM模塊中，這樣所構建的ROM 模塊就存儲有數字圖像是每個像素點的灰度值的詳細信息了。ROM 模塊中的每一個存儲單元都對應于數字圖像的每一個像素點的灰度值。

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

為了保證加法器有足夠的時間進行加法運算，此處設定的讀取數據所消耗的時間為10個時鐘。

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

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

經過分析可知，此處構建的ROM模塊在ROM控制模塊的控制下可以有序地進行順利的數據讀取。

ROM模塊的構建時，要對匹配的圖像所需要的ROM和目標圖像所需要的ROM分別進行構建。兩者進行匹配運算的流程如圖3所示。

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

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

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

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

圖3 模塊匹配運算簡圖

3 8位加法器的設計

基于BMP數字圖像的主要位圖信息的提取，ROM模塊的構建以及控制ROM模塊中的存儲單元所對應的存儲地址的控制輸出完成后，剩下的部分即是對兩個ROM模塊所輸出的存儲數據進行匹配運算，也就是減法運算。而減法運算其實可以通過求反變為加法運算，而求反又可以通過求補來進行。基于這種思路設計出的加法器其RTL級仿真結果如圖4所示。

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

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

圖4 并行加法器的RTL結構圖

圖5 加法器運算仿真結果圖

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

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

4 結果分析

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

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

[2]藍章禮,李益才,李艾星.數字圖像處理與圖像通信[M].北京:清華大學出版社,2008.

[3]夏宇聞.基于verilog HDL的數字系統設計入門教程[M].北京:北京航空航天大學出版社,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 設計計數器電路的關鍵路徑分析法[J].西安電子科技大學學報,1997,24(1):141-147.

[7]吳繼華.將低成本的FPGA用于視頻和圖像的處理[J].電子設計應用 ,2007.

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

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

[10]張靜亞.FPGA系統設計中硬件資源分配的分析與研究[J].信息化研究,2009.