Haar特征與積分圖

1. Adaboost方法的引入

1.1 Boosting方法的提出和發(fā)展

        在了解Adaboost方法之前,，先了解一下Boosting方法。

        回答一個(gè)是與否的問題,，隨機(jī)猜測(cè)可以獲得50%的正確率,。如果一種方法能獲得比隨機(jī)猜測(cè)稍微高一點(diǎn)的正確率，則就可以稱該得到這個(gè)方法的過程為弱學(xué)習(xí),；如果一個(gè)方法可以顯著提高猜測(cè)的正確率,，則稱獲取該方法的過程為強(qiáng)學(xué)習(xí)。1994年,，Kearns和Valiant證明,，在Valiant的PAC（Probably ApproximatelyCorrect）模型中，只要數(shù)據(jù)足夠多,，就可以將弱學(xué)習(xí)算法通過集成的方式提高到任意精度,。實(shí)際上，1990年,，SChapire就首先構(gòu)造出一種多項(xiàng)式級(jí)的算法,，將弱學(xué)習(xí)算法提升為強(qiáng)學(xué)習(xí)算法，就是最初的Boosting算法,。Boosting意思為提升,、加強(qiáng)，現(xiàn)在一般指將弱學(xué)習(xí)提升為強(qiáng)學(xué)習(xí)的一類算法,。1993年,，Drucker和Schapire首次以神經(jīng)網(wǎng)絡(luò)作為弱學(xué)習(xí)器，利用Boosting算法解決實(shí)際問題,。前面指出,，將弱學(xué)習(xí)算法通過集成的方式提高到任意精度，是Kearns和Valiant在1994年才證明的,，雖然Boosting方法在1990年已經(jīng)提出，但它的真正成熟,，也是在1994年之后才開始的,。1995年，Freund提出了一種效率更高的Boosting算法,。

1.2 AdaBoost算法的提出

        1995年,，F(xiàn)reund和Schapire提出了Adaboost算法，是對(duì)Boosting算法的一大提升,。Adaboost是Boosting家族的代表算法之一,，全稱為Adaptive Boosting,。Adaptively，即適應(yīng)地,，該方法根據(jù)弱學(xué)習(xí)的結(jié)果反饋適應(yīng)地調(diào)整假設(shè)的錯(cuò)誤率,，所以Adaboost不需要預(yù)先知道假設(shè)的錯(cuò)誤率下限。也正因?yàn)槿绱?，它不需要任何關(guān)于弱學(xué)習(xí)器性能的先驗(yàn)知識(shí),，而且和Boosting算法具有同樣的效率，所以在提出之后得到了廣泛的應(yīng)用,。

首先,，Adaboost是一種基于級(jí)聯(lián)分類模型的分類器。級(jí)聯(lián)分類模型可以用下圖表示：

級(jí)聯(lián)分類器介紹：級(jí)聯(lián)分類器就是將多個(gè)強(qiáng)分類器連接在一起進(jìn)行操作,。每一個(gè)強(qiáng)分類器都由若干個(gè)弱分類器加權(quán)組成,，

例如，有些強(qiáng)分類器可能包含10個(gè)弱分類器,，有些則包含20個(gè)弱分類器,，一般情況下一個(gè)級(jí)聯(lián)用的強(qiáng)分類器包含20個(gè)左右的弱分類器，然后在將10個(gè)強(qiáng)分類器級(jí)聯(lián)起來(lái),，就構(gòu)成了一個(gè)級(jí)聯(lián)強(qiáng)分類器,，這個(gè)級(jí)聯(lián)強(qiáng)分類器中總共包括200弱分類器。因?yàn)槊恳粋€(gè)強(qiáng)分類器對(duì)負(fù)樣本的判別準(zhǔn)確度非常高,，所以一旦發(fā)現(xiàn)檢測(cè)到的目標(biāo)位負(fù)樣本,，就不在繼續(xù)調(diào)用下面的強(qiáng)分類器，減少了很多的檢測(cè)時(shí)間,。因?yàn)橐环鶊D像中待檢測(cè)的區(qū)域很多都是負(fù)樣本,，這樣由級(jí)聯(lián)分類器在分類器的初期就拋棄了很多負(fù)樣本的復(fù)雜檢測(cè)，所以級(jí)聯(lián)分類器的速度是非?？斓?；只有正樣本才會(huì)送到下一個(gè)強(qiáng)分類器進(jìn)行再次檢驗(yàn)，這樣就保證了最后輸出的正樣本的偽正(false positive)的可能性非常低,。

 也有一些情況下不適用級(jí)聯(lián)分類器,，就簡(jiǎn)單的使用一個(gè)強(qiáng)分類器的情況，這種情況下一般強(qiáng)分類器都包含200個(gè)左右的弱分類器可以達(dá)到最佳效果,。不過級(jí)聯(lián)分類器的效果和單獨(dú)的一個(gè)強(qiáng)分類器差不多,，但是速度上卻有很大的提升。

 級(jí)聯(lián)結(jié)構(gòu)分類器由多個(gè)弱分類器組成,，每一級(jí)都比前一級(jí)復(fù)雜,。每個(gè)分類器可以讓幾乎所有的正例通過，同時(shí)濾除大部分負(fù)例,。這樣每一級(jí)的待檢測(cè)正例就比前一級(jí)少,，排除了大量的非檢測(cè)目標(biāo),，可大大提高檢測(cè)速度。

