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.

Duke Scholars

Author Carlo Tomasi Computer Science

Author Scott C. Schmidler Statistical Science

Author Sina Farsiu Biomedical Engineering