特征點法的VSLAM系統中，特征點并不是越多越好；相反， 少量 并且 質量高 的點會讓這個SLAM系統位姿精度更高，且消耗更少的存儲資源和計算資源。本文基于上述情況，提出了一種在SLAM系統中實現地圖點稀疏化的有效的圖優化方法，進而減少一般特征點SLAM系統中的3D點和關鍵幀，減少了計算和存儲資源，同時提高了位姿估計的精度。

Abstract

當將SLAM用于真實世界中實際的問題（例如自動駕駛、無人機和AR設備）上時，其內存占用和計算成本是限制性能和應用范圍的兩個主要的因素；在離散的特征點SLAM算法中，解決這個問題的一個有效的方式是通過local BA 和global BA刪除點進而限制地圖點的規模；本項研究中提出了一種在SLAM系統中 實現地圖點稀疏化的有效的圖優化方法，具體上作者將最大位姿可見性和最大空間多樣性問題表示成一個最小成本最大流量圖優化問題。作者所提出的方法可以在現存的SLAM系統中作為額外的一個步驟，因此它可以用于傳統 和學習的SLAM系統；通過大量的實驗評估證明所提出的方法用 大約1/3的地圖點 和 1/2的計算 實現了更精確的相機位姿。

Introduction

Motivation：基于特征點法的VSLAM系統具有較好的處理速度和計算效率從而達到實時的性能，但是VSLAM系統最大的缺陷之一是隨著地圖大小的增長，內存大小和計算成本會呈二次增長，解決這個日益增長的資源需求有兩個方向：一個是高效地求解優化問題[40]，比如許多算法都試圖利用地圖拓撲或問題結構來降低計算成本；另一個是減小整個SLAM系統的大小，包括特征/幀選擇、關鍵幀/3D點抽取等，它們大多集中于減少數據量或計算成本，同時略微犧牲位姿精度；在現有的SLAM系統中，為了在保持位姿定位精度的同時減少地圖大小和計算成本，作者引入了一種有效的點稀疏化算法，該算法可以直接集成到任何特征點的視覺SLAM系統中。

Contribution：

提出了一個 相機位姿對 和 3D點最大的點可見性 的 圖表示 方法；

提出了一種新的cost用于最大化圖像空間上二維特征的空間多樣性；

提出了一種 基于最小代價最大流量（minimum-cost maximum-flow）點稀疏化算法來控制剩余點的數量；

提供了詳細的位姿準確性、點減少和各種室內/室外公共數據集的改進速度比較；

據作者所知，本文的工作是第一次將關于特征和幀關系的多個屬性同時集成到稀疏化特征圖中，也是第一次為稀疏化地圖的本地化性能的維護提供了驗證。

圖1 上方圖：ORB-SLAM2生成的地圖點；下方圖：稀疏化圖；在構建地圖和在地圖上進行定位時，估計位姿精度都有一定的提高；與上方圖相比，下方圖的地圖包含39%的點

Related Work

針對VSLAM優化問題的快速計算和低計算量為目標的問題空間縮減方法可以大致分為兩個部分的工作；

第一個部分的工作研究了基于圖優化的快速位姿優化方法。[35]和[36]通過使用因子下降法和非循環因子下降法減少KLD (Kullback-Leibler Divergence)的迭代優化，提高了SLAM的準確性和速度；[29]提出了節點選擇問題相對于在結果稀疏化中付出的代價；[22]通過邊緣化舊節點的稀疏化節點，同時保持剩余節點的所有信息，并給出一個標準化的最小化問題，以保持圖組合的稀疏性；[39]設計了一種動態變量重新排序的方法，為快速增量Cholesky分解在增量更新和批量更新之間做出決定減少了與逆排列相關的工作量，為增量SLAM算法提供了節省計算量的方法；[26]提出了一種啟發式方法，通過消除復雜性度量來彌合圖結構及其計算之間的分析差距，從而減少批量優化和增量優化的計算量；[21]提出固定滯后方法，邊緣化SLAM問題中的變量，最小化圖稀疏化過程中的信息損失；[6]使用一種基于信息的方法和最小化問題的增量版本來高效地稀疏地標和姿態的數量，而不影響估計軌跡的準確性。

另一個部分的工作對SLAM中的圖幾何進行了縮減，以最小的信息損失對特征、點、幀進行了抽取。[2]提出了一種自適應的非最大抑制(ANMS)方法，可以快速均勻地重新分割圖像中的關鍵點，該算法通過對搜索范圍的平方逼近來抑制無關點，降低了計算復雜度，并根據圖像維數初始化搜索范圍，收斂速度更快；[15]通過通過 SDC (suppression via disk covering)算法高效地選擇一個空間分布的關鍵點集，該算法基于逼近最近鄰和貪婪方法對關鍵點進行聚類；[37]提出了一種通過SLAM系統跟蹤，利用連續幀之間的時間相關性和加權特征，通過多幀引用提取有用特征的策略。

Methods

作者在ORB-SLAM2上融合了本文所提出的方法；一旦通過n > 1幀的三角化估計的地圖點之間的連通性和相機姿勢被表示為一個具有流量和成本的圖結構，作者提出了一個點稀疏化的圖表示的解決方案。

