Presentation outline (maybe for report/paper too?)

#1: Hook (X stroke rate, Y death rate. Obviously rehab is important)

#2: Need (Current method relies on time only. Can we do better [qualitative]?)
#2a: show video of select exercises

#3: Approach
#3a: Use classification algorithms, but choose such that they give similarity scores
#3b: Obvious choices: DTW (cost) and HMM (log likelyhood). Others: ANN, decision tree: no score just classify. Naive Bayes: might work (probability)
#3c: This is basically gesture recognition
#3c-1: Problems: usually related to orientation and speed/amplitude
#3d: But we're solving a different problem because
#3d-1: We know the action a-priori, the amplitude is fixed (you have to perform the action as specified in the test) and we can still use time.
#3e: So this lets us work with the path data not just the acceleration
#3f: DTW on the path
#3g: HMM on the path - novel state space
#3g-1: and most importantly we can fix the orientation

#4: Implementation details
#4a: application
#4b: remote control
#4c: algorithms implemented on phone: DTW and HMM (log-likelyhood)
#4c-1: and 'energy' (current method used)

#5: Results
#5a: similar actions = similar scores
#5b: Show DTW and HMM graphs
#5c: Experiments with weights and 'poor motion'
#5d: W/ weights, not conclusion, with 'poor motion' pretty good results
#5d-1: Energy is inconclusive even for 'poor motion'
#5e: Ex. #5 added after other work to show the method wasn't tuned to ex. 1-4
#5f: 'High-box' tested to look at similar actions. Scores are similar, but we're not classifying, similar actions get similar scores.

#6: Conclusion Future work
#6a: We do a more quantitative measurement of the actions similarity
#6a-1: On an easy to use, inexpensive system (with remote control)
#6b: But our experiment is a bit un-scientific
#6c: So future directions are:
#6c-1: Can existing kinematic captures of patients be used to test our system
#6c-2: And of course if we could test it on a few actual patients.

Graphs

I think I've got most of my graphs made. See here.

Also, the gist of the data collected is that purposely screwing up the motion to emulate a patient causes a large increase in the score. This is good. It doesn't always increase the energy. This is also good since energy is sort of the current measure used, we can say we're better.

Jin: can you make some 3D plots of the paths for some of our 'poor motion' examples?

Otherwise I think we're good.

Data from today

Both the raw data, and the split up data is here

Energy results

The energy results are not very encouraging. Exercise #1 seems to be the most effected. Again, it is hard to know how relevant to a stroke patient these results are.

Normal:
Ex: Energy
--------------
1 168.53
2 66.442
3 94.084
4 483.74

Weighted:
Ex: Energy
--------------
1 221.3
2 57.46
3 56.263
4 205.54

DTW results from weighted test

While not a homerun, the results are interesting, see below. The take-away from all of this is that the weights probably changed our motion in a way the DTW algorithm could detect, but the result is not consistent.

So for exercises #1 and #4, the DTW score is lower for the unweighted. Unfortunately, for the others it is higher. However, for both of those exercises the major motion is lifting of the arm, so perhaps the weights matter more there. Also, we don't know how good of an analogue the weights are, so keep that in mind.

Ex. Avg. Normal Avg. With Weights
------------------------------------
1 2079.35  4877.96
2 5925.08  3834.49
3 20313.27  17464.42
4 15911.03  18382.09

Also, it depends on the person:

Andrew

Ex. With Weights (min,mean,max,(stdev))
---------------------
1 1654.56, 2404.40, 3048.16 (438.37)
2 378.62, 957.23, 2641.28, (657.71)
3 17518.23, 26805.36, 41087.51 (5961.64)
4 7375.40, 17831.87, 32354.52 (8689.43)

Jin

Ex. With Weights
---------------------
1 1731.9, 3284.3, 4548.3 (771.31)
2 3947.8, 5788.8, 9190.8 (1820.9)
3 4298, 10568, 20295 (4663.9)
4 4806.2, 9506, 14470 (3355.6)

Scott

Ex. With Weights
---------------------
1 2464.1, 8945.2, 20658 (6588.5)
2 2658.5, 4757.4, 8741.8 (1936)
3 8992.3, 15020, 19028 (3275.4)
4 14906, 27808, 46056 (10216)

Smoothness...

