趙春暉，樊斌，田利民，胡勁文，潘泉

西北工業(yè)大學(xué) 自動(dòng)化學(xué)院，西安 710072

視覺(jué)同時(shí)定位與構(gòu)圖(SLAM)的初始化階段需要利用特征匹配進(jìn)行三角化得到3D點(diǎn)云[1-2]，特征匹配的準(zhǔn)確率和召回率的高低直接影響著3D點(diǎn)云的數(shù)量和3D坐標(biāo)的準(zhǔn)確性，進(jìn)而影響相機(jī)位姿的估計(jì)精度。

BF(Brute Force)算法[3]通過(guò)計(jì)算2幅圖像特征點(diǎn)描述子之間的歐式距離，找到最接近的特征點(diǎn)作為候選匹配。但是，由于虛假的檢測(cè)，最接近的特征點(diǎn)可能不是真正匹配的特征點(diǎn)。為解決該問(wèn)題，F(xiàn)LANN(Fast Library for Approximate Nearest Neighbors)算法[4-5]被提出。它利用比率測(cè)試來(lái)驗(yàn)證候選匹配特征點(diǎn)對(duì)，以剔除虛假匹配。但存在2個(gè)主要問(wèn)題：① 高分辨率圖像的特征點(diǎn)成千上萬(wàn)，對(duì)數(shù)千個(gè)特征點(diǎn)進(jìn)行描述是一項(xiàng)艱巨的任務(wù)；② 特征點(diǎn)隨機(jī)分布的假設(shè)并不適用于具有重復(fù)結(jié)構(gòu)的圖像，如窗戶、農(nóng)田等。由于相似的外觀，比率測(cè)試拒絕了許多重復(fù)結(jié)構(gòu)的特征點(diǎn)。為解決該問(wèn)題現(xiàn)已提出了一些解決方案，但需要重復(fù)結(jié)構(gòu)共面或特征仿射不變等額外的假設(shè)和處理步驟[6-8]。RANSAC (RANdom SAmple Consensus)算法[9-11]可以緩解這些問(wèn)題,但RANSAC本身要求大多數(shù)誤匹配應(yīng)被預(yù)先排除,并且當(dāng)最近距離匹配集合中的誤匹配數(shù)量較多時(shí)會(huì)失效。

羅楠等[12]在研究具有重復(fù)結(jié)構(gòu)的圖像匹配方法時(shí)，針對(duì)基于局部特征的匹配方法容易出現(xiàn)誤匹配以及全局特征點(diǎn)主方向依然通過(guò)計(jì)算局部特征點(diǎn)相關(guān)信息得到等問(wèn)題，提出了一種基于成對(duì)特征點(diǎn)的匹配方法。該方法通過(guò)修正特征點(diǎn)的方向信息來(lái)提高匹配準(zhǔn)確率，啟示了本文特征點(diǎn)主方向的研究。劉威等[13]對(duì)ORB(Oriented FAST and Rotated BRIEF)特征采用K近鄰搜索策略來(lái)減少誤匹配，利用雙向匹配得到初匹配，對(duì)初匹配采用比率法，按照比率升序排列，選擇前若干個(gè)匹配對(duì)計(jì)算RANSAC的模型參數(shù)，再計(jì)算所有匹配對(duì)的誤差和內(nèi)點(diǎn)數(shù)量。該算法利用ORB特征提高計(jì)算效率的同時(shí)利用最近鄰和次近鄰的比值作為匹配對(duì)質(zhì)量好壞的判斷標(biāo)準(zhǔn)進(jìn)行篩選，對(duì)本文特征點(diǎn)匹配算法的研究提供了很大的參考。Shah等[14-15]選取部分特征點(diǎn)估計(jì)基本矩陣，利用對(duì)極約束計(jì)算每個(gè)特征點(diǎn)在目標(biāo)圖中的極線，利用二維圖像網(wǎng)格化劃分搜索區(qū)域以確定候選匹配，最后利用RANSAC去除誤匹配。該算法利用部分特征點(diǎn)計(jì)算基本矩陣的思想值得借鑒。

