Tree Topology Estimation

Loading...

Date

2013

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

395
views
6591
downloads

Abstract

Tree-like structures are fundamental in nature. A wide variety of two-dimensional imaging techniques allow us to image trees. However, an image of a tree typically includes spurious branch crossings and the original relationships of ancestry among edges may be lost. We present a methodology for estimating the most likely topology of a rooted, directed, three-dimensional tree given a single two-dimensional image of it. We regularize this inverse problem via a prior parametric tree-growth model that realistically captures the morphology of a wide variety of trees. We show that the problem of estimating the optimal tree has linear complexity if ancestry is known, but is NP-hard if it is lost. For the latter case, we present both a greedy approximation algorithm and a heuristic search algorithm that effectively explore the space of possible trees. Experimental results on retinal vessel, plant root, and synthetic tree datasets show that our methodology is both accurate and efficient.

Description

Provenance

Subjects

Computer science, Biomedical engineering, Medical imaging and radiology, Graph theory, Image analysis, Stochastic processes, Tree estimation

Citation

Citation

Estrada, Rolando Jose (2013). Tree Topology Estimation. Dissertation, Duke University. Retrieved from https://hdl.handle.net/10161/8074.

Collections


Except where otherwise noted, student scholarship that was shared on DukeSpace after 2009 is made available to the public under a Creative Commons Attribution / Non-commercial / No derivatives (CC-BY-NC-ND) license. All rights in student work shared on DukeSpace before 2009 remain with the author and/or their designee, whose permission may be required for reuse.