3SIFT算法的OpenCL实现

　　图1为并行设计的SIFT特征提取流程。整个设计充分利用全局内存以降低数据传输延时。主机端首先分配相应内存对象，然后依次入列高斯模糊、DOG金字塔和极值点检测3个OpenCL内核，完成后即可生成尺度空间和DOG金字塔，从全局优化考虑，将这两部的结果驻留在全局内存中，只返回经压缩的极值点坐标。接着按序运行极值点精确定位、特征点方向计算和特征向量生成3个步骤，计算完成后即完成特征提取全过程。整个流程仅有返回极值点坐标和返回特征点结果两次读回操作，其余的中间结果全部在显存中完成交互，提高数据利用率，降低显存带宽要求。

　　3.1高斯模糊+DOG+极值点检测内核设计

　　深入发掘算法的并行潜力，充分利用OpenCL的内存层次、合理配置工作项数量和工作组大小是性能提升的关键，也是内核设计的难点。

　　3.1.1高斯滤波内核设计及工作项分配

　　为降低计算量，将二维高斯变换分解为沿水平和垂直方向的一维变换，分解后可减少(N2-2×N)×W×H次乘法运算(N为高斯核大小，W、H为图像的宽和高)。由于每个像素相互独立，所以在NDRange函数入列高斯滤波内核时将工作项大小设置为W×H-N，即每个工作项完成一个像素的卷积。另外，进行卷积时相邻像素(图2黑实线框内数据)要重复读取图2灰色部分的数据，为提高读取效率，本文通过配置工作组，实现原始数据在局部内存中共享。图2为水平高斯核宽度为7、工作组大小设置为8时的数据分配，图2表示每8个工作组读取14个数据，完成8个点(图2黑虚线框内数据)的卷积运算。

　　在工作组内共享局部内存通常能提高计算性能，但并不绝对[18]。为找到工作组的最佳大小，本文测试了不同工作组大小时，宽度为11的高斯核对分辨率为1280×960的图片进行水平卷积的耗时，测试结果如图3所示。随着工作组的增大，耗时逐渐减少，当工作组大于128后，耗时基本不再改变，又因为局部内存的限制，工作组不宜太大，于是本文将工作组大小配置为128。如此设计需考虑同一工作组中工作项的同步化问题，本文采用OpenCL提供的barrier(CLK_LOCAL_MEM_FENCE)障碍函数来实现，垂直滤波与此类似，不再赘述。

　　3.1.2DOG金字塔构建

　　此步骤的内核有两种设计方法：1)一次入列内核，只将高斯金字塔相邻两层相减，得到一层DOG图像;2)一次入列内核，将高斯金字塔整组图像传入内核，计算完成后即可得到一组DOG图像。

　　经实验发现，第2种方法数据利用率高，耗时较短。又因为高斯金字塔每组层数固定，所以第2种设计的参数也固定，于是本文采用第2种设计方法，数据划分如图4所示。为进一步提高运算效率，对数据的运算都以float4型向量进行，共配置(W×H+3)/4个工作项，即每个工作项完成一组高斯金字塔对应位置(图4单个虚线框内数据)的float4型向量相减。

　　3.1.3极值点检测及内核精确定位

　　入列极值点精确定位内核前，主机端需预先分配内存，而事先并不知道需要为多少个特征点分配内存，所以本文将极值点检测和精确定位作为两个内核先后入列，为减少数据传输，极值点检测内核只返回压缩的极值点坐标数组。

　　极值点检测内核计算完成后，根据返回的极值点坐标在CPU端统计极值点位置和个数N，然后为N个特征点分配内存，如图5所示(实际分配1.5×N个，Lowe[1]文中指出实际的特征点数会是极值点数N的1.15倍左右)。图5中每个虚线框用来保存一个特征点的完整信息。最后入列极值点精确定位内核，每个极值点配置一个工作项，计算出的精确坐标按工作项索引存入图5对应的位置。

　　3.2计算梯度方向直方图

　　至此，已经得到每个特征点的坐标、尺度，并按线性存储在图5所示的全局内存中。因为每个特征点在内存中按线性排列，相互独立，所以为每个特征点配置一个工作组来计算梯度方向直方图，工作组分配如图6(a)所示。将工作组内工作项设置为2维，为确定工作组最佳大小，本文尝试了{1，RAD}、{2，RAD}、{4，RAD}、{8，RAD}四种方式，经测试{2，RAD}效果最好(其中RAD为特征点的邻域宽度)。当RAD=5时，每个工作组分配10个工作项，工作组中的数据分配如图6(b)所示，图6(b)中标有相同数字的像素被同一工作项处理。为实现数据共享，在工作组local_memory中构建方向直方图，这时必须使用OpenCL提供的atomic_add原子累加操作才能保证多个工作项同时累加直方图同一位置时不会出错。直方图生成后统计出大于直方图极值80%的'点的个数和角度，作为独立的候选特征点，将结果填入图5中对应的位置。

　　3.3特征向量生成

　　计算出特征点主方向后，即可入列特征向量生成内核，因数据重构后各特征点在内存中线性存储且可独立计算，所以为每个特征点分配一个工作组。又因每个特征点邻域被划分为4×4个子区域，所以为每个工作组配置16个工作项分别计算每个子区域的8个方向，数据划分如图7。图7中每个箭头的长度表示每个方向的梯度累计值，箭头越长代表值越大。所有工作组计算完毕后，整个SIFT特征提取算法执行完毕，提取出的特征点全部存储在图5所示的线性内存中。

　　利用以上方法对两幅图片进行特征提取后，即可利用欧氏距离准则完成两幅图片特征点的粗匹配，然后用随机抽样一致(RANdom Sample Consensus， RANSAC)算法对粗匹配对进行提纯，计算得到两幅图片之间的变换矩阵，完成两幅图片的匹配。

4优化后的算法在CPU上的移植

　　为进一步验证OpenCL的可移植性并比较OpenCL在不同平台上的加速性能，本文将优化后的OpenCL_GPU_SIFT算法移植为能在CPU上运行的OpenCL_CPU_SIFT版本。尽管OpenCL具有跨平台特性，但由于硬件资源的差异，仍需注意以下两点：

　　1)本文采用的Intel core i5 3210m CPU不支持OpenCL 32位原子操作，所以在3.2节的内核设计中无法使用atomic_add原子累加操作，只能将3.2节的工作组大小配置为1，此时每个工作组中只有一个工作项，因而不能实现局部内存共享。

　　2)工作组中工作项的数量上限一般受限于两点：一是设备所能提供的资源数，二是内核所需的资源数，这里的资源主要指的是局部内存。针对3.2节的内核，GT635m GPU的局部内存为47KB(K表示×1024)，工作组上限为512，而Intel 3210m CPU的局部内存只有32KB(K表示×1024)，工作组上限为352，所以工作组大小一定要根据硬件平台来设置，这点尤为重要。针对以上两点修改后得到的OpenCL_CPU_SIFT版本即可运行于Intel 3210m CPU中，可见OpenCL具有较好的可移植性。