Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Bangle.js: more accurate step counter (pedometer) #1846

Closed
gfwilliams opened this issue Jun 3, 2020 · 32 comments
Closed

Bangle.js: more accurate step counter (pedometer) #1846

gfwilliams opened this issue Jun 3, 2020 · 32 comments

Comments

@gfwilliams
Copy link
Member

gfwilliams commented Jun 3, 2020

Referenced here: http://forum.espruino.com/conversations/345726/#comment15324507

https://github.com/Oxford-step-counter/C-Step-Counter

Might be worth a try including it?

@gfwilliams gfwilliams changed the title Bangle.js: more accurate step counter Bangle.js: more accurate step counter (pedometer) Jan 29, 2021
@gfwilliams
Copy link
Member Author

gfwilliams commented Feb 2, 2021

@dariosalvi78 @MarcusNordstrom I can do some integration to get your code inside the Bangle.js firmware, but it feels like you're probably best placed to ensure this is all working well.

If I sent you both Bangle.js devices, would you be interested in getting everything properly calibrated?

Currently we get acceleration data at 12.5 Hz which seems like a decent battery life compromise. Do you think the step counting algorithm could work well with that? It seems currently you're using 100Hz but I think that'd drain our battery too quickly if it was running all the time.

@dariosalvi78
Copy link

dariosalvi78 commented Feb 2, 2021

Hi Gordon, I'm glad that you are interested!

The 100Hz is not needed really. Marcus tried with 50Hz and accuracy didn't suffer. 12Hz should work in theory considering people rarely do more than 3 steps/s when running.

We have one Bangle here, I have programmed it the Espruino way, but this would probably need flashing the entire firmware: do you have instructions for how to do that? Also instructions about how to setup the toolchain would greatly help.

I would love to work on this but my time is limited right now. Marcus did his thesis with me, so I am not sure he would be still interested, but maybe he'd like to volunteer?

@gfwilliams
Copy link
Member Author

gfwilliams commented Feb 3, 2021

That's great! You can update the actual firmware with https://www.espruino.com/Bangle.js#firmware-updates and for building you can use https://github.com/espruino/Espruino/blob/master/README_Building.md - if you have access to Linux (or WSL under windows) it's pretty easy.

However developing this way can be a bit slow - so if for instance there are variables/constants that could be exposed to JS in order to help tuning it more quickly, that'd probably be best.

Totally understand on the limited time thing! Honestly any help would be great though. Based on https://github.com/Oxford-step-counter/C-Step-Counter we could do with a bunch of data from walking 150 steps?

Perhaps the first thing to do would be for me to make an app that made it easy to record accelerometer data in the CSV format you need, then post up a request on the forum to get as many people contributing CSV files as possible? We can then get a good idea what's needed for that 12.5Hz sample rate, and if everything looks ok, building it in should be pretty easy?

@MarcusNordstrom
Copy link

MarcusNordstrom commented Feb 3, 2021

Hi Gordon,

Unfortunately I am busy with a full time job and won't be able to help. Gathering data from your community sounds like a good idea and best of luck to you!

@dariosalvi78
Copy link

dariosalvi78 commented Feb 3, 2021

Before crowd-sourcing the data, I'd start with some tests ourselves. The best idea would be if you could write this app to save data in CSV format (format: timestamp in ms or us, accelX, accelY, accelZ, acceleration must be as they arrive from the accelerometer) and we collect a few files while counting the actual number of steps manually. With these files, I can try to optimise the algorithm offline, on my computer, and I can give you back the optimised code.

It's possible that we will not need some of the stages, like interpolation and even filtering givne the low sampling frequency, but we need to test it.

If it turns out that accuracy is bad at 12.5Hz, would you be able to increase it, for example, to 25Hz?

BTW, happy to continue this conversation over email if it makes sense: dariosalvi78 at gmail

@gfwilliams
Copy link
Member Author

gfwilliams commented Feb 3, 2021

if you could write this app to save data in CSV format

Just done: https://banglejs.com/apps/#accellog

I'd already posted it on the forum a few hours ago so we may get some data from other users anyway - although yes, it would have been better for me/us to do some testing ourselves first :)

If we could try getting it working well on your PC first, that'd be a really good way to do a proof of concept, and hopefully it's not too painful for you. Once it's working I can probably get it running on Bangle.js pretty well without wasting too much of your time.

