基于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.