Method of recognizing handwritten symbols

• US 5,333,209 A
• Filed: 03/24/1992
• Issued: 07/26/1994
• Est. Priority Date: 03/24/1992
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: Wilfong, Gordon T., Sinden, Frank W.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/857,198
• Time in Patent Office: 854 Days
• Field of Search: 382/13, 382/3, 382/59
• US Class Current: 382/187
• CPC Class Codes: G06V 30/333 Preprocessing; Feature extraction
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet
• CPC Class Codes: G07C 9/35 by means of a handwritten signature

Abstract

An unknown handwritten symbol written on a digitizing tablet is compared with symbols in a predefined "alphabet" or library of model symbols and the closest match chosen. Recognition is independent of the size, position or orientation of the symbols. The alphabet can be any collection of symbols, such as alphanumeric characters, ideograms or words in cursive script and is created by writing at least one example of each symbol on the tablet. A sequence of samples of the pen position is recorded while a symbol is being written. The samples form a vector, which is then translated so that the centroid of the symbol lies at an origin. The comparison, which can easily be done in real time, involves calculating a correlation factor from scalar products of the vector for the unknown symbol and two versions of the vector for each model symbol and choosing the model symbol having the highest correlation factor. If needed to distinguish between model symbols with similar correlation factors, the comparison can also include calculating a rotation factor from such vectors for use in making such choice. Embodiments of the invention can be configured that are user-independent, user-dependent or that evolve from one to the other.

Claims

1. A machine method of recognizing an unknown symbol as one of a set of stored model symbols wherein said unknown symbol and said model symbols are each represented as an ordered set of coordinate samples, which comprises:

translating the samples for said unknown symbol and each model symbol so that the centroids of said unknown symbol and said model symbol lie at a common origin,

comparing said unknown symbol with each model symbol in turn by equalizing the number of translated samples for said unknown symbol and said model symbol and determining the correlation of said unknown symbol with said model symbol from the equalized number of said translated samples for said unknown symbol and the equalized number of said translated samples for said model symbol by calculating said correlation as a quantity indicating the closeness of a representation of all possible rotations and sizes of said unknown symbol to a representation of all possible rotations and sizes of said model symbol and

recognizing said unknown symbol as the model symbol associated with the highest correlation,

whereby said recognition is independent of the size, position or orientation of said unknown symbol with respect to said model symbols.

2. The method of claim 1 wherein said calculating step further comprises:

calculating said correlation as;

##EQU9## where vector v.sub.α

is the equalized ordered set of translated samples for said unknown symbol, vector v_k is the equalized ordered set of translated samples for said model symbol, vector u_k is derived from vector v_k by a counterclockwise rotation of π

/2 radians and

said symbol associated with the highest correlation is the model symbol associated with the highest value of C.

3. The method of claim 1 which further comprises:

storing said ordered sets of coordinate samples for said model symbols while said model symbols are being handwritten on a digitizing tablet.

4. The method of claim 3 which further comprises:

storing the number of pen strokes used to write each model symbol and each unknown symbol and wherein said comparing step further comprises;

limiting said comparing step to those of said model symbols having the same number of pen strokes as the unknown symbol.

5. The method of claim 4 wherein said equalizing step further comprises equalizing said samples on a stroke-by-stroke basis.

6. The method of claim 5 wherein said equalizing step further comprises:

limiting vector v.sub.α

to a subset of essentially uniformly spaced samples from said ordered set for said unknown symbol, and

limiting vector v_k to include the same number of essentially uniformly spaced samples, stroke-by-stroke, from said ordered set for said model symbol as in said limited vector v.sub.α

.

7. The method of claim 5 wherein said equalizing step further comprises:

augmenting the number of samples in said vector v_k by interpolating a fixed number of additional samples between each adjacent pair of actual samples in said vector v_k, and

limiting vector v_k to include the same number of essentially uniformly spaced samples, stroke-by-stroke, from said augmented vector v_k as in said vector v.sub.α

.

8. The method of claim 1 which further comprises:

if an unknown symbol is recognized incorrectly, adapting said set of model symbols by adding said ordered sequence of samples for said incorrectly recognized symbol to said set of model symbols as an additional representative example of the correct symbol to be associated with said incorrectly recognized symbol.

9. The method of claim 1 which further comprises:

continually adapting said set of model symbols by storing said ordered sequences of samples for each of a specified number of the most recently entered instances of each model symbol.

10. The method of claim 2 which comprises the additional step of:

establishing a threshold value related to said highest value of C,

if the value of C for more than one model symbol exceeds said threshold value then, for each model having a value of C above said threshold value, calculating the rotation of said model symbol with respect to said unknown symbol and

wherein said recognizing step comprises recognizing said unknown symbol as the model symbol having the smallest rotation.

11. The model of claim 10 wherein said rotation calculating step further comprises:

calculating said rotation as;

##EQU10## wherein said model symbol having the smallest rotation is the symbol having R closest to unity.

12. The method of claim 11 wherein said establishing step further comprises establishing said threshold value as a fixed percentage of said highest value of C.

13. The method of claim 3 for use in verifying signatures wherein said model symbols are previously written signatures and said unknown symbol is a signature to be verified.

14. The method of claim 13 comprising the additional step of:

comparing said highest value of C with the next-highest value of C and rejecting said signature to be verified if said next-highest value exceeds a certain percentage of said highest value.

15. The method of claim 13 comprising the additional step of:

comparing said highest value of C with a threshold value and rejecting said signature to be verified if said highest value does not exceed said threshold value.

16. The method of claim 1 which further comprises:

storing sets of pre-recorded coordinate samples for a plurality of versions of said model symbols in said set of stored model symbols.

17. The method of claim 16 which further comprises:

as unknown symbols are recognized, replacing at least one set of pre-recorded samples for a model symbol with at least one set of samples for an unknown symbol recognized as said model symbol.

18. The method of claim 17 wherein said replacing step further comprises:

replacing said sets of pre-recorded samples for a model symbol with a smaller number of sets of samples for unknown symbols recognized as said model symbol.

19. The method of claim 16 which further comprises:

as unknown symbols are recognized, augmenting said sets of pre-recorded samples for a model symbol with at least one set of samples for an unknown symbol recognized as said model symbol.

20. A machine method of finding the closest match for an unknown symbol in a set of stored model symbols wherein said unknown symbol and said model symbols are each represented as an ordered set of coordinate samples with the centroids of said unknown symbol and said model symbols at a common origin, said samples for said unknown symbol are compared in turn with said samples for each of said model symbols, before each comparison, the number of translated samples for said unknown symbol is equalized with the number of said samples for said model symbol and during each comparison, the correlation of said unknown symbol with said model symbol is calculated from said equalized and translated samples and the model symbol associated with the highest correlation is identified as the closest match CHARACTERIZED IN THAT

said correlation calculation step further comprises:

calculating said correlation as a quantity indicating the closeness of a representation of all possible rotations and sizes of said unknown symbol to a representation of all possible rotations and sizes of said model symbol,

whereby said comparisons are independent of the size, position or orientation of said unknown symbol with respect to said model symbols.

21. The method of claim 20 FURTHER CHARACTERIZED IN THAT

said calculating step further comprises calculating said correlation as:

##EQU11## where vector v.sub.α

is the equalized ordered set of translated samples for said unknown symbol, vector v_k is the equalized ordered set of translated samples for said model symbol, vector u_k is derived from vector v_k by a counterclockwise rotation of π

/2 radians and

said symbol associated with the highest correlation is the symbol associated with the highest value of C.

22. The method of claim 20 FURTHER CHARACTERIZED IN THAT

said method further comprises:

storing said ordered sets of coordinate samples for said model symbols while said model symbols are being handwritten on a digitizing tablet.

23. The method of claim 22 FURTHER CHARACTERIZED IN THAT

said method further comprises:

storing the number of pen strokes used to write each model symbol and each unknown symbol and wherein said comparing step further comprises;

limiting said comparing step to those of said model symbols having the same number of pen strokes as the unknown symbol.

24. The method of claim 23 FURTHER CHARACTERIZED IN THAT

said equalizing step further comprises equalizing said samples on a stroke-by-stroke basis.

25. The method of claim 24 FURTHER CHARACTERIZED IN THAT

said equalizing step further comprises:

limiting vector v.sub.α

to a subset of essentially uniformly spaced samples from said ordered set for said unknown symbol, and

limiting vector v_k to include the same number of essentially uniformly spaced samples, stroke-by-stroke, from said ordered set for said model symbol as in said limited vector v.sub.α

.

26. The method of claim 20 FURTHER CHARACTERIZED IN THAT

if an unknown symbol is recognized incorrectly, adapting said set of model symbols by adding said ordered sequence of samples for said incorrectly recognized symbol to said set of model symbols as an additional representative example of the correct symbol to be associated with said incorrectly recognized symbol.

27. The method of claim 20 FURTHER CHARACTERIZED IN THAT

said method further comprises

continually adapting said set of model symbols by storing said ordered sequences of samples for each of a specified number of the most recently entered instances of each model symbol.

28. The method of claim 21 FURTHER CHARACTERIZED IN THAT

said method further comprises:

establishing a threshold value related to said highest value of C,

if the value of C for more than one model symbol exceed said threshold value then, for each model symbol having a value of C above said threshold value, calculating the rotation of said model symbol with respect to said unknown symbol and

wherein said recognizing step comprises recognizing said unknown symbol as the model symbol having the smallest rotation.

29. The model of claim 28 FURTHER CHARACTERIZED IN THAT

said rotation calculating step further comprises:

calculating said rotation as;

##EQU12## wherein said model symbol having the smallest rotation is the symbol having R closest to unity.

30. The method of claim 29 FURTHER CHARACTERIZED IN THAT

said establishing step further comprises establishing said threshold value as a fixed percentage of said highest value of C.

31. The method of claim 22 FURTHER CHARACTERIZED IN THAT

said method is used for verifying signatures, said stored model symbols are previously written signatures and said unknown symbol is a signature to be verified.

32. The method of claim 31 FURTHER CHARACTERIZED IN THAT

said method further comprises:

comparing said highest value of C with the next-highest value of C and rejecting said signature to be verified if said next-highest value exceeds a certain percentage of said highest value.

33. The method of claim 20 FURTHER CHARACTERIZED IN THAT

said method further comprises:

storing sets of pre-recorded coordinate samples for a plurality of versions of each said model symbol in said set of stored model symbols.

34. The method of claim 33 FURTHER CHARACTERIZED IN THAT

said method further comprises:

as unknown symbols are recognized, replacing at least part of said pre-recorded samples for each said model symbol with at least one set of samples for an unknown symbol recognized as said model symbol.

35. The method of claim 34 FURTHER CHARACTERIZED IN THAT

said replacing step further comprises:

replacing said sets of pre-recorded samples for each said model symbol with a smaller number of sets of samples for unknown symbols recognized as said model symbol.

36. The method of claim 33 FURTHER CHARACTERIZED IN THAT

said method further comprises

as unknown symbols are recognized, augmenting said sets of pre-recorded samples for each said model symbol with at least one set of samples for an unknown symbol recognized as said model symbol.