Feature request: supporting edges connecting non-sequential frames

yfukai commented 11 months ago

traccuracy version: 0.0.2
Python version: any
Operating System: any

Description

Currently the edges of the tracking graph are defined as follows:

Edges point from a node representing a cell in time point t to the same cell or its daughter in t+1.

However, I think some tracking models (including the popular LAP tracker implemented in the TrackMate, utrack and laptrack) can detect edges connecting nodes at non-sequential frames by assuming some cells are undetected in the skipped frames. To keep the metrics fair to those algorithms, it may be useful to revise the code so that they can deal with the frame-skipping edges. Thanks!

What I Did

not applicable

DragaDoncila commented 11 months ago

@yfukai yep agreed, this is a great point. I actually think this should be a feature before V1

cmalinmayor commented 10 months ago

TLDR

I propose adding "dummy" nodes to the TrackingGraph to represent skipping edges in the loading stage (essentially filling in the skipping edges, potentially with interpolated locations, but with a flag that indicates it is part of a skipping edge). Then all the assumptions about the graph structure remain true and all Metrics and Matchers work without any changes, but special cases can be handled if needed.

Original, slightly rambly, thoughts

I'm wary of allowing TrackingGraph edges to skip frames, as it might add a ton of complexity to the code. Would it be sufficient to interpolate skipping edges to include a node in each frame of the TrackingGraph during the loading phase? Or do the matchers and metrics actually need to know about the difference between normal edges and edges over multiple frames? If we actually need to adapt every matcher or metric to supporting skipping edges, we will need to think carefully about it. Here's some conceptual and implementation questions I have as I start considering it:

Currently we represent the matching on nodes only, and use that to infer edge matchings. Is that possible if we support skipping edges, or would we need to represent the matching on edges? This came up in our initial conversations at the Trackathon as well, but I'm not sure how skipping edges changes the conversation, although my next questions might shed some light.
Even for simple annotations like false negative nodes and edges, allowing skipping edges might change the meaning. Consider if have ground truth nodes g1, g2, and g3 connected in a chain from time 1 to 3, and we have a reconstruction with r1 and r3 connected with a skipping edge, and g1 is matched to r1, and g3 is matched to r3 (the basic skipping edge scenario). Presumably both ground truth edges would be considered True Positive edges, since they are both covered by the skipping edge? Is g2 a False Negative node, since it does not have a match? Or is it a True positive, since its presence is implied by the skipping edge?
Would each metric (and/or matcher) say if it supports skipping edges, similar to the types of matching validation that we plan to implement? Do the CTC metrics support skipping edges? How about the Division evaluation?
Would we need to compute each metric with and without skipping edges of different lengths, similar to the "frame buffer" aka frame tolerance on divisions?

I think adding "dummy" nodes to the TrackingGraph to represent the nodes implied by skipping edges solves most of these questions with maximum flexibility and minimal unnecessary complexity. The skipping edge information is still present in the graph, but Matchers and Metrics can totally ignore them and treat them as a series of normal edges if the difference is not important to the concepts in that Matcher or Metric. If they are important (e.g. we want to Match on location/IOU of non-dummy nodes and then infer matching of dummy nodes based on the "skipping edges"), the information is present. And if a particular matcher or metric explicitly wants to disallow skipping edges (or provide a flag to toggle them), that is also easy to implement.

DragaDoncila commented 10 months ago

@cmalinmayor maybe I'm missing something but I don't actually think edges spanning multiple frames would add that much complexity to the codebase? It's really only the loaders that need to change, no? Once you have the graph loaded, the matching would proceed as normal on nodes, and then the metrics would simply check whether two adjacent nodes in pred are also adjacent in GT - regardless of what frames they skip. What do you think is the source of complexity?

Presumably both ground truth edges would be considered True Positive edges, since they are both covered by the skipping edge?

I don't see a reason to make this assumption. I think if the GT has two edges connecting these three nodes, and we have just one edge connecting two nodes, then these are simply different solutions and they should be treated as such i.e. we should not do any reasoning about what constitutes a match.

Is g2 a False Negative node, since it does not have a match? Or is it a True positive, since its presence is implied by the skipping edge?

g2 is a False Negative node as it does not have a match. While the presence might be "implied" by the skipping edge, we are still missing a detection - which in some instances could be critical. But essentially, the human detected a cell here, and your method didn't, so yes, you should be penalized.

Would each metric (and/or matcher) say if it supports skipping edges, similar to the types of matching validation that we plan to implement? Do the CTC metrics support skipping edges? How about the Division evaluation?

CTC does support skipping edges afaik, I actually think I found an example in one of the datasets we're playing with (but will need to confirm). Certainly, the definition of the metric does not preclude edges across multiple frames. I'm not sure whether a metric or matcher should say if it supports skipping edges or not, I feel like that's more of a semantic question for users to answer about their GT and pred. Does their GT have skipping edges? Because if so, then their solution should (somehow, even if in post-processing), be augmented with these edges. It's up to them to define whether a skipping edge means "the cell was physically not visible at this time point" or whether it means "there may or may not be a cell there, but it doesn't matter because we've connected the lineage correctly".

