點雲分割一直是點雲研究領域一個很重要的分支，它在SLAM、自動駕駛、機器人等領域都有著重要的應用。點雲相比於2D影像，其有著更豐富的3D空間資訊，對物體的表面描述也更接近實際。然而，點雲的無序的特點以及缺乏直觀的拓撲結構，以及大場景下的爆炸般的點雲數據量，一直是點雲的核心問題。點雲的特徵表示、數據處理、演算法結構都是研究的熱門方向。深度學習已經在2D影像領域遍地開花，而在點雲領域，尤其是點雲分割領域，還有著很長的路要走。

MASK RCNN在2D影像分割領域算是一個非常有突破性的工作，在圖片或者影片的每一幀上，車、人等物體，都被精確的分割出來。然而這一切都是在2D上做的，2D照片本身是缺乏3D資訊的，我們不能知道照片中的人究竟距離我們有多遠，而這便限制了電腦去和這個世界的理解和交互。我們希望有更理想的電腦或者說機器人，能夠更像人一樣去和所見的東西，進行理解和交互，比如機器人的抓取，自動駕駛的感知，實時地圖構建，以及室內機器人導航，而這些工作，3D資訊將成為十分重要的輸入數據。

3D資訊在電腦中一般有以下幾種表示：

點雲的很大的應用優勢就是，可以實時被感測器測量出來、可以很緊湊的表示一個大規模場景的3D資訊、可以非常好的表示物體的3D形狀資訊，對光照等外界因素並不敏感（因為是主動式的發射反射光資訊，2D只是接受其它光源的反射光）。

當然，點雲也有其不好處理的一面。點雲是不規則的、不均勻的、無序的。雖然有這些缺點，但是其巨大的優點，讓研究者們不斷去想盡辦法，尋找足夠好的演算法，去更好的處理點雲。

點雲處理可以分為傳統方法和深度學習的方法，深度學習方法中又分為非點雲輸入和直接點雲輸入。前者將點雲先處理成如多角度圖片集或者體素網格等，後者則直接把點雲以原始的點集直接輸入處理。作者提到了一篇19年的點雲深度學習領域的survey: Deep Learning for 3D Point Clouds: A Survey(鏈接://arxiv.org/abs/1912.12033)，這是一篇非常好的survey，把點雲分類、檢測、分割幾個領域，詳細介紹了一遍，並且相關貢獻都以時間軸進行展示，推薦大家閱讀。

作者挑選了兩套處理點雲的方法：Voxel-based 和 Point-based。

PointNet和PointNet++是Point-based領域開拓性的工作，PointNet直接輸入點集，然後使用共享多層感知機及最大池化函數來提取逐點及全局特徵並同時確保點雲特徵的置換不變性。PointNet++相比於PointNet，增加了層次的局部特徵提取，相比於PointNet直接通過max-pooling得到的全局特徵有更好的效果。這兩篇文章是直接在點雲上進行處理的演算法的基礎，後續又有許多跟進的工作，進一步提升了分類識別及分割的效果。

如果你看過點雲相關的程式碼，你會發現大部分點雲方法都是在一個塊上進行操作的。比方說一間房子的點雲，20m×20m，裡面的點非常多，所以一般會在俯視視角上，切一個比如1m×1m×H的長方體，在這個長方體內做操作，而且這個長方體內的點雲也是非常多的，所以還要再做一個取樣，比如取樣4096個點。那麼這種切塊操作帶來的問題就顯而易見了，一個桌子切成兩半，然後在各自的塊內做分割，這就缺少了一種整體的特徵。因此，大場景下的點雲處理很有必要，也很有挑戰。如下圖，一個桌子在不同塊裡面被預測成不同的類別。

作者先簡單介紹了兩篇前人的工作，PointCNN和KPConv，這兩篇論文並不是做大場景的，但是它們提出的想法是基礎性的，就是自定義卷積，通過自定義的卷積在點雲上進行操作，可以提取更好的特徵。

在大場景領域，作者也簡單提了兩篇工作，SPG和FCPN。SPG為整個場景的點雲構建了一個超點圖，邊資訊表徵了點雲內在的關聯，然後在graph上進行操作。FCPN是結合了point-based和voxel-based，將無規則的點雲，轉換為內部有序的數據結構，然後再使用3D卷積進行處理。作者提到之前做大場景的工作，處理起來都非常耗時，因此RandLA-Net工作motivation便有了。

那現有的方法，比如pointnet和pointnet++能直接遷移到大場景領域嗎？作者做了相關實驗，首先pointnet是直接用max pooling來取得全局特徵，局部特徵的提取是缺失的。隨著切塊的塊越來越大，直接max pooling，必然會損失很多資訊，因此pointnet的性能會越來越低。那結合了局部特徵的pointnet++呢？通過實驗，我們發現隨著塊的變大，性能也在變好。然而耗時也越來越嚴重，因為pointnet++中使用的點集的降取樣演算法，是和點數的二次方成正比的，塊越大，點數越多，速度越慢。

那麼大場景點雲語義分割領域的難點在哪？作者提了三點，首先是整體的點雲相比於一個小塊的點雲的結構要複雜很多；其次是點數的增多勢必會帶來GPU顯示記憶體的上升；最後是感測器採集到的點雲數是非固定的，之前都是切塊後再采固定數量的點。

作者希望能找到一個符合以下三點的大場景處理方法：1)不用切塊，直接全局輸入；2)計算複雜度和顯示記憶體佔用要低；3)還要保證精度和能夠自適應輸入點數。