許多特征匹配方法首先使用全局比率測(cè)試，然后采用對(duì)極約束驗(yàn)證[16-19]，這樣會(huì)先發(fā)地拒絕許多重復(fù)結(jié)構(gòu)的特征。本文認(rèn)為，如果在比率測(cè)試之前使用對(duì)極約束，那么在重復(fù)結(jié)構(gòu)上可以保留較多真實(shí)的匹配。此外，Sampson距離用于基本矩陣的估計(jì)時(shí)更為簡(jiǎn)單，且對(duì)極約束模型的高階項(xiàng)相對(duì)一階項(xiàng)較小的時(shí)候近似效果會(huì)更好[1,20-21]。因此，本文提出了一種基于極線幾何的統(tǒng)計(jì)優(yōu)化特征匹配算法。正確匹配的特征點(diǎn)之間滿足對(duì)極約束，它同樣適用于具有重復(fù)結(jié)構(gòu)的圖像，而不需要任何假設(shè)或復(fù)雜的處理。由于基本矩陣的估計(jì)需要正確的特征匹配，首先,通過(guò)可靠地匹配2幅圖像的特征點(diǎn)子集，利用基于Sampson距離的RANSAC算法來(lái)估計(jì)2幅圖像之間的基本矩陣；然后，利用對(duì)極約束模型優(yōu)化正確匹配點(diǎn)的大致區(qū)域，從而避免由于重復(fù)結(jié)構(gòu)增加的誤匹配對(duì)，減小特征點(diǎn)搜索區(qū)域；最后，利用基于特征點(diǎn)主方向和尺度信息的統(tǒng)計(jì)優(yōu)化算法，得到最終匹配結(jié)果。

1 本文所提算法

本文算法首先通過(guò)可靠地匹配2幅圖像的尺度不變特征轉(zhuǎn)換(Scale Invariant Feature Transform,SIFT)特征子集，估計(jì)2幅圖像之間的基本矩陣并作為先驗(yàn)信息。然后對(duì)原圖中每一個(gè)特征點(diǎn)，利用對(duì)極約束優(yōu)化正確匹配點(diǎn)的大致區(qū)域，采用KD(K-Dimension)樹搜索出對(duì)應(yīng)匹配點(diǎn)，并利用雙向匹配反向驗(yàn)證得到初匹配。對(duì)于初匹配，再進(jìn)一步利用基于特征點(diǎn)尺度和主方向信息的統(tǒng)計(jì)優(yōu)化方法消除誤匹配，得到更精確的匹配結(jié)果。算法流程圖如圖1所示。

圖1 提出的算法流程圖Fig. 1 Flow chart of proposed algorithm

1.1 算法步驟及原理

步驟1基本矩陣的估計(jì)。首先，提取SIFT特征點(diǎn)，利用雙向FLANN匹配方法得到可靠匹配對(duì)；然后，利用基于Sampson距離的RANSAC算法估計(jì)基本矩陣F。

基于Sampson距離的RANSAC算法為：每次隨機(jī)不重復(fù)地選擇8組匹配對(duì)，利用歸一化8點(diǎn)算法[1]計(jì)算基本矩陣F，并分別計(jì)算所有的匹配對(duì)與對(duì)極約束模型之間的Sampson距離，如式(7)所示，若小于閾值，則加入內(nèi)點(diǎn)集合。經(jīng)過(guò)多次迭代，選擇內(nèi)點(diǎn)數(shù)量最多的集合為最終內(nèi)點(diǎn)集合，并利用該內(nèi)點(diǎn)集合結(jié)合RANSAC算法估計(jì)基本矩陣F。

基本矩陣F是一個(gè)3×3的矩陣，有8個(gè)自由度，每對(duì)匹配點(diǎn)只能得到一個(gè)方程，因此計(jì)算F至少需要8個(gè)匹配對(duì)。

構(gòu)造極線約束的代價(jià)函數(shù):

(1)

利用泰勒展開式作一階逼近：

(2)

(3)

JΔX=-CF(X)

(4)

f(ΔX)=ΔXTΔX-2λ(JΔX+CF(X))

(5)

求解可得

(6)

