Exponenta Banner

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)

ans = 617

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

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

edr(x,y,tol);

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

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

Скрипт 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])

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

tol = 0.1;

figure
edr(x1,x2,tol);

Расстояние между сигналами равняется 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')

Ограничение приводит к меньшему расстоянию редактирования, но искажает сигналы. Если ограничению нельзя соответствовать, то 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')

Скрипт 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);

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

свернуть все

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

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

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

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

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

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

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

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

Метрика расстояния в виде 'euclidean', 'absolute', 'squared', или 'symmkl'. Если X и Y является оба K - размерные сигналы, то metric предписывает dmn (X, Y), расстояние между m th выборка X и n th выборка 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' — Симметричная метрика Kullback-Leibler. Эта метрика допустима только для действительных и положительных X и Y:

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

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

свернуть все

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

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

Больше о

свернуть все

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

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

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

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

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

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

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

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

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

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

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

  1. D 1,1 = 0.

  2. D m, 1 = m – 1 для m = 2, …, M + 1.

  3. D 1, n = n – 1 для n = 2, …, N + 1.

  4. Для m, n > 1,

    Dm,n=min{Dm−1,n+1Dm,n−1+1Dm−1,n−1+{0⇐dm,n(X,Y)≤ε1⇐dm,n(X,Y)>ε}.

Наименьшим расстоянием редактирования между 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.

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

| | | |

Введенный в R2017b

Документация Signal Processing Toolbox
Поддержка