基于图形处理器的可变形部件模型算法的并行化
时间：2022-07-22 03:39:45
摘要：目前目标识别领域，在人体检测中精确度最高的算法就是可变形部件模型（DPM）算法，针对DPM算法计算量大的缺点，提出了一种基于图形处理器（GPU）的并行化解决方法。采用GPU编程模型OpenCL，对DPM算法的整个算法的实现细节采用了并行化的思想进行重新设计实现，优化算法实现的内存模型和线程分配。通过对OpenCV库和采用GPU重新实现的程序进行对比，在保证了检测效果的前提下，使得算法的执行效率有了近8倍的提高。
中图分类号： TP319
0引言
目前，在无人驾驶、智能监控、智能交通等人工智能领域中，人工智能正在发挥越来越重要的作用，正在逐渐使人类从繁琐重复的工作中解放出来。目前在这些领域中，由于这些场景都需要实时监测，所以最为普遍的需求是对算法进行并行化加速，以提高算法的执行效率，实现实时化处理。
本文将重点介绍一种目标识别算法――可变形部件模型（Deformable Part Model， DPM）算法[1]，目前DPM算法是一个检测精度非常高的算法，在目标检测和人脸识别等方面都有很好的应用，但是该算法也有计算量非常大、无法完成实时性处理等缺点。本文采用并行化编程模型OpenCL，重新设计DPM算法的并行化实现，提高算法的执行效率，使DPM算法应用在实时检测成为可能。
1相关工作
目标检测一直是计算机视觉领域内的难题，尤其是像人体这种非刚性物体，文献[1]中提到，这类目标外表和目标大小千差万别，不同角度下人体姿势也是千变万化，由于这类目标不是刚性物体且容易产生形变，所以这类目标检测起来的难度更大。
2005年，Dalal等[3]两位法国科学家提出了使用梯度方向直方图（Histogram of Oriented Gradient， HOG）来描述人体的方法，此方法使用基于HOG特征的单一模板来表示目标，采用HOG+支持向量机（Support Vector Machine，SVM）分类的方法进行人体检测。使用此模板在图像的多个尺度和图像中所有位置上进行人体检测，进而判别该区域是否包含人体。目前对HOG算法的并行化已经比较成熟，OpenCV中也已经提供了HOG算法的并行化版本。
文献[1]中详细介绍了DPM算法的实现细节，包含训练和检测两部分的细节实现，训练部分介绍关于隐藏变量支持向量机（Latent Support Vector Machine， LSVM）分类器的训练， 目前已成为众多分类器、分割、人体姿态和行为分类的重要部分。DPM算法的实现较为复杂，考虑到根和部件的两方面，人体的整体作为根，四肢、头部和肩部等可以作为部件，通过模型，考虑到部件的惩罚，可以最终算出一个根和部件的总分，这样检测效果显著提高，但是由于算法复杂性的提高，导致执行时间大幅增加。然而对于DPM算法的并行化研究工作依然比较少。
2012年，欧洲计算机视觉国际会议（Europeon Conference on Computer Vision， ECCV），来自美国伯克利大学的团队，所作的研究就是对DPM算法进行优化，使之能满足实时性要求。该团队提出一种稀疏模型，使DPM算法的计算量减少，结合图形处理器（Graphics Processing Unit， GPU）加速运算，使算法完全满足实时性的要求，而且在物体的模型训练上也比较全面，检测精度也非常高。
文献[2]介绍了基于计算统一设备架构（Compute Unified Device Architecture， CUDA）实现DPM算法并行化的工作，并获得了10倍的加速比。但是基于CUDA的并行化程序只能运行在Nvidia的独立显卡上，无法实现通用性。而OpenCL作为行业标准，具有通用性。因此，本文考虑采用OpenCL编程模型完成DPM算法的并行化移植。
文献[3]介绍了梯度方向直方图（HOG）算法的原理，可变形部件模型（DPM）算法的原理是HOG算法的优化，在算法的原理上具有相似的实现原理。文献[4-9]介绍了基于GPU的算法优化和实现原理，以及对算法的改进和DPM算法在不同领域的应用。
其中，文献[1]中详细介绍了DPM算法的实现细节，包含训练和检测两部分的细节实现，训练部分介绍关于LSVM分类器的训练。一系列的关于算法并行化的工作也已经实现，文献[4-7]中也提到一些基于GPU的算法并行化，以及算法的改进优化， 参考文献[8-9]等可以看出，国内很多领域都对DPM算法进行研究并应用，文献[9]中将DPM算法应用在人脸检测中，DPM在人脸检测中的检测精度也是非常高的，特别适合人脸检测的应用领域。
通过分析发现，DPM算法虽然检测精度高，但却因计算量巨大而无法对图像进行实时性检测。通过对算法的实现细节进行分析研究，发现DPM算法特别适合作并行化计算，而且其应用前景和领域非常广泛，所以它的并行化也就显得十分重要，下面详细介绍算法的并行化实现。
2算法的概述
DPM算法是基于HOG的改进，它使用基于根和n个部件间的位置关系来描述目标的结构，通过根来描述目标的整体轮廓，通过n个部件来描述组成部分，对于人体这种容易发生形变的目标，再通过部件的偏移进行部件惩罚，使目标检测更加准确。DPM可以理解为一种星型结构，此模型由1个根滤波器和n个部件滤波器组成，用整个模型来描述一个目标，目标的得分等于根得分加n个部件得分。在计算部件得分时，由于人体等非刚性目标的可变形，所以计算部件得分时需要在每个部件的理想位置的周围搜索部件的实际位置，部件在实际位置的最终得分等于部件在实际位置的特征值向量与滤波器的卷积得分减去部件实际位置相对于理想位置的偏移惩罚，用偏移惩罚来衡量目标的形变程度。根和部件的得分就是窗口特征值和滤波器的卷积。
含有n个部件的目标模型可以表示为一个（n+2）元组：（F0，P1，P2，…，Pn，b），每个部件模型可以表示为一个三元组（Fi，vi，di），其中： Pi表示第i个部件滤波器； vi是一个二维向量，表示第i个部件滤波器的锚点位置； di是一个四维向量，表示部件发生形变时的相对于锚点位置的变形惩罚。含有n个部件的目标模型的得分等于根滤波器分数加部件滤波器分数，减去部件滤波器相对于根位置的变形惩罚，再加上一个偏差值：
∑ni=0Fi・φ（H，pi）-∑ni=1di・φd（dxi，dyi）+b （1）
其中：H表示特征金字塔；pi=（xi，yi，l）代表计算的图像金字塔l层坐标为（xi，yi）的窗口特征值；式（1）中的变量（dxi，dyi）=（xi，yi）-（2（x0，y0）+vi），其中： （xi，yi）表示第i个部件滤波器的坐标，部件滤波器所在层的特征分辨率是根滤波器所在层的特征分辨率的2倍； （x0，y0）表示根滤波器的坐标；vi代表该部件的锚点位置，是一个二维向量。∑ni=1di・φd（dxi，dyi）是对部件的变形惩罚，具体系数会在训练好的分类器中。
3DPM算法的GPU并行化实现
CPU多核架构并不擅长于处理高清视频图像，但是GPU的众核架构在处理高清视频图像时具有非常大的优势。
通过利用参考文献[13-14]中介绍的CUDA和OpenCL编程模型，本文针对GPU的架构特点，对算法重新设计，无论是从执行模式还是从数据的存储模式，都需要针对并行化的方案进行重新设计。可变形部件模型算法的并行化具体实现步骤如下。
3.1建立图像金字塔
输入图像中人体尺寸的大小不一，而模型中检测窗口的大小是固定的，所以，需要通过缩放图像来适应检测窗口的大小，使算法能够检测到图像中任意大小的人体。对某一尺度的图像缩放时，图像中所有像素点之间的处理没有逻辑关系，非常适合并行化处理，为图像中的所有坐标位置分配一个线程，所有线程完成对对应坐标的像素点计算，通过不断地调整缩放尺度，最终建立一个图像金字塔。图像金字塔每隔10层缩放为原图像的一半。
3.2计算图像金字塔的梯度方向
图像金字塔建立完成后，将计算图像中所有像素点的梯度方向和梯度幅值。本文采用滤波器[-1，0，1]以及其转置来计算坐标为（x，y）处的像素点梯度幅值和方向。对于RGB彩色图像来说，我们分别计算像素点每一通道的幅值和方向，选取幅值最大的那一通道的梯度幅值和方向作为当前像素点处的梯度幅值和方向。
Gx（x，y）=H（x+1，y）-H（x-1，y）（2
Gy（x，y）=H（x，y+1）-H（x，y-1）（3）
式中：Gx（x，y），Gy（x，y）分别为当前坐标为（x，y）处像素点的水平方向梯度和垂直方向梯度。像素点（x，y）处的梯度幅值和梯度方向分别为：
G（x，y）=Gx（x，y）2+Gy（x，y）2（4
θ（x，y）=tan-1（Gx（x，y）Gy（x，y））（5
通过对上面的原理分析，可以看到，图像中每个像素点对应位置的梯度幅值和方向的计算均是独立的，和邻域内的计算没有任何逻辑关系，图像中所有像素点对应坐标可以并行计算，每个线程计算一个像素点对应坐标的梯度方向和幅值，图像边缘可以将梯度幅值和方向赋固定值（比如0）。
3.3计算梯度方向直方图
参考文献[1-2]中的直方图计算方法，将图像按照8×8个像素点作为一个cell进行分割，根据之前计算的每个像素点对应坐标的梯度方向和幅值，本文将以像素点的坐标（x，y）算出4个像素点的坐标； 然后依照当前像素点坐标（x，y）在其所处的8×8的cell当中的位置，分别算出对应的4个像素点的权重，用4个像素点的梯度幅值分别乘以权重进行投票，进行直方图归一化操作，最终每个cell将得到一个梯度方向直方图。
在设计GPU并行化解决方案时，考虑到线程之间的冲突和效率的原因，每个线程对应一个像素点的计算，本文为每个线程分配了一个18维（一个18个元素的float型数组）的共享内存，这样每个线程就会得到一个18维的梯度方向直方图，然后采用折半规约的方法进行规约，最终规约为每个cell一个梯度方向直方图。
通过计算得到对比度敏感的18维的梯度方向直方图和对比度不敏感的9维梯度方向直方图。为实现梯度方向直方图对偏置改变的不变性，本文将对得到的直方图分别进行归一化操作。根据当前cell的位置与周围cell的位置关系，算出4个归一化因子，对当前cell的9维和18维梯度方向直方图分别进行归一化操作和截断（截断因子设为0.2），然后再将4个归一化因子作为最后4维，得到最终的31维梯度方向直方图。
在设计归一化计算GPU实现时，本文为每个8×8的cell分配一个线程，每个线程都负责对当前cell的18维和9维的梯度方向直方图分别进行归一化，加上4个归一化因子，最终得到当前cell的31维梯度方向直方图。
3.4窗口区域特征值和滤波器的卷积
本文将在图像金字塔的所有尺度的缩放图像上进行人体检测，检测窗口的大小不一。对于根模型，本文使用三种大小：9×8、11×7、11×4（均以cell为单位），而对于部件模型，部件的大小均为6×6个cell组成。窗口的特征值即为该窗口内包含的cell的特征值串联起来，然后窗口的特征值和训练好的滤波器进行卷积，得到该窗口在图像中该位置的分数，在图像金字塔每一尺度上所有位置进行检测，得到所有尺度所有位置处的窗口分数。这样得到了图像金字塔所有尺度上的所有位置的根分数和部件分数，下一步就是对根和部件进行链接，得到整个检测窗口的分数。
在设计GPU并行化解决方案时，本文为每个检测窗口分配一个线程，相邻检测窗口之间相隔1个cell，可以理解为检测窗口的滑动步长为1个cell。在图像金字塔的某一个尺度上进行计算时，当前层由M×N个cell组成，那么就分配M×N个线程，通过内部的线程控制，使每个线程计算对应窗口的滤波器和特征值卷积，至于block线程分配，本文采用每个block由8×8个线程组成，可以根据实际情况合理调整。同时，内存的访问对于核函数的执行效率也有非常大的影响，本文在设计内存存储模型时，也尝试了多种内存的使用。最终，在上面的线程分配方案下，采用共享内存的方式，将当前block内的所有线程所需要的数据从全局内存缓存到共享内存中，然后线程进行计算，减少对全局内存的访问，大大提高了核函数的执行效率。
3.5距离转换
通过特征值和滤波器的卷积，得到图像金字塔中所有层中所有位置处的根和部件的得分，然后将可变形部件模型中根和部件联系起来，最终得到目标分数。首先部件位于图像金字塔中2倍于根所在图像大小的层，也就是部件所在层的特征分辨率是根所在层的特征分辨率的2倍，这样部件就可以捕获到相对于根更加精确的特征信息。目标的得分是根得分加一系列部件的得分之和，本文在计算部件得分时，将根坐标的2倍加锚点的位置，不同部件的锚点不同，这样就会得到不同部件未发生形变时的理想位置，而对于人这种容易发生形变的目标，要在理想位置的一定范围内进行部件实际位置的搜索，根据偏移对部件的实际位置出进行惩罚，得到实际位置处部件的得分。
Di，l（x，y）=maxdx，dy（Ri，l（x+dx，y+dy）-
di・φd（dx，dy））（6
距离转换将部件的变形惩罚考虑在内，在进行搜索的过程中，如果其中某个位置偏离锚点位置越远，则惩罚越严重，在部件的锚点附近寻找对部件滤波器响应最高分的检测窗口，这个窗口就是该部件的实际位置。
在设计GPU并行化解决方案时，通过分析可以看到，不同的根和部件的链接都是相互独立计算的，之前没有逻辑关系，所以本文的实现中为每一个根滤波器分配一个线程，每个线程负责处理在图像中某个位置处的检测窗口的根和部件的链接，同时负责在部件的锚点位置附近搜索部件的实际位置。从中可以看到，每个线程需要完成的计算量非常大，但是我们也尝试了其他的线程分配方式，发现这种的线程分配方式是执行时间最短的。
3.6包围盒合并
本文检测过程是对在图像金字塔中所有尺度的所有位置进行检测，这样就会出现同一个目标被多个框体包围的情况，本文使用非最大值抑制算法消除多余框体，根据框体的重叠面积，若重叠面积大于某一阈值，就贪心地保留分数较大的一个框体，实验表明，这种去除多余框体的效果非常好。
关于这一部分的并行化设计，发现图像金字塔的使用，不同层之间存在属于同一目标的窗体，而且需要将不同层的框体恢复到原图像中，依据框体所在的层数和当前检测窗体的大小进行恢复，而且金字塔中大部分的位置是没有人体的，如果采用并行化操作，肯定会大大增加计算量。所以本文将金字塔中的分数大于一定阈值的窗口信息拷回CPU端进行处理。本文将设计一个结构体，结构体中包含框体左上角坐标、宽高、分数、所处层数等信息，并且设置一个标志位，根据所有尺度下的窗体的重叠面积，若重叠面积大于某一阈值，根据两个窗体的分数大小，将分数较小的窗体的标志位置为false。这种方法大大减少计算量，并且去除多余窗体的效果非常好。
4实验结果及分析
本文测试检测效果和加速效果时，均是和OpenCV库中的DPM算法进行对比，同时本文也分析了显卡的资源使用情况。测试设备使用Intel Core i54460 CPU，内存4GB，显卡采用Intel集成显卡HD Graphics 4600。
4.1DPM算法的效果测试
测试图像中，本文选取比较有代表性的场景进行检测。测试效果如图1所示，在下面所有的基于OpenCV的检测图片中，每个检测窗口上的数字代表了该检测窗口的分数。
第1组测试的场景是单个行人且背景较为简单的情况；第2组测试的场景是单个行人，背景复杂且人体被部分遮挡的情况；第3组测试的场景是人数较多且人体之间相互存在遮挡的情况；第4组测试的场景是背景较为复杂的实际路况的图像，模拟车载摄像头的工作环境。
由上面4组具有代表性的检测图片可以看出，本文基于GPU实现的DPM算法的并行化，在检测效果上已经和OpenCV库接近一致，甚至要比OpenCV库检测效果更好。尤其是最后一张在车载摄像头的情况下，本文算法实现依然有比较好的检测效果。
4.2DPM算法加速效果分析
在检测效果和OpenCV保持一致甚至更优的前提下，本文将重点测试一下基于GPU的DPM算法相比OpenCV中CPU级联实现的加速效果。本文的测试环境依然是在Intel集成显卡HD Graphics 4600上进行测试。
由表1和图2中的数据，结合上一节中的检测效果可以看到，在保持检测精度和OpenCV一致的前提下，本文算法的执行效率有数倍的提高，并且在高清图像的处理中，检测效率有了近7倍的提高。由图2可以看出，图像越高清，数据量越大，利用GPU进行加速的效果越明显。
4.3显卡资源使用分析
对于集成显卡HD Graphics 4600来说，流处理器数量为20，位宽64B，带宽12.8GB/s，显存类型DDR3，GPU默认时钟频率350MHz，显存默认时钟频率800MHz。
通过表2中运行时参数变化可以看到：GPU的核心频率在运行时由600MHz变为1100MHz；GPU Power表示显卡功耗，由正常显示时的0.2W变为运行时的9.0W；GPU load表示GPU的占用量，正常显示时是5%甚至更低，运行DPM时是56%甚至更高到60%以上，还是有提高的空间。下面两个分别为显存的使用量，第一个为专用显存使用量，可以看到几乎没有变化；第二个为动态显存使用量由242MB变为546MB，大概要增加300MB左右的动态显存，这是因为对于集成显卡来说，显存是在内存上动态分配的，所以在运行的时候，DPM算法在运行时需要较多的显存空间，所以系统需要动态地为集成显卡分配显存。
5结语
可变形部件模型算法是目前最好的目标检测算法，本文通过对算法的并行化分析和实现，完成算法的GPU移植，使算法的执行效率显著提高，在某些特定情况下，结合其他算法，能够实现对小图像实时检测的要求。在模式识别领域中，进行目标检测很重要的一环是分类器的训练，在接下来的工作中，我们将尝试将GPU用在深度学习方面，通过GPU来训练分类器，使分类器的训练效率能够有明显提高，同时训练出自己的模型，使DPM算法能够在人脸检测等更多领域中有最好的检测效果。
参考文献：
[1]FELZENSZWALB P F， GIRSHICK R B， MCALLESTE D， et al. Object detection with discriminatively trained partbased models [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2010， 32（9）：1627-1645.
[2]GADESKI E， FARD H O， BORGNE H L. GPU deformable part model for object recognition[J]. Journal of RealTime Image Processing， 2014：1-13.
