Character segmentation technique with integrated word search for handwriting recognition

• US 5,917,941 A
• Filed: 08/08/1995
• Issued: 06/29/1999
• Est. Priority Date: 08/08/1995
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Yaeger, Larry S., Webb, Brandyn
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US08/512,330
• Time in Patent Office: 1,421 Days
• Field of Search: 382/229, 382/230, 382/231, 382/177, 382/178, 382/179, 382/186-189, 382/309, 382/310, 382/226, 382/228, 707/530, 707/531, 707/532, 707/533, 707/534
• US Class Current: 382/177
• CPC Class Codes: G06V 30/2276 with probabilistic networks, e.g. hidden Markov models

Abstract

After each complete stroke in a handwriting recognition process, a hypothesis is generated whether a word break is present between the previous stroke and the new stroke. This hypothesis is weighted with a probability of a word-break occurring between the strokes. This probability is determined from the geometrical relationships between characters. Subsequently, a word search is carried out on the basis of these weighted hypotheses, to identity the most likely candidates for the words represented by the written strokes. A user interface is provided that offers the user a limited list of alternative word recognitions for a group of characters. These recognitions undergo segmentation filtering, in accordance with the word breaks of the selected hypotheses, to present the user with only those alternatives having the same groupings of strokes.

Claims

1. A method for segmenting plural recognized characters into words in a handwriting recognition process, comprising the steps of:

generating hypotheses pertaining to respective combinations of characters having word-break spaces at different locations between the characters;

assigning a weight value to each hypothesis;

searching the hypotheses having the highest weight values, relative to a dictionary of recognized words; and

selecting the hypothesis whose combination of characters and word break spaces most closely matches entries in the dictionary.

2. The method of claim 1 wherein the weight value is related to spacing between adjacent hand-written characters.

3. The method of claim 1 wherein said step of generating hypotheses is carried out after each hand-written character is recognized.

4. The method of claim 1 further including the step of displaying a plurality of hypotheses, including the selected hypothesis.

5. The method of claim 4 further including the step of limiting the displayed hypotheses to those having the same word breaks as the selected hypothesis.

6. A handwriting recognition system, comprising:

an input device in which a user enters handwritten strokes;

a stroke processor for measuring distances between strokes;

a character classifier for classifying groups of strokes into recognized characters; and

a word recognition device for generating output signals indicative of possible words represented by the handwritten strokes, said word recognition device including;

means for generating hypotheses pertaining to respective combinations of characters having word-break spaces at different locations between the characters, and for assigning a weight value to each hypothesis;

means for searching the hypotheses having the highest weight values relative to a dictionary of recognized words; and

means for selecting the hypothesis whose combination of characters and word break spaces most closely matches entries in the dictionary.

7. The system of claim 6 wherein the weight value is related to the measured distance between adjacent hand-written strokes.

8. The system of claim 6 wherein said hypothesis generating means generates hypotheses after each group of strokes is classified by said classifier.

9. The system of claim 6 further including a display device for displaying a plurality of hypotheses, including the selected hypothesis.

10. The system of claim 9 further including means for limiting the displayed hypotheses to those having the same word breaks as the selected hypothesis.

11. A method for identifying words within handwritten characters, comprising the steps of:

receiving strokes entered by a user and classifying one or more strokes as a possible character;

receiving additional strokes entered by a user and classifying said additional strokes as additional possible characters;

grouping successive possible characters into combinations having word-break spaces at different respective locations between the possible characters to form word hypotheses, and assigning a weight value to each word hypothesis based upon a geometric relationship between the strokes comprising the possible characters;

searching the hypotheses having the highest weight values, relative to a dictionary of recognized words; and

selecting the hypothesis whose combination of characters and word break spaces most closely matches entries in the dictionary.

12. The method of claim 11 wherein said geometric relationship is the spacing between strokes.

13. A method for identifying words within handwritten characters, comprising the steps of:

receiving strokes entered by a user and classifying one or more strokes as a possible character;

receiving additional strokes entered by a user and classifying said additional strokes as a second possible character;

grouping said two possible characters into combinations having word-break spaces at different respective locations between the possible characters to form word hypotheses, and assigning a weight value to each word hypothesis based upon a geometric relationship between the strokes comprising the two possible characters;

receiving additional strokes entered by the user and classifying said additional strokes as successive possible characters;

after each successive possible character is classified, forming additional word hypothesis having word-break spaces at different respective locations between the possible characters, and assigning a weight value to each word hypothesis;

searching the hypotheses having the highest weight values, relative to a dictionary of recognized words; and

selecting the hypothesis whose combination of characters and word break spaces most closely matches entries in the dictionary.