OpenCV AdaBoost + Haar目標檢測技術內幕（下）

04-17

上文介紹了檢測部分，本文接著介紹訓練部分。

白裳丶：OpenCV AdaBoost + Haar目標檢測技術內幕（上）?

zhuanlan.zhihu.com

4 AdaBoost背景介紹

在了解AdaBoost之前，先介紹弱學習和強學習的概念：

弱學習：識別錯誤率小於1/2，即準確率僅比隨機猜測略高的學習演算法
強學習：識別準確率很高的學習演算法

縮進顯然，無論對於任何分類問題，弱學習都比強學習容易獲得的多。簡單的說：AdaBoost就是一種把簡單的弱學習拼裝成強學習的方法。事實上，在OpenCV圖像檢測模塊訓練程序中實現了4種AdaBoost演算法：

DAB(Discrete AdaBoost)
RAB(Real AdaBoost)
LB(LogitBoost)
GAB(Gentle AdaBoost)

其中DAB即是AdaBoost.M1（AdaBoost.M2是DAB的多分類版本），GAB是opencv_traincascade.exe的默認AdaBoost方法。

4.1 DAB介紹

DAB是最常見的AdaBoost演算法，其演算法原理如上所示。DAB演算法的核心是不斷的尋找當前權重下的最優分類器，然後加大被最優分類器誤判樣本的權重並重新訓練，直到得到強分類器。說到這裡不得不佩服前輩大神的奇思妙想，在實際應用中幾乎不可能直接找到有效的強分類器，而獲得弱分類器則相對簡單很多，DAB演算法只需要通過迭代就能組合弱分類器最終得到強分類器。

一起來看一個DAB例子。假設空間中分布著N=10個點，其中5個藍色的正(+)樣本點和5個紅色的負(-)樣本點，如圖1。開始前初始化權重數組，每個樣本權重為 $w_{i} = 1/N = 1/10$ 。

圖4-1 初始情況

在這裡限定弱分類器只能是水平or豎直的直線。那麼找到一個最優弱分類器 $f_{1}$ 將樣本分為2類，其中圓圈中3個樣本表示被 $f_{1}$ 錯誤分類，此時計算 $f_{1}$ 分類誤差 $e_{1}$ 和 $f_{1}$ 的權重 $c_{1}$ ，然後更新所有的樣本權重 $w_{i}$ 。

圖4-2 M=1時分類情況（圖中e_m就是e_1)

可以看到，當M=1循環結束時，直觀上被 $f_{1}$ 誤分類的樣本權重變大（被 $f_{1}$ 錯誤分類的3個+變大），下次訓練時則更加「重視」這幾個樣本。注意，更新權重後不要忘記權重歸一化（權重具體值沒有寫出來，請讀者自行推導）。

圖4-3 M=2時分類情況

還是類似，加大被 $f_{2}$ 誤分類的樣本權重（這次是三個-）。

圖4-3 M=3時分類情況

最後通過權重 $c_{1}$ 、 $c_{2}$ 、 $c_{3}$ 將弱分類器組成一個強分類器F：

圖4-4 最終分類器

可以看出循環M次則訓練M個弱分類器，並由這M個分類器最終組成強分類器。

最後給出論文中DAB的原始版本：

4.2 GAB介紹

首先定義加權平方和誤差WSE（即weighted square error）如下，其中 $w_{i}$ 表示權重， $f(x_{i})$ 表示弱分類器對樣本 $x_{i}$ 的輸出值， $y_{i}$ 表示樣本 $x_{i}$ 的標籤：

慣例，列出GAB演算法的官方描述：

仔細觀察可以發現，GAB和DAB有2處不同，解釋如下：

DAB和GAB使用的分類器權重誤差不一樣，GAB是「weighted least-squares」，也就是上面的WSE。應該比較好理解。
DAB和GAB的弱分類器對樣本 $x_{i}$ 的 $f(x_{i})$ 不一樣。DAB的 $f(x_{i})$ 不是+1就是-1；而GAB的 $f(x_{i})$ 輸出的是一種類似於概率的值。

