Search

Real-world data sets produce unmanageably large contour trees because of noise. Contour Tree Simplification (CTS) would remove small scale branches, and maintain essential structure of data. Despite multiple measures of importance (MOIs) available, conventional CTS approaches often use a single MOI, which is not enough in evaluating the importance of branches in the CTS. This paper proposes an importance-driven CTS approach. The proposed approach combines multiple MOIs through the introduction of various concepts to maximize advantages of each MOI. In the attribute space, various attributes of a branch are organized in a single space. The concept of the importance triangle is used to evaluate the importance of a branch by size of the importance triangle. It considers the whole attribute space and gives better evaluation of importance. Finally, new importance values of branches are compared in the importance space to make simplification decisions.

Topological simplification of scalar and vector fields is well-established as an effective method for analysing and visualising complex data sets. For multi-field data, topological analysis requires simultaneous advances both mathematically and computationally. We propose a robust multivariate topology simplification method based on ``lip''-pruning from the Reeb Space. Mathematically, we show that the projection of the Jacobi Set of multivariate data into the Reeb Space produces a Jacobi Structure that separates the Reeb Space into simple components. We also show that the dual graph of these components gives rise to a Reeb Skeleton that has properties similar to the scalar contour tree and Reeb Graph, for topologically simple domains. We then introduce a range measure to give a scaling-invariant total ordering of the components or features that can be used for simplification. Computationally, we show how to compute Jacobi Structure, Reeb Skeleton, Range and Geometric Measures in the Joint Contour Net (an approximation of the Reeb Space) and that these can be used for visualisation similar to the contour tree or Reeb Graph., Comment: Under Review in Journal

A contour tree is a good graphical tool for representing the spatial relations of contour lines and has many applications in map generalization, map annotation, terrain analysis, etc. A new method for generating contour trees by introducing a Voronoi-based interior adjacency concept is proposed in this paper. The immediate interior adjacency set is employed to identify all of the children contours of each contour without contour elevations. It has advantages over existing methods such as the geometric method and the region growing-based method.

This paper develops an exploratory method for analyzing the spatial relationship between two continuous surfaces. First, we classify the spatial relationship between two continuous surfaces into two categories: a "local relationship" and a "global relationship", and mathematically formulate these relationships. Second, we propose an index for the local relationship between two continuous surfaces. Third, we introduce a "contour tree" of a continuous surface, describe a qualitative characteristic of a continuous surface using a contour tree, and propose a method for exploring both local and global relationships. Last we apply the method to numerical examples and then show its effectiveness.

We revisit the classical problem of computing the contour tree of a scalar field $$f:\mathbb {M}\rightarrow \mathbb {R}$$f:MźR, where $$\mathbb {M}$$M is a triangulation of a ball in $$\mathbb {R}^d$$Rd. The contour tree is a fundamental topological structure that tracks the evolution of level sets of f and has numerous applications in data analysis and visualization. All existing algorithms begin with a global sort of at least all critical values of f, which can require (roughly) $$\Omega (n\log n)$$Ω(nlogn) time, where n is the number of vertices of the mesh. Existing lower bounds show that there are pathological instances where this sort is required. We present the first algorithm whose time complexity depends on the contour tree structure, and avoids the global sort for non-pathological inputs. (We assume that the Morse degree of the function f at any point is at most 3.) If C denotes the set of critical points in $$\mathbb {M}$$M, the running time is roughly $$O(N+\sum _{v \in C} \log \ell _v)$$O(N+źvźCloglv), where $$\ell _v$$lv is the depth of v in the contour tree and N is the total complexity of $$\mathbb {M}$$M. This matches all existing upper bounds, but is a significant asymptotic improvement when the contour tree is short and fat. Specifically, our approach ensures that any comparison made is between nodes that are either adjacent in $$\mathbb {M}$$M or in the same descending path in the contour tree, allowing us to argue strong optimality properties of our algorithm. Our algorithm requires several novel ideas: partitioning $$\mathbb {M}$$M in well-behaved portions, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis.

When the data are unevenly distributed and the behaviour of a function changes abruptly, the approximant can present undue oscillations. We present an algorithm to identify a domain decomposition, such that on each subdomain the behaviour of the function is sufficiently homogeneous in order to calculate separate approximants and to blend them together. © 2013 IMACS. Published by Elsevier B.V. All rights reserved.

Millions of people worldwide suffer from fragility fractures, which cause significant morbidity, financial costs and even mortality. The gold standard to quantify structural properties of trabecular bone is based on the morphometric parameters obtained from μCT images of clinical bone biopsy specimens. The currently used image processing approaches are not able to fully explain the variation in bone strength. In this study, we introduce the contour tree connectivity (CTC) as a novel morphometric parameter to study trabecular bone quality. With CTC, we calculate a new connectivity measure for trabecular bone by using contour tree representation of binary images and algebraic graph theory. To test our approach, we use trabecular bone biopsies obtained from 55 female patients. We study the correlation of CTC with biomechanical test results as well as other morphometric parameters obtained from μCT. The results based on our dataset show that CTC is the 3 rd best predictive feature of ultimate bone strength after bone volume fraction and degree of anisotropy.

We propose a novel technique for building geometry-preserving topological landscapes. Our technique creates a direct correlation between a scalar function and its topological landscape. This correlation is accomplished by introducing the notion of geometric proximity into the topological landscapes, reflecting the distance of topological features within the function domain. Furthermore, this technique enables direct comparative analysis between scalar functions, as long as they are defined on the same domain.We describe a construction technique that consists of three stages: contour tree computation, contour tree layout, and landscape construction. We provide a detailed description for the latter two steps. For the contour tree layout stage, we discuss dimension reduction and edge routing techniques that produce a drawing of the contour tree on the plane that preserves the geometric proximity. For the landscape construction stage, we develop a contour construction algorithm that takes the contour tree layout as an input, adds contours at heights that correspond to saddles of the contour tree, and produces a contour map. After an additional triangulation step, this construction method results in the landscape that has the same contour tree as the original function.

