一種無標(biāo)識圖像的FLANN-LM配準(zhǔn)算法

張乃千，王占剛

(北京信息科技大學(xué) 信息與通信工程學(xué)院，北京 100192)

0 引言

增強(qiáng)現(xiàn)實(shí)(augmented reality，AR)是一種實(shí)時地將攝像機(jī)角度、位置及相應(yīng)圖像、視頻、3D模型疊加計算的新興領(lǐng)域，用來完善用戶與現(xiàn)實(shí)世界交互的感官體驗(yàn)。傳統(tǒng)的增強(qiáng)現(xiàn)實(shí)大多使用基于人工標(biāo)識的跟蹤注冊技術(shù)，需要檢測有一定特征的標(biāo)志物。雖然能較好地抵抗干擾，但是應(yīng)用范圍受到大幅限制。

3D跟蹤注冊技術(shù)是增強(qiáng)現(xiàn)實(shí)技術(shù)的根本，而其關(guān)鍵技術(shù)是提取與匹配特征點(diǎn)，所以，尋找一種同時兼顧旋轉(zhuǎn)不變性、尺度不變性又伴隨魯棒性強(qiáng)、精確性高、實(shí)時性好的特征檢測匹配算法是增強(qiáng)現(xiàn)實(shí)系統(tǒng)不可或缺的存在。早期的 Harris角點(diǎn)檢測[1]實(shí)時性、魯棒性好，但不具備尺度不變性；Lee等[2]提出了基于尺度不變特征SIFT(scale-invariant feature transform)算子的特征檢測算法，較好地解決了圖像在不同尺寸、旋轉(zhuǎn)、光照等條件下的匹配失敗問題，但速度很慢；Chen等[3]提出了加速穩(wěn)健特征SURF(speed up robust features)算子，在一定程度上提高了處理速度，但降低了準(zhǔn)確性；Michael Calonder 等[4]提出了BRIEF (binary robust independent elementary features)算法，該算法高效簡單，但易受噪聲影響，不具備尺度不變性及旋轉(zhuǎn)不變性；Rublee[5]提出了ORB (ORIENTED BRIef) 算法，這是一種高效的二進(jìn)制局部特征描述算子，ORB算法雖在速度上有了很大提升，卻仍然沒有解決好圖像光照、紋理變化對注冊精度的影響；Alexandre Alahi 等[6]提出 了FREAK算法，該二進(jìn)制描述符以人類視網(wǎng)膜獲取圖像為基礎(chǔ)，利用由模糊到清晰、掃視搜索的匹配方法，更好地滿足了對光照、旋轉(zhuǎn)等變化的適應(yīng)性，同時完善了對于實(shí)時性的追求。在上述算法的基礎(chǔ)上，本文以圖像在自然特征下的虛實(shí)注冊為基礎(chǔ)，運(yùn)用SURF算法提取特征點(diǎn)，使用FREAK算法描述圖像特征點(diǎn)，利用FLANN-LM算法匹配特征點(diǎn)，完成整個增強(qiáng)現(xiàn)實(shí)系統(tǒng)的跟蹤注冊過程，并在此基礎(chǔ)上完成三維模型的融合疊加。

1 提取特征點(diǎn)

攝像頭采集到圖像后首先運(yùn)用SURF算法提取特征點(diǎn)，F(xiàn)REAK算法描述特征點(diǎn)，接著運(yùn)用FLANN算法粗匹配，最后運(yùn)用LM算法剔除錯誤匹配點(diǎn)提升匹配精度。圖像識別與匹配算法流程如圖1所示。

圖1 圖像識別與匹配算法流程

1.1 SURF特征點(diǎn)檢測及尺度空間的構(gòu)建

SURF算法利用H(X,σ)檢測圖像特征點(diǎn)[7]。圖像I(x,y)中，尺度為σ的點(diǎn)x的Hessian矩陣為

(1)

式中Lxx、Lxy、Lyy為二階微分算子。

為簡化計算，SURF算法利用尺度圖像積分獲取高斯二階微分函數(shù)的近似結(jié)果，組成圖像金字塔，完成多尺度空間的構(gòu)建[8]。其中，用加權(quán)的9×9框狀濾波器模板Dxx、Dxy、Dyy代替原來的二階微分算子，其中圖形積分過程如圖2所示。

圖2 高斯濾波器與框狀濾波器

簡化后的Hessian矩陣的行列式為

det(H)=DxxDyy-(0.9Dxy)2

(2)

Hessian矩陣的跡為

tr(H)=Dxx+Dyy

(3)

