Cell Tracking Using Viterbi

Track by detection based Greedy approach using dynamic programming for state analysis

Raghavendra Singh Chauhan

Tracking Algorithm Outline

1. Start with empty set of track
2. Add one track at a time in a greedy way that maximizes the scoring function
3. Stop when the scoring function cannot be increased by adding an additional track.
4. Ensure optimal nature in each track solution.
5. Improvisation using a notion of swap operations.

​

A representative image of segmented image with detection label.

Formulation of the problem

• segmentation algorithm outputs a set of detections

where Dt,i is detection number i in image t, Nt is the number of detections in image t, and T is the length of the image sequence.

• Given the set of detections D, we try to generate an accurate set of cell tracks

Representation of cell detections as Acyclic Graph

Representation of Track and scoring function

• represent a set of cell tracks and the mother-daughter relationships between them using an acyclic graph F with one or more connected components

​

• The nodes of F represent individual cells at different time-points, and are labeled with the indices of the detections that the cells occupy at those time-points.

​

Scoring function

• Scoring different solutions to the tracking problem which contain different events.
• A score g(F) is defined for the set of tracks F.

​

​

​

• E represents the events like mitosis,apoptosis,cell appearance,etc.

Scoring function requirements

• Memoryless function obeying the Markov property.
• Markov property requires that the score associated with a event must not depend on the location of the cell in images prior to image t, given that the location in image t is known.
• This assumption does not deteriorate the performance for cell tracking as otherwise dynamic motion model’s assumption of smooth motion is frequently violated.

Events

Generating tracks using operations

• Sequence of operations is performed where each operation adds a node to existing track which in turn gets added to a set F.
• Updation of variables of events according to the nature of events.
• Restrictions on operations to maintain consistency.

​

Cell Track with state space diagram representation

State Space Diagram

• Possibilities can be represented as states in a state space diagram
• The state space diagram has one state associated with each detection Dt,i in the image sequence.
• The operations associated with the arcs can either start the creation of a new track in F, append an additional node to the end of the track under creation, or end the track under creation.

Finding the highest scoring path

• Finding the track which increases the score of F the most is equivalent to finding the path from A to B in the state space diagram, with the highest summed utility.
• There can be multiple arcs between a pair of states, but only the arc with the highest utility can be a part of the optimal path from A to B.(Greedy Method)
• Define the arc set Arc, containing the maximum utility arcs between all pairs of states.

• From Arc choosing the one for which gmax(E) + ∆g(E, Et,i) is maximal.
• Backtrack from B to A to recreate the optimal path through the state space diagram.
• If gmax(B) becomes equal to g(F), the track linking algorithm is terminated.
• The worst case complexity of a naive implementation of the algorithm described above is O(τmaxT N⁴).

Scope For Improvisation

1. Adding the swap operation functionality to correct track linking errors in pre existing tracks.Also improves the time complexity.
2. Changing the module for probability distribution function such as GM-PHD.
3. Addition of pre conditioning filters according to need of dataset such as bandpass filtering for segmentation.

Thank You !

Reference

Global Linking Of Cell Tracks Using Viterbi Algorithm - Klas Magnusson