Date and Location of the 18th Seminar

The seminar will take place on Tuesday, 2. May at 5pm in the conference room.

After the talks there will be food and cold drinks in the common room of Mathematikon (INF 205), 5th floor.

Speakers and Abstracts

This time the speaker will be Ruobing Shen with the titel "Gradient Multicut: A Second Derivative Potts Model for Segmentation Using MILP".




Unsupervised image segmentation and denoising are two fundamental tasks in image processing. Usually, graph based models such as graph cuts or multicuts are used for globally optimum segmentations and variational models are employed for denoising. Our approach addresses both problems at the same time.

A (depth) image can be seen as a function y: P-->R giving the (depth) intensity of pixels located on a finite 2-dimensional grid P. The segmentation problem is tackled by fitting a piecewise linear function f: P-->R to y minimizing sum_{p \in P} |f(p)-y(p)| with an additional L_0 regularization term to count the number of variations (with respect to segments) per row and column.

Previous attemps are usually based on continuous or convex relaxations. We propose a novel MILP formulation of a second derivative Potts model, where binary variables are introduced to directly deal with the L_0 norm.

The model approximates the values of pixels in a segment by an affine plane and incorporates multicut constraints to enforce the connectedness of segments. As a by-product the image is denoised.

Our approach could also be interpreted as non-parametric discontinuous piecewise linear fitting in 2D.

To the best of our knowledge, it is the first mathematical programming model for finding globally optimum solutions. Numerical experiments demonstrate its performance.