haar+adaboost结合讲解（偏重实际）
【这是一篇之前总结的文档，大部分来源于csdn和文献，如有未标明引用，请联系我加上。】
目录
1 Haar特征和积分图
1.1 Haar特征的生成
1.2 计算Haar特征值
1.3 Haar特征值归一化
1.4 积分图
2. 级联分类器结构与XML文件含义
2.1 XML的头部
2.2 弱分类器结构
2.3 强分类器结构
2.4 级联分类器
3. 利用并查集合并检测结果窗口
3.1 并查集(Union-Set)
3.2 利用并查集合并检测结果窗口
4. 举例
1 Haar特征和积分图
研究OpenCV中的Adaboost级联分类器。我阅读了OpenCV中所有相关得代码，包括检测和训练部分，发现目前OpenCV中的Adaboost级联分类器代码有以下2个特点：
（1）OpenCV代码中的实际算法与Paul.Viola论文中的原始算法差异很大。最新的训练和检测代码实现了Haar、LBP和HOG特征接口，同时训练代码中支持DAB、LAB、RAB和GAB共4种Adaboost算法，另外还实现了trim weight方法。
（2）OpenCV由于一些历史遗留问题，代码中C结构（CvMat等）和C++结构（Mat::Mat等）共用，难以理解。
可能正是由于这些问题，导致代码极其复杂，没有几个人愿意花费时间去深挖代码。
图1 opencv_traincascade.exe训练程序usage界面
图1显示了opencv_traincascade的usage界面，仅仅一个traincascade训练程序就有如此之多的命令。翻遍目前网上介绍Adaboost级联分类器的文章，没有一篇文章能够完整的介绍上面所有命令的原理，甚至有些文章还存在错误，实在让人头疼。
基于知识共享的原则，我把这几个月分析代码的结果写成一个系列分享给出来，希望能够对OpenCV中的Adaboost级联分类器做出“盖棺定论”，同时也让大家也不再像我一样“摸着石头过河”。
本系列文章不追求高深的原理（其实是我水平低），力求简单粗暴、看完就能懂。目前OpenCV中的Adaboost级联分类器支持多种特征，考虑到篇幅问题，我选择用最基础的Haar特征进行分析。下面是本系列文章的基本写作思路：
首先，由Haar为引子，分析XML分类器中各个结点数值的含义，介绍Adaboost级联分类器的树状结构。
然后，以DAB(DiscreteAdaboost)为基础，介绍traincascade训练程序的原理。
最后，分析最复杂也是效果最好的的GAB(Gentle Adaboost)。
当然由于作者水平有限，难免出现遗漏和错误，真诚的欢迎各位大侠批评指正！接下来进入正题。
1.1 Haar特征的生成
既然是结合Haar特征分析Adaboost级联分类器，那么有必要先对Haar特征进行细致的分析。
Haar特征最先由Paul Viola等提出，后经过RainerLienhart等扩展引入45°倾斜特征，成为现在OpenCV所使用的的样子。图2展示了目前OpenCV（2.4.11版本）所使用的共计14种Haar特征，包括5种Basic特征、3种Core特征和6种Titled(即45°旋转)特征。
图2 OpenCV中使用的的Haar特征
而图1中haarFeatureParams参数中的mode参数正对应了训练过程中所使用的特征集合：
图3 mode参数
（1）如果设置mode为BASIC，则只使用BASIC的5种Haar特征进行训练，训练出的分类器也只包含这5种特征。
（2）如果设置mode为CORE，则使用BASIC的5种+CORE的3种Haar特征进行训练。
（3）如果设置mode为ALL，则使用BASICA的5种+CORE的3种+ALL的6种Titled共14种特征进行训练。
需要说明，训练程序opencv_trancascade.exe一般默认使用BASIC模式，实际中训练和检测效果已经足够好。不建议使用ALL参数，引入Titled倾斜特征需要多计算一张倾斜积分图，会极大的降低训练和检测速度，而且效果也没有论文中说的那么好。
在实际中，Haar特征可以在检测窗口中由放大+平移产生一系列子特征，但是白：黑区域面积比始终保持不变。
如图4，以x3特征为例，在放大+平移过程中白：黑：白面积比始终是1:1:1。首先在红框所示的检测窗口中生成大小为3个像素的最小x3特征；之后分别沿着x和y平移产生了在检测窗口中不同位置的大量最小3像素x3特征；然后把最小x3特征分别沿着x和y放大，再平移，又产生了一系列大一点x3特征；然后继续放大+平移，重复此过程，直到放大后的x3和检测窗口一样大。这样x3就产生了完整的x3系列特征。
图4 x3特征平移+放大产生一系列子特征示意图
那么这些通过放大+平移的获得的子特征到底有多少个？Rainer Lienhart在其论文中给出了完美的解释：假设检测窗口大小为W*H，矩形特征大小为w*h，X和Y为表示矩形特征在水平和垂直方向的能放大的最大比例系数：
图5 特征数量计算示意图
则如图5，在检测窗口Window中，一般矩形特征(upright rectangle)的数量为：
对应于之前的x3特征，当x3特征在24*24大小的检测窗口中时（此时W=H=24，w=3，h=1，X=8，Y=24），一共能产生27600个子特征。除x3外其他一般矩形特征数量计算方法类似，这里不做赘述。另外，我为认为title特征（即图5中的45°rotated reactangle）实用性一般，不再介绍，请查阅论文。
1.2 计算Haar特征值
看到这里，您应该明白了大量的Haar特征是如何产生的。当有了大量的Haar特征用于训练和检测时，接下来的问题是如何计算Haar特征值。
按照OpenCV代码，Haar特征值=白色区域内图像像素和 x 权重 - 黑色区域内图像像素和 x 权重：
对于x3和y3特征，weightwhite = 1且weightblack =2；对于point特征，weightwhite= 1且weightblack = 8；其余11种特征均为weightwhite = weightblack = 1。
这也就是其他文章中提到的所谓“白色区域像素和减去黑色区域像素和”，只不过是加权相减而已（在XML文件中，每一个Haar特征都被保存在2~3个形如
为什么要设置这种加权相减，而不是直接相减？请仔细观察图2中的特征，不难发现x3、y3、point特征黑白面积不相等，而其他特征黑白面积相等。设置权值就是为了抵消面积不等带来的影响，保证所有Haar特征的特征值在“灰度分布绝对均匀的图像”中为0（这种图像不存在，只是理论中的）。
了解了特征值如何计算之后，再来看看不同的特征值的含义是什么。我选取了MIT人脸库中2706个大小为20*20的人脸正样本图像，计算如图6位置的Haar特征值，结果如图7。
图6 Haar特征位置示意图（左边对应人眼区域，右边无具体意义）
图7 图6的2个Haar特征在MIT人脸样本中特征值分布图（左边特征结果为红色，右边蓝色）
可以看到，图6中2个不同Haar特征在同一组样本中具有不同的特征值分布，左边特征计算出的特征值基本都大于0（对样本的区分度大），而右边特征的特征值基本均匀分布于0两侧（对样本的区分度）。所以，正是由于样本中Haar特征值分布不均匀，导致了不同Haar特征分类效果不同。显而易见，对正负样本区分度越大的特征分类效果越好，即红色曲线对应图6中的的左边Haar特征分类效果好于右边Haar特征。
那么看到这里，应该理解了下面2个问题：
（1）在检测窗口通过平移+放大可以产生一系列Haar特征，这些特征由于位置和大小不同，分类效果也不同；
（2）通过计算Haar特征的特征值，可以有将图像矩阵映射为1维特征值，有效实现了降维。
1.3 Haar特征值归一化
本节属于实现细节，只关心原理的朋友可以跳过。
细心的朋友可能已经从图7中发现，仅仅一个12*18大小的Haar特征计算出的特征值变化范围从-2000~+6000，跨度非常大。这种跨度大的特性不利于量化评定特征值，所以需要进行“归一化”，压缩特征值范围。假设当前检测窗口中的图像为i(x,y)，当前检测窗口为w*h大小（例如图6中为20*20大小），OpenCV采用如下方式“归一化”：
（1）计算检测窗口中图像的灰度值和灰度值平方和：
（2）计算平均值：
（3）计算归一化因子：
（4）归一化特征值：
之后使用归一化后的特征值normValue与阈值对比（见下节）。
1.4 积分图
积分图是被各种文章写了无数次，考虑到文章完整性，我硬着头皮再写一遍。
之前我们分析到，仅仅在24*24大小的窗口，通过平移+缩放就可以产生数十万计大小不一、位置各异的Haar特征。在一个窗口内就有这么多Haar特征，而检测窗口是不断移动的，那么如何快速的计算这些Haar特征的特征值就是一个非常重要的问题了，所以才需要引入积分图。
对于图像中任何一点i(x,y)，定义其积分图为ii(x,y)为
其中i(x',y')为点(x',y')处的原始灰度图。这样就定义了一张类似于数学中“积分”的积分图。有了积分图ii(x,y)后，只需要做有限次操作就能获得任意位置的Haar特征值。
图8 积分图计算Haar矩形框示意图
如图8，如果要计算D区域内像素和，只需计算ii(x1,y1)-ii(x2,y2)-ii(x3,y3)+ii(x4,y4)，其中ii是积分图，(x1,y1)、(x2,y2)、(x3,y3)和(x4,y4)分别代表图8中的1、2、3、4点的图像坐标。显然可以通过此方法快速计算图像中任意位置和大小的Haar特征。此处Titled特征积分图不再讲解，请查阅论文。
-------------------------------------------
参考文献：
[1] Paul Viola and Michael J. Jones. Rapid Object Detection using aBoosted Cascade of Simple Features. IEEE CVPR, 2001.
[2] Rainer Lienhart and Jochen Maydt. An Extended Set ofHaar-likeFeatures for Rapid Object Detection. IEEE ICIP 2002, Vol. 1, pp. 900-903, Sep.2002.
-------------------------------------------
OK，第一章Haar特征分析就结束了，欢迎大家留言提问或者提出意见！
下一章，我会结合OpenCV中的XML，文件分析Adaboost级联分类器的结构，同时分析XML里面的internalNodes和leafValues等标签的具体含义。
2. 级联分类器结构与XML文件含义
前一篇文章分析了Haar特征，包括Haar特征生成、特征值计算和含义。这一篇则主要分析一下2个内容：
（1）OpenCV中的Adaboost级联分类器的结构，包括强分类器和弱分类器的形式；
（2）OpenCV自带的XML分类器中各项参数的含义，如internalNodes和leafValues标签里面的一大堆数字的意义。下面进入正题。
-------------------------------------------
众所周知，OpenCV中的Adaboost级联分类是树状结构，如图1，其中每一个stage都代表一级强分类器。当检测窗口通过所有的强分类器时才被认为是目标，否则拒绝。实际上，不仅强分类器是树状结构，强分类器中的每一个弱分类器也是树状结构。
图1 强分类器和弱分类器示意图
这篇文章将结合OpenCV-2.4.11中自带的haarcascade_frontalface_alt2.xml文件介绍整个级联分类器的结构。需要说明，自从2.4.11版本后所有存储得XML分类器都被替换成新式XML，所以本文对应介绍新式分类器结构。
2.1 XML的头部
在了解OpenCV分类器结构之前，先来看看存储分类器的XML文件中有什么。图2中注释了分类器XML文件头部信息，括号中的参数为opencv_traincascade.exe训练程序对应参数，即训练时设置了多少生成的XML文件对应值就是多少（如果不明白，可以参考我的前一篇文章）。
图2 分类器XML文件头部含义
2.2 弱分类器结构
之前看到有一部分文章将Haar特征和弱分类器的关系没有说清楚，甚至有些还把二者弄混了。其实Haar特征和弱分类器之间的关系很简单：
一个完整的弱分类器包含：Haar特征+ leftValue + rightValue + 弱分类器阈值(threshold)，这些元素共同构成了弱分类器，缺一不可。haarcascade_frontalface_alt2.xml的弱分类器深度为2，包含了2种形式，如图3。图3中的左边形式包含2个Haar特征、1个leftValue、2个rightValue和2个弱分类器阈（t1和t2）；左边形式包括2个Haar特征、2个leftValue、1个rightValue和2个弱分类器阈。
图3OpenCV树状弱分类器示意图
看图3应该明白了弱分类器的大致结构，接下来我们了解树状弱分类器是如何工作的。还是以图3左边的形式为例：
（1）计算第一个Haar特征的特征值haar1，与第一个弱分类器阈值t1对比，当haar1
（2）计算第二个Haar特征值haar2，与第二个弱分类器阈值t2对比，当haar2
即通过上述步骤计算弱分类器输出值，这与OpenCV的cascadedetect.hpp文件中的predictOrdered()函数代码对应（这里简单解释一下，在OpenCV中所有弱分类器的leftValue和rightValue都依次存储在一个一维数组中，代码中的leafOfs表示当前弱分类器中leftValue和rightValue在该数组中存储位置的偏移量，idx表示在偏移量leafOfs基础上的leftValue和rightValue值的索引，cascadeLeaves[leafOfs- idx]就是该弱分类器的输出）：
do
{
CascadeClassifier::Data::DTreeNode& node = cascadeNodes[root + idx];
double val =featureEvaluator(node.featureIdx);
idx = val < node.threshold ?node.left : node.right;
}
while( idx > 0 );
sum += cascadeLeaves[leafOfs -idx];
看到这里，你应该明白了弱分类器的工作方式，即通过计算出的Haar特征值与弱分类器阈值对比，从而选择最终输出leftValue和rightValue值中的哪一个。
那么第三个问题来了，这些Haar特征、leftValue、rightValue和弱分类器阈值t都是如何存储在xml文件中的？不妨来看haarcascade_frontalface_alt2.xml文件中的第一级的第三个弱分类器，如图4。图4中的弱分类器恰好是图3中左边类型，包含了
首先来看两个浮点数前的整数，即4和5。这两个整数用于标示所属本弱分类器Haar特征存储在
（
图4OpenCV弱分类器运行示意图
可以看到，每个弱分类器内部都是类似于这种树状的“串联”结构，所以我称其为“串联组成的的弱分类器”。（需要说明，本文为了介绍原理，选用了深度为2的分类器。而深度为1的分类器，如haarcascade_frontalface_alt.xml，则相比较简单，可以通过类比了解，不再赘述）
2.3 强分类器结构
在OpenCV中，强分类器是由多个弱分类器“并列”构成，即强分类器中的弱分类器是两两相互独立的。在检测目标时，每个弱分类器独立运行并输出cascadeLeaves [leafOfs- idx]值，然后把当前强分类器中每一个弱分类器的输出值相加，即：
sum += cascadeLeaves[leafOfs -idx];
图5OpenCV强分类器运行示意图
之后与本级强分类器的stageThreshold阈值对比，当且仅当结果sum>stageThreshold时，认为当前检测窗口通过了该级强分类器。当前检测窗口通过所有强分类器时，才被认为是一个检测目标。
可以看出，强分类器与弱分类器结构不同，是一种类似于“并联”的结构，我称其为“并联组成的强分类器”。
2.4 级联分类器
通过之前的介绍，到这应该可以理解OpenCV中：由弱分类器“并联”组成强分类器，而由强分类器“串联”组成级联分类器。那么还剩最后一个内容，那就是检测窗口大小固定（例如alt2是20*20像素）的级联分类器如何遍历图像，以便找到在图像中大小不同、位置不同的目标。
（1）为了找到图像中不同位置的目标，需要逐次移动检测窗口（随着检测窗口的移动，窗口中的Haar特征相应也随着窗口移动），这样就可以遍历到图像中的每一个位置；
（2）而为了检测到不同大小的目标，一般有两种做法：逐步缩小图像or逐步放大检测窗口。缩小图像就是把图像长宽同时按照一定比例（默认1.1 or 1.2）逐步缩小，然后检测；放大检测窗口是把检测窗口长宽按照一定比例逐步放大，这时位于检测窗口内的Haar特征也会对应放大，然后检测。一般来说，如果用软件实现算法，则放大检测窗口相比运行速度更快。
-------------------------------------------
OK，第二章分类器结构分析就结束了，欢迎大家留言提问或者提出意见！
下一章，我会介绍一个必须但又容易被忽略的问题——利用并查集合并检测结果窗口。
3. 利用并查集合并检测结果窗口
前一篇文章分析了OpenCV级联分类器结构，即“强分类器串联，弱分类器并联”，这一节我们来聊聊一些非常必要但是又容易人忽略的细节：如何利用并查集合并检测结果窗口。
-------------------------------------------
在上一篇文章中，我曾提到：级联分类器通过移动检测窗口寻找图像中不同位置的目标，同时通过放大检测窗口寻找图像中大小不同的目标，最终寻找到图像中不同位置、不同的大小的所有目标。那么必然存在这样的情况：一个被检测器检测为目标的窗口，其附近窗口也应该被检测到。例如在图像中的[x, y, w, h]窗口内检测到了人脸，那么[x-1, y-1, w+2, h+2]窗口也有极大的可能性被检测到，毕竟这2个窗口中的图像并没有明显差别（只是多了一个边而已）。
图1展示了使用haarcascade_frontalface_alt2.xml检测一副含有人脸图像的结果，左边为合并检测结果窗口之前的结果，右边为合并之后的结果。从图1左边可以看出，每个目标（人脸）附近都有一组重叠检测结果窗口，除此之外还有零散分布的误检结果窗口。看到这里你应该明白了有必要对重叠的检测结果窗口进行合并，同时剔除零散分布的错误检测窗口。
图1 检测结果合并窗口前后对比图
3.1 并查集(Union-Set)
在了解如何合并窗口前，先来了解一种数据结构——并查集。为了形象的说明并查集，首先来了解一个例子。江湖上存在各种各样的大侠，他们没什么正当职业，整天背着剑四处游荡，碰到其他大侠就大打出手。俗话说“双拳难敌四手”，这些大侠都会拉帮结派壮大实力。那么为了辨识每个大侠属于哪个帮派，就需要每个帮派都推举一个“老大”。这些大侠只需要知道自己和其他大侠的老大是不是同一个人，就能明白自己和对方是不是一个帮派，从而决定是否动手过招。
图2 江湖大侠关系图（箭头表示上一级）
如图2，现在武当派和明教分别推举了张三丰和张无忌作为老大。当帮派很大时组，每个大侠无法完整记住自己所在帮派的组织结构，那么他们只需要记住自己的上一级是谁，一级一级往上问就知道老大是谁了。某日，宋青书和殷梨亭在武当山门口遇到了，那么宋青书问宋远桥后得知自己的老大是张三丰，而殷梨亭的老大也是张三丰，那么他俩肯定是同门，必须不能动手了。而当宋青书遇到陈友谅时，一级一级向上询问后发现老大不是一个人，那就要拔剑分个你死我活。
在武林中，仅仅结成帮派是不够的，还需要通过其他关系组建帮派联盟扩大势力。既然杨不悔嫁给了殷梨亭，不妨直接设将明教老大张无忌的上级设置为武当派老大张三丰，这样就可以将明教和武当组成一个更大的联盟（如图2红色虚线，这里只关心数据的代表，忽略数据的内部结构）。例如，以后当宋青书和范右使相遇，一级一级往上问后发现老大都是张三丰，他俩就知道自己是一伙人了。但是，每次宋青书和范右使相遇，都像这样一级一级往上问速度很慢，而且次数多了上级大侠也会不耐烦。为了解决这个问题，需要压缩路径。当宋青书和范右使知道自己的老大是张三丰时，可以把自己的上司改为张三丰，这样就不必每次去问上级了，同时路径上的上级大侠也都把自己的上级改为老大张三丰。以范右使为例，压缩路径过程如下：
（1）范右使问张无忌：我的老大是谁；
（2）张无忌的上级就是老大张三丰，所以张无忌答复范右使：你的老大是张三丰；
（3）范右使知道自己的老大是张三丰，然后把自己的上级改为张三丰。
宋青书询问老大过程类似。当宋青书与范右使相遇后，问完老大后压缩路径结果如图3，下次他们遇到不用问上级就能就知道知道自己的老大是谁了。
图3 压缩路径后的江湖大侠关系图
并查集保持一组不相交的动态集合S={S1,S2,…,Sk}，每个动态集合Si通过一个代表ai来识别，代表是集合中的某个元素(ai∈Si)。在某些应用中，哪一个元素被选为代表是无所谓的，我们只关心在不修改动态集合的前提下分别寻找某一集合的代表2次获得的结果相同；在另外一些应用中，如何选择集合的代表可能存在预先说明的规则，如选择集合的最大or最小值作为代表。总之，在并查集中，不改变动态集合S则每个集合Si的代表ai不变。
不妨设x表示每个结点，p[x]表示x的父结点（即例中的上一级，如图2中p[宋远桥]==张三丰），rank[x]表示x节点的秩（即该节点最长路径中结点个数，如图2中最长路径为：张三丰-张无忌-杨左使-杨不悔，所以rank[张三丰]==4）。并查集伪代码如下：
MAKE-SET(x)
1 p[x] ← x
2 rank[x] ← 0
UNION(x, y)
1 LINK(FIND-SET(x),FIND-SET(y))
LINK(x, y)
1 if rank[x] < rank[y]
2 p[x] ← y
3 else
4 p[y] ← x
5 if rank[x]==rank[y]
6 rank[x] = rank[x] + 1
FIND-SET(x)
1 if x ≠ p[x]
2 p[x] ← FIND-SET(p[x])
3 return p[x]
其中，MAKE-SET函数用于在无序数据中初始化并查集数据结构，将每个结点父结点设为其本身；UNION函数通过调用LINK和FIND-SET实现带压缩路径的并查集合并；LINK函数通过秩进行并查集合并；FIND-SET是带压缩路径的寻找结点代表的函数。
还是以图2为例说明UNION函数。上次直接将明教老大张无忌的上级设置为了武当老大张三丰（如上文蓝色字体），导致了后续宋青书和范右使见面时查询老大路径太长。本着拒绝拖延症的原则，希望在合并明教和武当派时就提前压缩路径，不把问题留给宋青书和范右使。既然上面伪代码中的UNION是带压缩路径的合并结点函数，我们来看看调用UNION（殷梨亭，杨不悔）会发生什么：
（1）调用UNION（殷梨亭，杨不悔）。在调用LINK（FIND-SET（殷梨亭），FIND-SET（杨不悔））前，首先调用FIND-SET（殷梨亭）和FIND-SET（杨不悔）。
（2）调用FIND-SET（殷梨亭）和FIND-SET（杨不悔）。FIND-SET压缩路径函数通过递归把查询路径上每个人的上级变为本帮派的老大，如杨不悔的上级被设置为张无忌（由于杨左使和范右使的上级就是老大张无忌，所以其上级不变）；最后FIND-SET返回结点的老大，如FIND-SET（殷梨亭）返回张三丰，FIND-SET（杨不悔）返回张无忌。
（3）压缩路径后进行合并，即调用LINK（张三丰，张无忌）。由于rank[殷梨亭]==rank[杨不悔]==2秩相等，所以设置p[FIND-SET（杨不悔）]←FIND-SET（杨不悔），即设置p[张无忌]←张三丰，所以最终结果图为图4（注意：图3是查询时压缩路径，图4是合并时压缩路径）。
图4
如果还有不明白的地方，建议查阅《算法导论》中的第21章：《用于不相交的数据结构》。
3.2 利用并查集合并检测结果窗口
为了将并查集利用到合并窗口中，首先要定义窗口相似函数，即定义当前的2个窗口是不是“一伙人”。在OpenCV中，图像中的矩形窗口一般用Rect结构体表示，其包含x,y,width,height共4个成员变量，分别代表窗口的左上角点x坐标、y坐标、宽度和高度。下面代码定义了窗口相似函数SimilarRects::operator()，当2个窗口r1和r2位置很接近时返回TRUE，通过SimilarRects::operator()就可以将图1那些重叠的窗口合并在“一伙人”中。
class CV_EXPORTS SimilarRects
{
public:
SimilarRects(double _eps) : eps(_eps) {}
inline bool operator()(const Rect& r1,const Rect& r2) const
{
double delta = eps*(std::min(r1.width,r2.width) + std::min(r1.height, r2.height))*0.5;
return std::abs(r1.x - r2.x) <=delta &&
std::abs(r1.y - r2.y) <= delta&&
std::abs(r1.x + r1.width - r2.x -r2.width) <= delta &&
std::abs(r1.y + r1.height - r2.y -r2.height) <= delta;
}
double eps;
}
定义好窗口相似性函数后，就可以利用并查集合并窗口函数了，大致过程如下：
（1）首先利用MAKE-SET函数建立Rect对象的并查集初始结构；
（2）然后遍历整个并查集，用SimilarRects::operator()判断每2个窗口相似性，若相似则将这2个窗口合并为“一伙人”；
（3）运行完步骤2后应该出现几个相互间不相似的窗口“团伙”，当“团伙”中的窗口数量小于阈值minNeighbors时，丢弃该“团伙”（认为这是零散分布的误检）；
（4）之后剩下若干组由大量重叠窗口组成的大“团伙”，分别求每个“团伙”中的所有窗口位置的平均值作为最终检测结果。
下面的展示了OpenCV实现步骤1-2并查集归类窗口的代码。在之前算法描述中为了清晰简洁，使用递归实现了整个并查集；但在实际中递归需要保存现场并进行压栈，开销极大，所以OpenCV使用循环替代了递归。
// This function splits theinput sequence or set into one or more equivalence classes and
// returns the vector oflabels - 0-based class indexes for each element.
// predicate(a,b) returns trueif the two sequence elements certainly belong to the same class.
//
// The algorithm is describedin "Introduction to Algorithms"
// by Cormen, Leiserson andRivest, the chapter "Data structures for disjoint sets"
template
partition( constvector<_Tp>& _vec, vector
_EqPredicatepredicate=_EqPredicate())
{
int i, j, N = (int)_vec.size();
const _Tp* vec = &_vec[0];
const int PARENT=0;
const int RANK=1;
vector
int (*nodes)[2] =(int(*)[2])&_nodes[0];
// The first O(N) pass: create Nsingle-vertex trees // 即MAKE-SET，建立初始并查集结构
for(i = 0; i < N; i++)
{
nodes[i][PARENT]=-1;
nodes[i][RANK] = 0;
}
// The main O(N^2) pass: merge connectedcomponents // 即UNION，合并相似窗口
for( i = 0; i < N; i++ )
{
int root = i;
// find root
while( nodes[root][PARENT] >= 0 ) //即FIND-SET(root)，寻找root的老大并压缩路径
root = nodes[root][PARENT];
for( j = 0; j < N; j++ )
{
if( i == j || !predicate(vec[i],vec[j]))
continue;
int root2 = j;
while( nodes[root2][PARENT] >= 0) // 即FIND-SET(root2)，寻找root2的老大并压缩路径
root2 = nodes[root2][PARENT];
if( root2 != root ) // 即LINK(root,root2)
{
// unite both trees
int rank = nodes[root][RANK],rank2 = nodes[root2][RANK];
if( rank > rank2 )
nodes[root2][PARENT] =root;
else
{
nodes[root][PARENT] =root2;
nodes[root2][RANK] += rank== rank2;
root = root2;
}
assert( nodes[root][PARENT]< 0 );
int k = j, parent;
// compress the path from node2 to root
while( (parent =nodes[k][PARENT]) >= 0 )
{
nodes[k][PARENT] = root;
k = parent;
}
// compress the path from nodeto root
k = i;
while( (parent =nodes[k][PARENT]) >= 0 )
{
nodes[k][PARENT] = root;
k = parent;
}
}
}
}
// Final O(N) pass: enumerate classes
labels.resize(N);
int nclasses = 0;
for( i = 0; i < N; i++ )
{
int root = i;
while( nodes[root][PARENT] >= 0 )
root = nodes[root][PARENT];
// re-use the rank as the class label
if( nodes[root][RANK] >= 0 )
nodes[root][RANK] = ~nclasses++;
labels[i] = ~nodes[root][RANK];
}
return nclasses;
}
——————————————————————————————————————
参考文献：
[1] Thomas H.Cormen、CharlesE.Leiserson等.《算法导论》
[2] http://blog.csdn.net/dellaserss/article/details/7724401
——————————————————————————————————————
OK，第三章利用并查集进行窗口合并就结束了，欢迎留言提问或者提出意见！
下一章，我会逐步开始介绍opencv_traincasacde.exe的训练原理，可参考此文章： https://blog.csdn.net/playezio/article/details/80471078
4. 举例
第一次循环
当i=1时：
Found=0
设 m=5，每个样本的权重wk=0.2，且_y_1=_y_2=-1，_y_3=_y_4=y5=1；
Val__Vec_[_j_]=Feature[_i_][_j_](Val__Vec_存放特征1在所有样本上的特征值)
将Val__Vec_数组按特征值大小排序，使得：
Val__Vec_[1]≤Val__Vec_[2]≤Val__Vec_[3]≤Val__Vec_[4]≤Val__Vec_[5]
初始化：Left__Weight_=_Right___Weight_=_Left___Value_=_Right___Value_=0
当j=1时：
Left__Weight_=0.2；Right__Weight_=0.8；
Left__Value_=-0.2；Right__Value_=0.4；
α=Left__Type_=-1；β=Right__Type_=0.5；
Left__Error_=0；Right__Error_=0.65；
Eθ= Left__Error_+Right__Error_=0.65
Eθ≤E，则E= Eθ=0.65
第二次循环
可得出E=0，循环结束，得到该特征的最优弱分类器。
手机扫一扫
移动阅读更方便
你可能感兴趣的文章