面向分類錯誤率的自適應(yīng)FAST算法

任勝兵,謝如良

(中南大學(xué) 軟件學(xué)院,長沙 410075)

1 引 言

FAST[1,2](Feature from Accelerated Segment Test)算法是由Rosten、Porter和Drummond提出的一種新式簡單快速的特征點提取算法,該算法不僅能大大降低特征點的檢測時間,同時還能夠迅速排除大量非特征點,因此被廣泛應(yīng)用到圖像處理等實時系統(tǒng)中[3,4].

目前,在特征點提取領(lǐng)域中有大量的算法,如早期的SUSAN角點檢測算法和Plessey算法等.在這些經(jīng)典的特征提取算法之上,出現(xiàn)了大量的局部特征提取算法,如G.Lowe提出的尺度不變特征(scale invariant feature transform,SIFT)算法[5],該算法具有尺度旋轉(zhuǎn)、亮度變化、縮放的不變性,但是它的特征檢測計算量大,速度較慢,不適合實時應(yīng)用[6].文獻[7]提出了加速魯棒特征(Speeded-up Robust Feature,SURF)算法,它是SIFT算法的一種改進,提高了特征點的檢測速度,但是與FAST算法相比,速度還是相差較大.

近年來,FAST算法在實際應(yīng)用中有大量運用,如圖像配準[8]、機器人導(dǎo)航[9]、視覺跟蹤[10]等領(lǐng)域.在學(xué)術(shù)上FAST算法也有大量的研究成果,如S.Taylor等[11,12]改進了FAST算法,使之能快速匹配并更具魯棒性.但是FAST算法通常采用的閾值和半徑是固定的,對于不同的圖像,提取結(jié)果中會出現(xiàn)特征點冗余或者丟失的現(xiàn)象.例如,在多國紙幣冠字號識別研究中,由于不同幣種冠字號的字體和大小各異,因此FAST算法中固定的閾值與半徑無法適應(yīng)多種紙幣.

針對以上缺陷,本文基于AdaBoost[13,14]提出了AdaBoost_FAST算法,其中AdaBoost算法的基本原理是通過在每輪迭代中降低正確分類樣本的權(quán)重,增加錯誤分類樣本的權(quán)重,使得分類器在迭代過程中逐步改進,最終將所有分類器線性組合得到最終分類器.其中本文使用到的分類器為支持向量機(support vector machine,SVM)[15],該方法是機器學(xué)習(xí)中一種重要的算法,被廣泛應(yīng)用于解決模式識別中的分類和回歸分析問題中.本文根據(jù)AdaBoost算法的思想采用支持向量機進行訓(xùn)練,由分類器的錯誤率通過代價函數(shù)計算每組閾值和半徑的抽樣概率,當(dāng)錯誤率越低,其抽樣概率越大,對應(yīng)的閾值和半徑逐步接近最優(yōu)值,所提取的特征點精度越高.根據(jù)抽樣概率構(gòu)成的代價函數(shù)可知,經(jīng)過多次迭代以后,如果錯誤率較小并且無明顯變化,則表明此時的閾值和半徑已經(jīng)達到最優(yōu).通過本文實驗驗證,該算法在保證FAST算法時效性的同時,能夠有效地對閾值和半徑進行自適應(yīng)選擇,減少了特征點冗余或者丟失的情況,提高了特征點提取的精確度.

2 FAST特征點提取算法

FAST算法所提取的特征點通?？梢远x為:以r為半徑的某個像素點鄰域內(nèi),與該點處于不同灰度區(qū)域的像素點個數(shù)超過某一個閾值N,即有足夠多的像素點的灰度值大于或者小于該點的灰度值.FAST算法所涉及的像素點分布如圖1所示,中心點p為待判定像素點的像素值,當(dāng)半徑r為3時,周圍共有16個像素點.

雖然FAST算法在時間效率上相比其他算法有明顯的優(yōu)勢,但是由于其采用固定的閾值和半徑,對于不同圖像的特征點提取會出現(xiàn)冗余或者丟失的情況,導(dǎo)致提取的特征點精確度較低,難以取得良好的效果.例如在多國紙幣冠字號識別中,如圖2中所示,三種幣種冠字號的字體大小以及形狀存在明顯的差異.當(dāng)采用固定的閾值和半徑時,圖2(a)美元的特征點提取結(jié)果具有較高的代表性,并且精確度高.而圖2(b)中的比索由于其字體形狀較大,若采取同一閾值和半徑,則會出現(xiàn)特征點的冗余,導(dǎo)致特征點提取結(jié)果不精確并且影響時間效率.圖2(c)中,新西蘭元的字體形狀較小,采用此固定的閾值和半徑時,則會出現(xiàn)特征點的丟失情況,極大降低了特征點的提取精度.

