Dynamic Time Warping 动态时间规整算法

谁借莪１个温暖的怀抱￠ 2022-07-18 16:18 186阅读 0赞

Dynamic Time Warping（DTW）是一种衡量两个时间序列之间的相似度的方法，主要应用在语音识别领域来识别两段语音是否表示同一个单词。

1. DTW方法原理

在时间序列中，需要比较相似性的两段时间序列的长度可能并不相等，在语音识别领域表现为不同人的语速不同。而且同一个单词内的不同音素的发音速度也不同，比如有的人会把“A”这个音拖得很长，或者把“i”发的很短。另外，不同时间序列可能仅仅存在时间轴上的位移，亦即在还原位移的情况下，两个时间序列是一致的。在这些复杂情况下，使用传统的欧几里得距离无法有效地求的两个时间序列之间的距离（或者相似性）。

DTW通过把时间序列进行延伸和缩短，来计算两个时间序列性之间的相似性：

![09143115-3b440c0e84f3417fb7f42e88428ec030.jpg][]

如上图所示，上下两条实线代表两个时间序列，时间序列之间的虚线代表两个时间序列之间的相似的点。DTW使用所有这些相似点之间的距离的和，称之为归整路径距离(Warp Path Distance)来衡量两个时间序列之间的相似性。

2. DTW计算方法：

令要计算相似度的两个时间序列为X和Y，长度分别为|X|和|Y|。

归整路径(Warp Path)

归整路径的形式为W=w1,w2,...,wK，其中Max(|X|,|Y|)<=K<=|X|+|Y|。

wk的形式为(i,j)，其中i表示的是X中的i坐标，j表示的是Y中的j坐标。

归整路径W必须从w1=(1,1)开始，到wK=(|X|,|Y|)结尾，以保证X和Y中的每个坐标都在W中出现。

另外，W中w(i,j)的i和j必须是单调增加的，以保证图1中的虚线不会相交，所谓单调增加是指：

![09144722-0cb3256b215447419f1d19c64255403d.jpg][]

最后要得到的归整路径是距离最短的一个归整路径：

![09145112-fc7dd7bb40ca4fb1b4597930f5486589.jpg][]

最后求得的归整路径距离为D(|X|,|Y|)，使用动态规划来进行求解：

![09145159-11a439ce088840818b5e314bf12d2ef4.jpg][]

上图为代价矩阵(Cost Matrix) D，D(i,j)表示长度为i和j的两个时间序列之间的归整路径距离。

3. DTW实现：

matlab代码：

![复制代码][copycode.gif]

function dist = dtw(t,r)
    n = size(t,1);
    m = size(r,1);
    % 帧匹配距离矩阵
    d = zeros(n,m);
    for i = 1:n
        for j = 1:m
            d(i,j) = sum((t(i,:)-r(j,:)).^2);
        end
    end
    % 累积距离矩阵
    D = ones(n,m) * realmax;
    D(1,1) = d(1,1);
    % 动态规划
    for i = 2:n
        for j = 1:m
            D1 = D(i-1,j);
            if j>1
                D2 = D(i-1,j-1);
            else
                D2 = realmax;
            end
            if j>2
                D3 = D(i-1,j-2);
            else
                D3 = realmax;
            end
            D(i,j) = d(i,j) + min([D1,D2,D3]);
        end
    end
    dist = D(n,m);

![复制代码][copycode.gif]

C++实现：

dtwrecoge.h

![ContractedBlock.gif][]

dtwrecoge.cpp

![ContractedBlock.gif][]

C++代码下载：[DTW算法.rar][DTW_.rar]

出处：[http://www.cnblogs.com/luxiaoxun/][http_www.cnblogs.com_luxiaoxun]

[09143115-3b440c0e84f3417fb7f42e88428ec030.jpg]: /images/20220718/a66c6090e47f436f8d7cf0fb48741c55.png
[09144722-0cb3256b215447419f1d19c64255403d.jpg]: /images/20220718/1e7fdf179dac40a6bf61b065a428e3d4.png
[09145112-fc7dd7bb40ca4fb1b4597930f5486589.jpg]: /images/20220718/dcd9d7c9aa514c4bacfcc9bb3117600c.png
[09145159-11a439ce088840818b5e314bf12d2ef4.jpg]: /images/20220718/306fe6bfaf9c4a09b0e90471af81a9a3.png
[copycode.gif]: /images/20220718/158bf688b02a49c4b6dc5132603799f3.png
[ContractedBlock.gif]: /images/20220718/37a3c6356a1b438584394a417f5d684a.png
[DTW_.rar]: http://files.cnblogs.com/luxiaoxun/DTW%E7%AE%97%E6%B3%95.rar
[http_www.cnblogs.com_luxiaoxun]: http://www.cnblogs.com/luxiaoxun/