Main Content

dtw

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

Descripción

ejemplo

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.

ejemplo

[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.

ejemplo

[___] = 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.

ejemplo

[___] = 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.

ejemplo

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

contraer todo

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);

Figure contains 2 axes objects. Axes object 1 with title Original Signals contains 2 objects of type line. Axes object 2 with title Aligned Signals (Euclidean Distance: 21.593428) contains 2 objects of type line.

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);

Figure contains 2 axes objects. Axes object 1 with title Original Signals contains 2 objects of type line. Axes object 2 with title Aligned Signals (Euclidean Distance: 169.301757) contains 2 objects of type line.

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');

Figure contains 2 axes objects. Axes object 1 with title Original Signals contains 2 objects of type line. Axes object 2 with title Aligned Signals (Squared Euclidean Distance: 2.113124) contains 2 objects of type line.

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

Figure contains 4 axes objects. Axes object 1 contains an object of type line. Axes object 2 contains an object of type line. Axes object 3 contains an object of type line. Axes object 4 contains an object of type line.

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')

Figure contains 4 axes objects. Axes object 1 contains an object of type line. Axes object 2 contains an object of type line. Axes object 3 contains an object of type line. Axes object 4 contains an object of type line.

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

dtw(one,two);

Figure contains 6 axes objects. Axes object 1 with title Overlaid Aligned Signals contains an object of type image. Axes object 2 with title Aligned Signal (Y) contains an object of type image. Axes object 3 with title Aligned Signal (X) contains an object of type image. Axes object 4 with title Overlaid Original Signals contains an object of type image. Axes object 5 with title Original Signal (Y) contains an object of type image. Axes object 6 with title Original Signal (X) contains an object of type image.

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)

Figure contains 2 axes objects. Axes object 1 contains an object of type line. Axes object 2 contains an object of type line.

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);

Figure contains 2 axes objects. Axes object 1 with title Original Signals contains 2 objects of type line. Axes object 2 with title Aligned Signals (Euclidean Distance: 0.000000) contains 2 objects of type line.

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)])

Figure contains an axes object. The axes object contains 2 objects of type line.

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)])

Figure contains 2 axes objects. Axes object 1 with title Distance: 1.9 contains 2 objects of type line. Axes object 2 contains 2 objects of type line.

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);

Figure contains 2 axes objects. Axes object 1 with title Original Signals contains 2 objects of type line. Axes object 2 with title Aligned Signals (Euclidean Distance: 7.600000) contains 2 objects of type line.

Cargue una señal de voz muestreada a Fs=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)')

Figure contains 2 axes objects. Axes object 1 with title a indexOf 1 baseline contains an object of type line. Axes object 2 with title a indexOf 2 baseline contains an object of type line.

% 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)')

Figure contains 2 axes objects. Axes object 1 with title a indexOf 1 baseline , blank W a r p e d contains an object of type line. Axes object 2 with title a indexOf 2 baseline , blank W a r p e d contains an object of type line.

% 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')

Figure contains 2 axes objects. Axes object 1 with title Original Signals contains 2 objects of type line. Axes object 2 with title Aligned Signals (Absolute Distance: 163.663272) contains 2 objects of type line. These objects represent 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)

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);

Figure contains 6 axes objects. Axes object 1 with title Overlaid Aligned Signals contains an object of type image. Axes object 2 with title Aligned Signal (Y) contains an object of type image. Axes object 3 with title Aligned Signal (X) contains an object of type image. Axes object 4 with title Overlaid Original Signals contains an object of type image. Axes object 5 with title Original Signal (Y) contains an object of type image. Axes object 6 with title Original Signal (X) contains an object of type image.

Argumentos de entrada

contraer todo

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

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

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

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

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

Tipos de datos: single | double

Métrica de distancia, especificada como 'euclidean', 'absolute', 'squared' o 'symmkl'. Si X e Y son ambas señales de K dimensiones, metric prescribe dmn(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 dmn(X,Y).

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

    dmn(X,Y)=k=1K(xk,myk,n)*(xk,myk,n)

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

    dmn(X,Y)=k=1K|xk,myk,n|=k=1K(xk,myk,n)*(xk,myk,n)

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

    dmn(X,Y)=k=1K(xk,myk,n)*(xk,myk,n)

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

    dmn(X,Y)=k=1K(xk,myk,n)(logxk,mlogyk,n)

Argumentos de salida

contraer todo

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

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

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

Más acerca de

contraer todo

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=[x1,1x1,2x1,Mx2,1x2,2x2,MxK,1xK,2xK,M]

y

Y=[y1,1y1,2y1,Ny2,1y2,2y2,NyK,1yK,2yK,N],

que tienen M y N muestras respectivamente. A partir de dmn(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 dmn(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=mixniydmn(X,Y)

sea mínima. Las trayectorias aceptables de dist comienzan en d11(X,Y), terminan en dMN(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 d11(X,Y) y dMN(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 completasOmite muestrasVuelve 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

| | | |