Efficient Initial Pose-graph Generation for Global SfM

作者：Daniel Barath, Dmytro Mishkin, Ivan Eichhardt, Ilia Shipachev, and Jiri Matas

作者：chaochaoSEU|微信公眾號(hào)：3D視覺(jué)工坊

注1：文末附有【視覺(jué)SLAM、激光SLAM】交流群加入方式

注2：激光SLAM系統(tǒng)教程：徹底搞懂基于LOAM框架的3D激光SLAM: 源碼剖析到算法優(yōu)化：https://mp.weixin.qq.com/s/lfA-xwPNvR3-laemEGBAqQ

論文地址：https://www.zhuanzhi.ai/paper/dec76db822ad03e66265875c7477bf49

摘要：我們提出了加速全局SfM算法的初始位姿圖生成的方法。為了避免由 FLANN 形成暫定點(diǎn)對(duì)應(yīng)關(guān)系和由 RANSAC 進(jìn)行幾何驗(yàn)證，這是位姿圖創(chuàng)建中最耗時(shí)的步驟，我們提出了兩種新方法——基于圖像對(duì)（通常連續(xù)匹配）。因此，候選的相對(duì)姿態(tài)可以從部分構(gòu)建的位姿圖的路徑中恢復(fù)?？紤]到圖像的全局相似性和位姿圖邊緣的質(zhì)量，我們提出了 A* 遍歷的啟發(fā)式方法。給定來(lái)自路徑的相對(duì)姿態(tài)，通過(guò)利用已知的對(duì)極幾何，基于描述符的特征匹配變得“輕量級(jí)”。為了在應(yīng)用 RANSAC 時(shí)加快基于 PROSAC 的采樣，我們提出了第三種方法，根據(jù)先前估計(jì)的內(nèi)點(diǎn)概率對(duì)對(duì)應(yīng)項(xiàng)進(jìn)行排序。該算法在來(lái)自 1D SfM 數(shù)據(jù)集的 402 130 個(gè)圖像對(duì)上進(jìn)行了測(cè)試，它們將特征匹配速度提高了 17 倍，姿態(tài)估計(jì)速度提高了 5 倍。

1 引言

SfM在計(jì)算機(jī)視覺(jué)中得到了幾十年的深入研究。大多數(shù)早期的方法采用增量策略，逐步構(gòu)建重建，并在過(guò)程中逐個(gè)仔細(xì)地添加圖像[39, 36, 35, 1, 53, 41]。最近的研究[15, 16, 7, 26, 4, 9, 18, 33, 12, 8, 54]表明，全局方法在重建場(chǎng)景時(shí)同時(shí)考慮所有圖像，比增量技術(shù)具有類似或更好的精度，同時(shí)更有顯著效率。此外，全局方法也不太依賴于局部決策或圖像排序。

通常，SfM的原理包括以下步驟，如圖2所示。首先，在所有圖像中提取特征。這個(gè)步驟很容易并行化，并且具有O(n)個(gè)時(shí)間復(fù)雜度，其中n是重建中要包含的圖像的數(shù)量。然后，這些特征通常用于將圖像對(duì)從最可能匹配到最難匹配的圖像對(duì)排序，例如，通過(guò)視覺(jué)詞袋 [43]。接下來(lái)，通過(guò)匹配檢測(cè)到的特征點(diǎn)的通常高維（例如，128的SIFT[25]）描述符，在所有圖像對(duì)之間產(chǎn)生試探性的對(duì)應(yīng)。然后，通過(guò)應(yīng)用RANSAC [14]來(lái)過(guò)濾對(duì)應(yīng)關(guān)系并估計(jì)所有圖像對(duì)之間的相對(duì)姿態(tài)。通常，特征匹配和幾何估計(jì)步驟是迄今為止最慢的部分，兩者都對(duì)圖像的數(shù)量具有二次復(fù)雜度。此外，特征匹配具有二次最壞情況的時(shí)間復(fù)雜度，因?yàn)樗Q于各自圖像中特征數(shù)的乘積。最后，全局集束調(diào)整（BA）得到了成對(duì)位姿的精確重構(gòu)。有趣的是，與初始的位姿圖生成相比，這個(gè)步驟有可以忽略不計(jì)的時(shí)間需求，即，在我們的實(shí)驗(yàn)中需要幾分鐘。

