改進SIFT的圖像匹配算法

陳雪松,武小凱

(東北石油大學 電氣信息工程學院,黑龍江 大慶 163318)

0 引 言

圖像匹配是計算機視覺和圖像處理的重要基礎(chǔ)之一[1]。圖像匹配是指在圖像與圖像之間,經(jīng)過特定的算法,識別出圖像之間同名點的過程[2]。圖像匹配技術(shù)在遙感、醫(yī)療、全景影像、三維重建和圖像拼接等領(lǐng)域具有較為廣泛的應(yīng)用[3-6]。然而一般情況下,圖像經(jīng)常會受到旋轉(zhuǎn)、光照、模糊等因素影響圖像之間的匹配效果[7]。因此,如何快速且穩(wěn)定地對圖像進行匹配,逐漸成為圖像匹配的一個重要發(fā)展趨勢。

目前,較為常用的算法有Harris、SIFT(Scale-Invarivant Feature Transform)、SURF(Speeded-Up Robust Features)、FAST(Features from Accelerated Segment Test)、ORB(Oriented FAST and Rotated BRIEF)等,這幾種算法在使用中各有優(yōu)勢和特點[8]。其中SIFT算法是由David[9]于2004年提出,該算法在不同尺度下或圖像發(fā)生旋轉(zhuǎn)的情況下,匹配效果依然十分出色,而且對光線、視角以及噪聲變化均有很好的匹配效果。在某些場景中,由于紋理信息過于豐富,會在局部產(chǎn)生大量的無用特征點,影響運行速度；SIFT特征描述符具有128維向量,導致計算過于復雜,使匹配效率降低。針對上述情況,Mikolajczyk等[10]提出了GLOH描述子,使用對數(shù)極坐標代替坐標象限;Bay等[11]提出的SURF算法Hessian 矩陣行列式近似值圖像代替DOG(Difference of Gaussian)圖像,降低了運算量;馮政壽等[12]提出利用Harris算法提取的角點作為特征點,對特征點使用同心圓描述符,提高了匹配效率;李為民等[13]提出了對Harris改進的角點指示器,可根據(jù)需求檢測不同數(shù)量角點；趙小強等[14]提出了基于Harris角點與SIFT的快速圖像匹配算法,提高了圖像匹配的實時性；胡育誠等[15]提出了消除冗余性能的策略,并對SIFT算子進行改進,提升特征點檢測的時間效率。

筆者針對SIFT算法計算量大,實時性差的問題,分別對特征點與特征描述符進行改進,提出了一種Harris算法與SIFT算法相結(jié)合的方法。在一定程度上降低了SIFT算法的計算量,提升了匹配效率。

1 SIFT算法流程

1.1 尺度空間和極值點定位

為使從圖像中提取的特征點具備尺度不變性,進行特征點檢測時應(yīng)在不同的尺度中進行。將圖像I(x,y,σ)與不同尺度的高斯核函數(shù)G(x,y,σ)卷積得到高斯金字塔L(x,y,σ),如下

L(x,y,σ)=G(x,y,σ)*I(x,y,σ)

(1)

(2)

將高斯金字塔中相鄰尺度的高斯圖像作差得到高斯差分金字塔(DOG)。如下

D(x,y,σ)=(G(x,y,kσ)-D(x,y,σ))*I(x,y,σ)=L(x,y,kσ)-L(x,y,σ)

(3)

將差分金字塔中的每個像素與其相鄰的26個點(8+9×2=26)比較,判斷其是否為極值點。

1.2 特征點主方向

特征點確定主方向,是為減小描述符由于圖像旋轉(zhuǎn)等所帶來的負面影響。采用

(4)

(5)

可計算出像素點的梯度和方向。在每個特征點的鄰域范圍內(nèi)統(tǒng)計0360°之間的36個方向(每10°為一個方向)的梯度直方圖,取梯度直方圖峰值的方向作為特征點的主方向。

1.3 生成描述向量

將坐標軸旋轉(zhuǎn)至上述特征點的主方向上。以特征點為中心點,取16×16的窗口區(qū)域。平均分為4×4=16個子塊區(qū)域(種子點)。根據(jù)式(4)和式(5)統(tǒng)計出每個種子點在8個方向(每45°為一個方向)的梯度直方圖,并對每個梯度直方圖進行高斯加權(quán),以減弱遠離特征點的地方對特征點的影響。每個特征點的描述向量為4×4×8=128維。