為了說明，不妨設有x1~x5共5個樣本，某次訓練中選取了某個Feature來度量樣本，對應的Feature value為h1~h5。然後選擇某個閾值 $t$ 將樣本分為左右兩個部分。對於DAB：

對於DAB左邊輸出 $f(x_{i})=-1$ ，右邊 $f(x_{j})=+1$
而GAB左邊輸出 $f(x_{i})=P_{left}$ ，右邊 $f(x_{j})=P_{right}$ ，表示「加權離散度」。

獲得 $f(x_{i})$ 之後通過調整 $t$ 的大小，使WSE最小，即可完成該次訓練。其中最終的 $t$ 就是之前的弱分類器閾值。具體GAB如何應用在訓練中將在後續章節中講解。

從DAB到GAB，實現了從「是否」到「概率」的跨越。所以，千萬不要以「對=正 and 錯=負」這種非常絕對的概念去理解GAB，而要以概率論去理解，畢竟GAB是gentle的！

5 AdaBoost訓練演算法（重點哦）

本節分析AdaBoost訓練演算法，包括每個stage如何收集樣本；如何訓練每個弱分類器；如何界定強分類器的閾值等內容。

5.1 Precision vs Recall

對於所有的監督學習(supervised learning)，都需要一組正樣本(positive samples)和負樣本(negative samples)。以訓練人臉檢測器為例，人臉圖片即正樣本，所有的非人臉區域即為負樣本。對於一組positive samples和negative samples，經過檢測器後，會有以下4種情況：

positive sample會產生：

TP(true positive)，即positive sample被檢測器判定為目標
FN(false negative)，即positive samples被檢測器判斷為非目標，相當於檢測器「漏掉」了目標

negative sample會產生：

TN(true negative)，即negative sample被檢測器判定為非目標
FP(false positive)，即negative sample被檢測器判定為目標，相當於產生了「誤檢」 or 「虛警」

也就是說，在實際中不僅關心是否檢測錯誤，更關心的是把「什麼」檢測成了「什麼」。

圖5-1 Precision vs Recall

其中論文中常見的兩個指標：

$precision = tp / (tp + fp)$

$recall = tp / (tp + fn)$

一般在實際應用中，希望precision和recall都很高。還是以人臉檢測為例，不妨假設某張圖中有10個人臉。

若檢測器只發現了1個人臉，此時 $precision=1$ 雖然很高，但是 $recall=0.1$ 非常低
若檢測器發現了50個人臉（假設包含了10個真人臉），此時 $recall=1$ 很高，但是 $precision=10/50=0.2$ 很低

所以只有precision和recall都比較高時，討論檢測器的參數才有意義。但是現實情況中魚和熊掌不可兼得，很難做到precision和recall都很高，所以會繪製precision-recall曲線評估檢測器。

5.2 hitRate與falseAlarm

圖5-2 opencv_traincascade.exe工具命令

而在Adaboost訓練過程中，我們更關心的是minHitRate和maxFalseAlarmRate參數，如圖5-2紅框。在OpenCV的boost.cpp中CvCascadeBoost::isErrDesired()函數，對每一個stage有如下定義：

float hitRate = ((float) numPosTrue) / ((float) numPos);float falseAlarm = ((float) numFalse) / ((float) numNeg);

換個表達方式：

$hitRate = tp / (tp + fn) = recall$

$falseAlarm = fp / (tn + fp)$

這裡hitRate稱為「命中率」，度量檢測器對正樣本的通過能力，顯然越接近1越好；而falseAlarm稱為「虛警率」，度量檢測器對負樣本的通過能力，顯然越接近0越好。

圖5-3 adaboost級聯結構

考慮到Haar+Adaboost的stage間「串聯」形式，如圖5-3，stageNum個stage串聯後，已知每個stage的hitRate(i)和falseAlarm(i)，整個檢測器最終的hitRate和falseAlarmRate為：

$hitRate = hitRate_{1} imes hitRate_{2} imes ..... imes hitRate_{n} = prod_{1}^{n}hitRate_{i}$

