Handwritten character recognition using elastic matchingbased on a class-dependent deformation modelSeiichi Uchida and Hiroaki Sakoe
Faculty of Information Science and Electrical Engineering, Kyushu University
6-10-1 Hakozaki, Higashi-ku, Fukuoka-shi, 812-8581 Japan{uchida,sakoe}@is.kyushu-u.ac.jp
Abstract
For handwritten character recognition, a new elastic image matching (EM) technique based on a class-dependent
deformation model is proposed. In the deformation model,
any deformation of a class is described by a linear combination of eigen-deformations, which are intrinsic deformation directions of the class. The eigen-deformations canbe estimated statistically from the actual deformations ofhandwritten characters. Experimental results show that theproposed technique can attain higher recognition rates thanconventional EM techniques based on class-independent
deformation models. The results also show the superiority of the proposed technique over those conventional EMtechniques in computational efficiency.

1. Introduction
Elastic image matching (EM) techniques have been employed in handwritten character recognition tasks. The purpose of EM is to find the optimal fitting between a pair ofcharacter image patterns. The distance between the patterns
under the optimal fitting will be invariant to their deformations and thus favorable for deformation-tolerant recognition systems.
The fitting ability (i.e., the range of compensable deformations) depends on the deformation model of the EM.
The deformation models of conventional EM techniques areclass-independent. Namely, all classes are assumed to havethe same deformation tendency. It seems, however, morenatural to assume that each class has a intrinsic deformation tendency. For example, the two vertical strokes of “M”
are often tilted to be closer, whereas those of “H” are not(Fig. 1). This simple example reveals the limitation of theconventional class-independent models.
In this paper, a new EM technique based on a classdependent deformation model is proposed. In this modelany deformation of a class is described by a weighted linear combination of intrinsic deformation directions, called
eigen-deformations, of the class. The eigen-deformations
can be estimated statistically and automatically from the ac-tual deformations of handwritten characters.
The fitting problem of the proposed EM technique is anonlinear optimization problem and hard to solve directly.
This is due to the weights at the linear combination, which
are the control variables to be optimized, are contained in animage function. Thus, the approximation scheme employedin the tangent distance (TD) method by Simard et al. [4]-[6]are exploited to solve the problem.
The original idea of the eigen-deformations can befound in the Point Distribution Models (PDM) proposed byCootes et al. [1]. Uchida et al. [7] have extended the PDM todeal with fully 2D deformations and have used it in an EMbased handwritten character recognition system. In theirsystem, the eigen-deformations are used indirectly, that is,they are used in a posterior evaluation of the results of theEM based on a class-independent model. Contrary to this,in the proposed technique the eigen-deformations are directly embedded into a deformation model. Experimental
results will show the advantageous characteristics of thisnovel and straightforward use of the eigen-deformations.

2. The Proposed Elastic Matching Technique2.1. Problem Formulation
In general, parametric EM techniques are formulated as
the following minimization problemd(P c , E) = min s(α, P c ) − Eα(1)where P c = {Pc(x, y)} is the reference (i.e., prototype)character image of the class c and E = {E(x, y)} is
an input character image, where x, y = 1, 2, . . ., I. The
function s(α, P c ) is a deformation model and provides deformed images of P c according to M control parameters
α = {α1 , . . . , α m , . . ., α M }. If this deformation model
covers all deformations of the class c, the minimized distance d(P c , E) will be a deformation-invariant distance
between P c and E and thus favorable for deformationtolerant recognition systems.

manifolds(α,P)
Figure 1. Class-dependent deformation tendency. The counter-tilting of two verticalstrokes can be easily found in “M” (left) but
not in “H” (right).
y−α...

α=0+α

tangent planet(α,P)

P

tangent disntancedTD(P,E)

d(P,E)
Ex

Figure 3. Manifold s(α, P ), its tangent planet(α, P ), and tangent distance [4]-[6].
the eigen-deformations can be estimated automatically from
actual handwritten character samples.
Figure 2 shows the first three eigen-deformations of theclass “A”. (The displacement (Xc,m (x, y), Yc,m (x, y)) isrepresented by an arrow at each pixel (x, y).) The eigendeformations are ordered by their frequencies, and thus thisfigure shows that the global slant transformation appeared
as uc,1 is the most frequent deformation of the class “A”.

2.2. Optimization in Tangent Distance Framework
Figure 2. The reference pattern P c of the class“A” (top), the first three eigen-deformations
uc,1 = {(Xc,1 (x, y), Yc,1 (x, y))}, uc,2 , and uc,3 ofthe class (middle), and the reference patterns
deformed by these eigen-deformations, i.e.,{Pc(x + Xc,m (x, y), y + Yc,m (x, y))} (bottom).

