相恒永 周莉 巴曉輝，3? 陳杰

(1.中國科學(xué)院微電子研究所，北京100029;2.中國科學(xué)院大學(xué)電子電氣與通信工程學(xué)院，北京100049;3.中國科學(xué)院大學(xué)微電子學(xué)院，北京100049)

基于局部特征的圖像匹配是計(jì)算機(jī)視覺的基礎(chǔ)工作之一，被廣泛應(yīng)用于全景拼接、三維重建、視覺導(dǎo)航等熱門領(lǐng)域。該工作的主要思路是:從輸入圖像中提取關(guān)鍵點(diǎn)并計(jì)算描述子，然后通過描述子的相似性進(jìn)行匹配，從而得到輸入圖像中不同局部特征點(diǎn)之間的對應(yīng)關(guān)系。而在很多情況下，僅僅依靠特征進(jìn)行的圖像匹配結(jié)果不會很理想，這是因?yàn)槭止ぴO(shè)計(jì)的特征的可區(qū)分性與可重復(fù)性很難在所有的場景中都起作用。因此，如何從已經(jīng)得到的匹配集合中濾除錯誤匹配成為了一個(gè)值得研究的問題。

比較經(jīng)典的方法是RANSAC(隨機(jī)抽樣一致性)算法［1］，該方法使用隨機(jī)抽樣一致性方法建立特征匹配約束的空間幾何模型，并借助建立的模型過濾錯誤匹配。但由于二維平面點(diǎn)空間約束的不完備性，很多時(shí)候這種方法的效果并不是很好。因此，近年來的很多工作均聚焦于利用特征匹配之間的局部約束過濾錯誤匹配的方法。在2017年的CVPR(IEEE國際計(jì)算機(jī)視覺與模式識別會議)上，Bian等［2］提出了一種叫做GMS(基于網(wǎng)格的運(yùn)動統(tǒng)計(jì))的算法，它利用基于網(wǎng)格的運(yùn)動統(tǒng)計(jì)建立局部約束關(guān)系模型過濾錯誤匹配。該算法在速度與效果上都表現(xiàn)得很好。但是由于其使用了固定尺度、固定位置的網(wǎng)格，因此在尺度變換較大或者旋轉(zhuǎn)角度過大的場景中的匹配效果不佳。Ma等［3-5］提出了一種LPM(局部保持匹配)方法，這種方法通過保持局部結(jié)構(gòu)信息可以得到很好的匹配效果，不過其對于原始的輸入匹配集合質(zhì)量有較高要求，一般需要原始匹配集合中正確匹配的占比大于50%。因此文獻(xiàn) ［3-5］采用經(jīng)過預(yù)處理的SIFT(尺度不變特征變換)［6］特征匹配結(jié)果作為算法輸入。STFT特征具有較高的魯棒性，但是比較耗時(shí)，這使得算法很難應(yīng)用于實(shí)時(shí)任務(wù)。

由于目前特征匹配工作在視覺導(dǎo)航、實(shí)時(shí)三維重建等領(lǐng)域應(yīng)用較多，因此保證特征匹配的實(shí)時(shí)性非常重要。而上述方法中真正可以實(shí)時(shí)應(yīng)用的GMS算法在面對尺度變換較大或者旋轉(zhuǎn)角度較大的場景時(shí)表現(xiàn)不佳。為了得到一種實(shí)時(shí)的、魯棒的、實(shí)用的特征匹配篩選算法，文中深入分析了運(yùn)動統(tǒng)計(jì)方法的數(shù)學(xué)原理，提出了一種新的基于運(yùn)動統(tǒng)計(jì)的特征匹配篩選算法，下文中稱這種算法為DWMS(動態(tài)窗口運(yùn)動統(tǒng)計(jì))算法。DWMS算法使用可以動態(tài)調(diào)整尺度與位置的窗口代替網(wǎng)格進(jìn)行運(yùn)動統(tǒng)計(jì)，同時(shí)考慮到動態(tài)窗口的建立時(shí)間較長，故采用快速近似最近鄰［7］算法加速窗口的建立過程。

1 匹配的局部約束與GMS算法

對兩幅圖像完成特征匹配后，如何從匹配集合中過濾出錯誤的匹配是本文研究的重點(diǎn)。本節(jié)主要是描述匹配的局部約束關(guān)系原理，并給出相應(yīng)的數(shù)學(xué)分析，最后介紹基于網(wǎng)格的運(yùn)動統(tǒng)計(jì)方法的原理與局限性。