$falseAlarmRate = falseAlarm_{1} imes ...... imes falseAlarm_{n} = prod_{1}^{n}falseAlarm_{i}$

而∏表示連乘符號。那麼：

為了讓檢測器最終的 $hitRate$ 接近1，每一個stage的 $hitRate_{i}$ 必須很大，即每一個stage的正樣本通過率必須非常高。
同理，為了讓檢測器最終的 $falseAlarmRate$ 接近0，每一個stage的 $falseAlarm_{i}$ 必須很小，即每一個stage的負樣本虛警率必須比較低。

從圖2中可以看到默認 $minHitRate = 0.995$ ，默認 $maxFalseAlarmRate = 0.5$ 。假設 $stageNum = 20$ 時，最終檢測器有：

$hitRate ≈ x^{stageNum} = x^{20} = 0.904610...$

$falseAlarmRate ≈ x^{stageNum} = 0.5^{20} = 0.00000095...$

然後換一組參數， $minHitRate = 0.9$ ， $maxFalseAlarmRate = 0.6$ 時，最終的檢測器 $hitRate$ 竟然掉到了0.12，Amazing！

$hitRate ≈ 0.9^{20} = 0.12157...$

$falseAlarmRate ≈ 0.6^{20}= 0.000036...$

由此看出每一個stage的 $minHitRate$ 必須非常高(>=0.995)！而 $maxFalseAlarmRate$ 則相對「溫和」一些。

總結一下：

由於串聯的級數量很多，minHitRate必須非常接近1，才能保證最終檢測器有較好的recall；
falseAlarmRate相當於對檢測器的precision作了約束；

5.3 樣本收集過程

首先分析每一個stage訓練時如何收集樣本，事實上每一個stage訓練使用的正負樣本都不同。

正樣本patches收集過程：opencv_trancascade.exe使用的正樣本是一個vec文件，即由opencv_createsamples.exe把一組固定 $w imes h$ 大小的圖片轉換為二進位vec文件（只是讀取圖片並轉化為灰度圖，並按照二進位格式保存下來而已，不做任何改變）。由於經過如此處理的正樣本就是固定 $w imes h$ 大小的patches，所以正樣本可以直接進入訓練。
負樣本patches收集過程：而使用的負樣本就不一樣了，是一個包含任意大小圖片路徑的txt文件。在尋找負樣本的過程中，程序會以圖像金字塔(pyramid)+滑動窗口的模式(sliding-window)去遍歷整個負樣本集，以獲取 $w imes h$ 大小的負樣本patches。
對1和2步驟來中這些正負樣本的patches進行分類：獲取到這些固定w x h大小的正/負樣本patches後，利用已經訓練好的stage分類這些patches，並且從正樣本中收集numPos個TP patches；從負樣本中收集numNeg個FP patches（假設樣本是足夠的）。之後利用TP作為正樣本，FP作為負樣本訓練下一個stage。

那麼對於 $stage_{0}$ ，直接收集numPos個來自正樣本的patches + numNeg個來自負樣本的patches進行訓練；對於 $stage_{i}(i >0)$ ，則利用已經訓練好的 $stage_{0}$ 到 $stage_{i-1}$ 分類這些patches，分別從正樣本patches中收集numPos個TP，從負樣本patches中收集numNeg個FP（numPos和numNeg參數是在opencv_traincascade中預先設置的）。

圖5-4 每個Stage訓練前收集樣本示意圖

每一個stage都要進行上述收集+分類過程，所以實際中每一個stage所使用的訓練樣本也都不一樣！

在OpenCV的cascadeclassifier.cpp中，有如下fillPassedSamples()函數負責填充訓練樣本（修改此函數可以實現下文提到的保存TP和FP）。

