Graphs are more potential data structures useful for object representation in structural pattern recognition. Hence, they widely used in various domains such as computer vision and pattern recognition. Pattern Recognition and Image Processing techniques are suitable for character analysis and character recognition problems. In pattern^{ }
In the literature, various approaches have been proposed for graph matching problems. Most graph matching algorithms are based on the maximum common subgraph problem, and it is a nondeterministic polynomialtime complexity problem^{ }
From the above, it is very clear that the methods that appear to be simple are not efficient, and on the other hand, the methods that appear to be efficient are not robust. As a result, we attempted to design an efficient algorithmic model that measures the degree of similarity in the length of edit operations. This focused to combines exact graph matching and inexact graph matching techniques. The exact graph matching technique classifies characters by considering the number of vertices and edges as features to classify. Inexact graph matching measures the degree of similarity in the length of edit operations using an algorithmic model.
Furthermore, the proposed model can always compute, if not optimal, at least nearoptimal edit sequences. The edit distance between two graphs is estimated by constructing maximal spanning trees of graphs. Dynamic programming is used to create the proposed model, and edit distance is calculated by comparing binary tree preorder sequences. Furthermore, this work extends to classify English, Digits, and Kannada characters. English alphabets (26 capital letters and 26 small letters), digits (10 characters), and Conjunct – Consonants (35 characters), a subset of the Kannada character set chosen for the case study. The concept of agglomerative singlelink hierarchical clustering is used to classify bilingual characters. The proposed algorithmic model is sound enough at the first and second level of classifications to cluster all mutually isomorphic graphs (characters – based on the number of vertices and edges) as members of the same class and nonisomorphic graphs, as members of other classes. In the third level of classification, the maximal spanning tree and its corresponding tree traversal string template are considered to be the key to classifying/recognizing further. Extensive experimentation is conducted, and it is observed that the obtained results are encouraging.
Key contributions of this paper are listed as follows,
• A hybrid approach for converting a large class classification problem into a small class classification problem that takes advantage of both exact and inexact graph matching techniques.
• An algorithmic model is designed to represent each character as a unique string.
• Uses dynamic programming in the right places to get the optimal tree.
• Converting the graph matching problem to a string matching problem reduces the time complexity of the problem.
In this model, graphs are initially represented by an adjacency matrix, and then corresponding maximal spanning trees^{ }
In this model, graphs are represented in adjacency matrices, and then graphs are transformed into maximal spanning trees^{ }
This section introduces an algorithmic model based on the dynamic programming concept. This algorithmic model converts maximal spanning trees into general trees. The root of the general tree is the vertex having the highest degree in the graph. If there are many vertices of the same highest degree, the dynamic programming concept obtains the node whose subtree is of the highest depth. This vertex is selected to be the root of the general tree. The vertex with the next highest degree will be the leftmost child of the general tree. If there are many vertices with the same highest degree, we recommend considering the vertex as the leftmost child of the general tree with the highest degree child. Repeat the process for all the nodes of the spanning tree.
This conversion of the spanning tree to the general tree may result in more general trees corresponding to the maximal spanning tree. If such is the case, the general tree with the highest depth is selected to proceed further using the dynamic programming concept. Note that we will not generate all but only the desired one through dynamic programming.
Transformation of binary trees into full binary trees and Computation of edit distance: Tree Traversal Approach: Conversion of the general tree into its equivalent binary tree is a 11 correspondence relationship. Also, the preorder traversals of binary trees are a 11correspondence with general trees. Thus the general tree is converted into its equivalent binary tree. This algorithmic model uses the forest traversal technique to obtain equivalent binary trees. After obtaining binary trees, the root of binary trees has always only left a subtree. Therefore dummy nodes (denoted by d) are introduced in the empty place of the left subtree of the root of the binary tree, and introducing dummy nodes to the right part of the binary trees is avoided. Thus binary trees become full binary trees.
Using the tree traversal technique, we obtained a preorder traversal sequence of full binary trees to compute edit distance. During the comparison of the preorder sequences of the binary trees, the count of edit operations increases if the first preorder sequence entry is a numerical value and the second preorder sequence is "d" (empty place) or vice versa. The number of numerical values of the first preorder sequence corresponding to "d" values of the second preorder sequence will give the total number of deletions while transforming the first tree into the second tree. The number of "d" values of the first preorder sequence corresponding to numerical values of the second preorder sequence will give the total number of insertions while transforming the first tree into the second tree.
Input graphs are in
The preorder sequence of the full binary tree / graph (G1) shown in
3 3 2 1 1 1 d 1 . . . . . . . . . . (array 1)
3 2 2 1 d 2 1 1 . . . . . . . . . . (array 2)
The 5^{th} and 7^{th} entries in array 1 have numerical and "d" values, and the corresponding entries in array 2 have "d" values and numerical values, respectively. It implies that the deletion of one node from and addition of one node into the first tree will transform it into the second tree. Thus, two edit operations are required to transform the graph G1 to G2. Therefore edit distance is 2. This model is efficient enough to obtain the nearoptimal edit sequence if not the actual edit distance without considering all possible spanning trees. Unlike the approach based on adjacency relationships which can be employed only on small size graphs, the model proposed in this topic can even be used to obtain edit distance for graphs of larger size
The suitability of the proposed edit distance approach for classifying English, Digits, and Kannada alphabets in general, conjunct consonants, a subset of Kannada alphabets in particular, was investigated.
Each character represents a graph (equivalent full binary tree), and the corresponding preorder sequence is stored in the database. The characters are clustered based on the edit distance obtained for these preorder sequences. The proposed algorithm groups the closest matched characters with the shortest edit distance into a single cluster if no similar characters are found.
We have considered 52 English characters, 10 digits, and 35 Kannada conjunct consonants of a single style for experimentation. A smoothing algorithm^{ }
Next, thinning algorithm^{ }
Observation is that the proposed model is sound enough to cluster all mutually isomorphic graphs together or members of the same class and nonisomorphic graphs as deferent classes.




