Graph-based segmentation

The proposed approach is a segmentation method based on the graph-theory. After selecting one source point inside the Region of Interest (ROI), a segmentation process starts. It consists of two automatic stages: a cost-labeling phase and a graph-cutting phase. The algorithm finds optimal paths based on a new cost function by creating Minimum Path Spanning Tree (MPST). To extract the region, a cut of the obtained tree is necessary. A new criterion of the MPST-cut based on the compactness shape factor was developed for a medical application (carpal bone segmentation).

An extension to the multi-source case has been developed. The algorithm begins with a random insertion of source points and proceeds finding the optimal paths, MPST, based on the aforementioned cost function. The approach is recursively applied until a label map is generated. The source points location is driven by an optimal criterion, which takes into account the intermediate segmentation results.


The method is unsupervised, fast, it does not employ any a priori model or knowledge, and it is adaptive to the individual variability of the acquired data. It is robust and independent on parameters and order of analysis. In addition, it can be applied to 2D and 3D applications.