清华笔记:计算共形几何讲义 (2)代数拓扑

这次课程,我们简单介绍曲面基本群(一维同伦群)的理论梗概。主要概念有基本群的定义,表示,计算。然后我们介绍覆盖空间理论,特别是万有覆盖空间理论,曲线同伦检测算法。【1】给出了课程的视频。

这些理论工具在计算机图形学方面具有巧妙的应用实例,诱导了经典算法。我们仅举两个最为直接的例子:Konrad Polthier首先提出的曲面四边形网格化算法, QuadCover;Yaron Lipman提出的用深度学习来进行曲面的语义分割算法。这些算法的精髓来自于覆盖空间理论。

下一课,我们计算曲面单位切丛的基本群,介绍光滑同伦理论,这是瑟斯顿提出的用于解决“神圣网格”问题的理论基础。

计算机图形学中的应用

曲面四边形网格化

图1.jpg

图1. 曲面的四边形网格化。

如图1 所示,曲面的四边形剖分是计算机图形学的一个基本问题,四边形网格化对于计算力学而言非常重要。通常,我们可以计算曲面在每点的主曲率方向(principle direction),这样我们在曲面上定义了一个光滑标架场(Frame Field)。标架场具有一些奇异点。例如在脐点处(ambilical point),标架无法定义。

图2.jpg

图2. 分支覆盖(Branch Covering)。

我们可以构造曲面的分支覆盖空间,以奇异点为分支点,然后将曲面上的初始标架场“提升”到覆盖空间上的一个矢量场。然后,我们将覆盖空间的矢量场进行分解,求得调和分量,在投影回原来曲面,得到两组光滑矢量场。矢量场的积分曲线诱导了曲面的四边形网格。具体细节可以在【2】中找到。这种方法的关键思想是覆盖空间的概念,提升的概念,和矢量场的分解。

深度学习和曲面的结合

图3.jpg

图3. 曲面参数化,将曲面映射到平面长方形区域,生成“几何图像”。

目前,计算机图形学领域的一个研究热点是将神经网络和曲面结合,用深度学习的方法来进行几何处理,例如对曲面进行语义分割(symantic segmentation)。传统的卷积神经网的输入是二维图像,因此我们需要将曲面转换成“几何图像”,如图3所示。我们将曲面映射到平面区域,然后在平面上重新采样,得到二维点阵。

图4.jpg

图4. 用平环覆盖拓扑球面。

几何图像的一个缺陷是边界的不连续性。为了使边界光滑,我们采用分支覆盖。覆盖空间是拓扑环面,拓扑环面的覆盖空间是整个二维平面,可以作为神经网络的输入。如图4所示,大卫头曲面是拓扑球面,我们选择三个奇异点,构造4重分支覆盖,形成一个拓扑环面。拓扑环面的覆盖空间是二维平面。在【3】中,我们可以找到实现的细节。

基本群的概念和表示

图5.jpg

图3. 曲面上的蚂蚁。

代数拓扑由庞加莱创立。基本群的想法比较直观:假如我们是生活在曲面上的蚂蚁,一辈子没有跳离过曲面,因此没有三维的概念。那么,我们如何判断我们生活的曲面是否有“洞”?

图6.jpg

图4. 拓扑球面和拓扑轮胎面。

如图4所示,拓扑球面没有环柄,小猫曲面具有一个环柄,具有三维的“洞”。那么,这个“洞”是因为曲面嵌入在三维欧式空间中所产生的吗?换言之,这个“洞”是曲面和三维空间的相对关系,还是曲面自身内蕴的特性?

图7.jpg
图5. 拓扑轮胎曲面上,存在无法缩成点的圈。

如果蚂蚁比较智慧,它会追踪曲面上的封闭路径。拓扑球面上,所有的圈都能够缩成一个点;拓扑轮胎上,存在一些圈无法缩成点,如图5所示。“圈是否能够缩成点”的思想成为了同伦伦的源头。

图8.png
图6. 道路同伦。

基本概念


我们考察曲面上的道路,如果两条道路具有相同的起点和终点,并且一条道路能够在曲面上渐变成另外一条道路,则我们说它们彼此同伦,如图6。

如果道路的起点和终点重合,则我们称之为环路。我们在曲面上选定一个基点p。考察所有从基点出发,又回到基点的有向环路,将它们进行同伦分类。

  • 定义有向环路的乘法:两条环路首尾相接,构成一条更长的环路,则更长的环路为原来两条环路之积,如图7。

  • 能够缩成基点的环路被视作单位元。

  • 一条有向环路方向取反,所得的逆向环路被视为原来环路的逆元,如图8。

图9.png
图7. 环路乘积。红色的环路是两个黑色环路的乘积。

可以直接验证,所有过基点的有向环路同伦等价类,在连接操作(乘法)下成群。这个群被称为是曲面的基本群,一维同伦群,记为1.png

图10.png
图8. 环路取逆。红色的环路是黑色环路的逆。

表示

拓扑空间的同伦群的概念虽然直接,但是依然抽象,我们需要更为具体实际的表示方法。一般的方法是用同构的一个群,所谓的“词群”,来表示。

首先,假设我们给定一组“字母”,例如所有的英文字母,字母组成了词。两个词拼接成一个更长的词,这定义了词的乘法。显然,“空词”是这个乘法的单位元。同时,每个字母可以求逆,例如2.png互为逆元,它们之积为空词,即单位元。这样,所有的词在拼接的乘法下构成了一个群。这个群是由所有英文字母所自由生成的。

假设,存在一组特殊的词,“关系",它们等价于空词。给定一个词,我们可以对其进行如下基本操作:

  1. 在任何位置插入一个关系词,或关系词的逆,

  2. 如果在词中,存在一个子词等于某个关系词,或关系词的逆,去掉这一子词。

给定两个词,如果我们能够将其中的一个经过有限个基本操作变成另外一个,则我们说这两个词彼此等价。

所有词的等价类,在拼接操作的乘法下成群,被称为“词群”。一个词群的符号表示为 {生成元,关系词} 。

典范表示

在可定向的紧曲面上,存在基本群的生成元:

3.png

满足如下条件:

4.png

这里5.png代表环路a和环路b的代数相交数。所谓代数相交数可以如下理解。如果环路a和环路b横截相交于一点q, 并且a的切向量叉积b的切向量和曲面在q点的法向量一致,则q的指标为+1,如果相反,则指标为-1。如果环路a和环路b在点q相切,则q点的指标为0. 环路a和环路b的代数相交数等于所有交点的指标之和。

这种基本群的生成元被称为是基本群的典范基底。我们可以将曲面沿着一族典范基底切开,得到单连通的4g边形,所得的区域被称为是曲面的一个基本域,如图7所示。基本域的边界是

6.png,

边界可以缩成一个点。

图11.png

图9. 基本群的典范基底。

曲面上任何一条环路可以经同伦变换,使得它和典范基底只相交于基点。然后,将此环路最终分解为多个子环路的乘积,每个子环路只经过基点一次。在基本域上,每个子环路是连接两个角点的道路。道路可以同伦变换到基本域的一段边界上,由此子环路可以由8.png及其逆生成。这证明了7.png是基本群的生成元。因此,曲面基本群的典范表示是:

9.png.这里,g被称为是曲面的亏格,其直观意义是曲面上“环柄”的个数。每个环柄上有一对经度环路和纬度环路10.png,如图9所示。

基本群的计算方法

图的基本群

首先,我们考虑最为简单的情形:拓扑空间为一个图(Graph),记为G(V,E),这里V是顶点集合,E是边的集合。图中任何非平庸的环路都无法缩成一个点,因此图的基本群是自由生成的,其关系式为空集。首先,我们计算G的一个生成树(Spanning Tree)T,即T是G的一个不含任何环路的子图,同时T包含所有顶点。那么G\\T由一些边组成,我们称之为“余边”:11.png

每一条余边和生成树的并集12.png包含唯一的一条环路13.png,那么图G的基本群就是由这些环路生成,

14.png

注意,这里余边15.png是有定向的,相应的环路16.png也有定向,并且环路的定向和余边的定向相一致。

假设17.png是图上的一条定向环路,由一系列有向边次第连接而成,

18.png,

我们在序列中去掉所有的非余边,得到

19.png,

20.png的同伦类为

21.png

曲面的基本群 (火烧法)


直观描述 给定曲面M,我们假想曲面上长满了枯草。我们任选一个基点p,从基点处点燃枯草,火焰在曲面上逐渐蔓延。火焰的前沿在曲面上不停地拓展,两道火焰相遇而熄灭。火焰熄灭的轨迹成为曲面上的一个图,我们称之为曲面的割迹(Cut Locus),也称为曲面的割图(Cut Graph),记为G。火焰扫过的区域是一个单连通的拓扑圆盘(topological disk),我们称之为曲面的一个基本域(fundamental domain),记为22.png。假设图G的基本群为

23.png,

基本域的边界24.png是一条环路,这条环路在割图G上,25.png是包含映射,其在26.png中的词表示为27.png。那么,曲面M的基本群为

28.png

