21st International Conference on Pattern Recognition (ICPR 2012)
November 11-15, 2012. Tsukuba, Japan

Non-Markovian Dynamic Time WarpingSeiichi Uchida1 , Masahiro Fukutomi1 , Koichi Ogawara2 , Yaokai Feng112Kyushu University, Japan
Wakayama University, Japan
namic programming (DP) efficiently with O(T 2 ) computations. In other words, Markovian constraints havebeen forcibly employed for utilizing DP as the solver ofthe DTW problem. In fact, most DTW problems havebeen solved by DP (or its stochastic extension, HMM)
under some Markovian constraints.
However, many sequential patterns have nonMarkovian characteristics. Consider a handwriting
trajectory of “0”. The position of its ending pointshould be constrained by the starting point in orderto form a closed-circular shape of “0”. This example
clearly shows that our writing process is obviously nonMarkovian. In fact, we can find non-Markovian characteristics everywhere — we are often referring to not
only the latest point but also long past points. Similarly, it is highly probable that nonlinear timing fluctuation also has some non-Markovian characteristics.
For dealing this characteristics, we need to incorporate
non-Markovian constraints which restrict the relationship between ut and ut+n (n > 1). Unfortunately, as
discussed above, the conventional DP-based DTW cannot deal with them1 .
The main contribution of this paper is to realizea non-Markovian DTW, which can incorporate nonMarkovian constraints, such as α ≤ ut+n − ut ≤ β.
To the authors’ best knowledge, this is the first realization of the non-Markovian DTW. The key idea for thisrealization is to use graph cut instead of DP. In the proposed method, the DTW problem is re-formulated as agraph cut problem. Since graph cut does not assume any
Markovian characteristics of the problem, it is possible
to incorporate non-Markovian constraints in addition tothe Markovian constraints.

Abstract
This paper proposes a new dynamic time warping(DTW) method, called non-Markovian DTW. In the conventional DTW, the warping function is optimized generally by dynamic programming (DP) subject to someMarkovian constraints which restrict the relationshipbetween neighboring time points. In contrast, the nonMarkovian DTW can introduce non-Markovian constraints for dealing with the relationship between points
with a large time interval. This new and promising ability of DTW is realized by using graph cut as the optimizer of the warping function instead of DP. Specifically, the conventional DTW problem is first converted
as an equivalent minimum cut problem on a graph andthen edges representing the non-Markovian constraints
are added to the graph. An experiment on online character recognition showed the advantage of using nonMarkovian constraints during DTW.

1. Introduction
Dynamic time warping (DTW) between two sequential patterns, X = x1 , . . . , xt , . . . , xT and Y = y1 ,. . . , yτ , . . . , yT , is formulated as the optimization problem of the warping function τ = ut , which is shown
as a path in Fig. 1 (a) and matches xt to yτ (= yut ).
DTW is often called dynamic programming matchingor elastic matching and has widely been employed forcompensating nonlinear timing fluctuation in sequential
patterns, such as speech, handwriting, gesture, humanactivity, etc.
DTW is often implemented with some constraints inorder to exclude unexpected warping functions which
result in unnatural matching, or so-called over-fitting.
A typical constraint is the monotonicity and continuity
constraint, expressed as 0 ≤ ut+1 − ut ≤ ǫ, where ǫ is asmall integer (often 2). This constraint realizes a monotonic and continuous (i.e., smooth) warping function asshown in Fig. 1 (a).
An important fact about the monotonicity and continuity constraint is that it is a Markovian constraint,
which restricts the relationship between ut and ut+1 .
It is well-known that under Markovian constraints theglobally optimal warping function can be derived by dy-

978-4-9906441-1-6 ©2012 IAPR

2. Related Work
The proposed DTW method employs graph cut instead of DP. Graph cut can also obtain a globally optimal solution efficiently and thus has been applied to
1 Precisely speaking, it is “theoretically” possible to deal withthe relationship between ut and ut+n in DP by treating n variables(ut , ut+1 , . . . ut+n ) as a single high-dimensional variable. However, the computational complexity of the resulting DP algorithm becomes an exponential order of n [1] and thus the algorithm is computationally intractable even with small n.

