Finding events

[SteveGaukrodger]

Hi,

I am kind of new to all of this - I'm mainly a developer with delusions of mathematical ability. Apologies if this has been answered elsewhere, but I just don't know the right words to look for. I've watched a lot of tutorial videos and I just can't see an easy way to get to where I want. This doesn't seem like it should be so hard, so I figure I'm missing some basic concept.

I am trying to do very simple gait analysis. I have accelerometers on people's legs and I'm trying to segment a walk into steps. Ideally, I want to detect when their feet leave and hit the ground. I have data that looks like this:

A series of 4 standard strides looks like this (there are some anomalies that I'm willing to just ignore for now):

The problems I have are that:

• The height of the peak varies between strides
• The length of the stride varies
  This variation is especially noticeable between people - some people have stride times 3-4 times as long, with amplitudes from half as high to twice as high. To a person (yes, I know that recognising things is computationally hard) these steps are all visually recognizable as the same thing.

I understand motif discovery and I think it can help, although I've been looking at shapelets and maybe they're more useful. There's also the problem of time - I think I have to resample the data and look again? I'm not really sure.

In an ideal world, I could run a magic algorithm over the data and get
stride1_toe_off_time, stride1_heel_strike_time,
stride2_toe_off_time, stride2_heel_strike_time,
...

What technique should I be using?
Is there a tutorial or paper I can read that will help me?

[seanlaw]

@SteveGaukrodger Welcome to the STUMPY community and thank you for your question. I don't know the answer but I'm wondering if time series snippets might be useful here. It has been implemented in STUMPY but we are still working on the corresponding yet-to-be-published snippets tutorial.

The height of the peak varies between strides

Matrix profiles typically compare shapes (i.e., subsequences) that have been z-normalized (take each subsequence and subtract the mean from each point in the subsequence and divide by the standard deviation of the subsequence) and, for each subsequence within your time series, a matrix profile captures the one-nearest-neighbor for each sliding window subsequence. So, even if the first stride (stride "A") has a different height than the second stride (stride "B"), as long as the first stride (or second stride) repeats somewhere else in the time series then it should have a "one-nearest-neighbor", which should produce a small matrix profile (distance) value for that subsequence/stride. However, let's say the person is walking on a treadmill and the the first stride ("A") is the initial step of getting on the treadmill before the person establishes the right walking speed by stride two ("B"). Then, stride "B" will look nearly identical to every subsequent stride. In other words, after (and including stride "B"), all of the stride heights are essentially the same. While stride "A", which has a fundamentally different height, will look anomalous and have a large distance to its one-nearest-neighbor (as it looks different from everything else in the time series). Does that make sense?

The length of the stride varies
This variation is especially noticeable between people - some people have stride times 3-4 times as long, with amplitudes from half as high to twice as high. To a person (yes, I know that recognising things is computationally hard) these steps are all visually recognizable as the same thing.

This is more challenging and there is no real way to address this as there is no one-size-fits-all stride length (i.e., subsequence/window size). This usually requires a good deal of trial and error by playing with different window sizes. Note that it is possible to find different (window) sized motifs even within the same time series. Imagine a person who goes from walking to running (or moves from carpet to a hard surface like in the robot dog tutorial). The subject is still the same but the stride length may be different.

[SteveGaukrodger]

Hi Sean,

Thanks for that. I'll see what I can do with snippets and normalization.

In Stumpy the way it works at the moment Is there any normalization within the windows? And does it correct for trends? For instance, if you have two identically shaped windows but one has all values increased by 5, what happens?

I saw a talk by Eamonn Keogh where he suggests up and downsampling to fix this. It's strange - I feel like I should be able to use an object detection/segmentation CNN to find this (I do know deep learning - which you accurately describe as everyone's favourite hammer looking for a nail).

Heck, it feels like I should be able to print out the graph and use a CNN on that :)

It's strange that something we find so easy is so hard for a computer.

[seanlaw]

In Stumpy the way it works at the moment Is there any normalization within the windows? And does it correct for trends? For instance, if you have two identically shaped windows but one has all values increased by 5, what happens?

By default, every subsequence is z-normalized before it is compared with every other (z-normalized) subsequence. This is essentially de-trending the data at the subsequence level and allows for vertical shifts to be removed thanks to z-normalization. This is what is meant earlier by "comparing shapes" as the vertical increases/decreases have been z-normalized.

If you want to account for changes in amplitude then you'll need to explicitly set normalize=False to turn off z-normalization and compute the non-normalized Euclidean distance.

It's strange that something we find so easy is so hard for a computer.

Unfortunately, when two subsequences are identical then we can all agree that they are the same. However, anything that is not 100% identical then depends on the eye of the beholder. Sadly, your threshold for "similarity" may be different from my threshold even given the same data. So, it becomes somewhat subjective depending on what your use case is. Though, I would argue that any "magical" function that makes this threshold decision for you is likely making an assumption for you that could come back to bite you in the behind in the future and we (STUMPY) try very hard to force the user to make the hard decisions or to be consciously aware of their choices and to, hopefully, help the user understand their data at a deeper level. Alas, there is no free lunch.

[SteveGaukrodger]

Thanks very much. And the choice you've made is probably the best approach. It's just one of those things that makes me shake my head. And cry when I have to try to explain it to my boss.

[seanlaw]

Trust me. I'm crying with you every time I realize how a seemingly "simple" problem can become so complex so quickly. 😢 When things "work" then everyone is happy but the moment that things break then everyone wants to know "why?" and "how do we fix this?".

On another related note, you may also be interested in something called Dynamic Time Warping (DTW) for figuring out the best way to scale your data. I don't have any experience with it but thought that I'd mention it in case it may be of use to you.

[SteveGaukrodger]

Thanks for that. I've seen that it exists, but I wasn't sure if it would apply. I'll try snippets and maybe with a few simple warping techniques - e.g. up and down sampling.