Handwritten character recognition using multi-resolution models

• US 6,226,403 B1
• Filed: 02/09/1998
• Issued: 05/01/2001
• Est. Priority Date: 02/09/1998
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Parthasarathy, Kannan
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/020,838
• Time in Patent Office: 1,177 Days
• Field of Search: 382/159, 382/178, 382/187, 382/189, 382/227, 382/228, 382/192, 382/202, 345/171, 345/173, 345/179
• US Class Current: 382/187
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

A storage medium (72) having stored thereon a set of instructions, which when loaded into a microprocessor (74), causes the microprocessor (74) to extract strokes from a plurality of characters (76), derive a pre-defined number of stroke models based on the strokes extracted from the plurality of character (78) and represent the plurality of characters as sequences of stroke models (80).

Claims

1. A method of recognizing handwritten characters comprising:

receiving handwritten input comprising a plurality of strokes;

computing a set of features for each stroke in the handwritten input;

storing a pre-determined number of stroke models, the number of stroke models required to define a character being inversely proportional to the number of strokes required to create the character;

storing character models for a plurality of characters, the character models being comprised of stroke models wherein the stroke models are derived by a clustering analysis of strokes collected from the plurality of characters and wherein the clustering analysis comprises;

determining a pre-defined number of stroke models;

computing, for each stroke in the handwritten input, a distance measurement between a stroke and a nearest stroke model;

separating a fixed percentage of strokes that have a highest number of modeling errors;

using the fixed percentage of strokes that have the highest number of modeling errors to derive additional stroke models by clustering; and

repeating the separating and using steps more than once; and

computing a distance measurement between strokes of the handwritten input and stroke models of a character model.

2. The method according to claim 1 wherein character models are derived to account for variations in stroke order, stroke shape and a number of strokes.

3. The method according to claim 1 wherein a stylus down stroke and a stylus up stroke are treated equally with reference to a stroke model.

4. The method according to claim 1 wherein character models are determined through statistical analysis of a large number of handwritten samples from different writers.

5. The method according to claim 1 wherein the set of features for each stroke in the handwritten input describes a shape of a stroke and a size of the stroke.

6. The method according to claim 5 wherein the size of the stroke is based on a width and a height of a bounding box of the stroke.

7. The method according to claim 5 wherein the shape of the stroke is derived by the following steps:

dividing the stroke into twelve segments, having endpoints, with equal arc length;

joining the endpoints of each of the twelve segments with straight lines; and

computing angles of the straight lines that join the endpoints of each of the twelve segments.

8. The method according to claim 1 wherein the pre-determined number of stroke models is no more than 256 stroke models.

9. A method of handwritten character recognition using multi-resolution models, the method comprising:

storing a plurality of character models in a plurality of memory blocks, wherein a memory block contains character models with an identical number of strokes;

determining a number of strokes in a handwritten input;

storing a pre-determined number of stroke models corresponding to the handwritten input, the number of stroke models required to define a character being inversely proportional to the number of strokes required to create the character, the character models being comprised of stroke models;

selecting an appropriate memory block corresponding to the number of strokes in the handwritten input;

calculating a distance measurement to the plurality of characters models in the appropriate memory block to create an array of distances;

sorting the array of distances to create a sorted list;

selecting at least one candidate in the sorted list; and

reporting the at least one candidate in the sorted list.

10. The method according to claim 9 wherein the plurality of character models are expressed in terms of strokes selected from at least one pre-defined set of stroke models, wherein each pre-defined set of stroke models is comprised of a finite number of stroke models.

11. The method according to claim 9 wherein the step of calculating a distance measurement to the plurality of character models in the appropriate memory block to create an array of distances comprises performing a look up procedure in a pre-computed distance matrix of individual stroke distances.

12. The method according to claim 9 further comprising storing stroke features directly whenever a distance measurement between a stroke and a nearest stroke model exceeds a threshold.

13. The method according to claim 9 wherein at least one character model is based on characters written with a standard number of strokes.

14. The method according to claim 9 wherein at least one character model is based on characters written with one stroke less than a standard number of strokes.

15. The method according to claim 9 wherein multiple character models are stored for a character to account for variations in writing style.