Feature Selection for Character Recognition of Handwritten Devanagari and Odia Scripts

Handwritten character recognition has been a challenging task and it finds uses in many real time scenarios such as language translation, automatic Braille transliteration, automatic cheque book reading, automatic scanning of handwritten forms etc. This paper takes two Indian scripts namely Devanagari and Odia for handwritten character recognition and compares different gradient based features such as LBP, LDP, HOG and LOOP which can be used for learning the character pattern by a support vector classifier on various parameters. The paper uses two existing databases of handwritten Devanagari and Odia characters to train the support vector classifiers and compares the results of various features selection. It proposes the best possible feature for Devanagari and Odia character recognition based on graphical comparisons of parameters such as accuracy, training time and recognition rate. The maximum accuracy achieved on the Devanagari dataset of 92000 characters is 95.65% and the maximum accuracy achieved on the relatively small Odia dataset of 15400 characters is approximately 99%. The paper further investigates for the Devanagari characters getting misclassified more frequently.


INTRODUCTION
Handwritten character recognition has been a topic of research for many years now, but the problem is still open because of huge variation in writing style from one person to another. Further, Indian scripts are complicated in comparison to western scripts as the number of characters and modifiers are much more. In past few years, several works have been done for character recognition of various Indian scripts. Particularly the availability of strong database has increased the accuracy to an industry applicable level. While, the highest accuracies have been reported with the use of Deep Neural Networks, Support vector machines have comparable accuracies on character recognitions. Support vector machines have their own advantages of traditional neural networks. SVMs have simple geometrical representation and give sparse solution, further the independence of computation complexity on dimensionality of input space gives advantage to SVMs. SVM's drives on the idea of creating a hyperplane between classes to classify the test data. SVMs are less prone to overfitting. SVM training always finds a global minimum [Burgess 1988] whereas ANNs can suffer from the problem of multiple local minima.
It is essential to choose the optimum feature to train SVMs to get better results. The character recognition is a classification problem where it is important to evaluate the number of times the input characters are getting recognized correctly. It is not required to calculate how many a times a character is getting predicted as true class wrongly or how many times a character is not getting recognized when it is the true class. So, Accuracy of the classifier is more important than its sensitivity and specificity. Further it is observed that gradient based features work well with text recognitions. In this paper two good existing databases in Odia and Hindi have been used for comparing the different gradient based features. The present work first discusses the researches been done for character recognition of Hindi and Odia scripts, then describes the features which are used to train SVM and then compares the results on chosen databases based on heuristically selected parameters to select the best performing feature on both the Hindi and Odia characters.

RELATED WORKS
Character recognition is done in three steps: Database selection (creation), feature selection and classifier selection. A database must be unbiased, must have been gathered from multiple sources and should be large. In last decade, several databases of handwritten Hindi and Odia scripts have [1][2][3][4][5][6][7] been created by taking required measures to create a workable database. Earlier researchers used to work and validate their work on self-made databases which were quite small, and it was difficult to compare results from various researchers. Further it has been observed [8][9] that SVM and ANN are the two most successful classifiers for image analysis, in this case character recognition. Both the techniques have their advantages and disadvantages. ANN has higher shown higher accuracy at the cost of computation complexity and hardware implementation complexity. SVM shows comparable accuracy but requires good features which can represent the images to be classifier in a better manner. This paper has focused on selecting features which can be used to train an SVM without compromising on accuracy and cost of implementation. Features are a set of numbers that take the salient characteristics of the segmented image. Different classifier may work differently with a set of features [10]. Feature Selection is one of the most prime topics for character recognition. After choosing the right dataset and classifier for classification, features must be selected based on their performance on the chosen set of database and classifier.  [8] has reviewed character recognition techniques for different languages in India and he observed that feature extraction technique is the most important step for character recognition. S. Singh et al. [17] have surveyed extensively about the existing works in the field of Odia character recognition and observed that researchers have used features likeZernike moments [18], genetic algorithm [19], DCT and DWT [20][21], Standard deviation and zone centroid average distance-based feature matrix [22], a feature extracted using LU factorization [23][24], geometric features like centroid, shadow-based features and distance-based features [25], PCA [26] and rectangular HOG [27]. Through various research reviews it has been observed that HOG with SVM have been successful with character recognition on a larger dataset. However, texture-based features like local binary pattern, local derivative pattern etc. have not been tested much for character recognition, especially on Indian scripts. Some of the very recent works [28][29][30][31] have emphasized on the use of such features because they tend to reduce the computational cost. So, the present work compares the two texture-based features LBP and its variant LOOP with the proven feature HOG by finding out these features on two largest datasets of Devanagari and Odia and applying them to a support vector classifier individually. The results are compared based on three parameters: accuracy, training time and recognition rate.