對於大場景的點雲，如何直接處理呢？一個核心的步驟就是降取樣。作者認為我們需要一個更有效的降取樣演算法，來保留點雲的key points。同時還希望能夠有一種更好的局部特徵提取和聚合的演算法來學到局部特徵。

首先是降取樣。

作者先對現有的點雲降取樣技術做了總結，大範圍可以分為兩類：Heuristic Sampling(啟發式的)、Learning-based Sampling(可學習的)。

對於啟發式的降取樣：

• Farthest Point Sampling(FPS)：這是一種在點雲領域被廣泛使用的降取樣方法，如PointNet系列。每次取樣都去離采上一個點最遠的點，迭代進行，這樣可以把一些邊邊角角的點都能找到，但是演算法計算複雜度O(N^2)；

• Inverse Density Importance Sampling (IDIS)：先對每個點的密度進行排序，然後密集的部分多取樣，稀疏的部分儘可能都保留。然而這種演算法會容易受到雜訊的影響，計算複雜度O(N)；

• Random Sampling (RS)：隨機取樣，計算複雜度為O(1)，與輸入點數無關，當然可能會丟掉一些重要的點

對於可學習的降取樣：

• Generator-based Sampling (GS)：演算法通過學習來生成一個點雲子集來實現降取樣。這是很新穎的方法，然而這種方法可能比FPS方法的複雜度更高；

• Continuous Relaxation based Sampling (CRS)：通過學習一個矩陣，類似與實現一個全連接網路，然後和輸入點雲相乘得到輸出的低維點雲空間。然而當輸入點數非常大的時候，矩陣需要的顯示記憶體也將非常大；

• Policy Gradient based Sampling (PGS)：使用一個馬爾科夫決策來對每一個點進行決策，決定其是否被保留。當輸入點數很多的時候，其決策過程非常緩慢，搜索空間非常大，而且很容易不收斂。

通過以上的對比，最後作者認為也許隨機取樣才是最適合大場景的點雲分割任務的。然而，隨機取樣很容易去丟掉那些重要的點，我們該如何解決這個問題呢？作者提出了Local Feature Aggregation。這個Local Feature Aggregation主要包括三個子模組，分別是LocSE、Attentive Pooling、Dilated Residual Block。

該模組希望從輸入點雲里得到一個局部空間特徵。步驟是先對於每一個點進行K近鄰，找到它的鄰域點集；然後將中心點的坐標、鄰域點的坐標、鄰域點和中心點的相對坐標和鄰域點和中心點的歐式距離連在一起；再過一個MLP，和鄰域點的特徵在連在一起，得到最終輸出。

將上面提取到的特徵聚合在一起，PointNet系列一般都是直接一個Max Pooling，實現特徵聚合。作者認為Max Pooling有些粗暴，容易丟掉一些重要的資訊。作者使用Attention機制，在SeNet工作中提到過，學習一個MASK，來作為每個特徵的權值，然後加權，再過一個MLP，實現聚合。

