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) возвращает Расстояние Редактирования на Действительных Сигналах между последовательностями x и y. edr возвращает минимальное число элементов, которое должно быть удалено из xY, или оба 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(___) без выходных аргументов строит исходные и выровненные сигналы.

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

Примеры

свернуть все

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

Скрипт Open 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.

Отредактируйте расстояние и деформирующийся путь

Скрипт Open 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 смотрите Расстояние Редактирования на Действительных Сигналах.

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.

Выровняйте покрытые пятнами выборки почерка

Скрипт Open 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 th выборка X и n th выборка Y.

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

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

$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' — Симметричная метрика Kullback-Leibler. Эта метрика допустима только для действительных и положительных 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 th выборка X и n th выборка Y задано в metric, edr функционируйте расширяет X и Y на единый набор моментов, таким образом, что расстояние редактирования между сигналами является наименьшим.

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

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

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

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

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

D _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) ≤ ε или соответствует удалению одной выборки от каждого сигнала если _dm,n (X, Y) > ε. Соответствия не увеличивают расстояние. Удаления увеличивают его на 1.

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

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

Ссылки

[1] Чен, Леи, М. Тэмер Езсу и Винсент Ория. "Устойчивый и Быстрый Поиск Подобия Движущихся Объектных Траекторий". Продолжения 24-й Международной конференции ACM по вопросам управления Данными (SIGMOD ‘05). 2005, стр 491–502.

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

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

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

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

Введенный в R2017b

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

edr

Синтаксис

Описание

Примеры

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

Отредактируйте расстояние и деформирующийся путь

Выровняйте покрытые пятнами выборки почерка

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

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

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

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

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

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

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

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

`ix,iy` — Деформирование пути
векторы из индексов

Больше о

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

Ссылки

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

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

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

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

Поддержка

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

edr

Синтаксис

Описание

Примеры

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

Отредактируйте расстояние и деформирующийся путь

Выровняйте покрытые пятнами выборки почерка

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

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

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

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

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

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

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

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

ix,iy — Деформирование пути векторы из индексов

Больше о

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

Ссылки

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

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

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

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

Поддержка

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

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

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

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

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

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

`ix,iy` — Деформирование пути
векторы из индексов

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