Dynamic time warping

From Wikipedia, the free encyclopedia

Dynamic time warping is an algorithm for measuring similarity between two sequences which may vary in time or speed. For instance, similarities in walking patterns would be detected, even if in one video the person was walking slowly and if in another he or she were walking more quickly, or even if there were accelerations and decelerations during the course of one observation. DTW has been applied to video, audio, and graphics — indeed, any data which can be turned into a linear representation can be analyzed with DTW. A well known application has been automatic speech recognition, to cope with different speaking speeds.

In general, DTW is a method that allows a computer to find an optimal match between two given sequences (e.g. time series) with certain restrictions. The sequences are "warped" non-linearly in the time dimension to determine a measure of their similarity independent of certain non-linear variations in the time dimension. This sequence alignment method is often used in the context of hidden Markov models.

One example of the restrictions imposed on the matching of the sequences is on the monotonicity of the mapping in the time dimension. Continuity is less important in DTW than in other pattern matching algorithms; DTW is an algorithm particularly suited to matching sequences with missing information, provided there are long enough segments for matching to occur.

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

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..

[edit] Example of one of the many forms of the algorithm

int DTWDistance(char s[1..n], char t[1..m], int d[1..n,1..m]) {
    declare int DTW[0..n,0..m]
    declare int i, j, cost

    for i := 1 to m
        DTW[0,i] := infinity
    for i := 1 to n
        DTW[i,0] := infinity
    DTW[0,0] := 0

    for i := 1 to n
        for j := 1 to m
            cost := d[s[i],t[j]]
            DTW[i,j] := cost + minimum(DTW[ i-1, j   ],           // insertion
                                       DTW[ i  , j-1 ],           // deletion
                                       DTW[ i-1, j-1 ])           // match

    return DTW[n,m]
}

The same as the above, but written in Python:

    def time_warp_distance(s, t, d):
        """
        Dynamic Time Warp algorithm
        Requires numpy
        The input is subject to certain restrictions not enforced here
        """
        n = len(s)
        m = len(t)
        
        DTW = numpy.zeros((n, m))
        
        # Initialize the array.  Note that [0, 0] is skipped
        Infinity = float('infinity')
        
        for i in range(1, m):
            DTW[0, i] = Infinity
        
        for i in range(1, n):
            DTW[i, 0] = Infinity
        
        # And do the work
        for i in range(0, n):
            for j in range(0, m):
                cost = d[int(s[i]), int(t[j])]
                DTW[i, j] = cost + min(
                    DTW[i - 1, j],      # Insertion
                    DTW[i, j - 1],      # Deletion
                    DTW[i - 1, j - 1]   # Match
                )
        
        return DTW[n - 1, m - 1]

[edit] References

• C. S. Myers and L. R. Rabiner.
  A comparative study of several dynamic time-warping algorithms for connected word recognition.
  The Bell System Technical Journal, 60(7):1389-1409, September 1981.
• FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space, Stan Salvador and Philip Chan. Intelligent Data Analysis, 2007.

[edit] See also

• Levenshtein distance