葉 峰,洪 崢,賴乙宗,趙雨亭,謝先治

0 引言

基于圖像不變特征的配準方法以其魯棒性好、計算量小等特點廣泛應用于計算機視覺的諸多領域,如目標識別[1]、圖片拼接[2]、影像測量[3]、立體視覺[4],以及場景重建[5]等。尺度不變特征轉換(Scale-Invariant Feature Transform, SIFT)算法[6]是諸多局部不變特征中最具代表性的算法，不過SIFT不具備完全仿射不變性。為了滿足相機大視角變化下的圖像配準需求,Morel等[7]提出了一種可以抵抗強仿射變換的仿射-尺度不變特征變換(Affine-SIFT, ASIFT)算法。ASIFT較SIFT可以獲得更多的匹配特征點；但是計算復雜度高,并且在圖像局部變形很大的情況下其匹配成功率低。

然而,在大視角變化下,即使是對于同一物體其局部紋理也很難保持不變,此外也存在著不同局部區(qū)域紋理相似的情況,這些都容易導致基于局部不變特征的算法發(fā)生誤匹配。為了擺脫局部特征只攜帶自身近鄰信息的不足,Hundelshausen等[8]在局部紋理的基礎上提出了一種基于特征點間像素分布關系的描述網(wǎng)(Descriptor-Nets, D-Nets)算法。該算法在一定程度上具備了全局特征的特點,并可獲得數(shù)量相當多而且質(zhì)量很高的匹配點對,從而克服了包括SIFT、最大穩(wěn)定極值區(qū)域(Maximally Stable Extremal Regions, MSER)[9]、Hessian-Affine[10]、Harris-Affine[11]和ASIFT等在內(nèi)的傳統(tǒng)方法對于尺度、視差和光照變化較大的圖像配準效果不佳的缺陷；但D-Nets算法時間開銷大,實用性不理想。

本文主要針對D-Nets算法的效率問題提出了一種基于匹配質(zhì)量提純的改進D-Nets算法。該算法以縮小特征點規(guī)模為基礎，以基于匹配質(zhì)量的提純方法為手段,在不顯著降低配準精度的情況下盡量提高配準效率,以滿足快速性要求。實驗結果表明,本文方法可以有效地減少特征匹配的時間開銷,尤其是在局部紋理豐富以及特征點數(shù)量較多的場景中,提升效果更加明顯。

1 D-Nets算法

D-Nets算法[8]是一種基于特征點之間灰度分布信息的特征描述和匹配算法,其主要步驟如下:首先,在模板圖像和待匹配圖像上采用FAST(Features From Accelerated Segment Test)算法進行特征點檢測,同一幅圖像里連接不同特征點間的直線段即可構成一個閉合網(wǎng)絡;然后,對各直線段上的像素點進行等距采樣,將所得采樣點的灰度值歸一化后得到直線描述子;接著,利用哈希表和投票算法對所有直線描述子進行分類和匹配,篩選出可能的匹配點對;最后,借助仿射變換或歐氏變換進行參數(shù)擬合以及匹配對提純,進而得到最終的特征點匹配對。

1.1 特征點檢測

D-Nets算法并沒有提出新的特征點檢測算法,而是利用了FAST、SIFT或者SURF(Speed-up Robust Feature)等常規(guī)算法。為了提高D-Nets算法的運行效率,一般采用時間復雜度最低且效果不錯的FAST算法。通過角點響應函數(shù)CRF可實現(xiàn)FAST特征點[12]判據(jù),如式(1)～(2)所示:

(1)

(2)

其中:I(m)是中心像素點的灰度值;I(x)是圓形區(qū)域上任意一點的灰度值;εI是灰度值之差的閾值;F是所有圓形區(qū)域上的點與中心點的響應函數(shù)值之和,當F大于一定閾值時可判定該中心點為特征點。

1.2 直線描述子

1.3 粗匹配

在確定了所有直線描述子的標記后,D-Nets算法通過哈希表和投票機制結合的方式對標記進行分類投票,遴選票數(shù)較高的匹配點對作為特征點匹配結果。其基本思想為:先遍歷所有直線描述子的標記,構建出相應的哈希表,再根據(jù)設定的匹配規(guī)則對兩幅圖像的特征點進行投票,最終找出票數(shù)較高的匹配點對。對單個標記而言,其可能的存在狀態(tài)有2(s×b)種,相應地,哈希表最多就有2(s×b)條記錄,分別對應[0,(2(s×b)-1)]內(nèi)的各個整數(shù),記兩幅圖像的哈希表分別為HI和HI ′。假設圖像I檢出的特征點為v={a1,a2,…,an},圖像I′檢出的特征點為v′={b1,b2,…,bn′},則二維投票空間的單元總數(shù)為|v|×|v′|。記G(i,j)為圖像I的特征點ai和圖像I′中的特征點bj的匹配票數(shù),當特征點ai所對應最大的匹配票數(shù)為G(i,k)時,則可將特征點ai和bk視為匹配點對,兩者之間的直線描述子可記為t(i,k)。投票機制的算法步驟如下:

G:=0

for allh∈[0,2(s×b)-1] do

L:={(m,n)|t(m,n)=h&t(m,n)∈HI}

L′:={(m′,n′)|t(m′,n′)=h&t(m′,n′)∈HI ′}

tmp=1/(|L|×|L′|)

for all (m,n)∈Ldo

for all (m′,n′)∈L′ do

G[m,m′]=G[m,m′]+tmp

G[n,n′]=G[n,n′]+tmp

end for

end for

end for

1.4 匹配提純

2 改進D-Nets算法

盡管D-Nets算法具有平移、旋轉、光照、仿射及尺度不變性,且對于存在多個相似目標的場景亦有不低的匹配成功率,但其匹配速度相對較慢,不適用于對時間指標要求較高的場合。經(jīng)研究,D-Nets算法可分為特征點提取、描述子計算、Hash投票匹配和匹配提純這四大步驟,其中以描述子計算和匹配提純最為耗時。相應地,該算法存在著以下可改進的方面:一是直線描述子計算過程的時間復雜度為O(n2),假定在某圖像中檢出2 000個特征點,那么在特征提取階段的耗時不會低于10 s;二是隨著粗匹配點對數(shù)目的增多,提純算法的內(nèi)存占用和時間開銷會迅速增長。為此,本文提出了一種改進的D-Nets算法,通過篩選特征點和采用基于匹配質(zhì)量的提純方法,使其在總體運行效率方面上有了極大的提升。該改進算法的流程如圖1所示。

2.1 特征點篩選

FAST算法能提取出大量的特征點,但其中許多特征點的分布過于密集,對后續(xù)的匹配過程貢獻不大,于是可先通過Harris角點響應值對所有特征點進行排序,只保留響應值較高的特征點作為下一步特征提取的計算對象。

Harris算法[14]的基本原理是:取以目標像素點為中心的一個掩模,并將該掩模沿上下左右四個方向進行移動,分別計算各方向上掩模內(nèi)的灰度變換,取其中的最小值作為該中心像素點的角點響應函數(shù)值R,若該值比給定閾值大,可認定為角點。在掩模內(nèi)的梯度矩陣、角點響應函數(shù)如式(3)～(4):

(3)

R=det(M)-k×trace(M)2

(4)

其中:k為常數(shù),一般取0.04;Ix、Iy分別為沿x和y方向的灰度梯度;det(M)為矩陣M的行列式;trace(M)為矩陣M的跡。

對于D-Nets算法的直線描述子匹配而言,希望能得到相對準確且分布均勻的特征點。分布不均勻的特征點不僅會帶來數(shù)據(jù)冗余,同時也增加了后續(xù)粗匹配出錯的可能性。對于特征點分布相對密集的區(qū)域,需進行二次篩選。本文采用網(wǎng)格劃分的方法實現(xiàn)特征點篩選：先將單幅影像劃分成若干個大小相同的網(wǎng)格,再挑選各網(wǎng)格內(nèi)Harris響應值較高的特征點作為有效目標點。其中,網(wǎng)格劃分的疏密程度對最終特征點的整體質(zhì)量影響頗大,若劃分后的網(wǎng)格數(shù)量過多,則不利于區(qū)分相似特征點；反之則會導致獲得的特征點數(shù)量較少。因此,對于精度要求較高的應用場合,網(wǎng)格數(shù)量須作相應的增加,而在匹配速度有限制的場景下則可適當減少,本文采用60×60的網(wǎng)格劃分方案,能獲得質(zhì)量較高且數(shù)目較多的特征點。

圖1 改進D-Nets算法流程

2.2 基于匹配質(zhì)量的提純方法

D-Nets算法采用了構建大量變換矩陣的方式進行提純,不僅增加了計算的空間復雜度和時間復雜度,而且其固定分組的方式可能會導致變換矩陣的分布相對集中,并不能遍布整個變換空間。因此,本文提出了一種基于匹配質(zhì)量的提純方法,通過計算各匹配對之間的匹配質(zhì)量,可剔除絕大部分的誤匹配點,在不明顯降低提純精度的情況下大幅縮短了提純時間。

