李海濤　朱大明　楊琪莉

摘要：為了改進基于特征點的圖像匹配識別方法的精確度，文章對特征點匹配算法隨機蕨叢的性能進行評估，并與尺度不變特征變換算法SIFT的匹配性能進行對比研究。通過實驗將隨機蕨叢算法參數(shù)進行優(yōu)化配置，分別測試兩種算法的魯棒性能和匹配速度。實驗結(jié)果表明，隨機蕨叢算法的匹配精度能達到85%左右，明顯高于SIFT算法，匹配速度也遠快于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)鍵詞：圖像匹配；片元識別；半樸素貝葉斯方法；蕨結(jié)構(gòu)；分類

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

中圖分類號：TP391.4 文獻標識碼：A 文章編號：1006-4311（2016）05-0221-03

0 引言

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

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

1 隨機蕨叢算法

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

1.1 半樸素貝葉斯

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

貝葉斯公式展開為：

先驗概率P（C）與類別C之間是相互獨立的，所以式（1）可化簡為：

每一個二元測試fj的值只依賴于圖像片元I中兩個像素點的位置dj，1和dj，2的強度值，即：若I（dj，1）< I（dj，2）則fj值為1，反之為0。

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

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

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

1.2 隨機蕨叢訓練

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

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

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

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

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

1.3 隨機蕨叢算法

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

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

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

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

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

2 實驗分析

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

2.1 參數(shù)估計

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

2.2 算法性能

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

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

3 結(jié)論

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

參考文獻：

[1]余萍，袁輝，趙振兵，等.圖像識別中的興趣點匹配方法研究[J].計算機工程與應用，2010，46（3）：132-135.

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

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