圖2 全局SfM的原理圖

本文有三個(gè)主要貢獻(xiàn)——三種新算法，可以消除基于RANSAC的幾何估計(jì)的需要，并使基于描述的特征匹配“輕量級(jí)”。首先，提出了一種利用部分建立的位姿圖來(lái)避免基于計(jì)算要求的基于RANSAC的魯棒估計(jì)的方法。為此，我們?yōu)锳?[17]算法提出了一個(gè)啟發(fā)式算法，即使沒(méi)有視圖之間的度量距離，它也可以指導(dǎo)路徑查找。缺乏這樣的距離源于這樣一個(gè)事實(shí)，即位姿圖的邊緣表示相對(duì)位姿，因此，無(wú)論是全局尺度還是任何平移的長(zhǎng)度都是已知的。其次，我們提出了一種通過(guò)使用由A?確定的位姿來(lái)使耗時(shí)的基于描述符的特征匹配“輕量級(jí)”的技術(shù)。這種引導(dǎo)匹配方法使用基本矩陣有效地選擇關(guān)鍵點(diǎn)，從而通過(guò)hashing與位姿一致的對(duì)應(yīng)。第三，提出了一種算法，根據(jù)點(diǎn)對(duì)點(diǎn)對(duì)應(yīng)的歷史來(lái)自適應(yīng)地重新排序——無(wú)論在之前的估計(jì)中，其中一個(gè)或兩個(gè)點(diǎn)都不一致。該方法利用了這些嵌入的特征點(diǎn)可能代表與場(chǎng)景的剛性重建一致的三維點(diǎn)。這種自適應(yīng)排序通過(guò)引導(dǎo)PROSAC [10]盡早找到一個(gè)好的樣本，從而加快了魯棒估計(jì)。在1D SfM數(shù)據(jù)集[52]上進(jìn)行了測(cè)試，例如重建。它們持續(xù)而顯著地加快了位姿圖的生成。

1.1 相關(guān)技術(shù)

魯棒估計(jì)。為了加速魯棒估計(jì)，多年來(lái)提出了許多算法。NAPSAC [31]、PROSAC [10] 和 P-NAPSAC [6] 修改了 RANSAC 采樣策略，以增加早期選擇所有內(nèi)點(diǎn)樣本的概率。PROSAC 利用點(diǎn)的先驗(yàn)預(yù)測(cè)內(nèi)點(diǎn)概率等級(jí)，并從最有希望的點(diǎn)開始采樣。NAPSAC 建立在現(xiàn)實(shí)世界數(shù)據(jù)通常在空間上是一致的這一事實(shí)之上，并從局部鄰域中選擇樣本，在這些鄰域中，內(nèi)點(diǎn)比率可能很高。P-NAPSAC 結(jié)合了 PROSAC 和 NAPSAC 的優(yōu)點(diǎn)，首先在本地采樣，然后逐漸融合到全局采樣中。受 Wald 理論啟發(fā)的序列概率比率測(cè)試 [11] (SPRT) 用于在優(yōu)于先前最佳模型的概率低于閾值時(shí)盡早拒絕模型。所有提到的 RANSAC 改進(jìn)都考慮了單個(gè)、孤立的兩視圖魯棒估計(jì)的情況。在這里，我們利用在對(duì)圖像對(duì)的某些子集進(jìn)行估計(jì)時(shí)產(chǎn)生的信息，其中一些圖像匹配不止一次。

特征匹配。可以通過(guò)多種方式加速，例如，通過(guò)使用二進(jìn)制描述符 [40, 2, 50] 或通過(guò)限制檢測(cè)到的特征數(shù)量，就像在 SLAM 系統(tǒng)中經(jīng)常做的那樣 [30]。然而，對(duì)于一般的 3D 重建問(wèn)題，這通常會(huì)導(dǎo)致不準(zhǔn)確的相機(jī)位姿 [21]。通常，使用近似最近鄰算法，例如 kd-tree 或乘積量化 [29, 23]?；谟布募铀侔ㄊ褂?GPU [22]。這些技術(shù)都沒(méi)有考慮到匹配是在多個(gè)圖像對(duì)上執(zhí)行的，其中在匹配之前，相對(duì)姿態(tài)可能是已知的，至少大約是已知的。

