CLISTFT：基于GPU的尺度不变特征变换的优化研究外文翻译资料

CLISTFT：基于GPU的尺度不变特征变换的优化研究

摘要-尺度不变特征变换（SIFT）非常适合于图像匹配，因为它对于图像缩放和旋转的不变性，对照明或视角轻微的变化。然而，由于高的计算复杂度，在使用实时应用程序的情况下应用SIFT在技术上具有挑战性。为了解决这个问题，我们提出了CLSIFT，一种基于OpenCL加速和性能高度便携式SIFT方案。CLSIFT重要的优化技术在于如：（1）为了的到更少的全局内存通信量，逻辑独立的函数被合并到同一个内核来复用数据。（2）为了数据和中间结果重用引入了循环缓冲区。（3）在同一个分支内采用任务队列来调度线程以去除分支分歧。（4）数据分区是基于在工作群之间为了工作负载平衡的静态模式。（5）使用中央处理器时间的重叠和更好的并行策略。所有这些，使其分别对NVIDIA GPU和AMD对lena.jpg的clsift过程拥有74.2 FPS和43.4fps，远高于CPU的10 FPS左右和已知的最快SIFTGPU 的39.8 FPS和13FPS。此外，我们用定量比较的方法分析了那些成功打败了SIFTGPU的策略，一个著名的现有的GPU实现。此外，我们观察并得出结论，NVIDIA GPU由于一些因素能达到更好的占用和性能。最后，我们总结了一些其他GPU应用也能用的技术和经验性的指导原则。

关键词-SIFT；GPU；OpenCL；存储器访问；工作量；并行策略

1 介绍

图像匹配是计算机视觉中的许多应用程序的基础，包括对象或场景识别[ 1 ]，求解三维结构[ 2 ]和运动跟踪[ 3 ]，等等。1999年，戴维G. Lowe在图像匹配上提出了尺度不变特征变换（SIFT）[ 4 ]。与其他方法相比，SIFT所产生的特征经过图像缩放和旋转是不变的，对照明和三维相机的角度变化部分不变。然而，它由于复杂的计算不能满足苛刻的实时要求，在应用程序的情况下。为了克服这个问题，研究人员提出了简化算法PCA-SIFT [ 5 ]和SURF[ 6 ]。但他们为了减少计算和性能牺牲了精度和稳定性[ 7 ]，仍然不令人满意。在第3节中讨论了SIFT的细节和背景。

GPU已经成为计算密集型工作负载的理想平台。在第二节中记录了一些现有的GPU实现如SIFTGPU [ 8 ]，但他们失去了准确性而且还不完全满足苛刻的实时要求特别是对于高清图像。有一个有趣的问题是，是否存在一个优化的GPU SIFT方案能不失精度的完全解决问题。本文讨论了这个问题。在第四节，我们使用了更好的并行策略来将SIFT映射至GPU，减少了全局内存通信量，更好的内存层次开发，更少的分歧，缓解了失衡的工作量和延迟执行。他们都是精心设计以找到平衡的权衡点，导致了小的损耗和副作用。根据第五节的实验，CLSIFT在所有情况下都达到了可观的加速和性能。至于我们关注的，它比所有已知的GPU实现更快。与CPU的近10fps和SIFTGPU的39.8fps相比（一个声名鹊起的GPU实现），CLSIFT因为处理lena.jpg的72.4fps拥有绝对优势。即使是1920x1080高清图像，CLSIFT自信能达到处理速度25fps。此外，我们用定量比较的方法分析甚至改进了是那些成功打败了SIFTGPU的优化。我们评估了对AMD和NVIDIA GPU的CLSIFT并观察到，虽然他们有相似的峰值触发器和但AMD的GCN架构得到了新特性，NVIDIA的GPU实现更好的性能。从设备占用和飞行模式波前的角度，我们探讨了原因。第六节通过实践和分析，我们从CLSIFT实现得到了一些广泛的分享技术和经验的指导原则。我们也得出了GPU如何更适合哪些应用比如SIFT。

2 相关工作

在早些时候，两个OpenGL SIFT实现[ 9 ] [ 10 ]分别在10fps和20fps速度的情况下已发表了。灵感来自SIFT [ 11 ]，和[ 9 ]中的工作，支持CUDA和OpenGL的开源项目SIFTGPU[ 8 ]也已经发布了。就我们关注的而言，在CLSIFT之前SIFTGPU是在GPU上是最成熟和最快的SIFT实现。著名的SIFTGPU广泛集成到相关系统如图像搜索引擎[ 12 ]，3D建模[ 13 ]、[ 14 ]和增强现实等。所以我们比较我们的CLSIFT与著名的SIFTGPU新版本SIFTGPU V400来验证我们的方法的效率。

