0 引言

随着计算机视觉的普及，行人检测在图像和视频检测中的应用越来越广泛，针对图片或视频画面中的环境比较复杂且行人之间有严重遮挡等问题，可变形部件模型(Deformable Part Model, DPM)算法^[1]被提出，但由于传统DPM算法中的特征提取和行人定位两部分的计算量过大，严重影响其检测速度，近几年来针对提高检测速度这一问题，学者们进行了大量研究。文献[2]应用并行计算的方法，使行人检测的速度有了明显提高，但该方法对硬件的要求较高，不能广泛应用；文献[3]应用多分辨率下的层次部件模型判断目标假设，虽然达到了一定提速的效果，但影响了检测精度；文献[4]对部件中的稀疏线性组合进行编码，用来压缩部件数量，但对检测精度的影响也较大；文献[5]在行人定位的部分应用了级联检测(Cascaded Detection，CD)算法^[6]，检测速度有所提高，但耗时只为原算法的1/4，效果并不明显。

综上所述，目前的研究难点是在提高检测速度的同时不影响算法的检测精度，因此，本文主要在提高检测速度并适度提高检测精度的问题上进行改进：首先，在传统的DPM算法的模型训练部分增加部件模型个数，以提高检测精度；然后，在行人定位和检测部分融合CD算法和分支定界(Branch and Bound，BB)算法，以更高效地提高检测速度。本文的算法与传统DPM算法相比，在检测精度方面提高了12个百分点，并且将行人检测的速度也提高了近25倍。

1 相关工作

目标的检测属于计算机视觉分析^[7]领域和图像处理领域内最基础的工作，其中，行人的检测在近几年的应用中尤为突出，行人检测结果的好坏会直接影响之后的对行人的识别和跟踪。目前，对行人的检测普遍是在静态图像中完成的，但由于行人目标是非刚体，会产生形状变化和视觉变化等，例如图中可能有肤色不同、穿着不同的衣服、作着不同的姿势的行人，这些情况都会在一定程度上影响最终检测的结果，因此，在复杂的静态图像中如何使检测的性能和检测的速度两方面达到一个高水平的权衡，已经成为近几年来数字图像处理方面的研究热点和难点。

到目前为止，行人的检测大多是在静态图像中进行的，其主要方法可以分为两大类：一类是基于模板匹配^[8]的方法，通常又可以分为基于灰度模板的匹配、基于轮廓模板的匹配和基于形状模板的匹配。该类方法的主要思想是：提取描述行人信息的模板，如行人的肤色、穿着的衣服等，并对这些模板加以训练，将训练得到的模板与输入的静态图像进行匹配，从而可以检测并定位行人；但是，该类方法在行人数量很多、行人信息差异很大、行人之间有严重遮挡和环境比较复杂的情况下，检测结果并不理想。另一类是基于特征学习^[9]的方法，该方法属于机器统计学习领域，可以很好地解决行人遮挡严重和环境复杂情况下的误检问题，因此，近几年的应用十分广泛。该类方法的主要思想是：从输入的图像中提取行人的灰度、边缘、肤色、纹理或梯度直方图等信息，并建立模型，将模型放到分类器中进行训练，将得到的模型与输入的静态图像进行匹配，从而可以检测并定位行人。该类方法中的分类器最主流的有：AdaBoost迭代算法^[10]、支持向量机(Support Vector Machine，SVM)算法^[11]、神经网络算法和DPM算法。这些算法中AdaBoost迭代算法只能检测出近似正面或背面的行人；SVM算法对图像的分辨率要求很高；神经网络算法和DPM算法是近几年应用比较广泛的算法，相比之下，DPM算法的行人检测精度较高。该类算法主要的行人检测步骤分为：图像的特征提取、特征的建模与训练和行人检测。实验结果表明，在现有的特征中，鲁棒性最好的是梯度方向直方图(Histograms of Oriented Gradients，HOG)特征^[12]；而用SVM算法进行特征训练的效率最高；通过DPM算法进行行人检测得到的实验结果的准确率相对较高。传统的DPM检测算法是提取行人的HOG特征，得到图像的特征金字塔，建立可变形部件模型，将模型通过增加了潜在值信息的隐变量支持向量机(Latent Support Vector Machine，LSVM)进行训练，得到5个部件滤波器模型，并在输入图像内进行扫描和匹配，从而检测出行人。传统的DPM算法能高准确率地检测出行人目标，但由于部件滤波器与图像中的目标假设匹配过程中的计算量过大，导致检测速度过慢，无法实现实时检测。

