动态时间归整/规整/弯曲(Dynamic time warping,DTW)

动态时间规整DTW

 

在日常的生活中我们最经常使用的距离毫无疑问应该是欧式距离，但是对于一些特殊情况，欧氏距离存在着其很明显的缺陷，比如说时间序列，举个比较简单的例子，序列A：1,1,1,10,2,3，序列B：1,1,1,2,10,3，如果用欧氏距离，也就是distance[i][j]=(b[j]-a[i])*(b[j]-a[i])来计算的话，总的距离和应该是128，应该说这个距离是非常大的，而实际上这个序列的图像是十分相似的，这种情况下就有人开始考虑寻找新的时间序列距离的计算方法，然后提出了DTW算法，这种方法在语音识别，机器学习方便有着很重要的作用。

这个算法是基于动态规划（DP）的思想，解决了发音长短不一的模板匹配问题，简单来说，就是通过构建一个邻接矩阵，寻找最短路径和。

还以上面的2个序列作为例子，A中的10和B中的2对应以及A中的2和B中的10对应的时候，distance[3]以及distance[4]肯定是非常大的，这就直接导致了最后距离和的膨胀，这种时候，我们需要来调整下时间序列，如果我们让A中的10和B中的10 对应，A中的1和B中的2对应，那么最后的距离和就将大大缩短，这种方式可以看做是一种时间扭曲，看到这里的时候，我相信应该会有人提出来，为什么不能使用A中的2与B中的2对应的问题，那样的话距离和肯定是0了啊，距离应该是最小的吧，但这种情况是不允许的，因为A中的10是发生在2的前面，而B中的2则发生在10的前面，如果对应方式交叉的话会导致时间上的混乱，不符合因果关系。

接下来，以output[6][6](所有的记录下标从1开始，开始的时候全部置0)记录A，B之间的DTW距离，简单的介绍一下具体的算法，这个算法其实就是一个简单的DP，状态转移公式是output[i][j]=Min(Min(output[i-1][j],output[i][j-1]),output[i-1][j-1])+distance[i][j];最后得到的output[5][5]就是我们所需要的DTW距离.

DTW的C语言实现

#include<iostream>
#include<string.h>
using namespace std;
#define NUM 5       //序列中样本点的个数简单起见，假设2个序列的样本点一样多
#define Min(a,b) (a<b?a:b)

int main()
{
 int i,j,k;
 int a[NUM],b[NUM];
 int distance[NUM+1][NUM+1];
 int output[NUM+1][NUM+1];

 memset(distance,0,sizeof(distance));
 memset(output,0,sizeof(output));
 for(i=0;i<NUM;i++)  cin>>a[i];
 for(i=0;i<NUM;i++)  cin>>b[i];
 for(i=1;i<=NUM;i++)
  for(j=1;j<=NUM;j++)
   distance[i][j]=(b[j-1]-a[i-1])*(b[j-1]-a[i-1]);    //计算点与点之间的欧式距离

 for(i=1;i<=NUM;i++)
 {
  for(j=1;j<NUM;j++)
   cout<<distance[i][j]<<'\t';
  cout<<endl;
 } //输出整个欧式距离的矩阵
 cout<<endl;
 for(i=1;i<=NUM;i++)
  for(j=1;j<NUM;j++)
   output[i][j]=Min(Min(output[i-1][j-1],output[i][j-1]),output[i-1][j])+distance[i][j];
 //DP过程，计算DTW距离
   
 for(i=0;i<=NUM;i++)
 {
  for(j=0;j<NUM;j++)
   cout<<distance[i][j]<<'\t';
  cout<<endl;
 } //输出最后的DTW距离矩阵，其中output[NUM][NUM]为最终的DTW距离和
 
 return 0;
}

动态时间规整DTW

