1.1.1. 分类回归树分类回归树(Classification and regression trees,CART)是决策树的一种,它是基于吉尼(Gini)指标(并且是最简化的吉尼指标)的方法。
在OpenCV 下函数icvCreateCARTStageClassifier 实现层强分类器的构建,而它又调用了icvCreateCARTHaarClassifier 、icvInitCARTHaarClassifier 、icvEvalCARTHaarClassifier 实现了弱检测器的分类回归树的初始化、构建、赋值。
以下是简化了的算法描述:其中C 代表当前样本集,当前候选属性集用T 表示。
(1)新建一个根节点root(2)为root 分配类别(有人脸还是没有)(3)如果T 都属于同一类别(都是正样本或者反样本)或者C 中只剩下一个样本则返回root 为叶节点,为其分配属性。
(4)对任何一个T 中属性执行该属性上的划分,计算此划分的分类不纯度 (吉尼不纯度)(5)root 的测试属性是T 中最小GINI 系数的属性(6)划分C 得到C1 C2子集(7)对于节点C1重复(1)-(6)(8)对于节点C2重复(1)-(6)至于CART 的修剪、评估等算法就不给出了。
CART 的修剪的算法是分类错误算法。
如果想深入了解CART 树,则阅读上节给出的参考书目。
1.1.2. 弱分类器方法弱分类器的种类很多,但OpenCV 使用的是效果最好的决策树分类器。
关于分类器的介绍在第一章已经讨论过了,如果要有更深入理解可以看一些数据挖掘的图书后,再看看OpenCV 下的cvhaartraining.cpp 文件。
这里特别提下弱分类器的阈值的寻找方法。
阈值寻找算法定义在icvFindStumpThreshold_##suffix 函数里面,它是通过一个宏被定义的。
至于为什么通过这种方式定义,可以参考文献。
[i]函数icvFindStumpThreshold_##suffix输入参数介绍:wk 是第k 个样本的权重,yk 是第k 个样本是正样本还是反样本,如果是正样本则为+1,反样本则为-1,lerror 、rerror 是要求的最低误差,lerror=rerror=3.402823466e+38F(超大的数值),left 、right 是输出的误差。
threshold 是阈值,found 为是否找到阈值,初始是0。
For i=1:num(对每个排序后的样本)(1)∑==i k k wwl 1,∑+==num i k k w wr 1 (2)k i k k y wwyl *1∑== , k numi k k y w wyr *1∑+==(3)curleft=wyl/wl , curright=wyr/wr(4)如果curlerror+currerror<lerror+rerror则lerror=curlerrorrerror=curerrorthreshold 等于当前样本和前一个样本权重的均值left=curleftright=currightfound=1End返回found的值虽然lerror、rerror初始都是很大的值,但保证了程序一开始就可以进入(4),使它们改为当前的误差值(默认一定会找到阈值),不断循环下,它们就可以取得最小的误差值。
1.1.3.DAB的权重调整算法在OpenCV下函数icvBoostNextWeakClassifierDAB用于DAB的样本权重调整。
它实现了以最佳弱分类器进行一次样本权重的调整,并返回这次调整后的错误分类百分比。
流程如下:(1)初始化err=sumw=0;y向量是实际正反样本,f向量是样本在弱分类器下结果,都是1为真,-1为假。
w向量是样本的权重。
(2)调整部分(a)计算误检率。
对应了图中errm=Ew[1(y!=fm(x))]for i=0 to N-1如果y(i)不等于f(i)(表示未被正确分类),则err=err+w(i);如果相等,err不变;累加样本权重放到sumw中end;err=err/sumw;//计算了错误的比例,0<err<1/2err= - log(err/(1 - err));(b)更新权重for i=0 to N-1如果y(i)不等于f(i),则w(i)=w(i)*exp(err);否则w(i)不变累加新的权重放在sumw中end(c)归一化权重for i=0 to N-1w(i)=w(i)/sumw;end(3)返回err的值1.1.4.GAB的权重调整算法OpenCV下使用icvBoostNextWeakClassifierGAB函数调整GAB方法的权重,这个函数返回的alpha值恒为1,这点可以从输出分类器的算法(错误!未找到引用源。
节)中看到,它c项的。
是没有m(1)初始化sumw=0;(2)调整部分(a)更新权重for i=0 to N-1w(i)=w(i)*exp(-y(i)*f(i));//注意这里的f(i)数值不是-1和+1了。
累加权重放入sumw中end(b)权重归一for i=0 to N-1w(i)=w(i)/sumw;end(3)返回1.01.2. OpenCV下训练代码框架解读前几节使用了OpenCV进行了训练,而前几章人脸检测算法讲解比较分散,现在给出一个整体的算法流程,以弄清楚刚才的训练过程是怎么进行的。
首先要介绍下training_data的结构是CvHaarTrainingData,它是整个程序中最重要的数据。
先令N=posnum + negnum,即正反样本数量typedef struct CvHaarTrainingData{CvSize winsize; /* 图像大小*/int maxnum; /* 样本最大数量*/CvMat sum; /* 竖直积分图像,每个积分图像占据一行,N * (W+1)×(H+1)*/CvMat tilted; /* 旋转45度的积分图像,每个积分图像占据一行,N* (W+1)×(H+1) */CvMat normfactor; /* 一维向量, 1 * N*/CvMat cls; /* 所属类一维向量, 1 *N。
1表示有物体,0表示背景*/CvMat weights; /* 权重一维向量, 1 *N*/CvMat* valcache; /* 特征值*/CvMat* idxcache; /* 特征值标号*/} CvHaarTrainigData;函数cvCreateTreeCascadeClassifier的主体流程:(1)icvLoadTreeCascadeClassifier、icvFindDeepestLeaves、icvPrintTreeCascade读入已经训练好的数据,如果是第一次则不运行。
(2)icvCreateIntHaarFeatures//负责创建所有的Haar特征,并保存。
(3)icvCreateHaarTrainingData//给sum、tilted、normfactor、cls、weight分配内存空间(4)icvInitBackgroundReaders//初始化反样本图片的读入(具体实现又调用icvCreateBackgroundData、icvCreateBackgroundReader)(5)进入总循环//构造多层强分类器(A)再进入次循环循环//构造一层强分类器(a)icvSetLeafNode//从root找到路径到leaf(b)icvGetHaarTrainingDataFromVec//从.vec文件读入训练数据,经过计算得到的数据放到training_data下的sum、tilted、normfactor中(c)icvGetHaarTrainingDataFromBG//读入背景图片数据(d)判断是否达到required_leaf_fa_rate和nstages的要求,达到则程序结束。
否则继续(e)icvSetNumSamples//设置training_data中的行列都为总样本个数(f)根据equalweights初始化正反样本权重.如果它是真,则都设为1/num,否则posweight=1/2/poscount;negweight=1/2/negcount;(g)icvSetWeightsAndClasses//根据刚才的数据对training_data结构中的向量指针weights,cls分别赋值。
真样本在前反样本在后。
(h)icvPrecalculate//计算numprecalculated个haar特征(具体又通过icvGetTrainingDataCallback计算),保存到training_data->valcache下(i)icvCreateTreeCascadeNode//初始化,分配空间(j)icvCreateCARTStageClassifier//建立一层强分类器(k)icvNumSplits//返回这次强分类器一共使用的特征数量(l)开始聚类(clustering)操作,调用cvKMeans2函数等,这里最大不超过3类。
从2个类别开始进行聚类,每次聚类重新读入数据构造层CART树,找到最佳的类别数。
(B)次循环结束(6)开始寻找哪些节点应该被分裂,找到后添加新的节点。
并依次保存已经建好的节点,直到这棵树完全被存储。
(7)满足误差率或者层数则结束总循环,否则跳到(5)。
对照上面的步骤就可以很好的解释刚才训练过程。
需要注意的是,每一层训练时,正反样本数据都要重新载入,这个原因谈到过,是因为内存不够。
所以它每次处理后失去了原始的样本数据。
至于为什么最后程序无法停止,目前没有人给出解释。
1.3.对xml文件的解读在OpenCV进行长时间的训练后,我们能够得到一个.xml文件,这种文件是专门用于存储数据的,并且是跨平台的。
我们只是研究物体检测产生的.xml文件,只对它的结果进行解读,如果想深入了解.xml的编程可以参考相关书籍。
下面列出haarcascade_frontalface_alt2.xml文件中的一些内容:(/**/中文字是注释)<size>20 20</size>/*这行告诉我们这个分类器是使用20*20的图像训练出来的,因此他可以检测任何大于20*20的人脸图像。
*/<!-- stage 0-->/*代表第0层强分类器*/-<trees><!-- tree 0-->/*代表此层分类器下第0棵二叉树*/<!-- root node-->/*根节点*/-<feature>-<rects>/*矩形*/<_>2 7 16 4 -1.</_>/*前面四个数据表示矩形左上角坐标和矩形的长、宽,最后一个表示比重*/<_>2 9 16 2 2.</_>/*这个矩形比重是正的,可以画图发现是Haar_y2特征*/</rects><tilted>0</tilted>/*这个标志是不是旋转的特征,0表示不是*/</feature><threshold>4.3272329494357109e-003</threshold>/*表示这棵树的阈值*/<left_val>0.0383819006383419</left_val>/*小于阈值去左树枝*/<right_node>1</right_node>/*大于等于阈值取右树枝,这个节点有分裂了,继续往下找*/之后就可以找到这个节点,结构和刚才分析的是一样的。