An Efficient Algorithm for Co-Segmentation

The algorithm here was presented in the paper by Hochbaum and Singh:

Dorit S. Hochbaum, Vikas Singh. An efficient algorithm for co-segmentation. ICCV Oct 2009 , Kyoto, Japan, the 12th IEEE Conference on Computer Vision.

The abstract reads:

The Co-segmentation problem [1] is where the objective is to segment a similar object from a pair of images. The background in the two images may be arbitrary; therefore, simultaneous segmentation of both images must be performed with a requirement that the appearance of the two sets of foreground pixels in the respective images are consistent. Existing approaches [1, 2] cast this problem as a Markov Random Field (MRF) based segmentation of the image pair with a regularized difference of the two histograms – assuming a Gaussian prior on the foreground appearance [1] or by calculating the sum of squared differences [2]. Both are interesting formulations but lead to difﬁcult optimization problems, due to the presence of the second (histogram difference) term. The model proposed here bypasses measurement of the histogram differences in a direct fashion; we show that this enables obtaining efﬁcient solutions to the underlying optimization model. Our new algorithm is similar to the existing methods in spirit, but differs substantially in that it can be solved to optimality in polynomial time using a maximum ﬂow procedure on an appropriately constructed graph.

References: [1] C. Rother, T. Minka, A. Blake, and V. Kolmogorov. Cosegmentation of image pairs by histogram matching – incorporating a global constraint into MRFs. In Proc. of Conf. on Computer Vision and Pattern Recognition, 2006.

[2] L. Mukherjee, V. Singh, and C. R. Dyer. Half-integrality based algorithms for cosegmentation of images. In Proc. of
Conf. on Computer Vision and Pattern Recognition, 2009.

License Information

The code is using Hochbaum's PseudoFlow algorithm HPF with a MATLAB interface. The MATLAB interface was written jointly with V. Singh.
The source code is subject to the following academic license. Note this is not an open source license.

Copyright © 2012. The Regents of the University of California (Regents). All Rights Reserved.

Permission to use, copy, modify, and distribute this software and its documentation for educational, research, and not-for-profit purposes, without fee and without a signed licensing agreement, is hereby granted, provided that the above copyright notice, this paragraph and the following two paragraphs appear in all copies, modifications, and distributions. Contact The Office of Technology Licensing, UC Berkeley, 2150 Shattuck Avenue, Suite 510, Berkeley, CA 94720-1620, (510) 643-7201, for commercial licensing opportunities. HPF was created by Bala Chandran and Dorit S. Hochbaum, Department of Industrial Engineering and Operations Research, University of California, Berkeley. For the MATLAB part of the code Copyright is shared between The Regents of the University of California and the University of Wisconsin system.

IN NO EVENT SHALL REGENTS BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF REGENTS HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE AND ACCOMPANYING DOCUMENTATION, IF ANY, PROVIDED HEREUNDER IS PROVIDED "AS IS". REGENTS HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.

Source Code

Code [coseg_maxflow_distrib.tar.gz].
Data file [ pairimages.tar.gz].

Instructions

FUNCTION CALL

./segment -conf seg.conf.imagename imagefilename1 imagefilename2

seg.conf.stone provided with this distribution is setup to run on stone1_128_small.png and stone2_128_small.png, the histogram files (histfile1.raw and histfile2.raw) are created accordingly. Run as

./segment -conf seg.conf.stone ../pairimages/stone1_small_128.png ../pairimages/stone2_small_128.png

FOR INPUT

Before you can run this code on new images you will need the following files:

histsizes.dat (written by the matlab files under histogram_creation_code)

histfile1.raw (histogram of the 1st image, written by the matlab files under histogram_creation_code)

histfile2.raw (histogram of the 2nd image, written by the matlab files under histogram_creation_code)

ses.conf.imagename (this file is the configuration file, contains the path for the histfiles, value of the regularizer lambda, variables called epsilon and numLambdas that are always set to 1, these are internal parameters of the parametric max-flow), the sigma values for smoothness and datacost, the relative influence of the BG (called inflBG) and the number of fg and bg labels and finally these labels (one per line, first specify fg labels in sequence and then bg labels in sequence). These labels are used to set up the data cost for MRF. This configuration file must have seg.conf in the name. See the provided file for an example of what values it should have. To run a simple MRF, (not coseg) set lambda=0, inflBG=1.

FOR OUTPUT

The output is written in the directory output, two file names are created, mask_im1_seg.png and mask_im2_seg.png, which are the segmentation masks of the two images.

To see the mask as a regular binary image in matlab do the following.

im=imread('mask_im1_seg.png');
im=double(2-im./100);
imshow(im)

A sample histogram generation code is provided with this distribution.