图像特征匹配算法的FPGA 实现*

陈 超

(东南大学网络与信息中心，江苏 南京210096)

近年来，无人机遥感技术中的图像识别技术在航天军事、农业监测等领域发挥了不可替代的作用，尤其是在城市规划、环境检测、地图测绘、地形勘探等方面有着更为广泛的应用[1-2]。 在恶劣工作环境下，利用无人机图像识别系统拍摄的图像往往存在图像缩放旋转[3]、轻微抖动[4]、噪声干扰[5]、非线性畸变[6]、布局重叠[7]、图像序列获取不完整[8]等问题。 为了减小上述影响，SIFT 算法[9-10](Scale Invariant Feature Transform，尺度不变特征变换匹配算法)应运而生。 SIFT 算法能在保证上述大部分现象稳定运行的同时继续提高数据获取的精确度和系统鲁棒性，极大地提高人们的工作效率。 但SIFT 算法存在阈值过多的弊端，即计算效率低，实时性不够理想。 因此对SIFT 算法进行优化具有重要意义。

目前SIFT 算法大多应用在电脑主机、DSP 等平台上。 由于运用SIFT 算法进行图像配准计算较为复杂[11-13]，在上述平台上运行效率较差，本设计给出了基于FPGA(Field Programmable Gate Array，现场可编程门阵列)平台实现SIFT 算法的运行架构方案。 该方案的实现能提高图像数据获取的及时性和连续性，具有一定的推广价值。

1 SIFT 算法

SIFT 算法是David Lowe[14]在2004 年提出的用于图像处理领域的一种可扩展局部特征描述子。 在应对图像平移旋转、尺度缩放、明暗变化、仿射变换等情形时，其具有良好的不变性与抗噪能力。 SIFT 算法运算复杂，但能获得大量的特征向量，能充分达到特征匹配的需求，经优化后甚至可以满足系统实时性的要求。 SIFT 算法流程可简要概述为如下四步。

(1)尺度空间的构建:在实现尺度空间时通常使用DoG(Difference of Gaussian，高斯差分函数)来表示，首先通过连续减小原始图像(降采样)的顺序获得从大到小不同尺寸的一系列图像。 原始图像用作金字塔的底层，每次降采样获得的新参照用作原图像的上一层。 原始图像的尺寸和顶部图像的尺寸共同确定了金字塔中的层数。 随后，为反映尺度连续性，对高斯金字塔进行高斯滤波。 如图1 所示，高斯模糊被用于金字塔每层中具有不同参数的图像。 金字塔每层的多张高斯模糊图像被集体分为一组(Octave)。

图1 高斯金字塔示意图

最后，为得到DoG 尺度空间，利用不同尺度的高斯差分核与输入图像I(x，y)卷积生成高斯图像差分，如式(1)所示。

(2)尺度空间极值检测:特征值由差异空间的局部特征值形成。 通过比较每个像素及其周围每一个邻域像素点来查找差异函数的特征值，以查看它与其参照图和比例域的相邻点大小是否一致。 如图2 所示:中间检测点与相同比例的8 个相邻值和上下相邻尺度的9 个值相比，保证在尺度范围和二维图像范围中都检测到特征值。 此外，受边缘响应的影响，由此产生的离散空间的特征值不是真正的特征值，还需对标度空间DoG 函数进行曲线拟合，进而提高特征值的准确度和稳定性。

图2 极值点检测示意图

(3)特征点定位:要使关键描述符具有旋转不变性，有必要为每个关键点分配参考方向。 图像梯度用于找到邻域中结构的稳定方向。 如果在差分金字塔中检测到特征值，则采集并处理其所在高斯金字塔相邻窗口中像素的方向分布特征和梯度。 之后，处理邻域中的像素的梯度和方向以形成直方图。 如图3 所示，梯度直方图分为8 列(箱)，范围为0 到360°，每列45°。 直方图峰值表示关键值处的邻域梯度的方向，并且特征值的主方向由直方图中的峰值方向表示。对于具有相同梯度值的多个峰的特征值，它们将处于同样的坐标和比例。 在不同方向上创建不同特征值能够显着增强特征值配准的稳定性。

