Cursive character handwriting recognition system and method

• US 8,005,294 B2
• Filed: 11/29/2006
• Issued: 08/23/2011
• Est. Priority Date: 11/29/2006
• Status: Active Grant

• Current Assignee: Mitre Corporation
• Original Assignee: Mitre Corporation
• Inventors: Kundu, Amlan, Van Guilder, Linda C., Hines, Tom, Huyck, Ben, Phillips, Jon
• Primary Examiner(s): Ahmed, Samir A
• Assistant Examiner(s): Li, Ruiping
• Application Number:
  US11/605,415
• Publication Number:
  US 20080123940A1
• Time in Patent Office: 1,728 Days
• Field of Search: 382/186, 382/181, 382/115
• US Class Current: 382/159
• CPC Class Codes: G06V 30/2268 using stroke segmentation

Abstract

A cursive character handwriting recognition system includes image processing means for processing an image of a handwritten word of one or more characters and classification means for determining an optimal string of one or more characters as composing the imaged word. The processing means segments the characters such that each character is made up of one or more segments and determines a sequence of the segments using an over-segmentation-relabeling algorithm. The system also includes feature extraction means for deriving a feature vector to represent feature information of one segment or a combination of several consecutive segments. The over-segmentation-relabeling algorithm places certain segments considered as diacritics or small segments so as to immediately precede or follow a segment of the associated main character body. Additionally, the system also includes classification means that processes each string of segments and outputs a number of optimal strings which could be matched against a given lexicon.

Claims

1. A method for recognizing unconstrained cursive handwritten words, comprising:

processing an image of a handwritten word of one or more characters, the processing step including segmenting the imaged word into a set of one or more segments and determining a sequence of segments using an over-segmentation-relabeling algorithm;

extracting feature information of one segment or a combination of several consecutive segments;

repeating said extracting step until feature information from segments or combinations thereof have been extracted; and

classifying the imaged word as having a string of one or more characters using the extracted feature information,

wherein the segmenting the imaged word includes locating a first segment and a last segment in the imaged word, and wherein the determining a sequence of segments using an over-segmentation-relabeling algorithm includes;

characterizing segments as either situated segments or unsituated segments, wherein situated segments include the first and last segments, segments having an X-coordinate or Y-coordinate coverage that exceed a threshold value, and small segments that are cursively connected to segments on each side, and wherein unsituated segments are segments not characterized as situated segments; and

placing each unsituated segment having a situated segment above or below so as to either immediately precede or follow the situated segment in the sequence of segments.

2. The method of claim 1, wherein the feature information includes moment features, geometrical and positional information based features, pixel distribution features, topological features, stroke connectedness features, and reference line features.

3. The method of claim 2, wherein the imaged word is an Arabic word and the feature information further includes aspect ratio features, location and number of disconnected dots, and chain code features.

4. The method of claim 1, further comprising:

hypothesizing a set of one or more words from a given dictionary which are suggested by the string of one or more characters determined for the imaged word in the classifying step.

5. An unconstrained cursive character handwritten word recognition system, comprising a processor including:

an image processing module operable to process an image of a handwritten word of one or more characters, wherein the processing of the imaged word includes segmenting the imaged word into a finite number of segments and determining a sequence of the segments using an over-segmentation-relabeling algorithm, wherein each character includes one or more consecutive segments;

a feature extraction module operable to derive a feature vector to represent feature information of one segment or a combination of several consecutive segments; and

a classification module operable to determine an optimal string of one or more characters as composing the imaged word,

wherein the classification module uses a continuous-discrete hybrid probability modeling of features toy determine a final symbol probability of whether a given feature vector is indicative of a given distinct character,

wherein, in the continuous-discrete hybrid probability modeling of N features, the features N are separated into a first group N₁ and a second group N₂, features of the first group N₁ are distributed using a continuous probability model to obtain a continuous distribution probability measure, features of the second group N₂, are distributed using a discrete probability model given by equation (1)

6. The handwritten word recognition system of claim 5, wherein the image processing module includes means for slant normalization and noise reduction.

7. The handwritten word recognition system of claim 5, wherein a feature vector is derived for each segment and each combination of two or more consecutive segments.

8. The handwritten word recognition system of claim 5, wherein the over-segmentation-relabeling algorithm segments each character into at most two to seven consecutive segments.

9. The handwritten word recognition system of claim 8, wherein each character of the imaged word is segmented into at most four consecutive segments.

10. The handwritten word recognition system of claim 9, wherein a feature vector is derived for each segment and each combination of two to four consecutive segments.

11. The handwritten word recognition system of claim 5, wherein the feature information of includes moment features, geometrical and positional information based features, pixel distribution features, and reference line features.

12. The handwritten word recognition system of claim 5, wherein the imaged word is an Arabic word.

13. The handwritten word recognition system of claim 12, wherein the feature information includes aspect ratio features, location and number of disconnected dots, stroke connectedness features, and chain code features.

14. The handwritten word recognition system of claim 13, wherein the feature information represented by the feature vector consists of between 25 to 50 features.