A. ORB-SLAM2 Overview

ORB-SLAM2中影響內存和計算需求的關鍵因素之一是地圖點的數量和與地圖點相關的局部興趣點特征，隨著BA的增長，local和global BA的規模呈二次增長，這反過來又需要顯著增加的計算成本；所以主要研究方向有兩個：

（1）只提取相關的局部特征和點

（2）剔除這些對位姿優化貢獻不大的特征或點；在提出的方法中，在提取到足夠的特征點和臨時生成地圖點之后，作者著重于抽取點來建立一個更簡化的BA問題，并且通過大量的實驗驗證了該方法的有效性。

B. Graph Representation for Point Sparsification

圖2 （a）四個關鍵幀(A、B、C和D)共享3D空間中的三個點的事例；（b）由(a)構造二分圖；一共有4層頂點:兩個特殊頂點，一組點頂點，一組幀對頂點；在每個邊的上面，為示例寫了容量/成本值

圖2顯示了要在 BA 中優化的簡化局部地圖結構的示例，這里作者建立一個有向流圖結構來解釋幀和它們所看到的點之間的關系，該方法解決的核心問題是如何在local 和 global BA 問題中選擇結構變化最小的點子集，它相當于如何選擇這樣的點，使BA問題中的約束數量最大化，同時使點的數量最小化；此外，在調整每幀6DOF位姿時，圖像空間上的殘差構成了每個相機位姿的誤差協方差矩陣，殘差均勻分布有助于使協方差得到很好的正則化，相反，如果所有的特征點都聚集在圖像空間的一個角落附近，姿態調整問題空間的邊緣都很陡峭，導致很難有效地解決；同樣，兩幀之間的幀baseline越寬，各點約束的雅可比矩陣值也就越相似。直觀上看，如果一個點的兩幀基線角度接近于零，深度估計會變得困難，點調整也會變得困難。

有以上三點觀察結果可以概括為選點的三個目標：

最大點可見性:最大限度地共享一個點的幀數（選擇在多幀之間觀測到多次的點）；

最大空間多樣性:特征點在圖像空間上的分布是多樣化的（要求點分布均勻）；

最大幀baseline長度:使任意兩幀之間的相機中心距離最大化（這個是關鍵幀選擇）。

為了集成一個算法解決上述問題，作者提出一種基于有向圖表示的新方法，即節點對應于點和位姿對；在此圖中，利用節點之間的成本和容量能力，將節點的實際點可見性、空間多樣性和基線轉化為最小成本最大流量的二部分圖。

1）Point Connectivity：首先考慮一個點和共享該點的特征點的frames之間的連通性，連通性高的點表示高可見性，具有魯棒的局部特征，這種高度可見的點容易被選擇，因為它們在位姿圖上的多個位姿提供了強約束；將Vso 與點vpi 之間的邊的代價函數cc 定義為具有高連通性的vpi 的較低的代價值：

2）Spatial Diversity of Interest Points：ORB- slam2在ORB特征提取步驟中包含了空間均勻分布的興趣點選擇過程，但是興趣點的初始均勻分布并不能保證在下面的步驟(包括點稀疏化)中得到相似的興趣點分布；這里定義了邊緣e(vP, vF)的空間代價cs，以確保在點稀疏過程中特征分布保持甚至改善：

3）Frame Pair Baseline：這里考慮了每一幀對的基線距離；對幀對中觀測到的超過一定距離的點進行優化可以更可靠地進行，并可能對補償關鍵幀之間累積的漂移誤差有用；基線代價cb 應用于vF 和vsi 之間的邊：

C. Minimum Cost Maximum Flow Graph Optimization

上面 B. Graph Representation for Point Sparsification 將整個有向圖構建出來了，本節描述如何計算這個有向圖。作者使用最小代價最大流算法[11]來解決上述圖問題去計算從 Vso 到 Vsi 的最大流量，進而使總的代價最小：

其中 f(e) 是邊 e 上的流量；通過計算在容量約束下成本最小的最優流量，能測量點和幀之間邊上的流量，與上述定義的三個理想條件的滿足程度有關；計算流量后，只取e邊( Vso, Vpi)上流量大于預先設定閾值θf的點pi；Goldberg算法[17]保證最差情況下的時間復雜度限制在:

其中n是頂點總數，m是邊總數，C是最大的輸入成本。

Experiment

實驗部分先是給出了所提出的方法的實現細節，然后將該方法在各種數據集上進行實驗并對結果進行分析。

A. Implementation Details

本文的系統建立在ORB-SLAM2上。具體的，本文的方法在ORB-SLAM2 的 local mapping部分每個 local BA 之前執行；作者使用兩種方式修改了ORB-SLAM2，首先是將現有的多線程處理改為單線程處理，目的如下：

（1）對總運行時間的客觀評估

（2）確定效果評估

