Jérôme Darbon
EPITA Research and Development Laboratory (LRDE)
1416 rue Voltaire F94276
Le KremlinBicêtre,France
Minimization of total variation (TV) under data fidelity is a popular image restauration technique [24]. It is wellknown that solutions live in the space of functions of bounded variation which allows for sharp boundaries [13]. However, in [7], Chan et al note that the minimizer generally presents a loss of contrast (this is mainly due to the use of fidelity). As a consequence they propose to replace it by . In this paper, we consider the minimization of TV under fidelity. We present new theoretical results (to our knowledge) of minimizers of this functional along with some new filters.
Suppose an image is defined on a rectangle of , we are interested in minimizing the following energy:
In [18], it is stated that a square cannot arise as a minimizer of (1). As a consequence, in [11,12], Dibos et al. propose an iterative algorithm to minimize TV where only graylevels of level sets are allowed to change while their shapes remain unchanged. Their algorithm relies on the topographic map [6] (also known as FLSTtree) which is a contrast invariant representation of the image and a tree. This tree can be efficiently built using the Fast Level Sets Transform (FLST) described in [20].
In this paper, we show that minimization of (1) yields a selfdual and contrast invariant filter. Then we follow the ideas of Dibos et al. by minimizing (1) under the supplementary constraint that shapes can only change their graylevels. The rest of this paper is as follows. In section 2, we show that TV minimization under fidelity is a selfdual and contrast invariant filter. We briefly present the FLSTtree in section 3. In section 4 we reformulate minimization on the FLSTtree and show that it corresponds to a Markov Random Field (MRF). A fast and exact minimization algorithm and some results are presented in section . Finally we draw some conclusions in section .
In this section we show that the minimization of the total variation under the norm as a data fildelity term yields a contrast invariant filter.
We first introduce the notion of level sets and change of contrast.
and
Lower level sets of will also be referred to as for convenience.
We define a continous change of contrast as follows [14]:
The same property holds for upper level sets.
We now reformulate (1) using the level sets of an image as described in [7,9]. The coarea formula states that for any function which belongs to the space of functions of bounded variation, we have for almost all
Using previous equalities, equation (1) rewrites as follows:
It is important to note that any term involves thresholded images and only. In other words, this decomposition rewrites (1) as a summation on all graylevels of quantities. Moreover, in [9,10], it is shown that one can independently optimizes every in order to minimize (1), and then to reconstruct the minimizer using (2). We are now ready to show that minimization of yields a contrast invariant filter.
Selfdual invariance is easily obtained.
These results of contrast invariance and selfduality are new to our knowledge.
In this section we briefly review the topographic map[6] which is built using the Fast Level Sets Transform. We refer the reader to [19,20] for a complete presentation.
The topographic map relies on simple inclusions of level sets. The family of lower and upper level sets are respectively increasing and decreasing, i.e,
These inclusion properties allow for a nonredundant and complete representation of an image into a tree, which will be referred to as FLSTtree for the rest of this paper. Basically, we consider connected components of level sets whose holes have been filled, referred to as shapes. A node of the FLSTtree corresponds to a shape. The parent of a node is the smallest shape that contains it while descendants are all shapes included into it. Because the FLSTtree considers both lower and upper level sets for inclusion, each shape is tagged to know if it comes from a lower or upper level set. Figure 1 depicts such a tree on a simple example. Thus, this tree decomposes an image into shapes , where is the root of the tree.
Many attributes associated to each shape can be computed. For the remaining of this paper we only consider attributes required to rewrite on the FLSTtree. Thus we need for each shape the following attributes:

Finally, note that the definition of the FLSTtree only involves level sets. Thus two images which differ only by a change of constrast give the structure of the tree (only gray level of shapes differs). The same property holds for self duality.
In this section we consider the FLSTtree of the observed image . Since, this tree is a complete representation of the image, we use it to reformulate the functional (1). Thus, we will minimize under the following new constraint: only gray level values of shapes are allowed to change. Boundaries of shapes do not move. In what follows, original and minimizer gray level value of a shape will be referred to as and respectively.
We first reformulate fidelity terms and the total variation term. Then we show that it is a Markov Random Field.
The idea relies on defining a partition of obtained using the FLSTtree. Such a partition is obtained as follows: for each shape we have kept pixels which are in but not in its descendants. Recall that such a set is denoted by . As a consequence the family is a partition of . Therefore data fidelity term can be rewritten as follows:
Using the shapes provided by the FLSTtree and the coarea formula (3), we rewrite the total variation as follows:
It only depends on the difference between the gray values of a shape and its parent weighted by the perimeter of the considered shape.
As a consequence, we are interested in finding a family which minimizes the following energy:
We briefly present an exact optimization algorithm for minimizing (5) and then present some results.
We are interested in minimizing exactly energy (5). Many algorithms are available to minimize it since this energy is convex. However this energy is not differentiable because of the use of absolute norm. Thus is it quite difficult to get an exact minimizer using gradient descent. Note that one could take benefit from the tree structure for this minimization, and use a Viterbilike algorithm as described in [25]. However, this is intractable because some nodes of the FLSTtree have too many children (typically more than 200).
We used the algorithm described in [10] which provides an exact global minimizer of energy (5) using a divide and conquer approach. Basically it uses the formulation in terms of level sets given in (4). Each term is discretized and it yields a MRF where only binary variables are involved. Exact solutions of these binary MRF are found thanks to minimumcut [16]. It is also shown that if two neighboring pixels at a level are different (i.e one is above and the other below), then they do not interact with each other anymore. Thus optimizations involving these pixels can be performed independently. This algorithm requires minimum cuts where is the number of gray levels (typically ). In practice, time required to perform a minimum cut is quasilinear with respect to the number of pixels [5].
We used the implementation of the FLST algorithm available in
the Megawave image processing library [17].
Time results (in seconds on a 3GHz Pentium 4) for the wellknown
lena image and for the two
images depicted in figures 2 and 3 are
presented in table 1.
Image 
FLST  Minimization 
Lena (256x256)  0.18  0.11 
Lena (512x512)  1.09  1.04 
Woman (522x232)  0.39  0.06 
Squirrel (209x288)  0.24  0.19 
We demonstrate on some examples that total variation minimization with data fidelity and constrained by the FLSTtree can be a good image simplification filter. In particular, experimental results show that it can be very useful as a preprocessing step for segmentation.
Figure 2 depicts minimizers for the image "woman" with different regularization coefficients . As one can see, the higher is the more the image is simplified. The background tends to become homogeneous and face details are removed, while the contrast is not lost. This is mainly due to the morphological behavior of the filter. Results suggest than these images can be used as good initial starts for a segmentation algorithm. Finally, only few regions remain when a very high is used. Level lines of such a minimizer are depicted in Figure 2 superimposed on the original image. Note that the boundaries do not move. This result shows that this filter behaves correctly even in the limit of strong weighted coefficient.
Figure 3 depicts minimizers for a textured image. On this image, the higher is the more the texture is removed. However, the background and the squirrel almost do not merge. They merge where the tail has a hole and where the tail is dark due to shading. Except from these two areas, results are very good. Note how well the separation between the two textured regions (background/squirrel) is, using a high . This latter result could be a segmentation result itself except for the two problems mentioned above, and also because the eye, being too small, is missed.

In this paper we have shown that minimizing the total variation under the norm as data fidelity yields a selfdual and contrast invariant filter. We have added a constraint such that boundaries of level sets cannot move. Experiments have shown that this filter behaves particularly well in order to simplify an image. This is mainly due to its morphological behavior. Moreover an efficient algorithm is available to perform the minimization.
Further extensions are considered. We could use other morphological trees like Min/Max trees as proposed by Salembier et al. in [26]. We are currently working on formalizing connected attribute opening/closing as a minimization process on these trees using our approach. Finally, extension of this method to vectorial selfdual mathematical morphology will be presented in a forthcoming paper.
This document was generated using the LaTeX2HTML translator Version 200221 (1.71)
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 Jérôme Darbon on 20060222