Abstract
Bayesian inference provides a powerful framework to optimally integrate statistically learned prior knowledge into numerous computer vision algorithms. While the Bayesian approach has been successfully applied in the Markov random field literature, the resulting combinatorial optimization problems have been commonly treated with rather inefficient and inexact general purpose optimization methods such as Simulated Annealing. An efficient method to compute the global optima of certain classes of cost functions defined on binary-valued variables is given by graph min-cuts. In this paper, we propose to reconsider the problem of statistical learning for Bayesian inference in the context of efficient optimization schemes. Specifically, we address the question: Which prior information may be learned while retaining the ability to apply Graph Cut optimization? We provide a framework to learn and impose prior knowledge on the distribution of pairs and triplets of labels. As an illustration, we demonstrate that one can optimally restore binary textures from very noisy images with runtimes on the order of a second while imposing hundreds of statistically learned constraints per pixel.
Chapter PDF
Similar content being viewed by others
Keywords
- Bayesian Inference
- Combinatorial Optimization Problem
- Markov Chain Monte Carlo Method
- Statistical Prior
- Stripe Pattern
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abend, K., Harley, T., Kanal, L.N.: Classification of binary random patterns. IEEE Transactions on Information Theory 11, 538–544 (1965)
Barbu, A., Zhu, S.-C.: Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities. IEEE Trans. on Patt. Anal. and Mach. Intell. 27(8), 1239–1253 (2005)
Besag, J.: On the statistical analysis of dirty pictures. J. Roy. Statist. Soc, Ser. B. 48(3), 259–302 (1986)
Blake, A., Zisserman, A.: Visual Reconstruction. MIT Press, Cambridge (1987)
Boykov, Y., Kolmogorov, V.: An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. on Patt. Anal. and Mach. Intell. 26(9), 1124–1137 (2004)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. on Patt. Anal. and Mach. Intell. 23(11), 1222–1239 (2001)
Cross, G.R., Jain, A.K.: Markov random fields texture models. IEEE Trans. on Patt. Anal. and Mach. Intell. 5(1), 25–39 (1983)
Derin, H., Elliott, H.: Modeling and segmentation of noisy and textured images using Gibbs random fields. IEEE Trans. on Patt. Anal. and Mach. Intell. 9(1), 39–55 (1987)
Ford, L., Fulkerson, D.: Flows in Networks. Princeton University Press, Princeton (1962)
Freeman, W.T., Pasztor, E.C., Carmichael, O.T.: Learning low-level vision. Int. J. of Computer Vision 40(1), 24–57 (2000)
Geman, S., Geman, D.: Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. on Patt. Anal. and Mach. Intell. 6(6), 721–741 (1984)
Gimelfarb, G.: Texture modeling by multiple pairwise pixel interaction. IEEE Trans. on Patt. Anal. and Mach. Intell. 18(11), 1110–1114 (1993)
Greig, D.M., Porteous, B.T., Seheult, A.H.: Exact maximum a posteriori estimation for binary images. J. Roy. Statist. Soc., Ser. B 51(2), 271–279 (1989)
Ishikawa, H.: Exact optimization for Markov random fields with convex priors. IEEE Trans. on Patt. Anal. and Mach. Intell. 25(10), 1333–1336 (2003)
Ising, E.: Beitrag zur Theorie des Ferromagnetismus. Zeitschrift für Physik 23, 253–258 (1925)
Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Trans. on Patt. Anal. and Mach. Intell. 24(5), 657–673 (2004)
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 3rd edn. Springer, Heidelberg (2006)
Kumar, S., Hebert, M.: Approximate parameter learning in discriminative fields. In: Snowbird Learning Workshop, Utah (2004)
Manjunath, B.S., Chellappa, R.: Unsupervised texture segmentation using Markov random field models. IEEE Trans. on Patt. Anal. and Mach. Intell. 13(5), 478–482 (1991)
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Physics 21, 1087–1092 (1953)
Picard, J.C., Ratliff, H.D.: Minimum cuts and related problems. Networks 5, 357–370 (1975)
Pieczynski, W., Benboudjema, D., Lanchantin, P.: Statistical image segmentation using triplet Markov fields. In: SPIE Int. Symposium on Image and Signal Processing for Remote Sensing VIII, March, vol. 4885, pp. 92–101. SPIE (2003)
Winkler, G.: Image Analysis, Random Fields and Markov Chain Monte Carlo Methods. Appl. of Mathematics, vol. 27. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cremers, D., Grady, L. (2006). Statistical Priors for Efficient Combinatorial Optimization Via Graph Cuts. In: Leonardis, A., Bischof, H., Pinz, A. (eds) Computer Vision – ECCV 2006. ECCV 2006. Lecture Notes in Computer Science, vol 3953. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11744078_21
Download citation
DOI: https://doi.org/10.1007/11744078_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33836-9
Online ISBN: 978-3-540-33837-6
eBook Packages: Computer ScienceComputer Science (R0)