This webpage briefly presents some results on my work done with Marc Sigelle on total variation minimization. Note many more results are about to come; We are waiting for notification of submitted papers. So feel free to come and see this page.
Most of the results presented here have been published in [1] and [2].
Jérôme Darbon  Marc Sigelle
We assume that takes values in the discrete set and is defined on a discrete lattice . We denote by the value of the image at the site . We consider the thresholding images where . One can reconstruct the original image from its level sets using .
The coarea formula states that for any function which belongs to the space of bounded variation [3] one has almost surely. In the discrete case, we write , where is the perimeter of (notice that for every , which explains the previous summation up to .) Let us define the neighboring relationship between two sites and as . The associated cliques of order two are noted as . This enables to estimate the perimeter using the approach proposed in [5]. Thus we have , where is set to 0.26 and 0.19 for the four and eight connected neighborhood, respectively.
Proof: See [2]
Note that each is a binary MRF with an Ising prior model. To minimize one can minimize all independently. Thus we get a family which are respectively minimizers of . Clearly the summation will be minimized and thus we have a minimizer of provided this family is monotone:
Since the MRF posterior energy is decomposable into levels, it is useful to define the ``local neighborhood configurations'': and .
In other words, given a binary solution to the problem , there exists at least one solution to the problem such that .
Clearly both + TV and + TV models enjoy this convexity property and satisfy thus the conditions of application of our Lemma.
Although the previous section proves that the monotone property holds, it does not provide an algorithm to compute a solution. Our algorithm makes use of the formulation shown in equation 2 which allows independent optimizations.
We use a divide and conquer based algorithm to minimize the energy. Such an approach requires to decompose a problem into smaller ones, then to solve these subproblems and to recombine the subsolutions to get an optimal solution. Our algorithm takes benefit of the following. Suppose we minimize at some level . Then, for all pixels of the minimizer we know whether they are below or above . Thus it is useless to take into account pixels above for further optimizations which only allow pixels to be lower than . Obviously, the same holds for pixels which are below . Then, every connected component (it defines a partition of the image) of the minimizer can be optimized independently from each others. The latter corresponds to the decomposition of the problem into subproblems. Once minimizers of subproblems are computed, they are recombined to yield an optimal solution. The recombination is straightforward since the decomposition was a partition.

A good choice to choose the threshold level is to use a dichotomic process. For instance, suppose the minimizer is a constant image, then our algorithm requires exactly (we suppose is a power of two) binary optimizations to compute it. The following table presents some time results (in seconds) on a pentium 4 3GHz.
Consequently, our algorithm is quasilinear with respect to the number of pixels of the image and proportional to .
Some results for for the image "woman". Results for different are presented.
Some results for L2 + TV are about to come...
We have presented an algorithm which computes an exact solution for the minization of the total variation under a convex constraint. The method relies on the decomposition of the problem into binary ones using the level sets of an image. Moreover, this algorithm is quite fast. Comparison to other algorithms with respect to time complexity must be made. Extension of this method to other type of regularization is in progress.
This document was generated using the LaTeX2HTML translator Version 200221 (1.70)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html split=1 ./article.tex
The translation was initiated by DARBON Jerome on 20050207