基于八叉樹的卷積神經(jīng)網(wǎng)絡(luò)三維模型分割

楊曉文，李 靜，韓 燮，韓慧妍，陶 謙

(中北大學(xué) 大數(shù)據(jù)學(xué)院，山西 太原 030051)

0 引 言

由于獲取3D信息設(shè)備的不斷發(fā)展，通過建模工具所創(chuàng)建的三維模型不斷增多，對其進行研究成為熱點問題。其中，三維模型的分割包括對點云與網(wǎng)格模型的分割，根據(jù)語義上的不同，把完整的三維模型分割為相鄰子部分[1]。三維模型的分割有利于進一步理解和分析三維模型，包括變形、簡化、檢索以及曲面重建等[2]，同時也是古文物保護、建筑物及城市場景三維建模、動植物外形建模、醫(yī)學(xué)檢測、幾何壓縮與傳輸?shù)裙ぷ鞯幕A(chǔ)，在許多模型處理和視覺應(yīng)用上也越來越重要。

1 相關(guān)研究

卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural networks, CNN)不斷應(yīng)用在各領(lǐng)域中，國內(nèi)外研究學(xué)者根據(jù)對三維形狀的分析，利用卷積神經(jīng)網(wǎng)絡(luò)對三維模型的分割進行了研究，其中，主要為基于體素，流形以及多視圖3類方法。

基于體素的方法是指以三維空間的體素作為定義域進行3D卷積，將CNN拓展到三維空間進行學(xué)習(xí)。Maturana等[3]將3D形狀光柵化并在密集體素上采樣距離函數(shù)，在整個體素上應(yīng)用3D CNN。Wu NZ等[4]在體素上定義3D CNN以進行形狀分析，提出了用于物體識別和形狀分析的3D ShapeNets，但是該方法只適合于低分辨率的三維模型。為了降低基于全體素方法的計算成本，Graham B[5]提出了3D稀疏CNN，對于深層CNN，該方法的計算和存儲成本仍然很高。這些方法計算量大，不易儲存，不適用于高分辨率模型。

基于流形的方法是指對流形網(wǎng)格上定義的特征進行CNN操作。Boscaini等[6]將3D表面參數(shù)化為2D圖像，將采樣的特征圖像饋送到CNN中以進行形狀分析。Bronstein等[7]將CNN擴展到由不規(guī)則三角形網(wǎng)格定義的圖形上。這些方法對于三維模型的等距變形較為穩(wěn)健，但是它們被約束為平滑的流形網(wǎng)格時難以提取局部特征，噪聲較大。

基于多視圖的方法是指利用空間投影將三維模型轉(zhuǎn)化為多個視圖下的二維影像，并將圖像堆棧作為2D CNN的輸入。謝智歌等[8]提出了基于全卷積的多角度多層次極限學(xué)習(xí)機的三維模型分割方法，該方法通過對深度圖像的多標(biāo)簽訓(xùn)練、預(yù)測以及把標(biāo)簽回投到三維模型的三角面片上得到分割結(jié)果。Kalogerakis等[9]設(shè)計了一個投影卷積網(wǎng)絡(luò)應(yīng)用于三維形狀的分割。這些方法直接利用基于圖像的CNN進行3D形狀分析并處理高分辨率輸入，但是不能確定視圖數(shù)量以完全覆蓋三維模型，無法避免遺失三維信息。

本文利用八叉樹表示三維點云模型，將卷積計算限制在八叉樹節(jié)點上，使計算量只和八叉樹節(jié)點數(shù)目相關(guān)，卷積、反卷積、池化、反池化操作由于八叉樹的數(shù)據(jù)和層次結(jié)構(gòu)在迭代過程中計算高效，減少了計算與存儲成本，避免了視圖選擇問題，可以處理高分辨率的點云輸入。實驗及評估度量結(jié)果表明，實驗數(shù)據(jù)集中大多數(shù)模型取得了良好的分割效果。

2 背景知識

2.1 卷積神經(jīng)網(wǎng)絡(luò)