15. The handwritten word recognition system of claim 14, wherein the feature information represented by the feature vector consists of 45 features.

16. The handwritten word recognition system of claim 5, wherein a modified Viterbi algorithm is used to determine the optimal string.

17. The handwritten word recognition system of claim 16, wherein the modified Viterbi algorithm is adapted to a variable duration hidden Markov model by incorporating state duration probabilities associated with each distinct character, wherein a state duration probability of a given distinct character represents a probability that the given character has a duration of a defined number of segments.

18. The handwritten word recognition system of claim 5, further comprising:

a post-processing module operable to hypothesize a set of one or more words from a given dictionary which are suggested by the optimal string.

19. The handwritten word recognition system of claim 18, wherein the post-processing module uses the Levenshtein edit distance function with empirically determined weights to hypothesize the set of one or more words.

20. A method for training an unconstrained cursive character handwritten word recognition system, comprising:

processing a corpus of handwritten word images, each imaged word having one or more characters, the processing step including segmenting each of the imaged words into a set of one or more segments and determining a sequence of the segments using an over-segmentation-relabeling algorithm;

extracting feature information of individual characters of the imaged words;

estimating symbol probability parameters associated with each distinct character so as to allow a statistical measure that given feature information is indicative of a distinct character; and

estimating state duration probabilities associated with each distinct character, wherein a state duration probability of a given distinct character represents a probability that a segmented image of the given character will have a duration of a defined number of segments,

wherein the segmenting each imaged word includes locating a first segment and a last segment in the imaged word, wherein the determining a sequence of segments using an over-segmentation-relabeling algorithm includes;

characterizing segments as either situated segments or unsituated segments, wherein situated segments include the first and last segments, segments having an X-coordinate or Y-coordinate coverage that exceed a threshold value, and small segments that are cursively connected to segments on each side, and wherein unsituated segments are segments not characterized as situated segments; and

placing each unsituated segment having a situated segment above or below so as to either immediately precede or follow the situated segment in the sequence of segments;

21. The method of claim 20, wherein the estimating symbol probability parameters step includes calculating representative feature information for each distinct character based on the feature information extracted from character images of a like distinct character in the imaged words.

22. The method of claim 20, wherein the duration of any given character is from one to four segments, and wherein a state duration probability is estimated for each duration of one to four segments for each distinct character.

23. A method for determining a sequence of segments of a segmented image of a cursive written word processed in a word recognition system, comprising:

finding the number of segments, wherein the finding step includes locating a first segment and a last segment in the imaged word; and

determining the sequence of segments using an over-segmentation-relabeling algorithm, wherein the over-segmentation-relabeling algorithm includes;

characterizing segments as either situated segments or unsituated segments, wherein situated segments include the first and last segments, segments having an X-coordinate or Y-coordinate coverage that exceed a threshold value, and small segments that are cursively connected to segments on each side, and wherein unsituated segments are segments not characterized as situated segments; and

placing each unsituated segment having a situated segment above or below so as to either immediately precede or follow the situated segment in the sequence of segments.

24. The method of claim 23, wherein each unsituated segment having a situated segment below is placed so as to immediately follow the situated segment below, and wherein each unsituated segment having a situated segment above but not a situated segment below is placed so as to immediately precede the situated segment above.

25. The method of claim 23, wherein each unsituated segment having a situated segment below is placed so as to immediately precede the situated segment below, and wherein each unsituated segment having a situated segment above but not a situated segment below is placed so as to immediately follow the situated segment above.

26. The method of claim 23, further comprising:

rechecking the segment sequence to ensure continuity of segment placements and no multiple placement of a segment.

27. The method of claim 23, wherein the imaged word has one or more characters, wherein each character of the imaged word is segmented into at most between two to seven segments.

28. The method of claim 23, wherein the situated segments further include any special diacritic present in the imaged word, wherein a special diacritic includes a double consonant or a shadda.

29. A method for recognizing unconstrained cursive handwritten words, comprising:

processing an image of a handwritten Arabic word of one or more characters, the processing step including segmenting the imaged word into a set of one or more segments and determining a sequence of segments using an over-segmentation-relabeling algorithm;

after the processing step, extracting feature information from one segment or a combination of several consecutive segments of the image word processed in the processing step, wherein the feature information includes at least one of aspect ratio features, location and number of disconnected dots, stroke connectedness features and chain code features,

wherein the aspect ratio features include two aspect ratio features, ƒ

_hv and ƒ

_vh, which are computed by finding maximum vertical extent (vd) and maximum horizontal extent (hd) of the character, wherein feature ƒ

_hv is based on a horizontal to vertical aspect ratio, and feature ƒ

_vh is based on a vertical to horizontal aspect ratio,

wherein the location and number of disconnected dots includes three features, ƒ

_du, ƒ

_dm, and ƒ

_dl relating to the number of disconnected diacritics located in an upper zone, a middle zone, and a lower zone, respectively, of the one segment or the combination of several consecutive segments,

wherein the stroke connectedness features include two stroke connectedness features, ƒ

