–
5.01.
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 art 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.