Potentially we could raise the sampling frequency if needed, yes - but that has knock on effects on battery life, and I'd probably get a few grumbles from users - so ideally we'd stick with it as-is if possible. I'm hopeful that 12.5 will be ok though.

Would you prefer email? GitHub works fine for me - it makes it easier to reference code sometimes.

@dariosalvi78
Copy link

dariosalvi78 commented Feb 3, 2021

that was quick!
I will try to collect some data these days and see how far I can get. I'll let you know.

I am OK with using Github issues, so let's keep it here for now.

@dariosalvi78
Copy link

dariosalvi78 commented Feb 15, 2021

I've collected a few files walking 100 steps. If I plot them I can definitely see the steps inside (you can use this to plot them youserlf). Looks like the low sampling frequency should not affect too much, but I'll need to confirm it!

I'll keep you posted...

Archive.zip

@gfwilliams
Copy link
Member Author

gfwilliams commented Feb 15, 2021

Great! There are also some other contributed sets of steps at http://forum.espruino.com/conversations/359542 as well now.

I'll take a look at getting the code building in Espruino

@gfwilliams
Copy link
Member Author

gfwilliams commented Feb 16, 2021

Ok, I integrated it here: https://github.com/espruino/Espruino/tree/step_counting

I ran the optimisation tool based on all the data we had available, tried to adjust the low-pass filter for 12.5Hz, and came up with these changes: e269ac7

It runs, but (as you could see from the non-active pedometer widget, or Bangle.on('step',print)) seems to detect a lot of spurious steps at the moment. Maybe I've got the filter wrong or something?

@dariosalvi78
Copy link

dariosalvi78 commented Feb 16, 2021

I'm working on it, there are a few optimizations to be done and I am also checking if there are any bugs.

Question: does the MCU have a coprocessor or would it be better to use the approximated implementation of the SQRT?

@gfwilliams
Copy link
Member Author

gfwilliams commented Feb 16, 2021

Thanks! Yeah, right now it seems there's at least 5k of RAM used for step counting buffers and it'd be really good to try and reduce that substantially.

The MCU does have a 32 bit FPU but I think your integer implementation is likely to be significantly faster than converting to/from floats.

@dariosalvi78
Copy link

dariosalvi78 commented Feb 16, 2021

I'm getting somewhere!
It turns out that there was a bug in the interpolation step and that I had to stretch the parameters quite a lot to adapt to this hardware.
Preview of a few, well-detected steps:
image

@gfwilliams
Copy link
Member Author

gfwilliams commented Feb 17, 2021

That's great! Is the interpolation needed since all the samples arrive at exactly the same 12.5Hz period? I just disabled it on my build for Bangle.js

@dariosalvi78
Copy link

dariosalvi78 commented Feb 17, 2021

good news! I've got a working version, see attachment.

The new version includes the "best" parameters I have found for my set of experiments. These are:
windowSize=10 threshold=0+1/6 time=300

with these set, I get avg abs error of 7% min 0% max 20% on my files and avg 15% min 3% max 52% on community's files.
If trying to optimise parameters on community's files I cannot get below 11% error and with similar parameters, so I don't think it's worth trying to optimise further. I suppose those files are more representative of a "in the wild" situation, so don't expect miracles from this algorithm!

Some fixes and optimisations:

  • fixed the issue with interpolation
  • filtering set to 0dB on 0-3Hz and -10dB on 4-6.25Hz
  • you can skip interpolation and filtering without affecting accuracy significantly, but you would save some CPU cycles
  • there's a config.h file where you can set if you want to skip those steps
  • the config.h file also allows you to specify the types for acceleration, time and magnitude. Currently these are very generous, so you may want to reduce size to save some memory
  • you can use math.h sqrt instead of the approximation: accuracy increases, but very little
  • I have reduced the size of the buffers to 16 (it was 64), but they can be made smaller and even removed actually
  • the algo actually detects steps, the counting is done after that, so you can easily hook a callback and inform apps when steps are detected

Gotchas:

  • this is a peak detector, it cannot distinguish between peaks produced by steps, jumps, waving or whatever...
  • some variables oll over can cause troubles, particularly it assumes an ever increasing time and a counter variable in the detection stage, my recommendation is to reset the algo when time is going to overflow
  • the algorithm adapts to the signal (it computes a mean and SD over the whole acquired signal), so if someone leaves the watch still most of the time, it will end up detecting steps out of noise

