基于Agast-Adaboost的圖像匹配算法

徐鑄業(yè), 趙小強(qiáng),2,3

(1. 蘭州理工大學(xué) 電氣工程與信息工程學(xué)院, 甘肅 蘭州 730050; 2. 蘭州理工大學(xué) 甘肅省工業(yè)過程先進(jìn)控制重點(diǎn)實(shí)驗(yàn)室, 甘肅 蘭州 730050; 3. 蘭州理工大學(xué) 國家級(jí)電氣與控制工程實(shí)驗(yàn)教學(xué)中心, 甘肅 蘭州 730050)

圖像匹配是圖像處理和計(jì)算機(jī)視覺領(lǐng)域中的重要研究?jī)?nèi)容之一，目前已被廣泛應(yīng)用于目標(biāo)識(shí)別[1]、三維重建[2]、圖像檢索[3]、圖像融合[4]和醫(yī)學(xué)圖像分析[5]等領(lǐng)域.其本質(zhì)是在變換空間中尋找一種或多種最優(yōu)變換，使來自不同時(shí)間、不同傳感器和不同視角的同一場(chǎng)景的兩幅或多幅圖像在空間上保持一致.為了尋求這種最優(yōu)變換，研究者們需要在兩幅圖圖像的全局或局部提取特定的描述符.全局特征描述符在提取時(shí)過程復(fù)雜且速度慢，而局部特征描述符提取則相對(duì)簡(jiǎn)單，同時(shí)提取速度快且對(duì)尺度、旋轉(zhuǎn)及光照等因素具有良好的魯棒性.因此，研究局部特征描述符逐漸成為學(xué)者們研究的重點(diǎn)和方向.

在研究局部特征描述符的過程中，Lowe等[6]在2004年首先提出了浮點(diǎn)型的SIFT(scale invariant feature transform)算法，通過構(gòu)建圖像組層，將尺度空間中的極值點(diǎn)作為特征點(diǎn)，并用梯度直方圖生成128維的特征向量.雖然SIFT算法對(duì)旋轉(zhuǎn)、尺度縮放及光照變化具有不變性，但128維的描述向量計(jì)算復(fù)雜，運(yùn)行時(shí)間過長(zhǎng)，很難滿足實(shí)時(shí)性要求.在SIFT算法的基礎(chǔ)上，改進(jìn)的浮點(diǎn)型算法逐漸被提出.Ke等[7]提出的PCA-SIFT(principal component analysis-scale invariant feature transform)算法是用主元分析法代替直方圖，在41×41的圖像塊上計(jì)算39×39×2 (x,y方向)個(gè)梯度導(dǎo)數(shù)，然后用PCA將生成的特征向量降維，算法能夠?qū)μ卣飨蛄窟M(jìn)行有效的降維，縮短匹配時(shí)間，但構(gòu)建特征向量所需時(shí)間增加，總體的運(yùn)行時(shí)間只是略低于SIFT.Bay等[8]提出的SURF(speeded up robust features)算法是將原圖像的積分圖像和尺度不等的箱體濾波器作卷積，通過Harr小波構(gòu)建浮點(diǎn)型描述向量，代替SIFT中的不同尺度圖像與高斯函數(shù)作卷積的過程，很大程度上減少了特征點(diǎn)檢測(cè)時(shí)間，實(shí)時(shí)性能約是SIFT算法的2～3倍.Mair等[9]提出的AGAST算法是對(duì)FAST[10](features from accelerated segment test)算法的改進(jìn)，通過判斷待檢測(cè)點(diǎn)的灰度值與周圍鄰域內(nèi)設(shè)定閾值的大小關(guān)系來確定該檢測(cè)點(diǎn)是否為特征點(diǎn)，AGAST算法雖然對(duì)檢測(cè)效率有一定的提高，但該算法仍然存在對(duì)尺度變化及旋轉(zhuǎn)變換敏感的問題.以上改進(jìn)的浮點(diǎn)型算法與SIFT算法相比在性能上有所提升，但研究表明，這些改進(jìn)算法在匹配精度和匹配效率上均有明顯下降.

