algorithm
Dynamiczne wypaczanie czasu

Wprowadzenie do dynamicznego dopasowywania czasu

Dynamiczne dopasowanie czasu (DTW) jest algorytmem do pomiaru podobieństwa między dwiema sekwencjami czasowymi, które mogą różnić się prędkością. Na przykład podobieństwa w chodzeniu można wykryć za pomocą DTW, nawet jeśli jedna osoba chodzi szybciej niż druga, lub jeśli podczas obserwacji występują przyspieszania i zwalniania. Można go użyć do dopasowania przykładowego polecenia głosowego z poleceniem innych, nawet jeśli dana osoba mówi szybciej lub wolniej niż wcześniej nagrany przykładowy głos. DTW można zastosować do tymczasowych sekwencji danych wideo, audio i graficznych - w rzeczywistości wszelkie dane, które można przekształcić w sekwencję liniową, można analizować za pomocą DTW.

Ogólnie rzecz biorąc, DTW jest metodą, która oblicza optymalne dopasowanie dwóch podanych sekwencji z pewnymi ograniczeniami. Ale trzymajmy się prostszych punktów tutaj. Powiedzmy, że mamy dwie sekwencje głosowe Próbka i Test i chcemy sprawdzić, czy te dwie sekwencje są zgodne, czy nie. Tutaj sekwencja głosowa odnosi się do przetworzonego cyfrowego sygnału twojego głosu. Może to być amplituda lub częstotliwość twojego głosu, które oznaczają słowa, które wypowiadasz. Załóżmy:

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

Chcemy znaleźć optymalne dopasowanie między tymi dwiema sekwencjami.

Najpierw określamy odległość między dwoma punktami, d (x, y), gdzie x i y reprezentują dwa punkty. Pozwolić,

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

Stwórzmy tabelę macierzy 2D, używając tych dwóch sekwencji. Obliczymy odległości między każdym punktem próbki z każdym punktem testu i znajdziemy optymalne dopasowanie między nimi.

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

Tabela [i] [j] przedstawia tutaj optymalną odległość między dwiema sekwencjami, jeśli weźmiemy pod uwagę sekwencję aż do próbki [i] i testu [j] , biorąc pod uwagę wszystkie optymalne odległości, które zaobserwowaliśmy wcześniej.

W pierwszym rzędzie, jeśli nie bierzemy żadnych wartości z próbki , odległość między tym a testem będzie nieskończona . Więc umieszczamy nieskończoność w pierwszym rzędzie. To samo dotyczy pierwszej kolumny. Jeśli nie bierzemy żadnych wartości z testu , odległość między tym a próbką również będzie nieskończona. Odległość między 0 a 0 będzie po prostu wynosić 0 . Dostajemy

+------+------+------+------+------+------+------+------+
|      |   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 |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

Teraz dla każdego kroku rozważymy odległość między poszczególnymi punktami i dodamy ją do minimalnej odległości, jaką znaleźliśmy do tej pory. To da nam optymalną odległość dwóch sekwencji do tej pozycji. Nasza formuła będzie

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

Dla pierwszego d (1, 1) = 0 , tabela [0] [0] reprezentuje minimum. Tak więc wartość tabeli [1] [1] będzie wynosić 0 + 0 = 0 . Dla drugiego d (1, 2) = 0 . Tabela [1] [1] przedstawia minimum. Wartość będzie wynosić: Tabela [1] [2] = 0 + 0 = 0 . Jeśli będziemy kontynuować w ten sposób, po zakończeniu stół będzie wyglądał następująco:

+------+------+------+------+------+------+------+------+
|      |   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  |
+------+------+------+------+------+------+------+------+

Wartość w tabeli [7] [6] reprezentuje maksymalną odległość między tymi dwiema podanymi sekwencjami. Tutaj 1 oznacza maksymalną odległość między próbką a testem wynoszącą 1 .

Teraz, gdy cofniemy się od ostatniego punktu, aż do punktu początkowego (0, 0) , otrzymamy długą linię, która porusza się poziomo, pionowo i po przekątnej. Nasza procedura cofania będzie:

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

Będziemy kontynuować, dopóki nie osiągniemy (0, 0) . Każdy ruch ma swoje znaczenie:

• Ruch poziomy reprezentuje usunięcie. Oznacza to, że nasza sekwencja testu została przyspieszona w tym okresie.
• Ruch pionowy oznacza wstawienie. Oznacza to, że sekwencja testowa została spowolniona w tym okresie.
• Ruch po przekątnej reprezentuje dopasowanie. W tym okresie Test i Próbka były takie same.

Nasz pseudo-kod będzie:

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]

Możemy również dodać ograniczenie lokalizacji. Oznacza to, że wymagamy, aby jeśli Sample[i] była dopasowana do Test[j] , to |i - j| nie jest większy niż w , parametr okna.

Złożoność:

Złożoność obliczania DTW wynosi O (m * n), gdzie m i n reprezentują długość każdej sekwencji. Szybsze techniki obliczania DTW obejmują PrunedDTW, SparseDTW i FastDTW.

Aplikacje:

• Rozpoznawanie słów mówionych
• Analiza mocy korelacji