Dynamic Time Warping - UCR Suite in C#

So, as mentioned in this comment, to achieve fast DTW calculations, one way is to use "lower bounds" in the DTW process, the UCR Suite is a great example of how this can be acheived.

I wanted to post this in my blog a long time ago, just didn't have the time to do everything for this.
the UCR Suite is written in C++ and since it's really easy moving around pointers than it is in C# safe code, I understand the choice of language.
However, with some thought the same code could be written in C# and be even faster and more efficient.

So, since i am primarily a .net coder, and wanted to only use managed code and no unsafe exceptions, I had to take the C++ code and port it to C# code.

When built in "Release" configurations it is quite faster than the C++ Suite.

Prof. Eamonn Keogh and company did a great job optimizing DTW and the applications are endless.

I've placed the C# Code as a Visual Studio 2010 Solution on github.
Get the code here!

This code is written without unsafe code.
I might publish another unsafe version for even better performance.

Dynamic Time Warping

Given two sequences of data, there are many ways to establish a metric to calculate their mutual distance.
Dynamic time warping is a fascinating algorithm invented by Sakoe and Chiba.
Basically, it's looking at the underlying data and seeing how much one sequence needs to change in order to be like the other sequence.
However, it searches for time differences in the data, and gives discounts for latent or stretched appearances of the same data.
Think of it this way, if you had one audio sample of you saying:
"Hello"
and another of you saying
"       Helloo"
You would want to detect these samples as being very very similar.
The lag in the second sample is insignificant, as well as the long "o" at the end.
This is where DTW comes to the rescue.

It's a simple algorithm, but it's not easy to find a C# implementation on the web.
So I've been asked if i could write it down.
I hope I'll be able to post the more interesting implementations of fast DTW algorithms in the future.

Basic DTW implementation in C#:

 public static double DTW(double[] arr1, double[] arr2)  
     {  
       int M = arr1.Length;  
       int N = arr2.Length;  
       var DTW = new double[M + 1,N + 1];  
       //Initial matrix  
       DTW[0, 0] = 0;  
       for (int j = 1; j <= M; j++)  
       {  
         DTW[j, 0] = double.PositiveInfinity;  
       }  
       for (int i = 1; i <= N; i++)  
       {  
         DTW[0, i] = double.PositiveInfinity;  
       }  
       //End of Init  
       for (int i = 1; i <= M; i++)  
       {  
         for (int j = 1; j <= N; j++)  
         {  
           double cost = Math.Abs(arr1[i - 1] - arr2[j - 1]);  
           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, N];  
     }  

References:

• Wikipedia - Dynamic time warping
• Sakoe, H. and Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, IEEE Transactions on Acoustics, Speech and Signal Processing, 26(1) pp. 43– 49, 1978, ISSN: 0096-3518