The problem of cosegmentation consists of segmenting the
same object (or objects of the same class) in two or more distinct images.
Recently a number of different models have been proposed for this
problem. However, no comparison of such models and corresponding optimization
techniques has been done so far. We analyze three existing
models: the L1 norm model of Rother et al. [1], the L2 norm model of
Mukherjee et al. [2] and the "reward" model of Hochbaum and Singh [3].
We also study a new model, which is a straightforward extension of the
Boykov-Jolly model for single image segmentation [4].
In terms of optimization, we use a Dual Decomposition (DD) technique
in addition to optimization methods in [1, 2]. Experiments show a significant
improvement of DD over published methods. Our main conclusion,
however, is that the new model is the best overall because it: (i) has
fewest parameters; (ii) is most robust in practice, and (iii) can be optimized
well with an efficient EM-style procedure.