也有一些我们的介绍的技术现有的工作，特别是在该领域的并行策略。Timo Aila和Samuli Laine[ 15 ]提出的，持久的线程只能调用一些线程仅仅来隐藏延迟和完成所有的任务。然而，他们没有考虑到没有足够的任务来调用多线程的情况如第四节中描述的那样。此外，还有许多以前的作品[ 16 ] [ 17 ] [ 18 ]利用中央处理器重叠隐藏处理器执行。他们启发我们适当的分配CPU的任务，和隐藏花费的时间。

3 背景

3.1 SIFT算法

SIFT由于拥有许多特性使其适合于匹配不同的图像，所以在计算机视觉中起着重要的作用。要实现不变的图像缩放，旋转，和部分不变的照明和三维相机的角度变化，SIFT的设计如下。

3.1.1 高斯与变异高斯金字塔的结构

为了达到缩放的不变性，高斯金字塔和变异高斯金字塔（DoG）作为尺度空间的代表被引入到SIFT。在高斯金字塔，每倍频程的初始图像卷积的高斯反复在同一尺寸产生的图像集合，然后最后的模糊图像调整大小作为下一个倍频程初始的图像。然后卷积是一次又一次的进行。图1左边显示了整个过程。高斯卷积里，在一个特定的邻域的所有点首先乘以高斯系数然后相加得到输出像素。因为，高斯模糊可以被分成在水平方向上的一个滤波，和另一个在垂直方向上的滤波。这使得有可能执行卷积的同时，避免冗余计算。

要产生DoG图像，相邻的高斯图像要相减如图1右边所示。最后，尺度空间用高斯金字塔和DoG金字塔表示了出来。

图1 高斯金字塔（左）和DoG金字塔（右）的程序

3.1.2 关键点识别

SIFT定义关键点的3个条件：极值点，足够的对比度和足够的曲率。为了减少关键点的提取成本，SIFT由低成本和收益步骤开始逐步走向高成本的步骤。在DoG金字塔中的像素的值代表了像素与其相邻像素之间的区别度。作为最具特色的像素，在三维图2所示的27点的极值点成为了关键点候选人。然后引入门限根据他们的低对比度响应来排除关键候选人因为容易受到噪声干扰。与其直接使用像素值，SIFT采用泰勒展开（至二次项如公式1）的尺度空间函数以迭代的方式来评价极值点的值。阈值通常是0.03。

(1)

DoG有沿边缘的强烈反应，但在主边的关键点并不包括在内。为此，通过Hessian矩阵方程来消除对边缘点如公式2。曲率与Hessian矩阵的特征值有一定的关系如公式3。 稳定点的曲率半径应小于10，所以H的迹与测定值之商由于函数值随着r的增大而增大应小于12.1。

（2）

（3）

图2 27个点的极值点

3.1.3 方向计算

通过分配与周边地区相关方向的关键点，关键点可以得到旋转不变性。所以关键点的所有周边点都要计算其方向和大小。这些结果将和高斯因子一起积累到一个直方图以确定方向。

直方图平滑两次后，直方图中的最高峰值对应于梯度方向的主导方向，所以选择它为方向。其他峰值超过最高80%的地方也用于创建该方向下的关键点。

3.1.4 特征生成

通过之前的所有操作后，所有的关键点就被赋予了图像的位置、尺度和方向，导致这些参数不再变化。该特征描述还需要考虑到附近的点，使其有很高的独特性和对照明或视角具有部分不变性。为了生成特征，首先，坐标会根据关键点的方向移动。然后，计算在邻近区域的采样像素的梯度的大小和方向。这些样本和高斯因子积累到几个方向的子直方图来总结子区域的内容。最后子直方图进行归一化和平滑。

3.2 OpenCL概述

OpenCL（Open Computing Language）[ 19 ]是一个对CPU、GPU和其他处理器开放的通用并行编程工业标准。

对于计算模型，OpenCL提出了一种与传统CPU相比开关损耗可以忽略的光线。这是一个常识，基于GPU的线程数量应该很大来隐藏指令时间成本。

在OpenCL内存模型定义了全局，地方和私人三种内存空间。全局物理内存位于芯片上。只有全局内存中的常量和映像缓冲区被缓存为有效访问。本地和私人内存都在芯片上。他们快得多，但要小得多。为了实现高性能，充分利用存储器层次结构是关键。

分支分歧是GPU的一个独特问题。当相同的弯曲或波阵面上的线程采取不同的路径时，所有路径不同时执行但连续地执行。

4 CLSIFT：实现与优化

在这一部分中，我们主要在以下3个方面呈现了高度加速CLSIFT实现与现有的SIFTGPU的区别。

4.1 存储器存取

GPU具有理论峰值计算能力，所以在大多数情况下，计算部件必须等待存储器访问数据。由于这个内存墙，我们将内存访问作为第一优先级来优化。

4.1.1 合并内核减少全局内存访问流量

如3.1.1提到的，在金字塔生成内的所有图片意味着大量的全局内存访问流量都在读取和写入。繁忙的信息量是一个限制吞吐量的关键瓶颈。图3中的数据流通过显示输入和写入的输出来显示这个问题。

减少全局内存访问流量，我们用3个等级考虑合并不同的逻辑独立的内核，这取决于数据流中的数据依赖来利用快速的本地内存。

我们把2个分离方向的过滤内核合并成一个。在合并后的内核中，横向滤波的相位将中间结果写入到本地存储器，所以垂直滤波可以得到输入直接数据。

此外，数据流显示的高斯模糊输入和输出是相邻的层，准确的输入，以产生一个DoG层。尽管有逻辑上的独立性，我们也能合并减法和高斯模糊内核。因此，DoG层没有额外的阅读产生。

一个高斯模糊步骤的输出是下一个的输入，所以有机会进一步合并两个甚至多个连续的高斯模糊步骤。

然而，本地存储器的使用的更多，那么飞行的前波就越少。这是一个常识，活跃的波前数应尽可能大来隐藏执行的延迟（或运算器、存储器访问）。所以内核不能不断地合并，应考虑全局内存信息量和工作组之间的协调。通过测试，我们找到一个平衡点，只有合并2个高斯模糊的步骤和它们的减法来实现最佳性能。

图3 数据流

4.1.2 减少全局内存流量和冗余计算的循环缓冲区

在关键点辨识的过程中，整个金字塔的每个像素和它相邻像素通过访问完成辨识，导致全局存储器读取交通障碍。乍一看，自动缓存功能，图像记忆是一种声音选项来利用这个地方，siftgpu选择并从中受益。

然而，经过深入的分析，我们发现，在这种情况下，数据访问模式是高度可预测的。这是一种模式，每一个像素都必须与三维相邻26像素比较，每一层都会像以前一样，当不同的层被检测当前和下一层分别一次。在这样一个高度预测的情况下，预取所有需要的像素从全局内存到本地内存，手动缓存将是一个更好的选择，因为它的100%命中率，无缓存查询的成本和潜在的存储中间结果。

在细节上，我们在本地内存中设计并设置了3个层的循环缓冲区。我们选择穿越相同的八层而不是串行遍历法在宽度和H八在同一层图像。我们选择穿越同倍频程的层而不是在同一层图像中的宽度和高度的序列穿越方法。在穿越过程中，循环缓冲区将新层的数据更新到旧层，然后改变所有层的角色标签，如图4所示，在循环缓冲区的帮助下数据是从全局内存读取的，只有一次扮演3个角色，减少全球内存流量。

三维中所有的26相邻像素都需要比较。但我们把它转移以在这26个点中寻找极值点，以便我们可以重用将计算结果存储在循环缓冲区中。具体而言，我们首先获得额外相等的值的连续3点作为中间结果。然后，我们得到垂直连续3个点的极端值，即在一个层中相邻的9个点的极端值。最后，我们得到了三层的极值并与被检测点相比较。循环缓冲区显示它的值不仅在存储输入数据，而且还存储这些中间结果。重新利用循环缓冲区中间结果，clsift只需要平行的6个而不是26个的比较。

图4 循环缓冲循环

4.1.3 工作负载均衡

几乎所有的并行和分布式应用程序都有负载平衡问题。在相同的波阵面的分支的分歧问题，让GPU更麻烦。所以我们从2个层次考虑这个问题：在工作组，在工作组之间。

4.1.4 在一组内消除分歧以平衡工作量

作为一个SIMD风格的架构，GPU并不擅长以独特分支发散问题分支语句。在SIFT算法中，不是所有的，但有几点是极端点，应该继续计算合同响应和曲率。换句话说，当在相同的波前有额外点时，不加分那些线程将会变得空闲，这导致硬件资源的利用率变低，如图5所示。

队列和本地存储的帮助CLSIFT索引出这个问题。在工作组中波前运行到极值点时，队列的目录原子添加，然后点被存储在索引元素指示的队列。响应和曲率不会被计算，除非队列的大小大于波阵面大小超过或所有点都被检查为极端点。队列中，极端点检查与进一步计算是分开的，并且避免分支发散而且在图4的情况下，将变成图6。

将图5和图6比较，可以断定队列可以消除分歧，提高性能。队列由在本地存储器的原子操作保持在本地存储器。其实这与维护它在全局内存或将其分成多个内核有比较小的成本。其实，如果我们只保持队列但不要直接如图5中进行直接计算，时间成本并不比无队列的情况更高。所以无副作用，保持队列可以以很小的代价得到很大的好处。

图5 程序分支分歧的例子

图6 队列消除分支分歧

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[148408]，资料为PDF文档或Word文档，PDF文档可免费转换为Word