User-guided graph reduction for fast image segmentation

Graph-based segmentation methods such as the random walker (RW) are known to be computationally expensive. For high resolution images, user interaction with the algorithm is significantly affected. This paper introduces a novel seeding approach for graph-based segmentation that reduces computation time. Instead of marking foreground and background pixels, the user roughly marks the object boundary forming separate regions. The image pixels are then grouped into a hierarchy of increasingly large layers based on their distance from these markings. Next, foreground and background seeds are automatically generated according to the hierarchical layers of each region. The highest layers of the hierarchy are ignored leading to a significant graph reduction. Finally, validation experiments based on multiple automatically generated input seeds were carried out on a variety of medical images. Results show a significant gain in time for high resolution images using the new approach.