以数据的名义——浅谈三维几何的处理与分析（上）
分析与处理三维形体是计算机图形学中的一个基本任务与研究方向。近年来随着三维数据获取的便捷和三维数据集的迅猛增长，这个研究方向也面临新的挑战和契机。一方面，在新的数据形势下，传统算法的一些前提假设不再成立，研发新型算法的需求迫在眉睫。另一方面，大数据的出现，可以使得传统的三维分析和机器学习更加有机地结合起来，从而帮助人们加深对三维世界的认知，有效地理解现实三维几何世界并构建虚拟数字世界。结合近期微软亚洲研究院网络图形组在这方面的一些工作，刘洋博士在文中分享了数据在三维几何处理与分析的作用与效力。本文是该系列文章的上篇，主要介绍了三维几何处理中的去噪问题。
从“三维去噪”谈起
问题缘起
关于三维网格去噪或点云去噪的问题，图形学的初学者一定不会陌生。举一个例子，利用微软的Kinect设备扫描三维物体（图一(a)），我们可以获得三维网格（图一(b)）。但由于Kinect设备的低精度，三维网格存在着大量的噪声。去除这些噪声并尽量恢复物体的原貌（如图一(c)）就是三维去噪需要解决的问题。从简单的拉普拉斯平滑到复杂点的谱分析去噪，从热门的
图 一：三维网格去噪
三维去噪问题的前生今世
在回答上述具体问题之前，我们先从一个更大的范畴来考察三维去噪问题。 首先我们做了一个有意思的文献调研，看看这些年有多少在这方面的研究成果。我们在文献搜索引擎上以“点云去噪”、“点云平滑”、“网格去噪”、“网格平滑”、“曲面去噪”、“曲面平滑”等关键词联合搜索近三十年的相关文献。得到的文献数目相当惊人—— 超过一万篇。虽然其中一部分文献弱相关，但该数目也反映了去噪问题的重要性及其在实际中的需求。我们对文献数目和文献年份也做了一个简单的分析（见下图），可以看到相关文献呈递增趋势。这一方面与三维扫描、游戏、虚拟现实、增强现实的发展有关，另一方面也说明去噪问题还没有完美的解决方案。
去噪问题难在何处？我们对该问题有以下几点认识：
● 去噪问题本质上是求解一个病态的逆问题：在噪声的类型和程度未知、真实模型的几何特性未知的前提下，如果要把噪声从输入中完美剥离，必然需要引入各种假设来辅助求解。
● 很多去噪算法对真实物体的几何特性做了很强的假设，比如曲面是
● 众多算法显式或隐含地对噪声模型做了假设，这些模型基本以高斯噪声为主，更广义一点，算法假设噪声是独立同分布。然而真实噪声的成因复杂，这些假设在很多情况下并不成立。针对高斯噪声的去噪方法在实际中也表现一般。
● 很多算法的机理和评测是有缺陷的，呈现理论和实际脱节的情况。以三角网格曲面去噪为例，很多算法在已知网格上加若干噪声，然后用去噪结果和已知曲面的差异来比较算法的优劣。这些算法有两大缺陷：（1）噪声类型人为给定，与真实不符。（2）已知网格和加噪网格共享相同的网格连接关系，与真实情况不符。如无视这些缺陷，就无助于解决真实去噪问题。
● 实用中各个算法的参数需要人为调配，根据不同输入反复尝试。对于用户而言，调参显然是一门痛苦且颇具经验色彩的苦力活。
让数据说话
不同采集设备由于精度和三维数据获取方式的差异会导致数据噪声的不同（比如Kinect一代和二代的噪声迥异），噪声在相异几何特征和不同物体材质上的表现也会有所不同。真实噪声是与数据以及设备相关的，简单的噪声模型不可能刻画出真实的噪声。因此，我们提出用数据驱动的方式来学习噪声和数据的关系，从而帮助解决去噪这一问题。
众所周知，数据驱动不能盲目地进行，数据本身要有内在并自洽的联系。在假定了三维数据获取方式的一致性、物体材质的相似性之后，我们认为符合这些前提获取的数据集可以用来揭示其中噪声的特点，并有效地帮助去除这类数据的噪声。
算法概略
我们对无噪声三维曲面做一个合理的假设：曲面局部光滑并且任意一点的法方向
描述子。注意到双边法向滤波算子具有一定的抗噪性，我们提出整合不同参数下的双边法向滤波算子来构造上述的特征描述子，并称之为“法方向描述子”(FND)。FND在不同噪声下具有很好的抗噪性，并且可以用来区分不同的几何特征。下图是我们用FND来聚类噪声曲面的面片（每一类用不同颜色绘制）。可以看到，具有不同几何特征的噪声区域被明显地区分开来，在不同噪声下（高斯噪声、均匀噪声）划分也具有比较一致的相似性。
级联回归网络。 在给定无噪声曲面和其对应的含噪声曲面数据下，我们通过构造一个简单的神经网络来寻找
去噪实战
我们的算法在人工合成的噪声数据和真实扫描数据上都表现卓越。比起现有的去噪算法以及它们最佳的参数搭配，在质量和速度上都有很大程度的提高。下图中展示的是我们使用的真实三维物体（树脂石膏材料）。我们用高精度的三维扫描仪获取这些雕像的真实几何模型并当作无噪声数据（groundtruth）。
我们准备了三种噪声数据：1.利用 Kinect 一代的单帧深度数据构成的三角网格；2. 利用Kinect 二代的单帧深度数据构成的三角网格；3. 利用Kinect Fusion 技术重构的三角网格。前面提到，噪声跟数据、设备都相关，因此对于这三个来源不同的数据，我们分别训练不同的级联回归网络用来去噪。以下各图展示了典型的噪声数据和它们对应的无噪声数据。
我们的算法可以很好地针对以上数据去噪。以下各图展示了我们的算法在这三类数据的测试集上的表现。左右两端分别是噪声数据和真实数据。可以看到与其他算法（双边法向滤波bilateral normal、引导法向滤波 guided normal、
Kinect V1 数据上的去噪比较结果
KinectV2 数据上的去噪比较结果
KinectFusion 数据上的去噪比较结果
小结
从数据中学习噪声与三维数据之间的复杂关系是我们去噪方法的核心思想。从这项工作中我们也认识到：忽略真实数据去研发一个放之四海而皆准的去噪算法是不可行的。既然噪声来自数据，我们就应该从数据中探究其中的奥秘。我们的工作也体现了数据的威力。感兴趣的读者不妨参考我们发表在Siggraph Asia 2016的文章[1]并试试附带的Matlab代码。
值得一提的是，我们的算法假设了物体某点噪声只和该点附近区域的数据相关。这个局部相关的假设并不总是成立。比如Kinect二代这样飞时测距的设备，光线由于物体几何形状不同可以产生多次反射，从而造成全局位置偏差。我们的算法并不能很好地去除这样的偏差。是否可以从数据中挖掘其中的规律，还是一个值得探讨的问题，欢迎大家在文章下方留言与我们交流探讨。
附录：
[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 (点击阅读原文，访问项目主页)
注：在下篇中，刘洋博士将继续分享网络图形组在三维几何处理领域的研究工作 – 如何利用卷积神经网络高效处理三维数据，敬请期待。
刘洋，微软亚洲研究院主管研究员。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。