計(jì)算機(jī)視覺作業(yè)

計(jì)算機(jī)視覺作業(yè)姓名：學(xué)號(hào)： 學(xué)院：自動(dòng)化工程學(xué)院專業(yè)：控制工程基于AdaBoost算法的人臉檢測(cè)1引言PAC學(xué)習(xí)模型的提出，計(jì)算學(xué)習(xí)理論得到了很大的發(fā)展，從而使“學(xué)習(xí)”有了計(jì)算上的判定方法。PAC模型中提出了弱學(xué)習(xí)和強(qiáng)學(xué)習(xí)的概念，后來證明通過某種方法（后稱為Boosting）可以將弱學(xué)習(xí)提升為強(qiáng)學(xué)習(xí)——這使得訓(xùn)練機(jī)器學(xué)習(xí)來得更加方便。1995年，F(xiàn)reund和Schapire提出了AdaBoost算法。AdaBoost全稱為AdaptiveBoosting，作者說取名叫作AdaBoost是因?yàn)檫@個(gè)算法和以前的Boosting算法都不同（原先的Boosting算法需要預(yù)先知道假設(shè)的錯(cuò)誤率下限），它根據(jù)弱學(xué)習(xí)的反饋適應(yīng)性地（adaptively）調(diào)整假設(shè)的錯(cuò)誤率也就是說，AdaBoost算法不需要任何關(guān)于弱學(xué)習(xí)器性能的先驗(yàn)知識(shí)，加上它和原來Boosting算法的效率一樣，因此可以非常容易地應(yīng)用到實(shí)際問題中。AdaBoost算法提出后在機(jī)器學(xué)習(xí)領(lǐng)域受到了極大的關(guān)注，實(shí)驗(yàn)結(jié)果顯示無論是應(yīng)用于人造數(shù)據(jù)還是真實(shí)數(shù)據(jù)，AdaBoost都能顯著提高學(xué)習(xí)精度。2人臉檢測(cè)方法的性能評(píng)測(cè)2.1人臉圖像數(shù)據(jù)庫人臉圖像數(shù)據(jù)庫可用于人臉檢測(cè)的訓(xùn)練和測(cè)試。大部分的人臉檢測(cè)方法都需要人臉訓(xùn)練圖像數(shù)據(jù)，原先用于人臉識(shí)別實(shí)驗(yàn)的據(jù)庫現(xiàn)在都可以用來進(jìn)行人臉檢測(cè)的訓(xùn)練。通常人臉識(shí)別實(shí)驗(yàn)所采用的人臉庫不大，一般僅包括100幅左右的人臉圖像，如MIT庫、Yale庫、CMU庫等都是小型庫。卜表列出了常見的一些人臉識(shí)別圖像數(shù)據(jù)庫：表1常用的人臉圖像數(shù)據(jù)庫數(shù)據(jù)庫描述位置MIT共有16個(gè)人的臉，每個(gè)人有27幅在不同光線、不同尺度、不同頭部角度情況下的圖像/pub/imagesFERET收集了大量的男性、女性人臉，每張圖像包含了一張?zhí)囟ū砬榈娜四?humanid/feretUMIST分為20個(gè)主題，共564張圖像，每個(gè)主題包括從側(cè)面到正面的不同人臉姿態(tài)http://images.ee.umist.ac.uk/danny/database.htmlUniv.ofBern30個(gè)人的300張正面人臉（每人10張）ftp://ianftp.unibe.ch/pub/images/faceimages/

