Image Anal Stereol 2005;24:145-158 Original Research Paper
SPATIALLY ADAPTIVE MORPHOLOGICAL IMAGE FILTERING USING INTRINSIC STRUCTURING ELEMENTS
Johan Debayle and Jean-Charles Plnoli
E´cole Nationale Superieure des Mines de Saint-Etienne, 158, cours Fauriel Saint-Etienne cedex 2, France e-mail: debayle@emse.fr, pinoli@emse.fr (Accepted October 21, 2005)
ABSTRACT
This paper deals with spatially adaptive morphological filtering, extending the theory of mathematical morphology to the paradigm of adaptive neighborhood. The basic idea in this approach is to substitute the extrinsically-defined, fixed-shape, fixed-size structuring elements generally used by morphological operators, by intrinsically-defined, variable-shape, variable-size structuring elements. These last so-called intrinsic structuring elements fit to the local features of the image, with respect to a selected analyzing criterion such as luminance, contrast, thickness, curvature or orientation. The resulting spatially-variant morphological operators perform efficient image processing, without any a priori knowledge of the studied image and some of which satisfy multiscale properties. Moreover, in a lot of practical cases, the elementary adaptive morphological operators are connected, which is topologically relevant. The proposed approach is practically illustrated in several application examples, such as morphological multiscale decomposition, morphological hierarchical segmentation and boundary detection.
Keywords: adaptive neighborhood, connected operators, intrinsic spatial analysis, mathematical morphology, multiscale representation.
INTRODUCTION
Firstly, a lot of image processing techniques use spatially-invariant transformations, with fixed operational windows. This kind of operators, such as morphological operators or convolution filters, give efficient and compact computing structures, in the sense where data and operators are independent. However, due to their fixed operational windows, they consequently have several strong drawbacks such as creating artificial patterns, changing the detailed parts of large objects, damaging transitions or removing significant details (Arce and Foster, 1989).
Alternative approaches towards spatially-variant image processing have been proposed (Gordon and Rangayyan, 1984; Perona and Malik, 1990; Salembier, 1992; Alvarez et al., 1993; Charif-Chefchaouni and Schonfeld, 1994; Vogt, 1994; Braga Neto, 1996; Cuisenaire, 2005; Lerallut et al., 2005) with the introduction of adaptive operators, where the adaptive concept results from the spatial adjustment of the operational window. A spatially adaptive operator will no longer be spatially-invariant, but must vary over the whole image with adaptive windows, taking locally into account the image context. Such transforms perform efficient image processing.
Secondly, usual image processing operators have some limitations concerning their operational windows (adaptive or not). In fact, these last ones are usually extrinsically defined with regard to the local features
of the image. A priori constraints are imposed upon the size and/or the shape of the operational windows, which is not the most appropriate. For instance, spatially-invariant approaches such as wavelets (Mallat, 1989), morphological pyramids (Sun and Maragos, 1989; Laporterie et al., 2002), and isotropic scale-spaces (Lindeberg, 1994; Heijmans and Boomgaard, 2000) use sliding windows extrinsically defined with regard to the analyzing scales. Indeed, their size and shape are fixed on the whole image for each scale, i.e., a priori determined, independently of the image context. In an other example (Vogt, 1994), spatially-variant morphological operators are used, where the shape of morphological structuring elements that automatically adjust the gray tones in a range image is rectangular or ellipsoidal, involving a priori knowledge about the image context.
Therefore, intrinsic approaches, using self-defined operational windows that fit to the local content of the image, without any a priori spatial constraints, are more appropriate. Following this idea, image processing based on the Adaptive Neighborhood (AN) paradigm (Paranjape et al., 1994) has been proposed. A set of adaptive neighborhoods (ANs set) is defined around each point within the image, whose extent depends on the local features of the image in which the given point is situated. Thus, for each point to be processed, its associated ANs set is used as (intrinsic) operational windows of the considered transformation. The resulting operators
145
Debayle J et al: Adaptive neighborhood mathematical morphology
perform meaningful image processing as shown in various image filtering processes (Rabie et al., 1994; Rangayyan et al., 1998; Rangayyan and Das, 1998; Ciuc et al., 2000; Buzuloiu et al., 2001; Ciuc, 2002).
In this paper, an intrinsic spatially-variant approach in the context of Mathematical Morphology (MM) is then proposed using autoreflected Structuring Elements (traditionally called symmetric (Serra, 1988a), i.e., structuring elements which are equal to their reflected set), based on the AN paradigm.
While autoreflectedness is not necessary in the general framework of spatially-variant mathematical morphology, as formally proposed by Charif-Chefchaouni and Schonfeld (1994) and practically used by Cuisenaire (2005) and Lerallut et al. (2005), it is relevant for three main reasons:
1.   it is more adapted to image analysis for topological and visual reasons,
2.   both dualities by adjunction and by involution for dilation and erosion are satisfied,
3.   it allows to simplify mathematical expressions of morphological operators, without increasing computational complexity of algorithms.
Thereafter, the fixed-size, fixed-shape SEs generally used for morphological operators are substituted by (intrinsic) Adaptive Structuring Elements (ASEs) adjusted to a specified set of adaptive neighborhoods based on an analyzing criterion. It leads to Adaptive Neighborhood Mathematical Morphology (ANMM), which provides convincing spatially adaptive morphological filters (Debayle and Pinoli, 2005a). Some of which satisfy multiscale properties (Debayle and Pinoli, 2005b). Moreover, in a lot of practical cases, the elementary adaptive morphological operators are connected, contrary to the usual ones which fail to this property. The proposed approach is practically illustrated through several application examples, such as multiscale decomposition, hierarchical segmentation and boundary detection on the ‘cameraman’ image, the ‘tools’ image and a metallurgic grains real image, respectively.
ADAPTIVE NEIGHBORHOOD SETS
The first step in this ANMM approach consists in defining a set of adaptive neighborhoods determined on the spatial support of the studied image.
Let DCl2 (or more generally in Rn (Debayle, 2005)), the (usually rectangular) domain of definition
of the images and I the set of image mappings from D into R. For each point x G D of an image f G I, the adaptive neighborhood (AN) sets, denoted Vmh(x), are computed in relation with an homogeneity tolerance m G R+ on a criterion mapping h (based on a local measurement such as luminance, contrast, curvature, thickness or orientation related to the image f) belonging to the set C of mappings from D into R. More precisely, for all point x G D its associated AN setVmh(x) CD:
•     depends on two parameters:
-    h: analyzing criterion
-    m: homogeneity tolerance
•     fulfills two conditions:
-    its points have a measurement value close to that of the point x:
VyGVmh(x)    \h(y)-h(x)\<m
-    the  set  is  path-connected  (with  the  usual Euclidean topology on D C R2)
Definition 1 (AN sets)
V(m,h,x)GR+xCxD
mW  =  C h-Kh x_mhx)+m]) (x),       (1)
where CX(x) denotes the path-connected component (with the usual Euclidean topology on D C R2) of XCD containing x G D.
Fig. 1 gives an impression, on a 1-D example, of the computation of an AN set.
measurement value
Fig. 1. One-dimensional computation of an adaptive neighborhood set Vmh(x). For a point x, a tube of tolerance m is first computed around h(x). Secondly, the inverse image of this interval gives a subset of the 1-D spatial support. Finally, the path-connected component holding x provides its AN set Vmh(x).
Fig. 2 illustrates the AN set of a point x computed with the luminance criterion or the contrast (defined in the sense of (Jourlin et al., 1988; Pinoli, 1991))
146
Image Anal Stereol 2005;24:145-158
criterion, on an electrophoresis gel image provided by           So, the AN sets Vhm (x) are defined with the help of
the software Micromorph®. In practice, the choice      a region growing process, which is of great computing
of the appropriate criterion results from kind of the      importance, where the aggregating condition is given
considered application.                                                  by: \h(.) - h(x) | < m.
Definition 3 (AN sets - equivalent definition)
V(m,h , x)6t+xCxD
(a) original image
(b) h1: luminance
(c) h2: contrast
(d) seed point x
(e) V1h01 (x)
h2
(f) V3h02(x)
Fig. 2. Original electrophoresis gel image (a). The adaptive neighborhood set for the seed point highlighted in (d) is respectively homogeneous (e,f), with respect to the tolerance m, in relation to the luminance criterion (b) or to the contrast criterion (c).
In the following, the notion of path is defined so as to get a practical equivalent definition of these AN sets, involving computing interests.
Definition 2 (Path)
A path of extremities x G D and y G D respectively, denoted PL is a continuous mapping (with the usual Euclidean topologies on [0,1] and D) (Choquet, 2000):
Py :
[0,1]    -»¦   D
0          ^   x
1            h^    y
(2)
h,m
Vhm(x)    =    {yeD\y^x}
(3)
h,m
where -^ denotes the path-connectivity relationship:
y^x   <*   3Pyx\izGPyx([0,1])\h(z)-h(x)\<m.
Remark 1 This definition of the AN sets V*(x) is similar to those of connected regions Rfm(x) defined by Braga Neto (1996) but are more general in the sense that they take into account a criterion mapping h.
These AN sets satisfy several properties as stated in the following:
Properties 1 (AN sets)
Let(m,h,x)eR+xCxD
1.   reflexivity:
GV^(x)
(4)
2.  increasing with respect to m:
(mi,m2)GM+2
)^V   ( x )CV   ( x )     (5)
 m\ < m%