综上所述，本文在传统DPM算法的基础上增加了部件滤波器的数量，用来提高行人检测的准确性；同时为了解决部件滤波器的增加带来的计算时间过长和传统的DPM算法检测速度过慢的问题，本文算法又在传统的DPM算法中融合了BB算法和CD算法，并与传统的DPM算法进行了比较。实验结果表明，本文算法不但提高了检测的准确率，从而将行人检测的时间从10 s提高到了0.3 s。为了便于描述，将本文提出的算法称之为融合分支定界算法和级联检测算法的可变形部件模型算法(deformable Part Model with Branch and Bound algorithm and Cascaded Detection algorithm，BBCDPM)。

2 可变形部件模型算法

可变形部件模型是由一个较为粗糙的且覆盖整个目标的全局根滤波器、若干个高分辨率的部件滤波器和部件滤波器相对于根滤波器的位置这三部分组成。DPM算法主要分为提取行人轮廓特征，对可变形部件的建模，对可变形部件的训练和行人的检测。

2.1 特征提取

行人特征的提取作为行人检测的第一步尤为重要，应选鲁棒性强和描述行人特征能力好的特征，因此，DPM算法选取了HOG特征，通过描述行人的梯度直方图特征实现特征的提取。HOG特征是一种在计算机视觉和图像处理中用来进行物体检测的特征描述子，它通过计算和统计图像局部区域的方向梯度方向直方图来构成特征。与其他的特征描述方法相比，由于HOG特征是在图像的局部方格单元上操作，所以它对图像几何的和光学的形变都能保持很好的不变性，这两种形变只会出现在更大的空间领域上，并且，在粗的空域抽样、精细的方向抽样以及较强的局部光学归一化等条件下，只要行人大体上能够保持直立的姿势，可以容许行人有一些细微的肢体动作，这些细微的动作可以被忽略而不影响检测效果。

为了使滤波器在扫描图像时不受图像分辨率的影响，近几年的DPM算法中还利用了特征金字塔^[13]的方式。具体步骤如下。

步骤1  对输入的图像进行归一化处理，压缩公式为：

$I(x, y) = \mathop {\mathit{\boldsymbol{I}}(x, y)}\nolimits^{gamma} $

(1)

其中gamma=1/2，将图像I缩放至尺度s。

步骤2  从输入的原始图像I开始，在每一个倍频程中相对于上一步以2^1/t的倍数进行下采样，直至经历t次迭代操作达到原图像的1/2为止，得到输入图像的图形金字塔。

步骤3  通过计算标准图像金字塔中每一层图像的HOG特征得到HOG特征金字塔，HOG金字塔中每一层的最小单位是细胞单元。

步骤4  将每一层得到的HOG特征金字塔归一化并串联得到最终图像的HOG特征金字塔。

2.2 可变形部件的建模

可变形部件模型的实质是根滤波器和一系列部件滤波器结合形成的星形结构模型，而每一个滤波器的实质是一个权重向量。例如一个u×v的滤波器是一个含有u×v×g×h的权重向量，其中g×h为一个HOG细胞单元的特征向量的维数，每个滤波器的分数实质是由该滤波器对应的权重向量与HOG金字塔中u×v大小的HOG特征向量的点积得到的，则总的测试窗口的得分就是根滤波器的分数加上所有部件滤波器的分数的和，再与相应的该部件滤波器在特征金字塔中的位置进行点积后，减去每个部件滤波器相对于根位置的偏移量与偏移实数之和就构成了它的语义模型, 如式(2) 所示：

$ \begin{array}{l} score(\mathop p\nolimits_0,p_1, \ldots, \mathop p\nolimits_n ) = \sum\limits_{i = 0}^n {\mathop F\nolimits_i \times \varphi (H, \mathop p\nolimits_i )-} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\sum\limits_{i = 1}^n {\mathop d\nolimits_i \times \mathop \varphi \nolimits_d (\mathop d\nolimits_i, \mathop d\nolimits_0 ) + b} \end{array} $

(2)

