Signature verification method using hidden markov models

• US 6,157,731 A
• Filed: 07/01/1998
• Issued: 12/05/2000
• Est. Priority Date: 07/01/1998
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.), Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.), Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Nelson, Winston Lowell, Turin, William, Hu, Jianying, Kashi, Ramanujan S.
• Primary Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US09/108,892
• Time in Patent Office: 888 Days
• Field of Search: 382/115, 382/116, 382/119-123, 382/168, 382/170, 382/171, 382/186-191, 382/195, 382/190, 382/224-229, 704/256, 704/239-243
• US Class Current: 382/119
• 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 40/30 Writer recognition; Reading and verifying signatures

Abstract

A signature verification method involves segmenting a smoothed and normalized signature and, for each segment, evaluating at least one local feature, thereby to obtain a feature-value vector. The method further includes computing the likelihood that the segments having the observed sequence of feature values were generated by a particular hidden Markov model, such model comprising a sequence of states having duration probabilities and feature-value histograms. In one aspect, the invention involves explicit state-duration modeling to account for duration in the respective states underlying the unknown signature. In another aspect, the invention involves computing a measure of signature complexity, and setting the number of states of the hidden Markov model according to such complexity measure.

Claims

1. A method for processing a set of at least two training signatures provided by a person, leading to a stored model of the class of signatures made by said person, the method comprising, for each said signature:

receiving a digitally sampled signature signal and storing it as a raw signature;

smoothing and normalizing the raw signature and storing the result as a preprocessed signature;

dividing the pre-processed signature into segments;

evaluating at least one observable on each said segment, thereby to obtain a respective feature value; and

mapping each segment to a particular state of a hidden Markov model according to a rule, wherein;

the rule tends to maximize the likelihood that the respective feature values were generated by a sequence of states defined by said mapping, and

there are more segments than there are states, so that each signature will have more than unit duration in at least some states;

the method further comprising;

storing, as part of said model, a statistical distribution over the training signatures of the feature values corresponding to at least one said observable;

CHARACTERIZED IN THAT

the method further comprises;

storing as part of said model, a statistical distribution over the training signatures of the duration in each of the states.

2. The method of claim 1, wherein the at least one observable comprises a quantized inclination angle for each segment.

3. The method of claim 2, wherein the at least one observable further comprises a quantized difference between the inclination angle of a given segment, and the inclination angle of the next segment.

4. The method of claim 1, wherein the statistical distribution of duration has a constant value over the range of durations that occur in the set of training signatures, and a substantially smaller value outside of said range.

5. The method of claim 1, wherein the mapping of segments is performed in an iterative process that tends to improve a mean likelihood score over the set of training signatures, in each iteration, until said mean score satisfies a convergence test.

6. The method of claim 1, further comprising measuring the complexity of the training signatures, and setting the number of states in response to said measurement.

7. The method of claim 6, wherein said complexity measurement comprises counting the number of local curvature maxima in each of the preprocessed training signatures.

8. The method of claim 1, wherein the mapping of segments comprises computing a likelihood score for the feature values corresponding to at least one said observable.

9. The method of claim 8, wherein the likelihood score, expressed logarithmically, accrues an additive increment equal to log b(k) for each instance of feature value k within a given state, wherein b(k) is a probability, conditional on the given state, of occurrence of feature value k.

10. The method of claim 8, wherein there are two or more observables, and the mapping of segments further comprises computing a joint likelihood score by multiplying together the likelihood scores corresponding to the respective observables.

11. A method for verifying a signature provided by a person, comprising:

receiving a digitally sampled representation of the signature and storing said representation as a raw signature;

smoothing and normalizing the raw signature and storing the result as a preprocessed signature;

dividing the pre-processed signature into segments;

evaluating at least one observable on each said segment, thereby to obtain a respective feature value;

mapping each segment to a particular state of a hidden Markov model according to a rule, wherein;

the rule tends to maximize a score related to the likelihood that the respective feature values were generated by a sequence of states defined by said mapping, and there are more segments than there are states, so that each signature will have more than unit duration in at least some states;

performing a threshold test based, at least in part, on said score; and

in response to the threshold test, generating an indication of acceptance or rejection of the signature;

CHARACTERIZED IN THAT

the method further comprises including in the score, for each of said states, a factor that explicitly takes account of the duration of the signature in said state.

12. The method of claim 11, wherein the score, expressed logarithmically, accrues for each state an additive increment equal to log p(d), wherein p(d) is a probability, conditional on the given state, that duration in the given state is equal to d.

13. The method of claim 12, wherein, for each state, p(d) has a constant value over the range of durations that occur in a set of training signatures, and a substantially smaller value outside of said range.

14. The method of claim 11, wherein the at least one observable comprises a quantized inclination angle for each segment.

15. The method of claim 14, wherein the at least one observable further comprises a quantized difference between the inclination angle of a given segment, and the inclination angle of the next segment.

16. The method of claim 11, wherein the score, expressed logarithmically, accrues an additive increment equal to log b(k) for each instance of feature value k within a given state, wherein b(k) is a probability, conditional on the given state, of occurrence of feature value k.

17. The method of claim 11, wherein:

there are two or more observables;

said score is a joint likelihood score;

and the joint likelihood score is computed by multiplying together individual likelihood scores corresponding to the respective observables.

18. A method for processing a set of at least two training signatures provided by a person, leading to a stored model of the class of signatures made by said person, the method comprising, for each said signature:

receiving a digitally sampled signature signal and storing it as a raw signature;

smoothing and normalizing the raw signature and storing the result as a pre-processed signature;

dividing the pre-processed signature into segments;

evaluating at least one observable on each said segment, thereby to obtain a respective feature value; and

mapping each segment to a particular state of a hidden Markov model according to a rule, wherein;

the rule tends to maximize the likelihood that the respective feature values were generated by a sequence of states defined by said mapping, and

there are more segments than there are states, so that each signature will have more than unit duration in at least some states;

CHARACTERIZED IN THAT the method further comprises;

measuring the complexity of the training signatures, and

setting the number of states in response to said measurement.

19. The method of claim 18, wherein said complexity measurement comprises counting the number of local curvature maxima in each of the pre-processed training signatures.