Universal symbolic handwriting recognition system

• US 5,454,046 A
• Filed: 09/17/1993
• Issued: 09/26/1995
• Est. Priority Date: 09/17/1993
• Status: Expired due to Term

• Current Assignee: Fficiency Software Incorporated
• Original Assignee: Penkey Corporation
• Inventors: Carman, Frank C. II
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US08/123,609
• Time in Patent Office: 739 Days
• Field of Search: 382/13, 382/24, 382/30, 382/34, 178/18
• US Class Current: 382/186
• CPC Class Codes: G06V 30/196 using sequential comparisons of the image signals with a plurality of references
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet

Abstract

A universal symbolic handwriting recognition system for converting user entered time ordered stroke sequences into computer readable text is described. The system operates on two levels: (1) a word-level recognizer, which recognizes the entire group of strokes as a unit, and (2) a parser-level recognizer, which breaks the strokes into segments and recognizes groups of stroke segments within a word, thus recognizing separate characters or character sequences within a word to build a complete recognition string. In both recognition levels, the system trains on actual user samples, either on an entire word, or on a character or character sequence within a word. It does so by building a user specific sample recognition data-base file of text/pattern pairs, where the text is specified by the user in a word confirmation process and the pattern, composed of an index and a feature vector, is created from the actual user input strokes. Thus, as the user continues to use the recognition system and augments his/her user specific sample recognition data-base file, the correct recognition rate climbs approaching 100 percent in normal usage. The word-level recognizer can also be used to train on abbreviations, custom shorthands, and pictographic characters, such as the Japanese Kanji, or Chinese. An abbreviated Japanese Kanji or Chinese handwritten entry can even be trained for recognition. The text in the user specific sample data-base file is maintained in the Unicode format, and the user can specify the recognized return string format as either Unicode, ANSI, or JIS.

Claims

1. A system for the symbolic-based recognition of a handwriting input to an input surface having an output provided as a stream of coordinate data points, comprising:

a data base memory storing a compilation of text-pattern pairs, said pattern of each pair having been derived as sample features of said handwriting and including an associated sample index derived as aspects of said handwriting sample features, said text of each said pair representing at least one predetermined character glyph;

a processor, responsive to said output to extract pattern test features and a corresponding test index therefrom, responsive to access said memory stored compilation and identify a said sample index corresponding with said test index, responsive to carry out a comparison of said pattern test features with said pattern sample features associated with said identified sample index, responsive in the presence of a correspondence between said pattern test and sample features to derive output signals corresponding with said text associated with said pattern sample features;

said pattern sample and test features including index based features derived from the stroke defining sequences of said data points representing a word and comprising

a first index component provided as a value corresponding with the total number of strokes comprising a word,

a second index component provided as a value corresponding with the number of inflection points of a stroke, wherein such inflection points comprise a significant bend in a stroke, a top location, a bottom location and a baseline crossing point in the stroke, and

a third index component provided as a value corresponding with the termination of inflection point index components for a given stroke; and

display means responsive to said derived output signals for effecting the publication of a said predetermined character glyph of said text associated with said pattern sample features.

2. The system of claim 1 in which said pattern sample and test features include:

a first word feature provided as a value corresponding with the relative word bottom location of a said output representing a word;

a second word feature provided as a value corresponding with the relative height of a said output representing a word; and

a third word feature provided as a value corresponding with the aspect ratio of a said output representing a word.

3. The system of claim 1 in which said pattern sample and test features include stroke based features derived from each stroke defining sequence of said data points and comprising:

a first stroke feature provided as a value corresponding with the worm moment based average moment of a stroke;

a second stroke feature provided as a value corresponding with the aspect ratio of a stroke; and

a third stroke feature provided as a value corresponding with the beginning and ending locations of a stroke relative to a dimension of a word within which such stroke is incorporated.

4. The system of claim 1 in which said pattern sample and test features include segment based features derived from each segment of each stroke defining sequence of said data points and comprising:

a first segment feature provided as a value corresponding with the accumulated distances between sequential pairs of said data points defining a stroke from the beginning of a stroke to the end of a segment of a stroke, relative to the total distance from the beginning of the stroke to the end of the stroke;

