隨機(jī)蕨叢算法匹配識(shí)別性能研究

李海濤　朱大明　楊琪莉

摘要：為了改進(jìn)基于特征點(diǎn)的圖像匹配識(shí)別方法的精確度，文章對(duì)特征點(diǎn)匹配算法隨機(jī)蕨叢的性能進(jìn)行評(píng)估，并與尺度不變特征變換算法SIFT的匹配性能進(jìn)行對(duì)比研究。通過實(shí)驗(yàn)將隨機(jī)蕨叢算法參數(shù)進(jìn)行優(yōu)化配置，分別測(cè)試兩種算法的魯棒性能和匹配速度。實(shí)驗(yàn)結(jié)果表明，隨機(jī)蕨叢算法的匹配精度能達(dá)到85%左右，明顯高于SIFT算法，匹配速度也遠(yuǎn)快于SIFT算法，但仍然有待提高。

Abstract： In order to improve the accuracy of the image matching recognition method on the basic of feature points， this paper evaluates the random ferns performance of the feature matching algorithm and compares it with the matching performance of SIFT with scale invariant feature transform algorithm. Through the experiment， the optimized configuration of the parameters of random ferns algorithm is carried out， the robust performance and matching speed of the two algorithms are tested. The experimental results show that the matching accuracy of random ferns algorithm can reach 85%， it is significantly higher than SIFT algorithm， the matching speed of it is far faster than SIFT algorithm， but it remains to be improved.

關(guān)鍵詞：圖像匹配；片元識(shí)別；半樸素貝葉斯方法；蕨結(jié)構(gòu)；分類

Key words： image matching；fragment identification；semi-naive bayesian approach；fern structure；classification

中圖分類號(hào)：TP391.4 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2016）05-0221-03

0 引言

圖像匹配技術(shù)被廣泛應(yīng)用于目標(biāo)識(shí)別和圖像姿態(tài)估計(jì)領(lǐng)域[1]。基于特征點(diǎn)的圖像識(shí)別匹配方法主要分為兩大類，一類是通過計(jì)算圖像的局部描述子，該描述子在透視變化和光照變化的情況下能保持不變。主要有SIFT描述子[2]。另一類方法依賴于統(tǒng)計(jì)學(xué)的學(xué)習(xí)技術(shù)，通過對(duì)圖像片元的所有可能出現(xiàn)的情況進(jìn)行建模，利用該模型進(jìn)行匹配識(shí)別。主要算法有結(jié)合PCA和多高斯模型[3]。

上述方法都具有一定的局限性，SIFT描述子通過對(duì)圖像進(jìn)行高斯卷積，差分近似以及梯度計(jì)算，保證其尺度，光照和透視不變性，具有較好的匹配效果，但也產(chǎn)生了較大的時(shí)間代價(jià)，算法實(shí)時(shí)性較差。PCA和多高斯模型方法對(duì)于透視變形的圖像將匹配失敗，應(yīng)用范圍比較局限。隨機(jī)蕨叢算法將匹配過程分為在線和離線階段，保證其匹配實(shí)時(shí)性，在訓(xùn)練階段對(duì)每個(gè)特征點(diǎn)出現(xiàn)的變形情況進(jìn)行了充分的訓(xùn)練，保證其匹配正確率。

1 隨機(jī)蕨叢算法

隨機(jī)蕨叢算法[4，5]是Lepetit等在隨機(jī)森林算法基礎(chǔ)上發(fā)展來的，將傳統(tǒng)的匹配問題轉(zhuǎn)換為分類問題。隨機(jī)蕨叢算法在每個(gè)蕨類節(jié)點(diǎn)包含一個(gè)隨機(jī)二元測(cè)試，利用該二元測(cè)試將訓(xùn)練樣本的片元空間進(jìn)行剖分來實(shí)現(xiàn)圖像的識(shí)別。每個(gè)類別的訓(xùn)練樣本是該類別關(guān)鍵點(diǎn)所有可能出現(xiàn)的圖像片元的集合，結(jié)合每個(gè)隨機(jī)蕨包含的二元測(cè)試結(jié)果以及半樸素貝葉斯理論[6]訓(xùn)練得到關(guān)于該類別的概率分布，并用該分布對(duì)測(cè)試圖像進(jìn)行分類。

1.1 半樸素貝葉斯

隨機(jī)蕨叢分類是利用半樸素貝葉斯理論對(duì)測(cè)試圖像的特征點(diǎn)片元估計(jì)其最可能的類別的過程。類別集合為C={c1，c2…ci}，i=1，2，…，H，二元測(cè)試集合為F={f1，f2…fj}，j=1，2，…，N。對(duì)于片元P的類別ci可公式化為：

貝葉斯公式展開為：

