A streaming hardware architecture for real-time SIFT feature extraction
- 作者：Hector A. Li Sanchez; Alan D. George
- 机构：匹兹堡大学
- 年份：2021
- 期刊/会议：2021 International Conference on Field-Programmable Technology (ICFPT)
- 原文地址：A streaming hardware architecture for real-time SIFT feature extraction
尺度不变特征变换 (SIFT) 是一种特征提取器，可作为许多计算机视觉管道中的关键步骤。基于纯软件方法的实时操作通常是不可行的，但可以使用 FPGA 来并行执行和加速应用程序以满足延迟要求。在这项研究中，我们提出了一种用于 SIFT 特征提取的基于流的硬件加速架构。使用一种新颖的策略来存储描述符计算所需的像素，与以前的设计相比，生成 SIFT 描述符所需的执行时间大大缩短。该策略还通过引入多个处理元素 (PE) 来并行计算多个 SIFT 描述符，从而进一步减少执行时间。此外，所提出的架构支持任意数量的octave的关键点检测，并允许各种参数的运行时配置。部署了针对 Xilinx Zynq-7045 片上系统 (SoC) 器件的 FPGA 实现，以展示所提议架构的效率。在目标硬件中，最终系统能够以高达 150 FPS 的速度处理分辨率为 1280 × 720 像素的图像，同时保持适度的资源利用率。
Ⅰ 介绍
视觉特征提取仍然是许多计算机视觉处理管道中的一个基本阶段。使用特征提取的应用示例包括图像配准、3D 重建以及同步定位和映射 (SLAM)。大多数传统的特征提取管道使用手工制作的算法，例如尺度不变特征变换 (SIFT) 、定向快速和旋转简要 (ORB) 和加速鲁棒特征 (SURF) 。最近，基于深度学习方法的特征提取器也有人提出过，尽管大多数具有实时要求的嵌入式应用程序仍然依赖于手工制作的特征，因为与深度卷积神经网络相关的计算成本很高。
SIFT 特征对尺度、旋转和光照的变化具有鲁棒性，这使得它们非常受欢迎。然而，诸如 ORB 之类的紧凑二进制功能在嵌入式应用程序中通常是首选，因为 SIFT 的大多数软件实现无法满足实时要求。为了克服这个问题，大量的研究致力于使用硬件加速 SIFT。特别是，基于 FPGA 的架构在加速 SIFT 特征提取以满足性能要求方面取得了一些成功。然而，文献中使用的硬件优化策略通常会降低结果描述符的质量。这种质量下降消除了使用 SIFT 优于其他鲁棒性较差的特征提取器的主要优势。此外，SIFT 描述符的计算往往成为处理瓶颈。
在这项研究中，我们提出了一种新颖的 SIFT 特征提取架构，能够以高达 150 FPS 的速度处理 1280×720 图像，资源利用率适中。FPGA 块 RAM (BRAM) 资源的双端口配置允许在不停止关键点检测流水线的情况下计算 SIFT 描述符，从而显着提高了先前设计的性能。据我们所知，本研究还首次在 FPGA 上实现了 SIFT 描述符的平方根归一化。该架构在 Xilinx Zynq-7045 片上系统 (SoC) 上实现，该系统具有双核 ARM Cortex-A9 CPU 和 Kintex 7 系列 FPGA 结构。对系统的描述符质量、执行时间和资源利用率进行性能评估，以评估建议优化的影响。
Ⅱ 背景
在本节中，我们简要回顾了 SIFT 特征提取。这包括突出显示算法和相关计算的主要步骤。
SIFT关键点检测
SIFT 算法流程的第一步是构建高斯差分 (DoG) 金字塔，用于关键点检测。首先，通过对输入图像与式(1)中的二维卷积核
进行卷积来创建尺度空间金字塔。每个高斯滤波器的标准差
由基准标准差
计算，然后依次乘以一个常数因子
生成每个后续
.
在我们的设计中，尺度空间金字塔包含五个尺度，遵循 SIFT 算法的原始作者的建议，使用基础标准偏差和一个常数因子
. 对应于最后一个尺度的高斯图像被下采样并用作金字塔中下一个octave的输入图像。这个过程可以重复任意次。为了构建DoG金字塔，尺度空间金字塔中的每个高斯图像都从对应于下一个尺度的图像中减去。
在计算完DoG金字塔之后，通过执行非极大值抑制来选择候选关键点。对于 DoG 金字塔中的每个像素（不包括第一个和最后一个尺度），创建一个 3×3×3 的窗口，该窗口由当前和相邻尺度内的相邻像素组成。如果点是该窗口内的局部极值并且幅度大于某个阈值，则它们被选为候选关键点。
一旦选择了一个点作为候选关键点，就会执行另一个测试以拒绝具有强边缘响应的特征，以提高稳定性。首先Hessian矩阵 的迹和行列式在候选关键点位置处使用二阶梯度计算。这个过程可以在（2）到（4）中观察到。根据这些值，使用(5) 中的不等式评估候选关键点的边缘响应。如果不等式为真，则选择该点作为特征。变量
用作阈值参数，可以调整以修改检测器的灵敏度。
SIFT描述子计算
每个 SIFT 描述符的计算是使用来自尺度空间金字塔的高斯图像执行的，该图像对应于检测到关键点的倍频程和尺度。首先，将主要方向分配给关键点，以便特征描述符不受旋转变化的影响。为了实现这一点，每个像素的梯度方向和幅度在以关键点位置为中心的窗口补丁中计算。然后，计算由 36 个均匀间隔的 bin 组成的方向直方图。选择幅度最大的 bin 作为主要方向。
下一步包括计算 SIFT 直方图。关键点位置周围正方形区域中的每个像素根据指定的主方向旋转。接下来，该区域以 4×4 的正方形图案划分为 16 个子区域。区域的大小取决于检测到关键点的比例。为每个子区域计算由八个 bin 组成的方向直方图。三线性插值用于将每个像素的幅度分布到相邻的直方图箱中。将 16 个直方图连接起来以产生一个由 16 × 8 = 128 个值组成的非标准化向量。
最后，描述符被归一化，每个向量条目被量化为 8 位，创建最终的输出描述符。在最初的 SIFT 实现[1] 中，使用L2范数。然而，有文献进一步研究表明，平方根归一化 (rootSIFT) 会产生更准确的特征描述符。对于 rootSIFT 归一化，每个条目首先除以L1范数。然后，计算每个值的平方根以产生最终的归一化值。
Ⅲ 相关工作
以前的研究已经探索了用于实现 SIFT 特征提取的硬件架构。有人提出了一种用于 SIFT 关键点检测的并行硬件架构。使用基于流的方法在 FPGA 上计算 DoG 金字塔和梯度方向/幅度图像。然而，描述符计算是通过使用软核处理器在软件中执行的，这造成了显着的处理瓶颈。有人提出了一种用于 SIFT 检测的硬件架构，该架构在单个卷积块中对多个倍频程进行交错处理。这种设计也缺乏用于计算 SIFT 描述符的硬件架构。因此，这种设计无法实时运行。为了解决计算 SIFT 描述符的处理瓶颈，有人提出了一种基于 SIFT 关键点和简要描述符的实时特征提取架构。通过使用BRIEF二进制描述符，作者能够在FPGA上实现完整的特征提取，实现1280×720视频60 FPS的实时处理。然而，本研究中使用的简要描述符对旋转和比例的变化并不稳健，限制了架构的实际使用。
一些方法不是使用完全不同的特征描述符，而是修改部分 SIFT 算法以实现实时计算。有人介绍了用于图像分类的 SIFT 特征提取的 FPGA 实现。他们设计的性能受到描述符计算的限制，对于每个检测到的特征需要。有人提出了一种窗口分割方法，无需旋转即可重新排序描述符直方图。尽管他们的设计可以在 512 × 512 图像上实现实时性能，但整个图像帧必须存储在 BRAM 中，这使得处理高分辨率图像不切实际。此外，研究中使用的 15 × 15 描述符窗口不够大，无法确保在大规模变化时的稳健性。因此，整体描述符质量降低。有人提出了一种用于 SIFT 特征提取的架构，该架构完全流水线化描述符计算步骤。使用这种架构，无论特征数量如何，作者都能实现恒定的执行时间。然而，完全流水线化描述符计算会导致高资源利用率。对于此设计，需要超过 100,000 个查找表 (LUT)，相当于所用目标设备中大约 80% 的可用资源有人采用了类似的方法. 在这个实现中，SIFT 描述符的计算也完全流水线化，成本超过 600 个数字信号处理器 (DSP) 和 60,000 个 LUT。这些设计中的高资源利用率还会导致路由拥塞，最终会降低设计的工作频率并限制性能。
在硬件中计算 SIFT 描述符最具挑战性的方面是主要方向分配和直方图计算所需的大滑动窗口。在考虑先前的研究时，可以根据用于实现描述符窗口缓冲区的资源对设计进行分类。基于寄存器的方法使用寄存器的二维数组来实现滑动窗口。这种方法的优点是可以同时访问窗口中的所有像素，并且可以完全流水线化以允许在不停止关键点检测流水线的情况下计算描述符。这种方法的缺点是资源利用率高，组合逻辑路径长。另一方面，基于 BRAM 的方法，通过在片上存储器资源中存储像素值来实现滑动窗口。这种方法资源高效，但性能有限，因为一次只能访问一个像素值。因此，每次计算描述符时都必须停止关键点检测管道。对于大量功能，计算描述符所需的延迟增加可能会超出应用程序的要求。这项研究的一个主要动机是设计一种架构来平衡这两种方法，以最大限度地提高系统的性能。
Ⅳ 系统架构
提议的 SIFT 加速器架构利用了 Zynq SoC 的处理系统 (PS) 和可编程逻辑 (PL) 区域。整体系统架构如图1所示。CPU 通过高级可扩展接口 4 - Lite (AXI4-Lite) 接口管理直接内存访问 (DMA) 控制器、SIFT 关键点检测器和 SIFT 描述符计算机 IP 的配置。该系统通过一系列流运行。在图 1，假设所有流都将数据移入/移出 DDR 存储器，但在实际应用中，输入图像可以直接从摄像机传输。关键点检测可以以串行方式针对任意数量的八度音程执行，因为用作下一个检测octave基础的图像被写入输出流。以下小节讨论 SIFT 加速器的 FPGA 实现，重点介绍用于最大化性能的硬件优化。
A.加速器配置
建议的架构中有几个配置参数，以适应各种应用程序的需求。可以通过 AXI4-Lite 接口从 CPU 修改多个运行时参数。最大输入分辨率是静态定义的，以确定行缓冲区的大小，但实际输入分辨率可以在运行时通过写入图像大小寄存器来更改。此外，还可以在运行时修改关键点检测期间的非最大抑制和边缘抑制阈值，以调整关键点检测器的灵敏度。最后，用于 SIFT 描述符计算的处理元素 (PE) 的数量可以静态指定，其中更多的 PE 会以更高的资源利用率为代价导致更短的执行时间。
B.DoG金字塔的构建
图 2 显示了用于关键点检测的流式架构图. 为了计算 DoG 金字塔，尺度空间中的每个高斯图像都是并行构建的。为了降低资源利用率，利用高斯核的可分离性将每个 2D 卷积计算为两个跨图像行和列操作的 1D 卷积。首先执行垂直过滤步骤，以便在所有尺度上共享实现行缓冲区所需的资源。每个高斯核的系数被转换为定点表示（8 个整数位和 8 个小数位），以便有效地执行卷积。对应于第一尺度的高斯图像被写入用于计算 SIFT 描述符的输出流。下一个倍频程的输入是通过将对应于最后一个比例的高斯图像向下采样两倍并将其写入输出流来计算的。一系列减法器用于从尺度空间金字塔计算 DoG 金字塔。由此产生的架构为 DoG 金字塔中的每个图像生成一个流，并且每个周期可以处理一个输入像素。
C. SIFT 关键点的选择
DoG 金字塔流被送入一系列关键点选择模块以检测 SIFT 关键点。每个模块包含两个并行执行非最大抑制和边缘抑制测试的数据路径。对于非极大值抑制，为每个尺度实例化一个 3 × 3 滑动窗口，将相邻尺度组合起来形成 3 × 3 × 3 窗口。为了执行边缘拒绝测试，使用滑动窗口计算 DoG 图像的二阶梯度，将结果流输入另一个模块，该模块计算(3)、(4)和(5) 中所示的公式。
每个测试都会产生一个单位输出，指示是否应该拒绝该点。如果两个测试都通过，则将包含结果关键点的倍频程、比例、行/列位置和响应强度的 64 位值写入输出流。通过在所有尺度上并行执行检测，系统能够以每个周期一个像素的速率执行关键点检测步骤，而不管检测到的特征数量如何。
D. SIFT 描述符的并行计算
根据先前的研究，很明显 SIFT 描述符计算是主要瓶颈。该问题与用于主要方向分配和 SIFT 直方图计算的描述符窗口的大尺寸有关。为了使用 BRAM 实现描述符窗口，而不会因每次计算描述符时暂停关键点检测管道而导致性能下降，我们提出了一种以并行 PE 为中心的新架构。建议的架构示意图如图 3所示. 在这个架构中，由于两个优化，执行时间得到了极大的改善。首先，利用 BRAM 的简单双端口配置大大减少了计算描述符时的停顿周期数。此外，此配置允许引入独立的 PE，它可以并行计算多个 SIFT 描述符。
E. 描述符窗口缓冲区
为了计算每个 SIFT 描述符，一个 15 × 15 的窗口用于主要方向分配，而一个 31 × 31 的窗口用于创建 SIFT 描述符直方图。由于滑动窗口的尺寸很大，使用 BRAM 在环形缓冲区结构中存储来自图像的 31+ 行比实例化大量寄存器更有利。通过在计算高斯图像时将数据流式传输到此缓冲区，描述符窗口缓冲区包含在任何给定时间为位于 31 × 31 窗口中心的关键点计算描述符所需的所有像素。在以前的工作中，使用单端口 BRAM 来实现缓冲区。对于本文档的其余部分，我们将把这种实现称为朴素架构。在图 4，一系列概念图说明了这种朴素架构的局限性，以及我们提出的解决方案如何解决这一局限性。在每个图中，KPT和DSC 分别代表关键点检测和描述符计算管道的操作。与检测到的关键点位置对应的像素用字母标记。
在简单的实现中，不可能将新像素写入描述符窗口缓冲区，同时从缓冲区读取描述符计算所需的像素，因为只有一个内存端口。每当计算一个描述符时，关键点检测管道必须完全停止，直到计算出整个描述符。因此，整体执行时间将随着特征的数量线性增加，从而降低系统的性能。在我们的架构中，这对应于每个特征 1,382 个周期的延迟。计算每个 SIFT 描述符所需的时间在图 4 中通过五个周期的延迟进行了说明。
F. 方向和幅度计算
方向和幅度 (OriMag) 窗口是连续生成的，首先计算用于主要方向分配的窗口。使用 3 × 3 滑动窗口计算图像的一阶梯度，然后将其连接到另一个并行计算幅度和方向的管道。所需的反正切和平方根运算使用作为 Xilinx IP 库一部分提供的 CORDIC IP 模块作为定点函数实现。输入梯度存储为 9 位有符号整数，输出幅度存储为 10 位有符号整数，输出方向存储为 6 位无符号整数，对应于 5.625 度增量。
G. 主要方向分配
为了计算主方向，OriMag 窗口中的每个值都用于创建方向直方图。使用包含 32 个 bins 而不是 36 个 bins 的方向直方图，这简化了将 OriMag 窗口中的每个数据点分配到 bin 的过程。在计算直方图时，一个简单的比较器电路会跟踪幅度最大的 bin 索引。一旦处理了整个窗口，就会声明一个标志以指示主方向有效并且可以开始主描述符直方图的计算。
H. 直方图计算
SIFT 描述符直方图的计算方式与主要方向分配类似，一次处理一个样本。然而，由于所需的旋转和三线性插值，需要更复杂的电路来累加直方图。实现旋转，每个样本的坐标相对于窗口中心根据主要方向使用（6）和（7）旋转
. 一个小的查找表用于计算主方向角的正弦和余弦，因为该角度仅限于 32 个离散值。
对于三线性插值，每个数据点可能对描述符向量中的最多八个条目有贡献。因此，使用 8 个 BRAM 阵列来累积 SIFT 描述符直方图，每个阵列包含 128 个条目。对于每个数据点，旋转坐标每个数据点的方向和方向用于计算幅度在八个 bin 索引中的分布情况。每个 BRAM 阵列都可以独立访问，因此可以流水线化累积以处理每个周期的一个数据点。处理完整个窗口后，使用加法器树将来自八个 BRAM 阵列的值相加，然后将包含未归一化 SIFT 描述符的 128 个条目的阵列流式传输到下一个模块。
I. 描述符归一化
完整的未归一化直方图流入最终模块，该模块执行归一化，如在 rootSIFT 中所做的那样。输入首先转换为浮点表示并存储在单个 BRAM 单元中，而直方图的L1范数是并行计算的。浮点运算是使用Xilinx IP 库中可用的模块实现的，这些模块利用专用 DSP 资源来提高面积效率。直方图中的每个条目除以L1范数，然后是平方根运算。最后，归一化的条目从浮点数转换为定点数表示并量化为八位。使用一系列 FIFO 和多路复用器将来自每个 PE 的输出合并为单个输出流。
Ⅴ 性能评估
所提议架构的实现是用 VHDL 编写的，并部署在包含 Zynq-7045 SoC 的 Xilinx ZC706 开发板上。FPGA 比特流是在 Vivado 2019.1 版中使用默认综合和实现设置生成的。CPU 时钟频率设置为 800 MHz，而 SIFT 加速器和 DMA 控制器的 FPGA 时钟频率分别设置为 225 MHz 和 100 MHz。对于软件基线，使用了 OpenCV 3.4.0 版中的 SIFT 实现。默认情况下，SIFT 的 openCV 实现使输入图像分辨率加倍，这显着增加了执行时间。禁用此功能以确保在软件基线和建议的架构之间进行公平比较。使用了 Zynq PS 中的两个 ARM Cortex-A9 内核。
所提出架构的性能评估由四部分组成。首先，将硬件加速器生成的 SIFT 描述符的质量与软件基线进行比较。验证对 SIFT 算法执行的修改不会影响描述符的质量至关重要。其次，在各种配置下测量加速器的执行时间特性。第三，收集建议系统中每个组件的资源利用数据。最后，将所提出架构的性能与以前的设计进行比较。
A. 描述符质量
在特征提取的上下文中，评估结果描述符质量的最简单方法是执行图像匹配任务。对于此任务，使用具有已知单应性的一对图像来测试检测可跨多个场景识别的特征点的能力。在这项研究中，我们使用了流行的仿射协变特征数据集。特征匹配结果的示例如图 5所示。我们从每个图像对中提取特征，并尝试通过最近邻搜索找到对应关系。然后，已知的单应性用于计算正确匹配的数量。
评价结果如表I所示。从这些数据中，可以观察到所提出的系统的性能与软件基线相似。对于某些序列，FPGA 获得了比软件基线更多的对应关系；这可能是由于引入了平方根归一化。
B. 执行时间
通过测量在 1280 × 720 图像上执行特征提取所需的时间，对所提出架构的运行时性能进行了基准测试。关键点检测以两个倍频程分辨率进行。尽管对于给定分辨率，关键点检测的执行时间是固定的，但总执行时间将根据计算的描述符数量而变化。因此，我们使用许多图像和检测阈值来执行特征检测，以收集范围广泛的检测特征的执行时间数据。在表二，我们提供每个配置在选定操作点的平均性能。正如预期的那样，提议的实施明显快于软件实施。此外，我们还提供了与使用单端口内存的简单实现的比较。通过利用双端口 BRAM，仅使用单个 PE 就可以实现比原始实现高达 32% 的加速。当引入多个 PE 时，这种加速会增加。具有四个 PE 的配置（本研究中使用的最大数量）可以计算 3,000 个 SIFT 描述符，同时仅将整体执行时间增加约 1.5 毫秒。相比之下，使用原始架构计算相同数量的描述符需要 18.4 毫秒的额外执行时间。
为了进一步探索使用多个 PE 的影响，我们将我们提出的设计在各种配置下的描述符计算时间与图 6 中的简单实现进行了比较。从这些数据中，可以得出一些结论。
当检测到的特征数量较少时，关键点的位置足够稀疏，因此所提出的双端口 BRAM 配置策略几乎可以消除所有停顿周期。这对应于具有多达 1000 个特征的图像的所有配置的加速急剧上升。当检测到的特征数量变大时，由于增加的关键点密度导致消除停顿周期的机会减少，加速开始下降。当使用更多 PE 时，性能开始下降的点会增加。对于极其大量的关键点，实现的加速缓慢地接近与所使用的 PE 数量相等的因子。这种退化发生得足够慢，以至于在实际应用中预期的特征计数范围内实现了显着的加速。
C. 资源利用
表 III 中分别显示了 DMA 控制器、SIFT 关键点检测器和 SIFT 描述符计算机用于不同数量的 PE 的资源利用率数据。这些值是使用 Vivado 设计工具的实施后报告获得的。即使在最大配置下，所提议的架构也非常适合Zynq-7045 SoC的可用资源（如表 III中括号中所示）。
Ⅵ 性能对比
在表 IV 中，我们将我们的性能结果与先前的研究进行了比较。我们包括我们提出的最小和最大配置架构的性能数据——分别包含一个和四个描述符 PE。执行直接比较的一个挑战是各种研究中图像分辨率和目标硬件的可变性。但是，仍然可以从数据中得出一些结论。
在考虑检测时间时，所有设计的吞吐量都是每个周期一个像素。这意味着执行关键点检测所需的时间大约等于图像中像素总数除以工作频率。因此，在比较实现时，应考虑各种设计中使用的不同图像大小。从表 IV中可以看出，除了图像尺寸为 320 × 240 像素之外，所提出的设计的检测时间比所有其他作品都低。对于这样的分辨率，所提出架构的检测时间测量为 0.49 毫秒。因此，我们的关键点检测器优于所有以前的设计。
描述时间通常报告为每个描述符的时间，期望总描述时间与检测到的特征数量成线性关系。这是因为大多数设计使用串行结构来实现描述符计算，并在每个描述符的计算过程中完全停止关键点检测管道。[9]中显示的实现不包含描述符体系结构，因此没有为其报告描述时间数据。[10]中的实现使用了BRIEF描述符而不是SIFT描述符，但这里仍然报告了描述时间数据以供比较。对于[13]、[14]中的设计，描述符是使用完全流水线化的并行结构计算的，因此每个特征的时间只是时钟周期。如观察到的图6中，所提出的实现每个功能的时间取决于检测到的特征的数量。为了提供与其他设计进行比较的方法，我们在检测到 3,000 个特征时计算每个特征的时间，这提供了描述时间的最坏情况估计。对于具有一个 PE 的配置，我们的架构的描述时间比基于串行结构的实现中的一种都短。除了使用完全并行结构进行描述符计算的实现之外，具有四个 PE 的配置优于所有实现。
无法对资源利用率进行直接比较，因为每种资源类型的内部结构可能因 FPGA 供应商和器件系列而异。但是，可以看出，与其他实现方式相比，所提出的设计通常显示出适度的资源利用率。正如预期的那样，由于描述符计算的完全并行化，[13]、[14] 中的设计具有明显更高的资源利用率。
Ⅶ 结论
本文提出了一种用于实时 SIFT 特征提取的最先进的 FPGA 加速器架构，并分析了其在描述符质量、执行时间和资源利用率方面的性能。仔细考虑以确保提议的架构产生与软件实现质量相当的 SIFT 描述符。通过专注于提高任务级并行性而不是减少计算量，所提出的架构的执行时间比以前的设计有了很大的改进，而不会影响提取特征的质量。利用片上 BRAM 资源的双端口配置，无需完全并行的结构即可显着减少描述时间，这导致了可以部署在低资源 FPGA 上的面积高效设计。此外，所提出的通过任务级并行来改善描述时间的概念可以应用于其他局部特征描述符。
所提出的设计能够以高达 150 FPS 的速度对 1280×720 图像执行 SIFT 特征提取。这种性能使 SIFT 特征能够在多个应用程序中使用，否则无法实时实现特征提取。未来的研究将侧重于扩展提议的架构，为自主导航应用程序设计完整的处理管道。
