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

01-28

很多使用過OpenCV的小夥伴都見過如下代碼，這段極其簡單的代碼，能夠檢測出圖像中人臉，非常神奇。這其實就是一個Adaboost級聯分類器的經典實現；但是當你希望深入代碼學習原理時，估計會被代碼複雜度嚇到。

希望這篇文章能幫助你了解背後的所有原理，不再迷茫。

#include <opencv2/opencv.hpp>n#define CV_COLOR_RED cv::Scalar(0, 0, 255)nint main(int argc, char** argv)n{ntcv::CascadeClassifier faceDetector("haarcascade_frontalface_alt2.xml");ntcv::Mat image = cv::imread("Your image path.");nntstd::vector<cv::Rect> objects;ntfaceDetector.detectMultiScale(image, objects);nntfor (int i = 0; i < objects.size(); i++)nt{nttcv::rectangle(image, objects[i], CV_COLOR_RED);nt}ntcv::imshow("result", image);ntcv::waitKey(0);nntreturn 0;n}n

文章很長，建議按需閱讀。

1 Haar特徵

在OpenCV介面中，實現了Haar/LBP/HOG等多種特徵，本文以Haar特徵為例介紹。

1.1 Haar特徵的生成

Haar特徵最先由Paul Viola等人提出，後經過Rainer Lienhart等擴展引入45°傾斜特徵，成為現在OpenCV所使用的的樣子。圖1-1展示了目前OpenCV（2.4.11版本）所使用的共計14種Haar特徵，包括5種Basic特徵、3種Core特徵和6種Titled(即45°旋轉)特徵。

圖1-1 OpenCV中使用的的Haar特徵

在實際中，Haar特徵可以在檢測窗口中由放大+平移產生一系列子特徵，但是白：黑區域面積比始終保持不變。

如圖1-2，以x3特徵為例，在放大+平移過程中白：黑：白面積比始終是1:1:1。首先在紅框所示的檢測窗口中生成大小為3個像素的最小x3特徵；之後分別沿著x和y平移產生了在檢測窗口中不同位置的大量最小3像素x3特徵；然後把最小x3特徵分別沿著x和y放大，再平移，又產生了一系列大一點x3特徵；然後繼續放大+平移，重複此過程，直到放大後的x3和檢測窗口一樣大。這樣x3就產生了完整的x3系列特徵。

圖1-2 x3特徵平移+放大產生一系列子特徵示意圖

那麼這些通過放大+平移的獲得的子特徵到底總共有多少個？Rainer Lienhart在他的論文中給出了完美的解釋：假設檢測窗口大小為W*H，矩形特徵大小為w*h，X和Y為表示矩形特徵在水平和垂直方向的能放大的最大比例係數：

圖1-3 特徵數量計算示意圖

則如圖1-3，在檢測窗口Window中，一般矩形特徵(upright rectangle)的數量為：

簡單解釋一下，上述公式可以理解為：

特徵框豎直放大1倍，即無放大，豎直方向有(H-h+1)個特徵
特徵框豎直放大2倍，豎直方向有(H-2h+1)個特徵
特徵框豎直放大3倍，豎直方向有(H-3h+1)個特徵
如此到豎直放大Y=floor(H/h)倍，豎直方向有1個特徵，即(H-Y*h+1)

那麼豎直方向總共有(H-h+1)+(H-2h+1)+(H-3h+1)+......+(H-Y*h+1)=Y[H+1-h(1+Y)/2]個特徵。考慮到水平和豎直方向縮放是獨立的，所以能得到上述公式。對應於之前的x3特徵，當x3特徵在24*24大小的檢測窗口中時（此時W=H=24，w=3，h=1，X=8，Y=24），一共能產生27600個子特徵，除x3外其他一般矩形特徵數量計算方法類似。

1.2 如何計算Haar特徵值

看到這裡，該明白了大量的Haar特徵是如何產生的。當有了大量的Haar特徵用於訓練和檢測時，接下來的問題是如何計算Haar特徵值。按照OpenCV代碼，Haar特徵值=整個Haar區域內像素和×權重 + 黑色區域內像素和×權重：

