dtw

Distancia entre señales mediante la deformación dinámica del tiempo

Sintaxis

dist = dtw(x,y)

[dist,ix,iy] = dtw(x,y)

[___] = dtw(x,y,maxsamp)

[___] = dtw(___,metric)

dtw(___)

Descripción

dist = dtw(x,y) estira dos vectores, x y y, en un conjunto común de instantes tal que dist, la suma de las distancias euclidianas entre los puntos correspondientes, sea la más pequeña. Para estirar las entradas, dtw repite cada elemento de x e y tantas veces como sea necesario. Si x e y son matrices, dist las estira repitiendo sus columnas. En ese caso, x e y deben tener el mismo número de filas.

[dist,ix,iy] = dtw(x,y) devuelve el conjunto común de instantes, o la trayectoria de deformación, de modo que x(ix) e y(iy) tengan la menor dist posible entre ellos.

Los vectores ix e iy tienen la misma longitud. Cada uno de ellos contiene una secuencia monótonamente creciente en la que los índices de los elementos de la señal correspondiente, x o y, se repiten el número necesario de veces.

Cuando x e y son matrices, ix e iy son tales que x(:,ix) e y(:,iy) tienen una separación mínima.

[___] = dtw(x,y,maxsamp) restringe la trayectoria de deformación para que esté dentro de las muestras de maxsamp de un ajuste recto entre x e y. Esta sintaxis devuelve cualquiera de los argumentos de salida de las sintaxis anteriores.

[___] = dtw(___,metric) especifica la métrica de distancia que se debe utilizar además de cualquiera de los argumentos de entrada de las sintaxis anteriores.

dtw(___) sin argumentos de salida representa las señales originales y alineadas.

• Si las señales son vectores reales, la función muestra las dos señales originales en una subgráfica y las señales alineadas en una subgráfica debajo de la primera.

• Si las señales son vectores complejos, la función muestra las señales originales y alineadas en gráficas tridimensionales.

• Si las señales son matrices reales, la función utiliza imagesc para mostrar las señales originales y alineadas.

• Si las señales son matrices complejas, la función representa sus partes reales e imaginarias en la mitad superior e inferior de cada imagen.

Ejemplos

Deformación dinámica del tiempo de un chirp y una sinusoide

Genere dos señales reales, un chirp y una sinusoide.

x = cos(2*pi*(3*(1:1000)/1000).^2);
y = cos(2*pi*9*(1:399)/400);

Utilice la deformación dinámica del tiempo para alinear las señales de manera que la suma de las distancias euclidianas entre sus puntos sea la menor. Muestre las señales alineadas y la distancia.

dtw(x,y);

Cambie la frecuencia de la sinusoide al doble de su valor inicial. Repita el cálculo.

y = cos(2*pi*18*(1:399)/400);

dtw(x,y);

Añada una parte imaginaria a cada señal. Restablezca la frecuencia inicial de la sinusoide. Utilice la deformación dinámica del tiempo para alinear las señales mediante la minimización de la suma de las distancias euclidianas al cuadrado.

x = exp(2i*pi*(3*(1:1000)/1000).^2);
y = exp(2i*pi*9*(1:399)/400);

dtw(x,y,'squared');

Alinear muestras de escritura

Diseñe un tipo de letra que se asemeje a la salida de los primeros ordenadores. Utilícelo para escribir la palabra MATLAB®.

