基于改進SURF的增強現實圖像匹配方法

賈一鑫,鄧魏永,殷 強,毋 濤

(1.西安工程大學 計算機科學學院,陜西 西安 710699;2.華宇錚鎣集團,福建 泉州 362801;3.中國紡織工業聯合會,北京 100020)

0 引 言

隨著計算機視覺的飛速發展,增強現實技術[1](Augmented Reality,AR)在多個領域得到廣泛應用,包括游戲娛樂[2]、教育培訓[3]和工業制造[4]等。其中,圖像匹配技術是AR最基本的一步,其基本原理就是將攝像頭捕獲的圖像中提取的關鍵點和特征描述子與預先建立好的數據模型中的關鍵點及特征描述子進行匹配,最終得到匹配結果。

Lowe提出了SIFT[5](Scale-Invariant Feature Transform)算法,該算法能夠在不同的光照、旋轉、縮放等變換下提取出相同的特征點,因此在計算機視覺和圖像處理領域得到廣泛應用。但是此算法仍有很多不足,如算法復雜度高、計算量大、匹配成功率低、花費時間長等。Herbert Bay等在2006年提出了SURF[6](Speeded-Up Robust Features)算法,在計算機視覺和增強現實等領域得到廣泛應用。盡管SURF算法在匹配速度和穩健性方面表現良好,但在一些特殊情況下,例如場景發生劇烈變化或存在光照變化時,其匹配精度仍然有待進一步提高。因此,研究人員提出了許多改進SURF的算法,旨在提高其匹配精度和魯棒性。黃春鳳等[7]提出了一種改進SURF算法,該算法采用近鄰搜索算法實現Kd-Tree快速查找最近鄰特征點,最后用雙向唯一性匹配的方法完成特征匹配,雖然該算法降低了時間復雜度并提高了匹配精度,但是魯棒性有待提高。Liu等[8]提出了一種改進RANSAC特征圖像匹配方法,雖然提高了匹配精度,但是算法的時間復雜度較高。Gu等[9]提出了一種用于大旋轉角估計的數字圖像相關的改進SURF方法,此方法用新的收斂閾值從參考圖像和變形圖像中細化初始參數,并提出了一種由多環模板發展而來的評估標準來計算特征點對的相似性,以提高收斂速度和采樣精度,但是該算法的時間復雜度相對于傳統算法沒有提高。鄒玉英等[10]提出一種用SURF算法來提取待匹配圖像特征點,之后對SURF的度描述符降維,用KNN算法雙向匹配特征點,再使用RANSAC算法剔除錯誤匹配的匹配算法,此算法提高了匹配精度,但是匹配效率較差。

針對以上問題,該文提出了一種基于SURF算法的改進圖像匹配算法。首先,對SURF算法中的特征描述子進行改進,對于匹配結果,用RANSAC[11]去除極端異常值;然后,使用基于三角不規則網絡(TIN)[12]局部估計來去除其余虛假匹配,從而提高其匹配精度和魯棒性。

1 相關理論

1.1 SURF算法

SURF算法采用Hessian矩陣行列式近似值圖像,也就是DOH算子,替代了SIFT的DOG算子[13]。該算法繼承了SIFT算法的魯棒性,并且改進了其特征提取部分,大大縮短了SIFT算法的計算時間[14]。SURF算法主要包括以下三個步驟。

第一步:特征檢測。首先,建立積分圖像,I∑(x)表示位于位置(x,y)處像素上方的左側的輸入圖像的像素總和,其公式如下:

(1)

然后,用Box濾波器取代二階高斯濾波器開始檢測和定位特征點,目的是降低計算成本,Box濾波器的原理就是利用模板近似高斯二階偏導數,如圖1(a)所示。通過以上兩步可以求得尺度空間函數。與SIFT的高斯差分金字塔不同,SURF建立尺度空間是不需要進行高斯模糊。SURF特征點定位的核心是Hessian矩陣,公式如下:

