Bendy Tanios

Francis Bony

Thierry Bosch

Error Analysis due to Laser Beams Misalignment of a Double Laser Self-Mixing Velocimeter

Keywords: Self-mixing, velocimetry, optical feedback interferometry, laser sensors. I

In this paper, we present a self-mixing double-head laser diode velocimeter. Analyzes are performed to evaluate the sensitivity to misalignment for this setup and calculate errors due to this misalignment. The analyses and calculations are verified by experimental results.

INTRODUCTION

Velocity contactless measurements of moving targets like mechanical structures are often used in various industrial applications for nondestructive testing and quality control, like for example, for speed synchronization to stabilize the manufacturing process [START_REF] Engineers | Float Glass Manufacturing Process[END_REF]. Moreover, velocity measurement processes may become crucial if it is one of the parameters governing the safety and performance of a system like in transportation.

Ultrasonic or microwave devices have a relatively poor spatial definition and optical sensors able to achieve this purpose are often too expensive, for example Laser Doppler Velocimetry (LDV) [START_REF] Adrian | Selected Papers on Laser Doppler Velocimetry[END_REF]. Optical feedback interferometry [START_REF] Giuliani | [END_REF], commonly named self-mixing, is an attractive emerging solution enabling us to design low-cost laser sensors with good accuracy.

It has been proven in [START_REF] Tanios | Optimization of the Performances of a Self-mixing Velocimeter by using a Double Laser Diode Configuration[END_REF] that the robustness of a self-mixing velocimeter is increased by using a double laser diode (LD). This approach has proved to be useful when the angle between the target and the laser can not be controlled like for an on-board velocimeter for car safety [START_REF] Raoul | [END_REF]. However, the laser beams of the double LD velocimeter are assumed to be perfectly aligned. The purpose of this paper is to analyze errors due to laser beams misalignment of the double LD self-mixing velocimeter.

II. SELF-MIXING VELOCIMETRY

In optical feedback interferometry, the beam emitted by a laser diode is reflected by an external target in front of the LD back into the laser active cavity and interferes with the inner beam. This interference induces optical output power variations due notably to the Doppler effect [START_REF] Giuliani | [END_REF]- [6]. Then, The target velocity V T is given by equation [START_REF] Engineers | Float Glass Manufacturing Process[END_REF] where λ is the emitted laser wavelength, f D is the Doppler frequency (DF) shift (fundamental frequency of the optical power signal) and γ is the angle between the normal (N) to velocity vector and the optical propagation axis.

(1) However, with a single LD, the angle γ must be known to determine the velocity of a target, limiting drastically the potential applications. It has been shown in [START_REF] Tanios | Optimization of the Performances of a Self-mixing Velocimeter by using a Double Laser Diode Configuration[END_REF] that better tolerance on variation Δγ of angle γ is obtained for superior values of γ but at the usual price of a high bandwidth (high f D ). Therefore, a single LD velocimeter is limited for applications where  may vary widely. We are then proposing a double LD self-mixing velocimeter that permits to increase the potentialities of this sensing method.

III. DOUBLE LASER DIODE VELOCIMETER

The double-head LD prototype is presented in Fig. 1(a) where the two optical propagation axes are set orthogonal to improve the performance of the sensor [START_REF] Tanios | Optimization of the Performances of a Self-mixing Velocimeter by using a Double Laser Diode Configuration[END_REF]. B is the bisector of the angle (90°) between the two laser beams, N is the normal to the velocity vector V T belonging to the plane of the two laser beams, θ is the angle between the optical propagation axes and B (θ=45°), and α is the angle between B and N. Both LDs (named LD1 and LD2) are identical. V T is given by [START_REF] Adrian | Selected Papers on Laser Doppler Velocimetry[END_REF] where f D1 and f D2 are the Doppler frequency shifts of the optical power signals emitted by LD1 and LD2 respectively. Equation ( 2) gives [START_REF] Giuliani | [END_REF] By substituting α given by (3) in [START_REF] Adrian | Selected Papers on Laser Doppler Velocimetry[END_REF] and with θ=45°, we obtain .

(

) 4
where and are the orthogonal projections of V T onto the optical propagation axes (Ax) and (Ay) of LD1 and LD2 respectively (Fig. 1(b)).

By measuring both DFs, the direction and the module of the velocity vector V T are estimated using (3) and ( 4) respectively. Note that the velocity V T measured by the double LD velocimeter is the orthogonal projection of the velocity vector V onto the plane (x,y) containing the two LDs (Fig. 1(b)). Several analyses and experiments have permitted to prove the performance and robustness of the double LD velocimeter in terms of accuracy and insensitivity to angle variations of the target [START_REF] Tanios | Optimization of the Performances of a Self-mixing Velocimeter by using a Double Laser Diode Configuration[END_REF]. However, the laser beams are assumed to be coplanar and illuminating the same point on the target. Though, the laser beams are possibly not perfectly illuminating the same point and even not coplanar. In the next sections, velocity estimation errors of the double-head LD velocimeter due to laser beams misalignment are quantified for flat surface solid target in translational and rotational motion respectively.

A LD2 V x V y V z (b) x y z LD1 + (a) LD1 Target surface LD2 N B α +θ -θ α-θ α+θ A IV.

QUANTIFICATION OF ERRORS DUE TO LASER BEAMS MISALIGNMENT FOR A TARGET IN TRANSLATIONAL MOTION

When a solid target is moving with translational motion, all its points have the same velocity vector V T . Thus, if the two laser beams are illuminating two different points A and B on the target (Fig. 2) then A and B have the same velocity vector V T :

(5)

Therefore, the equations ( 2), ( 3) and ( 4) are still valid. In this case, the measurement is not influenced by the misalignment of the laser beams. And there are no velocity estimation errors due to this misalignment.

V. QUANTIFICATION OF ERRORS DUE TO LASER BEAMS MISALIGNMENT FOR A TARGET IN ROTATIONAL MOTION AROUND A FIXED AXIS

When a solid target is moving with a rotational motion around a fixed axis perpendicular to the target (Fig. 3), the velocity V A of a point A on the target is related to the angular velocity w of the target via V A = r A w where r A is the distance from the axis of rotation to point A, i.e. r A = OA. Thus, in a rigidly rotating target, the velocity increases linearly with (perpendicular) distance from the axis of rotation. The direction of V A is perpendicular to the radius OA.

Therefore, velocity estimation errors may occur when the two laser beams illuminate 2 different points A and B on the rotating target. This is due to the fact that equation ( 2) is not valid anymore. These errors are quantified for two cases. In the first one, the laser beams are considered to be coplanar but illuminating two different points on the target. In the second one, they are not coplanar and the second one has a parallel direction to its original direction, i.e. the optical propagation axis of LD2 is translated in parallel to z-axis (Fig. 7(a)). Note that in these two cases the target is considered in a plane perpendicular to the (x,y) plane (Fig. 7(a)).

A. Coplanar Laser Beams A. Theoretical Analysis

Laser beam emitted by LD1 illuminate a point A on the rotating target. A is situated on the z-axis which belongs to the plane of the target orthogonal to the (x,y) plane. LD2 is translated normally to its optical propagation axis in parallel to x-axis (Fig. 3(a)). The second laser beam illuminates now an alternative point noted B on the target. The 2 points A and B belong to the intersection (AX) of the target plane and the (x,y) plane containing the 2 laser beams (Fig. 3(a)). The velocities at point A and B are respectively:

LD2 LD1 N 1 B 1 α +θ -θ α-θ α+θ N 2 B 2 α A B + and (6)
where r A and r B are the distances from the axis of rotation to point A and B respectively. Note that V A is in the plane of the 2 laser beams contrary to V B which is out of the (x,y) plane. The orthogonal projection V BX of V B onto the (x,y) plane is given by (7

)
where δ is the angle between (OB) and (BX) (Fig. 3(b)). δ is given by ( 8)

Equations ( 6), ( 7) and (8) give .

Therefore, equation ( 2) is valid in this case. Hence there are no velocity estimation errors when the two laser beams are still coplanar and the target is in a perpendicular plane to the laser beams plane.

B. Experimental Results

The experimental set-up is composed of 2 LDs from Hitachi (HL7851G) emitting at a wavelength λ = 785 nm, with a maximum power of 50 mW. They are fixed on 2 orthogonal rails (i.e. θ=45°) corresponding to x-axis and yaxis. The target is a disc rotating at a constant velocity and the angle α is equal to 10°.

Both LDs have 2 degrees of freedom: translation in the direction of the rails and normally to the rails. Translation in the direction of the rails is used to adjust the distance (around 30 cm) between the LDs and the target. Translation normally to the rails is used to misalign the 2 nd laser beam from the original position A on the z-axis to an alternative position B (Fig. 3(a)). This translation maintains the laser beams in the same plane ((x,y) plane). The target has 2 degrees of freedom: 2 orthogonal translations in the plane of the rails used to align in the beginning the z-axis with the laser beams.

The acquisition of the self-mixing signal was performed with a 1 million-point memory scope at 2-MHz sampling frequency. Three acquisitions were taken at each position of B for 0 < AB < 4.5 cm. Target velocity is estimated using the method described in the 3 rd section.

The experimental results are showed in Fig. 4, Fig. 5 and Fig. 6. Figure 4 presents the variation of f D1 and f D2 regarding the initial measurement where both laser beams illuminate the original position A. The variations in f D1 are due to measurements errors. Note that the variations Δf D2 are a little bit higher than Δf D1 due to the sweeping of the rotating disc, i.e. the disc is not perfectly rotating around its fixed axis. However, Δf D2 remains lower than 1.5% of original f D2 . Figure 5 shows the original and estimated velocities function of misalignment distance AB. Estimated velocities vary roughly around the original one. The standard deviations and errors of these estimations are presented in Fig. 6. One can note that Mean Percentage Error (MPE), i.e. relative error in percentage between the estimated velocity and the original one, remains lower than 1%.

It can then be observed from the results showed above that the double-head LD velocimeter remains accurate for coplanar misaligned laser beams illuminating a rotating disc orthogonal to laser beams plane.

B. Non Coplanar Laser Beams A. Theoretical Analysis

Now, LD2 is translated normally to its optical propagation axis in parallel to z-axis (Fig. 7(a)). The 2 points A and B are on the z-axis. In this case, the velocity vectors V A and V B are in the (x,y) plane. We define δr as the difference between the distances from the axis of rotation to point B and A:

(10) And the variation of V B regarding V A is given by .

(11)

δV induces a variation δf D2 in f D2 estimation:

Then the measured f D2 is shifted by δf D2 versus the actual one corresponding to velocity V A . The velocity measured by the double LD velocimeter is in this case:

(13)

The relative error of the measured velocity V T regarding the actual velocity V A is given by ( 14) The velocity vectors V Bi at points B i of the parallel (Δ) to (AX) in B have equal orthogonal projections V BiX onto the (x,y) plane in the same way that it was demonstrated in the previous section:

(15)
Then, if the second laser beam illuminates a point B i , the velocity estimation error is the same than in B. Therefore the velocity estimation error depends only of δr according to z-axis (Fig. 7(b)).