確定特征點(diǎn)的位置可以采用非極大值抑制[9]。為簡化計算，求主曲率D與特征值的比值rratio。假設(shè)最大特征值記為α，最小特征值記為β，且α=rβ，則比值rratio可表示為

(4)

1.2 FREAK特征描述子

FREAK算法是根據(jù)人眼識別物體提出的，其描述子的采樣點(diǎn)與視網(wǎng)膜結(jié)構(gòu)類似，采樣點(diǎn)和特征點(diǎn)分別均勻分布在小圓和大圓圓心上。FREAK描述子每個圓圈代表一塊感受野，重疊的感受野可以獲取更多信息，具有更好的性能。

由于FREAK特征描述子是由0、1組成的二進(jìn)制描述符，采樣點(diǎn)的二值描述[10]可以通過對比采樣點(diǎn)附近一組點(diǎn)對的強(qiáng)度得到：

(5)

(6)

為保證算法具有旋轉(zhuǎn)不變形性，一般以梯度作為特征點(diǎn)主方向，特征點(diǎn)方向集合如圖3所示。

圖3 特征點(diǎn)方向集合

特征點(diǎn)計算方法如下：

(7)

2 FLANN-LM配準(zhǔn)圖像

2.1 FLANN匹配搜索

Hamming距離[11]是比較等長字符串上不同字符數(shù)量，即特征描述子間的相似程度，因此可以用Hamming距離衡量配準(zhǔn)圖像與參考圖像間的關(guān)系。由于匹配的準(zhǔn)確性與閾值T有關(guān)，根據(jù)參考文獻(xiàn)[12]對快速二進(jìn)制高維最近鄰FLANN算法的描述，其關(guān)鍵在于快速找到特征點(diǎn)的近鄰點(diǎn)。若最近鄰與次近鄰的特征點(diǎn)p、q的歐式距離用Dp和Dq表示，則Dp與Dq的比值為Dr=Dp/Dq。將該比值與閾值T作比較，若Dr小于T則匹配成功，否則匹配失敗。FLANN匹配算法在保證匹配精度的同時，能有效減少計算量，提高匹配速度。

2.2 求解相機(jī)內(nèi)外參數(shù)值

根據(jù)攝像機(jī)的成像模型可知[13]，若一個二維點(diǎn)坐標(biāo)m=[u,v]T和一個三維點(diǎn)M=[X,Y,Z]T存在投影關(guān)系，則該三維點(diǎn)M與其圖像投影點(diǎn)m的關(guān)系可以表示為

(8)

增強(qiáng)現(xiàn)實(shí)系統(tǒng)中[14]，使用相機(jī)模型建立二維圖像點(diǎn)與相機(jī)視覺三維空間點(diǎn)的聯(lián)系。轉(zhuǎn)換模型共涉及4種坐標(biāo)系，世界坐標(biāo)系(XwYwZw)可以從現(xiàn)實(shí)世界中獲得，相機(jī)坐標(biāo)系(XcYcZc)以相機(jī)光心為原點(diǎn)，圖像坐標(biāo)系(OIXY)以圖像平面的中心為原點(diǎn)。整個轉(zhuǎn)換過程如圖4所示。

圖4 坐標(biāo)系的相互轉(zhuǎn)換

根據(jù)上述坐標(biāo)系變換，可得到世界坐標(biāo)系與圖像坐標(biāo)系間的轉(zhuǎn)換關(guān)系

(9)

式中：fx、fy、u0、v0為攝像機(jī)的內(nèi)部參數(shù)；M為內(nèi)參矩陣。該矩陣實(shí)現(xiàn)了二維坐標(biāo)與三維坐標(biāo)間的轉(zhuǎn)換。

由于標(biāo)定棋盤位于世界坐標(biāo)系中的Zw=0平面[15]，因此，可將式(8)按照式(9)的形式改寫成

(10)

其中，矩陣H為世界坐標(biāo)系轉(zhuǎn)換到圖像坐標(biāo)系3×3的單應(yīng)性矩陣：

(11)

式中1為歸一化后的結(jié)果。這樣矩陣只包含8個未知數(shù)，達(dá)到了簡化計算的目的。將式(11)代入式(8)化簡可得：

(12)

根據(jù)式(12)化簡可得：

(13)

式中：

(14)

將式(13)用Ah=0的矩陣形式描述，要想求解H至少需要4組對應(yīng)的世界坐標(biāo)系點(diǎn)和圖像坐標(biāo)系點(diǎn)，但在真實(shí)場景中計算點(diǎn)對會包含如像素偏差或特征點(diǎn)匹配錯誤等噪聲，一般都會選取遠(yuǎn)大于4組匹配點(diǎn)對求解單應(yīng)性矩陣。由于單硬性矩陣的求解過程中涉及到最優(yōu)解求解問題，因此運(yùn)用非線性最小二乘法[16]優(yōu)化誤差函數(shù)，得到單硬性矩陣H。

