Quickstart

Download this page as a Jupyter notebook

Consider the following example track graph, where each node is a potential object and each edge a potential link of objects between frames:

(click here to see how to create the example track graph)

import motile
import networkx as nx

cells = [
        {'id': 0, 't': 0, 'x': 1, 'score': 0.8},
        {'id': 1, 't': 0, 'x': 25, 'score': 0.1},
        {'id': 2, 't': 1, 'x': 0, 'score': 0.3},
        {'id': 3, 't': 1, 'x': 26, 'score': 0.4},
        {'id': 4, 't': 2, 'x': 2, 'score': 0.6},
        {'id': 5, 't': 2, 'x': 24, 'score': 0.3},
        {'id': 6, 't': 2, 'x': 35, 'score': 0.7}
]

edges = [
    {'source': 0, 'target': 2, 'score': 0.9},
    {'source': 1, 'target': 3, 'score': 0.9},
    {'source': 0, 'target': 3, 'score': 0.5},
    {'source': 1, 'target': 2, 'score': 0.5},
    {'source': 2, 'target': 4, 'score': 0.7},
    {'source': 3, 'target': 5, 'score': 0.7},
    {'source': 2, 'target': 5, 'score': 0.3},
    {'source': 3, 'target': 4, 'score': 0.3},
    {'source': 3, 'target': 6, 'score': 0.8}
]

graph = nx.DiGraph()
graph.add_nodes_from([
    (cell['id'], cell)
    for cell in cells
])
graph.add_edges_from([
    (edge['source'], edge['target'], edge)
    for edge in edges
])

graph = motile.TrackGraph(graph)

import motile
from motile_toolbox.visualization import draw_track_graph, draw_solution

draw_track_graph(graph, alpha_attribute='score', label_attribute='score')

The numbers in nodes show how likely it is that a node represents a true object (versus being a false positive). Similarly, for edges the number shows how likely the incident nodes represent the same object across time.

We want to find tracks in this graph that globally maximize the overall score, subject to certain constraints.

We will start with a very simple case:

1. nodes and edges should be selected based on their score

2. objects are not supposed to split or merge

3. there should be a small penalty for starting a new track

motile comes with costs and constraints that allow us to do exactly that.

Adding Costs for Nodes and Edges

First, we have to create a Solver for our track graph:

import motile

# create a motile solver
solver = motile.Solver(graph)

Once a solver is created, we can add costs and constraints to it. We start with the most basic ones: the cost for selecting a node or an edge. Both nodes and edges in our example graph have an attribute score, which indicates how likely the node or edge is a true positive and should therefore be selected. A higher score is better.

motile, however, expects us to give a “cost” for selecting nodes and edges. It will then minimize those costs to find the globally optimal solution. Here, lower is better. Therefore, we need to invert the scores, which we can easily do by giving them a negative weight. We can do this by instantiating the classes costs.NodeSelection and costs.EdgeSelection:

from motile.costs import NodeSelection, EdgeSelection

solver.add_cost(
    NodeSelection(
        weight=-1.0,
        attribute='score'))
solver.add_cost(
    EdgeSelection(
        weight=-1.0,
        attribute='score'))

After solving the optimization problem…

solution = solver.solve()

…we are ready to inspect the solution. For that, we make use of motile’s variables. Specifically, we are interested in the assignments of the node and edge selection variables:

from motile.variables import NodeSelected, EdgeSelected

node_selected = solver.get_variables(NodeSelected)
edge_selected = solver.get_variables(EdgeSelected)

for node in graph.nodes:
  if solution[node_selected[node]] > 0.5:
    print(f"Node {node} has been selected")
for u, v in graph.edges:
  if solution[edge_selected[(u, v)]] > 0.5:
    print(f"Edge {(u, v)} has been selected")

Node 0 has been selected
Node 1 has been selected
Node 2 has been selected
Node 3 has been selected
Node 4 has been selected
Node 5 has been selected
Node 6 has been selected
Edge (0, 2) has been selected
Edge (0, 3) has been selected
Edge (1, 3) has been selected
Edge (1, 2) has been selected
Edge (2, 4) has been selected
Edge (2, 5) has been selected
Edge (3, 5) has been selected
Edge (3, 4) has been selected
Edge (3, 6) has been selected

Variables are instantiated and managed by the solver. All we have to do is to ask the solver for the kind of variables we are interested in via Solver.get_variables(). The returned value (e.g., node_selected) is a dictionary that maps what to where: in the case of node variables, the dictionary keys are the nodes themselves (an integer) and the dictionary values are the indices in the solution vector where we can find the value of the variable. Both node and edge indicators are binary variables (one if selected, zero otherwise).

Here is our graph again, showing all the selected nodes and edges:

All nodes and edges have been selected! This is indeed what we asked for, but not what we want. Time to add some constraints.

Adding Constraints

With negative costs, the solver is incentivised to pick every node and edge, which is not what we want. We will add two constraints to the solver, constraints.MaxParents and constraints.MaxChildren, to make sure that tracks don’t merge or split:

from motile.constraints import MaxParents, MaxChildren

solver.add_constraint(MaxParents(1))
solver.add_constraint(MaxChildren(1))

If we solve again, the solution does now look like this:

solution = solver.solve()

Nodes do now indeed have at most one parent (to the previous time frame) and at most on child (to the next time frame). There are multiple possible solutions that satisfy those constraints and the solver picked the one that has the least total costs.

This is starting to look good, but we note that a single node was selected in the last timeframe, without any link to the past or future. This is in fact a track consisting of just one node. To avoid those short tracks, we can add a constant cost for the appearance of a track: only tracks that are long enough to offset this cost will then be selected.

Adding a Cost for Starting a Track

motile provides costs.Appear, which we can add to our solver to discourage selection of short tracks. We add them similarly to how we added the node and edge selection costs:

from motile.costs import Appear

solver.add_cost(Appear(constant=1.0))

And if we solve the tracking problem again with those costs…

solution = solver.solve()

…we see that the orphan node is gone now. Its (negative) cost is not enough to justify starting a new track:

Download this page as a Jupyter notebook