Would we need to compute each metric with and without skipping edges of different lengths, similar to the "frame buffer" aka frame tolerance on divisions?

I think, no. I think we should not infer anything about the semantics of the solution. If there's an edge that skips 10 frames in the GT, we look for that edge in pred. If it's there, great. If it's not, then it's not, and we don't try to find an "equivalent" edge or set of edges (unless that's specifically how a specific metric is defined, like the divisions with frame tolerance).

Curious what you think. Am I missing something? Maybe would be good to have a couple of examples and see how they would affect our current metrics and implementations.

cmalinmayor commented 10 months ago

Presumably both ground truth edges would be considered True Positive edges, since they are both covered by the skipping edge?

I don't see a reason to make this assumption. I think if the GT has two edges connecting these three nodes, and we have just one edge connecting two nodes, then these are simply different solutions and they should be treated as such i.e. we should not do any reasoning about what constitutes a match.

@yfukai Since you have more experience evaluating with edges that skip frames, perhaps you can share how you've dealt with this kind of issue in the past? Are the skip edges just connecting nodes to maintain identity for questions like "Is this leaf node in the last time point connected to the correct cell in the first time point?" or would you expect to get "credit" for the intermediate ground truth edges as well?

Does their GT have skipping edges?

I hadn't considered situations where the GT would have skip edges. I assumed all skip edges were for correcting missed detections in the reconstruction, and I didn't think about situations where they would be a desired outcome. Are there situations where they would be a desired outcome? If a cell or particle leaves the FOV and then re-enters, we likely have no way to tell that it is the same cell/particle (even in the ground truth). But I guess in a task like tracking people in 2D video, one can feasibly detect if it is the same person in GT and reconstruction even after leaving and re-entering the FIV.

If we want to support GT having skip edges, then obviously @DragaDoncila is correct, we cannot assume that skip edges should mean that the object is present in the intermediate frames as well, as my suggestion did. Any skip edges that DO mean that should probably be interpolated prior to (or during) loading a solution into traccuracy.

Curious to hear what Yohsuke was thinking and get other opinions on what a skip edge does/could/should represent.

yfukai commented 10 months ago

Hi @cmalinmayor and @DragaDoncila, thanks for your consideration! I've been thinking about this, and let me share my thoughts. I hope I understand the point correctly, but please let me know if not.

Unfortunately, I didn't seriously consider those situations in my metric implementation for laptrack. However, it seems that I took the way @DragaDoncila mentioned: Not trying to find "equivalent" edges for a skipping edge but directly comparing the set of edges to calculate TP, FN, etc. The implementation wouldn't get complicated for the target effectiveness and track purity since we just need to compare the set of edges.

Are the skip edges just connecting nodes to maintain identity for questions like "Is this leaf node in the last time point connected to the correct cell in the first time point?" or would you expect to get "credit" for the intermediate ground truth edges as well?

I think it's not necessary to get the "credit" for the intermediate ground truth edges. The following arguments may support the idea:

The benefit of having those skip edges can already be seen in the metrics measuring cell identities.
It would be easier to interpret the result if the metric is as simple as possible.
There would be many arbitrary ways to credit the intermediate corresponding edges, and the selection would affect the score. Keeping the metric simple should somehow guarantee the "non-arbitrariness" of the metric.

Are there situations where they would be a desired outcome?

Those situations may be a bit rare, but I can imagine the following cases as examples of GTs having skip edges:

blinking particles: for example, some fluorescent dyes blink during observation. There may be cases where one would like to find edges jumping over a "dark" particle with some prior knowledge.
overlapping cells: in a 2D cell culture, sometimes a cell overlaps onto another one and then returns to the substrate. That cell may be missed in the segmentation, but one may like to keep the cell's identity.
3D cell culture: I think there are cases in which a cell escapes in the Z direction, but one can predict the cell identity with high probability using the arrangement of neighbor cells.

I hope this will be a help to decide the implementation direction!

cmalinmayor commented 10 months ago

@yfukai Thanks for your input! This helps a lot, and clarifies many of my questions. I'm on board with @DragaDoncila now - if we simply allow skip edges but don't treat them specially in any way, it shouldn't add much complexity. I think to implement this we just need to change the TrackingGraph documentation and validity checking, check the implementations of loaders, matchers, and metrics that depend on edges not skipping, and add test cases.

yfukai commented 10 months ago

Wonderful, thanks a lot for that @cmalinmayor and @DragaDoncila!

lupinthief commented 10 months ago

I see this may be closed now but when implementing a loader for my data (from vector rather than segmentation stack) I ran into this issue where I have skipped frames in my GT (and hopefully pred) tracks. This stems from the tracking domain spanning multiple asynchronous and partially overlapping scenes such that at some timesteps there just isn't data over some areas of the tracking domain. This may end up being a common situation for geospatial tracking using satellite data so great to see that it can be accommodated. I agree with the approach that allowing skip edges seems the least complex way forward. Thanks for implementing and I look forward to having a go.

Janelia-Trackathon-2023 / traccuracy