當存在著多個匹配對時,某一匹配對的匹配質(zhì)量可通過匹配點與其余特征點分別在模板圖像和待匹配圖像中的直線描述子的相似度來描述。簡而言之,匹配質(zhì)量越高,則說明該匹配對與其他匹配對的相容程度越高,就越不可能是誤匹配。設粗匹配得到的匹配結果為S={(e1,f1),(e2,f2),…,(en,fn)},其中模板圖像的特征點集合為E={e1,e2,…,en},目標圖像的特征點集合為F={f1,f2,…,fn}。對于任意兩個匹配對Si、Sj,它們之間直線描述子的距離可通過統(tǒng)計各采樣點對應灰度值歸一化結果的差值實現(xiàn),計算公式如式(5)所示:

(5)

其中:t(ei,ej).[l]表示取特征點ei和ej之間標記的第l個采樣值。

兩匹配對之間的相似判據(jù)可定義為:

(6)

其中:ε為相似度閾值,一般取ε=2s。

對于某一匹配對Sk,其匹配質(zhì)量的計算公式如式(7):

(7)

基于匹配質(zhì)量的誤匹配剔除方法如下:循序處理各匹配對,根據(jù)式(7)求出對應的匹配質(zhì)量Q,并采用雙閾值法進行正確性判定。若Q大于設定的高閾值Qhigh,則可認定該匹配對為正確匹配;若Q小于設定的低閾值Qlow,則視其為誤匹配;而對于Q處于兩閾值Qlow和Qhigh之間(包括等于)的情況,則須重新計算其與正確匹配之間的匹配質(zhì)量,重復上述過程直至無誤。本文取Qlow=10,Qhigh=25,在匹配質(zhì)量和匹配成功率之間能取得較好的均衡。

3 實驗與分析

本文在PC平臺上實現(xiàn)了上述的改進D-Nets算法,并將其與原始D-Nets算法以及經(jīng)典的特征點匹配算法(SIFT、ASIFT等)進行了比較。實驗采用了牛津大學提供的Mikolajczyk標準圖像數(shù)據(jù)集,涉及到包括縮放、旋轉、平移、壓縮失真、視角變化、光照變化、模糊等在內(nèi)的常見圖像變換,共計8組測試數(shù)據(jù),其中每組均有6幅圖像,以graf組為例,該組測試數(shù)據(jù)如圖2所示。實際操作中以各組測試數(shù)據(jù)中的第一幅作為參考圖像,依次與組內(nèi)其余圖像進行匹配。實驗平臺配置如下:Windows 10專業(yè)版操作系統(tǒng),Intel Xeon E3-1230處理器,8 GB內(nèi)存,Visual Studio 2013開發(fā)環(huán)境。

圖2 graf組測試圖像

3.1 特征點規(guī)模實驗

為了研究特征點數(shù)量與匹配效果之間的關系,可先提取足量的特征點并根據(jù)Harris響應值進行排序,再從中篩選不同指定數(shù)目的特征點進行匹配。本次實驗主要通過有效特征點比率曲線展示最終的匹配效果,同時也通過平均各點耗時曲線展示了不同特征點規(guī)模下的時間開銷情況。其中,有效特征點比率是最終匹配對的數(shù)量與粗匹配所利用的特征點總數(shù)之比,而平均各點耗時則是總耗時與特征點總數(shù)之比。為方便描述,實驗在8組測試數(shù)據(jù)里各抽取1對圖像作為匹配對象,實驗結果如圖3～4所示,由于平均各點耗時基本相近,故只繪制具有代表性的前四組數(shù)據(jù)曲線。

圖3 有效特征點比率曲線

圖4 平均各點耗時曲線

圖5 兩種提純算法的ROC曲線

由圖3可知,有效特征點比率在區(qū)間[500,2 000]內(nèi)能保持相對較高的數(shù)值,且大部分情況下隨著特征點數(shù)量的增加,其變化程度不大;在特征點數(shù)量低于500的區(qū)間內(nèi)該值有相對劇烈的波動。與此同時,從圖4可看出,平均各點耗時與特征點數(shù)量在區(qū)間[250,2 000]內(nèi)基本上成線性增長關系;而在區(qū)間[0,250]內(nèi)由于最終的匹配點對數(shù)目過少,其變化趨勢恰恰相反。綜上所述,若能將特征點數(shù)量限制在區(qū)間[500,1 000]內(nèi),在獲得較高比例的匹配對的同時降低了整體耗時,從而保持整個算法精度與復雜度之間的平衡。

3.2 提純算法性能對比實驗

