Zhicheng Hou

Isabelle Fantoni

Composite Nonlinear Feedback-based Bounded Formation Control of Multi-quadrotor Systems

This paper presents a bounded formation controller for multiple quadrotors (UAVs) system with leaderfollower structure. Considering the actuator saturation of the quadrotors, the hyperbolic function is used in the formation controller design. The composite nonlinear feedback is integrated in the formation controller in order to improve the formation performance. The simulation and experimental results show that the formation task is achieved with small overshoot and rapid response speed.

I. INTRODUCTION

The cooperative control of multi-quadrotor systems has recently attracted the attention. The manipulation and transportation of large payloads by using multiple UAVs are investigated in [START_REF] Kushleyev | Towards a swarm of agile micro quadrotors[END_REF] and [START_REF] Michael | Cooperative manipulation and transportation with aerial robots[END_REF]. The problem of cooperative surveillance in large outdoor areas by a fleet of micro aerial vehicles is studied in [START_REF] Saska | Autonomous deployment of swarms of micro-aerial vehicles in cooperative surveillance[END_REF]. The applications such as search and rescue are covered in [START_REF] Dames | Autonomous localization of an unknown number of targets without data association using teams of mobile sensors[END_REF].

In practice, the inputs of a quadrotor are subject to actuator saturations. This problem is taken into account in the quadrotor controller design in the literature. For instance, a nested saturation controller is proposed in [START_REF] Kendoul | Real-time nonlinear embedded control for an autonomous quadrotor helicopter[END_REF]. An algorithm of feasible trajectories planning is investigated in [START_REF] Hehn | Quadrocopter trajectory generation and control[END_REF], where the input constraints of quadrotor are considered.

To the best of our knowledge, the input saturations are not very much considered in the multi-quadrotor systems control. In [START_REF] Su | Semi-global leader-following consensus of linear multi-agent systems with input saturation via low gain feedback[END_REF], a low gain feedback control is proposed to avoid the saturation of the system, such that a semi-global leader-follower consensus of linear multi-agent system is achieved. In the formation control of multi-UAV systems, a large formation error can generate a large control output. This could lead to big attitude angles for the UAVs of the formation. Although the low gain controller [START_REF] Su | Semi-global leader-following consensus of linear multi-agent systems with input saturation via low gain feedback[END_REF] can guarantee the control output small, the response speed of the closedloop system is low.

In this paper, the formation of quadrotors with Leader-Follower (L-F) structure is investigated. Considering the input saturation of the quadrotor, a bounded formation controller is developed. The formation control strategy is proposed aiming at investigating a bounded differentiable formation controller and obtaining the closed-loop system with fast response speed and small overshoot.

Zhicheng HOU and Isabelle FANTONI are with Sorbonne universités, Université de technologie de Compiègne, CNRS, UMR 7253 Heudiasyc, 60200 Compiègne, France.

zhicheng.hou/isabelle.fantoni@hds.utc.fr This work was carried out and funded in the framework of the Labex MS2T (Reference ANR-11-IDEX-0004-02) and the ROBOTEX Equipment of Excellence (Reference ANR-10-EQPX-44). They were supported by the French Government, through the program Investments for the future managed by the National Agency for Research.

In recent years, authors in [START_REF] Lin | Toward improvement of tracking performance nonlinear feedback for linear systems[END_REF] [START_REF] Chen | Composite nonlinear feedback control for linear systems with input saturation: theory and an application[END_REF] have proposed and implemented a "composite nonlinear feedback" (CNF) control to improve the performance of a system. The objective of this control method is to reduce the overshoot and meanwhile, keep a rapid rising response.

In this paper, we are inspired by the CNF control method to improve the performance of the formation of UAVs. Considering the input saturation of the quadrotors, a hyperbolic tangent function is used instead of a standard saturated function, which has two non-differentiable points when the function gets saturated. The high-order derivatives of the formation controller of each UAV are needed for the attitude control. Therefore, if we use the standard saturated function, an infinite derivative will be generated at the nondifferentiable points. In contrary, the hyperbolic tangent function is always differentiable and has bounded high-order derivatives.

The paper is organized as follows. The modeling and control of one quadrotor are presented in section II. The formation control design and the stability analysis are shown in section III. Simulation and experimental results are given in section IV. Finally, conclusions are stated in section V.

II. MODELING AND CONTROL OF ONE UAV

A. Modeling

The dynamics of a quadrotor is modeled as the motion of a rigid body in 3-D space under a thrust force and three moments, which are generated by the thrust forces of the four rotors. The orientation of the quadrotor with respect to the inertial frame is represented by the rotation matrix R i ∈ SO(3), where SO(3) represents a special orthogonal group, and whose determinant is one.

Vector

X i = [X i ,Y i , Z i ]
T represents the coordinates of the center of mass of a quadrotor in the fixed inertial frame o e x e y e z e . The Euler angles (roll, pitch and yaw) are represented by the vector Θ i = [φ i , θ i , ψ i ] T . The inertia matrix J = diag{I x b , I y b , I z b } of a quadrotor is diagonal, if I x b , I y b and I z b represent the moments of inertia with respect to the bodyfixed frame x b , y b and z b respectively. The angular velocity of the quadrotor i in the body-fixed frame is represented by Ω i ∈ R 3 . The function S(•) : R 3 → R 3×3 represents an operation that transforms a vector in R 3 to a skew-symmetric matrix R 3×3 .

The roll, pitch and yaw moments are represented by

τ i = [τ φ i , τ θ i , τ ψ i ] T ∈ R 3 .
The thrust force is represented by F T i . The rotation matrix R i from the body-fixed frame to the inertial frame is with the sequence of roll-pitch-yaw, thus, we obtain the translational dynamics as follows Ẍi = (sin ψ i sin φ i + cos ψ i cos φ i sin θ i )

F T i m Ÿi = (cos φ i sin ψ i sin θ i -cos ψ i sin φ i ) F T i m Zi = -g + (cos θ i cos φ i ) F T i m (1)
where m represents the mass of a quadrotor and g represents the gravity.

Let us denote

T i =   1 0 -sin θ i 0 cos φ i cos θ i sin φ i 0 -sin φ i cos θ i cos φ i   and Ti =   tan θ i 0 cos θ i + tan θ i sin θ i 0 -cos θ i 0 sec θ i 0 tan θ i  
We can rewrite the rotational dynamics as follows

  φi θi ψi   =(JT i ) -1 τ i + Ti •   φi θi φi ψi θi ψi   + (JT i ) -1 S T   T i •   φi θi ψi     JT i •   φi θi ψi   (2)
The dynamics of a quadrotor can be generally divided into two parts, namely, the translational dynamics (1) in outer-loop, and the rotational dynamics (2) in inner-loop respectively.

B. Attitude control

Since the attitude angles and the angular velocities are measurable, the torque vector τ i is given as follows

τ i = JT i τi -JT i Ti   φi θi φi ψi θi ψi   -S T T i • Θi JT i • Θi (3)
where τi = Θd i -

k 2Θ i ε ( Θi -Θd i ) - k 1Θ i ε 2 (Θ i -Θ d i ) (4)
k 2Θ i ε ( Θi -Θd i ) - k 1Θ i ε 2 (Θ i -Θ d i ) (5)
Then, the attitude angles in Θ i can track Θ d i exponentially. The converging speed is decided by the gain matrices k 1Θ i and k 2Θ i . Let us denote e Θ i = Θ i -Θ d i and ẽΘ i = εe Θ i , then, we can rewrite (5) as follows

ε d dt e Θ i ėΘ i = 0 3×3 I 3 -k 1Θ i -k 2Θ i e Θ i ėΘ i (6)
If we define dt/dt = 1/ε, then, we have

d εe Θ i ε ėΘ i T dt = d e Θ i ėΘ i T dt
such that the dynamics of the attitude errors in ( 6) can be represented in the time scale t as follows.

d e Θ i (t) ėΘ i (t) T dt = 0 3×3 I 3 -k 1Θ i -k 2Θ i e Θ i (t) ėΘ i (t) (7)
It is not difficult to verify that the origin of ( 7) is exponentially stable, such that we obtain