卷積神經(jīng)網(wǎng)絡(luò)是一種前饋神經(jīng)網(wǎng)絡(luò)，包含卷積計算并具有深層結(jié)構(gòu)，其不斷應(yīng)用在深度學(xué)習(xí)中[10]。CNN的本質(zhì)是多層感知機，局部連接和權(quán)值共享的方式減少了權(quán)值的數(shù)量更易于優(yōu)化網(wǎng)絡(luò)，降低模型的復(fù)雜度，減小過擬合的風(fēng)險。通過構(gòu)建多層網(wǎng)絡(luò)提取數(shù)據(jù)中具有抽象語義信息的高層次特征，得到更好的特征魯棒性。

CNN是基于監(jiān)督學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)，實現(xiàn)特征提取功能的核心模塊位于隱含層的卷積層和池化層，每層有多個特征圖，每個特征圖有多個神經(jīng)元，并使用大小不等的卷積濾波器提取特征。其中，卷積層為特征提取層，通過權(quán)值共享的卷積核使每一層的特征都由上一層的局部區(qū)域激勵得到，即將每個神經(jīng)元的輸入與上一層的局部感知野相連，并由激活函數(shù)形成并輸出特征映射圖[11]。池化層位于連續(xù)的卷積層中，用于壓縮數(shù)據(jù)和參數(shù)量，去除冗余信息，防止過擬合。

2.2 八叉樹結(jié)構(gòu)

二維圖像通常結(jié)構(gòu)化表示為二維平面上的矩陣，但是三維形狀是非結(jié)構(gòu)化的，尤其點云數(shù)據(jù)是不規(guī)則和無序的。因此，利用卷積神經(jīng)網(wǎng)絡(luò)處理點云數(shù)據(jù)時，由于輸入數(shù)據(jù)的不穩(wěn)定性使得卷積操作難以直接應(yīng)用到點云數(shù)據(jù)上。

利用自適應(yīng)的空間剖分來壓縮存儲點云數(shù)據(jù)，八叉樹[12]是一個非常好的選擇。八叉樹是一種遞歸、軸對齊且空間分隔的數(shù)據(jù)結(jié)構(gòu)，將空間分成等體積的立方體可以加速細分運算，且單元大小的存儲也可以節(jié)省空間。三維空間根據(jù)是否含有三維點云的一部分決定是否一分為八，并在子塊里重復(fù)劃分。八叉樹結(jié)構(gòu)常用于計算機幾何進行優(yōu)化碰撞檢測、最鄰近搜索等，且常用于三維數(shù)據(jù)的表達。

3 基于八叉樹的卷積神經(jīng)網(wǎng)絡(luò)的三維模型分割

本文使用八叉樹結(jié)構(gòu)化表示三維點云模型，在點云模型的邊界表面占據(jù)的稀疏八分體上執(zhí)行CNN操作對三維點云模型進行分割。本文方法流程包括：①對點云模型進行預(yù)處理并在此基礎(chǔ)上構(gòu)建表示點云的八叉樹結(jié)構(gòu)，八叉樹的最深葉節(jié)點處存儲點云的信息，提取最大深度的葉子八分體中采樣點云的平均法向量與平均曲率，并將其融合作為卷積網(wǎng)絡(luò)的輸入特征，存儲在相對應(yīng)的葉節(jié)點上；②將卷積計算限制在八叉樹節(jié)點上，計算每個深度的相鄰水平節(jié)點的特征，池化合并之后，將特征下采樣到父節(jié)點并且被傳送到下一八叉樹深度層。級聯(lián)反卷積神經(jīng)網(wǎng)絡(luò)進行逐點預(yù)測，遍歷整個神經(jīng)網(wǎng)絡(luò)，不斷迭代神經(jīng)網(wǎng)絡(luò)層訓(xùn)練并測試，得出點云模型分割預(yù)測標(biāo)簽；③使用CRF優(yōu)化并進行分割可視化得出三維點云模型分割結(jié)果。本文方法流程如圖1所示。

圖1 本文方法流程

3.1 數(shù)據(jù)準(zhǔn)備過程

3.1.1 點云預(yù)處理