和150張側(cè)面人臉（每人5張）Yale在不同光照條件下，戴眼鏡的表情人臉AT&T(Olivetti)40個(gè)主題，每個(gè)主題10張圖像HarvardHarvard在不同光照條件下的剪裁好的人臉圖像/pub/facesM2VTS一個(gè)包含不同圖像序列的多態(tài)數(shù)據(jù)庫http://poseidon.csd.auth.gr/m2vts/index.htmlPurdueAR3276張?jiān)诓煌庹諚l件下的表情和有遮擋的人臉圖像/~aleix/aleix_face_db.html圖1典型的正面人臉圖像數(shù)據(jù)庫中的人臉圖像如圖1,就是MIT的一個(gè)典型的正面人臉數(shù)據(jù)庫中的圖像，圖像的尺寸都為20x20。本論文的檢測(cè)算法所用的訓(xùn)練圖像即為這個(gè)數(shù)據(jù)庫中的。由于不同研究任務(wù)的需要，必要時(shí)可以設(shè)計(jì)和建立具有特色的專用數(shù)據(jù)庫。2?2性能評(píng)測(cè)由于不同人臉庫所取得的圖像條件和質(zhì)量不同，因此不同的識(shí)別程序之間很難進(jìn)行比較。為促進(jìn)人臉識(shí)別算法的深入研究和實(shí)用化，美國國防部發(fā)起了人臉識(shí)別技術(shù)(FaceRecognitionTechnology，F(xiàn)ERET)工程，它包括一個(gè)通用人臉庫和一套通用測(cè)試標(biāo)準(zhǔn)，用于定期對(duì)各種人臉識(shí)別算法進(jìn)行性能測(cè)試，其分析測(cè)試結(jié)果對(duì)未來的工作起到了一定的指導(dǎo)作用。圖2左側(cè)為測(cè)試圖像，右側(cè)為檢測(cè)結(jié)果。不同的標(biāo)準(zhǔn)會(huì)導(dǎo)致不同的檢測(cè)結(jié)果對(duì)于人臉檢測(cè)來說，一般關(guān)注兩個(gè)指標(biāo)：人臉檢測(cè)率(DetectionRate)：在給定圖像中，檢測(cè)出來的人臉和人臉總數(shù)的比率。但是，“人臉”的定義并沒有統(tǒng)一標(biāo)準(zhǔn)，例如，如果一個(gè)人臉被遮擋，那么究竟遮擋了多大部分后，就能判定剩余部分不再是一個(gè)“人臉”？；錯(cuò)誤檢測(cè)數(shù)(FalseDetection)：有多少的非人臉被當(dāng)成是人臉檢測(cè)出來了。這個(gè)指標(biāo)非常重要，有些檢測(cè)算法可以給出甚至100%的檢測(cè)率，但是其錯(cuò)誤檢測(cè)的數(shù)量可能非常巨大。一個(gè)理想化完美的人臉檢測(cè)算法，應(yīng)該有100%的人臉檢測(cè)率和0錯(cuò)誤檢測(cè)數(shù)。現(xiàn)階段也許只有人的大腦有這個(gè)能力。雖然現(xiàn)在有很多檢測(cè)算法，但是它們中的大部分還沒有經(jīng)過大量的圖像數(shù)據(jù)集測(cè)試。而且，這些方法的實(shí)驗(yàn)結(jié)果大都是用不同的測(cè)試集得出的。即使采用了相同的訓(xùn)練集和測(cè)試集，由于研究者對(duì)“檢測(cè)成功”的看法不盡相同，使得檢測(cè)率的標(biāo)準(zhǔn)不唯一，也會(huì)導(dǎo)致對(duì)不同檢測(cè)算法評(píng)測(cè)的困難。如圖4,假設(shè)右圖中的所有子圖像都被檢測(cè)器認(rèn)為是人臉，那么一個(gè)寬泛的標(biāo)準(zhǔn)會(huì)認(rèn)為檢測(cè)到的這所有的人臉都是成功的，但是一個(gè)嚴(yán)格標(biāo)準(zhǔn)可能認(rèn)為這些檢測(cè)到的人臉有很多是錯(cuò)誤的。為了公平地比較和評(píng)價(jià)這些方法，也有必要像FERET一樣定義一套標(biāo)準(zhǔn)的測(cè)試數(shù)據(jù)集和測(cè)試方法。3PAC學(xué)習(xí)模型3.1概述可學(xué)習(xí)理論可以分為統(tǒng)計(jì)學(xué)習(xí)理論和計(jì)算學(xué)習(xí)理論兩大部分。統(tǒng)計(jì)學(xué)習(xí)理論與經(jīng)驗(yàn)過程有著密切的聯(lián)系，而計(jì)算學(xué)習(xí)理論是概率理論中發(fā)展比較成熟的一個(gè)重要分支，它主要用于處理在實(shí)驗(yàn)的基礎(chǔ)上進(jìn)行的各種量的估計(jì)，研究當(dāng)采樣越來越多的時(shí)候，這些估計(jì)值是否收斂到未知的真值的問題，它的理論基礎(chǔ)主要是概率理論；計(jì)算學(xué)習(xí)理論主要研究如何構(gòu)造有效的學(xué)習(xí)算法以及討論學(xué)習(xí)算法的計(jì)算復(fù)雜性問題。PAC（ProbablyApproximatelyCorrect）模型是計(jì)算學(xué)習(xí)理論中常用的模型，它是由Valiant于1984年首先提出來的。這篇論文認(rèn)為“學(xué)習(xí)”是當(dāng)明顯清晰的過程或模式不存在時(shí)仍能獲取知識(shí)的一種“過程”，并給出了一個(gè)從計(jì)算角度來獲得這種“過程”的方法，這種方法包括：（1）適當(dāng)信息收集機(jī)制的選擇；（2）學(xué)習(xí)的協(xié)定；（3）對(duì)能在合理步驟內(nèi)完成學(xué)習(xí)的概念的分類。雖然內(nèi)在的算法復(fù)雜性限制了能夠?qū)W習(xí)的概念的范圍，論文仍然給出了一些有現(xiàn)實(shí)意義的，重要的，能夠?qū)W習(xí)的概念例子。PAC學(xué)習(xí)的實(shí)質(zhì)就是在樣本訓(xùn)練的基礎(chǔ)上，使算法的輸出以概率接近未知的目標(biāo)概念。PAC學(xué)習(xí)模型是考慮樣本復(fù)雜度及計(jì)算復(fù)雜度2的一個(gè)基本框架，成功的學(xué)習(xí)被定義為形式化的概率理論。3.2弱學(xué)習(xí)與強(qiáng)學(xué)習(xí)如何根據(jù)觀測(cè)數(shù)據(jù)來學(xué)習(xí)并得到精確的假設(shè)是機(jī)器學(xué)習(xí)領(lǐng)域中人們非常關(guān)注的一個(gè)問題，機(jī)器學(xué)習(xí)的一個(gè)重要目標(biāo)就是對(duì)新的樣本盡可能給出精確的估計(jì)。隨機(jī)猜測(cè)一個(gè)是或否的問題，將會(huì)有50%的正確率。如果一個(gè)假設(shè)能夠稍微地提高猜測(cè)正確的概率，那么這個(gè)假設(shè)就是弱學(xué)習(xí)算法，得到這個(gè)算法的過程稱為弱學(xué)習(xí)?？梢允褂冒胱詣?dòng)化的方法為好幾個(gè)任務(wù)構(gòu)造弱學(xué)習(xí)算法，構(gòu)造過程需要數(shù)量巨大的假設(shè)集合，這個(gè)假設(shè)集合是基于某些簡單規(guī)則的組合和對(duì)樣本集的性能評(píng)估而生成的。如果一個(gè)假設(shè)能夠顯著地提高猜測(cè)正確的概率，那么這個(gè)假設(shè)就稱為強(qiáng)學(xué)習(xí)。生成只比隨機(jī)猜測(cè)好一點(diǎn)的弱學(xué)習(xí)算法很容易，但是構(gòu)造一個(gè)強(qiáng)學(xué)習(xí)算法卻是一件相當(dāng)困難的事情。Kearns提出了弱學(xué)習(xí)算法與強(qiáng)學(xué)習(xí)算法間的等價(jià)問題一一是否能把弱學(xué)習(xí)算法轉(zhuǎn)化為強(qiáng)學(xué)習(xí)算法。如果兩者等價(jià)，則只需要找到一個(gè)弱學(xué)習(xí)算法就可以直接將其提升為強(qiáng)學(xué)習(xí)算法。Kearns和Valiant證明：只要有足夠的數(shù)據(jù)，弱學(xué)習(xí)算法就能通過集成的方式生成任意高精度的假設(shè)（強(qiáng)學(xué)習(xí)方法）。4Boosting方法Boosting原意為提升、加強(qiáng)。現(xiàn)在一般指的是將弱學(xué)習(xí)算法提升為強(qiáng)學(xué)習(xí)算法的一類算法。Boosting算法是在Kearns和Valiant證明后才真正成熟起來的。1990年，Schapire最先構(gòu)造出一種多項(xiàng)式級(jí)的算法，即最初的Boosting算法。這種算法可以將弱分類規(guī)則轉(zhuǎn)化成強(qiáng)分類規(guī)則。一年后，F(xiàn)reund提出了一種效率更高的Boosting算法。1993年，Drucker和Schapire第一次以神經(jīng)網(wǎng)絡(luò)作為弱學(xué)習(xí)器，應(yīng)用Boosting算法來解決實(shí)際的OCR問題。Boosting算法在分類、建模、圖像分割、數(shù)據(jù)挖掘等領(lǐng)域均已得到簡單而有效的應(yīng)用。1995年，F(xiàn)reund和Schapire提出的Adaboost，是對(duì)Boosting算法的一大提高。下面章節(jié)將逐步具體說明AdaBoost算法。

