0 引言

　　随着互联网的发展，网络信息量不断膨胀。根据Cisco的预测，到2016年每月产生的数据量将超过8万PB，其中图像和视频已经成为传输和处理的主要数据类型。统计数据显示，YouTube网站每分钟有60 h时长的视频被上传，Facebook存储的图片量超过2 000亿张。如何从这些数据中提取有用的信息并进行高效的分析和处理变得越来越重要，各种新型的图像检索类应用也不断涌现。

　　图像检索主要分为基于全局特征的算法和基于局部特征的算法。基于全局特征的检索算法用一个特征数据代表整个数据，精确度低，也不能识别两幅图像中的相似元素，处理图像的伸缩和裁剪[1]。基于局部特征的检索算法通常提取成百上千个特征来描述一个图像或视帧，保证了检索精度，还能对图片的变形进行处理。SIFT算法是其中最具代表性的算法之一。而局部特征提取算法要保证处理精度，其处理速度相对缓慢。如何有效提高特征提取算法的处理速度，成为图像检索算法需要解决的关键问题之一。

　　随着半导体技术的发展和多核技术的普及，各种并行计算系统逐渐成为硬件处理平台的设计主流。图像处理单元GPGPU由于其通用性和可编程性为加速图像特征提取算法处理速度提供了机会。

　　结合图像特征提取算法面临的处理速度挑战，本文设计实现了一种基于GPGPU的SIFT并行加速算法。首先对SIFT算法的核心模块进行深入分析，并在此基础上对各个核心模块进行了有针对性的细粒度并行，以适应其在GPGPU上处理，然后通过利用GPGPU的特性对算法进行优化。最后，通过流水化CPU和GPGPU处理的任务来进一步提升系统性能。

1 SIFT算法和GPGPU简介

　　本节将简单介绍SIFT算法的基本处理过程和GPGPU基本结构。

　　1.1 SIFT算法

　　如何从大量图像和视频数据中提取有用信息并进行分析和处理变得越来越重要，各种多媒体检索应用不断涌现。

　　SIFT(Scale-Invariant Feature Transform)算法是由David Lowe于1999年首次提出并于2004年总结完善的[2]图像特征提取算法。SIFT算法提取的特征基于物体上的一些局部外观显著的特征点而生成，它的检测器在选择特征点时，已将图像缩放等情况考虑进来，而它的描述器在描述每个特征点时都会计算该特征点的方向向量。因此SIFT算法提取的特征与图像的大小和旋转无关，对于光线、噪声和轻微视角改变的容忍度也相当高，具有很强的匹配能力。目前SIFT算法已成为当前最主流的图像特征提取算法之一。

　　SIFT算法首先检测图像中的显著区域，即相比于周围的像素变化明显的部分。在此基础上结合特征点周围的信息对这些特征加以描述。如图1所示，其算法主要由特征检测和特征描述两部分组成。

　　(1)特征检测：特征检测的目标是对图像中的显著区域的特征点进行定位。为了能对图像的缩放进行处理，首先建立图像不同缩放尺寸的高斯金字塔，高斯金字塔由octave和每个octave中的interval两个层次组成，octave包含一组大小相同的图层；每个octave中的interval进行不同程度高斯模糊后用于描述不同伸缩范围下的图像特征。图像高斯差金字塔是将高斯金字塔中同一个octave的连续两个interval的图像相减而得到的。最后通过查找金字塔中的极值找到图像中显著的特征点；

　　(2)特征描述：特征描述主要对检测出来的图像特征点加以描述形成特征向量。为了提高特征点的描述范围，特征描述基于特征点及其周围像素点的信息计算特征点的方向，之后通过对特征点进行特征值的提取，生成特征向量，以完成对特征信息的描述。

　　为了保证特征点的精确性，SIFT算法通常包含复杂的处理过程，从而使其具有计算密集的特点。而随着网络带宽的增加，需处理的数据量也不断增加，已有的串行算法已经不能满足实时处理的要求。

　　为了给后继优化提供更明确的优化方向，本设计收集了SIFT算法在CPU上串行执行时各个阶段大致所需要的时间，具体如图1所示。特征描述所占的时间比例最大，占到超过3/4的时间；特征检测其次，占到近1/4的时间；加载图像和计算灰度图像只占很少的时间。

　　1.2 GPGPU简介

　　随着图形处理单元GPGPU性能的快速增长及其可编程性的不断增强，GPGPU逐渐成为一种主流的计算系统，成为一个具有强大算术处理能力的并行可编程处理器[3]。

