海天讲座（二）最优传输理论
图1. 最优传输理论在计算机图形学领域中的应用：怪兽模型保面积参数化。
近二十年来，计算机图形学技术取得革命性发展，游戏产业和电影工业日益蓬勃发展。在CG电影中和计算机游戏中，人物，怪兽等具有独特的表示形式，在这种内在表示形式中几何信息和纹理信息是分离的。我们可以将其比喻为灯笼的构成方式，灯笼的骨架由竹篾扎成，决定了灯笼的几何形状；灯笼的蒙皮是将棉纸糊在骨架之上，蒙皮上画上各种图案文字。如图2-4所示，我们在计算机中表示一张人脸曲面，曲面的竹篾骨架构由所谓的三角网格表示，如图2所示，三角网格决定了曲面的几何形状，但是没有颜色图案；曲面的蒙皮由标准的二维图像表示，被称作纹理图像，如图3所示；然后，我们需要将蒙皮贴在骨架上，得到带有纹理的曲面，如图4所示。相同的几何（三角网格），贴上不同的纹理图像，得到不同的视觉效果。将纹理图像贴到三角网格的过程被称为纹理贴图。等价的，将三角网格展平到纹理图像上的操作被称为参数化。
图4. 带有纹理的人脸模型，同样的几何，不同的纹理，得到不同的视觉效果。
当我们把灯笼蒙皮贴在骨架上的时候，尽量光滑熨帖，避免将蒙皮撕破或者出现皱褶，在几何上这等价于曲面参数化应该是微分同胚。同时，将平面的蒙皮贴到弯曲的骨架上，我们尽量减小蒙皮的延展拉伸。等价地，曲面参数化将弯曲的曲面映到平面上面，我们希望得到等距变换，即映射保持任意两点间的测地距离。但是，我们知道，等距变换保持高斯曲率，一般情况下，我们无法将弯曲的曲面等距地映到平面上面，几何畸变无可避免。参数化带来的畸变可以分成两种，角度畸变和面积畸变。保角映射保持角度不变，保面积映射保持面元不变，既保角又保面元的映射为等距变换。等距的参数化一般并不存在，因此在实践中，曲面参数化的目标是：或者得到保角变换，或者保面积变换，或者在二者中寻求平衡。
图5显示了人脸曲面的保角参数化结果，保角变换将曲面上无穷小圆映到平面上的无穷小圆，但是无穷小圆的面积发生变化，映射局部是相似变换。图6显示了保面元参数化的结果，人脸曲面上的无穷小椭圆映到平面的无穷小圆上，所有椭圆的面积都相等。
2000年左右，在计算机图形学领域，GPU硬件技术被发明出来，GPU的普及极大地推动了各种几何处理和物理渲染算法的发展，曲面参数化成为学界研究的热点。寻求严格而高效的算法，计算保角参数化和保面积参数化成为学界共同目标。各种保角参数化算法很快就被发明出来，但是严格意义上，保面积参数化算法的发明却被推迟了数年。简单的保角映射需要解线性偏微分方程，保面积映射需要解非线性的蒙日-安培方程，两种方法的理论难度和工程难度不可同日而语。现在回顾历史，令人感慨良多。
在丘成桐先生的指导下，基于霍奇理论，老顾当年解决了曲面整体保角参数化问题。而后，老顾一直苦苦求索保面积参数化方法。其实，丘先生在1996-1997年间向老顾传授了蒙日-安培方程的理论知识，Brenier的理论在1991年就已发表。但是，老顾学习蒙日-安培方程理论是依循凸几何的视角，特别是基于俄罗斯Minkowski学派的专著，无法将蒙日-安培方程和最优传输理论建立联系，后来没有及时跟踪这方面理论的发展，因此没有看出蒙日-安培方程就是保面积参数化问题的答案。这一耽搁，就是十年！
从另一个角度讲，不同于基础科学，计算机技术发展异常迅猛，高潮迭起，每次硬件的革命都会产生一批基本问题。很多时候，人们缺乏足够的耐心来彻底从理论上解决这些问题，而是采用工程近似方法。最为常见的工程方法就是设定一个能量，将面元畸变作为惩罚函数，然后用传统方法进行优化。这种方法理论并不严密，只能用一些数值模拟的实例来显示算法的有效性。因为没有理论证明，算法的普适性和可复制性没有保证。在基础理论领域，这种不严密性是无法被广泛接受的；在工程领域，这种方法却是被认可的。因此，在很长时间里，老顾意识到从理论上解决这个问题需要发费巨大的气力，但是工程界并不真正感激，因此缺乏动力来真正彻底解决这个问题。但是，老顾对于这种工程经验性方法一直觉得隔靴搔痒，无法释怀。依随时间的流逝，这种隐忧愈发强烈，因此最终还是追随初心，不计代价地投入进来。离散最优传输理论在【1】中总结，基于最优传输理论的保面积参数化方法发表在【2】中。
回顾这十年的经验教训，老顾觉得首先是理论基础不够扎实，虽然已经学习了蒙日-安培方程理论，但是没有将其理解透彻，没能做到融汇贯通，只看到其凸几何的源头，没有看到其最优传输方面的本质联系；其次，老顾追随潮流，没有真正静下心来解决艰深的基础问题，为了“谋生”，做了大量简单肤浅的小问题；再次，老顾没有坚持自己的价值观念，没有看到短期的工程价值不会取代长期的理论价值，没有坚持初心。值得庆幸的是十年后，这一历史遗留问题终于圆满解决。可谓：
“桃李春风一壶酒，江湖夜雨十年灯。”
图7. 胸像曲面的保角参数化。
相比于保角参数化，保面积参数化有一些独到的优势。如图7所示，保角参数化会带来面积的剧烈畸变，例如脸部的参数面积小到只有几个像素，这会为下一步操作带来强烈的数值不稳定。相反的，保面积参数化保持面元，对于任意一个曲面上的区域，其曲面面积和参数面积相等。在一些几何处理或渲染绘制的应用中有一定优势。下面，我们就保面积参数化来继续最优传输理论的讨论。
最优传输理论的一个显著优点是她广泛的普适性，无论是光滑情形还是离散情形，同样的理论框架都适用，无需做任何更改。（作为对比，对于Ricci流理论，光滑情形和离散多面体曲面，理论的语言表述截然不同。）为了计算的便利，我们在这里考察最为简单的离散情形，最优传输理论在这个框架下比较清晰明了，易于理解。
离散最优传输问题 如图9所示，定义域是平面上的单位圆盘
值域是平面上的离散点集，配有离散测度（Dirac Measure）
离散测度之和等于圆盘总面积，
我们需求圆盘的一个胞腔分解
每个胞腔被映射到离散点，
我们说这一离散映射保测度，如果每个胞腔的面积等于其像点的离散测度：
这一离散映射的传输代价定义为：
离散最优传输问题就是在所有保测度的离散映射中，寻求传输代价最小者。
离散Brenier势能函数 根据Brenier理论，最优传输映射等于某一个凸函数的梯度映射，这一凸函数被称为Briener势能函数。在离散情形，Brenier势能函数是一个分片线性函数，构造方法如下。首先，每个离散点
这里
几何上，这意味着Brenier势能函数的图（Graph）是平面族
因此，每个离散点对应着一个支撑平面，所有支撑面的上包络给出了离散Brenier势能函数，上包络向平面的投影构成了定义域的胞腔分解，每个胞腔映射到对应的离散点，这样就构成了离散Brenier势能函数的梯度映射。
我们通过调节这些平面的截距来垂直移动它们，从而改变这些支撑平面的上包络，由此调节上包络在平面上的投影，使得平面上每个胞腔
勒让德对偶 我们在这里讨论平面族上包络的计算方法，这需要应用勒让德对偶原理。假设
图11. 离散Brenier势能函数的勒让德对偶。
离散Brenier势能函数的Legendre对偶显示在图11中，每个面
对偶为一个顶点
每个顶点为三个面的交点，对偶成连接三个平面对偶顶点的三角形。因此，平面族
凸包的算法 由勒让德对偶，我们将平面族的上包络问题转换成离散点集的凸包问题。离散点集的凸包问题是传统计算几何的中心问题，存在很多成熟算法。最为简单的当属增量凸包算法（incremental convex hull）。算法梗概如下：给定点集
我们假设Brenier势能函数存在并唯一，那么由凸包算法我们可以计算平面族的上包络，从而得到单位圆盘的胞腔分解，进一步得到离散最优传输映射。
保面积参数化
如图5左帧所示，我们用三维扫描仪获取人脸曲面的采样点几何数据，再将这些采样点进行三角剖分，将人脸曲面用三角网格S来表示。首先，我们将人脸三角网格进行放缩变换，使得其总面积等于单位圆盘面积。我们用保角参数化将人脸三角网格映射到平面圆盘上，
那么复合映射
给出了从人脸曲面到单位圆盘的保面积参数化，如图6右帧所示。其他的图中保面积参数化都是基于这种算法。当采样点的密度趋于无穷时，离散保面积映射收敛到连续保面积映射。
总结
这里，我们用保面积参数化作为实例来解释离散最优传输问题的解法。所有的一切归结为如下的问题：
如图10所示，一族开放的凸多面体，每个面可以上下移动，给定一组正数
是否存在一个凸多面体，每个面的投影面积等于相应的
【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
请长按下方二维码，选择 “识别图中二维码”，即可关注。
【老顾谈几何】邀请国内国际著名纯粹数学家，应用数学家，理论物理学家和计算机科学家，讲授现代拓扑和几何的理论，算法和应用。