分享

《计算共形几何》教程第一章

 九亩荷塘一书屋 2018-08-10


暑假课程预告


报告人:顾险峰  美国纽约州立大学石溪分校,哈佛大学

时间:  2018年7月8日、15日、22日、29日 每周日  14:30-16:00

地点:  清华大学近春园西楼三层报告厅

题目:  计算共形几何

直播:  online.conformalgeometry.org  




【最近老顾等人合著的汉语教程《计算共形几何》已经完成初稿。这里我们将第一章公布,其他章节会在清华暑期课程中讲授。希望大家批评指正,不吝赐教。有兴趣预定者,请联系gu@cmsa.fas.harvard.edu。】

理论简介

根据克莱因(Felix Klein)的厄尔朗根纲领(Erlangen Programm),不同的几何研究不同变换群下的不变量。在工程和医疗领域,常用的几何包括拓扑(Topology)、共形几何(Conformal Geometry)、黎曼几何(Riemannian Geometry)和曲面微分几何(Surface Differential Geometry),其对应的变换群为拓扑变换群、共形变换群、等距变换群和曲面在欧氏空间中的刚体变换群。这些变换群构成了嵌套子群序列, 刚体变换群等距变换群共形变换群拓扑同胚群。不同变换群下的不变量也可视作不同的结构,这些结构彼此构成层次关系。以嵌入在三维欧氏空间中的曲面为例,曲面具有拓扑结构,共形结构,黎曼度量结构和嵌入结构。后面的结构以前面的结构为基础,内涵逐步丰富。我们课程的核心目的就是介绍这些结构的概念,证明基本定理,给出计算这些结构的实用计算机算法


拓扑结构 给定两张曲面间的映射,如果是连续双射,则被称为是拓扑同胚,两张曲面拓扑等价,具有相同的拓扑不变量。直观上,我们说两个曲面拓扑等价,如果一个曲面可以连续变形成另外一个曲面,不发生撕破或者粘连。为了研究拓扑结构,数学上的一个通用手法就是为所研究的对象赋予不同的群,通过对群结构的分析来理解刻画抽象的对象。群的概念虽然抽象,但是群的数据结构和算法却是精确明晰的,虽然依然曲折,但是在计算机的帮助下,人类是能够把握的。因此,代数拓扑的基本思想就是将拓扑问题代数化,在拓扑空间上赋予各种代数结构,通过研究这些代数结构来探究空间的拓扑结构。例如,我们在流形上定义同伦群和同调群,希望用这些群的结构来反映流形的拓扑结构。


在将拓扑代数化的过程中,会有信息丢失,比如对于三维流形,同调群反映的信息不完全,同伦群反映的信息更多。更为严密的说法是:给定两个封闭的三维流形,如果它们拓扑同构当且仅当它们的同伦群同构。但是,相应的结论对于同调群不成立。对于不同的问题,需要选取不同的群来进行处理。例如,很多全局拓扑障碍的表述需要用到上同调类。在计算共形几何中,曲面的de Rham上同调群,调和微分形式的上同调群起到了至关重要的作用。


计算拓扑的算法复杂度很高。同伦群通常是非交换的,其计算归结为符号计算。计算一个流形的基本群(一维同伦群)是线性时间复杂度的,但是判定两个群是否同构,通常非常困难。同调群是可交换的,其计算归结为线性代数问题。但是整系数同调群计算归结为整数矩阵的Smith标准型,计算复杂度很高。


为了解决拓扑问题,代数拓扑并非唯一的选择,微分拓扑和几何拓扑会提供强有力的计算方法。例如,如果一个纽结不剪断和重新链接、可以渐变成另外一个扭结,则我们说这两个纽结彼此同痕。我们可以用代数拓扑方法来判定纽结同痕:两个纽结同痕,当且仅当它们在三维欧氏空间中的补集的同伦群同构。我们也可以用几何拓扑方法:将它们的补空间配上常曲率的黎曼度量,然后判定补空间是否等距。对于这个问题,几何拓扑的方法更加简洁直接。


共形结构 给定两张带有黎曼度量曲面间的可逆映射,如果映射诱导的拉回度量和初始度量彼此相差一个标量函数,

,

