Tree Topology Estimation.
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.
Rolando
R
Estrada
Carlo
C
Tomasi
Scott C
SC
Schmidler
Sina
S
Farsiu
D000465:Algorithms; D001185:Artificial Intelligence; D016208:Databases, Factual; D006801:Humans; D021621:Imaging, Three-Dimensional / Q000379:methods*; D008030:Lightning; D012171:Retinal Vessels / Q000033:anatomy & histology; D013269:Stochastic Processes; D014197:Trees