2 Harris-SIFT算法

由于Harris算法提取的角點具有高穩(wěn)定性,為此筆者將Harris算法與SIFT算法相結(jié)合,流程如圖1所示。

圖1 筆者算法流程圖Fig.1 Algorithm flowchart

2.1 特征點定位

首先對輸入的圖像使用Harris算法檢測出角點,再對圖像進行SIFT特征點檢測,若SIFT特征點與Harris算法檢測的特征點之間小于閾值,則該SIFT特征點作為筆者的特征點[14]。雖然會增加特征點提取的時間,但篩選得到的SIFT特征點將會同時具有Harris特征點的高穩(wěn)定性,且減少了后續(xù)算法的時間。閾值如下

(6)

其中σoct為Harris角點所在尺度。

2.2 改進的描述符

圖2 改進的描述符Fig.2 Improved descriptor

筆者采用圓形描述符,由于圓形具有旋轉(zhuǎn)不變性,故無需確定特征點主方向。以關(guān)鍵點為圓心,取半徑為11的圓形窗口為特征點鄰域范圍,將該領(lǐng)域分別以半徑為1、2、3、4、5、7、9、11個像素劃分為8個同心圓,即8個種子點。統(tǒng)計每個同心圓上8個方向(每45°為一個方向)的像素梯度與方向。每個特征向量具有8×8=64個特征向量,并對特征向量進行排序,描述符如圖2所示。為防止距離特征點較遠的像素對描述符的影響過大,采用高斯窗口進行加權(quán)。為減小由于光照變化對匹配效果產(chǎn)生負面影響,采用歸一化對特征向量進行處理。

2.3 特征匹配

筆者采用最近鄰距離(min)與次近鄰距離(secmin)的比值(min/secmin)作為匹配依據(jù)[16]。閾值一般設(shè)置為0.6～0.8之間,數(shù)值越小,誤匹配率越低,匹配點對也將變少。筆者將閾值設(shè)置為0.6。由于在匹配中經(jīng)常發(fā)生誤匹配的情況,筆者采用RANSAC(RANdom SAmple Consensus)算法對特征點進行提純[17]。

3 實驗結(jié)果與分析

對筆者所提出的算法與SIFT算法進行圖像匹配實驗,并對結(jié)果進行對比與分析。圖3a和圖3b分別為SIFT算法和筆者算法提取的特征點。筆者算法相較于SIFT算法,特征點的數(shù)量有所減少,但特征點大部分為角點,提高了特征點的穩(wěn)定性。

圖3 提取的特征點Fig.3 Extracted feature points

表1為兩種匹配算法的統(tǒng)計結(jié)果。圖4和圖5分別為SIFT算法和改進SIFT算法的的匹配效果。使用兩種算法分別進行20組以上的圖像匹配,求出每次平均所使用時間?？梢钥闯?筆者算法與原SIFT算法相比節(jié)約大約1/3的時間,誤匹配率比SIFT算法有所降低。

圖4 SIFT算法匹配結(jié)果 圖5 改進SIFT算法匹配結(jié)果 Fig.4 SIFT algorithm matching result Fig.5 Improved SIFT algorithm matching result

表1 實驗結(jié)果Tab.1 Experimental results

從該實驗中,可得出以下兩點結(jié)論。

1) 筆者算法相較于SIFT算法減少了特征點的數(shù)量。且筆者算法提取的特征點大部分為圖像角點,增加了特征點的穩(wěn)定性,保障了算法的精確度。

2) 筆者采用的64維描述符相比于SIFT算法的128維描述符,降低了描述符維度,減少了算法的復雜度。誤匹配率有所下降。整體所用時間減少了大約1/3,提高了特征匹配的實時性。

4 結(jié) 語

針對SIFT算法復雜的情況,筆者使用Harris算法與SIFT算法相結(jié)合的方式提取特征點,篩選出在Harris特征點附近的SIFT特征點作為筆者特征點,使用64維圓形描述符代替SIFT算法的128維高維向量,有效的降低了算法復雜度。經(jīng)實驗證明,筆者算法相比于SIFT算法在一定程度上提高了運行速度,降低了算法的復雜度,且誤匹配率有所降低。