基于方向信息的隨機(jī)蕨特征匹配算法

孫博文，邱子鑒，沈 斌，張艷鵬

(哈爾濱理工大學(xué) a. 計(jì)算中心；b. 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 1 50080)

基于方向信息的隨機(jī)蕨特征匹配算法

孫博文a，邱子鑒b，沈 斌b，張艷鵬a

(哈爾濱理工大學(xué) a. 計(jì)算中心；b. 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 1 50080)

特征點(diǎn)匹配是計(jì)算機(jī)視覺領(lǐng)域研究的核心問題之一。現(xiàn)有的隨機(jī)蕨算法具有簡單、高速的優(yōu)點(diǎn)，但隨機(jī)蕨算法訓(xùn)練得到的分類器體積過大，低內(nèi)存的移動(dòng)設(shè)備難以承受，嚴(yán)重限制了該算法的應(yīng)用范圍。針對(duì)該問題，提出一種基于方向信息的隨機(jī)蕨特征匹配算法，對(duì)用于訓(xùn)練的小圖塊進(jìn)行“歸零化”處理，提取特征屬性構(gòu)造特征向量，建立樸素貝葉斯模型訓(xùn)練分類器。實(shí)驗(yàn)結(jié)果表明，經(jīng)過該方法處理后，在相近識(shí)別精度下，得到的分類器體積減小到原始算法的1/8～1/16，滿足實(shí)時(shí)性要求。

隨機(jī)蕨；特征匹配；增強(qiáng)現(xiàn)實(shí)；模式識(shí)別；貝葉斯模型；方向蕨

1 概述

尺度不變性特征變換(Scale-invariant Feature Transform, SIFT)[1]特征點(diǎn)檢測器和描述器是十幾年前提出的算法，但是它在圖像識(shí)別、圖像匹配等領(lǐng)域中有著廣泛的應(yīng)用。然而，對(duì)于實(shí)時(shí)性要求高的系統(tǒng)，或者計(jì)算能力低的設(shè)備來說，SIFT的算法復(fù)雜度過大，無法滿足要求，這很大程度地限制了該算法的應(yīng)用范圍。為降低圖像匹配算法的計(jì)算復(fù)雜度，世界各國學(xué)者提出了許多改進(jìn)算法，其中，快速穩(wěn)健性特征(Speeded up Robust Features, SURF)[2]算法是公認(rèn)的高效算法之一，該算法在保持SIFT高特異性的基礎(chǔ)上，加速了局部特征點(diǎn)的獲取與匹配，然而，仍不能滿足實(shí)時(shí)性的要求。隨著計(jì)算機(jī)硬件性能的不斷提升，一些基于圖像處理器(Graphic Processing Unit, GPU)的算法相繼提出，如GPU-SIFT[3]和GPU-SUFR[4]，這些算法充分利用了GPU并行處理的優(yōu)勢，很大程度地提高了算法的效率，對(duì)于高性能的GPU，這些算法可以實(shí)現(xiàn)對(duì)圖像的實(shí)時(shí)處理。但是這類算法對(duì)GPU依賴過大，限制了算法的應(yīng)該范圍。由Willow G arage大學(xué)研究人員[5]提出的ORB(Oriented Brief)算法，結(jié)合簡單高速的加速區(qū)域分割(Features from Accelerated Se gment Test, F AST)[6]檢測器及二元魯棒獨(dú)立特征描述算子( Binary Robust In dependent E lementary Fe atures, BRIEF)[7]，執(zhí)行速度比SIFT快2個(gè)數(shù)量級(jí)，比SURF快1個(gè)數(shù)量級(jí)。但是由于FAST特征點(diǎn)不包含尺度信息，因此ORB算法對(duì)尺度的魯棒性較差。

以上提及的算法都是基于文獻(xiàn)[8]的理論構(gòu)造的框架：(1)局部特征提??；(2)對(duì)特征進(jìn)行不變性描述；(3)特征匹配；(4)基于外極幾何約束，求得兩圖像間的對(duì)應(yīng)關(guān)系。為降低運(yùn)算量，文獻(xiàn)[9-10]提出隨機(jī)蕨(Random Fern)算法，把圖像匹配視為分類問題，利用樸素貝葉斯分類算法對(duì)局部圖像(小圖塊)進(jìn)行分類。隨機(jī)蕨算法相對(duì)與SIFT，具有計(jì)算量小，魯棒性高的優(yōu)勢。然而，隨機(jī)蕨產(chǎn)生的分類器較大，消耗內(nèi)存嚴(yán)重。