(2)

(3)

其中,x和y表示點X的坐標。

接著,用多向BOX濾波器進行卷積得到Dxx,Dxy,Dyy,替換Hessian矩陣中的Lxx,Lxy,Lyy,從而得到SURF快速Hessian矩陣,其公式如下:

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

(4)

然后,在3×3×3尺度空間中應用非極大值抑制,如圖1(b)所示,在尺度空間中所選點的26個鄰居中的極值點被視為SURF特征點,其對源圖像的尺度是不變的。

圖1 盒式濾波和非極大值抑制

第二步:特征描述。每個SURF特征點的主要方向由x和y方向上的高斯分布加權的Haar小波卷積表示。Haar小波模板如圖2所示。

圖2 特征點主方向和描述符構造

以當前特征點為中心,半徑為6σ(σ是濾波器的大小)的滑動π/3扇窗,以掃描此處的圓形區域的小波響應,如圖2(a)所示,小波響應之和最大的扇形被確定為特征主方向。

完成之后開始構建特征描述符。在確定當前特征點的主方向后,構建一個正方形采樣區域,接著,將這個采樣區域劃分為16個子區域,并進一步將每個子區域劃分為25個樣本網格,并從Haar小波卷積中獲得每個子區域的x軸和y軸正負方向上的四個描述符。隨后,獲得SURF特征點的64維描述符,如圖2(b)所示。

第三步:特征匹配。對于參考圖像和待匹配圖像,分別執行步驟一和二。使用對應的描述符來計算兩個圖像中的所有SURF特征點之間的歐幾里得距離d。d的最小值和次最小值分別定義為最短距離d1和第二短距離d2。如果比率d1/d2低于指定的閾值,則可以獲得一對匹配點。所有SURF特征點都是以這種方式獲得的,并且所有特征點都形成了匹配特征集。

1.2 DAISY描述符

盡管SURF算法的速度比SIFT算法的速度快三到四倍,但是與局部特征算子的性能相比,SURF算法的魯棒性較差[15]。

DAISY[16]描述符是一種局部特征描述符。它由一些中心對稱的圓構成,如圖3所示,以原點為中心,構建一個三層同心圓,每層包含8個采樣點,并且這些點呈45度分布[17]。且每個采樣點具有相同的高斯尺度值,隨著與原點的距離越來越大,高斯尺度值也逐漸增大。這種結構使得DAISY描述符對圖像的仿射變換和光照變化具有良好的魯棒性。

圖3 DAISY描述符

1.3 隨機抽樣一致算法

RANSAC算法[11]是一種高度魯棒的估計技術,通過去除給定數據集中的異常值來擬合任何給定模型。它主要基于隨機投票原理計算模型參數,即使在存在大量異常值的情況下也能高效計算,并能魯棒地處理多種結構數據[18]。下面是RANSAC算法的主要步驟:

(1)從數據集中隨機選擇一個子集作為內點集合,使用該子集來估計模型的參數。

(2)對于數據集中的所有其他點,計算它們與估計的模型之間的誤差。將所有與該模型擬合誤差小于某個預定義閾值的點視為內點,其他點視為外點(離群點)。

(3)如果當前估計的模型內點數目大于之前模型的內點數目,則用當前模型來更新內點集合,并重新估計模型參數。

(4)前模型內點數目小于預定義的閾值,則返回第1步。

(5)如果最大迭代次數或內點數目超過某個預定義的閾值時,終止算法。

最后輸出的模型參數是在所有迭代中擁有最多內點的模型的參數。RANSAC算法的優點在于它的魯棒性,即能夠對包含大量噪聲和異常值的數據集進行有效的模型擬合。另外,由于它是一種隨機采樣的算法,因此在不同的采樣次數下,能夠獲得不同的模型參數,并能夠找到全局最優解。

