| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs
October 2001 (vol. 23 no. 10)
pp. 1137-1143
—In this paper, we propose an error-tolerant subgraph isomorphism algorithm formulated in terms of Region Adjacency Graphs (RAG). A set of edit operations to transform one RAG into another one are defined. Regions are represented by polylines and string matching techniques are used to measure their similarity. The algorithm follows a branch and bound approach driven by the RAG edit operations. This formulation allows matching computing under distorted inputs and also reachong a solution in a near polynomial time. The algorithm has been used for recognizing symbols in hand drawn diagrams.
[1] 1137 C. Ah-Soon, “Analyse de Plans Architecturaux,” PhD thesis, Institut Nat'l Polytechnique de Lorraine, 1998.[2] H.A. Almohamad and S.O. Duffuaa, “A Linear Programming Approach for the Weighted Graph Matching Problem,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, no. 5, pp. 522-525, May 1993.[3] H.P. Amann and H. Hugli, “An Algorithm for the Inexact Matching of High Level 3D Polyhedric Representations,” Proc. SPIE Conf. Intelligent Robotic Systems, vol. 1609, pp. 134-140, Nov. 1991.[4] H. Bunke and B.T. Messmer, “Recent Advances in Graph Matching,” Int'l J. Pattern Recognition and Artificial Intelligence, vol. 11, no. 1, pp. 169-203, 1997.[5] 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.[6] A.D.J. Cross, R.C. Wilson, and E.R. Hancock, “Inexact Graph Matching Using Genetic Search,” Pattern Recognition, vol. 30, no. 6, pp. 953-970, 1997.[7] M.A. Eshera and K.S. Fu, “A Similarity Measure between Attributed Relational Graphs for Image Analysis,” Proc. Seventh Int'l Conf. Pattern Recognition, pp. 75-77, 1984.[8] A.M. Finch, R.C. Wilson, and E.R. Hancock, “Matching Delaunay Graphs,” Pattern Recognition, vol. 30, no. 1, pp. 123-140, 1997.[9] G.P. Ford and J. Zhang, “A Structural Graph Matching Approach to Image Understanding,” Proc. SPIE Conf. Intelligent Robots and Computer Vision X: Algorithms and Techniques, vol. 1607, pp. 559-569, 1991.[10] E. Gmür and H. Bunke, “3D Object Recognition Based on Subgraph Matching in Polynomial Time,” Structural Pattern Analysis, R. Mohr, T.H. Pavlidis, and A. Sanfeliu, eds., pp. 131-147, World Scientific, 1989.[11] 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.[12] A.H. Habacha, “Structural Recognition of Disturbed Symbols Using Discrete Relaxation,” Proc. First Int'l Conf. Document Analysis and Recognition, pp. 170-178, Sept.-Oct. 1991.[13] T.C. Henderson, Discrete Relaxation Techniques. Oxford Univ. Press, 1990.[14] 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.[15] X. Jiang, A. Münger, and H. Bunke, “Synthesis of Representative Graphical Symbols by Computing Generalized Median Graph,” Graphics Recognition: Recent Advances, A.K. Chhabra and D. Dori, eds. pp. 183-192, Springer-Verlag, 2000.[16] P. Kuner and B. Ueberreiter, “Pattern Recognition by Graph Matching: Combinatorial versus Continuous Optimization,” Int'l J. Pattern Recognition and Artificial Intelligence, vol. 2, no. 3, pp. 527-542, Sept. 1988.[17] S.W. Lee, J.H. Kim, and F.C.A. Groen, “Translation-, Rotation-, and Scale-Invariant Recognition of Hand-Drawn Symbols in Schematic Diagrams,” Int'l J. Pattern Recognition and Artificial Intelligence, vol. 4, no. 1, pp. 1-25, 1990.[18] J. Lladós, “Combining Graph Matching and Hough Transform for Hand-Drawn Graphical Document Analysis. Application to Architectural Drawings,” PhD thesis, Universitat Autònoma de Barcelona and Universitéde Paris 8, 1997.[19] M. Maes, “Polygonal Shape Recognition Using String-Matching Techniques,” Pattern Recognition, vol. 24, no. 5, pp. 433-440, 1991.[20] K. Mehlhorn, Graph Algorithms and NP-Completeness.Berlin: Springer-Verlag, 1984.[21] B.T. Messmer and H. Bunke, “A New Algorithm for Error-Tolerant Subgraph Isomorphism Detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 5, pp. 493-504, May 1998.[22] R. Mohr and T.C. Henderson, “Arc and Path Consistency Revisited,” Artificial Intelligence, vol. 28, pp. 225-233, 1986.[23] 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.[24] J. Rocha and T. Pavlidis, "A Shape Analysis Model With Applications to a Character Recognition System," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, pp. 393-404, 1994.[25] D.S. Seong, Y.K. Choi, H.S. Kim, and K.H. Park, “An Algorithm for Optimal Isomorphism between Two Random Graphs,” Pattern Recognition Letters, vol. 15, pp. 321-327, Apr. 1994.[26] L. Shapiro, “Relational Matching,” Handbook of Pattern Recognition and Image Processing: Computer Vision, T.Y. Young, ed., pp. 475-496, Academic Press, 1993.[27] H. Sossa and R. Horaud, Model Indexing: The Graph-Hashing Approach Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 811-815, 1992.[28] 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.[29] P.N. Suganthan, E.K. Teoh, and D.P. Mital, “Pattern Recognition by Homomorphic Graph Matching Using Hopfield Neural Networks,” Image and Vision Computing, vol. 13, no. 1, pp. 45-60, Feb. 1995.[30] K. Tombre, C. Ah-Soon, P. Dosch, G. Masini, and S. Tabonne, “Stable and Robust Vectorization: How to Make the Right Choices,” Graphics Recognition: Recent Advances, A.K. Chhabra and D. Dori, eds., pp. 3-18, 2000.[31] Y.T. Tsay and W.H. Tsai, “Model-Guided Attributed String Matching by Split-and-Merge for Shape Recognition,” Int'l J. Pattern Recognition and Artificial Intelligence, vol. 3, no. 2, pp. 159-179, 1989.[32] J.R. Ullman, “An Algorithm for Subgraph Isomorphism,” J. ACM, vol. 23, no. 1, Jan. 1976.[33] 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.[34] R.A. Wagner and M.J. Fischer, "The String-to-String Correction Problem," J. ACM, vol. 21, no. 1, pp. 168-78, 1974.[35] C. Wang and K. Abe, “Region Correspondence by Inexact Attributed Planar Graph Matching,” Proc. Fifth Int'l Conf. Computer Vision, pp. 440-447, June 1995.[36] J.T.L. Wang, K. Zhang, and G.W. Chirn, “The Approximate Graph Matching Problem,” Proc. 12th Int'l Conf. Pattern Recognition, pp. 284-288, Oct. 1994.[37] R.C. Wilson and E.R. Hancock, “A Bayesian Compatibility Model for Graph Matching,” Pattern Recognition Letters, vol. 17, pp. 263-276, 1996.[38] 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. 599-609, Sept. 1985.[39] E.K. Wong, “Model Matching in Robot Vision by Subgraph Isomorphism,” Pattern Recognition, vol. 25, no. 3, pp. 287-304, 1992.
Citation:
J. Lladós, E. Martí, J.J. Villanueva, "Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 10, pp. 1137-1143, Oct. 2001, doi:10.1109/34.954603
