Handwriting recognition employing pairwise discriminant measures

• US 5,005,205 A
• Filed: 01/12/1990
• Issued: 04/02/1991
• Est. Priority Date: 01/12/1990
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jeanty, Henry H., Ellozy, Hamed A., Tappert, Charles C.
• Primary Examiner(s): Brinich, Stephen
• Application Number:
  US07/463,770
• Time in Patent Office: 445 Days
• Field of Search: 382/3, 382/13, 382/34
• US Class Current: 382/187
• CPC Class Codes: G06F 18/24133 Distances to prototypes
• CPC Class Codes: G06F 18/24317 Piecewise classification, i.e. whereby each classification requires several discriminant rules
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18 Extraction of features or characteristics of the image
• CPC Class Codes: G06V 30/19173 Classification techniques
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

In a handwriting recognition system a method for differentiating a first character from a second character having similar characteristics. The method includes the steps of determining during a training session at least one pairwise discriminant measure associated with the first character and with the second character. The step of determining includes a step of evaluating with a potential discriminant measure a plurality of prototype first characters and a plurality of prototype second characters. Subsequently, during a handwriting recognition session, the method evaluates with at least one of the previously determined discriminant measures selected from a set of same an input character identified as being either the first prototype character or the second prototype character. The step of evaluating includes a step of analyzing a stroke or strokes associated with the input character in accordance with one or more of the pairwise discriminant measures selected from the set, summing the results of each discriminant measure analysis to obtain a result for each of the pair of characters associated with the pairwise discriminate measure, and selecting a character from the pair that has a maximum value result.

Claims

1. In a handwriting recognition system, a method for discriminating a first handwritten character from a second handwritten character, comprising the steps of:

selecting one or more discriminants that satisfy a predetermined threshold relating to a number of occurrences (N) of original characters in a training set and to a predetermined threshold relating to a percent accuracy (P) in correctly differentiating between training characters;

assigning a weight to each selected discriminant, the weight being equal to a product (P*G) of a goodness value (G) associated with the discriminant and (P); and

summing the weights to discriminate between the first and the second characters.

4. A method as set forth in claim 1 wherein (N) is at least approximately 12 and wherein P is approximately 95 percent.

2. A method as set forth in 1 wherein G is defined as a difference between a mean of a first prototype character (char1) and a mean of a second prototype character (char2) divided by an average of a standard deviation of the first prototype character and a standard deviation of the second prototype character in accordance with the expression:

##EQU5##

3. A method as set forth in claim 2 wherein a threshold for discriminant decision is determined to be (a) approximately midway within a gap between disjoint probability distributions of the first prototype character and the second prototype character or (b), is determined to yield an optimal recognition of the correct character for overlapping probability distributions of the first prototype character and the second prototype character.

5. In a handwriting recognition system, a method for differentiating a first character from a second character, comprising the steps of:

determining during a training session at least one discriminant measure associated with the first character and with the second character, the step of determining including a step of evaluating with a potential discriminant measure a plurality of prototype first characters and a plurality of prototype second characters; and

during a handwriting recognition session evaluating with at least one of the previously determined discriminant measures an input character identified as being either the first prototype character or the second prototype character;

wherein the step of determining includes a step of calculating a goodness value associated with the first prototype character and the second prototype character, wherein the goodness value is defined as a difference between a mean of the first prototype character (char1) and a mean of the second prototype character (char2) divided by an average of a standard deviation of the first prototype character and a standard deviation of the second prototype character in accordance with the expression ##EQU6##

6. A method as set forth in claim 5 wherein the step of determining further includes a step of selecting a potential discriminate measure when a plurality of conditions are found to be satisfied, the plurality of conditions including (a) a training set of prototype characters is found to contain at least (N) occurrences of each of the plurality of first prototype characters and the plurality of second prototype characters, and (b) the potential discriminate measure correctly discriminates between at least (P) percent of the prototype first characters and prototype second characters of the training set.

7. A method as set forth in claim 6 wherein a threshold for discriminant decision is determined to be approximately midway within a gap between disjoint probability distributions of the first prototype character and the second prototype character.

