edr

Отредактируйте расстояние по реальным сигналам

Синтаксис

dist = edr(x,y,tol)

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

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

[___] = edr(___,metric)

edr(___)

Описание

пример

dist = edr(x,y,tol) возвращает значение параметра Edit Distance on Real Signals between sequences x и y. edr возвращает минимальное количество элементов, которые необходимо удалить из x, y, или и то, и другое x и y, так что сумма евклидовых расстояний между оставшимися сигнальными элементами находится в пределах заданного допуска, tol.

[dist,ix,iy] = edr(x,y,tol) возвращает путь деформации таким образом, чтобы x(ix) и y(iy) иметь наименьшее возможное dist между ними. Когда x и y матрицы, ix и iy таковы, что x(:,ix) и y(:,iy) минимально разделены.

пример

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

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

пример

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

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

Примеры

свернуть все

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

Открыть Live Script

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

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;

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

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

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

ans = 617

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

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

edr(x,y,tol);

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

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

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

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

Редактирование расстояния и пути

Открыть Live Script

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

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

Figure contains 2 axes. Axes 1 contains an object of type line. Axes 2 contains an object of type line.

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

tol = 0.1;

figure
edr(x1,x2,tol);

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

Расстояние между сигналами 7. Чтобы выровнять их, необходимо удалить семь центральных нулей x2 или добавить семь нулей в x1.

Вычислите матрицу D, чей нижний правый элемент соответствует расстоянию редактирования. Для определения D смотрите Edit Distance on Real Signals.

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

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