算法描述 问题的关键是计算割图G。曲面被三角剖分,而被表示成为三角网格,仍然记为M。

  1. 计算网格29.png的对偶30.png,顶点31.png的对偶为面32.png,面33.png的对偶为顶点34.png,边35.png的对偶依然为边36.png

  2. 计算对偶网格37.png的生成树38.png

  3. 割图G由所有其对偶不在39.png的边组成,

40.png


我们将网格41.png沿着割图G切开,就会得到基本域D。然后,我们调用图的同伦群算法,计算割图的生成元,和基本域边界42.png的表示,分别得到43.png的生成元和关系式。


图12.jpg
图10. 亏格为2的曲面上的割图,正反视图。


图13.jpg
图11. 曲面基本群的一组基底。


一般拓扑空间


一般拓扑空间的基本群计算主要是基于CW-胞腔分解。所谓k维CW-胞腔,就是k维拓扑圆盘。例如0维胞腔是点,1维胞腔是线段,2维胞腔是拓扑圆盘,3维胞腔是实心球体,等等。我们用44.png来表示第i个k维胞腔。假设M是一个n维流形,其CW-胞腔分解可以如下递归定义:

1.零维骨架是一族离散点

45.png

2.第k维骨架46.png是(k-1)维骨架47.png和一族k-维胞腔48.png的并集,并且每个k-维胞腔的边界49.png在(k-1)维骨架50.png上,

51.png

3. 第n-维骨架52.png等于原来的流形M, 53.png

图12.png

图12.亏格为1的曲面的CW-胞腔分解。

假设流形M的二维骨架

54.png,

一维骨架的基本群为自由群:

55.png

每个2维胞腔的边界56.png57.png中的表示为58.png,则流形M的基本群为

59.png

实际上,曲面的火烧法就是计算曲面的一个CW-胞腔分解,割图G是1-骨架,基本域D是2维胞腔。

理论证明


这里介绍的同伦群的组合算法是基于Seifert-van Kampen定理,这个定理的实质是分而治之的策略。就是将原来流形分解成子流形,分别计算每个子流形的基本群,然后将子流形的基本群拼成原来流形的基本群。


我们将原来拓扑空间M分解成U和V的并集,60.png;U和V的交集为W,61.png,这里U,V和W都是道路联通空间。62.png是包含映射。选取基点63.png,每个子空间的基本群是

64.png,

那么原来拓扑空间的基本群是

65.png

Seifert-van Kampen定理是说并集的生成元等于生成元的并,并集的关系式等于关系式的并加上交的生成元

我们来看曲面情形,曲面分解为基本域D和割图G的并集,基本域D和割图G的交集是一条环路66.png同伦于基本域的边界67.png68.png为包含映射。由Seifert-van Kampen定理

69.png

因此70.png

覆盖空间的理论

基本概念


直观而言,覆盖映射局部是拓扑同胚,但全局是多对一的映射。


假设1.jpg2.jpg是拓扑空间,3.jpg是连续满射,对于任意一点4.jpg,存在一个开集5.jpg,使得

6.jpg

满足7.jpg,如果8.jpg,同时映射的限制9.jpg是拓扑同胚。那么,我们说10.jpg是一个覆盖映射,11.jpg是底空间,12.jpg13.jpg的覆盖空间。


构造方法

抽象构造方法:假设14.jpg是一个流形,固定基点15.jpg,我们考察流形上

所有从基点出发的道路

16.jpg,

然后将这些道路依据同伦分类,得到同伦类集合,

17.jpg

我们在微信图片_20190412200341.jpg中引入拓扑。给定任意一点19.jpg, 道路20.jpg的终点为21.jpg。取以29.jpg为中心的一个开球22.jpg,考虑开球内从中心出发的道路集合23.jpg,

我们定义微信图片_20190412200341.jpg中的开球为 24.jpg。所有这样的开球构成26.jpg的一族拓扑基,因此2.jpg也成为一个流形。

投影映射将道路同伦类28.jpg映到道路的终点29.jpg

30.jpg

在这种构造下,32.jpg是底流形33.jpg的万有覆盖空间。这种构造方法过于抽象,很难直观想象。下面我们给出另外一种更为直接了当的构造方法,这种方法依赖于典范基本群基底的选取。

组合构造法 假设M是一个高亏格封闭曲面,固定基点34.jpg,我们计算其基本群的一组典范基底,

35.jpg,

我们将曲面M沿着典范基底切开,得到单连通的基本域

36.jpg,

则基本域的边界为

37.jpg

我们将许多基本域的拷贝沿着相应的边界逐片粘和起来,粘和过程中保证所得曲面一直是单联通的。最终我们所得的曲面被称为是原来曲面的万有覆盖空间。如图1所示,对于亏格为1的曲面,其万有覆盖空间可以配上一个平直黎曼度量,从而铺满整个欧式平面;对于亏格为2的曲面,其万有覆盖空间可以配上一个双曲度量,从而铺满整个双曲平面(欧式单位圆盘)。

