第3章?骨架涡旋上的三个形状指纹、 测地轨迹和自由阿贝尔群   本章重新审视单元复合形中的细丝骨架、骨架涡旋和骨架神经。这里的重点是基于数字图像计算拓扑(CTdi)的群论。数字图像是所谓形状空间的一个例子。空间是任何非空的点集。形状空间是一组点X的集族,并且X子集中的每个特定配置(点的排列)定义了一个形状。数字图像形状空间是数字化光学传感器值的集族,可提供色调饱和度值的颜色空间中像素色调角度的记录。在给定的时空中,像素色调角与视觉场景中表面反射光的波长之间存在一对一的关系。正是这种一对一的关系导致对三角化视频帧图像上的骨架复合形有更深入的了解。 3.1?引言:空间的形状   Zomorodian [1,1.2节,p.3]对空间的形状进行了介绍。CTdi揭示的许多数字图像形状在很大程度上对随意检查是隐藏的。数字图像的这种隐藏特征促使将图像分解为可识别的几何形状,从而可以测量和比较图像子区域中的形状。例如,可以通过对图像形状空间上的选定点进行三角剖分来完成这种分解。CTdi提供了一些算法(方法),它们给出了获得有关图像目标形状的特定结果的步骤。本章还介绍了视觉场景中的Betti-Nye涡旋循环以及对持久贝蒂数的异想天开的观点。表3.1给出了本章中使用的形状复合形、骨架和其他符号的选择。 表3.1?形状复合形、骨架和其他有用的符号 符号 含义 符号 含义 R2 欧氏平面 K 单纯复合形 ▲ 2-单元(实心三角形) 2K K的子集集族 顶点p和q之间的弧 covA A的覆盖 shA 形状A x mod 2 x除以2后的余数 子集Ai的交集 shA? covA 形状A,覆盖covA的子集 ?g? 循环群生成元 shA?2K 形状shA,2K中的子集族 skE 细丝骨架 skVA?2K K中的骨架涡旋 skNrvE 骨架神经 shA 物理骨架A 3.2?在三角化表面形状上发现定向细丝骨架的生成元   本节简要介绍一种在三角化表面上的定向细丝骨架中寻找生成元的方法。回想一下,一个定向细丝骨架是由一族有序的、路径连通的顶点定义的,并且每个定向细丝骨架skA都有一个独特的顶点a? skA,称为生成元(由?a?表示)。例如,定向细丝骨架skA的生成元?a?是骨架中边之间的最小细丝长度。 在哪里寻找生成元    寻找形状骨架涡旋和骨架神经生成元的途径是通过在三角形表面形状上构建定向的双向细丝骨架。细丝骨架是定向的、双向的,前提是可以从任何骨架顶点开始并沿着骨架的细丝向前或向后移动。 ■  骨架将从连接到顶点v1的起始顶点v0开始,并且该段的长度为,因此骨架skA中的每个其他段的长度都是该初始段长度的倍数,这是一个定义在skA中k个路径连通顶点的有序集合上的生成元a(由?a?表示),即   为简单起见,我们通常在?a?明确时将其写成a。然后从每条路径中连通的细丝引入映射,使得每条细丝的长度是生成元?a?的倍数。让m1, ..., mi, ...,mk?1是生成元a的倍数。这意味着,如沿着特定的细丝向前移动会导致 并且沿着同一根细丝向相反方向移动会导致   例如,可写出   路径边之间的“+”读作“连接到”。一条路径由一条边开始形成,其中顶点v0是路径中前端的开始,是细丝骨架中有序顶点集中的下一条边。回想一下,边被称为细丝。术语细丝用于描述涡旋循环中的边,引起人们对三角化图片(视觉场景快照)中事物的物理方面的注意。通过将生成元?a?写成mia的倍数,我们忽略了任何细丝长度中生成元距离的变化分数,而专注于对生成元长度的倍数求和。   对于skA中的每个细丝,在相反方向上都有一个对应的(我们允许在骨架上向前或向后移动)。因此,对于每个mia,存在加性逆?mia。也就是说,我们总是可以写出mia ? mia = 0。还要注意,每组定向的、路径连通的顶点都有一个零运动。我们写成 由0表示的空细丝或由0表示的零运动称为加性恒等。实际上,这种细丝骨架的所有成员都可以表示为其生成元的线性组合。后续中,我们考虑定向细丝骨架的循环群表示。为了保持人们对视觉场景中CW复合形细丝骨架的兴趣,回想一下如何在三角形形状空间上构建细丝骨架。   例3.1   贝壳表面一对涡旋的外部和内部分别表示在图?3.1(a)和图?3.1(b)中1。从计算机视觉的角度来看,这些图像中的暗区是孔(即吸收与表面碰撞光(光子流动)的表面区域)。这些图像中的白色区域是表面反射光的那些部分(所谓的目标区域)。 (a) 外部贝壳涡旋 (b)内部贝壳涡旋 图3.1?贝壳涡旋样本   为了解有关表面形状(例如图3.1(a)中的贝壳涡旋)的更多信息,执行以下操作。   (1)选择一组包含某些表面目标区域质心的种子点S。   (2)对S中的点执行德劳内三角剖分。最终结果是一个单元复合形K,它是一个实心三角形▲(2-单元)的集族。每个三角形▲的顶点是S中贝壳表面上彼此最接近的种子点。   (3)在K上找到一个或多个最大核聚类(MNC)。回想一下,三角剖分MNC是具有公共顶点的三角形的最大集族。   (4)找出MNC三角形的重心以及与MNC接壤三角形上的三角形。   (5)绘制一个细丝骨架skA,它表示一组在skA上路径连通的有序重心。   与MNC接壤三角形的重心上的示例细丝骨架skA在图3.2中显示为连通的黄色边2。skA的形状反映了质心在与MNC接壤的形状空间里小的子区域中的分布。至少,skA提供了一种查找与skA相似的其他表面区域的简单方法。 图3.2?由贝壳图像表示的形状空间三角剖分 ■   skA中的路径连通顶点的排序很重要,因为我们总是可以将skA中的特定顶点a指定为骨架中有序顶点开始处的顶点,即所谓的生成元?a?。这种排序让我们对细丝骨架的循环群表示有了新的认识,我们将在本章的后续中进行解释(例如,参见3.21节)。   对CW复合形中定向细丝骨架的研究(来自2.5节),也为称为自由阿贝尔群的高阶代数结构打开了大门,这是骨架涡旋(来自2.10节)和骨架神经(来自2.6节)的简单结果。修补这些结构(细丝骨架、骨架涡旋和神经)的实际结果是一种新形式的条形码,该条形码基于涡旋复合形的自由阿贝尔群表示的贝蒂数或由多个骨架神经循环相交而构建的看似摩天大楼的骨架的贝蒂数。简而言之,贝蒂数是自由阿贝尔群中生成元数量的计数(参见词汇表A.2)。   随着基于贝蒂数的条形码的出现,我们可以开始考虑视频中图像帧形状在时空中的持久性。也就是说,只要形状的群所表示的贝蒂数持续存在,形状就会在视频帧图像序列中持续存在。实际上,我们得到了一种非常简单的方法来测量视觉场景中表面的形状磨损。形状磨损指示在一系列视频帧图像中记录的表面形状能持续多长时间。 3.3?图像几何学:研究图像目标形状的方法   CTdi在很大程度上是更通用的计算拓扑(CT)的应用,以Edelsbrunner和Harer [2]为代表。CT融合了几何学和拓扑学,并提供了大量非常有用的算法,这些算法可以在不同的环境中轻松实现。CTdi还包括计算接近度(CP)组件。CP是一种算法方法,用于查找彼此靠近或相距很远的非空点集。连通性、有界性、神经复合形、凸性、形状和形状理论是研究物理和抽象形状的接近和分离的主要主题。   故事从图像几何开始,这是从图像的三角剖分中轻松得出的结论。基本思想是将图像分解成三角形,顶点位于图像中的各个位置(通常称为种子点或关键点)。我们主要对平面图像感兴趣。平面图像的三角剖分更容易处理,而不是试图理解2-D或3-D图像中像素集的相互关系。隐藏的图像结构,例如形状和子形状聚类,通过对图像进行三角剖分来揭示。由于三角剖分属于初等几何学,没有进行三角剖分的图像中非常复杂的东西现在变得更加简单。   有关CT及其应用的介绍,请参阅Zomorodian [3]关于构建点集的组合表示和采样空间的拓扑(点和集的接近度)的恢复。要从几何拓扑的角度深入介绍CT,请参阅Edelsbrunner和Harer [2]以及Rote和Vegter [4],另参阅Zomorodian [5]。   CT中的主要主题是图(尤其是连通组件)、曲面(尤其是三角剖分)、复合形(例如单纯复合形和德劳内复合形)、同源性(尤其是从循环中导出的群)、持久性(即结构随时间的生存)和稳定性(即结构对随时间变化的抵抗力)。CT中的这些主要主题从CTdi中的应用角度以各种形式重新出现。CT有一个庞大的拓扑组件,当我们考虑结构(如亚历山德罗夫神经)在随时间变化的三角化形状空间中的持久性时,它就会浮现出来。   有关拓扑的非常好的介绍,请参阅亚历山德罗夫[6]、J?nich [7]、Hatcher [8]、Ghrist [9]和Giblin [10]。有关计算接近性(CTdi中的一个强大组件)的介绍,请参阅Peters [11]。有关CTdi在计算机视觉中的基本应用,请参阅Peters [12]。   在CTdi中,映射是图像形状中重要结构的中心来源。映射是一对集合之间的对应关系。在图像形状的研究中,将形状子图像集上的映射定义为三角形(s集。在单元复合形的拓扑中,我们考虑将形状内部集合映射到孔上的路径连通顶点集合。   连通形状路径是边(1-单元)的序列,这些边由三角剖分的形状上的单元复合形中的路径连通顶点(0-单元)来定义。这些连通的形状路径可以是形状孔的边界、循环连接形状路径(1-循环)或非循环连接形状路径(不在同一顶点开始和结束的骨架)。在同一顶点开始和结束的形状路径具有循环组表示。   回想一下,群是配备了二元运算○的非空元素集,它是关联的。每个群都有不同的元素,称为标识或单元元素e。群G的每个成员x都有一个由x?1表示的逆,即x○x?1 = e。   循环群G是一组n个元素ai,i = 0, 1, 2, ..., n?1称为生成元(表示为?ai?),配备有二元运算○。对G是一个循环群的要求是   Herstein [13,2节,p.29]观察到具有n个元素的循环群的几何实现是让群生成元在单位圆的圆周上旋转2πn的角度。二元运算○是阿贝尔运算,因为a○b = b○a满足所有G中的成员a、b。在CTdi形状理论中,通过让运算○成为加法模n,即○ = + modn来简化问题。对于(a + b)mod n,请记住加法模n等于总和除以n后的余数。因此,如果让(G,+mod 2)是一组包括5和8的整数。那么   对从三角形上的循环导出的循环群元素的系数执行加法+mod 2。Edelsbrunner和Harer [2,IV.1节,p.79]观察到,在单纯复合形里单元复合形的形式和之中,形式和的项的系数通常为0或1(称为模2系数)。   在CTdi中,循环群是由在围绕三角化形状上的连通形状路径上游动的循环来定义的。除了形状的轮廓之外,图像形状的内部还有很多这样的路径。因此,CTdi中的循环群通常包含不止一个生成元。 3.4?从图像形状分析角度看CTdi   本节从图像形状分析的角度简单介绍CTdi。术语图片和数字图像可互换使用。数字图像是指光栅图像。对于游戏等许多应用程序,对图像的关注从光栅图像转移到矢量图像。本章及以后常用的符号见表3.1。本书中使用的符号的完整列表在本书末尾的主题索引的开头给出。   故事从将图片(也称为数字图像)分解为图像上选定关键点之间连通的三角形集族开始。通过将图像分解为连通顶点、边和三角形的集族,我们可以访问图像中的一些隐藏内容。对图像进行三角剖分的直接结果是单纯复合形,它是一族覆盖图像的由顶点唯一确定的非重叠三角形。图像X被单元复合形A覆盖,只要X?A,即只要图像点集是复合形A的子集。由有限有界区域的三角剖分产生的单元复合形称为(复合形(又名实心三角形复合形)。隐藏在大多数具有适度复杂性的图像中的是我们在每幅图像上绘制的三角形网格中捕获的大小形状的集族。   例3.2 (三角化的形状)   一个简单的袋鼠形状A(用shA表示)如图3.3(a)所示。这种形状有许多由深色表面区域代表的孔,即耳朵、眼睛和嘴巴。将该形状分解为填充三角形的集族{(}(称为集族covA)如图3.3(b)所示。请注意,形状shA被covA覆盖,即shA? covA。这标志着图像目标形状研究的开始。 图3.3?袋鼠形状和三角化形状 ■ 3.5?单元、单元复合形,循环和边界   本节介绍数字图像计算拓扑中的一些基本构建块,从(复合形中的单元和单元复合形(绘制在图像形状上的连通的1-单元的序列)开始。从基本结构(例如图像形状的顶点和边)出发,我们可以访问更丰富的结构,例如沿着形状边界的连通闭合弧序列(称为闭合1-单元)或开放圆盘之间的连通弧序列(称为2-单元)或称为0-单元(顶点)的最小图像形状结构。下一步很容易开始考虑弧链(1-复合形),每个链通过一对顶点之间的一系列弧而将一个顶点(0-单元)连接到另一个顶点。   简而言之,链是表示为形式总和的单元复合形的有限集族。由此,我们获得了一个包含顶点之间连通路径的链复合形。在链复合形包含简单的、封闭的连通路径的情况下,图像区域被可测量的路径包围。有关链的更多信息,请参见附录A.12节。在解开图像形状中的隐藏结构时,我们主要对所谓的1-链感兴趣。1-链是(复合形中连接弧(1-单元)的形式总和。   对于平面形状,形状的几何是通过用单元复合形覆盖形状来找到的。单元复合形(由(复合形表示)是连通单元的集族,这些单元是通过沿着称为循环的路径将顶点和边拼接在一起而构建的。对于每个给定的图像形状,基本方法是从一组0-单元(顶点)开始,并通过将边(1-单元)附加到每个顶点来构建单元复合形。在获得(复合形之后,我们可以根据形状的单元覆盖来确定图像目标的几何形状,或者可以开始在(复合形中跟踪由从一个顶点到另一个顶点的边序列所确定的不同类型的路径。每个(复合形包含不同类型的路径,可用于对形状进行分类。   我们对循环(位于平面形状上的简单、封闭、连通的路径)的构建感兴趣。这样做的动机是我们对形状的某些部分进行了易于处理的近似。形状本身可能非常复杂,即使是最简单的形状也是如此。 形状指纹    通过在形状上构建单元循环,我们获得了形状的指纹,这是由于每个形状边界的限制而产生的形状特征。形状指纹是从形状的一部分到形状的另一部分的独特连通路径。形状指纹告诉我们有关形状的信息,而无需查看形状的每个部分。这里有一个试图证明或反驳的猜想。   猜想3.3    每个物理目标至少有一个独特的形状指纹。 ■  在数字图像的上下文中,基于没有两个数字图像完全相同的假设,还有第二个猜想需要考虑。   猜想3.4   每幅数字图像至少有一个独特的形状指纹。 ■   将形状指纹视为连通的封闭1-单元的集族。闭合的1-单元(闭合弧)是具有端点的1-单元。   例3.5 (从单元映射构建形状循环)   三个0-单元和两个1-单元的集族如图3.4(b)所示。每个形状路径循环的构建都从选择一对0-单元开始,这些单元映射到一个开弧或1-单元。例如,一对0-单元v和v′(用●表示)到开弧的边界(标记为1a)的映射如图3.4(a)所示。设V是一组顶点。映射cellMap本身是 定义为 图3.4?从连通的闭合1-单元序列构造形状循环   面到面映射的结果是一个闭合的弧,一个形状循环中的边。将一个闭合弧嫁接到另一个闭合弧上是通过一系列面到面映射来完成的。设v″是一个0-单元,如图3.4(b)所示。然后单元映射产生一个简单的闭环(路径)片段∪,如图3.4(b)所示,即,   回想一下,两个集合A、B的交集是两个集合中所有公共点的集合(用A?B表示)。在这个例子中,每个面到面({v, v′})都是闭合弧中的一组点。每对连通的弧都有一个共同的0-单元(顶点)。在这种情况下,顶点v′是一对面到面映射的共同点。   继续这个面到面映射序列,我们得到标记为?a?的循环,它是一条连通路径,具有在顶点v开始和结束的遍历。完整的面到面映射序列的最终结果是边标记为1a、2a、3a和0a(循环结束)的形状循环。实际上,该循环的遍历具有4小时制的时钟上的旋转时钟指针的外观(当完成标记为0a的段的遍历时,计数重新开始)。 ■   (-复合形中的路径是在复合形中的一对顶点之间引导的边序列。如果路径中的任何一对顶点之间存在一系列边,则路径是连通的。一条路径是简单的,只要这条路径没有自相交(循环)。如果路径中的顶点对之间有一系列边连接,则路径是闭合的。一个0-单元是链复合形中的顶点,而不是(复合形中的顶点。 3.6?在图像形状上绘制的定向弧上旋转   沿着封闭的连通路径(我们称之为形状循环)来回导航需要双向1-单元(也称为定向弧)。回想一下,双向定向弧(也称为定向边)是可以从端点v遍历到另一个端点v′并且也可以从v′遍历到v的弧。定向弧的旋转行为需要沿正向遍历弧,然后沿反向遍历边。尽管弧和边这两个术语可以互换,但弧比边更受欢迎,因为图像边(以及物理世界中的所有其他边)往往是弯曲的而不是直线的。直边的概念是欧氏几何的延续,欧氏几何是测量员通过经纬仪所见的简化视图。   例3.6?(在定向闭合弧上旋转)   两种形式的定向弧如图3.5所示,即,   (1)图3.5(a)显示了单个定向闭合弧(在正方向标记为1a,在反(负)方向标记为–1a)。静止状态是每个旋转行为的一部分。在定向弧的旋转行为中,静止状态是没有旋转的状态。静止状态(无旋转)由0a表示(图3.5(a)中未显示)。这条弧上的旋转是通过沿着箭头→从顶点v到v′遍历弧,然后通过沿着箭头→从顶点v′遍历这条弧回到v来执行的。定向弧的完整旋转行为由集合表示: 图3.5 连通定向闭合1-单元   这种在定向弧上旋转的自然结果是如下形式的循环   (2)图3.5(b)显示了一对连接的定向弧(标记为1a)和(标记为2a)。图3.5(b)还显示了从v″到v′(标记为?2a)然后从v′到v(标记为?1a)的反向遍历。这对连通的弧上的旋转是通过沿着箭头→从顶点v到v″遍历弧,然后沿着箭头→从顶点v″遍历这条弧回到v来执行的。定向弧的完整旋转行为由集合表示:   这种在连通弧上旋转的自然结果是如下形式的循环   定向弧上的旋转行为可以压缩成表格形式。这是通过将沿着边的每次遍历视为对弧标签的系数进行模2加法的一种形式来完成的。设a和b是整数。回想一下,加法(a + b)模2等于a + b除以2后的余数。那么,可在如下表中表示单个定向弧上的完整旋转行为。 +mod 2 0a 1a –1a +mod 2 0 1 –1 0a 0a 1a –1a 0 0 1 –1 1a 1a 0a –0a 1 1 0 –1 –1a –1a 0a –0a –1 –1 0 –0  当通过去掉弧标签a和–a将左边的+mod 2表映射到右边的系数表时,表示定向弧旋转行为的表格被简化了。在这两种情况下,请注意保留了旋转行为。在这两个表中都有一个恒等元素,即左侧表中的0a和右侧表中的0。并且每个元素的逆元素也表示在这些表格中。对一系列连通的定向弧的加法模2运算也为我们提供了循环群的两个简单例子。 ■   习题3.7?   使用加法模2运算以表格形式表示图3.5(b)中连通弧对的旋转行为。 ■ 3.7?单元复合形中形状循环的构建   在计算机视觉中开展计算图像形状几何的研究是很常见的,它可以使用镶嵌或三角化图像形状,例如,请参阅Peters [12,1.4节,p.8ff]。   简而言之,通过使用多边形尽可能多地覆盖形状来形成所谓的沃罗诺伊图,从而对图像形状进行镶嵌。这是通过预先选择一组关键点(通常沿着图像中形状的边缘)来实现的。然后,每个关键点p成为通过将直(或弯曲)边连接到最接近p的每对关键点而构建的多边形的中心。相比之下,也可通过让每个关键点p成为三角形的顶点来对图像形状进行三角化,三角形的顶点是通过将p的直边连接到最接近p的一对关键点来构造的。这种方法称为德劳内三角剖分。在任何一种情况下,我们都会获得图像形状的单纯复合形覆盖。有关德劳内三角剖分的介绍,请参阅Edelsbrunner和Harer [2]以及Peters [14]和[12,1.4节,p.8ff]。   在形状空间中,连通弧是形状表面上路径中连通闭合弧的集族。设(闭合弧集中的一对闭合弧)、? clX1。那么,映射?:clX1 × clX1→ clX1定义为   实际上,映射?将闭合弧黏合在一起以形成连通的闭合弧。单元复合形是一族连通的闭合弧线,用于定义形状表面上的连通路径。单元复合形是可以从形状的一个部分穿越到形状的另一部分的道路。如果连通的闭合弧允许在同一顶点开始和结束遍历,则连通的闭合弧可以定义称为循环的简单闭合路径。如算法9所示,构建了一个单循环的单元复合形。 算法9:构建形状循环  回想一下CW拓扑中的C读作有限闭包,因为我们正在处理循环上的闭合弧;W读作弱拓扑,我们通常只关心图像形状循环上的相交弧,这被认为是弱拓扑,因为普通拓扑中开集的并集不是我们考虑的一部分。这里的主要原因是相交循环产生新形式的循环群,而形状循环的并集通常不会产生循环群。每个循环都被称为单元复合形,因为我们在构建形状循环时使用简化形式的图像拓扑结构中的开放弧单元。   这是从检查图像三角剖分中的顶点到0-单元的重要转变,0-单元是图像形状上简单闭合连通路径(循环)中的基本构建块。类似地,1-单元是链中的一个开放弧(或开放边,即没有端点的边),作为形成单元复合形的胶水,作为图像形状上的简单闭合路径,具有新的特征。将我们的注意力从三角化图像形状上的顶点和边转移到作为简单连通路径中1-单元端点的0-单元的主要动机是简化图像中形状的表征、比较和分类。也就是说,使用三角剖分,重点是用三角形覆盖一个形状并检测具有公共顶点的相交三角形的集族(称为亚历山德罗夫神经)。相比之下,覆盖条件随着在图像形状上游动的单元复合形构成循环(简单的、封闭的、有界的、连通的路径)而消失。实际上,我们提供了一种通过考虑形状表面上的循环来检测形状指纹的简单方法。 3.8?闭合连通的路径:图像形状中孔的边界   通过构建循环的闭合弧,我们获得了一种隔离单元复合形(又名链复合形)边界内形状的内部区域的方法。在图像目标形状的研究中,通常考虑两种类型的形状循环,即,   作为孔边界的循环:形状孔是包含具有均匀强度的像素的有界图像区域。这意味着形状孔有多种外观。孔是均匀暗或均匀亮的图像区域。三角化形状中三角形的边是近似形状边界的方便来源。   例3.8?(形状孔边界)   图3.6(a)显示了示例袋鼠形孔Ho的边界(由bdyHo表示)。边界bdyHo由三角形的边定义。 图3.6 袋鼠形状边界和三角化形状循环 ■   不是孔边界的环:形状A上的环(用cycA表示)是一个简单的、封闭的、连通的路径,它要么围绕有边界的孔,要么不围绕形状孔。   例3.9 (形状循环)   形状循环cycA样例如图3.6(b)所示。在这个例子中,cycA的内部没有可见的孔。■   CT的重要部分是仅考虑围绕孔的循环作为边界。这是有道理的,因为孔基本上是一个有边界的空白空间。在将围绕孔的循环声明为边界时,我们通常处理的是孔的边界的近似值。扫过图像形状空间的其他循环不是孔的边界。   例3.10 (围绕多个孔的形状循环)   围绕几个图像孔的形状循环cycB如图3.7所示。在这个例子中,cycB在其内部包含可见的孔,即袋鼠形状的耳朵、眼睛和嘴。 图3.7?环绕多个孔的循环cycB ■ 3.9?映射到神经复合形的形状顶点   对图像进行三角化的最终结果是将图像划分为包含图像形状的单独区域。其基本思想是从仅仅限制我们对三角化图像的观察进到对三角形图片区域的集族去仔细观察图像三角形的内部,这是开集,即没有边界的三角形内部,这是数字图像拓扑的开始。有关弧的链的更多信息,请参见Flegg [15,p.43]。该方法可以看作是一系列映射(图像点到顶点、弧和相交三角形的投影):(-复合形是对形状shA(由cov(shA)表示)的覆盖,满足(图3.8) 图3.8?形状映射示例 即,形状shA完全位于覆盖层的内部(是cov(shA)的真子集)或shA占据与覆盖层cov(shA)相同的平面区域。   映射是目标(例如图像)与其三角剖分之间的对应关系。覆盖图像目标形状shA的每个(-复合形都包含称为神经复合形(由NrvA表示)的结构。   定义3.11?(亚历山德罗夫神经复合形)   设shA是一个被(-复合形cov(shA)覆盖的平面形状,设v是覆盖cov(shA)中的一个顶点。那么一个亚历山德罗夫神经复合形NrvA是相交三角形(? cov(shA)的集族,即,   神经核NrvA是神经中所有共有的顶点。 ■   源自三角化曲面的神经复合形以亚历山德罗夫(P. Alexandroff)的名字命名,他于1926年[16]引入了神经复合形,1935年他给出了一个非常易读的介绍[6,33节,p.39]。   例3.12?(神经复合形样例)   图3.9显示了袋鼠形状覆盖物中的一对样本神经复合形。图3.9(a)中的神经NrvA是一族三角形,覆盖了袋鼠的头部、肩部和颈部的大部分。红色●是NrvA的核。图3.9(b)中的神经NrvB是一族风筝形的三角形集合,覆盖了袋鼠的大部分肩部和部分颈部。同样,红色●是NrvB的核。 图3.9?袋鼠形状复合形NrvA和NrvB ■   请注意,相交神经提供了一种简单的方法来描述由具有共同顶点或共同边或共同实心三角形的一对神经部分覆盖的形状。   例3.13?(相交神经复合形样例)   图3.10显示了一对相交神经复合形部分地覆盖袋鼠形状的样例。神经NrvA与神经NrvG有一个共同边。 图3.10?相交神经NrvA和NrvG ■   定理3.14   单纯复合形中的每个顶点都是神经的核。   证明:令K为单纯复合形,令v, v′为K中的顶点。根据定义,存在神经NrvA? 2K使得   类似地,有一个神经NrvB? 2K,核v′?v。由于v,v′是任意的,所以得到证明。■ 3.10?形状映射到具有顶点中心的球   本节介绍从三角化平面形状shA到中心为c和半径为r的开单纯形球(由Br(c)表示)的映射。   定义3.15?(开球)   设shA是覆盖单元复合形K的平面形状,顶点为c?K,半径r> 0。单纯形球Br(c)定义为 Br(c)是一个开球,因为Br(c)没有边界。 ■   例3.16?(开球样例)   图3.11显示了一对部分覆盖袋鼠形状shA的开球。图3.11(a)中的球Br(c)部分覆盖了袋鼠的头部,这提供了一种此类头部形状与另一种头部形状进行比较的简化方法。这可以通过使用球的面积粗略近似头部形状来完成。相比之下,图3.11(b)中半径为r′ >r且顶点中心为c′的Br(c′)覆盖了形状shA的较大部分。 图3.11?开单纯形球Br(c)和Br(c′) ■   定理3.17   单元复合形中的每个顶点都是球的中心。   证明:可直接从定义3.15得到。 ■   根据应用的不同,包含边界的球(即闭合球)可用于分析单元复合形。   定义3.18?(闭合球)   设shA是覆盖单元复合形K的平面形状,顶点为c?K,半径r> 0。闭合球cl(Br(c))定义为 cl(Br(c))是一个闭合球,因为cl(Br(c))包括它的边界。 ■   例3.19?(闭合球样例)   图3.12显示了部分覆盖袋鼠形状shA的一对闭合球。图3.12(a)中的球cl(Br(c))部分覆盖了袋鼠的头部,这提供了一种用头部部分到边界或到闭合球内部的距离来比较两个头部形状简化方法。同样,这可以通过使用区域以及闭合球的边界作为头部形状的粗略近似来完成。相比之下,图3.12(b)中半径为r′ >r且顶点中心为c′的cl(Br(c′))覆盖了形状shA的较大部分。 图3.12?闭合单纯形球cl(Br(c))和cl(Br(c′)) ■ 3.11?切赫神经中的多个球   单元复合形K上的切赫(?ech)神经是一族交叉球,每个中心c?K,半径为r(由Cechr(K)表示),定义为   从具有倒圆角边的三角形平面形状的角度来看,切赫神经优于亚历山德罗夫神经,因为切赫神经中的球的外边缘往往更容易符合形状边缘。   例3.20?(切赫神经样例)   设K为覆盖图3.13(a)中袋鼠形状的单元复合形。图3.13(a)显示了部分覆盖三角袋鼠形状shA的切赫神经样本Cechr(K)。K中选定的顶点是切赫神经中的球的中心来源。在 图?3.13(a)中,每个球中心都用●表示。在构建切赫神经时,有必要识别所有相交的球(具有一个或多个共同点)。半径为r′ >r的第二个切赫神经样本Cechr′(K)如图3.13(b)所示。这个切赫神经完全覆盖了袋鼠头。由于这个原因,Cechr′(K)比图3.13(a)中较小的切赫神经更有趣。   在测量三角化平面形状时,重叠的切赫神经也很有趣。因为这给我们提供了一个方便的形状测量来源,在对大且相交的形状区域比较时,形成了所谓的切赫复合形(图?3.14)。    图3.13?切赫神经Cechr(K)和Cechr′(K) ■ 图3.14?重叠的切赫神经Cechr(K)和Cechr′(K) 3.12?切赫复合形:切赫神经重叠   本节介绍计算拓扑学中的一个众所周知的结构,即在一组顶点S上的切赫复合形。切赫复合形是在S上相交的切赫神经集族里球中心的三角剖分(表示为cxCechr(S)),定义为   回想一下,每个切赫神经Cechr(K)是一族相交的球,每个球都有自己的中心,半径为r。在这里,重点从构建单元复合形的顶点三角剖分转移到相交切赫神经集族里球的中心的三角剖分。   例3.21?(切赫复合形样例)   设S是一组顶点(S中的每个顶点用红色●表示。图3.15显示了S上的样本切赫复合形部分覆盖袋鼠形状。这个切赫复合形cxCechr(S)包含三个重叠的切赫神经,即, 这是三个切赫神经的非空交点。每个Ai都是位置S集的一个子集。请注意,每个切赫神经与中心球重叠,中心球为绿色阴影的切赫神经Cechr(A2? 2S),如图3.15所示。然后在三个神经的球的中心处进行三角剖分。   在近似形状方面,从球的中心向外展开的三角形的中心处部分地覆盖形状是对覆盖形状的普通单纯复合形的改进。从球的中心派生出的一族三角形与切赫神经相交是单纯复合形的另一种形式。有关这方面的更多信息,请参阅Edelsbrunner和Harer [2,III.2节,p.60]。 图3.15?切赫复合形 ■ 3.13?同源映射和神经之间的轨迹   本节介绍形状之间的边轨迹(路径)。轨迹是一系列连通的边,其联合同源于一条横跨轨迹中初始顶点和结束顶点的线段,如Boltyanski?和Efremovich [17,1.4节,p.11]所介绍。   设X、Y为非空集。回想一下,从X到Y的映射h(由h:X→Y表示)具有这样的性质,即对于每个x?X,对应恰好一个y?Y。让aδb读作a接近b,对于元素a, b?X。集合Y称为映射h的范围(也称为图像)。集合X称为映射h的域(也称为预图像或前像)。   映射h:X→Y是连续的,假设对于元素a, b?X,每当aδb(即a和b接近),则h(a) δh(b)(即h(a)和h(b)接近),即h是连续的,h将X中的接近点映射到Y中的接近点。符号h(X)读作h(X)等于Y的子集,前提是h将X映射进(into)Y。在into的情况下,h(X) ?Y。如果h将X映射到(onto)Y,则h(X) = Y。这里将onto映射称为满射映射。   映射h:X→Y是一对一的,写成1?1(也是单射或可逆的),前提是h范围内的每个元素都对应于h的X域的唯一成员。换句话说,如果映射h是1?1的,那么h范围内的每幅图像在h的域中都有一个唯一的前像。映射h的逆表示为h?1。每当映射可逆时,则h?1(x) = x。既是1?1的又是onto的映射称为双射。有关映射的详细介绍,请参阅Gellert百科全书[18,14.5节,p.325ff]。   例3.22?(1-1的类型,onto映射)   考虑可逆映射h:X→Y的图像,这类似于每一侧都有一个手柄的头发梳子,其中梳子的每个尖齿都在由●表示的X中的成员x和由●表示的h(x) = Y中的成员y之间(图3.16(a)中的映射h既是1?1的又是onto的,图3.16(b)中的映射只是1?1的而不是onto的)。图?3.16(b)中的映射不是onto的,因为Y的一些成员不包括在映射中,即Y的成员(由●表示不连接到X中的成员)不包括在映射h的范围内。 图3.16?h:X→Y映射与非映射的类型 图3.16?h:X→Y映射与非映射的类型(续) ■   例3.23?(非映射)   每当X上的映射将多个成员映射到Y中的同一个y时,该映射就不是1?1的。例如,图?3.16(c)中的映射h不是1?1的,但却是onto的,因为Y的所有成员都包含在h的范围内。图3.16(d)中表示的映射h不是1?1的,也不是onto的,因为Y的一些成员不包括在h的范围内。在图3.16(e)中,X和Y之间的关系h不是映射,因为X中有一个成员x被同时映射到Y中的y1和y2(如图3.16(f)所示),即h没有将x映射到单个(唯一)Y的成员。   设X和Y为一对群。同源(也称同胚)是一个映射h:X→Y,假设映射h是1?1的(域中的每个元素只映射到范围内的一个元素)和onto的(h(X) = Y),而且映射h是连续的,并且逆映射h?1也是连续的。同源通常称为同源映射。换句话说,映射h是一个双射,而h是双连续的(即映射及其逆都是连续的)。 ■   例3.24?(路径映射到单个边)   设X = {,,}是图3.17所示的连通弧的轨迹。例如,顶点p1和p2之间的曲线段表示为。也设映射h:X→Y定义为 图3.17?连通边的轨迹映射到单个线段   映射h是1?1的,因为X中的每个点都映射到中的单个点。映射h是X到的onto映射,因为范围内的所有点都包含在映射中。对A, B?X,令AδB读作A接近B。观察到h是连续的,因为对范围中的h(x)和h(x′),X中xδx′映射到h(x) δh(x′)。最后,h?1也是连续的,因为h?1(x) δh?1(x′)映射到xδx′。因此,轨迹X同源于段。 ■   引理3.25   三角化平面区域中的每一对顶点之间都有轨迹。   证明:设p,q? cxK是一组顶点K上三角化平面区域中的一对顶点。每个顶点p?K连接到附近的顶点p′?K,并在边上。选择p″?K靠近p′,并在边上。重复此步骤,直到q是连通边序列、、..,、中的边的端点。这一系列连通的边在p和q之间形成一条轨迹。 ■   引理3.26   在三角化的有限有界平面区域中的每对神经之间都有一条轨迹。   证明:设p和q分别是一对神经NrvA(p)和NrvB(q)的核,位于三角化平面区域中。根据引理3.25,在核p和q之间有一条轨迹。 ■   例3.27?(神经之间的路径)   图3.18显示了一对神经NrvA(p)和NrvB(q)中的核p和q之间的样本轨迹。 图3.18?神经核之间连通边的轨迹 ■ 单元分裂轨迹    单元拓扑的一个重要副产品是识别具有匹配特征矢量的单元面(单元分裂瞬间单元中的组件),以及存在来自空间中单元面的集族(团块)的动态变化的分段连续映射,从时空到它们的描述。随着时间的推移,这些从父单元到其子单元的单元面映射序列的效果是Boltyanski?和Efremovich引入的Boltyanski?-Efremovich轨迹[17,1.4节,p.11],它引导父单元中的特征矢量(n-D顶点)到达具有匹配特征矢量的子单元。 ■  回想一下,Boltyanski?-Efremovich轨迹是一系列顶点之间的连通边序列,这些顶点的联合同源为单个线段,只有原始序列中的端点。就单元活动平面视图的三角剖分而言,主要结果是顶点之间轨迹的展开(随时间传播)使得追踪单元分裂树中的后代成为可能。   另一个重要的结果是通过在单元分裂期间从一系列流形中沿着特征矢量之间的轨迹移动一个非常小的两轮车来近似测地线。在不同顶点之间发现最短测地线取决于随着时间的推移,单元分裂的连续嵌入空间曲线(也称为扭曲曲线)的方式。有关空间曲线的介绍,请参见Hilbert和Cohn-Vossen [19]。在每个接合点,单元测地线在通过曲面上顶点的曲线中具有最小的曲率,并且在测地线的顶点处具有相同的切线。 3.14?形状之间的测地线轨迹   测地线是局部长度最小化曲线[20]。这里的重点是位于三角化平面区域里的测地线轨迹上的形状。测地线轨迹是三角化有限有界平面区域中顶点之间的所有轨迹中长度最短的轨迹。在极限情况下,测地线是直线上的一系列线段(或H.Weyl所说的大地线[21,p.115])。在实践中,测地线轨迹就像图3.18中的扭曲(摆动)轨迹。有关三角化图像目标形状的测地线的最新研究,请参阅Ahmad和Peters [22]。在该研究中,重点是在对形状的近似中使用直线和曲线测地线。在这里,重点转移到通过形状顶点之间的测地线轨迹来确定三角化形状的接近度。   例如,观察图3.19中那不勒斯早餐图片3中形状之间的许多可能的测地线轨迹。   例3.28?(形状顶点之间的测地线)   图3.19中那不勒斯早餐的三角剖分如图3.20(a)所示。一对形状shA(p)和shB(q)中顶点p、q之间的样本测地线是图3.19所示的红色线段序列——。例如,图3.20(b)中形状shA上的特定顶点p由shA(p)表示。类似地,图3.20(c)中形状shB上的顶点q由shB(q)表示。图3.20(c)中标记为shB的突出显示的黄色区域表示具有最大数量的三角形的神经,这些三 角形具有共同的核q。根据对形状上顶点的选择,测地线的长度会有所不同。以下是shA(p)和shB(q)之间的测地线样例。   测地线末端顶点的选择将取决于每个形状的最感兴趣的部分。 图3.20 三角化图像形状上的测地线样本 ■   定理3.29   在三角化的有限有界平面区域上的每对形状之间存在测地线轨迹。   证明:令cxK是有界平面区域的顶点集合K上的三角剖分。根据定义,每个平面形状shA都有一个边界bdy(shA),它是一条简单的闭合曲线。选择形状shA、shB? cxK。选择边界bdy(shA)上的顶点p和边界bdy(shB)上的顶点q。根据引理3.26,在p和q之间有一个轨迹。通过选择路径中每对可能顶点之间的最短轨迹,我们获得了p和q之间的测 地线。