一种改进的AdaBoost检测算法

摘要：针对传统AdaBoost算法在人脸图片训练过程中可能会出现退化现象和训练目标类权重分布过适应的问题，提出一种基于调整正负误差比和设定阈值的改进AdaBoost算法。该算法首先把设定的阈值和当前分类错误样本的权值比较来更新样本的权值，其次通过调整正误差和负误差之间的偏重关系来控制训练样本的偏重。经过实验表明，不同人脸图像库和不同正负样本比不影响该算法的有效性，在LFW非受限人脸图像库正负样本比例为1∶1情况下，检测率为86.7%，高于传统AdaBoost算法；弱分类器数目为116，比传统AdaBoost算法多15个。实验结果可以看出所提算法抑制了退化和训练目标类权重过适应现象，有效地提高了人脸图片检测率。

关键词：AdaBoost算法；正误差；负误差；阈值；人脸图像库

中图分类号： TP391.4

文献标志码：A

Improved detection algorithm of AdaBoost

LIU Pingguang*， WEN Chengyu， DU Hong

College of Communication Engineering， Chengdu University of Information Technology， Chengdu Sichuan 610225， china

Abstract： Considering the degradation and problem that the weight distribution of training targets is wider than average in the traditional AdaBoost algorithm in the process of human face image training， an improved AdaBoost algorithm was proposed based on adjusting margin of error and setting the threshold value. First， the weight values of the samples were updated according to the comparative result between the threshold value and the weight value of the matching errors of the current samples. Then， the emphasis of the training samples was controlled by adjusting the emphasis relation between positive error and negative error. The experimental results showed that different human face image databases and different ratios of positive and negative errors had little effects on the validness of the improved AdaBoost algorithm. Under the positive and negative error ratio of 1∶1 in unrestricted face database LFW， the detection rate was 86.7%， which was higher than that of the traditional AdaBoost algorithm； the number of weak classifiers was 116， which was 15 more than that of the traditional AdaBoost algorithm. The results prove that the proposed algorithm suppresses the degradation and the problem that the weight distribution of training targets is wider than average， and effectively improves the detection rate of human face images.

Key words：

AdaBoost algorithm； positive error； negative error； threshold； face image library

0引言

人脸检测是计算机视觉（Computer Vision， CV）领域研究的热点问题。AdaBoost算法作为经典的人脸检测算法，能够有效地将多个弱分类器[1]集成得到一个强分类器。目前，AdaBoost算法已经被广泛应用到雷达跟踪[2]、人脸检测[3]和目标识别[4]等领域中。

应用在人脸检测领域中原始的AdaBoost算法在训练分类器过程中经常出现退化以及目标样本权值重分布的现象。针对这些问题，研究者们进行了很多的改进，如：缪丹权等[5]提出了变化弱分类器加权参数求解方式的手段来降低误检率，李文昊等[6]提出了一种线性不对称分类器的改进方法用来增加检测率，严云洋等[7]提出了基于特征值等分和双阈值的增强型快速训练算法。这些方法都是通过不同的方式提高检测率或者是提高训练的速度。但当样本训练集中包含噪声样本和一些罕见的难分类样本时，这些算法将会给错误样本分配较高的权重，最终导致这些样本的过适应，对其他样本产生忽视性偏见现象，使检测率降低。为此，黄兴等[8]提出在每轮训练中定义一个阈值，并通过阈值确定权重的重新分配，取得了比较好的效果；李文辉等[9]通过调整正误差和负误差比的分布限制目标类权重的扩张，提高了检测率。但是这两种方法都只考虑了单一的影响因素，本文则考虑从设定阈值和限制正负误差权重比过大两方面来改进AdaBoost检测算法。实验结果表明，该算法能抑制过适应现象的出现，得到了较高的检测率。

但是黄兴从设定阈值限制整体权重过大方面提高检测率，李文辉从限制正误差和负误差权重过大方面提高检测率，他们只考虑了单一的影响因素，基于此从设定阈值和限制正负误差权重比过大两方面本文提出了一种新的高效的AdaBoost检测算法，本文的算法抑制了过适应现象的出现，得到了较高的检测率。

1AdaBoost检测算法组成

1.1级联分类器[10]

