I'm currently working on an DTW algorithm implementation and do have a question about how DTW works if the next steps are the same or if the correct next step is the actually not less-cost one. I do understand that the next step DTW takes if we're going from left top corner to the right bottom corner of the matrix looks like that:
min({D[i + 1][j + 1], D[i][j + 1], D[i + 1][j]})
But here's a couple of examples that are bothering me.
Example 1:
1 2 2 6
4 0 4 5
8 3 3 8
9 8 6 1
The DTW path here is: 1,1 -> 2,2 -> 3,3 -> 4,4
In this example, we can see that when we're on point (2,2), which is 0, there're three options: (3,3) which is 3, (2,3) which is 4 and (3,2) which is 3. How the algorithm decides that (3,3) is better than (3,2) in this situation?
Example 2:
2 6 2 6
1 3 7 5
8 9 2 8
9 8 6 1
The DTW path here is: 1,1 -> 2,2 -> 3,3 -> 4,4
In this example, when we're on point (1,1), there're three options: (2,2) which is 3, (1,2) which is 6 and (2,1) which is 1. But, despite (2,1) being the less-cost next step locally -- the algorithm will choose to go to (2,2) next, which is the bigger than (2,1), but at the end will provide the less-cost way from (1,1) to (3,3).
So, my question is what am I missing here? I think I misunderstood some ideas of how DTW works since it's not obvious to me, why are we looking for the minimal value next step and at the same time, ending up picking the one that is not the minimal one, but at the end leads us to the less-cost path.
Thank you for your patience!