a second segment feature provided as a value corresponding with the x-coordinate overlap between two adjacent segments of a stroke; and

a third segment feature provided as a value corresponding with the relative x-coordinate based distance between adjacent inflection points of a stroke.

5. The system of claim 1 in which said pattern sample and test features include segment based features derived from each segment of each stroke defining sequence of said data points and comprising:

a fourth segment feature provided as a value corresponding with the absolute inflection point x-coordinate;

a fifth segment feature provided as a value corresponding with the absolute inflection point y-coordinate;

a sixth segment feature provided as a value corresponding with the x curvature of a segment of a said stroke; and

a seventh segment feature provided as a value corresponding with the y curvature of a segment of a said stroke.

6. The system of claim 1 in which said pattern sample and test features include signature verification features derived from each word defining sequence of said data points and comprising:

a first signature verification feature provided as a value corresponding with the relative interval of time taken to write the word.

7. The system of claim 1 in which said pattern sample and test features include stroke based signature verification features derived from each stroke defining sequence of said data points and comprising:

a second signature verification feature provided as a value corresponding with the relation between the beginning time of a stroke and the interval of time taken to write the word; and

a third signature verification feature provided as a value corresponding with the relation between the ending time of a stroke and the interval of time taken to write the word.

8. The system of claim 1 in which said pattern sample and test features include segment based signature verification features derived from each segment of each stroke defining sequence of said data points and comprising:

a fourth signature verification feature provided as a value corresponding with the relation between the interval of time taken to write a segment and the interval of time taken to write a stroke.

9. The system of claim 1 in which said processor is responsive to effect a search of all sample patterns to find those sample patterns whose pattern index features are the same as the index features of said test pattern in order to effect a comparison between the test pattern features and the sample pattern features.

10. The system of claim 1 in which said processor is responsive to effect said comparison by deriving a feature match value corresponding with the deviation of said pattern test features from said pattern sample features and is responsive to derive said output signals when said feature match value is as great as a predetermined recognition cutoff value.

11. The system of claim 10 in which said processor is responsive to generate a new said text-pattern pair corresponding with user entered text and associated said pattern test features and enter said new text pattern pair into said database memory when said feature match value is below said predetermined recognition cutoff value.

12. A system of claim 10 in which said processor is responsive when said feature match value is less than said predetermined recognition cutoff value to enter a search tree based parser mode to extract first pattern stroke and stroke segment features and a corresponding test index therefrom wherein each stroke segment is delimited by either a stroke beginning point ending point or by a stroke inflection point that is close to a baseline, is responsive to carry out a comparison of said first pattern test features with said pattern sample features associated with said identified sample index, responsive in the presence of a correspondence between said first pattern test features and said sample features to derive a first text character sequence result, responsive to selectively combine said stroke and stroke segment features to provide second pattern test features, responsive to carry out a comparison of said second pattern test features with said pattern sample features associated with said identified sample index, and responsive in the presence of a correspondence between said second pattern test features and said sample features to derive output signals corresponding with said text;

and

display means responsive to said derived output signals for effecting the publication of a said predetermined character sequence of said text associated with said pattern sample features.

13. The method for generating and displaying text corresponding with a stream of coordinate data points generated as the output of a stylus responsive user handwriting input device, comprising the steps of:

storing a compilation of text-pattern pairs in memory, each said pair having been derived as sample features of said handwriting and including an associated sample index derived as aspects of said handwriting sample features, said text of each said pair representing at least one predetermined character glyph;

extracting pattern test features from a stream of said coordinate data points and forming a corresponding test index including the steps of;

determining bounding box parameters for a word defining sequence of said coordinate data points,

scanning said word defining coordinate data points and determining word crossings corresponding to each scan line therewith,

determining a base line for said word defining sequence of data coordinate points,

determining bounding box parameter for each stroke of said word defining sequence of said coordinate data points,

determining the aspect ratio of each said stroke wherein such stroke aspect ratio generally is determined to be K/π

*ARCTAN (stroke-height/stroke-width) where K is a constant,

