Classification and Recognition of Bilingual Text Using Graph Edit Distance Based Degree of Similarity

M J Roopa; K Mahantesh

doi:10.17485/IJST/v15i27.2405

Article

Classification and Recognition of Bilingual Text Using Graph Edit Distance Based Degree of Similarity

VIEWS 1221
PDF 227

Indian Journal of Science and Technology

DOI: 10.17485/IJST/v15i27.2405

Year: 2022, Volume: 15, Issue: 27, Pages: 1336-1343

Original Article

Classification and Recognition of Bilingual Text Using Graph Edit Distance Based Degree of Similarity

M J Roopa^1*, K Mahantesh²

¹Department of Computer Science and Engineering, SJB Institute of Technology, Bangalore-
560060, Karnataka, India
²Department of Electronics and Communication Engineering, SJB Institute of Technology,
Bangalore-560060, Karnataka, India

*Corresponding Author
Email: [email protected]

Received Date:23 December 2021, Accepted Date:22 February 2022, Published Date:14 July 2022

This work is licensed under a Creative Commons Attribution 4.0 International License.

Abstract

Objectives: Graph Edit distance-based classification and recognition method is introduced in this study for bilingual characters. Specifically, this method aims to classify characters first and then recognize them in the 2nd level. Methods: This study combines both exact graph matching and inexact graph matching techniques to achieve better Recognition. The exact graph matching technique classifies characters by considering the number of vertices and edges as features to classify. Inexact graph matching uses an algorithmic model to measure the degree of similarity in the length of edit operations. Findings: The proposed model can compute, if not optimal, sequences all the time, at least near-optimal edit sequence. The proposed model is based on dynamic programming. Edit distance is estimated by comparing preorder sequences of the respective binary trees. Finally, this model uses the loss function to recognize text accurately. To bring out the practicality of the proposed model, we present a case study on the classification of English alphabets and Kannada conjunct consonants. Novelty: (i) A hybrid approach for converting a large class classification problem into a small classification problem that takes advantage of both exact and inexact graph matching techniques. (ii) An algorithmic model is designed to represent each character as a unique string. (iii) Uses dynamic programming in the right places to get the optimal tree, and (iv) to convert the graph matching problem to a string matching problem reduces the time complexity of the problem.

Keywords: Bilingual text; Character Recognition; Degree of Similarity; Graph Edit Distance; Graph Matching

References

Adel D, Ibrahim C, Saïd Y. Efficient approximate approach for graph edit distance problem. Pattern Recognition Letters (IF3.756). 2021;151:310–316. Available from: https://doi.org/10.1007/s10618-020-00733-5
Ma G, Ahmed NK, Willke TL, Yu PS. Deep graph similarity learning: a survey. Data Mining and Knowledge Discovery. 2021;35(3):688–725. Available from: https://doi.org/10.1109/ACCESS.2020.2993191
Osman AH, Barukub OM. Graph-Based Text Representation and Matching: A Review of the State of the Art and Future Challenges. IEEE Access. 2020;8:87562–87583. Available from: https://doi.org/10.1109/ACCESS.2020.2993191
Ok S. A graph similarity for deep learning. Advances in Neural Information Processing Systems, 2020-December(NeurIPS. 2020. Available from: https:// papers.nips.cc/paper/2020/file/0004d0b59e19461ff126e3a08a814c33-Paper.pdf
Raveaux R. On the unification of the graph edit distance and graph matching problems. Pattern Recognition Letters. 2021;145:240–246. Available from: https://doi.org/10.1016/j.patrec.2021.02.014
Serratosa F. Redefining the Graph Edit Distance. SN Computer Science. 2021;2(6):1–8. Available from: https://doi.org/10.1007/s42979-021-00792-5
Rica E, Álvarez S, Serratosa F. Ligand-Based Virtual Screening Based on the Graph Edit Distance. International Journal of Molecular Sciences. 2021;22(23):12751. Available from: https://doi.org/10.3390/ijms222312751
Marcelli A, Quer S, Squillero G. The Maximum Common Subgraph problem: A portfolio approach. 2019. Available from: https://arxiv.org/pdf/1908.06418.pdf
Harsh P, Purvi P. Study and Analysis of Decision Tree Based Classification Algorithms. International Journal of Computer Sciences and Engineering. 2018;6(10):74–78. Available from: https://doi.org/10.26438/ijcse/v6i10.7478
Chawhan RB, Rao MR. Graph Based Printed Kannada Character Recognition System By Using Backpropagation Neural Network. 2020;11:418–424.
Jiang Z, Wang T, Yan J. Unifying Offline and Online Multi-Graph Matching via Finding Shortest Paths on Supergraph. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2021;43(10):3648–3663. Available from: https://doi.org/10.1109/TPAMI.2020.2989928
Kumar V, Ramakrishnan B, AG. Machine recognition of printed Kannada text. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics. 2002;p. 37–48. Available from: https://doi.org/10.1007/3-540-45869-7_4
Hazra A, Choudhary P, Inunganbi S, Adhikari M. Bangla-Meitei Mayek scripts handwritten character recognition using Convolutional Neural Network. Applied Intelligence. 2021;51(4):2291–2311. Available from: https://doi.org/10.1007/s10489-020-01901-2
Chen Z, Xie Z, Yan J, Zheng Y, Yang X. Layered Neighborhood Expansion for Incremental Multiple Graph Matching. Computer Vision – ECCV 2020. 2020;p. 251–267. Available from: https://doi.org/10.1007/978-3-030-58607-2_15
Bhagwat G, Kumari S, Patekar V, Deaconu AM. Novel Static Multi-Layer Forest Approach and Its Applications. Mathematics. 2021;9(21):2650. Available from: https://doi.org/10.3390/math9212650
Sheikh IA, Shahid I. Minimum Spanning Tree Algorithms and and Techniques. 2018. Available from: http://www.ijciras.com/PublishedPaper/IJCIRAS1101.pdf
Sann SS, Win SS, Thant ZM. An analysis of various Image Pre-Processing techniques in Butterfly Image. International Journal of Advance Research. 2021;6(1).
Dey R, Balabantaray RC, Mohanty S. Sliding window based off-line handwritten text recognition using edit distance. Multimedia Tools and Applications. 2021. Available from: https://doi.org/10.1007/s11042-021-10988-9

Copyright

© 2022 Roopa & Mahantesh. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Published By Indian Society for Education and Environment (iSee)