但是,RANSAC算法也存在一些缺點。首先,由于它是基于隨機采樣的,因此可能無法找到最優解。其次,RANSAC算法的性能取決于內點數目,而內點數目與預定義的閾值有關。這個閾值可能需要根據實際情況進行調整,這會導致算法的復雜性增加。

1.4 三角不規則網絡

三角不規則網絡(TIN)也可用于剔除誤匹配對,算法原理如下:

(1)使用匹配點的坐標構建三角網,并通過以下步驟逐一判斷三角網中的點;

(2)基于TIN結構收集當前判斷點周圍的幾個最近的相鄰點。通過迭代方法確定相鄰點:首先,收集與判斷點相鄰的所有點,然后找到更多與所收集的點相鄰的點,并不斷地收集這些點;

(3)基于所收集的匹配點的坐標,可以估計局部失真的仿射變換參數;

(4)使用先前獲得的仿射參數來計算判斷點的殘差。如果誤差大于某個閾值,則判斷點及其對應點被消除為假匹配。否則,進入步驟(2)來判斷下一點;

(5)在遍歷三角網中的所有點之后,返回步驟(1),使用剩余的點重建新的三角網[12]。該過程繼續進行,直到所有點的殘余誤差滿足要求為止。

最后,將所有獲得的關鍵點連接到一組匹配點。

2 文中算法

由于傳統SURF算法在特征描述階段采用高達64維的特征描述符,導致算法的復雜度高,計算量大,并且最終匹配結果正確率不高。因此,該文對特征描述符進行改進,并對匹配結果進行提純。算法流程如圖4所示。

圖4 算法流程

2.1 改進特征描述符

SURF算法在特征描述階段獲得特征主方向后,使用DAISY描述符替代SURF中的64維描述符,與SIFT和SURF使用矩形鄰域不同,DAISY描述符使用圓形鄰域,因為圓形鄰域具有更好的定位特性。DAISY算子采用高斯核卷積完成梯度直方圖加權,由于高斯核存在各向同性,無需重復計算梯度直方圖。由圖3可知,每隔45度取一個采樣點,共得到25個采樣點。DAISY描述符可較容易獲得旋轉不變性,因此該文選擇DAISY描述符替換SURF算法的描述符。DAISY描述符的基本流程如下。

首先,原始圖像上像素的八個方向梯度可以表示為Lxy*Dxy,其中Dxy表示梯度方向。然后,通過多次高斯卷積可以獲得同心圓中每層的采樣點高斯卷積值。對于每個像素,可以獲得長度為8的向量來表示局部梯度方向直方圖,用Hxy表示。因此,可以得到DAISY的描述符方程,其表示如下:

(5)

其中,?H表示每層的方向,x表示以像素為中心的同心圓上采樣點的坐標。最終獲得的特征向量包含8個維度,兩個向量的歐幾里得距離用于測量描述符之間的相似性,如果低于設定的閾值,則可以獲得一堆匹配點。

2.2 匹配結果提純

如果使用SURF中的匹配算法進行匹配,這樣的策略不能完全降低在特征匹配階段匹配的關鍵點集中出現錯誤匹配和異常值的風險。

因此,大多數匹配策略采用RANSAC算法或其變體來減少失配。然而,這種算法無法準確處理復雜的局部失真,尤其是當圖像比較大或目標需要精確匹配時[19]。因此,對于2.1獲得的匹配點對,該文首先應用RANSAC算法來去除極端異常值,然后使用基于三角不規則網絡(TIN)的局部估計[12]去除其余虛假匹配。

文中算法雖然略微增加了算法時間復雜度,但提高了經典SURF算法在處理圖像旋轉匹配方面的能力,不僅在計算速度上保持了原始SURF算法的優點,而且提高了匹配精度和魯棒性。

3 實驗結果和分析