DESCRIPTION OF FEATURES
The character recognition problem has seen huge amount of research in recent past. Most of the image recognition problems have observed that gradient based features render the best information of images for training a classifier. Rather than representing the image by using true pixel values, features try to map the information in terms of local changes in the pattern. Character recognition is a in integral though a small part of text recognition which involves, line segmentation, word segmentation, character segmentation, recognition of modifiers and normalization of text after recognition of constituents. Therefore, it is essential to consider the recognition rate as one of the important parameters for selection of a feature. Another important parameter is the complexity of the feature which effects the hardware implementation of algorithm developed for text recognition. Based on this criterion the present work has heuristically chosen Local binary pattern (LBP), Local directional pattern (LDP), Histogram of oriented gradients (HOG) and Local optimal-oriented pattern (LOOP) as features for training support vector classifiers. Another reason for selection these features is the proven utility of them in various texture-based segmentation of images. These features offer fast computation and compressed representation of images to even reduce the dimensionality of the input feature space. Other features like SIFT and SURF have been proven good results for finding out key points in scene images but they are relatively computationally complex and application of such features to find key points in very small images like that of characters is very unlikely. Another parameter of comparison of features considered in this work is the training time. SVM is a classifier which does not take in to account all the inputs, its choses some of the inputs which are likely to be misclassified and calls them support vectors. Apart from the size of the feature vector, the training time may also be affected by the correlation of the features. So, the three parameters chosen for feature evaluation are the accuracy, the recognition rate and the training time.

Local Binary Pattern
LBP features [32] [35] are computationally very less costly as compared to other features. To find out LBP features for an image, the image is divided into grids of equal size and for each grid features are evaluated independently and finally they are vertically concatenated to form the feature vector for the image. LBP is of two types: circular and non-circular. To calculate the circular LBP feature vector for a single grid, neighborhood of each pixel is decided by making a circle about it and placing the predefined number of neighborhood locations N at equal angles starting at zero degree with horizontal axis as shown in Figure 1. If the neighborhood location falls in between pixels, then its pixel value is found out using interpolation of the surrounding pixels. In a noncircular LBP, simple N-neighborhood is considered to find the first order derivative in N-directions. Now considering the center pixel with pixel value P as the threshold, if any pixel at selected neighborhood location has value Q < P, then its value is replaced by zero otherwise by one. After assigning binary values, pixel values are accumulated sequentially leaving the center pixel giving a N bit value. This N bit value is converted to decimal and it is assigned to the center pixel. The order in which it is collected is not specified, but process must be same for all the pixels. After assigning a new value to each pixel in the grid, A histogram is calculated for each grid which represents the feature vector of the grid.

Fig. 1: Neighborhood of pixel for different radii [38]
It is observed that practically a smaller number of binary patterns are repeated, and they are divided into two categories: Uniform binary patterns and Non-uniform binary patterns [33]. When 0-1 or 1-0 transitions are at max two in a binary pattern than it is termed as uniform binary pattern. There are 58 such codes for 8 neighborhoods. So, while binning each uniform code is given a separate bin whereas all the nonuniform patterns are kept in a single bin effectively giving only 59 bins for the case of 8 neighborhood.

