一种基于尺度不变特征转换算法的硬件加速方法及系统

技术领域

本发明属于算法的硬件加速设计领域，更具体地，涉及一种基于尺度不变特征转换算法的硬件加速方法及系统。

背景技术

尺度不变特征转换(Scale-invariant feature transform，简称SIFT)算法是一种局部特征提取算法，可以解决两幅图像因发生平移、旋转、仿射变换等情况带来的匹配问题。SIFT算法可以将一幅图片转换为一个具有大量局部特征向量(SIFT描述子)的集合。该算法在图像发生仿射变化、3D视角变化、比例缩放、曝光度变化和噪声加入等条件下仍然能够获得较为可靠的匹配结果。因此，SIFT算法被广泛应用于智能自主移动机器人及自动驾驶的建图定位、匹配重建、运动分割跟踪、图像全景融合等需要图像识别匹配的场景。

然而，现有SIFT硬件加速系统实现的帧率较低。2012年，F.Huang等人在IEEE视频电路与系统学报发表的SIFT硬件加速系统采用了关键点检测部分和描述符产生部分交互进行的设计策略，存在处理速度很低的问题。2016年，J.Yum等人在IEEE视频电路与系统学报发表的SIFT硬件加速系统通过优化的存储设计，减小了存储的硬件开销；但是由于描述符产生部分中的主方向计算过程和描述符产生过程仍为串行执行，所以处理速度受到限制。

发明内容

针对现有技术的缺陷和改进需求，本发明提供了一种基于尺度不变特征转换算法的硬件加速方法及系统，旨在解决现有SIFT加速系统设计的并行性受到限制，处理帧率较低的技术问题。

为实现上述目的，第一方面，本发明提供了一种基于尺度不变特征转换算法的硬件加速方法，包括以下步骤：

S11、并行计算SIFT关键点以及所有像素点的梯度幅值和方向；

S12、将关键点及其对应的梯度幅值和方向分别按奇数帧和偶数帧进行存储，以实现乒乓操作；

S21、对每一关键点，确定其圆形邻域，并将所述圆形邻域等分为16N个区域，利用所述圆形邻域的同心圆将每一所述区域划分为两个子区域，从而得到32N个子区域；

S22、并行计算SIFT关键点主方向以及统计32N个子区域的直方图，其中每个直方图统计16N个方向；

S23、待主方向和32N个直方图均确定后，先根据主方向调整每个直方图中的16N个方向，实现每个子区域内部的旋转操作；再根据主方向调整32N个直方图之间的顺序，实现子区域之间的旋转操作；然后将每个直方图中相邻4N个方向的向量相加得到8个向量，实现每个子区域内部的向量降维；最后将32N个子区域中相邻4N个子区域的直方图数据相加得到16个直方图，实现子区域之间的向量降维，N为正整数；

S24、对最终得到的128维向量归一化处理得到关键点描述子。

进一步地，所述S11之前，还包括：

S10、对原始图像进行高斯滤波处理，以并行构建多层的高斯金字塔和高斯差分金字塔。

进一步地，所述S11包括：

基于所述高斯差分金字塔确定SIFT关键点，同时基于所述高斯金字塔计算所有像素点的梯度幅值和方向。

进一步地，所述S23中，将每个直方图中相邻4N个方向的向量相加得到8个向量，包括：依次间隔2N个方向将每个直方图中相邻4N个方向的向量相加得到8个向量。

进一步地，所述S23中，将32N个子区域中相邻4N个子区域的直方图数据相加得到16个直方图，包括：

利用所述圆形邻域的同心圆将16N个区域划分为内外各16N个子区域，对内部16N个子区域，依次间隔2N个子区域将相邻4N个子区域的直方图数据相加得到8个直方图；对外部16N个子区域，依次间隔2N个子区域将相邻4N个子区域的直方图数据相加得到8个直方图；从而得到16个直方图。

第二方面，本发明提供了一种基于尺度不变特征转换算法的硬件加速系统，包括：

第一并行处理模块，用于并行计算SIFT关键点以及所有像素点的梯度幅值和方向；

缓存模块，用于将关键点及其对应的梯度幅值和方向分别按奇数帧和偶数帧进行存储，以实现乒乓操作；

第二并行处理模块，用于对每一关键点，确定其圆形邻域，并将所述圆形邻域等分为16N个区域，利用所述圆形邻域的同心圆将每一所述区域划分为两个子区域，从而得到32N个子区域；以及用于并行计算SIFT关键点主方向以及统计32N个子区域的直方图，其中每个直方图统计16N个方向；

