HartSift: A High-Accuracy and Real-Time SIFT Based on GPU
- 作者：Zhihao Li; Haipeng Jia; Yunquan Zhang
- 机构：中国科学院
- 年份：2017
- 期刊/会议：International Conference on Parallel and Distributed Systems (ICPADS)
- 原文地址：HartSift A High-Accuracy and Real-Time SIFT Based on GPU
尺度不变特征变换 (SIFT) 是最流行和最强大的特征提取算法之一，因为它对尺度、旋转和光照保持不变。它已被广泛应用于视频跟踪、图像拼接、同时定位和映射（SLAM）、运动结构（SFM）等领域。然而，高计算复杂度限制了其在实时系统中的进一步应用。这些系统必须在准确性和性能之间进行权衡以实现实时特征提取。他们采用其他更快但精度较低的算法，如 SURF 和 PCA-SIFT。为了解决这个问题，本文提出了一种使用 CUDA 的 GPU 加速 SIFT，命名为 HartSift，充分利用单机CPU和GPU的计算资源，实现高精度、实时的特征提取。实验表明，在 NIVDIA GTX TITAN Black GPU 上，HartSift 可以根据图像的大小在 3.14-10.57ms (94.61-318.47fps) 内处理图像。此外，HartSift 分别比 OpenCV-SIFT（CPU 版本）和 SiftGPU（GPU 版本）快 59.34-75.96 倍和 4.01-6.49 倍。同时，HartSift 的性能和 CudaSIFT（迄今为止最快的 GPU 版本）的性能几乎相同，而 HartSift 的准确度远高于 CudaSIFT。
Ⅰ 介绍
SIFT算法可以提取大量显著特征，这些特征在缩放、旋转、光照和3D视点保持不变，还提供了跨越噪声和仿射失真的稳健匹配。但SIFT的高计算复杂度限制了其在大规模数据和实时系统中的进一步应用。而复杂度较低的算法，如SURF、PCA-SIFT的准确性又不太高。因此，在主流计算平台上实现高精度、实时的SIFT是一个重要而有意义的研究课题。
而SIFT算法具有很好的并行性，可以正确移植到GPU上。因此，在配备GPU的异构计算系统上实现高性能的SIFT具有重要的实用价值。
SIFT 算法包含三个阶段，包括高斯差分（DoG）金字塔的构建、精确的关键点定位和 128 维描述符生成。由于每个阶段都有自己的并行特性，因此必须使用不同的并行粒度和优化来实现高性能。尤其是后两个阶段，负载不平衡不利于GPU优化，会导致性能下降。
本文的主要贡献和创新可以概括如下：
在 GPU 上开发了 CUDA 版本的 SIFT 算法，满足高精度和实时计算机视觉应用的苛刻要求。
引入了两种优化（重新平衡工作负载和多粒度并行）来解决将 SIFT 移植到 GPU 平台时的负载不平衡问题。两者也适用于其他负载不平衡的图像算法。
在GPU上提出了两种高性能直方图算法（基于warp的直方图算法和无原子直方图算法）来有效地积累样本的信息。
Ⅱ 相关工作
有许多工作尝试在GPU上使用SIFT算法。
- Heymann使用并行SIFT在NVIDIA Quadro FX 3400 GPU获得17.24 fps的处理速度。
- Warn使用OpenMP和CUDA在NVIDIA Quadro FX 5800 GPU获得1.9倍加速。
- Sinha的GPU-SIFT在NVIDIA GeForce 7800 GTX GPU上获得比CPU版本大约10倍的提速。
- Wu开源了SIFT-GPU，在NVIDIA GeForce 8800 GTX GPU上获得27.22 fps的帧速。
- Acharya提出GPU SIFT，在NVIDIA Tesla S1070 GPU约有13.36fps的处理速率。
- Bjorkman在NVIDI-A GeForce GTX 580 GPU上可以达到78.74 fps的处理速率。
然而，为了实现高性能，他们省略了 SIFT 算法的一些重要步骤，例如将输入图像加倍、保持尺度变化的连续性和拟合二次函数以定位准确的关键点信息。作者的实验表明，这些遗漏会导致 SIFT 丢失很多关键点和准确性。
Ⅲ 算法概述
A. 构造高斯差分金字塔
Lowe将输入图像尺寸加倍作为高斯金字塔的最底层，每个尺度
通过高斯卷积产生：
- 高斯金字塔Octave
由图像大小决定；
- 每个Octave包含
层，因此尺度空间一共包含
张图；
- 每一个Octave的第一张图由上一个Octave的第
层的下采样。
高斯金字塔确定之后，利用相同Octave的层级相减，得到差分金字塔：
其中，在本文中，
.
B. 准确的关键点定位
检测尺度空间极值
将DoG金字塔每个像素与相邻像素比较，同层8个，上下层9个，若像素是局部最大值或局部最小值，将其视为关键点候选。
去除无效关键点
去除较低对比度和不稳定边缘响应的候选关键点，通过将3D二次函数拟合到附近数据执行子像素插值，以获取精确的位置、比例和主曲率比。
方向分配
将候选关键点周围的梯度累积到36 bins的直方图中，根据每层的尺度计算搜索半径。每个紧邻像素由一个高斯加权窗口加权，梯度方向累计到36 bins的方向直方图中。峰值为主要梯度方向，同时超过峰值80%的局部峰值bin也被视为关键点方向。
C. 生成描述符
对关键点周围像素计算梯度直方图，搜索半径比上一步骤大得多，同样用一个高斯加权函数用于为每个邻居的梯度值分配权重。
根据梯度方向将最终的梯度值累积到一个 360-bin 的圆形方向直方图。最后，直方图将被归一化、平滑并转换为 128D 描述符。
Ⅳ 实现与优化
A. 构造高斯金字塔
构建金字塔应该保持顺序，以保证尺度空间变化连续性。Acharya和Bjorkman为加快这一过程，牺牲准确性打破构建顺序。考虑到不能使准确性降低，构建顺序在HartSift中保留。
分离卷积核
对于大小的卷积核处理
大小的图像需要进行
次运算，如果将2D卷积核拆解为两个1D的卷积核，计算量减少至
. 通过使用共享内存和向量化方法，更容易实现合并全局内存访问并减少一维卷积的冗余访问。
Uber 内核
Uber内核将多个不同任务放到一个物理内核中，在一个内核中并行处理任务，而不需要在内核之间切换。差分金字塔第层由高斯金字塔第
和第
层决定。将高斯差分金字塔和高斯卷积核封装在单个核中，可以充分挖掘并行性。
线程不需要重复读取高斯金字塔第层的值，这是由于第
层的值计算完后，结果会放在寄存器内而不是全局内存中。借助Uber内核的优势，我们可以节省
的空间和
的内核运行时间
异构并行
HartSift 采用异构并行方法来加速这一阶段。CPU 和 GPU 将并行协作，构建 DoG 金字塔。
由于GPU处理小图像没有优势，作者将以下的图像放到CPU处理，大图像放到GPU处理。用户也可以自行设置分离点，确保CPU和GPU负载平衡。
B. 准确的关键点定位
存在两个问题：
- 检测候选关键点将导致两个级别的负载不平衡：经线间负载不平衡和经线内负载不平衡。
- 方向分配部分的核心操作是为关键点构造直方图，如何为相对较小的样本集构建直方图。
负载均衡
Warp是GPU最小并行执行单元，即以锁步方式执行的 32 个线程的集合。若负载不均衡，则warp执行时间取决于最后一个线程完成的时间，warp负载不均衡会导致GPU效率降低。
由于候选关键点分布的随机性，几乎所有经线都包含不同数量的空闲线程。如果这些warp继续处理以下部分，就会出现两个级别的负载不平衡.
在去除无效的候选关键点部分时，线程将进行亚像素插值以获得准确的候选关键点信息，从而去除具有低对比度或不稳定边缘响应的关键点候选。换句话说，一些线程会比其他线程更早返回一次。负载不平衡会变得更加严重。
为了突破性能瓶颈，HartSift 引入了重新平衡工作负载和多粒度并行优化。
重新平衡工作负载
当检测到负载不平衡时，HartSift 将通过启动具有适当粒度的新内核并分派每个具有 32 个活动线程的新经线来重新平衡工作负载。
此外，启动三个内核分别处理这三个部分，不仅可以重新平衡工作量，还可以根据不同部分的并行特性提供多粒度的并行。
多粒度并行
重新平衡工作负载优化保证每个内核中的线程和经线被完全加载，多粒度并行优化保证工作负载将平均分配到线程和经线。此外，不同内核的并行粒度取决于工作负载的特性。
HartSift通过将一个线程映射到一个或多个像素，采用与关键点候选检测部分和无效关键点去除部分并行的线程粒度。然而，线程粒度并行会导致方向分配部分的负载不平衡，因为不同关键点的相邻区域半径不同。线程粒度并行会为单个线程分配过多的工作，这在某些情况下限制了硬件资源的利用率。所以在这部分应用混合粒度并行：扭曲粒度构建直方图，线程粒度找出并将主导方向分配给相应的关键点。
基于扭曲的直方图算法
作者针对每个关键点提出了一种基于扭曲粒度和原子操作的高性能直方图算法，以充分利用局部性。
C. 生成描述符
该阶段关键点的邻域半径远大于前一阶段。需要为每个关键点累积数千个邻居到一个 360-bin 直方图。如果采用前一阶段的基于原子扭曲的直方图算法，会对这一阶段的性能产生不同的影响。
HartSift引入了一种atomic-free的直方图算法，进一步提升了这一阶段的性能。
该算法包含三个步骤：
- 采用无原子的多密钥约简来累积所有邻居的信息。同一个warp内的线程可以通过使用warp级别的指令直接相互通信，例如shuffle/vote内在指令，而不是使用全局/共享内存。
- 设置一个名为captain thread 的线程来保存每个bin的部分和，然后让这些captain 线程将它们的部分warp 结果累积到驻留在共享内存中的本地直方图，在每次迭代时没有任何bank 冲突和本地同步。
- 在处理完所有邻居之后，warp 中的线程将与任何原子操作同时将本地直方图复制到全局内存。无原子直方图算法伪代码如下：
为了消除线程间的负载不平衡，实现全局合并访问，HartSift 使用一个warp 来处理一个keypoint 的所有邻居。当线程计算出它们的方向 bin 时，它们需要根据bin变量的值将梯度值累加到局部直方图。考虑到有如此多的邻居并且一个经线的一些线程可能具有相同的 bin，算法1引入了一种无原子的多键约简方法来累积每个经线的部分和。这种方法可以利用warp级shuffle和vote指令完全消除原子操作和本地同步。它根据bin对经纱的线程进行分组并指定每组具有最低车道的线程作为队长线程。队长线程将保存他们自己的 bin 的部分总和，并将它们并行地累积到驻留在共享内存中的本地直方图，而不会发生 bank 冲突和同步。在遍历所有邻居后，HartSift 将最终的局部直方图复制到驻留在全局内存中的全局直方图。
Ⅴ 评估
Ⅵ 结论
本文提出了一种GPU上的并行SIFT，命名为Hart-Sift，它可以在单机内同时使用CPU和GPU来实现高精度和实时的特征提取。HartSift根据每个阶段的不同特点，通过适当采用不同的优化策略来提升性能，例如负载均衡、基于warp的直方图算法和不同尺度样本的atomic-free直方图算法等。在NVIDIA GTX TITAN Black GPU上，HartSift可以在3.14 ~ 10.57ms（94.61 ~ 318.47fps）内提取高精度特征，轻松满足高精度和实时性的苛刻要求。另外，与OpenCV-SIFT和SiftGPU相比，HartSift获得了59.34 ~ 75.96倍和4.01 ~ 6.49倍加速分别。同时，HartSift 和 CudaSIFT 的性能几乎相同，但 HartSift 远比 CudaSIFT 准确。
