Method and apparatus for capturing information in drawing or writing

• US 5,226,091 A
• Filed: 05/01/1992
• Issued: 07/06/1993
• Est. Priority Date: 11/05/1985
• Status: Expired due to Fees

• Current Assignee: Colin S. Hilton, David N.L. Howell, John S. Bridle, Martin J. Russell, Roger K. Moore
• Original Assignee: Colin S. Hilton, David N.L. Howell, John S. Bridle, Martin J. Russell, Roger K. Moore
• Inventors: Russell, Martin J., Bridle, John S., Moore, Roger K., Howell, David N. L., Hilton, Colin S.
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/877,232
• Time in Patent Office: 431 Days
• Field of Search: 382/3, 382/13, 382/56, 382/54, 178/18, 178/19, 178/20
• US Class Current: 382/107
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 10/12 Details of acquisition arrangements; Constructional details thereof
• CPC Class Codes: G06V 40/30 Writer recognition; Reading and verifying signatures
• CPC Class Codes: G07C 9/35 by means of a handwritten signature

Abstract

A signature to be verified is written on an area which carries horizontal and vertical lines using a pen. As the lines are crossed signals representative of the vertical and horizontal components of the pen tip velocity and whether the tip is in contact with the area are passed to a computer. A hidden Markov model derived from vertical and horizontal velocities and a "contact" signal occurring as a number of authentic signatures are written is stored by the computer. A forward pass of the Baum-Welch algorithm is used to calculate the probability that the vertical and horizontal components of the pen tip and the contacts between pen tip and the writing area could have been produced from the hidden Markov model. This probability is used to decide whether the signature is authentic. The hidden Markov model stored by the computer is derived from an initial model based on pen tip velocities and contacts occurring in an authentic signature, and re-estimation carried out using forward and backward passes of the Baum-Welch algorithm and velocities and contacts from further authentic signatures.

Claims

1. A method of verifying a signature comprising the steps of:

using modeling means to generate a representation of a signature from data representing a finite state machine previously derived from a plurality of genuine signatures; and

comparing the generated signature with a trial signature to be verified in rejecting or accepting the trial signature.

2. Apparatus for use in signature verification comprising:

modeling means for storing data defining the states of a finite state machine model of a signature; and

means for generating a display of a representation of the signature from at least some of the stored data;

whereby a signature to be verified can be compared with said representation.

3. A method of generating a representation of a signature comprising the steps of:

retrieving a series of values from stored data representing a finite state machine derived by modeling means from examples of the signature written using a writing instrument with a tip, each value being at least one of a number of values defining states of the finite state machine, and the values in the series being retrieved from the stored data and representing successive states of the finite state machine; and

generating a series of visible points and/or lines in a representation of the signature from the series of values.

4. A method according to claim 3 wherein the values in the series comprise a series of mean velocities of a pen tip writing an authentic signature;

said generating step comprising a step of generating the visible points and/or lines by calculating point positions from the mean velocities.

5. A method according to claim 3 wherein the number of visible points and/or lines generated from the stored data representing each state of the finite state machine depends on the reciprocal of the probability of transition from that state back to the same state.

6. A method according to claim 3 wherein the values stored and retrieved include, for each state of the finite state machine, two mean tip velocity components and the probability of transition back to that state, said generating step comprising the steps of:

calculating a duration using the reciprocal of said probability of transition for that state; and

generating a line having a direction dependent on the velocity components for that state and a length dependent on said duration and said velocity components.

7. A method according to claim 6 wherein the values stored and retrieved include, for each state, the mean value of a contact signal indicating whether the tip is in contact with a writing surface, said generating step including the step of:

generating a line for a state only when the contact signal has a predetermined relationship to a threshold value.

8. Apparatus for generating a representation of a signature comprising:

modeling means for retrieving a series of previously stored values from data representing a finite state machine, each value being at least one of a number of values defining states of the finite state machine, and the values in the series being retrieved from said data and representing successive states of the finite state machine; and

means for generating a series of visible points and/or lines as a representation of the signature from the series of values.

9. A method of automatic signature verification comprising, for each signatory, the steps of:

using modeling means for deriving and storing finite state machine data representing a finite state machine particular to the signatures of a specific signatory based on corresponding measurements of a plurality of signatures from the specific signatory written on a writing surface carrying parallel lines, the measurements of each signature comprising discrete velocities of the tip of a writing instrument used to write the said plurality of signatures determined from the rate at which the said lines are crossed by said tip, each state of the finite state machine being defined at least partially by a mean tip velocity component particular to that state; and

verifying signatures by comparing the finite state machine data with data from signatures alleged to be written by the signatory.

10. A method according to claim 9 wherein the said measurements include two components of the said velocity in directions normal to one another, the surface has two sets of parallel lines with the lines of one set of lines normal to those of the other, and the sets of lines are such that crossing the lines of one set of lines by the said tip can be distinguished from such crossings of the other set of lines.

11. A method according to claim 9 wherein the data represents a finite state machine having between thirty and one hundred states.

12. A method according to claim 9 wherein the data represents a hidden Markov model (HMM).

13. A method according to claim 12 wherein each state of the HMM has not more than two transitions to other states.

14. A method according to claim 9, said using step comprising the steps of:

deriving one signal representing each said measurement;

dividing each signal into an equal number of segments; and