對於圖2中的x3和y3特徵， $weight_{all}$ = 1， $weight_{black}$ = -3；
對於point特徵， $weight_{all}$ = 1， $weight_{black}$ = -9；
其餘11種特徵均為 $weight_{all}$ =1， $weight_{black}$ = -2。

這也就是其他文章中提到的所謂「白色區域像素和減去黑色區域像素和」，只不過是加權相加而已。例如：

對於x2特徵：(黑 + 白) * 1+黑 * (-2) = 白 - 黑；
對於Point特徵：(黑 + 白) * 1 + 黑 * (-9) = 白 - 8 * 黑。

為什麼要設置這種加權相減，而不是直接相減？請仔細觀察圖2中的特徵，不難發現x3、y3、point特徵黑白面積不相等，而其他特徵黑白面積相等。設置權值就是為了抵消面積不等帶來的影響，保證所有Haar特徵的特徵值在灰度分布絕對均勻的圖中為0。

了解了特徵值如何計算之後，再來看看不同的特徵值的含義是什麼。我選取了MIT人臉庫中2706個大小為20*20的人臉正樣本圖像，計算如圖1-4位置的Haar特徵值，結果如圖1-5。

圖1-4 Haar特徵位置示意圖

圖1-5 圖4的2個Haar特徵在MIT人臉樣本中特徵值分布圖（左邊特徵結果為紅色，右邊藍色）

可以看到，圖1-4中2個不同Haar特徵在同一組樣本中具有不同的特徵值分布，左邊特徵計算出的特徵值基本都大於0，而右邊特徵的特徵值基本均勻分布於0兩側（分布越均勻對樣本的區分度越小）。所以，正是由於樣本中Haar特徵值分布不同，導致了不同Haar特徵分類效果不同。顯而易見，對樣本區分度越大的特徵分類效果越好，即紅色曲線對應圖1-4中的的左邊Haar特徵分類效果好於右邊Haar特徵。那麼看到這裡，應該理解了下面2個問題：

在檢測窗口通過平移+放大可以產生一系列Haar特徵，這些特徵由於位置和大小不同，分類效果也各異；
通過計算Haar特徵的特徵值，可以有將圖像矩陣映射為1維特徵值，有效實現了降維

1.3 Haar特徵如何保存？

對應的，在OpenCV XML文件中，每一個Haar特徵都被保存在2~3個形如：

<x y width height weight>

的標籤中，其中x和y代表Haar矩形左上角坐標（以檢測窗口左上角為原點），width和height代表矩形的寬和高，而weight則對應了上面說的權重值，例如圖4中的左邊x2類型的Haar特徵應該為<4 2 12 8 1.0>（整個Haar，權重1）和<4 2 12 4 -2.0>（黑色區域，權重-2）。

1.4 Haar特徵值標準化

從上文圖1-5中發現，僅僅一個12*18大小的Haar特徵計算出的特徵值變化範圍從-2000~+6000，跨度非常大。這種跨度大的特性不利於量化評定特徵值，所以需要進行「標準化」，壓縮特徵值範圍。假設當前檢測窗口中的圖像為i(x,y)，當前檢測窗口為w*h大小（例如圖6中為20*20大小），OpenCV採用如下方式「標準化」：

計算檢測窗口中間部分(w-2)*(h-2)的圖像的灰度值和灰度值平方和：

計算平均值：

計算標準化因子：

標準化特徵值：

具體代碼在cascadedetect.cpp中的HaarEvaluator::setImage()函數中可以看到，關鍵部分如下：

normrect = Rect(1, 1, origWinSize.width-2, origWinSize.height-2);nCV_SUM_PTRS( p[0], p[1], p[2], p[3], sdata, normrect, sumStep );nCV_SUM_PTRS( pq[0], pq[1], pq[2], pq[3], sqdata, normrect, sqsumStep );n

與代碼對應的，如圖中藍色為檢測窗口，紅色為標準化過程中使用到的像素。

圖1-6

為什麼一定要在norm的時候縮進去一個邊呢？作者猜測這可能是為了避免邊緣像素不穩定，干擾標準化因子的計算。其實如何標準化並不重要，重要的是檢測和訓練時的方法一定要一致，否則可能會由於標準化不同帶來的誤差導致模型無法工作！

