next »

[lithander]

I'm looking for a smoothing algorithm.

There's some incoming data every frame and that can be noisy and jerky (imagine some joystick data) and I want to smooth it before working with. There are two solutions that I frequently use:

1.) Every frame take the old value and move it towards the new value while constraining the step size by a value depending on the framerate. If you plot the value the result you get a continious graph with a gradient that is bounded.

2.) Sliding-Average. Just keep track of N values in a queue and average them where N depends on the framerate and the degreee of smoothing you want. That smoothes the graph nicer then 1. But it's costlys because you got to store N values and not just the last one. If there's a rapid change in the source data this approach is also too slow to adapt.

In my scenario 1 is not smooth enough and 2 is too costly. I could probably do something like "take 90% of the old value and 10% of the new value" and tinker until I'm happy... but i'm sure there are established solutions to this problem!

[Myran]

Is sliding average really that expensive? It does take some memory, but unless you constantly want to change the window size you could just store it in a circular buffer and cache the sum of the values. It seems really cheap to me...

[lithander]

Is sliding average really that expensive? It does take some memory, but unless you constantly want to change the window size you could just store it in a circular buffer and cache the sum of the values. It seems really cheap to me...

It's going to be used in the Motioncontroller of all Orcs&Heroes in HORDE . We hope to suppoort about 300 active combatants in a level. Each controller has about 10 values that need to be continious (e.g. smoothed) if I want to smooth over a duration of ~300ms at 60hz each buffer needs to hold 18 values. That are ~54000 numbers that I have to touch sum up and average every frame and it's script code. Also there's the overhead of iterating over 3000 containers. Maybe I've got to profile it first but I'm almost sure that's going to be a significant waste of CPU cycles.

It's not super critical but I thought maybe people were aware of a clever smoothing hack that I'm not.

[Fallsburg]

So, obviously, you'll want to check this out on other systems but in python, non-vectorized summing over 54,000 numbers takes ~0.004 seconds, so you'd be able to do it about 3.4 times per frame.

But you don't need to do that.  If you keep the sums for each controller value, then all you need to do is subtract off the one that is getting pushed out of the window and add the one that is getting pushed on (and divide, obviously), so instead of summing 54,000 numbers you would be summing 6000. Which my little benchmark says takes ~0.0006 seconds or could be done ~27.8 times per frame.

[lithander]

@Fallsburg: This is a good optimization if samples are not to be weighted. Also, as mentioned by Myran using an array as a ring buffer is probably faster then a queue. I'll make sure to implement it that way before judging it's performance.

Meanwhile I've found this presentation that gives a nice overview on smoothing algorithms for time series:

http://www.statoek.wiso.uni-goettingen.de/veranstaltungen/graduateseminar/SmoothingMethods_Narodzonek-Karpowska.pdf

A solution that does some trend projection might actually be a good thing.

[lithander]

Wikipedia is actually unexpectedly helpfull, too, and provides a great overview!

http://en.wikipedia.org/wiki/Exponential_smoothing

[lithander]

Tried em all! Not happy It's not a matter of tweaking the values it's that these standard algorithm don't know what I know about the problem space. (for example that a lot of values are bounded in the range of [-1..1])



Green - Original!
Red - Constrained gradient e.g x_smooth = Towards(x, delta_max);
Blue - MovingAverage, which works best but lags behind a lot.
White - Simple Exponential
Yellow - Double Exponential, considers trend which sometimes is awesome and sometimes just sucks.

Well... I guess I know enough now to cook up my own custom smoothers.

[BorisTheBrave]

Given what you've said so far, you are determined to find a problem with everything. It's hard to evaluate what you need, I know.

I doubt your data is *really* special enough that exponential smoothing won't do a decent job. But if you are convinced, check out Kalman filter's, which are designed for guessing at a hidden variable that you can only observe with noise. The algorithm specifically builds in knowledge you have about what is possible / likely values for the hidden variable. It can also do trend estimation by including velocity as an additional hidden variable.

(note: prediction what the *next* value will be is not the same as smoothing. It's not clear which one you are looking for from your comments)

Performance wise, nearly all the proposed filters are very cheap to evaluate. Exponential smoothing requires a multiply and an add, unweighted moving average requires two adds, a multiply and a load/store, and weighted moving average requires four adds, a multiply, two load/stores and a divide. If your scripting language cannot handle that per-frame for 3000 objects, get a new scripting language, it is useless to you.

[lithander]

Given what you've said so far, you are determined to find a problem with everything.

Sorry, that it seems that way! As long as there's jerky movement I'm not happy because somehow my gutfeeling tells me it should be possible to get smooth, believable motion.

It's not about prediciton at all. It really is about smoothing, and now that I hacked the double exponential smoothing that it won't overshoot the valid range [-1..1] I'm getting there. I achieved that by scaling beta (the amount of trend to factor in) based on where the current value is in the range of valid values. The scaling function evaluates to 0 at 1, 0 and -1 and to 1 at 0.5 and -0.5 which works pretty well, actually.

Performance wise, nearly all the proposed filters are very cheap to evaluate. Exponential smoothing requires a multiply and an add, unweighted moving average requires two adds, a multiply and a load/store, and weighted moving average requires four adds, a multiply, two load/stores and a divide. If your scripting language cannot handle that per-frame for 3000 objects, get a new scripting language, it is useless to you.

I'm using C# and the Unity engine. I guess I'm okay! Thanks for your reply, even if I annoy you a little, I found your (all) comments really helpful for various reasons.

Well... breakthrough imminent, back to work!

[lithander]

 

 

[ThemsAllTook]

Impressive! Looks great to my eyes.

[Christian Knudsen]

Yeah, that looks pretty darn good!

[lithander]

Thanks for the praise, guys! Really means a lot to me.

I shall use this opportunity to proclaim my love and appreciation for Squiggle, a plugin that visualizes values that you log each frame as nice, colored graphs. Not only does this help with finding the best smoothing algorithms.^^ It also makes it easier to collaborate with non-coders. Animators can relate what they see in the rendering to the curves and then tell you what they think needs to change and then you can iterate on that within seconds because the compile times in Unity/C# are negligable.