重排以及降维模块，用于待主方向和32N个直方图均确定后，先根据主方向调整每个直方图中的16N个方向，实现每个子区域内部的旋转操作；再根据主方向调整32N个直方图之间的顺序，实现子区域之间的旋转操作；然后将每个直方图中相邻4N个方向的向量相加得到8个向量，实现每个子区域内部的向量降维；最后将32N个子区域中相邻4N个子区域的直方图数据相加得到16个直方图，实现子区域之间的向量降维，N为正整数；

输出模块，用于对最终得到的128维向量归一化处理得到关键点描述子。

第三方面，本发明提供了一种计算机设备，所述设备包括：存储器及处理器；所述存储器用于存储计算机指令；所述处理器运行计算机指令实现如第一方面所述的基于尺度不变特征转换算法的硬件加速方法。

总体而言，通过本发明所构思的以上技术方案，能够取得以下有益效果：

相比于现有的SIFT硬件加速系统，本发明提出了一种新颖的全并行SIFT加速系统架构。该架构主要包括关键点检测和描述符产生两个部分，两个部分之间的四个缓冲器进行乒乓操作来提高系统处理速度。在关键点检测部分，首先并行计算多层的高斯金字塔和高斯差分金字塔，然后通过并行计算，得到关键点和梯度幅值和方向。在描述符产生部分，本发明提出了基于圆域的关键点邻域划分策略，实现了主方向计算模块和描述符产生模块的并行化计算，最后通过描述符重排和降维模块得到最后的输出。从而，实现全并行，能够提高处理帧率。

附图说明

图1为基于尺度不变特征转换算法的硬件加速方法流程图；

图2为基于尺度不变特征转换算法的硬件加速系统架构图；

图3为描述符产生模块使用的关键点邻域划分方式的示意图；

图4为描述符重排和降维的示意图；

图5(A)为子区域重叠的邻域划分方式示意图；

图5(B)为将主方向旋转到默认方向的示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

参阅图1，结合图2至图4，本发明提供了一种基于尺度不变特征转换算法的硬件加速方法，包括关键点检测和描述符产生两个部分，两个部分之间的四个缓冲器进行乒乓操作来提高系统处理速度。在关键点检测部分，首先并行计算多层的高斯金字塔和高斯差分金字塔，然后通过并行计算，得到关键点和梯度幅值和方向。在描述符产生部分，本发明提出了基于圆域的关键点邻域划分策略，实现了主方向计算模块和描述符产生模块的并行化计算，最后通过描述符重排和降维模块得到最后的输出。具体的，关键点检测部分包括操作S11和S12，描述符产生部分包括操作S21至S24。

操作S11、并行计算SIFT关键点以及所有像素点的梯度幅值和方向。

本实施例中，在步骤S11之前，还包括：

操作S10、对原始图像进行高斯滤波处理，以并行构建多层的高斯金字塔和高斯差分金字塔。

尺度空间的构建通过高斯卷积来实现，定义I(x,y)表示原图像，G(x,y,σ)表示高斯函数，且

在SIFT算法中，尺度空间的具体表现是高斯金字塔。它是通过对高斯模糊图像降采样，得到的由大到小的图像构成的塔形结构。关于高斯金字塔的构建，需要两步操作：①对图像做不同尺度的高斯模糊；②对高斯模糊图像做降采样。以原图像为基础，使用不同尺度因子σ的高斯函数对原图像进行高斯模糊，得到含有多层不同模糊程度的图像构成的第一组高斯金字塔。对第一组高斯金字塔中的一层做降采样，得到长宽为原图像一半的图像作为第二组的第一层，对该图像使用不同尺度因子σ的高斯函数进行高斯模糊得到第二组的其它层。其他组的构成方法以此类推。

构建高斯金字塔和高斯差分金字塔之后，现有技术先基于高斯差分金字塔确定SIFT关键点，再基于高斯金字塔计算SIFT关键点的梯度幅值和方向。区别于现有技术，本发明并行计算SIFT关键点以及所有像素点的梯度幅值和方向，可以加速计算过程。

具体地，梯度的幅值和方向计算方式分别为：

其中，m(x,y)为像素点的梯度幅值，θ(x,y)为像素点的梯度方向，L为关键点所在的尺度空间。

操作S12、将关键点及其对应的梯度幅值和方向分别按奇数帧和偶数帧进行存储，以实现乒乓操作。

