Fast combinatorial vector field topology

This paper introduces a novel approximation algorithm for the fundamental graph problem of combinatorial vector field topology (CVT). CVT is a combinatorial approach based on a sound theoretical basis given by Forman's work on a discrete Morse theory for dynamical systems. A computational framework for this mathematical model of vector field topology has been developed recently. The applicability of this framework is however severely limited by the quadratic complexity of its main computational kernel. In this work, we present an approximation algorithm for CVT with a significantly lower complexity. This new algorithm reduces the runtime by several orders of magnitude and maintains the main advantages of CVT over the continuous approach. Due to the simplicity of our algorithm it can be easily parallelized to improve the runtime further.     

Morse complexes for shape segmentation and homological analysis: discrete models and algorithms

Morse theory offers a natural and mathematically‐sound tool for shape analysis and understanding. It allows studying the behavior of a scalar function defined on a manifold. Starting from a Morse function, we can decompose the domain of the function into meaningful regions associated with the critical points of the function. Such decompositions, called Morse complexes, provide a segmentation of a shape and are extensively used in terrain modeling and in scientific visualization. Discrete Morse theory, a combinatorial counterpart of smooth Morse theory defined over cell complexes, provides an excellent basis for computing Morse complexes in a robust and efficient way. Moreover, since a discrete Morse complex computed over a given complex has the same homology as the original one, but fewer cells, discrete Morse theory is a fundamental tool for efficiently detecting holes in shapes through homology and persistent homology. In this survey, we review, classify and analyze algorithms for computing and simplifying Morse complexes in the context of such applications with an emphasis on discrete Morse theory and on algorithms based on it.     

基于广义离散Morse理论的强关联规则挖掘

针对强关联规则的挖掘问题,提出构造事务数据库的单元复形,利用广义离散Morse理论发现强关联规则的方法。在基本的离散Morse理论和关联规则的基础上延伸得到广义离散Morse理论和强关联规则的定义,通过在事务数据库的单元复形上定义离散Morse函数挖掘强关联规则,例证表明该方法的可行性和高效性。     

一种基于离散Morse理论的优化模型及其应用

根据Forman 的离散Morse 理论的特点, 提出一种基于离散Morse 理论的优化模型. 该模型在3 维及以上空间点构建离散Morse 函数进行最优化, 得到了问题的最优解或近似最优解. 同时, 证明了所构建的函数确实是复形上的离散Morse 函数. 利用4 个典型的测试函数进行仿真实验, 结果表明了该模型的有效性, 且该模型尤其适用于解决大数据量的优化问题. 从聚类的过程即目标函数的优化过程这一角度考虑, 尝试将优化模型应用于聚类分析. 仿真实验结果表明, 所提出的算法能较好地划分数据点重叠区域的聚类形状, 验证了所提出算法的可行性和有效性.     

Dimension-independent simplification and refinement of Morse complexes

Ascending and descending Morse complexes, determined by a scalar field f defined over a manifold M, induce a subdivision of M into regions associated with critical points of f, and compactly represent the topology of M. We define two simplification operators on Morse complexes, which work in arbitrary dimensions, and we define their inverse refinement operators. We describe how simplification and refinement operators affect Morse complexes on M, and we show that these operators form a complete set of atomic operators to create and update Morse complexes on M. Thus, any operator that modifies Morse complexes on M can be expressed as a suitable sequence of the atomic simplification and refinement operators we have defined. The simplification and refinement operators also provide a suitable basis for the construction of a multi-resolution representation of Morse complexes.     

Topology verification for isosurface extraction

The broad goals of verifiable visualization rely on correct algorithmic implementations. We extend a framework for verification of isosurfacing implementations to check topological properties. Specifically, we use stratified Morse theory and digital topology to design algorithms which verify topological invariants. Our extended framework reveals unexpected behavior and coding mistakes in popular publicly available isosurface codes.     

Feature correspondences using Morse Smale complex

Establishing corresponding features on two non-rigidly deformed 3D surfaces is a challenging and well-studied problem in computer graphics. Unlike previous approaches that constrain the matching between feature pairs using isometry-invariant distance metrics, we constrain the matching using a discrete connectivity graph derived from the Morse–Smale complex of the Auto Diffusion Function. We observed that the graph remains stable even for surfaces differing by topology or by significant deformation. This algorithm is simple to implement and efficient to run. When tested on a range of examples, our algorithm produces comparable results with state-of-art methods on surfaces with strong isometry but with greatly improved efficiency, and often gets better correspondences on surfaces with larger shape variances.     

