CN104732221A - 一种基于OpenCL并行加速的SIFT特征匹配方法 - Google Patents

Abstract

本发明涉及一种基于OpenCL并行加速的SIFT特征匹配方法，它包括SIFT特征匹配并行计算、基于OpenCL的棋盘式卷积运算和工作节点的任务分配及映射，具有将许多计算分割在CPU和GPU之间分别计算，发挥了各自的计算优势，充分体现了CPU+GPU异构计算的强大能力，实时性高，具有可移植性的Sift特征匹配并行算法实现了平台无关性。

Description

一种基于OpenCL并行加速的SIFT特征匹配方法

技术领域

本发明属于遥感机理与方法技术领域，具体涉及一种基于OpenCL并行加速的SIFT特征匹配方法。

背景技术

在过去的几十年里，国内外研究人员主要集中在通过购买以具有高运算速度的单核CPU为计算核心的服务器、工作站等设备，多核CPU计算平台的应用，采用单指令多数据流技术的并行处理结构等几种方式来加快信息处理速度，然而由于制造工艺技术的制约以及CPU架构本身设计目标的局限，性能的提升很快就碰到了技术壁垒，同时SIFT特征匹配算法复杂度高，导致影像匹配计算时间长，匹配速度较慢，因此，一方面，传统计算资源和计算加速方法已经难以满足遥感影像SIFT特征匹配实时处理的需求，在实时性要求较高的应用场合中，应用受到了限制，另一方面，由于硬件平台间互不兼容，软件跨平台可移植性差的问题凸显。

发明内容

本发明的目的在于克服现有技术的不足而提供一种处理速度快、兼容性能好、使用范围广的一种基于OpenCL并行加速的SIFT特征匹配方法。

一种基于OpenCL并行加速的SIFT特征匹配方法，它包括SIFT特征匹配并行计算、基于OpenCL的棋盘式卷积运算和工作节点的任务分配及映射，所述的SIFT特征匹配并行计算包括如下步骤：

步骤1：首先读取输入影像到主存，将不同尺度的高斯核数据由主存传入到GPU的常量存储器中，在GPU中进行分步连续滤波加速高斯尺度空间金字塔的构建，并将高斯金字塔存储在全局存储器内，然后高斯金字塔影像被回读到CPU，相邻尺度的两个高斯影像相减得到DOG金字塔多尺度空间表示，当把候选特征点集合信息上传至GPU中后，便可在GPU内对高斯差分金字塔所有候选特征点进行精确定位，计算关键点周围影像强度的主曲率，通过一个2×2的Hessian矩阵计算特征值比率，检测关键点主曲率是否超过设定的阈值，通过去掉多余的点后，确定关键点集合并精确标记关键点的位置和尺度，关键点位置、尺度将在GPU中恢复；

步骤2：利用在GPU中计算的关键点集合信息，启动kernel计算在关键点附近像素的梯度大小和方向，利用已经存储在全局存储器中的高斯权重函数，对关键点邻域窗口内的各像素的梯度大小进行高斯加权并累加建立方向直方图，检测直方图的峰值，确定关键点主方向；

步骤3：计算128维的SIFT描述符，以关键点为中心的16×16影像数据块根据关键点的尺度、位置和方向构造SIFT描述符的过程，在CPU上实现则可以发挥CPU逻辑分支、判断能力强的优势，高效地完成任务；

步骤4：SIFT特征匹配，确定匹配点位，按照原始点的自然顺序将维度数据读入本地存储器，优化的重点是距离计算，首先必须保证每个维度差值的平方在同一时刻被计算，而不是使用内循环方式，其次保证维度数目的中间结果的累加方式高效；

所述的基于OpenCL的棋盘式卷积运算包括如下步骤：

步骤1：卷积乘计算，在内核gaussConvolution启动后，待处理的影像数据就存放在全局存储器中，高斯核函数数据存放在常量存储器中，工作组中各个工作节点将对应的全局存储器和常量存储器的数据取出完成卷积乘运算后存入本地存储器中，根据单指令多线程执行模型的工作原理可知，活动warp是以时间片分配的，工作节点调度程序定期从一个warp切换到另一个warp，以最大限度利用多处理器的计算资源，只有指令中全部操作数就位的warps拥有执行资格，调度协议按照优先级选择其中一个warp执行，各个warp之间的执行次序是不确定的，可以是任何次序，由于在同一个warp中的这32个工作节点是被绑定在一起执行同一指令的，这意味着warp中的每个工作节点传递的都是指令库中的相同指令，指导工作节点执行一些操作或操纵GPU存储器；