3 AdaBoost_FAST算法

為了解決FAST算法中閾值和半徑不能自適應(yīng)的問題,本文提出了AdaBoost_FAST算法,其基本流程如圖3所示.

圖3 AdaBoost_FAST算法流程圖

AdaBoost_FAST算法的總體思路是依據(jù)分類器錯誤率來進行閾值和半徑的自適應(yīng)選擇,根據(jù)錯誤率通過一個代價函數(shù)計算每一組閾值和半徑的抽樣概率.錯誤率越高,說明在該組閾值和半徑下特征提取的效果較差,它的抽樣概率就會越小,反之則越大.因此最優(yōu)的閾值和半徑的抽樣概率將會逐漸變大,最終實現(xiàn)最優(yōu)閾值和半徑的自適應(yīng)選擇.

在此過程中,我們用變量Pt(j)表示第t次迭代的第j組閾值半徑的抽樣概率,它的初始值都設(shè)置為同一個值,意味著在第一輪迭代中所有的閾值和半徑的抽樣概率都是相同的.在每一輪迭代中,根據(jù)分類器的錯分率更新每對閾值和半徑的抽樣概率,其中分類器采用支持向量機(support vector machine,SVM)來進行訓(xùn)練.根據(jù)所有訓(xùn)練數(shù)據(jù)的分布Dt來計算每個分類器ft的錯分率,t是在第t輪迭代中選擇核函數(shù)k的分類器錯分率,如公式(1)所示:

t=

(1)

根據(jù)錯誤率計算并更新當(dāng)前組的閾值和半徑的抽樣概率,如公式(2)所示.其中γ∈(0,1)是一個不變的參數(shù),是更新閾值和半徑對抽樣概率的衰減系數(shù).Pt+1(j)是更新后第j組閾值和半徑的抽樣概率.從公式(2)分析可得,當(dāng)錯誤率越大,將會減小它在下一輪迭代的抽樣概率.

Pt+1(j)←Pt(j)γ

(2)

在第t輪迭代完成以后,對閾值和半徑的抽樣概率進行歸一化,如公式(3)所示,以確保抽樣概率在(0,1)之間.歸一化的步驟也是為了改變未被選擇閾值和半徑的抽樣概率,其中ZP是歸一化因子.

Pt+1(j)←Pt+1(j)/ZP,ZP=max(Pt+1+0.01)

(3)

當(dāng)錯誤率不再發(fā)生明顯變化并且錯誤率的值較小時(通常定義為錯誤率小于等于0.01),此時結(jié)束整個自適應(yīng)迭代的選擇過程,同時將此組中的閾值和半徑保存,該值即是最優(yōu)的閾值與半徑,如公式(4)所示:

ft=argmin
ftt=arg

(4)

根據(jù)AdaBoost算法的收斂性可知,在多次迭代以后,分類器的性能會逐漸改進,最終達到最優(yōu).針對本文算法的收斂性分析,由公式(2)知,γ∈(0,1),表明(2)式是一個減函數(shù).如果錯誤率t越大,則該閾值和半徑在下輪迭代中,其抽樣概率將會大大減小.如果錯誤率t越小,在下一輪的迭代中,其抽樣概率將會增大.因此在本文算法中,當(dāng)經(jīng)過多次迭代以后,分類器錯誤率越小的,說明提取的特征點的精確度越高,其對應(yīng)的閾值和半徑抽樣概率將會越趨近于1,算法中的最優(yōu)閾值和半徑最終將會收斂于錯誤率最小的分類器對應(yīng)的閾值和半徑.圖4描述了AdaBoost_FAST算法的偽代碼過程.

算法1.AdaBoost_FAST算法

INPUT:

訓(xùn)練樣本:(x1,y1),…,(xN,yN)

核函數(shù):k(·,·):X×X→

閾值半徑對:(n1,r1),…,(nT,rT)

初始化訓(xùn)練樣本的分布:D1(i)=1/N,i=1,…,N

初始化FAST算法中的閾值半徑對的概率分布:Ρ1(j)=0.8,j=1,…,T

FAST算法中參數(shù)抽樣衰減因子:0<γ<1