先驗(yàn)概率P（C）與類別C之間是相互獨(dú)立的，所以式（1）可化簡(jiǎn)為：

每一個(gè)二元測(cè)試fj的值只依賴于圖像片元I中兩個(gè)像素點(diǎn)的位置dj，1和dj，2的強(qiáng)度值，即：若I（dj，1）< I（dj，2）則fj值為1，反之為0。

需要對(duì)每個(gè)二元測(cè)試進(jìn)行大概N次的比較才能保證分類精度，考慮到二元測(cè)試之間的相關(guān)性以及算法的靈活性，通過將二元測(cè)試集分成M組，每組包含S個(gè)測(cè)試，S=N /M。每一個(gè)組就是一個(gè)蕨類，計(jì)算每一個(gè)蕨類的二元測(cè)試的聯(lián)合分布概率為：

其中Fk={fσ （k，1）， fσ （k，2），…， fσ （k，S）}，k=1，…，M，表示第k個(gè)蕨類，σ（k，S）表示從1到N的一個(gè)隨機(jī)序列函數(shù)。

利用半樸素貝葉斯的方法對(duì)二元測(cè)試集中的部分相關(guān)性進(jìn)行建模。使得原本需要計(jì)算2N次降到了M×2S次。通過對(duì)蕨類的數(shù)量M以及蕨類的大小S進(jìn)行調(diào)整，可使得算法在性能以及內(nèi)存開銷方面更靈活控制。

1.2 隨機(jī)蕨叢訓(xùn)練

算法訓(xùn)練階段需要對(duì)目標(biāo)圖像提取關(guān)鍵點(diǎn)集。關(guān)鍵點(diǎn)集是通過對(duì)目標(biāo)圖像多次變形，變形圖像可通過對(duì)目標(biāo)圖像進(jìn)行仿射變換得到。對(duì)每一個(gè)變形目標(biāo)圖像利用關(guān)鍵點(diǎn)描述子提取關(guān)鍵點(diǎn)，并跟蹤每一個(gè)關(guān)鍵點(diǎn)，被發(fā)現(xiàn)次數(shù)最多的點(diǎn)集就是穩(wěn)定的關(guān)鍵點(diǎn)集。每一個(gè)關(guān)鍵點(diǎn)對(duì)應(yīng)一個(gè)類別。隨機(jī)蕨叢算法通過計(jì)算圖像的Harris角點(diǎn)提取關(guān)鍵點(diǎn)。

隨機(jī)蕨叢訓(xùn)練過程要對(duì)公式（4）中的類別條件概率P（Fm|C=ci）進(jìn)行估計(jì)，每個(gè)蕨類的大小為S，即有S個(gè)二元測(cè)試組成，將產(chǎn)生K=2S個(gè)值，k =1，2，…，K，設(shè)pk，ci為每個(gè)蕨類葉子結(jié)點(diǎn)處類別為ci測(cè)試結(jié)果為k的概率。

對(duì)于參數(shù)pk，ci最簡(jiǎn)單的估計(jì)方法是利用最大似然估計(jì)，令Nk，ci表示在值為k的蕨類節(jié)點(diǎn)處類別為ci的樣本集出現(xiàn)的次數(shù)，Nci表示類別ci總的樣本數(shù)量。這兩個(gè)參數(shù)可對(duì)每個(gè)蕨類進(jìn)行獨(dú)立估計(jì)。則pk，ci即為Nk，ci與Nci的比值。

由于每個(gè)樣本的數(shù)量是有限的，所以有時(shí)候?qū)⒉粫?huì)有類別為ci的樣本出現(xiàn)在值為k的蕨類節(jié)點(diǎn)處，使得Nk，ci和pk，ci會(huì)很小甚至等于0，從而影響分類結(jié)果。為解決這個(gè)問題，采用：

Nr是正則化項(xiàng)，是統(tǒng)一的二元測(cè)試的值的Dirichlet先驗(yàn)值[7]，算法設(shè)置為Nr=1。如果一個(gè)類別ci沒有在某個(gè)特定的蕨類值k里出現(xiàn)，那么參數(shù)pk，ci也不會(huì)為0，影響概率估計(jì)，防止了過擬合產(chǎn)生的分類不正確問題。

1.3 隨機(jī)蕨叢算法

隨機(jī)蕨叢算法思想是，每個(gè)蕨類包含一個(gè)二元測(cè)試的集合，離線訓(xùn)練階段對(duì)已知類別的片元進(jìn)行學(xué)習(xí)，得到每個(gè)類別相對(duì)于每個(gè)蕨類的類別概率分布，在線匹配階段利用半樸素貝葉斯方法對(duì)每個(gè)蕨類的類別概率分布進(jìn)行聯(lián)合計(jì)算，得出分類結(jié)果，并利用法RANSAC剔除誤分類，從而判斷出兩個(gè)圖像是否匹配。步驟如下：

