Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Dynamic Time warping implemented in python
'''Implementation and Demostration of Dynamic Time Warping
Requires : python 2.7.x, Numpy 1.7.1, Matplotlib, 1.2.1'''
from math import *
import numpy as np
import sys
def DTW(A, B, window = sys.maxint, d = lambda x,y: abs(x-y)):
# create the cost matrix
A, B = np.array(A), np.array(B)
M, N = len(A), len(B)
cost = sys.maxint * np.ones((M, N))
# initialize the first row and column
cost[0, 0] = d(A[0], B[0])
for i in range(1, M):
cost[i, 0] = cost[i-1, 0] + d(A[i], B[0])
for j in range(1, N):
cost[0, j] = cost[0, j-1] + d(A[0], B[j])
# fill in the rest of the matrix
for i in range(1, M):
for j in range(max(1, i - window), min(N, i + window)):
choices = cost[i - 1, j - 1], cost[i, j-1], cost[i-1, j]
cost[i, j] = min(choices) + d(A[i], B[j])
# find the optimal path
n, m = N - 1, M - 1
path = []
while (m, n) != (0, 0):
path.append((m, n))
m, n = min((m - 1, n), (m, n - 1), (m - 1, n - 1), key = lambda x: cost[x[0], x[1]])
path.append((0,0))
return cost[-1, -1], path
def main():
A, B = np.array([1,2,3,4,2,3]), np.array([1,1,3,3,4,3,3])
C = np.array([7,8,5,9,11,9])
B = C
cost, path = DTW(A, B, window = 4)
print 'Total Distance is ', cost
import matplotlib.pyplot as plt
offset = 5
plt.xlim([-1, max(len(A), len(B)) + 1])
plt.plot(A)
plt.plot(B + offset)
for (x1, x2) in path:
plt.plot([x1, x2], [A[x1], B[x2] + offset])
plt.show()
if __name__ == '__main__':
main()
@wenhoujx

This comment has been minimized.

Copy link

wenhoujx commented Oct 13, 2014

for j in range(max(1, i - window), min(N, i + window)), In this line, the window is not symmetric around point i, because the function range() is exclusive on the right hand side.

@manhdao

This comment has been minimized.

Copy link

manhdao commented Jul 15, 2017

Should be:
for j in range(max(1, i - window), min(N, i + window + 1))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.