MACHINE RECOGNITION OF INDEPENDENT AND CONTEXTUALLY CONSTRAINED CONTOUR-TRACED HANDPRINTED CHARACTERS by GODFRIED T. TOUSSAINT B.Sc, University of Tulsa, 1968 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE i n the Department of E l e c t r i c a l Engineering We accept t h i s thesis as conforming to the required standard Research Supervisor Members of Committee Acting Head of Department Members of the Department of E l e c t r i c a l Engineering THE UNIVERSITY OF BRITISH COLUMBIA December, 1969 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 the r e q u i r e m e n t s f o r an advanced 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 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 Head o f my Depar tment 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 not 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 . 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 V a n c o u v e r 8, Canada Depa r tment / ABSTRACT A contour-tracing technique o r i g i n a l l y d i v i s e d by Clemens and Mason was modified and used with several d i f f e r e n t c l a s s i f i e r s of varying complexity to recognize upper case handprinted alphabetic characters. An analysis and comparison of the various c l a s s i f i e r s , with the modifications introduced to handle v a r i a b l e length feature vectors, i s presented. On independent characters, one e a s i l y r e a l i z e d suboptimum parametric c l a s s i f i e r y ielded recognition accuracies which compare favourably with other published r e s u l t s . A d d i t i o n a l simple tests on commonly confused characters improved r e s u l t s s i g n i f i c a n t l y as did use of contextual c o n s t r a i n t s . In addition, the above c l a s s i f i e r uses much less storage capacity than a non-parametric optimum Bayes c l a s s i f i e r and performs s i g n i f i c a n t l y better than the optimum c l a s s i f i e r when t r a i n i n g and t e s t i n g data are l i m i t e d . The optimum decision on a s t r i n g of m contextually constrained characters, each having a variable-length feature vector, i s derived. A computationally e f f i c i e n t algorithm, based on this equation, was developed and tested with monogram, bigram and trigram contextual constraints of English text. A marked improvement i n recognition accuracy was noted over the case when contextual constraints were not used, and a trade-off was observed not only between the order of contextual information used and the number of measurements taken, but also between the order of context and the value of a parameter ds which indicates the complexity of the c l a s s i f i c a t i o n algorithm. TABLE OF CONTENTS Page ABSTRACT i i TABLE OF CONTENTS i i i LIST OF ILLUSTRATIONS v ACKNOWLEDGEMENT ' v i I . INTRODUCTION 1 1.1 P u r p o s e o f R e s e a r c h 1 1.2 Review o f P r e v i o u s R e s e a r c h 1 1.3 Scope o f t h e T h e s i s 3 I I . THE PATTERN-RECOGNITION PROBLEM '. 5 2.1 I n t r o d u c t i o n 5 2.2 T r a n s d u c e r s 7 2.3 F e a t u r e E x t r a c t i o n 7 2.3.1 I n t r o d u c t i o n . . . 7 2.3.2 C o n t o u r T r a c i n g 8 2.3.3 Smoothing 11 2.3.4 G e s t a l t V a r i a b l e s 12 2.3.5 F e a t u r e V e c t o r F o r m a t i o n 12 2.4 C l a s s i f i c a t i o n 15 2.4.1 I n t r o d u c t i o n 15 2.4.2 The T a b l e Look-up Method... 16 2.4.3 The P a r a m e t r i c Bayes Ap p r o a c h 17 2.4.4 Minimum E u c l i d e a n D i s t a n c e from t h e Means 18 2.4.5 A N o n - E u c l i d e a n D i s t a n c e C l a s s i f i e r 18 2.4.6 Some I m p o r t a n t I n t e r r e l a t i o n s h i p s 19 2.4.7 H a n d l i n g F e a t u r e V e c t o r s i n M u l t i s p a c e 21 2.4.8 A P a r a l l e l - s e q u e n t i a l C l a s s i f i e r 23 2.4.9 Compound D e c i s i o n s f o r S t r i n g s o f Dependent C h a r a c t e r s 23 2.5 T r a i n i n g and S t o r a g e R e q u i r e m e n t s 25 I I . EXPERIMENTS . . . 27 i i i 3.1 I n t r o d u c t i o n 27 3.2 D e s c r i p t i o n o f t h e Data 28 3.3 E x p e r i m e n t s on Independent C h a r a c t e r s 30 3.4 E x p e r i m e n t s on Dependent C h a r a c t e r s 31 IV. RESULTS 33 4.1 I n t r o d u c t i o n 33 4.2 Independent C h a r a c t e r s 33 4.3 Dependent C h a r a c t e r s 37 V. DISCUSSION AND CONCLUSIONS 40 , 5.1 E v a l u a t i o n o f R e s u l t s 40 5.2 S u g g e s t i o n s f o r F u r t h e r R e s e a r c h 44 5.3 Summary o f C o n c l u s i o n s 46 REFERENCES • 47 i v LIST OF ILLUSTRATIONS FIGURE Page 1 The general pattern-recognition problem 6 2 I l l u s t r a t i n g the contour trace. Search for the character begins at S. The CONTOUR mode begins at C 10 3 CODE and COORD words for "C" 14 4 Some decision boundaries between two pattern-class-means i n two dimensional space 22 5 Alphabets from seven persons. The sixth and seventh alphabets are from PERSONS 1 and 2, r e s p e c t i v e l y 29 6 M i s c l a s s i f i c a t i o n and r e j e c t p r o b a b i l i t i e s i n per cent.. 34 7 Scans and decision trees f o r re s o l v i n g character con-fusions 36 8 Per cent error p r o b a b i l i t y as a function of ds for the 4-PAD te s t i n g data 38 9 Per cent error p r o b a b i l i t y as a function of the order of contextual information used 39 10 I l l u s t r a t i n g a technique for c l o s i n g small breaks i n broken characters 45 v ACKNOWLEDGEMENT Grateful acknowledgement i s given to the National Research Council of Canada, The Defence Research Board of Canada, and the B r i t i s h Columbia Telephone Company for the f i n a n c i a l support received under Grants NRC A-3308, and DRB 2801-30, and for the Graduate Scholarship, r e s p e c t i v e l y . I would l i k e to thank Dr. Robert W. Donaldson, the supervisor of t h i s p r oject, for h i s generous counsel, and constant a v a i l a b i l i t y and encourage-ment. I would l i k e to thank Dr. Michael P. Beddoes for reading the manuscript and for h i s h e l p f u l suggestions. I am g r a t e f u l to the graduate students of the E l e c t r i c a l Engineering Department of The U n i v e r s i t y of B r i t i s h Columbia for providing the handprinted character samples and for p a r t i c i p a t i n g i n the human recognition t e s t s . I am also g r a t e f u l to Messrs. J . Cavers, M. Ito and S. Hussain for the many i n t e r e s t i n g discussions over N+1 cups of coffee. I would also l i k e to thank my wife, N.inozka, for her encouragement and for operating the projector during the tedious preparation of the data, Miss Beverly Harasymchuk for typing the manuscript,-and Messrs. John Cossalter, Tom Fletcher, and Toomas Vilmansen, for proofreading the manuscript. v i 1 I. INTRODUCTION 1.1 Purpose of Research The purpose of th i s research was to: (1) assess the s u i t a b i l i t y of a simple contour-analysis feature-extraction scheme for recognizing hand-printed upper case characters when the feature vector i s operated on by c l a s s i f i e r s of varying degrees of complexity; (2) improve the r e s u l t s of the c l a s s i f i e r s above by using contextual constraints and a d d i t i o n a l simple class-dependent tests to d i f f e r e n t i a t e commonly confused characters; and (3) observe t r a d e - o f f s , i f any, between the number of measurements, complexity of the basic c l a s s i f i e r and order of contextual information used when the av a i l a b l e storage i s l i m i t e d . 1.2 Review of Previous Research The great s p a t i a l v a r i a b i l i t y of handprinted characters, even among samples from the same person, has lead many researchers to explore unique methods of feature extraction and c l a s s i f i c a t i o n . In many of these cases the preprocessing. i s of considerable complexity and the dimensionality of the feature vectors i s large, t y p i c a l l y greater than 100, making c l a s s i f i c a t i o n d i f f i c u l t [1-3]. Some of the researchers such as Kamentsky [4], Bakis et a l . [5], and Greanias et a l . [6] have considered only numeric character sets, and others such as Roberts [7], Highleyman [8] and Gr imsdale et a l . [9] used the same data set for t r a i n i n g and t e s t i n g which i s now known to y i e l d an overoptimistic p r e d i c t i o n of performance. In 1965 Clemens [10, 11] devised a r e l a t i v e l y simple contour tracing algorithm to recognize machine-printed characters. The r e l a t i v e ease of imple-mentation of the scheme and the low dimensionality of the feature vectors, t y p i c a l l y about 20, attracted researchers of handprinted character recognition. In 1966 Chodrow et a l . [12] reported poor r e s u l t s i n applying Clemens' techniaue to alphabetic handprinted characters. In 1968 Munson [13] obtained equally poor r e s u l t s using a s l i g h t modification of Clemens' technique. Since then,letter-r e s u l t s have been reported by Johnson et a l . [14], Munson [13, 15] and Knoll [16] using more complicated techniques, but there seems l i t t l e hope of a r r i v i n g at very s a t i s f a c t o r y r e s u l t s without the use of contextual information In the past, the use of contextual constraints to improve character recognition has been scant and l i m i t e d generally to the d i c t i o n a r y look-up method and the Markov approach. In 1959 Bledsoe and Browning [1] used the character confidences of a word together with a vocabulary of English words of the--length i n question to make a decision on the word. Cornew [17] applied an extensive d i c t i o n a r y look-up method to s p e l l i n g c o r r e c t i o n and A l t e r [18] used a sequential decoding method for determining which of many possible symbol sequences i s i n some sense most l i k e l y to have been intended given the sequence a c t u a l l y received.. The disadvantages of these methods are that a d i c t i o n a r y of p r a c t i c a l s i z e takes up too much storage, and not enough information i s used from the measurements. In fact these methods often operate on the output of a c l a s s i f i e r which contains the d e c i s i o n , rather than the category l i k e l i h o o d s , f or the input character. The Markov approach i s based on the assumption that the true i d e n t i t y of a character i s dependent on the true i d e n t i t i e s of neighbouring characters. Carlson [19] used the Markov approach to replace missing characters from names on the basis of the most probable trigrams. Edwards and Chambers [20] used c o n d i t i o n a l bigrams i n a machine-printed character recognition scheme,which uses the previous d e c i s i o n and a present choice based on the two categories having highest l i k e l i hoods, a c t u a l l y r e s u l t i n g i n a decrease i n performance for high i n i t i a l recog-n i t i o n accuracies. In 1966 Abend [21, 22] t h e o r e t i c a l l y solved the problem of optimum use of context using compound decision theory. P r a c t i c a l l y , however, t h i s s o l u t i o n i s v i r t u a l l y unrealizable and s i m p l i f y i n g assumptions have to be made. One way to s i m p l i f y the problem i s to assume Markov dependence among the characters to be recognized and then use sequential compound decision theory to make a d e c i s i o n on one character at a time [23]. Another way to s i m p l i f y the problem i s to have as the c l a s s i f i e r output only a fixed number of choice cat-egories having the highest confidence. This s i m p l i f i c a t i o n was made by Duda~- and Hart [24] in a handprinted character recognition scheme using both syntax and.semantics. However, the study.was made only on the FORTRAN language and the confidences used were not equal to the category l i k e l i h o o d s . Similar studies need to be made on the much more d i f f i c u l t problem of handling natural language such as English. In addition,, s i m i l a r d ecision algorithms need to be derived for handling variable-length feature vectors which r e s u l t from some feature extraction schemes such as the one used i n t h i s t h e s i s . 1.3 Scope of the Thesis In t h i s t h e s i s , the complete pattern recognition system shown i n F i g . 1 i s considered. The input to the system consists of upper case handprinted alphabetic characters, binary quantized on 50 x 50 arrays. The transducer, i n t h i s case, consists of an enlarger projector and keypunch operators. Two types of feature e x t r a c t i o n are performed on the data, for comparison, by a method of contour t r a c i n g based on Clemens' technique. Various algorithms are used i n the c l a s s i f i e r stage e i t h e r by themselves or making use of contextual information or t e n t a t i v e decision making followed by a d d i t i o n a l feature extrac-ti o n before proceeding to a f i n a l d ecision. The t h e o r e t i c a l aspects of the techniques used to solve the pattern recognition problem are treated i n Chapter I I . Some aspects regarding the square, contour trace not treated before i n the l i t e r a t u r e , i ncluding the equations for i t s implementation, are discussed i n section 2.3. Section 2.4 b r i e f l y reviews some of the simple c l a s s i f i c a t i o n techniques used i n the past and d e s c r i b e s t h e n e c e s s a r y changes needed t o h a n d l e v a r i a b l e l e n g t h f e a t u r e v e c t o r s . S u b s e c t i o n 2.4.5 d e s c r i b e s a n o n - E u c l i d e a n d i s t a n c e c l a s s i f i e r f o r w h i c h , t o t h e a u t h o r ' s knowledge, no c h a r a c t e r r e c o g n i t i o n e x p e r i m e n t s have been p r e v i o u s l y r e p o r t e d . S u b s e c t i o n 2.4.6 d e s c r i b e s some o f t h e i m p o r t a n t i n t e r r e l a t i o n s h i p s , n o t o b s e r v e d i n the l i t e r a t u r e , between t h e v a r i o u s c l a s s i f i e r s , and p r e s e n t s an i n t e r e s t i n g theorem and p r o o f c o n c e r n i n g t h e e q u i v a l e n c e between a l i n e a r d e c i s i o n boundary and t h e n o n l i n e a r d e c i s i o n boundary o f t h e c l a s s i f i e r o f s u b s e c t i o n 2.4.5. S u b s e c t i o n 2.4.8 d e s c r i b e s a p a r a l l e l - s e q u e n t i a l mode of c l a s s i f i c a t i o n f o r w h i c h the sca n s and d e c i s i o n t r e e s o f s e c t i o n 4.2 were d e s i g n e d . I t was n e c e s s a r y t o o b t a i n the e q u a t i o n , n o t a v a i l a b l e i n t h e l i t e r a -t u r e , f o r t h e optimum d e c i s i o n on a s t r i n g o f m c h a r a c t e r s h a v i n g v a r i a b l e l e n g t h f e a t u r e v e c t o r s . T h i s e q u a t i o n i s d e r i v e d i n s u b s e c t i o n 2.4.9 and a n . a p p a r e n t l y v e r y s u c c e s s f u l m o d i f i c a t i o n i s made f o r d e c r e a s i n g t h e amount o f c o m p u t a t i o n . The e x p e r i m e n t s a r e d e s c r i b e d i n C h a p t e r I I I . I n t h e p a s t , two methods have been used w i t h r e l a t i v e l y s m a l l d a t a s e t s ; t h e f i r s t does n o t use t h e d a t a e f f i c i e n t l y and t h e second needs a v e r y l a r g e amount o f c o m p u t a t i o n . A new e x p e r i m e n t a l p r o c e d u r e i s d e s c r i b e d w h i c h i s a compromise between t h e two methods above. The r e s u l t s a r e g i v e n i n C h a p t e r IV and t h e d i s c u s s i o n and c o n c l u s i o n s a r e t r e a t e d i n C h a p t e r V. 5 I I . THE PATTERN-RECOGNITION PROBLEM 2.1 I n t r o d u c t i o n The g e n e r a l p a t t e r n r e c o g n i t i o n p r o b l e m i s e x p r e s s e d i n t h e b l o c k d i a g r a m i n F i g . 1. The r e a l w o r l d d a t a s e t i s composed of a p o s s i b l y . i n f i n i t e number of p a t t e r n s w h i c h a r e t o be c l a s s i f i e d i n t o a f i n i t e number of c a t e g o r i e s i n d e c i s i o n . s p a c e . The t r a n s d u c e r c o n v e r t s a p a t t e r n from t h e r e a l w o r l d i n t o a p a t t e r n i n image space by d i g i t i z a t i o n and q u a n t i z a t i o n w h i c h c o n t r i b u t e t o the h i g h d i m e n s i o n a l i t y o f the image space. The f e a t u r e e x t r a c t o r maps t h e image space i n t o t h e , u s u a l l y much l o w e r d i m e n s i o n a l , measurement space. F e a t u r e e x t r a c t i o n i s e f f e c t e d by d e s i g n i n g t h e mapping i n such a way t h a t t h e r e e x i s t s t r o n g i n t r a - c a t e g o r y s i m i l a r i t i e s and s t r o n g i n t e r - c a t e g o r y d i s s i m i l a r i t i e s among f e a t u r e v e c t o r s . I n some c a s e s t h e t r a n s d u c e r and f e a t u r e e x t r a c t o r a r e d i f f i c u l t t o s e p a r a t e . The c l a s s i f i e r a c t s on measurement space and makes e i t h e r a t e n t a t i v e o r f i n a l d e c i s i o n e i t h e r s o l e l y on t h e b a s i s o f t h e f e a t u r e v e c t o r s o r w i t h t h e h e l p o f c o n t e x t u a l i n f o r m a t i o n . L e t t h e f e a t u r e s from p a t t e r n c l a s s C. be d e s c r i b e d by a v e c t o r • i X* = ( x ^ ,x^,. . . • I f P(C ) and P (x|c ) d e n o t e , r e s p e c t i v e l y , t h e p r o b a b i l i t y of C_^ and t h e p r o b a b i l i t y of % c o n d i t i o n e d on C_^ , t h e n t h e p r o b a b i l i t y o f m i s c l a s s i f i c a t i o n i s m i n i m i z e d by c h o o s i n g i t o ma x i m i z e any monotone i n c r e a s i n g f u n c t i o n o f R. = P(X"|C.) P(C.) = P ( x n , x ,..,x,|C.) P(C.) . (1) I n most h a n d p r i n t e d c h a r a c t e r r e c o g n i t i o n schemes t h e d i m e n s i o n a l i t y d o f I i s l a r g e ; t y p i c a l l y d > 100. Even i f t h e components o f ^ a r e b i n a r y , l e a r n i n g t h e s t a t i s t i c s o f 2 ^ " d i f f e r e n t p r o b a b i l i t i e s P(]^|C ) f o r each i r e q u i r e s many t r a i n i n g samples and much s t o r a g e c a p a c i t y . When t h e d components x ^ o f 5 a r e s t a t i s t i c a l l y i n d e p e n d e n t , however, d P($|C.) P(C.) = n P(x, |C.) P(C.) (2) X X I T K. X X k = l CONTEXTUAL INFORMATION IMAGE SPACE TRANSDUCER /a / A FEATURE EXTRACTOR MEASUREMENT SPACE x, DECISION SPACE CLASSIFIER FINAL DECISION /-- 7 /? TENTATIVE DECISION F i g . I The g e n e r a l p a t t e r n - r e c o g n i t i o n p r o b l e m . 7 i n w h i c h c a s e i t i s n e c e s s a r y to l e a r n and s t o r e o n l y the d terms P ( x |C.) k r f o r each i . Two p o s s i b i l i t i e s now a r i s e . (A) I f t h e components a r e not s t r o n g l y i n t e r d e p e n d e n t , and i f t h e r e a r e not enough samples to e s t i m a t e P(X|C ) s u f f i c i e n t l y w e l l when th e t r u e d i s t r i b u t i o n i s not known, i t may be b e s t t o assume ( 2 ) , or t o use some o t h e r suboptimum c l a s s i f i e r w h i c h can be t r a i n e d on fewer samples t h a n a r e needed to e s t i m a t e P(X|C ). (B) Even when P(x|c\) i s known a suboptimum c l a s s i f i e r w h i c h r e q u i r e s l e s s s t o r a g e c a p a c i t y t h a n t h e optimum c l a s s i f i e r may be d e s i r a b l e . Unused s t o r a g e can t h e n be o c c u p i e d by c o n t e x t u a l i n f o r m a t i o n and more s o p h i s t i c a t e d c l a s s i f i c a t i o n a l g o r i t h m s , b o t h o f w h i c h can e f f e c t c o n s i d e r a b l e improvement i n r e c o g n i t i o n a c c u r a c y [13, 18, 23, 2 4 ] . Thus, f e a t u r e e x t r a c t i o n schemes w h i c h r e t a i n t h o s e f e a t u r e s e s s e n t i a l f o r r e c o g n i t i o n w h i l e k e e p i n g d s m a l l a r e a t t r a c t i v e , b e c a u s e n o t o n l y do t h e y s i m p l i f y t h e c l a s s i f i e r i n terms o f l e s s s t o r a g e and c o m p u t a t i o n , b u t t h e r e l a t i v e i n d e p e n d e n c e of t h e x 's encourages t h e use o f ( 2 ) , f u r t h e r s i m p l i f y i n g t h e p r o b l e m . 2.2 T r a n s d u c e r s T r a n s d u c e r s can be r o u g h l y d i v i d e d i n t o two g r o u p s . I n one k i n d o n l y d i g i t i z a t i o n and q u a n t i z a t i o n a r e p e r f o r m e d and t h e d i f f e r e n c e between t h e p a t t e r n i n t h e r e a l w o r l d and i n image space i s m i n i m i z e d . I n the o t h e r k i n d a c t u a l f e a t u r e e x t r a c t i o n i s done d u r i n g t r a n s d u c i n g , t h u s mapping t h e r e a l w o r l d d i r e c t l y i n t o measurement space. E i t h e r scheme can be used w i t h c o n t o u r t r a c i n g . 2.3 F e a t u r e E x t r a c t i o n 2.3.1 I n t r o d u c t i o n There e x i s t s t o d a y no g e n e r a l t h e o r y t h a t w i l l y i e l d an o p t i m a l s e t o f f e a t u r e s f o r a g i v e n p a t t e r n r e c o g n i t i o n p r o b l e m . Hence t h e r e i s some j u s t i f i c a t i o n i n a l l o w i n g d e s i g n e r s t o use f e a t u r e s w h i c h they t h i n k might 8 e x t r a c t t h e s i g n i f i c a n t i n f o r m a t i o n from p a t t e r n s . I n the p a s t some s u c c e s s has been a c h i e v e d t h r o u g h i n t u i t i v e a p p l i c a t i o n of i d e a s from b i o l o g i c a l p r o -t o t y p e s but t h e f i e l d r emains an a r t r a t h e r than a s c i e n c e [ 2 5 ] . I t i s w e l l known t h a t t h e c o n t o u r s o f a p a t t e r n c o n t a i n most o f t h e i n f o r m a t i o n needed t o r e c o g n i z e i t [5, 6, 10-12, 25-3 2 ] , The f e a t u r e , e x t r a c t i o n a l g o r i t h m s used i n t h i s t h e s i s a r e based on two o b s e r v a t i o n s . F i r s t , r e a s o n a b l y l e g i b l e Roman c h a r a c t e r s a r e r e c o g n i z a b l e s o l e l y on t h e b a s i s of t h e i r e x t e r n a l c o n t o u r . Second, c o n f u s i o n between c h a r a c t e r s i s not random, b u t h i g h l y s t r u c t u r e d . F o r example, i n t h e e x p e r i m e n t s d e s c r i b e d below con-f u s i o n s a r o s e m o s t l y between t h e c h a r a c t e r s A and B., K and X, 0 and 0, and B and D. A c c o r d i n g l y , a c h a r a c t e r ' s o u t s i d e c o n t o u r was used to g e n e r a t e a b i n a r y v e c t o r X w h i c h was t h e n c l a s s i f i e d e i t h e r as a s i n g l e c h a r a c t e r , or as one o f a group o f c h a r a c t e r s n o t e a s i l y d i s t i n g u i s h e d s o l e l y on t h e b a s i s o f X. I n t h i s l a t t e r c a s e , s i m p l e c l a s s - d e p e n d e n t t e s t s were d e s i g n e d t o e f f e c t f i n a l r e c o g n i t i o n of the unknown c h a r a c t e r . The t r a n s f o r m a t i o n o f c h a r a c t e r c o n t o u r s i n t o b i n a r y v e c t o r s i s a m o d i f i c a t i o n of t h e one used by Clemens and Mason [10, 11, 25-27] and by T r o x e l [28, 29] f o r r e c o g n i z i n g m a c h i n e - p r i n t e d c h a r a c t e r s . I n a d d i t i o n to b e i n g easy t o implement, t h e t r a n s f o r m a t i o n y i e l d s a f e a t u r e v e c t o r o f s m a l l d i m e n s i o n a l i t y . 2.3.2 C o n t o u r T r a c i n g A l l c o n t o u r t r a c i n g a l g o r i t h m s a r e s i m i l a r i n t h a t t h e y e f f e c t , i n some manner, a s t e p w i s e t r a c e o f t h e b l a c k - w h i t e boundary .of a p a t t e r n . There a r e , however, s e v e r a l ways o f i m p l e m e n t i n g t h e s t e p w i s e t r a c e each s e r v i n g a s l i g h t l y d i f f e r e n t p u r p o s e and r e q u i r i n g d i f f e r e n t l o c a l p r o p e r t i e s o f t h e p a t t e r n s t o be t r a c e d [6, 10, 26, 29, 3 1 - 3 3 ] . G r e a n i a s e t a l . [6] was one o f t h e f i r s t to use c i r c u l a r t r a c i n g . I n h i s Ph.D. t h e s i s Clemens [10] i n t r o d u c e d h e x a g o n a l t r a c i n g , a simple, o p e r a t i o n r e q u i r i n g l i t t l e l o g i c . Later Mason and Clemens [26] used the square trace which i s used in t h i s thesis. The algorithm consists of making a l e f t turn upon entering a black square and a r i g h t turn upon entering a white square as i l l u s t r a t e d i n F i g . 2. Let R(x,y) be the image matrix composed of elements which can take on the values 'zero' or 'one', where the set of 'ones' i s the quantized representation of some pattern P(p ,p ,...,p ). D e f i n i t i o n Two elements of R are adj acent i f they d i f f e r by 1 in one of t h e i r coordinates. D e f i n i t i o n Two elements of R are diagonally adjacent i f they d i f f e r by 1 i n both of t h e i r coordinates. D e f i n i t i o n A pattern P i s connected i f , and only i f , given any two elements p^ and p , there e x i s t s a sequence of elements (p^»P2>•••»P^) where P j = P ^ a n d p = p. such that p and p ,-. are adjacent for 1 < m < Z—l. F j pm Fm+1 J — -Equations describing the square trace were derived i n order to compare them with those for hexagonal tra c i n g i n [10]. Let Cx^, Y^) a n ~ ( x k _ ^ > Y ^ - l ^ be the coordinates of the present and past l o c a t i o n of the scanning spot. The next l o c a t i o n on R i s given by the following 3-state equations: ^ 1 = ^ + ' n y k - y k _ 1 ] [ l - 2 R ( X k , y k ) ] } (3) ^ k + i = y k + { [ x k - x k - i ] [ 2 R ( x k ' V - 1 ] } ( 4 ) Although the square trace i s geometrically simpler than the hexagonal trace, the equations (3) and (4) needed to implement i t are s l i g h t l y more.complex than the 2-state equations i n [10] . The hexagonal method i s more suited to contour tra c i n g patterns i n the r e a l world because points are interrogated only once, thus combatting the. e f f e c t s of j i t - t e r . Troxel [29] modified the square trace to combat j i t t e r e f f e c t s also. One. advantage of the square trace i s that i t can completely contour trace c e r t a i n patterns containing sections which are only diagonally adjacent which cannot be traced completely by the hexagonal method. However, both schemes w i l l contour trace any pattern that i s connected i n the sense defined above, and the choice of the algorithm i n t h i s thesis i s s t r i c t l y a r b i t r a r y . An analogous theorem to that given i n [10] holds for the square trace. 11 Theorem If the square tracing routine i s started at the lowest black point of a non-white column, (x,y), i t s f i r s t move i s to (x-1, y) and the trace w i l l always return to (x-1, y) a f t e r tracing the outside contour of a connected pattern exactly once. This theorem can be i n d u c t i v e l y proved by s t a r t i n g with a pattern co n s i s t i n g of only one square and constructing a general connected pattern by adding other adjacent black squares. A formal proof, however, w i l l not be given here. 2.3.3 Smoothing The same two-dimensional hy s t e r e s i s smoothing technique used by Clemens [10, 25, 26] was used here. Let x^ and x^-fi be, r e s p e c t i v e l y , the s s present and future x-coordinate of the raw character trace. Let x^ and x ^ + ^ be, r e x p e c t i v e l y , the present and future x-coordinate of the smoothed character trace. The algorithm can be described with three interrogations. I f \ < \ + i - V 2 ' t h e n v i = \ + i - V 2 ' " * k + 1 - V 2 ± : :k ± x k + i + V 2> t h e n < + i = v ( 5 ) I f < > \ + i + T x / 2 > t h e n X k + 1 " X k + 1 + V 2> where T^ i s the threshold discussed i n subsection 2.3.5. A s i m i l a r operation i s used for the y d i r e c t i o n . The e f f e c t of t h i s algorithm i s to smooth out a l l extraneous extrema. The s i z e of the extraneous extrema i s determined by the r e l a t i v e s i z e of T^ and T^ with respect to the height and width, r e s p e c t i v e l y , of the character. .12 2.3.4 G e s t a l t V a r i a b l e s V a r i a b l e s w h i c h do n o t p r o v i d e t h e k i n d o f i n f o r m a t i o n needed t o r e c o n s t r u c t f a i r l y w e l l the o r i g i n a l p a t t e r n but w h i c h n e v e r t h e l e s s a b s t r a c t i m p o r t a n t p r o p e r t i e s o f the shape as a whole a r e known as g e s t a l t v a r i a b l e s . Examples of g e s t a l t v a r i a b l e s a r e , t h e number o f s i d e s i n a p o l y g o n , t h e h e i g h t t o w i d t h r a t i o (Ii/W) o f a c h a r a c t e r , o r t h e r a t i o o f the p e r i m e t e r t o t h e s q u a r e r o o t o f t h e a r e a o f a p a t t e r n ( P / / A ) [ 3 0 ] . Clemens used H/W v e r y s u c c e s s f u l l y on m a c h i n e - p r i n t e d c h a r a c t e r s w h i c h y i e l d e d f o u r v i r t u a l l y non- ' o v e r l a p p i n g d i s t r i b u t i o n s . I t was a n t i c i p a t e d t h a t f o r h a n d p r i n t e d c h a r a c t e r s H/W would n o t be s a t i s f a c t o r y and so P//K, w h i c h i s a measure o f t h e d i s p e r s i o n o f a shape, was t r i e d as w e l l . A l t h o u g h P//~Twas s l i g h t l y b e t t e r t h a n H/W as f a r as o v e r l a p p i n g d i s t r i b u t i o n s a r e c o n c e r n e d , t h e amount o f c o m p u t a t i o n needed f o r i t was too g r e a t t o j u s t i f y i t s improvement. I n a d d i t i o n P//K o n l y h e l p e d i n s e p a r a t i n g c a t e g o r i e s w h i c h d i d n o t need h e l p . A c c o r d i n g l y i t was d e c i d e d t o abandon g e s t a l t v a r i a b l e s and l o o k i n s t e a d toward t h e w h i t e -t o - b l a c k t r a n s i t i o n s c a n s o f s e c t i o n 4.2 t o h e l p w i t h t h e commonly c o n f u s e d c h a r a c t e r s r e s u l t i n g from c o n t o u r t r a c i n g a l o n e . 2.3.5 F e a t u r e V e c t o r F o r m a t i o n D u r i n g t h e SEARCH mode ( F i g . 2) t h e s c a n n i n g s p o t moves, p o i n t by' p o i n t , from t h e b o t t o m t o t h e t o p o f t h e l e f t most column, and s u c c e s s i v e l y r e p e a t s t h i s p r o c e d u r e on t h e column i m m e d i a t e l y t o the r i g h t o f t h e column p r e v i o u s l y s c a n n e d , u n t i l t h e f i r s t b l a c k p o i n t i s f o u n d . Upon l o c a t i n g t h i s p o i n t , t h e s c a n n e r e n t e r s t h e CONTOUR mode, i n w h i c h t h e s c a n n i n g spot moves a c c o r d i n g t o t h e s q u a r e t r a c e d e s c r i b e d e a r l i e r and t e r m i n a t e s when i t co m p l e t e s i t s t r a c e around t h e o u t s i d e o f a c h a r a c t e r and r e t u r n s t o i t s s t a r t i n g p o i n t . A f t e r the c h a r a c t e r has been t r a c e d once t h e r e c t a n g l e s u r r o u n d i n g 13 t h e c h a r a c t e r i s d i v i d e d i n t o e i t h e r f o u r o r s i x e q u a l - s i z e d s u b r e c t a n g l e s whose s i z e depends on t h e h e i g h t and w i d t h o f t h e l e t t e r (see F i g . 3 ) . I n p r e v i o u s r e s e a r c h o n l y t he f o u r - r e c t a n g l e s u b d i v i s i o n has been used b u t i t was a n t i -c i p a t e d t h a t l e s s i n f o r m a t i o n from the m i d d l e o f c h a r a c t e r s would be l o s t , due t o q u a n t i z a t i o n , w i t h a s i x - r e c t a n g l e s u b d i v i s i o n . To f u r t h e r r e d u c e q u a n t i z a t i o n e r r o r s t h e s u b d i v i s i o n s a r e a s s i g n e d 3 - b i t l a b e l s i n such a manner t h a t t h e Hamming d i s t a n c e between any two l a b e l s i s e q u a l t o t h e number o f r e c t a n g l e s between t h e two l a b e l s , v e r t i c a l l y and/or h o r i z o n t a l l y . A y t h r e s h o l d e q u a l t o o n e - h a l f each r e c t a n g l e ' s h e i g h t and an x t h r e s h o l d e q u a l t o o n e - h a l f each r e c t a n g l e ' s w i d t h a r e d e f i n e d and t h e c h a r a c t e r i s c o n t o u r t r a c e d f o r a second t i m e . Whenever the x. c o - o r d i n a t e o f t h e s c a n n i n g s p o t r e a c h e s a l o c a l extremum and moves i n the o p p o s i t e d i r e c t i o n t o a p o i n t one t h r e s h o l d away from t h e r e s u l t i n g extremum, t h e r e s u l t i n g p o i n t i s d e s i g n a t e d as e i t h e r an x o r x . .Analogous comments a p p l y t o t h e y c o - o r d i n a t e max mm o f t h e s c a n n i n g s p o t . The s t a r t i n g p o i n t o f t h e CONTOUR mode i s r e g a r d e d a s.an x'. . The CODE word f o r a c h a r a c t e r c o n s i s t s o f a 1 f o l l o w e d by b i n a r y mm d i g i t s whose o r d e r c o i n c i d e s w i t h t h e o r d e r i n w h i c h extrema o c c u r d u r i n g c o n t o u r t r a c i n g ; 1 denotes x - e x t r e m a , w h i l e 0 d e n o t e s y-extrema. The o r d e r i n g o f t h e b i n a r y l a b e l s o f t h e r e c t a n g l e s i n a c c o r d a n c e w i t h t h e r e c t a n g l e s i n w h i c h extrema f a l l i n eve n t sequence c o n s t i t u t e s t he COORD word. The f e a t u r e v e c t o r c o n s i s t s .of t h e c o n c a t e n a t i o n of t h e CODE and COORD words. F i g . 3 shows the CODE and COORD words f o r "C". F u r t h e r d e t a i l s r e l a t i n g t o CODE and COORD w o r d . g e n e r a t i o n appear e l s e w h e r e [10, 11, 25-2 9 ] . 14 01 11 110 111 Xm ax\ \ \ ^ Xmin "*£>Am(2X Ymax A/ Ymln\ \ / /Ymax / / 1 0 0 101 Ymin V.. . \ v Xmin OYmin PYmax *&&Xmax Ymax 00 10 START "CONTOUR" MODE ooo 001 CODE WORD 10111 COORD WORD 0 0,11,1100. 10 / / / ~ -v CODE WORD 1001010010 COORD WORD 000, 111, 111, 111,110,000, 001,001,001,000 F i g . 3 CODE and COORD words for "C". 15 2.4 C l a s s i f i c a t i o n 2.4.]. I n t r o d u c t i o n A g r e a t d e a l o f t h e o r y has been d e v e l o p e d d u r i n g the p a s t ten y e a r s i n the f i e l d o f c l a s s i f i c a t i o n t h e o r y [ 2 7 ] . Most c l a s s i f i e r s f a l l i n t o e i t h e r t h e p a r a l l e l o r s e q u e n t i a l t y p e . I n t h e p a r a l l e l c l a s s i f i e r a s e t o f measure-ments i s f i r s t t a k e n on a p a t t e r n and th e n a d e c i s i o n i s made. The b u l k o f t h e r e f e r e n c e s and t h i s t h e s i s a r e c o n c e r n e d m a i n l y w i t h t h i s t y p e o f c l a s s i f i e r . When t a k i n g measurements i s c o s t l y i t i s d e s i r a b l e t o use s e q u e n t i a l c l a s -s i f i c a t i o n [34] i n w h i c h a f t e r t a k i n g each measurement a d e c i s i o n i s made e i t h e r t o t a k e a n o t h e r measurement o r t o d e c i d e on the i d e n t i t y o f the p a t t e r n based on t h e measurements t a k e n up t o t h a t t i m e . E v e r y c l a s s i f i e r undergoes some k i n d o f t r a i n i n g p h a s e , when t h e p a t t e r n d i s t r i b u t i o n s a r e n o t known a p r i o r i , i n w h i c h e i t h e r t h e d i s t r i b u t i o n s t h e m s e l v e s a r e i m p l i c i t l y o r e x p l i c i t l y e s t i m a t e d ( n o n p a r a m e t r i c t r a i n i n g ) o r i n w h i c h some p a r a m e t e r s of t h e d i s t r i b u t i o n s a r e e s t i m a t e d ( p a r a m e t r i c t r a i n i n g ) . I n p a s t work Clemens [ 1 0 ] , Chodrow [ 1 2 ] , and Munson [13] a l l a p p l i e d a t a b l e l o o k - u p c l a s s i f i c a t i o n scheme t o the' f e a t u r e v e c t o r s . I n t h i s s e c t i o n t h e b a s i c form o f t h r e e p a r a m e t r i c c l a s s i f i e r s u s e d , as w e l l as t h e t a b l e look-uD method, a r e d e s c r i b e d . F o r c l a r i t y , more m e a n i n g f u l c o m p a r i s o n , and g e o m e t r i c i n t e r p r e t a t i o n , t h e c l a s s i f i e r s a r e l o o k e d a t from t h e d i s c r i m i n a n t f u n c t i o n p o i n t o f view [35] . F o r R c a t e g o r i e s t h e r e a r e R d i s c r i m i n a n t f u n c t i o n s y i e l d i n g R d i s c r i m i n a n t s o f w h i c h t h e l a r g e s t i s al w a y s chosen as r e p r e s e n t i n g t h e t r u e c a t e g o r y . G i v e n R . d i s c r i m i n a n t f u n c -t i o n s g , ( X ) , g 0 ( X ) , g (X) , f o r any two o f R c a t e g o r i e s i , j t h e e q u a t i o n J. z R o f t h e d e c i s i o n s u r f a c e between t h o s e two c a t e g o r i e s i s g i v e n by g_^(X) - g (X) = 0. F o r s i m p l i c i t y i t w i l l be assumed i n s u b s e c t i o n s 2.4.3 -2.4.5 t h a t a l l f e a t u r e v e c t o r s have t h e same d i m e n s i o n a l i t y and t h a t a l l 16 categories have equal a p r i o r i p r o b a b i l i t i e s . These s p e c i a l cases w i l l be treated i n 2.4.8 and 2.4.9. 2.4.2 The Table Look-up Method The table look-up method (also exact match c l a s s i f i e r ) i s a s p e c i a l case of the Fix and Hodges nonparametric method [36]. Given some fixed number N of t r a i n i n g patterns i n each of R categories a table i s made up containing the NR feature vectors. Nov?, to c l a s s i f y an a r b i t r a r y pattern )t, the feature vectors i n the R t r a i n i n g subsets are pooled and a search i s made of a l l feature vectors having zero-Hamming distance with the a r b i t r a r y pattern. Suppose that of a l l the zero-Hamming distance feature vectors found,n^ belong to C , n to C n to C . We then set 2 2 R R g x(X)'= n± ' g 2(?) = n 2 (6) g R(X) = n R and a de c i s i o n i s made by s e l e c t i n g the largest discriminant. If no zero-Hamming ->-distance feature vectors are found then the pattern X i s rejected. If the categories have some nonuniform a p r i o r i d i s t r i b u t i o n then the table can be set up by using t r a i n i n g subsets of si z e s proportional to the a p r i o r i p r o b a b i l i t i e s or the table can be constructed as above and the discriminants can be m u l t i p l i e d by the a p r i o r i p r o b a b i l i t i e s . Then n 1 , n 0 , n would become 1 2 R n p(C ), n p(C„),..., n p(C ) where p(C.) are estimates of the a p r i o r i probabi-X X Z Z K K 1 l i t i e s P(C^). C l e a r l y t h i s method i s an attempt to estimate the values of P(x|c_^)P(C^) for i = l , R. For a low r e j e c t rate a large number of t r a i n i n g samples are needed, e s p e c i a l l y with patterns of high v a r i a b i l i t y such as handprinted characters. This requires a great deal of storage as well as a r a p i d - a c c e s s memory [ 3 5 ] . T h i s method w i l l be r e f e r r e d t o as a l g o r i t h m ' 8 ' . 2 .4 .3 The P a r a m e t r i c Bayes Approach -> G i v e n a f e a t u r e v e c t o r X i t i s d e s i r e d t o maximize t h e a p o s t e r i o r i , -> p r o b a b i l i t y P(C |X) o v e r i o r an i n c r e a s i n g m onotonic f u n c t i o n o f i t as i n ( 1 ) . From ( 1 ) and ( 2 ) , assuming e q u i p r o b a b l e c h a r a c t e r s a l l w i t h d d i m e n s i o n a l f e a t u r e v e c t o r s and t a k i n g l o g a r i t h m s we get. t h e d i s c r i m i n a n t f u n c t i o n d g. (X) = E lnP(x. |C.) (7) 1 k = l R 1 where t h e P ^ ^ l c ^ ) f ° r i = l > R a n ^ k = l , . . . ,d a r e t h e p a r a m e t e r s o f t h e d i s t r i b u t i o n s P(x|c_j.). When a d i s c r i m i n a n t f u n c t i o n i s l i n e a r , i t s d e c i s i o n boundary i s a h y p e r p l a n e and i t can be v e r y e a s i l y implemented i n terms o f t h r e -s h o l d l o g i c e l e m e n t s [35]. . Any l i n e a r d i s c r i m i n a n t f u n c t i o n can be e x p r e s s e d as a l i n e a r e q u a t i o n i n terms of t h e components o f X as d g. (X) = I co x + co. k = l 1 » k k 1 > d + 1 (8) where t h e o r i e n t a t i o n o f t h e h y p e r p l a n e i s d e t e r m i n e d by t h e x^eights co. , f o r k = l , d, and t h e p o s i t i o n o f t h e h y p e r p l a n e i s d e t e r m i n e d by t h e w e i g h t co_j, c [ + ^ ' I t can be shown [37] t h a t f o r b i n a r y measurements (7) can be w r i t t e n i n t h e form o f (8) where d w - = E l n P ( x . =0|C.) i , d + l k 1 i (9) and co. , = l n P ( x = 1 C.) - l n P ( x = 0 C . ) . l ,k k 1 I k 1 I 18 2.4.4 Minimum E u c l i d e a n D i s t a n c e from t h e Means I n t h e E u c l i d e a n d i s t a n c e c l a s s i f i e r a m e t r i c , monotonic t o t h e E u c l i -dean d i s t a n c e such as t h e sq u a r e o f t h e E u c l i d e a n d i s t a n c e , i s m i n i m i z e d o v e r G\ , i = l , R [35, 3 8 ] . T h i s m e t r i c i s t a k e n between the g i v e n p a t t e r n X and t h e mean o f each c a t e g o r y X .. L e t t h e mean X . = (x, . ,x . , , . , x , .) where b J m,:i_ m,i 1,X 2 , i ' d,r x, . i s t h e mean of t h e k ' t h component of t h e t r a i n i n g f e a t u r e v e c t o r s f o r c a t e g o r y k, :i. C.. A d e c i s i o n i s t h e n made by m i n i m i z i n g d - 2 I ( x , - x .) (10) k = l ^ w h i c h can be put i n t h e l i n e a r d i s c r i m i n a n t f u n c t i o n form o f (8) where W i , d + 1 = - | X t H x k = l | c . ) ] 2 k = l and W i , k = P ( \ = 1 l C i > (11) x-jhen t h e measurements a r e b i n a r y v a l u e d . E q u a t i o n ( 1 1 ) , however, w i l l n o t be d e r i v e d i n t h i s t h e s i s . 2.4.5 A N o n - E u c l i d e a n D i s t a n c e C l a s s i f i e r A m e t r i c d i f f i c u l t t o f i n d i n c l a s s i f i c a t i o n t h e o r y b u t used i n s e q u e n t i a l d e c o d i n g f o r t e l e p h o n e s i g n a l s i s t h e d e c o d i n g d i s t a n c e d e s c r i b e d i n [39]. T h i s d i s t a n c e i s d e f i n e d as d _ E |x - x |. (12) k = l ' A l t h o u g h , i n g e n e r a l , (12) implements a n o n l i n e a r d e c i s i o n b o u n d a r y , i t w i l l be shown i n t h e n e x t s u b s e c t i o n t h a t , f o r b i n a r y measurements, i t i s e q u i -v a l e n t t o a l i n e a r d i s c r i m i n a n t f u n c t i o n c l o s e l y r e l a t e d t o (7) 19 2.4.6 Some I m p o r t a n t I n t e r r e l a t i o n s h i p s F o r t h e t h r e e c l a s s i f i e r s (7), (10) and (12) t h e p r o t o t y p e o r mean p o i n t f o r each c a t e g o r y l i e s somewhere i n s i d e a h y p e r c u b e . . F o r any two c a t e g o r i e s C^,C t h e r e a r e two mean p o i n t s w h i c h can have c e r t a i n s y m m e t r i e s w i t h r e s p e c t t o t h e s i d e s and v e r t i c e s o f t h e hypercube depending on t h e d i s t r i b u -t i o n s o f t h e b i n a r y f e a t u r e v e c t o r s . C e r t a i n i n t e r e s t i n g r e l a t i o n s h i p s a r i s e between ( 7 ) , (10) and (12) under c e r t a i n t y p e s o f symmetry. I n a d d i t i o n , t h e f o l l o w i n g i n t e r e s t i n g theorem t o c l a s s i f i c a t i o n t h e o r y i s p r o v e d . Theorem The minimum d e c o d i n g d i s t a n c e c l a s s i f i e r , (12), w h i c h , i n g e n e r a l , implements a n o n l i n e a r d e c i s i o n boundary i s e q u i v a l e n t t o a l i n e a r d i s c r i m i n a n t f u n c t i o n when t h e measurements a r e b i n a r y and t h e c a t e g o r i e s have e q u a l a p r i o r i p r o b a b i l i t i e s . P r o o f F o r b i n a r y measurements x, . = P(x =1|C.). (13) K j 1 K. X The minimum d e c o d i n g d i s t a n c e c l a s s i f i e r f o r e q u i p r o b a b l e c a t e g o r i e s can be w r i t t e n as ^ M - { E | x k - P ( x k = l | C i ) | } . X K.— X When x =1, |x - P ( x = l | c . ) | = P ( x = 0 | c ) . K. rC tC X K. X When x =0, |x - P ( x =l|c.)| = P ( x = l | c ) . K. K. K. X rC X . . (14) can be w r i t t e n as Mi n { E P(x =0|C.) + E P(x =1|C.)} (15) i i k ' l . , k I k e a keb where a i s the s.et of k's f o r w h i c h x =1 k and b i s t h e s e t o f k's f o r w h i c h x =0. K. 20 Since E P(x =0 C ) i s i n v e r s e l y monotonic i n i to E - P(x =0 C.) and to , k I ' k l Y. [1-P(x =0 | c . ) ] and since E [1-P(x =0 | c . l = E P(x = l | C ) . (15) can be Ic k 1 1, k 1 k k w r i t t e n as Max . { E P(x =1 |C.) + E P(x =0 |C.) } 1 , it 1 , .. K 1 k ea k eb which i s equal to the d i s c r i m i n a n t f u n c t i o n d k 1 I g (X) = E P ( x J C , ) . k=l (16) can be w r i t t e n as (16) g ±(X) = E [x k P ( x k = l | C . ) + ( l - x k ) P ( x k = 0 | C i ) ] k=l (17) Recombining terms y i e l d s d g.(X) - E [P(x =1|C.) - P(x =0|C.)]x, + E P(x=0|C.) 1 , - i K l K . 1 K , . , K X k=l k=l (18) v?hich i s a l i n e a r d i s c r i m i n a n t f u n c t i o n . Q.E.D. This a l g o r i t h m w i l l be c a l l e d 'TL'. Note i t s s i m i l a r i t y to (7). I t can be generated by ta k i n g the a n t i -l o g a r i t h m of every term i n the summation of (7). The r e l a t i o n s h i p between (7 ) , (10), (12) and TL can e a s i l y be observed when the symmetries are viewed i n two-dimensional space. Let the f o l l o w i n g symmecries be defined f o r any i and j , i ^ j : 'A' symmetry 'B' symmetry 'C symmetry 'D' symmetry P ( x 1 = l = P(x 1=0 P ( x 2 = l C ) l = P ( x 2 = l P ( x 2 = l c ) 1 = P(x 2=0 P ( x x = l c.) 1 = P ( x 1 = l P ( x x = l c.) X = P(x 2=0 P ( x 2 = l C ) 1 = -p(X;L=o P ( x x = l c.) 1 = P(x x=0 P(x 2=0 c.) 1 = P ( x 2 = l C ) J c.) J c.) J c.) J c.) J c.) J c.) J 21 It can be shown that (10) and TL implement the same decision l i n e when either A, B, C or D symmetries are observed, ( 7 ) , (10) and TL implement the same decision l i n e when either A, B or C symmetries are observed, and ( 7 ) , (10), (12) and TL a l l implement the same decision l i n e when A or B symmetries are observed. I f none of the. above symmetries are observed a l l four decision boundaries are d i f f e r e n t but some may s t i l l e f f e c t the same decision for biliary feature vectors. For example, (12) and TL always implement the same decision for binary feature vectors, and ( 7 ) , (10), (12) and TL do so under C symmetry. These ideas can be extended to treat hyperspace. Since i n r e a l i s t i c problems these symmetries are l i k e l y to occur infrequently i t i s reasonable, to expect d i f f e r e n t r e s u l t s for the three d i f f e r e n t algorithms. F i g . 4 shows an example of the dec i s i o n boundaries, implemented by ( 7 ) , (10), (12) and TL, for the two-dimensional case when the above symmetries are not observed. 2.4.7 Handling Feature Vectors i n Multispace In order to implement ( 7 ) , (10) or (12)., c e r t a i n modifications have to be made i n order to handle vectors i n multispace, a problem which seldom ar i s e s i n character recognition. In t h i s thesis three approaches to the problem are taken. Let x, . . P(x, |C.,L.) and. L. stand for the mean of the k , i , j , k 1 I j 3 k'th component of the i ' t h category y i e l d i n g feature vectors of the j ' t h length, the p r o b a b i l i t y of the k'th component conditioned on category i of length j , and the j ' t h length, r e s p e c t i v e l y . In addition l e t M be the maximum value of L. . 3 In the f i r s t approach feature vectors of length L^ < M were made to have lengths equal to M by s e t t i n g x^ = 0 for L < k <_ M. Index i was then chosen to maximize W. and minimize Y., where i i .M W. = E lnP(x, |C.) + lnP(C.) (19) 1 k=l • k 1 22 x2 A Eq. Alg. Eq. Eq. (12) TL (10) (7) F i g . 4 Some d e c i s i o n b o u n d a r i e s between two p a t t e r n - c l a s s - m e a n s i n two dimen-s i o n a l s p a c e . M _ Y. = E I x - x , . I - lnP(C.) l , _ 1 k k,x 1 l k=l (20) A l g o r i t h m s W and Y above a r e t h e same as (7) and ( 1 2 ) , r e s p e c t i v e l y , w i t h a p r i o r i p r o b a b i l i t y b i a s terms added. I n W t h e b i a s term f o l l o w s f r o m a d e c i s i o n t h e o r e t i c development, i n Y t h e b i a s term i s a r b i t r a r y b u t r e a s o n a b l e . I n t h e second a p p r o a c h , g i v e n an unknown c h a r a c t e r y i e l d i n g a f e a t u r e v e c t o r o f a p a r t i c u l a r l e n g t h L , o n l y t h e d i s c r i m i n a n t s f o r t h e c a t e g o r i e s G\ c o n t a i n i n g a p r o t o t y p e o f the same L were c a l c u l a t e d . Index i was t h e n chosen t o m i n i m i z e U. and V., where L. 1 1 U . = ^ | x k - x k j i j . | - l n P ( C . ) (21) L 1 - 2 V = E (x -x ) - l n P ( C ) (22) 1 j k k , l , _ ) 1 A l g o r i t h m s U and V above come from (12) and (10) r e s p e c t i v e l y w i t h b i a s terms added. A g a i n , a l t h o u g h the b i a s terms a r e a r b i t r a r y , t h e y a r e r e a s o n a b l e and easy t o implement because the P(C ) a r e known a p r i o r i . The t h i r d a p p r o a c h c o n s i s t s o f m a x i m i z i n g P ( X C . L . ) , t h e j o i n t p r o b a b i l i t y t h a t a f e a t u r e v e c t o r X has L components and comes from a c h a r a c t e r b e l o n g i n g t o c a t e g o r y C^ ,, under s t a t i s t i c a l i n d e pendence among components. As i n (21) and (22) o n l y t h e d i s c r i m i n a n t s f o r t h e c a t e g o r i e s c o n t a i n i n g a p r o -t o t y p e o f t h e same L. were c a l c u l a t e d . Index i was t h e n chosen t o maximize 3 T., where X Li . 3 T. = E l n P ( x . |C.,L.) + l n P ( L . | C . ) + l n P ( C . ) (23) 1 k = l 3 2 1 -y E q u a t i o n (23) f o l l o w s d i r e c t l y f rom P ( X C J L ) under s t a t i s t i c a l i n dependence among components. 2.4.8 A P a r a l l e l - S e q u e n t i a l C l a s s i f i e r I n t h e p a r a l l e l - s e q u e n t i a l mode o f c l a s s i f i c a t i o n some o f t h e d e c i s i o n s f o r m e r l y t a k e n as f i n a l i n a l g o r i t h m s T and U, were t a k e n as t e n t a t i v e and t h e s c a n s o f F i g . 7 ( a ) , f o r a l g o r i t h m U, were t a k e n s e q u e n t i a l l y a c c o r d i n g t o the d e c i s i o n t r e e s o f F i g . 7 ( b ) . The scans and d e c i s i o n t r e e s o f F i g . 7 a r e e x p l a i n e d i n s e c t i o n 4.2. 2.4.9 Compound D e c i s i o n s on S t r i n g s o f Dependent C h a r a c t e r s I n t h e a l g o r i t h m s d i s c u s s e d so f a r a d e c i s i o n was made on i n d i v i d u a l c h a r a c t e r s s o l e l y on the b a s i s o f the measurements and the a p r i o r i p r o b a b i l i t y o f t h o s e c h a r a c t e r s . T h i s mode o f d e c i s i o n i g n o r e s t h e d e p e n d e n c i e s t h a t c h a r a c t e r s may have i n a g i v e n sequence. I t i s d e s i r a b l e t o make use o f t h e s e d e p e n d e n c i e s by making d e c i s i o n s on a s t r i n g o f c h a r a c t e r s r a t h e r than on c h a r a c t e r s i n d i v i d u a l l y . I n t h i s s u b s e c t i o n t h e e q u a t i o n f o r t h e optimum d e c i s i o n on a s t r i n g o f c h a r a c t e r s , g i v e n v a r i a b l e - l e n g t h f e a t u r e v e c t o r s , i s d e r i v e d u s i n g c e r t a i n u n d e r l y i n g a s s u m p t i o n s , and a p r o c e d u r e f o r r e d u c i n g t h e amount o f c o m p u t a t i o n i s g i v e n . We w i s h t o maximize t h e a p o s t e r i o r i p r o b a b i l i t y o f a sequence o f m c h a r a c t e r s g i v e n by P(c|, . . . ,C^,L^, . . . ,LJ | X . . . . , X ) (24) 1 m l m 1 1 m where i s t h e c a t e g o r y o f the n ' t h c h a r a c t e r i n t h e sequence and can t a k e on i v a l u e s , i s t h e l e n g t h o f t h e f e a t u r e v e c t o r o f t h e n ' t h c h a r a c t e r and can t a k e on i v a l u e s , and X i s the f e a t u r e v e c t o r o f t h e n ' t h c h a r a c t e r . S i n c e . n we do n o t c a r e what l e n g t h s a r e a s s o c i a t e d w i t h t h e d e c i s i o n s C 1 , t h e n n optimum d e c i s i o n i s a r r i v e d a t by s e l e c t i n g t h e c a t e g o r i e s C^, C^, C1 1 2 m w h i c h m a x i m i z e ( 2 4 ) . U s i n g Bayes' r u l e (24) becomes P(X 1,...,X m|c 1 >.•.,C m,L 1,• . , L M ) P ( C 1 , . . . , C m , L 1 , . . • , L M ) (25) E x p a n d i n g t h e numerator o f (25) and d e l e t i n g t he de n o m i n a t o r because i t does no t depend on i y i e l d s P(21,./.,Xm|c^,...,^ . (26) Assuming t h a t , 1) X ^ i s i n d e p e n d e n t o f X ^ , and f o r n=l,...,m; h=l,...,m; £=l,...,m; n^h^£ , 2) L i s i n d e p e n d e n t o f L , and C , n h h f o r n = l , . . . , n ; h=l,...,m; n^h, (26) can be w r i t t e n as f o l l o w s : m _ . . m n P ( X | C \ L J ) n P ( L J | C 1 ) P ( C ^ , . . . , C 1 ) . ( 2 7 ) — n ' n n ., n ' n 1 m n= l n = l Taking n a t u r a l logarithms y i e l d s m m . E lnP(X \CX,L3) + E lnP(I. J IC1) + InP(c'\ . . . , 0 ^ . (28) , n 1 n n , n ' n 1 m n=l n=l I f i t i s now assumed that the components of X_ = (x ,x , ...,x .) are independent, I jn then the optimum d e c i s i o n on the sequence of m characters i s made by maximizing G(X l 5...,X ) over R™ p o s s i b l e sequences, where 1 m . m L-1 . . . G(X.,...,$ ) = E [ E n lnP(x. IC 1,^) + ]*P (Ir 1 I C1) ] I m - , _ k ' n n n ' n n=l k=l + lnPCC^",...^ 1). (29) 1 m One can v a s t l y reduce the computation time by assuming that i n an ordered l i s t of bracketed, [ ] , terms i n (29) over C 1,L 3 , the c o r r e c t i d e n t i t y of an unknown n n character has a high p r o b a b i l i t y of being i n the top ds e n t r i e s of the ordered l i s t , where ds i s c a l l e d the 'depth of search' and G. i s maximized over ( d s ) m sequences. For bigrams m-2 and f o r trigrams m=3. 2.5 T r a i n i n g and Storage Requirements P r o b a b i l i t i e s P(X|C.), P(x (c.) and P(x |C.,L.) were estimated or 1 rC X K. X J learned by determining the r e l a t i v e number of times a vec t o r X or component x, occurred, given the event C. or the -joint event C.,L.. Since we do not k x J i j know the p r o b a b i l i t y d i s t r i b u t i o n s of the p r o b a b i l i t y values themselves we .cannot make optimum estimates of those values and we are j u s t i f i e d i n using the maximum l i k e l i h o o d estimates described above. Algorithm S must l e a r n and s t o r e P(X|C.)P(C.) f o r v i r t u a l l y a l l X which occur i n a t e s t s e t . Algorithm T needs only P(x. | c.,L.), P(L.|C.) k i J J i and P(C_^). In a d d i t i o n to P(C_^), f o r b i n a r y measurements, U and V need P(x. |C.,L.) w h i l e W and Y need P(x, | c . ) . Algorithm G needs P(x, |C.,L.), k ' l j k ' l k ' l j P ( L . | c . ) and P(C^,...,C 1). Note t h a t , under the assumptions made, G learns the _J X X TTI same about the measurements as does T but needs t o s t o r e R i n s t e a d o f R a p r i o r i p r o b a b i l i t i e s and needs t o s e a r c h o v e r t h e same number o f d i s c r i m i n a n t s . I I I . EXPERIMENTS 3.1 I n t r o d u c t i o n A l t h o u g h the whole system of F i g . 1 can be s i m u l a t e d i n one program, too much c o m p u t a t i o n would be d u p l i c a t e d i n p e r f o r m i n g the many e x p e r i m e n t s . A c c o r d i n g l y , each s e c t i o n o f t h e r e c o g n i t i o n problem was s i m u l a t e d s e p a r a t e l y . The c o n t o u r t r a c e r was s i m u l a t e d u s i n g an IBM-7044 computer i n t o w h i c h punched c a r d s c o n t a i n i n g a l l t h e d a t a had been r e a d , and out of w h i c h punched c a r d s c o n t a i n i n g t h e f e a t u r e v e c t o r s were o b t a i n e d . Hence t h i s o p e r a t i o n was p e r f o r m e d once f o r 4-PAD and once f o r 6-PAD o n l y . A l l t h e c l a s s i f i e r s were s i m u l a t e d on an IBM-360/67 computer where the f e a t u r e v e c t o r s were s t o r e d . i n a f i l e . S i n c e t h e t r a i n i n g f o r a l g o r i t h m G i s t h e same as t h a t f o r T, a l l t h e l i k e l i h o o d s f o r each f e a t u r e v e c t o r i n t h e T e x p e r i m e n t s were s t o r e d on tape t o g e t h e r w i t h b i g r a m and t r i g r a m s t a t i s t i c s . Hence the b i g r a m and t r i g r a m programs o p e r a t e d o n l y on t h e l i k e l i h o o d s of the f e a t u r e v e c t o r s , t h u s s a v i n g a g r e a t d e a l o f c l a s s i f i c a t i o n c o m p u t a t i o n and r e d u c i n g t h e b i g r a m and t r i g r a m programs t o c o m b i n a t i o n a l o p e r a t i o n s f o r t h e most p a r t . The p u r p o s e o f t h e e x p e r i m e n t s i n t h i s t h e s i s i s f i v e - f o l d ; 1) t o compare th e s i x - p a r t a r e a d i v i s i o n (6-PAD) f e a t u r e e x t r a c t i o n scheme w i t h 4-PAD, 2) t o compare th e v a r i o u s c l a s s i f i c a t i o n a l g o r i t h m s i n terms o f p e r -formance and s t o r a g e r e q u i r e m e n t s , 3) t o o b s e r v e t h e e f f e c t s o f monogram, b i g r a m and t r i g r a m c o n t e x t u a l c o n s t r a i n t s i n terms o f p e r f o r m a n c e , c l a s s i f i e r c o m p l e x i t y , and added s t o r a g e r e q u i r e m e n t s , 4) t o o b t a i n r e a s o n a b l e p r e d i c t i o n s o f t h e p r o b a b i l i t y o f e r r o r on r e a l w o r l d d a t a , and 5) to compare p e r f o r m a n c e on an i n d i v i d u a l w i t h t h a t on the- p o p u l a t i o n . I n e a r l y e x p e r i m e n t s r e s e a r c h e r s i n the f i e l d p r e d i c t e d t h e p e r -formance o f a r e c o g n i t i o n scheme by o b t a i n i n g a sample o f d a t a , t r a i n i n g the * 4-PAD and 6-PAD r e f e r to f o u r and s i x - p a r t a r e a d i v i s i o n , r e s n e c t i v e l y . a l g o r i t h m on t h a t sample and t e s t i n g i t on the same sample. T h i s method i s known as t h e R method ( r e s u b s t i t u t i o n ) [42] . I t i s now w e l l known [40] t h a t t h i s p r o c e d u r e y i e l d s a b i a s e d o v e r -o p t i m i s t i c p r e d i c t i o n o f p e r f o r m a n c e . Highleyman [41] showed t h a t f o r v e r y l a r g e f i x e d samples o f d a t a t h e r e e x i s t s an optimum p a r t i t i o n i n g o f t h e s e t i n t o a t r a i n i n g s e t and a t e s t i n g s e t i n o r d e r t o b e s t p r e d i c t t h e p e r f o r m a n c e , w i t h t h e r e s u l t t h a t t h e t e s t i n g s e t s h o u l d n e v e r be s m a l l e r t h a n t h e t r a i n i n g s e t . F o r s m a l l d a t a s e t s , however, Highleyman's method b r e a k s down and y i e l d s an o v e r p e s s i m i s t i c e s t i m a t e of p e r f o r m a n c e [401. T h i s p r o c e d u r e i s r e f e r r e d t o as the H method ( h o l d o u t ) . I n 1968 L a c h e n b r u c h and M i c k e y [42, 43] showed t h a t f o r s m a l l sample s i z e s a much b e t t e r e s t i m a t e o f p e r f o r m a n c e c o n s i s t s of t r a i n i n g the c l a s s i f i e r on a l l b u t one p a t t e r n i n t h e s e t and t h e n t e s t i n g on t h e p a t t e r n l e f t out d u r i n g t r a i n i n g , r e p e a t i n g t h i s p r o -c e d u r e u n t i l e v e r y p a t t e r n o f t h e d a t a has been used as a t e s t p a t t e r n . N e e d l e s s t o s a y , u n l e s s t h e d a t a s i z e i s v e r y s m a l l , a g r e a t d e a l o f t r a i n i n g c o m p u t a t i o n i s needed i n t h i s method r e f e r r e d t o as t h e U method. I n t h i s t h e s i s a v a r i a t i o n o f t h e U method i s used t o p r e d i c t p e r -formance. The method and i t s advantages a r e d e s c r i b e d i n s e c t i o n 3.3. 3.2 D e s c r i p t i o n o f the Data A t o t a l o f twenty upper c a s e a l p h a b e t s were o b t a i n e d from seven d i f f e r e n t p e r s o n s , a l l o f whom were r e q u i r e d t o p r i n t on good q u a l i t y g r a p h paper i n s q u a r e s 0.40 i n . h i g h by 0.50 i n . w i d e . A Paper Mate t h i n - f e l t - t i p pen was u s e d . Each p e r s o n was asked t o l e a v e t h e o u t s i d e c o n t o u r o f each c h a r a c t e r unbroken. A l l seven p e r s o n s p r i n t e d the a l p h a b e t once from A-Z, as shown i n F i g . 5, and once from Z-A. Two p e r s o n s p r i n t e d t h r e e a d d i t i o n a l a l p h a b e t s by c o p y i n g three, r a n d omized l o w e r c a s e a l p h a b e t s . An e n l a r g e r -p r o j e c t o r o f m a g n i f i c a t i o n ten was used to p r o j e c t each c h a r a c t e r onto an 29 1. --]-I i I . 1 . i 1^ i I i 1 I. i l • I i ! ! , I ; • i ! I i i i ; I i • ; I J I i • i I ; I ! j ; » I ; j • i • M I • ; I J > ! ' '• H-I -1-— .1 • JJ—U i . L T | ; ! I , ! I in T_7 r - l -•i.J-.l.._.U',-', . 1.1 I. i _ ! I. I.! I l i I,! i i i | ! ! !...-.. I . L i __! i _ r n - r - r r n — T r ? - " T r n - n - r r — n ~ -|~; j L_J_ -4 4 -r T I. I -n-r-A' 1 ! • • 1 1 1 r i ' : • i •. J . u ^ p T - : r , r . . l . - j ( . - ; j y- 'j- ' ' , - . ~ ' | — j ~ r ' i i •. : l ! . •. ! . I 1 ; ' 1 1 1 ' • 1 i • ! 1 ; I : . • - i fete , 1 J 1 • 1 i 1 ; 1 1 1 1 ! . r - _ : !..... ..!... J /< , : i > t . i • i • : • • M A/ i ! ! i I i , i.: \s I i ! ! : I I I.. '.J F i g . 5 Alphabets from seven persons. The s i x t h and seventh alphabets are from PERSONS 1 and 2, r e s p e c t i v e l y . 30 a r e a d i v i d e d i n t o 2500 0.1 i n . s q u a r e s . I f more than 50% of any s q u a r e ' s a r e a was b l a c k the sq u a r e was b l a c k e n e d and a s s i g n e d a v a l u e 1. O t h e r w i s e the sq u a r e was l e f t w h i t e and a s s i g n e d a v a l u e 0. Each s p a t i a l l y q u a n t i z e d c h a r a c -t e r was the n encoded onto IBM punch c a r d s by e x p e r i e n c e d keypunch o p e r a t o r s . The l e g i b i l i t y o f t h e d a t a was e s t i m a t e d by a s k i n g 10 g r a d u a t e s t u d e n t s t o i d e n t i f y a l l 520 m a g n i f i e d . s p a t i a l l y q u a n t i z e d c h a r a c t e r s . Each s t u d e n t r e s p o n d e d v e r b a l l y t o c h a r a c t e r s v i e w e d o n e - a t - a - t i m e i n random o r d e r a t c l o s e range f o r as l o n g as d e s i r e d . A l l v i e w i n g was done a t one s e s s i o n w h i c h l a s t e d a p p r o x i m a t e l y 12 m i n u t e s p e r s t u d e n t . The r e c o g n i t i o n a c c u r a c y a v e r a g e d o v e r t h e f i r s t two a l p h a b e t s o f a l l seven p e r s o n s and o v e r a l l 10 v i e w e r s was 99.7%. A v e r a g i n g o v e r a l l 1 0 ' v i e w e r s and o v e r t h e f i v e a l p h a b e t s from PERSONS 1 and 2 y i e l d e d 99.8% and 100%, r e s p e c t i v e l y . Machine r e c o g n i t i o n e r r o r s i n e x c e s s o f a few p e r c e n t would t h e r e f o r e r e s u l t from weaknesses i n e i t h e r f e a t u r e e x t r a c t i o n o r c l a s s i f i c a t i o n , o r b o t h . 3.3 E x p e r i m e n t s on Independent C h a r a c t e r s The e x p e r i m e n t s on t h e t e s t d a t a o v e r t h e p o p u l a t i o n (POP) were p e r f o r m e d u s i n g t h e f i r s t two a l p h a b e t s f r o m f i v e p e r s o n s f o r t r a i n i n g , and two a l p h a b e t s ' f r o m each o f t h e two r e m a i n i n g p e r s o n s f o r t e s t i n g . The r e s u l t s were a v e r a g e d o v e r ' s e v e n t r i a l s . I n t h e i ' t h t r i a l , d a t a from PERSONS i and i + l , i = l , 2 , . . . , 6 , were used f o r t e s t i n g . I n t h e s e v e n t h t r i a l d a t a from PERSONS 7 and 1 were used f o r t e s t i n g . F o r t e s t s on d a t a from one i n d i v i d u a l , f o u r a l p h a b e t s were used f o r t r a i n i n g and t h e r e m a i n i n g one f o r t e s t i n g . The r e s u l t s were a v e r a g e d o v e r f i v e t r i a l s i n w h i c h a d i f f e r e n t a l p h a b e t s e r v e d as the t e s t d a t a f o r each t r i a l . T h i s p r o c e d u r e f o r e s t i m a t i n g t h e p e r f o r m a n c e i s a compromise between the H method and the U method [ 4 0 ] . A l t h o u g h t h e U method would be a b e t t e r e s t i m a t e and would p r o b a b l y p r e d i c t a b e t t e r p e r f o r m a n c e , too much t r a i n i n g c o m p u t a t i o n would be r e q u i r e d w i t h the d a t a s e t above. 31 The method used h e r e , i n a d d i t i o n t o b e i n g more e c o n o m i c a l on d a t a t h a n t h e H method, i n v o l v e s f a r l e s s t r a i n i n g c o m p u t a t i o n than the U method. I t i s , t h u s , a r e a s o n a b l e method t o use and i f a n y t h i n g p r o b a b l y y i e l d s a s l i g h t l y n e g a t i v e l y b i a s e d e s t i m a t e o f p e r f o r m a n c e . F o r e x p e r i m e n t s on the t r a i n i n g d a t a i n t h e POP t e s t s t h e f i r s t two a l p h a b e t s from each p e r s o n were used. I n t e s t s , on a l p h a b e t s from PERSONS 1 and 2 a l l f i v e a l p h a b e t s were used. The e x p e r i m e n t a l p r o c e d u r e s d e s c r i b e d above y i e l d e d maximum l i k e l i -hood e s t i m a t e s o f B(e|c ), i = . l , 2 , . . . , 26, i . e . , t h e p r o b a b i l i t y o f e r r o r c o n d i -t i o n e d on p a t t e r n c l a s s , f o r a l g o r i t h m s S, T, U, V, W and Y. To c a l c u l a t e t h e t o t a l p r o b a b i l i t y o f e r r o r , P ( e ) , f o r each a l g o r i t h m , t h e e s t i m a t e s o f P ( e | c . ) w e r e s u b s t i t u t e d i n t o 1 26 P(e) = Z P(e | c.)P(C.) (30) i = l 1 1 F o r t h e e x p e r i m e n t s on e q u i p r o b a b l e c h a r a c t e r s (EQP), P(G\) was made e q u a l t o 1/26 f o r a l l i i n (30) and i n t h e c l a s s i f i c a t i o n a l g o r i t h m s . F o r t h e e x p e r i m e n t s on E n g l i s h a p r i o r i p r o b a b i l i t y c h a r a c t e r s (ENG), 5 - d e c i m a l d i g i t e s t i m a t e s o f t h e v a l u e s o f P(C^) were o b t a i n e d from P i e r c e [ 4 4 ] . 3.4 E x p e r i m e n t s on Dependent C h a r a c t e r s A l g o r i t h m G, eq. ( 2 9 ) , was used w i t h b i g r a m (m=2) and t r i g r a m (m=3) c o n t e x t u a l c o n s t r a i n t s . Maximum l i k e l i h o o d e s t i m a t e s f o r t h e b i g r a m and t r i g r a m a p r i o r i p r o b a b i l i t i e s were o b t a i n e d by d i v i d i n g t h e i r f r e q u e n c y o f o c c u r r e n c e , g i v e n i n P r a t t [ 4 5 ] , by t h e i r t o t a l number o b s e r v e d . There were 304 and 2,510 b i g r a m and t r i g r a m e n t r i e s , r e s p e c t i v e l y . A l l o t h e r p o s s i b l e c o m b i n a t i o n s o f two and t h r e e c h a r a c t e r s were c o n s i d e r e d i l l e g a l . A c c o r d i n g l y , when t h e d e p t h o f s e a r c h (ds) was so s m a l l t h a t a l l t h e p r o s p e c t i v e s t r i n g s o f m c h a r a c t e r s were i l l e g a l , a d e c i s i o n was made on i n d i v i d u a l c h a r a c t e r s w i t h o u t u s i n g c o n t e x t . However, t h e l i k e l i h o o d o f o b s e r v i n g l e g a l b i g r a m s and t r i g r a m s i n t he s e a r c h made by G r a p i d l y i n c r e a s e s , v a r y i n g w i t h t h e s q u a r e and cube 32 o f d s , r e s p e c t i v e l y . The e x p e r i m e n t s on t h e t e s t d a t a were performed u s i n g the f i r s t two a l p h a b e t s from f i v e p e r s o n s f o r t r a i n i n g and f o r m i n g samples o f bi g r a m s and t r i g r a m s out o f t h e two a l p h a b e t s from each o f the two r e m a i n i n g p e r s o n s f o r t e s t i n g . T h e r e s u l t s were a v e r a g e d o v e r seven t r i a l s as d e s c r i b e d i n s e c t i o n 3.3. In each t r i a l 2 ( 2 ) m samples o f bi g r a m s o r t r i g r a m s were formed f o r each e n t r y , where 2™ samples a r e formed from t h e two c h a r a c t e r - s a m p l e s o f each t e s t i n g p e r s o n . F o r e x p e r i m e n t s on t h e t r a i n i n g d a t a the f i r s t two a l p h a b e t s from each o f t h e seven p e r s o n s were used f o r t r a i n i n g and 7(2)™ b i g r a m o r t r i g r a m samples p e r b i g r a m o r t r i g r a m e n t r y were formed, as d e s c r i b e d above, f o r t e s t i n g . The e x p e r i m e n t a l p r o c e d u r e s d e s c r i b e d above y i e l d e d e s t i m a t e s o f • P (e | C i ^ , Cl^ , . • . , C i ) f o r i ^ = l >••-•> 26; i 2 = l >•••> 26; . . . : i =1, . . . , 26 , where any c o m b i n a t i o n of i ^ , i 2 , . . . i was a l e g a l s t r i n g o f m c h a r a c t e r s . The t o t a l p r o b a b i l i t y o f e r r o r was t h e n c a l c u l a t e d u s i n g 26 26 26 P ( e ) = E E ... E P ( e | C i 1 , C i _ , . . . , C i ) P ( C i 1 , C i - , . . . , c i ) (31) i = l i = l l =1 1 2 m o v e r a l l t h e l e g a l s t r i n g s o f m c h a r a c t e r s . The p r o b a b i l i t y o f e r r o r was c a l c u l a t e d f o r v a r i o u s v a l u e s o f the de p t h o f s e a r c h , f o r b i g r a m s up t o ds=16 and f o r t r i g r a m s up t o ds=5, u s i n g POP t r a i n i n g d a t a w i t h 4-PAD f e a t u r e e x t r a c t i o n . H a v i n g found an e x p e r i m e n t a l optimum v a l u e o f d s , P ( e ) was c a l c u l a t e d f o r t h e 4-PAD TS c a s e and f o r the 6-PAD TR and TS c a s e s . 33 IV. RESULTS 4.1 I n t r o d u c t i o n A l t h o u g h t h e r e s u l t s of main i n t e r e s t a r e t h o s e coming from the t e s t s e t , r e s u l t s on the t r a i n i n g s e t a r e i n c l u d e d f o r t h r e e r e a s o n s . (1) The s m a l l e r t h e d i f f e r e n c e between the p e r f o r m a n c e of a c l a s s i f i e r on the t r a i n i n g s e t and on t h e t e s t i n g s e t i s , t h e s m a l l e r t h e amount of d a t a needed a l t o g e t h e r becomes. I n o t h e r words, i f b o t h methods y i e l d comparable r e s u l t s one can be r e a s o n a b l y c o n f i d e n t t h a t enough d a t a has been c o l l e c t e d . T h i s may be h e l p f u l t o know when d a t a i s d i f f i c u l t t o c o l l e c t . (2) G i v e n a s m a l l d a t a s e t , i f two c l a s -s i f i e r s p e r f o r m e q u a l l y w e l l on t h e t e s t i n g s e t i t may do w e l l t o d e c i d e on t h e c l a s s i f i e r y i e l d i n g b e t t e r p e r f o r m a n c e on t h e t r a i n i n g s e t . S i n c e i f a l a r g e d a t a s e t becomes a v a i l a b l e - one w o u l d e x p e c t t h e t e s t s e t r e s u l t s t o l i e between th e p r e v i o u s t e s t s e t and t r a i n i n g s e t r e s u l t s , t h e c l a s s i f i e r p r e v i o u s l y y i e l d i n g b e t t e r p e r f o r m a n c e on t h e t r a i n i n g s e t may s u b s e q u e n t l y y i e l d b e t t e r p e r f o r m a n c e on the t e s t i n g s e t . (3) I f the s m a l l d a t a s e t a v a i l a b l e i s an u n b i a s e d e s t i m a t e o f t h e f u t u r e c h a r a c t e r s t o come then t h e p e r f o r m a n c e on the t r a i n i n g d a t a o f t h e s m a l l s e t i s a r e a s o n a b l e e s t i m a t e f o r t h e p e r f o r m a n c e on t h e f u t u r e c h a r a c t e r s . F o r o t h e r comments see a l s o [ 4 6 j . 4.2 Independent C h a r a c t e r s R e s u l t s o b t a i n e d u s i n g a l g o r i t h m s S, T, U, V, W and Y o f s u b s e c t i o n 2.4.7 appear i n F i g . 6. EQP means e q u i p r o b a b l e c h a r a c t e r s ; ENG means t h a t t h e P(C_^) assumed t h e p r o b a b i l i t i e s i n E n g l i s h t e x t . TS and TR d enote t e s t s e t and t r a i n i n g s e t , r e s p e c t i v e l y , w h i l e 6 and 4 a p p l y to the a r e a d i v i s i o n . The f i r s t , s e c o n d , and t h i r d s q u a r e s a p p l y , r e s p e c t i v e l y , t o d a t a from t h e p o p u l a t i o n , PERSON 1 and PERSON 2. The numbers w h i c h a r e n e i t h e r i n b r a c k e t s nor p a r e n t h e s i s i n d i c a t e m i s c l a s s i f i c a t i o n ( e r r o r p l u s r e j e c t ) p r o b a b i l i t i e s when r e j e c t s do o c c u r ; i f no r e j e c t s o c c u r the-numbers i n d i c a t e , e r r o r p r o b a b i l i t i e s . Numbers 3 4 EQP ENG 6 7-7 TR 6-2 4-5 n 4 75 12 12 6 58 52 45 (48) (45) (40) TS 4 54 59 43 (36) (41) (31) TR 6 4-0 1-5 3-0 77 7-1 8-0 6 45 49 36 (41) (46) (33) TS 41 50 33 (26) (36) (21) TR 6 24 DQ] 12 [5] 8-5 [o-o] EQP 32 18 16 _ 6 30 23 20 (08) 43 33 (0-8) 26 TR 6" 14 4-4 7-5 4 21 14 14 ENG 6 19 10 17 (0-4) TS 4 30 25 (1-6) 19 EQP T JL L TS I £ L 4 TR ENG 6 TS I 4 TR EQP ENG TS | £ 6 TR 10 I 7-0 [3-5j\[0-8] 4-5 17 MI 13 • 12 27 21 15 (OB) 33 30 (OB) 17 4-3 P-BJ 2-0 [0-0] 30 [0-0] 12 7-5 8-0 20 12 13 (0-8) 23 19 (0-8) 18 18 9-2 7-6 23 16 15 27 21 19 (0-8) 38 29 (OB) 24 12 53 7-5 17 10 8-9 TS 19 10 (Ml 2 5 I s ) . 19 \ 6_ 4 23 8-5 4-6 31 20 14 4 41 \ 26 19 46 28 19 F i g . 6 M i s c l a s s i f i c a t i o n and r e j e c t p r o b a b i l i t i e s ' i n per cent 35 i n p a r e n t h e s e s denote the r e j e c t p r o b a b i l i t y .and numbers i n b r a c k e t s denote the e r r o r p r o b a b i l i t y when the scans of F i g . 7 were used to r e s o l v e c o n f u s i o n s . F o r a l g o r i t h m s W and Y, r e s u l t s a r e f o r e q u i p r o b a b l e c h a r a c t e r s on the t r a i n i n g s e t . Over POP's 1 4 a l p h a b e t s t h e a v e r a g e v e c t o r l e n g t h was 1 7 and 25 f o r 4-PAD and' 6-PAD, r e s p e c t i v e l y . The p r o c e d u r e used t o o b t a i n f i n i t e e s t i m a t e s o f P(X IC ) and i P ( x |C.,L.) makes r e j e c t i o n o f any c h a r a c t e r u n n e c e s s a r y . F o r example, when k. 1 j P(X|C_^)P(C^) = z e r o f o r a l l i , t h e optimum d e c i s i o n i s t o s e l e c t any one of t h e 26 c h a r a c t e r s as b e i n g c o r r e c t . The number i n p a r e n t h e s i s i n F i g . 4 m e r e l y i n d i c a t e s t h e p r o b a b i l i t y t h a t t h e optimum c h o i c e i s any one of t h e 26 c h a r a c t e r s ; i n many r e c o g n i t i o n schemes, however, t h e unknown c h a r a c t e r s . w o u l d be r e j e c t e d i n s u c h cases.. Thus, r e j e c t s a r e i n d i c a t e d f o r a l g o r i t h m S whenever a f e a t u r e v e c t o r d i f f e r e n t from any e n c o u n t e r e d d u r i n g t r a i n i n g o c c u r s d u r i n g t e s t i n g , and f o r T, U and V whenever the l e n g t h of t h e t e s t v e c t o r i s d i f f e r e n t from any e n c o u n t e r e d d u r i n g t r a i n i n g . No r e j e c t s o c c u r , as e x p e c t e d , when t e s t i n g i s done on t h e t r a i n i n g d a t a . F o r a l l a l g o r i t h m s , when th e d i s -c r i m i n a n t s o f two o r more c a t e g o r i e s were e q u a l , t h e unknown c h a r a c t e r was c l a s s i f i e d on t h e b a s i s o f t h e f i r s t d i s c r i m i n a n t i n a l p h a b e t i c o r d e r . Some sca n s used t o d i f f e r e n t i a t e e a s i l y c o n f u s e d c h a r a c t e r s appear i n F i g . 7 . F i g . 7 - ( a ) shows t h e scans f o r r e s o l v i n g c h a r a c t e r c o n f u s i o n s t h a t were used on t h e t r a i n i n g d a t a w i t h a l g o r i t h m U, 4-PAD, and e q u i p r o b a b l e c h a r a c -t e r s . S i n g l e headed arrows e x t e r n a l t o t h e boxes i n d i c a t e t h a t t h e s c a n b e g i n s a t t h e l e f t m o s t b l a c k p o i n t i n t h e t o p and b o t t o m rows, r e s p e c t i v e l y , o f S2 and S3, and a t t h e l o w e s t b l a c k p o i n t i n t h e l e f t m o s t column o f S8. C h a r a c -t e r w i d t h and h e i g h t i s W and H, r e s p e c t i v e l y . Double headed arrows accompany t h e h e i g h t o r w i d t h f r a c t i o n a t w h i c h the. scans o c c u r . F i g . 7 - ( b ) shows Jt> 3W/5 W/2 SI \H/3 S4 S5 W/4 \H/3 H/4\ S6 W/3 S7 S3 (a) AO [6.0] S1 S2 S3 -D •0 -A •B B [2-8] 0 S4 SS S6 •F S7 -2 •B [19] S8 Q 0 (b) ABD [7.7] S1 D S2 -B (c) S9 R [1-4] S6 S10 •R S2 -J S1 Blorl S9 [0.8] 3 I 1 1 J V S6 [0.8] •V 2 1 H K S10 [0.8] K 2 D •B F i g . 7 Scans and d e c i s i o n t r e e s f o r r e s o l v i n g c h a r a c t e r c o n f u s i o n s 37 t h e d e c i s i o n t r e e s f o r the p o p u l a t i o n . The number on a t r e e b r a n c h i n d i c a t e s the number o f w h i t e - t o - b l a c k (WB) t r a n s i t i o n s r e s u l t i n g from the s c a n shown a t t h e p r e v i o u s node. Thus, i f U i n e a u a t i o n (21) i s minimum f o r b o t h = A and = 0, the n SI i s a p p l i e d : i f t h r e e WB t r a n s i t i o n s o c c u r , f i n a l c l a s s i f i c a t i o n i s B. O t h e r w i s e S2 i s a p p l i e d f o l l o w e d , i f n e c e s s a r y , by S3. The d e c r e a s e i n e r r o r p r o b a b i l i t y f o r any g i v e n t r e e a p p e ars i n s q u a r e b r a c k e t s . F i g 7-(c) shows t h e d e c i s i o n t r e e s used f o r PERSON'2. Use o f t h e s e s c a n s and d e c i s i o n t r e e s on t h e t r a i n i n g d a t a w i t h a l g o r i t h m U r e d u c e d e r r o r p r o b a b i l i t y f o r POP from 24% t o 10%. The ABD d e c i s i o n t r e e r e d u c e d th e e r r o r f o r PERSON 2 from 8.5% t o 0.8%. A p r o c e d u r e s i m i l a r t o t h e one i n F i g . 7 y i e l d e d t h e o t h e r numbers i n s q u a r e b r a c k e t s i n F i g . 6, a l t h o u g h fewer s c a n s , t r e e s , and t r e e b r a n c h e s were needed i n t h e s e o t h e r c a s e s . A p p l y i n g d e c i s i o n t r e e s and sc a n s t o t h e ENG-6-PAD t r a i n i n g d a t a w i t h a l g o r i t h m T y i e l d e d r e c o g n i t i o n r a t e s o f 98.2%, 100% and 100% on t h e d a t a from t h e popula= t i o n , PERSON 1 and PERSON 2, r e s p e c t i v e l y . 4.3 Dependent C h a r a c t e r s R e s u l t s o b t a i n e d u s i n g a l g o r i t h m G •••ith m=2 and m=3 appear i n F i g s . 8 and 9. F i g . 8 shows the p e r c e n t e r r o r as a f u n c t i o n o f ds f o r t h e 4-PAD t e s t i n g d a t a . F o r t h e b i g r a m c a s e t h e p e r c e n t e r r o r was c a l c u l a t e d f o r ds up t o a v a l u e o f 16. Note t h a t t h e r e i s no need t o i n c r e a s e ds any f u r t h e r s i n c e , f o r t h e d a t a i n t h e s e e x p e r i m e n t s , 16 was the l a r g e s t number o f c a t e g o r i e s t h a t c o u l d have p r o t o t y p e f e a t u r e v e c t o r s o f t h e same l e n g t h as t h a t o f the unknown v e c t o r i n q u e s t i o n . I n o t h e r words, g i v e n any t e s t f e a t u r e v e c t o r , t h e l a r g e s t number o f p o s s i b l e c a t e g o r y l i k e l i h o o d s f o r t h a t v e c t o r was 16. F o r the t r i g r a m c a s e c a l c u l a t i o n o f t h e e r r o r r a t e s t o p p e d a t ds=5 be c a u s e the amount of computer time needed f o r ds > 5 would have been too l a r g e . A FORTRAN program w r i t t e n t w i c e f o r t h e sake of e f f i c i e n c y 21 A DEPTH OF SEARCH F i g . 8 P e r c e n t e r r o r p r o b a b i l i t y as a f u n c t i o n o f ds f o r the 4-PAD t e s t i n g d a t a . t o o k a l m o s t 2 ho u r s o f CPU tim e on t h e IBM-360/67 f o r t h e t r i g r a m c a s e w i t h ds=5. B o t h e r r o r r a t e s on F i g . 8 d e c r e a s e a t an a c c e l e r a t i n g r a t e r e a c h i n g a minimum a t ds=4, a f t e r w h i c h t h e y i n c r e a s e a t a d e c e l e r a t i n g r a t e . The b i g r a m P ( e ) r a p i d l y becomes u n i f o r m a t a v a l u e o f 17.9%. S i n c e t h e d a t a d i s t r i b u t i o n s a r e the same f o r t h e b i g r a m and t r i g r a m c a s e s and s i n c e t h e same u n d e r l y i n g a s s u m p t i o n s o f a l g o r i t h m G a r e made f o r b i g r a m s and t r i -grams one would e x p e c t t h a t t h e t r i g r a m e r r o r c u r v e f o r ds > 5. would behave i n a s i m i l a r f a s h i o n t o the b i g r a m e r r o r c u r v e . F i g . 9 shows the per c e n t P ( e ) , f o r t h e 4-PAD and 6-PAD ca s e s on the t r a i n i n g and t e s t i n g d a t a s e t s , as a f u n c t i o n o f the o r d e r o f c o n t e x t u a l i n f o r m a t i o n used. Zero o r d e r r e p r e s e n t s e q u i p r o b a b l e c h a r a c t e r s , f i r s t o r d e r 39 ORDER OF CONTEXTUAL INFORMATION F i g . 9 P e r c e n t e r r o r p r o b a b i l i t y as a f u n c t i o n of t h e o r d e r o f c o n t e x t u a l i n f o r m a t i o n used. r e p r e s e n t s monogram s t a t i s t i c s , e t c . . Note t h a t t h e z e r o and f i r s t o r d e r r e s u l t s come from a l g o r i t h m T w h i c h r e q u i r e s t h e same measurement t r a i n i n g as G but cannot make use o f c h a r a c t e r d e p e n d e n c i e s . The b i g r a m and t r i g r a m v a l u e s of P ( E ) a r e t h o s e f o r ds=4. W i t h t r i g r a m s and 6-PAD a l g o r i t h m G y i e l d s 86% and 98% c o r r e c t r e c o g n i t i o n on t h e t e s t i n g and t r a i n i n g d a t a r e s p e c t i v e l y . A marked improvement i s n o t e d i n a l l f o u r c a s e s i n g o i n g from z e r o t o t h i r d o r d e r c o n t e x t u a l i n f o r m a t i o n . The e r r o r r a t e f o r TS-4-PAD, f o r example, r e d u c e s from 33% t o 16%, i . e . , an e r r o r r e d u c t i o n of more t h a n 5 0 % . V. DISCUSSION AND CONCLUSIONS 5.1 E v a l u a t i o n o f R e s u l t s A l t h o u g h a l g o r i t h m S y i e l d e d t h e lowest P ( e ) on the t r a i n i n g s e t w i t h i n d e p e n d e n t c h a r a c t e r s , the d i f f e r e n c e between S and T i s s m a l l . T h i s s u g g e s t s t h a t t h e a s s u m p t i o n of s t a t i s t i c a l i ndependence among f e a t u r e v e c t o r components i s r e a s o n a b l e . A l g o r i t h m s T, U and V a l l p e r f o r m e d much b e t t e r t h a n S when the t r a i n i n g and t e s t d a t a were d i s j o i n t , w h i c h i n d i c a t e s t h a t i n such c i r c u m s t a n c e s suboptimum c l a s s i f i e r s h a v i n g r e l a t i v e l y few p a r a m e t e r s may be s i g n i f i c a n t l y b e t t e r t h a n optimum c l a s s i f i e r s r e q u i r i n g e x t e n s i v e t r a i n i n g . T h i s c o n c l u s i o n i s s i m i l a r t o t h e one r e a c h e d by Hughes [47] w h i c h was t h a t when a p a t t e r n r e c o g n i t i o n p r o b l e m i s s e l e c t e d a t random from a l l p o s s i b l e p r o b l e m s , t h e optimum number of t h e o r e t i c a l l y p o s s i b l e f e a t u r e v e c t o r s d e c r e a s e s w i t h . t h e amount o f t r a i n i n g d a t a . F o r • e q u i p r o b a b l e c h a r a c t e r s T p e r f o r m s b e t t e r t h a n U and V. T h i s i s r e a s o n a b l e b e c a u s e b o t h U and V do n o t have P ( L . C.) a v a i l a b l e as does T. I n a d d i t i o n i t can be shown j i (theorem i n s u b s e c t i o n 2.4.6), t h a t f o r e q u i p r o b a b l e c h a r a c t e r s and b i n a r y measurements, U can be g e n e r a t e d by o m i t t i n g t h e P ( L |C^,) term from T and t a k i n g t h e a n t i l o g a r i t h m o f t h e r e m a i n i n g terms. I f , i n a d d i t i o n , t h e compo-n e n t s of t h e f e a t u r e v e c t o r s a r e s t a t i s t i c a l l y i n d e p e n d e n t t h e n U must be i n f e r i o r t o T. When t h e P(C ) of E n g l i s h t e x t a r e used t h e d i f f e r e n c e between T, U and V on the t e s t i n g d a t a W i t h 6-PAD becomes m i n i m a l and, i n f a c t , U and V p e r f o r m e q u a l l y w e l l and b o t h p e r f o r m s l i g h t l y b e t t e r t h a n T. T h i s c l e a r l y i n d i c a t e s t h a t when s t o r a g e c a p a c i t y i s l i m i t e d a t r a d e - o f f e x i s t s between c o n t e x t u a l c o n s t r a i n t s and measurement s t a t i s t i c s . Suboptimum c l a s s i f i e r s w h i c h use. l e s s measurement s t a t i s t i c s and more c o n t e x t u a l d a t a may w e l l he-s u p e r i o r to optimum c l a s s i f i e r s w h i c h make l i t t l e o r no use of e x i s t i n g c o n t e x t u a l c o n s t r a i n t s . 41 Comparison of t h e r e s u l t s f o r T v s . W and U v s . Y shows t h a t n e g l e c t i n g t h e i n f o r m a t i o n c o n t a i n e d i n the l e n g t h of t h e f e a t u r e v e c t o r s , by making them e q u a l i n l e n g t h t h r o u g h t h e a d d i t i o n o f z e r o s , makes r e c o g n i t i o n more d i f f i c u . l t . I t s h o u l d be k e p t i n mind t h a t a l t h o u g h t h e f e a t u r e v e c t o r s i n W and Y a r e made l o n g e r by a d d i n g z e r o s , W and Y i n f a c t use. up much l e s s s t o r a g e t h a n T and U bec a u s e they s t o r e p r o b a b i l i t i e s f o r C_^ . r a t h e r t h a n C^,L c a t e g o r i e s . F o r T and U r e c o g n i t i o n a c c u r a c y improves as t h e number o f scans and d e c i s i o n t r e s s i n c r e a s e s . A l t h o u g h the e x p e r i m e n t s show t h a t t h e sca n s can i n d e e d improve r e c o g n i t i o n , t o f u l l y a p p r e c i a t e t h e i r c a p a b i l i t y , more e x p e r i m e n t s on l a r g e t e s t i n g s e t s would have t o be p e r f o r m e d . C o n s i d e r a b l e improvement r e s u l t s u s i n g 6-PAD r a t h e r t h a n 4-PAD w i t h a l l a l g o r i t h m s e x c e p t S. I t was e x p e c t e d t h a t S would p e r f o r m worse w i t h 6-PAD on t h e t e s t i n g d a t a b e c a u s e S has no g e n e r a l i z a t i o n c a p a b i l i t y and a l a r g e r number o f d i f f e r e n t f e a t u r e v e c t o r s have t o be l e a r n e d w i t h 6-PAD. Clemens [10] used t h e b i n a r y v e c t o r r e s u l t i n g f r o m 4-PAD, a l o n g w i t h two b i n a r y d i g i t s d e s c r i b i n g one o f the f o u r H/W r a t i o s o b s e r v e d , t o r e c o g n i z e 260 upper c a s e a l p h a b e t i c c h a r a c t e r s from 10 d i f f e r e n t t y p e f o n t s ( a l g o r i t h m S was u s e d ) . Even on t h e t r a i n i n g d a t a 15% e r r o r r e s u l t e d a l t h o u g h , by u s i n g x and y t h r e s h o l d s e q u a l t o 3/16 t h e l e t t e r h e i g h t , t h e e r r o r was r e d u c e d t o 3%. I m p o r t a n t extrema on many of t h e upper c a s e c h a r a c t e r s o c c u r i n s q u a r e s 100 and 101 i n F i g . 3, and t h e s e extrema a r e more a c c u r a t e l y l o c a t e d by a s i x - p a r t t h a n a f o u r - p a r t COORD word. I n a d d i t i o n , c h a r a c t e r s t h a t a r e commonly c o n f u s e d under 4-PAD, s u c h as P and D, due t o t h e f a c t t h a t t h e x max o c c u r s i n s q u a r e 10 f o r b o t h P and D, a r e not c o n f u s e d any more w i t h 6-PAD because the x l i e s i n r e c t a n g l e 101 f o r P and 001 f o r D i n F i g . 3. I n max a p p l y i n g Clemens' t e c h n i q u e t o t h e r e c o g n i t i o n o f upper ca s e h a n d p r i n t e d c h a r a c t e r s Munson [13] o b t a i n e d 42% m i s c l a s s i f i c a t i o n o f w h i c h 19% was r e j e c t when 2340 c h a r a c t e r s from seven w r i t e r s were used f o r t r a i n i n g and an ( a p p a r e n t l y ) comparable number of samples from d i f f e r e n t i n d i v i d u a l s was used f o r t e s t i n g . These r e s u l t s a r e f o r x and y t h r e s h o l d s o f 1/10 a c h a r a c t e r ' s w i d t h and h e i g h t , r e s p e c t i v e l y . P e r h a p s Munson's r e s u l t s would improve c o n s i d e r a b l y i f , i n a d d i -t i o n t o u s i n g a s i x - p a r t a r e a , e i t h e r a l a r g e r number o f t r a i n i n g samples were used o r t h e e x p e r i m e n t were r e p e a t e d u s i n g a l g o r i t h m T r a t h e r t h a n S. On. c o m p l e t e l y u n c o n s t r a i n e d c h a r a c t e r s t h e f e a t u r e e x t r a c t i o n scheme i n t h i s t h e s i s may e n c o u n t e r some d i f f i c u l t y w i t h b r o k e n c h a r a c t e r s such as "R" i n F i g . 10. Two methods of a t t a c k i n g t h i s p r o b l e m a r e s u g g e s t e d i n t h e n e x t s e c t i o n . Of c o u r s e the. p r o b l e m o f b r o k e n c h a r a c t e r s can' a l s o be s o l v e d by s i m p l y r e q u i r i n g t h a t p e o p l e a v o i d p r i n t i n g them, a c o n s t r a i n t w h i c h a p p a r e n t l y i n t h e s e e x p e r i m e n t s , d i d n o t cause t h e p r i n t e r r e a l d i f f i c u l t v a l t h o u g h some was r e p o r t e d i n [ 1 2 ] . A l l a l g o r i t h m s f o r a l l c a s e s p e r f o r m e d b e t t e r on i n d i v i d u a l s t h a n on t h e p o p u l a t i o n and i n some c a s e s t h e improvement was pronounced. F o r some c a s e s a l g o r i t h m s T and U y i e l d e d r e c o g n i t i o n a c c u r a c i e s o f 100% on t h e t r a i n i n g d a t a o f PERSONS 1 and 2 when t h e sca n s were used. As was e x p e c t e d b i g r a m and t r i g r a m i n f o r m a t i o n w i t h a l g o r i t h m G de-c r e a s e d P ( c ) f o r a l l c a s e s . L o o k i n g a t the TS 4-PAD and 6-PAD e r r o r c u r v e s o f F i g . 9 one can see t h a t t h e y t e n d t o f o l l o w a d e c r e a s i n g e x p o n e n t i a l p a t h . T h i s s u g g e s t s t h a t a d e c r e a s i n g amount o f new c o n t e x t u a l i n f o r m a t i o n becomes a v a i l a b l e by i n c r e a s i n g f u r t h e r the o r d e r o f the c o n t e x t u a l i n f o r m a t i o n used. I n f a c t t h e c u r v e s s u g g e s t t h a t P ( e ) would n o t . b e d e c r e a s e d s i g n i f i c a n t l y by g o i n g beyond 3 r d o r d e r c o n t e x t u a l i n f o r m a t i o n . The c u r v e s a l s o show t h a t as the o r d e r o f c o n t e x t i n c r e a s e s t h e d i f f e r e n c e i n p e r f o r m a n c e between 6-PAD and 4-PAD d e c r e a s e s a l t h o u g h i t s t i l l r emains i m p o r t a n t , n o t i n g t h a t 6-PAD w i t h b i g r a m s r e s u l t s i n a l o w e r P ( e ) tha n 4-PAD w i t h t r i g r a m s . I n a d d i t i o n i t i s much e a s i e r t o implement 6-PAD w i t h b i g r a m s because the storage, s a v i n g i n g o i n g from t r i g r a m s to b i g r a m s i s much g r e a t e r t h a n the e x t r a s t o r a g e 43 needed by t h e s l i g h t l y l o n g e r f e a t u r e v e c t o r s . These r e s u l t s i l l u s t r a t e t he i m p o r t a n c e o f b a l a n c i n g a p p r o p r i a t e l y the i n f o r m a t i o n from t h e measurements and from c o n t e x t as s u g g e s t e d by R a v i v [ 2 3 ] . I n a d d i t i o n , F i g . 8 shows t h a t i t i s a l s o i m p o r t a n t t o b a l a n c e c o n t e x t u a l i n f o r m a t i o n from t h e o r d e r o f t h e c o n t e x t used w i t h t h a t o b t a i n e d from t h e depth o f s e a r c h . A l t h o u g h f o r e v e r y v a l u e o f ds P ( e ) i s l o w e r f o r t r i g r a m s than f o r b i g r a m s , f o r bigra m s w i t h ds=4 i t . i s l o w e r t h a n f o r t r i g r a m s w i t h ds=3. I n a d d i t i o n , much l e s s s t o r a g e i s needed f o r b i g r a m s , and t h e c l a s s i f i c a t i o n , c o m p u t a t i o n i s r e d u c e d since»for the 2 former c a s e , 4 =16 a p o s t e r i o r i p r o b a b i l i t i e s a r e s e a r c h e d o r 8 p e r c h a r a c t e r , 3 w h i l e , f o r t h e l a t t e r c a s e , 3 =27 o r 9 p r o b a b i l i t i e s p e r c h a r a c t e r a r e s e a r c h e d . I t i s i n t e r e s t i n g t o n o t e t h a t t h e e x p e r i m e n t a l optimum v a l u e o f ds w i t h r e s p e c t t o P ( e ) does n o t c o r r e s p o n d w i t h t h a t p r e d i c t e d by eq. ( 2 9 ) . T h i s s u g g e s t s t h a t t h e a s s u m p t i o n s made i n s u b s e c t i o n 2.4.9 i n the d e r i v a t i o n o f (29) a r e n o t e n t i r e l y v a l i d . However, t h e a s s u m p t i o n s a r e n e v e r t h e l e s s n e c e s s a r y i n o r d e r t o make t h e s o l u t i o n f e a s i b l e . As was n o t e d i n s u b s e c t i o n 2.4.9 t h e c u r v e s o f F i g . 8 a r e e x p e c t e d t o depend a l s o On t h e d i s t r i b u t i o n o f t h e c o r r e c t l a b e l s ( c h a r a c t e r s ) w i t h r e s p e c t t o ds. I t i s r e a s o n a b l e t o e x p e c t P ( e ) t o d e c r e a s e a t an a c c e l e r a t i n g r a t e f o r low v a l u e s o f ds because f o r v e r y low v a l u e s o f ds l e s s c o n t e x t u a l i n f o r -m a t i o n i s made use o f . F o r example, out o f t h e 17,576 t h e o r e t i c a l l y p o s s i b l e t r i g r a m s o n l y 2,510 a r e E n g l i s h e n t r i e s i n t h e s e e x p e r i m e n t s ; w"hen ds has a 3 v a l u e o f 2 o n l y 2 o r 8 out o f t h e p o s s i b l e 17,576 a r e l o o k e d a t . One can see t h a t t h e r e i s a s i g n i f i c a n t p r o b a b i l i t y t h a t t h e 8 t r i g r a m s l o o k e d a t a r e p a r t o f t h e 15,066 i l l e g a l t r i g r a m s a f t e r w h i c h a d e c i s i o n i s made i n d i v i d u a l l y x ^ i t h o u t the use of c o n t e x t . T h i s was o b s e r v e d to happen q u i t e f r e q u e n t l y f o r ds=2. and l e s s f r e q u e n t l y f o r ds=3. I n s p i t e o f the. f r e q u e n t d i s r e g a r d f o r c o n t e x t when ds = 2, P ( e ) f o r bigram s was s t i l l s l i g h t l y l o w e r than t h a t r e s u l t i n g from the use o f monograms. 44 I t would seem from t h i s data that the bulk of the c o r r e c t l a b e l s occurs f o r ds <_ 4. This would help to e x p l a i n the s l i g h t i n c r e a s e i n P(e). : for-ds > 4. I f the greater part of the c o r r e c t l a b e l s occurs f o r ds < 4, i n c r e a s i n g ds f u r t h e r , would only i n c r e a s e the chance of f i n d i n g an erroneous bigram or tri g r a m w i t h a higher a p o s t e r i o r i p r o b a b i l i t y than the c o r r e c t one, and thus increase P ( e ) . 5.2 Suggestions f o r Further Research Since the requirement that people avoid p r i n t i n g broken characters may not be a d e s i r a b l e c o n s t r a i n t , i n view of the f a c t that some p r i n t e r s [12] found d i f f i c u l t y i n overcoming t h i s c o n s t r a i n t , two ways of handling un-constrained data are suggested. One c o r r e c t i v e measure i s to c l o s e small breaks by blackening a l l white squares adjacent to a bl a c k square and repeating t h i s procedure a c e r t a i n number of times. However, i f the break i s more than a few u n i t s wide the character can be d i s t o r t e d c o n s i d e r a b l y by rep e a t i n g the above procedure enough times to c l o s e the break. A second a l t e r n a t i v e without t h i s disadvantage i s to move a bar of length b along the outside contour, keeping one end of the bar against the contour and maintaining an angle of 90° between the bar and the l i n e tangent to the contour at the bar-contour point of contact. Whenever the other end of the bar encounters b l a c k during the contour t r a c e , the l i n e defined by that p o r t i o n of the bar between the two bl a c k p o i n t s i s made part of the c h a r a c t e r , as i n F i g . 10. The bar must be long enough to c l o s e most breaks but short enough that i n t e n t i o n a l breaks that d i f f e r e n t i a t e p a t t e r n c l a s s e s remain. More experiments w i t h and without the above methods should be per-formed on l a r g e unconstrained data s e t s . One source of feat u r e v e c t o r v a r i a b i l i t y w i t h i n p a t t e r n c l a s s e s i n the present scheme i s the mode of searching f o r the cha r a c t e r . In many characters 45 F i g . 10 I l l u s t r a t i n g a t e c h n i q u e f o r c l o s i n g s m a l l b r e a k s i n b r o k e n c h a r a c t e r s . t h e l e f t m o s t b l a c k p a r t o f t h e c h a r a c t e r may o c c u r a t t h e top o r t h e bottom o f the c h a r a c t e r i n v a r i o u s samples o f t h e same c h a r a c t e r , e s p e c i a l l y i f p r i n t e r s s l a n t i n d i f f e r e n t ways. T h i s causes t h e v e r t i c a l s e a r c h mode t o e n c o u n t e r t h e c h a r a c t e r sometimes a t t h e u p p e r - l e f t m o s t p a r t and sometimes a t t h e l o w e r -l e f t m o s t p a r t , r e s u l t i n g i n d i f f e r e n t f e a t u r e v e c t o r s . I n most o f t h e s e c a s e s , a d i a g o n a l s e a r c h mode a t 135 degrees w o u l d e n c o u n t e r t h e l o w e r - l e f t m o s t p a r t o f a c h a r a c t e r o n l y . As can be seen i n F i g . 6, w i t h E n g l i s h a p r i o r i p r o b a b i l i t i e s U p e r -formed b e t t e r on TS-6-PAD tha n T, even though U i s a s i m p l e r c l a s s i f i e r and uses l e s s s t o r a g e . S i m i l a r methods to a l g o r i t h m G f o r b i g r a m s and t r i g r a m s s h o u l d 46 be t e s t e d u s i n g U t o compare w i t h G's r e s u l t s . 5.3 Summary o f C o n c l u s i o n s A l t h o u g h f i n a l c o n c l u s i o n s s h o u l d w a i t f o r e x p e r i m e n t s on s e v e r a l l a r g e d a t a s e t s , i t a p p e a r s t h a t t h e p a r a m e t r i c c l a s s i f i e r s T, U and V o p e r a t i n g on b i n a r y v e c t o r s o b t a i n e d from c o n t o u r s o f c h a r a c t e r s q u a n t i z e d as i n F i g . 3 y i e l d r e c o g n i t i o n a c c u r a c i e s much b e t t e r t h a n t h o s e o b t a i n a b l e u s i n g the optimum n o n p a r a m e t r i c c l a s s i f i e r S, and t h a t i f 6-PAD i s used r e a s o n a b l y good r e c o g n i t i o n a c c u r a c i e s can be a c h i e v e d , p a r t i c u l a r l y i f E n g l i s h a p r i o r i p r o b a b i l i t i e s o f the c h a r a c t e r s a r e i n c o r p o r a t e d . The r e s u l t s a l s o s u g g e s t t h a t r e c o g n i t i o n schemes w h i c h use a d d i t i o n a l s i m p l e c l a s s dependent f e a t u r e e x t r a c t i o n t o d i f f e r e n t i a t e between commonly c o n f u s e d c h a r a c t e r s may p e r f o r m s i g n i f i c a n t l y b e t t e r t h a n t h o s e w h i c h use o n l y one f e a t u r e e x t r a c t i o n method common t o a l l p a t t e r n c l a s s e s . " I n a d d i t i o n , i t appears t h a t a l g o r i t h m G u s i n g b i g r a m and t r i g r a m s t a t i s t i c s , w i t h a d e p t h o f s e a r c h v a l u e e q u a l t o 4, can s i g n i f i c a n t l y improve the r e c o g n i t i o n a c c u r a c y . These c o n c l u s i o n s s u p p o r t t h o s e o f B a k i s e t a l . [5] t h a t c u r v e - f o l l o w i n g f e a t u r e s e x t r a c t the s i g n i f i c a n t i n f o r m a t i o n from h a n d p r i n t i n g , and t h o s e o f R a v i v [23] and Duda and H a r t [2<'] t h a t u s i n g t h e measurements of n e i g h b o u r i n g c h a r a c t e r s t o g e t h e r w i t h c o n t e x -t u a l c o n s t r a i n t s g r e a t l y i m p r o v e s ' t h e r e c o g n i t i o n a c c u r a c y . 4 7 REFERENCES 1. W.W. B l e d s o e and J. B r o w n i n g , " P a t t e r n r e c o g n i t i o n and r e a d i n g by machine," P a t t e r n R e c o g n i t i o n , L. Uhr., Ed., pp. 301-316, W i l e y , New Y o r k , 1966. 2. L. Uhr and C. V o s s l e r , "A p a t t e r n - r e c o g n i t i o n program t h a t g e n e r a t e s , e v a l u a t e s and a d j u s t s i t s own o p e r a t o r s , " Computers and Thought, Feigenbaum and Feldman, Eds., pp. 251-268, M c G r a w - H i l l , New Y o r k , 1963. 3. W.H. H i g h l e y m a n , " L i n e a r d e c i s i o n f u n c t i o n s w i t h a p p l i c a t i o n t o p a t t e r n r e c o g n i t i o n , " P r o c . IRE, V o l . 50, No. 6, pp. 1501-1514, June, 1962. 4. L.A. Kamentsky, "The s i m u l a t i o n of t h r e e machines w h i c h r e a d rows o f hand-w r i t t e n a r a b i c numbers," IRE T r a n s , on E l e c t r o n i c Computers, V o l . EC-10, No. 3, pp. 489-501, September, 1961. 5. R. B a k i s , N.M. H e r b s t , and G. Nagy, "An e x p e r i m e n t a l s t u d y of machine r e c o g -n i t i o n o f h a n d p r i n t e d n u m e r a l s , " IEEE T r a n s , on Systems S c i e n c e and C y b e r n e t i c s , V o l . SSC-4, pp. 119-132, J u l y , 1968. 6. E.C. G r e a n i a s , e t - a l . , "The r e c o g n i t i o n of h a n d w r i t t e n n u m erals by c o n t o u r a n a l y s i s , " IBM J o u r n a l , V o l . 7, No. 1, pp. 14-21, J a n u a r y , 1963. 7. L.G. R o b e r t s , " P a t t e r n r e c o g n i t i o n w i t h an a d a p t i v e n e t w o r k , " IRE 1960 I n t e r n a t i o n a l C o n v e n t i o n r e c o r d , pp. 66-70. 8. W.H. H i g h l e y m a n , "An a n a l o g method f o r c h a r a c t e r r e c o g n i t i o n , " IRE T r a n s . on E l e c t r o n i c Computers, V o l . EC-10, pp. 502.-512 , September, 1961. 9. R.L. G r i m s d a l e , e t a l . , "A s y s t e m f o r t h e a u t o m a t i c r e c o g n i t i o n o f p a t t e r n s , " P r o c . IEE , V o l . 106B, No. 26, pp. 210-221, March, 1959. 10. J.K. Clemens, " O p t i c a l 'Character R e c o g n i t i o n f o r Pleading Machine A p p l i c a t i o n s , " Ph.D. t h e s i s , Department of E l e c t r i c a l E n g i n e e r i n g , M.I.T., Cambridge, Mass., A u g u s t , 1965. 11. J.K. Clemens, " 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 f o r r e a d i n g machine a p p l i c a t i o n s , " M.I.T. E l e c t r o n i c s R e s e r a c h Lab., Cambridge Mass., Q u a r t . P r o g r e s s Rept. 79, pp. 219-227, O c t o b e r , 1965. 12. M.M. Chodrow, W . A . B i o v o n a and G.M. W a l s h , "A Study o f H a n d - P r i n t e d h a r a c t e r R e c o g n i t i o n T e c h n i q u e s , " Rome A i r Development C e n t e r T e c h n i c a l Report No. RADC-TR-65-444, F e b r u a r y , 1966. 13. J.H. Munson, "The r e c o g n i t i o n o f h a n d p r i n t e d t e x t , " P a t t e r n R e c o g n i t i o n , L. K a n a l , Ed., Thompson Book Co., W a s h i n g t o n , D.C, 1968. 14. D.D. J o h n s o n , C.F. Haugh, and K.P. L i , "The a p p l i c a t i o n of a few hyperplane. d e c i s i o n t e c h n i q u e s to h a n d p r i n t e d c h a r a c t e r r e c o g n i t i o n , " P r o c . NEC, V o l . 22, pp. 869-874, 1966.' 15. J.H. Munson, " E x p e r i m e n t s i n the r e c o g n i t i o n of h a n d - p r i n t e d t e x t : P a r t I -C h a r a c t e r r e c o g n i t i o n , " F a l l J o i n t Computer C o n f e r e n c e AFIPS P r o c . , V o l . 33, p t . 2, pp. 1125-1138, Thompson, W a s h i n g t o n , D.C, 1968. 4 8 16. A.L. K n o l l , " E x p e r i m e n t s w i t h ' c h a r a c t e r i s t i c l o c i ' f o r r e c o g n i t i o n of h a n d p r i n t e d c h a r a c t e r s , " IEEE T r a n s , on E l e c t r o n i c Computers, V o l . EC-18, pp. 366-372, A p r i l , 1969. 17. R.W. Cornew, "A s t a t i s t i c a l method of e r r o r c o r r e c t i o n , " I n f o r m a t i o n and C o n t r o l , No. 2, F e b r u a r y , 1968. 18. R. A l t e r , " U t i l i z a t i o n o f c o n t e x t u a l c o n s t r a i n t s i n a u t o m a t i c speech r e c o g n i t i o n , " IEEE T r a n s , on A u d i o and E l e c t r o a c o u s t i c s , March, 1968. 19. G. C a r l s o n , " T e c h n i q u e s f o r r e p l a c i n g c h a r a c t e r s t h a t a r e g a r b l e d on i n p u t , " AFIPS C o n f e r e n c e P r o c e e d i n g s , V o l . 28, 1966 S p r i n g J o i n t Computer Conf., pp. 189-192. 20. A.W. Edwards and R.L. Chambers, "Can a p r i o r i p r o b a b i l i t i e s h e l p i n c h a r a c t e r r e c o g n i t i o n ? " J . A s s o c . Computing M a c h i n e r y , V o l . 11, pp. 465-470, O c t o b e r , 1964. 21. K. Abend, "Compound d e c i s i o n p r o c e d u r e s f o r p a t t e r n r e c o g n i t i o n , " P r o c . NEC, V o l . 22, pp. 777-780, 1966. 22. K. Abend, "Compound d e c i s i o n p r o c e d u r e s f o r unknown d i s t r i b u t i o n s and f o r dependent s t a t e s of n a t u r e , " P a t t e r n R e c o g n i t i o n , L. K a n a l , Ed., Thompson Book Co., W a s h i n g t o n , D.C, 1968. 23. J . R a v i v , " D e c i s i o n making i n Markov c h a i n s a p p l i e d t o t h e p r o b l e m o f p a t t e r n r e c o g n i t i o n , " IEEE T r a n s , on I n f o r m a t i o n T h e o r y , V o l . IT-13, pp. 536-551, O c t o b e r 1967. . 24. R.O. Duda and P.E. H a r t , " E x p e r i m e n t s i n t h e r e c o g n i t i o n o f h a n d p r i n t e d t e x t : P a r t I I - c o n t e x t a n a l y s i s , " 1968 F a l l J o i n t Computer Conf. AFIPS P r o c . V o l . 33, p t . 2, W a s h i n g t o n , D.C: Thompson, 1968, pp. 1139-1149. 25. M.D. L e v i n e , " F e a t u r e e x t r a c t i o n : A s u r v e y , " P r o c . of IEEE, V o l . 57, No.. 8, pp. 1391-1407, A u g u s t , 1969. 26. S . J . Mason and J.K. Clemens, " C h a r a c t e r r e c o g n i t i o n i n an e x p e r i m e n t a l r e a d i n g machine f o r t h e b l i n d , " R e c o g n i z i n g P a t t e r n s , P.A. K o l e r s and M. Eden, ed. , The M.I.T. P r e s s , Cambridge, Mass., 1968, pp. 156-167. 27. G. Nagy, " S t a t e o f t h e a r t i n p a t t e r n r e c o g n i t i o n , " P r o c . IEEE, V o l . 56, pp. 836-862, May, 1968. 28. D.E. T r o x e l , F.F. Lee, and S . J . Mason, "Re a d i n g Machine f o r the B l i n d , " Q u a r t e r l y P r o g r e s s R e p o r t No. 89, R e s e a r c h L a b o r a t o r y o f E l e c t r o n i c s , M.I.T., A p r i l 15, 1968, pp. 245-248. 29. D.E. T r o x e l , "Page r e a d e r f o r a r e a d i n g machine f o r t h e b l i n d , " Q u a r t e r l y P r o g r e s s R e p o r t No. 94, R e s e a r c h L a b o r a t o r y of E l e c t r o n i c s , M.I.T., J u l y 15, 1969, pp. 233-246. 30. F. A t t n e a v e . a n d M.D. A r n o u l t , "The. q u a n t i t a t i v e s t u d y o f shape and p a t t e r n p e r c e p t i o n , " P a t t e r n R e c o g n i t i o n , L. Uhr, Ed., pp. 123-141, W i l e y , New Y o r k , 1966. 49 31. J.A. Bradshaw, " L e t t e r r e c o g n i t i o n u s i n g c a p t i v e s c a n , " IEEE T r a n s , on E l e c t r o n i c Computers, EC-12, p. 26, F e b r u a r y , 1963. 32. A.G. Semenovskiy, " R e c o g n i t i o n o f h a n d w r i t t e n c h a r a c t e r s by: means of a s e r v o s c a n , " C h a r a c t e r Readers and P a t t e r n R e c o g n i t i o n , V.A. K o v a l e v s k y Ed., S p a r t a n Books, New Y o r k , 1968, pp. 213-222^ 33. C M . A u s t i n , " D e s i g n and C o n s t r u c t i o n o f an Opaque O p t i c a l C o n t o u r T r a c e r f o r 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 , " M.A.Sc. T h e s i s , 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 , December, 1967. 34. K.S. Fu, " S e q u e n t i a l Methods i n P a t t e r n R e c o g n i t i o n and Machine L e a r n i n g , ' ' Academic P r e s s , New York and London, 1968. 35. N.J. N i 1 s s o n , ''Learning M a c h i n e s : F o u n d a t i o n s of T r a i n a b l e P a t t e r n -c l a s s i f y i n g Systems," M c G r a w - H i l l , 1965. 36. E. F i x , and J . L . Hodges, J r . , " D i s c r i m i n a t o r y A n a l y s i s , N o n p a r a r a e t r i c D i s c r i m i n a t i o n : C o n s i s t e n c y P r o p e r t i e s , " P r o j e c t 21-49-004, USAF S c h o o l o f A v i a t i o n M e d i c i n e , Randolph F i e l d , T e x a s , F e b r u a r y , 1951. 37. C K . Chow, " S t a t i s t i c a l i ndependence and t h r e s h o l d , f u n c t i o n , " IEEE T r a n s . E l e c t r o n i c Computers, V o l . EC-14, pp. 66-68, F e b r u a r y , 1965. 38. G.S. S e b e s t y e n , " D e c i s i o n - m a k i n g p r o c e s s e s i n p a t t e r n r e c o g n i t i o n , " The M a c m i l l a n Company, New Y o r k , 1962 39. J.M. W o z e n c r a f t and I.M. J a c o b s , " P r i n c i p l e s o f Communication E n g i n e e r i n g , " J o h n W i l e y & Sons, I n c . , New Y o r k , 1965, pp. 459-460. 40. ' L. K a n a l and B. C h a n d r a s e k a r a n , "On d i m e n s i o n a l i t y and sample s i z e i s s t a t i s t i c a l p a t t e r n c l a s s i f i c a t i o n " , N a t i o n a l E l e c t r o n i c s C o n f e r e n c e , C h i c a g o , 1968, pp. 2-7. 41. W.H. H i g h l e y m a n , "The d e s i g n and a n a l y s i s of p a t t e r n r e c o g n i t i o n e x p e r i -ments," The B e l l System T e c h n i c a l J o u r n a l , M a r c h , 1962, pp. 723-744. 42. P.A. L a c h e n b r u c h and M.R.'Mickey, " E s t i m a t i o n of E r r o r R a t e s i n D i s -c r i m i n a n t A n a l y s i s , " T e c h n o m e t r i c s , V o l . 10, No. 1, F e b r u a r y , 1968, pp. 1-11. 43. W.C C o c h r a n , "Commentary on " E s t i m a t i o n of E r r o r R a t e s i n D i s c r i m i n a n t A n a l y s i s , " T e c h n o m e t r i c s , V o l . 10, No. 1, F e b r u a r y , 1968, pp. 204-205. 44. J.R. P i e r c e , "Symbols, S i g n a l s and N o i s e : The n a t u r e and p r o c e s s o f c o m m u n i c a t i o n , " Harper & Row, New Y o r k , 1961, p. 283. 45. F. P r a t t , " S e c r e t and U r g e n t , t h e s t o r y o f codes and c i p h e r s , " B l u e R i b b o n Books, Garden C i t y , New Y o r k , 1942. ' 46. C T . T o u s s a i n t and R.W. D o n a l d s o n , " A l g o r i t h m s f o r r e c o g n i z i n g c o n t o u r -t r a c e d h a n d p r i n t e d c h a r a c t e r s , " IEEE T r a n s a c t i o n s on Computers, i n p r e s s . F. Hughes, ''On the mean a c c u r a c y o f s t a t i s t i c a l p a t t e r n r e c o g n i z e r s , IEEE T r a n s , on I n f o r m a t i o n T h e o r y , V o l . IT-14, No. 1, J a n u a r y 1968, pp. 55-63.