Living Lab Lecture No. 18: Graph Multi-Cuts and Image Analysis

In this lecture we learn how graph theory and combinatorial optimization can be used to solve problems from the field of image analysis. We consider the challenging task of segmenting a three dimensional volume image of an electron microscopy scan of a mouse neocortex. The state of the are method for solving this segmentation problem consists of a convolutional neural network and a post-processing step which involves solving the graph multi-cut problem. We will see how segmenting an image can be understood as a problem of cutting a graph into multiple components. The optimal multi-cut can be found by means of integer linear programming. This method, however, does not scale to large instances. To address this problem, we present a second algorithm that finds a good but not necessarily optimal solution efficiently. Finally, we will see that the multi-cut problem and algorithms have further applications beyond image segmentation.