基于GPU的SIFT算法耗时改进研究

文君城

（四川大学计算机学院，成都610065）

0 引言

在图像配准算法中，主要有分为两大类的配准方法：基于区域和基于特征的图像配准。在基于区域的图像配准方法中，可以分为基于空间域和基于变换域这两大类，基于空间域的配准方法的思想是，利用图像的灰度信息，通过某种查找算法，来确定一个变换模型可以使两图像间的相似区域的相似性测度达到最大。这种思想的算法优点是操作简单，而问题是首先计算量极大，需要以全图做相似性测度估计，并且受噪声的影响很大且不能解决旋转、缩放等问题；基于变换域的算法思想则是，根据傅里叶变换的平移不变性，将空间域上的像素的平移转换到了频域上相位的平移，该类算法优点是相对基于空间域的配准算法，解决了旋转和尺度缩放的问题，但是缺点则是其适用范围有限，一般对配准图像的重合度要求较高，且实现较为复杂。

基于特征的配准算法以其适用范围的广泛性、更高的鲁棒性以及更快的计算速度，成为如今更为主流的配准算法。与基于区域的算法相比，基于特征的配准算法不需要使用到图像的全部信息，只需要使用到诸如轮廓、角点或是特征点的部分信息，故而计算量大为降低。其中尺度不变特征变换（SIFT）算法[1～2]以其高鲁棒性、稳定性和强适应性，成为了如今图像配准算法中使用最为广泛的算法，诸多改进算法诸如PCA-SIFT[3]、Harris-SIFT[4]乃至SURF[5]算法，都是基于SIFT算法的思想而提出。针对SIFT算法计算量大并且具有较高的时间复杂度的问题，提出一种降低时间复杂度及运算量的改进SIFT算法。实验结果表明，该改进算法在具有较高的鲁棒性的前提下，运行速度大为提升。

1 SIFT算法介绍

SIFT算法的思想是，通过降采样和高斯函数构造尺度空间，再在差分金字塔中提取潜在极值点作为特征点并去除干扰点，根据特征点邻域内的像素的梯度作为特征点的描述符，最后根据计算特征向量的欧氏距离作为匹配的特征点对，该特征点具有尺度不变性、旋转不变性，以及光照不变性，是SIFT算法的主要优点。下面简单介绍一下SIFT算法的实现。

1.1 尺度空间中检测关键点

SIFT算法通过对图像降采样，并且使用高斯函数[6]G(x ,y,σ ) 对图像 I(x ,y)做卷积，构建图像尺度空间L(x ,y,σ )，公式如下：

其中：

σ0是高斯正态分布的标准差初始值，一般建议取值为 1.6；t∈[0 , …，T-1]，T是高斯图像金字塔的总级数，并且T=log[ ]min(X,Y)-2，X×Y为原图像尺寸；，s为每级金字塔的尺度空间层数，并且s>3。

通过对图像降采样和高斯函数卷积形成高斯金字塔后，在高斯金字塔每一级中相邻尺度图像两两相减，得到高斯差分金字塔（DoG），即：

其中 fi，i∈[0,s]，是尺度空间图像，最后构建出级数为T，每级包含有s-1层图像的DoG高斯差分金字塔。

特征点的检测即是在DoG高斯差分金字塔中进行的。每一个像素点会和它上下相邻3×3范围像素点内所有相邻点作比较，当某像素点的灰度值为该范围内的极值时，该点则为潜在特征点。再将位于曲率较低的边缘特征点剔除，通过拟合特征点所在的行和列的像素灰度值曲线，最终确定特征点的实际位置，得到最终的特征点。如图1所示。

图1特征点检测

1.2 特征点描述

确定特征点的位置之后，为使其保证旋转不变性，将为特征点指定方向参数。SIFT算法中，首先在特征点附近的一个圆形邻域内（一般选取3×1.5σ为半径）计算每个点的梯度和角度，根据角度作为横坐标计算直方图，纵坐标为幅值的叠加，选取纵坐标最大的方向作为特征点的主方向；再选取特征点16×16范围内为邻域，再将16×16邻域划分为16个4×4的子领域，在16个子领域内以45度为间隔，统计8个角度区间内的梯度幅值之和作为子领域的种子点，如图2所示；16个种子点各有8个方向，共构成8×16共128维的特征点描述符，如图3所示。最后对128维的特征向量归一化，去除光照的影响以保证光照不变性。

图2由特征点邻域梯度信息生成种子点

图3特征点128维描述符

2 改进的SIFT算法

