Method of automated signature verification

• US 5,680,470 A
• Filed: 06/07/1995
• Issued: 10/21/1997
• Est. Priority Date: 12/17/1993
• Status: Expired due to Fees

• Current Assignee: Quintet Incorporated
• Original Assignee: Quintet Incorporated
• Inventors: Moussa, Ali Mohammed, Chan, Chih
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): DEL ROSSO, GERARD DOMNICK
• Application Number:
  US08/483,942
• Time in Patent Office: 867 Days
• Field of Search: 382/123, 382/115, 382/119, 382/209, 382/218, 382/296, 382/298, 382/301, 382/155, 382/156, 382/159
• US Class Current: 382/119
• 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 method of automated signature verification, in which a test signature, e.g., a signature entered by an operator, may be preprocessed and examined for test features. The test features may be compared against features of a set of template signatures, and verified in response to the presence or absence of the test features in the template signatures. The test signature may be preprocessed, so as to normalize it and remove artifacts which are irrelevant to verification. The features of the template signatures may be determined and stored in an associative memory or a data structure with associative memory capabilities, e.g., a discrete Hopfield artificial neural network. The method of verification may be adjusted to greater or lesser sensitivity in response to external conditions.

Claims

1. A method of handwritten signature verification, comprising the steps of

receiving a plurality of handwritten template signature;

defining a template feature vector for each of said template signatures;

performing a vector comparison between each pair of said template feature vectors so as to determine a plurality of template-template distances;

selecting one of said template-template distances other than a minimum or a maximum;

constructing a bit vector in response to each template feature vector and training a neural network in response to said bit vectors;

receiving a handwritten test signature;

defining a test feature vector in response to said test signature;

inputting said test feature vector to said neural network and generating a derived feature vector, different from said test feature vector, in response thereto;

performing a vector comparison between said derived feature vector and each one of said template feature vectors so as to determine a plurality of test-template distances;

determining a minimum one of said plurality of test-template distances; and

verifying said test handwritten signature if said minimum one of said test-template distances is less than or equal to said selected one of said template-template distances.

2. A method as in claim 1, comprising the steps of

associating a set of authorization privileges with at least one said template signature;

associating said test signature with at least one said template signature, responsive to said step of verifying; and

authorizing a person associated with said test signature responsive to said step of verifying and responsive to said authorization privileges.

3. A method as in claim 1, comprising the steps of

transforming each one of said template signatures into a first data structure representative of movements of a writing instrument for said template signature;

identifying a relative rotation of each one of said template signatures; and

altering each one of said first data structures responsive to said step of identifying.

4. A method as in claim 1, comprising the steps of

transforming said test signature into a second data structure representative of movements of a writing instrument for said test signature;

identifying a relative rotation of said test signature; and

altering said second data structure responsive to said step of identifying.

5. A method as in claim 1, comprising the steps of

transforming each one of said template signatures into a first data structure representative of movements of a writing instrument for said template signature;

dividing said first data structure into a plurality of segments;

computing a measure of dispersion for each said segment;

defining, for a first said segment, a set of retained pixels less than all pixels in said first segment, responsive to said measure of dispersion for said first segment;

computing a regression line responsive to said retained pixels; and

rotating said template signature responsive to said regression line.

6. A method as in claim 1,

wherein each one of said template signatures comprises a plurality of pixels, each said pixel having spatial information associated therewith;

said method comprising the steps of

determining a measure of physical size for written representations of each one of said template signatures; and

altering said spatial information for each said pixel so that said measure is substantially equal for each one of said template signatures.

7. A method as in claim 1,

wherein each one of said template signatures comprises a plurality of pixels, each said pixel having spatial information associated therewith;

said method comprising the steps of

for a first pixel of said plurality, defining a neighborhood for said first pixel;

altering said spatial information associated with said first pixel, responsive to said spatial information associated with at least one pixel in said neighborhood;

computing a distance measure for said first pixel, responsive to at least one pixel in said neighborhood; and

repeating said steps of defining and altering, responsive to said distance measure.

