Interactive Natural Image Segmentation in Java
(Download the complete source code. Tested with Java ver 1.5.0_17.)
Introduction(A detailed description can be found in .) This project is an implementation of the graph matching framework described in  applied to interactive image segmentation, extending the previous work described in  by replacing the optimization algorithm by a (faster) matching technique based on deformed graphs. Here, the segmentation process can be divided into two steps: initial segmentation computed by graph matching and post-processing, including a connectivity constraint between the segmented regions and the scribbles, and a refinement at pixel level to improve the borders of the extracted objects. The graph matching step is based on the watershed transform and the goal is to match two graphs: an input graph, representing all the watershed regions, and a model graph, representing the regions marked by the scribbles. The algorithm computes a mapping from input vertices to model vertices, minimizing a cost function which takes into account two types of information: appearance and structure. In our particular case, appearance is represented by the region intensities (or colors), while structure is represented by the spatial relations among regions. In order to avoid topological differences caused by matching two graphs with different sizes (different number of vertices), an auxiliary graph called deformed graph is used to efficiently evaluate the structural information. Examples focusing on binary segmentation for object cutout and image composition are illustrated. The algorithm can also be applied to multi-label image segmentation.
Examples from Maximal Similarity Region Merging database:
Examples from Grabcut .
(Click here for more Grabcut examples.)
Image composition using the Berkeley Segmentation Dataset and Benchmark .
(Click here for more Berkeley examples.)
Multi-label Image segmentation example:
Bibliography L. A. Consularo and R. M. Cesar-Jr. and I. Bloch, Structural Image Segmentation with Interactive Model Generation, In Proc. IEEE International Conference on Image Processing, 2007.
Keywords: deformed graphs, watershed, multi-label segmentation, natural interactive image segmentation, background replacement, image composition, matting, graph matching, spatial relations, structural pattern recognition, homomorphism.