Convexity Shape Prior for Segmentation

Lena Gorelick, Olga Veksler, Yuri Boykov, Claudia Nieuwenhuis

In European Conference on Computer Vision (ECCV), Zurich, Switzerland, September, 2014.


Convexity is known as an important cue in human vision. We propose shape convexity as a new high-order regularization constraint for binary image segmentation. In the context of discrete optimization, object convexity is represented as a sum of 3-clique potentials penalizing any 1-0-1 configuration on all straight lines. We show that these non-submodular interactions can be efficiently optimized using a trust region approach. While the cubic number of all 3-cliques is prohibitively high, we designed a dynamic programming technique for evaluating and approximating these cliques in linear time. Our experiments demonstrate general usefulness of the proposed convexity constraint on synthetic and real image segmentation examples. Unlike standard second-order length regularization, our convexity prior is scale invariant, does not have shrinking bias, and is virtually parameter-free.

WHOLE PAPER: pdf file (3.8Mb)