C0 
(15), (27), (51) 
 
 
C1 
(35) 
 
 
C2 
(3), (4), (9), (10), (19), (21) (33), (34), (36), (39), (48), (55) 
C21 
(3), (9), (10), (19), (21), (39), (48), (55) 
C22 
(4), (33), (36) 

C3 
(12), (16), (17), (22), (28), (29), (30), (34), (37), (41), (43), (45), (46), (58) 
C31 
(45), (46) 
C32 
(12), (22), (28), (29), (30), (34), (58) 

C33 
(16), (17), (37), (41), (43) 

C4 
(2), (7), (14), (20), (25), (26), (32), (38), (40), (44), (50), (52), (53), (54), (57), (61), (62) 
C43 
(7), (14), (20), (25), (26), (32), (44), (50), (54), (57), (61), (62) 
C44 
(38), (40), (52), (53) 

C45 
(2) 

C5 
(1), (6), (13), (18), (23), (24), (31), (42), (56), (59), (60) 
C54 
(6), (13), (23), (24), (42), (56), (59), (60) 
C55 
(1), (18), (31) 

C6 
(5), (8), (11), (47), (49) 
 
 
equivalent tree traversal of full binary tree/string representation
The proximity matrix in




(3) 
0 
2 
6 
(43) 
 
0 
4 
(60) 
 
 
0 
The loss function defined for our model is good enough to recognize characters by considering the weight of the deleted edges during the conversion of the graph into the spanningtree process as one of the features. This function helps in recognizing characters when string representations of two different characters are the same. String representation of the graph index (16) and (19) are the same, and hence graph edit distance between them is zero. In this case, only classification is successful, but recognition fails in some cases. Therefore, the loss function plays a major role in successfully recognizing character by considering the deleted edge's weight. Refer
Loss function (L_{f}) = L_{we’ }+ L_{we}
Where L_{we'} is the sum of the all deleted edges weight during graph to spanning tree conversion and L_{we }is the sum of the weight of all edges of the spanning tree. The recognition rate for bilingual characters is as shown in



Neural Network^{ } 
Haar 
96.61 
Radial Basis Function^{ } 
Haar 
95.66 
Back Propagation Network^{ } 
Haar 
95.10 
Neural Network^{ } 
Discrete Cosine Transform 
96.79 
Radial Basis Function^{ } 
Discrete Cosine Transform 
95.48 
Back Propagation Network^{ } 
Discrete Cosine Transform 
93.78 
Proposed Algorithmic Method 
Graph features 
97.01 
In this study, an algorithmic model is designed to classify and recognize bilingual text. It is a hybrid technique. Initially, it applies the exact graph matching technique to simply classification, and then later inexact graph matching finally loss function is used to recognize text accurately. Proposed hybrid approach converts large class classification problem into a small class classification problem that takes advantage of both exact and inexact graph matching techniques. The inexact graph matching method determines the edit distance between graphs represented in terms of binary trees. The proposed system uses forest traversal and tree traversal techniques to compute edit distance in string matching of traversal sequences. The application of the proposed model to classify bilingual text that is English and Kannada conjunct consonants are explored, and the proposed model is smart enough to find the correct clusters as well as accurate Recognition. The benefit of this algorithmic model is that it allows the user to search for a desired character/graph in a database that contains string representations of the character/graph. It uses dynamic programming in the right places to get the optimal tree. This represents each character as a unique string. As a result, this model becomes general and adaptable framework for searching similar graphs (characters) and it can be extended to recognize any language text. Finally this algorithmic model represents each character as a unique string. Converting the graph matching problem to a string matching problem reduces the time complexity of the problem.