實驗平臺為MATLAB R2020b,實驗環境為DELL G15 5511,Intel Core i7-11800H 2.3 GHz,8核心16線程,GPU為NVIDIA GeForce RTX 3060 Laptop 6G (GDDR6 Micron),16 GB內存,操作系統為64位Windows 11。實驗數據采用兩張分辨率為2 641×3 519的書的圖片。

為驗證文中算法的性能,進行了對比實驗,分別使用SIFT算法、SURF算法、文獻[10]算法以及文中改進算法進行測試,如圖5所示。并從匹配正確率、算法所用時間和魯棒性三個方面進行驗證分析。

3.1 匹配正確率分析

匹配成功率是算法的重要指標之一,其計算方法是用成功匹配對數比正確匹配對數與錯誤匹配數之和。分別使用SIFT算法、SURF算法、文獻[10]算法和文中改進算法對同一組圖片進行多次實驗,最后取平均值,得到每個算法的匹配正確率。

從表1可知,SIFT算法獲得了最多的匹配點,相較于SIFT算法,SURF算法的正確率較低且匹配點數量較少。該文提出的算法直接使用DAISY描述符來替代原始SURF算法的描述符,降低了描述符維度,相對于SURF算法和文獻[10]算法,在平均正確率和平均正確匹配點數方面有較大的改進。這表明在相同的特征點檢測和主方向確定的情況下,使用DAISY描述符進行匹配比原始SURF描述符效率更高,并且使用RANSAC算法加TIN算法處理得到的結果正確率更高。

表1 四種算法正確率對比

圖5 四種算法對比

3.2 時間復雜度分析

時間復雜度是指執行算法所需要的計算工作量,公式如下:

T(n)=O(f(n))

(6)

其中,n為問題規模,T(n)為時間復雜度,f(n)和程序執行時間成正比,O表示程序執行的階。

實驗使用上述4種算法對同一組數據進行多次實驗,最后得到平均時間復雜度,并進行對比分析,結果見表2。

表2 三種算法時間復雜度對比

由表2可以看出,SIFT算法非常耗時,并且該算法的時間復雜度幾乎是SURF算法的三倍。傳統SIFT算法耗費時間最長,文獻[10]算法由于對描述符降維并對匹配結果進行了優化,因此耗費時長略大于原始SURF算法。文中算法采用了DAISY描述符代替SURF中的描述符,并采用隨機抽樣一致算法和TIN對匹配結果進行優化,雖然算法時間復雜度與傳統SURF算法以及文獻[10]算法相當,但在幾乎相同的時間內達到了更好的效果。

3.3 魯棒性分析

為了驗證文中算法的魯棒性,分別對實驗圖像做光照變換和旋轉變換,如圖6所示。

圖6 光照變換和旋轉變換

圖6中(a)和(b)分別表示使用文獻[10]算法和文中算法在光照變換和旋轉變換下的匹配結果。

由表3數據顯示,在實驗圖像光照變換和旋轉變換下,文中算法的平均時間復雜度比傳統文獻[10]算法略高,但匹配精度更高。綜合考慮匹配結果和計算時間,文中算法在運行時間略有增加的情況下,得到了更好的結果,這表明文中算法在魯棒性上比原始SURF算法以及文獻[10]算法更優越。

表3 光照變換和旋轉變換對比

4 結束語

針對原始SURF算法匹配精度較差、魯棒性不強等缺點,提出了一種改進SURF算法。首先用原始算法的Hessian矩陣進行特征點檢測和提取,然后計算原始圖像的梯度方向圖像,用DAISY描述符替代SURF算法的描述符,最后使用RANSAC算法結合TIN算法對匹配結果進行剔除和優化。實驗結果表明,該算法雖然略微增加了時間復雜度,但卻大大提高了原始SURF算法的魯棒性和匹配精度。

但是,由于增強現實對于圖像匹配算法的實時性要求很高,該算法還需要在時間復雜度上進一步優化,這也是未來工作的重點。