Was ist der DTW-Algorithmus?

dtw-Algorithmus bezieht sich auf den dynamischen Zeitverzerrungsalgorithmus, der auf der Idee der dynamischen Programmierung DP basiert. Es handelt sich um einen dynamischen Programmieralgorithmus, der die Ähnlichkeit zweier Zeitreihen berechnet, insbesondere Sequenzen unterschiedlicher Länge von Vorlagen mit unterschiedlichen Aussprachelängen. Das Matching-Problem ist ein früherer und klassischerer Algorithmus in der Spracherkennung. Der dtw-Algorithmus wird hauptsächlich in Zeitreihendaten verwendet, z. B. bei der Spracherkennung einzelner Wörter, der Gestenerkennung, dem Data Mining und dem Informationsabruf.

Die Betriebsumgebung dieses Tutorials: Windows 7-System, Dell G3-Computer.

Es gibt mehrere Ähnlichkeits- oder Distanzfunktionen für Zeitreihendaten, die bekannteste davon ist DTW. Bei der Spracherkennung einzelner Wörter ist die Verwendung des DTW-Algorithmus (Dynamic Time Warping) die einfachste und effektivste Methode. Dieser Algorithmus basiert auf der Idee der dynamischen Programmierung (DP) und löst das Problem der Vorlagenübereinstimmung verschiedener Aussprachen. Es handelt sich um einen früheren und klassischeren Algorithmus der Spracherkennung, der zur Erkennung isolierter Wörter verwendet wird.

Der dynamische Time-Warping-Algorithmus DTW (Dynamic Time Warping) ist ein dynamischer Programmieralgorithmus, der die Ähnlichkeit zweier Zeitreihen berechnet, insbesondere Sequenzen unterschiedlicher Länge. Es wird hauptsächlich in Zeitreihendaten verwendet, z. B. bei der Spracherkennung einzelner Wörter, der Gestenerkennung, dem Data Mining und dem Informationsabruf.

Der HMM-Algorithmus muss während der Trainingsphase eine große Menge an Sprachdaten bereitstellen, und die Modellparameter können durch wiederholte Berechnungen erhalten werden, während das Training des DTW-Algorithmus fast keine zusätzlichen Berechnungen erfordert. Daher wird der DTW-Algorithmus immer noch häufig bei der Spracherkennung einzelner Wörter verwendet.

Ob in der Trainings- und Vorlagenerstellungsphase oder in der Erkennungsphase, der Endpunktalgorithmus wird zunächst verwendet, um den Start- und Endpunkt der Rede zu bestimmen. Jeder in der Vorlagenbibliothek gespeicherte Eintrag wird als Referenzvorlage bezeichnet. Eine Referenzvorlage kann als R={R(1), R(2),..., R(m),..., R(M) ausgedrückt werden. }, m ist die Zeitnummer des Trainingssprachrahmens, m=1 ist der Startsprachrahmen, m=M ist der Endsprachrahmen, also ist M die Gesamtzahl der in der Vorlage enthaltenen Sprachrahmen und R( m) ist der Sprachmerkmalsvektor des m-ten Rahmens. Eine zu erkennende Eingabeeingabesprache wird als Testvorlage bezeichnet, die ausgedrückt werden kann als T = {T (1), T (2), ..., T (n), ..., T (N)}, n ist die Testsprache. Das Timing-Label des Rahmens, n=1 ist der Start-Sprachrahmen, n=N ist der End-Sprachrahmen, also ist N die Gesamtzahl der in der Vorlage enthaltenen Sprachrahmen und T(n). der Sprachmerkmalsvektor des n-ten Frames. Die Referenzvorlage und die Testvorlage verwenden im Allgemeinen denselben Merkmalsvektortyp (z. B. MFCC, LPC-Koeffizienten), dieselbe Rahmenlänge, dieselbe Fensterfunktion und dieselbe Rahmenverschiebung.

Angenommen, die Test- und Referenzvorlagen werden durch T bzw. R dargestellt. Um die Ähnlichkeit zwischen ihnen zu vergleichen, kann der Abstand zwischen ihnen D[T, R] berechnet werden. Um diesen Verzerrungsabstand zu berechnen, beginnen Sie mit dem Abstand zwischen entsprechenden Bildern in T und R. Es seien n und m willkürlich ausgewählte Bildnummern in T bzw. R, und d[T(n),R(m)] repräsentiert den Abstand zwischen den Merkmalsvektoren dieser beiden Bilder. Die Distanzfunktion hängt von der tatsächlich verwendeten Distanzmetrik ab, und im DTW-Algorithmus wird normalerweise die euklidische Distanz verwendet.

