Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Real-time computer recognition of handprinted characters Chui, Timothy Loong-kei 1976

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1976_A7 C49_8.pdf [ 5.62MB ]
Metadata
JSON: 831-1.0065484.json
JSON-LD: 831-1.0065484-ld.json
RDF/XML (Pretty): 831-1.0065484-rdf.xml
RDF/JSON: 831-1.0065484-rdf.json
Turtle: 831-1.0065484-turtle.txt
N-Triples: 831-1.0065484-rdf-ntriples.txt
Original Record: 831-1.0065484-source.json
Full Text
831-1.0065484-fulltext.txt
Citation
831-1.0065484.ris

Full Text

REAL-TIME COMPUTER RECOGNITION OF HANDPRINTED CHARACTERS by Timothy Loong-kei Chui B.S., Lowell Technological Institute, 1974 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENT FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in the Department E l e c t r i c a l Engineering We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA July 1976 (c) Timothy Loong-kei Chui, 1976 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e H e a d o f my D e p a r t m e n t o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Depa r t m e n t The U n i v e r s i t y o f B r i t i s h C o l u m b i a 2 0 7 5 Wesbrook P l a c e Vancouver, Canada V6T 1W5 ABSTRACT A real-time character recognition system was developed to re-cognize upper case handprinted characters in a real-time small machine environment. The recognition system consists of two major components: namely, a data acquisition system and a pattern recognition system. The data acquisition system was designed and implemented to allow the real world data flow into the computer from a COMPUTER writing tablet i n real time. The pattern recognition system was also designed and implemented to yield a decision on the input character i n real time (user time). A curve optimization technique originally devised by Reumann and Witkam was modified to extract only the significant data that de-scribes a character. Computations were minimized through mathematical simplifications, hardware-software trade-off, and special programming techniques at the machine le v e l . In addition, the preprocessor operated concurrently with the data acquisition routine to reduce data storage requirements as well as to-provide fast response to handprinted inputs. A non-uniform quantization plane was proposed and implemented to discriminate pen directions. Stroke patterns of a character were recognized using a syntactic approach. Finally, recognized stroke patterns within a character were classified as one of the known pattern classes by two classification methods: dictionary look-up and a modified nearest neighbor rule, both guided by special geometric measurements on some char-acter pairs. Character patterns were defined in the dictionary such that no user training or personalized dictionary i s required for future use. A test was conducted using the ACM proposed upper case hand-printed character set and a recognition rate of 98.3% was obtained from over 2300 characters of sizes varying from 1/4 inch t a l l to 3/4 inch t a l l i from 10 people. I t I s observed that the approach taken i n t h i s t h e s i s can a l s o be a p p l i e d to recognized handprinted p a t t e r n s other than the standard one proposed by the ACM. i i TABLE OF CONTENTS Page ABSTRACT . . . . . . . i TABLE OF CONTENTS i i i LIST OF ILLUSTRATIONS . . . . . . . . . . v LIST OF TABLES v i i ACKNOWLEDGEMENT v i i i I. INTRODUCTION 1 1.1 Introduction 1 1.2 Review . . . . . . . . . . . . . . . . 3 1.3 Scope of the Thesis . . . . . 7 II. DATA ACQUISITION SYSTEM 10 2.1 Introduction . . . . . . . . . . 10 2.2 A Writing Tablet and Its Interface to Computer . . . . 10 2.3 Software Support for Hardware Interface 13 III. THE PREPROCESSING PART OF THE PATTERN RECOGNITION SYSTEM . 18 3.1 Introduction 18 3.2 The Preprocessing Problem 20 3.3 Design of the Preprocessing Algorithm 21 3.4 Algorithm Simplification 29 3.5 On-line Data Processing . . . . . . . . . 33 IV. STROKE PRIMITIVE IDENTIFICATION 36 4.1 Introduction 36 4.2 Pattern Representation 39 4.2.1 Basic Feature Classification 39 i i i 4.2.2 Straight Line Representation 42 4.2.3 Slope Quantization 44 4.2.4 Curve Representation 47 4.3 Syntax Analysis 49 7. STROKE PRIMITIVE CLASSIFICATION ' 59 5.1 Introduction 59 5.2 Dictionary Look-up Method 59 5.3 Modified Nearest Neighbor Classifier 62 5.4 Geometric Aid to Classification 65 VI. EXPERIMENT AND RESULTS 69 6.1 Introduction 69 6.2 The Experiment 69 6.3 Results 74 6.4 Additional Results . . . , • 84 VII. CONCLUSIONS . . . . . . . . . . . . . . . 91 7.1 Discussion . . • 91 7.2 Summary 96 7.3 Suggestions for Further Research 97 REFERENCES . 102 APPENDIX A 106 i v LIST OF ILLUSTRATIONS Figure Page 1.1 The basic real-time computer recognition system diagram . 8 2.1 System diagram of handprinting system 12 2.2 Flowchart for the tablet handling task 17 3.1 The pattern recognition system block diagram 19 3.2 Curve segmentation diagram 22 3.3 Loss of local property of a curve due to a large T . . . 26 3.4 Comparison of rate of curvature changes in two different size characters 27 3.5 Calculation for distance d . 29 3.6 Flowchart for the preprocessor 32 3.7 Flowchart for the supervisor task . 35 4.1 The character 'C' in different shapes 38 4.2 Structural description of character 'R' 38 4.3 Flowchart for the stroke primitive identification process 40 4.4 Basic feature separation diagram 41 4.5 Two commonly seen quantization planes . 44 4.6 Stroke primitive comparison 45 4.7 The new quantization plane 46 4.8 Block diagram of syntactic curve recognizer •.. . 50 4.9 D-curve diagram 51 4.10 Three C-curve representations .. 53 4.11 Slope code sequence processing 54 4.12 Directional locus of an unknown vector 55 4.13 Examples of line drawings with abrupt slope changes . . . 55 4.14 Directional l o c i of the stroke primitives 57 v Figure Page 5.1 Character 'A' representations 62 5.2 The character pair *D' & 'P* 67 6.1 Handprinted samples obtained from the experiment (reduced by approximately 19%) > 72 6.2 Examples of successfully recognized handprinted characters other than the ACM Standard 86 6.3a Examples of successfully recognized, intentionally distor-ted characters 87 6.3b Examples of successfully recognized characters formed by badly drawn line drawings 89 6.3c Examples of successfully recognized extremely large and small characters 90 vi LIST OF TABLES Table Page 6.1 System test results: small-size characters . . . . . . . 75 6.2 System test results: medium-size characters 76 6.3 System test results: large-size characters . . . . . . . 77 6.4 System test results characters of a l l three sizes . . . . 78 6.5 Distribution of correct classification for the two stage c l a s s i f i e r 79 6.6 Summary of system test results 80 6.7 Classification of errors • 83 v l l ACKNOWLEDGEMENT I would like to express my gratitude to Professor Mabo R. Ito for his advice and encouragement during the course of this project. I am also grateful to Professor Robert W. Donaldson for reading the manu-script and offering helpful suggestions. Support of this study by the National Research Council of Canada under NRC Grant A9054, and through a B r i t i s h Columbia Telephone Company Graduate Scholarship are gratefully acknowledged. I wish to thank Mr. George Austin for providing technical assistance during the implementation of this project, Mr. Tony Leugner for building the writing tablet interface, members of the E l e c t r i c a l Engineering Department who participated in the handprinting experiment and Mr. James Yan for his helpful discussion. I also would like to thank my sister, Anne, and Ms. Flanagan for typing part of this manuscript, and my brother, Andrew, for pro-ducing some of the graphs included in this thesis. Finally, I am indebted to my parents for a l l they have done for me. v i i i 1 CHAPTER 1 INTRODUCTION 1.1 INTRODUCTION Research i n o n - l i n e c h a r a c t e r r e c o g n i t i o n negan i n the mid-60s [ 20,5,43,7 ] but very l i t t l e work has been r e p o r t e d i n t h i s area d u r i n g the past ten years. Most of the p u b l i s h e d r e s e a r c h i n machine c h a r a c t e r r e c o g n i t i o n i s t h a t ox o f f - l i n e and o p t i c a l c h a r a c t e r r e c o g n i t i o n [ 33,27 ] . The reason f o r t h i s i s t h a t an o n - l i n e c h a r a c t e r r e c o g n i t i o n system r e g u i r e s s p e c i a l hardware, such as a t a b l e t , i n t e r f a c e d to a computer, and the s e r v i c e of a computer i n r e a l time. Before the wide spread use of minicomputers i n the 70*s, i t seemed i m p r a c t i c a l t o perform an o n - l i n e c h a r a c t e r r e c o q n r t i o n on a g e n e r a l purpose computer i n terms of CPU time. However, with the advent of minicomputers and m i c r o p r o c e s s o r s , i t became p r a c t i c a l both i n terms of c o s t and CPU time t o a s s i g n a s m a l l machine to perform t h i s s p e c i a l t a s k . Generation of a handprinted c h a r a c t e r i s a dynamic, s e g u e n t i a l p r o c e s s . In o f f - l i n e r e c o g n i t i o n , measurements a r e taken on the c h a r a c t e r a f t e r i t i s formed, so t h a t the dynamic i n f o r m a t i o n d e s c r i b i n g the pen movement i s not r e t a i n e d . The o f f - l i n e r e c o g n i t i o n approach thus has t o e x t r a c t c h a r a c t e r f e a t u r e s from geometric o r i e n t a t i o n , r e l a t i v e p o s i t i o n s , contour t r a c i n g , mask. matching [30,33,45], e t c . O n - l i n e c h a r a c t e r g e n e r a t i o n i n f o r m a t i o n , on the other hand, not o n l y p r o v i d e s the s t a t i c geometric shape, i t a l s o y i e l d s the time sequence h i s t o r y of the pen movement. Host o n - l i n e c h a r a c t e r r e c o g n i z e r s developed t o d a t e have been developed on l a r g e systems and i n v o l v e d a l a r g e amount of computation. Many of those o n - l i n e a l g o r i t h m s , i n f a c t , ! s t a r t t h e i r r e c o g n i t i o n process only a f t e r the e n t i r e c h a r a c t e r has been drawn. Thus th e r e i s always s i g n i f i c a n t d e l a y from the c h a r a c t e r completion to macuine response, depending on the complexity of the r e c o g n i t i o n a l g o r i t h m . In order to achieve a high r e c o g n i t i o n r a t e , most of the r e c o g n i z e r s u s u a l l y r e g u i r e user t r a i n i n g , machine l e a r n i n g , p e r s o n a l i z e d d i c t i o n a r y b u i l d i n g , s p e c i f i c c h a r a c t e r s i z e and o r i e n t a t i o n s , e t c . I t i s the aim of t h i s t h e s i s to present an e f f i c i e n t , f a s t and simple a l g o r i t h m to r e c o g n i z e handprinted c h a r a c t e r s i n a s m a l l system environment i n r e a l time. Computations are minimized to reduce CPU time. P r e p r o c e s s i n g occurs c o n c u r r e n t l y with data a c g u i s i t i o n t o provide f a s t response time. No user t r a i n i n g , d i c t i o n a r y b u i l d i n g or machine l e a r n i n g i s r e q u i r e d . C h a r a c t e r s of v a r i a b l e s i z e s and reasonable degree of s l a n t and d i s t o r t i o n are a l s o a c c e p t a b l e . There are two g e n e r a l approaches to p a t t e r n r e c o g n i t i o n problems, namely, the d e c i s i o n - t h e o r e t i c , s t a t i s t i c a l , approach and the s y n t a c t i c approach. In a survey paper, Kanal[27] p o i n t e d out t h a t e x t e n s i v e r e s e a r c n i n d e c i s i o n -t h e o r e t i c , m u l t i v a r i a t e , s t a t i s t i c a l approaches marked the p e r i o d of 1960 to 1968 i n p a t t e r n r e c o g n i t i o n and he c r i t i c i z e d the d e c i s i o n - t h e o r e t i c , s t a t i s t i c a l approach f o r f o c u s i n g too much on the s t a t i s t i c a l r e l a t i o n s h i p among s c a l a r f e a t u r e s r a t h e r than on the s t r u c t u r a l p r o p e r t i e s t h a t d e s c r i b e p a t t e r n s . In the s y n t a c t i c approach, a complex p a t t e r n i s d e s c r i b e d i n terms of a composition of simple s u b p a t t e r n s , and each sub p a t t e r n again i s d e s c r i b e d i n terms of even s i m p l e r s u b p a t t e r n s ( p r i m i t i v e s ) [ 1 7 J . For ha n d p r i n t e d c h a r a c t e r s , each c h a r a c t e r can be c o n s i d e r e d t o ce composed of one or more s t r o k e s with each s t r o k e c o n s t i t u t i n g a simple p r i m i t i v e . In t h i s t h e s i s , s y n t a c t i c and pragmatic approaches are u t i l i z e d t o r e a l i z e a si m p l e , e f f i c i e n t , and p r a c t i c a l system i n a s m a l l machine environment t o r e c o q n i z e handprinted c h a r a c t e r s i n r e a l time. 1.2 Review Most of the e a r l i e r o n - l i n e computer r e c o g n i t i o n systems employed d i f f e r e n t hardware i n p u t d e v i c e s and r e s u l t e d i n d i f f e r e n t i n f o r m a t i o n about the p a t t e r n s . However, f o r a l l work, some time-sequence i n f o r m a t i o n was e x t r a c t e d . I n 1964, Brown[7 ] used a m e t a l l i c s t y l u s to t r a c e a c h a r a c t e r over a p l a t e n which had seven e l e c t r i c a l l y d i s t i n c t r e g i o n s . T e i t e l m a n [ 4 3 ] used a sensing t a b l e t on which the w r i t i n g area was d i v i d e d i n t o nine r e c t a n g l e s of 3X3 boxes. Gronerf 20,21 ], B e r n s t e i n [ 3 , 5 ] and M i l l e r [ 3 1 ] a l l used a RAND t a b l e t f14 ], and G a i l l e t [ 1 9 ] used a S h i n t r o n graph t a b l e t . A i l these t a b l e t s p r o v i d e the a b s o l u t e pen p o s i t i o n of the c h a r a c t e r t r a c e . Powers[39,40,38 ] used a system which c o n v e r t e d the analog t r a c e of the pen p o s i t i o n to d i g i t a l c o - o r d i n a t e s . F u j i s a k i e t a l [ 1 7 ] used a cathode-ray tube g r a p h i c d i s p l a y with a l i g h t pen as the data i n p u t d e v i c e . Other r e s e a r c h work has a l s o been r e p o r t e d [36,19,25,18,6,2,15]. I t i s observed t h a t many r e s e a r c h e r s have paid some a t t e n t i o n to the s t r o k e i n f o r m a t i o n and made use of d i r e c t i o n a l i n f o r m a t i o n i n one way or another-Among the p r e v i o u s r e s e a r c h i n the area or o n - l i n e r e c o g n i t i o n of handprinted c h a r a c t e r s , the s t u d i e s by Groner[20], B e r n s t e i n [ 3,5 ], I 1 i l l e r [ 3 1 ] and Powers[40] are the most s i g n i f i c a n t . Groner[20] s u c c e s s f u l l y developed a r e c o g n i z e r which ran on a l a r g e computer system to do w r i t i n g and e d i t i n g of computer codes and drawing of f l o w c h a r t s . In h i s r e c o g n i t i o n scheme, the f i r s t f o u r d i r e c t i o n s of a s t y l u s t r a c e were used t o separate the s t r o k e s i n t o v a r i o u s groups. Father a n a l y s i s was then c a r r i e d out through the use of data-dependent sequences, from which aspect r a t i o s , the number and p o s i t i o n of c o r n e r s , the number and p o s i t i o n s of maxima and minima i n X and Y, and the p o s i t i o n of the s t a r t i n g and ending p o i n t s r e l a t i v e to the symbol extremes were recorded. However, h i s c l a s s i f i c a t i o n was cased on c r o s s - l i n k e d t r e e s t r u c t u r e s which makes a d d i t i o n or d e l e t i o n of a symbol d i f r i c u l t and c o m p l i c a t e d . A l s o , f o r h i s experiment, users were r e q u i r e d to p a r t i c i p a t e i n a h a l f - h o u r t r a i n i n g s e s s i o n p r i o r to the t e s t . The average r e c o g n i t i o n r a t e of h i s system v a r i e d from 81% f o r those with no experience with h i s r e c o g n i t i o n scheme t o 93% f o r users who had c o n s i d e r a b l e experience with the: r e c o g n i t i o n scheme. Groner a l s o p o i n t e d out t a a t h i s system had d i f f i c u l t i e s i n r e c o g n i z i n g g u i c k l y p r i n t e d t e x t . B e r n s t e i n ' s e a r l y work i n o n - l i n e c h a r a c t e r r e c o g n i t i o n was r e p o r t e d i n 1966£3]. In 1969, B e r n s t e i n and H o w e l l [ 5 J developed a r e c o g n i t i o n system which operated under a Time-Share System. The d i r e c t i o n a l changes between p o i n t s were c a l c u l a t e d tb check i f c o r n e r s or i n f l e c t i o n p o i n t s e x i s t e d . In a d d i t i o n , an area f e a t u r e s t r i n g was used to d e s c r i b e the geometric shape of a s t r o k e . The r e c t a n g u l a r area used was d i v i d e d i n t o f i v e sub-areas with a diamond-shape a r e a i n the middle. The c l a s s i f i c a t i o n scheme r e g u i r e d exact match of area f e a t u r e s t r i n g t o one of the sample s t r i n g s i n the d i c t i o n a r y c o n s t r u c t e d from e a r l i e r t r a i n i n g s e t s , f o r t h i s reason, while b u i l d i n g h i s d i c t i o n a r y , a user had to i n p u t an average of t h r e e to f o u r d i c t i o n a r y e n t r i e s per c h a r a c t e r . Such an approach u s u a l l y r e g u i r e s more memory space and w i l l f a i l to r e c o g n i z e f e a t u r e s t r i n g s which are not i n c l u d e d i n the t r a i n i n g s e t . They a l s o p o i n t e d out t h a t some l e a r n i n g p e r i o d would be r e g u i r e d f o r u n t r a i n e d u s e r s . M i l l e r [ 3 1 ] used a bestmatch technigue which e l i m i n a t e d the m u l t i p l e e n t r i e s r e g u i r e d f o r d i c t i o n a r y b u i l d i n g . He 6 i n t r o d u c e d the i d e a of a contour v e c t o r sequence (CVS) as the f e a t u r e s t r i n g . The contour v e c t o r i s a f i x e d - l e n g t h v e c t o r i n d i c a t i n q the d i r e c t i o n seguence of a s t r o k e . A s t r o k e was normally d i v i d e d i n t o s i x e q u a l - l e n g t h segmentations r e g a r d l e s s of the c h a r a c t e r s i z e . Each segment was approximated by a s t r a i g h t l i n e and was a s s i g n e d an o c t a l q u a n t i z e d code i n d i c a t i n g the d i r e c t i o n of the segment. The code of a s t r o k e l a t e r formed p a r t of the CVS. The d i r e c t i o n a l i n f o r m a t i o n was o b t a i n e d through c a l c u l a t i o n of p o s i t i o n a l i n f o r m a t i o n . In b u i l d i n g of a user's d i c t i o n a r y , , one e n t r y per symbol was r e g u i r e d p r i o r t o the r e c o g n i t i o n . In the c l a s s i f i c a t i o n s t a g e , only the bestmatch d i c t i o n a r y e n t r y , based on the Lee d i s t a n c e was s e l e c t e d . In n i s system, f e a t u r e p r o c e s s i n g cannot take place u n t i l the complete s t r o k e i s f i n i s h e d , so t h a t a l l data must oe s t o r e d . U n f o r t u n a t e l y , even-spaced CVS's u s u a l l y i g n o r e tne l o c a l p r o p e r t i e s of c h a r a c t e r f o r m a t i o n . He r e s t r i c t e d c h a r a c t e r s i z e t o be 1/4 i n c h t a l l f o r which he achieved a r e c o g n i t i o n r a t e o f 98% on most s u b j e c t s . Powers[39,40,38 ] attempted t o r e c o g n i z e t e n A r a b i c numerals based on only one d i r e c t i o n a l parameter. He d e f i n e d a g e n e r a t i v e model which c o n s i s t e d of t h r e e p a r t s : a grammar and two s e t s of t r a n s f o r m a t i o n s . The s l o p e between each s u c c e s s i v e p a i r of c o - o r d i n a t e s was c a l c u l a t e d ana g u a n t i z e d i n t o one of the e i g h t p o s s i b l e d i r e c t i o n codes. The d i r e c t i o n sequence, c o n s i s t i n g of o c t a l d i r e c t i o n codes, was compacted i n order to be r e s o l v e d to an a r c . A noise r e d u c t i o n t r a n s f o r m a t i o n provided smoothing f o r d i s t o r t e d a r c s . F i n a l l y , a processed curve was e x t r a c t e d and was used to check a g a i n s t the d i c t i o n a r y u s i n g n e a r e s t neighbor c l a s s i f i c a t i o n . Powers r e a l i z e d t h a t the time sequence of pen d i r e c t i o n was a very prominent f a c t o r i n h i s o n - l i n e r e c o g n i t i o n approach. His i n v e s t i g a t i o n a l s o i n d i c a t e d t o what extent d i r e c t i o n i n f o r m a t i o n can be used r n o n - l i n e c h a r a c t e r r e c o g n i t i o n . C h a r a c t e r s which nave s i m i l a r d i r e c t i o n seguences, such as 6 and 0, c o u l d not ue e a s i l y d i s t i n g u i s h e d by d i r e c t i o n i n f o r m a t i o n a l o n e , l o a v o i d c o n f u s i o n between 6 and z e r o , users were r e g u i r e d t o add an e x t r a loop a t the end of a z e r o . A user of h i s system was r e g u i r e d to c o n s t r u c t a p e r s o n a l d i c t i o n a r y . In Powers' t e s t r e s u l t s , the unrecognized r a t e was somewhat h i g h , r a n g i n q from 7.2% f o r the author to 21.2% f o r o t h e r s . Powers p o i n t e d out t h a t f o r most ca s e s , the system f a i l e d to i d e n t i f y a sample when the sample was improperly c l a s s i f i e d i n t o a r c s i n the p r e p r o c e s s i n g s t a g e . 1.3 Scop_e of the T h e s i s The complete r e a l time c h a r a c t e r r e c o g n i t i o n system i s shown i n F i g . 1.1. I t c o n s i s t s of two major components: the data a c q u i s i t i o n system and the c h a r a c t e r r e c o g n i t i o n system. In Chapter 2, the i n t e r f a c e of the COdPUTEK w r i t i n g t a b l e t t o a computer and i t s software support are d e s c r i b e d 8 REAL irvo/tLbjt DIGITAL / DATA 2>ATA ACQUISITION SYSTEM CHARACTER. bECtS/0*J RECOGM'TIOtJ SYSTEM F i g . 1.1 The b a s i c r e a l - t i m e computer r e c o g n i t i o n , system diagram. with emphasis placed on r e a l - t i m e r e c o g n i t i o n needs. In Chapter 3, the p r e p r o c e s s i n g part of the r e c o g n i t i o n system i s presented. A s p e c i a l technique i s d - s c r i n e d t o e x t r a c t s i g n i f i c a n t f e a t u r e data of p a t t e r n s . I n Chapter 4, a s y n t a c t i c method i s developed to i d e n t i f y s t r o k e p a t t e r n s with r e f e r e n c e t o p r e d e f i n e d prototype p r i m i t i v e s . In Chapter 5, the st r o k e p r i m i t i v e s of a c n a r a c t e r or an unrecognized c l a s s , f i r s t by a d i c t i o n a r y look-up method, but i f t h a t f a i l s , a second method using d i s t a n c e measurement i s employed. Both methods are aided by a few s p e c i a l r o u t i n e s which are necessary f o r d i s t i n c t i o n of some c h a r a c t e r p a i r s . I n Chapter 6, an i n t e r a c t i v e experiment i s d e s c r i b e d to t e s t the de s i g n and implementation of the r e a l - t i m e c h a r a c t e r r e c o g n i z e r . Over 2300 c h a r a c t e r s were c o l l e c t e d from a p o p u l a t i o n of 10 people. A r e c o g n i t i o n r a t e i n excess of 98* 9 was obtained- A d d i t i o n a l r e s u l t s show f u r t h e r a p p l i c a t i o n of the approach taken i n t h i s t h e s i s and the c a p a b i l i t i e s of the r e c o g n i t i o n system on d i s t o r t e d c h a r a c t e r s . In Chapter 1, the o v e r a l l system design and performance are e v a l u a t e d and d i s c u s s e d . Futher improvements and e x t e n s i o n s of the present work are a l s o suggested. 10 CHAPTER 2 DATA ACQUISITION SYSTEM 2.1 I n t r o d u c t i o n As d i s c u s s e d i n Chapter 1, many kin d s or i n p u t d e v i c e s have been used i n p r e v i o u s o n - l i n e c h a r a c t e r r e c o g n i t i o n r e s e a r c h . However, they a l l provide some i n f o r m a t i o n about the time seguence of r e l a t i v e pen p o s i t i o n s on the t a b l e t . The RAND t a b l e t [ 1 4 ] has been used by Groner[20], B e r n s t e i n f 5 ] and M i l l e r [ 3 1 ] , In those systems, however, the u s e r ' s eyes are always foc u s e d on the CRT [19,20,5,31]. Tnat i s , while the pen i s moving on the t a b l e t , the a c t u a l ' i n k i n g * appears on the CRT. Such a w r i t i n g environment i s unnatural to most people. A l s o , d i s p l a y of the pen ' i n k i n g * u s u a l l y r e g u i r e s a d d i t i o n a l CPU time and memory. To the u s e r s , i t i s d e s i r a b l e t h a t the w r i t i n g environment c o n s i s t s only of a pen and a p i e c e of paper. The commercially a v a i l a b l e COMPUTEK w r i t i n g t a b l e t used i n t h i s t h e s i s meets t h i s reguirement. 2-.2 A W r i t i n g T a b l e t and I t s I n t e r f a c e to the Computer The o n - l i n e c h a r a c t e r r e c o g n i t i o n system was designed u s i n g the NOVA Real Time Disk Operating System environment. The computer system, shown i n F i g . 2.1, c o n s i s t s of a NOVA 840 minicomputer which has a 16 b i t word l e n g t h , 32K words o f memory and a c y c l e time of .8 microsecond. A s s o c i a t e d with the minicomputer are a d i s k u n i t , tape u n i t , t e l e t y p e , CRT 11 d i s p l a y and the COMPUTER t a b l e t . The t e l e t y p e and the CRT d i s p l a y are b a s i c a l l y used to g i v e the command to s t a r t t he system. Once the system i s s t a r t e d , these d e v i c e s are used t o gi v e a p p r o p r i a t e feedback i n the i n t e r a c t i v e environment. E i t h e r the t e l e t y p e or the CRT d i s p l a y i s s u f f i c i e n t . For; t h i s purpose, however, the CRT d i s p l a y can a l s o be used t o d i s p l a y the r e l a t i v e t r a c k of a c h a r a c t e r p r o d u c t i o n . The l i n e p r i n t e r can be used to c o l l e c t i n t e r m e d i a t e r e s u l t s of the r e c o g n i t i o n p r o c e s s . The magnetic tape can be used to c o l l e c t the raw data i f a data base of r e a l time h a n d p r i n t e d c h a r a c t e r s i s d e s i r e d . The COMPUTER t a b l e t c o n s i s t s of a sguare w r i t i n g s u r f a c e of 11.25 by 11.25 i n c h e s , with a pen a t t a c h e d to i t . The t a b l e t c o n t r o l l e r senses the pen movement and s u p p l i e s the computer with d i g i t a l r e p r e s e n t a t i o n s of the X, Y and Z co-o r d i n a t e s . C o - o r d i n a t e s X and Y each have a 10 b i t r e p r e s e n t a t i o n , thus y i e l d i n g a range of 0 to 1023 u n i t s f o r each c o - o r d i n a t e . The Z i n f o r m a t i o n i s c o n s i d e r e d t o have t h r e e modes; (i) pen o f f : i n which the pen i s 1/4 i n c h above the t a b l e t s u r f a c e and no i n t e r r u p t w i l l be sent t o the computer. ( i i ) pen p r o x i m i t y : i n which the pen i s w i t h i n 1 /4 i n c h of the t a b l e t s u r f a c e but has no downward w r i t i n g f o r c e on the t a o l e t or the f o r c e i s l e s s than 3 ounces. LINE PRINTER to F i g . 2.1 Block diagram of the ha n d p r i n t i n g system. 13 ( i i i ) pen p r e s s u r e : i n which the pen i s t o u c h i n g the t a b l e t s u r f a c e with a w r i t i n g f o r c e of 3 ounces or more. A r i g n t on the t a b l e t i n d i c a t e s to tne user t h a t there i s enough w r i t i n g f o r c e . The t a b l e t operates on c o n s e c u t i v e 800-microsecond time i n t e r v a l s but an i n t e r r u p t i s generated from tne t a n l e t only i f the pen has changed i t s p o s i t i o n ; hence the time e l a p s e d between two c o n s e c u t i v e i n t e r r u p t s i s always a m u l t i p l e of 800 microseconds. At present, t h e r e are one pusn button and f i v e switches on the t a b l e t to provide a wide v a r i e t y of c o n t r o l s d u r i n g the t a b l e t o p e r a t i o n . To write on the t a b l e t , a p i e c e of paper i s p l a c e d on the t a b l e t s u r f a c e and c h a r a c t e r s are p r i n t e d on tne paper i n a normal way using the t a b l e t pen. 2_-3 Software Support f o r Hardware I n t e r f a c e The design of software support f o r the COMPUIEK t a b l e t i n t e r f a c e to NOVA RDOS was determined by the s p e c i f i c reguirements of an o n - l i n e c h a r a c t e r r e c o g n i t i o n system. That i s , the software design must ensure t h a t no e s s e n t i a l data r e l a t i n g t o the dynamic h i s t o r y of the pen motion i s l o s t . In our system t h i s means t h a t a l l program i n t e r r u p t s generated by the t a b l e t must be honored. As i n many p a t t e r n r e c o g n i t i o n problems, a l a r g e amount of i n p u t data i s i n v o l v e d . In the o f f - l i n e approacn, t h i s data i s u s u a l l y s t o r e d i n magnetic tape or disk, and then processed at w i l l . In o n - l i n e r e c o g n i t i o n , some data must 14 a l s o be s t o r e d t e m p o r a r i l y f o r l a t e r p r o c e s s i n g . However, i f a l l the data i s s t o r e d p r i o r to p r o c e s s i n q , then e i t h e r an u n r e a l i s t i c amount of main memory i s r e q u i r e d or e x t r a time i s r e q u i r e d f o r d i s k s t o r a q e . Futhermore, s e q u e n t i a l o p e r a t i o n of the data a c q u i s i t i o n and p r e p r o c e s s i n q u n n e c e s s a r i l y degrades response time. I t i s d e s i r a u l e , i n a r e a l time environment, t h a t response time oe as f a s t as p o s s i b l e . To s o l v e both the data s t o r a g e and e x e c u t i o n speed problems, p r e p r o c e s s i n g of the i n p u t data occurs c o n c u r r e n t l y with the data i n p u t . Out of the l a r g e amount of raw data r e c e i v e d , o n l y a s m a l l f r a c t i o n i s s i g n i f i c a n t . I t i s d e s i r a b l e t h a t t h e i n s i g n i f i c a n t data be removed a t the e a r l i e s t p o s s i b l e stage so that the computations are reduced i n the l a t e r s t a g e s . Furthermore, removal of n o i s y data improves the chance of o b t a i n i n g c o r r e c t f e a t u r e s f o r a c h a r a c t e r . T h i s data r e d u c t i o n i s d i s c u s s e d i n d e t a i l i n Chapter 3. To u t i l i z e the l i m i t e d memory s i z e , t y p i c a l of s m a l l computers, a s m a l l c i r c u l a r b u f f e r i s used to h o l d raw data. T h i s data i s processed as i t flows i n , and o n l y t h a t data which i s of s i g n i f i c a n c e i s placed i n anotner d a t a stack f o r l a t e r use by a s t r o k e p r i m i t i v e i d e n t i f i e r . The i n p u t data can c o n t i n u o u s l y flow i n t o the c i r c u l a r b u f f e r and t h e r e i s no need t o t r a n s f e r data back and f o r t h to d i s k . Since the t a b l e t generates i n t e r r u p t s t o tae CPU at a maximum r a t e of once every 800 microseconds, tne p a r a l l e l p r o c e s s i n g task i s able to make use of the CPU time between 15 interrupts. However, since the tablet service routine has the highest pr ior i ty at a l l times, the paral le l processing task can always be temporarily interrupted to allow the CPU to serve the tablet . The preprocessing task is designed to work fast enough to ensure that no data w i l l ne missed. The execution speed of the processing task, or preprocessor, i s optimized by means of hardware-software trade-offs and computational s implif icat ion wherever possible. The tablet handling program has three major tasks: (i) I n i t i a l i z a t i o n : The tablet i s a user's device and i s unknown to the operating system. In order to use this device, the handler has the responsibili ty of notifying the operating system about the tablet so that the communication l ink between the two can be established. A l o g i c a l number i s associated with the tablet l i K e other RDOS devices. Other i n i t i a l i z a t i o n s , such as software f lags , stack pointers, buffer pointers, processing pointers e tc . , also need to be done before data i s accepted. (ii) Service Routine: Whenever interrupts are generated by the tablet , the service routine performs a l l the services reguired. The major jobs are as follow; a) To check the status of the tablet such as end of a character or user signoff from the tablet . b) To update the interrupt buffer ana decide what kind of data should be transferred to tne c ircular 16 b u f f e r f o r p r o c e s s i n g . c) To update the software f l a g s , b u f f e r p o i n t e r s , p r o c e s s i n g p o i n t e r s , e t c . The p a r a l l e l p r o c e s s i n g task i s informed of a l l t h i s i n f o r m a t i o n i n order to c a r r y out i t s task p r o p e r l y i n a m u l t i t a s k i n g environment. ( i i i ) S i g n o f f : When a user wishes r o s i g n o f f the t a b l e t , the handler ensures t h a t tne remaining p r o c e s s i n g i s completed and n o t i f i e s the iDOS t h a t t h i s user's d e v i c e s h o u l d be d e l e t e d from the o p e r a t i n g system. The h a n d l i n g r o u t i n e s e r v e s the t a o l e t i n r e a l time and cannot be i n t e r r u p t e d by other t a s k s . A f l o w c h a r t of the t a b l e t h a n d l i n g r o u t i n e i s shown i n P i g . 2.2. The l a c k of a need f o r other high data t r a n s f e r d e v i c e s makes tne above c o n c u r r e n t p r o c e s s i n g f e a s i b l e . 17 ENTER FROM RDOS I (/NiTiAUZWON) 7 SERVE INTERRUPT TABLE-T\ NO /NTBRRUPT, ? UPPA re INTERRUPT BUFFER YES REQUEST RDOS TO DISABLE FURTHER. TABLET INTERRUPT SET FLAOrS &*JariFy RECOGNIZER TO FINISH ITS JOB > * STORE £0cl £ NOTIFY PREPROCESSOR! SIGNOFF AN£> RETURN TO RDOS LV—pen down DV—pen up EOC—end of character f l a g UPPATE ALL FLAGS & POINTERS No TRANSFER C UR RENT POINT TO BUFFER NO YES TRANSFER, (CURRENT-1) pO/NT TO GuFFtfA Fig. 2.2 Flowchart for the tablet handling task. 18 CHAPTER 3 THE PREPROCESSING PART OF THE PATTERN RECOGNITION SYSTEM 2.2.1 I n t r o d u c t i o n The r e a l world i n p u t data i s a c q u i r e d *oy the data a c q u i s i t i o n system d e s c r i b e d i n Chapter 2 and c o n v e r t e d i n t o d i q i t a l data f o r the p a t t e r n r e c o q n i t i o n system. A q e n e r a l b l o c k diagram of the r e c o q n i t i o n system i s shown i n F i g . 3 . 1 . The p r e p r o c e s s o r forms the f i r s t component of the r e c o q n i t i o n system and runs c o n c u r r e n t l y with the t a b l e t h a n d l i n q r o u t i n e i n order t o minimize the data s t o r a q e requirements and e x e c u t i o n speed of the r e c o g n i z e r . A f t e r the p r e p r o c e s s i n g s t a g e , only a s m a l l f r a c t i o n of the data remains and t h i s i s the most s i g n i f i c a n t data t h a t d e s c r i b e the p a t t e r n . Based on the r e l a t i v e l y s m a l l , reuucea d a t a - s e t of the p a t t e r n , the p r i m i t i v e i d e n t i f i e r attempts t o i d e n t i f y the i n p u t s t r o k e p r i m i t i v e (subpattern) with some prot o t y p e of the r e f e r e n c e s t r o k e p r i m i t i v e s . F i n a l l y , tne s t r o k e p r i m i t i v e c l a s s i f i e r a s s i g n s the i d e n t i f i e d s t r o k e p r i m i t i v e s of a p a t t e r n t o one of the known p a t t e r n c l a s s e s or a "don't know" c l a s s . PRIMITIVE 1D£NT/F/CATIOH r PlQ-ITAL DATA PRE-PROCESSOR PATTERN REPRESENTATION L. grammatical INFERENCE JL SYNTAX ANALYSIS PRIMITIVE CLASSIFICATION btCTIOHAfiy spec)ac-table Su8PATTl PRIMITIVE T PRIM IT i vE CLASSIFICATION I I PRIMITIVE CLASSIFICATION I DECISION E> PEClSlON Fig. 3.1 The pattern recognition system block diagram. 20 l - v 2 The P r e p r o c e s s i n g Problem Due to the d i f f e r e n t eguipment and t e c o a i g u e s used i n the data a c q u i s i t i o n part of p r e v i o u s work, the p a t t e r n s were represented i n d i f f e r e n t forms, and the measurm^nts o b t a i n e d on the p a t t e r n were always of hiqh d i m e n s i o n a l i t y . However, amongst the l a r q e amount of i n p u t data only a f r a c t i o n i s c o n s i d e r e d important to the d e s c r i p t i o n of the p a t t e r n ; the r e s t are n o i s y , redundant or l e s s s i g n i f i c a n t data. I t i s d e s i r a b l e , i n both the d e c i s i o n - t h e o r e t i c and s y n t a c t i c approaches, t h a t the p a t t e r n be represented an a form as n o i s e f r e e and compact as p o s s i b l e before r e c o g n i t i o n t e c h n i q u e s are a p p l i e d [ 1 0 ] . Many p r e p r o c e s s i n g t e c h n i q u e s have been used i n e a r l i e r work and these depend e n t i r e l y on the s p e c i f i c problem and requirements under c o n s i d e r a t i o n . P r e p r o c e s s i n q t e c h n i q u e s are r e p o r t e d by Munson[32], Ullman[47], Hussain, l o u s s a i n t and Donaldson[23 ], L e v i n e [ 3 0 ] , Naqy[33], Groner [ 2 0 ] and B e r n s t e i n [ 5 ] . Each developed a technique to meet the s p e c i f i c need of a problem. I t has been r e a l i z e d t h a t the performance of the l a t e r stages of a r e c o g n i z e r , sucn as f e a t u r e e x t r a c t i o n and f e a t u r e c l a s s i f i c a t i o n , h e a v i l y depend on the data f i l t e r e d out from the p r e p r o c e s s o r . Powers[4Q] pointed out t h a t h i s high e r r o r r a t e r e s u l t e d l a r g e l y from the improper segmentation of the data i n t o component a r c s i n the p r e p r o c e s s i n g s t a g e . The p r e p r o c e s s i n g a l g o r i t h m presented i n s e c t i o n 3.3 i s 21 focused on handprinted c h a r a c t e r s and on the o n - l i n e data p r o c e s s i n g c r i t e r i a . However, a few parameters i n the p r e p r o c e s s i n g can be c o n v e n i e n t l y a d j u s t e d to d e a l witn other two dimensional p a t t e r n s of any nature, such as c h a r a c t e r s of extremely l a r g e s i z e or other g r a p h i c a l p i c t u r e s . 3.3 Design of the P r e p r o c e s s i n g Algorithm The p r e p r o c e s s i n g a l g o r i t h m i s c o n c e p t u a l l y s i m i l a r t o the method proposed by Heumann and Witkam [ 4 1 J f o r the d i s p l a y of curves on a CRT by o p t i m i z i n g curve segmentation. T h e i r method aimed at f a i t h f u l l y d i s p l a y i n g tne o r i g i n a l c urves with c o n s i d e r a b l e data r e d u c t i o n i n the d i s p l a y f i l e . However, i n a p a t t e r n r e c o g n i t i o n problem, the g o a l i s to c l a s s i f y a p a t t e r n i n t o one of the p r e s p e c i f i e d p a t t e r n c l a s s e s r a t h e r than to reproduce the o r i g i n a l c u r v e s . Thus curve segmentation and data r e d u c t i o n can be f u r t h e r o p t i m i z e d as long as the data r e t a i n e d w i l l enable the r e c o g n i t i o n task to be c a r r i e d out s u c c e s s f u l l y . S i n c e we have the time sequence of the i n p u t d a t a , i t i s p o s s i b l e to t r a c e the path of pen movement. The data r e d u c t i o n concept used here i s i l l u s t r a t e d i n F i q . 3.2. F i r s t , the i n i t i a l tanqent l i n e of the l i n e drawinq i s found. Two p a r a l l e l d o t t e d l i n e s on each s i d e of the tanqent l i n e are drawn. These two dotted l i n e s are e q u i d i s t a n t from the 22 Fig. 3.2 Curve Segmentation Diagram. tangent l i n e of the l i n e drawing, l e t these dotted l i n e s be c a l l e d guide l i n e s . When the two guide l i n e s are extended i n the d i r e c t i o n of the tangent l i n e , one w i l l i n t e r s e c t the curve which i s the t r u e t r a c k of the pen movement. Tne po i n t of the i n t e r s e c t i o n i s t r e a t e d as a s i g n i f i c a n t p o i n t d e s c r i b i n g the pen movement. Other p o i n t s between tne tangent p o i n t and the i n t e r s e c t i o n p o i n t are i g n o r e d . The i n t e r s e c t i o n p o i n t i s now t r e a t e d as the new tangent p o i n t , new guide l i n e s are drawn a c c o r d i n g l y and the above process i s repeated u n t i l the t e r m i n a l p o i n t of the curve i s reached. T h i s technique y i e l d s very few p o i n t s along a s t r a i g h t l i n e p o r t i o n while r e t a i n i n g more p o i n t s along a c u r v i l i n e a r p o r t i o n . Thus the data r e t a i n e d i s p r o p o r t i o n a l t o the c u r v a t u r e of the l i n e and so data r e d u c t i o n i s o p t i m i z e d . At the same time, the l i n e drawing d e s c r i p t i o n i s p r e s e r v e d . T h e o r e t i c a l l y , i f adj a c e n t p a i r s of c o - o r d i n a t e s are reasonably c l o s e , the i n i t i a l tangent l i n e may ue c a l c u l a t e d 23 by t a k i n g the s l o p e o f these two p o i n t s . The d i s t a n c e of each s u c c e s s i v e p o i n t t o the tangent l i n e i s c a l c u l a t e d u n t i l a p o i n t i s found to be l o c a t e d o u t s i d e the r e g i o n mounded by the guide l i n e s . Then the l a s t p o i n t t h a t f a l l s between the guide l i n e s i s kept and a new tangent l i n e determined. The COMPUTER t a b l e t has a 0.28 mm r a s t e r u n i t ; thus, tne d i s t a n c e between each a d j a c e n t p a i r of c o - o r d i n a t e s w i t h m the same l i n e drawing i s e i t h e r 0.28 mm or 0.40 mm, and i t s d i r e c t i o n i s one of the e i g h t p r i n c i p a l d i r e c t i o n s . That i s , i f 8 i s the d i r e c t i o n i n degrees, and n i s an i n t e g e r between 0 and 7, then, 9 = 45°*n The path of a l i n e drawing ob t a i n e d oy j o i n i n g the p o s i t i o n a l c o - o r d i n a t e s resembles a sawtooth and r e s u l t s from q u a n t i z a t i o n of the pen p o s i t i o n . Hence, the s l o p e at a p a r t i c u l a r p o i n t may not be the true d i r e c t i o n of the pen movement a t t h a t i n s t a n t . To overcome t h i s prooieia, the tangent l i n e i s measured between the i n i t i a l point, and the p o i n t a few r a s t e r u n i t s beyond. C o - o r d i n a t e s a r e read whenever t h e r e i s a change i n pen p o s i t i o n , p r o v i d e d t h a t s u f f i c i e n t pen pressure i s a p p l i e d . Let p be the p o i n t a t the j t h such p o s i t i o n a l change and T be the d i s t a n c e from the guide l i n e to the tangent l i n e . Then the i n i t i a l s l o p e i s measured between the j t h and (j+k+ 1)th p o i n t s , where k i s an i n t e g e r g r e a t e r than or egual to zero. The d i s t a n c e between the j t h and (j+k+1)th p o i n t s should 24 be at l e a s t 3 r a s t e r u n i t s . In cases where tne d i s t a n c e of the two p o i n t s i s too s m a l l , t h a t i s 3 r a s t e r u n i t s or l e s s , t o be used f o r meaningful s l o p e c a l c u l a t i o n , s u c c e s s i v e p o i n t s are checked f o r use i n the s l o p e c a l c u l a t i o n . In order t o ensure that the l i n e drawing between the (3 + 1)t,h and (j + k) t h p o i n t s i s c l o s e l y f o l l o w e u by the above tangent l i n e , each p o i n t , s t a r t i n g from the ( 1 + 1 )th , c o u l d be checked to see i f i t i s l o c a t e d i n the t o l e r a n c e zone. Then i f any p o i n t between (j + 1)th and (j+k)th, i n c l u s i v e , i s found to be l o c a t e d o u t s i d e the t o l e r a n c e zone, the p r e v i o u s l y e s t a b l i s h e d s l o p e would be c a n c e l l e d and a new s l o p e measured between the j t h p o i n t and whichever p o i n t i s f i r s t found to be l o c a t e d o u t s i d e the t o l e r a n c e zone. However, p r o c e s s i n g each raw datum i s very c o s t l y i n terms of CPU time which might otherwise be used f o r other tasics. I t was observed i n experiments, t h a t f o r a p a r t i c u l a r c h a r a c t e r s i z e , a c a r e f u l s e l e c t i o n of the value f o r k r e s u l t e d i n the k p o i n t s between the j t h and (j+k+1)th p o i n t s f a l l i n g w i t h i n the t o l e r a n c e zone. Such a s e l e c t i o n y i e l d s a s i g n i f i c a n t r e d u c t i o n i n the time f o r p r o c e s s i n g the l i n e drawing. To f u r t h e r o p t i m i z e the p r o c e s s i n g speed, another s t e p was undertaken. A f t e r the s l o p e between the j t h and (j+k+ 1)th p o i n t s i s v a l i d l y e s t a b l i s h e d , t h e next s e g u e n t i a l p o i n t , (j+k+2)th , i s at most 0.40 mm away and the (j+uk+1)£h i s a t most nx0.40 mm away from the tangent l i n e . Hence, i n s t e a d of p r o c e s s i n g each s u c c e s s i v e p o i n t a f t e r the (j+k+1)th p o i n t , a 25 measurement i s made d i r e c t l y on the ( j + 2 k + 1)th p o i n t . I f the (j + 2k+1)th point i s l o c a t e d w i t h i n the t o l e r a n c e zone, then i t i s reasonable t o assume t h a t the p o i n t s from the ( j + k + 2)th to (j+2k)th are a l s o l o c a t e d w i t h i n the t o l e r a n c e zone. L i k e w i s e , s u c c e s s i v e measurements can oe made on the. (j+nk+1)th p o i n t , where n i s g r e a t e r or egual to 2. I f t h i s t e s t f a i l s , then the (j+k+1)th p o i n t i s taken and the s l o p e c a l c u l a t i o n i s r e s t a r t e d from t h a t p o i n t . When the end of a l i n e drawing becomes known to the p r e p r o c e s s o r , the d i s t a n c e of the l a s t e x t r a c t e d s i g n i f i c a n t p o i n t and the end p o i n t i s measured to determine i f the endpoint should be saved. The reason f o r t h i s i s t n a t i n many cas e s , people c r e a t e a hook at the end of a l i n e drawing which causes a very d i f f i c u l t s i t u a t i o n f o r tne r e c o g n i t i o n t a s k . The amount of raw data t h a t r e p r e s e n t s a c h a r a c t e r depends on the speed and s t e a d i n e s s of the h a n d w r i t i n g process as w e l l as on the c h a r a c t e r s i z e , which can be any s i z e on the t a b l e t s u r f a c e . However, i n p a t t e r n r e c o g n i t i o n , approximately the same amount of data i s needed t o d e s c r i b e a p r e s p e c i f i e d p a t t e r n r e g a r d l e s s of i t s s i z e and tne speed of i t s f o r m a t i o n . Thus, i t i s d e s i r a b l e t o o b t a i n more data r e d u c t i o n i n the case of l a r g e s i z e c h a r a c t e r s than those of s m a l l e r s i z e s . Two parameters, namely k and T, can be used to a d j u s t the amount of data r e d u c t i o n , where k i s the next kth p o i n t being c o n s i d e r e d f o r measurement and T i s the width o f 26 the r e g i o n bounded by the tangent l i n e and the guide l i n e . The l i n e drawings t h a t c o n s t i t u t e a c h a r a c t e r can be d i v i d e d i n t o two g e n e r a l c a t e g o r i e s : namely, s t r a i q n t l i n e s and curves. For a p e r c e p t u a l l y s t r a i g h t l i n e , most of the raw. data w i l l be l o c a t e d c l o s e to the tangent l m e ; thus, i t i s d e s i r a b l e to have a value of T such t h a t a l l tne raw data be bounded by the two guide l i n e s and the f e a t u r e of the s t r a i g h t l i n e can then be e x t r a c t e d without being a f f e c t e d by q u a n t i z a t i o n e f f e c t s . I f a p e r c e p t u a l l y s t r a i g n t l i n e i s d i v i d e d i n t o a number of segments,the s l o p e measurements of those segments are q u i t e c l o s e . Thus, a l a r q e value f o r Jc has almost no e f f e c t on s t r a i q h t l i n e f e a t u r e e x t r a c t i o n . However, i f T i s too l a r q e , the l o c a l p r o p e r t i e s of a curve miqht be l o s t , s i n c e there i s no way to d i s t i n g u i s h a s t r a i q h t l i n e from a curve at t h i s staqe- T h i s matter e f f e c t i s i l l u s t r a t e d i n F i q - 3.3. l o s t corner p r o p e r t y p o s s i b l e l i n e approximation F i g . 3-3 Loss of l o c a l property of a curve due to a l a r g e T. In the case of c u r v e s , the value of k neeas to be p r o p e r l y s e l e c t e d so that the s l o p e measurements are always c l o s e to t h a t of the tangent l i n e s r a t h e r than t n a t of the chords. I t i s observed t h a t the r a t e of change of c u r v a t u r e of the curves i n l a r g e s i z e c h a r a c t e r s i s l e s s than t h a t of s m a l l s i z e c h a r a c t e r s . Consider the two i d e n t i c a l c n a r a c t e r s 'C* shown i n F i g . 3.4. Fig. 3-4 Comparison of Rate of Curvature Change i n Two Different Size Characters. They d i f f e r o n l y i n s i z e ; thus the raw data used to d e s c r i b e the two are d i f f e r e n t , yet the amount of e s s e n t i a l data r e g u i r e d to d e s c r i b e such p a t t e r n s i s the same s i n c e they are of the same c l a s s . However, i f the same value or k i s used to process the two 'C's, then the l a r g e 'C w i l l y i e l d more segments than the s m a l l *C'. L e t the slope measurement of the i t h segment i n . the l a r g e 'C be m| and the j t h segment i n s m a l l ' c ' oe nj, then 28 the a b s o l u t e r a t e s of change of c u r v a t u r e are approximately ^ 3 = , n i - n H where i s the r a t e of change i n c u r v a t u r e f o r l a r g e » C r and 4n f o r the s m a l l 'C 1. For two c o r r e s p o n d i n g segments o f the two 'C*s, i t i s e v i d e n t t h a t 4mj > 4nj In order t o i n c r e a s e the p r o c e s s i n g speed f o r t n e l a r g e •C 1, a l a r g e r value can be s e l e c t e d f o r k so t h a t the number of segments r e s u l t i n g i n the l a r g e * C* w i l l be a p p roximately the same as f o r t h e s m a l l 'C', p r o v i d e d t h a t the number o f segments i s adeguate to d e s c r i b e the p a t t e r n . In doing so t h e o v e r a l l computations saved are s i g n i f i c a n t . T h e r e f o r e , the optimum value t o be s e l e c t e d f o r the parameters T and k depend on s p e c i f i c p a t t e r n c l a s s , i t s s i z e and i t s r e c o g n i t i o n requirements. F o r handprinted c h a r a c t e r s , T and k are a t p r e s e n t p r e s e t t o 3 and 9, r e s p e c t i v e l y . The experiments d e s c r i b e d l a t e r show t h a t such a c h o i c e y i e l d s s a t i s f a c t o r y r e s u l t s f o r c h a r a c t e r s of s i z e s from 1/8 i n c h t o 3 i n c h e s t a l l . However, f o r the above v a l u e s , tne o p t i m a l performance i n terms of r e c o q n i t i o n r a t e i s round f o r c h a r a c t e r s of s i z e s from 3/8 to 3/4 i n c h h i g n . The two parameters can a l s o be s e t t o o t h e r v a l u e s t o achieve o p t i m a l performance on any character, s i z e s or p a t t e r n s of other shapes. 29 3.4 A l g o r i t h m S i m p l i f i c a t i o n E x e c u t i o n speed of v a r i o u s t a s k s i s a major concern i n a r e a l - t i m e environment. Hence, r e d u c t i o n or s r m p l i c a t l o n of any computations r e q u i r e d i s h e l p f u l or even necessary under c e r t a i n c i r c u m s t a n c e s . In a d d i t i o n to the use of s p e c i a l t e c h n i q u e s t o speed up the p r e p r o c e s s i n q t a s k , s i m p l i f i c a t i o n s i n computation are a l s o used to s u i t our r e a l - t i m e minicomputer environment. u=j+nk+l P i g - 3-5 C a l c u l a t i o n f o r d i s t a n c e d. 30 The method f o r c a l c u l a t i n g d, the d i s t a n c e of a p o i n t from the tanqent l i n e , i s based on that of Heumann and Hitkam[41 ]. For our case, a p o i n t i s l o c a t e d o u t s i d e the t o l e r a n c e zone i f d > T . To reduce the computations r e q u i r e d f o r c a l c u l a t i n q the d i s t a n c e , the f o l l o w i n g approximations are used. From F i g . 3.5, d can be expressed as : d = I ( x u-Y u«)•cos 6| where Yu' i s the Y c o - o r d i n a t e of the tanqent l i n e a t X=X U. Throuqh geometric r e l a t i o n s , Ya' can be expressed as; x i and vi + k + i ~ x j cos 6 L e t 4X = Xj + k+i-Xj and then, we have d = I A* = l [ — •(X u-X)-(Y l 4-Yj ) ]• AX 3 1 / X 2 + / Y 2 = < By using a Chebyshev approximation 0.96»|/JX| + 0.398*|4YJ ; 0.96»MY|+0,398«|/1X| ; IZXKIAYI which results a maximum r e l a t i v e error of 4 A, and l e t t i n g I 4 Z 1 J = U V / t f l * 1 M Z 2 | = MX/AY I < 1 I /IX I d = |[ |^1 | • (Xu-X; ) - (Yu-Y-. ) ]• 1 | J 0.96*1/4X1 + 0.396*|/1Y || Normally, d i s calculated and checked f o r d > T The check then becomes I AX | l[ I 4 Z 1 ] • (Xu-X- )-(Y u-Y) ]« 1 > T | 0 0.96«|/lX| + 0.398*|4i|l I J 4 Z 1 I • (X u-Xj ) - (Y u-Yj ) | > 0/MX) «T« (0.96-l/X| + 0.398«|4Y|) | M Z 1 |- (X u-Xj ) "(Yu-Yj ) | > 0.96»T+0.398T*| (/Y//1X) 1 Let C1=0.96T and C2=0.398T. Since T i s constant for a s p e c i f i c problem, these two constants need only be calcula t e d once at the beginning ' of the program. Thus, the distance check s i m p l i f i e s to: | | 2 5 Z 1 | » { X U - X J ) - ( Y U - Y J ) | > C 1 + C 2 - U Z 1 I ; i f (/Ix//iX)<1 or | (X u-Xj ) - | ^ 2 | • (Y u-Yj ) | >' C 1 + C 2 * M Z 2 | ; i f (AX/AZ) > 1 32 'RECOQNITMI F/N£> SLOPE YES PEN Up > NO CALCULATE Pi STANCE d No YES STORS S/G-NlFICAMr PQ i NT yes ± STROKE—0\ yes. STORE END POINT 1 YES STORE FtRST pO /NT OF STROKE RESET COVtircq TO k> REQUEST aSFX\ TO REWRITE RETURN TO HOUSE /KEEPING F i g . 3.6 Flowchart for the preprocessor. ^UTIHE, 33 The r i g h t hand s i d e of these i n e q u a l i t i e s need to be c a l c u l a t e d only once f o r each new tangent l i n e . The above f o r m u l a s , used f o r measuring d i s t a n c e , are q u i t e simple i n terms of computations r e g u i r e d and so are very important to the o n - l i n e data processing d i s c u s s e d i n s e c t i o n 3.5. F i g . 3.6 prese n t s a simple f l o w c h a r t wnich shows the a l g o r i t h m d i s c u s s e d above. 3.5 O n - l i n e Data P r o c e s s i n g There are many d i f f e r e n t ways o f approaching c h a r a c t e r r e c o g n i t i o n based on r e a l - t i m e d a t a . For example, i l i l l e r [ 3 1 ] f o cused on c h a r a c t e r s 1/4 i n c h h i g h . His r e c o g n i z e r accepted a new c o - o r d i n a t e whenever the change i n e i t h e r X or I d i r e c t i o n was 0.03 i n c h . Other p r o c e s s i n g had to wait u n t i l the completion of the symbol because the number of p o i n t s t h a t r e p r e s e n t the curve had to be counted i n order t h a t s i x evenly d i v i d e d chords might be c o n s t r u c t e d . Powers£40] r e a l i z e d t h a t data may be processed while i t i s f l o w i n g i n t o the computer. The l a t t e r approach i s taken i n t h i s t h e s i s . S i n c e data i s generated n e i t h e r randomly nor a t a f i x e d r a t e , a l l data has to be checked f o r s i g n i f i c a n c e i n d e s c r i b i n g a l i n e . I f each such check takes a c o n s i d e r a b l e amount of time, the o v e r a l l time i n v o l v e d w i l l be s i g n i f i c a n t . In our d e s i g n , some data i s t e m p o r a r i l y p l a c e d i n a s m a l l c i r c u l a r b u f f e r i n r e a l time. T h e r e f o r e , t o a v o i d l o s s of i n p u t d a t a , the p r o c e s s i n g r a t e of the c o n c u r r e n t 34 p r e p r o c e s s o r must exceed the average i n p u t r a t e . To minimize the time r e g u i r e d i n p r e p r o c e s s i n g , the f o l l o w i n g s t e p s were taken : 1. Choice of a p r e p r o c e s s i n g tecnnique wnicn r e g u i r e s minimal computations. 2. Programming the p r e p r o c e s s i n g r o u t i n e i n macaine l e v e l language so t h a t the computer can be • manipulated to work i n the most e f f i c i e n t way f o r t h i s s p e c i f i c problem. 3. Development of software r o u t i n e s t o perform t a s k s which are normally done by hardware, but i n a l o n g e r time. F l o a t i n g p o i n t a r i t h m e t i c i s handled oy s o f t w a r e i n f i x e d p o i n t a r i t h m e t i c . Some m u l t i p l y and d i v i d e o p e r a t i o n s are a l s o manipulated by software t o i n c r e a s e the e x e c u t i o n speed. In a m u l t i - t a s k , p a r a l l e l p r o c e s s i n g environment, the s u p e r v i s o r r o u t i n e has the important r o l e of m a i n t a i n i n g the proper e x e c u t i o n of each task and the communication between t a s k s . For our problem, t h e r e are o n l y two tasks working i n p a r a l l e l . S i m p l i f i e d f l o w c h a r t s of these t a s k s are shown i n F i g . 3.7, but the communication between tne t a s k s as expressed i n terms of hardware and software s i g n a l s are not shown. 35 fr-i INCREMENT PROCESS INC POINTER PROCESS tNG-DATA RETURN TO RbCS F i g . 3.7 Flowchart f o r the s u p e r v i s o r task 36 CHAPTER 4 STROKE PRIMITIVE IDENTIFICATION 4.1 I n t r o d u c t i o n In the s y n t a c t i c approach t o p a t t e r n r e c o g n i t i o n , a co m p l i c a t e d p a t t e r n may be d e s c r i b e d i n terms of a composition of l e s s c o m p licated subpatterns and each s u b p a t t e r n can agai n be d e s c r i b e d i n terms of s i m p l e r s u b p a t t e r n s u n t i l the s i m p l e s t s u b p a t t e r n , or p r i m i t i v e , i s reached. The use of s y n t a c t i c - a i d e d or l i n g u i s t i c methods i n p a t t e r n r e c o g n i t i o n are d e s c r i b e d by Narasimnan et a l £34] and Uhr £ 4 6 ] . Such an approach i s very powerful when the p a t t e r n d e a l t with c o n t a i n s r i c h s t r u c t u r a l i n f o r m a t i o n . F o r handprinted c h a r a c t e r s , s t r u c t u r a l i n f o r m a t i o n p l a y s an important r o l e i n c h a r a c t e r i z i n g the p a t t e r n s and i s u s u a l l y i g n o r e d i n the d e c i s i o n - t h e o r e t i c approach where the two di m e n s i o n a l p i c t u r e s are t r e a t e d as u n s t r u c t u r e d e n t i t i e s . U n l i k e t y p e p r i n t e d c h a r a c t e r s , handprinted syuiools t h a t i n d i c a t e the same c h a r a c t e r can vary widely with r e s p e c t to t h e i r s i z e s , shapes and s t r u c t u r e s , depending on who p r i n t e d them and when. T h e r e f o r e , a s e t of s c a l a r measurements on a p a r t i c u l a r c h a r a c t e r seems inadequate t o r r e c o g n i t i o n . I t i s d e s i r a b l e t h a t the r e c o g n i t i o n scheme i n t r o d u c e d w i l l be a b l e to cope i n t e l l i g e n t l y with r e a l - w o r l d phenomena. In a d d i t i o n to the s t a t i c i n f o r m a t i o n t h a t d e s c r i b e s a c h a r a c t e r a f t e r i t i s formed, the dynamic i n f o r m a t i o n t h a t d e s c r i b e s the process of c h a r a c t e r formation i s a l s o known i n a r e a l - t i m e p r i n t i n g environment. U n l i k e t y p e p r i n t e d c h a r a c t e r s , handprinted c h a r a c t e r s are formed i n terms of a f i n i t e s e t of s t r o k e p a t t e r n s i n a s p e c i f i c time seguence as w e l l as i n terms of t h e i r geometric r e l a t i o n s h i p s . Our r e a l -time approach takes advantage of these a t t r i b u t e s . A f t e r a c h a r a c t e r i s formed, i t i s very d i f r i c u l t to s e p a r a t e the s t r o k e s (from pen down to pen up again) t h a t were used t o form the c h a r a c t e r . However, i n r e a l - t i m e measurement, s t r o k e s e p a r a t i o n i s not d i f f i c u l t even i f there i s c o n n e c t i v i t y between d i f f e r e n t s t r o k e s because the pen pressure i s sensed by computer. The time h i s t o r y of c h a r a c t e r f o r m a t i o n i s a l s o recorded while i t i s being formed and i n t h i s t h e s i s , t h i s i n f o r m a t i o n i s u t i l i z e d to improve r e c o g n i t i o n performance. fiegardless of the wide v a r i a t i o n s i n a s p e c i f i c s t r o k e p a t t e r n , such as the C-curves shown i n F i g . 4 . 1 , tney are a l l r e c o g n i z a b l e by humans. While c o n s t r u c t i n g a c u r v e , the drawer has a curve p a t t e r n i n mind such t h a t a f t e r i t i s formed, i t w i l l be understood to other viewers. A l l the in-curves shown i n F i g . 4.1 are meant t o approximate s e m i c i r c l e s with openings a t t h e i r r i g h t . Thus the d e s c r i p t i o n s of the curve p a t t e r n s are unique and should be c l a s s i f i e d i n the same p a t t e r n c l a s s . 38 c c c c C F i g . 4.1 The charac t e r 'C* i n d i f f e r e n t shapes. The s y n t a c t i c approach d e s c r i b e s a c h a r a c t e r rn terms of s t r o k e subpatterns and each s t r o k e p a t t e r n i s d e s c r i b e d i n terms of segment p r i m i t i v e s . An example i s shown i n F i g . 4.2. \ CHARACTER LEVEL II RELATION OPERATION STROKE PRIMITIVES r, E T O W LEVEL I COMPOSITE OPERATION CONCATENATION r, SLOPE CODE SEQUENCE F i g . 4.2 S t r u c t u r a l d e s c r i p t i o n of the ch a r a c t e r 'R1. Let an elementary s t r o k e p r i m i t i v e . Then s t r o k e p a t t e r n a seguence of c l a s s s t r o d e ue c a l l e d a p r i m i t i v e s d e s c r i b e s a c h a r a c t e r and the r e c o g n i t i o n problem becomes s i m p l e r . Such an approach can, through many l e v e l s of p r i m i t i v e e x t r a c t i o n , d e s c r i b e a complicated p a t t e r n i n terms of a composition o f a few i d e n t i f i e d s ubpatterns- In our problem, the r e c o g n i t i o n process uses two sucn r e v e l s - F i r s t , a s l o p e seguence i s processed and i d e n t i f i e d as one of the p r e s p e c i f i e d s t r o k e p r i m i t i v e s . Second, the c n a r a c t e r i s c l a s s i f i e d on the b a s i s of the s t r o k e p r i m i t i v e s e x t r a c t e d . F i g . 4.2 i n d i c a t e s t h i s approach. The f l o w c h a r t of F i g - 4.3 shows the process of s t r o k e p r i m i t i v e i d e n t i f i c a t i o n which i s d e s c r i b e d i n more d e t a i l i n the f o l l o w i n g two s e c t i o n s . 4.2 P a t t e r n Representat ion 4._2.. 1, Basic Feature C l a s s i f i c a t i o n As d i s c u s s e d i n s e c t i o n 4.1, s e p a r a t i o n of one s t r o k e from another i s e a s i l y d e t e c t e d i n r e a l - t i m e h a n d p r i n t i n g because a s t r o k e i s d e s c r i b e d from the pen-down i n s t a n t u n t i l the next pen-up i n s t a n t . The presence of pen pressure ( e q u i v a l e n t t o pen-down) i s checked when the pen i s w i t h i n 1/4 i n c h from the s u r f a c e of the t a b l e t . Therefore,- the number of s t r o k e s t h a t formed the c h a r a c t e r i s p r e c i s e l y known. For E n g l i s h upper case handprinted c h a r a c t e r s , the s t r o k e s used to form the 26 c h a r a c t e r s can be d i v i d e d i n t o two g e n e r a l c a t e g o r i e s : namely, s t r a i g h t l i n e s and c u r v e s . FROM PREPROCESSOR A 40 CLASS I CLASSJ QUANTIZATION" SLOPE COOE SEQUENCE CONSTRUCTION 1 FORTH £ PROCES > R i>ATA SING QUAMT 1 ZATI ON NOISY SLOPE CODE SEQUENCE ! PROCESSING S W T A X A N A t- ys Is YES ( CHARAC1ER\ REJECTED J . •" * STROKE p a r i tTlVE ASSi^NNBNT f STROKE PATTERN CLASSIPfCAT/O" P i g . 4.3 Flowchart "for the strok e p r i m i t i v e i d e n t i f i c a t i o n process. 41 For example, E, F, K are formed s o l e l y by s t r a i g h t l i n e s t r o k e s , while C, S, 0 are formed s o l e l y by c u r v e s . Some c h a r a c t e r s , such as B, 0, P and R, are formed ny a combination of c u r v e s and s t r a i g h t l i n e s . The f e a t u r e s of a curve and t h a t of a s t r a i g h t l i n e are g u i t e d i f f e r e n t and can be separated i n the e a r l y stage of the r e c o g n i t i o n . An a l g o r i t h m t a i l o r e d to these s p e c i f i c category requirements can thus be employed. The p r i n c i p l e used to d i s t i n q u i s h s t r a i g h t x i n e s from curves i s b a s i c a l l y the same as t h a t used i n the p r e p r o c e s s i n g . At the output of the p r e p r o c e s s i n g s t a g e , the data t h a t d e s c r i b e s a s t r o k e p a t t e r n i s compact yet s i g n i f i c a n t . The d i s t a n c e s between output p o i n t s a r e , however, f a r t h e r a p a r t . The p r e p r o c e s s i n g a l g o r i t h m i s m o d i f i e d i n the b a s i c f e a t u r e c l a s s i f i c a t i o n r o u t i n e so that F i g . 4.4 B a s i c f e a t u r e s e p a r a t i o n diagram. 42 only one tangent l i n e i s c a l c u l a t e d by j o i n i n g the i n i t i a l and the end p o i n t s of a s t r o k e . The distance; of the guide l i n e s from the tangent l i n e used here i s l a r g e r than i n the p r e p r o c e s s i n g case. Parameter k, d e f i n e d i n the p r e p r o c e s s i n g case, i s not used here and every p o i n t i s checKed s i n c e they are a l l s i g n i f i c a n t p o i n t s . F i g . 4.4 demonstrates the method. For a p e r c e p t u a l l y s t r a i g h t l i n e , a l l tne p o i n t s are l o c a t e d c l o s e to the tangent l i n e because the s l o p e change between segments i s r e l a t i v e l y s m a l l ; hence, almost any slope segment can approximate the s l o p e s of the other segments. On the other hand, f o r a c u r v e , some p o i n t s are l o c a t e d o u t s i d e the bounded r e g i o n because the s l o p e s of a curve are r a p i d l y changing and t h e r e i s no s i n g l e tangent l i n e t h a t can approximate a l l the s l o p e s t h a t c h a r a c t e r i z e the c u r v e . 4 i 2 i 2 S t r a i g h t Line R e p r e s e n t a t i o n The number of p o i n t s t h a t are output from the p r e p r o c e s s i n g stage to d e s c r i b e the s t r a i g h t l i n e v a r i e s with d i f f e r e n t s i z e s of c h a r a c t e r s and the s t r a i g h t n e s s of the s t r a i g h t l i n e i t s e l f . For a very s t r a i g h t l i n e , o n l y two p o i n t s , namely the i n i t i a l and the end p o i n t s , are f i l t e r e d through the p r e p r o c e s s o r . The two parameters, k and T, i n the p r e p r o c e s s i n g and the s i n g l e parameter, T xn the b a s i c f e a t u r e c l a s s i f i c a t i o n r o u t i n e can be tuned to y i e l d o p t i m a l raw data r e d u c t i o n on c h a r a c t e r s of p a r t i c u l a r s i z e s . With op t i m a l r e d u c t i o n , a s t r a i g h t l i n e s t r o k e of a c h a r a c t e r o f intended s i z e w i l l be d e s c r i b e d by only two p o i n t s even i f the s t r a i g h t l i n e does not look very s t r a i g h t . But i f c h a r a c t e r s are not of intended s i z e s or because of d i s t o r t i o n i n the handwriting, then more than two p o i n t s are output t o d e s c r i b e the w r i t e r ' s intended ' s t r a i g h t l i n e s ' . While they may not be g e o m e t r i c a l l y s t r a i g h t l i n e s , they are i n t e r p r e t e d as s t r a i g h t l i n e s i n the con t e x t of a symbol by humans. T h e r e f o r e , r e c o g n i t i o n of a s t r a i g h t l i n e s t r o k e s h o u l d be based on human p e r c e p t i o n which u s u a l l y t o l e r a t e s some d i s t o r t i o n s . From the time h i s t o r y of the pen movement, the s t a r t i n g and the ending p o i n t s of the s t r o k e and the d i r e c t i o n i t t r a v e l s are known. For s t r a i g h t l i n e s t h a t a re d e s c r i b e d by onl y two p o i n t s , the p r i m i t i v e i d e n t i f i c a t i o n i s c l e a r l y very s i m p l e . For s t r a i g h t l i n e s t h a t are d e s c r i b e d i n t h r e e or more p o i n t s , the p r i m i t i v e i d e n t i f i c a t i o n t e c h n i g u e employed i s t o s e l e c t only the two p o i n t s t h a t nest d e s c r i b e the s t r a i g h t l i n e r e p r e s e n t e d . In most cas e s , tne i n i t i a l and end p o i n t s are chosen s i n c e the remaining points are u s u a l l y l o c a t e d c l o s e to the tangent l i n e as e x p l a i n e d i n s e c t i o n 4.2 . 1 . The d i r e c t i o n s of s t r a i g h t l i n e s are g u a n t i z e d i n t o s l o p e codes as d i s c u s s e d i n the s e c t i o n to f o l l o w . Thus i f S denotes a s t r o k e , then a s t r a i g h t l i n e s t r o x e e v e n t u a l l y becomes rep r e s e n t e d by a s i n g l e s l o p e code, g, t h a t i s , S = (g ) There are e i g h t s l o p e codes and thus e i g n t s t r a i g h t l i n e 44 p r i m i t i v e s . 4^2^.3 Slope Q u a n t i z a t i o n A coding approach to p a t t e r n r e c o g n i t i o n nas oeen widely used by many r e s e a r c h e r s [16,35,5,31,39]. Amongst the p r e v i o u s r e s e a r c h , a u n i f o r m l y g u a n t i z e d o c t a l plane has been c o n s i d e r e d the most f a v o r a b l e . P i g . 4.5 shows two g e n e r a l ways of un i f o r m l y p a r t i t i o n i n g the two d i m e n s i o n a l plane. Both d i v i d e the plane i n t o e i g h t e g u a l l y spaced r e g i o n s with 45» i n each r e g i o n . The only d i f f e r e n c e i s t h a t one uses the c o - o r d i n a t e axes as the c e n t r a l l i n e of the r e g i o n , while the other uses the axes as r e g i o n boundaries. (a) (b) F i g . 4.5 Two commonly seen q u a n t i z a t i o n planes. 45 In c h a r a c t e r r e c o g n i t i o n , e i g h t guanta are c o n s i d e r e d t o be s a t i s f a c t o r y i n d i s c r i m i n a t i n g pen d i r e c t i o n s . The purpose of s t r o k e p r i m i t i v e i d e n t i f i c a t i o n i s t o e x t r a c t unigue p r i m i t i v e r e p r e s e n t a t i o n s . T n i s o o j e c t i v e i s achieved by using a d i f f e r e n t s l o p e g u a n t i z a t i o u scheme than the above. Consider the symbols shown i n F i g . 4.6. A l l the symbols are e a s i l y d i s t i n g u i s h e d by human beings, p a r t l y by each i n d i v i d u a l s l o p e and p a r t l y by the geometric r e l a t i o n s h i p s among them. C o n s i d e r i n g the f i r s t s t r o k e of the t h r e e symbols, the sl o p e code r A 1 . i n F i g . 4.6(b) i s very l i k e l y to be the same as r H i i n F i g . 4.6(c), but d i f f e r e n t from r A l i n F i g . 4.6(a). From human p e r c e p t i o n , r f l i and r A l>. s h o u l d be c o n s i d e r e d to be the same s t r o k e p r i m i t i v e s and r e c e i v e the same s l o p e code. However, i n machine r e c o g n i t i o n , the measurements of r/u« and r H | are l i k e l y to be d e s c r i b e d by the same s l o p e codes. To e x t r a c t an unigue s t r o k e p r i m i t i v e based on s c a l a r measurements becomes very d i f f i c u l t . Pig. 3-13 Stroke primitive comparison. 4 6 In our problem, i t i s d e s i r a b l e t h a t r A i , oe i n c l u d e d i n the same quantized r e g i o n as that of r^, , and that r H 1 be l o c a t e d i n another quanti z e d r e g i o n . A non-uniform q u a n t i z a t i o n plane was designed t o meet txiis k i n d o f requirement. A diagram of the new s l o p e g u a n t i z a t i o n i s shown; i n F i g . 4.7. The two parameters, 9i , and 6 Z can be a d j u s t e d F i g . 4.7 The new q u a n t i z a t i o n plane. so t h a t r e g i o n s 1,3,5,7 w i l l be l a r g e r than i n the uniform case. r A 1 and r A i , then can both be i n c l u d e d i n the same r e g i o n . At present, the boundaries are pr e s e t to 20° and 15° about the X and Y axes, r e s p e c t i v e l y . Such a d e s i g n can c o r r e c t l y i d e n t i f y the s t r o k e p r i m i t i v e s of E n g l i s h c h a r a c t e r s which are w r i t t e n improperly, such as s l a n t e d and d i s t o r t e d c h a r a c t e r s , but which are recognizanxe by human bei n g s . However, the above method sometimes w i l r f a i l t o i d e n t i f y the c o r r e c t s t r o k e p r i m i t i v e . The re m e d i a l method d i s c u s s e d i n s e c t i o n 5.3 i s then a p p l i e d to y r e l d a f i n a l d e c i s i o n . When a segment s l o p e , or the s t r o k e s l o p e i n the case of a s t r a i g h t l i n e , i s c a l c u l a t e d , a s l o p e code, g, w i l l be as s i g n e d to i t u s i n g the new q u a n t i z a t i o n plane, i'he s l o p e code, g , i s d e f i n e d as q € Q and Q i s d e f i n e d as the s e t Q = (0,1,2,3,4,5,6,7) as numbered F i g . 4 .7 . iLs.2-.4 Curve R e p r e s e n t a t i o n I d e n t i f i c a t i o n o f a curve p r i m i t i v e i s more d i f f i c u l t than a s t r a i g h t l i n e p r i m i t i v e ; hence, syntax a n a l y s i s i s used to hy p o t h e s i z e and t e s t the curve p r i m i t i v e . Before syntax a n a l y s i s can be a p p l i e d , however, a s t r i n g of concatenated segment p r i m i t i v e s must be pr o v i d e d . Wnen i t i s determined t h a t the i n p u t s t r o k e i s a curve r a t h e r than a s t r a i g h t l i n e , then a l l the f i l t e r e d data t h a t d e s c r i b e the curved s t r o k e are used to c a l c u l a t e the segments of the s t r o k e . L e t t i n g S' be the st r o k e and P be p o i n t s w i t h i n the s t r o k e , then 48 S» = {Px#.P2# #p*} *. f o ^ n>3 Furthermore, l e t t i n g m^  be the s l o p e of the segment -joining Pi and P^ + i , and S be the s t r o k e d e s c r i p t i o n i n terms of a s l o p e seguence, then s " - { n » 1 # m 2 ,01^^} Using the s l o p e q u a n t i z a t i o n techniques of s e c t i o n 4 . 3 . 3 , each s l o p e measurement i s quantized i n t o a s l o p e code. That i s , m i — > 4] F i n a l l y , the s t r o k e becomes r e p r e s e n t e d by the s l o p e code sequence S. The slope code sequence, S, i s a d i r e c t i o n a l d e s c r i p t i o n of the c u r v e . Since slope codes, q , are quantized numbers, the r e are s i t u a t i o n s where f o r adjacent segments, / a t qj= q i + 1 i n t h i s case, the a d j a c e n t s l o p e code, q(- +1 , does not provide a d d i t i o n a l i n f o r m a t i o n and so only one of tnese two seqments ar e needed i n the s l o p e code sequence t o d e s c r i o e the c u r v e . Redundant s l o p e codes are hence d e l e t e d as f o l l o w s . A l l a d j a c e n t s l o p e codes are compared with each other and reduced u n t i l no a d j a c e n t s l o p e codes are the same, that i s , q-t # q i t J L ; f o r 1<i<u-2 E v e n t u a l l y , a compact slope code sequence i s o b t a i n e d 49 d e s c r i b i n g the d i r e c t i o n a l h i s t o r y of the pen movement. Thus, S = ( g i , g 2 , ...,q„) ;where m<n-1 For example, suppose the i n i t i a l s l o p e code seguence o b t a i n e d i s : S = (0 , 1 ,1,2,3,3,4) t h i s i s e g u i v a l e n t t o s a y i n g t h a t the d i r e c t i o n o f pen movement t r a v e r s e d the q u a n t i z e d d i r e c t i o n seguence 0 ,1,2,3,4. Hence, S can be s i m p l i f i e d t o S = (0 , 1,2,3,4), which has the same d i r e c t i o n a l i n f o r m a t i o n as be f o r e . 4^3 Syntax A n a l y s i s The s l o p e code seguence, S, obt a i n e d i n s e c t i o n 4.2.4 i s simply the d e s c r i p t i o n of the i r r e d u n d a n t d i r e c t i o n a l h i s t o r y of the pen movement while a curved s t r o k e was oeing formed-I t does not c o n t a i n a c c u r a t e p o s i t i o n a l i n f o r m a t i o n nor a b s o l u t e d i s t a n c e s , such as how f a r the pen has t r a v e l l e d a long each p r i n c i p l e d i r e c t i o n . In the s t r o k e p r i m i t i v e i d e n t i f i c a t i o n s t a g e , each s t r o k e i s analyzed i n d e p e n d e n t l y of o t h e r s t r o k e s w i t h i n the c h a r a c t e r because geometric r e l a t i o n s h i p s among the s t r o k e s are not known a t t h i s s t a g e . S y n t a c t i c a n a l y s i s i s t h e r e f o r e used to s o l v e tne problem of c o r r e c t l y i d e n t i f y i n g s t r o k e s which p e r c e p t u a l l y a re of the same c l a s s but have d i f f e r e n t s l o p e code sequences. To apply the s y n t a c t i c approach to han d p r i n t e d c h a r a c t e r s , i n p u t s t r o k e s must be meaningful r e p r e s e n t a t i o n s of the st r o k e p a t t e r n s e x i s t i n g , i n the upper case E n g l i s h a l p h a b e t . A c e r t a i n degree of s l a n t or d i s t o r t i o n which i s a c c e p t a b l e to humans should a l s o be a c c e p t a b l e to the machine. Hence, the s t r o k e a n a l y s i s d e s c r i b e d below determines i f the s t r o k e i s a v a l i d r e p r e s e n t a t i o n of a p r e s p e c i f i e d s t r o k e p a t t e r n and i d e n t i f i e s tne s t r o k e p r i m i t i v e c l a s s to which i t belongs. Two di m e n s i o n a l l i n e drawings, such as handprinted c h a r a c t e r s , d i s p l a y s t r o n g d e t e r m i n i s t i c s t r u c t u r e and a model based on such i n f o r m a t i o n i s d e r i v e d . Since a s t r a i g h t l i n e can e a s i l y be i d e n t i f i e d , s y n t a c t i c a n a l y s i s i s done onl y on curved s t r o k e s . The model shown i n f i g . 4.8 i s designed t o r e c o g n i z e such s t r o k e p r i m i t i v e s . Corresponding to N c l a s s e s of stroice p a t t e r n s , w x , w 2 w n , N grammars Gx,G 2,....,Gn are c o n s t r u c t e d r e s p e c t i v e l y . The i n p u t to t h i s model i s the s l o p e code seguence, S, of the cur v e . T e s t s are made to see i f S e L (Gj ) ; f o r j = 1,2,.... ,n where L (G) i s the grammar f o r a s t r o k e p r i m i t i v e . r CURVE S 6 —I I I ! S€L(Gk> L_ F i g . 4.8 Block diagram f o r the s y n t a c t i c curve r e c o g n i z e r . 51 Presumably, i f the d i f f e r e n t s t r o k e p a t t e r n s a r e rep r e s e n t e d by unique slope code sequences, then S can re p r e s e n t e i t h e r one of the N c l a s s e s of p a t t e r n s or none of the s p e c i f i e d p a t t e r n s - That i s , a d e c i s i o n . i s made as f o l l o w s : 1. I f S e L (Gj ) where 1<j<n; then S —>w . 2. I f S ^ L (Gj ) f o r 1<j<n; then S i s unrecognized. T h i s d e c i s i o n process i s i n d i c a t e d i n F i q . 4.8. Sin c e only d i r e c t i o n a l i n f o r m a t i o n i s used t o r e c o q n i z e a c u r v e , 'concatenation* i s chosen as the only c o m p o s i t i o n o p e r a t i o n used i n d e s c r i b i n q the s t r o k e p a t t e r n s . Inus the D-curve i n c h a r a c t e r s , 'D',*P','R', and 'B, are a l l c a t e g o r i z e d i n t o the same s t r o k e p a t t e r n c l a s s based s o l e l y on tne d i r e c t i o n a l i n f o r m a t i o n . In f a c t , i f a D-curve i s i s o l a t e d from a c h a r a c t e r as shown i n F i g . 4.9, we have no way of t e l l i n g i f i t i s the D-curve i n c h a r a c t e r *D', 'P, *B', or even 'R'. As f a r as a s i n g l e s t r o k e p a t t e r n i s concerned, we would a l l agree t h a t i t i s a D-curve. The same p r i n c i p l e a p p l i e s to the C-curve i n the c h a r a c t e r s *C and 'G* and the F i g . 4.9 D-curve diagram. 52 0-curve i n the c h a r a c t e r s '0' and ' Q*. Aitnough many c h a r a c t e r s have curved s t r o k e s , the number of b a s i c s t r o k e p a t t e r n s i s r e d u c i b l e to only a few. These o a s i c s t r o k e p a t t e r n s , c a l l e d s t r o k e p r i m i t i v e s , are known to us. For each s t r o k e p r i m i t i v e , a grammar i n terms of a s l o p e code seguence i s d e f i n e d so t h a t an i n p u t slope code seguence can be checked to see i f i t i s s y n t a c t i c a l l y c o r r e c t . In other words, the grammar f o r a p a r t i c u l a r stroke p r i m i t i v e i s c o n s t r u c t e d from the slope code seguence which c o n t a i n s the complete d e s c r i p t i o n of the d i r e c t i o n a l h i s t o r y of the s t r o k e p r i m i t i v e . Thus a l l str o k e p a t t e r n s of the same c l a s s , r e g a r d l e s s of the v a r i a t i o n s i n c h a r a c t e r s t r u c t u r e and s l o p e code seguence, sh o u l d be c o r r e c t l y i d e n t i f i e d as of t h a t p r i m i t i v e c l a s s . For example. F i g - 4-10 snows t h r e e handprinted c h a r a c t e r s . These t h r e e c h a r a c t e r s a r e very s i m i l a r yet t h e i r r e s u l t a n t s l o p e code seguence are d i f f e r e n t i n composition and l e n g t h depending on the parameters k and T used i n the p r e p r o c e s s i n g . Wide v a r i a r i o n s i n tne han d p r i n t e d c h a r a c t e r s of users must be a n t i c i p a t e d because the approach taken i n t h i s t h e s i s does not r e g u i r e p e r s o n a l d i c t i o n a r y b u i l d i n g . Thus, a grammar i s used to d e s c r i b e a l l C-curves t h a t normally occur. In F i g . 4.10 the d i r e c t i o n a l l o c i o f each of tne above c h a r a c t e r s i s shown. The gu a n t i z e d s l o p e code seguence f o r the l e f t - m o s t C-curve i s 53 \ I \ i 8^(6.0.1.2.3.4.5) S' = (7,0,1,2,3,4). S"=(0,l,2,3,4) F i g . 4.10 Three C-curve r e p r e s e n t a t i o n s . S i= (6,0,1,2,3,4,5) I t i s r e a s o n a b l e t o assume t h a t SL = S ; where S = (6,7,0,1,2,3,4,5) S i n c e S r e p r e s e n t s a curve and the s l o p e o f the curve i s 54 changing smoothly, the d i r e c t i o n a l change from '6* t o *Q' can be expected t o pass through d i r e c t i o n '7'. The abrupt change i n d i r e c t i o n here i s due to segmentation and g u a n t i z a t i o n e f f e c t s . In other words, i f the curve i s d i v i d e d i n t o s m a l l e r s l o p e segments, then the d i r e c t i o n a l change would be smoother and o c t a l d i r e c t i o n * 7' would a l s o be i n c l u d e d i n the s l o p e code sequence, as shown i n F i g . 4 . 1 1 . F i g . 4-11 The slope code sequence processing.. L i k e w i s e , S" i s i n c l u d e d i n the d e s c r i p t i o n of S« and S* i n S . That i s , (0 ,1,2,3,4) d (7,0,1,2,3,4) Q (6,7,0,1,2,3,4,5) We c a l l S the g e n e r a l d e s c r i p t i o n of a C-curve, s i n c e a l l O c u r v e s normally accepted by human beings are a subset of S. T h e r e f o r e , S i s an adeguate s l o p e code sequence d e s c r i p t i o n t o r e p r e s e n t C-curve s t r o k e p a t t e r n s . C o n s i d e r , f o r example, t h a t an unknown s t r i n g i s X= (7,2,3,5). I t s d i r e c t i o n a l path must r e a l l y be X = (7,0,1,2,3,4,5) 55 as shown i n F i g . 4.12, which again i s a subset of a C-curve s l o p e code sequence. That i s , V ' \ / F i g . 4-12 D i r e c t i o n a l l o cus of an unknown v e c t o r . X S where S= (6,7,0,1,2,3,4,5) Hence, we say t h a t the d i r e c t i o n a l d e s c r i p t i o n of X belongs to the C-curve s t r o k e p a t t e r n c l a s s . For l i n e drawings, such as those shown i n F i g - 4.13, which do have abrupt s l o p e chanqes, the r u l e s used are s l i g h t l y d i f f e r e n t . The s l o p e code sequence, i n t h i s c ase, must show such an abrupt chanqe. For example, i n *L* t h e r e i s an abrupt change i n d i r e c t i o n from »2' to '4'. L 6 V M F i g . 4.13 Examples of l i n e drawings w i t h abrupt slope changes. 56 In d e f i n i n g a s l o p e code d e s c r i p t i o n f o r a p a r t i c u l a r s t r o k e p a t t e r n c l a s s , c a r e must be taken t o ensure t h a t i t i n c l u d e s a l l p o s s i b l e s u b s e t s which are v a l i d r e p r e s e n t a t i o n s of the s t r o k e p a t t e r n and r e j e c t those which a r e not. The s l o p e code seguence d e s c r i p t i o n designea f o r the b a s i c c u r v e d - s t r o k e p a t t e r n c l a s s e s a r e : Sj = (2 ,1,0 ,7,6,5) S 3 = (5 , 4,3,2 , 1,0 , 7 ) S„ = (3 , 4,5) Sc = (6 , 7,0 , 1,2,3 , 4,5) S 0 = (6 , 7,0 , 1,2,3 , 4,5,6 , 7,0 , 1 ) S s = (5,6 , 7,0 , 1,2,3 , 4,3,2 , 1,0 , 7,6,5) The c o r r e s p o n d i n g d i r e c t i o n l o c i are shown i n F i g 4 . 1 4 . These curve p r i m i t i v e s , together with the s t r a i g h t l i n e p r i m i t i v e s , are s u f f i c i e n t t o c o n s t r u c t handprinted E n g l i s h c h a r a c t e r s a c c o r d i n g to the st a n d a r d proposed by the ACM [ 2 9 ] . For a l t e r n a t i v e ways of c o n s t r u c t i n g h a n d p r i n t e d c h a r a c t e r s , a d d i t i o n a l s t r o k e p r i m i t i v e s can be d e f i n e d i n terms of new sl o p e code sequence d e s c r i p t i o n s . For handprinted c h a r a c t e r s , one s t r o k e p a t t e r n can be a subset o f another s t r o k e p a t t e r n . For example, c o n s i d e r Sc - (6 , 7,0 , 1,2,3 , 4,5) S c = (6 , 7,0 , 1,2,3 , 4,5,6 , 7,0 , 1 ) I t i s obvious t h a t 57 F i g . 4.14 The d i r e c t i o n a l l o c i of the s t r o k e p r i m i t i v e s . 58 According to the s t r a t e g y d e r i v e d , a c-curve s t r o k e p r i m i t i v e c o u l d a l s o be an O-curve type- To a v o i d such ambiguity, the checking of an i n p u t s t r i n g with the s p e c i f i e d s t r o k e p a t t e r n s i s done i n ordered seguence. Suppose S i n c l u d e s a l l p o s s i b l e v a l i d r e p r e s e n t a t i o n s of a C-curve but; not a s i n g l e v a l i d r e p r e s e n t a t i o n of an O-curve. T h i s means t h a t f o r n C-curves and m O-curves: ^ i ' ^2 i^"> ( f Y j , - . . . , YfV, ( S Q but ; f o r 1<i<m To s o l v e t h i s problem, the i n p u t s l o p e code seguence i s checked with S t f i r s t . I f i t i s found t o ne a subset of Se , then the i n p u t i s a C-curve; i f i t i s not, i t w i l l be checked a g a i n s t the O-curve p r i m i t i v e , S c. Hence, by f i r s t c hecking with the C-curve p r i m i t i v e , an O-curve w i l l always be r e j e c t e d and no ambiguity w i l l occur. The code a s s i g n e d to each s t r o k e p r i m i t i v e was c a r e f u l l y s e l e c t e d to prepare f o r the technigues used i n the s u b p a t t e r n r e c o g n i t i o n s t a g e . A f t e r - a l l the s t r o k e p r i m i t i v e s w i t h i n a c h a r a c t e r are i d e n t i f i e d , s u o p a t t e r n c l a s s i f i c a t i o n i s i n i t i a t e d t o y i e l d a d e c i s i o n on the i n p u t c h a r a c t e r as d e s c r i b e d i n the next chapter. CHAPTER 5 STROKE PRIMITIVE CLASSIFICATION 5_-._1 I n t r o d u c t i o n Stroke p r i m i t i v e s are i d e n t i f i e d independently and then the s t r o k e p r i m i t i v e s w i t h i n a c h a r a c t e r are r e l a t e d f o r c l a s s i f i c a t i o n i n t o one of the p r e d e f i n e d c h a r a c t e r s - At p r e s e n t , the s t a n d a r d s e t of handprinted c h a r a c t e r s proposed by the ACM [ 2 9 ] i s c o n s i d e r e d t o be the only a c c e p t a b l e p a t t e r n s e t . In the ACM c h a r a c t e r s e t , the number of s t r o k e s and t h e i r time seguence i n c o n s t r u c t i n g a c h a r a c t e r a r e r e s t r i c t e d . However, a l t e r n a t i v e ways of p r i n t i n g a c h a r a c t e r can a l s o be e a s i l y handled as w i l l be d i s c u s s e d r n s e c t i o n 6.4. Emphasis i s placed on the ACM c h a r a c t e r s e t because i t i s a proposed s t a n d a r d and necause i t g i v e s a reasonable s i z e p a t t e r n s e t f o r e x p e r i m e n t a l purposes. In a d d i t i o n , the c h a r a c t e r s p r i n t e d are ,assumed to be a meaningful r e p r e s e n t a t i o n of the E n g l i s h upper case alphabet so t h a t the r e c o g n i t i o n problem i s f u r t h e r s i m p l i f i e d . Two c l a s s i f i c a t i o n methods, namely a d i c t i o n a r y look-up method and a n e a r e s t neighbor r u l e , are used. They are augmented by geometric measurements on c h a r a c t e r s which cannot be d i s t i n g u i s h e d by d i r e c t i o n a l i n f o r m a t i o n a l o n e . taken i s to attempt to a p a r t i c u l a r type of 5^2 Dictionary. Look-up Method In t h i s t h e s i s , the approach r e s o l v e an unigue r e p r e s e n t a t i o n f o r 60 s t r o k e p r i m i t i v e . When each s t r o k e p r i m i t i v e w i t h i n a c h a r a c t e r i s i d e n t i f i e d , the c h a r a c t e r r e c o q n i t i o n problem i s reduced to the a n a l y s i s of the r e l a t i o n s h i p s of these s t r o k e p r i m i t i v e s . T h i s a n a l y s i s y i e l d s d e c i s i o n s on the i n p u t c h a r a c t e r s , based on a d i c t i o n a r y look-up method, a s s i s t e d by geometric measurements. The p a t t e r n c l a s s e s , E n g l i s h c h a r a c t e r s , are d e f i n e d i n the d i c t i o n a r y i n terms of number and type of s t r o k e p r i m i t i v e s , order of t h e i r appearance and o p t i o n a l requirement f o r geometric measurements. For c h a r a c t e r s t h a t are w r i t t e n p r o p e r l y a c c o r d i n g to the r u l e s imposed, the i n f o r m a t i o n about the c h a r a c t e r s of the same c l a s s at t h i s stage i s c o n s i s t e n t . Thus, each p a t t e r n c l a s s can be d e s c r i b e d i n terms of a s i n g l e c h a r a c t e r v e c t o r , C^, where 1<«<<26. For r a p i d d i c t i o n a r y s e a r c h i n g , the d i c t i o n a r y i s o r g a n i z e d as a two d i m e n s i o n a l a r r a y , C©< — C j j = {S ; j j_ ,S;j2 Sfj,-)) where C;J s i g n i f i e s the j t h c h a r a c t e r vector i n the s e t of c h a r a c t e r s having i s t r o k e p r i m i t i v e s , S;j p i s the pth s t r o k e p r i m i t i v e of the j t h c h a r a c t e r v e c t o r i n the s e t of c h a r a c t e r s having i s t r o k e p r i m i t i v e s . The i n d i c e s i and j are r e l a t e d to C<* as shown i n t a b l e A -1 of appendix A. For c h a r a c t e r s adhering t o the ACH s t a n d a r d , the maximum number of s t r o k e s i n a c h a r a c t e r i s f o u r . Thus, a f t e r the s t r o k e p r i m i t i v e i d e n t i f i c a t i o n stage, an unknown i n p u t c h a r a c t e r i s r e p r e s e n t e d i n the form of a very compact v e c t o r , C, of s m a l l 61 d i m e n s i o n a l i t y : C = (Sj , S^  , • • • • S n ) The d i c t i o n a r y look-up method r e q u i r e s a p e r f e c t match of the i n p u t c h a r a c t e r v e c t o r to one of the 26 c h a r a c t e r v e c t o r s i n the d i c t i o n a r y . That i s , the method determines i f ; C = C x , f o r 1<=otC= 26 I f a f f i r m a t i v e f o r some then the i n p u t p a t t e r n C i s assigned to p a t t e r n c l a s s C<* . S i n c e the number of s t r o k e s i n a c h a r a c t e r i s e a s i l y determined i n our r e a l - t i m e approach, the r e c o g n i t i o n speed i s i n c r e a s e d by comparing o n l y those C o t 's whica are of the same l e n g t h as the i n p u t c h a r a c t e r v e c t o r . T h e r e f o r e , o n l y a few C c x ' s i n the d i c t i o n a r y need be searched. For c h a r a c t e r s t h a t have i d e n t i c a l d i r e c t i o n a l i n f o r m a t i o n , the c h a r a c t e r v e c t o r s are the same and geometric measurements must be a p p l i e d t o c l a s s i f y these c h a r a c t e r s . For i n p u t c h a r a c t e r s t h a t match a d i c t i o n a r y e n t r y , a f i n a l d e c i s i o n about the c h a r a c t e r i s made at t h i s time. I f none of the c h a r a c t e r v e c t o r s i n the d i c t i o n a r y match tne i n p u t c h a r a c t e r v e c t o r , then a second method, a n e a r e s t neighbor r u l e i s employed, as d i s c u s s e d i n s e c t i o n 5.3. In a r e a l - t i m e environment where r e c o g n i t i o n speed i s of major concern, the d i c t i o n a r y look-up method i s f a s t and adeguate with r e s p e c t to our p a r t i c u l a r problem. The r e j e c t o p t i o n i t prov i d e s a l s o a l l o w s a second c l a s s i f i e r t o make a d e c i s i o n . 62 5^3 M o d i f i e d Nearest Neighbor C l a s s i f i e r Although s t r o k e p a t t e r n s which belong to the same c l a s s from the human viewpoint s h o u l d r e s u l t i n unique r e p r e s e n t a t i o n s , s l a n t and d i s t o r t i o n i n c h a r a c t e r w r i t i n g sometimes cause m i s i d e n t i f i c a t i o n of the s t r o k e p r i m i t i v e s . For example, c o n s i d e r the f i r s t s t r o k e s of the f o u r A*s i n F i g . 5. 1 . The l e f t m o s t 1A * i s p r o p e r l y drawn while the other three are t i l t e d . S l i g h t l y t i l t e d or d i s t o r t e d c h a r a c t e r s a r e . u s u a l l y a c c e p t a b l e by human re a d e r s . However, i n our machine method, the d i c t i o n a r y has only the e n t r y of the p r o p e r l y w r i t t e n 'A* and the d i c t i o n a r y looit-up method w i l l r e j e c t the r e s t s i n c e a p e r f e c t match i s needed f o r c o r r e c t c l a s s i f i c a t i o n . A • -7 ^ ^ C *(l,3,4) C =(0,2,3) C =(2,3,4) C =(2,3,5) F i g . 5.1 The v e c t o r r e p r e s e n t a t i o n s of the c h a r a c t e r 'A1. In the f o u r c h a r a c t e r s shown i n F i g . 5.1, tne f i r s t s t r o k e s vary from approximately 1S5° to 280°, and the s l o p e code q u a n t i z a t i o n s vary from 0 to 2. In order to r u l f ij.1 the exact match a l q o r i t h m , the q u a n t i z a t i o n . o f s l o p e s from 195° to 2800 should a l l be coded as 1. However, such a q u a n t i z a t i o n would be u n s a t i s f a c t o r y i n t h a t a h o r i z o n t a l or v e r t i c a l s t r o k e may then confused with a d i a g o n a l s t r o k e , such as i n the c h a r a c t e r 'A». To s o l v e t h i s problem, a second 63 stage c l a s s i f i c a t i o n i s i n t r o d u c e d . The concept of a m u l t i s t a g e r e c o g n i t i o n system has a l s o been proposed by Tou and Gonzalez [ 4 4 ] . The preprocessed data i s t e m p o r a r i l y s t o r e d so t h a t i f the f i r s t r e c o g n i t i o n stage f a i l s , the second r e c o g n i t i o n stage i s i n i t i a t e d to work on the same data s e t . T h i s procedure i s very u s e f u l when d e a l i n g with the noise and the v a r i a b i l i t y problems that occur i n p a t t e r n r e c o g n i t i o n . In our approach, the same c h a r a c t e r v e c t o r used f o r the d i c t i o n a r y look-up method i s again used i n the second stage c l a s s i f i e r because a r e t u r n t o the f e a t u r e e x t r a c t i o n s t a g e would mean t h a t a much l o n g e r time would be r e g u i r e d f o r the r e c o g n i t i o n t a s k . T h e r e f o r e , the codes designed f o r the stroke p r i m i t i v e i n s e c t i o n 4.3 are compatible f o r both c l a s s i f i c a t i o n methods. The second stage method used here i s a m o d i f i e d n e a r e s t neighbor c l a s s i f i e r . T h i s i s a non-parametric metnod u s i n g a d i s t a n c e measurement 1 ] . Let X be a set of n independent samples where X = (X|_ ,X£ X M) The d i s t a n c e between the new p a t t e r n v e c t o r , X', and the re f e r e n c e v e c t o r , X j , f o r j = 1,....,n, i s c a l c u l a t e d . Suppose X^ i s the n e a r e s t neighbor among X to X', then, the d e c i s i o n i s to c l a s s i f y X i n t o the same p a t t e r n c l a s s as X^. The modified nearest neighbor method employs o n l y the c h a r a c t e r v e c t o r s i n the d i c t i o n a r y as the sample v e c t o r s ; hence f o r each p a t t e r n c l a s s t h e r e i s only one sample. T h i s 64 i s p o s s i b l e because the unknown p a t t e r n a t t h i s staqe i s a very simple, compact v e c t o r . The d i s t a n c e used i s tne non-E u c l i d e a n c i t y block d i s t a n c e (sometimes c a l l e d Manhattan dis t a n c e ) £ 1 ]. I t i s simple to c a l c u l a t e and i s found to work s a t i s f a c t o r i l y . Such a d i s t a n c e c a l c u l a t i o n i s c o n c e p t u a l l y the same as Lee d i s t a n c e £37] used by M i l l e r [ 3 1 ] , Xosnida and Ichikawa[24,25] i n o n - l i n e c h a r a c t e r r e c o g n i t i o n . F u r t h e r progress i n d i s t a n c e and s i m i l a r i t y measures i n p a t t e r n r e c o g n i t i o n i s a l s o r e p o r t e d by Diday[12]. The sample c h a r a c t e r v e c t o r s t h a t need to be compared are oni y those which have the same number of s t r o k e s . T h e r e f o r e , the c a l c u l a t i o n s i n v o l v e d are minimized. L e t the unknown c h a r a c t e r v e c t o r be g i v e n by C= (S l f S 2 ,. .. . Sn) . The prototype v e c t o r C ;j having the minimum d i s t a n c e D-, * , J n D,r = min D ;: = min YI S,-;p—Sp | where j i s the value of j f o r which the R.ii.S. i s a minimum, i s t e n t a t i v e l y c o n s i d e r e d t o be the p a t t e r n r e p r e s e n t i n g the unknown'pattern C. In cases where more than one prototype v e c t o r has the same minimum d i s t a n c e , the s e l e c t i o n c r i t e r i o n i s to take the f i r s t one encountered. F i n a l l y , an a c c e p t / r e j e c t t e s t i s made as f o l l o w s . Only i f the unknown p a t t e r n C f a l l s i n the d e c i s i o n space, 65 rt D ' J " I | 3 ; J P ~ S P 1 < t ' i s i t c l a s s i f i e d i n t o the same p a t t e r n c l a s s as C-,j ; o t h e r w i s e , a " d o n ' t know" c a t e g o r y i s a s s i g n e d t o the unknown p a t t e r n C. The s i z e of the d e c i s i o n space i s d e t e r m i n e d ay t , which i s a f u n c t i o n of number o f s t r o k e s i n a c h a r a c t e r , t n a t i s t = f<S) a t p r e s e n t , t i s e g u a l to the l e n g t h of the c h a r a c t e r v e c t o r of the unknown p a t t e r n . As d i s c u s s e d i n Chapter 4, the code ass ignments g i v e n to s t r o k e p r i m i t i v e s were c a r e f u l l y s e l e c t e d so t h a t d i s t a n c e c a l c u l a t i o n i n terms o f p r i m i t i v e s i m i l a r i t i e s i s m e a n i n g f u l as w e l l as p o w e r f u l . The use of t h i s second s t a g e c l a s s i f i e r has i n c r e a s e d the c a p a b i l i t y of t h e r e c o g n i t i o n sys tem to h a n d l e s l a n t e d and d i s t o r t e d c h a r a c t e r s which are a d i f f i c u l t problem i n many r e c o g n i t i o n s y s t e m s . 5._4 G e o m e t r i c A i d to C l a s s i f i c a t i o n A problem i n o n - l i n e c h a r a c t e r r e c o g n i t i o n i s . t h a t some h a n d p r i n t e d c h a r a c t e r s may have t h e same dynamic d i r e c t i o n a l i n f o r m a t i o n , yet s i g n i f y d i f f e r e n t c h a r a c t e r s . A l t h o u g h h a n d p r i n t i n g i s a dynamic p r o c e s s , a human can r e c o g n i z e a c h a r a c t e r based e n t i r e l y on the g e o m e t r i c r e l a t i o n s h i p s o f the s t r o k e p r i m i t i v e s . Powers [ 3 8 , 4 0 , 3 9 J a t t e m p t e d t o r e c o g n i z e h a n d p r i n t e d numerals based on o n l y a s i n g l e 66 d i r e c t i o n a l parameter. However, he pointed out that •6* and z e r o , which are e a s i l y r e c o g n i z e d by humans cannot be e a s i l y d i s t i n g u i s h e d by machine from d i r e c t i o n a l i n f o r m a t i o n a l o n e . T h e r e f o r e , he r e g u i r e d that a zero be w r i t t e n with a simple loop added at the f i n i s h . In h i s c o n c l u s i o n , he a l s o pointed out t h a t some c h a r a c t e r p a i r s are d i s t i n g u i s h e d only by the r e l a t i v e s i z e s or placement of s t r o k e p a t t e r n s . For example, D, P and X, Y p a i r s would l e a d to an even g r e a t e r degree of ambiguity than t h a t observed i n the c o n f u s i o n between 6 and 0. Ichikawa [ 2 5 ] r e q u i r e d the c h a r a c t e r s , D, 0, be w r i t t e n as D and 0 f o r r e c o g n i t i o n purposes. In order t o al l o w c h a r a c t e r s t o be w r i t t e n i n a n a t u r a l way, s p e c i a l r o u t i n e s are brought i n to analyze some c h a r a c t e r p a i r s which r e q u i r e qeometric r e l a t i o n s h i p s f o r d i s c r i m i n a t i o n between them. When i t i s determined t h a t the unknown c h a r a c t e r belonqs t o a p a r t i c u l a r amoiguous p a i r , then the s p e c i a l r o u t i n e f o r t h a t p a i r i s i n i t i a t e d . For example, when a c h a r a c t e r c o n s i s t s of a v e r t i c a l down s t r o k e p l u s a D-curve (|, ^  ), the unknown c h a r a c t e r can e i t h e r be a 1D* or a 'P 1 depending on how the two s t r o k e s are r e l a t e d . G e n e r a l l y speaking, the h e i g h t of v e r t i c a l s t r o k e i n 'ti' i s approximately the same as the D-curve. In 'P 1 the lower h o r i z o n t a l p o r t i o n o f the D-curve i s higher than the end p o i n t of the v e r t i c a l s t r o k e and l o o k s l i k e a f l a g . Hence, the d e c i s i o n r u l e must d e f i n e under what c i r c u m s t a n c e s 'D* and »P' are to be d i s t i n g u i s h e d from one another. 67 F i g . 5-2 shows 5 c h a r a c t e r s i n which the second and the t h i r d c h a r a c t e r s from the l e f t are ambiguous, even f o r humans. As the ' l e g * p o r t i o n l a b e l l e d 1 becomes i a r g e r as a f r a c t i o n of the h e i g h t of the c h a r a c t e r , i t becomes more apparent t h a t the c h a r a c t e r should be a *P'. D , 0 , P «P P F i g . 5.2 The cha r a c t e r p a i r 'D' & 'P'. The f o l l o w i n g l i s t shows, the d e c i s i o n r u l e s used to r e s o l v e the ambiguity between c h a r a c t e r p a i r s . C h a r a c t e r P a i r D e c i s i o n Rules D/P: The d i s t a n c e between the lower h o r i z o n t a l p o r t i o n of the D-curve and the endpoint of v e r t i c a l s t r o k e must be a t l e a s t of the o v e r a l l c h a r a c t e r height to be c l a s s i f i e d as a *P'; otherwise, i t i s c l a s s i f i e d as a 'D•. V/X: The d i s t a n c e between the two s t a r t i n g p o i n t s of s t r o k e s must be at l e a s t 3 times t h a t of the end p o i n t s t o be c l a s s i f i e d as a • V ; oth e r w i s e , i t i s an 'X*. L/T: The h o r i z o n t a l s t r o k e must be l o c a t e d a t the upper h a l f of the c h a r a c t e r t o oe c l a s s i f i e d to be a 'T'; otherwise, i t i s c l a s s i f i e d as a ' 1' • Q/0: The t a i l a t t a c h e d t o the c i r c l e must be l o c a t e d at the upper r e g i o n of the c h a r a c t e r to be c l a s s i f i e d as an • 0 1; otnerwise, i t i s a »Q«-F / I : The lower h o r i z o n t a l s t r o k e must be a t l e a s t one f i f t h of the o v e r a l l c h a r a c t e r h e i g h t 68 above the endpoint of the v e r t i c a l s t r o k e t o be c l a s s i f i e d as a 'F'; otnerwise, i t i s an •I». The d i s t a n c e between the end p o i n t s of the f i r s t two s t r o k e s are comparea to the d i s t a n c e between t h e i r s t a r t i n g p o i n t s . A r a t i o g r e a t e r than 2 i s c l a s s i f i e d as a 'A 1, a • K' f o r l e s s than 0.5; otherwise, i t i s an •H»-The d i s t a n c e between the endpornt of the f i r s t s t r o k e and s t a r t i n g p o i n t of t n e t h i r d s t r o k e must be l e s s than 20* of tne o v e r a l l c h a r a c t e r height t o be c l a s s i f i e d as a *Y. • ; othe r w i s e , i t i s c l a s s i f i e d as a •K•. 69 CHAPTER 6 EXPERIMENT AND RESULTS 6_iJ I n t r o d u c t i o n The r e c o g n i t i o n system shown i n F i g . 1.1 xs implemented on a NOVA 840 minicomputer system. A study t a o l e was h u i l t t o h o l d the w r i t i n g t a b l e t so t h a t the w r i t i n g environment i s s i m i l a r to t h a t found i n o f f i c e s , s c h o o l s or a t nome. The purpose of the experiments was as f o l l o w : 1. To observe the response of the r e c o g n i z e r i n a r e a l -time environment. 2. To observe the performance f o r a l a r g e p o p u l a t i o n who were u n t r a i n e d to the w r i t i n g system. 3. To observe the c a p a b i l i t y of preset parameters on v a r i a b l e c h a r a c t e r s i z e s . 4. To e v a l u a t e how w e l l the geometric r e l a t i o n s do i n r e s o l v i n g the a m b i g u i t i e s among c h a r a c t e r s . 5. To f i n d any major weaknesses of the system. 6. To demonstrate other c a p a b i l i t i e s of the system. 7. To show a d d i t i o n a l r e s u l t s which apply the approach taken i n t h i s t h e s i s . 6_j_2 The Experiment In order to t e s t the i d e a of r e a l - r i m e c h a r a c t e r r e c o g n i t i o n , the experiment was conducted i n a man-machine 70 i n t e r a c t i v e environment i n the form of a normal h a n d p r i n t i n g task- The environment i n our work should be d i s t i n g u i s h e d from the i n t e r a c t i v e p a t t e r n r e c o g n i t i o n r e p o r t e d by Kanal [ 2 6 ] and Chien [11], i n which users take a c t i v e p a r t i n the r e c o g n i t i o n process. A BDOS command i n i t i a t e s the t a s k and the system remains i n the man-machine communication mode u n t i l the user i n d i c a t e s the t e r m i n a t i o n of the task by t u r n i n g o f f a s w i t c h on the t a b l e t - During the c h a r a c t e r r e c o g n i t i o n t a s k , a p p r o p r i a t e messages are given to i n s t r u c t a user t o p r i n t c h a r a c t e r s on the t a n l e t . When a user i n d i c a t e s the end of a c h a r a c t e r , the macnine responds immediately to the i n p u t c h a r a c t e r . In cases where a user does not f o l l o w the r u l e s o f the t a s k , messages are a l s o output to i n d i c a t e the nature of the e r r o r and to ask the user t o r e w r i t e a c h a r a c t e r . T h i s task can be c o n t i n u e d f o r any l e n g t h of time. I t i s e s s e n t i a l t h a t each s u b j e c t know how to use the COMPUTEK pen p r o p e r l y . The pen has a wire a t t a c n e d t o i t and i s s l i g h t l y d i f f e r e n t from a r e g u l a r pen. However, one can become accustomed t o the pen i n l e s s than a minute. Before the experiment s t a r t s , each s u b j e c t i s given a few minutes, u s u a l l y fewer than t h r e e , to t r y out the pen with a few warm-up c h a r a c t e r s , but not every c h a r a c t e r i n the alp h a b e t . S u b j e c t s were asked to f o l l o w the handprinted c h a r a c t e r standard proposed by the ACM . In other words, the number of s t r o k e s , t h e i r t y p e s , and the seguence t h a t form a p a r t i c u l a r 71 c h a r a c t e r are r e s t r i c t e d . C h aracter s e p a r a t i o n xs p r o v i d e d by means of a push button on the t a b l e t , t o g e t h e r witn a s h o r t check, mark which a l s o i n d i c a t e s t h a t the c h a r a c t e r has teen p r i n t e d , s i n c e c h a r a c t e r s are w r i t t e n randomly. A t o t a l of ten people were i n v i t e d to p a r t i c i p a t e i n t h i s experiment. Graduate s t u d e n t s , undergraduate s t u d e n t s , f a c u l t y members, and p r o f e s s i o n a l s t a f f were i n c l u d e d . Each s u b j e c t was asked to p r i n t 9 s e t s or axphauets (234 c h a r a c t e r s ) on t h r e e d i f f e r e n t s h e e t s . Samples of completed sheets are shown i n F i g . 6-1. For each sheet; a s u e j e c t was reguested t o p r i n t t h r e e s e t s of a l p h a b e t s i n each of the p r e s p e c i f i e d s i z e s , which ranged from c h a r a c t e r s of 1/4 i n c h t a l l f o r the " s m a l l " s i z e , 1/2 i n c h t a l l f o r the "medium" s i z e and 3/4 inch t a l l f o r the " l a r g e " s i z e . Inese s i z e s are l a b e l l e d 'S', 'H 1, r e s p e c t i v e l y . C h a r a c t e r s d i d not have to be p r i n t e d i n a l p h a b e t i c a l or s i z e o r d e r , however, each sheet comprised of a t o t a l of 78 c h a r a c t e r s c o n s i s t i n g of t h r e e E n g l i s h a l p h a b e t s i n three s i z e s . A t a b l e on tne upper g u a r t e r of the sheet was provided to mark each c h a r a c t e r t h a t has been completed. The task was repeated f o r another two s h e e t s . Thus, a s u b j e c t f r e g u e n t l y changes the s i z e of c h a r a c t e r s produced. . f t B y € 0 •IF c b M > / • — L d m <& ' IP 1 f •Iii. V/- > M L - - — - • V NAME : . SUBJECT B T C M X 5 -?6 o o M 36 •?5" / o L 0 | / i s i A £ r r P N B C H L T r K X VV U \/ T y a Y -Gr E F s i /? n p A £ i l V X. Y Sr. L M K/ . p - r Q ft H D F I H J K f r F V> Z J ' S U P w Pig. 6.1 Handprinted samples obtained from the experiment (reduced by approximately 19$). --3 ro s s X \ \ X X X \ X X X. X. \ M S x \ X \ •x. N x» X X. L X \ \ \ \ \ \ \ \ X •INI-•& ® w f 'ILjl' ¥ w. % > \ X \ \ \ V X \ V M s s s V N \ \ \ \ V % L \ • \ \ \ \ \ V \ \ X V NAME • SUBJECT A T C M X 5 16 / o M Zt> 0 0 L o i 0 ' s 1 N\i ^ H> C. Y A3 P Cr Li W O A N k T K X L V S F x H i APR S G ^ V/LYilTFYM VIX n a n rrr: NI.TR K ? f , Q A , S T r V s T Y R D F H X R N / M W I J Q ' I P T I F i g . 6.l(cont.) Handprinted samples obtained from the experiment (reduced by approximately 19$). VjJ 74 £-.3 R e s u l t s A t o t a l of 2339 upper case E n g l i s h c a a r a c t e r s were ob t a i n e d from the 10 s u b j e c t s . The r e s u l t s on each s i z e c a t e g o r y , as w e l l as o v e r a l l performance, i s examined and compared here. The r e s u l t s are presented i n the form of c o n f u s i o n m a t r i c e s r a t h e r than by simply g i v i n g the r e c o g n i t i o n r a t e , s i n c e the l a t t e r by i t s e l f i s l e s s i n f o r m a t i v e . Table 6.1, f o r example, shows tne memberships of the i n p u t c h a r a c t e r s and the memberships of t h e i r response c a t e g o r i e s . The g u a n t i t i e s T, C, M and X are d e f i n e d as f o l l o w s : T - number of samples of a giv e n c h a r a c t e r s . C - number of samples c o r r e c t l y c l a s s i f i e d . M - number of samples m i s c i a s s i f i e d . X - number of samples u n c l a s s i f i e d . The bottom row shows the t o t a l s f o r T, C, a, X and t h e i r percentages as w e l l as the t o t a l number of i n p u t c a a r a c t e r s . T a b l e s 6.1 through 6.3 show the experimental r e s u l t s f o r s m a l l , medium, and l a r g e s i z e c h a r a c t e r s , r e s p e c t i v e l y . Table 6.4 g i v e s the combined r e s u l t s of these t a b l e s . Tattle 6.5 shows the d i s t r i b u t i o n o f c o r r e c t c l a s s i f i c a t i o n f o r the two stage c l a s s i f i e r . Out of the 2299 c o r r e c t l y r e c o g n i z e d c h a r a c t e r s , the d i c t i o n a r y look-up method alone achieved a r e c o g n i t i o n r a t e of 87.2%, with the best performance being o b t a i n e d f o r the medium s i z e c h a r a c t e r s . TABLE 6.1 SYSTEM TEST RESULTS: SMALL-SIZE CHARACTERS Response A B C 1- E !p G 1 1 — ! H | I J K L M N ! 0 p Q R S T U V V X Y z ? T C M X A 30 1 i 1 j ! i 1 i 30 30 0 0 B 30 i 3 30 30 0 0 C 30 t i 30 30 0 0 D 30 \ 1 30 30 0 0 E 30 | 1 1 30 30 0 0 P 30 i i .... j . , 30 30 0 0 G 30 30 • 30 0 ' 0 H 30 1 i 30 30 0 0 I 2 28 30 28 2 0 J 26 4 30 26 4 0 K 30 30 30 0 0 L 30 30 30 0 0 M 30 30 30 0 0 N 30 30 30 0 0 •• 0 27 2 | 1 30 27 2 1 ?.. 30 ! 30 30 0 0 Q 2 28 I ! i i 30 28 2 0 R 1 29 i i 30 29 1 0 S 24 M M 6 30 24 0 6 T i 30 •1 30 30 0 , 0 U 30 ! ! | 30 30 0 0 V 30 j | S 30 30 0 • 0 W • |30i | 30 30 0 0 X_ j30| 30 30 0 0 Y i 1 j 130 30 30 0 0 Z I i 30 30 30 0 0 780 762 11 ; 7 97.7% 1.4% 0.9% TABLE 6.2 SYSTEM TEST RESULTS: MEDIUM-SIZE CHARACTERS Response A B C D E P G E I J K L M N 0 P Q R S T U V W X Y Z ? T C M X A 30 30 ' 30 0 0 3 30 30 30 0 0 C 30 30 30 0 0 D 30 30 30 0 0 E 30 30 30 0 0 P 30 30 30 0 0 G 28 2 30 • 28 0 2 H 30 30 30 0 0 I 30 30 30 0 0 J 29 1 30 29 1 0 K 29 1 30 29 0 1 L 30 30 30 0 0 K 29 1 30 29 0 1 N 30 30 30 0 o •• 0 26 2 2 30 26 2 - 2 P.. 30 30 30 0 0 Q 2 28 30 30 0 0 R 30 30 28 2 0 S 29 1 30 29 0 1 T 30 30 30 0 0 U 30 * 30 30 0 0 V 30 30 30 0 0 V 30 30 30 0 0 X 30 30 30 0 0 Y 30 30 30 0 0 z • 30 30 30 0 0 780 768 5 7 98.5% 0.6% 0.9% TABLE 6.3 SYSTEM TEST RESULTS: LARGE-; •SIZE CHARACTERS Response A B C D E F G H I J K L M N 0 P Q R S T U V W X Y Z ? T C M X 'A 30 30 30 0 0 B 29 1 30 29 0 1 C 29 1 30 29 0 1 D 30 30 30 0 0 E 30 30 30 0 0 F 30 30 30 0 0 G 30 30 • 30 0 0 H 30 30 30 0 0 I 30 30 30 0 0 J 29 • 1 30 29 1 0 K 29 29 29 0 0 L • 30 30 30 0 0 M 29 1 30 29 0 1 N 1 29 j . 1 30 29 1 0 0 29 I 1 30 29 0 1 P.. 30" 30 30 0 0 Q i 28 2 30 28 0 2 R | 29 1 30 29 0 1 S i 29 1 30 29 0 1 T : 1 30 30 30 0 0 U 30 a 3 30 30 0 0 V 30 30 30 0 0 W 30 30 30 0 0 X i 30 30 30 0 0 Y . 30 30 30 0 0 z • 30 30 30 0 0 779 769 2 . 8 98.7% 0.3% 1.0% TABLE 6 . 4 SYSTEM TEST RESULTS: CHARACTERS OP ALL THREE SIZES Response A B C D E F G H I J K L M N 0 P Q R S T U V W X 1 Z ? T C M X A 9 0 9 0 ' 9 0 0 0 B 8 9 1 9 0 8 9 0 1 C 8 9 1 9 0 8 9 0 1 D 9 0 9 0 9 0 0 0 E 9 0 9 0 9 0 0 0 P 9 0 9 0 9 0 0 0 G 8 8 2 9 0 • 8 8 0 2 H 9 0 9 0 9 0 0 0 I 2 8 8 9 0 8 8 2 0 J 8 4 — • 6 9 0 8 4 6 0 K 8 9 1 8 9 8 8 0 1 L 9 0 9 0 9 0 0 0 M 8 8 2 9 0 8 8 0 2 N 8 9 1 9 0 8 9 1 0 0 8 2 A A 9 0 8 2 4 4 P.. 9 0 9 0 9 0 0 0 Q 4 8 4 2 9 0 8 4 A 2 R 1 8 8 1 9 0 8 8 1 1 S 8 2 8 9 0 8 2 0 8 T 9 0 9 0 9 0 0 0 U 9 0 9 0 9 0 0 0 V 9 0 I j 9 0 9 0 0 0 W 9 0 I i 9 0 9 0 0 0 X 9 0 i i 9 0 9 0 0 0 Y 9 0 9 0 9 0 0 0 Z 9 0 9 0 9 0 0 0 • 2 3 3 9 2299 1 8 2 2 9 8 , . 3% 0 . 8 % 0 . 9 % 79 TAELE 6.5 DISTRIBUTION OF CORRECT CLASSIFICATION FOR THE TWO STAGE CLASSIFIER small size medium size large size overall I I I I I I I I I I I I A 23 7 21 9.,. 18 12 62 28 B 30 0 30 0 29 0 89 0 C 30 . 0 29 1 29 0 88 1 D 29 1 30 0 28 2 87 .3 E 28 2 30 0 29 1 87 3 F 29 1 29 1 29 1 87 3 G 28 2 27 1 28 2 83 5 H 28 2 30 0 30 0 88 2 I 28 0 30 0 29 1 87 1 J 24 2 27 2 29 0 80 4 K 27 3 28 1 29 0 84 4 L 28 2 29 1 30 0 87 3 M 20 10 19 10 22 7 61 27 N 28 2 29 1 28 1 85 '4 0 18 9 15 . 11.. 14 15 57 35 P 28 2 29 1 30 0 87 3 Q 24 4 26 4 27 1 75 9 R 23 6 26 2 28 1 79 9 S 11 13 14 15 11 18 36 46 T 29 1 30 0 29 1 88 2 U 29 1 30 0 29 .1 88 2 V 24 6 24 6 25 5 73 17 W 21 9 16 14 17 13 54 36 X 29 1 30 0 30 0 89 1 Y 27 3 29 1 29 . 1 85 5 Z 30 0 30 0 29 1 89 1 673 89 687 81 685 84 2005 254 86.3% 11.4% 88.2% 10.4% 87.8% 10.8% 87.2% 11.0% NOTE: I Method I ; dictionary look-up method. I I Method I I , modified nearest neighbor rule. 80 .TABLE 6.6 SUMMARY OF SYSTEM TEST RESULTS small size medium size large size overall average total no. of samples 780 780 779 2339 fo correctly-c l a s s i f i e d 97.7% 98.5% 98.7% 98.3% * misclassified 1.4% 0.6% 0.3% 0.8% % unclassified 0.9% 0.9% 1.0% 0.9% 81 The use of the second stage c l a s s i f i e r y i e l d e d an a d d i t i o n a l 11% improvement i n the r e c o g n i t i o n r a t e f o r the r e c o g n i t i o n system. The o v e r a l l r e c o g n i t i o n r a t e i s 93.3A. T a b l e 6.6 shows a summary of the t e s t r e s u l t s i n term of percentage f i g u r e s . The performance on the sm a l l s i z e c l a s s snows a s l i g h t l y h i g h e r e r r o r r a t e than f o r the other two s i z e s . The reasons f o r t h i s are as f o l l o w s . F i r s t l y , the COMPUTER pen was found to be u n s u i t a b l e f o r c h a r a c t e r s 1/4 i n c h t a i l or s m a l l e r . Most s u b j e c t s found t h a t c h a r a c t e r s 1/4 inch t a i l cannot a l l be w r i t t e n n a t u r a l l y because of t h e combination of the s i z e of the pen, which i s l a r g e r than a Parker pen, and t h e s i z e of the l e a d i s 1.0 mm t h i c k . Secondly, the COMPUTER pen r e g u i r e s a w r i t i n g f o r c e of 3 ounces f o r data to be a c c e p t e d . S u b j e c t s , however, are used to t h e i r normal way of handwriting i n which d i f f e r e n t w r i t i n g f o r c e s are a p p l i e d t o d i f f e r e n t p o r t i o n s of a curve. In other words, sometimes only p a r t o f a curve r e c e i v e d a w r i t i n g f o r c e i n excess of 3 ounces and caused incomplete i n f o r m a t i o n to be generated. F o r example, an 'R1 may be r e c o g n i z e d as a ' R*, ana a 1 J ' may be re c o g n i z e d as a 'T'. For medium and l a r g e s i z e c h a r a c t e r s , the c u r v a t u r e of a curved s t r o k e changes more s l o w l y and the s u b j e c t s u s u a l l y a p p l i e d enough f o r c e througuout a curve p r o d u c t i o n . T h i r d l y , the two parameters T and k were p r e s e t and not o p t i m a l l y tuned f o r s m a l l s i z e c h a r a c t e r s . Of the 2339 i n p u t c h a r a c t e r s , . only 40 c n a r a c t e r s , o r 82 1.7&, were e i t h e r m i s c l a s s i f i e d or u n c l a s s i f i e d - The source of e r r o r s can be d i v i d e d i n t o t h r e e c a t e g o r i e s , i - F a i l u r e to i d e n t i f y a curve: E r r o r s i n t h i s c a t e g o r y are mainly caused by the freedom the s u b j e c t s a l l o w themselves i n handwriting- Examples are: a f u z z y curve t h a t i s beyond a c c e p t a b i l i t y , or a long hook at the end of a s t r o k e , i i . M i s i d e n t i f i c a t i o n of a curve as a s t r a i g h t l i n e and v i c e v e r s a . For example, i f a s h o r t J - c u r v e i s m i s i d e n t i f i e d as a v e r t i c a l l i n e , the c h a r a c t e r i s c l a s s i f i e d as a 'T*. In other cases, a long s t r a i g h t l i n e i s m i s i d e n t i f i e d as a curve. The reason f o r these e r r o r s i s t h a t the two parameters T and k of p r e p r o c e s s i n g r o u t i n e are o p t i m a l l y s e t f o r c h a r a c t e r s of a p a r t i c u l a r s i z e . For c h a r a c t e r s t h a t are s m a l l e r , the T and k should r e a l l y be decreased t o y i e l d o p t i m a l performance. At the present time, I and k are f i x e d and c h a r a c t e r s i z e s are v a r i e d ; thus performance on l a r g e and s m a l l c h a r a c t e r s are a f f e c t e d s l i g h t l y . Since T i s too l a r g e f o r s m a l l c h a r a c t e r s , a c u r v e , f o r example, would be m i s i d e n t i f i e d as a s t r a i g h t l i n e . M i s c l a s s i f i c a t i o n at t h i s stage causes f a i l u r e l a t e r i n p r o p e r l y c l a s s i f y i n g a c h a r a c t e r . • i i i . F a i l u r e to r e s o l v e the ambiguity between c h a r a c t e r p a i r s . As d i s c u s s e d i n s e c t i o n 6.3, the geometric measurements used are minimal. Consequently, they are 83 somewhat inadequate for some badly formed characters that are recognized by humans. In other words, geometric measurements ad d i t i o n a l to tne present desiqn could be carried out to further resolve the amibiguity between character pairs, again, taere i s a trade-off between recognition speed ana higher recognition rate. TABLE 6 . 7 CLASSIFICATION OF ERRORS " ~ \ ^ t y p e of s i z e ^ ^ f I II III Small 0.30% 0.21% 0.26% Medium 0.21% 0.13% 0.17% Large 0.34% 0.08% 0 Total 0.86% 0.43% 0.43% NOTE; I . Failure to identify a curve. I I . Misidentification of a curve as a straight line and vice versa. I I I . Failure to resolve the ambiguity between character paris. 84 Table 6.7 g i v e s a summary of the above e r r o r t y p e s . An e r r o r r a t e of 5% i s g e n e r a l l y c o n s i d e r e d a c c e p t a b l e i n r e a l -time r e c o g n i t i o n s i n c e any e r r o r can be c o r r e c t e d ny the user immediately. Our system r e s u l t s an e r r o r of l e s s than 2% from 2339 samples among a p o p u l a t i o n of 10 people and i s t h e r e f o r e more than a c c e p t a b l e . 6.2.4 A d d i t i o n a l R e s u l t s The s t a n d a r d proposed by the ACM f o r n a n d p r i n t e d c h a r a c t e r s was used f o r the experiments. However, o t n e r ways of w r i t i n g E n g l i s h c h a r a c t e r s , or even tne a l p h a b e t of another language, can be handled using the approach presented i n t h i s t h e s i s . For example, i n order t o accept other ways of h a n d p r i n t i n g E n g l i s h upper case c h a r a c t e r s , new e n t r i e s c o r r e s p o n d i n g t o the new ways of p r i n t i n g are addea i n t o the present d i c t i o n a r y . These added c h a r a c t e r s may be formed by e x i s t i n g s t r o k e p r i m i t i v e s , or i f new s t r o k e p r i m i t i v e s a r e d e s i r a b l e , these new s t r o k e p r i m i t i v e s can be d e f i n e d f o l l o w i n g the method d e s c r i b e d i n s e c t i o n 4.3. New ambiguous c h a r a c t e r p a i r s might a r i s e when the new e n t r i e s a r e mixed with the e x i s t i n g d i c t i o n a r y e n t r i e s . I f t h a t i s the c a s e , s p e c i a l geometric measurements must a l s o be p r o v i d e d . Once a new c h a r a c t e r s e t i s d e f i n e d , the r e c o g n i z e r can be c o n v e n i e n t l y used without r e g u i r i n g a d d i t i o n a l samples from u s e r s . F i g . 6.2 shows some c h a r a c t e r s t h a t were a l s o r e c o g n i z e d by the system, i n a d d i t i o n to those p r e d e f i n e d by 85 the ACM s t a n d a r d , s i m p l y by d e f i n i n g new s t r o k e p r i m i t i v e s and a d d i n g new e n t r i e s i n t o the d i c t i o n a r y . Some i n t e n t i o n a l l y s l a n t e d and d i s t o r t e d c h a r a c t e r s , w r i t t e n on u n r u l e d p a p e r , are shown i n F i g . 6 . 3 . These c h a r a c t e r s were a l l s u c c e s s f u l l y r e c o g n i z e d , i t *as found t h a t a c o r r u p t e d c h a r a c t e r formed from s t r a i g h t , l i n e s t r o k e s i s e a s i e r to r e c o g n i z e than a c h a r a c t e r which has one or more c u r v i l i n e a r s t r o k e s . However, s t r a n g e l y d i s t o r t e d C h a r a c t e r s are seldom e n c o u n t e r e d i n e v e r y d a y p r i n t i n g . 86 A A A / ) B B B 6 <=> Q G, G\ Cj n r\ n M / A M IVI /i ^ i n • U U U u u V V K V v \/v/ \yJ W VA7 L ^ U ( i F i g . 6.2 Examples o f s u c c e s s f u l l y r e c o g n i z e d h a n d p r i n t e d c h a r a c t e r s o t h e r t h a n t h e ACM s t a n d a r d . 87 M K ^ A- I) H H H H M ^ XA k /r \ . Nf Y- K / V N rA. ^ Y F i g . 6.3a Examples of s u c c e s s f u l l y recognized, i n t e n t i o n a l l y d i s t o r t e d c h a r a c t e r s . 88 7" ^ j" -7~ U )J \J ^ U (j V j/ V y \ / >^ X X 7< X j* r i S 5 5 3 s F i g . 6 . 3 a(cont.) Examples of s u c c e s s f u l l y recognized, i n t e n t i o n a l l y d i s t o r t e d c h a r a c t e r s . 89 A A M H X e C R Pig. 6.3b Examples of successfully recognized characters formed by badly drawn line drawings. 90 F i g . 6.3c Examples of s u c c e s s f u l l y recognized extremely l a r g e and s m a l l c h a r a c t e r s . 91 CHAPTER 7 CONCLUSIONS 1.2.1 D i s c u s s i o n In r e a l - t i m e c h a r a c t e r r e c o g n i t i o n , response time i s very important and the r e c o g n i t i o n r a t e s h o u l d keep up with the h a n d p r i n t i n g speed at a l l times. In the d e s i g n of the r e c o g n i z e r i n t h i s t h e s i s , much e f f o r t was p l a c e d on r e c o g n i t i o n speed o p t i m i z a t i o n . The experiments snowed t h a t the reponse to a handprinted c h a r a c t e r i n p u t takes p l a c e immediately a f t e r the end of c h a r a c t e r i s i n d i c a t e d by the s u b j e c t . T h e r e f o r e , a s u b j e c t i s allowed to w r i t e at maximum speed because the machine response i s f a s t enough to keep up with the w r i t i n g speed. Host c h a r a c t e r r e c o g n i z e r s todate have r e g u i r e d a p e r s o n a l d i c t i o n a r y , c o l l e c t i o n of numerous pr o t o t y p e samples, s p e c i a l t r a i n i n g , or machine l e a r n i n g p r o c e s s e s p r i o r to the r e c o g n i t i o n of a s u b j e c t ' s C h a r a c t e r s . The r e c o g n i z e r presented i n t h i s t h e s i s i s designed f o r i n d i v i d u a l s who are n e i t h e r f a m i l i a r with the w r i t i n g system nor whose samples have been c o l l e c t e d i n advance by the machine. N e i t h e r does the r e c o g n i z e r undergo any s o r t of l e a r n i n g process. The experiments show t h a t u n t r a i n e d s u b j e c t s can perform j u s t as w e l l as someone wno i s f a m i l i a r with COMPUTER t a b l e t w r i t i n g . The same p r e d e f i n e d d i c t i o n a r y i s found to work very w e l l f o r a l l the s u b j e c t s who p a r t i c i p a t e d i n the experiment. The design presented here not 92 only saves storage requirements, which i s very important i n the s m a l l machine environment, but a l s o saves c o n s i d e r a b l e computational time. Most p r e v i o u s r e s e a r c h e r s only accepted c h a r a c t e r s of a s p e c i f i e d s i z e and none, to the author's knowledge, designed a r e c o g n i z e r that w i l l accept both l a r g e ana s m a l l s i z e c h a r a c t e r s . As mentioned i n chapter 3 the two parameters T and k can be a d j u s t e d to accept c h a r a c t e r s of p r a c t i c a l l y any s i z e . At the present time, the pr e s e t values f o r T and k can accept c h a r a c t e r s of reasonable s i z e s . Tne e x p e r i m e n t a l r e s u l t s show t h a t the r e c o g n i t i o n r a t e s on l a r g e , medium and s m a l l c h a r a c t e r s are approximately the same. I t s h o u l d be noted that a l a r g e c h a r a c t e r i s t h r e e times as l a r g e as a s m a l l c h a r a c t e r . A 3/4 i n c h t a l l c h a r a c t e r i s c o n s i d e r e d to be very l a r g e f o r d a i l y h a n d p r i n t i n g , whereas a 1/4 i n c h t a l l c h a r a c t e r i s found to be s m a l l when u s i n g the COMPUTER pen. Most s u b j e c t s found t h a t a 3/8 i n c h t a l l c h a r a c t e r s i z e can be w r i t t e n q u i t e n a t u r a l l y . In f a c t , T and k are o p t i m a l l y tuned f o r c h a r a c t e r s of t h a t s i z e although c l e a r l y , s m a l l e r and l a r q e r c h a r a c t e r s can a l s o be re c o g n i z e d s a t i s f a c t o r i l y as w e l l . In d a i l y a p p l i c a t i o n , c h a r a c t e r s are o f t e n w r i t t e n i n a c o n s i s t e n t s i z e and, i n some cases, c n a r a c t e r s a r e r e q u i r e d t o be produced i n a c e r t a i n form, such as f o r proqram coding sheets and r e c e i p t s . At the present time, a d i c t i o n a r y look-up method i s used f o r the i n i t i a l c h a r a c t e r c l a s s i f i c a t i o n . T h i s method i s 93 simple and f a s t and i s found t o be adequate i n c l a s s i f y i n g w e l l drawn c h a r a c t e r s . For c h a r a c t e r s t h a t cannot be re c o g n i z e d by the d i c t i o n a r y look-up method, tne m o d i f i e d n e a r e s t neighbor r u l e i s a p p l i e d t o y i e l d a f i n a l d e c i s i o n on the i n p u t p a t t e r n . In f a c t , t h i s method can ne used, e x c l u s i v e l y to c l a s s i f y the st r o k e p r i m i t i v e p a t t e r n s , but i t would take much more time than the d i c t i o n a r y look-up method. Although i t may seem that the f i r s t stage c l a s s i f i c a t i o n i s unnecessary, s i n c e the second stage c l a s s i f i c a t i o n can do the job, i t must be r e a l i z e d t h a t r e c o g n i t i o n speed i s very important i n a r e a l - t i m e approach. For some types of c h a r a c t e r s , such as s l a n t e d or d i s t o r t e d c h a r a c t e r s , the two stage method i s slower than u s i n g the second stage method alone. However, most c h a r a c t e r s t h a t are wa l l drawn can be r e c o g n i z e d immediately by the f i r s t stage c l a s s i f i e r which i s much f a s t e r than the second s t a g e . Conseguentiy, the average time r e g u i r e d f o r r e c o g n i t i o n i s s i g n i f i c a n t l y reduced by the two stage approach. The d i s t a n c e measurement used i n the second stage c l a s s i f i e r i s found t o be s a t i s f a c t o r y f o r upper case E n g l i s h c h a r a c t e r s . However, i f new p r i m i t i v e s , such as f o r another a l p h a b e t , are c o n s t r u c t e d , tnen s p e c i a l care must be e x e r c i s e d i n a s s i g n i n g a p a t t e r n t o a p r e s p e c i f i e d sample c l a s s . S p e c i a l r o u t i n e s are provided t o c a l c u l a t e the geometric r e l a t i o n s h i p s of s t r o k e s w i t h i n a c h a r a c t e r i n the cases 94 where d i r e c t i o n a l i n f o r m a t i o n alone cannot r e s o l v e the ambiguity of some c h a r a c t e r p a i r s . As mentioned i n Chapter 5 , geometric measurements are necessary i n the r e c o g n i t i o n of E n g l i s h c h a r a c t e r s . However, s i n c e e x e c u t i o n speed i s a major concern i n the r e a l - t i m e approach, geometric c a l c u l a t i o n s and temporary data s t o r a g e requirements are a l s o minimized. At t h i s time, o n l y the i n i t i a l and the end p o i n t s of a s t r o k e a r e t e m p o r a r i l y s t o r e d i n case they w i l l be c a l l e d upon to a i d i n the c h a r a c t e r c l a s s i f i c a t i o n . For most c h a r a c t e r p a i r s , the amount of data t e m p o r a r i l y saved proved to be adeguate and a m b i q u i t i e s are r e s o l v e d e a s i l y with o n l y a few c a l c u l a t i o n s . However, f o r the c h a r a c t e r p a i r the data saved proved t o be inadequate and o c c a s i o n a l l y caused c o n f u s i o n between these two c h a r a c t e r s . T h i s problem can be e a s i l y s o l v e d simply by usinq more temporary data s t o r a g e so t h a t the o v e r a l l c h a r a c t e r s i z e can be c a l c u l a t e d . Such a m o d i f i c a t i o n means a s a c r i f i c e i n e x e c u t i o n speed s i n c e more data are t o be s t o r e d from every s t r o k e and tne o v e r a l l r e c o q n i t i o n w i l l take a longer time. The s y n t a c t i c method i s found t o be g u i t e s a t i s f a c t o r y f o r i d e n t i f y i n g the s t r o k e p r i m i t i v e s , r e g a r d l e s s of the wide v a r i a t i o n s which e x i s t among a l a r g e p o p u l a t i o n or even f o r the same i n d i v i d u a l at d i f f e r e n t times. Such a metnod w i l l be even more powerful when the p a t t e r n s d e a l t with are of a higher degree of c o m p l e x i t y . For p a t t e r n s such as n a n d p r i n t e d c h a r a c t e r s , s t r u c t u r a l i n f o r m a t i o n i s found to play an 95 important r o l e i n c h a r a c t e r i z i n g the p a t t e r n s . In a d d i t i o n to the s t a t i c i n f o r m a t i o n t h a t d e s c r i b e s a c h a r a c t e r a f t e r i t i s formed, the dynamic i n f o r m a t i o n that d e s c r i b e s the process of c h a r a c t e r f o r m a t i o n i s a l s o known i n a r e a i - t i m e w r i t i n g environment. I t i s t h i s advantage of having tne d i r e c t i o n a l h i s t o r y of the pen movement and s t r o k e s e p a r a t i o n i n the r e a l - t i m e approach, as compared with the o f f - l i n e approach, which make the s y n t a c t i c method f e a s i b l e i n a n a l y z i n g s t r o k e p r i m i t i v e s . When s t r o k e p r i m i t i v e s are i d e n t i f i e d , the r e c o g n i t i o n problem i s reduced to t h a t of a n a l y z i n g the r e l a t i o n s h i p s amongst s t r o k e p r i m i t i v e s . The r e c o g n i z e r can be m o d i f i e d t o r e c o g n i z e c h a r a c t e r s other than the ACM proposed standard handprintea upper case E n g l i s h c h a r a c t e r s [ 2 9 ]. To what extent t h i s approach can be e f f i c i e n t l y a p p l i e d to other c h a r a c t e r s e t s remains to be i n v e s t i g a t e d by f u r t h e r experiments. f i g . 6.2 shows a l t e r n a t i v e samples of the upper case alphabet r e c o g n i z e d simply by d e f i n i n g new s t r o k e p r i m i t i v e s and e n t r i e s i n the d i c t i o n a r y . Such a m o d i f i c a t i o n was e a s i l y done by the author. For users who have no knowledge of tne r e c o g n i t i o n scheme, the m o d i f i c a t i o n would be d i f f i c u l t . However, when a r e c o g n i z e r i s developed, i t i s not i n t e n d e d to oe m o d i f i e d a t the user's l e v e l . Most p r e v i o u s r e s e a r c h i n handprinted c h a r a c t e r s has been done o f f - l i n e on l a r g e machine systems, whereas the approach taken i n t h i s t h e s i s i s focused on r e a l - t i m e 96 r e c o g n i t i o n i n a s m a l l m a c h i n e e n v i r o n m e n t . I t h a s been d e m o n s t r a t e d t h a t a d i f f i c u l t p r o b l e m c a n oe s o l v e d by means o f a f a s t , s i m p l e method w i t h t h e a i d o f r e a l - t i m e i n f o r m a t i o n w h i c h g r e a t l y r e d u c e s t h e c o m p l e x i t y o f h a n d p r i n t e d p a t t e r n s . W i t h t h e a d v e n t o f l o w - c o s t m i c r o p r o c e s s o r s , r e a l - t i m e , i n t e r a c t i v e s y s t e m s b a s e d on m i c r o p r o c e s s o r s w i l l be w i d e l y u s e d i n a l l a s p e c t s o f e v e r y d a y l i f e . A c o m p a c t r e a l - t i m e c h a r a c t e r r e c o g n i z e r o r a s p e e c h r e c o g n i z e r becomes i n c r e a s i n g l y n e c e s s a r y i n a n a t u r a l man-machine c o m m u n i c a t i o n e n v i r o n m e n t a n d t h e work r e p o r t e d h e r e i n d i c a t e s t h e f e a s i b i l i t y o f s u c h a r e c o g n i z e r . 7.2 Summary, To s u m m a r i z e , a s i m p l e , e f f i c i e n t r e c o g n i z e r was d e v e l o p e d t o r e c o g n i z e h a n d p r i n t e d c h a r a c t e r s i n r e a l t i m e i n a s m a l l m a c h i n e e n v i r o n m e n t . A d a t a a c q u i s i t i o n s y s t e m was d e s i g n e d a n d i m p l e m e n t e d t o a l l o w r e a l w o r l d d a t a t o f l o w i n t o t h e c o m p u t e r f r o m a COMPUTER w r i t i n g t a b l e t . A p a t t e r n r e c o g n i z e r was d e s i g n e d , i m p l e m e n t e d a n d r a n s u c c e s s f u l l y i n p a r a l l e l w i t h t h e d a t a a c g u i s i t i o n r o u t i n e t o m i n i m i z e t h e d a t a s t o r a g e r e q u i r e m e n t s a n d t o p r o v i d e f a s t r e s p o n s e t o h a n d p r i n t e d i n p u t s . A c u r v e seqment o p t i m i z a t i o n t e c h n i q u e was e m p l o y e d s o t h a t o n l y t h e most s i g n i f i c a n t d a t a t h a t d e s c r i b e a c h a r a c t e r a r e p a s s e d on t o t h e s t r o k e p r i m i t i v e i d e n t i f i c a t i o n s t a q e - A new n o n - u n i f o r m s l o p e q u a n t i z a t i o n 97 method was developed f o r t h i s o p t i m i z a t i o n . The r e s u l t i n g s t r o k e p a t t e r n s are c l a s s i f i e d as one of the p r e d e f i n e d s t r o k e p r i m i t i v e c l a s s e s by a s y n t a c t i c approach. F i n a l l y , the combination of s t r o k e p a t t e r n s w i t h i n a c h a r a c t e r a re c l a s s i f i e d as one of the known c h a r a c t e r s f i r s t by the d i c t i o n a r y look-up method. For c h a r a c t e r s t h a t are r e j e c t e d by t h i s stage, a m o d i f i e d n e a r e s t neighborhood r u l e i s then a p p l i e d to y i e l d a f i n a l d e c i s i o n . The r e c o g n i z e r i s designed as an i n t e r a c t i v e w r i t i n g task on a NOVA 840 minicomputer system. A t o t a l of ten people were i n v i t e d to t e s t the system. F i v e were t o t a l l y i n e x p e r i e n c e d with COMPUTES t a b l e t w r i t i n g ; f o u r had l i m i t e d e x p e r i e n c e with the t a b l e t but no expe r i e n c e with the r e c o g n i t i o n system. An average r e c o g n i t i o n r a t e o f 98.3% was o b t a i n e d f o r 2339 c h a r a c t e r s o f t h r e e s i z e s ranging from 1/4 inch t o 3/4 i n c h t a l l . From the a d d i t i o n a l r e s u l t s provided i n Chapter 6, i t i s suggested t h a t the approach taken i n t h i s t h e s i s can be a p p l i e d t o handprinted p a t t e r n s other than the standard proposed by the ACM [ 2 9 ] . 7^3 Suggestions f o r Furth e r Research Since i t i s assumed t h a t users w i l l w r i t e meaningful r e p r e s e n t a t i o n s of E n g l i s h upper case c h a r a c t e r s , ana because of the concern f o r r e c o g n i t i o n speed, the c l a s s i f i c a t i o n stage mainly checks on the order of occurrence of each i n d i v i d u a l s t r o k e p r i m i t i v e w i t h i n a c h a r a c t e r . For the many 98 c h a r a c t e r s t h a t have unique d i r e c t i o n a l i n f o r m a t i o n , geometric r e l a t i o n s amonq the s t r o k e p a t t e r n s w i t h i n a c h a r a c t e r are not used. Althouqh qeometric a n a l y s i s on each c h a r a c t e r slows down the r e c o q n i t i o n speed, r t i s s t i l l d e s i r a b l e t o do so i n some cases to cur down the m i s r e c o g n i t i o n r a t e . The experimental r e s u l t s suggest t h a t the m i s c l a s s i f i c a t i o n r a t e wouid be decreased i f the c l a s s i f i e r were more s o p h i s t i c a t e d . Therefore f u r t h e r geometric a n a l y s i s would tend to improve the system performance. I s o l a t i o n of c h a r a c t e r s i s at present e s t a b l i s h e d by a hardware s i g n a l g i v e n by the user- In r e a l world a p p l i c a t i o n s , i t i s d e s i r a b l e t h a t the r e c o g n i z e r be a b l e t o sep a r a t e c h a r a c t e r s a u t o m a t i c a l l y so that the user can co n c e n t r a t e e n t i r e l y on h i s problem. Character s e p a r a t i o n can be done by measuring the geometric d i s t a n c e of one s t r o k e p a t t e r n from another. I t i s reasonable t o assume t h a t s t r o k e p a t t e r n s t h a t belong t o the same c h a r a c t e r tend to be c l o s e t o g e t h e r when compared to s t r o k e s from another c h a r a c t e r . In othe r words, the f i r s t s t r o k e of a c h a r a c t e r w i l l be some d i s t a n c e from the l a s t s t r o k e of pr e v i o u s c h a r a c t e r p r i n t e d , presuming c h a r a c t e r s are w r i t t e n from l e f t to r i g n t , as i n most European and North American c o u n t r i e s . When a rormatted paper, such as a F o r t r a n coding sheet i s used, the problem i s even s i m p l e r s i n c e c h a r a c t e r s i z e i s f i x e d . The s y n t a c t i c method used t o i d e n t i f y s t r o k e p r i m i t i v e s 99 can a l s o be a p p l i e d to r e c o q n i z e handprinted lower case E n g l i s h c h a r a c t e r s , numerals, c h a r a c t e r s or otner a l p h a b e t s , and handwritten E n g l i s h words. For example, the s i n g l e s t r o k e c h a r a c t e r s d i s c u s s e d i n t h i s t h e s i s , C, S, 0 , H, N, W, U, V, L, are very s i m i l a r t o lower-case E n g l i s h c h a r a c t e r s . Each c h a r a c t e r has a d i s t i n c t p a t t e r n and can be d e f i n e d as an unigue s t r o k e p r i m i t i v e . For most hand-drawn lower case c h a r a c t e r s , the l i n e drawings c o n s i s t of mostly c u r v e s and the s y n t a c t i c approach would be very u s e f u l . For handwritten E n g l i s h words, each word may be d e f i n e d by a d i s t i n c t s t r o k e p r i m i t i v e ; hence, an i n p u t word may then be i d e n t i f i e d as one of these p r i m i t i v e s . For example,the E n g l i s n words •low', •go', •me* are a l l s i n g l e s t r o k e p a t t e r n s and each- may be co n s i d e r e d as a d i s t i n c t p r i m i t i v e . For handwritten words which c o n t a i n s the l e t t e r s ' t * , ' i ' e t c , geometric measurements become i n c r e a s i n g i m p o r t a n t . Due t o the freedom t h a t human beings allow themselves i n handwriting, p a t t e r n s t h a t supposedly belong to the same c l a s s vary widely from one another. Although the shape of the c h a r a c t e r when c o n s t r u c t e d may be v a s t l y d i f f e r e n t , the d i r e c t i o n a l h i s t o r y o b t a i n e d from the pen movement may have many s i m i l a r i t i e s . Precognition of handwritten words using the approach d i s c u s s e d i n t h i s t h e s i s i s worthwhile i n v e s t i g a t i n g s i n c e very rew r e s e a c h e r s have ever attempted to t a c k l e t h i s kind of problem due to i t s complexity. R e c o g n i t i o n of p r i n t e d Chinese c h a r a c t e r s i s a d i f f i c u l t 100 task [22,3 ,10,42,9 ,17], I t i s noted t h a t a ha n d p r i n t e d Chinese c h a r a c t e r i s a dynamic p r o d u c t i o n formed from a qroup of s t r o k e p r i m i t i v e s i n a d e f i n i t e sequence. Such m i or ma t i on i s s i m i l a r t o t h a t o b t a i n e d i n our data a c q u i s i t i o n system so the s y n t a c t i c approacn would be very u s e f u l . O b v i o u s l y , Chinese c h a r a c t e r s are more complicated than E n g l i s h c h a r a c t e r s and would r e q u i r e many l e v e l s of s u b p a t t e r n i d e n t i f i c a t i o n , a i d e d by s o p h i s t i c a t e d syntax a n a l y s i s . The present r e c o q n i z e r i s e s t a b l i s h e d as an i n t e r a c t i v e program which responds to user i n p u t c h a r a c t e r s i n r e a l time. The data t h a t d e s c r i b e a c h a r a c t e r i s processed o e f o r e the c h a r a c t e r i s f i n i s h e d and o n l y some of the s i g n i f i c a n t data i s temporary s t o r e d . T h i s program can be e a s i l y m o d i f i e d to save a l l the data f o r a c h a r a c t e r , so t h a t when a c h a r a c t e r i s r e c o g n i z e d , such data may be r e c o r d e d i n i t s c o r r e s p o n d i n g sample c l a s s i n a data base. A user could d e l e t e c o r r u p t e d c h a r a c t e r s immediately and c o u l d i n s t r u c t the computer to d i s c a r d t h i s d a ta. The c r e a t i o n of a data base of a a n d p r i n t e d c h a r a c t e r s would allow other r e s e a r c h e r s to go d i r e c t l y i n t o the r e c o g n i t i o n phase ' of r e a l - t i m e hand-drawn p a t t e r n s without going through the d i f f i c u l t stage of data a c q u i s i t i o n , which r e g u i r e s s p e c i a l hardware , software support and e f f o r t . The t a b l e t . s e r v i c e r o u t i n e and the p a r a l l e l p r o c e s s i n g p r o c e s s o r can a l s o be e a s i l y m o d i f i e d f o r use independently i n p r o c e s s i n g g r a p h i c a l p i c t u r e s such as e n g i n e e r i n g curves 101 and c i r c u i t diagrams. The switches on the t a b l e t can a l s o be used to s e t the t a b l e t i n d i f f e r e n t modes to perform d i f f e r e n t t a s k s . I 102 REFERENCES [1] B. Batchelor, Practical Approach to Pattern Classification, . Plenum Press, Condon, New York, 1974. [2] P. Berker and K. Nielsen, "Pattern recognition using dynamic pic-t o r i a l information,", IEEE Trans, on System, Man and Cybernetics, Vol. SMC -.2, pp. 434-437, July, 1972. [3] M. Bernstein, "A method for recognizing handprinted characters i n real time". In Pattern Recognition (L. Kanal, ed.), Thompson Book Co., 1968. [4] M. Bernstein, "Toward natural man-machine dialogue", In Multiaccess  Computing (Rosenthal and Mish, ed.). Hayden Book Co. Inc., Rochelle Park, N.J., 1974. [5] M. Bernstein and H. Howell, "Handprinted input for on-line systems", Rep. NASA-CR-1284, Systems Develop. Corp., Santa Monica, California, 1969. [6] M. Berthod and J. Maroy, "Morphological features and sequential information in real time handprinted recognition", Proc. of Second International Joint Conference on Pattern Recognition, Copenhagen, Denmark, pp. 358-363, August 1974. [7] R. Brown, "On-line computer recognition of hand-printed characters", IEEE Trans, on Electronic Computers, Vol. EC-13, No. 6, pp. 750-752, December 1964. [8] R. Casey and G. Nagy, "Recognition of printed Chinese characters", IEEE Trans, on Elect. Computers-, Vol. EC-15, No. 1, pp. 91-101, February 1966. [9] S. Chang, "An interactive system for Chinese character generation and retrieval", IEEE Trans, on System, Man and Cybernetics. SMC-3, No. 3, pp. 257-265, May 1973. [10] S. Chang,"Automated interpretation and editing of fuzzy line draw-ings", AFIPS Proc. SJCC, Vol. 38, pp. 393-399, 1971. [11] Y. Chien, "Interactive pattern recognition techniques and systems", IEEE Computer Magazine, Vol. 8, No. 4, pp. 11-25, May 1976. [12] E. Diday, "Recent progress in distance and similarity measures in pattern recognition", Proc. of Second International Joint Confer-ence on Pattern Recognition, Copenhagen, Denmark, pp. 534-539, August 1974. [13] R. Duda and P. Hart, Pattern Classification and Scene Analysis, John Wiley, New York, 1973. [14] T. E l l i s and W. Sibley, "On the development of equitable graphic I/O", IEEE Trans, on Human Factors in Electronics, Vol. HFE-8, No. 1, pp. 15-17, March 1967. 103 [15] R. Farag and Y. Chien, "Real time analysis and verification of hand-printed signatures", Tech. Rep. CS-72-1, University of Connecticut, June, 1972. [16] H. Freeman, "Computer processing of line drawing images", ACM Com-puting Surveys, Vol. 6, No. 1, pp. 57-97, 1974. [17] K. Fu, Syntactic Methods in Pattern, Recognition, Academic Press, New York, 1974. [18] H. Fujisaki, S. Nagai and N. Hidaka, "On-line recognition of hand-printed numerals", Annual Report of the Engineering Research I n s t i -tute, Faculty of Engineering, University of Tokyo, Vol. 30, revised August 3, 1971. [19] G. Gail l a t , "An on-line character recognizer with learning capabil-i t i e s " , Proc. of Second International Joint Conference on Pattern Recognition, Copenhagen, Denmark, pp. 305-306, August 1974. [20] G. Groner, "Real-time recognition of handprinted text", AFIPS Proc. FJCC, Vol. 29, pp. 591-601, 1966. [21] G. Groner, "Real-time recognition of handprinted symbols", In Pattern  Recognition (L. Kanal, ed.), Thompson Book Co., 1968. [22] G. Groner, J. Heafner and T. Robinson, "On-line computer recognition of handprinted Chinese characters as a terminal aid", IEEE Trans, on Electronics Computers, Vol. EC-8, No. 6, pp. 856-860, December 1967. [23] A. Hussain, G. Toussaint and R. Donaldson, "Results obtained using a simple character recognition procedure on Munson's handprinted data", IEEE Trans, on Computers, Vol. C-21, No. 2, pp. 201-205, February 1972. [24] T. Ichikawa, "An associative mechanism based on coding theory and i t s application to pattern recognition", Proc. of the Conference on Computer Graphics, Pattern Recognition & Data Structure, pp. 14-16, May 1975. [25] T. Ichikawa and J. Yoshida, "On-Line Recognition of handprinted characters with associative read-out of patterns in a memory", Proc. of Second International Joint Conference on Pattern Recog-nition, pp. 206-207, August 1974. [26] L. Kanal, "Interactive pattern analysis and cla s s i f i c a t i o n systems: a survey and commentary", Proc. IEEE, Vol. 60, No. 10, pp. 1200-1215, October 1972. [27] L. Kanal, "Patterns in pattern recognition: 1968-1974", IEEE Trans. On Information Theory, Vol. IT-20, No. 6, pp. 697-722, November 1974. 104 [28] L. Kanal and B. Chandrasekaran, "On l i n g u i s t i c , s t a t i s t i c a l and mixed models for pattern recognition", In Frontiers of Pattern Recog-nition (S. Watanabe, ed.), Academic Press, New York, 1972. [29] C. Kerpelman, ed., "Proposed American national standard: presenta-tion of alphameric characters for information processing", Communi-cations of the ACM, Vol. 12, No. 12, pp. 696-698, December 1969. [30] M. Levine, "Feature extraction: a survey", Proc. IEEE, Vol. 57, No. 8, pp. 1391-1407, August 1969. [31] G. Miller, "On-line recognition of hand-generated symbols", AFIPS Proc. FJCC, Vol. 35, pp. 399-412, 1969. [32] J. Munson, "Experiment in the recognition of handprinted text, part I - Character recognition", AFIPS Proc. FJCC, Vol. 33, pt. 2, pp. 1125-1138, 1968. [33] G. Nagy, "State of art in pattern recognition" Proc. IEEE, Vol. 56, No. 5, pp. 836-862, May 1968. [34] R. Narasimhan and V. Reddy, "A syntax-aided recognition scheme for handprinted English letters" Pattern Recognition, Vol. 3, No. 4, pp. 345-361, November 1971. [35] J. O'Callaghan, 'X coding approach to pattern recognition", Pattern Recognition, Vol. 2, pp. 199-214, September 1970. [36] J. O'Callaghan, "Problems in on-line character recognition", In Picture Language Machine (S. Kaneff, ed.), Academic Press, New York, 1970. [37] W. Peterson and E. Weldon, Jr., Error-Correcting Codes, Second Ed-i t i o n , The MIT Press, Cambridge, Mass, 1972. [38] V. Powers, "Handwritten character recognition from pen direction", Naval Postgraduate School Technical Report, No. NPS-52PW72041A, April 1972. [39] V. Powers, "On-line recognition of hand-drawn characters from d i r -ectional information", Ph.D. dissertation, University of Michigan, 1970. [40] V. Powers, "Pen direction sequences in character recognition", Pattern Recognition, Vol. 5, pp. 291-302, December 1973. [41] K, Reumann and:A. Witkam, "Optimizing curve segmentation in computer graphics", In International Computing Symposium (A. Guther et a l . , ed.), North Holland Publ. Co. 1974. [42] W. Stallings, "Computer description and recognition of printed Chinese characters", AFIPS Proc. FJCC, Vol. 44, pp. 1015-1025, 1975. 105 [43] W. Teitelman, "Real time recognition of hand-drawn characters", AFIPS Proc. FJCC, Vol. 26, part 1, pp. 559-575, 1964. [44] J. Tou and R. Gonzalez, "Recognition of handwritten characters by topological feature extraction and multilevel categorization", IEEE Trans, on Computers, Vol. G-21, No. 7, pp. 776-785, July 1972. [45] G. Toussaint and R. Donaldson, "Algorithm for recognizing contour-traced handprinted charscters 1', IEEE Trans, on Computers, Vol. C-19, No. 6, pp. 1096-1098, June 1970. [46] L. Uhr, "Flexible l i n g u i s t i c pattern recognition", Pattern Recogni-tion, Vol. 3, No. 4, pp.,363-383, November 1971. [47] J. Ullman, Pattern Recognition Techniques, London Butterworths, London, 1973. [48] T. Young and T. Calvert, Classification, Estimation and Pattern  Recognition, American Elsevier Publ. Co., New York, 1974. 106 APPENDIX A TAELE A - l RELATIONSHIP BETWEEN ( i , j ) AND C 3 > ' 1 2 3 4 5 6 7 8 9 10 11. 1 C -. 2 D P V . X L T ©• J S 3 A H F I N K B G R U Y 4 M E W z 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0065484/manifest

Comment

Related Items