DTW 动态时间规整

单位要做唤醒，同事扔来了一个MFCC-DTW的就完了，大致研究了一下，下面内容摘自各博客和对照代码的总结。

问题描述

DTW主要解决两段语音的相似性问题：当数据在时间线上不对齐的时候，使用传统的匹配方法，是无法使用传统的全局匹配度量法的。该算法基于动态规划（DP）的思想，解决了发音长短不一的模板匹配问题，是语音识别中出现较早、较为经典的一种算法，用于孤立词识别。

算法简介

给定两个时间序列，长度分别为n和m：
$Q = q_1, q_2,…,q_i,…, q_n ;$
$C = c_1, c_2,…, c_j,…, c_m ;$
由于m和n不等长，因此需要对其两组序列，但是由于不清楚两组数据的局部缩放情况，所以不能整段缩放（对应后面矩阵应该是一条直线），因此需要采用动态规划的方法（dynamic programming）
动态规划的核心思想可以用一幅图来解释
构造一个距离矩阵矩阵元素 $(i,j)$ 表示两个序列对应元素的距离 $d( q_i,c_j)$ ,矩阵元素就表示这两个点之间的距离，或者说是相似度，距离越小，相似度越高。
而动态规划的主要目的，就是需要一条最优路径，使两段语音的累积路径和最小，可以得到的两段语音的相似性越高。用公式描述即：
$DTW(Q,C ) = min{( \frac {\sum_{k= 1}^{K}W_k}{ K})}$
其中， $W_k$ 是距离， $K$ 是规划的路径长度。
$W_k$ 满足的约束条件：

1）边界条件： $w_1=(1, 1)$ 和 $w_K=(m, n)$ 。任何一种语音的发音快慢都有可能变化，但是其各部分的先后次序不可能改变，因此所选的路径必定是从左下角出发，在右上角结束。
2）连续性：如果 $w_k-1= (a’, b’)$ ，那么对于路径的下一个点 $w_k=(a, b)$ 需要满足 $(a-a’) \leq 1$ 和 $(b-b’)\leq 1$ 。也就是不可能跨过某个点去匹配，只能和自己相邻的点对齐。这样可以保证Q和C中的每个坐标都在W中出现。
3）单调性：如果 $w_k-1= (a’, b’)$ ，那么对于路径的下一个点 $w_k=(a, b)$ 需要满足 $0\leq (a-a’)$ 和 $0\leq (b-b’)$ 。这限制W上面的点必须是随着时间单调进行的。以保证图B中的虚线不会相交。