Figure 8 presents the relative error of velocity estimations function of relative misalignment δr/r A of the second laser beam and angle α. δr/r A = -1 corresponds to when the second laser beam illuminates the centre of rotation O, i.e. B is coincident with O, δr/r A = 0 when the 2 laser beams are ideally aligned in A, i.e. B is coincident with A and δr/r A = 1 when r B = 2 r A . For δr/r A around 0, i.e. when the two laser beams are almost aligned, velocity estimations error is low. Then it increases with the absolute value of δr/r A to attend roughly 90% for δr/r A = ±1 and α = 40°.

Axis of rotation

Note that higher errors are obtained for higher values of α. This is due to that velocity estimation is more correlated to f D2 than to f D1 for high values of α and contrary for low values of α.

B. Experimental Results

The same experimental set-up as the previous section is used. But now, the LDs second degree of freedom turn into translation up/down normally to the rails, i.e. in parallel to z-axis. It is used to misalign the 2 nd laser beam from its original position A (r A = OA 1.4 cm) on the z-axis to an alternative position B on the z-axis too (Fig. 7(a)). In this case, the laser beams are not coplanar anymore.

The acquisition of the self-mixing signal was performed with a 1 million-point memory scope at 2-MHz sampling frequency. Three acquisitions were taken at each position of B for -0.5 < AB < 3 cm.

The experimental results are showed in Fig. 9 and Fig. 10. Figure 9 presents the variation of measured and calculated f D1 and f D2 (using equation ( 12)), i.e. f D2 = original f D2 + δf D2 , regarding the initial measurement where both laser beams illuminate the original position A (AB = 0). The variations in f D1 are due to measurement errors. Note that (a) calculated f D1 are equal to original f D1 because, theoretically, f D1 remains equal to its original value and (b) calculated and measured Δf D2 increase linearly with the misalignment distance AB (AB = δr). Figure 10(a) shows the original, estimated and calculated velocities (using equation ( 13)) function of misalignment distance AB. Mean percentage error of estimated velocities and MPE calculated using equation ( 14) are presented in Fig. 10(b). They increase almost linearly with AB. The results presented in Fig. 9 and Fig. 10 show the accordance of the measurements with calculations. It can then be observed from the results showed above that the double-head LD velocimeter is not accurate for non coplanar laser beams illuminating a rotating disc orthogonal to laser beams plane. Errors due to this misalignment have been theoretically calculated and approved with experimental measurements. They depend of the misalignment distance and the angle α.

VI. CONCLUSION

In this paper, a robust double-head LD self-mixing sensor was presented. Errors due to laser beams misalignment were analyzed for flat surface solid target in translational and rotational motion respectively. For a target in translational motion, analyzes demonstrated that the double LD velocimeter is insensitive to laser beams misalignment. Moreover, the velocimeter is insensitive to coplanar laser beams misalignment for a rotating target orthogonal to laser beams plane. However, when the laser beams are not coplanar, measurements errors result from this misalignment. These errors have been quantified.

Experimental results validated the theoretical analyses and calculations. Additional analysis and experiments may be performed to quantify the errors due to laser beams misalignment for alternative orientations and motions of the target.

FIGURE 1 .

 1 FIGURE 1. (a) Double-head laser diode velocimeter prototype with θ = 45°, (b) Representation of double-head laser diode velocimeter in an orthonormal basis (A, , , ).

FIGURE 2 .

 2 FIGURE 2. Laser beams emitted by LD1 and LD2 illuminate 2 different points A and B on the target.

FIGURE 3 .

 3 FIGURE 3. Coplanar laser beams illuminating two points A and B on a rotating target whose plane is perpendicular to the (x,y) plane of the 2 laser beams. (a) view in 3D and (b) view 2D in the plane of the target.

FIGURE 4 .

 4 FIGURE 4. Variation of Doppler frequency measurements when the laser beams are coplanar but not illuminating the same point on the target.

FIGURE 5 .

 5 FIGURE 5. Variation of velocity measurements when the laser beams are coplanar but not illuminating the same point on the target.

FIGURE 6 .

 6 FIGURE 6. (a) Standard deviations, (b) mean squared error and (c) mean percentage error of velocity estimations for coplanar laser beams not illuminating the same point on the target.

FIGURE 7 .

 7 FIGURE 7. Non coplanar laser beams illuminating two points A and B on a rotating target whose plane is perpendicular to the (x,y) plane of the 2 laser beams. (a) view in 3D and (b) view 2D in the plane of the target.

FIGURE 8 .

 8 FIGURE 8. Relative error in percentage between the measured velocity and the actual velocity.(a) for -1 < δr/r A < 0 and (b) for 0 < δr/r A < 1.

FIGURE 9 .

 9 FIGURE 9. Variation of Doppler frequency measurements when the laser beams are not coplanar.

FIGURE 10 .

 10 FIGURE 10. (a) Original, calculated and estimated velocities and (b) mean percentage error of velocity estimations for non coplanar laser beams.


Jean Cousty
email: j.cousty@esiee.fr

Laurent Najman
email: l.najman@esiee.fr

Fabio Dias
email: f.dias@esiee.fr

Jean Serra
email: j.serra@esiee.fr

Morphological filtering on graphs

Keywords: Graphs, mathematical morphology, adjunctions, spatially variant morphology

We study some basic morphological operators acting on the lattice of all subgraphs of an arbitrary (unweighted) graph G. To this end, we consider two dual adjunctions between the edge set and the vertex set of G. This allows us (i) to recover the classical notion of a dilation/erosion of a subset of the vertices of G and (ii) to extend it to subgraphs of G. Afterward, we propose several new openings, closings, granulometries and alternate filters acting (i) on the subsets of the edge and vertex set of G and (ii) on the subgraphs of G. The proposed framework is then extended to functions that weight the vertices and edges of a graph. We illustrate with applications to binary and grayscale image denoising, for which, on the provided images, the proposed approach outperforms the usual one based on structuring elements.

Introduction

From a formal point of view, digital image processing historically consists of analyzing the transformations that act on the subsets of Z 2 (the sets of pixels in a binary image) and the transformations that act on the maps from Z 2 to N (the images themselves). In such a perspective, mathematical morphology provides a set of filtering and segmenting tools that are very useful in applications.

On the other hand, there is a growing interest for considering digital objects not only composed of points but also composed of elements lying between them and carrying structural information about how the points are glued together (see [START_REF] Cousty | Watershed cuts: Minimum spanning forests and the drop of water principle[END_REF][START_REF] Couprie | New characterizations of simple points in 2D, 3D, and 4D discrete spaces[END_REF][START_REF] Loménie | Morphological mesh filtering and α-objects[END_REF]31,[START_REF] Dias | Some morphological operators on simplicial complex spaces[END_REF]2] for recent examples). The simplest of these representations are the graphs. The domain of an image is considered as a graph (which can be planar or not) whose vertex set is made of the pixels and whose edge set is given by an adjacency relation on these pixels. Note that this adjacency relation can be either spatially invariant or spatially variant leading to operators that are either spatially invariant or spatially variant (see e.g. [START_REF] Lerallut | Image filtering using morphological amoebas[END_REF][START_REF] Tankyevych | Spatially-variant morpho-hessian filter: Efficient implementation and application[END_REF][START_REF] Verd-Monedero | Spatially-variant anisotropic morphological filters driven by gradient fields[END_REF][START_REF] Stawiaski | Minimum spanning tree adaptive image filtering[END_REF] for examples of spatially variant morphological operators). In this context, it becomes relevant to consider the transformations acting on the set of all subgraphs and not only those acting on the set of all subsets of pixels.

When dealing with a graph G, we often need (see e.g. ([6, 7, 8, 22]) to consider the graph induced by a subset X • of vertices of G. To this end, we associate with X • the largest subset of edges of G such that the obtained pair is a graph (see e.g. Fig. 1 where the red and blue graph X of Fig. 1b is induced by the set X • of red and blue vertices depicted in Fig. 1a). In other cases, we have to consider a graph induced by a subset of the edges of G.

Motivated by classifying and understanding these operations and their combinations, we propose a systematic study of the basic operators which are used to derive a set of edges from a set of vertices and a set of vertices from a set of edges. Before studying these operators, we start by presenting in Section 2 a lattice structure for the set of all subgraphs of G. In fact, it turns out that the mentioned basic graph operators are dilations and erosions in this lattice. They allow us (i) to recover the usual notion of a (a) X • (b) X (red and blue vertices) (red and blue subgraph)

(c) dilation δ(X • ) of X • (d) dilation [δ, ∆] (X)
of X (red and blue vertices) (red and blue subgraph) dilation/erosion of a subset of vertices (see e.g. [START_REF] Vincent | Graphs and mathematical morphology[END_REF][START_REF] Heijmans | Graph morphology in image analysis[END_REF]) and (ii) to extend it to subgraphs (Section 3). Then, we propose in Section 4 several new openings, closings, granulometries and alternate sequential filters acting (i) on the subsets of edges and on the subsets of vertices and (ii) on the subgraphs. In Section 5, the proposed framework and operators are extended to functions that weights the vertices and edges of a graph. Afterward, Section 6 presents several illustrations where the proposed framework is applied for image processing. In Sections 6.1 and 6.2, quantitative and qualitative comparisons with usual morphological filters by structuring elements (see e.g. [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]), with connected filters (see e.g. [START_REF] Salembier | Flat zones filtering, connected operators, and filters by reconstruction[END_REF][START_REF] Ronse | Set-theoretical algebraic approaches to connectivity in continuous or digital spaces[END_REF][START_REF] Braga-Neto | Connectivity on complete lattices: new results[END_REF]23]), and with median filters illustrate the interest of the proposed filters for denoising impulse noise on binary 2D and 3D images. In Section 6.3 an illustration of the proposed framework to the denoising of a grayscale image is presented. As a first example, filters on a spatially invariant graph are considered. Finally, the results are improved by replacing the spatially invariant graph by a spatially variant one. Hence, this final example illustrate that the proposed framework includes spatially variant morphological filters, encompassing in particular spatially variant morphological filters based on discrete spatially variant (symmetric) structuring element. We emphasize that, contrarily to most of the previous work on morphology in graphs (such as [START_REF] Vincent | Graphs and mathematical morphology[END_REF][START_REF] Heijmans | Graph morphology in image analysis[END_REF][START_REF] Meyer | Micro-viscous morphological operators[END_REF][START_REF] Meyer | Morphological operators for flooding, leveling and filtering images using graphs[END_REF]31,[START_REF] Loménie | Morphological mesh filtering and α-objects[END_REF]2]), the input and output of the main operators of this paper are both graphs. This property can impact the results of further processing where connectivity and adjacency are involved [START_REF] Salembier | Flat zones filtering, connected operators, and filters by reconstruction[END_REF][START_REF] Ronse | Set-theoretical algebraic approaches to connectivity in continuous or digital spaces[END_REF][START_REF] Braga-Neto | Connectivity on complete lattices: new results[END_REF]23]. For instance, using the definitions of [START_REF] Vincent | Graphs and mathematical morphology[END_REF], dilating the subset X • of red and blue vertices of Fig. 1a leads to the set of red and blue vertices of Fig. 1c which is connected. On the other hand, using the definitions proposed in this paper, dilating the subgraph X induced by X • (depicted in red and blue in Fig. 1b) leads to the red and blue subgraph shown in Fig. 1d which is not connected. However, in the last example the two connected components (i.e. the red and the blue subgraphs of Fig. 1d) are adjacent to each other. Intuitively, one may say that, on this example, the operator acting on subgraphs enriches the one acting on subsets of vertices by allowing to make the distinction between adjacency and connectedness. The evaluation of the practical impact of such distinction is beyond the scope of this paper. Indeed, the various operators created by mathematical morphology stem from the two sources of an adjunction and of a connection. The first one leads to openings and closings by adjunction, and then, to morphological filters. The second source introduces connected components, regional minima, homotopic thinning and thickening, topological watershed, etc. . . The two sources are not incompatible, and one can combine their axioms (e.g. a connected opening). In practice the first line expresses mainly filtering, whereas the second one focuses on segmentation. The present paper is exclusively devoted to the building up of an adjunction on graph operators, and to its consequences in terms of filtering. Therefore, the heart of the matter in this paper is provided by Section 3, and in particular by Definitions 4, 7, 10, 13, and Theorem 15. Sections 4 and 5 draw, for the case of graphs, the usual consequences of an adjunction.

