Derivative of signal with missing samples

Question

I have software that tracks an object moving (in the x-dimension only) across a video shot from a stationary camera. I need to find the velocity and acceleration of the object as functions of time. This calculation can be done offline, so there are no real-time constraints. The motion of the object is also pretty regular, decelerating approximately constantly throughout the duration of motion.

Normally I would design an FIR differentiator to do the job, however the object in the video becomes occluded for up to a few frames at a time on a regular basis throughout it's motion, so I don't have a point for it for several frames. In other words, my data looks like this:

frame_index = [1 2 3 6 7 8 9 13 14 15 16 17 18 21 22 ... ]
x_position  = [0 0.2 0.39 1.14 1.22 ... ]

I've thought about interpolating and then using an FIR differentiator but am unsure what a good scheme for interpolating irregular data like this would be. I've also thought about using a formulation based on Lagrange interpolating polynomials to calculate derivatives directly, but do not know enough about them to understand trade-offs. My goal is accuracy.

So, what would be the best way to go about calculating approximations of the first and second derivatives of the data?

Answer 1

See Smooth noise-robust differentiators. While Pavel doesn't address your specific problem there, he and I corresponded about a similar "missing samples" problem earlier this year, and he has some good ideas that you can try. In particular, he recommends polynomial approximation in the region of the missing samples. In addition I'll mention that if you use Neville's Algorithm you can guarantee that the polynomial passes through your "good" sample values. You can find Pavel's contact info in various places on his Website.

Greg Berchin