动态时间规整DTW(dynamic time warping)曾经是语音识别的一种主流方法。
其思想是：由于语音信号是一种具有相当大随机性的信号，即使相同说话者对相同的词，每一次发音的结果都是不同的，也不可能具有完全相同的时间长度。因此在与已存储模型相匹配时，未知单词的时间轴要不均匀地扭曲或弯折，以使其特征与模板特征对正。用时间规整手段对正是一种非常有力的措施，对提高系统的识别精度非常有效。
动态时间规整DTW是一个典型的优化问题，它用满足一定条件的的时间规整函数W(n)描述输入模板和参考模板的时间对应关系，求解两模板匹配时累计距离最小所对应的规整函数。

™将时间规整与距离测度结合起来，采用动态规划技术，比较两个大小不同的模式，解决语音识别中语速多变的难题；
™一种非线性时间规整模式匹配算法；

DTW ( Dynamic Time Warping )，即「动态时间扭曲」或是「动态时间规整」。这是一套根基于「动态规划」（Dynamic Programming，简称DP）的方法，可以有效地将搜寻比对的时间大幅降低。
DTW 的目标就是要找出两个向量之间的最短距离。一般而言，对于两个 n 维空间中的向量 x 和 y，它们之间的距离可以定义为两点之间的直线距离，称为尤拉距离（Euclidean Distance）。
dist(x, y) = |x – y| ，
但是如果向量的长度不同，那它们之间的距离，就无法使用上述的数学式來计算。一般而言，假設这两个向量的元素位置都是代表时间，由于我们必須容忍在时间轴的偏差，因此我们並不知道两个向量的元素对应关系，因此我们必須靠着一套有效的运算方法，才可以找到最佳的对应关系。

DTW是用于与说话人有关（Speaker Dependent）的语音识别，使用者自行录音然后再以自己的声音來比对之前录好的语音资料。此方法比較适合同一位说话人的声音來进行比較，因此应用范围比较狭隘，譬如目前手机 Name Dialing 等等。

DTW的问题：
™运算量大；
™识别性能过分依赖于端点检测；
™太依赖于说话人的原来发音；
™不能对样本作动态训练；
™没有充分利用语音信号的时序动态特性；
DTW适合于特定人基元较小的场合，多用于孤立词识别；

动态规划算法总体思想
动态规划算法基本思想是将待求解问题分解成若干个子问题
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

动态规划基本步骤
找出最优解的性质，并刻划其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息，构造最优解

一、动态时间规整的提出
　　语音信号具有很强的随机性，不同的发音习惯，发音时所处的环境不同，心情不同都会导致发音持续时间长短不一的现象。如单词最后的声音带上一些拖音，或者带上一点呼吸音，此时，由于拖音或呼吸音会被误认为一个音素，造成单词的端点检测不准，造成特征参数的变化，从而影响测度估计，降低识别率，因此在语音识别时，首先有必要对语音信号进行时间规整。

二、动态时间规整的定义

　　一次正确的发音应该包含构成该发音的全部音素以及正确的音素连接次序。其中各音素持续时间的长短与音素本身以及讲话人的状况有关。为了提高识别率，克服发同一音而发音时间长短的不同，采用对输入语音信号进行伸长或缩短直到与标准模式的长度一致。这个过程称为时间规整。

三、动态时间规整的原理描述

　　60年代由日本学者提出，算法的思想是把未知量伸长或缩短(压扩)，直到与参考模板的长度一致，在这一过程中，未知单词的时间轴会产生扭曲或弯折，以便其特征量与标准模式对应。

原理描述

　　DTW 是把时间规整和距离测度计算结合起来。测试语音参数共有I帧矢量，而参考模板共有J帧矢量，I和J不等，寻找一个时间规整函数j=w(i)，它将测试矢量的时间轴i非线性地映射到模板的时间轴j上，并使该函数w(i)满足：

第i帧测试矢量T(i)和第j帧模板矢量R(j)之间的距离测度D。

 　　最优时间规整情况下所有矢量帧间的距离，也称为代价函数。

