An expectation-maximisation approach to graph matching | SpringerLink
Skip to main content
Springer Nature Link
Log in

An expectation-maximisation approach to graph matching

  • Structural Models
  • Conference paper
  • First Online:
Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR 1997)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1223))

Abstract

This paper describes how relational graph matching can be effected using the EM algorithm. The matching process is realised as a two-step iterative process. Firstly, updated symbolic matches are located so as to minimise a Kullback-Leibler divergence between the model and data graphs. Secondly, with the updated matches to hand probabilities describing the affinity between nodes in the model and data graphs may be computed. The probability distributions underpinning this study are computed using a simple model of uniform matching errors. As a result the Kullback-Leibler divergence is defined over a family of exponential distributions of Hamming distance. We evaluate the noise sensitivity of our matching method on synthetically generated graphs. Finally, we offer comparison with both mean-field annealing and quadratic assignment.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aarts E. and Korst J., “Simulated Annealing and Boltzmann Machines”, John Wiley and Sons, New York, 1989.

    Google Scholar 

  2. Adelson E.H. and Weiss Y., “A Unified Mixture Framework for Motion Segmentation: Incorporating Spatial Coherence and Estimating the Number of Models” Proceedings IEEE CVPR Conference, pp. 321–326, 1996.

    Google Scholar 

  3. Barrow H.G. and R.J. Popplestone, “Relational Descriptions in Picture Processing”, Machine Intelligence, 6, 1971.

    Google Scholar 

  4. Becker S. and Hinton G.E, “Learning Mixture Models of Spatial Coherence”, Neural Computation, 5, pp 267–277, 1992.

    Google Scholar 

  5. Blake A. and Zisserman A., “Visual Reconstruction”, MIT Press, 1987.

    Google Scholar 

  6. Bridle J.S. “Training stochastic model recognition algorithms can lead to maximum mutual information estimation of parameters” NIPS2, pp. 211–217, 1990.

    Google Scholar 

  7. Cross A.D. J., R.C. Wilson and E.R. Hancock, “Discrete Relaxation on a Boltzmann Machine”, Proceedings ICANN 95, pp. 491–496,1995.

    Google Scholar 

  8. Cross A.D.J., R.C. Wilson and E.R. Hancock, “Genetic Search for structural matching”, Proceedings ECCV96, Lecture Notes in Computer Science 1064, pp. 514–525, 1996.

    Google Scholar 

  9. Cross A.D.J. and E.R.Hancock, “Relational Matching with stochastic optimisation” IEEE Computer Society International Symposium on Computer Vision, pp. 365–370, 1995.

    Google Scholar 

  10. Dayan P., Hinton G.E., Neal R.M., Zemel R.S., “The Helmholtz Machine”, Neural Computation, 7, pp. 889–904, 1995.

    PubMed  Google Scholar 

  11. Dempster A.P., Rubin N.M. and Rubin D.B., “Maximum-likelihood from incomplete data via the EM algorithm”, J. Royal Statistical Soc. Ser. B (methodological), 39, pp 1–38, 1977.

    Google Scholar 

  12. Durbin R. and Willshaw D., “An analogue approach to the travelling salesman problem”, Nature, 326, pp. 689–691, 1987.

    PubMed  Google Scholar 

  13. Durbin R., Szeliski R. and Yuille A.L., “An analysis of the elastic net approach to the travelling salesman problem”, Neural Computation, 1, 348–358, 1989.

    Google Scholar 

  14. Finch A.M., Wilson R.C. and Hancock E.R., “Relational Matching with Mean-Field Annealing”, Proceedings of the 13th International Confererence on Pattern Recognition, Volume II, pp. 359–363, 1996.

    Google Scholar 

  15. Finch A.M., Wilson R.C. and Hancock E.R., “Softening Discrete Relaxation”, to appear in Advances in Neural Information Processing Systems 9, MIT Press 1997.

    Google Scholar 

  16. Geman S. and D. Geman, “Stochastic relaxation, Gibbs distributions and Bayesian restoration of images,” IEEE PAMI, PAMI-6, pp. 721–741, 1984.

    Google Scholar 

  17. Gold S., A. Rangarajan and E. Mjolsness, “Learning with pre-knowledge: Clustering with point and graph-matching distance measures”, Neural Computation, 8, pp. 787–804, 1996.

    Google Scholar 

  18. Gold S. and A. Rangarajan, “A Graduated Assignment Algorithm for Graph Matching”, IEEE PAMI, 18, pp. 377–388, 1996.

    Google Scholar 

  19. Hancock, E.R. and J. Kittler, “Discrete Relaxation,” Pattern Recognition, 23, pp. 711–733, 1990.

    Article  Google Scholar 

  20. Hornegger J. and H. Niemann, “Statistical Learning Localisation and Identification of Objects” Proceedings Fifth International Conference on Computer Vision, pp. 914–919, 1995.

    Google Scholar 

  21. Jordan M.I. and Jacobs R.A, “Hierarchical Mixtures of Experts and the EM Algorithm”, Neural Computation, 6, pp. 181–214, 1994.

    Google Scholar 

  22. Kirkpatrick S., C.D. Gelatt and M.P. Vecchi, “Optimisation by Simulated Annealing”, Science, 220, pp. 671–680, 1983.

    Google Scholar 

  23. Maclean J. and Jepson A., “Recovery of Ego-motion and Segmentation of Independent Object Motion using the EM Algorithm”, Proceedings BMVC, pp. 175–184, 1994.

    Google Scholar 

  24. Meer P., Mintz D., Rosenfeld A. and Kim D.Y., “Robust Regression Methods for Computer Vision — A Review”, International Journal of Computer vision, 6, pp. 59–70, 1991.

    Article  Google Scholar 

  25. Mjolsness E., G. Gindi and P. Anandan, “Optimisation in model matching and perceptual organisation”, Neural Computation, 1, pp. 218–219, 1989.

    Google Scholar 

  26. Moghaddam B. and Pentland A., “Probabilistic Visual Learning for Object Detection”, Proceedings of the Fifth International Conference on Computer Vision, pp. 786–793, 1995.

    Google Scholar 

  27. Novovicova J., Pudil P. and Kittler J., “Divergence Based Feature Selection for Multi-modal Class Densities”, IEEE PAMI, 18, pp. 218–223, 1996.

    Google Scholar 

  28. Peterson C. and Soderberg B., “A New Method for Mapping Optimisation Problems”, International Journal of Neural Systems, 1, pp 2–33, 1989.

    Article  Google Scholar 

  29. Sanfeliu A. and Fu K.S., “A Distance Measure Between Attributed Relational Graphs for Pattern Recognition”, IEEE SMC, 13, pp 353–362, 1983.

    Google Scholar 

  30. Shapiro L. and R.M. Haralick, “Structural Description and Inexact Matching”, IEEE PAMI, 3, pp 504–519, 1981.

    Google Scholar 

  31. Shapiro L. and R.M. Haralick, “A Metric for Comparing Relational Descriptions”, IEEE PAMI, 7, pp 90–94, 1985.

    Google Scholar 

  32. Simic P., “Constrained nets for graph matching and other quadratic assignment problems”, Neural Computation, 3, pp. 268–281, 1991.

    Google Scholar 

  33. Suganathan P.N., E.K. Teoh and D.P. Mital, “Pattern Recognition by Graph Matching using Potts MFT Networks”, Pattern Recognition, 28, pp. 997–1009, 1995.

    Article  Google Scholar 

  34. Utans J., “Mixture Models and the EM Algorithms for Object Recognition within Compositional Hierarchies”, ICSI Berkeley Technical Report, TR-93-004, 1993.

    Google Scholar 

  35. P. Viola and W. Wells, “Alignment by Maximisation of Mutual Information”, Proceedings of the Fifth International Conference on computer Vision, pp. 16–23, 1995.

    Google Scholar 

  36. Wells W.M., “MAP Model Matching”, IEEE Computer Society Computer Vision and Pattern Recognition Conference, pp. 486–492, 1991.

    Google Scholar 

  37. Wilson R.C., Evans A.N. and Hancock E.R., “Relational Matching by Discrete Relaxation”, Image and Vision Computing, 13, pp. 411–421, 1995.

    Article  Google Scholar 

  38. Wilson R.C and Hancock E.R., “Relational Matching with Dynamic Graph Structures”, Proceedings of the Fifth International Conference on Computer Vision, pp. 450–456, 1995.

    Google Scholar 

  39. Yuille A.L., Stolorz P. and Utans J., “Statistical Physics, Mixtures of Distributions, and the EM Algorithm” Neural Computation, 6, pp. 334–340, 1994.

    Google Scholar 

  40. Yuille A., “Generalised Deformable Models, Statistical Physics and Matching Problems”, Neural Computation, 2, pp. 1–24, 1990.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of York, Y01 5DD, York, UK

    Andrew M. Finch, Richard C. Wilson & Edwin R. Hancock

Authors
  1. Andrew M. Finch
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Richard C. Wilson
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Edwin R. Hancock
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Marcello Pelillo Edwin R. Hancock

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Finch, A.M., Wilson, R.C., Hancock, E.R. (1997). An expectation-maximisation approach to graph matching. In: Pelillo, M., Hancock, E.R. (eds) Energy Minimization Methods in Computer Vision and Pattern Recognition. EMMCVPR 1997. Lecture Notes in Computer Science, vol 1223. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62909-2_95

Download citation

  • DOI: https://doi.org/10.1007/3-540-62909-2_95

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-62909-2

  • Online ISBN: 978-3-540-69042-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation