以數據的名義——淺談三維幾何的處理與分析（下）

編者按：在「以數據的名義——淺談三維幾何的處理與分析（上）」中，微軟亞洲研究院主管研究員劉洋探討了三維幾何處理中的去噪問題。今天，我們繼續分享網路圖形組在三維幾何處理領域的研究工作——如何利用卷積神經網路高效處理三維數據。

邁向三維理解的階梯：三維深度學習

從感知到理解、從理解到改變，人類時時刻刻都在與身邊的物理世界發生互動。聲、光、色、觸覺、味覺等感知信號輔助人類認知這個世界。在計算機視覺領域裡，人們通過分析大量的圖像數據來幫助機器理解世界；在語音信號處理領域裡，人們藉助機器學習從大量的語音數據中解析語言的魅力。隨著三維數據的日益增多，讓機器通過分析三維數據來理解物理世界也方興未艾，優秀的工作也層出不窮。 其中做為三維理解的第一步，人們希望能從數據中學習三維形體空間。

簡而言之，我們希望理解同類形體的共性、異類物體的差異、為什麼「椅子是椅子、桌子是桌子」、三維世界有什麼、現在發生了什麼、將會有什麼發生。傳統的三維形狀理解一般依靠規則、根據固定模式、藉助具體特徵，但是隨著三維數據種類和數量的增多，這類理解方案變得低效和不準確，對人為定義特徵的依賴也導致已有方案在大數據面前捉襟見肘。而隨著深度學習尤其是卷積神經網路（CNN）這一利器在各領域裡的卓越表現，如何將CNN運用到三維數據上成為計算機視覺和圖形學一個焦點課題。

形狀空間與3Ｄ CNN

三維形狀在數字世界裡可以有不同的表達，如三角網格、點雲、體素、參數曲面、隱式曲面等。不同的表達和CNN也有著不同的結合方式。有的方法將網格參數化到二維空間，在二維空間編碼幾何特徵，並利用CNN在二維定義域上類似圖像空間進行卷積；有的將曲面局部處理成測地圓盤域並在其上編碼幾何信號，然後在圓盤上進行CNN卷積；也有的以三維空間的體素作為定義域，示性函數作為信號（即物體形狀內部信號編碼為1，外部為0）進行3D卷積，將CNN直接拓展到三維空間；還有一大類方法是利用空間投影將物體變為多個視圖下的二維影像，然後當作圖像來處理。在近年的視覺、機器學習、計算機圖形學的會議上，如CVPR/ICCV/NIPS/SIGGRAPH，針對三維形狀的深度學習網路已開始大放光彩。但這些方法各有利弊，對輸入也各有不同的要求。

我們希望發明一個對輸入魯棒（如不對形狀拓撲、曲面光滑程度、物體可見範圍等做過多假設）的三維CNN網路，用來處理紛雜的三維數據。這裡面最接近我們期望的就是基於體素的3D CNN。基於體素的3D CNN是圖像空間CNN的自然推廣，然而從二維推廣到三維，CNN涉及的離散元素（2D是像素，3D是體素）個數是空間格點解析度的三次方，即。龐大的存儲量和計算量讓基於體素的3D CNN畏足於高解析度，徘徊於這樣低解析度的數據中，使得該方法在眾多的三維學習任務中飲恨敗北。

突破口之一：八叉樹的稀疏表達與面向CNN的高效訪問

如何提升基於體素的3D CNN的能力？我們依舊讓數據說話。

和圖像空間不同，三維形狀只佔其所在三維空間的一小部分，大部分三維區域是空的。用空間中所有體素來表達形體，無疑是非常浪費存儲的。一個自然的想法是，利用自適應的空間剖分來壓縮存儲，八叉樹顯然是個非常好的選擇。在指定最大深度的情況下，三維空間根據是否含有三維形狀的一部分來決定是否一分為八，並在子塊里重複這樣的劃分。八叉樹的最深葉節點可以存儲三維形狀的信息。在我們的實現中，這些葉節點只需存儲所含區域的平均法向，並且它們的數目也只是。這樣的存儲方式不受形狀表達的限制，網格、曲面、點雲等都可以輕鬆存儲。