在隨機(jī)蕨特征匹配過程中，首先采集目標(biāo)圖像的特征點(diǎn)(又稱角點(diǎn))，以特征點(diǎn)為中心，在31×31的鄰域(小圖塊)內(nèi)，隨機(jī)抽取數(shù)10個(gè)點(diǎn)對(duì)提取位特征(binary feature)，作為待分類項(xiàng)的特征屬性[11]。一個(gè)訓(xùn)練集包含著目標(biāo)圖像的各種仿射變換，采取這種沒有考慮到小圖塊方向的方式，忽略了不同方向的同一小圖塊之間的聯(lián)系——通過“歸一化”處理，可以旋轉(zhuǎn)小圖塊到“零”方向。顯然，以這種方式提取的特征屬性會(huì)影響分類器的質(zhì)量，降低分類器的識(shí)別率。為解決這一問題，本文提出一種基于方向信息的隨機(jī)蕨特征匹配算法，在提取位特征之前，對(duì)小圖塊進(jìn)行“歸一化”處理，降低隨機(jī)蕨叢的無向性對(duì)分類結(jié)果的影響。為與原始隨機(jī)蕨算法加以區(qū)別，本文算法命名為OFern。

2 基于方向信息的隨機(jī)蕨特征識(shí)別與匹配

隨機(jī)蕨算法采用機(jī)器學(xué)習(xí)算法中的貝葉斯分類模型處理特征識(shí)別與匹配問題，將計(jì)算量龐大的特征不變性描述和特征匹配過程轉(zhuǎn)移由分類器處理。本文采用基于方向信息的隨機(jī)蕨特征，利用樸素貝葉斯分類模型，通過離線訓(xùn)練分類器和在線識(shí)別2個(gè)階段實(shí)現(xiàn)特征的分類及匹配[12]。盡管算法增加了特征點(diǎn)方向信息的計(jì)算所需的系統(tǒng)開銷，但是利用包含有方向信息的特征向量所訓(xùn)練的分類器，分類器識(shí)別率明顯高于原始算法。并且實(shí)驗(yàn)結(jié)果證明，計(jì)算特征點(diǎn)方向的算法可滿足實(shí)時(shí)性要求。

2.1 灰度重心

矩特征主要表征了圖像區(qū)域的幾何特征，又稱為幾何矩，由于其具有旋轉(zhuǎn)、平移、尺度等特性的不變特征，因此又稱其為不變矩[13]。本文利用從小圖塊的中心在它的灰度重心的向量，計(jì)算出該小圖塊的方向。在文獻(xiàn)[14]中，用圖像矩來計(jì)算小圖塊的灰度重心，公式定義如下：

其中，I( x, y)代表在點(diǎn)(x, y)處的圖像灰度值。一階矩用于確定圖像質(zhì)心，即：

如果用O代表小圖塊的中心，那么從中心到重心的向量為OC，則該小圖塊的方向可以表示為：

目前，有許多計(jì)算圖像方向的方法，在文獻(xiàn)[5]中，研究人員將該方法與其他2種基于梯度的方法進(jìn)行了比較。他們的結(jié)果顯示，在較大圖像噪聲的情況下，基于圖像矩的方法計(jì)算得到的方向更為穩(wěn)定。

2.2 樸素貝葉斯分類模型

在隨機(jī)蕨特征匹配過程中，首先采集目標(biāo)圖像的特征點(diǎn)(角點(diǎn))，以特征點(diǎn)為中心，選取31× 31的鄰域塊(小圖塊)，作為識(shí)別與分類的基本單位。為獲得豐富且全面的訓(xùn)練集，系統(tǒng)會(huì)模擬出大量的仿射變換圖像，并為圖像添加高斯噪聲。以同一特征點(diǎn)為中心生成的各種小圖塊看作一類，ci, i=1,2,…,N ，所有的類別記作N。位特征用gj表示，位特征計(jì)算公式如下：

其中，dj1和dj2表示在小圖塊I中的2個(gè)點(diǎn)(測試點(diǎn)對(duì))。

由于旋轉(zhuǎn)小圖塊后再根據(jù)上式計(jì)算位特征與旋轉(zhuǎn)這個(gè)測試點(diǎn)對(duì)，再計(jì)算位特征的方式等價(jià)，并且前者需要遍歷小圖塊內(nèi)所有像素，后者只需要旋轉(zhuǎn)2個(gè)點(diǎn)，計(jì)算復(fù)雜度明顯低于前者，則旋轉(zhuǎn)公式如下：

其中，Dj1和Dj2是在小圖塊中隨機(jī)選取的2個(gè)位置，稱為基準(zhǔn)測試點(diǎn)對(duì)。θ由式(3)計(jì)算得到。分類問題用下式描述：

