Globally optimal model-based matching of anatomical trees

Michael W. Graham, William Evan Higgins

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations


Modern MDCT and micro-CT scanners are able to produce high-resolution three-dimensional (3D) images of anatomical trees, such as the airway tree and the heart and liver vasculature. An important problem arising in many contexts is the matching of trees depicted in two different images. Three basic steps are used in order to match two trees: (1) image segmentation, to extract the raw trees from a given pair of 3D images; (2) axialanalysis, to define the underlying centerline structure of the trees; and (3) tree matching, to match the centerline structures of the trees. We focus on step (3). This task is complicated by several problems associated with current segmentation and axial-analysis methods, including missing branches, false branches, and other topological errors in the extracted trees. We propose a model-based approach in which the extracted trees are assumed to arise from an initially unknown common structure corrupted by a sequence of modelled topological deformations. We employ a novel mathematical framework to directly incorporate this model into the matching problem. Under this framework, it is possible to define the set of matches that are consistent with a given deformation model. The optimal match is the member of this set that maximizes a user-definable similarity measure. We present several such similarity measures based upon geometrical attributes (e.g., branch lengths, branching angles, and relative branchpoint locations as measured from the 3D image data). We locate the globally optimal match via an efficient dynamic programming algorithm. Our primary analytical result is a set of sufficient conditions on the user-definable similarity measure such that our dynamic programming algorithm is guaranteed to locate an optimal match. Experimental results have been generated for 3D human CT chest scans and micro-CT coronary arterial-tree images of mice. The resulting matches are in good agreement with correspondences defined by human experts.

Original languageEnglish (US)
Title of host publicationMedical Imaging 2006
Subtitle of host publicationImage Processing
StatePublished - 2006
EventMedical Imaging 2006: Image Processing - San Diego, CA, United States
Duration: Feb 13 2006Feb 16 2006

Publication series

NameProgress in Biomedical Optics and Imaging - Proceedings of SPIE
Volume6144 I
ISSN (Print)1605-7422


OtherMedical Imaging 2006: Image Processing
Country/TerritoryUnited States
CitySan Diego, CA

All Science Journal Classification (ASJC) codes

  • Electronic, Optical and Magnetic Materials
  • Atomic and Molecular Physics, and Optics
  • Radiology Nuclear Medicine and imaging
  • Biomaterials


Dive into the research topics of 'Globally optimal model-based matching of anatomical trees'. Together they form a unique fingerprint.

Cite this