王志成，余朝暉，衛(wèi) 剛，孫 雨

（同濟大學CAD研究中心，上海201804）

點云是一種重要的三維數(shù)據(jù)表示形式，數(shù)據(jù)保存時每一個點由坐標加上該位置上的值構成。因為點云的存儲形式具有不規(guī)則、無序性以及數(shù)據(jù)抽象和難以可視化等特點，因此點云處理面臨著巨大的挑戰(zhàn)。傳統(tǒng)方法在處理點云數(shù)據(jù)時存在著精度低、算法泛化能力差等問題。隨著深度學習在二維圖像任務如識別、檢測以及分割上取得巨大突破，學者們開始探索將神經(jīng)網(wǎng)絡運用到點云處理上并取得重大的進展。

將深度學習算法應用到點云處理上的最直接方法是先將數(shù)據(jù)轉換為體素化模型［1］，也就是三維結構化數(shù)據(jù)，然后直接用三維濾波器來訓練一個卷積神經(jīng)網(wǎng)絡，如應用于自動駕駛的全卷積網(wǎng)絡模型［2］。然而，該方法使體積數(shù)據(jù)變得龐大，訓練數(shù)據(jù)以及卷積核由二維變成三維，這意味著需要大量的計算，現(xiàn)階段的計算能力難以達到要求。還有一些方法采用多視圖數(shù)據(jù)，比較經(jīng)典的就是基于多視角的三維目標檢測網(wǎng)絡［3］。Charles 等［4］提出了第一個直接處理點云數(shù)據(jù)的神經(jīng)網(wǎng)絡算法PointNet，將點云數(shù)據(jù)投影到二維平面。該方法不直接處理三維的點云數(shù)據(jù)，而是先將點云投影到某些特定視角。許多研究對PointNet特征提取方式進行改進，如PointCNN［5］，通過一種自定義的X?Conv 操作，使常規(guī)的Convolution 也能處理點云。Jiang 等［6］提出了PointSIFT 模型，對于每一個點云能端對端地輸出一個表征向量，該向量編碼了各個方向的信息，同時自適應地選擇合適的表征尺度。目前，對于深度學習在點云數(shù)據(jù)實例分割中的運用已經(jīng)有了進展，相似度分組網(wǎng)絡（SGPN）［7］模型是第一個直接學習三維點云特征的實例分割網(wǎng)絡框架。使用PointNet提取特征，通過一個單獨網(wǎng)絡去預測點組推薦并為各個推薦組分配相應標簽；采用深度相似矩陣表征特征空間中每對點之間的相似性，進而產生點分組建議。

現(xiàn)階段點云實例分割并不能達到理想的效果，各種算法還有待提升。提出了一種基于超點圖的點云實例分割（ISPG）方法，旨在提高實例分割任務的精度和效率，并且在實驗中驗證方法的有效性。

1 基于超點圖的點云實例分割方法

為了處理無序的、不規(guī)則的點云數(shù)據(jù)，提出將大場景三維點云用一系列相互聯(lián)系的簡單形狀構成超點的表達方式，這種表達方式與影像分割中的超像素類似，由一種稱為超點圖（SPG）［8］的屬性有向圖結構描述。超點圖的節(jié)點表示簡單的結構，而富有邊特征的邊描述了它們的連接關系。

超點圖的表達方式有以下幾個顯著優(yōu)點：

（1）超點圖將目標的分割部分作為一個整體，而不是對單個點或者體素進行分類，部分點的整體—超點具備比單個點或者體素更加顯著的特征，有利于后續(xù)的實例分割。

（2）超點圖可以詳細描述相鄰目標之間的位置關系，這對于上下文分類至關重要，如車輛通常是在道路上、天花板由墻面包圍等。

（3）超點圖的大小由場景中簡單結構的數(shù)量決定，相比于處理之前的點集或者體素，超點圖在數(shù)據(jù)量上要小得多。因此，可以對長距離的交互進行建模，而這在沒有強假設的成對連接中是很難實現(xiàn)的。

