基于非線(xiàn)性尺度空間的增強(qiáng)現(xiàn)實(shí)場(chǎng)景識(shí)別算法

寇 蘭，秦鳴謙，趙新雨，黃宏程

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

增強(qiáng)現(xiàn)實(shí)(augmented reality，AR)[1-3]是當(dāng)前計(jì)算機(jī)視覺(jué)領(lǐng)域的研究熱點(diǎn)，它是由虛擬現(xiàn)實(shí)技術(shù)發(fā)展而來(lái)，通過(guò)在真實(shí)場(chǎng)景中添加虛擬信息增強(qiáng)人們對(duì)于真實(shí)場(chǎng)景的認(rèn)知。場(chǎng)景識(shí)別則是一套增強(qiáng)現(xiàn)實(shí)系統(tǒng)中非常關(guān)鍵的一個(gè)環(huán)節(jié)[4]，特征點(diǎn)匹配則是其中的關(guān)鍵技術(shù)。SIFT(scale invariant feature transform)算法的應(yīng)用[5]是特征檢測(cè)和圖像匹配中的一個(gè)里程碑，信息量大，獨(dú)特性好，它被廣泛應(yīng)用在很多不同的領(lǐng)域，如目標(biāo)識(shí)別，但此算法的運(yùn)算量過(guò)大、匹配速度慢；受到SIFT算法的啟發(fā)，SURF(speeded up robust feature)算法[6]運(yùn)算速度明顯增快，并且同樣具有縮放旋轉(zhuǎn)不變性，對(duì)照度和視點(diǎn)變換也具有一定的魯棒性；而B(niǎo)RIEF(binary robust independent elementary feature)算法[7]在圖像匹配中，計(jì)算速度和識(shí)別率等方面都超過(guò)了SIFT和SURF。

SIFT、SURF的特征描述對(duì)視點(diǎn)變換、照度變換、模糊、旋轉(zhuǎn)縮放變換等都有一定的魯棒性，但由于其描述符維數(shù)比較大，分別為128維和64維，導(dǎo)致每個(gè)描述符所占的空間比較大，因此造成后續(xù)的搜索和匹配時(shí)間消耗增大，識(shí)別速度下降，這對(duì)于對(duì)實(shí)時(shí)性要求很高的增強(qiáng)現(xiàn)實(shí)應(yīng)用而言是相當(dāng)不利的。而B(niǎo)RIEF算法與SIFT、SURF相比，在生成描述符和描述符匹配的時(shí)間消耗上低于前兩種算法，速度明顯增快，但是由于在BRIEF算法中是用二進(jìn)制串對(duì)特征點(diǎn)進(jìn)行描述，所以它對(duì)噪聲比較敏感，而且不具備旋轉(zhuǎn)不變性和尺度不變性。ORB(oriented fast and rotated brief)算法[8-10]對(duì)特征點(diǎn)描述的細(xì)致程度要低于SIFT和SURF，但在計(jì)算速度上要明顯快于SIFT和SURF。作為一種局部不變特征描述符，ORB具有旋轉(zhuǎn)不變性，但不足的是該算法并不具備尺度不變性，對(duì)于圖像的縮放變換魯棒性較差。其根本原因在于ORB算法采用FAST(features from accelerated segment test)[11]算法進(jìn)行特征點(diǎn)提取，但是FAST算法沒(méi)有賦予特征點(diǎn)尺度不變信息，因此使得ORB描述符不具備尺度不變性。文獻(xiàn)[12-14]分別利用SIFT和SURF算法的思想使描述符具備了尺度不變性。但這種基于高斯金字塔的改進(jìn)方法造成邊界模糊和細(xì)節(jié)丟失，使特征點(diǎn)檢測(cè)錯(cuò)誤率增高，而采用建立非線(xiàn)性尺度空間提取特征點(diǎn)的方法可有效彌補(bǔ)此方面的不足[15,16]。

1 基于非線(xiàn)性尺度空間的特征點(diǎn)提取

1.1 非線(xiàn)性尺度空間的建立