提純算法的性能主要從精度和速度兩個方面進行分析。由于提純過程能近似為二元分類問題,因此可通過受試者工作特征(Receiver Operator Characteristic, ROC)曲線體現(xiàn)其精度優(yōu)劣。特異度(False Positive Rate, FPR)和靈敏度(True Positive Rate, TPR)的定義如下:假設待檢索空間中所有樣本(特征點對)構成集合,則可以根據(jù)判定結果分為正確保留的樣本(True Positives,TP)、錯誤保留的樣本(False Positives,FP)、正確排除的樣本(True Negatives,TN)和錯誤排除的樣本(False Negatives,FN)四類。FPR、TPR分別表示為：

為了比較算法的提純性能,可分別采用原始提純算法和基于匹配質(zhì)量的改進提純方法對同一匹配點對集進行提純,各組內(nèi)三對圖像的實驗結果如圖5所示,其中每列第一幅圖像為模板圖像(圖像1),圖像對1-2、1-3、1-4指各組內(nèi)圖像1分別與圖像2、圖像3、圖像4進行匹配。

在bark和boat組主要表現(xiàn)為縮放及旋轉變換的圖像中,隨著變化程度的增加,改進提純方法與原始提純算法都能保持很高的水平。然而,在bark組最后一幅圖像中可看出改進提純方法明顯優(yōu)于原始提純算法,這得益于改進提純方法采用基于匹配質(zhì)量的誤匹配判定標準。由于該幅圖像相對原圖的縮放倍數(shù)較大,只關注空間幾何約束的算法所得的最優(yōu)變換矩陣容易產(chǎn)生計算偏差,而匹配質(zhì)量的計算不受相似變換的影響,所以基于該類約束的算法可保證一致且良好的提純效果。在leuven組主要表現(xiàn)為光照變化的圖像中,隨著環(huán)境亮度的降低,原始提純算法能保持同一水準的發(fā)揮,而改進提純方法的表現(xiàn)則有所下滑,其原因是整體亮度的變化使得各像素點之間的明暗差異變小,從而影響了匹配質(zhì)量約束的作用。對于模糊、視角變換和壓縮失真等變化的其余各組圖像,改進提純方法與原始提純算法的效果差異不大。

為了突顯改進提純方法在速度方面的優(yōu)勢,此處與原始提純算法進行提純時間上的比較。二者的時間開銷如圖6所示。

圖6 D-Nets算法改進前后的時間開銷

由圖6可看出,對于存在各種常見圖像變換的匹配過程,改進提純方法的速度均比原始提純方法快了至少一個數(shù)量級。

3.3 總體性能對比實驗

為了驗證本文提出的改進D-Nets算法的實用性,可分別與包括SIFT、ASIFT、原始D-Nets等多種算法進行對比實驗。其中,對于SIFT、ASIFT算法,將匹配距離最小的2 000個匹配對作為最終的匹配結果;在保留Harris響應值較高的1 000個特征點的基礎上,改進D-Nets方法將圖像劃分成60×60個網(wǎng)格并進行區(qū)域分塊篩選,然后在提純階段采用基于匹配質(zhì)量的提純方法,其余步驟則與原始D-Nets算法一致。改進D-Nets、原始D-Nets、SIFT、ASIFT的最終匹配精度如圖7所示。

圖7 不同算法的配準精度

由圖7可知,SIFT表現(xiàn)最差,大多數(shù)情況下只有不到60%的正確率,精度相對較低;原始D-Nets算法與ASIFT算法在某些場景時可以達到90%及以上的匹配精度,但二者隨變換程度的波動較大,個別極端條件下的精度不足40%;本文提出的改進D-Nets算法魯棒性最佳,平均匹配精度為92.2%,且最低精度保持在70%以上。以graf組的圖像1和圖像5為例,四種算法的最終匹配效果如圖8所示,可見SIFT和ASIFT算法均存在很多誤匹配,而原始D-Nets和改進D-Nets算法中絕大部分都是正確匹配。

為了比較不同算法的效率,分別統(tǒng)計各算法的時間開銷,其結果如圖9所示。從圖9可看出,原始D-Nets算法和ASIFT算法的時間開銷基本都在20 s以上,在個別情況下甚至高達100 s;SIFT算法的耗時較前兩者相對較少,但其數(shù)值波動很大,最差的情形時可至27 s;改進D-Nets算法所用時間最少,僅為2.48 s,且穩(wěn)定性最好,尤其是在局部紋理相似度較高以及特征點數(shù)量較多的場景中,效果更加明顯。

圖8 不同算法的配準結果(graf1～5)

