Dynamic-Time-Warping

Dynamic-Time-Warping

Dynamic time warp(ing) ist ein Algorithmus, um Wertefolgen unterschiedlicher Länge aufeinander abzubilden.[1]

Inhaltsverzeichnis

Anwendung

Als prominentestes Beispiel kann hier die Spracherkennung gelten: Hier sollen durch den Vergleich mit gespeicherten Sprachmustern einzelne Wörter aus einem gesprochenen Text erkannt werden. Ein Problem besteht darin, dass die Wörter oft unterschiedlich ausgesprochen werden. Vor allem Vokale werden oft länger oder kürzer gesprochen, als es im gespeicherten Sprachmuster der Fall ist: das Wort „heben“ zum Beispiel kann einmal mit kurzem „e“ und ein anderes mal wie „heeeben“ ausgesprochen werden. Für einen erfolgreichen Mustervergleich sollte das Wort also entsprechend gedehnt bzw. gestaucht werden, jedoch nicht gleichmäßig, sondern vor allem an den Vokalen, die länger bzw. kürzer gesprochen wurden. (In geringerem Maße gilt dies übrigens auch für Konsonanten, auch können bestimmte Laute komplett verschluckt werden.) Diese adaptive Zeitnormierung leistet der Algorithmus.[2][3]

Weitere Anwendungsbereiche des dynamic time warping sind z. B. Gestenerkennung in der Bildbearbeitung oder Messungen bei korreliertem Rauschen in der Physik.[4]

Algorithmus

Der Algorithmus findet z. B. bei der Spracherkennung Anwendung. Ein gesprochenes Sprachsignal soll mit einer Menge existierender Schablonen (engl. Templates) abgeglichen werden, um das gesprochene Wort wiedererkennen zu können, und beispielsweise auf einem Mobiltelefon eine entsprechende Aktion auszuführen. Sprachsignale werden dabei üblicherweise als spektrale bzw. cepstrale Wertetupel abgespeichert, ergänzt mit weiteren Stimminformationen wie Intensität usw. als Merkmalsvektoren.

Mit Hilfe einer Gewichtungsfunktion für die einzelnen Parameter jedes Wertetupels kann ein Differenzmaß zwischen zwei beliebigen Werten der beiden Signale aufgestellt werden (Kostenfunktion), beispielsweise eine normalisierte euklidische Distanz oder die Mahalanobis-Distanz.[5]

Der Algorithmus sucht nun den „kostengünstigsten“ Weg vom Anfang zum Ende beider Signale über die aufgespannte Matrix der paarweise vorliegenden Kosten aller Punkte beider Signale. Dies geschieht mit Hilfe der dynamischen Programmierung effizient. Den tatsächlichen Pfad, also das Warping, erhält man durch das sogenannte Backtracking nach dem ersten Durchlauf des Algorithmus. Für die reine Kostenbestimmung (also die Templateauswahl) reicht allerdings der einfache Durchlauf ohne Backtracking. Das Backtracking ermöglicht hierbei also eine genaue Abbildung jedes Punktes des kürzeren Signales auf einen oder mehrere Punkte des längeren Signales und stellt damit die ungefähre Zeitverzerrung dar.

Aufgrund algorithmischer Probleme bei der Extraktion von Sprachsignalparametern (Oktavfehler, Stimmaktivierungsfehler etc.) muss der optimale Pfad durch die Signaldifferenzmatrix nicht unbedingt der tatsächlichen Zeitverzerrung entsprechen.

Siehe auch

Einzelnachweise

  1. DTW oder dynamic time warping. www.inf.fu-berlin.de. Abgerufen am 8. April 2009.
  2. Wendemuth, Andreas: Grundlagen der stochastischen Sprachverarbeitung, S. 137
  3. DTW oder dynamic time warping. www.inf.fu-berlin.de. Abgerufen am 8. April 2009.
  4. Wendemuth, Andreas: Grundlagen der stochastischen Sprachverarbeitung, S. 133
  5. Black, A. W.; P. Taylor (1997a): Automatically clustering similar units for unit selection in speech synthesis. In: Proc. Eurospeech ’97.

Literatur


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Dynamic Time Warping — Dynamic time warp(ing) ist ein Algorithmus, um Wertefolgen unterschiedlicher Länge aufeinander abzubilden.[1] Inhaltsverzeichnis 1 Anwendung 2 Algorithmus 3 Siehe auch 4 Einzelnachweise 5 …   Deutsch Wikipedia

  • Dynamic time warping — Not to be confused with the Time Warp mechanism for discrete event simulation, or the Time Warp Operating System that used this mechanism. Dynamic time warping (DTW) is an algorithm for measuring similarity between two sequences which may vary in …   Wikipedia

  • Time series — Time series: random data plus trend, with best fit line and different smoothings In statistics, signal processing, econometrics and mathematical finance, a time series is a sequence of data points, measured typically at successive times spaced at …   Wikipedia

  • Dynamic programming — For the programming paradigm, see Dynamic programming language. In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems… …   Wikipedia

  • Speech recognition — For the human linguistic concept, see Speech perception. The display of the Speech Recognition screensaver on a PC, in which the character responds to questions, e.g. Where are you? or statements, e.g. Hello. Speech recognition (also known as… …   Wikipedia

  • Needleman–Wunsch algorithm — The Needleman–Wunsch algorithm performs a global alignment on two sequences (called A and B here). It is commonly used in bioinformatics to align protein or nucleotide sequences. The algorithm was published in 1970 by Saul B. Needleman and… …   Wikipedia

  • Levenshtein distance — In information theory and computer science, the Levenshtein distance is a string metric for measuring the amount of difference between two sequences. The term edit distance is often used to refer specifically to Levenshtein distance. The… …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • Edit-Distanz — Die Levenshtein Distanz (auch Edit Distanz, Editierdistanz oder Editierabstand) bezeichnet in der Informationstheorie ein Maß für den Unterschied zwischen zwei Zeichenketten bezüglich der minimalen Anzahl der Operationen Einfügen, Löschen und… …   Deutsch Wikipedia

  • Editierdistanz — Die Levenshtein Distanz (auch Edit Distanz, Editierdistanz oder Editierabstand) bezeichnet in der Informationstheorie ein Maß für den Unterschied zwischen zwei Zeichenketten bezüglich der minimalen Anzahl der Operationen Einfügen, Löschen und… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”