那么我们说是一个共形双射,两张曲面共形等价,具有相同的共形不变量。直观上,共形映射保持角度,所以又被称为是保角映射。


图1. 复平面上的共形映射(双全纯映射)。


图1显示了平面到自身的共形变换,换言之双全纯映射。书桌上放置一个相框。将整个办公室拍摄下来,将照片放入相框。那么,在相框中出现了次级相框,次级相框中出现三级相框。如此迭代,出现无穷级嵌套相框,这些相框的交点为一个孤立的点p。同时,整个相片和相框内的相片之间相差一个相似变换生成变换群,n取遍所有整数。那么p点是群的不动点。复平面去掉点p,在群作用下的商空间是一个拓扑环带。共形映射将拓扑环带映射到自身,得到右帧图像。封闭的相框被映射成无限的螺旋线。图像中的局部形状,例如纸兔子、大卫王头像、毕加索的“镜前少女”都被保持,同时面积发生变化。局部上看,共形映射在每一点的切空间上都是相似变换,因此保持局部形状,这是“共形”的含义。



图2. 曲面到平面区域的共形映射。



图2显示了曲面到平面区域的共形映射。大卫王头像曲面具有复杂的几何,映射到平面上之后,曲率变成零,但是眉眼鼻唇的细节,头发蜷曲的形状被保持,同时局部面积发生变化。同样,共形映射在曲面每点的切空间诱导的切映射为相似变换。


图3. 共形变换的保角性质。


图3显示了曲面到平面区域共形映射的保角性。曲面上任意两条相交曲线被共形变换映射成平面圆盘上两条相交曲线,曲面曲线的交角等于平面曲线的交角,即交角保持不变。

图4. 共形变换和拟共形变换的比较。


图4比较了共形变换和拟共形变换。我们将人脸曲面映射到平面圆盘,在平面圆盘上放置很多彼此相切的小圆,构成圆盘填充(circle packing)的模式,平面小圆被映射拉回到曲面上。上面一行显示的是共形映射,平面上的无穷小圆被映射拉回到曲面上的无穷小圆;下面一行显示的是一般的微分同胚,这里是拟共形映射,平面上的无穷小圆被映射拉回到曲面上的无穷小椭圆。由此可以看出共形映射保持无穷小圆。


图5. 封闭曲面的单值化定理。


图6. 带边曲面的单值化定理。


曲面微分几何中最为深刻而基本的定理是单值化定理。如图5所示,所有带度量的封闭紧曲面都可以共形映射到三种标准空间中的一种:球面,欧氏平面,或者双曲平面。图5中左帧显示了一个亏格为0的封闭曲面被共形映射到单位球面上,女孩雕塑的几何特征,例如眉眼发髻都被完美保留在球面像上。中帧是一个亏格为1 的小猫曲面,配上和初始度量共形等价的平直度量,得到一个平直环面,平直环面的万有覆盖曲面等距地覆盖整个欧氏平面。右帧是一个亏格为2的曲面,配上和初始度量共形等价的双曲度量,得到一个双曲曲面,其万有覆盖曲面等距地覆盖整个双曲平面。图6显示了带边界曲面的单值化。左帧是亏格为0的曲面带有多条边界,曲面可以被共形地映射到平面圆域,每条边界被映射为欧氏圆周。中帧是亏格为1的曲面,带有三条边界,周期性的映射到欧氏平面,每条边界被映射为欧氏圆周。右帧是亏格为2的曲面带有多条边界,可以被周期性地映射到双曲平面,每条边界被映成双曲圆周。


图5和图6显示了所有可能的紧曲面。单值化定理具有非常重要的理论意义和现实意义,极大地简化了很多曲面几何问题的理论证明和算法设计。计算曲面单值化是本书的核心目标之一。


单值化定理也直观地解释了曲面共形不变量。图5左帧,所有亏格为0的封闭曲面都可以共形映射到单位球面上,因此都彼此共形等价。图6左帧,亏格为0的带边界曲面都和平面圆域共形等价,因此其共形不变量由平面圆域所决定,即所有的圆心和半径。图5中帧,亏格为1 的封闭曲面都共形等价于欧氏平面模掉一个二维的欧氏平移变换群,这个平移变换群的生成元就是曲面的共形不变量。图6中帧是亏格为1的曲面带有边界,其共形不变量包括平移变换群的生成元,和所有欧氏圆的圆心和半径。图5右帧,高亏格曲面都共形等价于双曲平面模掉一个双曲刚体变换群,这个双曲刚体变换群的生成元构成了曲面的共形不变量。图6右帧,高亏格带边界曲面都共形等价于双曲平面模掉一个双曲刚体变换群然后挖掉一些双曲圆盘,曲面的共形不变量包括双曲刚体变换群的生成元,和这些双曲圆盘的圆心和半径。


