A showcase of ÉTS researchers’ publications and other contributions

A generalized graph reduction framework for interactive segmentation of large images


Downloads per month over past year

Gueziri, Houssem-Eddine, McGuffin, Michael J. and Laporte, Catherine. 2016. « A generalized graph reduction framework for interactive segmentation of large images ». Computer Vision and Image Understanding, vol. 150. pp. 44-57.
Compte des citations dans Scopus : 10.

[thumbnail of A-Generalized-Graph-Reduction-Framework-for-Interactive-Segmentation-of-Large-Images.pdf]
Use licence: Creative Commons CC BY-NC-ND.

Download (11MB) | Preview


The speed of graph-based segmentation approaches, such as random walker (RW) and graph cut (GC), depends strongly on image size. For high-resolution images, the time required to compute a segmentation based on user input renders interaction tedious. We propose a novel method, using an approximate contour sketched by the user, to reduce the graph before passing it on to a segmentation algorithm such as RW or GC. This enables a significantly faster feedback loop. The user first draws a rough contour of the object to segment. Then, the pixels of the image are partitioned into “layers” (corresponding to di�erent scales) based on their distance from the contour. The thickness of these layers increases with distance to the contour according to a Fibonacci sequence. An initial segmentation result is rapidly obtained after automatically generating foreground and background labels according to a specifically selected layer; all vertices beyond this layer are eliminated, restricting the segmentation to regions near the drawn contour. Further foreground / background labels can then be added by the user to refine the segmentation. All iterations of the graphbased segmentation benefit from a reduced input graph, while maintaining full resolution near the object boundary. A user study with 16 participants was carried out for RW segmentation of a multi-modal dataset of 22 medical images, using either a standard mouse or a stylus pen to draw the contour. Results reveal that our approach significantly reduces the overall segmentation time compared with the status quo approach (p < 0:01). The study also shows that our approach works well with both input devices. Compared to super-pixel graph reduction, our approach provides full resolution accuracy at similar speed on a high-resolution benchmark image with both RW and GC segmentation methods. However, graph reduction based on super-pixels does not allow interactive correction of clustering errors. Finally, our approach can be combined with super-pixel clustering methods for further graph reduction, resulting in even faster segmentation.

Item Type: Peer reviewed article published in a journal
McGuffin, Michael John
Laporte, Catherine
Affiliation: Génie logiciel et des technologies de l'information, Génie électrique
Date Deposited: 30 May 2016 16:11
Last Modified: 17 May 2018 04:00

Actions (login required)

View Item View Item