Key character extraction and lexicon reduction for cursive text recognition

• US 6,327,386 B1
• Filed: 08/09/2000
• Issued: 12/04/2001
• Est. Priority Date: 09/14/1998
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mao, Jianchang, Zimmerman, Matthias
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): Dastouri, Mehrdad
• Application Number:
  US09/635,200
• Time in Patent Office: 482 Days
• Field of Search: 382/186, 382/187, 382/188, 382/190, 382/192, 382/193, 382/195, 382/229, 382/230, 382/156, 382/157
• US Class Current: 382/186
• CPC Class Codes: G06V 30/2272 with lexical matching

Abstract

A method, apparatus, and article of manufacture employing lexicon reduction using key characters and a neural network, for recognizing a line of cursive text. Unambiguous parts of a cursive image, referred to as “key characters,” are identified. If the level of confidence that a segment of a line of cursive text is a particular character is higher than a threshold, and is also sufficiently higher than the level of confidence of neighboring segments, then the character is designated as a key character candidate. Key character candidates are then screened using geometric information. The key character candidates that pass the screening are designated key characters. Two-stages of lexicon reduction are employed. The first stage of lexicon reduction uses a neural network to estimate a lower bound and an upper bound of the number of characters in a line of cursive text. Lexicon entries having a total number of characters outside of the bounds are eliminated. For the second stage of lexicon reduction, the lexicon is fitter reduced by comparing character strings using the key characters, with lexicon entries. For each of the key characters in the character strings, it is determined whether there is a mismatch between the key character and characters in a corresponding search range in the lexicon entry. If the number of mismatches for all of the key characters in a search string is greater than (1+(the number of key characters in the search string/4)), then the lexicon entry is eliminated. Accordingly, the invention advantageously accomplishes lexicon reduction, thereby decreasing the time required to recognize a line of cursive text, without reducing accuracy.

Claims

1. A method for lexicon reduction, comprising:

ascertaining, for each of a plurality of images of features in a line of cursive text, a number indicative of a feature;

inputting the number indicative of each of the features into a feedforward neural network;

computing with the neural network an estimate of a maximum length (len_max), and a minimum length (len_min) of the line of cursive text;

comparing len_max and len_min to a lexicon entry;

eliminating the lexicon entry if it has more characters than len_max; and

eliminating the lexicon entry if it has less characters than len_min,

wherein said len_min and said len_max comprise a dynamic range that changes from image to image.

10. The method of claim 1, wherein said computing also produces a best length (len_best);

and

said comparing determines a distance between said lexicon entry and said len_best.

2. A method for lexicon reduction, comprising:

ascertaining, for each of a plurality of features in a line of cursive text, a number indicative of a feature;

inputting the number indicative of each of the features into a feedforward neural network;

computing with the neural network an estimate of a maximum length (len_max), and a minimum length (len_min) of the line of cursive text;

comparing len_max and len_min to a lexicon entry;

eliminating the lexicon entry if it has more characters than len_max; and

eliminating the lexicon entry if it has less characters than len_min,

wherein the plurality of features comprises;

(a) the number of connected components in the line of cursive text;

(b) the number of graphemes in the line of cursive text;

(c) the number of horizontal transitions in the line of cursive text;

(d) the sum of the number of horizontal transitions in each grapheme in the line of cursive text; and

(e) the average height of the graphemes in the line of cursive text.

3. A method for lexicon reduction, comprising:

ascertaining, for each of a plurality of features in a line of cursive text, a number indicative of a feature;

inputting the number indicative of each of the features into a feedforward neural network;

computing with the neural network an estimate of a maximum length (len_max), and a minimum length (len_min) of the line of cursive text;

comparing len_max and len_min to a lexicon entry;

eliminating the lexicon entry if it has more characters than len_max; and

eliminating the lexicon entry if it has less characters than len_min,

wherein the neural network has a len_best output unit, a len_max output unit, and the len_min output unit, and further comprising;

using a difference about 8(len_true−

len_best) in a back propagation step in training the len_min output unit when the length is overestimated by len_best;

using a difference about 0.25(len_true−

len_best) in the back propagation step in training the len_min output unit when the length is underestimated by len_best;

using a difference about 0.25(len_true−

len_best) in a back propagation step in training a len_max output unit when the length is overestimated by len_best;

using a difference about 8(len_true−

len_best) in the back propagation step in training the len_max output unit when the length is underestimated by len_best.

4. An article of manufacture comprising a data storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for lexicon reduction, the method comprising:

ascertaining, for each of a plurality of images of features in a line of cursive text, a number indicative of a feature;

inputting the number indicative of each of the features into a feedforward neural network;

computing with the neural network an estimate of a maximum length (len_max), and a minimum length (len_min) of the line of cursive text;

comparing len_max and len_min to a lexicon entry;

eliminating the lexicon entry if it has more characters than len_max; and

