Toward a theory of statistical tree-shape analysis

TY - JOUR

T1 - Toward a theory of statistical tree-shape analysis

AU - Feragen, Aasa

AU - Lo, Pechin Chien Pau

AU - de Bruijne, Marleen

AU - Nielsen, Mads

AU - Lauze, Francois Bernard

PY - 2013

Y1 - 2013

N2 - To develop statistical methods for shapes with a tree-structure, we construct a shape space framework for tree-shapes and study metrics on the shape space. This shape space has singularities which correspond to topological transitions in the represented trees. We study two closely related metrics on the shape space, TED and QED. QED is a quotient euclidean distance arising naturally from the shape space formulation, while TED is the classical tree edit distance. Using Gromov's metric geometry, we gain new insight into the geometries defined by TED and QED. We show that the new metric QED has nice geometric properties that are needed for statistical analysis: Geodesics always exist and are generically locally unique. Following this, we can also show the existence and generic local uniqueness of average trees for QED. TED, while having some algorithmic advantages, does not share these advantages. Along with the theoretical framework we provide experimental proof-of-concept results on synthetic data trees as well as small airway trees from pulmonary CT scans. This way, we illustrate that our framework has promising theoretical and qualitative properties necessary to build a theory of statistical tree-shape analysis.

AB - To develop statistical methods for shapes with a tree-structure, we construct a shape space framework for tree-shapes and study metrics on the shape space. This shape space has singularities which correspond to topological transitions in the represented trees. We study two closely related metrics on the shape space, TED and QED. QED is a quotient euclidean distance arising naturally from the shape space formulation, while TED is the classical tree edit distance. Using Gromov's metric geometry, we gain new insight into the geometries defined by TED and QED. We show that the new metric QED has nice geometric properties that are needed for statistical analysis: Geodesics always exist and are generically locally unique. Following this, we can also show the existence and generic local uniqueness of average trees for QED. TED, while having some algorithmic advantages, does not share these advantages. Along with the theoretical framework we provide experimental proof-of-concept results on synthetic data trees as well as small airway trees from pulmonary CT scans. This way, we illustrate that our framework has promising theoretical and qualitative properties necessary to build a theory of statistical tree-shape analysis.

U2 - 10.1109/TPAMI.2012.265

DO - 10.1109/TPAMI.2012.265

M3 - Journal article

C2 - 23267202

SN - 0162-8828

VL - 35

SP - 2008

EP - 2021

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

IS - 8

ER -