目录
1）m和n不一定相等，这不必担心，在算法中将产生wraping调整
一、说明
时间序列：时间序列是一系列中不能反转的信号序列。图像和声音是不可逆的序列。然而，声音比图像更灵活，即在不改变原意的情况下，将局部声音加长和缩短。
[En]
Time series: a time series is a signal sequence in a series that cannot be reversed. Image and voice are irreversible sequences. However, sound is more flexible than image, that is, the local sound is lengthened and shortened without changing the original meaning.
在时间序列分析中，动态时间扭曲 (DTW) 是一种用于测量两个时间序列之间相似性的算法，这两个时间序列的速度可能不同。例如，即使一个人走得比另一个人快，或者在观察过程中出现加速和减速，也可以使用 DTW 检测步行的相似性。 DTW 已应用于视频、音频和图形数据的时间序列。实际上，任何可以转换为线性序列的数据都可以使用 DTW 进行分析。一个众所周知的应用是自动语音识别，以应对不同的语速。其他应用包括说话人识别和在线签名识别。它还可以用于部分形状匹配应用。
二、DTW算法原理分析
2.1 约束和限定
一般来说，DTW 是一种计算两个给定序列（例如时间序列）之间的最佳匹配的方法，具有一定的限制和规则：
- 第一个序列中的每个索引都必须与另一个序列中的一个或多个索引匹配，反之亦然
- 第一个序列的第一个索引必须与另一个序列的第一个索引匹配（但它不必是唯一匹配）
- 第一个序列的最后一个索引必须与另一个序列的最后一个索引匹配（但它不必是唯一匹配）
- *从第一个序列的索引到另一个序列的索引的映射必须是单调递增的，反之亦然，即如果j和i都是第一个序列的索引值，且 ；l和k是另一个序列索引，且 ；那么，不允许出现（i，l）匹配，（j，k）匹配。
最佳匹配由满足所有限制和规则并具有最小
的匹配表示，其中计算为每个匹配的索引对在它们的值之间的绝对差的总和。
序列在时间维度中被非线性地”扭曲”，以确定它们的相似性的度量，而与时间维度中的某些非线性变化无关。这种序列比对方法常用于时间序列分类。尽管 DTW 测量两个给定序列之间的类似距离的量， 但它并不能保证三角不等式成立。
2.2 朴素的匹配
除了两个序列之间的相似性度量之外，还产生了所谓的”扭曲路径”，通过根据该路径扭曲两个信号可以在时间上对齐。具有原始点集 X(original), Y(original) 的信号被转换为 X(warped), Y(warped)。这在基因序列和音频同步中找到了应用。在相关技术中，可以使用该技术对不同速度的序列进行平均，参见平均序列部分。他在概念上与 Needleman-Wunsch 算法非常相似。
这个例子说明了当两个序列 s 和 t 是离散符号串时动态时间扭曲算法的实现。对于两个符号 x 和 y，d(x, y) 是符号之间的距离，例如d(x, y) = | x – y |。
int DTWDistance(s: array [1..n], t: array [1..m]) {
DTW := array [0..n, 0..m]
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 := 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]
}
其中 DTW[i, j] 是 s[1:i] 和 t[1:j] 之间具有最佳对齐的距离。
举个例子:有两个序列，其序列值为
str1 = [1,2,4,3,5,3,2,3,2,5]
str2 = [1,1,2,4,3,5,3,2,3,2]
step1：首先求出边界的DTW：
step2：逐行填写
。。。。。。。。。。。
2.3 带有窗口范围的匹配
我们有时想添加一个局部约束。也就是说，我们要求如果 s[i] 与 t[j] 匹配，则
不大于 w，一个窗口参数。
我们可以轻松地修改上述算法以添加局部约束（已标记差异）。然而，上述修改仅在
时有效n – m |不大于 w，即终点在距对角线的窗口长度内。为了使算法工作，必须调整窗口参数 w 使得 （请参阅代码中标有 (*) 的行）。
int DTWDistance(s: array [1..n], t: array [1..m], w: int) {
DTW := array [0..n, 0..m]
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)
DTW[i, j] := 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]
}
本文主要研究了基本的匹配问题，并在实际应用中继续讨论了与窗口的匹配问题。
[En]
This paper focuses on the basic matching problem, and the matching with window can continue to be discussed in the application.
三、DTW用于语音匹配
动态时间规整DTW是一个典型的优化问题，它用满足一定条件的的时间规整函数W(n)描述测试模板和参考模板的时间对应关系，求解两模板匹配时累计距离最小所对应的规整函数。
假设我们有两个时间序列Q和C，他们的长度分别是n和m：（实际语音匹配运用中，一个序列为参考模板，一个序列为测试模板，序列中的每个点的值为语音序列中每一帧的特征值。例如语音序列Q共有n帧，第i帧的特征值（一个数或者一个向量）是qi。至于取什么特征，在这里不影响DTW的讨论。我们需要的是匹配这两个语音序列的相似性，以达到识别我们的测试语音是哪个词）
Q= q1,q2,…,qi,…, qn ;
C= c1,c2,…, cj,…, cm ;
比对两个序列，
1）m和n不一定相等，这不必担心，在算法中将产生wraping调整
2） 这种warping有一定要求， 需要满足以下几个约束
- 1 ）边界条件：w1=(1,1)和wK=(m, n)。任何一种语音的发音快慢都有可能变化，但是其各部分的先后次序不可能改变，因此所选的路径必定是从左下角出发，在右上角结束。
- 2 ）连续性：如果wk-1=(a’, b’)，那么对于路径的下一个点wk=(a, b)需要满足 (a-a’)
结合连续性和单调性约束，每一个格点的路径就只有三个方向了。例如如果路径已经通过了格点(i, j)，那么下一个通过的格点只可能是下列三种情况之一：(i+1, j)，(i, j+1)或者(i+1, j+1)。
可以存在满足上述约束的指数数量的路径，然后我们感兴趣的是最小化后续标准化的成本的路径。
[En]
There can be an exponential number of paths that meet the above constraints, and then we are interested in the paths that minimize the cost of the following normalization.
3）最小距离的路径确定
参考文章：
【Paper】DTW&Sequence Analysis_liudongdong_jlu-CSDN博客
【ML算法】DWT时序匹配_liudongdong_jlu-CSDN博客_dwt算法
DTW(dynamic time wraping)算法浅析以及改进 – 知乎 (zhihu.com)
Original: https://blog.csdn.net/gongdiwudu/article/details/122154441
Author: 无水先生
Title: 语音识别：时间序列的动态扭曲相似度（DTW）算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/527243/
转载文章受原作者版权保护。转载请注明原作者出处！