Java DTW

Attached is test code that calculates the DTW score between two signals. Each signal needs to be an ArrayList of arrays, where the array is a length 3 array of doubles. Said another way, each sample (double integrated) x,y,z gets put into an array of length 3 and then added to an ArrayList. The code looks ugly from the test arrays I loaded. Those two signals are Jin's first two exercise #1 examples. My code produces exactly the same output as MATLAB.

All you should need to do is rip out the pathcompare class.

This code doesn't double integrate. I'm working on that now, but in the spirit of releasing often...

Code

DTW not as sensitive to phone alignment

The above image is an interesting result. It shows the histogram of DTW scores for Jin-Andrew (blue) and Jin-Scott (red). Here we see that indeed the red histogram has higher scores, but not significantly. The mode is shifted by about 1000 and the bins above the mode do have more scores. Regardless, this implies that the orientation (at least for an offset of this small amount) translates into a fixed offset that is much smaller than the overall DTW cost.

50 examples for 4 excercises on 3 people

Download full data set so far here

Machine learning rocks!

Quite a weekend of work for Jin...

The HMM will be good since we can use the log-likelyhood as a scoring method similar to the path cost on the DTW. Also, your setup of the 27-way transitions is clever and will make for good report material.

As far as smoothing goes... we can use a low-pass filter and then calculate the difference, which is what Jin's first idea is.

My other idea is something along the lines of:

0. Perhaps normalize the length of the sequence (I need to think about this step more, could probably use the DTW to warp all of the sequences of an action to a common length)
1. Take a DFT or DCT of the sequences.
2. Average the DCTs together and normalize
3. Find the peak (mode) of the averaged DFT
4. Find the ratio of energy above and below the mode.
5. Perform the same math on a exercise example and compare the energy above the mode.

Another idea:

Use a more and more severe smoothing filter until the DTW scores changes drastically (say 20%?) (or the HMM log-likely hood). Then do the comparison as Jin suggested.

Following up on Jin's posts

While I agree with Jin that we may need more than one metric, we need to be careful about just throwing ad-hoc measures up without justification. DTW on the path makes sense because it compares the similarity of the overall action.

Some sort of statistical measure of acceleration or velocity might also be good, but we need to think about why/what. Some sort of smoothness measure would probably be good. We could take a normalized FFT of the gesture and compare the amount of energy above the mean (or perhaps median or mode).

Here is what I would propose:

1. DTW (lower is better score)
2. 1-(HMM probability)
3. "Smoothness" metric

We don't want to propose too many or make the score an amalgamation of too many pieces until we know which scoring methods correlate to good/bad motion (which in the scope of this semester, we will never know since we can't work with stroke patients.) What we do want to do is propose a good set of plausible metrics that can be implemented on the phone by the end of the month.

Jin just posted his results regarding the HMM... so here are some suggestions:

Create some synthetic motion traces that have motion only in one direction, x, y or z. See if your code can learn those motions.

Use a MATLAB HMM library for now to see if you can get better results.

Train on the path data (double integrated acceleration data). If it performs best in DTW it likely means there are unique features in the data stream that an HMM might pick up on.

Try creating an alternate feature stream by using a windowed FFT with some overlap. Performing this FFT across the acceleration data will give a sequence of FFTs that can be fed to the HMM. This is similar to what speech recognizers do for HMM speech recognition.

Hello Histogram!

I used the 3D DTW algorithm on the double-integrated path data. Above is the histogram result. Hello separation! Task 1 and task 2 separate their scores by about 40,000. Task 1 and 3 over lap some, but overall the tight grouping for task 1 to task 1 comparisons and the good separation mean that this method should give very good similarity scores.

Edit: the MATLAB code to play around with this is here

Eaiser way to calculate 3D paths

If you have a as your time series acceleration data, then just do:

>>v = cumtrapz(a);
>>p = cumtrapz(p);

This works because velocity is the integral of acceleration and position is the integral of velocity. Now you have v = velocity series and p = position series.