　　GPGPU的主要厂家NVIDIA于2006年引入Tesla统一图形和计算体系结构[4]扩展了GPGPU。以NVIDIA GeForce 8800 GTX为例，其包含16个流多处理器（SM），每个流多处理器中有8个流处理器（SP）。流多处理器包含寄存器文件、共享存储器、共享的指令缓存与数据缓存、指令的读取/分发单元、特别功能单元和1个双精度浮点计算单元。

　　GPGPU作为加速部件已广泛应用于各种计算密集领域。GU L等人[5]在GPGPU上设计了一个二维和三维的傅里叶变换函数；CHEN Y等人[6]在GPGPU集群上实现一个大规模傅里叶变换算法；NAGHMOUCHI J等人[7]使用GPGPU来加速正则表达式的匹配。GPGPU的这种特性也为提升SIFT算法的处理速度提供了可能。

2 GPGPU加速算法

　　为了提升SIFT算法的处理速度，本文设计和实现了一种基于GPGPU的加速算法。

　　2.1 算核并行化

　　GPGPU具有丰富的并行计算资源，适合处理数据并行操作，需要根据SIFT每个阶段算核的特点进行有针对性的细粒度的并行。

　　SIFT算法的特征检测阶段大多是对图像进行变换和操作，各个部分之间不存在依赖关系。对于这部分算法的并行化，可以将图像划分成子块，分到不同的线程块执行。在特征描述阶段，主要对检测的特征点进行操作。这个部分算核的并行化可以以特征点为基本处理单位，由不同的线程块处理不同的特征点，然后再根据特征描述具体阶段的算法并行划分。

　　2.1.1 特征检测的实现

　　SIFT算法的特征检测由以下几个部分组成，各个组成部分并行划分后，由一个或若干个GPGPU内核加以实现：

　　(1)对图像缩放形成多个octave：将图像分成二维的图像子块，一个线程块处理图像中一个图像块。

　　(2)图像的高斯滤波：计算图像的高斯滤波分成两个步骤：①将图像分成宽度为W、高度为1的图像块，每个图像块由一个线程块处理，线程块中每个线程负责处理图像块的一列。W的值可以根据实际使用的图像选择不同的大小。②将图像分成宽度为1、高度为H的图像块，每个图像块由一个线程块处理。通过行列的分别计算，得到的结果就是高斯滤波后的图像。

　　(3)计算图像高斯差：图像被分成二维的图像块，一个线程块处理图像中特定大小(测试中使用16×16)的图像块，线程块中一个线程计算两个相邻高斯图像对应一个像素点的差值。

　　(4)寻找局部极值点：将图像（上中下3层）分成二维的图像块，每个线程块处理不同的图像块。为了记录哪些点是极值点，使用一个宽度为w（w为图片宽度）、高度为h/32（h为图片高度）的二维整数数组来进行记录。每个整数32位，每一位表示对应高度像素点是否为极值点。

　　(5)计算极值点的实际位置：把极值点分成不同的组，每组由一个线程块计算，线程块中每个线程负责计算一个极值点的实际位置。

　　2.1.2 特征描述的实现

　　SIFT的特征描述分为两部分：计算特征方向和描述特征点。特征点的计算是彼此独立的，而在计算特征方向和特征描述时，内部的计算又可以分成不同的线程，在线程块内部的线程上加以并行：

　　(1)计算特征方向：一个线程块负责计算一个特征点的方向，一个线程块包含32个线程，分别负责计算32个方向的Bin的值。最后由每个线程块中的第一个线程负责计算出32个方向Bin的最大值，作为特征点的特征方向。

　　(2)描述特征点：一个线程块描述一个特征点。在描述一个特征点时，采用的是4×4个方格，每个方格8维柱状图，一共128维的特征值向量。一个线程块中的一个线程负责一个方格的柱状图的计算。

　　2.2 基于GPGPU特性的优化

　　对SIFT进行有针对性的细粒度的并行，实现了算法的各个算核在GPGPU的并行处理。为了进一步优化算法，可以利用GPGPU的特性进行优化。

　　(1)内存和显存分配优化：在GPGPU的处理过程中，需要不停地对输入图像进行处理。减少动态的存储空间分配的次数可以有效提高性能。为了降低内存和显存的分配次数，只有当处理第一张图像或图像大小改变时才重新进行内存或显存的分配和初始化，只有图像大小改变或处理完最后一张图像后才进行释放。对于存储特征点的数组，根据特征点最大值设定一个特征点数上限，数组大小就固定了，避免了每次处理重复分配内存引入的额外开销。

