UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Machine recognition of typewritten characters based on shape descriptors Kanciar, Eugene J.A. 1974

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

Item Metadata

Download

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

Full Text

MACHINE RECOGNITION OF TYPEWRITTEN CHARACTERS BASED ON SHAPE DESCRIPTORS  by  Eugene J . A . K a n c i a r B.A.Sc,  U n i v e r s i t y of Western O n t a r i o , 1972  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE  in  the  Department of  Electrical  Engineering  We a c c e p t t h i s t h e s i s as required^standard  conforming to  THE UNIVERSITY OF BRITISH COLUMBIA O c t o b e r , 1974  the  In  presenting  an  advanced  the I  Library  further  for  degree shall  agree  scholarly  by  his  of  this  written  this  thesis  in  at  University  the  make  that  it  purposes  for  freely  permission may  representatives. thesis  partial  is  financial  of  of  Columbia,  British  available for  by  the  understood  gain  for  extensive  be g r a n t e d  It  fulfilment  shall  Head  be  permission.  (  Department  of  The U n i v e r s i t y o f B r i t i s h Vancouver 8, Canada  Date  Columbia  requirements  reference copying  that  not  the  of  agree  and  of my  I  this  or  allowed  without  that  study. thesis  Department  copying  for  or  publication my  ii ABSTRACT An 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 t e c h n i q u e  f o r typewritten  l e t t e r s was d e v e l o p e d w i t h a p p l i c a t i o n t o a p e r s o n a l r e a d i n g machine for the b l i n d .  The f e a t u r e e x t r a c t i o n p r o c e s s d e f i n e d a c h a r a c t e r  i n terms o f l i n e s and shapes w h i c h a r e c l o s e l y r e l a t e d t o a p e r s o n ' s d e s c r i p t i o n o f form.  The system was developed t o i d e n t i f y a l l upper  and l o w e r - c a s e t y p e w r i t t e n c h a r a c t e r s i n t h e a l p h a b e t .  A l e t t e r was  d e s c r i b e d by any c o m b i n a t i o n o f seven b a s i c f e a t u r e s , u s u a l l y i n a 3x3  feature matrix.  The e x t r a c t i o n o f t o p o l o g i c a l ( o r s t r u c t u r a l )  p r o p e r t i e s had s e v e r a l advantages; a v e r y s m a l l f e a t u r e d i c t i o n a r y w i t h about 100 code-word e n t r i e s ; q u i c k and s i m p l e t r a i n i n g p r o c e d u r e f o r a new f o n t ; and, a s t r o n g c a p a b i l i t y t o h a n d l e c h a r a c t e r d e f o r m i t i e s . A separate  technique,  based on edge e x a m i n a t i o n ,  was d e v e l o p e d t o  i d e n t i f y c h a r a c t e r s w i t h prominent d i a g o n a l f e a t u r e s .  Sequential  c l a s s i f i c a t i o n was employed t h r o u g h o u t t h e e n t i r e system so t h a t r e c o g n i t i o n was made once a s u f f i c i e n t l y unique measure was s a t i s f i e d . T e s t s on b o t h r e p e a t e d p ^ c f ' j ^ ^ d ^p"-^c"i™."*"cly 7 Q  < y  characters  and  t y p e w r i t t e n passages  c"cu"ccy v h c n t h e s y t — *.— c ~pp i c 1  J  *~z  t h r e e f o n t s w h i c h v a r i e d from a s t y l i z e d t o a s e r i f l e s s p r i n t . F o r a scanning  r a t e o f 60 wpm, a r e c o g n i t i o n speed o f two c h a r a c t e r s p e r  second was a c h i e v e d . i s f u l l y compatible memory.  The system was d e v e l o p e d on a PDP-12 computer and f o r r e a l i z a t i o n on a PDP-8 computer w i t h 8K o f  iii  TABLE OF CONTENTS Page Abstract  i i  Table of Contents  •  L i s t of I l l u s t r a t i o n s Acknowledgement I.  II.  v .  ....  v i  INTRODUCTION  1  1.1  Purpose o f R e s e a r c h  1.2  Perspective  1.3  E x i s t i n g Schemes  1.4  ••  '? ?  1 1  •• •  2  1.3.1  Template M a t c h i n g  2  1.3.2  Contour T r a c i n g  3  A New Approach  4  THE PATTERN RECOGNITION SCHEME 2.1  i i i  6  Introduction Ir^v.T.t? -  6  „ . ; . . . . . . . . . . . » • • >i' . . . . . i '  2.3  Preprocessing  6  2.4  Feature E x t r a c t i o n , Part 1  7  2.4.1  Introduction  2.4.2  B a s i c Concepts  7  2.4.3  String Indentification  8  2.4.4  Four L e v e l R e s o l u t i o n  9  2.4.5  B a s i c F e a t u r e Assignment  10  2.4.6  V e r t i c a l Compression  12  2.4.7  Serif Deletion  13  2.4.8  H o r i z o n t a l Feature I n t e g r a t i o n  14  2.4.9  H o r i z o n t a l Compression  16  2.4.10 2.5  An Example w i t h C u r v a t u r e  •  7  17  Feature E x t r a c t i o n , Part 2  19  2.5.1  Characters with Diagonals  19  2.5.2  S p e c i a l Cases  20  iv  2.6  2.7 III  IV  Classification  20  2.6.1 I n t r o d u c t i o n  20  2.6.2 Code-Word G e n e r a t i o n  21  2.6.3 Subgroup Assignment  21  2.6.4 I d e n t i f i c a t i o n  22  O v e r a l l System C o n f i g u r a t i o n  23  TESTS AND RESULTS  24  3.1  D e s c r i p t i o n o f Test M a t e r i a l  24  3.2  T e s t s and R e s u l t s w i t h Repeated L e t t e r s  25  3.3  T e s t s and R e s u l t s w i t h T y p e w r i t t e n P a s s a g e s  25  3.4  Sources o f E r r o r  26  3.5  T r a i n i n g Procedure  28  3.6  Speed  28  3.7  System S t o r a g e R e q u i r e m e n t s  29  3.8  System F l e x i b i l i t y  29  CONCLUSION  30  4.1  Summary  30  4.2  Recommendations f o r F u r t h e r R e s e a r c h  31  References  33  APPENDIX A  Confusion Matrices  35  APPENDIX B  Examples o f t h e C h a r a c t e r R e c o g n i t i o n P r o c e s s ....  40  APPENDIX C  Examples o f E r r o r s  43  APPENDIX D  Examples o f System F l e x i b i l i t y  45  APPENDIX E  B a s i c Flowchart f o r t h e Diagonal Checking Routine.  47  V  L I S T OF ILLUSTRATIONS Page 1.  The template  m a t c h i n g scheme  2  2.  The c o n t o u r t r a c i n g scheme  4  3.  The c l o s u r e c r i t e r i a  8  4.  String identifications  5.  Four l e v e l r e s o l u t i o n o f s t r i n g i n f o r m a t i o n f o r t h e l e t t e r  i n t h e l e t t e r 'R'  9  'R'  10  6.  B a s i c f e a t u r e a s s i g n m e n t s f o r t h e l e t t e r 'R'  12  7.  Vertical  12  8.  Serif  9.  H o r i z o n t a l f e a t u r e i n t e g r a t i o n f o r t h e l e t t e r 'R'  10. 11.  H o r i z o n t a l c o m p r e s s i o n f o r t h e l e t t e r ' R' Feature i n t e g r a t i o n a p p l i e d t o a character w i t h the l e t t e r ' s' as an example  12.  compression t o three l e v e l s  f o r t h e l e t t e r 'R' ...  d e l e t i o n i n t h e l e t t e r 'R'  13  R e c o g n i t i o n o f d i a g o n a l c h a r a c t e r s by s e l e c t i v e examination  16 17 curvature, 18 edge 19  13.  The t h r e e code-words f o r t h e l e t t e r 'R'  21  14.  Subgrouping t h e a l p h a b e t  22  15.  Character  16.  B l o c k diagram o f t h e system  17.  The t h r e e f o n t s used i n t h e t e s t s ,  18.  Suggested c l o s u r e c r i t e r i a t o r e p l a c e t h e c r i t e r i a i n Figure 3  identification,  the l e t t e r  ' c ' as an example ...  23 23  reproduced i n f u l l s i z e  24 32  ACKNOWLEDGEMENT The a u t h o r w o u l d l i k e t o t h a n k Dr. M.P. Beddoes f o r h i s c o n s t a n t i n t e r e s t and i n p u t o f i d e a s i n t o t h i s p r o j e c t . time t o my i n q u i r i e s  The a v a i l a b i l i t y o f h i s  i s gratefully appreciated.  Thanks a r e a l s o due t o  Rodney G. George f o r a l l h i s a s s i s t a n c e w i t h s o f t w a r e i m p l e m e n t a t i o n as w e l l as h i s p r a c t i c a l i n s i g h t i n t o problem a r e a s .  F i n a l l y I would l i k e  t o e x t e n d my a p p r e c i a t i o n t o a l l t h e g r a d u a t e s t u d e n t s , f a c u l t y and s t a f f w i t h whom I s h a r e d my e x p e r i e n c e s . F i n a n c i a l a s s i s t a n c e was p r o v i d e d b y t h e N a t i o n a l R e s e a r c h C o u n c i l o f Canada, t h e M e d i c a l R e s e a r c h C o u n c i l o f Canada, and t h e Vancouver F o u n d a t i o n .  1 I.  1.1  INTRODUCTION  Purpose o f Research The  purpose o f t h i s r e s e a r c h was t o : (1) d e v i s e an 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 scheme t h a t would be a p p l i c a b l e t o a p e r s o n a l r e a d i n g machine f o r t h e b l i n d ;  (2) d e v e l o p a f e a t u r e e x t r a c t i o n  t e c h n i q u e based on shape a n a l y s i s and comparable t o human d e s c r i p t i o n of form; (3) o b t a i n p r e l i m i n a r y r e c o g n i t i o n r e s u l t s and d e t e r m i n e the s o u r c e s o f e r r o r s w i t h t y p e w r i t t e n  1.2  characters.  Perspective The b a s i c a p p r o a c h t o r e a d i n g a i d s f o r t h e b l i n d has been  to develop d i r e c t t r a n s l a t i n g devices of c h a r a c t e r s w i t h e i t h e r t a c t i l e The  advantages a c h i e v e d  t h a t produce f a c s i m i l e r e p r o d u c t i o n s  [4] o r a u d i t o r y [ 3 ] , [20] o u t p u t .  i n t h i s approach a r e compactness, t e c h n i c a l  s i m p l i c i t y , and economy. The d i s a d v a n t a g e s o f t h i s approach a r e t h a t the r e a d e r must be t r a i n e d t o decode t h e o u t p u t and t h e r e a d i n g  rates  are low. The n e x t o r d e r o f c o m p l e x i t y  i n a r e a d i n g machine h a s been  t o employ OCR ( 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 ) w i t h s p e l l e d o r spoken speech a s o u t p u t .  Character  r e c o g n i t i o n schemes have been i n c o m m e r c i a l  use f o r a number o f y e a r s . P r e s e n t u s e r s o f OCR i n c l u d e t h e p o s t o f f i c e , government, and i n d u s t r i a l c o n c e r n s .  I n t h e s e c a s e s OCR i s used w i t h  a p p l i c a t i o n s r e q u i r i n g l a r g e volume, h i g h speed, and a c c u r a c y .  Usually  t h e s e schemes u t i l i z e a w e l l d e f i n e d s e t o f c h a r a c t e r s . By c o n t r a s t , r e l a x a t i o n o f many performance c r i t e r i a may be a p p l i e d t o a p e r s o n a l r e a d i n g machine; b u t , a t t h e same t i m e t h i s machine must cope w i t h a w i d e r range o f f o n t s and p r i n t i n g q u a l i t y t h a n t h o s e w h i c h a r e e n c o u n t e r e d i n commercial a p p l i c a t i o n s . Two schemes have been d e v e l o p e d o v e r t h e l a s t t e n y e a r s f o r t h i s p a r t i c u l a r purpose and t h e s e a r e d i s c u s s e d i n t h e n e x t s e c t i o n .  2  1.3  E x i s t i n g Schemes  1.3.1  Template M a t c h i n g One s o l u t i o n t o t h e OCR p r o b l e m has been Smith-Mauch s 1  t e m p l a t e m a t c h i n g scheme [ 2 0 ] .  The l o c a t i o n s o f b l a c k a r e a s ,  encountered  as t h e t e m p l a t e scans a c r o s s t h e c h a r a c t e r , a r e p r o c e s s e d t o i d e n t i f y it.  T h i s system, i l l u s t r a t e d i n F i g u r e  probe t h a t f o c u s e s  1, c o n s i s t s o f a hand h e l d  the p r i n t e d c h a r a c t e r onto a two-dimensional p h o t o c e l l  a r r a y o f 12 s e n s o r s .  The d i s c r i m i n a t i n g r o u t i n e i s a p p l i e d i n a  m u l t i p l e snapshot sequence.  As a c h a r a c t e r i s scanned a c r o s s t h e  optical input, i t stimulates a trigger c e l l to b l a c k o r b l a c k t o w h i t e t r a n s i t i o n o c c u r s  (TC).  i n the t r i g g e r c e l l ,  a snapshot o f a l l t h e c e l l s i n t e m p l a t e i s t a k e n . c e l l s i s converted The  Every time a w h i t e Output f r o m t h e s e  i n t o a f i v e - b i t code t h a t s p e c i f i e s t h e c h a r a c t e r .  o b j e c t i v e o f t h i s scheme i s a n a c c u r a c y o f 90% t o 9 5 % a t 80 wpm  to 90 wpm b u t t h i s h a s y e t t o be a c h i e v e d . i s about 20 wpm t o 25 wpm.  The p r e s e n t  reading  speed  The r e c o g n i t i o n l o g i c o f t h i s machine i s  designed w i t h i n t e g r a t e d c i r c u i t s . For t h i s scheme t o work w e l l , s e v e r a l c r i t i c a l p a r a m e t e r s must be s a t i s f i e d . i s important.  The e x a c t p o s i t i o n i n g o f t h e t e m p l a t e o v e r t h e l e t t e r  A l s o , t h e t h r e s h o l d f o r i n f o r m a t i o n when a c e l l on t h e  template i s only p a r t i a l l y i n a b l a c k f i e l d  i s a relevant consideration.  T h i s scheme, i n e x t r a c t i n g s p a t i a l i n f o r m a t i o n i n a snapshot manner, does not make good use o f g e o m e t r i c o r s t r u c t u r a l p r o p e r t i e s w h i c h r e q u i r e more c o n t i n u o u s measurements.  Thus t h e system's p e r f o r m a n c e i s l i m i t e d  because t h e e x t r a c t e d i n f o r m a t i o n i s n o t c o m p l e t e enough t o h a n d l e problems s u c h as c h a r a c t e r d i s t o r t i o n s o r a m b i g u i t i e s .  FIRST "SNAPSHOT"  Fig.  1  SECOND "SNAPSHOT"  The t e m p l a t e m a t c h i n g scheme.  THIRD "SNAPSHOT"  FOURTH "SNAPSHOT"  3  1.3.2  Contour T r a c i n g Mason [16] and Clemens [6] proposed a n OCR scheme w h i c h  u t i l i z e d contour  tracing.  This technique,  i l l u s t r a t e d i n F i g u r e 2,  r e q u i r e s t h r e e p i e c e s o f i n f o r m a t i o n : a code word t h a t s p e c i f i e s t h e c h a r a c t e r ' s g e o m e t r i c extrema i n t h e x and y d i r e c t i o n s ; a c o o r d word w h i c h s t o r e s the l o c a t i o n o f each extremum; and,  the  height-to-width  r a t i o (H/W) t h a t c l a s s i f i e s t h e c h a r a c t e r i n t o one o f f o u r subgroups. From t h e s e measurements a 3 0 - b i t code word i s d e r i v e d .  The l o o k u p  t a b l e c o n t a i n s t h r e e t o f i v e p o s s i b i l i t i e s f o r e v e r y c h a r a c t e r . The o r i g i n a l scheme, a s d e v e l o p e d b y Clemens [6] a c h i e v e d  1% t o 3% e r r o r a t  100 wpm and was t e s t e d o n t e n f o n t s .  F u r t h e r improvements upon the  system have r e d u c e d the e r r o r t o 0.1%  b u t t h i s has been a c h i e v e d o n work  w i t h o n l y one f o n t [ 1 3 ] , [ 1 6 ] .  T h i s system u s e s a PDP-9 t y p e o f computer  and r e q u i r e s a f l y i n g spot scanner f o r the d a t a i n p u t . The shape.  code word i s a good t o p o l o g i c a l d e s c r i p t i o n o f a c h a r a c t e r ' s  However b o t h t h e c o o r d word and the h e i g h t - t o - w i d t h r a t i o  are  r i g i d g e o m e t r i c measurements w h i c h do not make t h i s scheme r e a d i l y auap U c t u x c Lu  uLuei  J.UHL&.  iiie  COGi.ll w G i i U  j_o d  £>cuSi.kiyc  iUii^i-j-Cix o f  p o s i t i o n and a s s u c h , i t w i l l a l t e r a s t h e extrema a r e l o c a t e d i n new regions.  The h e i g h t - t o - w i d t h r a t i o s a l s o v a r y among t h e d i f f e r e n t f o n t s . The  p r i n t m a t e r i a l u s e d b y Mason and Clemens t o t e s t  r e c o g n i z e r was f r e e from b r e a k s .  their  As t h e r e c o g n i z e r deduces from t h e  p r i n t n o t o n l y t h e p r i n t i n f o r m a t i o n b u t a l s o the p o s i t i o n t o e x p l o r e n e x t , a b r e a k produces a doubly c a t a s t r o p h i c e r r o r . These b r e a k e r r o r s are minimized Lee  b y u s i n g h i g h r e s o l u t i o n (60 x 60 p o i n t s were used b y  [13]). One  l a s t b a s i c l i m i t a t i o n w i t h t h e Mason-Clemens r e c o g n i z e r  i s t h a t o n l y the o u t s i d e c o n t o u r o f a c h a r a c t e r i s u s e d . p a i r s o f c h a r a c t e r s such a s 'D' and 'B',  W i t h ambiguous  ' c ' and 'e', a s p e c i a l t e c h n i q u e ,  s u c h as t a k i n g a v e r t i c a l s l i c e t h r o u g h the c h a r a c t e r ' s c e n t r e and n o t i n g the number o f i n t e r s e c t i o n s (two o r t h r e e ) was u s e d , b e c a u s e t h e o u t s i d e c o n t o u r was a n i n s u f f i c i e n t measure.  i.  code word:  1 0  0  1 1  2. coord word: 00 00 00 10 3. H/W  start-* ( 00  Fig. 2 1.4  01  ratio  10  The contour tracing scheme.  A New  Approach The pattern recognition techniques that have been developed  on large computers are not r e a l i z a b l e on small, economical processors. S t a t i s t i c a l and p r o b a b a l i s t i c approaches [2], [11] are not applicable for t h i s purpose because of t h e i r complexity.  The two schemes discussed  i n Section 1.3 represent one*approach to the problem; that i s , d i s c r e t e s p a t i a l information was  extracted and no attempt was made to integrate  the measurements into more general and higher order information. t h i s thesis such a new  approach was  In  undertaken.  The process of i d e n t i f y i n g a l e t t e r by means of features i s w e l l known [1], [14].  However, r e s u l t s show that a complex machine i s  needed to recognize one  font [16].  This work set out, as a main aim,  to invent a set of features to i d e n t i f y a l e t t e r simply.  A further  consideration has been to r e l a t e these features to descriptors of shape which would appear natural to the human reader.  For example, with the  l e t t e r 'b' we could use the d e s c r i p t i o n : "a s t r a i g h t v e r t i c a l l i n e at the l e f t which c a r r i e s a l i t t l e f l a g ( s e r i f ) at the top; t h i s l i n e i n t e r s e c t s two h o r i z o n t a l l i n e s , one at the bottom and one h a l f way up, which are traced to the r i g h t and, moving together, form a j u n c t i o n at the r i g h t . "  This compact d e s c r i p t i o n of form i s strongly t o p o l o g i c a l  and gives the g i s t of how  t h i s OCR  scheme i n t e r p r e t s a character.  technique requires seven features to characterize a l e t t e r . the l e t t e r was technique was  Our  Usually  reconstructed w i t h i n a 3 x 3 feature matrix. A s p e c i a l used f o r characters with prominent diagonal features, such  5  as 'W',  whereby t h e c h a r a c t e r ' s edge was u s e d f o r i t s i d e n t i f i c a t i o n .  T h i s scheme s h o u l d be l e s s s e n s i t i v e t o d i s t o r t i o n and more f l e x i b l e i n i t s r e c o g n i t i o n c a p a b i l i t y t h a n t h e e x i s t i n g schemes. T h i s t h e s i s i s based on o r i g i n a l work and i s c o n c e p t u a l l y most s i m i l a r t o work done b y G e n c h i [12] and Marko [ 1 5 ] . G e n c h i has d e v e l o p e d an OCR scheme w h i c h i s used i n the Japanese p o s t a l s y s t e m f o r r e c o g n i t i o n of handprinted  numerals.  The numerals were  by e x t r a c t i n g a sequence o f f e a t u r e s i n h o r i z o n t a l zones.  recognized A 3 x 3  s c a n n i n g window i d e n t i f i e d each 9 element a r r a y as one o f 7 p o s s i b l e s t r o k e segments such as b l a n k , v e r t i c a l , s l a n t e d , e t c . I n t h e second s t e p , each h o r i z o n t a l s t r i n g o f s t r o k e segments was c l a s s i f i e d one o f 16 h o r i z o n t a l f e a t u r e s .  into  The t h i r d s t e p was t o c o n n e c t  v e r t i c a l l y a l l the i n d i v i d u a l h o r i z o n t a l f e a t u r e s by u s i n g a t r a n s i t i o n table.  The c h a r a c t e r was r e c o g n i z e d b y t h i s t a b l e . W i t h Marko's system,  s p a t i a l f i l t e r i n g was performed on t h e c h a r a c t e r i n f o u r d i r e c t i o n s ( h o r i z o n t a l , v e r t i c a l , and two d i a g o n a l d i r e c t i o n s ) .  From t h i s  h i g h e r o r d e r f e a t u r e s such as a n g l e s , c u r v a t u r e s , and e n d p o i n t s extracted. matrix.  processing, were  I n f o r m a t i o n was t h e n i n t e g r a t e d i n t o a v e r y compact f e a t u r e  F i n a l l y , a weighting  w h i c h were t h e n p r o c e s s e d  scheme was a p p l i e d t o t h e s e  by the c l a s s i f i e r .  features  6  II. 2.1  THE PATTERN RECOGNITION SCHEME  Introduction In order to describe the techniques  employed i n t h e c h a r a c t e r  r e c o g n i t i o n system i t i s u s e f u l t o employ a g e n e r a l model f o r a p a t t e r n r e c o g n i t i o n system w i t h each s t e p i n t h e p r o c e s s i n g b e i n g  input -Mpreprocessor\-^\feature  identified:  extractorh^classifien-*  output  The s c a n n e r i s t h e t r a n s d u c e r , a p h o t o - e l e c t r i c d e v i c e , w h i c h converts the p r i n t e d character i n t o a two-state p r e p r o c e s s o r , i f p r e s e n t , employs t e c h n i q u e s and s t r o k e t h i n n i n g .  ( b i n a r y ) i n p u t . The  such a s d a t a n o r m a l i z a t i o n  The purpose o f t h e f e a t u r e e x t r a c t o r I s t o o b t a i n .  a s e t o f c h a r a c t e r i s t i c measures and s t a t e m e n t s  upon w h i c h a d e c i s i o n  as t o t h e most p r o b a b l e i d e n t i t y o f t h e p a t t e r n sample c a n be made.  The  c l a s s i f i e r , on t h e b a s i s o f t h e i n f o r m a t i o n p r o v i d e d by t h e f e a t u r e e x t r a c t o r , a p p l i e s a d e c i s i o n c r i t e r i o n t o t h e p a t t e r n measurements t o make a d e c i s i o n a s t o w h i c h , i f any, belongs.  2.2  o f the allowable c l a s s e s the p a t t e r n  The o u t p u t r e l a y s t h e i d e n t i f i c a t i o n i n a n a p p r o p r i a t e form.  Input A 64 v e r t i c a l element  R e t i c o n RL-64P s o l i d - s t a t e l i n e s c a n n e r  p r o v i d e d t h e i n p u t f o r a PDP-12 computer. corresponded  t o approximately  The speed o f t h e s c a n  60 words p e r m i n u t e .  The t y p i c a l  p i c t u r e frame f o r a s i n g l e upper c a s e c h a r a c t e r c o n t a i n e d 15 x 30 elements and 12 x 20 elements f o r a s m a l l l o w e r c a s e l e t t e r .  2.3  Preprocessing Preprocessing r e f e r s to data manipulation i n the primary  s t a g e s o f a p r o c e s s so t h a t redundancy and d i s t o r t i o n c a n be a p p r e c i a b l y reduced.  I n t h e OCR scheme t h a t was d e v e l o p e d ,  was no f o r m a l p r e p r o c e s s i n g .  there  I t was b e l i e v e d t h a t t h e s u c c e s s i v e  s t a g e s o f i n f o r m a t i o n h a n d l i n g c o n t a i n e d enough s o p h i s t i c a t i o n t o be a b l e t o cope w i t h t h e i n h e r e n t n o i s e i n t h e b i n a r y d a t a . was  d e s i g n e d w i t h t h i s p r e m i s e i n mind.  A preprocessor  The system [24] c a n have  the f o l l o w i n g o b j e c t i v e s : a c h a r a c t e r s h o u l d i d e a l l y be o f u n i t  7  thickness;  t h i s s k e l e t o n must resemble t h e l i n e p a t t e r n a human  w o u l d draw, t h a t i s , no i n f o r m a t i o n o t h e r than t h e l i n e w i d t h i s l o s t ; b r e a k s i n t h e c h a r a c t e r must be s e a r c h e d the c o n t i n u i t y s h o u l d be r e s t o r e d .  f o r and, where m i s s i n g ,  As u s e f u l as t h e s e o b j e c t i v e s may  be, f o r t h i s s p e c i f i c a p p l i c a t i o n , where t h e c o s t o f machine implement a t i o n must be k e p t l o w and a n e r r o r r a t e o f a few p e r c e n t tolerated, t h i s preprocessing  2.4  can be  i s not j u s t i f i e d .  Feature E x t r a c t i o n , P a r t 1  2.4.1  Introduction F e a t u r e e x t r a c t i o n i n OCR h a s r e c e i v e d c o n s i d e r a b l e a t t e n t i o n  because t h e e f f e c t i v e n e s s o f t h i s s t a g e p r e d i c a t e s t h e r e c o g n i t i o n a b i l i t y o f t h e e n t i r e system. of three p o s s i b l e techniques  I t c o n s i s t s o f one o r a  combination  [21] : g e o m e t r i c a l , t o p o l o g i c a l and  mathematical (or s t a t i s t i c a l ) feature e x t r a c t i o n . T o p o l o g i c a l feature e x t r a c t i o n has been c o n s i d e r e d i n t h e r e c o g n i t i o n o f h a n d w r i t t e n characters.  Eden and H a l l e [9] found t h a t o n l y 18 d i f f e r e n t s t r o k e s  were needed t o c o n s t r u c t any E n g l i s h c h a r a c t e r .  By p a r t i t i o n i n g t h e  p e r i m e t e r around a c h a r a c t e r i n t o e i g h t s e c t i o n s , Tou [22] was a b l e to  e x t r a c t t o p o l o g i c a l f e a t u r e s s u c h a s b a y s , i n f l e c t i o n s and  c u r v a t u r e s from each o c t a n t . t o p o l o g y has been r e p o r t e d  I n t e r e s t i n g work on  computational  [23] , however, t h i s a p p r o a c h i s y e t t o .  be a p p l i e d .  2.4.2  B a s i c Concepts I m p o r t a n t c o n c e p t s and terms a r e i n t r o d u c e d . A s t r i n g i s  a continuous  segment o f b i n a r y l ' s w i t h i n a column and has t h e  p r o p e r t y l e n g t h , L.  Each s t r i n g i s c h a r a c t e r i z e d by one o f t h r e e  d e s c r i p t i o n s : a v e r t i c a l (V), a closure (C), o r a centre c e l l (CC). F o r a c h a r a c t e r o f h e i g h t H, H/4=T+R (where t h e r e m a i n d e r , R, i s 0 ^ 3 ) d e f i n e s t h e 1/4 h e i g h t t h r e s h o l d T. Two types o f v e r t i c a l s a r e d e f i n e d : a f u l l v e r t i c a l and a minor v e r t i c a l .  A s t r i n g w i t h T<L<3T was a s s i g n e d a minor v e r t i c a l .  A s t r i n g w i t h L>3T was a s s i g n e d a f u l l  vertical.  8  Whenever two b r a n c h e s o f a c h a r a c t e r converged t o o r d i v e r g e d from a s t r i n g common t o b o t h ,  t h a t s t r i n g was c l a s s i f i e d a s a c l o s u r e .  I n t h e l e t t e r ' c ' i n F i g u r e 3, column t h r e n i s i d e n t i f i e d a s a c l o s u r e because i t i n i t i a t e s t h e d i v e r g e n c e  o f t h e two b r a n c h e s i n column f o u r .  For c l o s u r e t o e x i s t a l l t h e c o n d i t i o n s i n F i g u r e 3, must b e s a t i s f i e d . If  columns t h r e e and f o u r a r e i n t e r c h a n g e d  convergence.  the t e s t would i n d i c a t e  Any s t r i n g w h i c h was c l a s s i f i e d a s a minor v e r t i c a l was  tested for closure.  I f t h e s t r i n g was i d e n t i f i e d a s a f u l l v e r t i c a l ,  the c l o s u r e c r i t e r i o n was n o t a p p l i e d . A s t r i n g w i t h L<T was a s s i g n e d  i t s centre c e l l .  s t r i n g w i t h T/2<L<T was a l s o checked f o r a c l o s u r e .  However, a  Occasionally a  c l o s u r e d i d o c c u r e w i t h L<T/2 and i n t h e s e c a s e s t h e c l o s u r e was m i s s e d but t h e s e e r r o r s were i n f r e q u e n t . I oooooo ooo ooo ? oo I ooo oo oo ooo oo ooo oo ooo oo ooo oo ooo ooo "55  +  +  88  oo oo °°„ go ooo oo oo ooo ooooooooo oooooo  F i g . 3 The c l o s u r e 2.4.3  String The  4  16 — C . lo^ A—oo « oo—D o o o o o g  II-  8  A>C n D  <  u E  o _ oo—E B—oo 0—F  criteria.  Identification l e t t e r 'R* was c h o s e n t o d e m o n s t r a t e t h e OCR t e c h n i q u e  t h a t was d e v e l o p e d .  A t y p i c a l b i n a r y p i c t u r e f o r t h e l e t t e r 'R' i s  shown i n F i g u r e 4A. The  f i r s t i n f o r m a t i o n t o b e n o t e d about t h e c h a r a c t e r was i t s  h e i g h t and w i d t h  (28 x 17) and, T (28/4=7).  one t h r o u g h t h r e e were l e s s t h a n T. d e s c r i b e d b y i t s CC.  The s t r i n g s i n columns  Thus each s t r i n g was c o m p l e t e l y  F o r t h e s t r i n g i n column f o u r L>3T, s o a f u l l  v e r t i c a l was n o t e d . information.  Columns f i v e t h r o u g h e l e v e n c o n t a i n e d  o n l y CC  I n column t w e l v e t h e f i r s t s t r i n g was a s s i g n e d  i t s CC.  F o r t h e second s t r i n g T<L<3T; t h i s was t h e c o n d i t i o n f o r f u r t h e r processing  t o d e t e r m i n e i f t h e s t r i n g was b e s t d e s c r i b e d as a minor  v e r t i c a l or a closure.  I n t h i s case divergence  was i n d i c a t e d . I n  column t h i r t e e n t h e f i r s t two s t r i n g s were c l a s s i f i e d a s CC's b u t t h e t h i r d s t r i n g , T<L<3T a n d a g a i n a check f o r c l o s u r e was i n i t i a t e d . s t r i n g conveyed l e n g t h i n f o r m a t i o n o n l y and was i d e n t i f i e d a s V.  "This The  f i r s t s t r i n g i n column f o u r t e e n was a l s o t e s t e d f o r c l o s u r e and was found t o b e t h e convergence f o r t h e two b r a n c h e s i n column t h i r t e e n . The  remaining  s t r i n g s i n t h e c h a r a c t e r were a l l CC's.  These  i d e n t i f i c a t i o n s a r e t a b u l a t e d i n F i g u r e 4B. 12345678901234567 ooooooooooo ooo oooo oo oo o oo o oo o oo o o o o o o o o oo oo oo oo ooo oo ooooooooo oo oooo o oo o o oo o oo o oo oo o oo o oo oo oo oo oo oo oo ooooooo ooo oooooooo ooooo  1  2  3  1  1  1 V  27 27 27  4  5  6  7  8  9 10 11 12 13 14 15 16 17  1  1  1  1  1  1  1  13 13 14 14 14 15 15 ?n 97 ?7 ?8  2  4  C 27 28 28  C 12 27 V  26  F i g u r e 4B  12345678901234567  F i g u r e 4A Fig.  4  2.4.4  S t r i n g i d e n t i f i c a t i o n s i n t h e l e t t e r 'R'. Four L e v e l The  Resolution  c h o i c e o f a f o u r l e v e l r e s o l u t i o n system was b a s e d on  the f a c t t h a t t h e maximum number o f f e a t u r e l e v e l s i n any E n g l i s h alphanumeric i s f o u r .  The number o f f e a t u r e l e v e l s i s e q u a l t o t h e  maximum number o f i n t e r s e c t i o n s t h a t a v e r t i c a l l i n e c a n make t h r o u g h a character.  F o r example, t h e c h a r a c t e r s  have f o u r , t h r e e , and two f e a t u r e l e v e l s .  'g', 'e', a n d 'o' r e s p e c t i v e l y The r e s o l u t i o n f r o m t h i s  arrangement p r o v e d s a t i s f a c t o r y . Thus t h e s t r i n g i d e n t i f i c a t i o n s f o r  each column were q u a n t i z e d i n t o one o f f o u r p o s s i b l e v e r t i c a l  quadrants.  F o r t h e example t r e a t e d i n S e c t i o n 2.4.3, t h e i n f o r m a t i o n s o p r o c e s s e d appears i n F i g u r e 5.  1  The b l a n k q u a d r a n t s a r e z e r o  2 3 4 5 6  entries.  7 8 9 10 11 12 13 14 15 16 17  1 1 V 1 1 1 1 1 27 27 27 13 13 1A 1A 1A 15 15 1  2 A C 27 28 28 C 12 27 V  20 27 27 28 26 1  1  1 V  27 27 27  Fig.  5  2.4.5.  1  1  1  1  1  1  1  2 A C 12  C  V 13 13 1A 1A 1A V 20 15 15  C V  V 26 27 27 28  C V 27 27 28 28  Four l e v e l r e s o l u t i o n o f s t r i n g i n f o r m a t i o n f o r t h e l e t t e r 'R'. B a s i c F e a t u r e Assignment Each column e n t r y o f d a t a i s compared t o t h e i n f o r m a t i o n  s t o r e d i n t h e n e x t column.  T h i s c o m p a r i s o n r e s u l t s i n one o t s i x  b a s i c features being assigned : (/) U - Up (\) D - Down (—) H - H o r i z o n t a l ( | ) V - Vertical (X)  C - Closure  ( • ) Z - Zero F o r two a d j a c e n t columns, a p a i r o f a d j a c e n t can be o b t a i n e d . for  two a d j a c e n t  F i g u r e 6A summarizes t h e f e a t u r e s e l e c t i o n p r o c e s s columns.  The assignment o f b a s i c f e a t u r e s i s  i l l u s t r a t e d i n F i g u r e 6B. second, t h e f i r s t  elements (X,Y)  (X,Y)  When t h e f i r s t column was compared t o t h e  p a i r was (1,1) w h i c h was r e p r e s e n t e d b y an H.  L i k e w i s e f o r t h e second p a i r (27,27). produced i d e n t i c a l r e s u l t s . s t u d i e d , t h e p a i r s (1,V)  The s e c o n d and t h i r d  columns  When t h e t h i r d and f o u r t h columns were  and (27,V) r e s u l t e d i n V e n t r i e s i n t h e f i r s t  and f o u r t h v e r t i c a l q u a d r a n t s .  These e n t r i e s , a l t h o u g h  they may seem  s u p e r f l u o u s , a r e n e c e s s a r y f o r the c o n t i n u i t y o f the f e a t u r e s e l e c t i o n process.  The r e a s o n i n g b e h i n d such e n t r i e s w i l l become e v i d e n t when  columns e l e v e n and t w e l v e a r e d i s c u s s e d . a s s i g n e d t o column f o u r . p a i r s (1,1) and (20,0).  A four l e v e l v e r t i c a l  I n columns f i v e and s i x , the f i r s t  (13,13) produced  two H f e a t u r e s .  I n such a case a check was performed  i m m e d i a t e l y above (13,13) and b e l o w ( 2 6 , 2 7 ) .  The  two  third pair  was  on the p a i r e d elements Thus (13,13) was  pared t o a p o s s i b l e c o m b i n a t i o n o f (20,13); s i m i l a r l y , compared t o (20,27).  was  com-  (26,27) was  I n b o t h c a s e s the (X,Y) c o m b i n a t i o n w i t h X = 20  was t h e p o o r e s t c h o i c e .  The comparison  t h e r e f o r e remains w i t h (20,0)  f o l l o w e d by the l a s t column p a i r (26,27).  These p a i r s r e s u l t i n Z  and D f e a t u r e s b e i n g e n t e r e d r e s p e c t i v e l y .  The second p a i r i n c o l -  umns n i n e and t e n (14,0) r e q u i r e d a s i m i l a r s e a r c h ; however, i n t h i s case a more a p p r o p r i a t e p a i r (14,15) was and thus a D f e a t u r e was  found d u r i n g t h e s e a r c h  s t o r e d i n t h e second l e v e l .  The  selected  b a s i c f e a t u r e was e n t e r e d on the same v e r t i c a l l e v e l as t h e X i n die  (X,Y)  pair,  i h e f i r s t p a i r (1,2) i n columns e l e v e n and  produced a D f e a t u r e .  F o r t h e second p a i r (15,C) C was  The r e a s o n f o r s t o r i n g C was  twelve  assigned.  t o m a i n t a i n the c o n t i n u i t y o f t h e  columns w i t h o u t i n t r o d u c i n g f a l s e i n f o r m a t i o n .  S i n c e the  first  p a i r (1,2) spanned b o t h columns, a Z e n t r y f o r a no comparison f o r t h e p a i r (15,C) would have b r o k e n column c o n t i n u i t y i n t h e row.  Whereas, p o s s i b l y e n t e r i n g an H f e a t u r e t o i n d i c a t e  c o n t i n u i t y w o u l d have i n t r o d u c e d new Now,  assume C i s e n t e r e d f o r (15,C).  second this  i n f o r m a t i o n i n t o the l e t t e r . The n e x t t i m e t h i s same C  i s e n c o u n t e r e d between columns t w e l v e and t h i r t e e n , i t w i l l as (C,V) and, from F i g u r e 6A, a n o t h e r C w i l l be e n t e r e d . C's w i l l have been e n t e r e d f o r t h e same datum.  appear  Thus two  As i t w i l l be shown  l a t e r , c o n t i n u o u s h o r i z o n t a l e n t r i e s o f C o r V can be reduced o n l y one C o r V w i t h o u t any l o s s o f i n f o r m a t i o n .  to  I  A . cc cc UDH  C  Col  Next Column C  V  ue  c  C  C  C  C  V  v  V  V  V  z  Z  z  z  z  01 to 41 M  Hi  V  1 .2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17  1  1 V  1  1  1  1  1  1  1  1  2  V 13 13 14 14 14  z  V 20 27 27 27  —  search f o r best y  F i g u r e 6A  V 26 27 27 28  11 1 1 1 1\  —  —  15 15  —  —  —  —  —  —  —  \  —  —  \  \  —  C C  C  V  C  V 27 27 28 28  \ X X  X X  X X 1 X 1— \  —  \  —  4 12  —  F i g u r e 6B  Fig. 6 2.4.6  B a s i c f e a t u r e a s s i g n m e n t s f o r t h e l e t t e r 'R* Vertical  Compression  A f t e r t h e assignment o f b a s i c f e a t u r e s , t h e c h a r a c t e r was compressed v e r t i c a l l y t o t h r e e h o r i z o n t a l rows w i t h t h e r e s u l t i n g advantages o f compactness and b e t t e r l e v e l c o n t i n u i t y . Rows two and t h r e e were compressed t o g e t h e r . The r e s u l t o f c o m p r e s s i o n between two b a s i c f e a t u r e s i s summarized  i n F i g u r e 7A.  The f o l l o w i n g  order  or s u p e r p o s i t i o n i n g dominance was imposed : (U,D,H)>C>V>Z. Rows two and t h r e e a r e compressed i n F i g u r e 7B. '  1  3 r d Row UDH  C  V  Z  =  UDH  UDH  UDH  UDH  C  C  C  UDH  C  V  V  UDH  c  V  z  ' .•»' •  &  o •o  UDH  C  (3 V  CM  z  —  2 —  —  —  —  —  —  Fig. 7  4  5  I 1 1 1 1 1\  6  —  7  8  9 10 11 12 13 14 15 16  —  —  —  —  —  —  \  —  —  \  —  11 1 \ 1 1\ —  —  —  —  —  no compression  F i g u r e 7A  3  —  \ —  —  —  —  —  —  \  —  \ F i g u r e 7B  \ \ X X  ....  X X X X 1 X 1— \  \ \ X X X X X X X 1— \  V e r t i c a l compression t o three l e v e l s f o r t h e l e t t e r  —  —  'R'.  13  2.4.7  Serif Deletion Serifs*  which a r e the c r o s s - l i n e s f i n i s h i n g o f f l e t t e r s ,  tend to increase a l e t t e r ' s l e g i b i l i t y .  However i n t h e machine  r e c o g n i t i o n p r o c e s s , t h e s e r i f s were c o n f u s i n g .  Due  to s e r i f s '  short  l e n g t h s , t h e p r i n t i n g q u a l i t y , and t h e r e s o l u t i o n o f t h e s c a n n e r , a s e r i f c o u l d be d e s c r i b e d by z e r o , one, i n t r o d u c e d an u n n e c e s s a r y amount o f s e r i f  o r more b a s i c f e a t u r e s .  This  variability.  To i n c r e a s e system r e p r o d u c i b i l i t y , h o r i z o n t a l s e r i f d e l e t i o n was  implemented.  S e r i f s a r e found i n t h e t o p and b o t t o m q u a d r a n t s o f a  l e t t e r and a r e a s s o c i a t e d w i t h v e r t i c a l s .  By a s s i g n i n g an  s e r i f l e n g t h f o r t h e f o n t b e i n g r e a d , s e a r c h i n g t h e t o p and  appropriate bottom  q u a d r a n t s o n l y , and n o t i n g t h e f a c t t h a t a s e r i f b e g i n s f r o m an empty s p a c e and ends i n a v e r t i c a l (and v i c e v e r s a ) , s e l e c t i v e d e l e t i o n o f s e r i f s was  achieved.  The s e r i f l e s s c h a r a c t e r i s p r e s e n t e d i n F i g u r e  I n a d d i t i o n t o t h e s e r i f s b e i n g d e l e t e d , t h e two v e r t i c a l s i n column t h r e e were a l s o e l i m i n a t e d .  A m i n o r r o u t i n e d e l e t e d any  column w h i c h  c o n t a i n e d o n l y e x t r a n e o u s v e r t i c a l s w i t h no U, D o r H i n f o r m a t i o n present.  F o r t h i s example, column f o u r c o u l d s u i t a b l y r e p r e s e n t a l l  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 b o t h columns t h r e e and  2  1 —  —  3  4  5  6  1 1 \ \ 1 1\ —  —  —  —  —  8  8  9 10 11 12 13 14 15 16  —  —  —  —  —  —  \  —  —  1 1 1 Fig.  7  \ \ X X  X X X X X 1 \ —  \ —  \  —  —  \  —  S e r i f d e l e t i o n i n the l e t t e r  \ X X  X X X X X 1 »R'.  —  four.  8.  14  2.4.8  H o r i z o n t a l Feature I n t e g r a t i o n A f t e r a l e t t e r was  compressed v e r t i c a l l y i n t o t h r e e rows,  h o r i z o n t a l f e a t u r e i n t e g r a t i o n ( o r c o m p r e s s i o n ) was row.  The  s t a t e t r a n s i t i o n t a b l e i n F i g u r e 9A was  a p p l i e d a l o n g each  used t o s e l e c t the  most a p p r o p r i a t e i n t e g r a t e d shape t h a t would d e s c r i b e a c o n t i n u o u s of i n d i v i d u a l U, D and H b a s i c f e a t u r e s .  The  programme took the  ent s t a t e of t h e f e a t u r e i n t e g r a t i o n p r o c e s s and n e x t b a s i c f e a t u r e t o g e n e r a t e the new the t a b l e r e p r e s e n t e d the p r e s e n t  state.  encountering  The n e g a t i v e  sign i n  r e i n i t i a l i z e d w i t h the n e x t b a s i c f e a t u r e upon  the n e g a t i v e  sign.  H i n d i v i d u a l elements i n t o one g e n e r a l i z e d f e a t u r e . c o m b i n a t i o n o f ) U, D or H c o n s e c u t i v e  b e f o r e any  the  As w e l l , the s t a t e  • E s s e n t i a l l y , the t a b l e encoded a c o n t i n u o u s row ( o r any  pres-  a t e r m i n a l c o n d i t i o n whereby the s y s t e m s t o r e d  s t a t e of the i n t e g r a t i o n p r o c e s s .  t r a n s i t i o n t a b l e was  compared i t t o  row  of U, D  At l e a s t  f e a t u r e s had  i n t e g r a t e d f e a t u r e c o u l d be a s s i g n e d .  two  to occur  Similarly,  minimum of two e n t r i e s were n e c e s s a r y f o r a g e n e r a l i z e d  and  a  Z.  A s i g n i f i c a n t d i f f e r e n c e o c c u r r e d w i t h the V and C f e a t u r e s . F o r t h i s s i t u a t i o n , one V o r C e n t r y was the g e n e r a l i z e d f e a t u r e s . had  T h i s was  g r e a t e r s i g n i f i c a n c e than any  enough t o c o n s i d e r them as  the case because t h e s e two  features  s i n g l e U, D, H o r Z e l e m e n t . Con-  t i n u o u s h o r i z o n t a l row e n t r i e s of e i t h e r V o r C were g e n e r a l i z e d i n t o o n l y one e n t r y o f the a p p r o p r i a t e  feature.  S i n c e C was  a more s e l e c -  t i v e o c c u r e n c e than V, i n a c o n t i n u o u s s t r i n g w i t h b o t h V and C e n t r i e s , C was The  chosen o v e r V t o be r e p r e s e n t a t i v e o f t h a t row  of f e a t u r e s .  r e a s o n f o r t h i s masking of V by C i s i l l u s t r a t e d by the l e t t e r  i n F i g u r e 3. t h r e e was  Column two was  the c l o s u r e .  c l a s s i f i e d as a minor v e r t i c a l ;  Column two i s e x p a n d i n g towards and  t h e c l o s u r e i n column t h r e e and c a n be r e p r e s e n t e d s i g n i f i c a n t f e a t u r e , the c l o s u r e .  'c'  column developing  by the more  The  above d i s c u s s i o n i s summarized as f o l l o w s :  for single entries: Z = U = D = H = 0 V = V, C = C f o r repeated  horizontal entries: X  n  = (<)  n - 1  X where X = ( Z, U, D, H, V, C )  f o r a row o f V and C e n t r i e s :  vm  The  c - v° = (<) n  m  +  °  +  n  -  h  symbol (<) i n d i c a t e d the c o n t i n u i t y a c r o s s columns of  feature to i t s right.  Integrated features other than  above are a l s o p o s s i b l e .  the  t h e one  listed  These o c c u r r e d w i t h c o m b i n a t i o n s o r U,  D,  and H f e a t u r e s ( S e c t i o n 2.4.10). F i g u r e 9B a p p l i e s t h e s t a t e t r a n s i t i o n t a b l e t o t h e example being developed. was  I n b o t h rows one  s t o r e d r a t h e r t h a n the D.  check w h i c h was  and  T h i s was  two a g e n e r a l i z e d H  feature  the r e s u l t o f an a d d i t i o n a l  p e r f o r m e d on the t e r m i n a l f e a t u r e s t a t e o f  the  i n t e g r a t i o n p r o c e s s t o e n s u r e t h a t t h e most a p p r o p r i a t e s e l e c t i o n had been made.  I n t h i s i n s t a n c e , a s i m p l e check on the f i r s t row s u c h as  n o t i n g t h a t t h e r e were s i x H and two D e l e m e n t s d i s q u a l i f i e d a D  entry.  I n s t e a d an H e n t r y was  was  deemed most s u i t a b l e .  a p p l i e d t o the second row.  The  To d e v i s e a l a r g e r and more complex s t a t e  t r a n s i t i o n t a b l e t o h a n d l e e v e r y p o s s i b i l i t y was mentally  impractical.  formance was  same c r i t e r i o n  found t o be e x p e r i -  Instead, s a t i s f a c t o r y feature i n t e g r a t i o n per-  achieved w i t h a two-step procedure.  T h i s was  accomplished  by u s i n g a t r a n s i t i o n t a b l e of moderate s i z e i n c o n j u n c t i o n w i t h a secondary v e r i f i c a t i o n r o u t i n e .  16  Next B a s i c Feature U  Z  V  C  IH  IU  Z  V  c  initial  IU  H  HH  U  IZ  V  c  i n i t i a l up  ID IH  D  LH  H  IZ  V  c  i n i t i a l down  LH  H  HH  IZ  V  c  i n i t i a l horizontal  teg rat ion  H  ID  V  -V  -V  -V  -V  V  c  vertical  C  -C  -C  -C  -C  c  c  closure  Row 1  LH  D  LH  PU  -H  -H  -H  low h o r i z o n t a l  State  e  HH  PD  HH  U  -H  -H  -H  high h o r i z o n t a l  Store  V  o  D  D  D  CU  -D  -D  -D  down  ate  D IZ  w CA  CA  U  U  -U  -U  -U  up  Row 2  CA  CA  U  -CA -CA -CA  cap  State  1  CU  D  CU  CU  -CU -CU -CU  cup  Store  V  PD  CA  PD  H  -H  -H  -H  peaked and downward  PU  H  PU  CU  -H  -H  -H  peaked and upward  Row 3  H  LH  H  HH  -H  -H  -H  horizontal  State  1  Z  -Z  -Z  -Z  Z  -Z  -Z  zero  Store  M  4-t CO  *J  resi  c  11)  1  zero  2  2.4.9  9  4  6  5  7  1_ 1 \ 1  —  —  \  —  1  —  —  —  —  —  V IH  —  11 H  H  H  9 10 n \ \ X X X X X X X 1 8  \ \ X X H LH  D  c  H —  \  —  —  V IH LH LH LH  V IZ  \ D  c  D  c  c  c  H  Z  Z  Z  Z  Z  Z  X 1 c  Z  c IZ  c  F i g u r e 9B  H o r i z o n t a l Compression Once t h e i n t e g r a t i o n p r o c e s s was c o m p l e t e d , h o r i z o n t a l The i n t e g r a t e d  features  a l l o w e d f o r a compact r e p r e s e n t a t i o n o f t h e l e t t e r . A f e a t u r e r e p r e s e n t a t i o n was o b t a i n e d i n t h e f o l l o w i n g manner.  matrix  The columns were  examined i n p a i r s , s t a r t i n g on t h e r i g h t s i d e and ending a t column one. A d j a c e n t h o r i z o n t a l q u a d r a n t s i n e a c h p a i r o f columns were c h e c k e d f o r continuities.  I f t h e r e e x i s t e d a t l e a s t one c o n t i n u i t y i n each p a i r  o f h o r i z o n t a l q u a d r a n t s t h e n t h e two columns were compressed i n t o one. T h i s p r o c e s s c o n t i n u e d u n t i l two a d j a c e n t encountered.  c c  H o r i z o n t a l f e a t u r e i n t e g r a t i o n f o r t h e l e t t e r 'R'.  c o m p r e s s i o n was a p p l i e d t o t h e c h a r a c t e r .  c  X X X X  —  V  F i g u r e 9A  Fig.  3  i n t e g r a t e d f e a t u r e s were  A t t h i s p o i n t t h e compressed column, w h i c h c o n t a i n e d a l l  17  the  f e a t u r e s t o t h e r i g h t o f i t , was s a v e d . Column c o m p r e s s i o n  then r e i n i t i a l i z e d w i t h the n e x t column.  was  R e f e r r i n g t o F i g u r e 10,  columns e l e v e n and t e n and n i n e t h r o u g h twc were reduced t o o n l y one column each.  1 2  1 1 1  F i g . 10. 2.4.10  3 4  5  6  7  8  <  <  <  <  <  <  <  <  <  <  <  <  <  <  <  <  <  A B C  9 10 11 —  <  <  <  <  <  <  X  1 1 1  X X  <  H o r i z o n t a l compression f o r t h e l e t t e r  — —  .c  X X . X  'R'  An example w i t h C u r v a t u r e To demonstrate t h e f u l l c a p a b i l i t i e s  o f the i n t e g r a t i o n p r o c e s s ,  e s p e c i a l l y i n the i d e n t i f i c a t i o n of c u r v a t u r e s , the l e t t e r selected. form.  * s ' was  I n F i g u r e 11, t h e l e t t e r has been r e d u c e d t o i t s t h r e e l e v e l  Each row was  horizontally  integrated w i t h the s t a t e t r a n s i t i o n  compressed.  The cap (r\)  and cup ( W )  t a b l e and t h e n  descriptions  were w e l l s u i t e d t o r e p r e s e n t t h e c u r v a t u r e s a l o n g the h o r i z o n t a l  levels.  T h i s example a l s o i l l u s t r a t e s t h e g e n e r a l i t y o f t h e c l o s u r e symbol (X)«  A c l o s u r e can r e p r e s e n t e i t h e r d i v e r g e n c e o r  E x p e r i m e n t a l l y i t was found t h a t the d i s t i n c t i o n between a  convergence. convergence  and a d i v e r g e n c e was n o t c r i t i c a l t o the l e t t e r ' s i d e n t i f i c a t i o n . assignment o f an a l l i n c l u s i v e  c l o s u r e (X)  was a c o n v e n i e n t  The  simplification.  18  Next B a s i c Feature D  H  U  Z  V  C  IZ  ID  IH  IU  Z  V  C  initial  IU  H  HH  U  IZ  V  c  i n i t i a l up  ID  D  LH  H  IZ  V  c  i n i t i a l down  1  zero  2  X  LH  H  HH  IZ  V  c  i n i t i a l horizontal  -V  -V  -V  -V  V  c  vertical  C  -c  -C  -C  -C  C  c  closure  Row 1  LH  D  LH  PU  -H  -H  -H  low h o r i z o n t a l  e m o  State  HH  PD  HH  U  -H  -H  -H  high h o r i z o n t a l  Store  C  D  D  D  CU  -D  -D  -D  down  ate  U  CA  U  U  -U  -U  -U  Row 2  CA  CA  CA  U  -CA -CA -CA  up cap  X  a  CU  D  CU  CU  -CU -CU -CU  cup  res<  \ \ 1 1\  IH  PD  CA  PD  H  -H  -H  -H  peaked and downward  teg rat  •ri  M  4-1 CO  4J  QJ  A  1X / /  V  a o  3  e  State  1X V  IZ  PU  H  PU  CU  -H  -H  -H  peaked and upward  Row 3  LH  H  HH  -H  -H  -H  horizontal  State  Z  -Z  -Z  -Z  Z  -Z  -Z  zero  Store^  / /  C IU  —  U  \  6  7  — —  —  u  —  —  —  —  u  9 10  \ \ 1  U PD CA  V  CA  V  \ \ \ X X  —  c Ill LH LH  D  D  D  C  D  1 1\ l \ -1/1/ v  8  \ \ 1 \ \ \ X X / / / X X  —  c  Store  H  —  5  V ID  »  c  / X X  D PU CU CU  V  c  CU  c  c c  A B C <  <  X X  1  <  <  <  <  <  <  <  <  <  <  <  <  <  <  <  <  \  <  <J  <  1  X X  X r\ 1 X \ X 1<j X  F i g . 11 F e a t u r e i n t e g r a t i o n a p p l i e d t o a c h a r a c t e r w i t h c u r v a t u r e w i t h the l e t t e r * s ' as an example.  19  2.5  Feature E x t r a c t i o n , P a r t 2  2.5.1  Characters w i t h Diagonals The l e t t e r s  'A, k, K, v , V, w, W, x, X, y, Y,' a r e c o m p r i s e d  b a s i c a l l y o f d i a g o n a l s and r e q u i r e a s e p a r a t e a p p r o a c h f o r t h e i r identification.  An a l t e r n a t e method o f f e a t u r e e x t r a c t i o n i s used.  I n F i g u r e 12, t h e m a j o r i t y o f the s t r i n g s w h i c h form t h e d i a g o n a l s a r e l o n g enough t o s a t i s f y L, where T<L<3T and a r e i d e n t i f i e d as m i n o r v e r t i c a l s ; thus, the d i r e c t i o n a l q u a l i t y of the diagonals i s l o s t . The most d e s c r i p t i v e f e a t u r e s i n t h e s e c h a r a c t e r s a r e t h e i r c o n t i n u o u s edge t r a n s i t i o n s .  By l o o k i n g a t t h e s i d e o f each c h a r a c t e r  from t h e d i r e c t i o n s i n d i c a t e d by t h e arrows i n F i g u r e 12, t h e u n o b s t r u c t e d ( s e r i f l e s s ) and u n i q u e d i a g o n a l f e a t u r e s a r e c l e a r l y identified.  U s i n g t h e programme i n Appendix E, each o f t h e d i a g o n a l  c h a r a c t e r s was viewed a l o n g i t s u n i q u e s i d e ( s ) : t h e top s i d e f o r 'A'; the b o t t o m s i d e f o r 'v, V, w, W'; f o r 'k, K, x, X, y, Y'. (number  and, b o t h t h e l e f t and r i g h t  sides  The s p e c i f i c a t i o n s o f a d i a g o n a l l e n g t h  o f i n c r e m e n t s ) and t h e up-down sequence f o r a p a r t i c u l a r  were used f o r t h i s subgroup's i d e n t i f i c a t i o n .  side  The l o c a t i o n o f t h i s  p a r t i c u l a r r o u t i n e i n t h e o v e r a l l system i s shown i n S e c t i o n 2.7.  _ >f _ £59 X x 2 _ g o o O O  o o o o o o o o o o o o o o O ° g X o o o o o o o o  O  o o o O O O O o o o o 2 ° 2 o o _ o o o g o g o o o Oo  =1  11  gg  gg  o oo oo o oo o o0 0 o o o o o o o a o o o o S o o o o  F i g . 12  o o o o o o o o o o oo 0 0 0 0 0 0 0 0o o o o o o o o o o o o o  o o o o o o o o o o o o  fie  8 8  O O O o o o o o o o o o o o  Q O O C O o o o o o o o o o o o o o o  O  OO  o n o o o o o o 5 o o  8° 8  o S o o So o o o p o o o o o o S o o o o o o o o ' o o o o o w  o o o o o o o o o  A •  V  _ o o o o o o o o o o o o o o Q O S o o o o o o o o o o o o o o o o o o o o o o  n  g§§  g8§  V  o o o o oooo oo o o o o o o o o o o g o . o o o o o o o o _ 2 2 o o o o o o o o o o o o o o o o o o o o 7  9  R e c o g n i t i o n o f d i a g o n a l c h a r a c t e r s by s e l e c t i v e edge e x a m i n a t i o n .  20  2.5.2  S p e c i a l Cases The  l e t t e r s 'g, i , j , m' d i d n o t r e q u i r e t h e e n t i r e f e a t u r e  e x t r a c t i o n process f o r t h e i r i d e n t i f i c a t i o n . I n these s p e c i a l cases the i d e n t i f i c a t i o n was made once a u n i q u e measurement was s a t i s f i e d . The  d i s t i n c t i v e c h a r a c t e r i s t i c of the l e t t e r s  t h a t they a r e d o t t e d .  ' i ' and 'j.' i s t h e f a c t  To d e t e c t t h e d o t a l l t h e columns were  i n c l u s i v e l y OR'ed"-together.  An ' i ' o r ' j ' was assumed i f a b r e a k  e x i s t e d i n t h e upper h a l f o f t h e OR'ed c h a r a c t e r .  The l e n g t h o f t h e  s e c t i o n below t h e dot was used t o d i s t i n g u i s h between t h e two; and  ' j ' without  t h e i r d o t s have t h e same h e i g h t a s a s m a l l and t a l l  character, respectively. in  the alphabet.  ' i '  The l e t t e r ' g  The c o n t e n t s  1  i s the only four l e v e l  character  o f l e v e l s two and t h r e e were a l w a y s  examined b e f o r e v e r t i c a l c o m p r e s s i o n ( S e c t i o n 2.4.7) t o t h r e e l e v e l s was  applied.  I f b o t h t h e second and t h i r d rows were f i l l e d  w i t h U, D,  and H i n f o r m a t i o n then t h e unknown c h a r a c t e r was i d e n t i f i e d as a 'g'. The  letter  'm' i s u n i q u e because i t c o n t a i n s t h r e e f u l l h e i g h t  verticals.  When t h i s c o n d i t i o n was s a t i s f i e d i n t h e s t r i n g i d e n t i f i c a t i o n r o u t i n e -(Section 2.4.3) an m :  :  was a s s i g n e d .  These measurements were s i m p l e and e f f e c t i v e . r e a l i z e d i n computational  The s a v i n g s  t i m e and i n t h e r e d u c t i o n o f e n t r i e s i n t h e  l o o k - u p t a b l e made t h i s a n a t t r a c t i v e approach.  2.6 2.6.1  Classification Introduction If  t h e c o s t o f t a k i n g f e a t u r e measurements i s h i g h ,  then  s e q u e n t i a l d e c i s i o n p r o c e d u r e s ( c l a s s i f i c a t i o n ) s h o u l d be a p p l i e d . This i s e s p e c i a l l y pertinent i n the design of the r e c o g n i t i o n l o g i c for  a p e r s o n a l r e a d i n g machine.  F u [8] emphasizes t h a t a t r a d e - o f f  between t h e e r r o r and t h e number o f f e a t u r e s t o be measured c a n be o b t a i n e d by t a k i n g measurements s e q u e n t i a l l y and t e r m i n a t i n g t h e p r o c e s s when a s u f f i c i e n t l y u n i q u e measurement i s s a t i s f i e d . must be o r d e r e d  The measurements  i n s u c h a way t h a t t h e e x t r a c t e d f e a t u r e s w i l l  the t e r m i n a l d e c i s i o n a s e a r l y as p o s s i b l e . incorporated i n this  classifier.  cause  These p r i n c i p l e s were  21  2.6.2  Code-Word Generation A code-word was  compressed character.  assigned to every h o r i z o n t a l l e v e l i n the  This code-word does not contain c o n t i n u i t i e s  (<). Furthermore, only a Z bounded on both sides by features other than a continuity or another Z was  stored i n the code-word. In Figure 13,  the three code-words f o r the l e t t e r *R* are generated.  Since there  are seven possible values f o r a feature, a minimum of three b i t s i s required to specify any one of these features.  Thus i n a twelve-bit  code-word, up to four features can be packed. Feature Matrix  Fig. 2.6.3  13  Feature  •  Code  0  / \  —-  1 2  3  1X  4  5  6  7  1 1  |  — —  •  The three code-words f o r the l e t t e r  Code-words  X X X  4  3  5  4  3  5  4  0  5  'R'.  Subgroup Assignment Rather than compare the code-words to a l l the alphabetic  p o s s i b i l i t i e s , a c l a s s i f i c a t i o n technique was  implemented which confined  the recognizer to search within a l i m i t e d subgroup of characters.  The  separation of characters into classes was based on two p h y s i c a l properties of a l e t t e r .  F i r s t , f o r a random s e l e c t i o n of characters,  'a, B, c, E, G, H, N, 0', the height i s used to separate small l e t t e r s from t a l l ones: 'a, c' and  'b, E, H, N, 0'. Secondly, the number  of f u l l character height v e r t i c a l s , whether zero, one, or two, further subgroups the characters: *a, c' (small l e t t e r s ) and and 'b, E' (one v e r t i c a l ) and  'H, N' (two v e r t i c a l s ) .  four d i s t i n c t classes are i d e n t i f i e d . Figure 14. included.  'G, 0' (no v e r t i c a l s ) In t h i s manner  The alphabet i s subgrouped i n  The s p e c i a l cases and the two forms 'g* and 'g' are also  22  Small L e t t e r s  a  c  e  n  o  r  No  C  G  0  Q  S  Z  b B  d D  f E  g F  h I  1 J  H  M  N  U  K  w V  W  y X  Y  i  j  m  Verticals  One V e r t i c a l Two  - l o w e r case -upper case  Verticals  Diagonal  C h a r a c t e r s - l o w e r case -upper case  S p e c i a l Cases  F i g . 14 2.6.4  k A  V  g  X  s  u  z  P L  q p  t R  T  Subgrouping t h e a l p h a b e t . Identif ication Three code-words were a s s i g n e d  f o r each o f t h e t h r e e f e a t u r e l e v e l s .  t o a n unknown c h a r a c t e r , one  The f i r s t code-word was compared  t o a l l t h e s t o r e d code-words f o r t h a t l e v e l , i n i t s a p p r o p r i a t e subgroup. Each code-word was a s s o c i a t e d w i t h a second t w e l v e - b i t word w h i c h s t o r e d a l l t h e p o s s i b l e c h a r a c t e r s w i t h t h a t code-word i n common. were l e s s  t h a n t w e l v e c h a r a c t e r s i n any upper o r l o w e r  Since  there  case subgroup,  each b i t o f t h e second t w e l v e - b i t word was a s s o c i a t e d w i t h a s p e c i f i c character.  The e n t r y o f a '1' o r '0' f o r a p a r t i c u l a r  b i t indicated  whether t h e code-word was common t o t h a t c h a r a c t e r o r n o t .  I f t h e code-  word was u n i q u e t o o n l y one c h a r a c t e r t h e n t h e i d e n t i f i c a t i o n was made a t t h a t p o i n t .  I f t h e code-word was s h a r e d by s e v e r a l c h a r a c t e r s ,  t h e n t h e s e p o s s i b i l i t i e s were r e c o d e d and t h e p r o c e s s was r e p e a t e d f o r t h e n e x t f e a t u r e l e v e l code-word. were found a f t e r was  I f no u n i q u e code-word matches  searching the three l e v e l s ,  then the i d e n t i f i c a t i o n  based o n t h e c h a r a c t e r w i t h t h e maximum number o f code-word matches. L e t us assume t h a t *-he unknown c h a r a c t e r i n F i g u r e 15 i s  t h e l e t t e r 'c'. ' c' and * s'.  The code-word f o r t h e f i r s t l e v e l i s common t o b o t h  However, t h e second l e v e l i n ' c ' i s u n i a u e t o i t and s o t h e  i d e n t i f i c a t i o n as ' c ' i s made.  F o r t h e example o f t h e l e t t e r 'R',  23  t h e r e a r e no u n i q u e code-words  and thus t h e i d e n t i f i c a t i o n i s b a s e d  on t h e maximum number o f code-word matches.  This character recognition  p r o c e s s i s i l l u s t r a t e d i n Appendix B.  1  X X  1  /  1 1  X X X  1 <  X X X  h —  1  x  X  1  p  1  1  1  x r > l x  1 XI  1  X XMIX  /  1  1 1  Subgroup  a c e n o r s u z  1st CW Matches  0 1 0 0 0 0 1 0 0  2nd CW Matches. 0 1 0 0 0 0 0 0 0  3rd CW Matches  F i g . 15  1. . /  1  1  1  1  1  1  1 —  X X  —  X X  i  Unique  0 1 1 0 0 0 0 0 0  Character i d e n t i f i c a t i o n ,  U V C J L d X X  X n 1 X \ X 1 <j X  u  t h e l e t t e r ' c' as an example.  U  The e n t i r e s y s t e m i s r e p r e s e n t e d i n b l o c k d i a g r a m f o r m i n F i g u r e 16.  The p a t t e r n r e c o g n i t i o n p r o c e s s h a s been b r o k e n down  i n t o i t s various stages.  Each s t a g e i s f u r t h e r i d e n t i f i e d a s t o t h e  r o u t i n e s w h i c h a r e performed w i t h i n i t .  The numbered r o u t i n e s i n d i c a t e  p r o c e s s e s t h a t o c c u r d u r i n g one major programme.  The l e t t e r i n g  refers  to d i s c r e t e r o u t i n e s t h a t a r e c l a s s i f i e d a c c o r d i n g t o t h e i r common f u n c t i o n .  input from photocell scanner  Initialization A. l . height and width 2. set a l l parameters ^ 3. store edgea along the four sides B. check for ' i V j  Identification 1. string identification (CC,V,C) 2. check for 'a'  and r i g h t edges  1  output via display and TTY  Classification A. subgroup assignment B. search through look-up tabic and identification  Feature Co isolidation A. horizontal feature integration B. horizontal compression into feature matrix C. assignment of three code-words  F i g . 16  Diagonal Check 1. 'A'-toD edee 2. *v,V,w,W'-bottom edge 3. 'k.K.x.X.v.Y'-left  B l o c k d i a g r a m o f t h e system.  Feature Extraction A. four level resolution B. basic feature assignment (Z,U,D,H,V,C)  Feature Enhancement A. l . check for ^Q' 2. vertical compression to three levels B. serif deletion  III.  3.1  TESTS AND RESULTS  D e s c r i p t i o n of the Test M a t e r i a l Three d i f f e r e n t t y p e w r i t e r f o n t s were used i n t h e t e s t i n g  of t h e system: Hermes Ambassador (HA), Gothic  (G).  IBM D e l e g a t e (D), and IBM  These f o n t s were s e l e c t e d because o f t h e i r l a r g e p r i n t  w h i c h e n s u r e d good machine r e s o l u t i o n . w r i t e r fonts are t h i s s i z e .  About o n e - h a l f  o f a l l type-  T h i s t h e s i s was t y p e d w i t h t h e IBM  P r e s t i g e - E l i t e font; i t s s i z e i s t y p i c a l of the smaller s i z e d fonts. The  t h r e e f o n t s shown i n F i g u r e 17, were s e l e c t e d bacause t h e y c o v e r  t h e range o f p r i n t s t y l e s , e x c l u d i n g i t a l i c  and s c r i p t , f r o m the most  s t y l i z e d HA, t h r o u g h a m o d e r a t e l y s t y l i z e d D, t o a b o l d and s e r i f l e s s G. The  h e i g h t o f t h e t a l l and s m a l l l e t t e r s i s a p p r o x i m a t e l y t h e same  for  the three fonts although,  the w i d t h s v a r y .  The t e s t m a t e r i a l  i n c l u d e d a l l upper- and l o w e r - c a s e c h a r a c t e r s .  Carbon r i b b o n was  used f o r a l l t y p i n g .  Hermes Ambassador, pitch 10 ABO-DE-PGHIJKLMNOPQRST. UVWXTZ a b c d e f g h i j k l m n o p q r s t u v w x y z  IBM A a  Delegate,  p i t c h  10  B C D E F G H I J K L M N b c d e f g h i j k l m  O n  P o  Q R S T U V W X Y p q r s t u v w x  Z y  z  IBM G o t h i c , p i t c h 12 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z  Fig.  17 The t h r e e f o n t s u s e d ; i n  the t e s t s , reproduced i n f u l l  size.  25  3.2  T e s t s and R e s u l t s The  manner. a row.  w i t h Repeated L e t t e r s  t y p e w r i t t e n m a t e r i a l was  Each upper and  lower case c h a r a c t e r was  A f t e r s c a n n i n g one row,  out on the TTY.  p r e s e n t e d i n the f o l l o w i n g  T e s t i n g was  t a b l e on a l l t h r e e f o n t s .  t y p e d 10 t i m e s i n  the r e c o g n i t i o n r e s u l t s were p r i n t e d  p e r f o r m e d f i r s t w i t h the HA  Then t h e system was  look-up  t r a i n e d on each o f  D and G f o n t s , i n d i v i d u a l l o o k - u p t a b l e s were d e v e l o p e d , and were r e p e a t e d on the newly t r a i n e d f o n t s . a d j u s t e d o n l y once a t the b e g i n n i n g  The  the  the t e s t s  l i g h t i n g i n t e n s i t y was  of each f o n t ' s t e s t f o r maximum  resolution.  The  f o l l o w i n g r e s u l t s were o b t a i n e d  from t h e s e t e s t s :  font  HA  D  untrained  —  66.8  68.9  trained  88.2  85.2  89.0  Over 65% o f the HA  l o o k - u p t a b l e was  t o the o t h e r f o n t s w i t h o u t t r a i n i n g . accuracies.  G  g e n e r a l enough t o be  applicable  A l l three fonts achieved s i m i l a r  S i n c e t h e t r a i n i n g p r o c e d u r e was  s i m p l e and  accomplished  q u i c k l y , the system demonstrated good m u l t i f o n t a d a p t a b i l i t y . matrices  have been t a b u l a t e d f o r the t e s t r e s u l t s and  Confusion  are i n c l u d e d i n  Appendix A.  3.3.  T e s t s and R e s u l t s w i t h T y p e w r i t t e n T h i s t e s t was  Passages  p e r f o r m e d t o d e t e r m i n e the r e c o g n i t i o n c a p a b i l i t y  o f the system on m u l t i c h a r a c t e r t e x t under more r e a l i s t i c t h a n i n S e c t i o n 3.2.  A passage f r o m a magazine a r t i c l e was  e x c l u s i v e of p u n c t u a t i o n ,  w i t h the t h r e e f o n t s .  w i t h t h e t r a i n e d look-up t a b l e s f o r each f o n t . t r a i n e d b e f o r e h a n d on t h i s passage. the scanner was  The  The The  conditions typed,  t e s t s were p e r f o r m e d system was  not  r e s o l u t i o n ( i l l u m i n a t i o n ) of  a d j u s t e d o n l y once a t the b e g i n n i n g  o f each f o n t ' s  text.  C h a r a c t e r i d e n t i f i c a t i o n s were p r i n t e d on t h e TTY a t t h e end o f  each l i n e . The r e c o g n i t i o n r e s u l t s f o r a t y p e w r i t t e n p a s s a g e w h i c h c o n t a i n e d 293 c h a r a c t e r s ,  a r e g i v e n below :  font  HA  results  D  89.9%  89.1%  G 87.7%  The passages as r e c o g n i z e d by t h e system a r e i n c l u d e d i n Appendix A.  In t h i s t e s t m a t e r i a l characters  s e g m e n t a t i o n scheme [5] was 3.4  r a r e l y touched and no  implemented.  Sources o f E r r o r I n t h i s s e c t i o n t h e m a j o r c o n t r i b u t o r s t o the e r r o r a r e  identified.  T y p i c a l e r r o r s a r e I l l u s t r a t e d i n Appendix D. From t h e  c o n f u s i o n m a t r i c i e s w h i c h were t a b u l a t e d have been c a t e g o r i z e d  f o r HA  (Appendix A ) , t h e e r r o r s  as f o l l o w s :  m i s i n t e r p r e t a t i o n of a closure  25.4%  m i s c l a s s i f i e d features  23.8%  missing a diagonal  ( b l o t t e d or broken characters)  character  15.9%  indiscriminate serif deletion  12.7%  c o n f u s i o n among s i m i l a r c h a r a c t e r s  11.1%  i m p r o p e r subgroup assignment  11.1%  A s i g n i f i c a n t s o u r c e of e r r o r was due t o m i s i n t e r p r e t a t i o n of a c l o s u r e as a minor v e r t i c a l and v i c e v e r s a .  A closure  required  c e r t a i n c o n s t r a i n t s ( S e c t i o n 2.4.2) t o be s a t i s f i e d , b u t t h e s e measurements p r o v e d t o be i n c o m p l e t e and a r e f o r m u l a t i o n o f t h e c l o s u r e c r i t e r i a i s s u g g e s t e d ( S e c t i o n 4.2).  27  A broken; s t r i n g d e s c r i b i n g a m i n o r v e r t i c a l o r a c l o s u r e i n an e r r o r .  A b r e a k i n a f u l l v e r t i c a l c o u l d be checked f o r and  c o r r e c t e d by c o u n t i n g  t h e number o f b l a c k c e l l s i n a column and, i f t h e  t a l l y exceeded t h e h e i g h t was a s s i g n e d .  r e q u i r e m e n t f o r a f u l l v e r t i c a l , t h e n one  However, w i t h m i n o r v e r t i c a l s and c l o s u r e s no s u c h  c r i t e r i o n e x i s t e d t o d e t e c t a b r e a k and t h u s an e r r o r r e s u l t s . features  resulted  i n a character  also resulted i n error.  Blotted  F o r example, a b l o t t e d  a r e a c a n change a s h o r t s t r i n g i n t o a l o n g e r one, t h u s w r o n g l y c h a n g i n g its  i d e n t i t y from a CC t o a V. The p e r f o r m a n c e o f t h e r o u t i n e t h a t checked f o r d i a g o n a l  c h a r a c t e r s was t r o u b l e s o m e .  The p r o b l e m was t h a t t h e programming  was i n e f f i c i e n t t o d e a l w i t h a l l t h e v a r i a t i o n s e n c o u n t e r e d i n f o l l o w i n g the i n c r e m e n t a l  changes a l o n g an edge.  C e r t a i n groups o f c h a r a c t e r s  were d i f f i c u l t t o d i s t i n g u i s h .  For example, t h e l e t t e r s 'V' and 'Y' were d i f f i c u l t t o s e p a r a t e . These m i s c l a s s i f i c a t i o n e r r o r s were c o n f i n e d characters  t o one o r two s i m i l a r  and u s u a l l y o c c u r r e d w i t h i n t h e same subgroup.  m i s c l a s s i f i c a t i o n was c o n f i n e d  t o p o s s i b l y one o f t h r e e  Thus characters  r a t h e r t h a n one i n f i f t y - t w o . The s e r i f d e l e t i o n r o u t i n e , b e s i d e s r e d u c i n g  the v a r i a b i l i t y  of t h e i n f o r m a t i o n , was sometimes i n d i s c r i m i n a n t l y a p p l i e d . when s e r i f s a r e e l i m i n a t e d  F o r example,  from t h e l e t t e r s '1' and ' I ' i d e n t i c a l  r e s u l t s are obtained. A n o t h e r t y p e o f e r r o r was i m p r o p e r subgroup a s s i g n m e n t .  In  the case o f s u c h l e t t e r s a s ' J ' and 'U', t h e h e i g h t c r i t e r i o n f o r a f u l l v e r t i c a l was o c c a s i o n a l l y m i s s e d because o f t h e r o u n d i n g o n t h e v e r t i c a l s ' bottoms, wrong subgroup.  thus  c o n f i n i n g t h e code-word  search to the  28  3.5  T r a i n i n g Procedure A s i m p l e t r a i n i n g p r o c e d u r e was  i d e n t i c a l c h a r a c t e r s was  scanned.  The  used.  A row o f  ten  o p e r a t o r then o b s e r v e d  computer d i s p l a y s f o r each c h a r a c t e r , w h i c h were s i m i l a r t o  the those  i n Appendix B, and noted the most common f e a t u r e m a t r i x r e p r e s e n t a t i o n s . The new  look-up  t a b l e f o r e i t h e r D o r G was  developed  t a b l e by s i m p l e a l t e r a t i o n of the e x i s t i n g code-words.  f r o m the  HA  I n most  cases  n o t a l l t h r e e code-words f o r a c h a r a c t e r r e q u i r e d m o d i f i c a t i o n .  Rather,  one o r two code-words were i n need o f m o d i f i c a t i o n and, u s u a l l y o n l y p a r t o f the code-word. 'C  For example, w i t h the c h a r a c t e r s 'C  code-words  for  the  to closure-cap  two r e m a i n i n g  The system r e q u i r e d a p p r o x i m a t e l y  t r a i n e d to a new  font.  letter  4 h o u r s t o be  Speed Ihe speed o f c h a r a c t e r r e c o g n i t i o n was  to 668 ms.  T h i s r e s e a r c h was  such a way  i n the range o f 376  e x p l o r a t o r y and, as s u c h , no  was made t o o p t i m i z e the programming.  attempt  The programme was w r i t t e n i n important.  performed on the d a t a a t a time and,  of e f f o r t e x i s t s . by a p p r o x i m a t e l y  Thus o n l y one  operation  as a r e s u l t , much d u p l i c a t i o n  The speed o f the p r e s e n t system can be i n c r e a s e d 150 ms.  using  more e f f i c i e n t programming  For a p r a c t i c a l system, the s e p a r a t e r o u t i n e s can be together.  ms.  t h a t each s t e p o f p r o c e s s i n g c o u l d be r e a d i l y f o l l o w e d ;  as w e l l , the ease of m o d i f i c a t i o n was was  ( f e a t u r e code 56)  feature levels i n this  were i d e n t i c a l .  3.6  and  ( G ) , o n l y the code-word f o r the top l e v e l needed t o be changed from  c l o s u r e - c a p - v e r t i c a l ( f e a t u r e code 564) The  (HA)  techniques. incorporated  F o r i n s t a n c e , s t r i n g i d e n t i f i c a t i o n need o c c u r o n l y one  ahead o f b a s i c f e a t u r e a s s i g n m e n t , w h i c h i n t u r n s h o u l d be o n l y column ahead o f the f e a t u r e i n t e g r a t i o n p r o c e s s .  column  one  T h i s type of s y s t e m  c o n f i g u r a t i o n s h o u l d be a b l e t o a c h i e v e a r e a d i n g r a t e o f 10  char/sec.  29  3.7  System S t o r a g e Requirements T h i s OCR system was a l l o c a t e d 8 K o f memory on t h e PDP-12  computer.  The r e c o g n i t i o n programme i t s e l f r e q u i r e d o n l y 4K o f memory.  The second 4K was o c c u p i e d by t h e I/O and d i s p l a y r o u t i n e s a s w e l l a s the s t o r a g e o f a l l t h e p r o c e s s e d i n f o r m a t i o n .  The programming was  w r i t t e n i n PDP-8 language and t h e r e f o r e t h e system c a n be implemented on a PDP-8 m i n i c o m p u t e r . A p p r o x i m a t e l y 100 code-word look-up t a b l e o f a p a r t i c u l a r f o n t .  e n t r i e s were n e c e s s a r y f o r t h e About 40% o f t h e s e code-words  were unique e n t r i e s ; o r , 60% o f t h e code-words were s h a r e d by -two o r more c h a r a c t e r s . 3.8  System  Flexibility  The a b i l i t y o f t h i s system t o accomodate poor image q u a l i t y , d i s t o r t i o n , and complex shapes was h i g h l y s a t i s f a c t o r y . The system's f l e x i b i l i t y i s i l l u s t r a t e d i n A p p e n d i x D. a b l o t t e d p r i n t i n g c o u l d be accomodated.  A break i n a character o r I f damage was l o c a l i z e d ,  then  o n l v one code-word was a f f e c t e d and, t h e o t h e r two c o u l d s t i l l be used f o r i d e n t i f i c a t i o n . E l o n g a t i o n and c o m p r e s s i o n o f a c h a r a c t e r was t o l e r a t e d by t h e system.  T h i s type of rubber-sheet d i s t o r t i o n of a  p l a n e i s known as a t o p o l o g i c a l mapping [7] and e s t a b l i s h e s t h e s t r o n g l y t o p o l o g i c a l ; n a t u r e o f t h i s scheme.  The system's a b i l i t y t o h a n d l e  c a r e f u l l y h a n d p r i n t e d c h a r a c t e r s was n o t e d .  The scheme was a l s o a b l e  t o r e s o l v e complex shapes i n t o more s i m p l i f i e d  structures.  30 IV.  4.1  CONCLUSION  Summary T h i s t h e s i s has d e v e l o p e d an OCR  system w i t h a p o t e n t i a l  a p p l i c a t i o n t o a p e r s o n a l r e a d i n g machine f o r the b l i n d .  A topological  f e a t u r e e x t r a c t i o n t e c h n i q u e b a s e d on l i n e and shape d e s c r i p t o r s implemented.  A v e r t i c a l p h o t o c e l l a r r a y , scanning  used t o o b t a i n a b i n a r y image.  A continuous  a t 60 wpm,  was  was  s t r i n g of black c e l l s  c h a r a c t e r i z e d by one o f t h r e e p o s s i b i l i t i e s : a s i n g l e p o i n t t o  was  represent  the c e n t r e c e l l o f a s h o r t s t r i n g ; a v e r t i c a l o f a p p r o p r i a t e l e n g t h t o c h a r a c t e r i z e a l o n g s t r i n g ; and,  an a r e a o f c l o s u r e t o d e f i n e  convergence o r d i v e r g e n c e o f two b r a n c h e s w i t h i n a l e t t e r . r e s o l u t i o n o f column d a t a was  adopted and each column was  i t s next neighbour to generate continuous Feature  the  A four l e v e l compared t o  f e a t u r e s a c r o s s t h e columns.  enhancement, such as s e r i f d e l e t i o n and v e r t i c a l c o m p r e s s i o n  t o t h r e e l e v e l s , was  implemented.  A transition table integrated  h o r i z o n t a l f e a t u r e s a l o n g the t h r e e f e a t u r e l e v e l s . c o m p r e s s i o n , a c h a r a c t e r ' s shape was  After horizontal  d e s c r i b e d by any  combination  of  seven b a s i c f e a t u r e s , u s u a l l y w i t h i n a 3 x 3 f e a t u r e m a t r i x . Each o f the t h r e e h o r i z o n t a l l e v e l s was The  a s s i g n e d a code-word.  c l a s s i f i e r c o n f i n e d the unknown c h a r a c t e r i n t o a subgroup  o f the a l p h a b e t ;  t h i s was  based on t h e c h a r a c t e r ' s h e i g h t and  of f u l l l e n g t h v e r t i c a l s which i t contained. when a u n i q u e code-word i n the l e t t e r was  the number  I d e n t i f i c a t i o n was  made  e n c o u n t e r e d ; o r , i f the code-  words were a l l common w i t h i n the subgroup, t h e n t h e r e c o g n i t i o n  was  on the b a s i s o f t h e c h a r a c t e r w i t h t h e maximum number o f code-word matches.  A s p e c i a l t e c h n i q u e was  developed to i d e n t i f y characters w i t h  p r o m i n e n t d i a g o n a l f e a t u r e s ; the t r a n s i t i o n o f an edge a l o n g a  specific  s i d e o f a c h a r a c t e r was  Sequential  c l a s s i f i c a t i o n was  used f o r t h i s subgroup's r e c o g n i t i o n .  employed t h r o u g h o u t t h e s y s t e m so t h a t i d e n t i f i c a t i o n  was made once a s u f f i c i e n t l y u n i q u e measure was  satisfied.  31  The system was t e s t e d on upper- and l o w e r - c a s e c h a r a c t e r s o f t h r e e d i f f e r e n t t y p e w r i t e r f o n t s w h i c h v a r i e d from a s t y l i z e d to a s e r i f l e s s p r i n t .  Results i n d i c a t e d that the l e v e l of r e c o g n i t i o n  a c h i e v e d was a p p r o x i m a t e l y c h a r a c t e r s p e r second.  87% a c c u r a c y f o r a r e c o g n i t i o n speed o f two  The t r a i n i n g of t h e system t o a new f o n t  was  a s i m p l e p r o c e d u r e t h a t r e q u i r e d about f o u r h o u r s of e f f o r t . A p p r o x i m a t e l y 100 code-word  e n t r i e s were s t o r e d i n t h e l o o k - u p t a b l e .  An OCR method has been p r o p o s e d w h i c h uses shape d e s c r i p t o r s w h i c h i n a sense p a r a l l e l d e s c r i p t i o n s t h a t a man would u s e . which w i l l  l e a v e the l e t t e r ' s i d e n t i t y u n a l t e r e d t o man  be used by the machine. of t h i s approach.  Transformations  should l i k e w i s e  The p i l o t s t u d i e s i n d i c a t e s e v e r a l advantages  Rubber-sheet changes o f s c a l e produce i n v a r i a b l e r e s u l t s .  B r e a k s i n c h a r a c t e r s produced l o c a l i z e d u n c e r t a i n t y w h i c h i n most Instances  allowed  the c h a r a c t e r t o be c o r r e c t l y i d e n t i f i e d .  The  p r e s e n c e o r absence o f s t y l i z a t i o n , such as s e r i f s , i n t h e f o n t seem t o have l i t t l e e f f e c t on i d e n t i f i c a t i o n .  A few c a r e f u l l y drawn, hand-  p r i n t e d c h a r a c t e r s were t r i e d w i t h t h e OCR and were c o r r e c t l y i d e n t i f i e d .  4.2  Recommendations f o r F u r t h e r  Research  The d e t e c t i o n of a c l o s u r e as s t a t e d i n S e c t i o n 2.4.2  i s weak.  R e f e r r i n g t o F i g u r e 18, a more r i g o r o u s r e f o r m u l a t i o n o f the c l o s u r e c r i t e r i a i s now p r e s e n t e d :  1.  t h e column (B) a t w h i c h t h e c l o s u r e  o c c u r s must have two s t r i n g s i n the a d j a c e n t l o c a t e d a t i t s e x t r e m i t i e s ; 2.  column  (C), that are  t o be c e r t a i n o f t h e i d e n t i t y o f the  two s t r i n g s as a c t u a l l y two b r a n c h e s t h a t converge t o form t h e c l o s u r e , the n e x t column  (D) o v e r from t h e s e two s t r i n g s must be checked f o r  t h e i r c o n t i n u a t i o n ; 3. the column (A) p r e c e e d i n g  the c l o s u r e  should  be s m a l l e r t h a n the c l o s u r e s t r i n g t o i n d i c a t e e x p a n s i o n towards the closure. letters  Such a new c r i t e r i a can c o r r e c t t h e c l o s u r e e r r o r s i n t h e 'e, C, U' i n Appendix  C.  The c l a s s i f i e r i s u n d e r d e v e l o p e d . the f e a t u r e m a t r i c e s  F o r example i n Appendix C  f o r b o t h 'P' and '0' a r e good c h a r a c t e r d e s c r i p t i o n s  d e s p i t e the m i s c l a s s i f i c a t i o n s .  The e r r o r s were c o n f i n e d t o o n l y  one  column; however, i n t h e h o r i z o n t a l d i r e c t i o n s e v e r a l rows were a f f e c t e d .  Thus more t h a n one code-word was a l t e r e d by t h e same e r r o r .  We  suggest  t h a t t h r e e code-words f o r t h e v e r t i c a l d i r e c t i o n i n a d d i t i o n t o the t h r e e code-words f o r the h o r i z o n t a l d i r e c t i o n w i l l produce a more powerful c l a s s i f i e r .  This w i l l double the s i z e of the present  t a b l e t o about 200 e n t r i e s , b u t t h i s i s s t i l l a modest s i z e . improvement t o the system for  is  anticipated  look-up An  because the s i x code-words  each c h a r a c t e r w i l l r e s u l t i n a b e t t e r d i s t i n c t i o n among c h a r a c t e r s ,  d o u b l e the p o s s i b i l i t i e s f o r u n i q u e code-words, degree o f e r r o r t o l e r a n c e . the l e t t e r s  and i n t r o d u c e a h i g h  Such a c l a s s i f i e r w i l l be a b l e t o r e c o g n i z e  'P' and '0' i n Appendix C from t h e i r v e r t i c a l  code-words.  From t h e d i s c u s s i o n on e r r o r s ( S e c t i o n 3.7), i t was  noted  t h a t t h e r e e x i s t s m a l l s e t s o f c h a r a c t e r s w h i c h the b a s i c system f i n d s some d i f f i c u l t y i n s e p a r a t i n g .  An advanced system w i l l have t o  i n c l u d e a s m a l l number o f s o r t i n g r o u t i n e s whenever t h e s e l a t e n t ambiguities are encountered. The r o u t i n e t h a t checks f o r d i a g o n a l c h a r a c t e r s has t o be improved.  S p e c i f i c a l l y , t h e . a b i l i t y t o accomodate l o c a l i z e d  distortions  when f o l l o w i n g an edge must be i n c o r p o r a t e d i n t o t h e programming.  D  A B C D  B ooo oooooo ooo ooo oo ,loo ooo 'oo ooo oo ooo oo ooo oo oo ooo ooo ooo oo oo oo oo oo oo oo ooo oo oo ooo ooooooooo oooooo 0 0  Fig.  18  A-B  m i o o o  B-C  C-D  a > b  b >  c+1  e < f  b < i-1  g < h-1  f >  k+1  i  f <  g-1  It  Suggested c l o s u r e c r i t e r i a t o r e p l a c e t h e c r i t e r i a i n F i g u r e 3.  c >  7*  d+1 m  33  REFERENCES [I]  S.K. A b d a l i , " 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 * , P a t t e r n R e c o g n i t i o n , 3, pp. 3-23, A p r i l , 1971.  [2]  H.C. Andrews, M a t h e m a t i c a l Y o r k : W i l e y , 1972.  [3]  M.P. Beddoes, "An I n e x p e n s i v e R e a d i n g Instrument f o r t h e B l i n d " , IEEE T r a n s . Bio-Med. Eng., V o l . BME-15, pp. 70-79, A p r i l , 1968.  [4]  J.C. B l i s s , "A R e l a t i v e l y H i g h - R e s o l u t i o n R e a d i n g A i d f o r t h e B l i n d " , IEEE T r a n s . Man-Mach. S y s t . , V o l . MMS-10, pp. 1-9, March, 1969.  [5]  C l a y d e n e t a l . , " L e t t e r R e c o g n i t i o n and the S e g m e n t a t i o n o f Running T e x t " , I n f o r m a t i o n and C o n t r o l , 9, pp. 246-264, 1966.  [6]  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 p l i c a t i o n s " , Ph.D. t h e s i s , M.I.T., September, 1965.  [7]  R.O. Duda and P.E. H a r t , P a t t e r n R e c o g n i t i o n and Scene A n a l y s i s , pp. 327-378. New Y o r k : W i l e y , 1973.  [8]  M. Eden, "The A p p l i c a t i o n o f C 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 t o the Development o f r e a d i n g machines f o r the B l i n d " , Image P r o c e s s i n g i n B i o l o g i c a l S c i e n c e , ed. D.M. Ramsey, U.C.L.A. P r e s s , pp. 35-56, 1968.  [9]  M. Eden and M. H a l l e , " C h a r a c t e r i z a t i o n o f C u r s i v e H a n d w r i t i n g " , P r o c . 4 t h London Symp. Inform. Theory , C. Chery e d . , London: Butterworths, I96T7 ~  1  [10] K.S. ing.  Techniques i n P a t t e r n R e c o g n i t i o n ,  New  Ap-  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 New Y o r k : Academic P r e s s , 1968.  [ I I ] K. Fukunaga, I n t r o d u c t i o n t o 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 t i o n . Y o r k : Academic P r e s s , 1972. [12] H. G e n c h i e t a l . , " R e c o g n i t i o n o f H a n d w r i t t e n N u m e r i c a l f o r A u t o m a t i c L e t t e r S o r t i n g " , P r o c . I E E E , V o l . 56, no. 1301, A u g u s t , 1968.  New  Characters 8, pp. 1292-  [13] F. Lee, "A R e a d i n g Machine: From T e x t t o Speech", IEEE T r a n s . A u d i o and E l e c t r o a c o u s t i c s , v o l . 17, no. 4, pp. 275-282, December, 1969. [14] 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 . IEEE, v o l . 57, no. 8, pp. 1391-1407, A u g u s t , 1969. [15] H. Marko, "A B i o l o g i c a l Approach t o P a t t e r n R e c o g n i t i o n " , IEEE T r a n s . Systems, Man, and C y b e r n e t i c s , v o l . SMC-4, no. 1, pp. 34-39, J a n u a r y , 1974.  34  [16]  S . J . Mason and J . K i 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 Reading 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 , e d s . P.A. K o l e r s and M. Eden, M.I.T. P r e s s . Cambridge, Mass., pp. 156167, May,1968.  [17]  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 . v o l . 56, pp. 836-862, May, 1968.  [18]  P.W. Nye and J.C. B l i s s , "Sensory A i d s f o r t h e B l i n d : A C h a l l e n g i n g P r o b l e m w i t h Lessons f o r t h e F u t u r e " , P r o c . IEEE, v o l . 58, no. 12, pp. 1878-1898, December, 1970.  [19]  A. R o s e n f e l d , " F i g u r e E x t r a c t i o n " , A u t o m a t i c I n t e r p r e t a t i o n and C l a s s i f i c a t i o n o f Images,' ed. A. G r o s s e l l i , Academic P r e s s , New Y o r k , pp. 137-153, 1969.  [20]  G.C. Smith and H.A. Mauch, "Summary R e p o r t on t h e Development o f a R e a d i n g Machine f o r the B l i n d " , B u l l . P r o s t h e t i c s Res., v o l . BPR 10-12, pp. 243-271, F a l l , 1969.  [21]  J.T. Tou, " F i g u r e E x t r a c t i o n i n P a t t e r n R e c o g n i t i o n " , P a t t e r n Reco g n i t i o n , v o l . 1, pp. 3-11, J u l y , 1968.  [22]  J.T. Tou and R.C. G o n z a l e z , " 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 T o p o l o g i c a l F e a t u r e E x t r a c t i o n and M u l t i l e v e l C a t e g o r i z a t i o n " . IEEE Trans. Computers, v o l . C-21, pp. 776-785, J u l y ; 1972.  [23]  G. T o u r l a k i s and J . M y l o p o u l o s , "Some R e s u l t s i n C o m p u t a t i o n a l Topology", J . ACM 30, 3, pp. 439-455, J u l y , 1973.  [24]  E.E. T r i e n d l , " S k e l e t o n i z a t i o n o f N o i s y Handdrawn Symbols U s i n g P a r a l l e l O p e r a t i o n s " , P a t t e r n R e c o g n i t i o n , v o l . 2, pp. 215-226, 1970.  IEEE,  35  APPENDIX A Confusion  Matrices The  f i r s t t h r e e pages c o n t a i n t h e c o n f u s i o n m a t r i c e s  t a b u l a t e d from t e s t s w i t h r e p e a t e d c h a r a c t e r s constant  under the c o n d i t i o n s  i l l u m i n a t i o n and t r a i n e d l o o k - u p t a b l e s f o r each f o n t .  f i g u r e i s the l o w e r case r e s u l t s and The  q u e s t i o n mark ( ? ) , w h i c h i s one 'X' r e p r e s e n t s  of  The  top  the b o t t o m i s f o r t h e upper c a s e . of t h e p o s s i b i l i t i e s o f  identifica-  t i o n , i n d i c a t e s t h a t no code-word matches were found f o r t h i s An  t h a t were  complete r e c o g n i t i o n ( 1 0 / 1 0 ) .  A s l a s h (/)  character. through a  number i n d i c a t e s t h a t , i f t h i s i s the l o w e r - c a s e m a t r i x , t h e n the  confu-  s i o n i s w i t h the u p p e r - c a s e c h a r a c t e r , and v i c e v e r s a . The  r e c o g n i t i o n r e s u l t s f o r the t y p e w r i t t e n passages a r e i n -  c l u d e d on the f o u r t h page of t h i s a p p e n d i x . above each e r r o r .  An a s t e r i s k (*)  i s located  a b c d e f g h i  a X b 9 c X d X e X c  X  g  h i J k a El  X 8 1 XI X  2 2  7  1  8 9  n 1 o P <J r  i  6  1  t  7'  X y 2 1  1 3  1  ? X  lx  1  8 X  la  U V  w  I  1 X  X  X 1  T?  y Z ?  I  1  X  2  Identification j k 1 m n o. P q r s t u V  R 7  9  8 1  • Identification F G H I J K L M N 0 P Q R S T u V w X T z  A B C D U >j B X C 8 2 D 9 1 E X F 2 7 1 G 8 2 H 8 2 I 2 7 1 J 1 9 K 1 9 L 2 8 M 71 2 N K 0 X P 8 1 1 7 Q 1 R 1 1 8 1 S X T 7 3 U 7 1 ?, V X W X X ? 8 Tf 1 9 Z 1 7?  *\  C o n f u s i o n m a t r i c e s f o r Hermes Ambassador f o n t , on w h i c h t h e system developed.  was  Identification a b c d e f B h i j k 1 T.1 n o P q r s t u V w X y z ? a 7 2 1 b 9 1 c 9 1 d 1 9 e 1 8 1 f X 8 g h 1 9 i X j k 1 1 9 1 3 7 tn 3 1 1 n 1 9 o X 1 P 9 q X r X s 1 2 7 t 8 1 1 u X V X w X 1 9 y  z L  6  1  1  B  • Identification • 1  B  C  A B c D E F G K I J K L M N 0 P Q R S T U V W X Y Z ? i  8  D  J K L M N 0 P Q R S T TJ  •  i  i  "  X  I  •  I  X 7 2 8  F G I  i  ?  E H  i  9  J,  1  2 9  4  t  8  t  1  1  9  I  6  2  91 X 1  1  9 1  ?  j  7  3 7  9 9  V W X Y Z  C o n f u s i o n m a t r i c e s f o r IBM D e l e g a t e  1  X X 6  9  1  4 7  font  (trained).  i  Identification a b e d e f g h i j k l m n o p q r s t u v w x y z ? 1 a 8 1 1 b X 1 c 9 1 1 d 8 1 2 e xi — — f X X g h X i ix X J k 2 8 1 be ra 8 2 1 n 9 o P q r  28  2  s  1  9  9  t 7  1 5  t u V w X  X  1 X X  X  X  y z  X  X  Identification A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ? 9 1  8  1 1 9  9  8-  8  8  X  ? X 7 2 9  to  V H  1  1  1 1  be  1 9  2  1  8  1  1 1 8  X 91 6  4  1 9  %  8  8  X 7  C o n f u s i o n m a t r i c e s f o r IBM G o t h i c f o n t  (trained).  2 X  9  3  1  X  A f t e r o u r documentary The F i f t h E s t a t e was a i r e d by t h e CIO K e v i n O N e i l l who was r e v e a l e d  a s d i r e c t o r o f Canadas l a r g e s t  i n t e l l i g e n c e agency t h e Communications B r a n c h o f t h e N a t i c i i a l R e s e a r c h C o u n c i l CBNRC was a s k e d by a newspaper r e p o r t e r vho i t was t h a t he r e p o r t s t o O N e i l l t o l d  him t h a t he had s p e r i ;  most o f t h e m o r n i n g t r y i n g t o d e t e r m i n e j u s t  that  A f t e r o u r documentary The F i f t h E s t a t e was a i r e d by t h e CIC Kevin  O N e i l l who was r e v e a l e d  as d i r e c t o r o f Canadas l a r g e s t  i n t e l l i g e n c e agency t h e Communications B r a n c h o f t h e N a t i c n a l Research C o u n c i l  CBNRC was a s k e d by a newspaper r e p o r t e r vho  i t was t h a t he r e p o r t s  to ONeill told  most o f t h e m o r n i n g t r y i n g  After  o u r documentary The F i f t h  Kevin  ONeill  intelligence Research it  most  who w a s r e v e a l e d  Estate  was a i r e d b y t h e CBC  as d i r e c t o r o f Canadas  CBNRC w a s a s k e d b y a n e w s p a p e r  he r e p o r t s  to ONeill  told  him t h a t  o f t h emorning t r y i n g t o determine j u s t  Reading  results  from  and  Gothic  fonts.  IBM  that  largest  agency t h e Communications Branch o f t h e N a t l o r a l  Council  was t h a t  him t h a t he had s p e r t  t o determine j u s t  a  continuous  r e p o r t e r wfo he h a d s p e n t  that  passage.  Top  * * * « A f t e r our documeatary The F i f t b Estute was a i c e d by the CBC * ft* * * * * K e v i u O N e i l l who wnu r e v e a l e d au J i r e c t o r o f Oanadas l a c g e s t * ft* ft * i u t e l l i g e n c e uKency the Comraunicationc Bracch o f t h e . N a t i o n a l ft ft ft ft ft ft Feuearch C o u n c i l OBMC was usbed by a newspaper r e p o r t e r t-jho ft* ft ft i t wuu thut he r e p o r t u to O N e i l l t o l d him that he had spent ft ft * mout o f the morning t r y i u g t u determine j u s t t h a t  ft ft ft ft ft ft A f t e r our documentar? Lhe L i f t h Estate wax a i r e d bV tbe CBC * * * ft * * ft K a v i n O N e i l l who w?s r e v e ? l e J es d i r e c t o c of Canadax l a r g e s t ft ft ft ft ft ft i n t e l l i ? e n c e a?enc? the Communications Br?nch o f the N a t l o ? a l * * * * Research C o u n c i l CBNKC was axked b? a newspaper -reporter who ft ft ft i t was t h c t he r e p o r t s to O N e i l l t o l d aim that he had xpent ft* ft * * ft m o s t of tAe morninq t r ? i n g to betermine j u s t t h a t  ft ft ft ft * A f t e r our decunentary The F i f t h Estate was aiwed ?y the CBF ft ft ft * Kevlw O N e i l l who was r e v e a l e d av d i r e c t o r o f Cawahas l a r g e s t ft ft * * ** * i a t e l l i g e a c e egency the Comnunicatioax Braach of the N a t i o n a l * ft ft ft ft ftft ft ft * ft Pexearch C o u n s i l CBNPC ras axbed by a newspepar r e p o r t e r w?o * * * f t * i t wes thab he reporfs bo O N e i l l bold him t h a t he had spent ft ft * ft movt o f the norning t r y j n g to determire j u s t t h a t  bottom:  Hermes  Ambassador,  IBM  Delegate,  40  APPENDIX B Examples o f the C h a r a c t e r ' R e c o g n i t i o n The numbered statements  Process  r e f e r t o a r e a s w i t h i n each p i c t u r e ,  as  i l l u s t r a t e d i n the f i g u r e a t the b o t t o m o f the page. 1.  i n p u t t o the system from the p h o t o c e l l scanner.  2.  the p o i n t s r e p r e s e n t the c e n t r e c e l l s o f the s h o r t  3.  the p o i n t s r e p r e s e n t v e r t i c a l s and c l o s u r e s and a r e l o c a t e d d i r e c t l y above the column t o w h i c h they  4.  strings.  belong.  the c h a r a c t e r i s q u a n t i z e d i n t o f o u r l e v e l s and each s t r i n g i s a s s i g n e d i t s appropriate feature.  5.  v e r t i c a l compression to three l e v e l s ; s e r i f d e l e t i o n .  6.  h o r i z o n t a l f e a t u r e i n t e g r a t i o n a l o n g each l e v e l .  7.  f i n a l f e a t u r e m a t r i x ; a code-word i s a s s i g n e d f o r each l e v e l .  8.  the t h r e e l e v e l s c o r r e s p o n d  t o t h e t h r e e code-words; markers i d e n t i f y  code-word matches. 9.  subgroup t o w h i c h the c l a s s i f i c a t i o n i s c o n f i n e d ; top and b o t t o m a r e a s r e p r e s e n t the l o w e r and.upper case c h a r a c t e r s , r e s p e c t i v e l y .  10.  a number above a c h a r a c t e r i n d i c a t e s the i d e n t i t y o f the unknown c h a r a c t e r ; t h e numbers one t h r o u g h  t h r e e s p e c i f y a t what f e a t u r e l e v e l  the i d e n t i f i c a t i o n i s made; a f o u r i n d i c a t e s t h a t the  identification  i s based on the c h a r a c t e r w i t h the most code-word matches.  u  1  3  2  7  6  5  4  \ .....  ....  -  —  -  X  41  i n x — N — l • • - x — l • • •xx—x• x x s x — - x — x x j —x  j .»" h !  m  RCCNDRSU:  J  :::::ti  .ill  |  X X X — — s s s l  XXX  N S S | •• •  xss-sx-xxxl•••  x<<<<<<<<ni<< x<<<<<<<<UI<<•  ii  iitHni  • • |XXXXX--s| ••  1I XXX—I ••••II • I  • ••  •VN-SX-XXXl••• XI N  2 BDPHLPm  ». . . . . . .  < • 1<<<<<<<<<<• <•i<<<<<<<ni<< • i <<<<<<<•i<• • i<<• i ni• •i•i •  <<<!<<<<<-!<• <x< << < < < < x | < • <x<<<<<<<UI < •  •I.II  • • | •x x x x — M •• • •Ix 1 • •  B  III x — s — I •• — x - x — I •• X X X S - - x - x x | -x  •:  ::  3  BDPHLPftT • • • •  • • • • • •  BDCPIVLPRl  <<<<<<<<<•1<<• xni • *UI •  • • •• • •• •  B  BDEFX7LPRT  RCENDR5UI  11XXX—I  •• • • j  I  <<<-<!<<<<x| <<<•<!<<<<<• <<<-!<<<-<<•  • •  <• 1 •  xxx-I-s BDPHLPU7 xsx-l - s - — . . . . j <<<•I<<<<<• <<<-l<<<<<<<<•I<<<<<U  RCCNDRSU: —x| • • I I• • ss-xxxx-Is-  BDCPI7LPR7  I<<<<<<<•I<• !<<<<<<<•K• I<<<<<<U<I<•  42  :: ii |l'  ,  |  /  /  /  X  K  BDFHLPH7 •  m  ,  | - \ /  /  /  /  X  X  <<•|<<<<<<<<X<X  2 B0CFI7LPRT  << • 1<<<<<<<<•<x << • 1<<<<<<<</<x  • • •  • 1 sx I X • 1/x  X / - X |  • •  I I II 1  X  |  X  s  — X / - X | j  I •  •X / * — / — x-xxxxx • BDFHLPH7  /  • X W S • X / / - /  |x  • X X X X  <<<<<-<I<<<<<<<<<•<!<<<<• <<<<<-!<<<<<-  BDCPI3LPRT . . . . • • • . . • . | ~ i —  S / - / / / X X ' X - X X X X X -  x|  S / - / / / X X -  <: x< <<<<<< <<<fl<x< <x<<<<<<<<<<< • <x <x<<<<<<<<<<U<x< xf)x  X- X  xux  - V | / X  • - S | / X -  . ..J  xxxx • • XX I XXX I••• • • • • K| X X  x/-/—s-sssslI xxsx——s—s-••• ssxx -  BOFHLP«7  — S S X X - • — XXXXX I •  N W - S - - / - / / X X  X X X X - - X - - X X X X X I X X X - X / - / / X X  • • • • K|XX-  <<•!<<<<<<<<-<*<<• <<•!<<<<<<-<<<<*<• <<•!<<<<<<<•<M<<<-  I  x/-/--x-xxxx| I  4 EFX7LPRT  x<<<<<<<<<<n<i x< <<<<<<<<<x<x !<<<<<<<<<<U<x  2 CGDUSZ • - aa • ••  ••B  43  APPENDIX C Examples o f ' E r r o r s Top L e f t ; because  The c l o s u r e on the r i g h t s i d e was missed f o r t h i s  the s t r i n g at which the two branches converged was too  Top R i g h t ;  short.  A broken c l o s u r e on the r i g h t s i d e r e s u l t e d i n m i s c l a s s i f i -  cation of t h i s Centre L e f t ; vergence  character  s t r i n g as a minor v e r t i c a l . The c l o s u r e on the r i g h t s i d e was m i s s i n g because  c r i t e r i o n was n o t s a t i s f i e d .  the lower b r a n c h ended b e f o r e  Specifically,  the l a s t  the s t r i n g p e r f o r m i n g the a c t u a l  case i n d i s c r i m i n e n t , c r i t e r i a p r e s e n t l y  Centre R i g h t :  closure.  f o r two b r a n c h e s .  detected  this  isfy  used.  A check f o r b r a n c h c o n t i n u i t y would have  error. The l o n g s t r i n g on the c h a r a c t e r ' s l e f t  the c r i t e r i o n f o r a f u l l v e r t i c a l .  v e r t i c a l was m i s s e d ,  Improper subgroup assignment  side  f a i l e d to  sat-  Any s t r i n g o t h e r than a f u l l  t i c a l o r a v e r y s h o r t s t r i n g was t e s t e d f o r c l o s u r e . the f u l l  and i n  The upper r i g h t c o r n e r was assumed t o be the p o i n t o f d i -  vergence  Bottom L e f t :  con-  string in  A more comprehensive t e s t f o r a c l o s u r e must r e p l a c e the r i g i d , this  the  the s t r i n g s a t i s f i e d  In t h i s  ver-  c a s e , when  the c l o s u r e c r i t e r i o n .  o c c u r r e d as a consequence  o f the l o s t  vert-  ical. Bottom R i g h t :  The f e a t u r e m a t r i x was ambiguous f o r t h i s  the d e l e t i o n o f the s e r i f s  r e s u l t e d i n a l o s s of features.  back to the c h a r a c t e r ' s s t r u c t u r e b e f o r e s e r i f d e l e t i o n , can be r e s o l v e d . all  For this  the code-words.  c h a r a c t e r , the system f i r s t  o r more e q u a l l y l i k e l y p o s s i b i l i t i e s letter  i n the s e r i e s .  c h a r a c t e r ' b ' was  the  because  By r e f e r r i n g ambiguity  s e a r c h e d through  When no unique e n t r i e s were f o u n d , a s e a r c h was i n -  i t i a t e d f o r the c h a r a c t e r w i t h the most f e a t u r e  first  letter  selected.  For t h i s  existed,  l e v e l matches.  When two  the programme chose  the  example, w i t h m u l t i l e c h o i c e s ,  the  44  •y I  MM'  •  I  •  -K|  • I ISS-S /-//KX' • • /////-S-WNN- K* I' MM | • I I W-S S-SSMM-  'I • ! «  < • <<<<<<<<<<<n<K< I <<<<<<<<<<<<• < < X  <<!<<<<<<<<<<u<*<  i i i I  — x - i 11 • 1111  :::  :  HCEN0RSU2  S S  s - lII •  \ "  :  I  I SS—--«'#'*»-•  l<<<<<<n<<i< I<<<<<<-<<<!  •:  I<<<<<<<<< u<  •! x • •x  • • •X S - S  • ••!x  • • • •X S - S  ! • I • /'-I •  Ix  I  x  • xssss s*\ I <x<<<<<<<<<n<x <x<<<<<<<<<<-x <x<<<<<<<<<U<I  4 BDFHLPH7  BDFHLPftT  I• •  .'-1  <<•<x<<<<<<<<• I <: <<•<x<<<<<<<<•|< <<<•x<<<<<<<<-!<  S - S S | K X  • X S S S S - - — • • I  "'hhiii'"  111 I  • s S S  Ix ix  <• l < < <•!<<• <•l<<-  45  APPENDIX D Examples o f System F l e x i b i l i t y Top L e f t ;  H i g h l i g h t i n g i n t e n s i t y produced a b r e a k a t t h e b o t t o m o f t h e  character.  Because t h e damage was l o c a l i z e d t o o n l y one l e v e l , i d e n t i -  f i c a t i o n was s t i l l p o s s i b l e w i t h t h e code words f r o m t h e two r e m a i n i n g feature l e v e l s . Top R i g h t :  Low l i g h t i n g i n t e n s i t y produced a b l o t t e d image.  l e v e l i n the feature matrix, although  The second  s t i l l p l a u s i b l e , was n o t c h a r a c -  t e r i s t i c o f t h i s l e t t e r under n o r m a l c o n d i t i o n s . Centre L e f t :  C o r r e c t c l a s s i f i c a t i o n r e s u l t e d when t h i s l e t t e r was com-  p r e s s e d by 1/3. Centre Right:  E l o n g a t i o n by 1/3 o f t h e same c h a r a c t e r produced s i m i l a r  r e s u l t s as above. Bottom L e f t : T h i s c a r e f u l l y h a n d p r i n t e d  c h a r a c t e r was c o r r e c t l y  identi-  fied. Bottom R i g h t :  Good f e a t u r e s i m p l i f i c a t i o n was o b t a i n e d on t h i s hand-  w r i t t e n c h a r a c t e r from t h e U k r a i n i a n  alphabet.  46  47  APPENDIX E B a s i c Flowchart f o r the Diagonal Checking  Routine  (eg.)  enter  (eg.) N  i s 1st b i t of information i n top 1/4 o f 1 s t column ?  1  tall letter ? N  i s 1st b i t o f information i n b o t t o m 3/4 of 1 s t column ?  N  check t o p edge  check bottom edge DU ?  UD ?  »v,V  -s>A  DUDU ?—»w,W $Jcheck l e f t and r i g h t edges k. V-VUD ?•  ->k  V-UD ? DU-U ? DV-UV ?•  -5>Y  DU-UD ?  -»x,X  T  exit  Notation: vertical  JJ^down  OR  V-UD  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items