In this paper, a new parametric EM technique based on
the following class-dependent deformation model:s(α, Pc(x, y))Mαm Xc,m (x, y),= Pc x +m=1y+M
αm Yc,m (x, y)) ,(2)m=1where (Xc,m (x, y), Yc,m (x, y)) is the (x, y)th element of
the mth eigen-deformation u c,m of the class c. The eigendeformation uc,m is a 2I 2 -dimensional vector and represents the mth intrinsic deformation direction of the class.
The element Xc,m (x, y) and Yc,m (x, y) are the vertical andthe horizontal displacements at the position (x, y), respectively. In the deformation model (2), any deformation of thereference P c is expressed by a weighted linear combinationof the M eigen-deformations. As we will see in Section 2.4,

The optimization problem (1) with the deformation
model (2) is hard to solve directly, because the parameters α
to be optimized are contained in the nonlinear 2D-1D function P c . Thus, some approximation is required to solve theoptimization problem. In the following, the subscript c is
dropped for notational simplicity, whenever there is no confusion.
Here, we employ the approximation scheme used in thetangent distance (TD) method [4]-[6], where it is consideredthat an M -dimensional manifold is formed by the the models(α, P ) in an I 2 -dimensional pattern space. Figure 3 illustrates the manifold at M = 1. In this case, the manifold isreduced to a curve controlled by α 1 . Note that the manifold
passes the original reference pattern P at α = 0.
As shown in Fig. 3, the distance d(P , E) can be approximated by the following TDdTD (P , E) = min t(α, P ) − E ,α(3)where t(α, P ) is the tangent plane of the manifold s(α, P )at α = 0. This tangent plane is obtained by the first-order
Taylor expansion of s(α, P ) around α = 0, i.e.,t(α, P ) = P +M

m=1


αm


∂s(α, P ).
∂αm
α=0(4)

With the proposed deformation model (2), the tangent planeP (x, y) [4]-[6], where G σ (x, y) is the Gaussian function.
Then,Px(x, y) ∼φ1

φ2

φ3Figure 4. The first three tangent vectors of
the class “A”. (Their values were normalized
to be displayed as gray-scale images.)(4) becomest(α, P ) = P +M

α m φm ,(5)m=1where φm is the tangent vector obtained asφm (x, y) = Px (x, y)Xm (x, y) + Py (x, y)Ym (x, y), (6)where Px(x, y) and Py (x, y) are x- and y-derivatives ofP (x, y), respectively. Since the tangent vector φ m can also
be considered as an I × I image, Equation (5) indicates thatany deformed reference pattern can be approximated by asimple linear combination of M images φ 1 , . . ., φ M and its
original image P . Figure 4 shows the first three tangent vectors of the class “A” obtained from the eigen-deformationsof Fig.2.
Substituting (5) into (3), the approximated solution α canbe obtained as(7)α = Φ−1 λwhere Φ and λ are an M × M matrix and an M dimensional vector respectively. Their elements Φm,m andλm (m, m = 1, . . . , M ) areΦm,m =

φm (x, y)φm (x, y),x,yandλm =φm (x, y)(E(x, y) − P (x, y)).

x,yThe above TD approximation has the advantage that aclosed-form solution can be obtained as (7). The TD approximation also has the disadvantage that the approximation may be accurate only around α = 0, i.e., accurate forrelatively small deformations.

2.3. Implementation Techniques and Computational Complexity
A sophisticated way for obtaining the derivatives P x and
Py is to use the blurred image P (x, y) ∗ G σ (x, y) instead of∂P (x, y) ∗ Gσ (x, y)∂Gσ (x, y)= P (x, y) ∗.
∂x∂x

In our experiments, the standard deviation σ was fixed at
1.25 by a preliminary experiment. (As remarked in [5], thisvalue was not critical. In fact, similar results were obtainedwith σ ∈ [0.75, 1.5] in our experiment.)
The computational complexity to obtain d TD (P , E) isabout O(M I 2 +M 2 ). In practice, the number of parameters
M can be a very small value (∼ 3) as we shall see in Section
3. Consequently, the complexity becomes comparative to or
far less than that of conventional EM techniques. Note thatthe matrix Φ−1 and φm (x, y) are independent of the input
character E and therefore they can be calculated and storedin advance.