隨機降取樣不可避免會丟掉一些重要的點，如何解決這個問題，作者認為如果每個點的感受野足夠大，其能夠更好地聚合局部的特徵，而且當這種感受野足夠大時，即便有些點的特徵被隨機的丟掉了，但整個點雲的大部分資訊還是能夠被有效地保留下來。因此我們將多個LocSE和Attentive Pooling模組連在一起，組成一個大的Dilated Residual Block。這樣的話，輸入點雲通過不斷的聚合，便增大了保留下點的視野。

基於上面的方法，作者設計了一個沙漏網路的結構，即點數先降低，再增加。每一層局部特徵聚合和隨機取樣交替進行，點數下來了，每個點的視野也上去了。

通過實驗，作者發現隨機取樣方法，無論是從速度還是顯示記憶體，都是對比最優的，整體方法的效率，在大場景領域對比也是速度最快。再看精度，在Semantic3D、SemanticKITTI和S3DIS上，作者的方法也取得的非常好的效果。

實例分割和語義分割的區別是，語義分割是將每一個點進行分類，如桌子、椅子等。而實例分割不僅要分出這個點是什麼類，還要分出來不同的物體，即桌子1、桌子2、椅子1、椅子2等。

點雲的實例分割在深度學習中的發展最早的一篇工作是CVPR18的SPGN，目前一般可以分為兩類方法：Proposal-based methods和Proposal-free methods。前者是基於檢測的，即先檢測出點雲中每個物體的Bounding Box，點雲中的BBox是一個長方體，然後在每一個BBox中進行物體和背景的點的分類。後者是不基於檢測，直接通過點的特徵進行聚類。兩個方法都有優缺點。基於檢測的，往往是兩階段的，也要進行NMS，速度較慢。不基於檢測的雖然相比骨架速度較快，但是它的分割出來的物體的整體性比較差，而且需要比較麻煩的後處理，後處理主要是基於特徵空間的度量。

因此作者希望能找到一種方法，結合兩種方法的優點。即單階段、不需要檢測的錨點、端到端訓練的一種方法——3D-BoNet。

整體思想很簡單，即點雲輸入，然後特徵提取，直接吐出來一系列的BBox，這些Bbox沒有類別標籤，就是一些框框，然後再在這些Bbox里進行點的分類。

說到這裡是不是有些疑惑了，這不還是基於檢測的嗎？和基於檢測有區別嗎？我一開始也不能理解。其實要注意，這裡生成的BBox首先是沒有類別標籤的，你可以理解成，它這個過程只是完成了二階段檢測任務的第一個階段，即RPN階段，預測出一堆可能存在物體的屬於BBox，然後再在裡面進行點的分類。

先說預測BBox部分，點雲輸入，提取一個特徵，然後過幾個FC即可得到一系列的BBox，而且這種方法是預設一個K值，表示預測的BBox的個數。在實際場景中，讓K大於輸入點雲最大的實例數即可。

那得到了K個BBox之後，如何結合Groud Truth來進行監督學習呢？所以這設計到一個匹配問題。比如預測5個BBox，GT中有3個BBox，根據匹配演算法，找到預測中的3個BBox，然後去回歸這兩個BBox，抑制另外2和BBox，這樣就解決了監督學習的問題。

但是如何設計匹配演算法呢？作者設計了3個標準：

1)  預測和GT的BBox的頂點的歐氏距離：空間距離越近越好；

2)  預測和GT的BBox的IoU：重合度越高越好；

3)  預測和GT的BBox交叉熵：預測的Bbox越大越好。

然後將上面三個部分的loss加和就得到最終的loss。

實驗結果部分，提交的時候，在Scannet和S3DIS上，本演算法是最優的。在速度上，相比之前的演算法也是相對比較快的。

作者提了幾個有意義的工作，值得各位未來去探索：

點雲是一個非常有前景的研究領域，這個領域還有很多很多問題沒有解決，希望大家如果感興趣，就付諸努力，為這個領域添磚加瓦吧！