一種改進(jìn)的AdaBoost算法_ADAdaBoost_圖文

1、第30卷第1期2007年1月計(jì)算機(jī)學(xué)報(bào)C HIN ESE J OU RNAL OF COM PU TERSVol.30No.1Jan.2007收稿日期:2004210222;修改稿收到日期:2006206211.本課題得到國家自然科學(xué)基金(60472002資助.李闖,男,1975年生,博士研究生,研究方向?yàn)槟Ｊ阶R別和計(jì)算機(jī)視覺等.E 2mail :lich ocrserv.ee.t .丁曉青,女,1939年生,教授,博士生導(dǎo)師,研究領(lǐng)域?yàn)橹悄軋D文信息處理、模式識別、圖像處理、文字識別等.吳佑壽,男,1925年生,教授,博士生導(dǎo)師,中國工程院院士,主要研究領(lǐng)域?yàn)閿?shù)字通信、數(shù)字信號處理和模式識別等

2、.一種改進(jìn)的Ada Boost 算法AD Ada Boost李闖丁曉青吳佑壽(清華大學(xué)電子工程系北京100084摘要目標(biāo)檢測問題是計(jì)算機(jī)視覺領(lǐng)域最普遍和關(guān)鍵的問題之一.基于級聯(lián)結(jié)構(gòu)的AdaBoost 算法目前被認(rèn)為是較有效的檢測算法,但是其在低FRR 端的性能仍需改進(jìn).文章提出了一種針對目標(biāo)檢測問題的改進(jìn)AdaBoost 算法AD AdaBoost.AD AdaBoost 采用了新的參數(shù)求解方法,弱分類器的加權(quán)參數(shù)不但與錯(cuò)誤率有關(guān),還與其對正樣本的識別能力有關(guān).該算法能夠有效地降低分類器在低FRR 端的FAR ,使其更適用于目標(biāo)檢測問題.新舊算法在復(fù)雜背景中文字檢測的實(shí)驗(yàn)結(jié)果對比證實(shí)了新算法在

3、性能上的改進(jìn).關(guān)鍵詞AD AdaBoost ;目標(biāo)檢測;級聯(lián)結(jié)構(gòu);弱分類器;加權(quán)參數(shù)中圖法分類號TP391A R evised Ada Boost Algorithm AD Ada BoostL I Chuang DIN G Xiao 2Qing WU Y ou 2Shou(Depart ment of Elect ronic Engineering ,Tsinghua Universit y ,Bei j ing 100084Abstract Object detection is one of t he mo st pop ular and important issues in t he

4、 domain of com 2p uter vision.AdaBoo st algorit hm based on cascade st ruct ure can solve t he p roblem effectively ,however it has it s own shortcoming.This paper p ropo ses a revised type of AdaBoost algorit hm ,AD AdaBoo st.AD AdaBoo st adopt s a new met hod to acquire parameters.The weighted par

5、ame 2ters of weak classifiers are determined not o nly by t he error rates ,but also by t heir abilities to recognize t he positive samples.The algorit hm can decrease t he classifiers false alarm rates in t he low false rejection rate end ,so it is more adaptive to t he object detection based on ca

6、scade struc 2t ure.The experiment result s p rove t he imp rovement achieved by t he new algorit hm.K eyw ords AD AdaBoost ;object detection ;cascade structure ;weak classifier ;weighted parameter1引言目標(biāo)檢測問題是計(jì)算機(jī)視覺領(lǐng)域最普遍和關(guān)鍵的問題之一.在很多情況下,人們往往只關(guān)心觀測信號中某些特定的目標(biāo),比如雷達(dá)信號中敵方飛機(jī)的信號;觀測圖像中的文字或者人臉等等.因此尋找準(zhǔn)確快速的目標(biāo)檢測算法一直受

7、到研究者們的廣泛關(guān)注.在目標(biāo)檢測問題中,代表目標(biāo)信號的正樣本和代表背景信號的負(fù)樣本在概率分布上是極度不均衡的,兩者在重要性上也存在差異,這使得目標(biāo)檢測問題可以被看作是一個(gè)非對稱的兩類分類問題.由于問題的非對稱性,在設(shè)計(jì)分類器時(shí),整體的分類錯(cuò)誤率不再是決定性的指標(biāo),必須對正負(fù)樣本的分類錯(cuò)誤率分別加以考慮.另外,在對分類器進(jìn)行學(xué)習(xí)的過程中,容易得到足夠的代表檢測目標(biāo)的正訓(xùn)練樣本,但卻難以得到能代表各種背景信號的足夠的負(fù)樣本集合,負(fù)樣本的匱乏增加了分類器學(xué)習(xí)和訓(xùn)練的困難.針對目標(biāo)檢測問題的特點(diǎn),研究者們采用了多種學(xué)習(xí)算法進(jìn)行了嘗試.Papageorgiou采用基于冗余小波特征的支持向量機(jī)(SVM來構(gòu)

8、建檢測算法1.Schneiderman提出了一個(gè)基于多尺度小波變換的貝葉斯分類器來進(jìn)行檢測2.Rowley在人臉檢測系統(tǒng)中使用的是神經(jīng)網(wǎng)絡(luò)的方法3.Viola和Jones則提出了一個(gè)基于級聯(lián)結(jié)構(gòu)的AdaBoost分類器4,級聯(lián)結(jié)構(gòu)由多級分類器組成,每一級的分類器都采用AdaBoo st算法進(jìn)行訓(xùn)練.對比其它的算法,Viola和Jones所提出的基于級聯(lián)結(jié)構(gòu)的AdaBoo st算法在解決實(shí)際應(yīng)用問題時(shí)更為有效.該算法在人臉檢測的研究中被廣泛地加以采用,取得了很好的結(jié)果.該算法通過AdaBoost學(xué)習(xí)算法將多個(gè)弱分類器集成得到一個(gè)強(qiáng)分類器,具備很強(qiáng)的泛化能力,保證了算法的穩(wěn)定性.同時(shí),由于采取了級

9、聯(lián)結(jié)構(gòu),大多數(shù)的負(fù)樣本都在前面比較簡單的級次中被濾除,提高了檢測的速度.級聯(lián)結(jié)構(gòu)還提供了方便的采集負(fù)訓(xùn)練樣本的方法,將前面級次中誤識的負(fù)樣本作為下一個(gè)級次分類器的負(fù)訓(xùn)練樣本.正因?yàn)榛诩壜?lián)結(jié)構(gòu)的AdaBoo st算法的這些特點(diǎn)符合目標(biāo)檢測問題的要求,所以在實(shí)踐中取得了成功.Viola等在人臉檢測中采用了傳統(tǒng)的AdaBoo st 算法,其訓(xùn)練過程中參數(shù)的選擇準(zhǔn)則是訓(xùn)練集錯(cuò)誤率上界的最小化.但是,錯(cuò)誤率上界的最小化并不能保證錯(cuò)誤率的最小化.因而,AdaBoo st分類器實(shí)際上并不是最小錯(cuò)誤率的分類器.因此,仍然有可能對其進(jìn)行改進(jìn),以獲得更好的錯(cuò)誤率性能.更重要的是,傳統(tǒng)的AdaBoost算法是基于

10、對稱的兩類分類問題的,正樣本的錯(cuò)誤率FR R和負(fù)樣本的錯(cuò)誤率FA R在訓(xùn)練過程中處于平等的地位,而在目標(biāo)檢測問題通常采用的級聯(lián)結(jié)構(gòu)中,這樣的假設(shè)不再成立.對于一個(gè)具有5個(gè)級次的級聯(lián)結(jié)構(gòu)分類器來說,如果每一級的FR R和FA R均為10%,那么最后整體級聯(lián)結(jié)構(gòu)的FR R和FA R分別為41%(1-01950141和01001%(0115= 0100001.顯然,FR R這么高的分類器是無法滿足檢測要求的.在級聯(lián)結(jié)構(gòu)中,要達(dá)到整體分類器對FR R的要求,每一級的分類器必須具有很低的FR R,而FA R的目標(biāo)則通過增加級數(shù)來實(shí)現(xiàn).為了在保證FR R的前提下使用較少的級數(shù)獲得理想的FA R,就要使得每

11、級的分類器在低FR R的條件下,FA R 盡可能地小,而不再是像傳統(tǒng)的AdaBoost算法那樣追求錯(cuò)誤率上界的最小化.優(yōu)化目標(biāo)的變化使得傳統(tǒng)AdaBoo st的參數(shù)選擇方案不再那么有效.為此,本文在AdaBoost的基礎(chǔ)上提出了一種新的算法AD(Adaptive to DetectionAdaBoo st.這種算法比傳統(tǒng)的AdaBoo st算法更適合于目標(biāo)檢測問題中所使用的級聯(lián)結(jié)構(gòu).AD AdaBoo st采用了新的弱分類器加權(quán)參數(shù)的求解算法,使得分類器在給定的低FR R前提下對應(yīng)的FA R有明顯降低,從而改進(jìn)目標(biāo)檢測算法的性能.本文首先在第2節(jié)中對傳統(tǒng)的基于級聯(lián)結(jié)構(gòu)的AdaBoost分類器進(jìn)

12、行簡單的介紹;然后,在第3節(jié)介紹新的算法AD AdaBoo st,并且對它所取得的性能改善加以分析;最后是算法的實(shí)驗(yàn)結(jié)果和結(jié)論.2基于級聯(lián)結(jié)構(gòu)的Ada Boost分類器Viola提出的級聯(lián)結(jié)構(gòu)的分類器是指一組串行的分類器.在對待識樣本進(jìn)行分類時(shí),只有被前面一級的分類器判決為正的樣本才被送入后面的分類器繼續(xù)處理,反之則被認(rèn)為是負(fù)樣本直接輸出.最后,只有那些被每一級的分類器都判決為正的樣本才作為正樣本輸出.級聯(lián)結(jié)構(gòu)的示意圖如圖1所示 .圖1級聯(lián)結(jié)構(gòu)的示意圖在級聯(lián)結(jié)構(gòu)中,前面幾級的分類器相對來說結(jié)構(gòu)比較簡單,使用的特征數(shù)也較少,但具有很高的檢測率,同時(shí)能夠盡可能地濾除那些與目標(biāo)差異較大的負(fù)樣本.后面

13、級次的分類器則使用更多的特征和更復(fù)雜的結(jié)構(gòu),從而可以區(qū)分那些與目標(biāo)相似的負(fù)樣本.在實(shí)際的目標(biāo)檢測問題中,由于待檢測的正樣本通常在整體樣本中只占很小的比例,大部分的樣本在級聯(lián)結(jié)構(gòu)前端的分類器就會被濾除,只有少量的樣本需要通過所有級的分類器,因而級聯(lián)結(jié)構(gòu)大大地降低了運(yùn)算復(fù)雜度.在級聯(lián)結(jié)構(gòu)的分類器中,Viola和Jones采用AdaBoost算法來對每一級的分類器進(jìn)行訓(xùn)練.Ada2401計(jì)算機(jī)學(xué)報(bào)2007年Boo st算法的基本思想是將多個(gè)弱分類器集成成為一個(gè)強(qiáng)分類器.在訓(xùn)練過程中,每個(gè)訓(xùn)練樣本被賦予一個(gè)初始權(quán)值,當(dāng)一個(gè)弱分類器訓(xùn)練完成后,根據(jù)其在訓(xùn)練集上的分類結(jié)果對所有的樣本權(quán)值進(jìn)行調(diào)整,使得下一

14、次訓(xùn)練的弱分類器更關(guān)注那些被識別錯(cuò)誤的樣本.最后的強(qiáng)分類器的判決結(jié)果是所有弱分類器的判決結(jié)果的加權(quán)和.Viola4和Tu5分別在人臉檢測和文字檢測中采用基于級聯(lián)結(jié)構(gòu)的AdaBoost分類器,取得了較好的結(jié)果,證明了基于級聯(lián)結(jié)構(gòu)的AdaBoo st分類器在解決目標(biāo)檢測問題時(shí)是有效的.但是該算法仍然具有改進(jìn)的空間,后來的研究者也在其基礎(chǔ)上提出了很多新的修正.當(dāng)采用級聯(lián)結(jié)構(gòu)的AdaBoo st分類器解決目標(biāo)檢測問題時(shí),要滿足最后整個(gè)系統(tǒng)對FR R的要求,每級的分類器都要具有很低的FR R.一般來說,在前面幾級的分類器中,要達(dá)到接近于0的FR R(即接近100%的檢測率,在后面級次的分類器中,由于正負(fù)

15、樣本較難區(qū)分,所以對FR R的要求相應(yīng)地下降.此時(shí),級聯(lián)結(jié)構(gòu)中每級分類器判決閾值的選取不再是像傳統(tǒng)的兩類分類問題那樣選取對應(yīng)最小錯(cuò)誤率處的閾值,而是要調(diào)整到與符合要求的FR R 相對應(yīng).在這種情況下,基于最小錯(cuò)誤率上界的傳統(tǒng)AdaBoo st算法以及求解的加權(quán)參數(shù),在低FR R端并不一定能夠獲得好的性能.為了解決這個(gè)問題,研究者們提出了一些改進(jìn)的算法.AdaCo st6和Cost2Sensitive AdaBoost7采取類似的思路對樣本權(quán)值的更新過程進(jìn)行改進(jìn).在分類器進(jìn)行訓(xùn)練時(shí),每次權(quán)值更新的過程中都偏重于提高正樣本的權(quán)值,這樣使得每個(gè)弱分類器對正樣本更加重視,從而改善低FR R端的性能.但

16、是,這類算法的參數(shù)訓(xùn)練過程仍然是基于最小錯(cuò)誤率上界的,所以得到的改進(jìn)相對有限.3一種新的Ada Boost算法AD Ada Boost本文提出了一種新的AdaBoost算法AD AdaBoo st,它在判決閾值調(diào)整到對應(yīng)低FR R一端時(shí)能夠獲得比傳統(tǒng)AdaBoo st算法更好的性能,因而更加適用于目標(biāo)檢測問題中通常采用的級聯(lián)結(jié)構(gòu)分類器.下文首先對算法的流程進(jìn)行介紹,然后對它取得的改進(jìn)進(jìn)行分析.311AD Ada Boost算法流程新算法的流程為:1.給定標(biāo)定的訓(xùn)練樣本集:(x1,y1,(x2,y2, (x m,y m,其中,x iX,y iY=-1,+1.2.對樣本權(quán)值進(jìn)行初始化:D1(i=1

17、/m;3.循環(huán)t=1,2,T:3.1.在當(dāng)前的分布D t下,針對每個(gè)單特征訓(xùn)練一個(gè)弱分類器,并從中選取錯(cuò)誤率最小的一個(gè)作為此次循環(huán)的弱分類器h t;3.2.對選定的h t:XY,計(jì)算加權(quán)錯(cuò)誤率:t=h t(x iy iD t(i以及識別正確的正樣本的權(quán)值和p t=y i=1,h t(x i=1D t(i.3.3.求解弱分類器h t的加權(quán)參數(shù)t=12ln1-tt+ke p t,k為一個(gè)常數(shù),其取值滿足在本次循環(huán)中,令最小錯(cuò)誤率的上界下降.3.4.為下次循環(huán)更新樣本權(quán)值D t+1(i=D t(iZ t×e-t,h t(x i=y iet,h t(x iy i=D t(ie(-t y i

18、h t(x iZ t,其中,Z t是歸一化因子,即Z t=iD t(ie(-t y i h t(x i.4.最后的強(qiáng)分類器為H(x=signTt=1t h t(x-T h,其中,T h是滿足FR R要求的判決閾值.新的算法采用了與傳統(tǒng)AdaBoost算法不同的加權(quán)參數(shù)的求解公式:t=12ln1-tt+ke p t(1其中,k為常數(shù),p t=y i=1,h t(x i=1D t(i.顯然,p t是第t次循環(huán)的弱分類器中所有被識別正確的正樣本的權(quán)值和,它能夠代表弱分類器h t 對正樣本的識別能力.而ke p t是p t的增函數(shù),這樣求得的新的加權(quán)參數(shù),在錯(cuò)誤率t相同的情況下,那些對正樣本識別能力更

19、強(qiáng)的弱分類器具有更大的權(quán)值.下文的理論分析和實(shí)驗(yàn)結(jié)果可以證明,采用上述參數(shù)求解方法的AD AdaBoost,應(yīng)用到目標(biāo)檢測問題中能夠得到性能上的改進(jìn).5011期李闖等:一種改進(jìn)的AdaBoost算法AD AdaBoost312對AD Ada Boost 的分析AdaCo st 6,Asymmet ric AdaBoo st 8等算法通過改變樣本權(quán)值的更新過程來使訓(xùn)練算法更適應(yīng)目標(biāo)檢測問題的要求,而本文提出的新算法則通過改變?nèi)醴诸惼骷訖?quán)參數(shù)的求解方式來實(shí)現(xiàn)這一點(diǎn).本節(jié)對AD AdaBoo st 在性能上得到改進(jìn)的原因加以分析.前文已經(jīng)指出,在目標(biāo)檢測所采用的級聯(lián)結(jié)構(gòu)中,為了滿足FR R 的要求,

20、要對判決閾值進(jìn)行調(diào)整.如圖2所示,閾值不再是對應(yīng)最小錯(cuò)誤率處的A 點(diǎn),而是要調(diào)整到B 點(diǎn),即min H (x i (y i 滿足y i =1附近.分布在B 點(diǎn)附近的正樣本,其H (x i 值較小的原因是早期選取的加權(quán)參數(shù)較大的弱分類器對它們的識別能力比較差,雖然它們的樣本權(quán)值因此得到提升,后面的弱分類器對它們的識別能力比較強(qiáng),但是由于后面的弱分類器對應(yīng)的加權(quán)參數(shù)通常都很小,所以最后的加權(quán)和H (x i 比較小 .圖2閾值調(diào)整的示意圖而采用了AD AdaBoo st 后,從式(1可以看出,弱分類器的加權(quán)參數(shù)不但與錯(cuò)誤率有關(guān),還與其對正樣本的識別能力有關(guān).在實(shí)際訓(xùn)練過程中,雖然后面循環(huán)中的弱分類器

21、通常錯(cuò)誤率都很高,接近50%,但是其中有的弱分類器仍然具有很強(qiáng)的對正樣本的識別能力.這樣,這些弱分類器的權(quán)值就比傳統(tǒng)AdaBoost 算法中的權(quán)值有很大的提高.此時(shí)再考察H (x i 值較小的那些正樣本,上文已經(jīng)提到,循環(huán)早期權(quán)值較高的弱分類器對它們的識別能力較差.而采用新的算法后,后期對正樣本識別能力強(qiáng)的弱分類器由于權(quán)值上升比較大,并且對此類樣本更容易識別正確,因而能夠有效地彌補(bǔ)前面的弱分類器的不足,提高最后的加權(quán)和H (x i .如果與此同時(shí),負(fù)樣本的加權(quán)和H (x i 并不上升,或者上升的幅度較小,那么AD AdaBoost 就可以在相同的FR R 要求下獲得更小的FA R.下文證明AD

22、 AdaBoost 確實(shí)能夠通過改善樣本H (x i 值的分布來改進(jìn)分類器在訓(xùn)練集上的性能.令f (p t =k e pt .則新算法中樣本x i 對應(yīng)的加權(quán)和H (x i 為H (x i =tt h t(x i =t12ln 1-tt+f (p t h t (x i =t12ln 1-tth t (x i +tf (p th t(x i(2式(2最右端的前一項(xiàng)仍然保持了傳統(tǒng)Ada 2Boo st 算法的形式,因而主要考察后一項(xiàng).令H (x i =tf (p th t(x i,對于那些正樣本:y i =1H(x i =y i =1tf (p th t(x i=ty i =1f (p th t(

23、x i=tf (p ty i =1h t(x i(3令N p 為訓(xùn)練集中正樣本的數(shù)量,N n 為訓(xùn)練集中負(fù)樣本的數(shù)量,C t 為第t 次循環(huán)中正樣本的權(quán)值和.即C t =y i =1D t(i .那么可以得到在第t 次循環(huán)中,識別正確的正樣本數(shù)量約為N pp tC t,則y i =1h t (x i =N p p tC t1+N p -N pp tC t(-1=N p 2p tC t-1(4將式(4代入式(3可以得到y(tǒng) i =1H(x i =tf (p ty i =1h t(x i=2N ptf (p t p tC t-015(5對于那些負(fù)樣本,同公式(3類似,可以求得y i =-1H(x i

24、 =tf (p ty i =-1h t(x i(6已知第t 個(gè)弱分類器的錯(cuò)誤率為t =h t (x i y iDt(i ,即第t 個(gè)弱分類器識別錯(cuò)誤的樣本總數(shù)約為(N p +N n t ,其中識別錯(cuò)誤的正樣本數(shù)前文已經(jīng)給出,為N p -N pp tC t,則識別錯(cuò)誤的負(fù)樣本數(shù)為601計(jì)算機(jī)學(xué)報(bào)2007年(N p +N n t -N p -N p p tC t,因此,識別正確的負(fù)樣本數(shù)為 N n -(N p +N n t -N p -N pp tC t.則y i =-1h t (x i =N n -(N p +N n t -N p - N p p tC t (-1+(N p +N n t -N

25、p -N pp t C t1=2(N p +N n t -N p -N pp tC t-N n .在弱分類器的訓(xùn)練過程中,能夠保證每個(gè)弱分類器的錯(cuò)誤率是小于015的,即t <015,那么根據(jù)上式可以得出y i =-1h t(x i<2(N p +N n 015-N p -N p p tC t-N n =2N pp tC t-015(7綜合式(5,(6和式(7,所以有y i =-1H(x i =tf (p ty i =-1h t(x i<2N p tf (p t p tC t -015=y i =1H(x i (8通過上述分析以及式(8可以看出 ,AD Ada 2Boo st

26、對比傳統(tǒng)的AdaBoost 算法,正樣本和負(fù)樣本的H (x i 分布向兩側(cè)拉伸.這樣,在固定FR R 的要求下,就能夠獲得更低的FA R .圖3給出了圖像中的文字檢測問題中分別采用傳統(tǒng)的AdaBoost 算法和新算法時(shí)H (x i 分布的對比.可以看到用實(shí)線表示的新算法的H (x i 分布對比傳統(tǒng)的AdaBoost 算法(用虛線表示有明顯的改善,因而在符合FR R 要求的閾值T h 處具有更低的FA R .圖3新舊算法H (x i 分布的對比313常數(shù)k 值的選取本小節(jié)將對新的參數(shù)求解公式(1中常數(shù)k 值的選取加以討論.從312節(jié)中的分析來看,較大的k 值對應(yīng)的H (x i 分布的拉伸效果更明

27、顯,但是這并不說明k 值越大對性能的改進(jìn)越有利.k 值過大會使得參數(shù)求解公式(1中的前一項(xiàng)重要性下降,從而使得分類器喪失對負(fù)樣本的識別能力.Freund 和Schapire 在文獻(xiàn)9中已經(jīng)證明,AdaBoost 算法最小錯(cuò)誤率的上邊界為Tt =1Z t .新的算法沒有改變樣本權(quán)值的更新過程,所以最小錯(cuò)誤率的上邊界仍然是T t =1Z t.那么在考慮新算法中k 的取值時(shí),仍然要保證此時(shí)每個(gè)弱分類器對應(yīng)的Z t <1,即在AD Ada 2Boo st 中,循環(huán)中每加入一個(gè)新的弱分類器還能保持最小錯(cuò)誤率上邊界Tt =1Z t 的下降.參考訓(xùn)練過程,能夠得到Z t =(1-t e -t +t e

28、 t=(1-t e -12ln1-tt+f (p t +t e12ln1-tt+f (p t =(1-t t (e-f (p t +e f(p t<1,即e -f (p t +e f(p t<1(1-t t(9當(dāng)f (p t =k e pt 時(shí),k 的取值要滿足在所有弱分類器中不等式(9成立.一般的,在訓(xùn)練完成某級弱分類器h t 后,對其對應(yīng)的Z t 進(jìn)行驗(yàn)證,滿足Z t <1的弱分類器才會被加入.當(dāng)取k =1/120時(shí),對應(yīng)的錯(cuò)誤率t <01494的弱分類器都可以滿足Z t <1.4實(shí)驗(yàn)結(jié)果自然景物圖像中的文字檢測問題是一個(gè)典型的目標(biāo)檢測問題,基于該問題對本文所

29、提出的AD AdaBoost 算法進(jìn)行了實(shí)驗(yàn).在檢測過程中,采用16×16的移動窗口在不同尺度上對圖像進(jìn)行掃描,以確定文字的位置.對每個(gè)掃描窗口,使用AdaBoo st 分類器來對其是否是文字進(jìn)行判決,分類器的訓(xùn)練算法分別是本文提出的新算法AD AdaBoost 和傳統(tǒng)的AdaBoo st 算法.因?yàn)槲淖植幌袢四樐菢泳哂邢嗨频膬?nèi)部結(jié)構(gòu),所以分類所使用的特征是與人臉檢測不同的直方圖特征.實(shí)驗(yàn)分別在訓(xùn)練集和測試集上進(jìn)行.正樣本是從自然景物圖像中的文字區(qū)域截取的,負(fù)樣本則是7011期李闖等:一種改進(jìn)的AdaBoost 算法AD AdaBoost108 計(jì) 算 機(jī) 學(xué) 報(bào) 2007 年 從非

30、文字區(qū)域中隨機(jī)獲取的 . 訓(xùn)練集包括 10000 個(gè) 正樣本和 10000 個(gè)負(fù)樣本 , 測試集則包括 10000 個(gè) 正樣本和 20000 個(gè)負(fù)樣本 . 訓(xùn)練采用的特征是從 8784 維直方圖特征庫中 選取的 . 對于級聯(lián)結(jié)構(gòu)的第一級 ,選用 100 維特征各 自在 AD AdaBoo st 和傳統(tǒng)的 AdaBoo st 算法下訓(xùn)練 分類器 . 圖 4 給出了分別采用兩種算法在訓(xùn)練集和 測試集上對應(yīng)的 ROC 曲線 ,可以看出 , 在高檢測率 端 ,即 FR R 較低的一端 , 新算法的 FA R 性能得到 了改善 . 為了體現(xiàn) AD AdaBoo st 在低 FR R 端 FA R 的下降

31、 ,圖中的 ROC 曲線截取的是對應(yīng)高檢測率 即 FR R 較小的部分 . 圖 4 ROC 曲線 ,為級聯(lián)結(jié)構(gòu)的第一級分類器確定閾值 , 使其滿足在訓(xùn)練集上的 FR R 為 01 1 %. 此時(shí) , 表 1 給出 了 分 類 器 在 訓(xùn) 練 集 和 測 試 集 上 的 FR R 和 FA R . 可以看出 , 與傳統(tǒng)的 AdaBoo st 算法對比 ,AD AdaBoo st 在訓(xùn)練集上具有更低的 FA R , 其在測試 集上的 FR R 和 FA R 也有不同程度的改善 . 要 32 級才能夠滿足同樣的要求. 基于 AD AdaBoo st 的級聯(lián)結(jié)構(gòu)分類器由于具有較少的級數(shù) , 其運(yùn)算速

32、度更快 ,泛化能力也更強(qiáng) . 在對自然景物圖像中的文字進(jìn)行檢測的應(yīng)用系 統(tǒng)中 ,首先采用基于 AD AdaBoo st 的級聯(lián)結(jié)構(gòu)分類 器對掃描窗口進(jìn)行判決 , 然后對判決結(jié)果進(jìn)行合并 等操作以實(shí)現(xiàn)對文字區(qū)域的檢測定位 . 圖 5 給出了 檢測的過程和結(jié)果 . 表1 新舊算法在訓(xùn)練集 FRR = 01 1 %時(shí)的實(shí)驗(yàn)結(jié)果對比 算法 訓(xùn)練集 測試集 FR R ( % FA R ( % FR R ( % FA R ( % 出的 AD AdaBoo st 算法對比傳統(tǒng)的 AdaBoo st 算法 具有更好的性能 . 當(dāng)采用 AD AdaBoo st 對圖像中文 字檢測所使用的級聯(lián)結(jié)構(gòu)分類器進(jìn)行訓(xùn)練時(shí)

33、 ,22 級 的分類器即可滿足檢測問題對 FR R 和 FA R 的要 求 . 而若采用傳統(tǒng)的 AdaBoo st 算法進(jìn)行訓(xùn)練 ,則需 根據(jù)本文 31 2 節(jié)中對閾值調(diào)整的闡述和圖 4 的 AD AdaBoost AdaBoost 上述的實(shí)驗(yàn)結(jié)果說明了 , 在低 FR R 端 , 本文提 01 10 01 10 461 51 521 38 01 82 01 90 651 20 701 45 圖 5 5 結(jié) 論 基于級聯(lián)結(jié)構(gòu)的 AdaBoo st 分類器是解決目標(biāo) 1期 李 闖等 : 一種改進(jìn)的 AdaBoo st 算法 AD AdaBoo st 2 109 檢測問題的有效途徑之一 . 但是

34、, 傳統(tǒng)的 AdaBoo st 算法是針對對稱的兩類分類問題的 , 其優(yōu)化目標(biāo)是 錯(cuò)誤率上界的最小化 ; 而目標(biāo)檢測是一個(gè)非對稱的 兩類分類問題 ,在采用級聯(lián)結(jié)構(gòu)時(shí) ,其對分類器的要 求是在低 FR R 端 FA R 盡可能地小 . 因此 , 傳統(tǒng)的 AdaBoo st 算法仍需進(jìn)一步改進(jìn)才能更適應(yīng)目標(biāo)檢 測問題 . 本文提出了一種新的 AdaBoo st 算法 AD AdaBoo st . 該算法采用了更為有效的參數(shù)求解方 法 ,即弱分類器的加權(quán)參數(shù)不但與錯(cuò)誤率有關(guān) ,還與 其對正樣本的識別能力有關(guān) . AD AdaBoo st 能夠通 過改善樣本 H ( x i 值的分布有效地降低低 FR

35、 R 端 的 FA R ,使其更適用于目標(biāo)檢測問題的要求 . 實(shí)驗(yàn)結(jié)果證明了新算法對比傳統(tǒng)算法所取得的 性能改進(jìn) . 本文采用新算法訓(xùn)練基于級聯(lián)結(jié)構(gòu)的分 類器并將其應(yīng)用到自然景物圖像中的文字檢測 , 取 得了較好的結(jié)果 . 參 考 1 ject detection applied to faces and cars/ / Proceedings of t he tion. U SA , 2000 : 7462751 Press , 2002 : 131121318 3 4 5 6 7 8 文 獻(xiàn) 9 Papageorgiou C P , Oren M , Poggio T. A general

36、 f ramework ference on Co mp uter Vision. Bombay , India , 1998 : 5552562 for object detection/ / Proceedings of t he 6t h International Con2 L I Chuang , born in 1975 , Ph. D. candidate. His research interest s include pattern recognition and comp uter vision. Background This wo rk is suppo rted by

37、 t he National Nat ural Science Fo undation of China under grant No1 60472002 ( research on statistical based comp uter vision t heories , met hods and appli2 cations . This o bjective of t his wo rk is to imp rove t he well2known machine learning algo rit hm , AdaBoo st , which is widely used in co

38、mp uter visio n applicatio ns. AdaBoo st has low comp uta2 tio n complexity , simple st ruct ure as well as st ro ng generali2 zatio n ability. However , t here is still a lot of works need to be done to imp rove t he AdaBoo st algo rit hm , especially in some special applicatio ns. AdaBoo st algo r

39、it hm is pop ular in t he research of object detectio n and has got many p romising result s. But so me fea2 t ures of Na ve AdaBoo st are not adaptive to t he object detec2 tio n p ro blems. The reason is t hat Na ve AdaBoo st interest in t he minimal error rate , but not t he false alarm rate at l

40、ow false rejectio n rate end , which is much more impo rtant in t he object detetion. There are very few effort s to solve t he p rob2 lem in mo st current research works. This app roach p ropo ses a revised type of AdaBoo st algo2 rit hm , AD AdaBoo st . Compared wit h t he Na ve AdaBoo st , AD Ada

41、Boo st adopt s a different met hod to co mp ute t he weighted parameters of t he weak classifiers. Thus t he algo2 rit hm can get lower false alarm rates at t he low false rejectio n rate end , so it has st ro nger classification abilities t han t he Na ve AdaBoo st facing t he o bject detection p r

42、oblems. The experiment result s of text detection in images p rove t he im2 p rovement achieved by t he given algorit hm. This algorit hm can be used in many o bject detectio n ap 2 plications , such as face detectio n , text detectio n , vehicle de2 tection , etc. It will imp rove t he performance

43、of many co m2 p uter vision systems. DING Xiao2 Qing , born in 1939 , p rofesso r , Ph. D. su2 perviso r. Her research interests include intelligent information p rocessing of images and documents , pattern recognition , im2 age processing and optical character recognition , etc. WU You2Shou , born in 1925 , p rofessor , Ph. D. super2 visor , member of Chinese Academy of Engineering. His re2 search interest s include digital communication , digital signal p rocessing and pattern recognitio n , etc. detection. IEEE Transactions o