2294

τ=ut

DTW the lower bound αt,t+1 = 0 and the upper bound
βt,t+1 = ǫ = 2 are fixed for all t, this constraint canbe rewritten simply as 0 ≤ ut+1 − ut ≤ 2; however,for the latter discussion, we use the above generalized
notation. The boundary conditions u1 = 1, uT = T are
also assumed during the minimization.
It is noteworthy that the Markovian constraint israther lax. Figure 1 (b) shows the area of possible paths
under the constraint after the path goes through a point(t, ut ). This figure indicates that the relationship between ut and ut+n becomes weaker for larger n andthus the conventional Markovian DTW is too flexible toavoid over-fitting. In the conventional DTW, therefore,
a warp range limitation (|t − ut | ≤ δ) of Fig. 1 (c) has
often been imposed to restrict the warping function.

τ=utt

t t+1(a)(b)

ut+n
τ=utt(c)t+n(d)

Figure 1. (a) Warping function τ = ut .
(b) Markovian constraint. (c) Range limitation.(d) Non-Markovian constraint.

4. DTW as a Graph Cut Problem
The globally optimal solution of (1) can be obtainedby not only DP but also graph cut as proved in [10]. As
noted before, DP treats the DTW problem as a path optimization problem on a t–τ plane as shown in Fig. 2(a).
In contrast, the graph cut treats the DTW problem as aminimum cut problem on a directed graph G = (V, E)
of (b). Hereafter, using Fig. 2, we will show how thisgraph (b) is derived from (a).
The nodes V are comprised of two special nodes(source and sink) and other nodes, each of which corresponds to a grid point (t, τ ) on the 2D-space of (a).
Specifically, as shown in (c), for every grid point (t, τ ),0
1
a pair of nodes (vt,τ, vt,τ) are prepared in G.
The edges E are comprised of several groups hav1
0and vt,τ
ing different roles. First, the edge between vt,τhas a weight dt (τ ). Consequently, the cost for the pathin (a) is equivalent to the cost for the cut in (c). Second, the edges connected to sink or source nodes in (d)have an infinity weight and represent boundary conditions. For example, the two cuts in (d) represent thecases of u1 = 3 6= 1 and uT = 2 6= T , respectively.
They never happen because they have an infinite costby cutting those edges. Third, the edges in (e) and (f)also have an infinite weight and play a role to exclude
unexpected cuts (like “NG” cuts in these figures).
The monotonicity and continuity constraint with thelower bound αt,t+1 and the upper bound βt,t+1 is also
represented by edges with an infinite weight. The edgesin (g) are for αt,t+1 = 1 (where, for a simpler visibility,αt,t+1 is fixed at 1 instead of 0) and the edges in (h) arefor βt,t+1 = 2.
Now we have all the elements, that is, nodes andedges of the graph G of (b). In short, the nodes andthe edges of (c) are prepared for representing the local
costs and the edges of (d)-(h) are prepared for regulating
possible cuts equivalent to possible paths. Thus, we canvarious optimization problems [2] including matchingtasks between 1D patterns [3, 4], 2D patterns [5] and 3D
patterns [6]. Coefficients for unary and binary terms ingraph cut can be learned statistically from training patterns [7, 8, 9]. These facts enable graph cut to deal withrecognition tasks [9, 5] where DP is often used. Since
its optimization principle is totally different from DP,
it has a potential to avoid the limitation of DP, such as
Markovian characteristics. However, most of the previous approaches using graph cut cannot handle nonMarkovian characteristics in matching or recognition
tasks [3, 4, 5, 6].
Ishikawa et al. [10] have applied graph cut to stereo
matching problem, which is essentially the same asDTW. The proposed method extends their method by
newly introducing non-Markovian constraints. As emphasized in Section 1, non-Markovian characteristics
can be observed everywhere and therefore this promising extension will give a new research direction to DTW
and other nonlinear matching problems.

