英语原文共 10 页，支付完成后下载完整资料

在大规模三角网格地形上提取莫尔斯复形

摘要

本文研究的是基于离散莫尔斯理论的不规则三角网（TIN）上的高效计算和简化莫尔斯复合体的问题。为了实现上述目标，本文采用的方法是根据由地形高程定义的离散莫尔斯梯度场开发紧凑编码（适合与仅存储其顶点和三角形的任何TIN数据结构组合）。文中展示了如何根据TIN顶点给出的高程值计算离散莫尔斯梯度场，以及如何有效地简化它以减少关键元素的数量。同时本文中还展示了提取莫尔斯复合体中的单元以及连接离散梯度场中的关键元素的图算法，这种算法对于大面积地形的有效性和可扩展性通过实验得到了验证。我们将本文中的方法应用到了两种TIN数据结构上，分别是IA和PR-star四叉树。

关键词

离散莫尔斯理论、形态学简化、空间拓扑数据结构

第一章：引言

莫尔斯理论原本是用于地形分析的形态学方法，这种理论通过在标量场上计算分解体（称为莫尔斯分解体），通过这种分解体可以得到标量场上关键点的影响区域。然而，莫尔斯理论仅仅适用于连续函数，而在实际应用中，我们需要处理离散的地形数据。因此，最近的研究集中于组合拓扑方法，可以避免计算导数从而降低数据中噪声的影响。Forman的离散莫尔斯理论将莫尔斯理论扩展为单纯复形（也就是二维的三角网）。同时这种离散公式在开发鲁棒离散算法方面具有实际应用，克服了先前莫尔斯分解算法在离散领域的局限性。

本文的工作集中在根据离散地形的TIN数据结构计算离散莫尔斯分解体。为此，首先从TIN数据结构中计算离散梯度场，TIN数据结构中的顶点，边和三角形都会对离散梯度场的计算造成影响。然而，储存了所有顶点，边和三角形的TIN数据结构会造成计算上的冗余。为了解决这个问题，我们为Forman梯度引入了一种紧凑的编码，它可以仅附加到三角形上。因此这种编码适合与任何仅储存顶点和三角形的TIN数据结构结合，例如，IA。此外，我们提出了PR-star四叉树的一种实现方法，这种实现方法可以通过在网格上进行空间索引计算出网格的局部连通性。PR-star四叉树不仅有上述提到的存储方面的优势，并且在计算Forman梯度场和TIN数据结构上离散莫尔斯复合体也十分高效。

当通过形态学的方法（如莫尔斯分解）描述大尺寸地形时，一个容易产生的缺陷是由于存在噪声和不感兴趣的地形特征，所得到的大尺寸的地形分割。我们提出了一种可以简化大规模地形中的形态学表示的算法，称作消除。消除是指移除梯度场上积分线两端的关键点。这种简化的算法允许在不同的拓扑精度水平上提取形态特征（莫尔斯分解体单元和连接关键点的网络）。

本文的其余部分安排如下。第二章介绍了关于连续和离散莫尔斯理论的一些基本概念。第三章介绍了计算莫尔斯分解和空间索引的相关工作。在第四章中，我们描述了紧凑的Forman梯度编码及其在IA和PR-star四叉树这两种TIN数据结构上的实现。在第五章中，我们提出了在离散情况下莫尔斯复合体的定义。在第六章中，我们描述了简化算法（消除）及其在IA和PR星数据结构上的实现。在第七章中，我们对实验的结果进行了分析。在第八章中，我们进行了总结并进行了展望。

第二章：背景知识

这一章介绍关于莫尔斯理论以及离散莫尔斯理论的一些基本概念。莫尔斯理论研究了拓扑结构与在拓扑结构上定义的标量函数的关键点之间的关系。考虑一个定义在上的二阶可微实值函数f，当（）满足 时，称为函数的关键点，否则，称其为正则点。将函数的海塞矩阵（二阶偏导数矩阵）标记为，如果海塞矩阵的行列式不等于0，点为非退化点。负特征值的数量叫做关键点p的莫尔斯指数。在二维条件条件下，关键点是最小点，最大点和鞍点，它们分别是莫尔斯指数0,2和1的关键点。

