Extraction of airway trees using multiple hypothesis tracking and template matching

Raghavendra Selvan, Jens Petersen, Jesper Johannes Holst Pedersen, Marleen de BruijnearXiv 2016 · arXiv

Introduction

Accurately mapping the airway tree is a critical component in diagnosing and monitoring Chronic Obstructive Pulmonary Disease (COPD). However, segmenting these structures in Computed Tomography (CT) images presents significant technical challenges. Airways are complex, tree-like structures that vary drastically in scale, ranging from the 10mm trachea down to peripheral bronchioles as small as 1mm.

Traditional segmentation methods, such as region growing, often fail due to a fundamental trade-off: high sensitivity leads to "leaks" into surrounding lung tissue, while strict parameters cause the algorithm to miss smaller branches. This paper proposes an automated method that combines tubular template matching with Multiple Hypothesis Tracking (MHT) to create a robust, scale-independent segmentation tool.

Methodology

The proposed approach adapts a semi-automatic vessel-tracking technique for the specific challenges of airway segmentation through several key innovations.

Voxel Classification

Airways appear as dark, air-filled regions in CT scans, whereas blood vessels appear bright. To leverage existing vessel-tracking frameworks, the authors first employ a $k$-nearest neighbor (KNN) classifier. This transforms the raw CT data into "probability images" where airway-like voxels have high values, effectively converting the task into tracking bright tubular structures.

Template Matching

To estimate the radius and orientation of an airway at any given point, the algorithm fits idealized 3D tubular templates to the probability data. This fitting is performed using a weighted least-squares approach via the Levenberg-Marquardt algorithm. The template profile represents the expected cross-sectional intensity of an airway.

The idealized profile used for tubular template matching.

Multiple Hypothesis Tracking (MHT)

A major limitation of standard tracking algorithms is their "greedy" nature—they pick the best immediate next step. In contrast, MHT utilizes a deferred decision-making process. It constructs a tree of potential paths (hypotheses) up to a specific search depth. By exploring several steps ahead before committing to a path, the system can "average out" local noise or image artifacts that might otherwise derail the tracker.

Comparison between instantaneous (a) and deferred (b) decision-making in airway tracking.

Statistical Ranking and Bifurcation Handling

To handle the vast range of airway sizes, the authors introduced a statistical ranking system. Hypotheses are scored locally from 0 to 1 based on their significance at that specific step. This normalization makes the global threshold scale-independent, allowing the same parameters to track both large and small airways. Additionally, when a branch splits (bifurcation), the new branches inherit the history and state of the parent MHT tree, ensuring statistical continuity and stability at complex junctions.

Evaluation and Results

The method was evaluated using 32 CT scans from the Danish Lung Cancer Screening Trials (DLCST), split evenly into training and test sets. Reference segmentations were provided by expert manual annotations.

The "Modified MHT" (mod-MHT) significantly outperformed the original vessel-tracking method. While the original method exhibited a median error of approximately 4mm, the mod-MHT reduced this to roughly 2mm. Although simple region growing on probability images showed slightly lower median errors in some cases, the authors emphasize that the MHT approach is theoretically more robust against local data anomalies and the "leaking" common in region-growing techniques.

Conclusion

By replacing instantaneous decisions with a deferred MHT framework and introducing scale-independent statistical ranking, this research provides a more robust and fully automatic solution for airway tree extraction. Future work will focus on dynamically adapting the number of hypotheses based on local complexity and incorporating formal state-space models to further refine tracking accuracy.

Summary updated

Abstract

Knowledge of airway tree morphology has important clinical applications in diagnosis of chronic obstructive pulmonary disease. We present an automatic tree extraction method based on multiple hypothesis tracking and template matching for this purpose and evaluate its performance on chest CT images. The method is adapted from a semi-automatic method devised for vessel segmentation. Idealized tubular templates are constructed that match airway probability obtained from a trained classifier and ranked based on their relative significance. Several such regularly spaced templates form the local hypotheses used in constructing a multiple hypothesis tree, which is then traversed to reach decisions. The proposed modifications remove the need for local thresholding of hypotheses as decisions are made entirely based on statistical comparisons involving the hypothesis tree. The results show improvements in performance when compared to the original method and region growing on intensity images. We also compare the method with region growing on the probability images, where the presented method does not show substantial improvement, but we expect it to be less sensitive to local anomalies in the data.
BibTeX
@misc{selvan2016extraction,
  author = {Raghavendra Selvan and Jens Petersen and Jesper Johannes Holst Pedersen and Marleen de Bruijne},
  title = {{Extraction of airway trees using multiple hypothesis tracking and template matching}},
  year = {2016},
  eprint = {1611.08131},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1611.08131},
}
Figure