m X[ ][ ][ ][ ]rX[ ][ ][ ][ ][ ]
X[ ][ ][ ][ ][ ]
X[ ][ ][ ][ ][ ]
[0]XXXXX
n
Each cell in the n*m matrix is defined as follows:
dtw(i,j) = local_distance(i,j) + MIN3(dtw(i-1,j-1), dtw(i-1,j), dtw(i,j-1))
Cells marked with an X are set to infinity.
The bottom-left cell is set to 0.
The top-right cell is the result.
At any given time, we only need two columns of the matrix, thus we use
two arrays dtw1 and dtw2 as our data structure.
[ ] [ ]
[ j ] [ j ]
[j-1] [j-1]
[ ] [ ]
[ X ] [ X ]
dtw1 dtw2
A cell can thus be calculated as follows:
dtw2(j) = local_distance(i,j) + MIN3(dtw2(j-1), dtw1(j), dtw1(j-1))
m X[ ][ ][ ][ ]r X[ ][ ][ ][ ][ ] X[ ][ ][ ][ ][ ] X[ ][ ][ ][ ][ ] [0]XXXXX n Each cell in the n*m matrix is defined as follows:
dtw(i,j) = local_distance(i,j) + MIN3(dtw(i-1,j-1), dtw(i-1,j), dtw(i,j-1)) Cells marked with an X are set to infinity. The bottom-left cell is set to 0. The top-right cell is the result. At any given time, we only need two columns of the matrix, thus we use two arrays dtw1 and dtw2 as our data structure. [ ] [ ] [ j ] [ j ] [j-1] [j-1] [ ] [ ] [ X ] [ X ] dtw1 dtw2 A cell can thus be calculated as follows: dtw2(j) = local_distance(i,j) + MIN3(dtw2(j-1), dtw1(j), dtw1(j-1))