Deformare dinamică a timpului

Dynamic Time Warping , sau DTW, este un algoritm care permite alinierea între două secvențe și care poate duce la o măsurare a distanței între cele două secvențe aliniate. Acest algoritm este deosebit de util pentru tratarea secvențelor în care componentele individuale au caracteristici care variază în timp și pentru care expansiunea sau compresia liniară simplă a celor două secvențe nu aduce rezultate satisfăcătoare. A fost utilizat în diverse domenii de aplicare, de la recunoașterea vorbirii , până la recunoașterea activităților motorii.

În general, DTW este o metodă care permite găsirea unei corespondențe optime între două secvențe, printr-o distorsiune neliniară în raport cu variabila independentă (de obicei timpul). Unele restricții pentru calcularea corespondenței sunt utilizate în general: monotonitatea în corespondențe trebuie garantată, iar limita maximă a corespondențelor posibile între elementele adiacente ale secvenței.

Exemplu de implementare

Iată o implementare a calculului unei măsurători de distanță bazată pe DTW, când cele două secvențe sunt șiruri de simboluri discrete. d(x, y) este distanța dintre simboluri, de ex. d(x, y) = | x - y |.

 int DTWDistance (int s [1..n], int t [1..m]) {
    declarați int DTW [0..n, 0..m]
    declara int i, j, cost

    pentru i: = 1 până la n
     pentru j: = 1 până la m
       DTW [i, j]: = infinit
    
    DTW [0, 0]: = 0
 

    pentru i: = 1 până la n
        pentru j: = 1 până la m
            cost: = d (s [i], t [j])
            DTW [i, j]: = cost + minim (DTW [i-1, j], // inserție
                                        DTW [i, j-1], // ștergere
                                        DTW [i-1, j-1]) // se potrivesc

    returnează DTW [n, m]
}

Referințe bibliografice

• Sakoe, H. și Chiba, S., Optimizarea algoritmului de programare dinamică pentru recunoașterea cuvintelor vorbite , IEEE Transactions on Acoustics, Speech and Signal Processing, 26 (1) pp. 43-49, 1978, ISSN 0096-3518

Alte proiecte

• Wikimedia Commons conține imagini sau alte fișiere despre deformarea dinamică a timpului