①輸入目標(biāo)圖像，并提取關(guān)鍵點(diǎn)，生成關(guān)鍵點(diǎn)片元；

②生成包含隨機(jī)二元測(cè)試集的隨機(jī)蕨叢，并將步驟①的關(guān)鍵點(diǎn)片元投入隨機(jī)蕨叢，生成隨機(jī)蕨叢分類器。離線訓(xùn)練完成；

③輸入測(cè)試圖像，并提取關(guān)鍵點(diǎn)，生成關(guān)鍵點(diǎn)片元；

④將測(cè)試圖像關(guān)鍵點(diǎn)片元投入隨機(jī)蕨叢分類器，利用RANSAC方法剔除誤分類，輸出分類結(jié)果。

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

為了驗(yàn)證隨機(jī)蕨叢算法在圖像匹配方面的性能，實(shí)驗(yàn)采用書封面以及人臉作為目標(biāo)圖像，分別有不同的紋理和結(jié)構(gòu)。測(cè)試圖像為電腦攝像頭錄制視屏序列，分辨率為640480。

2.1 參數(shù)估計(jì)

在1.1節(jié)討論了，影響隨機(jī)蕨叢算法性能的參數(shù)有蕨類大小S以及數(shù)量M。通過實(shí)驗(yàn)來優(yōu)化S，M兩個(gè)參數(shù)可提升算法識(shí)別率。圖1，圖2列出了蕨類數(shù)量M和蕨類大小S與算法識(shí)別率的關(guān)系圖，由圖可看出當(dāng)蕨類數(shù)量大于30 以及蕨類大小大于13時(shí)，算法識(shí)別率增長變緩，識(shí)別率在83%左右。對(duì)算法內(nèi)存需求預(yù)計(jì)訓(xùn)練時(shí)間的考慮，蕨類數(shù)量為30-50，蕨類大小為12-20較為適宜。算法采用S=13，M=30。

2.2 算法性能

本文從算法匹配正確率和算法運(yùn)行時(shí)間兩方面對(duì)隨機(jī)蕨叢算法進(jìn)行性能評(píng)估，利用書封面以及人臉兩組實(shí)驗(yàn)數(shù)據(jù)進(jìn)行測(cè)試，并將實(shí)驗(yàn)結(jié)果與SIFT算法進(jìn)行比較。圖3列出了兩種算法對(duì)于書封面的匹配示意圖，圖中白色圈表示算法匹配正確的點(diǎn)。在發(fā)生旋轉(zhuǎn)，尺度變化以及部分遮擋的情況下隨機(jī)蕨叢算法都能有效匹配。

利用隨機(jī)蕨叢算法對(duì)書封面進(jìn)行匹配，并將匹配結(jié)果SIFT算法進(jìn)行比較。隨機(jī)蕨叢算法識(shí)別率平均在85%，SIFT算法識(shí)別率平均在83%。在識(shí)別率方面隨機(jī)蕨叢算法要稍優(yōu)于SIFT算法。在匹配時(shí)間方面，隨機(jī)蕨叢算法由于涉及到計(jì)算尺度空間并計(jì)算HARRIS特征點(diǎn)增加了其匹配時(shí)間，平均每幀匹配時(shí)間在1400ms，要優(yōu)于進(jìn)行高斯卷積，差分近似和主方向計(jì)算的SIFT算法（4000ms/f）。

3 結(jié)論

實(shí)驗(yàn)結(jié)果表明隨機(jī)蕨叢算法在識(shí)別率方面要優(yōu)于SIFT算法，能達(dá)到85%左右的識(shí)別率；并在匹配時(shí)間上也要優(yōu)于SIFT算法，能有效對(duì)目標(biāo)圖像進(jìn)行識(shí)別，可應(yīng)用與圖像匹配以及圖像片元識(shí)別等領(lǐng)域。但該算法實(shí)時(shí)性有待提高，后續(xù)可引入能快速檢測(cè)的特征點(diǎn)在不影響識(shí)別率的前提下，增強(qiáng)算法實(shí)時(shí)性。

參考文獻(xiàn)：

[1]余萍，袁輝，趙振兵，等.圖像識(shí)別中的興趣點(diǎn)匹配方法研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（3）：132-135.

[2]石躍祥，蔡自興，王學(xué)武.基于改進(jìn)的PCA算法和Fisher線性判別的人臉識(shí)別技術(shù)[J].小型微型計(jì)算機(jī)系統(tǒng)，2006，27（9）：1731-1736.

[3]程克非，張聰.基于特征加權(quán)的樸素貝葉斯分類器[J].計(jì)算機(jī)仿真，2006，23（10）：92-94.