dtw

Расстояние между сигналами с использованием динамического искажения времени.

Библиотека

EngeeDSP

Синтаксис

Вызов функции

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

___ = dtw(x, y, maxsamp) — ограничивает путь искажения в пределах maxsamp отсчетов линейной аппроксимации между x и y.

___ = dtw(___, metric) — использует метрику расстояния в дополнение к любым входным аргументам в предыдущих синтаксисах. Метрика metric может принимать значения "euclidean", "absolute", "squared" или "symmkl".

___ = dtw(___, out=:plot) — строит графики исходных и выровненных сигналов.

Аргументы

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

# x — входной сигнал
вектор | матрица

Details

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

Типы данных	`Float32`, `Float64`
Поддержка комплексных чисел	Да

# y — входной сигнал
вектор | матрица

Details

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

Типы данных	`Float32`, `Float64`
Поддержка комплексных чисел	Да

# maxsamp — ширина окна настройки
Inf (по умолчанию) | положительный целочисленный скаляр

Details

Ширина окна настройки, заданная как положительный целочисленный скаляр.

Типы данных

Float32, Float64

# metric — метрика расстояния
"euclidean" (по умолчанию) | "absolute" | "squared" | "symmkl"

Details

Метрика расстояния, заданная как одно из значений: "euclidean", "absolute", "squared" или "symmkl". Если и являются -мерными сигналами, то метрика задает — расстояние между -м отсчетом и -м отсчетом . Подробнее о см. в разделе Динамическое преобразование времени.

"euclidean" — корень из суммы квадратов разностей, также известный как евклидова метрика или :
"absolute" — сумма абсолютных разностей, также известная как расстояние городских кварталов, метрика Манхэттена, метрика такси или :
"squared" — квадрат евклидовой метрики, состоящий из суммы квадратов разностей:
"symmkl" — симметричная метрика Кульбака—Лейблера. Эта метрика верна только для вещественных и положительных и :

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

# dist — минимальное расстояние между сигналами
положительный вещественный скаляр

Details

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

# ix — путь искажения первого сигнала
вектор индексов | матрица индексов

Details

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

# iy — путь искажения второго сигнала
вектор индексов | матрица индексов

Details

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

Примеры

Динамическое преобразование времени сигнала синусоиды с линейно изменяющейся частотой и синусоиды

Details

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

import EngeeDSP.Functions: dtw

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

dtw(x,y, out=:plot)

dtw 6

Изменим частоту синусоиды в два раза и повторим вычисления.

import EngeeDSP.Functions: dtw

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

dtw(x,y, out=:plot)

dtw 7

Дополнительно

Динамическое преобразование времени

Details

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

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

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

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

dtw 1

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

минимально.

Допустимые пути dist начинаются в , заканчиваются в и представляют собой комбинации ходов «шахматного короля»:

ход по вертикали: ;
ход по горизонтали: ;
ход по диагонали: .

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

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

dtw 2

Следующие пути не допускаются:

Не выравнивает все сигналы:
Пропускает отсчеты:
Поворачивает назад, повторяя элемент:

Литература

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