Introduction
Mapping the complex, branching structure of the human airway from Computed Tomography (CT) scans is essential for diagnosing and monitoring chronic lung diseases. However, standard automated tools often struggle with the inherent noise and physical obstructions found in clinical data. The traditional approach, region growing, starts at a seed point and adds neighboring voxels based on intensity. This method is notoriously "short-sighted"; if it encounters a patch of noise, a low-contrast wall, or a mucus plug, the algorithm either stops prematurely or "leaks" into surrounding lung tissue.
This paper introduces a recursive tracking method designed to overcome these local occlusions by using a locally optimal path search. By "looking ahead" beyond immediate neighbors, the algorithm can bridge gaps that typically halt standard extraction tools.
Methodology
The proposed method shifts from a voxel-by-voxel approach to a recursive local search strategy.
Local Path Search
Starting from a known airway point ($x_0$), the algorithm defines a local search space—a sphere with a 20mm radius ($r_s$). It then utilizes Dijkstra’s algorithm to find the optimal paths from the center to every point on the sphere's surface. This allows the system to evaluate potential continuations of the airway even if the immediate vicinity is obscured by noise or pathology.
The Cost Function
To identify the most likely airway paths, the algorithm minimizes a cost function based on three primary factors:
- Voxel Classification: A K-Nearest Neighbor (KNN) classifier trained on 32 low-dose CT images to distinguish airway textures from lung parenchyma.
- Tubeness ($M_{tube}$): A geometric measure derived from Hessian eigenanalysis that identifies bright, cylindrical structures characteristic of airways.
- Orientation: A penalty applied to paths that exhibit sharp, unrealistic turns, ensuring the extracted tree follows natural anatomical trajectories.
Selection and Iteration
Candidate paths reaching the sphere's surface are evaluated for confidence and overlap. Valid paths are integrated into the tree, and their endpoints—along with any detected branching points—serve as new seeds for the next recursive iteration. This naturally handles bifurcations without requiring separate branching logic.
Experimental Results
The method was evaluated on 10 separate CT scans from the Danish Lung Cancer Screening Trial (DLCST) and validated using the EXACT’09 challenge tools.
Quantitative Performance
The proposed method significantly outperformed the baseline region-growing approach across several metrics:
- Tree Length: Achieved a 36% increase in total tree length, averaging 258 cm compared to 192 cm for region growing.
- Completeness: The method captured 96% of the total tree structure found in a union of both methods, whereas region growing captured only 71%.
- Statistical Significance: Improvements in both total length and branch count were statistically significant ($p < 0.01$).
Visual Comparison
As shown in the 3D reconstructions below, the proposed method (right) successfully extracts significantly more distal branches than the region-growing baseline (left). While there was a slight increase in the false positive rate (3.79% vs. 1.35%), this is a common trade-off when attempting to map the smaller, more peripheral branches of the lung.
Conclusion
By employing a locally optimal path search, this method effectively "jumps" over local occlusions like mucus plugs and noise that typically stymie airway extraction. The resulting trees are substantially more complete and longer than those produced by traditional methods. Future work aims to refine the algorithm by implementing multi-radius search schemes to better capture the narrowing diameters of peripheral airways.
Summary updated