1.1 特征匹配的局部約束原理

通常用作局部特征匹配的兩張圖片，是由攝像機(jī)從不同的角度對同一實(shí)物場景拍攝的。一個(gè)正確匹配的兩個(gè)端點(diǎn)是由真實(shí)世界中同一三維點(diǎn)在兩個(gè)相機(jī)成像平面上投影形成的。如果將點(diǎn)拓展成塊，真實(shí)世界中的一個(gè)立方體塊在分別投影到兩個(gè)成像平面上后就是對應(yīng)的兩個(gè)平面區(qū)域，此時(shí)在這兩個(gè)平面區(qū)域中檢測到的特征點(diǎn)應(yīng)該是相互匹配的，這是一種天然的約束。

如圖1所示，假設(shè)其中的一個(gè)匹配xi(鼻子處)是正確的，則在其鄰域 (周圍黃色圓圈區(qū)域)中還會存在一些其他的匹配對與其指向一致，文中稱這些匹配對是匹配xi在其鄰域中的支持匹配。相反，如果一個(gè)匹配xj(嘴巴處)是錯誤的，則在這個(gè)匹配的鄰域 (周圍紅色圓圈區(qū)域)中將很難再找到其他的匹配?；谶@一事實(shí)，在得到初始的匹配集合后，可以通過這種鄰域的約束關(guān)系完成匹配集合的篩選工作。

1.2 對特征匹配局部約束的數(shù)學(xué)分析

假設(shè)在兩幅不同的圖像I1、I2中存在相同的場景，從這兩幅圖像中分別提取出N個(gè)特征點(diǎn)，最近鄰匹配后得到如下匹配集合:

圖1 正確匹配與錯誤匹配的鄰域約束對比Fig.1 Comparison of correct matching and mismatched neighborhood constraints

從中選定一個(gè)匹配xi，假設(shè)這個(gè)匹配的兩端點(diǎn)在I1、I2上的鄰域分別為a、b。已知在鄰域a、b中分別提取出了n、n′個(gè)特征點(diǎn)。如果匹配xi是錯誤的，則鄰域a中的其他n-1個(gè)特征會無規(guī)律地匹配到圖像I2的N個(gè)特征點(diǎn)上，假設(shè)此時(shí)其落在鄰域b上的概率為Pf;反之，如果匹配xi是正確的，則假設(shè)其落在鄰域b上的概率為Pt。令Si表示鄰域a、b中的匹配數(shù)量，也就是匹配xi的支持匹配的數(shù)量。由文獻(xiàn)［2］可知在一定假設(shè)下Si服從如下二項(xiàng)分布:

圖2中畫出了更加直觀的分布形式。

圖2 正確、錯誤匹配的鄰域得分分布情況Fig.2 Positive and false matching neighborhood score distribution

如果匹配xi是錯誤的，則Si的均值mf與標(biāo)準(zhǔn)差sf為

可以使用下式表示上述正確、錯誤兩類分布的類間距:

基于運(yùn)動統(tǒng)計(jì)方法的目標(biāo)就是在保證計(jì)算量的前提下設(shè)計(jì)出使D足夠大的算法，并據(jù)此完成匹配的篩選。

1.3 基于網(wǎng)格的運(yùn)動統(tǒng)計(jì)方法

前文介紹了匹配的局部約束關(guān)系，而運(yùn)動統(tǒng)計(jì)是描述這種局部約束關(guān)系的方法，基于網(wǎng)格的運(yùn)動統(tǒng)計(jì)算法GMS在2017年被提出，該算法通過將圖像劃分為網(wǎng)格來進(jìn)行運(yùn)動統(tǒng)計(jì)。值得一提的是，在GMS算法中并不是僅僅只評估兩個(gè)對應(yīng)網(wǎng)格的運(yùn)動統(tǒng)計(jì)。如圖3所示，在GMS算法中，首先使用一定數(shù)量的網(wǎng)格對圖像進(jìn)行劃分。當(dāng)待驗(yàn)證匹配的兩端分別落在網(wǎng)格i5與j5中時(shí)，統(tǒng)計(jì)網(wǎng)格i5與j5中的匹配的數(shù)量，當(dāng)其高于一定閾值時(shí)，會繼續(xù)對i5與j5周圍的8對網(wǎng)格進(jìn)行運(yùn)動統(tǒng)計(jì)，只有在周圍8個(gè)網(wǎng)格對 (i1到j(luò)1，i2到j(luò)2，…，i9到j(luò)9)的運(yùn)動統(tǒng)計(jì)加起來大于一定閾值時(shí)才會認(rèn)為該匹配有效。