3.    equality between iso-valued points:
(x,y)eD2   \
xeVhm(y)     )^Vhm(x)=Vhm(y)        (6)
h(x) = h(y) J
4.    addition invariance with respect to h:
ceR^Vhm+c(x) = VhJx)               (7)
5.    multiplication compatibility with respect to h:
aLR+\{0}^V%l(x)=V'm(x)          (8)
Proof:
h,m
1.   x^x,soxGV^(x).
147
Debayle J et al: Adaptive neighborhood mathematical morphology
2.
m1 < m2   =>
=>
=>
[h(x)-m1h(x)+m1] c [h(x)-m2,h(x)+m2]) C h-H[h{xymiMx)+mi]) (x)C
C h-KHxym2,Kx)+m2]) (x)
V(x)cV 2(x)
3.    Let z be a point in V«(x). So, there exists a path Pzx such that: Mw G P|([0,1]) \h(w)-h(x)\ < m. Moreover, x belongs to Vt(y), i.e., there exists a path P^ such that: VueP*([0,1])\h(u)-h(y)\<m.
Thus, there exists a path P* such that P*([0,1]) =
PJ([0,1])UP|([0,1]).
Consequently, for all t in P* ([0,1]), if t belongs to
PL([0,1]) then \h(t)-h(y)\ < m else t belongs to
P*([0,1]) and \h(t)-h(y)\ = \h(t)-h(x)\ <m.
So, for all t in P*([0,1]) \h(t)-h(y)\ < m and then
zeVJ,y.
Conversely, if z belongs to Vhm(y) then there exists
a path P* such that:
VwGP^([0,1])|h(w)-h(y)|<m.
Since x belongs to Vhm{y) and h(y) = h(x), then
y belongs to V^(x) (seen with the inverse path
Pt ( • ) —— P   ( • ) ~~ P^ ( 1 —    )).
So, there exists a path P* such that P|([0,1]) =
pž([0,1])up5([0>1]).
A similar reasoning leads to the expecting result,
i.e.,zeVhm(x).
4.      (h+c)  1 ([(h+c) (x) -m, (h+c) (x) +m]) = {yeD\(h+c)(y) G [(h+c)(x)-m,
(h+c)(x)+m}} = {yeD\h(y) G [h(x)-m,h(x)+m]} = h-1([h(x)-m,h(x)+m})
5.      {ah)-1{[{ah){x)-m,{ah){x)+m\)
= {yeD\(ah)(y) G [(ah)(x)-m,(ah)(x)+m]} = {yeD\h(y) G [h(x)-(%),h(x) + (%)]}
= h-1([h x)-(h)h x + (h)])
(a) criterion: luminance
(b) AN sets