1.1 超點劃分

算法將點云劃分成幾何上簡單且有意義的形狀，稱之為超點。算法的目標不是檢索單個對象，如汽車或椅子，而是將對象分解為簡單的幾何部分。對于聚類的結果，不僅要求在幾何上是簡單的，還期望在語義上是同質的，也就是每個幾何形狀不覆蓋不同類的對象。在超點圖的網(wǎng)絡中，將整個點云作為算法的輸入，從點云分區(qū)可以很容易地計算出超點圖。為了提高效率，這里使用了全局能量模型。

輸入點云C 是n 個點的集合，每個點由包含（x，y，z）的位置信息和其他觀察值定義，如顏色和強度等。對于每個點，將一組幾何特征ρ 作為局部特征。在本研究中，使用了文獻［9］中提出的三個特征描述符，包括線性、平面性和反射強度，以及文獻［8］中引入的垂直度特征。特征描述符是由鄰域定義的，對于每個點的鄰域，一組點的坐標的協(xié)方差矩陣的特征值分別為 λ1、λ2、λ3，規(guī)定 λ1≥λ2≥λ3。特征描述符的計算式如下所示：

式中：ρl表示線性度；ρp表示平面度；ρs表示散射值。線性度描述了鄰域的連續(xù)程度，平面度評估了鄰域點對于平面的擬合程度，散射值反映了各向同性和曲面度。在實驗中，垂直范圍被證明對區(qū)分道路和墻壁，以及具有相似尺寸的電線和電線桿至關重要。因此，還使用了垂直范圍分量η這個描述子。設u1、u2、u3是分別與λ1、λ2、λ3對應的三個特征量。將垂直范圍分量定義為特征向量各維度絕對值的加權和的近似，權重為對應的特征向量的值，計算式如下所示：

式中：uk表示單位化的特征向量。點云的空間結構可以由無向圖Gu=(V，E)表示，其中節(jié)點V代表點云的點，邊E 代表節(jié)點間的鄰接關系。全局能量模型［9］由距離每個點最近的n 個點定義，使用無向圖Gu=(V，Enn)，Enn表示最近的n個點的平均距離，算法的n取10。該幾何分區(qū)的問題被定義為以下能量泛函的極值問題：

式中：g 表示擬合既定特征；f 表示點的幾何特征，包含四個維度（ρl，ρp，ρs，η)；μ表示正則化系數(shù)，作用是保證分割的形狀足夠簡單；σ 為激活函數(shù)。該方法不僅可以達到有效逼近l0?cut 算法的效果，還具有自適應的效果。在幾何形狀變得復雜時，超點中包含的點的個數(shù)將下降，反之將上升。

1.2 超點圖定義

在第1.1 節(jié)中得到超點后，使用有向圖Go=(S，E，ω)表示整個點云，并命名為超點圖。S是所有超點的集合，S={S1， }S2，S3，… ，其中Si表示一個超點的點集；E表示超點之間的鄰接關系，命名為超邊，E={E1， }E2，E3，… ，其中Ei表示超邊；ω表示編碼超點圖邊界的權重。Ε表示無向圖中所有邊的集合，如果圖上有一條邊將超點連接在一起，則將兩個超點定義為相鄰，表達式如下所示：

式中：ωs，t表示（s，t）連接的個數(shù)。

超邊示意圖如圖1所示。點之間的邊用實線表示，部分超點分割之間的鄰接用虛線表示。

圖1 超邊Fig.1 Superedge

超邊還可以通過比較相鄰超點的形狀和大小來定義特征。用|S|表示超點S包含的點數(shù)。此外，還定義了長度L=λ1、表面積A=λ1λ2和體積v=λ1λ2λ3等形狀特征。λ1、λ2、λ3是每個超點中點的坐標的協(xié)方差矩陣的特征值，按遞減順序排序。表1描述了超邊特征，p表示一個超點。

表1 超邊描述子及定義Tab.1 Superedge descriptors and definitions

1.3 超點嵌入

