三维几何变换图（以数据的名义浅谈三维几何的处理与分析）

编者按：在“以数据的名义——浅谈三维几何的处理与分析（上）”中，微软亚洲研究院主管研究员刘洋探讨了三维几何处理中的去噪问题。今天，我们继续分享网络图形组在三维几何处理领域的研究工作——如何利用卷积神经网络高效处理三维数据。

迈向三维理解的阶梯：三维深度学习

从感知到理解、从理解到改变，人类时时刻刻都在与身边的物理世界发生互动。声、光、色、触觉、味觉等感知信号辅助人类认知这个世界。在计算机视觉领域里，人们通过分析大量的图像数据来帮助机器理解世界；在语音信号处理领域里，人们借助机器学习从大量的语音数据中解析语言的魅力。随着三维数据的日益增多，让机器通过分析三维数据来理解物理世界也方兴未艾，优秀的工作也层出不穷。 其中做为三维理解的第一步，人们希望能从数据中学习三维形体空间。

简而言之，我们希望理解同类形体的共性、异类物体的差异、为什么“椅子是椅子、桌子是桌子”、三维世界有什么、现在发生了什么、将会有什么发生。传统的三维形状理解一般依靠规则、根据固定模式、借助具体特征，但是随着三维数据种类和数量的增多，这类理解方案变得低效和不准确，对人为定义特征的依赖也导致已有方案在大数据面前捉襟见肘。而随着深度学习尤其是卷积神经网络（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)等。

你也许还想看：

感谢你关注“微软研究院AI头条”，我们期待你的留言和投稿，共建交流平台。来稿请寄：msraai@microsoft.com。

微软小冰进驻微软研究院微信啦！快去主页和她聊聊天吧。

,