determining the aspect ratio of said word, wherein such word aspect ratio generally is derived as K (height/diagonal) where K is a constant, height is word height and diagonal is the square root of the height squared plus the width squared,

determining the relative bottom location of said word, and

determining the relative height of said word;

accessing said compilation and identifying a said sample index corresponding with said test index;

accessing said pattern sample features corresponding with said identified sample index and comparing said accessed pattern sample features with said pattern test features;

accessing the said text corresponding with said accessed pattern sample features in the event said comparison derives an acceptable correspondence between said accessed pattern sample features and said pattern test features; and

displaying said accessed text.

14. The method of claim 13 including the steps of:

acquiring text associated with said pattern test features when a said sample index is not identified to correspond with said test index; and

storing said pattern test features with said acquired text and said test index in said memory as additional said text-pattern pairs.

15. The method of claim 13 including the steps of:

acquiring text associated with said pattern test features when said comparison results in an unacceptable correspondence between said accessed pattern sample features and said pattern test features; and

storing said pattern test features with said acquired text and said test index in said memory as additional said text-pattern pairs.

16. The method for generating and displaying text corresponding with a stream of coordinate data points generated as the output of a stylus responsive user handwriting input device, comprising the steps of:

storing a compilation of text-pattern pairs in memory, each said pair having been derived as sample features of said handwriting and including an associated sample index derived as aspects of said handwriting sample features, said text of each said pair representing at least one predetermined character glyph;

extracting pattern test features from a stream of said coordinate data points and a corresponding test index, including the steps of;

carrying out an extrapolation between a sequence of said coordinate data points defining a stroke and deriving a representation of a sequence of data points which are uniformly spaced along the locus thereof defining said strokes, and

determining worm moments of said stroke evaluating a select, progressive sequence of a predetermined number of positions of said data points;

accessing said compilation and identifying a said sample index corresponding with said test index;

accessing said pattern sample features corresponding with said identified sample index and comparing said accessed pattern sample features with said pattern test features;

accessing the said text corresponding with said accessed pattern sample features in the event said comparison derives an acceptable correspondence between said accessed pattern sample features and said pattern test features; and

displaying said accessed text.

17. The method of claim 16 in which said step for extracting pattern test features includes the steps of:

deriving the average value of said predetermined worm moment of said stroke; and

determining the location of stroke bends from said worm moment of said stroke.

18. The method of claim 16 in which said step for extracting pattern test features includes the steps of:

determining the location of inflection points by finding the tops and bottoms of a stroke defining sequence of said representation of coordinate data points;

determining the location of inflection points by deriving the locations of points of crossing of a base line extending through said representation of coordinate data points; and

determining the location of inflection points by locating peak values of said worm moments.

19. The method of claim 18 in which said step for extracting pattern test features includes the step of determining the percentage of horizontal, x-coordinate overlap between two contiguous stroke segments as defined by stroke endings and said inflection points.

20. A system for the symbolic-based recognition of a handwriting input to an input surface having an output provided as a stream of coordinate data points, comprising:

a data base memory storing a compilation of text-pattern pairs, said pattern of each said pair having been derived as sample features of said handwriting and including an associated sample index derived as aspects of said handwriting sample features, said text of each said pair representing at least one predetermined character glyph;

a processor, responsive to said output to extract pattern test features and a corresponding test index therefrom, responsive to access said memory stored compilation and identify a said sample index corresponding with said test index, responsive to carry out a comparison of said pattern test features with said pattern sample features associated with said identified sample index, responsive in the presence of a correspondence between said pattern test and sample features to derive output signals corresponding with said text associated with said pattern sample features,

said pattern symbols and test features including;

a first word feature provided as a value corresponding with the word bottom location relative to the word base line of a said output representing a word, said relative word bottom being determined to be K* ((y_max +line-space)/(2*line-space)) where y_max is the visually lowest part of such word measured from the baseline, line-space is a selected spacing between writing lines and K is a constant,

a second feature word provided as a value corresponding with the relative height of a said output representing a word, and