8. A method as in claim 1, wherein each one of said template signatures comprises a plurality of pixels, each said pixel having spatial information associated therewith, and wherein said step of defining a template feature vector for each of said template signatures comprises the steps of

dividing each one of said template signatures into a plurality of segments;

computing a summary measure for each said segment, responsive to a set of pixels in said segment;

quantizing said summary measure for each said segment to generate a quantized measure, wherein said quantized measure comprises fewer than nine bits; and

constructing a bit vector comprising said quantized measures.

9. A method as in claim 8, wherein said writing information is in the set composed of

a set of positions, at known time intervals, of a writing implement used to generate said first set of signatures;

a set of speeds, at known time intervals, of said writing implement;

a set of pen-up/pen-down status bits, at known time intervals, of said writing implement;

a set of measures of pixel dispersion, at known time intervals, of said first set of signatures;

a euclidean coordinate map of at least one of said first set of signatures;

a polar coordinate map of at least one of said first set of signatures; and

a set of stroke turning positions in a euclidean coordinate map of at least one of said first set of signatures.

10. A method as in claim 1, wherein said step of selecting one of said template-template distances comprises the steps of

sorting said template-template distances by magnitude to generate an ordered list;

and

selecting one of said template-template distances in said ordered list responsive to a position on said ordered list.

11. A method as in claim 1, wherein said template feature vector for each said template signature comprises a binary vector having less than 2400 bits of information.

12. A method as in claim 1, wherein said step of selecting one of said inter-template distances comprises the steps of

ranking said template-template distances;

and

selecting a one of said template-template distances having a rank other than a minimum or maximum.

13. A method for determining whether a first person is a particular individual, said method comprising the steps of

storing a plurality of template features for each of a plurality of template signatures of the particular individual, each of said template features representing a selected characteristic of one of said template signatures;

performing a comparison between each pair of said sets of template features so as to determine a plurality of template-template distances;

selecting one of said template-template distances other than a minimum or a maximum;

training a neural network in response to said sets of template features;

providing a plurality of test features for a test signature made on a signature transducer by said first person, each of said test features representing a selected characteristic of said test signature;

inputting said set of test features to said neural network and generating a set of derived features, different from said set of test features, in response thereto;

performing a vector comparison between said derived feature vector and each one of said template feature vectors so as to determine a plurality of test-template distances;

selecting one of said plurality of test-template distances; and

generating a signal indicating a match if said selected one of said test-template distances is less than or equal to said selected one of said template-template distances.

14. A method as in claim 13, wherein said selected one of said plurality of test-template distances is a minimum one of said plurality of test-template distances.

15. Apparatus for handwritten signature verification, comprising

a pen tablet;

a processor coupled to said pen tablet and disposed for receiving a plurality of template signatures and a test signature;

said processor comprising means for defining a template descriptor for each said template signatures and a test descriptor for said test signature;

said processor being disposed for comparing each pair of said template descriptors, generating a plurality of template-template distances in response thereto, and selecting one of said plurality of template-template distances other than a maximum;

an associative memory, said associative memory disposed for storing each of said template descriptors, for being addressed using said test descriptor, and for retrieving a derived descriptor in response to said template descriptors and said test descriptor;

said processor comprising means for comparing said derived descriptor against each said template descriptor, generating a plurality of test-template distances in response thereto, selecting one of said plurality of test-template distances, and comparing said one of said plurality of test-template distances against said one of said plurality of template-template distances; and

means for displaying an output of said processor responsive to said means for comparing said one of said plurality of test-template distances against said one of said plurality of template-template distances.

16. Apparatus as in claim 15, wherein

said associative memory comprises a discrete Hopfield artificial neural network weight matrix stored in a memory coupled to said processor, said neural network having a set of weights defined in response to said template descriptors;

and

said means for comparing comprises

means for inputting said test descriptor to said neural network, and

means for generating an output from said neural network.

17. Apparatus as in claim 15, wherein said means for selecting one of said plurality of test-template distances is disposed for selecting a minimum thereof.

18. Apparatus as in claim 15, wherein said means for comparing generates a signal verifying said test handwritten signature if said selected one of said test-template distances is less than or equal to said selected one of said template-template distances.

19. Apparatus as in claim 15, comprising

a database associating a set of authorization privileges with at least one said template signature;

and

means for accessing said database responsive to said step of comparing.

20. Apparatus as in claim 15, comprising

a memory storing a plurality of first data structures, each representative of movements of a writing instrument for one of said template signatures;

said processor comprising means for identifying a relative rotation of each one of said template signatures; and

said processor comprising means for altering each one of said first data structures responsive to said means for identifying.

21. Apparatus as in claim 15, comprising

a memory storing a second data structure representative of movements of a writing instrument for said test signature;

said processor comprising means for identifying a relative rotation of said test signature; and

said processor comprising means for altering said second data structure responsive to said means for identifying.

22. Apparatus as in claim 15, comprising

a memory storing a plurality of first data structures, each representative of movements of a writing instrument for one of said template signatures;

said processor comprising means for dividing said first data structure into a plurality of segments;

said processor comprising means for computing a measure of dispersion for each said segment;

said processor comprising means for defining, for a first said segment, a set of retained pixels less than all pixels in said first segment, responsive to said measure of dispersion for said first segment;

said processor comprising means for computing a regression line responsive to said retained pixels; and

said processor comprising means for rotating said first signature responsive to said regression line.

23. Apparatus as in claim 15, wherein

each one of said template signatures comprises a plurality of pixels, each said pixel having spatial information associated therewith;

said processor comprises means for determining a measure of physical size for each one of said template signatures; and

said processor comprises means for altering said spatial information for each said pixel so that said measure is substantially equal for each one of said template signatures.

24. Apparatus as in claim 15, wherein each said template descriptor comprises a binary vector having less than 2400 bits of information.

25. A method of handwritten signature verification, comprising the steps of

receiving a plurality of handwritten template signatures;

generating a template feature vector for each one of said template signatures;

determining a template-template distance between each pair of said template feature vectors;

selecting one of said template-template distances in response to a statistical measure of said template-template distances;

storing said template feature vectors in an associative memory;

receiving a handwritten test signature;

generating a test feature vector for said test signature;

generating a derived feature vector in response to said associative memory and said test feature vector;

determining a test-template distance between said derived feature vector and each one of said template feature vectors;

selecting one of said plurality of test-template distances;

verifying said test signature in response to a comparison of said selected one of said test-template distances and said selected one of said inter-template distances.

26. A method as in claim 25, wherein

said step of storing said template feature vectors in an associative memory comprises the step of training a neural network using said template feature vectors;

and

said step of generating a derived feature vector comprises the step of inputting said test feature vector to said neural network.

27. A method as in claim 25, wherein said statistical measure is a ranking within said plurality of template-template distances.

28. A method as in claim 25, wherein

said step of storing comprises the steps of

constructing a bit vector for each said template feature vector, and

defining a set of weights for a discrete Hopfield artificial neural network weight matrix, responsive to each said bit vector;

and

said step of comparing comprises the steps of

inputting said test feature vector to said discrete Hopfield artificial neural network, and

generating an output from said discrete Hopfield artificial neural network.

29. A method as in claim 28, wherein said step of defining a set of weights comprises unsupervised training of a neural network.

30. Apparatus for determining whether a first person is a particular individual, said apparatus comprising

a first memory including a template descriptor for each of a plurality of template signatures of the particular individual, and a plurality of template-template distances between each pair of said template descriptors;

a second memory including a test descriptor for a test signature made on a signature transducer by said first person;

an associative memory, said associative memory disposed for storing each of said template descriptors, for being addressed using said test descriptor, and for retrieving an derived descriptor different from said test descriptor;

a third memory including a plurality of test-template descriptors between said derived descriptor and each one of said template descriptors;

a processor coupled to said first memory, said second memory, and said third memory and disposed for comparing a selected one of said test-template distances with a selected one of said template-template distances other than a maximum thereof; and

means for displaying a match only if said said selected test-template distance is less than of said selected template-template distance.

31. Apparatus as in claim 30, wherein said selected test-template distance is a minimum thereof.

32. Apparatus as in claim 30, wherein said selected template-template distance is responsive to a rank ordering thereof.