Maison  >  Article  >  Qu'est-ce que l'algorithme DTW ?

Qu'est-ce que l'algorithme DTW ?

coldplay.xixi
coldplay.xixioriginal
2020-12-18 10:08:5411088parcourir

L'algorithme dtw fait référence à l'algorithme de déformation temporelle dynamique, qui est basé sur l'idée de programmation dynamique DP. Il s'agit d'un algorithme de programmation dynamique qui calcule la similitude de deux séries temporelles, en particulier des séquences de longueurs différentes ; il résout le problème de la longueur de la prononciation. Le problème de correspondance des différents modèles est un algorithme plus ancien et plus classique en reconnaissance vocale. L'algorithme dtw est principalement utilisé dans les données de séries chronologiques, telles que la reconnaissance vocale de mots isolés, la reconnaissance gestuelle, l'exploration de données et la récupération d'informations.

Qu'est-ce que l'algorithme DTW ?

L'environnement d'exploitation de ce tutoriel : système Windows 7, ordinateur Dell G3.

Il existe de nombreuses fonctions de similarité ou de distance pour les données de séries chronologiques, dont la plus importante est DTW. Dans la reconnaissance vocale de mots isolés, la méthode la plus simple et la plus efficace consiste à utiliser l'algorithme DTW (Dynamic Time Warping) Cet algorithme est basé sur l'idée de programmation dynamique (DP) et résout le problème de la correspondance de modèles. différentes prononciations. Le problème est un algorithme plus ancien et plus classique en reconnaissance vocale, utilisé pour la reconnaissance de mots isolés.

L'algorithme de déformation temporelle dynamique DTW (Dynamic Time Warping) est un algorithme de programmation dynamique qui calcule la similarité de deux séries temporelles, en particulier des séquences de longueurs différentes. Il est principalement utilisé dans les données de séries chronologiques, telles que la reconnaissance vocale de mots isolés, la reconnaissance gestuelle, l'exploration de données et la récupération d'informations.

L'algorithme HMM doit fournir une grande quantité de données vocales pendant la phase de formation, et les paramètres du modèle peuvent être obtenus grâce à des calculs répétés, tandis que la formation de l'algorithme DTW ne nécessite pratiquement aucun calcul supplémentaire. Par conséquent, l’algorithme DTW est encore largement utilisé dans la reconnaissance vocale de mots isolés.

Que ce soit dans la phase de formation et de création de modèles ou dans la phase de reconnaissance, l'algorithme de point final est d'abord utilisé pour déterminer le point de départ et le point final du discours. Chaque entrée stockée dans la bibliothèque de modèles est appelée modèle de référence. Un modèle de référence peut être exprimé sous la forme R={R(1), R(2),..., R(m),..., R(M). }, m est le numéro de synchronisation de la trame vocale d'entraînement, m=1 est la trame vocale de départ, m=M est la trame vocale de fin, donc M est le nombre total de trames vocales incluses dans le modèle, et R( m) est le vecteur de caractéristiques vocales de la m-ième trame. Une parole d'entrée à reconnaître est appelée un modèle de test, qui peut être exprimé sous la forme T = {T (1), T (2), ..., T (n), ..., T (N)}, n est la parole de test. L'étiquette de synchronisation de la trame, n=1 est la trame vocale de début, n=N est la trame vocale de fin, donc N est le nombre total de trames vocales contenues dans le modèle, et T(n) est le vecteur de caractéristiques vocales de la nième trame. Le modèle de référence et le modèle de test utilisent généralement le même type de vecteur de caractéristiques (tels que les coefficients MFCC, LPC), la même longueur de trame, la même fonction de fenêtre et le même décalage de trame.

Supposons que les modèles de test et de référence soient représentés respectivement par T et R. Afin de comparer la similarité entre eux, la distance D[T, R] entre eux peut être calculée. Plus la distance est petite, plus la distance est petite. plus la similarité est élevée. Pour calculer cette distance de distorsion, partez de la distance entre les images correspondantes en T et R. Soient n et m des numéros de trame sélectionnés arbitrairement dans T et R respectivement, et d[T(n),R(m)] représente la distance entre les vecteurs de caractéristiques de ces deux trames. La fonction de distance dépend de la métrique de distance réelle utilisée, et la distance euclidienne est généralement utilisée dans l'algorithme DTW.

Si N=M, cela peut être calculé directement Sinon, l'alignement de T (n) et R (m) doit être envisagé. L'alignement peut utiliser la méthode d'expansion linéaire. Si N

Si chaque numéro d'image n=1~N du modèle de test est marqué sur l'axe horizontal dans un système de coordonnées rectangulaires bidimensionnel, et que chaque numéro d'image m=1~M du modèle de référence est tracé sur l'axe vertical Marquez et tracez des lignes verticales et horizontales passant par ces coordonnées entières représentant le numéro de trame pour former un réseau. Chaque point d'intersection (n, m) dans le réseau représente le point d'intersection d'une certaine trame en mode test. L'algorithme DP peut être résumé comme trouvant un chemin à travers plusieurs points de grille dans ce réseau. Les points de grille traversés par le chemin sont les numéros de trame calculés dans les modèles de test et de référence. Le chemin n'est pas choisi arbitrairement. Tout d'abord, la vitesse de prononciation de tout son vocal peut changer, mais l'ordre de ses parties ne peut pas être modifié. Par conséquent, le chemin sélectionné doit commencer par le coin inférieur gauche et se terminer par le coin supérieur droit.

Afin de décrire ce chemin, supposons que tous les points de grille passés par le chemin sont (n1, m1),..., (ni, mj),..., (nN, mm), où (n1, m1) = (1,1), (nN,mM)=(N,M). Le chemin peut être décrit par la fonction m = Oslash;(n), où n =i, i=1, 2,...,N, Ø(1)=1, Ø(N)=M. Afin d'éviter que le chemin ne soit trop incliné, la pente peut être limitée à une plage comprise entre 0,5 et 2. Si le chemin a déjà dépassé le point de grille (n, m), alors le point de grille suivant (n, m). ) transmis ne peuvent être que les trois suivants. Premier cas :

(n ,m )=(n +1,m)
(n ,m )=(n +1,m +1)
(n ,m )=(n ,m+1 )

Utilisez r pour représenter les trois contraintes ci-dessus. Le problème de trouver le meilleur chemin peut être réduit à trouver la meilleure fonction de chemin m =Ø(n) lorsque la condition de contrainte r est satisfaite, de sorte que la distance accumulée le long du chemin atteigne la valeur minimale, soit :

搜索该路径的方法如下:搜索从(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)即为最佳匹配路径所对应的匹配距离

更多相关知识,请访问常见问题栏目!

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn