Tree Topology Estimation.

Journal Article (Journal Article)

Tree-like structures are fundamental in nature, and it is often useful to reconstruct the topology of a tree - what connects to what - from a two-dimensional image of it. However, the projected branches often cross in the image: the tree projects to a planar graph, and the inverse problem of reconstructing the topology of the tree from that of the graph is ill-posed. We regularize this problem with a generative, parametric tree-growth model. Under this model, reconstruction is possible in linear time if one knows the direction of each edge in the graph - which edge endpoint is closer to the root of the tree - but becomes NP-hard if the directions are not known. For the latter case, we present a heuristic search algorithm to estimate the most likely topology of a rooted, three-dimensional tree from a single two-dimensional image. Experimental results on retinal vessel, plant root, and synthetic tree data sets show that our methodology is both accurate and efficient.

Full Text

Duke Authors

Cited Authors

  • Estrada, R; Tomasi, C; Schmidler, SC; Farsiu, S

Published Date

  • August 2015

Published In

Volume / Issue

  • 37 / 8

Start / End Page

  • 1688 - 1701

PubMed ID

  • 26353004

Pubmed Central ID

  • PMC4566856

Electronic International Standard Serial Number (EISSN)

  • 1939-3539

International Standard Serial Number (ISSN)

  • 0162-8828

Digital Object Identifier (DOI)

  • 10.1109/tpami.2014.2382116


  • eng