公式2

计算两倒谱矢量帧(i和j) 间的欧氏距离，两矢量帧中分别具有p个倒谱参数。

 　　为了使T（测试）的第i个样本与R（参考）的第j个样本对正，其对应的点不在直线对角线上，得到一条弯曲的曲线j=w(i) 。j=w(i)称为规整函数。

时间规整的依据

　　设 T={a1 , a2 , …… , ai , …… , aI} i=1～I 　　R={b1 , b2 , …… , bj , …… , bJ} j=1～J 　　I≠J　　时间规整要解决的问题是使元素a和元素b之间匹配，使每对匹配样本之间的差别最小,达到欧氏距离最小。

 

 

 

 

 

Veeraraghavan等人用动态时间规整（dynamic time warping，DTW）来匹配运动序列。DTW是一种时变数据序列匹配方法，常用于微生物学的DNA匹配、字符串和符号的比较以及语音分析[77]。DTW算法的思想是给定参考模板特征矢量序列与输入特征矢量序列，寻找一个最佳的时间规整函数，使得输入序列的时间轴映射到参考模板的时间轴上总的累计失真最小。对DTW而言，即使测试序列模式与参考序列模式的时间尺度不能完全一致，只要时间次序约束存在，它仍能较好地完成测试序列与参考序列之间的模式匹配。DTW具有概念简单、算法鲁棒的优点，能够对图像序列进行分类。文献[35]在形状空间中用动态时间规整方法计算两个形状序列之间的距离来识别动作和步态，取得了很好的分类结果。然而，DTW算法计算量较大，缺乏考虑相邻时序之间的动态特性，而在实际中，运动序列中相邻序列在时间和空间上有高度的相关性。

1)  dynamic time war ping (DTW) 
动态时轴弯曲或动态时间规正(DTW)
2)  DTW 
动态时间规整(DTW)
3)  dynamic time warping 
动态时间弯曲
1.Time series similar pattern matching based on wavelet and dynamic time warping; 
基于小波和动态时间弯曲的时间序列相似匹配
2.Similarity matching algorithm for interval-valued time series based on dynamic time warping;
基于动态时间弯曲的区间值时间序列匹配算法
3.Through dynamic time warping analysis to the hot-fire test data and simulated fault data of a certain liquid rocket engine,the warped path sets were obtained.
对某大型液体火箭发动机的热试车数据及通过发动机模型仿真得到的故障数据进行动态时间弯曲分析,得到弯曲路径集,然后结合决策树方法进行了故障检测和诊断。
更多例句>>
4)  Dynamic Time Warping(DTW) 
动态时间弯曲
1.An efficient lower bounding technique is proposed based on Dynamic Time Warping(DTW) for time series similarity search,which measures the distance between original sequence reduced dimensionality by Piecewise Aggregate Approximation(PAA) approximation method and query sequence reduced dimensionality by Grid Minimum Bounding Rectangle(GMBR) representation approach.
针对时间序列数据,提出一种新的基于动态时间弯曲的下界技术,该技术首先基于分段聚集近似的线性表示对原始序列进行降维,同时生成查询序列的网格最小边界矩形近似表示,然后利用基于动态时间弯曲距离对两者下界距离度量。
更多例句>>
5)  dynamic time alignment 
时间动态规正
6)  dynamic time warping 
动态时间规正
1.Gait contour by using Fourier descriptors was described,to make quasi-periodic analysis on height and width ratio of gait image,and to solve the problems resulting from image sequence of different gait cycle by using dynamic time warping.
利用傅立叶描绘子对步态轮廓图像进行描述,用步态图像的高宽比进行步态的准周期性分析,并采用动态时间规正算法解决不同的步态周期的图像序列之间的比较问题。
2.In the system, RelAtive SepeTrAl(RASTA) filter was used to reduce the convolution channel noise mixed in speech signal, and the improved dynamic time warping (DTW) algorithm was adopted for recognizing speech command.
该系统采用RASTA滤波方法去除语音信号中夹杂的卷积信道噪声,采用改进的动态时间规正(DTW)算法对语音命令进行识别。

 