傳統八叉樹的實現是構建標準的樹型結構，其訪問周邊鄰居的效率並不高。而在CNN計算中，經常要大量訪問周邊鄰居來做卷積運算。為此，我們構造了一種高效的八叉樹結構並在GPU上高效實現：八叉樹的每一層由一個排序過的散亂鍵數組、一個標記非空節點序號的數組組成。訪問節點鄰居可以通過這些數組快速獲得，並支持高效訪問所有同父節點的鄰居。這一實現非常利於CNN計算，並且數據的下採樣也非常便捷。 在下圖中我們用二維的四叉樹來闡述我們的數據結構。

圖一：O-CNN數據結構。圖(a)中紅色部分表示一個二維形狀，l=0,1,2表示了不同深度下四叉樹，每個節點的標號用排序過的散亂鍵標定並記在數組裡 (圖(b))，每一層非空節點的序號（從1開始計數，0表示空節點））由數組存儲(圖(c))。在四叉樹每一層都存儲CNN網路的特徵數組，和相對應，比如。當下採樣發生的時候，如在上，四個同父的子節點通過可以迅速把採樣結果放在中父節點所對應的位置。

突破口之二：限制在八叉樹節點的CNN計算

圖像域上每一像素都含有具體信息，都會經歷CNN的計算，如卷積、池化。而在三維空間中，並不是每個體素都含有三維形體信息。我們認為，盲目地對所有體素做CNN計算是得不償失的。為此，我們提出只在八叉樹節點上進行CNN運算，這樣的方式有以下三個好處。

存儲優勢：由於卷積計算限制在八叉樹節點上，多次卷積也不會擴張卷積的計算區域，從而保證了計算量只和八叉樹節點數目相關。而已有的一些基於稀疏存儲的CNN的工作在多次卷積後會將整個空間佔據，變得低效且無法處理高解析度。

計算高效：八叉樹的層次結構和便捷的數據組織使得卷積、反卷積、池化、反池化操作與八叉樹高效結合。比如，常見池化操作就是把一個父節點的所有子節點的信息降採樣到該父節點上。

信息傳播優勢：我們限定卷積計算只在八叉樹節點上發生，實際上是隱式地將網路信息在形狀表面上傳播，從而可以更高效地交換和共享信息。基於全空間體素的3D CNN將信息在整個空間傳播，信息流動的效率慢，很多含零信號的區域並不能貢獻有效信息。從另一方面看，我們的限定計算也和多視角CNN、基於流形的CNN思想不謀而合：CNN計算都在形狀表面發生。雖然目前我們還缺乏理論上對這一優勢的嚴密分析，但我們的實驗已經很好地體現這方面的優勢。

基於八叉樹的卷積神經網路（O-CNN）

基於高效的八叉樹和限定CNN計算思想，我們提出了一個基於八叉樹的卷積神經網路（O-CNN）。為了體現我們方法的優越性，並盡量避免不同網路結構所帶來的優劣難以做公正的評價，我們只用常見的卷積和池化層來構造網路。把卷積+BN+ReLU+池化看作一個構建單元並記作（如果卷積是應用在八叉樹的第l層）。O-CNN的前端構造如下：。為了使得不同八叉樹結構在最後具有相同長度的特徵，我們對所有八叉樹的第二層空節點補零填滿。 基於這個前端(見下圖)，我們開發了完整的O-CNN網路，用在形狀識別、檢索、分割等三維分析的任務上。

圖二： O-CNN 前端

牛刀小試

