  Image segmentation has come a long way since the early days of computer
vision, and still remains a challenging task. Modern variations of the
classical (purely bottom-up) approach, involve, e.g., some form of user
assistance (interactive segmentation) or ask for the simultaneous segmentation
of two or more images (co-segmentation). At an abstract level, all these
variants can be thought of as "constrained" versions of the original
formulation, whereby the segmentation process is guided by some external source
of information. In this paper, we propose a new approach to tackle this kind of
problems in a unified way. Our work is based on some properties of a family of
quadratic optimization problems related to dominant sets, a well-known
graph-theoretic notion of a cluster which generalizes the concept of a maximal
clique to edge-weighted graphs. In particular, we show that by properly
controlling a regularization parameter which determines the structure and the
scale of the underlying problem, we are in a position to extract groups of
dominant-set clusters that are constrained to contain predefined elements. In
particular, we shall focus on interactive segmentation and co-segmentation (in
both the unsupervised and the interactive versions). The proposed algorithm can
deal naturally with several type of constraints and input modality, including
scribbles, sloppy contours, and bounding boxes, and is able to robustly handle
noisy annotations on the part of the user. Experiments on standard benchmark
datasets show the effectiveness of our approach as compared to state-of-the-art
algorithms on a variety of natural images under several input conditions and
constraints.
