Adaboost算法詳解（haar人臉檢測）

轉自：https://wizardforcel.gitbooks.io/dm-algo-top10/content/adaboost.html（臉書動不動上不去故轉載）（主要看adaboost的例子、公式）

資料挖掘算法學習（八）Adaboost算法（例子好）

來源：http://blog.csdn.net/iemyxie/article/details/40423907

Adaboost是一種疊代算法，其核心思想是針對同一個訓練集訓練不同的分類器（弱分類器），然後把這些弱分類器集合起來，構成一個更強的最終分類器（強分類器）。Adaboost算法本身是通過改變資料分布來實作的，它根據每次訓練集之中每個樣本的分類是否正确，以及上次的總體分類的準确率，來确定每個樣本的權值。将修改過權值的新資料集送給下層分類器進行訓練，最後将每次得到的分類器最後融合起來，作為最後的決策分類器。

算法概述

1、先通過對N個訓練樣本的學習得到第一個弱分類器； 2、将分錯的樣本和其他的新資料一起構成一個新的N個的訓練樣本，通過對這個樣本的學習得到第二個弱分類器； 3、将1和2都分錯了的樣本加上其他的新樣本構成另一個新的N個的訓練樣本，通過對這個樣本的學習得到第三個弱分類器 4、最終經過提升的強分類器。即某個資料被分為哪一類要由各分類器權值決定。

與boosting算法比較

1. 使用權重後選取的訓練資料代替随機選取的訓練樣本，這樣将訓練的焦點集中在比較難分的訓練資料樣本上； 　　 2. 将弱分類器聯合起來，使用權重的投票機制代替平均投票機制。讓分類效果好的弱分類器具有較大的權重，而分類效果差的分類器具有較小的權重。

與Boosting算法不同的是，AdaBoost算法不需要預先知道弱學習算法學習正确率的下限即弱分類器的誤差，并且最後得到的強分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。

算法步驟

1. 給定訓練樣本集S，其中X和Y分别對應于正例樣本和負例樣本；T為訓練的最大循環次數； 2. 初始化樣本權重為1/n ，即為訓練樣本的初始機率分布； 　　 3. 第一次疊代：(1)訓練樣本的機率分布相當，訓練弱分類器;(2)計算弱分類器的錯誤率;(3)選取合适門檻值，使得誤差最小；(4)更新樣本權重； 　　 經T次循環後，得到T個弱分類器，按更新的權重疊加，最終得到的強分類器。

具體步驟如下：

一.樣本

Given: m examples (x1, y1), …, (xm, ym)
     where xiX, yiY={-1, +1}
     xi表示X中第i個元素，
     yi表示與xi對應元素的屬性值，+1表示xi屬于某個分類，
     -1表示xi不屬于某個分類
           

二.初始化訓練樣本

xi的權重D(i) :i=1,……，m;
     (1).若正負樣本數目一緻，D1(i) = 1/m
     (2).若正負樣本數目m+, m-則正樣本D1(i) = 1/m+，
         負樣本D1(i) = 1/m-
           

if（e>=0.5） stop;因為這個弱分類器将一半以上的樣本都分錯了；是以該特征不可作為弱分類器的特征使用；

執行個體詳解（例子好，必看）

圖中“+”和“-”表示兩種類别。我們用水準或者垂直的直線作為分類器進行分類。

算法開始前預設均勻分布D，共10個樣本，故每個樣本權值為0.1.

第一次分類：

第一次劃分有3個點劃分錯誤，根據誤差表達式

 計算可得

e1=（0.1+0.1+0.1）/1.0=0.3

分類器權重：

a1=(1/2).*(log((1-e1)./e1))=0.42;

然後根據算法把錯分點的權值變大。對于正确分類的7個點，權值不變，仍為0.1,對于錯分的3個點，權值為：

D1=D0*(1-e1)/e1=0.1*(1-0.3)/0.3=0.2333
           

第二次分類：

如圖所示，有3個"-"分類錯誤。上輪分類後權值之和為：0.17+0.23333=1.3990

分類誤差：

e2=0.1*3/1.3990=0.2144

分類器權重

a2=0.6493

錯分的3個點權值為：

D2=0.1*（1-0.2144）/0.2144=0.3664

第三次分類：

同上步驟可求得：

e3=0.1365

 ；

a3=0.9223

；

D3=0.6326

最終的強分類器即為三個弱分類器的疊加，如下圖所示：