全局圖像的相似性。與匹配（例如視頻序列）相比，匹配無(wú)序圖像集合通常是一項(xiàng)更難、更耗時(shí)的任務(wù)。這有兩個(gè)原因。首先，許多圖像對(duì)可能沒(méi)有場(chǎng)景的任何常見可見部分，并且浪費(fèi)了在匹配嘗試上花費(fèi)的時(shí)間。此外，不匹配是 RANSAC 的最壞情況，它將運(yùn)行最大迭代次數(shù)，通常比可能匹配的情況多幾個(gè)數(shù)量級(jí)。其次，估計(jì)對(duì)極幾何所花費(fèi)的時(shí)間在很大程度上取決于暫定對(duì)應(yīng)關(guān)系的內(nèi)點(diǎn)比率 [13]。內(nèi)點(diǎn)比率反過(guò)來(lái)取決于兩個(gè)觀點(diǎn)之間的差異：差異越大，正確的暫定對(duì)應(yīng)關(guān)系越少 [28, 27]。一個(gè)自然的問(wèn)題是——是否可以將圖像對(duì)從最可能匹配到最難匹配或最不可能匹配？圖像檢索技術(shù)通常用于它，例如，可以重用提取的局部特征，通過(guò)視覺(jué)詞袋[43]找到最有希望的候選匹配，然后使用幾何約束快速重新排序初步列表[34，42]，因?yàn)樗窃?COLMAP SfM [41] 中實(shí)現(xiàn)的。此類系統(tǒng)運(yùn)行良好，但內(nèi)存占用很大，現(xiàn)在已被基于 CNN 的全局描述符 [38, 37, 51] 所克服，它們計(jì)算速度更快并提供更準(zhǔn)確的結(jié)果。

作為初步步驟，我們使用以下方法生成完全連接的圖像相似度圖。首先，我們使用 ResNet-50 [20] CNN 提取 GeM [38] 描述符，在 GLD-v1 數(shù)據(jù)集 [32] 上進(jìn)行預(yù)訓(xùn)練。然后我們計(jì)算所有描述符之間的內(nèi)積相似度，得到一個(gè) n × n 相似度矩陣。相似度矩陣的計(jì)算是我們管道的唯一二次步驟。但是，標(biāo)量乘積運(yùn)算速度極快。實(shí)際上，相似度矩陣的創(chuàng)建和處理花費(fèi)的時(shí)間可以忽略不計(jì)。

2. 因定向行走而產(chǎn)生的相對(duì)位姿

我們提出了一種通過(guò)盡可能避免運(yùn)行 RANSAC 來(lái)加速姿勢(shì)圖生成的方法。核心思想利用了這樣一個(gè)事實(shí)，即在從圖像集合中估計(jì)第 (t+1) 個(gè)圖像對(duì)之間的相對(duì)位姿時(shí)，我們會(huì)得到一個(gè)由 t 個(gè)邊（即 t 個(gè)視圖對(duì)）組成的位姿圖。該位姿圖通常可用于估計(jì)姿勢(shì)，而無(wú)需運(yùn)行類似 RANSAC 的穩(wěn)健估計(jì)。

在接下來(lái)的描述中，我們假設(shè)視圖對(duì)是按照它們的相似度分?jǐn)?shù)排序的。因此，我們從最相似的視圖對(duì)開始姿態(tài)估計(jì)。讓我們假設(shè)我們已經(jīng)成功匹配了 t 個(gè)圖像對(duì)，因此，我們得到了位姿圖

，如圖3所示。

因此，視圖vs和vd之間的相對(duì)位姿通過(guò)W被計(jì)算為φ(W)。

