Detection and Segmentation of Pathological Structures by the Extended Graph-Shifts Algorithm

Jason J. Corso, Alan L. Yuille, Nancy L. Sicotte, Arthur W. TogaMICCAI 2007 · DOI

Introduction

Medical image segmentation often requires distinguishing healthy tissue from pathological structures. Two primary hurdles hinder existing methods: the unpredictable number of pathological instances (e.g., multiple sclerosis lesions) and the tendency of energy minimization techniques to settle in local minima. This paper, presented at MICCAI 2007, introduces the Extended Graph-Shifts (EGS) algorithm to address these challenges through a hierarchical framework capable of dynamic topology updates.

Methodology: The Extended Graph-Shifts Algorithm

The EGS algorithm operates on a hierarchical graph where the base layer consists of individual voxels and higher layers represent increasingly coarse groupings. Unlike traditional methods that modify labels at the voxel level, EGS performs "shifts" on entire branches of the hierarchy, allowing for rapid convergence and avoidance of local minima.

The "Spawn" Shift

The defining innovation of EGS is the "spawn" move. By incorporating a specialized "spawning node" connected to all other nodes, the algorithm can dynamically instantiate new model labels. This allows for the detection of an arbitrary number of detached structures without prior knowledge of the instance count.

The Extended Graph-Shifts mechanism: a "spawn" shift allows the hierarchy to dynamically create new model instances.

Energy Formulation

The algorithm minimizes a hybrid energy function consisting of unary and pairwise terms. Unary terms represent local evidence for a label, computed using a Probabilistic Boosting-Tree (PBT) trained on approximately 3,000 features, including intensity gradients and Haar-like filters. Pairwise terms act as a smoothness constraint, penalizing boundary length to ensure realistic segmentations.

Experimental Results

The EGS algorithm was validated on clinical datasets for brain tumors (Glioblastoma Multiforme) and Multiple Sclerosis (MS).

Qualitative segmentation results demonstrating the algorithm's ability to identify multiple distinct regions.

Performance and Accuracy

For brain tumor segmentation, the algorithm achieved Jaccard scores between 86% and 88%, with precision and recall for tumor mass and edema reaching up to 98%. In MS lesion detection, the "spawn" move proved critical, enabling the identification of small, detached lesions that previous fixed-label versions of the algorithm missed, resulting in an 81% recall rate.

Efficiency

A significant advantage of the EGS framework is its speed. By calculating energy decreases recursively through the hierarchy, the algorithm can process a full 3D MRI volume (e.g., 256 x 256 x 50 voxels) in approximately one minute.

Discussion and Conclusion

The Extended Graph-Shifts algorithm represents a significant advancement in hierarchical segmentation. By allowing for dynamic graph reconfiguration through the "spawn" shift, it effectively handles the variable topology of pathological structures. While the reliance on hand-crafted features and small clinical datasets are noted limitations, the algorithm's speed and accuracy established a high benchmark for automated medical image analysis at the time of its publication. Future work could involve scaling the validation to larger cohorts and integrating learned feature representations.

Summary updated

BibTeX
@inproceedings{corso2007detection,
  author = {Jason J. Corso and Alan L. Yuille and Nancy L. Sicotte and Arthur W. Toga},
  title = {{Detection and Segmentation of Pathological Structures by the Extended Graph-Shifts Algorithm}},
  booktitle = {International Conference on Medical Image Computing and Computer-Assisted Intervention},
  year = {2007},
  doi = {10.1007/978-3-540-75757-3\_119},
}
Figure