Algoritmo DTW (Dynamic Time Warping)

El algoritmo de alineamiento temporal dinámico nos permite medir la similitud entre dos secuencias que pueden variar en el tiempo o en el espacio.

Gracias a él, podremos calcular la distancia entre un gesto que realicemos y cada uno de los gestos patrón almacenados. El gesto reconocido será aquel que se encuentre a menor distancia.

Aunque podríamos haber elegido no utilizar este algoritmo, hay que tener en cuenta que, cuando realizamos un gesto, no siempre haremos un movimiento de la misma duración. Si calculásemos distancias euclídeas y tuviésemos dos vectores idénticos, pero uno desplazado ligeramente en el tiempo respecto al otro, al hacer la comparación punto a punto pensaríamos que ambos vectores son distintos. Sin embargo, con el DTW podremos realizar gestos con mayor o menor velocidad y darnos cuenta de que son idénticos.

Originalmente,  el algoritmo DTW se usaba para comparar distintos patrones acústicos en el reconocimiento automático del habla. Otras aplicaciones son el reconocimiento de gestos o de escritura.

Con esta entrada aprenderemos cuál es el fundamento matemático de este algoritmo y cómo ha sido programado en Java.

Fundamento matemático

Sean las secuencias X=(x1,x2,...,xN), de longitud N, e Y=(y1,y2,...,yM), de longitud M. Estas secuencias pueden ser señales discretas o señales muestreadas en puntos equidistantes en el tiempo.

Definimos un espacio vectorial F formado por estas muestras, de manera que:

Si queremos comparar dos secuencias, necesitamos una medida de costes o distancias locales; esta función se define como: 

Esta función nos devolverá un coste c(x,y) pequeño si x e y son similares y un coste c(x,y) elevado si son muy distintas. Si utilizamos esta función para calcular la distancia entre cada par de elementos de las secuencias X e Y, obtenemos una matriz de costes:

Cada elemento de esta matriz se define como c(n,m)=c(xn,ym). La matriz C nos permite alinear las secuencias X e Y, buscando un camino de alineación de coste mínimo a lo largo de ella.

Formalmente, un camino de alineación (warping path) se define como una secuencia:

 Esta secuencia debe satisfacer tres condiciones:

1. Condición de frontera:
   
    para que los primeros  y los últimos elementos de X e Y estén alineados y así las secuencias completas estén alineadas.
2.  Condición de monotonía:
    Con ella nos aseguramos de que elementos que se sucedan en el tiempo también se sucedan al ser alineados.
3. Condición de salto:
   
   Nos indica que no se puede omitir ningún elemento de X e Y y que el camino de alineamiento es continuo.

En la siguiente figura vemos claramente en qué consiste cada una de estas condiciones para una secuencia X de longitud N=7 y una secuencia Y de longitud M=9. Mientras que en (a) se cumplen las 3, en (b) se viola la condición de frontera, en (c) la de monotonía y en (d) la de salto.

El coste total cp(X,Y) de un camino de alineamiento p será la suma de todos los costes locales:

El camino de alineamiento óptimo entre X e Y es un camino de alineamiento p* que, entre todos los posibles caminos de alineamiento, tiene el coste total mínimo. Se define la distancia DTW entre X e Y como el coste total de p*:

La distancia DTW es la que calcularemos para comparar los gestos que han de ser reconocidos con los patrones.

Para determinar cuál es el camino óptimo p* entre dos secuencias, se podrían probar todos los caminos de alineamiento entre X e Y; sin embargo, la complejidad de este problema crecería de forma exponencial con N y M. Para simplificarlo, trabajaremos con la matriz D de costes acumulados:

En esta expresión, aparecen unas secuencias prefijo:

La distancia acumulada es la distancia entre la celda actual y la mínima de las distancias acumuladas para los elementos adyacentes:

Por lo tanto, el cálculo de distancia acumulada se podrá programar de manera recursiva y podremos calcular la distancia DTW en función de la acumulada:

Clase DTW.java

Una vez que conocemos el fundamento matemático del algoritmo DTW, es muy fácil traducirlo al lenguaje de programación y ver los pasos que sigue la clase DTW.java para el cálculo de distancias.

