王溪波，王 彬，赵 海，朱宏博，葛宏帅，朴春赫

（1.沈阳工业大学信息科学与工程学院，沈阳 110870；2.东北大学 信息科学与工程学院，沈阳 110819）

基于HOG特征的优化区域模板匹配检测*

王溪波1，王 彬1，赵 海2，朱宏博2，葛宏帅1，朴春赫2

（1.沈阳工业大学信息科学与工程学院，沈阳 110870；2.东北大学 信息科学与工程学院，沈阳 110819）

针对HOG算法滑动窗口检测效率低和目标特征描述不精确的问题，提出了一种基于

梯度方向直方图；可变形部件模型；滑动窗口；外形相似性；边缘特征；根滤波器；部件滤波器；支持向量机

随着数字图像技术的广泛使用，人们对图像内容方面的处理越来越重视.目标检测是最近比较热门的一个课题，它是一种基于目标几何和统计特征的图像分割，将目标的分割和识别合二为一，其准确性和实时性是整个系统的一项重要能力［1－3］.

近年来，目标检测领域出现了许多优秀的算法.其中，使用最广泛的一种算法就是通过提取HOG特征［4］来描述感兴趣目标，同时采用支持向量机（SVM）分类器对HOG特征进行训练和分类，最后运用分类器对测试图像进行检测.但是，该算法也存在很多问题需要改善.首先，HOG算法的向量维数比较高，使得检测计算量比较大，而且滤波器检测图像中的目标时，比较常用的检测方法是滑动窗口（sliding window）方法，需要遍历所有像素，造成了计算量的进一步增大；另外，由于HOG精度不够高，通过 HOG特征训练出的分类器对于外形比较相似的物体可能会产生误检和漏检的现象.

针对上述问题，本文首先根据对大量图片的观察发现，目标出现的位置比较具有规律性，目标更可能出现在图片的中心，并且检测结果更倾向于存在性的图片，比如路面上行人检测，而对于处于边缘的像素，可以考虑降低对其检测的可能性，以减少计算量；其次，针对检测评分处于阈值比较小的邻域内的区域，利用可变形部件模型进行相似性确认检测以保证检测的正确性.本文方法主要针对静态图片，而不是连续的帧图像.通过在PASCAL VOC 2007数据集上试验得出的结果可以发现，与滑动窗口相比，本文算法在该数据集的20个类别中有13个类别获得更快检测速度.

1 相关工作

本文在传统 Dalal-Triggs模型基础上引入了可变形部件模型［5］（deformable part model）.通过使用可变形部件模型可以更加精准、灵活地对检测区域进行评价.与传统的可变形部件模型使用方法不同的是，本文算法并不是在图像的每个区域都使用该模型进行评价，而是仅对可能存在目标的概率达到阈值时进一步对部件进行评价［6］，从而可以大大提高算法的检测效率.

1.1 HOG特征

梯度方向直方图（histogram of oriented gradients，HOG）是由Dalal等人提出的，它可以通过多维向量来表示目标特征，通过训练形成丰富的特征集.

HOG特征的计算是利用每个像素点与周围相邻像素点的灰度差，在单位区域内进行梯度方向统计，进而形成梯度向量.划分单位区域时，图片首先被分割成指定大小的无重叠的像素区域，称为cell.算法针对每一个 cell统计其中的梯度直方图.每个像素的梯度被离散化为9个方向 bin中的一个，每个像素为它的梯度方向增加权值，权值根据梯度值的大小决定.所有 cell统计成直方图以后，多个 cell组成一个bock.例如，假设检测窗口大小是64×64像素，分成 8×8＝64个 cell，每个cell的大小是8×8个像素点.将相邻的2×2＝4个单元格组合成一个 bock，需要注意的是，每个bock之间存在相互重叠的部分，可以通过归一化梯度值来减少光照的影响［7－9］.

通过以上步骤，得到了一个高维度的向量，这样 HOG对于图像的描述向量就生成了.

1.2 可变形部件模型

尽管 HOG特征具有良好的描述效果，但是对于局部特征而言，检测效果有限.为了获得更好的检测效果，本文使用可变形部件模型来对检测提供进一步的保障.