由于歐拉法在收斂時(shí)步長(zhǎng)非常小，迭代次數(shù)多，計(jì)算成本高，所以在求解非線(xiàn)性擴(kuò)散方程時(shí)若用傳統(tǒng)的正向歐拉法效率會(huì)很低。由此，本文在進(jìn)行非線(xiàn)性擴(kuò)散濾波時(shí)使用加性算子分裂算法(additive operator splitting，AOS)[17]，這樣對(duì)于任意步長(zhǎng)都可以獲得穩(wěn)定的非線(xiàn)性尺度空間。

通常利用非線(xiàn)性偏微分方程對(duì)非線(xiàn)性擴(kuò)散濾波方法進(jìn)行描述，如式(1)

(1)

為了降低邊緣位置的擴(kuò)散，增加區(qū)域內(nèi)部的平滑程度，函數(shù)c(x,y,t)可以根據(jù)梯度幅值的大小來(lái)進(jìn)行設(shè)定。函數(shù)g的形式有如下幾種

(2)

(3)

(4)

c函數(shù)選擇g3夠平滑區(qū)域內(nèi)部并且避免邊界信息的丟失[18]。參數(shù)k是控制擴(kuò)散級(jí)別的對(duì)比度因子，k的值越大，邊緣信息丟失得越多。在本文中，參數(shù)k的值設(shè)為圖像平滑后的梯度直方圖75%百分位上的值[18]。

因?yàn)榉蔷€(xiàn)性偏微分方程沒(méi)有解析解，所以，本文先將方程式(1)離散化，轉(zhuǎn)化為如式(5)的隱式差分格式

(5)

式中：Al是表示圖像在各維度(l)上傳導(dǎo)矩陣。該方程的解如下

(6)

式中：I表示單位矩陣；m表示顯性擴(kuò)散步數(shù)；τ表示時(shí)間步長(zhǎng)。

為了能夠針對(duì)不同圖像的檢測(cè)都能保持較高的正確率，本文采用一種自適應(yīng)選取尺度空間組數(shù)的方法[18]：

構(gòu)造尺度空間，尺度級(jí)別按對(duì)數(shù)遞增，尺度參數(shù)σi為

(7)

式中：o表示組；s表示層；σ0表示尺度參數(shù)的初始值；O為總組數(shù)；S為總層數(shù)；N=O×S為整個(gè)尺度空間包含的圖像總數(shù)。O和S太大會(huì)花費(fèi)過(guò)多時(shí)間構(gòu)造尺度空間，而O和S太少會(huì)造成匹配率降低。在本文中，將S設(shè)為經(jīng)驗(yàn)值4，再按照式(8)來(lái)獲取O的值

(8)

式中：c為輸入圖像的行數(shù)，r為輸入圖像的列數(shù)；[]表示取整。

非線(xiàn)性濾波擴(kuò)散模型是以時(shí)間為單位，因此需要將離散空間內(nèi)以像素為單位的參數(shù)σi轉(zhuǎn)換為時(shí)間單位，按照式(9)求出進(jìn)化時(shí)間ti，最后將ti根據(jù)式(6)求得相應(yīng)尺度圖像

(9)

具體非線(xiàn)性尺度空間的建立流程可參見(jiàn)文獻(xiàn)[17]，最終可求得到非線(xiàn)性尺度空間的所有圖像，結(jié)果為式(10)

(10)

1.2 特征點(diǎn)提取

本文采用FAST算子來(lái)對(duì)特征點(diǎn)進(jìn)行提取，F(xiàn)AST算法的原理是若在某個(gè)待測(cè)點(diǎn)周?chē)袧M(mǎn)足一定數(shù)量的像素點(diǎn)的特征與該點(diǎn)不同，則認(rèn)為該點(diǎn)為角點(diǎn)。FAST算法具體定義請(qǐng)參見(jiàn)文獻(xiàn)[11]。在非線(xiàn)性尺度空間每一層都采用FAST算法檢測(cè)特征點(diǎn)，并將檢測(cè)得到的特征點(diǎn)所在非線(xiàn)性尺度空間的組數(shù)o與層數(shù)s記錄下來(lái)。求出候選點(diǎn)及其FAST分?jǐn)?shù)V，V是候選點(diǎn)和以它為圓心的Bresenham圓上16個(gè)像素點(diǎn)絕對(duì)偏差的和。若候選點(diǎn)的分?jǐn)?shù)V大于其同一尺度層中的8個(gè)相鄰點(diǎn)以及與其相鄰的上下尺度層中的9×2個(gè)點(diǎn)，則保留此候選點(diǎn)。