式（1）的問(wèn)題是，一個(gè)錯(cuò)誤估計(jì)的姿態(tài)φ(f)，f屬于W，使整個(gè)φ(W)錯(cuò)誤。因此，我們的目標(biāo)是在給定的距離內(nèi)找到multiple walks，即最大深度被限制，以避免無(wú)限長(zhǎng)的walk。返回的walk將按順序和立即計(jì)算，請(qǐng)參見Alg.1。每當(dāng)發(fā)現(xiàn)一個(gè)新的walk W時(shí)，從姿態(tài)φ(W)和源圖像和目標(biāo)圖像之間的對(duì)應(yīng)關(guān)系vs和vd分別計(jì)算出它的inlier ratio。

Termination。終止。有兩種情況下 尋找和測(cè)試行的程序終止。它們是如下。

1. 當(dāng)沒(méi)有找到更多的walk時(shí)，這個(gè)過(guò)程就結(jié)束了，因?yàn)樵谧畲缶嚯x內(nèi)沒(méi)有找到更多的行。

2. 如果找到了一個(gè)相當(dāng)好的姿勢(shì)P，這個(gè)過(guò)程就會(huì)終止。我們認(rèn)為一個(gè)相對(duì)位姿是合理的，如果它至少有Imin的異常值。

Pose refinement。如果從其中一次walk中成功獲得位姿，則僅從位姿圖Gt的邊緣計(jì)算，而不考慮圖像vs和vd之間的對(duì)應(yīng)關(guān)系。為了提高精度和獲得P?，我們采用了由新估計(jì)的模型P初始化的迭代重新加權(quán)的最小平方擬合。

Failures。在某些情況下，在視圖vs和vd之間至少存在一次walk，但隱含的位姿是不正確的，即，它不會(huì)導(dǎo)致合理數(shù)量的傾斜度。在這些情況下，我們應(yīng)用了傳統(tǒng)的方法，即基于RANSAC的魯棒估計(jì)。

Visibility。在O（1）時(shí)間內(nèi)，可以通過(guò)聯(lián)合查找算法在 O(1) 時(shí)間內(nèi)確定在視圖 vs 和 vd 之間的姿勢(shì)圖中是否至少有一次walk。平均而言，更新的時(shí)間復(fù)雜度為O（log(n)）。

Parallel graph building。通過(guò)使用每個(gè)線程匹配下一個(gè)最佳視圖對(duì)的讀寫器鎖定機(jī)制，構(gòu)建圖 G、檢查可見性、查找和評(píng)估在多個(gè) CPU 上并行運(yùn)行是有效的。讀取器是試圖在兩個(gè)視圖之間尋找游走的進(jìn)程，或者是檢查視圖 vs 是否從 vd 可見的進(jìn)程。一個(gè)進(jìn)程只有在向姿勢(shì)圖添加新邊或更新聯(lián)合查找方法以進(jìn)行可見性檢查時(shí)才成為寫入者，這兩者都只需要幾個(gè)操作。

2.1.位姿圖遍歷

如何有效地在視圖 vs 和 vd 之間找到一個(gè)步行是一個(gè)相當(dāng)重要的問(wèn)題。有許多圖遍歷，但是，其中大多數(shù)不適合在合理的時(shí)間內(nèi)在大圖中返回游走。我們選擇 A* [17] 算法，因?yàn)楫?dāng)存在良好的啟發(fā)式算法時(shí)，它可以很好地完成此類任務(wù)。在本節(jié)中，我們提出了一種通過(guò)為 A* 算法定義啟發(fā)式方法來(lái)獲得位姿圖 Gt 中多次游走的方法。

目標(biāo)是定義一個(gè)啟發(fā)式方法，它在訪問(wèn)盡可能少的頂點(diǎn)的同時(shí)引導(dǎo) A? 算法從節(jié)點(diǎn) vs 到節(jié)點(diǎn) vd。由于給定了一個(gè)相對(duì)位姿圖，我們無(wú)法定義度量，即測(cè)量視圖對(duì)的歐幾里得距離。當(dāng)具有相對(duì)位姿時(shí)，全局和局部尺度仍然未知，因此，所有平移都有單位長(zhǎng)度。因此，不清楚兩個(gè)視圖彼此接近還是遠(yuǎn)離。建議的啟發(fā)式算法由兩個(gè)函數(shù)組成。

3. 帶有位姿的引導(dǎo)匹配

在匹配圖像集合時(shí)，最耗時(shí)的過(guò)程通常是局部描述符匹配 [21]，也就是建立暫定對(duì)應(yīng)關(guān)系。原因是它具有 O(n2) 復(fù)雜度，分別與局部特征的數(shù)量（即單個(gè)圖像對(duì)）和圖像的數(shù)量（即整個(gè)集合）有關(guān)。我們已經(jīng)解決了第二個(gè)問(wèn)題（參見第 1.1 節(jié)），但是匹配單個(gè)圖像對(duì)仍然需要大量時(shí)間。加速特征匹配的常用方法是使用近似最近鄰搜索，而不是精確搜索，例如使用 FLANN [29] 中實(shí)現(xiàn)的 kd-tree 算法。然而，即使是近似匹配仍然需要相當(dāng)長(zhǎng)的時(shí)間并降低相機(jī)姿勢(shì)的準(zhǔn)確性 [21]。我們提出了一種替代解決方案——利用來(lái)自當(dāng)前姿勢(shì)圖中的步行的姿勢(shì)來(lái)建立暫定的對(duì)應(yīng)關(guān)系。通過(guò)僅檢查與姿勢(shì)一致的對(duì)應(yīng)關(guān)系，這些姿勢(shì)將用于使標(biāo)準(zhǔn)描述符匹配“輕量級(jí)”。

Guided feature matching with pose. 讓我們假設(shè)我們有一組關(guān)鍵點(diǎn) Ki， Kj 分別在第 i 個(gè)和第 j 個(gè)圖像中，以及從第 i 個(gè)圖像到第 j 個(gè)圖像的相對(duì)姿態(tài) Pij = (tij, Rij)∈SE(3)。人們可以很容易地計(jì)算出基本矩陣 Eij = [tij]×Rij，并使用它通過(guò) Sampson 距離或?qū)ΨQ對(duì)極誤差 [19] 來(lái)測(cè)量點(diǎn)對(duì)的距離。因此，目標(biāo)是找到點(diǎn)對(duì) (pi, pj)，其中 pi ∈ Ki, pj ∈Kj 和 (pi, pj,Eij) 小于內(nèi)點(diǎn)-離群點(diǎn)閾值。與使用 L2 范數(shù)在所有可能關(guān)鍵點(diǎn)的高維描述符向量上定義特征匹配的傳統(tǒng)方法相比，我們建議使用基本矩陣選擇一小部分候選匹配。因此，描述符匹配變得明顯更快。

由于在 2D 中進(jìn)行匹配，該過(guò)程可以通過(guò)散列而不是蠻力或近似成對(duì)過(guò)程來(lái)完成。使用基本矩陣，在源圖像中找到可能的點(diǎn)對(duì)降級(jí)為在目標(biāo)點(diǎn)中找到相應(yīng)的極線投影到正確位置的點(diǎn)，即，到源圖像中的選定點(diǎn)上。因此，可以根據(jù)源圖像中的極線將目標(biāo)圖像中的點(diǎn)放入 bin 中。一個(gè)直接的選擇是在對(duì)極線的角度上定義 bin，如圖 5 所示。我們?cè)谶M(jìn)一步的部分中稱這種技術(shù)為對(duì)極散列 (EH)。請(qǐng)注意，即使內(nèi)在相機(jī)參數(shù)未知，EH 也適用，因此，我們只有一個(gè)基本矩陣。

圖5 對(duì)極哈希。圖像 C2中的點(diǎn) p2 被分配給 C1（灰色區(qū)域）中對(duì)應(yīng)的極線 l 選擇的 bin。bin 定義在 C1 中對(duì)極線的角度上。對(duì)極是 e1 和 e2。

讓我們將第二個(gè)圖像中的點(diǎn)(x,y)的第一個(gè)圖像中對(duì)應(yīng)的上極性線l的角度表示為α(x,y)∈[0；π)。由于上極性幾何學(xué)的性質(zhì)，某些α(x,y)角是不可能的。因此，我們定義了由有效角組成的間隔，因此，我們將用一些箱子覆蓋為[a, b]：