圖4 算法偽代碼

圖4算法偽代碼中,輸入為相關(guān)數(shù)據(jù)集和參數(shù)的初始化,輸出為最優(yōu)分類器以及最優(yōu)閾值和半徑.算法1的1至9步是進行閾值和半徑的最優(yōu)化選擇.其中第2至第3步是根據(jù)樣本的分布抽取n個樣本,根據(jù)抽樣概率隨機抽取一組閾值和半徑.第4步根據(jù)已獲得的閾值和半徑對樣本進行特征點提取.5到6步是訓(xùn)練分類器,并且計算訓(xùn)練錯誤率.第7步根據(jù)錯誤率更新閾值和半徑的抽樣概率.第8步即對抽樣概率進行歸一化操作.最后,進行T輪迭代后,如果滿足錯誤率無明顯變化且值小于給定的條件時,則結(jié)束整個迭代的過程.同時將此輪迭代中的閾值和半徑保存,該值即為最優(yōu)的閾值和半徑,最終實現(xiàn)閾值和半徑的自適應(yīng)選譯.

該算法在進行最優(yōu)閾值和半徑選擇的過程中,根據(jù)算法1第7步的公式可知,最優(yōu)的分類器所對應(yīng)的閾值和半徑的抽樣概概率最大.即該組值將會參加多次迭代,所以重復(fù)閾值和半徑的特征提取僅需操作一次,從而大大的減少了算法的運算量.在時間和空間效率上表現(xiàn)出了優(yōu)越的性能.

4 實驗結(jié)果與分析

4.1 實驗設(shè)置

為了驗證本文的AdaBoost_FAST算法能否有效地進行閾值和半徑的自適應(yīng)選擇,我們在MNIST數(shù)據(jù)集*http://yann.lecun.com/exdb/mnist/上進行了實驗驗證,MNIST數(shù)據(jù)集是來自美國國家標(biāo)準與技術(shù)研究所(NIST),其中訓(xùn)練集(training set)由來自250個不同人手寫的數(shù)字和字母構(gòu)成,其中50%是高中學(xué)生,50%來自人口普查局的工作人員.測試集也是同樣比例的手寫數(shù)字和字母.

在算法1中,首先給定閾值和半徑一個取值范圍,本實驗中,閾值的取值范圍為5～16,半徑取值范圍為1～5,閾值和半徑對的初始抽樣概率P1(j)都設(shè)定為0.8,訓(xùn)練樣本的初始化分布D1為均勻分布.為了在時間效率上達到最優(yōu)效果,我們根據(jù)經(jīng)驗將抽樣衰減因子γ初始值設(shè)為2-5.整個實驗將在Microsoft Windows xp(32位),2.7 GHz Intel CPU,4GB RAM的python3.5.1與opencv 3.0平臺進行,其中SVM將采用libsvm進行求解.

4.2 閾值和半徑自適應(yīng)實驗分析

4.2.1 閾值和半徑自適應(yīng)實驗1

本文首先采用了MNIST數(shù)據(jù)集中的12000個訓(xùn)練樣本.我們將按照字體大小將分成2組,一組為字體形狀較大的(A組),另外一組為字體形狀較小的(B組),由于大小不同的字體對應(yīng)的最優(yōu)閾值和半徑各不相同,因此分成兩組數(shù)據(jù)能夠有效的驗證本文算法的閾值和半徑自適應(yīng)選擇的性能.本文算法自適應(yīng)選擇最優(yōu)閾值和半徑的整個迭代過程如圖5所示.

圖5 閾值和半徑自適應(yīng)收斂過程

圖5中橫軸表示自適應(yīng)選擇最優(yōu)閾值和半徑過程中的迭代次數(shù),豎軸表示該次迭代經(jīng)過支持向量機訓(xùn)練所得到的分類器的錯誤率.每一次迭代根據(jù)錯誤率更新當(dāng)前組閾值和半徑的抽樣概率,當(dāng)?shù)揭欢ù螖?shù)以后,錯誤率較高的分類器所對應(yīng)的閾值和半徑的抽樣概率會逐漸變小,反之其抽樣概率將會變大.而錯誤率最小的分類器,其對應(yīng)的閾值和半徑的抽樣概率會逐漸趨于1.

