UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Design and construction of an opaque optical contour tracer for character recognition research 1967

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
UBC_1968_A7 A88.pdf
UBC_1968_A7 A88.pdf [ 6.01MB ]
Metadata
JSON: 1.0104301.json
JSON-LD: 1.0104301+ld.json
RDF/XML (Pretty): 1.0104301.xml
RDF/JSON: 1.0104301+rdf.json
Turtle: 1.0104301+rdf-turtle.txt
N-Triples: 1.0104301+rdf-ntriples.txt
Citation
1.0104301.ris

Full Text

DESIGN AND CONSTRUCTION OF AN OPAQUE OPTICAL CONTOUR TRACER FOR CHARACTER RECOGNITION RESEARCH by GEORGE. MARSHALL AUSTIN B.A.Sc, University of Br i t i s h Columbia, 1964 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE i n the Department of Ele c t r i c a l Engineering We accept this thesis as conforming to the standards required from candidates for the degree of Master of Applied Science Members of the Department of E l e c t r i c a l Engineering THE UNIVERSITY OF BRITISH COLUMBIA. December, 1967 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r an advanced degree at the U n i v e r s i t y of B r i t i s h C o lumbia, I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y purposes may be g r a n t e d by the Head of my Department o r by h i s r e p r e s e n - t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Depa rtment The U n i v e r s i t y of B r i t i s h Columbia Vancouver 8, Canada ABSTRACT This thesis describes the design and instrumentation of an opaque contour-tracing scanner for studies i n o p t i c a l character recognition (OCR). Most previous OCR machines have attempted to recognize characters by mask matching, a technique which requires a large and expensive computer, and which i s sensitive to small changes i n type font. Contour tracing i s a promising new approach to OCR. In contour t r a c i n g , the outside of the character i s followed, and the r e s u l t i n g horizontal and v e r t i c a l co-ordinates, X(t) and Y ( t ) , of the scanning spot are processed for recognition. Although much additional research i s required on both scanner design and processing algorithms, i t i s expected that an OCR device which uses a contour-tracing scanner w i l l be s i g n i f i c a n t l y less expensive than e x i s t i n g multifont recognition machines. In t h i s t h esis, four possible contour-tracing scanners are proposed and evaluated on the.basis of cost, complexity and a v a i l a b i l i t y of components. The design that was chosen for construction used an X-Y oscilloscope and a photomultiplier as a flying-spot scanner. In instrumenting t h i s design, a d i g i t a l - to-analogue converter, an up-down counter and many other special purpose logic c i r c u i t s were designed and constructed.- The scanner successfully contour traced Letraset characters, typewritten characters and handprinted characters. At the machines maximum speed, a character i s completely traced i n approximately 10 msec. Photographs of contour traces and . the X(t) and Y(t) waveforms are included i n the t h e s i s . i i Although the present system w i l l only trace two adjacent characters, proposed modifications to the system would enable an entire l i n e of characters to be contour-traced. Included i n the thesis are recommendations for further research on scanner design. i i i TABLE OP CONTENTS Page ABSTRACT . . i i TABLE OP CONTENTS i v LIST OF ILLUSTRATIONS . . . v i ACKNOWLEDGEMENT .. v i i i I. INTRODUCTION 1 1.1 Purpose of Research 1 1.2 A B r i e f Review of Previous Work on OCR ... 2 1.3 P r i n t i n g Noise 5 1.4 The Contour-Tracing Method of OCR ... 6 1.5 Scope of t h i s Thesis 12 I I . METHODS FOR IMPLEMENTING CONTOUR TRACING ..... 14 2.1 The Contour-Tracing Algorithm 14 2.2 A General Contour Tracer 15 2.3 Analysis of Pour Proposed Contour-Tracing Scanners 17 2.4 Summary and Comparison of the Four Proposed Contour-Tracing Systems ......... 22 I I I . DESIGN AND INSTRUMENTATION OP THE CONTOUR- TRACING SCANNER 24 3.1 Captive Scan Control C i r c u i t s 24 3.2 System Control C i r c u i t r y 29 3.3 Error Correction C i r c u i t s 33 IV. RESULTS OF SYSTEM TEST . ... 37 4.1 A B r i e f Review of the System Operation .. 37 4.2 Contour-Tracing Results 38 4.3 Problems Encountered i n Contour Tracing . 43 i v Page 4^4 Suggestions for Further Work 46 APPENDIX I COMPARISON OF SOME COMMERCIALLY AVAILABLE OCR MACHINES . . 48 APPENDIX II MODIFICATIONS REQUIRED TO TRACE AN ENTIRE LINE OF CHARACTERS ' ........................ 49 A 2 . 1 Analogue Method of Tracing a F u l l Line of Characters 49 A 2 . 2 D i g i t a l Method of Tracing a F u l l Line of Characters 51 APPENDIX III UP-DOWN COUNTER ... ' 53 APPENDIX IV WEIGHTED-RESISTOR DIGITAL-TO-ANALOGUE ' CONVERSION CIRCUITRY AND ERROR ANALYSIS . 57 A 4 . 1 Weighted-Resistor Digital-to-Analogue (D/A) C i r c u i t s 57 A 4 . 2 Steady State Errors i n the Weighted-Resistor D/A Converter 58 A 4 . 3 Speed Limitations i n the Weighted-Resistor D/A Converter 62 A 4 . 4 Resistor Trimming C i r c u i t r y 65 A 4 . 5 D/A Current-Switch Driver C i r c u i t s 68 APPENDIX V DESIGN OF THE OPTICS SYSTEM 69 A 5 . 1 Contour-Tracing Scanner Optical Requirements 69 A 5 . 2 Results of the -Thick "Lens Optics . Investigation 70 APPENDIX VI THE SYSTEM BLOCK DIAGRAM . . . 73 REFERENCES . . 76 v LIST OP ILLUSTRATIONS Figure Page 1-1 Basic components of an OCR system 1 1-2 Optical mask matching . .3 1-3 An i l l u s t r a t i o n of contour t r a c i n g 7 1-4 Extrema on the contour trace . 8 1-5 Hysteresis smoothing 9 1- 6 Code and co-ord word formation 10 2- 1 An example of the contour-tracing algorithm . 15 2-2 A general contour tracer 16 2-3 Scanning with a l i n e a r array of photodiodes. The photodiode outputs are sampled and stored i n a character memory 18 2- 4 Analogue method of contour t r a c i n g 21 3- 1 Block diagram showing the basic parts of the contour-tracing scanner 24 3-2 Truth tables for up-down logic control 26 3-3 Up-down control c i r c u i t r y . The symbol § denotes the complemented Exclusive OR operation 27 3-4 Toggle pulse synchronization c i r c u i t r y 28 3-5 C i r c u i t r y for determining a complete contour trace. Only the c i r c u i t s for the Y co-ordinate are shown, c i r c u i t s for the X co-ordinate are i d e n t i c a l 30 3-6 C i r c u i t r y for storing Xmax, the rightmost point on the character being scanned 31 .3-7 C i r c u i t r y for counting three consecutive turns i n the same d i r e c t i o n 34 3-8 Error correction c i r c u i t r y 35 3-9 A troublesome s t a r t i n g point 36 v i Figure Page 3- 10 Starting-point error correction c i r c u i t r y . . 36 4- 1 Contour-tracing r e s u l t s ; characters are from Letraset sheet 210 39 4-2 Contour-tracing r e s u l t s - typewritten characters (Hermes E l e c t r i c ) 4l 4-3 Contour-tracing r e s u l t s - handprinted and typewritten characters 42 4-4 Contour trace of an upper case N using a PDP-9 computer 45 4-5 Upper case M contour trace from a Letraset 210 sheet 45 A3-1 Up-counting sequence 53 A3-2 P a r a l l e l up counter 54 A3 -3 P a r a l l e l up-down counter 56 A4-1 Weighted-resister D/A converter c i r c u i t ... 57 A4-2 Operational amplifier model 58 A4 -3 Current d i v i d i n g r e s i s t o r tolerance for weighted-resistor digital-to-analogue converters 63 A4-4 C i r c u i t for adjusting R T to the required accuracy --65 A4-5 Resistance values for a weighted-resistor 8 b i t D/A converter .... 67 A4-6 Current-switch driver c i r c u i t 68 A5-1 Scanner o p t i c a l system 71 A5-2 F i n a l o p t i c a l system design 71 A6-1 D e f i n i t i o n of symbols and terminology 73 A6-2 System block diagram 74 A6-3 System'control logic 75 v i i ACKNOWLEDGEMENT Acknowledgement i s very g r a t e f u l l y given to the National Research Council for t h e i r f i n a n c i a l support of t h i s project, and also for the summer supplement received during the summer of 1967. I would l i k e to thank Dr. R. W. Donaldson for his many hel p f u l suggestions both during the design of the scanner and also during the writing of t h i s t h e s i s , and Dr. M. P. Beddoes for reading the manuscript and his h e l p f u l suggestions. I would also l i k e to thank Dr. R. A. Nodwell of the U.B.C. Physics Department for his he l p f u l suggestions concerning the o p t i c a l system, Mr. C. Chubb, for his assistance and suggestions concerning the mechanical work i n the project, Mr. K. Spencer for the assistance he gave me i n programming the PDP-9 computer, and Mr. D. McCracken for his help i n getting the computer interface operational. I would also l i k e to thank my parents for t h e i r constant encouragement, and Miss S. Rogers, Miss J. M. Towers and Mrs. R. Thomas for typing t h i s manuscript. Also many thanks to the Department of F i s h e r i e s of Canada, who made t h e i r f a c i l i t i e s a v a i l a b l e for typing the f i n a l manuscript and to my colleagues who proofread the t h e s i s . v i i i DESIGN AND CONSTRUCTION OF AN OPAQUE OPTICAL OONTOUR TRACER FOR CHARACTER RECOGNITION RESEARCH I. INTRODUCTION 1.1 Purpose of Research This thesis describes the design and construction of an o p t i c a l scanner for research i n machine recognition of type- written, handprinted, and handwritten characters. An OCR. system i s often considered to be a concatenation of the three subsystems shown i n F i g . 1-1. [ l ] S t a t i s t i c s of Input Character Set F i g . 1-1 Basic components of an OCR system. The scanner transforms each character into e l e c t r i c a l signals. These signals are then processed to y i e l d a set of measure- ments. The decision device uses these measurements and the s t a t i s t i c s of the input character set to i d e n t i f y the character. The p r o b a b i l i t y of an i d e n t i f i c a t i o n error depends on the set of allowable characters, the s t a t i s t i c s of the character set, the way i n which the characters are transformed into e l e c t r i c a l 2 signals, the signal processing algorithm, and the decision algorithm. An OCR machine would have many uses, some of which are: 1. A computer input device - an OCR device which could translate typewritten, handprinted or handwritten characters d i r e c t l y into machine language would eliminate the time consuming and costly process of key-punching programs and data. 2. A transducer for data communication - a device which could convert printed characters d i r e c t l y into signals for transmission to a distant point would be extremely useful. 3- A sensor for machines which sort mail, packages, and other objects i n accordance with i d e n t i f y i n g characters f a l l into t h i s category. 4. An input for machines which transforms characters into non-visual stimuli - one such machine i s a reading machine for the b l i n d . 1.2 A B r i e f Review of Previous Work on OCR Many attempts have been made to b u i l d character readers. Some of these attempts have been p a r t i a l l y successful, although the readers are very expensive. Most machines do not recognize a l e t t e r or character i n a way that depends on the ch a r a c t e r i s t i c shape of the l e t t e r . For t h i s reason, they recognize only a few of the hundreds of d i f f e r e n t type fonts. The most common technique i s to make an o p t i c a l or electronic image of the unknown character and compare i t with either an o p t i c a l or electronic mask of a l l characters i n the machine's "vocabulary" [2,3j . The mask which most clos e l y f i t s the unknown character i d e n t i f i e s the character. Usually the masks are applied both p o s i t i v e l y and negatively, i n order to check both white and black areas. Optical mask matching i s i l l u s t r a t e d i n F i g . 1-2. (a) An E Projected on an F Mask Oo) An F Projected on an E Mask vfi |B o l QD ] | I |G H| IJ yJ I i l i mm Bo dl J IR 2I IT ul (b) Comparison Mask (c) Recognition F i g . 1-2 Optical mask matching. In electronic mask matching, the l e t t e r i s read into computer memory using a flying-spot scanner, or an array of photocells, or some other similar device. The mask matching i s done i n memory rather than o p t i c a l l y . Although the electronic matching technique i s much faster than the o p t i c a l scheme, the two methods are equivalent i n p r i n c i p l e and have In B B d d B B d d '•1 |fl R R >1 Jl R R Jl Jl ;;] d B B d d B B d d d fl R R Jl J) Rl R Jl Jl d B B d d B B d d (a) Image Array s i m i l a r error p r o b a b i l i t i e s . I f the image s i z e , the type font, or the orientation of the unknown, character i s not almost i d e n t i c a l to the mask, then p o s i t i v e i d e n t i f i c a t i o n w i l l not be made. A v a r i a t i o n on mask matching, N-tuple matching, was used by L i u and Shelton [^] . Each N-tuple consists of f i v e to nine points i n a prescribed s p a t i a l arrangement, and has a pre- scribed assignment of black and white states for each point. These .N-tuples are shi f t e d with respect to the input character so that the N-tuples are tested for a match i n a l l discrete positions on the character. It was found that N-tuple matching would be useful i n a multifont machine only i f many N-tuple comparisons were made. As a r e s u l t , a large, fast and expensive computer would be required. Performance data on character recognition using contour tracing i s very scarce, but most encouraging [ 5 , 6 ] . To. indicate the range of speed, cost and f l e x i b i l i t y that e x i s t i n g machines have, a set of p a r t i a l s p e c i f i c a t i o n s for some of the commercially available o p t i c a l readers obtained from [ 2 ] are presented i n Appendix I. The error rates were given for only two of the six machines, the Philco, and Sylvania machines. Philco and Sylvania machines both claim an error rate of .01%. As can be seen from Appendix I, these machines are very expensive. 5 1.3 Pr i n t i n g Noise P r i n t i n g noise occurs when, a character i s not always written or printed i n exactly the same way. The most common kinds of p r i n t i n g noise are l i s t e d below. 1. Variations i n character style - The exact appearance of each printed character depends upon the type font. For t h i s reason, multifont recognition machines should recognize characters from t h e i r o v e r a l l general shape. 2. Type size variations - General purpose OCR machines must not be sensitive to character size v a r i a t i o n s . 3. Character orientation f a u l t s - Variations i n orienta t i o n occur occasionally when a'character i s printed with a t i l t from the v e r t i c a l . 4. Character r e g i s t r a t i o n f a u l t s - Occasionally characters appear s l i g h t l y above or below the p r i n t i n g l i n e . 5. Character spacing f a u l t s - Some OCR devices depend on regular character spacing for correct recognition. Orientation, r e g i s t r a t i o n , spacing f a u l t s cause incorrect p o s i t i o n i n g and make machine recognition d i f f i c u l t . 6. Touching characters - Touching characters are troublesome for OCR machines which require the i n d i v i d u a l characters to be separated for in d i v i d u a l recognition. 7. Broken characters - Broken characters are troublesome for most OCR machines, es p e c i a l l y those employing contour t r a c i n g . 8. Salt and Pepper Noise - Salt and pepper noise i s caused by a lack of ink when p r i n t i n g . The character produced i s not completely black, but i s mottled black and white. Thus, i n d i s t i n c t boundaries r e s u l t . 9. Ink.run - Ink run occurs when too much ink i s used i n p r i n t i n g . Ink run a l t e r s the shape of the character contour. The most common causes of p r i n t i n g noise are variations i n l e t t e r s t y l e and s i z e . The next most common causes are r e g i s t r a t i o n and orientation errors; these f a u l t s occur mainly i n newspaper text. Character spacing i n some type fonts i s proportional to l e t t e r width. A l l other sources of p r i n t i n g noise occur very r a r e l y . characters and handwritten words. Reliable s t a t i s t i c s on r e l a t i v e occurrences of the various kinds of noise are not a v a i l a b l e . Previous attempts to recognize handwriting i s d i s - cussed i n [7,8] . Techniques for recognition of handprinted numerals are discussed i n 111 . 1.4 The Contour-Tracing Method of OCR The l i m i t a t i o n s and high cost of e x i s t i n g character recognition techniques motivated the search for new ones. Recently, Clemens [5] proposed a contour-tracing scheme i n which the unknown character i s recognized by the shape of i t s outside contour. A l i t t l e work with a p e n c i l and paper shows that i f any white areas of a typewritten character completely enclosed by black are blackened, the l e t t e r i s s t i l l recognizable from the exterior contour which remains. This statement applies The above kinds of noise are also present i n handprinted to well-formed handprinted characters, and to handwritten words made by t good writer. Clemens tested his idea by using a f l y i n g spot scanner to make a spot of l i g h t follow the black/ white interface around the outside of the typewritten characters. The trace started at the extreme l e f t point on the l e t t e r and then proceeded In a clockwise d i r e c t i o n around the outside of the l e t t e r , This contour trace yielded the time functions X(t) and Y ( t ) , the horizontal and v e r t i c a l co-ordinates of the scanning spot (see F i g . 1-3). The o r i g i n of the co-ordinate system i s the s t a r t i n g point of the trace. Direction of trace X,Y Start p o s i t i o n F i g . 1-3 An i l l u s t r a t i o n of contour tracing. Prominent l o c a l extrema i n the X(t) and Y(t) functions r e s u l t from sudden changes i n contour curvature. The locations i n X-Y space of these extrema are used to recognize the l e t t e r s F i g . 1-4 shows that j o i n i n g the X and Y extrema by straight l i n e s i n the order i n which the extrema occur y i e l d s a l e t t e r which i s s t i l l recognizable. It appears that the location of 8 prominent extrema provides s u f f i c i e n t information for recognition. F i g . 1 -4 Extrema on the contour trace. Quantization of X(t) and Y ( t ) , ink run, fuzzy edges and variations i n type style cause spurious l o c a l extrema to appear along with the prominent extrema i n X(t) and Y ( t ) . Spurious l o c a l extrema i n X(t) which res u l t from type font variations r a r e l y exceed W/4, where W i s the l e t t e r ' s width. Spurious l o c a l extrema i n Y(t) r e s u l t i n g from-type font variations r a r e l y exceed H / 4 , where H i s the l e t t e r ' s height. Prominent extrema nearly always exceed W/4 and H /4. Clemens showed that spurious extrema could often be removed by hysteresis smoothing. A simple hysteresis smoothing c i r c u i t and smoothed output i s shown i n F i g . 1 - 5 . The voltage E i s approximately W/4, and i s d i f f e r e n t for each character traced. For t h i s reason, the character must be traced twice, the f i r s t time to measure the height and width, the second time'to record the extrema of the . smoothed X(t) and Y(t) functions. 9 F i g . 1-5 Hysteresis smoothing. Contour tr a c i n g with hysteresis smoothing can be made to minimize the eff e c t of variati o n s i n character style and s i z e . The ef f e c t s of character size variations are removed by measuring the height and width. Spacing and r e g i s t r a t i o n errors are eliminated, since each character i s located by a search scan. Clemens found that the contour t r a c i n g method of OCR i s not sensitive to small character o r i e n t a t i o n f a u l t s . Touching • 1 0 l e t t e r s can be contour traced £.nd recognized as one character. Broken l e t t e r s , however, are s t i l l troublesome. Fortunately, touching l e t t e r s and broken l e t t e r s occur very r a r e l y . Clemens' system recorded the extrema of the smoothed trace i n the order i n which they occurred i n tracing around the l e t t e r . A l i t t l e thought shows that there w i l l always be two choices for a future extremum. Thus i t was natural to use a binary number system to record the sequence of extrema. A d i g i t a l one was recorded for each X extremum and a d i g i t a l zero for each Y extremum. The r e s u l t i n g binary number was c a l l e d the codeword. To indicate the locations of the various extrema, each character was divided up into four quadrants l a b e l l e d 0 0 , 0 1 , 10 and 1 1 . Each time an extremum was found, the quadrant i n which the extremum occurred was recorded. The r e s u l t i n g number was c a l l e d the co-ord word (co-ordinate word). An example of how the code ' and co-ord word are formed i s given i n F i g . 1 - 6 . W/4 < > Xmax F i g . 1-6 Code and co-ord word formation. • 11 Clemens used the codeword, the co-ord word and the height to width r a t i o , along with the table look-up f a c i l i t i e s of a computer to recognize type-set l e t t e r s . In t e s t i n g his techniques, he scanned a transparency of a page of Time magazine, stored the points i n a computer and simulated his contour trace. Over 3300 characters were encountered. The o v e r a l l error rate was approximately 3%, including l e t t e r s , and punctuation marks from both t i t l e s and text. It was predicted that had the f a c i l i t y for detecting ascenders and decenders been incorporated, the error rate would be approximately 1%. It was found that broken l e t t e r s would be the only source of p r i n t i n g noise that could not be e a s i l y overcome. Some of the confusions made by the machine were among l e t t e r s most e a s i l y confused by eye. For example, c and e were confused, as were i and 1, r and p and B and D. Since confusions are not random substitutions of the other 25 l e t t e r s of the alphabet, they can probably be reduced by some error correcting scheme. Ex i s t i n g e l e c t r o n i c components w i l l permit tracing twice around an average'letter i n approximately one to two m i l l i - seconds, assuming (conservatively) that 250 points on the contour are examined during each trace, and that examination of each point requires 1 ysec. The time quoted would allow for approximately 700 usee to search for the next l e t t e r . Signal processing and decision making would be completed during the search for the next l e t t e r . The recognition rate would be between 500 and 1000 characters a second. Accuracy figures w i l l not be available u n t i l various processing and decision algorithms have been investigated. The cost of the scanner i s estimated at $ 5 , 0 0 0 or le s s . The cost of the processing and decision making part of system i s estimated at $ 1 0 , 0 0 0 . I t appears that typewritten characters can be recognized with considerable accuracy from the shape of t h e i r exterior contour alone, and the OCR system using contour tracing w i l l be much less expensive than e x i s t i n g systems. More research on processing and decision algorithms i s needed. In p a r t i c u l a r , algorithms should be devised which make e f f i c i e n t use of s t a t i s t i c a l constraints between characters. Also i t seems worthwhile to try to extend Clemens' technique or a modified form of i t to the recognition of handprinted characters and handwritten words. 1.5 Scope of t h i s Thesis The remainder of t h i s thesis describes the design and construction of a contour-tracing scanner for an experimental OCR system. The sp e c i f i c a t i o n s for the scanner are as follows: 1. The scanner must be able to follow the white/black interface around the outside of the characters at a high rate of speed. For a prototype machine, a tracing time for one character of 1 to 1.5 msec, would be required. For the experimental machine described i n t h i s t h e s i s , a tracing time of 1 0 0 msec, i s acceptable. 2 . When the trace around one l e t t e r i s complete, the scan must go into a search mode to fin d the next l e t t e r i n 13 sequence. • 3. The scanner must automatically go into the trace mode when the next l e t t e r i s found. 4. The scanner must have enough resolution to be y.ble to trace around characters having a wide range i n size and s t y l e . 5. The scanner must be able to scan an entire l i n e on a &i inch wide paper. 6 . When the scanner gets to the end of a l i n e , i t must search f o r the next l i n e , return to the star t of the next l i n e , and automatically st a r t searching for the f i r s t character. The scanner was constructed to meet the f i r s t four s p e c i f i c a t i o n s . The design was such that the basic scanner system would e a s i l y interconnect with the additional c i r c u i t r y required to make the system trace a whole page. 14 II. METHODS FOR IMPLEMENTING CONTOUR TRACING 2.1 The Contour-Tracing Algorithm Contour tracing consists of two basic scanning operations; search and trace. The search operation i s used to f i n d the leftmost point of a character. The search scan starts at a point just below the l i n e of print and travels i n a v e r t i c a l d i r e c t i o n to a point just above the l i n e of p r i n t . If no black spot i s seen, the trace i s moved one increment to the ri g h t and the v e r t i c a l scan i s repeated. This search scan continues u n t i l the f i r s t black point i s found. The f i r s t black spot seen causes the system to switch to the trace mode. In the trace operation, a very simple contour- tracing algorithm i s used to guide the trace around the outside of the character. This algorithm consists of three r u l e s . To use these rules, the d i r e c t i o n defined by the present point and the pre- viously examined point i s used as a reference d i r e c t i o n . Rule 1: If the point being examined i s black, turn 90° to the l e f t , move one increment, and test this new point. Rule 2: I f the point being examined i s white, turn 90° to the r i g h t , move one increment, and test this new point. Rule 3: If three consecutive turns i n the same d i r e c t i o n occur, turn i n the opposite d i r e c t i o n on the fourth turn. The f i r s t two rules are essential for contour tracing a character. The t h i r d i s an error correcting rule that tends to force the trace back to the black/white interface of the character i f a wrong decision as to the colour of a point i s made. Fig.'2-1 i l l u s t r a t e s the contour trace. r1 15- Pig. 2-1 An example of the. contour-tracing algorithm. Some thought shows that these rules cause the scanning spot to move around the outside of the character i n a clockwise d i r e c t i o n , and that the trace must h i t every black spot on the character that i s within one increment of the edge. It follows that the scanning spot always returns to the s t a r t i n g point, providing no error i s made i n deciding on the colour of any point. To ensure a unique s t a r t i n g point for the trace, and to prevent the trace from breaking into the inside contour of l e t t e r s , the l i n e width of each character must equal or exceed two increments. '2.2 A General Contour Tracer The general structure of four proposed contour-tracing systems to be described i n the next section appears i n F i g . 2-2. 1 6 Character Memory Detector Logic i —» V* Test- P o s i t i o n - Control 1 • Output x(t) Y(t) System Control "S. F i g . 2-2 A general contour tracer. The shape of the character's outside contour i s stored i n the character memory. The character memory may be the actual printed page or a hardware memory. The location i n memory to be examined i s selected by the te s t - p o s i t i o n - c o n t r o l block. The detector then ascertains whether the spot corresponding to that lo c a t i o n i s white or black. The signal from the detector i s used by the lo g i c network to calculate the co-ordinates of the next point to be examined. The te s t - p o s i t i o n - c o n t r o l block then uses the logic block signal to select the next location to be examined. The output section of the system takes the signals from the te s t - p o s i t i o n - c o n t r o l block and produces the two time functions, X(t) and Y ( t ) . The main function of the system- • 17 control block i s to use the signals generated by the t e s t - p o s i t i o n - c o n t r o l block to switch the system from the search to the trace mode,or from trace to search node at the appropriate times. 2.3 Analysis of Four Proposed Contour-Tracing Scanners In se t t i n g out to design a f l e x i b l e contour-tracing scanner, many s p e c i f i c systems were considered. The four most promising systems are described below. System 1: Photodiode Matrix An optics system would be used to focus the image of the unknown character onto a two dimensional, 50 by 5 0 , array of photodiodes (or phototransistors). This array would constitute the character memory. The t e s t - p o s i t i o n - c o n t r o l block would consist of two b i - d i r e c t i o n a l s h i f t r e g i s t e r s , one for each axis of the array, so that any element of the array could be selected for examination by the detector. The detector would decide whether the l i g h t f a l l i n g on that p a r t i c u l a r element came from a white or a black spot on the character. The l o g i c block and the output portion of the system would function as described i n Section 2.2. The output block would consist of two up-down counters and two digital-to-analogue (D/A) converters to produce X(t) and Y ( t ) . The system-control block would have to control the repositioning of the array r e l a t i v e to the next character, i n addition to c o n t r o l l i n g the system modes (search and t r a c e ) . The time required for t h i s mechanical repositioning would severely l i m i t the rate at which a l i n e of print could be scanned. 18 Furthermore, a 50 by 50 array of phototranslstors would have to be a s p e c i a l l y constructed item, not r e a d i l y a v a i l a b l e and very expensive. As an example of the cost involved, a l i n e a r array of 126 photodiodes on 6 mil centres costs $788. [ l l ] System 2: Linear Photodiode Array and Core Memory System 2 attempts to overcome the repositioning d i f f i c u l t y , the high cost and long delivery time inherent i n System 1. In System 2, an optics system would be used to focus the printed characters onto a v e r t i c a l , l i n e a r array of 50 photodiodes or phototranslstors. The page would move r e l a t i v e to the array, and at a fixed increment i n distance, the l i n e a r array would be sampled and deposited i n the character memory (see F i g . 2-3). page l i n e a r array of photodiodes magnetic core ^/ memory F i g . 2-3 Scanning with a l i n e a r array of photodiodes. The photodiode outputs are sampled and stored i n a character memory. The character memory would i n a l l p r o b a b i l i t y be a magnetic core array. Contour tracing would be carried out i n the memory as described i n Section 2 . 2 . The detector, l o g i c , t e s t - p o s i t i o n - c o n t r o l and output blocks would be similar, to" thoss described i n System 1. I f the time required to trace a character i n memory i s less than the time required for the photocell array to scan a character, then the memory would need to store only two complete characters and not a l l the characters on a l i n e . The storing of the next character would be time shared with the traci n g of the present character. The system control block would have to control the scan mode, the time sharing, and possibly the scanning rate. System 2 has overcome the pos i t i o n - c o n t r o l problem by remapping the o p t i c a l image of the character i n memory. The electronic complexity of System 2 has increased over that of System 1. The cost of a core memory of 50 by 100 elements would probably be i n the order of $5,000 to $ 6 , 0 0 0 . This price would include core, core d r i v e r s , random access r e g i s t e r , information r e g i s t e r , and r e g i s t e r i n d i c a t o r s . This price i s based on a quotation on a 256 words by 18 b i t s memory. [12] The delivery time would be approximately six months. Because of the high cost and long delivery time associated with System 2, a t h i r d system was contemplated. System 3: Oscilloscope and Photomultiplier - Discrete Scan In System 3, the printed page becomes the character memory. The t e s t - p o s i t i o n - c o n t r o l block uses an X-Y oscilloscope as an e l e c t r o n i c a l l y positioned l i g h t source. The signals to the oscilloscope are derived from up-down counters coupled to D/A converters. The l i g h t from the oscilloscope's cathode ray tube • 20 (CRT) i s focused onto the page by,an optics system. The detector i s a photomultiplier positioned to gather the l i g h t r e f l e c t e d from the page. The amount of l i g h t gathered determines whether or not the illuminated spot on the page i s white or black. The logic block calculates the necessary co-ordinate changes as described i n Section 2 . 2 . The output signals are the X and Y oscilloscope input signals. The system control i s e s s e n t i a l l y the same as described i n Section 2 . 2 . Unfortunately, the resolving power of the CRT i s not s u f f i c i e n t to allow any more than'two characters to be traced at a time, since the optics system must reduce the size of the object by a factor of 1 0 (see Appendix V). In Appendix I I , modifications to System 3 are proposed which w i l l enable an entire l i n e of print to be scanned. Another d i f f i c u l t y with System 3 i s .that there i s very l i t t l e l i g h t available from the CRT i f good re s o l u t i o n i s desired. Consequently, not much l i g h t w i l l be r e f l e c t e d from the page. The reasonable cost and the o f f - t h e - s h e l f a v a i l a b i l i t y of oscilloscopes and photomultipliers makes System 3 a t t r a c t i v e . An X-Y oscilloscope costs approximately $ 1 , 5 0 0 . A photomultiplier costs approximately $ 1 0 0 . System 4: Oscilloscope and Photomultiplier Analogue Scan. System 4 i s similar to System 3 i n p r i n c i p l e , and i t contains the e s s e n t i a l l y the same components, an X-Y oscilloscope and a photomultiplier. In System 4, however, the control signals to the oscilloscope are derived from two sinusoidal o s c i l l a t o r s and two sample and hold (S & H) c i r c u i t s . The o s c i l l a t o r : 21 frequencies are i d e n t i c a l but t h e i r phase angles d i f f e r by TT/2 radians. The output of the S & H c i r c u i t s act as variable p o s i t i o n signals for the X-Y oscilloscope. The held voltages on the two S & H c i r c u i t s become the X and Y co-ordinates of the centre of the small c i r c l e produced by the two o s c i l l a t o r s . When a t r a n s i t i o n from white to black i s found, the X and Y de f l e c t i o n voltages are stored i n the S & H c i r c u i t s . The o s c i l l a t o r s then cause the scanning spot to move i n a c i r c u l a r arc u n t i l another white to black t r a n s i t i o n i s found. At t h i s point the S & H "circuits are again triggered, and t h i s new edge point becomes the centre of the next c i r c l e . F i g . 2-4 shows that the trace follows the outside contour of the l e t t e r . D i f f i c u l t y may be encountered i n storing the analogue co-ordinates of the start p o s i t i o n , since S & H c i r c u i t s cannot hold a dc l e v e l without the voltage sagging with time. F i g . 2-4 Analogue method of contour tracing. There i s also another problem; i f the above technique i s adapted to t r a c i n g a l i n e of characters, the design of the S & H becomes very d i f f i c u l t . A 70 space l i n e at 40 increments per space has • 22 2800 increments. A p r a c t i c a l S & H w i l l work between the l i m i t s of ± 10 v o l t s ; therefore each increment must be approximately 7 mv. The S & H voltage must be at least one order of magnitude more accurate than-the smallest increment. To design an S & H c i r c u i t to operate over a range of 20 v o l t s with an accuracy of less than 1 mv i s extremely d i f f i c u l t . 2.4 Summary and Comparison of the Pour Proposed Contour-Tracing Systems The contour-tracing speed of System 1, which uses a two dimensional photosensitive array, i s limited by the time required to mechanically p o s i t i o n the array. Also, the array i s very expensive. System 2 , which uses a magnetic core memory, should contour trace very quickly with a minimum of mechanical positioning problems. The major disadvantage Is the high cost and long delivery time of core memory. In System 3, t r a c i n g an entire l i n e of characters and making e f f e c t i v e use of low l i g h t l e v e l s w i l l be the major problems to overcome. Appendix II describes two possible ways i n which an entire l i n e of characters may be contour traced. Low l i g h t l e v e l s can be tolerated i f a very sensitive PM i s used. Some t e s t s , however, would have to be carried out to determine the s e n s i t i v i t y required. System 3 has the advantage that i t may be b u i l t now, using r e l a t i v e l y inexpensive and rea d i l y available components to scan two consecutive characters, and at a l a t e r 23 date the system may be expanded to trace a whole l i n e of characters. System 4 may have a s l i g h t cost advantage over System 3, but i t i s not suitable for tracing an entire l i n e of characters. Since the X(t) and Y(t) waveforms from single characters are needed for research on recognition algorithms, System 3 was designed and b u i l t to trace two consecutive characters. The design was such that only minor modifications were required to enable the scanner to read an entire page. The cost of the system would be approximately $3,000. An a d d i t i o n a l $2,000 would be required to make the scanner read an entire l i n e . I I I . DESIGN AND INSTRUMENTATION OP THE CONTOUR-TRACING SCANNER 3.1 Captive Scan Control C i r c u i t s The basic contour-tracing scanner consists of a Tektronix RM56IA oscilloscope with two 3A75 amplifier plug-ins, a P h i l l i p s 53AVP eleven stage photomultiplier (PM), an optics system and appropriate d i g i t a l control c i r c u i t s . The oscilloscope's cathode ray tube (CRT) has a fast decay Pl6 phosphor. The phosphor decays to 10$ of the o r i g i n a l . i n t e n s i t y 120 nsec aft e r the e x c i t a t i o n is-removed. The basic contour-tracing system, excluding some of the control c i r c u i t s 3 a p p e a r s i n block diagram form i n Pig. 3-1• Y Up-down Counter D/A — V Clock Clock Logic D i g i t a l - t o - • Analogue Converter Up-down P Control PM < A -<-Optics Logic G E Photomultiplier X Up-down Counter D/A Fi g . 3-1- Block diagram showing the basic parts of the contour-tracing scanner. 25 The X and Y counters are each six b i t d i g i t a l counters designed to count up or down, depending upon the d i g i t a l signals applied to the counter control terminals. The D/A converters convert the six b i t d i g i t a l output from each counter to an analogue voltage proportional to the value of the d i g i t a l number. The up-down counter and the D/A converter are discussed i n d e t a i l i n Appendices III and TV, respectively. The D/A converter outputs are coupled d i r e c t l y to the X and Y.inputs of the X-Y oscilloscope. The f i r s t two rules for contour tr a c i n g (Section 2.1) imply a short term memory, since the scanning spot needs to know the d i r e c t i o n from which i t came i f i t i s to turn i n the proper d i r e c t i o n . The switching functions required to implement the above rules are now derived. Let P be the d i g i t a l photomultiplier s i g n a l . I f the illuminated spot on the page i s black, P = 0 and i f the spot i s white, P = 1. Let X i and Y^ be the up- down d i g i t a l control signals to the X and Y counters resp e c t i v e l y . I f X^ or Y^ i s one, the respective counter counts up. S i m i l a r l y , i f X^ or Y^ equals zero, the respective counter counts down. Let X^ + 1 and Y^ + 1 be the new up-down signals for the X and Y counters respectively, calculated from the current values of X^, Y i and P. To determine Y i + 1 , the P and X^ signals must be considered, since P represents the colour seen by the PM and X.̂  s p e c i f i e s the d i r e c t i o n from which the trace came. Similarly, X^ +^ i s a function of P and Y^. The truth tables for X^+^ and are shown i n Pig. 3-2 Y i p x i + i x i p Y i + 1 0 . 0: I 0 0 0 0 1 0 0 1 1 l 6 0 1 0 1 l I I 1 1 0 F i g . 3-2 Truth tables for up-down lo g i c control. It i s seen that these truth tables are consistent with the two t r a c i n g rules given above. I f the symbol © indicates the Exclusive OR function then the truth table may be replaced by the equations l + l l X. + 1 = Y± © P The function A © B i s s l i g h t l y easier to r e a l i z e using NOR gates than the function A © B. For brevity the symbol © w i l l be used to denote the complemented Exclusive OR function. The decision to increment the counters i n either the up or the down d i r e c t i o n must be made before the counting pulse reaches the counters. For t h i s reason, two clock pulses equally spaced from each other i n time are used. These two clock pulses are c a l l e d clock 1 and clock 2. Clock 1 i s used to t r i g g e r a l t e r n a t e l y the X and Y counters, and clock 2 i s used al t e r n a t e l y to set the counter control terminals according to the value of P and the previous d i r e c t i o n of t r a v e l . The c i r c u i t i n F i g . 3-3 calculates the counter control signals. After the X counter has been toggled by clock 1, and P are read by the § c i r c u i t and P © X i i s obtained and.routed to the J-K terminals of FF . The clock 2 pulse i s gated to make FF assume the state determined by i t s V J-K terminals. Y i o—*-Y counter control signals o — < — X. 1 o—<-X counter control signals o—<- Buffer J-K f l i p flop 1 R j n T K 1 R J FF T X 0 K f l >4 Complemented Exclusive OR Gate F i g . 3-3 Up-down control c i r c u i t r y . The symbol © denotes the complemented Exclusive OR operation. After Buffering, the output of FF becomes the Y counter up- y down control signals. In a similar way, the X counter up-down control signal i s derived from P © Y.. It should 28 be noted that PF and FF form the short term memory necessary x y to remeirber from where the trace came. In the search mode, both F F x and F7 are held i n the reset state, causing both the X and Y counters to count up. The switching of clock 1 a l t e r n a t e l y to the X and Y counters must be synchronized with the switching of clock 2 alte r n a t e l y to F F x and'FF . F i g . 3-4 shows a suitable synchronizing system. Cl To X counter toggle input J I T. J-K FF • K 0 B B o To Y counter toggle' input NOR gate *—-o To FF toggle X * o To FF toggle F i g . 3-4 Toggle pulse synchronization c i r c u i t r y . From Fig.. 3-4 i t follows that i f A = B when the clock 1 pulse. a r r i v e s , then the clock 1 pulses are dispatched a l t e r n a t e l y to the X and Y counters and the clock 2 pulses are dispatched alternately to FF and FF . I f A f B when the clock 1 pulse x y a r r i v e s , neither counter receives a pulse and thus the B signal does not change. When the next clock 2 pulse arrives,the A signal changes and the system i s again synchronized. The steering gates and the f l i p flops which produce the A and B signals are a l l contained i n the block i n F i g . 3-1 l a b e l l e d clock l o g i c . Additional gates are provided to i n h i b i t the X counter pulses during the search mode In a way that produces a sequential v e r t i c a l scan. In F i g . 3-3, the ¥ gates, FF , FF , and the steering x y gates for d i r e c t i n g the t r i g g e r pulses to FF , FF are a l l x y contained i n the block•labelled up-down l o g i c . The clock 1 and clock 2 pulses are approximately 200 nsec wide and are produced from monostable multivibrators i n the block i n F i g . 3-1 l a b e l l e d clock. The optics block i n F i g . 3-1 i s discussed i n Appendix V. 3.2 System Control C i r c u i t r y The main function of the System Control c i r c u i t r y i s to switch the system from the search mode to trace mode and back again at the correct times. Consider now the electronic measurements that must be made to achieve system control. The system must switch from the search to the trace mode when the leftmost portion of the character i s contacted. After tracing 30 around the character twice, the system must prepare to switch back to \-.he search mode. C i r c u i t r y must be designed to t e l l the system when two successive traces have been completed, af t e r which the search scan must again be i n i t i a t e d at the rightmost portion of the character. C i r c u i t r y must also be designed to detect and store Xmax (the rightmost portion of the character). Pig. 3-5 shows c i r c u i t r y which w i l l detect each complete contour trace. Store Y Start pulse Register 77 Y Up-down Counter D i g i t a l A Comparison I. Gates A = 1 i f Y up-down Counter i s i d e n t i c a l to the Y start Register A = 0 otherwise F i g . 3-5 C i r c u i t r y for determining a complete contour trace Only the c i r c u i t s for the Y co-ordinate are shown, c i r c u i t s for the X co-ordinate are i d e n t i c a l . When the system switches from the search to the trace mode (mode 1 to 2) a pulse i s applied to the toggle input terminals of the X and Y start r e g i s t e r s causing the co-ordinates of the trace's s t a r t i n g position to be stored. The d i g i t a l comparison gates compare the binary numbers contained i n the X and Y re g i s t e r s and the X and Y up-down counters and indicate 31 i f the numbers are . i d e n t i c a l . Each time the X and Y counters return to the start p o s i t i o n , a monostable multivibrator produces an output pulse. A two-bit counter counts the number of monostable pulses and after three pulses a set-reset f l i p f l o p (S-R PP) i s set to indicate that two traces have been completed. and store the Xmax co-ordinate. The Xmax counter i s . a s i x - b i t up counter with i t s t r i g g e r i n g pulse gated as follows. Only i f the d i g i t a l comparison gates indicate that the corresponding b i t s of the X up-down counter and the Xmax counter are i d e n t i c a l and that the X up-down counter i s to count up w i l l the Xmax counter count up i n synchronism with the X up-down counter. The r e s u l t i s that the Xmax counter counts up to Xmax and remains there. The c i r c u i t r y i l l u s t r a t e d i n Pig. 3-6 i s used to detect X toggle X Up-down Counter " D i g i t a l Comparison Gates C AND gate X toggle X up signal C Counter Xmax C = 1 i f X up-down counter . i s i d e n t i c a l to the Xmax counter C = 0 otherwise Pig. 3-6 C i r c u i t r y for storing Xmax, the rightmost point on the character being scanned. 32 The quickest way to proceed to Xmax a f t e r two complete traces i s to jam transfer Xmax into the X up-down counter. Unfortunately, t h i s operation complicates the c i r c u i t r y associated with the up-down counter. For t h i s reason, a much simpler, although s l i g h t l y slower, method was adopted. After the second complete trace i s detected, the trace i s allowed to continue- u n t i l Xmax i s again detected at which time the system i s switched back to the search mode. The current mode (search or trace) i s stored i n a set- reset f l i p flop (S-R FF). The f i r s t black spot seen by the PM during the search mode causes the mode S-R'FF to set, putting the system into the trace mode.. The S-R FF cannot be reset u n t i l two traces have been completed and the count on the X up-down counter i s equal to Xmax. The system control c i r c u i t r y was designed to enable the automatic controls to be replaced by external manual controls. The manual control i s achieved with f i v e toggle switches. Activating a switch merely grounds an input to a gate on a c i r c u i t card. The controls are as follows: Stop Switch - removes the clock pulses from the system. External/Internal Switch - selects either an in t e r n a l pulse source or an external pulse, source to produce the clock pulses. Reset Switch - resets the X and Y counters. Search Switch - Activating t h i s switch causes the system to go into the search mode. The system i s prevented from entering the trace mode by causing the system to e f f e c t i v e l y see a white PM si g n a l . Trace Switch - This switch causes the system to remain i n the trace mode. The system i s prevented from returning to the search mode by disabling the gate c o n t r o l l i n g the re s e t t i n g of the mode, f l i p f l o p . 3.3 Error Correction C i r c u i t s When the above system was b u i l t and tested, i t was found that the trac i n g spot sometimes became trapped and made four consecutive turns to either the right or l e f t . This trap did not seem to be a re s u l t of a logic error, as the trapped trace was generally r i g h t on the edge of the character. It was : postulated that the spot of l i g h t from the CRT was landing on neither a white spot nor a black spot but on an edge, and the PM had d i f f i c u l t y i n determining the colour of the r e f l e c t e d l i g h t on a consistent basis.. Perhaps a reason for t h i s d i f f i c u l t y i s hysteresis i n the response of the PM. After seeing many white spots i n a row, the PM w i l l c o r r e c t l y detect only spots which are e n t i r e l y black; a p a r t i a l l y black spot w i l l be c a l l e d white. Thus, i t i s possible for the PM to • i n i t i a l l y examine a p a r t i a l l y black spot, c a l l i t black and then proceed to three t o t a l l y . white spots. When the trace returns to the i n i t i a l spot, i t now because of hysteresis, sees the spot as being white, and the trace becomes trapped. What i s needed i s the t h i r d rule i n the contour- tracing algorithm (Section 2.1); a f t e r three consecutive turns i n the same d i r e c t i o n , turn i n the opposite d i r e c t i o n on 34 the fourth turn. The operation of the c i r c u i t r y required to r e a l i z e this rule can be understood with the aid of F i g . 3-7 ._ NOR gate Mode 1/2 | A Mode 1/2 Mono • Mono Monostable multivibrator" Clock g Mode 2 to 1 pulse Mono - Mono Two-bit Counter n Detect 3 Detect 3 Two-bit Counter A- F i g . 3-7 C i r c u i t r y for counting three consecutive turns i n the same direction. Two 2-bit up counters are provided and the toggle pulses from clock 2 are gated into one of the two counters. The counter selected depends on the value of P-̂  (derived from P as w i l l be shown l a t e r ) . The output binary numbers from each of the two-bit counters are routed to two input NOR gates which detect the count of three. The toggle input of one counter resets the other counter v i a a delay mono- stable multivibrator. Consequently the output of one of the two input NOR gates w i l l indicate when three consecutive 35 turns i n the same d i r e c t i o n occur. In F i g . 3-7 3 A^ = 1 i f three consecutive l e f t turns are made (P^ = 0 ) , and = 1 i f three consecutive right turns are made (P^ = 1 ) . Signals A-̂  and B^ are used to modify the value of P for the fourth turn. Consider the following truth table and the corresponding c i r c u i t i n F i g . 3-8. A l B l p p l 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 p l = A l + B l p NOR gate F i g . 3-8 Error correction c i r c u i t r y . From the above c i r c u i t diagram and tru t h table, i t can be seen that i f A 1 = B x = 0 , P 1 = P, and i f A1 or B 1 = 1, ? 1 i s changed i n accordance with the t h i r d contour t r a c i n g r u l e . The above c i r c u i t was added to the up-down logic card to modify P to P r An additional problem arose i n the t e s t i n g of the o r i g i n a l system. Sometimes the system would begin searching a f t e r only one complete trace around the l e t t e r or sometimes the system would become trapped i n the trace mode. One possible reason for these d i f f i c u l t i e s l i e s i n the fact that i t i s possible i n applying the three contour tr a c i n g rules to return to the st a r t i n g point without completely tracing the' l e t t e r . Refer to Fi g . 3-9- , X,Y start co-ordinates Pig. 3-9 A troublesome s t a r t i n g point. In t h i s case the counter counting the number of complete traces around the character receives an erroneous s i g n a l . Since the trace must make three consecutive turns i n the same d i r e c t i o n before i t can return to i t s start p o s i t i o n (or else go completely round the character), the A-̂  and signals can be used to i n h i b i t the fa l s e count signal on the start p o s i t i o n counter. The c i r c u i t i l l u s t r a t e d i n F i g . 3-10 was added to the miscellaneous one card to achieve the error correction. A*B Monostable multivibrator Mono NOR gate B: + Count of three F i g . 3-10 Starting point error correction c i r c u i t r y . A block diagram of the complete contour-tracing scanner appears i n Appendix V I . 3 7 IV. RESULTS OF SYSTEM TEST 4 . 1 A Br i e f Review of the System' Operation The contour tracer has two mo^es of operation, search and trace. In the trace mode, each of the X and Y up-down counters i s triggered a l t e r n a t e l y and i n such a way that the contour-tracing rules are obeyed. In the search mode, a sequential v e r t i c a l scan i s used to f i n d the leftmost portion of the next character. When the f i r s t black spot i s seen by the PM, the system switches from the search to the trace mode. The system can return to the search mode only a f t e r the charcter has been traced twice and the trace has returned to Xmax. In order to determine the number of times a character has been completely traced, the X and Y co-ordinates of the start p o s i t i o n must be stored i n d i g i t a l r e g i s t e r s . D i g i t a l comparison gates are used to compare the count on the up-down counters to the values stored i n the X and Y start r e g i s t e r s so that the system knows when the s t a r t i n g p o s i t i o n i s again reached. A small binary counter i s used to count the number of times the system returns to the start p o s i t i o n . The Xmax r e g i s t e r i s an up counter,, suitably gated so that i t counts up to the maximum deviation i n the X d i r e c t i o n (Xmax) and remains there u n t i l a f t e r two character traces have been completed. 38 4.2 Contour-Tracing Results I n i t i a l tests using Letrasev- characters indicated that the contour tracer w i l l operate successfully at clock rates up to 200 kHz. For a clock rate of 200 kHz and a l i n e a r r e s olution of approximately 40 increments per character, the time required to trace twice around a character i s approximately 10 ms. -It was found that acceptable contour tracing could be achieved using only 20 increments per character i f Letraset characters were used, but 3 5 to 40 increments per character were required to successfully contour trace the typewritten characters from the Hermes Ambassador e l e c t r i c typewriter. Increased resolution i s required because the typewritten characters have very narrow l i n e widths. Even with 40 increments per character, the close spacing of the s e r i f s and the narrow l i n e width made the lower case M from the - Hermes typewriter d i f f i c u l t to trace. The system was tested on many d i f f e r e n t characters from several sources. Exhaustive tests were not carried out on a l l characters i n any given font, but almost a l l characters attempted were traced successfully. It was found that characters from a conventional typewriter using an old, conventional typewriter ribbon could not be contour traced due to poor black/white contrast on the page. F i g . 4-1 shows photographs of the oscilloscope•trace for characters from a Letraset sheet (sheet 210). Also shown are the X(t) and Y(t) waveforms. To y i e l d more d e t a i l i n X(t) and Y(t) waveform pictures, only 1 complete trace around the l e t t e r i s shown. In F i g . 4-2 contour traces are shown 70 msec/div F i g . 4-1 Contour-tracing r e s u l t s ; characters are from Letraset sheet 210. 10 msec/div cont d Contour-tracing r e s u l t s ; characters are f r L e t r a s e t sheet 210. 41 20 msec/div F i g . 4-2 Contour-tracing results - typewritten characters (Hermes E l e c t r i c ) 42 x HANDPRINTED e subject no. 1 Yft) Xft) 10 msec/div HANDPRINTED e subject no. 2 Yft) Xft) x HANDPRINTED e subject no. 3 Y(t) Xft) 10 msec/div. 10 msec/div. TYPWRITTEN e HERMES ELECTRIC Yft) Xft) 20 msec/div F i g . 4-3 Contour-tracing results - handprinted and typewritten characters. for several characters from a Hermes e l e c t r i c typewriter along with t h e i r respective X(t) and Y(t) waveforms. The system was also tested using some handprinted characters. The r e s u l t s are shown i n Pig. 4-3 along with a sample from the typewriter. The conditions for a l l the tests shown i n Figs. 4-1 to 4-3 were as follows: Clock rate: 10 kHz X-Y oscilloscope s e n s i t i v i t y : 2v/div. X(t) v e r t i c a l s e n s i t i v i t y : 5v/div. Y(t) v e r t i c a l s e n s i t i v i t y : 5v/div. \ Sweep rates: as l a b e l l e d The resolution i n each of Figs. 4-1 to 4-3 was approximately the same, 35 to 40 increments per character f o r lower case l e t t e r s and approximately 50 increments per character for c a p i t a l l e t t e r s . 4.3 Problems Encountered i n Contour Tracing The major d i f f i c u l t y encountered during contour tracing was the system's tendency to become trapped i n the trace mode. It was postulated that the PM would sometimes make an incorrect decision as to the colour of a point that f a l l s on a character boundary, with the re s u l t that the trace moves away from the black/white interface by more than one increment. Rule three i n the trace algorithm would then bring the trace back to within one increment of the l e t t e r edge. However, i f the PM decision error i s commit- ted while the trace i s i n the v i c i n i t y of Xmax, then the Xmax counter may become elevated to a count that may never be reached by 44 successive tracings of the character. I f the PM decision error i s made at the beginning of a character, the X and Y co-ordinates that are stored to represent the start p o s i t i o n , may never be N returned to i n subsequent tracings of the character. -In order to test the hypothesis that f a u l t y signals from the PM cause the system to become trapped i n the trace mode, the PM and the o p t i c a l system were disconnected from the system and were simulated by a PDP-9 computer. A c a p i t a l l e t t e r N was drawn graphically, and the correct PM output signals were determined by hand and stored i n 143 eighteen b i t words i n the computer. The computer program caused the stored PM information to be delivered sequentially to the contour-tracing electronics system. The purpose of the simulation was to test the ele c t r o n i c s portion of the system; i f t h i s portion were not performing according to design, the system would not respond c o r r e c t l y to the computerized PM signals. Correct response of the elect r o n i c s system to the computer signals would indicate that contour-tracing errors are caused by inadequate o p t i c a l r e s o l u t i o n and/or PM decision errors. Pig. 4-4 shows a photograph of the contour trace with r e s u l t s from the computerized PM signals. A photograph of a contour trace made by the actual system which uses the PM and o p t i c a l system appears i n F i g . 4-5. It i s seen that the trace made by the. computer simulated PM signals i s never any wider than two increments, whereas the regular contour trace i n F i g . 4-5 i s , for the most part,three increments wide and i n places four increments wide. It i s apparent that the electronic c i r c u i t r y i s performing F i g . 4-4 Contour trace of an upper case N using a PDP-9 computer. F i g . 4-5 Upper case M contour trace from a Letraset 210 sheet. as designed and that the optics and PM portion of the system causes the tra c i n g errors. There are several solutions to the above problem, some of N which are l i s t e d below. 1. I f a high quality- flying-spot scanner were used instead of the oscil l o s c o p e , then a much smaller spot size could be expected. [ l 3 J A smaller spot size would decrease the p r o b a b i l i t y of the spot landing on an edge and would be expected to increase the system r e s o l u t i o n . This solution could be very expensive. 2. The character could be re-mapped into a magnetic core memory. The contour tracing would be done on the stored image, as described i n connection with System 2 i n Chapter I I . Since the character image i n memory i s constant, there would be no d i f f i c u l t y i n returning to the star t p o s i t i o n or to Xmax. This solution i s very s i m i l a r to system design number 2 discussed i n Chapter I I . 4.4 Suggestions for Further Work For research into various algorithms for character recognition, the present contour-tracing scanner can be used with a tape recorder to provide the X(t) and Y(t) signals for computer analysis. A prototype contour t r a c i n g machine must not however be prone to getting trapped i n a character trace. Of the two solutions proposed i n Section 4.3, the second seems most p r a c t i c a l . Consider the advantages inherent i n a system similar to System 2 discussed i n Chapter.II. 47 1. The system could operate i n daylight. 2. Remapping the character into memory would eliminate the problem of inconsistently reading the colour of the examined x spot. 3 . Decision operations could be made very quickly i n core memory. (1 usee or l e s s ) . 4. In comparison with the other contour-tracer designs. System 2 would present only minor problems i n contour tracing a complete l i n e of characters. The mechanical po s i t i o n i n g problems inherent i n the other three designs have been exchanged for increased electronic complexity i n System 2. Increased electronic complexity can be handled r e l a t i v e l y inexpensively and e f f i c i e n t l y with commercially available magnetic core memories and d i g i t a l integrated c i r c u i t s . reveal the design s p e c i f i c a t i o n s , the approximate cost and the expected instrumentation problems. To improve the performance of the exi s t i n g system, further research into s p e c i f i c a t i o n s and cost of a better flying-spot scanner would be needed. Further i n v e s t ! gation into the design of System 2 would . 4 8 APPENDIX I COMPARISON OF SOME COMMERCIALLY AVAILABLE OCR MACHINES Compiled by Robert A. Wilson, 3005 Fairmount Street, Dallas, Texas 75201 CHARACTERISTICS ' ̂ FARRINGT0N OPTICAL SCANNER, 40DEL 1? IBM 1428 ALPHAMERIC CHARACTER READER, MODEL 3 PHILCO GENERAL PURPOSE PRINT READER CONTROL DATA 915 PAGE READER, RABIN0U ELECTRONICS RECOGNITION EQUIPMENT,INC ELECTRONIC RETINA W CHARACTER READER SYLVANIA ELECTRONIC SYSTEMS 01V (3) UNIVERSAL PAGE READER REMARKS GENERAL DATA ,1111111111 milium milium / / / / / / / / / / / IIIIIIUIIU milium Scanning method employed Stroke anal. Rote ting disk 'lying spot Flving soot Core memory built-in? ( I t . 1,000 characters) No core No. See note 1 Yes. 4* & up No. Set note 1 Yes. 8 to 64*. Not known *0ne "K" - 1,000 characters Compatibility with other computer systems Yes. General No. IBM only Yes. General No. CDC only Yes. General Yes. Ctoaral Delivery time from date of order 1 yr 6 mo 1 yr 6 mo 1 yr Not known INPUT MEDIUMS OTHER THAN REGULAR PRINTED PACES / / / / / / / / / / / milium milium milium milium milium Microfilm option Ko No No Yes Yes Preprinted form pages Yes Yes Yes Yea Yes Yea PRINT-READING ABILITY (VOCABULARY) milium milium milium IIIUIIIIU minium milium Standard letterpress fonts No No No No Yes Yes Standard typewriter fonts . No No Yes No Yes Yes .Special stylized (OCR) fonts only, and kind 'arr.Selfchek IBM font-onl; Not limited OCR only Not limited Not limited Computer ltneprlnter print - Yes* Yes* Yes No Yes Yes *When equipped with special OCR font. Capitals only, or caps. & lover case (I.e.) intermixed Caps, only Caps, only Caps. 6 I.e. Caps, only | Caps & I.e. Caps & I.e. Hark sensing (manual marking) available Yes Yea Yes Yes ! Yes Yes No, of alphanumeric characters ln vocabulary 60 42 Approx. 50 \ Unlimited* Unlimited * PAPER SIZES HANDLED mmmii milium / / / / / / / / / / / III mm ii | minimi IIIIIIUIIU Maximum page or document (D) size. In Inches 13 X 8.5 4 7/3x8 3/4D U X 8.5 12 X U | 1* X 1* 11 X 8.5 Minimum page or document (D) size, in inches i . H 5 2-1/3 X 3 Dre 3 X 5 A X 2-1/2 3- 1/4 X 4-7/8 Not known Can sizes be intermixed, within reasonable limits? Yes No Yes Not known Yes Yes milium i/utimm mmuui milium milium minimi No. oE characters per second (cps) 250 480 (max) Up to 2000 370 2400 max 2200 max No. of lines scanned per second on one page^ 5 2 Not known 2.7 apsrox, 12 Not known ^Depends on no. of characters in line, No. of f u l l text pages read per minute * Not known Joes not read Full cane Up to 20 5.5 12 to 30 Not known •Depending on amount of print on page 3UTPUT MEDIUMS AVAILABLE UIUII/IU IIIIUUIU / / / / / / / / / / / IIIIUUIU UIIIIIIIII milium Magnetic tope (the usual output medium) Yes Yes Yes Yes Yea Yea Punchcar-ds Yea Yea Yes Yes Yes No Punched paper tape Yes Yes Yes . Yes Yes Yes Typewriter No Yes Yes • Yes Yes Yes Teletype or comparable data transmission device Yes Yes Yes Yet Yes Not known REJECT HANDLING milium milium mmuui milium tlllUIIIIII UUIUUIIU Operator can handle on-line No No .Yes Yes No Ye'ss«) Reject pages (l)marked, (2)offset, (3)separately stacked 1, 2 1, 2 1, 3 1, 3 1, 2, 3, 3.See note 6 PRICES FOR BASIC SYSTEM milium minimi IIIUIIIIU/ iimiiuu mimiiiu milium Purchase. Including 1 yr maintenance charge 5156,000 $164,000 $525,000 $132,000«> $455,000 Not known Lease, monthly rental (includes maintenance charge) 4,235 3,475 14,000 3,500 13,500 Not known IAN INSTRUCTIONS BE STORED IN OPTICALLY READABLE FORM? No No YesW No No Yes 1. This tsachln* has no b u i l t - i n cart memory of Its own, but uses the core storage of the computer to which i t la attached. 2. For example, stubs from punchcard u t i l i t y b i l l s or gasoline credit card statements 3. By Philco Auto-Load, using pre-prlnted forms on which instructions may be coded in binary.form with a pen. 4. Includes magnetic tape unit, but no maintenance charges. 5. Not yet aold commercially. It is understood that a prototype machine with the above-listed characteristics he* been built and tested In plant, with primary application being the scanning of technical journals for mechanized Information retrieval and machine translation purposes. 6. Unreadable characters are displayed in their Immediate context on a viewing scope for manual correction via a console typewriter. "Electronic Retina" is a registered trademark of Recognition Equipment, Inc. ^9 APPENDIX II MODIFICATIONS REQUIRED TO TRAvIE AN ENTIRE LINE OF CHARACTERS A 2 .1 Analogue Method of Tracing a F u l l Line of Characters Because of the limited resolution of the oscilloscope CRT, no more than one or two characters can be traced at a time using the photomultiplier-oscilloscope design. A modification to the design has been developed to enable a whole l i n e of characters to be traced. In t h i s modification, a signal proportional to the average horizontal p o s i t i o n of the trace on the page i s subtracted from the horizontal trace s i g n a l , and the difference- signal i s displayed on the CRT. Since the average p o s i t i o n signal i s subtracted from the trace s i g n a l , the CRT need only be wide enough to display the contour, of one character. Consider that the page containing the l i n e of characters to be traced i s mounted on a moveable carriage, and l e t the horizontal p o s i t i o n of the carriage be denoted by X £. Let v"c = K X be the output voltage from a l i n e a r potentiometer mechanically coupled to the carriage, where K Q i s a constant of pr o p o r t i o n a l i t y . I f AV"T i s the analogue voltage proportional to the d i g i t a l number V"T on the X-axis up-down counter, then the de f l e c t i o n signal to the CRT can be written as follows. X = K (AV m - K X ) A 2 .1 s s T c c Where K i s a constant of pr o p o r t i o n a l i t y . The subtraction i s s effected i n a d i f f e r e n t i a l amplifier. I f V™ i s considered fixed 50 a n d X i s a l l o w e d t o v a r y b y A X , t h e n t h e c h a n g e A X , i n X i s c c s s ^ X s = - K s K c A V A 2 ' 2 A c h a n g e i n A X i n s p o t p o s i t i o n o n t h e CRT f a c e c a u s e s t h e s i m a g e o f t h e s p o t t o m o v e a d i s t a n c e o f A X' w h e r e A X ^ = m A X s A 2 . 3 T h e c o n s t a n t m i s t h e m a g n i f i c a t i o n o f t h e o p t i c a l s y s t e m . F o r p r o p e r o p e r a t i o n , t h e CRT s p o t m u s t t r a c k t h e c a r r i a g e m o t i o n , t h u s AX' = AX . T h e r e f o r e , 1 = K K A 2 .4 m s c To t r a c e a l i n e o f 70 c h a r a c t e r s a t 40 i n c r e m e n t s p e r c h a r a c t e r , a 12 b i t u p - d o w n c o u n t e r i s r e q u i r e d . T h e m a x i m u m u s e a b l e CRT s c r e e n w i d t h i s 6 cm a n d t h e r e q u i r e d o p t i c a l m a g n i f i c a t i o n , m i s - . 1 ( s e e A p p e n d i x V ) . A p r a c t i c a l D/A c o n v e r t e r o u t p u t r a n g e i s ± 10 v o l t s . I f 100 i n c r e m e n t s a r e d e s i r e d i n a 6 cm d e f l e c t i o n , t h e n t h e c o n s t a n t s i n e q u a t i o n A 2 . 1 a r e a s f o l l o w s : A = . 0 0 4 9 v o l t s / i n c r e m e n t K = 1 2 . 2 5 c m / v o l t s • • K = .815 v o l t s / c m . c . T h e r e a r e s e v e r a l i n s t r u m e n t a t i o n p r o b l e m s a s s o c i a t e d w i t h t h i s s y s t e m . E a c h i n c r e m e n t i n t r a c i n g v o l t a g e i s a p p r o x i m a t e l y 5 1 5 mv, and t h e p o s i t i o n o f t h e c a r r i a g e must be m e a s u r e d t\n o r d e r o f m a g n i t u d e more a c c u r a t e l y t h a n a t r a c i n g i n c r e m e n t . C o n s e q u e n t l y , two v o l t a g e s e a c h w i t h a m a g n i t u d e o f a p p r o x i m a t e l y 1 0 v o l t s must be s u b t r a c t e d a c c u r a t e l y t o . 5 0 0 y v . Thus a common- mode r e j e c t i o n r a t i o o f 2 0 , 0 0 0 i s r e q u i r e d . A T e k t r o n i x t y p e 3A3 d i f f e r e n t i a l a m p l i f i e r p l u g - i n w i l l s a t i s f y t h e s e s p e c i f i c a t i o n s up t o 1 0 0 kHz. The o u t p u t o f t h e D/A c o n v e r t e r and t h e p o t e n t i o m e t e r must have v e r y l i t t l e n o i s e , s i n c e t h e o s c i l l o s c o p e d e f l e c t i o n s i g n a l s a r e v e r y s m a l l . The p o t e n t i o m e t e r must, o f c o u r s e , be a v e r y l i n e a r f u n c t i o n o f h o r i z o n t a l c a r r i a g e p o s i t i o n . A 1 2 b i t D/A c o n v e r t e r may be d i f f i c u l t t o b u i l d and keep t u n e d s i n c e t h e c u r r e n t d i v i d i n g r e s i s t o r s must be v e r y a c c u r a t e . I t s h o u l d be n o t e d f r o m e q u a t i o n A 2 . 4 t h a t a change i n t h e o p t i c a l m a g n i f i c a t i o n , m, r e q u i r e s t h a t t h e p r o d u c t K • X be s c c h a n g e d a c c o r d i n g l y . S i n c e K i s p r o p o r t i o n a l t o t h e v o l t a g e c a c r o s s t h e c a r r i a g e p o s i t i o n p o t e n t i o m e t e r , i t i s e a s i l y a d j u s t e d . A 2 . 2 D i g i t a l Method o f T r a c i n g a F u l l L i n e o f C h a r a c t e r s I f t h e above s y s t e m p r o v e s t o be u n s a t i s f a c t o r y , i t c a n be m o d i f i e d t o overcome some o f t h e d i f f i c u l t i e s m e n t i o n e d a b o v e . I n s t e a d o f s u b t r a c t i n g two a n a l o g u e s i g n a l s i n a d i f f e r e n t i a l a m p l i f i e r , t h e c a r r i a g e p o s i t i o n c o u l d be d i g i t i z e d u s i n g a l i n e a r e n c o d e r . The two d i g i t a l s i g n a l s V and X would t h e n be s u b t r a c t e d d i g i t a l l y . The c a r r i a g e p o s i t i o n s h o u l d be d i g i t i z e d t o 1 5 o r 1 6 b i t s , s i n c e X must be known more a c c u r a t e l y t h a n a t r a c i n g i n c r e m e n t . The r e s u l t o f t h e s u b t r a c t i o n o p e r a t i o n would 52 be a 9 or 10 b i t number which would be c o n v e r t e d t o an analogue d e f l e c t i o n s i g n a l . The d i g i t a l s u b t r a c t i o n has removed the problems a s s o c i a t e d w i t h t h e d i f f e r e n t i a l a m p l i f i e r . A l s o t h e D/A c o n v e r t e r r e q u i r e m e n t s have been reduced t o 10 b i t s from 12. The d i g i t a l s u b t r a c t o r has a l s o e l i m i n a t e d the problem of low s i g n a l l e v e l s . I f o p e r a t i o n i s d e s i r e d over a l a r g e range o f o p t i c a l m a g n i f i c a t i o n , m, the d i g i t a l number, X , r e p r e s e n t i n g t h e c a r r i a g e p o s i t i o n must be s c a l e d i f t h e o s c i l l o s c o p e d e f l e c t i o n i s t o t r a c k t h e c a r r i a g e m o t i o n . T h i s s c a l i n g can be a c h i e v e d by m e c h a n i c a l l y s c a l i n g the l i n e a r encoder or by d i g i t a l m u l t i p l i c a t i o n o f t h e b i n a r y number c o r r e s p o n d i n g t o t h e c a r r i a g e p o s i t i o n by a d i g i t a l s c a l e f a c t o r . F o r s m a l l changes i n m, ' t r a c k i n g can be a c h i e v e d by a d j u s t i n g K . s The analogue method f o r t r a c i n g a f u l l l i n e o f c h a r a c t e r s would c o s t $1000 t o $1200, the main c o s t b e i n g f o r the d i f f e r e n t i a l a m p l i f i e r . The d i g i t a l v e r s i o n would c o s t between $3000 and $4000, the main c o s t b e i n g f o r t h e l i n e a r encoder. APPENDIX I I I UP-DOWN COUNTER 53 The up-down c o u n t e r s u s e d i n t h e c o n t o u r - t r a c i n g s c a n n e r a r e p a r a l l e l c o u n t e r s . The t e r m p a r a l l e l i s u s e d b e c a u s e a l l o f t h e f l i p f l o p s a r e t r i g g e r e d s i m u l t a n e o u s l y . The main a d v a n t a g e o f a p a r a l l e l c o u n t e r o v e r a r i p p l e c o u n t e r i s i n t h e s p e e d o f o p e r a t i o n . An up-down r i p p l e c o u n t e r has a p r o p a g a t i o n t i m e o f a p p r o x i m a t e l y 60 n s e c p e r b i t , whereas a p a r a l l e l up- down c o u n t e r has an o v e r a l l d e l a y o f o n l y 15 t o 20 n s e c ( t h e t i m e r e q u i r e d t o complement a J-K f l i p f l o p ) . The d e c i s i o n t o complement an i n d i v i d u a l f l i p f l o p i n a p a r a l l e l up c o u n t e r i s made by n e g a t i v e l o g i c "AND" g a t e s whose o u t p u t s a r e c o n n e c t e d t o i t s J and K ( s e t and r e s e t ) t e r m i n a l s . C o n s i d e r t h e f o l l o w i n g b i n a r y s e q u e n c e f o r c o u n t i n g p u l s e s ' . i n P i g . A3-1. P u l s e Number B i n a r y Number 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 F i g . A3-1 U p - c o u n t i n g s e q u e n c e I t w i l l be ' n o t i c e d t h a t t h e l e a s t s i g n i f i c a n t b i t (LSB) complements e a c h t i m e a p u l s e a r r i v e s . The o t h e r b i t s complement on t h e p u l s e i m m e d i a t e l y f o l l o w i n g t h e t i m e when a l l t h e b i t s o f l e s s e r s i g n i f i c a n c e a r e a l l d i g i t a l o n e s . F i g , A3-2 shows a p a r a l l e l up c o u n t e r . l e a s t i s i g n i f i c a n t 1 f l i p f l o p J 1 T J-K F F K 0 + n e g a t i v e l o g i c AND g a t e \y T o g g l e R a i l J . 1 T K 0 J 1 T K 0 F i g . A3-2 P a r a l l e l up c o u n t e r . The n e g a t i v e l o g i c AND g a t e s a r e u s e d t o d e t e c t one s t a t e s d f l e s s e r s i g n i f i c a n c e . . S i n c e t h e AND g a t e s d e t e c t O's r a t h e r t h a n l ' s , t h e complement o f t h e f l i p f l o p s t a t e i s u s e d as an i n p u t . The o u t p u t o f e a c h AND g a t e i s c o n n e c t e d t o t h e J-K t e r m i n a l s o f t h e f l i p f l o p c o r r e s p o n d i n g t o t h e n e x t most s i g n i f i c a n t b i t and t o t h e i n p u t o f t h e n e x t AND g a t e . S i n c e a J-K f l i p f l o p o n l y complements when b o t h t h e J and K t e r m i n a l s a r e a t z e r o , a g i v e n f l i p f l o p i s complemented o n l y when a l l t h e f l i p f l o p s o f l e s s e r s i g n i f i c a n c e a r e i n t h e one s t a t e . A down c o u n t e r r e s u l t s i f a d e c i s i o n i s made t o complement a f l i p f l o p i f a l l t h e f l i p f l o p s o f l e s s e r s i g n i f i c a n c e a r e i n t h e z e r o s t a t e . To make an up-down c o u n t e r , a s y m e t r i c a l l y s i m i l a r s e t o f g a t e s i s added t o d e t e c t t h e o c c u r r e n c e o f l e s s e r s i g n i f i c a n t z e r o s . . S e l e c t i o n o f e i t h e r t h e c o u n t up o r c o u n t down f u n c t i o n i s a c c o m p l i s h e d by p r o v i d i n g s i g n a l s t o d i s a b l e e i t h e r t h e u p - c o u n t o r t h e down-count g a t e s as shown i n P i g . A3-3. In t h e c o n t o u r - t r a c i n g s c a n n e r , t h e r e was no r e q u i r e m e n t f o r t h e up-down c o u n t e r t o have a d i s a b l e d mode. F o r t h i s reason, t h e i n p u t AND g a t e on t h e l e a s t s i g n i f i c a n t f l i p f l o p was n o t i n c l u d e d on t h e c o u n t e r c a r d s . When t h e c o u n t e r was b u i l t and t e s t e d , i t was f o u n d t h a t t h e r e was a p r o p a g a t i o n t i m e o f a p p r o x i m a t e l y 100 n s e c t h r o u g h e a c h s t a g e o f g a t i n g . To r e d u c e t h i s p r o p a g a t i o n t i m e , t h e two i n p u t NOR g a t e s u s e d t o d r i v e t h e J-K t e r m i n a l s ' o f t h e f l i p f l o p s i n F i g . A3-3 were b u i l t f r o m d i s c r e t e components i n o r d e r t h a t speed-up c a p a c i t o r s c o u l d be u s e d . The e f f e c t o f speed-up c a p a c i t o r s was t o r e d u c e t h e p r o p a g a t i o n t i m e t o a p p r o x i m a t e l y 30 t o 40 n s e c p e r s t a g e . 56 Down R a i l I n p u t AND g a t e C M + J 1 T J-K F F K 0 + Up R a i l I J 1 T K 0 + + J 1 T K 0 l e a s t s i g n i f i c a n t f l i p f l o p Up r a i l = 1 Down r a i l = 0 Up r a i l = 0 Down r a i l = 1 Up r a i l = 1 Down r a i l = 1 Up r a i l = 0 Down r a i l = 0 c o u n t e r c o u n t s up c o u n t e r c o u n t s down c o u n t e r d i s a b l e d o p e r a t i o n n o t d e f i n e d A l l t o g g l e i n p u t s t o t h e f l i p f l o p s a r e t i e d i n p a r a l l e l and d r i v e n by a 200 n s e c p u l s e . F i g . A3-3 P a r a l l e l up-down c o u n t e r . 57 APPENDIX IV WEIGHTED-RESISTOR DIGITAL-TO-ANALOGUE CONVERSION CIRCUITRY AND ERROR ANALYSIS A 4.1 W e i g h t e d - R e s i s t o r D i g i t a l - t o - A n a l o g u e (D/A) C i r c u i t s A f t e r c o n s i d e r i n g t h e two methods o f D/A c o n v e r s i o n , t h e w e i g h t e d - r e s i s t o r t e c h n i q u e was c h o s e n o v e r t h e R-2R l a d d e r n e t w o r k [ l 4 , 1 5 ] . A w e i g h t e d - r e s i s t o r D/A c o n v e r t e r i s shown i n P i g . A4-1. D s 0 e o - « - • R. D V D s l aO D 5 a l E D sk "k :R k e k-K]- D vz ak •n-1 R n-1 sn-1 en-l-Kh D V an-1 R = 2 n 1 k R k = o , l , . . . , n - l k - n-1 3 3 3 1 :Rl Vo F i g . A4-1 W e i g h t e d - r e s i s t o r D/A c o n v e r t e r c i r c u i t , The o p e r a t i o n a l a m p l i f i e r i s u s e d t o sum t h e c u r r e n t s c o n t r i b u t e d by e a c h b r a n c h i n t h e c u r r e n t - d i v i d e r n e t w o r k . The d i o d e s D , and D , a r e c u r r e n t s w i t c h e s , w h i c h f o r c e t h e sk ak * c u r r e n t , i ^ , t o f l o w e i t h e r t o w a r d t h e o p e r a t i o n a l a m p l i f i e r o r i n t o t h e s w i t c h i n g - s i g n a l s o u r c e , e^.. I f e^ i s + 1.5 v o l t s , 58 D s k i s r e v e r s e b i a s e d , D & k i s f o r w a r d b i a s e d and t h e k t h b r a n c h c u r r e n t i s r o u t e d t o t h e o p e r a t i o n a l a m p l i f i e r . I f e k i s - 1 . 5 v o l t s , t h e b r a n c h c u r r e n t i s r o u t e d i n t o t h e s w i t c h i n g s i g n a l s o u r c e . The s i g n a l s e^ a r e d e r i v e d f r o m t h e c o r r e s p o n d i n f l i p f l o p o u t p u t s . The w e i g h t e d r e s i s t o r .D/A c i r c u i t has two m a i n a d v a n t a g e s o v e r t h e R-2R l a d d e r c i r c u i t . T h e s e a d v a n t a g e s a r e as f o l l o w s : 1 . The c u r r e n t , i ^ . , c o r r e s p o n d i n g t o t h e k^*1 b i t c a n be a d j u s t e d i n d e p e n d e n t l y f r o m t h e o t h e r b i t c u r r e n t s by a d j u s t i n g r e s i s t o r R^. 2. O n l y one h i g h l y a c c u r a t e r e f e r e n c e s u p p l y (E) and n c u r r e n t s w i t c h e s a r e n e c e s s a r y f o r t h e w e i g h t e d - r e s i s t o r D/A c o n v e r t e r whereas i n t h e R-2R l a d d e r n e t w o r k , n a c c u r a t e , s w i t c h e d v o l t a g e s o u r c e d r i v e r s a r e n e e d e d . A 4.2 S t e a d y S t a t e E r r o r s i n t h e W e i g h t e d - R e s i s t o r D/A C o n v e r t e r I n a n a l y s i n g t h e s t e a d y - s t a t e e r r o r s , t h e o p e r a t i o n a l a m p l i f i e r may be m o d e l e d as shown i n P i g . A4-2. i A W * — r 1 P i g . A4-2 O p e r a t i o n a l a m p l i f i e r model. 59 In- F i g . A4-2 Vo = - i R / ( i - K ) A 4.1a S I X R L ( R Q . y R Q R f R± y R f w h e r e K r = „ - A R f ) R T " A i-i O I 1 F o r an i d e a l o p e r a t i o n a l a m p l i f i e r , t h e open l o o p g a i n , A and t h e i n p u t r e s i s t a n c e , R ^ are" i n f i n i t e , w h i l e t h e o u t p u t r e s i s t a n c e , R i s z e r o . Thus K i s e q u a l t o z e r o . F o r a non-o r ^ i d e a l a m p l i f i e r , t h e n o n - z e r o v a l u e o f m e r e l y s c a l e s t h e o u t p u t v o l t a g e . From e q u a t i o n A 4.1a, t h e r e l a t i v e e r r o r i n t h e o u t p u t v o l t a g e c a n be c a l c u l a t e d by c o n s i d e r i n g .the e r r o r s i n t h e i n p u t c u r r e n t i . n-1 I s A 4.2a k=o R ^ = 2 n 1 k R ^ k = o ^ ^ ^ ^ . i A 4.2b F o r an i d e a l o p e r a t i o n a l a m p l i f i e r and i d e a l d i o d e s , t h e o p e r a t i o n a l a m p l i f i e r i n p u t v o l t a g e , e^; t h e f o r w a r d v o l t a g e a c r o s s t h e k s w i t c h i n g d i o d e , and t h e k d i o d e l e a k a g e c u r r e n t , i , a r e z e r o and t h e a c c u r a c y o f t h e c u r r e n t , i , 3 ok 17 • s 3 d e p e n d s o n l y on t h e a c c u r a c y o f t h e c u r r e n t d i v i d i n g r e s i s t o r s , R ^ . The p a r a m e t e r a ^ i s e i t h e r 0 o r 1 d e p e n d i n g on t h e b i n a r y number b e i n g c o n v e r t e d t o an a n a l o g u e v o l t a g e . F o r n o n - i d e a l c omponents, t h e e r r o r i n i due t o V,, , e. and i , must be * 3 . s a k 3 I ok c a l c u l a t e d . A i •sk LaR K= O k d e . o i , rii , - ^ A e . + - ^ A v H 1 + "sk dk ok ok E - V •sk = a dk k R. k 6 0 A 4 . 3 a A ' 4 . 3 b The e r r o r due t o v " d k , and t h e e r r o r due t o i Q k when = 1 need n o t be c o n s i d e r e d , s i n c e c a n be a d j u s t e d t o compensate f o r t h e s e e r r o r s . However, when a k = 0 , t h e l e a k a g e c u r r e n t d o e s p r o d u c e an e r r o r i n i The e r r o r due t o t h e r e s i s t o r t o l e r a n c e must a l s o be c a l c u l a t e d . I n o r d e r t o c a l c u l a t e t h e e r r o r i n i due t o e., an s x ' u p p e r bound on e. must be f o u n d . I n F i g . A4-2 - Ae. V o R f R o V V A V R. R R „ R r o i L R R T + R R~ + R~R T o L o f f L A 4 . 4 a A 4 . 4 b I t s h o u l d be n o t e d t h a t AR^>> R q and t h a t by t h e use o f a low impedance c u r r e n t b o o s t e r on t h e o u t p u t o f t h e o p e r a t i o n a l a m p l i f i e r , R q c a n be made much l e s s t h a n e i t h e r R^ o r R^. T h e r e f o r e R Q = R̂ .. C o n s e q u e n t l y t h e a m p l i f i e r i n p u t v o l t a g e c a n be a p p r o x i m a t e d by Vo R f 1 A A I t i s d e s i r e d t o compute t h e r a t i o o f t h e e r r o r i n i . c ii A i c a u s e d by ̂ e i , A i Q k , a n d . A R ^ ' w i t h r e s p e c t t o a l e a s t s i g n i f i c a n t b i t ( L S B ) c u r r e n t . L e t t h e m a g n i t u d e o f t h e s e A 4 . 5 6 i r e l a t i v e e r r o r s be Si. and Si 1 o Some a l g e b r a shows t h e s e e r r o r s t o be: R, r e s p e c t i v e l y . </ 2 R f AR n - 1 "o Si 4 ( 2 n - 1) R R, A 4.6 A 4.7 A 4.8 k I n e q u a t i o n A .4.8, a l l r e s i s t o r t o l e r a n c e s were assumed e q u a l . The r e s u l t shown i n e q u a t i o n A 4.6 i s i n agreement w i t h t h e r e s u l t f o u n d i n [15J ; however, i t s h o u l d be n o t e d t h a t t h e bound on Si c a n be t i g h t e n e d by an a d d i t i o n a l f a c t o r o f two i f t h e f o l l o w i n g argument i s c o n s i d e r e d . The c a l c u l a t i o n s t h a t l e d t o e q u a t i o n A 4.6 were made a s s u m i n g t h e o p e r a t i o n a l a m p l i f i e r summed o n l y c u r r e n t s f l o w i n g i n one d i r e c t i o n . I f c u r r e n t b i a s i s added t o t h e o p e r a t i o n a m p l i f i e r i n p u t t o s h i f t t h e o u t p u t v o l t a g e u n t i l i t i s s y m m e t r i c a b o u t z e r o v o l t s , t h e maximum i n p u t c u r r e n t t o t h e o p e r a t i o n a l a m p l i f i e r i s h a l v e d and t h u s e. and 1 £1 a r e h a l v e d . See e q u a t i o n A 4.5, Si y. 2 V e. s y m m e t r i c a l o u t p u t 1 . v o l t a g e s w i n g AR A 4.9 n - 1 F o r a s y m m e t r i c a l o u t p u t o f ± 10 v o l t s , a most s i g n i f i c a n t b i t (MSB) c u r r e n t o f 30 ma, E = 30 v o l t s , A = 5 x 10 , n = 12 and a maximum d i o d e l e a k a g e c u r r e n t o f 10 na f o r a r e v e r s e b i a s o f 1 v o l t bounds on t h e r e l a t i v e e r r o r s due t o e. and i were f o u n d t o be: 1 s Si 4 2>7% Prom t h e above I t c a n be s e e n t h a t f o r up t o 12 b i t s , t h e e r r o r s c a u s e d by t h e o p e r a t i o n a l a m p l i f i e r and t h e s w i t c h i n g d i o d e s i n t h e D/A c o n v e r t e r a r e e i t h e r s m a l l o r c a n be c o m p e n s a t e d f o r . Thus t h e m a i n l i m i t a t i o n t o p r o d u c i n g an a c c u r a t e D/A c o n v e r t e r f o r n ^ 12 l i e s i n t h e c u r r e n t d i v i d i n g r e s i s t o r s . S i n c e t h e o u t p u t v o l t a g e i s l i n e a r l y r e l a t e d t o i f r o m s e q u a t i o n A 4.1, t h e e r r o r i n Vo w i t h r e s p e c t t o a LSB i n o u t p u t vo l t a g e , ^ V o i s e q u a l t o i f t h e e r r o r s and a r e n e g l e c t e d . The r e l a t i v e o u t p u t v o l t a g e e r r o r OVo i s p l o t t e d a g a i n s t r e s i s t o r t o l e r a n c e f o r 2 ^ n ^ 12 i n F i g . A4-3. A 4.3 Speed L i m i t a t i o n s i n t h e W e i g h t e d - R e s i s t o r D/A C o n v e r t e r T h e r e a r e two m a i n l i m i t a t i o n s on c o n v e r s i o n s p e e d I n t h e w e i g h t e d - r e s i s t o r D/A c o n v e r t e r ; t h e s w i t c h i n g and s e t t l i n g t i m e o f t h e d i o d e s and t h e s l e w r a t e o f t h e o p e r a t i o n a l a m p l i f i e r . ' . • . .01 .02 .05 .1 .2 .5 1 2 5 10 RESISTOR TOLERANCE , M^/fy, % FIG. A 4-3 CURRENT DIVIDING RESISTOR TOLERANCE FOR WEIGHTED-RESISTOR DIGITAL -TO-ANALOGUE CONVERTERS ALL RESISTOR TOLERANCES CONSIDERED EQUAL, Vo JS THE ANALOGUE OUTPUT VOLTAGE. LSB IS THE OUTPUT VOLTAGE INCREMENT CORRESPONDING TO A CHANGE IN THE LEAST SIGNIFICANT BIT. n IS THE NUMBER OF BITS. 64 To make an e s t i m a t e o f t h e s e t t l i n g t i m e o f t h e d i o d e s , one must c o n s i d e r t h e d i o d e j u n c t i o n c a p a c i t a n c e and t h e d i o d e r e c o v e r y v-ime. The r e c o v e r y t i m e o r s w i t c h i n g t i m e o f t h e 1N4154 d i o d e c a n be c a l c u l a t e d a s shown on t h e s p e c i f i c a t i o n s h e e t on t h e 1N4154 t o be a p p r o x i m a t e l y 6 n s e c f o r 30 ma o f f o r w a r d c u r r e n t . The j u n c t i o n c a p a c i t a n c e f o r t h e 1N4154 d i o d e i s a p p r o x i m a t e l y 4 p f . The v o l t a g e a c r o s s t h e d i o d e o n l y c h a n g e s by 1.5 v o l t s , so t h e j u n c t i o n c a p a c i t a n c e c a n be c o n s i d e r e d t o be c h a r g e d by a c o n s t a n t c u r r e n t s o u r c e . The w o r s t c a s e w i l l o c c u r on t h e LSB, s i n c e t h e c h a r g i n g c u r r e n t i s s m a l l e s t i n t h i s c a s e . F o r n = 10, and a MSB c u r r e n t o f 30 ma, t h e LSB c u r r e n t i s 60 ua. The c h a r g i n g t i m e t i s c t - — • = 100 n s e c . c i The j u n c t i o n c a p a c i t a n c e i s d i s c h a r g e d t h r o u g h t h e low f o r w a r d r e s i s t a n c e o f a c o n d u c t i n g d i o d e , w h i c h i s a p p r o x i m a t e l y 7.5K a t a f o r w a r d c u r r e n t o f 60 ua. The t i m e c o n s t a n t i s a p p r o x i m a t e l y —12 3 4 x 10 ( 7 . 5 x 10 ) = 30 n s e c . The j u n c t i o n c a p a c i t a n c e c a n be c o n s i d e r e d f u l l y c h a r g e d a f t e r 150 n s e c (5 t i m e c o n s t a n t s ) . Thus f o r a 10 b i t D/A c o n v e r t e r , o p e r a t i o n a t a 1 MHz r a t e seems q u i t e r e a s o n a b l e f r o m c o n s i d e r a t i o n , o f s w i t c h i n g and s e t t l i n g t i m e o f t h e d i o d e s . The s l e w r a t e o f t h e o p e r a t i o n a m p l i f i e r l i m i t s t h e maximum r a t e o f change o f t h e o u t p u t v o l t a g e , Vo. T h e r e w i l l be t r a n s i e n t s i n i t i a t e d by e a c h change i n t h e d i g i t a l number, however t h e p r o p e r a p p l i a c t i o n o f a s m a l l c a p a c i t o r a c r o s s t h e f e e d b a c k r e s i s t o r w i l l r e d u c e t h e s e t r a n s i e n t s t o an a c c e p t a b l e l e v e l . 65 A 4.4 R e s i s t o r T r i m m i n g C i r c u i t r y T h e r e was an im m e d i a t e need f o r an 8 b i t D/A c o n v e r t e r w i t h an a c c u r a c y o f a t l e a s t 1/2 LSB ( <*>Vo ̂  1/2) f o r a n o t h e r p r o j e c t a s w e l l a s f o r a 6 b i t D/A c o n v e r t e r f o r t h e c o n t o u r - t r a c i n g s c a n n e r . Thus an 8 b i t D/A c o n v e r t e r w i t h an a c c u r a c y o f 1/4 LSB ( S V o ^ 1/4) was d e s i g n e d . Prom F i g . A4 - 3 , i t i s se e n t h a t a r e s i s t o r a c c u r a c y o f .1% i s r e q u i r e d . The c o n f i g u r a t i o n shown i n F i g . A4-5 was u s e d t o c o n s t r u c t a r e s i s t o r a c c u r a t e t o .1% f r o m i n e x p e n s i v e components. (N+M)R (N+M+l) F i g . A4-4 C i r c u i t f o r a d j u s t i n g R^ t o t h e r e q u i r e d a c c u r a c y To a c h i e v e a t e m p e r a t u r e s t a b i l i t y w h i c h e x c e e d s t h a t o f t h e o r d i n a r y r e s i s t o r s , a 1% r e s i s t o r was u s e d f o r t h e r e s i s t o r R. The c o n f i g u r a t i o n shown i n F i g . A4-4 has c e r t a i n a d v a n t a g e s o v e r a s e r i e s c o m b i n a t i o n o f a 1% r e s i s t o r and a s m a l l t r i m m i n g r e s i s t o r . The p a r a l l e l c o n f i g u r a t i o n m i n i m i z e s t h e i n d u c t i v e e f f e c t o f a p o t e n t i o m e t e r , s i n c e l e s s t h a n 10$ o f t h e c u r r e n t p a s s e s t h r o u g h i t . I f more a d j u s t m e n t i s r e q u i r e d 66 on a g i v e n r e s i s t o r , t h e r e s i s t o r NR c a n be c h a n g e d t o g i v e t h e d e s i r e d a d j u s t m e n t w i t h o u t t h e n e c e s s i t y o f c h a n g i n g a 1% r e s i s t o r . I f R,p i s t h e combined r e s i s t a n c e o f t h e t h r e e r e s i s t o r s , t h e n (N + Mmax) R . ,. , A R T m a x = (N + Mmax + 1) • ' I'D R T m i n = ™ ' A 4.11 . Rrpinax - R^.min Mmax A 4 12 R^ ^ "(N + 1) (N + Mmax) where R Tmax and Mmax a r e t h e maximum v a l u e s o f R T and M r e s p e c t i v e l y . I f M c a n be s e t t o an a c c u r a c y o f AM, t h e n t h e maximum a c c u r a c y t h a t R T c a n be s e t t o i s A R T A M A 4.13 R T (N + M) (N + M + 1) The w o r s t c a s e o c c u r s when M = 0. T h e r e f o r e , •^ R T / • A M A 4.14 Rrp - N(N + 1) I f Mmax - N = 10, and i f M i s a d j u s t a b l e t o 1% "(A M = .1) t h e n A Rrp/Rrp - .1% B.S r e q u i r e d . I t f o l l o w s f r o m e q u a t i o n A 4.12 t h a t t h e t o t a l r a n g e o f a d j u s t m e n t o f R̂ , i s a p p r o x i m a t e l y 5$. I f t h e MSB c u r r e n t , i n _ ^ > 1 S 15 ma then, t h e s w i t c h i n g d i o d e v o l t a g e d r o p s c a n be mea s u r e d t o d e t e r m i n e t h e c o m p e n s a t i o n r e q u i r e d i n t h e r e s i s t o r s R^. One s u c h measurement gave a r a n g e i n v o l t a g e d r o p s v a r y i n g f r o m .73 v o l t s a t 1^ = 15 ma t o .48 v o l t s a t I f = 120 ua. F o r a r e f e r e n c e v o l t a g e 67 (E) o f 30 v o l t S j t h e e r r o r due t o t h e d i o d e d r o p s v a r i e s f r o m 2.4$ t o 1,655. S i n c e t h e r a n g e o f a d j u s t m e n t on t h e r e s i s t o r s i n t h e n e t w o r k i s a p p r o x i m a t e l y 5%, a l l t h e r e s i s t o r s R k were c a l c u l a t e d t o be a p p r o x i m a t e l y 2% loy t o compensate f o r t h e e r r o r due t o t h e f o r w a r d d r o p a c r o s s t h e d i o d e s . P i g . A4-5 shows t h e s e t o f r e s i s t a n c e v a l u e s c h o s e n f o r t h e 8 b i t D/A c o n v e r t e r . N o m i n a l R e s i s t a n c e Rj OHMS R ( l * ) OHMS MmaxR OHMS NR OHMS Range o f A d j u s t m e n t o f R T 2K 2.1 K 22K 18K 5.5% 4K 4.12K 47K 33K .6.335 8K 8 .25K 100K 68K .6.3? 16K 17.4 K 100K 120K 5.3% 32K 34.0 K 220K 270K •M.7% 64K 68.1 K 470K 470K 6 % 128K 133 K 1 meg.. 1.2 meg. 4.4$ 256K 267 K 2.2 meg. 2.2 meg. •5.1% A4-5 R e s i s t a n c e v a l u e s f o r a w e i g h t e d - r e s i s t o r 8 D/A c o n v e r t e r b i t I f more r e s o l u t i o n i s r e q u i r e d f o r r e s i s t o r s R^ , t h e r e s o l u t i o n on t h e t r i m m i n g p o t e n t i o m e t e r MR may be i n c r e a s e d , o r t h e r a n g e o f a d j u s t m e n t may be d e c r e a s e d o r a c o m b i n a t i o n o f b o t h may be u s e d . 68 A 4 . 5 D/A C u r r e n t - S w i t c h D r i v e r C i r c u i t s The D/A c o n v e r t e r must t a k e t h e s i g n a l s f r o m t h e b i n a r y number s o u r c e and c o n v e r t them t o s u i t a b l e c u r r e n t s w i t c h i n g s i g n a l s o f ± 1 .5 v o l t s . C o n s i d e r t h e c i r c u i t i n P i g . A 4 - 6 . +3.6 v T r a n s i s t o r s a r e 2 N 3 6 4 6 +1.5 v - 1 . 5 v - 6 v P i g . A4 - 6 C u r r e n t - s w i t c h d r i v e r c i r c u i t S i n c e t h e k t h d r i v e r must be c a p a b l e o f a c c e p t i n g t h e c u r r e n t i ^ f r o m t h e k^*1 b r a n c h o f t h e c u r r e n t d i v i d e r , t h e r e s i s t o r Re must be a d j u s t e d on t h e most s i g n i f i c a n t d r i v e r s t o be a b l e t o a c c e p t t h i s c u r r e n t . F o r c u r r e n t s i ^ l e s s t h a n o r e q u a l t o . .7.5 ma, Re = 4 7 0 D i s a d e q u a t e . F o r h i g h e r c u r r e n t s , Re must be r e d u c e d . 6 9 APPENDIX V DESIGN OF THE OPTICS SYSTEM A 5.1 C o n t o u r - T r a c i n g S c a n n e r O p t i c a l R e q u i r e m e n t s The f u n c t i o n o f t h e o p t i c s s y s t e m i s t o f o c u s t h e s p o t o f l i g h t f r o m t h e CRT o n t o t h e p a g e . I f t h e s i z e o f an a v e r a g e c h a r a c t e r i s a b o u t 2 mm s q u a r e , and i f a p p r o x i m a t e l y 30 i n c r e m e n t a r e r e q u i r e d i n e a c h d i m e n s i o n , t h e n a s p o t o f l i g h t o f a b o u t .06 mm d i a m e t e r i s r e q u i r e d on t h e page. The s p o t s i z e on t h e CRT i s a p p r o x i m a t e l y .6 mm i n d i a m e t e r ( t h e d i a m e t e r v a r i e s w i t h t h e i n t e n s i t y s e t t i n g ) , t h e r e f o r e , a s i z e r e d u c t i o n by a f a c t o r o f 10 i s r e q u i r e d . S i n c e a p h o t o m u l t i p l i e r (PM) w i l l be u s e d t o c o l l e c t t h e l i g h t r e f l e c t e d f r o m t h e p a g e , t h e r e must be enough room between t h e l e n s and t h e page t o e n a b l e t h e PM t o • be p l a c e d so t h a t t h e l i g h t w i l l be c o l l e c t e d a t as s m a l l an a n g l e o f r e f l e c t i o n as p o s s i b l e and as c l o s e t o t h e page as i s p r a c t i c a l . The o p t i c a l s y s t e m s h o u l d be d e s i g n e d t o g a t h e r t h e maximum amount o f l i g h t c o n s i s t e n t w i t h low o p t i c a l d i s t o r t i o n , r e a s o n a b l e c o s t , and a v a i l a b i l i t y o f o p t i c a l c omponents. A 55 mm f / 1 . 8 Super-Takumar A s a h i P e n t a x camera l e n s was p u r c h a s e d t o do some t e s t s on g a t h e r i n g l i g h t f r o m a page u s i n g a RCA 931A p h o t o m u l t i p l i e r . The P e n t a x l e n s gave t h e r e q u i r e d d e f i n i t i o n and w o r k i n g d i s t a n c e ( d i s t a n c e between t h e page and l e n s ) f o r t h e 931A PM. The t e s t s showed, however, t h a t a much more s e n s i t i v e PM was r e q u i r e d . As a r e s u l t , a P h i l l i p s 53AVP was o r d e r e d . The 53AVP however, i s a l a r g e r t u b e and r e q u i r e s g r e a t e r w o r k i n g d i s t a n c e . The w o r k i n g d i s t a n c e r e q u i r e d f o r t h e 70 53AVP was c a l c u l a t e d g r a p h i c a l l y t o be 3 i n c h e s . T h i s i n c r e a s e i n r e q u i r e d w o r k i n g d i s t a n c e c a u s e s a change i n o p t i c s d e s i g n . Some p r e l i m i n a r y c a l c u l a t i o n s b a s e d on t h e t h i n l e n s a p p r o x i m a t i o n showed t h a t f o r a w o r k i n g d i s t a n c e o f 3 i n c h e s ( i n a t h i n l e n s , t h e w o r k i n g d i s t a n c e and t h e image d i s t a n c e a r e t h e same) and a m a g n i f i c a t i o n o f - . 1 , t h e o b j e c t d i s t a n c e was 30 i n c h e s and t h e f o c a l l e n g t h 6.9 cm. I f a u s e a b l e l e n s d i a m e t e r o f 1.5 i n c h e s i s assumed, t h e n t h e o p t i c a l s y s t e m i n p u t s o l i d a n g l e o f l i g h t c a n be c a l c u l a t e d t o be 1.9 x 10 s t e r a d i a n s . I n v i e w o f t h e l o n g l e n g t h r e q u i r e d , t h e l i g h t g a t h e r i n g a b i l i t y and t h e d i s t o r t i o n e x p e c t e d i n a s i m p l e t h i n l e n s o p t i c a l s y s t e m , i t was d e c i d e d t o i n v e s t i g a t e a t h i c k l e n s o p t i c a l s y s t e m . A 5.2 R e s u l t s o f t h e T h i c k L e n s O p t i c s I n v e s t i g a t i o n A s t u d y o f t h i c k l e n s o p t i c a l s y s t e m s [io] r e v e a l e d t h a t i t was p o s s i b l e t o use t h e P e n t a x l e n s i n a m o d i f i e d c o n f i g u r a - t i o n t o y i e l d a s h o r t e r o p t i c a l s y s t e m w i t h t h e r e q u i r e d w o r k i n g d i s t a n c e . B r i e f l y - , t h i s was a c h i e v e d as f o l l o w s . The l o c a t i o n s o f t h e p r i n c i p l e p l a n e s , P 2 and P £ , i n t h e P e n t a x l e n s were f o u n d u s i n g an o p t i c a l b e n c h . I t was f o u n d t h a t i f a d i v e r g i n g l e n s was u s e d i n f r o n t o f t h e P e n t a x l e n s , t h e image s p a c e p r i n c i p l e p l a n e ( l o c a t e d a t P') f o r t h e o v e r a l l o p t i c a l s y s t e m c o u l d be f o r c e d o u t s i d e t h e l e n s and t o w a r d t h e image p l a n e . See P i g . A5-1. a c t u a l P e n t a x l e n s \ ^ P r i n c i p l e p l a n e s - o f m o d i f y i n g l e n s Image F i g . A5-1 S c a n n e r o p t i c a l s y s t e m . S i n c e s' i s m e asured f r o m . P 1 , s' may be d e c r e a s e d w i t h o u t d e c r e a s i n g W, t h e w o r k i n g d i s t a n c e , p r o v i d e d P' i s f o r c e d c l o s e r t o t h e image p l a n e . I t was n e c e s s a r y t o c a l c u l a t e t h e r e q u i r e d f o c a l l e n g t h , f | o f t h e d i v e r g i n g l e n s and t h e s e p a r a t i o n d i s t a n c e , d, between t h e P e n t a x l e n s and t h e d i v e r g i n g l e n s . A p p r o p r i a t e e q u a t i o n s were d e r i v e d and s o l v e d y i e l d i n g t h e o p t i c a l s y s t e m shown i n F i g . A5 - 2 . \ 5.69 cm To o b j e c t < . P. AP 3.o A P To image d f 1 •- W = f i = 1 8.49 cm 3.7 cm 7.62 cm (3 i n c h e s ) - 6 . 1 cm r 2 r 5.14 cm f ' s s' 5.5 cm 40.7 cm 4.07 cm F i g . A5-2 F i n a l o p t i c a l s y s t e m d e s i g n . 72 The o v e r a l l f o c a l l e n g t h , f was c a l c u l a t e d t o be 3 . 7 cm and t h e i n p u t s o l i d a n g l e o f l i g h t t o t h e o p t i c a l s y s t e m was -3 f o u n d t o be 1 .32 x 10 J s t e r a d i a n s . F o r an image d i s t a n c e o f 4.07 cm, t h e w o r k i n g d i s t a n c e was f o u n d t o be 7 . 6 2 cm o r 3 i n c h e s . • . To a l l o w f o r s m a l l a d j u s t m e n t s i n t h e m a g n i f i c a t i o n and t o e x c l u d e e x t r a n e o u s l i g h t , a t e l e s c o p e a d j u s t a b l e i n l e n g t h was b u i l t t o h o l d t h e l e n s . The m a g n i f i c a t i o n was made a d j u s t a b l e f r o m - . 0 9 2 t o - . 1 1 . 73 APPENDIX V I THE SYSTEM BLOCK DIAGRAM - The o v e r a l l b l o c k d i a g r a m o f t h e c o n t o u r - t r a c i n g s c a n n e r i s p r e s e n t e d i n P i g s . A6-2 and A6-3. The symbols u s e d i n t h e b l o c k d i a g r a m s a r e d e f i n e d i n F i g . A6-1. OR g a t e I n v e r t e r B u f f e r AND g a t e -f- p — NOR g a t e I n v e r t e r R e s e t Count o f T h r e e Complemented E x c l u s i v e OR g a t e M o n o s t a b l e M u l t i v i b r a t o r ( p o s i t i v e p u l s e o u t p u t ) NAND g a t e — J R 1 T J-K F F K - 0 J-K f l i p f l o p — s 1 S-R F F R 0 S e t - R e s e t f l i p f l o p A t w o - b i t c o u n t e r w i t h a p p r o p r i a t e g a t e s on t h e o u t p u t t o d e t e c t t h e c o u n t o f t h r e e . F i g . A6-1 D e f i n i t i o n o f sy m b o l s and t e r m i n o l o g y . store pulse (modt 1 to 2 pulse) Y reset Y START REGISTER Y reset pulse to system control logic _ Y most significant Y UP-DOWN COUNTER external pulse external/ internal sw/ten, stop switch CLOCK clock 1 clock 2 mode 1/2 mode 2to1 pulse . X up-down X toggle X reset store pulse X UP-DOWN COUNTER (mode 1 to 2 pulse) X reset X START REGISTER Xmax toggle XMAX COUNTER P = 0 black spot. P = 1 white spot DIGITAL mode 1/2 '0, COMPARISON A A = 1 if inputs identical mode 1/2 = 1. GATES D/A CONVERTER • mode 1/2 D/A CONVERTER Y analogue signal PHOTOMULTIPLIER X analogue signal A • B- DIGITAL B COMPARISON GATES c - X toggle X up-down reset switch search switch DIGITAL • COMPARISON C GATES trace switch clock 2 Y reset pulse PAGE OPTICS . SYSTEM CONTROL LOGIC mode 1/2 •mode 1/2 Xmax toggle mode I to 2 pulse mode 2 to I pulse A, B, X reset Y reset FIG. A6- 2 SYSTEM BLOCK DIAGRAM -Cr 75 mode 1/2 P, clock mode 1/2 toggle pulse -H 4 - Y v l » - MONO —— MONO mode 2to1 pulse MONO MONO toggle pulse COUNT OF THREE reset reset COUNT OF THREE A, B, mode 2 tot pulse reset 1 COUNT OF 9R S-R S THREE FF 1 0 + 3.6v count of 3 I X reset (0 if count of 3) reset switch 1 Y reset y reset +3.6v pulse P = 0 black spot P = 1 white spot mode 1/2 = 0. search mode (mode 1) mode 1/2 - 1. trace mode (mode 2) trace switch 1 " -t +3.6v search switch c4 count of 3,^7y S-R FF 1 0 X toggle^ X up down ^ ^ 7 ^ 0 Xmax toggle mode 1/2 tol mode 1/2 FIG. A6-3 SYSTEM CONTROL LOGIC 76 REFERENCES SIMEK, J.G. and C . J . TUNIS, " H a n d p r i n t i n g I n p u t D e v i c e , f o r Computer S y s t e m s " , I E E E S p e c t r u m , pp. 7 2 - 8 1 , J u l y , 1967. WILSON, R.A., O p t i c a l Page R e a d i n g D e v i c e s , R e i n h o l d , New Y o r k , 1966. FISCHER, G.L., e t a l , 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 , S p a r t a n B o o k s , W a s h i n g t o n , D . C , 1 9 6 2 . L I U , C.N. and G.L. SHELTON, "An E x p e r i m e n t a l I n v e s t i g a t i o n o f a M i x e d - F o n t P r i n t R e c o g n i t i o n S y s t e m " , I E E E T r a n s a c t i o n s - on E l e c t r o n i c C o m p u t e r s , v o l . EC-15, no. 6 , pp. 9 1 6 - 9 2 5 , December, 1 9 6 6 . CLEMENS, J.K., " 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 M a c h i n e A p p l i c a t i o n s " , PhD T h e s i s M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , September, 1 9 6 5 . CLEMENS, J.K., " 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 M a c h i n e A p p l i c a t i o n s " , Q u a r t e r l y P r o g r e s s R e p o r t , R e s e a r c h L a b o r a t o r y o f E l e c t r o n i c s , C a m b r i d g e , M a s s a c h u s e t t s , no. -79 > O c t o b e r 1 5 , 1 9 6 5 , pp. 2 1 9 - 2 2 7 . LINDGREN, N., "Machine R e c o g n i t i o n o f Human L a n g u a g e , P a r t I I I - C u r s i v e S c r i p t R e c o g n i t i o n " , I E E E S p e c t r u m , pp. 104- 116 , May, 1 9 6 5 . EDEN, M., " H a n d w r i t i n g and P a t t e r n R e c o g n i t i o n " , IRE T r a n s a c t i o n s , I n f o r m a t i o n T h e o r y , pp. 1 6 0 - 1 6 6 , F e b r u a r y , 1 9 6 2 . LEIMER, J . J . , " D e s i g n - f a c t o r s i n t h e De v e l o p m e n t o f 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 M a c h i n e " , IRE T r a n s a c t i o n s , I n f o r m a t i o n T h e o r y , pp. 1 6 7 - 1 7 1 , F e b r u a r y , 1 9 6 2 . LONGHURST, R.S., G e o m e t r i c a l and P h y s i c a l O p t i c s , Longmans, G r e e n and Co. L t d ~ 1 9 6 4 , L o n d o n , pp. 1-40. P e r s o n a l c o r r e s p o n d e n c e ' t o H. C. B o r d e n , F a i r c h i l d S e m i c o n d u c t o r , M o u n t a i n v i e w , C a l i f o r n i a , J u l y , 1 9 6 6 . P e r s o n a l c o r r e s p o n d e n c e t o W.B. B a r n e s , S t a n d a r d Memories I n c . , S a n t a Ana, C a l i f o r n i a , J u n e , 1967• BROWN, J ' . C , " R e s o l u t i o n o f F l y i n g Spot S c a n n e r s " , I E E E S p e c t r u m , pp. 7 3 - 7 8 , A u g u s t , 1967 . 77 14. DONALDSON, R.W. and D. CHAN, " C a l c u l a t i o n o f S t e a d y S t a t e E r r o r s i n D i g i t a l - t o - A n a l o g u e L a d d e r C o n v e r t e r s " , I E E E l e c t r o n i c s L e t t e r s , v o l . 3 , no. 5, pp. 2 0 8 - 2 0 9 , May, 1 9 6 7 . 15. DONALL'SON, R.W., " S e n s i t i v i t y A n a l y s i s o f a D i g i t a l - b y - A n a l o g u e M u l t i p l i e r and a W e i g h t e d R e s i s t o r D i g i t a l - t o - A n a l o g u e C o n v e r t e r " , I E E E l e c t r o n i c s L e t t e r s , v o l . 3 , no. 1 0 , pp. 4 4 7-448, O c t o b e r , 1 9 6 7 .

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 8 13
Japan 7 0
France 2 0
United States 2 1
City Views Downloads
Beijing 8 0
Tokyo 7 0
Unknown 3 0
Ashburn 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}

Share

Share to:

Comment

Related Items