Image Anal Stereol 2004;23:89-109 Review Article
MORPHOLOGICAL SAMPLING OF CLOSED SETS
LSIIT UMR 7005 CNRS-ULP, Parc d’Innovation, Boulevard Sebastien Brant, BP 10413, 67412ILLKIRCH
CEDEX (FRANCE)
e-mail: {cronse,tajine}@dpt-info.u-strasbg.fr
(Accepted March 2, 2004)
ABSTRACT
We briefly survey the standard morphological approach (Heijmans, 1994) to the sampling (or discretization) of sets. Then we summarize the main results of our metric theory of sampling (Ronse and Tajine, 2000; 2001; 2002; Tajine and Ronse, 2002), which can be used to analyse several sampling schemes, in particular the morphological one. We extend it to the sampling of closed sets (instead of compact ones), and to the case where the sampling subspace is boundedly compact (instead of boundedly finite), and obtain new results on morphological sampling. In the original morphological theory for sampling (Heijmans, 1994), some reconstruction of the sampling was shown to converge, relative to the Fell topology (or Hausdorff-Busemann metric), to the original closed set when the resolution of the sampling space tends to zero. As we explain here, this reconstruction step is artificial and unnecessary, the sampling itself converges to the original closed set under the Hausdorff metric, which is a stronger convergence than for the Hausdorff-Busemann metric.
Keywords: boundedly compact set, compact set, dilation, discretization, Hausdorff metric, metric space, proximinal set, sampling.
Christian Ronse and Mohamed Tajine
INTRODUCTION
Sampling (or discretization) of shapes is an important topic in imaging sciences; it is part of the more general question of the relationship between discrete and Euclidean models of objects. The morphological approach to sampling involves set-theoretical interactions with structuring elements. The seminal work in this respect is that of Heijmans and Toet (1991), who introduced the discretization by dilation, which was studied extensively in Heijmans (1994).
Consider the Euclidean space E = Rn, and let D be a discrete subspace of E, for example D = (pZ)n (where p > 0 is the spacing of the grid D). Write ® for the Minkowski addition (Heijmans, 1994; Matheron, 1975; Serra, 1982) defined by X ® Y = {x+y\xLX, y G Y}. Consider a subset A of E, called a structuring element. Write Ap for the translate of A by p (Ap = {a+p | a G A}) andA for the symmetrical of A (A = {—a | a G A}). We make the covering assumption, namely that D®A = E. Then the discretization by dilation is the map AA, : LP(E) —> L?(D) defined by setting:
VXCE,    a%(x)   =(X®A ¡)HD
= {peD\ApnX^0/} .   (1)
A particular case is the well-known supercover discretization (Cohen-Or and Kaufman, 1995). We associate with each p e D the closed cell C(p)
consisting of all Euclidean points x L E which are at least as close to p as to any other point in D:
VpeD,   C(p) = {xeE\yqeD\{p},d2(x,p)<d2(x,q)} ,     (2)
where d2 is the Euclidean distance. The supercover discretization ASC associates with every X <G L?(E) the set of all p G D such that C (p) intersects X (see Figure 1):
VXCE,    ASC(X) = {peD\C(p)nX^0/} .   (3)
In fact, we have ASC(X) = A^(X), where A is the square structuring element giving the cell’s shape: C(p)=Ap.
Fig. 1. Here E = R2 and D = Z2. a) The cell C(p) centered about the discrete point p, b) an Euclidean set X, and the discrete points p with their cells C(p) nearX, c) the supercover discretization ASC(X).
Now Heijmans and Toet (1991) associate with the discretization by dilation A^, a reconstruction E^ :
89
Ronse C et al: Morphological sampling
g?(D) —> LP(E), which is the adjoint erosion, that is, it associates to every Y e ,^>(D) the greatest X e LP(E) such that A^ (X) C Y, in other words
E A (Y)=E\[(D\Y)®A].
The main theoretical interest of this definition of reconstruction is that the pair (EA,A^) forms what is called in mathematical morphology (Heijmans, 1994) an adjunction, something which leads to interesting algebraic properties, in particular for X C E and Y C D we have: AA(EA(AA(X))) = AL(X), and EA(Ai(EA(Y))) = EA(Y). As we will see in Subsection “Morphological discretization”, this reconstruction is questionable from a topological point of view.
This approach (Heijmans and Toet, 1991) to sampling and reconstruction led to further developments towards image discretization (Heijmans, 1991), discretization of binary random fields (Sivakumar and Goutsias, 1996) discretization of morphological image processing operations (Heijmans, 1992; Sivakumar and Goutsias, 1997) (see also Section 3.3 of (Tajine and Ronse, 2002)). The preservation of topological properties, such as connectedness, in a discretization have been studied (Latecki et al, 1998; Tajine and Ronse, 2002), in particular in the morphological framework (Schmitt, 1998). For more bibliographical references on the topic of discretization, we refer the reader to Ronse and Tajine (2000).
In Ronse and Tajine (2000; 2001); Tajine and Ronse (2002), the authors introduced a new approach to discretization, based on the idea that the discretized set must be “close” to its Euclidean counterpart, the “closeness” between the two sets being measured by the Hausdorff distance. Now the latter is a metric (it satisfies the axioms of a distance) on the family of all compact sets of a metric space. Thus we formalized our approach as follows. Let E be an arbitrary metric space, in other words E is a set provided with a metric d (E plays the role of a “Euclidean” space). Now let D be a nonvoid proper subspace of E; here D is “discrete” in the following sense: every bounded subset of D is finite, we say that D is boundedly finite. Given a nonvoid compact subset K of E, a possible discretization of K is a compact subset S of D, whose Hausdorff distance to K is minimal (note that since D is boundedly finite, S is in fact finite). We called any such S a Hausdorff discretizing set of K, or simply a Hausdorff discretization of F. In fact, there are in general several such sets, but the family of all Hausdorff discretizations is nonvoid, finite, and closed under union, so their union is the
greatest Hausdorff discretization ofK, (we called it the maximal Hausdorff discretization).
For example, take E = Rn, D = Zn, and a metric d on E induced by a norm which is symmetrical w.r.t. the coordinate axes; for instance d can be the Lp metric, which includes as particular cases the city-block (p = 1), chessboard (p = oo), and Euclidean (p = 2) distances. Then for every nonvoid compact subset K of E, its supercover discretization ASC(K) is a Hausdorff discretiziation of K (Ronse and Tajine, 2001).
p		q		s
w •	o	•	O	•  W\
fA		üiB		C\
		r		
		•		