Further work:

  • buffers can be removed. They are nice to work with, but are not really needed here. This would allow saving a few bytes
  • I would add a threshold on minimum energy or SD on a small window before even starting peak detection, this would allow to discard weak parts of the signal and avoid detecting steps on noise. Given that all watches share the same accelerometer, this should be easy to do

Let me know if this works and if it's slim enough (memory and CPU-wise) for the Bangle!

@gfwilliams
Copy link
Member Author

gfwilliams commented Feb 17, 2021

Great! I'll give this a go now. It'd be amazing if it were possible to remove the interpolation and buffers - but thanks for dropping the size. I'll see if I can get a figure for the RAM usage with/without the algorithm in.

We actually have a power-saving mode for when the accelerometer isn't moving much, so what I'll do is just not feed data into the step counter while we're power saving - which should help with the issue with adaption.

gfwilliams added a commit that referenced this issue Feb 17, 2021
@gfwilliams
Copy link
Member Author

gfwilliams commented Feb 17, 2021

Ok, so I've pulled this in (zip file attached - espruino_2v08.191_banglejs.zip), and here's what I can tell so far:

  • There's roughly 1.4kB of extra memory usage (so that's roughly 25% more than everything else combined, which feels a bit steep) - as you say removing buffers and moving to smaller types would help massively with this.
  • When walking, it seems to pick up steps pretty well
  • When stationary, it's ok for a little while, then starts counting random steps every second - pretty much as you mention with the threshold

So I think for it to be at a stage where it can be merged and it's producing more useful data than the current peak detector it'd probably need what you mention under further work. Would you be happy to look into that?

On commercial step counting solutions they 'debounce' steps (https://blog.st.com/pedometer-mems-step-count/) so you only really count once someone has got a steady pace. Is that something the current implementation does?

I'd asked the folks in the forum to try different types of walking, including stopping and changing styles - and I guess that would account for why there was so much difficulty actually finding steps in the contributed data.

@dariosalvi78
Copy link

dariosalvi78 commented Feb 17, 2021

The sampling is not very precise even at that frequency, I have noticed some samples being lost completely and the period is sometimes less than 80ms. Nonetheless, interpolation can be removed safely, it doesn't impact the accuracy: just set the flag inside config.h. Also remove filtering, it doesn't bring anything useful.

Memory: I am quite surprised! Removing the buffers should help, but I don't expect a huge change. Try adjusting the types, maybe it helps as well. We would need a bit of profiling to understand where the biggest gain would come from, I am not sure how to do that (I'm not a C guru TBH).

As for detecting steps out of noise, some more processing can be done either in a preliminary stage, where it simply checks if enough energy is in the signal or with this "debouncing" idea in postprocessing, but I haven't got a ready-made solution for it. I would need to gather some signals and play with them.

@dariosalvi78
Copy link

dariosalvi78 commented Feb 18, 2021

regarding types, here are some suggestions:

// type for the accelerometer samples, this depends on your hardware
// for example, if your accelerometer uses 12bits then an int16_t would suffice
typedef int32_t accel_t;

// type used for time: warning the algorithm is not robust to roll-over of this variable
// reset the algorithm if time overflows
// preferably, time should be in ms, if not, use timeScalingFactor in the preprocessing stage to adjust it to ms
// example: a year worth of ms needs 35 bits, 32 bits allows you to store about 50 days of ms
// as time doesn't go back, using unsigned integers makes sense
typedef int64_t time_t;

// magnitude of acceleration
// this should be 1 bit bigger than accel_t
// example: if the accelerometer works at 12 bits, magnitude should be 13 bits, therefore choosing int16_t for both will do
typedef int64_t magnitude_t;

// accumulator of magnitude, should be bigger than magnitude
// the size depends on the length of the filter in the filtering stage
// example: accelerometer works at 12 bits, the filter has 8 taps -> accumulator should be at least 12 + 3 bits -> using int16_t will do
typedef int64_t accumulator_t;

// steps count type
// the size of this depends on what is the maximum number of steps you are willing to show and store
// example: is the step count is reset every 24h and one walks no more than 20k / day (reasonable) -> 16 bits should be enough
typedef int32_t steps_t;

I am not sure how time and acceleration are treated internally, but you are probably fine to use int16_t in most places except time

@gfwilliams
Copy link
Member Author

gfwilliams commented Feb 18, 2021

Thanks - that sounds good. Looks like we can cut things down a lot.

