266      阿裏雲  技術社區[雲棲]

經典的HaarTraining算法

1. Haar與OpenCV

特征檢測專題

2. 網絡資源

https://answers.opencv.org/question/27970/cascadeclassifierload-from-memory/

Adaboost+Haar+Opencv博客

12年的文章，感覺收集的很全了。全部看完也差不多了解了

OpenCV源碼中Haar訓練及特征提取的代碼說明

上麵幾篇源碼分析放到一個頁麵裏了

3. 源碼分析

還沒有看到有全局調用的解釋，即call graph。call graph都需要 profiling(動態)或編譯（static analysis）。

好像clang++就可以輸出call graph。另外codeViz+graphViz是很好的選擇。有空了畫一個。現在先手動吧。。。

3.1 opencv haartraining 分析三：icvCreateCARTStageClassifier （cvhaartraining.cpp）

函數icvCreateCARTStageClassifier負責訓練一個強分類器 

trainer = cvBoostStartTraining( &data->cls, weakTrainVals, &data->weights,

                 sampleIdx, boosttype );//data->cls 一個1*m的矩陣，元素為0.0或1.0，分別代表背景和有行人,本程序sampleIdx = NULL

cart = (CvCARTClassifier*) cvCreateCARTClassifier( data->valcache,
                        flags,
                        weakTrainVals, 0, 0, 0, trimmedIdx,
                        &(data->weights),
                        (CvClassifierTrainParams*) &trainParams );//開始構建cart樹弱分類器

        classifier = (CvCARTHaarClassifier*) icvCreateCARTHaarClassifier( numsplits ); //初始化

        icvInitCARTHaarClassifier( classifier, cart, haarFeatures );//把caar和haarFeature數據放到classifier中

if( falsealarm > maxfalsealarm )
    {
        stage = NULL;
    }
    else
    {
        stage = (CvStageHaarClassifier*) icvCreateStageHaarClassifier( seq->total,
                                                                       threshold );
        cvCvtSeqToArray( seq, (CvArr*) stage->classifier );
    }

3.2  opencv haartraining 分析一：cvCreateTreeCascadeClassifier（cvhaartraining.cpp）

haar_features = icvCreateIntHaarFeatures( winsize, mode, symmetric );//這個是計算haar特征的數目以及相關參數(計算每個特征的計算公式)，

//CvTreeCascadeNode包含CvStageHaarClassifier* stage;也就是說找最後一個stage作為最深的葉leaf;
CV_CALL( leaves = icvFindDeepestLeaves( tcc ) );

CV_CALL( icvPrintTreeCascade( tcc->root ) );
//根據模式和對稱性以及winsize獲得haar特征，每個特征由最多三個矩形矩形加減形成，
//這裏包含了所有的允許特征，允許特征是可能特征的一部分，過濾掉的是麵積比較小的特征
haar_features = icvCreateIntHaarFeatures( winsize, mode, symmetric );

printf( "Number of features used : %d\n", haar_features->count );
//分配用於訓練的緩衝區，包括正負樣本的矩形積分圖和傾斜積分圖

typedef struct CvTHaarFeature

{

    char desc[CV_HAAR_FEATURE_DESC_MAX];

    int  tilted;

    struct

    {

        CvRect r;

        float weight;

    } rect[CV_HAAR_FEATURE_MAX];

} CvTHaarFeature;

typedef struct CvFastHaarFeature

{

    int tilted;

    struct

    {

        int p0, p1, p2, p3;

        float weight;

    } rect[CV_HAAR_FEATURE_MAX];

} CvFastHaarFeature;

typedef struct CvIntHaarFeatures

{

    CvSize winsize;

    int count;

    CvTHaarFeature* feature;

    CvFastHaarFeature* fastfeature;

} CvIntHaarFeatures;

其中CvTHaarFeature和CvFastHaarFeature的區別在於：CvTHaarFeature是標示特征覆蓋的窗口的坐標（Cvrect r）,CvFastHaarFeature是將特征覆蓋的窗口區域拉直，然後計算cvEvalFastHaarFeature.