deriving the data to represent a finite state machine with a number of states dependent on the number of segments.

15. A method according to claim 9 wherein the states of the finite state machine are defined by at least one probability density function (pdf) represented by the mean and variance of a Gaussian distribution.

16. A method according to claim 15 wherein each mean and variance for each state relate to the velocity of the said tip in a said segment which relates to that state.

17. A method according to claim 9, further comprising the step of:

carrying out a further measurement on each signature used to derive the data, said further measurement indicating whether said tip is in contact with a writing surface on which said plurality of signatures is written.

18. A method according to claim 9, said using step comprising the steps of:

calculating the forward and backward probabilities from signals representing one of the plurality of signatures and an initial form of the finite state machine data based on measurements from one of the plurality of signatures;

re-estimating values defining the finite state machine data from the forward and backward probabilities;

repeating the step of calculating forward and backward probabilities and re-estimating values using the initial form of the finite state machine data and input signals from each of a number of the plurality of signatures while accumulating re-estimated values defining the finite state machine data;

deriving values re-defining the finite state machine data from the accumulated values;

accumulating a plurality of re-estimated values defining the finite state machine data by repeatedly calculating the forward and backward probabilities from the re-defined form of the finite state machine data and input signals from each of a number of the plurality of signatures;

deriving values re-defining the finite state machine data from the accumulated values;

continually repeating the steps of accumulating re-estimated values and calculating the forward probability and deriving values re-defining the finite state machine data until the increase in the forward probability calculated for the final state falls below a predetermined threshold, the last said values derived then defining the final version of the finite state machine data.

19. A method according to claim 9, said verifying step comprising the steps of:

calculating the forward probabilities from the finite state machine data and measurements from a trial signature to be verified which correspond to the measurements from which the finite state machine data was derived; and

comparing the forward probability calculated for the final state with a predetermined threshold value to determine whether to accept or reject the trial signature.

20. Apparatus for signature verification comprising:

velocity-measuring means for determining the velocity of the tip of a writing instrument used to write signatures on a writing surface carrying parallel lines by determining the rate at which the said lines are crossed by the said tip;

modeling means for deriving and storing sets of data representing a respective finite state machine for the signature of each person whose signature is to be recognized by the apparatus, each set of data being based on measurements on a plurality of signatures from one said person written on a writing surface carrying parallel lines and the measurements of each signature comprising discrete velocities of the tip of a writing instrument used to write the said plurality of signatures as determined by the said velocity measuring means, and each state of each finite state machine being defined at least partially by a mean tip velocity component particular to that state; and

means for verifying signatures based on the sets of stored data.

21. Apparatus according to claim 20 wherein the modeling means is arranged to derive finite state machine data for each signature which represents a finite state machine having between thirty and one hundred states.

22. Apparatus according to claim 20 wherein:

the velocity-measuring means determines the components of the velocity of the said tip in two directions at right angles when used to write signatures on a writing surface carrying two sets of parallel lines with the lines of one set at right angles to the lines of the other set; and

the modeling means is arranged to use the said components in deriving said sets of data.

23. A method of modeling a signature comprising the steps of:

obtaining corresponding measurements from a plurality of signatures from one signatory written on a writing surface carrying parallel lines, the measurements on each signature comprising discrete velocities of the tip of a writing instrument used to write the said plurality of signatures determined from the rate at which said parallel lines are crossed; and

using modeling means to define data representing a finite state machine particular to that signatory based on the measurements obtained, each state of the finite state machine being defined at least partially by a mean tip velocity component particular to that state.

24. Apparatus for deriving a finite state machine modelling a signature comprising:

velocity-measuring means for determining the velocity of the tip of a writing instrument used to write signatures on a writing surface carrying parallel lines by determining the rate at which the said lines are crossed by said tip; and

modeling means for deriving and storing data representing a finite state machine particular to one signatory based on corresponding discrete velocity measurements obtained using the velocity-measuring means from a plurality of signatures from that signatory, each state of the finite state machine being defined at least partially by a mean tip velocity component particular to that state.

25. A method of verifying a signature comprising the steps of:

obtaining measurements from a signature to be verified written on a writing surface carrying parallel lines, the measurements comprising discrete velocities of the tip of a writing instrument used to write the signature determined from the rate at which said parallel lines are crossed;

determining the probability that the said measurements could have been generated by a finite state machine represented by stored data derived by modeling means from at least one genuine signature, each state of the finite state machine being defined at least partially by a mean tip velocity component particular to that state; and

accepting or rejecting the signature on the basis of the probability determined.

26. Apparatus for verifying a signature comprising:

means for obtaining measurements from a trial signature to be verified written on a writing surface carrying parallel lines, the measurements comprising discrete velocities of the tip of a writing instrument used to write the signature determined from the rate at which said parallel lines are crossed;

means for determining the probability that said measurements could have been generated by a finite state machine represented by stored data derived by modeling means from at least one genuine signature, each state of the finite state machine being defined at least partially by a mean tip velocity component particular to that state; and

means for accepting or rejecting the signature on the basis of the probability determined.

27. Apparatus according to claim 26 wherein:

the means for determining the said probability calculates the forward probability of the final state of the finite state machine from the stored finite state machine data and the measurements from the trial signature; and

the means for accepting or rejecting the signature uses the forward probability calculated for the final state to determine whether the trial signature is to be accepted or rejected.