基于OpenCL的尺度不变特征变换算法的并行设计与论文
针对尺度不变特征变换(SIFT)算法实时性差的问题，提出了利用开放式计算语言(OpenCL)并行优化的SIFT算法。首先，通过对原算法各步骤进行组合拆分、重构特征点在内存中的数据索引等方式对原算法进行并行化重构，使得计算机网络算法的中间计算结果能够完全在显存中完成交互;然后，采用复用全局内存对象、共享局部内存、优化内存读取等策略对原算法各步骤进行并行设计，提高数据读取效率，降低传输延时;最后，利用OpenCL语言在图形处理单元(GPU)上实现了SIFT算法的细粒度并行加速，并在中央处理器(CPU)上完成了移植。与原SIFT算法配准效果相近时，并行化的算法在GPU和CPU平台上特征提取速度分别提升了10.51～19.33和2.34～4.74倍。实验结果表明，利用OpenCL并行加速的SIFT算法能够有效提高图像配准的实时性，并能克服统一计算设备架构(CUDA)因移植困难而不能充分利用异构系统中多种计算核心的缺点。
0引言
以尺度不变特征变换(Scale Invariant Feature Transform， SIFT)算法[1]为代表的基于特征的图像匹配方法近几年发展迅速，该算法对光照、角度或尺度变化的图像都有较好的匹配精度和适应性，但实时性差。为了提高实时性，在此基础上又衍生出了主成分分析(Principal Component Analysis， PCA)SIFT[2]、快速鲁棒特征(Speed Up Robust Feature， SURF)检测[3]等改进算法。这些改进的算法尽管在速度方面有所提升，但实时性仍然不能满足实际应用要求且在抗尺度和抗旋转方面性能都有不同程度的下降，因此仍无法取代经典的SIFT算法[4]。
近年来随着图形处理器(Graphics Processing Unit， GPU)计算能力的不断提升，利用GPU天然硬件并行的特性来加速非图形通用大规模运算逐渐受到人们的青睐，目前较为成熟并得到广泛应用的GPU并行编程模型为英伟达(NVIDIA)公司开发的统一计算设备架构(Compute Unified Device Architecture， CUDA)模型。文献[5-7]利用CUDA实现了SIFT算法关键步骤的GPU并行加速，取得了一定的加速效果。文献[8-9]在移动GPU平台上利用开放式计算语言(Open Computing Language， OpenCL)实现了SIFT算法的并行加速，相对于移动中央处理器(Central Processing Unit， CPU)取得了4.6～7.8倍的加速效果。另外，完成同样的计算，GPU比CPU的功耗低87%，即利用OpenCL实现的GPU并行运算相对于传统的CPU具有更高的性能功耗比，但以上方法大多采用步骤分离的优化，没能充分利用GPU全局内存以及算法各步骤的中间计算结果，加速效果受显存带宽的制约。
另外利用CUDA实现的算法只适用于NVIDIA显卡，移植困难，而目前的计算机系统大多是“CPU+协处理器”的异构系统[10]，这使得CUDA无法充分利用异构系统中不同类型的计算核心。具有跨平台特性的开放式并行编程语言OpenCL的出现为解决此问题提供了契机，利用OpenCL设计的并行算法能够在CPU+(GPU、数字信号处理器(Digital Signal Processor， DSP)、现场可编程门阵列(FieldProgrammable Gate Array， FPGA)等异构系统间移植[11-12]，该特性使得经OpenCL优化的算法能够摆脱对硬件平台的依赖。自2010年OpenCL1.1发布以来，对OpenCL技术的应用研究逐渐兴起。陈钢等[13]对OpenCL内存操作作了深入的分析;Yan等[14]利用OpenCL实现了SURF算法的并行加速。OpenCL编程相比CUDA更为复杂[15]，在软件开发方面也面临更多的挑战和困难，目前在PC平台上还没有利用OpenCL并行优化的SIFT算法出现。
针对以上问题，本文对SIFT算法步骤及数据索引方式进行重构，提高其并行度，然后通过优化内存读取、合理利用OpenCL内存层次等策略对该算法进一步优化，在NVIDIA GPU平台上实现了SIFT特征的快速提取。为研究OpenCL的可移植性，将优化的GPU版本移植到Intel双核CPU平台上，实验表明优化后的算法在两种计算平台上的实时性都有一定提升。
1SIFT特征提取算法流程
SIFT算法最早由Lowe[1]在1999年提出并于2004年完善，由于其良好的匹配特性，目前已得到广泛研究与应用。SIFT特征点提取实质是在不同尺度空间上查找关键点(特征点)，算法基本步骤如下。
1)尺度空间构建。
2)高斯差分金字塔空间构建。
3)DOG空间极值点检测。
DOG空间极值点检测就是将DOG图像中每个像素与它同尺度的8邻域点及上下相邻尺度对应的9×2个邻域点进行比较，若为极值点则作为候选特征点，记录其位置和对应的尺度。为获得更精确的特征点位置，在候选特征点处进行泰勒展开，得到式(4)：
D(x)=D+DTxx+12xT2Dx2x(4)
其中：关键点偏移量为x此处的偏移量x，与后面的x的命名重复，不太规范，因一篇论文中，一个变量仅能代表一个含义，若包括两个含义，则指代不清晰，是否可以用另一个变量对此进行说明?
回复：这两个变量x是使用字体来区分的，一个是粗斜体表示向量，一个是细斜体，表示普通变量。是可以区分的。
这个公式是经典文献[1]中此算法的原作者提出的公式，也是用这种方式表述的。为保持统一，所以我觉得可以不用修改。=(x，y，σ)T;(x，y，σ)在该极值点处的值为D;令D(x)x=0，可通过式(5)求得极值：
=-2D-1x2Dx(5)
在Lowe[1]的文章中当在任意方向上的偏移量大于0.5时，认为该点与其他关键点很相似，将其剔除;否则保留该点为候选特征点，并计算该点对应的尺度。
4)特征点主方向计算。
5)SIFT特征矢量生成。
将特征点邻域内图像坐标根据步骤4)计算出的特征点主方向进行旋转，使得特征向量具有旋转不变性，旋转后以特征点为中心划分成4×4个子区域，在每个子区域内计算8方向的梯度方向直方图，即可构成4×4×8共128维SIFT特征矢量。
2SIFT算法的并行化重构
OpenCL标准将内核可用的内存分为私有内存、局部内存和全局内存/常量内存等类型[16]，所以在利用OpenCL优化算法时，充分挖掘GPU内存的存储层次，合理分配工作组大小是提高并行运算效率的关键[17]。为提高算法并行度方便数据划分、降低内存带宽要求，本文对SIFT算法作了以下重构。
1)步骤合并。将构造尺度空间、创建高斯金字塔及极值点检测三步骤统一设计，目的是充分利用OpenCL的global memory和local memory的访问机制，使得这3个步骤的中间计算结果最大限度地在显存中完成交互，减少内存与显存间的数据交换次数，隐藏带宽延时。
2)步骤拆分。将极值点定位分为极值点坐标检测和极值点精确定位两步：第1步只返回极值点坐标，目的是辅助主机端完成内存分配;第2步完成极值点精确定位。
3)重构数据索引。本文全面摒弃基于队列的特征点索引方式，而是采用线性存储的方式管理特征点集，这对OpenCL内核的工作项划分、提高数据读取效率以及降低内存访问冲突都非常有效。
4)任务细粒度并行。经过数据索引重构，在OpenCL的内核运行时，可方便地部署大规模的工作组和工作项，实现计算任务的细粒度划分。经过以上设计后不仅能提高数据访问速度，而且能够避免潜在的内存访问冲突。