Feature Desynchronization in Online Character Recognition
Seiichi Uchida

Kazuya Niyagawa
Hiroaki Sakoe
Kyushu University
744 Motooka, Nishi-ku, Fukuoka-shi, 819-0395, Japanuchida@is.kyushu-u.ac.jp

Abstract
This paper discusses desynchronization of feature elements, such as X-coordinate and Y-coordinate, in online
character recognition. The main results were twofold:First, the feature desynchronization has ability to compensate the shape difference between character patterns.
Second, the feature desynchronization is useful to improverecognition accuracy if its range is regulated according toactual deformation characteristics of characters.

Keywords:

desynchronization, feature vector, online
character recognition, elastic matching1.

Introduction

In online character recognition, each character pattern
is usually represented as a temporal sequence of feature
vectors. As the elements of the feature vector, - and-coordinates, local direction, pen pressure, and pen tilt
have been utilized. Those elements are generally acquiredat the same timing and therefore used synchronously.
For example, if a character pattern is represented as asequence of two-dimensional coordinate feature vectors,


i.e.,

 , the elements
andare always coupled tightly and not treated in
any independent manner. Note that this synchronous usage of the feature elements is also common in other temporal pattern recognition tasks, such as speech recognition
and gesture recognition.
The main purpose of this paper is to see the effect ofdesynchronization of feature elements in online character
recognition. Under the desynchronization, two feature elements acquired at the different timings can be coupled asa virtual feature vector like .
Note that the desynchronization discussed in this paper
does not mean that feature elements are used in a totally
independent manner. In fact, the range of the desynchronization should be limited because the totally independent
desynchronization will cause unexpected results as experimentally shown in a later section.
As the first trial of desynchronization in online char-  

acter recognition, we assume the above two-dimensional
. In other words, we
coordinate feature vector
assume that horizontal pen movement and vertical pen
movement are partially asynchronous on writing character patterns. Although this assumption has not been fully
supported by any theory at this moment, our trial is still
meaningful because of the following points. First, the has the ability of synthedesynchronization ofsizing new patterns from a single pattern (Section 4) andthis ability is useful to achieve better recognition performance (Section 5). Second, we can find some hint of thetheoretical support in the past research on writing kinematics (Section 6.2). Third, it is possible to extend thistrial to a more solid trial by using other feature elements(Section 6.1).
In this paper, the feature desynchronization is examined in a online character recognition technique based onelastic matching. Elastic matching provides an optimal
point-to-point correspondence between two character patterns and therefore can not only compensate nonlinear
temporal fluctuation but also adjust variations in patternlength. For the optimization, we will employ dynamic
programming (DP), which has been widely used (e.g.,[1, 2]).





2.

Related work

There are few past attempts on feature desynchronization in sequential pattern recognition tasks 1 other than
online character recognition. Those attempts have tried tocouple two hidden Markov models (HMMs), which can beconsidered as a statistical extension of the DP-based elastic matching technique used in this paper. Brand et al. [3]has coupled two HMMs for gesture recognition. A similar idea can be found in Matsuda et al. [4], where coupled
HMMs has been applied to speech recognition.
This paper is different from those past attempts at several points; for example, the difference in models (DP and
HMM), the difference in applications, and the difference
1 It is interesting to note that the desynchronized matching algorithm
has a close relation to the algorithms in genome science as discussed in
Section 6.3.

anddence problem between    










 :

 


  







      (1)    represents
where the sequence the point-to-point correspondence to be optimized. At
the optimization, we assume the boundary constraints,   and  , and the so-called monotonicity
and continuity constraint,     (2)

It is important to note that two feature elements are
and are equallyused synchronously in (1), that is,
indexed by . Accordingly, as shown in Fig. 1 (a), thetwo elements  and  at the same th point on correspond to the elements at the same th point on  .

Figure 1. (a) Conventional(b) Desynchronized matching.

elastic

matching.



3.2.
in features. In addition to those superficial differences,
there is an essential difference that the purpose of this paper includes the observation on the effect of the desynchronization. In fact, the desynchronization has a powerful effect of synthesizing virtual patterns (Section 4.2),
while the effect has not been pointed out in the past attempts.
Artières et al. [5] also have proposed several algorithms of coupled HMMs and applied them to online character recognition. They have coupled an HMM for online
recognition with an HMM for offline recognition. Froman algorithmic viewpoint, none of their algorithms is thesame as the proposed one. It will be possible to apply the
proposed algorithm to their task for more accurate evaluation with less complexity. In addition, there is the above
essential difference with each other.

3.