圖9 不同算法的時間開銷

4 結語

針對原始D-Nets算法匹配效率不高的問題,本文提出了一種基于匹配質(zhì)量提純的改進D-Nets算法,通過Harris角點響應函數(shù)以及區(qū)域分塊策略對特征點進行篩選,并且設計了一種基于匹配質(zhì)量的提純方法,在不顯著降低配準精度的同時大幅減少了時間開銷。對于圖像視角變化較大且存在大量局部紋理特征相似的場景,本文算法均可保證良好的配準效果以及快速性,不僅克服了基于局部特征的配準算法的不足,而且展示了基于匹配質(zhì)量提純方法的速度優(yōu)勢。雖然本文算法相對原始算法已取得了數(shù)量級的速度提升,但對于高速實時應用該算法的優(yōu)化實施仍需進一步探討,采用GPU硬件加速和FPGA并行處理是下一步工作的主要方向。

參考文獻(References)

[1] 陳娟娟, 劉財興, 高月芳, 等. 基于改進特征袋模型的奶牛識別算法[J]. 計算機應用, 2016, 36(8): 2346-2351.(CHEN J J, LIU C X, GAO Y F, et al. Cow recognition algorithm based on improved bag of feature model[J]. Journal of Computer Applications, 2016, 36(8): 2346-2351.)

[2] KIM J, KIM T, SHIN D, et al. Fast and robust geometric correction for mosaicking UAV images with narrow overlaps [J]. International Journal of Remote Sensing, 2017, 38(8/9/10): 2557-2576.

[3] CHO B, KIM Y C. Recognition of urban buildings by SIFT matching with Google street view images [C]// RACS 2016: Proceedings of the 2016 International Conference on Research in Adaptive and Convergent Systems. New York: ACM, 2016: 46-50.

[4] BUSAM B, ESPOSITO M, CHEROSE S, et al. A stereo vision approach for cooperative robotic movement therapy [C]// ICCV 2015: Proceedings of the 2015 IEEE International Conference on Computer Vision. Piscataway, NJ: IEEE, 2015: 519-527.

[5] ZHOU Q, KOLTUN V. Dense scene reconstruction with points of interest [J]. ACM Transactions on Graphics, 2013, 32(4): Article No. 112.

[6] LOWE D G. Distinctive image features from scale-invariant keypoints [J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[7] MOREL J M, YU G S. ASIFT: a new framework for fully affine invariant image comparison [J]. SIAM Journal on Image Sciences, 2009, 2(2): 438-469.

[8] HUNDELSHAUSEN M, SUKTHANKAR R. D-Nets: beyond patch-based image descriptors [C]// CVPR 2012: Proceedings of the 2012 IEEE International Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2012: 2941-2948.

[9] MATAS J, CHUM O, URBAN M, et al. Robust wide-baseline stereo from maximally stable extremal regions [J]. Image Vision Computing, 2004, 22(10): 761-767.

[10] MIKOLAJCZYK K, SCHMID C. An affine invariant interest point detectors [C]// ECCV 2002: Proceedings of the 7th European Conference on Computer Vision Copenhagen, LNCS, 2350. Berlin: Springer, 2002: 128-142.

[11] MIKOLAJCZYK K, SCHMID C. Scale & affine invariant interest point detectors [J]. International Journal of Computer Vision, 2004, 60(1): 63-86.

[12] 高晶, 陳莉, 蘭小艷, 等. 基于FAST特征點提取的圖像拼接算法[J]. 西北大學學報(自然科學版), 2016, 46(3): 351-357.(GAO J, CHEN L, LAN X Y, et al. Image mosaic algorithm based on the FAST feature points extraction [J]. Journal of Northwest University (Natural Science Edition), 2016, 46(3): 351-357.)

[13] QUIST E B, NIEDFELDT P C, BEARD R W. Radar odometry with recursive-RANSAC [J]. IEEE Transactions on Aerospace and Electronic Systems, 2016, 52(4): 1618-1630.

[14] 曾新貴, 陶衛(wèi), 顏發(fā)才, 等. 基于Harris算子和方向場的圖像配準算法[J]. 計算機應用, 2016, 36(增刊1): 146-148.(ZENG X G, TAO W, YAN F C, et al. Image registration algorithm based on Harris operator and direction field[J]. Journal of Computer Applications, 2016, 36(S1): 146-148.)

This work is partially supported by the Special Fund for Public Welfare Research and Capacity Building of Guangdong Province (2016A010106005), the Project of Ministry of Education on the Integration of Industry, Education and Research in Guangdong Province (2012A090300013).