1.5 積分圖

以OpenCV自帶的人臉分類器haarcascade_frontalface_alt2.xml為例，其中存儲了超過1000個大小和位置都不相同的Haar特徵（XML文件解釋見下節）。在運算中，伴隨著檢測窗口的移動，如何快速計算Haar特徵值就成了一個很重要的問題。在設計Haar+AdaBoost演算法時，Paul Viola等人就提出積分圖。

對於灰度圖像中任意一點image(x,y)，OpenCV定義其積分圖為sum(x,y)為：

$sum(X,Y)=sum_{x<X,y<Y}^{ }{image(x-1,y-1)}$

其中第0行和第0列為0：

$sum(X,0)=0$ 且 $sum(0,Y)=0$

其中image(x,y)為點(x,y)處的原始灰度圖。這樣就定義了一張類似於數學中「積分」的積分圖。如圖1-7，如果要計算D區域內灰度和，只需計算

$sum(D) = sum(x4,y4) - sum(x3,y3) -sum(x2,y2) + sum(x1,y1)$

其中(x1,y1)、(x2,y2)、(x3,y3)和(x4,y4)依次代表圖1中image的1 2 3 4點的圖像坐標。需要說明，在計算D區域灰度和時sum(x1,y1)深藍色區域被減去了2次，最後需要補上。顯然可以通過此方法快速計算圖像中任意位置和大小區域的灰度和，即通過積分圖只需要做有限次操作就能獲得任意位置的Haar特徵值

圖1-7 積分圖計算Haar矩形框示意圖

1.6 旋轉積分圖

為了提高檢測精度，Rainer Lienhart等人首先提出了45°旋轉積分圖，如圖1-8。旋轉積分圖用於快速計算圖1中的titled_x2和titled_y2等共6種旋轉Haar特徵。

圖1-8 45°旋轉積分圖

與一般積分圖類似，OpenCV中45°旋轉積分圖同樣採用了「擴邊」方式（即旋轉積分圖比原灰度圖多1行和1列，其中第1行和第1列元素為0），對應的計算公式為：

$titled(X,Y)=sum_{y<Y,|x-X+1|<=Y-y+1}^{}{image(x-1,y-1)}$

其中第一行第一列為0：

$titled(X,0)=0$ 且 $titled(0,Y)=0$

有了旋轉積分圖如何計算任意位置和大小的45°傾斜長方形區域的灰度和呢？

設有如圖9紅色方框大小的灰度圖image，其計算出來的45°旋轉灰度圖為titled（第0行和第0列為0），虛線代表image中cv::Rect為<3 1 2 3>區域。顯然虛線區域的灰度和為：

$titled(2,6) - titled(1,4) - titled(6,3) + titled(1,4)$

應該不難理解。

圖1-9

在實際中，如果使用旋轉特徵，則需要多計算一張積分圖。但是旋轉特徵的效果往往不理想，得不償失，不建議使用。

PS：45°旋轉旋轉積分圖還有另外一種實現方式，但是OpenCV由於數據存儲方式限定，不那樣做。

圖1-10

2 級聯分類器結構

了解Haar特徵之後，接下來分析級聯分類器結構，主要包括以下2個內容：

OpenCV中的Adaboost級聯分類器的結構，包括強分類器和弱分類器的形式；
OpenCV自帶的XML分類器中各項參數的含義，如internalNodes和leafValues標籤裡面的一大堆數字的意義。

OpenCV中的Adaboost級聯分類是樹狀結構，如圖2-1，其中每一個stage都代表一級強分類器。當檢測窗口通過所有的強分類器時才被認為是目標，否則拒絕。實際上，不僅強分類器是樹狀結構，強分類器中的每一個弱分類器也是樹狀結構。

圖2-1 強分類器和弱分類器示意圖（此圖有誤，應是stage1，stage2，...，stageN）

這篇文章將結合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-2 分類器XML文件頭部含義

其中<features>標籤存儲了所有的Haar特性，在之前1.3節有講解。

2.2 弱分類器結構

之前看到有一部分文章將Haar特徵和弱分類器的關係沒有說清楚，甚至有些還把二者弄混了。其實Haar特徵和弱分類器之間的關係很簡單：