e Θ i (t) ėΘ i (t) = exp 0 3×3 I 3 -k 1Θ i -k 2Θ i t e Θ i (t 0 ) ėΘ i (t 0 ) (8)
The initial value t0 = 0 is defined at t = t k , where t k is an arbitrary time instant in time scale t. Then the new time variable satisfies t = (tt k )/ε. Then we obtain t = t k + ε t.

If ε is sufficiently small, the variable t slowly varies in time scale t. Intuitively, the time variable t is not "sensitive" to the change of t because of the small ε. Since

0 3×3 I 3 -k 1Θ i -k 2Θ i is negative definite, there exists a finite time ta in time scale t such that exp 0 3×3 I 3 -k 1Θ i -k 2Θ i
t converges to a small neighborhood Ω(e Θ i , ėΘ i ) of the equilibrium point e Θ i ėΘ i = 0 6 . This convergence dose not depend on the time instance t k and the translational states X i (t k ). Thus, the equilibrium point of system ( 7) is exponentially stable, uniformly in (t, X i (t),Y i (t)).

We recall that the torques in τ i and the total thrust force F T i are generated by the thrusts of the four propellers of the quadrotor. In practice, the propellers have limit power.

According to [START_REF] Kendoul | Real-time nonlinear embedded control for an autonomous quadrotor helicopter[END_REF], in order to prevent τ i from hitting the input saturation, the terms Θ d i , Θd i and Θd i should be bounded. Additionally, we require that the absolute values of the desired pitch and roll angles are smaller than π/2.

C. Altitude control

In this work, the desired altitude Z d i of each UAV is constant. In other words, the formation takes place in o e x e y e plan. The thrust force is given as follows

F T i = mg + m • u Z i cos θ i cos φ i (9)
where u Z i represents the altitude controller. Substituting F T i in (1), we obtain

Ẍi = sin ψ i tan φ i cos θ i + cos ψ i tan θ i (u Z i + g) Ÿi = sin ψ i tan θ i -cos ψ i tan φ i cos θ i (u Z i + g) Zi = u Z i (10)
We observe from [START_REF] Hou | Distributed leader-follower formation control for multiple quadrotors with weighted topology[END_REF] that the altitude control is decoupled with the planar translational dynamics (X i and Y i ). Thus, we give the altitude controller as follows

u Z i = σ b (-k 2Z Żi -k 1Z (Z i -Z d i )) (11)
Function σ b (•) represents a standard saturation function.

σ b (a) = sgn(a) min{b, |a|} (12)
where "sgn" represents the sign function. We select b = 1. The controller (11) asymptotically stabilizes the altitude. Since the altitude control is decoupled with the planar translational dynamics, the convergence of Z i do not depend on the other states of the quadrotors except Z i and Żi . When the altitude of the quadrotors gets stabilized, u Z i ≈ 0. III. FORMATION CONTROLLER DESIGN Since the planar translational motions are generated by the attitude angles, the formation controller is to obtain the proper desired attitude angles Θ d i . If we design the desired attitude angles as follows

θ d i = arctan u X i g φ d i = arctan -u Y i cos(arctan(u X i /g)) g ψ d i = 0 (13)
where u X i and u Y i represent the formation controllers in direction x e and y e in the inertial frame. Then, the planar translational dynamics of UAV i yields

Ẍi =u X i + δ X i Ÿi =u Y i + δ Y i (14)
The terms δ X i and δ Y i have the following expression.

δ X i = (g + u Z i )• sin ∆ψ i • tan(φ d i + ∆φ i ) cos θ d i + ∆θ i + cos ∆ψ i • tan θ d i + ∆θ i - g g + u Z i tan θ d i δ Y i = (g + u Z i )• -cos ∆ψ i • tan(φ d i + ∆φ i ) cos(θ d i + ∆θ i ) + sin ∆ψ i • tan θ d i + ∆θ i + g g + u Z i tan φ d i cos θ d i
where ∆φ i , ∆θ i and ∆ψ i represent the tracking error of the attitude angles

Θ i -Θ d i = [∆φ i , ∆θ i , ∆ψ i ].
We can observe that δ X i and δ Y i are in terms of u Z i , and

Θ i -Θ d i .
According to (8), the attitude tracking error Θ i -Θ d i is bounded (since Θ d i is bounded) and exponentially converges to the origin. Additionally, |u Z i | ≤ 1 and u Z i → 0 when the altitude is stabilized. Thus, we obtain that δ X i and δ Y i are bounded.

A. Leader-Follower formation of UAVs

In this paper, an L-F formation is considered. The indices of the UAVs compose a set V = {1, 2, . . . , n}, where n is the number of the UAVs in the formation. The subset V L ⊆ V represents the indices of the leaders, therefore, V -V L represents the set of followers.

Firstly, we define the "formation task" for a multiquadrotor system as follows.

Definition 1 (Formation task): A formation task for a multi-quadrotor system with L-F architecture is represented by a desired formation trajectory (given to the leader(s)) and a desired geometric pattern (desired inter-distance and orientation between neighboring quadrotors) for the group of quadrotors.

The formation task describes the desired integral behaviors of the multiple quadrotors. The objective of the formation control is to accomplish the formation task, i.e., the quadrotors keep the desired pattern and track a given trajectory by using the formation controllers.

We consider the planar formation of UAVs. The desired altitude is given constant. We denote by x i = [X i ,Y i ] T and ẋi = [ Ẋi , Ẏi ] T the planar position and velocity vectors for UAV i. Each UAV can obtain the relative positions and velocities with respect to its neighbors, which can be represented by vectors [(x ix j ) T , ( ẋiẋ j ) T ] T , j ∈ N i . If the UAV is a leader, besides the foregoing measurements, it can also obtain the relative position and velocity with respect to the formation trajectory [(x ir(t)) T , ( ẋiṙ(t)) T ] T , where we denote by r(t) = [r X (t), r Y (t)] T the reference formation trajectory (RFT).

The rigid formation of quadrotors are considered in this paper. Thus, the formation controller is designed to guarantee that all the quadrotors track the RFT with some constant biases

d i0 = [d X i0 , d Y i0 ] ∈ R 2
, such that the quadrotors keep a constant formation pattern. Therefore, the desired trajectory for each UAV should satisfy x d i (t)r(t) = d i0 and ẋd i (t)ṙ(t) = 0, then, we obtain

x d i (t) = d i0 + r(t) and ẋd i (t) = ṙ(t)
An example of four UAVs with rigid formation task is shown in Fig. 1. However, the RFT r(t) is not available for the followers, therefore, the desired trajectory x d i (t) for UAV i is not explicitly available. The behavior of each UAV depends on its neighbors states (and r(t), if it is a leader), then, the formation task is finally achieved. The bias with respect to the RFT is attained implicitly by the constant inter-distances between a UAV and its neighbors. Then, the formation problem becomes: how to find the available desired trajectory for UAV i ∈ V.

Let us make a sum of the relative position state vectors. Note that we drop the explicit expression of time in the related terms for the sake of simplicity.

∑ j∈N i (x i -x j -d i j ) if i ∈ V -V L ∑ j∈N i (x i -x j -d i j ) + x i -r -d i0 if i ∈ V L (15)
The inter-distance is given by d i j = d i0 -d j0 . Then, equations (15) can be rewritten as follows

∑ j∈N i (x i -r -d i0 -(x j -r -d j0 )) if i ∈ V -V L ∑ j∈N i (x i -r -d i0 -(x j -r -d j0 )) + x i -r -d i0 if i ∈ V L
We introduce the available desired trajectory for each UAV as follows

xd i =      1 |N i | ∑ j∈N i (x j + d i j ) if i ∈ V -V L 1 |N i +1| ∑ j∈N i (x j + d i j ) + r + d i0 if i ∈ V L
(16) we then observe that xd i is available for UAV i. We rewrite equation (15) in matrix form for all the quadrotors as follows

   x 1 -xd 1 . . . x n -xd n    = (G ⊗ I 2 )    x 1 -x d 1 . . . x n -x d n    (17)