每個區域是屬于哪個屬性，由這個區域所在分類器的權值綜合決定。比如左下角的區域，屬于藍色分類區的權重為h1 中的0.42和h2 中的0.65，其和為1.07；屬于淡紅色分類區域的權重為h3 中的0.92；屬于淡紅色分類區的權重小于屬于藍色分類區的權值，是以左下角屬于藍色分類區。是以可以得到整合的結果如上圖所示，從結果圖中看，即使是簡單的分類器，組合起來也能獲得很好的分類效果。

分類器權值調整的原因

由公式可以看到，權值是關于誤差的表達式。每次疊代都會提高錯分點的權值，當下一次分類器再次錯分這些點之後，會提高整體的錯誤率，這樣就導緻分類器權值變小，進而導緻這個分類器在最終的混合分類器中的權值變小，也就是說，Adaboost算法讓正确率高的分類器占整體的權值更高，讓正确率低的分類器權值更低，進而提高最終分類器的正确率。

算法優缺點

優點

1)Adaboost是一種有很高精度的分類器 2)可以使用各種方法建構子分類器,Adaboost算法提供的是架構 3)當使用簡單分類器時，計算出的結果是可以了解的。而且弱分類器構造極其簡單 4)簡單，不用做特征篩選 5)不用擔心overfitting(過度拟合)

缺點

1)容易受到噪聲幹擾，這也是大部分算法的缺點

2)訓練時間過長

3)執行效果依賴于弱分類器的選擇

y=y=(1-x)./x;  （D1=D0*(1-e1)/e1=0.1*(1-0.3)/0.3=0.2333）某點的權值的變化：

y=(1/2).*(log((1-x)./x));a1=(1/2).*(log((1-e1)./e1))=0.42;弱分類器權重：

這篇文章講解haar+adaboost檢測人臉将的好：https://www.cnblogs.com/dylantsou/archive/2012/08/11/2633483.html（主要看haar特征個數的計算；如何從haar特征中選取弱分類器需要的特征）

摘要：

基于haar特征的Adaboost人臉檢測技術

基于haar特征的Adaboost人臉檢測技術

本文主要是對使用haar+Adabbost進行人臉檢測的一些原理進行說明，主要是快找工作了，督促自己複習下~~

一、AdaBoost算法原理

　　AdaBoost算法是一種疊代的算法，對于一組訓練集，通過改變其中每個樣本的分布機率，而得到不同的訓練集Si，對于每一個Si進行訓練進而得到一個弱分類器Hi，再将這些若分類器根據不同的權值組合起來，就得到了強分類器。

　　第一次的時候，每個樣本都是均勻分布，通過訓練得到分類器H0，在該訓練集中，分類正确的，就降低其分布機率；分類錯誤的，就提高其分布機率，這樣得到的新的訓練集S1就主要是針對不太好分類的樣本了。再使用S1進行訓練，得到分類器H1，依次疊代下去……，設疊代此外為T，則得到T個分類器。

　　對于每個分類器的權值，其分類準确性越高，權值越高。

二、Haar特征

Haar-like特征是計算機視覺領域一種常用的特征描述算子(也稱為Haar特征，這是因為Haar-like是受到一維haar小波的啟示而發明的,是以稱為類Haar特征)，後來又将Haar-like擴充到三維空間(稱為3DHaar-Like)用來描述視訊中的動态特征。關于Haar的發展曆程如圖1所示。

　　2.1 特征樣子

　　就是一些矩形特征的模闆，在viola&Jones的論文中，有下面這五種

在opencv中的方法中，有下面這14種，

　　2.2 特種的個數

　　對于一個給定的24X24的視窗，根據不同的位置，以及不同的縮放，可以産生超過160,000個特征。

　　特征個數的計算方法：

int getHaarCount(int W, int H, int w, int h){
	int X = W / w;
	int Y = H / h;
	int count = 0;

	//放大Haar特征到 iw*jh  
	for (int i = 1; i <= X; i++)
	for (int j = 1; j <= Y; j++)
		//滑動iw*jh矩形，周遊圖像計算每個位置Haar特征  
	for (int x = 1; x <= W - i*w + 1; x++)
	for (int y = 1; y <= H - j*h + 1; y++)
		count++;

	return count;
}
           

　　2.3 特征計算方法——積分圖

　　有點類似于動态規劃的思想，一次計算，多次使用

　　對應于兩矩形特征2，矩陣A的值可以用i(5)+ii(1)-ii(4)-ii(2)表示，矩陣B的值用ii(6)+ii(2)-ii(3)-ii(5)表示