步骤2：积的累加计算，当工作组中所有工作节点卷积乘计算完毕后，采用并行归约求和算法计算出影像中某个像素点的卷积值，最后将计算结果通过主机端控制从设备端转移到主机端的内存；

所述的工作节点的任务分配及映射包括如下步骤：

步骤1：卷积并行中工作节点的任务分配及映射，根据卷积运算中卷积乘相互无关的特性，卷积并行最自然的想法是每一个卷积乘由一个工作节点计算，即每个工作节点负责将一个像素值与高斯模板值相乘，由于在卷积并行中采用并行缩减求和算法计算影像中某个像素点的卷积值，因此每个工作节点还将负责一对卷积乘乘积值的求和，通过get_group_id二维索引向量和get_local_id一维索引向量来寻址：

const unsigned int tid＝get_local_id(0)；

const int baseAddress＝get_group_id(1)*col+get_group_id(0)+tid；

const int offset＝col_GAUSS_MODELDIM；

步骤2：剔除边缘点并行计算中工作节点的任务分配及映射，在候选特征点检测完成后，形成了一个线性数据结构集合，因此可以分配一个工作节点去完成是否剔除一个边缘点的判断，通过OpenCL在每个工作组中开辟512个工作节点并行判断是否保留该候选特征点，工作节点地址映射关系如下所示：

const unsigned int tid＝globalWorkSize[0]*get_group_id(0)+get_local_id(0)；

步骤3：欧氏距离并行计算中工作节点的任务分配及映射，关键点的128维描述子可以看成是一个线性数据结构集合，因此可以分配一个工作节点去完成一对相应维度的差平方计算，通过OpenCL在每个工作组中开辟128个工作节点并行计算出每一对维度的差平方值，并将结果保存到本地存储器中，由于在欧氏距离并行中采用并行缩减求和算法计算距离，因此每个工作节点还将负责一对差平方值的求和，此处的工作节点地址映射关系如下所示：

const unsigned int tid＝get_local_id(0)

const unsigned int bid＝get_group_id(0)；

所述的SIFT特征匹配并行计算为SIFT特征匹配GPU并行化处理计算模式。

所述的基于OpenCL的棋盘式卷积运算为一个顺序运算的过程。

本发明具有以下优点：随着影像像幅的降低和滤波窗口的增大，GPU的加速效果十分明显，影像对进行SIFT特征匹配单GPU运算的总加速比高，具有密集的计算任务和工作量大的特点，并通过优化达到最佳效果，另外基于OpenCL的SIFT特征匹配算法通过并行性分析，将许多计算分割在CPU和GPU之间分别计算，发挥了各自的计算优势，充分体现了CPU+GPU异构计算的强大能力，实时性高，具有可移植性的Sift特征匹配并行算法实现了平台无关性。

附图说明

图1为本发明一种基于OpenCL并行加速的SIFT特征匹配方法的SIFT特征匹配并行算法执行模式示意图。

图2为本发明一种基于OpenCL并行加速的SIFT特征匹配方法的棋盘式卷积乘示意图。

图3为本发明一种基于OpenCL并行加速的SIFT特征匹配方法的不同影像像幅SIFT特征匹配GPU加速效率趋势图。

图4为本发明一种基于OpenCL并行加速的SIFT特征匹配方法的不同滤波窗口SIFT特征匹配GPU加速效率趋势图。

图5为本发明一种基于OpenCL并行加速的SIFT特征匹配方法的SIFT特征匹配效果的对比示意图。

具体实施方式

下面结合实施例对本发明作进一步的说明。

实施例1

如图1、图2、图3、图4和图5所示，一种基于OpenCL并行加速的SIFT特征匹配方法，它包括SIFT特征匹配并行计算、基于OpenCL的棋盘式卷积运算和工作节点的任务分配及映射，所述的SIFT特征匹配并行计算包括如下步骤：

