User Identification Using HTK

User Identification Using HTK

Vinita Balbhim Patil IV SEM, M.tech in Digital Electronics, Dept of ECE,

Appa IET Gulbarga

Shashidhar Sonnad ASSOC Prof, Dept of ECE, Appa IET, Gulbarga

Dr. Lalita Y S

1. Head, Dept of ECE, Appa IET, Gulbarga

   Abstract- As the rate of crime is increasing it is necessary to provide secure access for every individual. There are many methods for personal identification such as Smart cards, Personal identification number (PIN), Passwords. Though they provide secure access to authorized users, smart cards can be stolen, lost or duplicated while PIN and passwords can be forgotten, cracked. Forgery of signature can be done. But handwriting of every individual has unique characteristic. Hence it can be used to provide secure access. The main objective of this paper is to recognize cursive handwriting of a user by using Hidden Markov Model (HMM) with the help of HMM tool kit(HTK) in MATLAB.

   This Paper recognizes English handwritten scripts of 100 different users, where each user 9 instances are taken, in which some are kept separately for testing. By increasing the number of training instances, the rate of correct recognition goes on increasing.

   Key words: User identification, Handwriting recognition, Hidden Markov Model, HTK, Feature Extraction.

   1. INTRODUCTION

      Writer identification systems are very popular widely used and biometric systems for the authentication of financial transactions. Handwriting can be used for writer identification. Handwriting samples have the advantage of being more easily available then signature samples and also provide more data for analysis.

      Handwriting of different person has different stroke, tilt and other patterns. Each writing may comprise of different set of characters. Therefore handwriting recognition mainly depends upon extracting such features. Thus HMM is a suitable technique for detecting such features. The system is first normalized with respect to slant, skew, baseline location and height. A sliding window is used to transform a normalized handwritten text line into a sequence of feature vectors. The window is one pixel wide and shifted from left to right over a line of text. At each position of the window, five geometrical features are extracted and HTK is installed, HMM model is built, features extracted are passed into model.

      In this paper, offline personal identification system based on handwriting is described. Technique used to implement the handwriting recognition system3 is the Hidden Markov Model

      (HMM). As the handwritings are considered random in nature, first handwriting of a person is scanned and given as input to the system. System extracts the features and creates a feature database. When a sample scanned image of a person is given as input to HMM model, it identifies the writer.

      HMM based recognizers have a number of advantages over other approaches: First, they are resistant to noise and cope with shape variations. Second, they allow to model characters of variable width occurring in the text. Third, HMM based recognizers are able to implicitly segment a text line into words and characters, a task that is difficult to perform explicitly. Last, their exist standard algorithm for training and testing.

      For each writer in the considered population, an individual HMM based handwriting recognition is trained using only data from writer. Thus for n different writers we obtain n different HMMs. They all have the same architecture, but their parameters, i.e., transition and output probabilities, are different because they are trained on different data each.

      This paper is organized into 5 sections; section 1 gives the brief introduction of the topic .The remainder of the paper contains 4 sections. Section 2 describes the technique used for handwriting recognition i.e., HMM, Section 3 describes the proposed work, experimental results are presented in section 4 and conclusion is drawn in section 5.

   2. HMM

A Hidden Markov Model (HMM) [1] is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved (hidden) states. A HMM can be considered the simplest dynamic Bayesian network. The mathematics behind the HMM was developed by L. E. Baum and coworkers. It is closely related to an earlier work on optimal nonlinear filtering problem (stochastic processes) by Ruslan L. Stratonovich, who was the first to describe the forward-backward procedure.

In simpler Markov models (like a Markov chain), the state is directly visible to the observer, and therefore the state transition probabilities are the only parameters. In a hidden

Markov model, the state is not directly visible, but output, dependent on the state, is visible. Each state has a probability distribution over the possible output tokens. Therefore the sequence of tokens generated by an HMM gives some information about the sequence of states. Note that the adjective 'hidden' refers to the state sequence through which the model passes, not to the parameters of the model; the model is still referred to as a 'hidden' Markov model even if these parameters are known exactly.

Hidden Markov models are especially known for their application in temporal pattern recognition such as speech, handwriting, gesture recognition, part-of-speech tagging, musical score following, partial discharges and bioinformatics.

A Hidden Markov Model can be considered a generalization of a mixture model where the hidden variables (or latent variables), which control the mixture component to be selected for each observation, are related through a Markov process rather than independent of each other.

The formal definition of a HMM is as follows:

= , ,

(2.1)

A= state transition probability matrix B=observation probability matrix

=initial probability distribution for the states