本文采用基于分层形式的方法来处理人脸检测，其具体含义是把训练过程中筛选出的大量弱分类器划分为不同的层次，每一个层次有若干个弱分类器级联成一个较强的分类器，在级联结构中，前面几级分类器使用较少的几个重要特征以排除大部分负样本，后边级次的分类器则使用较多的特征，以便区分与目标类似的负样本，因此可以看出级联分类器能很大程度降低了人脸检测的复杂度。图1为级联分类器示意图。

1.2类Haar矩形特征

类Harr特征是由Viola等[11]在其图片检测中引入的一系列简单矩形模板特征。矩形特征反映了图像灰度变化程度，Harr特征通过计算积分图像快速地获取积分图像。

为了能够尽量使Harr特征适应目标检测，对Harr特征的扩充研究不断出现，相继出现了45°方向的Harr特征[12]以及在此基础之上扩展的14种Harr特征原型，旋转45°方向的Harr特征克服了当人脸存在旋转角度时检测失效的问题。为了能在多种尺度情况下快速计算AdaBoost算法中分类器所需要的Haar特征，采用积分图进行计算，因为积分图计算能在使用相同时间的条件下计算更多不同的特征，从而大大提升了系统的检测速率。对于输入图像，图中某一点像素的积分图像值定义为：ii（x，y）=∑x′≤x∑y′≤yi（x′，y′）。其中：点（x，y）的像素值为i（x′，y′），对点（x，y）进行积分图计算后的结果为ii（x，y）。由上述公式知，积分图的计算就是像素点i（x′，y′）在当前位置左上角所有点的像素求和。如果要计算一个区域内的像素值，则可利用该区域的端点的积分图进行计算。图2中，D为所求的目标区域，其中区域A的像素值为ii（1），区域A和区域B像素值为ii（2），区域A和区域C像素值为ii（3），区域A、区域B、区域C和区域D所形成的整体区域像素值为ii（4），所以很容易就能得到区域D的像素值为ii（4）+ii（1）-[ii（2）+ii（3）]。

求图像的积分图像矩阵时，只需要对图像的每一个样本进行一次遍历，然后对每一个样本的每个积分点求积分图，并将计算的结果作为一个元素保存，图片中所有像素点的积分图形成一个序列，这些序列就形成了该图的积分图矩阵。由此积分图便很容易得到特征矩形的特征值。这种计算方式大大简化了计算的复杂度，提高了检测的速度。

1.3传统AdaBoost算法

AdaBoost算法是现在最有价值的机器学习[13]算法之一，它是一种迭代加权的分类方法，其核心思想是针对同一训练集训练不同的弱分类器，然后把这些弱分类器集合起来构成一个强分类器。AdaBoost算法本身是通过改变数据的分布来实现的，它根据每次训练集中每个样本的分类是否正确，以及上一次总体样本概率的分布，来确定每个样本的权值，然后将每次训练得到的弱分类器加权求和，形成最后的决策分类器。

1.4传统AdaBoost算法分析

AdaBoost对于普通的含有人脸图片和非人脸图片样本效果较好，但是当样本中含有噪声样本和一些罕见的特别样本时，传统的AdaBoost算法对这些特殊的样本在每一轮的训练分类中无法正确分类，这些样本可能被错分多次，导致这些样本的权重不断增大，这样在步骤4被错分的权值不断增大，产生样本权重严重扭曲现象。当训练样本中含有较多这一类样本时，每轮次产生的弱分类器的错误率不断增大，最终导致生成的强分类器中最后加权投票所占的正确权重变得比较小，会严重降低对目标样本的正确预测度。由于存在这些特殊样本，当循环迭代增多时，已经被正确分类的样本权重在整个样本集中的权重逐渐减小，导致步骤5预测函数正确的样本权值不断减小，前几轮循环迭代生成的比较准确的分类规则将会由于权重过度适应而逐渐遭到破坏或者丢失分类能力，当出现更严重的情况时，即当最小加权误差大于0.5时，将导致训练结束。

2改进型AdaBoost算法

2.1改进思路

针对传统AdaBoost算法在处理含有噪声样本和一些罕见的特别样本而出现检测率下降的问题，本文从阈值限制和控制正负误差偏重两方面改进了AdaBoost算法。

从设定阈值方面：在每一轮次的训练过程，设定一个阈值Wt，从样本是否分类错误和此轮分类错误的样本的权值是否大于Wt，制定一个判决和更改权重规则，当错分样本权重过度适应时更改权重的值，避免分类错误的样本权重过度适应遭到破坏或者丢失分类能力。