a third word feature provided as a value corresponding with the aspect ratio of a said output representing a word, said word aspect ratio generally being determined to be K (height/diagonal) where K is a constant, height is word height, and diagonal is the square root of the height squared plus the width squared; and

display means responsive to said derived output signals for effecting the publication of a said predetermined character glyph sequence of said text associated with said pattern sample features.

21. The system of claim 20 in which said pattern and test features include stroke based features derived from each stroke defining sequence of said data points and comprising:

a first stroke feature provided as a value corresponding with the average worm moment based moment of a stroke;

a second stroke feature provided as a value corresponding with the aspect ratio of a stroke; and

a third stroke feature provided as a value corresponding with the beginning and ending locations of a stroke relative to a dimension of a word within which such stroke is incorporated.

22. The system of claim 20 in which said pattern sample and test features include segment based features derived from each segment of each stroke defining sequence of said data points and comprising:

a first segment feature provided as a value corresponding with the accumulated distances between sequential pairs of said data points defining a stroke from the beginning of a stroke to the end of a segment of a stroke relative to the total distance from the beginning of the stroke to the end of the stroke;

a second segment feature provided as a value corresponding with the x-coordinate overlap between two adjacent segments of a stroke; and

a third segment feature provided as a value corresponding with the relative x-coordinate based distance between adjacent inflection points of a stroke.

23. The system of claim 20 in which said pattern sample and test features include segment based features derived from each segment of each stroke defining sequence of said data points and comprising:

a fourth segment feature provided as a value corresponding with the absolute inflection point x-coordinate relative to the stroke'"'"'s bounding box;

a fifth segment feature provided as a value corresponding with the absolute inflection point y-coordinate relative to the stroke'"'"'s bounding box;

a sixth segment feature provided as a value corresponding with the x curvature of a segment of a said stroke; and

a seventh segment feature provided as a value corresponding with the y curvature of a segment of a said stroke.

24. The system of claim 20 in which said pattern sample and test features include signature verification features derived from each word defining sequence of said data points and comprising:

a first signature verification feature provided as a value corresponding with the relative interval of time taken to write the word.

25. The system of claim 20 in which said pattern sample and test features include stroke based signature verification features derived from each stroke defining sequence of said data points and comprising:

a second signature verification feature provided as a value corresponding with the relation between the beginning time of a stroke and the interval of time taken to write the word; and

a third signature verification feature provided as a value corresponding with the relation between the ending time of a stroke and the interval of time taken to write the word.

26. The system of claim 20 in which said pattern sample and test features include segment based signature verification features derived from each segment of each stroke defining sequence of said data points and comprising:

a fourth signature verification feature provided as a value corresponding with the relation between the interval of time taken to write a segment and the interval of time taken to write a stroke.

27. A system for the symbolic-based recognition of a handwriting input to an input surface having an output provided as a stream of coordinate data points, comprising:

a data base memory storing a compilation of text-pattern pairs, said pattern of each said pair having been derived as sample features of said handwriting and including an associated sample index derived as aspects of said handwriting sample features, said text of each said pair representing at least one predetermined character glyph;

a processor, responsive to said output to extract pattern test features and a corresponding test index therefrom, responsive to access said memory stored compilation and identify a said sample index corresponding with said test index, responsive to carry out a comparison of said pattern test features with said pattern sample features associated with said identified sample index, responsive in the presence of a correspondence between said pattern test and sample features to derive output signals corresponding with said text associated with said pattern sample features,

wherein said pattern sample and test features include stroke based features derived from each stroke defining sequence of said data points and comprising;

a first stroke feature provided as a value corresponding with the average worm moment based moment of stroke,

a second stroke feature provided as a value corresponding with the aspect ratio of a stroke, said stroke aspect ratio generally being determined to be K/π

* ARCTAN (stroke-height/stroke-width) where K is a constant, and

a third stroke feature provided as a value corresponding with the beginning and ending locations of a stroke relative to a dimension of a word within which such stroke is incorporated, said third stroke feature for the general case being expressed as;

x₀ =K (x_b -x_min)/(x_max -x_min) and

x₁ =K (x_e -x_min)/(x_max x_min),

