Skip to main content
SpringerLink
Log in

The theory and practice of Bayesian image labeling

  • Published:
International Journal of Computer Vision Aims and scope Submit manuscript

Abstract

Image analysis that produces an image-like array of symbolic or numerical elements (such as edge finding or depth map reconstruction) can be formulated as a labeling problem in which each element is to be assigned a label from a discrete or continuous label set. This formulation lends itself to algorithms, based on Bayesian probability theory, that support the combination of disparate sources of information, including prior knowledge.

In the approach described here, local visual observations for each entity to be labeled (e.g., edge sites, pixels, elements in a depth array) yield label likelihoods. Likelihoods from several sources are combined consistently in abstraction-hierarchical label structures using a new, computationally simple procedure. The resulting label likelihoods are combined with a priori spatial knowledge encoded in a Markov random field (MRF). From the prior probabilities and the evidence-dependent combined likelihoods, the a posteriori distribution of the labelings is derived using Bayes' theorem.

A new inference method, Highest Confidence First (HCF) estimation, is used to infer a unique labeling from the a posteriori distribution that is consistent with both prior knowledge and evidence. HCF compares favorably to previous techniques, all equivalent to some form of energy minimization or optimization, in finding a good MRF labeling. HCF is computationally efficient and predictable and produces better answers (lower energies) while exhibiting graceful degradation under noise and least commitment under inaccurate models. The technique generalizes to higher-level vision problems and other domains, and is demonstrated on problems of intensity edge detection and surface depth reconstruction.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J.Pearl, “On evidential reasoning in a hierarchy of hypotheses,” Artificial Intelligence 28 (1):9–15, 1986.

    Google Scholar 

  2. G. Reynolds, D. Strahman, N. Lehrer, and L. Kitchen, “Plausible reasoning and the theory of evidence,” COINS Technical Report 86-11, April 1986.

  3. A.Rosenfeld, R.Hummel, and S.Zucker, “Scene labeling by relaxation operations,” IEEE Trans. Syst., Man, Cybern, 6:420, 1976.

    Google Scholar 

  4. S.Peleg, “A new probabilistic relaxation scheme,” IEEE Trans. PAMI 2:362, 1980.

    Google Scholar 

  5. L.S.Davis and A.Rosenfeld, “Cooperating processes for lowlevel vision: A survey,” Artificial Intelligence 17:245–263, 1981.

    Google Scholar 

  6. J.Kittler and J.Foglein, “On compatibility and support functions in probabilistic relaxation,” Comput. Vision, Graphics, Image Process. 34:257–267, 1986.

    Google Scholar 

  7. R.M.Haralick, “An interpretation for probabilistic relaxation,” Comput. Vision, Graphics, Image Process. 22:388–395, 1983.

    Google Scholar 

  8. J.Gordon and E.H.Shortliffe, “A method of managing evidential reasoning in a hierarchical hypothesis space,” Artificial Intelligence 26:323–357, 1985.

    Google Scholar 

  9. P.B. Chou, “The theory and practice of Bayesian image labeling,” Tech. Reprt. 258, Computer Science Department, University of Rochester, August 1988.

  10. P.B. Chou and C.M. Brown, “Probabilistic information fusion for multi-modal image segmentation,” Proc. 10th Intern. Joint Conf. Artif. Intell., Milan, Italy, August 1987.

  11. I.J.Good, Probability and the Weighing of Evidence, Hafner Publishing: New York, 1950.

    Google Scholar 

  12. R.O. Duda, P.E. Hart and N.J. Nilsson, “Subjective Bayesian methods for rule-based inference systems,” SRI Tech. Note 124, SRI International, 1976.

  13. R.C. Bolles, “Verification vision for programmable assembly,” Proc. 5th Intern. Joint Conf. Artif. Intell., Cambridge, MA. pp. 569–575, August 1977.

  14. D.B. Sher, “A probabilistic approach to low-level vision,” Tech. Reprt. 232, University of Rochester, October 1987.

  15. R.M.Bolle and D.B.Cooper, “Bayesian recognition of local 3-D shape by approximating image intensity functions with quadric polynomials,” IEEE Trans. PAMI 6 (4):418–429, 1984.

    Google Scholar 

  16. R.M.Bolle and D.B.Cooper, “Optimal statistical techniques for combining pieces of information applied to 3-D complex object position estimation.” In Pattern Recognition in Practice, E.S.Gelsema and L.N.Kanal (eds.), Elsevier Science Publishers: North Holland, pp. 243–253, 1986.

    Google Scholar 

  17. J. Besag, “On the statistical analysis of dirty pictures,” J. Roy. Statis. Soc. B48(3), 1986.

  18. H.Derin and W.S.Cole, “Segmentation of textured images using Gibbs random fields,” Comput. Vision, Graphics, Image Process. 35:72–98, 1986.

    Google Scholar 

  19. J.L. Marroquin, Probabilistic Solution of Inverse Problems, MIT Artificial Intelligence Laboratory, September 1985.

  20. J.Besag, “Spatial interaction and the statistical analysis of lattice systems (with discussion),” J. Roy. Statis. Soc., ser. B 36:192–326, 1974.

    Google Scholar 

  21. M.Hassner and J.Slansky, “The use of Markov random fields as models of texture.” In Image Modeling, A.Rosenfeld (ed.), Academic Press: San Diego, CA, pp. 185–198, 1980.

    Google Scholar 

  22. G.R.Cross and A.K.Jain, “Markov random field texture models,” IEEE Trans. PAMI 5(1):25–39, 1983.

    Google Scholar 

  23. J. Marroquin, S. Mitter, and T. Poggio, “Probabilistic solution of ill-posed problems in computational vision,” Proc. Image Understanding Workshop, pp. 293–309, December 1985.

  24. S.Geman and D.Geman, “Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images,” IEEE Trans. PAMI 6(6):721–741, 1984.

    Google Scholar 

  25. D.W.Murray and B.F.Buxton, “Seene segmentation from visual motion using global optimization,” IEEE Trans. PAMI 9(2):220–228, 1987.

    Google Scholar 

  26. F.S.Cohen and D.B.Cooper, “Simple parallel hierarchical and relaxation algorithms for segmenting noncausal Markovian random fields,” IEEE Trans. PAMI 9(2):195–219, 1987.

    Google Scholar 

  27. R. Szeliski, “Regularization uses fractal priors,” Proc. AAAI 87, July 1987.

  28. S. Geman and C. Graffigne, “Markov random field image models and their applications to computer vision,” Proc. Intern. Cong. Mathematicians, Berkeley, CA, pp. 1496–1517, 1986.

  29. T. Poggio, “Integrating vision modules with coupled MRFs,” Working Paper No. 285, MIT A.I. Lab., December 1985.

  30. E. Gamble and T. Poggio, “Visual integration and detection of discontinuities: The key role of intensity edges,” MIT A.I. Memo No. 970. October 1987.

  31. R. Kindermann and J.L. Snell, “Markov random fields and their applications.” In Contemporary Mathematics, vol. 1, American Mathematical Society, 1980.

  32. G.E. Hinton and T.J. Sejnowski, “Optimal perceptual inference,” Proc. IEEE Conf. Comput. Vision Pattern Recog., Washington, D.C., 1983.

  33. J.Besag, “Statistical analysis of non-lattice data,” The Statistician 24:179–195, 1975.

    Google Scholar 

  34. H. Elliott and H. Derin, “Modeling and segmentation of noisy and textured images using Gibbs random fields,” #ECE-UMASS-SE84-I, University of Massachusetts, 1984.

  35. J.A.Feldman and Y.Yakimovsky, “Decision theory and artificial intelligence: I.A Semanties-Based Region Analyzer,” Artificial Intelligence 5:349–371, 1974.

    Google Scholar 

  36. N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller, “Equations of state calculations by fast computing machines,” J. Chem. Physics 21, 1953.

  37. J.J. Hopfield and D.W. Tank, ““Neural” computation of decisions in optimization problems,” Biological Cybernetics 52, 1985.

  38. D.Marr, VISION, W.H. Freeman: New York, 1982.

    Google Scholar 

  39. J.A. Feldman and D.H. Ballard, “Computing with connections,” Tech. Rept. 72, Computer Science Department, University of Rochester, 1981.

  40. C.Koch, J.Marroquin, and A.Yuille, “Analog ‘Neuronal’ Networks in Early Vision,” Proc. Nat. Acad. Sci. USA 83:4263–4267, 1986.

    Google Scholar 

  41. A.Blake and A.Zisserman, Visual Reconstruction, MIT Press: Cambridge, MA, 1987.

    Google Scholar 

  42. D.B. Sher, “Advanced likelihood generators for boundary detection,” TR197, University of Rochester, Computer Science Dept., January 1987.

  43. B.H. Stuth, D.H. Ballard and C.M. Brown, “Boundary conditions in multiple intrinsic images,” Proc. 8th Intern. Joint Conf. Artif. Intell. Karlsruhe, pp. 1068–1072, 1983.

  44. J.F. Canny, “Finding edges and lines in images,” AI-Tech. Rept. 720, MIT Artificial Intelligence Laboratory, 1983.

  45. B.K.P.Horn, “Obtaining shape from shading information.” In The Psychology of Computer Vision, P.H.Winston (ed.). McGraw-Hill: New York, pp. 115–155, 1975.

    Google Scholar 

  46. P.R. Cooper, “Order and structure in correspondence by dynamic programming,” Tech. Rept. 216, University of Rochester, June 1987.

Download references

Author information

Authors and Affiliations

  1. IBM Research Division, Thomas J. Watson Research Center, 10598, Yorktown Heights, NY

    Paul B. Chou & Christopher M. Brown

  2. Computer Science Department, University of Rochester, 14627, Rochester, NY

    Paul B. Chou & Christopher M. Brown

Authors
  1. Paul B. Chou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christopher M. Brown
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chou, P.B., Brown, C.M. The theory and practice of Bayesian image labeling. Int J Comput Vision 4, 185–210 (1990). https://doi.org/10.1007/BF00054995

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00054995

Keywords

Search

Navigation