Abstract

Many computer vision problems such as object segmentation or re- construction can be formulated in terms of labeling a set of pixels or voxels. In certain scenarios, we may know the number of pixels or voxels which can be as- signed to a particular label. For instance, in the reconstruction problem, we may know size of the object to be reconstructed. Such label count constraints are ex- tremely powerful and have recently been shown to result in good solutions for many vision problems. Traditional energy minimization algorithms used in vision cannot handle label count constraints. This paper proposes a novel algorithm for minimizing energy functions under constraints on the number of variables which can be as- signed to a particular label. Our algorithm is deterministic in nature and outputs ?-approximate solutions for all possible counts of labels. We also develop a vari- ant of the above algorithm which is much faster, produces solutions under almost all label count constraints, and can be applied to all submodular quadratic pseudo- boolean functions. We evaluate the algorithm on the two-label (foreground/back- ground) image segmentation problem and compare its performance with the state-of-the-art parametric maximum flow and max-sum diffusion based algo- rithms. Experimental results show that our method is practical and is able to gen- erate impressive segmentation results in reasonable time.