Exact optimization of discrete constrained total variation minimization problems

Authors

Jérôme Darbon, Marc Sigelle

Where

Proceedings of the 10th International Workshop on Combinatorial Image Analysis (IWCIA)

Place

Auckland, New Zealand

Type

inproceedings

Publisher

Springer-Verlag

Projects

Olena

Keywords

Image

Date

2004-09-01

Abstract

This paper deals with the total variation minimization problem when the fidelity is either the $L^{2}$-norm or the $L^{1}$-norm. We propose an algorithm which computes the exact solution of these two problems after discretization. Our method relies on the decomposition of an image into its level sets. It maps the original problems into independent binary Markov Random Field optimization problems associated with each level set. Exact solutions of these binary problems are found thanks to minimum-cut techniques. We prove that these binary solutions are increasing and thus allow to reconstruct the solution of the original problems.

Bibtex (lrde.bib)

@InProceedings{	  darbon.04.iwcia,
  author	= {J\'er\^ome Darbon and Marc Sigelle},
  title		= {Exact optimization of discrete constrained total variation
		  minimization problems},
  booktitle	= {Proceedings of the 10th International Workshop on
		  Combinatorial Image Analysis (IWCIA)},
  year		= 2004,
  address	= {Auckland, New Zealand},
  month		= dec,
  pages		= {548--557},
  editors	= {R. Klette and J. Zunic},
  series	= {Lecture Notes in Computer Science Series},
  publisher	= {Springer-Verlag},
  volume	= 3322,
  abstract	= {This paper deals with the total variation minimization
		  problem when the fidelity is either the $L^2$-norm or the
		  $L^1$-norm. We propose an algorithm which computes the
		  exact solution of these two problems after discretization.
		  Our method relies on the decomposition of an image into its
		  level sets. It maps the original problems into independent
		  binary Markov Random Field optimization problems associated
		  with each level set. Exact solutions of these binary
		  problems are found thanks to minimum-cut techniques. We
		  prove that these binary solutions are increasing and thus
		  allow to reconstruct the solution of the original
		  problems.}
}