为确定在SIFT算法中，在各个算法步骤具体哪些步骤最为耗时，通过将算法步骤分为：尺度空间建立、极值点检测、关键点主方向分配、特征描述4个步骤，并选取了3种不同分辨率的3张图片，经过实验，统计了各个步骤不同分辨率图片情况下的耗时在总耗时中的平均占比情况，如表1。

表1不同分辨率下SIFT算法各步骤耗时对比

从表中可以看出，随着分辨率的增大，可检测到的特征点数成倍上升，耗时也在成倍的增加。SIFT算法具体实现步骤中，最为耗时的步骤是极值点检测（包含去除边缘响应点及通过拟合函数来确定特征点的位置及尺度）的过程，占了总耗时一半以上的时间。而相对来说，SIFT算法中尺度空间的建立和特征点的128维描述符也是比较耗时的步骤，两步骤耗时占比也占了40%以上。通过对算法实现的分析，大致造成以上情况的原因如下：

原因1：构建尺度空间具有一定的复杂性，需要不断的降采样和高斯卷积，构建的层数越多，耗时也越多。

原因2：关键点是由DoG空间的局部极值点组成的，而关键点的初步探查是通过对同一组内各个DoG相邻两层图像之间的比较完成。为了寻找DoG函数的极值点，每一个像素点都要和它所有相邻的点比较，看其是否比它的图像域和尺度域相邻的点大还是小。而这映射到算法实现上，则是通过一个三重循环来实现的，需要分别遍历相邻上下两层及各层3×3区域内所有像素点，故而是个时间复杂度很大且计算量庞大的实现过程，耗时严重。

原因3：为了保证旋转不变性，SIFT中的描述子使用在关键点尺度空间内4×4的窗口中计算8个方向的梯度信息，共4×4×8=128维的向量来表征，而分辨率越大，图像信息越复杂，可检测到的特征点也就越多，为每一个特征点分配一个128维的特征向量描述符计算量过大，造成耗时严重。

针对上述SIFT算法在实现过程中存在的问题，提出一种基于GPU的SIFT改进算法，具体改进措施为：

（1）针对SIFT算法中构建尺度空间及极值点检测计算量大的问题，基于GPU强大的并行计算能力，提出使用GPU加速尺度空间的建立及在差分金字塔中检测极值点两步骤的实现。

（2）针对SIFT算法中，特征点的128维描述子维数过高，计算量过大的问题，提出一种以带权值的圆形梯度计算区域取代原算法中的4×4方形区域，将128维描述子降为64维描述子，在保证一定旋转不变性前提下降低数据量以提升算法运行效率。

2.1 SIFT算法GPU实现

（1）GPU 简介

图形图像处理单元GPU（Graphic Processing Unit），NVIDIA公司于1999年发布GeForce256图形处理芯片的时候首次提出了GPU的概念，是由硬件实现的，一个专门的图形的核心处理器。相较于CPU而言，CPU的架构设计注重的是程序执行的效率，大部分为控制器和寄存器，擅长的是如操作系统、通用应用程序这类拥有复杂的指令调度、循环、分支或是逻辑判断等复杂的程序任务。而GPU的架构则是面向适合于矩阵类型的数值计算而设计的，拥有更多的ALU（Arithmetic Logic Unit，逻辑运算单元）用于数据处理，其架构设计复杂度远低于CPU，其最大的优势是处理大量同类型数据的密集计算，例如图形数据的矩阵运算[7]。CPU在执行计算任务时，同一时刻只会处理一个数据，不存在真正意义上的并行。而GPU具有多个处理器核，可以同时并行处理上千个没有逻辑关系的数值计算线程。GPU具有强大的浮点数编程和计算能力，在计算吞吐量和内存带宽上远超CPU，即当算法中具有大量无逻辑联系的密集计算，且可并行处理的计算部分时，通过使用GPU加速，可以大大提升算法的运算效率。

（2）GPU加速SIFT算法过程

由表1分析所得SIFT算法各步骤的耗时情况，且由于GPU加速的数据处理并行条件约束，并不是所有步骤都适用于采取GPU进行加速，故将采取GPU+CPU混合实现的方式[8]，通过GPU加速SIFT算法中尺度空间的创建及极值点的检测过程，再将处理数据传回CPU，进行主方向分配，再通过降维的特征点描述子算法获取描述符。具体实现流程如下。

