Exponenta Banner
exponenta event banner

edr

Изменение расстояния по реальным сигналам

свернуть все на странице

Синтаксис

dist = edr (x, y, tol)
[dist, ix, iy] = edr (x, y, tol)
[___] = edr (x, y, maxsamp)
[___] = edr (___, метрика)
edr (___)

Описание

пример

dist = edr(x,y,tol) возвращает значение параметра «Редактировать расстояние для реальных сигналов между последовательностями». 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 для отображения исходного и выровненного сигналов.

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

Примеры

свернуть все

Открыть сценарий в реальном времени

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

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.

Открыть сценарий в реальном времени

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

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.

Открыть сценарий в реальном времени

Файлы 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);

Figure contains 6 axes. Axes 1 with title Overlaid Aligned Signals contains an object of type image. Axes 2 with title Aligned Signal (Y) contains an object of type image. Axes 3 with title Aligned Signal (X) contains an object of type image. Axes 4 with title Overlaid Original Signals contains an object of type image. Axes 5 with title Original Signal (Y) contains an object of type image. Axes 6 with title Original Signal (X) contains an object of type image.

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

свернуть все

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

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

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

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

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

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

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

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

Метрика расстояния, указанная как 'euclidean', 'absolute', 'squared', или 'symmkl'. Если X и Y оба являются K-мерными сигналами, то metric предписывает dmn (X, Y), расстояние между m-м образцом X и n-м образцом 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' - симметричная метрика Куллбэка-Лейблера. Эта метрика действительна только для вещественных и положительных 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-м образцом X и n-м образцом Y, указанным вmetric, edr функция растягивает X и Y на общий набор моментов, так что расстояние редактирования между сигналами является наименьшим.

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

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

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

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

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

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

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

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

  1. D1,1  = 0.

  2. Dm,1  = m - 1 для m = 2, ... ,  M + 1.

  3. D1,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 равно DM + 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) ≤   Матчи не увеличивают расстояние. Удаление увеличивает его на 1.

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

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

Ссылки

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

[2] Паливал, К. К., Анант Агарвал и Сарваджит С. Синха. «Модификация алгоритма динамического искажения времени Сакоэ и Тибы для изолированного распознавания слов». Обработка сигналов. т. 4, 1982, стр. 329-333.

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

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

Создание кода C/C + +
Создайте код C и C++ с помощью MATLAB ® Coder™

.

См. также

| | | |

Представлен в R2016b

Документация по инструментам обработки сигналов

Поддержка