我們首先在Princeton ModelNet40數據集上測試O-CNN的形狀識別能力。該數據集含有標定物體類別的40類三維數據，共含12311個CAD模型。我們利用這個數據集訓練並測試了六個O-CNN網路：O-CNN(3)、O-CNN(4)、O-CNN(5)、O-CNN(6)、O-CNN(7)、O-CNN(8)。其中的數字表示所用八叉樹的最大深度，即這個六個網路所用的最大空間解析度為。下表展現了這六個網路以及其他一些深度學習網路在ModelNet40上的識別率。從中可以看出，在同等解析度下，O-CNN明顯優於其他方法。值得一提的是，在低解析度下，我們的O-CNN(3)和O-CNN(4)也表現不俗。O-CNN(7)和O-CNN(8)稍遜於O-CNN(6)，這主要是由於ModelNet40的數據量不足以很好地訓練這些相對深的網路。

我們也在ModelNet40數據集上測評了O-CNN在不同解析度下（即八叉樹最大深度）的顯存開銷以及運算時間，並和基於全部體素的3D CNN做了對比。實驗中我們使用了一塊 GeForce 1080 GPU (8GB顯存），網路的minibatch大小為32。下表是各個網路的內存開銷。

O-CNN網路平均一個前向和反向運算時間見下表。

由此可見，O-CNN的內存佔用和計算時間明顯佔優，尤其在高解析度下得到充分體現。

在形狀檢索任務中，我們和SHREC16比賽中的各個方法也做了對比。在ShapeNet55 Core數據集上，我們測評了O-CNN(5)和O-CNN(6)，O-CNN(5)和其他方法中最好的結果類似，O-CNN(6)在各項測評指標上有明顯優勢。圖三中展示了一些檢索結果。

圖三： O-CNN(6) 的形狀檢索結果。

在形狀分割任務中（其中需要反卷積和反池化操作），O-CNN(6)也取得非常好的成績 （下表中對比了我們方法和其他方法的結果，黑體標示最好的指標）。 限於篇幅，感興趣的讀者可以閱讀我們即將發表在Siggraph2017上的文章[2]。

表一： 形狀分割對比結果。比較指標為分類結果的IoU。

O-CNN在三維分析任務中的優良表現讓我們更有信心在未來研究工作中繼續探索O-CNN的其他任務能力，如「以數據的名義——淺談三維幾何的處理與分析（上）」中提到的去噪、形狀對應、形狀補全、形狀生成、場景理解等範疇更廣、粒度更細的三維分析與理解的任務。

結語

紛繁蕪雜的三維數據構建了多姿多彩的三維幾何世界，如何整合數據的力量、結合機器學習與圖形學知識來認識三維世界是我們研究的重點方向。我們將沿著這一方向繼續前行！也期望看到更多年輕學子和研究學者加入到這一充滿活力的前沿領域。

附錄：感興趣的讀者可以深入閱讀我們近期的工作成果並嘗試我們的方法。

[1]:Peng-Shuai Wang, Yang Liu and Xin Tong: Mesh Denoising via Cascaded Normal Regression, ACM Transactions on Graphics (Siggraph Asia 2016), 35(6).

Project webpage: http://wang-ps.github.io/denoising.html

[2]:Peng-Shuai Wang, Yang Liu, Yu-Xiao Guo, Chun-Yu Sun and Xin Tong: O-CNN: Octree-based Convolutional Neural Networks for 3D Shape Analysis, accepted to ACM Transactions on Graphics (Siggraph Asia 2017), 36(4).

Project webpage: http://wang-ps.github.io/O-CNN.html

作者簡介

劉洋，微軟亞洲研究院主管研究員。2000年和2003年於中國科學技術大學數學系獲得理學學士及碩士學位。2008年於香港大學計算機系獲得博士學位。2008年至2010年於法國INRIA/LORIA研究所從事博士後工作。2010年至今工作於微軟亞洲研究院網路圖形組。研究興趣包括幾何建模與處理、計算機圖形學、CAGD、建築幾何等方向。

在高水平學術會議和期刊上發表論文五十餘篇，在多個國際圖形學會議上擔任或曾擔任程序委員會委員，如SiggraphAsia 2014、Symposium on Geometry Processing(2014-2016)、Pacific Graphics(2013-2017)、Geometric Modeling and Processing(2014-2017)等。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！