Signed graph partitioning: why it is an important primitive in computer vision, and how to solve it efficiently

Video here

Perennial computer vision problems such as image partitioning, instance segmentation or tracking can be reduced to combinatorial graph partitioning problems. The majority of models developed in this context have relied on purely attractive interactions between graph nodes. To obtain more than a single cluster, it is then necessary to pre-specify a desired number of clusters, or set thresholds. A notable exception to the above is multicut partitioning / correlation clustering, which accommodates repulsive in addition to attractive interactions, and which automatically determines an optimal number of clusters. Unfortunately, the multicut problem is NP-hard.
In this talk, I will characterize the combinatorial problem and discuss its representations in terms of node or edge labelings. I will discuss greedy algorithms that find approximate solutions and do well in real applications, in particular the mutex watershed and greedy agglomerative signed graph partitioning.

Joint work with Steffen Wolf, Constantin Pape, Nasim Rahaman, Alberto Bailoni, Ullrich Koethe, Anna Kreshuk.

Fred Hamprecht develops machine learning algorithms for image analysis. He applies these methods to challenging problems mainly from bioimage analysis, and is particularly interested in making "structured" predictions. His favorite methods have a sound mathematical background, such as combinatorial optimization or algebraic graph theory, while being widely applicable and useful in practice.

Fred is a Professor at Heidelberg University and still thinks of science as the greatest profession on earth.

Contact