其次,，Adaboost是一種迭代算法,。初始時(shí)，所有訓(xùn)練樣本的權(quán)重都被設(shè)為相等,，在此樣本分布下訓(xùn)練出一個(gè)弱分類器,。在第（  =1,2,3, …T，T為迭代次數(shù)）次迭代中,，樣本的權(quán)重由第  -1次迭代的結(jié)果而定,。在每次迭代的最后，都有一個(gè)調(diào)整權(quán)重的過程,，被分類錯(cuò)誤的樣本將得到更高的權(quán)重,。這樣分錯(cuò)的樣本就被突出出來(lái)，得到一個(gè)新的樣本分布,。在新的樣本分布下,，再次對(duì)弱分類器進(jìn)行訓(xùn)練，得到新的弱分類器,。經(jīng)過T次循環(huán),，得到T個(gè)弱分類器，把這T個(gè)弱分類器按照一定的權(quán)重疊加起來(lái),，就得到最終的強(qiáng)分類器,。

2. 矩形特征

2.1 Haar特征\矩形特征

AdaBoost算法的實(shí)現(xiàn)，采用的是輸入圖像的矩形特征,，也叫Haar特征,。下面簡(jiǎn)要介紹矩形特征的特點(diǎn)。

影響Adaboost檢測(cè)訓(xùn)練算法速度很重要的兩方面是特征的選取和特征值的計(jì)算,。臉部的一些特征可以由矩形特征簡(jiǎn)單地描繪,。用圖2示范：

上圖中兩個(gè)矩形特征，表示出人臉的某些特征,。比如中間一幅表示眼睛區(qū)域的顏色比臉頰區(qū)域的顏色深,，右邊一幅表示鼻梁兩側(cè)比鼻梁的顏色要深。同樣,，其他目標(biāo),，如眼睛等，也可以用一些矩形特征來(lái)表示,。使用特征比單純地使用像素點(diǎn)具有很大的優(yōu)越性，并且速度更快,。

在給定有限的數(shù)據(jù)情況下,，基于特征的檢測(cè)能夠編碼特定區(qū)域的狀態(tài),，而且基于特征的系統(tǒng)比基于象素的系統(tǒng)要快得多。
矩形特征對(duì)一些簡(jiǎn)單的圖形結(jié)構(gòu),，比如邊緣,、線段，比較敏感,，但是其只能描述特定走向（水平,、垂直、對(duì)角）的結(jié)構(gòu),，因此比較粗略,。如上圖，臉部一些特征能夠由矩形特征簡(jiǎn)單地描繪,，例如,，通常，眼睛要比臉頰顏色更深,；鼻梁兩側(cè)要比鼻梁顏色要深,；嘴巴要比周圍顏色更深。

對(duì)于一個(gè) 24×24 檢測(cè)器,，其內(nèi)的矩形特征數(shù)量超過160,000 個(gè),，必須通過特定算法甄選合適的矩形特征，并將其組合成強(qiáng)分類器才能檢測(cè)人臉,。

常用的矩形特征有三種：兩矩形特征,、三矩形特征、四矩形特征,，如圖：

由圖表可以看出,，兩矩形特征反映的是邊緣特征，三矩形特征反映的是線性特征,、四矩形特征反映的是特定方向特征,。

特征模板的特征值定義為：白色矩形像素和減去黑色矩形像素和。接下來(lái),，要解決兩個(gè)問題,，1：求出每個(gè)待檢測(cè)子窗口中的特征個(gè)數(shù)。2：求出每個(gè)特征的特征值,。

