An algorithm for piecewise-constant velocity estimation and application to particle trajectories in microscopy

We describe a new method for the analysis of spatio-temporal trajectories consisting of the automated identification of periods of constant velocity. Our jump-sparse formalism has critical advantages: (1) it is invariant to trajectory translation, rotation or scaling, (2) it does not rely on a sliding time-window of fixed width, (3) it is robust to random-walk processes, (4) it does not require known number of states and their velocity values. We devise fast algorithms for solving the velocity estimation problem using a combination of convex trajectory regularization and graph cuts optimization techniques and show its accuracy for time-lapse microscopy data.