where G ∈ R n×n represents the normalized interaction matrix (see [START_REF] Hou | Distributed leader-follower formation control for multiple quadrotors with weighted topology[END_REF]). The symbol ⊗ represents the Kronecker product. The formation task is achieved if G is invertible and for each UAV i ∈ V, x ixd i → 0 asymptotically. According to [START_REF] Hou | Distributed leader-follower formation control for multiple quadrotors with weighted topology[END_REF], G is invertible if the graph of the multi-UAV system is connected and at least one leader exists. In this paper, we assume that this condition is satisfied. In the following subsection, we will investigate the formation controller which stabilizes the formation error x ixd i → 0.

B. Formation control

We firstly consider the nominal model of (14) by setting δ X i and δ Y i null. The dynamics of X i and Y i are similar, thus, we consider the dynamics of X i for example. Note that in the sequel, the superscript "X" is omitted for the sake of simplicity. Then, we have

Ẍi = u i (18)
Let us denote by e iX = X i -Xd i the formation error in x e direction. Let us define a nonlinear function ρ i : R 2 → R. We propose the formation controller as follows

u i = -M tanh (k 2 ėiX + k 1 e iX ) -M tanh(ρ i (e iX , ėiX )) + Ẍd i ρ i (e iX , ėiX ) = k N ėiX (19)
where M represents a positive constant scalar. k 1 and k 2 are two positive constant gains. The symbol k N represents a positive nonlinear gain. For example, we can select k N as follows

k N = η 1 exp -η 2 e 2 iX ( 20
)
where η 1 ≥ 0, η 2 > 0. The selection of k N in (20) has a physical meaning. When the formation error e iX is large, the effect of ρ i (e iX , ėiX ) is small. In contrary, when e iX approaches zero, the nonlinear gain k N increases, which can reduce the approaching velocity, such that the overshoot is small. Proposition 1: The formation controller u i (19) is bounded.

Proof: According to (16), the desired trajectory Xd i for UAV i satisfies

Xd i =      1 |N i | ∑ j∈N i (X j + d i j ) if i ∈ V -V L 1 |N i +1| ∑ j∈N i (X j + d i j ) + r X + d i0 if i ∈ V L
where d i j , d i0 ∈ R (recall that the subscript "X" has been omitted here) represent some constant offset scalar. Then,

Ẋd i =      1 |N i | ∑ j∈N i Ẋj if i ∈ V -V L 1 |N i +1| ∑ j∈N i Ẋj + ṙX if i ∈ V L Let us denote by ūi = k 2 ėiX + k 1 e iX . Then, if i ∈ V -V L , Ẍd i = 1 |N i | ∑ j∈N i -M tanh ū j -M tanh ρ j + Ẍd j such that Ẍd i - 1
|N i | ∑ j∈N i Ẍd j = - 1 |N i | ∑ j∈N i (M tanh ū j + M tanh ρ j ) if i ∈ V L , Ẍd i = 1 |N i + 1| ∑ j∈N i -M tanh ū j -M tanh ρ j + Ẍd j + rX such that Ẍd i - 1 |N i + 1| ∑ j∈N i Ẍd j = - 1
|N i + 1| ∑ j∈N i (M tanh ū j + M tanh ρ j ) -rX
Without loss of generality, we assume that UAVs 1 ∼ i are leaders, while i + 1 ∼ n are followers. Then, we rewrite the foregoing equations for all the quadrotors in matrix form as follows

   Ẍd 1 . . . Ẍd n    = G -1 •                  -1 |N 1 +1| ∑ j∈N 1 (M tanh ū j + M tanh ρ j ) -rX . . . -1 |N i +1| ∑ j∈N i (M tanh ū j + M tanh ρ j ) -rX -1 |N i+1 | ∑ j∈N i+1 (M tanh ū j + M tanh ρ j ) . . . -1 |N n | ∑ j∈N n (M tanh ū j + M tanh ρ j )                  (21)
The RFT is usually selected such that its derivatives are bounded. Then, we observe that Ẍd i , i ∈ V are bounded, since the function tanh(•) is bounded by 1. Therefore, we conclude that u i , i ∈ V are bounded.

Substituting (19) into the first equation in (18), we obtain

ëiX = -M tanh ūi -M tanh ρ i (22)
Proposition 2: The origin of ( 22) is globally asymptotically stable, if i) k N is given by (20); ii) the gains in ūi satisfy

k 1 ≥ η 1 k 2 M.
Proof: Let us define a continuously differentiable, radially unbounded positive-definite function as follows

V i = ln cosh(k 2 ėiX + k 1 e iX ) + k 1 2M ė2 iX (23)
V i = 0, if and only if e iX = 0 and ėiX = 0. Then, the derivative of

V i yields Vi = tanh ūi • ui + k 1 M ėiX ëiX = tanh ūi (k 2 ëiX + k 1 ėiX ) + k 1 M ėiX (-M tanh ūi -M tanh ρ i ) = tanh ūi (k 2 (-M tanh ūi -M tanh ρ i ) + k 1 ėiX ) -k 1 ėiX (tanh ūi + tanh ρ i ) = -k 2 M tanh 2 ūi -k 2 M tanh ūi tanh ρ i -k 1 ėiX tanh ρ i (24)
Then, we have

Vi ≤ -k 2 M tanh 2 ( ūi ) -k 1 ėiX tanh ρ i + k 2 M| tanh ūi || tanh ρ i |
According to (19), ρ i has the same sign as ėiX . Then, -k 1 ėiX tanh ρ i ≤ 0.

• Case 1:

If |ρ i | ≤ | ūi |, | tanh ρ i | ≤ | tanh ūi |. Then, | tanh ρ i || tanh ūi | ≤ tanh 2 ūi . Therefore, Vi ≤ -k 1 ėiX tanh ρ i ≤ 0 (25)
We obtain that Vi is semi-definite negative. We then invoke here the LaSalle's invariance principle. Let us compute the largest invariant set where Vi = 0, such that equation (24) equal to zero. We consider the following cases.

-Case a: if ėiX = 0, then, according to (25), Vi < 0, which contradicts Vi = 0. -Case b: if ėiX = 0, then, according to (24), Vi = -k 2 M tanh 2 (k 1 e iX ) = 0, which implies e iX = 0. Therefore, in Case 1, the largest invariant set contains only the origin.

• Case 2: If |ρ i | > | ūi |, |ρ i | > | tanh ūi | ≥ 0. Since k 1 ≥ η 1 k 2 M, then, we have k 2 M| tanh ūi | < k 1 | ėiX |. Thus, Vi ≤ -k 2 M tanh 2 ūi ≤ 0 (26)
We obtain that Vi is semi-definite negative. As mentioned before, we compute the largest invariant set where Vi = 0, such that equation (24) equal to zero. We consider the following cases.

-Case a: if | ūi | = 0, then, according to (26), Vi < 0, which contradicts Vi = 0. -Case b: if | ūi | = 0, then, according to (24), Vi = -k 1 ėiX tanh ρ i = 0, which implies ėiX = 0. Since ūi = 0, we obtain that e iX = 0. Therefore, in Case 2, the largest invariant set contains only the origin. Since the largest invariant set contains only the origin, then, according to the LaSalle theorem, the origin of the system (22) is globally asymptotically stable.

Remark 1: The decoupled property of X and Y dynamics permits us to design the formation controller separately, the design procedure of u Y i is the same as u X i , such that Let us reconsider the terms δ X i and δ Y i in (14) caused by the tracking error of the attitude angles. We introduce our main result in the following theorem.

u Y i = -M tanh(k 2 ėiY + k 1 e iY ) -
Theorem 1: Let G be the interaction matrix of an L-F formation of quadrotors with constant topology. The formation controllers are given in ( 19) and ( 27). The attitude is controlled by [START_REF] Saska | Autonomous deployment of swarms of micro-aerial vehicles in cooperative surveillance[END_REF]. The altitude is controlled by [START_REF] Chen | Composite nonlinear feedback control for linear systems with input saturation: theory and an application[END_REF] where u Z i is given in (11). Then, e iX and e iY converge to zero asymptotically, if i) G is invertible, ii) the initial velocity of each UAV is finite.

