一种基于可变形部件模型的快速对象检测算法

李春伟 于洪涛 李邵梅 卜佑军



一种基于可变形部件模型的快速对象检测算法

李春伟*于洪涛 李邵梅 卜佑军

(国家数字交换系统工程技术研究中心 郑州 450002)

为了解决可变形部件模型检测过程中的速度瓶颈问题，该文针对模型的检测流程，提出一种结合快速特征金字塔计算的级联可变形部件模型。由于模型的检测速度主要取决于特征计算以及对象定位这两个过程，提出一种两阶段的加速算法：首先采用尺度上稀疏采样的特征金字塔来近似表示精细采样的多尺度图像特征，以加快特征计算过程；然后在定位过程中结合级联算法，以一个序列模型顺序地评估各个部件，从而快速剪除大部分可能性较小的对象假设，以加快对象定位过程。在PASCAL VOC 2007和INRIA数据集上的实验结果表明，该算法可以明显加快检测速度，而检测精度仅略有下降。

快速对象检测；可变形部件模型；特征计算；级联检测

1 引言

对象检测技术是计算机视觉的关键技术和研究热点之一。可变形部件模型[1](Deformable Part Model, DPM)作为现今最流行的对象检测算法之一，在对象检测领域著名的PASCAL VOC竞赛中多次取得优异的成绩，目前已经扩展应用到人体姿态估计[2]，行人检测[3]，人脸检测[4]，以及智能交通[5]等诸多领域。但是DPM模型中涉及的梯度方向直方图[6](Histogram of Oriented Gradient, HOG)特征金字塔的提取和对象定位两部分的运算量都较大，导致在单机上处理单张PASCAL数据集中的图像时，运行时间在10 s左右，无法满足实际应用需求。为此，近年来研究学者针对DPM的加速问题开展了系列研究。现有的DPM模型加速研究主要集中在以下两个方面：

单类别加速算法：主要关注于单个类别检测中DPM模型的加速效果。文献[7,8]通过较早地剪除无望的对象假设来减少计算量，前者根据部件滤波器的得分，使用中间阈值来剪除得分较低的部件假设。但是需要专门的确认数据集来训练中间阈值。后者通过使用多分辨率的层次部件模型，逐次对目标假设进行判断，但是其对于检测精度有一定的影响。文献[9]采用一种类似于文献[7]中的加速策略，通过一种积极的部件选择策略优化了滤波器评估的顺序。文献[10]在所有可能的图像区域上搜索全局最优的分类结果，然而该方法使用最大响应的上确界进行搜索窗口的裁剪操作，其有效性极大地依赖于边界的健壮性。文献[11]采用GPU实现并行计算，但是对计算机硬件提出了较高的要求；文献[12]使用快速傅里叶变换来加速检测过程中卷积计算过程。文献[13]通过多种加速方法间的组合来构建完整的加速策略。

多类别加速算法：文献[14]使用大量部件集合中的稀疏线性组合来对可变形部件进行编码，以此来压缩模型中所使用的有效部件数；文献[15]使用少量基本的部件集合的线性组合来近似表示模板中视角、形变、尺度等方面的变化。类似的方法在文献[16]中也进行了相关研究。这两种方法都是通过学习得到一组共享的基元部件，来获取类别层次的检测效果。文献[17]提出了基于局部敏感的哈希算法来近似DPM中的卷积计算，处理的对象类别达到了100000种，但是对于检测精度的影响较大。

综上，可以看出已有研究中主要关注对象定位加速，并且取得了一些成果，但是对于特征计算加速关注较少。所以想要进一步提高DPM模型的处理速度，就不得不考虑特征计算部分的加速问题。由此，本文提出了一种针对可变形部件模型的两阶段加速算法：首先，采用尺度上稀疏采样的特征金字塔近似表示精细采样的多尺度特征金字塔，以此来加快特征计算过程；然后，采用级联算法来加速对象定位过程。为了便于叙述，后续将本文提出的方法称之为结合快速特征金字塔的级联可变形部件模型(Cascade Deformable Part Model with Fast feature pyramid, FCDPM)。

2 基于幂指定律的快速特征金字塔计算

在基于多尺度特征金字塔的滑动窗口模型中为了解决模板尺寸与对象尺寸不一致的问题，需要对目标图像多次进行下采样得到不同尺度下的图像，然后再在逐个尺度的图像上逐个位置上计算图像特征，从而生成精细的特征金字塔，该方法得到的特征精度高，但是相应的时间开销也较大。已有研究人员对特征金字塔进行研究，发现多尺度金字塔尺度间的特征存在一定的关系，且满足幂指定律[18,19]。由此，本文提出在特征金字塔的计算过程中，利用多尺度特征中的幂指定律有选择地计算部分尺度图像的特征，然后基于这些尺度图像的特征对临近尺度图像的特征进行近似计算，从而减少特征计算的运算量。