隨著圖像本身包含的信息以指數(shù)級(jí)的速度增加，浮點(diǎn)型的描述方案逐漸不適合當(dāng)前高速高精度的工程應(yīng)用需求.因此，許多研究人員提出利用二進(jìn)制描述向量代替浮點(diǎn)型描述向量，通過Hamming距離代替歐氏距離，從而快速完成特征點(diǎn)匹配.在二進(jìn)制描述符的研究過程中，Calonder等[11]提出了二進(jìn)制魯棒獨(dú)立基礎(chǔ)特征(binary robust independent elementary features,BRIEF)算法，該算法對(duì)隨機(jī)選取的高斯分布點(diǎn)對(duì)進(jìn)行比較，從而構(gòu)建二進(jìn)制描述符向量，且與浮點(diǎn)型的描述算法相比具有明顯的實(shí)時(shí)性能優(yōu)勢(shì).Rublee等[12]提出的ORB(oriented FAST and rotated BRIEF)算法采用改進(jìn)的BRIEF算法生成二進(jìn)制特征向量，然后與Hamming距離結(jié)合實(shí)現(xiàn)特征點(diǎn)的匹配，實(shí)驗(yàn)結(jié)果表明ORB算法相比BRIEF算法具有更好的區(qū)分性和魯棒性.Leutenegger等[13]提出的BRISK(binary robust invariant scalable keypoints)算法，在同心圓上用AGAST算法提取特征點(diǎn)，然后等間隔采樣并計(jì)算其距離集合，最后采用Hamming距離完成特征匹配.

以上二進(jìn)制描述算法雖然在實(shí)時(shí)性上具有一定的優(yōu)勢(shì)，但魯棒性和區(qū)分性與浮點(diǎn)型算法相比明顯降低，在實(shí)際工程領(lǐng)域很難得到廣泛應(yīng)用.為此，本文提出了一種基于尺度空間金字塔與AGAST融合的局部二進(jìn)制特征匹配算法(ALBFMA).通過構(gòu)建高斯尺度金字塔并與AGAST融合，實(shí)現(xiàn)特征點(diǎn)的快速提取，同時(shí)使AGAST算法具備尺度不變性，然后用改進(jìn)的Adaboost對(duì)特征點(diǎn)進(jìn)行描述，從而使匹配算法具有較好的匹配效率和較高的匹配精度，同時(shí)對(duì)尺度及旋轉(zhuǎn)等具有良好的魯棒性.

1 AGAST 檢測(cè)算法

AGAST算法是在FAST算法的基礎(chǔ)上改進(jìn)而來，為了進(jìn)一步提高檢測(cè)效率與檢測(cè)速度，該算法提取足夠多的像素點(diǎn)，并且以待檢測(cè)點(diǎn)為圓心，半徑為3個(gè)像素的Bresenham圓作為模板，將灰度值大于或小于周圍鄰域內(nèi)閾值的待檢測(cè)點(diǎn)視為特征點(diǎn).雖然AGAST算法與FAST算法具有相似的特征點(diǎn)檢測(cè)標(biāo)準(zhǔn)，但其對(duì)復(fù)雜圖像有更好的性能，并且采用下式所示的”非較亮”與”非較暗”模式對(duì)原配置空間進(jìn)行擴(kuò)展:

(1)

2 ALBFMA算法

2.1 ALBFMA特征點(diǎn)提取

在特征點(diǎn)提取階段，本文采用將AGAST算法與尺度空間理論進(jìn)行融合.首先用高斯差分濾波器把圖像構(gòu)建成N組S層的高斯差分金字塔，然后分別在尺度空間金字塔的每層都使用AGAST特征點(diǎn)檢測(cè)算法，如圖1所示.

由于AGAST算法不具備尺度不變性，且高斯核是實(shí)現(xiàn)尺度變換的唯一線性核，因此本文將高斯函數(shù)與原始圖像進(jìn)行卷積從而得到尺度空間，圖像I對(duì)應(yīng)的尺度空間函數(shù)L(x,y,σ)為

L(x,y,σ)=G(x,y,σ)*I(x,y)

(2)

(3)

式中:k為常數(shù)，表示相鄰的尺度空間倍數(shù).

特征點(diǎn)檢測(cè)過程如圖2所示.它由n個(gè)octave層ci和n個(gè)中間層di組成(i=0,1,…，i-1)，其中，ci是由原始圖像c0降采樣生成，中間層di位于ci和ci+1之間，將1.5倍的原始圖像c0進(jìn)行降采樣得到d0，然后再對(duì)d0降采樣即可得到其他內(nèi)層.差分結(jié)果表明：若標(biāo)記點(diǎn)為極值點(diǎn)，則記錄該點(diǎn)的尺度空間和位置；若該點(diǎn)為非極值點(diǎn)，則將相鄰兩層與當(dāng)前層作二次函數(shù)擬合，然后對(duì)特征空間作插值運(yùn)算，并將與插值點(diǎn)對(duì)應(yīng)的像素點(diǎn)的尺度空間和位置記錄，則此像素點(diǎn)即為新的特征點(diǎn).

2.2 ALBFMA特征描述符

