Patent GB-1516220-A (GB)
Title: Apparatus for verifying a signature
IPC: G06K9/00
Filed: 1976-02-27
Abstract: 1516220 Signature verification INTERNATIONAL BUSINESS MACHINES CORP 27 Feb 1976 [4 March 1975] 07743/76 Heading G4R A signature is verified by comparing acceleration signals representing movement of, e.g. a pen with stored acceleration signals derived when forming reference signatures and determining the correlation between the two sets of signals. As described a sequence of second derivative values are calculated from the position of the pen and stored, together with a list of pen lift pointers. The maximum second derivative is determined and all second derivative signals are reduced to + 1, - 1 or 0 by comparison with a quarter of this maximum value to produce a "clipped" list. Segment lists are then derived using the pen lift pointer list. From the segment list, by comparison with the segment lists of stored reference signatures revised segment lists are formed by inserting a break point if one of the segment lists has considerably more samples than the other segment list. A mathematical mean Maj is calculated for each segment j of the form where a i  is the ith element in the segment and N j  is the number of samples in the segment. The verification is effected in a correlator to which the values in the clipped lists, the revised segment lists and the mean segment lists are fed. Derivation of second derivatives (Figs. 2A-D, not shown). Initially a counter (counter E) is loaded with a start address at which pen list pointers are to be stored. During each cycle of signals (SD) a counter (A) is incremented and if the pen is lifted during that cycle the contents of this counter are stored at the address pointed to by the first counter (E) which is then incremented. Each new sample of the pen position during an input signature, digitized in an A/D converter (126) is stored in a register (register 3), the immediately preceeding samples being in registers (2, 1) and in each cycle an arithmetic unit (202) computes the acceleration signal y n+2 -2y n+1  + y n  and stores it in a further register (4), this result being then stored in main memory at an address determined by the contents of counter A. The contents of the registers (3, 2) are then transferred to registers (2, 1) and the process repeated. Derivation of maximum second derivative (Figs. 3A-B, not shown). Initially the contents of counter (A) are set to their initial position and fed to address register (MAR) for the main memory. The acceleration value consequently read out is stored in register (1), compared in comparator (278) with the contents of register (3) initially set to zero. If the contents of register (1) are larger a gate (156) is enabled to transfer these contents to register (3). The counter (A) is then incremented and the process repeated so that the maximum stored acceleration value is finally held in register (3). Derivation of clipped lists (Figs. 4A-4C, not shown). The maximum contents in the register (3) are shifted right two places to divide them by four and the counter (A), first set to its initial value, is successively incremented and used to address the memory to read out the acceleration values for comparison with the divided maximum value by comparator (278). A "1" is stored if the read-out value is greater than the divided value and a "0" otherwise at an address determined by the contents of a counter (C) set to an initial value and incremented at each comparator. Derivation of segment list (Figs. 5A-5C, not shown). Since the number of samples between successive pen lists is represented by the difference between the values of counter (A) stored at successive addresses pointed to by the counter (E) each stored value is fed to register (1) subtracted in subtractor (428) from the preceding value in register (3) and the result stored in register (2) from which it is read into the main memory at an address indicated by a counter (I), the counter (I) being incremented and the contents of register (1) being transferred to register (3) before the next stored value is read out by incrementing counter (E). Derivation of revised segment lists (Figs. 6A-6G, not shown). If the number of samples in the first segments of the reference and segment lists differs by more than 100, the larger segment is divided into two. Corresponding values of segment length for the reference and sample signatures are read out from main memory by counters (H, I) to registers (1, 3) and compared by comparator (278) to set a latch (528) if the reference signal is larger than the sample segment. Subtractor (428) determines the difference in the two values and feeds the result to register (2). Comparator (278) then compares the contents of register (2) with the contents of register (4) which is set to 100. If the difference is greater than 100 an updating sequence is initiated in which in dependence on the setting of the latch (528) (what follows is not as stated in the specification), the smaller of the two values is stored at the address pointed to by the other counter, that counter is incremented and the contents at that address are temporarily stored in register (3), the output of the subtractor (i.e. contents of register (2)) being stored at this address. The contents of register (3) are then transferred to register (2), the same counter is again incremented and the memory contents at this address temporarily stored in register (3) &c. In this way a segment in the list of reference and sample values which exceeds the corresponding segment in the other list by more than 100 is replaced by two segments, one of the same length as the shorter segment and a second of the length equal to difference between the two segments, all segments in the list then being shifted down by one and the process repeated. Derivation of mean segment lists (Fig. 7A-E, not shown). Using the reference clipped list and the reference segment list a mean segment list for the reference is first derived. Initially the address in counter (H) is used to access memory to read out the first value in the segment list (i.e. the number of elements in the first segment) to register (1), counter (A) being set to 1. The memory is then accessed using the contents of counter (B) to read out the first element in the clipped list fed to accumulator (780). Counters (A, B) are incremented and the process repeated until counter (A) is greater than the contents of register (1), i.e. until all the values in the clipped list corresponding to the first reference segment have been accumulated. The contents of the accumulator and the register are then fed to the divider as dividend and divisor respectively, the result being fed to register (2) for storage in the main memory at an address pointed to by counter (J). Counters (J, H, D) are then incremented and the sequence repeated until all segments have been processed. The process is repeated for the sample lists. Correlation operation (Figs. 8A-O and Figs. 9A-B, not shown). The values of the first segment in the reference and sample segment lists are fetched from main memory using the addresses in counters (H, I) and stored in registers (2, 1). Register (3) is set to zero and register (4) is set to 30. The larger of the contents of the registers (1, 2) are compared with the contents of register (4) and if register (4) is the larger contents, the contents of register (3) i.e. zero is stored in main memory at an address pointed to by counter (L). Counters (H, I, L) are then incremented and the contents of registers (1, 2) are added to the contents of counters (D.ST., E.ST) and the result stored in counter (D.ST), (E.ST). Otherwise the larger of the two values is fed to shift register (976) and shifted right two places, the three least significant bits being set to zero. This value is then stored in displacement counter (994) shifted one bit left and indicates the number of displacements of eight units to be effected during correlation. One of six subsystems is then entered in dependence on the relative values of the registers and the shift register (i.e. in dependence on the possible boundary conditions between the segments that exist), after each of which the shift register is decremented by eight units until it is zero when a sign latch is set. It is then incremented by eight units in each cycle, the displacement counter being decremented. At each correlation the value computed is compared with a previous largest value held in register (B) and the larger of the two values is stored so that at the end of the correlation of each pair of segments the register holds the maximum value MAX C, this being stored at the address specified by counter (L). When all segments for a signature have been computed the geometric mean of the correlations is computed and compared with a threshold. Example of one subsystem for correlation computation. If the system of length contained in the smaller register lies wholly within the segment length contained in the larger register even when it is shifted by one quarter of its length then the contents of the larger register are fed to the correlator as La, the contents of the smaller register are fed as Lb and as the overlap AB. The contents Na at the address pointed to by a counter (K) are accessed and a new Mb is calculated by fetching the original Mb at an address pointed to by a counter (J) and computing Mh.Lb/La. The elements b in the clipped list associated with the longer segment are accessed sequentially, the elements a in the clipped list associated with the shorter segment, displaced by the displacement between the segments being accessed simultaneously with the elements b and the correlation unit is operated to compute, for a displacement of k in the displacement counter This is then repeated for all the other displacements until the displacement counter is zero.