（3）由于處理延遲，在優化步驟中禁用幀丟失；第二點是因為ORB-SLAM2中確定關鍵幀的條件與來自local mapping線程的跟蹤點數量和 local mapping線程的狀態有關，因此當應用單線程處理或點稀疏化時，local BA執行的數量會發生變化，所以這里作者使用基于平移和旋轉變化量的確定性關鍵幀插入準則用來衡量所提出的點稀疏化的影響。

整個實驗中，作者設置 θf 為邊緣容量的一半，同時使用Google Optimization Research Tools解決最小成本最大流圖問題。

B. Performance Evaluation

作者在EuRoC、TUM、ScanNet、ICL-NUIM和KITTI數據集上進行了評估，使用RMS ATE度量位姿精度，通過計算估計位姿與gt位姿之間的絕對距離來表示估計軌跡的全局一致性；下面是在各個數據集上的實驗情況及說明。

表1 在EuRoC序列上選擇點和關鍵幀的比例

圖3 EuRoC上的總運行時間和RMS ATE與表I相關

表 1 和圖 3 為雙目模式下EuRoC數據集的實驗結果，參數 M 代表；特征點減少的同時，關鍵幀也會減少，因為它們有連接的映射點的減少會導致連接低于閾值的關鍵幀自動退出，總體處理時間也大大減少，因為通過減少約束的數量，BA和跟蹤過程；圖 3 顯示了表I中實驗的總運行時間和RMS ATE的圖，結果顯示所提出的方法減少了 1/3 的運行時間并且性能上幾乎保持甚至提高，ATE差值最多在4cm以內；參數M不同 ，證明所提出的方法不平衡屬于一個位姿的約束成功地刪除了只對優化有負面影響的點；

表2 通過多個不同的M值對所提出的方法進行比較；序列依次為TUM，ICL-NUIM和ScanNet

作者將所提方法在TUM，ICL-NUIM和SCANNET數據集上也進行了實驗對比；因為與EuRoC數據集相比，空間比例尺不同，生成的地圖點更少，所以M的取值范圍不同；圖1是ScanNet在scene0000上保存的地圖點的可視化，以及根據估計軌跡得到的場景的三維重建環境。

表3 在雙目式下使用KITTI對室外環境的實驗結果

作者使用KITTI數據集對室外環境進行了驗證，表 3 是M=100 和M=200的實驗結果，與室內環境不同的是，它在一個相對較小的空間尺度上采用了許多地圖點和多個連接，并有許多重新審視的點，關鍵幀丟失在室外環境中并不常見；時間的增加也不像在室內那樣顯著；然而，當地圖點選擇像室內其他結果一樣保守執行時，也可以觀察到性能的提高。

C. Comparisons

圖4 圖像上選定的關鍵點的可視化；從上到下，原來的方法，ANMS，作者的方法；右下圖顯示了關鍵點的覆蓋范圍和聚類情況

表4 與ANMS點選擇的比較包括原始結果；最低的RMS ATE用粗體表示

自適應非最大抑制(ANMS)算法[2]通過高效計算選擇待均勻分布的圖像上檢測到的關鍵點，提高了SLAM和圖像配準性能；表IV顯示了在點選擇比例最低的情況下應用ANMS和根據ANMS產生的地圖點總數應用作者的方法時的結果，作者的方法4例中有3例的結果優于ANMS和原方法；圖4是通過ANMS和作者的方法對一幅圖像中選定的局部感興趣點的可視化。

D. Ablation Study

表5 在TUM數據集上以部分和全部成本降低姿態精度

該部分評估了三種代價的有效性；當使用所有這三種成本時，最低的ATE是通過在大基線下更多地使用幀來實現的，同時最大限度地提高位姿連接和空間多樣性。

E. Localization Test

本節通過從相同場景中收集的兩組序列來檢驗原始地圖和稀疏地圖的位姿定位精度；使用 EuRoC dataset的MH01 & MH02 和 ScanNet的scene0000 00 & scene0000 01 進行測試；對MH01和scene0000 00分別采用原始和稀疏兩種模式構建參考地圖，對MH02, scene0000 01進行定位。

表6 定位精度評價

具體結果如上所示，MH01序列的稀疏化地圖相比原始地圖只包含了23.9%的點和34.4%的關鍵幀，同時計算時間和地圖大小有顯著性減小，但是位姿精度上升了；與原始地圖相比，scene0000只使用了38.6%的點和59.1%的關鍵幀，姿態誤差也減少了。

Conclusion

本文介紹了一種基于圖的SLAM點稀疏化方法，該方法在點稀疏化過程中同時實現了3個目標:最大點連通性（maximizing the point connectivity）、最大空間多樣性（maximizing the spatial diversity）和最大幀基線長度（ maximizing frame baseline length）；以ORBSLAM2為baseline，提出的方法在保持甚至提高局部映射過程中姿態跟蹤精度的同時，大大減小了地圖尺寸；提出的方法可以用于地圖創建后的后壓縮或global BA前的預處理，它通常適用于基于局部特征SLAM系統，包括多傳感器SLAM，并提供了有效的地圖抽取和加速，可用于其他具有計算挑戰性的環境，如可穿戴設備。

未來的研究方向包括邊緣圖優化的快速優化，以及考慮三維點的空間密度和二維特征多樣性。