一种多架构加速的尺度不变特征变换快速计算方法

一种多架构加速的尺度不变特征变换快速计算方法

规模-特征变换（sit）是一种测量和描述图像局部特征的算法。sit函数具有旋转、缩去、偏移等几何变量的不变性，并且对噪声和光的变化具有良好的稳定性。这是图像局部特征的优秀描述符号，在图像识别、图像配置等领域得到了广泛应用。然而,SIFT特征的算法复杂度高、计算耗时过长,无法用于实时性要求较高的场合.随着可编程图像处理器GPU技术的成熟,其强大的并行计算能力和浮点运算能力,以及可编程能力使图像处理操作的加速成为可能.针对SIFT特征提取的计算效率问题,国内外学者进行了很多研究,其中基于GPU和多核CPU对SIFT算法进行实现与优化成为近年来的研究热点.Sinha等人基于OpenGL和Cg语言在NVIDIA7900GTX显卡上实现SIFT特征的GPU并行运算,但限于当时的软硬件条件,很多步骤并没有在GPU上执行,导致GPU和CPU之间的数据传输量很大,耗费了很多时间.Zhang等人在Intel8核CPU上实现SIFT算法,并对算法的可伸缩性进行了详细的分析与实验.本文提出一种基于统一计算设备架构(computeunifieddevicearchitecture,CUDA)加速的SIFT特征提取算法,优化各计算步骤在GPU和CPU间的分配、调度及数据传输,并充分利用GPU浮点运算、并行计算及内存管理等方面的优势,使得SIFT特征提取的计算时间大大缩减.1特征点提取和描述SIFT算法首先应用高斯卷积核构造图像尺度空间:L(x,y,σ)=G(x,y,σ)*I(x,y).(1)式中:符号*表示卷积;G(x,y,σ)是尺度可变高斯函数.G(x‚y‚σ)=12πσ2e-(x2+y2)/2σ2G(x‚y‚σ)=12πσ2e−(x2+y2)/2σ2.(2)式中:(x,y)是空间坐标,代表图像的像素位置;σ是尺度空间因子.然后,利用不同尺度的高斯差分核与图像卷积构造高斯差分尺度空间(DoGscale-space).D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))*I(x,y)=L(x,y,kσ)-L(x,y,σ).(3)在DoG尺度空间中进行局部极值点检测,该过程需要遍历每一个像素点,并将其与26邻域的像素相比较,若该像素点灰度值是极大或极小值,则将其作为候选关键点保留下来.接下来,对得到的候选关键点进行进一步的精选.首先获取关键点处拟合函数:D(X)=D+∂DΤ∂XX+12XΤ∂2D∂X2X,(4)再对式(4)求导并让方程等于零,可以得到极值点:ˆX=-∂2D-1∂X2∂D∂X.(5)对应极值点,方程的值为D(ˆX)=D+12∂DΤ∂XˆX.(6)DoG算子会产生较强的边缘响应,需要剔除不稳定的边缘响应点.获取特征点处的Hessian矩阵,主曲率通过一个2×2的Hessian矩阵H求出,Η=[DxxDxyDxyDyy].(7)H的特征值α和β代表x和y方向的梯度,tr(Η)=Dxx+Dyy=α+β‚det(Η)=DxxDyy-(Dxy)2=αβ.}(8)tr(H)表示矩阵H对角线元素之和,det(H)表示矩阵H的行列式.假设α是较大的特征值,β是较小的特征值,α=rβ.为了剔除边缘响应点,只需检测式(9)是否小于某阈值,tr(Η)2det(Η)=(α+β)2αβ=(rβ+β)2rβ2=(r+1)2r.(9)对精选得到的关键点进行方向分配,得到梯度模值m(x,y)和梯度方向θ(x,y):m(x‚y)=√(L(x+1‚y)-L(x-1‚y))2+(L(x‚y+1)-L(x‚y-1))2,θ(x‚y)=arctan(L(x‚y+1)-L(x‚y-1)L(x+1‚y)-L(x-1‚y)).}(10)式中L表示关键点的尺度.最后,生成128维的特征点描述符.Lowe在论文中指出,对每个关键点使用4×4共16个种子点来描述,每个种子点由8个方向梯度组成.这样对于一个关键点就可以产生128个数据,即最终形成128维的SIFT特征向量,如图1所示.2特征算法流程充分利用图像处理单元(GPU)在并行计算、浮点计算、内存管理等方面的优势,合理分配主机端和设备端的资源以及在SIFT特征计算中所承担的角色.特征算法流程如图2所示,其中高斯差分尺度空间构建、局部极值点检测、特征点方向梯度计算以及特征描述符计算在设备端(即在CUDA架构下)进行,这是提高SIFT特征提取算法速度的关键所在.2.1基于gpu的高斯滤波和高斯差分无线网络构建首先将图像从主机端的内存拷入设备端,并绑定纹理内存.选择纹理内存是考虑到以下因素:1)纹理内存能够享受GPU内部针对二维数据访问优化的纹理缓存,从而在随机存取的环境下保持较高的性能;2)纹理内存还能享受硬件的双线性插值,从而完成需要的图像缩放操作;3)图像在高斯滤波时要面临内存边界问题,但GPU程序不擅长条件判断语句的执行;采用纹理内存可以通过属性设置,使GPU在访问纹理内存时自动、高效地处理此类问题.根据式(1)计算高斯滤波结果,高斯滤波的各个参数在主机端计算完毕后传入设备端的常量存储器.每个栅格处理1幅图像,其中的block按照二维地址排序;每个block处理1幅图像中的一部分,大小可以设为16×16,即每个block中包含256个thread;每个thread处理1个像素及其周围8邻域的像素值.计算得到的中间结果存放在共享存储器中,最后将高斯滤波的计算结果存入全局存储器.得到高斯金字塔后,将其计算结果保存在全局存储器中,然后可以根据式(3)构建高斯差分金字塔,进而得到高斯差分尺度空间.假设高斯金字塔共O组,每组有S层.因为每个差分金字塔的构建过程只与同组高斯金字塔的相邻层相关,而彼此间关系不大,且构建过程都不会对已有的高斯金字塔产生改变;因此可以将高斯金字塔按照其所在层、组,将其分配到不同的block中,并在各个block中按照式(3)并行计算各个像素的差分值,最后再整合各个block中的计算结果,得到差分金字塔.2.2局部极值点提取假设有O组S层的高斯金字塔,构建得到O组S-1层的差分金字塔DoG之后,即可以在各个尺度下对每个采样点进行26邻域的局部极值点检测,得到O组S-3层局部极值点.据此,可以循环调用O次kernel函数来面向各个尺度,每个循环处理一个尺度的差分金字塔的数据,而在kernel函数中同样通过S-3次循环来计算各层的局部极值点.在每个循环中,为减少warp的分支判断,优化算法效率,每个block处理16×16尺寸的图像数据,若图像整体宽、高无法满足16的整数倍,本文采用在原图像外边缘用灰度值为0的像素补齐的方法来保证图像尺寸为16的整数倍.实验表明,每个像素先进行8邻域的局部极值点检测,可以剔除95%的像素点,与直接检测26邻域的局部极值点相比,可以很大程度地提高算法效率;因此本文首先在8邻域进行局部极值点检测,再在26邻域进行局部极值点检测.由于设备端对分支、判断等逻辑语句的处理效率较低,因此将初步计算得到的局部极值点传输到主机端,并通过式(9)进一步精确确定极值点位置,再将计算结果传回设备端,保存在全局存储器中.2.3高斯图像邻域处理根据计算得到的特征点分配设备端的block.根据式(10)对每个特征点及其对应尺度下的高斯图像邻域进行处理,从而得到高斯图像邻域内每个像素点所对应的梯度模值和方向.每个block处理16×16邻域的图像数据,每个thread处理1个像素的计算过程如图3所示.2.4特征向量的计算本文特征描述符取128维向量,其在设备端的计算过程与特征点梯度类似.每个block取1个特征点及其邻域进行特征向量的计算,block尺寸为16×16,共计256个thread,这256个thread被分为4×4个种子区域,每个区域中根据梯度方向形成一个分组数为8、彼此间相隔π/4的直方图.block中每个thread针对一个邻域像素点,负责计算该像素对其所在的4×4的种子区域所形成直方图的8个方向的模值贡献度.3实验结果与分析实验所用的计算机软硬件配置如表1所示.实验中,将本文算法与标准SIFT算法执行效率相比较,选取的图像分辨率分别为300×200,640×480,800×640,1200×800,1600×1200,图像来源于UCBerkeleyComputerVisionGroup的BSDS500数据集,其SIFT特征提取效果图分别如图4所示.本文算法与CPU架构下算法的对比结果如表2所示.实验中,算法的参数设置如下:组数根据图像分辨率确定;每组中DoG层数为3,DoG函数阈值为0.04,主曲率阈值为10,特征描述符种子区域为4×4,特征描述符向特征点邻域进行投影的方向数为8,特征点主方向分配在