•
Fig. 2. Top. A compact set K = A U B U C, overlaid with discrete points p,q,r,s and their cells C(p),C(q),C(r),C(s). Bottom. For the Euclidean distance d%, the greatest Hausdorff discretization of K is {p,q,r,s}; we show the circles of radius rH{K) centered about these points. The point r belongs to this discretization because the lower corners of the triangles A and C increase the Hausdorff radius rH{K) of K. The only other Hausdorff discretization of K is {p,q,s}.
This approach to discretization is global, in the
sense that whether a point p G D belongs to a
Hausdorff discretization of K or not, may depend on
points of K which can be at an arbitrary distance
from p (see Figure 2). We showed in fact that the
greatest Hausdorff discretization of K consists of all
points p G D such that BrHK(p), the closed ball
of radius rH{K) centered about p, intersects K; that
radius rH{K), called the Hausdorff radius ofK, is the
maximal distance from a point of K to the closest point
ofD:
rH(K)=maxd(k,D) .                   (4)
keK
Clearly rH (K) depends globally on K (and on D), and it is precisely this dependence of rH(K) on K that makes Hausdorff discretization global.
90
Image Anal Stereol 2004;23:89-109
The main interest of our approach is that the Hausdorff distance between a nonvoid compact set K and its Hausdorff discretizations is equal to the Hausdorff radius rH{K). Now a measure of the resolution (or grid spacing) of the “discrete” space D is what we call the covering radius, namely the supremum rc of the distances of points of E to D:
rc = supd{x,D) .
xeE
For example, when E = Rn,D = (pZ)n and the metric d is induced by a norm, rc will be p times the norm of the vector (\,...,\) (Ronse and Tajine, 2001). We assumed that rc < °°, and we have always rH(K) < rc. Consequently, when the resolution of D tends to zero, so does rH(K), and the Hausdorff discretization tends to the compact set in the Hausdorff metric sense.
We also extended our results to the discretization by dilation (Heijmans, 1994; Heijmans and Toet, 1991). We showed (Ronse and Tajine, 2000) that under the covering assumption, the Hausdorff distance between a nonvoid compact K and its discretization by dilation AA(K) is bounded by the radius of the structuring element A, defined as
rA = supd{o,a) ,
aeA
where o is the origin.
In fact, we adopted a more general approach than the one of (Heijmans, 1994; Heijmans and Toet, 1991) described above. Instead of a structuring element, we considered a windowing function W associating with each point p G E a window W(p) C E; instead of A, we have the dual windowing function W defined by peW(q) ^^ qeW(p) for all p,q G E. The dilation 5W by W is defined as follows:
5W{X) = [J W(x) .
xeX
Here the covering assumption is expressed as E = 8W(D). Now the discretization by dilation by W is the map AW : &>(E) -»¦ &>(D) defined by
VXCE,
AW(X) = SW(X)nD = {peD\W(p)nX^0/} .
We showed that under the covering assumption, the Hausdorff distance between a nonvoid compact K and its discretization AW(K) is bounded by
rW = sup  sup d(p,x) ,
peDxeW(p)
what we call the radius of the windowing function W.
Now if the resolution of D and the radius of W tend simultaneously to zero (while the covering assumption is preserved), the discretization by dilation tends to the original compact set in the Hausdorff metric sense. For example we take E = Rn, D = Zn and a structuring element A satisfying the covering assumption D® A = E; then for a scalar factor p > 0, we change the resolution by taking pD = (pZ)n and p A = {pa \ a G A} instead of D and A, the covering assumption is still satisfied here (pD(BpA = E), but we have rpA = prA. So taking p -»¦ 0, the Hausdorff distance between a compact set and its discretization by dilation will be bounded by prA, which tends to zero.
Let us stress that the standard morphological approach to sampling (Heijmans, 1994; Heijmans and Toet, 1991), as well as our Hausdorff metric approach (Ronse and Tajine, 2000; 2001; 2002; Tajine and Ronse, 2002), are not models of the way image acquisition devices make discrete images from physical phenomena in the (Euclidean) real world. Indeed, a sensor measures the amount of light energy, so this means that for a binary object X, the discretization of X is made of all pixels p such that the area of X n C(p) exceeds some threshold; this discretization calls for a probabilistic formulation (Hall and Molchanov, 1999). However the morphological or metric models are appropriate for image synthesis, as well as for the discretization of structuring elements (shapes chosen by the user) that are used in morphological image processing.
There are reasons calling for an extension of our metric theory of discretization. We explain them below, and point out what we achieved in this respect.
In general, discretization methods are applicable to any subset of E. The theory of morphological discretization has been studied for closed subsets of E. Our approach is based on the Hausdorff distance, which is a metric on the family of compact sets. That is why in (Ronse and Tajine, 2000; 2001) we restricted our discretization to compact subsets of E. However the Hausdorff distance can also be defined on closed sets, and it satisfies then all axioms of a metric, except that it can take an infinite value; we say thus that it is a generalized metric. It is not hard to generalize our theory of Hausdorff discretization to closed sets: this was done in Tajine and Ronse (2002) in the case where E = Rn and D = (pZn), and we have given in Ronse and Tajine (2002) similar results in a more general framework (we will summarize them in Section “Hausdorff sampling”).
One of the purposes of this paper is to extend the methodology of Ronse and Tajine (2002) to morphological discretization. As we will see, the main
91
Ronse C et al: Morphological sampling
results of Ronse and Tajine (2000) extend to any closed set F, in particular the fact that the Hausdorff distance between F and its discretization by dilation with a covering windowing function W is bounded by the radius rW of that windowing function. We have again the convergence, in the Hausdorff metric sense, of the discretization to the original closed set, when the resolution of D tends to zero.
However, since we take an abstract approach with an arbitrary metric space (E,d), some of our results on Hausdorff and morphological discretization given in Ronse and Tajine (2000) can be extended from compact sets to closed sets only if we make some general topological assumptions. For some results we will assume that the closed set F to be discretized is proximinal, which means that for every point p outside F, there is a point q in F at minimum distance to p. Note that if the space E is boundedly compact, that is every bounded closed subset of E is compact, then every closed subset F of E is proximinal. This restriction on the space E is not problematic, since the usual metric spaces Rn and Zn are boundedly compact. Moreover in the classical exposition of the theory of morphological discretization and convergence given in Heijmans (1994), it is generally assumed that the metric space E is boundedly compact. See Section “Topology and closed sets in a metric space” for more details on these notions.
Despite these minor theoretical complications, this generalization from compact sets to closed ones is useful, since it allows one to give models for the discretization of standard unbounded shapes like straight lines, parabolas, etc.
In the classical morphological approach for the discretization of closed sets (Heijmans, 1994), a reconstruction was introduced, and it was shown that the reconstruction of the discretization converges (in the Fell topology, see below) to the original closed set when the resolution of the discrete space tends to zero. As we will explain in Section “Dilation-based sampling”, given a closed subset F of E, a morphological discretization S of F, and a morphological reconstruction R of S in E, not only the Hausdorff distance between F and S, but also that between S and R, are bounded by a multiple of the resolution of the discrete space D, so both S and R tend to F (in the Hausdorff metric sense) when that resolution tends to zero. Thus our approach is simpler than the usual morphological one when it comes to studying the convergence of discretized sets to their originals.
Let us say a few words about topologies used for results about convergence of a discretization to
the original set. We use convergence in the Haudorff metric sense for closed sets (as said above, it is a metric for compact sets, and a generalized metric for closed sets). The topology on nonvoid compact sets induced by the Hausdorff metric has been called in the literature the myope (Matheron, 1975), sup weak or sup narrow (Vervaat, 1988) topology; it is the relative topology on compact sets of the Vietoris (1922) or Michael (1951) topology on closed sets. Note however that on non-compact closed sets, the topology induced by the Hausdorff generalized metric is distinct from the Vietoris-Michael topology.
In the morphological approach to discretization (Heijmans, 1994), convergence results are given in the Fell topology (Fell, 1962), also called hit-or-miss (Matheron, 1975) or sup vague (Vervaat, 1988) topology. Now the Fell topology is a subset of the Hausdorff metric topology (Heijmans, 1994), in other words convergence for the Hausdorff metric is stronger than convergence for the Fell topology. Thus for closed sets, we have a better convergence than in previous morphological works, besides the fact that giving a quantitative bound on the Hausdorff distance in terms of the resolution is more precise than a qualitative result of convergence when the resolution tends to zero.
We can see this in another way. In a boundedly compact space, the Fell topology on closed sets is induced by the Hausdorff-Busemann metric (Busemann, 1955; Heijmans, 1994). Now the Hausdorff-Busemann metric is smaller than the Hausdorff generalized metric (see Subsection “Hausdorff metric on compact, closed, and proximinal sets”), so convergence for the latter is stronger than convergence for the former.
In Ronse and Tajine (2000; 2001) the assumption that the space D is “discrete” took the following form: every bounded subset of D is finite (we say that D is boundedly finite). Here we relax this requirement, we suppose that every bounded closed subset of D is compact, in other words D is boundedly compact. This means that D is not necessarily a discrete space, so we will speak here of “sampling” instead of “discretization”. We already used this general framework in Ronse and Tajine (2002) in order to study Hausdorff sampling (as a generalization of the Hausdorff discretization studied in Ronse and Tajine (2000)), and we will apply it here to the study of morphological sampling as an extension of morphological discretization.
This generalization from the case where D is boundedly finite to that where it is boundedly compact leads to minor complications in the theory, so it needs some justifications. From a theoretical point of view,
92
Image Anal Stereol 2004;23:89-109
this allows us to give a complete theory of sampling on any kind of grid with variable resolution, especially if that grid has accumulation points. For example, in the log-polar model for circular images, where pixels are positioned by sampling the angle and the logarithm of the radius, the origin is an accumulation point of such a grid. Although the accumulation point is excluded from the digital model, it has to be taken into account in any theory that deals with all possibles resolutions (in the same way as the theory of real numbers is necessary to understand digital numbers with arbitrary precision).
Another justification comes from the sampling and quantization of numerical functions. Given the “Euclidean” space E and the “discrete” subspace D, an “analog” function f : E -> R (where R = R U {+00, -00}) must be discretized into a “digital” function fd:D^Z (where Z = Z U {+°o, -00}). In order to apply to functions a discretization method for sets, these functions must be transformed into sets. The customary morphological approach (Heijmans, 1994; Ronse, 1990) is to associate with a function f : E -> R its umbra or hypograph
U{f) = {{p,t)eExR\t<f(p)} .
This umbra is discretized into a discrete umbra A(U(f)) C D x Z, and the digitized function fd is obtained as the upper envelope of A(U(f)).
In classical signal processing, the digitization of a function E -> R usually involves two steps: a spatial sampling transforming its domain E into D, _and a numerical quantization transforming its range R into Z. It is interesting to study these two operations separately, in terms of umbras. The sampling L (from E x R into D x R) transforms the umbra U(f) into a sampled umbra Z(U(F)) CDxR, whose_upper envelope gives the sampled function fs : D -> R. On the other hand, the quantization Q (from ExR into E x Z) transforms the umbra U(f) into a quantized umbra Q(U(F)) CExZ, whose upper envelope gives the quantized function fq : E -> Z. We illustrate this in Figure 3 in the case where E = R and D = Z, and with the discretization by dilation; we use a horizontal structuring element H for sampling, and a vertical one V for quantization, they satisfy the covering assumption by (Z x R) ® H = R2 and (R x Z) e V = R2. Note that the sampling and quantization subspaces Z x R and R x Z used in this example are not boundedly finite, but boundedly compact.
b)
c)
H
d)				...	-"	
e)                !		•
•,,-""		.-»'-"*
V
g)	•
	
	
h)	--	--	
--'''			__.----
			
Fig. 3. a) the function f : R ->¦ R (with the coordinate axes as dotted lines). b) the umbra U(F) C R2. c) the horizontal segment H of length 1 centered about the origin satisfies the covering assumption (Z x R) ® H = R2; we show it with the horizontal neighbourhood of the origin in Z2. d) the sampled umbra Z(U(F)) is made of all points peZxR such that HpnU (F) / 0/. e) the upper enveloppe ofL(U(F)) gives the sampled function fs : Z -»¦ R (with f shown dashed). f) the vertical segment V of length 1 centered about the origin satisfies the covering assumption (R x Z) ® H = R2; we show it with the vertical neighbourhood of the origin in Z2. g) the quantized umbra Q(U(F)) is made of all points peRxZ such that Vp DU(F) / 0/. h) the upper enveloppe ofQ(U(F)) gives the quantized function fq:R^Z (with f shown dashed).
As we will see in Section “Dilation-based sampling”, composing the sampling by H and the quantization by V amounts to discretization of R x R into Z x Z by dilation using the structuring element H®V. However, if we use Hausdorff discretization, the discretization of R x R into Z x Z is not equivalent to the succession of a sampling from E x R into E x Z followed by a quantization from E x Z into D x Z.
An operation similar to the spatial sampling of numerical functions arises when one discretizes an
f)
93
Ronse C et al: Morphological sampling
Euclidean object only in some of its coordinates, so one associates with a closed subset F of E = Ra+b a closed subset S of D = Ra x Zb; again D will be boundedly compact, but not boundedly finite.
Related to the sampling of numerical functions is the discretization of measures on sets. A measure on Euclidean sets is a function /x associating with a closed subset F of E a nonnegative real number /x (F) (say: area, diameter, perimeter, etc.); a corresponding discrete measure ßd associates with a closed set S of D a real number pd(S). Assume that we have a metric m on closed subsets of E (say, the Hausdorff metric derived from a metric on points); it can be extended into a metric non#(E)xR by setting
n((Futi),(F2,t2)) =max(m(Fi,F2),|ti-t2|)  •
Then a way to quantify the quality of \id as discrete approximation of /x, is given by the Hausdorff distance (derived from metric n) between the set ^[/x] of pairs (F, 11(F)) for all closed F c E and the set 3§\p.d\ of pairs (S,ßd(S)) for all closed S c D; if it is < e, it means that for every S closed in D there is some F closed in E with both m(F,S) < e and |/x(F) -Hd(S)\ <L, and vice versa.
Sendov (1990) introduced a metric approach to the approximation of functions, which is in some way related to our approach: to approximate a given function f by a function in some class S, one takes the function g&y such that the Hausdorff distance between the graphs off and g is the smallest possible.
PAPER ORGANIZATION
Section “Topology and closed sets in a metric space” summarizes the essentials about closed and compact sets in a metric space, boundedly compact or boundedly finite spaces, and proximinal sets (see Section 2 of Ronse and Tajine (2002) for more details). It recalls also the Hausdorff metric on compact sets and its extension to closed sets, as well as the Hausdorff-Busemann metric. Section “Hausdorff sampling” is devoted to Hausdorff sampling; it mainly consists of a summary of the main results of Ronse and Tajine (2000; 2002). The theory has different aspects, according to whether we sample compact or closed subsets of E, and whether the sampling subspace D is boundedly finite or boundedly compact. In Section “Dilation-based sampling” we consider topological and Hausdorff metric properties of dilation by a windowing function, and of the method for sampling or discretization based on this operator. Then we discuss the relation of our results with the morphological theory of discretization (Heijmans, 1994). The Conclusion gives the place of these results in relation to previous ones, and suggests possible ways for further research.
TOPOLOGY AND CLOSED SETS IN A METRIC SPACE
This section is devoted to the topological prerequisites of our theory. It consists mainly in recalling more or less known facts from metric topology; the reader is referred to Barnsley (1993); Busemann (1955); Choquet (1966); Hocking and Young (1988); Ronse and Tajine (2002) for more details. In Subsection “Boundedly compact, boundedly finite, and proximinal sets” we give a nomenclature of concepts related to closed sets: boundedly compact and boundedly finite spaces, and proximinal sets. The definition and basic properties of the Hausdorff metric for these sets are given in Subsection “Hausdorff metric on compact, closed, and proximinal sets”. There we recall also the definition of the Hausdorff-Busemann metric.
We present our terminology. Given a topological or metric space E, and a topological or metric property t, for any subset X of E, we will say that X has property t if the relative topological or metric space X has that property. Given a family ,9> (defined from some property) of subsets of the space E, we write ,9" for the family of nonvoid elements of J?; when the space E in which it is defined must be specified, we will write y{E) and ,9"{E). For any X C E, we will write y{X) (resp., ,9"{X)) for the analogous family in the relative topology or metric of X, consisting of subsets (resp., nonvoid subsets) of X having that property.
We write a topological space as a pair (E,if), where if is the family of open subsets; we write & for the family of closed subsets of E. For X C E, write X for the closure of X.
For XCE, the relative topology on X is the one whose open sets are the traces XnGof the open sets GofE.
We write &M for the family of finite subsets of E. Note that (E, if) is Tx iff ^fin C &.
E is compact (resp., sequentially compact) if from every covering of E by a family (resp., countable family) of open sets, one can extract a covering by a finite sub-family of those open sets. When E is nonvoid and compact, every continuous function f : E -> R reaches a minimum and a maximum in E.
A subset X of E is compact if the relative topology on X is compact. Every finite set is compact, and the intersection of a compact set with a closed set is
94
Image Anal Stereol 2004;23:89-109
compact. Write X for the family of compact subsets of E (NB: in Ronse and Tajine (2000), following Barnsley (1993), we wrote J>Y instead of Jf'). Given Y C X, Y is compact in the relative topology on X iff it is compact in the topology on E, that is:
VXCE,    X(X) = X(E)V\»(X) .       (5)
This is analogous to the what happens for finite sets: for XCE, ^fin(X) = ^fin(E) n &>(X). For closed set, we have &(X) 5 &(E) n »(X), but whenX is closed, the reverse inclusion holds, thus
VXG^,     ^(X)=^(E)n^(X) .        (6)
We say that E is separable if E has a countable dense subset (that is, E = X for a countable X).
Let E be any set; a metric on E is a function d : E2 -> R satisfying the following properties for any
x,y,ze E: (i) d(x,x) = 0 and forx^y, d(x,y) > 0; (ii) d(x,y) = d(y,x) (symmetry); (iii) d(x,z) < d(x,y) + d(y,z) (triangular inequality). The pair (E,d) is then called a metric space.
From now on assume that (E, d) is a metric space. Given xeE,we define for any r > 0 the closed ball of radius r centered about x, Br(x), and for any r > 0 the open ball of radius r centered about x, B° (x), by
Br(x) = {yeE\d(x,y)<r}    (r>0)  , and B°(x) = {yeE \ d(x,y)<r}    (r>0).     ()
The metric d endows E with a topology with basis made of all open balls B°(x); in other words the open sets are all unions of open balls. As a topological space, E is T\.
Given X C E, (X,d) is a metric space, and the metric topology of (X,d) coincides with the relative topology on X induced by the metric topology of
(E,d).
A metric space (E,d) is bounded if E = Br(p) for some r > 0 and p G E. A subset X of a metric space is bounded if the metric subspace (X,d) is bounded; in fact X is bounded iff we have X c Br(p) for some r > 0 and p G E.
A Cauchy sequence is a sequence (x„)„6N in E, such that for any L > 0 there is some M G N such that for all m,n>Mwe have d(xm,x„) < e. We say that the metric space (E,d) is complete if every Cauchy sequence in E converges to some point in E.
The following characterization of compactness of a metric space is well-known:
Property 1 A metric space is compact iff it is sequentially compact, and then it is complete.
Note that every compact subset of a metric space is bounded and closed. The reciprocal is not always true, see the next Subsection.
Now we consider separability in a metric space, and its relation to compactness:
Property 2 The following properties are equivalent in a metric space (E,d):
1.   E is separable.
2.   The topology on E has a countable basis.
3.   From every covering of E by open sets, one can extract a countable covering.
Note that if E has a countable basis, the same holds for any subspace of E. Hence any subspace of a separable metric space is separable.
The space E is said to be locally compact if every point of E has a neighbourhood whose closure is compact; when E is a metric space, this means that for every p G E there is some r > 0 such that Br(p) is compact. Every closed subspace of a locally compact metric space is locally compact.
Property 3 Let (E,d) be a metric space.
1.   If E is a countable union of compact sets, then E is separable.
2.   When E is locally compact, E is separable if and only if it is a countable union of compact sets.
Let us now make some definitions that will be used in relation to the Hausdorff distance between closed
sets.
Given a subset X of E, for every point p G E we define the distance between p and X as
d(p,X) = inf{d(p,x)\xeX} .            (8)
We have d(p,X) = 0 iff p G X. Note that the function “distance to X” p h-> d(p,X) is Lipschitz: \d(p,X) -d(q,X)\ < d(p,q), hence continuous.
For r > 0 we define the dilation of radius r as the map 8r: »(E) -»¦ &>(E) given by
Sr(X)= \jBr(x) ,                     (9)
xeX
95
Ronse C et al: Morphological sampling
and for r > 0 we define 8°, the open dilation of radius r,by
8°(X) = \jB°(x) .                   (10)
xeX
For r > 0 we define the upper dilation of radius r as the map 8+ : &>(E) -»¦ L*(E) given by
5+(X) = f|5;(X) = f|5s(X) .          (11)
s>r                   s>r
(The last equality comes from the fact that for t > s > r we have S°(X) c 8s(X) c $°(X).) We have always
5r°(X) = {p G E | d(p,X) < r} ,          (12)
and combining this with (11), we obtain
8+(X) = {peE\d(p,X)<r} .         (13)
Note that S°(X), being a union of open balls, is open. On the other hand S+(X), being the inverse image of the closed interval [0,r] by the continuous function x h-> d(x,X), is closed. We have the following inclusions:
8°{X)c8r{X)c8+{X) ,
and   \/s>r,    8+(X)c8°(X) .   (14)
The condition for having 8r(X) = S+(X) will be discussed in the next Subsection. For X bounded, 8r(X) is also bounded: X c Bs(p) gives 8r(Bs(p)) c Br+s(p).
In the sequel we will use the following elementary result:
Lemma 4 Let (E,d) be a metric space, and let F G &'(E) and K G X'iE) such that F n K = 0. Then there is some h>0 such that for every peKandqeF wehaved(p,q)>h.
BOUNDEDLY  COMPACT,   BOUNDEDLY FINITE, AND PROXIMINAL SETS
As said above, every compact subset of a metric space is bounded and closed; the reciprocal does not always hold (for example the metric space (E,d), where E is infinite and d(p, q) = 1 for any two distinct p, q G E, is bounded and closed, but not compact). We consider here the case where this reciprocal is verified.
Definition 5 A metric space (E,d) is called boundedly compact (or in brief: BC) if every bounded and closed subset of E is compact.
Heijmans (1994) says that E is finitely compact, following Busemann (1955). Note that any compact space E is boundedly compact. A subset X of E is called boundedly compact if the metric subspace (X, d) is boundedly compact. Write ,^hc for the family of boundedly compact subsets of E.
There are alternate formulations for this definition (Lemma 1 of Ronse and Tajine (2002)):
Lemma 6 The following properties are equivalent in a metric space (E,d):
1.    E is boundedly compact.
2.    For every peEandr>0, Br(p) is compact.
3.    For every infinite and bounded X<ZE, some yeE is a limit point ofX (that is, Mr > 0, B°(x) DX\
{y} + 0/).
A boundedly compact space has the following topological properties (Heijmans, 1994):
Property 7 A boundedly compact metric space is locally compact, separable, and complete.
Using the analogy between compact sets and finite sets (cfr. the comment after (5)), we will now consider a property stronger than being boundedly compact, which corresponds to the notion of a discrete space in image processing:
Definition 8 A metric space (E,d) is called boundedly finite (or in brief: BF) if every bounded subset of E is finite.
Note that in this definition we do not require the bounded subset to be closed, because for a bounded X, X is bounded by the same ball as X.
Clearly every boundedly finite space is boundedly compact. In fact, a boundedly finite space E is countable (it is Un=i Bn(p) for p fixed, with each Bn(p) finite). A space E is boundedly finite and compact iff it is finite. A subset X of E is called boundedly finite if the metric subspace (X,d) is boundedly finite. Write ^bf for the family of boundedly finite subsets of E.
There are alternate formulations for this definition (Lemma 2 of Ronse and Tajine (2002)):
Lemma 9 The following properties are equivalent in a metric space (E,d):
1.   E is boundedly finite.
96
Image Anal Stereol 2004;23:89-109
2.    Every bounded subset ofE is compact.
3.    E is boundedly compact, and every subset ofE is closed.
4.    For every p G E and r > 0, Br(p) is finite.
Note that a boundedly finite metric space (E,d) is discrete in the classical sense (i.e., F = G = P(E)).
The next notion that we will use is a property of subsets of a metric space, and not of that space itself; it comes from Borwein and Fitzpatrick (1989); Deutsch and Lambert (1980):
Definition 10 A subset X ofE is called proximinal if
either X = 0, or for every y <L X, there is some x G X minimizing the distance to y, that is
Vy(LX,3xeX   d{y,x) = d{y,X) .
Write Fp for the family of proximinal subsets of E. Note that E is trivially proximinal.
Finite, boundedly finite, boundedly compact, compact and closed spaces or sets, as well as proximinal sets, are all that needs to be considered for our theory. Let us describe the relations between all the above notions.
Proposition 11 In any metric space (E,d):
1.    Jf U ^bf C ^bc C «^p C «r and Jfn^bf = ^iin.
2.    IfE is boundedly finite, then every subset ofE is boundedly finite, that is &bf = ,^hc = &v = & = &{E).
3.    If E is boundedly compact, then every closed subset ofE is boundedly compact, that is ,^bc = 3?p = 3?.
Items 1 and 3 are essentially Proposition 1 of Ronse and Tajine (2002), while item 2 is a straightforward consequence.
Let us now see the relation of boundedly compact and proximinal sets with 8r, the dilation of radius r (9). ForX G &>(E), we have always X = 80(X), while So(X) = {peE\ d(p,X) = 0} = X. Thus Sq(X) = {p G E | d(p,X) = 0} iff X is closed. For r > 0, (13,14) give Sr(X) C 8+(X) = {peE\ d(p,X) < r}, and the inclusion can be sharp, even for X closed. In Proposition 2 and Corollary 1 of Ronse and Tajine (2002) we proved the following two results:
Proposition 12 In a metric space (E,d), a set X is proximinal iff for every r>0we have
8r{X) = {peE\d{p,X)<r} ,
that is Sr(X) = S+(X). In particular,  when X is proximinal, 8r(X) is closed.
Proposition 13 The     following     properties     are equivalent in a metric space (E,d):
1.   E is boundedly compact.
2.   For every nonvoid compact K and r > 0, ?r(K) is compact.
3.   For every nonvoid closed F and r > 0, ?r(F) is boundedly compact.
HAUSDORFF METRIC ON COMPACT, CLOSED, AND PROXIMINAL SETS
LetX and Y be two nonvoid compact subsets ofE. We define
hd{X,Y)=max{d{x,Y)\xeX} ,        (15)
which we call the oriented Hausdorff distance from X to Y. We define the Hausdorff distance between X and Y as:
Hd(X,Y) = max(hd(X,Y),hd(Y,X))  .         (16)
It is well-known (Barnsley, 1993) that Hd is a metric on the space Jf' of nonvoid compact subsets ofE, and that (E,d) is complete iff (Jf'(E),Hd) is complete. We have the following characterization (Barnsley, 1993) of hd and Hd:
Property 14 For everyX,Y G Jf'andfor every r>0:
hd{X,Y)<r   ^   XQ8r{Y)  , Hd(X,Y)<r   ^   X<z8r{Y)andY<z8r{X) .
(17) In particular
-    hd(X,Y) is the least r > 0 such thatX C 8r(Y).
-    Hd(X,Y) is the least r > 0 such that both X C 8r{Y)andY<z8r{X).
In the case where E = Rn and d is the Euclidean distance, in the above formulas 8r(Y) and 8r(X) are replaced by the Minkowski additions Y ® ,<%r and X®mr respectively, where mr = Br(0); such an expression of the Euclidean Hausdorff distance in terms of Minkowski additions was considered in Serra (1982).
97
Ronse C et al: Morphological sampling
One can extend the Hausdorff metric from Jf' to &' (Baddeley, 1991). Given two nonvoid closed sets X and Y, we set
hd{X,Y)=sup{d{x,Y)\xeX} ;         (18)
now we define the Hausdorff distance Hd(X,Y) as in (16). Then Hd is a generalized metric on &; by this we mean that Hd satisfies the axioms of a metric, with the only difference that it can take infinite values. Nevertheless {&',Hd) will define a topology on &' in the same way as a metric space, but here we have to consider only the balls of finite radius.
Let us recall that when taking infima and suprema of non-negative reals, one sets to 0 an empty supremum and to °o an empty infimum: sup0 = 0 and inf 0 = oo. Using (11,13), we see easily that Property 14 becomes here:
Property 15 For every X,Y G &' and for every r > 0:
hd(X,Y)<r<^XC8+(Y) ,                      (19)
Hd(X, Y) < r ^^ X C 5+ (Y) and Y C 5+ (X) .
In particular
-    hd{X,Y)=inf{r>0\XC8r{Y)}.
-    If hd(X,Y) < oo, it is the least r > 0 such that
XC8+(Y).
-    Hd{X,Y) = inf{r > 0 | X C 8r{Y) andY C 8r{X)}.
-    IfHd (X, Y) < oo, it is the least r > 0 such that both X<z8+(Y)andY<z8+(X).
However, from Proposition 12 it follows that for two nonvoid proximinal sets X,Y,in Property 15 we can replace S+(X) and S+(Y) by 8r(X) and 8r(Y); hence (19) becomes (17) and Property 14 is true for
Hd(X,Y) <oo.
We have an alternative definition for the Hausdorff distance on &' (Baddeley, 1991):
yX,Ye^',    Hd(X,Y) = sup\d{p,X)-d{p,Y)\  .
peE
(20)
Note that it is also possible to define the Hausdorff distance when one of the sets is empty, using formulas (8,18):
hd(0/,0/)   =   Hd(0/,0/)    =   0 ; VFg^',                        hd(0/,F)    =   0       (21)
and   hd(F,0/)    =   Hd(F,0/)    =   °o .
Then Property 15 remains true in this particular case.
In the sequel we will use the following result in conjunction with Lemma 4:
Lemma 16 Let (E,d) be a metric space, and let F0,Fi G &'{E) andh>0 such that for every p G F0 and qeFlwe have d(p,q) > h. Then for every F G &(E) such thatHd{F,F{) < h, we have F C\F0 = 0.
Proof   F / 0/ by (21). Take any p G F0. We have
d{p,Fi) > h; now (20) gives \d{p,F) -d{p,F{)\ < Hd{F,Fi) < h; combining the two inequalities, we get d(p,F) > 0, so that p (/ F. Q.E.D.
The Hausdorff-Busemann distance (Busemann, 1955; Heijmans, 1994) is the metric on nonvoid closed sets defined by setting VX, Y G &':
HBd(X,Y) = supe-d(o'pi\d{p,X)-d{p,Y)\  ,   (22) peE
where o is a fixed point of E (the origin). Now HBd(X,Y) <2 + d{o,X) + d{o,Y), so that HBd takes always finite values (contrarily to the Hausdorff distance for non-compact closed sets). Of courses, we have HBd{X,Y) < Hd{X,Y), so that the topology on &' arising from the Hausdorff-Busemann metric is smaller than the one arising from the Hausdorff metric (and convergence for the Hausdorff metric is stronger than convergence for the Hausdorff-Busemann metric).
HAUSDORFF SAMPLING
In Ronse and Tajine (2000) we gave a new theory of discretization of nonvoid compact subsets of a metric space (E,d) into a boundedly finite space D. In Tajine and Ronse (2002) we also considered the discretization of nonvoid closed sets in the case where E = Rn and D = (pZ)n. This theory was extended in Ronse and Tajine (2002) to the case where D is boundedly compact instead of boundedly finite, and then to closed sets instead of compact ones. We summarize these results here, and give a few new ones.
Formally, we have a “Euclidean” metric space (E,d) and a possibly “discrete” space D, which is in fact a nonvoid proper subspace of E (0 / D c E). We assume that D is boundedly compact. We consider the transformation of closed subsets of E into closed subsets of D, what we call sampling; it is only in the particular case where D is boundedly finite (“discrete”) that we will speak of discretization.
98
Image Anal Stereol 2004;23:89-109
We define the covering radius (of D for the distance d) as the positive number rc given by
rc
supd(x,D)
x?E
hd(E,D)
(23)
In Ronse and Tajine (2000; 2002), we assumed that rc < oo. Indeed, the Hausdorff distance between a closed set and its Hausdorff samplings will then be bounded by rc. Note that since D is closed, for x i D we have d(x,D) > 0, and since D is a proper subset of E, we get rc > 0.
For any F G &'(E), the Hausdorff radius of F (Ronse and Tajine, 2002) (w.r.t. D for the distance d) is the nonnegative number
rH(F)
supd(x,D)
x?F
hd(F,D)
(24)
This generalizes the similar definition (4) made for compact sets in Ronse and Tajine (2000).
Obviously rc = rH{E) and rH{F) < rc for F G &'(E). As D is proximinal, applying Proposition 12 and Property 15 with X = F and Y = D, we get: rH(F) is the least r > 0 such that F C Sr(D). In particular for F = E: rc is the least r > 0 such that E = Sr(D). This generalizes Lemmas 16 and 22 of Ronse and Tajine (2000).
Let us now recall the definition of Hausdorff sampling (Ronse and Tajine, 2002). For F G &'(E), a Hausdorff sampling of F (Ronse and Tajine, 2002) is any S G &'(D) which minimizes the Hausdorff distance Hd(F,S). We define the set JtH{F) of Hausdorff samplings of F:
JKH{F) = {S g &'{d) | vT G &'{D),
Hd(F,S)<Hd(F,T)} .
(25)
Note that when F is bounded (for example, if F is compact), then for any closed subset S of D, Hd (F, S) < oo implies that S is bounded, and as D is boundedly compact, S is compact. We get thus:
VK€Jtr'(E), ^H(K) = {SeJf'(D)\VTeJf>(D),        (26) Hd(K,S)<Hd(K,T)} ,
which is the definition of Ronse and Tajine (2000).
It is also possible to define Hausdorff sampling for the empty set. From (21) we derive that:
^h(0) = {0}    and    rH(0/) = 0
(27)
In the sequel, we will consider the properties of Hausdorff sampling only for nonvoid closed sets, but these properties trivially hold for the empty set.
We need to discuss the relevance of the requirement that rc < °°. In fact, it is essential only for sampling unbounded sets. Indeed, let F be a nonvoid, bounded and closed subset of E. For any compact subset S of D, Hd(F,S) will be finite. There is thus some r > 0 such that we have Hd(F,S) < r for some S G JT'(D), hence J(H{F) C 8+(F), in other words JlHiF) is bounded. Taking E0 = 8+(F) and D0 = E 0 n D, E0 is closed, D0 is nonvoid (it contains S) and boundedly compact (by Proposition 11), and JlHiF) C D0. Hence for Hausdorff sampling of F, we can replace E and D by E0 and D0, and rc by hd(E0,D0), which is finite. On the other hand, if F is unbounded, for any closed subset S of D, we have
Hd{F,S) > hd{F,S) > hd{F,D) = rH{F) ,
so that if rH{F) = °o, all closed subsets of D will be at infinite Hausdorff distance from F, and JlHiF) = &'{D), which is meaningless. Thus we need a guarantee that rH(F) is finite, and as rc = rh{E) > rh(F), we must require rc < °o.
We can thus summarize our axioms for Hausdorff sampling:
-     (E,d) is a metric space, D is a nonvoid proper subspace of E (0 / D c E), and D is boundedly compact.
-    Hausdorff sampling applies to closed subset of E.
-    If the sampling is not restricted to bounded subset of E, then the covering radius rc must be finite.
We recall a few more definitions from Ronse and Tajine (2002). For r > 0, the sampling of radius r is the map Ar :&{E)^> &{D) defined by
VXCE,
Ar(X) = Sr(X)nD
= {peD\Br(p)nX^0/}
(28)
Now the open sampling of radius r is the map A° : &>(E)^0>(D) defined by
VXCE,
A°(X) = 8°(X)f]D
= {peD r B°r(p)nX^0/}
(29)
Finally, we define the upper sampling of radius r as the map A+ : &>(E) -»¦ &{D) given by
VXCE,    A+(X) = f]As(X) = 8+(X)nD.   (30)
Thanks to (13) and Proposition 12, we get the following result (Ronse and Tajine, 2002):
_
s>r
99
Ronse C et al: Morphological sampling
Lemma 17 ForX G &>(E) and r>0,
A+(X) = {peD\d{p,X)<r}
(31)
and this set is closed. When F is proximinal, A+ (F) =
Ar(F).
In Ronse and Tajine (2002) we extended the approach of Subsection 3.4 of Ronse and Tajine (2000) in order to give an explicit description of Hausdorff sampling:
Proposition 18 Let F e &'{E) and S G &'{D). Then Hd(F,S) > rH(F), andforany r > rH(F), Hd(F,S) < r iff both S C A+(F) and F C 8r(S).
Corollary 19 For F G &'{E) and r > rH{F), we have Hd{F,At(F)) <randHd{F,\^F)) < r.
Theorem 20 For F G &'(E),
1.    A+    } (F) is the greatest Hausdorff sampling ofF;
2.    the Hausdorff samplings of F are the closed subsets ofA+(F)(F), whose dilation of Hausdorff radius covers F:
J(h{F) = {S G &'{D) | S C A+ {F)(F), and F C
SrH(FS)};
3.    the Hausdorff radius of F minimizes the Hausdorff distance beween F and nonvoid closed subsets of D:
rH(F) = min{H(F,S) | S G &'(D)},   that  is
Hd(F,A+H{F)(F))=rH(F).
Remark 21 When F is proximinal, by Lemma 17, for every r > 0 we have A+ (F) = Ar(F) = Ar(F), so:
-    in Proposition 18,Hd(F,S)<r iff both SCAr(F) andFC8r(S);
-    in Corollary 19, Hd (F, Ar (F)) < r;
-    in Theorem 20, Ä+(F) (F) = Ar[l{F) (F).
Hence for proximinal sets, the above three results take the same form as the ones given in Ronse and Tajine (2000) for compact sets (in the case where D is boundedly finite); the only difference is that we consider here S G &'(D) instead of S G JT'(D), but see above how (26) derives from (25). In particular, if E is boundedly compact, then every closed subset of E is proximinal, so we obtain the same theory as for compact sets. Note also that for D boundedly finite, a subset of D is compact iff it is finite, that is why in Ronse and Tajine (2000) we always considered finite subsets of D.
We have rH(F) < rc, so we have a bound on the Hausdorff distance rH(F) between a closed set F and any of its Hausdorff samplings. Now rc is a measure of the resolution of D, so when that resolution tends to zero, the Hausdorff distance between F and its Hausdorff samplings tends also to zero.
In Ronse and Tajine (2000; 2002), we wrote ?H(F) for the greatest Hausdorff sampling; thus ?H(F) = ?+rH(F)(F). The following generalizes several arguments from Ronse and Tajine (2000; 2002):
Proposition 22 Let F G &'(E) and let y be a nonvoid part of .J?H{F); then [j^ G ^h(F). In particular, when D is boundedly finite, [j^ is closed and\jy LJ?h{F).
Proof Apply Theorem 20. For all S G y, S C A+ {F){F), hence [j^ ^ Kh(f)(f), and as AtH(F)(F) is closed (Lemma 17), \Jy C A+ {F){F). For S G
y,   F <z SrH{F)(S),   and   as   K \jy,   we   get
F C 8r[l{F)(\Jy\ Hence \Jy G MH{F). When
D is boundedly finite, every subset of D is closed (Lemma 9), so \jy = \jy. Q.E.D.
The reader is referred to Propositions 6 and 7 of Ronse and Tajine (2002) for further results on the structure of MH(F). There we considered also an alternate definition of Hausfdorff sampling for a non-compact set: take the union of the greatest Hausdorff samplings of its compact parts:
A(X)
U    Ah(k)
KeK'(X)
We showed in Proposition 9 of Ronse and Tajine (2002) that this gives:
1.    if for some p e F we have d(p,D) = rH(F), then A(F) = ArH{F)(F);
2.    if for every p e F we have d(p,D) < rH(F), then
a(f)=a°h{f)(f).
Note that for F compact, we are in case 1 (cfr. (4)), and according to Theorem 20 and Remark 21, A(F) = ArH{F)(F) is the greatest Hausdorff sampling.
By Corollary 19, we have Ar[l{F)(F) G JCH{F). We showed in Proposition 10 of Ronse and Tajine (2002) that in case 2, A°F) (F) G JKH{F). So, in any
case, ~K(F) G MH{F). Note that if D is boundedly finite, every subset of D is closed, so that ArH{F)(F)
100
Image Anal Stereol 2004;23:89-109
and ??rH(F) are always closed, hence we don’t need to take the closure of these sets.
We can give a bound on the cardinal of some Hausdorff samplings:
Proposition 23 Let F G &'{E) such that F is separable. Then every S G JtH{F) has a countable subset T such that T G J?H{F). The cardinal of T is at most that of the continuum.
Proof By Property 2, as F is separable, from every covering of F by open sets, one can extract a countable covering. Take S G JtH{F) and let r = Hd(S,F). For any integer n > 0, we have F C \JxeSB°+l/n{x)
because hd(F,S) < r; as F is separable, there is a countable Sn <z S such that F c {JxeSnB°r+i/n(x). Let T = \Jn>oSn; thus T is countable. As T C S G J^(D), T G ^'(D). Then for every n > 0, as Sn C T , we_have F C xeTBr+i/nx, which implies that hd(F,T) < r+1/n; as this holds for all n > 0, we get hd(F,T) < r. Now as hd(S,F) < r and T C S,_we get hd(T,F) < r. Therefore Hd(T,F) < r and so T G .^H(F). Since T is countable, the cardinal of T is at most that of the continuum. Q.E.D.
Note that every subset of E which is compact, boundedly compact, or a countable union of compact subsets, is separable (see Properties 2, 3 and 7). For example, if E is boundedly compact, then every closed subset of E is boundedly compact, and hence separable. When D is boundedly finite, Proposition 23 is unnecessary, since every subset S of D is countable.
DILATION-BASED SAMPLING
In this section we will generalize the results of Ronse and Tajine (2000) concerning sampling (or discretization) by dilation and its “cover” variant, based on the notion of covering windows. There we assumed that the subspace D is boundedly finite, and we gave bounds on the Hausdorff distance between a compact set and its discretization. Here, as in the previous section, we assume that D is boundedly compact, and give similar bounds for a closed set instead of a compact one.
Then we will apply our results to the classical morphological approach for discretization. We will show that our approach is more natural and gives a better convergence of the discretization to the original set when the grid resolution tends to zero.
PRELIMINARIES
In order to give our theory of sampling by covering windows, we require several mathematical preliminaries.
It is well-known (Matheron, 1975; Serra, 1982) that in the Euclidean space Rn, the Minkowski sum F e K of a closed set F and a compact set K is closed. We will give below three generalizations of this result, where we replace the Minkowski sum by the dilation of a closed set by closed windows.
Let U and V be two “spaces”, in fact arbitrary sets. We consider a map W : U ->¦ 0>{V) which associates with every p G U a window W(p) C V, and call it a windowing function. The dual windowing function is the map W : V ->¦ &>(U) defined by
\/peU,\/qeV,     pe W{q) <=^ q G W(p)  .  (32)
In particular, we have W = W. Note that a window W(p) or W(q) can be empty; indeed, for every q G V such that q L W(p) for all p G U, we have W(q) = 0/. We define now the map SW : ^(U) -> ^>(V) as follows:
VXCU,    SW(X)= \JW{x) .          (33)
xgX
Here 8^ is a map &>(V) ->¦ ^(U). It is easily checked that
VX C U,      W{X) = {q G V | W(q) nX / 0/} ;
VY c V,    8W(Y) = {peU\ W(p) n Y / 0/} .
(34) For example, take U = V = E (where E = Rn or Zn), let A be a subset of E, and for every p G E set W (p) = Ap = {a + p | a G A} (the translate of A by p); then 8W(X) reduces to the Minkowski addition X® A. On the other hand, the dual window W gives W(p) = {A ¡)p and 8W(X) =X®A ¡, where A = {-a | a G A}.
We recall some classical notions of mathematical morphology (Heijmans, 1994; Serra, 1988). A map 8 : &>(U) ->¦ 0>{V) is called a dilation if it distributes the union operation:
VXiCU, ieI,    8(\)Xi)=\j8(Xi) ;
ieI              ieI
(in particular, for I = 0: 8 (0) = 0). Then we have a one-to-one correspondence between dilations &>(U) ->¦ ^(V) and windowing functions U ->¦ ^(V), in the sense that:
-    Given a windowing function W : U ->¦ ^(V), 5W is a dilation.
101
Ronse C et al: Morphological sampling
- Every dilation 8 : ,^>{U) -> &>(V) is of the form SW for a unique windowing function W : U -> ^(V). In fact, for every peUwe have W(p) = $({p}).
We will call 5W the dilation by W. For more details on the standard properties of 5W, as well as examples, see Ronse and Tajine (2000).
We will now concentrate on the case where U and V are metric spaces (U,du) and (V,dv). Write Hu and Hv for the corresponding Hausdorff generalized metrics on closed sets. We will see under what conditions the dilation of a closed set with closed windows gives a closed set.
For a windowing function W : U ->¦ &'(V) (i.e., such that every window W(p) is nonvoid and closed), we say that W is continuous if it is a continuous map from the metric space (U,du) to the generalized metric space (&'(V),Hv), in other words if
\/peU,\/r>0, 3s >0, \/qeU, du(p,q) <s ==> Hv(W(p),W(q)) < r .
Our first result gives sufficient conditions for the dilation  W (F) by the dual window W to be closed:
Proposition 24 Given two metric spaces (U,du) and (V,dv), and a continuous windowing function W:U^ &'(V):
1.   for every KG J(r(V),8W(K)e &(U);
2.    if all windows W (p) (p G U) are compact, then for every F G &(V), 8W(F) G &{U).
Proof Let F G &(U); assume that either F is compact or all windows W(p) are compact. If F = 0, then 8W(F) = 0 G &{U). Assume now that F / 0/. Let peU\ 8W(F); then by (34) W(p) D F = 0. As one of F and W(p) is nonvoid closed and the other is nonvoid compact, by Lemma 4 there is some h > 0 such that for every x G W(p) and y G F we have du(x,y) >h.AsW is continuous, there is some s > 0 such that for every qLU, du(p,q) < s implies that Hv(W(p),W(q)) < h. Now by Lemma 16 we have W(q) D F = 0, that is q G U\5^(F). We have thus shown that forp g U\5^(F), there is some s > 0 such that B°(p) <^U\ W~(F). Hence U\5^(F) is open in U, and 5^(F) G W{U). Q.E.D.
In order to obtain ?W(F) closed, we have an analogue of only the first item of the previous proposition:
Proposition 25 Given two metric spaces (U,du) and (V,dv), and a continuous windowing function W :U ->¦ &>'(V), for every K G JtT{U), SW(K) G ^(V).
Proof If K = 0, then SW(K) = 0 G &(V). Assume now that K / 0/. Let p G V \ 5W(K). As W is continuous, for every x e K, for every r > 0, there is some s > 0 such that for every y G K, du(x,y) < s implies Hv(W(x),W(y)) < r, so that by (20) we have \dv(p,W(x)) - dv(p,W(y))\ < r. Thus the map K -»¦ R : x h-> dv(p, W(x)) is continuous, and as K G Jf(U), it admits a minimum h: there is some zp G K such that dvpWfzp)) = h and for every xeKwe have dv(p,W(x)) > h; now as p L SW(K), p i W(zp), and as W(zp) is closed, h = dv(p,W(zp)) > 0. For every x G K, as dv(p,W(x)) > h, we have B°h(p)nW(x) = 0. So Bjj(p) C V \ 8W(K). We have thus shown that for every peV\SW(K), there is some h > 0 such that Bž(p) CV\^(K . Hence V \ SW(K) is open, and 5W(K) is closed. Q.E.D.
We do not have a similar analogue for the second item of Proposition 24. We show an example of a continuous windowing function W : U ->¦ Jf'(V) such that for some F G &'(U), SW(F) is not closed. Indeed, take U = V = R, with dU = dV being the usual metric d(x,y) = \x-y\, and let W(x) = {arctanx}. Clearly W is a windowing function R -> Jf'(R). As the function arctan is continuous, and the Hausdorff distance between singletons reduces to the distance between points (that is, Hd({p},{q}) = d(p,q)), W is continuous. But R is closed and 8W(R) =} -n/2,+n/2[, which is open.
Note that in this example, the distance d(x,arctan(x)) is not bounded over R, which is contrary to the usual practice of taking bounded windows, in the sense that we have a bound M such that d(x,y) < M for every point x and every yeW(x). However, we can take in R the metric d! given by d'(x,y) = \x-y\/(1 + \x-y\), which is topologically equivalent to d; then the map arctan is still continuous on (R,dr), and for all x,y G R we have d'(x,y) < 2, so d'(x, arctan(x)) is bounded over R. However for the metric d!, R is bounded and closed, but not compact, so it is not boundedly compact.
We will thus require a bounded distance between each p and the points of its window W(p), and apply the dilation 5W to a boundedly compact set F:
Proposition 26 Consider a metric space (E,d), two closed subspace U and V of E, and a continuous windowing function W:U^>&'(V) such that
sup sup d(x,y) < oo . xeUyeW(x)
102
Image Anal Stereol 2004;23:89-109
Then for every Fe ß^{U), 8W{F) e &(V).
Proof If F = 0, then SW(F) = 0 G &(V). We assume now that F / 0/. For some r > 0, we have d(x,y) < r for every x G F and y G W(x). Let p G V \ SW(F); setK = Ff] B2r(p); as F is boundedly compact, K is compact. As ^(K) c^(F), we have p L ^(K), and by Proposition 25, 5W(K) is closed, so there is some s > 0 with SW(K) nB°(p) = 0. Let h = min(s, r), so 5W(K) n B^(p) = 0. Now for x G F \ K, we have d(p,x) > 2r, while for ally G W(x), d(x,y) < r, so that d(p,y) > r > h; hence W(x) nB°h(p) = 0. Thus SW(F \ K)nBl(p) = 0. Hence 5W(F) = 5W(K) U 5W(F\K) is disjoint from B°h(p), that is B°h(p) <^V\5W(F). Therefore V\5W(F) is open, that is 5W(F) is closed. Q.E.D.
In the Euclidean space Rn, for a closed set F and a compact set K, we have F ® K = SW(F) for the windowing function W defined by W(p) = Kp (the translate of Kby p). We can also write F®K = 8Wi (K) for the windowing function W defined by W'(p) = Fp. For any closed subset A of Rn, we have Hd(Ap,Aq) < d(p,q) for any translation-invariant distance d, so the windowsW and W are continuous. In fact, their duals W and W, given by W(p) = (K) p and W'(p) = (F) p (where K ¡ and F are the symmetricals of K and F), are also continuous. So any of items 1 and 2 of Proposition 24, Propositions 25 and 26 can be applied to obtain that F ® K is closed.
Note however that the Minkowski sum of two unbounded closed subsets of Rn is not necessarily closed. Take for example n = 2, Fx = {(x,0) | x G R} and F2 = {(y,arctany) | y G R}. Then Fx ® F2 = {(x + yarctany) | x,y G R} = Rx] - n/2,+n/2[, which is not closed.
We will now give a general result which will be used for sampling and reconstruction.
Proposition 27 Let (E,d) be a metric space, letr>0
and letW : E ^ ,^>{E) be a windowing function such that for every x G E andy G W(x) we have d(x,y) < r. Then for any F,F' G &{E) we have:
1.    IfF' C 8W(F), then hd(F',F) < r.
2.    IfF C d^F7), then hd(F,F') < r.
3.    IfF' C 8W(F) and F C S^F1), then Hd (F, F')<r.
4.    IfW(p) ^ 0/for every p G F, then Hd (F, 5W{F)) < r.
Proof 1: If F = 0, then SW(F) = 0, 5W(F) = 0, so F' = 0 and hd(F',F) = hd(0,0) = 0 by (21); so we assume that F / 0/. Let z G F'; as F' c 5W(F), for every h > 0 there is some y e SW(F) such that d(z,y) < h; there is some xeF such that yeW(x), and so d(x,y) < r; hence d(z,x) < r+h, and we derive that d(z,F) <r + h for all h > 0, that is d(z,F) < r. Hence hd(F',F) <rby(18).
2: For x G E andy G W(x) we havex eW(y) and so d(y,x) < r. The result follows from applying item 1 with W instead of W and F and F' interchanged.
3:     We combine items 1 and 2 with (16).
4: If F = 0, then 5W(F) = 0, and by (21) Hd(F,8W(F)) = Hd(0/,0/) = 0; so we assume F / 0/. For every x G F, there is some y G W(x); here y G 5W(F), so y G MF); butx G W(y), so x G 8W (~8W(F))
and x G SW(MF)). We have thus shown that F ^ SW(SW(F)). The result follows by applying item 3 with F' = 8W(F). Q.E.D.
WINDOW-BASED SAMPLING
Let us apply the above results to sampling by dilation and related samplings using windows. Let (E,d) be a metric space, and D a nonvoid proper subspace of E. We consider a windowing function W : D -»¦ &>(E) (or more generally E -»¦ &>(E)). For the moment, we do not yet put any topological condition on D and W; later we will require that D is boundedly compact, and W : D -> ^'(E) is continuous. We recall first some notions from Ronse and Tajine (2000):
Definition 28 For any windowing function W:
-    For X C E, we say that W covers X if every point of X belongs to some window W(p) (p G D), in other words if X<zSW(D).
-    We say that W is covering if W covers E, that is E = SW(D).
-    The radius ofW is the nonnegative number
rW = sup  sup  d(p,x) .             (35)
peDxeW(p)
The first item of the following result comes from Proposition 10 of Ronse and Tajine (2000); the last three items generalize Lemma 29 of Ronse and Tajine (2000) to closed sets, and their proof is the same:
Lemma 29 For any windowing function W:
1.   ForX G &>(E), W coversXiffX C 5W{AW{X)).
103
Ronse C et al: Morphological sampling
2.    IfW covers F G &'(E), then rw > rH{F).
3.    IfW is covering, then rw > rc.
4.    Ifrw < oo, then rw is the least r>0 such that for allpeD we have W(p) C Br(p).
The following definition comes from Ronse and Tajine (2000) (see equation (15) and Definition 12 there):
Definition 30 Let W be a windowing function.
1.   The sampling by dilation by W is the map Aw :
&>(E) ->^(D) defined by:
VXCE, AW(X)
<%(X)nD                          (36)
{peD\W(p)nX^0/} .
2. For anyX<ZE such that W covers X, and S <Z D, we say that S is a W-sampling of X if both the following hold:
-   For everypeS,W(p)nX^ 0/, in other words
SCAW(X).
-   XC\JpeSW{p) = 5w{S).
In Ronse and Tajine (2000) we said a W-discretizing set of X for a W-sampling of X. When W covers X, by item 1 of Lemma 29, AW(X) is a W-sampling of X, and in fact it is the greatest W-sampling of X. If we consider the restriction WD : D -> 9>(E) of W to D, then Wd is the windowing function E -> & (D) given by WD(x) = W(x)nD, and combining (34,36),
we have Aw = 8sr.
wD
We show now that the composition of a sampling followed by a subsampling amounts to a sampling.
Proposition 31 Let 0 C D0 C Dj c E and let W0
and Wi be two windowing functions. Let W0' be the windowing function given by W0'{p) = W0 (p) n Dj and define the windowing function W by
W{p) =    [J    Wi(q)  .
qeW0a)
Then:
1.    ForXCE,8w(X) = 8Wl(8wi(X)).
2.    For X<ZE,AW{X) = Aw0 (Aw^ (X)).
3.    If Wo covers D\ and W\ covers E, then W covers E.
4. For X C E, So C D0 and Si C Dh: ifWx covers X, S\ is a Wi-sampling ofX, W0 covers Sh and S0 is a Wo-sampling of Si, then W covers X and S0 is a W-sampling ofX.
Proof Note that for X C E,
Sw^X) = U W0'(X) = J (Wo(x)nDi)
xeX
xeX
 U W0(X)   nDi = 5w0(X) nDi xeX
1:     For X C Ewe have
5w{X) = J W{p) = U     U    Wifq) peX                peXqew^ip)
c                                                                                           ~1
UJWiqlqG [J Wb'(p)}
= U{wi(q)Iqg5w0;(x)} = ^i(5w0;(x)) .
2: We have p G Aw0(Awi(X)) iff p G D0 and there is some q G W0(p) such that q G Awi(X); the latter means that q G Dj and Wi(q) nX / 0/. Thus
pGAw0(Awi(X))iff:
pGDo,     3qeW0{p),qeDh    Wi(q)nX^0/.
This means that p e D0 and there is some q G W0'(p) such that Wi (q) n X ^ 0/. This is equivalent to having p G Do with
W{p)C\X
(  U   Witq))nX
96^ (p)
=    U    {Wi(q)nX)^0/,
in other words p G AW(X).
3: As W0 covers Di, that is Dx C 5w0(D0), then Di C 5w0(D0) nDi = 5^(D0). As Wi covers E, 5^ (Di) = E. We conclude that E c SWl (5^ (D))) = MD)), that is W covers E.
4: As Si is a Wi -sampling of X, we have Si C Awi(X) and X C 5^(Si). As S0 is a W0-sampling of Si, we have S0 c Aw0(Si) and SX c ^0(So). We get thus So C Aw0(Awi(X)) = AW(X). As Si CDi, we have Si c 5W0(So)nD1 = 5^(S0), and so X c
^(5^(S0)) = 5w(S0) c 5^(D0). Hence W coversX and S0 is a W-sampling of X. Q.E.D.
We give here a more abstract view of this result. By restricting the domain of W0 to D0 and its range
_
_
_
_
_
104
Image Anal Stereol 2004;23:89-109
to D1, we obtain W0* = W^Dq : D0 ->¦ ^(D1) : p ^ W0(p) HD1; we take also W1* = W1Dl : D1 -> &>(E) (the restriction of W1 to D1) and W* = WDo : D0 -> L*(E). Then we have 5W* = 5W*8WS, 8w<t = 8~tS~t,
5^ = AW, 8$i = AW° and 5~t = AW.
This result explains our assertion after Figure 3, that composing sampling by dilation and quantization by dilation, amounts to discretization by dilation, with the Minkowski sum of the structuring elements used in the two steps.
We will now analyse the relation between W-sampling and Hausdorff metric; since we need to consider closed subsets of D, D itself should be at least closed. So from now on, we assume that D is boundedly compact. We give first the generalization of Theorem 32 of Ronse and Tajine (2000) to the present framework:
Theorem 32 Let F G &(E) and W a windowing function that covers F, and such that r_W < °°. Then for every W-sampling S of F, Hd(F,S) < rW. Furthermore, this bound rW is optimal for nonvoid closed sets: for every r < rW, there is a point q G E and a point p G D such that {p} is a W-sampling of {q}, and Hd({q},{p}) > r; in particular Hd({q},AW({q})) > r.
Proof If F = 0, then 0 is the only W-sampling of F, and Hd(0/,0/) = 0. Assume now that F ± 0/. By definition, we haveSCAW(F) and F c 5W(S). Thus
F C 5W{S) C ~8W(S). Now AW(F) = 8W(F) n D C 8W(F), so S C 8W(F); hence S C 5^{F). Applying item 3_ of Proposition 27 (with F W = S), we get Hd{F,S) <rW.
Let r < rW; from (35), there is some p G D and q G W(p) such that d(p,q) > r; here {p} and {q} are closed, {p} is a W-sampling of {q}, and Hd{{q},{p}) = d{p,q) > r. As {p} C AW({^}), we have Hd({q},AW({q})) > hd(AW({q}),{q} > hd({p},{q}) = d(p,q) > r. Q.E.D.
When F is bounded, S will be bounded, so that it will be compact (because D is boundedly compact); furthermore if D is boundedly finite (as in Ronse and Tajine (2000)), then S will be finite (and S = S).
Note that when D is not boundedly finite, there is a priori no reason for having all W-samplings of F G &'(E) to be closed in D. Often a dense subset of AW(F) will be a_W-sampling. Moreover, for a W-sampling S of F, S will not necessarily be a W-sampling S; this requires AW(F) to be closed:
Lemma 33 Given  F G &(E)   and  a   windowing function W that covers F, the following are equivalent:
1.   AW(F)e^(D).
2.    For every W-sampling SofF,S is a W-sampling ofF.
Proof 1 => 2: Let S be a W-sampling of F. By Definition 30, this means that S C AW(F) and F C
5W(S). As S C S, we have SW(S) c 5W(S), so F c 5W(S); as AW_(F) is closed, we get S c AW(F) = AW(F); hence S is a W-sampling of F.
2 => 1: Applying item 2 with S = AW (F), AW(F) is a W-sampling of F, so by Definition 30 we have AW{F) c aw(F), and AW(F) is closed. Q.E.D.
We have a sufficient condition which guarantees that ?W(F) will be closed:
Proposition 34 Let F e^{E) and take a windowing function W that covers F. Assume thatW(p) G Jf'(E) for every p G D, and that the windowing function W is continuous on D. Then for every F G &(E),AW(F) G &(D), and for every W-sampling S of F, S is a W-sampling ofF.
Proof As we remarked after Definition 30, if we take the restriction WD : D -> &>{E) of W to D, we have AW = 8Wd. By hypothesis, WD is D -»¦ Jf'(E) and continuous. Applying item 2 of Proposition 24,
AW(F) = 5W Dr (F) G J(D). By Lemma 33, for any W-
sampling S of F, S is a W-sampling ofF. Q.E.D.
Note that when D is boundedly finite, every W-sampling is closed, so the above result is unnecessary in this case.
We can now give the counterpart of Proposition 23.
Proposition 35 Let F G ^'(E) such that F is separable. Let W be a windowing function that covers F, with rW < oo, and such that AW(F) is closed. Assume thatW(p) G &'{E) for every peD, and that the windowing function W is continuous on D. Then every W-sampling S of F has a countable subsetT such that T is a W-sampling ofF. The cardinal of T is at most that of the continuum.
105
Ronse C et al: Morphological sampling
Proof For every n > 0, set Wn(x) = 8?/n(W(x)) for any x G E; note that Wn(x) is open and W(x) C Wn(x) for all n > 0 and x G E. As $°/n is a dilation, for
all X G ^(E) we have SWn(X) = 8°/n(5W(X)), and 5W(X) C SW„(X). As S is a W-sampling of F, we have F <zdW(S)<z SWn(S), so the open balls Wn(x) for x G S cover F. As F is separable, there is a countable Sn c S such that F c UxgS„ Wn (x) = 5Wn (Sn). Let T = \Jn>0Sn; thus T is a countable subsej_of S. For every n > 0 we have F C 5Wn(T) C 5W„(T). As AW(F) is closed, T <^S C AW(F). AsT c D and D is boundedly compact, T is a boundedly compact subset of D_Applying Proposition 26 with U = D and V = E, 8W(T) will be closed. As for all n > 0 we have F c ^(T) = ^/n(MT)), by (12) each x G F satisfies d (x, 5W(T)) <J/n, and as 8W(T) is closed, this means that F C 5W(T). Combining this with T C AW(F), T is a W-sampling of F by JDefinition 30. Since T is countable, the cardinal of T is at most that of the continuum. Q.E.D.
As said above, when D is boundedly finite, every subset S of D is countable and closed, so the above result is unnecessary.
As we will see in the next subsection, often one associates with a discretization a “reconstruction”, which associates with every closed subsets of D a subset of E, preferably closed. We give here a bound on the Hausdorff distance between a “discrete” set and its reconstruction:
Proposition 36 Let W be a windowing function with rW < oo and W(p)_L0/Jor all p G D. Then for every S G &(D), Hd(S,5W(S)) < rW. Furthermore, ifW is continuous on D and and W(p) G &'(E) for every peD,thendW(S)e^(E).
Proof Applying item 4 of Proposition 27 with F = S, we get Hd(S,5W(S)) < rW. Assume now the further continuity and closedness conditions on W. As S is a closed subset of the boundedly compact set D, S is boundedly compact. By Proposition 26, 5W(S) G &(E). Q.E.D.
Note that when D is boundedly finite, the metric topology of D is discrete (every point of D is isolated), so the windowing function will always be continuous onD.
Consider the usual case where E = Rn and every W(p) is the translate Ap of a nonvoid structuring element A. Let A = {-a \ a G A}. Note that when
A is closed, A will also be closed, and when A is
compact, A will also be compact. As seen in the
previous subsection, we have SW(X) = X®A and
W (X) = X e A, and the windowing functions W and
W are continuous. Here rW = r^ = ra = supaGA d(o,a), the radius of A. Furthermore, every closed subset of Rn is boundedly compact. Take any nonvoid proper closed subspace D of Rn (D will be boundedly compact). When rA < °o and A is covering (D ® A = E), Theorem 32 applies. Proposition 36 is valid also; finally, we can apply Proposition 34 when A is compact. Note that in general one takes D = Zn or D = Y\ni=l{PiZ), where pi is the resolution or grid spacing along the i-th axis, so that D is boundedly finite, and every subset of D is closed: here Proposition 34 is unnecessary.
MORPHOLOGICAL DISCRETIZATION
Mathematical morphology (Heijmans, 1994; Serra, 1982) introduced discretization by dilation in the particular case where E = Rn, D = nni=i(PiZ) (where pi is the resolution or grid spacing along the i-th axis), and the windowing function is translation-invariant, in other words every window W(p) is the translate Ap of a structuring element A by the point p. Then the windowing function W is continuous. The assumption that the windowing function W is covering (namely, 8W(D) = E) can then be expressed as D® A = E, and it is customarily called the covering assumption. Assuming a tranlation-invariant distance, the radius rW of W coincides with the radius of A, that is rA = supaeAd(o,a), where o is the origin.
In this case, D is boundedly finite, so every subset of D is closed, and E is boundedly compact, so every closed subset of E is boundedly compact.
By Theorem 32, for every closed subset F of E and any W-discretization S of F, Hd(F,S)) < rW. This holds in particular for S = AW(F), the discretization by dilation. The resolution and size of A can be made to tend simultanenously to zero while preserving the covering assumption: we replace D and A by aD and aA respectively (so that aD(BocA = a(D®A) = aE = E), and we make a tend to zero. Assuming further that the distance d is compatible with scaling (that is, d arises from a norm), then raA = arA, so that rW tends to zero with a. Hence AW(F) converges to F for the Hausdorff metric.
However, in the morphological approach, the original closed set F is compared, not to its discretization AW(F), but to a reconstruction R(AW(F)) of it, where R is a mapping &(D) ->¦ &(E). There are two choices for R considered in the literature.
106
Image Anal Stereol 2004;23:89-109
The simplest one is to take for R a dilation. For example in Serra (1982) R is the dilation 8C by the cells C(p) of (2), which are here translates of a compact structuring element. More generally, one can take the dilation by an arbitrary nonvoid compact structuring element B. Indeed, by Proposition 36 we will have Hd(S,S®B) < rB for every S C D. As above, when D is replaced by aD with a —> 0, we replace B by aB, having raB = arB. Now
Hd{F,R{AW(F)))
<Hd(F,AW(F))+Hd(AW(F),R( < arA + arB ,
\W
(F)))
and so R[Aw(F)) converges to F for the Hausdorff metric.
More generally in our abstract framework, given two windowing functions V,W both continuous on D, with W covering, rVrW < °°, and V(p),W(p) G J(f'(E) for every p G E, then for every F G &{E), SV{AW(F)) G &(E) andHd(F,8V{AW(F))) <rW + rV.
The second approach is due to Heijmans (1994), and is based on the algebraic notion of adjunction. The theory of adjunctions is presented extensively in Heijmans (1994), but we recall in Ronse and Tajine (2000) the main facts about it in the case of sets. Since AW is a dilation LP(E) —> L?{D), there is an erosion EW : LP(D) —> LP(E) forming an adjunction with it. For every S C D, EW(S) is the greatest X C E such that AW(X) C S; we have:
EW (S) = {x G E | Mp G D, x G W(p) = E\5W(D\S) .
peS} (37)
The windowing function W being covering, and 5W being a dilation, for every S C D we have 5W (S) U SW(D\S) = 5W{D) = E, so that
EW(S) = E\8W(D\S) <Z SW(S)
(38)
For example with the windows W(p) being the cells C(p) of (2), EW(S) is the interior of SW(S) (this is illustrated in Figure 2.e of Ronse and Tajine (2000)). We show in Figure 4 EW(S) for E = R2, D = Z2, d the Euclidean distance, and each window W(p) being the closed disk of covering radius centered about p.
For E = Rn,Da rectangular grid, and the dilation by a nonvoid compact structuring element in E (that is, W(p) = Ap for A G Jf'(E)), EW(S) will be open. On the other hand, taking an open structuring element, EW(S) will be closed. Therefore Heijmans postulated that the structuring element A used in the discretization by dilation is open. This requirement is inappropriate,
first because it runs counter to popular schemes like the supercover (3) which uses as windows the closed cells of (2), and second because all our results require closed windows. It would be better to use as reconstruction EW(S) with W(p) =Ap for A G JtT'{E).
If we make the reasonable requirement that W(p)f] D = {p} for every p G D (Heijmans makes such an assumption), then it is easily seen that every S C D gives S C EW(S). Combining this with (38) and Proposition 36 (as D = Zn is boundedly finite, W is always continuous on D), we get the following:
o             o             o
W
o             o             o
Fig. 4. Here E = R2, D = Z2, and d is the Euclidean distance. Left: a pixel p (shown as a filled disk) and its neighbours (shown as hollow disks), and the outlines of the cells centered about them (dashed); the window W(p) is the closed disk of covering radius rc = V2/2 centered about p, so W is covering. Right: a set S of pixels (shown as filled disks) and the neighbouring pixels ofD\S (shown as hollow disks); the grey area represents the portion ofSW(D\ S) in the neighbourhoodofS, andEW(S) = E\SW(D\S) is the hatched area, not containing its border.
Property 37 Let W be a covering windowing function such that rW <°° and for each p G D we have W (p) G X\E) andW(p)C\D = {p}. Then:
SCEW(S)cSW(S)e^(E) .
This is for example the case if we choose W(p) = Ap for A G X'(E) such that D ® A = E (covering assumption) and A n D = {o}. It follows then that S c EW(S) c SW(S); now hd(S,EW(S)) = hd(S,5W(S)) = 0, while hd(EW(S),S) < hd{5W(S),S), so Hd(S,EW(S)) < Hd(S,8W(S)). Hence we obtain here, as with the reconstruction by dilation seen above, the result that the Hausdorff distance between F and the reconstruction of its discretization is bounded as a function of the grid resolution, and that this reconstruction converges for the Hausdorff metric to
107
Ronse C et al: Morphological sampling
the original set, when the resolution and size of the structuring elements tend simultaneously to zero.
In the morphological approach to discretization (Heijmans, 1994; Serra, 1982), it is usually shown that R(AW(F) l converges to F for the Fell topology, or equivalents (Heijmans, 1994) under the Hausdorff-Busemann metric (22). As seen at the end of Subsection “Hausdorff metric on compact, closed, and proximinal sets”, the Hausdorff-Busemann metric is smaller than the Hausdorff (generalized) metric, hence convergence under the Hausdorff-Busemann metric is weaker than convergence under the Hausdorff metric.
As one usually takes a regularly spaced sampling grid (like nn=i (PiZ)) and applies a uniform sampling method on closed sets, where with each portion of the closed set one associates some neighbouring grid points, the “closeness” of the original set to its sampling must be measured in the same way at any location in space. This explains why for a regularly spaced sampling grid, the Hausdorff-Busemann metric is insufficient for describing the closeness of a sampled set to its original as a function of the grid resolution, and the convergence when that resolution tends to zero. Here the Hausdorff metric, which is uniform over space, is appropriate. On the other hand, if one takes a sampling grid whose resolution grows coarser as one moves away from the origin (like in the human retina), with covering radius rc = °° (because the spacing between grid points tends to °° when these points tend to oo), then the Fell topology and the Hausdorff-Busemann metric would be quite appropriate.
CONCLUSION
In Ronse and Tajine (2000; 2002) we introduced a metric theory for the sampling (or discretization) of nonvoid closed subsets of a “Euclidean” space E into a boundedly compact “discrete” subspace D. The possible samplings of a nonvoid closed F ? E are all nonvoid closed S ? D minimizing the Hausdorff distance to F. Such samplings were characterized. In Ronse and Tajine (2000) the Hausdorff metric approach was applied to the morphological discretization by dilation (Heijmans, 1994), and to its “cover” variant (what we call here the W-sampling, see Definition 30), but only for compact subsets of E, and with the assumption that D is boundedly finite.
In this paper we have generalized the results from Ronse and Tajine (2000) on morphological sampling, to closed subsets of E, and with the assumption that D is boundedly compact. We have also given some new
properites of Hausdorff and morphological samplings, in a very general framework.
Since the morphological approach to sampling (or discretization) applies to all closed sets, we could compare it with ours, and we showed that we have a better and simpler description of the relation between a Euclidean set and its sampling, in particular we have a stronger form of convergence of the sampling to the original set when the resolution tends to zero.
We have also considered several methods for reconstruction of a set from its sampling, and shown that we have a bound for the Hausdorff distance between a sampled set and its reconstruction.
We have finally argued against the use of the Fell topology (equivalently, the Hausdorff-Busemann metric) for studying the convergence of sampling (or discretization) on a regularly spaced grid.
Apart from the fact that D is boundedly compact, we simply assumed that the covering radius rc is finite (i.e., the distance from a point of E to the nearest point of D is bounded). In the case of compact sets (Ronse and Tajine, 2000), this assumption is not necessary to prove the existence of Hausdorff or morphological sampling and to characterize it, but only to give a bound on the Hausdorff distance between a compact and its sampling, and so to derive the convergence of the sampling to the original compact set when the resolution tends to zero. However for closed sets, this assumption of a finite covering radius is necessary for the existence of Hausdorff sampling, because the Hausdorff distance between two unbounded closed sets can be infinite. We could envisage a variant of our approach which would not require the covering radius to be finite, by using the Hausdorff-Busemann metric instead of the Hausdorff metric. The theory would not be as elegant as the one we have now, because the Hausdorff-Busemann distance cannot be expressed in terms of balls as can the Hausdorff distance. Then the convergence of the sampling to the original set would be in terms of the Hausdorff-Busemann distance (equivalently, the Fell topology) instead of the Hausdorff distance, in other words we would trade an axiom for a weaker convergence. However in practice one usually takes E = Rn and D = ?ni= 1(?iZ) (where ?i is the resolution or grid spacing along the i-th axis), so here for usual norm-based distances, the covering radius is finite, and so such a variant is not justified by applications.
This paper is part of a wider project (Ronse and Tajine, 2000; 2001; Tajine and Ronse, 2002; Ronse and Tajine, 2002) to analyse the sampling or discretization of objects (sets or images), and of operators transforming objects, in terms of the Hausdorff distance. Its role in this project is to explore
108
Image Anal Stereol 2004;23:89-109
some mathematical aspects of this question, and to show that our metric approach is better than the ones of Serra (1982) and Heijmans (1994). Further work should be made to explore the topological properties of Hausdorff and morphological samplings, and to extend our approach to numerical functions (grey-level images) and image processing operators.
REFERENCES
Baddeley AJ (1991). Hausdorff metric for capacities. CWI Report BS-R9127.
Barnsley MF (1993). Fractals Everywhere. Academic Press, 2nd edition.
Borwein JM, Fitzpatrick S (1989). Existence of nearest points in Banach spaces. Canadian J Math 51(4):702– 720.
Busemann H (1955). The Geometry of Geodesics. New York: Academic Press.
Choquet G (1966). Topology, Academic Press.
Cohen-Or D, Kaufman A (1995). Fundamentals of surface voxelization. Graph Model Im Proc 57(6):453–461.
Deutsch F, Lambert J (1980). On continuity of metric projections. J Approx Theory 29:116–131.
Fell JMG (1962). A Hausdorff topology for the closed sets of a locally compact non-Hausdorff space. Proc Am Math Soc 13:472–476.
Hall P, Molchanov IS (1999). Corrections for systematic boundary effects in pixel-based area counts. Patt Recogn 32:1519–1528.
Heijmans HJAM (1991). Morphological discretization. In U. Eckhardt et al., editors, Geometrical Problems in Image Processing. Berlin: Akademie Verlag, pp. 99– 106.
Heijmans HJAM (1992). Discretization of morphological operators. J Vis Commun Image Repr 3(2):182–193.
Heijmans HJAM (1994). Morphological Image Operators. Boston: Academic Press.
Heijmans HJAM, Toet A (1991). Morphological sampling. CVGIP-Imag Understan 54(3):384–400.
Hocking JG, YoungGS (1988). Topology.New York: Dover Publications Inc.
Latecki LJ, Conrad C, Gross A (1998). Preserving topology by a digitization process. J Math Imaging Vis 8:131– 159.
Matheron G (1975). Random Sets and Integral Geometry. New York: J. Wiley & Sons.
Michael E (1951). Topologies on spaces of subsets. Trans Am Math Soc 71:152–182.
Ronse C (1990). Why mathematical morphology needs complete lattices. Signal Process 21(2):129–154.
Ronse C, Tajine M (2000). Discretization in Hausdorff space. J Math Imaging Vis 12(3):219–242.
Ronse C, Tajine M (2001). Hausdorff discretization for cellular distances, and its relation to cover and supercover discretizations. J Vis Commun Image Repr 12(2):169–200.
Ronse C, Tajine M (2002). Hausdorff sampling of closed sets into a boundedly compact space. In Digital and Image Geometry: Advanced Lectures, Proceedings Winterschool Wadern, Germany, Dec. 2000, G. Bertrand, A. Imiya & R. Klette, eds., LNCS 2243, Springer-Verlag, pp. 250–271.
Schmitt M (1998). Digitization and connectivity. In International Symposium on Mathematical Morphology 1998. Mathematical morphology and its applications to image and signal processing IV, H. Heijmans & J. Roerdink, eds., Kluwer Academic Publishers, pp. 67– 74.
Sendov B (1990). Hausdorff Approximations. Kluwer Academic Publishers.
Serra J (1982). Image Analysis and Mathematical Morphology. London: Academic Press.
Serra J (1988). Image Analysis and Mathematical Morphology, Vol. 2: Theoretical Advances. London: Academic Press.
Sivakumar K, Goutsias J (1996). Binary random fields, random closed sets, and morphological sampling. IEEE Trans Image Proc 5(6):899–912.
Sivakumar K, Goutsias J (1997). On the discretization of morphological operators. J Vis Commun Image Repr 8(1):39–49.
Tajine M, Ronse C (2002). Topological properties of Hausdorff discretization, and comparison to other discretization schemes. Theor Comput Sci 283(1):243– 268.
Vervaat W (1988). Narrow and vague convergence of set functions. Stat Probabil Lett 6:295–298.
Vietoris L (1922). Bereiche zweiter Ordnung. Monatsh Math Phys 32:258–280.
109