This paper2 extends a paper [START_REF] Cousty | Some morphological operators in graph spaces[END_REF] published in a conference. In particular, it contains the proof of all properties presented in [START_REF] Dias | Some morphological operators on simplicial complex spaces[END_REF]. For the convenience of the mathematically oriented reader, these proofs are given below the statement of the properties.

Lattice of graphs

We define a (undirected) graph as a pair X = (X • , X × ) where X • is a set and

X × is composed of unordered pairs of distinct elements in X • , i.e., X × is a subset of {{x, y} ⊆ X • | x = y}. Each element of X • is called a vertex or a point (of X)
, and each element of X × is called an edge (of X). In the sequel, to simplify the notations, e x,y stands for the edge {x, y} ∈ X × .

Let X and Y be two graphs. If Y • ⊆ X • and Y × ⊆ X × , then X and Y are ordered and we write Y ⊑ X. If Y ⊑ X, we say that Y is a subgraph of X, or that Y is smaller than X and that X is greater than Y .

Important remark. Hereafter, the workspace is a graph G = (G • , G × ) and we consider the sets G • , G × and G of respectively all subsets of G • , all subsets of G × and all subgraphs of G. Property 1. The set G of the subgraphs of G is a complete lattice. The supremum and the infimum of any family F = {X 1 , . . . X ℓ } of elements in G are given by respectively ⊔F = ( i∈ [1,ℓ]

X i • , i∈[1,ℓ] X i × ) and ⊓F = ( i∈[1,ℓ] X i • , i∈[1,ℓ] X i × ). Proof. Let F = {X 1 , . . . X ℓ } and let X = ( i∈[1,ℓ] X i • , i∈[1,ℓ] X i × ). For any i ∈ {1, . . . , ℓ}, we have X i ⊑ X since, by definition of X, X i • ⊆ X • and X i × ⊆ X × .
Let Y be any graph in G that is greater than any element of F . Thus, for any i ∈ {1, . . . , ℓ}, we have

X i • ⊆ Y • and X i × ⊆ Y × . Therefore, we have i∈[1,ℓ] X i • ⊆ Y • and i∈[1,ℓ] X i × ⊆ Y × . Hence, we deduce that X ⊑ Y , which completes the proof that X = ( i∈[1,ℓ] X i • , i∈[1,ℓ] X i × ) is the supremum of F . The proof that X ′ = ( i∈[1,ℓ] X i • , i∈[1,ℓ] X i × )
is the infimum of F is similar, and as such, it is left to the reader.

Let S 0 , S 1 ⊆ G be the sets of respectively the graphs made of a single vertex and the graphs made of a pair of vertices linked by an edge, i.e.,

S 0 = {({x}, ∅) | x ∈ G • } and S 1 = {({x, y}, {e x,y }) | e x,y ∈ G × }. We set S = S 0 ∪S 1 .
It can be seen that any graph X ∈ G is exactly the supremum of the family F = {X 1 , . . . , X ℓ } of all elements in S that are smaller than X: X

= ( i∈[1,ℓ] X i • , i∈[1,ℓ] X i × )
. Therefore, the following property can be deduced.

Property 2. The lattice G is sup-generated by the set

S = S 0 ∪ S 1 . If X • ⊆ G • (resp. Y × ⊆ G × ), we denote by X • (resp. Y × ) the complementary set of X • (resp. Y × ) in G • (resp. G × ), that is X • = G • \ X • (resp. Y × = G × \ Y × ).
Remark 3. Observe that, if X is a subgraph of G, then, except in some degenerated cases, the pair (X • , X × ) is not a graph. Furthermore, if G × is nonempty, then the lattice G is not complemented.

Dilations and erosions

In the graph G, we can consider sets of points as well as sets of edges. Therefore, it is convenient to consider operators to go from one kind of sets to the other one. In this section, we investigate such operators and we study their morphological properties. Then, based on these operators, we propose several dilations and erosions acting on the lattice of all subgraphs of G.

Let X • be a subset of G • , we denote by G X • the set of all subgraphs of G whose vertex set is X • . Let Y × be a subset of G × . We denote by G Y × the set of all subgraphs of G whose edge set is Y × . Definition 4 (edge-vertex correspondences). We define the operators δ

• , ǫ • from G × into G • and the operators ǫ × , δ × from G • into G × as follows: G × → G • G • → G × Provide the object with a graph structure X × → δ • (X × ) such that (δ • (X × ), X × ) = ⊓G X × X • → ǫ × (X • ) such that (X • , ǫ × (X • )) = ⊔G X • Provide its complement with a graph structure X × → ǫ • (X × ) such that (ǫ • (X × ), X × ) = ⊓G X × X • → δ × (X • ) such that (X • , δ × (X • )) = ⊔G X • In other words, if X • ⊆ G • and Y × ⊆ G × , (δ • (Y × ), Y × ) is the smallest subgraph of G whose edge set is Y × , (X • , ǫ × (X • )) is the largest subgraph of G whose vertex set is X • , (ǫ • (Y × ), Y × ) is the smallest subgraph of G whose edge set is Y × , and (X • , δ × (X • )) is the largest subgraph of G whose vertex set is X • .
These operators are illustrated in Figs. 2a-f. The choice of X (Fig. 2b) is made to depict a representative sample of the different configurations that can be found in subgraphs of G (Fig. 2a). Applications to image filtering are illustrated in Section 6 where different ways to derive graphs from images are discussed.

Morphological operators on functions that weight the edges or vertices of a graph have been first studied by Meyer, Angulo and Lerallut [START_REF] Meyer | Micro-viscous morphological operators[END_REF][START_REF] Meyer | Morphological operators for flooding, leveling and filtering images using graphs[END_REF]. The following Property 5 clarifies the links between their operators and those of Definition 13. In particular, the characterization of the graph operators given in Property 27, which extends the one given in Property 5 to functions that weight the edges or vertices of a graph, is taken as a definition in [START_REF] Meyer | Micro-viscous morphological operators[END_REF][START_REF] Meyer | Morphological operators for flooding, leveling and filtering images using graphs[END_REF]. Note, moreover, that all properties of our paper are original (except Property 6, which appears in [START_REF] Meyer | Micro-viscous morphological operators[END_REF][START_REF] Meyer | Morphological operators for flooding, leveling and filtering images using graphs[END_REF], for the case of functions that weight the edges or vertices of a graph). In particular the important Theorem 15 about structure does not appear in [START_REF] Meyer | Micro-viscous morphological operators[END_REF] or [START_REF] Meyer | Morphological operators for flooding, leveling and filtering images using graphs[END_REF], neither do Theorem 22 nor Corollary 26.

Property 5. For any

X × ⊆ G × and Y • ⊆ G • : 1. δ • : G × → G • is such that δ • (X × ) = {x ∈ G • | ∃e x,y ∈ X × }; 2. ǫ × : G • → G × is such that ǫ × (Y • ) = {e x,y ∈ G × | x ∈ Y • and y ∈ Y • }; 3. ǫ • : G × → G • is such that ǫ • (X × ) = {x ∈ G • | ∀e x,y ∈ G × , e x,y ∈ X × }; 4. δ × : G • → G × is such that δ × (Y • ) = {e x,y ∈ G × | x ∈ Y • or y ∈ Y • }. Proof.
1. To establish Property 5.1, we will prove that the two following relations hold true:

δ • (X × ) ⊆ {x ∈ G • | ∃e x,y ∈ X × } (1) {x ∈ G • | ∃e x,y ∈ X × } ⊆ δ • (X × ) (2)
In order to establish relation (1), let us prove that any vertex z in δ

• (X × ) belongs to {x ∈ G • | ∃e x,y ∈ X × }. Since z ∈ δ • (X × ), we have z ∈ [⊓G X × ]
• by definition of δ • and, by Property 1, we a: have

G b: X = (X • , X × ) c: δ • (X × ) d: ǫ × (X • ) e: ǫ • (X × ) f: δ × (X • ) g: [δ, ∆] (X) h: [ǫ, E ] (X) i: α3(X) j: β3(X)
z ∈ ∩{Z • | Z ∈ G X × }.
It can be seen that (∪X × , X × ) is a subgraph of any graph in G X × . Hence, as z ∈ ∩{Z • | Z ∈ G X × }, we deduce that z ∈ ∪X × . Thus, there exists an edge e z,z ′ in X × , which proves that z ∈ {x ∈ G • | ∃e x,y ∈ X × }.

In order to establish relation (2), let us prove that any vertex w in {x ∈ G • | ∃e x,y ∈ X × } belongs to δ • (X × ). Since w ∈ {x ∈ G • | ∃e x,y ∈ X × }, there exists an edge e w,w ′ ∈ X × . By definition of G X × and by Property 1, the edge e w,w ′ is an edge of ⊓G X × . Therefore, since ⊓G X × is a graph, w is a vertex of ⊓G X × . Hence, the fact that w ∈ δ • (X × ) follows directly from the definition of δ • . 2. To establish Property 5.2, we will prove that the two following relations hold true

ǫ × (Y • ) ⊆ {e x,y ∈ G × | x ∈ Y • and y ∈ Y • } (3) {e x,y ∈ G × | x ∈ Y • and y ∈ Y • } ⊆ ǫ × (Y • ) (4)
In order to establish relation 3, let us prove that any edge e z,z

