Popular in Course
verified elite notetaker
Popular in Business
This 11 page Document was uploaded by an elite notetaker on Sunday December 20, 2015. The Document belongs to a course at a university taught by a professor in Fall. Since its upload, it has received 16 views.
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 12/20/15
International Journal of Computer Engineering and Technology (IJCET), ISSN 0976 – 6367(Print), ISSN 0976 – 6375(Online) Volume 3, Issue 1, January- June (2012), © IAEME & TECHNOLOGY (IJCET) ISSN 0976 – 6367(Print) ISSN 0976 – 6375(Online) IJCET Volume 3, Issue 1, January- June (2012), pp. 115-125 © IAEME: www.iaeme.com/ijcet.html © I A E M E Journal Impact Factor (2011): 1.0425 (Calculated by GISI) www.jifactor.com PERFORMANCE OF ON-LINE MALAYALAM HANDWRITTEN CHARACTER RECOGNITION USING HMM AND SFAM Primekumar K.P Cochin University of Science and Technology email@example.com Sumam Mary Idicula Cochin University of Science and Technology firstname.lastname@example.org ABSTRACT Nowadays HMM is most successfully used for the on-line recognition of handwriting characters. The disadvantages of existing systems using HMM are that it requires large training time and it does not support incremental learning. In order to overcome these difficulties we have chosen SFAM network, which requires very less training time and supports incremental learning. This paper presents the comparative performance of On-line Malayalam handwritten character recognitionsystem using Discrete HMM and SFAM. The input co-ordinates and the angle features are used to form the feature vector. The performance of the system for states varying from 3 to 11 is analyzed for HMM. For the system using SFAM the vigilance parameter is varied from 0.7 to 0.92. The system gives maximum accuracy of 95.24% for HMM and 97.81% for SFAM when tested on 1279 character samples. Time required for recognizing a symbol varies from 0.7 sec to 2.6 sec for HMM and about 0.5sec for SFAM. Also it is found that the memory requirement of SFAM is comparatively higher than that of HMM. Keywords — Online Handwriting recognition, Wavelet transform, HMM, Simplified Fuzzy ART MAP. I. INTRODUCTION Man machine interface has improved a lot with the advent of devices like PDAs. Using these devices we can interact with the machine in natural and comfortable way. It will be again a good advantage if we are utilizing these technologies to interact with the machine in the regional language. This will help many who know only the regional language to interact with the system. 115 International Journal of Computer Engineering and Technology (IJCET), ISSN 0976 – 6367(Print), ISSN 0976 – 6375(Online) Volume 3, Issue 1, January- June (2012), © IAEME Compared to western scripts, the character set of Malayalam script is so large that it is difficult to enter them using keyboard. Also for typing consonant conjuncts in Malayalam it is necessary to press two or more keys in the English keyboard. In order to overcome these difficulties,a systemwhich enablesto enter datain natural way is necessary. Even though there had been some effort for the offline recognition of Malayalam characters , a very little effort was there for the on-line recognition. There exist different methods for on-line handwriting recognition based on time and frequency domain features [3-6]. Here we have considered only time domain features. The problem with frequency domain features is that a small change in the time domain co-ordinate sequence in a small interval of time will affect entire frequency domain leading large inter class co-variance. In this paper the performance of the On-line Malayalam handwriting recognition system using Discrete HMM and SFAM classifier is analyzed. HMMs are basically sequence classifiers and are widely used for the recognition of handwritten characters . They are stochastic models and can cop with noise and other variations in handwriting. The disadvantage of HMM is that it takes much training time, especially at higher number of states, also recognition time increases with increase in number of states. Secondly they do not support incremental learning. In order to overcome these difficulties we have also chosen another neural network architecture called Simplified Fuzzy ARTMAP (SFAM), which takes very less trainingtime compared to other methods like HMM and back propagation. Also the time for recognizing a symbol is very less. Another advantage is that they support incremental learning. Since they are designed to overcome stability-plasticitydilemma,theycan incorporatenew symbols/characters without affecting the previously trained weights. These advantages make it ideal for practical implementation. The disadvantage of the system using SFAM is that it requires larger memory compared to those using HMM. The input to the system is a sequence of x-y co-ordinates corresponding to the pen trajectory. From the normalized co-ordinates, angle features direction and curvature at different points on the trajectory are calculated. Then for the system using HMM, vector quantization of the featuresis done and is given as the input of training / Recognition module. For the systemusing SFAM wavelet transform of the normalized x-y co-ordinates and the angle features is used to form the resultant feature vector, which is given to the input of SFAM network. The main stages in the proposed system are Data acquisition, Preprocessing, Feature extraction and Training and Recognition. This paper is arranged as seven sections. Section II deals with the Malayalam language, Section III deals with data acquisition and preprocessing Section IV shows different features extracted from the normalized data. Section V describes the training and recognition process using HMM and SFAM Section VI gives the detailed comparative performance analysis and results conclusion is given in section VII. Figure 1, 2 shows block diagram of the system using HMM and SFAM. Figure 1 Block Diagram of the system using HMM 116 International Journal of Computer Engineering and Technology (IJCET), ISSN 0976 – 6367(Print), ISSN 0976 – 6375(Online) Volume 3, Issue 1, January- June (2012), © IAEME Figure 2 Block Diagram of the system using SFAM II. M ALAYALAM SCRIPT Malayalam, the official language of the south Indian state Kerala, is one of the four major languages of the Dravidian family. Character types of Malayalam script consists of Independent vowels, Dependent vowel signs, Consonant letters, Consonant signs, Consonant conjuncts and Chillu. Independent vowels are signs that stand on their own. These are used to write syllables, which starts with a vowel. Dependent vowel signs occur only in combination with a base consisting of a sign for a single consonant or a consonant cluster .Each consonant letter representsa single consonant sound followed bythe inherent vowel /a/ thereby making an orthographic syllable. Consonant letters may also be rendered as half forms which go in to the constitution of consonant conjuncts. Consonant conjuncts are those which serve as orthographic abbreviations of two or more adjacentletter forms. To omit the inherent vowel in a consonant or consonant conjunct, a crescent mark namely ‘Chandrakkala’ is typed after it. Five signs representing pure consonants with out any inherent vowel are referred to as Chillu. The proposed system considers Independent vowels, consonants, Dependent vowel signs, Consonant signs and Chillu. In Figure 3 symbols (1-15) represent vowels, (16-51) represents consonants, (52-65) corresponds to dependent vowelsigns, (66-69) represents consonant signs and (70-75) are Chillu. Thus there are 64 different symbols and all of these symbols can be written in a single stroke except “x” which can be classified easily using rule base depending upon the relative position. Consonant conjuncts arenot considered here as this would make the system little more complex. 117 International Journal of Computer Engineering and Technology (IJCET), ISSN 0976 – 6367(Print), ISSN 0976 – 6375(Online) Volume 3, Issue 1, January- June (2012), © IAEME Figure 3 Malayalam Characters III. DATA ACQUISITION AND P REPROCESSING The handwritten data was acquired using I-balls ‘Take Note On-line’ . The data acquired by the hardware is a sequence of x-y co-ordinates at different time instances, which goes through different preprocessing steps before feature extraction. The main objective of preprocessing is to rectify the ambiguities present in the acquired data and normalize the character co-ordinates so as to make it suitable for feature extraction. The procedures used in pre-processing step are duplicate point elimination, smoothing, size normalization and equidistance re-sampling. Co-ordinates having the identical neighboring points are removed as these extra points do not contain any extra information. Smoothing is done in order to remove noise present in the acquired data. It is done by replacing the current point by the mean value of its neighboring points . Size normalization is done to remove the variations due to different size of writing. It is done by fitting the sample in to a fixed area such that the aspect ratio is not changed. For the system using HMM, sampling of the co-ordinates is done as in , and for 118 International Journal of Computer Engineering and Technology (IJCET), ISSN 0976 – 6367(Print), ISSN 0976 – 6375(Online) Volume 3, Issue 1, January- June (2012), © IAEME SFAM equidistance re-sampling is done so that the character is sampled in to 26 sample points. These normalized character co-ordinates are then used for feature extraction described in the next section. IV. F EATURE EXTRACTION In this stage a sequence of relevant featuresthat distinguish each character is extracted from the normalized character co-ordinates. Total of six time domain features are extracted. The first two consists of x-y co-ordinates itself. Then angular features, direction and curvature are extracted. Angular features are included because they are almost invariant to translation and scaling. The overall process is described below. Normalized x and y co-ordinate First two features consist of normalized values of x and y co-ordinates on the trajectory. Writing direction Local writing direction at a point x(t), y(t) is described using sine and cosine of the angle ‘α ’subtended by the line joining the preceding and succeeding points with the horizontal line . Figure 4 Writing direction From the above figure, ∆x(t) cos αt) = ∆x (t)+∆y (t) ∆y(t) sinα(t) = 2 2 ∆x (t)+∆y (t) where ∆x(t) = x(t +1)− x(t −1) and ∆y(t) = y(t +1)− y(t −1) Curvature Curvature or angular difference at a point x(t),y(t) may be represented using the sine and cosine of the angleκ‘’.It isthe angle bywhich the preceding directionvector is to be rotated in 119 International Journal of Computer Engineering and Technology (IJCET), ISSN 0976 – 6367(Print), ISSN 0976 – 6375(Online) Volume 3, Issue 1, January- June (2012), © IAEME counter clockwise direction so as to coincide with the succeeding direction vector. It is a measure of angular difference between the preceding and successive direction vectors as shown in Figure 5. ‘κ ’can be calculated as follows. Figure 5 Curvature From the above figure, −1 y(t)− y(t −2) θ1= tan x(t)− x(t −2) θ2 = tan −1y(t +2)− y(t) x(t +2)− x(t) if (θ1−θ 2 > 0, κ =360−(θ −θ1) 2 else κ = (θ 2θ )1 After extracting these six features, they are normalized to values between 0 and 1. These normalized features are given as the input of Training/ Recognition stage. V. T RAINING AND RECOGNITION Training and Recognition using HMM After feature extraction process, in the training phase, the features of the whole training dataset are clustered using K-means algorithm choosing Euclidian distance as the clusteringcriteria. Here 240 clusters are used andeach of the cluster centre is assigned a unique symbol. Then the feature vectors are converted to a sequence of symbols by assigning each of the temporal features, the symbol corresponding to the nearest cluster centre. Then these sequences of symbols are fed as input to Discrete HMM, in which the observations are discrete symbols  . Hidden Markov models are doubly stochastic process with an underlying stochastic process, corresponding to states that are hidden, but the state changes are observed through another set of stochastic process. It explores the relationships between consecutive observations of the pattern to be classified. The HMM is trained using Baum–Welch algorithm .Here we have used left-to-right HMM model. Thenumber of states used varies from 3 to 11 and the time taken for training is proportional to the number of states. Here 63 HMMs corresponding to 63 symbols were trained. In the recognition phase the feature vector is vector 120 International Journal of Computer Engineering and Technology (IJCET), ISSN 0976 – 6367(Print), ISSN 0976 – 6375(Online) Volume 3, Issue 1, January- June (2012), © IAEME quantized and is converted in to a sequence of symbols. Then the decoding of this sequence of symbols is done using Viterbi algorithm . We have used rule base depending upon the position and size to distinguish between the symbols “w”, “T” and “x” as they differ only by size. Training and Recognition using SFAM For the system using SFAM , wavelet transform of the features are extracted, which is given as the input of SFAM network. Wavelet transform is mainly done to compress the individual features extracted so that only relevant information in them is filtered out reducing the size of resultant feature vector. Wavelet transform represents the signals in terms of approximation and detailed coefficients . The representation of extracted features like x-y co-ordinates and angular features with respect to time are not complex such as that of speech as given in Figure 6. So simple wavelets, such as ‘haar’ is enough to represent these individual features with sufficient level of accuracy. We have used ‘db1’ and ‘haar’ wavelets for wavelet decomposition, as empirically these gives maximum accuracy, and their relative performance were analyzed. Third level wavelet decomposition is carried out on each of these individual features and only the approximation coefficients were used to form the resultant feature vector. The approximation coefficients were normalized between 0 and 1.Then these normalized values of approximation coefficients of these six feature vectors were concatenated to get 24 dimensional resultant feature vector, which was given to the Training and Recognition module. Figure 6 shows the approximation coefficients at various levels of decomposition using ‘haar’ wavelet for the x co-ordinates of the symbol ‘S’. Figure 6 Approximation Coefficients at various levels of decomposition using ‘haar’ wavelet for the ‘x’ co-ordinates of the symbol ‘S’ A self organizing neural network, known as Simplified Fuzzy ARTMAP (SFAM) is used for training and classification stage. ARTMAP is a class of network that can perform incremental learning . Fuzzy ARTMAP extends the ARTMAP by integrating fuzzy logic in to the system. A Simplified Fuzzy ARTMAP (SFAM) is a simplified version of the fuzzy ARTMAP neural network model . It was designed to improve the computational efficiency of the fuzzy ARTMAP model with a minimal loss of learning effectiveness. Figure 7 shows the architecture of SFAM network. 121 International Journal of Computer Engineering and Technology (IJCET), ISSN 0976 – 6367(Print), ISSN 0976 – 6375(Online) Volume 3, Issue 1, January- June (2012), © IAEME Figure 7 SFAM Network SFAM Network has three layers, namely input layer (F1 layer), Cluster layer (F2 layer), and Class layer (F3 layer).The class (category) layer merely holds the names of the categories that the network is expected to classify. The basic idea behind ART system is to learn only if resonates. Resonance occurs when the output in the first layer (F1) after feedback from the second layer (F2) matches the original pattern usedas input for the first layer in that processing cycle . To measure the degree of match, a parameter namely Vigilance parameter ρ ) is used in the learning phase of the network; its range is 0 to 1 and is used to control the granularity of the output nodes. In the training phase first the input vector is complement coded and is given to the input layer. The activation of the ‘j’th output node in the F2 layer is calculated using I ∧ w T I =) j , j α + w j Where, I = Compliment coded input vector th w j weight vector of ‘j’ output node α = Choice parameter The node havingmaximumvalue of T (j) is taken asthe winner. If category of the input belongs to that of winning node and the match factor M is greater than vigilance parameρer ( then the weighs are adjusted using the equation. w J(new= β I ∧w J(ol)+ 1−β w ) J(old) where, β = Learning rate parameter The match factor is computed using I ∧ w Match factor M = J I Once SFAM has been trained, a ‘feed-forward’ pass through the compliment-coder and the input layer classifies an unknown pattern. We haveused rule base depending upon the position 122 International Journal of Computer Engineering and Technology (IJCET), ISSN 0976 – 6367(Print), ISSN 0976 – 6375(Online) Volume 3, Issue 1, January- June (2012), © IAEME and size to distinguish between the symbols “w” and “T” and “x” as they differ only by size. The variation of Recognition rate for various values of vigilance parameters are shown in the Table 2. VI. P ERFORMANCE A NALYSIS The systems were trained using 2530 samples collected from 40 different users. The samples per class was approximately 40. The test set, a totally different set consisting of 1279 samples collected from of 20 different users other than the above mentioned, also consists of approximately 20 symbols per class. For HMM, we have analyzed the performance of the system for different number of states varying from 3 to 11. It gives a maximum accuracy of 95.24% when the number of states was 10, the corresponding memory requirement is 13kB, the time required for training is about six and half hours and the recognition time was about 2.25 seconds/symbol. When number of states used was three, training time is reduced to about one hour recognition time was reduced to about 0.7 seconds/symbol, but the accuracy was 92.88%. The memory requirement in case of HMM is proportional to the number of states used. Table1 shows Recognition Rate and memory requirement corresponding to different states. States Recognition Memory Rec Rate (%) Requirement Time (kB) (sec) 3 92.88 6.49 0.7 4 93.17 8.16 0.8 5 93.17 9.07 1.0 6 94.05 9.86 1.25 7 94.60 10.7 1.4 8 93..73 11.0 1.5 9 94.44 12.1 1.7 10 95.24 13.0 2.25 11 94.90 13.9 2.6 Table 1 Recognition Rate and memory requirement corresponding to different states. When SFAM is used in the recognition stage, the performance of the system using ‘db1’and ‘haar’ wavelets was analyzed . The system gives a maximum accuracy of 97.81% when ‘haar’ wavelet is used and when the vigilance parameter is 0.92, the corresponding prototype weight vectors is 786 and memory requirement is 232kB. Time required for training the system is less than five minutes and the recognition time was about 0.5 seconds/symbol. Total memory requirement in case of SFAM increases with increase in the value of vigilance parameter. Compared to HMM the memory requirement of SFAM is much higher. Table2 shows Recognition Rate, number of prototype weight vectors and memory requirement for different values of vigilance parameter (. 123 International Journal of Computer Engineering and Technology (IJCET), ISSN 0976 – 6367(Print), ISSN 0976 – 6375(Online) Volume 3, Issue 1, January- June (2012), © IAEME Recognition No. of Rate (%) prototype Memory requirement ρ weight vectors (kB) Db1 Haar Db1 Haar Db1 Haar 0.7 95.62 94.45 103 105 31.9 32.5 0.8 96.25 95.07 197 194 60.4 59.5 0.85 96.56 95.23 301 298 91.1 90.2 0.92 97.73 97.81 793 786 230 232 Table 2 Recognition Rate corresponding to different Vigilance parameterρ() Precision (P) and F- measure (F) of some most misclassified symbols are shown in the Table3. Precision is the ratio of predicted positive instances that were correct to the total number of false positive and true positive instances. F-measure is calculated using the following equation . 2 F = ( +1 )P×TPR β P+TPR Where ‘P’ is the precision, ‘TPR’ is true positiveβr’ is a positive number that adjust the relative importance of TPR and P. It is seen that for these symbols Precision of the system using HMM is generally higher than that of SFAM. The systems were implemented in MATLAB 7 and tested on a machine having Dual core AMD Opteron processor (2.19GHz) and 16GB of RAM. VII. C ONCLUSION It is observed that the overall performance of the system using SFAM is better than that of using HMM. Using SFAM we have got maximum accuracy of 97.81% and using HMM an accuracy of 95.24% is obtained. Training time required for SFAM is less than five minutes for the system and for HMM training time is in hours and proportional to number of states used. While using SFAM the recognition time is about 0.5 sec/symbol and for HMM recognition is proportional to number of states used and varies from 0.7 to 2.6 sec. Also the system using SFAM supports incremental learning, these features makes it ideal for practical implementation. The disadvantage of SFAM is that the memoryrequirement of SFAM is much higher than that of HMM and is proportional to the number of training patterns. There was some reduction in the accuracy of the systems due to some of the similar looking characters as well as poor handwriting styles. The performance ofthe system can be improved by using even 124 International Journal of Computer Engineering and Technology (IJCET), ISSN 0976 – 6367(Print), ISSN 0976 – 6375(Online) Volume 3, Issue 1, January- June (2012), © IAEME better features that will discriminate the similar looking characters. Again the system needs to be extended to recognize the Consonant conjuncts. R EFERENCES  G.Raju, 2006. “Recognition of Unconstrained Handwritten Malayalam Characters using Zero-crossing of Wavelet Coefficients,”. Proceedings. of ADCOM2006 , pp. 217–221.  V.S Roshini, Shanifa Beevi, Revathy,2005. “Machine Recognition of Malayalam Characters,” Proceedings of the International Conference on Cognition and Recognition, pp 477-481.  Bharath A Sriganesh madhvanath, 2007. “Hidden Markov Models for Online Handwritten Tamil Word Recognition,” ICDAR 2007, Vol. 1,pp 506-510.  S.Jaeger, S.Manke, J.Reichert, A Waibel, 2001. “On-Line handwriting recognition: The NPen++ Recognizer,” International journal of Document Analysis and Recognition, vol.3, no.3, pp 169-180.  V.Jagadeesh Babu, L.Prasanth, R.Raghunath Sharma, G.V. Prabhakara Rao, 2007. “HMM-based On-line Handwriting Recognition System for Telugu Symbols,”.ICDAR2007, Vol.1, pp 63:67.  M.pastor,A. Toselli, and E. Vidal. 2005. “Writing speed Normalization for On-Line handwritten text Recognition”. Proceedings of the 8tInternational conference on Document Analysis and Recognition, Vol. 2, pp 1131-1135.  Lawrence R. Rabiner. “A tutorial on HMMs and selected applications in speech recognition”. Proceedings of IEEE, Vol77, No2, Feb1989. www.tdil.mit.gov.in/MalayalamScriptDetailsApr02.pdf.  www.iball.co.in/Product.aspx.  H. Bunke, M. Roth, and E.G Schukat-Talamazzini 1995. “Offline Cursive Handwriting Recognition using Hidden Markov Models”. Pattern recognition, Vol 28 no.9, pp 1399-1413.  G.Rigoll, A.Kosmala, J.Rottland, Ch. Neukirchen 1996. “A comparison between Continuous and Discrete Density Hidden Markov Models for Cursive Handwriting Recognition”. Proceedings of ICPR , Vol. 2, pp 205-209.  K.P Soman, K.I ramachandran, “Insight in to Wavelets from theory to Practice”, Second Edition, Prentice Hall of India, 2005.  carpenter G.A, Grossberg S, et al, “Fuzzy ARTMAP: A Neural Network Architecture for Incremental Supervised Learning of Analog Multi dimensional Map”. IEEE Transactions on Neural Networks,vol.3,1992,pp.698-712  S. Rajasekharan and G. A. Vijayalakshmi pai, “Neural Networks, Fuzzy logic, Genetic algorithms: synthesis and applications”, PHI Publication, 2004.  M.Ananda Rao and J. Srinivas, “Neural Networks Algorithms and applications”.Narosa Publishing house.  Kasuba, T. "Simplified fuzzy ARTMAP." AI Expert,Vol.3,1993 Nov, pp18–25. [17 ] Prime kumar K.P and Sumam Mary Idiculla.“On-line Malayalam Handwritten Character Recognitionusing wavelet transform and SFAM”. Proceedings of ICECT 2010 , pp 205-209.  Data Mining: Methods and Techniques, ABM shawkat Al, Saleh A Wasimi, CENGAGE Learning. 125
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'