本文詳細解析三維語義分割的幾個主流方案，文末給出了對比

作者任浩帆，杭州電子科技大學智能信息處理實驗室大三學生。長江後浪推前浪啊文中含大量鏈接，因公眾號限制無法顯示，可在文末點閱讀原文查看

本文提綱：

0. 三維表示的數據結構0.1. Point cloud0.2 3D voxel grids0.3 collections of images/muti-view0.4 polygon1. PointNet1.1 提升準確度的關鍵步驟1.1.1. 解決無序性1.1.2. 解決幾何旋轉問題1.2 網路結構1.3 結果2. PointNet++2.1 網路結構2.2 自適應的特徵提取層2.2.1 MSG(Multi-scale grouping)2.2.2 MRG(Multi-resolution grouping 2.3 特徵傳播2.4 結果3. PointSIFT4. SPG4.1 geometric partition

4.2 構建SPG 4.3 得到上下文特徵

4.4 上下文分割

5. 3P-RNN 5.1 Pointwise pyramid pooling

5.2 RNN for context ensemble

6. pointwize 7. 效果比較 8. 總結

語義分割需要兩部分

  • classification: 需要全局信息
  • segmentation：更加依賴全局信息和局部信息
  • 一般的網路結構是：提特徵-特徵映射-特徵圖壓縮（降維）-全連接-分類，其實就是encoder-decoder的過程，比如在二維的的pspnet，fcn等等, 可能還有CRF去調整

0. 三維表示的數據結構

0.1. Point cloud

本質是對三維世界幾何形狀的低解析度重採樣，因此只能提供片面的幾何信息 點雲的一些feature：

1. normal 法向量
2. intensity 激光雷達的採樣的時候一種特性
強度信息的獲取是激光掃描儀接受裝置採集到的回波強度，此強度信息與目標的表面材質、粗糙度、入射角方向，以及儀器的發射能量，激光波長有關

3. local density 局部稠密度
4. local curvature 局部曲率
5. linearity, planarity and scattering propesed by [this paper]Dimension- ality based scale selection in 3D lidar point clouds
6. verticality feature proposed by Weakly supervised segmentation-aided classification of urban scenes from 3d LiDAR point clouds

  • 無序性點雲實際上是無序的，比如有8個點雲，你放到矩陣裡面，是有順序的，但是實際上打亂順序也都表示的是同樣的一個點雲。換句話說，不同的矩陣表示的是同一個點雲，而你分割的結果肯定不可能對於不同的輸入表示矩陣，結果不一樣。

如果有N個點，就需要對N！permutations invariant

解決方法：

  1. sorting

但是實際上不存在這樣一個穩定的從高緯度到1維度的映射

  1. RNN

數據的一些抖動也得到了增強

  1. symmetric function
  • 幾何旋轉性：相同的點雲在空間中經過一定的剛性變化（旋轉或平移），坐標發生變化。 不論點雲在怎樣的坐標系下呈現，網路都能正確的識別出。這個問題可以通過STN（spatial transform network）來解決。二維的可以看一下這個，實際上就是一些放射變換之類的。Point cloud rotations should not alter classification results
  • 抽密度不均勻採樣的時候，點雲的稠密度，一般是不一樣的，距離鏡頭近的物體點雲稠密度比較大，距離遠的比較稀疏。如下圖：

也有一些方法去解決這種問題，比如PU-Net: Point Cloud Upsampling Network這幾點就要求在點雲的處理過程要非常的魯棒。

  • 不規則性點雲不像grid和pixel，有很規範的格式，所以並不能直接的採用CNN，這是一個很嚴重的問題。當然也有一些提出一些直接能夠對點雲做操作的網路，Pointwise Convolutional Neural Networks Binh-Son，但是從效果看起來，似乎比pointnet要差一些，但是不是差的特別大，有些地方有略超過pointnet的地方，但是我覺得計算量。。。。。。。會很大

還有一些方式比如就是將點雲轉換成其他方式，SegCloud uses 3D con- volutions on a regular voxel grid，但是點雲轉換成volme的方法效率很低，而且這個過程丟失掉一些細節

0.2 3D voxel grids

類似二維的三維卷積，是規律化的並且易於類比二維的，但同時因為多了一個維度出來，時間和空間複雜度都非常高，目前已經不是主流的方法了；

體素的方式呢，SPG的作者認為do not capture the inherent structure of 3D point clouds

相關方法：Subvolume， voxelnet

0.3 collections of images/muti-view

這樣的好處是可以直接採用一些二維的運算元去處理，特徵被view pooling procedure聚合起來形成三維物體；常見方法MVCNN

0.4 polygon

可以運用一些mesh的表達和合適的演算法，比如三角剖分等等。

這三種數據結構是可以相互轉換的，但是貌似三維結構的表示相互轉換，時間複雜度比價高

1. PointNet

主頁 | 論文 | 補充材料 | Code | 會議報告講解論文視頻 | 作者答疑解惑 | 作者中文講解視頻 | Open3D-PointNettime：Dec 2, 2016

  • Input: coordinates(x,y,z)
  • Output: labels. added by computing normals and other local or global features

在這個網路之前其他的方式都是對三維數據表達進行轉換變成規則， 比如：

voxelization ----- 3D CNN
Projection/rendering --- 2D CNN

1.1 提升準確度的關鍵步驟

1.1.1. 解決無序性

用來解決unorder set的問題。所謂對稱函數，比如f(x1,x2) = x1 + x2, 互換x1，x2不影響結果。就是unorder set問題的一個數學表述

h:特徵提取
g是simple symmetric function
r是更高維度的特徵提取

在Fig5中，測試了三種方法，最後發現max pooling對解決無序性效果最好

可以看論文的Fig5是關於選取不同g對於結果的如何影響。以下是經過實驗論文採用的方法

1.1.2. 解決幾何旋轉問題

  • 背景我們知道對於多維空間，只要找到一個合適的旋轉矩陣和平移矩陣這兩個矩陣就可以構成一個仿射變換（齊次坐標可以將這兩個變換表示成一個矩陣），但是點雲分割是一個多分類的問題，平移對於整體的點雲分類影響不是很大，你可以理解一個向量在原點，和將平移一下，他的指向是不會變的。（形象化的展示可以看《線性代數的幾何意義》）

所以如果是點雲是這樣一個矩陣 A = N x M

N：表示點雲有N個點

M：表示點雲的feature，可以是坐標，x,y,z，這樣的話就是3列，還可以有在0.0中提到的一些其他feature，比如法向量之類的。

我們只需要一個左乘一個矩陣B = N x N 的矩陣就可以對A矩陣做旋轉變換

或者右乘一個矩陣C = M x M 的矩陣也可以對A矩陣做旋轉變換

B和C都是方陣是為了保持變換之後我們的點雲矩陣A維度不變，不損失信息。區別僅僅在於B是對矩陣的行空間做變換，C是對列空間做變換。

按照之前的說法，點雲的無序性就是行空間不一樣，具體的說就是矩陣A第i行和第j行互換，但是表示的點雲是一樣的。所以對於A左乘B做行空間的變換沒有意義。所以我們如果要旋轉的話要用矩陣C對列空間進行變換，而我們知道最後分類是通過點雲列空間上那個class的值最大去判斷輸入哪一個類別的。所以列空間的變換是真正有意義的

這篇論文用了一個網路T-net去兩次擬合這個矩陣C

  • 原生輸入變換這裡做轉換的原因應該是為了讓網路在做初步的特徵提取前的，一個預處理

  • 特徵轉換（Embedding Space Alignment）根據網路的整個pipeline，這裡是為了在較低特徵維度的層面上經過一個類似activation function的作用，找到一個合適的超平面，讓網路之後能夠學習到更好的特徵。類似二維的這裡

此外在這裡，還加入了一個正則約束項：

這個正則項的意思是使得那個旋轉矩陣要儘可能接近於一個正交矩陣。論文裡面說，因為在特徵空間裡面的轉換矩陣的維度要遠遠比原生空間裡面的轉換矩陣維度高很多，具體就是64*64 > 3*3。因為緯度高所以優化的難度大，所以加入了這個正則項。（A is the feature alignment matrix predicted by a mini-network. An orthogonal transformation will not lose information in the input, thus is desired）

  • 思考我覺得實際上有些奇怪，我們知道旋轉矩陣本身就是正交矩陣是為了保持旋轉前後模長不變，那為什麼之前那個變換沒有加這個正則呢？可能作者做過時間，對效果可能沒影響，或者影響不大，反而增加了時間複雜度。

但是這個正則項的影響，在論文中的Robustness test測試的時候是準確度提高了0.5% 其他的兩個變換，加和沒加對準確度的影響如下：

可見想法很好，但是提高並不是非常明顯。但是論文作者覺得加入了正則項之後（We find that by adding the regularization term, the optimization becomes more stable and our model achieves better performance）

1.2 網路結構

我記得之前看到，kolmogorov理論指出，了對於分類問題，理論上只要兩層hiddenlayer的mlp就足以解決任意複雜的分類問題

輸出兩個score，一個只是簡單的分類，另一個score是將類別具體做確定，確定具體屬於哪一類

1.3 結果

時間複雜度：0(N)，N是點雲個數處理速度經驗估計大概：每秒100萬個點用1080x GPU，這個速度相當的快point cloud classifica- tion (around 1K objects/second) or semantic segmentation (around 2 rooms/second)

不足：分割的時候並沒有加入足夠多的局部信息。

2. PointNet++

上海交大的工作。核心貢獻就是提出了一個3d-sift的submodel，文章里有很詳細的運算元說明，這裡就不多做介紹了。

主頁 | 論文 | code | Open3D-PointNet2-Semantic3Dtime：Jun 7, 2017

Pointnet++是在pointnet基礎上改進的。解決了pointnet在局部特徵上提取的不足。我們先來看一下效果

2.1 網路結構

在set abstraction階段，不斷的進行上採樣，學習局部特徵。將原始的點雲在一個領域的範圍內，採集成質心。之後分classification比較常規。segmentation其實就是decoder部分，通過插值的方法得到原始的每一個點雲的feature vector，而不是只有質心的feature vector。

論文中的特徵提取大部分使用poinenet去做的。poinet（vanilla）就相當於point++的一層

  • 網路的輸入和輸出：input: ,N points withe d-dim coordinates and C-dim point featureoutput:
  • Sampling layer -- defines the centroids of local regions
    • input:
    • output: 這裡因為是局部區域的質心，所以N『就代表了N』個局部區域的N『個質心
    • innovation1.在質心數量相同的情況下，用FPS去採樣，比隨機採樣能夠更好的覆蓋整個點集2.和CNN去掃描向量空間的數據空間分布來講， FPS產生的感受野是相對獨立，因為是最遠點。
  • Grouping layer -- constructs local region sets by finding 「neighboring」 points around the centroids
    • CNN, 每個降採樣的像素點都是有臨近的像素，構成的，所以決定點的領域取決於你的metric　distance
    • Ball query可以通過設置一個上線，找到鄰域內的所有點
    • KNN找到鄰域內的固定數量的點．
    • Compared with kNN, ball query』s local neighborhood guarantees a fixed region scale thus making local region feature more generalizable across space, which is preferred for tasks requiring local pattern recognition (e.g. semantic point labeling).
    • input: ，
    • output: groups of point with size of
    • each group corresponds to a local region
    • K is the number of points in the neighborhood of centroid points
    • K varies across groups but the succeeding PointNet layer is able to convert flexible number of points into a fixed length local region feature vector.
    • Approaches for grouping
  • PointNet layer -- encode local region patterns into feature vectors.
    • input:
    • output:

再輸入pointnet之前，我們先要先要把局部區域的坐標做一個線性變換,so that we can capture point-to-point realations in the local region

2.2 自適應的特徵提取層

為了解決點雲抽密度不均勻的問題

2.2.1 MSG(Multi-scale grouping)

質心：一個局部領域裡面的所謂中心位置的點，就是把N個點坐標加起來除以N。

對於每一個質心，通過學習多尺度的特徵，能更好的學習fine-grained patterns。在訓練的過程當中，隨機的丟棄掉了一些點。所以就能讓網路對不同的稠密度有魯棒性但是這樣的計算量是比較大的，對於每一個質心，都需要去遍歷。

2.2.2 MRG(Multi-resolution grouping (MRG)

假設concat下面的vector左邊的那個是層經過特徵提取的，右邊是層經過pointnet得到的的。表示的是質點，層表示的是沒有經過上採樣的點。如果說點雲本身比較稀疏的話，那麼左邊的特徵提取意義不大，因為如果本身稀疏的話，那麼你上採樣之後就會變得更加稀疏。所以對原生的特徵提取更加意義。反之亦然。

點雲稀疏的時候，後邊的權重增加，左邊的權重減小。點雲稠密的時候，後邊的權重減小，左邊的權重增加。

2.3 特徵傳播

因為我們提取到的是質點的一些特徵，我們在這個過程中隨機丟掉了一些點。所以我們要想辦法去得到每一個點的特徵。一個方法就是把每一個點當成質心，這。。。你懂得。所以我們採用差值的方法去和我們上採樣質心之前的層去比較，讓二者儘可能近似。論文選用的插值方法是：inverse distance weighted average based on k nearest neighbors

最後連接特徵的時候用了unit pointnet，作用類似與1*1卷積

2.4 結果

可以看到論文在一些benchmark上的準確度提升不會特別高。但是在稀疏點的分類上，效果非常魯棒。

3. PointSIFT

主頁 | 論文 | codeJul 2, 2018

在SA步驟，不使用pointnet++的方式，也能夠去抓取更好的點。

在平面sift的情況，檢測到一個極值點之後16*16，分成4份，總計每個像素的梯度方向，合成一個組。

類似的就是將每一個點周圍分成八個子領域，實現方向性，尺度的話，就是多次疊加人這個層。

其他的一些網路，再降採樣的過程中丟失了更多的點，而Pointsitft可以抓取更多有效的點。

4. SPG

論文 | codeMar 28, 2018

這篇論文採用的是無監督的方式去做的，當然也用到了PointNet。但是採用超點了廣義最小割的方法去解決這個問題，想法可以說是非常好的一種方式。

superpoint graph<font color=red>這種表達方式非常好，只有可以研究一下這篇文章的先驗文章，related work 之後再重新看一下</red>

SPG一種能很好的表示點雲的組織形式的結構，能很好的表達圖像的上下文關係。通常的場景的點雲有百萬級別個點，但是用SPG可以在保持豐富特徵的前提下，降採樣到幾百個點，這樣就可以用一些pointnet之類的去處理。

SPG本質就是一種廣義的有權有向圖。節點表示一些簡單的形狀，邊描述了豐富的邊緣特徵來表述的鄰接關係。（Its nodes represent simple shapes while edges describe their adjacency relationship characterized by rich edge features.）

整體流程

文章的基本想法是是先對原始的點雲做幾何分割，這樣就可以得到superpoints，這個過程是一個無監督的過程，效率是很快的。之後可以很簡單的有幾何分割後的結果計算得到SPG，這個時候點雲的量級已經從幾百萬個變成了幾百個，得到SPG之後就可以輸入到一些contextual segmentation的方法中，文章中採用的是Pointnet去處理，但是還加入了GRU去做微調

4.1 geometric partition

這一步得到的應該是superpoints，這一步你可以理解成一個局部的聚類，但是並不在意能不能檢索到物體，實際上相反，是將物體拆分成一些簡單的幾何形狀，每一個幾何形狀實際上就代表一個superpoint，或者說是semantically homogeneous 看一下這張圖片就明白了：

這一步的理想情況是每一個superpoint都沒有包含的不同類別的物體，至少是一類物體的某個局部。具體的說就是要是椅子的腿，就不能有屬於桌子的點。多分幾個superpoint沒關係，但是分出來的superpoint裡面的raw points就得是semantically homogeneous。

根據結果來看，貌似是可以適應的去確定一個superpoint中的raw points的多少，也就是一個局部的聚類。Another advantage is that the segmentation is adaptive to the local geometric complexity.In other words, the segments obtained can be large simple shapes such as roads or walls, as well as much smaller com-ponents such as parts of a car or a chair。

文章是借用了【Weakly Supervised Segmentation-Aided Classification of Urban Scenes from 3d LIDAR Point Clouds】裡面的能量函數去做的

the global energy:

: the point s features: linearity, planarity, scattering, verticality,normal: 點pi和點pj，linearly decreasing with respect to the edge length：正則化強度

4.2 構建SPG（superpoints graph）

數學表達：S: superpoints: adjacency bwtween superpoints referred to as superedges: superedge 的feature，具體文章中這個feature用了很多，見Table1

4.3 得到上下文特徵(contextual info)

首先先得到每一個superpoints的descriptor，通過embedding到一個固定維度的向量當中，每一個superpoints的嵌入都是孤立的。

我們只使用graph convolution去得到contextual info。在動態降採樣大np=128的點，少於np的superpoints將會被代替，實際上由於maxpool的影響，是沒關係的，但是實際過程中very small superpoints of less than nminp = 40 points in training harms the overall performance。

輸入pointnet之前：normalized position、 observations oi、 geometric features fi輸出pointnet之後：the original metric diameter of the superpoint is concatenated to stay covariant with shape sizes.

4.4 上下文分割

終於到了最後一步，這裡就是最後一步，分類的問題。

分類的對象是：用向量表示的抄點，和他在SPG中的local surroundings。這一步用了兩個很重要的graph convolution：

  1. Gated Graph Neural Networks2016
  2. Edge-Conditioned Convolutions (ECC)2017

5. 3P-RNN

論文Pointnet使用mlp去對每一個點單獨的產生local feature，之後通過symmetric max pooling去產生global feature， which is invariant against the permutations of points。但是有兩個缺點：

  • failing to capture local structures represented by neighboring points
  • a point cloud is first subdivided into small volumetric blocks and each block is predicted independently without any connection

5.1 Pointwise Pyramid pooling

在pointnet，當中

f是MLP提取到的高級特徵。ki denotes one-stride pooling window size。相比於pointnet來講，這樣做的好處是通過one-stride pooling，可以產生和輸入點同樣大小的vector，就是輸入是輸出是：，這樣很顯然抓取到了更好的local feature

5.2 RNN for context ensemble

6. pointwize

論文 | code29 Mar 2018

效果和pointnet相比總體來講略差，而且時間複雜度很高。看了一些結果semanticfusion的準確度在floor和table的準確度相對來講要高一些。

卷積運算元：

網路結果：

7. 效果比較

S3DIS為例子：

MethodOAmIoUPointNet-----2 Dec 2016.V178.6247.713P-RNN------September 201886.956.4SPGraph-----27 Nov 2017.v185.562.1PointSIFT-----------2 Jul 2018.Submitted88.7270.23Pointwise56.581.5

8. 總結

總結一下，直接對三維信息做語義分割，有一些方法，本文對點雲的處理做了一些總結，可以看到基本上都是對pointnet做的一系列的改進。改進的方向基本在於如何更好的得到局部的信息。但是算力仍然是一個嚴峻的問題，要想達到實時的效果，只依靠演算法的改進恐怕很難，而且點雲的這種表達方式，有著兩個致命的缺點：一是雜訊無法避免，二是數據量過於龐大。18-19年有一些點雲分割相關的工作，但是似乎並沒有一些很好的解決這些問題，還是在pointnet之後順延的一些想法。值得注意的是18年ECCV有一篇depth-aware cnn的paper，在基本不增加計算量和參數量的前提上，成功的將depth和color image有效的融合在一起去提高二維圖片的分割精度。這可以看作是將depth的三維信息fusion到二維當中提高了二維語義分割的精度。從這個角度來講，depth是應該比point cloud更好的方式。另外值得關注的一個現象是，二維的語義分割通過depth投影到三維和接處理點雲做語義分割相比，效果會非常差，反過來，語義分割好的點雲投影到二維之後，從二維來看，分割效果也非常差，尤其是邊緣信息。這其實也說明三維和二維實際上還是差別很大，不知道之後會不會有人一些類似於平面約束的方式去改善投影與反投影的效果。另外與slam相結合，構建語義地圖的相關工作或者替代其中一個模塊，比如semanticfusion，就是用二維分割再投影到三維，fusion++利用maskrcnn檢測的物體做landmark，進行迴環檢測。類似的工作實際上都是用的二維投影三維，因為對於slam講landmark可能不要求像素級別那麼精細。總結起來，之後可能對於三維直接分割來講，速度可能是一個比較難以解決的問題，可能的思路就是利用SPG的先聚類的方式降低複雜度，但是這就要求要有比pointnet速度更快的方式。另外從工程和經濟成本上講，是否有比較直接對三維物體做精細的語義分割也有待商榷。

原文鏈接：

超詳細乾貨 | 三維語義分割概述及總結?

mp.weixin.qq.com圖標

推薦閱讀

計算機視覺方向簡介 | 從全景圖恢復三維結構

計算機視覺方向簡介 | 陣列相機立體全景拼接

計算機視覺方向簡介 | 單目微運動生成深度圖

計算機視覺方向簡介 | 深度相機室內實時稠密三維重建

計算機視覺方向簡介 | 深度圖補全

計算機視覺方向簡介 | 人體骨骼關鍵點檢測綜述

計算機視覺方向簡介 | 人臉識別中的活體檢測演算法綜述

計算機視覺方向簡介 | 目標檢測最新進展總結與展望

計算機視覺方向簡介 | 唇語識別技術

計算機視覺方向簡介 | 三維深度學習中的目標分類與語義分割

計算機視覺方向簡介 | 用深度學習進行表格提取

實戰 | 基於SegNet和U-Net的遙感圖像語義分割


推薦閱讀：
相关文章