Method and system for recognizing a boundary between characters in handwritten text

• US 5,818,963 A
• Filed: 11/04/1996
• Issued: 10/06/1998
• Est. Priority Date: 09/09/1994
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Société Des Céramiques Techniques
• Inventors: Murdock, Michael, Wang, Shay-Ping T.
• Primary Examiner(s): SHALWALA, BIPIN H
• Application Number:
  US08/743,332
• Time in Patent Office: 701 Days
• Field of Search: 382/159, 382/173, 382/177, 382/178, 382/179, 382/186, 382/187, 382/190, 382/199, 382/203, 382/120, 382/122, 382/241, 382/242, 382/224, 382/225, 382/228, 382/156, 382/227, 395/21
• US Class Current: 382/187
• CPC Class Codes: G06F 18/2453 non-linear, e.g. polynomial classifier
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32
• CPC Class Codes: G06V 30/153 using recognition of characters or words
• CPC Class Codes: G06V 30/2268 using stroke segmentation
• CPC Class Codes: G06V 30/248 involving plural approaches, e.g. verification by template match; Resolving confusion among similar patterns, e.g. "O" versus "Q" G06V30/242 takes precedence
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context
• CPC Class Codes: G06V 30/333 Preprocessing; Feature extraction
• CPC Class Codes: G06V 30/36 Matching; Classification

Abstract

A method and system for identifying boundaries of characters in handwritten text by classifying segment strokes provides improved performance in a handwriting recognition system. A segment stroke is a portion of handwritten text which includes a boundary between two characters. The segment stroke is recognized by the same method used to recognized characters. Recognition of a segment stroke is accomplished by training a learning machine to act as a classifier which implements a discriminant function based on a polynomial expansion.

Claims

1. A handwriting recognition system, comprising:

a feature extractor for extracting a plurality of features from cursive handwriting, the cursive handwriting comprising a plurality of characters and a segment stroke between the plurality of characters; and

a boundary classifier for generating a boundary classifier output signal based on the plurality of features, a plurality of discriminant function coefficients, and a discriminant function, wherein the plurality of discriminant function coefficients are derived from a plurality of cursive segment stroke examples, each of the cursive segment stroke examples connecting the end point of a first cursive character to the start point of a second cursive character

wherein the discriminant function has a form ##EQU2## Wherein y represents the boundary classifier output signal;

wherein I, m, and n are integers;

wherein wi-1 represents the plurality of discriminant function coefficients;

wherein x1, x2, . . . , xn represents the plurality of features; and

wherein g1i, . . . , gni represent a plurality of exponents of the discriminant function.

3. The handwriting recognition system of claim 1, wherein the boundary classifier comprises:

a plurality of computing elements for generating a plurality of discriminant function terms; and

a summing circuit for generating the boundary classifier output signal in response to the plurality of discriminant function terms.

4. The handwriting recognition system of claim 1, wherein at least one of the plurality of features is extracted while the cursive handwriting is being written.

5. The handwriting recognition system of claim 1, wherein the plurality of features are selected from angular velocity, curvilinear velocity, stroke angle, stroke curvature, Fourier coefficients, and a plurality of polynomial coefficients.

6. The handwriting recognition system of claim 1, further comprising:

a plurality of character classifiers for generating a plurality of character classifier output signals in response to the plurality of features; and

a selector for identifying the plurality of characters based on the plurality of character classifier output signals and the boundary classifier output signal.

7. The handwriting recognition system of claim 1, wherein the feature extractor generates the plurality of features by fitting a first order polynomial to a curvilinear velocity profile

8. The handwriting recognition system of claim 1, wherein the feature extractor generates the plurality of features by fitting a first order polynomial to an angular velocity profile

9. The handwriting recognition system of claim 1, further comprising:

a trainer, operatively coupled to the boundary classifier, for generating the plurality of discriminant function coefficients.

10. The handwriting recognition system of claim 1, wherein the plurality of discriminant function coefficients are derived using a technique selected from least-squares estimation and matrix inversion.

2. The handwriting recognition system 1, wherein the boundary classifier includes a neural network.

11. In a handwriting recognition system, a method for recognizing a character, the method comprising the steps of:

extracting a plurality of features from cursive handwriting, the cursive handwriting comprising a plurality of characters and a boundary between the plurality of characters;

generating the plurality of features by fitting a first order polynomial to a curvilinear velocity profile

