Directly to content
  1. Publishing |
  2. Search |
  3. Browse |
  4. Recent items rss |
  5. Open Access |
  6. Jur. Issues |
  7. DeutschClear Cookie - decide language by browser settings

MILP Formulations for Unsupervised and Interactive Image Segmentation and Denoising

Shen, Ruobing

PDF, English
Download (11MB) | Terms of use

Citation of documents: Please do not cite the URL that is displayed in your browser location input, instead use the DOI, URN or the persistent URL below, as we can guarantee their long-time accessibility.


Image segmentation and denoising are two key components of modern computer vision systems. The Potts model plays an important role for denoising of piecewise defined functions, and Markov Random Field (MRF) using Potts terms are popular in image segmentation. We propose Mixed Integer Linear Programming (MILP) formulations for both models, and utilize standard MILP solvers to efficiently solve them.

Firstly, we investigate the discrete first derivative (piecewise constant) Potts model with the ` 1 norm data term. We propose a novel MILP formulation by introducing binary edge variables to model the Potts prior. We look into the facet-defining inequalities for the associated integer polytope. We apply the model for generating superpixels on noisy images.

Secondly, we propose a MILP formulation for the discrete piecewise affine Potts model. To obtain consistent partitions, the inclusion of multicut constraints is necessary, which is added iteratively using the cutting plane method. We apply the model for simultaneously segmenting and denoising depth images.

Thirdly, MILP formulations of MRF models with global connectivity constraints were investigated previously, but only simplified versions of the problem were solved. We investigate this problem via a branch-and-cut method and propose a user-interactive way for segmentation.

Our proposed MILPs are in general NP-hard, but they can be used to generate globally optimal solutions and ground-truth results. We also propose three fast heuristic algorithms that provide good solutions in very short time. The MILPs can be applied as a post-processing method on top of any algorithms, not only providing a guarantee on the quality, but also seek for better solutions within the branch-and-cut framework of the solver.

We demonstrate the power and usefulness of our methods by extensive experiments against other state-of-the-art methods on synthetic images, standard image datasets, as well as medical images with trained probability maps.

Item Type: Dissertation
Supervisor: Reinelt, Prof. Dr. Gerhard
Date of thesis defense: 20 June 2018
Date Deposited: 26 Jul 2018 12:08
Date: 2018
Faculties / Institutes: The Faculty of Mathematics and Computer Science > Department of Applied Mathematics
The Faculty of Mathematics and Computer Science > Department of Computer Science
Subjects: 004 Data processing Computer science
510 Mathematics
About | FAQ | Contact | Imprint |
OA-LogoDINI certificate 2013Logo der Open-Archives-Initiative