2.4. Estimation of Eigen-Deformations
The remaining problem is how to estimate the eigendeformations {uc,m } for each class c. As proposed in [7],this estimation can be done automatically using some conventional (i.e., class-independent model-based) EM technique and principal component analysis (PCA). The twostep procedure for the estimation is outlined as follows. (Formore details, see [7].)Step 1: Collection of actual deformations
Using some conventional EM, P c is fitted to each of N
training samples T c,n (n = 1, . . . , N ). Then the deformation of T c,n is detected from the optimized fitting (i.e.,pixel-to-pixel correspondence) between two image patterns
as a 2I 2 (or less)-dimensional displacement vector.
Step 2: Estimation using PCA
The eigen-deformations {uc,m } can be estimated by applying PCA to the collected displacement vectors of the classc. Specifically, the eigen-deformations are obtained as theeigen-vectors of the covariance matrix of the N displacement vectors. The eigen-vector which has the largest eigenvalue becomes the first eigen-deformation uc,1 .
The conventional EM technique employed in Step 1
should have accuracy and flexibility enough to detect theexact deformations of T c,n . Such EM technique often has
two drawbacks for its use in recognition systems, that is, (i)it requires numerous computations, and (ii) it has the highrisk of over-fitting, which is the phenomenon that an image
pattern of a class is closely fitted to another image patternof a different class. These drawbacks, however, do not matter in the present framework, because the conventional EM
is only used to match of two patterns of the same class intraining process and not used in recognition process. In theexperiment of Section 3, a non-parametric EM techniquecalled piecewise-linear two-dimensional warping (PL2DW)

3.1. Database
Recognition experiments was conducted on 26 (classes)
× 1100 isolated handwritten English uppercase character
images from the standard character database ETL6, whichis commonly used mainly in Japan. Each sample was normalized linearly so that its character region became 16×16.
The margin of 2 pixels was then added around the normalized sample; thus I = 20. After this preprocessing,
the first 100 samples of each class were simply averaged
to create one reference pattern P c . The next 500 samples were used as training samples T c,n in the estimationof the eigen-deformations. The remaining 500 samples(13000 = 26 × 500 samples in total) were used as test samples E in the following recognition experiment.
The pixel feature (Pc(x, y) and E(x, y)) was a five dimensional vector which consists of four-dimensional directional features [2] and one-dimensional gray-level feature.
The modification of the proposed technique for the use ofthis high-dimensional pixel feature is easy and omitted here.

3.2. Recognition Results
Figure 5 shows the recognition rates attained by theproposed EM as a function of the number of the eigendeformations M . The highest recognition rate is 99.21%and it is 1.12% (145 samples) improvement from the simple rigid matching.
The recognition rates are saturated fast at M = 3. This
fact shows that the proposed deformation model (2) can
cover most of actual deformations with a few parameters.
Furthermore, since the amount of the computations requiredby the proposed EM is relative to M , this fact also shows thehigh computational efficiency of the proposed technique.

3.3. Comparison to EM Techniques Based on ClassIndependent Deformation Models
In order to ensure the effectiveness of the classdependent deformation model of (2), the proposed technique was experimentally compared to two conventional
EM techniques based on class-independent deformation
models. The comparison is done on their recognition scoresand computational efficiency.
Comparison 1:
The first class-independent EM technique is the original
TD-based EM [4]-[6], where the following affine deformation model is employed in all classess(α, Pc(x, y))=Pc (x+α1 x+α2 y+α3 , y+α4 x+α5 y+α6 ) (8)recognition rate (%)

3. Experimental Results

99.4
99.2

proposed EM(TD + eigen-defomations)99.21 (M=3)
99.19 (M=6)

99.0
98.98
conventional EM(TD + affine)

98.8
98.6
98.4
98.2rigid matching

98.0 05101520253035404550

the number of parameters (M)Figure 5. Recognition rates attained by theproposed EM and the affine-based EM.
99.4
99.2

recognition rate (%)[8] was employed, where the pixel-correspondence is directly optimized by a combinatorial optimization scheme.

proposed EM(TD+eigen-deformations)better

M=50

99.0
98.8

conventional EM(PL2DW)

conventional EM(TD+affine)

M=1

98.6
98.4
98.2

rigidmatching

98.0
0.01

0.1

1101001000

averaged computation time (ms)Figure 6. Relation between computation time(ms) and recognition rate (%).
instead of the class-dependent model (2). This model has
six parameters (i.e., M = 6).
As shown in Fig. 5, its recognition rate was 98.98% andlower than 99.21% of the proposed EM at M = 3. This
fact shows that the deformation model (2) can cover the actual deformations more compactly than the commonly usedaffine deformation model. In addition, it is shown that theproposed deformation model can provide more computationally efficient EM than the affine deformation model.
Comparison 2:
The second class-independent EM technique is PL2DW [8],which was used for the estimation of the eigendeformations as noted in Section 2.4. PL2DW is a nonparametric EM technique, that is, the displacement of eachpixel in P c is directly optimized as a variable in a costly 2D
combinatorial optimization scheme.
The best recognition rate of PL2DW was 99.12% andslightly lower than 99.22% of the proposed EM. As suggested in 2.4, this inferiority will be due to over-fitting
which results from the high and class-independent flexibil-ity of PL2DW.
On computational efficiency, their difference becomes
more clear. In fact, the proposed EM technique is far morecomputationally efficient than PL2DW. Figure 6 plots therelation of their recognition rates and computation times
for one matching required by a PC (CPU: Xeon 2.0GHz).
This result shows that the proposed EM only requires about
1/500∼ 1/1000 computation time of PL2DW for almost thesame (or higher) recognition rates.