Proof: The terms δ iX and δ iY are in terms of the tracking errors of the attitude angles (∆φ i , ∆θ i and ∆ψ i ) and u Z i . According to (21), ( 19), ( 27) and (11), the controllers u X i , u Y i and u Z i are bounded. Then, according to (13), we know that θ d i , φ d i and ψ d i are bounded. The attitude angles are controlled by (3), then, ∆φ i , ∆θ i and ∆ψ i are bounded. Therefore, δ iX and δ iY are bounded.

We take e iX for example. Then, (22

) becomes ëiX = -M tanh ūi -M tanh ρ i + δ iX (28)
The derivative of the positive semidefinite function V i in (23) yields

Vi = tanh ūi • ui + k 1 M ėiX ëiX = tanh ūi (k 2 ëiX + k 1 ėiX ) - k 1 M ėiX (M tanh ūi + M tanh ρ i -δ iX ) = tanh ūi (k 2 (-M tanh ūi -M tanh ρ i + δ iX ) + k 1 ėiX ) -k 1 ėiX (tanh ūi + tanh ρ i + δ iX M ) = -k 2 M tanh 2 ūi -k 2 M tanh ūi tanh ρ i -k 1 ėiX tanh ρ i + k 2 tanh ūi δ iX - k 1 M ėiX δ iX ≤ -k 2 M tanh 2 ūi -k 2 M tanh ūi tanh ρ i -k 1 ėiX tanh ρ i + (k 2 | tanh ūi | + k 1 M | ėiX |)|δ iX |
Since the states of a linear system will not diverge to infinite within finite time interval with bounded control input, then, if the initial condition is in the compact set {(e iX (t 0 ), ėiX (t 0 ))| ėiX (t 0 ) < ∞}, we obtain that ėiX is bounded in finite time interval [t 0 ,t 1 ), where t 1 < ∞. As analyzed in section II-B, the rotational dynamics of a quadrotor is in the fast time scale t with controller (4). Then, there exists a finite time ta t 1 such that the attitude errors e Θ i enter the neighborhood of the origin, which renders |δ iX (t a )| ≤ ζ , where ζ is a scalar. Then, for t > ta , we have

k 2 | tanh ūi | + k 1 M | ėiX | |δ iX | ≤ |k 2 M tanh 2 ūi + k 2 M tanh ūi tanh ρ i + k 1 ėiX tanh ρ i | (29)
Then, Vi ≤ 0, when t > ta . Therefore, the semi-global asymptotic stability of the origin of system (28) is derived, when t > ta .

Remark 3: In theorem 1, if the condition (29) is satisfied when ta = t 0 , the semi-global stability of the system (28) is obtained.

IV. SIMULATION AND EXPERIMENTAL RESULTS

Heudiasyc laboratory has developed a PC-based simulatorexperiment framework for controlling a quadrotor and also a flock of quadrotors. The programs (written in C++) running in the UAVs are the same, both in the simulator and in the embedded processors of real UAVs. When we realize the real-time experiment, the PC acts as a ground station, which is responsible for displaying and sending instructions such as taking off and landing. The UAVs are all autonomous. The formations with and without the CNF are shown in Fig. 2 and Fig. 3 respectively. In this test, the formation controllers (19) and ( 27) are simplified by setting Ẍd i = 0 and Ÿ d i = 0. We observe that in both formations, the quadrotors are able to converge to the desired positions with hyperbolic tangent function-based controller. However, after adding CNF, the performance is greatly improved.

The foregoing tests validated by using the simulator are carried out in the real-time experiments. The output curves are shown in Fig. 4. We observe that the formation with the CNF controller (on the right) has small overshoot and rapid response. The corresponding video is available on the site In this paper, the CNF based bounded formation controller is proposed. The hyperbolic tangent function is used to generate a differentiable formation controller. The simulation and the experimental results show that the CNF based formation controller with hyperbolic tangent function have better performance than a controller without CNF and a controller with a standard saturated function.

Fig. 1 .

 1 Fig. 1. Rigid formation task for four UAVs, where UAV 1 is a leader. The objective is to track the trajectory r(t) with biases d 10 = [-1, 1] T , d 20 = [-1, -1] T , d 30 = [1, -1] T and d 40 = [1, 1] T .

Fig. 2 .

 2 Fig. 2. Formation of four quadrotors without CNF

Fig. 3 .

 3 Fig. 3. Formation of four quadrotors with CNF

Fig. 4 .

 4 Fig. 4. Real-time formation of four quadrotors. Left: without CNF; Right: with CNF https://youtu.be/tDBiRAGp6r0 V. CONCLUSION

  M tanh ρ i (e iY , ėiY ) + Ÿ d i (27) Remark 2: The desired attitude angles for each UAV are obtained by substituting (19) and (27) into (13).

	Owing to the
	use of the hyperbolic tangent function, u X i and u Y i are high-order differentiable, such that the derivatives θ d i , θ d i and φ d i , φ d i are bounded.


Ibanda Paulin

Kabaka

Paulin Ibanda

come

La promotion de la parité hommes-femmes dans l'accès à l'encadrement supérieur de la fonction publique d'Etat

La promotion de la parité hommes-femmes dans l'accès à l'encadrement supérieur de la fonction publique d'Etat

Auteur : IBANDA KABAKA Paulin, Doctorant en Droit public Mail : ibandapaulin@yahoo.fr Il y a toujours eu un problème d'égalité entre les hommes et les femmes dans l'accès aux postes d'encadrement de la fonction publique d'Etat.

Dès lors, faire progresser la parité entre les hommes et les femmes dans toutes les sphères de la vie nationale devrait s'inscrire dans le cadre des actions à mettre en place par tout gouvernement recherchant le respect les droits de l'Homme dans son ensemble. C'est dans ce cadre que le Gouvernement AYRAULT 1 a mis en place un certain nombre des dispositifs légaux et réglementaires afin de promouvoir l'égal accès des femmes aux postes d'encadrement de la haute fonction publique (dans ces 3 versants : Etat, collectivités territoriales, hospitalière).

En effet, la notion de parité constitue le fondement des politiques de lutte contre les inégalités entre les hommes et les femmes. L'émancipation économique et sociale des femmes et la promotion de la parité des sexes sont deux conditions essentielles à l'avènement d'un développement économique et social en faveur de toutes les couches de la population.

Dans le cadre de cet article, nous sommes amené à tabler sur le bilan de la situation actuelle et des étapes de la démarche mise en place dans un premier temps puis d'analyser les actions à mettre en place, y compris les obstacles susceptibles de les contrarier dans le second temps.

BILAN DE LA SITUATION ACTUELLE ET ETAPES DE LA DEMARCHE

Bien qu'inscrite dans le Bloc de Constitutionnalité au titre de la Déclaration universelle des droits de l'homme et du citoyen, l'égalité entre les hommes et les femmes a du mal à être instaurée dans la haute fonction publique de la France, notre pays. Afin d'analyser les actions mises en oeuvre, un bilan ainsi que l'identification des étapes de l'égal accès des femmes aux postes d'encadrement de la haute fonction publique s'imposent. Ceci montre la détermination des pouvoirs publics français à matérialiser l'égalité des femmes dans l'accès à la haute fonction publique au titre de l'exemplarité dont l'Etat dont l'Etat doit être le modèle à suivre.

Pour matérialiser ces objectifs chiffrés dans le temps, plusieurs mesures ont été proposées par le Gouvernement.

ACTIONS A METTRE EN PLACE ET OBSTACLES A REDOUTER

Concernant la partie active en vue de la promotion de l'égalité hommes-femmes dans la haute fonction publique, il y a lieu de parler des mesures à prendre (A) et des obstacles susceptibles de les freiner(B).

A. MESURES A METTRE EN PLACE

Sous l'égide de la Ministre ayant dans ses attributions le droit des femmes, un plan d'action interministériel sur la période 2013-2017, faisant office de feuille de route du Gouvernement en matière d'égalité professionnelle, de la parité, de la protection des femmes contre les violences et de la lutte contre les stéréotypes du genre , a été mis en place.

Dans chaque ministère, un haut fonctionnaire en charge de l'égalité des droits devrait être nommé dès 2013. Il sera en charge, en collaboration avec le secrétariat général et les Ressources humaines, du suivi de l'égalité professionnelle entre les hommes et les femmes, en l'occurrence lors des nominations.