其中：$\sum\limits_{i = 0}^n {\mathop F\nolimits_i } $表示根滤波器和部件滤波器的分数的和；φ(H, p_i)为每个部件滤波器相对于特征金字塔中的位置；d_i为每个部件滤波器相对于根位置的偏移量；b是一个偏移实数，需要强调的是，部件滤波器的分数是该部件滤波器的各个空间位置分数的最大值。

2.3 可变形部件的模型训练

有了语义模型后，下一步是对可变形部件滤波器进行训练，最初使用SVM算法的分类器训练模型，但由于SVM算法是一个凸函数，在最终的行人检测中，只标注了行人目标的整体位置，而不能标出每个部件的位置，因此，DPM算法采用LSVM来训练模型滤波器，它是在原有的SVM算法上添加了潜在值信息，即SVM算法中遗漏的输入信息，使得算法成为一个非凸函数，从而在行人检测过程中既可以标出整个行人目标的位置，又可以标出所有部件的位置。LSVM算法主要分为两个部分：对参数模型进行优化和对优化模型进行训练。

对参数模型进行优化  在LSVM算法中，假设β为根滤波器、部件滤波器和部件滤波器相对于根位置的偏移量串联起来得到的模型参数向量，z为目标匹配参数，集合Z(x)定义了样本x中可能的隐形变量的值。ψ(x, z)是特征金字塔中的一层HOG特征和部件的形变特征串联起来构成的特征向量，则每一个样本的得分就等于各个部件模型在给定位值的得分的最大值，如式(3) 所示：

$ \mathop f\nolimits_\mathit{\boldsymbol{\beta }} (x) = \mathop {\max }\limits_{z \in Z(x)} \mathit{\boldsymbol{\beta }} \times \mathit{\boldsymbol{\psi }}(x, z) $

(3)

优化模型参数向量β要通过使用梯度下降算法迭代，使得函数值收敛到L(β)的最小值，即得到了函数的局部最优值，L(β)的计算如式(4) 所示：

$L(\mathit{\boldsymbol{\beta }}) = \frac{1}{2}\mathop {{\rm{||}}\mathit{\boldsymbol{\beta }}{\rm{||}}}\nolimits^2 {\rm{ + }}C\sum\limits_{i{\rm{ = }}1}^n {\max (0, 1 - \mathop y\nolimits_i \mathop f\nolimits_\mathit{\boldsymbol{\beta }} (\mathop x\nolimits_i )} )$

(4)

对优化模型的训练  初始化并更新根滤波器；初始化并更新部件滤波器。具体步骤如下。

步骤1  对于每个目标类别，根据训练数据集中目标矩形框大小的统计值，自动选取根滤波器的尺寸，使用不含隐藏变量的SVM训练得到一个初始的根滤波器，正样本从实验选取的数据集中无遮挡的目标图片中截取得到，负样本从不包含目标的图片中随机截取。

步骤2  在输入的静态图中，如果训练得到的根滤波器和训练数据集中的目标矩形框有显著重叠时，找到滤波器得分最高的位置。

步骤3  在根位置周围选出具有最大分数的矩形区域，初始化为部件滤波器。

步骤4  不断添加负样本，不断训练新的部件模型来替换原来的部件模型。

3 快速行人检测

由于在可变形部件模型算法中，部件滤波器的数量越多检测的精度越高，如图 1所示为部件滤波器个数和检测精度之间的关系折线图，实验数据表明当部件滤波器的数量在5到8之间时，检测精度有明显的提高；当部件滤波器的数量为8以后时，检测精度虽然有所增加，但提高幅度不大。由式(2) 可知，$\sum\limits_{i = 0}^n {\mathop F\nolimits_i } $表示每个滤波器的分数，部件滤波器的增加虽然增加了检测精度，但也会增大求解滤波器分数的工作量，影响行人定位和检测过程的速度。在考虑最大限度提高检测精度的同时，应尽可能地降低对检测速度的影响。

