Tree Topology Estimation

Loading...
Thumbnail Image

Date

2013

Authors

Estrada, Rolando Jose

Advisors

Tomasi, Carlo

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

390
views
6557
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

Citation

Citation

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

Collections


Dukes student scholarship is made available to the public using a Creative Commons Attribution / Non-commercial / No derivative (CC-BY-NC-ND) license.