edr

Editar distancia en señales reales

Sintaxis

dist = edr(x,y,tol)

[dist,ix,iy] = edr(x,y,tol)

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

[___] = edr(___,metric)

edr(___)

Descripción

dist = edr(x,y,tol) devuelve las secuencias entre y . devuelve el número mínimo de elementos que deben eliminarse de , , o ambos y , de modo que la suma de las distancias euclidianas entre los elementos de señal restantes se encuentra dentro de la tolerancia especificada, .Editar distancia en señales realesxyedrxyxytol

[dist,ix,iy] = edr(x,y,tol) devuelve la ruta de deformación de tal manera que ( ) y ( ) tengan el menor posible entre ellos.xixyiydist Cuándo y son matrices, y son tales que y están mínimamente separados.xyixiyx(:,ix)y(:,iy)

[___] = edr(x,y,maxsamp) restringe las operaciones de inserción para que la ruta de deformación permanezca dentro de las muestras de un ajuste en línea recta entre y .maxsampxy Esta sintaxis devuelve cualquiera de los argumentos de salida de las sintaxis anteriores.

[___] = edr(___,metric) especifica la métrica de distancia que se utilizará además de cualquiera de los argumentos de entrada de las sintaxis anteriores. puede ser uno de , , , o .metric'euclidean''absolute''squared''symmkl'

edr(___) sin argumentos de salida traza las señales originales y alineadas.

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

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

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

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

Ejemplos

Editar distancia entre Chirp y Sinusoid con valores atípicos

Genera dos señales reales: un chirrido y un sinusoides. Agregue una sección claramente periférica a cada señal.

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

Deformar las señales para que la distancia de edición entre ellas sea más pequeña. Especifique una tolerancia de 0,1. Trazar las señales alineadas, antes y después de la deformación, y la salida entre ellas.

tol = 0.1; edr(x,y,tol)

ans = 617 

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

y = cos(2*pi*18*(1:399)/400); y(100:115) = 7;  edr(x,y,tol);

Añade una parte imaginaria a cada señal. Restaure la frecuencia sinusoides inicial. Alinee las señales minimizando la suma de distancias euclidianas cuadradas.

x = exp(2i*pi*(3*(1:1000)/1000).^2); y = exp(2i*pi*9*(1:399)/400);  x(400:405) = 5+3j; x(405:410) = 7;  y(100:107) = 3j; y(108:115) = 7-3j;  edr(x,y,tol,'squared');

Editar distancia y trazado de deformación

Generar dos señales que consisten en dos picos distintos separados por valles de diferentes longitudes. Traza las señales.

x1 = [0 1 0 1 0]*.95; x2 = [0 1 0 0 0 0 0 0 0 0 1 0]*.95;  subplot(2,1,1) plot(x1) xlim([0 12]) subplot(2,1,2) plot(x2) xlim([0 12])

Calcular la distancia de edición entre las señales. Establezca una tolerancia pequeña para que las únicas coincidencias estén entre muestras iguales.

tol = 0.1;  figure edr(x1,x2,tol);

La distancia entre las señales es 7. Para alinearlos, es necesario eliminar los siete ceros centrales de o añadir siete ceros a .x2x1

Calcular la matriz, cuyo elemento inferior derecho corresponde a la distancia de edición.D Para la definición de , véase .DEditar distancia en señales reales