因此，本文应用的BBCDPM算法将传统的DPM算法中训练得到的5个部件滤波器增加到了8个，这样既可以将检测的精度提高到93.71%，并且对行人检测速度的负面影响在可控制的范围内。为了进一步地提高检测速度，虽然之前的研究工作中利用了动态规划^[14-15]和距离转换算法^[16]，在搜索工作中可以排除部分假设位置，但效果并不明显，而文献[5]的DPM算法中加入了CD算法，将原始36维特征向量投影得到的11维特征向量，使用低维特征可以产生参数较少的模型，不但没有降低检测准确率，反而能够加速学习和检测。然而由于在计算特征金字塔时需要相对耗时的投影步骤，使获得的加速优势有所减少，因此，本文在其基础上应用了将BB和CD算法结合的方法，首先使用CD算法以一个序列模型顺序地评估各个部件，从而快速排除大部分可能性较小的对象假设，以加快对象定位过程，可将检测速度提高到传统算法的3倍；同时应用BB算法在所有可能的图像区域上搜索全局最优的分类结果，使用最大响应的上界限进行搜索窗口的裁剪操作，这样可以大幅提高检测速度，结果显示本文BBCDPM算法将行人检测的时间从10 s提高到了0.3 s。

3.1 级联检测算法

在行人检测中，分数大于全局阈值的根位置是检测的关键，CD算法的实质是计算每一个目标假设位置的分数，并从大到小进行重新排列，从而得到目标假设位置的裁剪阈值，并通过阈值修剪简化检测模型。将得到的修剪阈值与每一个目标假设位置的得分进行比较，将大于阈值的目标假设位置留下，并设定为感兴趣区域，排除大部分无效的目标假设位置。只需将得分最高的根部件在感兴趣区域内的每个假设目标的位置上进行级联检测，确定根位置。由于根部件和其他部件之间不是相互独立的，是有位置关联的，因此，其他部件滤波器可依次在其确定的根位置周围进行扫描和匹配。

3.2 分支界限分支定界算法

BB算法被用于非凸的或者不可微的函数值的最大值化的计算，该算法的主要思想是先将整个图像划分为区间，计算每个区间内的所有函数值，找出区间内函数值的最大值，将整个区间内的函数值都重新赋值为计算得到的该区间内函数值的最大值，每个区间的最大值是通过该区间内的函数上界限决定的。假设区间X₀的函数为S(x)，BB算法可以在区间X₀内判断出该函数值的最大值，因为BB算法可以将每一个区间内的函数近似看作一个抛物线函数，这样易于在一个复合非凸的函数中找到对应函数值的最大值，即这个抛物线函数的顶点函数值。X₀可被再次细划分成两个下级区间X₁和X₂，同样的，可以分别计算X₁内和内函数值的最大值，X₁和X₂又可以继续各自划分为两个区间，这样就可以很快地找出每个小区间内的最大的函数值，并将整个区间的所有函数值都用这个最大值重新定义，如式(5) 所示：

$ S(x) = \mathop {\max }\limits_{x \in X} S(x) $

(5)

3.3 算法的融合

综上所述：CD算法的实质是遍历所有目标假设位置，找到并保留大于阈值的目标假设位置，其他的部分被裁剪掉；BB算法的实质是通过优先权的思想，计算出每个区域内函数值的最大值，将这个区域内的函数值全部重新定义为这个最大值。两种算法的融合步骤如下。

步骤1   利用主成分分析(Principal Component Analysis，PCA)系数矩阵^[17]对特征向量和特征金字塔进行降维，保证维度一致。将标准的星形模型^[18]简化为星形级联模型，并计算得到级联检测阈值。

步骤2   将输入图像划分为区域，每个区域内得到目标假设位置的函数。

步骤3   计算每个区域内函数值的最大值，并将该区域内的所有函数值都重新赋值为该最大值。

步骤4   对行人目标的假设位置和形变进行裁剪，计算每一个目标假设位置的分数，将该分数与级联检测阈值进行比较，保留大于阈值的目标假设位置，并设置为感兴趣区域。

步骤5   在感兴趣区域中，进行级联检测，用根部件进行扫描，确定根部件的位置后，其他部件可通过与根部件的相对位置，在根部件周围区间进行扫描，从而检测出行人，并标识。

4 实验结果与分析

本文训练所用的数据库选择INRIA数据库，该数据库包括从各种人体照片中剪切得到1805个64×128像素的行人图片。这些人体目标大多数是站立的，但行人朝向各不相同，并且背景是复杂且不同的，有些背景中还有人群。实验选择在Matlab(R2015a)上进行；测试设备使用Intel Core i5-6300HQ CPU、内存为4.00 GB、系统为64位操作系统、基于x64的处理器。

