Image analysis – Pattern recognition – Unconstrained handwriting
Reexamination Certificate
1996-10-15
2002-01-15
Johns, Andrew W. (Department: 2621)
Image analysis
Pattern recognition
Unconstrained handwriting
C382S201000
Reexamination Certificate
active
06339655
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to pattern recognition systems in general and to systems for recognizing handwritten patterns, such as letters, numbers and signatures, in particular.
BACKGROUND OF THE INVENTION
Various pattern recognition systems are known in the art and they have varying degrees of success at recognition. These systems typically assume some particular structure of the characters (patterns) under investigation and utilize the structure to improve their recognition ability. For example, Kanji characters are formed of a plurality of strokes, defined as the points between pen-down and pen-up, where some characters have more strokes than others.
An example prior art system is shown in
FIG. 1
to which reference is now made. It typically includes a digitizer
10
, a segmenter
12
, a feature extractor
14
, a classifier
16
and a reference character database
18
. The digitizer
10
converts an input pattern into a series of paired position (x,y) and sometimes also pressure P coordinates of sample points along the stroke. The segmenter
12
divides the input pattern into separate characters (i.e. if the input pattern was a handwritten “the”, the segmenter
12
would divide the separate strokes into the characters “t”, “h” and “e”). The feature extractor
14
extracts the features of each character and transforms each character into a standard format. The classifier
16
then compares the standardized input character against the standardized reference characters stored in the reference database
18
. The reference character which has the best match, by some criterion or criteria, is output as the recognized character.
U.S. Pat. No. 3,930,229 to Crane et al. describes a system for identifying handwritten characters which codes the motion a pen follows when writing a character. Each character is defined as a sequence of primal directions, namely, up, down, rig However, the primal directions, without any other information, are not sufficient a result, the system is vulnerable to writing styles, noise and normal writing variation.
U.S. Pat. No. 4,284,975 to Odaka describes a handwriting identification system which takes the sample points of each stroke of each character and replaces them with two to five “feature points” which are equidistant points along the stroke. The distances between each feature point of the input pattern and its corresponding feature point of the patterns in the reference library are determined and the sum of the distances determined. The reference pattern with the smallest accumulated distance is the recognized character. This method is useful for characters formed of many relatively simple strokes, like Kanji characters but is not descriptive enough for general use and for complex, curved strokes.
U.S. Pat. No. 4,561,105 to Crane et al. describes a system where each stroke of a handwritten character is approximated by a polygon formed by connecting a fixed number of vertices at equidistant intervals. The angle of each polygon segment is calculated and is stored as a feature. The matching metric is defined as the sum of the differences between each angle in the input pattern and its corresponding angle in the reference pattern against which it is matched. The smallest value of the metric defines the recognized character.
The system of '105 cannot separate the noise in a character from the signal itself. For example, the system of '105 might define a handwritten “v” as a “u” since most of the equidistant vertices will fall on either side of the sharp angle change of the “v”. It will also have trouble with other symbols for the same reasons. A further drawback of the system of '105 is that the number of vertices is fixed while, in reality, the number of vertices which is appropriate is highly dependent on the specific writing style of each user.
U.S. Pat. No. 4,190,820 also to Crane et al. describes a handwriting recognition system useful for recognizing signatures. The system compares strokes of a signature where the strokes are defined as extending between two landmarks, the pen-down and pen-up moments. The strokes are stretched or contracted, and translated to match corresponding strokes in the reference data.
SUMMARY OF THE PRESENT INVENTION
Applicants have realized that handwritten patterns, which include characters, symbols and signatures, have “stable points” through which a writer always moves when he writes the pattern. In effect, the stable points are the points by which a writer defines the pattern in his mind. For example, a “3” always has two curves which come together at a point, whether or not the two curves overlap or cross. The intersection point of the two curves is a stable point for the number “3”.
It is an object of the present invention to provide a handwriting recognition system which extracts the stable points of strokes of a pattern, where a stroke is defined as the sample points between pen-down and pen-up. The system of the present invention includes a stable point extractor to extract the stable points of strokes and a classifier which utilizes the stable points to divide a stroke, of both an input and of reference patterns, into substrokes. The classifier then compares the input and reference substrokes to each other. As a result of the substroke creation, the system of the present invention compares substrokes of a pattern which are likely to have similar shapes.
It is noted that, if an input pattern is comprised of more than one stroke, the handwriting recognition system of the present invention only compares it with reference patterns having the same number of strokes, performing the stroke classification between the strokes of the input pattern with their corresponding strokes of the reference patterns.
The classifier preferably includes a comparison point apparatus for generating a multiplicity of comparison points which divide the substroke into a multiplicity of equal length intervals and for storing the local angle of the tangent at each comparison point. The classifier typically also includes a substroke comparison apparatus for generating, for each substroke, a value describing the comparison of the tangent angles of the comparison points of the input substroke with those of the corresponding reference substroke. Finally, the classifier typically also includes a matching apparatus for producing a match value describing the comparison over the whole stroke and over the whole pattern, if it is a multi-stroke pattern.
In one embodiment of the present invention, the substroke comparison apparatus generates differences between corresponding tangent angles of comparison points of the input substroke and the reference substroke. The match value is the sum, non-modulo
360
of the differences. Furthermore, the matching apparatus normalizes the match value for each substroke by the percentage of the entire stroke which the substroke occupies. The match value for the whole of the current reference pattern is the sum of the normalized totals. For multi-stroke patterns, the stroke match value is normalized by the percentage of the entire pattern which the stroke occupies and the pattern match value is the sum of the normalized stroke match values. The reference pattern with the smallest matching metric is the matched pattern.
The classifier can divide the stroke into substrokes in a number of ways and therefore, can be formed of any of a number of different matchers. A whole stroke matcher defines the entire stroke as being formed of only one substroke. A substroke matcher compares input strokes to those reference strokes having the same number M of stable points. A dynamic matcher matches the input stroke of M stable points to those reference strokes having M−k to M+k (k typically being less than 5) stable points and is useful since sometimes, a stable point is generated indicating a substroke, such as a serif, which is not a standard part of the pattern. For a given reference stroke having k more or k less stable points than the input stroke, the dynamic matcher repeats
Aharonson Eran
Davidor Yuval
Davidov Doron
Ilan Gabriel
Art Advanced Recognition Technologies Inc.
Eitan Pearl Latzer & Cohen-Zedek
Johns Andrew W.
LandOfFree
Handwriting recognition system using substroke analysis does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Handwriting recognition system using substroke analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Handwriting recognition system using substroke analysis will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2859089