然得过高估计假设的出错率，这是因为它不是计算某一算法的样本复杂度(即使存在一个简单的一致算法)，而是对任意一致算法都成立的一个样本复杂度的上界。这就使得基本的PAC模型不能预测学习曲线(1earning curve)。
4.4 Boosting 方法
Boosting 原意为提升、加强。现在一般指的是将弱学习算法提升为强学习算法的一类算法。Boosting 算法是在Kearns 和Valiant 证明后才真正成熟起来的。
1990 年，Schapire 最先构造出一种多项式级的算法，即最初的Boosting算法。这种算法可以将弱分类规则转化成强分类规则。一年后，Freund 提出了一种效率更高的Boosting 算法。1993 年，Drucker 和Schapire 第一次以神经网络作为弱学习器，应用Boosting 算法来解决实际的OCR 问题。
Boosting 算法在分类、建模、图像分割、数据挖掘等领域均已得到简单而有效的应用。1995 年，Freund 和Schapire 提出的Adaboost，是对Boosting 算法的一大提高。
4.5 Adaboost算法性能分析
强分类器H(x)对训练样本集的误判率称为训练误判率，记为?，则有：
1R??ED[H(x)?y]??N
Ni?1其中，
R?{10ififH(xi)?yi
H(xi)?yi对于AdaBoost算法，Freund和Schapire 给出了关于训练误判率的重要理论结果。定理：假设运行Adaboost算法经过T轮训练后生成的弱分类器分别h1,，??hT，其对样本集误判率分别?t，则训练误判率有上界：?t?0.5。详细的证明过程可参见文献。在定理中，如果每个?t?0.5，令?t?0.5??t则最终强分类器H(x)的训练误判率上界可改写为：
???1?4?t2?et?1T?2??t2t?1T
由此可见，训练误判率：随训练轮数T的增大呈指数级的减小。特别的，如果所有的弱分类器误判率都相等，即?t??1，?t??1上式可简化为：
??exp(?2T?)
可见，强分类器误判率随着弱分类器数量增多和弱分类器误判率的降低而迅速下降。只要有足够多的弱分类器，就可以使强分类器达到任意低的误判率。对于两分类问
2121
题，只需要弱学习算法的准确性略好于随机猜测，便可以保证Adaboost算法收敛。
第5章 矩形特征与积分图
5.1 引言
本章节将描述对AdaBoost 人脸检测训练算法速度很重要的两方面，特征的选取和特征值的计算。
把矩形作为人脸检测的特征向量，称为矩形特征。本算法选取了最简单的5个矩形特征模板进行训练，以得到一套用于人脸检测的最适合的矩形特征，事实证明，这种特征选取方法的训练速度虽然不快，但是检测效率很高。
Viola 提出将积分图(integral image)应用到特征值的计算之中。积分图的引用，可以只对图像进行一次遍历计算，就能够在用常量时间完成每个特征值的计算，这使得训练和检测的速度大大提升。
5.2 矩形特征
5.2.1 概述
将矩形特征作为对输入图像的人脸检测的特征向量，称为矩形特征。在给定有限的数据情况下，基于特征的检测能够编码特定区域的状态，而且基于特征的系统比基于象素的系统要快得多。
矩形特征对一些简单的图形结构，比如边缘、线段，比较敏感，但是其只能描述特定走向（水平、垂直、对角）的结构，因此比较粗略。如下图5-1，脸部一些特征能够由矩形特征简单地描绘，例如，通常，眼睛要比脸颊颜色更深；鼻梁两侧要比鼻梁颜色要深；嘴巴要比周围颜色更深。
对于一个24×24 检测器，其内的矩形特征数量超过160,000 个，必须通过特定算法甄选合适的矩形特征，并将其组合成强分类器才能检测人脸。
22
图5-1 矩形特征在人脸上的特征匹配
(上行是24×24 子窗口内选出的矩形特征， 下行是子窗口检测到的与矩形特征的匹配)
5.2.2 特征模板
我们将使用简单矩形组合作为我们的特征模板。这类特征模板都是由两个或多个全等的矩形相邻组合而成，特征模板内有白色和黑色两种矩形（定义左上角的为白色，然后依次交错），并将此特征模板的特征值定义为白色矩形像素和减去黑色矩形像素和。本算法选取了最简单的5个矩形特征模板进行训练，以得到一套用于人脸检测的最合适的矩形特征，事实证明，这种特征选取方法的训练速度虽然不快，但是检测效率很高。
通过改变特征模板的大小和位置，可在图像子窗口中穷举出大量的特征。为了描述的方便，本文将图5-1的特征模板称为“特征原型”；特征原型在图像子窗口中扩展（平移伸缩）得到的矩形特征数值（feature value）称为“特征值”。
最简单的5个矩形特征模板： 23
(a) (b) (c) (d) (e)
图5-2 人脸检测使用的矩形特征值
矩形特征值是指图像中两个或多个形状大小相同的矩形内所有像素的灰度值之和的差值。对于图5-2中的a、b和e这类特征，特征数值计算公式为：
v?Sum白?Sum黑 （5.1）
而对于c、d来说，计算公式如下：
v?Sum白?2?Sum黑 （5.2） 公式（5.2）将黑色区域像素和乘以2，是为了使两种矩形区域中的像素数目一致。 假设训练或者检测窗口的大小为W?H个像素，w,h 分别为特征原型的长、宽，图5-2所示五种特征原型对应的wh分别为：21，12，31，13，22。
HW 令X?[]，Y?[]，“[]”表示取整。一个w?h的特征原型在W?H子窗口产
hw生的矩形特征数量可用下面的公式计算：
X?1Y?1)?(H?1?h) （5.3） X?Y?(W?1?w225.3 积分图
5.3.1 积分图的概念
积分图像就是将原图像中任一点的左上方的全部像素相加作为当前点像素值所
得到的图像。通过积分图像可以方便的计算出原图像中任意矩形区域内的像素点的和的值，而不用每次都重新计算，从而达到加快计算的目的。
b一个简单的微积分类比：如果我们要经常计算?f(x)dx，那我们会先计算
abF(x)??f(x)dx，那么?f(x)dx?F(b)?F(a)。见下图5-3。积分图的含义与此类似。
a24
相关推荐：
loading