_cr and ƒ

_cl,

wherein the chain code features include three 8-directional chain code based features, ƒ

_ch, ƒ

_rough, and ƒ

_con;

repeating said extracting step until feature information from segments or combinations thereof have been extracted; and

classifying the imaged word as having a string of one or more characters using the extracted feature information.

30. The method of claim 29, wherein the feature information includes the aspect ratio features.

31. The method of claim 29, wherein the feature information includes the location and number of disconnected dots.

32. The method of claim 31, wherein the location and number of disconnected dots further includes reference line features relating to the number of diacritics with respect to a global baseline of the imaged word and a local baseline of the one segment or the combination of several consecutive segments.

33. The method of claim 31, wherein the feature information includes the stroke connectedness features.

34. The method of claim 31, wherein the feature information further includes a maximum horizontal zero crossing feature, ƒ

_mzh, and a maximum vertical zero crossing feature, ƒ

_cr and ƒ

_mzv.

35. The method of claim 31, wherein the feature information includes the chain code based features.

36. An unconstrained cursive character handwritten word recognition system, comprising a processor including:

an image processing module operable to process an image of a handwritten word of one or more characters, wherein the processing of the imaged word includes segmenting the imaged word into a finite number of segments and determining a sequence of the segments using an over-segmentation-relabeling algorithm, wherein each character includes one or more consecutive segments;

a feature extraction module operable to derive a feature vector to represent feature information of one segment or a combination of several consecutive segments;

a classification module operable to determine an optimal string of one or more characters as composing the imaged word; and

;

a post-processing module operable to output hypotheses of one or more words from a given dictionary which are suggested by the optimal string, wherein the hypotheses are based on weighted edit distances using weight factors determined from linguistic reasoning and empirically derived mutual character confusion information and without using probabilities given by a modified Viterbi algorithm as a weight factor.

37. The handwritten word recognition system of claim 36, wherein the edit distance function is the Levenshtein edit distance.

38. The handwritten word recognition system of claim 36, wherein the empirically derived mutual character confusion information is derived from a confusion matrix generated from symbol probabilities computed from training the system or by running the system in a recognition mode using character images as input.

39. A non-transitory computer-readable medium having stored thereon, computer readable program code that, if executed by a system, cause the system to perform a method for recognizing unconstrained cursive handwritten words, the method comprising:

processing an image of a handwritten word of one or more characters, the processing step including segmenting the imaged word into a set of one or more segments and determining a sequence of segments using an over-segmentation-relabeling algorithm;

extracting feature information of one segment or a combination of several consecutive segments;

repeating said extracting step until feature information from all segments or combinations thereof have been extracted; and

classifying the imaged word as having a string of one or more characters using the extracted feature information,

wherein the segmenting the imaged word includes locating a first segment and a last segment in the imaged word, and wherein the determining a sequence of segments using an over-segmentation-relabeling algorithm includes;

characterizing segments as either situated segments or unsituated segments, wherein situated segments include the first and last segments, segments having an X-coordinate or Y-coordinate coverage that exceed a threshold value, and small segments that are cursively connected to segments on each side, and wherein unsituated segments are segments not characterized as situated segments; and

placing each unsituated segment having a situated segment above or below so as to either immediately precede or follow the situated segment in the sequence of segments.

40. The computer-readable medium of claim 39, wherein the classifying comprises using a modified Viterbi algorithm to determine the string.

41. The computer-readable medium of claim 40, further comprising:

outputting hypotheses a set of one or more words from a given dictionary which are suggested by the string of one or more characters, wherein the hypotheses are based on weighted edit distances using weight factors determined from linguistic reasoning and empirically derived mutual character confusion information and without using probabilities given by the modified Viterbi algorithm as a weight factor.

42. A non-transitory computer-readable medium having stored thereon, computer readable program code that, if executed by a system, cause the system to perform a method for training an unconstrained cursive character handwritten word recognition system, the method comprising:

processing a corpus of handwritten word images, each imaged word having one or more characters, the processing step including segmenting each of the imaged words into a set of one or more segments and determining a sequence of the segments using an over-segmentation-relabeling algorithm;

extracting feature information of segments where one or more consecutive segments represent individual characters of the imaged words;

estimating symbol probability parameters associated with each distinct character so as to allow a statistical measure that given feature information is indicative of a distinct character; and

estimating state duration probabilities associated with each distinct character, wherein a state duration probability of a given distinct character represents a probability that a segmented image of the given character will have a duration of a defined number of segments,

wherein the segmenting each imaged word includes locating a first segment and a last segment in the imaged word, wherein the determining a sequence of segments using an over-segmentation-relabeling algorithm includes;

characterizing segments as either situated segments or unsituated segments, wherein situated segments include the first and last segments, segments having an X-coordinate or Y-coordinate coverage that exceed a threshold value, and small segments that are cursively connected to segments on each side, and wherein unsituated segments are segments not characterized as situated segments; and

placing each unsituated segment having a situated segment above or below so as to either immediately precede or follow the situated segment in the sequence of segments.