羊 发自 凹非寺
量子位 报道 | 公众号 QbitAI

画数学插图令人头秃？

现在，CMU的研究人员们开发出了一款实用工具Penrose：

以纯文本的方式输入，根据语言描述，就能自动生成数学图表。

集合论：

几何：

线性代数：

光线追踪：

都不在话下。

整个过程，不需要手动进行繁琐调整，只需在软件中用编程语言的方式，描述数学表达式。

并且，这些表达式不仅限于基本功能，而是可以表达任何数学领域的复杂关系。

这一研究成果，入选计算机图形学顶会SIGGRAPH 2020。

在GitHub上，也得到了3500标星，登上热榜。

有网友认为：Penrose，就像是科学图表中LaTeX。

纯文本绘制数学图表

用LaTeX编辑数学公式的快乐，谁用谁知道。

那么Penrose具体是怎么绘制出数学图表的呢？

比如，要画出这样一个集合关系：

在软件界面中，完成这样的输入就能自动生成：

如果对配色、布局不满意，点击「resample」，系统会提供其他不同的选择：

也可以自己手动在「sty」文件中进行调整：

研究人员还提到，该系统支持与基于Web的应用程序集成。并且，Penrose IDE能够提供自动语法高亮和自动补全功能。

不过，目前Penrose尚处在初期版本，未向公众开放。研发团队表示，他们正在快马加鞭，希望能尽快上线公开版本。

数学符号如何变成精美图表？

作者之一、CMU计算机科学和机器人学助理教授Keenan Crane表示，他们打造Penrose的目的，是让所有人都能拥有数学家一般，绘制漂亮图表的能力。

为了实现这一目标，Penrose围绕两个设计原则来实现：

• 通过从数学符号到视觉图标的映射来规定图表；
• 通过求解相关有约束的优化问题来合成图表。

第一步，是用编程语言来规定数学对象及其可视化表示。

具体而言分为三个部分：

• Substance：类似于HTML，用来指定内容。
• Style：类似于CSS，用于调整外观和可视化表示。
• Domain：声明数学领域中可用的对象、关系和符号。

需要说明的是，这并不意味着用户想要上手Penrose，必须学会三种语言。

实际上，大多数用户只要掌握Substance语言，类似这样：

Set A,B
intersecting(A,B)
set C := intersection(A,B)
Label A $\text{Circles}$
Label B $\text{Diagrams}$
Label C $\text{Venn Diagrams}$

Domain和Style就交给专业人士，要用的时候调用软件包就行了。

第二步，使用约束性优化来合成满足给定规范的图。

该方法主要受到手绘图的启发。

3500星，登上GitHub热榜

Penrose展现的效果，得到了网友们的点赞。

目前，Penrose的GitHub已经有3500标星，在Hacker News上也有399的热度。

有网友认为，想要理解数学概念，可视化是非常重要的手段，而Penrose可能会给数学教育带来很大的帮助。

还有网友表示，希望几何绘图软件Geogebra能集成这一功能。

不过，也有网友指出，简单的示例说明了系统的思想，但还是希望看到Penrose实现的更为复杂的数学概念可视化，以证明其确实可以表达数学领域的复杂关系。

传送门

论文地址：http://penrose.ink/media/Penrose_SIGGRAPH2020.pdf

GitHub地址：https://github.com/penrose/penrose

官网：http://www.penrose.ink/

— 完 —

量子位 QbitAI · 头条号签约作者

关注我们，第一时间获知前沿科技动态

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

从“三维去噪”谈起

问题缘起

关于三维网格去噪或点云去噪的问题，图形学的初学者一定不会陌生。举一个例子，利用微软的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二代这样飞时测距的设备，光线由于物体几何形状不同可以产生多次反射，从而造成全局位置偏差。我们的算法并不能很好地去除这样的偏差。是否可以从数据中挖掘其中的规律，还是一个值得探讨的问题，欢迎大家在文章下方留言与我们交流探讨。

附录：

[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。微软小冰进驻微软研究院微信啦！快去主页和她聊聊天吧。