基于SURF的改進FLANN匹配算法

張志敏，李 彬+，田聯房，丁煥文

(1.華南理工大學 自動化科學與工程學院，廣東 廣州 510641；2.華南理工大學 醫學院，廣東 廣州 510006)

0 引 言

計算機輔助骨科手術系統有卓越的表現，受到各國骨科醫生的高度重視[1]，同時諸多研究結果表明在計算機輔助骨科手術中應用增強現實技術[2](augmented reality，AR)具有非常高的臨床應用價值。AR技術的實現依賴于視頻圖像，需要對其中的目標進行檢測匹配跟蹤。但由于視頻圖像中復雜目標、光線及視角變化等因素影響，使得視頻圖像的目標檢測匹配成為了一個頗具挑戰的問題。研究人員為解決這一難題提出了許多不同的視頻圖像匹配方法，其中基于SURF[3,4]特征點匹配方法最適合于視頻圖像匹配。近些年，很多學者對SURF特征點做了大量的研究，提出了不同的改進方法。Shene等[5]改進了SURF特征點的提取步驟；Oszust等[6]對SURF特征點的描述符算子進行了改進；Feng等[7]提出了改進的匹配方法。但這些改進的算法僅適用于簡單的圖像特征點匹配或者視頻的個別幀圖像匹配，無法直接應用到視頻連續的幀圖像中。

基于上述背景，本文針對視頻圖像匹配提出了一種基于SURF特征點的改進FLANN[8,9]匹配算法。首先改進了SURF特征點的描述符算子，然后以FLANN算法為基礎，結合隨機抽樣一致性(random sample consensus,RANSAC)算法，剔除大量誤匹配、無用的特征點，從而大幅提高匹配速度。經實驗驗證，本方法的穩定性及快速性較好，能夠在計算機輔助骨科手術系統中實現AR的過程，有效輔助醫生對骨科手術患者中病灶區域的定位。

1 基于SURF特征點的改進FLANN視頻圖像匹配算法概述

本文提出的基于SURF特征點的改進FLANN圖像匹配算法。算法的流程如圖1所示。

圖1 基于SURF特征點的FLANN視頻圖像匹配算法流程

2 基于改進的SURF特征點提取

SURF是SIFT的加速版，具有旋轉尺度不變特征，其不但能測出圖像中的關鍵點，穩定描述關鍵點的局部信息，而且理論上是SIFT算子速度的3倍。

2.1 基于Hessian矩陣行列式的特征點提取

提取SURF特征點的過程，首先是用圖像的Hessian矩陣行列式構成SURF尺度空間，用非極大值抑制提取特征點。特征點受Hessian行列式閾值的影響，閾值越大得到的特征點的魯棒性越好，實際中需要適當的調整閾值。

2.2 改進的SURF特征點描述符

在復雜的視頻圖像匹配中，由于匹配對圖像特征點描述的局部信息依賴性較高，單個特征點不足以描述該特征點的局部區域信息。針對此問題，在不改變SURF特征點原有的旋轉尺度不變性的前提下，本文提出了改進的特征點描述符，在特征向量中加入了特征點4-領域內的特征點描述符信息。

在構成的SURF尺度空間中提取到的特征點，用f0表示該特征點原有的描述符。在圖像中該特征點的4個方向距離10 s(s為特征點所在的尺度)的特征點分別用f1、f2、f3、f4表示。為了使該特征點能夠更準確地描述局部信息，構建特征點4-領域的描述符f1、f2、f3、f4都使用f0的主方向，以確保特征點的旋轉不變性。然后由該特征點及其它4個特征點描述符構建新的描述符，作為特征點的特征向量，表示為v={f0,f1,f2,f3,f4}。新構成的特征點不僅保留SURF特征點原有的旋轉尺度不變性，還加大對局部信息的描述，對復雜的目標有更大的區分度。

3 基于SURF特征點的改進FLANN匹配算法