圖3 基于網(wǎng)格的運(yùn)動統(tǒng)計(jì)示意圖［2］Fig.3 Diagram of motion statistics based on grid

上述實(shí)現(xiàn)思路帶來了兩個(gè)問題。首先，GMS算法固定網(wǎng)格劃分的尺寸，這使得算法不具備尺度不變性。雖然文獻(xiàn) ［2］中提到GMS算法可以通過對圖像做尺度縮放來解決這個(gè)問題，但是由于事先并不知道第2幅圖像相對于第1幅圖像的尺度變換比例，因此需要在很多尺度空間上分別進(jìn)行GMS算法，然后選取其中結(jié)果最好的。比如在GMS的多尺度版本實(shí)現(xiàn)中一共在5個(gè)尺度空間上進(jìn)行了GMS操作，它們的縮放尺度分別為1、、2。在上述5個(gè)尺度空間上分別執(zhí)行GMS算法，然后比較結(jié)果，從而選取最好的一個(gè)作為輸出。這種做法的缺點(diǎn)一是不能精確定位最佳尺度，使得算法結(jié)果很難達(dá)到最佳，二是不同尺度空間上的重復(fù)操作會降低 GMS算法的時(shí)效性。其次，GMS算法同樣不具備旋轉(zhuǎn)不變性，很顯然，GMS算法基于九宮格的運(yùn)動統(tǒng)計(jì)假設(shè)了兩幅圖像中匹配所處的中心網(wǎng)格周圍的8個(gè)網(wǎng)格一一對應(yīng)，而當(dāng)上述兩幅圖像相對旋轉(zhuǎn)一定角度時(shí)，該一一對應(yīng)關(guān)系便不再適配。雖然類似尺度變換場景，GMS算法中提供了一個(gè)較簡單的解決方案，即對第2幅圖像上九宮格外圍的8個(gè)網(wǎng)格做依次旋轉(zhuǎn)然后分別進(jìn)行GMS操作，最后選取其中效果最好的那個(gè)。但是這種做法也帶來了同樣的問題:①由于不能精確定位旋轉(zhuǎn)角度，如果待處理兩幅圖像之間的旋轉(zhuǎn)不剛好是45°的倍數(shù)時(shí)，最后的結(jié)果都會受到影響;②在不同旋轉(zhuǎn)角度上的重復(fù)操作會降低GMS算法的時(shí)效性。

綜上，GMS算法基于網(wǎng)格的運(yùn)動統(tǒng)計(jì)方式足夠新奇，但是帶來的兩個(gè)問題同樣需要解決。

2 DWMS算法

前文詳細(xì)分析了特征匹配的局部約束原理，并介紹了GMS算法的原理與不足，接下來介紹基于動態(tài)窗口的運(yùn)動統(tǒng)計(jì)方法DWMS算法與其實(shí)現(xiàn)細(xì)節(jié)。

2.1 基于動態(tài)窗口的運(yùn)動統(tǒng)計(jì)

前文關(guān)于局部約束的數(shù)學(xué)分析是在匹配的鄰域上進(jìn)行的，在GMS算法中使用固定尺寸與位置的網(wǎng)格來確定鄰域，這使得其不具備尺度不變性與旋轉(zhuǎn)不變性。在DWMS算法中使用動態(tài)窗口為匹配確定鄰域范圍，這個(gè)動態(tài)窗口以該匹配為中心，分別為該匹配的兩個(gè)端點(diǎn)確定鄰域范圍。確定鄰域范圍后，便可以通過運(yùn)動統(tǒng)計(jì)算法完成對正確匹配與錯誤匹配的劃分。

首先，選定一個(gè)匹配xi，確定其在I1與I2上的鄰域a、b，鄰域a、b中均存在n個(gè)特征點(diǎn)。文中算法定義該匹配在鄰域上的運(yùn)動統(tǒng)計(jì)得分為

