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 [3].) This project is an implementation of the graph matching framework described in [2] applied to interactive image segmentation, extending the previous work described in [1] 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.

Software

News:
2011-nov-18: new examples for multilabel segmentation of similar images.
2010-oct-14: new examples for binary and multilabel segmentation.
2009-sep-14: inclusion of examples for segmentation and the GPL license file.
2009-aug-31: fixed important bugs, accelerating the pre-processing step.
2009-jun-15: reduced user effort, exploring connectivity constraint for region merging; more accurate segmentations, exploring appearance information at pixel level for binary segmentation and object cutout.
2009-jun-05: a new faster and more accurate version available for image segmentation, using deformed graphs.
.


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

[1] 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.

[2] A. NOMA and A. PARDO and R. M. CESAR JR. Structural matching of 2D electrophoresis gels using deformed graphs. In Pattern Recognition Letters, Vol. 32, Issue 1, p.3-11, 2011.

[3] A. Noma and A. B. V. Graciano and R. M. Cesar-Jr. and L. A. and Consularo and I. Bloch, Interactive Image Segmentation by Matching Attributed Relational Graphs, In Pattern Recognition, Vol. 45, Issue 3, p.1159-1179, 2012.

Keywords: deformed graphs, watershed, multi-label segmentation, natural interactive image segmentation, background replacement, image composition, matting, graph matching, spatial relations, structural pattern recognition, homomorphism.