以下文章摘录自：
《机器学习观止——核心原理与实践》
京东： https://item.jd.com/13166960.html
当当：http://product.dangdang.com/29218274.html
(由于博客系统问题，部分公式、图片和格式有可能存在显示问题，请参阅原书了解详情)
1.1.1 Haar-like feature
Haar-like最早应该可以追溯到1998年Papageorgiou等人发表的《A General Framework for Object Detection》中。据悉“Haar-like”这个名称，是因为它和“Haar wavelet”比较类似而得名的。
图 ‑ 一些基础的Haar-like特征
另外，后来业界有不少人也对Haar-like做了进一步分析和扩展，例如R.Lienhart等人在《An extended set of Haar-like features for rapid object detection》中将特征扩展到了14个;Paul Viola和Michael Jones则于2001年的论文《Rapid Object Detection using a Boosted Cascade of Simple Features》中提出了积分图计算的概念等等。
图 ‑ 一些扩展的Haar-like特征
接下来我们分别介绍Haar-like的特征提取，特征数量计算，积分图以及Adaboost等，它们都是我们理解Haar-like的核心基础。
1.1.1.1 Haar-like特征提取
Haar-like特征提取算法的处理过程并不复杂，核心思想就是：
特征值= 将feature中黑色部分的所有像素值之和 - 白色部分所有像素值之和
另外，计算特征值时还需要考虑增加一定的权重，以抵消黑白区域的像素值数量差异。例如下面所示的feature:
因为黑色部分的像素点只有白色部分的一半，所以特征值计算公式就要变成：
特征值= 将feature中黑色部分的所有像素值之和*2 - 白色部分所有像素值之和
在实际执行过程中：
l 每个feature是要在原图像上做窗口滑动的，步进为1
l 窗口在宽度或长度上会成比例的放大，然后再次执行上述的滑动操作，直到最后一个比例结束
不难理解，窗口可以放大的最大比例(宽和高)是：
以及
其中wI和hI是整个图像的宽和高，而wwin和hwin是Haar特征的原始宽和高的值。因为我们需要以不同的窗口大小来提取图像特征，这样一来无疑会增加Haar特征的计算量(通常会达到160000+次)。所以如何识别出重复的计算过程，从而有效减少计算量就成为Haar需要重点解决的问题之一了。
1.1.1.2 Haar特征数量
假设：
l 子窗口大小为m*m
l 特征窗口的左上顶点为A(x1,y1)，右下顶点为B(x2, y2)
l 并且上述特征窗口满足(s, t)条件：
n 它的x方向可以被自然数s整除
n 它的y方向可以被自然数t整除
换句话说，特征窗口的最小尺寸为s*t(也就是倍数为1时)，最大尺寸为：
[m/s]*s x [m/t]*t，其中[]表示整除运算符
对于左上角顶点A，它的取值范围如下所示：
对于右下角顶点B，它的取值范围如下所示：
其中：
这样一来，一个m*m子窗口中，所有满足(s,t)条件的特征窗口的数量为：
举例来说，对于一个24*24大小的子窗口，它在如下几种特征模板下的数量分别为：
l (s,t) = (1, 2)
这种特征模板形状如下：
根据前面计算公式，其数量为43200
l (s,t) = (1, 3)
这种特征模板形状如下：
根据前面计算公式，其数量为27600
l (s,t) = (3, 1)
这种特征模板形状如下：
根据前面的计算公式，其数量为27600
1.1.1.3 积分图
前面我们指出了Haar可能会需要大量的计算操作，因而如何降低计算量是其中的一个关键因素。积分图(Integral Image)就是用于解决这个问题的，它来源于《Rapid object detection using a boosted cascade of simple features》这篇paper。
积分图的基本思想不算太复杂，其实就是将可能会被多次用到的计算结果保存起来，以便减少重复计算的过程。具体来讲，就是把图像从原点到其它各个点所形成的矩形区域内的所有像素之和保存到数组中，后续计算Haar时可以直接查找数组得到像素和，从而达到加速的目的。
参考公式如下所示：
以下面的范例来说：
图 ‑ 积分图计算范例
我们如何计算D区域的像素和呢？
以前的办法，就是将D区域内的所有像素值都相加一遍，得到结果——利用积分图则可以降低计算复杂度。
接下来我们讲解一下具体的计算过程。
根据积分图的定义可知，保存到数组中的矩形框应该都是从原点出发的。所以如果我们假设：
A + B + C + D = E
A + B = F
A + C = G
那么不难理解E、F和G都是可以直接从积分图中查询得到的。
因而：
D = E - F - G + A
换句话说，借助于积分图我们只需要简单的几次加减法就可以得到像素求和结果了，从而大大降低了Haar的计算量。
1.1.1.4 AdaBoost
我们通过前面的步骤，已经可以获取到非常多的特征值了，但是它们之间多数是没有相关性(irrelevant)的。以下面的图示为例：
图 ‑ 特征非相关性图例
上半部分是两个特征，左下角是输入图像，右下角则是我们提取特征时的效果图。对于第一个feature，它可以匹配出“人眼比鼻子和脸颊颜色更深”的人脸特点;同理第二个feature，则可以表达“两只眼睛比鼻梁颜色更深”的另一个人脸特点——但这里有一个前提条件，即它们都需要在图像的合适位置时才能发挥作用。
那么我们怎么知道成千上万的features中哪些才是最佳的呢？
这就是Adaboost的“用武之地”了。
当然，AdaBoost本身是一种比较通用的分类器提升算法，而非Haar的“专属利器”。简单来讲，AdaBoost可以帮助Haar在“特征组合选择”上做得更好。
如果从历史渊源的角度来看，AdaBoost实际上是一种自适应的Boosting算法——后者的鼻祖则是L.G.VALIANT，他于1984年发表了一篇名为《A theory of the Learnable》的论文，揭开了Booting领域几十年的发展历程。
图 ‑ A theory of the Learnable
Boosting算法的理论基础是PAC(Probably Approximately Correct)，它是综合考虑了样本复杂度和计算复杂度情况下的一个学习框架。在Valiant提出的Boosting原始算法中，涉及到两个基础概念，即：
l 弱学习
这种学习算法的识别率较弱，只比随机识别好一点
l 强学习
这种学习算法的识别率很强
Michael J. Kearns等人在《The Computational Complexity of Machine Learning》中提出了弱学习和强学习等价的观点，并证明了在数据量足够的条件下，弱学习算法能够通过集成手段生成任意高识别率的强学习算法。
由Freund和Schapire等人提出的Adaboost算法，可以说是对Boosting算法的一大提升。为什么这么说呢？Adaboost是“Adaptive Boosting”的缩写——Adaptive译为“适应性地”，具体而言就是它可以根据弱学习的结果自适应地调整假设的错误率，所以Adaboost不需要预先知道假设的错误率下限。换句话说，它不需要任何关于弱学习器性能的先验知识，而且和Boosting算法具有同样的效率。
具体来讲，Adaboost针对传统boost算法的如下两个问题提出了新的思路：
l 面向同一个训练集，如何做到重复训练的目的
Adaboost会结合每一轮训练出的模型的分类结果，来调整样本的权重(比如本次分类出错的样本，我们在权重上要有相应的侧重，以便下一次训练时可以对它进行“重点关注”)，以实现同一训练集达到不同样本分布的目的
l 弱分类器如何有机组合，达到更好的效果
Adaboost中采用加权表决的方法来组合弱分类器——简单而言就是分类精度越高的弱分类器，其“话语权”越大，以此来将它们组成更加优秀的强分类器
我们参考《Rapid Object Detection using a Boosted Cascade of Simple Features》中对AdaBoost算法的伪代码描述，如下所示：
最终的强分类器表达如下：
简单来讲，其核心思想就是：
l 给定一个数据样本集S(包含n个样本)，它的初始样本权重为1/n。我们训练得到第一个弱分类器
l 针对第一个弱分类器分错的样本，调整它们的样本权重，然后重新训练得到第二个弱分类器
l 经过T个弱分类器后，按照权重叠加，得到最终的强分类器
借助于Adaboost，我们就可以结合Haar-like特征来构建出强大的分类器了——它们二者的组合，在行人检测和人脸识别方向上有广泛应用。