Point (0， 0) 是第二個(gè)圖像的左上角，w2 是它的寬度，h2 是它的高度。散列點(diǎn)時(shí)，bin 的大小將為 (b?a)/( #bins)。這是實(shí)踐中的一個(gè)重要步驟，因?yàn)橛袝r(shí)對(duì)極點(diǎn)遠(yuǎn)在圖像之外，因此角度范圍 < 1。如果沒(méi)有自適應(yīng) bin 大小計(jì)算，算法在這種情況下不會(huì)加速匹配。注意 [a, b] 是 [0, π) 當(dāng)對(duì)極落在圖像內(nèi)時(shí)。在進(jìn)行傳統(tǒng)的描述符匹配時(shí)，我們只考慮那些位于相應(yīng) bin 中且 Sampson 距離低于用于確定姿勢(shì)的閾值的匹配。

執(zhí)行引導(dǎo)后，對(duì) 2 到 30 個(gè)可能的候選對(duì)象而不是所有關(guān)鍵點(diǎn)進(jìn)行描述符匹配。為了進(jìn)一步清理它，我們應(yīng)用具有自適應(yīng)比率閾值的標(biāo)準(zhǔn) SIFT 比率測(cè)試 [25, 21]，這取決于最近鄰居的數(shù)量——池越小，比率測(cè)試越嚴(yán)格。詳細(xì)信息已添加到補(bǔ)充材料中。

如果找到一個(gè)好的位姿，則在 A* 之后應(yīng)用匹配過(guò)程。由于 A? 需要一組對(duì)應(yīng)關(guān)系來(lái)確定位姿是否合理，因此我們使用來(lái)自當(dāng)前圖像可見的點(diǎn)軌跡的對(duì)應(yīng)關(guān)系。當(dāng)成功匹配新圖像對(duì)時(shí)，將計(jì)算并更新多視圖軌跡。由于全局和增量 SfM 算法都需要點(diǎn)跟蹤，因此此步驟不會(huì)增加最終處理時(shí)間。

4. 自適應(yīng)對(duì)應(yīng)關(guān)系排序

在本節(jié)中，我們提出了一種策略，在大規(guī)模問(wèn)題中進(jìn)行成對(duì)相對(duì)位姿估計(jì)時(shí)，自適應(yīng)地設(shè)置 PROSAC 采樣 [10] 的點(diǎn)對(duì)應(yīng)權(quán)重。PROSAC 利用點(diǎn)的先驗(yàn)預(yù)測(cè)內(nèi)點(diǎn)概率等級(jí)，并從最有希望的點(diǎn)開始采樣。逐漸地，抽取不太可能導(dǎo)致所尋求模型的樣本。所提出算法的主要思想是基于這樣一個(gè)事實(shí)，即在匹配圖像集合時(shí)，在一張圖像中檢測(cè)到并與其他圖像匹配的特征經(jīng)常出現(xiàn)多次。因此，在 PROSAC 采樣中將首先使用包含較早內(nèi)點(diǎn)點(diǎn)的對(duì)應(yīng)關(guān)系。相反，之前圖像中的異常點(diǎn)應(yīng)該稍后繪制。

假設(shè)我們得到第 t 個(gè)圖像對(duì)以匹配關(guān)鍵點(diǎn) Ki、Kj 的集合。來(lái)自任一組的每個(gè)關(guān)鍵點(diǎn) p 的得分為 s(t) p∈ [0, 1] 用于確定其在所有關(guān)鍵點(diǎn)中的異常值等級(jí)。在成功估計(jì)圖像對(duì)的姿態(tài) Pij 后，我們得到了 (p, q) 的概率 P ((p, q) | Pij) 是給定位姿 Pij 的異常值，其中 (p，q) 是一個(gè)暫定的對(duì)應(yīng)關(guān)系，p ∈Ki，q ∈Kj。概率 P ((p, q) | Pij)可以計(jì)算，例如，在 MSAC [49]、MLESAC [49] 或 MAGSAC++ [6] 中，從假設(shè)正態(tài)或 χ2 分布的點(diǎn)到模型殘差。由于我們不知道概率 P (p| Pij) 和 P (q| Pij) 如何相關(guān)，我們假設(shè) p 和 q 與剛性重建一致是獨(dú)立事件，因此， P((p, q)| Pij) = P(p|Pij)P(q|Pij)。為了能夠分解概率 P ((p, q) | Pij)，我們假設(shè) P (p|Pij)=P (q| Pij) = sqrt(P ((p, q) | Pij))。然后在第 t 個(gè)圖像對(duì)匹配為 s(t+1) p= s(t)pP (p| Pij) 和 s(t+1)q = s(t)q 之后，使用此概率更新分?jǐn)?shù) sp 和 sq。讓我們?cè)O(shè)置 s(0) p = 1，因?yàn)樗嘘P(guān)鍵點(diǎn)在開始時(shí)都可能是異常值。