图14.jpg

图13. 亏格为1曲面的万有覆盖空间。

提升和升腾


我们考察万有覆盖空间38.jpg,我们称底空间为楼下,覆盖空间为楼上。楼下的一条环路能够被提升为楼上的一条道路。图.jpg


39.jpg是楼下的一条环路,40.jpg是楼上的一条道路,楼上道路的投影等于楼下的环路:41.jpg换言之,上面的图表可交换。

图16.png
图14. 环路提升。

如图2所示,我们在楼下找一族开覆盖

42.jpg,

在楼上找到每个开集的原像,43.jpg, 并且 44.jpg,则存在唯一的道路45.jpg, 覆盖环路。通常情况下,楼下的一条环路可以提升为楼上无数条道路。如果我们固定提升道路在覆盖空间中的起点,则提升道路唯一。



同理,我们可以将曲面间的映射提升到覆盖空间之间,称为升腾:

图2.jpg

图表可交换:46.jpg


拓扑,代数关系


我们考察万有覆盖空间47.jpg底空间(楼下)上任取一点48.jpg, 其在覆盖空间(楼上)上的原像为离散点集

49.jpg

被称为是对应50.jpg的轨道。考察楼上任意一条道路,起始于51.jpg,终止于同一轨道内的另一点,

52.jpg

那么其投影必为楼下的一条环路。楼上两条这样的道路同伦,当前仅当它们的终点重合。投影映射保持同伦,楼下起始于基点的两条环路,如果它们同伦,则其提升道路同伦,因此提升道路具有同样的起止点。我们由此得到:楼上的轨道和楼下的基本群同构。

考察楼上所有这样的自同构,它保持投影映射不变,这样的自同构被称为是覆盖空间的甲板映射

图3.jpg
甲板映射使得上面的图表可交换。所有的甲板映射构成群,称之为甲板映射群:

53.jpg

投影映射诱导了覆盖空间的基本群到底流形的基本群的同态,其同态像是底流形基本群的正规子群,商群同构于覆盖空间的甲板映射群,

54.jpg

这一公式对于底空间的任意覆盖空间都成立,万有覆盖空间是一特例。楼下基本群的任意正规子群都对应着一个覆盖空间。

直接应用


同伦检测 在计算拓扑中,判定两个复杂环路是否同伦是一个饶有兴味的问题。

图17.jpg
图18.jpg
图15. 同伦检测。


我们可以将底流形上的环路提升到万有覆盖空间的道路, 然后判断这些道路是否起止于同样的点。


不动点类问题


假设55.jpg是拓扑复杂曲面的自映射,如果存在点56.jpg, 使得57.jpg,那么58.jpg被称为是映射的不动点。如果我们同伦变换映射59.jpg,使得不动点个数减少,那么不动点个数的下界是多少?这个问题非常艰深,借用万有覆盖空间理论,我们可以给出初步答案。


我们将映射60.jpg升腾61.jpg, 那么升腾并不唯一。升腾的不动点一定覆盖原映射的不动点;同时,对于原来映射的任何不动点,一定存在一个升腾,这个升腾的不动点覆盖原映射的不动点。


楼下的两个不动点等价,如果存在一个升腾,升腾的两个不动点分别覆盖这两个楼下的不动点。这样,我们将楼下的所有不动点分类。同一等价类的不动点可以经过同伦变换映射而融合。如果,等价的不动点具有相反指标,则它们融合后可以彼此相抵相消。因此,不动点个数的下限等于总指标非零的不动点等价类的个数。我们以后会详细讨论,如果对更为深入的理论有兴趣,请参阅江泽涵先生的专著《不动点类理论》。


【1】http://m.iqiyi.com/w_19rtqmw8mp.html?msrc=10_107_192&u1;=qyid1424935073&wx;_uid2=wxidoG0a9jh7lM1t3z2B8P3BDI9fbOwM

【2】F. Kalberer, M. Nieser and Konrad Polthier, "QuadCover – Surface Parameterization using Branched Coverings", Computer Graphics Forum, 2017.

 

【3】H. Maron, M. Galun, N. Aigerman, M. Trope, N. Dym, E. Yumer, V. Kim, Y. Lipman, Convolutional Neural Networks on Surfaces via Seamless Toric Covers, SIGGRAPH 2017.

原文发布在【老顾谈几何】公众号 (2017年7月5日)

https://blog.sciencenet.cn/blog-2472277-1172906.html

上一篇:第一性原理 – 与张首晟先生一席谈
下一篇:清华笔记:计算共形几何讲义 (4)单纯同调

© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片