一個完整的弱分類器包括：

若干個Haar特徵 + 和Haar特徵數量相等的弱分類器閾值
若干個leftValue
若干個rightValue

這些元素共同構成了弱分類器，缺一不可。haarcascade_frontalface_alt2.xml的弱分類器Depth=2，包含了2種形式，如圖2-3：

左邊形式包含2個Haar特徵、1個leftValue、2個rightValue和2個弱分類器閾（t1和t2）
右邊形式包括2個Haar特徵、2個leftValue、1個rightValue和2個弱分類器閾值

圖2-3 Depth=2的樹狀弱分類器示意圖

看圖2-3應該明白了弱分類器的大致結構，接下來我們了解樹狀弱分類器是如何工作的。還是以圖3左邊的形式為例：

計算第一個Haar特徵的特徵值haar1，與第一個弱分類器閾值t1對比，當haar1<t1時，進入步驟2；當haar1>t1時，該弱分類器輸出rightValue2並結束。
計算第二個Haar特徵值haar2，與第二個弱分類器閾值t2對比，當haar2<t2時輸出leftValue；當haar2>t2時輸出rightValue1。

即通過上述步驟計算弱分類器輸出值，這與OpenCV的cascadedetect.hpp文件中的predictOrdered()函數代碼對應（這裡簡單解釋一下，在OpenCV中所有弱分類器的leftValue和rightValue都依次存儲在一個一維數組中，代碼中的leafOfs表示當前弱分類器中leftValue和rightValue在該數組中存儲位置的偏移量，idx表示在偏移量leafOfs基礎上的leftValue和rightValue值的索引，cascadeLeaves[leafOfs - idx]就是該弱分類器的輸出）：

don{n CascadeClassifier::Data::DTreeNode& node = cascadeNodes[root + idx];n double val = featureEvaluator(node.featureIdx);n idx = val < node.threshold ? node.left : node.right;n}nwhile( idx > 0 );nsum += cascadeLeaves[leafOfs - idx];n

即弱分類器的工作方式：通過計算出的Haar特徵值與弱分類器閾值對比，從而選擇最終輸出leftValue和rightValue值中的哪一個。

那麼這些Haar特徵、leftValue、rightValue和弱分類器閾值t都是如何存儲在xml文件中的？不妨來看haarcascade_frontalface_alt2.xml文件中的第一級的第三個弱分類器，如圖2-4。圖2-4中的弱分類器恰好是圖3中左邊類型，包含了<internalNodes>和<leafValues>兩個標籤。其中<leafValues>標籤中的3個浮點數由左向右依次是rightValue2、leftValue和rightValue1；而<internalNodes>中有6個整數和2個浮點數，其中2個浮點數依次分別是弱分類器閾值t1和t2，剩下的6個整數容我慢慢分解。

首先來看兩個浮點數前的整數，即4和5。這兩個整數用於標示所屬本弱分類器Haar特徵存儲在<features>標籤中的位置。比如數值4表示該弱分類器的haar1特徵存儲在xml文件下面<features>標籤中第4個位置，即為：

而<internalNodes>的其他4個整數1、0和-1、-2則用於控制弱分類器樹的形狀。在運行時，OpenCV會把1賦值給當前的node.left，並把0賦值給node.right（請注意do-while代碼中的條件，只有idx<=0時才停止循環，參考圖3應該可以理解這4個整數的含義）。如此，OpenCV通過這些巧妙的數值和結構，控制了整個分類器的運行。可以看到，每個弱分類器內部都是類似於這種樹狀的「串聯」結構，所以我稱其為「串聯組成的的弱分類器」。

圖2-4 OpenCV弱分類器運行示意圖

而Depth=1（如haarcascade_frontalface_alt.xml）類型的弱分類器，結構更加簡單且運行方式對比可知，不在贅述。

圖2-5 Depth=1的stump弱分類器示意圖

2.3 強分類器結構

在OpenCV中，強分類器是由多個弱分類器「並列」構成，即強分類器中的弱分類器是兩兩相互獨立的。在檢測目標時，每個弱分類器獨立運行並輸出cascadeLeaves[leafOfs - idx]值，然後把當前強分類器中每一個弱分類器的輸出值相加，即：