Conventional elastic matching technique

3.1.

Problem formulation                   


Let



 denote an input pattern and   denote the referandence pattern of the category . (Strictly speaking,should be denoted as  and  .) Throughout this paper, we will assume the two-dimensional coordinate fea .
ture vector, i.e.,     
The nature of elastic matching is to establish the optimal point-to-point correspondence between
and  .
The matching cost under the optimal correspondence isinvariant to temporal fluctuation and therefore useful torealize practical recognition systems.
The conventional DP-based elastic matching technique is formulated as the following optimal correspon-











Algorithm of conventional elastic matching

The optimal correspondence problem of (1) can beconsidered as an optimal path problem on the plane. Fig. 2 illustrates the optimal path representing
. The constraint (2) assures asmoothness and the monotonicity of the path.
This optimal path problem can be solved effi ciently by a DP-based algorithm. Letting    , the DP algorithm is orga 
nized as calculation of the following recursive equation
at all from   to :   







 

             (3)where  represents the minimum matching cost between         and          . Consequently,   is the minimum matching cost between and  ,i.e.,  
(4) 

and invariant to temporal fluctuation of . The minimum
 is used as a discrimination function;
matching cost
the category giving the smallest
 is selected as therecognition result of .







4.

Desynchronized matching

4.1.

Problem formulation

The elastic matching problem with the desynchronization of – feature elements is formulated by slightly
modifying the conventional elastic matching problem asfollows: 

 





       


 

(5)

J
j=j(i)
j’=j(i-1)

Rc

1 1

i-1 i

k(i)

I

j(i)

Figure 2. Conventional elastic matching as an optimal path problem.

~
Rc
(a)

(b)

(c)

Figure 4. Synthetic patterns
tion.

Y1

Y1

Yk

YJ
Figure 3. Pattern synthesis by the desynchronizationof – feature elements.






where
 and
 represent the point-to-point correspondences onand coordinate feature elements,
respectively. The objective function is to be andminimized with respect to  under the boundary conditions    and  and the monotonicity and continuity constraints,              










               (6)Fig. 1 (b) depicts the idea of the desynchronization of and -coordinate feature elements. Under the desynchronization, those feature elements of the th point on
correspond to different points,  and  , on  respectively. In other words,       corresponds to      .


4.2.



 











Effect of desynchronization

It is an important fact that the desynchroniza–feature elements is a pattern syntion ofthesis process.
As shown in Fig. 3, is a synthetic pattern, since each
is not an actual point on
point   
. Accordingly, if we control the point correspon-  






XJ

X1

(d)

by desynchroniza-

Yk

YJ
Xj

XJ

X1

Xj

Figure 5. A pair of character patterns with similar horizontal and vertical pen movements.





 



dence





, wecan produce various synthetic patterns. The ability of synthesizing patterns is very impressive; from a diagonal line
segment, we can synthesize any monotonic and continuous curve connecting the two ends of the original line
segment, if we allow free desynchronization.
Although the desynchronization is a “tricky” way tosynthesize deformed patterns from a single reference pattern, it has a high potential to mimic actual patterns. In
fact, Figs. 4 (a) and (b) are synthetic patterns from thesame pattern “0” by different desynchronized correspondences. Those synthetic patterns seem natural (actually,
we found a sample like (b) in the database used) and thus
the desynchronized matching technique is more tolerant
to the deformations than the conventional elastic matching
technique which compensates temporal difference only.
On the other hand, it is possible to provide unexpectedsynthetic patterns as shown in Figs. 4 (c) and (d). Suchunexpected patterns will degrade recognition accuracy because they may result in the misrecognition due to overfitting, which is the phenomenon that the reference patternof a wrong category is closely fitted to the input pattern.
In fact, a character pair of “4” and “9” of Fig. 5

This is because every character may have its local deformation characteristics; heavy deformations appear aroundsome position and not around another position. For example, the deformations at the beginning part of “1” areheavier than those at its horizontal ending part.
The following adaptive lag limitation is a simple andreasonable extension of the constant lag limitation to deal
with the local deformation characteristics:

      changes with . The
where the positive parameterparameter
must be optimized for each category insome way. (Thus, strictly speaking,must be denotedas  .) An example of the optimization will be given in
Section 5.3.
will reflect local deforThe optimized parametermation characteristics of the category . A larger (smaller)
reflects larger (smaller) deformations around . Thus,around the beginning part of “1” may become a large
value.

