Image analysis – Pattern recognition – Unconstrained handwriting
Reexamination Certificate
1998-01-20
2001-06-05
Johns, Andrew W. (Department: 2621)
Image analysis
Pattern recognition
Unconstrained handwriting
Reexamination Certificate
active
06243493
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to methods for handwriting recognition and the use of invariant features to reduce or eliminate geometric distortion.
BACKGROUND OF THE INVENTION
The principal difficulty in the recognition of patterns by computer is dealing with the variability of measurements, or features, extracted from the patterns, among different samples. The extracted features vary between samples for different reasons, depending on the type of pattern data being processed. In handwriting recognition the source of variations include input device noise, temporal and spatial quantization error, and variability in the rendering of input by the writer. There are two principal methods for dealing with variability in pattern recognition. One, the patterns can be normalized before feature extraction by some set of preprocessing transformations, and two, features can be chosen to be insensitive to the undesirable variability.
Writer induced variations have both a temporal and a spatial component. The temporal component relates to the sequence of strokes that comprise a letter; sequence of letters that comprise a word; and the sequence of elements of any defined grammar. The temporal component of writer induced variability is normalized during preprocessing and most probable sequences are approximated by Hidden Markov Model (HMM), processes well known in the art. The present invention addresses the spatial component of writer induced variation, that is, the geometric distortion of letters and words by rotation, scale and translation and teaches a new feature as well as a new use of an old feature for handwriting recognition, invariant with respect to translation, scale and rotation.
Eliminating feature spatial variation requires selecting a feature that is invariant under arbitrary similitude transformation, a transformation that involves a combination of translation, scale and rotation. The feature should allow recognition of a handwriting sample, independent of its position, size and orientation on a planar surface. Basic HMM based handwriting recognition systems known in the art, use the tangent slope angle feature as a signature of a handwriting sample, which is invariant under translation and scaling, but not rotation. Curvature is another feature that is invariant with respect to translation and rotation, but not scale. In general, it is easy to chose features that are invariant with respect to translation. It is more difficult to find features invariant with respect to scale and rotation and features invariant with respect to all three factors.
A similitude transformation of the Euclidean plane R
2
→R
2
is defined by:
w=c∪r+v
where c is a positive scalar,
U
=
[
cos
ω
-
sin
ω
sin
ω
cos
ω
]
,
v
=
[
v
x
v
y
]
T
representing a transformation that includes scaling by c, rotation by angle &ohgr; and translation by v. Two curves are equivalent if they can be obtained from each other through a similitude transformation. Invariant features are features that have the same value at corresponding points on different equivalent curves.
A smooth planar curve P(t)=(x(t),y(t)) can be mapped into
{overscore (P)}
(
{overscore (t)}
)=(
{overscore (x)}
(
{overscore (t)}
),
{overscore (y)}
(
{overscore (t)}
))
by a reparametrization and a similitude transformation, resulting in
{overscore (P)}
(
{overscore (t)}
)=
cUP
(
t
(
{overscore (t)}
))+
v
Without loss of generality, one may assume that both curves are parametrized by arc length, so that
d{overscore (s)}=cds
and the relationship between the corresponding points on the two curves is represented by
P
~
(
s
~
)
=
cUP
[
s
~
-
s
~
o
c
]
+
v
It has been shown that curvatures at the corresponding points of the two curves is scaled by 1/c, so that
κ
~
(
s
~
)
=
1
c
κ
[
s
~
-
s
~
o
c
]
A feature invariant under similitude transformation, referred to as the normalized curvature, is defined by the following formula:
κ
~
′
(
s
~
)
[
κ
~
(
s
~
)
]
2
=
κ
′
[
(
s
~
-
s
~
o
)
/
c
]
κ
[
(
s
~
-
s
~
o
)
/
c
]
2
where the prime notation indicates a derivative. For a more complete explanation and derivation of this equation see A. M. Bruckstein, R. J. Holt, A. N. Netravali and T. J. Richardson,
Invariant Signatures for Planar Shape Recognition Under Partial Occlusion,
58 CVGIP: Image Understanding 49-65 (July 1993), the teachings of which are incorporated herein by reference, as if fully set forth herein.
The computation of the normalized curvature defined above involves derivative estimation of up to the third order. Invariant features have been discussed extensively in computer vision literature. However, they have been rarely used in real applications due to the difficulty involved in estimating high order derivatives. As shown below, high order invariant features can be made useful with careful filtering in derivative estimation.
An invariant feature can be viewed as an invariant signature: every two equivalent curves have the same signatures. Any curve can be recognized and distinguished from classes of equivalent curves, by comparing its signature with the signature of one of the members of each class, which can be considered a model curve of that class. When the sample curve corresponds to only one model curve, in other words the sample always appears the same, there is complete correspondence between the sample curve and its matching model curve. In this case, many global invariant features; features normalized by global measurements such as total arc length, can be used for matching. This is the case for example, in handwriting recognition when whole word models are used. However, for systems aiming at writer-independent recognition with large and flexible vocabularies, letter models or sub-character models are often used. In this case each sample curve such as a word, corresponds to several model curves, such as letters, connected at unknown boundary points, which makes it more difficult to compute global invariant features. Therefore, it is important to develop invariant features which do not depend on global measurements. These features are sometimes referred to as local or semi-local invariant features to distinguish them from global features.
Two factors make it impossible to have exact match of model and sample signatures in real applications. First, since handwriting samples are not continuous curves, but comprise sequences of signals, i.e., sample points, the exact matching point on the-model curve for each sample point cannot be determined. Second, even with similitude transformation, handwritten samples of the same symbol are not exact transformed copies of an ideal image. Shape variations which cannot be accounted for by similitude transformation occur between samples written by different writers, or samples written by the same writer at different times. Therefore only approximate correspondence can be found between the sample curve and the model curves. One method for determining such correspondence is to define a similarity measurement for the features and then apply dynamic time warping. For a more detailed description of dynamic time warping and its application for approximating correspondence between sample and model curves see C. C. Tappert,
Cursive Script Recognition by Elastic Matching,
26 IBM Journal of Research and Development 765-71 (November 1982), the teachings of which are incorporated herein by reference, as if fully set forth herein. Another method is to characterize segments of curves by a feature probability distribution and find the correspondence between segments of curves statistically. The latter is the approach taken by HMM based systems, of which an improved system is disclosed and claimed in U.S. patent application Ser. No. 08/290623 and its related applications.
SUMMARY OF THE INVENTION
Accordingly, it is an objective of the present inven
Brown Michael Kenneth
Hu Jianying
Turin William
AT&T Corp.
Azarian Seyed H.
Johns Andrew W.
LandOfFree
Method and apparatus for handwriting recognition using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for handwriting recognition using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for handwriting recognition using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2525980