查看原文
其他

海天讲座(二)最优传输理论

顾险峰 老顾谈几何 2019-12-18

图1. 最优传输理论在计算机图形学领域中的应用:怪兽模型保面积参数化。


近二十年来,计算机图形学技术取得革命性发展,游戏产业和电影工业日益蓬勃发展。在CG电影中和计算机游戏中,人物,怪兽等具有独特的表示形式,在这种内在表示形式中几何信息纹理信息是分离的。我们可以将其比喻为灯笼的构成方式,灯笼的骨架由竹篾扎成,决定了灯笼的几何形状;灯笼的蒙皮是将棉纸糊在骨架之上,蒙皮上画上各种图案文字。如图2-4所示,我们在计算机中表示一张人脸曲面,曲面的竹篾骨架构由所谓的三角网格表示,如图2所示,三角网格决定了曲面的几何形状,但是没有颜色图案;曲面的蒙皮由标准的二维图像表示,被称作纹理图像,如图3所示;然后,我们需要将蒙皮贴在骨架上,得到带有纹理的曲面,如图4所示。相同的几何(三角网格),贴上不同的纹理图像,得到不同的视觉效果。将纹理图像贴到三角网格的过程被称为纹理贴图。等价的,将三角网格展平到纹理图像上的操作被称为参数化。


图2. 人脸曲面的几何模型。
图3. 人脸模型的纹理图像。


图4. 带有纹理的人脸模型,同样的几何,不同的纹理,得到不同的视觉效果。


当我们把灯笼蒙皮贴在骨架上的时候,尽量光滑熨帖,避免将蒙皮撕破或者出现皱褶,在几何上这等价于曲面参数化应该是微分同胚。同时,将平面的蒙皮贴到弯曲的骨架上,我们尽量减小蒙皮的延展拉伸。等价地,曲面参数化将弯曲的曲面映到平面上面,我们希望得到等距变换,即映射保持任意两点间的测地距离。但是,我们知道,等距变换保持高斯曲率,一般情况下,我们无法将弯曲的曲面等距地映到平面上面,几何畸变无可避免。参数化带来的畸变可以分成两种,角度畸变和面积畸变。保角映射保持角度不变,保面积映射保持面元不变,既保角又保面元的映射为等距变换。等距的参数化一般并不存在,因此在实践中,曲面参数化的目标是:或者得到保角变换,或者保面积变换,或者在二者中寻求平衡


图5显示了人脸曲面的保角参数化结果,保角变换将曲面上无穷小圆映到平面上的无穷小圆,但是无穷小圆的面积发生变化,映射局部是相似变换。图6显示了保面元参数化的结果,人脸曲面上的无穷小椭圆映到平面的无穷小圆上,所有椭圆的面积都相等。



图5. 保角参数化。




图6. 保面积(保面元)参数化。


2000年左右,在计算机图形学领域,GPU硬件技术被发明出来,GPU的普及极大地推动了各种几何处理和物理渲染算法的发展,曲面参数化成为学界研究的热点。寻求严格而高效的算法,计算保角参数化和保面积参数化成为学界共同目标。各种保角参数化算法很快就被发明出来,但是严格意义上,保面积参数化算法的发明却被推迟了数年。简单的保角映射需要解线性偏微分方程,保面积映射需要解非线性的蒙日-安培方程,两种方法的理论难度和工程难度不可同日而语。现在回顾历史,令人感慨良多。


在丘成桐先生的指导下,基于霍奇理论,老顾当年解决了曲面整体保角参数化问题。而后,老顾一直苦苦求索保面积参数化方法。其实,丘先生在1996-1997年间向老顾传授了蒙日-安培方程的理论知识,Brenier的理论在1991年就已发表。但是,老顾学习蒙日-安培方程理论是依循凸几何的视角,特别是基于俄罗斯Minkowski学派的专著,无法将蒙日-安培方程和最优传输理论建立联系,后来没有及时跟踪这方面理论的发展,因此没有看出蒙日-安培方程就是保面积参数化问题的答案。这一耽搁,就是十年!


