A simpli ed feature vector obtained by wavelets method for fast and accurate recognition of handwritten characters o -line

Abstract

This paper presents an algorithm for simpli ed features extraction based on a wavelet method for o -line recognition of handwritten character. The proposal is applied to a set of 3250 handwritten symbols, which include the digits and the upper and lowercase character of English alphabet. The e ectiveness of our algorithm is tested by comparison against the descriptors FKI and Wavelets using the Nearest Neighbour rule as classi er. The classi cation is measured in percentage of overall Accuracy and the processing time obtained by each methods.

Introduction

The study of character recognition is divided into o -line and on-line methods mainly [ 1 ]. The di erence between them lies on how handwriting is done and analyzed. For the o -line recognition, the data are taken to be a static representation of text, since it can not be establish the order on which they were produced by a machine or handwritten [ 2 ]. On the other hand, in the on-line recognition, the original data are glyphs and points, which are normally storage on regular intervals of time [ 3 ].

This paper is focused on the o -line recognition of handwritten characters. The study is based on descriptors such as FKI [ 4 ] and discrete wavelets [ 5 ]. The dataset used in this work have been generated by [ 6 ] which includes digits and characters (0 9, A-Z, a-z). Our proposal was compared with the descriptors FKI and the discrete wavelet, in accuracy and processing time terms using the Nearest Neighbour rule 1-NN as classi er. 1.1

The FKI o ine features

The FKI algorithm was proposed by [ 4 ] which obtain a set of geometric features that has been used in handwriting recognition. That is, given a binary image ? Corresponding author S(x; y) of size M N , the method computes nine geometrical features ci where i 2 f1; :::; 9g for each entry column x such that 1 x M . This is done on each column of the image, thus the method obtain 9N features in total. The authors also have features such as number of black and white pixels and their transitions, centre of gravity and second order moments. 1.2

Wavelets Descriptors

The wavelets are transformations which decompose an image into multi-resolution descriptions localized in space and frequency domain providing a smaller frames of the images. The frequency domain analyse di erent variations that has been successfully used in many image processing applications [ 7 ].

The DWT decompose the image S into wavelet blocks, an average image of smaller size than the original for a factor of two, and three more images containing the gradients and contours of itself, according to the following de nitions: Wg(j; m; n) = p Whi (j; m; n) = p 1 1 M N x=0 y=0 M N x=0 y=0

M 1 N 1 X X S(x; y)gjimn(x; y) M 1 N 1 X X S(x; y)hijmn(x; y) (1) (2) where g is g(x) = 1 x 2 [0; 21 ] and h belongs to the Daubechies family of 1 x 2 [ 12 ; 1] mother wavelets; where as before i 2 fH; V; Dg. The wavelet blocks will be denoted by Aj = Wg(j; m; n), Hj = WhH (j; m; n), Vj = WhV (j; m; n) and Dj = WhD(j; m; n) where j is an index that indicates level of decomposition of the image (see Figure 1 (b)).

Frequency domain analysis is the background of representation of the feature vector. Di erent textural and statistical values are also computed which enrich the feature vector, like mean ( ) and standard deviation ( ) [ 5 ]. The type of entropies in the reference, which we have also implemented for comparison to our proposal, are like shannon, Log energy, threshold, sure and norm, which are computed on approximation the Aj coe cient block, as illustrated in Figure 1 (a). 2

Our Proposal

The main objective of the proposal method is to obtain an strategy which combine feature extraction methods in handwritten characters o -line and the recognition process of these characters in an accurate way. For that, segmentation and binarization methods were used before the actual feature extraction. 2.1

Binarization and segmentation

A pre-processing to the image is applied before feature extraction in order to eliminating noise of the image. In this way, rstly the images are converted into a binary type by analysing their histogram in a gray scale, in order to determine the optimal cut threshold. On a second stage, the symbol image is segmented extracting pixels corresponding to the symbol only. Finally, the symbol image are resized to a xed size of 120 120. The size has been xed in order to get optimal results when the wavelet transform is applied. 2.2

Feature extraction by a simpli ed vector feature using wavelets method

Feature extraction in the context of image processing, speci cally in handwriting character recognition, is based on two types [ 8 ]; structured and statistical methods. The rst one, are derived from the probability distributions of pixels, e.g. zones, rst and second moments, projection and direction histograms. The second one, are based on topological and geometrical properties of the object under study.