DTW（Dynamic Time Warping，动态时间归整）算法，该算法基于动态规划（DP）的思想，解决了发音长短不一的模板匹配问题，是语音识别中出现较早、较为经典的一种算法。用于孤立词识别，DTW算法与HMM算法在训练阶段需要提供大量的语音数据，通过反复计算才能得到模型参数，而DTW算法的训练中几乎不需要额外的计算。所以在孤立词语音识别中，DTW算法仍然得到广泛的应用。

 

 

机群系统上并行计算时间序列的动态弯曲距离
莫倩芸　 钟诚　
时间序列的相似性度量是衡量两个序列相似性的依据.动态时间弯曲距离计算方法具有较强的健壮性且可以度量不同长度的时间序列间的相似性,但其十分耗时.采用波前式推进方法并行计算动态时间弯曲距离并以流水线并行方式传送局部子结果,提出一个在机群系统上实现的度量两个时间序列相似性的并行算法.PC机群系统上的实验结果表明,该并行算法高效,获得了良好的加速和可扩展性.
关键词：时间序列;动态时间弯曲;并行计算;机群系统

 

基于分段线性动态时间弯曲的时间序列聚类算法研究
翁颖钧  朱仲英 
时间序列是一类重要的复杂类型数据 ,时间序列知识发现正成为知识发现的研究热点之一。欧几里德距离及其扩展作为相似测度被广泛应用于时间序列的比较中 ,但是这种距离测度对数据没有好的鲁棒性。动态时间弯曲技术是基于非线性动态编程的一种模式匹配算法 ,但是其计算复杂性相当高。本文提出了基于时间序列分段线性表示的动态时间弯曲算法 ,通过计算线性分段序列数据之间的最短弯曲路径来获得序列的匹配。对综合控制时间序列数据进行基于不同距离测度的聚类分析对比结果表明本文提出的算法有很高的精度和对振幅差异、嘈声和线性漂移有强的鲁棒性 ,大大降低计算复杂性 ,具有良好的应用价值

 

1)  Segmented Dynamic Time Warping Distance 
分段动态弯曲距离
1.After finding similar segmented subsequence by Segmented Dynamic Time Warping Distance,this method then search this subsequence point by point,by which the subsequence is acquired accurately.
该算法首先通过中线距离阈值和极值点两个约束条件分段线性拟合时间序列,利用分段动态弯曲距离度量获得相似的分段子序列,逐点检索该子序列实现序列的精确查询。
2)  Time Warping Distance 
动态弯曲距离
3)  segmented time warping distance 
分段时间弯曲距离
4)  Dynamic Time Warping distance 
动态时间弯曲距离
5)  range curvature distortion 
距离弯曲
1.In this dissertation, the presence of range curvature distortion in conventional PFA is analyzed from data format perspective.
本文对聚束模式经典算法极坐标格式算法(Polar Format Algorithm, PFA)进行讨论,从信号格式角度分析了PFA中距离弯曲对高分辨率成像区域大小的限制,并给出补偿距离弯曲的一般方法,但距离弯曲的空变性使得补偿复杂且运算量大。
更多例句>>
6)  range curvature distinction 
距离弯曲差
1.Effect caused by range curvature distinction for deception jamming under SAR imaging 
距离弯曲差对SAR欺骗干扰成像的影响

动态时间归整算法http://www.doc88.com/p-91694157837.html
动态时间归整算法http://www.docin.com/p-86210991.html

