Dynamic Time Warping

[Dustin Bruening]

Hi all, I wonder if anyone is familiar with using dynamic time warping (DTW) and might have some insights into how to implement it. I am specifically looking at using it in place of time normalization - for example, for a data set consisting of 10 subjects' knee joint angles during gait - each subject's curve would typically be time normalized to 100% of stance, after which a mean at each point would be taken to represent the group. This works fairly well most of the time, especially in gait, but in some applications, peaks and transitions can be offset between subjects so that the mean dilutes these peaks. DTW "warps" each curve, rather than simply stretching or compressing them, so that the peaks are mostly lined up. This seems like a good thing to adopt in biomechanics applications, but I have yet to see any ready made implementations that I could easily adapt to specific data sets. Matlab has a dtw function which appears to work well on two curves, but I'm not sure how to convert it to apply to more than two. In addition, comments on pros and cons of dtw for biomechanics applications would also be welcome, as well as comments on how well it would be accepted in publications, particularly as whole waveform analysis (e.g. functional data analysis or statistical parametric mapping) becomes more common.

[Todd Pataky]

Re: Dynamic Time Warping

Hi Dustin, thank you for raising this topic! There have been quite a few papers published regarding DTW, but I completely agree that there aren't very many general-use software tools out there.

The closest candidate I know of is the Insight Toolkit (ITK) and in particular its registration framework:

https://itk.org/Doxygen/html/RegistrationPage.html

ITK is used mainly for 2D and 3D image processing, but it can also be applied to 1D data. Here is a brief discussion regarding how DTW can be accomplished using ITK registration algorithms:

http://itk-users.7.n7.nabble.com/1D-deformable-registration-td7244.html

If there are clearly discernible landmarks like local minima / maxima, a somewhat easier option might be to implement piecewise linear registration, wherein homologous points P1, P2, ... PN are manually or algorithmically defined in all curves. Then sequential linear interpolations of the P1-P2, P2-P3, ... P(N-1)-PN segments will achieve a similar result to nonlinear DTW. Here's a relevant discussion in a MATLAB forum:

http://blogs.mathworks.com/loren/2008/08/25/piecewise-linear-interpolation/

Todd

[John Harry]

Re: Dynamic Time Warping

Hi All,

Here is another resource (with Matlab code examples) for Dynamic Time Warp. This example is specific to speech, but I have had discussions with a colleague of mine in computer engineering about the potential of DWT in human movement analyses.

http://www.ee.columbia.edu/ln/rosa/matlab/dtw/

[Morgan Sangeux]

Re: Dynamic Time Warping

Hi Dustin,

You may also be interested in the techniques developed to register (including time warping) curve data within the functional data analysis framework. Some of these are introduced in these lecture notes or these other ones. Then, if you are interested in functional data analysis, software in Matlab and R is available here, and a general purpose book is also available.

Good luck,

[Dustin Bruening]

Re: Dynamic Time Warping

I appreciate all the responses. I've seen some of these before, but thought on first glance that they required more effort to implement than I was willing to give them .

I was not familiar with the ITK toolkit. I was originally hoping for something I had a lot of control over – like some Matlab functions – but maybe I should look into this a bit more.

John, the speech example looks to be still a 2 curve warping example – I think maybe what the dtw function might be based on. I think I just learned something, however, from looking at that more. Someone can correct me if I am wrong. It looks like there is a method to grab the average of multiple curves, called DTWbarycenter averaging (or DBA). Then each curve gets time warped to that average using the dtw function. I think… so says Wikipedia. If so, that sounds easily doable in Matlab. DBA matlab code is at: https://github.com/fpetitjean/DBA/blob/master/DBA.m

I had seen the functional data analysis stuff from Jim Ramsay before, but it always seemed intimidating. I think that may very well be a good route to go if I can get in and understand it a bit better. Thank you also for the lecture notes, they are helpful.

It also sounds like there is a lot more available in R on this topic as well (if only I knew R).

I do hope that both curve registration and statistical waveform comparisons can get used more in biomechanics (separately and together). There is potentially a lot more information that can be conveyed. I’d encourage those who have used it successfully to help simplify it for those who would like to use it but are slightly intimidated.

Thanks,
-Dustin