4. Discussions and Future Work4.1. Another Usage of Eigen-Deformations in EM
Another usage of the eigen-deformations has been proposed in [7], where the eigen-deformations are used indirectly in a EM-based recognition system. Specifically, theeigen-deformations are used in a posterior evaluation of theresult of some conventional (i.e., class-independent) EM.
From the viewpoint of recognition accuracy, this approach
will be good enough as reported in [7]. The approach,however, is not computationally efficient because highlyflexible conventional EM (such as PL2DW) should be performed with large computational burden in advance to theposterior evaluation. Furthermore, the conventional EM
will waste the computations for useless deformation candidates (e.g., the counter-tilting deformation of “H” illustratedin Fig. 1). Such useless candidates are totally excluded in
the proposed EM by embedding the eigen-deformations directly into the deformation model.

4.2. Another Optimization Strategy
The linear approximation is a good strategy for solving
the nonlinear optimization problem (1) with less computations, but has the side effect that the deformations compensable by the model (2) are limited to relatively small ones.
Thus, iterative algorithms can be an alternative strategies forsolving the problem because the iterative algorithms are freefrom the linear approximation. Wakahara et al. [9] have proposed such an iterative algorithm for EM based on the affine
deformation model (8). This algorithm can be extended todeal with the class-dependent deformation tendencies by replacing its affine deformation model by our class-dependent
deformation model (2).

4.3. Relation with Subspace Methods
The tangent approximation (5) is similar to the subspacemethods [3] in the sense that in the both methods a deformed pattern is approximated by a linear combination ofbasis images derived from training patterns using PCA (,orKLT). However, there is an essential difference betweenthese two methods; the basis images of the subspace methods are orthogonal in the original pattern space, whereas
those of the proposed EM, i.e., φm are not. Their experimental comparison is left as future work.

5. Conclusion
For handwritten character recognition, a novel elastic
image matching (EM) technique based on a class-dependent
deformation model was proposed. In the model, any deformation of the class is represented by a linear combinationof the eigen-deformations, which are intrinsic deformation
directions of the class. In order to solve the nonlinear optimization problem with respect to the model, tangent distance approximation was employed. Experimental results
showed that the recognition system using the pattern distance provided by the proposed EM technique can attainhigher recognition rates than conventional EM techniques
based on class-independent deformation models. The results also showed the superiority of the proposed techniqueover those conventional techniques in computational efficiency.
Acknowledgement: The authors thank the Electrotechnical Laboratory for providing us ETL6. This work wassupported in part by The Ministry of Education, Culture,Sports, Science and Technology in Japan under a Grant-inAid for Scientific Research No.14780293.

References[1] T. F. Cootes, C. J. Taylor, D. H. Cooper, and J. Graham,“Active shape models - their training and application,”
Comput. Vis. Image Und., 61(1):38–59, 1995.
[2] S. Mori, K. Yamamoto, and M. Yasuda, “Research onmachine recognition of handprinted characters,” IEEE
Trans. PAMI, 6(4):386–405, 1984.
[3] E. Oja, Subspace methods of pattern recognition, Research Studies Press Ltd., 1983.
[4] P. Simard, Y. Le Cun, J. Denker, and B. Victorri, “Anefficient algorithm for learning invariances in adaptiveclassifier,” Proc. 11th ICPR, 2:651–655, 1992.
[5] P. Simard, Y. Le Cun, and J. Denker, “Efficient pattern recognition using a new transformation distance,”
Advances in Neural Information Processing Systems,
5:50–58, 1993.
[6] P. Simard, Y. Le Cun, and J. Denker, “Memory-based
character recognition using a transformation invariantmetric,”Proc. 12th ICPR, 2:262–267, 1994.
[7] S. Uchida and H. Sakoe, “ Eigen-deformations for elastic matching based handwritten character recognition,”
Pattern Recognition, to appear, 2003.
[8] S. Uchida, and H. Sakoe, “Piecewise linear twodimensional warping,” Proc. 15th ICPR, 3:538–541,
2000.
[9] T. Wakahara, Y. Kimura, and A. Tomono, “Affineinvariant recognition of gray-scale characters using
global affine transformation correlation,”