FAST算法檢測(cè)出的特征點(diǎn)不具有旋轉(zhuǎn)不變性。所以使用強(qiáng)度中心[11]的方法讓特征點(diǎn)具備方向信息：將特征點(diǎn)作為原點(diǎn)在取點(diǎn)區(qū)域U內(nèi)創(chuàng)建坐標(biāo)系，計(jì)算出特征點(diǎn)在U內(nèi)的質(zhì)心位置，以原點(diǎn)到質(zhì)心坐標(biāo)的向量方向作為特征點(diǎn)的方向，計(jì)算步驟如下所示：

區(qū)域U的矩定義為式(11)

(11)

式中：I(x,y)是圖像的灰度表達(dá)式，該矩的質(zhì)心為C=(Cx,Cy)。其中Cx=M1,0/M0,0，Cy=M0,1/M0,0，那么FAST特征點(diǎn)的方向?yàn)?/p>

θ=arctan(M0,1/M1,0)

(12)

2 特征點(diǎn)描述

在特征點(diǎn)描述上本文采用BRIEF算法[19]，BRIEF算法利用二進(jìn)制串對(duì)圖像區(qū)域進(jìn)行描述，不僅節(jié)約了存儲(chǔ)空間，而且大大減少了匹配時(shí)間。

以特征點(diǎn)為中心定義S×S大小的鄰域窗口P，在窗口內(nèi)隨機(jī)取一個(gè)點(diǎn)對(duì)(x,y)，以式(13)為準(zhǔn)則進(jìn)行二進(jìn)制賦值

(13)

式中：p(x)、p(y)分別是像素點(diǎn)x、y處的灰度值。選擇n個(gè)點(diǎn)對(duì)時(shí)，根據(jù)式(13)得到n維二進(jìn)制碼串的描述符，如式(14)所示

(14)

在本文中將n的值設(shè)置為256。由于采用二進(jìn)制碼串對(duì)圖像區(qū)域進(jìn)行描述，會(huì)產(chǎn)生噪聲敏感的問(wèn)題。為此，采用積分圖像來(lái)解決此問(wèn)題：在31×31的窗口中，隨機(jī)產(chǎn)生一對(duì)點(diǎn)對(duì)后，分別以隨機(jī)點(diǎn)為中心，兩個(gè)5×5的子窗口，然后比較兩個(gè)子窗口內(nèi)的灰度值之和的大小進(jìn)行二進(jìn)制賦值[8]。

根據(jù)以上方法的特征描述符并沒(méi)有包含方向信息，因此需要把1.2節(jié)中獲得的特征點(diǎn)方向θ作為描述符的主方向，使其具有旋轉(zhuǎn)不變性。對(duì)于(xi,yi)處的領(lǐng)域內(nèi)選取任意n個(gè)點(diǎn)對(duì)集

(15)

通過(guò)旋轉(zhuǎn)角度θ形成相應(yīng)的旋轉(zhuǎn)矩陣Rθ，構(gòu)建Sθ=RθS，這樣的BRIEF描述符便具有旋轉(zhuǎn)不變性。如式(16)所示

gn(p,θ)=fn(p)|(xi,yi)∈Sθ

(16)

通過(guò)貪婪搜索，將計(jì)算得到的所有像素點(diǎn)對(duì)中關(guān)聯(lián)性最低的n個(gè)作為具有旋轉(zhuǎn)不變性的BRIEF特征。

3 目標(biāo)匹配

本文中的目標(biāo)匹配分兩步進(jìn)行，分別為特征點(diǎn)匹配和目標(biāo)查找。

