以数据的名义——浅谈三维几何的处理与分析（上）

分析与处理三维形体是计算机图形学中的一个基本任务与研究方向。近年来随着三维数据获取的便捷和三维数据集的迅猛增长，这个研究方向也面临新的挑战和契机。一方面，在新的数据形势下，传统算法的一些前提假设不再成立，研发新型算法的需求迫在眉睫。另一方面，大数据的出现，可以使得传统的三维分析和机器学习更加有机地结合起来，从而帮助人们加深对三维世界的认知，有效地理解现实三维几何世界并构建虚拟数字世界。结合近期微软亚洲研究院网络图形组在这方面的一些工作，刘洋博士在文中分享了数据在三维几何处理与分析的作用与效力。本文是该系列文章的上篇，主要介绍了三维几何处理中的去噪问题。

关于三维网格去噪或点云去噪的问题，图形学的初学者一定不会陌生。举一个例子，利用微软的Kinect设备扫描三维物体（图一(a)），我们可以获得三维网格（图一(b)）。但由于Kinect设备的低精度，三维网格存在着大量的噪声。去除这些噪声并尽量恢复物体的原貌（如图一(c)）就是三维去噪需要解决的问题。从简单的拉普拉斯平滑到复杂点的谱分析去噪，从热门的  平滑到便捷的双边滤波， 林林总总有非常多的算法可以使用，也有非常多的图像域上的去噪方法可以借鉴。但遗憾的是对于类似图一的噪声，已有的算法并不能很好地去除。问题出在何处？

图 一：三维网格去噪

在回答上述具体问题之前，我们先从一个更大的范畴来考察三维去噪问题。 首先我们做了一个有意思的文献调研，看看这些年有多少在这方面的研究成果。我们在文献搜索引擎上以“点云去噪”、“点云平滑”、“网格去噪”、“网格平滑”、“曲面去噪”、“曲面平滑”等关键词联合搜索近三十年的相关文献。得到的文献数目相当惊人—— 超过一万篇。虽然其中一部分文献弱相关，但该数目也反映了去噪问题的重要性及其在实际中的需求。我们对文献数目和文献年份也做了一个简单的分析（见下图），可以看到相关文献呈递增趋势。这一方面与三维扫描、游戏、虚拟现实、增强现实的发展有关，另一方面也说明去噪问题还没有完美的解决方案。

去噪问题难在何处？我们对该问题有以下几点认识：

● 去噪问题本质上是求解一个病态的逆问题：在噪声的类型和程度未知、真实模型的几何特性未知的前提下，如果要把噪声从输入中完美剥离，必然需要引入各种假设来辅助求解。

● 很多去噪算法对真实物体的几何特性做了很强的假设，比如曲面是光滑，或者曲面类似CAD模型具有分片光滑和含有大量平面的特性。 然而这一类的曲面只占三维物体类型中一小部分。

● 众多算法显式或隐含地对噪声模型做了假设，这些模型基本以高斯噪声为主，更广义一点，算法假设噪声是独立同分布。然而真实噪声的成因复杂，这些假设在很多情况下并不成立。针对高斯噪声的去噪方法在实际中也表现一般。

● 很多算法的机理和评测是有缺陷的，呈现理论和实际脱节的情况。以三角网格曲面去噪为例，很多算法在已知网格上加若干噪声，然后用去噪结果和已知曲面的差异来比较算法的优劣。这些算法有两大缺陷：（1）噪声类型人为给定，与真实不符。（2）已知网格和加噪网格共享相同的网格连接关系，与真实情况不符。如无视这些缺陷，就无助于解决真实去噪问题。

● 实用中各个算法的参数需要人为调配，根据不同输入反复尝试。对于用户而言，调参显然是一门痛苦且颇具经验色彩的苦力活。

不同采集设备由于精度和三维数据获取方式的差异会导致数据噪声的不同（比如Kinect一代和二代的噪声迥异），噪声在相异几何特征和不同物体材质上的表现也会有所不同。真实噪声是与数据以及设备相关的，简单的噪声模型不可能刻画出真实的噪声。因此，我们提出用数据驱动的方式来学习噪声和数据的关系，从而帮助解决去噪这一问题。

众所周知，数据驱动不能盲目地进行，数据本身要有内在并自洽的联系。在假定了三维数据获取方式的一致性、物体材质的相似性之后，我们认为符合这些前提获取的数据集可以用来揭示其中噪声的特点，并有效地帮助去除这类数据的噪声。 

