Global Tracking via the Viterbi Algorithm

Posted on Aug 27, 2020

Tags: Object Tracking

This post is for Magnusson, K. E. G., Jalden, J., Gilbert, P. M., & Blau, H. M. (2015). Global Linking of Cell Tracks Using the Viterbi Algorithm. IEEE Transactions on Medical Imaging, 34(4), 911–929.

In cell and developmental biology, different cell types are studied either

• in cell cultures (in vitro)
• in live organisms or embryos (in vivo)
• in live tissue (in situ)

Time-lapse microscopy can be used to characterize and quantify many different aspects of cell behavior, such as proliferation (增殖), mitosis (cell division), apoptosis (cell death), migration, and morphology.

Cell tracking algorithms are normally classified into

• model evolution algorithms, where mathematical models of the cells are propagated in time
• tracking by detection, where the tracking problem is separated into finding the outlines of the cells (segmentation) and linking the detected outlines into tracks (track linking, data association, or tracking)

The main challenge of the track linking problem is to perform data association despite errors in the segmentation.

Problem Statement

Assume that the segmentation algorithms outputs a set of detections $\cal D={D_{t,i}}_{t=1:T,i=1:N_t}$.

For every set of proposed tracks $F$, there is a unique set of assignments to the event variables $\cE(F)={\cE_m(F)}_{m=1:\vert\cE\vert}$, then define a score $g(F)$ for the set of tracks $F$, as the sum of the logarithmic probabilities of the assignments to the individual event variables, i.e.,

\[g(F) = \sum_{m=1}^{\vert \cE\vert}\log \Pr(\cE_m = \cE_m(F))\,.\]

The scoring function is memoryless in the sense that the score associated with an event in a cell track does not depend on prior events in the track. This is equivalent to a Markov property saying that the event following the current time-point is independent of prior states of the cell, given the current state of the cell.

Track Linking

1. generating tracks using operations:
2. state space diagram
   • the states are for the added track
   • an added track can either pass through one of the detections, not be present because the cell has yet to appear in the image sequence, or not be present because it has disappeared from the image sequence
   • so the added track doesn’t change the previous added tracks?! Yeah!! This issue would be discussed in the swaps.
3. finding the highest scoring path
   • the change in the score of $F$, that occurs when a track is added, can be computed as the sum of the arc utilities along the corresponding path through the state space diagram.
4. swaps
   • the state space diagram does not allow previously created tracks to be altered
   • the swap operation, which modifies links in preexisting tracks during the creation of a new track, is done by splitting a preexisting track in two parts and linking the second part of the preexisting track to the end of the track under creation.