SURF特征點的匹配主要是通過Lowe等提出的FLANN算法來匹配，該算法是通過判斷兩特征點的歐氏距離來確定匹配度。然而FLANN算法的匹配速度并不滿足視頻圖像匹配的需求。因此本文提出了一種改進的FLANN搜索算法，在原來的基礎上結合RANSAC算法，剔除無匹配、誤匹配的特征點，進一步提升匹配速度。

FLANN匹配算法需要兩兩計算求出最佳匹配點對，其中誤匹配、不相關的特征點也參與到計算，而RANSAC算法則需要對特征點進行多次迭代，求出概率最大的模型，均不符合視頻圖像匹配快速性的要求。因此本文提出了一種改進的FLANN算法，其結合了RANSAC算法的思想來剔除大部分不相關的特征點以達到快速匹配的效果。在現實場景中圖像常被檢測出大量無用的SURF特征點，在提取SURF特征點之前先對原視頻圖像序列進行下采樣，以減少一部分不必要的特征點。其次在計算兩點的歐氏距離之前先利用他們的跡做初步篩選，特征點跡的符號相同即表示兩特征點具有相同方向上的對比度變化。改進算法的流程如圖2所示。

圖2 改進的FLANN算法流程

改進的FLANN匹配算法步驟如下：

(1)在原來的FLANN算法中，利用RANSAC[10]算法增加特征點的匹配先驗信息，以減少大量的配對計算。首先根據前一幀圖像求得的匹配點對，利用RANSAC算法求出配對點之間的映射關系；

原來的RANSAC算法是通過迭代循環找出一個數據集的模型。RANSAC每次迭代都隨機選取4組特征點計算出它們的映射關系，統計符合該映射的特征點。迭代一定次數后選出符合特征點數量最多的模型作為最終模型。

將RANSAC算法加入到FLANN算法中。由于前一幀已經求得最佳的配對點，故不需要迭代，只需從前一幀中配對好的特征點選出4組即可求出映射矩陣H。其中的映射關系如式(1)所示

(1)

其中，(x′,y′)是特征點(x,y)的映射點坐標，H是映射矩陣。映射矩陣H的求解可將式(1)展開，得到式(2)

(2)

將式(2)整理可得式(3)

(3)

由于變換矩陣H可進行任意尺度縮放，故令h33=1。每組匹配的特征點可以得到兩個方程組，因此通過4組特征點可得4組方程(3)，即可算出矩陣H的8個參數，得到矩陣H。求得映射矩陣進入步驟(3)。

若當前幀是視頻的第一幀或者上一幀沒找到配對點則跳過這步進入步驟(3)，直接用原來的FLANN算法求配對點。

(2)在FLANN算法中，根據RANSAC算法增加了配對點的預測區域，在局部區域搜索配對點。通過計算特征點p0(x0,y0)的預測配對點，以該預測點的30領域作為配對點的預測區域。首先通過式(1)計算出p0的映射點坐標，然后優先在映射點的30領域內搜索配對點，找到與p0點領域內有最小歐氏距離的配對點。

假設兩個m維特征向量分別為p(xp1,xp2,…,xpm)、q(xq1,xq2,…,xqm)，則他們的歐氏距離Dpq如式(4)所示

(4)

在p0的映射點領域內有很大概率可以找到最小歐氏距離小于100的最佳配對點，因為通常前后一幀圖像移動范圍會比較小。否則進入步驟(3)和步驟(4)繼續調用原來的FLANN算法搜索剩余的特征點。

(3)在進行FLANN算法匹配之前，先對特征點的跡符號歸類，以進一步篩選配對點，減少配對計算量。判斷兩個特征點的跡符號是否相同，若符號相同再進行下一步，否則跳過歐氏距離計算直接判為不同點，如式(5)所示

(5)