式中，xab為鄰域a、b上特征匹配的數(shù)量，也就是匹配xi的支持匹配數(shù)量。參考圖2中的概率分布，即運(yùn)動統(tǒng)計(jì)得分越高的匹配是正確匹配的概率也越高，文中設(shè)置

作為閾值區(qū)分出錯誤匹配，如式 (4)中表示的一樣，mf、sf分別為錯誤匹配的支持匹配數(shù)量均值和標(biāo)準(zhǔn)差，α為對sf的一個(gè)調(diào)和參數(shù)，它的作用是確保更多錯誤的匹配可以被找到。

最后，本文方法使用如下公式判別匹配xi是正確匹配還是錯誤匹配:

式中，T為DWMS算法最終保留的匹配集合，F(xiàn)為被DWMS算法濾除的匹配集合。

2.2 動態(tài)窗口的獲取

本文方法基于動態(tài)窗口確定匹配的鄰域范圍，在確定超參數(shù)n后，如何建立動態(tài)窗口是一個(gè)關(guān)鍵的問題。

使用傳統(tǒng)暴力最近鄰的方式獲取DWMS所需的動態(tài)窗口復(fù)雜度較高，會使算法喪失實(shí)時(shí)性。本文考慮到此處所需的動態(tài)窗口無需是嚴(yán)格的最近鄰窗口，因此DWMS算法采用快速近似最近鄰算法加速動態(tài)窗口的獲取。

快速近似最近鄰算法有很多，此處選用的是kd 樹 (k-dimension tree［8］)算法。該算法比較簡單，并且在低維空間中表現(xiàn)優(yōu)異，比較適合此處的應(yīng)用場景。該算法的主要思路是根據(jù)給定的相似性度量方式在搜索空間中建立一棵二叉樹，通過這棵樹對搜索空間進(jìn)行層層劃分，樹的每個(gè)節(jié)點(diǎn)都代表整個(gè)搜索空間的一個(gè)子集，其中根節(jié)點(diǎn)代表整個(gè)搜索空間，子節(jié)點(diǎn)將父親節(jié)點(diǎn)代表的搜索空間劃分成兩個(gè)大小相同的不相交子集，并存儲自身每個(gè)維度的邊界值。

圖4所示的是k-d樹在二維空間中的經(jīng)典劃分方式，它使用一個(gè)正方形平面代表整個(gè)搜索空間，搜索空間中每個(gè)點(diǎn)用兩維坐標(biāo) (X，Y)表示，依次通過點(diǎn)的數(shù)量分布對空間進(jìn)行二等分，在劃分完畢后其對應(yīng)的k-d樹的樹狀結(jié)構(gòu)如圖5所示。此處需要指出的是，對于一個(gè)大小是N的集合，使用暴力搜索的平均時(shí)間復(fù)雜度是O(N)，而使用k-d樹結(jié)構(gòu)的索引結(jié)構(gòu)進(jìn)行索引的平均時(shí)間復(fù)雜度僅為O(lbN)。

圖4 二維搜索空間劃分Fig.4 2D search space partition

圖5 k-d樹結(jié)構(gòu)Fig.5 k-d tree structure

在本文算法中，一張圖像代表一個(gè)二維平面，每個(gè)特征點(diǎn)在圖像上都有一個(gè)二維坐標(biāo)代表其在圖像中的位置。DWMS算法會據(jù)此建立k-d樹索引，對一個(gè)匹配xi建立動態(tài)窗口的過程其實(shí)就是利用k-d樹算法獲得當(dāng)前匹配的n近鄰窗口的過程。

2.3 超參數(shù)n大小的確定與分析

DWMS算法中使用動態(tài)窗口為匹配確定鄰域范圍，動態(tài)窗口以該匹配為中心，尋找距離該匹配最近的其他匹配構(gòu)成鄰域。此時(shí)窗口內(nèi)的匹配數(shù)量即該匹配鄰域中的匹配數(shù)量n，由1.2節(jié)的推導(dǎo)可知類間距D服從如下規(guī)律:

即鄰域中匹配數(shù)量越多，錯誤類與正確類的統(tǒng)計(jì)差異越明顯。但是，上述推導(dǎo)的一個(gè)前提是鄰域a、b是局部的，這意味著如果鄰域范圍很大，局部約束的概念便不再適用。并且隨著鄰域中匹配數(shù)量的增大，基于k-d樹的最近鄰算法復(fù)雜度增長較快。因此鄰域大小的確定是一個(gè)需要仔細(xì)考慮的問題。下文會結(jié)合實(shí)驗(yàn)對n的取值進(jìn)行詳細(xì)說明。