黎曼几何  给定两张带有黎曼度量曲面间的可逆映射,如果映射诱导的拉回度量等于初始度量,那么我们说是一个等距双射,两张曲面等距。等距变换保持高斯曲率。


任给一个可定向的带度量曲面,任给一点,都存在p的一个邻域,在此邻域上,我们可以选择特定的局部坐标系,使得黎曼度量具有简洁的表达形式, 这样的局部坐标被称为是等温坐标。曲面上所有的等温局部坐标卡组成了曲面的共形图册,由此决定了曲面的共形结构。所以我们得到结论:黎曼度量决定了共形结构。


曲面的黎曼度量决定了高斯曲率,高斯曲率在曲面上的积分却只和曲面的拓扑有关。当我们共形变换黎曼度量时,,高斯曲率的变化满足Yamabe方程,,这里分别是诱导的高斯曲率。令等于常值,通过求解Yamabe方程,我们可以得到单值化度量。


曲面黎奇流是求解Yamabe方程强有力的方法,其关键思路是令黎曼度量依随时间演化,演化速率正比于当前的高斯曲率,,这样曲率演化遵循扩散-反应方程,在一定曲率条件下,最后收敛到常值。黎奇流是通过曲率构造黎曼度量强有力的工具,也是目前构造黎曼度量最为有效的方法。将光滑曲面黎奇流理论推广到离散情形,建立离散曲面黎奇流理论,是本书的重点之一。


曲面微分几何 曲面微分几何研究曲面在三维欧氏空间刚体变换群下的不变量,主要是第一基本形式和第二基本形式。除了黎曼度量之外,增添了曲面在三维欧氏空间中的嵌入信息。曲率定义更加丰富,除了高斯曲率,还有法曲率、主曲率、平均曲率。


图7. 光滑曲面离散化逼近。


在计算机中,光滑曲面经常用离散曲面来表示,由此我们需要研究几何逼近理论:如何在曲面上采样,如何计算采样点的三角剖分,才会保证离散曲面在各种范数下收敛到光滑曲面。为此,我们介绍离散法丛理论(normal cycle),这一理论将光滑曲面的曲率测度和离散曲面的曲率测度统一起来。如图7所示,基于这一理论和单值化定理,我们给出构造方法用离散曲面来逼近光滑曲面,并保证曲率测度收敛,这为整个计算理论奠定了坚实的基础。


图8. 曲面上的叶状结构。


曲面上可以定义实或者复微分形式,微分形式构成曲面的de Rham上同调群,反映了曲面的拓扑性质。霍奇分解定理断言每一个de Rham上同调类中,唯一存在一个调和微分形式。黎曼-罗赫定理给出了一般亚纯微分形式空间的维数。曲面上的调和微分形式、全纯微分形式在计算共形映射中起到了关键性的作用。曲面的全纯二次微分形式和曲面上的叶状结构等价类具有对应关系,叶状结构奠定了曲面和网格生成的理论基础。一般的微分同胚可以用拟共形映射来刻画。固定映射的同伦类,使得共形结构畸变最小者被称为是极值映射,通常极值映射也是Teichmuller映射,和曲面的全纯二维微分具有深刻的联系。本书会介绍这些理论及其计算方法。


如果我们将曲面视作由橡皮膜制成,曲面间映射的扭曲会诱导弹性形变能量,被表示成调和能量。使得调和能量极小者被称为是调和映照。调和映照的存在性,唯一性和正则性都强烈依赖于曲面的拓扑和黎曼度量,特别是调和映照的微分同胚性和计算稳定性更是由曲面的曲率所决定。调和映照和共形映射具有密切的关系,在度量变分情况下,调和映照和Teichmuller映射也有密切联系。我们用几何偏微分方程理论来加以讨论。

应用简介

