algorithm
Dynamisk tidsförskjutning

Introduktion till dynamisk tidsförskjutning

Dynamic Time Warping (DTW) är en algoritm för att mäta likheten mellan två temporära sekvenser som kan variera i hastighet. Till exempel kunde likheter i promenader upptäckas med hjälp av DTW, även om en person gick snabbare än den andra, eller om det fanns accelerationer och retardationer under en observationsförlopp. Det kan användas för att matcha ett exempel på ett röstkommando med andra-kommando, även om personen pratar snabbare eller långsammare än den förinspelade samplingsrösten. DTW kan tillämpas på temporära sekvenser av video-, ljud- och grafikdata, och all data som kan förvandlas till en linjär sekvens kan analyseras med DTW.

Generellt sett är DTW en metod som beräknar en optimal matchning mellan två givna sekvenser med vissa begränsningar. Men låt oss hålla oss till de enklare punkterna här. Låt oss säga, vi har två röstsekvenser Exempel och test , och vi vill kontrollera om dessa två sekvenser matchar eller inte. Här avser röstsekvens den konverterade digitala signalen för din röst. Det kan vara amplituden eller frekvensen för din röst som anger orden du säger. Låt oss anta:

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

Vi vill ta reda på den optimala matchningen mellan dessa två sekvenser.

Först definierar vi avståndet mellan två punkter, d (x, y) där x och y representerar de två punkterna. Låta,

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

Låt oss skapa en 2D matris tabell med användning av dessa två sekvenser. Vi kommer att beräkna avståndet mellan varje punkt i provet med alla testpunkter och hitta den optimala matchningen mellan dem.

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

Här representerar tabell [i] [j] det optimala avståndet mellan två sekvenser om vi betraktar sekvensen upp till provet [i] och Test [j] , med tanke på alla de optimala avstånden vi observerade tidigare.

För den första raden, om vi inte tar några värden från provet , kommer avståndet mellan detta och testet att vara oändligt . Så vi satte oändlighet på den första raden. Samma sak gäller den första kolumnen. Om vi inte tar några värden från testet kommer avståndet mellan denna och provet också att vara oändligt. Och avståndet mellan 0 och 0 blir helt enkelt 0 . Vi får,

+------+------+------+------+------+------+------+------+
|      |   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 för varje steg kommer vi att överväga avståndet mellan varje berörda punkter och lägga till det med det minsta avstånd som vi hittat hittills. Detta ger oss det optimala avståndet mellan två sekvenser upp till den positionen. Vår formel kommer att vara,

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

För den första, d (1, 1) = 0 , representerar tabell [0] [0] minimum. Så värdet på tabell [1] [1] kommer att vara 0 + 0 = 0 . För den andra är d (1, 2) = 0 . Tabell [1] [1] representerar minimum. Värdet är: Tabell [1] [2] = 0 + 0 = 0 . Om vi fortsätter på detta sätt kommer bordet att se ut efter att ha slutat:

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

Värdet vid tabell [7] [6] representerar det maximala avståndet mellan dessa två givna sekvenser. Här en representerar det maximala avståndet mellan prov och Test är ett.

Nu om vi backspårar från den sista punkten, hela vägen tillbaka mot startpunkten (0, 0) , får vi en lång rad som rör sig horisontellt, vertikalt och diagonalt. Vårt backtracking-förfarande kommer att vara:

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

Vi fortsätter detta tills vi når (0, 0) . Varje drag har sin egen betydelse:

• Ett horisontellt drag representerar borttagning. Det betyder att vår testsekvens accelererade under detta intervall.
• Ett vertikalt drag representerar införande. Att organ ut Provsekvens retarderas under detta intervall.
• Ett diagonalt drag representerar matchning. Under denna period var test och prov samma.

Vår pseudokod kommer att vara:

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]

Vi kan också lägga till en lokaliseringsbegränsning. Det vill säga, vi kräver att om Sample[i] matchas med Test[j] , så |i - j| är inte större än w , en fönsterparameter.

Komplexitet:

Komplexiteten hos beräkningen DTW är O (m * n) där m och n representerar längden på varje sekvens. Snabbare tekniker för att beräkna DTW inkluderar PrunedDTW, SparseDTW och FastDTW.

Användningsområden:

• Talat ordigenkänning
• Korrelationskraftsanalys