sum += cascadeLeaves[leafOfs - idx];n

圖2-6 OpenCV強分類器運行示意圖

之後與本級強分類器的stageThreshold閾值對比，當且僅當結果sum>stageThreshold時，認為當前檢測窗口通過了該級強分類器。當前檢測窗口通過所有強分類器時，才被認為是一個檢測目標。可以看出，強分類器與弱分類器結構不同，是一種類似於「並聯」的結構，我稱其為「並聯組成的強分類器」。

2.4 如何搜索目標？

還有一個問題：檢測窗口大小固定（例如alt2是20*20像素）的級聯分類器如何遍歷圖像，以便找到在圖像中大小不同、位置不同的目標？

解決方法如下：

為了找到圖像中不同位置的目標，需要逐次移動檢測窗口（窗口中的Haar特徵相應也隨著移動），這樣就可以遍歷到圖像中的每一個位置；而為了檢測到不同大小的目標，一般有兩種做法：逐步縮小圖像or逐步放大檢測窗口，這樣即可遍歷到圖像中不同大小的目標
縮小圖像就是把圖像按照一定比例逐步縮小然後滑動窗口檢測，如圖2-7；放大檢測窗口是把檢測窗口長寬按照一定比例逐步放大，這時位於檢測窗口內的Haar特徵也會對應放大，然後檢測。一般來說，如果用用硬體實現則縮小圖像更快，用軟體實現演算法則放大檢測窗口更快。

圖2-7 經典的Pyramid+Sliding-window檢測（借用一張大佬的照片）

新版c++函數CascadeClassifier::detectMultiScale()只實現了縮小圖像檢測；舊版的c函數cvHaarDetectObject()同時實現了縮小圖像和放大窗口兩種檢測方式，當函數參數flag為CV_HAAR_SCALE_IMAGE時是縮小圖像檢測，默認flag=0時放檢測大窗口檢測。

#define CV_HAAR_SCALE_IMAGE 2n

3 對檢測結果NMS

考慮這樣的情況：一個被檢測為目標的窗口，其附近窗口也應該被檢測到。例如在圖像中的[x, y, w, h]窗口內檢測到了人臉，那麼[x-1, y-1, w+2, h+2]窗口也有極大的可能性被檢測到，畢竟這2個窗口中的圖像並沒有明顯差別（只是多了一個邊而已）。

圖3-1展示了使用haarcascade_frontalface_alt2.xml檢測一副含有人臉圖像的結果，左邊為合併檢測結果窗口之前的結果，右邊為合併之後的結果。從圖1左邊可以看出，每個目標（人臉）附近都有一組重疊檢測結果窗口，除此之外還有零散分布的誤檢結果窗口。看到這裡你應該明白了有必要對重疊的檢測結果窗口進行合併，同時剔除零散分布的錯誤檢測窗口。今天寫Faster RCNN突然想到，如果非要給這玩意起個高大上的名字，應該叫做NMS(non-maximum suppression)。

圖3-1 檢測結果合併窗口前後對比圖

3-1 並查集(Union-Set)

在了解如何合併窗口前，先來了解一種數據結構——並查集。為了形象的說明並查集，首先來了解一個例子。江湖上存在各種各樣的大俠，他們沒什麼正當職業，整天背著劍四處遊盪，碰到其他大俠就大打出手。俗話說「雙拳難敵四手」，這些大俠都會拉幫結派壯大實力。那麼為了辨識每個大俠屬於哪個幫派，就需要每個幫派都推舉一個「老大」。這些大俠只需要知道自己和其他大俠的老大是不是同一個人，就能明白自己和對方是不是一個幫派，從而決定是否動手過招。

圖3-2 江湖大俠關係圖（箭頭表示上一級）

如圖3-2，現在武當和明教分別推舉張三丰和張無忌為老大。當幫派很大時，每個大俠記不住幫派所有人，那麼他們只需要記住自己的上一級是誰，一級一級往上問就知道老大是誰了。某日，宋青書和殷梨亭在武當山門遇到，那麼宋青書問宋遠橋後得知自己的老大是張三丰，而殷梨亭的老大也是張三丰，那麼他倆是同門。反之宋青書遇到陳友諒時，一級一級向上詢問後發現老大不是一個人，就不是同門。

