Signed Graph Partitioning: An Important Computer Vision Primitive

Fred Hamprecht, Heidelberg University

March 24, 2021


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.

Event Info

The event will take place on Wednesday, March 24, 2021 at 11:00am . It will be a joint event with the DKFZ Data Science Seminar and will take place online. You can join the live stream at this URL! Kindly help us plan ahead by registering for the event on our meetup page.