Skip to main content
SpringerLink
Log in

On the Foundations of Probabilistic Relaxation with Product Support

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

Traditional probabilistic relaxation, as proposed by Rosenfeld, Hummel and Zucker, uses a support function which is a double sum over neighboring nodes and labels. Recently, Pelillo has shown the relevance of the Baum-Eagon theorem to the traditional formulation. Traditional probabilistic relaxation is now well understood in an optimization framework.

Kittler and Hancock have suggested a form of probabilistic relaxation with product support, based on an evidence combining formula. In this paper we present a formal basis for Kittler and Hancocks probabilistic relaxation. We show that it too has close links with the Baum-Eagon theorem, and may be understood in an optimization framework. We provide some proofs to show that a stable stationary point must be a local maximum of an objective function.

We present a new form of probabilistic relaxation that can be used as an approximate maximizer of the global labeling with maximum posterior probability.

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. Kittler and J. Illingworth, “Relaxation labeling algorithms—A review,” Image and Vision Computing, Vol. 3, No.4, pp. 206–216, 1985.

    Google Scholar 

  2. S.-S. Yu and W.-H. Tsai, “Relaxation by the Hopfield neural network,” Pattern Recognition, Vol. 25, No.2, pp. 197–209, 1992.

    Google Scholar 

  3. J. Kittler, “Cooperative decision making processes and their neural net interpretation,” in From Statistics to Neural Networks, V. Cherkassky, J. H. Friedman, and H. Wechsler (Eds.), NATO Adv. Study Inst: Les Arcs, June 1993, pp. 263–281.

    Google Scholar 

  4. M. Pelillo and M. Refice, “Learning compatibility coefficients for relaxation labeling processes,” IEEE Pattern Analysis and Machine Intelligence, Vol. 16, No.9, pp. 933–945, 1994.

    Google Scholar 

  5. M. Pelillo, “On the dynamics of relaxation labeling processes,” IEEE Int. Conf. Neural Networks, Orlando, 1994.

  6. M. Pelillo, “The dynamics of nonlinear relaxation labeling processes,” Journal of Mathematical Imaging and Vision, Vol. 7, No.4, pp. 309–323, 1997.

    Google Scholar 

  7. A. Rosenfeld, R. A. Hummel, and S. W. Zucker, “Scene labeling by relaxation operations,” IEEE Trans. Systems, Man and Cybernetics, Vol. 6, pp. 420–433, 1976.

    Google Scholar 

  8. R. A. Hummel and S. W. Zucker, “On the foundations of relaxation labeling processes,” IEEE Pattern Analysis and Machine Intelligence, Vol. 5, No.3, pp. 267–287, 1983.

    Google Scholar 

  9. X. Zhuang, R. M. Haralick, and H. Joo, “A simplex-like algorithm for the relaxation labeling process,” IEEE Pattern Analysis and Machine Intelligence, Vol. 11, pp. 1316–1321, 1986.

    Google Scholar 

  10. S. W. Zucker, E. V. Krishnamurthy, and R. L. Haar, “Relaxation processes for scene labeling: convergence, speed and stability,” IEEE Trans. Systems, Man and Cybernetics, Vol. 8, pp. 41–48, 1978.

    Google Scholar 

  11. S. Peleg, “A new probabilistic relaxation scheme,” IEEE Pattern Analysis and Machine Intelligence, Vol. 2, No.4, pp. 362–369, 1980.

    Google Scholar 

  12. R. L. Kirby, “A product rule relaxation method,” Computer Graphics and Image Processing, Vol. 13, pp. 158–189, 1980.

    Google Scholar 

  13. S. A. Lloyd, “An optimization approach to relaxation labeling algorithms,” Image and Vision Computing, Vol. 1, No.2, pp. 85–91, 1983.

    Google Scholar 

  14. S. Ullman, “Relaxation and constrained optimization by local processes,” Computer Graphics and Image Processing, Vol. 10, pp. 115–125, 1979.

    Google Scholar 

  15. T. Elfving and J.-O. Eklundh, “Some properties of stochastic labeling procedures,” Computer Graphics and Image Processing, Vol. 20, pp. 158–170, 1982.

    Google Scholar 

  16. J. S. Duncan and W. Frei, “Relaxation labeling using continuous label sets,” Pattern Recognition Letters, Vol. 9, pp. 27–37, 1989.

    Google Scholar 

  17. J. S. Duncan and T. Birkhölzer, “Reinforcement of linear structure using parametrized relaxation labeling,” IEEE Pattern Analysis and Machine Intelligence, Vol. 14, No.5, pp. 502–515, 1992.

    Google Scholar 

  18. J. Kittler and E. R. Hancock, “Combining evidence in probabilistic relaxation,” Int. J. of Pattern Recognition and Artificial Intelligence, Vol. 3, No.1, pp. 25–51, 1989.

    Google Scholar 

  19. E. R. Hancock and J. Kittler, “Edge-labeling using dictionary-based relaxation,” IEEE Pattern Analysis and Machine Intelligence, Vol. 12, No.2, pp. 165–181, 1990.

    Google Scholar 

  20. W. J. Christmas, J. Kittler, and M. Petrou, “Structural matching in computer vision using probabilistic relaxation,” IEEE Pattern Analysis and Machine Intelligence, Vol. 17, No.8, pp. 749–764, 1995.

    Google Scholar 

  21. J. Kittler, P. Papachristou, and M. Petrou, “Combining evidence in dictionary based probabilistic relaxation,” in 8th Scandinavian Conference on Image Analysis, Tromso, Norway, 1993, pp. 785–795.

  22. J. Kittler and J. Foglein, “On compatibility and support functions in probabilistic relaxation,” Computer Vision, Graphics and Image Processing, Vol. 34, pp. 257–267, 1986.

    Google Scholar 

  23. B. M. ter Haar Romeny, Geometry-Driven Diffusion in Computer Vision, Kluwer: Dordrecht, The Netherlands, 1994.

    Google Scholar 

  24. D. Terzopoulos, “Regularisation of inverse visual problems involving discontinuities,” IEEE Pattern Analysis and Machine Intelligence, Vol. 8, No.4, pp. 413–424, 1986.

    Google Scholar 

  25. M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: active contour models,” Int. Conf. Computer Vision, London, 1987, pp. 259–268.

  26. J. Besag, “Spatial interaction and the statistical analysis of lattice systems,” J. Royal Statistical Society B-Methodological, Vol. 36, No.2, pp. 192–236, 1974.

    Google Scholar 

  27. K. E. Price, “Relaxation matching techniques—A comparison,” IEEE Pattern Analysis and Machine Intelligence, Vol. 7, No.5, pp. 617–623, 1985.

    Google Scholar 

  28. S. Geman and D. Geman, “Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images,” IEEE Pattern Analysis and Machine Intelligence, Vol. 6, No.6, pp. 721–741, 1984.

    Google Scholar 

  29. O. D. Faugeras and M. Berthod, “Improving consistency and reducing ambiguity in stochastic labeling: An optimization approach,” IEEE Pattern Analysis and Machine Intelligence, Vol. 3, No.4, pp. 412–424, 1981.

    Google Scholar 

  30. R. M. Haralick, “An interpretation for probabilistic relaxation,” Computer Vision, Graphics and Image Processing, Vol. 22, pp. 388–395, 1983.

    Google Scholar 

  31. R. Szeliski, “Bayesian modelling of uncertainty in low-level vision,” Kluwer: Boston, 1989.

    Google Scholar 

  32. D. Terzopoulos and R. Szeliski, “Tracking with Kalman Snakes,” Active Vision, A. Blake and A. Yuille (Eds.), MIT Press, 1993, Chapter 1.

  33. L. E. Baum and J. A. Eagon, “An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology,” Bulletin of the American Mathematical Society, Vol. 73, pp. 360–363, 1967. L. E. Baum, G. R. Sell, “Growth transformations for functions on manifolds,” Pacific Journal of Mathematics, Vol. 27, No. 2, pp. 211–227, 1968.

    Google Scholar 

  34. J.-P. LaSalle, The Stability and Control of Discrete Processes, Springer-Verlag: New York, 1986.

    Google Scholar 

  35. A. J. Stoddart, M. Petrou, and J. Kittler, “A new algorithm for probabilistic relaxation based on the Baum-Eagon theorem,” CAIP, Prague, Sept. 1995. Available at ftp://ftp.ee. surrey.ac.uk/pub/vision/papers.

    Google Scholar 

  36. A. J. Stoddart, M. Petrou, and J. Kittler, “Probabilistic relaxation as an optimizer,” British Machine Vision Conference, Birmingham: UK, Sept. 1995.

  37. J. Matas, R. Marik, and J. Kittler, “On representation and matching of multi-coloured objects,” Proc. of the 5th Int. Conf. on Computer Vision, Boston, 1995, pp. 726–732.

Download references

Author information

Authors and Affiliations

  1. School of Electronic Engineering, Information Technology and Mathematics, University of Surrey, Guildford, GU2 5XH, U.K.

    Andrew J. Stoddart, Maria Petrou & Josef Kittler

Authors
  1. Andrew J. Stoddart
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Maria Petrou
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Josef Kittler
    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

Stoddart, A.J., Petrou, M. & Kittler, J. On the Foundations of Probabilistic Relaxation with Product Support. Journal of Mathematical Imaging and Vision 9, 29–48 (1998). https://doi.org/10.1023/A:1008218126123

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008218126123

Search

Navigation