【新智元導讀】今天分享一篇被今年CVPR接收的論文。該文提出的算法可以高效處理百萬量級的點組成的大場景3D點雲，同時計算效率高、內存佔用少，能直接處理大規模點雲，不需要複雜的預處理/後處理，比基於圖的方法SPG快了接近200倍，這對自動駕駛和AR非常關鍵。
牛津大學和國防科技大學合作的一篇題為「RandLA-Net: Efficient Semantic Segmentation of Large-Scale Point Clouds」的論文已被今年CVPR接收，今天為大家解讀這篇論文。
論文地址：https://arxiv.org/pdf/1911.11236.pdf
TensorFlow代碼：https://github.com/QingyongHu/RandLA-Net
本文提出了一種針對大規模三維點雲場景的輕量級、高效點雲語義分割新算法RandLA-Net。通過對現有的採樣策略進行全面綜合的分析，本文採用簡單高效的隨機採樣來顯著地減少計算量以及內存消耗，並且引入了全新的局部特徵聚合模塊持續地增大每個點有效的感受野，保留大多數有效的信息。
RandLA-Net能直接處理大規模點雲，不需要複雜的預處理/後處理，比基於圖的方法SPG快了接近200倍，有助於解決自動駕駛和AR等領域的核心問題。
高效處理百萬量級的點組成的大場景3D點雲，比基於圖的方法SPG快近200倍
Introduction
實現高效、準確的大場景三維點雲語義分割是當前三維場景理解、環境智能感知的關鍵問題之一。然而，由於深度傳感器直接獲取的原始點雲通常是非規則化 (irregular)、非結構化 (unstructure)並且無序 (orderless)的，目前廣泛使用的卷積神經網絡並不能直接應用於這類數據。
Motivation
自從2017年能夠直接在非規則點雲上進行處理的PointNet [1] 被提出以來，越來越多的研究者開始嘗試提出能夠直接處理非規則點雲的網絡結構，出現了許多諸如PointNet++ [2], PointCNN [3], PointConv [4] 等一系列具有代表性的工作。儘管這些方法在三維目標識別和語義分割等任務上都取得了很好的效果，但大多數方法依然還局限於在非常小(small-scale)的點雲上(e.g., PointNet, PointNet++, Pointconv等一系列方法在處理S3DIS數據集時都需要先將點雲切成一個個1m×1m的小點雲塊, 然後在每個點雲塊中採樣得到4096個點輸入網絡)。這種預處理方式雖然說方便了後續的網絡訓練和測試，但同時也存在著一定的問題。舉例來說，將整個場景切成非常小的點雲塊是否會損失整體的幾何結構？用一個個小點雲塊訓練出來的網絡是否能夠有效地學習到空間中的幾何結構呢？
圖 1. PointNet在Area 5中的分割結果
帶著這樣的疑問，我們對PointNet在S3DIS數據集Area 5上的分割結果進行了可視化。如上圖highlight的區域所示，PointNet錯誤地將一張桌子的左半部分識別為桌子，而將右半部分識別為椅子。造成這樣明顯不一致結果的原因是什麼呢？可以看到，這張桌子在預處理切塊(左圖)的時候就已經被切分成幾個小的點雲塊，而後再分別不相關地地輸入到網絡中。也就是說，在點雲目標幾何結構已經被切塊所破壞的前提下，網絡是難以有效地學習到桌子的整體幾何結構的。
既然切塊太小會導致整幾何結構被破壞，那我能不能把塊切大一點？這樣不就可以在一定程度上更好地保留原始點雲的信息了嗎？
圖 2. PointNet和PointNet++在S3DIS Area5的對比實驗結果。S3DIS中的數據分別被切割為1m×1m到5m×5m的點雲塊，然後再輸入到網絡中進行訓練和測試。
對此，我們也進一步設計了對比實驗，把切塊的尺寸從最初的1m×1m增加到5m×5m(每個block中的點數也相應地從4096增加至102400)，得到的實驗結果如上圖所示，可以看到：
PointNet的mIoU結果出現了比較明顯的下降。我們分析這主要是由於在PointNet框架中，每個點的特徵是由shared MLP提取的per-point feature以及global max-pooling提取的global feature組成。當輸入點雲的規模越來越大時，通過簡單的global max-pooling得到的全局特徵能發揮的作用就越來越小，進而導致分割性能隨著block size增大而持續地下降PointNet++的分割性能隨著block_size的增大有了一定提升，這是符合我們預期的。然而，從右邊的時間變化曲線我們也可以進一步看到，網絡inference的時間也隨著block_size增大而出現了顯著的增長，從最開始的每3s/百萬點增加到需要接近100s/百萬點。上述實驗結果表明：簡單地增大block_size也並不能有效地解決這個問題。通過進一步分析我們發現，阻礙當前大多數方法直接處理大場景點雲的原因主要有以下三點：
網絡的降採樣策略。現有的大多數算法採用的降採樣策略要麼計算代價比較昂貴，要麼內存佔用大。比如說，目前廣泛採用的最遠點採樣(farthest-point sampling)需要花費超過200秒的時間來將100萬個點組成的點雲降採樣到原始規模的10%。許多方法的特徵學習模塊依賴於計算代價高的kernelisation或graph construction。現有大多數方法在提取特徵時感受野(receptive fields)比較有限，難以高效準確地學習到大場景點雲中複雜的幾何結構信息當然，最近也有一些工作已經開始嘗試去直接處理大規模點雲。比如說SPG用超圖(super graph)和超點(superpoints)來表徵大場景點雲，FCPN和PCT等方法結合了voxel和point的優勢來處理大規模點雲。儘管這些方法也達到了不錯的分割效果，但大多數方法的預處理計算量太大或內存佔用高，難以在實際應用中部署。
本文的目標是設計一種輕量級，計算效率高(computationally-efficient)、內存佔用少(memory-efficient)的網絡結構，並且能夠直接處理大規模3D點雲，而不需要諸如voxelization/block partition/graph construction等預處理/後處理操作。然而，這個任務非常具有挑戰性，因為這種網絡結構需要:
一種內存和計算效率高的採樣方法，以實現對大規模點雲持續地降採樣，確保網絡能夠適應當前GPU內存及計算能力的限制；一種有效的局部特徵學習模塊，通過逐步增加每個點的感受野的方式來學習和感知複雜的幾何空間結構。基於這樣的目標，我們提出了一種基於簡單高效的隨機降採樣和局部特徵聚合的網絡結構(RandLA-Net)。該方法不僅在諸如Semantic3D和SemanticKITTI等大場景點雲分割數據集上取得了非常好的效果，並且具有非常高的效率(e.g. 比基於圖的方法SPG快了接近200倍)。本文的主要貢獻包括以下三點：
我們對現有的降採樣方法進行了分析和比較，認為隨機降採樣是一種適合大規模點雲高效學習的方法我們提出一種有效的局部特徵聚合模塊，通過逐步增加每個點的感受野來更好地學習和保留大場景點雲中複雜的幾何結構RandLA-Net在多個大場景點雲的數據集上都展現出了非常好的效果以及非常優異的內存效率以及計算效率隨機採樣&局部特徵聚合模塊組合，組建RandLA-Net
Overview
如下圖所示，對於一個覆蓋數百米範圍、由百萬量級的點組成的大場景點雲而言，如果希望將其直接輸入到深度神經網絡中進行處理，那麼持續有效地對點雲進行逐步地降採樣，同時儘可能地保留有用的幾何結構信息是非常有必要的。
圖 3. 網絡結構的大致流程圖
The quest for efficient sampling
為了尋找到一種高效的降採樣方法。我們首先對現有的的降採樣方法進行研究：主要可以分為Heuristic Sampling以及Learning-based Sampling兩大類：
(1) Heuristic Sampling
Farthest Point Sampling (FPS)：顧名思義，也就是每次採樣的時候都選擇離之前採樣得到的 k-1個點距離最遠的點。FPS能夠比較好地保證採樣後的點具有較好的覆蓋率，因而在點雲分割領域被廣泛地使用(e.g., PointNet++, PointCNN, PointConv, PointWeb)。然而，FPS的計算複雜度是 ，計算量與輸入點雲的點數呈平方相關。這表明從FPS可能不適合用來處理大規模點雲。舉例來說，當輸入一個具有百萬量級點的大場景點雲時，使用FPS將其降採樣到原始規模的10%需要多達200秒。Inverse Density Importance Sampling (IDIS): 這個也比較好理解，簡而言之就是根據每個點的密度來對其重新進行排序，儘可能地保留密度比較低的地方的點。IDIS [5] 的計算複雜度近似為 (取決於如何計算每個點的密度)。相比於FPS, IDIS顯然更加高效，但IDIS對噪點(outliers)也更加敏感。Random Sampling (RS): 隨機降採樣均勻地從輸入的 N 個點中選擇 K 個點，每個點具有相同的被選中的概率。RS的計算複雜度為 , 其計算量與輸入點雲的總點數無關，只與降採樣後的點數 K 有關，也即常數時間複雜度。因而具有非常高的效率以及良好的可擴展性。與FPS和IDIS相比，RS僅需0.004s即可完成與FPS相同的降採樣任務。(2) Learning-based Sampling
Generator-based Sampling (GS)：與傳統降採樣方法不一樣，這類方法通過學習生成一個子集來近似表徵原始的點雲。GS [6,7] 是一種task-oriented, data-driven的learnable的降採樣方法，但問題在於inference階段需要將生成的子集與原始點雲進行匹配，這一步依賴於FPS matching，進而引入了更多額外的計算。使用GS將百萬量級點的大場景點雲降採樣到原始規模的10%需要多達1200秒。Continuous Relaxation based Sampling (CRS): CRS [8,9] 使用reparameterization trick來將non-differentiable的降採樣操作鬆弛(relax)到連續域使得端到端訓練變成可能。CRS採樣後得到的每個採樣點其實都是整個點雲的一個加權和(weighted sum)。具體來說，對於一個大場景的輸入點雲(size: N×3)，CRS通過學習得到一個採樣矩陣 (size: K × N) (最終會非常稀疏), 最後採樣矩陣左乘輸入點雲即可實現降採樣。然而，當 N 是一個非常大的值時(e.g. 10^6), 這種方式學習到的採樣矩陣會帶來非常大的內存消耗。舉例來說，使用CRS將百萬量級點的大場景點雲降採樣到原始規模的10%需要多達300GB的GPU內存。Policy Gradient based Sampling (PGS): PGS [10] 將降採樣操作表示為一個馬爾科夫決策過程，旨在學習到一種有效的降採樣策略。該方法序貫地對每一個點學習到一個概率來決定是否保留。然而，當輸入是大場景點雲時，整個網絡有著極大的搜索空間(exploration space)。舉例來說，完成與上述採樣方法相同的任務的搜索空間是 。通過進一步地實驗我們發現，將PGS應用到大型點雲時，網絡非常難以收斂。總結一下：
對於大場景點雲，FPS, IDIS和GS的計算代價都比較高， CRS對GPU內存的要求太高，而PGS難以學到一個有效的採樣策略(sampling policy)。相比之下，隨機採樣具有以下兩個優點：1)計算效率高, 因為是常數計算複雜度, 與輸入點數無關 2)內存開銷少，採樣過程並不需要額外的內存消耗。因此，對於大場景點雲作為輸入的情況，我們何不嘗試下隨機降採樣呢？
但新的問題又來了：隨機地對點雲進行降採樣勢必會導致有用的信息被丟失，如何克服這個問題？
Local Feature Aggregation
為了緩解這個問題，我們進一步提出了與隨機採樣互補的局部特徵聚合模塊(Local feature aggregation)。如圖所示，該模塊主要包括三個子模塊:1)局部空間編碼(LocSE), 2) attentive pooling, 3)擴張殘差塊(dilated residual block)。
圖 4. 局部特徵聚合模塊。包括局部空間編碼(Local Spatial Encoding)，Attentive Pooling以及Dilated Residual Block三個子模塊。
(1) 局部空間編碼(Local Spatial Encoding)
此模塊用於顯式地對輸入的點雲的三維坐標信息進行編碼。不同於直接將各個點的三維坐標作為一個普通的通道特徵輸入到網絡中，LocSE模塊旨在顯式地去編碼三維點雲的空間幾何形狀信息，從而使得網絡能夠從各個點的相對位置以及距離信息中更好地學習到空間的幾何結構。具體來說分為以下步驟：
首先，我們用 最近鄰搜索算法為每一個點 找到歐氏空間中最近的個鄰域點對於 的個最近鄰點 , 我們顯式地對點的相對位置進行編碼，將中心點的三維坐標 , 鄰域點的三維坐標 , 相對坐標 以及歐式距離 連接(concatenation)到一起。如下所示：最後我們將鄰域點 對應的點特徵 與編碼後的相對點位置 連接到一起，得到新的點特徵 。在Semantic3D，S3DIS以及SemanticKITTI等多個數據集上實驗：優勢明顯
Experiments
(1) Efficiency of Random Sampling
首先我們對上述提到的採樣策略進行評估，主要從計算時間和GPU內存消耗兩個方面來考量。具體來說，我們進行如下的實驗：仿照PointNet++的主體框架，我們持續地對點雲進行降採樣，總共五次降採樣，每次採樣僅保留原始點雲中25%的點。實驗結果如下圖所示，可以看出：
對於小規模的點雲~10^3, 上述採樣方法在計算時間和內存消耗的差距並不明顯, 總體來說都是可接受的對於大規模點雲~10^6, FPS/IDIS/GS所需要的計算時間顯著增加, 而CRS需要佔用大量的GPU內存(圖b虛線)。相比之下，RS在計算時間和內存消耗方面都有著顯著的優勢，因此非常適合處理大規模點雲。這個結果也進一步說明了為什麼大多數算法選擇在小規模點雲上進行處理和優化，主要是因為它們依賴於昂貴的採樣方法。
圖 7. 不同採樣方法的時間和內存消耗。虛線表示由於GPU內存有限而產生的估計值
(2) Efficiency of RandLA-Net
我們進一步對RandLA-Net在處理真實場景中的大規模三維點雲的效率進行評估。具體來說，我們選擇在SemanticKITTI數據集的驗證集(序列8：一共4071幀)進行對比測試。主要評估以下三個方面的指標：總時間，模型參數以及網絡最多可處理點數。公平起見，我們在每一幀中將相同數量的點(81920)輸入到baseline以及我們RandLA-Net中。實驗結果如下表所示，可以看出：
表1. 不同方法在處理SemanticKITTI數據集的序列8的總時間、模型參數和最多可處理點數對比。
SPG[23]的模型參數最少，但耗時最長。主要原因是幾何劃分(geometrical partitioning)和超圖構建(super-graph construction)等步驟的計算代價較高；PointNet++和PointCNN的耗時也很長，主要原因是FPS在處理大場景點雲時比較耗時PointNet和KPConv無法一次性處理非常大規模的點雲 ，主要原因是沒有降採樣操作(PointNet)或者模型較為複雜。得益於簡單的隨機採樣以及基於MLP的高效的局部特徵聚合模塊，RandLA-Net的耗時最少(~23幀/每秒)，並且能夠一次處理總數高達10^6的點雲。(3) 公共數據集評估結果
Semantic3D由30個大規模的戶外場景點雲組成，包含真實三維空間中160×240×30米的場景，總量高達40億個點。其中每個點包含3D坐標、RGB信息以及強度信息。RandLA-Net只用了三維坐標以及對應的顏色信息進行處理。從表中可以看出我們的方法達到了非常好的效果，相比於SPG, KPConv等方法都有較明顯的提升。
表 2. 不同方法對Semantic3D (reduced-8)的定量結果對比
SemanticKITTI數據集由21個序列, 43552幀點雲組成。每一幀的點雲由~10^5個點組成，包含真實三維空間中160×160×20 米的場景。我們按照官方的train-validation-test進行分類，其中序列00~07以及09~10(19130幀)作為訓練集，序列08(4071幀)作為驗證集，序列11~21(20351幀)用於在線測試。需要注意的是，這個數據集中的點雲僅包含各個點的三維坐標，而沒有相應的顏色信息。實驗結果如下表所示，可以看出：RandLA-Net相比於基於點的方法(表格上半部分)有著顯著的提升，同時也優於大部分基於投影的方法，並且在模型參數方面相比於DarKNet53Seg等有著比較明顯的優勢。
表 3. 不同方法對SemanticKITTI數據集的定量結果對比
S3DIS數據集由6個區域的271個房間組成。每個點雲包含真實三維空間中20×15×5米的室內場景。6-fold的交叉驗證實驗結果也進一步證實了我們方法的有效性。
表4. 不同方法對S3DIS數據集的定量結果對比
在Ablation study中，我們也進一步證實了各個子模塊對整體性能的貢獻。詳細的分析見paper以及supplementary。
表 5. Ablation study結果對比
最後總結一下，我們提出了一種針對大規模三維點雲場景的輕量級、高效點雲語義分割算法，與當前的大多數基於FPS等計算代價高的採樣策略的算法不同，本文嘗試使用簡單高效的隨機採樣來顯著地減少計算量以及內存消耗，並且引入了局部特徵聚合模塊持續地增大每個點有效的感受野，以確保大多數有效的信息不會因為隨機採樣而丟失。在Semantic3D，S3DIS以及SemanticKITTI等多個數據集上的大量實驗證明了我們的方法的有效性。下一步可以嘗試將我們的工作延申到大場景三維點雲實例分割以及實時動態點雲處理。
最後的話
對於三維點雲語義分割任務而言，與其在被切割的點雲上提出非常複雜的算法來提升性能，不如直接嘗試在大場景點雲上進行處理，這樣更加有實際意義。三維點雲分割網絡的scalability也是實際應用中一個比較重要的點。i.e., 理想情況下train好的網絡應該可以用於inference任意點數的輸入點雲，因為每個時刻採集到的點雲的點數不一定是相同的。這也是RandLA-Net沒有使用全局特徵的原因，i.e. 確保學到的參數是agnostic to number of points.順便打一波廣告，對於剛剛進入三維點雲處理領域的同學，有一份最新的綜述論文(Deep Learning for 3D Point Clouds: A Survey)可供參考，內含大量主流的點雲目標分類，三維目標檢測，三位場景分割算法的最新研究進展及總結。牛津大學出品，作者團隊介紹
論文合著者包括牛津大學博士生胡慶擁，楊波，謝林海，王智華；博士後Stefano Rosa；國防科技大學副教授郭玉蘭；以及牛津大學教授Niki Trigoni和Andrew Markham。
胡慶擁
楊波
其中論文一作胡慶擁研究方向是3D視覺和機器學習，專注於大規模3D點雲分割和理解，動態點雲處理和跟蹤。論文二作(通訊作者)楊波專注於讓智能機器從2D圖片或3D點雲中理解和重構完整3D場景。更多信息見個人主頁:
https://qingyonghu.github.io
https://yang7879.github.io
Reference
[1] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. PointNet: Deep learning on point sets for 3D classification and segmentation. CVPR, 2017.
[2] Charles R Qi, Li Yi, Hao Su, and Leonidas J Guibas. PointNet++: Deep hierarchical feature learning on point sets in a metric space. NeurIPS, 2017
[3] Yangyan Li, Rui Bu, Mingchao Sun, Wei Wu, Xinhan Di, and Baoquan Chen. PointCNN: Convolution on X-transformed points. NeurIPS, 2018.
[4] Wenxuan Wu, Zhongang Qi, and Li Fuxin. PointConv: Deep convolutional networks on 3D point clouds. CVPR, 2018.
[5] Fabian Groh, Patrick Wieschollek, and Hendrik P. A. Lensch.Flex-convolution (million-scale point-cloud learning beyond grid-worlds). ACCV, 2018
[6] Oren Dovrat, Itai Lang, and Shai Avidan. Learning to sample. CVPR, 2019.
[7] Itai Lang, Asaf Manor, and Shai Avidan. SampleNet: Differentiable Point Cloud Sampling. arXiv preprint arXiv:1912.03663 (2019).
[8] Abubakar Abid, Muhammad Fatih Balin, and James Zou. Concrete autoencoders for differentiable feature selection and reconstruction. ICML, 2019
[9] Jiancheng Yang, Qiang Zhang, Bingbing Ni, Linguo Li, Jinxian Liu, Mengdie Zhou, and Qi Tian. Modeling point clouds with self-attention and Gumbel subset sampling. CVPR, 2019.
[10] Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. ICML, 2015
[11] Hugues Thomas, Charles R Qi, Jean-Emmanuel Deschaud, Beatriz Marcotegui, Franc ois Goulette, and Leonidas J Guibas. Kpconv: Flexible and deformable convolution for point clouds. ICCV, 2019.