2.4 DWMS算法的實(shí)現(xiàn)

經(jīng)典的手工設(shè)計(jì)的局部特征算法有 SIFT、SURF(加速魯棒特征)算法［9］、KAZE 算法［10］等，近期基于深度學(xué)習(xí)的局部特征算法有LIFT(學(xué)習(xí)不變特征變換)算法［11］、Superpoint算法［12］等，都可以作為本文算法的前置算法。最終考慮到本文任務(wù)對實(shí)時(shí)性和魯棒性的較高要求，經(jīng)過大量實(shí)驗(yàn)驗(yàn)證，最終DWMS算法選用更加快速、簡單的 ORB(Oriented FAST and Rotated BRIEF)［13］特征。同時(shí)算法實(shí)現(xiàn)時(shí)有3個(gè)環(huán)節(jié)需要特別標(biāo)注:①使用Flann(快速近似最近鄰搜索庫)［14］實(shí)現(xiàn)初始匹配的快速構(gòu)建;②采用k-d樹的索引結(jié)構(gòu)加速動態(tài)窗口的建立;③經(jīng)過實(shí)驗(yàn)，為了保證鄰域a、b可以具備更好的兼容性，本文算法設(shè)置鄰域b中的特征數(shù)量是鄰域a中的1.2倍。

DWMS算法詳細(xì)步驟如下。