′ in ǫ × (Y • ) belongs to {e x,y ∈ G × | x ∈ Y • and y ∈ Y • }. Since e z,z ′ ∈ ǫ × (Y • ), by definition of ǫ × , we have e z,z ′ ∈ [⊔G Y • ] × . Hence, by Property 1, we have e z,z ′ ∈ ∪{Z × | Z ∈ G Y • }. Thus, there exists a graph Z ∈ G Y • such that e z,z ′ ∈ Z × . Since Z is a graph, w and w ′ are both in Z • . As Z ∈ G Y • , Z • = Y • . Therefore, the vertices w and w ′ are both in Y • . Thus, e w,w ′ belongs to {e x,y ∈ G × | x ∈ Y • and y ∈ Y • }.
In order to establish relation 4, let us prove that any edge e z,z

′ in {e x,y ∈ G × | x ∈ Y • and y ∈ Y • } belongs to ǫ × (Y • ). Since e z,z ′ ∈ {e x,y ∈ G × | x ∈ Y • and y ∈ Y • }, we have z ∈ Y • and z ′ ∈ Y • . Hence, the pair (Y • , {e z,z ′ }) is a graph in G Y • . Thus, by Property 1, we have e z,z ′ ∈ [⊔G Y • ] × which implies e z,z ′ ∈ ǫ × (Y • )
, by definition of ǫ × . 3. Property 5.3 will be deduced by duality from Property 5.1. By Definition 4, we have ǫ

• (X × ) = [⊓G X × ]
• . Thus, again by Definition 4, we have ǫ • (X × ) = δ • (X × ). Therefore, by Property 5.1, we have the equality ǫ

• (X × ) = {x ∈ G • | ∃e x,y ∈ X × } which is equivalent to the equality ǫ • (X × ) = {x ∈ G • | ∀e x,y ∈ G × , e x,y ∈ X × }.
(Y • ) = {e x,y ∈ G × | x ∈ Y • and y ∈ Y • } which is equivalent to ǫ • (X × ) = {e x,y ∈ G × | x ∈ Y • or y ∈ Y • }.
In other words, Property 5 states that δ • (X × ) is the set of all vertices which belong to an edge of X × , ǫ × (Y • ) is the set of all edges whose two extremities are in Y • , ǫ • (X × ) is the set of all vertices which do not belong to any edge of X × , and δ × (Y • ) is the set of all edges which have at least one extremity in Y • . Thus, the previous property locally characterizes the operators of Definition 4. This property leads in particular to simple linear-time algorithms (with respect to the cardinality of

G • and G × ) to compute δ • (X × ), ǫ × (Y • ), ǫ • (X × ) and ǫ • (X × ) without explicitly considering the families G X × , G X • , G X × and G X • .
Before further analyzing the operators defined above, let us briefly recall some algebraic tools which are fundamental in mathematical morphology [START_REF] Ronse | Algebraic foundations of morphology[END_REF][START_REF] Heijmans | Morphological image operators[END_REF].

Given two lattices L 1 and L 2 , an operator δ :

L 1 → L 2 is called a dilation when it preserves the supremum (i.e. ∀E ⊆ L 1 , δ(∨ 1 E) = ∨ 2 {δ(X) | X ∈ E}, where ∨ 1 is the supremum in L 1 and ∨ 2 the supremum in L 2 ).
Similarly, an operator which preserves the infimum is called an erosion.

Two operators ǫ :

L 1 → L 2 and δ : L 2 → L 1 form an adjunction (ǫ, δ) when for any X in L 2 and any Y in L 1 , we have δ(X) ≤ 1 Y ⇔ X ≤ 2 ǫ(Y )
, where ≤ 1 and ≤ 2 denote the order relations on respectively L 1 and L 2 . Given two operators ǫ and δ, if the pair (ǫ, δ) is an adjunction, then ǫ is an erosion and δ is a dilation (see, e.g., [15] or [START_REF] Ronse | Algebraic foundations of morphology[END_REF][START_REF] Heijmans | Morphological image operators[END_REF]). If L 1 , L 2 , and L 3 are three lattices and if δ :

L 1 → L 2 , δ ′ : L 2 → L 3 , ǫ : L 2 → L 1 ,
and ǫ ′ : L 3 → L 2 are four operators such that (ǫ, δ) and (ǫ ′ , δ ′ ) are adjunctions, then the pair (ǫ • ǫ ′ , δ ′ • δ) is also an adjunction (see [START_REF] Ronse | Algebraic foundations of morphology[END_REF][START_REF] Heijmans | Morphological image operators[END_REF]).

Given two complemented lattices L 1 and L 2 , two operators α and β from L 1 into L 2 are dual (with respect to the complement) of each other when, for any X ∈ L 1 , we have β(X) = α(X). If α and β are dual of each other, then β is an erosion whenever α is a dilation. Proof.

1. Let X • ∈ G • (resp. Y × ∈ G × ). We have ǫ × (X • ) = [⊔G X • ] × , by definition of ǫ × , (resp. ǫ • (Y × ) = [⊓G Y × ] • , by definition of ǫ • ). Thus ǫ × (X • ) = [⊔G X • ] × . Hence, we deduce that ǫ × (X • ) = δ × (X • ) by definition of δ × (resp. ǫ • (Y × ) = δ • (Y × ), by definition of δ • ). 2.
To establish Property 6.2, we proceed in three steps.

(i) We show that ∀X × ∈ G × and ∀Y • ∈ G • , δ • (X × ) ⊆ Y • =⇒ X × ⊆ ǫ × (Y • ); (ii) we prove that ∀X × ∈ G × and ∀Y • ∈ G • , X × ⊆ ǫ × (Y • ) =⇒ δ • (X × ) ⊆ Y • , which completes the proof that (ǫ × , δ • ) is an adjunction; (iii) we deduce that (ǫ • , δ × ) is an adjunction by duality from (ii). (i) Let X × ∈ G × and Y • ∈ G • . Assume that that δ • (X × ) ⊆ Y • . We have to prove that X × ⊆ ǫ × (Y • ). Let e x,y ∈ X × . By Property 5.1, we have x ∈ δ • (X × ) and x ∈ δ • (X × ). As δ • (X × ) ⊆ Y • , we also have x ∈ Y • and y ∈ Y • .
Therefore, by Property 5.2, we may affirm that e x,y belongs to ǫ × (Y • ). Hence,

X × ⊆ ǫ × (Y • ). (ii) Let X × ∈ G × and Y • ∈ G • . Assume that that X × ⊆ ǫ × (Y • ). We have to prove that δ • (X × ) ⊆ Y • . Let x ∈ δ • (X × )
. By Property 5.1, there exists an edge e x,y in X × . As

X × ⊆ ǫ × (Y • ),
we have e x,y ∈ ǫ × (Y • ). Then, by Property 5.2, we may affirm that x belongs to

Y • . Hence, δ • (X × ) ⊆ Y • . (iii) Let X × ∈ G × and Y • ∈ G • . The six following statements are equivalent. δ × (Y • ) ⊆ X × ǫ × (Y • ) ⊆ X ×
, by duality of δ × and ǫ × (Property 6.1)

ǫ × (Y • ) ⊇ X × Y • ⊇ δ • (X × ) , since (ǫ × , δ •
) is an adjunction (Properties (i) and (ii))

Y • ⊆ δ • (X × ) Y • ⊆ ǫ • (X × )
, by duality of δ • and ǫ • (Property 6.1).

Thus, (ǫ • , δ × ) is an adjunction.

3-4. Items 3 and 4 follow from item 2 by the dilation / erosion property of adjunctions.

Let us compose these dilations and erosions to act on G • and G × .

Definition 7 (vertex-dilation, vertex-erosion). We define δ and ǫ that act on G

• (i.e., G • → G • ) by δ = δ • • δ × and ǫ = ǫ • • ǫ × .
For instance, if we consider the graph G represented in Fig. 2a and the subset X • of G • depicted in black in Fig. 2b, then δ(X • ) and ǫ(X • ) are the sets of points represented in black in Fig. 2g and2h respectively. Remark 8. As compositions of respectively dilations and erosions, δ and ǫ are respectively a dilation and an erosion. Moreover, by composition of adjunctions and dual operators, δ and ǫ are dual and (ǫ, δ) is an adjunction. Property 9. For any X • ⊆ G • , the two following statements hold true.

1. δ(X • ) = {x ∈ G • | ∃e x,y ∈ X × , e x,y ∩ X • = ∅}; 2. ǫ(X • ) = {x ∈ G • | ∀e x,y ∈ G × , {x, y} ⊆ X • }.
Proof.

1. The following statements are equivalent.

δ(X • ) = δ • (δ × (X • ))
, by Definition 7

δ(X • ) = δ • ({e x,y ∈ G × | either x ∈ X • or y ∈ X • }) , by Property 5.4 δ(X • ) = {x ∈ G • | ∃e x,y ∈ X × , e x,y ∩ X • = ∅} , by Property 5.1 2.
The following statements are equivalent.

ǫ(X • ) = ǫ • (ǫ × (X • )) , by Definition 7 ǫ(X • ) = ǫ • ({e x,y ∈ G × | x ∈ X • and y ∈ X • }) , by Property 5.2 ǫ(X • ) = {x ∈ G • | ∀e x,y ∈ G × , x ∈ X • and y ∈ X • } , by Property 5.3
In other words, the set δ(X • ) comprises the non-isolated vertices of X • (i.e., the vertices of X • contained in at least one edge of G) and all vertices adjacent to a vertex in X • , while the set ǫ(X • ) comprises all vertices of X • whose neighborhood is included in X • . Hence, from these characterizations, it can be shown that δ and ǫ correspond exactly to the usual notions of an erosion and of a dilation of a set of vertices in a graph [START_REF] Vincent | Graphs and mathematical morphology[END_REF]. It means, in particular that, when G • is a subset of the grid points Z d and when the edge set G × is obtained from a symmetrical structuring element, then the operators defined above are equivalent to the usual binary dilation and erosion by the considered structuring element. For instance, in Fig. 2,G • is a rectangular subset of Z 2 and G × corresponds to the basic "cross" structuring element. It can be verified that the vertex sets in Fig. 2g andh, obtained by applying δ and ǫ to X • (Fig. 2b), are the dilation and the erosion by a "cross" structuring element of X • .

Let us now compose the operators of Definition 4, to obtain operators acting on the subsets of the edge set of G.

Definition 10 (edge-dilation, edge-erosion). We define ∆ and E that act on

G × by ∆ = δ × • δ • and E = ǫ × • ǫ • .
For instance, if we consider the graph G represented in Fig. 2a and the subset X × of G × depicted in black in Fig. 2b, then ∆(X × ) and E(X × ) are the sets of edges represented in black in Fig. 2g and 2h respectively.

Remark 11. As compositions of respectively dilations and erosions, ∆ and E are respectively a dilation and an erosion. Moreover, by composition of adjunctions and dual operators, δ and ǫ are dual and (ǫ, δ) is an adjunction.

Property 12. For any X × ⊆ G × , the two following statements hold true.

1. ∆(X × ) = {e x,y ∈ G × | either ∃e x,z ∈ X × or ∃e y,w ∈ X × }; 2. E(X × ) = {e x,y ∈ G × | ∀e x,z , e y,w ∈ G × , e x,z ∈ X × , e y,w ∈ X × }.
Proof.