本实施例中，在关键点检测部分，高斯金字塔和高斯差分金字塔产生模块对原始的帧图像进行高斯滤波处理，得到高斯金字塔和高斯差分金字塔，并分别在两个缓存器中存储。关键点检测模块从高斯差分图像缓存器读出高斯差分金字塔图像的像素值，进行极值点的比较找到候选的关键点，再通过阈值比较以及边缘响应的剔除，得到最终的关键点并存储在关键点缓存器。同时，梯度幅值和方向计算模块从高斯图像缓存器中读出高斯金字塔图像的像素值，对每个像素点进行梯度幅值和方向的计算并存储在梯度幅值和方向缓存器。

关键点缓存器和梯度幅值方向缓存器有两组，分别存储奇数帧和偶数帧关键点和梯度幅值和方向以实现乒乓操作。因此，整个系统的处理速度可以由关键点检测部分和描述符产生部分中处理速度较慢的部分决定。

操作S21、对每一关键点，确定其圆形邻域，并将所述圆形邻域等分为16N个区域，利用所述圆形邻域的同心圆将每一所述区域划分为两个子区域，从而得到32N个子区域。

本实施例中，以N＝1为例，如图3所示，对每一关键点，确定其圆形邻域，并将所述圆形邻域等分为16个区域，利用圆形邻域的同心圆将每一区域划分为两个子区域，从而得到32个互不重叠的子区域(R0、R1、……、R31)；图3中虚线箭头表示16个方向。

相比于现有技术基于方形进行关键点邻域划分，本发明基于圆域进行关键点邻域划分，便于后续实现主方向计算步骤和描述符产生步骤的并行化处理，即描述符产生步骤不再依赖于主方向计算步骤得到的主方向，而是可以先计算初步的描述符，通过后续的描述符重排来实现现有技术中的描述符产生步骤中首先需要按照关键点主方向进行旋转的过程。同时，区别于直接将圆形邻域等分为32个子区域，本发明将圆形邻域划分为图3所示的32个子区域，可以使得子区域中的像素点尽可能集中。

操作S22、并行计算SIFT关键点主方向以及统计32N个子区域的直方图，其中每个直方图统计16N个方向。

邻域划分之后，现有技术先计算SIFT关键点主方向，再统计各个子区域的直方图，这种串行实现的方式限制了整个系统对图像的处理速度。区别于现有技术，本发明并行计算SIFT关键点主方向以及统计各个子区域的直方图，通过后续的描述符重排来实现现有技术中的描述符产生步骤中首先需要按照关键点主方向进行旋转的过程，最后通过降维增强了描述符的鲁棒性。

操作S23、待主方向和32N个直方图均确定后，先根据主方向调整每个直方图中的16N个方向，实现每个子区域内部的旋转操作；再根据主方向调整32N个直方图之间的顺序，实现子区域之间的旋转操作；然后将每个直方图中相邻4N个方向的向量相加得到8个向量，实现每个子区域内部的向量降维；最后将32N个子区域中相邻4N个子区域的直方图数据相加得到16个直方图，实现子区域之间的向量降维，N为正整数。

本实施例中，以N＝1为例，如图4所示，待主方向和32个直方图均确定后，首先根据主方向，通过重新排序图4中(a)所示的每个直方图中的16个方向来实现图4中(b)所示的每个子区域内部的旋转操作，得到图4中(c)。接着，根据主方向调整32个直方图之间的顺序实现子区域之间的旋转操作，得到图4中(d)。然后，如图4中(e)所示，将每个直方图中的16个向量通过向量相加合并得到8个向量，得到图4中(f)，以此实现子区域内部的向量降维。最后，如图4中(g)所示，通过将32个直方图数据合并相加得到16个直方图数据，得到图4中(h)，以此实现子区域之间的向量降维。最后可以得到一个128维的向量用于表示一个关键点的SIFT描述子。

此外，本实施例中32个子区域互不重叠，相比于子区域存在重叠的情况，本发明鲁棒性更好。具体原因如下：如果事先将子区域进行重叠，如图5(A)所示，R0+R1+R2+R3为子区域S1，R2+R3+R4+R5为子区域S2；下一步应将主方向旋转到默认方向，如图5(B)所示，旋转之后，则R3+R4+R5+R6应为一个子区域。此时，会有错加的部分(R2本不该加而R6本应该加)，错加会导致描述子鲁棒性变差。

操作S24、对最终得到的128维向量归一化处理得到关键点描述子。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。