(4)FLANN算法的核心是計算兩特征點的歐氏距離。通過判斷距離某SURF特征點最小歐氏距離和次小歐氏距離的比值是否低于某閾值，來篩選該特征點是否存在唯一的匹配點。可通過式(6)進一步篩選特征點匹配對

(6)

式中：Dpq為距離特征點p的最小歐氏距離，Dpk為距離特征點p的次小歐氏距離。T為比率閾值，本文經過多次實驗得出T=0.6最為合適。

使用改進的FLANN算法進行特征點匹配時，只要視頻畫面不是高速移動，該算法都可以找到特征點對應的配對點。高速移動也會出現視頻丟幀或幀模糊的情況，這種情況也無法找到相應的配對點。

4 三維模型的構建與位姿估計誤差

4.1 三維模型的構建與初始化

本文用于匹配的三維模型是實際患者的三維骨骼模型，是由醫學圖像DICOM序列經過一系列的解析、處理后，通過Marching Cubes[11]面繪制算法構成的，它可以反應出患者的真實信息，為輔助醫師診斷提供更多的信息。

得到的三維模型結果由于其原點坐標不在其中心位置，旋轉、平移等操作不繞其中心位置變化，人機交互性很差，因此在匹配初始化時，首先加載三維模型，并對其坐標初始化，使原點在其中心位置。初始化主要是將三維模型的每個三角形面片中心Ci與對應的三角形面片的面積Si的乘積累加求和，再除以總的三角形面積的加和S便得到模型的中心C。如式(7)所示

(7)

然后將每個三角形面片的頂點坐標減去中心位置C，得到三維模型新的坐標，即可在不改變三維模型的形狀、相對位置的情況下將其坐標同一化。本文提出的算法是通過手動選取初始特征點，因此在初始化時，首先要確定三維模型世界坐標空間中的4個坐標點，然后在二維圖像中選取對應的點才能做進一步的目標跟蹤。

4.2 三維模型的位姿估計誤差

在二維圖像與三維模型上選取了4組匹配的特征點后，經過PNP問題[12-14]的求解，可以得到三維模型世界空間坐標系的旋轉矩陣R和平移矩陣t，即可在實時渲染三維模型時對目標進行相應的旋轉和平移，最終在二維屏幕上表現出相應的姿態。

三維模型的位姿估計會出現誤差，主要是來源于三維模型的初始化位置、二維圖像特征點的匹配跟蹤的誤差以及三維模型位姿求解誤差。三維模型的位姿估計結果是求得旋轉矩陣R和平移矩陣t，其旋轉誤差計算需要將旋轉矩陣R轉換為對應的旋轉角度(θx,θy,θz)，如式(8)所示

(8)

式中：rij是旋轉矩陣的第i行第j列的元素。然后按式(9)計算旋轉誤差ER和式(10)計算平移誤差Et

(9)

(10)

5 結果討論

本文通過實驗驗證提出算法的穩定性和快速性。為了模擬手術場景，實驗所采用的三維模型是由軍區總醫院提供的脊柱CT經三維重建得到的模型，并將對應的三維模型3D打印出來，用于替代手術中的患者。實驗中使用的攝像機是鈺創免驅攝像頭驅動2012版：分辨率是640*480，最大幀率：50 Hz，視頻編碼格式：YUY2/MJPG。實驗的硬件環境為：CPU Intel(R)Core(TM)i5-3230M，主頻2.60 Ghz；內存8.00 GB。軟件環境為：Microsoft Visual Studio 2013、Qt5.60。

5.1 實驗結果

為了驗證結果，實驗一共使用10組不同的人體脊柱三維模型來驗證本文提出的算法。

5.1.1 實驗數據

所使用的CT圖像序列是由廣州軍區總醫院提供的脊椎CT圖像序列，如表1所示，每個序列切片數量約為200～500張。部分CT切片效果如圖3所示。

表1 脊柱CT圖像序列數據

圖3 CT序列圖像