El código de esta clase no ha sido escrito por nosotros, sino que su autor es Cheol-Woo Jung y nosotros lo hemos adaptado para poder calcular la distancia DTW entre dos arrays de objetos de la clase Data (donde se almacenan las coordenadas de la aceleración sufrida por el acelerómetro del móvil al realizar un gesto).

Las variables que utilizamos son:

• Dos arrays de Data seq1 (coordenadas del gesto a reconocer) y seq2 (coordenadas del patrón).
• Un array bidimensional de enteros warpingPath, que representa un camino de alineamiento.
• 3 enteros n, m y k, que serán usados como índices para recorrer bucles.
• El double warpingDistance, donde quedará almacenada finalmente la distancia DTW que calculemos.

Los métodos de los que disponemos para este complejo cálculo de distancias son:

• protected double distanceBetween(Data p1, Data p2): Calcula la distancia euclídea entre 2 puntos cualesquiera que le pasemos como parámetro. Como en nuestro caso trabajamos con 3 coordenadas de aceleración, se calculará esta distancia como:
  
• protected int getIndexOfMinimum(double[] array): Devuelve el índice del elemento con valor mínimo en un array de doubles.
• public double getDistance(): Simplemente devuelve el valor de la variable “warpingDistance”. Tras realizar el cálculo de la distancia DTW, el valor final estará almacenado en esta variable y lo podremos recuperar con este getter.
• protected void reversePath(int[][] path): Invierte el orden de un camino de alineamiento, es decir, hace que su primer punto se convierta en el último y viceversa. Para ello, parte del array bidimensional “path” que le pasamos como parámetro y crea uno nuevo llamado “newPath” del mismo tamaño y con los elementos en orden decreciente. Finalmente almacena el nuevo camino de alineamiento en la variable “warpingPath”.
• public void compute(): Es el método más importante de la clase, que utiliza a todos los demás para poder determinar el camino de alineamiento óptimo y la distancia DTW asociada a él. Este proceso lo realiza a través de la matriz de distancias acumuladas.
  

Conociendo las variables y los métodos de los que disponemos, explicaremos de forma sencilla qué pasos sigue esta clase para obtener distancias DTW:

1. Se llama al constructor de la clase, pasando como parámetro un array de Data “sample” con las coordenadas del gesto a reconocer y otro “template” con las coordenadas del patrón con el que se quiere comparar.
2. Se inicializan las variables “seq1” con el array “sample” y “n” con su longitud; de la misma manera, “seq2” es inicializado con el array patrón “template” y “m” con su longitud.
3. Se inicializa el array bidimensional “warpingPath” con un tamaño de (N+M)x2 y establecemos que la distancia del camino óptimo “warpingDistance” inicialmente es 0.
4. El constructor invoca al método compute() para que calcule la distancia DTW. En primer lugar, éste crea una matriz “d”, que contiene la distancia euclídea entre cada punto de la primera y de la segunda secuencia que se están comparando (por lo tanto, es una matriz NxM). También crea la matriz “D”, que será la matriz de costes acumulados.
5. A partir de la matriz de distancias “d”, se va completando la matriz de costes acumulados “D”.
6. Gracias a la matriz de costes acumulados, se va construyendo el camino de alineamiento óptimo rellenando el array bidimensional “warpingPath”, de tamaño Kx2 (siendo K<N+M). El cálculo de este camino p*=(p1,p2,...,pK) se realiza en orden inverso, empezando por el punto final pK=(N,M). Cada elemento se obtiene como:
   
   
   
   
7.  Como tendremos el camino de alineamiento óptimo calculado en orden inverso, tendremos que invertirlo llamando al método reversePath().
8. La distancia DTW entre las dos secuencias, que almacenaremos en la variable “warpingDistance” y será el resultado final de nuestro cálculo, se obtiene como la distancia acumulada al llegar al último punto de este camino de alineamiento óptimo.

Con esta entrada damos por terminada la explicación de todo lo relacionado con nuestro sistema de reconocimiento de gestos mediante el acelerómetro de un dispositivo Android. En los próximos días os hablaremos de cómo hemos implementado el control del robot Kigo mediante Kinect.