DTW算法原理分析与源码

end

dist = D(n,m);

程序中，首先申请两个n×m的距阵D和d，分别为累积距离和帧匹配距离。这里n和m为测试模板与参考模板的帧数。然后通过一个循环计算两个模板的帧匹配距离距阵d。接下来进行动态规划，为每个格点（i，j）都计算其三个可能的前续格点的累积距离D1、D2和D3。考虑到边界问题，有些前续格点可能不存在，因此要加入一些判断条件。

最后利用最小值函数min，找到三个前续格点的累积距离的最小值作为累积距离，与当前帧的匹配距离d（i，j）相加，作为当前格点的累积距离。该计算过程一直达到格点（n，m），并将D（n，m）输出，作为模板匹配的结果。

3.2 DTW的高效算法

由于匹配过程中限定了弯折的斜率，因此许多格点实际上是到达不了的，如图3-1所示。因此菱形之外的格点对应的帧匹配距离是不需要计算的。另外也没有必要、保存所有的帧匹配距离距阵和累积距阵，因为每一列各格点上的匹配计算只用到了前一列的三个网格。充分利用这两个特点可以减少计算量和储存空间的需要。

如图3-1所示，把实际的动态弯折分为三段，（1，Xa），（Xa+1，Xb）和（Xb+1，N），其中：

图3-1 匹配路径约束示意图

Xa和Xb都取相近的整数。由此也得出对M和N长度的限制条件： 当不满足以上条件时，认为两者差别实在太大，无法进行动态弯折匹配。

在X轴上的每一帧不再需要与Y轴上的每一帧进行比较，而只是与Y轴上[y ，y ]间的帧进行比较，y 和y 的计算如下式：

也可能会出现Xa>Xb的情况，此时弯折匹配的三段为（1，Xb），（Xb+1，Xa）和（Xa+1，N）。

对于X轴上每前进一帧，虽然所要比较Y轴上的帧数不同，但弯折特性是一样的，累积距离的更新都是用下式实现的：

由于X轴上每前进一帧，只需要用到前一列的累积距离距阵。每前进一帧都进行更新，即按上式利用前一列的累积距离D和当前列的所有帧匹配的距离d（x，y），求出当前帧的累积距离，保存于矢量d中，再把更新的距离d赋值给D，作为新的累积距离，供下一列使用。如图3-2所示。这样一直前进到X轴上最后一列，矢量D的第M个元素即为两个模板动态弯折的匹配距离。

图3-2 累积距离矢量的动态更新

用这种方法实现的另一种DTW算法的代码如下： function dist = dtw(test, ref) global x y_min y_max global t r global D d global m n t = test; r = ref; n = size(t,1); m = size(r,1); d = zeros(m,1);

D = ones(m,1) * realmax; D(1) = 0;

% 如果两个模板长度相差过多，匹配失败 if (2*m-n<3) | (2*n-m<2) dist = realmax; return end

% 计算匹配区域 xa = round((2*m-n)/3); xb = round((2*n-m)*2/3); if xb>xa

%xb>xa, 按下面三个区域匹配

% 1 :xa % xa+1:xb % xb+1:N for x = 1:xa y_max = 2*x; y_min = round(0.5*x); warp end

for x = (xa+1):xb

y_max = round(0.5*(x-n)+m); y_min = round(0.5*x); warp end

for x = (xb+1):n

y_max = round(0.5*(x-n)+m); y_min = round(2*(x-n)+m); warp end elseif xa>xb

%xa>xb, 按下面三个区域匹配 % 0 :xb % xb+1:xa % xa+1:N

for x = 1:xb y_max = 2*x; y_min = round(0.5*x); warp end

for x = (xb+1):xa y_max = 2*x;

y_min = round(2*(x-n)+m); warp end

for x = (xa+1):n

y_max = round(0.5*(x-n)+m); y_min = round(2*(x-n)+m); warp end elseif xa==xb

%xa=xb, 按下面两个区域匹配 % 0 :xa % xa+1:N for x = 1:xa y_max = 2*x; y_min = round(0.5*x); warp