The Wavelet transformation is used to compress an image by transforming it into the frequency domain [ 9 ]. In order to accomplish this, the image are represented using a set of basic functions produced by translation and scale up of a mother function. Let S(x; y) be an input image, where x; y represent indexes, whereas S(x; y) is the pixel value. In this paper, a 2D wavelet transform is used, the scaling of S(x; y) is given by the functions g and h.

Coe cients wavelet analysis are obtained from three blocks; it was observed that wavelet coe cient of the third block are features of the input image, that is, it maintains representative information of the symbol. The wavelet transformation for the third state generate four images of size 15 15, A2, H2, V2 and D2 with 17 features correspondlly. The information from the approximation coe cients A2 in third block keeps the information of the input image and the other four coe cients obtained represent 12% of the original image size and 25% of the size of the A0 coe cient.

S(x; y) g[x] h[x] along x along x #2 gjmn(x; y) #2 hjmn(x; y) (a) g[y] h[y] g[y] h[y] along y along y along y along y #2 Aj AV22DH22 H1 #2 Vj #2 Dj #2 Hj

V1 D1

V0 (b)

H0 D0

For each coe cient obtained, were calculated the median, entropy and standard deviation; additionally ve entropy wavelets are also calculated: Shannon, Log energy, Threshold, sure and norm; with this in mind we are reducing an amount of 77% the statistical measures as compared with the original method.

The Algorithm 1 represent the feature extraction of the vector formed by 21 features proposed for this study.

Algorithm 1 Simpli ed vector feature using Wavelet method Require: Gray scale input image Ensure: Set of 21 features 1: Convert image to binary type 2: Apply the wavelet transform to obtain the coe cients of the third block A2, H2,

V2, D2 thus obtainig four features. 3: Calculate the mean ( ), standard deviation ( ), entropy (E) thus giving 12 features 4: Calculate the entropies shannon, Log energy, threshold, sure, norm from A2 thus generating ve features at this stage. 5: Repeat steps 1 to 4, for each symbol image in order to form its feature vector. 3 3.1

Tools and Methods

Data set

The results here reported correspond to the experiments over the data set generated by [ 6 ], which includes digits 0 9 with 10 classes and 527 feature vectors, the uppercase characters A Z form 26 classes and 1402 feature vectors, the lowercase characters a z with 26 classes and 1321 feature vectors.

For the data, the 10-fold cross-validation method was employed to estimate the classi cation error: 80% of the available patterns were for training purposes and 20% for the test set. On the other hand, we use as base classi er the 1-NN rule, expressed as [ 10 ]:

vu e E (V1; V2) = utX(V1[j] j=1

V2[j])2 (3) Where E is the euclidean distance between vectors V1 test feature and V2 training feature . 3.2

The con guration of the method

