Histogram of Oriented Gradients Based Off-Line Handwritten Devanagari Characters Recognition Using SVM, K-NN and NN Classifiers

In modern communication utilization of electronic files is common and most favored of information sharing. This electronic document saves human efforts and time of rewriting. It is also called as soft copy which is electronic copy of some type of data. It is easy and secure way of storing and sharing documents. But still many applications like mail sorting, digital signature verification, postal cards [1], government documents, historical data processing [2] require handwritten documents to be processed. Consequently, the necessity of having automated tool to recognize handwritten documents accurately is required. Recognizing the printed documents by a computer (referred as OCR) and recognizing the handwritten documents (referred as HCR) are two major groupings of character recognition (CR) process. HCR again divided into two types: online HCR and offline HCR. In Online HCR technique input images are accepted using pen tablet called as digitizer. While writing character using pen tablet its online information is captured such as x, y coordinates, pressure and stroke information etc. In offline HCR method input images are collected by optical scanning of the paper using scanner and converting it into computer format. Due to many reasons listed below it is very difficult to recognize handwritten characters: i) low distraction due to noise while collecting the OCR data compared to HCR, ii) In OCR variation is only limited to selected font type and size whereas in HCR the variation is result of individual’s style of writing, iii) Individual’s personal situation also causes variation in handwriting style making HCR further complex, iv) Shape similarity and v) complex variation in writing due to number of combinations of different characters like Matras and composite letters.

Generally, recognition of character is classified into two classes: OCR and HCR. In the category of OCR has achieved relatively good performance and now researchers are focusing on HCR systems. While Chinese and English are top two written languages in the world, Hindi stands third widely spoken and written language [3]. Likewise, explore on Devanagari script has attracted ample interest because of its great market potential. Bristow et al. [4] showed that HOG features can be reformulated as affine weighting on the margin of SVM classifier to its quadratic kernel and achieved great success. In paper [5], authors state comparative study on Arabic text using SVM and NN machine learning algorithms. They collected data from news articles for training and testing and reveal that SVM performing better. In paper [6] author used different types of moments as features to recognize online as well as offline Devanagari characters. Here classification is done using NN. Different moment feature combination is explored to improve recognition accuracy of Devanagari characters. Wan et al. [7] proposed hybrid approach (SVM+K-NN classifiers) for categorization of text. In this hybrid approach, training data points are reduced to support vectors using SVM for each class and for calculating distance between testing data to support vectors is done by using KNN. Experiment results of Kamble and Hegadi [8] reveal that proposed hybrid approach has minimum dependency on training parameters. Author explained rectangle HOG feature extraction method and they achieved great results on these features using SVM and NN classifiers. Effective indexing schemas on images based on texture based features are explained in the study of Minu et al. [9], which is used for dimensionality reduction purpose. The approach proposed by author required less computational time due to reduction happened in feature vector. Features extracted by HOG are so efficient to recognize not only Devanagari characters but also Malayalam [14], Bangla [15] and Kannada [16] popular scripts of India. Bannigidad et al. [16] presented the work which shows the importance of HOG feature descriptor to recognize different age-typed historical Kannada documents. Classification done by using two different classifiers K-NN and SVM. SVM achieved best accuracy than K-NN on HOG features. The main research work proposed by Nongmeikapam et al. [17] is to recognize all characters of Manipuri Meetei-Mayek using feed forward NN and SVM with HOG descriptor. Further, a comprehensive survey is done by Puri and Singh [18] along with the concept of Hindi handwritten as well as printed document classification using fuzzy logic and SVM. On-line Devanagari character recognition is presented by Deore and Pravin [19] using 1-D moment descriptor. They explored that in case of on-line character recognition system 1-D moment features are giving good accuracy on handwritten characters which are is not subjective to stroke sequence. Experiments are done by the author proved that 1-D moments can also be used to recognize character images which are not influenced by stroke information.

The study reveals that many researches have contributed significant work towards recognition of handwritten/ printed characters in spite of many challenges. The common challenges/problems encounter is difficulty in recognition of similar shape and compound characters, time, memory space and very important reliability. Where the numerical values are involved reliability is very important. They have explored many different feature extraction and classification methods where HOG descriptor giving very good performance in classification. HOG features having some unique features like they are stable with change in radiance and due to operating on local cells they are invariant to geometric and photometric transformations. Motivated by this particular work, our contributions toward research are:

• Presented a system to recognize Isolated Handwritten Devanagari Characters based on HOG features to minimize the challenges arising due to complexities discussed above.
• Analysis of recognition time and accuracy with different HOG cells. Experiments shows efficiency of the system improves as cell size increases.
• With SVM we also explored two more popular classifiers: K-NN and NN to evaluate effectiveness of HOG descriptor.

The flow of the paper is ordered as: Section 2 introduces features of Devanagari Scripts and its importance, Section 3 describes architecture of the proposed system with classifiers, experimental results are discussed in Section 4. Finally, Section 5 presents conclusion and perspective.

2.jpg

Figure 2. HDCRS architecture

3.2 Feature extraction: Histogram of oriented gradients

The HOG feature extraction technique uses the distribution of directions of gradients as features. Important feature like oriented gradients are extracted using HOG. Gradients of an image are beneficial because the magnitude of gradients is large around edges and corners because there only intensity changes suddenly. In our work, edges and corners information is considered as they specify shape of the image perfectly. Magnitude and direction of gradient is computed by Eq. (1).and Eq. (2). as shown below [11]:

$g=\sqrt{g x^{2}+g y^{2}}$                           (1)

$\theta=\arctan (g y / g x)$                            (2)

where, gx is change in the x-direction and gy is change in y- direction. Then total gradient magnitude g is calculated using Eq. (1). Magnitude is high when large change in intensity values specially around edges. Then the orientation θ is calculated. Now gradients and orientation used to calculate histrogram. Experiments are performed on dividing images into 2×2, 4×4 and 8×8 cells and then HOG is calculated on each cell. Figure 3 shows gradient directions and magnitude computed using 8×8 cells on specific patch of image.

3.jpg

Figure 3. (a) HOG features on one patch of the image. (b) Gradient Direction. (c) Gradient Magnitude

Next step is to calculate histogram of gradients. The histogram contain array of 9 bins related to angles and particular magnitude information will go to respective bin. Like these 324 feature vectors are computed on 32×32 image using 8×8 cell.

3.3 Classification

In classification phase three classifiers SVM, K-NN and NN are implemented to comprehend effect of HOG features. This section presents brief theory of SVM, K-NN and NN classifiers

3.3.1 SVM classifier

Support Vector Machine (SVM) classifier is mainly defined by the presence of a separating hyperplane. That is, given a labelled set of training data the algorithm outputs an optimal hyper plane which classifies the new examples. Hyperplane basically divides data into two classes. The main aim is to discover a plane which having maximum margin. Margin distance maximization gives some support so that new data classified with more certainty. Linear classification is very easy but for non-linear classification different kernel functions are used to map the given input data into higher dimensional space so that separation can be easily possible using lines. A non-linear curve makes data separation so difficult. Support vector machine is extremely preferred by several as it gives significant accuracy with minimum computation power. Mainly SVM comes under binary classification category and also can be used for multiclass classification. Several binary SVMs are required implementing for multiclass problem. Two approaches are useful: One-vs-rest and one-vs-one SVM. The proposed framework utilizes K (K – 1)/2 binary SVM models utilizing the one vs one methodology, where k is number of class labels.

3.3.2 K-NN classifier

K-NN is one of the simplest classifiers uses distance measure to classify the class of new data. In training phase feature vectors divided into number of regions and then according to the similarity present between them are combined to specific region. For similarity calculation distance measure is used. Basically it works well on small data set. K-NN algorithm locates k closest training vector irrespective of labels as shown in Figure 4. When new data Xi is given for classification algorithm it locates for k closest neighbors form new data point using distance function here in example k is 3. Then voting will happened and new data is classified accordingly in testing phase. For our experiment k value is selected as 3 and Euclidean distance function for performing experiment. The Euclidean distance function is stated below:

$d(x, y)=\sqrt{\sum_{i=1}^{n}\left(x_{i}-y_{i}\right)^{2}}$                     (3)

where, x is the feature vector of the input data, y stands for training dataset samples and n denotes the size of the feature vector [12].

4.jpg

Figure 4. 2-D Feature vectors with 3-NN classifier

3.3.3 NN classifier

Multilayer feedforward neural network is designed using backpropagation method. It comprises 3 layers as input, one hidden and output layers which usage gradient descent to reduce the squared error between observed output and target output. Initially assign small random weights to the network. Propagate input forward through the network. Calculate output for each unit using predefined weights. For each output unit calculate error which is propagated back through the network and weights are updated accordingly. The objective is to minimize these errors and improve efficiency. Network parameters like hidden layer neurons, its activation function and training function can be different and chosen for the optimal functioning of the network. Designated parameters for the proposed system are given in Table 1.

Table 1. Neural network parameters of HDCRS