　　根據定義，haar特征的值為白色矩形減去黑色矩形的值。

三、選取弱分類器

　　一個弱分類器，實際上就是在這160,000+的特征中選取一個特征，用這個特征能夠區分出人臉or非人臉，且錯誤率最低。

　　現在有人臉樣本2000張，非人臉樣本4000張，這些樣本都經過了歸一化，大小都是24X24的圖像。那麼，對于160,000+中的任一特征fi，我們計算該特征在這2000人臉樣本、4000非人臉樣本上的值，這樣就得到6000個特征值。将這些特征值排序，然後選取一個最佳的特征值，在該特征值下，對于特征fi來說，樣本的權重錯誤率最低。選擇160,000+個特征中，錯誤率最低的特征，用來判斷人臉，這就是一個弱分類器，同時用此分類器對樣本進行分類，并更新樣本的權重。

轉自：http://blog.csdn.net/watkinsong/article/details/7631241（主要看弱分類器、強分類器的關系排布）

首先，Adaboost是一種基于級聯分類模型的分類器。級聯分類模型可以用下圖表示：

級聯分類器介紹：級聯分類器就是将多個強分類器連接配接在一起進行操作。每一個強分類器都由若幹個弱分類器權重組成，例如，有些強分類器可能包含10個弱分類器，有些則包含20個弱分類器，一般情況下一個級聯用的強分類器包含20個左右的弱分類器，然後在将10個強分類器級聯起來，就構成了一個級聯強分類器，這個級聯強分類器中總共包括200若分類器。因為每一個強分類器對負樣本的判别準确度非常高，是以一旦發現檢測到的目标位負樣本，就不在繼續調用下面的強分類器，減少了很多的檢測時間。因為一幅圖像中待檢測的區域很多都是負樣本，這樣由級聯分類器在分類器的初期就抛棄了很多負樣本的複雜檢測，是以級聯分類器的速度是非常快的；隻有正樣本才會送到下一個強分類器進行再次檢驗，這樣就保證了最後輸出的正樣本的僞正(false positive)的可能性非常低。

也有一些情況下不适用級聯分類器，就簡單的使用一個強分類器的情況，這種情況下一般強分類器都包含200個左右的弱分類器可以達到最佳效果。不過級聯分類器的效果和單獨的一個強分類器差不多，但是速度上卻有很大的提升。

轉自：http://blog.csdn.net/watkinsong/article/details/7631949（主要看：分析為什麼haar可以用于檢測人臉；和弱分類器的訓練）

1. 弱分類器

在确定了訓練子視窗中的矩形特征數量和特征值後，需要對每一個特征f ，訓練一個弱分類器h(x,f,p,O) 。

在CSDN裡編輯公式太困難了，是以這裡和公式有關的都用截圖了。

特别說明：在前期準備訓練樣本的時候，需要将樣本歸一化和灰階化到20*20的大小，這樣每個樣本的都是灰階圖像并且樣本的大小一緻，保證了每一個Haar特征（描述的是特征的位置）都在每一個樣本中出現。

3. 再次介紹弱分類器以及為什麼可以使用Haar特征進行分類

對于本算法中的矩形特征來說，弱分類器的特征值f(x)就是矩形特征的特征值。由于在訓練的時候，選擇的訓練樣本集的尺寸等于檢測子視窗的尺寸，檢測子視窗的尺寸決定了矩形特征的數量，是以訓練樣本集中的每個樣本的特征相同且數量相同，而且一個特征對一個樣本有一個固定的特征值。

對于理想的像素值随機分布的圖像來說，同一個矩形特征對不同圖像的特征值的平均值應該趨于一個定值k。

這個情況，也應該發生在非人臉樣本上，但是由于非人臉樣本不一定是像素随機的圖像，是以上述判斷會有一個較大的偏差。

對每一個特征，計算其對所有的一類樣本(人臉或者非人臉)的特征值的平均值，最後得到所有特征對所有一類樣本的平均值分布。

下圖顯示了20×20 子視窗裡面的全部78,460 個矩形特征對全部2,706個人臉樣本和4,381 個非人臉樣本6的特征值平均數的分布圖。由分布看出，特征的絕大部分的特征值平均值都是分布在0 前後的範圍内。出乎意料的是，人臉樣本與非人臉樣本的分布曲線差别并不大，不過注意到特征值大于或者小于某個值後，分布曲線出現了一緻性差别，這說明了絕大部分特征對于識别人臉和非人臉的能力是很微小的，但是存在一些特征及相應的門檻值，可以有效地區分人臉樣本與非人臉樣本。