本文采用的BBCDPM算法应用了HOG特征对行人的梯度直方图特征进行描述，并得到了输入图像的特征金字塔。通过LSVM对可变形部件模型进行训练，本文BBCDPM算法与传统DPM算法训练的可变形部件模型对比结果如图 2所示，图 2(a)为传统的DPM算法训练得到的根滤波器模型、5个部件滤波器模型，分别为头部、左上身部、右上身部、腿部、脚部和对应的5个部件模型；图 2(b)为本文BBCDPM算法细化的行人部件滤波器，将部件滤波器增加后训练得到的根滤波器模型、8个部件滤波器模型，分别是在原有的头部、左上身部、右上身部、腿部、脚部的基础上，将上身部细化为左肩部、右肩部、左腹部、右腹部；又将脚部细化为左脚部右脚部，及对应的8个部件模型。由图可以看出，通过细化部件滤波器，图 2(b)中的根滤波器相比较图 2(a)更为清晰，并且由于部件滤波器数量的增加使行人部件匹配的过程中可以更准确地匹配，从而可以提高行人定位和检测的准确度。

将得到的部件模型在静态图中的感兴趣区域内进行检测，得到的检测结果如图 3所示：图 3(a)为本文算法在单个行人的静态图像上的检测结果；图 3(b)为本文算法在多个行人且行人之间没有重叠时的静态图像上的检测结果；图 3(c)为本文算法在多个行人且行人之间有部分重叠时的静态图像上的检测结果。从图 3中可以看到，由于使用了非凸的LSVM算法进行模型的训练，因此，当可变形部件模型检测出行人时，图 3中不仅能够看到所有右侧图中标识出的整个行人目标，即根部件的位置，并且能够看到所有对应的左侧图中标识出的行人各个部件的位置，但由于其他部件位置与根位置是有相对关系的，因此确定根位置后，其他部件滤波器会在根位置周围根据相对距离关系进行扫描，所以，在图 3(c)中可以发现左右两个人的左右脚的部件位置出现了误检，但不影响整个行人的检测。

DPM算法一般用于静态图像中的人脸识别和人体检测，准确率较高，但在输入的静态图像中行人较多且有严重遮挡的情况下，漏检率过高，针对这一问题，本文增加了部件滤波器的数量。如表 1所示为传统的DPM算法训练得到的5个部件滤波器和本文BBCDPM算法训练得到的8个部件滤波器的实验结果数据对比，传统的DPM算法得到的行人检测的结果准确率为81.71%，但是却存在13.1%的漏检率；而本文所提出的BBCDPM算法的检测准确率为93.71%，相比较传统的DPM算法提高了12个百分点，并且漏检率也降低到4%，因此本文的BBCDPM算法在行人检测的准确率和漏检率方面都有明显的提高。

由于DPM算法的计算量过大，所以影响了行人检测的速度，改进后的DPM算法提高了在行人检测中的速度。实验数据表明，传统DPM算法的行人检测所花费的时间为10.74±1.00 s，应用了CD算法后的DPM算法在行人检测中所花费的时间为3.08±1.00 s，而本文提出的BBCDPM算法在行人检测中所花费的时间为0.25±0.1。由实验数据可以看出，传统的DPM算法所需的时间花费过大，再结合了CD算法后，虽然行人检测的速度有所提高，但由于在行人特征提取的过程中获得特征金字塔的计算量过大，单纯只结合CD算法并不能抵消之前的时间花费，因此，提速的效果并不明显。所以在此基础上，本文的BBCDPM算法在只结合了CD算法的DPM算法的基础之上，又结合了BB算法，得到图像各个区域的函数最大值，有利于CD算法排除大量不可能的对象假设，从而使检测时间从原有的10 s左右缩短到了0.3 s左右。

5 结语

DPM算法是近几年被应用于行人检测中准确度较好的算法，但由于计算量很大，导致检测速度过慢，不能进行实时的行人检测。为了更好地体现算法在行人检测中的优势，本文在提高准确率和提高检测速度两个方面都进行了相应的改进，将部件滤波器的数量从原有的5个增加到了8个，这一改进将行人检测的准确率提高了12个百分点。在此基础上，本文又在改进DPM算法中结合了BB算法和CD算法，使得本文BBCDPM算法的检测时间大幅缩短。

但在多个行人有严重遮挡的情况下，实验会出现漏检，因此，下一步的改进将研究添加多个行人检测器，以提高在行人互相有严重遮挡情况时的准确率。