如圖5中的A組實驗迭代到第13次時,已經(jīng)開始收斂于最優(yōu)值,此時最優(yōu)的閾值和半徑的抽樣概率已經(jīng)遠大于其他的閾值和半徑的抽樣概率,并且在后續(xù)迭代過程中分類器的錯誤率都保持在一個較小的值,說明在該組閾值和半徑下提取的特征點精確度高,因此該組閾值和半徑為最優(yōu)值.B組實驗的閾值和半徑的自適應(yīng)選擇過程和A組基本相同,B組在第12次迭代時已經(jīng)收斂于最優(yōu)閾值和半徑.其中AB兩組實驗1至20次迭代所對應(yīng)的閾值和半徑以及錯誤率如表1所示.AB兩組數(shù)據(jù)所取最優(yōu)閾值和半徑不同是由于A組字體形狀較大,字體內(nèi)部比較空曠,因此所采取的閾值和半徑較大,而B組字體形狀較小,只需要較小的閾值和半徑就能保證提取到關(guān)鍵的特征點.綜合兩組數(shù)據(jù),本文算法能夠有效的通過分類器錯誤率進行閾值和半徑的自適應(yīng)選擇,在選擇的最優(yōu)閾值和半徑下提取的特征點精確度高,不會出現(xiàn)特征點丟失或者冗余的現(xiàn)象.

表1 AB組實驗自適應(yīng)選擇過程中閾值半徑和錯誤率表

4.2.2 閾值和半徑自適應(yīng)實驗2

在4.2.1節(jié)的實驗中,將樣本分為字體大和字體小的兩組,是為了說明閾值和半徑的最優(yōu)值與不同類別的圖像是有關(guān)聯(lián)的.為了進一步驗證本文算法的自適應(yīng)性,本組實驗將不再按照字符的大小進行分組.而是將所有大小不同的手寫體字分為一組,然后進行實驗.從實驗結(jié)果中,挑選出五組不同大小的字符,其中每一組中的字體大小相近,獲取每一組的最優(yōu)閾值和半徑.得到的結(jié)果如表2所示.表2中,編號較小的組其字體較小,編號較大的組其字體較大.從表2的結(jié)果中分析可得,當(dāng)將所有大小不同的樣本混合進行實驗時,本文算法同樣能夠根據(jù)圖像字體大小的不同有效地自適應(yīng)選擇最優(yōu)的閾值和半徑.

表2 最優(yōu)閾值半徑和錯誤率表

在表2中,在字體較小時,即編號較小的組中,選擇的是較小的閾值和半徑.在字體較大的組中,根據(jù)FAST算法的原理,其最優(yōu)閾值和半徑應(yīng)該較大.同時每組在選擇出最優(yōu)閾值和半徑時,分類錯誤率也達到了較小.以上分析說明本文算法能夠有效的自適應(yīng)選擇出最優(yōu)閾值和半徑.

4.3 AdaBoost_FAST與FAST的比較

為了驗證本文算法在特征提取精度上的優(yōu)勢,本文在4.2實驗的基礎(chǔ)上,進行了兩次特征提取實驗.其中圖6中分別給出了FAST算法和AdaBoost_FAST算法提取的部分圖像的特征點分布圖,從圖6(a)中我們能夠發(fā)現(xiàn),當(dāng)A組(字體形狀較大)的圖像與B組(字體形狀較小)的圖像分別采用FAST算法固定的閾值和半徑時,圖6(a)中字體形狀較大的出現(xiàn)了特征點冗余,而字體形狀較小的出現(xiàn)了特征點丟失的情況.而在圖6(b)采用本文算法自適應(yīng)選取最優(yōu)的閾值和半徑時,提取的特征點數(shù)量少,代表性高,特征點提取精度高,沒有出現(xiàn)冗余的特征點,同時也沒有出現(xiàn)特征點丟失的現(xiàn)象.

圖6 部分圖像特征點分布圖

表3中的聚集率是衡量某一區(qū)域中是否有誤檢為特征點的一個指標(biāo),反應(yīng)了特征點的丟失和冗余程度.假設(shè)M為圖像中提取的總特征點數(shù),Mc為周圍聚集超過3個特征點的特征點總數(shù),則聚集率可表示為公式(5).當(dāng)c較大時,說明特征點存在冗余,如果c過小,即提取的特征點存在丟失的情況,根據(jù)實驗結(jié)果觀察所得c的值在百分之十左右時說明特征點的提取精確度高.

(5)

