fiji.plugin.trackmate.tracking.oldlap

## Class LAPTracker

• All Implemented Interfaces:
SpotTracker, Algorithm, Benchmark, MultiThreaded, OutputAlgorithm<org.jgrapht.graph.SimpleWeightedGraph<Spot,org.jgrapht.graph.DefaultWeightedEdge>>
Direct Known Subclasses:
FastLAPTracker

```public class LAPTracker
implements SpotTracker```

## Overview

This class tracks objects by formulating the problem as a Linear Assignment Problem.

For reference, see: Jaqaman, K. et al. "Robust single-particle tracking in live-cell time-lapse sequences." Nature Methods, 2008.

In this tracking framework, tracking is divided into two steps:

1. Identify individual track segments
2. Gap closing, merging and splitting

Both steps are treated as a linear assignment problem. To solve the problems, a cost matrix is created for each step, and the Hungarian Algorithm is used to determine the cost-minimizing assignments. The results of the calculations are the complete tracks of the objects. For more details on the Hungarian Algorithm, see http://en.wikipedia.org/wiki/Hungarian_algorithm.

## Cost Matrices

Since there are two discrete steps to tracking using this framework, two distinct classes of cost matrices are required to solve the problem. The user can either choose to use the cost matrices / functions from the paper (for Brownian motion), or can supply their own cost matrices.

One matrix corresponds to step (1) above, and is used to assign individual objects to track segments. A track segment is created by linking the objects between consecutive frames, with the condition that at an object in one frame can link to at most one other object in another frame. The options for a object assignment at this step are:

• Object linking (an object in frame t is linked one-to-one to a object in frame t+1)
• Object in frame t not linked to an object in frame t+1 (track end)
• Object in frame t+1 not linked to an object in frame t (track start)

The cost matrix for this step is illustrated in Figure 1b in the paper, and is described in more detail in `LinkingCostMatrixCreator`.

The other matrix corresponds to step (2) above, and is used to link together the track segments into final tracks. Track segments can be:

• Linked end-to-tail (gap closing)
• Split (the start of one track is linked to the middle of another track)
• Merged (the end of one track is linked to the middle of another track
• Terminated (track ends)
• Initiated (track starts)

The cost matrix for this step is illustrated in Figure 1c in the paper, and is described in more detail in `TrackSegmentCostMatrixCreator`.

Solving both LAPs yields complete tracks.

## How to use this class

To use the default cost matrices/function, use the default constructor, and simply call `process()`.

Author:
Nicholas Perry
• ### Field Summary

Fields
Modifier and Type Field and Description
`protected boolean` `defaultCosts`
Stores whether the default cost matrices from the paper should be used, or if the user will supply their own.
`protected org.jgrapht.graph.SimpleWeightedGraph<Spot,org.jgrapht.graph.DefaultWeightedEdge>` `graph`
The graph this tracker will use to link spots.
`protected Logger` `logger`
Logger used to echo progress on tracking.
`protected List<Spot>` `mergingMiddlePoints`
Holds references to the middle spots considered for merging in the track segments.
`protected int[]` `mergingMiddlePointsSegmentIndices`
Each index corresponds to a Spot in middleMergingPoints, and holds the track segment index that the middle point belongs to.
`protected List<Spot>` `middlePoints`
Holds references to the middle spots in the track segments.
`protected double[][]` `segmentCosts`
The cost matrix for linking individual track segments (step 2).
`protected Map<String,Object>` `settings`
The settings map that configures this tracker.
`protected List<Spot>` `splittingMiddlePoints`
Holds references to the middle spots considered for splitting in the track segments.
`protected int[]` `splittingMiddlePointsSegmentIndices`
Each index corresponds to a Spot in middleSplittingPoints, and holds the track segment index that the middle point belongs to.
`protected SpotCollection` `spots`
The Spot collection that will be linked in the graph.
`protected List<SortedSet<Spot>>` `trackSegments`
Store the track segments computed during step (1) of the algorithm.
• ### Fields inherited from class net.imglib2.algorithm.MultiThreadedBenchmarkAlgorithm

`processingTime`
• ### Fields inherited from class net.imglib2.algorithm.MultiThreadedAlgorithm

`errorMessage, numThreads`
• ### Constructor Summary

Constructors
Constructor and Description
```LAPTracker(SpotCollection spots, Map<String,Object> settings)```
• ### Method Summary

All Methods
Modifier and Type Method and Description
`boolean` `checkInput()`
`protected AssignmentAlgorithm` `createAssignmentProblemSolver()`
Hook for subclassers.
`protected double[][]` ```createFrameToFrameLinkingCostMatrix(List<Spot> t0, List<Spot> t1, Map<String,Object> settings)```
Hook for subclassers.
`boolean` `createTrackSegmentCostMatrix()`
Creates the cost matrix used to link track segments (step 2).
`String` `getErrorMessage()`
`org.jgrapht.graph.SimpleWeightedGraph<Spot,org.jgrapht.graph.DefaultWeightedEdge>` `getResult()`
`double[][]` `getSegmentCosts()`
Get the cost matrix used for step 2, linking track segments into final tracks.
`List<SortedSet<Spot>>` `getTrackSegments()`
Returns the track segments computed from step (1).
`boolean` `linkObjectsToTrackSegments()`
Creates the track segments computed from step 1.
`boolean` `linkTrackSegmentsToFinalTracks()`
Creates the final tracks computed from step 2.
`boolean` `process()`
Use only if the default cost matrices (from the paper) are to be used.
`void` `reset()`
Reset any link created in the graph result in this tracker, effectively creating a new graph, containing the spots but no edge.
`void` `setLogger(Logger logger)`
Sets the `Logger` instance that will receive messages from this `SpotTracker`.
`void` `setSegmentCosts(double[][] segmentCosts)`
Set the cost matrix used for step 2, linking track segments into final tracks.
`int[][]` `solveLAPForFinalTracks()`
Computes and returns the optimal final track using the cost matrix segment costs.
`boolean` `solveLAPForTrackSegments()`
Perform the frame to frame linking.
• ### Methods inherited from class net.imglib2.algorithm.MultiThreadedBenchmarkAlgorithm

`getProcessingTime`
• ### Methods inherited from class net.imglib2.algorithm.MultiThreadedAlgorithm

`getNumThreads, setNumThreads, setNumThreads`
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Methods inherited from interface net.imglib2.algorithm.MultiThreaded

`getNumThreads, setNumThreads, setNumThreads`
• ### Field Detail

• #### logger

`protected Logger logger`
Logger used to echo progress on tracking.
• #### segmentCosts

`protected double[][] segmentCosts`
The cost matrix for linking individual track segments (step 2).
• #### defaultCosts

`protected boolean defaultCosts`
Stores whether the default cost matrices from the paper should be used, or if the user will supply their own.
• #### trackSegments

`protected List<SortedSet<Spot>> trackSegments`
Store the track segments computed during step (1) of the algorithm.

In individual segments, spots are put in a `SortedSet` so that they are retrieved by frame order when iterated over.

The segments are put in a list, for we need to have them indexed to build a cost matrix for segments in the step (2) of the algorithm.

• #### middlePoints

`protected List<Spot> middlePoints`
Holds references to the middle spots in the track segments.
• #### mergingMiddlePoints

`protected List<Spot> mergingMiddlePoints`
Holds references to the middle spots considered for merging in the track segments.
• #### splittingMiddlePoints

`protected List<Spot> splittingMiddlePoints`
Holds references to the middle spots considered for splitting in the track segments.
• #### mergingMiddlePointsSegmentIndices

`protected int[] mergingMiddlePointsSegmentIndices`
Each index corresponds to a Spot in middleMergingPoints, and holds the track segment index that the middle point belongs to.
• #### splittingMiddlePointsSegmentIndices

`protected int[] splittingMiddlePointsSegmentIndices`
Each index corresponds to a Spot in middleSplittingPoints, and holds the track segment index that the middle point belongs to.
• #### graph

`protected org.jgrapht.graph.SimpleWeightedGraph<Spot,org.jgrapht.graph.DefaultWeightedEdge> graph`
The graph this tracker will use to link spots.
• #### spots

`protected final SpotCollection spots`
The Spot collection that will be linked in the graph.
• #### settings

`protected final Map<String,Object> settings`
The settings map that configures this tracker.
• ### Constructor Detail

• #### LAPTracker

```public LAPTracker(SpotCollection spots,
Map<String,Object> settings)```
• ### Method Detail

• #### createAssignmentProblemSolver

`protected AssignmentAlgorithm createAssignmentProblemSolver()`
Hook for subclassers. Generate the assignment algorithm that will be used to solve the `AssignmentProblem` held by this tracker.

Here, by default, it returns the Hungarian algorithm implementation by Gary Baker and Nick Perry that solves an assignment problem in O(n^4).

• #### reset

`public void reset()`
Reset any link created in the graph result in this tracker, effectively creating a new graph, containing the spots but no edge.
• #### getResult

`public org.jgrapht.graph.SimpleWeightedGraph<Spot,org.jgrapht.graph.DefaultWeightedEdge> getResult()`
Specified by:
`getResult` in interface `OutputAlgorithm<org.jgrapht.graph.SimpleWeightedGraph<Spot,org.jgrapht.graph.DefaultWeightedEdge>>`
• #### setSegmentCosts

`public void setSegmentCosts(double[][] segmentCosts)`
Set the cost matrix used for step 2, linking track segments into final tracks.
Parameters:
`segmentCosts` - The cost matrix, with structure matching figure 1c in the paper.
• #### getSegmentCosts

`public double[][] getSegmentCosts()`
Get the cost matrix used for step 2, linking track segments into final tracks.
Returns:
The cost matrix.
• #### getTrackSegments

`public List<SortedSet<Spot>> getTrackSegments()`
Returns the track segments computed from step (1).
Returns:
the track segments.
• #### checkInput

`public boolean checkInput()`
Specified by:
`checkInput` in interface `Algorithm`
• #### getErrorMessage

`public String getErrorMessage()`
Specified by:
`getErrorMessage` in interface `Algorithm`
Overrides:
`getErrorMessage` in class `MultiThreadedAlgorithm`
• #### process

`public boolean process()`
Use only if the default cost matrices (from the paper) are to be used.
Specified by:
`process` in interface `Algorithm`
• #### createTrackSegmentCostMatrix

`public boolean createTrackSegmentCostMatrix()`
Creates the cost matrix used to link track segments (step 2).
Returns:
True if executes successfully, false otherwise.

`public boolean linkObjectsToTrackSegments()`
Creates the track segments computed from step 1.
Returns:
True if execution completes successfully.

`public boolean linkTrackSegmentsToFinalTracks()`
Creates the final tracks computed from step 2.
Returns:
`true` if execution completes successfully, `false` otherwise.
• #### solveLAPForTrackSegments

`public boolean solveLAPForTrackSegments()`
Perform the frame to frame linking.

For each frame, compute the cost matrix to link each spot to another spot in the next frame. Then compute the optimal track segments using this cost matrix. Finally, update the graph with found links.

```protected double[][] createFrameToFrameLinkingCostMatrix(List<Spot> t0,
List<Spot> t1,
Map<String,Object> settings)```
Hook for subclassers.

Create the cost matrix required in the frame to frame linking.

Parameters:
`t0` - the list of spots in the first frame
`t1` - the list of spots in the second frame
`settings` - the tracker settings that specifies how this cost should be created
Returns:
the cost matrix as an array of array of double
• #### solveLAPForFinalTracks

`public int[][] solveLAPForFinalTracks()`
Computes and returns the optimal final track using the cost matrix segment costs.
Returns:
`true` if this executes correctly, `false` otherwise.
• #### setLogger

`public void setLogger(Logger logger)`
Description copied from interface: `SpotTracker`
Sets the `Logger` instance that will receive messages from this `SpotTracker`.
Specified by:
`setLogger` in interface `SpotTracker`
Parameters:
`logger` - the logger to echo messages to.