cnd = (abs(x1'-x2))>tol; D = zeros(length(x1)+1,length(x2)+1); D(1,2:end) = 1:length(x2); D(2:end,1) = 1:length(x1);  for h = 2:length(x1)+1     for k = 2:length(x2)+1         D(h,k) = min([D(h-1,k)+1 ...             D(h,k-1)+1 ...             D(h-1,k-1)+cnd(h-1,k-1)]);     end end  D

D = 6×13

     0     1     2     3     4     5     6     7     8     9    10    11    12
     1     0     1     2     3     4     5     6     7     8     9    10    11
     2     1     0     1     2     3     4     5     6     7     8     9    10
     3     2     1     0     1     2     3     4     5     6     7     8     9
     4     3     2     1     1     2     3     4     5     6     7     7     8
     5     4     3     2     1     1     2     3     4     5     6     7     7

Calcular y mostrar la ruta de deformación que alinea las señales.

[d,i1,i2] = edr(x1,x2,tol);  E = zeros(length(x1),length(x2));  for k = 1:length(i1)     E(i1(k),i2(k)) = NaN; end  E

E = 5×12

   NaN     0     0     0     0     0     0     0     0     0     0     0
     0   NaN     0     0     0     0     0     0     0     0     0     0
     0     0   NaN   NaN   NaN   NaN   NaN   NaN   NaN   NaN     0     0
     0     0     0     0     0     0     0     0     0     0   NaN     0
     0     0     0     0     0     0     0     0     0     0     0   NaN

Repita el cálculo, pero ahora restrinja la ruta de deformación para desviar como máximo dos elementos de la diagonal. Trazar las señales estiradas y la trayectoria de deformación. En el segundo gráfico, establezca las columnas de matriz para que se ejecuten a lo largo del eje.x

[dc,i1c,i2c] = edr(x1,x2,tol,2);  subplot(2,1,1) plot([x1(i1c);x2(i2c)]','.-') title(['Distance: ' num2str(dc)]) subplot(2,1,2) plot(i2c,i1c,'o-',[i2(1) i2(end)],[i1(1) i1(end)]) axis ij title('Warping Path')

La restricción da como resultado una distancia de edición más pequeña, pero distorsiona las señales. Si no se puede cumplir la restricción, se devuelve la distancia.edrNaN Vea esto forzando la ruta de deformación para desviar se desvíe como máximo de un elemento de la diagonal.

[dc,i1c,i2c] = edr(x1,x2,tol,1);  subplot(2,1,1) plot([x1(i1c);x2(i2c)]','.-') title(['Distance: ' num2str(dc)]) subplot(2,1,2) plot(i2c,i1c,'o-',[i2(1) i2(end)],[i1(1) i1(end)]) axis ij title('Warping Path')

Alinear muestras de escritura a mano manchadas

Los archivos y contienen dos muestras manuscritas de la palabra "MATLAB®."MATLAB1.gifMATLAB2.gif Cargue los archivos. Agregue valores atípicos obstinando los datos.

samp1 = fullfile(matlabroot,'examples','signal','MATLAB1.gif'); samp2 = fullfile(matlabroot,'examples','signal','MATLAB2.gif');  x = double(imread(samp1)); y = double(imread(samp2));  x(15:20,54:60) = 4000; y(15:20,84:96) = 4000;

Alinee las muestras de escritura a mano a lo largo del eje utilizando la distancia de edición.x Especifique una tolerancia de 450.

edr(x,y,450);

Argumentos de entrada

x — Señal de entrada

Vector | Matriz

Señal de entrada, especificada como un 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 un vector o matriz real o complejo.

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

tol — Tolerancia

escalar positivo

Tolerancia, especificada como escalar positiva.

Tipos de datos: single | double

maxsamp — Ancho de la ventana de ajuste

Inf (predeterminado) | entero positivo

Ancho de la ventana de ajuste, especificado como un entero positivo.

Tipos de datos: single | double

metric — Métrica de distancia

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

Métrica de distancia, especificada como , , , o .'euclidean''absolute''squared''symmkl' Si y son ambas señales -dimensionales, entonces prescribeXYKmetric D_mn( , ), la distancia entre la muestra y la muestra de .XYmXnY

• — Suma de raíz de diferencias cuadradas, también conocidas como euclidianas o'euclidean' ℓ₂ Métricas:

  $$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)}}$$

• — Suma de diferencias absolutas, también conocida como Manhattan, la manzana de la ciudad, el taxi o'absolute' ℓ₁ Métricas:

  $$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)}}$$

• — Plaza de la métrica euclidiana, que consiste en la suma de las diferencias cuadradas:'squared'

  $$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)}$$

• — Métrica simétrica de Kullback-Leibler.'symmkl' Esta métrica solo es válida para reales y positivos y:XY

  $$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,iy — Ruta de deformación

vectores de índices

Ruta de deformación, devuelta como vectores de índices. y tienen la misma longitud.ixiy Cada vector contiene una secuencia que aumenta monótonamente en la que los índices de los elementos de la señal correspondiente, o , se repiten el número necesario de veces.xy

Más acerca de

Editar distancia en señales reales

Dos señales con características equivalentes dispuestas en el mismo orden pueden parecer muy diferentes debido a las diferencias en las duraciones de sus secciones. distorsiona estas duraciones para que las entidades correspondientes aparezcan en la misma ubicación en un eje de tiempo común, resaltando así las similitudes entre las señales.edr El criterio utilizado para realizar la distorsión está diseñado para ser robusto a los valores atípicos.

Considere las señales bidimensionalesK