5.1.2 實驗結果

三維模型由上一節所述的CT圖像序列，通過項目組開發平臺算法Marching Cubes面繪制算法構成，結果如圖4所示。實際使用的三維模型是通過3D打印技術生成的三維模型。

圖4 三維重建平臺

使用本文提出的匹配算法對攝像機中的目標進行匹配跟蹤，并估計目標的三維位姿，實時渲染三維模型。實驗使用10組不同的三維模型驗證本文提出的算法，部分效果如圖5所示。

圖5 現實場景目標與三維模型的匹配效果

其中圖5(a)和圖5(c)是使用一個假的骨骼模型來模擬現實手術中的患者，與本實驗室的一個數字三維模型進行匹配，效果如圖5(b)和圖5(d)所示，可以實現匹配跟蹤效果。

而圖5(e)、圖5(g)、圖5(i)、圖5(k)的實際模型是通過項目組平臺生成的三維模型，然后將對應的三維模型通過3D打印技術打印出來，實際縮放尺寸均在133*100*200 mm上下浮動，材質是光敏樹脂。將數字三維模型與對應的實體模型用于驗證該算法，其匹配效果分別如圖5(f)、圖5(h)、圖5(j)、圖5(l)所示。對比結果圖5中的每組圖像，可以發現數字三維模型與現實的模型匹配度非常高，實驗結果表明了提出算法的有效性，具體的匹配定量分析將在5.5節分析。

5.2 SURF中不同的Hessian矩陣行列式閾值對結果的分析與對比

在SURF特征的提取中，Hessian行列式閾值h是篩選特征點的主要依據，h值越大，特征點的數量越少且越穩定，魯棒性越好。但是當特征點的數量太少時，有可能會出現局部位置特征點較少或者沒有的情況，進而導致較后面的幀圖像丟失該區域的匹配特征點；而特征點數量太多則會影響匹配速度，降低視頻的幀率。本節針對不同的h值進行多組實驗，取結果的平均值，見表2。根據表2的實驗結果，畫出匹配的特征點個數與h值的關系以及匹配時間與匹配的特征點個數的關系曲線，如圖6、圖7所示。

表2 不同的Hessian行列式閾值的SURF特征點匹配結果

圖6 匹配的特征點個數與Hessian行列式閾值的關系

圖7 匹配時間與SURF特征點個數的關系

由表2可見，以及綜合圖6、圖7的實驗結果，在理想情況下，特征點個數是隨著h值的增大而減少，而匹配時間也會隨著特征點個數的減少而降低。在本研究中既要保證穩定性，也要保證快速性，因此在SURF特征點的個數要從具體實驗中測試，來選擇適中的個數。

對比以上兩圖可以發現，h值為2000和2500時，特征點數量不多也不少，而且匹配速度也比較快。考慮到特征點的分布(圖8)，h值為2500時，部分區域的特征點非常稀疏，從穩定性方面考慮，選擇最優的h值為2000，在保證穩定性的同時不失快速性。

圖8 不同的Hessian行列式閾值時SURF特征點的分布

5.3 FLANN算法最鄰近距離與次鄰近距離的比值閾值T對匹配結果的影響

通過特征點的最近鄰距離與次近鄰距離的比值來篩選錯誤的匹配點對。為了選出最適合的閾值T，在實驗中截取兩幀圖像，改變閾值T，分析不同的T值對匹配結果的影響。由于FLANN算法匹配的特征點對比較多，難以一一驗證每組配對點是否正確匹配，故通過特征點配對連線效果圖觀察有無錯誤配對特征點，來判斷是否最優的T值。配對效果如圖9所示。

圖9 不同的閾值T的特征點匹配連線效果

