Email chain of correspondence with Pascal
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
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)
“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.
Eamonn on Mar. 5, 2020, 09:43
What language do you perfer?
Pascal on Mar. 6, 2020, 01:22
Python would be ideal, but C++ would also work for me.
Renjie on Mar. 6, 2020, 22:05
Please check the attached file for the python cDTW implementation.
The function signature is
dtwupd(a, b, r)
where and is the data and query respectively and is the size of Sakoe-Chiba warping band.
As warp window size w = / 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 to be passed into should be ceil(N * w) = ceil(1024 * 10%) = 103.
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.
- 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.
Eamonn on Mar. 10, 2020, 09:58
Hi Pascal. Many thanks, this is very helpful