I made it so that when the watch is stationary for ~1 minute (or you switch apps) it stops recording and resets/sets the time counter to 0 - so I think 32 bits will do us fine there too.

@kuleszdl
Copy link

kuleszdl commented Mar 7, 2021

Thanks for all these improvements!

One thing where I see some more potential are the default settings and the thresholds. I have the effect that I get quite many steps counted while only sitting and doing office work on my computer. I am open to suggestions and will be happy to test a few setups and share my experience.

Also, I noticed that it seems to count waaay to many steps when I actually do move. Would it be possible to have some kind of "handicap" so it would divide the measurements e.g. by a factor of 5?

I guess the main reason for this is as stated above by you @dariosalvi78 :

the algorithm adapts to the signal (it computes a mean and SD over the whole acquired signal), so if someone leaves the watch still most of the time, it will end up detecting steps out of noise

@gfwilliams
Copy link
Member Author

gfwilliams commented Mar 8, 2021

I think what you might be hitting is what I mentioned at #1846 (comment) - it looks like many commercial step counters have a second part which only passes on steps that occur at regular intervals.

I feel like having that filter (even applied to the original Bangle.js step counter that's being used) would probably sort out a significant amount of these issues. I just need to figure out how to do it :)

@dariosalvi78
Copy link

dariosalvi78 commented Mar 8, 2021

I have some ideas, I just need to find the time to work on them.

As for overcounting when walking, could you send us some tracks with acceleration and a reference step count? You can count your steps in your head or use another device (like a phone) as a reference. We can try to optimise the parameters based on that. Please be aware that the algo does not distinguish between steps and other types of periodical movement so it'll never be 100% accurate.

@dariosalvi78
Copy link

dariosalvi78 commented Apr 29, 2021

Hello! I have found the time to work a little more on this. Attached an improved version of the algo that skips counting steps when there is no movement.

Unrelated: I am using your HR detection algorithm on a mobile phone camera project. It works quite well!

@gfwilliams
Copy link
Member Author

gfwilliams commented May 4, 2021

Great - thanks! Right now I'm trialling a very simple step counting based a bandpass filter and threshold, but I just pulled in your most recent code to the branch (needed a few tweaks as now sqrt and time_t overwrite C builtins) so we can see how the two compare

@gfwilliams
Copy link
Member Author

gfwilliams commented May 4, 2021

Great to hear about the HR detection... Which one was it? The old autocorrelation one, or the new bandpass one?

@dariosalvi78
Copy link

dariosalvi78 commented May 4, 2021

I have a couple of students testing something similar to what you did here.
It's based on autocorrelation.

We want to compare it with a peak detector (the same used here for step counting!) and see which one is more accurate.

But you say that you have another algorithm? Have you published it somewhere?

@gfwilliams
Copy link
Member Author

gfwilliams commented May 4, 2021

Ahh, nice! I meant this one: https://github.com/espruino/Espruino/blob/master/libs/misc/heartrate.c

It's what I'm trying now - literally just a bandpass filter, then a threshold detector, then a median filter on the resulting time periods. We'll see how it works in reality but I feel like it's able to recover more easily from bits of invalid data.

@dariosalvi78
Copy link

dariosalvi78 commented May 4, 2021

the problem with thresholding is that it's hard to find the right one!

Maybe you can combine it with some of the following ideas:

  • base your threshold on mean and standard deviation. This is for example done here
  • deriving the signal after filtering, it has the effect of amplifying and narrowing peaks
  • using a more sophisticated scoring algorithm like here, this also has the effect of amplifying peaks

I'm very curious to see how this evolves!

@BartS23
Copy link
Contributor

BartS23 commented Dec 22, 2021

Hello @gfwilliams,

will this feature be implemented for BangleJS 2 at some point?

regards Romek

@gfwilliams
Copy link
Member Author

gfwilliams commented Jan 4, 2022

Hi - yes, it's been in Bangle.js 2 since the start.

If you think it's not accurate, best bet would be to record a bunch of data with the acceleration logger app and then add it to https://github.com/gfwilliams/step-count - we can then tweak the current algorithm to work more accurately.

@dariosalvi78
Copy link

dariosalvi78 commented Jan 4, 2022

Hi,
just wanted to mention that we have a repository where we can benchmark algorithms at: https://github.com/dariosalvi78/banglejs-algos-tester

It currently includes 2 algorithms, one of which, as I understand it, is the one included in the official firmware. You are very welcome to contribute with your own data or with a new algorithm!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

5 participants