(1)特征點(diǎn)匹配。因?yàn)椴捎枚M(jìn)制碼串對(duì)特征點(diǎn)進(jìn)行描述，所以采用計(jì)算漢明距離來(lái)判斷特征點(diǎn)是否匹配。采用層次聚類(lèi)算法檢索匹配的特征點(diǎn)，尋找與查詢(xún)圖像特征描述符距離最近的樣本特征描述符，設(shè)定一個(gè)閾值Rth，當(dāng)兩者之間的距離低于Rth的時(shí)候，則認(rèn)為這兩點(diǎn)為一對(duì)匹配點(diǎn)，特征匹配。

(2)目標(biāo)查找。將查詢(xún)圖像的全部特征描述符都在訓(xùn)練樣本中進(jìn)行最近鄰查找，本文通過(guò)設(shè)定特征點(diǎn)的正確匹配率來(lái)對(duì)查詢(xún)圖像是否和樣本圖像屬于同一場(chǎng)景進(jìn)行判斷。設(shè)e為當(dāng)前查詢(xún)圖像特征點(diǎn)的總個(gè)數(shù)，nmax為樣本圖像最大匹配點(diǎn)數(shù),r為樣本圖像的匹配率，如式(17)，thd為特征點(diǎn)匹配率閾值

(17)

當(dāng)r>thd成立時(shí)，說(shuō)明查詢(xún)圖像與樣本圖像的匹配程度比較高，便可認(rèn)為查詢(xún)圖像與此樣本圖像為同一場(chǎng)景。

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

4.1 實(shí)驗(yàn)條件

計(jì)算機(jī)配置：處理器為Intel Xeon E3-1231 V3，主頻為3.4 GHz。操作系統(tǒng)為Windows 10 64位系統(tǒng)，編程環(huán)境為Visual Studio 2010與opencv 2.4.10。

實(shí)驗(yàn)數(shù)據(jù)分為兩組：一組為Mikolajczyk 05標(biāo)準(zhǔn)測(cè)試圖集，如圖1所示，該數(shù)據(jù)集分為8個(gè)子集，共有5種變換：視點(diǎn)、模糊、照度、JPEG壓縮，以及尺度和旋轉(zhuǎn)。另一組為國(guó)際圖像標(biāo)準(zhǔn)庫(kù)UKBench，如圖2所示，一共有2550個(gè)不同物體，每個(gè)物體包含了從4個(gè)不同視角拍攝的圖像，共10 200幅。

圖1 Mikolajczyk 05標(biāo)準(zhǔn)測(cè)試圖集

圖2 UKBench數(shù)據(jù)集

4.2 實(shí)驗(yàn)過(guò)程

算法流程如圖3所示，分為訓(xùn)練階段和識(shí)別階段。訓(xùn)練階段計(jì)算數(shù)據(jù)集中的圖像的特征點(diǎn)描述符存入容器中，識(shí)別階段計(jì)算查詢(xún)圖像的特征點(diǎn)描述符，然后進(jìn)行圖像匹配。

圖3 本文算法流程

4.3 算法評(píng)估

4.3.1 性能對(duì)比

將本文算法和SIFT、SURF算法進(jìn)行對(duì)比實(shí)驗(yàn)，利用圖1中的5組測(cè)試圖像，對(duì)識(shí)別算法的正確匹配率(樣本圖像最大匹配點(diǎn)數(shù)與查詢(xún)圖像特征點(diǎn)的總個(gè)數(shù)的比值)進(jìn)行對(duì)比分析。算法正確匹配率如圖4所示。對(duì)于這5種變換條件下的圖像識(shí)別結(jié)果，從匹配率看，由于本文算法的非線(xiàn)性尺度構(gòu)建以及自適應(yīng)選取尺度空間組數(shù)，在視點(diǎn)變換、縮放旋轉(zhuǎn)變換和JPEG壓縮下，正確匹配率均高于SIFT、SURF算法，而在模糊和照度變換下，本文算法略低于SIFT、SURF。本文算法相對(duì)于SIFT、SURF能得到較高的匹配率，并且在視點(diǎn)、縮放旋轉(zhuǎn)和JPEG壓縮變換下具有較高的魯棒性。

圖4 算法正確匹配率對(duì)比

4.3.2 算法訓(xùn)練時(shí)間、識(shí)別時(shí)間和識(shí)別精度對(duì)比