Contours, the connected components of level sets, play an important role in understanding the global structure of a scalar field. In particular their nesting behavior and topology – often represented in form of a contour tree – have been used extensively for visualization and analysis. However, traditional contour trees only encode structural properties like number of contours or the nesting of contours, but little quantitative information such as volume or other statistics. Here we use the segmentation implied by a contour tree to compute a large number of per-contour (interval) based statistics of both the function defining the contour tree as well as other co-located functions. We introduce a new visual metaphor for contour trees, called topological cacti, that extends the traditional toporrery display of a contour tree to display additional quantitative information as width of the cactus trunk and length of its spikes. We apply the new technique to scalar fields of varying dimension and different measures to demonstrate the effectiveness of the approach.

We present an algorithm to compute the connected components of upper or lower level sets from level lines. The running time is O (n + |τ|), where n is the size of the image and |τ| is the number of level lines.

The contour tree is an abstraction of a scalar field that encodes the nesting relationships of isosurfaces. We show how to use the contour tree to represent individual contours of a scalar field, how to simplify both the contour tree and the topology of the scalar field, how to compute and store geometric properties for all possible contours in the contour tree, and how to use the simplified contour tree as an interface for exploratory visualization.

We present an I/O-efficient version of an algorithm for simplifying contour trees of two- and three-dimensional scalar fields described by Carr et al. [7]. Our algorithm uses optimal ${\mathcal{O}}(Sort(N))={\mathcal{O}}(\frac{N}{B}\log_{M/B} \frac{N}{B})$ I/Os, where N is the size of the contour tree, M the size of main memory and B the disk block size.

In this video, we describe our experiences in implementing an algo-rithm to compute time-varying contour trees and highlight the chal-lenges in applying this algorithm to real-world scientific datasets. For ease of illustration we restrict our explanations to contour trees of time-varying functions defined on the plane.

Cartograms, which are also referred to as value-by-area maps, are a useful and intuitive way to visualize statistical data about a set of regions like countries, states or provinces. The size of a region in a cartogram corresponds to a particular geographic variable [1]. Since the sizes of the regions are not their true sizes they generally cannot keep both their shape and their adjacencies. A good cartogram, however, preserves the recognizability in some way. Globally speaking, there are three types of cartogram. The standard type (the contiguous area cartogram) has deformed regions so that the desired sizes can be obtained and the adjacencies kept. Algorithms for such cartograms are described in [2, 3, 6, 9]. The second type of cartogram is the non-contiguous area cartogram [7]. The regions have the true shape, but are scaled down and generally do not touch anymore. The third type of cartogram is the rectangular cartogram, introduced by Raisz in 1934 [8], where each region is represented by a rectangle. This has the advantage that the sizes (area) of the regions can be estimated much better than with the first two types. Tobler states in a recent survey, “Thirty-five years of computer cartograms” [10], that none of the existing cartogram algorithms are capable of generating rectangular cartograms. However, even more recently the last two authors of this abstract presented the first algorithms for rectangular cartogram construction [11].

Quantifying the connectivity of material microstructures is important for a wide range of applications from filters to biomaterials. Currently, the most used measure of connectivity is the Euler number, which is a topological invariant. Topology alone, however, is not sufficient for most practical purposes. In this study, we use our recently introduced connectivity measure, called the contour tree connectivity (CTC), to study microstructures for flow analysis. CTC is a new structural connectivity measure that is based on contour trees and algebraic graph theory. To test CTC, we generated a dataset composed of 120 samples and six different types of artificial microstructures. We compared CTC against the Euler parameter (EP), the parameter for connected pairs, the nominal opening dimension ( d nom ) and the permeabilities estimated using direct pore scale modelling. The results show that d nom is highly correlated with permeability ( R 2 = 0.91), but cannot separate the structural differences. The groups are best classified with feature combinations that include CTC. CTC provides new information with a different connectivity interpretation that can be used to analyse and design materials with complex microstructures.

3D building model reconstruction is of great importance for environmental and urban applications. Airborne light detection and ranging (LiDAR) is a very useful data source for acquiring detailed geometric and topological information of building objects. In this study, we employed a graph-based method based on hierarchical structure analysis of building contours derived from LiDAR data to reconstruct urban building models. The proposed approach first uses a graph theory-based localized contour tree method to represent the topological structure of buildings, then separates the buildings into different parts by analyzing their topological relationships, and finally reconstructs the building model by integrating all the individual models established through the bipartite graph matching process. Our approach provides a more complete topological and geometrical description of building contours than existing approaches. We evaluated the proposed method by applying it to the Lujiazui region in Shanghai, China, a complex and large urban scene with various types of buildings. The results revealed that complex buildings could be reconstructed successfully with a mean modeling error of 0.32 m. Our proposed method offers a promising solution for 3D building model reconstruction from airborne LiDAR point clouds.

We show that contour trees can be computed in all dimensions by a simple algorithm that merges two trees. Our algorithm extends, simplifies, and improves work of S. P. Tarasov and M. N. Vyalyi [Construction of contour trees in 3D in O(nlogn) steps. In Proc. 14th Annu. ACM Sympos. on Comput. Geom., 68-75 (1998)] and of M. van Kreveld, R. van Oostrum, C. Bajaj, V. Pascucci and D. Schikore [Contour trees and small seed sets for isosurface traversal. In Proc. 13th Annu, ACM Sympos. Comput. Geom., 212-220 (1997)].