5.矩形特征本章節(jié)描述了對(duì)AdaBoost人臉檢測(cè)訓(xùn)練算法速度很重要的兩方面，特征的選取和特征值的計(jì)算。將矩形作為人臉檢測(cè)的特征向量，稱為矩形特征。本算法選取了最簡單的5個(gè)矩形特征模板進(jìn)行訓(xùn)練，以得到一套用于人臉檢測(cè)的最適合的矩形特征，事實(shí)證明，這種特征選取方法的訓(xùn)練速度雖然不快，但是檢測(cè)效率很高。Viola提出將積分圖(integralimage)應(yīng)用到特征值的計(jì)算之中。積分圖的引用，可以只對(duì)圖像進(jìn)行一次遍歷計(jì)算，就能夠在用常量時(shí)間完成每個(gè)特征值的計(jì)算，這使得訓(xùn)練和檢測(cè)的速度大大提升。在給定有限的數(shù)據(jù)情況下，基于特征的檢測(cè)能夠編碼特定區(qū)域的狀態(tài)，而且基于特征的系統(tǒng)比基于象素的系統(tǒng)要快得多。矩形特征對(duì)一些簡單的圖形結(jié)構(gòu)，比如邊緣、線段，比較敏感，但是其只能描述特定走向(水平、垂直、對(duì)角)的結(jié)構(gòu)，因此比較粗略。如圖3,臉部一些特征能夠由矩形特征簡單地描繪，例如，通常，眼睛要比臉頰顏色更深；鼻梁兩側(cè)要比鼻梁顏色要深；嘴巴要比周圍顏色更深。對(duì)于一個(gè)24X24檢測(cè)器，其內(nèi)的矩形特征數(shù)量超過160,000個(gè)，必須通過特定算法甄選合適的矩形特征，并將其組合成強(qiáng)分類器才能檢測(cè)人臉。到的與矩形特征的匹配。到的與矩形特征的匹配。6程序?qū)崿F(xiàn)及結(jié)果6.1樣本集AdaBoost算法效果如何的重點(diǎn)在于前期訓(xùn)練時(shí)候的弱分類器的選取，而弱分類器的選取在一定程度上依賴于樣本集的選取。因而訓(xùn)練樣本集顯得十分重要。在前面提到了一些圖像庫，最大最全的是FERET數(shù)據(jù)庫，但是其由美國軍方開發(fā)，在美國以外地區(qū)無法獲得。本文使用的是一套MIT的人臉訓(xùn)練樣本庫，共有樣本7,087個(gè)，其中人臉樣本2,706個(gè)，非人臉樣本4,381個(gè)。其中人臉圖像的示例參見圖3，非人臉圖像的示例參見圖4。?*.E?' E3H函茶■■垣蕓＜■必蘭圖4訓(xùn)練用的非正面人臉圖像這個(gè)樣本庫中的人臉樣本都是20X20像素、正面正向人臉，有同一個(gè)人的多種光照條件下的樣本。非人臉樣本尺寸和人臉樣本相同，是從圖像中隨機(jī)自動(dòng)截取的。這個(gè)樣本庫的將側(cè)面人臉、非正向人臉、有遮擋的人臉都?xì)w入了非人臉樣本。因此，依此樣本庫訓(xùn)練的強(qiáng)分類器只對(duì)正面正向人臉敏感。6.2訓(xùn)練難點(diǎn)及優(yōu)化6.2.1計(jì)算成本由于特征數(shù)量極其多，訓(xùn)練的時(shí)間和空間開銷特別大。在每輪循環(huán)中，都要計(jì)算所有樣本對(duì)所有特征的特征值，則需要運(yùn)算：78,460x7,087=556,046,020次在我的電腦上實(shí)測(cè)得到，上述運(yùn)算共花時(shí)675秒（11分鐘15秒）。為了訓(xùn)練200個(gè)弱分類器，則需要進(jìn)行200輪運(yùn)算，則共需要37.5小時(shí)。但這并不是最終的運(yùn)算時(shí)間，最終的運(yùn)算時(shí)間要加上每輪運(yùn)算中選擇最佳閾值所要進(jìn)行的排序、遍歷等運(yùn)算。時(shí)間的開銷是巨大的。因?yàn)橐粋€(gè)特征對(duì)一幅圖像的特征值是固定的，那么可以只運(yùn)行一次上述運(yùn)算，將得到的特征值結(jié)果都保存在硬盤上，這樣可以減少每次計(jì)算的時(shí)間開銷，需要的磁盤空間為（采用4字節(jié)的unsignedlong存儲(chǔ)）：556,046,020x4=2,224,184,080Bytes=2.07Gbytes空間開銷是巨大的。但是，對(duì)于一般的 PC機(jī)，硬盤的峰值讀取速度為66Mb/s，則讀取上述內(nèi)容的時(shí)間開銷仍有32秒。6.2.2減少矩形特征的數(shù)量為了提高訓(xùn)練速度，得從其他方面考慮。分析知道，除了算法效率外，影響運(yùn)算次數(shù)的因素只有訓(xùn)練集數(shù)量和特征數(shù)量，而訓(xùn)練集數(shù)量不可能減少，這樣會(huì)直接影響最后得到的強(qiáng)分類器效果；因此必須得減少特征數(shù)量才能減少訓(xùn)練時(shí)間。對(duì)于特征數(shù)量的減少，主要有兩個(gè)途徑：第一是在特征生成階段人為剔出。例如，完全不必考慮寬度為一個(gè)像素的矩形特征，因?yàn)轱@然用這樣的特征計(jì)算特征值隨機(jī)性太大，不可能尋找到合適的閾值。這一步，特征數(shù)量可以減少6,520個(gè)，變成71,940個(gè)。又因?yàn)橛?xùn)練集的人臉特征都集中在中部，邊緣上的矩形特征的貢獻(xiàn)不會(huì)特別大，因此可以適當(dāng)減少邊緣的矩形特征，例如不考慮涉及到邊緣1像素的矩形特征，則矩形特征的數(shù)量可以進(jìn)一步減少到46,953個(gè)。第二步是在訓(xùn)練過程中動(dòng)態(tài)地減少矩形特征。對(duì)于在訓(xùn)練中，閾值的選取對(duì)錯(cuò)誤率降低成效不大的那些矩形特征，被認(rèn)為是對(duì)人臉和非人臉區(qū)分能力很低的，可以設(shè)定一個(gè)錯(cuò)誤率范圍（逐輪改變），在每輪訓(xùn)練中按照這個(gè)范圍，對(duì)矩形特征進(jìn)行排除。進(jìn)行了上述處理后，運(yùn)算速度可以得到40%以上的提升。6.2.3樣本預(yù)處理為了減小圖像本身由于灰度分布12帶來造成的影響，需要對(duì)訓(xùn)練樣本做歸一化處理。對(duì)于MIT訓(xùn)練庫中的所有樣本，采用直方圖歸一化處理所有的樣本圖5樣本歸一化前后對(duì)比6.3檢測(cè)結(jié)果6.3.1檢測(cè)器用于檢測(cè)的圖像一般都大于子窗口20X20的分辨率。于是，在對(duì)一副圖像作檢測(cè)的時(shí)候需要從不同的尺度和不同的位置逐個(gè)檢測(cè)。對(duì)于不同尺度的檢測(cè)，我們選擇對(duì)檢測(cè)器進(jìn)行縮放而不是對(duì)圖像本身進(jìn)行縮放，因?yàn)樵谌魏纬叨认?，特征都可以用同樣的代價(jià)求出。我們的使用的檢測(cè)器基本大小為20X20，實(shí)驗(yàn)結(jié)果表明，檢測(cè)器每次放大1.25倍是最佳的。此外，檢測(cè)器還需要在不同的位置逐個(gè)檢測(cè)。每一次，檢測(cè)器平移k個(gè)象素；如果放大后的檢測(cè)器尺度為S，則檢測(cè)器窗口每次平移kS。這里，k的選擇非常重要，它既影響檢測(cè)的精度，又影響檢測(cè)的速度。如果k取的較大，檢測(cè)速度可以很快，但是同時(shí)很多人臉由于檢測(cè)器的移動(dòng)步長較大最終被忽略了；反之，如果k取的較小，雖然可能會(huì)提高檢測(cè)的精度，但是將使檢測(cè)速度大大降低。在實(shí)際檢測(cè)中，按照人臉結(jié)構(gòu)的“三庭五眼”準(zhǔn)則，選擇k=20X1=4。5由于檢測(cè)器對(duì)于尺度和位置上的微小變化不敏感，所以，對(duì)于同一張人臉，檢測(cè)結(jié)果中可能會(huì)把它檢測(cè)出很多次，因而我們需要對(duì)檢測(cè)結(jié)果進(jìn)行消減。消減的方法十分簡單：對(duì)于邊界有相交區(qū)域的檢測(cè)結(jié)果，對(duì)它們的四個(gè)頂點(diǎn)分別取平均值作為新的頂點(diǎn)，從而合成一個(gè)檢測(cè)結(jié)果。6.3.2實(shí)驗(yàn)結(jié)果首先與Viola實(shí)驗(yàn)的結(jié)果進(jìn)行了比較。Viola的結(jié)果

