Dynamic Time Warping

DynamicTimeWarping.java

package processing.segmentation;

import java.util.ArrayList;

/**
 * Compute the Dynamic Time Warping Distance 
 *
 * @author Daniel Kohlsdorf
 */
public class DynamicTimeWarping {

    /**
     * Save DTW matrix
     */
    private double dtw[][];

    /**
     * Compute the Euclidean distance between two vectors
     */
    public static double euc(double[] x, double[] y) {
        double dist = 0.0;
        for (int i = 0; i < x.length; i++) {
            dist += Math.pow(x[i] - y[i], 2);
        }
        return Math.sqrt(dist);
    }
    
    /**
     * Compute the min of three values
     */
    private double min(double x, double y, double z) {
        double min = x;
        if (y < min) {
            min = y;
        }
        if (z < min) {
            min = z;
        }
        return min;
    }

    /**
     * The actual dynamic time warping algorithm
     */
    public double dist(ArrayList<double[]> x, ArrayList<double[]> y) {
        int n = x.size();
        int m = y.size();
        dtw = new double[n + 1][m + 1];
        
        /**
         * INIT
         */
        for (int i = 1; i < n + 1; i++) {
        	dtw[i][0] = Double.POSITIVE_INFINITY;
        }

        for (int j = 1; j < m + 1; j++) {
        	dtw[0][j] = Double.POSITIVE_INFINITY;
        }

        dtw[0][0] = 0.0;
        
        /**
         * Recursion
         */
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                dtw[i][j] = euc(x.get(i - 1), y.get(j - 1)) + min(
                        dtw[i][j - 1],
                        dtw[i - 1][j],
                        dtw[i - 1][j - 1]);
            }
        }
        
        return dtw[n][m];
    }

}