實驗所用原始模型是稀疏點云，并且點云模型缺失了對應(yīng)的法線信息，為此將點云模型與相應(yīng)的3D網(wǎng)格對齊，并將點投影到三角面片中，然后采用射線射擊算法在三角網(wǎng)格中確定密集點，將密集點所在的三角面片的法線分配給該點，得到預(yù)處理的點云模型。射線射擊算法具體來說，在將點云模型投影到三角面片的基礎(chǔ)上，根據(jù)點云中每個點所在的三角面片確定包含該點云模型的邊界立方體(該邊界立方體是根據(jù)三角面片統(tǒng)一采樣來確定的)，將多個虛擬相機均勻放置在包含點云模型的邊界立方體的各個面中心，從每個方向均勻地對模型發(fā)射平行光線，計算光線與三角面片的交點，如果此三角面片中包含了點云模型中的點，即將該點的法線指向相機，不相交的點被舍棄，得到點云模型的密集點，以此預(yù)處理點云得到具有定向法線和密集點的點云數(shù)據(jù)。

3.1.2 構(gòu)造八叉樹結(jié)構(gòu)

為了構(gòu)造表示三維點云的八叉樹結(jié)構(gòu)，首先將三維點云模型縮放于軸對稱的3D立方體中，然后采用廣度優(yōu)先算法，細分點云模型的邊界立方體，并不斷迭代，直到將深度為d處的點云模型邊界所占據(jù)的所有非空八分體細分到下一深度d+1處的八個子八分體，即達到指定的八叉樹深度，迭代停止。八叉樹的每一層由排序后的隨機鍵數(shù)組和標(biāo)記非空節(jié)點序號的標(biāo)簽數(shù)組組成[13]，通過這些數(shù)組可以快速訪問節(jié)點鄰居。八叉樹構(gòu)造過程如圖2所示。

圖2 八叉樹構(gòu)造過程

其中，隨機鍵是用來表示深度為d的八分體O在3D空間中的相對位置：key(O)∶x1y1z1x2y2z2..xdydzd,xiyizi∈{0，d}。 通過隨機鍵升序排列八分體，第d深度的所有八分體中排序后的隨機鍵存儲在隨機鍵矢量Sd中，矢量的長度是當(dāng)前深度的八分體的數(shù)量，該矢量用于構(gòu)建3D卷積中八分體的鄰域。類比四叉樹節(jié)點的隨機鍵與每個深度的相應(yīng)隨機鍵數(shù)組如圖3所示。

圖3 四叉樹隨機鍵與標(biāo)簽

描述相鄰深度的父子八分體之間的關(guān)系，通過池化操作將深度為d的八分體處計算得到的特征經(jīng)過下采樣計算后連接到深度為d+1的子八分體，并為非空八分體指定標(biāo)簽p， 并將該深度處的所有八分體的標(biāo)簽存儲在標(biāo)簽矢量Ld中。詳細定義請參見文獻[13]。在第d深度的一個非空節(jié)點處定義索引j，計算第d+1深度處其第一個子八分體的索引k=8*(Ld[j]-1)， 從而可以快速找到父節(jié)點到其子節(jié)點的對應(yīng)關(guān)系。類比四叉樹每個深度的標(biāo)簽矢量如圖3所示。

3.1.3 提取特征

構(gòu)造點云的八叉樹結(jié)構(gòu)之后，提取最大深度的葉子八分體中采樣點云的平均法向量[14]與平均曲率，兩者相融合作為CNN的輸入特征。對于空葉子八分體，將其指定為零向量作為輸入特征；對于非空葉子八分體，對嵌入葉子八分體中的點云形狀表面的一組點進行采樣，利用點云預(yù)處理過程中分配給各點的定向法線計算平均法向量。

(1)

式中：NP(i) 表示點pi在該葉子八分體區(qū)域，N表示該葉子八分體內(nèi)點的個數(shù)，pj是pi在此葉子八分體內(nèi)的鄰域點，從而得到pi的協(xié)方差如式(2)所示

(2)

式中：C是一個半正定矩陣，可以取3個非負特征值λi(i=0,1,2)。 當(dāng)λ0<λ1<λ2， 并定義λi的對應(yīng)正交特征向量為ni(i=0,1,2)， 又由式(3)所示

(3)