space="preserve" listing-type="equation">v.sub.(k) =a.sub.0 +a.sub.1 v.sub.(k-1) +a.sub.2 v.sub.(k-2) +a.sub.3 v.sub.(k-3) ;

wherein v.sub.(k) represents the curvilinear velocity of a kth sample datum, v.sub.(-1) represents the curvilinear velocity of a (k-1)th sample datum, v.sub.(k-2) represents the curvilinear velocity of a (k-2)th sample datum, v.sub.(k-3) represents the curvilinear velocity of a (k-3)th sample datum, k is an integer index, and a₀, a₁, a₂, and a₃ represent the plurality of features, and wherein the kth, (k-1)th, (k-2)th, and (k-3)th sample datum are derived from the cursive handwriting,

distributing the plurality of features to a plurality of character classifiers;

generating a plurality of character classifier output signals;

distributing the plurality of features to a boundary classifier;

,

generating a boundary classifier output signal by applying the plurality of features to a boundary discriminant function; and

identifying the character based on the plurality of character classifier output signals and the boundary classifier output signal.

12. The method of claim 11, wherein the step of extracting includes:

extracting at least one of the plurality of features while the cursive handwriting is being written.

13. The method of claim 11 wherein the plurality of features are selected from angular velocity, curvilinear velocity, stroke angle, stroke curvature, Fourier coefficients, and a plurality of polynomial coefficients.

14. In a handwriting recognition system, a method for recognizing a character, the method comprising the steps of:

extracting a plurality of features from cursive handwriting, the cursive handwriting comprising a plurality of characters and a boundary between the plurality of characters;

generating the plurality of features by fitting a first order polynomial to an angular velocity profile

space="preserve" listing-type="equation">v.sub.(k) =b.sub.0 +b.sub.1 v.sub.(k-1) +b.sub.2 v.sub.(k-2) +b.sub.3 v.sub.(k-3) ;

wherein v.sub.(k) represents the angular velocity of a kth sample datum, v.sub.(k-1) represents the angular velocity of a (k-1)th sample datum, v.sub.(k-2) represents the angular velocity of a (k-2)th sample datum, v.sub.(k-3) represents the angular velocity of a (k-3)th sample datum, k is an integer index, and b₀, b₁, b₂, and b₃ represent the plurality of features, and wherein the kth, (k-1)th, (k-2)th, and (k-3)th sample datum are derived from the cursive handwriting,

distributing the plurality of features to a plurality of character classifiers;

generating a plurality of character classifier output signals;

distributing the plurality of features to a boundary classifier;

generating a boundary classifier output signal by applying the plurality of features to a boundary discriminant function;

identifying the character based on the plurality of character classifier output signals and the boundary classifier output signal.

15. A handwriting recognition system, comprising:

a feature extractor for extracting a plurality of features from handwriting, the handwriting comprising a plurality of characters and a boundary between the plurality of characters;

a plurality of character classifiers for generating a plurality of character classifier output signals in response to the plurality of features;

a boundary classifier for generating a boundary classifier output signal by applying the plurality of features to a polynomial discriminant function;

wherein the polynomial discriminant function Y(X) has a form ##EQU3## wherein X={x₀, x₁, . . . , x_n } represents the plurality of features, Y represents the boundary classifier output signal, w_i represents a discriminant function coefficient, g_ji represents an exponent, and i, j, m and n are integers; and

a selector for identifying the plurality of characters based on the plurality of character classifier output signals and the boundary classifier output signal.

16. The handwriting recognition system of claim 15, wherein the plurality of classifier output signals are generated according to a plurality of polynomial discriminant functions.

18. The handwriting recognition system of claim 15, wherein at least one of the plurality of features is extracted while the handwriting is being written.

19. The handwriting recognition system of claim 15, wherein the plurality of features are selected from angular velocity, curvilinear velocity, stroke angle, stroke curvature, Fourier coefficients, and a plurality of polynomial coefficients.

20. The handwriting recognition system of claim 15, wherein the feature extractor generates a plurality of polynomial coefficients by fitting a first order polynomial to a curvilinear velocity profile

21. The handwriting recognition system of claim 15, wherein the feature extractor generates a plurality of polynomial coefficients by fitting a first order polynomial to an angular velocity profile

22. The handwriting recognition system of claim 15, wherein the boundary classifier comprises:

a plurality of computing elements for generating a plurality of polynomial discriminant function terms; and

a summing circuit for generating the boundary classifier output signal in response to the plurality of polynomial discriminant function terms.

17. The handwriting recognition system 15, wherein the boundary classifier includes a neural network.