[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

Повторите расчет, но теперь ограничьте путь деформации, чтобы отклонить самое большее два элемента от диагонали. Постройте график растянутых сигналов и пути деформации. На втором графике установите матричные столбцы, чтобы проходить вдоль оси 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')

Figure contains 2 axes. Axes 1 with title Distance: 5 contains 2 objects of type line. Axes 2 with title Warping Path contains 2 objects of type line.

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

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

Figure contains 2 axes. Axes 1 with title Distance: NaN contains 2 objects of type line. Axes 2 with title Warping Path contains 2 objects of type line.

Выравнивание выборок блотченного рукописного текста

Открыть Live Script

Файлы MATLAB1.gif и MATLAB2.gif содержит две рукописные выборки слова «MATLAB ®». Загрузите файлы. Добавьте выбросы путем блоттинга данных.

samp1 = 'MATLAB1.gif';
samp2 = 'MATLAB2.gif';

x = double(imread(samp1));
y = double(imread(samp2));

x(15:20,54:60) = 4000;
y(15:20,84:96) = 4000;

Выровняйте выборки рукописного ввода по оси X с помощью расстояния редактирования. Задайте допуск 450.

edr(x,y,450);

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

свернуть все

`x` - Входной сигнал
вектор | матрица

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

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

`y` - Входной сигнал
вектор | матрица

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

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

`tol` - Допуск
положительная скалярная величина

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

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

`maxsamp` - Ширина окна регулировки
`Inf` (по умолчанию) | положительное целое число

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

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

`metric` - Метрика расстояния
`'euclidean'` (по умолчанию) | `'absolute'` | `'squared'` | `'symmkl'`

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

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

$d_{m n} (X, Y) = \sqrt{\sum_{k = 1}^{K} {(x_{k, m} - y_{k, n})}^{*} (x_{k, m} - y_{k, n})}$
'absolute' - Сумма абсолютных различий, также известная как Манхэттен, городской блок, таксикаб или ℓ 1 метрика:

$d_{m n} (X, Y) = \sum_{k = 1}^{K} | x_{k, m} - y_{k, n} | = \sum_{k = 1}^{K} \sqrt{{(x_{k, m} - y_{k, n})}^{*} (x_{k, m} - y_{k, n})}$
'squared' - Квадрат евклидовой метрики, состоящий из суммы квадратов различий:

$d_{m n} (X, Y) = \sum_{k = 1}^{K} {(x_{k, m} - y_{k, n})}^{*} (x_{k, m} - y_{k, n})$
'symmkl' - Симметричная метрика Кулбэка-Лейблера. Эта метрика действительна только для реальных и положительных X и Y:

$d_{m n} (X, Y) = \sum_{k = 1}^{K} (x_{k, m} - y_{k, n}) (\log x_{k, m} - \log y_{k, n})$

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

свернуть все

`dist` - Минимальное расстояние
положительный действительный скаляр

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

`ix,iy` - Путь деформации
векторы индексов

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

Подробнее о

свернуть все

Редактирование расстояния по реальным сигналам

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

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

$X = [\begin{matrix} x_{1, 1} & x_{1, 2} & \dots & x_{1, M} \\ x_{2, 1} & x_{2, 2} & \dots & x_{2, M} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ x_{K, 1} & x_{K, 2} & \dots & x_{K, M} \end{matrix}]$

$Y = [\begin{matrix} y_{1, 1} & y_{1, 2} & \dots & y_{1, N} \\ y_{2, 1} & y_{2, 2} & \dots & y_{2, N} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ y_{K, 1} & y_{K, 2} & \dots & y_{K, N} \end{matrix}],$

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

Заданное ε - действительное число, которое является допуском, заданным в tol, объявить, что m-я выборка X и n-я выборка Y совпадают, если _dmn (X , Y) < ε. Если две выборки, m и n, не совпадают, можно сделать так, чтобы они совпадали любым из трех способов:

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

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

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

Создайте (M + 1) -by- (N + 1) матрицу, D, такую что:

<reservedrangesplaceholder0> 1,1 = 0.
D _m, 1 = m - 1 при m = 2,. .. , M + 1.
D _1, n = n - 1 для n = 2,. .. , N + 1.
Для m n > 1,

$D_{m, n} = \min {\begin{matrix} D_{m - 1, n} + 1 \\ D_{m, n - 1} + 1 \\ D_{m - 1, n - 1} + {\begin{matrix} 0 \Leftarrow d_{m, n} (X, Y) \leq ε \\ 1 \Leftarrow d_{m, n} (X, Y) > ε \end{matrix} \end{matrix}} .$

Наименьшее расстояние редактирования между X и Y затем D _{M + 1,} N + 1.

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

Вертикальные перемещения: (m, n ) → ( m + 1, n) соответствует удалению выборки из X или добавлению выборки к Y. Каждый ход увеличивает расстояние редактирования по 1.
Горизонтальные перемещения: (m, n ) → (m, n + 1) соответствует удалению выборки из Y или добавлению выборки к X. Каждый ход увеличивает расстояние редактирования по 1.
Диагональные шаги: (m, n) , (m + 1, n + 1) соответствует матчу, если _dm,n (X, Y ) ≤ <reservedrangesplaceholder2> или соответствует удалению одной _{выборки} от каждого сигнала если dm,n (X, Y)> ε. Матчи не увеличивают дистанцию. Удаление увеличивает его на 1.

Эта структура гарантирует, что любой приемлемый путь выравнивает полные сигналы, не пропускает выборки и не повторяет функций сигнала. Кроме того, желаемый путь проходит близко к диагональной линии, проходящей между d _1,1 (X, Y) _{и dM,N} (X, Y). Это дополнительное ограничение, скорректированное maxsamp аргумент, гарантирует, что искривление сравнивает участки подобной длины.

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

Ссылки

[1] Chen, Lei, M. Tamer Özsu, and Vincent Oria. «Робастный и быстрый поиск подобия для движущихся траекторий объектов». Материалы 24-й Международной конференции ACM по управлению данными (SIGMOD "05). 2005, стр 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 (неопр.) (недоступная ссылка). Обработка сигналов. Том 4, 1982, стр. 329-333.

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

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

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

См. также

alignsignals | dtw | finddelay | findsignal | xcorr

Введенный в R2016b

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

edr

Синтаксис

Описание

Примеры

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

Редактирование расстояния и пути

Выравнивание выборок блотченного рукописного текста

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

`x` - Входной сигнал
вектор | матрица

`y` - Входной сигнал
вектор | матрица

`tol` - Допуск
положительная скалярная величина

`maxsamp` - Ширина окна регулировки
`Inf` (по умолчанию) | положительное целое число

`metric` - Метрика расстояния
`'euclidean'` (по умолчанию) | `'absolute'` | `'squared'` | `'symmkl'`

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

`dist` - Минимальное расстояние
положительный действительный скаляр

`ix,iy` - Путь деформации
векторы индексов

Подробнее о

Редактирование расстояния по реальным сигналам

Ссылки

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

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

См. также

Signal Processing Toolbox документация

Поддержка

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

edr

Синтаксис

Описание

Примеры

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

Редактирование расстояния и пути

Выравнивание выборок блотченного рукописного текста

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

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

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

tol - Допуск положительная скалярная величина

maxsamp - Ширина окна регулировки Inf (по умолчанию) | положительное целое число

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

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

dist - Минимальное расстояние положительный действительный скаляр

ix,iy - Путь деформации векторы индексов

Подробнее о

Редактирование расстояния по реальным сигналам

Ссылки

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

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

См. также

Signal Processing Toolbox документация

Поддержка

`x` - Входной сигнал
вектор | матрица

`y` - Входной сигнал
вектор | матрица

`tol` - Допуск
положительная скалярная величина

`maxsamp` - Ширина окна регулировки
`Inf` (по умолчанию) | положительное целое число

`metric` - Метрика расстояния
`'euclidean'` (по умолчанию) | `'absolute'` | `'squared'` | `'symmkl'`

`dist` - Минимальное расстояние
положительный действительный скаляр

`ix,iy` - Путь деформации
векторы индексов

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