此時T(x) 表示點pi的最小二乘平面，近似看作點pi切平面。n0表示點pi在局部區(qū)域內(nèi)的法矢，特征值λ表示為該曲面的變分。由Pualy等[16]定義可得該曲面變分近似于點pi處的曲率，如式(4)所示

(4)

并根據(jù)平均曲率定義求得點pi處平均曲率。

特征融合[16]是指從多個相關(guān)原始特征集中獲得最具差異性的信息，能夠消除因不同特征集之間的相關(guān)性而產(chǎn)生的冗余信息。本文方法中計算出平均法向量和平均曲率之后，利用并行特征融合策略將其合并成一個比單個輸入特征更具有判別能力的特征并將其作為卷積神經(jīng)網(wǎng)絡(luò)的輸入特征。并行特征融合策略的思想是：假設(shè)α，β是同一樣本的兩組特征向量，用復(fù)向量來表示樣本的并行組合特征[16]，融合公式如式(5)所示

γ=α+iβ(i是虛數(shù))

(5)

最后將融合后的特征作為卷積神經(jīng)網(wǎng)絡(luò)的輸入特征并將其存儲到輸入特征矢量中。

3.2 卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

卷積神經(jīng)網(wǎng)絡(luò)對點云的八叉樹結(jié)構(gòu)反復(fù)應(yīng)用卷積和池化操作，本文中激活函數(shù)使用ReLU(f∶x∈R→max(0,x))， 并使用批量標(biāo)準(zhǔn)化(BN)來減少內(nèi)部協(xié)變量偏移。將“convolution+BN+ReLU+pooling”作為基本單元，當(dāng)卷積操作應(yīng)用于深度為d的八分體時，由Ud表示，Ud的特征映射的通道數(shù)設(shè)置為2max(d，9-d)， 卷積核大小為3*3*3。 該部分網(wǎng)絡(luò)結(jié)構(gòu)定義為CNN(d)：輸入→Ud→Ud-1→…→U2。

本文方法參考圖像語義分割網(wǎng)絡(luò)DeconvNet[17]，在卷積網(wǎng)絡(luò)之后級聯(lián)反卷積網(wǎng)絡(luò)進行密集逐點預(yù)測。卷積網(wǎng)絡(luò)被設(shè)置為CNN(d)，反卷積網(wǎng)絡(luò)是CNN(d)的鏡像，其中卷積和池化運算符由反卷積和上池化代替。將“unpooling+deconvolution+BN+ReLU”作為一個基本單位，將反卷積操作應(yīng)用于深度為d的八分體時，則由DUd表示。所以整體卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)定義為： CNN(d)→DU2→DU3→…DUd。 網(wǎng)絡(luò)結(jié)構(gòu)如圖4所示。

圖4 網(wǎng)絡(luò)結(jié)構(gòu)

3.2.1 3D卷積

3D卷積(3D convolution)是指卷積核的維度為三維，最早提出用于行為識別等領(lǐng)域。在本文方法中，將卷積運算應(yīng)用于某個深度處的所有八分體，需要在該八叉樹深度處連接其相鄰八分體，卷積運算φc如式(6)所示

(6)

3.2.2 池 化

池化(pooling)的目的是逐步壓縮空間大小，是對卷積層輸出的特征圖做下采樣操作。池化層在每個通道上獨立運行，并在空間上調(diào)整其大小，去除冗余信息，最常見的形式是max-pooling和avy pooling，本文采用max-pooling操作。八叉樹結(jié)構(gòu)上應(yīng)用max-pooling可以從每8個連續(xù)存儲的子八分體屬性值中挑選出最大值。

3.2.3 上池化

上池化(unpooling)操作是匯集和執(zhí)行上采樣的逆向操作，一般指的是max-pooling的逆過程，廣泛用于CNN可視化和圖像分割。應(yīng)用max-pooling之后，每個池區(qū)域中最大值的位置記錄并存儲在一組變量中，這些變量將當(dāng)前特征映射放入上采樣特征映射的適當(dāng)位置。在CNN中，最大池化操作是不可逆的，可以通過使用一組轉(zhuǎn)換變量記錄每個池化區(qū)域內(nèi)最大值的位置獲得一個近似的逆操作結(jié)果。

3.2.4 反卷積