2.1 多尺度特征间的幂指定律

为了便于描述，本节先简要介绍一下多尺度图像间的幂指定律。对于给定的输入图像，定义其对应的通道特征为图像像素的某种线性或是非线性变换的输出响应：。其中表示某种计算函数，表示输出响应。定义为的权值加和：,为图像在尺度上的重采样图像，其中的维数是图像维数的倍。那么就被定义为

2.2基于幂指定律的尺度间HOG特征近似计算

本节将上述定律应用到DPM模型中的HOG特征计算中。在传统DPM模型中，计算尺度图像的特征的方法为，其中表示采样函数，即需要首先将图像缩放至尺度，然后再计算图像的HOG特征。根据上述定律，和之间存在对应关系，为此在已知原始尺寸图像的特征的情况下，可以根据其对进行近似计算，从而提高特征计算的速度。

2.3 基于幂指定律的HOG特征金字塔计算

3 结合级联算法的可变形部件模型对象定位

3.1 可变形部件模型中对象定位流程

本节首先简要介绍可变形部件模型中对象定位的处理流程。DPM模型为一个两层模型，其中根滤波器用于检测对象的整体轮廓，个部件相对于根滤波器允许有一定的位移，用于描述目标对象的细节特征及其位置偏移导致的形变特征，从而模型在处理大尺度外观变化时有优势。第个部件由滤波器以及形变模型进行参数化表示。一个对象假设由进行定义。其中表示根滤波器的位置，表示第个部件的位置。根滤波器以及部件滤波器之间通过图结构模型进行连接，形变模型用于描述两者之间的形变特征。为了检测出图像中目标对象的位置，在每一个根位置上根据最有可能的部件配置来计算对象假设的整体得分：

3.2结合级联的快速对象定位

从上述描述中可以看出，基于计算出的多尺度HOG特征，在DPM模型的对象定位过程中，需要逐尺度层采用滑窗搜索进行匹配检测。但是，事实上对象通常仅出现在图像场景中的有限位置，图像尺度空间上的绝大部分窗口对于视觉对象检测而言是无效的，如果在每个尺度、每个位置都进行完整的匹配操作，这就导致了计算复杂度的增加。由此提出在对象定位过程中结合级联检测，迅速减除大部分可能性较小的对象假设，以此来提高定位过程的速度。

首先对原模型中部件进行排序来构建层次结构的新模型。在拥有个部件(其中包括根滤波器)的DPM模型中，采用一个全局阈值和个中间阈值的序列，从而得到一个长度为的序列模型。在计算匹配得分时，部件得分是按照一定的次序逐个匹配，在计算每一个部件表现得分以及相应的变形开销时都要与中间阈值进行判别，如果小于预设的中间阈值，相应的目标假设就被剪除。

4 结合快速特征金字塔的级联可变形部件模型

表1 FCDPM算法

图1 FCDPM算法的示例

5 实验结果

5.1实验准备

为了评估所提算法的性能，本文采用平均精度(Average Precision, AP)值作为评价指标，分别在PASCAL VOC 2007数据集以及INRIA数据集上进行了测试，并且与初始的DPM模型以及相关算法进行了比较，AP值定义如下：

5.2 在PASCAL VOC 2007数据集上的实验结果

PASCAL VOC 2007是一个通用的对象检测数据集，其测试集中包含20种类别的图像，共有4952张测试图片以及14976个人工标注的目标对象。通过上面的叙述，设为在特征金字塔计算中，由每一个基准尺度所外推计算的尺度数，当时，即表示精细采样的特征金子塔。的取值会影响特征金字塔的计算速度，取值越大，计算速度越快，但是这也会在一定程度上影响特征金字塔的计算精度，首先讨论了不同的取值对于AP值以及相对于DPM模型检测速度的影响，相应的结果如图2所示。

表2比较了FCDPM算法，与初始的DPM模型以及若干种加速算法，其中包括CSC算法[7]，CF算法[8]，BB算法[10]，在PASCAL2007数据集上的实验结果，其中FCDPM旁的数字表示的取值。每一种算法在20种类别检测过程中的平均特征计算时间、对象定位时间以及完整检测时间如表3所示。

从表3可以发现，CSC算法、CF算法、BB算法相比于初始的DPM模型在PASCAL2007数据集上取得了10倍左右的加速效果，本文算法与之相比，可以3倍快于这些改进算法，但是平均的AP值有一定的下降(特别是与CSC算法相比较)。即当时，可以取得最快的加速效果，相应的精度下降也最多，但是与CF算法和BB算法相比，综合考虑精度以及速度，具有较大的优势；而且可以通过调整这一参数，从而在检测精度和速度之间取得一定的平衡。当时，平均的AP值为31.3%，当时，平均的AP值上升到32.4%，此时与CSC算法仅相差0.4%，检测速度为CSC算法的1.6倍。

