一、概述
在时间序列中，需要比较相似性的两段时间序列的长度可能并不相等，在语音识别领域表现为不同人的语速不同。在这些复杂情况下，使用传统的欧几里得距离无法有效求解两个时间序列之间的距离，即相识度。
大部分情况下，两个序列整体上具有非常相似的形状，但是这些形状在x轴上并不是对齐的。DTW的思想是把两个时间序列进行延伸和缩短，来得到两个时间序列性距离最短也就是最相似的那一个warping，这个最短的距离也就是这两个时间序列的最后的距离度量。
Warping正确性判定：直观上理解，当然是warping一个序列后可以与另一个序列重合recover。这个时候两个序列中所有对应点的距离之和是最小的。warping的正确性一般指“feature to feature”对齐，即特征对齐。
二、动态时间规整DTW
DTW是用满足一定条件的时间规整函数W(n)描述测试模板和参考模板的时间对应关系，求解两模板匹配时累计距离最小所对应的规整函数。
假设我们有两个时间序列Q和C，他们的长度分别是n和m：序列中的每个点的值为语音序列中每一帧的特征值（实际语音匹配运用中，一个序列为参考模板，一个序列为测试模板）。
Warping通常采用动态规划算法。为了对齐这两个序列，我们需要构造一个n x m的矩阵网格，矩阵元素(i, j)表示qi和cj两个点的距离d(qi, cj)（也就是序列Q的每一个点和C的每一个点之间的相似度，距离越小则相似度越高。这里先不管顺序），一般采用欧式距离，d(qi, cj)= (qi-cj)2（也可以理解为失真度）。每一个矩阵元素(i, j)表示点qi和cj的对齐。DP算法可以归结为寻找一条通过此网格中若干格点的路径，路径通过的格点即为两个序列进行计算的对齐的点。
我们把这条路径定义为Warping Path规整路径，并用W来表示， W的第k个元素定义为wk=(i,j)k，定义了序列Q和C的映射。这样我们有：
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)。我们的目的是使得下面的规整代价最小的路径：
分母中的K主要是用来对不同的长度的规整路径做补偿。
这里我们定义一个累加距离(cumulative distances)。从(0, 0)点开始匹配这两个序列Q和C，每到一个点，之前所有的点计算的距离都会累加。到达终点(n, m)后，这个累积距离就是我们上面说的最后的总的距离，也就是序列Q和C的相似度。
累积距离γ(i,j)可以按下面的方式表示，累积距离γ(i,j)为当前格点距离d(i,j)，也就是点qi和cj的欧式距离（相似性）与可以到达该点的最小的邻近元素的累积距离之和：
最佳路径是使得沿路径的积累距离达到最小值这条路径。这条路径可以通过动态规划(dynamic programming)算法得到。
三、DTW在语音中的运用
假定一个孤立字（词）语音识别系统，利用模板匹配法进行识别。这时一般是把整个单词作为识别单元。在训练阶段，用户将词汇表中的每一个单词说一遍，提取特征后作为一个模板，存入模板库。在识别阶段，对一个新来的需要识别的词，也同样提取特征，然后采用DTW算法和模板库中的每一个模板进行匹配，计算距离。求出最短距离也就是最相似的那个就是识别出来的字了。
动态规划求解相似度示例：
假设标准模板R为字母ABCDEF(6个)，测试模板T为1234(4个)。R和T中各元素之间的距离已经给出。如下：
题目要计算出测试模板T和标准模板R之间的距离。因为2个模板的长度不同，所以其对应匹配的关系有很多种，我们需要找出其中距离最短的那条匹配路径。现假设题目满足如下的约束：当从一个方格((i-1,j-1)或者(i-1,j)或者(i,j-1))中到下一个方格(i,j)，如果是横着或者竖着的话其距离为d(i,j)，如果是斜着对角线过来的则是2d(i,j)。则得到如下dp公式：
此题采用自底向上的动态规划求解即可，如果想输出相应路径，通过回溯即可。
代码实现如下：
#include <iostream>
using namespace std;
const int MAXN = 999999;
const int col = 4;
const int row = 6;
char R[] = {'A', 'B', 'C', 'D', 'E', 'F'};
int T[] = {1, 2, 3, 4};
void print(int dp[][col + 1]) {
for (int i = 1; i <= 6; ++i) {
for (int j = 1; j <= 4; ++j) {
cout << dp[i][j] << "\t";
}
cout << endl;
}
}
void printPath(int d[][col], int dp[][col + 1], int i, int j) {
if (i == 1 && j == 1) {
cout << R[i - 1] << " - " << T[j - 1] << endl;
return;
}
if (dp[i][j] == dp[i - 1][j - 1] + 2 * d[i - 1][j - 1]) {
printPath(d, dp, i - 1, j - 1);
} else if (dp[i][j] == dp[i][j - 1] + d[i - 1][j - 1]) {
printPath(d, dp, i, j - 1);
} else {
printPath(d, dp, i - 1, j);
}
cout << R[i - 1] << " - " << T[j - 1] << endl;
}
int boundaryJudge(int d[][col], int dp[][col + 1], int i, int j) {
int exp = MAXN;
if (i - 1 == 0 && j - 1 == 0) {
//起始点
dp[i][j] = 2 * d[i - 1][j - 1];
} else if (dp[i - 1][j] == MAXN) {
//位于第一行
dp[i][j] = dp[i - 1][j - 1] + 2 * d[i - 1][j - 1];
exp = dp[i][j - 1] + d[i - 1][j - 1];
} else if (dp[i][j - 1] == MAXN) {
//位于第一列
dp[i][j] = dp[i - 1][j - 1] + 2 * d[i - 1][j - 1];
exp = dp[i - 1][j] + d[i - 1][j - 1];
} else {
dp[i][j] = dp[i - 1][j - 1] + 2 * d[i - 1][j - 1];
exp = (dp[i][j - 1] > dp[i - 1][j] ? dp[i - 1][j] : dp[i][j - 1]) + d[i - 1][j - 1];
}
return exp;
}
/**
* dp[i][j] = min{ dp[i-1][j-1] + 2d[i][j]; dp[i][j] = dp[i-1][j] + d[i][j]; dp[i][j] = dp[i][j-1] + d[i][j] }
*/
void match(int d[][col], int dp[][col + 1]) {
for (int i = 0; i <= 6; ++i) {
dp[i][0] = MAXN;
}
for (int i = 0; i <= 4; ++i) {
dp[0][i] = MAXN;
}
for (int i = 1; i <= 6; ++i) {
for (int j = 1; j <= 4; ++j) {
int exp = boundaryJudge(d, dp, i, j);
if (exp < dp[i][j]) {
dp[i][j] = exp;
}
}
}
}
int main(int argc, char const *argv[]) {
int dp[row + 1][col + 1];
int d[row][col] = {{2, 1, 5, 1},
{3, 4, 8, 2},
{5, 2, 4, 3},
{4, 7, 2, 4},
{1, 5, 1, 6},
{2, 1, 7, 5}};
match(d, dp);
cout << "相似度为：" << dp[row][col] << endl;
printPath(d, dp, row, col);
return 0;
}
过几天会分享一个利用DTW做的一个孤立词识别的语音识别入门程序。
