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

1、第30卷第1期2007年1月計(jì)算機(jī)學(xué)報(bào)C HIN ESE J OU RNAL OF COM PU TERSJan.2007一種改進(jìn)的Ada Boost 算法AD Ada Boost李闖丁曉青吳佑壽(清華大學(xué)電子工程系北京100084A 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 detec

2、tion is one of t he mo st pop ular and important issues in t he 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

3、st adopt s a new met hod to acquire parameters.The weighted parame 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 e

4、nd ,so it is more adaptive to t he object detection based on cascade 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)檢測(cè)問題是計(jì)算機(jī)視覺領(lǐng)域最普遍和關(guān)鍵的問題之一.在很多情況下,人們往往只

5、關(guān)心觀測(cè)信號(hào)中某些特定的目標(biāo),比如雷達(dá)信號(hào)中敵方飛機(jī)的信號(hào);觀測(cè)圖像中的文字或者人臉等等.因此尋找準(zhǔn)確快速的目標(biāo)檢測(cè)算法一直受到研究者們的廣泛關(guān)注.在目標(biāo)檢測(cè)問題中,代表目標(biāo)信號(hào)的正樣本和代表背景信號(hào)的負(fù)樣本在概率分布上是極度不均衡的,兩者在重要性上也存在差異,這使得目標(biāo)檢測(cè)問題可以被看作是一個(gè)非對(duì)稱的兩類分類問題.由于問題的非對(duì)稱性,在設(shè)計(jì)分類器時(shí),整體的分類錯(cuò)誤率不再是決定性的指標(biāo),必須對(duì)正負(fù)樣本的分類錯(cuò)誤率分別加以考慮.另外,在對(duì)分類器進(jìn)行學(xué)習(xí)的過程中,容易得到足夠的代表檢測(cè)目標(biāo)的正訓(xùn)練樣本,但卻難以得到能代表各種背景信號(hào)的足夠的負(fù)樣本集合,負(fù)樣本的匱乏增加了分類器學(xué)習(xí)和訓(xùn)練的困難.針對(duì)

6、目標(biāo)檢測(cè)問題的特點(diǎn),研究者們采用了多種學(xué)習(xí)算法進(jìn)行了嘗試.Papageorgiou采用基于冗余小波特征的支持向量機(jī)(SVM來(lái)構(gòu)建檢測(cè)算法1.Schneiderman提出了一個(gè)基于多尺度小波變換的貝葉斯分類器來(lái)進(jìn)行檢測(cè)2.Rowley在人臉檢測(cè)系統(tǒng)中使用的是神經(jīng)網(wǎng)絡(luò)的方法3.Viola和Jones則提出了一個(gè)基于級(jí)聯(lián)結(jié)構(gòu)的AdaBoost分類器4,級(jí)聯(lián)結(jié)構(gòu)由多級(jí)分類器組成,每一級(jí)的分類器都采用AdaBoo st算法進(jìn)行訓(xùn)練.對(duì)比其它的算法,Viola和Jones所提出的基于級(jí)聯(lián)結(jié)構(gòu)的AdaBoo st算法在解決實(shí)際應(yīng)用問題時(shí)更為有效.該算法在人臉檢測(cè)的研究中被廣泛地加以采用,取得了很好的結(jié)果.該

7、算法通過AdaBoost學(xué)習(xí)算法將多個(gè)弱分類器集成得到一個(gè)強(qiáng)分類器,具備很強(qiáng)的泛化能力,保證了算法的穩(wěn)定性.同時(shí),由于采取了級(jí)聯(lián)結(jié)構(gòu),大多數(shù)的負(fù)樣本都在前面比較簡(jiǎn)單的級(jí)次中被濾除,提高了檢測(cè)的速度.級(jí)聯(lián)結(jié)構(gòu)還提供了方便的采集負(fù)訓(xùn)練樣本的方法,將前面級(jí)次中誤識(shí)的負(fù)樣本作為下一個(gè)級(jí)次分類器的負(fù)訓(xùn)練樣本.正因?yàn)榛诩?jí)聯(lián)結(jié)構(gòu)的AdaBoo st算法的這些特點(diǎn)符合目標(biāo)檢測(cè)問題的要求,所以在實(shí)踐中取得了成功.Viola等在人臉檢測(cè)中采用了傳統(tǒng)的AdaBoo st 算法,其訓(xùn)練過程中參數(shù)的選擇準(zhǔn)則是訓(xùn)練集錯(cuò)誤率上界的最小化.但是,錯(cuò)誤率上界的最小化并不能保證錯(cuò)誤率的最小化.因而,AdaBoo st分類器實(shí)際