結(jié)合式(3)，可得Sampson距離為

(7)

(8)

圖2 極線搜索示意圖Fig.2 Schematic diagram of epipolar search

步驟4為了得到更為精確的匹配結(jié)果，本文利用基于特征點(diǎn)主方向和尺度信息的統(tǒng)計(jì)優(yōu)化方法進(jìn)一步消除誤匹配。對(duì)于步驟1～步驟3得到的初匹配結(jié)果，每次隨機(jī)選取一定比例的初匹配結(jié)果計(jì)算匹配主方向差和尺度比的標(biāo)準(zhǔn)差，若匹配主方向差的標(biāo)準(zhǔn)差大于某閾值，則去除其中的離群值對(duì)應(yīng)的匹配對(duì)；若匹配尺度比的標(biāo)準(zhǔn)差大于某閾值，則去除其中的離群值對(duì)應(yīng)的匹配對(duì)，不斷迭代，最終得到更加精確的匹配結(jié)果。

綜上，本文算法利用對(duì)極約束為每個(gè)特征點(diǎn)構(gòu)造了一個(gè)較小的待匹配特征點(diǎn)集合，并基于特征點(diǎn)主方向和尺度信息進(jìn)一步優(yōu)化匹配結(jié)果。而對(duì)于原圖某一特征點(diǎn)，傳統(tǒng)特征匹配方法中的待匹配特征點(diǎn)集合是目標(biāo)圖的所有特征點(diǎn)，此時(shí)當(dāng)在極線外存在與其結(jié)構(gòu)重復(fù)的特征點(diǎn)時(shí)，傳統(tǒng)方法可能會(huì)匹配錯(cuò)誤。因此本文算法可以減少搜索范圍和重復(fù)結(jié)構(gòu)的錯(cuò)誤拒絕，而且基于特征點(diǎn)主方向和尺度信息可以對(duì)初匹配結(jié)果進(jìn)一步優(yōu)化。

1.2 基于特征點(diǎn)主方向和尺度信息的統(tǒng)計(jì)優(yōu)化

假設(shè)提取的某SIFT特征點(diǎn)位置為(x,y)，尺度為σ，如圖3(a)所示，則該特征點(diǎn)所在的尺度圖像為

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

(9)

式中：*表示卷積；I(x,y)為圖像區(qū)域；G(x,y,σ)為高斯核函數(shù)，滿足:

(10)

使用有限差分計(jì)算以(x,y)為中心、3×1.5σ為半徑的鄰域內(nèi)每個(gè)像素L(x,y)對(duì)應(yīng)梯度的幅值和幅角，即

(11)

利用梯度直方圖統(tǒng)計(jì)該鄰域內(nèi)所有像素的梯度分布特性，其橫軸是梯度幅角(將0°～360°的范圍分為36個(gè)柱，每10°一個(gè)柱，共36個(gè)柱)，縱軸是梯度幅角對(duì)應(yīng)的梯度幅角個(gè)數(shù)，如圖3(b)所示。最后，通過(guò)對(duì)直方圖中主峰值和距離它最近的2個(gè)柱值進(jìn)行拋物線插值得到該特征點(diǎn)的主方向θ。

圖4為匹配主方向差的定義示意圖。圖4中：θL為原圖中的特征點(diǎn)fL(實(shí)線箭頭)的主方向；σL為原圖對(duì)應(yīng)尺度；θR為目標(biāo)圖中匹配特征點(diǎn)fR(虛線箭頭)的主方向；σR為目標(biāo)圖對(duì)應(yīng)尺度。即

θ1=θL

(12)

θ2=(θL+180°)%360°

(13)

定義1匹配主方向差為2個(gè)已匹配特征點(diǎn)的主方向之間的夾角α。若目標(biāo)圖中匹配特征點(diǎn)的主方向位于區(qū)域A，則α>0；若目標(biāo)圖中匹配特征點(diǎn)的主方向位于區(qū)域B，則α<0。如圖4所示，即

1) 0°≤θL<180°

(14)

2) 180°≤θL<360°

圖3 SIFT主方向的定義示意圖Fig.3 Schematic diagram of definition of SIFT main direction

