Search

The topology of isosurfaces changes at isovalues of critical points, making such points an important feature when building contour trees or Morse-Smale complexes. Hexahedral elements with linear interpolants can contain additional off-vertex critical points in element bodies and on element faces. Moreover, a point on the face of a hexahedron which is critical in the element-local context is not necessarily critical in the global context. In ‘`Exploring Scalar Fields Using Critical Isovalues’' Weber et al. introduce a method to determine whether critical points on faces are also critical in the global context, based on the gradient of the asymptotic decider in each element that shares the face. However, as defined, the method of Weber et al. contains an error, and can lead to incorrect results. In this work we correct the error.

As the most important manifestation of the activities of the life service industry, the reasonable layout of spatial agglomeration and dispersion of the accommodation and catering industry plays an important role in guiding the spatial structure of the urban industry and population. Applying the contour tree and location quotient index methods, based on points of interest (POI) data of the accommodation and catering industry in Beijing and on the identification of the spatial structure and cluster center of the accommodation and catering industry, we investigated the distribution and agglomeration characteristics of the urban accommodation and catering industry from the perspective of industrial spatial differentiation. The results show that: (1) the accommodation and catering industry in Beijing presents a polycentric agglomeration pattern in space, mainly distributed within a radius of 20 km from the city center and on a relatively large scale, areas beyond this distance contain isolated single cluster centers. (2) From the perspective of the industry, the cluster centers close to the core area of the city are characterized by the agglomeration of multiple advantageous industries, while those in the outer suburbs of the city are more prominent in a single industry. (3) From the perspective of the location quotient of cluster centers, the leisure catering industries are mainly located close to the urban centers. On the contrary, the cluster centers in the outer suburbs and counties are relatively small and dominated by restaurants and fast food industries. Commercial accommodation businesses are mainly distributed in the transportation hub centers and in entertainment and leisure areas.

Land surface temperature (LST) clusters within cities are typical regions reflecting the spatial heterogeneity of the urban thermal environment. To explore the spatial heterogeneity of the urban thermal environment in the central urban area of Guangzhou, we used the localized contour tree method to identify high- and low-LST clusters. In addition, to understand the characteristics of LST clusters (characteristics of the thermal environment and landscape distribution within the LST cluster), we obtained thermal field value (TFV) data based on the rules of equal-area division and determined the urban functional grid (UFG) based on multi-source data. We found that the characteristics of the high- and low-LST clusters significantly differed. Compared with that of the low-LST clusters, the spatial distribution of the high-LST clusters is denser. The number and total area of low-LST clusters are smaller than that of high-LST clusters, although the average area of low-LST clusters is larger. The spatial heterogeneity of the 10 types of UFGs within the high- and low-LST clusters is significant. The developed and ecological UFGs classified from 10 types of UFGs affect the formation of LST clusters. In addition, there are main UFGs that affect the mean TFV of the LST clusters. This study provides a new approach for the identification of LST clusters and a new perspective for exploring the spatial heterogeneity of urban thermal environments.

Drumlins are ubiquitous landforms in previously glaciated regions, formed through a series of complex subglacial processes operating underneath the paleo-ice sheets. Accurate delineation and characterization of drumlins are essential for understanding the formation mechanism of drumlins as well as the flow behaviors and basal conditions of paleo-ice sheets. Automated mapping of drumlins is particularly important for examining the distribution patterns of drumlins across large spatial scales. This paper presents an automated vector-based approach to mapping drumlins from high-resolution light detection and ranging (LiDAR) data. The rationale is to extract a set of concentric contours by building localized contour trees and establishing topological relationships. This automated method can overcome the shortcomings of previously manual and automated methods for mapping drumlins, for instance, the azimuthal biases during the generation of shaded relief images. A case study was carried out over a portion of the New York Drumlin Field. Overall 1181 drumlins were identified from the LiDAR-derived DEM across the study region, which had been underestimated in previous literature. The delineation results were visually and statistically compared to the manual digitization results. The morphology of drumlins was characterized by quantifying the length, width, elongation ratio, height, area, and volume. Statistical and spatial analyses were conducted to examine the distribution pattern and spatial variability of drumlin size and form. The drumlins and the morphologic characteristics exhibit significant spatial clustering rather than randomly distributed patterns. The form of drumlins varies from ovoid to spindle shapes towards the downstream direction of paleo ice flows, along with the decrease in width, area, and volume. This observation is in line with previous studies, which may be explained by the variations in sediment thickness and/or the velocity increases of ice flows towards ice front.

As data sets grow to exascale, automated data analysis and visualization are increasingly important, to intermediate human understanding and to reduce demands on disk storage via in situ analysis. Trends in architecture of high performance computing systems necessitate analysis algorithms to make effective use of combinations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses relationships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for computing the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analysis. While there is some work on distributed contour tree computation, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. We report the first shared SMP algorithm for fully parallel contour tree computation, with formal guarantees of $O(\mathrm{lg}\; V \;\mathrm{lg} t)$ O ( lg V lg t ) parallel steps and $O(V\; \mathrm{lg}\; V)$ O ( V lg V ) work for data with $V$ V samples and $t$ t contour tree supernodes, and implementations with more than $30\times$ 30 × parallel speed up on both CPU using TBB and GPU using Thrust and up $70\times$ 70 × speed up compared to the serial sweep and merge algorithm.

Urban structure is of vital importance to urban planning, transportation, economics and other applications. Since detecting and analyzing urban centers is crucial for understanding urban structure, a large number of studies on urban center extraction have been performed. In this paper, we propose an analysis framework to identify urban centers by using taxi trajectory data. The proposed approach differs from previous methods by employing a novel way to simulate taxi trajectory data with the topographic surface. We extracted pick-up and drop-off spots from taxi trajectory data and employed the localized contour tree method to delineate the boundaries and hierarchies of urban centers. The experiments show that the proposed method can successfully detect urban centers and analyze their temporal patterns in different periods in Shanghai, China.

Sinkhole mapping is critical for understanding hydrological processes and mitigating geological hazards in karst landscapes. Current methods for identifying sinkholes are primarily based on visual interpretation of low-resolution topographic maps and aerial photographs with subsequent field verification, which is labor-intensive and time-consuming. The increasing availability of high-resolution LiDAR-derived digital elevation data allows for an entirely new level of detailed delineation and analyses of small-scale geomorphologic features and landscape structures at fine scales. In this paper, we present a localized contour tree method for automated extraction of sinkholes in karst landscapes. One significant advantage of our automated approach for sinkhole extraction is that it may reduce inconsistencies and alleviate repeatability concerns associated with visual interpretation methods. In addition, the proposed method has contributed to improving the sinkhole inventory in several ways: (1) detection of non-inventoried sinkholes; (2) identification of previously inventoried sinkholes that have been filled; (3) delineation of sinkhole boundaries; and (4) characterization of sinkhole morphometric properties. We applied the method to Fillmore County in southeastern Minnesota, USA, and identified three times as many sinkholes as the existing database for the same area. The results suggest that previous visual interpretation method might significantly underestimate the number of potential sinkholes in the region. Our method holds great potential for creating and updating sinkhole inventory databases at a regional scale in a timely manner.

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.

International audience; This paper presents a new algorithm for the fast, shared memory multi-threaded computation of contour trees on tetrahedral meshes. In contrast to previous multi-threaded algorithms, our technique computes the augmented contour tree. Such an augmentation is required to enable the full extent of contour tree based applications, including for instance data segmentation. Our approach relies on a range-driven domain partitioning. We show how to exploit such a partitioning to rapidly compute contour forests. We also show how such forests can be efficiently turned into the output contour tree. We report performance numbers that compare our approach to a reference sequential implementation for the computation of augmented contour trees. These experiments demonstrate the run-time efficiency of our approach. We demonstrate the utility of our approach with several data segmentation tasks. We also provide a lightweight VTK-based C++ implementation of our approach for reproduction purposes.

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

© 2016 IEEE. As data sets grow to exascale, automated data analysis and visualisation are increasingly important, to intermediate human understanding and to reduce demands on disk storage via in situ analysis. Trends in architecture of high performance computing systems necessitate analysis algorithms to make effective use of combinations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses relationships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for computing the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analysis. While there is some work on distributed contour tree computation, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. We report the first shared SMP algorithm for fully parallel contour tree computation, withfor-mal guarantees of O(lgnlgt) parallel steps and O(n lgn) work, and implementations with up to 10x parallel speed up in OpenMP and up to 50x speed up in NVIDIA Thrust.

Differential topology, and specifically Morse theory, provide a suitable setting for formalizing and solving several problems related to shape analysis. The fundamental idea behind Morse theory is that of combining the topological exploration of a shape with quantitative measurement of geometrical properties provided by a real function defined on the shape. The added value of approaches based on Morse theory is in the possibility of adopting different functions as shape descriptors according to the properties and invariants that one wishes to analyze. In this sense, Morse theory allows one to construct a general framework for shape characterization, parametrized with respect to the mapping function used, and possibly the space associated with the shape. The mapping function plays the role of a lens through which we look at the properties of the shape, and different functions provide different insights. In the last decade, an increasing number of methods that are rooted in Morse theory and make use of properties of real-valued functions for describing shapes have been proposed in the literature. The methods proposed range from approaches which use the configuration of contours for encoding topographic surfaces to more recent work on size theory and persistent homology. All these have been developed over the years with a specific target domain and it is not trivial to systematize this work and understand the links, similarities, and differences among the different methods. Moreover, different terms have been used to denote the same mathematical constructs, which often overwhelm the understanding of the underlying common framework. The aim of this survey is to provide a clear vision of what has been developed so far, focusing on methods that make use of theoretical frameworks that are developed for classes of real functions rather than for a single function, even if they are applied in a restricted manner. The term geometrical-topological used in the title is meant to underline that both levels of information content are relevant for the applications of shape descriptions: geometrical, or metrical, properties and attributes are crucial for characterizing specific instances of features, while topological properties are necessary to abstract and classify shapes according to invariant aspects of their geometry. The approaches surveyed will be discussed in detail, with respect to theory, computation, and application. Several properties of the shape descriptors will be analyzed and compared. We believe this is a crucial step to exploit fully the potential of such approaches in many applications, as well as to identify important areas of future research.

The process of contourization is presented which converts a raster image into a discrete set of plateaux or contours. These contours can be grouped into a hierarchical structure, defining total spatial inclusion, called a contour tree. A contour coder has been developed which fully describes these contours in a compact and efficient manner and is the basis for an image compression method. Simplification of the contour tree has been undertaken by merging contour tree nodes thus lowering the contour tree's entropy. This can be exploited by the contour coder to increase the image compression ratio. By applying general and simple rules derived from physiological experiments on the human vision system, lossy image compression can be achieved which minimises noticeable artifacts in the simplified image. The contour merging technique offers a complementary lossy compression system to the QDCT (Quantised Discrete Cosine Transform). The artifacts introduced by the two methods are very different; QDCT produces a general blurring and adds extra highlights in the form of overshoots, whereas contour merging sharpens edges, reduces highlights and introduces a degree of false contouring. A format based on the contourization technique which caters for most image types is defined, called the contour tree image format. Image operations directly on this compressed format have been studied which for certain manipulations can offer significant operational speed increases over using a standard raster image format. A couple of examples of operations specific to the contour tree format are presented showing some of the features of the new format., Science and Engineering Research Council

As one of the most fundamental elements of a topographic map, contour lines have a wide application. The relationships of contour lines play a key role in these applications. In this paper, a new approach of using tree structure to represent the relationship between contour lines is proposed. Firstly, contour lines in a contour map are divided into two types according to whether it is closed or not. Then create spatial adjacent contour trees for closed contour lines and open contour lines respectively. Finally, merge the two independent contour trees generating a complete adjacent contour tree, which represents the adjacent relationship of the contour lines. Besides, the inclusion relationship can be deduced from it with elevations. The algorithm is simple to understand and easy for realization of automation programs.

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.

Spatial neighbour relations are a very important concept in spatial information science. Neighbourhood information is indispensable for many operations in spatial information systems, and it is therefore significant to describe and acquire it in an efficient way. In this paper, the concept of k-order neighbours is developed and a Voronoi-based model is formed for this type of neighbours, resulting in the so-called Voronoi k-order neighbours. Several methods for the computation of k-order neighbours for various given conditions are developed. An application in contour analysis is illustrated, i.e. the generation of a contour tree.

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.

Entering the era of big data, human beings are faced with an unprecedented amount of geometric data today. Many computational challenges arise in processing the new deluge of geometric data. A critical one is data uncertainty: the data is inherently noisy and inaccuracy, and often lacks of completeness. The past few decades have witnessed the influence of geometric algorithms in various fields including GIS, spatial databases, and computer vision, etc. Yet most of the existing geometric algorithms are built on the assumption of the data being precise and are incapable of properly handling data in the presence of uncertainty. This thesis explores a few algorithmic challenges in what we call geometric computing over uncertain data.We study the nearest-neighbor searching problem, which returns the nearest neighbor of a query point in a set of points, in a probabilistic framework. This thesis investigates two different nearest-neighbor formulations: expected nearest neighbor (ENN), where we consider the expected distance between each input point and a query point, and probabilistic nearest neighbor (PNN), where we estimate the probability of each input point being the nearest neighbor of a query point.For the ENN problem, we consider a probabilistic framework in which the location of each input point and/or query point is specified as a probability density function and the goal is to return the point that minimizes the expected distance. We present methods for computing an exact ENN or an \\eps-approximate ENN, for a given error parameter 0 < \\eps < 1, under different distance functions. These methods build an index of near-linear size and answer ENN queries in polylogarithmic or sublinear time, depending on the underlying function. As far as we know, these are the first nontrivial methods for answering exact or \\eps-approximate ENN queries with provable performance guarantees. Moreover, we extend our results to answer exact or \\eps-approximate k-ENN queries. Notably, when only the query points are uncertain, we obtain state-of-the-art results for top-k aggregate (group) nearest-neighbor queries in the L1 metric using the weighted SUM operator.For the PNN problem, we consider a probabilistic framework in which the location of each input point is specified as a probability distribution function. We present efficient algorithms for (i) computing all points that are nearest neighbors of a query point with nonzero probability; (ii) estimating, within a specified additive error, the probability of a point being the nearest neighbor of a query point; (iii) using it to return the point that maximizes the probability being the nearest neighbor, or all the points with probabilities greater than some threshold to be the nearest neighbor. We also present some experimental results to demonstrate the effectiveness of our approach.We study the convex-hull problem, which asks for the smallest convex set that contains a given point set, in a probabilistic setting. In our framework, the uncertainty of each input point is described by a probability distribution over a finite number of possible locations including a null location to account for non-existence of the point. Our results include both exact and approximation algorithms for computing the probability of a query point lying inside the convex hull of the input, time-space tradeoffs for the membership queries, a connection between Tukey depth and membership queries, as well as a new notion of \\beta-hull that may be a useful representation of uncertain hulls.We study contour trees of terrains, which encode the topological changes of the level set of the height value \\ell as we raise \\ell from -\\infty to +\\infty on the terrains, in a probabilistic setting. We consider a terrain that is defined by linearly interpolating each triangle of a triangulation. In our framework, the uncertainty lies in the height of each vertex in the triangulation, and we assume that it is described by a probability distribution. We first show that the probability of a vertex being a critical point, and the expected number of nodes (resp. edges) of the contour tree, can be computed exactly efficiently. Then we present efficient sampling-based methods for estimating, with high probability, (i) the probability that two points lie on an edge of the contour tree, within additive error; (ii) the expected distance of two points p, q and the probability that the distance of p, q is at least \\ell on the contour tree, within additive error and/or relative error, where the distance of p, q on a contour tree is defined to be the difference between the maximum height and the minimum height on the unique path from p to q on the contour tree.

Lighting design plays critical roles in depicting structural details in volume rendering. Insufficient and excessive illumination can both affect effectiveness of presenting structural details in visualization. This paper introduces topological importance into the lighting design and proposes the importance-aware lighting. In the proposed approach, the lighting in volume rendering is enhanced based on topological importance. As a result, importance of structures can be depicted from the lighting perspective. The contour tree, one of topological data structures, is used to represent topology in this paper. Topological importance such as persistence derived from the contour tree is used to modulate lighting coefficients. The experimental results demonstrate that the importance-aware lighting not only helps to depict structural details more clearly but also reveal topological importance of structures in rendering. The importance-aware lighting is more meaningful to users but not a random selection without physical meanings based on preferences.

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.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES The three dimensional visualization of data from Computed Tomography scans has aided medical diagnosis. The most used approach is the direct volume rendering, due to the natural representation of such datasets and the simplicity of interpretation of the results. One of the factors that directly impact on the visual results is the transfer function used to map the intensity values to visual properties, such as color and opacity. Therefore, to optimize the visualization process, it would be useful to, automatically or semiautomatically, generate the appropriate transfer functions according to the user’s visualization goals. This work proposes a way to generate such transfer functions by using topological parameters in a contour tree, coupled with an opacity flow model modelled by the Darcy’s law for flow on porous medium. A visualização tridimensional de dados provenientes de Tomografias Computadorizadas tem auxiliado o diagnóstico médico. Uma das técnicas mais utilizadas é a visualização direta, ou direct volume rendering, devido a naturalidade da representação dos datasets e a simplicidade da interpretação dos resultados. Um dos fatores que influenciam diretamente o resultado visual são as funções de transferência utilizadas para mapear os valores do dataset para valores de cor e opacidade. Portanto, para melhorar a visualização, seria útil poder gerar, automaticamente ou semi-automaticamente, funções de transferência adequadas para o tipo de visualização desejada. O presente trabalho propõe uma forma de gerar tais funções de transferência utilizando atributos de topologia na forma de uma árvore de contornos, juntamente com um modelo de fluxo de opacidade, especificamente a Lei de Darcy para fluxo em meios porosos.

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.

A comparative analysis of three important shape analysis techniques viz. real spherical harmonic (RSH) coefficient, shape signatures based on ray-tracing, and multi-resolution attributed contour tree (MACT) is performed to understand their strengths and weaknesses in terms of their shape description power and computational ability. The analysis is performed on anti-HIV ligands extracted from NCI database and the binding pockets of the HIV-1 protease proteins extracted from PDB. The results demonstrate that the RSH technique is more sensitive to capture the detailed shape changes of the ligand molecules and protein binding pockets over the other two techniques.

A contour tree is a topological abstraction of a scalar field. Contour tree simplification (CTS) removes branches corresponding to noise, while making the size of the tree small enough for maintaining essential structure of data. This paper proposes a similarity-driven multi-level partial CTS (PCTS) approach. The PCTS preserves branches corresponding to structures of interest or specific objects specified by users, while removing other branches of the contour tree. A clustering method (e.g. k-means clustering) is used to cluster branch nodes into groups based on their similarities (i.e., similar locations) in the attribute space. As a result, the contour tree is simplified with multi-levels based on different clustering groups. Furthermore, various interfaces and rendering windows are provided and synchronized, which makes the simplification process more meaningful and efficient compared with traditional simplification methods using slide-bar based approaches. The proposed approach can be generalized to process branches with more than three measures.

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.

Contour trees can represent the topology of large volume data sets in a relatively compact, discrete data structure. However, the resulting trees often contain many thousands of nodes; thus, many graph drawing techniques fail to produce satisfactory results. Therefore, several visualization methods were proposed recently for the visualization of contour trees. Unfortunately, none of these techniques is able to handle uncertain contour trees although any uncertainty of the volume data inevitably results in partially uncertain contour trees. In this work, we visualize uncertain contour trees by combining the contour trees of two morphologically filtered versions of a volume data set, which represent the range of uncertainty. These two contour trees are combined and visualized within a single image such that a range of potential contour trees is represented by the resulting visualization. Thus, potentially erroneous topological structures are visually distinguished from more certain structures. Moreover, topological structures can be revealed that are otherwise obscured by data errors. We present and discuss results obtained with a prototypical implementation using well-known volume data sets.

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.

Many of the topological features of the isosurfaces of a scalar volume field can be compactly represented by its contour tree. Unfortunately, the contour trees of most real-world volume data sets are too complex to be visualized by dot-and-line diagrams. Therefore, we propose a new visualization that is suitable for large contour trees and efficiently conveys the topological structure of the most important isosurface components. This visualization is integrated into a histogram of the volume data; thus, it offers strictly more information than a traditional histogram. We present algorithms to automatically compute the graph layout and to calculate appropriate approximations of the contour treeand the surface area of the relevant isosurface components. The benefits of this new visualization are demonstrated with the help of several publicly available volume data sets.

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.

Algorithms for computing contour trees for visualization commonly assume that the input is defined by barycentric interpolation on simplicial meshes or by trilinear interpolation on cubic meshes. In this paper, we describe a general framework for computing contour trees from a graph that captures all significant topological features. We show how to construct these graphs from any mesh-based interpolant by using cell-by-cell “widgets,” and also how to avoid constructing the entire graphs by making finite state machines that capture their traversals.

We consider the problem of representing and extracting morphological information from scalar fields. We focus on the analysis and comparison of algorithms for morphological representation of both 2D and 3D scalar fields. We review algorithms which compute a decomposition of the domain of a scalar field into a Morse and Morse-Smale complex and algorithms which compute a topological representation of the level sets of a scalar field, called a contour tree. Extensions of the morphological representations discussed in the chapter are briefly discussed.

Topology provides a foundation for the development of mathematically sound tools for processing and exploration of scalar fields. Existing topology-based methods can be used to identify interesting features in volumetric data sets, to find seed sets for accelerated isosurface extraction, or to treat individual connected components as distinct entities for isosurfacing or interval volume rendering. We describe a framework for direct volume rendering based on segmenting a volume into regions of equivalent contour topology and applying separate transfer functions to each region. Each region corresponds to a branch of a hierarchical contour tree decomposition, and a separate transfer function can be defined for it. The novel contributions of our work are 1) a volume rendering framework and interface where a unique transfer function can be assigned to each subvolume corresponding to a branch of the contour tree, 2) a runtime method for adjusting data values to reflect contour tree simplifications, 3) an efficient way of mapping a spatial location into the contour tree to determine the applicable transfer function, and 4) an algorithm for hardware-accelerated direct volume rendering that visualizes the contour tree-based segmentation at interactive frame rates using graphics processing units (GPUs) that support loops and conditional branches in fragment programs.

Computing and analyzing the topology of scalar fields has proven to be a powerful tool in a wide variety of applications. In recent years the field has evolved from computing contour trees of two-dimensional functions to Reeb graphs of general two-manifolds, analyzing the topology of time-dependent volumes, and finally to creating Morse-Smale complexes of two and three dimensional functions. However, apart from theoretical advances practical applications depend on the development of robust and easy to implement algorithms. The progression from initial to practical algorithms is evident, for example, in the contour tree computation where the latest algorithms consist of no more than a couple of dozens lines of pseudo-code. In this paper we describe a similarly simple approach to compute progressive Morse-Smale complexes of functions over two-manifolds. We discuss compact and transparent data-structures used to compute and store Morse-Smale complexes and demonstrate how they can be used to implement interactive topology based simplification. In particular, we show how special cases arising, for example, from manifolds with boundaries or highly quantized functions are handled effectively. Overall the new algorithm is easier to implement and more efficient both run-time and storage wise than previous approaches by avoiding to refine a given triangulation.

Locating and segmenting objects such as bones or internal organs is a common problem in medical imaging. Existing segmentation methods are often cumbersome to use for medical staff, since they require a close initial guess and a range of different parameters to be set appropriately. For this work, we present a two-stage segmentation framework which relies on an initial isosurface interactively extracted by topological analysis. The initial isosurface seldom provides a correct segmentation, so we refine the surface using an iterative level set method to better match the desired object boundary. We present applications and improvements to both the flexible isosurface interface and level set segmentation without edges.

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.

A geographic information system (GIS) is a software package for storing geographic data and performing complex operations on the data. Examples are the reporting of all land parcels that will be flooded when a certain river rises above some level, or analyzing the costs, benefits, and risks involved with the development of industrial activities at some place. A substantial part of all activities performed by a GIS involves computing with the geometry of the data, such as location, shape, proximity, and spatial distribution. The amount of data stored in a GIS is usually very large, and it calls for efficient methods to store, manipulate, analyze, and display such amounts of data. This makes the field of GIS an interesting source of problems to work on for computational geometers. In chapters 2-5 of this thesis we give new geometric algorithms to solve four selected GIS problems.These chapters are preceded by an introduction that provides the necessary background, overview, and definitions to appreciate the following chapters. The four problems that we study in chapters 2-5 are the following: Subdivision traversal: we give a new method to traverse planar subdivisions without using mark bits or a stack. Contour trees and seed sets: we give a new algorithm for generating a contour tree for d-dimensional meshes, and use it to determine a seed set of minimum size that can be used for isosurface generation. This is the first algorithm that guarantees a seed set of minimum size. Its running time is quadratic in the input size, which is not fast enough for many practical situations. Therefore, we also give a faster algorithm that gives small (although not minimal) seed sets. Settlement selection: we give a number of new models for the settlement selection problem. When settlements, such as cities, have to be displayed on a map, displaying all of them may clutter the map, depending on the map scale. Choices have to be made which settlements are selected, and which ones are omitted. Compared to existing selection methods, our methods have a number of favorable properties. Facility location: we give the first algorithm for computing the furthest-site Voronoi diagram on a polyhedral terrain, and show that its running time is near-optimal. We use the furthest-site Voronoi diagram to solve the facility location problem: the determination of the point on the terrain that minimizes the maximal distance to a given set of sites on the terrain.

A geographic information system (GIS) is a software package for storing geographic data and performing complex operations on the data. Examples are the reporting of all land parcels that will be flooded when a certain river rises above some level, or analyzing the costs, benefits, and risks involved with the development of industrial activities at some place. A substantial part of all activities performed by a GIS involves computing with the geometry of the data, such as location, shape, proximity, and spatial distribution. The amount of data stored in a GIS is usually very large, and it calls for efficient methods to store, manipulate, analyze, and display such amounts of data. This makes the field of GIS an interesting source of problems to work on for computational geometers. In chapters 2-5 of this thesis we give new geometric algorithms to solve four selected GIS problems.These chapters are preceded by an introduction that provides the necessary background, overview, and definitions to appreciate the following chapters. The four problems that we study in chapters 2-5 are the following: Subdivision traversal: we give a new method to traverse planar subdivisions without using mark bits or a stack. Contour trees and seed sets: we give a new algorithm for generating a contour tree for d-dimensional meshes, and use it to determine a seed set of minimum size that can be used for isosurface generation. This is the first algorithm that guarantees a seed set of minimum size. Its running time is quadratic in the input size, which is not fast enough for many practical situations. Therefore, we also give a faster algorithm that gives small (although not minimal) seed sets. Settlement selection: we give a number of new models for the settlement selection problem. When settlements, such as cities, have to be displayed on a map, displaying all of them may clutter the map, depending on the map scale. Choices have to be made which settlements are selected, and which ones are omitted. Compared to existing selection methods, our methods have a number of favorable properties. Facility location: we give the first algorithm for computing the furthest-site Voronoi diagram on a polyhedral terrain, and show that its running time is near-optimal. We use the furthest-site Voronoi diagram to solve the facility location problem: the determination of the point on the terrain that minimizes the maximal distance to a given set of sites on the terrain.

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)].