Local Directional Pattern and Local Optimal-Oriented Pattern
If a non-circular LBP is thought of as a collection of filter bank it can be seen an application of 8 directional Sobel operator on the pixel surrounding as shown in Figure 2.

Fig. 2:
Calculating LBP using filter bank [36] Local directional pattern or LDP [32] is another local pattern which uses Kirsch derivatives in place of Sobel operators for finding directional derivatives. This has shown to be less susceptible to noise as compared to LBP. Unlike LBP where the center pixel value is considered as threshold, threshold selection in LDP is empirical. Suppose N directional derivatives Mi where i= 0,1,2,….7 are found using the Kirsch masks, then the k th highest value where k<N, is chosen as threshold and i th location pixel value is replaced as 1 if Mi >= Mk otherwise the i th pixel value is replaced by 0. So, in an N bit pattern obtained like this, always k number of bits are 1, this limits the number of possibilities of patterns. After assigning binary values to the neighboring pixels, the new values are assigned in similar manner as it is done in LBP.
Local optimal oriented pattern or LOOP [36] proposed in 2018 is an amalgamation of LBP and LDP which tries to overcome the drawbacks of LBP while retaining their utility. Like LDP the directional derivatives in LOOP are calculated using Kirsch masks, but like LBP, weights are assigned to each binary position according to the rank of the directional derivatives. If N neighborhood is considered, the position having highest directional derivative is given a weightage of 2 N-1 and weights reduce by half for successively ranked directional derivative position. Assignment of binary values is done by assuming the center pixel as threshold value like LBP.

Histogram of Oriented gradients
HOG [34], like LBP is more than two-decade old feature used extensively in feature extraction of images for classification purposes. The gradients store the information of the shape very well and when these features are used with learning algorithms like SVM, the observed accuracy is remarkable. For finding HOG features of a block of image, gradient of the image block at every pixel is found. For every block, a fixed number of bins are made between 0 to 180 degrees and bins of a particular range of angles are filled by the magnitude (or proportion) of the gradients in that range.

RESULT ANALYSIS
The comparison of features is done based on three heuristically chosen parameters: accuracy, training time and recognition rate. Initial observations showed that LBP alone does not provide good accuracy as shown later. So, the texture-based feature alone does not work well for character recognition. It is also observed during literature survey that texture-based features work much better for object recognitions when they are combined with HOG feature. Adding to that, LOOP is modified LDP, therefore the three features for which comparisons are shown, are LBP, HOG and LOOP followed by HOG. For every feature, SVMs are trained for both the strong dataset taken into consideration and the results are compared.
The most important parameter of evaluating a character recognizer is its accuracy. It can be observed from table2 and table3 that HOG has outperformed the other features by having 95.54% and 98.33% accuracies for Hindi and Odia databases, respectively. While LBP has performed worst, LOOP with HOG has considerable improvement over LBP in overall accuracy with 83.61% and 87.83% for Hindi and Odia databases, respectively. In terms of recognition rate also, HOG features are slightly better than LOOP with HOG.    Some writer's character_21_pa may be close with some other writer's character_25_ma. So, along with HOG features of the characters if some region properties are also used for training the classifier, slightly more accuracy can be expected.

CONCLUSIONS
This research work has studied the previous works in character recognition of Hindi and Odia scripts. It choses SVM classifier for character recognition and heuristically selects three features for making a character recognizer keeping in mind the hardware implement ability. It achieved the accuracies of close to 82, 96 & 84 percent respectively for LBP, HOG and LOOP features used in Hindi character classification. It achieved the accuracies of close to 62, 98 & 88 percent respectively for LBP, HOG and LOOP features used in Odia character classification. It than showed that for both the scripts, HOG outperforms the other features in terms of accuracy which is the most desirable aspect for a character recognizer. Further it analyzed the reason of misclassification in case of Hindi classifier with HOG features and reasoned the misclassification to the closeness in the representation of one character written by one person to another character written by another person.
The work then suggested that if some region properties of the characters is also used along with the HOG features of the classifier then accuracy can be slightly improved.