y₀ =K (y_b -y_min)/(y_max y_min) and

y₁ =K (y_e -y_min)/(x=y_max y_min),

where x₀, y₀ are the stroke'"'"'s respective beginning x- and y- coordinate features, x₁, y₁ are the strokes respective ending x- and y- coordinate features x_b, y_b are the stroke'"'"'s beginning respective x- and y- coordinate values, x_min, y_min are the word'"'"'s minimum respective x- and y- coordinates, x_max, y_max are the word'"'"'s maximum respective x- and y- coordinates, and x_e, y_e are the stroke'"'"'s respective x- and y- ending coordinate values; and

display means responsive to said derived output signals for effecting the publication of a said predetermined character glyph sequence of said text associated with said pattern sample features.

28. The system of claim 27 in which said pattern sample and test features include segment based features derived from each segment of each stroke defining sequence of said data points and comprising:

a first segment feature provided as a value corresponding with the accumulated distances between sequential pairs of said data points defining a stroke from the beginning of a stroke to the end of a segment of a stroke relative to the total distance from the beginning of the stroke to the end of the stroke;

a second segment feature provided as a value corresponding with the x-coordinate overlap between two adjacent segments of a stroke; and

a third segment feature provided as a value corresponding with the relative x-coordinate based distance between adjacent inflection points of a stroke.

29. The system of claim 27 in which said pattern sample and test features include segment based features derived from each segment of each stroke defining sequence of said data points and comprising:

a fourth segment feature provided as a value corresponding with the absolute inflection point x-coordinate relative to the stroke'"'"'s bounding box;

a fifth segment feature provided as a value corresponding with the absolute inflection point y-coordinate relative to the stroke'"'"'s bounding box;

a sixth segment feature provided as a value corresponding with the x curvature of a segment of a said stroke; and

a seventh segment feature provided as a value corresponding with the y curvature of a segment of a said stroke.

30. The system of claim 27 in which said pattern sample and test features include signature verification features derived from each word defining sequence of said data points and comprising:

a first signature verification feature provided as a value corresponding with the relative interval of time taken to write the word.

31. The system of claim 27 in which said pattern sample and test features include stroke based signature verification features derived from each stroke defining sequence of said data points and comprising:

a second signature verification feature provided as a value corresponding with the relation between the beginning time of a stroke and the interval of time taken to write the word; and

a third signature verification feature provided as a value corresponding with the relation between the ending time of a stroke and interval of time taken to write the word.

32. The system of claim 27 in which said pattern sample and test features include segment based signature verification features derived from each segment of each stroke defining sequence of said data points and comprising:

a fourth signature verification feature provided as a value corresponding with the relation between the interval of time taken to write a segment and the interval of time taken to write a stroke.

33. A system for the symbolic-based recognition of a handwriting input to an input surface having an output provided as a stream of coordinate data points, comprising:

a data base memory storing a compilation of text-pattern pairs, said pattern of each pair having been derived as sample features of said handwriting and including an associated sample index derived as aspects of said handwriting sample features, said text of each said pair representing at least one predetermined character glyph;

a processor, responsive to said output to extract pattern test features and a corresponding test index therefrom, responsive to access said memory stored compilation and identify a said sample index corresponding with said test index, responsive to carry out a comparison of said pattern test features with said pattern sample features associated with said identified sample index, responsive in the presence of a correspondence between said pattern test and sample features to derive output signals corresponding with said text associated with said pattern sample features;

said pattern sample and test features including segment based features derived from each segment of each stroke defining sequence of said data points and comprising;

a first segment feature provided as a value corresponding with the accumulated distances between sequential pairs of said data points defining a stroke from the beginning of a stroke to the end of a segment of a stroke relative to the total distance from the beginning of the stroke to the end of the stroke,

a second segment feature provided as a value corresponding with the x-coordinate overlap between two adjacent segments of a stroke, and

a third segment feature provided as a value corresponding with the relative x-coordinate based distance between adjacent inflection points of a stroke, wherein such inflection points comprise a significant bend in a stroke, a top location, a bottom location, and a baseline crossing point in the stroke; and

