Getting the weights between super nodes in an EdgeContractionGraph

[alexandre01]

In order to reimplement the paper "SSAP: Single-Shot Instance Segmentation With Affinity Pyramid" (https://arxiv.org/abs/1909.01616), I'm defining a lifted multicut objective on an UndirectedLongRangeGridGraph with 5x5 neighborhood adjacency.

This works very well, however, to improve the efficiency of this procedure, the paper proposes a pyramidal propagation approach, starting from a very coarse resolution map and propagating the segmentations to finer grained maps. This means pixels that are inside of segments in a coarse map are upsampled and set as fixed for the finer resolution map, so that the associated graph nodes are merged into one super-node. I'm doing this by contracting the edges between the nodes to merge, e.g. with the following piece of code:

edges = g.edgesFromNodeList( nodes_to_merge )

cg = nifty.graph.edgeContractionGraph( g, callback )
for e in edges:
    u, v = g.uv( e )
    cu = cg.findRepresentativeNode( u )
    cv = cg.findRepresentativeNode( v )
    if cu != cv:
        ce = cg.findRepresentativeEdge( e )
        cg.contractEdge( ce )

However, since the graph doesn't include any weight information, how can I ensure that the new weights between two super-nodes are the sum of the weights between their included nodes?

Thanks for your help!

[constantinpape]

I have implemented a helper class for this a while back in nifty.tools. In this case, you could use it, after you have merged the graph, like this:

node_labels = np.array([cg.findRepresentativeNode(u) for u in range(g.numberOfNodes)])
merger = nifty.tools.EdgeMapping(g.uvIds(), node_labels)
new_weights = merger.mapEdgeValues(weigths, "sum")  # also supports "mean", "min", or "max"
assert len(new_weights) == cg.numberOfEdges  # make sure the results are consistent

Note that I fixed some bugs in this function not too long ago, so I would recommend using an up-to-date version of nifty if you run into any issues with this.

[constantinpape]

Btw, I would be super interested in seeing this:

In order to reimplement the paper "SSAP: Single-Shot Instance Segmentation With Affinity Pyramid" (https://arxiv.org/abs/1909.01616)

Is it open source / would it be possible to make it open source at some point?

[alexandre01]

@constantinpape What I implemented this morning was using the callback functions to sum weights whenever two edges are merged, but this is a really neat (nifty?) solution! Thank you 👍 👍 !

While I doubt that the SSAP authors will make their code available, the work I'm currently doing (and which is partially using/extending this idea) will be open sourced upon acceptance of the paper!

[constantinpape]

What I implemented this morning was using the callback functions to sum weights whenever two edges are merged

That's also a good solution, because it's very flexible. For the simple use-case of just keeping track of the sum, the helper function will do the trick though (and I use it in production, so it's decently tested).

While I doubt that the SSAP authors will make their code available, the work I'm currently doing (and which is partially using/extending this idea) will be open sourced upon acceptance of the paper!

Great, please let us know once you have made it public :).