3. Problem Formulation of DTW
Let us start with a conventional DTW where only aMarkovian constraint is imposed. The Markovian DTWis formulated as the minimization problem of the following objective function F with respect to the warping
function U = u1 , . . . , uT :min F =minu ,...,u1

TTXdt (ut )(1)αt,t+1 ≤ut+1 −ut ≤βt,t+1 t=1

where dt (ut ) denotes the local matching cost between
xt and yut . As noted before, the monotonicity andcontinuity constraint αt,t+1 ≤ ut+1 − ut ≤ βt,t+1
is a Markovian constraint. Since in the conventional2295

d1(4)

sink∞

1v1,40v1,4

τNGNG
1v1,10v1,1t(a)(b)∞

source(c)(d)∞∞∞OKNGOKNGNGNG(e)(f)(g)(h)Figure 2. (a) DTW as a path optimization problem. (b) DTW as a graph cut problem. (c) Edgesfor di (ui ). (d) Edges for boundary constraints. (e) and (f) Edges for excluding unexpected cuts.
(g) Edges representing αt,t+1 = 1. (h) Edges representing βt,t+1 = 2.

∞

ut+1 , . . . , ut+n−1 directly.
By comparison between Fig. 1 (b) and (d), we canexpect that non-Markovian constraints can regulate thewarping function in more various ways. In fact, nonMarkovian constraints are very flexible; for example, itis possible to put such a constraint between t = 4 and 9
but not between t = 7 and 11. In Section 6, we will introduce a learning method to design the non-Markovian
constraints automatically for a specific DTW task.
Similar to the Markovian constraints, nonMarkovian constraints are also introduced as edgesof graph G. If we want to restrict the relationshipbetween ut and ut+n , we need to put several edges
with an infinite weight between nodes at t andt + n. Figure 3 shows a non-Markovian constraint
1 = αt,t+n ≤ ut+n − ut ≤ βt,t+n = 2.
By obtaining the minimum cut of the resulting graph,
we can have the globally optimal solution of nonMarkovian DTW. We do not need to make any special
care for the graph cut algorithm; just like the Markovian case, the algorithm can provide the optimal solution for the graph with edges for non-Markovian constraints. An important fact is that the introduction of
non-Markovian constraints affect computational complexity of DTW just linearly. Considering Footnote 1,
this is a distinct advantage of the proposed method overthe conventional DP-based implementation.

NGτ+3
τ+2OK...

τ+1
τt

...

t+nFigure 3. Non-Markovian constraint
αt,t+n = 1, βt,t+n = 2 as edges of G.
understand the minimum cut of (b) is equivalent to theoptimal path of (a). In other words, the solution by somegraph cut algorithms is exactly the same as the solutionby DP. Most graph cut algorithms, such as EdmondsKarp algorithm, require polynomial-order computations
and are still efficient for Markovian DTW.

5. Introducing Non-Markovian Constraints
As described in Section 1, non-Markovian constraints restrict the relationship between ut and ut+n(n > 1). Figure 1 (d) shows an example of nonMarkovian constraint. It forces a warping function taking the value τ at t to pass through one of four values as
ut+n at t + n. It is important that such a non-Markovianconstraint 2 is written as αt,t+n ≤ ut+n − ut ≤ βt,t+n .
It is also important that this constraint does not restrict

6. Learning Non-Markovian Constraints
The purpose of introducing non-Markovian constraints for sequential pattern recognition with DTW isgenerally to allow all possible warping functions be-

2 In the extra page of our camera-ready version, we will show anextended version of non-Markovian constraints, which depend not
only on t and n but also on τ .

2296

ut

Table 1. Recognition rate (%).
MarkovianNon-MarkovianAverage
88.7
89.4

Class “6”
83.3
86.3

Class “1”
73.3
74.7

t

4 8 10 19t

13ut

tween patterns of the same class and to exclude the otherwarping functions for suppressing over-fitting by DTW.
Based on this fact, the non-Markovian constraints canbe simply learned as follows. First, the allowable
warping functions U are collected by the conventional
Markovian DTW between patterns of the class c. Then,for each timing pair t and t + n, the maximum and minimum values of ut+n − ut are set as αt,t+n , βt,t+n for
non-Markovian DTW of class c.

