exponenta event banner

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(___) без выходных аргументов строит график исходного и выровненного сигналов.

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

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

  • Если сигналы являются вещественными матрицами, функция использует 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. Axes 1 with title Original Signals contains 2 objects of type line. Axes 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. Axes 1 with title Original Signals contains 2 objects of type line. Axes 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. Axes 1 with title Original Signals contains 2 objects of type line. Axes 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. Axes 1 contains an object of type line. Axes 2 contains an object of type line. Axes 3 contains an object of type line. Axes 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. Axes 1 contains an object of type line. Axes 2 contains an object of type line. Axes 3 contains an object of type line. Axes 4 contains an object of type line.

Повторите вычисления, используя встроенные функциональные возможности dtw.

dtw(one,two);

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

Генерировать два сигнала, состоящих из двух различных пиков, разделенных впадинами разной длины. Постройте график сигналов.

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. Axes 1 contains an object of type line. Axes 2 contains an object of type line.

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

figure
dtw(x1,x2);

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

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

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

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

Figure contains an axes. The axes 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. Axes 1 with title Distance: 1.9 contains 2 objects of type line. Axes 2 contains 2 objects of type line.

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

dtw(x1,x2,1);

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

Загрузите речевой сигнал, дискретизированный при Fs = 7418 Гц. Файл содержит запись женского голоса, говорящего слово «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. Axes 1 with title a_1 contains an object of type line. Axes 2 with title a_2 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. Axes 1 with title a_1, Warped contains an object of type line. Axes 2 with title a_2, Warped 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. Axes 1 with title Original Signals contains 2 objects of type line. Axes 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. Axes 1 with title Overlaid Aligned Signals contains an object of type image. Axes 2 with title Aligned Signal (Y) contains an object of type image. Axes 3 with title Aligned Signal (X) contains an object of type image. Axes 4 with title Overlaid Original Signals contains an object of type image. Axes 5 with title Original Signal (Y) contains an object of type image. Axes 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-м образцом X и n-м образцом Y. Для получения дополнительной информации о dmn (X, Y) см. Динамическое искажение времени.

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

    dmn (X, Y) =∑k=1K (xk, m yk, n) * (xk, m − yk, n)

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

    dmn (X, Y) =∑k=1K'xk,m−yk,n|=∑k=1K (xk, m yk, n) * (xk, m − yk, n)

  • 'squared' - квадрат евклидовой метрики, состоящий из суммы квадратичных разностей:

    dmn (X, Y) =∑k=1K (xk, m yk, n) * (xk, m − yk, n)

  • 'symmkl' - симметричная метрика Куллбэка-Лейблера. Эта метрика действительна только для вещественных и положительных X и Y:

    dmn (X, Y) =∑k=1K (xk, m yk, n) (logxk, m − logyk, n)

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

свернуть все

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

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

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

Подробнее

свернуть все

Динамическая деформация по времени

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

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

X=[x1,1x1,2⋯x1,Mx2,1x2,2⋯x2,M⋮⋮⋱⋮xK,1xK,2⋯xK,M]

и

Y=[y1,1y1,2⋯y1,Ny2,1y2,2⋯y2,N⋮⋮⋱⋮yK,1yK,2⋯yK,N],

которые имеют M и N образцов соответственно. Учитывая dmn (X, Y), расстояние между m-м образцом X и n-м образцом Y, указанным вmetric, dist растягивает X и Y на общий набор моментов, так что измерение глобального расстояния сигнал-сигнал является наименьшим.

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

Тогда dist ищет путь через решетку, параметризованный двумя последовательностями одинаковой длины,ix и iy- такое, что

d=∑m∈ixn∈iydmn (X, Y)

минимально. Приемлемый dist пути начинаются на d11 (X, Y), заканчиваются на dMN (X, Y) и представляют собой комбинации ходов «шахматного короля»:

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

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

  • Диагональные ходы: (м, н ) → ( м + 1, н + 1)

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

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

Следующие пути не разрешены:

Не выравнивает все сигналыПропускает образцыВозврат к самому себе, повторяя элемент

Ссылки

[1] Паливал, К. К., Анант Агарвал и Сарваджит С. Синха. «Модификация алгоритма динамического искажения времени Сакоэ и Тибы для изолированного распознавания слов». Обработка сигналов. т. 4, 1982, стр. 329-333.

[2] Сакоэ, Хироаки и Сейби Тиба. «Оптимизация алгоритма динамического программирования для распознавания разговорных слов». Транзакции IEEE ® для обработки акустики, речи и сигналов. т. ASSP-26, № 1, 1978, стр. 43-49.

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

Создание кода C/C + +
Создайте код C и C++ с помощью MATLAB ® Coder™

.

См. также

| | | |

Представлен в R2016a