Search

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.

Shape analysis has been applied in many applications across a broad range of domains.Among various different families of ``complex'' shapes, the ones with 1D non-linear topological structures (skeletons) are particularly interesting. These shapes are simple, as they can be decomposed into 1-d pieces, but still informative in representing the connectivity and other important information behind data.In this thesis, I focus on two objects from computational topology that have been useful for modeling the skeleton of data: the Reeb graph (and its variants) and the 1-(un)stable manifold from discrete Morse theory,and study their properties as well as applications to shape analysis.The two specific topological objects that I focus on have both already been widely used in practical applications.Further theoretical understanding and applications of these two objects in modeling and studying the skeleton of data will be provided.The first part of the dissertation work concerns the so-called Reeb graph and its loop-free variant, the contour tree, which can be used to provide a 1D tree summary of an input scalar field. It has been commonly used in computer graphics and visualization.I have investigated one problem regarding to the theoretical understanding of the contour tree, as well as developing a variant of the Reeb graph to address the issue of noise. Carr et. al. has proposed an algorithm for computing the contour tree for a piece-wise linear function defined on a simplicial complex domain.This algorithm is simple, efficient and has been widely used in practice.However, the algorithm is often applied even when the output contour tree may not exist,in which case the algorithm may not terminate or exit with only partial output.My work provides new understanding of this contour tree algorithm and characterizes the cause for such behavior. I also propose a simple variation of the contour tree (called JS-graph) to handle this situation in practice.The Reeb graph, which provides a general 1D summary of a scalar field, has been used to extract the skeleton behind data. However, when there is significant amount of ambient noise, the Reeb graph mayno longer reflect the structures of the data.To handle such ambient noise, I propose and develop a concept called ``gradational Reeb graph'', which incrementally merges the Reeb graphs from different density levels while keeping structures from high density regions. I demonstrate that when extracting the road network from GPS samples, the ``gradational Reeb graph'' could capture finer structures, which traditional Reeb graph cannot.In the second part of my thesis, I will focus on the so-called 1-(un)stable manifold from Morse Theory, which is another topological object for modeling and extracting data skeleton. In this thesis, I develop a pipeline for the automatic map reconstruction problem that aims to reconstruct the underlying road network, which can be considered as a hidden geometric graph from GPS trajectory samples.I also develop a Morse theory based approach that can integrate multiple maps (graphs)into a single one, as well as correct an existing map with a partial but more trustworthy map.The effectiveness of the method is demonstrated by reconstructing maps from GPS trajectories sampled in the cites of Athens, Beijing, Berlin and Chicago.This work proposes a new methodology with simpler pipeline for handling large maps with better performance, which also advances the state of art.The closing topic of this thesis is the extension of 1-stable manifold to a 3D application, neuron tracing,which asks to extract trees representing neurons from digital images.Here I aim to tackle the challenges such as the massive size and noisy nature of data.In this work I have developed a new algorithm that handles new large data of 3D meso-scale brain by divide and conquer topological method.Experiments have demonstrated that the proposed method has obtained quantitatively better results than those from existing algorithms in tracing single neurons,while my methods can also produce a summary of trends for more challenging and general injection data containing multiple neurons.

Scalar functions are virtually ubiquitous in scientific research. A vast amount of research has been conducted in visualization and exploration of low-dimensional data during the last few decades, but adapting these techniques to high-dimensional, topologically-complex data remains challenging. Traditional metric-preserving dimensionality reduction techniques suffer when the intrinsic dimension of data is high, as the metric cannot generally survive projection into low dimensions. The metric distortion can be arbitrarily large, and preservation of topological structure is not guaranteed, resulting in a misleading view of the data.When preservation of geometry is not possible, topological analysis provides a promising alternative. As an example, simplicial homology characterizes the structure of a topological space (i.e. a simplicial complex) via its intrinsic topological features of various dimensions. Unfortunately, this information can be abstract and difficult to comprehend. The ranks of these homology groups (the Betti numbers) offer a simpler, albeit coarse, interpretation as the number of voids of each dimension. In high dimensions, these approaches suffer from exponential time complexity, which can render them impractical for use with real data.In light of these difficulties, we turn to an alternative type of topological characterization. We investigate the Reeb graph as a visualization and analysis tool for such complex data. The Reeb graph captures the topology of the set of level sets of a scalar function, providing a simple, intuitive, and informative topological representation. We present the first sub-quadratic expected time algorithm for computing the Reeb graph of an arbitrary simplicial complex, opening up the possibility of using the Reeb graph as a tool for understanding high-dimensional data.While the Reeb graph effectively captures some topological structure, it is still somewhat terse. The Morse-Smale complex summarizes a scalar function by by partitioning the domain according to gradient flow source and destination. While this information is rich and useful, it can be impractical to compute in high dimensions. The Morse crystal decomposition approximates the Morse-Smale complex, accepting a significant gain in computational efficiency for potential under-segmentation of the domain. We demonstrate how the novel Reeb graph algorithm enhances the Morse crystal decomposition by potentially reducing the degree of under-segmentation that occurs.A Reeb graph without loops is known as a contour tree. Contour trees can arise, for example, when the domain is simply connected. In their raw forms, Reeb graphs and contour trees can be difficult to interpret, as their graph-like structures can be complex and hard to visualize. We propose a method for visualizing a high-dimensional scalar function by constructing an ensemble of two-dimensional terrain models which share its contour tree. These "topological landscapes" perfectly preserve certain metric information, providing intuition about the topology and geometry of the scalar function.From these foundations, we develop a collaborative visual analytics suite for protein folding and computational chemistry researchers. This software focuses on the topological landscape, allowing users to interactively visualize and explore massive high-dimensional molecular dynamics datasets. Users collaborate in annotating interesting biochemical events and assemble them into cohesive narratives using a simple storyboard interface.

Hurricanes and tropical storms represent severe threats to coastal properties, settlements, and infrastructure. Until recently, the assessment of hurricane-induced damages has been based on ground surveys and aerial photography. Recent advent of airborne LiDAR technology offers an extraordinary capability of gathering highly accurate and densely sampled coastal topography data. Airborne LiDAR surveys conducted before and after storm events allow for an entirely new level of analysis of coastal geomorphologic and sediment volumetric changes induced by hurricane hazards. This research presents an object-oriented method and associated algorithms and software tool for representing and quantifying hurricane-induced damages to buildings, beaches and sand dunes, coastal vegetation canopy, and infrastructure. Multi-level slicing, contour tree construction, and critical isocontour identification are the key components of the new algorithm for change object detection and extraction. An ontology and taxonomy is proposed to classify change objects into different types of coastal damages in terms of their semantic properties. This method has been successfully applied to assess the damages of Hurricane Ike to the Bolivar Peninsula based on pre- and post-storm airborne LiDAR data and color infrared (CIR) aerial photographs.