賈一鑫,鄧魏永,殷 強(qiáng),毋 濤

(1.西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,陜西 西安 710699;2.華宇錚鎣集團(tuán),福建 泉州 362801;3.中國紡織工業(yè)聯(lián)合會,北京 100020)

0 引 言

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

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

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

1 相關(guān)理論

1.1 SURF算法

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

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

(1)

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

(2)

(3)

其中,x和y表示點(diǎn)X的坐標(biāo)。

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

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

(4)

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

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

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

圖2 特征點(diǎn)主方向和描述符構(gòu)造

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

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

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

1.2 DAISY描述符

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

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

圖3 DAISY描述符

1.3 隨機(jī)抽樣一致算法

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

(1)從數(shù)據(jù)集中隨機(jī)選擇一個(gè)子集作為內(nèi)點(diǎn)集合,使用該子集來估計(jì)模型的參數(shù)。

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

(3)如果當(dāng)前估計(jì)的模型內(nèi)點(diǎn)數(shù)目大于之前模型的內(nèi)點(diǎn)數(shù)目,則用當(dāng)前模型來更新內(nèi)點(diǎn)集合,并重新估計(jì)模型參數(shù)。

(4)前模型內(nèi)點(diǎn)數(shù)目小于預(yù)定義的閾值,則返回第1步。

(5)如果最大迭代次數(shù)或內(nèi)點(diǎn)數(shù)目超過某個(gè)預(yù)定義的閾值時(shí),終止算法。

最后輸出的模型參數(shù)是在所有迭代中擁有最多內(nèi)點(diǎn)的模型的參數(shù)。RANSAC算法的優(yōu)點(diǎn)在于它的魯棒性,即能夠?qū)Π罅吭肼暫彤惓Ｖ档臄?shù)據(jù)集進(jìn)行有效的模型擬合。另外,由于它是一種隨機(jī)采樣的算法,因此在不同的采樣次數(shù)下,能夠獲得不同的模型參數(shù),并能夠找到全局最優(yōu)解。

但是,RANSAC算法也存在一些缺點(diǎn)。首先,由于它是基于隨機(jī)采樣的,因此可能無法找到最優(yōu)解。其次,RANSAC算法的性能取決于內(nèi)點(diǎn)數(shù)目,而內(nèi)點(diǎn)數(shù)目與預(yù)定義的閾值有關(guān)。這個(gè)閾值可能需要根據(jù)實(shí)際情況進(jìn)行調(diào)整,這會導(dǎo)致算法的復(fù)雜性增加。

1.4 三角不規(guī)則網(wǎng)絡(luò)

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

(1)使用匹配點(diǎn)的坐標(biāo)構(gòu)建三角網(wǎng),并通過以下步驟逐一判斷三角網(wǎng)中的點(diǎn);

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

(3)基于所收集的匹配點(diǎn)的坐標(biāo),可以估計(jì)局部失真的仿射變換參數(shù);

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

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

最后,將所有獲得的關(guān)鍵點(diǎn)連接到一組匹配點(diǎn)。

2 文中算法

由于傳統(tǒng)SURF算法在特征描述階段采用高達(dá)64維的特征描述符,導(dǎo)致算法的復(fù)雜度高,計(jì)算量大,并且最終匹配結(jié)果正確率不高。因此,該文對特征描述符進(jìn)行改進(jìn),并對匹配結(jié)果進(jìn)行提純。算法流程如圖4所示。

圖4 算法流程

2.1 改進(jìn)特征描述符

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

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

(5)

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

2.2 匹配結(jié)果提純

如果使用SURF中的匹配算法進(jìn)行匹配,這樣的策略不能完全降低在特征匹配階段匹配的關(guān)鍵點(diǎn)集中出現(xiàn)錯(cuò)誤匹配和異常值的風(fēng)險(xiǎn)。

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

文中算法雖然略微增加了算法時(shí)間復(fù)雜度,但提高了經(jīng)典SURF算法在處理圖像旋轉(zhuǎn)匹配方面的能力,不僅在計(jì)算速度上保持了原始SURF算法的優(yōu)點(diǎn),而且提高了匹配精度和魯棒性。

3 實(shí)驗(yàn)結(jié)果和分析

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

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

3.1 匹配正確率分析

匹配成功率是算法的重要指標(biāo)之一,其計(jì)算方法是用成功匹配對數(shù)比正確匹配對數(shù)與錯(cuò)誤匹配數(shù)之和。分別使用SIFT算法、SURF算法、文獻(xiàn)[10]算法和文中改進(jìn)算法對同一組圖片進(jìn)行多次實(shí)驗(yàn),最后取平均值,得到每個(gè)算法的匹配正確率。

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

表1 四種算法正確率對比

圖5 四種算法對比

3.2 時(shí)間復(fù)雜度分析

時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量,公式如下:

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

(6)

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

實(shí)驗(yàn)使用上述4種算法對同一組數(shù)據(jù)進(jìn)行多次實(shí)驗(yàn),最后得到平均時(shí)間復(fù)雜度,并進(jìn)行對比分析,結(jié)果見表2。

表2 三種算法時(shí)間復(fù)雜度對比

由表2可以看出,SIFT算法非常耗時(shí),并且該算法的時(shí)間復(fù)雜度幾乎是SURF算法的三倍。傳統(tǒng)SIFT算法耗費(fèi)時(shí)間最長,文獻(xiàn)[10]算法由于對描述符降維并對匹配結(jié)果進(jìn)行了優(yōu)化,因此耗費(fèi)時(shí)長略大于原始SURF算法。文中算法采用了DAISY描述符代替SURF中的描述符,并采用隨機(jī)抽樣一致算法和TIN對匹配結(jié)果進(jìn)行優(yōu)化,雖然算法時(shí)間復(fù)雜度與傳統(tǒng)SURF算法以及文獻(xiàn)[10]算法相當(dāng),但在幾乎相同的時(shí)間內(nèi)達(dá)到了更好的效果。

3.3 魯棒性分析

為了驗(yàn)證文中算法的魯棒性,分別對實(shí)驗(yàn)圖像做光照變換和旋轉(zhuǎn)變換,如圖6所示。

圖6 光照變換和旋轉(zhuǎn)變換

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

由表3數(shù)據(jù)顯示,在實(shí)驗(yàn)圖像光照變換和旋轉(zhuǎn)變換下,文中算法的平均時(shí)間復(fù)雜度比傳統(tǒng)文獻(xiàn)[10]算法略高,但匹配精度更高。綜合考慮匹配結(jié)果和計(jì)算時(shí)間,文中算法在運(yùn)行時(shí)間略有增加的情況下,得到了更好的結(jié)果,這表明文中算法在魯棒性上比原始SURF算法以及文獻(xiàn)[10]算法更優(yōu)越。

表3 光照變換和旋轉(zhuǎn)變換對比

4 結(jié)束語

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

但是,由于增強(qiáng)現(xiàn)實(shí)對于圖像匹配算法的實(shí)時(shí)性要求很高,該算法還需要在時(shí)間復(fù)雜度上進(jìn)一步優(yōu)化,這也是未來工作的重點(diǎn)。