Updating hypotheses graph edges only if connected to merger nodes

[JaimeIvanCervantes]

During merger resolving, updating edges of hypotheses graph only if connected to merger nodes. Also, some minor changes to the hypotheses graph diagram.

[chaubold]

The changes you made to IlastikMergerResolver are that you only update the tracking result in the direct vicinity of mergers (masked by the merger node-attribute), even though you run min-cost max-flow on the full graph. First I was wondering why there should be any difference to what happens without withFullGraph=True, which is running min-cost max-flow only in the subgraphs that have merger=True set.

Looking at a situation like in the sketch below (which is taken from one of our email discussions from May 2016) reminded me of why you were adding the withFullGraph option in the first place. We wanted to have the ability that the red/yellow/green tracks could swap in the merger-resolved tracking, not just red+yellow.

Now I do see 2 1 problems with the full-graph and your new masking option from this PR:

1. as I mentioned several times before, max-flow tracking ignores all costs and just finds any solution that can push as many objects(=amount of flow) through the graph as possible. So in the screenshot above, if we had all the red/yellow/green edges available, we would get a random assignment! To fix this, we must use min-cost max-flow tracking again. This means calling the full-fledged track method in MergerResolver.run(), but also specifying proper weights. But to do this properly we'd have to recompute the features and predict the ObjectCount Classifier for the resolved merger nodes, which is a major effort.
2. even if the resulting assignment after running any solver on the full graph is correct (in the sketch: it assigns red/yellow/green correctly), but we only copy over those parts of the hypotheses graph that are connected to mergers directly, we must make sure that we get a valid solution after merging them. In this example, we'd have to make sure that after copying over the values of the red/yellow/green linking, we also turn off the original green->green link.

Please set up a test that uses withFullGraph=True to evaluate this in more detail.

[chaubold]

Oh, actually we are doing min-cost max flow tracking for the merger resolving... Sorry about that, I confused myself here. See https://github.com/chaubold/dpct/blob/master/src/flowgraph.cpp#L109.

I've edited the message above.

[JaimeIvanCervantes]

@chaubold here's an example of a case where computing the full graph would make a difference, and an explanation of the difference between the full-graph enabled vs full-graph disabled:

Full-Graph Enabled

Here's an example of four frames, where the full graph is computed during merger resolving and the IDs are assigned correctly:

1) Hypotheses graph passed to the first stage solver:

2) Solution graph for the first stage solver:

3) Hypotheses graph passed to the merger-resolver solver. Note that all the edge hypotheses are reactivated, which enables the solver to consider edges that might have been disabled due to linking costs that were computed with the centers of the old merger nodes:

4) Solution graph from the merger-resolver solver. Note that the IDs were resolved correctly:

Full-Graph Disabled

Here's the same example with the full-graph disabled. You can clearly see that the IDs were assigned incorrectly (IDs are swapped):

1) Hypotheses graph passed to the first-stage solver (same as above):

2) Solution graph for first-stage solver (same as above):

3) Hypotheses graph passed to merger-resolver solver. Notice that in this case, ONLY the enabled edges are being passed to the solver, and therefore the right solution can't even be obtained:

4) Solution graph from the merger-resolver solver. Note that the IDs were swapped.

The problem was that I was replacing all the edges on the final solution graph, instead of just replacing the edges connected to mergers. Since the merger-resolver solver doesn't allow appearances and disappearances in the middle of the sequence (only at the beginning and the end), the IDs with appearances/disappearances would be completely removed from the solution.

To answer your concern about updating the final solution graph, remember that the old merger nodes and their corresponding edges are entirely replaced by the new nodes and their edges, and the rest of the graph stays the same, therefore only the merger nodes edges and neighbors will be affected.

[chaubold]

Thanks for the extensive explanation, very helpful!

My concern is not completely ruled out though, and I think your figure withFullGraph 4) has an edge turned on which should be off, visualizing exactly what I meant with Problem 2) above (if it is not just an artifact of visualization, but I guess not):

The source node of this edge now has two active outgoing edges! What needs to be done here is that an edge that connects two non-merger nodes and was turned on before merger resolving, needs to be switched off if that object was now assigned to/from resolved merger nodes. To be more precise: The nodes A and C were added by splitting up a merger. Now the old link between non-merger nodes B->D was replaced by A->D and B->C. The masking you use for copying the results back catchesA->D and B->C because these were connected to at least one merger. But it does not update the state of the link B->D to "not used" because no merger was involved!

I am a bit surprised how robust our code is dealing with this, but I assume after merger resolving we do not check for correctness anymore (a non-merger node with two active outgoing links should cause problems). But apparently the lineageID computation does the right thing, or your results would look different...

[JaimeIvanCervantes]

Good catch, I see your point now. I updated the code here: https://github.com/chaubold/hytra/commit/0094c8e97f2ad9b1f0264dcc20968fd08af0e856

I'm now checking that the nodes connected to mergers have the correct number of edges (in the original hypotheses graph). Here's how the final graph looks now:

[chaubold]

Okay that looks much better! The only thing that is a bit too drastic now in my eyes is that now you are deleting edges from the part of the hypotheses graph that is not directly adjacent to mergers, but you could have simply set that edge's value=0, which would be the minimally invasive solution. That would prevent confusion if we continue to use the hypotheses graph after merger resolving for more than just looking up the tracking result (e.g. for debugging?). Right now we're building a new graph in every run of track anyways and don't use it much otherwise, so that probably does not matter too much.

[chaubold]

FYI, I've just improved that edge removal-code a bit more because if the source node was a division, it would remove any previous outgoing child arcs, resulting in an invalid solution.