从另一个角度讲,不同于基础科学,计算机技术发展异常迅猛,高潮迭起,每次硬件的革命都会产生一批基本问题。很多时候,人们缺乏足够的耐心来彻底从理论上解决这些问题,而是采用工程近似方法。最为常见的工程方法就是设定一个能量,将面元畸变作为惩罚函数,然后用传统方法进行优化。这种方法理论并不严密,只能用一些数值模拟的实例来显示算法的有效性。因为没有理论证明,算法的普适性和可复制性没有保证。在基础理论领域,这种不严密性是无法被广泛接受的;在工程领域,这种方法却是被认可的。因此,在很长时间里,老顾意识到从理论上解决这个问题需要发费巨大的气力,但是工程界并不真正感激,因此缺乏动力来真正彻底解决这个问题。但是,老顾对于这种工程经验性方法一直觉得隔靴搔痒,无法释怀。依随时间的流逝,这种隐忧愈发强烈,因此最终还是追随初心,不计代价地投入进来。离散最优传输理论在【1】中总结,基于最优传输理论的保面积参数化方法发表在【2】中。


回顾这十年的经验教训,老顾觉得首先是理论基础不够扎实,虽然已经学习了蒙日-安培方程理论,但是没有将其理解透彻,没能做到融汇贯通,只看到其凸几何的源头,没有看到其最优传输方面的本质联系;其次,老顾追随潮流,没有真正静下心来解决艰深的基础问题,为了“谋生”,做了大量简单肤浅的小问题;再次,老顾没有坚持自己的价值观念,没有看到短期的工程价值不会取代长期的理论价值,没有坚持初心。值得庆幸的是十年后,这一历史遗留问题终于圆满解决。可谓:


“桃李春风一壶酒,江湖夜雨十年灯。”




图7. 胸像曲面的保角参数化。



图8. 胸像曲面的保面积参数化。


相比于保角参数化,保面积参数化有一些独到的优势。如图7所示,保角参数化会带来面积的剧烈畸变,例如脸部的参数面积小到只有几个像素,这会为下一步操作带来强烈的数值不稳定。相反的,保面积参数化保持面元,对于任意一个曲面上的区域,其曲面面积和参数面积相等。在一些几何处理或渲染绘制的应用中有一定优势。下面,我们就保面积参数化来继续最优传输理论的讨论。


最优传输理论的一个显著优点是她广泛的普适性,无论是光滑情形还是离散情形,同样的理论框架都适用,无需做任何更改。(作为对比,对于Ricci流理论,光滑情形和离散多面体曲面,理论的语言表述截然不同。)为了计算的便利,我们在这里考察最为简单的离散情形,最优传输理论在这个框架下比较清晰明了,易于理解。



图9. 离散最优传输问题。


离散最优传输问题 如图9所示,定义域是平面上的单位圆盘

值域是平面上的离散点集,配有离散测度(Dirac Measure)

,

离散测度之和等于圆盘总面积,

我们需求圆盘的一个胞腔分解

每个胞腔被映射到离散点,

我们说这一离散映射保测度,如果每个胞腔的面积等于其像点的离散测度:

这一离散映射的传输代价定义为:

离散最优传输问题就是在所有保测度的离散映射中,寻求传输代价最小者


离散Brenier势能函数 根据Brenier理论,最优传输映射等于某一个凸函数的梯度映射,这一凸函数被称为Briener势能函数。在离散情形,Brenier势能函数是一个分片线性函数,构造方法如下。首先,每个离散点对应一个线性函数,亦即平面方程:

这里分别是平面方程的梯度和截距。Brenier势能函数定义为

几何上,这意味着Brenier势能函数的图(Graph)是平面族上包络(Upper Envelope),如图10所示。平面族的上包络构成一个开放的凸多面体,这些平面构成凸多面体的支撑平面,每个支撑平面和凸多面体的交集是多面体的一个面。所有面的集合记为。每个面在平面上的投影和单位圆盘的交集为胞腔,Brenier势能函数在胞腔上的限制为线性函数,其梯度为离散点。因此,Brenier势能函数的梯度映射为:


因此,每个离散点对应着一个支撑平面,所有支撑面的上包络给出了离散Brenier势能函数,上包络向平面的投影构成了定义域的胞腔分解,每个胞腔映射到对应的离散点,这样就构成了离散Brenier势能函数的梯度映射。


图10 离散Brenier势能函数。



我们通过调节这些平面的截距来垂直移动它们,从而改变这些支撑平面的上包络,由此调节上包络在平面上的投影,使得平面上每个胞腔的面积等于。这时,根据Brenier定理,离散映射就是离散最优传输映射。那么,这种上包络是否存在?如果存在,是否唯一?如果既存在,又唯一,那么如何找到这一最优的截距?我们会在下一章节给出这些问题的解答。


勒让德对偶 我们在这里讨论平面族上包络的计算方法,这需要应用勒让德对偶原理。假设是一个函数,其勒让德对偶(Legendre Dual)定义为


图11. 离散Brenier势能函数的勒让德对偶。


离散Brenier势能函数的Legendre对偶显示在图11中,每个面

对偶为一个顶点

每个顶点为三个面的交点,对偶成连接三个平面对偶顶点的三角形。因此,平面族的上包络(upper envelope)对偶成点集的凸包(convex hull)。Brener势能函数在平面上的投影构成胞腔分解,其对偶函数在平面上的投影构成胞腔分解的对偶三角剖分,三角剖分以离散点集为顶点集合。



凸包的算法 由勒让德对偶,我们将平面族的上包络问题转换成离散点集的凸包问题。离散点集的凸包问题是传统计算几何的中心问题,存在很多成熟算法。最为简单的当属增量凸包算法(incremental convex hull)。算法梗概如下:给定点集,我们首先用前4个点构成一个四面体,法向量指向外部,作为初始的凸包;然后每一步,我们选取下一个新点,将眼睛放在处,望向当前的凸包。当前凸包上的一些面能够被看到,另外一些面无法被看到。去掉能够被看到的面,留下看不到的面,这两张面之间的分界线被称为凸包的轮廓线。我们将轮廓线上的每条边和新点构成一个三角形,这样就得到了扩大的凸包。重复这一步骤,直至穷尽P中的所有点。最终得到的凸包即为所求结果。


我们假设Brenier势能函数存在并唯一,那么由凸包算法我们可以计算平面族的上包络,从而得到单位圆盘的胞腔分解,进一步得到离散最优传输映射。


保面积参数化

如图5左帧所示,我们用三维扫描仪获取人脸曲面的采样点几何数据,再将这些采样点进行三角剖分,将人脸曲面用三角网格S来表示。首先,我们将人脸三角网格进行放缩变换,使得其总面积等于单位圆盘面积。我们用保角参数化将人脸三角网格映射到平面圆盘上,,如图5右帧所示。人脸三角网格上每个顶点和多个三角形相邻,我们将这些三角形在中人脸曲面上的总面积的三分之一设为的测度。然后我们计算离散最优传输映射

那么复合映射 


给出了从人脸曲面到单位圆盘的保面积参数化,如图6右帧所示。其他的图中保面积参数化都是基于这种算法。当采样点的密度趋于无穷时,离散保面积映射收敛到连续保面积映射。


总结


这里,我们用保面积参数化作为实例来解释离散最优传输问题的解法。所有的一切归结为如下的问题:


如图10所示,一族开放的凸多面体,每个面可以上下移动,给定一组正数

是否存在一个凸多面体,每个面的投影面积等于相应的?这正是凸几何中经典的Alexandrov问题。我们将会在下一章节给出具体的理论和算法来解决这一问题,并由此建立凸几何与最优传输理论的内在联系。



【1】X. Gu, F. Luo, J. Sun and S-T Yau, Variational Principles forMinkowski
Type Problems, Discrete Optimal Transport, and Discrete Monge-Ampere
Equations, arXiv:1302.5472v1, 2013.


【2】X. Zhao, Z. Su, X. Gu, A. Kaufman, J. Sun, J. Gao, F. Luo, Area-preservation Mapping using Optimal Mass Transport, IEEE Transaction on Visualization and Computer Graphics, IEEE TVCG, 2013.



【本文博客版本】http://blog.sciencenet.cn/blog-2472277-952296.html



请长按下方二维码,选择 “识别图中二维码”即可关注。


【老顾谈几何】邀请国内国际著名纯粹数学家,应用数学家,理论物理学家和计算机科学家,讲授现代拓扑和几何的理论,算法和应用。





    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存