are easily misrecognized by free desynchronization. The
horizontal movement of “4” is almost the same asthat of “9” and therefore   under the op. Simitimized correspondence larly,    under the optimized correspondence.
Consequently, the matching
cost 
 becomes very small between “4” and “9”by an unexpected (i.e., over-fitted) synthetic pattern.

            
4.3.



   Limiting desynchronization

It is possible to avoid unexpected synthetic patterns bylimiting the range of desynchronization. Two limitation
schemes, constant lag limitation and adaptive lag limitation, are introduced in the following.
4.3.1.

 where is a positive constant to limit the maximum lag
between  and. Its effect is shown in Fig. 4 where(a) and (b) are synthetic patterns with the limitation at  whereas (c) and (d) are those without limitation. Notethat if  , the desynchronized matching is reduced tothe conventional elastic matching technique of Section 3.







Adaptive lag limitation

The constant lag limitation (7) assumes that the maximum lag is independent of and values. In otherwords, the deformation range of the character  is assumed not to change with the positions on the characterstroke. This assumption, however, is somewhat rough.









Algorithm of desynchronized matching

The optimal correspondence problem of (5) can beconsidered as the optimal path problem on the threedimensional - - space and still can be solved by aDP-based algorithm. Fig. 6 illustrates the DP algorithm which searches for the optimal path representing





 under thelag limitation, (7) or (8).
Letting       , the DP algorithm for the desynchronized matching is organized as the calculation of the following recursive equa from   to :tion at all pairs of      

Constant lag limitation

One of the simplest ways to limit the desynchronization is to introduce the following constraint on the correspondence:     (7)

4.3.2.




4.4.







Figure 6. Desynchronized matching (with constantlag limitation) as an optimal path problem.

(8)




    ¾ ½  ¾½



 

     (9)If the lag limitation is introduced, the equation (9) must violating the limitation.
not be calculated at any pairisprovided as.
The matching cost 




5.

Experimental results

5.1.

Character samples  

The numeric character samples from the public
database called Ethem Alpaydin Digit [6] were used in
the experiment. The database is comprised of 7,494 training samples and 3,498 test samples. The training samples
were written by 30 writers and the test samples were written by other 14 writers. The training samples were used
only for training the parameters of the adaptive lag limitation in Section 5.3. Every sample was preprocessed
to be a single-stroke character by simply connecting its
component strokes and then linearly rescaled to 128 128

98
desynchronized matching(with adaptive lag limitation)

96

conventional matching

95

E

94
93

desynchronized matching(with constant lag limitation)

92

0

constant
lag limitation

Figure 8. A pair of patterns
matching results
.

91
90

Rc

1

2
3
4
window size L
Figure 7. Recognition accuracy.

