Sunday, April 29, 2012

Iterative DTW

In my previous post : Dynamic Time Warping, I've added the Iterative version of the classic DTW algorithm.
However, the matrix initialization, with the "Positive Infinity" is actually for the recursive version of the algorithm.
The algorithm will work, however this is the more classic iterative version:

 public static double DTW2(double[] arr1, double[] arr2)  
     {  
       int M = arr1.Length;  
       int N = arr2.Length;  
       var DTW = new double[M, N];  
       //Initial matrix  
       DTW[0, 0] = Math.Abs(arr1[0] - arr2[0]);  
       for (int i = 1; i < M; i++)  
       {  
         DTW[i, 0] = Math.Abs(arr1[i] - arr2[0]) + DTW[i - 1, 0];  
       }  
       for (int j = 1; j < N; j++)  
       {  
         DTW[0, j] = Math.Abs(arr1[0] - arr2[j]) + DTW[0, j - 1];  
       }  
       //End of Init  
       for (int i = 1; i < M; i++)  
       {  
         for (int j = 1; j < N; j++)  
         {  
           double cost = Math.Abs(arr1[i] - arr2[j]);  
           DTW[i, j] = cost + Math.Min(DTW[i - 1, j],        // insertion  
                         Math.Min(DTW[i, j - 1],    // deletion  
                              DTW[i - 1, j - 1])); // match  
         }  
       }  
       return DTW[M-1, N-1];  
     }  

1 comment: