DTW-Toolbox

Wissenschaftliche Zusammenfassung

BTU Cottbus · November 2003

Einleitung

Das Dynamic Time Warping (DTW) ist ein Verfahren, das Ende der sechziger Jahre entwickelt wurde. Es bedeutet übersetzt so viel wie dynamische Zeitverzerrung, Zeitwindung oder auch Zeitkrümmung. Das Verfahren dient der nichtlinearen und somit dynamisch zeitlichen Verzerrung von Signalen oder Mustern.

Anwendungsgebiete: Von der automatischen Spracherkennung bis zur Bild- und Videoanalyse – überall dort, wo Muster oder Signale verglichen werden müssen.

Die Grundlage bildet die Dynamische Programmierung, die um 800 von Al Chwarizmi entwickelt wurde. Richard Bellman griff diese auf und entwickelte daraus die vollständige „Dynamische Programmierung“.

Zielsetzung

Entwicklung einer Matlab-Toolbox für das DTW-Verfahren in der Sprach- und Sprechererkennung. Der Grundgedanke ist nicht die Klassifikation von Sprachsignalen, sondern die Bestimmung des Abstandes zwischen zwei Signalen als Qualitätsmerkmal in der Sprachsynthese.

Kapitel 2–5

Theoretische Grundlagen

Fensterung

Sprachsignale sind nicht stationär. Um Analysetechniken anwenden zu können, wird die Fensterung eingesetzt. Die zeitliche Dauer, in der ein Signal als näherungsweise stationär bezeichnet werden kann, liegt zwischen 5 ms und 30 ms.

f(m) = fₙ · w_{m-n}

Fensterarten

  • Rechteckfenster
  • Hammingfenster
  • Hanningfenster
  • Blackman-Fenster
  • Kaiser-Fenster
  • Gauss-Fenster

Spektrale Eigenschaften

  • Breite des Hauptbandes gering halten
  • Höhe der Seitenbänder minimieren
  • Trade-off: spektral vs. temporal

Merkmalsextraktion

Die Erzeugung von Merkmalen ist die zweite Stufe auf dem Weg zur DTW. Durch die Parametrisierung wird die Datenmenge drastisch reduziert.

Merkmal Beschreibung Anwendung
Energie Kurzzeitenergie des Signals Klassifizierung stimmhaft/stimmlos
Nulldurchgangsrate Vorzeichenwechsel im Signal Frequenzinformation
Autokorrelation Selbstähnlichkeit des Signals Periodenerkennung
Cepstrum Inverse FFT des Log-Spektrums Sprecheridentifikation
LPC-Koeffizienten Lineare Prädiktionskoeffizienten Sprachkodierung

Abstandsmaße

  • City Block Abstand – Summe der absoluten Differenzen
  • Euklidischer Abstand – Geometrischer Abstand im Raum
  • Minkowski Abstand – Verallgemeinerung mit Parameter p
  • Mahalanobis Abstand – Berücksichtigt statistische Korrelationen
  • Cosine Abstand – Winkel zwischen Vektoren

Kapitel 6

Der DTW-Algorithmus

DTW Schema
Abb. 1: Schematische Darstellung des DTW-Verfahrens

Grundprinzip

Zwei unterschiedlich lange Signale können auf zwei Arten zeitlich angepasst werden:

Lineare Zeitanpassung

  • Signal wird gleichmäßig gestreckt/gestaucht
  • Unabhängig vom Inhalt
  • Problem: Sprecher variiert Geschwindigkeit

Dynamische Zeitanpassung

  • Nichtlineare Anpassung
  • Bereiche individuell behandelt
  • Bessere Ergebnisse bei Sprache

Dynamische Programmierung

Das Kernstück des DTW ist die dynamische Programmierung (DP). Das Prinzip besteht darin, eine Reihe von Entscheidungen zu treffen, wobei jede Entscheidung den aktuellen Zustand in einen neuen überführt.

Optimalitätsprinzip: „In einer Folge optimaler Entscheidungen ist jede Teilfolge selbst eine optimale Folge von Entscheidungen.“

D_{i,j} = d(x_i, y_j) + min{D_{i-v,j-u}}
DTW Warpingpfad
Abb. 2: Optimaler Warpingpfad durch die Distanzmatrix

Restriktionen

Monotonie-Bedingung

Der Pfad darf sich nicht in der Zeit zurückbewegen: i(l-1) ≤ i(l) und j(l-1) ≤ j(l)

Kontinuitäts-Bedingung

Keine Stützstellen dürfen ausgelassen werden: |i(l) – i(l-1)| ≤ 1

Anfangs-/Endbedingungen

Der Pfad beginnt bei W(1)=(1,1) und endet bei W(L)=(I,J)

Globale Beschränkungen

Sakoe/Chiba-Band oder Itakura-Band zur Einschränkung des Suchraums

Kapitel 7

Die DTW-Toolbox

Die DTW-Toolbox ist eine umfangreiche Matlab-Implementierung des DTW-Verfahrens mit grafischer Benutzeroberfläche.

Vorverarbeitung

  • Laden von WAV-Dateien
  • 16 verschiedene Fensterarten
  • Statische & dynamische Segmentierung
  • Merkmalsextraktion

DTW-Analyse

  • 8 Formen der Anpassungsfunktion
  • 9 Abstandsmaße
  • Lokale & globale Restriktionen
  • Strahlsuche (Beam Search)
Modul Funktionen
Signalverarbeitung Fensterung, Merkmalsberechnung, Segmentierung
Distanzberechnung 9 verschiedene Abstandsmaße inkl. Mahalanobis
DTW-Kern Dynamische Programmierung, Pfadrückverfolgung
Visualisierung Distanzmatrix, Viterbi-Matrix, Warpingpfad
Export Zeitnormalisierte WAV-Dateien, Protokolle

Kapitel 9

Ergebnisse und Ausblick

DTW Ergebnisse
Abb. 3: Beispiel einer erfolgreichen Zeitnormalisierung

Zusammenfassung

Die DTW-Toolbox stellt eine umfangreiche Realisierung des DTW-Verfahrens dar. Neben der Spezialisierung auf Sprachsignale kann sie auch für andere Signalarten verwendet werden.

Hauptergebnisse: Erfolgreiche nichtlineare Zeitanpassung, quantifizierbarer Abstand als Qualitätsmaß, flexible Parametrisierung, schrittweise Visualisierung.

Mögliche Erweiterungen

  • Overlap-Einstellung bei Fensterung
  • Weitere Merkmale (MFCC, PARCOR)
  • Mehrdimensionale DTW
  • Stapelverarbeitung

Vor- und Nachteile

  • + Einfach zu verstehen
  • + Optimales Ergebnis garantiert
  • − Quadratische Komplexität O(n²)
  • − Hoher Speicherbedarf