利用改進(jìn)的AGAST算法提取特征點(diǎn)時(shí)具有尺度及旋轉(zhuǎn)不變性，且具有較高的準(zhǔn)確率，但描述向量存在維數(shù)高且計(jì)算時(shí)間長(zhǎng)的問題，因此本文采用改進(jìn)的Adaboost算法對(duì)生成的特征向量降維.Adaboost算法[14]是由劉沖等在Boosting算法[15]的基礎(chǔ)上提出的一種機(jī)器學(xué)習(xí)方法，它在分類時(shí)計(jì)算弱分類的權(quán)重，并沒有考慮測(cè)試集中各樣本的特征從而導(dǎo)致達(dá)不到預(yù)期的效果.因此，本文通過對(duì)測(cè)試樣本集聚類，找到每個(gè)測(cè)試樣本最近的樣本組，并計(jì)算它們之間的相似度，然后根據(jù)各弱分類器對(duì)各樣本組分類的錯(cuò)誤率賦予其相應(yīng)的權(quán)重，最后結(jié)合測(cè)試樣本與各樣本組的相似度并加權(quán)各弱分類器的權(quán)重來構(gòu)成最終的決策分類器，從而達(dá)到降維的目的.

以下是本文提出的改進(jìn)的Adaboost算法的弱分類器和決策分類器的實(shí)現(xiàn)過程.

輸入：訓(xùn)練數(shù)據(jù)集

S={(x1,y1),(x2,y2),…,(xn,yn)}

初始化：S1(i)=1/N，其中i=1,2，…，n

fori=1,2,…,k其中k為迭代次數(shù)

1) 從S中有放回抽樣，得到Sk；

2) 在Sk中訓(xùn)練出弱分類器hk；

3) 計(jì)算hk的錯(cuò)誤率εk：

4) 對(duì)每個(gè)樣本的權(quán)重歸一化.

輸出：弱分類器H=(h1,h2,…,hk)

在得到弱分類器后將S分為b組，各組為(b1,b2,…,bm),并用錯(cuò)誤率計(jì)算每個(gè)弱分類器對(duì)各組的權(quán)重，如下式：

(4)

式中:abk為第i個(gè)弱分類器對(duì)第b個(gè)組分類的錯(cuò)誤率.再通過下面兩式計(jì)算第b個(gè)樣本組對(duì)第i個(gè)弱分類器的權(quán)重vbi以及整體權(quán)重Vbk：

(5)

(6)

計(jì)算第j個(gè)樣本到第c個(gè)樣本組的距離djc和相似度ljc：

式中：xjθ為第j個(gè)樣本的第θ個(gè)屬性值；bcθ為第c個(gè)樣本組的第θ個(gè)屬性值.然后通過下式可得第j個(gè)樣本相應(yīng)的第i個(gè)弱分類器的權(quán)重：

(9)

最后對(duì)多個(gè)弱分類器加權(quán)，得到?jīng)Q策分類器H(X)：

(10)

2.3 ALBFMA算法收斂性分析

ALBFMA算法在弱分類器的實(shí)現(xiàn)過程中采用迭代采樣的實(shí)現(xiàn)方式，在Adaboost算法訓(xùn)練過程中，其收斂性通常是由最終決策分類器的錯(cuò)誤率是否有界來進(jìn)行判斷.由Adaboost算法的弱分類器實(shí)現(xiàn)過程可知，迭代次數(shù)為k，且弱分類器hk的錯(cuò)誤率為

則由Freund[16]提出的理論可知,對(duì)任意的Adaboost算法，若每次迭代生成的弱分類器的錯(cuò)誤率分別為ε1,ε2,…，εk，則最終的決策分類器的訓(xùn)練錯(cuò)誤率ε有上界，且終止條件為

(11)

由此可知，本文所提算法是收斂的.

3 實(shí)驗(yàn)分析

為了驗(yàn)證本文算法在復(fù)雜應(yīng)用場(chǎng)景中的有效性，將Oxford dataset[17]標(biāo)準(zhǔn)測(cè)試圖像集中的2幅圖像Img1和Img2作為待匹配圖像和參考圖像，然后對(duì)2幅圖像分別用SIFT算法、FAST算法、 BRISK算法和本文算法進(jìn)行匹配實(shí)驗(yàn)，匹配結(jié)果如圖3和表1所示.

