從傳統(tǒng)到深度學(xué)習(xí)：淺談點(diǎn)云分割中的圖結(jié)構(gòu)

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

圖1  一個(gè)典型的圖拓?fù)浣Y(jié)構(gòu)和分割示例。頂點(diǎn)（白點(diǎn)）在這里與5個(gè)最近的近鄰點(diǎn)相連。邊的成本由邊的粗細(xì)反映。a）對(duì)象點(diǎn)和箭頭所指向的背景點(diǎn)。b）種子點(diǎn)被相應(yīng)的終端替換，新創(chuàng)建的終端邊繼承先前連接的種子點(diǎn)權(quán)重。c）圖分割。淺灰色的頂點(diǎn)為前景對(duì)象，深灰色的是背景對(duì)象。

利用分割技術(shù)來(lái)識(shí)別空間上不均勻的連續(xù)區(qū)域，識(shí)別和圖像索引等更高層次的問(wèn)題也可以利用匹配中的分割結(jié)果，但在3D點(diǎn)云中分割對(duì)象的問(wèn)題是具有挑戰(zhàn)性的。例如前景通常與背景高度糾纏在一起，另外真實(shí)世界的數(shù)據(jù)具有大量噪點(diǎn)，采樣不均勻等特點(diǎn)，例如地面掃描的點(diǎn)密度在掃描方向上較為密集，而周?chē)^為稀疏；機(jī)載掃描對(duì)幾乎垂直的表面采樣則很差。此外，受設(shè)備自身技術(shù)參數(shù)的影響，使用不同設(shè)備采集得到的點(diǎn)云數(shù)據(jù)會(huì)導(dǎo)致不同物體之間的采樣率存在相當(dāng)大的差異，并且通常出現(xiàn)在同一物體的不同表面。受到計(jì)算機(jī)視覺(jué)和計(jì)算機(jī)圖形學(xué)中圖割技術(shù)的啟發(fā)，眾多學(xué)者將基于圖切割的方法應(yīng)用于點(diǎn)云的前景和背景分離，從而將3D表面分解為多個(gè)部分。

雖然點(diǎn)云中的圖割方法是圖像技術(shù)的擴(kuò)展。但與圖像技術(shù)明顯不同，顏色或紋理信息一般不在點(diǎn)云的圖割問(wèn)題中使用，并且與大多數(shù)計(jì)算機(jī)圖形分割問(wèn)題不同，點(diǎn)云處理的輸入端是表示帶有大量自然噪點(diǎn)的場(chǎng)景點(diǎn)云，而不是具有光滑表面的單個(gè)對(duì)象模型。

傳統(tǒng)點(diǎn)云方法中基于最小圖割的分割方法通常在點(diǎn)云上創(chuàng)建一個(gè)最近鄰圖來(lái)實(shí)現(xiàn)，定義一個(gè)懲罰函數(shù)來(lái)判斷平滑分割，其中前景與背景采用弱連接，并用最小切割最小化該函數(shù)。

圖2 傳統(tǒng)點(diǎn)云方法中圖割的典型應(yīng)用。

一個(gè)通用的表示即：用G=<V，E>表示要分割的點(diǎn)云，V和E分別是頂點(diǎn)（vertex）和邊（edge）的集合。普通的圖由頂點(diǎn)和邊構(gòu)成，如果邊的有方向的，這樣的圖被則稱(chēng)為有向圖，否則為無(wú)向圖，且邊是有權(quán)值的，不同的邊可以有不同的權(quán)值，分別代表不同的物理意義。同時(shí)，每條邊都有一個(gè)非負(fù)的權(quán)值，也可以理解為cost,這里的cost函數(shù)是需要人為定義的。一個(gè)cut（割）就是圖中邊集合E的一個(gè)子集C，那這個(gè)割的cost（表示為|C|）就是邊子集C的所有邊的權(quán)值的總和。

一般可以用類(lèi)似下面公式的一個(gè)能量函數(shù)E(L)描述點(diǎn)云圖割問(wèn)題。能量函數(shù)定義為：

L = {Lp|p∈V}是點(diǎn)云V的label。系數(shù)λ≥0用來(lái)指定區(qū)域項(xiàng)Rp()與邊界屬性項(xiàng)B <p,q>的相對(duì)重要性。將來(lái)自V的所有N個(gè)最近鄰對(duì)定義為集合M。

邊界屬性項(xiàng)反映了相鄰點(diǎn)之間的距離函數(shù)，即：

其中，

以上部分可以說(shuō)是老生常談，其實(shí)最重要的是如何解決這個(gè)優(yōu)化問(wèn)題。某些情況下該問(wèn)題為一個(gè)NP-hard問(wèn)題，感興趣的朋友可以去了解一下該問(wèn)題的求解方法，可以先從一個(gè)簡(jiǎn)單的二元優(yōu)化問(wèn)題入手。