display means responsive to said derived output signals for effecting the publication of a said predetermined character glyph sequence of said text associated with said pattern sample features.

34. The system of claim 33 in which said pattern sample and test features include segment based features derived from each segment of each stroke defining sequence of said data points and comprising:

a fourth segment feature provided as a value corresponding with the absolute inflection point x-coordinate relative to the stroke'"'"'s bounding box;

a fifth segment feature provided as a value corresponding with the absolute inflection point y-coordinate relative to the stroke'"'"'s bounding box;

a sixth segment feature provided as a value corresponding with the x curvature of a segment of a stroke; and

a seventh segment feature provided as a value corresponding with the y curvature of a segment of a said stroke.

35. The system of claim 33 in which said pattern sample and test features include signature verification features derived from each word defining sequence of said data points and comprising:

a first signature verification feature provided as a value corresponding with the relative interval of time taken to write the word.

36. The system of claim 33 in which said pattern sample and test features include stroke based signature verification features derived from each stroke defining sequence of said data points and comprising:

a second signature verification feature provided as a value corresponding with the relation between the beginning time of a stroke and the interval of time taken to write the word; and

a third signature verification feature provided as a value corresponding with the relation between the ending time of a stroke and the interval of time taken to write the word.

37. The system of claim 33 in which said pattern sample and test features include segment based signature verification features derived from each segment of each stroke defining sequence of said data points and comprising:

a fourth signature verification feature provided as a value corresponding with the relation between the interval of time taken to write a segment and the interval of time taken to write a stroke.

38. A system for the symbolic-based recognition of a handwriting input to an input surface having an output provided as a stream of coordinate data points, comprising:

a data base memory storing a compilation of text-pattern pairs, said pattern of each said pair having been derived as sample features of said handwriting and including an associated sample index derived as aspects of said handwriting sample features, said text of each said pair representing at least one predetermined character glyph;

a processor responsive to said output to extract pattern test features and a corresponding test index therefrom, responsive to access said memory stored compilation and identify a said sample index corresponding with said test index, responsive to carry out a comparison of said pattern test features with said pattern sample features associated with said identified sample index, responsive in the presence of a correspondence between said pattern test and sample features to derive output signals corresponding with said text associated with said pattern sample features;

said pattern sample and test features including segment based features derived from each segment of each stroke defining sequence of said data points and comprising;

a first segment feature provided as a value corresponding with the absolute inflection point x-coordinate, said absolute inflection point x-coordinate being a function of the difference of the x-coordinate distance of the inflection point from the minimum x-coordinate value of a stroke to the x-coordinate span of such stroke,

a second segment feature provided as a value corresponding with the absolute inflection point y-coordinate, said absolute inflection point y-coordinate being a function of the difference of the y-coordinate distance of the inflection point from the minimum y-coordinate value of a stroke to the y-coordinate span of such stroke,

a third segment feature provided as a value corresponding with the x curvature of a segment of a said stroke relative to the stroke'"'"'s bounding box, and

a fourth segment feature provided as a value corresponding with the y curvature of a segment of a said stroke relative to the stroke'"'"'s bounding box; and

display means responsive to said derived output signals for effecting the publication of a said predetermined character glyph of said text associated with said pattern sample features.

39. The system of claim 38 in which said pattern sample and test features include signature verification features derived from each word defining sequence of said data points and comprising:

a first signature verification feature provided as a value corresponding with the relative interval of time taken to write the word.

40. The system of claim 38 in which said pattern sample and test features include stroke based signature verification features derived from each stroke defining sequence of said data points and comprising:

a second signature verification feature provided as a value corresponding with the relation between the beginning time of a stroke and the interval of time taken to write the word; and

a third signature verification feature provided as a value corresponding with the relation between the ending time of a stroke an the interval of time taken to write the word.

41. The system of claim 38 in which said pattern sample and test features include segment based signature verification features derived from each segment of each stroke defining sequence of said data points and comprising:

a fourth signature verification feature provided as a value corresponding with the relation between the interval of time taken to write a segment and the interval of time taken to write a stroke.