首先图像上传GPU设备端，分析构建尺度空间并行性可知，假设高斯金字塔有s组，每组有o层的图像，首先对每层图像的高斯卷积是互不影响的，可以并行实现；其次，每一组的各层图像降采样也只依赖于第0层的第一张图像尺寸，故对每层图像的降采样也可并行执行；所以在构建高斯金字塔时，对每组每层的降采样及模糊操作都可GPU加速处理。得到高斯金字塔后，由于每个差分金字塔的构建过程只跟其相邻上下两层有关，因此也可并行化差分金字塔构建。具体实现步骤为：线程格按二维地址排序，每个线程格（block）含16×16个线程，给图像每一像素绑定一个线程ID，每一像素都和高斯核的所有元素（由外部输入）相乘并累加权值，而多次使用的变量使用共享内存进行缓存，将得到的高斯模糊结果存入全局存储器中。此后，按照高斯金字塔不同层和不同组，交由不同的线程块（block）处理，并行计算得到各个像素的差分值后，最后整合所有block的值，得到差分金字塔，再将每层图像划分为16×16的块，而线程块对应16×16的结构设计，以减少循环次数，而对图像不是16×16的倍数的情况按补0处理。这样每一个线程对应求取一个极值点。最终将极值点传回CPU端。

考虑到对极值点的过滤、对关键点的定位以及对关键点主方向的分配，GPU端对于处理分支、判断等逻辑语句的效率较低[9]，故需将极值点检测结果传回CPU端，而CPU端和GPU端之间数据传输也是一个较为耗时的操作，为保证CPU端及GPU端只需一次数据传输以减少时间损耗，提出一种降维的特征点描述子算法来优化SIFT算法的效率。

2.2 改进的特征描述符

借鉴于SURF算法中基于圆形的特征描述符的区域选择，且由于圆形区域自带的良好的旋转不变性[10]，在获得关键点特征描述符的过程中，提出一种采用圆环形取代原SIFT算法中方形区域的方法以降低描述符的维数达到降低计算数据量，减少获取特征描述符的耗时。

图5圆形的特征描述构造

如图5所示，考虑到所选取的环形区域对特征点的描述贡献，距离特征点越近的区域描述特征点的贡献越大[11]，故在基于16×16的关键点邻域内，考虑采用（3，2，2，1）的环数构造，距离关键点最近的局域设置为3环，而距离关键点最远的区域设置为1环，由此划分为4个环形区域。具体实现步骤如下：

（1）建立以关键点为中心的16×16像素点领域区域，按（3，2，2，1）的环数构造划分为 4 个环形区域。

（2）以36度为间隔，统计4个环形区域10个方向的梯度累加值，得到4×10共40维的特征向量。

（3）为了降低光照对特征向量的影响，最终对其做归一化处理，使用公式为：

其中di为各特征向量，D为归一化后的向量。

（4）考虑到可能存在大梯度的异常特征向量影响，设定一个阈值，对梯度差值大于阈值的描述符做舍弃处理，经过实验，阈值取经验值0.12。

3 实验结果

为了检测改进算法的特征检测效果，以及改进算法的特征检测在速度上的提升，实验主要通过对三组不同分辨率的图片进行改进算法的特征检测实验，与原算法对比其特征检测效果及具体耗时情况。

图6不同分辨率实验组图

实验首先统计了改进算法各步骤耗时情况，并与原算法各步骤耗时进行了比较，如表2所示。

表2不同分辨率改进算法与原SIFT算法对比

实验结果表明，改进算法检测到的特征点数量相比于原算法，由于对算法相关参数并未改变，所以相差无几，这说明改进算法继承了原算法对图像特征检测方面的优越性，保证了改进算法的特征检测精度。其次，耗时情况上，使用GPU加速的建立尺度空间和极值点检测两步骤耗时降低最为明显，相比于原算法表1，平均加速比达到了20倍以上。而对于改进的特征描述耗时，大约与原算法相比，有近一倍的提升。体现在总耗时上，改进算法总耗时相比于SIFT原算法，有5倍以上加速比。

其次，实验针对特征检测描述效果，也做了相应对比实验，如图7所示：

图7不同分辨率下特征描述对比

通过实验，首先改进算法的特征描述对于大梯度下的异常特征向量有一个很明显的区分。其次，改进算法的特征描述较原算法而言，对于轮廓的描述稍有不足，但仍有不错的局部描述效果，且在耗时情况上有一个很大的提升。

4 结语

针对SIFT算法计算量大，耗时严重的问题，提出了一种基于GPU和降低描述子的改进算法。首先通过提取出SIFT算法中可并行部分，使用GPU加速该部分计算来提升运算速度，其次，改进了特征点的描述构造，采用圆形取代方形，降低了特征描述维度来加快运算速度。实验表明，本改进算法在保证特征点检测精度的前提下，稍降低了特征描述精度，但在耗时方面大为提升，保证了原算法大致鲁棒性的情况下，本算法具有了更快速的特点。