2.3 LM算法剔除錯誤匹配點(diǎn)

LM(levenberg-marquardt)算法是在高斯牛頓算法的基礎(chǔ)上得到的，是梯度下降算法與高斯牛頓算法的結(jié)合，該算法穩(wěn)定性高[17]、速度快，適合運(yùn)用在對實(shí)時性要求高的增強(qiáng)現(xiàn)實(shí)系統(tǒng)中。

用最大似然估計最小化真實(shí)值與標(biāo)定點(diǎn)間的差異后，建立優(yōu)化目標(biāo)函數(shù)

(15)

為了減小圖像標(biāo)定點(diǎn)ECi與圖像實(shí)測點(diǎn)Ci位置的噪聲誤差，本文通過求解迭代增量確定單應(yīng)性矩陣的最優(yōu)解，并判斷該特征點(diǎn)是否可以作為匹配特征點(diǎn)。根據(jù)LM算法將迭代增量改寫為

Xn+δxn?

(16)

在迭代過程中，給定初始值k=0，ε0=10-3。判斷得到的Δhlm是否使得誤差減小，若減小則保留；將ε除以10，否則將ε乘以10，重新求解方程，直到誤差減小為止。

LM算法進(jìn)一步剔除了誤配的特征點(diǎn)，圖像匹配的準(zhǔn)確性得到了良好的改善，有助于提升圖像虛實(shí)融合的精度。

通過優(yōu)化得到的單應(yīng)性矩陣及已經(jīng)標(biāo)定的攝像機(jī)內(nèi)參A可以很容易地求解攝像機(jī)外參：

(17)

式中：A為攝像機(jī)內(nèi)參矩陣；h1、h2、h3為單應(yīng)性矩陣；r1、r2、r3是正交旋轉(zhuǎn)矩陣R的參數(shù)；T為平移變換矩陣。

3 實(shí)驗(yàn)仿真及運(yùn)行結(jié)果

本文的實(shí)驗(yàn)環(huán)境：電腦Intel(R)CPU為Core (TM)i7-2600，主頻為3.40 GHz，內(nèi)存4.00 GB，win7系統(tǒng), 以Visual Studio 2013為主要平臺，利用OpenCV圖像處理工具、OpenGL三維圖形庫進(jìn)行開發(fā)，并配合使用Unity3D加入FBX三維模型文件，最終完成基于FLANN-LM配準(zhǔn)算法的虛實(shí)融合實(shí)驗(yàn)。

3.1 目標(biāo)識別與匹配效果實(shí)驗(yàn)

在特征點(diǎn)的提取與匹配實(shí)驗(yàn)中，對同一幅圖像改變旋轉(zhuǎn)角度、遮擋特征點(diǎn)，比較本文算法與傳統(tǒng)SURF- RANSAC、SURF-FREAK-RANSAC算法得到的匹配效果。

圖像旋轉(zhuǎn)時，特征點(diǎn)匹配效果如圖5所示。

圖5 圖片旋轉(zhuǎn)時不同配準(zhǔn)算法比較

從圖5可以看出，圖像發(fā)生旋轉(zhuǎn)時，傳統(tǒng)SURF方法經(jīng)過RANSAC處理后，匹配到的特征點(diǎn)數(shù)量較少，不適合增強(qiáng)現(xiàn)實(shí)系統(tǒng)的應(yīng)用。SURF-FREAK-RANSAC雖然部分提升了特征點(diǎn)匹配的準(zhǔn)確性，但在圖像旋轉(zhuǎn)時，錯誤匹配點(diǎn)沒有剔除干凈。而用本文算法匹配特征點(diǎn)，匹配精度較前2種算法明顯提高。

遮擋部分圖像特征，特征點(diǎn)匹配效果如圖6所示。

圖6 圖片遮擋時不同配準(zhǔn)算法比較

從圖6可以看出，圖像發(fā)生遮擋時，經(jīng)過RANSAC處理的圖像特征點(diǎn)匹配數(shù)量少，不利于增強(qiáng)現(xiàn)實(shí)系統(tǒng)虛實(shí)融合實(shí)驗(yàn)的進(jìn)行。使用SURF-FREAK-RANSAC匹配特征點(diǎn)準(zhǔn)確性明顯提高，但仍有個別特征點(diǎn)匹配錯誤，導(dǎo)致增強(qiáng)現(xiàn)實(shí)系統(tǒng)的三維模型無法正確疊加。而本文算法的匹配準(zhǔn)確性及抗干擾性較前2種傳統(tǒng)算法有明顯提高，更有利于圖像進(jìn)行虛實(shí)融合。

比較本文算法與傳統(tǒng)方法在圖片旋轉(zhuǎn)、遮擋的平均時間及匹配準(zhǔn)確率，對比結(jié)果如表1所示。

表1 算法性能對比

從表1可以看出，本文算法SURF-FREAK-FLANN- LM在運(yùn)行速度上比傳統(tǒng)的SURF-RANSAC算法提高約2倍，比SURF-FREAK-RANSAC方法提升約1.4倍，匹配的準(zhǔn)確性更是達(dá)到了91.2%，滿足了增強(qiáng)現(xiàn)實(shí)系統(tǒng)對實(shí)時性和穩(wěn)定性的要求。

3.2 虛實(shí)融合疊加實(shí)驗(yàn)結(jié)果

完成圖5、圖6特征點(diǎn)的匹配與剔除后，對該識別圖進(jìn)行三維疊加，實(shí)現(xiàn)增強(qiáng)現(xiàn)實(shí)渲染，論證本文方法的可行性。

實(shí)驗(yàn)共分為3組，第一組：不增加任何干擾且不增加紋理直接識別圖片，驗(yàn)證實(shí)驗(yàn)的可行性。第二組：圖片發(fā)生旋轉(zhuǎn)并給模型增加紋理貼圖。第三組：圖片發(fā)生遮擋并給模型增加紋理貼圖。

無干擾無紋理直接識別圖片，并疊加不同的三維模型，虛實(shí)注冊結(jié)果如圖7 所示。

圖7 直接識別圖片疊加三維模型效果

為驗(yàn)證本文算法的可行性，即更清晰看出三維模型和要識別的物體，本組實(shí)驗(yàn)分別將無紋理的椅子模型、仙人掌模型及電腦模型疊加到識別圖的側(cè)面位置。從圖7可以看出，本方法可以很好地完成增強(qiáng)現(xiàn)實(shí)系統(tǒng)的虛實(shí)融合實(shí)驗(yàn)。

旋轉(zhuǎn)角度發(fā)生變化時，虛實(shí)注冊結(jié)果如圖8所示。

圖8 圖片發(fā)生旋轉(zhuǎn)三維模型疊加效果

圖8是識別圖順時針或逆時針旋轉(zhuǎn)90度時，識別并疊加三維模型的虛實(shí)融合效果，根據(jù)實(shí)驗(yàn)結(jié)果可以看出改變識別圖旋轉(zhuǎn)角度仍可以很好地實(shí)現(xiàn)跟蹤注冊。

特征點(diǎn)發(fā)生遮擋時，虛實(shí)注冊結(jié)果如圖9所示。

圖9 圖片發(fā)生遮擋三維模型疊加效果

圖9為特征點(diǎn)發(fā)生遮擋時的跟蹤注冊效果，以白色紙條為遮擋物，在遮擋一部分特征點(diǎn)時，以上3幅圖仍可以很好地實(shí)現(xiàn)增強(qiáng)現(xiàn)實(shí)系統(tǒng)的虛實(shí)渲染實(shí)驗(yàn)。

本文方法在改變圖片旋轉(zhuǎn)角度和遮擋特征點(diǎn)的情況下均能較好地實(shí)現(xiàn)圖像的虛實(shí)融合。另外，除了抗干擾性能的提升，系統(tǒng)的實(shí)時性也得到了有效地改善，能更好地滿足不同實(shí)驗(yàn)對象的應(yīng)用條件。

4 結(jié)束語

為了加強(qiáng)人類對于真實(shí)世界的感官體驗(yàn)，本文以實(shí)現(xiàn)不同對象的增強(qiáng)現(xiàn)實(shí)應(yīng)用為背景，改善增強(qiáng)現(xiàn)實(shí)系統(tǒng)匹配效果差和運(yùn)行速率慢的問題。本文提出以SURF算法為依據(jù)，配合使用FREAK算法描述特征點(diǎn)，利用FLANN及LM算法剔除錯誤特征點(diǎn)，完成特征點(diǎn)的匹配與篩選，實(shí)現(xiàn)特征圖的識別與疊加。實(shí)驗(yàn)證明，該算法具有較好的抗干擾性、穩(wěn)定性及實(shí)時性，適用于圖像自然特征的虛實(shí)融合場景，以此完善用戶對現(xiàn)實(shí)世界與虛擬世界的交互體驗(yàn)，具有一定的參考與應(yīng)用價值。