2001 StructuralGraphMatchingUsingEMandSVD

From GM-RKB
Jump to: navigation, search

Subject Headings: Graph Matching Task, Graph Distance Function, EM Algorithm, Matrix Factorization, Mixture Model, Delaunay Triangulation, Singular Value Decomposition.

Notes

Cited By

Quotes

Abstract

This paper describes an efficient algorithm for inexact graph matching. The method is purely structural, that is, it uses only the edge or connectivity structure of the graph and does not draw on node or edge attributes. We make two contributions: 1) commencing from a probability distribution for matching errors, we show how the problem of graph matching can be posed as maximum-likelihood estimation using the apparatus of the EM algorithm; and 2) we cast the recovery of correspondence matches between the graph nodes in a matrix framework. This allows one to efficiently recover correspondence matches using the singular value decomposition. We experiment with the method on both real-world and synthetic data. Here, we demonstrate that the method offers comparable performance to more computationally demanding methods


References

  • A.P. Ambler, H.G. Barrow, C.M. Brown, R.M. Burstall, and R.J. Popplestone, "A Versatile Computer-Controlled Assembly System," In: ProceedingsThird Int'l Conference Artifical Intelligence, pp. 298-307, 1973.
  • H.G. Barrow and R.J. Popplestone. (1971). “Relational Descriptions in Picture Processing." In: Machine Intelligence, 5.
  • R.E. Blake, Development of an Incremental Graph Matching Device, vol. 30, of NATO ASI series, pp. 355-366. Berlin: Spinger-Verlag, (1987).
  • K. Boyer and A. Kak. (). “Structural Stereopsis for 3D Vision." In: IEEE Trans. Pattern Analysis and Machine Intelligence]], vol. 10, no. 2, pp. 144-166, Feb. (1988).
  • J.S. Bridle. (). “Training Stochastic Model Recognition Algorithms can Lead to Maximum Mutual Information Estimation of Parameters." In: ProceedingsNeural Information Processing Systems, pp. 211-217, (1990).
  • H. Bunke. (). “Error Correcting Graph Matching: On the Influence of the Underlying Cost Function." In: IEEE Trans. Pattern Analysis and Machine Intelligence]], vol. 21, no. 9, pp. 917-922, Sept. (1999).
  • H. Bunke and G. Allermann. (). “Inexact Graph Matching for Structural Pattern Recognition." In: Pattern Recognition Letters, vol. 1, pp. 245-253, (1983).
  • H. Bunke and B.T. Messmer. (). “Recent Advances in Graph Matching." In: IEEE Trans. Pattern Analysis and Machine Intelligence]], vol. 11, pp. 169-203, (1997).
  • H. Bunke and K. Shearer. (). “A Graph Distance Metric Based on the Maximal Common Subgraph." In: Pattern Recognition Letters, vol. 19, pp. 255-259, (1998).
  • Christopher M. Bishop, Neural Networks for Pattern Recognition. Oxford: Clarendon Press, (1995).
  • W.J. Christmas, J. Kittler, and M. Petrou. (). “Structural Matching in Computer Vision Using Probabilistic Relaxation." In: IEEE Trans. Pattern Analysis and Machine Intelligence]], vol. 17, no. 8, pp. 749-764, Aug. (1995).
  • F.R.K. Chung, Spectral Graph Theory, Am. Math. Soc., ed., CBMS Series 92. 1997,
  • A.D.J. Cross and E.R. Hancock. (). “Graph Matching with a Dual- Step EM Algorithm." In: IEEE Trans. Pattern Analysis and Machine Intelligence]], vol. 20, no. 11, pp. 1236-1253, Nov. (1998).
  • A.D.J. Cross, R.C. Wilson, and E.R. Hancock. (). “Inexact Graph Matching with Genetic Search." In: Pattern Recognition, vol. 30, no. 6, pp. 953-970, (1997).
  • B.D. Ripley, Pattern Recognition and Neural Networks. New York: Cambridge Univ. Press, (1996).
  • Arthur P. Dempster, N.M. Laird, and D.B. Rubin. (). “Maximum-Likelihood from Incomplete Data via the EM Algorithm." In: J. Royal Statistical Soc. Series B, vol. 39, pp. 1-38, 1977.
  • M.A. Eshera and K.S. Fu. (). “An Image Understanding System Using Attributed Symbolic Representation and Inexact Graph- Matching." In: J. Assoc. Computing Machinery, vol. 8, no. 5, pp. 604-618, (1986).
  • A.M. Finch, R.C. Wilson, and E.R. Hancock. (). “Softening Discrete Relaxation." In: Advances in Neural Information Processing Systems, M. Michael I. Jordan Mozer, and T. Petsche, eds., vol. 9, pp. 438-444, (1997).
  • A.M. Finch, R.C. Wilson, and E.R. Hancock. (). “An Energy Function and Continuous Edit Process for Graph Matching." In: Neural Computation, vol. 10, no. 7, pp. 1873-1894, (1998).
  • A.M. Finch, R.C. Wilson, and E.R. Hancock. (). “Symbolic Graph Matching with the EM Algorithm." In: Pattern Recognition, vol. 31, no. 11, pp. 1777-1790, (1998).
  • M. Fischler and R. Elschlager. (1973). “The Representation and Matching of Pictorical Structures." In: IEEE Trans. Computers, 22(1).
  • G.J. McLachlan and K.E. Basford, Mixture Models: Inference and Applications to Clustering. New York: Marcel Dekker, (1988).
  • S. Gold and A. Rangarajan. (). “A Graduated Assignment Algorithm for Graph Matching." In: IEEE Trans. Pattern Analysis and Machine Intelligence]], vol. 18, no. 4, pp. 377-388, Apr. (1996).
  • L. Herault, R. Horaud, F. Veillon, and J.J. Niez. (). “Symbolic Image Matching by Simulated Annealing." In: ProceedingsBritish Machine Vision Conf., pp. 319-324, (1990).
  • T. Hoffmann and J.M. Buhmann. (). “Pairwise Data Clustering with Deterministic Annealing." In: IEEE Trans. Pattern Analysis and Machine Intelligence]], vol. 19, no. 1, pp. 1-14, Jan. (1997).
  • R. Horaud and T. Skordas. (). “Stereo Correspondence through Feature Grouping and Maximal Cliques." In: IEEE Trans. Pattern Analysis and Machine Intelligence]], vol. 11, no. 11, pp. 1168-1180, Nov. (1989).
  • R. Horaud and H. Sossa. (). “Polyhedral Object Recognition by Indexing." In: Pattern Recognition, vol. 28, no. 12, pp. 1855-1870, (1995).
  • J. Hornegger and H. Niemann. (). “Statistical Learning, Localization, and Identification of Objects." In: ProceedingsInt'l Conference Computer Vision, pp. 914-919, (1995).
  • B. Luo, A.D.J. Cross, and E.R. Hancock. (). “Corner Detection via Topographic Analysis of Vector Potential." In: Pattern Recognition Letters, vol. 20, pp. 635-650, (1999).
  • S. Moss and E.R. Hancock. (). “Registering Incomplete Radar Images with the EM Algorithm." In: Image and Vision Computing, vol. 15, pp. 637-648, (1997).
  • M. Pelillo, K. Siddiqi, and S. W. Zucker. (). “Matching Hierarchical Structures Using Association Graphs." In: IEEE Trans. Pattern Analysis and Machine Intelligence]], vol. 21, no. 11, pp. 1105-1120, Nov. (1999).
  • M. Pellilo. (). “Replicator Equations, Maximal Cliques, and Graph Isomorphism." In: Neural Computation, vol. 11, no. 8, pp. 1933-1955, (1999).
  • C. Peterson and B Soderberg. (). “A New Method for Mapping Optimisation Problems." In: Int'l J. Neural Systems, vol. 1, pp. 2-33, (1989).
  • A. Rangarajan, S. Gold, and E. Mjolsness. (). “A Novel Optimizing Network Architecture with Applications." In: Neural Computation, vol. 8, pp. 1041-1060, (1996).
  • A. Sanfeliu and K. S. Fu. (1983). “A Distance Measure between Attributed Relational Graphs for Pattern Recognition." In: IEEE Trans. Systems, Man, and Cybernetics, 13(3).
  • G.L. Scott and H.C. Longuet-Higgins. (). “An Algorithm for Associating the Features of 2 Images." In: ProceedingsRoyal Soc. London Series B, vol. 244, no. 1309, pp. 21-26, (1991).
  • K. Sengupta and K.L. Boyer. (). “Modelbase Partitioning Using Property Matrix Spectra." In: Computer Vision and Image Understanding, vol. 70, no. 2, pp. 177-196, (1998).
  • L.G. Shapiro and R.M. Haralick. (1985). “A Metric for Comparing Relational Descriptions." In: IEEE Trans. Pattern Analysis and Machine Intelligence]], 7(1).
  • L.S. Shapiro and J.M. Brady. (). “Feature-based CorrespondenceÐAn Eigenvector Approach." In: Image and Vision Computing, vol. 10, pp. 283-288, (1992).
  • A. Shokoufandeh, S.J. Dickinson, K. Siddiqi, and S.W. Zucker. (). “Indexing Using a Spectral Encoding of Topological Structure." In: ProceedingsIEEE Conference Computer Vision and Pattern Recognition, pp. 491- 497, (1999).
  • P.D. Simic. (). “Constrained Nets for Graph Matching and other Quadratic Assignment Problems." In: Neural Computation, vol. 3, pp. 268-281, (1991).
  • P.N. Suganthan, E.K. Teoh, and D.P. Mital. (). “Pattern-Recognition by Graph Matching Using the Potts MFT Neural Networks." In: Pattern Recognition, vol. 28, no. 7, pp. 997-1009, (1995).
  • S. Tirthapura, D. Sharvit, P. Klein, and B.B. Kimia. (). “Indexing Based on Edit-Distance Matching of Shape Graphs." In: Multimedia Storage and Archiving Systems III, vol. 3527, pp. 25-36, (1998).
  • J.R. Ullman. (). “An Algorithm for Subgraph Isomorphism." In: J. ACM, vol. 23, no. 1, pp. 31-42, Jan. 1976.
  • S. Umeyama. (). “An Eigen Decomposition Approach to Weighted Graph Matching Problems." In: IEEE Trans. Pattern Analysis and Machine Intelligence]], vol. 10, pp. 695-703, (1988).
  • J. Utans. (). “Mixture Models and EM Algorithms for Object Recognition within Compositional Hierarchies." In: ICSI Berkeley Technical Report TR-93-004, (1993).
  • W.M. Wells. (). “Map Model Matching." In: IEEE Conference Computer Vision and Pattern Recognition, pp. 486-492, (1991).
  • M.L. Williams, R.C. Wilson, and E.R. Hancock. (). “Deterministic Search for Relational Graph Matching." In: Pattern Recognition, vol. 32, no. 7, pp. 1255-1271, (1999).
  • R.C. Wilson and E.R. Hancock. (). “Structural Matching by Discrete Relaxation." In: IEEE Pattern Analysis and Machine Intelligence]], vol. 19, no. 6, pp. 634-648, June (1997).
  • A.K.C. Wong and M. You. (). “Entropy and Distance of Random Graphs with Application to Structural Pattern Recognition." In: IEEE Trans. Pattern Analysis and Machine Intelligence]], vol. 7, no. 5, pp. 509-609, Sept. (1985).
  • A.L. Yuille and J.J. Kosowsky. (). “Statistical Physics Algorithms that Converge." In: Neural Computation, vol. 6, pp. 341-356, (1994).
  • A.L. Yuille, P. Stolorz, and J. Utans. (). “Statistical Physics, Mixtures of Distributions, and the EM Algorithm." In: Neural Computation, vol. 6, pp. 334-340, 1994.,


 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
2001 StructuralGraphMatchingUsingEMandSVDBin Luo
Edwin R. Hancock
Structural Graph Matching Using the EM Algorithm and Singular Value DecompositionIEEE Transactions on Pattern Analysis and Machine Intelligencehttp://www.aprs.org.au/accv2002/accv2002 proceedings/Luo75.pdf10.1109/34.9546022001