定义一个标量场为，其中f是在定义在上的二阶可微实值函数（可以理解为地面的高程值），是中的点的映射。如果函数的所有关键点都是非退化的，则称函数为莫尔斯函数。过任意正则点均有一条沿f梯度方向的曲线，该曲线称为积分线。收敛于指数为的关键点p的积分线称为p点的下降i-流形，起始于莫尔斯指数为i的关键点p的积分线称为p点的上升-流形。上升/下降流形是成对不相交的，并且将分解为单元，所有下降（上升）流形的集合形成下降（上升）莫尔斯复合体。

在离散莫尔斯理论中也有对应的概念，它在单元的复合体中的所有单元上定义了离散莫尔斯函数。在定义在上的几何独立的点集₀,V₂,hellip;,V_K上，称K-单形为S中K 1个点的凸包。于是在三角网Sigma;上，我们将三角形，边和顶点分别称为2，1-和0-单形。

函数F：，如果所有的i-单形的函数值比在其边界上的（）-单形的函数值大，而且其函数值小于（）-单形的函数值，至多存在一个例外，则称函数F为离散莫尔斯函数。也就是说离散莫尔斯函数是一个随着维数增长而增长的实数函数。如果存在例外的话，定义一对单元，叫做梯度对。如果没有这样的例外（即的函数值和与其相邻的单形均满足随着维数增长而增长），那么称为指数为p的关键单形。一个1-非关键单形既可以与另一个2-非关键单形组成一个梯度对，也可以与0-非关键单形组成梯度对。梯度对可以看作一个箭头，其头部是i-单形，尾部是（）-单形。如果不是任何箭头的头部和尾部，则称其为关键单形。

图一 Forman梯度场在地形三角网上的例子，红色的点代表关键

三角形（最大点），绿色的点表示关键边（鞍点），蓝色点代表关键顶点（最小点）。

V路径是单形对[]的序列，其中和位于的边界上，并且()是配对的单形。其中i = 0，...，q。所有单形对和在Sigma;上关键单形的集合组成了离散莫尔斯梯度场V（不存在闭合的V路径）。图一展示了一个简化的地形数据集上的离散莫尔斯梯度场。V路径对应莫尔斯理论上的积分线。我们称任何满足以下条件的V路径为分界线V_j路径，分界线V_j路径为单形对[]的序列，其中和分别是j-单形和（j-1）-单形。在三角形网格Sigma;中，我们有分界线V₁路径连接关键边（对应鞍点）到关键点（对应最小值），以及分界线V₂路径连接关键三角形（对应于最大值）到关键边（对应鞍点）。

第三章：研究现状

除了上一章节中的离散莫尔斯理论之外，还有有几种方法可以将莫尔斯理论拓展到离散领域，并在离散的情况下表示出莫尔斯复合体和Morse-Smale复合体。Banchoff基于莫尔斯理论提出了分段线性的流形和函数。

最近，基于离散莫尔斯理论的算法收到广泛关注。有相关论文基于此开发了用于计算莫尔斯和MS复合体的鲁棒离散算法。克服了先前技术的内在限制。已经针对规则网格或四面体网格开发了基于离散莫尔斯理论的算法。有研究者提出了一种用于计算大型二维结构网格的二维MS复合体的并行算法。还有论文中讨论了生成更精确几何的算法，从而确定了MS复合体的正确连通性。

已经为点，多边形，三维物体和三角网格提出了各种层次空间索引。在有的论文中，引入了四面体网格的一系列空间索引，称为四面体树。对于地图、三角网和三维点来说。这样的索引仅在其叶节点中包含几何实体，因此，四面体树的形状与实体的插入顺序无关。

PR-star八叉树，是一种与四面体网格在基本概念上不同的数据结构，使用可嵌入的网格进行拓扑结构的索引。该数据结构已使用Robins等人的Forman梯度流式计算算法实现了从地形和体数据集中提取形态特征的目标。其他方法通过使用空间索引来减少对核外或内存密集型网格处理的内存需求，或者通过为单形网格开发简化的数据结构来提出进行局部计算的方法。

第四章：为TIN数据结构和离散莫尔斯梯度场编码