　　(2)针对访存的优化：访存性能对整体处理性能影响很大。GPGPU的存储层次复杂，保证各层访问的局部性可以达到更好的性能。为此，本设计的优化包括：设计的内核不大，保证指令的局部性，因为由于寄存器具有最快的处理速度，小的内核划分尽可能让局部变量保存在寄存器中，达到最优的访存效率；一些常量频繁使用，保存在只读的常量寄存器中；将线程需要频繁使用的共享数据放到共享存储器中；由于GPGPU的纹理存储器可以实现数据的二维访问，通过绑定纹理存储器提升性能。

　　2.3 CPU与GPGPU的协同工作

　　把SIFT算法最耗时的算核部分交由GPGPU处理后，各个部分都获得较大的性能提升。算核通过GPGPU加速后通常可以获得几十甚至上百倍的性能提升。而无法交给GPGPU处理的串行部分则不能匹配GPGPU部分的执行速度，成为性能的瓶颈。

　　CPU上的核负责对图像进行预处理，GPGPU负责内核的计算。两部分串行执行，将会造成较多的彼此等待，影响整体处理性能。由于处理的图像没有相关性，GPGPU的任务可以与CPU为后继运算进行的预处理并行执行，形成流水线。这样，GPGPU只需要计算最复杂的特征检测和描述两部分，其他部分由CPU完成。

　　目前，多核的CPU处理器已经相当普遍，4核已经成为PC的通用配置。PC处理器已经有了8核乃至16核。除去控制GPGPU的核和预处理的流水线核，多核的处理器可能还有多余的核。为了使主机系统资源得到完全利用，还可以在剩余的核上运行多核版本的图像特征提取算法来提高整个系统的吞吐率。

3 实验评估

　　为了计算算法的有效性，本文对GPGPU加速算法进行了评估。

　　3.1 评估环境

　　实验中使用Rob Hess的开源实现作为SIFT的基准，以英特尔E7-4807处理器上串行处理时间作为基准，其对SIFT串行处理速度是1.53 s/帧，吞吐量是0.65 帧/s。GPGPU程序的编写基于NVIDIA CUDA编程模型。评估中使用的测试图像是MIKOLAJCZYK K提供的用来评估各种特征检测器和描述器的标准图像集合[8-9]。操作系统为Ubuntu，Linux内核版本为2.6.28-11-generic。硬件测试主要使用了两种配置：（1）主机是Intel Core 2 Quad Q8300的4核CPU，内存2 GB。GPGPU为GeForce GTX 260，共216个核，时钟率为1.24 GHz，显存的大小为1 GB。（2）主机是Intel Core i7 930的4核CPU，内存为2 GB。GPGPU是GeForce GTX 295，共480个核，时钟率为1.24 GHz，显存的大小为1 792 MB。

　　3.2 性能评估

　　在GTX 260上实现的SIFT算法，吞吐率达到39.67 帧/s，平均每张图片耗时25.21 ms，其中在CPU上所花的时间包括图像加载1.269 ms，主机对GPGPU的显存和设备管理及CPU处理的计算所花6.765 ms，其余时间是GPGPU的计算时间。

　　在GTX 295上实现的SIFT算法，吞吐率达到76.15 帧/s，平均每张图片耗时13.131 ms，其中在CPU上所花的时间包括图像加载0.440 ms，主机对GPGPU的显存和设备管理及CPU处理的计算所花3.895 ms，其余时间是GPGPU的计算时间。

　　为了更直观的比较加速效果，图2分别给出了GTX 260和GTX 295上SIFT各阶段GPGPU加速的柱形图。可以看出，各个算核在GPGPU上都有较好的加速效果，并具有较好的可扩展性。

　　3.3 整体性能评估

　　表1给出各GPGPU实现的SIFT并行版本的吞吐量以及相对于串行CPU版本的加速比。可以看到，SIFT随着GPGPU性能的增强，核数的增多，吞吐量和加速比也有相应的提升，在GTX295上达到了118.2倍的加速，吞吐量达到76.86 帧/s。从实验结果可以看出，在GPGPU上实现的SIFT算法具有良好的性能，能满足图像特征提取的实时处理需求。流水线的使用和充分利用系统剩余资源可以进一步提高系统吞吐率。