為了更好地說明問題，我們從78,460 個矩形特征中随機抽取了兩個特征A和B，這兩個特征周遊了2,706 個人臉樣本和4,381 個非人臉樣本，計算了每張圖像對應的特征值，最後将特征值進行了從小到大的排序，并按照這個新的順序表繪制了分布圖如下所示：

可以看出，矩形特征A在人臉樣本和非人臉樣本中的特征值的分布很相似，是以區分人臉和非人臉的能力很差。

下面看矩形特征B在人臉樣本和非人臉樣本中特征值的分布：

可以看出，矩形特征B的特征值分布，尤其是0點的位置，在人臉樣本和非人臉樣本中差别比較大，是以可以更好的實作對人臉分類。

由上述的分析，門檻值q 的含義就清晰可見了。而方向訓示符p 用以改變不等号的方向。

一個弱學習器（一個特征）的要求僅僅是：它能夠以稍低于50%的錯誤率來區分人臉和非人臉圖像，是以上面提到隻能在某個機率範圍内準确地進行區分就

已經完全足夠。按照這個要求，可以把所有錯誤率低于50%的矩形特征都找到（适當地選擇門檻值，對于固定的訓練集，幾乎所有的矩形特征都可以滿足上述要求）。每輪訓練，将選取當輪中的最佳弱分類器（在算法中，疊代T 次即是選擇T 個最佳弱分類器），最後将每輪得到的最佳弱分類器按照一定方法提升（Boosting）為強分類器

4 弱分類器的訓練及選取

訓練一個弱分類器（特征f）就是在目前權重分布的情況下，确定f 的最優門檻值，使得這個弱分類器（特征f）對所有訓練樣本的分類誤差最低。

選取一個最佳弱分類器就是選擇那個對所有訓練樣本的分類誤差在所有弱分類器中最低的那個弱分類器（特征）。

對于每個特征 f，計算所有訓練樣本的特征值，并将其排序。通過掃描一遍排好序的特征值，可以為這個特征确定一個最優的門檻值，進而訓練成一個弱分類器。具體來說，對排好序的表中的每個元素，計算下面四個值：

6. 圖像檢測過程

在對輸入圖像進行檢測的時候，一般輸入圖像都會比20*20的訓練樣本大很多。在Adaboost 算法中采用了擴大檢測視窗的方法，而不是縮小圖檔。

為什麼擴大檢測視窗而不是縮小圖檔呢，在以前的圖像檢測中，一般都是将圖檔連續縮小十一級，然後對每一級的圖像進行檢測，最後在對檢測出的每一級結果進行彙總。然而，有個問題就是，使用級聯分類器的AdaBoost的人臉檢測算法的速度非常的快，不可能采用圖像縮放的方法，因為僅僅是把圖像縮放11級的處理，就要消耗一秒鐘至少，已經不能達到Adaboost 的實時處理的要求了。

因為Haar特征具有與檢測視窗大小無關的特性（想要了解細節還要讀一下原作者的文獻），是以可以将檢測視窗進行級别方法。

在檢測的最初，檢測視窗和樣本大小一緻，然後按照一定的尺度參數（即每次移動的像素個數，向左然後向下，一開始一次檢測20×20的區域）進行移動，周遊整個圖像，标出可能的人臉區域。周遊完以後按照指定的放大的倍數參數放大檢測視窗，然後在進行一次圖像周遊；這樣不停的放大檢測視窗對檢測圖像進行周遊，直到檢測視窗超過原圖像的一半以後停止周遊。因為 整個算法的過程非常快，即使是周遊了這麼多次，根據不同電腦的配置大概處理一幅圖像也就是幾十毫秒到一百毫秒左右。

在檢測視窗周遊完一次圖像後，處理重疊的檢測到的人臉區域，進行合并等操作。

我的了解是：在檢測時：一開始用24×24的子視窗掃描原圖，子視窗分别用訓練好的Adaboost檢測，在第一級的時候就可以抛掉大部分的非人臉樣本了；然後将子視窗和特征視窗（haar視窗）放大相同的倍數再掃描原圖查找；

用Cascade Adaboost 檢測為什麼快：先用第一層檢測圖像标記可能是人臉的區域，用第二層檢測第一層标記的區域，再用第三層檢測第二層标記的區域，依次執行；被最後一層标記的區域即為人臉區域；