步骤1：首先读取输入影像到主存，将不同尺度的高斯核数据由主存传入到GPU的常量存储器中，在GPU中进行分步连续滤波加速高斯尺度空间金字塔的构建，并将高斯金字塔存储在全局存储器内，然后高斯金字塔影像被回读到CPU，相邻尺度的两个高斯影像相减得到DOG金字塔多尺度空间表示，当把候选特征点集合信息上传至GPU中后，便可在GPU内对高斯差分金字塔所有候选特征点进行精确定位，计算关键点周围影像强度的主曲率，通过一个2×2的Hessian矩阵计算特征值比率，检测关键点主曲率是否超过设定的阈值，通过去掉多余的点后，确定关键点集合并精确标记关键点的位置和尺度，关键点位置、尺度将在GPU中恢复；

步骤2：利用在GPU中计算的关键点集合信息，启动kernel计算在关键点附近像素的梯度大小和方向，利用已经存储在全局存储器中的高斯权重函数，对关键点邻域窗口内的各像素的梯度大小进行高斯加权并累加建立方向直方图，检测直方图的峰值，确定关键点主方向；

步骤3：计算128维的SIFT描述符，以关键点为中心的16×16影像数据块根据关键点的尺度、位置和方向构造SIFT描述符的过程，在CPU上实现则可以发挥CPU逻辑分支、判断能力强的优势，高效地完成任务；

步骤4：SIFT特征匹配，确定匹配点位，按照原始点的自然顺序将维度数据读入本地存储器，优化的重点是距离计算，首先必须保证每个维度差值的平方在同一时刻被计算，而不是使用内循环方式，其次必须保证维度数目的中间结果的累加方式高效；

所述的基于OpenCL的棋盘式卷积运算包括如下步骤：

步骤1：卷积乘计算，在内核gaussConvolution启动后，待处理的影像数据就存放在全局存储器中，高斯核函数数据存放在常量存储器中，工作组中各个工作节点将对应的全局存储器和常量存储器的数据取出完成卷积乘运算后存入本地存储器中，根据单指令多线程执行模型的工作原理可知，活动warp是以时间片分配的，工作节点调度程序定期从一个warp切换到另一个warp，以最大限度利用多处理器的计算资源，只有指令中全部操作数就位的warps拥有执行资格，调度协议按照优先级选择其中一个warp执行，各个warp之间的执行次序是不确定的，可以是任何次序，由于在同一个warp中的这32个工作节点是被绑定在一起执行同一指令的，这意味着warp中的每个工作节点传递的都是指令库中的相同指令，指导工作节点执行一些操作或操纵GPU存储器；

步骤2：积的累加计算，当工作组中所有工作节点卷积乘计算完毕后，采用并行归约求和算法计算出影像中某个像素点的卷积值，最后将计算结果通过主机端控制从设备端转移到主机端的内存；

所述的工作节点的任务分配及映射包括如下步骤：

步骤1：卷积并行中工作节点的任务分配及映射，根据卷积运算中卷积乘相互无关的特性，卷积并行最自然的想法是每一个卷积乘由一个工作节点计算，即每个工作节点负责将一个像素值与高斯模板值相乘，由于在卷积并行中采用并行缩减求和算法计算影像中某个像素点的卷积值，因此每个工作节点还将负责一对卷积乘乘积值的求和；

下面是算法中涉及到的数据结构向OpenCL映射后的具体描述，通过get_group_id二维索引向量和get_local_id一维索引向量来寻址：

const unsigned int tid＝get_local_id(0)；

const int baseAddress＝get_group_id(1)*col+get_group_id(0)+tid；

const int offset＝col_GAUSS_MODELDIM；

步骤2：剔除边缘点并行计算中工作节点的任务分配及映射，在候选特征点检测完成后，形成了一个线性数据结构集合，因此可以分配一个工作节点去完成是否剔除一个边缘点的判断，通过OpenCL在每个工作组中开辟512个工作节点并行判断是否保留该候选特征点，这里的工作节点地址映射关系如下所示：

const unsigned int tid＝globalWorkSize[0]*get_group_id(0)+ger_local_id(0)；

