Abstract
An algorithm is described for extracting tree-structure skeletons that are accurate and robust. Volumetric skeletons are needed to accurately measure the length along branching and winding structures. Skeletons are also needed for automatic virtual navigation, such as traveling through human organs to control the movement and orientation of a virtual camera. The proposed algorithm finds the skeleton accurately and rapidly. The solution is automatically obtained, freeing the user from having to engage in preprocessing the data. Accurate skeletons were computed on a number of test datasets, and the algorithm was demonstrated to be efficient with running times of below five minutes.
Introduction
In medical imaging and engineering, simplifying complex 3D shapes—such as the aorta, colon, or branching pipes—into 1D "skeletons" is essential. These skeletons facilitate precise length measurements and enable "virtual navigation," where a virtual camera automatically traverses human organs.
The primary challenge in skeletonization is maintaining "centrality." Traditional shortest-path algorithms, like Dijkstra’s, often "cut corners" in sharply curved structures, hugging the inner wall. Conversely, "onion peeling" methods are computationally intensive and prone to connectivity issues. This paper presents a robust algorithm that ensures centrality through a novel penalized distance field approach.
Methodology: The Penalized Distance Field
The core of the proposed method is the Penalized Distance Field (PDRF). Instead of treating all internal points equally, the algorithm assigns a "cost" to moving through the 3D volume based on its proximity to the boundary.
Step-by-Step Process
- Bounding Box: The object is isolated to reduce the computational volume.
- Distance from Boundary Field (DBF): The Euclidean distance of every internal point to the nearest boundary is calculated.
- Endpoint Detection: A distance field from an arbitrary point identifies the furthest extremity.
-
Penalty Function: A penalty $p(v)$ is applied to each voxel $v$: $p(v) = \alpha \cdot [1 - DBF(v)/M]^\beta$ where $M$ is the maximum distance to the boundary, and $\alpha, \beta$ are tuning constants. This exponentially increases the cost of voxels near the boundary.
-
Penalized Shortest Path: Dijkstra’s algorithm finds the "shortest" path based on these costs. The high cost of boundary-adjacent voxels forces the path to remain centered.
- Labeling and Iteration: Found segments are labeled, and the process repeats for branching regions until the entire tree is mapped.
Results and Discussion
The algorithm was tested on diverse 3D datasets, including the human aorta, colon, ribs, and a lobster specimen.
Performance and Accuracy
The method proved remarkably efficient. The complex human colon dataset was processed in just 208 seconds on a 194MHz CPU, significantly faster than previous state-of-the-art methods. Qualitative analysis confirms that the skeletons remain perfectly centered even within the sharpest turns and complex folds of the colon.
Key Insights
- Economic Centrality: By framing centrality as a cost-optimization problem rather than a purely geometric one, the algorithm leverages standard shortest-path logic to achieve superior results.
- Robustness: The reliance on a global distance field makes the method resistant to surface noise that typically plagues local thinning algorithms.
Conclusion
The proposed algorithm provides a fast, automated, and accurate solution for tree-structure extraction. While it currently requires pre-segmented binary data and may produce slightly jagged voxel-level lines, its robustness and speed make it highly suitable for clinical workflows. Future work will focus on integrating smoothing filters to enhance the skeletons for fluid camera animations.
Summary updated