將超點轉化為固定維度的向量表示。每個超點的轉化都是獨立進行的，超點所需要的上下文信息從第1.4節(jié)中獲取。

選取PointNet 作為超點嵌入算法模型。PointNet 網(wǎng)絡簡單，并且具有很好的魯棒性和較高的效率，在實驗中表現(xiàn)出不俗的性能，具體流程如圖2所示。在PointNet中，輸入點首先由空間變換網(wǎng)絡（STN）［10］實現(xiàn)對齊，然后由多層感知器（MLP）獨立處理，最后用最大池化提取到全局特征。圖2 中，np表示每次輸入的節(jié)點數(shù)，dp表示特征維度，dz表示輸出的特征維度。

圖2 超點嵌入Fig.2 Superpoint embedding

在超點的處理中，使用更為簡潔的PointNet 完成嵌入，一定程度上節(jié)省了在門控循環(huán)單元（GPU）上評估時的內存占用。具體做法：首先對超點進行采樣，訓練時點的個數(shù)小于40的超點將影響訓練效果，因此對此類超點的分類將依據(jù)上下文信息進行判斷。

為了使PointNet學習不同形狀的空間分布，在處理之前需要將每個超點都重新縮放到單位球面范圍內。因此，每個點由歸一化后的位置信息p′j、觀測信息oj以及幾何特征fj描述。此外，原始矩陣的縮放尺度將作為一個額外特征連接到最大池化后得到全局信息。

1.4 上下文語義中的分割

Pipeline 的最后一步是根據(jù)嵌入和超點圖中的局部特征對超點進行分類?；谥敖⒌某c圖模型，采用圖卷積來做最后的處理。

根據(jù)超邊的信息改善超點的嵌入。具體來說，每個超點si都在GRU 中保留其隱藏狀態(tài)。隱藏狀態(tài)初始化為嵌入，之后保留的是每輪迭代的結果。在迭代中，一個GRU 單元（見圖3）將其隱藏狀態(tài)和傳入信息作為輸入，并計算一個新的隱藏狀態(tài)。對超點si，傳入信息是和超點si鄰接的超點的隱藏狀態(tài)的加權和。

圖3 GRU模塊Fig.3 GRU module

GRU由一系列線性以及非線性計算組成，GRU的前向傳播過程如下所示：

式中：x(t)i為輸入；h(t)i為輸出；⊙為矩陣點乘運算；h?(t)i為隱藏狀態(tài)；σ(?)為sigmoid函數(shù)；z(t)i為重置門輸出矩陣；r(t)i為更新門輸出矩陣；W、U和b為GRU中共享的可訓練參數(shù)。式（7）和式（8）中出現(xiàn)了GRU的兩個組件，即重置門z(t)i和更新門r(t)i。為了提高訓練的穩(wěn)定性，對式（7）和式（8）在線性變換后采用歸一化操作，定是一個常數(shù)。

GRU 具有基于隱藏狀態(tài)對輸入進行加權的能力。例如，如果GRU的類別狀態(tài)非常確定，GRU就會自動忽略上下文，或者只關注特定的特性通道。在輸入之前乘上隱藏狀態(tài)的權重，通過設置這些權重可以控制消息。

邊緣條件卷積在模型中起著至關重要的作用，通過多層感知機處理連續(xù)序列的特征Fji動態(tài)生成過濾權重。多層感知機對權重矩陣進行回歸，這一操作需要對每個邊向量進行矩陣向量乘法，帶來大量的額外計算量，增加了運行時間、訪存以及參數(shù)量。為了減少計算量，只對特定于邊緣的權重向量進行回歸，并進行逐元素乘法，然后與GRU更新規(guī)則結合使用，使得通道混合被推遲。通過簡化，邊緣非特定方式的性能已達到與邊緣特定方式相似的水平。盡管感知機沒有明確S型激活函數(shù)，但逐元素乘法可以選擇學習來充當邊緣條件門。受到DenseNet［11］的啟發(fā)，將所有迭代過程中的隱藏狀態(tài)串聯(lián)起來，并進行線性變換，以生成稠密特征yi。多層感知機在時間迭代中是共享的，定義為WO，表達式如下所示：