Enfin, des bilans semestriels et annuels évalueront les efforts réalisés par tous les ministères.

Par ailleurs, des sanctions financières ont été mises en place afin d'inciter toutes les Administrations à promouvoir cette égalité entre les hommes et les femmes. Pour toute nomination entravant les nouvelles règles, 30.000 euros d'amendes par cas constaté de 2013 à 2014, 60.000 euros de 2015à 2017 et 90.000 euros à partir de 2018.

En outre dans la composition des jurys et comités de sélection pour le recrutement ou la promotion des fonctionnaires, une proportion minimale de 40 % des personnes de chaque sexe devra être respectée dès le 1 er janvier 2015.

Enfin, nous rappelons que tous les textes législatifs et règlementaires devraient dorénavant procéder à une étude de leur impact sur l'égalité hommes-femmes.

Au titre d'autres mesures à prendre, le Comité de pilotage à l'égal accès des femmes et des hommes aux emplois supérieurs de la fonction publique a proposé notamment : de constater les inégalités avec des tableaux statistiques, de développer une stratégie de mise en oeuvre de la logique paritaire (cfr plan gouvernemental 2013-2017),de stimuler la prise en compte de la logique paritaire dans l'action des administrations centrales et déconcentrées par la désignation d'un délégué interministériel et des coordonnateurs ministériels et par le développement des formations à l'égalité , et enfin de suivre l'application des mesures et évaluer leur efficacité.

Néanmoins, certains observateurs ont relevé quelques obstacles de nature à entraver l'efficacité de telles mesures.

B .OBSTACLES A SURMONTER

Sur le chemin de la réalisation de l'égal accès des femmes aux postes supérieurs de la fonction publique, il y a certains obstacles à surmonter selon l'avis des observateurs au nombre desquels il faut citer la volonté politique et les sanctions financières mis en place.

S'agissant de l'absence de la volonté politique forte et permanente, il convient de rappeler que la lutte pour l'égalité professionnelle des 2 sexes et notamment des femmes vient de loin et a toujours souffert des stéréotypes.

D'où il faut en permanence la présence d'une volonté politique forte afin de contraindre les différents décisionnaires publics chargés du recrutement et des nominations de tenir compte de cette parité. Ainsi toute absence de volonté politique affichée en cette matière serait un frein à la réalisation de cet objectif dans un contexte réversible des situations.

En ce qui concerne la mise en oeuvre des sanctions financières, cela est de nature à pénaliser les Administrations qui commettront des manquements dans l'application de différents quotas temporels. Néanmoins, il est à craindre, comme le stigmatise le Député TOURRET, une préférence au paiement de l'amende à récupérer sur une hausse d'impôts que le respect de l'application de la parité. Ainsi, une sanction dissuasive de type annulation de toutes les nominations en cause ferait réfléchir plus d'un décideur public.

  que 10 % à le faire, soit plus du quart des femmes contre le dixième des fonctionnaires hommes. Au terme de ce bilan sombre, le Gouvernement français, afin de pallier à cette situation dramatique concernant le droit des femmes à l'égalité, a mis en place des objectifs à atteindre par phases successives. Nous parlerons à présent de ces phases, disons de ces étapes . B. ETAPES DE LA PROMOTION DE L'EGALITE ENTRE LES SEXES DANS LES POSTES D'ENCADREMENT DE LA FONCTION PUBLIQUE D'ETAT La promotion de l'égal accès des femmes aux postes d'encadrement de la haute fonction publique a été entreprise au travers de 2 prismes à la fois juridique et temporel. Au plan juridique, la Loi N° 2012-347 du 12 mars 2012 relative à l'accès à l'emploi titulaire , aux agents contractuels, et à la lutte contre les discriminations dans la fonction publique, qui a rétabli l'article 6 de la Loi de 1983 tablant sur les droits et obligations des fonctionnaires ainsi que ces Décrets d'application pris en 2012 constituent une grande avancée dans la réalisation de la parité hommes et femmes dans la haute fonction publique en ce qu'ils instituent des critères chiffrés.

	A. BILAN DE L'ACCES DES FEMMES AUX POSTES D'ENCADREMENT DE LA
	FONCTION PUBLIQUE D'ETAT
	Le bilan de la mixité des femmes et des hommes dans l'accès aux postes supérieurs de la
	fonction publique d'Etat est mitigé.
	En effet, les femmes restent minoritaires dans les emplois d'encadrement supérieur et de
	direction de la fonction publique d'Etat. Au 31 décembre 2010, mis de coté les enseignants,
	les femmes ne représentent que 36 % des cadres supérieurs (A+).

Il convient de relever que les corps et emplois d'encadrement et de direction ne comptent que 25% des femmes et 16 % s'agissant des corps et emplois de décision.

Par ailleurs, les femmes occupent plus souvent des emplois à temps partiel dans le 3 versants de la fonction publique. Ainsi, 27 % des femmes travaillent à temps partiel au moment où les hommes ne sont Le décret du 30 avril 2012 relatif aux modalités de nominations équilibrées dans l'encadrement supérieur de la fonction publique est une grande avancée. En effet, ce Décret institue l'obligation des nominations équilibrées des hommes et des femmes dans les emplois supérieurs de l'Etat, des collectivités territoriales et des hôpitaux.

Ensuite ce texte est suivi de plusieurs circulaires dont celle relative à l'étude d'impact sur la parité hommes-femmes lors de l'élaboration des lois et règlements.

Au plan temporel, dans ses Décrets et circulaires d'application pris en 2012, le Premier

Ministre a mis en place des objectifs à atteindre dans le temps et ce, dès le 1 er janvier 2013. de ce fait, les nominations dans les plus hauts postes de la fonction publique de l'Etat, des collectivités territoriales (pour les communes, seules celles de plus de 80 000 habitants sont concernées) et des hôpitaux et assimilés, doivent concerner 20 % des personnes de chaque sexe en 2013, au moins 30 % à partir de 2015 et 40 % dès 2018.

Des bilans semestriels et annuels seront présentés en Conseil des ministres et publiés sur le site du Gouvernement.


Jean Serra
email: jean.serra@esiee.fr

B Ravi Kiran

Digitization of partitions and tessellations

Keywords: Tessellations, Regular sets, Hierarchies, Khalimsky topology, Simplicial complexes, 3-D grids

We study hierarchies of partitions in a topological space where the interiors of the classes and their frontiers are simultaneously represented. In both continuous and discrete spaces our approach rests on tessellations whose classes are R-open sets. In the discrete case, the passage from partitions to tessellations is expressed by the Alexandrov topology and yields double resolutions. A new topology is proposed to remove the ambiguities of the diagonal configurations. It leads to the triangular grid in Z 2 and the centered cubic grid in Z 3 , which are the only translation invariant grids which preserve connectivity and permit the use of saliency functions.

Introduction

When a set is partitioned, the frontiers between classes are not explicitly addressed, while the operations on these frontiers might not trivial. Does the frontier between two classes belong to one of them, to both, or to none? How does one combine set interiors and frontiers in a unique representation? This is the focus of the current study. When one goes up in a hierarchy of partitions, the frontier elements which disappear are only those separating classes, e.g. the two medians in Fig. 1b, and not the barbs of Fig. 1c. How does one differentiate between these two cases? An answer is given by the notion of tessellation (section 3).

Preserving connectivity within classes may also be troublesome. How does one merge the squares of Fig. 1a? Must we firstly link the "2"s, or rather the "8"s ? In 2D, the classical digital approach focuses on the boundaries, which are usually supposed to be Jordan curves [START_REF] Kronheimer | The topology of digital images[END_REF][START_REF] Rosenfeld | Digital topology[END_REF]. One could also constructs "well composed set", whose boundaries have no diagonal configurations [START_REF] Latecki | Well-composed sets[END_REF].

In this study, our intuition is based on the fact that the classes themselves, and not their boundaries, would provide a more convenient input to the present problem. We will see that Jordan curves are totally useless in what follows, though the particular structure of the classes (R-open sets) is crucial.

