Abstract
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 quadratic 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.
Chapter PDF
Similar content being viewed by others
References
Boykov, Y., Kolmogorov, V.: Computing geodesics and minimal surfaces via graph cuts. In: International Conference on Computer Vision, pp. 26–33 (2003)
Pock, T., Cremers, D., Bischof, H., Chambolle, A.: Global solutions of variational models with convex regularization. SIAM Journal on Imaging Sciences 3, 1122–1145 (2010)
Schoenemann, T., Kahl, F., Masnou, S., Cremers, D.: A linear framework for region-based image segmentation and inpainting involving curvature penalization. Int. Journal of Computer Vision (2012)
Bredies, K., Pock, T., Wirth, B.: Convex relaxation of a class of vertex penalizing functionals. J. Math. Imaging and Vision 47(3), 278–302 (2013)
Olsson, C., Ulen, J., Boykov, Y., Kolmogorov, V.: Partial enumeration and curvature regularization. In: International Conference on Computer Vision (ICCV), Sydney, Australia (December 2013)
Nieuwenhuis, C., Töppe, E., Gorelick, L., Veksler, O., Boykov, Y.: Efficient regularization of squared curvature. In: IEEE conference on Computer Vision and Pattern Recognition (CVPR), pp. 4098–4105 (June 2014)
Liu, Z., Jacobs, D., Basri, R.: The role of convexity in perceptual completion: beyond good continuation. Vision Research 39, 4244–4257 (1999)
Mamassian, P., Landy, M.: Observer biases in the 3d interpretation of line drawings. Vision Research 38, 2817–2832 (1998)
Boykov, Y., Jolly, M.P.: Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images. In: IEEE International Conference on Computer Vision, ICCV (2001)
Tang, M., Gorelick, L., Veksler, O., Boykov, Y.: Grabcut in one cut. In: International Conference on Computer Vision (2013)
Gorelick, L., Schmidt, F.R., Boykov, Y.: Fast trust region for segmentation. In: IEEE conference on Computer Vision and Pattern Recognition (CVPR), Portland, Oregon, pp. 1714–1721 (June 2013)
Vicente, S., Kolmogorov, V., Rother, C.: Graph cut based image segmentation with connectivity priors. In: IEEE Conference on Computer Vision and Pattern Recognition, CVPR (2008)
Nowozin, S., Lampert, C.H.: Global interactions in random field models: A potential function ensuring connectedness. SIAM J. Imaging Sciences 3(4), 1048–1074 (2010)
Veksler, O.: Star shape prior for graph-cut image segmentation. In: Forsyth, D., Torr, P., Zisserman, A. (eds.) ECCV 2008, Part III. LNCS, vol. 5304, pp. 454–467. Springer, Heidelberg (2008)
Gulshan, V., Rother, C., Criminisi, A., Blake, A., Zisserman, A.: Geodesic star convexity for interactive image segmentation. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR (June 2010)
Winn, J., Shotton, J.: The layout consistent random field for recognizing and segmenting partially occluded objects. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 37–44 (2006)
Liu, X., Veksler, O., Samarabandu, J.: Order-preserving moves for graph-cut based optimization. Transactions on Pattern Analysis and Machine Intelligence (tPAMI) 32, 1182–1196 (2010)
Felzenszwalb, P., Veksler, O.: Tiered scene labeling with dynamic programming. In: IEEE Conference on Computer Vision and Pattern Recognition, CVPR (2010)
Strekalovskiy, E., Cremers, D.: Generalized ordering constraints for multilabel optimization. In: International Conference on Computer Vision, ICCV (2011)
Fujishige, S.: Submodular functions and optimization. Annals of Discrete Mathematics (1991)
Yuan, Y.: A review of trust region algorithms for optimization. In: The Fourth International Congress on Industrial & Applied Mathematics, ICIAM (1999)
Gorelick, L., Boykov, Y., Veksler, O., Ben Ayed, I., Delong, A.: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1154–1161 (June 2014)
Leordeanu, M., Hebert, M., Sukthankar, R.: An integer projected fixed point method for graph matching and map inference. In: Neural Information Processing Systems (NIPS), pp. 1114–1122 (2009)
Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26(2), 147–159 (2004)
Boros, E., Hammer, P.L.: Pseudo-boolean optimization. Discrete Applied Mathematics 123, 2002 (2001)
Kolmogorov, V., Schoenemann, T.: Generalized sequential tree-reweighted message passing. arXiv:1205.6352 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Gorelick, L., Veksler, O., Boykov, Y., Nieuwenhuis, C. (2014). Convexity Shape Prior for Segmentation. In: Fleet, D., Pajdla, T., Schiele, B., Tuytelaars, T. (eds) Computer Vision – ECCV 2014. ECCV 2014. Lecture Notes in Computer Science, vol 8693. Springer, Cham. https://doi.org/10.1007/978-3-319-10602-1_44
Download citation
DOI: https://doi.org/10.1007/978-3-319-10602-1_44
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-10601-4
Online ISBN: 978-3-319-10602-1
eBook Packages: Computer ScienceComputer Science (R0)