当使用正方形网格（RSG）表示地形时，Forman梯度场以位向量的形式被隐式编码。当地形被表示为单形网格（三角网），为了计算同时计算离散莫尔斯复合体和同源性和持久同源性，将单形网格编码为IG这种数据结构。IG的一个更紧凑的简化版本，专用于单形网格叫做SIG。SIG编码了三角网中所有单形、三角形（2-单形）与其边（1-单性）之间的边界关系、对于每条边对其两个顶点进行编码、对于每个顶点每条相关的边都会被编码。

IA是一种更为紧凑的单形网格的数据结构，这种数据结构仅编码0-单形和2-单形。对于三角形网格Sigma;，IA数据结构仅编码顶点和三角形，对于每个三角形，编码其三个顶点及其三个相邻三角形的索引，对于每个顶点，编码它的坐标加上顶点中的一个三角形的索引已经有相关的文献证明，IA数据结构平均占用的空间是三角形网格中IG数据结构的2.8倍，是SIG数据结构的2.4倍。PR-star四叉树提供了一种比IA数据结构更紧凑的编码方式，它仍然只编码顶点和三角形，但使用完全不同的方法来进行对网格连通性和拓扑关系的处理。

4.1 PR-star四叉树

PR-star四叉树是二维版本的PR-star八叉树，使用这种数据结构进行空间索引时可以有效地生成拓扑结构。PR-star四叉树是基于基于点区域四叉树(PR四叉树)，即点数据的空间索引。由PR-四叉树定义的域分解由单个参数控制，我们将其表示为k_v，表示可以被叶节点索引到的的最大的点数。在PR-quadtree中将新点插入完整的叶子会导致叶子分裂，并且其索引点将在其四个子节点之间重新分配，因此，由PR-四叉树引起的域分解独立于其点的插入顺序。

PR-star四叉树对三角网Sigma;的顶点和三角形进行编码，包括：(1) 顶点数组P，编码了Sigma;的几何形状。(2)索引三角形的数组T，其中每个元素根据其三个顶点的索引用P表示;(3)作为辅助数据结构的PR四叉树N，其叶节点可以索引顶点数组P中的子集。图二是PR-star四叉树的一个例子。

图二 PR-star四叉树的一个叶节点（KV=4），编码一组顶点和由这些顶点组成的所有三角形，棕色的三角形是完全由叶子索引的三角形（蓝色矩形）；黄色的三角形包含了入射到叶子内部的顶点；灰色的那些几何上与叶子相交但不会入射到它的内部顶点（也就是说没有被叶节点索引）

还有有种更紧凑的PR星形四叉树叶子（通过重新索引数组P和T，利用四叉树提供的空间局部性来实现）。除了与四叉树相关的分层信息（即从节点到其父节点及其子节点的指针），每个叶节点n_L包括：n_L中包含的顶点P的索引范围v_start和v_end；完全包含在n_L中的三角形的T中的索引t_start和t_end的范围；指向入射在这些顶点中的T的剩余三角形列表的指针，即每个这样的三角形在n_L的域内具有至少一个顶点并且在域外至少具有一个顶点。

IA和PR-star四叉树数据结构对于网格的三角形-顶点具有相同的编码关系，即每个三角形与其顶点之间的边界关系，需要的项数满足欧拉公式：，因为在三角网格中。IA数据结构需要额外的的项数来编码其他拓扑关系，我们称之为拓扑开销。相反，PR星形四叉树的每个节点需要用于空间索引的项目，和| T | 用于存储三角形列表，其中表示三角形出现的四叉树节点的平均数量（即，1le;chi;le;3）。PR星形四叉树的拓扑开销就变成了|T| 9|N|，根据我们的实验结果，的估计值为1.5，节点数符合公式|N|asymp;|P|/k_v，根据上述的公式计算可得PR四叉树的拓扑开销约为4|P|。

4.2 为Forman梯度场编码

我们在此描述的是与三角网Sigma;相关联的Forman梯度场V的编码，其中关于Forman梯度V的信息仅附加到三角形上。编码将Sigma;中的每个三角形sigma;与涉及其面的矢量对的子集相关联，因此，它针对IA和PR星数据结构进行全局存储。具体来说，sigma;编码所有矢量对，即（tau;1，sigma;#39;），对应于

资料编号：[3134]