特征點重復(fù)率是表示算法的穩(wěn)定性以及魯棒性,假設(shè)在第一次實驗與第二次實驗中提取的特征點數(shù)分別為M1與M2,在第二次實驗中提取到的特征點中與第一次實驗中提取的特征點相重合的個數(shù)記為Mr,則特征點重復(fù)率的表達式如公式(6)所示,通常特征點重復(fù)率越高表示算法的穩(wěn)定性越好.

(6)

表3中分別給出了本文算法以及FAST算法提取特征點的性能分析對比情況,其中源圖像都相同,分別來自AB兩組不同的十幅圖像.從表3中可知,采用本文算法得到的特征點聚集率適中,提取精確度高,不會出現(xiàn)特征點丟失以及冗余的情況.而在表3采用FAST算法的實驗中,A組聚集率比采用本文算法的A組高,明顯出現(xiàn)了冗余的特征點,而B組的聚集率相比采用本文算法的B組低,說明出現(xiàn)了特征點丟失的情況.采用本文算法的AB兩組數(shù)據(jù)通過兩次實驗得到的特征點重復(fù)率相比FAST算法較高,表明本文算法具有良好的穩(wěn)定性.本文算法在進行最優(yōu)閾值和半徑選擇時,會進行迭代計算,但是時間效率與FAST算法為同一個數(shù)量級,能夠保證算法的實時性.

表3 AdaBoost_FAST算法與FAST算法特征點提取性能對比

4.4 參數(shù)選擇實驗

參數(shù)的選擇能夠影響算法在準確率以及時間效率方面的性能,本文算法中的參數(shù)包括迭代次數(shù)T,以及抽樣衰減因子γ.為了檢驗這些參數(shù)的影響,本文進行了一系列實驗來評估它們在算法中對閾值和半徑自適應(yīng)選擇的準確性和效率性能的影響.將實驗數(shù)據(jù)分成A、B、C三個組進行實驗.

如圖7所示,迭代通常進行到12-18次時,分類器的錯誤率已經(jīng)收斂到較小的值,并且在后續(xù)迭代中能夠保持穩(wěn)定,因此已經(jīng)收斂于最優(yōu)閾值和半徑.

圖7 迭代次數(shù)與錯誤率變化

另一方面結(jié)合圖8中的信息,隨著迭代次數(shù)的增加,時間成本也是成線性增加.綜合經(jīng)驗觀察表明,當(dāng)?shù)螖?shù)選擇為20時,閾值和半徑自適應(yīng)選擇的準確性和效率性能都表現(xiàn)良好.

圖9γ取值與時間效率的關(guān)系圖中,三組數(shù)據(jù)中γ都取較大值時,時間增加較快.因為當(dāng)γ值較大時,閾值和半徑的抽樣概率衰減幅度會較小.若要選擇出最優(yōu)的閾值和半徑,迭代次數(shù)會增多,從而時間效率成本將會增大.結(jié)合圖10中的信息,在不同γ的取值所對應(yīng)的最優(yōu)閾值和半徑以及分類器錯誤率關(guān)系中.當(dāng)γ取值大于0.03時,不同γ的取值所對應(yīng)的分類器錯誤率都能夠達到很小的值,即選擇出的閾值和半徑都為最優(yōu)值.當(dāng)γ的值遠小于0.03時,閾值和半徑的抽樣概率衰減過大,導(dǎo)致大量閾值和半徑都無法參與迭代過程,因此可能會錯失最優(yōu)值的選擇以致分類器錯誤率較高.結(jié)合圖9和圖10的信息,本文根據(jù)經(jīng)驗γ的值選擇為2-5.

圖8 迭代次數(shù)與耗時變化

圖9 gama取值與耗時關(guān)系

圖10 gama取值與最優(yōu)解的關(guān)系

5 結(jié) 論

本文提出了一種AdaBoost_FAST算法,該算法基于AdaBoost思想,根據(jù)支持向量機分類器錯誤率通過代價函數(shù)計算每組閾值和半徑的抽樣概率.經(jīng)過多次迭代以后,最優(yōu)的閾值和半徑的抽樣概率將會遠大于其他值的抽樣概率,逐步實現(xiàn)最優(yōu)閾值和半徑的自適應(yīng)選擇.實驗結(jié)果表明,選取合適的參數(shù)值,該算法能夠有效地進行閾值和半徑的自適應(yīng)選擇,從而減少了FAST算法中特征點冗余和丟失的情況,提高了特征點提取精度,同時能夠保證FAST算法的時效性,對于實時系統(tǒng)的應(yīng)用具有重要意義.