2018基于图形处理器的可变形部件模型算法的并行化

8470275

　　摘要：目前目标识别领域，在人体检测中精确度最高的算法就是可变形部件模型(DPM)算法，针对DPM算法计算量大的缺点，提出了一种基于图形处理器(GPU)的并行化解决方法。采用GPU编程模型OpenCL，对DPM算法的整个算法的实现细节采用了并行化的思想进行重新设计实现，优化算法实现的内存模型和线程分配。通过对OpenCV库和采用GPU重新实现的程序进行对比，在保证了检测效果的前提下，使得算法的执行效率有了近8倍的提高。
　　关键词：可变形部件模型;OpenCL;人体检测;图形处理器
　　引言
　　目前，在无人驾驶、智能监控、智能交通等人工智能领域中，人工智能正在发挥越来越重要的作用，正在逐渐使人类从繁琐重复的工作中解放出来。目前在这些领域中，由于这些场景都需要实时监测，所以最为普遍的需求是对算法进行并行化加速，以提高算法的执行效率，实现实时化处理。
　　本文将重点介绍一种目标识别算法――可变形部件模型(Deformable Part Model， DPM)算法[1]，目前DPM算法是一个检测精度非常高的算法，在目标检测和人脸识别等方面都有很好的应用，但是该算法也有计算量非常大、无法完成实时性处理等缺点。本文采用并行化编程模型OpenCL，重新设计DPM算法的并行化实现，提高算法的执行效率，使DPM算法应用在实时检测成为可能。
　　一、相关工作
　　目标检测一直是计算机视觉领域内的难题，尤其是像人体这种非刚性物体，文献[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算法特别适合作并行化计算，而且其应用前景和领域非常广泛，所以它的并行化也就显得十分重要，下面详细介绍算法的并行化实现。
　　二、算法的概述
　　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=1did(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=1did(dxi，dyi)是对部件的变形惩罚，具体系数会在训练好的分类器中。