隨著相關(guān)學(xué)者的進(jìn)一步深入，后續(xù)又出現(xiàn)了新的圖結(jié)構(gòu)，比如下面的這種半邊圖結(jié)構(gòu)。

圖3 典型的半邊圖結(jié)構(gòu)

該圖結(jié)構(gòu)將多邊形存儲(chǔ)為頂點(diǎn)的雙向鏈表可以方便地支持算法中處理多邊形所需的許多操作。例如，當(dāng)將兩個(gè)跨切線的凸多邊形組合成一個(gè)更大的凸多邊形時(shí)（例如在需要進(jìn)行分而治之的凸包算法中），處理速度將變得非?？臁?/span>

這種半邊數(shù)據(jù)結(jié)構(gòu)也稱(chēng)作雙連接邊列表（DCEL），是一種數(shù)據(jù)結(jié)構(gòu)，用于表示平面圖在平面中的嵌入，以及3D中的多面體。這種數(shù)據(jù)結(jié)構(gòu)提供了對(duì)象（頂點(diǎn)、邊、面）相關(guān)聯(lián)的拓?fù)湫畔ⅰ?/span>

圖4 分解為三層均勻超圖的超圖圖示

再比如上圖所示的超圖（Hypergraph），一個(gè)（無(wú)向）超圖H=(V,E)在n個(gè)頂點(diǎn)（或頂點(diǎn)）的有限集合V = {v1 , v2, ... ,vn}上被定義為p個(gè)超邊的集合E={e1,e2, ...,ep}。其中每個(gè)超邊都是V的非空子集。設(shè)H=(V,E)是一個(gè)超圖，w是一個(gè)權(quán)重，使得每個(gè)超邊e∈E映射到一個(gè)實(shí)數(shù)w(e)。超圖Hw = (V,E,w)被稱(chēng)為加權(quán)超圖。

簡(jiǎn)單的來(lái)說(shuō)，相比較普通圖而言，它的一個(gè)邊（edge）只能和兩個(gè)頂點(diǎn)連接；而對(duì)于超圖來(lái)講，人們定義它的邊（這里叫超邊，hyperedge）可以和任意個(gè)數(shù)的頂點(diǎn)連接。一個(gè)圖和超圖的示意圖如圖5所示：

圖5 一般圖和超圖的對(duì)比

隨著深度學(xué)習(xí)技術(shù)的發(fā)展，研究人員的工作重心又轉(zhuǎn)向了如何將圖結(jié)構(gòu)部署到深度學(xué)習(xí)網(wǎng)絡(luò)當(dāng)中去，一個(gè)典型的例子是2019年ICCV的一篇文章《Hierarchical Point-Edge Interaction Network for Point Cloud Semantic Segmentation》。

在這篇文章中，作者提出了一種邊分支結(jié)構(gòu)，從而為point branch提供上下文信息；同時(shí)，作者還利用分層圖結(jié)構(gòu)，實(shí)現(xiàn)一個(gè)由粗到細(xì)的信息生成過(guò)程。

圖6 所提框架的簡(jiǎn)單說(shuō)明。點(diǎn)分支和邊緣分支一起用來(lái)預(yù)測(cè)語(yǔ)義標(biāo)簽。

文章的主要貢獻(xiàn)就是探究局部區(qū)域中點(diǎn)之間的語(yǔ)義關(guān)系并利用上下文信息，作者顯式地在點(diǎn)與它們的上下文鄰居之間建立邊緣，并建立具有輔助邊緣損失的分層邊緣分支，如圖6所示。具體來(lái)說(shuō)，除了PointNet ++中的編碼器-解碼器點(diǎn)分支之外，所提出的新邊緣分支還接受來(lái)自不同層的點(diǎn)特征，并逐步生成邊緣特征，然后將其饋送到點(diǎn)分支以在局部圖中融合信息。對(duì)于每個(gè)點(diǎn)，相應(yīng)的邊緣特征提供局部固有的幾何和區(qū)域語(yǔ)義信息以增強(qiáng)點(diǎn)表示。

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

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

圖9  該框架在S3DIS數(shù)據(jù)集上語(yǔ)義分割結(jié)果

關(guān)于點(diǎn)云中的圖結(jié)構(gòu)還有很多相關(guān)paper，感興趣的小伙伴下來(lái)可以自己查找學(xué)習(xí)。

備注：作者也是我們「3D視覺(jué)從入門(mén)到精通」特邀嘉賓：一個(gè)超干貨的3D視覺(jué)學(xué)習(xí)社區(qū)

原創(chuàng)征稿

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

投稿方式

郵箱：[email protected] 或者加下方的小助理微信，另請(qǐng)注明原創(chuàng)投稿。

▲長(zhǎng)按加微信聯(lián)系

▲長(zhǎng)按關(guān)注公眾號(hào)