Main Page | See live article | Alphabetical index

Dynamic time warping

Dynamic time warping is a technique applied in automatic speech recognition to cope with different speaking velocities. In general, it is a method that allows to find an optimal match between two given sequences (e.g. time series) with certain restrictions, i.e. the sequences are "warped" non-linearly to match each other. This sequence alignment method is often used in the context of hidden Markov models.

A typical example of the restrictions imposed on the matching of the sequences are the following:

The optimization process is carried out using dynamic programming, hence the name.

Interestingly, the extension of the problem for two-dimensional "series" like images (planar warping) is NP-complete, while the problem for one-dimensional signals like time series can be solved in polynomial time.