$$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 y muestras, respectivamente.MN Dado d_mn( , ), la distancia entre la muestra y la muestra de especificada en , la función se estira y en un conjunto común de instantes de modo que la entre las señales sea más pequeña.XYmXnYmetricedrXYdistancia de edición

Dado , un número real que es la tolerancia especificada en , declarar que la muestra y la ésima muestra de ifεtolmXnYPartido d_mn( , ) <  .XYε Si dos muestras, y , no coinciden, puede hacer que coincidan de tres maneras:mn

1. Quite de la primera señal, como cuando la siguiente muestra coincide con .mn Esta eliminación equivale a añadir a la segunda señal y obtener dos coincidencias consecutivas.m

2. Alargar la primera señal añadiendo en la posición una muestra que coincida y desplazando el resto de las muestras por una ubicación.n Esta adición equivale a eliminar el no coincidente de la segunda señal.n

3. Sustituya con en la primera señal o, equivalentemente, elimine ambos y .mnmn

La distancia de edición es el número total de estas operaciones que se necesitan para hacer que las dos señales coincidan. Este número no es único. Para calcular la distancia de edición más pequeña posible entre y , a partir de estos hechos:XY

1. Dos señales vacías tienen una distancia cero entre ellas.

2. La distancia entre una señal vacía y una señal con muestras es, porque es el número de muestras que se deben añadir a la señal vacía para recuperar la otra.LL Equivalentemente, es el número de muestras que se deben eliminar de una señal -sample para vaciarla.LL

Cree una matriz ( + 1)-by-( + 1), de tal forma que:MND

1. D_1,1 = 0.

2. D_m,1 = m – 1 Para m = 2, …, M + 1.

3. D_1,n = n – 1 Para n = 2, …, N + 1.

4. Para m, n > 1,

   $$D_{m,n}=\min \left\{\begin{array}{c}{D}_{m-1,n}+1\\ D_{m,n-1}+1\\ D_{m-1,n-1}+\{\begin{array}{c}0\Leftarrow d_{m,n}(X,Y)\le \epsilon \\ 1\Leftarrow d_{m,n}(X,Y)>\epsilon \end{array}\end{array}\right\}.$$

La distancia de edición más pequeña entre y es entoncesXY D_M+1,N+1.

El resultado a través de eso en esta distancia de edición más pequeña se parametriza por dos secuencias de la misma longitud, y , y es una combinación de movimientos de "rey de ajedrez":trayectoria de deformaciónDixiy

• Movimientos verticales: (m,n) → (m + 1,n) corresponde a la eliminación de una muestra de o agregar una muestra a .XY Cada movimiento aumenta la distancia de edición en 1.

• Movimientos horizontales: (m,n) → (m,n + 1) corresponde a la eliminación de una muestra de o agregar una muestra a .YX Cada movimiento aumenta la distancia de edición en 1.

• Movimientos diagonales: (m,n) → (m + 1,n + 1) corresponde a un partido si d_m,n( , ) o corresponde a la eliminación de una muestra de cada señal siXYε d_m,n( , ) >  .XYε Las coincidencias no aumentan la distancia. Las eliminaciones lo aumentan en 1.

Esta estructura garantiza que cualquier trayecto aceptable alinee las señales completas, no omita las muestras y no repita las características de la señal. Además, una ruta deseable se ejecuta cerca de la línea diagonal extendida entre d_1,1( , ) yXY d_M,N( , ).XY Esta restricción adicional, ajustada por el argumento, garantiza que la deformación compara secciones de longitud similar.maxsamp

La penalización por hacer que dos muestras coincidan es independiente de la diferencia de valor entre las muestras. Dos muestras que difieren un poco más que la tolerancia incurren en la misma penalización que dos muestras que son marcadamente diferentes. Por este motivo, la distancia de edición no se ve afectada por los valores atípicos. Por el contrario, repetir muestras para alinear dos señales tiene un costo, que no es el caso con la deformación dinámica del tiempo.

Referencias

[1] Chen, Lei, M. Tamer Özsu, and Vincent Oria. “Robust and Fast Similarity Search for Moving Object Trajectories.” Proceedings of 24th ACM International Conference on Management of Data (SIGMOD ‘05). 2005, pp. 491–502.

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

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

Consulte también

alignsignals | dtw | finddelay | findsignal | xcorr

Introducido en R2016b

×

Abrir ejemplo

Tiene una versión modificada de este ejemplo. ¿Desea abrir este ejemplo con sus modificaciones?

No, sobrescribir la versión modificada Sí