1. The following statements are equivalent.

∆(X × ) = δ × (δ • (X × ))
, by Definition 10

∆(X × ) = δ × ({x ∈ G • | ∃e x,y ∈ X × }) , by Property 5.1 ∆(X × ) = {e x,y ∈ G × | either ∃e x,z ∈ X × or ∃e y,w ∈ X × }
, by Property 5.4

2. The following statements are equivalent.

E(X × ) = ǫ × (ǫ • (X × ))
, by Definition 10

E(X × ) = ǫ × ({x ∈ G • | ∀e x,y ∈ G × , e x,y ∈ X × })
, by Property 5.3

E(X × ) = {e x,y ∈ G × | ∀e x,z , e y,w ∈ G × , e x,z ∈ X × , e y,w ∈ X × } , by Property 5.2
In other words, the set ∆(X × ) comprises the edges in X × and the edges of G that are adjacent to an edge in X × (i.e., the edges of G that share at least one vertex with an edge in X × ), while the set E(X × ) contains each edge e in X × whose neighborhood (i.e. the set of all edges adjacent to e) is included in X × . Based on the vertex-dilation and edge-dilation (and their adjunct erosions) of Definitions 7 and 10, we now define the dilation acting on subgraphs (and its adjunct erosions) that was informally presented in the introduction of the paper through in particular Fig. 1.

Definition 13. We define the operators [δ, ∆] and [ǫ, E] by respectively

[δ, ∆] (X) = (δ(X • ), ∆(X × )) and [ǫ, E] (X) = (ǫ(X • ), E(X × )), for any X ∈ G.
For instance, Figs. 2g and 2h present the results obtained by applying the operator [δ, ∆] and the operator [ǫ, E] to the subgraph X (Fig. 2b) of G (Fig. 2a). Proof. Let X be any graph in G.

We first establish that [δ, ∆] (X) is a graph in G. To this end, it is sufficient to prove that, for any edge e x,y ∈ ∆(X × ), we have x ∈ δ(X • ) and y ∈ δ(X • ). Let e x,y be any edge in ∆(X × ). By Property 12.1, there exists either an edge e x,z ∈ X × or an edge e y,w ∈ X × . If there exists e x,z ∈ X × , then, since X is a graph, x ∈ X • and if there exists e y,w ∈ X × , then, since X is a graph, y ∈ X • . Thus, in any of these two cases, we have e x,y ∩ X • = ∅, which by Property 9.1 implies that both x ∈ δ(X • ) and y ∈ δ(X • ).

Let us now establish that [ǫ, E] (X) is a graph in G. To this end, it is sufficient to prove that, for any edge e x,y ∈ E(X × ), we have x ∈ ǫ(X • ) and y ∈ ǫ(X • ). Let e x,y be any edge in E(X × ). By Property 12.2, for any e x,z and any e y,w in G × , we have e x,z ∈ X × and e y,w ∈ X × . Thus, as X is a graph, for any e x,z and any e y,w in G × , we have x ∈ X • , z ∈ X • , y ∈ X • , and w ∈ X • . Hence, by Property 9.2, we deduce that both x ∈ ǫ(X • ) and y ∈ ǫ(X • ).

Theorem 15 (graph-dilation, graph-erosion). The operators [δ, ∆] and [ǫ, E] are respectively a dilation and an erosion acting on the lattice (G, ⊑). Furthermore, ([ǫ, E] , [δ, ∆, )] is an adjunction.

Proof. Let X and Y be two graphs in G. The following statements are equivalent.

[δ, ∆] (X) ⊑ Y δ(X • ) ⊆ Y • and ∆(X × ) ⊆ Y × , by definition of ⊑ X • ⊆ ǫ(Y • ) and X × ⊆ E(Y × )
, by definition of the adjunctions (ǫ, δ) and (E, ∆)

X ⊑ [ǫ, E] (Y )
, by Lemma 14, by definitions of [ǫ, E] and ⊑ .

Thus, the pair ([ǫ, E] , [δ, ∆]) is an adjunction, which implies that [ǫ, E] is an erosion and that [δ, ∆] is a dilation.

Note that since lattice G is sup-generated by set S, it suffices to know the dilation of the graphs in S for characterizing the dilation of the graphs in G.

Compared to usual morphological operators on sets, the dilations and erosions introduced in Definition 13 furthermore convey some connectivity properties different than the ones which can be deduced from usual dilations and erosions. Observe, for instance, in Figs. 1, that some adjacent vertices of δ(X • ) (Fig. 1c) are not linked by an edge in the graph [δ, ∆] (X) (Fig. 1d). A similar observation can be made in Fig. 2g, where some 4-adjacent vertices of δ(X • ) are not linked by an edge in the graph [δ, ∆] (X). These properties can have an impact on the results of further processing involving for instance connected operators [START_REF] Salembier | Flat zones filtering, connected operators, and filters by reconstruction[END_REF][START_REF] Ronse | Set-theoretical algebraic approaches to connectivity in continuous or digital spaces[END_REF][START_REF] Braga-Neto | Connectivity on complete lattices: new results[END_REF]23]. The evaluation of this impact is left to future work.

By its very definition the vertex set (resp. edge set) of [δ, ∆] (X) depends only on the vertex set (resp. edge set) of the graph X. Thus, the dilation of an isolated vertex does not contain any edge (see e.g. the graph X of Fig. 2b that contains an isolated vertex and its dilation [δ, ∆] (X) shown in Fig. 2g). In fact, due to the operators presented in Definition 4, other adjunctions (hence dilations/erosions) can be defined on G:

1. (α 1 , β 1 ) such that ∀X ∈ G, α 1 (X) = (G • , X × ) and β 1 (X) = (δ • (X × ), X × ); 2. (α 2 , β 2 ) such that ∀X ∈ G, α 2 (X) = (X • , ǫ × (X • )) and β 2 (X) = (X • , ∅); 3. (α 3 , β 3 ) such that ∀X ∈ G, α 3 (X) = (ǫ • (X × ), ǫ × • ǫ • (X × )) and β 3 (X) = (δ • • δ × (X • ), δ × (X • )).
Note that, using usual graph terminologies, β 1 (resp. α 2 ) can be defined as the operator which associates to a graph the graph induced by its edge set (resp. vertex set). The adjunction (α 3 , β 3 ) is illustrated in Figs. 2i and2j. Remark that contrary to the dilation [δ, ∆] (X), the dilation β 3 (X) depends (only) on the vertex set of X. In particular, the edge set of β 3 (X) contains all edges which have at least one extremity in X • . Hence, the dilation β 3 of a graph that has an isolated vertex comprises all the edges of G containing this isolated vertex (see e.g. Fig. 2b in Fig. 2j).

a: Y b: [γ, Γ] 1 (Y ) c: [γ, Γ] 1/2 (Y ) d: β3 • α3(Y ) e: Z f: [φ, Φ] 1 (Z) g: [φ, Φ] 1/2 (Z) h: α3 • β3(Z)

Filters

In mathematical morphology, a filter is an operator α acting on a lattice L, which is increasing (i.e. ∀X, Y ∈ L, α(X) ≤ α(Y ) whenever X ≤ Y ) and idempotent (i.e. ∀X ∈ L, α(α(X)) = α(X)). A filter α on L which is extensive (i.e. ∀X ∈ L, X ≤ α(X)) is called a closing on L whereas a filter α on L which is anti-extensive (i.e. ∀X ∈ L, α(X) ≤ X) is called an opening on L. It is known that composing the two operators of an adjunction yields an opening or a closing depending on the order in which the operators are composed [START_REF] Ronse | Algebraic foundations of morphology[END_REF]. In this section, the operators of Section 3 are composed to obtain filters on G • , G × and G.

Definition 16 (opening, closing).

1. We define γ 1 and φ 1 , that act on G • , by Definition 17 (half-opening, half-closing). We define

γ 1 = δ • ǫ and φ 1 = ǫ • δ. 2. We define Γ 1 and Φ 1 , that act on G × , by Γ 1 = ∆ • E and Φ 1 = E • ∆. 3. We define the operators [γ, Γ] 1 and [φ, Φ] 1 by respectively [γ, Γ] 1 (X) = (γ 1 (X • ), Γ 1 (X × )) and [φ, Φ] 1 (X) = (φ 1 (X • ), Φ 1 (X × )) for any X ∈ G.
1. γ 1/2 and φ 1/2 , which act on G • , by γ 1/2 = δ • • ǫ × and φ 1/2 = ǫ • • δ × 2. Γ 1/2 and Φ 1/2 , which act on G × , by Γ 1/2 = δ × • ǫ • and Φ 1/2 = ǫ × • δ • . 3. [γ, Γ] 1/2 and [φ, Φ] 1/2 by [γ, Γ] 1/2 (X) = (γ 1/2 (X • ), Γ 1/2 (X × )) and [φ, Φ] 1/2 (X) = (φ 1/2 (X • ), Φ 1/2 (X × )),
for any X ∈ G.

Due to Property 5, the operators defined above can be locally characterized as presented in the next property whose proof is similar to the one of Property 9 and Property 12, and as such is left to the reader.

Property 18. Let X • ⊆ G • and Y × ⊆ G × .
The eight following statements hold true.

1. γ 1/2 (X • ) = {x ∈ X • | ∃e x,y ∈ G × with y ∈ X • } 2. γ 1/2 (X • ) = X • \ {x ∈ X • | ∀e x,y ∈ G × , y / ∈ X • } 3. Γ 1/2 (Y × ) = {u ∈ G × | ∃x ∈ u with {e x,y ∈ G × } ⊆ Y × } 4. Γ 1/2 (Y × ) = Y × \ {u ∈ Y × | ∀x ∈ u, ∃e x,y ∈ G × with e x,y / ∈ Y × } 5. φ 1/2 (X • ) = {x ∈ G • | ∀e x,y ∈ G × , either x ∈ X • or y ∈ X • } 6. φ 1/2 (X • ) = X • ∪ {x ∈ X • | ∀e x,y ∈ G × , y ∈ X • } 7. Φ 1/2 (Y × ) = {e x,y ∈ G × | ∃e x,z ∈ Y × and ∃e y,w ∈ Y × } 8. Φ 1/2 (Y × ) = Y ∪ {e x,y ∈ Y × | x ∈ δ • (Y × ) and y ∈ δ • (Y × )}
Informally speaking, γ 1/2 removes from X • its isolated vertices (i.e. the vertices whose strict neighborhood is included in X • ) whereas Γ 1/2 removes from Y × the edges which do not contain at least a vertex completely covered by edges in Y × (i.e., a vertex such that any edge of G containing this vertex is included in Y × ). Due to Property 6, it may be furthermore seen that γ 1/2 (resp. Γ 1/2 ) is the dual of φ 1/2 (resp. Φ 1/2 ). Thus, φ 1/2 adds to X • any vertex of X • completely surrounded by elements of X • (i.e., any vertex whose strict neighborhood is included in X • ) whereas Φ 1/2 adds to Y × the edges of Y × whose two extremities belong to at least one edge in Y × (see for instance Fig. 3).

The operator [γ, Γ] 1 (resp. [φ, Φ] 1 ) is defined in Definition 16.3 by its independent actions on the vertex set and on the edge set of a graph. In fact, [γ, Γ] 1 (resp. [φ, Φ] 1 ) can also be characterized as a composition of operators acting on graphs.

Lemma 19. The two following statements hold true.

[γ, Γ]

1 = [δ, ∆] • [ǫ, E] 2. [φ, Φ] 1 = [ǫ, E] • [δ, ∆] Proof.
1. Let X be any graph in G. By Definition 16.3, we have [γ, Γ] 1 (X) = (γ 1 (X • ), Γ 1 (X × )). Thus, by Definitions 16.1 and 16.2, we have

[γ, Γ] 1 (X) = (δ • ǫ(X • ), ∆ • E(X × )). Hence, by Definition 13, we have [γ, Γ] 1 (X) = [δ, ∆] • [ǫ, E] (X). 2.
The proof of this statement is similar, and as such, it is left to the reader.

The next property, which is one of the main results of this section, allows the operators presented in Definitions 16 and 17 to be classified as openings and closings acting on subsets of vertices, subsets of edges or subgraphs of G.

Property 20 (graph-openings, graph-closings).

1. The operators γ 1/2 and, γ 1 (resp. Γ 1/2 and Γ 1 ) are openings on G • (resp. G × ) and φ 1/2 , and Φ 1 (resp.

Φ 1/2 and φ 1 ) are closings on G • (resp. G × ).

The family G is closed under

[γ, Γ] 1/2 , [φ, Φ] 1/2 , [γ, Γ] 1 ,
× (resp. e x,y ∈ [φ, Φ] 1/2 (X) × ) , we have x ∈ [γ, Γ] 1/2 (X) • and y ∈ [γ, Γ] 1/2 (X) • (resp. x ∈ [φ, Φ] 1/2 (X) • and y ∈ [φ, Φ] 1/2 (X) • ).
Let us first consider [γ, Γ]

x ∈ [[φ, Φ] 1/2 (X)] • and y ∈ [φ, Φ] 1/2 (X) • . Thus, G is closed under [φ, Φ] 1/2 . 3. Let X ⊑ Y ⊑ G.
Then, by definition of ⊑, we have X • ⊆ Y • and X × ⊆ Y × . By Property 20.1, the operators γ 1/2 and Γ 1/2 are openings. By idempotence of openings, we have

γ 1/2 (γ 1/2 (X • )) = γ 1/2 (X • ) and Γ 1/2 (Γ 1/2 (X × )) = Γ 1/2 (X ×
). Thus, by Definition 17.3, we deduce that [γ, Γ] 1/2 is idempotent:

[γ, Γ] 1/2 ([γ, Γ] 1/2 (X)) = [γ, Γ] 1/2 (X) (5)
By increasingness of openings, we have γ

1/2 (X • ) ⊆ γ 1/2 (Y • ) and Γ 1/2 (X × ) ⊆ Γ 1/2 (Y × ).
[γ, Γ] 1/2 (X) ⊑ [γ, Γ] 1/2 (Y ) (6)
By anti-extensivity of openings, we have γ

1/2 (X • ) ⊆ X • and Γ 1/2 (X × ) ⊆ X × . Thus, since [γ, Γ] 1/2 (X)
is a graph (Property 20.2), by Definition 17.3 and by definition of ⊑, we deduce that [γ, Γ] 1/2 is antiextensive:

[γ, Γ] 1/2 (X) ⊑ X (7)
From Equations 5, 6, and 7, we deduce that [γ, Γ] 1/2 is an opening. Similarly, one proves that [γ, Γ] 1 is an opening, and that [φ, Φ] 1/2 and [φ, Φ] 1 are closings.

Composing the operators of the adjunctions (α i , β i ), defined at the end of Section 3, also yields remarkable openings and closings. Indeed, it can be easily seen that:

α 1 • β 1 = α 1 , α 2 • β 2 = α 2 , β 1 • α 1 = β 1 and β 2 • α 2 = β 2 .
Thus α 1 and α 2 are both a closing and an erosion and β 1 and β 2 are both a dilation and an opening. This means, in particular, that α 1 and α 2 are idempotent extensive erosions and that β 1 and β 2 are idempotent anti-extensive dilations. The opening and the closing resulting from the adjunction (α 3 , β 3 ) are illustrated in Figs. 3d and3h.

It is possible to associate with any lattice L, the lattice of all increasing operators on L. In this context, two filters ϕ 1 and ϕ 2 on the lattice L are said ordered if, for any X ∈ L, ϕ 1 (X) ≤ ϕ 2 (X) or if, for any X ∈ L, ϕ 2 (X) ≤ ϕ 1 (X). A usual way to build a hierarchy of filters (i.e. an ordered family of filters) from an adjunct pair (α, β) of erosion and dilation consists of building the dilations and erosions obtained by iterating several times α and β. In general, composing these iterated versions of α and β leads to hierarchies of filters when the number of iterations increases. In the remaining of the section, we follow this classical approach to build granulometries and alternate sequential filters in the lattice G.

Let α be an operator acting on a lattice L and i be a nonnegative integer. The operator α i is defined by the identity on L when i = 0 and by α • α i-1 otherwise.

Definition 21. Let λ ∈ N. We define [γ, Γ] λ/2 (resp. [φ, Φ] λ/2 ) by [γ, Γ] λ/2 = [δ, ∆] i • ([γ, Γ] 1/2 ) j • [ǫ, E] i (resp. [φ, Φ] λ/2 = [ǫ, E] i • ([φ, Φ] 1/2 ) j • [δ, ∆] i )
, where i and j are respectively the quotient and the remainder in the integer division of λ by 2.

Theorem 22 (granulometries). The families

{[γ, Γ] λ/2 | λ ∈ N} and {[φ, Φ] λ/2 | λ ∈ N} are granulometries:
2. By Lemma 23.3 (applied to [ǫ, E] (X)), we have:

[γ, Γ] 1 • [ǫ, E] i (X) ⊑ [γ, Γ] 1/2 • [ǫ, E] i (X) ⊑ [ǫ, E] i (X) (8) Since ([ǫ, E] i , [δ, ∆] i
) is an adjunction (see above), the operator [δ, ∆] i is a dilation and as such it is increasing (see e.g. Lemma 2.1 in [15] for increasingness of dilations). Thus, from Equation 8, we deduce that:

[δ, ∆] i • [γ, Γ] 1 • [ǫ, E] i (X) ⊑ [δ, ∆] i • [γ, Γ] 1/2 • [ǫ, E] i (X) ⊑ [δ, ∆] i • [ǫ, E] i (X). ( 9
)
Hence, by Lemma 19 and by Definition 21, we have:

[γ, Γ] (2×i+2)/2 (X) ⊑ [γ, Γ] (2×i+1)/2 (X) ⊑ [γ, Γ] (2×i)/2 (X). ( 10
)
This last statement allows the proof to be completed by induction.

Similar arguments (according to the opposite order of ⊑) allows the statements on {[φ, Φ] λ/2 | λ ∈ N} to be proved: these proofs are left to the reader.

Definition 25 (ASF). Let λ ∈ N. We define the operator ASF λ/2 by the identity on graphs when λ = 0 and by

ASF λ/2 = [γ, Γ] λ/2 • [φ, Φ] λ/2 • ASF (λ-1)/2 otherwise.
Note that it is possible to define a second family of operators similar to

ASF = {ASF λ/2 | λ ∈ N} by replacing in Definition 21.2 the sequence of primitives [γ, Γ] λ/2 • [φ, Φ] λ/2 by the sequence [φ, Φ] λ/2 • [γ, Γ] λ/2 .
The following proposition, which establishes that ASF is a family of alternate sequential filters, also holds true for this second family.

Corollary 26. The family {ASF λ/2 | λ ∈ N} is a family of alternate sequential filters:

• for any two elements λ, µ ∈ N, λ ≥ µ implies that ASF λ/2 • ASF µ/2 = ASF λ/2 .

Proof. Due to Equation 10.4 in [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF], the result is a direct corollary of Theorem 22.

Given a graph X ∈ G, it must be noticed that the vertex set (resp. edge set) of [γ, Γ] λ/2 (X) and [φ, Φ] λ/2 (X) depends only on the vertex set (resp. edge set) of X. Thus, Definition 21 also induces granulometries and alternate sequential filters on G • and G × . If we consider the case where λ is even, we deduce from the observation stated after Definition 7 that, when G • is a subset of the grid points Z d and when G × is obtained from a symmetrical structuring element, then the vertex parts of [γ, Γ] λ/2 and [φ, Φ] λ/2 correspond to the usual opening and closing of size λ/2. Hence, we can see that, in the case of a set of points, the proposed framework completes the granulometries and filters which are classically used in applications by considering the odd values of λ.

Flat morphological operators on weighted graphs

The morphological operators presented in previous sections are increasing. As such, they all induce stack operators acting on functions weighting the vertices and/or edges of a graph (see [START_REF] Wendt | Stack filters[END_REF] for stack operators, [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF][START_REF] Maragos | Morphological filters-Part I: Their set-theoretic analysis and relations to linear shift-invariant filters[END_REF][START_REF] Heijmans | Theoretical aspects of gray-level morphology[END_REF][START_REF] Ronse | Flat morphology on power lattices[END_REF] for stack operators in the context of flat mathematical morphology, and [1] for stack operators in the context of watershed image segmentation). This allows filters for weighted graphs and thus for grayscale images to be systematically inferred from the ones on non-weighted graphs. In this section, we first recall the definition of stack operators through threshold decomposition of functions. Then, we give a simple characterization of the stack operators induced by the basic operators of Definition 4.

In this section, the symbol n denotes any positive integer and the symbol K stands for the set of all integers between 0 and n: K = {0, . . . , n}.

Let E be any set, we denote by Fun(E) the set of all maps from E to K. Let k ∈ K and let F ∈ Fun(E). The k-section (or k-threshold) of F is the subset X k (F ) of E made of the elements of E whose value is above k according to the function F : X k (F ) = {x ∈ E | F (x) ≥ k}. Note that Fun(E) with the order relation ≤ inferred by threshold decomposition from the inclusion relation ⊆ on E is a complete lattice. Its supremum ∨ can also be characterized by threshold decomposition. More precisely, for any two functions F 1 and F 2 in Fun(E), we have:

F 1 ≤ F 2 iff ∀k ∈ K, X k (F 1 ) ⊆ X k (F 2 ) (11) [F 1 ∨ F 2 ](x) = max{k ∈ K | x ∈ [X k (F 1 )] ∪ [X k (F 2 )]}, ∀x ∈ E. (12)
Furthermore, since the lattice K forms a finite chain, Equation 12 can be generalized to arbitrary (infinite) supremum and union, and also to arbitrary (infinite) infimum and intersection.