8. A method as set forth in claim 6 wherein a threshold for discriminant decision is determined to yield an optimal recognition of the correct character for overlapping probability distributions of the first prototype character and the second prototype character.

9. A method as set forth in claim 6 wherein (N) is at least approximately 12.

10. A method as set forth in claim 5 wherein the step of evaluating includes the steps of:

analyzing a stroke or strokes associated with the input character in accordance with one or more previously determined discriminant measures;

summing the results of each discriminant measure analysis to obtain a result for each character; and

selecting a character having a maximum result value.

11. A method of determining with a handwriting recognition system an identity of a handwritten character tentatively identified to be either a first character or a second character, the method including the steps of inputting a handwritten stroke or strokes expressive of a character;

and analyzing the strokes in accordance with one or more pairwise discriminant measures selected from a set of pairwise discriminant measures, the selected pairwise discriminant measure or measures having been previously determined to accurately discriminate at least (P) percent of the time between the first character and the second character based on a plurality of at least N prototype first characters and on a plurality of at least N prototype second characters.

12. A method as set forth in claim 11 wherein each pairwise discriminant measure is selected from a set of pairwise discriminant measures comprised of:

space="preserve" listing-type="tabular">______________________________________ PAIR # STR DISCRIMINANT MEASURE ______________________________________ D-P F-1 X-Y O,0-6 1,2 3 2 1 ##STR16## a-d 1 ##STR17## D-P V-Y X-Y 2 2 2 ##STR18## a-d h-n K-k 2 2 2 ##STR19## P-p q-9 z-3 1,2 1 1 ##STR20## b-h g-q G-6 1,2 1,2 1 ##STR21## a-u c-e g-y C-L 1 1 1 1 ##STR22## C-O 1 ##STR23## O-U,V 1 ##STR24## h-n 0-6 a-9 J-T 1 1 1 2 ##STR25## r-v J-T 1 2 ##STR26## J-T 1-( 2 1 ##STR27## U-V C-L 1 1 ##STR28## Z-2 1 ##STR29## U-V 1 ##STR30## ______________________________________

wherein for a plurality of character pairs (PAIR) each character is formed by a number of strokes (#STR), each stroke being defined by x and y coordinates, and wherein Length L(*) is a sum of lengths of line segments (*), cg(*) is a center-of-gravity(*), H(*) is ymax(*)-ymin(*) and Width is xmax(*)-xmin(*).

13. A method as set forth in claim 11 and including an initial step of determining during a training session one or more pairwise discriminants associated with the character pair, the step of determining including a step of evaluating with a potential pairwise discriminant measure a plurality of the prototype first characters and a plurality of the prototype second characters, wherein the step of determining includes a step of calculating a goodness value associated with the first prototype character and with the second prototype character, and wherein the goodness value is defined as a difference between a mean of the first prototype character (char1) and a mean of the second prototype character (char2) divided by an average of a standard deviation of the first prototype character and a standard deviation of the second prototype character in accordance with the expression ##EQU7##

14. A method as set forth in claim 11 wherein (N) is at least approximately 12 and wherein P is approximately 95 percent.

15. A method as set forth in claim 13 wherein the step of analyzing includes the steps of:

assigning a weight to each selected discriminant measure, the weight being equal to a product (P*G) of the goodness value (G) associated with the discriminant measure and (P); and

summing the weights to discriminate between the first character and the second characters.

16. A method as set forth in claim 11 wherein the step of analyzing includes an initial step of selecting pairwise discriminate that discriminates between the first character and the second character based upon a character stroke feature selected from the group consisting of linear extension, closure, other feature and combinations thereof.

17. A method as set forth in claim 11 wherein the step of analyzing includes an initial step of selecting a pairwise discriminate that discriminates between the first character and the second character based upon a character feature known to be considered by human subjects when visually discriminating between the first character and the second character.

18. A method as set forth in claim 11 wherein the one or more pairwise discriminant measures are selected based upon a tentative identification of the input character.