本文結(jié)果圖6與Viola實(shí)驗(yàn)結(jié)果比較1:總數(shù)15/漏檢0/錯(cuò)檢5Viola的結(jié)果本文結(jié)果圖7與Viola實(shí)驗(yàn)結(jié)果比較2：總數(shù)7/漏檢1/錯(cuò)檢4更多實(shí)驗(yàn)結(jié)果如下:圖8多人圖像檢測(cè)結(jié)果：總數(shù)14/漏檢2/錯(cuò)檢1圖9多人圖像檢測(cè)結(jié)果：總數(shù)6/漏檢1/錯(cuò)檢4圖10多人圖像檢測(cè)結(jié)果：總數(shù)卻漏檢0/錯(cuò)檢4

圖11不含人臉圖像檢測(cè)結(jié)果：總數(shù)0/漏檢0/錯(cuò)檢457結(jié)論Viola由于采用了層級(jí)處理方法，大大提高了檢測(cè)速度，在同一臺(tái)計(jì)算機(jī)上，對(duì)于384X288像素的圖像，檢測(cè)速度可以達(dá)到15幀/秒。本文的算法檢測(cè)384X288像素的圖像，約需要30秒，比Viola的層級(jí)處理方法慢了許多。另外，本方法的漏檢和錯(cuò)檢率還比較高。這只要是因?yàn)橛?xùn)練集數(shù)量太少，而且非人臉樣本比重偏低。事實(shí)上，世界上的非人臉樣式要遠(yuǎn)遠(yuǎn)大于人臉樣式，因此有足夠多的非人臉樣本，才能夠讓分類器對(duì)非人臉圖案的“分辨”能力大大提高。8Matlab源碼function[test_targets,E]=ada_boost(train_patterns,train_targets,test_patterns,params)%ClassifyusingtheAdaBoostalgorithm%Inputs:%train_patterns-Trainpatterns%train_targets-Traintargets%test_patterns-Testpatterns%Params-[NumberOfIterations,WeakLearnerType,Learner'sparameters]%%Outputs%test_targets-Predictedtargets%E -Errorsthroughtheiterations%%NOTE:Suitableforonlytwoclasses%[k_max,weak_learner,alg_param]=process_params(params);[Ni,M] =size(train_patterns);W =ones(1,M)/M;IterDisp=10;full_patterns =[train_patterns,test_patterns];test_targets =zeros(1,size(test_patterns,2));%DotheAdaBoostingfork=1:k_max,%TrainweaklearnerCkusingthedatasampledaccordingtoW:%...sosamplethe