其中，C表示隨機(jī)的某一個(gè)類。

根據(jù)貝葉斯公式，可將上式分解成：

由于先驗(yàn)概率P( C=ci)與分母P( g1, g2,…,gN)均為常數(shù)，因此式(6)可等價(jià)于：

隨后將N個(gè)特征分為大小為S的M個(gè)組，每一個(gè)組叫做“蕨”。則式(7)可表示為：

根據(jù)以上樸素貝葉斯分類模型的相關(guān)公式，通過由計(jì)算機(jī)生成的訓(xùn)練樣本集來訓(xùn)練分類器。

2.3 分類器離線訓(xùn)練

一個(gè)完善的分類器需要對(duì)圖像光照變化、投影形變、圖像模糊以及圖像噪聲具有較強(qiáng)的穩(wěn)健性。這里利用仿射變換模擬出不同尺度、不同視角下的圖像樣本集合。對(duì)生成的圖像人為地添加高斯噪聲，以提高分類器對(duì)噪聲的魯棒性。然后從形變圖像中提取特征點(diǎn)，利用逆仿射變換計(jì)算出特征點(diǎn)在模板圖像中對(duì)應(yīng)的坐標(biāo)，選取特征點(diǎn)出現(xiàn)次數(shù)最多的前N個(gè)，每一個(gè)特征點(diǎn)記作一個(gè)類。

在原始的隨機(jī)蕨算法中，通過在小圖塊內(nèi)隨機(jī)選取測試點(diǎn)對(duì)的方式，獲得位特征屬性。然而，采用這種方法，對(duì)于僅方向不同的小圖塊提取到的位特征屬性會(huì)有很大差別，影響分類器的性能?？紤]以上原因，本文引入圖像矩的思想，通過一階矩來計(jì)算圖像的灰度重心，以圖像的中心到重心的向量作為該圖像的方向，然后進(jìn)行圖像“歸一化”處理。在理想狀態(tài)下，從經(jīng)過處理后的小圖塊中，隨機(jī)選取測試點(diǎn)對(duì)，僅方向不同的小圖塊的位特征應(yīng)當(dāng)相同。雖然，額外添加了圖像“歸一化”環(huán)節(jié)，使算法復(fù)雜度增加，但是實(shí)驗(yàn)表明，在相同的參數(shù)設(shè)置下，基于方向信息的隨機(jī)蕨算法的識(shí)別率明顯高于原始算法。

離線訓(xùn)練分類器的主要目的是，根據(jù)訓(xùn)練樣本中每個(gè)類別下的各個(gè)蕨出現(xiàn)的頻率估計(jì)各每個(gè)蕨的條件概率。條件概率P( Gm|C=ci)計(jì)算公式如下：

其中，nm, i表示在類別ci中第m個(gè)蕨的樣本個(gè)數(shù)；分母為在類別ci中所有的訓(xùn)練樣本數(shù)。

2.4 實(shí)時(shí)特征識(shí)別

在實(shí)時(shí)特征識(shí)別階段，從圖像采集設(shè)備上得到的圖像中，提取特征點(diǎn)，以特征點(diǎn)為中心的31×31的鄰域塊(小圖塊)作為待分類項(xiàng)，根據(jù)2.2節(jié)中相關(guān)公式，旋轉(zhuǎn)基測試點(diǎn)對(duì)，獲得每一個(gè)小圖塊的位特征屬性，用于后驗(yàn)概率的計(jì)算。根據(jù)位特征屬性，從分類器中檢索出對(duì)應(yīng)的各個(gè)的類別后驗(yàn)概率，其中，后驗(yàn)概率最大的類別為該待分類項(xiàng)，進(jìn)而實(shí)現(xiàn)了模板特征點(diǎn)與輸入圖像的特征點(diǎn)的識(shí)別與匹配，如圖1所示。

圖1 模板圖像有效識(shí)別及定位

3 實(shí)驗(yàn)結(jié)果與分析

為對(duì)算法的識(shí)別率及運(yùn)行速率等性能進(jìn)行驗(yàn)證，使用如圖2所示的2幅圖像，分辨率分別為640×480、320×240，作為模板圖像，在相同參數(shù)設(shè)置線，比較隨機(jī)蕨與本文算法的性能指標(biāo)。

圖2 模板圖像

3.1 識(shí)別率比較

