第一句子网 > 语音识别：时间序列的动态扭曲相似度（DTW）算法

语音识别：时间序列的动态扭曲相似度（DTW）算法

时间：2019-10-15 03:33:34

一、说明

二、DTW算法原理分析

2.1 约束和限定

2.2 朴素的匹配

2.3 带有窗口范围的匹配

三、DTW用于语音匹配

1）m和n不一定相等，这不必担心，在算法中将产生wraping调整

2）这种warping有一定要求，需要满足以下几个约束

3）最小距离的路径确定

一、说明

时间序列：时间序列就是序列中，次序不能颠倒的信号序列。图像、语音都是不可颠倒的序列。然而声音比图像更加有弹性，那就是局部音拉长缩短，不改变原来的意思。

在时间序列分析中，动态时间扭曲 (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 nfor j := 0 to mDTW[i, j] := infinityDTW[0, 0] := 0for i := 1 to nfor j := 1 to mcost := d(s[i], t[j])DTW[i, j] := cost + minimum(DTW[i-1, j ], // insertionDTW[i , j-1], // deletionDTW[i-1, j-1]) // matchreturn 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 nfor j:= 0 to mDTW[i, j] := infinityDTW[0, 0] := 0for i := 1 to nfor j := max(1, i-w) to min(m, i+w)DTW[i, j] := 0for i := 1 to nfor 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 ], // insertionDTW[i , j-1], // deletionDTW[i-1, j-1]) // matchreturn DTW[n, m]}

这里重点探讨基本的匹配问题，带窗口的匹配可以在应用中继续探讨。

三、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’) <=1和 (b-b’) <=1。也就是不可能跨过某个点去匹配，只能和自己相邻的点对齐。这样可以保证Q和C中的每个坐标都在W中出现。3）单调性：如果wk-1=(a’, b’)，那么对于路径的下一个点wk=(a, b)需要满足0<=(a-a’)和0<= (b-b’)。这限制W上面的点必须是随着时间单调进行的。以保证图B中的虚线不会相交。

结合连续性和单调性约束，每一个格点的路径就只有三个方向了。例如如果路径已经通过了格点(i, j)，那么下一个通过的格点只可能是下列三种情况之一：(i+1, j)，(i, j+1)或者(i+1, j+1)。

满足上面这些约束条件的路径可以有指数个，然后我们感兴趣的是使得下面的规整代价最小的路经。