dtw

Расстояние между сигналами с помощью динамической трансформации временной шкалы

Описание

пример

dist = dtw(x,y) фрагменты два вектора, x и y, на единый набор моментов, таким образом, что dist, сумма Евклидовых расстояний между соответствующими точками, является самым маленьким. Расширять входные параметры, dtw повторения каждый элемент x и y так же много раз по мере необходимости. Если x и y матрицы, затем dist расширяет их путем повторения их столбцов. В этом случае, x и y должен иметь одинаковое число строк.

пример

[dist,ix,iy] = dtw(x,y) возвращает единый набор моментов или деформирующийся путь, такой что x(ix) и y(iy) имейте самый маленький dist между ними.

Векторы ix и iy имейте ту же длину. Каждый содержит монотонно увеличивающуюся последовательность в который индексы к элементам соответствующего сигнала, x или y, повторяются необходимое число раз.

Когда x и y матрицы, ix и iy таковы что x(:,ix) и y(:,iy) минимально разделяются.

пример

[___] = dtw(x,y,maxsamp) ограничивает деформирующийся путь, чтобы быть в maxsamp выборки прямолинейной подгонки между x и y. Этот синтаксис возвращает любой из выходных аргументов предыдущих синтаксисов.

пример

[___] = dtw(___,metric) задает метрику расстояния, чтобы использовать в дополнение к любому из входных параметров в предыдущих синтаксисах.

пример

dtw(___) без выходных аргументов строит исходные и выровненные сигналы.

  • Если сигналы являются векторами действительных чисел, функция отображает два исходных сигнала на подграфике и выровненные сигналы в подграфике ниже первого.

  • Если сигналы являются комплексными векторами, функция отображает исходные и выровненные сигналы в 3D графиках.

  • Если сигналы являются действительными матрицами, функциональным использованием imagesc отобразить исходные и выровненные сигналы.

  • Если сигналы являются комплексными матрицами, графики функций их действительные и мнимые части в верхней и нижней половине каждого изображения.

Примеры

свернуть все

Сгенерируйте два действительных сигнала: щебет и синусоида.

x = cos(2*pi*(3*(1:1000)/1000).^2);
y = cos(2*pi*9*(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: 21.593428) contains 2 objects of type line.

Измените частоту синусоиды в дважды ее начальное значение. Повторите расчет.

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.

Добавьте мнимую часть в каждый сигнал. Восстановите начальную частоту синусоиды. Используйте динамическую трансформацию временной шкалы, чтобы выровнять сигналы путем минимизации суммы Евклидовых расстояний в квадрате.

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.

Создайте гарнитуру, которая напоминает выход ранних компьютеров. Используйте его, чтобы записать слову 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];

Повредите слово путем повторения случайных столбцов букв и варьирования интервала. Покажите исходное слово и три поврежденных версии. Сбросьте генератор случайных чисел для восстанавливаемых результатов.

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.

Сгенерируйте две более поврежденных версии слова. Выровняйте их использующий динамическую трансформацию временной шкалы.

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

Отобразите невыровненные и выровненные слова.

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.

Повторите расчет с помощью встроенной функциональности 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.

Сгенерируйте два сигнала, состоящие из двух отличных peaks, разделенных оврагами различных длин. Постройте сигналы.

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.

Выровняйте сигналы без ограничения на деформирующийся путь. Чтобы произвести совершенное выравнивание, функция должна повторить только одну выборку более короткого сигнала.

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.

Постройте деформирующийся путь и прямолинейную подгонку между двумя сигналами. Чтобы достигнуть выравнивания, функция расширяет канавку между peaks великодушно.

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

Повторите расчет, но теперь ограничьте деформирующийся путь отклонять самое большее три элемента от прямолинейной подгонки. Постройте расширенные сигналы и деформирующийся путь.

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

Ограничение устраняет деформирование от концентрации слишком много на небольшом подмножестве выборок, за счет качества выравнивания. Повторите вычисление с ограничением с одной выборкой.

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.

Загрузите речевой сигнал, произведенный в Fs=7418Hz. Файл содержит запись женского голоса, говоря слово "MATLAB®".

load mtlb

% To hear, type soundsc(mtlb,Fs)

Извлеките два сегмента, которые соответствуют двум экземплярам/æ/фонемы. Первый происходит примерно между 150 мс и 250 мс, и второй между 370 мс и 450 мс. Постройте эти две формы волны.

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)

Деформируйте оси времени так, чтобы Евклидово расстояние между сигналами было минимизировано. Вычислите разделяемую "длительность" деформированных сигналов и постройте их.

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

Повторите эксперимент с полным словом. Загрузите файл, содержащий слово, "сильное", произнесенное женщиной и мужчиной. Сигналы производятся на уровне 8 кГц.