2 算法流程

ISPG模型如圖4所示。算法分為以下三個步驟：

（1）按照幾何形狀均勻分區(qū)

將點云劃分為幾何上簡單且有意義的形狀，稱之為超點。這一步驟完全是無監(jiān)督的，分割出來的簡單形狀可以是大型的形狀如道路或墻壁，也可以是更小的組件，如汽車或椅子的零件。

圖4 ISPG模型Fig.4 ISPG model

（2）超點的嵌入

超點圖的每個節(jié)點對應整體點云的一小部分，也就是對應幾何形狀簡單的基元。假設超點在語義上是齊次的，將這些超點基元降采樣到最多數(shù)百個點來表示。小尺寸點云可使用PointNet方法處理。

（3）鄰域點云的分割

超點圖的數(shù)量級比建立在原始點云上的任何圖都小，基于圖卷積的深度學習算法使用超點的邊緣特征對這些節(jié)點進行分割，從而實現(xiàn)語義的分割。

3 實驗

基于ScanNet［12］數(shù)據(jù)集、斯坦福大型三維（3D）室內空間數(shù)據(jù)集（S3DIS）［1］以及KITTI 數(shù)據(jù)集評估算法。此外，評估指標是基于原始點云計算的，而不是基于超點。使用tensoflow 神經(jīng)網(wǎng)絡框架和單個Nvidia GTX1080 Ti GPU進行實驗。

3.1 超點質量

從圖5 的可視化結果可以看出，全局能量模型可以很好地對稠密特征和稀疏特征的物體進行自適應分割。幾何形狀比較復雜的物體，如桌子、書架等（樣本1和樣本3），在較小的尺度內被分割成較多超點；墻、地板和天花板等物體（樣本2），在特征空間內的距離很近，因此被分割成較為完整的超點。

3.2 對比實驗設置

將分割結果與以下兩種方法進行比較：

（1）簇分割（Seg?Cluster）模型

該模型在與SGPN［12］模型相關的論文中首次提出，采取一種貪婪策略對點云進行簡單分割。使用PointNet 網(wǎng)絡執(zhí)行語義分割，然后選擇所有點作為種子。從種子點開始，利用廣度優(yōu)先搜索具有相同標簽的鄰居。如果找到的群集超過200 個點，就將其視為有效群組，然后采用分組合并算法合并有效組群。

（2）SGPN（PointNet）模型

SGPN模型中使用單個網(wǎng)絡來預測點云的聚類區(qū)域及每個區(qū)域對應的語義類別。因此，該方法可以直接提取實例分割的結果。

3.3 ScanNet數(shù)據(jù)集測試結果

在ScanNet數(shù)據(jù)集上對18種常見對象類別進行評估和比較。原始點云作為輸入，目標是分割場景中屬于18 個對象類別的每個實例及其語義標簽。IoU（αIoU)閾值為0.5 的平均精度（βAP）用作評估指標，αIoU和βAP的計算式如下所示：

式中：NTP、NFP、NFN分別表示預測正確、預測錯誤、沒有預測到的物體數(shù)目。

圖5 全局能量模型生成超點Fig.5 Superpoints produced by global energy model

如表2 所示，ISPG 模型的平均精度在大多數(shù)對象類別上的表現(xiàn)都超過了SGPN 模型。由于ISPG模型只需要捕獲相對簡單的對象分布就可以生成非常高質量的候選群組，因此可以針對幾何變化較小的類別獲得很高的精度。對于在分割過程中需要稠密信息的類別（如門、窗），SGPN模型無法獲得良好的評分，因為它們的相似性度量無法有效地被編碼；ISPG模型在這些類別上獲得了更好的結果，這表明在生成候選群組時產生的特征更有利于分類。

