algorithm
Dynamisches Time Warping
Suche…
Einführung in Dynamic Time Warping
Dynamic Time Warping (DTW) ist ein Algorithmus zum Messen der Ähnlichkeit zwischen zwei zeitlichen Sequenzen, deren Geschwindigkeit variieren kann. Zum Beispiel könnten Ähnlichkeiten beim Gehen mit DTW erkannt werden, selbst wenn eine Person schneller als die andere ging oder wenn im Verlauf einer Beobachtung Beschleunigungen und Verzögerungen auftraten. Es kann verwendet werden, um einen Beispiel-Sprachbefehl mit anderen Befehlen abzugleichen, selbst wenn die Person schneller oder langsamer spricht als die zuvor aufgenommene Beispielstimme. DTW kann auf zeitliche Sequenzen von Video-, Audio- und Grafikdaten angewendet werden. In der Tat können alle Daten, die in eine lineare Sequenz umgewandelt werden können, mit DTW analysiert werden.
Im Allgemeinen ist DTW eine Methode, die eine optimale Übereinstimmung zwischen zwei gegebenen Sequenzen mit bestimmten Einschränkungen berechnet. Bleiben wir aber bei den einfacheren Punkten. Nehmen wir an, wir haben zwei Sprachsequenzen, Sample und Test , und wir möchten prüfen, ob diese beiden Sequenzen übereinstimmen oder nicht. Die Sprachsequenz bezieht sich hier auf das konvertierte Digitalsignal Ihrer Stimme. Es kann die Amplitude oder Frequenz Ihrer Stimme sein, die die Wörter kennzeichnet, die Sie sagen. Angenommen:
Sample = {1, 2, 3, 5, 5, 5, 6}
Test = {1, 1, 2, 2, 3, 5}
Wir wollen die optimale Übereinstimmung zwischen diesen beiden Sequenzen herausfinden.
Zuerst definieren wir den Abstand zwischen zwei Punkten, d (x, y), wobei x und y die beiden Punkte darstellen. Lassen,
d(x, y) = |x - y| //absolute difference
Erstellen wir eine 2D- Matrixtabelle mit diesen beiden Sequenzen. Wir berechnen die Abstände zwischen jedem Punkt der Probe mit jedem Testpunkt und finden die optimale Übereinstimmung zwischen ihnen.
+------+------+------+------+------+------+------+------+
| | 0 | 1 | 1 | 2 | 2 | 3 | 5 |
+------+------+------+------+------+------+------+------+
| 0 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 1 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 2 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 3 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 6 | | | | | | | |
+------+------+------+------+------+------+------+------+
Hier stellt Tabelle [i] [j] den optimalen Abstand zwischen zwei Sequenzen dar, wenn wir die Sequenz bis zu Probe [i] und Test [j] betrachten, wobei alle zuvor beobachteten optimalen Abstände berücksichtigt werden.
Wenn wir für die erste Zeile keine Werte von Sample nehmen , ist der Abstand zwischen diesem und Test unendlich . Also setzen wir unendlich in die erste Reihe. Gleiches gilt für die erste Spalte. Wenn wir keine Werte von Test nehmen , ist der Abstand zwischen diesem und Sample ebenfalls unendlich. Und der Abstand zwischen 0 und 0 ist einfach 0 . Wir bekommen,
+------+------+------+------+------+------+------+------+
| | 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 | | | | | | |
+------+------+------+------+------+------+------+------+
Jetzt werden wir für jeden Schritt die Entfernung zwischen den betroffenen Punkten berücksichtigen und sie mit der Mindestentfernung hinzufügen, die wir bisher gefunden haben. Dies gibt uns die optimale Entfernung von zwei Sequenzen bis zu dieser Position. Unsere Formel wird sein,
Table[i][j] := d(i, j) + min(Table[i-1][j], Table[i-1][j-1], Table[i][j-1])
Für das erste ist d (1, 1) = 0 , wobei Tabelle [0] [0] das Minimum darstellt. Der Wert von Tabelle [1] [1] ist also 0 + 0 = 0 . Für die zweite ist d (1, 2) = 0 . Tabelle [1] [1] repräsentiert das Minimum. Der Wert ist: Tabelle [1] [2] = 0 + 0 = 0 . Wenn wir so weitermachen, wird der Tisch wie folgt aussehen:
+------+------+------+------+------+------+------+------+
| | 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 |
+------+------+------+------+------+------+------+------+
Der Wert in Tabelle [7] [6] repräsentiert den maximalen Abstand zwischen diesen beiden angegebenen Sequenzen. Hier stellt 1 den maximalen Abstand zwischen Probe und Test dar 1 .
Wenn wir nun vom letzten Punkt zurück zum gesamten Startpunkt (0, 0) zurückkehren, erhalten wir eine lange Linie, die sich horizontal, vertikal und diagonal bewegt. Unser Backtracking-Verfahren wird sein:
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
Wir setzen das fort, bis wir (0, 0) erreichen . Jeder Zug hat seine eigene Bedeutung:
- Eine horizontale Bewegung steht für das Löschen. Das heißt, unsere Testsequenz hat sich in diesem Intervall beschleunigt.
- Eine vertikale Bewegung steht für das Einfügen. Das bedeutet , dass aus Prüfablauf während dieses Intervalls verzögert.
- Eine diagonale Bewegung steht für Übereinstimmung. Während dieser Zeit waren Test und Probe gleich.
Unser Pseudo-Code lautet:
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]
Wir können auch eine Ortsbeschränkung hinzufügen. Das heißt, wenn Sample[i] mit Test[j] übereinstimmt, müssen |i - j| ist nicht größer als w , ein Fensterparameter.
Komplexität:
Die Komplexität der Berechnung von DTW ist O (m * n), wobei m und n die Länge jeder Sequenz darstellen. Schnellere Techniken zum Berechnen von DTW umfassen PrunedDTW, SparseDTW und FastDTW.
Anwendungen:
- Erkennung gesprochener Wörter
- Korrelationsleistungsanalyse