子窗口中的特征個(gè)數(shù)即為特征矩形的個(gè)數(shù),。訓(xùn)練時(shí)，將每一個(gè)特征在訓(xùn)練圖像子窗口中進(jìn)行滑動(dòng)計(jì)算,，獲取各個(gè)位置的各類矩形特征,。在子窗口中位于不同位置的同一類型矩形特征，屬于不同的特征?？梢宰C明,，在確定了特征的形式之后，矩形特征的數(shù)量只與子窗口的大小有關(guān)^[11],。在24×24的檢測(cè)窗口中,，矩形特征的數(shù)量約為160,000個(gè)。

特征模板可以在子窗口內(nèi)以“任意”尺寸“任意”放置,，每一種形態(tài)稱為一個(gè)特征,。找出子窗口所有特征，是進(jìn)行弱分類訓(xùn)練的基礎(chǔ),。

2.2子窗口內(nèi)的條件矩形,，矩形特征個(gè)數(shù)的計(jì)算

如圖所示的一個(gè)m*m大小的子窗口，可以計(jì)算在這么大的子窗口內(nèi)存在多少個(gè)矩形特征,。

以 m×m 像素分辨率的檢測(cè)器為例,，其內(nèi)部存在的滿足特定條件的所有矩形的總數(shù)可以這樣計(jì)算：
對(duì)于 m×m 子窗口，我們只需要確定了矩形左上頂點(diǎn)A(x1,y1)和右下頂點(diǎn)B(x2,63) ,，即可以確定一個(gè)矩形,；如果這個(gè)矩形還必須滿足下面兩個(gè)條件（稱為(s, t)條件，滿足(s, t)條件的矩形稱為條件矩形）：

1) x 方向邊長(zhǎng)必須能被自然數(shù)s 整除（能均等分成s 段）,；
2) y 方向邊長(zhǎng)必須能被自然數(shù)t 整除（能均等分成t 段）,；
則 ， 這個(gè)矩形的最小尺寸為s×t 或t×s,， 最大尺寸為[m/s]·s×[m/t]·t 或[m/t]·t×[m/s]·s,；其中[ ]為取整運(yùn)算符。

2.3條件矩形的數(shù)量

我們通過下面兩步就可以定位一個(gè)滿足條件的矩形：

由上分析可知,，在m×m 子窗口中,，滿足(s, t)條件的所有矩形的數(shù)量為：

實(shí)際上，(s, t)條件描述了矩形特征的特征,，下面列出了不同矩形特征對(duì)應(yīng)的(s, t)條件：

下面以 24×24 子窗口為例,，具體計(jì)算其特征總數(shù)量：

下面列出了，在不同子窗口大小內(nèi),，特征的總數(shù)量：

3. 積分圖

3.1 積分圖的概念

在獲取了矩形特征后,，要計(jì)算矩形特征的值。Viola等人提出了利用積分圖求特征值的方法,。積分圖的概念可用圖3表示：

坐標(biāo)A(x,y)的積分圖是其左上角的所有像素之和（圖中的陰影部分）,。定義為：

其中ii(x,y)表示積分圖，i(x,y)表示原始圖像,，對(duì)于彩色圖像,，是此點(diǎn)的顏色值；對(duì)于灰度圖像，是其灰度值,，范圍為0~255,。

在上圖中，A(x,y)表示點(diǎn)(x,y)的積分圖,；s(x,y)表示點(diǎn)(x,y)的y方向的所有原始圖像之和。積分圖也可以用公式（2）和公式（3）得出：

3.2 利用積分圖計(jì)算特征值

3.3 計(jì)算特征值

由上一節(jié)已經(jīng)知道,，一個(gè)區(qū)域的像素值,，可以由該區(qū)域的端點(diǎn)的積分圖來(lái)計(jì)算。由前面特征模板的特征值的定義可以推出,，矩形特征的特征值可以由特征端點(diǎn)的積分圖計(jì)算出來(lái),。以“兩矩形特征”中的第二個(gè)特征為例，如下圖,，使用積分圖計(jì)算其特征值：

級(jí)聯(lián)分類器與檢測(cè)過程

1. 弱分類器

在確定了訓(xùn)練子窗口中的矩形特征數(shù)量和特征值后,，需要對(duì)每一個(gè)特征f ，訓(xùn)練一個(gè)弱分類器h(x,f,p,O) ,。

在CSDN里編輯公式太困難了,，所以這里和公式有關(guān)的都用截圖了。