圖6 為SGPN 模型與ISPG 模型之間的定性比較。SGPN模型需要在學習的相似性度量空間中劃出清晰的邊界來區(qū)分對象實例，可以觀察到許多對象包括一個對象的部分或多個對象的預測。與SGPN模型相比，ISPG模型生成的對象具有更高的針對性，從而帶來了更好的細分質量。當存在大量背景點時，SGPN 模型很難學習良好的相似性度量標準，因為其僅專注于前景點的語義和相似性的學習，并且在訓練過程中忽略了背景點，因此增加了基于背景的假陽性預測。

表2 ScanNet測試集IoU閾值為0.5的平均精度Tab.2 Average accuracy of ScanNet dataset with 0.5 IoU threshold

3.4 斯坦福數(shù)據(jù)集測試結果

斯坦福大型三維室內空間數(shù)據(jù)集S3DIS［1］包含從6 個區(qū)域和13 個對象掃描得到的270 個室內場景。使用203 個場景進行訓練，其余67 個場景進行評估。對于斯坦福大型三維室內空間數(shù)據(jù)集（S3DIS），將每個房間分成面積為1 m×1 m的塊，并且將每個點表示為九維（9D）矢量（XYZ，RGB 和歸一化的空間坐標）。在訓練過程中為每個模塊采樣了4 096個點，所有點都用于測試。

圖6 ScanNet數(shù)據(jù)集上ISPG與SGPN模型可視化結果Fig.6 Visualization results of ISPG and SGPN model on ScanNet dataset

圖7 顯示了使用ISPG 模型在S3DIS 上的實例分割結果。由于對象實例是無序的，因此同一組中點的顏色不一定與真實情況中對應點的顏色相同。為可視化實例類，還添加了語義分割結果。ISPG模型在各種房間類型上均表現(xiàn)出色。ISPG 模型的測試結果與SGPN 模型相比，很少出現(xiàn)邊緣分割混亂情況，這說明ISPG 模型的測試效果有了進一步的提升。

計算每個預測的和真實的標簽之間的點的αIoU。若αIoU大于閾值，則將檢測到的實例視為真陽性。進一步計算平均精度以進行實例分割性能評估，表3為IoU閾值0.5時每個類別的平均精度。

3.5 KITTI數(shù)據(jù)集測試結果

KITTI 數(shù)據(jù)集［13］包含市區(qū)、鄉(xiāng)村和高速公路等場景，每張圖像中包含豐富的行為和車輛的信息以及一些遮擋。整個數(shù)據(jù)集由389 對立體圖像、光流圖39.2 km視覺測距序列以及超過20萬個三維標注物體的圖像組成，以10 Hz的頻率采樣及同步。

對于該數(shù)據(jù)集，ISPG模型在小物體類別上獲得了可觀的收益，可以通過分區(qū)算法檢測。此外，在執(zhí)行空間規(guī)則化時，小物體通常與道路合并，可成為之后算法的一個改進方向。

KITTI數(shù)據(jù)集上的可視化效果如圖8所示。可以看出，雖然KITTI 數(shù)據(jù)集與前兩個數(shù)據(jù)集差異巨大，但是ISPG 模型依舊起到了很好的效果，說明模型具有很好的泛化能力。

表3 S3DIS測試集IoU閾值為0.5的平均精度Tab.3 Average accuracy of S3DIS dataset with 0.5 IoU threshold

圖7 S3DIS數(shù)據(jù)集上SGPN和ISPG模型可視化結果Fig.7 Visualization results of SGPN and ISPG model on S3DIS dataset

圖8 KITTI數(shù)據(jù)集上ISPG模型可視化結果Fig.8 Visualization results of ISPG model on KITTI dataset

4 結語

提出了基于超點圖的點云實例分割模型。首先將點云分割為超點，然后構建超點嵌入與邊特征，最后通過上下文信息對超點進行分類。超點圖的提出使得卷積運算不再運行在點上，而是運行在超點上，并通過豐富的邊特征來表征上下文的信息，在保證分割效果的同時，加快了運行速度。在多個數(shù)據(jù)集上對該算法進行了全面的驗證，取得了不錯的實例分割效果。