I've done a lot more poking around in MATLAB, and I think that the energy is the best measurement we can use right now. I may post a few plots of the DFT of some of the signals later, but my observation is that it is hard to quantify which parts of the signal are necessary movements and which aren't (the jerks or stop/starts).

However, the energy is a simple measure of the amount of effort required to perform the action. A smooth, quick action will have only the minimal energy required to perform the action, while a slow, jerky action will have much more total energy.

The energy for a signal like this is just the integral of the signal squared, which is closely approximated by the inner (dot) product of the signal with itself. So the following code will give us our smoothness score:

double x_e=0.0,y_e=0.0,z_e=0.0;
for(int i=0;i < A.size();i++)
{
 Double[] sample = A.get(i);
 x_e+=Math.pow(sample[X],2);
 y_e+=Math.pow(sample[Y],2);
 z_e+=Math.pow(sample[Z],2);
}
double t_e = x_e+y_e+z_e;

'A' must be the ArrayList of the acceleration signal. Not the double integrated path. You also need add the following somewhere in the same scope:

private static final int X = 0;
private static final int Y = 1;
private static final int Z = 2;

Path based DTW in Java

I've uploaded a new version of my Java code. I overwrote the previous version.

Once you have the samples in an ArrayList of the x,y,z triples say A and B, then all you do is:

pA = acceltopath(A);
pB = acceltopath(B);
cost = pathcost(pA,pB);

My java code produces exactly the same numerical answer as MATLAB for the examples in the code.

Now I will go about finding the "golden" examples to store in the Android application. Will probably be one of the averages...

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.

Encouraging DTW results

This is an encouraging first result from some playing around I've done with DTW. I modified Jin's DTW MATLAB code to calculate the difference matrix as the Euclidean distance at each point in 3D between the two input data sets. The graph above shows a histogram of the results when 10 recorded actions from task 1 are compared to 10 actions from task 1 (blue), task 2(red) and task 3(green).

What does this means? The histogram is of the 'dist' return value, which is a measure of similarity. So when comparing task 1 actions to task 1 actions all of the scores are below 65. When comparing task 1 to task 2 all of the scores are above 72. Similarly, task 1 and task 3 separate fairly well too. In short, it appears DTW can be used as a good similarity measure between like tasks, with lower scores being better.

Split data and other thoughts

I've split the data up into different files for the three tasks in Jin's data set. You can get it here. In MATLAB you can then do:

>>load t1-00

Now you'll have a variable called 't1_00' with three columns.

As far as the key/lock exercise goes, I think we can just stand at a door and turn the lock. I can do this at my house in any number of doors...

Friday meeting/algorithm

I think we should collect as much data as possible on Friday. We should each run through the five exercises several times to collect a baseline. I may have an extra lock at home, otherwise we should get one. We should bring a few playing cards as well.

It turns out dynamic time warping can be used to align and score the similarity between two sequences.

See wikipedia, or http://labrosa.ee.columbia.edu/matlab/dtw/ for some MATLAB code.

Then this data should be aligned and averaged using dynamic time warping to create a reference. The reference sequences become part of the Android application.

Looking at the data files, it seems like it will be easy to detect the start/stop of the exercise in the signal.

Next, I envision the Android application flow to be (only the testing/scoring part):

Describe the exercise.
"Are you ready to start?"
Count down and then start beep.
Start recording.
Record until two minutes have elapsed, or 2 (or 5?) seconds of stillness are observed.
Ask: "Did you complete the exercise?"
If yes:
Search the signal for the start and end of motion. Compare using DTW and give the score as a time,similarity tuple. Store the tuple in a database for later recall.
If no:
Ask: "Do you want to try again?"

The above is open to feedback/suggestions of course.

This paper has some good information: http://www.ri.cmu.edu/pub_files/...h.../wilson_daniel_h_2004_1.pdf

Two modes

Perhaps we should have two modes to our application:

#1: Simple mode. This mode is used to perform all (or most activities). In the standardized testing mode the score is only related to time. An observer uses a Bluethooth remote to trigger explanation and start/stop events. This would enable un-trained observers to administer the test (perhaps at home). Scores could be stored, uploaded, etc.

#2: Automatic mode: may still require an observer to trigger the start/stop events (or maybe voice recognition?) but the score is based on some TBD combination of time, smoothness, "quality?"

Test blog post

This is the blog for our CSCI546 project: Dr. Droid. We're looking into using a mobile phone as a sensor to improve stroke rehab.