The experiments were carried out datasets with di erent dimension of the feature vector, depending on the method used. That is: { The FKI method, obtain nine features by column that containing the image, therefore the feature vector will have nine features by the number of columns that containing the image. { Wavelts method obtain 55 features. The vector dimension is computed by the matrix of A0, which generates ( x2 ) ( y2 ) features, where, x and y are the original image size, plus 54 features which represent the statistical averages. { The Simpli ed vector features using Wavelet method obtain a vector with 21 features. That is, the whole of the features is ( x8 ) ( y8 ) plus 17 features which represent the statistical averages. 4

Results and Discussion

In this paper, we study two descriptor methods: FKI and Wavelets, in comparison with our wavelets method for recognition of handwritten characters o -line, in Accuracy and processing time terms. The Accuracy is obtained as follow:

Classes (c)

In order to identify the statistic signi cance between the methods, the Table 1, shows the average accuracy for each dataset, bold values represent the best results. For that, the rank of each method was calculated as follows [ 11 ]: For each dataset, the method with the best accuracy receives rank 1, and the worst receives rank 3. If there is a tie, the ranks are shared. Thus the overall rank of a method is the averaged rank of this method across the data set used. The results shown that the highest rank is obtained by the Wavelet method and the method with lowest rank is the FKI method.

To complete the analysis of statistical signi cance between the results, the Namenyi test is used [ 11 ] DC = q q K(6KN+1) , where q is critical value, K is the number of methods to compare and N is the number of training set used. The test obtains a critical di erence (CD) to reject the assumptions on which the corresponding p value is less than the adjusted . In this paper we compare three feature selection methods and analyse their behaviour on three di erent datasets; the corresponding value for qa are: q0:05 is 2.343 and for q0:10 is 2.052. The critical di erence for q0:5 is 1.913 and for q0:10 is 1.675.

To interpret the results it is stated that a particular method A is signi cantly di erent than B, if the overall rank (A) + CD < rank(B). From results in Table 1 it is posible to identify that the behaviour of our method and the Wavelets method do not o er statistic di erence, that is to say that it is competitive with the Wavelets methdo. However, comparing the resulst respect to the FKI method, the Wavelets method is signi catively better (1:3 (Wavelets Rank) +1:675(CD0:10) < 3 (FKI Rank)). 4.2

Processing time

Conclusions and future work

In this paper we propose a method for reducing the feature vector for handwriting recognition in comparison to the results reported by [ 5 ], in which method obtain a vector with 55 features. Our method obtain a feature vector of 21 features only, using the third moment of the wavelet transformation. This allow us to reduce processing time compared to the FKI and traditional wavelet methods. That means, our algorithm reduces the processing time from 74.65% to 16.51% and decrease in size vector from 74.87% to 15% respect to FKI and Wavelet method respectively.

The future work will be focus on the processing of the dataset generated through a simpli ed vector feature using Wavelet method. We are in search to improve accuracy of the classi er by using the multilayer perceptron.

Acknowledgment. This work has partially been supported by the SEPPRODEP-3238 and 3834/2014/CIA Mexican Projects and by the Mexican Science and Technology Council (CONACYT-Mexico) through the Masters scholarship 702528.

References

1. Fotini Simistira , Vassilis Katsouros, and George Carayannis . Recognition of online handwritten mathematical formulas using probabilistic fSVMsg and stochastic context free grammars . Pattern Recognition Letters , 53 : 85 { 92 , 2015 .

2. Ernesto Tapia . A survey on recognition of on-line handwritten mathematical notation . In Technical Report B-07-01 . Freie Universitat Berlin, Germany, 2007 .

3. Ernesto Tapia . Understanding mathematics: A system for the recognition of online handwritten mathematical expressions . PhD thesis , Freie Universitat Berlin, Germany, 2005 .

4. F. Alvaro , J. A. Sanchez , and J. M. Bened . O ine features for classifying handwritten math symbols with recurrent neural networks . In Pattern Recognition (ICPR) , 2014 22nd International Conference on, pages 2944 { 2949 , Aug 2014 .

5. Sk Md Obaidullah , Chayan Halder, Nibaran Das , and Kaushik Roy . Numeral script identi cation from handwritten document images . Procedia Computer Science , 54 : 585 { 594 , 2015 .

6. Teo lo Em dio de Campos, Bodla Rakesh Babu, and Manik Varma . Character Recognition in Natural Images . Proceedings of the International Conference on Computer Vision Theory and Applications , Lisbon, Portugal, February 273 { 280 , 2009 .

7. K. B. Raja , S. Sindhu , T. D. Mahalakshmi , S. Akshatha , B. K. Nithin , M. Sarvajith , K. R. Venugopal , and L. M. Patnaik . Robust image adaptive steganography using integer wavelets . In Communication Systems Software and Middleware and Workshops , 2008 . COMSWARE 2008 . 3rd International Conference on, pages 614 { 621 , Jan 2008 .

8. Hedieh Sajedi . Handwriting recognition of digits, signs, and numerical strings in Persian . Computers & Electrical Engineering , 49 : 52 { 65 , 2016 .

9. R Colom , Rafael Gadea , A Sebastia , Marcos Mart nez , Vicente Herrero, and Vicente Arnau . Transformada Discreta Wavelet 2-D para procesamiento de video en tiempo real . Actas de las XII Jornadas de Paralelismo, 2010 .

10. Cristina Garc a Cambronero and Irene Gomez Moreno . Algoritmos de aprendizaje: knn & kmeans. Intelgenc a en Redes de Comunicacion , 2006 .

11. Janez Demsar . Statistical comparisons of classi ers over multiple data sets . The Journal of Machine Learning Research , 7 :1{ 30 , 2006 .