Email chain of correspondence with Pascal

  • 3 minutes read

Original email subject

Gesture Recognition in RGB Videos Using Human Body Keypoints and Dynamic Time Warping

Go back to the supporting page for FastDTW is approximate and Generally Slower than the Algorithm it Approximates.

Eamonn on Feb. 29, 2020, 15:54

Hello.

I am writing to you because you wrote a recent paper that use FastDTW.

I would like to ask you a favor.

I believe that FastDTW is in error, that simple DTW is actually MUCH faster, and exact.

In order to establish my credibility here, we me mention:

1) I recently did DTW 61,041,100,000,000 times for a paper.

2) I have published 40+ papers on DTW.

Can we ask you to rerun your experiments, but using simple cDTW code instead, and tell us if you agree it is really faster?

This would really help the community.

If you are willing to do this, Renjie will send you the code (Java, Matlab, C++ etc)

Many thanks

Eamonn

[a] https://www.cs.ucr.edu/~eamonn/time_series_data_2018/

“Another topic of research is how this method can be sped up, desirably up to the point where it reaches real-time capability”

What you are doing can be done a ten thousand times faster than real time for over a decade. Look at at this video. It is 8 years old, but does DTW 30,000 time faster than real time https://www.youtube.com/watch?time_continue=5&v=d_qLzMMuVQg&feature=emb_logo

Pascal on Mar. 5, 2020, 01:39

Dear Mr. Keogh,

thank you for reaching out to us. I’d be glad to help you with your research and endeavors to speed up DTW. Simply send the code to me and I will report my results back to you. I can’t tell you exactly when I will find the time to do this, though, I hope you understand.

By the way, our remarks on the yet lacking real-time capability were mostly referring to OpenPose, which accounted for the majority of the computational cost in our experiments.

Kind regards

Pascal Schneider

Eamonn on Mar. 5, 2020, 09:43

Hi Pascal.

What language do you perfer?

eamonn

Pascal on Mar. 6, 2020, 01:22

Hello,

Python would be ideal, but C++ would also work for me.

Kind regards,

Pascal Schneider

Renjie on Mar. 6, 2020, 22:05

Hi Pascal,

Please check the attached file for the python cDTW implementation.

The function signature is

dtwupd(a, b, r)

where a and b is the data and query respectively and r is the size of Sakoe-Chiba warping band.

As warp window size w = r / N, where N is the length of the time series, so assume the length of time series is 1024 and you want to set w to 10%, then r to be passed into dtwupd should be ceil(N * w) = ceil(1024 * 10%) = 103.

Thanks,
Renjie

Attachment

Pascal on Mar. 10, 2020, 09:20

Hello Eamonn, hello Renjie,

I reran the main experiment from our paper with the newest released version of the “fastdtw” package for Python (version 0.3.4) as well as with the implementation you provided me (using radius=30 for both).

  • Using FastDTW reproduced the same results we originally published (77.38% of gestures correctly classified)
  • Using your version improved the results of our classifier by about 5% (82.14% of gestures correctly classified)

I also compared the runtime of the two DTW implementations during the experiment. I ran the whole experiment twice, which amounts to a total of 2 x 5.851 = 11.702 runs of each DTW implementation for which I compared the runtimes.

Result:

  • your implementation was approx. 24x faster than FastDTW on average (mean: 23.7059, std: 3.587)
  • in the “slowest” case, your implementation was still approx. 5.8x faster than FastDTW

I’d conclude that these tests suggest that your implementation is indeed superior in terms of speed as well as for usage in time-series classification.

I attached the data for the speed-ups I measured, just in case you have a use for it.

Let me know if I can help you any further.

Regards,
Pascal Schneider

Attachments

Eamonn on Mar. 10, 2020, 09:58

Hi Pascal. Many thanks, this is very helpful

eamonn