algorithm
Déformation temporelle dynamique
Recherche…
Introduction à la déformation temporelle dynamique
Dynamic Time Warping (DTW) est un algorithme permettant de mesurer la similarité entre deux séquences temporelles dont la vitesse peut varier. Par exemple, les similitudes dans la marche pourraient être détectées à l'aide de DTW, même si une personne marchait plus vite que l'autre ou s'il y avait des accélérations et des décélérations au cours d'une observation. Il peut être utilisé pour associer un exemple de commande vocale à d'autres commandes, même si la personne parle plus rapidement ou plus lentement que la voix échantillon préenregistrée. DTW peut être appliqué à des séquences temporelles de données vidéo, audio et graphiques. En effet, toutes les données pouvant être transformées en une séquence linéaire peuvent être analysées avec DTW.
En général, DTW est une méthode qui calcule une correspondance optimale entre deux séquences données avec certaines restrictions. Mais restons aux points les plus simples ici. Disons que nous avons deux séquences vocales, Sample et Test , et nous voulons vérifier si ces deux séquences correspondent ou non. Ici, la séquence vocale fait référence au signal numérique converti de votre voix. Ce pourrait être l'amplitude ou la fréquence de votre voix qui dénote les mots que vous dites. Assumons:
Sample = {1, 2, 3, 5, 5, 5, 6}
Test = {1, 1, 2, 2, 3, 5}
Nous voulons trouver la correspondance optimale entre ces deux séquences.
Au début, nous définissons la distance entre deux points, d (x, y) où x et y représentent les deux points. Laisser,
d(x, y) = |x - y| //absolute difference
Créons un tableau de matrice 2D en utilisant ces deux séquences. Nous allons calculer les distances entre chaque point de l' échantillon avec chaque point de test et trouver la correspondance optimale entre eux.
+------+------+------+------+------+------+------+------+
| | 0 | 1 | 1 | 2 | 2 | 3 | 5 |
+------+------+------+------+------+------+------+------+
| 0 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 1 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 2 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 3 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 6 | | | | | | | |
+------+------+------+------+------+------+------+------+
Ici, le tableau [i] [j] représente la distance optimale entre deux séquences si l'on considère la séquence jusqu'à Sample [i] et Test [j] , en tenant compte de toutes les distances optimales observées auparavant.
Pour la première ligne, si nous ne prenons aucune valeur de Sample , la distance entre cette valeur et Test sera infinie . Nous avons donc mis l' infini sur la première ligne. Même chose pour la première colonne. Si nous ne prenons aucune valeur de Test , la distance entre celui-ci et Sample sera également infinie. Et la distance entre 0 et 0 sera simplement 0 . On a,
+------+------+------+------+------+------+------+------+
| | 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 | | | | | | |
+------+------+------+------+------+------+------+------+
Maintenant, pour chaque étape, nous allons considérer la distance entre chaque point concerné et l'ajouter à la distance minimale que nous avons trouvée jusqu'à présent. Cela nous donnera la distance optimale de deux séquences jusqu'à cette position. Notre formule sera,
Table[i][j] := d(i, j) + min(Table[i-1][j], Table[i-1][j-1], Table[i][j-1])
Pour le premier, d (1, 1) = 0 , le tableau [0] [0] représente le minimum. La valeur de la table [1] [1] sera donc 0 + 0 = 0 . Pour le second, d (1, 2) = 0 . Le tableau [1] [1] représente le minimum. La valeur sera: Table [1] [2] = 0 + 0 = 0 . Si nous continuons de cette façon, après avoir fini, la table ressemblera à:
+------+------+------+------+------+------+------+------+
| | 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 |
+------+------+------+------+------+------+------+------+
La valeur du tableau [7] [6] représente la distance maximale entre ces deux séquences données. Ici 1 représente la distance maximale entre l' échantillon et le test est 1 .
Maintenant, si nous faisons un retour en arrière du dernier point, jusqu'au retour (0, 0) , nous obtenons une longue ligne qui se déplace horizontalement, verticalement et en diagonale. Notre procédure de retour en arrière sera:
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
Nous continuerons jusqu'à ce que nous atteignions (0, 0) . Chaque mouvement a sa propre signification:
- Un mouvement horizontal représente la suppression. Cela signifie que notre séquence de test s'est accélérée pendant cet intervalle.
- Un déplacement vertical représente une insertion. Cela signifie que la séquence de test est décélérée pendant cet intervalle.
- Un mouvement en diagonale représente une correspondance. Pendant cette période, Test et Sample étaient les mêmes.
Notre pseudo-code sera:
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]
Nous pouvons également ajouter une contrainte de localité. Autrement dit, nous exigeons que si Sample[i] correspond à Test[j] , alors |i - j| n'est pas plus grand que w , un paramètre de fenêtre.
Complexité:
La complexité du calcul de DTW est O (m * n) où m et n représentent la longueur de chaque séquence. Les techniques plus rapides de calcul de DTW incluent PrunedDTW, SparseDTW et FastDTW.
Applications:
- Reconnaissance de mots parlés
- Analyse de puissance de corrélation