在檢測的最初，檢測視窗和樣本大小一緻，然後按照一定的尺度參數（即每次移動的像素個數，向左然後向下，一開始一次檢測20×20的區域）進行移動，周遊整個圖像，标出可能的人臉區域。

• 在檢測不同大小的人臉時，沒有采用金字塔政策，而是直接用不同尺度的人臉檢測器在同一幅圖像上掃。作者認為生成金字塔太慢。但除了24*24尺度的，其它尺度的檢測器的cascade細節幾乎沒有介紹。不知道是不是我搞錯了？

摘自：論文“Robust Real-Time Face Detection”：

這裡面的門檻值（θ ）應該是一個比值，表示的是前百分之多少判為正，（1-θ ）×num判為正；

當判斷一個新值時也可以比較新特征在特征表中按大小排序的位置，看是不是百分之θ内的；

Adaboost算法：

Adaboost 和boosting 算法的差別：http://blog.csdn.net/whiteinblue/article/details/14518773

在最後顯然 a 表示的就是弱分類器的權值；當某個弱分類器認為是真樣本時使 h = 1；

假設 a 被歸一化了，那麼右邊必然等于0.5，左邊的 h 等于 0 或 1 ，意思豈不是判對的弱判決器的比重占到一半以上的話，就是正的話，你們強判決器就判為正；

誤檢率 F；檢測率 D ；

減小誤檢率的同時，也減小的檢測率；

Cascade Adaboost算法：

false positive rate：假正率、檢測為0的樣本中正樣本的機率：（檢測為1，實際為0的樣本）/（所有檢測為1的樣本）；

TPR（True positive rate）：召回率：（檢測為1實際也為1的樣本）/（所有檢測為1的樣本）；

detection rate：（檢測到的正樣本）/（所有的正樣本）；

• User selects values for f , the maximum acceptable false
positive rate per layer and d, the minimum acceptable detection
rate per layer.
• User selects target overall false positive rate, Ftarget.
• P = set of positive examples
• N = set of negative examples
• F0 = 1.0; D0 = 1.0
• i = 0
• while Fi > Ftarget （某層誤檢率小于Ftarget，則停止）
– i ← i + 1
– ni = 0; Fi = Fi−1
– while Fi > f × Fi−1  （這層的錯檢率要小于上次的*f）
∗ ni ← ni + 1
∗ Use P and N to train a classifier with ni features using AdaBoost
∗ Evaluate current cascaded classifier on validation set to
determine Fi and Di .
∗ Decrease threshold for the ith classifier until the current cascaded classifier has a detection rate of at least d × Di−1 (this also affects Fi )（這層的檢測率至少達到上次的檢測率*d）
– N ← ∅
– If Fi > Ftarget then evaluate the current cascaded detector on the set of non-face images and put any false detections into the set N
           

• User selects values for f , the maximum acceptable false
positive rate per layer and d, the minimum acceptable detection
rate per layer.
• User selects target overall false positive rate, Ftarget.
• P = set of positive examples
• N = set of negative examples
• F0 = 1.0; D0 = 1.0
• i = 0
• while Fi > Ftarget （某層誤檢率小于Ftarget，則停止）
– i ← i + 1
– ni = 0; Fi = Fi−1
– while Fi > f × Fi−1  （這層的錯檢率要小于上次的*f）
∗ ni ← ni + 1
∗ Use P and N to train a classifier with ni features using AdaBoost
∗ Evaluate current cascaded classifier on validation set to
determine Fi and Di .
∗ Decrease threshold for the ith classifier until
 the current cascaded classifier has 
a detection rate of at least d × Di−1 (this also affects Fi )
（這層的檢測率至少達到上次的檢測率*d）
– N ← ∅
– If Fi > Ftarget then evaluate the current 
cascaded detector on the set of non-face images 
and put any false detections into the set N
           

反思：haar檢測中的特征個數為什麼那麼多，因為一個坐标的某個特征視窗的，某個尺寸就是一個特征；也就是說特征是由在歸一化後的訓練集（24×24圖檔）的某個坐标上、某個特征窗、某個窗尺寸，，三個一起決定的，是以說訓練的時候，有所謂的是不是眼睛對齊、人臉在正中間等；

名詞解釋：

1 false positive rate（假陽率） ：false positive rate，FPR.，誤診率或第Ⅰ類錯誤的。即實際無病或陰性，但被判為有病或陽性的百分比。

Adaboost應用系列之二：Opencv2.0中利用Adaboost訓練LBP特征産生xml分類器：http://blog.csdn.net/holybin/article/details/16863043