1. Hidden Markov Model Structure Used In User Identification

   There are various structures of HMM .The most general structure is the ergodic or fully connected HMM. In this model transition can take place from every state to every other state of the model. Hence it is suitable for handwriting recognition as handwritings are random in nature and are independent of time. The model fulfills all the techniques. This model has the property 0< aij <1. The state transition matrix for an ergodic model can be described by:

   11 12 13 14

   =

   21 22 23 24

   31 32 33 34

   41 42 43 44

   Figure 1: Ergodic model

2. PROPOSED WORK

In this work the handwritten samples of 100 persons have been taken on a plane white a4 sheet and then scanned it, next step is to prepare the database for the experiment, so those scanned samples of individual users were taken in paint and cropped to extract the different lines/instances of a particular user, nine instances of each user were taken and for some users there are less than nine instances. Hence totally 880 instances are present including all 100 users.

Then some instances are used for training and remaining are kept separately for testing i.e, for all users first 1 instance of every user are trained and remaining 8 instances are kept for testing which are called validation set and note down the results for all the 100 users, than increase the training instances to 2 and then to 3 and so on. This is in order to improve the system performance.

Install the HTK and then build the model i.e., first initialize the model randomly and then improe guess by training them by using Baum-Welch algorithm from HTK, where it re-estimates the model by using the equations. Then use maximum likelihood classifier for recognition, if we get the

value of log likelihood same for many users then set a threshold for infinity, if the value is near to it then declare it as no match, else find the lowest value and declare it as class detected. If we give any instances other than 100 users, then we should set the threshold of 0.001 any value of log likelihood below this value declare it as no match.

The experiment is performed by training 1,2,3,4, 5 and 6 instances of each user. Features extracted value must be always 1,because HMM does not operate on 0 value, so while feature extraction if we get any 0 zero value than simply make it 1.In order to overcome this effect we take the mean and standard deviation before rotations(slant correction) and those values are used if we get multiple non 0 values.

Database: In the current work, the handwritten scripts of hundred different users are used. In this application 600 instances i.e., 6 instances of each user are used in training phase and 280 instances are used as validation set. It is scanned and stored, and then its features are extracted by below procedure.

1. Features Extraction

When we write we have different strokes, tilt and other patterns. Each writing may comprise of different set of characters. Therefore handwriting recognition depends on extracting such features. Thus HMM is suitable for detecting such features.

Preprocessing

The application considered in this thesis is the recognition of cursive handwriting. As basic classifier HMM-

based recognizer is used. Each person has a different writing style with his/her own characteristics. This fact makes the recognition complicated. To reduce variation in handwritten text as much as possible, the number of preprocessing operations is applied. The input for these preprocessing operations is images of instances extracted from the database. The images are scanned for good resolution. The following preprocessing steps are carried out

1. Binarisation: Convert the image to gray and then take the histogram of that image and convert it to binary image and take the negation of image.

   Figure 2: original image

   Figure 3: Grayscale of image

   Figure 4: Histogram of image

   Figure 5: Binary image

   Figure 6: Negation of image

2. Slant correction: Applying a shear transformation, The slant writings are transformed into an upright position and then the images is rotated from -45 degree to +45 degree in the instances of 5 degree and count all possible pixel values.

3. Skew correction: The word is horizontally aligned i.e., rotated such that base line is parallel to x axis of the image.

   Figure 7: slant angle and skew angle

   1. Line positioning: the words total extent in vertical direction is normalized to a standard value. Moreover applying a vertical scaling operation the location of upper and lower base line is adjusted to standard position.

   2. GEOMETRICAL FEATURE EXTRACTION

As previously stated there are around 300 features- this introductory article attempts to explain some of the basic ones that can be readily understood and which give interesting information like: slant, size, pressure, word spacing, line spacing and page margins.

No single handwriting feature proves anything specific or absolute by itself; a single feature alone can only identify a trend. It is the combination of features, and the interaction between them that enable a full and clear interpretation.

The main strategies for segmentation is straight segmentation tries to decompose the image in a set of subimages, each one corresponding to character. In segmentation recognition strategies the image is subdivided in a set of subimages whose combination are used to generate character. The number of subimages is greater than the number of characters and the process is referred to as over segmentation. A HMM is proposed for recognition of offline handwritten words. The histogram of the chain-code directions in the image scripts, scanned from left to right by sliding window is used as the feature vector.

The system for writer identification described here is based on HMM recognizers designed for the task of handwritten text line recognition. Each text line presented to the system is first normalized with respect to slant, skew, baseline location and height. A sliding window is used to transform a normalized handwritten text line into a sequence of feature vectors. The window is one pixel wide and shifted from left to right over a line of text. At each position of the window, five geometrical features are extracted. Hence the input to HMM is a sequence of five dimensional feature vectors of variable length.

The features represent the following geometrical quantities:

1. Number of black pixels in the window

