Tree Topology Estimation

dc.contributor.advisor

Tomasi, Carlo

dc.contributor.author

Estrada, Rolando Jose

dc.date.accessioned

2013-11-14T19:15:10Z

dc.date.available

2013-11-14T19:15:10Z

dc.date.issued

2013

dc.department

Computer Science

dc.description.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.

dc.identifier.uri

https://hdl.handle.net/10161/8074

dc.subject

Computer science

dc.subject

Biomedical engineering

dc.subject

Medical imaging and radiology

dc.subject

Graph theory

dc.subject

Image analysis

dc.subject

Stochastic processes

dc.subject

Tree estimation

dc.title

Tree Topology Estimation

dc.type

Dissertation

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Estrada_duke_0066D_12101.pdf
Size:
36.49 MB
Format:
Adobe Portable Document Format

Collections