本文定义的目标模型是由一个覆盖了目标整体的较为粗糙的根滤波器和较为精细的部件滤波器组成，其中，部件滤波器只覆盖物体中的较小部分.部件滤波器的特征是以根滤波器分辨率的两倍来计算的，例如，如果在第l层通过根滤波器获得了比较高的评分，那么就需要在 l＋2层使用部件模型进行检测.因此，部件滤波器可以呈现出更好的边缘效果，与根滤波器相比，可以更精准地定位目标［10－11］.例如，考虑为脸部建立一个模型，根滤波器可以捕获粗糙的边缘，例如人脸轮廓，而部件滤波器可以捕获细节，例如眼睛、鼻子和嘴.

为了解决图像尺度不统一的问题，本文采用了HOG特征金字塔，它是通过计算标准图像金字塔的每一层 HOG特征来定义的.金字塔顶层特征捕获相对粗糙的梯度，主要用于根滤波器；而底层特征捕获较精细的梯度，主要用于部件滤波器.

根滤波器和部件滤波器都是通过与滑动窗口中的HOG特征向量做点积（dot product）来评价目标.检测窗口的总评分（score）是窗口的根滤波器评分与结果子窗口中的部件滤波器评分之和，再加上区域评估.算法将具有 n个部件的目标模型定义为一个根滤波器 F0和一组部件模型（P1，P2，…，Pn），其中，Pi＝（Fi，vi，si，ai，bi），i＝1，2，…，n，Fi为第i个部件的滤波器；vi为一个二维向量，用来确定第i个部件相对于根滤波器的可能区域；si给出了该区域的大小；ai和bi均为二维向量，用来确定方程系数.计算对第i个部件可能区域的评分，其表达式为

2 HOG算法改进

2.1 检测区域选取

由于检测窗口的覆盖区域为当前的检测区域，则检测窗口位置的选取效率会影响到算法执行效率.当前的趋势是使用滑动窗口的穷举方式来寻找目标，该方法虽然准确度较高，不会漏掉目标，但是穷举的方式会大大影响检测的效率.如果把图片的检测区域分出优先级，也就是说，如果检测窗口的检测位置能够先检测那些目标出现概率更大的区域，那么就能尽快地找到目标，从而使算法的收敛速度得到较大的提升［11］.

如果想从一幅图片中分析出目标的可能分布区域，主要有以下两种方式：

1）对图像进行预分割，把图像中的内容进行初步的分离.由于分离出来的部分很有可能是感兴趣目标，因此可以优先检测这部分.

2）通过统计，优先检测目标出现较大概率区域.对于一幅图片，中间的位置是感兴趣目标比较容易出现的位置.

本文用红框标出图片的中心区域，如图1所示.图1a中的主要内容为家具，可以看出屋中绝大部分的家具都在红框范围内；图1b中的主要内容为马术比赛，马、人及其他关键目标都在红框范围内；图1c中的主要内容为汽车，图中最为明显的一辆汽车处于红框范围内.根据上述现象可以推断，检测窗口的位置应该优先寻找图片中间的区域，降低比较靠近图片边缘区域的优先级，这样就可以更快速地找到目标.

图1 优化区域标定Fig.1 Calibration for optimized region

通过对比以上两个特点可以发现，预分割的方法对图像目标的定位比较准确，但是分割速度通常耗时较多.由于本文使用相似模板确认的方法对结果进行确定，考虑效率问题，算法不适合使用图像预分割的方法，因此，本文算法使用大概率区域检测方法来提高检测速度.

2.2 模板相似性确认

在滤波器检测出评分接近检测阈值的区域之后，需要对这种不确定的区域进行进一步确认，而本文主要确认的内容就是目标的相似性.

检测目标在形状上具有相似性，会对算法的检测结果产生干扰.例如，假设目标图中的内容为长度较短的火车，如果用巴士的模板进行检测，也可能会获得接近阈值的评分，但最终就可能得到错误的结果.

对于上述问题，本文采用关联分类的方法对这种干扰因素进行特殊处理.本文使用的数据集为PASCAL VOC 2007，其中包含20个分类.通过对这20个分类进行观察发现，从形状上可能产生相似性干扰的类别为：1）鸟和飞机；2）猫和狗；3）自行车和摩托车；4）牛、马和羊；5）巴士和轿车；6）巴士和火车；7）椅子和桌子；8）椅子和沙发.这些分类在提取边缘之后呈现出相似的边缘特性，如图2所示.图2a为自行车提取边缘后的结果，图2b为摩托车提取边缘后的结果，通过对比可以发现，自行车与摩托车的边缘特征是非常相似的.另外，对于这些数据集之外的其他分类也可能对检测结果产生干扰.例如，假设检测的目标是行人，但是待检测图片中包含猴子，由于猴子的外形与小孩相似，这可能产生把猴子错误地检测成小孩的情况，这样就会造成误检.

图2 自行车与摩托车的边缘对比Fig.2 Comparison in edge of bike and motorbike

通过以上分析可以得出，如果目标的检测评分高于阈值较多，说明检测出的目标特征比较明显，正确的概率较大，此时出现相似性误检的概率较小，则认为该检测不需要进行相似性确认.如果检测评分出现在阈值较小范围的邻域内时，就可能出现因外形相似而造成误检.判断是否需要进行相似模板的确认，其表达式为

式中：sco表示对可能区域的总评分；thresh表示判断阈值；neig表示判断邻域的大小.PD（sco）的结果如果为0表示需要进行相似模板的确认，结果为1表示不需要.

对于相似模板的确认，本文使用可变形部件模型.该模型通过将待检测目标分成各个部件来提高检测的准确度，可以很好地解决模板相似的问题.例如，飞机和鸟外形相似，在根滤波器下评分接近，但是通过对敏感部位的检测，如鸟的腿部和飞机机身，可以得到相对较大的评分差距，进而增加最终结果的准确度.

由于PASCAL VOC 2007只有20个分类，并且具有相似性的分类集合最大为3，那么对于时间上的额外消耗也就处在了可控的范围内，不会对算法的速度产生太大影响.

2.3 模板训练

本文遵循传统的HOG算法，使用线性支持向量机（SVM）作为分类判别器，并且使用PASCAL VOC 2007作为训练数据集.该数据集含有大量训练图片，这些图片中的检测目标都由边框标注出来.初始的根滤波器是通过PASCAL VOC 2007数据集中带边框的图片产生的，部件滤波器由根滤波器初始化得到.

本文算法的具体学习过程主要分为两个阶段：第一阶段是进行正样本训练和负样本训练，其中正样本图片包含待检测目标，负样本图片不包含待检测目标，从而得到初步的分类判别器；第二阶段使用已经得到的初步分类器对负训练图像进行扫描，把扫描结果有误的图片作为误测样本，然后用正样本、负样本和误测样本组成一个总的集合，再次学习得到最终的分类判别器.分类器的分类界面表达式为

式中，w、b为平面参数.这样就可以使用得到的分类判别器对待检测图像进行分类［11］.

3 基于HOG的模板匹配检测算法

本文算法主要分成两个阶段：训练阶段和检测阶段.由于数据集变得越来越复杂，使用简单的训练方法往往就可以达到比较好的效果，因此，本文使用线性支持向量机（SVM）来进行分类.检测部分的算法流程如图3所示.

图3 算法总体流程图Fig.3 Overall flow chart of algorithm

算法的检测首先是从图片的中心区域开始，可以尽可能快速地找到目标.如果某个区域评分非常高，可直接认定该区域为待检测目标，如果图片中出现了评分比较接近阈值的区域，则需要使用可变形部件模型进行更加精确地评分.由于可变形部件模型只用于评分较为模糊的区域，减少了不必要的计算，这对算法速度的提高有较大帮助.

如果检测过程中发现中心区域确实没有待检测目标，算法也会对图像中出现概率小的地方进行检测，防止对目标的遗漏.

在检测过程中，算法首先使用HOG算法的根滤波器进行检测并计算评分.如果评分明显大于或小于阈值，则认定该区域是否为待检测目标.如果不能认定，则使用可变形部件模型进行检测.由于使用可变形部件模型非常耗时，但又具有很高的准确性，所以对于可变形部件模型的使用时机十分关键.在普通情况下，使用根滤波器处理结果分明的图片，也就是评分较高或较低的图片，不使用可变形部件可以节省大量的检测时间.

通过上述描述可以发现，本文方法主要检测对象是针对静态图片的，由于静态图片中的场景相对规范，更容易找到目标.另外，本文方法更倾向于确定目标是否存在，而不是统计目标数量.

4 实验结果与分析

为了验证算法的可行性，本文对算法进行了测试，并提供各个步骤的结果.程序的运行环境是W indows 7操作系统下的Matlab R2013a，硬件环境中CPU为Intel Core I7 4770k，内存8GB.测试环境使用PASCAL VOC 2007数据集，该数据集包括9 963张图片，共分成20个目标类.

图4为3组图片的实验结果.3组图片中，第1组的检测目标为羊，第2组的检测目标为鸟，第3组的检测目标为火车.每组包含图片处理3个阶段的结果，分别为原始图像、对图像中心区域的标注、根滤波器对中心区域的评分，图像中亮度越暗，表示评分越高.

