Global Solutions for Shape Optimization in Computer Vision

Daniel Cremers
University of Bonn

Graph cuts allow to compute globally optimal solutions to a number of Computer Vision problems such as image segmentation, 3D reconstruction and planar shape matching. In my presentation, I will discuss strength and weaknesses of the graph cut method and relate it to alternative global optimization methods. Firstly I will focus on the cases of image segmentation and multiview reconstruction where the binary labelling problems can be optimized globally in a spatially continuous setting by reverting to convex relaxations. I will discuss advantages of this continuous analogue of the graph cut solution in the light of metrication errors, memory requirements and efficient parallel implementations. Secondly, I will focus on the case of planar shape matching and compare a recent graph cut formulation to a recursive shortest path formulation. Thirdly, I will show that the combinatorial problem of elastically matching shapes to images can be solved optimally by shortest path techniques in appropriate higher-dimensional spaces, thereby allowing to impose elastic shape priors in a globally optimal segmentation method.

*This is joint work with Kalin Kolev, Maria Klodt, Thomas Brox, Selim Esedoglu, Thomas Schoenemann, Frank Schmidt, Dirk Farin and Yuri Boykov.

Back to Graph Cuts and Related Discrete or Continuous Optimization Problems