Pattern recognition is a task of searching particular patterns or features in the given input. The data mining, computer networks, genetic engineering, chemical structure analysis, web services etc. are few rapidly growing applications where pattern recognition has been used. Graphs are very powerful model applied in various areas of computer science and engineering. This paper proposes a graph based algorithm for performing the graphical symbol recognition. In the proposed approach, a graph based filtering prior to the matching is performed which significantly reduces the computational complexity. The proposed algorithm is evaluated using a large number of input drawings and the simulation results show that the proposed algorithm outperforms the existing algorithms.
References
[1]
Ullman, J.R. (1976) An Algorithm for Subgraph Isomorphism, Journal of ACM, 23, 31-42. https://doi.org/10.1145/321921.321925
[2]
Fernandez, M.L. and Valiente, G. (2001) A Graph Distance Metric Combining Maximum Common Subgraph and Minimum Common Supergraph. Pattern Recognition Letters, 22, 753-758. https://doi.org/10.1016/S0167-8655(01)00017-4
[3]
Raymond, J.W. and Willett, P. (2002) Maximum Common Subgraph Isomorphism Algorithms for the Matching of Chemical Structures. Journal of Computer-Aided Molecular Design, 16, 521-533. https://doi.org/10.1023/A:1021271615909
[4]
Messmer, B. and Bunke, H. (1998) A New Algorithm for Error-Tolerant Subgraph Isomorphism Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20, 493-505. https://doi.org/10.1109/34.682179
[5]
Conte, D., Foggia, P., Sansone, C. and Vento, M. (2004) Thirty Years of Graph Matching in Pattern Recognition. International Journal of Pattern Recognition and Artificial Intelligence, 18, 265-298. https://doi.org/10.1142/S0218001404003228
[6]
Cordella, L.P., Foggia, P., Sansone, C. and Vento, M. (2004) Subgraph Isomorphism Algorithm for Matching Large Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26, 1367-1372.
[7]
Llados, J., Marti, E. and Villanueva, J.J. (2001) Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23, 1137-1143. https://doi.org/10.1109/34.954603
[8]
Sanchez, G., Llados, J. and Tombre, K. (2002) An Error Correction Graph Grammar to Recognize Textured Symbols. In: Blostein, D. and Kwon, Y.B., Eds., Graphics Recognition Algorithms and Applications, Springer, Berlin, Heidelberg, 128-138.
[9]
Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York.
[10]
Cook, S.A. (1971) The Complexity of Theorem-Proving Procedures. Proceeding of 3rd ACM Symposium on Theory of Computing, Shaker Heights, 3-5 May 1971, 151-158. https://doi.org/10.1145/800157.805047
[11]
Luks, E.M. (1980) Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time. 21st Annual Symposium on Foundations of Computer Science, Syracuse, 13-15 October 1980, 42-49.
[12]
Datta, S., Limaye, N., Nimbhorkar, P., Thierauf, T. and Wagner, F. (2009) Planar Graph Isomorphism Is in Log-Space. 24th Annual IEEE Conference on Computational Complexity, Paris, 15-18 July 2009, 203-214. https://doi.org/10.1109/CCC.2009.16
[13]
Foggia, P., Sansone, C. and Vento, M. (2001) A Performance Comparison of Five Algorithms for Graph Isomorphism. Proceeding of the 3rd IAPR Workshop on Graph Based Representations in Pattern Recognition, 23 May 2001, 188-199,
[14]
Bunke, H. (1999) Error Correcting Graph Matching: On the Influence of the Underlying Cost Function. IEEE Transactions on Pattern Analysis and Machine Learning, 21, 917-922.
[15]
Joyner, I. and Holder, L.B. (2001) Graph-Based Hierarchical Conceptual Clustering. Journal of Machine Learning Research, 2, 19-43.
[16]
Irniger, C. and Bunke, H. (2005) Decision Trees for Error-Tolerant Graph Database Filtering. 5th IAPR International Workshop, Vol. 3434, Poitiers, 11-13 April 2005, 301-311.
[17]
Sengupta, K. and Boyer, K. (1995) Organizing Large Structural Model Bases. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17, 321-332. https://doi.org/10.1109/34.385984
[18]
Shapiro, L. and Haralick, R. (1982) Organization of Relational Models for Scene Analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3, 595-602. https://doi.org/10.1109/TPAMI.1982.4767312
[19]
Sossa, H. and Horaud, R. (1992) Model Indexing: The Graph-Hashing Approach. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Champaign, 15-18 June 1992, 811-814.
[20]
Messmer, B. and Bunke, H. (1999) A Decision Tree Approach to Graph and Subgraph Isomorphism. Pattern Recognition, 32, 1979-1998. https://doi.org/10.1016/S0031-3203(98)90142-X
[21]
Riesen, K. and Bunke, H. (2009) Dissimilarity Based Vector Space Embedding of Graphs Using Prototype Reduction Schemes. Proceedings of the 6th International Conference on Machine Learning and Data Mining in Pattern Recognition, Leipzig, 23-25 July 2009, 617-631.
[22]
Irniger, C. and Bunke, H. (2003) Theoretical Analysis and Experimental Comparison of Graph Matching Algorithms for Database Filtering. Proceedings of 4th IAPR International Workshop on Graph Based Representations in Pattern Recognition, Vol. 2726, 30 June-2 July 2003, 118-129. https://doi.org/10.1007/3-540-45028-9_11
[23]
Legaspe, E.P., Silva, W.S., Fontana, C.F. and Dias, E.M. (2011) Automatic Character Recognition Based on Graph Theory: A New Approach to Automation. The Proceedings of the 2nd International Conference on Circuits, Systems, Communications and Computers, Puerto De La Cruz, 71-79.
[24]
Li, M.J. and Dai, R.W. (1995) A Personal Handwritten Chinese Character Recognition Algorithm Based on the Generalized Hough Transform. The Proceedings of the 3rd International Conference on Document Analysis and Recognition, Vol. 2, Montreal, 14-16 August 1995, 828-831.
[25]
Gao, X., Xiao, B., Tao, D. and Li, X. (2010) A Survey of Graph Edit Distance. Pattern Analysis and Applications, 13, 113-129.