图4 各阶段实验结果对比Fig.4 Com paring in experimental results in each stage

通过实验可以看出，前 2组图片根滤波器评分中黑白对比比较模糊，说明根滤波器评分比较接近阈值；而第3组根滤波器评分的对比比较明显，说明评分比较高.这就需要对前两组图片进行下一步的检测，而第3组图片的检测结果可以作为最后的结果.

图5为3组图片的最终检测结果.由于前两组图片的检测使用了可变形部件模型以及相似模板，因此检测结果是通过分散的部件评估出来的整体结果.

图5 实验最终结果对比Fig.5 Comparing in final experimental results

表1给出了本文算法与文献［11－12］中算法的平均准确率（average precision，AP）的对比. AP是对不同召回率特定点上的正确率进行求平均值的计算，其表达式为

式中：t为对召回率所有值分成的份数；Qi为每个召回率中每个特定点对应的准确率.例如，计算AP时首先把召回率从0～1分成10等份，根据召回率分别为0，0.1，0.2，…，1.0的11个边界点上的正确率求平均值，则AP就等价于这11个点的平 均值［13］.

表1 平均准确率对比Tab.1 Comparison in average accuracy

由表1可以看出，本文算法对于边缘轮廓有相似性的分类，如自行车、飞机、羊和火车的效果比较好，而对于相似性不大的分类，如船和轿车等的检测效果提升不明显，说明本文算法通过对模板相似性进行检测起到了提高准确率的作用，但是仅对图片中心大概率部分进行检测会丢失图片中的其他检测目标，从而降低准确率.

为了分析各种算法的效率，表2给出了本文算法与文献［11－12］中算法的运行时间对比.从表2中可以看出，本文算法对于船、人和轿车等分类的检测速度提高较大，而对于其他分类效果不明显，例如自行车和飞机.通过分析可以发现，自行车与摩托车，以及飞机与鸟的相似度较大，检测过程中更有可能进行相互评分对比，由此造成检测速度降低.而船和人没有相似的模板，因此在每次的检测中都会节省大量的时间.

表2 运行时间对比Tab.2 Comparison in running time s

通过上述实验对比可以发现，本文算法对于大部分类别在速度上有稳定保证，但是该算法也存在一定的问题，对图片边缘地带会出现漏检现象.因此，本文算法对检测结果准确度和速度同时都有需求的情况下比较适用.

5 结 论

本文提出了一种基于传统 HOG算法的区域优化模板检测算法.该算法通过检测图像大概率区域并使用相似模板确认检测的方法，改进了传统的检测窗口效率低下和相似模板误检的问题，而且该算法还能够分辨边缘相似类别的同时提高算法的检测速度，提升了算法总体效率.通过对实验中各个类别的统计可以发现，文献［11－12］的算法对这些类别的检测平均AP分别为0.288、0.317，使用时间分别为4.59、4.64 s，而本文算法的平均 AP为0.293，平均时间为4.28 s.结果表明，本文算法在时间上提升比较明显，在 AP的对比上低于文献［12］.由此可以推断，该方法在对检测结果要求不严格的情况下可以起到比较明显的快速检测效果.

（

）：

［1］孙锐，侯能干，陈军.基于特征融合和交叉核 SVM的快速行人检测方法［J］.光电工程，2014，41（2）：53－62.（SUN Rui，HOU Neng-gan，CHEN Jun.Fast pedestrian detection method based on features fusion and intersection kernel SVM［J］.Opto-Electronic Engineering，2014，41（2）：53－62.）

［2］魏岩，涂铮铮，郑爱华，等.结合RGB颜色特征和纹理特征的消影算法［J］.计算机技术与发展，2013，23（10）：72－74.（WEI Yan，TU Zheng-zheng，ZHENG Ai-hua，et al. Shadow elimination algorithm of combination of RGB color feature and texture feature［J］.Computer Technology and Development，2013，23（10）：72－74.）

［3］于成龙.基于PCA的特征选择算法［J］.计算机技术与发展，2011，21（4）：123－125.（YU Cheng-long.Features selection algorithm based on PCA ［J］.Computer Technology and Development，2011，21（4）：123－125.）

［4］Dalal N，Triggs B.Histograms of oriented gradients for human detection［C］／／Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington D C，USA，2005：886－893.