(a)

(b)

22(c)

Figure 4. Two improved examples. (a) Test
sample X. (b) Result by Markovian DTW.
(c) Non-Markovian constraints.
(α4,10 , β4,10 ) and (α8,19 , β8,19 ) of class “8”. Consequently, the steep slope, i.e., over-fitting, was suppressed in the non-Markovian DTW and these two test
samples were correctly recognized.

7. Experimental Results
To evaluate the effect of non-Markovian DTW, an
online character recognition experiment was conductedusing the Ethem Alpaydin Digit dataset which is comprised of online handwritten digit samples (“0”– “9”).
Each sample was simply represented as a sequence of
two-dimensional pen-tip coordinate. The length T was
about 50. The dataset was decomposed into 700 training samples per class and 300 test samples (X) perclass. From the training samples, 21 reference patterns(1∼4 samples per class) were determined by a clustering method. Mahalanobis distance was used for the local cost dt (ut ). The cost min F was calculated between
a test sample and each of the 21 reference patterns, andthe class of the minimum cost reference pattern wasconsidered as the recognition result. Note that for improving the recognition accuracy of the conventional
Markovian DTW, a warp range limitation (|t − ut | ≤ δ)
was introduced with the optimized parameter δ.
Computational time is less than 5ms for each nonMarkovian DTW. This proves the high efficiency of theproposed method, if we consider the fact that the DPbased implementation is computationally intractableeven around T = 10.
Table 1 shows that non-Markovian DTW could provide higher recognition accuracy than conventional
Markovian DTW. Figure 4 (a) shows two improved examples, “6” and “1”, which were misrecognized as “8”and “9” respectively by the Markovian DTW. The warping function U by the Markovian DTW (b) shows asteep slope around its beginning part for matching patterns of different classes. This slope is allowed by theMarkovian slope constraint (even with the warp rangelimitation) and then causes over-fitting. In contrast,
this steep slope was not allowed in the non-Markovian
constraints. As shown in (c), the warping function
violates the non-Markovian constraints, for example,

8. Conclusion
A non-Markovian dynamic time warping (DTW) has
been proposed. Use of graph cut, instead of dynamic
programming (DP), as the optimizer of the warping
function allows us to introduce non-Markovian constraints, which can restrict the relationship between
points with a large time interval during DTW, still withpolynomial computations. The usefulness of the nonMarkovian DTW has been shown through an online
character recognition experiment.

References[1] U. Bertele and F. Brioschi, Nonserial Dynamic Programming,
Academic Press, 1972.
[2] B. Price, B. Morse, and S. Cohen, “Geodesic Graph Cut forInteractive Image Segmentation,” Proc. CVPR, 2010.
[3] F.R. Schmidt, E. Toppe, D. Cremers, and Y. Boykov, “EfficientShape Matching via Graph Cuts,” Proc. CVPR, 2007.
[4] F.R. Schmidt, E. Toppe, and D. Cremers, “Efficient Planar
Graph Cuts with Applications in Computer Vision,” Proc.
CVPR, 2009.
[5] O. Duchenne, A. Joulin and J. Ponce, “A Graph-Matching Kernel for Object Categorization,” Proc. ICCV, 2011.
[6] W. Chang and M. Zwicker, “Automatic Registration for Articulated Shapes,” Proc. ESGP, 2008.
[7] S. Kumar and M. Hebert, “Discriminative Fields for Modeling
Spatial Dependencies in Natural Images,” Proc. NIPS, 2003.
[8] D. Cremers and L. Grady, “Statistical Priors for Efficient Combinatorial Optimization via Graph Cuts,” Proc. ECCV, 2006.
[9] D. Anguelov, B. Taskar, V. Chatalbashev, D. Koller, D. Gupta,G. Heitz, and A. Ng, “Discriminative Learning of Markov Random Fields for Segmentation of 3D Scan Data,” Proc. CVPR,
2005.
[10] H. Ishikawa and D. Geiger, “Occlusions, Discontinuities, andEpipolar Lines in Stereo,” Proc. ECCV, 1998.

2297