2001 StructuralGraphMatchingUsingEMandSVD

• (Luo & Hancock, 2001) ⇒ Bin Luo, and Edwin R. Hancock. (2001). “Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition.” In: IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(10). doi:10.1109/34.954602

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

Notes

• It presents an algorithm for Inexact Graph Matching.
• It uses only Graph Structure information.
• It show how Point-Sets of different sizes can be matched using Singular Value Decomposition.
• It can handle Graph Structure Noise by using the EM Algorithm.
• It cast the problem into Matrix Operation and solves it using Singular Value Decomposition.
• It is a Journal Paper of a their Conference Paper at ICPR 2000.

Cited By

• ~226 http://scholar.google.com/scholar?q=%22Structural+Graph+Matching+Using+the+EM+Algorithm+and+Singular+Value+Decomposition%22+2001

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.

---

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2001 StructuralGraphMatchingUsingEMandSVD	Bin Luo Edwin R. Hancock			Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition		IEEE Transactions on Pattern Analysis and Machine Intelligence	http://www.aprs.org.au/accv2002/accv2002 proceedings/Luo75.pdf	10.1109/34.954602		2001