浅析人脸检测之Haar分类器方法(2)

我现在脑子里浮现了很多问题，总结起来大概有这么些个： ??弱分类器和强分类器是什么？ ??弱分类器是怎么得到的？ ??强分类器是怎么得到的？ ??二叉决策树是什么？

要回答这一系列问题，我得跟你罗嗦一会儿了，这得从AdaBoost的身世说起。

2.2.1 AdaBoost的身世之谜

关于AdaBoost的身世，我把相关英文文献从上世纪80年代一直下到2001年，我发现我在短时间内没法读完，所以我只能尝试着从别人的总结中拼凑那些离散的片段，难免有误。

之前讲Haar分类器的前世今生也简单说过AdaBoost的身世，但是说的还不透。我比较喜欢查算法的户口，所以新写了一章查了下去。

AdaBoost的老祖宗可以说是机器学习的一个模型，它的名字叫PAC(Probably Approximately Correct)。

PAC模型是计算学习理论中常用的模型，是Valiant牛在我还没出生的1984年提出来的【5】，他认为“学习\是模式明显清晰或模式不存在时仍能获取知识的一种“过程”，并给出了一个从计算角度来获得这种“过程\的方法，这种方法包括：

(1)适当信息收集机制的选择； (2)学习的协定；

(3)对能在合理步骤内完成学习的概念的分类。

PAC学习的实质就是在样本训练的基础上，使算法的输出以概率接近未知的目标概念。PAC学习模型是考虑样本复杂度(指学习器收敛到成功假设时至少所需的训练样本数)和计算复杂度(指学习器收敛到成功假设时所

需的计算量)的一个基本框架，成功的学习被定义为形式化的概率理论。（来自论文《基于Adaboost的人脸检测方法及眼睛定位算法研究》）

简单说来，PAC学习模型不要求你每次都正确，只要能在多项式个样本和多项式时间内得到满足需求的正确率，就算是一个成功的学习。

基于PAC学习模型的理论分析，Valiant牛提出了Boosting算法【5】，Boosting算法涉及到两个重要的概念就是弱学习和强学习，所谓的弱学习，就是指一个学习算法对一组概念的识别率只比随机识别好一点，所谓强学习，就是指一个学习算法对一组概率的识别率很高。现在我们知道所谓的弱分类器和强分类器就是弱学习算法和强学习算法。弱学习算法是比较容易获得的，获得过程需要数量巨大的假设集合，这个假设集合是基于某些简单规则的组合和对样本集的性能评估而生成的，而强学习算法是不容易获得的，然而，Kearns 和Valiant 两头牛提出了弱学习和强学习等价的问题 【6】 并证明了只要有足够的数据，弱学习算法就能通过集成的方式生成任意高精度的强学习方法。这一证明使得Boosting有了可靠的理论基础，Boosting算法成为了一个提升分类器精确性的一般性方法。【4】

1990年，Schapire牛提出了第一个多项式时间的算法【7】，1年后Freund牛又提出了一个效率更高的Boosting算法【8】。然而，Boosting算法还是存在着几个主要的问题，其一Boosting算法需要预先知道弱学习算法学习正确率的下限即弱分类器的误差，其二Boosting算法可能导致后来的训练过分集中于少数特别难区分的样本，导致不稳定。针对Boosting的若干缺陷，Freund和Schapire牛于1996年前后提出了一个实际可用的自适应Boosting算法AdaBoost【9】，AdaBoost目前已发展出了大概四种形式的算法，Discrete AdaBoost（AdaBoost.M1）、Real AdaBoost、LogitBoost、gentle AdaBoost,本文不做一一介绍。至此，AdaBoost的身世之谜就这样揭开鸟。同时弱分类器和强分类器是什么的问题也解释清楚了。剩下3个问题，我们先看一下，弱分类器是如何得到的。

2.2.2 弱分类器的孵化

最初的弱分类器可能只是一个最基本的Haar-like特征，计算输入图像

的Haar-like特征值，和最初的弱分类器的特征值比较，以此来判断输入图像是不是人脸，然而这个弱分类器太简陋了，可能并不比随机判断的效果好，对弱分类器的孵化就是训练弱分类器成为最优弱分类器，注意这里的最优不是指强分类器，只是一个误差相对稍低的弱分类器，训练弱分类器实际上是为分类器进行设置的过程。至于如何设置分类器，设置什么，我们首先分别看下弱分类器的数学结构和代码结构。

??数学结构

一个弱分类器

由子窗口图像x，一个特征f，指示不等号方

向的p和阈值组成。P的作用是控制不等式的方向，使得不等式都是<号，形式方便。

??代码结构 1 /*

2 * CART classifier 3 */

4 typedef struct CvCARTHaarClassifier 5 {

6 CV_INT_HAAR_CLASSIFIER_FIELDS() 7 int count; 8 int* compidx;

9 CvTHaarFeature* feature; 10 CvFastHaarFeature* fastfeature; 11 float* threshold; 12 int* left;

13 int* right; 14 float* val;

15 } CvCARTHaarClassifier;

代码结构中的threshold即代表数学结构中的阈值。

这个阈值究竟是干什么的？我们先了解下CvCARTHaarClassifier这个结构，注意CART这个词，它是一种二叉决策树，它的提出者Leo Breiman等牛称其为“分类和回归树（CART）”。什么是决策树？我如果细讲起来又得另起一章，我只简略介绍它。

“机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。”（来自《维基百科》）

决策树包含：分类树，回归树，分类和回归树（CART），CHAID 。 分类和回归的区别是，分类是当预计结果可能为两种类型(例如男女，输赢等)使用的概念。 回归是当局域结果可能为实数(例如房价，患者住院时间等)使用的概念。

决策树用途很广可以分析因素对事件结果的影响（详见维基百科），同时也是很常用的分类方法，我举个最简单的决策树例子，假设我们使用三个Haar-like特征f1，f2，f3来判断输入数据是否为人脸，可以建立如下决策树：

可以看出，在分类的应用中，每个非叶子节点都表示一种判断，每个路径代表一种判断的输出，每个叶子节点代表一种类别，并作为最终判断的结果。

一个弱分类器就是一个基本和上图类似的决策树，最基本的弱分类器只包含一个Haar-like特征，也就是它的决策树只有一层，被称为树桩（stump）。

最重要的就是如何决定每个结点判断的输出，要比较输入图片的特征值和弱分类器中特征，一定需要一个阈值，当输入图片的特征值大于该阈值时才判定其为人脸。训练最优弱分类器的过程实际上就是在寻找合适的分类器阈值，使该分类器对所有样本的判读误差最低。

具体操作过程如下：

1）对于每个特征 f，计算所有训练样本的特征值，并将其排序。 扫描一遍排好序的特征值，对排好序的表中的每个元素，计算下面四个值：

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库浅析人脸检测之Haar分类器方法(2)在线全文阅读。