隨著3D掃描技術的進步，如何將點云的前景和背景正確分離成為點云處理的一個具有挑戰(zhàn)性的問題。具體來說，就是給定一個對象位置的估計，目標是識別屬于該對象的那些點，并將它們與背景點分開。除了將前景與背景分離的基本任務外，分割還有助于定位、分類和特征提取。根據(jù)人類視覺感知的原理，一個典型的2D圖像的圖割問題如圖1所示。

作者：PCB_Segment|微信公眾號：3D視覺工坊

注1：文末附有【三維點云】交流群加入方式

注2：激光SLAM系統(tǒng)教程：https://mp.weixin.qq.com/s/lfA-xwPNvR3-laemEGBAqQ

注3：結構光系統(tǒng)教程：https://mp.weixin.qq.com/s/WLyuE3ByntGA-Y0w8GZ29A

注4：自動駕駛系統(tǒng)課程：https://mp.weixin.qq.com/s/0-mb6M6HvKU3Uau0a4taTw

注5：三維重建系統(tǒng)課程：https://mp.weixin.qq.com/s/9gtdrloSWR2kJlYk5CnWIQ

注6：三維點云系統(tǒng)課程：https://mp.weixin.qq.com/s/uJ34xjWjAFCzDDduoo0ixA

圖1 一個典型的圖拓撲結構和分割示例。頂點（白點）在這里與5個最近的近鄰點相連。邊的成本由邊的粗細反映。a）對象點和箭頭所指向的背景點。b）種子點被相應的終端替換，新創(chuàng)建的終端邊繼承先前連接的種子點權重。c）圖分割。

淺灰色的頂點為前景對象，深灰色的是背景對象。利用分割技術來識別空間上不均勻的連續(xù)區(qū)域，識別和圖像索引等更高層次的問題也可以利用匹配中的分割結果，但在3D點云中分割對象的問題是具有挑戰(zhàn)性的。例如前景通常與背景高度糾纏在一起，另外真實世界的數(shù)據(jù)具有大量噪點，采樣不均勻等特點，例如地面掃描的點密度在掃描方向上較為密集，而周圍較為稀疏；機載掃描對幾乎垂直的表面采樣則很差。此外，受設備自身技術參數(shù)的影響，使用不同設備采集得到的點云數(shù)據(jù)會導致不同物體之間的采樣率存在相當大的差異，并且通常出現(xiàn)在同一物體的不同表面。受到計算機視覺和計算機圖形學中圖割技術的啟發(fā)，眾多學者將基于圖切割的方法應用于點云的前景和背景分離，從而將3D表面分解為多個部分。雖然點云中的圖割方法是圖像技術的擴展。但與圖像技術明顯不同，顏色或紋理信息一般不在點云的圖割問題中使用，并且與大多數(shù)計算機圖形分割問題不同，點云處理的輸入端是表示帶有大量自然噪點的場景點云，而不是具有光滑表面的單個對象模型。傳統(tǒng)點云方法中基于最小圖割的分割方法通常在點云上創(chuàng)建一個最近鄰圖來實現(xiàn)，定義一個懲罰函數(shù)來判斷平滑分割，其中前景與背景采用弱連接，并用最小切割最小化該函數(shù)。

圖2 傳統(tǒng)點云方法中圖割的典型應用。一個通用的表示即：用G=<V，E>表示要分割的點云，V和E分別是頂點（vertex）和邊（edge）的集合。普通的圖由頂點和邊構成，如果邊的有方向的，這樣的圖被則稱為有向圖，否則為無向圖，且邊是有權值的，不同的邊可以有不同的權值，分別代表不同的物理意義。同時，每條邊都有一個非負的權值，也可以理解為cost,這里的cost函數(shù)是需要人為定義的。一個cut（割）就是圖中邊集合E的一個子集C，那這個割的cost（表示為|C|）就是邊子集C的所有邊的權值的總和。一般可以用類似下面公式的一個能量函數(shù)E(L)描述點云圖割問題。能量函數(shù)定義為：

L = {Lp|p∈V}是點云V的label。系數(shù)λ≥0用來指定區(qū)域項Rp()與邊界屬性項B <p,q>的相對重要性。將來自V的所有N個最近鄰對定義為集合M。邊界屬性項反映了相鄰點之間的距離函數(shù)，即：

其中，

以上部分可以說是老生常談，其實最重要的是如何解決這個優(yōu)化問題。某些情況下該問題為一個NP-hard問題，感興趣的朋友可以去了解一下該問題的求解方法，可以先從一個簡單的二元優(yōu)化問題入手。隨著相關學者的進一步深入，后續(xù)又出現(xiàn)了新的圖結構，比如下面的這種半邊圖結構。

