Smoothing a staircase

I have some data from a position encoder, so naturally i want to estimate its speed. However, the data is very quantized, so it's difficult to smooth enough to differentiate easily:

Each step level is about 70-140 data points long on average, so my usual tricks of savitzky-golay filtering aren't up to it. I've played with piecewise splines as well, but not had much luck; there's a lot of ringing.

Is there a straightforward way to draw the obvious line through the trace?

• What level of quantization is acceptable for you? You could try and look at the FFT result and attempt to take out the frequencies due to quantization.
– Moti
Aug 23, 2016 at 1:27
• Low-pass filter it. maybe add some zero-mean dither and low-pass filter it. Aug 23, 2016 at 2:53
• A related question: stackoverflow.com/questions/1203427/… Aug 23, 2016 at 8:08
• Do you have a way to share the data? Does offline processing suffices, or would you need causal filtering in the future? Aug 24, 2016 at 5:55
• It's mouse movement data for a neuroscience experiment; all analysis is post-hoc, and correlates mouse speed to neural activity. Aug 24, 2016 at 15:44

Looks like your data is virtually free of noise. That, combined with a very high sampling frequency would mean that at the jumps the data is exactly at the threshold between two quantized values. Set up nodes at the middle points of the vertical jumps and construct splines that connect the nodes. The easiest is to just draw straight lines between successive nodes, which gives a piece-wise constant differential. I wonder if that is good enough, or if you already tried that. If you need the velocity real-time, this approach is problematic because occasionally you might have to wait for a new node for some time.

You can further low-pass filter the interpolated data. If you use a filter with an impulse response that is nowhere negative, such as a Gaussian function, then there will be no overshoot.

With linear interpolation, everywhere between successive nodes, the speed will be simply the position difference between the nodes divided by the time difference between the nodes. You can run the smoothing filter on that piece-wise constant speed data and the result will be the same as if you'd run it on the linear position ramps and then differentiated (associative property of convolution, as both differentiation and filtering are convolution).

• A sufficiently low low-pass filter was enough. Aug 23, 2016 at 17:15
• good answer. i would suggest further putting nodes at both the midpoints of the vertical lines and the midpoints of the horizontal lines and using something like a Hermite polynomial spline to connect the dots. Aug 23, 2016 at 17:29
• where should I start to read up on taking the node-based approach? Aug 23, 2016 at 21:48
• en.wikipedia.org/wiki/Linear_interpolation for starters Aug 24, 2016 at 5:35
• @robertbristow-johnson For dithering to help, it should come before quantization, methinks. And that is not possible in this case. Aug 24, 2016 at 19:46

As robert mentioned, low-passing helps here.

No matter how long your constant periods are, they should be much longer than the duration of the actual edges (I suspect these even happen from one sample to the next).

So, these steps have energy content in high frequencies. Look at the (amplitude) discrete Fourier transform of a step function:

So if we filter away all the frequencies above e.g. 1/shortes constant period, we smooth away the quantization.

In effect, this is equivalent to oversampling increasing your total bitwidth.