Construction of harmonic map flows through the method of discrete Morse flows

By the method of discrete Morse flows, we construct the Morse flow of harmonic map from a Riemannian manifold with measurable and bounded metric into that with Alexander non-positive curvature. The construction is directly derived without isometrically embedding of the target manifold into Euclidean space. Our method will be in force in the case, as treated in [11], where a target manifold has the bounded positive curvature.     

Extraction Of Feature Lines On Surface Meshes Based On Discrete Morse Theory

We present an approach for extracting extremal feature lines of scalar indicators on surface meshes, based on discrete Morse Theory. By computing initial Morse‐Smale complexes of the scalar indicators of the mesh, we obtain a candidate set of extremal feature lines of the surface. A hierarchy of Morse‐Smale complexes is computed by prioritizing feature lines according to a novel criterion and applying a cancellation procedure that allows us to select the most significant lines. Given the scalar indicators on the vertices of the mesh, the presented feature line extraction scheme is interpolation free and needs no derivative estimates. The technique is insensitive to noise and depends only on one parameter: the feature significance. We use the technique to extract surface features yielding impressive, non photorealistic images.     

Perfect discrete Morse functions on 2-complexes

This paper is focused on the study of perfect discrete Morse functions on a 2-simplicial complex. These are those discrete Morse functions such that the number of critical i-simplices coincides with the ith Betti number of the complex. In particular, we establish conditions under which a 2-complex admits a perfect discrete Morse function and conversely, we get topological properties necessary for a 2-complex admitting such kind of functions. This approach is more general than the known results in the literature (Lewiner et al., 2003), since our study is not restricted to surfaces. These results can be considered as a first step in the study of perfect discrete Morse functions on 3-manifolds.     

拓扑结构正确的三线性插值曲面的三角片逼近

在等值面的三角片逼近问题中，采样点的选择对于逼近等值面拓扑结构的正确性和逼近的精确性都非常关键．现有的Marching Cubes以及对其进行改进的方法缺乏对原始曲面拓扑结构的考虑，通常选择同类采样点，无法保证逼近等值面具有正确的拓扑结构．为解决上述问题，将Morse理论的基本思想引入到等值面逼近问题中，提出基于拓扑复杂度的等值面逼近的新方法，该方法根据体元内部曲面拓扑复杂度不同，自适应地提取两类等值点作为采样点：临界点和边界等值点．由于临界点是反映曲面拓扑结构的关键点，因此，无论原始曲面的拓扑结构复杂与否，新方法都能保证逼近等值面具有正确的拓扑结构、较高的逼近精度且基本不增加计算量和数据量．用实例对新方法和已有方法的逼近结果做了比较．     

Robust Morse decompositions of piecewise constant vector fields

In this paper, we introduce a new approach to computing a Morse decomposition of a vector field on a triangulated manifold surface. The basic idea is to convert the input vector field to a piecewise constant (PC) vector field, whose trajectories can be computed using simple geometric rules. To overcome the intrinsic difficulty in PC vector fields (in particular, discontinuity along mesh edges), we borrow results from the theory of differential inclusions. The input vector field and its PC variant have similar Morse decompositions. We introduce a robust and efficient algorithm to compute Morse decompositions of a PC vector field. Our approach provides subtriangle precision for Morse sets. In addition, we describe a Morse set classification framework which we use to color code the Morse sets in order to enhance the visualization. We demonstrate the benefits of our approach with three well-known simulation data sets, for which our method has produced Morse decompositions that are similar to or finer than those obtained using existing techniques, and is over an order of magnitude faster.     

Morse set classification and hierarchical refinement using Conley index

Morse decomposition provides a numerically stable topological representation of vector fields that is crucial for their rigorous interpretation. However, Morse decomposition is not unique, and its granularity directly impacts its computational cost. In this paper, we propose an automatic refinement scheme to construct the Morse Connection Graph (MCG) of a given vector field in a hierarchical fashion. Our framework allows a Morse set to be refined through a local update of the flow combinatorialization graph, as well as the connection regions between Morse sets. The computation is fast because the most expensive computation is concentrated on a small portion of the domain. Furthermore, the present work allows the generation of a topologically consistent hierarchy of MCGs, which cannot be obtained using a global method. The classification of the extracted Morse sets is a crucial step for the construction of the MCG, for which the Poincare′ index is inadequate. We make use of an upper bound for the Conley index, provided by the Betti numbers of an index pair for a translation along the flow, to classify the Morse sets. This upper bound is sufficiently accurate for Morse set classification and provides supportive information for the automatic refinement process. An improved visualization technique for MCG is developed to incorporate the Conley indices. Finally, we apply the proposed techniques to a number of synthetic and realworld simulation data to demonstrate their utility.     