8、上并不是最小錯(cuò)誤率的分類器.因此,仍然有可能對(duì)其進(jìn)行改進(jìn),以獲得更好的錯(cuò)誤率性能.更重要的是,傳統(tǒng)的AdaBoost算法是基于對(duì)稱的兩類分類問題的,正樣本的錯(cuò)誤率FR R和負(fù)樣本的錯(cuò)誤率FA R在訓(xùn)練過程中處于平等的地位,而在目標(biāo)檢測(cè)問題通常采用的級(jí)聯(lián)結(jié)構(gòu)中,這樣的假設(shè)不再成立.對(duì)于一個(gè)具有5個(gè)級(jí)次的級(jí)聯(lián)結(jié)構(gòu)分類器來(lái)說(shuō),如果每一級(jí)的FR R和FA R均為10%,那么最后整體級(jí)聯(lián)結(jié)構(gòu)的FR R和FA R分別為41%(1-01950141和01001%(0115= 0100001.顯然,FR R這么高的分類器是無(wú)法滿足檢測(cè)要求的.在級(jí)聯(lián)結(jié)構(gòu)中,要達(dá)到整體分類器對(duì)FR R的要求,每一級(jí)的分類器必須具

9、有很低的FR R,而FA R的目標(biāo)則通過增加級(jí)數(shù)來(lái)實(shí)現(xiàn).為了在保證FR R的前提下使用較少的級(jí)數(shù)獲得理想的FA R,就要使得每級(jí)的分類器在低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)檢測(cè)問題中所使用的級(jí)聯(lián)結(jié)構(gòu).AD AdaBoo st采用了新的弱分類器加權(quán)參數(shù)的求解算法,使得分類器在給定的低FR

10、R前提下對(duì)應(yīng)的FA R有明顯降低,從而改進(jìn)目標(biāo)檢測(cè)算法的性能.本文首先在第2節(jié)中對(duì)傳統(tǒng)的基于級(jí)聯(lián)結(jié)構(gòu)的AdaBoost分類器進(jìn)行簡(jiǎn)單的介紹;然后,在第3節(jié)介紹新的算法AD AdaBoo st,并且對(duì)它所取得的性能改善加以分析;最后是算法的實(shí)驗(yàn)結(jié)果和結(jié)論.2基于級(jí)聯(lián)結(jié)構(gòu)的Ada Boost分類器Viola提出的級(jí)聯(lián)結(jié)構(gòu)的分類器是指一組串行的分類器.在對(duì)待識(shí)樣本進(jìn)行分類時(shí),只有被前面一級(jí)的分類器判決為正的樣本才被送入后面的分類器繼續(xù)處理,反之則被認(rèn)為是負(fù)樣本直接輸出.最后,只有那些被每一級(jí)的分類器都判決為正的樣本才作為正樣本輸出.級(jí)聯(lián)結(jié)構(gòu)的示意圖如圖1所示 .圖1級(jí)聯(lián)結(jié)構(gòu)的示意圖在級(jí)聯(lián)結(jié)構(gòu)中,前面

11、幾級(jí)的分類器相對(duì)來(lái)說(shuō)結(jié)構(gòu)比較簡(jiǎn)單,使用的特征數(shù)也較少,但具有很高的檢測(cè)率,同時(shí)能夠盡可能地濾除那些與目標(biāo)差異較大的負(fù)樣本.后面級(jí)次的分類器則使用更多的特征和更復(fù)雜的結(jié)構(gòu),從而可以區(qū)分那些與目標(biāo)相似的負(fù)樣本.在實(shí)際的目標(biāo)檢測(cè)問題中,由于待檢測(cè)的正樣本通常在整體樣本中只占很小的比例,大部分的樣本在級(jí)聯(lián)結(jié)構(gòu)前端的分類器就會(huì)被濾除,只有少量的樣本需要通過所有級(jí)的分類器,因而級(jí)聯(lián)結(jié)構(gòu)大大地降低了運(yùn)算復(fù)雜度.在級(jí)聯(lián)結(jié)構(gòu)的分類器中,Viola和Jones采用AdaBoost算法來(lái)對(duì)每一級(jí)的分類器進(jìn)行訓(xùn)練.Ada2401計(jì)算機(jī)學(xué)報(bào)2007年Boo st算法的基本思想是將多個(gè)弱分類器集成成為一個(gè)強(qiáng)分類器.在訓(xùn)練

12、過程中,每個(gè)訓(xùn)練樣本被賦予一個(gè)初始權(quán)值,當(dāng)一個(gè)弱分類器訓(xùn)練完成后,根據(jù)其在訓(xùn)練集上的分類結(jié)果對(duì)所有的樣本權(quán)值進(jìn)行調(diào)整,使得下一次訓(xùn)練的弱分類器更關(guān)注那些被識(shí)別錯(cuò)誤的樣本.最后的強(qiáng)分類器的判決結(jié)果是所有弱分類器的判決結(jié)果的加權(quán)和.Viola4和Tu5分別在人臉檢測(cè)和文字檢測(cè)中采用基于級(jí)聯(lián)結(jié)構(gòu)的AdaBoost分類器,取得了較好的結(jié)果,證明了基于級(jí)聯(lián)結(jié)構(gòu)的AdaBoo st分類器在解決目標(biāo)檢測(cè)問題時(shí)是有效的.但是該算法仍然具有改進(jìn)的空間,后來(lái)的研究者也在其基礎(chǔ)上提出了很多新的修正.當(dāng)采用級(jí)聯(lián)結(jié)構(gòu)的AdaBoo st分類器解決目標(biāo)檢測(cè)問題時(shí),要滿足最后整個(gè)系統(tǒng)對(duì)FR R的要求,每級(jí)的分類器都要具有很

13、低的FR R.一般來(lái)說(shuō),在前面幾級(jí)的分類器中,要達(dá)到接近于0的FR R(即接近100%的檢測(cè)率,在后面級(jí)次的分類器中,由于正負(fù)樣本較難區(qū)分,所以對(duì)FR R的要求相應(yīng)地下降.此時(shí),級(jí)聯(lián)結(jié)構(gòu)中每級(jí)分類器判決閾值的選取不再是像傳統(tǒng)的兩類分類問題那樣選取對(duì)應(yīng)最小錯(cuò)誤率處的閾值,而是要調(diào)整到與符合要求的FR R 相對(duì)應(yīng).在這種情況下,基于最小錯(cuò)誤率上界的傳統(tǒng)AdaBoo st算法以及求解的加權(quán)參數(shù),在低FR R端并不一定能夠獲得好的性能.為了解決這個(gè)問題,研究者們提出了一些改進(jìn)的算法.AdaCo st6和Cost2Sensitive AdaBoost7采取類似的思路對(duì)樣本權(quán)值的更新過程進(jìn)行改進(jìn).在分類器

14、進(jìn)行訓(xùn)練時(shí),每次權(quán)值更新的過程中都偏重于提高正樣本的權(quán)值,這樣使得每個(gè)弱分類器對(duì)正樣本更加重視,從而改善低FR R端的性能.但是,這類算法的參數(shù)訓(xùn)練過程仍然是基于最小錯(cuò)誤率上界的,所以得到的改進(jìn)相對(duì)有限.3一種新的Ada Boost算法AD Ada Boost本文提出了一種新的AdaBoost算法AD AdaBoo st,它在判決閾值調(diào)整到對(duì)應(yīng)低FR R一端時(shí)能夠獲得比傳統(tǒng)AdaBoo st算法更好的性能,因而更加適用于目標(biāo)檢測(cè)問題中通常采用的級(jí)聯(lián)結(jié)構(gòu)分類器.下文首先對(duì)算法的流程進(jìn)行介紹,然后對(duì)它取得的改進(jìn)進(jìn)行分析.311AD Ada Boost算法流程新算法的流程為:1.給定標(biāo)定的訓(xùn)練樣本集

15、:(x1,y1,(x2,y2, (x m,y m,其中,x iX,y iY=-1,+1.2.對(duì)樣本權(quán)值進(jìn)行初始化:D1(i=1/m;3.循環(huán)t=1,2,T:t=h t(x iy iD t(i以及識(shí)別正確的正樣本的權(quán)值和p t=y i=1,h t(x i=1D t(i.t=12ln1-tt+ke p t,k為一個(gè)常數(shù),其取值滿足在本次循環(huán)中,令最小錯(cuò)誤率的上界下降.D t+1(i=D t(iZ te-t,h t(x i=y iet,h t(x iy i=D t(ie(-t y i h t(x iZ t,其中,Z t是歸一化因子,即Z t=iD t(ie(-t y i h t(x i.4.最后的強(qiáng)

16、分類器為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)的弱分類器中所有被識(shí)別正確的正樣本的權(quán)值和,它能夠代表弱分類器h t 對(duì)正樣本的識(shí)別能力.而ke p t是p t的增函數(shù),這樣求得的新的加權(quán)參數(shù),在錯(cuò)誤率t相同的情況下,那些對(duì)正樣本識(shí)別能力更強(qiáng)的弱分類器具有更大的權(quán)值.下文的理論分析和實(shí)驗(yàn)結(jié)果可以證明,采用上述參數(shù)求解方法的AD AdaBoost,應(yīng)用到目

17、標(biāo)檢測(cè)問題中能夠得到性能上的改進(jìn).5011期李闖等:一種改進(jìn)的AdaBoost算法AD AdaBoost312對(duì)AD Ada Boost 的分析AdaCo st 6,Asymmet ric AdaBoo st 8等算法通過改變樣本權(quán)值的更新過程來(lái)使訓(xùn)練算法更適應(yīng)目標(biāo)檢測(cè)問題的要求,而本文提出的新算法則通過改變?nèi)醴诸惼骷訖?quán)參數(shù)的求解方式來(lái)實(shí)現(xiàn)這一點(diǎn).本節(jié)對(duì)AD AdaBoo st 在性能上得到改進(jìn)的原因加以分析.前文已經(jīng)指出,在目標(biāo)檢測(cè)所采用的級(jí)聯(lián)結(jié)構(gòu)中,為了滿足FR R 的要求,要對(duì)判決閾值進(jìn)行調(diào)整.如圖2所示,閾值不再是對(duì)應(yīng)最小錯(cuò)誤率處的A 點(diǎn),而是要調(diào)整到B 點(diǎn),即min H (x i (

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

19、AdaBoost 算法中的權(quán)值有很大的提高.此時(shí)再考察H (x i 值較小的那些正樣本,上文已經(jīng)提到,循環(huán)早期權(quán)值較高的弱分類器對(duì)它們的識(shí)別能力較差.而采用新的算法后,后期對(duì)正樣本識(shí)別能力強(qiáng)的弱分類器由于權(quán)值上升比較大,并且對(duì)此類樣本更容易識(shí)別正確,因而能夠有效地彌補(bǔ)前面的弱分類器的不足,提高最后的加權(quán)和H (x i .如果與此同時(shí),負(fù)樣本的加權(quán)和H (x i 并不上升,或者上升的幅度較小,那么AD AdaBoost 就可以在相同的FR R 要求下獲得更小的FA R.下文證明AD AdaBoost 確實(shí)能夠通過改善樣本H (x i 值的分布來(lái)改進(jìn)分類器在訓(xùn)練集上的性能.令f (p t =k e

20、 pt .則新算法中樣本x i 對(duì)應(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,對(duì)于那些正樣本:y i =1H(x i =y i =1tf (p th t(x i=ty i =1f (p th t(x i=tf (p ty i =1h t(x i(3令N p 為訓(xùn)練集中正樣本的數(shù)量,N n 為訓(xùn)練集中負(fù)樣本的數(shù)量

21、,C t 為第t 次循環(huán)中正樣本的權(quán)值和.即C t =y i =1D t(i .那么可以得到在第t 次循環(huán)中,識(shí)別正確的正樣本數(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對(duì)于那些負(fù)樣本,同公式(3類似,可以求得y i =-1H(x i =tf (p ty i =-1h t(x i(6已知第t 個(gè)弱分類器的錯(cuò)誤率為t =h t (x i y iDt(

22、i ,即第t 個(gè)弱分類器識(shí)別錯(cuò)誤的樣本總數(shù)約為(N p +N n t ,其中識(shí)別錯(cuò)誤的正樣本數(shù)前文已經(jīng)給出,為N p -N pp tC t,則識(shí)別錯(cuò)誤的負(fù)樣本數(shù)為601計(jì)算機(jī)學(xué)報(bào)2007年(N p +N n t -N p -N p p tC t,因此,識(shí)別正確的負(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 p -N pp t C t1=2(N p +N n t -N p -N pp tC t-N n .在弱分類器的訓(xùn)練過

23、程中,能夠保證每個(gè)弱分類器的錯(cuò)誤率是小于015的,即t 015,那么根據(jù)上式可以得出y i =-1h t(x i2(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 i2N p tf (p t p tC t -015=y i =1H(x i (8通過上述分析以及式(8可以看出 ,AD Ada 2Boo st 對(duì)比傳統(tǒng)的AdaBoost 算法,正樣本和負(fù)樣本的H (x i 分布向兩側(cè)拉伸.這樣,在固定FR R 的要求下,就能夠獲得更低的FA R .

24、圖3給出了圖像中的文字檢測(cè)問題中分別采用傳統(tǒng)的AdaBoost 算法和新算法時(shí)H (x i 分布的對(duì)比.可以看到用實(shí)線表示的新算法的H (x i 分布對(duì)比傳統(tǒng)的AdaBoost 算法(用虛線表示有明顯的改善,因而在符合FR R 要求的閾值T h 處具有更低的FA R .圖3新舊算法H (x i 分布的對(duì)比313常數(shù)k 值的選取本小節(jié)將對(duì)新的參數(shù)求解公式(1中常數(shù)k 值的選取加以討論.從312節(jié)中的分析來(lái)看,較大的k 值對(duì)應(yīng)的H (x i 分布的拉伸效果更明顯,但是這并不說(shuō)明k 值越大對(duì)性能的改進(jìn)越有利.k 值過大會(huì)使得參數(shù)求解公式(1中的前一項(xiàng)重要性下降,從而使得分類器喪失對(duì)負(fù)樣本的識(shí)別能力.

25、Freund 和Schapire 在文獻(xiàn)9中已經(jīng)證明,AdaBoost 算法最小錯(cuò)誤率的上邊界為Tt =1Z t .新的算法沒有改變樣本權(quán)值的更新過程,所以最小錯(cuò)誤率的上邊界仍然是T t =1Z t.那么在考慮新算法中k 的取值時(shí),仍然要保證此時(shí)每個(gè)弱分類器對(duì)應(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 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 t1

26、,即e -f (p t +e f(p t1(1-t t(9當(dāng)f (p t =k e pt 時(shí),k 的取值要滿足在所有弱分類器中不等式(9成立.一般的,在訓(xùn)練完成某級(jí)弱分類器h t 后,對(duì)其對(duì)應(yīng)的Z t 進(jìn)行驗(yàn)證,滿足Z t 1的弱分類器才會(huì)被加入.當(dāng)取k =1/120時(shí),對(duì)應(yīng)的錯(cuò)誤率t 01494的弱分類器都可以滿足Z t 1.4實(shí)驗(yàn)結(jié)果自然景物圖像中的文字檢測(cè)問題是一個(gè)典型的目標(biāo)檢測(cè)問題,基于該問題對(duì)本文所提出的AD AdaBoost 算法進(jìn)行了實(shí)驗(yàn).在檢測(cè)過程中,采用1616的移動(dòng)窗口在不同尺度上對(duì)圖像進(jìn)行掃描,以確定文字的位置.對(duì)每個(gè)掃描窗口,使用AdaBoo st 分類器來(lái)對(duì)其是否是文

27、字進(jìn)行判決,分類器的訓(xùn)練算法分別是本文提出的新算法AD AdaBoost 和傳統(tǒng)的AdaBoo st 算法.因?yàn)槲淖植幌袢四樐菢泳哂邢嗨频膬?nèi)部結(jié)構(gòu),所以分類所使用的特征是與人臉檢測(cè)不同的直方圖特征.實(shí)驗(yàn)分別在訓(xùn)練集和測(cè)試集上進(jìn)行.正樣本是從自然景物圖像中的文字區(qū)域截取的,負(fù)樣本則是7011期李闖等:一種改進(jìn)的AdaBoost 算法AD AdaBoost108 計(jì) 算 機(jī) 學(xué) 報(bào) 2007 年 從非文字區(qū)域中隨機(jī)獲取的 . 訓(xùn)練集包括 10000 個(gè) 正樣本和 10000 個(gè)負(fù)樣本 , 測(cè)試集則包括 10000 個(gè) 正樣本和 20000 個(gè)負(fù)樣本 . 訓(xùn)練采用的特征是從 8784 維直方圖特征庫(kù)

28、中 選取的 . 對(duì)于級(jí)聯(lián)結(jié)構(gòu)的第一級(jí) ,選用 100 維特征各 自在 AD AdaBoo st 和傳統(tǒng)的 AdaBoo st 算法下訓(xùn)練 分類器 . 圖 4 給出了分別采用兩種算法在訓(xùn)練集和 測(cè)試集上對(duì)應(yīng)的 ROC 曲線 ,可以看出 , 在高檢測(cè)率 端 ,即 FR R 較低的一端 , 新算法的 FA R 性能得到 了改善 . 為了體現(xiàn) AD AdaBoo st 在低 FR R 端 FA R 的下降 ,圖中的 ROC 曲線截取的是對(duì)應(yīng)高檢測(cè)率 即 FR R 較小的部分 . 圖 4 ROC 曲線 ,為級(jí)聯(lián)結(jié)構(gòu)的第一級(jí)分類器確定閾值 , 使其滿足在訓(xùn)練集上的 FR R 為 01 1 %. 此時(shí) ,

29、表 1 給出 了 分 類 器 在 訓(xùn) 練 集 和 測(cè) 試 集 上 的 FR R 和 FA R . 可以看出 , 與傳統(tǒng)的 AdaBoo st 算法對(duì)比 ,AD AdaBoo st 在訓(xùn)練集上具有更低的 FA R , 其在測(cè)試 集上的 FR R 和 FA R 也有不同程度的改善 . 要 32 級(jí)才能夠滿足同樣的要求. 基于 AD AdaBoo st 的級(jí)聯(lián)結(jié)構(gòu)分類器由于具有較少的級(jí)數(shù) , 其運(yùn)算速 度更快 ,泛化能力也更強(qiáng) . 在對(duì)自然景物圖像中的文字進(jìn)行檢測(cè)的應(yīng)用系 統(tǒng)中 ,首先采用基于 AD AdaBoo st 的級(jí)聯(lián)結(jié)構(gòu)分類 器對(duì)掃描窗口進(jìn)行判決 , 然后對(duì)判決結(jié)果進(jìn)行合并 等操作以實(shí)現(xiàn)對(duì)

30、文字區(qū)域的檢測(cè)定位 . 圖 5 給出了 檢測(cè)的過程和結(jié)果 . 表1 新舊算法在訓(xùn)練集 FRR = 01 1 %時(shí)的實(shí)驗(yàn)結(jié)果對(duì)比 算法 訓(xùn)練集 測(cè)試集 FR R ( % FA R ( % FR R ( % FA R ( % 出的 AD AdaBoo st 算法對(duì)比傳統(tǒng)的 AdaBoo st 算法 具有更好的性能 . 當(dāng)采用 AD AdaBoo st 對(duì)圖像中文 字檢測(cè)所使用的級(jí)聯(lián)結(jié)構(gòu)分類器進(jìn)行訓(xùn)練時(shí) ,22 級(jí) 的分類器即可滿足檢測(cè)問題對(duì) FR R 和 FA R 的要 求 . 而若采用傳統(tǒng)的 AdaBoo st 算法進(jìn)行訓(xùn)練 ,則需 根據(jù)本文 31 2 節(jié)中對(duì)閾值調(diào)整的闡述和圖 4 的 AD A

31、daBoost AdaBoost 上述的實(shí)驗(yàn)結(jié)果說(shuō)明了 , 在低 FR R 端 , 本文提 01 10 01 10 461 51 521 38 01 82 01 90 651 20 701 45 圖 5 5 結(jié) 論 基于級(jí)聯(lián)結(jié)構(gòu)的 AdaBoo st 分類器是解決目標(biāo) 1期 李 闖等 : 一種改進(jìn)的 AdaBoo st 算法 AD AdaBoo st 2 109 檢測(cè)問題的有效途徑之一 . 但是 , 傳統(tǒng)的 AdaBoo st 算法是針對(duì)對(duì)稱的兩類分類問題的 , 其優(yōu)化目標(biāo)是 錯(cuò)誤率上界的最小化 ; 而目標(biāo)檢測(cè)是一個(gè)非對(duì)稱的 兩類分類問題 ,在采用級(jí)聯(lián)結(jié)構(gòu)時(shí) ,其對(duì)分類器的要 求是在低 FR

32、R 端 FA R 盡可能地小 . 因此 , 傳統(tǒng)的 AdaBoo st 算法仍需進(jìn)一步改進(jìn)才能更適應(yīng)目標(biāo)檢 測(cè)問題 . 本文提出了一種新的 AdaBoo st 算法 AD AdaBoo st . 該算法采用了更為有效的參數(shù)求解方 法 ,即弱分類器的加權(quán)參數(shù)不但與錯(cuò)誤率有關(guān) ,還與 其對(duì)正樣本的識(shí)別能力有關(guān) . AD AdaBoo st 能夠通 過改善樣本 H ( x i 值的分布有效地降低低 FR R 端 的 FA R ,使其更適用于目標(biāo)檢測(cè)問題的要求 . 實(shí)驗(yàn)結(jié)果證明了新算法對(duì)比傳統(tǒng)算法所取得的 性能改進(jìn) . 本文采用新算法訓(xùn)練基于級(jí)聯(lián)結(jié)構(gòu)的分 類器并將其應(yīng)用到自然景物圖像中的文字檢測(cè) ,

33、取 得了較好的結(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 f ramework ference on Co mp uter Vision. Bombay , India , 1998 : 5552562 for object detection/ / Pr

34、oceedings 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 t he National Nat ural Science Fo undation of China under grant No1 60472002 ( research on statisti

35、cal 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 comp uter visio n applicatio ns. AdaBoo st has low comp uta2 tio n complexity , simple st ruct ure as

36、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 rit hm is pop ular in t he research of object detectio n and has got many p romising result s. But so

37、 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 low false rejectio n rate end , which is much more impo rtant in t he object detetion. There are very

38、 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 AdaBoo st adopt s a different met hod to co mp ute t he weighted parameters of t he weak classifiers. T

39、hus 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 roblems. The experiment result s of text detection in images p rove t he im2 p rovement achieved by t

40、 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 of many co m2 p uter vision systems. DING Xiao2 Qing , born in 1939 , p rofesso r , Ph. D. su2 pervi

41、so 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 on Pattern Analysis and Ma2 chine Intelligence , 1998 , 20 (1 : 22238