CV_INLINE float cvEvalFastHaarFeature( const CvFastHaarFeature* feature,
                                       const sum_type* sum, const sum_type* tilted )
{
    const sum_type* img = feature->tilted ? tilted : sum;//此處img是判斷是否是旋轉後的。如果不是，那麼這個是已經計算了每個位置的像素積分和的。

// CvMat normfactor;
// CvMat cls;
// CvMat weights;
training_data = icvCreateHaarTrainingData( winsize, npos + nneg );
sprintf( stage_name, "%s/", dirname );
suffix = stage_name + strlen( stage_name );
//獲得背景信息，包括讀取背景信息裏背景文件的文件名信息並索引該文件，

//讀取正樣本，並計算通過所有的前麵的stage的正采樣數量，這樣可以計算出檢測率
//調用函數情況
//icvGetHaarTrainingDataFromVec內部調用icvGetHaarTrainingData
//icvGetHaarTrainingData，從規定的回調函數裏icvGetHaarTraininDataFromVecCallback獲得數據，
//並通過前麵訓練出的分類器過濾掉少量正采樣,然後計算積分圖，
//積分圖存放在training_data結構中
poscount = icvGetHaarTrainingDataFromVec( training_data, 0, npos,
(CvIntHaarClassifier*) tcc, vecfilename, &consumed );

//讀負采樣，並返回虛警率
//從文件中將負采樣讀出，並用前麵的訓練出的stage進行過濾獲得若幹被錯誤劃分為正采樣的負采樣，如果得到的數量達不到nneg
//則會重複提取這些負樣本，以獲得nneg個負采樣，所以如果當被錯誤劃分為正采樣的負采樣在當前的stage後為0，則會出現死循環
//解決方法可以通過reader的round值判斷。
//這種情況應該是訓練收斂，因為虛警率為0，符合條件if( leaf_fa_rate <= required_leaf_fa_rate )，可以考慮退出訓練
nneg = (int) (neg_ratio * poscount);
//icvGetHaarTrainingDataFromBG內部調用
//icvGetBackgroundImage獲得數據並計算積分圖，將其放在training_data結構分配的內存，位置是在poscount開始nneg個數量
//training_data分配了npos + nneg個積分圖內存以及權值
negcount = icvGetHaarTrainingDataFromBG( training_data, poscount, nneg,
(CvIntHaarClassifier*) tcc, &false_alarm );
printf( "NEG: %d %g\n", negcount, false_alarm );

icvSetNumSamples( training_data, poscount + negcount );
posweight = (equalweights) ? 1.0F / (poscount + negcount) : (0.5F/poscount);
negweight = (equalweights) ? 1.0F / (poscount + negcount) : (0.5F/negcount);
//這裏將正樣本設置為1，負樣本設置為0，在後麵將用於分辨樣本類型，統計檢測率和虛警率
//這裏也設置加權值
icvSetWeightsAndClasses( training_data,
poscount, posweight, 1.0F, negcount, negweight, 0.0F );

//預先計算每個樣本(包括正負樣本的前麵numprecalculated特征)
//內部調用cvGetSortedIndices將所有樣本的每一個特征按其特征值升序排序，idx和特征值分別放在training_data
//的 *data->valcache和*data->idxcache中;
icvPrecalculate( training_data, haar_features, numprecalculated );

/訓練由多個弱分類器級連的強分類器
single_cluster->stage =
(CvStageHaarClassifier*) icvCreateCARTStageClassifier

printf( "Cluster: %d\n", cluster );
last_pos = negcount;
//將分類好的正樣本根據cluster與負樣本組合，則訓練出k個node,
//與前麵不一樣的是正樣本放後麵負樣本放前麵
//重新計算加權
icvSetWeightsAndClasses( training_data,
poscount, posweight, 1.0F, negcount, negweight, 0.0F );

3.3 另一篇不錯的獨立分析

1.結構:
程序的總體結構是一棵多叉樹,每個節點多少個叉由初始設定的maxtreesplits決定

樹節點結構:
typedef struct CvTreeCascadeNode
{
CvStageHaarClassifier* stage; // 指向該節點stage強分類器的指針

struct CvTreeCascadeNode* next; // 指向同層下一個節點的指針
struct CvTreeCascadeNode* child; // 指向子節點的指針
struct CvTreeCascadeNode* parent; // 指向父節點的指針

struct CvTreeCascadeNode* next_same_level;//最後一層葉節點之間的連接
struct CvTreeCascadeNode* child_eval; //用於連接最終分類的葉節點和根節點
int idx; //表示該節點是第幾個節點
int leaf; //從來沒有用到過的參數
} CvTreeCascadeNode;

這裏需要說明的是child_eval這個指針，雖說人臉檢測是一個單分類問題，程序中的maxtreesplits的設置值為0，沒有分叉，但是樹本身 是解決多分類問題的，它有多個葉節點，也就有多個最終的分類結果。但是我們使用的時候，雖然是一個多分類的樹，也可能我們隻需要判斷是或者不是某一類。於 是我們就用root_eval和child_eval把這個分類上的節點索引出來，更方便地使用樹結構。當然，這一點在本程序中是沒有體現的。

分類器結構：
每個樹節點中都包含了一個CvStageHaarClassifier強分類器，而每個CvStageHaarClassifier包含了多個 CvIntHaarClassifier弱分類器。當CvIntHaarClassifier被使用的時候，被轉化為 CvCARTHaarClassifier，也就是分類樹與衰減數分類器作為一個弱分類器。

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;

CvCARTHaarClassifier結構中包含了弱分類器的左值右值閾值等數組，在我們的程序中CART隻選用了一個特征進行分類，即退化成了stump。這裏的數組裏麵就隻存有一個元了

那麼這裏為什麼要使用一個如此複雜的結構呢。大體來說有兩個好處：
1、 方便弱分類器之間的切換，當我們不選用CART而是其他的弱分類器結構的時候，就可以調用CvIntHaarClassifier時轉換成其他的指針
2、 這樣方便了Haar訓練的過程和Boost過程的銜接。

特征的結構：


2.OpenCV的HaarTraining程序中一種常用的編程方法：
在這個程序中，函數指針是一種很常用的手法。函數指針的轉換使讀程序的人更難把握程序的脈絡，在這裏舉一個最極端的例子，來說明程序中這種手法的應用。

我們在cvBoost.cpp文件中的cvCreateMTStumpClassifier函數（這是一個生成多閾值(Multi-threshold)stump分類器的函數）下看到了一個這樣的調用：
findStumpThreshold_16s[stumperror]（……….）
這裏對應的stumperror值是2

在cvboost.cpp中我們找到了一個這樣的數組
CvFindThresholdFunc findStumpThreshold_16s[4] = {
icvFindStumpThreshold_misc_16s,
icvFindStumpThreshold_gini_16s,
icvFindStumpThreshold_entropy_16s,
icvFindStumpThreshold_sq_16s
};
這個數組的類型是一個類型定義過的函數指針typedef int (*CvFindThresholdFunc)（…..）

因此這個數組中的四項就是四個指針，我們在cvCreateMTStumpClassifier中調用的也就是其中的第三項icvFindStumpThreshold_entropy_16s。

然後我們發現這個函數指針沒有直接的顯性的實現。那麼問題出在哪裏呢？
它是通過宏實現的：
程序中定義了一個這樣的宏：
#define ICV_DEF_FIND_STUMP_THRESHOLD_SQ( suffix, type )
ICV_DEF_FIND_STUMP_THRESHOLD( sq_##suffix, type,


curlerror = wyyl + curleft * curleft * wl - 2.0F * curleft * wyl;
currerror = (*sumwyy) - wyyl + curright * curright * wr - 2.0F * curright * wyr;
)

和一個這樣的宏：
#define ICV_DEF_FIND_STUMP_THRESHOLD( suffix, type, error )
CV_BOOST_IMPL int icvFindStumpThreshold_##suffix(…..)
{
……..
}

這兩個宏中，後者是函數的主體部分，而函數的定義通過前者完成。即：
ICV_DEF_FIND_STUMP_THRESHOLD_ENTROPY( 16s, short )，這樣的形式完成。這相當於給前者的宏傳遞了兩個參數，前者的宏將第一個參數轉換成sq_16s後和第二個參數一起傳到後者的宏。（##是把前後兩個 string連接到一起，string是可變的兩，在這裏suffix就放入了16s和sq_結合成了sq_16s）
後者的宏接收到參數以後就進行了函數的定義：
CV_BOOST_IMPL int icvFindStumpThreshold_sq_16s

這樣icvFindStumpThreshold_sq_16s就被定義了。這樣做的好處是，12個非常相似的函數可以通過兩個宏和12個宏的調用來實現，而不需要直接定義12個函數。

3.訓練結果中數據的含義：
- <feature>
- <rects>
<_>6 4 12 9 -1.</_>
//矩陣。前四個數值是矩陣四個點的位置，最後一個數值是矩陣像素和的權值
<_>6 7 12 3 3.</_>
//矩陣。前四個數值是矩陣四個點的位置，最後一個是像素和的權值，這樣兩個矩陣就形成了一個Haar特征
</rects>
<tilted>0</tilted> //是否是傾斜的Haar特征
</feature>
<threshold>-0.0315119996666908</threshold> //閾值
<left_val>2.0875380039215088</left_val> //小於閾值時取左值
<right_val>-2.2172100543975830</right_val> //大於閾值時取右值


4. 訓練過程中使用的算法
這裏主要講弱分類器算法

•矩形特征值：Value[i][j], 1≤i≤n代表所有的Haar特征，1≤j≤m代表所有的樣本
•FAULT = (curlerror + currerror)表示當前分類器的錯誤率的最小值，初始設置：curlerror currerror= 1000000000000000000000000000000000000000000000000(反正給個暴力大的數值就對了)

3.4 又一篇不錯的獨立分析

一、樹狀分類器
1、構造一棵決策樹CvCARTClassifier，樹狀分類器
//層次關係：CvCARTClassifier CvCARTNode CvStumpClassifier
//CvCARTClassifier由count個CvCARTNode組成，每個CvCARTNode有一個CvStumpClassifier，

CvClassifier* cvCreateCARTClassifier( CvMat* trainData,//所有樣本的所有特征值
int flags, //標識矩陣按行或列組織
CvMat* trainClasses,
CvMat* typeMask,
CvMat* missedMeasurementsMask,
CvMat* compIdx,
CvMat* sampleIdx,//選擇部分樣本時的樣本號
CvMat* weights,
CvClassifierTrainParams* trainParams )

#define CV_CLASSIFIER_FIELDS() \
int flags; \
float(*eval)( struct CvClassifier*, CvMat* ); \
void (*tune)( struct CvClassifier*, CvMat*, int flags, CvMat*, CvMat*, CvMat*, \
CvMat*, CvMat* ); \
int (*save)( struct CvClassifier*, const char* file_name ); \
void (*release)( struct CvClassifier** );

typedef struct CvClassifier
{
CV_CLASSIFIER_FIELDS()
} CvClassifier;

typedef struct CvCARTNode
{
CvMat* sampleIdx;
CvStumpClassifier* stump;
int parent; //父節點索引號
int leftflag; //1：left節點時;0：right節點
float errdrop;//剩餘的誤差
} CvCARTNode;

//一個弱分類器，所用特征的索引、閾值及哪側為正樣本
typedef struct CvStumpClassifier
{
CV_CLASSIFIER_FIELDS()
int compidx; //對應特征的索引

float lerror;
float rerror;

float threshold; //該特征閾值
float left; //均值或左側正樣本比例，left＝p(y=1)/(p(y=1)+p(y=-1)),對分類器若left為正樣本則為1，反之為0
float right;
} CvStumpClassifier;

typedef struct CvCARTClassifier
{
CV_CLASSIFIER_FIELDS()
int count;
int* compidx;
float* threshold;
int* left;//當前節點的左子節點為葉節點時，存葉節點序號的負值（從0開始）；非葉節點，存該節點序號
int* right;//當前節點的右子節點為葉節點時，存葉節點序號的負值（從0開始）；非葉節點，存該節點序號

float* val;//存葉節點的stump->left或stump->right，值為正樣本比例p(y=1)/(p(y=1)+p(y=-1))
} CvCARTClassifier;

typedef struct CvCARTTrainParams
{
CV_CLASSIFIER_TRAIN_PARAM_FIELDS()

int count;//節點數
CvClassifierTrainParams* stumpTrainParams;
CvClassifierConstructor stumpConstructor;

//定義了函數指針變量，變量名為splitIdx，將樣本按第compidx個特征的threshold分為left和right
void (*splitIdx)( int compidx, float threshold,
CvMat* idx, CvMat** left, CvMat** right,
void* userdata );
void* userdata;
} CvCARTTrainParams;
2、用樹狀分類器進行檢測
//sample隻是一個樣本，判斷該樣本在CvCARTClassifier樹中的那個葉節點上
//返回該樣本所在葉節點的正樣本比例p(y=1)/(p(y=1)+p(y=-1))
float cvEvalCARTClassifier( CvClassifier* classifier, CvMat* sample )

//根據樹狀分類器判斷樣本在樹上的位置，即在哪個葉節點上。返回葉節點序號
float cvEvalCARTClassifierIdx( CvClassifier* classifier, CvMat* sample )

二、boost
1、boost過程流程，將各種類型歸為一個函數cvBoostStartTraining/cvBoostNextWeakClassifier,
通過參數區分不同類型的boost。都是在最優弱分類器已知，各樣本對該分類器估計值已計算存入weakEvalVals
typedef struct CvBoostTrainer
{
CvBoostType type;
int count;
int* idx;//要麼null,要麼存樣本索引號
float* F;//存logiBoost的F
} CvBoostTrainer;

調用順序：cvBoostStartTraining ———> startTraining[type] ———> icvBoostStartTraining等
//定義函數cvBoostStartTraining
CvBoostTrainer* cvBoostStartTraining( ...,CvBoostType type )
{
return startTraining[type]( trainClasses, weakTrainVals, weights, sampleIdx, type );
}
//定義函數指針類型的數組變量startTraining[4]
CvBoostStartTraining startTraining[4] = {
icvBoostStartTraining,
icvBoostStartTraining,
icvBoostStartTrainingLB,
icvBoostStartTraining
};
//定義函數指針類型CvBoostStartTraining
typedef CvBoostTrainer* (*CvBoostStartTraining)( CvMat* trainClasses,
CvMat* weakTrainVals,
CvMat* weights,
CvMat* sampleIdx,
CvBoostType type );

調用順序：cvBoostNextWeakClassifier———> nextWeakClassifier[trainer->type]———> icvBoostNextWeakClassifierLB等
//定義函數cvBoostNextWeakClassifier
float cvBoostNextWeakClassifier( ..., CvBoostTrainer* trainer )
{
return nextWeakClassifier[trainer->type]( weakEvalVals, trainClasses,weakTrainVals, weights, trainer);
}
//定義函數指針類型的數組變量nextWeakClassifier[4]
CvBoostNextWeakClassifier nextWeakClassifier[4] = {
icvBoostNextWeakClassifierDAB,
icvBoostNextWeakClassifierRAB,
icvBoostNextWeakClassifierLB,
icvBoostNextWeakClassifierGAB
};
//定義函數指針類型CvBoostNextWeakClassifier
typedef float (*CvBoostNextWeakClassifier)( CvMat* weakEvalVals,
CvMat* trainClasses,
CvMat* weakTrainVals,
CvMat* weights,
CvBoostTrainer* data );

2、具體的startTraining和NextWeakClassifier
//y*=2y-1,類別標簽由{0，1}變為{-1，1}，並將它填入weakTrainVals
//返回CvBoostTrainer，其中F = NULL;
CvBoostTrainer* icvBoostStartTraining( CvMat* trainClasses,//類別標簽{0，1}，
CvMat* weakTrainVals,//類別標簽{-1，1}，
CvMat* weights,
CvMat* sampleIdx,//要麼null,要麼存樣本索引號
CvBoostType type )

//更新權重，特征的響應函數值weakEvalVals已知,即分類器已確定，分類結果在weakEvalVals
float icvBoostNextWeakClassifierDAB( CvMat* weakEvalVals,//響應函數值{1，-1}
CvMat* trainClasses,//類別標簽{0，1}，
CvMat* weakTrainVals,//沒使用，應該是{1，-1}
CvMat* weights, //將被更新
CvBoostTrainer* trainer )//用於確定要被更新權重的樣本

//更新Real AdaBoost權重，特征的響應函數值weakEvalVals已知,即分類器已確定
float icvBoostNextWeakClassifierRAB( CvMat* weakEvalVals,//響應函數值,應該是測對率=（測對數/總數）
CvMat* trainClasses,//類別標簽{0，1}，
CvMat* weakTrainVals,//沒使用
CvMat* weights, //被更新，w=w*[exp（-1/2*log(evaldata/1-evaldata))]
CvBoostTrainer* trainer )//用於確定要被更新的樣本

//樣本數，權重，類別標簽，響應函數值F，z值，樣本索引
//由F計算LogitBoost的w和z，z返回到traindata
void icvResponsesAndWeightsLB( int num, uchar* wdata, int wstep,
uchar* ydata, int ystep, //類別標簽
uchar* fdata, int fstep, //響應函數值F
uchar* traindata, int trainstep,//用於存z
int* indices ) //樣本索引

//初始F=0;得p=1/2，計算w、z
CvBoostTrainer* icvBoostStartTrainingLB( CvMat* trainClasses,//類別標簽{0，1}，
CvMat* weakTrainVals, //存Z值
CvMat* weights,
CvMat* sampleIdx,//要麼null,要麼存樣本索引號
CvBoostType type )

//已知f,先算F=F+f,再算p=1/(1+exp(-F)),再算z,w
float icvBoostNextWeakClassifierLB( CvMat* weakEvalVals,//f,是對z的回歸
CvMat* trainClasses,//類別標簽{0，1}
CvMat* weakTrainVals,//存Z值
CvMat* weights,
CvBoostTrainer* trainer )

//Gentle AdaBoost，已知f,算w=w*exp(-yf)
CV_BOOST_IMPL
float icvBoostNextWeakClassifierGAB( CvMat* weakEvalVals,//f=p(y=1|x)-p(y=-1|x)
CvMat* trainClasses,//類別標簽{0，1}
CvMat* weakTrainVals,//沒使用
CvMat* weights,
CvBoostTrainer* trainer )

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;

最後更新：2017-04-03 05:40:06

  上一篇： 8.27 super hero

  下一篇： 深入分析Android (build/core/*.mk腳本)