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:

• continuity (no large gaps in the sequences should occur, e.g. only one item of a sequence may be skipped)
• monotonicity (the order of the elements in the sequence should not be inversed)

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.