m = 5
m = 10
m = 15
m = 20
m = 25
(c) color table
Fig. 3. Nesting of AN sets of four seed points (b) using the luminance criterion (a) and different homogeneity tolerances: m = 5,10,15,20 and 25 encoded by the color table (c). An AN set defined with a certain homogeneity tolerance could be represented by several tinges of the color associated to its seed point.
Fig. 3 shows that the AN sets are, through the analyzing criterion and the homogeneity tolerance, intrinsically-defined with respect to the local structures of the studied image, performing a real spatially adaptive analysis.
So, morphological operations have to be adjusted to these AN sets so as to develop Adaptive Neighborhood Mathematical Morphology (ANMM).
ADAPTIVE NEIGHBORHOOD MATHEMATICAL MORPHOLOGY
D
To illustrate the nesting property (Eq. 5) with respect to m, the AN sets of four initial points are computed on the ‘Lena’ image (Fig. 3) with the luminance as analyzing criterion.
The origin of mathematical morphology stems from the study of the geometry of porous media by Matheron (1967). The mathematical analysis is based on set theory, integral geometry and lattice algebra. Its development is characterized by a cross-fertilization between applications, methodologies, theories, and algorithms. It leads to several processing
148
Image Anal Stereol 2005;24:145-158
tools in the aim of image filtering, image segmentation and classification, image measurements, pattern recognition, or texture analysis.
Inspired by Braga Neto (1996), the proposed spatially-variant mathematical morphology approach is based on the adaptive neighborhood paradigm proposed by Paranjape et al. (1994). In this paper, only the flat MM (ie with structuring elements as subsets in R2) is considered, though the approach is not restricted and can also address the general case of functional MM (ie with functional structuring elements from a subset of D into R) (Debayle, 2005).
The space of images I is provided with the partial ordering relation < defined in terms of the usual ordering relation < of real numbers:
V(f,g)GI   f<g^(VxGD   f(x)<g(x)).   (9)
Thus, the partially-ordered set (I, <), still named I, is a complete lattice (Serra, 1988a).
ADAPTIVE STRUCTURING ELEMENTS
To get the morphological duality (adjunction) between erosion and dilation, reflected (or transposed) structuring elements (SEs) (Serra, 1988a), whose definition is mentioned below, should be used.
Definition 4 (Reflected subset) The reflected subset of A(x) C D, element of a collection {A(z)}zeD, is defined as:
A(x) = {zGD;xgA(z)}
(10)
The notion of autoreflectedness is then defined as following (Serra, 1988a):
Definition 5 (Autoreflected subset) The subset A(x) C D,  element of a collection  {A(z)}zeD  is autoreflected if and only if:
A ¡(x)=A(x),                        (11)
that is to say: \/(x,y) G D2   x G A(y) «ye A(x).
Remark 2 The term autoreflectedness is employed in place of symmetry which is generally used in literature (Serra, 1988a), so as to avoid the confusion with the geometrical symmetry. Indeed, an autoreflected subset A(x) CD belonging to {A(z)}zeD is generally not symmetric with respect to the point x.
Spatially-variant mathematical morphology using adaptive SEs which do not satisfy the autoreflectedness condition   (Eq.   11)   has   been   formally   proposed
by Charif-Chefchaouni and Schonfeld (1994) and practically used in image processing (Lerallut et al, 2005; Cuisenaire, 2005). Nevertheless, while autoreflectedness is restrictive from a strict mathematical point of view, it is relevant for three main reasons:
1.    it is more adapted to image analysis for topological and visual reasons (Rem. 3),
2.   both dualities by adjunction and by involution for dilation and erosion are satisfied,
3.    it allows to simplify mathematical expressions of morphological operators, without increasing computational complexity of algorithms.
From this point, autoreflected adaptive structuring elements are considered in this paper. Therefore, the
AN sets Vmh(x) are not autoreflected (Fig. 4).
measurement value
4,10]
h(x) = 7 h(y) = 5 [2,8]
H------------------------------------------------------I--------------------------------------------------------------------
point line
Fig. 4. The AN sets {Vhm(z)}zeD are not autoreflected: x G V3( y ) andy i V h(x). Consequently, (V h) = V3.
So, the adaptive SEs, denoted Rhm(x)}xGD, are defined while satisfying the AN paradigm and the autoreflectedness condition.
Definition 6 (Adaptive structuring elements)
V(m,h , x)GR+xCxD
Rhm(x)
I     I < V
zeD
z)\xeVmh(z)}
(12)
These adaptive SEs (Eq. 12) are anisotropic and self-defined with respect to the criterion image mapping h. They satisfy the following properties:
Properties 2 (Adaptive structuring elements)
V(m,mi,m2,h , x)GR+3xCxD 1.   geometric nesting:
Vhm(x)CRhm(x)c:V h m(x
2.  symmetry:
eRhm(y)^yeRhm (x)
(13)
(14)
x
149
Debayle J et al: Adaptive neighborhood mathematical morphology
3.   reflexivity:
eR x
(15)
4.    increasing with respect to m:
m1<m2^Rhmi(x)CRhm2(x)
5.    addition invariance with respect to h:
ceR^Rhm+c(x)=Rhm(x)
6.    multiplication compatibility with respect to h:
(16)
(17)
aeR+\{0}^R,
ah/
- Rt (x)
(18)
Proof:
1.    Since x belongs to Vhm{x), Vhm{x) is included as subset in Rhm(x).
Let y be a point in Rhm{x). So, there exists z in D such that y belongs to Vhm (z) (with the path PL) and x belongs to Vhm{z) (with the path PL). Thus, the path PL such that pI([0,1]) = P¡*([0,1]) U P^([0,1]) is well-defined.
Let w in PL([0,1]). If w belongs to P^([0,1]) then \h(w)-h(x)\ < \h(w)-h(z)\+\h(z)-h(x)\ < m+m = 2m, else w belongs to P*([0,1]) = P?([0,11) (P¡* and Pf have same image) and so \h(w)-h\x)\ < \h(w)-h(z)\+\hz)-h(x)\ < m+m = 2m. Consequently, Vw G P^([0,1]) \h(w)-h(x)\ < 2m and therefore y G V^x.
2.    If y belongs to R (x), there exists z in D such that y and x both belong to Vhm{z). So, R(y) holds x.
3-6.These    properties     are    inferred    from corresponding ones of AN sets (Prop. 1).
the
D
The ASEs satisfy the AN paradigm through the geometric nesting (Eq. 13). Fig. 5 compares the shape of usual SEs Br(x) as disks of radius r e R+ and adaptive SEs Rhm{x) as sets self-defined with respect to the criterion mapping h and the homogeneity tolerance meE+.
Remark 3 Autorefletedness is argued to be more adapted to image analysis from both topological and visual reasons. In fact, it allows a symmetric neighborhood system Rhm (x) to be defined at each point x belonging to D. Topologically, it means that if x is in the neighborhood of y at level m (x G Rhm{y)), then y is as close to x as x is close to y (y G Rhm{x)) (Prop 2.2). In terms of metric, this is a required condition to define a distance function d, starting from all the Rhm{.), satisfying the symmetry axiom: d(x,y) = d(yx)
(Cech, 1966). Indeed, symmetry is needed to introduce a non-degenerate topological metric space (the authors are currently working on topological approaches with respect to the AN paradigm). From a visual point of view, the symmetry property appears closely linked to the human visual perception (Gestalt theory, ...) (Wertheimer, 1938; Dakin and Hess, 1997).
r,m
Br{x1)
R(x4)
Fig. 5. Example of adaptive Rhm and non-adaptive Br structuring elements with three values both for the homogeneity tolerance parameter m, and for the disks radius r. The shape ofBr(x1) andBr(x2) are identical and {Br{x)}r is a family of homothetic sets for each pointx G D. On the contrary, the shape ofRhm{x3) and Rhm{x4) are dissimilar and {Rm(x)}m is not a family of homothetic sets.
The next step consists in defining adaptive basic operators of MM in the aim of building adaptive morphological filters.
ADAPTIVE ELEMENTARY MORPHOLOGICAL OPERATORS
The elementary dual operators of adaptive dilation and erosion are defined accordingly to the flat ASEs Rhm(x). The formal definitions are given as following:
Definition 7 (Adaptive dilation/erosion)
V(m,h)Ll+xC
D
I
(19)
where  D*(f)
where  EhJf)
—Y       I
f      »   D(f)      ,
D   ->   1
x    h->      sup   f(w)   (20)
—>   I
f ^   E hJf) ,
D   ->   1
x    h->       inf   f(w)   (22)
weRi(x)
I
(21)
150
Image Anal Stereol 2005;24:145-158
Next, the lattice theory (Serra, 1988a) allows to define the most elementary (adaptive) morphological filters (Serra, 1988b). More precisely, the adaptive closing and opening are respectively defined as:
Definition 8 (Adaptive closing/opening)
V(m,h)Ll+xC
Ch
Ohm
I
f
EhmoDhm(f)
DhmoEhm(f)
(23) (24)
7.  increasing, decreasing with respect to m:

(mi,m2)GM+2

8.  addition invariance with respect to h:
cel=>
Dh+c(f)
h+c m
h+c Em h+c
(f) Chm+c(f) Ohm+c(f)
Dhm(f) Ehm(f) Chm(f) Ohm(f)
(31)
(32)
These adaptive elementary morphological operators satisfy several properties stated in the following. Properties 1 through 6 are standard, that is to say analogous to those of the usual morphological operators:
Properties 3 (Adaptive morphological operators)
Let(m,h,f,fhf2)eR+xCxI3.
9.  multiplication compatibility with respect to h:
1.  increasing:
fl<f2=>
 D hmifl)<D hmif2)
Ehm(fi)<Ehm(L) Chm(fi)<Chm(fi) I Ohm(fi)<Ohm(f2)
2.    adjunction (morphological duality):
Dhm(f1)<f2^fi<E hm(f2)
3.    extensiveness, anti-extensiveness:
O hm(f)<f<Chm(f)
4.    distributivity with V, A:
f \l[Dhm(fi)\=Dhm(\i[fi
V(fi) g IK
ieK                            ieK
AlEhMi)]=Ehm(/\[fi]) ieK                           ieK
where K is an index set (finite or not). 5.  duality with respect to the involution —.:
I D hmf} = Ehm(f)
Chm(f) = Ohm(f)
6.   idempotence:
/ Chm(ChM))=Chm(f)  Ohm(Ohm(f)) = Ohm(f)
(25)
(26)
(27)
(28)
(29)
(30)
aeR+\{0}^
D?m h(f) = Dh?m (f)
(f) = Ehm (f)
C?hm (f)
O?hm (f)
?h m
?m h(f) ?m h(f)
(33)
Proof:
1-6.These properties are inferred from the lattice theory of increasing mappings (Serra, 1988a;b).
7-9.It is directly inferred from the properties 4-6 of the adaptive structuring elements (Prop. 2).
D
The usual and adaptive morphological operators of erosion, dilation, opening and closing are illustrated in Fig. 6. Note that Er, Dr, Or and Cr denote the classical erosion, dilation, opening, closing with the disk Br of radius r as isotropic structuring element.
Moreover, with the ‘luminance’ criterion (h = f), the adaptive dilation (Eqs. 19-20) and erosion (Eqs. 21-22) satisfy the connectedness (Serra and Salembier, 1993) condition (Prop. 4) which is of great morphological importance. On the contrary, the usual dilation and erosion fail to this property.
Definition 9 (Connectedness) An operator <p : I ^ I is connected if and only if: VfGI V(x,y) neighbors
f(x)=f(y) => Hf)(x) = Hf)(y)
(34)
Properties 4 (Connectedness of adaptive operators)
VmGM+J  f^Dmif)   are connected operators.
 f h^Em (f)

