Note: Descriptions are shown in the official language in which they were submitted.
21 62~ 89
METHOD OF STROKE SEGMENTATION
FOR HANDWRITTEN INPUT
Background of the Invention
Field of the Invention
This invention relates generally to handwriting recognition,
1 0 and more particularly to a method of stroke segmentation of
handwritten input.
Description of the Prior Art
1 5 MAçhine recognition of human handwriting is a very difficult
problem, and with the recent explosion of pen-based computing
devices, has become an important problem to be addressed. There
exist many very different approaches to this problem, but one useful
approach has been to divide the writing into a sequence of
2 0 filn~l~mental movements, or "strokes", and use the strokes (which
are parametrized in some way) as inputs to a character recognizer.
A key requirement in a stroke-based recognizer is that multiple
instances of the same character class (e.g. the letter "A" written at
different times and by different writers) should be divided into a
2 5 .simil~r set of strokes each time. This helps insure that recognition is
not too difficult, because the description of the character instances
will "look" simil~r to the character recognizer itself. In the ideal
case, all instances of a given character would always contain the
same~umber of strokes, the strokes would all be in the same relative
3 0 locations, and the featural descriptions of the strokes would all be
very .simil~r across the instances. This ideal is not achievable in
practice, but to the extent it can be approached, recognition accuracy
can be improved.
2 2162~89
In one technique in the prior art, stroke boundaries are set at
points where pen velocity in the vertical (or "y") direction is zero --
that is, at points where the writing begins moving upward, or begins
5 moving downward. The resulting set of strokes may then be called
"upstrokes" and "downstrokes". This method is discussed in
Mermelstein & Eden, "Experiments on Computer Recognition of
Connected Handwritten Words", in Information And Control vol. 7,
pp. 255-270, 1964. One problem with this method is that it is overly
l 0 sensitive to changes in the vertical direction, and not sensitive at all
to changes in the horizontal direction. Yet many characters are
composed of horizontal pieces -- for example, the cross of a "t" and the
three prongs of an "E" are normally much more horizontal than
vertical, even in sloppy writing. A y-velocity based stroke segmenter
l 5 will sometimes break a horizontal piece into one stroke, but often it
will be broken into two, three, or even many more, simply because of
small jitters of the pen in the vertical direction. This leads to poor
recognition accuracy, because multiple instances of the same
character will often be segmented into different-looking sets of
2 0 strokes. Attempts to correct the inaccuracies of this method,
including requiring a minimum vertical direction change before
creating a new stroke have had only limited success, and many of the
same basic problems still remain.
In another existing technique, this problem is solved by setting
2 5 the stroke boundaries at points where curvature is at a local
m~3~imum and exceeds some threshold value that corresponds to
sharp bends in the writing. Since a sharp bend can occur regardless
of the direction the pen is moving, this method is not sensitive to the
orientation of the various parts of handwritten input, such as words
3 0 or characters. However, the curvature-based technique has its own
problems as well. Suppose, for example, a person writes an "L" with
a very gradual bend, rather than a sharp bend, so that it starts to look
more like a "C". The method might fail to segment the "L" in this
case if the threshold curvature required for stroke boundaries was
3 5 not met. Simply lowering the threshold does not solve the problem,
- ` 3 2~ 62~89
because this can simply lead to excessive numbers of strokes. Having
too many extra strokes is just as bad as having too few, because again
it means that multiple instances of the same character are often
segmented into different types of strokes.
Accordingly a need exists for a stroke segmentation technique
- that is more accurate and not subject to the problems in the methods
discussed, such as the y-velocity method and the existing curvature
method.
1 0 Sllmm~ry of the Invention
Accordingly, the present invention provides a method of
segmenting handwritten input into strokes which are consistent in
number across multiple instances of each particular character class.
The present invention provides a method of segmenting
handwritten input into strokes which are ~imil~r in shape and
- location across multiple instances of each particular character class
of input.
Generally, the method of the present invention includes a step
2 0 of calculating the derivative, or instantaneous rate of change, of the
curvature at points in the handwritten input. The method then
selects as stroke boundary points certain points (or pixels) in the
input which lie between a point of high curvature derivative and a
succeeding point of low curvature derivative. Such boundary points
2 5 are not influenced by absolute curvature values, but rather only by
relative changes in the curvature.
- _ 4 2162~89
Brief Description of the Drawings
FIG.l Illustrates a flow diagram of operation for identifying
stroke boundaries in accordance with a preferred embodiment of the
S present invention.
FIG.2 Illustrates segmentation into strokes of handwritten
input produced by the y-velocity prior art method.
FIG.3 Illustrates segmentation into strokes of handwritten
input produced by the curvature prior art method.
FIG 4 Illustrates segmentation into strokes of handwritten
input produced by a preferred embodiment of the present invention.
FIG.5 Illustrates points m~king up the letter "L" as received
from a digitizing device.
FIG.6 Illustrates points m~qking up the letter "L" after
15 resampling to a constant distance in accordance with a preferred
embodiment of the present invention.
FIG.7 Is an exploded view Illustrating a curvature
calculation of a preferred embodiment of the present invention.
FIG.8 Illustrates graphically the curvature values calculated
2 0 for each point in FIG.7.
FIG.9 Illustrates graphically the derivative of curvature
values calculated for each point in FIG.7.
2 5 Detailed Description of the P.efeI~ed Embodiments
Typically, handwritten character input is collected from the
user in the form of discrete continuous segments. A discrete
continuous segment consists of one or more pen strokes, where a pen
3 0 stroke is the mark left by a pen during its period of contact with an
input device such as a digitizing tablet or paper.
In the present invention one or more discrete continuous
segments are the units of handwritten input being recognized.
Handwritten input is input which is captured electronically that
3 5 includes but is not limited to the following: handwritten input;
5 21 62~ 89
electronic input; input captured through pressure, such as stamped
input; input that is received electronically, such as via f~csimile,
pager, or other device.
A stroke is represented as a sequence of points sampled at
approximately regular intervals by the input device. Each point is
described at minimum by an X and a Y coordinate. Strokes may be
captured electronically using a digitizing tablet, or alternatively may
be derived from a scanned or faxed image through a process of line
detection in the image; such methods of capturing electronically are
understood in the art. In a ~lererled method handwritten input is
accepted by a device, such as a personal digital assistant (PDA) or
other device. Other devices that function to receive handwritten input
include, but are not limited to, the following: computers, modems,
pagers, telephones, digital televisions, interactive televisions, devices
having a digitizing tablet, f~csimile devices, sc~nning devices, and
other devices with the ability to capture handwritten input.
Generally, when strokes are captured electronically, each point is
represented by a pixel, such that a stroke is represented by a series of
pixel on the device.
2 0 In accordance with the present invention, handwritten input
maybe in the form of alphanumeric characters, ideographic
characters or other forms of characters or symbols of written
communication.
Referring now to the FIGs. and FIGs. 2 and 3 illustrate stroke
2 5 segmentation of alphanumeric handwritten input with a high
probability of inaccuracies in interpretation of the input when stroke
segmentations are passed to a stroke-based recognizer. FIG. 4
illustrates stroke segmentation of the same alphanumeric input of
FIGs. ~ and 3 where the stroke segmentation is made in accordance
3 0 with the te~çhing.c of the present invention and such stroke
segmentation has a high probability of accurate interpretation when
passed to a stroke-based recognizer.
Referring now to Fig. 1, illustrating a flowchart of a preferred
the method in accordance with the te~çhings of the present
3 5 invention. Handwritten input from the digitizer or other device is
- ~ 6 21621~9
received in the form of xy coordinates (110) (with associated penup or
pendown states). Typically these points are represented by pixels.
Generally, the present method resamples the handwritten input to
obtain points which are equally spaced along the length of the
S handwritten input (120). Figure 5 illustrates an example of the letter
"L" (500) as a series of points or pixels before resampling. Figure 6
illustrates the same letter "L" (600) as a series of points or pixels after
resampling. Resampling is done using an interpoint distance d (610)
that is constant throughout the handwritten input. Preferably, the
l 0 value of d chosen is such that the median input height in the
handwritten input is approximately in the range of 15 to 30 times d.
For ~mple, in FIG. 6 the value of d chosen is such that the median
letter height in the word is approximately in the range of 15 to 30
times d.
l S The preferred embodiment of FIG. 1 calculates the curvature
at each resampled point (130). Figure 7 illustrates graphically a
depiction of the data for calculation of curvature at a point R (710).
Curvature at a resampled point R (710) is defined as the distance to
R's successor (point R+1 (730)) from a point P (720), obtained by
2 0 projecting linearly from R's predecessor (R-1, 750) through R itself.
This distance is shown in Figure 7 as element 740. Curvature at
endpoints of the handwritten input is defined as equal to that at the
corresponding nearest neighbor points. Curvatures at the interior
points of the handwritten input may also be computed by projecting
2 S two points away from R, rather than one point (and using a point two
points prior to R, rather than R-1), to obtain a more robust estimate.
Figure 8 illustrates graphically the curvature values obtained for the
points shown in Figure 7.
-For example, the above mentioned example of an "L" with a
3 0 gradual bend could be segmented into a vertical and a horizontal
stroke as long as the two "straight" parts of the "L" were significantly
straighter than the bend between them. The curvature would then be
increasing going into the bend (i.e., the curvature derivative would be
high) and decreasing going away from the bend (the curvature
7 2162 1~9
derivative would be low), thus allowing a stroke boundary at or near
the bend, as desired.
In a preferred embodiment of the present invention, once the
curvatures have been obtained for each resampled point, the array of
S curvatures for the resampled points may be smoothed to minimi7e
any known artifacts introduced by the digitizing process. The type of
smoothing to be performed should be a standard method which is
selected based on the particular digitizing characteristics at hand.
This might include averaging the value of a point with its neighhor
l 0 points (weighting the point itself and nearest points higher), and
repl~ing the curvature value of the point in question with the
computed average. The size of the smoothing window used here
should ideally be wider at low-curvature sections of the writing and
narrower at high-curvature sections, to minimi7e loss of important
l S information in the smoothing process. Since it is the curvature itself
that is being smoothed, though, one ~efelable way to smooth is to
compute initial curvatures, smooth based on those curvatures, and
then re-smooth based on the new curvatures computed.
In a preferred embodiment of the present invention, for each
2 0 resampled point the absolute value of the curvature is computed by
multiplying any negative curvature values by the value -1. Preferably
the absolute values are used in computing curvature derivatives,
rather than the actual curvatures values, because the overall
preferred embodiments
2 5 of the present invention process are only concerned with the
sharpness of bends in the writing, and not which direction a given
bend curves.
As illustrated in FIG. 1, the process next calculates the
derivative of curvature at each resampled point (140). Referring to
3 0 Figure 7, the derivative of curvature at point R is defined as the
absolute value of curvature at point R+1 minus the absolute value of
curvature at point R-1, divided by two (i.e., the slope of the curve of
plotted curvature values). Figure 9 illustrates graphically the
derivative of curvature obtained at each point shown in Figure 7.
3 5 .~imil~r to the use of more than two points to get a more accurate
2l62~89
measure of curvature as described above, the derivative of curvature
should be computed using a wider window (five points versus three)
where the relevant points exist, and a narrower one (two points
versus three) where necessary. Since the derivative of curvature
cannot be calculated at the endpoints of the ink segment, the
derivative of curvature at the endpoints is simply defined to be equal
to that at the corresponding neighhor points.
Referring now to FIGs. 1 and 9, a preferred embodiment of the
process next çx~mines the newly calculated array of curvature
derivative values to locate points where the derivative is at a local
m~imum (910) (defined to include points at the end of an inflection
and about to decrease) or where the derivative is at a local minimum
(920) (defined to include points at the end of an inflection and about to
increase). For each section of input (in time) after a local m~ximum
1 5 and before a local minimum, the midpoint of the section (in terms of
arc length of the section) is located (930). This midpoint is defined as
M (930). If the difference between the local m~imum and the local
minimum values for a section exceeds a threshold value T' (940), and
the absolute curvature value at M exceeds some threshold value T"
2 0 (820), the point M is selected as a stroke boundary (150).
The parameters T' and T" must be estimated and depend on
the units in which curvature and curvature derivative are measured.
There exact values are not critical as long as an error-tolerant
character recognizer is used. In performing any experimental
2 5 tuning of these or any other parameters for creating a specific
embodiment of the invention, the desired goal is to attain
segmentation which is as consistent as possible across multiple
instances of particular character classes. This should be done
empirically by e~mining how the procedure segments various
3 0 actual samples of the writing to be recognized.
In addition to the selected stroke boundary points described,
points where the pen is lifted or put down are also selected as stroke
boundary points. In a preferred embodiment of the present invention,
curvature derivative-based boundary points maybe shifted by as much
3 5 as two points to cause them to fall on points where absolute curvature
9 2162~9
value is m~q~im~l (160). By shifting the curvature derivative based
boundary points, location of the stroke boundary points can be
improved by m~king both the measure of curvature and the derivative
of curvature yield the same stroke boundary. This preferred
5 application of the present invention is only done for a given point if no
stroke of less than three points will be produced, however.
The set of stroke boundary points in accordance with the
present invention defines a set of corresponding strokes. These
strokes can then be forwarded to a stroke-based character recognizer
1 0 for recognition of the handwritten input.
The present invention and its preferred embodiments relate to
novel more accurate methods of stroke segmentation. In accordance
with the present invention, in multiple instances of handwritten
input the input is repeatedly divided into a simil~r set of strokes each
l 5 time. For example, if the handwritten input is the Letter "L" written
at different times by different writers, the present invention and its
preferred embodiments would more accurately divide each time the
input of the letter "L" into simil~r stroke segmentation boundary
points regardless of the variances of the different writers. Such
2 0 stroke segmentation would aid in providing more accurate
interpretation by a stroke-based recognizer.
Those skilled in the art will find many embodiments of the
present invention to be useful. One obvious extension is from the case
of printed handwriting described here to that of cursive writing. The
2 5 actual method of segmentation of strokes is independent of the
method of segmenting characters, and thus techniques which allow
processing of cu~sive writing may readily make use of the stroke
segmentation process described here. Another embodiment would be
the segmentation of scanned, or "off-line" writing, into strokes. A
3 0 straightforward way of applying the present invention to such a task
would be to perform thinning of the writing to obtain a constant-width
ink curve. Stroke boundaries could then be set at both curvature
derivative-based points and at intersection points, since the lack of
temporal information makes intersections and touching bends look
3 5 similar.