2. Mean

3. Moment

4. Number of black-to-white transitions in the window

5. Fraction of pixels between upper and lower-most pixel

   Figure 8: Handwritten script of user 1 consisting of 9 lines

   (first 5 lines used for training and remaining 3 used for testing)

   Figure 9: Feature extraction of user 1

6. RESULTS AND DISCUSSION

   First a base classifier with 100 states is designed and then the experiment is performed for different trained instances i.e.,100,200,300, 400,500 and 600, where 5 different

   features are calculated for 100, 200, 300, 400, 500, 600 whereas for 700 we improve the feature extraction and passed to the classifier. Then the classifier is tested on validation set, immediately after training cycle is completed. The performance of the system was fond to be 10.25%, 19.11%, 32.75%, 47.29%, 57.36% and 92.85% respectively as shown in the table I.Figure 10 shows that as we train more number of instances the accuracy or rate of correct recognition go on increasing.

   Table I Performance of the system

   No of instances trained	No of testing instances	No of mismatched Instances	Accuracy In %
   1*100	780	700	10.25
   2*100	680	550	19.11
   3*100	580	390	32.75
   4*100	480	253	47.29
   5*100	380	162	57.36
   6*100	280	20	92.85

   Figure 10: System Performance

7. CONCLUSION AND FUTURE WORK

This project mainly does the handwriting recognition using statistical model that is, Hidden Markov Model. The recognition is writer dependent. We have used the discrete HMM and ergodic model, which uses the model evaluation, Baum-Welch algorithm and loglikelihood algorithm. This project recognizes English handwritten scripts of 100 different users, where each users 9 instances are taken, in which some are kept separately for testing. By increasing the number of training instances the rate of correct recognition goes on increasing. Results show that the average classification of 100 classes with 100 state and 600 instances trained is nearly 92.85%.

Future Improvements: The accuracy of the designed classifier may be improved by training more number of data, taking higher order features for extracting the features and increasing the number of states and so on.

ACKNOWLEDGMENT

I would like to express my sincere gratitude towards my guide Prof. Shashidhar and PG head Dr. Lalita.Y.S for their invaluable guidance. This work would not be complete without their constant support and encouragement.

1. L. R..Rabiner and B. H. Juang, An Introduction to Hidden Markov ModelsJanuary 1986 IEEE ASSP Magazine.

2. Lawrence R Rabiner-A Tutorial on Hidden Markov Model and selected applications in speech recognition- Proceedings of IEEE, vol. 22, No.2, February 1989.

3. Emanuel Inderm uhle1 and Marcus Liwicki1,2 and Horst Bunke1, Recognition of Handwritten Historical Documents: HMM-Adaptation vs. Writer Specific Training

4. Bing Feng, Xiaoqing Ding, Youshou Wu, Chinese Handwriting Recognition Using Hidden Markov Models 1051-4651/02 $17.00 (c) 2002 IEEE.

5. Anoop M. Namboodiri, Student Member, IEEE, and Anil K. Jain, Fellow, IEEE-Online Handwritten Script Recognition, IEEE transactions on pattern analysis and machine intelligence, vol. 26, no. 1, January 2004

6. Alain Lifchitz A fast lexically constrained viterbi algorithm for online handwriting recognition In: L.R.B. Schomaker and L.G. Vuurpijl (Eds.), Proceedings of the Seventh International Workshop on Frontiers in Handwriting Recognition,September 11-13 2000, Amsterdam, ISBN 90- 6942-01-3, Nijmegen: International Unipen Foundation.

7. Charles C. Tappert and Sung-Hyuk Cha,English Language Handwriting Recognition Interfaces- Chapter 6 in Text Entry Systems, ed. MacKenzie and Tanaka-Ishii,Morgan Kaufman, 2007.

8. Fadi Biadsy, Jihad El-Sana, Nizar Habash-Online Arabic Handwriting Recognition Using Hidden Markov Models

9. Z.Hachkar, A. Farchi , B.Mounir, J. EL Abbadi Building HMM recognizer for Arabic Digits using HTK

10. B. VERMA, M. BLUMENSTEIN & S. KULKARNI- Recent Achievements in Off-line Handwriting Recognition Systems

11. E. Kavallieratou, N. Fakotakis, G. Kokkinakis-An unconstrained handwriting recognition system IJDAR (2002) 4: 226242.

12. Christophe Choisy and Abdel Belaid-Handwriting Recognition Using Local Methods for Normalization and Global Methods for Recognition-ICDAR

13. A. L. Koerich, R. Sabourin, C. Y. Suen-Large vocabulary off-line handwriting recognition:A survey- Pattern Anal Applic (2003) 6: 97121, DOI 10.1007/s10044-002-0169-3.