圖3 典型的半邊圖結構該圖結構將多邊形存儲為頂點的雙向鏈表可以方便地支持算法中處理多邊形所需的許多操作。例如，當將兩個跨切線的凸多邊形組合成一個更大的凸多邊形時（例如在需要進行分而治之的凸包算法中），處理速度將變得非?？臁＿@種半邊數(shù)據(jù)結構也稱作雙連接邊列表（DCEL），是一種數(shù)據(jù)結構，用于表示平面圖在平面中的嵌入，以及3D中的多面體。這種數(shù)據(jù)結構提供了對象（頂點、邊、面）相關聯(lián)的拓撲信息。

圖4 分解為三層均勻超圖的超圖圖示再比如上圖所示的超圖（Hypergraph），一個（無向）超圖H=(V,E)在n個頂點（或頂點）的有限集合V = {v1 , v2, ... ,vn}上被定義為p個超邊的集合E={e1,e2, ...,ep}。其中每個超邊都是V的非空子集。設H=(V,E)是一個超圖，w是一個權重，使得每個超邊e∈E映射到一個實數(shù)w(e)。超圖Hw = (V,E,w)被稱為加權超圖。簡單的來說，相比較普通圖而言，它的一個邊（edge）只能和兩個頂點連接；而對于超圖來講，人們定義它的邊（這里叫超邊，hyperedge）可以和任意個數(shù)的頂點連接。一個圖和超圖的示意圖如圖5所示：

圖5 一般圖和超圖的對比隨著深度學習技術的發(fā)展，研究人員的工作重心又轉向了如何將圖結構部署到深度學習網(wǎng)絡當中去，一個典型的例子是2019年ICCV的一篇文章《Hierarchical Point-Edge Interaction Network for Point Cloud Semantic Segmentation》。在這篇文章中，作者提出了一種邊分支結構，從而為point branch提供上下文信息；同時，作者還利用分層圖結構，實現(xiàn)一個由粗到細的信息生成過程。

圖6 所提框架的簡單說明。點分支和邊緣分支一起用來預測語義標簽。文章的主要貢獻就是探究局部區(qū)域中點之間的語義關系并利用上下文信息，作者顯式地在點與它們的上下文鄰居之間建立邊緣，并建立具有輔助邊緣損失的分層邊緣分支，如圖6所示。具體來說，除了PointNet ++中的編碼器-解碼器點分支之外，所提出的新邊緣分支還接受來自不同層的點特征，并逐步生成邊緣特征，然后將其饋送到點分支以在局部圖中融合信息。對于每個點，相應的邊緣特征提供局部固有的幾何和區(qū)域語義信息以增強點表示。

圖7 總體架構。N表示原始點云中的點數(shù)。N的下標是層索引。較大的索引表示具有更多點的圖層。C表示點要素通道的數(shù)量。K表示邊緣特征通道的數(shù)量。E表示邊集。邊緣特征是從最粗糙的層0開始編碼的，并逐漸被后來的層的點特征所精煉。不同層中的邊緣要素也參與相應的點模塊以提供上下文信息。

圖8 邊緣向上采樣的演示。i,j為經(jīng)過點模型新增加的點，通過尋找i,j的共同近鄰來作為新增邊的特征。圖中第三副就是i近鄰點的特征邊，第四幅圖中紅色的邊就是兩個點近鄰共同擁有的邊。

圖9 該框架在S3DIS數(shù)據(jù)集上語義分割結果關于點云中的圖結構還有很多相關paper，感興趣的小伙伴下來可以自己查找學習。備注：作者也是我們「3D視覺從入門到精通」特邀嘉賓：一個超干貨的3D視覺學習社區(qū)

原創(chuàng)征稿

初衷

3D視覺工坊是基于優(yōu)質原創(chuàng)文章的自媒體平臺，創(chuàng)始人和合伙人致力于發(fā)布3D視覺領域最干貨的文章，然而少數(shù)人的力量畢竟有限，知識盲區(qū)和領域漏洞依然存在。為了能夠更好地展示領域知識，現(xiàn)向全體粉絲以及閱讀者征稿，如果您的文章是3D視覺、CV&深度學習、SLAM、三維重建、點云后處理、自動駕駛、三維測量、VR/AR、3D人臉識別、醫(yī)療影像、缺陷檢測、行人重識別、目標跟蹤、視覺產品落地、硬件選型、求職分享等方向，歡迎砸稿過來~文章內容可以為paper reading、資源總結、項目實戰(zhàn)總結等形式，公眾號將會對每一個投稿者提供相應的稿費，我們支持知識有價！投稿方式

郵箱：vision3d@yeah.net 或者加下方的小助理微信，另請注明原創(chuàng)投稿。

微信交流群：

歡迎加入「3D視覺工坊」交流群，方向涉及3D視覺、計算機視覺、深度學習、vSLAM、激光SLAM、立體視覺、自動駕駛、點云處理、三維重建、多視圖幾何、結構光、多傳感器融合、VR/AR、學術交流、求職交流等。工坊致力于干貨輸出，為3D領域貢獻自己的力量！歡迎大家一起交流成長~

添加小助手微信：CV_LAB，備注學校/公司+姓名+研究方向即可加入工坊一起學習進步。