步骤3：欧氏距离并行计算中工作节点的任务分配及映射，关键点的128维描述子可以看成是一个线性数据结构集合。因此可以分配一个工作节点去完成一对相应维度的差平方计算。通过OpenCL在每个工作组中开辟128个工作节点并行计算出每一对维度的差平方值，并将结果保存到本地存储器中。由于在欧氏距离并行中采用并行缩减求和算法计算距离，因此每个工作节点还将负责一对差平方值的求和。此处的工作节点地址映射关系如下所示：

const unsigned int tid＝get_local_id(0)

const unsigned int bid＝get_group_id(0)；

随着影像像幅的降低和滤波窗口的增大，GPU的加速效果十分明显，影像对进行SIFT特征匹配单GPU运算的总加速比高，具有密集的计算任务和工作量大的特点，并通过优化达到最佳效果，另外基于OpenCL的SIFT特征匹配算法通过并行性分析，将许多计算分割在CPU和GPU之间分别计算，发挥了各自的计算优势，充分体现了CPU+GPU异构计算的强大能力，实时性高，具有可移植性的Sift特征匹配并行算法实现了平台无关性。

实施例2

如图1、图2、图3、图4和图5所示，一种基于OpenCL并行加速的SIFT特征匹配方法，它包括SIFT特征匹配并行计算、基于OpenCL的棋盘式卷积运算和工作节点的任务分配及映射，所述的SIFT特征匹配并行计算包括如下步骤：

步骤1：首先读取输入影像到主存，将不同尺度的高斯核数据由主存传入到GPU的常量存储器中，在GPU中进行分步连续滤波加速高斯尺度空间金字塔的构建，并将高斯金字塔存储在全局存储器内，然后高斯金字塔影像被回读到CPU，相邻尺度的两个高斯影像相减得到DOG金字塔多尺度空间表示，当把候选特征点集合信息上传至GPU中后，便可在GPU内对高斯差分金字塔所有候选特征点进行精确定位，计算关键点周围影像强度的主曲率，通过一个2×2的Hessian矩阵计算特征值比率，检测关键点主曲率是否超过设定的阈值，通过去掉多余的点后，确定关键点集合并精确标记关键点的位置和尺度，关键点位置、尺度将在GPU中恢复；

步骤2：利用在GPU中计算的关键点集合信息，启动kernel计算在关键点附近像素的梯度大小和方向，利用已经存储在全局存储器中的高斯权重函数，对关键点邻域窗口内的各像素的梯度大小进行高斯加权并累加建立方向直方图，检测直方图的峰值，确定关键点主方向；

步骤3：计算128维的SIFT描述符，以关键点为中心的16×16影像数据块根据关键点的尺度、位置和方向构造SIFT描述符的过程，在CPU上实现则可以发挥CPU逻辑分支、判断能力强的优势，高效地完成任务；

步骤4：SIFT特征匹配，确定匹配点位，按照原始点的自然顺序将维度数据读入本地存储器，优化的重点是距离计算，首先必须保证每个维度差值的平方在同一时刻被计算，而不是使用内循环方式，其次必须保证维度数目的中间结果的累加方式高效；

所述的基于OpenCL的棋盘式卷积运算包括如下步骤：

步骤1：卷积乘计算，在内核gaussConvolution启动后，待处理的影像数据就存放在全局存储器中，高斯核函数数据存放在常量存储器中，工作组中各个工作节点将对应的全局存储器和常量存储器的数据取出完成卷积乘运算后存入本地存储器中，根据单指令多线程执行模型的工作原理可知，活动warp是以时间片分配的，工作节点调度程序定期从一个warp切换到另一个warp，以最大限度利用多处理器的计算资源，只有指令中全部操作数就位的warps拥有执行资格，调度协议按照优先级选择其中一个warp执行，各个warp之间的执行次序是不确定的，可以是任何次序，由于在同一个warp中的这32个工作节点是被绑定在一起执行同一指令的，这意味着warp中的每个工作节点传递的都是指令库中的相同指令，指导工作节点执行一些操作或操纵GPU存储器；

步骤2：积的累加计算，当工作组中所有工作节点卷积乘计算完毕后，采用并行归约求和算法计算出影像中某个像素点的卷积值，最后将计算结果通过主机端控制从设备端转移到主机端的内存；

所述的工作节点的任务分配及映射包括如下步骤：