當(dāng)使用 PROSAC 采樣匹配第 (t + 1) 個(gè)圖像對(duì)時(shí)，對(duì)應(yīng)關(guān)系根據(jù)它們的離群點(diǎn)等級(jí) s(0) p 逐漸排序，使得第一個(gè)最不可能是離群點(diǎn)。

5. 實(shí)驗(yàn)

旋轉(zhuǎn)和平移誤差（以角度為單位）和處理時(shí)間（以秒為單位）的累積分布函數(shù)如圖 6 所示。我們?cè)谶@里不包括 MST，因?yàn)樗ヅ涞膱D像對(duì)（9922）比其他方法（402）少得多 130)。在準(zhǔn)確性方面，基于 A* 的技術(shù)導(dǎo)致最準(zhǔn)確的旋轉(zhuǎn)矩陣，同時(shí)具有與基于廣度優(yōu)先和窮舉匹配相似的平移誤差。在處理時(shí)間方面，所提出的基于 A* 的技術(shù)導(dǎo)致比 EM 或 BF 更有效的姿勢(shì)圖生成。請(qǐng)注意，處理時(shí)間曲線中的斷點(diǎn)是由將 RANSAC 迭代的最大次數(shù)設(shè)置為 5000 引起的。這是為了避免在內(nèi)點(diǎn)比率較低時(shí)運(yùn)行 RANSAC 時(shí)間過(guò)長(zhǎng)。

圖 6 在 1DSfM 數(shù)據(jù)集的所有場(chǎng)景上，由不同初始化技術(shù)生成的姿態(tài)圖的誤差（以 ee 為單位）和處理時(shí)間（以秒為單位）的累積分布函數(shù)。所有算法都返回了 402 130 個(gè)姿勢(shì)。

成對(duì)姿態(tài)估計(jì)算法的平均、中值和總處理時(shí)間如表 1 所示。運(yùn)行時(shí)間也包含這些情況，當(dāng) A* 或廣度優(yōu)先遍歷沒(méi)有找到有效姿態(tài)時(shí)，因此， GC-RANSAC 用于恢復(fù)姿勢(shì)。A* 算法導(dǎo)致幾乎一個(gè)數(shù)量級(jí)的加速，其中值時(shí)間約為 比GC-RANSAC低20倍。它驗(yàn)證了所提出的啟發(fā)式算法，即廣度優(yōu)先算法明顯慢于 A*。因此，所提出的啟發(fā)式方法成功地指導(dǎo)了姿勢(shì)圖中的尋路。

我們比較了使用或不使用由 A* 算法確定的姿勢(shì)的特征匹配速度。在 FLANN 和蠻力匹配中，這意味著我們找到了所有導(dǎo)致對(duì)極誤差小于內(nèi)部異常閾值的候選匹配。然后通過(guò)基于描述符的匹配選擇最佳候選者。運(yùn)行時(shí)間在表 2 中報(bào)告。使用姿勢(shì)顯著加快了基于 FLANN 的算法和蠻力算法。與傳統(tǒng)的基于 FLANN 的特征匹配相比，所提出的對(duì)極散列可實(shí)現(xiàn) 17 倍以上的加速。此外，通過(guò)對(duì)極散列，可以精確地找到鄰居，而不是像 FLANN 那樣進(jìn)行近似。

