自适应阈值FAST特征点检测算法的FPGA实现

程 彪，黄 鲁

(中国科学技术大学 信息科学技术学院，安徽 合肥 230026)

0 引言

特征点检测是计算机视觉中非常重要的技术之一，在物体检测、视觉跟踪、三维重建等领域都有很广泛的应用[1]。目前最常用的特征点检测算法有FAST、Harris、Shi-Tomasi和SUSAN等。FAST特征点检测算法由于结构简单[2]，在同步定位与地图构建技术(Simultaneous Localization And Mapping，SLAM)[3]中得到了较广泛应用。

传统的FAST特征点检测算法都是基于通用处理器CPU实现的，通用处理器按顺序串行执行指令。图像处理算法中的所有元素均可以实行同样操作，存在固有的并行性。FPGA硬件配置灵活，具有并行执行优势[4]，在大数据量图像处理领域有着天然优势。FAST特征点检测算法结构简单，只涉及整数运算，非常适合用FPGA来实现。对于相同大小的图片，FPGA实现的FAST特征点检测算法在主频小于ARM的情况下仍可以获得可观的算法运算速度提升。

1 FAST特征点检测算法原理

FAST特征提取的主要原理为比较候选像素与其周围一圈像素的灰度值，若灰度值相差较大的像素能组成连续且弧长大于圆周长3/4的圆弧，则是FAST角点[5]。FAST-9主要步骤为：

(1)如图1所示，在一个以像素p为中心、半径为3的Bresenham圆上，有16个像素点(p1，p2，…，p16)，定义一个阈值t。

(2)计算p与p1、p9、p5、p13的像素差，若它们的绝对值至少有3个大于阈值，则当做候选点，进行第3步；否则，直接排除。

图1 FAST特征点Bresenham圆示意图

(3)计算p与p1到p16这16个点的像素差，若它们的绝对值至少有连续9个大于阈值，则是特征点；否则，直接排除掉。

(4)进行非极大值抑制，计算特征点的FAST得分函数值V(如公式(1)所示)，若以特征点p为中心的一个邻域(如7×7)内有多个特征点，而且p点得分值为邻域所有特征点中响应值最大的，则保留；否则，抑制。若邻域内只有一个特征点，则保留。

(1)

图3 FAST特征点检测算法模块

2 系统设计方案

2.1 系统硬件结构

系统的硬件结构框图如图2所示，FPGA芯片通过SCCB接口对OV5640摄像头的寄存器进行配置，得到帧率为30 f/s、分辨率为480×272的灰度视频图像。DDR3存储控制模块通过配置FPGA内置的MCB硬核将摄像头采集的数据缓存到DDR3芯片中。

图2 系统框图

将DDR3图像存储空间分为两块，当地址1开始的区域作为图像数据写地址的时候，地址2开始的区域就作为图像的读开始地址，等一幅图像数据写入DDR3完成后交换读写地址空间，这样可以避免物体运动产生图像拖影的现象。将读取到的数据送入FAST特征提取算法模块处理后再显示，对于一幅图像，将作为特征点的坐标的像素置为8’b0，以便在LCD显示屏上可以直观观察特征点。

2.2 FAST特征点提取算法硬件实现

FAST特征点提取算法总体硬件实现由7×7窗口生成模块、FAST主模块、特征点判断模块、自适应阈值模块、得分值计算模块和非极大值抑制模块构成。总体硬件实现框图如图3所示。

系统的主要数据流如箭头所示，从DDR3缓存中读出来的像素数据以串行的数据流方式传入7×7窗口生成模块。此后FAST主模块在同一个时钟沿并行地获取中心像素值以及对应的bresenham圆上的16个像素点，FAST主模块用中心像素值与bresenham圆上的这些像素值作差值、比较等运算，运算结果传入得分值计算模块和特征点判断模块处理，非极大值抑制模块对处理结果进行比较运算，得到最终的特征点，自适应阈值模块再对特征点进行计数，设计自适应阈值再传回FAST主模块。

2.2.17×7窗口生成模块

7×7窗口生成模块由6个深度为480、数据宽度为8的FIFO和49个8位寄存器构成[6]，其结构如图4所示，FIFO的读写、寄存器的控制均由同一个时钟信号控制，可以在同一个时钟沿并行地获取中心像素值以及对应的bresenham圆上的16个像素点数据。随着串行数据的输入，模块以滑动窗口的形式(每个时钟周期处理一个图像窗口)完成整幅图像的处理。

图4 7×7窗口生成模块

2.2.2FAST主模块

7×7窗口生成模块在同一个时钟沿将中心元素center和圆周像素p_n(n=1,2，…，16)传入FAST主模块，实现圆周像素是否为亮、暗点的判断。以亮点判断为例，主模块将p_n减center得到值S1_B，将S1_B减阈值得到值S2_B。如果S2_B大于0，则表示该点为亮点，将S2_B赋值给bright_n；否则，将bright_n赋0值。通过16组并行的硬件实现16个圆周像素的亮点判断运算。同理，暗点的判断与亮点硬件结构一致，只有暗点的S1_B值为center减p_n得到这一点不同。总体的硬件结构如图5所示。

图5 FAST主模块

串行处理器实现以上步骤至少需要2×16×3个指令周期，而FPGA硬件实现只要3个时钟周期，利用面积换速度的方法实现了硬件加速[7]。

2.2.3特征点判断模块

对于FAST-9算法，圆环上具有9个以上的连续亮点或暗点的center像素即为特征点。特征点判断模块由FAST主模块传入的bright[15:0]和dark[15:0]来实现判断。bright[15:0]=16’b0000_1111_0000_1111表示圆环上的p1～p4，p9～p12为亮点，其余的为非亮点；同理dark[15:0]=16’b0000_1111_0000_1111表示圆环上的p1～p4,p9～p12为暗点，其余的为非暗点。