訓(xùn)練分類器過程中使用隨機(jī)生成仿射圖像(10 0 00張)來訓(xùn)練分類器，用隨機(jī)生成的200張圖像驗(yàn)證生成的分類器的識(shí)別率。在隨機(jī)蕨算法中，影響分類器性能的有如下參數(shù)：類的數(shù)量，蕨的個(gè)數(shù)以及每個(gè)蕨中測試點(diǎn)對(duì)的多少。圖3～圖5為在不同參數(shù)下隨機(jī)蕨算法與本文算法在識(shí)別率上的比較。

圖3 不同參數(shù)下分類器識(shí)別率變化比較1

圖4 不同參數(shù)下分類器識(shí)別率變化比較2

圖5 不同參數(shù)下分類器識(shí)別率變化比較3

其中，圖3為確定蕨個(gè)數(shù)與每個(gè)蕨中測試點(diǎn)對(duì)個(gè)數(shù)不變，隨著類數(shù)量變化分類器識(shí)別率變化比較。圖4為確定蕨個(gè)數(shù)與類數(shù)量不變，隨著每個(gè)蕨中測試點(diǎn)對(duì)的個(gè)數(shù)不同分類器識(shí)別率變化比較。圖5為確定每個(gè)蕨中測試點(diǎn)對(duì)個(gè)數(shù)與類數(shù)量不變，隨著蕨個(gè)數(shù)變化分類器識(shí)別率變化比較。

如圖3所示，盡管隨著類的個(gè)數(shù)增加，識(shí)別率有所下降，但是本文算法的分類器識(shí)別率始終優(yōu)于隨機(jī)蕨算法。而且分類器的識(shí)別率也更加穩(wěn)定。實(shí)驗(yàn)結(jié)果顯示，本文算法可以處理更多的特征點(diǎn)。

圖4和圖5數(shù)據(jù)說明，隨著蕨個(gè)數(shù)與每個(gè)蕨中測試點(diǎn)對(duì)的個(gè)數(shù)的增加，本文算法的識(shí)別率明顯高于隨機(jī)蕨，尤其是在蕨個(gè)數(shù)與每個(gè)蕨中測試點(diǎn)對(duì)的個(gè)數(shù)都較小的情況下，本文算法的識(shí)別率約是隨機(jī)蕨算法的2倍。因此，可以在識(shí)別率較高的情況下，獲得更小的分類器。

3.2 分類器大小比較

由于隨機(jī)蕨算法生成的分類器通常較大，十分消耗內(nèi)存資源，因此本文針對(duì)此問題提出了基于方向信息的隨機(jī)蕨的改進(jìn)方法。在相近識(shí)別率的條件下，原始算法與本文算法生成的分類器體積比較如表1所示。

表1 相近識(shí)別率下分類器體積大小的比較

其中，分類器的體積用classes × 2sizes× ferns 表示。

由表1可見，在較高識(shí)別率下，本文算法生成的分類器體積明顯小于原始算法，驗(yàn)證了本文算法的有效性。

為達(dá)到穩(wěn)定的識(shí)別效果，本文算法參數(shù)選取分別為：類的數(shù)量為100，每個(gè)蕨中測試點(diǎn)對(duì)的個(gè)數(shù)為7，蕨個(gè)數(shù)為20。則相應(yīng)的分類器大小為500 KB(100×27×20×2 Byte/ 1 024)，對(duì)于如今的智能手機(jī)而言，可輕松處理。

3.3 運(yùn)行時(shí)間測試

對(duì)于實(shí)時(shí)性要求較高的應(yīng)用，如增強(qiáng)現(xiàn)實(shí)，對(duì)算法的運(yùn)行時(shí)間有著嚴(yán)格的限制。一般而言，圖像每幀能夠在30 ms內(nèi)處理完畢，其圖像序列在視覺效果上會(huì)比較流暢。隨機(jī)蕨算法的主要優(yōu)勢在于它的實(shí)時(shí)性，對(duì)于640×480大小的圖像，它的運(yùn)行時(shí)間是20 ms/幀。

本文采用[6]提供的測試視頻，測試機(jī)器配置為：AMD Athlon II X2處理器，2.69 GHz主頻，2 GB內(nèi)存。對(duì)于此測試視頻，本文算法的平均處理時(shí)間為20 m s/幀，完全可以滿足實(shí)時(shí)性的要求。

4 結(jié)束語