步骤1：卷积并行中工作节点的任务分配及映射，根据卷积运算中卷积乘相互无关的特性，卷积并行最自然的想法是每一个卷积乘由一个工作节点计算，即每个工作节点负责将一个像素值与高斯模板值相乘，由于在卷积并行中采用并行缩减求和算法计算影像中某个像素点的卷积值，因此每个工作节点还将负责一对卷积乘乘积值的求和；

下面是算法中涉及到的数据结构向OpenCL映射后的具体描述，通过get_group_id二维索引向量和get_local_id一维索引向量来寻址：

const unsigned int tid＝get_local_id(0)；

const int baseAddress＝get_group_id(1)*col+get_group_id(0)+tid；

const int offset＝col_GAUSS_MODELDIM；

步骤2：剔除边缘点并行计算中工作节点的任务分配及映射，在候选特征点检测完成后，形成了一个线性数据结构集合，因此可以分配一个工作节点去完成是否剔除一个边缘点的判断，通过OpenCL在每个工作组中开辟512个工作节点并行判断是否保留该候选特征点，这里的工作节点地址映射关系如下所示：

const unsigned int tid＝globalWorkSize[0]*get_group_id(0)+get_local_id(0)；

步骤3：欧氏距离并行计算中工作节点的任务分配及映射，关键点的128维描述子可以看成是一个线性数据结构集合。因此可以分配一个工作节点去完成一对相应维度的差平方计算。通过OpenCL在每个工作组中开辟128个工作节点并行计算出每一对维度的差平方值，并将结果保存到本地存储器中。由于在欧氏距离并行中采用并行缩减求和算法计算距离，因此每个工作节点还将负责一对差平方值的求和。此处的工作节点地址映射关系如下所示：

const unsigned int tid＝get_local_id(0)

const unsigned int bid＝get_group_id(0)；

所述的SIFT特征匹配并行计算为SIFT特征匹配GPU并行化处理计算模式。

所述的基于OpenCL的棋盘式卷积运算为一个顺序运算的过程。

随着影像像幅的降低和滤波窗口的增大，GPU的加速效果十分明显，影像对进行SIFT特征匹配单GPU运算的总加速比高，具有密集的计算任务和工作量大的特点，并通过优化达到最佳效果，另外基于OpenCL的SIFT特征匹配算法通过并行性分析，将许多计算分割在CPU和GPU之间分别计算，发挥了各自的计算优势，充分体现了CPU+GPU异构计算的强大能力，实时性高，具有可移植性的Sift特征匹配并行算法实现了平台无关性。

实施例3

如图1、图2、图3、图4和图5所示，一种基于OpenCL并行加速的SIFT特征匹配方法，它包括SIFT特征匹配并行计算、基于OpenCL的棋盘式卷积运算和工作节点的任务分配及映射，以经过预处理的不同像幅大小的影像对滤波窗口为21×21进行SIFT特征匹配对比实验，分别运行SIFT特征匹配的CPU系统、单GPU系统和多GPUs系统，并记录处理时间，见表1，以489×561像幅的影像对进行不同滤波窗口大小的SIFT特征匹配对比实验，分别运行SIFT特征匹配的CPU系统、单GPU系统和多GPUs系统，并记录处理时间，见表2。

表1 不同像幅SIFT特征匹配串并行性能对比

表2 不同滤波窗口SIFT特征匹配串并行性能对比

Claims (3)

1.一种基于OpenCL并行加速的SIFT特征匹配方法，它包括SIFT特征匹配并行计算、基于OpenCL的棋盘式卷积运算和工作节点的任务分配及映射，其特征在于：所述的SIFT特征匹配并行计算包括如下步骤：

步骤1：首先读取输入影像到主存，将不同尺度的高斯核数据由主存传入到GPU的常量存储器中，在GPU中进行分步连续滤波加速高斯尺度空间金字塔的构建，并将高斯金字塔存储在全局存储器内，然后高斯金字塔影像被回读到CPU，相邻尺度的两个高斯影像相减得到DOG金字塔多尺度空间表示，当把候选特征点集合信息上传至GPU中后，便可在GPU内对高斯差分金字塔所有候选特征点进行精确定位，计算关键点周围影像强度的主曲率，通过一个2×2的Hessian矩阵计算特征值比率，检测关键点主曲率是否超过设定的阈值，通过去掉多余的点后，确定关键点集合并精确标记关键点的位置和尺度，关键点位置、尺度将在GPU中恢复；

