Establishing trajectories of moving objects without identities: The intricacies of cell tracking and a solution

Storing, querying, predicting, and interpolating trajectories of moving objects is a topic which the database community has studied for decades. We study a new variant of this problem in this article: We deal with a set of moving objects which do not have an identity, i.e., one does not know whether an object is identical to one observed earlier at another position. Our use case is a stream of images of cells of developing embryos. There exist so-called tracking tools. They match cells in such image sequences, to build trajectory vectors. However, these trackers have certain weaknesses, including counter-intuitive parameters and the expectation of users manually correcting trajectories. In this paper, we propose fully automatic tracking algorithms. They rely on space partitioning heuristics to match cells. This gives way to much cheaper data-analysis pipelines, as we will explain. We also propose two algorithms predicting the next positions of cells, given earlier ones. Experiments over 12 datasets show that our new approaches reduce the execution time by up to 7.8 times for tracking and 6.2 times for prediction. Prediction quality increases by up to 5.6% over the best tracker.