特別說(shuō)明：在前期準(zhǔn)備訓(xùn)練樣本的時(shí)候,，需要將樣本歸一化和灰度化到20*20的大小,，這樣每個(gè)樣本的都是灰度圖像并且樣本的大小一致，保證了每一個(gè)Haar特征（描述的是特征的位置）都在每一個(gè)樣本中出現(xiàn),。

2. 訓(xùn)練強(qiáng)分類器

在訓(xùn)練強(qiáng)分類器中,，T表示的是強(qiáng)分類器中包含的弱分類器的個(gè)數(shù)。當(dāng)然,，如果是采用級(jí)聯(lián)分類器,，這里的強(qiáng)分類器中的弱分類器的個(gè)數(shù)可能會(huì)比較少，多個(gè)強(qiáng)分類器在級(jí)聯(lián)起來(lái),。

在c(2)步驟中,，“每個(gè)特征f”指的是在20*20大小的訓(xùn)練樣本中所有的可能出現(xiàn)的矩形特征，大概要有80,000中,，所有的這些都要進(jìn)行計(jì)算,。也就是要計(jì)算80,000個(gè)左右的弱分類器，在選擇性能好的分類器,。

訓(xùn)練強(qiáng)分類器的步驟如圖：

3. 再次介紹弱分類器以及為什么可以使用Haar特征進(jìn)行分類

對(duì)于本算法中的矩形特征來(lái)說(shuō),，弱分類器的特征值f(x)就是矩形特征的特征值。由于在訓(xùn)練的時(shí)候,，選擇的訓(xùn)練樣本集的尺寸等于檢測(cè)子窗口的尺寸,，檢測(cè)子窗口的尺寸決定了矩形特征的數(shù)量，所以訓(xùn)練樣本集中的每個(gè)樣本的特征相同且數(shù)量相同，而且一個(gè)特征對(duì)一個(gè)樣本有一個(gè)固定的特征值,。

對(duì)于理想的像素值隨機(jī)分布的圖像來(lái)說(shuō),，同一個(gè)矩形特征對(duì)不同圖像的特征值的平均值應(yīng)該趨于一個(gè)定值k。
這個(gè)情況,，也應(yīng)該發(fā)生在非人臉樣本上,，但是由于非人臉樣本不一定是像素隨機(jī)的圖像，因此上述判斷會(huì)有一個(gè)較大的偏差,。

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

下圖顯示了20×20 子窗口里面的全部78,460 個(gè)矩形特征對(duì)全部2,706個(gè)人臉樣本和4,381 個(gè)非人臉樣本6的特征值平均數(shù)的分布圖,。由分布看出，特征的絕大部分的特征值平均值都是分布在0 前后的范圍內(nèi),。出乎意料的是,，人臉樣本與非人臉樣本的分布曲線差別并不大，不過注意到特征值大于或者小于某個(gè)值后,，分布曲線出現(xiàn)了一致性差別,，這說(shuō)明了絕大部分特征對(duì)于識(shí)別人臉和非人臉的能力是很微小的，但是存在一些特征及相應(yīng)的閾值,，可以有效地區(qū)分人臉樣本與非人臉樣本,。

為了更好地說(shuō)明問題，我們從78,460 個(gè)矩形特征中隨機(jī)抽取了兩個(gè)特征A和B,，這兩個(gè)特征遍歷了2,706 個(gè)人臉樣本和4,381 個(gè)非人臉樣本,，計(jì)算了每張圖像對(duì)應(yīng)的特征值，最后將特征值進(jìn)行了從小到大的排序,，并按照這個(gè)新的順序表繪制了分布圖如下所示：

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

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

可以看出,，矩形特征B的特征值分布，尤其是0點(diǎn)的位置,，在人臉樣本和非人臉樣本中差別比較大,，所以可以更好的實(shí)現(xiàn)對(duì)人臉分類。

由上述的分析,，閾值q 的含義就清晰可見了,。而方向指示符p 用以改變不等號(hào)的方向。

一個(gè)弱學(xué)習(xí)器（一個(gè)特征）的要求僅僅是：它能夠以稍低于50%的錯(cuò)誤率來(lái)區(qū)分人臉和非人臉圖像,，因此上面提到只能在某個(gè)概率范圍內(nèi)準(zhǔn)確地進(jìn)行區(qū)分就
已經(jīng)完全足夠,。按照這個(gè)要求,，可以把所有錯(cuò)誤率低于50%的矩形特征都找到（適當(dāng)?shù)剡x擇閾值，對(duì)于固定的訓(xùn)練集,，幾乎所有的矩形特征都可以滿足上述要求）,。每輪訓(xùn)練，將選取當(dāng)輪中的最佳弱分類器（在算法中,，迭代T 次即是選擇T 個(gè)最佳弱分類器）,，最后將每輪得到的最佳弱分類器按照一定方法提升（Boosting）為強(qiáng)分類器

