From Wikipedia, the free encyclopedia.
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)
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.