Image processing rests either on Euclidean background, or on the digital one, but the problem of the frontiers in a partition is set upstream this distinction, and its solution will apply to both continuous and discrete models. In the second case Khalimsky topology is a convenient starting point, for it identifies Z n with Euclidean n-cubes [START_REF] Bertrand | Completions and simplicial complexes[END_REF][START_REF] Mazo | Paths, homotopy and reduction in digital images[END_REF]. It involves simplicial complexes which lead to double resolution techniques [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF][START_REF] Cousty | Some morphological operators in graph spaces[END_REF][START_REF] Kiran | Fusion of ground truths and hierarchies of segmentations[END_REF] (section 5). But it does not preserve connectivity (see Fig. 1a), unlike the topological variant developed in section 6.

Lattice of the regular open sets (reminder)

Let E be a set equipped with a (non necessarily separated) topology, and G be the class of its open sets. G is a complete lattice, but not complemented. Now, the notion of a complement is essential, and this orients us toward the family R = R(E) of the regular open sets of E. An open set B is said to be regular, or R-open, when it does not change when one takes its adherence B, and then one takes the interior of the latter, i.e. B = (B) • . It is the case of Fig. 1b for example, but not of Fig. 1c. 3 . The main result about R is the following theorem [START_REF] Rikker | Les treillis compacts[END_REF][START_REF] Heijmans | Morphological Image Operators[END_REF][START_REF] Ronse | Regular open or closed sets[END_REF]: Theorem 1. R is a complete lattice for the inclusion ordering, where the supremum and the infimum are given by

∨B i = (∪B i ) • ; ∧ B i = (∩B i ) • . ( 1
)
Lattice R is completely distributive and with unique complement

complB = ( B) • . ( 2
)
Here the symbol designates the set complement operator. For example, in the two Fig. 4a andb, the complement of each class is the supremum, in R, of the three other ones.

Tessellations

A "tessellation" is a partition of a topological space where both interiors and their boundaries are classes [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]: Definition 1. We define a tessellation τ of a topological space E as any family {B i , i ∈ I} of disjoint open sets called "classes":

τ = {B i , i ∈ I} with i = j ⇒ B i ∩ B j = ∅ (3)
such that the union of all B i and of all boundaries F r(B i , B j ) = B i ∩ B j covers the space E:

E = ∪{B i , i ∈ I} ∪ {B i ∩ B j , i, j ∈ E, i = j}, (4)
We will designate by N (N for "net") the set ∪{B i ∩ B j , i, j ∈ E, i = j} of all boundaries between classes. In [START_REF] Matheron | Eléments pour une théorie des milieux poreux[END_REF], p.156-157, he builds a σ-algebra of regular closed sets and proves a series of characteristic properties; in [START_REF] Matheron | Random Sets and Integral Geometry[END_REF] he associates a random set to every pair (A • , A), A ∈ P(E); in [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF] he interprets the regularization operator as a strong morphological filter, and gives a middle element between (A) • and (A • ) • . For his part, Ch. Ronse shows in [START_REF] Ronse | Regular open or closed sets[END_REF] that any complete boolean lattice is isomorphic to a lattice of regular open sets, and indicates as a watermark that the associated topology is Alexandrov.

Tessellations and R open sets

Besides, the set difference ∆ = S\B between S and B coincides with the difference between the boundaries F r(B) and F r(S): Proof. We prove the theorem in the negative, by showing that if B i = (B i ) • = S i , then the B i do not generate a tessellation. We firstly observe that the B i are disjoint iff the corresponding R-open sets S i are disjoint. We have

