Applicability to instance segmentation

[kevinjohncutler]

Hi @pmneila, I'm scoping out options for segmenting images based on affinity graphs (basically generated via DNNs, but much more convoluted than that), and I am wondering if maxflow can output labeled segments via get_grid_segments. From your reconstruction example, it looks like it just outputs a binary foreground/background designation for each node.

[pmneila]

Hi, @kevinjohncutler

Indeed, the max-flow (and min-cut) algorithm is designed to divide a graph into two separate sets, and get_grid_segments returns the nodes belonging to each set. This means that the output of the algorithm will always be binary.

That said, there are several ways to use max-flow for multi-label image segmentation. PyMaxflow, for instance, implements the alpha expansion and alpha-beta swap methods, as described in Boykov01 (pdf here), in its fastmin module. Note that this implementation has limitations, allowing only 4-pixel connectivity with uniform pair-wise costs.

Another simple approach is described in Ishikawa98, which involves assigning multiple graph nodes per pixel and transforming the binary output of max-flow into non-binary labels by determining which nodes of the pixel were assigned to the source or the sink sets.

However, in most cases, DNNs provide smooth segmentation labels and using max-flow to improve the results is unnecessary (though there are some exceptions where it may be helpful).

I hope this information helps. If you have any further questions, please let me know.

Best

[kevinjohncutler]

@pmneila Thank you for the info! Sounds like fastmin may not be adequate, as I would Ideally land on an approach that works on 8-connected pixels in 2D and 3^N-1 in ND. If I understand this right, these algorithms are aiming to solve the problem of graph partitioning when the edge weights are variable, and in a greyscale image segmentation context the edge weights are set according to the similarity between node/pixel values. I think I have an even simpler problem. My current segmentation algorithm, Omnipose, predicts a vector field which I recently realized can be processed into an affinity graph (roughly speaking, pixels whose flows form a 90 degree angle or less are assigned an affinity of 1). Because my affinity graph is binary, it seems a little overkill to define and solve an energy minimization problem - we can consider the starting point I have as the solution to the optimal set of pixel connections, and I just need to do the last step of grouping the pixels that form disjoint networks and assigning each group a unique label.

Ultimately it comes down to having a set of connected pixel indices (a,b),(b,c),(d,e),(e,f) and grouping them into subsets ((a,b),(b,c)) and ((d,e),(e,f)). You might have some insight on that last step, and maybe pymaxflow has a module that already handles this problem.

Edit: networkx has a fine connected_componenets implementation, and that's really what I need, assuming that alll the connections I have generated are correct. There is the issue, however, with even a single bad connection causing two otherwise disjoint subgraphs to merge into one. This gets back into some kind of paritioning optimization, even with binary edge weights.