Investigate the use of Dynamic Time Warping

[vvasco]

The Dynamic Time Warping (DTW) technique is commonly used in action recognition systems for synchronizing two temporal sequences (typically a template action and the performed action).
Some references may be found here:

• [Reyes et al., 2011], Feature Weighting in Dynamic Time Warping for Gesture Recognition in Depth Data, International Conference on Computer Vision Workshops
• [Sempena et al. 2011], Human Action Recognition Using Dynamic Time Warping, International Conference on Electrical Engineering and Informatics

We want to investigate the use of DTW in our framework to provide feedback on the quality of the performed movement (#71, #72).
Open libraries:
https://github.com/lemire/lbimproved
https://github.com/nickgillian/grt/wiki

[vvasco]

The classical DTW requires that the template and the test timeseries are fully known (the starting and the ending point must be known, but not necessarily equal).
This is an example of how DTW works when having a full template and noisy test time series. The cost matrix is also shown, with the blue part indicating the optimal path used to align the two time series.

The alignment works very well and we might use classical DTW to provide a real-time feedback after the exercise is finished (and marked as finished).

However, during the exercise, we do not have the full test sequence a-priori (instead, we might have the full template). Therefore, if we want to provide real-time feedback during the exercise, a variant of DTW has to be used:

• The open-begin-end DTW (OBE-DTW) allows for open-begin and open-end matches.
  A R package is available here: https://github.com/cran/dtw.
  http://dirk.eddelbuettel.com/code/rcpp.html might also be useful to interface R and C++.

• The online DTW (oDTW) aligns the time series incrementally (only the template sequence must be known in its entirety).
  The C++ library is available here: https://github.com/RVirmoors/RVdtw-/tree/master/oDTW

[vvasco]

Given we know the duration of the exercise (D) and the number of repetitions (nrep) of a movement, we can evaluate the signals every n*(D/nrep) seconds, in order to have a template containing n repetitions of the movement, with defined starting and ending points.
The DTW distance (normalized by the length of the vector) between segmented template and test is an indicator of how well the movement is being performed, in terms of speed. If the normalized DTW distance is below a threshold, we can assume template and test are mostly synchronized (i.e. they move at the same speed). Otherwise, a difference in speed can be detected.

The expected situations are described below. The examples show the 1D case for simplicity, considering the x position of the hand during an abduction exercise. However, this analysis has to be extended to the whole skeleton, using the multivariate DTW.
In the following examples, the full signals are shown and segmented signals (template is segmented in order to have n = 4 repetitions of the movement) with the corresponding DTW distance.
DTW distance is typically lower when template and test move at same speed.

• Template and test moving at same speed:

DTW dist = 0.078	DTW dist = 0.081

• Test moving slower than the template:

DTW dist = 0.10	DTW dist = 0.11

• Test moving faster than the template:

DTW dist = 0.10	DTW dist = 0.12

• Test moving randomly / not moving:

DTW dist = 0.36	DTW dist = 0.51

[vvasco]

The same analysis was repeated by considering all the joints (the z component was not used, since, at the moment, it is not reliable (#76, #77)). The multivariate DTW was used, by computing the cost matrix for each x and y component of each joint, and the sum of each DTW distance was considered as final distance.
The table below summarizes the results. Each row reports the DTW distance for different parts of the template and test signals.
As desired, DTW distance is typically lower when template and test move at same speed.

Same speed	Slower test	Faster test	Not moving / randomly moving test
DTW dist = 0.40	0.62	0.61	3.44
DTW dist = 0.48	0.65	0.70	4.31
DTW dist = 0.46	0.63	0.68	4.17
DTW dist = 0.45	0.68	0.69	4.01

[pattacini]

That's super cool @vvasco!
Thus, DTW seems to be the tool we were seeking for!