∆ = S\B ⇔ F r(S) = F r(B)\∆, ( 6
B i ∩ B j = ∅ ⇔ B i ∩ B j = ∅ ⇒ B i ∩ (B j ) • = ∅ = B i ∩ S j ⇒ S i ∩ S j = ∅
as well as the inverse implication, since S i ⊇ B i , ∀i. Besides, we have, from Rel. [START_REF] Fedorov | A Course in Crystallography[END_REF], ∪{B i ∩ B j , i, j ∈, i = j} = ∪{S i ∩ S j , i, j ∈, i = j} so that the S i form a tessellation of E. If there exists one B i at least which is strictly included in S i then z ∈ S i \ B i does not belong to any B i or to any boundaryB i ∩ B j since S i is open. Therefore the B i do not cover set E, which achieves the proof.

All in all, just as a partition of E is a family in P(E) whose each element is the complement of the union of all the others, a tessellation of E is a family in R(E) whose each element is the complement of the supremum of all the others, both complement and supremum being taken in R.

The algebraic closing B → S = (B)

• fills up the fine fissure, isthmuses and the point lacunae of B. However, some separations, too narrow, may not be filled up. Take for example, B composed of two disjoint open squares of R 2 whose adherence share one vertex only, then the adherence B 1 ∪ B 2 joins the two squares, but the interior (B 1 ∪ B 2 ) • separates them again.

In the literature, an example of tessellation is given by the clefts in the perfect fusion graphs of J. Cousty and G. Bertrand [START_REF] Cousty | Uniqueness of the perfect fusion grid on z d[END_REF]. Theorem 2 reminds us of Jordan's one, though it is true in any topological space, and it does not focus on the frontiers, but on the classes. In R 2 every Jordan curve induces a tessellation [START_REF] Kiran | Fusion of ground truths and hierarchies of segmentations[END_REF], but a tessellation into two open classes, even connected, can have a frontier which is not a Jordan curve. Fig. 4b depicts a digital contour which separates R-open sets and which is thick. Note also that connectivity is not involved in the above theorem, whereas it is essential in Jordan's one.

Structure of the tessellations

We now introduce a minimal tessellation τ 0 of the space E . The classes {s i } of τ 0 are called "the leaves", and are supposed in locally finite number. These leaves are indivisible R-open sets, i.e. each class of a larger tessellation contains one leave at least and is disjoint from those that it does not contain. The family T of all tessellations of E is obviously ordered by the following relation :

τ ≤ τ ⇔ S(x) ⊆ S (x) x ∈ τ 0 τ, τ ∈ T (7)
where S(x) (resp. S (x)) is the class of τ (resp. τ ) at point x. This ordering provides T with the structure of a complete lattice. More precisely, consider a set P of labels and the family {τ p , p ∈ P }: Proposition 1. The set T of all tessellations τ ≥ τ 0 of E forms a complete lattice for the ordering of Rel. [START_REF] Heijmans | Morphological Image Operators[END_REF], with universal elements τ 0 and E. The infimum of family {τ p , p ∈ P, τ p ≥ τ 0 } is the tessellation whose class at point x is the infimum, in R, of the classes of the τ p at point x, and the supremum is the smallest tessellation whose classes are suprema of the classes of the τ p in R.

Proof. Let x and y be two classes of τ 0 , and S p (x) (resp. S p (y)) be the class of τ p at point x (resp. y). We have to prove that {[∩S p (x)] • , x ∈ τ 0 } is a tessellation. If so, then this tessellation will be the greatest lower bound of the τ p , since on cannot find at point x an R-open class greater than [∩S p (x)] • and which is included in all S p (x). The point y ∈ S p (x) iff x ∈ S p (y); therefore, if y ∈ [∩S p (x)] then [∩S p (x)] = [∩S p (y)] and the two R-infima [∩S p (x)] • and [∩S p (y)] • are equal. If for some p the two sets S p (x) and S p (y) are disjoint, then a fortiori the R-infima [∩S p (x)] • and [∩S p (y)] • are also disjoint. Finally, as ∪{x, x ∈ τ 0 } ⊆ ∪{[∩S p (x)] • , x ∈ τ 0 }, and as ∪{x, x ∈ τ 0 } = E, the family {[∩S p (x)] • , x ∈ τ 0 } turns out to be a tessellation of E, and T is a complete inf-semi Lattice. But in addition T admits a greatest element, namely E itself, so that T is a complete lattice, which achieves the proof.

Hierarchies of tessellations

The tessellations met in image processing often form hierarchies, i.e. totally ordered closed sequences starting from the leaves and ending at E itself, considered as an R-open class.

One cannot merge the classes of a tessellation τ of the hierarchy by performing a simple union of their leaves, since the frontiers between adjacent leaves (i.e. with non-empty intersection of the adherences) would neither belong to classes, nor to the background net N which separates the classes. We must find out another law of composition. Consider a partition the totality of the leaves into J sub-sets B 1 , ..B j , ..B J , then

Proposition 2. The unique tessellation whose each class includes exactly one

B j , 1 ≤ j ≤ J has the R-open sets S j = (B j ) • , 1 ≤ j ≤ J as classes.
Proof. Theorem 2 shows that we must replace each B j with its R-open version S j for finding again a tessellation. Moreover, there is no tessellation {S j } which keeps disjoint the family {S j } and such that S j ⊃ S j ∀j. Such a strict inclusion would mean that one could find an open set containing x ∈ F r(S j ) ∩ S j , such that S j is not disjoint from S i , which is impossible.

The supremum and the infimum of a family of classes are those involved in the lattice R of the R-open sets. Consequently, in a hierarchy of tessellations, every point of the net N is absorbed by a class, sooner or later.

Connected classes and saliency function

Connectivity does not intervene in the paradigm of the hierarchies of tessellations. However the leaves are often connected, and the question of preserving the connectivity of the classes arises. Now this requirement is not always possible, neither in Euclidean topologies, nor in digital ones. Even when the leaves {s i } are connected, the R-open sets S j = (B j ) • of Prop. 2 may be not connected. One can also think of the example of the two open squares of R 2 whose adherences have only one point in common. They are connected, regular, their adherence is connected, but their union, though regular, is again not connected.

To overcome this issue, we have to specify the nature of topological space E, which is for now supposed to be locally arcwise connected, i.e. where the arcwise-connected components of an open set are open. Furthermore, we say that a pair of two regular sets S i and S j of E is strongly connected when the sets are adjacent (i.e. the intersection of their adherences is not empty) and when one can find a point x in their common frontier which is included in a small neighborhood δ(x) which itself is included in the union of their adherences,i.e.

S i ∩ S j = ∅ and ∃x ∈ S i ∩ S j | x ∈ δ(x) ⊆ S i ∪ S j . ( 8
)
Hierarchies of tessellations require this strong adjacency to transmit the connectivity from the leaves to their clusters into classes: Theorem 3. let E be a locally arcwise connected set, and τ 0 be a tessellation of E into R-open connected leaves {s i , i ∈ I} where every adjacent pair is strongly adjacency [START_REF] Khalimsky | Topological structures in computer science[END_REF]. The R-supremum of any finite sequence {s k , 1 ≤ k ≤ n} of leaves is then connected. Proof. Let S = ∨{s k , 1 ≤ k ≤ n} be the R-supremum of the family. From Prop. 2, S is the union of the {s k } and of the boundaries between pairs {s k , s l }. Consider two strongly adjacent leaves {s k , s l }. By strong adjacency, there exists a point x of the boundary s k ∩s l which has a neighborhood δ(x) ⊆ s k ∪ s l . As E is locally arcwise connected, there exists also a connected neighborhood δ ⊆ δ(x) which thus contains points of s k and of s l . Therefore the union s k ∪ s l ∪ F r(s k , s l ) is arcwise connected, and so is S, which achieves the proof.

In particular, the usual spaces R n and Z n are locally arcwise connected. Note that a same leave may appear several times in the sequence {s p , 1 ≤ p ≤ n}. When a hierarchy H with n levels τ p , 1 ≤ p ≤ n of tessellations satisfies the conditions of Theorem 3 then one can allocate a numerical value to each point of the net N 0 of the frontiers between the leaves of H. This function on N 0 , s say, indicates the level when the frontier element adjacent between two classes vanishes, and the classes merge. This is nothing but the classical saliency function [START_REF] Najman | Geodesic saliency of watershed contours and hierarchical segmentation[END_REF], here generalized, and without assuming that the boundaries are Jordan curves (in the case of R 2 ). When the conditions of Theorem 3 are not satisfied, as in Fig. 1a, the saliency function may be undefined at some crucial points. Finally, when the classes are possibly not connected, the saliency function may no longer summarizes exhaustively the hierarchy, as shown in Fig. 2.

Tessellations of Z n and Khalimsky spaces

The notion of a tessellation rests on R-open sets, and to apply it to Z n , we first need to provide a topology to this space.

Reminder on Khalimsky topology

E. Khalimsky topology clearly shows the analogies between the tessellations of R n and those of Z n . It was published in Russian in the sixties, but it is better known by more recent papers in English [START_REF] Khalimsky | Topological structures in computer science[END_REF]. It is just sketched here, but the reader will find a more detailed presentation in papers by E. Melin [START_REF] Melin | Digital surfaces and boundaries in khalimsky spaces[END_REF], L. Mazo et Al. [START_REF] Mazo | Paths, homotopy and reduction in digital images[END_REF], and the lecture notes of Ch. Kiselman [START_REF] Kiselman | Digital geometry and mathematical morphology[END_REF].

In 1937, P.S. Alexandrov introduced topological spaces E with smallest neighborhood (in short sn-topology), where it is assumed that the class of the open sets is closed under intersection [START_REF]Diskrete raüme rec. math[END_REF]. Khalimsky topology belongs to this category. In R, it associates the open interval ]m -1 2 , m + 1 2 [ with every pair m ≤ m of odd integers, and the closed interval [n -1 2 , n + 1 2 ] with every pair n ≤ n of even integers. The unions of open (resp. closed) intervals generate a non separated sntopology. When m = m and n = n then R is partitioned into unit intervals, and is thus connected. The product topology of n Khalimsky lines generates the topology in R n . When all coordinates of their centers are odd (resp. even), then the n-cubes are open (resp.closed), and the others n-cubes are said to be mixed.

In R 2 the Kovalevsky cells provide an equivalent approach, which allow us to display these topologies [START_REF] Kovalevsky | Finite topology as applied to image analysis[END_REF]. This structure is akin to the simplicial complexes [START_REF] Bertrand | Completions and simplicial complexes[END_REF], to fusion grids [START_REF] Cousty | Uniqueness of the perfect fusion grid on z d[END_REF] and to the planar graphs.

According to Theorem 2, in a Khalimsky space the tessellations are R-open sets, which simplifies the basic elements. In Z 2 for example, the isolated points and the pending edges are removed. The background net N is made of loops contouring the classes and where open edges and points alternate (see Fig. 3).

Khalimsky digital tessellations

The use of Khalimsky topology in digital image processing is classical [START_REF] Mazo | Paths, homotopy and reduction in digital images[END_REF][START_REF] Melin | Digital surfaces and boundaries in khalimsky spaces[END_REF]. In this section we indicate its links with the R-open sets and tessellations, and we show that this topology does not solve the question of the diagonal configurations. Khalimsky topology on Z is obtained by identifying each unit interval of R with the corresponding integer. The open intervals are obtained in the same manner from ]m -1 2 , m + 1 2 [ where m and m are odd and m ≤ m . In this topology Z is connected. The extension to Z n is made as previously with R n .

Interpret the points of a set X ⊆ Z 2 as points of odd coordinates in a Khalimsky plane K 2 which contains twice more points by line and twice more lines [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF][START_REF] Cousty | Some morphological operators in graph spaces[END_REF][START_REF] Kiran | Fusion of ground truths and hierarchies of segmentations[END_REF]. In Kovalevsky representation, the initial points of X ⊆ Z 2 become squares and the additional points become segments and points, as depicted in Fig. 3b. The adherence X → X is the union of the adherences of its basic elements, and the interior X → (X) • is the complement of the adherence of the complement set. Fig. 3b depicts the step X → X for one class of X, and Fig. 3c X → (X) • depicts the construction of the regularized version (X) • . The two classes of tessellation (X) • are separated by the net in bold of Fig. 3d. In the double resolution plane K 2 , all points of the background have odd coordinates. This example illustrates the following property: Proposition 3. Let K n be the Khalimsky space of n dimensions and Z n be the sub-space formed by the points of K n whose all coordinates are odd. Every partition π of Z n induces in K n a unique tessellation τ whose each class contains one class of π, and the correspondence between π and τ is biunivocal.

Proof. When Z n is embedded in K n , each class B i of π becomes open, since all its coordinates are odd. Replace all B i by their regularized versions S i = (B i ) • , and let z be a point of K n which does not belongs to any class, i.e. z ∈ [∪ S i ] c . Point z, which has one even coordinate at least, is the center of a unit cube which meets two classes S i at least, which amounts to say that the S i cover the space. Thus the family{S i } forms a tessellation of K n . Conversely, let τ be a tessellation of K n . Those points whose all coordinates are odd lie necessarily in some classes, as they are open, therefore the inverse passage to Z n forms a partition. This proposition theoretically justifies the classical rule of the double sampling [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF][START_REF] Cousty | Some morphological operators in graph spaces[END_REF][START_REF] Kiran | Energetic-Lattice based optimization[END_REF]. The fine mesh displays the net of the contours, which are topologically closed in R n as in K n , and which envelop the connected open sets. The odd points of K n , i.e. the unit open cubes play exactly the same role as the leaves in a hierarchy. But the topology of K n does not remove the ambiguity of the diagonals, as shown in Fig. 1a. We must introduce another topology.

6 Tessellations of Z 2 and Z 3 by Voronoi polyhedra Let X ⊆ R n be a locally finite set of centers. One can always associate with each center x ∈ X the so-called Voronoi polyhedron Q(x) of all points y ∈ R n closer to x than to any other center. Q(x) is convex and open, hence regular, so that the set {Q(x), x ∈ X} of all Voronoi polyhedra generates a tessellation of R n . In particular in R, when the centers are the points m of odd integer abscissae m, the corresponding Voronoi polyhedron is ]m -1, m + 1[. We find again Khalimsky topology.

Let H 3 represent the truncated octahedron. Let us come back to R n and impose the following two conditions to the Voronoi polyhedra:

1. they must be identical, up to a translation (i.e. regular grid); 2. the adherences of two adjacent polyhedra always have a common face of n-1 dimension.

Concerning the first constraint, the mineralogist E.S. Fedorov proved that there are only two solutions in R 2 , the square and the hexagon, and five in R 3 , the cube, the hexagonal prism, the truncated octahedron, and the two elongated and rhombic dodecahedra [START_REF] Fedorov | A Course in Crystallography[END_REF].

The second condition imposes strong adjacencies, thus preserves connectivity, according to Theorem 3. This condition reduces Fedorov possibilities to the only hexagon in the plane, and only truncated octahedron in the space. In the 2-D case the centers describe the triangular grid, in the 3-D case the centered cubic grid [START_REF] Serra | Cube, cube-octahedron or rhombododecahedron as bases for 3-d shape descriptions[END_REF] (see Fig. 5a). If we are not interested in preserving connectivity, this second condition becomes cumbersome.

Hexagonal tessellation of Z 2

In spite of its advantages the hexagonal grid is not often used (though it recently re-appeared about the simplicial complexes for digital watersheds [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF]). Consider in R 2 three axes of coordinates at 120 • , and the origin O. Take for centers all points of the plane whose coordinates are odd on each of the three axes. The associated Voronoi polygons are open hexagons. The other open sets are obtained by unions of these hexagons plus the edges adjacent between them. They result in a sn-topology where the triple points are closed. In Fig. 4b the previous squares and hexagons are replaced by the unique symbol of big discs, which indicate the pixels of X ⊆ Z , and the small points are added to give the (X) • . The asterisks indicate the net of the frontiers of the tessellation in the double resolution. By comparison with Khalimsky tessellation in square grid (Fig. 4a) two major differences appear. On the one hand, the frontiers are no longer Jordan arcs (clusters of pixels in the hexagonal grid),and on the other hand the ambiguous diagonal were removed by suppression of the quadruples points. If Fig. 4b is interpreted as the leaves of a hierarchy, a unique value is allocated to each crossing point, namely that of the level when North-East and South-West classes merge.

Tessellation of Z 3 by truncated octahedra

The Voronoi polyhedra of the centered cubic grid are the truncated octahedra depicted in Fig. 5. They partition R 3 in open polyhedra, square and hexagonal faces, triple edges and quadruple vertices. These elements generate a sn-topology. The regularization fills up the internal 1-D or 2-D fissures of zero thickness, and the background net is a connected union of faces and edges which completely envelops the classes.

In the digital version, the double resolution rule for inducing a tessellation is indicated in Fig. 5. One starts from three horizontal planes of the cubic grid containing the vertices of the unit cube (n • 1 and 5 in the Fig. ), and the center (n • 3). The planes n • 2 and 4 are added for generating a centered cubic grid twice finer. In the three directions of the cube and the four ones of the main diagonals alternate points of Z 3 with those added for forming the double resolution space.

Again the tessellation reduces the cells to the two types of the (open) truncated octahedra, and the (closed) square or hexagonal faces, i.e. something that can be described in terms of graphs. If the first elements are displayed by points and the second by asterisks, like in Fig. 4 in 2-D, and if we connect the asterisks which share an edge, then each class turns out to be a cluster of points completely surrounded by a net of asterisks. In practice, the centered cubic grid can easily be emulated by shifting horizontally the even planes by the vector (1, 1, 0).

Conclusion

In this paper, we characterized the partitions whose interiors and frontiers of the classes are jointly represented. They are the tessellations, consist of R-open sets. No conditions like to be Jordan curves (in 2D) hold on the frontiers, which can have a certain thickness. The theory applies to both Euclidean and digital spaces, which gives more soundness to the numerical techniques. It was shown in detail how the notions of tessellation, Alexandrov topology, and double resolution interact. In digitizing a partition we make use of the double resolution.

For Z 3 we proposed a variant of Khalimsky topology which suppresses the ambiguities of the diagonal configurations, it is based on the truncated octahedra, that is the regular vornoi polyhedra of the centerd-cubic grid.

Finally, it would be interesting to consider other alegraic closing operations, since they would also treat the classes and their frontiers in a unique representation.

Fig. 1 .

 1 Fig. 1. a) In a hierarchy, must we firstly connect the "2"s, or the "8"s? Do the frontiers in Figure c) play the same role as in Figure b)?

