Dynamic time warping
Il Dynamic time warping, o DTW, è un algoritmo che permette l'allineamento tra due o più sequenze, e che può portare ad una misura di distanza tra le due sequenze allineate. Tale algoritmo è particolarmente utile per trattare sequenze in cui singole componenti hanno caratteristiche che variano nel tempo, e per le quali la semplice espansione o compressione lineare delle due sequenze non porta risultati soddisfacenti. È stato utilizzato in diversi campi di applicazione, dal Riconoscimento vocale, al riconoscimento di attività motorie.
In generale, DTW è un metodo che permette di trovare una corrispondenza ottima tra due sequenze, attraverso una distorsione non lineare rispetto alla variabile indipendente (tipicamente il tempo). Alcune restrizioni per il calcolo della corrispondenza sono generalmente utilizzate: deve essere garantita la monotonicità nelle corrispondenze, ed il limite massimo di possibili corrispondenze tra elementi contigui della sequenza.
Esempio di implementazione[modifica | modifica wikitesto]
Qui viene riportata una implementazione del calcolo di una misura di distanza basata su DTW, quando le due sequenze sono stringhe di simboli discreti. d(x, y) è la distanza tra i simboli, e.g. d(x, y) = | x - y |.
int DTWDistance(int s[1..n], int t[1..m]) {
declare int DTW[0..n, 0..m]
declare int i, j, cost
for i := 1 to n
for j := 1 to m
DTW[i, j] := infinity
DTW[0, 0] := 0
for i := 1 to n
for j := 1 to m
cost:= d(s[i], t[j])
DTW[i, j] := cost + minimum(DTW[i-1, j ], // insertion
DTW[i , j-1], // deletion
DTW[i-1, j-1]) // match
return DTW[n, m]
}
Riferimenti Bibliografici[modifica | modifica wikitesto]
- Sakoe, H. and Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, IEEE Transactions on Acoustics, Speech and Signal Processing, 26(1) pp. 43– 49, 1978, ISSN 0096-3518
Altri progetti[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su Dynamic time warping