反卷積(deconvolution)，也稱為轉(zhuǎn)置卷積和反向卷積，用來放大和加密特征圖，步長為k的反卷積核可以實現(xiàn)特征圖的k倍放大效果。卷積層的反向傳播過程是反卷積層的前向傳播過程，基于先前描述的八叉樹上的卷積操作，可以相應(yīng)地實現(xiàn)反卷積操作。

3.2.5 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法

(7)

ωt+1=ωt+Vt+1

(8)

其中， ?是負梯度的學(xué)習(xí)率(base_lr),μ是上一次梯度值的權(quán)重(momentum)，用來加權(quán)之前梯度對現(xiàn)在梯度下降方向的影響，這兩個參數(shù)值需要通過不斷調(diào)整得到最合適的值。

3.2.6 損失函數(shù)

損失函數(shù)[19]在CNN中是用來衡量預(yù)測標(biāo)簽與初始標(biāo)簽一致性的度量指標(biāo)。本文中使用SoftmaxWithLoss計算訓(xùn)練過程中的損失值，卷積過程中，SoftmaxWithLossLayer主要使用了兩個概率統(tǒng)計原理：邏輯回歸和最大似然估計。

邏輯回歸對應(yīng)于Softmax,其將神經(jīng)網(wǎng)絡(luò)的輸出特征轉(zhuǎn)化成概率，最大似然估計用于計算損失函數(shù)，其核心公式如式(9)、式(10)所示

(9)

(10)

其中，yi為標(biāo)簽值，k為輸入點云標(biāo)簽所對應(yīng)的神經(jīng)元，m為輸出的最大值，主要考慮數(shù)值穩(wěn)定性。而反向傳播時loss計算公式如式(11)所示

(11)

對輸入的zk求導(dǎo)可得式(12)

(12)

3.3 CRF優(yōu)化

本文使用條件隨機場CRF(conditional random field algorithm)[20]優(yōu)化分割結(jié)果。由于反卷積網(wǎng)絡(luò)分別對每個點進行預(yù)測，分割后的點云模型中相鄰區(qū)域之間仍然存在噪聲，因此使用CRF對結(jié)果進行調(diào)整。

E(x)=∑iφu(xi)+∑i

(13)

式中：i和j的范圍從1到N。φu(xi) 用來約束最終輸出結(jié)果，定義為φu(xi)=-log(p(xi))， 其中p(xi) 是神經(jīng)網(wǎng)絡(luò)生成標(biāo)簽的概率。φp(xi,xj) 用于合并信息以輸出精確結(jié)果，如式(14)所示

(14)

式中：Wθi表示具有標(biāo)準(zhǔn)差θi的高斯函數(shù)，μ(xi,xj) 是標(biāo)簽函數(shù)，ωi和θi是超參數(shù)。通過CRF優(yōu)化算法之后，點云模型的不同分割區(qū)域之間噪聲減小，邊緣更平滑。

4 實驗討論

4.1 數(shù)據(jù)集與實驗環(huán)境

本文實驗使用數(shù)據(jù)集ShapeNetCore的一個子集，包含16種形狀類別，大約17 000個點云模型，每個類別有2到6個部分，總共有50類不同區(qū)域的標(biāo)簽注釋。在實驗中，對于每一類的點云模型分別以模型總數(shù)90%的數(shù)據(jù)量作訓(xùn)練數(shù)據(jù)，10%的數(shù)據(jù)量作測試數(shù)據(jù)。

實驗環(huán)境：以Caffe為深度學(xué)習(xí)框架，支持GPU運算；Intel(R)Core(TM)i7，CPU@2.80 GHz，NVIDIA GeForce GTX 1050 Ti 4 GB，VS2015+anaconda 3.4.2，CUDA8.0+cudnn-8.0-windows10-x64-v5.0。

4.2 訓(xùn)練與測試

