Estimating and quantifying uncertainties on level sets using the Vorob'ev expectation and deviation with Gaussian process models

Several methods based on Kriging have recently been proposed for calculating a probability of failure involving costly-to-evaluate functions. A closely related problem is to estimate the set of inputs leading to a response exceeding a given threshold. Now, estimating such a level set—and not solely its volume—and quantifying uncertainties on it are not straightforward. Here we use notions from random set theory to obtain an estimate of the level set, together with a quantification of estimation uncertainty. We give explicit formulae in the Gaussian process set-up and provide a consistency result. We then illustrate how space-filling versus adaptive design strategies may sequentially reduce level set estimation uncertainty.

Densities with Spherical Level Sets in the Gauss-exponential Domain

2000 Mathematics Subject Classification: 60F05, 60B10.

Efficient Output-Sensitive Construction of Reeb Graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. This paper describes a near-optimal two-step algorithm that constructs the Reeb graph of a Morse function defined over manifolds in any dimension. The algorithm first identifies the critical points of the input manifold, and then connects these critical points in the second step to obtain the Reeb graph. A simplification mechanism based on topological persistence aids in the removal of noise and unimportant features. A radial layout scheme results in a feature-directed drawing of the Reeb graph. Experimental results demonstrate the efficiency of the Reeb graph construction in practice and its applications.

Topology-Guided Tessellation Of Quadratic Elements

Topology-based methods have been successfully used for the analysis and visualization of piecewise-linear functions defined on triangle meshes. This paper describes a mechanism for extending these methods to piecewise-quadratic functions defined on triangulations of surfaces. Each triangular patch is tessellated into monotone regions, so that existing algorithms for computing topological representations of piecewise-linear functions may be applied directly to the piecewise-quadratic function. In particular, the tessellation is used for computing the Reeb graph, a topological data structure that provides a succinct representation of level sets of the function.

Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O(nlogn+nlogg(loglogg)3) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O(nlogn(loglogn)3) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O(n2) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice.

Constructing Reeb Graphs using Cylinder Maps

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. In this video, we describe a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Arcs in the Reeb graph are computed in the second step using a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The algorithm is also able to handle non-manifold domains.

Symmetry in Scalar Field Topology

Study of symmetric or repeating patterns in scalar fields is important in scientific data analysis because it gives deep insights into the properties of the underlying phenomenon. Though geometric symmetry has been well studied within areas like shape processing, identifying symmetry in scalar fields has remained largely unexplored due to the high computational cost of the associated algorithms. We propose a computationally efficient algorithm for detecting symmetric patterns in a scalar field distribution by analysing the topology of level sets of the scalar field. Our algorithm computes the contour tree of a given scalar field and identifies subtrees that are similar. We define a robust similarity measure for comparing subtrees of the contour tree and use it to group similar subtrees together. Regions of the domain corresponding to subtrees that belong to a common group are extracted and reported to be symmetric. Identifying symmetry in scalar fields finds applications in visualization, data exploration, and feature detection. We describe two applications in detail: symmetry-aware transfer function design and symmetry-aware isosurface extraction.

Output-Sensitive Construction of Reeb Graphs

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. This paper describes a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds or non-manifolds in any dimension. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Critical points correspond to nodes in the Reeb graph. Arcs connecting the nodes are computed in the second step by a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The paper also describes a scheme for controlled simplification of the Reeb graph and two different graph layout schemes that help in the effective presentation of Reeb graphs for visual analysis of scalar fields. Finally, the Reeb graph is employed in four different applications-surface segmentation, spatially-aware transfer function design, visualization of interval volumes, and interactive exploration of time-varying data.

Computing Reeb Graphs as a Union of Contour Trees

The Reeb graph of a scalar function tracks the evolution of the topology of its level sets. This paper describes a fast algorithm to compute the Reeb graph of a piecewise-linear (PL) function defined over manifolds and non-manifolds. The key idea in the proposed approach is to maximally leverage the efficient contour tree algorithm to compute the Reeb graph. The algorithm proceeds by dividing the input into a set of subvolumes that have loop-free Reeb graphs using the join tree of the scalar function and computes the Reeb graph by combining the contour trees of all the subvolumes. Since the key ingredient of this method is a series of union-find operations, the algorithm is fast in practice. Experimental results demonstrate that it outperforms current generic algorithms by a factor of up to two orders of magnitude, and has a performance on par with algorithms that are catered to restricted classes of input. The algorithm also extends to handle large data that do not fit in memory.

Some questions on integral geometry on noncompact symmetric spaces of higher rank

Let be a noncompact symmetric space of higher rank. We consider two types of averages of functions: one, over level sets of the heat kernel on and the other, over geodesic spheres. We prove injectivity results for functions in which extend the results in Pati and Sitaram (Sankya Ser A 62:419-424, 2000).

Elliptic Object Detection Based on Shape Preserving and Active Contour

本文通过形状约束方程(组)与一般主动轮廓模型结合,将目标形状与主动轮廓模型融合到统一能量泛函模型中,提出了一种形状保持主动轮廓模型即曲线在演化过程中保持为某一类特定形状。模型通过参数化水平集函数的零水平集控制演化曲线形状,不仅达到了分割即目标的目的,而且能够给出特定目标的定量描述。根据形状保持主动轮廓模型,建立了一个用于椭圆状目标检测的统一能量泛函模型,导出了相应的Euler-Lagrange常微分方程并用水平集方法实现了椭圆状目标检测。此模型可以应用于眼底乳头分割,虹膜检测及相机标定。实验结果表明,此模型不仅能够准确的检测出给定图像中的椭圆状目标,而且有很强的抗噪、抗变形及遮挡性能。

基于形状保持主动轮廓模型长直条的检测

通过形状约束方程(组)与一般主动轮廓模型结合,将目标形状与主动轮廓模型融合到统一能量泛函模型中,提出一种形状保持主动轮廓模型。模型通过参数化水平集函数的零水平集表示某一类特定形状,不仅达到了分割即目标的目的,而且能够给出特定目标的定量描述。根据形状保持主动轮廓模型,建立一个用于长直条状目标检测的统一能量泛函模型,导出相应的Euler-Lagrange常微分方程并用水平集方法实现了长直条状区域的检测。此形状保持模型的一种特殊情况可以用于直线状地平(海天)线提取。实验结果表明,该模型不仅能够准确地检测出给定图像中的长直条状区域而且有很强的抗噪、抗变形及遮挡性能。