从控制正负误差方面：传统的AdaBoost算法样本训练过程中，样本错分的误差包含两种可能。第一种是目标样本为正样本被划为负样本，即把含有人脸图片的样本划为非人脸图片样本，属于漏检，记为正误差；第二种是目标样本为负样本被划分为正样本，属于误检，记为负误差。在每轮训练中，统计样本正误差ε+j、负误差ε-j，然后计算正负误差之比。该正负误差比在一个合理的区间内为正常，超出该区间则限制其比值畸形增加。最后为正负误差比设定两个常数阈值，通过该常数来调整正负误差比。

2.2改进算法模型

1）对于训练集{（x1，y1），（x2，y2），…，（xn，yn）}，n为训练的样本数目，m为正样本数目，l为负样本数目，n=m+l，Dt（xi）为第t次循环中第i个样本的权重。其中：yi∈Y={0，+1}，对于yi=0的样本，负样本概率Dt（xi）=（2l）-1；对于yi=+1的样本，正样本概率Dt（xi）=（2m）-1。

b）对于每个Harr特征j，训练一个弱分类器hj，并计算该弱分类器的错误率εj。其中εj=∑ni=1Dt（xi）|hj（xi）-yi|，从这训练的一系列弱分类器中找到一个有最小错误率εj的弱分类器ht。

c）该轮训练的阈值为Wt：Wt=1n∑nj=1Dt（xj），其中Dt（xj）是上一轮训练后未归一化的权重。

d）权重更新因子at为：

步骤2计算正负误差之比ψ=ε+/ε-。

步骤3设定两个常数d1、d2（0

当ψ超出该定义范围为不合适范围，当ψ

当ψ>Kd2时，增大产生负误差的负样本的权值，即增大Kd2倍。

3）T轮训练完，形成最终的强分类器为：

H（x）=sign（∑nt=1atht（x））

（9）

3实验与结果分析

3.1改进算法原理分析

上述改进算法模型的步骤c）在每轮设定阈值前提下，如果错分样本权重比阈值小时，仍保持传统AdaBoost算法计算，目的是让其错误样本权重仍保持更快的更新，使其在下一轮更容易检测到错误，更快地形成强分类器。

在错分样本权重比每轮设定的阈值大时，每轮的权重设置为Z-1tDt（xj）×e（1-ψ）/2， 其中e（1-ψ）/2是使错误样本权重减小的权重因子，一方面该因子使错误样本权重减小，另一方面该因子也不会使错误样本权重减小得过小，因为如果错误样本权重变得很小会导致多次训练弱分类器，训练时间增加。

修正正负误差比ψ以算法中设定的d1、d2常量参数和正样本和负样本初始误差比K为决定条件的，以正样本与负样本比值

K=1时来判定ψ在不同情况下的结果，一般情况下，取d1∈[0.5，1.0）， d2∈（1.0，1.5]。

如果ψ>d2，则说明误差偏向于正样本，通过本文中提出的算法限制正样本权重的增加；相反，如果ψ

3.2d1、d2参数设置

为了确定d1、d2参数的合适取值，采用中国科学院的CASPEALR1共享人脸图像库[14]作为测试样本，分别采用正负样本数目比为1000∶2000，1500∶1500，2000∶1000三种状况，d1、d2取值如表1。采用0.5，1.5；0.7，1.4；0.8，1.3三种状况，经过本文算法的验证得出如下表格。其中第一列d1，d2参数后边小括号里的比例为正负样本数目比。

通过表1的数据可以看出在d1=0.8，d2=1.3时检测率最高，但是所用的时间也最多；

当d1=0.5，d2=1.5时检测率最低，但是所用的时间最短；

当d1=0.7，d2=1.4时检测率有较大提高，训练所用时间适中。

从表1还可以看出，当正样本与负样本比值一定的情况下，人脸图片检测率随d2-d1的值的减小而增大，但是随d2-d1的减小其检测率增大趋势减缓；训练样本时间随d2-d1的值的减小而增大，所用时间增加趋势没有减缓现象。

从上述论述可以看出d1、d2的值不是一成不变的，可以根据相应的实验条件和要求选取相对合适的参数值。

基于以上分析，本文采用d1=0.7，d2=1.4来验证算法的效果，该值既能较快地完成训练过程，又能较好地提高人脸图片的检测率。

从表1还可以得知在三种正负样本比例状况下，在d1=0.5，d2=1.5时人脸图片检测率、训练样本时间大致相同；在d1=0.7，d2=1.4以及

d1=0.8，d2=1.3下也相同。所以正样本和负样本数目比例的变化对人脸图片检测率和训练时间基本没有影响。

3.3正负误差比曲线

图3是传统AdaBoost算法与本文的改进AdaBoost算法在正负样本比分别为1000∶2000，1500∶1500，2000∶1000三种

情况下的正负误差比曲线对比。可以看出：传统AdaBoost算法正负误差比会随着训练弱分类器数目的增加而呈现增大趋势；不同比例的正负样本随着训练轮数的增加，正负误差比成增大趋势，正误差偏大，负误差偏小，在后边的训练中出现了权重分配过适现象，即权重分布扭曲的现象，影响了训练的精确度。

而本文的改进AdaBoost算法的误差比大多数分别被限制在0.35～0.7，0.7～1.4，1.4～2.8范围内，不会出现过小或过大的状况，抑制了权重分配过适现象；除此之外，在训练相同样本的前提下，本文算法会产生更多的弱分类器，因此有助于提高检测率。

3.4检测率与弱分类器数目关系

图4是采用中国科学院的CASPEALR1共享人脸图像库作为测试库，采用正负样本数目比例为1500∶1500的测试样本时得到的弱检测器数目与检测率关系的曲线，可以看出，与传统AdaBoost算法和文献[8]的算法相比，本文算法有较高的检测率。

传统的AdaBoost算法随着弱分类器增多，检测率并不是一直增大，当达到最大值后，随着分类器增多检测率却下降了很多，这是由于正负样本权重出现了严重的扭曲，导致检测率下降；文献[8]的算法通过设定阈值有效地避免了退化以及目标样本权值重分布的现象，但检测率并没有达到最好的效果；本文算法通过设定阈值限制了正负样本权重分配过适问题，通过修正负误差比使其在一个合理的比值范围内，检测率得到了一定的提高。从图中也可以看出，本文算法需要训练更多的弱分类器来达到更高的检测率。

在最终生成的强分类器数目和最终的检测率比较中，本文采用中国科学院的CASPEALR1共享人脸图像库、Feret人脸图像库和非受限人脸图像库LFW，测试样本采用正负样本之比为1000∶2000，1500∶1500，2000∶1000三种状况，在表2～4中把比例简化为1∶2，1∶1，2∶1。实验环境为Intel Corei5 双核，2.4GHz，4GB内存，操作系统为Windows 7， 在VS2010平台上进行编程实现。

从表2～4可以看出，本文算法使弱分类器数目达到了最大值，其检测率也达到了最好的效果。

在实验的三种样本比例中，不同比例的样本对检测率和弱分类器数目没有影响，而且不同人脸图像库并不影响算法的有效性，因而本文算法适合在多种人脸图像库上训练样本。

3.5工程应用效果

基于本文的改进算法，采用VS2010+OpenCV进行了编程测试，并与传统算法进行比较。其中：图5（a）、（c）为传统算法检测结果，（b）、（d）为本文算法检测结果；具体检测数据如表5所示。从表5可以得出图5（b）、（d）正负误差比被限制在了07～1.4，而图5（a）、（c）超出了范围，图5（b）、（d）的检测率均高于对应的图5（a）、（c）的检测率，说明本文算法能有效提高检测率。

4结语

本文提出了一种通过调整正负误差比和设定阈值改进的AdaBoost算法，验证了在不同正负样本比例和不同人脸图像库下，算法性能不受影响，而且优于传统的AdaBoost算法和文献[8-9]的改进算法，在噪声样本和存在一些罕见的难分类样本情况下仍能有效提高人脸图片检测率。但本文还未对改进的两个方面进行关联分析，因此这也是下一步研究的重点方向。

参考文献：

[1]

HAO H， WANG Z， YIN X， et al. Dynamic selection and circulating combination for multiple classier systems [J]. Acta Automatica Sinica， 2011， 37（11）： 1290-1295. （郝红卫，王志彬，殷绪成，等.分类器的动态选择与循环集成方法[J].自动化学报，2011，37（11）：1290-1295.）

[2]