机群系统上并行计算时间序列的动态弯曲距离http://wenku.baidu.com/view/c40dabba1a37f111f1855b60.html

 

 

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 time or speed. For instance, similarities in walking patterns would be detected, even if in one video the person was walking slowly and if in another he or she were walking more quickly, or even if there were accelerations and decelerations during the course of one observation. DTW has been applied to video, audio, and graphics — indeed, any data which can be turned into a linear representation can be analyzed with DTW. A well known application has been automatic speech recognition, to cope with different speaking speeds.

In general, DTW is a method that allows a computer to find an optimal match between two given sequences (e.g. time series) with certain restrictions. The sequences are "warped" non-linearly in the time dimension to determine a measure of their similarity independent of certain non-linear variations in the time dimension. Thissequence alignment method is often used in the context of hidden Markov models.

One example of the restrictions imposed on the matching of the sequences is on the monotonicity of the mapping in the time dimension. Continuity is less important in DTW than in other pattern matching algorithms; DTW is an algorithm particularly suited to matching sequences with missing information, provided there are long enough segments for matching to occur.

The extension of the problem for two-dimensional "series" like images (planar warping) is NP-complete, while the problem for one-dimensional signals .like time series can be solved in polynomial time

Example of one of the many forms of the algorithm

This example illustrates the implementation of dynamic time warping when the two sequences are strings of discrete symbols. d(x, y) is a distance between symbols, i.e. d(x, y) = | x - y |.

int DTWDistance(char s[1..n], char t[1..m]) { declare int DTW[0..n, 0..m] declare int i, j, cost for i := 1 to m DTW[0, i] := infinity for i := 1 to n DTW[i, 0] := infinity DTW[0, 0] := 0 for i := 1 to n for j := 1 to m cost:= d(s[i], t[j]) DTW[i, j] := cost + minimum(DTW[i-1, j ], // insertion DTW[i , j-1], // deletion DTW[i-1, j-1]) // match return DTW[n, m] }

We sometimes want to add a locality constraint. That is, we require that if s[i] is matched with t[j], then |i - j | is no larger than w, a window parameter.

We can easily modify the above algorithm to add a locality constraint (differences marked in bold italic). However, the above given modification works only if |n - m| is no larger than w, i.e. the end point is within the window length from diagonal. In order to make the algorithm work, the window parameter w must be adapted so that |n - m ≤ w| (see the line marked with (*) in the code).

int DTWDistance(char s[1..n], char t[1..m], int w) { declare int DTW[0..n, 0..m] declare int i, j, cost w := max(w, abs(n-m)) // adapt window size (*) for i := 0 to n for j:= 0 to m DTW[i, j] := infinity DTW[0, 0] := 0 for i := 1 to n for j := max(1, i-w) to min(m, i+w) cost := d(s[i], t[j]) DTW[i, j] := cost + minimum(DTW[i-1, j ], // insertion DTW[i , j-1], // deletion DTW[i-1, j-1]) // match return DTW[n, m] }

Open Source software

• The lbimproved C++ library implements Fast Nearest-Neighbor Retrieval algorithms under the Dynamic Time Warping (GPL). It also provides a C++ implementation of Dynamic Time Warping as well as various lower bounds.
• The R package dtw implements most known variants of the DTW algorithm family, including a variety of recursion rules (also called step patterns), constraints, and substring matching.
• The mlpy Python library implements DTW.

References

• Sakoe, H. and Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, IEEE Transactions on Acoustics, Speech and Signal Processing, 26(1) pp. 43- 49, 1978, ISSN: 0096-3518
• C. S. Myers and L. R. Rabiner. A comparative study of several dynamic time-warping algorithms for connected word recognition. The Bell System Technical Journal, 60(7):1389-1409, September 1981.
• L. R. Rabiner and B. Juang. Fundamentals of speech recognition. Prentice-Hall, Inc., 1993 (Chapter 4)

See also

• Levenshtein distance
• Elastic matching

Retrieved from "http://en.wikipedia.org/w/index.php?title=Dynamic_time_warping&oldid=477883155"