Dynamic Time Warping

Beschreibung

Gegeben sind zwei Sprachaufnahmen. Gesucht ist ein Verfahren, um die Ähnlichkeit der Aufnahmen berechnen zu können, und zwar möglichst unabhängig von Variationen im Sprechtempo. Der DTW-Algorithmus bietet eine Möglichkeit, eine zu testende Aufnahme zeitlich an die Referenzaufnahme anzupassen und ein Maß für die Ähnlichkeit zu bestimmen.

Bei den Aufnahmen "Temporalanpassung" und "Temporaaaaaalanpassung" ginge es also darum, die Vektoren, die zum kurzen "a" der ersten Aufnahme gehören, den Vektoren zum langen "aaaa" aus der zweiten Aufnahme zuzuordnen.

Es wird angenommen, dass die Aufnahmen bereits zu Merkmalsvektoren aufgearbeitet sind.

Gegeben

• %$ I $% Merkmalsvektoren %$ \vec x_i $% des zu testenden Signals und %$ J $% Vektoren %$ \vec y_j $% des Referenzsignals.
• Ein Verfahren zur Berechnung des Abstands zweier Vektoren %$ \vec x_i $% und %$ \vec y_j $%

Gesucht

• Eine nichtlineare Abbildung %$ j = wr(i) $%, die jedem %$ i $% ein oder mehrere %$ j $% zuordnet (oder umgekehrt). Diese Abbildung kann man sich als Pfad durch die Zuordnungsmatrix vorstellen:

(Annahme: Abszisse=x-Vektoren, Ordinate=y-Vektoren) In dieser Abbildung werden die ersten beiden Merkmalsvektoren mit gleichem Index einander zugeordnet: %$ \vec x_1=\vec y_1, \vec x_2=\vec y_2$%. Den x-Vektoren 3 und 4 wird jeweils der y-Vektor 3 zugeordnet, danach wird dem x-Vektor 5 der y-Vektor 4 zugeordnet usw.

Die Abbildung muss folgenden Bedingungen genügen:

• Der Pfad startet mit der linken unteren Ecke und endet in der rechten oberen Ecke
• Der Pfad muss monoton steigen und darf keinen Zeitschritt rückwärts gehen
• Es dürfen keine Sprünge auftreten

Vorgehen

Jeder Pfad steht für eine Zuordnung der Testaufnahme zur Referenzaufnahme. Die Kosten für einen Pfad berechnen sich so:

• Jeder Schritt kostet einen festen Betrag (links, rechts, diagonal)
• Wird durch eine Zuordnung ein Vektor durch einen anderen ersetzt, sind die Kosten gleich dem Abstand der Vektoren

Der optimale Pfad wird ermittelt, indem für jeden Teilpfad die Kosten berechnet werden und anschließend von der rechten oberen Ecke aus rückwärts der jeweils günstigste Weg gewählt wird.

Geht es darum, zu entscheiden, wie ähnlich zwei Aufnahmen desselben Wortes sind, ist die Arbeit hier getan. Geht es darum, zu entscheiden, welches Wort das wahrscheinlichste ist, würde man die bisherige Arbeit auf alle Referenzwörter anwenden und dann bestimmen, an welches Referenzwort sich das Testwort mit besten anpassen lässt (also mit minimalen Kosten).

Siehe auch

• Verfahren zur Spracherkennung: DTW
• Dynamic Time Warp (Ausarbeitung zu einem Seminar)

-- AlexGrupe -- 02 Apr 2004