Patent GB-837341-A (GB)
Title: Improvements in form recognition system
IPC: G06V10/75
Filed: 1957-10-24
Abstract: 837,341. Automatic recognition of characters or other curves. GENERAL ELECTRIC CO. Oct. 24, 1957 [Oct. 26, 1956], No. 33225/57. Class 106 (1). Apparatus for recognizing an unknown curve has means for following the path of the curve and deriving voltages corresponding to coordinate values, a computer producing from these voltages at least one property of the curve which is independent, except possibly for a constant additive term, of its position, orientation or magnification, and a comparator for comparing the values of the same property computed from at least one known curve, a recognition being indicated when the values for the two curves have a predetermined relationship to each other. The properties selected as invariants, except for a constant term in the latter, are (1) the rate of change of radius of curvature with respect to arc length, and (2) the logarithm of the radius of curvature at various points. (1) ... u = dR/ds (2) ... v = Log R(s) These are shown in Fig. 1 in respect of a standard known curve (a) and an unknown curve (b). Property u is invariant. The second property v is invariant under the transformations of translation and orientation but a constant term is added when the curve is magnified, since the radius of curvature is doubled when the scale is doubled and the value v is increased accordingly by the logarithm of two. This term is shown in Fig. 1 (d) as a value log M added to the curve (4), Fig. 1 (c). Fig. 2 shows the method of scanning the curve (3). A television-type raster covering the whole area 10 could be used but a curve follower is to be preferred of the kind disclosed in Specification 670,143 in which a photo-electric head follows a closed curve and controls the work-table of a machine tool. This apparatus is modified by causing the " x " and " y " lead screws to control the wiper arms of potentiometers. Voltages are therefore developed representing the x and y co-ordinates of the curve (3). These voltages developed in block 11, Fig. 2, pass to a circuit 12 adapted to compute dR/ds and log R(s) which values are applied to a comparator 13 together with standard values of the same functions or properties of various known curves transmitted from store 14. When there is agreement an indication is given on indicator 15. This may be a bank of indicator lamps. Computor circuit 12.-The co-ordinates of the curve represented by voltage analogues x<SP>1</SP> and y<SP>1</SP> are applied to switches 21, 22, Fig. 4. When the scanner is initially set at any arbitrary point on the curve switches 21, 22 apply the corresponding x<SP>1</SP> and y' voltages to storage elements 23, 24. These may be servo-controlled potentiometers which set themselves to retain the initial x<SP>1</SP> and y<SP>1</SP> values and are immobilized when the switches 21, 22 open. Otherwise condensers could be used. When the initial values have been entered, the scanning cycle round the curve begins and the switches now apply the new values of x<SP>1</SP> and y<SP>1</SP> to amplitude comparators 25, 26 which also receive the initial values from stores 23, 24. These may be differential relays driven by balanced D.C. amplifiers and are each arranged to emit a pulse when the two inputs are the same. Therefore, whenever the applied x<SP>1</SP> and y<SP>1</SP> voltages cross the initial level, pulses are produced which pass to coincidence circuit 27, an output pulse from which indicates that one complete scan of the curve has been made. During a scan the x<SP>1</SP> and y<SP>1</SP> voltages are also applied to an analogue computer loop which works out the total arc length s<SP>1</SP> round the perimeter of the curve. The loop includes differentiators 29, 30 producing signals representing the rate of change of the input voltages dx<SP>1</SP>/dt and dy<SP>1</SP>/dt which derivatives are squared by units 31, 32 and added in adder 33. The square root of this sum, found by unit 34, gives the rate of change of s<SP>1</SP>, i.e. ds<SP>1</SP>/dt. The signal is applied to integrator 35 the output of which at any instant represents the total arc length s<SP>1</SP> so far traced by the curve follower. This is passed to a sampler 36 which is normally closed but opens on receipt of a coincidence pulse from circuit 27, indicating that a complete scan has been made, to allow the output of the integrator 35, representing the complete arc length, to pass to unit 37 which divides the length by 100 to determine a convenient value #s<SP>1</SP> to be used as a sampling interval in the next scan round the curve. This value is retained in a store 38 and is applied to one input to a comparator 39 of the kind emitting a pulse when the two input values are the same. A pulse from circuit 27 also passes to delay element 40, the delayed pulse opening a gate 41. This gate stays open until reset by a signal from a counter 44. On the second scan therefore the output s<SP>1</SP> of the integrator is applied to the other input of comparator 39 which emits a pulse whenever s<SP>1</SP> becomes equal to #s<SP>1</SP>. The end-of-scan pulse from circuit 27 also passes to unit 43 to reset the integrator 35 to zero and to counter 44 which emits a resetting pulse on completion of the second scan. The comparator emits a pulse on to the output line L from gate 27 whenever the integrator output equals the value #s<SP>1</SP> stored in store 38. These pulses also pass to unit 43 and counter 44, there being 100 pulses during the second scan. The counter after counting 101 pulses emits a pulse to mark the end of the second scan, which closes gate 41 and may also be used to feed the next character or curve into the sensing position. Pulses on line L also pass to sampling circuits 45, 46 to which the x<SP>1</SP> and y<SP>1</SP> voltages are applied. The analogue values at each step #s<SP>1</SP> are applied to analogue-to-digital converters 47, 48 having for example a binary coded output. Numbers representing the x<SP>1</SP> and y<SP>1</SP> co-ordinates at each step are applied in succession to subtractors 49, 50 which determine the first differences between consecutive values #x<SP>1</SP> = x<SP>1</SP> n - (x<SP>1</SP> n  -  1 ) and #y<SP>1</SP>= y<SP>1</SP> n - (y<SP>1</SP> n  -1 ).Since these values refer to points spaced apart by equal arc lengths #s<SP>1</SP> they may be taken as first derivatives of x<SP>1</SP> and y<SP>1</SP> with respect to arc length s<SP>1</SP>, i.e. #x<SP>1</SP> = dx<SP>1</SP>/ds<SP>1</SP>; #y<SP>1</SP> = dy<SP>1</SP>/ds<SP>1</SP>. These values are entered into a store e.g. a magnetic drum with address track 51 and storage tracks 53, 54, 57, 58. The first difference values are read out and subtracted in units 55, 56 from succeeding values to give the second differences representing the second differentials, e.g. d<SP>2</SP>x<SP>1</SP>/ds<SP>12</SP>. These are recorded in tracks 57, 58 and read out to squaring circuits 59, 60, an adder 61 and a unit 62 which takes the square root of the sum of the two squares. This represents the curvature of the curve as a function of arc length, k(s<SP>1</SP>). The reciprocal of this value taken by divider 63 corresponds to radius of curvature R(s<SP>1</SP>) and is entered in store 64. Successive consecutive values are subtracted in unit 65 to give first differences, i.e. 100 values for u<SP>1</SP> = dR<SP>1</SP>/ds<SP>1</SP>. Values of R(s<SP>1</SP>) also pass to unit 66 which finds the log of these values using for example stored tables. The output is therefore v<SP>1</SP> = log R<SP>1</SP>(s<SP>1</SP>). These values are entered into stores 67, 68, Fig. 5. A sequencing unit 69 selects the smallest value of v<SP>1</SP> having the smallest corresponding value of u<SP>1</SP> i.e. to start at the point on curve 5, Fig. 1, nearest the origin. These smallest values pass to stores 71, 72 subsequent pairs of values being read out in ascending order and stored, there then being 100 pairs of values in stores 71, 72. The corresponding values of the standard curves are stored in a similar ascending sequence in store 14. The smallest value of log R(s) from store 14 is subtracted in unit 73 from the smallest value of log R<SP>1</SP>(s<SP>1</SP>) from store 72. The difference is the constant additive term log M representing the magnification factor. It passes to magnification indicator 74 which may find the antilogarithm and display the value. The value of log M from subtractor 73 is also subtracted by unit 75 from all stored values of log R<SP>1</SP>(s<SP>1</SP>) and the remainders entered in store 76. The pairs of values dR<SP>1</SP>/ds<SP>1</SP> from store 71 and (log R<SP>1</SP>(s<SP>1</SP>)- log M) from store 76 are applied in turn to comparator 13 with corresponding pairs from the store 14. When all values coincide in the sequence of 100 pairs a recognition indicator 15 is caused to determine from the address track 51, Fig. 4, which of the known curves corresponds to the unknown curve. The possibility of using other invariant properties of the curve is considered and a system described using dR/ds and cos I 1 (s), where I 1  is the angle between tangents drawn to two points on the curve. These values having been derived are applied to the plates of a cathode-ray tube and the curve shape produced is optically compared with a standard by means of a stencil. In this method several tubes each with stencils may compare the derived curve simultaneously with several standard curves, an output being produced where identity is found.