Grain Filters.
Motivated by operators simplifying the topographic map of a function, we study the theoretical properties of two kinds of grain filters. The first category, discovered by L. Vincent, defines grains as connected components of level sets and removes those of small area. This category is composed of two filters, the maxima filter and the minima filter. However, they do not commute. The second kind of filter, introduced by Masnou, works on shapes, which are based on connected components of level sets. This filter has the additional property that it acts in the same manner on upper and lower level sets, that is, it commutes with an inversion of contrast. We discuss the relations of Masnou's filter with other classes of connected operators introduced in the literature. We display some experiments to show the main properties of the filters discussed above and compare them.
Introduction
Filters used to simplify an image and satisfying a minimal set of invariance
properties are scarce. Actually, only one of them has the maximal
set of invariance properties, and it is driven by the parabolic partial
dierential equation [1, 26, 18]:
@t
where curvu(x) is the curvature of the level line of u at the point x,
this being restricted to the regular points of u.
However, the previous lter is optimal (in terms of invariance) among
regular lters, that is, lters driven by a P.D.E. This property
of regularity, while desirable in theory, has the drawback of modifying
all contours, and, in particular, of destroying T -junctions, which are
important clues for occlusion [5, 4]. If we drop this requirement, a bunch
of other lters satisfying the same invariance properties are available.
Motivated by the study of a family of lters by reconstruction [9,
10, 21, 31, 32], Serra and Salembier [30, 25] introduced the notion of
http://pascal.monasse.free.fr
c
2001 Kluwer Academic Publishers. Printed in the Netherlands.
V. Caselles and P. Monasse
connected operators. Such operators simplify the topographic map of
the image. These lters have become very popular in image processing
because, on an experimental basis, they have been claimed to simplify
the image while preserving contours. This property has made them very
attractive for a large number of applications, such as noise cancellation
or segmentation [17, 33]. More recently, they have become the basis of a
morphological approach to image and video compression [23, 24, 22, 6].
Dierent classes of connected operators have been studied by Meyer
[15, 16], Serra [29] or Heijmans [8] (see also references therein).
In this article, we study the theoretical properties of two kinds of
connected operators: the extrema lters and the \shape" lters. Each
of them simplies the topographic map of the image, but with dierent
senses given to the term topographic map. The maxima lter removes
connected components of upper level sets of insu-cient area, while
keeping the other ones identical [31, 32]. This ensures that regional
maxima of the ltered image have a minimal grain size. Similarly,
the minima lter removes too small connected components of lower
level sets. For these lters, the \grain" corresponds to a connected
component of a level set, and small grains are considered as noise. This
can be seen as the pruning of the tree of the connected components of
upper, or lower, level sets.
In a previous work [3], we introduced the notion of \shapes", designed
to deal symmetrically with upper and lower level sets. The
shapes are also organized in a tree, driven by inclusion. When applied
to images of positive minimal grain size, we showed that the structure
of this tree is nite. As shown here, any image resulting from the
application of the extrema lters has this property. This new tree also
provides the denition of another grain lter, for which the grain is a
shape [13, 19, 20]. It removes small shapes while preserving the ones
of su-cient area. The essential improvement over the extrema lters is
that it deals in the same manner with upper and lower level sets. In
the vocabulary of mathematical morphology [14, 27, 28], this lter is
selfdual when applied to continuous functions.
The present article is organized as follows. Section 2 recalls the foundations
of mathematical morphology and underlines the link between
morphological lters and set operators. Section 3 introduces the main
properties of extrema lters and proves them. In Section 4 we prove
the analogous properties for the grain lter and, in particular, that it
is a self-dual lter on continuous functions, generalizing a result of [2].
Finally, in Section 5 we illustrate these lters with an experiment.
2. General results from mathematical morphology
Throughout this section, we shall consider real functions dened in a
subset of IR N . If u is a real function dened on D  IR N , we denote
by [u  ] the set fx 2 D : u(x)  g,  2 IR. Similarly, we dene the
sets [u > ], [u  ], [u < ].
2.1. Level sets
If u is any real function, and X
which implies, in particular, that
Conversely, if X  is a family of sets satisfying
then X  is the level set at level  of the function u dened by
namely, X
Under the weaker hypothesis of monotonicity of (X  ) 2IR , Guichard
and Morel show in [7] that X  a.e. and for almost every  2 IR.
2.2. Contrast invariance
A contrast change, in the restrictive sense, is a strictly increasing continuous
IR. It is therefore a homeomorphism of IR onto
an open interval of IR. A direct consequence is
For an image u, the contrast change g applied to u is g-u. A contrast
change g will indierently be considered as a function dened on IR or
as an operator acting on functions u. A direct consequence of (1) is
which can also be written as
4 V. Caselles and P. Monasse
showing that the families of level sets of g - u and of u are the same,
only their level changes.
A morphological lter ~
T is a map acting on functions u that commutes
with any contrast change: g - ~
g.
2.3. Link between set operator and morphological filter
If T is an operator acting on sets, a necessary requirement for T to
transform the level sets of a function into the level sets of a function is
thus
The lter ~
T associated to T is dened by
or equivalently
~
If we denote by B then we observe ([11, 12]) that
~
Indeed, let ~
be the right hand side term of this equality. If  is
such that x 2 T ([u  ]), by denition of B x we deduce that [u
on the other hand, since
u(y)
we get immediately ~
Tu(x). Conversely, if
u(y)  n
That is, B n  [u   1=n] and, therefore,
Taking the intersection over all n, we get that x 2 ~
~
We say that contrast change if g is nondecreasing
and upper semicontinuous. For a general contrast change, we
have that
where
We use the convention
If T is only dened on closed sets and satises (2) when the sets
F n are closed, then ~
T is dened on upper semicontinuous functions.
Then it is easy to check that ~
T and g commute when applied to upper
semicontinuous functions. We get contrast invariance in a strong sense,
since g can have constant stretches, and needs not be continuous.
2.4. Spatial invariance properties
If D  IR N , f : D ! D is a map and ~
T a morphological lter, whose
associated set operator is T , and whose structuring elements are given
by the family B x at x, we denote by f ~
T the morphological operator
dened by (f ~
and we dene ~
by ( ~
is an image.
g. If f(B x is easy to see
that f ~
. Then we say that T is invariant with respect to f . For
instance, if B
T is translation invariant.
The lters we shall discuss below satisfy the property that their
respective family of structuring elements is globally invariant with respect
to any area preserving map, i.e., a special a-ne map. These lters
are thus special a-ne invariant. They depend on a parameter ". If
x
is the set of structuring elements of such a lter at x, they also satisfy
that B s"
x for any s > 0. In particular, this implies that, for any
a-ne map f , we have
f ~
3. Extrema lters
3.1. Definition
Extrema lters are constructed in such manner that the connected components
of level sets of an image have a minimum area. We call them
extrema lters because a connected component of level set contains
a regional extremum. This is achieved in two steps: rst, connected
components of upper level sets are ltered, then lower level sets. We
dene the set operators ensuring such properties.
Let us rst x some notation.
Let
be a set homeomorphic to the
closed unit ball of IR N (N  2),
and
be the
6 V. Caselles and P. Monasse
interior of
Note that, in
particular,
is compact, connected and
locally connected.
Moreover,
is unicoherent, i.e., for any A; B
closed connected sets such that
A\B is connected. For a set
X, we denote cc(X) any of its connected components and by cc(X; x)
the one containing the point x, provided x 2 X, and by extension
and C is connected, cc(X; C) is
cc(X; x), with x 2 C.
" be a parameter, representing an area threshold, and let X be
a subset
of
. We dene the lters
"g. We dene the maxima lter M
" and
the minima lter M " by
sup
We will show that they are morphological lters, whose associated set
operators are M " and M 0
" , respectively. The denitions are voluntarily
not symmetric, so that both can act on (upper) semicontinuous func-
tions. To avoid the cases where
suppose that " <
j.
3.2. Preliminary results
LEMMA 1. If (C n ) n2IN is a nonincreasing sequence of compact sets
and
If (O n ) n2IN is a nondecreasing sequence of open sets and O
then
Proof. It is clear that cc(C; x)  cc(C n ; x) for any n. Conversely,
is an intersection of continua, thus, it is a continuum.
Since it contains x and is included in C, we get the other inclusion.
For any n, cc(O
On the
other hand, O being open
and
locally connected, cc(O; x) is an open
set. Hence, for any y 2 cc(O; x), there is some continuum K y  cc(O; x)
containing x and y. Since K y  S
O n and it is a compact set, we
can extract a nite covering of K y , and as the sequence (O n ) is non-
decreasing, there is some n such that K y  O n . Since K y is connected
and contains x, we have that y 2 K y  cc(O n ; x). We conclude that
PROPOSITION 1. We have the following properties for M " and M 0
" are nondecreasing on subsets
of
.
upper semicontinuous on compact sets: being a non-increasing
sequence of compact sets, then M "
" is lower semicontinuous on open sets: (O n ) n0 being a nondecreasing
sequence of open sets, then M 0
" O n .
Proof. Property (i) is a direct consequence of the denitions.
" is monotone, we have that M " F
Applying Lemma 1, we observe that
cc(F; x). In particular,
O n . Since M 0
" is monotone, S
" O. Now, let
" O. Then is such that jU j > ". Let U
Lemma 1 proves that
". Hence for n large enough, jU n j > ". We
conclude that x 2 U n  M 0
" O n .
If A and B are two families of sets, we say that A is a basis of B if
A  B and for any B 2 B, there is some A 2 A such that A  B.
2. B " is a basis of fX
" is a basis of
" Xg.
Proof. This is a direct consequence of the denitions.
COROLLARY 1. Applied to upper semicontinuous functions, M
morphological lter whose associated set operator is M "
8 V. Caselles and P. Monasse
precisely, for all ,
"
Proof. Let Xg. A consequence of Proposition 1
we have (
u(y)
We now use the fact that B " is a basis of C " , as shown in Lemma 2. As
we deduce that
u (x)  sup
there is some
u(y)  inf
"
and by taking the supremum over all B, we get
sup
u
A similar proof applies to link M " and M 0
" .
PROPOSITION 2. Let u; v
IR. Then
"
(ii) If u  v, then M
"
" v.
The proofs are immediate and we will not include the details.
COROLLARY 2. Let u
IR be such that u n ! u uniformly
in
. Then M
" uniformly
in
.
Proof. Given - > 0, let n 0 be such that u -  u n
Using Proposition 2, (ii), (iii) and (iv), we obtain
for all n  n 0 . Hence uniformly
in
. Similarly,
we prove that M +
" uniformly
in
.
3.3. Properties
PROPOSITION 3. If u is an upper semicontinuous function, also are
" u. If u is continuous, also are M
" u.
Proof. Let u be an upper semicontinuous function. Then, for any
" As [u  ] is a closed set, its connected
components are closed. Since M " [u  ] is a nite union of some of
them, it is closed. Thus M
" u is upper semicontinuous.
In the same manner, [M " u <
is an
open set, its connected components are also open, and its image by M 0
is thus a union of open sets, which is open. This proves that M " u is
upper semicontinuous.
Finally, suppose that u is continuous. We just have to prove that
" closed for any  2 IR. Using Corollary 1, we write
"
"
We claim that
If
C). Since O is open and contains the closed set C, we deduce that
O n C is open and not empty, and, thus, of positive measure. Hence
jOj > jCj  ". This proves that
be such that jOj > ". Then, thanks to
Lemma 1, we have
V. Caselles and P. Monasse
There is some n such that
". This proves the remaining
inclusion in (). The right hand side of this equality being open, we
conclude that [M
" closed.
To prove the same result for M " , we write
We claim that the last set coincides with "g. If
O n is open and C is closed, we have that "  jCj < jO n j. Hence,
n ] for all n. Then we have
Applying Lemma 1, we get
yielding
Hence jcc([u  ];
This proves that
and, thus, the equality of both terms. The right hand side term, being
a nite union of closed sets, it is also closed.
PROPOSITION 4. When restricted to upper semicontinuous function-
s, M
" is idempotent.
Proof. Let u be an upper semicontinuous function and  2 IR.
Clearly, we have . Applying this equality to the set
[u  ], and using Corollary 1, we get
"
"
Now, thanks to Proposition 3, we have that [M
" closed and
we can apply again Corollary 1 to the left hand side of this equality to
obtain
"
"
Since this equality holds for any  2 IR, we conclude that M +
" .
The same proof applies to M " .
PROPOSITION 5. Let u 2
Proof. (i) Both cases being similar, it will be su-cient to prove the
rst part of the assertion. Let
" u(x). Observe that v
is lower semicontinuous. Assume that M := max
0be such that
contains an open set, hence,
Letting choosing
Mwhich is a contradiction. We conclude that and the proposition
is proved.
(ii) Both cases being similar, we shall only prove that M +
uniformly as " ! 0+. For that, let us write
"
"
Given - > 0, let " 0 > 0 be small enough so that
V. Caselles and P. Monasse
and
"
"
i.e.,
Collecting these facts we have that
3.4. Interpretation
Let u be an upper semicontinuous function and
jCj  ", we have thus, C is a connected component
of
" C is not
a connected component of [M
" u  ]: it does not even meet this set,
since [M
" so that
"
Conversely, if
" u  ]), we have
being a connected component of [u  ], and since C 6= ;,
we have
Summing up these remarks, we can see that the connected components
of [M
" are exactly the connected components of [u  ] of
measure  ". In particular, since the connected components of upper
level sets have a structure of tree driven by inclusion, the tree of M
"
is the tree of u pruned of all nodes of insu-cient measure.
The same observations can be made concerning M " and the connected
components of [u < ]. The tree of M " is the tree of connected
components of lower level sets of u pruned of all nodes of insu-cient
measure.
Summarizing the above discussion, we have the following result.
PROPOSITION 6. If
" u  ]) 6= ;, then jXj  . If jcc([u  ])j   (resp.
" u < ])j
In particular, the above result implies that the connected components
of [M
". The
same thing can be said of connected components of the upper and lower
level sets of
" u.
3.5. Composition
LEMMA 3. Let u be an upper semicontinuous function and  2 IR.
Then
Proof. Let
" u < ]). If the consequence was false, we
would have C  [u  ]. If
then we have
"
since
This contradicts the denition of C. If C
, C being
open, we have C ) C and @C  [M
"
Then x belongs to a connected component D of [u  ] such that
connected and included in [u  ]. As
jD[Cj  ", we get D[C  [M
" contradicting the denition of
C. This proves our claim that there is some x 2 C such that u(x) < .
arguing as above, we have
which contradicts the
hypothesis. Thus, we may assume that C
. Let
Since C is closed and D open, then C ( D. Thus there is some x in
meaning that
jcc([u < ]; x)j > ". This component must be D and, therefore jDj > ".
Finally, we observe that D  [M " u < ], which is a contradiction.
THEOREM 1. The operators M
(i) transform upper semicontinuous functions into upper semicontinuous
functions, and continuous functions into continuous functions;
(ii) are idempotent on upper semicontinuous functions.
Proof. (i) is a direct consequence of the equivalent properties we
have proved for
" and M " in Proposition 3.
As a consequence of Proposition 2, we have
"
any function u. Applying this to M
of u, we get
14 V. Caselles and P. Monasse
We apply the rst part of Lemma 3 to
that
We nd a point x 2 C \ [v < ]. Let
We know that jDj  ". Since M
that D  [M
and D is connected, we have
This proves that
thus, we have the
equality
" to each member and
using its idempotency, we conclude that
With a similar proof, using the second part of Lemma 3, we prove
that
" is idempotent.
4. Grain lter
4.1. Definitions
The problem with the extrema lters presented above, is that we have
two operators which act on both upper and lower level sets. In general,
they do not commute. Moreover, none of them has the property to deal
symmetrically with upper and lower level sets. Actually, they work
in two steps: rst upper, then lower level sets are treated (or in the
opposite order). That is, these operators are not selfdual.
DEFINITION 1. A morphological lter ~
T , associated to the set operator
T , is said to be selfdual on continuous functions if the following
equivalent properties hold for any continuous function u
1. ~
2. 8x, sup B2B inf y2B describing the
structuring elements of ~
T .
3. 8, T [u
To show the equivalence of the rst two properties, it su-ces to write
the second one with u instead of u. By taking  instead of , we
can see that the third property is equivalent to
Now, using the contrast invariance of ~
amounts to write
which means exactly that ~
Tu.
We recall the denition and the essential properties of a saturation
operator.
DEFINITION 2. Let p 1 be a xed point
of
. For X
, we call
holes of X the connected components
of
X. The external hole of
X is
X. The other holes are the internal holes
of X. The saturation of X, Sat(X), is the union of X and its internal
holes.
The following results are proved in [3]:
PROPOSITION 7.
1.
2.
3. X connected ) Sat(X) connected and
connected

4. X open (resp. closed) ) Sat(X) open (resp. closed).
5.
closed
6. @Sat(X) is a connected subset of @X.
7. H internal (resp. external) hole of X
8. are nested or disjoint.
9. Let X be open or closed,
X) such that x 2 Sat(O)  Sat(C).
If u is an upper semicontinuous function, we call shapes of u the elements
of
The tree structure of u is expressed by the properties [3]:
.
are nested or disjoint.
V. Caselles and P. Monasse
We restrict the denition of our set operator to closed sets, since
later we will dene our lter on upper semicontinuous images. If K is
a compact set, we dene
f
internal hole of C; jC 0
j, we clearly have that G " compact K. Thus
we will always suppose that "
j.
Remark. We have dened the grain lter for compact sets since this
will be su-cient for the extension of this lter to upper semicontinuous
functions in
Obviously, the denition has sense for any subset of
4.2. Preliminary results
LEMMA 4. G " is nondecreasing on compact sets.
Proof. Let K  L be compact sets. Let be such that
be the family of internal holes of C such that
". Then we observe that there is some C
On the other hand, if H 0 is an internal hole of C 0 such that
included in a hole H of C, and, thus, jHj > ".
From these observations we deduce that
i , are the families of internal holes of C, resp. C 0 ,
whose measure is > ". We conclude that G " K  G " L.
LEMMA 5. If K is compact, then
Proof. Let us denote by (C i ) i2I the family of connected components
of K and let I "  I be the set of indices for which jSat(C i )j  ".
monotone, we have that S
the
other inclusion is immediate from the denition, we have the identity
We also observe that G " C i , if not ;, is the union
of C i and some of its internal holes and, thus, it is connected.
Let J be a subset of I " whose cardinal is at least 2, and let
. We now prove that D is not connected.
not connected, there is an open and closed
subset E 0 in D 0 dierent from ; and D 0 . Observe that E 0 is an union
of C j , since each of those sets is connected. To be precise, let us write
We prove that E
is open and closed in D, hence, D is not connected.
Clearly, we have that ; 6= E ( D. Since E 0 is open in D 0 , there is
an open set U 0 such that U 0 \ D
the union of the connected components of U 0 that meet some C l , l 2 L.
The set U 00 , as a union of open sets, is open, and the set U , as the
union of U 00 and some internal holes of C l , which are all open, is also
open. If j 2 J nL, we have that E\G "
Indeed, if the last equality does not hold, we would have
There is a connected component O of U 0 meeting some C l , l 2 L (by
denition of U 00 ), and C j . Indeed, if it meets some hole H of C j with
jHj  ", then H cannot not contain C l . Otherwise, since H n Sat(C l )
is open and not empty, thus of positive measure, we would have jHj >
l )j  ". Thus O is connected and meets two dierent connected
components
of
and the component containing C l ), hence
O \ C j 6= ;. This implies that U 0 \ C j 6= ;, contradicting the identity
We conclude that () does not hold, i.e., U 00 \G "
and therefore U 00 \ (D n E) = ;, proving that U \ We have
shown that the set E is open in D. Applying the same argument to
of D we prove that E is also closed in D.
LEMMA 6. Let (C n ) n2IN be a nonincreasing sequence of continua and
n C n . If H is a hole of C, there exists n 0 2 IN and a non-decreasing
sequence being a hole of C n , such that
Proof. If x 2 H, then there is some n 0 such that x 62 C n for n  n 0 .
Thus, if n  n 0 , x is in some hole H n of C n . Obviously, H n  H, and
therefore S H n  H.
U be a neighborhood of y and V be a connected
neighborhood of y such that V  U . Since y 2
H n there is some
and, by monotonicity of (H n ), we may write
nnn H n , we also have that
V. Caselles and P. Monasse
From () and (), the connectedness of V implies that
It follows that V \ C 6= ;, which implies
that U \ C 6= ;. This being true for any neighborhood U of y, we get
that y 2
@
This implies that H \ @
H n is closed
in H. Since it is also open, as a union of open sets, the connectedness
of H implies that
THEOREM 2. The operator G " is upper semicontinuous, i.e., if (K n )
is a nonincreasing sequence of compact sets, then
Proof. The inclusion of the left hand side term into the right hand
side one is due to the monotonicity of G " . We just have to show the
other inclusion.
As of Lemma 5, for any n, there is some
. For each n  1, C n is inside some
implying, due to Lemma 5, that This shows that the sequence
of continua (C n ) is nonincreasing, so that their intersection C
is a continuum, thanks to Zoretti's theorem. Since C is contained in
some component of T
remains to show that x 2 G " C.
By taking H
proves that H
so that
. Thus jSatCj  ". Moreover, if x belongs to
some internal hole H of C, since x 2 G " C n , the associated sequence H n
obtained from Lemma 6 is such that jH n j  " and thus
". Hence x
4.3. Properties
LEMMA 7. If A is a closed set, C a connected component of A and
H an internal hole of A, then, for any x in H,
G:
Proof. The right hand side term of this equality, H 0 , is obviously
contained in H. Suppose this inclusion is strict. The set H being connected
and H 0 being open (as a union of open sets), H 0 is not closed
in H, so that H \ @H 0 6= ;. Let y 2 H \ @H 0 and let U be a connected
neighborhood of y. We claim that U\A 6= ;. Otherwise, we would have
U
A, and as U meets some
n A with U [ G 0 being
connected, contradicting G
A). We conclude that y 2 A.
Then there is some G
Since G is an open set, it contains some neighborhood of y 2 @H 0 , in
particular, it meets some G
n A)) such that x 2 G 00  H.
Thus G and G 00 are nested, and, as G 6 H 0 , we have that G 00  G.
Thus, x 2 G and G  H, implying that G  H 0 , which contradicts our
assumption since y 2 G. We conclude that H
LEMMA 8. Let A; B
be closed sets.
Proof. Suppose that A and B are disjoint. Taking components of A
and B instead of A and B, we may assume that A and B are connected.
The result being obvious if G " A, or G " B, is empty, we may also assume
none of them is empty. Then Sat(A) and Sat(B) are either nested or
disjoint. If they are disjoint, since G " A  Sat(A) and G " B  Sat(B),
(5a) is obvious. If they are nested, without loss of generality, we may
assume that Sat(A)  Sat(B). Then Sat(A) is inside a hole H of B.
We get that jHj  jSatAj  ". Since Sat(A) is closed and H is open,
is an open and nonempty set, thus, it has positive measure.
This yields jHj > ", and therefore Sat(A) \
(5a).
Now, we suppose that A [
Let x 62 G " A. In particular,
this implies that Sat(C)
for any C = cc(A). For any such set C,
n SatC is connected, and also
is
n SatC, which is a compact set.
By Lindelof's theorem, the intersection of a family of continua can be
written as the intersection of a sequence of them. We can thus nd a
sequence (C n ) of connected components of A such that
V. Caselles and P. Monasse
Let D
Clearly, (D n ) is a nonincreasing sequence of
continua, and we may write
which is thus a continuum D. We observe that D  B. Indeed, if
y is in some connected component C of A. Since
yn Sat(C), obviously we have that y 2 @Sat(C)  @C. Now, we
prove that any connected neighborhood U of y meets a point
of
A.
Otherwise, C[U  A would be connected, which, in turn, implies that
U  C.
Since
n A  B, we conclude that y B, a contradiction
with our choice of y. This proves that D  B. We also observe that
, and, thus, jSat(D)j  ".
one of the following cases happens:
(iii) There is some such that x 2 Sat(C) and jSat(C)j  ".
Suppose that (i) holds. Then x 2 D. Since jSat(D)j  ", we have
Suppose that (ii) holds. Let D be the set dened above. If x 2 D
we have again that x 2 D  G " D  G " B. If x 62 D, then x is in a hole
H of D. Thanks to Lemma 7, we can write
G:
Thanks to Lindelof's theorem, this union of open sets can be written
as the union of a sequence G n of these sets. For each n,
Since
that G 0
and we obtain that jG n j  jSat(C)j < ". We conclude that
sup n2IN jG n j  ". Thus x 2 H  G " D  G " B.
Finally, we suppose that (iii) holds. Let
C:
We claim that being a connected component of A.
If there is a nite number of sets E in the intersection above, the result
is just due to the fact that they are nested. If there is an innite number
of such sets E, we can write their intersection as the intersection of a
sequence E n of them, thanks to Lindelof's theorem. By taking T n
instead of E n , we may also assume that this sequence is nonincreasing.
The set T is therefore a continuum and jT
connected neighborhood of y. Since U 6 T , so
there is some n such that U n E n 6= ;. Since U is connected and meets
its complement, U also meets @E n  @A  A. We obtain that
A. This shows that @T  A. On the other hand, we observe
that the complement of T is connected, being the union of an increasing
sequence of connected sets. Thus @T can be written as the intersection
of two continua, thus, it is connected,
since
is unicoherent. Thus,
there is some T such that @T  T 0 , and this implies that
jEj  ", we have that T 0 \E 6= ;, and, therefore, sat(T 0 )  E. It follows
that Sat(T 0 )  T. We have, thus, the equality
Now, observe that x must be in a hole H of T 0 and we must have
jHj > ", since otherwise x A. Using Lemma 7, we write
G;
and, as above, we may write the above union as the union of a non-decreasing
sequence of such sets G n . Thus there is some n such that
". We write G
n . If x is in a hole H 0 of
contained in a connected component K of A and
". In this case, we
also have that x
n . Since G 0
n is contained in some connected
component K 0 of B, we get that x
THEOREM 3. Restricted to continuous functions, ~
G " is selfdual.
Proof. We shall prove that condition 3 of Denition 1 holds.
According to (5a), we may write for any  2 IR,
and, since G " [u
n ], by taking the intersection
over all n, we get
Therefore
22 V. Caselles and P. Monasse
let x be such that for all n > 0, x
Due to (5b),
we have that x 2
This proves that
and, thus,
By taking the complement of each part, we get:
which proves that
and, actually, we have the equality of both sets.
THEOREM 4. ~
semicontinuous functions into upper
semicontinuous functions and continuous functions to continuous functions

Proof. We have to show that the image of a compact set K is a
compact set. Let sequence of points of G " K converging to
x. We shall prove that x 2 G " K.
As shown by Lemma 5, x n belongs to some G " K n , where K
cc(K). If the family fK n ; n 2 INg is nite, we can extract a subsequence
of belonging to some G " K n 0
, which is a closed set since its
complement is a union of holes of K n 0
, and the holes are open sets.
Thus, x
. We may now assume that fK n ; n 2 INg is innite,
and, maybe after extraction of a subsequence, that Km \ K
any m 6= n.
We have that Sat(G " K n only a nite number of
these saturations are two by two disjoint, since each of them has measure
at least ". Thus, after extraction of a subsequence, if necessary, we
may assume that they all intersect, so that they form either a decreasing
or an increasing sequence.
If the sequence (Sat(K n )) n2IN is decreasing, then their intersection
is a set Sat(K 0 ), cc(K). This can be shown as in Lemma 8. Then
we have that jSat(K 0
(otherwise, we would have K su-ciently large n), and
contained in a hole of K n for
any n, thus x n 62 Sat(K 0 ) for any n. Since x 2 Sat(K 0 ) we conclude that
the desired result.
Let us assume that (Sat(K n )) n2IN is increasing. Since the lim inf of
the sequence K n is nonempty (it contains x), its lim sup is a continuum
C, according to Zoretti's theorem. Since K is compact, it follows that
C). We observe that x 2 K 0 . We shall prove
that jSat(K 0 )j  ", and more precisely that all Sat(K n ), which have
measure  ", are in the same internal hole of K 0 . This result implies
If K n \K 0 6= ;, then K since both are connected components
of K. Since we are assuming that the sets K n are two by two disjoint,
this cannot happen twice. Thus we may assume that K n \ K
for any n. The sequence (Sat(K n being increasing, all K n are in the
same hole of K 0 . Suppose that this hole is the external hole H of K 0 .
Since H is open, there is a continuum L joining p 1 and an arbitrary
point y 0 of K 0 . Since K 0 is in an internal hole of K 1 , there is some
. In this manner, we can construct a sequence (y n ) n2N such
that y n 2 L\K n for all n. L being compact, some subsequence of (y n )
converges to a point y 2 L\C. It follows that K 0 \L 6= ;, contrary to
the assumption that L was in a hole of K 0 . This proves our claim.
Applying the preceding result, if u is continuous, ~
" u is upper semi-
continuous. Since u is also upper semicontinuous, ~
" u is
also upper semicontinuous, hence ~
" u is lower semicontinuous. Thus,
~
" u is continuous.
PROPOSITION 8. For " 0  ", ~
Therefore ~
G " is
idempotent.
Proof. The conclusion that ~
G " is idempotent derives from the previous
statement by taking "
The result amounts to show that for any , G " 0 [u
We distinguish three families among the connected components
I
V. Caselles and P. Monasse
We observe that I . Thanks to Lemma 5, we may write
internal hole of C
internal hole of C
the measure of
is
For the same reason, if
In conclusion, this yields
The following properties are an easy consequence of the denition
of ~
LEMMA 9. The operator ~
" satises the following properties
(i) If u  v, then ~
function u and any  2 IR.
LEMMA 10. Let u be an upper semicontinuous function and let
Proof. Let us x " < -. Since [ ~
it will be
su-cient to prove that G " [v  almost all  2 IR. Let
denote the family of connected components of
K and H(K) the family of internal holes of K. We observe that
C2C(K);jSat(C)j"
internal hole of C; jHj > "g:
Since, by Proposition 6, the connected components of K have measure
-, any C 2 C(K) satises jSat(C)j  ". Similarly, since any internal
hole of K contains a connected component of [v < ], it has also
measure  - > ". Hence, the family of sets H 2 H(K); jHj  " is
empty. We conclude that G "
PROPOSITION 9. Let u 2
0+.
Proof. Using the above Lemma, we have
~
for any "; - > 0 such that " < -. By Proposition 5, given  > 0, there
is some - 0 > 0 such that
This implies that
~
u)  ~
and, therefore,
u) ~
Now, we choose " < - 0 and we obtain that
u) ~
2:
The proposition follows.
4.4. Relations with connected operators
We want to compare the grain lter described above with the notion of
grain operators as dened in [8]. To x ideas, we shall work
in
with
the classical connectivity. Thus, we denote by C the family of connected
sets
of
. A grain criterion is a mapping c : C ! f0; 1g. Given two grain
criteria, f for the foreground and b for the background, the associated
grain operator f;b is dened by
or
In [8], Heijmans characterizes when the grain operators are selfdual and
when are increasing. Indeed, he proves that f;b is self-dual if and only
b. He also proves that f;b is increasing if and only if f and b are
increasing and the following condition holds
for any X
and any x.
We shall say that a grain criterion c : C ! f0; 1g is upper semicontinuous
on compact sets if c(\ n K n decreasing
sequence of continua K n , n 2 IN .
26 V. Caselles and P. Monasse
PROPOSITION 10. Let be a self-dual and increasing grain oper-
ator
in
associated to the grain criterion c. Assume that c upper
semicontinuous.
.
Proof. We have that either
or
for some point x. In the rst case, we deduce that
any nonempty subset X
of
and, therefore, we have that
for any ; 6= X
Since also we have that
any X
In the second case, using the upper semicontinuity of c
we have that c(B(x;
choose observe that c(cc(X [fxg;
which contradicts (6).
The above proposition says that there are no nontrivial translation
invariant, increasing and self-dual grain operators. Other types of connected
operators called
attenings and levelings were introduced by F.
Meyer in [15],[16] and further studied in [29]. In particular, Serra proves
that there exist increasing and selfdual
attenings and levelings based
on markers [29].
Finally, let us prove that the grain lter we have introduced above
corresponds to a universal criterion to dene increasing and self-dual
lters. Let us recall the denition of connected operator [25], [30], [8].
For that, given a set X
, we denote by P (X) the partition
of
constituted by the cc(X) and cc(X c ). The family of all subsets of X
will be denoted by
P(DEFINITION 3. An operator :
P(
P(
connected if the
partition P ( (X)) is coarser than P (X) for every set X
.
Given a connected operator
P(
P(
we shall say that
(i) is increasing if (X)  (Y ) for any X  Y
(ii) acts additively on connected components if
when X i is the family of connected components of X.
(iii) is self-dual if (IR N n any open or closed
set X
(iv) is bounded if p 1
It is not di-cult to see that if is a connected operator which is
increasing and self-dual then it induces an increasing and self-dual lter
on continuous functions.
PROPOSITION 11. Let :
P(
P(
) be a connected operator.
Suppose that is increasing, self-dual, bounded and acts additively on
connected components. Let Ker := fX
be an open or closed connected set. Then, if Sat(X) 62 Ker , we have
where H(X) denotes the family of internal holes of X.
Proof. Since is self-dual, without loss of generality, we may assume
that p 1 62 X. Since is a connected operator, if Z is simply
connected, then (Z) must be one of the sets f;;
g. Since
is bounded we must have that either In
particular, either Sat(X). In the rst case, we
have that Sat(X) 2 Ker . In the second case, using the additivity of
on connected components and the observation at the beginning of the
proof, we have
Now, using the self-duality of we have
(X)
Obviously, if is increasing, then Ker is an ideal of sets, i.e., if
Y  X and X 2 Ker , then Y 2 Ker .
4.5. Interpretation
Similar remarks to those for the extrema lters can be made concerning
the shapes of ~
. The shapes of ~
" u are the shapes of u of su-cient
measure. ~
" corresponds to a pruning of the tree of shapes of u.
5. Experiment
Theoretically, the lters M
" and G " are dierent. This
is illustrated in Figure 1. The second row shows the ltered images
3 u; they are all dierent, stressing that their
respective notions of grains are dierent.
The dierence appears in presence of holes. Concerning natural im-
ages, the dierence would be the most apparent on certain images of
28 V. Caselles and P. Monasse11202

Figure

1. Top-left: original image u. The three constant regions are supposed of area
2. Bottom left: G3u. Middle column: M 3 u and M
3 u and
3 u.

Figure

2. Texture image of a carpet, size 254  173.
textures, for which the nestedness of shapes would be important. Figure
2 shows a complex texture, and Figure 3 the image ltered according
to the three lters of parameter pixels. Whereas they are actually
dierent, they are visually equivalent, and distinguishing them requires
some eort. We can explain that by the fact that connected components
of level sets having a hole of greater area than themselves are scarce.
In other words, the situation illustrated by Figure 1 is not frequent.
Figure

3. Three grain lters applied to the image u of Figure 2. Left column: G30u,

Acknowledgements

We acknowledge partial support by the TMR European project \Vis-
cosity solutions and their applications", reference FMRX-CT98-0234
and the CNRS through a PICS project. The rst author acknowledges
partial support by the PNPGC project, reference BFM2000-0962-C02-
V. Caselles and P. Monasse



--R







'Image Iterative Smoothing and P.D.E.'s'.






Random Sets and Integral Geometry.
Mathematical Morphology and Its Application to Signal and Image Processing
Mathematical Morphology and Its Application to Signal and Image Processing










Image Analysis and Mathematical Morphology.






--TR
Introduction to mathematical morphology
Watersheds in Digital Spaces
Affine invariant scale-space
Morphological multiscale segmentation for image coding
Self-dual morphological operators and filters
From connected operators to levelings
The levelings
Fundamenta morphologicae mathematicae
A Compact and Multiscale Image Model Based on Level Sets

--CTR
Renato Keshet, Shape-Tree Semilattice, Journal of Mathematical Imaging and Vision, v.22 n.2-3, p.309-331, May       2005
Renato Keshet, Adjacency lattices and shape-tree semilattices, Image and Vision Computing, v.25 n.4, p.436-446, April, 2007
connected sets;extrema filters;connected operators;grain filters;mathematical morphology