algorithm
Dynamische Time Warping

Inleiding tot dynamische time warping

Dynamic Time Warping (DTW) is een algoritme voor het meten van de overeenkomst tussen twee temporele sequenties die in snelheid kunnen variëren. Gelijkenissen in lopen konden bijvoorbeeld worden gedetecteerd met behulp van DTW, zelfs als de ene persoon sneller liep dan de andere, of als er versnellingen en vertragingen waren tijdens een observatie. Het kan worden gebruikt om een voorbeeld van een spraakopdracht te matchen met een opdracht van anderen, zelfs als de persoon sneller of langzamer spreekt dan de vooraf opgenomen voorbeeldstem. DTW kan worden toegepast op tijdelijke sequenties van video-, audio- en grafische gegevens - inderdaad, alle gegevens die in een lineaire reeks kunnen worden omgezet, kunnen met DTW worden geanalyseerd.

Over het algemeen is DTW een methode die een optimale overeenkomst tussen twee gegeven sequenties met bepaalde beperkingen berekent. Maar laten we ons bij de eenvoudigere punten hier houden. Laten we zeggen dat we twee stemsequenties Sample en Test hebben en we willen controleren of deze twee sequenties overeenkomen of niet. Hier verwijst spraakvolgorde naar het geconverteerde digitale signaal van uw stem. Het kan de amplitude of frequentie van je stem zijn die de woorden aangeeft die je zegt. Laten we aannemen:

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

We willen de optimale match tussen deze twee sequenties ontdekken.

Eerst definiëren we de afstand tussen twee punten, d (x, y) waarbij x en y de twee punten vertegenwoordigen. Laat,

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

Laten we een 2D-matrix Tabel gebruik van deze twee sequenties. We berekenen de afstanden tussen elk punt van Sample met elk testpunt en vinden de optimale match daartussen.

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

Hier vertegenwoordigt tabel [i] [j] de optimale afstand tussen twee reeksen als we de reeks tot monster [i] en test [j] beschouwen, rekening houdend met alle optimale afstanden die we eerder hebben waargenomen.

Als we voor de eerste rij geen waarden uit Sample nemen , is de afstand tussen deze en Test oneindig . Dus zetten we oneindigheid op de eerste rij. Hetzelfde geldt voor de eerste kolom. Als we geen waarden uit Test nemen , is de afstand tussen deze en Sample ook oneindig. En de afstand tussen 0 en 0 is gewoon 0 . We krijgen,

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

Nu beschouwen we voor elke stap de afstand tussen de betreffende punten en voegen we deze toe met de minimale afstand die we tot nu toe hebben gevonden. Dit geeft ons de optimale afstand van twee reeksen tot die positie. Onze formule zal zijn,

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

Voor de eerste, d (1, 1) = 0 , vertegenwoordigt tabel [0] [0] het minimum. De waarde van tabel [1] [1] is dus 0 + 0 = 0 . Voor de tweede, d (1, 2) = 0 . Tabel [1] [1] vertegenwoordigt het minimum. De waarde zal zijn: Tabel [1] [2] = 0 + 0 = 0 . Als we op deze manier doorgaan, ziet de tabel er na afloop uit als:

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

De waarde in tabel [7] [6] vertegenwoordigt de maximale afstand tussen deze twee gegeven reeksen. Hier is 1 de maximale afstand tussen monster en test is 1 .

Als we nu teruggaan vanaf het laatste punt, helemaal terug naar het startpunt (0, 0) , krijgen we een lange lijn die horizontaal, verticaal en diagonaal beweegt. Onze backtracking-procedure is:

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

We zullen hiermee doorgaan tot we (0, 0) bereiken . Elke beweging heeft zijn eigen betekenis:

• Een horizontale beweging staat voor verwijdering. Dat betekent dat onze testreeks tijdens dit interval is versneld.
• Een verticale beweging staat voor invoeging. Dat betekent dat de testreeks tijdens dit interval is vertraagd.
• Een diagonale beweging staat voor wedstrijd. Gedurende deze periode waren test en monster hetzelfde.

Onze pseudo-code zal zijn:

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]

We kunnen ook een plaatsbeperking toevoegen. Dat wil zeggen dat we vereisen dat als Sample[i] overeenkomt met Test[j] , dan |i - j| is niet groter dan w , een vensterparameter.

complexiteit:

De complexiteit van het berekenen van DTW is O (m * n) waarbij m en n de lengte van elke reeks voorstellen. Snellere technieken voor het berekenen van DTW omvatten PrunedDTW, SparseDTW en FastDTW.

toepassingen:

• Gesproken woordherkenning
• Correlatie Power Analysis