步骤2：利用在GPU中计算的关键点集合信息，启动kernel计算在关键点附近像素的梯度大小和方向，利用已经存储在全局存储器中的高斯权重函数，对关键点邻域窗口内的各像素的梯度大小进行高斯加权并累加建立方向直方图，检测直方图的峰值，确定关键点主方向；

步骤3：计算128维的SIFT描述符，以关键点为中心的16×16影像数据块根据关键点的尺度、位置和方向构造SIFT描述符的过程，在CPU上实现则可以发挥CPU逻辑分支、判断能力强的优势，高效地完成任务；

步骤4：SIFT特征匹配，确定匹配点位，按照原始点的自然顺序将维度数据读入本地存储器，优化的重点是距离计算，首先必须保证每个维度差值的平方在同一时刻被计算，而不是使用内循环方式，其次保证维度数目的中间结果的累加方式高效；

所述的基于OpenCL的棋盘式卷积运算包括如下步骤：

步骤1：卷积乘计算，在内核gaussConvolution启动后，待处理的影像数据就存放在全局存储器中，高斯核函数数据存放在常量存储器中，工作组中各个工作节点将对应的全局存储器和常量存储器的数据取出完成卷积乘运算后存入本地存储器中，根据单指令多线程执行模型的工作原理可知，活动warp是以时间片分配的，工作节点调度程序定期从一个warp切换 到另一个warp，以最大限度利用多处理器的计算资源，只有指令中全部操作数就位的warps拥有执行资格，调度协议按照优先级选择其中一个warp执行，各个warp之间的执行次序是不确定的，可以是任何次序，由于在同一个warp中的这32个工作节点是被绑定在一起执行同一指令的，这意味着warp中的每个工作节点传递的都是指令库中的相同指令，指导工作节点执行一些操作或操纵GPU存储器；

步骤2：积的累加计算，当工作组中所有工作节点卷积乘计算完毕后，采用并行归约求和算法计算出影像中某个像素点的卷积值，最后将计算结果通过主机端控制从设备端转移到主机端的内存；

所述的工作节点的任务分配及映射包括如下步骤：

步骤1：卷积并行中工作节点的任务分配及映射，根据卷积运算中卷积乘相互无关的特性，卷积并行最自然的想法是每一个卷积乘由一个工作节点计算，即每个工作节点负责将一个像素值与高斯模板值相乘，由于在卷积并行中采用并行缩减求和算法计算影像中某个像素点的卷积值，因此每个工作节点还将负责一对卷积乘乘积值的求和，通过get_group_id二维索引向量和get_local_id一维索引向量来寻址：

const unsigned int tid＝get_local_id(0)；

const int baseAddress＝get_group_id(1)*col+get_group_id(0)+tid；

const int offset＝col-GAUSS_MODELDIM；

步骤2：剔除边缘点并行计算中工作节点的任务分配及映射，在候选特征点检测完成后，形成了一个线性数据结构集合，因此可以分配一个工作节点去完成是否剔除一个边缘点的判断，通过OpenCL在每个工作组中开辟512个工作节点并行判断是否保留该候选特征点，工作节点地址映射关系如下所示：

const unsigned int tid＝globalWorkSize[0]*get_group_id(0)+get_local_id(0)；

步骤3：欧氏距离并行计算中工作节点的任务分配及映射，关键点的128维描述子可以 看成是一个线性数据结构集合，因此可以分配一个工作节点去完成一对相应维度的差平方计算，通过OpenCL在每个工作组中开辟128个工作节点并行计算出每一对维度的差平方值，并将结果保存到本地存储器中，由于在欧氏距离并行中采用并行缩减求和算法计算距离，因此每个工作节点还将负责一对差平方值的求和，此处的工作节点地址映射关系如下所示：

const unsigned int tid＝get_local_id(0)

const unsigned int bid＝get_group_id(0)。

2.如权利要求1所述的一种基于OpenCL并行加速的SIFT特征匹配方法，其特征在于：所述的SIFT特征匹配并行计算为SIFT特征匹配GPU并行化处理计算模式。

3.如权利要求1所述的一种基于OpenCL并行加速的SIFT特征匹配方法，其特征在于：所述的基于OpenCL的棋盘式卷积运算为一个顺序运算的过程。