表 4 顯示了對(duì) PROSAC 使用不同對(duì)應(yīng)排序技術(shù)的穩(wěn)健估計(jì)的平均、中值和總處理時(shí)間（以秒為單位）。比較了三種方法：最初為 RANSAC 提出的均勻匹配（無(wú)序）；PROSAC 當(dāng)對(duì)應(yīng)關(guān)系根據(jù)其 SIFT 比率排序時(shí) [10]；以及考慮來(lái)自早期估計(jì)的點(diǎn)的先驗(yàn)信息而提出的自適應(yīng)重新排序。與均勻采樣相比，根據(jù)其 SIFT 比率對(duì)對(duì)應(yīng)項(xiàng)進(jìn)行排序?qū)⒐烙?jì)速度提高了 10%，而所提出的自適應(yīng)重新排序?qū)е缕骄~外的 8% 加速。

表 3 報(bào)告了由傳統(tǒng)詳盡匹配 (EM)、廣度優(yōu)先圖遍歷 (BF)、建議的基于 A* 的圖遍歷和使用最小生成樹 (MST) 生成的姿勢(shì)圖初始化的 Theia 結(jié)果。雖然基于最小生成樹的姿態(tài)圖的生成速度非常快，但可以看出全局 SfM 算法不足以提供合理大小的重建。由 MST 初始化時(shí)重建的平均視圖數(shù)量明顯低于使用其他技術(shù)?？梢钥闯?，所提出的基于 A* 的方法導(dǎo)致與傳統(tǒng)方法相似的視圖數(shù)量和相似的錯(cuò)誤。

在圖 7 中，A*traversal 訪問(wèn)的平均節(jié)點(diǎn)數(shù)（左）和獲得的準(zhǔn)確相對(duì)姿勢(shì)的比率（右）被繪制為權(quán)重 λ 的函數(shù)。不同的曲線表示不同的最大深度。

6.結(jié)論

與初始姿態(tài)圖生成相比，全局 SfM 算法的最終集束調(diào)整的時(shí)間需求可以忽略不計(jì)。為了將這一步加快近一個(gè)數(shù)量級(jí)，我們提出了三種新算法。用于估計(jì)來(lái)自 1D SfM 數(shù)據(jù)集的所有場(chǎng)景的位姿圖的標(biāo)準(zhǔn)程序（即，F(xiàn)LANN 的特征匹配；類似 RANSAC 的穩(wěn)健估計(jì)的姿勢(shì)估計(jì)）在單個(gè) CPU 上總共花費(fèi)了 726 487 秒——大約 202 小時(shí)。通過(guò)使用所提出的算法集（即基于 A* 的姿態(tài)估計(jì)；用于匹配的對(duì)極散列；自適應(yīng)重新排序），總運(yùn)行時(shí)間減少到 105593 秒（29 小時(shí)）。在實(shí)驗(yàn)中，A* 在 93:8% 的圖像對(duì)中找到了有效位姿。因此，由 RANSAC 進(jìn)行的傳統(tǒng)基于 FLANN 的特征匹配和姿態(tài)估計(jì)僅應(yīng)用于 6:2 % 的圖像對(duì)。

微信交流群

歡迎加入「3D視覺(jué)工坊」交流群，方向涉及3D視覺(jué)、計(jì)算機(jī)視覺(jué)、深度學(xué)習(xí)、vSLAM、激光SLAM、立體視覺(jué)、自動(dòng)駕駛、點(diǎn)云處理、三維重建、多視圖幾何、結(jié)構(gòu)光、多傳感器融合、VR/AR、學(xué)術(shù)交流、求職交流等。工坊致力于干貨輸出，為3D領(lǐng)域貢獻(xiàn)自己的力量！歡迎大家一起交流成長(zhǎng)~

添加小助手微信：CV_LAB，備注學(xué)校/公司+姓名+研究方向即可加入工坊一起學(xué)習(xí)進(jìn)步。