We introduce the term cosegmentation which denotes the task of segmenting simultaneously the common parts of an image pair. A generative model for cosegmentation is presented. Inference in the model leads to minimizing an energy with an MRF term encoding spatial coherency and a global constraint which attempts to match the appearance histograms of the common parts. This energy has not been proposed previously and its optimization is challenging and NP-hard. For this problem a novel optimization scheme which we call trust region graph cuts is presented. We demonstrate that this framework has the potential to improve a wide range of research: Object driven image retrieval, video tracking and segmentation, and interactive image editing. The power of the framework lies in its generality, the common part can be a rigid/non-rigid object (or scene), observed from different viewpoints or even similar objects of the same class.

Consider the triplet of images in the top row. The left and middle image depict the same object, a bus, where the right image shows an unrelated scene. The distance (SAD) of the global texton histograms of the whole images says that the middle image is more similar to the right (47%) than to the left image (53%). This is the wrong answer. Running cosegmentation gives the correct answer (bottom row), the images of the two busses are now more similar than the middle and right image. Consider the left and middle image, the bus was segmented as the foreground object and the remaining image parts labelled as background (light blue). The energy which measures the similarity of the foreground parts only (Background is ignored), serves as the image distance.    

1. C. Rother, V. Kolmogorov, T. Minka, A. Blake, Cosegmentation of Image Pairs by Histogram Matching - Incorporating a Global Constraint into MRFs. CVPR 2006, New York, USA, June 2006, PDF VERSION; Detailed Technical Report