| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition
October 2001 (vol. 23 no. 10)
pp. 1120-1136
—This paper describes an efficient algorithm for inexact graph matching. The method is purely structural, that is to say, it uses only the edge or connectivity structure of the graph and does not draw on node or edge attributes. We make two contributions. 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. Our second contribution is to cast the recovery of correspondence matches between the graph nodes in a matrix framework. This allows us to efficiently recover correspondence matches using 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.
[1] A.P. Ambler, H.G. Barrow, C.M. Brown, R.M. Burstall, and R.J. Popplestone, “A Versatile Computer-Controlled Assembly System,” Proc. Third Int'l Conf. Artifical Intelligence, pp. 298-307, 1973.
[2] H.G. Barrow and R.J. Popplestone, “Relational Descriptions in Picture Processing,” Machine Intelligence, vol. 5, pp. 377-396, 1971.
[3] R.E. Blake, Development of an Incremental Graph Matching Device, vol. 30, of NATO ASI series, pp. 355-366. Berlin: Spinger-Verlag, 1987.
[4] K.L. Boyer and A.C. Kak,“Structural stereopsis in 3D vision,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 10, no. 2, pp. 144-166, 1988.
[5] J.S. Bridle, “Training Stochastic Model Recognition Algorithms as Networks Can Lead to Mutual Information Estimation of Parameters,” Advances in Neural Information Processing Systems, D.S. Touretzky, ed., vol. 2, pp. 211-217, 1990.
[6] H. Bunke, “Error Correcting Graph Matching: On the Influence of the Underlying Cost Function,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 21, no. 9, pp. 917-922, Sept. 1999.
[7] H. Bunke and G. Allermann, “Inexact Graph Matching for Structural Pattern Recognition,” Pattern Recognition Letters, vol. 1, pp. 245-253, 1983.
[8] H. Bunke and B.T. Messmer, “Recent Advances in Graph Matching,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, pp. 169-203, 1997.
[9] H. Bunke and K. Shearer, “A Graph-Distance Metric Based on the Maximal Common Subgraph,” Pattern Recognition Letters, vol. 19, nos. 3-4, pp. 255-259, 1998.
[10] C.M. Bishop, Neural Networks for Pattern Recognition. Clarendon Press, 1995.
[11] W.J. Christmas, J. Kittler, and M. Petrou, “Structural Matching in Computer Vision Using Probabilistic Relaxation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 8, pp. 749–764, Aug. 1995.
[12] F.R.K. Chung, Spectral Graph Theory, Am. Math. Soc., ed., CBMS Series 92. 1997,
[13] A.D.J. Cross and E.R. Hancock, Graph Matching with Dual Step Em Algorithm IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, pp. 1236-1253, 1998.
[14] A.D.J. Cross, R.C. Wilson, and E.R. Hancock, “Inexact Graph Matching with Genetic Search,” Pattern Recognition, vol. 30, no. 6, pp. 953-970, 1997.
[15] B.D. Ripley, Pattern Recognition and Neural Networks. New York: Cambridge Univ. Press, 1996.
[16] A.P. Dempster, N.M. Laird, and D.B. Rubin, “Maximum-Likelihood from Incomplete Data via the EM Algorithm,” J. Royal Statistical Soc. Series B, vol. 39, pp. 1-38, 1977.
[17] M.A. Eshera and K.S. Fu, "An Image Understanding System Using Attributed Symbolic Representation and Inexact Graph-Matching," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, pp. 604-619, Sept. 1986.
[18] A.M. Finch, R.C. Wilson, and E.R. Hancock, “Softening Discrete Relaxation,” Advances in Neural Information Processing Systems, M. Jordan, M. Mozer, and T. Petsche, eds., vol. 9, pp. 438-444, 1997.
[19] A.M. Finch, R.C. Wilson, and E.R. Hancock, “An Energy Function and Continuous Edit Process for Graph Matching,” Neural Computation, vol. 10, no. 7, pp. 1873-1894, 1998.
[20] A.M. Finch, R.C. Wilson, and E.R. Hancock, “Symbolic Graph Matching with the EM Algorithm,” Pattern Recognition, vol. 31, no. 11, pp. 1777-1790, 1998.
[21] M. Fischler and R. Elschlager, “The Representation and Matching of Pictorical Structures,” IEEE Trans. Computers, vol. 22, no. 1, pp. 67-92, Jan. 1973.
[22] G.J. McLachlan and K.E. Basford, Mixture Models: Inference and Applications to Clustering. New York: Marcel Dekker, 1988.
[23] S. Gold and A. Rangarajan, “A Graduated Assignment Algorithm for Graph Matching,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 4, pp. 377-388, Apr. 1996.
[24] L. Herault, R. Horaud, F. Veillon, and J.J. Niez, “Symbolic Image Matching by Simulated Annealing,” Proc. British Machine Vision Conf., pp. 319-324, 1990.
[25] T. Hofmann and M. Buhmann, Pairwise Data Clustering by Deterministic Annealing IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 1, pp. 1-14, Jan. 1997.
[26] R. Horaud and T. Skordas, “Stereo Correspondence Through Feature Grouping and Maximal Cliques,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, pp. 1,168-1,180, 1989.
[27] R. Horaud and H. Sossa, “Polyhedral Object Recognition by Indexing,” Pattern Recognition, vol. 28, no. 12, pp. 1855-1870, 1995.
[28] J. Hornegger and H. Niemann, “Statistical Learning, Localization, and Identification of Objects,” Proc. Int'l Conf. Computer Vision, pp. 914-919, 1995.
[29] B. Luo, A.D.J. Cross, and E.R. Hancock, Corner Detection via Topographic Analysis of Vector-Potential Pattern Recognition Letters, pp. 635-650, 1999.
[30] S. Moss and E.R. Hancock, “Registering Incomplete Radar Images with the EM Algorithm,” Image and Vision Computing, vol. 15, pp. 637-648, 1997.
[31] M. Pelillo, K. Siddiqi, and S.W. Zucker, “Matching Hierarchical Structures Using Association Graphs,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 21, no. 11, pp. 1105-1120, 1999.
[32] M. Pelillo, “Replicator Equations, Maximal Cliques, and Graph Isomorphism,” Neural Computation, vol. 11, no. 8, pp. 2023-2045, 1999.
[33] C. Peterson and B Soderberg, “A New Method for Mapping Optimisation Problems,” Int'l J. Neural Systems, vol. 1, pp. 2-33, 1989.
[34] A. Rangarajan, S. Gold, and E. Mjolsness, "A Novel Optimizing Network Architecture with Applications," Neural Computation, (in press), 1996.
[35] A. Sanfeliu and K. S. Fu, “A Distance Measure between Attributed Relational Graphs for Pattern Recognition,” IEEE Trans. Systems, Man, and Cybernetics, vol. 13, no. 3, pp. 353-362, May 1983.
[36] G.L. Scott and H.C. Longuet-Higgins, “An Algorithm for Associating the Features of 2 Images,” Proc. Royal Soc. London Series B, vol. 244, no. 1309, pp. 21-26, 1991.
[37] M. Renovell, P. Huc, and Y. Bertrand, "CMOS Bridging Fault Modelling," Proc. 12th IEEE VLSI Test Symp. (VTS 94), IEEE CS Press, Los Alamitos, Calif., 1994, pp. 392-397.
[38] L.G. Shapiro and R.M. Haralick, “A Metric for Comparing Relational Descriptions,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 7, no. 1, pp. 90-94, Jan. 1985.
[39] L.S. Shapiro and J.M. Brady, “Feature-Based Correspondence: An Eigenvector Approach,” Image and Vision Computing, vol. 10, pp. 283-288, 1992.
[40] A. Shokoufandeh, S.J. Dickinson, K. Siddiqi, and S.W. Zucker, “Indexing Using Spectral Encoding of Topological Structure,” Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, June 1999.
[41] P.D. Simic, "Constrained Nets for Graph Matching and Other Quadratic Assignment Problems," Neural Computation, vol. 3, pp. 268-281, 1991.
[42] P.N. Suganthan, E.K. Teoh, and D.P. Mital, “Pattern-Recognition by Graph Matching Using the Potts MFT Neural Networks,” Pattern Recognition, vol. 28, no. 7, pp. 997-1009, 1995.
[43] S. Tirthapura, D. Sharvit, P. Klein, and B.B. Kimia, “Indexing Based on Edit-Distance Matching of Shape Graphs,” Multimedia Storage and Archiving Systems III, vol. 3527, pp. 25-36, 1998.
[44] J.R. Ullman, “An Algorithm for Subgraph Isomorphism,” J. ACM, vol. 23, no. 1, Jan. 1976.
[45] S. Umeyama, “An Eigendecomposition Approach to Weighted Graph Matching Problems,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 10, no. 5, pp. 695-703, Sept. 1988.
[46] J. Utans, “Mixture Models and EM Algorithms for Object Recognition within Compositional Hierarchies,” ICSI Berkeley Technical Report TR-93-004, 1993.
[47] W.M. Wells,“MAP model matching,” Conf. Computer Vision and Pattern Recognition, pp. 486-492, 1991.
[48] M.L. Williams, R.C. Wilson, and E.R. Hancock, “Deterministic Search for Relational Graph Matching,” Pattern Recognition, vol. 32, no. 7, pp. 1255-1271, 1999.
[49] R.C. Wilson and E.R. Hancock, “Structural Matching by Discrete Relaxation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 6, pp. 634-648, June 1997.
[50] A.K.C. Wong and M. You, “Entropy and Distance of Random Graphs with Application to Structural Pattern Recognition,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 7, no. 5, pp. 509-609, Sept. 1985.
[51] A.L. Yuille and J.J. Kosowsky, “Statistical Physics Algorithms that Converge,” Neural Computation, vol. 6, pp. 341-356, 1994.
[52] A.L. Yuille, P. Stolorz, and J. Utans, "Statistical Physics, Mixtures of Distributions, and the EM Algorithm," Neural Computation, vol. 6, pp. 334-340, Mar. 1994.
Citation:
B. Luo, E.R. Hancock, "Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 10, pp. 1120-1136, Oct. 2001, doi:10.1109/34.954602