eliminating the lexicon entry if it has less characters than len_min, wherein said len_min and said len_max comprise a dynamic range that changes from image to image.

11. The article of manufacture of claim 4, wherein said computing also produces a best length (len_best);

and

said comparing determines a distance between said lexicon entry and said len_best.

5. An article of manufacture comprising a data storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for lexicon reduction, the method comprising:

ascertaining, for each of a plurality of features in a line of cursive text, a number indicative of a feature;

inputting the number indicative of each of the features into a feedforward neural network;

computing with the neural network an estimate of a maximum length (len_max), and a minimum length (len_min) of the line of cursive text;

comparing len_max and len_min to a lexicon entry;

eliminating the lexicon entry if it has more characters than len_max; and

eliminating the lexicon entry if it has less characters than len_min,

wherein the plurality of features comprises;

(a) the number of connected components in the line of cursive text;

(b) the number of graphemes in the line of cursive text;

(c) the number of horizontal transitions in the line of cursive text;

(d) the sum of the number of horizontal transitions in each grapheme in the line of cursive text; and

(e) the average height of the graphemes in the line of cursive text.

6. An article of manufacture comprising a data storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for lexicon reduction, the method comprising:

ascertaining, for each of a plurality of features in a line of cursive text, a number indicative of a feature;

inputting the number indicative of each of the features into a feedforward neural network;

computing with the neural network an estimate of a maximum length (len_max), and a minimum length (len_min) of the line of cursive text;

comparing len_max and len_min to a lexicon entry;

eliminating the lexicon entry if it has more characters than len_max; and

eliminating the lexicon entry if it has less characters than len_min,

wherein the neural network has a len_best output unit, a len_max output unit, and a len_min output unit, the method further comprising;

using a difference about 8(len_true−

len_best) in a back propagation step in training the len_min output unit when the length is overestimated by len_best;

using a difference about 0.25(len_true−

len_best) in the back propagation step in training the len_min output unit when the length is underestimated by len_best;

using a difference about 0.25(len_true−

len_best in the back propagation step in training the len_max output unit when the length is overestimated by len_best; and

using a difference about 8(len_true−

len_best, in the back propagation step in training the len_max output unit when the length is underestimated by len_best.

7. A digital data processing apparatus, programmed to reduction, comprising:

ascertaining, for each of a plurality of images of features in a line of cursive text, a number indicative of a feature;

inputting the number indicative of each of the features into a feedforward neural network;

computing with the neural network an estimate of a maximum length (len_max), and a minimum length (len_min) of the line of cursive text;

comparing len_max and len_min to a lexicon entry;

eliminating the lexicon entry if it has more characters than len_max; and

eliminating the lexicon entry if it has less characters than len_min, wherein said len_min and said len_max comprise a dynamic range that changes from image to image.

12. The apparatus of claim 7, wherein said computing also produces a best length (len_best);

and

said comparing determines a distance between said lexicon entry and said len_best.

8. A digital data processing apparatus, programmed to reduction, comprising:

ascertaining, for each of a plurality of features in a line of cursive text, a number indicative of a feature;

inputting the number indicative of each of the features into a feedforward neural network;

computing with the neural network an estimate of a maximum length (len_max), and a minimum length (len_min) of the line of cursive text;

comparing len_max and len_min to a lexicon entry;

eliminating the lexicon entry if it has more characters than len_max; and

eliminating the lexicon entry if it has less characters than len_min,

wherein the plurality of features comprises;

(a) the number of connected components in the line of cursive text;

(b) the number of graphemes in the line of cursive text;

(c) the number of horizontal transitions in the line of cursive text;

(d) the sum of the number of horizontal transitions in each grapheme in the line of cursive text; and

(e) the average height of the graphemes in the line of cursive text.

9. A digital data processing apparatus, programmed to reduction, comprising:

ascertaining, for each of a plurality of features in a line of cursive text, a number indicative of a feature;

inputting the number indicative of each of the features into a feedforward neural network;

computing with the neural network an estimate of a maximum length (len_max), and a minimum length (len_min) of the line of cursive text;

comparing len_max and len_min to a lexicon entry;

eliminating the lexicon entry if it has more characters than len_max; and

eliminating the lexicon entry if it has less characters than len_min,

wherein the neural network has a len_best output unit, a len_max output unit, and a len_min. output unit, the method further comprising;

using a difference about 8(len_true−

len_best) in a back propagation step in training the len_min output unit when the length is overestimated by len_best;

using a difference about 0.25(len_true−

len_best) in the back propagation step in training the len_min output unit when the length is underestimated by len_best; and

using a difference about 0.25(len_true−

len_best) in the back propagation step in training the len_max output unit when the length is overestimated by len_best; and

using a difference about 8(len_true−

len_best) in a back propagation step in training the len_max output unit when the length is underestimated by len_best.