本文從訓(xùn)練時(shí)間、識(shí)別時(shí)間和識(shí)別精度3個(gè)方面與SIFT算法和SURF算法進(jìn)行對(duì)比。訓(xùn)練時(shí)間：訓(xùn)練開(kāi)始到訓(xùn)練結(jié)束所花費(fèi)時(shí)間；識(shí)別時(shí)間：從獲取圖片到識(shí)別結(jié)果出現(xiàn)所花費(fèi)的時(shí)間；識(shí)別精度：識(shí)別成功的次數(shù)與識(shí)別總次數(shù)的比值。

每次實(shí)驗(yàn)隨機(jī)選取不同的場(chǎng)景，每個(gè)場(chǎng)景里任意選取3個(gè)不同視角的圖片作為訓(xùn)練樣本，將剩下一張作為測(cè)試樣本。實(shí)驗(yàn)結(jié)果取100次測(cè)試的平均值。

圖5是算法訓(xùn)練時(shí)間對(duì)比。從圖5中可以看出，本文算法在訓(xùn)練中用時(shí)最少，相較于SIFT和SURF算法具有顯著優(yōu)勢(shì)，SIFT算法用時(shí)約為本文算法的15倍，SURF算法用時(shí)約為本文算法的3倍多。

圖5 算法訓(xùn)練時(shí)間對(duì)比

圖6是算法識(shí)別時(shí)間對(duì)比。從圖6中可以看出，本文算法和SURF算法的完成識(shí)別所花費(fèi)的時(shí)間都明顯少于SIFT算法，而SURF算法平均識(shí)別時(shí)間在樣本數(shù)少時(shí)與本文算法相差不多，但是當(dāng)樣本數(shù)量增多時(shí)便高于本文算法，約為本文算法的1.25倍。實(shí)驗(yàn)結(jié)果表明，本文算法在識(shí)別時(shí)間優(yōu)于另外兩種算法，且平均識(shí)別時(shí)間在0.5 s以?xún)?nèi)，具有良好的實(shí)時(shí)性。

圖6 算法識(shí)別時(shí)間對(duì)比

圖7是算法識(shí)別精度對(duì)比。由圖7可以看出，在樣本庫(kù)的數(shù)量比較小的時(shí)候，本文算法和另外兩種算法的識(shí)別精度都比較高，識(shí)別率都保持在90%以上；但隨著樣本庫(kù)的不斷增多，3種算法的識(shí)別精度都在不斷降低，其中SURF算法下降的趨勢(shì)較其它兩種算法最為明顯，本文算法識(shí)別精度稍微低于SIFT算法。實(shí)驗(yàn)結(jié)果表明，本文算法在不同大小的圖像樣本庫(kù)中都達(dá)到了較高的識(shí)別精度。

圖7 算法識(shí)別精度對(duì)比

5 結(jié)束語(yǔ)

本文提出的場(chǎng)景識(shí)別算法在特征提取方面通過(guò)構(gòu)建非線(xiàn)性尺度空間，用FAST算法對(duì)非線(xiàn)性空間每一層進(jìn)行特征點(diǎn)檢測(cè)；然后采用具有旋轉(zhuǎn)不變性的BRIEF特征描述算法進(jìn)行特征描述；在進(jìn)行目標(biāo)匹配時(shí)首先采用層次聚類(lèi)算法進(jìn)行特征點(diǎn)匹配，然后通過(guò)最近鄰算法進(jìn)行目標(biāo)查找。實(shí)驗(yàn)結(jié)果表明，本文算法在場(chǎng)景識(shí)別上展現(xiàn)了良好的效果，在視點(diǎn)變換、尺度旋轉(zhuǎn)變換和JPEG壓縮的變換下具有較強(qiáng)的魯棒性，而且在可以實(shí)現(xiàn)快速場(chǎng)景識(shí)別的同時(shí)，還能夠達(dá)到較高的識(shí)別精度。本算法也有不足之處，當(dāng)訓(xùn)練樣本數(shù)量太多時(shí)，識(shí)別時(shí)精度會(huì)下降，所以無(wú)法支持大規(guī)模場(chǎng)景識(shí)別，下一步的計(jì)劃是研究如何改善這一問(wèn)題。