本文提出一種基于方向信息的隨機(jī)蕨特征匹配算法，OFern。利用灰度重心公式，對(duì)用于訓(xùn)練的小圖塊進(jìn)行“歸零化”處理，使得理想狀態(tài)下，僅方向不同的小圖塊提取得到的特征屬性相同，該方法有效地解決了方向變化對(duì)隨機(jī)蕨性能的影響。實(shí)驗(yàn)結(jié)果證明，經(jīng)過該方法處理后，在相近識(shí)別精度下，可以大幅降低分類器的體積，并且算法依然保持著良好的實(shí)時(shí)性能。隨著移動(dòng)設(shè)備硬件的不斷更新升級(jí)，使得在移動(dòng)平臺(tái)上實(shí)現(xiàn)實(shí)時(shí)、高精度的圖像匹配成為可能。因此，下一階段工作將嘗試移植該算法到移動(dòng)設(shè)備上，測試其性能，并結(jié)合GPU的并行處理優(yōu)勢，進(jìn)一步優(yōu)化算法。

[1] Lowe D G. Object Rec ognition from Local Scale-invariant Features[C]//Proceedings of the 7th IEEE In ternational Conference on Computer V ision. [S. 1.]: IEEE Press, 1999: 1150-1157.

[2] Bay H, Tuytelaars T, van Gool L. Surf: Speeded up Robust Features[C]//Proceedings of ECCV’06. Berlin, Germany: Springer, 2006: 404-417.

[3] Rublee E, Rabaud V, Konolige K, et al. ORB: An Efficient Alternative to SIFT or SURF[C]//Proceedings of the 7th IEEE International Conference on Computer Vision. [S. 1.]: IEEE Press, 2011: 2564-2571.

[4] Cornelis N, van Gool L. Fast Scale Invariant Feature Detection and Matching on Programmable Graphics Hardware[C]// Proceedings of CVPR’08. [S. 1.]: IEEE Press, 2008: 1-8.

[5] Terriberry T B, French L M, Helmsen J. GPU Accelerating Speeded-up Robust Features[C]//Proceedings of the 4th International Symposium on 3D Data Processing, Visualization and Transmission. [S. 1.]: IEEE Press, 2008: 355-362.

[6] Rosten E, Drummond T. Machine Learning for High Speed Corner Detection[C]//Proceedings of European Conference on Computer Vision. [S. 1.]: IEEE Press, 2006: 430-443.

[7] Calonder M, Lepetit V, Strecha C, et al. BRIEF: Binary Robust Independent Elementary Features[M]. Berlin, Germany: Springer, 2010.

[8] Schmid C, Mohr R. Local Gray Value Invariants for Image Retrieval[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(5): 530-535.

[9] Ozuysal M, Calonder M, Lepetit V, et al. Fast Keypoint Recognition Using Random Ferns[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(3): 448-461.

[10] Ozuysal M, Fua P, Lepetit V. Fast Keypoint Recognition in Ten Lines of Code[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. [S. 1.]: IEEE Press, 2007: 1-8.

[11] 李 珍, 江貴平. 基于條件互信息量的隨機(jī)蕨特征匹配算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2012, 33(5): 1908-1912.

[12] 陳 冰, 趙亦工, 李 欣. 基于隨機(jī)蕨的光電成像末端制導(dǎo)目標(biāo)初始化[J]. 光學(xué)學(xué)報(bào), 2010, 30(11): 19-22.

[13] Wikipedia Contributors. Moment(Mathematics)[EB/OL]. (2013-04-14). http://en.wikipedia.org/w/index.php?title=Moment_ (mathematics)&oldid=550315652.

[14] Rosin P L. Measuring Corner Properties[J]. Computer Vision and Image Understanding, 1999, 73(2): 291-307.

編輯 索書志

Random Fern Feature Matching Algorithm Based on Orientation Information

SUN Bo-wena, QIU Zi-jianb, SHEN Binb, ZHANG Yan-penga

(a. Compute Center; b. School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China)

Feature point matching is a key base of many computer vision problems. A large advantage of fern algorithm, simple and fast, is noticed among the existing algorithms, but classifier trained by fe rn is too lar ge to low memory device, such as cellphones. For cutting down the size of a classifier, this paper proposes an improved version of fern, n amed Oriented Fern(OFern), which “normal” patches are done that training for a classifier, and features are extracted, a Naive Bayesian model is built to train a classifier. Experimental results show that compared with the traditional fern, OFern can save memory to 1/8～1/16 at the similar recognition rate, while it still keeps high speed for real-time applications.

Random Fern(RF); feature matching; augmented reality; pattern recognition; Bayes model; Oriented Fern(OFern)

10.3969/j.issn.1000-3428.2014.05.040

孫博文(1963－)，男，副教授，主研方向：模式識(shí)別，虛擬現(xiàn)實(shí)，增強(qiáng)現(xiàn)實(shí)；邱子鑒、沈 斌，碩士研究生；張艷鵬，碩士。

2013-04-23

2013-06-10E-mail：949868412@qq.com

1000-3428(2014)05-0192-04

A

TP18