Let E 1 and E 2 be two sets, and let P(E 1 ) and P(E 2 ) be the set of all subsets of E 1 and E 2 respectively. Any increasing operator ψ from the lattice P(E 1 ) to the lattice P(E 2 ) induces the stack operator Ψ that maps any function F in Fun(E 1 ) to the function Ψ(F ) in Fun(E 2 ) according to the following relation:

∀x ∈ E 2 , Ψ (F ) (x) = max{k ∈ K | x ∈ ψ (X k (F ))} (13)
In fact, since the lattice K forms a finite chain, for any k ∈ K, the k-section of Ψ(F ) is exactly the result of the operator ψ applied to the k-section of F . More precisely, Ψ is the stack operator induced by ψ if and only if, for any map F ∈ Fun(E 1 ), the following relation holds true:

∀k ∈ K, X k (Ψ (F )) = ψ (X k (F )) . (14)
By abuse of notation, in the following, we use the same symbol to denote an operator acting from P(E 1 ) to P(E 2 ) and its induced stack operator acting from Fun(E 1 ) to Fun(E 2 ). By threshold decomposition, the lattice G of subgraphs of G presented in Section 2 induces a lattice Fun(G • ) ⊗ Fun(G × ) of pairs of functions weighting respectively the vertices and the edges of G such that the simultaneous threshold of these two functions at any given level yields a subgraph of G.

Note that using Equation 13, the operators acting on the lattices G • , G × , or G, presented in Sections 3 and 4, induce stack operators acting on the lattices Fun(G • ), Fun(G × ), and Fun(G • ) ⊗ Fun(G × ). Furthermore, due in particular to Equation 12, any property presented in Sections 3 and 4 for operators on the lattices G • , G × , or G also holds true for operators on the lattices Fun(G • ), Fun(G × ), and Fun(G • ) ⊗ Fun(G × ). Among the operators on unweighted graphs, those presented in Definition 4 play the role of elementary building blocks. Therefore, we shall first characterize their induced stack filters. Property 27. Let F • ∈ Fun(G • ) and let F × ∈ Fun(G × ). The four following relations hold true.

δ • (F × )(x) = max{F × (e x,y ) | e x,y ∈ G × }, ∀x ∈ G • (15) ǫ × (F • )(e x,y ) = min{F • (x), F • (y)}, ∀e x,y ∈ G × (16)
ǫ • (F × )(x) = min{F × (e x,y ) | e x,y ∈ G × }, ∀x ∈ G • (17) δ × (F • )(e x,y ) = max{F • (x), F • (y)}, ∀e x,y ∈ G × (18)
Property 27, which is as a "stack analogous" to Property 5, locally characterizes the stack operators δ • , ǫ × , ǫ • , δ × . It leads in particular to a simple linear time algorithm (with respect to the size

|G • | + |G × | of G)
to compute the results of these operators. More interestingly, since the proposed operators acting on subgraphs of G have all been characterized as compositions of these four basic operators, all induced stack operators acting on functions weighting the edges and/or vertices of the graph G can be characterized as composition of these basic operators. Furthermore, the opening/closing and granulometry properties proved in the previous sections extend from sets to weight functions by flat morphology.

Illustration to image processing

This section presents three illustrations that show the application of the proposed framework to image processing. We first illustrate in Section 6.1 the differences between the ASF filters proposed in this paper and the usual ASF filters by symmetric structuring elements for denoising binary images. Then, the second illustration (Section 6.2) presents the results of the proposed ASF filter, of a median filter, and of the an area filter [START_REF] Vincent | Morphological area openings and closings for grey-scale images[END_REF] applied to several degraded versions of a binary image. Finally, the third illustration (Section 6.3) shows the ability of the proposed filters to process noisy grayscale images. Firstly, filters on a spatially invariant graph are used. Then, it is shown that the proposed framework also includes spatially variant morphological filters. Indeed, the obtained results are improved by replacing the initial spatially invariant graph by a second graph that is spatially variant.

ASF filters applied on binary images

In order to illustrate the proposed framework, let us analyze the effect of our filters on the binary image of Fig. 4b obtained by adding random impulse noise of different size and shape to the digital shape shown in Fig. 4a. Fig. 4c shows the results given by the "usual" ASF (using the structuring elements corresponding to the 4-adjacency relation) of size 4. Fig. 4d presents the results given by ASF 8/2 (on the graph induced by the 4-adjacency relation) which is the corresponding alternate filter in our framework. Note that for the illustrations in image processing shown in this paper the restriction of the filters to G • are considered. Clearly, ASF 8/2 removes more noise than the usual ASF. However, it requires more iterations since it considers the filters [γ, Γ] λ/2 and [φ, Φ] λ/2 for both odd and even values of λ whereas the usual ASF only considers the even values of λ (see last paragraph of Section 4). In order to compare the proposed ASF with filters using the same number of iterations, we produce two other filtered images. The first one is obtained by filtering the image with a usual ASF of size 8 (Fig. 4e). It can be seen that more noise are removed but also that less details are preserved (see in particular the head of the zebra). The second one (Fig. 4f) is obtained in three steps: 1) double the resolution of the noisy image; 2) apply to it a usual ASF of size 8; and 3) divide by two the resolution of the output image. Visually, this last procedure removes more noise than the usual ASF but does not perform as well as the ASF introduced in the present paper (a quantitative study is provided below). Fig. 5 provides a similar illustration for the case of a 3-dimensional synthetic binary object.

To assess the filtering results also quantitatively, we generated 20 binary images of 800x600 pixels containing white characters on a black background, one of them is illustrated on Fig. 6a. We then created eleven sets of noisy versions of those images, each set with increasing level of noise, from around 5% up to around 25%. The noise was generated using sets of random points of uniform distribution, that were then dilated separately using a dilation by different structuring elements: lines, disks and crosses, with different sizes and directions, along with single points. Those images were then combined with the original image using an exclusive or logical operator. Fig. 6b to Fig. 6l shows the same section of one of the resulting noisy images for each one of the considered levels of noise.

Each set of noisy images was then filtered using the usual ASF, with normal and double resolution, and the graph ASF. We kept the same configuration used to process the images on Fig. 4. We considered filters with sizes between 1/2 and 10. As error measure we computed the mean square error, that, considering binary images, is equivalent to the number of different pixels divided by the number of pixels in the image, expressed here in percentages. Fig. 7a (resp. Fig. 7b and Fig. 7c) shows the average error of each set of filtered images using the usual ASF (usual ASF with double resolution and graph ASF) for all the considered sizes. Points corresponding to the same set are connected by a line. Clearly the graph ASF presents a lower error for all sizes of the considered filters. For instance, remark in particular that for the highest value of noise, the error measure obtained by graph ASF of size 10/2 is approximately 4%, whereas it is approximately 16% for the usual ASF of size 5 and 7.5% for the usual ASF of size 10 applied on images of double resolution.

A filter is called autodual if it leads to equivalent results considering both the original image and its complement, that is, by complementing the filtered result of the complement image, we obtain the filtered result of the original image. It is known that the ASF filters based on structuring elements are in general not autodual. The ASF filters proposed in this paper are not autodual either. However, treating white and black pixels in a balanced way is surely an interesting property. To assess the behavior of the filters on this aspect, we repeated this same experiment, but now considering the complement of the images (which is equivalent to inverting the opening and closing in Definition 25 of ASFs). The results are presented on Fig. 8. We obtain the same behavior as the previous case, that is, the graph ASF still outperforms the usual ASF, with normal and double resolution. Further, to measure how balanced our filters are, we compared the filtered images generated using the original image and its complement. The result of that comparison, considering only the set of images with most noise, is shown on figure 9. The images generated using the graph ASF considering the original image and the complement are more similar than using the usual ASF, with normal and double resolution.

From the presented results we can conclude that, considering this type of image and noise, the graph ASF outperforms the usual approach, removing more noise for a given size of filter. Additionally, our operator treats white noise and black noise in a more balanced way than the usual filters.

ASF, median, and area filters applied on binary images

The previous experiment was designed to illustrate the differences between the proposed graph filters and their corresponding versions in the usual framework of morphology by structuring elements. Let us now illustrate the difference between the proposed graph filters and some filters that are frequently used for denoising binary images. To this end, we degrade the image I shown in Fig. 10 according to the model of [START_REF] Kanungo | A statistical, nonparametric methodology for document degradation model validation[END_REF] which is known as a realistic document degradation model. Roughly speaking, the resulting degradation, obtained by a flipping process, includes impulse black and white noise and contour perturbation. From the initial image I, we produced five levels of degraded images I 1 , . . . , I 5 . Then, these images were processed with the ASF filter proposed in this paper (with parameter 2/2), with a median filter (by a diamond structuring element of size 5), and with the composition of an area opening and an area closing (of size 20). The results for an intermediate level of degradation are shown in Figs. 10 and11. The mean square errors (MSEs) compared to the original image achieved by these three methods on the five degraded images I 1 , . . . , I 5 , are presented in Table 1. On all these degraded images the MSEs of the graph ASF are less than the ones of the median filter. For low levels of degradation the MSEs of the graph ASF and of the area filtering are similar, while the MSEs of the graph ASF become lower than the ones of the area filters when the level of degradation increases. In this illustration, the parameters of the filters were chosen qualitatively to produce the best results on these five particular degraded images. In order to state any definitive conclusion about the comparison of these filters for denoising binary images, quantitative experiments on a larger database of real images need to be done. However, performing such an evaluation is beyond the scope of this paper.

Spatially invariant and variant ASF filters applied on grayscale images

As an illustration of the framework presented in Section 5, one can consider the stack extension of the family {ASF λ/2 | λ ∈ N} and apply it to weighted graphs. Similarly to the case of unweighted graphs, it can be seen that the weights on the vertices of the resulting graph depend only of the weights of the vertices of the original graph. Therefore, the operators of the family {ASF λ/2 | λ ∈ N} also induce alternate sequential filters on vertex weighted graphs. In particular, since a grayscale image equipped with an adjacency relation can be seen as a vertex weighted graph, we obtain new alternate sequential filters acting on grayscale images equipped with adjacency relations. Fig. 12b shows a grayscale image obtained by adding random impulse noise of different size to the grayscale image of Fig. 12a. Fig. 13a shows the results given by the "usual" alternate sequential filter (using the structuring elements corresponding to the 4-adjacency relation) of size 3. Fig. 13b presents the results given by the stack operator ASF 6/2 (on the graph induced by the 4-adjacency relation) which is the corresponding alternate filter in our framework. Visually, ASF 6/2 removes more noise than the usual alternate sequential filter. More precisely, compared to the original image of Fig. 12a, the mean square error (MSE) achieved by the graph filter equals 159.5, whereas it equals 175 for the "usual" alternate sequential filter. As in the binary case presented in Section 6.1, we also applied a usual ASF of size 12 to the image obtained from Fig. 12b by doubling the resolution. On this particular image, the resulting MSE equals 162.2 which is a little more than with the graph ASF. For concision, we do not present in this section a quantitative assessment on a larger database of grayscale images. Such quantitative assessment is left for future work.