4 相关工作

　　由于串行的局部特征提取算法处理速度较慢，已有一些研究在并行硬件上分析和实现了局部特征提取算法来获得加速。ZHANG Q等人[10]针对多核系统架构提出SIFT的两种并行算法，在8核机器上达到6.4倍的性能加速效果。FENG H等人[11]的实现在16核机器上达到11倍的加速。这两者都是采用图象的分块并行。这两篇文献都对串行算法进行了局部串行优化，这些串行优化基本实现了约2倍的速度提升。这意味着在8核处理器上并行的实际加速大约为3倍，而在16核平台上的加速只有5.5倍。CHEN P等人[12]对SIFT实现了一种通用的动态流水线的并行，在开启超线程的16核处理器上对SIFT达到16.88倍加速。SINHA S[13]也在GPGPU对SIFT进行了实现，在GeForce 7800 GTX上处理640×480大小图像的速度为10 帧/s。HEYMANN S等人[14]的实现在QuadroFX 3400上达到20 帧/s。他们的实现没有充分考虑GPGPU的特性，也没有考虑到充分利用CPU资源可能对系统性能的影响。本文基于GPGPU的特性设计和实现了高效的SIFT并行加速算法，并通过充分利用CPU资源进一步提升系统性能，相比于已有的技术可以获得更大的性能提升。

5 结论

　　本文针对海量数据环境下图像检索的实时处理需求，使用新型的高性能计算硬件GPGPU来加速图像局部特征提取的SIFT算法。测试结果表明，相对于CPU上的串行版本，SIFT的实现达到了118.2倍的加速，吞吐量达到76.86 帧/s。

参考文献

　　[1] BERRANI S，AMSALEGL，GROS P.Robust content-based image searches for copyright protection[C].In Proceedings ofACM Workshop on Mul-timedia Databases，2003：70-77.

　　[2] LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：404-417.

　　[3] OWENS J D，HOUSTON M，LUEBKE D，et al.GPU com-puting[J].In Proceedings of the IEEE，May 2008，96（5）：879-899.

　　[4] LINDHOLM E，NICKOLLS J，OBERMAN S，et al.NVIDIA Tesla: A unified graphics and computing architecture[J].IEEE Micro5，Mar/Apr 2008，28（2）：39-5.

　　[5] GU L，LI X，SIEGEL J.An empirically tuned 2D and 3D FFT library on CUDA GPU[C].In Proceedings of ICS，2010：305-314.

　　[6] CHEN Y，CUI X，MEI H.Large-scale FFT on GPU clus-ters[C].In Proceedings of ICS，2010：315-324.

　　[7] NAGHMOUCHI J，SCARPAZZA D P，BEREKOVIC M.Small-ruleset regular expression matching on GPGPUs：Quantitative performance analysis and optimization[C].In Proceedings of ICS，2010：337-348.

　　[8] MIKOLAJCZYK K，SCHMID C.A performance evaluation oflocal descriptors[J].IEEE Trans.Pattern Anal.Mach.Intell，2005，27（10）：1615-1630.

　　[9] BAUER J，S?譈NDERHAUF N，PROTZEL P.Comparing severalimplementations of two recently published feature detectors[C].In Proceedings of the International Conference on Intelligentand Autonomous Systems，2007.

　　[10] ZHANG Q，CHEN Y，ZHANG Y，et al.Sift implementationand optimization for multi-core systems[C].In Parallel andDistributed Processing，2008.IPDPS 2008. IEEE Interna-tional Symposium on，2008：1-8.

　　[11] FENG H，LI E，CHEN Y，et al.Parallelization and charac-terization of sift on multi-core systems[C].IEEE Interna-tional Symposium on Workload Characterization，2008：14-23.

　　[12] CHEN P，YANG D，ZHANG W，et al.Adaptive pipeline parallelism for image feature extraction algorithms[C].In Parallel Processing(ICPP)，2012 41st International Confer-ence on IEEE，2012：299-308.

　　[13] SINHA S，FRAHM J，POLLEFEYS M，et al.GPU-based video feature tracking and matching[C].In Proc.of the 2006 Workshop on Edge computing Using New CommodityArchitectures（EDGE），Chapel Hill，NC，2006：6-12.

　　[14] HEYMANN S，MULLER K，SMOLIC A，et al.SIFT imple-mentation and optimization for general-purpose GPU[C].In WSCG′07，2007：317-322.