基于非線性尺度空間的增強現實場景識別算法

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

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

0 引 言

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

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

1 基于非線性尺度空間的特征點提取

1.1 非線性尺度空間的建立

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

通常利用非線性偏微分方程對非線性擴散濾波方法進行描述，如式(1)

(1)

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

(2)

(3)

(4)

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

因為非線性偏微分方程沒有解析解，所以，本文先將方程式(1)離散化，轉化為如式(5)的隱式差分格式

(5)

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

(6)

式中：I表示單位矩陣；m表示顯性擴散步數；τ表示時間步長。

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

構造尺度空間，尺度級別按對數遞增，尺度參數σi為

(7)

式中：o表示組；s表示層；σ0表示尺度參數的初始值；O為總組數；S為總層數；N=O×S為整個尺度空間包含的圖像總數。O和S太大會花費過多時間構造尺度空間，而O和S太少會造成匹配率降低。在本文中，將S設為經驗值4，再按照式(8)來獲取O的值

(8)

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

非線性濾波擴散模型是以時間為單位，因此需要將離散空間內以像素為單位的參數σi轉換為時間單位，按照式(9)求出進化時間ti，最后將ti根據式(6)求得相應尺度圖像

(9)

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

(10)

1.2 特征點提取

本文采用FAST算子來對特征點進行提取，FAST算法的原理是若在某個待測點周圍有滿足一定數量的像素點的特征與該點不同，則認為該點為角點。FAST算法具體定義請參見文獻[11]。在非線性尺度空間每一層都采用FAST算法檢測特征點，并將檢測得到的特征點所在非線性尺度空間的組數o與層數s記錄下來。求出候選點及其FAST分數V，V是候選點和以它為圓心的Bresenham圓上16個像素點絕對偏差的和。若候選點的分數V大于其同一尺度層中的8個相鄰點以及與其相鄰的上下尺度層中的9×2個點，則保留此候選點。

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

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

(11)

式中：I(x,y)是圖像的灰度表達式，該矩的質心為C=(Cx,Cy)。其中Cx=M1,0/M0,0，Cy=M0,1/M0,0，那么FAST特征點的方向為

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

(12)

2 特征點描述

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

以特征點為中心定義S×S大小的鄰域窗口P，在窗口內隨機取一個點對(x,y)，以式(13)為準則進行二進制賦值

(13)

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

(14)

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

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

(15)

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

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

(16)

通過貪婪搜索，將計算得到的所有像素點對中關聯性最低的n個作為具有旋轉不變性的BRIEF特征。

3 目標匹配

本文中的目標匹配分兩步進行，分別為特征點匹配和目標查找。

(1)特征點匹配。因為采用二進制碼串對特征點進行描述，所以采用計算漢明距離來判斷特征點是否匹配。采用層次聚類算法檢索匹配的特征點，尋找與查詢圖像特征描述符距離最近的樣本特征描述符，設定一個閾值Rth，當兩者之間的距離低于Rth的時候，則認為這兩點為一對匹配點，特征匹配。

(2)目標查找。將查詢圖像的全部特征描述符都在訓練樣本中進行最近鄰查找，本文通過設定特征點的正確匹配率來對查詢圖像是否和樣本圖像屬于同一場景進行判斷。設e為當前查詢圖像特征點的總個數，nmax為樣本圖像最大匹配點數,r為樣本圖像的匹配率，如式(17)，thd為特征點匹配率閾值

(17)

當r>thd成立時，說明查詢圖像與樣本圖像的匹配程度比較高，便可認為查詢圖像與此樣本圖像為同一場景。

4 實驗結果與分析

4.1 實驗條件

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

實驗數據分為兩組：一組為Mikolajczyk 05標準測試圖集，如圖1所示，該數據集分為8個子集，共有5種變換：視點、模糊、照度、JPEG壓縮，以及尺度和旋轉。另一組為國際圖像標準庫UKBench，如圖2所示，一共有2550個不同物體，每個物體包含了從4個不同視角拍攝的圖像，共10 200幅。

圖1 Mikolajczyk 05標準測試圖集

圖2 UKBench數據集

4.2 實驗過程

算法流程如圖3所示，分為訓練階段和識別階段。訓練階段計算數據集中的圖像的特征點描述符存入容器中，識別階段計算查詢圖像的特征點描述符，然后進行圖像匹配。

圖3 本文算法流程

4.3 算法評估

4.3.1 性能對比

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

圖4 算法正確匹配率對比

4.3.2 算法訓練時間、識別時間和識別精度對比

本文從訓練時間、識別時間和識別精度3個方面與SIFT算法和SURF算法進行對比。訓練時間：訓練開始到訓練結束所花費時間；識別時間：從獲取圖片到識別結果出現所花費的時間；識別精度：識別成功的次數與識別總次數的比值。

每次實驗隨機選取不同的場景，每個場景里任意選取3個不同視角的圖片作為訓練樣本，將剩下一張作為測試樣本。實驗結果取100次測試的平均值。

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

圖5 算法訓練時間對比

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

圖6 算法識別時間對比

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

圖7 算法識別精度對比

5 結束語

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