除此之外，在武林中還需要組建聯盟擴大幫派勢力。既然楊不悔嫁給了殷梨亭，不妨直接設張無忌的上級為張三丰，這樣就可以將明教和武當組成一個更大的聯盟（如圖3-2紅色虛線。需要說明，我們只關心數據的代表，而忽略數據內部結構）。從此以後當宋青書再和楊不悔相遇，一級一級查詢後可以確定是同夥了。但是如果大俠們相遇都像這樣一級一級往上問，查詢路徑很長。所以這種直接連接最上級的方法不是最優。

為了解決這個問題，需要壓縮路徑——每個人記住自己最終的老大就行（如宋青書記住自己老大是張三丰，不在去問宋遠橋），基本思路如下：

以武當為例，張三丰創建門派（明教也類似）
宋遠橋和殷梨亭加入武當派，上級設置為張三丰
宋青書通過與宋遠橋的關係加入武當派，壓縮路徑後設置上級為張三丰，同時也設置其所有原上級的上級為張三丰（由於原上級宋遠橋的上級就是張三丰，沒有變化）。

壓縮完路徑後的武當與明教狀態圖如下，其中紅色代表壓縮路徑：

圖3-3

楊不悔通過與殷梨亭的關係也加入武當派別，壓縮路徑後設置上級為張三丰，同時設置原上級張無忌的上級是張三丰。綠色代表此次壓縮路徑。

圖3-4

以後每次在合併中關係到了誰，就壓縮誰的路徑，同時壓縮誰的所有上級的路徑。此後宋青書和楊不悔的查詢路徑就短了很多。

假如某天范右使收徒了，徒弟也要加入聯盟。在加入的時候，也需要壓縮路徑，設置徒弟的上級為張三丰；同時設置徒弟的原上級（范右使和張無忌）的上級為張三丰，如藍色箭頭。由於張無忌的上級就是張三丰，所以沒有改變。這樣，范右使的路徑也得到壓縮。

圖3-5

看完例子之後，一起來看看並查集定義。並查集保持一組不相交的動態集合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）。並查集偽代碼如下：

//創建Union-setnMAKE-SET(x)n1 p[x] ← x //←號表示賦值n2 rank[x] ← 0nn//合併x和y，底層壓縮路徑nUNION(x, y)n1 LINK(FIND-SET(x), FIND-SET(y))nnLINK(x, y)n1 if rank[x] < rank[y]n2 p[x] ← yn3 elsen4 p[y] ← xn5 if rank[x]==rank[y]n6 rank[x] = rank[x] + 1nnFIND-SET(x)n1 if x ≠ p[x]n2 p[x] ← FIND-SET(p[x])n3 return p[x]n

其中，MAKE-SET函數用於在無序數據中初始化並查集數據結構，將每個結點父結點設為其本身；UNION函數通過調用LINK和FIND-SET實現帶壓縮路徑的並查集合併；LINK函數通過秩進行並查集合併；FIND-SET是帶壓縮路徑的尋找結點代表的函數。如果還有不明白的地方，建議查閱《演算法導論》中的第21章：《用於不相交的數據結構》。

3.2 利用並查集合併檢測結果窗口

為了將並查集利用到合併窗口中，首先要定義窗口相似函數，即當前的兩個窗口是不是「一伙人」。在OpenCV中，圖像中的矩形窗口一般用Rect結構體表示，其包含x,y,width,height共4個成員變數，分別代表窗口的左上角點x坐標、y坐標、寬度和高度。下面代碼定義了窗口相似函數SimilarRects::operator()，當2個窗口r1和r2位置很接近時返回TRUE，通過SimilarRects::operator()就可以將圖1那些重疊的窗口合併在「一伙人」中。

class CV_EXPORTS SimilarRectsn{npublic:n SimilarRects(double _eps) : eps(_eps) {}n inline bool operator()(const Rect& r1, const Rect& r2) constn {n double delta = eps*(std::min(r1.width, r2.width) + std::min(r1.height, r2.height))*0.5;n return std::abs(r1.x - r2.x) <= delta &&n std::abs(r1.y - r2.y) <= delta &&n std::abs(r1.x + r1.width - r2.x - r2.width) <= delta &&n std::abs(r1.y + r1.height - r2.y - r2.height) <= delta;n }n double eps;n}n