f

I
I


151
Debayle J et al: Adaptive neighborhood mathematical morphology
(a) original image f
(b) E1(f)
(c) D1( f)
(d) O1( f )
(e) C1( f )
(f) E2f0(f)
(g) D2f0( f )
(h) O2f0( f )
(i) C2f0( f)
Fig. 6. Usual vs adaptive morphological operators on a blood vessels (a) image f: usual erosion (b) / dilation (c) / opening (d) / closing (e) with a disk of radius 1 as isotropic SE - adaptive erosion (f) / dilation (g) /opening (h) / closing (i) with adaptive SE computed with the luminance criterion f and the homogeneity tolerance m = 20.
Proof:
Let g be in I. For all (x,y) neighboring points (with the usual Euclidean topology on D C M2), if g{x) = g(y) then VL(x) = VL(y). In addition, for all z G D, x L Vi (z) => y G Vi (z) since x and y are neighbors with the same gray tone.So, Rgm(x) = Rgm(y). Consequently Dl, (g) (x) = Dl, (g) (y) and E* (g) (x) = Egm (g) (y). Thereafter, the closing and the opening are connected operators by composition of connected operators (Serra and Salembier, 1993).                                  D
This property is an overwhelming advantage in comparison to the usual ones which fail to this connectedness condition. Besides, it allows to define several connected operators built by composition or combination with the supremum and the infimum (Serra and Salembier, 1993) of these adaptive elementary morphological operators, as adaptive closings (Eq. 23) and openings (Eq. 24). Thus, the operators OC^ = OC and CO^ = C O, called adaptive opening-closing and adaptive closing-opening respectively, are (adaptive) morphological filters (Matheron, 1988), and in addition, connected operators with the luminance criterion.
ADAPTIVE SEQUENTIAL MORPHOLOGICAL OPERATORS
The families of adaptive morphological filters {O«}m>0 (Eq. 24) and {Chm}m>0 (Eq. 23) are generally not a size distribution and anti-size distribution respectively, due to the notion of semi-group which is generally not satisfied (Serra, 1988a). Nevertheless, such families are built by naturally reiterate adaptive dilation or erosion. Explicitly, adaptive sequential dilation, erosion, closing and opening, are respectively defined as:
Definition 10 (Adaptive sequential dilation/erosion)
V(m,p,h)GM+xNxC
Dhm,p   :f
I    —>   I
^   D*°-°D*(f)        (35)
Ehm,      :
m,p
p times I      —>    I
f   ^   Ehmo---oEhm(f)        (36)
p times
Definition 11 (Adaptive sequential closing/opening)
V(m,p,h)GM+xNxC
152
Image Anal Stereol 2005;24:145-158
h               I      —*     I
Cm'p   :    I f    ~    Em poDm,p(f)   ,       (37)
h            i   I      —*     I
Om'p    :        f    ^    Dm poe h,^f)   '       (38)
The morphological duality of Dhm p (Eq. 33) and Ehmp (Eq. 34) provides, so among other things, the two sequential morphological filters C hmtp (Eq. 35) and Ohmp (Eq. 36). Moreover, these last ones generate size and antisize distributions:
Properties 5 (Size/antisize distribution)
V(m,h)el+xC
1.    {Ohm,p} >0 is a size distribution
2.    {Chm,p} >0 is an antisize distribution
Proof:
Let f G I and (p, q) G N2 such that p > q.
Ohm,p    <    Dhm,qoDhm,„oEhm p qoE hm q
<    Dhm,qoO hm,„oEhm,q
<    Dhm,qoEhm,q
<    O hm q-
Chm p    >    Ehm qoEhm p qoD hm^oD hm q
>  C hm)q
D
Thus, the extension of the well-known alternating sequential filters (ASFs) (Serra, 1988c) can be defined:
Definition 12 (Adaptive alternating sequential filters)
V(m,n,h)   G   R+  x N\{0} x C   V(pi)   G   N^ increasing sequence ASFOChm >n :
(I    —>   I
f»   OCmipno...oOC mip 1(f)(x)         (39)
ASFCOhm ,n :
(I    —>   I
f» CO m po...oCO m)p1(f)(x)       (40)
These adaptive ASFs are similar to those defined by Braga Neto (1996) using the AN paradigm.
RESULTS
Adaptive morphological processes are now applied and illustrated in the field of image filtering and segmentation. The results are all achieved with the luminance criterion (mapping h).
MULTISCALE DECOMPOSITION
In this subsection, a multiscale representation of the ‘cameraman’ image (Fig. 7) is constituted following a specific kind of morphological operators: the alternating sequential filters (ASFs) which satisfy relevant multiscale properties (Serra and Salembier, 1993). Usual ASFs, usual ASFs by reconstruction (Crespo et al., 1995) and adaptive ASFs, are applied, supplying results which are compared and discussed.
Note that ASFCOm,p and ASFRCOm,p stand for the usual ASF and the ASF by reconstruction of order p, respectively, with a disk of radius m as uniform SE. As regards the filter ASFCOmf ,p, it denotes the adaptive ASF of order p using the adaptive SEs with the luminance criterion mapping f and the homogeneity tolerance m.
These results show that the connectedness of adaptive ASFs and usual ASFs by reconstruction is an overwhelming advantage. Indeed, the edges are quickly damaged by the usual ASFs, while they are preserved with the connected ASFs. Moreover, the filters by reconstruction remove fine details so far, as revealed in the scene upon the camera (Fig. 7e) and the eye of the human face (Fig. 7e), although they are connected. On the contrary, the decomposition of the original image with ANMM-based filters, does not decimate relevant structures from fine-to-coarse scales (Fig. 7h-j).
BOUNDARY DETECTION
A real example in the field of image segmentation is now illustrated on a metallurgic grain boundaries image (Fig. 8). Several methods have ever been introduced (e.g., Chazallon and Pinoli, 1997) requiring most of the time complex processes. Elementary ANMM-based processing is then suggested and compared with the corresponding usual MM approach. Seeing that the crest lines of the original image fit with the narrow grain boundaries, the watershed transform, denoted W, is directly applied on smoothed images (processed with closing-opening filters) in order to avoid an over-segmentation. Note that COr (resp. COhm) stands for the usual closing-opening using a disk of radius r as uniform SE (resp. using the adaptive SEs with the homogeneity tolerance m, and the criterion mapping h).
153
Debayle J et al: Adaptive neighborhood mathematical morphology
(a) original f
(b) ASFCO1,4(f)
(c) ASFCO1,7(f)
(d) ASFCO1,10(f)
(e) ASFRCO1,4(f)
(f) ASFRCO1,7(f)
(g) ASFRCO1,10(f)
(h) ASFCO5f,4(f)
(i) ASFCO5f,7(f)
(j) ASFCO5f,10(f)
Fig. 7. Multiscale decomposition with usual ASFs (b-d), usual ASFs by reconstruction (e-g), and adaptive ASFs (h-j) of the original image (a).
The adaptive approach overcomes the usual one, achieving an efficient segmentation of the original image, with the expected result for m = 20 .
Indeed, the adaptive filters, contrary to the usual ones, do not damage the boundaries and well smooth the image inside the grains. This event is a direct consequence of the connectedness of the adaptive morphological operators. Besides, the minima of the
(adaptively) filtered images provide markers, for the watershed transformation, all the more significant so the parameter m increases. This argument leads to the well-segmented image W(CO2f0(f)). In their current research works, the authors take an interest in the difficult task of automatically picking the fair parameter m.
154
Image Anal Stereol 2005;24:145-158
(a) original image
(b) CO1(f)
(c) CO2(f)
(d) CO3(f)
(e) S( f )
(f) W(CO1(f))
(g) W(CO2(f))
(h) W(CO3(f))
(i) CO5f (f)
(j) CO1f0(f)
(k) CO2f0(f)
(l) W(CO5f (f))
(m) W(CO1f0(f))
(n) W(CO2f0(f))
Fig. 8. Usual (b-d) and adaptive (i-k) closing-opening filters of the original image (a) and their corresponding segmentation (resp. (f-h) and (l-n)) using the watershed transformation, denoted W. The original image is primarily filtered in order to avoid an over-segmentation (e).
155
Debayle J et al: Adaptive neighborhood mathematical morphology
(a) original image
(b) C4f,5( f )
(c) C4f,10( f )
(d) C4f,15( f )
(e) S(f)
(f) S(C4f,5(f))
(g) S(C4f,10( f))
(h) S(C4f,15(f))
Fig. 9. Hierarchical pyramidal segmentation of the ‘Tools’ (a) image. First, the original image is decomposed using adaptive sequential closing filters (b-d). Secondly, the application of the morphological gradient followed by the watershed transformation, denoted S, achieves the images (f-h). The original image is decomposed so as to avoid an over-segmentation (e). The process S(C4f,n(f)) provides a well-accepted segmentation for n ? 15 (g,h).
ADAPTIVE MORPHOLOGICAL HIERARCHICAL SEGMENTATION
In this last application example, the ‘tools’ test image (Fig. 9) is hierarchically segmented. The process is achieved in three steps:
1.   firstly, the original image is smoothed with adaptive sequential closing filters (Eq. 35) which satisfy relevant properties (anti-size distribution and connectedness), supplying a multiscale representation,
2.   secondly, the morphological gradient is computed on decomposed images,
3.   finally, the watershed transform is applied to the previous images.
In this way, it leads to a hierarchical segmentation (Vachier, 2001) without any operators by reconstruction.
The resulting hierarchical segmentation supplies nested  partitions  of  the  spatial  support  of  the
original image, which could induce a graph representation (Serra and Salembier, 1993; Vachier, 2001). Thereafter, the process C4f,n offers the expected result for n = 15 or n > 15. Indeed, this operator is saturated from this value:
Vn>15
C4f,
n(f)
C4f,15
(f)
This characteristic has been studied and promises relevant topological properties (Debayle, 2005).
Furthermore, the resulting hierarchical segmentation, where flat zones are nested, is achieved without any operators by reconstruction (Crespo et al., 1995). Filters by reconstruction require geodesic transformations, so as to define connected operators, which are traditionally used for this kind of multiscale segmentation (Serra and Salembier, 1993; Salembier and Serra, 1995; Vachier, 2001).
So, the connectedness of the elementary ANMM-based operators is an overwhelming advantage: all operators built by composition or combination with the supremum and the infimum of the adaptive dilation and erosion, define connected operators.
156
Image Anal Stereol 2005;24:145-158
IMPLEMENTATION ISSUE
The algorithms of the proposed morphological operators are built in two steps. Firstly, the AN sets are computed and stored in random access memory (RAM). The equality property (Prop. 1.3) between iso-valued points is used so as to save memory and reduce computation time. Secondly, the operators are run with the stored AN sets. In this way, AN sets are computed once time even for advanced operators, such as adaptive ASFs. Nevertheless, this methodology requires a large random access memory (RAM) so as to store all the AN sets. Moreover, the computational time of AN sets is rather long, about 2-3 minutes for of a 256 × 256 image, with a Pentium IV (3GHz / 2Go RAM) using the software AphelionTM and C++ language. Conversely, the running of morphological operators is faster (for example 4-5 seconds for a dilation).
CONCLUSION
The proposed spatially-variant morphological approach provides adaptive operators without any a priori knowledge of the studied image. Theoretically, such transforms possess several strong advantages such as the connectedness of the operators, contrary to the usual ones which fail to this property. In practice, it yields good results in the field of image filtering and segmentation. The idea of building spatially adaptive operators using intrinsic operational windows which locally fit to the features of an image is very promising and can suit different image processing tools, more particularly in multiscale image analysis as studied in (Debayle and Pinoli, 2005b).
Currently, the authors are interested in AN sets taking into account physical and psychophysical settings allowing to be consistent with several image formation models and with the human visual perception. In addition, other analyzing criteria are actually being studied.
ACKNOWLEDGMENT
The authors thank their colleague Yann Gavet (Ecole Nationale Supe´rieure des Mines de Saint-Etienne, France) for his computing contributions.
REFERENCES
Alvarez L, Guichard F, Lions PL, Morel JM (1993). Axioms and fundamental equations in image processing. Arch Ration Mech An 123:199–257.
Arce GR, Foster RE (1989). Detail-preserving ranked-order based filters for image processing. IEEE Trans Acoust Speech 37:83–98.
Braga Neto UdM (1996). Alternating sequential filters by adaptive-neighborhood structuring functions. In: Maragos P, Schafer RW, Butt MA, eds. Mathematical Morphology and its Applications to Image and Signal Processing. Kluwer Academic Publishers, 139-46.
Buzuloiu V, Ciuc M, Rangayyan RM, Vertan C (2001). Adaptive-neighborhood histogram equalization of color images. Electron Imaging 10:445–59.
Cech A (1966). Topological Spaces. John Wiley and Sons.
Charif-Chefchaouni M, Schonfeld D (1994). Spatially-variant mathematical morphology. In: Proceedings of the IEEE International Conference on Image Processing. Austin, Texas, USA, November 13-16, vol. 2, 555–9.
Chazallon L, Pinoli JC (1997). An automatic morphological method for aluminium grain segmentation in complex grey level images. Acta Stereol 16:119–30.
Choquet G (2000). Cours de topologie, chap. Espaces topologiques et espaces me´triques. Paris: Dunod, 45– 51.
Ciuc M (2002). Traitement d’images multicomposantes: application a` l’imagerie couleur et radar. Ph.D. thesis, Universite´ de Savoie - Universite´ Polytechnique de Bucarest, Roumanie.
Ciuc M, Rangayyan RM, Zaharia T, Buzuloiu V (2000). Filtering noise in color images using adaptive-neighborhood statistics. Electron Imaging 9:484–94.
Crespo J, Serra J, Schafer RW (1995). Theoretical aspects of morphological filters by reconstruction. Signal Process 47:201–25.
Cuisenaire O (2005). Locally adaptable mathematical morphology. In: Proceedings of the IEEE International Conference on Image Processing. Genova, Italy, September 11-14, vol. II, 125–8.
Dakin SC, Hess RF (1997). The spatial mechanisms mediating symmetry perception. Vision Res 37:2915– 30.
Debayle J (2005). General Adaptive Neighborhood Image Processing. Ph.D. thesis, Ecole Nationale Supe´rieure des Mines, Saint-Etienne, France. In preparation.
Debayle J, Pinoli JC (2005a). Adaptive-neighborhood mathematical morphology and its applications to image filtering and segmentation. In: 9th European Congress on Stereology and Image Analysis. Zakopane, Poland; May 10-13, vol. 2, 123–30.
Debayle J, Pinoli JC (2005b). Multiscale image filtering and segmentation by means of adaptive neighborhood mathematical morphology. In: Proceedings of the IEEE
157
Debayle J et al: Adaptive neighborhood mathematical morphology
International Conference on Image Processing. Genova, Italy; September 11-14, vol. III, 537–40.
Gordon R, Rangayyan RM (1984). Feature enhancement of mammograms using fixed and adaptive neighborhoods. Appl Opt 23:560–4.
Heijmans HJAM, Boomgaard RVD (2000). Algebraic framework for linear and morphological scale-spaces. J Vis Commun Image R 13:269–301.
Jourlin M, Pinoli JC, Zeboudj R (1988). Contrast definition and contour detection for logarithmic images. J Microsc 156:33–40.
Laporterie F, Flouzat G, Amram O (2002). The morphological pyramid and its applications to remote sensing: Multiresolution data analysis and features extraction. Image Anal Stereol 21:49–53.
Lerallut R, Decencire E, Meyer F (2005). Image filtering using morphological amoebas. In: Ronse C, Najman L, Derencie`re E, eds., Proceedings of the 7th International Symposium on Mathematical Morphology. Paris, France; April 18-20, 13–22.
Lindeberg T (1994). Scale-space theory: a basic tool for analysing structures at different scales. J Appl Stat 21:225–70. (Supplement on Advances in Applied Statistics: Statistics and Images: 2).
Mallat SG (1989). A theory for multiresolution decomposition: The wavelet representation. IEEE Trans Pattern Anal 11:674–93.
Matheron G (1967). Ele´ments pour une the´orie des milieux poreux. Paris: Masson.
Matheron G (1988). Image Analysis and Mathematical Morphology. Volume 2: Theoretical Advances, chap. Filters and Lattices. London: Academic Press, 115–40.
Paranjape RB, Rangayyan RM, Morrow WM (1994). Adaptive neighbourhood mean and median image filtering. Electron Imaging 3:360–7.
Perona P, Malik J (1990). Scale-space and edge detection using anisotropic diffusion. IEEE Trans Pattern Anal 12:629–39.
Pinoli JC (1991). A contrast definition for logarithmic images in the continuous setting. Acta Stereol 10:85– 96.
Rabie TF, Rangayyan RM, Paranjape RB (1994). Adaptive-neighborhood image deblurring. Electron Imaging 3:368–78.
Rangayyan RM, Ciuc M, Faghih F (1998). Adaptive-neighborhood filtering of images corrupted by signal-dependent noise. Appl Opt 37:4477–87.
Rangayyan RM, Das A (1998). Filtering multiplicative noise in images using adaptive region-based statistics. Electron Imaging 7:222–30.
Salembier P (1992). Structuring element adaptation for morphological filters. J Vis Commun Image R 3:115– 36.
Salembier P, Serra J (1995). Flat zones filtering, connected operators, and filters by reconstruction. IEEE Trans Image Process 4:1153–9.
Serra J (1988a). Image Analysis and Mathematical Morphology. Volume 2: Theoretical Advances, chap. Mathematical Morphology for Complete Lattices. London: Academic Press, 13–35.
Serra J (1988b). Image Analysis and Mathematical Morphology. Volume 2: Theoretical Advances, chap. Introduction to Morphological Filters. London: Academic Press, 101–14.
Serra J (1988c). Image Analysis and Mathematical Morphology. Volume 2: Theoretical Advances, chap. Alternating Sequential Filters. London: Academic Press, 203–16.
Serra J, Salembier P (1993). Connected operators and pyramids. In: Proceedings of SPIE. San Diego, USA, 65–76.
Sun FK, Maragos P (1989). Experiments on image compression using morphological pyramids. In: Proceedings of the SPIE Visual Communications and Image Processing, vol. IV, 1303–12.
Vachier C (2001). Morphological scale-space analysis and feature extraction. In: Proceedings of the IEEE International Conference on Image Processing. Thessaloniki, Greece, October, vol. 3, 676–679.
Vogt RC (1994). A spatially variant, locally adaptive, background normalization operator. In: Serra J, Soille P, eds., Mathematical Morphology and its Applications to Image Processing. Kluwer Academic Publishers, pp. 45-52.
Wertheimer M (1938). A sourcebook of Gestalt Psychology, chap. Laws of Organization in Perceptual Forms. New York: Hartcourt, Brace, 71–88.
158