int CvCascadeClassifier::fillPassedSamples( int first, int count, bool isPositive, double minimumAcceptanceRatio, int64& consumed ){ int getcount = 0; Mat img(cascadeParams.winSize, CV_8UC1); for( int i = first; i < first + count; i++ ) { for( ; ; ) { if( consumed != 0 && ((double)getcount+1)/(double)(int64)consumed <= minimumAcceptanceRatio ) return getcount; bool isGetImg = isPositive ? imgReader.getPos( img ) : imgReader.getNeg( img ); //讀取樣本 if( !isGetImg ) return getcount; //如果不能讀取樣本（出錯or樣本消耗光了），返回 consumed++; //只要讀取到了樣本，不管判斷結果如何，消耗量consumed增加1 //當參數isPositive = true時，填充正樣本隊列，此時選擇TP進入隊列 //當參數isPositive = false時，填充負樣本隊列，此時選擇FP進入隊列 featureEvaluator->setImage( img, isPositive ? 1 : 0, i ); //將樣本img塞入訓練隊列中 if( predict( i ) == 1 ) //根據isPositive判斷是否是TP/FP, 是則break進入下一個；反之繼續循環，並覆蓋上面setImage的樣本 { getcount++; //真正添加進訓練隊列的數量 printf("%s current samples: %d ", isPositive ? "POS":"NEG", getcount); break; } } } return getcount;}

接下來看看第20行的predict()函數：

int CvCascadeClassifier::predict( int sampleIdx ){ CV_DbgAssert( sampleIdx < numPos + numNeg ); for (vector< Ptr<CvCascadeBoost> >::iterator it = stageClassifiers.begin(); it != stageClassifiers.end(); it++ ) { if ( (*it)->predict( sampleIdx ) == 0.f ) return 0; } return 1;}

再進入第7行的(*it)->predict()函數：

float CvCascadeBoost::predict( int sampleIdx, bool returnSum = false ) const{ CV_Assert( weak ); double sum = 0; CvSeqReader reader; cvStartReadSeq( weak, &reader ); cvSetSeqReaderPos( &reader, 0 ); for( int i = 0; i < weak->total; i++ ) { CvBoostTree* wtree; CV_READ_SEQ_ELEM( wtree, reader ); sum += ((CvCascadeBoostTree*)wtree)->predict(sampleIdx)->value; //stage內的弱分類器wtree輸出值求和sum } if( !returnSum ) //默認進行sum和stageThreshold比較 //當sum<stageThreshold，輸出0，否決當前樣本；sum>stageThreshold，輸出1，通過 sum = sum < threshold - CV_THRESHOLD_EPS ? 0.0 : 1.0; return (float)sum; //若returnSum==true則不與stageThreshold比較，直接返回弱分類器輸出之和。下文用到}

看到這就很清晰了，默認returnSum為false時每個stage內部弱分類器wtree的輸出值加起來和stageTheshold比較，當樣本通過時輸出1，不通過輸出0（參考文系列文章三）。那麼對於positive samples，輸出1即是TP；對於negative samples，輸出1即是FP。至此代碼與上述內容對應，over!

5.3 分類器的訓練過程

分析到到此，讀者已經了解如何獲得了用於訓練的正負樣本。

獲取樣本後，接下來分析如何運用這些正負樣本訓練每一個stage分類器。為了方便理解，以下章節都是以maxDepth=1為例分析訓練過程，其他深度請自行分析代碼。

在收集到numPos個TP和numNeg個FP後，就可以訓分類器了，過程如下：

首先計算所有Haar特徵對這numPos+numNeg個樣本patches的特徵值，排序後分別保存在的vector中，如圖5-5

圖5-5 分類器訓練過程示意圖

按照如下方式遍歷每個存儲特徵值的vector

至此，已經有很多弱分類器了。但是哪一個弱分類器最好呢？所以要挑選最優弱分類器放進stage中。

通過前面2步後每一個弱分類器都有一個基於Best split threshold的GAB WSE ERROR，那麼顯然選擇ERROR最小的那個弱分類器作為最優弱分類器放進當前訓練的stage中。

依照GAB方法更新當前訓練的stage中每個樣本的權重

對numPos+numNeg個權重按照如下公式更新權重（注意更新後需要對權重進行歸一化）。

計算當前的強分類器閾值stageThreshold

使用當前的stage中已經訓練好的弱分類器去檢測樣本中的每一TP，計算弱分類器輸出值之和保存在eval中（如果不明白，請查閱第三節「並聯的弱分類器」）。
對eval升序排序
利用minHitRate參數估計一個比例thresholdIdx，以eval[thresholdIdx]作為stage閾值stageThreshold，顯然TP越多估計的stageThreshold越準確。

上述1-3過程由boost.cpp中的CvCascadeBoost::isErrDesired()函數實現，關鍵代碼如下：

int numPos = 0;for( int i = 0; i < sCount; i++ ) //遍歷樣本 if( ((CvCascadeBoostTrainData*)data)->featureEvaluator->getCls( i ) == 1.0F ) //if current sample is TP eval[numPos++] = predict( i, true ); //predict加入true參數後，會返回當前stage中弱分類器輸出之和（如上文predict介紹）icvSortFlt( &eval[0], numPos, 0 ); //升序排序int thresholdIdx = (int)((1.0F - minHitRate) * numPos); //按照minHitRate估計一個比例作為indexthreshold = eval[ thresholdIdx ]; //取該index的值作為stageThreshold

至此，stage中的弱分類器+stageThreshold等參數都是完整的

重複之前stage訓練步驟（黑體字），直到滿足下列任意一個條件後停止並輸出當前的stage

stage中弱分類器的數量 >= maxWeakCount參數
利用當前的stage去檢測FP獲得當前stage的falseAlarmRate，當falseAlarmRate < maxFalseAlarmRate停止

同樣是boost.cpp中的CvCascadeBoost::isErrDesired()函數：

int numNeg = 0;for( int i = 0; i < sCount; i++ ){ if( ((CvCascadeBoostTrainData*)data)->featureEvaluator->getCls( i ) == 0.0F ) { numNeg++; if( predict( i ) ) //predict==1也就是falseAlarm，虛警，即俗稱的誤報 numFalse++; }}float falseAlarm = ((float) numFalse) / ((float) numNeg);

一直訓練，直到滿足 $falseAlarm < maxFalseAlarm$ 後停止當前stage訓練。

然後重複訓練每一個stage，直到滿足下面任意一個條件：

stage數量 >= numStages
所有stage總的falseAlarmRate < pow(maxFalseAlarmRate,numStages)

5.5 一個OpenCV訓練的小例子

作者選用了約12000張人臉樣本，使用opencv_traincascade.exe程序，設置numPos=numNeg=10000，w=h=24，進行一次簡單的訓練。如下圖紅線所示，在 $stage_{0}$ 的時候，程序直接從正負樣本中各抽取10000張24x24大小的子圖片進行訓練，獲得了一個包含3個決策樹的強分類器。

在 $stage_{1}$ 的時，掃描了10008張正樣本後獲得了10000個TP（當前實際hitRate=10000/10008）；掃描了很多負樣本窗口後獲得了10000個FP（比例為acceptanceRatio=0.243908，即是當前實際falseAlarmRate）。訓練完成後獲得一個包含5個決策樹的強分類器。

可以看到，在一般情況下，隨著訓練的進行，acceptancesRatio會越來越低，即直觀上看每一級收集的FP會越來越像正樣本；那麼為了區分TP與FP，每一個stage包含的決策樹也會逐漸增多。

註：上圖中每一級的前幾個分類器HR=1，FA=1，這是由訓練程序中的數值計算細節導致的，有興趣的朋友可以自己去翻代碼......

5.6 訓練過程總結

其實回顧一下，整個分類器的訓練過程可以分為以下幾個步驟：

尋找TP和FP作為訓練樣本
計算每個Haar特徵在當前權重下的Best split threshold+leftvalue+rightvalue，組成了一個個弱分類器
通過WSE尋找最優的弱分類器
更新權重
按照minHitRate估計stageThreshold
重複上述1-5步驟，直到falseAlarmRate到達要求，或弱分類器數量足夠。停止循環，輸出stage。
進入下一個stage訓練

OpenCV Cascade Boosting介紹就結束了。

歡迎關注本專欄其他文章。