adaptive
lag limitation{

recognition rate (%)

97

 and

~
Rc

and their

5

while keeping its original aspect ratio. Reference patterns   were created manually to cover typical writing orders. The number of reference patterns was 21;  reference patterns were prepared for each category.



5.2.

Recognition results with constant lag limitation

Fig. 7 plots the recognition accuracies by the conventional (synchronous) elastic matching technique and the
proposed desynchronized elastic matching technique un. Noteder the constant lag limitation (7) at  again that the proposed technique at   is reduced tothe conventional technique. The conventional techniqueachieved the accuracy of 94.7% 2.
As shown in Fig. 7, the proposed technique with theconstant lag limitation could not outperform the conventional technique at any . Moreover, a larger achieveda lower recognition accuracy. Fig. 8 shows a typical misrecognition result. Under the constant lag limitation, thereference pattern  of the category “2” was over-fitted tothe input pattern of “1” as  . In fact, curved parts of“2” became diagonal lines by the desynchronization.

   







5.3.



Recognition results with adaptive lag limitation

Another experiment has been conducted to show thatthe recognition accuracy can be improved by the adaptivewaslag limitation. In this paper, the maximum lag
parameterized by , , , , and , as shown in
Fig. 9. Specifically,                     




















(10)

2 We can expect a higher recognition rate by another feature vector,
such as        where  is local writing direction. Since the purposeof this paper is to observe the effect of the desynchronization, we adhere
to the simpler feature vector     .

Figure 9. Desynchronized matching with adaptive laglimitation.

For each category , those five parameters were optimized in an exhaustive manner. The parameter were fixedat the values which gave the highest recognition accuracy
for the training patterns of the category.
Fig. 10 shows the optimized parameters of the adaptive lag limitation for the categories “0”, “1”, and “2.” For
the category “0”, the optimal values of , , and 
were found equally at 2. This fact indicates that the local
deformation characteristics of “0” are uniform. The parameters for “1” coincide with the fact that its beginningpart tends to be deformed more heavily than those at its
ending part.
The recognition accuracy achieved with the adaptive
lag limitation was 95.7% and therefore the proposed technique could outperform the conventional technique. As
shown in Fig. 8, the over-fitting of “2” to “1” was suppressed successfully by the adaptive lag limitation.

 

6.

Discussion

6.1.

Desynchronization of other features

Desynchronization between the coordinate feature anda pen-up/down feature is another promising trial. Desyn-

L1=2

L1=2

L1=4

B1

L3=2

L2=2
B2

B2

B1

B1

L2=2

L2=3

L3=0

B2

L3=1

Figure 10. Adaptive lag limitation for the categories“0”, “1”, and “2.”chronization of those features will appear as a hook or ashortened stroke and therefore be useful to compensate
those deformations. The result of this trial will be discussed elsewhere.
On the other hand, we must be careful in the desynchronization of feature elements with strong mutual dependence. For example, the desynchronization of the co and the local pen direction feaordinate feature
ture is not a simple problem because is generally derived by and
  and thus thoughtlessdesynchronization will cause conflicting results. (Actually, we cannot have a consistent synthetic pattern by thedesynchronization.)





6.2.







Relation to the theory of writing kinematics

At this moment, there is no firm theoretical supportof the deformation compensation by the desynchronization of – feature elements, as noted in Section 1. We,
however, can find some relation to the well-known writing
model by Flash and Hogan [7]. In their writing model, two
diagonally aligned points are connected by a minimumjerk curve whereas two vertically (or horizontally) aligned
points are connected by a straight line. This property resembles synthetic patterns by desynchronization and may
support the validity of the desynchronization matching.



6.3.

Relation to multiple alignment problem

From an algorithmic viewpoint, the DP-based algorithm for desynchronized matching in Section 4.4 areclosely related to the so-called multiple alignment problem, which has been investigated actively in genome
science[8]. If we want to desynchronize three or morefeature elements, the computational complexity of the optimal path problem becomes intractable. Thus, we should
resort to various approximation algorithms developed forthe multiple alignment problems.

7.

Conclusion

Desynchronization of feature elements was proposed
and applied to online character recognition. The featuredesynchronization had ability to compensate the shapedifference between character patterns by combining fea-

ture elements at different timings. It was shown experimentally that the desynchronization can improve recognition accuracy (94.7% 95.7% for numerics) by incorporating actual deformation characteristics as a limitation of
the desynchronization.
Future work will focus on the desynchronization ofother feature elements as noted in Section 6.1. Investigating theoretical relation to the writing kinematics will
be an interesting topic. We can apply the idea of the feature desynchronization to other sequential patterns, suchas gesture patterns. When each gesture pattern is represented as a sequence of two-dimensional feature vectors
representing the movements of the left and the right hands,
we can expect that the virtual feature vector by the desynchronization can compensate the asynchronous temporal
distortions of the hands. Patterns acquired from multimodal channels also can be promising application.
Acknowledgment: This work is partially supported byMicrosoft Research Asia Mobile Computing in Education
Theme Program.

References[1] S. D. Connell and A. K. Jain, “Template-based
online character recognition,” Pattern Recognit.,
vol. 34, no. 1, pp. 1–14, 2001.
[2] C. Bahlmann and H. Burkhardt, “The writer independent online handwriting recognition system frogon hand and cluster generative statistical dynamic
time warping,” IEEE Trans. PAMI, vol. 26, no. 3,
pp. 299-310, 2004.
[3] M. Brand, N. Oliver, and A. Pentland, “Coupled hidden Markov models for complex action recognition,”
Proc. CVPR, pp.994–999, 1997.
[4] S. Matsuda, M. Nakai, H. Shimodaira, and
S. Sagayama, “Asynchronous-transition HMM,”
Proc. ICASSP, vol. 2, pp. II1005–II1008, 2000.
[5] T. Artières, N. Gauthier, P. Gallinari, and B. Dorizzi,“A hidden Markov model combination frameworkfor handwriting recognition,” Int. J. Doc. Anal.
Recog., vol. 5, no. 4, pp. 233-243, 2002.
[6] http://archive.ics.uci.edu/ml/
datasets/Pen-Based+Recognition+of+Handwritten+Digits[7] T. Flash and N. Hogan, “The coordination of arm
movements: an experimentally confirmed mathematical model,” Journal of Neuroscience, vol. 5,
pp. 1688-1703, 1985.
[8] R. Eddy, A. Krogh, G. Mitchison, R. Durbin, Biological Sequence Analysis, Cambridge University
Press, 1999.