一种基于离散梯度向量域的可视化应用研究

研究了基于莫尔斯理论的离散梯度向量域方法，并将其应用于拓扑可视化。用该方法和流形可视化方法分别演示了Moebius带和海螺并做了分析对比，并介绍了相关理论，分析了如何构造离散梯度向量域，最后完成向量域的演示并给出了实验结果证明其有效性。该方法可直接应用于计算机辅助设计和虚拟模拟的演示。     

Fully deformable 3D digital partition model with topological control

We propose a purely discrete deformable partition model for segmenting 3D images. Its main ability is to maintain the topology of the partition during the minimization process. To do so, our main contribution is a new definition of multi-label simple points (ML simple point) that is easily computable. An ML simple point can be relabeled without modifying the overall topology of the partition. The definition is based on intervoxel properties, and uses the notion of collapse on cubical complexes. This work is an extension of a former restricted definition (Dupas et al., 2009) that prohibits the move of intersections of boundary surfaces. A deformation process is carried out with a greedy energy minimization algorithm. A discrete area estimator is used to approach at best standard regularizers classically used in continuous energy minimizing methods. We illustrate the potential of our approach with the segmentation of 3D medical images with known expected topology.     

Continuity of operators on continuous and discrete time streams

We consider the semantics of networks processing streams of data from a complete metric space. We consider two types of data streams: those based on continuous time (used in networks of physical components and analog devices), and those based on discrete time (used in concurrent algorithms). The networks are both governed by global clocks and together model a huge range of systems. Previously, we have investigated these two types of networks separately. Here we combine their study in a unified theory of stream transformers, given as fixed points of equations. We begin to develop this theory by using the standard mathematical techniques of topology to prove certain computationally desirable properties of these semantic functions, notably continuity, which is significant for models of a physical system, according to Hadamard’s principle.     

基于离散点的光线跟踪的研究

在计算机图形中,光线跟踪是获得具有正确的反射、折射和阴影等效果的更加真实的图像的一个有效方法.研究了基于离散点造型的光线跟踪方法,探讨了在只有物体的离散采样点集合而没有点之间的连接信息的情况下,如何进行光线与物体求交的具体过程.     

Consensus strategy for a class of multi‐agents with discrete second‐order dynamics

This paper investigates consensus strategies for a group of agents with discrete second‐order dynamics under directed communication topology. Consensus analysis for both the fixed topology and time‐varying topology cases is systematically performed by employing a novel graph theoretic methodology as well as the classical nonnegative matrix theory. Furthermore, it is shown that the necessary and sufficient condition for the agents under fixed communication topology to reach consensus is that the communication topology has a spanning tree; and sufficient conditions for the agents to reach consensus when allowing for the dynamically changing communication topologies are also given. Finally, an illustrative example is provided to demonstrate the effectiveness of the proposed results. Copyright © 2011 John Wiley & Sons, Ltd.     

Geometrical Dissipativity‐Based Output Synchronization of Discrete Dynamical Networks with Non‐Identical Nodes

In this paper, we investigate the generalized output synchronization problem for discrete dynamic networks with non‐identical nodes. We consider two cases: output synchronization for fixed topology and arbitrary switching topology. For the first case, we establish several criteria for generalized output synchronization using the geometrical dissipativity property. For the other case, we present a LaSalle invariance principle for discrete switched systems, based on which criteria for generalized output synchronization under arbitrary switching topology are given. Finally, an example is provided to illustrate the effectiveness of the main results.     

Detection and classification of topological evolution for linear metamorphosis

The advantage of functional methods for shape metamorphosis is the automatic generation of intermediate shapes possible between the key shapes of different topology types. However, functional methods have a serious problem: shape interpolation is applied without topological information and thereby the time values of topological changes are not known. Thus, it is difficult to identify the time intervals for key frames of shape metamorphosis animation that faithfully visualize the topological evolution. Moreover, information on the types of topological changes is missing. To overcome the problem, we apply topological analysis to functional linear shape metamorphosis and classify the type of topological evolution by using a Hessian matrix. Our method is based on Morse theory and analyzes how the critical points appear. We classify the detected critical points into maximum point, minimum point, and saddle point types. Using the types of critical points, we can define the topological information for shape metamorphosis. We illustrate these methods using shape metamorphosis in 2D and 3D spaces.