定義好窗口相似性函數後，就可以利用並查集合併窗口函數了，大致過程如下：

首先利用MAKE-SET函數建立Rect對象的並查集初始結構
然後遍歷整個並查集，用SimilarRects::operator()判斷每2個窗口相似性，若相似則將這2個窗口合併為「一伙人」；
運行完步驟2後應該出現幾個相互間不相似的窗口「團伙」，當「團伙」中的窗口數量小於閾值minNeighbors時，丟棄該「團伙」（認為這是零散分布的誤檢）；
之後剩下若干組由大量重疊窗口組成的大「團伙」，分別求每個「團伙」中的所有窗口位置的平均值作為最終檢測結果。

這裡只介紹NMS基本演算法，代碼請讀者自行查閱OpenCV源碼。不過在演算法描述中為了清晰簡潔，使用遞歸實現了整個並查集；但在實際中遞歸需要保存現場並進行壓棧，開銷極大，所以OpenCV使用循環替代了遞歸。

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時分類情況

可以看到，當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);nfloat falseAlarm = ((float) numFalse) / ((float) numNeg);n

換個表達方式：

$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} times hitRate_{2} times ..... times hitRate_{n} = prod_{1}^{n}hitRate_{i}$

$falseAlarmRate = falseAlarm_{1} times ...... times 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 x h大小的圖片轉換為二進位vec文件（只是讀取圖片並轉化為灰度圖，並按照二進位格式保存下來而已，不做任何改變）。由於經過如此處理的正樣本就是固定w x h大小的patches，所以正樣本可以直接進入訓練。
負樣本patches收集過程：而使用的負樣本就不一樣了，是一個包含任意大小圖片路徑的txt文件。在尋找負樣本的過程中，程序會以圖像金字塔(pyramid)+滑動窗口的模式(sliding-window)去遍歷整個負樣本集，以獲取w x 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 )n{n int getcount = 0;n Mat img(cascadeParams.winSize, CV_8UC1);n for( int i = first; i < first + count; i++ )n {n for( ; ; )n {n if( consumed != 0 && ((double)getcount+1)/(double)(int64)consumed <= minimumAcceptanceRatio )n return getcount;nn bool isGetImg = isPositive ? imgReader.getPos( img ) : imgReader.getNeg( img ); //讀取樣本n if( !isGetImg )n return getcount; //如果不能讀取樣本（出錯or樣本消耗光了），返回n consumed++; //只要讀取到了樣本，不管判斷結果如何，消耗量consumed增加1nn //當參數isPositive = true時，填充正樣本隊列，此時選擇TP進入隊列n //當參數isPositive = false時，填充負樣本隊列，此時選擇FP進入隊列n featureEvaluator->setImage( img, isPositive ? 1 : 0, i ); //將樣本img塞入訓練隊列中n if( predict( i ) == 1 ) //根據isPositive判斷是否是TP/FP, 是則break進入下一個；反之繼續循環，並覆蓋上面setImage的樣本n {n getcount++; //真正添加進訓練隊列的數量n printf("%s current samples: %dr", isPositive ? "POS":"NEG", getcount);n break;n }n }n }n return getcount;n}n

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

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

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

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

看到這就很清晰了，默認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;nfor( int i = 0; i < sCount; i++ ) //遍歷樣本n if( ((CvCascadeBoostTrainData*)data)->featureEvaluator->getCls( i ) == 1.0F ) //if current sample is TPn eval[numPos++] = predict( i, true ); //predict加入true參數後，會返回當前stage中弱分類器輸出之和（如上文predict介紹）nicvSortFlt( &eval[0], numPos, 0 ); //升序排序nint thresholdIdx = (int)((1.0F - minHitRate) * numPos); //按照minHitRate估計一個比例作為indexnthreshold = eval[ thresholdIdx ]; //取該index的值作為stageThresholdn

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

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

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

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

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

返回false時，停止當前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訓練

各位看官老爺，理解了么？

最後求贊求關。謝謝！