Visualaization. Tree-structure Extraction Algorithm for Accurate and Robust Skeletons.

Mie Sato, Ingmar Bitter, Michael A. Bender, Arie Kaufman, Masayuki NakajimaThe Journal of The Institute of Image Information and Television Engineers 2000 · DOI

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

  1. Bounding Box: The object is isolated to reduce the computational volume.
  2. Distance from Boundary Field (DBF): The Euclidean distance of every internal point to the nearest boundary is calculated.
  3. Endpoint Detection: A distance field from an arbitrary point identifies the furthest extremity.
  4. 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.

  5. 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.

  6. Labeling and Iteration: Found segments are labeled, and the process repeats for branching regions until the entire tree is mapped.
Numerical representation of the Distance from Boundary Field (left) and propagation from a start point (right).
Illustration of the shortest path on the Penalized Distance Field (PDRF) staying centered within a curved structure.

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

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 t he algorithm was demonstrated to be efficient with running times of below five minutes.
BibTeX
@article{sato2000visualaization,
  author = {Mie Sato and Ingmar Bitter and Michael A. Bender and Arie Kaufman and Masayuki Nakajima},
  title = {{Visualaization. Tree-structure Extraction Algorithm for Accurate and Robust Skeletons.}},
  journal = {The Journal of The Institute of Image Information and Television Engineers},
  year = {2000},
  doi = {10.3169/itej.54.1756},
}
Figure