这里我们简要介绍一下计算共形几何在工程和医疗领域的直接应用,并指出这些应用的理论基础。


计算机图形学 在计算机图形学领域,计算共形几何应用于曲面参数化(surface parameterization)。如图9左帧所示,曲面参数化是指用一个拓扑同胚将曲面映射到平面或者球面区域,使得映射的畸变尽量小。如图9右帧所示,我们在平面区域上设计绘制二维纹理图像,参数化映射将纹理图像拉回到曲面上面,得到纹理贴图。例如,我们将大理石的纹理贴到大卫王的头像上面,得到大理石雕塑的视觉效果。纹理贴图技术是动漫动画的基石,极大地提高了渲染结果的逼真程度。

图9. 曲面参数化。


但是,曲面参数化不可避免地会带来几何畸变。通常畸变分成两类,角度畸变和面积畸变。如图10左列所示,共形变换可以完全去除角度畸变,但是可能会带来强烈的面积畸变;如图10右列所示,最优传输映射可以完全去除面积畸变,但是可能会带来强烈的角度畸变。同时保持角度和面元的映射是等距映射,等距映射保持高斯曲率,因此无法将弯曲的曲面铺平。在实际应用中,保角参数化和保面积参数化各有独到的优点,根据实际应用加以选择。共形几何的单值化定理和最优传输映射构成曲面全局参数化的理论基础

图10. 曲面保角和保面积的参数化。


图11. 基于相位平移方法的三维扫描得到的人脸曲面。


计算机视觉 在计算机视觉领域,曲面配准具有根本的重要性。依随三维扫描技术的发展和成熟,获取三维曲面相对变得容易。图11显示了用结构光的相位平移法获取的人脸曲面。如何处理高精度、高分辨率的几何数据,成为计算机视觉的一个主要问题。如图12所示,曲面配准的目的在于建立两个曲面之间的微分同胚,,满足一定的条件,例如将特征点映到相应的特征点,同时尽量减小几何畸变和纹理误差等。为此,我们首先将曲面共形映射到平面区域,;然后在平面区域间建立同胚;映射的复合给出了曲面间的同胚,。平面区域间的映射比曲面间的映射相对容易计算,应用拟共形映射的方法,我们可以在所有同胚构成的空间中进行变分,从而得到最优映射。

图12. 曲面注册的计算框架。


例如,我们可以找到所有的特征点,然后在保持特征点对应的同胚空间寻找Teichmuller映射,基于拟共形几何理论,这种映射存在并且唯一,同时使得角度畸变达到最小。这种映射可以通过变换曲面的共形结构,应用迭代法得到。如果我们扫描得到一系列的动态曲面,例如人脸曲面带有表情变化,应用曲面配准方法我们可以在一系列曲面间建立微分同胚,从而可以追踪到表情的变化。这种技术在动漫动画领域,可以用于表情追踪。图13显示了一个动态曲面追踪的实例。带有表情变化的人脸曲面由平移相位法获得,蓝色四边形网格从一帧曲面映射到下一帧曲面,显示了追踪的结果。拟共形几何、Teichmuller理论构成曲面配准的理论基础


图13. 动态曲面追踪。


几何建模  在动漫动画领域,曲面可以表示成分片线性的多面体曲面;在机械制造领域,所有的曲面都必须是至少2阶可导的光滑曲面,因为数控机床需要计算道具的力和加速度,这需要用到曲面的2阶微分。通常扫描得到的是点云数据,进而转换成多面体曲面,最终转换成所谓的样条曲面(Spline Surface),从而用于机械加工。


对于拓扑复杂的曲面而言,建立全局处处2阶可导的样条曲面非常困难。这是因为传统的样条是基于仿射几何不变量来构造的,如果我们能够在流形上实现仿射几何,则我们可以将定义在欧氏空间中的样条理论直接推广到流形上面。这需要所谓流形的仿射结构,亦即一族图册,所有的坐标变换都是仿射变换。由拓扑障碍理论,通常的流形并不允许这种结构。由此,在流形上定义的样条不可避免地具有奇异点。如何控制奇异点的个数,和奇异点的位置成为几何建模领域的核心问题之一。


图14. 弥勒佛样条曲面。


