1886Accesses
536Citations
6 Altmetric
Abstract
This paper proposes a novel framework for labelling problems which is able to combine multiple segmentations in a principled manner. Our method is based on higher order conditional random fields and uses potentials defined on sets of pixels (image segments) generated using unsupervised segmentation algorithms. These potentials enforce label consistency in image regions and can be seen as a generalization of the commonly used pairwise contrast sensitive smoothness potentials. The higher order potential functions used in our framework take the form of the RobustPn model and are more general than thePn Potts model recently proposed by Kohli et al. We prove that the optimalswap andexpansion moves for energy functions composed of these potentials can be computed by solving a st-mincut problem. This enables the use of powerful graph cut based move making algorithms for performing inference in the framework. We test our method on the problem of multi-class object segmentation by augmenting the conventionalcrf used for object segmentation with higher order potentials defined on image regions. Experiments on challenging data sets show that integration of higher order potentials quantitatively and qualitatively improves results leading to much better definition of object boundaries. We believe that this method can be used to yield similar improvements for many other labelling problems.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
Explore related subjects
Discover the latest articles and news from researchers in related subjects, suggested using machine learning.References
Alahari, K., Kohli, P., & Torr, P. (2008). Reduce, reuse and recycle: efficiently solving multi-label MRFs. InIEEE conference on computer vision and pattern recognition.
Blake, A., Rother, C., Brown, M., Perez, P., & Torr, P. (2004). Interactive image segmentation using an adaptive GMMRF model. InEuropean conference on computer vision (pp. I: 428–441).
Borenstein, E., & Malik, J. (2006). Shape guided object segmentation. InIEEE conference on computer vision and pattern recognition (pp. 969–976).
Boros, E., & Hammer, P. (2002). Pseudo-boolean optimization.Discrete Applied Mathematics,123(1–3), 155–225.
Boykov, Y., & Jolly, M. (2001). Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images. InInternational conference on computer vision (pp. I: 105–112).
Boykov, Y., Veksler, O., & Zabih, R. (2001). Fast approximate energy minimization via graph cuts.IEEE Transactions on Pattern Analysis and Machine Intelligence,23(11), 1222–1239.
Bray, M., Kohli, P., & Torr, P. (2006). Posecut: Simultaneous segmentation and 3d pose estimation of humans using dynamic graph-cuts. InEuropean conference on computer vision (pp. 642–655).
Comaniciu, D., & Meer, P. (2002). Mean shift: A robust approach toward feature space analysis.IEEE Transactions on Pattern Analysis and Machine Intelligence,24(5), 603–619.
Felzenszwalb, P., & Huttenlocher, D. (2004). Efficient graph-based image segmentation.International Journal of Computer Vision,59(2), 167–181.
Flach, B. (2002).Strukturelle bilderkennung (Tech. Rep.). Universit at Dresden.
Freedman, D., & Drineas, P. (2005). Energy minimization via graph cuts: Settling what is possible. InIEEE conference on computer vision and pattern recognition (pp. 939–946).
Fujishige, S. (1991).Submodular functions and optimization. Amsterdam: North-Holland.
He, X., Zemel, R., & Carreira-Perpiñán, M. (2004). Multiscale conditional random fields for image labeling. InIEEE conference on computer vision and pattern recognition (2) (pp. 695–702).
He, X., Zemel, R., & Ray, D. (2006). Learning and incorporating top-down cues in image segmentation. InEuropean conference on computer vision (pp. 338–351).
Hoiem, D., Efros, A., & Hebert, M. (2005a). Automatic photo pop-up.ACM Transactions on Graphics,24(3), 577–584.
Hoiem, D., Efros, A., & Hebert, M. (2005b). Geometric context from a single image. InInternational conference on computer vision (pp. 654–661).
Huang, R., Pavlovic, V., & Metaxas, D. (2004). A graphical model framework for coupling MRFs and deformable models. InIEEE conference on computer vision and pattern recognition (Vol. 11, pp. 739–746).
Ishikawa, H. (2003). Exact optimization for Markov random fields with convex priors.IEEE Transactions on Pattern Analysis and Machine Intelligence,25, 1333–1336.
Kohli, P., Kumar, M., & Torr, P. (2007).P3 and beyond: solving energies with higher order cliques. InIEEE conference on computer vision and pattern recognition.
Kohli, P., Ladicky, L., & Torr, P. (2008). Robust higher order potentials for enforcing label consistency. InCVPR.
Kolmogorov, V. (2006). Convergent tree-reweighted message passing for energy minimization.IEEE Transactions on Pattern Analysis and Machine Intelligence,28(10), 1568–1583.
Kolmogorov, V., & Zabih, R. (2004). What energy functions can be minimized via graph cuts?IEEE Transactions on Pattern Analysis and Machine Intelligence,26(2), 147–159.
Komodakis, N., & Tziritas, G. (2005). A new framework for approximate labeling via graph cuts. InInternational conference on computer vision (pp. 1018–1025).
Komodakis, N., Tziritas, G., & Paragios, N. (2007). Fast, approximately optimal solutions for single and dynamic MRFs. InCVPR.
Kumar, M., & Torr, P. (2008). Improved moves for truncated convex models. InProceedings of advances in neural information processing systems.
Kumar, M., Torr, P., & Zisserman, A. (2005). Obj cut. InIEEE conference on computer vision and pattern recognition (1) (pp. 18–25).
Lafferty, J., McCallum, A., & Pereira, F. (2001). Conditional random fields: Probabilistic models for segmenting and labelling sequence data. InInternational conference on machine learning (pp. 282–289).
Lan, X., Roth, S., Huttenlocher, D., & Black, M. (2006). Efficient belief propagation with learned higher-order Markov random fields. InEuropean conference on computer vision (pp. 269–282).
Lauristzen, S. (1996).Graphical models. Oxford: Oxford University Press.
Lempitsky, V., Rother, C., & Blake, A. (2007). Logcut—efficient graph cut optimization for Markov random fields. InICCV.
Levin, A., & Weiss, Y. (2006). Learning to combine bottom-up and top-down segmentation. InEuropean conference on computer vision (pp. 581–594).
Lovasz, L. (1983). Submodular functions and convexity. InMathematical programming: the state of the art (pp. 235–257).
Orlin, J. (2007). A faster strongly polynomial time algorithm for submodular function minimization. InProceedings of integer programming and combinatorial optimization (pp. 240–251).
Paget, R., & Longstaff, I. (1998). Texture synthesis via a noncausal nonparametric multiscale Markov random field.IEEE Transactions on Image Processing,7(6), 925–931.
Potetz, B. (2007). Efficient belief propagation for vision using linear constraint nodes. InIEEE conference on computer vision and pattern recognition.
Rabinovich, A., Belongie, S., Lange, T., & Buhmann, J. (2006). Model order selection and cue combination for image segmentation. InIEEE conference on computer vision and pattern recognition (1) (pp. 1130–1137).
Ren, X., & Malik, J. (2003). Learning a classification model for segmentation. InInternational conference on computer vision (pp. 10–17).
Roth, S., & Black, M. (2005). Fields of experts: A framework for learning image priors. InIEEE conference on computer vision and pattern recognition (pp. 860–867).
Rother, C., Kolmogorov, V., & Blake, A. (2004). Grabcut: interactive foreground extraction using iterated graph cuts. InACM transactions on graphics (pp. 309–314).
Russell, B., Freeman, W., Efros, A., Sivic, J., & Zisserman, A. (2006). Using multiple segmentations to discover objects and their extent in image collections. InIEEE conference on computer vision and pattern recognition (2) (pp. 1605–1614).
Schlesinger, D., & Flach, B. (2006).Transforming an arbitrary minsum problem into a binary one (Tech. Rep. TUD-FI06-01). Dresden University of Technology, April 2006.
Sharon, E., Brandt, A., & Basri, R. (2001). Segmentation and boundary detection using multiscale intensity measurements. InIEEE conference on computer vision and pattern recognition (1) (pp. 469–476).
Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation.IEEE Transactions on Pattern Analysis and Machine Intelligence,22(8), 888–905.
Shotton, J., Winn, J., Rother, C., & Criminisi, A. (2006). TextonBoost: Joint appearance, shape and context modeling for multi-class object recognition and segmentation. InEuropean conference on computer vision (pp. 1–15).
Tu, Z., & Zhu, S. (2002). Image segmentation by data-driven Markov chain Monte Carlo.IEEE Transactions on Pattern Analysis and Machine Intelligence,24(5), 657–673.
Veksler, O. (2007). Graph cut based optimization for MRFs with truncated convex priors. InCVPR.
Wainwright, M., Jaakkola, T., & Willsky, A. (2005). Map estimation via agreement on trees: message-passing and linear programming.IEEE Transactions on Information Theory,51(11), 3697–3717.
Wang, J., Bhat, P., Colburn, A., Agrawala, M., & Cohen, M. (2005). Interactive video cutout.ACM Transactions on Graphics,24(3), 585–594.
Yedidia, J., Freeman, W., & Weiss, Y. (2000). Generalized belief propagation. InNIPS (pp. 689–695).
Author information
Authors and Affiliations
Microsoft Research, Cambridge, UK
Pushmeet Kohli
Oxford Brookes University, Oxford, UK
L’ubor Ladický & Philip H. S. Torr
- Pushmeet Kohli
Search author on:PubMed Google Scholar
- L’ubor Ladický
Search author on:PubMed Google Scholar
- Philip H. S. Torr
Search author on:PubMed Google Scholar
Corresponding author
Correspondence toPushmeet Kohli.
Rights and permissions
About this article
Cite this article
Kohli, P., Ladický, L. & Torr, P.H.S. Robust Higher Order Potentials for Enforcing Label Consistency.Int J Comput Vis82, 302–324 (2009). https://doi.org/10.1007/s11263-008-0202-0
Received:
Accepted:
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative