DTW

Dynamic Time Warping是Vintsiuk于1968年提出的算法。

Taras Klymovych Vintsiuk，1939～2012，乌克兰科学家，毕业于Kyiv Polytechnic Institute。模式识别专家，语音识别领域的奠基人之一。

图1

如上图所示，因为语音信号具有相当大的随机性，即使同一个人在不同时刻发同一个音，也不可能具有完全的时间长度。而且同一个单词内的不同音素的发音速度也不同，比如有的人会把“A”这个音拖得很长，或者把“i”发的很短。在这些复杂情况下，使用传统的欧几里得距离，无法有效地求得两个时间序列之间的距离（或者相似性）。

回到上面的图。如果我们将两个序列中相关联的点，用上图中的虚线连接的话，就会发现这两个序列实际上是很相似的。

那么如何用数学的方式描述上述DTW算法的思想呢？

假设现在有一个标准的参考模板R，是一个M维的向量，即R={R(1),R(2)，⋯，R(M)}R={R(1),R(2)，⋯，R(M)}，每个分量可以是一个数或者是一个更小的向量。现在有一个才测试的模板T，是一个N维向量，即T={T(1),T(2)，⋯，T(N)}T={T(1),T(2)，⋯，T(N)}同样每个分量可以是一个数或者是一个更小的向量，注意M不一定等于N，但是每个分量的维数应该相同。

然后，将两个序列二维展开得到下图：

这样，两个序列中点与点之间的关联关系，就可以用这个二维矩阵W来表述。比如，可以用W(i,j)表示第1个序列中的第i个点和第2个序列中的第j个点相对应。所有这样的W(i,j)最终构成了上图中的曲线。这条曲线也被称作归整路径（Warp Path）。

显然，这个归整路径不是随意选择的，它需要满足以下几个约束：

1）边界条件：w1=(1,1)w1=(1,1)和wk=(m,n)wk=(m,n)。任何一种语音的发音快慢都有可能变化，但是其各部分的先后次序不可能改变，因此所选的路径必定是从左下角出发，在右上角结束。

2）连续性：如果wk−1=(a′,b′)wk−1=(a′,b′)，那么对于路径的下一个点wk=(a,b)wk=(a,b)需要满足(a−a′)≤1(a−a′)≤1和(b−b′)≤1(b−b′)≤1。也就是不可能跨过某个点去匹配，只能和自己相邻的点对齐。这样可以保证R和T中的每个坐标都在W中出现。

3）单调性：如果wk−1=(a′,b′)wk−1=(a′,b′)，那么对于路径的下一个点wk=(a,b)wk=(a,b)需要满足0≤(a−a′)0≤(a−a′)和0≤(b−b′)0≤(b−b′)。这限制W上面的点必须是随着时间单调进行的。以保证图1中的虚线不会相交。

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

归整路径实际上就是满足上述约束的所有路径中，cumulative distances最小的那条路径，即：

D(i,j)=Dist(i,j)+min(D(i−1,j),D(i,j−1),D(i−1,j−1)),D(1,1)=0D(i,j)=Dist(i,j)+min(D(i−1,j),D(i,j−1),D(i−1,j−1)),D(1,1)=0

这里的距离可以使用欧氏距离，也可以使用马氏距离。

DTW实例的具体计算过程可参见：

http://www.cnblogs.com/tornadomeet/archive/2012/03/23/2413363.html

从一个实例中学习DTW算法

从中可以看出，DTW实际上是一个动态规划问题。

更一般的，DTW也可用于计算两个离散的序列(不一定要与时间有关)的相似度。和《机器学习（二十二）》的EMD距离相比，DTW距离能够保持序列的形状信息。

除此之外，我们还可以增加别的约束：

全局路径窗口(Warping Window)：∣ϕx(s)−ϕy(s)∣≤r∣ϕx(s)−ϕy(s)∣≤r。比较好的匹配路径往往在对角线附近，所以我们可以只考虑在对角线附近的一个区域寻找合适路径(r就是这个区域的宽度);

斜率约束(Slope Constrain)：ϕx(m)−ϕx(n)ϕy(m)−ϕy(n)≤pϕx(m)−ϕx(n)ϕy(m)−ϕy(n)≤p和ϕy(m)−ϕy(n)ϕx(m)−ϕx(n)≤qϕy(m)−ϕy(n)ϕx(m)−ϕx(n)≤q，这个可以看做是局部的Warping Window，用于避免路径太过平缓或陡峭，导致短的序列匹配到太长的序列或者太长的序列匹配到太短的序列。

上图是两种常见的约束搜索空间的方法。

DTW的缺点：

1.运算量大；

2.识别性能过分依赖于端点检测；

3.太依赖于说话人的原来发音；

4.不能对样本作动态训练；

5.没有充分利用语音信号的时序动态特性；

DTW适合于特定人基元较小的场合，多用于孤立词识别；

参考：

http://blog.csdn.net/zouxy09/article/details/9140207

动态时间规整（DTW）

https://blog.csdn.net/raym0ndkwan/article/details/45614813

DTW动态时间规整

http://www.cnblogs.com/luxiaoxun/archive/2013/05/09/3069036.html

Dynamic Time Warping动态时间规整算法

https://zhuanlan.zhihu.com/p/39450321

时间序列的搜索

Spectrogram

Window function

Fourier transform研究的是整个时间域和频率域的关系。但实际的信号处理过程，不可能对无限长的信号进行测量和运算，而是取其有限的时间片段进行分析。做法是从信号中截取一个时间片段，然后用截取的信号时间片段进行周期延拓处理，得到虚拟的无限长的信号，然后就可以对信号进行FT、相关分析等数学处理。

无限长的信号被截断以后，其频谱发生了畸变，原来集中在f(0)处的能量被分散到两个较宽的频带中去了（这种现象称之为频谱能量泄漏）。

为了减少频谱能量泄漏，可采用不同的截取函数对信号进行截断，这些截断函数称为Window function。

常用的Window function有：Hann window、Rectangular window、Triangular window、Hamming window、Gaussian window等。

不同的窗函数对信号频谱的影响是不一样的。例如，Rectangular window主瓣窄，旁瓣大，频率识别精度最高，幅值识别精度最低；Blackman window主瓣宽，旁瓣小，频率识别精度最低，但幅值识别精度最高。

对Window function更详细的叙述参见：

https://en.wikipedia.org/wiki/Window_function

Hann window

Hann window虽然是以Julius Ferdinand von Hann的名字命名，但却是Blackman和Tukey的作品。他们和同一实验室的Claude E. Shannon, Hendrik Wade Bode，合称为Information Age的四大先锋。

Julius Ferdinand von Hann，1839～1921，奥地利气象学家。现代气象学之父。

Ralph Beebe Blackman，1904～1990，美国数学家。长期供职于AT&T Bell Laboratories。二战时，参与了防空火炮控制系统的平滑研究。

John Wilder Tukey，1915～2000，美国数学家。Princeton University博士，长期供职于AT&T Bell Laboratories。英国皇家学会会员。Cooley–Tukey FFT算法发明者。

w(n)=∑k=0K(−1)kakcos(2πknN−1),0≤n≤N−1w(n)=∑k=0K(−1)kakcos⁡(2πknN−1),0≤n≤N−1

上式是Cosine-sum windows的计算公式，令K=1，则：

w(n)=a0−(1−a0)a1⋅cos(2πnN−1),0≤n≤N−1w(n)=a0−(1−a0)⏟a1⋅cos⁡(2πnN−1),0≤n≤N−1

这类Window function有好几个特例：

Hann window：

w(n)=0.5[1−cos(2πnN−1)]=sin2(πnN−1)w(n)=0.5[1−cos⁡(2πnN−1)]=sin2⁡(πnN−1)

Hamming window：

w(n)=0.54−0.46⋅cos(2πnN−1)w(n)=0.54−0.46⋅cos⁡(2πnN−1)

Richard Wesley Hamming，1915～1998，美国数学家。University of Chicago本科（1937）+University of Nebraska硕士（1939）+UIUC博士（1942）。参与曼哈顿计划，后长期供职于Bell Lab。通信和计算机工程领域的宗师级人物，美国工程院院士，图灵奖得主（1968）。Hamming code 、Hamming distance等都是他的贡献。

STFT

STFT{x(t)}(τ,ω)≡X(τ,ω)=∫∞−∞x(t)w(t−τ)e−jωtdtSTFT{x(t)}(τ,ω)≡X(τ,ω)=∫−∞∞x(t)w(t−τ)e−jωtdt

上式是STFT（Short-time Fourier transform）的定义。和FT相比，STFT将FT中的被积函数x(t)x(t)，换成了x(t)w(t−τ)x(t)w(t−τ)。其中，w(t)是窗函数（Window function），因此STFT又叫做加窗傅立叶变换。

Spectrogram

DTW是一种时域方法，作为信号处理自然少不了频域方法。这里我们先来了解一个叫声谱图的东西。

这段语音被分为很多帧，每帧语音都对应于一个频谱（通过短时FFT计算），频谱表示频率与能量的关系。在实际使用中，频谱图有三种，即线性振幅谱、对数振幅谱、自功率谱（对数振幅谱中各谱线的振幅都作了对数计算，所以其纵坐标的单位是dB（分贝）。这个变换的目的是使那些振幅较低的成分相对高振幅成分得以拉高，以便观察掩盖在低幅噪声中的周期信号）。

我们先将其中一帧语音的频谱通过坐标表示出来。

再将左边的频谱旋转90度。

然后把这些幅度映射到一个灰度级表示的直方图。0表示白色，255表示黑色。幅度值越大，相应的区域越黑。

这样我们会得到一个随着时间变化的频谱图，这个就是描述语音信号的spectrogram声谱图。

Cepstrum Analysis

上图是一个语音的频谱图。峰值就表示语音的主要频率成分，我们把这些峰值称为共振峰（formants），而共振峰就是携带了声音的辨识属性（就是个人身份证一样）。所以它特别重要。用它就可以识别不同的声音。

既然它那么重要，那我们就是需要把它提取出来！我们要提取的不仅仅是共振峰的位置，还得提取它们转变的过程。所以我们提取的是频谱的包络（Spectral Envelope）。这包络就是一条连接这些共振峰点的平滑曲线。

原始的频谱由两部分组成：包络和频谱的细节。这里用到的是对数频谱，所以单位是dB。

怎么把他们分离开呢？也就是，怎么在给定logX[k]log⁡X[k]的基础上，求得logH[k]log⁡H[k]和logE[k]log⁡E[k]以满足logX[k]=logH[k]+logE[k]log⁡X[k]=log⁡H[k]+log⁡E[k]呢？

为了达到这个目标，我们需要Play a Mathematical Trick。这个Trick是什么呢？就是对频谱做FFT。