Non-Markovian dynamic time warping

Seiichi Uchida, Masahiro Fukutomi, Koichi Ogawara, Yaokai Feng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)


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 some Markovian constraints which restrict the relationship between neighboring time points. In contrast, the non-Markovian 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 and then edges representing the non-Markovian constraints are added to the graph. An experiment on online character recognition showed the advantage of using non-Markovian constraints during DTW.

Original languageEnglish
Title of host publicationICPR 2012 - 21st International Conference on Pattern Recognition
Number of pages4
Publication statusPublished - 2012
Event21st International Conference on Pattern Recognition, ICPR 2012 - Tsukuba, Japan
Duration: Nov 11 2012Nov 15 2012

Publication series

NameProceedings - International Conference on Pattern Recognition
ISSN (Print)1051-4651


Other21st International Conference on Pattern Recognition, ICPR 2012

All Science Journal Classification (ASJC) codes

  • Computer Vision and Pattern Recognition


Dive into the research topics of 'Non-Markovian dynamic time warping'. Together they form a unique fingerprint.

Cite this