由圖3和表1可以看出，SIFT算法在兩幅圖像中都能檢測(cè)出較多的特征點(diǎn)，但匹配點(diǎn)數(shù)要少于BRISK和本文算法；FAST算法的特征點(diǎn)的檢測(cè)個(gè)數(shù)和匹配點(diǎn)數(shù)都遜色于SIFT算法、BRISK算法和本文算法；BRISK算法檢測(cè)出的特征點(diǎn)個(gè)數(shù)少于SIFT和本文算法，但其匹配點(diǎn)數(shù)多于SIFT算法；本文算法的特征點(diǎn)檢測(cè)個(gè)數(shù)和匹配點(diǎn)數(shù)都優(yōu)于SIFT、FAST、BRISK算法，從而可以體現(xiàn)出本文算法在復(fù)雜應(yīng)用場(chǎng)景下的有效性.

表1 四種算法匹配點(diǎn)數(shù)對(duì)比

為了進(jìn)一步驗(yàn)證所提算法的有效性，將本文算法與SIFT算法、FAST算法以及BRISK算法作了一系列實(shí)驗(yàn)對(duì)比.實(shí)驗(yàn)同樣采用來自于Oxford dataset的標(biāo)準(zhǔn)測(cè)試圖像集，本文選擇數(shù)據(jù)包bikes、Leuven、UBC、boat四組圖像的第1張和第4張圖像作為參考圖像和待匹配圖像，分別選擇模糊變換(bikes)、光照變換(Leuven)、JPEG壓縮(UBC)、尺度變換和旋轉(zhuǎn)變換(boat)測(cè)試四種算法在不同條件的性能.仿真硬件環(huán)境為CPU Intel(R) Core(TM) i5-2430M 2.40 GHz、RAM 8GB、MATLAB R2014a和64位Windows10 SP1.

圖4是本文所選四種圖像變換的測(cè)試圖像，為進(jìn)一步評(píng)估上述四種算法在四種圖像變換下的匹配性能，采用文獻(xiàn)[17]的查準(zhǔn)率(recall)和查錯(cuò)率(1-性能優(yōu)越的匹配算法可以在匹配率高的同時(shí)找出更多的匹配點(diǎn),而且具有更高的正確匹配率，即在查錯(cuò)率相同的情況下，查準(zhǔn)率越高算法匹配性能越優(yōu)越.

precision)作為評(píng)估標(biāo)準(zhǔn)：

圖5為四種算法在圖像發(fā)生模糊變換時(shí)的匹配結(jié)果.從圖中可以看出,隨著查錯(cuò)率的不斷增加，本文算法和BRISK算法表現(xiàn)出良好的匹配性能，而SIFT 算法和FAST算法則對(duì)模糊變換相對(duì)敏感，這是由于SIFT和FAST算法采用易受環(huán)境影響的浮點(diǎn)型描述符，而本文算法和BRISK算法采用更加穩(wěn)定的二進(jìn)制描述符，從而對(duì)模糊變換體現(xiàn)出更好的魯棒性.

四種算法在圖像發(fā)生光照變換時(shí)的匹配結(jié)果如圖6所示.從圖中可以看出,當(dāng)給圖像加上不同強(qiáng)度的光源后，本文算法性能最佳，受光照影響最小.這是由于本文算法對(duì)生成的描述符作了歸一化處理，從而使其對(duì)光照變換具有更好的不變性.

四種算法在發(fā)生JPEG壓縮變換時(shí)的匹配結(jié)果如圖7所示.從圖中可以看出,本文算法對(duì)JPEG壓縮變換性能優(yōu)于SIFT算法、FAST算法和BRISK算法，且隨著查錯(cuò)率的增加，本文算法和BRISK算法查準(zhǔn)率逐漸接近，由此可知本文算法和BRISK算法對(duì)JPEG壓縮變換都具有良好的魯棒性.

四種算法對(duì)尺度和旋轉(zhuǎn)變換的匹配結(jié)果如圖8所示.從圖中可以看出,本文算法對(duì)尺度和旋轉(zhuǎn)具有良好的魯棒性，這是由于本文算法在特征點(diǎn)提取階段對(duì)AGAST算法進(jìn)行改進(jìn)，使其與尺度空間理論融合，從而具有較好的尺度和旋轉(zhuǎn)不變性.

4 結(jié)語

針對(duì)傳統(tǒng)浮點(diǎn)型特征描述算法誤匹配率高、匹配率低的問題，本文提出一種新的圖像匹配算法ALBFMA，將尺度空間理論與AGAST融合，使AGAST具有尺度不變性，然后用改進(jìn)的Adaboost生成二進(jìn)制特征向量，從而提高算法的匹配精度和匹配效率.經(jīng)實(shí)驗(yàn)驗(yàn)證，本文算法和SIFT、FAST、 BRISK算法相比具有匹配率高的優(yōu)勢(shì)，同時(shí)對(duì)模糊變換、光照變換和尺度變換具有良好的魯棒性.