网站建设 金手指 下拉22,域名可以同时做邮箱和网站么,安全管理平台,长乐区建设局网站由于工作需要#xff0c;我开始研究人脸检测部分的算法#xff0c;这期间断断续续地学习Haar分类器的训练以及检测过程#xff0c;在这里根据各种论文、网络资源的查阅和对代码的理解做一个简单的总结。我试图概括性的给出算法的起源、全貌以及细节的来龙去脉#xff0c;但… 由于工作需要我开始研究人脸检测部分的算法这期间断断续续地学习Haar分类器的训练以及检测过程在这里根据各种论文、网络资源的查阅和对代码的理解做一个简单的总结。我试图概括性的给出算法的起源、全貌以及细节的来龙去脉但是水平有限只能解其大概希望对初学者起到帮助更主要的是对我个人学习的一次提炼。
一、Haar分类器的前世今生
人脸检测属于计算机视觉的范畴早期人们的主要研究方向是人脸识别即根据人脸来识别人物的身份后来在复杂背景下的人脸检测需求越来越大人脸检测也逐渐作为一个单独的研究方向发展起来。
目前的人脸检测方法主要有两大类基于知识和基于统计。
“基于知识的方法主要利用先验知识将人脸看作器官特征的组合根据眼睛、眉毛、嘴巴、鼻子等器官的特征以及相互之间的几何位置关系来检测人脸。基于统计的方法则将人脸看作一个整体的模式——二维像素矩阵从统计的观点通过大量人脸图像样本构造人脸模式空间根据相似度量来判断人脸是否存在。在这两种框架之下发展了许多方法。目前随着各种方法的不断提出和应用条件的变化将知识模型与统计模型相结合的综合系统将成为未来的研究趋势。”来自论文《基于Adaboost的人脸检测方法及眼睛定位算法研究》
基于知识的人脸检测方法 Ø 模板匹配 Ø 人脸特征 Ø 形状与边缘 Ø 纹理特性 Ø 颜色特征
基于统计的人脸检测方法 Ø 主成分分析与特征脸 Ø 神经网络方法 Ø 支持向量机 Ø 隐马尔可夫模型 Ø Adaboost算法
本文中介绍的Haar分类器方法包含了Adaboost算法稍候会对这一算法做详细介绍。所谓分类器在这里就是指对人脸和非人脸进行分类的算法在机器学习领域很多算法都是对事物进行分类、聚类的过程。OpenCV中的ml模块提供了很多分类、聚类的算法。
注聚类和分类的区别是什么一般对已知物体类别总数的识别方式我们称之为分类并且训练的数据是有标签的比如已经明确指定了是人脸还是非人脸这是一种有监督学习。也存在可以处理类别总数不确定的方法或者训练的数据是没有标签的这就是聚类不需要学习阶段中关于物体类别的信息是一种无监督学习。
其中包括Mahalanobis距离、K均值、朴素贝叶斯分类器、决策树、Boosting、随机森林、Haar分类器、期望最大化、K近邻、神经网络、支持向量机。
我们要探讨的Haar分类器实际上是Boosting算法的一个应用Haar分类器用到了Boosting算法中的AdaBoost算法只是把AdaBoost算法训练出的强分类器进行了级联并且在底层的特征提取中采用了高效率的矩形特征和积分图方法这里涉及到的几个名词接下来会具体讨论。
虽说haar分类器采用了Boosting的算法但在OpenCV中Haar分类器与Boosting没有采用同一套底层数据结构《Learning OpenCV》中有这样的解释“Haar分类器它建立了boost筛选式级联分类器。它与ML库中其他部分相比有不同的格局因为它是在早期开发的并完全可用于人脸检测。”
是的在2001年Viola和Jones两位大牛发表了经典的《Rapid Object Detection using a Boosted Cascade of Simple Features》【1】和《Robust Real-Time Face Detection》【2】在AdaBoost算法的基础上使用Haar-like小波特征和积分图方法进行人脸检测他俩不是最早使用提出小波特征的但是他们设计了针对人脸检测更有效的特征并对AdaBoost训练出的强分类器进行级联。这可以说是人脸检测史上里程碑式的一笔了也因此当时提出的这个算法被称为Viola-Jones检测器。又过了一段时间Rainer Lienhart和Jochen Maydt两位大牛将这个检测器进行了扩展【3】最终形成了OpenCV现在的Haar分类器。之前我有个误区以为AdaBoost算法就是Viola和Jones搞出来的因为网上讲Haar分类器的地方都在大讲特讲AdaBoost所以我错觉了后来理清脉络AdaBoost是Freund 和Schapire在1995年提出的算法是对传统Boosting算法的一大提升。Boosting算法的核心思想是将弱学习方法提升成强学习算法也就是“三个臭皮匠顶一个诸葛亮”它的理论基础来自于Kearns 和Valiant牛的相关证明【4】在此不深究了。反正我是能多简略就多简略的把Haar分类器的前世今生说完鸟得出的结论是大牛们都是成对儿的。。。额回到正题Haar分类器 Haar-like特征 积分图方法 AdaBoost 级联
注为何称其为Haar-like这个名字是我从网上看来的《Learning OpenCV》中文版提到Haar分类器使用到Haar特征但这种说法不确切应该称为类Haar特征Haar-like就是类Haar特征的意思。
二、Haar分类器的浅入浅出
之所以是浅入浅出是因为我暂时深入不能只是根据其他人的总结我加以梳理归纳用自己的理解阐述出来难免会有错误欢迎指正。
Haar分类器算法的要点如下
① 使用Haar-like特征做检测。
② 使用积分图Integral Image对Haar-like特征求值进行加速。
③ 使用AdaBoost算法训练区分人脸和非人脸的强分类器。
④ 使用筛选式级联把强分类器级联到一起提高准确率。
2.1 Haar-like特征你是何方神圣
一看到Haar-like特征这玩意儿就头大的人举手。好很多人。那么我先说下什么是特征我把它放在下面的情景中来描述假设在人脸检测时我们需要有这么一个子窗口在待检测的图片窗口中不断的移位滑动子窗口每到一个位置就会计算出该区域的特征然后用我们训练好的级联分类器对该特征进行筛选一旦该特征通过了所有强分类器的筛选则判定该区域为人脸。
那么这个特征如何表示呢好了这就是大牛们干的好事了。后人称这他们搞出来的这些东西叫Haar-Like特征。
下面是Viola牛们提出的Haar-like特征。 下面是Lienhart等牛们提出的Haar-like特征。 这些所谓的特征不就是一堆堆带条纹的矩形么到底是干什么用的我这样给出解释将上面的任意一个矩形放到人脸区域上然后将白色区域的像素和减去黑色区域的像素和得到的值我们暂且称之为人脸特征值如果你把这个矩形放到一个非人脸区域那么计算出的特征值应该和人脸特征值是不一样的而且越不一样越好所以这些方块的目的就是把人脸特征量化以区分人脸和非人脸。
为了增加区分度可以对多个矩形特征计算得到一个区分度更大的特征值那么什么样的矩形特征怎么样的组合到一块可以更好的区分出人脸和非人脸呢这就是AdaBoost算法要做的事了。这里我们先放下积分图这个概念不管为了让我们的思路连贯我直接开始介绍AdaBoost算法。 2.2 AdaBoost你给我如实道来
本节旨在介绍AdaBoost在Haar分类器中的应用所以只是描述了它在Haar分类器中的特性而实际上AdaBoost是一种具有一般性的分类器提升算法它使用的分类器并不局限某一特定算法。
上面说到利用AdaBoost算法可以帮助我们选择更好的矩阵特征组合其实这里提到的矩阵特征组合就是我们之前提到的分类器分类器将矩阵组合以二叉决策树的形式存储起来。
我现在脑子里浮现了很多问题总结起来大概有这么些个
v 弱分类器和强分类器是什么
v 弱分类器是怎么得到的
v 强分类器是怎么得到的
v 二叉决策树是什么
要回答这一系列问题我得跟你罗嗦一会儿了这得从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 AdaBoostAdaBoost.M1、Real AdaBoost、LogitBoost、gentle AdaBoost,本文不做一一介绍。至此AdaBoost的身世之谜就这样揭开鸟。同时弱分类器和强分类器是什么的问题也解释清楚了。剩下3个问题我们先看一下弱分类器是如何得到的。
2.2.2 弱分类器的孵化
最初的弱分类器可能只是一个最基本的Haar-like特征计算输入图像的Haar-like特征值和最初的弱分类器的特征值比较以此来判断输入图像是不是人脸然而这个弱分类器太简陋了可能并不比随机判断的效果好对弱分类器的孵化就是训练弱分类器成为最优弱分类器注意这里的最优不是指强分类器只是一个误差相对稍低的弱分类器训练弱分类器实际上是为分类器进行设置的过程。至于如何设置分类器设置什么我们首先分别看下弱分类器的数学结构和代码结构。
² 数学结构 一个弱分类器由子窗口图像x一个特征f指示不等号方向的p和阈值组成。P的作用是控制不等式的方向使得不等式都是号形式方便。
/*
* CART classifier
*/
typedef struct CvCARTHaarClassifier
{CV_INT_HAAR_CLASSIFIER_FIELDS()int count;int* compidx;CvTHaarFeature* feature;CvFastHaarFeature* fastfeature;float* threshold;int* left;int* right;float* val;
} CvCARTHaarClassifier;代码结构中的threshold即代表数学结构中的阈值。
这个阈值究竟是干什么的我们先了解下CvCARTHaarClassifier这个结构注意CART这个词它是一种二叉决策树它的提出者Leo Breiman等牛称其为“分类和回归树CART”。什么是决策树我如果细讲起来又得另起一章我只简略介绍它。
“机器学习中决策树是一个预测模型他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象而每个分叉路径则代表的某个可能的属性值而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出若欲有复数输出可以建立独立的决策树以处理不同输出。从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。”来自《维基百科》
决策树包含分类树回归树分类和回归树CARTCHAID 。
分类和回归的区别是分类是当预计结果可能为两种类型(例如男女输赢等)使用的概念。 回归是当局域结果可能为实数(例如房价患者住院时间等)使用的概念。
决策树用途很广可以分析因素对事件结果的影响 可以看出在分类的应用中每个非叶子节点都表示一种判断每个路径代表一种判断的输出每个叶子节点代表一种类别并作为最终判断的结果。
一个弱分类器就是一个基本和上图类似的决策树最基本的弱分类器只包含一个Haar-like特征也就是它的决策树只有一层被称为树桩stump。
最重要的就是如何决定每个结点判断的输出要比较输入图片的特征值和弱分类器中特征一定需要一个阈值当输入图片的特征值大于该阈值时才判定其为人脸。训练最优弱分类器的过程实际上就是在寻找合适的分类器阈值使该分类器对所有样本的判读误差最低。
具体操作过程如下
1对于每个特征 f计算所有训练样本的特征值并将其排序。 扫描一遍排好序的特征值对排好序的表中的每个元素计算下面四个值 全部人脸样本的权重的和t1 全部非人脸样本的权重的和t0 在此元素之前的人脸样本的权重的和s1 在此元素之前的非人脸样本的权重的和s0
2最终求得每个元素的分类误差
在表中寻找r值最小的元素则该元素作为最优阈值。有了该阈值我们的第一个最优弱分类器就诞生了。
在这漫长的煎熬中我们见证了一个弱分类器孵化成长的过程并回答了如何得到弱分类器以及二叉决策树是什么。最后的问题是强分类器是如何得到的。
2.2.3 弱分类器的化蝶飞
首先看一下强分类器的代码结构:
span stylefont-family:宋体; /*/spaninternal stage classifier */
typedef struct CvStageHaarClassifier
{CV_INT_HAAR_CLASSIFIER_FIELDS()int count;float threshold;CvIntHaarClassifier** classifier;
}CvStageHaarClassifier;/* internal weak classifier*/
typedef struct CvIntHaarClassifier
{CV_INT_HAAR_CLASSIFIER_FIELDS()
} CvIntHaarClassifier;这里要提到的是CvIntHaarClassifier结构
它就相当于一个接口类当然是用C语言模拟的面向对象思想利用CV_INT_HAAR_CLASSIFIER_FIELDS()这个宏让弱分类CvCARTHaarClassifier强分类器和CvStageHaarClassifier继承于CvIntHaarClassifier。 强分类器的诞生需要T轮的迭代具体操作如下
1. 给定训练样本集S共N个样本其中X和Y分别对应于正样本和负样本 T为训练的最大循环次数
2. 初始化样本权重为1/N 即为训练样本的初始概率分布
3. 第一次迭代训练N个样本得到第一个最优弱分类器步骤见2.2.2节
4. 提高上一轮中被误判的样本的权重
5. 将新的样本和上次本分错的样本放在一起进行新一轮的训练。
6. 循环执行4-5步骤T轮后得到T个最优弱分类器。
7.组合T个最优弱分类器得到强分类器组合方式如下 相当于让所有弱分类器投票再对投票结果按照弱分类器的错误率加权求和将投票加权求和的结果与平均投票结果比较得出最终的结果。
至此我们看到其实我的题目起的漂亮却并不贴切强分类器的脱颖而出更像是民主的投票制度众人拾材火焰高强分类器不是个人英雄主义的的产物而是团结的力量。但从宏观的局外的角度看整个AdaBoost算法就是一个弱分类器从孵化到化蝶的过程。小人物的奋斗永远是理想主义者们津津乐道的话题。但暂时让我们放下AdaBoost继续探讨Haar分类器的其他特性吧。
2.3 强分类器的强强联手
至今为止我们好像一直在讲分类器的训练实际上Haar分类器是有两个体系的训练的体系和检测的体系。训练的部分大致都提到了还剩下最后一部分就是对筛选式级联分类器的训练。我们看到了通过AdaBoost算法辛苦的训练出了强分类器然而在现实的人脸检测中只靠一个强分类器还是难以保证检测的正确率这个时候需要一个豪华的阵容训练出多个强分类器将它们强强联手最终形成正确率很高的级联分类器这就是我们最终的目标Haar分类器。
那么训练级联分类器的目的就是为了检测的时候更加准确这涉及到Haar分类器的另一个体系检测体系检测体系是以现实中的一幅大图片作为输入然后对图片中进行多区域多尺度的检测所谓多区域是要对图片划分多块对每个块进行检测由于训练的时候用的照片一般都是20*20左右的小图片所以对于大的人脸还需要进行多尺度的检测多尺度检测机制一般有两种策略一种是不改变搜索窗口的大小而不断缩放图片这种方法显然需要对每个缩放后的图片进行区域特征值的运算效率不高而另一种方法是不断初始化搜索窗口size为训练时的图片大小不断扩大搜索窗口进行搜索解决了第一种方法的弱势。在区域放大的过程中会出现同一个人脸被多次检测这需要进行区域的合并这里不作探讨。
无论哪一种搜索方法都会为输入图片输出大量的子窗口图像这些子窗口图像经过筛选式级联分类器会不断地被每一个节点筛选抛弃或通过。
它的结构如图所示。 我想你一定觉得很熟悉这个结构不是很像一个简单的决策树么。
在代码中它的结构如下
/* internal tree cascade classifier node */
typedef struct CvTreeCascadeNode
{CvStageHaarClassifier* stage;struct CvTreeCascadeNode* next;struct CvTreeCascadeNode* child;struct CvTreeCascadeNode* parent;struct CvTreeCascadeNode* next_same_level;struct CvTreeCascadeNode* child_eval;int idx;int leaf;
} CvTreeCascadeNode;
/* internal tree cascade classifier */
typedef struct CvTreeCascadeClassifier
{CV_INT_HAAR_CLASSIFIER_FIELDS()CvTreeCascadeNode* root; /* root of the tree */CvTreeCascadeNode* root_eval; /* root node for the filtering */int next_idx;
} CvTreeCascadeClassifier;级联强分类器的策略是将若干个强分类器由简单到复杂排列希望经过训练使每个强分类器都有较高检测率而误识率可以放低比如几乎99%的人脸可以通过但50%的非人脸也可以通过这样如果有20个强分类器级联那么他们的总识别率为0.99^20 98%错误接受率也仅为0.5^20 0.0001%。这样的效果就可以满足现实的需要了但是如何使每个强分类器都具有较高检测率呢为什么单个的强分类器不可以同时具有较高检测率和较高误识率呢
下面我们讲讲级联分类器的训练。主要参考了论文《基于Adaboost的人脸检测方法及眼睛定位算法研究》
设K是一个级联检测器的层数D是该级联分类器的检测率F是该级联分类器的误识率di是第i层强分类器的检测率fi是第i层强分类器的误识率。如果要训练一个级联分类器达到给定的F值和D值只需要训练出每层的d值和f值这样 d^K D,f^K F
级联分类器的要点就是如何训练每层强分类器的d值和f值达到指定要求。
AdaBoost训练出来的强分类器一般具有较小的误识率但检测率并不很高一般情况下高检测率会导致高误识率这是强分类阈值的划分导致的要提高强分类器的检测率既要降低阈值要降低强分类器的误识率就要提高阈值这是个矛盾的事情。据参考论文的实验结果增加分类器个数可以在提高强分类器检测率的同时降低误识率所以级联分类器在训练时要考虑如下平衡一是弱分类器的个数和计算时间的平衡二是强分类器检测率和误识率之间的平衡。具体训练方法如下,我用伪码的形式给出
1设定每层最小要达到的检测率d最大误识率f最终级联分类器的误识率Ft
2P人脸训练样本N非人脸训练样本D01.0F01.0
3i0
4for : FiFt l i; l ni0;FiFi-1; l for : Fif*Fi-1 n ni; n 利用AdaBoost算法在P和N上训练具有ni个弱分类器的强分类器; n 衡量当前级联分类器的检测率Di和误识率Fi; n for : did*Di-1; Ø 降低第i层的强分类器阈值; Ø 衡量当前级联分类器的检测率Di和误识率Fi; n N Φ; n 利用当前的级联分类器检测非人脸图像将误识的图像放入N;
2.4 积分图是一个加速器
之所以放到最后讲积分图Integral image不是因为它不重要正相反它是Haar分类器能够实时检测人脸的保证。当我把Haar分类器的主脉络都介绍完后其实在这里引出积分图的概念恰到好处。
在前面的章节中我们熟悉了Haar-like分类器的训练和检测过程你会看到无论是训练还是检测每遇到一个图片样本每遇到一个子窗口图像我们都面临着如何计算当前子图像特征值的问题一个Haar-like特征在一个窗口中怎样排列能够更好的体现人脸的特征这是未知的所以才要训练而训练之前我们只能通过排列组合穷举所有这样的特征仅以Viola牛提出的最基本四个特征为例在一个24×24size的窗口中任意排列至少可以产生数以10万计的特征对这些特征求值的计算量是非常大的。
而积分图就是只遍历一次图像就可以求出图像中所有区域像素和的快速算法大大的提高了图像特征值计算的效率。
我们来看看它是怎么做到的。
积分图是一种能够描述全局信息的矩阵表示方法。积分图的构造方式是位置i,j处的值ii(i,j)是原图像(i,j)左上角方向所有像素的和 积分图构建算法
1用s(i,j)表示行方向的累加和初始化s(i,-1)0;
2用ii(i,j)表示一个积分图像初始化ii(-1,i)0
3逐行扫描图像递归计算每个像素(i,j)行方向的累加和s(i,j)和积分图像ii(i,j)的值 s(i,j)s(i,j-1)f(i,j) ii(i,j)ii(i-1,j)s(i,j) 4扫描图像一遍当到达图像右下角像素时积分图像ii就构造好了。
积分图构造好之后图像中任何矩阵区域的像素累加和都可以通过简单运算得到如图所示。 三、Haar分类器你敢更快点吗 这一章我简略的探讨下Haar分类器的检测效率。
我尝试过的几种方法
1尝试检测算法与跟踪算法相结合原本以为Camshift是个轻量级的算法但是正如我后来看到的建立反向投影图的效率实在不高在PC上效果不错但是在ios上速度很慢这个我后来发现可能是因为ios浮点运算效率不高的原因。但是即便速度能上去靠Camshift跟踪算法太依赖肤色了导致脖子或是手什么的干扰很严重这个调起来很费神也不一定能调好。
2修改OpenCV中Haar检测函数的参数效果非常明显得出的结论是搜索窗口的搜索区域是提高效率的关键。
3根据2的启发我打算利用YCbCr颜色空间粗估肤色区域以减少人脸的搜索面积但是后来苦于没能高效率的区分出肤色区域放弃了该方法。
4换了策略考虑到视频中人脸检测的特殊性上一帧人脸的位置信息对下一帧的检测有很高的指导价值所以采有帧间约束的方法减少了人脸搜索的区域并且动态调整Haar检测函数的参数得到了较高的效率。
5其他关于算法之外的优化需要根据不同的处理器做具体的优化。
四、总结
之前没怎么接触到计算机视觉领域这次reseach对我来说是一个不小的挑战发现其中涉及大量的数学知识线代统计学数学分析等等虽然感到困难重重但我感到莫大的兴趣尤其是机器学习领域在我眼前展开的是一幅美妙的画面大牛们神乎其技各显神通复杂的数学公式背后蕴含着简单的哲理和思想。