XU Z， XIONG Z， SONG D， et al. Doublenull monopulse lowangle tracking algorithm with array radars [J]. Journal of National University of Defense Technology， 2015， 37（1）： 130-135. （徐振海，熊子源，宋聃，等.阵列雷达双零点单脉冲低角跟踪算法[J].国防科技大学学报，2015，37（1）：130-135.）

[3]

YANG D， ZHANG Y， ZHAO H， et al. An improved face detection method [J]. Research and Exploration in Laboratory， 2015， 34（2）： 111-116. （杨定礼，张宇林，赵环宇，等.一种改进的人脸检测方法[J].实验室研究与探索，2015，34（2）：111-116.）

[4]

ZHOU Y， LIU Y， WANG C. Contrast research of several human motion detection algorithm [J]. Journal of Jilin University： Information Science Edition， 2009， 27（6）： 652-657. （周游，刘艳滢，王春民.几种人体运动检测算法的比较研究[J].吉林大学学报：信息科学版，2009，27（6）：652-657.）

[5]

MIAO D， ZHENG H， GU G. AdaBoost face detection algorithm based on optimized weighting parameter [J]. Computer Engineering and Applications， 2014， 50（19）： 173-177. （缪丹权，郑河荣，顾国民.基于优化加权参数的AdaBoost人脸检测算法[J].计算机工程与应用，2014，50（19）：173-177）

[6]

LI W，CHEN Z.Improved AdaBoost face detection algorithm [J]. Video Engineering， 2014，38（15）： 207-212. （李文昊，陈泽华.一种改进的AdaBoost人脸检测算法[J].电视技术，2014，38（15）：207-212.）

[7]

YAN Y， GUO Z， YANG J. Fast enhanced AdaBoost algorithm based on dualthreshold [J]. Computer Engineering，2007，33（21）：172-174. （严云洋，郭志波，杨静宇.基于双阈值的增强型AdaBoost快速算法[J].计算机工程，2007，33（21）：172-174.）

[8]

HUANG X， WANG X， LU L. Fast and efficient method of human face detection [J]. Computer Engineering and Applications， 2013， 49（3）： 198-201. （黄兴，王小涛， 陆丽华.一种快速高效的人脸检测方法[J].计算机工程与应用，2013，49（3）：198-201.）

[9]

LI W， NI H. An improved AdaBoost training algorithm [J]. Journal of Jilin University： Science Edition， 2011，49（3）：498-504. （李文辉，倪洪印.一种改进的AdaBoost训练算法[J].吉林大学学报：理学版，2011，49（3）：498-504.）

[10]

GAO W， TANG Y， ZHU M. Study on the cascade classifier in target detection under complex background [J]. Chinese Journal of Physics， 2014， 63（9）：094204-1-094204-9. （高文，汤洋，朱明.复杂背景下目标检测的级联分类器算法研究[J].物理学报，2014，63（9）：094204-1-094204-9）

[11]

VIOLA P， JONES M. Robust realtime face detection [J]. International Journal of Computer Vision， 2004， 57（2）： 137-154.

[12]

JIANG W， GUO G， LAI Z. An improved AdaBoost algorithm based on new Harrlike feature for face detection [J]. Journal of Shandong University： Engineering Science， 2014，44（2）：43-48. （江伟坚，郭躬德，赖智铭.基于新Haarlike特征的AdaBoost人脸检测算法[J].山东大学学报：工学版，2014，44（2）：43-48.）

[13]

HE Q， LI N， LUO W， et al. A survey of machine learning algorithms for big data [J]. Pattern Recognition and Artificial Intelligence， 2014， 27（4）： 327-336. （何清，李宁，罗文娟，等.大数据下的机器学习算法综述[J].模式识别与人工智能，2014，27（4）：327-336.）

[14]

ZHANG X， SHAN S， CAO B， et al. CASPEAL： a largescale Chinese face database and some primary evaluations [J]. Journal of ComputerAided Design & Computer Graphics， 2005， 17（1）： 9-17. （张晓华，山世光，曹波，等.CASPEAL大规模中国人脸图像数据库及其基本评测介绍[J].计算机辅助设计与图形学学报，2005，17（1）：9-17.）

[15]

GU S. Face preprocessing algorithm in good complex illumination [J]. Computer Engineering and Applications， 2014， 50（19）： 187-191. （顾思思.复杂光照条件下的人脸预处理算法[J].计算机工程与应用，2014，50（19）：187-191.）