Wenn N=M, kann es direkt berechnet werden. Andernfalls sollten Sie eine Ausrichtung von T (n) und R (m) in Betracht ziehen. Für die Ausrichtung kann die lineare Erweiterungsmethode verwendet werden. Wenn N < )} Entfernung berechnet werden. Bei solchen Berechnungen wird jedoch nicht berücksichtigt, dass sich die Dauer jedes Sprachsegments unter verschiedenen Umständen länger oder kürzer ändern kann, sodass der Erkennungseffekt nicht optimal sein kann. Daher werden dynamischere Programmiermethoden (DP) verwendet.

Wenn jede Bildnummer n=1~N der Testvorlage auf der horizontalen Achse in einem zweidimensionalen rechteckigen Koordinatensystem markiert ist und jede Bildnummer m=1~M der Referenzvorlage auf der vertikalen Achse markiert ist, Durch Zeichnen einiger vertikaler und horizontaler Linien können diese ganzzahligen Koordinaten, die die Frame-Nummer darstellen, ein Netzwerk bilden. Jeder Schnittpunkt (n, m) im Netzwerk repräsentiert den Schnittpunkt eines bestimmten Frames im Testmodus. Der DP-Algorithmus kann so zusammengefasst werden, dass er einen Pfad durch mehrere Gitterpunkte in diesem Netzwerk findet. Die vom Pfad durchlaufenen Gitterpunkte sind die in den Test- und Referenzvorlagen berechneten Frame-Nummern. Der Pfad wird nicht willkürlich gewählt. Erstens kann sich die Aussprachegeschwindigkeit eines Sprachlauts ändern, aber die Reihenfolge seiner Teile kann nicht geändert werden. Daher muss der ausgewählte Pfad in der unteren linken Ecke beginnen und in der oberen rechten Ecke enden

Zur Beschreibung dieses Pfads wird davon ausgegangen, dass alle vom Pfad durchlaufenen Gitterpunkte (n1, m1),..., (ni, mj),..., (nN, mm) sind, wobei (n1, m1 ) = (1, 1), (nN,mM)=(N,M). Der Pfad kann durch die Funktion m = Oslash;(n) beschrieben werden, wobei n =i, i=1, 2,...,N, Ø(1)=1, Ø(N)=M. Um zu verhindern, dass der Pfad zu stark geneigt ist, kann die Neigung auf einen Bereich von 0,5 bis 2 beschränkt werden. Wenn der Pfad den Gitterpunkt (n, m) bereits passiert hat, wird der nächste Gitterpunkt (n, m) angezeigt ) übergeben werden, können nur die folgenden drei sein. Fall eins:

（n ，m ）=（n +1，m）
（n ，m ）=（n +1，m +1）
（n ，m ）=（n ，m+1 ）

Verwenden Sie r, um die oben genannten drei Einschränkungen darzustellen. Das Problem, den besten Pfad zu finden, lässt sich auf das Finden der besten Pfadfunktion m =Ø(n) reduzieren, wenn die Einschränkungsbedingung r erfüllt ist, sodass die akkumulierte Distanz entlang des Pfads den Mindestwert erreicht, d. h.:

搜索该路径的方法如下：搜索从（n, m）点出发，可以展开若干条满足ŋ的路径，假设可计算每条路径达到（n, m）点时的总的积累距离，具有最小累积距离者即为最佳路径。易于证明，限定范围的任一格点（n, m）只可能有一条搜索路径通过。对于（n, m），其可达到该格点的前一个格点只可能是（n-1, m）、（n-1, m -1）和（n, m-1），那么（n, m）一定选择这3个距离之路径延伸而通过（n, m），这时此路径的积累距离为：

D[(n, m)]=d[T(n),R(m)]+min{D(n-1,m),D(n-1,m-1),D(n,m-1)}

这样可以从（n ，m ）=（1，1）出发搜索（n ，m ），对每一个（n ，m ）都存储相应的距离，这个距离是当前格点的匹配距离与前一个累计距离最小的格点（按照设定的斜率在三个格点中进行比较）。搜索到（n ，m ）时，只保留一条最佳路径。如果有必要的话，通过逐点向前寻找就可以求得整条路径。这套DP算法便是DTW算法。

DTW算法可以直接按上面描述来实现，即分配两个N×M的矩阵，分别为积累距离矩阵D和帧匹配距离矩阵d，其中帧匹配距离矩阵d（i，j）的值为测试模板的第i帧与参考模板的第j帧间的距离。D（N，M）即为最佳匹配路径所对应的匹配距离

更多相关知识，请访问常见问题栏目！

Das obige ist der detaillierte Inhalt vonWas ist der DTW-Algorithmus?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!