algorithm
Ускорение динамического времени

Введение в динамическое деформирование времени

Dynamic Time Warping (DTW) - это алгоритм для измерения сходства между двумя временными последовательностями, которые могут варьироваться в зависимости от скорости. Например, сходство в ходьбе можно обнаружить с помощью DTW, даже если один человек идет быстрее, чем другой, или если в ходе наблюдения наблюдались ускорения и замедление. Его можно использовать для сопоставления с образцовой голосовой командой с другими командами, даже если человек говорит быстрее или медленнее, чем предварительно записанный образец голоса. DTW может применяться к временным последовательностям видео-, аудио- и графических данных - действительно, любые данные, которые могут быть преобразованы в линейную последовательность, могут быть проанализированы с помощью DTW.

В общем, DTW - это метод, который вычисляет оптимальное совпадение между двумя заданными последовательностями с определенными ограничениями. Но давайте придерживаться более простых моментов здесь. Предположим, у нас есть две голосовые последовательности Sample и Test , и мы хотим проверить, соответствуют ли эти две последовательности или нет. Здесь голосовая последовательность относится к преобразованному цифровому сигналу вашего голоса. Это может быть амплитуда или частота вашего голоса, который обозначает слова, которые вы говорите. Предположим:

Sample = {1, 2, 3, 5, 5, 5, 6}
Test   = {1, 1, 2, 2, 3, 5}

Мы хотим найти оптимальное совпадение между этими двумя последовательностями.

Сначала мы определяем расстояние между двумя точками, d (x, y), где x и y представляют две точки. Позволять,

d(x, y) = |x - y|     //absolute difference

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

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   1  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   2  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   3  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   6  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

Здесь таблица [i] [j] представляет оптимальное расстояние между двумя последовательностями, если мы рассмотрим последовательность до Sample [i] и Test [j] , учитывая все оптимальные расстояния, которые мы наблюдали ранее.

Для первой строки, если мы не принимаем значения из Sample , расстояние между этим и Test будет бесконечным . Поэтому мы помещаем бесконечность в первую строку. То же самое касается первого столбца. Если мы не будем принимать значения из теста , расстояние между этим и Sample также будет бесконечным. И расстояние между 0 и 0 будет просто 0 . Мы получаем,

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |   0  |  inf |  inf |  inf |  inf |  inf |  inf |
+------+------+------+------+------+------+------+------+
|   1  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   2  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   3  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   6  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

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

Table[i][j] := d(i, j) + min(Table[i-1][j], Table[i-1][j-1], Table[i][j-1])

Для первого, d (1, 1) = 0 , таблица [0] [0] представляет собой минимум. Таким образом, значение таблицы [1] [1] будет равно 0 + 0 = 0 . Для второго d (1, 2) = 0 . Таблица [1] [1] представляет собой минимум. Значение будет: Таблица [1] [2] = 0 + 0 = 0 . Если мы продолжим этот путь, после окончания таблицы таблица будет выглядеть так:

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |   0  |  inf |  inf |  inf |  inf |  inf |  inf |
+------+------+------+------+------+------+------+------+
|   1  |  inf |   0  |   0  |   1  |   2  |   4  |   8  |
+------+------+------+------+------+------+------+------+
|   2  |  inf |   1  |   1  |   0  |   0  |   1  |   4  |
+------+------+------+------+------+------+------+------+
|   3  |  inf |   3  |   3  |   1  |   1  |   0  |   2  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |   7  |   7  |   4  |   4  |   2  |   0  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |  11  |  11  |   7  |   7  |   4  |   0  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |  15  |  15  |  10  |  10  |   6  |   0  |
+------+------+------+------+------+------+------+------+
|   6  |  inf |  20  |  20  |  14  |  14  |   9  |   1  |
+------+------+------+------+------+------+------+------+

Значение в таблице [7] [6] представляет собой максимальное расстояние между этими двумя заданными последовательностями. Здесь 1 представляет максимальное расстояние между образцом и тестом 1 .

Теперь, если мы отступим от последней точки, все пути назад к стартовой точке (0, 0) , мы получим длинную линию, которая перемещается горизонтально, вертикально и по диагонали. Наша процедура обратного отслеживания будет:

if Table[i-1][j-1] <= Table[i-1][j] and Table[i-1][j-1] <= Table[i][j-1]
    i := i - 1
    j := j - 1
else if Table[i-1][j] <= Table[i-1][j-1] and Table[i-1][j] <= Table[i][j-1]
    i := i - 1
else
    j := j - 1
end if

Мы продолжим это, пока не достигнем (0, 0) . Каждый ход имеет свое значение:

• Горизонтальное перемещение представляет собой удаление. Это означает, что наша тестовая последовательность ускорилась в течение этого интервала.
• Вертикальный ход представляет собой вставку. Это означает, что тестовая последовательность замедляется в течение этого интервала.
• Диагональный ход представляет собой совпадение. В течение этого периода тест и образец были такими же.

Наш псевдокод будет:

Procedure DTW(Sample, Test):
n := Sample.length
m := Test.length
Create Table[n + 1][m + 1]
for i from 1 to n
    Table[i][0] := infinity
end for
for i from 1 to m
    Table[0][i] := infinity
end for
Table[0][0] := 0
for i from 1 to n
    for j from 1 to m
        Table[i][j] := d(Sample[i], Test[j])
                       + minimum(Table[i-1][j-1],      //match
                                 Table[i][j-1],        //insertion
                                 Table[i-1][j])        //deletion
    end for
end for
Return Table[n + 1][m + 1]

Мы также можем добавить ограничение локальности. То есть, мы требуем, чтобы если Sample[i] соответствовал Test[j] , то |i - j| не больше w , параметр окна.

Сложность:

Сложность вычисления DTW равна O (m * n), где m и n представляют длину каждой последовательности. Более быстрые методы для вычисления DTW включают PrunedDTW, SparseDTW и FastDTW.

Приложения:

• Распознавание слов
• Анализ корреляции мощности