Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Thesis.pdf (14.28 MB)

ETD Abstract Container

Abstract Header

Analyzing data with 1D non-linear shapes using topological methods

Wang, Suyi, Wang
http://rave.ohiolink.edu/etdc/view?acc_num=osu1524020976023345

Abstract Details

2018, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
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 may no 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.
Yusu Wang (Advisor)
Rephael Wenger (Committee Member)
Tamal Dey (Committee Member)
162 p.
Computer Engineering; Computer Science; Geographic Information Science; Neurosciences
Shape Analysis; Computational Topology; Map Reconstruction; Neuron Tracing; JS-Graph; Contour Tree; Reeb Graph; Persistent Homology; 1-Stable Manifold; DiMorSC

Recommended Citations

Citations

  • Wang, Wang, S. (2018). Analyzing data with 1D non-linear shapes using topological methods [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1524020976023345

    APA Style (7th edition)

  • Wang, Wang, Suyi. Analyzing data with 1D non-linear shapes using topological methods. 2018. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1524020976023345.

    MLA Style (8th edition)

  • Wang, Wang, Suyi. "Analyzing data with 1D non-linear shapes using topological methods." Doctoral dissertation, Ohio State University, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=osu1524020976023345

    Chicago Manual of Style (17th edition)

osu1524020976023345
443
© 2018, some rights reserved.Creative Commons License Analyzing data with 1D non-linear shapes using topological methods by Suyi Wang Wang is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. Based on a work at etd.ohiolink.edu.
This open access ETD is published by The Ohio State University and OhioLINK.