chr = @(x)dec2bin(x')-48;

M = chr([34 34 54 42 34 34 34]);
A = chr([08 20 34 34 62 34 34]);
T = chr([62 08 08 08 08 08 08]);
L = chr([32 32 32 32 32 32 62]);
B = chr([60 34 34 60 34 34 60]);

MATLAB = [M A T L A B];

Corrompa la palabra repitiendo columnas aleatorias de las letras y variando el espaciado. Muestre la palabra original y tres versiones corrompidas. Reinicie el generador de números aleatorios para obtener resultados reproducibles.

rng('default')

c = @(x)x(:,sort([1:6 randi(6,1,3)]));

subplot(4,1,1,'XLim',[0 60])
spy(MATLAB)
xlabel('')
ylabel('Original')

for kj = 2:4
    subplot(4,1,kj,'XLim',[0 60])
    spy([c(M) c(A) c(T) c(L) c(A) c(B)])
    xlabel('')
    ylabel('Corrupted')
end

Genere otras dos versiones corrompidas de la palabra. Alinéelas mediante la deformación dinámica del tiempo.

one = [c(M) c(A) c(T) c(L) c(A) c(B)];
two = [c(M) c(A) c(T) c(L) c(A) c(B)];

[ds,ix,iy] = dtw(one,two);

onewarp = one(:,ix);
twowarp = two(:,iy);

Muestre las palabras sin alinear y alineadas.

figure

subplot(4,1,1)
spy(one)
xlabel('')
ylabel('one')

subplot(4,1,2)
spy(two,'r')
xlabel('')
ylabel('two')

subplot(4,1,3)
spy(onewarp)
xlabel('')
ylabel('onewarp')

subplot(4,1,4)
spy(twowarp,'r')
xlabel('')
ylabel('twowarp')

Repita el cálculo mediante la funcionalidad incorporada de dtw.

dtw(one,two);

Trayectoria de deformación restringida

Genere dos señales compuestas por dos picos distintos separados por valles de diferente longitud. Represente las señales.

x1 = [0 1 0 0 0 0 0 0 0 0 0 1 0]*.95;
x2 = [0 1 0 1 0]*.95;

subplot(2,1,1)
plot(x1)
xl = xlim;
subplot(2,1,2)
plot(x2)
xlim(xl)

Alinee las señales sin restricción en la trayectoria de deformación. Para producir una alineación perfecta, la función necesita repetir una sola muestra de la señal más corta.

figure
dtw(x1,x2);

Represente la trayectoria de deformación y el ajuste recto entre las dos señales. Para lograr la alineación, la función amplía generosamente la depresión entre los picos.

[d,i1,i2] = dtw(x1,x2);

figure
plot(i1,i2,'o-',[i1(1) i1(end)],[i2(1) i2(end)])

Repita el cálculo, pero ahora restrinja la trayectoria de deformación para que se desvíe como máximo tres elementos del ajuste recto. Represente las señales estiradas y la trayectoria de deformación.

[dc,i1c,i2c] = dtw(x1,x2,3);

subplot(2,1,1)
plot([x1(i1c);x2(i2c)]','.-')
title(['Distance: ' num2str(dc)])
subplot(2,1,2)
plot(i1c,i2c,'o-',[i1(1) i1(end)],[i2(1) i2(end)])

La restricción impide que la deformación se concentre demasiado en un pequeño subconjunto de muestras, a expensas de la calidad de la alineación. Repita el cálculo con una restricción de una sola muestra.

dtw(x1,x2,1);

Deformación dinámica del tiempo de señales de voz

Cargue una señal de voz muestreada a $$F_s=7418Hz$$. El archivo contiene una grabación de una voz femenina diciendo la palabra "MATLAB®".

load mtlb

% To hear, type soundsc(mtlb,Fs)

Extraiga los dos segmentos que corresponden a las dos instancias del fonema /æ/. El primero se produce aproximadamente entre 150 ms y 250 ms, y el segundo entre 370 ms y 450 ms. Represente las dos formas de onda.

a1 = mtlb(round(0.15*Fs):round(0.25*Fs));
a2 = mtlb(round(0.37*Fs):round(0.45*Fs));

subplot(2,1,1)
plot((0:numel(a1)-1)/Fs+0.15,a1)
title('a_1')
subplot(2,1,2)
plot((0:numel(a2)-1)/Fs+0.37,a2)
title('a_2')
xlabel('Time (seconds)')

% To hear, type soundsc(a1,Fs), pause(1), soundsc(a2,Fs)

Deforme los ejes temporales de manera que la distancia euclidiana entre las señales se minimice. Calcule la "duración" compartida de las señales deformadas y represéntelas.

[d,i1,i2] = dtw(a1,a2);

a1w = a1(i1);
a2w = a2(i2);

t = (0:numel(i1)-1)/Fs;
duration = t(end)

duration = 
0.1297

subplot(2,1,1)
plot(t,a1w)
title('a_1, Warped')
subplot(2,1,2)
plot(t,a2w)
title('a_2, Warped')
xlabel('Time (seconds)')

% To hear, type soundsc(a1w,Fs), pause(1), sound(a2w,Fs)

Repita el experimento con una palabra completa. Cargue un archivo que contiene la palabra "strong" pronunciada por una mujer y por un hombre. Las señales se muestrean a 8 kHz.

load('strong.mat')

% To hear, type soundsc(her,fs), pause(2), soundsc(him,fs)

Deforme los ejes temporales de manera que la distancia absoluta entre las señales se minimice. Represente las señales originales y las transformadas. Calcule su "duración" deformada compartida.

dtw(her,him,'absolute');
legend('her','him')

[d,iher,ihim] = dtw(her,him,'absolute');
duration = numel(iher)/fs

duration = 
0.8394

% To hear, type soundsc(her(iher),fs), pause(2), soundsc(him(ihim),fs)

Deformación dinámica del tiempo para la alineación de escritura manuscrita

Los archivos MATLAB1.gif y MATLAB2.gif contienen dos muestras manuscritas de la palabra "MATLAB®". Cargue los archivos y alinéelos a lo largo del eje x mediante la deformación dinámica del tiempo.

samp1 = 'MATLAB1.gif';
samp2 = 'MATLAB2.gif';

x = double(imread(samp1));
y = double(imread(samp2));

dtw(x,y);

Argumentos de entrada

x — Señal de entrada

vector | matriz

Señal de entrada, especificada como vector o matriz real o complejo.

Tipos de datos: single | double
Soporte de números complejos: Sí

y — Señal de entrada

vector | matriz

Señal de entrada, especificada como vector o matriz real o complejo.

Tipos de datos: single | double
Soporte de números complejos: Sí

maxsamp — Anchura de la ventana de ajuste

Inf (predeterminado) | entero positivo

Anchura de la ventana de ajuste, especificada como entero positivo.

Tipos de datos: single | double

metric — Métrica de distancia

'euclidean' (predeterminado) | 'absolute' | 'squared' | 'symmkl'

Métrica de distancia, especificada como 'euclidean', 'absolute', 'squared' o 'symmkl'. Si X e Y son ambas señales de K dimensiones, metric prescribe d_mn(X,Y), la distancia entre la m-ésima muestra de X y la n-ésima muestra de Y. Consulte Deformación dinámica del tiempo para obtener más información sobre d_mn(X,Y).

• 'euclidean': suma de diferencias al cuadrado, también conocida como métrica euclidiana o ℓ₂:

  $$d_{mn}(X,Y)=\sqrt{{\displaystyle \sum _{k=1}^K{\left(x_{k,m}-y_{k,n}\right)}^{*}\left(x_{k,m}-y_{k,n}\right)}}$$

• 'absolute': suma de diferencias absolutas, también conocida como métrica Manhattan, de ciudad (city block), de taxista (taxicab) o ℓ₁:

  $$d_{mn}(X,Y)={\displaystyle \sum _{k=1}^K\left|x_{k,m}-y_{k,n}\right|}={\displaystyle \sum _{k=1}^K\sqrt{{\left(x_{k,m}-y_{k,n}\right)}^{*}\left(x_{k,m}-y_{k,n}\right)}}$$

• 'squared': cuadrado de la métrica euclidiana, compuesta por la suma de las diferencias al cuadrado:

  $$d_{mn}(X,Y)={\displaystyle \sum _{k=1}^K{\left(x_{k,m}-y_{k,n}\right)}^{*}\left(x_{k,m}-y_{k,n}\right)}$$

• 'symmkl': métrica de Kullback-Leibler simétrica. Esta métrica solo es válida para X e Y reales y positivos:

  $$d_{mn}(X,Y)={\displaystyle \sum _{k=1}^K\left(x_{k,m}-y_{k,n}\right)\left(\log x_{k,m}-\log y_{k,n}\right)}$$

Argumentos de salida

dist — Distancia mínima

escalar real positivo

Distancia mínima entre señales, devuelta como un escalar real positivo.

ix — Trayectoria de deformación de la primera señal

vector de índices | matriz de índices

Trayectoria de deformación de la primera señal, devuelta como vector o matriz de índices.

iy — Trayectoria de deformación de la segunda señal

vector de índices | matriz de índices

Trayectoria de deformación de la segunda señal, devuelta como vector o matriz de índices.

Más acerca de

Deformación dinámica del tiempo

Dos señales con características equivalentes dispuestas en el mismo orden pueden parecer muy distintas debido a las diferencias en las duraciones de sus secciones. La deformación dinámica del tiempo distorsiona estas duraciones para que las características correspondientes aparezcan en la misma ubicación en un eje temporal común, lo que pone de manifiesto las similitudes entre las señales.

Considere las dos señales de K dimensiones

$$X=\left[\begin{array}{cccc}{x}_{1,1}& x_{1,2}& \cdots & x_{1,M}\\ x_{2,1}& x_{2,2}& \cdots & x_{2,M}\\ ⋮& ⋮& \ddots & ⋮\\ x_{K,1}& x_{K,2}& \cdots & x_{K,M}\end{array}\right]$$

y

$$Y=\left[\begin{array}{cccc}{y}_{1,1}& y_{1,2}& \cdots & y_{1,N}\\ y_{2,1}& y_{2,2}& \cdots & y_{2,N}\\ ⋮& ⋮& \ddots & ⋮\\ y_{K,1}& y_{K,2}& \cdots & y_{K,N}\end{array}\right],$$

que tienen M y N muestras respectivamente. A partir de d_mn(X,Y), la distancia entre la m-ésima muestra de X y la n-ésima muestra de Y especificada en metric, dist estira X e Y hacia un conjunto común de instantes tal que una medida de distancia global entre señales sea la menor.

Al principio, la función ordena todos los valores posibles de d_mn(X,Y) en una rejilla con la forma

A continuación, dist busca una trayectoria a través de la rejilla, parametrizada por dos secuencias de la misma longitud, ix e iy, de forma que

$$d={\displaystyle \sum _{\begin{array}{c}m\in \text{ix}\\ n\in \text{iy}\end{array}}{d}_{mn}(X,Y)}$$

sea mínima. Las trayectorias aceptables de dist comienzan en d₁₁(X,Y), terminan en d_MN(X,Y) y son combinaciones de movimientos del “rey en ajedrez”:

• Movimientos verticales: (m,n) → (m + 1,n)

• Movimientos horizontales: (m,n) → (m,n + 1)

• Movimientos diagonales: (m,n) → (m + 1,n + 1)

Esta estructura garantiza que cualquier trayectoria aceptable alinee las señales completas, no omita muestras y no repita características de la señal. Además, una trayectoria conveniente discurre cerca de la línea diagonal que se extiende entre d₁₁(X,Y) y d_MN(X,Y). Esta restricción adicional, ajustada por el argumento maxsamp garantiza que la deformación compare secciones de longitud similar y no sobreajuste las características atípicas.

Esta es una posible trayectoria a través del entramado:

No se permiten las siguientes trayectorias:

No alinea las señales completas	Omite muestras	Vuelve sobre sí misma repitiendo una característica

Referencias

[1] Paliwal, K. K., Anant Agarwal, and Sarvajit S. Sinha. "A Modification over Sakoe and Chiba’s Dynamic Time Warping Algorithm for Isolated Word Recognition." Signal Processing. Vol. 4, 1982, pp. 329–333.

[2] Sakoe, Hiroaki, and Seibi Chiba. "Dynamic Programming Algorithm Optimization for Spoken Word Recognition." IEEE^® Transactions on Acoustics, Speech, and Signal Processing. Vol. ASSP-26, No. 1, 1978, pp. 43–49.

Capacidades ampliadas

Generación de código C/C++
Genere código C y C++ mediante MATLAB® Coder™.

Historial de versiones

Introducido en R2016a

Consulte también

alignsignals | edr | finddelay | findsignal | xcorr