如图14所示,我们在曲面上构造一个平直度量,将所有的曲率集中到预定的奇异点处,这可以由黎奇曲率流实现。平直度量诱导了去掉奇异点的曲面的一个仿射结构,从而可以用传统方法定义样条曲面。如此我们就可以控制奇异点的位置和个数。流形上的仿射几何和拓扑障碍理论构成流形样条的理论基础

图15. 无线传感器网络路由设计。


无线传感器网络 如图15左帧所示,每个无线传感器带有一个GPS坐标,可以和某个邻域内的所有传感器进行通信,但是没有任何一个传感器具有全局信息。传感器网络往往采用贪婪算法作为路由协议,每个获得消息的传感器选择邻域中的另外一个传感器,其距离终点的距离小于当前传感器距离终点的距离,然后将消息传递过去。每个传感器都遵循同样算法,使得当前拥有消息的传感器到达终点的距离逐步减小。但是,网络内部有各种各样的障碍,例如水塘和建筑物,当消息传至某个角点时,有可能当前传感器到终点的距离小于所有邻域中其他的传感器,因而协议终止,路由失败。我们可以采用分布式算法,将网络共形变换成平面圆域,每个边界都是标准圆,对于任意一个节点,都存在一个邻居,距离终点更近。整个网络在虚拟坐标上进行路由,可以保证消息送达。曲面的共形模理论构成无线传感器网络几何路由算法的理论基础

图16. 虚拟肠镜技术。


医学图像 计算共形几何方法在医学图像领域具有很多应用。图16显示了虚拟肠镜技术。直肠癌是发病率较高的一种病症,预防直肠癌最为有效的手段是肠镜技术。传统的光学肠镜方法对病患具有侵犯性,需要进行全身麻醉,并且容易诱导并发症。虚拟肠镜方法用CT扫描获取腹部断层图像,然后用图像处理方法重建直肠曲面,再用共形映射将直肠曲面铺平在平面上。这种方法设备和病患没有接触,不需要麻醉,不会诱导并发症。直肠曲面上有很多皱褶,传统光学肠镜方法无法看到皱褶内部的肠壁,有一定的漏检率。虚拟肠镜方法将所有皱褶摊开,所有的直肠息肉都被暴露出来,漏检率为0。因此,虚拟肠镜技术具有很多优势,日益普及开来。


图17. 共形脑图技术。


共形脑图技术广泛应用于奥兹海默症的诊断和预防。首先,通过核磁共振获取大脑断层图像,重建大脑皮层曲面,然后将大脑皮层曲面共形映射到单位球面,再复合上最优传输映射,得到大脑皮层到球面的保面积映射。大脑皮层曲面具有非常复杂的几何,沟回的结构因人而异,并且依随年龄增长而发生变化。直接建立两个大脑皮层曲面间的映射相对困难,通过它们球面像之间的映射来寻找微分同胚相对容易。通过比较不同时期扫描的同一个大脑皮层曲面,我们可以监控各个功能区域的萎缩情况,从而做出预测和诊断,采取相应的预防措施。

图18.规则六面体网格生成。


网格生成  在计算力学中,设计的机械零件需要进行仿真。仿真意味着求解有关力学、热学和电磁学等方面的偏微分方程。有限元法是最为常见的偏微分方程数值求解方法,这需要将机械零件进行胞腔分解,生成体网格,然后在体网格上用分片多项式来逼近真实解,多项式的系数成为未知变量。通常将偏微分方程转化成变分问题,通过优化求得未知系数。在这一过程中,关键步骤在于体网格生成。


共形几何为结构化的六面体网格生成奠定了理论基础。六面体网格在体的表面诱导了四边形网格,我们将四边形网格无限细分,得到两族彼此横截的有限叶状结构。曲面上有限叶状结构都和某个Strebel微分的水平轨迹等价。所有的全纯二次微分构成一个线性空间,Strebel微分在此线性空间中稠密。我们可以用计算共形几何的方法来构造全纯二次微分线性空间的基底,从空间中挑选合适的Strebel微分,构造曲面的四边形网格,然后扩展成六面体网格。这种方法保证奇异线的数目最少,网格整体结构规则,适用于精确的力学计算。流形叶状结构理论、Strebel微分理论、拓扑障碍理论构成规则六面体网格生成的理论基础




    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多