load('strong.mat')

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

Деформируйте оси времени так, чтобы абсолютное расстояние между сигналами было минимизировано. Постройте исходные и преобразованные сигналы. Вычислите их разделяемую деформированную "длительность".

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)

Файлы MATLAB1.gif и MATLAB2.gif содержите две рукописных выборки слова "MATLAB®". Загрузите файлы и выровняйте их вдоль оси X с помощью динамической трансформации временной шкалы.

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.

Входные параметры

свернуть все

Входной сигнал в виде вектора действительных чисел или комплексного вектора или матрицы.

Типы данных: single | double
Поддержка комплексного числа: Да

Входной сигнал в виде вектора действительных чисел или комплексного вектора или матрицы.

Типы данных: single | double
Поддержка комплексного числа: Да

Ширина окна корректировки в виде положительного целого числа.

Типы данных: single | double

Метрика расстояния в виде 'euclidean', 'absolute', 'squared', или 'symmkl'. Если X и Y является оба K - размерные сигналы, то metric предписывает dmn (X, Y), расстояние между m th выборка X и n th выборка Y. Смотрите Динамическую трансформацию временной шкалы для получения дополнительной информации о dmn (X, Y).

  • 'euclidean' — Корневая сумма различий в квадрате, также известных как Евклидово или 2 метрики:

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

  • 'absolute' — Сумма абсолютных разностей, также известных как Манхэттен, городской квартал, такси или 1 метрика:

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

  • 'squared' — Квадрат Евклидовой метрики, состоя из суммы различий в квадрате:

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

  • 'symmkl' — Симметричная метрика Kullback-Leibler. Эта метрика допустима только для действительных и положительных X и Y:

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

Выходные аргументы

свернуть все

Минимальное расстояние между сигналами, возвращенными как положительный действительный скаляр.

Деформирование пути для первого сигнала, возвращенного как вектор или матрица индексов.

Деформирование пути для второго сигнала, возвращенного как вектор или матрица индексов.

Больше о

свернуть все

Динамическая трансформация временной шкалы

Два сигнала с эквивалентными функциями, расположенными в том же порядке, могут казаться очень отличающимися из-за различий в длительности их разделов. Динамическая трансформация временной шкалы искажает эту длительность так, чтобы соответствующие функции появились в том же местоположении на общей оси времени, таким образом подсветив общие черты между сигналами.

Рассмотрите два K - размерные сигналы

X=[x1,1x1,2x1,Mx2,1x2,2x2,MxK,1xK,2xK,M]

и

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

которые имеют M и выборки N, соответственно. Учитывая dmn (X, Y), расстояние между m th выборка X и n th выборка Y задано в metricdist X и Y фрагментов на единый набор моментов, таким образом, что глобальная мера по расстоянию от сигнала к сигналу является самой маленькой.

Первоначально, функция располагает все возможные значения dmn (X, Y) в решетку формы

Затем dist ищет путь через решетку — параметрированный двумя последовательностями той же длины, ix и iy— таким образом, что

d=mixniydmn(X,Y)

минимально. Приемлемый dist пути запускаются в d 11 (X, Y), конец в dMN (X, Y), и являются комбинациями “шахматного короля” перемещения:

  • Вертикальные перемещения: (m, n) → (m + 1, n)

  • Горизонтальные перемещения: (m, n) → (m, n + 1)

  • Диагональные перемещения: (m, n) → (m + 1, n + 1)

Эта структура гарантирует, что любой приемлемый путь выравнивает полные сигналы, не пропускает выборки и не повторяет функции сигнала. Кроме того, привлекательный путь запускается близко к диагональной линии, расширенной между d 11 (X, Y) и dMN (X, Y). Это дополнительное ограничение, настроенное maxsamp аргумент, гарантирует, что деформирование сравнивает разделы подобной длины и не сверхсоответствует функциям выброса.

Это - возможный путь через решетку:

Следующие пути не позволены:

Не выравнивает целые сигналыВыборки пропусковВозвращается на себе, повторяя функцию

Ссылки

[1] Paliwal, K. K. Anant Agarwal и Сарвэджит С. Синха. "Модификация по Sakoe и Алгоритму Динамической трансформации временной шкалы Чибы для Изолированного Распознавания слов". Обработка сигналов. Издание 4, 1982, стр 329–333.

[2] Sakoe, Hiroaki и Чиба Seibi. "Динамическая оптимизация алгоритма программирования для распознавания произносимого слова". IEEE® Транзакции на Акустике, Речи и Обработке сигналов. Издание ASSP-26, № 1, 1978, стр 43–49.

Расширенные возможности

Генерация кода C/C++
Генерация кода C и C++ с помощью MATLAB® Coder™.

Смотрите также

| | | |

Введенный в R2016a