图3 特征点梯度直方图统计

(4)特征点方向确定及描述子生成:首先根据特征值的方向旋转坐标轴，保证旋转不变性，旋转结果如图4 所示。

图4 特征点邻域旋转结果

由左图坐标旋转到右图坐标转换公式如式(2)所示:

然后为每个特征点生成SIFT 描述符。 描述符使用临界点标度空间中的4×4 窗口计算的八个方向的梯度数据，由4×4×8＝128 维向量表示，如图5 所示。

最后按特征点的尺度对特征描述向量进行规范化。 如式(3)所示。

图5 128 维SIFT 向量生成图

式中:Ij表示规范化后的SIFT 特征向量，wj表示未规范化的SIFT 特征向量。

在实际应用中，SIFT 算法还需进行特征点配准。 为了减少错误匹配的可能性，采用欧氏距离来作为SIFT 描述子相似度的判别依据。 式(4)给出了欧氏距离的计算公式:

2 SIFT 配准硬件整体构架

通过FPGA 开发平台设计SIFT 算法整体构架，设计流程主要包括电路设计和输入，时序仿真，电路综合优化，以及集成功能仿真，程序板级验证，编译和程序调试。 工程师在分析要实现的电路功能时通常采用自顶向下的设计方法，这样利于模块划分和软件维护，提升可移植性和仿真效率。 考虑到FPGA 内部资源的特性，并行设计思想更为重要。为此，本设计采用Verilog 语言进行程序编写。

如图6 所示，系统主要是通过FPGA 与PC 机实现通信。 FPGA 主要完成SIFT 关键值描述符的产生、存储、位置坐标提取、注册及通信功能等。 PC 机上主要是实现图像配准结果的最终显示。

图6 SIFT 配准硬件整体构架图

3 FPGA 通信模块设计

本设计中，特征点描述子产生模块将产生的特征点坐标顺序储存在FIFO(First Input First Output)存储器中，而通信模块的主要功能是将FIFO 中的坐标数据读出来，并通过串口与PC 机通信，最终由Labview 界面接收和显示。

3.1 UART 传输时序和发送程序

UART 是一种用于异步通信的通用串行数据总线。 在FPGA 开发板设计中，UART 用来与PC 进行通信，包括数据通信，命令和控制信息的传输等，特点是能进行双向通信，能满足FPGA 并行设计要求。

图7 给出了UART 传输时序图。 消息帧由低起始位、数据位和高位停止位组成。 接收器在找到消息帧起始位时开始与发送器时钟频率同步，表示传输数据的开始。 在数据位后加上奇偶校验位，用于校验数据传输的正确性。

图7 UART 传输时序图

UART 发送程序包含3 个程序，分别是时钟产生程序(clkdiv.v)，串口发送程序(uarttx.v)和串口发送测试程序(testuart.v)。 程序clkdiv.v 用于处理波特率为9 600 bit/s 的时钟信号和UART 接收信号，这里产生的时钟clkout 是波特率的16 倍，以便在UART 接收期间接收的所有数据位有16 个时钟样本。 若对50 MHz 的系统时钟进行分频，则分频系数为50 000 000/(16×9 600)＝325.52，取整为326。 uarttx.v 程序用于发送数据，在接收到数据传输命令之后，线路起始位的时间T被下拉，然后数据从低位到高位顺序传输。 在一帧数据传输完成之后，发送停止位并等待下一个数据传输指令。 testuart.v 程序用于校准UART 发送模块的正确性，通过产生串口发送数据(0～0xFF)和发送命令信号给串口发送模块从而请求发送。

3.2 硬件介绍

硬件设计采用Silicon Labs CP2102 GM 芯片作为USB 和UART 电平转换的桥梁，USB 接口规格为Micro USB 接口，用户可以用一根开发板自带的USB 线连接到PC 上进行数据通信。 串口部分的原理图如图8 所示:RXD 从PC 发送给FPGA，TXD 从FPGA 发送给PC，以此实现全双工传输和接收。

图8 USB 转串口原理图

3.3 顶层文件原理图

图9 给出了顶层文件原理图。 各个模块间用导线连接，其中testuart 的dataout[7..0]和uarttx 的datain[7..0]之间用Diagonal Bus Tool 连接；其他的线用Diagonal Node Tool 连接。 再添加2 个输入端口分别连接到clk50 和rst＿n，同时添加一个输出端口连接到tx，另外把每个端口的名字改成与实际的功能一致，便于后续程序的调试与扩展。

图9 顶层文件原理图

3.4 测试结果

使用USB 电缆连接PC 和FPGA 开发板，然后打开串行调试助手。 在串口调试助手中，可设置波特率、校验位、数据位、停止位的一些信息。 另外，将端口设置为我们在设备管理器中看到的端口号。

下载uart＿tx.sof 到FPGA 开发板，我们可以在串口工具上看到从FPGA 开发板不断发给PC 的从0 到FF 的16 进制的测试数据。

4 SIFT 配准算法FPGA 实现与结果

4.1 Sift＿top 顶层设计

SIFT 算法整体结构如图10 所示，主要由高斯金字塔模块，差分金字塔模块，极值点检测模块等组成。 基于FPGA 开发平台实现的图像特征匹配算法以Sift＿top 作为顶层依次调用上述模块。 最终通过通信模块发送特征点坐标位置至串口，并导入MATLAB 显示最终匹配结果。

图10 SIFT 算法程序整体构图

4.2 系统实现结果分析

首先根据特征匹配需求选择一个FPGA 型号并对整体程序进行时序仿真。 由于SIFT 算法提高了准确度和系统鲁棒性，因此程序在时序仿真和功能仿真过程中耗时较长。 从仿真结果我们可以看出硬件资源的消耗情况，从而可以判断我们选择的FPGA 型号是否满足设计要求。

随后进行功能仿真，这个过程主要是验证程序时序仿真结果和算法整体架构是否符合FPGA 实现的要求。

图11 给出了最终的实现平台，以FPGA 开发板作为主控，利用通信模块建立FPGA 开发板与PC机之间的通信。 将存储在FIFO 中的特征点坐标提取出来并利用串口通信方式传输到上位机界面上进行显示。

图11 最终实现平台

Labview 上位机界面采集的数据即为存储在FIFO 中的特征点位置坐标，如表1 所示。

表1 上位机界面接收的特征点位置坐标

针对本设计利用MATLAB 平台，读取FPGA 运行程序得到的匹配特征点的位置坐标文件，并在原图像上进行显示，如图12 所示。 由于FPGA 资源的限制，运行SIFT 后得到的特征点对数量较少，但保证了特征点准确度，因此基本满足特征匹配的需求。

图12 SIFT 算法FPGA 实现结果展示图

5 结束语

本设计在研究了基于SIFT 图像配准算法相关理论基础上，对其进行了FPGA 硬件平台实现。 主要完成了SIFT 算法的FPGA 整体结构设计以及FPGA 显示与通信模块设计。

本设计给出了高斯滤波、尺度空间、DoG 金字塔、特征点提取等模块的设计方法与理念。 不但要求熟练进行FPGA 时序设计，还要熟悉相关配置和通信流程，才能进行二者的顺利通信。 SIFT 算法中梯度直方图的计算采用双口RAM 进行同时读取，而通讯模块设计采用串口传输方式，合理分配了FPGA 的内部资源，提高了系统的实时性和连续性。利用MATLAB 平台进行数据读取，并将最终配准结果进行显示。 在FPGA 开发板及上位机上实现图像实时匹配验证，匹配结果初步满足实用要求，具有一定的应用价值。