Документация Engee

edr

Расстояние редактирования вещественных сигналов.

Библиотека

EngeeDSP

Синтаксис

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

  • dist = edr(x, y, tol) — возвращает Расстояние редактирования вещественных сигналов между последовательностями x и y. Функция edr возвращает минимальное количество элементов, которые необходимо удалить из x, y или из обеих последовательностей x и y, чтобы сумма евклидовых расстояний между оставшимися элементами сигнала находилась в пределах указанного допуска tol.

  • dist, ix, iy = edr(x, y, tol) — возвращает также путь преобразования, при котором x(ix) и y(iy) имеют минимально возможное расстояние между собой. Если x и y — матрицы, то ix и iy таковы, что x(:,ix) и y(:,iy) минимально разделены.

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

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

Аргументы

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

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

Details

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

Типы данных

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

Да

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

Details

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

Типы данных

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

Да

# tol — допуск
скаляр

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, iy — путь преобразования
размерность

Details

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

Примеры

Расстояние редактирования между косинусом с изменяющейся частотой и синусоидой с учетом выбросов

Details

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

import EngeeDSP.Functions: edr


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

tol = 0.1

p1 = plot(1:length(x), x, linewidth=2, color=:blue)
plot!(1:length(y), y, linewidth=2, color=:red, linestyle=:dash, legend=false)
title!("Original signals")

edr 1

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

d,x1,y1 = edr(x, y, tol)

x_aligned = x[x1]
y_aligned = y[y1]


p2 = plot(1:length(x_aligned), x_aligned, linewidth=2, color=:blue)
plot!(1:length(y_aligned), y_aligned, linewidth=2, color=:red, linestyle=:dash, legend=false)
title!("Aligned signals")

edr 2

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

Расстояние редактирования вещественных сигналов

Details

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

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

и

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

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

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

  2. Удлинить первый сигнал, добавив в позицию отсчет, соответствующий , и сместив остальные отсчеты на одну позицию. Это добавление эквивалентно удалению не совпавшего из второго сигнала.

  3. Заменить на в первом сигнале или, что эквивалентно, удалить и , и .

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

  1. Два пустых сигнала имеют нулевое расстояние между собой.

  2. Расстояние между пустым сигналом и сигналом с отсчетами равно , поскольку именно столько отсчетов необходимо добавить к пустому сигналу, чтобы восстановить другой. Аналогично, — это количество отсчетов, которое необходимо удалить из сигнала с отсчетами, чтобы сделать его пустым.

Создадим матрицу размером на таким образом, чтобы

  1. ;

  2. для ;

  3. для ;

  4. Для

Наименьшее расстояние редактирования между и в этом случае равно .

Путь преобразования через , приводящий к этому наименьшему расстоянию преобразования, параметризуется двумя последовательностями одинаковой длины, ix и iy, и представляет собой комбинацию ходов «шахматного короля»:

  • Вертикальные ходы: соответствуют удалению отсчета из или добавлению отсчета к . Каждый ход увеличивает расстояние редактирования на 1;

  • Горизонтальные ходы: соответствуют удалению отсчета из или добавлению отсчета к . Каждый ход увеличивает расстояние редактирования на 1;

  • Диагональные ходы: соответствуют совпадению, если , или удалению одного отсчета из каждого сигнала, если . Совпадения не увеличивают расстояние. Удаления увеличивают его на 1.

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

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

Литература

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

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