雖然無法直接統計特征點的正確匹配率，但通過觀察特征點配對連線圖，可以發現隨著T值減小錯誤的匹配對逐漸減少。當T=0.7時還存在少數的錯誤配對，T=0.6時已無錯誤配對，T小于0.6時配對的特征點數逐漸減少。在T=0.6時，使用不同的實體模型進行特征點匹配，也無錯誤的特征點匹配，其效果如圖10所示。因此，在確保準確配對時T=0.6是最優的閾值。

圖10 不同模型的特征點匹配連線效果

5.4 改進的FLANN算法匹配結果與其它算法的分析與對比

為了驗證本文改進的FLANN算法的有效性及快速性，在實驗中用SURF特征點的匹配時間和匹配成功率作為匹配評估指標，并且與前人改進的算法做對比實驗。在同一實驗環境下，并采用相同的視頻圖像數據，測試上述不同算法的性能指標。實驗中使用10組模型，每組模型使用攝像機連續截取100幀視頻圖像，測試得到結果并取平均值，見表3。

表3 不同的匹配算法的性能指標

提出的算法與對比的算法都是先得到粗配對的結果，經過算法篩選才得到正確的配對，匹配成功率是通過最終成功配對的數量除以初配對的數量得到的。特征點對是否正確匹配是通過觀察它們的匹配連線圖來判斷的。

由表3可見，文獻[7]中算法的FLANN算法是直接通過最近鄰與次近鄰的比值來篩選最佳匹配特征點，特征點配對時進行全局特征點匹配，需要配對的特征點總數比較多，導致匹配耗時較長，且匹配正確度不高；而文獻[15]算法使用RANSAC策略來剔除無效的特征點，雖提高了匹配正確度，但找出最佳的RANSAC模型需要進行多次迭代，導致匹配耗時更長。本文提出的改進FLANN算法，首先選取待匹配的局部區域(如圖11每個圖的左圖)，然后根據上一次匹配的結果計算出兩幀之間的映射關系，找出配對特征點的預測區域，最后在預測的局部區域搜索匹配特征點，因此減少大量的無用特征點匹配，比前兩者的匹配速度快，而且也有較高的匹配成功率。實驗結果表明了本文改進的FLANN算法對視頻圖像匹配的快速性。

圖11 改進的FLANN算法匹配

5.5 三維模型位姿估計誤差的定量分析

為了進一步驗證提出算法的準確性，通過三維模型位姿估計的誤差來評估，采用10組不同的三維模型(數字三維模型與打印的三維模型，部分如圖5(e)、5(g)、5(i)、5(k)所示)，在實驗室中測量模型的真實旋轉角度與平移量的平均值，通過式(9)、式(10)來計算三維模型位姿估計的誤差，結果如圖12所示。由于是手工測量實際的旋轉平移量，其旋轉角度的測量精度是±1°，平移精度是5 mm，取多個測量值的平均值作為結果。

由圖12、圖13可見，位姿估計的誤差確實存在的，但其誤差相對三維模型的尺寸來說影響不大，最終的視覺效果(圖5)在可控制的范圍內。減少誤差主要從以下幾方面考慮：①初始化選點時，二維圖像目標要與三維模型準確對應；②盡量保持環境光線明亮，提高特征點匹配率；③平穩移動攝像機，保證不丟失目標；④提高攝像機的分辨率，提高特征點描述符的辨識度。

圖12 位姿估計的角度誤差

圖13 位姿估計的平移量誤差

6 結束語

本文針對視頻圖像匹配提出了基于SURF特征點的改進FLANN算法，該算法是基于上一幀的匹配結果，利用RANSAC算法的改進FLANN匹配算法，先找到特征點匹配的預測區域，然后在預測區域進行特征點搜索，避免了大量無用特征點的匹配，從而提高匹配效率。實驗結果表明，本文提出的算法對視頻圖像匹配的穩定性及快速性。目前該算法在目標低速移動的視頻匹配有良好的表現，下一步的研究主要進一步優化提出的算法，并將該算法應用到快速移動的視頻圖像中。