/
dtw_algorithm.py
111 lines (77 loc) · 3.59 KB
/
dtw_algorithm.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
import math
class Vector:
def __init__(self, x, y, z):
self.x = x
self.y = y
self.z = z
def __sub__(self, other): # for if you were to subtract one vector object from another, uses Pythagorean theorem
x = self.x - other.x
y = self.y - other.y
z = self.z - other.z
distance = math.sqrt(x ** 2 + y ** 2 + z ** 2)
return distance
class Gesture:
def __init__(self, vectors): # pass in list of Vector objects to create a Gesture
self.vectors = vectors
def __sub__(self, other): # to subtract one gesture from another (to get the difference, lower difference = more similar)
return dtw(self.vectors, other.vectors)
def create_gesture(vector_list):
vector_objects = []
for vector in vector_list: # convert vector data into vector objects
new_vector = Vector(vector[0], vector[1], vector[2])
vector_objects.append(new_vector)
return Gesture(vector_objects)
def distance_euclidean(a, b):
return abs(a-b)
# instead of building whole matrix, just build one row at a time to be more memory efficient
def dtw(x_axis, y_axis, distance=distance_euclidean):
# set up foundation row
row = []
current_x = x_axis[0]
for val_y in y_axis:
row.append(distance_euclidean(current_x, val_y))
for position_x in range(1, len(x_axis)):
current_x = x_axis[position_x]
temp = row[0]
row[0] = distance_euclidean(current_x, y_axis[0]) + row[0]
for i in range(1, len(y_axis)):
temp_2 = row[i]
row[i] = distance_euclidean(current_x, y_axis[i]) + min(row[i-1], temp, temp_2)
temp = temp_2
return row[-1]
# algorithm from http://en.wikipedia.org/wiki/Dynamic_time_warping#Implementation
def dtw_old(x_axis, y_axis, distance=distance_euclidean): # set_a and set_b are lists, default distance fn to use is distance_euclidean but could pass in a different fn to use instead if needed
x = len(x_axis) + 1
y = len(y_axis) + 1
dtw_matrix = build_borders(x, y)
# #for loops go from (1, 1) to (1, y-1) positions, then (2, 1) to (2, y-1) until you end up with a value for (x-1, y-1)
for i in range(1, x):
for j in range(1, y):
# get distance value for the cell
d = distance(x_axis[i-1], y_axis[j-1])
# fill in cell with distance plus min of earlier cell (above, to left, or diagonal towards origin)
dtw_matrix[i][j] = d + min(dtw_matrix[i-1][j],
dtw_matrix[i][j-1],
dtw_matrix[i-1][j-1])
# print out what matrix looks like
# for j in range(0, y):
# for i in range(0, x):
# print dtw_matrix[i][j],
# print ""
return dtw_matrix[x-1][y-1]
def build_borders(x, y):
# make empty matrix (list of lists) that are x across and y deep
dtw_matrix = [0]*x # set up matrix's full length along x-axis
for j in range(x):
temp_list = []
for i in range(y):
temp_list.append([]) # set up matrix's full length along y-axis
dtw_matrix[j] = temp_list # do it this way so that don't get a list of the same list over and over again, next line wouldn't work to only change value for one cell in matrix
dtw_matrix[0][0] = 0 # set first box to be 0 as starting point
# fill in top/left borders of matrix with infinity
inf = float("inf") # use this way to get infinity as a value in Python
for i in range(1, x):
dtw_matrix[i][0] = inf
for i in range(1, y):
dtw_matrix[0][i] = inf
return dtw_matrix