4 弱分類器的訓(xùn)練及選取

訓(xùn)練一個(gè)弱分類器（特征f）就是在當(dāng)前權(quán)重分布的情況下，確定f 的最優(yōu)閾值,，使得這個(gè)弱分類器（特征f）對(duì)所有訓(xùn)練樣本的分類誤差最低,。
選取一個(gè)最佳弱分類器就是選擇那個(gè)對(duì)所有訓(xùn)練樣本的分類誤差在所有弱分類器中最低的那個(gè)弱分類器（特征）。

對(duì)于每個(gè)特征 f,，計(jì)算所有訓(xùn)練樣本的特征值，并將其排序,。通過掃描一遍排好序的特征值,，可以為這個(gè)特征確定一個(gè)最優(yōu)的閾值，從而訓(xùn)練成一個(gè)弱分類器,。具體來(lái)說(shuō),，對(duì)排好序的表中的每個(gè)元素，計(jì)算下面四個(gè)值：

5. 強(qiáng)分類器

注意,，這里所說(shuō)的T=200個(gè)弱分類器,，指的是非級(jí)聯(lián)的強(qiáng)分類器。若果是用級(jí)聯(lián)的強(qiáng)分類器,，則每個(gè)強(qiáng)分類器的弱分類器的個(gè)數(shù)會(huì)相對(duì)較少,。

一般學(xué)術(shù)界所說(shuō)的級(jí)聯(lián)分類器，都是指的是級(jí)聯(lián)強(qiáng)分類器,，一般情況有10個(gè)左右的強(qiáng)分類器,，每個(gè)強(qiáng)分類有10-20個(gè)弱分類器。當(dāng)然每一層的強(qiáng)分類器中弱分類器的個(gè)數(shù)可以不相等,，可以根據(jù)需要在前面的層少放一些弱分類器,，后面的層次逐漸的增加弱分類器的個(gè)數(shù)。

6. 圖像檢測(cè)過程

在對(duì)輸入圖像進(jìn)行檢測(cè)的時(shí)候,，一般輸入圖像都會(huì)比20*20的訓(xùn)練樣本大很多,。在Adaboost 算法中采用了擴(kuò)大檢測(cè)窗口的方法，而不是縮小圖片,。

為什么擴(kuò)大檢測(cè)窗口而不是縮小圖片呢,，在以前的圖像檢測(cè)中，一般都是將圖片連續(xù)縮小十一級(jí),，然后對(duì)每一級(jí)的圖像進(jìn)行檢測(cè),，最后在對(duì)檢測(cè)出的每一級(jí)結(jié)果進(jìn)行匯總,。然而，有個(gè)問題就是,，使用級(jí)聯(lián)分類器的AdaBoost的人臉檢測(cè)算法的速度非常的快,，不可能采用圖像縮放的方法，因?yàn)閮H僅是把圖像縮放11級(jí)的處理,，就要消耗一秒鐘至少,，已經(jīng)不能達(dá)到Adaboost 的實(shí)時(shí)處理的要求了。

因?yàn)镠aar特征具有與檢測(cè)窗口大小無(wú)關(guān)的特性（想要了解細(xì)節(jié)還要讀一下原作者的文獻(xiàn)）,，所以可以將檢測(cè)窗口進(jìn)行級(jí)別方法,。

在檢測(cè)的最初，檢測(cè)窗口和樣本大小一致,，然后按照一定的尺度參數(shù)（即每次移動(dòng)的像素個(gè)數(shù),，向左然后向下）進(jìn)行移動(dòng)，遍歷整個(gè)圖像,，標(biāo)出可能的人臉區(qū)域,。遍歷完以后按照指定的放大的倍數(shù)參數(shù)放大檢測(cè)窗口，然后在進(jìn)行一次圖像遍歷,；這樣不停的放大檢測(cè)窗口對(duì)檢測(cè)圖像進(jìn)行遍歷,，直到檢測(cè)窗口超過原圖像的一半以后停止遍歷。因?yàn)?整個(gè)算法的過程非?？?，即使是遍歷了這么多次，根據(jù)不同電腦的配置大概處理一幅圖像也就是幾十毫秒到一百毫秒左右,。

在檢測(cè)窗口遍歷完一次圖像后,，處理重疊的檢測(cè)到的人臉區(qū)域，進(jìn)行合并等操作,。