我们对无噪声三维曲面做一个合理的假设：曲面局部光滑并且任意一点的法方向可以由其局部邻域的法方向构成的函数刻画。进一步假设局部邻域的法方向可以构造一个特征描述子  并且存在一个函数使得 。如果该特征描述子对噪声不敏感，那么在该曲面相对应的噪声曲面上，可以寻找类似的函数并使得 来近似真实的法方向（是噪声曲面上对应 的区域）。

描述子。注意到双边法向滤波算子具有一定的抗噪性，我们提出整合不同参数下的双边法向滤波算子来构造上述的特征描述子，并称之为“法方向描述子”(FND)。FND在不同噪声下具有很好的抗噪性，并且可以用来区分不同的几何特征。下图是我们用FND来聚类噪声曲面的面片（每一类用不同颜色绘制）。可以看到，具有不同几何特征的噪声区域被明显地区分开来，在不同噪声下（高斯噪声、均匀噪声）划分也具有比较一致的相似性。

级联回归网络。 在给定无噪声曲面和其对应的含噪声曲面数据下，我们通过构造一个简单的神经网络来寻找。该神经网络是一个单隐层的RBF网络，其输入是噪声数据的法方向，损失函数由和其对应的真实法方向的差异构造。为了进一步减少回归误差，我们针对由FND分类的区域分别寻找各自的。回归出来的法方向结果，用来指导噪声曲面顶点位置的更新，从而达到减少噪声的效果。注意到单隐层网络的拟合能力有限，我们利用级联的方式将当前去噪后曲面的法方向作为输入，训练新的网络降低逼近误差。我们发现，级联若干个单隐层网络可以极大程度地减少噪声并不失计算的便捷性。在实际中，三次级联就可以带来非常优秀的去噪结果。训练出来的网络在实际运用时也不再有调参之苦。

我们的算法在人工合成的噪声数据和真实扫描数据上都表现卓越。比起现有的去噪算法以及它们最佳的参数搭配，在质量和速度上都有很大程度的提高。下图中展示的是我们使用的真实三维物体（树脂石膏材料）。我们用高精度的三维扫描仪获取这些雕像的真实几何模型并当作无噪声数据（groundtruth）。

我们准备了三种噪声数据：1.利用 Kinect 一代的单帧深度数据构成的三角网格；2. 利用Kinect 二代的单帧深度数据构成的三角网格；3. 利用Kinect Fusion 技术重构的三角网格。前面提到，噪声跟数据、设备都相关，因此对于这三个来源不同的数据，我们分别训练不同的级联回归网络用来去噪。以下各图展示了典型的噪声数据和它们对应的无噪声数据。

我们的算法可以很好地针对以上数据去噪。以下各图展示了我们的算法在这三类数据的测试集上的表现。左右两端分别是噪声数据和真实数据。可以看到与其他算法（双边法向滤波bilateral normal、引导法向滤波 guided normal、 光顺等）相比，我们算法的输出更忠实于真实结果：噪声引起的曲面波动明显减少，曲面也无过分光滑和过强的剧烈变化。图下方数值表示的网格法方向与真实值的平均误差也进一步说明了我们数据驱动下的算法优越性。

Kinect  V1 数据上的去噪比较结果

KinectV2 数据上的去噪比较结果

KinectFusion 数据上的去噪比较结果

从数据中学习噪声与三维数据之间的复杂关系是我们去噪方法的核心思想。从这项工作中我们也认识到：忽略真实数据去研发一个放之四海而皆准的去噪算法是不可行的。既然噪声来自数据，我们就应该从数据中探究其中的奥秘。我们的工作也体现了数据的威力。感兴趣的读者不妨参考我们发表在Siggraph Asia 2016的文章[1]并试试附带的Matlab代码。

值得一提的是，我们的算法假设了物体某点噪声只和该点附近区域的数据相关。这个局部相关的假设并不总是成立。比如Kinect二代这样飞时测距的设备，光线由于物体几何形状不同可以产生多次反射，从而造成全局位置偏差。我们的算法并不能很好地去除这样的偏差。是否可以从数据中挖掘其中的规律，还是一个值得探讨的问题，欢迎大家在文章下方留言与我们交流探讨。

​原文链接：http://mp.weixin.qq.com/s/0o-3bG4_RwrAHnDb39bvlA