硬件实现上，分为并行的两路实现，一路实现亮点匹配，另一路实现暗点匹配。以亮点bright[15:0]为例，b1，b2，…，b16为其16个bit位元素。match信号的生成逻辑如公式(2)所示，match1为1时，表示p1～p9满足亮点匹配。同理可以得到match2,match3,…,match16。亮点匹配的逻辑实现如图6所示，由16路4级并行逻辑实现。FPGA硬件是通过两级6输入查找表实现9输入match1函数，如图7所示，时延仅为两级查找表表延时，显著加快了运算速度。

match1=b1 &b2 &…b9

match2=b2 &b3 &…b10

…

match16=b16 &b1 &...b8

(2)

图6 亮点匹配的逻辑实现图

图7 match1函数FPGA硬件实现

满足亮点匹配信号由16个match信号的或运算得出，如公式(3)所示。

is_corner_b=match1|match2...|match16

(3)

特征点判断模块的最终输出信号iscorner为两路匹配判断电路或运算计算结果，如公式(4)所示。

is_corner=is_corner_b|is_corner_d

(4)

2.2.4得分值计算模块

得分值计算模块对FAST主模块的输出o_bright_n[9:0]、o_dark_n[9:0](n=1,2，…，16)进行操作。硬件实现上也分为两路，一路实现o_bright_n的16个元素相加，另一路实现o_dark_n的16个元素相加，如公式(5)所示。

sum_b=o_bright_1+...+o_bright_16

sum_d=o_dark_1+...+o_dark_16

(5)

sum_b的硬件实现结构如图8所示，sum_d的硬件结构与其一致。采用了4级流水线实现了16个数的加法操作[8]，相比于串行处理器(需要16次取数据指令，15次加法指令)加快了计算sum_b的运算速度。最后的得分值输出结果为sum_b和sum_d之间的较大值，在硬件上用一个比较器实现。

图8 sun_b信号生成电路结构图

2.2.5非极大值抑制模块

非极大值抑制模块将得分值计算模块的输出数据corner_score[12:0]输入到7×7窗口生成模块。7×7窗口生成模块由6个深度为480、数据宽度为16的FIFO和49个13位寄存器构成。从上级模块输入的is_corner为候选特征点指示信号,高电平有效。

对于窗口中的49个数据，如果窗口中心元素大于其他所有48个元素，则保留中心元素为特征点，置corner_right为1，否则则抑制，置corner_right为0。完成这些操作需要48次比较运算和47次与运算。

2.2.6自适应阈值模块

实际工程应用中，多样化环境会使传统的单一阈值方法失效，环境纹理丰富程度变化时，FAST算法提取角点数目波动范围非常大，不利于后续算法处理。基于ORB-SLAM的定位算法中FAST算法提取300～500个特征点是一个比较理想的结果。

本文采用了自适应阈值的方法来解决该问题。只需人为设定初始阈值，后续一帧图像的阈值由前一帧的阈值和前一帧图像检测到的特征点数目来得到[9](如表1所示)。如果检测的特征点数目偏少，程序会根据检测到的特征点数目区间将自适应阈值减去相应值，反之增加相应的值。当前后帧图像差异较大时，得到最终的自适应阈值过程的迭代次数会增加。将两幅纹理不同的图片开始阈值都设为25，经程序运行后得到的结果如图9(纹理丰富)、图10(纹理稀少)所示，这表明了该方法可以很好地得到满足条件的自适应阈值。硬件实现上使用计数器对corner_right计数来得到特征点数目，自适应阈值使用5路数字比较器比较后对前一帧阈值作相应增减得到。

表1 当前帧阈值与前一帧阈值th的关系

图9 自适应阈值为39 检测出特征点数为490

图10 自适应阈值为12 检测出特征点数为331

3 实验验证分析

本文实现的FAST特征点检测算法的硬件平台为Xlinx公司Spartan6系列xc6slx45芯片，采用ISE14.7软件和Verilog语言来编写程序。用ISim进行功能仿真，用FPGA作板级验证。

3.1 功能仿真

由于直接观察波形图结果不够直观，testbench中将为角点的像素坐标处像素值设为255，其余像素值保持不变，将处理好的图片数值保存在txt文件中，再利用MATLAB将txt文件中的像素数据恢复成图片[8]，恢复出的结果如图11所示，由仿真图可知，可以很好地检测出FAST特征点。

3.2 板级验证

FPGA硬件平台实时检测特征点效果如图12所示为了直观显示效果，将图12局部放大如图13所示，黑点为实时检测到的特征点。板级验证结果表明FPGA实现的FAST特征点检测精度和实时性均良好。

图11 MATLAB还原结果

图12 实时检测特征点示意图

图13 局部放大示意图

3.3 速度比较

对于同样的算法，图片都为大小480×272的灰度图。由仿真得知，FPGA处理一幅图片需要132 976个时钟周期，系统时钟为100 MHz，处理时间为1.33 ms。ARM处理器为三星S5PV210，主频达1 GHz，其处理时间为5.01 ms(算法为OpenCV-2.4.10标准库函数，运行时间为50次运行时间平均值)。在主频只有ARM 1/10的情况下，FPGA达到了3.8倍的运行时间性能提升。

4 结论

本文提出了一种基于FPGA的FAST特征点检测算法硬件实现方法。实验结果表明，该硬件实现能根据环境纹理的丰富程度设计自适应阈值，使每幅图片都可以检测到300～500个特征点。该实现能够充分发挥FPGA硬件平台的并行执行优势，相比通用处理器，算法的运算速度有了大幅提高。该实现对FPGA实现基于模板图像处理算法具有通用性，对FPGA实现图像处理算法的加速具有重要意义。