Abstract

This paper is concerned with energy-based image segmen- tation problems. We introduce a general class of regional functionals defined as an arbitrary non-linear combination of regional unary terms. Such (high-order) functionals are very useful in vision and medical ap- plications and some special cases appear in prior art. For example, our general class of functionals includes but is not restricted to soft con- straints on segment volume, its appearance histogram, or shape. Our overall segmentation energy combines regional functionals with standard length-based regularizers and/or other submodular terms. In general, regional functionals make the corresponding energy minimiza- tion NP-hard. We propose a new greedy algorithm based on iterative line search. A parametric max-flow technique efficiently explores all so- lutions along the direction (line) of the steepest descent of the energy. We compute the best “step size”, i.e. the globally optimal solution along the line. This algorithm can make large moves escaping weak local minima, as demonstrated on many real images.