5.3在INRIA数据集上的实验结果

INRIA数据集是一个常用的行人检测数据集，其中包含614幅图像，共有1237个正样本和1218个负样本。表4说明了上述算法在该数据集上的实验结果。在数据集中的运行时间的比较如表5所示。从中可以发现改进算法在行人检测这一领域也取得了在PASCAL对象检测数据集中相似的检测结果。FCDPM算法在该数据集上最快可以取得将近32倍的加速效果。当时，可以取得与CSC算法相接近的AP值，但是检测速度为CSC算法的两倍。从而验证本文算法在行人检测领域也是适用的。

图2 nApp的取值对于检测速度以及精度的影响

表2不同算法在PASCAL2007数据集中20个类别的AP值结果(%)

算法AeroBicycleBirdBoatBottleBusCarCatChairCow DPM32.159.910.613.524.947.748.927.517.427.0 CSC[7]33.658.510.213.425.044.749.228.017.127.2 CF[8]27.658.610.510.616.552.742.127.612.929.1 BB[10]30.653.9 8.710.422.543.238.917.513.522.6 FCDPM935.957.6 8.411.826.944.348.118.014.722.8 FCDPM535.558.610.211.627.446.550.619.416.423.4 FCDPM137.059.610.311.227.444.350.820.617.923.0 DogHorseMbikePersonPlantSheepSofaTableTrainTv平均 14.457.450.038.413.321.036.831.147.542.333.0 13.557.750.038.514.121.636.828.647.442.032.8 15.355.244.626.312.422.738.632.844.832.230.6 9.055.747.227.411.117.128.323.344.538.428.2 8.755.346.033.313.319.229.525.944.536.530.0 9.953.247.036.615.022.832.426.843.138.831.3 11.657.950.839.015.223.534.426.047.041.632.4

6 结束语

针对可变形部件模型的检测流程，为了加速模型的检测速度，本文提出了一种两阶段的加速算法，分别采用特征计算中尺度间的幂指定律以及级联算法加速特征计算以及对象定位过程，从而显著地提高模型的检测速度。下一步的工作集中在加速检测过程中的卷积计算，这与之前的工作[8,11]是互补的，相结合预期可以得到显著的加速效果；还可以与目前流行的对象建议算法[20]相结合，以进一步提升算法的检测速度。

表3在PASCAL2007数据集中的平均运行时间(s)

算法特征计算对象定位运行时间之和加速倍数 DPM0.3769.1979.573 1.00 CSC[7]0.3760.4390.81511.74 CF[8]0.5480.4380.986 9.71 BB[10]0.3761.2871.663 5.53 FCDPM90.0900.2510.34128.10 FCDPM50.1100.2750.38524.87 FCDPM10.1930.3180.51118.73

表4不同算法在INRIA数据集上的AP值(%)

算法DPMCSCCFBBFCDPM9FCDPM5FCDPM1 AP值88.788.683.685.583.986.687.7

表5在INRIA数据集中的平均运行时间(s)

算法特征计算对象定位运行时间之和加速倍数 DPM0.76614.42515.1911.00 CSC0.766 0.670 1.44110.54 CF1.242 0.445 1.687 9.00 BB0.766 1.477 2.243 6.77 FCDPM90.157 0.323 0.48031.65 FCDPM50.212 0.354 0.56626.84 FCDPM10.326 0.443 0.76919.75

[1] FELZENSZWALB P, GIRSHICK R, MCALLESTER D,. Object detection with discriminatively trained part based models[J]., 2010, 32(9): 1627-1645. doi: 10.1109/TPAMI.2009.167.

[2] YAO Benjamin, NIE Bruce, LIU Zicheng,. Animated pose templates for modeling and detecting human actions[J]., 2014, 36(3): 436-452. doi:10.1109/TPAMI. 2013.144.

[3] WEN Jia, WANG Xueping, KONG Lingfu,. Using weighted part model for pedestrian detection in crowded scenes based on image segmentation[J]., India Section A: Physical Scienes 2016, 86(1): 125-136. doi: 10.1007/s40010-015- 0231-3.

[4] OROZCO J, MARTINEZ B, and PANTIC M. Empirical analysis of cascade deformable models for multi-view face detection[J]., 2015, 42(1): 47-61. doi: 10.1016/j.imavis.2015.07.002.

[5] OHNBAR E and TRIVEDI M M. Learning to detect vehicles by clustering appearance patterns[J]., 2015, 16(5): 2511-2521. doi: 10.1109/TITS.2015.2409889.

[6] DALAL N and TRIGGS B. Histograms of oriented gradients for human detection[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Diego, USA, 2005: 886-893.doi: 10.1109/ CVPR.2005.177.

[7] FELZENSZWALB P, GIRSHICK R, and MCALLESTER D. Cascade object detection with deformable part models[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Francisco, USA, 2010: 2241-2248. doi:10.1109/CVPR.2010.5539906.

[8] PEDERSOLI M, VEDALDI A, GONZALEZ J,. A coarse-to-fine approach for fast deformable object detection[J]., 2015, 48(7): 1844-1853. doi: 10.1016/j.patcog.2014.11.006.

[9] ZHU Menglong, ATANASOV N, PAPPAS G J,. Active deformable part models inference[C]. Proceedings of the 13th European Conference on Computer Vision, Zurich, Switzerland, 2014: 281-296. doi: 10.1007/978-3-319- 10584-0_19.

[10] KOKKINOS I. Bounding part scores for rapid detection with deformable part models[C]. Proceedings of the 12th European Conference on Computer Vision, Firenze, Italy, 2012: 41-50. doi: 10.1007/978-3-642-33885-4_5.

[11] LIU Qi, HUANG Zi, and HU Fuqiao. Accelerating convolution-based detection model on GPU[C]. Proceedings of the IEEE Estimation, Detection and Information Fusion, Harbin, China, 2015: 61-66. doi: 10.1109/ICEDIF.2015. 7280163.

[12] DUBOUT C and FLEURET F. Exact acceleration of linear object detectors[C]. Proceedings of the 12th European Conference on Computer Vision, Firenze, Italy, 2012: 301-311. doi: 10.1007/978-3-642-33712-3_22.

[13] YAN Junjie, LEI Zhen, WEN Longyin,. The fastest deformable part model for object detection[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Columbus, USA, 2014: 2497-2504. doi: 10.1109/CVPR.2014.320.

[14] SONG H O, GIRSHICK R, ZICKLER S,. Generalized sparselet models for real-time multiclass object recognition[J]., 2015, 37(5): 1001-1012. doi: 10.1109/TPAMI. 2014.2353631.

[15] PIRSIAVASH H. Steerable part models[C]. Proceedings of the 2012 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Providence, USA, 2012: 3226-3233. doi: 10.1109/CVPR.2012.6248058.

[16] KOKKINOS I. Shufflets: shared mid-level parts for fast object detection[C]. Proceedings of the 14th International Conference on Computer Vision, Sydney, Australia, 2013: 1393-1400. doi: 10.1109/ICCV.2013.176.

[17] DEAN T, RUZON M, SEGAL M,. Fast, accurate detection of 100,000 object classes on a single machine[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Portland, USA, 2013: 1814-1821. doi: 10.1109/CVPR.2013.237.

[18] RUDERM D L. The statistics of natural images[J]., 2009, 5(4): 517-548. doi: 10.1088/0954-898X_5_4_006.

[19] DOLLAR P, APPEL R, BELONGIE S,. Fast feature pyramids for object detection[J]., 2014, 36(8): 1532-1545. doi: 10.1109/TPAMI.2014.2300479.

[20] HOSANG J, BENENSON R, DOLLAR P,. What makes for effective detection proposals?[J]., 2016, 38(4): 814-830. doi: 10.1109/TPAMI.2015.2465908.

Rapid Object Detection Algorithm Based on Deformable Part Models

LI Chunwei YU Hongtao LI Shaomei BU Youjun

(&,450002,)

To solve the speed bottleneck of deformable part models in the detection process, this paper proposes a cascade deformable part model with rapid computation of feature pyramids for the detection process of the model. Because the speed of the detection is mainly determined by the two processes of the feature computation and the object location, a two-stage speedup algorithm is proposed. Firstly, sparsely-sampled feature pyramids on the scale are utilized to approximate finely-sampled multi-scale image features to speed up the process of feature computation. Then combined with the cascade algorithm in the location process, a sequence model is utilized to evaluate individual parts sequentially so as to rapidly prune most object hypotheses of small possibilities in order to speed up the process of object location. The experimental results on PASCAL VOC 2007 dataset and INRIA dataset show that the algorithm in the paper apparently speeds up the speed of detection with minor loss in detection precision.

Rapid object detection; Deformable part model; Feature computation; Cascade detection

TP391.4

A

1009-5896(2016)11-2864-07

10.11999/JEIT160080

2016-01-19；改回日期：2016-06-08；

2016-09-01

李春伟 lichunwei15@126.com

国家自然科学基金(61572519, 61521003)

The National Natural Science Foundation of China (61572519, 61521003)

李春伟： 男，1991年生，博士，研究方向为图像处理、计算机视觉.

于洪涛： 男，1970年生，研究员，研究方向为通信、信息系统、社交网络.

李邵梅： 女，1982年生，讲师，研究方向为通信，信息系统、图像处理.

卜佑军： 男，1978年生，讲师，研究方向为通信、信息系统.