Interestingly, the framework of graphs presented in this paper encompasses the one of mathematical morphology based on discrete spatially variant (symmetric) structuring elements or amoebas (see e.g. [START_REF] Lerallut | Image filtering using morphological amoebas[END_REF][START_REF] Tankyevych | Spatially-variant morpho-hessian filter: Efficient implementation and application[END_REF][START_REF] Verd-Monedero | Spatially-variant anisotropic morphological filters driven by gradient fields[END_REF][START_REF] Stawiaski | Minimum spanning tree adaptive image filtering[END_REF]). Let us then illustrate the effect of the alternate filters proposed in this framework on a graph that is spatially variant. To this end, we considered a smoothed version H • of the image F • (Fig. 12b) obtained by a Gaussian filter. Then, we derive from the "spatially invariant" vertex weighted graph (G 4 , H • ) associated to the grayscale image H • equipped with the 4-adjacency relation a graph G that is "spatially variant". To obtain this graph G, we first consider a simple gradient ∇ : G × → K of H • given by ∇(e x,y ) = |H • (x) -H • (y)| for any edge e x,y in G 4 × . Note that, using the framework of this paper, this simple gradient can be straightforwardly characterized in morphological terms: ∇(e x,y ) = δ × (H • )(e x,y )-ǫ × (H • )(e x,y ), for any edge e x,y in G 4 × . Then, this gradient ∇ can be thresholded at a value ν in order to produce a new graph G such that G • = G 4

• and G × = {e x,y ∈ G 4 × | ∇(e x,y ) ≤ ν}. The image shown in Fig. 13d presents the result obtained by applying ASF 6/2 to the map F • in the graph G which is obtained by the above strategy for ν = 35. For comparison purposes, we also display in Fig. 13c, the result obtained using the usual alternate sequential filter of size 3 (i.e., the filter obtained without considering the odd values of λ) using the spatially variant structuring element corresponding to the same graph G. Visually the result of the proposed filter outperforms the one of usual spatially variant filter. Furthermore, the MSE compared to the original image of Fig. 12a also assesses that the proposed filter outperforms the usual one on this image (140 vs. 151.3). Note also that using spatially variant filters instead of invariant ones allows the results of ASF 6/2 to be improved (140.9 vs. 159.5 as respective MSE).

On a conventional PC (Intel Core 2 Duo CPU, 2.4 GHz, 2GB), the processing time for applying ASF 6/2 to the image of Fig. 12b (800 × 815 pixels) in the case of the spatially invariant (resp. variant) graph is 2.75 seconds (resp. 2.55 seconds).

Conclusion

This paper investigates the lattice of all subgraphs of a graph and provides it with morphological operators. In particular, we propose new filters whose input and output are both graphs. We show the interest of restricting these filters to sets of vertices. Indeed, they allow us to complete some usual morphological filters used in image analysis applications. It is also shown that the proposed framework can be extended from subgraphs to functions that weight the vertices and/or edges of a graph. This allows in particular the processing of grayscale images by spatially invariant as well as spatially variant morphological operators. The extension of this framework to multi-valued functions allowing to process in particular color images remains for future work, as well as the study of new algorithms, based e.g. on distance maps, allowing very fast computation for the case of iterated operators.

Simplicial (and cubical) complexes (see [START_REF] Couprie | New characterizations of simple points in 2D, 3D, and 4D discrete spaces[END_REF][START_REF] Cousty | Collapses and watersheds in pseudomanifolds[END_REF] for image operators defined in cubical complexes and [START_REF] Loménie | Morphological mesh filtering and α-objects[END_REF] for examples of morphological operators in 2D simplicial complexes) allows topological properties of discrete objects to be better handled than with graphs. These topological structures extend graphs to higher dimensions in the sense that a graph is a 1-D structure made of points and edges considered as 0D and 1D elements. As shown in [START_REF] Dias | Some morphological operators on simplicial complex spaces[END_REF], the framework presented in this paper can be extended to complexes by considering additional generators. In 2D, for instance, a third generator for the elementary triangles (or squares) is required.

Another interesting field of investigation for future work includes the study of morphological operators for (directed and undirected) graphs embedded in metric spaces (or more generally weighted graphs spaces). In this context, the result of a given operator depends on the "length" of the edges according to the metric. Such kind of operators, acting with dilation-like behavior, have been studied in particular in [31]. Nevertheless, as far as we know, the existing operators do not satisfy the important algebraic properties of morphological operators such as for instance idempotence of the filters.

Figure 1 :

 1 Figure 1: Illustration of a vertex-dilation and of a graph-dilation.

Figure 2 :

 2 Figure 2: Dilations and erosions.

Property 6 ( 1 .

 61 dilation, erosion, adjunction, duality). Operators ǫ × and δ × (resp. ǫ • and δ • ) are dual of each other. 2. Both (ǫ × , δ • ) and (ǫ • , δ × ) are adjunctions. 3. Operators ǫ • and ǫ × are erosions. 4. Operators δ • and δ × are dilations.

Lemma 14 .

 14 The family G is closed under the operators [δ, ∆] and [ǫ, E]. More precisely, for any subgraph X of G, both [δ, ∆] (X) and [ǫ, E] (X) are subgraphs of G.

Figure 3 :

 3 Figure 3: Openings and closings (G is induced by the 4-adjacency relation).

Figs. 3b and

  Figs. 3b and 3f present the result of [γ, Γ] 1 and [φ, Φ] 1 for respectively the subgraph of Fig. 3a and the one of Fig. 3e. In fact, by composing δ • with ǫ × and δ × with ǫ • , less active filters are obtained (Property 20 and Lemma 23).

  (a) original binary image (b) noisy binary image (c) usual ASF (d) graph ASF (e) usual ASF of double size (f) usual ASF (double resolution)

Figure 4 :

 4 Figure 4: ASF illustration [see text].

Figure 5 :

 5 Figure 5: Same as Fig. 4 but in 3D. Rendering of: (a) original binary image, (b) noisy binary image, (c) result of usual ASF, (d) result of graph ASF, (e) result of usual ASF of double size and (f) result of usual ASF (double resolution) [see text].

Figure 6 :

 6 Figure 6: Example of noisy images considered for the assessment of the filters [see text].

Figure 7 :

 7 Figure 7: Average error for sets of filtered images: (a) usual ASF, (b) usual ASF with double resolution, (c) graph ASF [see text].

Figure 8 :

 8 Figure 8: Average error for complement of the sets of filtered images: (a) usual ASF, (b) usual ASF with double resolution, (c) graph ASF [see text].

Figure 9 :

 9 Figure 9: Difference between the filtered images considering the original image and its complement.

Figure 10 :

 10 Figure 10: (a): Original image I, (b): the degraded image I 3 , (c,d,e): filtering of I 3 by respectively ASF 2/2 , a median filter, and area filters. To ease printing and visualization the images in b-e are inverted.

Figure 11 :

 11 Figure 11: (a-e): Close-up views on a part of Figs. 10a-e (without inversion).

Figure 12 :

 12 Figure 12: Original image (a) and its noisy version (b).

Figure 13 :

 13 Figure 13: Result of morphological filtering of sizes 3 and 6/2 applied to the image of Fig. 12b.

  4. Property 5.4 will be deduced by duality from Property 5.2. By Definition 4, we have δ× (Y • ) = [⊔G Y • ] × .Thus, again by Definition 4, we have δ × (Y • ) = ǫ × (Y • ). Therefore, by Property 5.2, we have the equality δ ×

  and [φ, Φ] 1 . 3. The operators [γ, Γ] 1/2 and [γ, Γ] 1 are openings on G and [φ, Φ] 1/2 and [φ, Φ] 1 are closings on G. Due to the fundamental theorem of adjunctions recalled in the introduction of the section, Property 20.1 is a direct consequence of the facts that (ǫ × , δ • ), (ǫ• , δ × ), (ǫ, δ) and (E, ∆) are adjunctions (Property 6, Remarks 8 and 11). 2. By Lemma 14, G is closed under [δ, ∆] and [ǫ, E], and by Lemma 19, [γ, Γ] 1 and [φ, Φ] 1 are the compositions of these two operators. Hence, G is closed under [γ, Γ] 1 and [φ, Φ] 1 . In order to complete the proof of Property 20.2, it remains to show that G is also closed under [γ, Γ] 1/2 and [φ, Φ] 1/2 . Let X ∈ G. We are going to prove that [γ, Γ] 1/2 (X) (resp. [φ, Φ] 1/2 ) is a graph. To this end, it is sufficient to prove that, for any edge e x,y ∈ [γ, Γ] 1/2 (X)

	1.
	Proof.

  1/2 . Let e x,y ∈ [γ, Γ] 1/2 (X)

×

. By Definition 17.3, we have e x,y ∈ Γ 1/2 (X × ). Thus, by Property 18.3, one of the two statements [{x x,z ∈ G × } ⊆ X × ] and [{x y,w ∈ G × } ⊆ X × ] must hold true. In any case, we have e x,y ∈ X × . Thus, x ∈ X • and y ∈ X • , which imply by Property 18.1 that x and y belong to γ 1/2 (X • ). Hence, by Definition 17.3, the vertices x and y belong to

[γ, Γ] 1/2 (X) • . Thus, G is closed under [γ, Γ] 1/2 .

Let us now consider [φ, Φ] 1/2 . Let e x,y ∈ [[φ, Φ] 1/2 (X)] × . By Definition 17.3, the edge e x,y belongs to Φ 1/2 (X × ). By Property 18.7, there exists an edge e x,z ∈ X × , and there exists an edge e y,w ∈ X × . Since X is a graph, we deduce that x ∈ X • and that y ∈ X • . Therefore, by Property 18.6, we have x ∈ φ 1/2 (X • ) and y ∈ φ 1/2 (X • ). Hence, by Definition 16.3, we have

Table 1 :

 1 Mean square error achieved by different filters applied to five noisy images obtained by degradation of Fig.10a.

		I 1	I 2	I 3	I 4	I 5
	graph ASF	0.5% 0.7% 1.3% 1.7% 3.6%
	area filter	0.5% 0.7% 1.6% 2.1	4.5%
	median filter 1%	1.4% 2.2% 2.6% 6%

The framework presented in this paper is a particular case of the one in[START_REF] Dias | Some morphological operators on simplicial complex spaces[END_REF] presented at the conference DGCI 2011 to which this special issue is dedicated.

As composition of adjunctions, ([ǫ, E] i , [δ, ∆]i ) is an adjunction. Thus, by the fundamental result aboutadjunction recalled in Section 3, [γ, Γ] (2×i)/2 = [δ, ∆] i •[ǫ, E] i is an opening. Furthermore, since [γ, Γ] 1/2is an opening (Property 20), by Lemma 24, we deduce that [γ, Γ](2×i+1)/2 = [δ, ∆] i • [γ, Γ] 1/2 • [ǫ, E] iis also an opening.

Acknowledgement

The authors warmly thank Laurent Mennillo for his help with the degradation model and algorithm used in Section 6.2.

The authors also would like to thank the anonymous reviewers for their helpful comments.

This work received funding from the Agence Nationale de la Recherche, contract ANR-2010-BLAN-0205-03.