computes path through a distance matrix with simple Dynamic Time > Warping > > @param D: distance matrix > > @retval p path with matrix indices > @retval C cost matrix ======================================================================
0001 %computes path through a distance matrix with simple Dynamic Time 0002 %> Warping 0003 %> 0004 %> @param D: distance matrix 0005 %> 0006 %> @retval p path with matrix indices 0007 %> @retval C cost matrix 0008 % ====================================================================== 0009 function [p, C] = ToolSimpleDtw(D) 0010 0011 % cost initialization 0012 C = zeros(size(D)); 0013 C(1, :) = cumsum(D(1, :)); 0014 C(:, 1) = cumsum(D(:, 1)); 0015 0016 % traceback initialization 0017 DeltaP = zeros(size(D)); 0018 DeltaP(1, 2:end) = 3; % (0,-1) 0019 DeltaP(2:end, 1) = 2; % (-1,0) 0020 0021 % init directions for back-tracking [diag, vert, hori] 0022 iDec = [-1 -1; -1 0; 0 -1]; 0023 0024 % recursion 0025 for n_A = 2:size(D, 1) 0026 for n_B = 2:size(D, 2) 0027 % find preceding min (diag, column, row) 0028 [fC_min, DeltaP(n_A, n_B)] = min([C(n_A-1, n_B-1), ... 0029 C(n_A-1, n_B), ... 0030 C(n_A, n_B-1)]); 0031 C(n_A, n_B) = D(n_A, n_B) + fC_min; 0032 end 0033 end 0034 0035 % traceback 0036 p = size(D); % start with the last element 0037 n = [size(D, 1), size(D, 2)]; %[n_A, n_B]; 0038 while ((n(1) > 1) || (n(2) > 1)) 0039 n = n + iDec(DeltaP(n(1),n(2)), :); 0040 0041 % update path (final length unknown) 0042 p = [n; p]; 0043 end 0044 end