輸入:一對圖像 I1、I2，匹配集合 C={xi;

輸出:正確匹配集合 T={ti′}，其中 ti′為第i′個(gè)正確的匹配，nt為正確匹配的數(shù)量;

(1)基于兩張圖像中的特征點(diǎn)集合構(gòu)建兩個(gè)快速最近鄰索引結(jié)構(gòu);

(2)對匹配集合C中的每個(gè)匹配構(gòu)建n近鄰鄰域;

(3)在每個(gè)匹配的鄰域范圍內(nèi)，計(jì)算其運(yùn)動統(tǒng)計(jì)得分Si與判斷閾值;

(4)根據(jù)式 (8)判斷匹配的合理性，將合理匹配 ti′加入 T;

(5) 輸出結(jié)果 T={ti′}。

3 實(shí)驗(yàn)

實(shí)驗(yàn)部分主要分為6個(gè)部分進(jìn)行介紹，首先是進(jìn)行算法衡量指標(biāo)的介紹，接下來介紹本文實(shí)驗(yàn)涉及到的4個(gè)數(shù)據(jù)集，最后從幾個(gè)方面來具體測試DWMS算法的綜合性能。一是考察超參數(shù)n的不同取值對算法效果的影響;二是進(jìn)行DWMS與GMS算法、DWMS與RANSAC算法的對比實(shí)驗(yàn);三是對上述各種算法的耗時(shí)進(jìn)行對比。下文實(shí)驗(yàn)的運(yùn)行環(huán)境是ubuntu16.04系統(tǒng)，處理器型號為Intel Core i5-4200U，4 GB內(nèi)存，開發(fā)語言為 C+ +，OpenCV版本為4.0.0。

3.1 衡量指標(biāo)介紹

通常以正確匹配為正類、錯誤匹配為負(fù)類，正確匹配的篩選就變成了一個(gè)二分類問題。對于二分類問題常用的評價(jià)指標(biāo)是精確率與召回率［15］。依據(jù)分類器在測試集上預(yù)測的結(jié)果，會出現(xiàn)如下4類情況:①將正確匹配預(yù)測為正類，將此類個(gè)數(shù)記為TP;②將正確匹配預(yù)測為負(fù)類，將此類個(gè)數(shù)記為FN;③將錯誤匹配預(yù)測為正類，將此類個(gè)數(shù)記為FP;④將錯誤匹配預(yù)測為負(fù)類，將此類個(gè)數(shù)記為TN?？梢酝ㄟ^如下公式計(jì)算出匹配結(jié)果的精確率P與召回率R:

下文中較多使用精確率與召回率的調(diào)和均值F1來綜合評價(jià)匹配的性能。

3.2 實(shí)驗(yàn)數(shù)據(jù)集介紹

實(shí)驗(yàn)中一共涉及了4個(gè)數(shù)據(jù)集。第1個(gè)數(shù)據(jù)集是專門用于特征匹配的VGG數(shù)據(jù)集［16-17］，全名為Affine Covariant Regions Datasets，這個(gè)數(shù)據(jù)集提供了8組圖像序列共40張圖片，這些序列分別代表了圖像模糊、尺度縮放、旋轉(zhuǎn)變換、視角變換和光照變換等場景。每個(gè)圖像序列包含6張圖片與圖片對之間對應(yīng)的單應(yīng)矩陣信息。第2個(gè)數(shù)據(jù)集是被廣泛用于視覺同時(shí)定位與建圖的TUM［18］數(shù)據(jù)集，全名為RGB-D SLAM Dataset and Benchmark，這個(gè)數(shù)據(jù)集一共3141張圖片，提供了彩色圖片和與之對應(yīng)的深度圖，同時(shí)提供了攝像機(jī)的運(yùn)動軌跡真值信息。整個(gè)數(shù)據(jù)集提供了各種條件下的測試場景。第3個(gè)數(shù)據(jù)集是三維重建數(shù)據(jù)集 Strecha［19］，全名為Dense Multi-view Stereo Dataset，這個(gè)數(shù)據(jù)集一共500張圖片，提供了每張圖片的位姿和場景的3D模型，整個(gè)數(shù)據(jù)集紋理比較豐富。最后一個(gè)數(shù)據(jù)集是Cabinet［18］，這個(gè)數(shù)據(jù)集與TUM數(shù)據(jù)集一樣，由慕尼黑工業(yè)大學(xué)提供，一共578張圖片，提供了彩色圖片和與之對應(yīng)的深度圖，同時(shí)提供了攝像機(jī)的運(yùn)動軌跡真值信息。整個(gè)數(shù)據(jù)集記錄了強(qiáng)光照條件下的低紋理環(huán)境。

3.3 超參數(shù)n的分析實(shí)驗(yàn)

由前文的分析可知，本文方法通過超參數(shù)n確定匹配的鄰域范圍，而鄰域范圍的大小對基于局部約束的匹配篩選方法具有較大影響。為了確保最終匹配的性能與效率，本文設(shè)計(jì)如下實(shí)驗(yàn)。在3.2節(jié)提到的4種數(shù)據(jù)集上，當(dāng)每對圖像一共具有500、1000、2000個(gè)特征匹配的情況下，分別繪制出由DWMS算法得到的精確率與召回率的調(diào)和均值F1和每對圖像進(jìn)行匹配的平均耗時(shí)與超參數(shù)n的對應(yīng)關(guān)系曲線圖，如圖6所示。由圖6可以發(fā)現(xiàn)，超參數(shù)n的取值在1到5之間時(shí)，DWMS算法得到的F1值會有一個(gè)迅速的提升，之后便會逐漸趨于穩(wěn)定，n繼續(xù)增大對性能提升不再明顯。而隨著n的增大，DWMS算法的耗時(shí)也會近似呈線性趨勢上升，故n的取值不宜過大。因此綜合考慮算法表現(xiàn)與時(shí)間成本，通過如下公式設(shè)置超參數(shù)n的大小效果較好:

n的取值被控制在5到10之間，此時(shí)DWMS算法性能已經(jīng)達(dá)到較高水準(zhǔn)，同時(shí)基本可以保證算法耗時(shí)在幾十毫秒左右，可以實(shí)時(shí)應(yīng)用。此處需要說明的一點(diǎn)是，由于本文主要提出的是一種可以實(shí)時(shí)應(yīng)用的特征匹配篩選算法，所以圖像提取的特征點(diǎn)總數(shù)不宜過多，因此實(shí)驗(yàn)假設(shè)的2000已經(jīng)是一幅圖像提取特征點(diǎn)的最大數(shù)量，超過2000時(shí)僅僅特征點(diǎn)的提取與匹配工作便很難實(shí)時(shí)進(jìn)行。

圖6 n對匹配的影響Fig.6 Effect of n on matching

3.4 DWMS與GMS算法的對比實(shí)驗(yàn)

由于本文算法與GMS算法都是對局部約束進(jìn)行運(yùn)動統(tǒng)計(jì)的方法，所以本文針對這兩種算法進(jìn)行一次詳細(xì)的對比。首先分別在4種數(shù)據(jù)集上針對旋轉(zhuǎn)角度與尺度變化進(jìn)行實(shí)驗(yàn)，然后在其他更豐富的場景下進(jìn)行實(shí)驗(yàn)，并依此對兩種算法進(jìn)行全方位的對比。

3.4.1 DWMS與GMS算法的旋轉(zhuǎn)與尺度變化實(shí)驗(yàn)

首先，由于本文算法對GMS算法的主要優(yōu)勢是在旋轉(zhuǎn)與尺度變換的場景中，因此首先在此場景下進(jìn)行實(shí)驗(yàn)，其中VGG數(shù)據(jù)集是標(biāo)準(zhǔn)的特征匹配數(shù)據(jù)集，其boat序列主要用來驗(yàn)證算法是否可以適應(yīng)旋轉(zhuǎn)與尺度變化的場景，圖7關(guān)于VGG數(shù)據(jù)集的實(shí)驗(yàn)中以序列中的boat 1為基準(zhǔn)，橫坐標(biāo)所示2-6是另外5張圖片的序號 (分別對應(yīng)boat 2到boat 6)，而另外3個(gè)數(shù)據(jù)集都是用于視覺同時(shí)定位與建圖或者三維重建的數(shù)據(jù)集，因此本文統(tǒng)計(jì)圖片序列的旋轉(zhuǎn)角度，據(jù)此繪制出在旋轉(zhuǎn)角度從0°到30°變換時(shí)的算法性能變化 (在此類數(shù)據(jù)集中縮放信息不容易確定，因此暫且只考慮角度變換)。繪制出的GMS算法、多角度多尺度版本的GMS算法(圖中簡稱為MGMS)及DWMS 3種算法在4種數(shù)據(jù)集中的表現(xiàn)如圖7所示。

圖7 GMS與DWMS算法的旋轉(zhuǎn)不變性實(shí)驗(yàn)Fig.7 Rotation invariance experiment of GMS and DWMS

從圖7中可以發(fā)現(xiàn)，在旋轉(zhuǎn)變化的情況下，DWMS算法相對GMS算法優(yōu)勢明顯，對多角度多尺度版本的GMS算法也具備一定優(yōu)勢。

最后，為了更加直觀地對比DWMS與GMS算法在這個(gè)序列上的匹配結(jié)果，本文畫出了這兩種算法在boat序列上boat 1與boat 6的匹配效果圖 (見圖8)，其中紅色線代表錯誤匹配，黃色線代表正確匹配。

圖8 兩種算法的匹配效果圖Fig.8 Matching effect diagram of two algorithms

3.4.2 DWMS與GMS算法的其他場景實(shí)驗(yàn)

本文對其他場景下DWMS與GMS算法的匹配性能進(jìn)行了對比。一共在6個(gè)場景下進(jìn)行實(shí)驗(yàn)，分別是VGG數(shù)據(jù)集的bikes、graf、leuven和ubc序列上與TUM數(shù)據(jù)集的freiburg3_structure_texture_far序列上以及Cabinet數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。其中bikes序列展示了模糊變換的場景，graf序列展示了視角變換的場景，leuven序列展示了光照變換的場景，ubc序列展示了圖片壓縮變換的場景，TUM數(shù)據(jù)集的圖片序列展示了紋理與結(jié)構(gòu)豐富的場景，Cabinet數(shù)據(jù)集展示了強(qiáng)光照條件下的低紋理環(huán)境。本文會以每個(gè)序列的第1幅圖片為基準(zhǔn)，將接下來的圖片與其進(jìn)行匹配，并應(yīng)用匹配篩選算法，最終獲得兩種算法 (GMS與DWMS算法)匹配篩選的調(diào)和均值F1，結(jié)果如表1所示。

表1 其他場景下GMS和DWMS算法的F1值對比Table 1 Comparison of F1obtained by GMS and DWMS in other scenes

由表1可以發(fā)現(xiàn)，本文算法在更多的場景中具有較優(yōu)的表現(xiàn)。因此，本文算法在顯著提高了旋轉(zhuǎn)與尺度變換場景性能的同時(shí)，并沒有犧牲其對其他場景下的魯棒性。

3.5 DWMS與RANSAC算法的對比實(shí)驗(yàn)

RANSAC算法是綜合性能均衡的算法，其基于兩視圖平面幾何約束進(jìn)行匹配的篩選，目前被廣泛采用。本文方法是基于局部約束的篩選算法，與基于空間約束的方法原理差異較大，但是兩者應(yīng)用任務(wù)相同，因此有必要對這兩種算法進(jìn)行詳細(xì)的對比實(shí)驗(yàn)。首先在VGG數(shù)據(jù)集上對比兩種算法在各種常見的、具有挑戰(zhàn)性的場景下的表現(xiàn)，然后通過修改閾值，對比兩種算法在TUM數(shù)據(jù)集上的P-R曲線［20］差異，以此來觀察兩種算法的性能特點(diǎn)。

3.5.1 DWMS與RANSAC算法在VGG數(shù)據(jù)集上的對比實(shí)驗(yàn)

首先本文在VGG數(shù)據(jù)集上進(jìn)行兩種算法在不同挑戰(zhàn)下匹配的性能分析。其中，bikes與trees表示的是平滑操作的序列，graf和wall是視角變化的序列，bark和boat是縮放與旋轉(zhuǎn)變換序列，leuven是亮度變化的序列，ubc是圖像壓縮下的序列。由表2可以發(fā)現(xiàn)兩種算法在很多場合下效果相當(dāng)，在視角變化場景下RANSAC算法較有優(yōu)勢，在平滑變換的圖片上本文算法效果更優(yōu)。

表2 VGG數(shù)據(jù)集上兩種算法的對比實(shí)驗(yàn)數(shù)據(jù)Table 2 Comparison of experimental data obtained by two algorithms

3.5.2 DWMS與RANSAC算法在TUM數(shù)據(jù)集上的對比實(shí)驗(yàn)

在一些任務(wù)中可能會要求算法達(dá)到一定的召回率或精確率，本文會在TUM數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，做出兩種方算法的P-R曲線［20］，通過對兩種算法閾值的修改，來考察兩種算法的召回率與精確率特性。如圖9所示，在TUM數(shù)據(jù)集上，室內(nèi)機(jī)器人主動探索的一般場景下，總體來看本文算法所得P-R曲線下的面積更大，綜合性能更加全面。另外在召回率大于90%時(shí)，RANSAC算法具有一定優(yōu)勢，但當(dāng)召回率小于90%時(shí)，DWMS算法綜合性能會更好一些。這說明基于空間約束的RANSAC算法在高召回率要求時(shí)表現(xiàn)較為優(yōu)秀，但是由于兩視圖下平面約束的不完備性，使得其在高精確率要求下表現(xiàn)不佳。而基于局部約束的DWMS算法在一般場景下可以得到更高的精確率。因此在與其他匹配方法［21］進(jìn)行協(xié)同工作時(shí)，RANSAC算法更適合作為前置操作，本文算法更適合作為后置操作。

圖9 兩種算法的P-R曲線圖Fig.9 P-R curve of two algorithms

3.6 算法耗時(shí)對比

本文也對這3種算法的耗時(shí)進(jìn)行了測量。在每張圖片提取2000個(gè)ORB特征點(diǎn)的情況下，測量3種算法在每張圖片上的平均總耗時(shí)，得到GMS算法、DWMS、RANSAC、多尺度多角度版本的GMS算法平均每張圖片耗時(shí)分別為143.12、191.79、185.28、276.57ms。

從上述實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)本文算法的時(shí)間性能相比于單尺度單角度的GMS算法稍有落后，與RANSAC算法相比基本處于同一水平，但優(yōu)于多尺度多角度版本的GMS算法。

4 結(jié)論

本文提出了一種利用動態(tài)窗口進(jìn)行運(yùn)動統(tǒng)計(jì)的特征匹配篩選算法，該算法十分簡單、有效。由于在使用ORB特征進(jìn)行快速特征匹配時(shí)往往會出現(xiàn)原始匹配中錯誤匹配較多的問題，故本文算法利用特征匹配的局部約束關(guān)系完成錯誤匹配的過濾，使用動態(tài)窗口靈活的適應(yīng)尺度與角度變化大的場景，應(yīng)用快速近似最近鄰算法加速動態(tài)窗口的建立過程，提高整體匹配的實(shí)時(shí)性。實(shí)驗(yàn)表明本文算法有效地解決了運(yùn)動統(tǒng)計(jì)方法不能適應(yīng)尺度與旋轉(zhuǎn)變化場景的問題，并保持了其在其他場景下的良好表現(xiàn);同時(shí)本文算法具有良好的時(shí)間性能，可以應(yīng)用于實(shí)時(shí)任務(wù)。