圖4 匹配主方向差的定義示意圖Fig.4 Schematic diagram of definition of main direction difference

(15)

定義2匹配尺度比為原圖中的特征點(diǎn)的尺度與目標(biāo)圖中匹配特征點(diǎn)尺度的比值,即

(16)

由定義1可知，匹配主方向差的范圍為-180°～180°。本文采用TUM數(shù)據(jù)集[22]的freiburg3_long_office_household中的視頻序列圖片，通過(guò)大量實(shí)驗(yàn)分析匹配主方向差和尺度比在已匹配特征點(diǎn)對(duì)上的分布情況。

分別將目標(biāo)圖逆時(shí)針旋轉(zhuǎn)90°和縮放0.5倍后與原圖匹配，對(duì)匹配點(diǎn)對(duì)的尺度比和主方向差進(jìn)行測(cè)試，如圖5所示，其中紅色為無(wú)旋轉(zhuǎn)和縮放變換，藍(lán)色為旋轉(zhuǎn)變換，綠色為縮放變換。

分別將數(shù)據(jù)集中第0幀與第0,1,…,99幀用BF、FLANN、ROBUST算法進(jìn)行匹配，統(tǒng)計(jì)匹配主方向差和尺度比的標(biāo)準(zhǔn)差的分布，如圖6和圖7所示。

圖5 匹配點(diǎn)對(duì)的尺度比和主方向差的分布Fig.5 Distribution of scale ratio and main direction difference of matching features

圖6 匹配主方向差的標(biāo)準(zhǔn)差的分布Fig.6 Distribution of standard deviation of main direction difference of matching

圖7 匹配尺度比的標(biāo)準(zhǔn)差的分布Fig.7 Distribution of standard deviation of scale ratio of matching

由圖5可知，匹配主方向差和尺度比的分布較為集中，但同時(shí)也存在少量的孤立點(diǎn)和離群值，這是因?yàn)榇嬖谡`匹配。

由于BF匹配結(jié)果中存在大量誤匹配，即BF匹配主方向差和匹配尺度比中存在大量離群值； FLANN和ROBUST匹配結(jié)果中誤匹配較少，其中的離群值相對(duì)較少。結(jié)合圖6和圖7可知，正確匹配對(duì)的匹配主方向差和尺度比的標(biāo)準(zhǔn)差較小，分布較為集中，因此可以利用匹配主方向差和匹配尺度比的標(biāo)準(zhǔn)差判斷初匹配結(jié)果是否正確。即，每次從初匹配結(jié)果中隨機(jī)選取部分匹配結(jié)果，計(jì)算其匹配主方向差和尺度比的標(biāo)準(zhǔn)差，若匹配主方向差的標(biāo)準(zhǔn)差大于某閾值，可以去除其中的離群值對(duì)應(yīng)的匹配以消除誤匹配；若匹配尺度比的標(biāo)準(zhǔn)差大于某閾值，可以去除其中的離群值對(duì)應(yīng)的匹配以消除誤匹配。

2 實(shí)驗(yàn)和結(jié)果

本實(shí)驗(yàn)采用Ubuntu 14.04平臺(tái)，基于OpenCV搭建Cmake工程。實(shí)驗(yàn)選取TUM[22]和DTU[23]數(shù)據(jù)集，如表1所示。實(shí)驗(yàn)閾值設(shè)置如表2所示。實(shí)驗(yàn)原圖和目標(biāo)圖如圖8所示，分別包含模糊、視角變化、光照變化和低紋理等噪聲。

每組實(shí)驗(yàn)的實(shí)驗(yàn)環(huán)境分為3部分：原圖像分別與目標(biāo)圖像(場(chǎng)景1)、目標(biāo)圖像順時(shí)針旋轉(zhuǎn)90°(場(chǎng)景2)、目標(biāo)圖像縮放0.5倍(場(chǎng)景3)進(jìn)行匹配測(cè)試，實(shí)驗(yàn)結(jié)果如表3所示。

表1 數(shù)據(jù)集簡(jiǎn)介Table 1 Introduction of data sets

表2 實(shí)驗(yàn)閾值設(shè)置Table 2 Experimental threshold setting

圖8 實(shí)驗(yàn)圖像Fig. 8 Images for experiment

結(jié)合表3，從圖9可以看出對(duì)于重復(fù)結(jié)構(gòu)下的匹配，本文算法匹配數(shù)量更多。圖10和圖11的匹配結(jié)果表明本文方法對(duì)圖像的旋轉(zhuǎn)和縮放變換具有良好的魯棒性。由表3中各種實(shí)驗(yàn)環(huán)境下的算法比較可知，本文算法的匹配數(shù)量約是FLANN和ROBUST算法的1.2倍，匹配準(zhǔn)確率平均提高了1%左右；實(shí)驗(yàn)5的結(jié)果也表明對(duì)于具有重復(fù)結(jié)構(gòu)的圖像間的匹配，本文算法的匹配數(shù)量和準(zhǔn)確率都有很大的提升。

圖9 實(shí)驗(yàn)5重復(fù)結(jié)構(gòu)下的匹配結(jié)果Fig.9 Experiment 5 matching result in repetitive structure

表3 本文算法與FLANN和ROBUST匹配算法的性能比較Table 3 Comparison of performance of proposed algorithm, FLANN and ROBUST matching algorithms

圖10 實(shí)驗(yàn)2匹配結(jié)果Fig.10 Mathing results of Experiment 2

圖11 實(shí)驗(yàn)4匹配結(jié)果Fig.11 Matching results of Experiment 4

3 結(jié) 論

1) 本文算法對(duì)圖像的旋轉(zhuǎn)和縮放變換具有良好的魯棒性，匹配數(shù)量達(dá)到了FLANN和ROBUST算法的1.2倍左右，匹配準(zhǔn)確率平均提高了1%左右，并且也能較好地處理具有重復(fù)結(jié)構(gòu)的圖像間的匹配。

2) 本文算法的時(shí)間復(fù)雜度為O(kn2)，計(jì)算量相對(duì)較大，如何提高本文算法的運(yùn)行效率和處理嚴(yán)重重復(fù)結(jié)構(gòu)的能力將是接下來(lái)的研究目標(biāo)。

參 考 文 獻(xiàn)

[1] HARTLEY R, ZISSERMAN A. Multiple view geometry in computer vision[M]. Cambridge: Cambridge University Press, 2003: 191-215.

[2] MUR-ARTAL R, MONTIEL J M M, TARDOS J D. ORB-SLAM: A versatile and accurate monocular SLAM system[J]. IEEE Transactions on Robotics, 2015, 31(5): 1147-1163.

[3] ARYA S, MOUNT D M. Approximate nearest neighbor queries in fixed dimensions[C]∥SODA’93: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1993: 271-280.

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

[5] MUJA M, LOWE D G. Fast approximate nearest neighbors with automatic algorithm configuration[J]. International Conference on Computer Vision Theory and Applications (VISAPP), 2009, 2(1): 331-340.

[6] KUSHNIR M, SHIMSHONI I. Epipolar geometry estimation for urban scenes with repetitive structures[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(12): 2381-2395.

[7] ZHANG W, KOSECKA J. Generalized RANSAC framework for relaxed correspondence problems[C]∥Third International Symposium on 3D Data Processing, Visualization, and Transmission. Piscataway, NJ: IEEE Press, 2006: 854-860.

[8] SUR F, NOURY N, BERGER M O. Image point correspondences and repeated patterns[J]. Computer Vision & Pattern Recognition, 2011, 8(2): 216-243.

[9] FISCHLER M A, BOLLES R C. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

[10] CHIN T J, YU J, SUTER D. Accelerated hypothesis generation for multi-structure data via preference analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(4): 625-638.

[11] 王云麗, 張?chǎng)? 高超, 等. 航拍視頻拼圖中基于特征匹配的全局運(yùn)動(dòng)估計(jì)方法[J]. 航空學(xué)報(bào), 2008, 29(5): 1218-1225.

WANG Y L, ZHANG X, GAO C, et al. The global motion estimation method based on feature matching in video[J]. Acta Aeronautica et Astronautica Sinica, 2008, 29(5): 1218-1225 (in Chinese).

[12] 羅楠, 孫權(quán)森, 陳強(qiáng), 等. 針對(duì)重復(fù)模式圖像的成對(duì)特征點(diǎn)匹配[J]. 中國(guó)圖象圖形學(xué)報(bào), 2015, 20(1): 113-124.

LUO N, SUN Q S, CHEN Q, et al. Pair-wise feature points based matching algorithm for repetitive patterns images[J]. Journal of Image and Graphics, 2015, 20(1): 113-124 (in Chinese).

[13] 劉威, 趙文杰, 李德軍, 等. 一種基于ORB檢測(cè)的特征點(diǎn)匹配算法[J]. 激光與紅外, 2015, 45(11): 1380-1384.

LIU W, ZHAO W J, LI D J, et al. Feature points matching algorithm based on ORB detection[J]. Laser and Infrared, 2015, 45(11): 1380-1384 (in Chinese).

[14] SHAH R, SRIVASTAVA V, NARAYANAN P J. Geometry-aware feature matching for structure from motion applications[C]∥2015 IEEE Winter Conference on Applications of Computer Vision (WACV). Piscataway, NJ: IEEE Press, 2015: 278-285.

[15] SHAH R, DESHPANDE A, NARAYANAN P J. Multistage SFM: Revisiting incremental structure from motion[C]∥2014 2nd International Conference on 3D Vision (3DV). Piscataway, NJ: IEEE Press, 2014: 417-424.

[16] ZHANG Z, DERICHE R, FAUGERAS O, et al. A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry[J]. Artificial Intelligence, 1995, 78(1-2): 87-119.

[17] 陳潔, 高志強(qiáng), 密保秀, 等. 引入極線約束的SURF特征匹配算法[J]. 中國(guó)圖象圖形學(xué)報(bào), 2016, 21(8): 1048-1056.

CHEN J, GAO Z Q, MI B X, et al. SURF feature matching based on epipolar constraint[J]. Journal of Image and Graphics, 2016, 21(8): 1048-1056 (in Chinese).

[18] 李立春, 張小虎, 傅丹, 等. 基于極線局部校正的特征匹配方法[J]. 光學(xué)技術(shù), 2008, 34(2): 285-288.

LI L C, ZH X H, FU D, et al. Feature matching algorithm based on rectification of epipolar-line region[J]. Optical Technique, 2008, 34(2): 285-288 (in Chinese).

[19] 張培耘, 華希俊, 夏樂(lè)春, 等. 基于 RANSAC 算法的極線約束立體視覺(jué)匹配方法研究[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2013(11): 20-22.

ZHANG P G, HUA X J, XIA L C, et al. Stereo matching with epipolar line constraints based on RANSAC algorithm[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2013(11): 20-22 (in Chinese).

[20] 單欣, 王耀明, 董建萍. 基于RANSAC算法的基本矩陣估計(jì)的匹配方法[J]. 上海電機(jī)學(xué)院學(xué)報(bào), 2006, 9(4): 66-69.

SHAN X, WANG Y M, DONG J P. The matching method based on RANSAC algorithm for estimation of the fundamental matrix[J]. Journal of Shanghai Dianji University, 2006, 9(4): 66-69 (in Chinese).

[21] 田謹(jǐn)思, 蘇劍波. 基于Sampson誤差計(jì)算單應(yīng)的立體匹配[J]. 計(jì)算機(jī)工程與應(yīng)用, 2005, 41(3): 7-9.

TIAN J S, SU J P. Stereo matching with epipolar line constraints based on RANSAC algorithm[J]. Computer Engineering and Applications, 2005, 41(3): 7-9 (in Chinese).

[22] STURM J, ENGELHARD N, ENDRES F, et al. A benchmark for the evaluation of RGB-D SLAM systems[C]∥2012 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Piscataway, NJ: IEEE Press, 2012: 573-580.

[23] AANAES H, DAHL A L, PEDERSEN K S. Interesting interest points[J]. International Journal of Computer Vision, 2012, 97(1): 18-35.