實驗中神經(jīng)網(wǎng)絡(luò)的參數(shù)和函數(shù)設(shè)置見表1。網(wǎng)絡(luò)模型采用SDG優(yōu)化算法，迭代學(xué)習(xí)中隨機均勻采樣訓(xùn)練數(shù)據(jù)，更新模型參數(shù)，逐層調(diào)節(jié)權(quán)重參數(shù)，使用SoftmaxWithLoss通過大量的迭代訓(xùn)練提高網(wǎng)絡(luò)的精度，并計算迭代過程中的損失值。針對不同類別的個別參數(shù)進行調(diào)整，其中基礎(chǔ)學(xué)習(xí)率變化范圍在0.1到0.001之間；批量大小和測試間隔隨測試集的數(shù)量大小進行調(diào)整，調(diào)整規(guī)則為2的整數(shù)次冪；最大迭代數(shù)根據(jù)訓(xùn)練集的大小調(diào)整。

表1 實驗參數(shù)/函數(shù)設(shè)置

在卷積神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程中，訓(xùn)練與測試同時進行，并將測試間隔設(shè)置為200，即每訓(xùn)練200次測試一次，同時計算各自的準(zhǔn)確率與損失值。在訓(xùn)練迭代結(jié)束后，生成caffemodel(caffemodel里不僅存儲了權(quán)重和偏置等信息，還存儲了整個訓(xùn)練網(wǎng)絡(luò)的結(jié)構(gòu)信息)。在測試階段，調(diào)用每個類別的caffemodel獲得每個最精細葉節(jié)點的輸出標(biāo)簽和預(yù)測概率，此時可以得到通過神經(jīng)網(wǎng)絡(luò)輸出的逐點的預(yù)測標(biāo)簽。

4.3 結(jié)果與對比

本文使用pcl工具可視化分割結(jié)果。簡單來說，使用八叉樹結(jié)構(gòu)中的葉節(jié)點表示點云模型，使用神經(jīng)網(wǎng)絡(luò)得到的預(yù)測標(biāo)簽分別以不同顏色分類顯示分割結(jié)果的不同區(qū)域。經(jīng)過CRF優(yōu)化之后，本文方法得到的分割效果如圖5所示。

圖5 本文方法應(yīng)用于ShapeNetCore子集的分割效果

本文還分別使用PointNet[21]，SpecCNN[22]，O-CNN(5)[13]，O-CNN(6)[13]，SPGN[23]的方法進行實驗并且與本文方法進行比較，如圖6所示，可以看出，O-CNN(6)方法在模型右側(cè)椅腿與椅座連接處噪聲明顯，本文方法則在分割相鄰區(qū)域處以及邊界處噪聲較小，邊緣更平滑，分割效果更好。為了更準(zhǔn)確地描述分割效果的優(yōu)劣，采用IoU(intersection over union)標(biāo)準(zhǔn)對以上不同方法和本文方法進行度量，該標(biāo)準(zhǔn)用于測量實際標(biāo)簽值和預(yù)測標(biāo)簽值之間的相關(guān)度，相關(guān)度越高，度量值越高，分割效果越好，對比結(jié)果見表2。對比結(jié)果表明，本文方法對飛機，椅子，汽車，吉他等三維點云模型都有較好的分割結(jié)果。

圖6 O-CNN(6)分割結(jié)果(a)與本文結(jié)果(b)對比

5 結(jié)束語

本文針對三維點云數(shù)據(jù)的計算量大以及存儲成本高的問題，使用八叉樹數(shù)據(jù)結(jié)構(gòu)表示三維點云模型，同時為了避免顯式的特征提取帶來的局限性，使用兩種基礎(chǔ)特征相融合作為卷積神經(jīng)網(wǎng)絡(luò)的輸入特征，利用卷積神經(jīng)網(wǎng)絡(luò)級聯(lián)反卷積神經(jīng)網(wǎng)絡(luò)對三維點云模型進行分割，實現(xiàn)了分割結(jié)果可視化，提高了實驗數(shù)據(jù)集中大多數(shù)類別的分割準(zhǔn)確率。但是由于使用八叉樹結(jié)構(gòu)表示點云模型，對于部分類的分割結(jié)果的分割區(qū)域之間存在噪聲，模型邊界處鋸齒狀明顯，在分割可視化時部分模型效果欠佳。其次由于數(shù)據(jù)量不同以及在訓(xùn)練過程中存在擬合問題使各類點云的預(yù)測標(biāo)簽存在誤差，需要進一步研究處理。

表2 以IoU為評價度量的對比結(jié)果