Abstract
High-order and non-submodular pairwise energies are important for image segmentation, surface matching, deconvolution, tracking and other computer vision problems. Minimization of such energies is generally NP-hard. One standard approximation approach is to optimize an auxiliary function - an upper bound of the original energy across the entire solution space. This bound must be amenable to fast global solvers. Ideally, it should also closely approximate the original functional, but it is very difficult to find such upper bounds in practice.
Our main idea is to relax the upper-bound condition for an auxiliary function and to replace it with a family of pseudo-bounds, which can better approximate the original energy. We use fast polynomial parametric maxflow approach to explore all global minima for our family of submodular pseudo-bounds. The best solution is guaranteed to decrease the original energy because the family includes at least one auxiliary function. Our Pseudo-Bound Cuts algorithm improves the state-of-the-art in many applications: appearance entropy minimization, target distribution matching, curvature regularization, image deconvolution and interactive segmentation.
Chapter PDF
Similar content being viewed by others
Keywords
References
An, L.T.H., Tao, P.D., Canh, N.N., Thoai, N.V.: Dc programming techniques for solving a class of nonlinear bilevel programs. J. Global Optimization 44(3), 313–337 (2009)
Ben Ayed, I., Chen, H.M., Punithakumar, K., Ross, I., Li, S.: Graph cut segmentation with a global constraint: Recovering region distribution via a bound of the bhattacharyya measure. In: CVPR, pp. 3288–3295 (2010)
Ben Ayed, I., Gorelick, L., Boykov, Y.: Auxiliary cuts for general classes of higher order functionals. In: IEEE Conference on Computer Vision and Pattern Recognition (2013)
Boros, E., Hammer, P.L.: Pseudo-boolean optimization. Discrete Applied Mathematics 123, 2002 (2001)
Boykov, Y., Jolly, M.-P.: Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images. In: ICCV, vol. I, pp. 105–112 (July 2001)
Delong, A., Osokin, A., Isack, H., Boykov, Y.: Fast approximate energy minimization with label costs. International Journal of Computer Vision 96, 1–27 (2012)
Eisner, M.J., Severance, D.G.: Mathematical techniques for efficient record segmentation in large shared databases. J. ACM 23(4), 619–635 (1976)
El-Zehiry, N., Grady, L.: Fast global optimization of curvature. In: Proc. of CVPR 2010. IEEE Computer Society. IEEE (June 2010)
Fashing, M., Tomasi, C.: Mean shift is a bound optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence 27, 471–474 (2005)
Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18(1), 30–55 (1989)
Gorelick, L., Boykov, Y., Veksler, O., Ayed, I.B., Delong, A.: Submodularization for binary pairwise energies. In: IEEE conference on Computer Vision and Pattern Recognition (CVPR), Columbus, Ohio (June 2014)
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)
Gould, S.: Max-margin learning for lower linear envelope potentials in binary markov random fields. In: ICML (2011)
Hochbaum, D.S.: Polynomial time algorithms for ratio regions and a variant of normalized cut. IEEE Trans. Pattern Anal. Mach. Intell. 32(5), 889–898 (2010)
Jiang, H.: Linear solution to scale invariant global figure ground separation. In: CVPR. pp. 678–685 (2012)
Kappes, J.H., Andres, B., Hamprecht, F.A., Schnorr, C., Nowozin, S., Batra, D., Kim, S., Kausler, B.X., Lellmann, J., Komodakis, N., Rother, C.: A comparative study of modern inference techniques for discrete energy minimization problem. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 1328–1335 (2013)
Kim, J., Kolmogorov, V., Zabih, R.: Visual correspondence using energy minimization and mutual information. In: Int. Conf. on Comp. Vision (ICCV), vol. 2, pp. 1033–1040 (October 2003)
Kohli, P., Ladický, L., Torr, P.H.: Robust higher order potentials for enforcing label consistency. Int. J. Comput. Vision 82(3), 302–324 (2009)
Kolmogorov, V., Schoenemann, T.: Generalized sequential tree-reweighted message pass. In: arXiv:1205.6352 (2012)
Kolmogorov, V., Boykov, Y., Rother, C.: Applications of parametric maxflow in computer vision. In: IEEE International Conference on Computer Vision (2007)
Kolmogorov, V., Rother, C.: Minimizing non-submodular functions with graph cuts - a review. IEEE transactions on Pattern Analysis and Machine Intelligence 29(7), 1274–1279 (July 2007)
Lange, K., Hunter, D.R., Yang, I.: Optimization transfer using surrogate objective functions. Journal of Computational and Graphical Statistics 9(1), 1–20 (2000)
Lee, D.D., Seung, H.S.: Algorithms for non-negative matrix factorization. In: NIPS, pp. 556–562 (2000)
Leordeanu, M., Hebert, M., Sukthankar, R.: An integer projected fixed point method for graph matching and map inference. In: NIPS, pp. 1114–1122 (2009)
Li, T., Ma, S., Ogihara, M.: Entropy-based criterion in categorical clustering. In: Proc. of Intl. Conf. on Machine Learning (ICML), pp. 536–543 (2004)
Mukherjee, L., Singh, V., Dyer, C.R.: Half-integrality based algorithms for cosegmentation of images. In: CVPR. pp. 2028–2035 (2009)
Narasimhan, M., Bilmes, J.A.: A submodular-supermodular procedure with applications to discriminative structure learning. In: UAI, pp. 404–412 (2005)
Nieuwenhuis, C., Toeppe, E., Gorelick, L., Veksler, O., Boykov, Y.: Efficient squared curvature. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Columbus, Ohio (June 2014)
Pham, V.Q., Takahashi, K., Naemura, T.: Foreground-background segmentation using iterated distribution matching. In: CVPR. pp. 2113–2120 (2011)
Rother, C., Kolmogorov, V., Lempitsky, V., Szummer, M.: Optimizing binary mrfs via extended roof duality. In: IEEE CVPR (2007)
Rother, C., Minka, T.P., Blake, A., Kolmogorov, V.: Cosegmentation of image pairs by histogram matching - incorporating a global constraint into mrfs. In: CVPR. pp. 993–1000 (2006)
Rother, C., Kolmogorov, V., Blake, A.: Grabcut - interactive foreground extraction using iterated graph cuts. In: ACM Tran. on Graphics, SIGGRAPH (2004)
Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22(8), 888–905 (2000)
Shotton, J., Sharp, T., Kohli, P., Nowozin, S., Winn, J., Criminisi, A.: Decision jungles: Compact and rich models for classification. In: Advances in Neural Information Processing Systems (NIPS), pp. 234–242 (2013)
Tang, M., Gorelick, L., Veksler, O., Boykov, Y.: Grabcut in one cut. In: International Conference on Computer Vision (ICCV), Sydney, Australia (2013)
Vicente, S., Kolmogorov, V., Rother, C.: Joint optimization of segmentation and appearance models. In: IEEE ICCV (2009)
Woodford, O.J., Rother, C., Kolmogorov, V.: A global perspective on map inference for low-level vision. In: ICCV, pp. 2319–2326 (2009)
Yuan, Y.: A review of trust region algorithms for optimization. In: Proceedings of the Fourth International Congress on Industrial and Applied Mathematics, ICIAM (1999)
Zhang, Z., Kwok, J.T., Yeung, D.Y.: Surrogate maximization/minimization algorithms and extensions. Machine Learning 69, 1–33 (2007)
Zhu, S.C., Yuille, A.: Region competition: Unifying snakes, region growing, and Bayes/MDL for multiband image segmentation. IEEE Transactions on PAMI 18(9), 884–900 (1996)
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
Tang, M., Ben Ayed, I., Boykov, Y. (2014). Pseudo-bound Optimization for Binary Energies. 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_45
Download citation
DOI: https://doi.org/10.1007/978-3-319-10602-1_45
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-10601-4
Online ISBN: 978-3-319-10602-1
eBook Packages: Computer ScienceComputer Science (R0)