［5］Felzenszwalb P，McAllester D，Ramanan D.A discriminatively trained，multiscale，deformable part model［C］／／IEEE Conference on Computer Vision and Pattern Recognition.Anchorage，USA，2008：1－8.

［6］Yuhi G，Koichiro Y，Hironobu F.CS-HOG：color similarity-based HOG［C］／／2013 19th Korea-Japan Joint Workshop on Frontiers of Computer Vision. Incheon，Korea，2013：266－271.

［7］刘威，段成伟，遇冰，等.基于后验 HOG特征的多姿态行人检测［J］.电子学报，2015，43（2）：217－224.（LIUWei，DUAN Cheng-wei，YU Bing，et al.Multipose pedestrian detection based on posterior HOG feature［J］.Acta Electronica Sinica，2015，43（2）：217－224.）

［8］Plath N，Toussaint M，Nakajima S.Multi-class image segmentation using conditional random fields and global classification［C］／／Proceedings of the 26th Annual International Conference on Machine Learning. Quebec，Canada，2009：817－824.

［9］姚雪琴，李晓华，周激流.基于边缘对称性和HOG的行人检测算法方法［J］.计算机工程，2012，8（5）：179－182.（YAO Xue-qin，LIXiao-hua，ZHOU Ji-liu.Pedestrian detection method based on edge symmetry and HOG［J］.Computer Engineering，2012，8（5）：179－182.）

［10］宫义山，董晨.基于贝叶斯网络的缺失数据处理［J］.沈阳工业大学学报，2010，32（1）：79－83.（GONG Yi-shan，DONG Chen.Data patching method based on Bayesian network［J］.Journal of Shenyang University of Technology，2010，32（1）：79－83.）

［11］Felzenszwalb P F，M cAllester D，Ramanan D.Object detection with discriminatively trained part-based models［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（9）：1627－1645.

［12］Zhu L，Chen Y H，Yuille A L，et al.Latent hierarchical structural learning for object detection［C］／／The Twenty-Third IEEE Conference on Computer Vision and Pattern Recognition.San Francisco，USA，2010：1062－1069.

［13］常娥，侯汉清.平均检准率研究［J］.情报科学，2006，24（4）：627－631.（CHANG E，HOU Han-qing.Study on average precision in information retrieval［J］.Information Science，2006，24（4）：627－631.）

（责任编辑：钟 媛 英文审校：尹淑英）

Template matching detection for optimized region based on HOG features

WANG Xi-bo1，WANG Bin1，ZHAO Hai2，ZHU Hong-bo2，GE Hong-shuai1，PAK Chun-hyok2
（1.School of Information Science and Engineering，Shenyang University of Technology，Shenyang 110870，China；2.School of Information Science and Engineering，Northeastern University，Shenyang 110819，China）

In order to solve the problem that the the detection efficiency of sliding window in HOG algorithm is low and the feature description of target is not accurate，an improved algorithm based on HOG was proposed，which could improve the detection efficiency of sliding window and reduce the influence of the target template similarity on the results.The entire target and each part were described with HOG features in the algorithm，and the area with high appearing probability of target would be preferentially detected.For the area whose score got near to the threshold，the deformable part model was used to carry out the accurate detection，which could avoid the inaccurate detection of templates with contour similarity. The results show that the proposed algorithm has higher accuracy for static images，and exhibits faster detection speed in many categories with low similarity.

histogram in gradient direction；deformable part model；sliding window；shape similarity；edge feature；root filter；part filter；support vector machine

TP 391.4

A

1000－1646（2016）06－0667－07

10.7688／j.issn.1000－1646.2016.06.13

2015－10－20.

辽宁“百千万人才工程”培养基金资助项目（2012921041）；中央高校基本科研业务费优秀科技人才培育基金资助项目（N140405004）.

王溪波（1964－），男，辽宁沈阳人，教授，博士，主要从事智能信息处理等方面的研究.

09－07 16∶08在中国知网优先数字出版.

http：∥www.cnki.net／kcms／detail／21.1189.T. 20160907.1608.038.htm l

HOG的改进算法，提高了滑动窗口的检测效率并减少了目标模板相似性对结果带来的影响.该算法利用HOG特征来描述目标的整体和各个部件，优先检测图像中目标出现概率较大的区域.对于检测评分比较接近阈值的区域使用可变形部件模型进行精确检测，从而可以避免具有轮廓相似性的模板检测结果的不准确.结果表明，该算法对于静态图片有较高的准确率，且对于很多相似度不高的分类具有较快的检测速度.