5 ) 3

 53 In what follows, S = (B) • designates the R-open transform of the open set B ∈ G(E). The operation B → S = (B) • is an algebraic closing on the set G of the open sets of E, and the image of G is R. For example, if we take Fig. 1c for B, we obtain Fig. 1b for transform S. This closing means that S is the smallest R-open set that contains B. Indeed, if another R-open S contains B, then S = (S ) • ⊇ (B) • = S. Note that S = (B) • ⇒ S ⊇ B and S = B. B ∈ G (In mathematical morphology, the three major bibliographic sources come from G. Matheron, Ch. Ronse, and H. Heijmans. The notion of an R-open (closed) set recurrently appears in Matheron works, from 1969 until 1996.

Theorem 2 .

 2 ) and the frontier of B contains that of S. The open sets of a tessellation cannot admit lacunae or fissures of empty interior, which makes the tessellation impossible. Thus the convenient class to consider are that of the R-open sets. Indeed, All classes B i of any tessellation τ = {B i , i ∈ I} are necessarily R-open.

Fig. 2 .

 2 Fig. 2. The space E is the 10 points of Z. The saliency function {x, y, z} does not detect the non connected class (in black) which appears at level 3 of this hierarchy.

Fig. 3 .

 3 Fig. 3. Simple resolution: a) two classes of a partition of Z 2 . Double resolution: b) Khaminsky closure of the first class of Fig.a; c) regular open versions of the two classes; d) corresponding tessellation (in black, the net between classes).

Fig. 4 .

 4 Fig. 4. Square versus hexagonal tessellation. The big discs are the elementary open sets; the unions of big and small discs form the regular open sets the small discs represent the segments and the points (square grid); and the contours with segments and asterisks delineate the background net. In the hexagonal case the quadruple point vanishes (thus its inherent ambiguity), but the background is no longer threadlike (small triangles).

Fig. 5 .

 5 Fig. 5. Left: Truncated octahedron and centered cubic grid. Center: Partition the space. Right: Top-down sections of the truncated octahedron. The big points are the open truncated octahedric cells of Z 3 , the small points and the rings are the points added to make H 3 . The regularization is obtained by union of big and small voxels.

Acknowledgment : The authors acknowledge G. Bertrand J. Cousty and T. Geraud for their useful comments, and the two reviewers for their pertinent remarks.