S Bonnabel

P Martin

P Rouchon

E Salaün

A Separation Principle on Lie Groups

Keywords: Lie groups, Separation principle, Non-holonomic systems, Mechanical systems

For linear time-invariant systems, a separation principle holds: stable observer and stable state feedback can be designed for the time-invariant system, and the combined observer and feedback will be stable. For non-linear systems, a local separation principle holds around steady-states, as the linearized system is time-invariant. This paper addresses the issue of a nonlinear separation principle on Lie groups. For invariant systems on Lie groups, we prove there exists a large set of (time-varying) trajectories around which the linearized observer-controler system is time-invariant, as soon as a symmetry-preserving observer is used. Thus a separation principle holds around those trajectories. The theory is illustrated by a mobile robot example, and the developed ideas are then extended to a class of Lagrangian mechanical systems on Lie groups described by Euler-Poincaré equations.

INTRODUCTION

The celebrated separation principle plays a key role in the linear theory of control. It states that the problem of designing an optimal stable feedback controller can be broken into two parts: designing an optimal stable observer meant to feed an optimal stable controller. As a particular application of this principle it is proved that for a linear time-invariant system, combining a stable observer and a stable controller yields a stable closed-loop system.

When the system is non-linear, the separation principle does not holds. However a local separation principle can always be stated around steady-states, as the linearized system around steady-states is linear and time-invariant. But in general it does not hold around other types of trajectories. In this paper, we consider invariant systems on Lie groups, and we state a local separation principle around a large class of trajectories that are not necessarily steady-states. Note that separation principles for special classes of non-linear systems have been addressed in e.g. [START_REF] Atassi | A separation principle for the stabilization of a class of nonlinear systems[END_REF]; [START_REF] Gauthier | A separation principle for bilinear systems with dissipative drift[END_REF], [START_REF] Maithripala | Intrinsic observer-based stabilization for simple mechanical systems on lie groups[END_REF].

Various systems of engineering interest can be modeled as invariant systems on Lie groups, mainly cart-like vehicles and mechanical systems such as rigid bodies in space.

There is an extensive literature on control on Lie groups (see e.g. [START_REF] Bullo | Tracking for fully actuated mechanical systems: A geometric framework[END_REF]; [START_REF] Grizzle | The structure of nonlinear systems possessing symmetries[END_REF]; [START_REF] Respondek | Nonlinearizable singleinput control systems do not admit stationary symmetries[END_REF]; [START_REF] Morin | Practical stabilization of driftless systems on lie groups, the transverse function approach[END_REF] and [START_REF] Jurdjevic | Control systems on lie groups[END_REF] as one of the pioneering papers), but general methods for observer design on Lie groups have only been introduced recently [START_REF] Bonnabel | Nonlinear symmetry-preserving observers on lie groups[END_REF]; [START_REF] Lagemann | Gradient-like observers for invariant dynamics on a lie group[END_REF]; [START_REF] Mahony | Nonlinear complementary filters on the special orthogonal group[END_REF]). In this paper, a link is established between those two fields or reasearch and a separation principle on Lie groups is stated.

In Section 2, we recall the linear separation principle, and the local non-linear separation principle around steady states. In Section 3, we consider a left-invariant system on a Lie group and we build a symmetry-preserving observer. It has been proved that, for such observers there exists a large set of trajectories around which the estimation error is time-invariant: the so-called permanent trajectories [START_REF] Bonnabel | Symmetry-preserving observers[END_REF][START_REF] Bonnabel | Nonlinear symmetry-preserving observers on lie groups[END_REF]). In this paper, we prove that the tracking error is also time-invariant when the reference trajectory is a permanent trajectory. As a result, the linearized closed-loop observer-controler system is time-invariant around permanent trajectories. This implies a (local) separation principle around permanent trajectories. This result advocates that the recently introduced permanent trajectories for systems on Lie groups generalize steady states for general non-linear systems. Indeed, if the observer is not a symmetry-preserving observer, the linearized closed-loop observer-controler system around permanent trajectories is time-varying (in general), implying that a local separation principle does not hold.

In Section 4, we consider the well-known problem of localizing from landmarks using sonar (see e.g. [START_REF] Betke | Mobile robot localization using landmarks[END_REF]). Observability follows from triangulation, and position estimation is generally achieved via the widespread Extended Kalman filter (see e.g. [START_REF] Roumeliotis | Bayesian estimation and kalman filtering: a unified framework for mobile robot localization[END_REF]). For this system we derive a class of symmetry-preserving observers that converge around any permanent trajectories (i.e. circles and lines with constant speed). The separation principle derived in this paper allows to prove that, as soon as the control scheme is stable around those trajectories, the closed-loop system is also stable around those trajectories and the eigenvalues of the closed-loop linearized system are those of the observer together with those of the controller. It is interesting to note that this stability result does not hold for an Extended Kalman Filter. Note that symmetry-preserving observers have already been used for localization from landmarks in [START_REF] Vasconcelos | Landmark based nonlinear observer for rigid body attitude and position estimation[END_REF].

Besides the two main contribution of this paper, which are to derive a (local) separation principle for invariant systems on Lie groups, and to derive an observer-controler for the localization problem from landmarks with guaranteed convergence properties around a large set of trajectories, we consider in Section 5 a (very) particular observation problem for simple mechanical systems on Lie groups whose motion is described by Euler-Poincaré equations. Such systems have been extensively studied in the literature (see e.g. [START_REF] Bullo | Controllability and motion algorithms for underactuated lagrangian systems on lie groups[END_REF]; [START_REF] Bullo | Tracking for fully actuated mechanical systems: A geometric framework[END_REF]; [START_REF] Marsden | Introduction to Mechanics and Symmetry[END_REF]. By a similar token as the one of Section 2 we prove a local separation principle around permanent trajectories.

THE LINEAR SEPARATION PRINCIPLE

Consider the system ẋ = f (x, u) (1) y = h(x, u),
(2) where (x, u, y) belongs to an open subset X ×U ×Y ⊂ R n × R m × R p . We would like to track the reference trajectory ẋr = f (x r , u r ) (3) y r = h(x r , u r ) (4) using only the measured output y. In other words we want to stabilize the equilibrium point (η x , ηu ) := (0, 0) of the error system ηx = f (x r + η x , u r + η u )f (x r , u r ) (5) η y = h(x r + η x , u r + η u )h(x r , u r ), (6) where η x := xx r , η u := uu r and η y := yy r . Here we are interested only in local stability, i.e. we want to stabilize the linearized error system

ξx = ∂ 1 f (x r , u r )ξ x + ∂ 2 f (x r , u r )ξ u = Aξ x + Bξ u (7) ξ y = ∂ 1 h(x r )ξ x + ∂ 2 h(x r , u r )ξ u = Cξ x + Dξ u . (8)
The notation ∂ i stands for the derivative with respect to the i th argument.

Notice the system (5)-( 6) as well as the matrices A, B, C, D are in general not time-invariant unless the reference trajectory (x r , u r ) is an equilibrium point, i.e. is constant and such that f (x r , u r ) = 0.

Linear controller with linear observer

To stabilize the linearized system, one can use the linear controller-observer

ξ u = -K ξx (9) ξx = A ξx + Bξ u -L(C ξx + D ξu -ξ y ) = (A -BK -LC + BLD) ξx + Lξ y , (10)
where the m × n matrix K and n × p matrix L are to be chosen. Indeed, setting e

x := ξx -ξ x the closed-loop system ξx = (A -BK)ξ x -BKe x (11) ėx = (A -LC)e x
(12) has a triangular structure hence its eigenvalues are those of A -BK together with those of A -LC. If (x r , u r ) is an equilibrium point, it can easily be stabilized by placing separately the eigenvalues of A -BK through K and those of A -LC through L (provided of course (A, B) is controllable and (A, C) is observable). This is the well-known separation principle for linear time-invariant systems. The result still applies if the reference trajectory is slowly-varying, i.e. f x r (t), u r (t) ≈ 0 for all t; K and L may also depend on the reference trajectory to provide gain-scheduling. This shows that the control law

η u = -K ξx (13) ξx = (A -BK -LC + BLD)ξ x + Lη y , (14)
where the input ξ y and output ξ u of ( 9)-( 10) are replaced by η y and η u , locally stabilizes the equilibrium point (η x , ηu ) := (0, 0) of ( 5). In other words

u = u r -K ξx ξx = (A -BK -LC + BLD) ξx + L(y -y r )
stabilizes (1) around the reference trajectory (3)-( 4) using only the measured output (2).

Linear controller with extended observer

Instead of the linear observer of the previous section, the so-called "extended" observer ẋ = f (x, u) -L h(x, u)y can be used. The n × p gain matrix L may depend on x to provide gain-scheduling. We assume this observer converges, i.e. the origin of the error system εx

= f (x, u) -L h(x, u) -h(x -ε x , u) -f (x -ε x , u
) is stable, where ε x := xx is the observation error. Once again we are interested only in local stability, i.e. we assume only the stability of the linearized error system

ėx = ∂ 1 f (x, u) -L∂ 1 h(x, u) e x .
(15) Notice it is usually not easy to ensure even this local stability, unless the reference trajectory (x r , u r ) is an equilibrium point. In this case (15) can be further linearized around (x r , u r ), which yields (12).

The control law

u = u r -K(x -x r ) ẋ = f (x, u) -L h(x, u) -y
then locally stabilizes (1) around the reference trajectory (3)-( 4) using only the measured output (2). Indeed,

η u = -K(x -x + x -x r ) = -K(ε x + η x ), hence ξ u = -K(e x + ξ x ), so that the linearized closed-loop system ξx = (A -BK)ξ x -BKe x ėx = ∂ 1 f (x, u) -L∂ 1 h(x, u) e
x is clearly stable.

A SEPARATION PRINCIPLE FOR INVARIANT SYSTEMS

We again consider the system (1)-( 2), but now X is a Lie group of dimension n with identity e and group law x 2 x 1 := ϕ(x 2 , x 1 ).

Definition 1. Let Σ be an open set (or more generally a manifold). A transformation group on Σ is a smooth map

(x, ξ) ∈ X × Σ → φ(x, ξ) ∈ Σ such that • φ(e, ξ) = ξ for all ξ • φ x 2 , φ(x 1 , ξ) = φ(x 2 x 1 , ξ) for all x 1 , x 2 , ξ. By construction φ(x, •) is a diffeomorphism on Σ for all x.
Consider then the transformation group on X × U × Y defined by φ x 0 , (x, u, y) := ϕ(x 0 , x), ψ(x 0 , u), ̺(x 0 , y) . We will assume in the sequel that the system (1)-( 2) enjoys the following important invariance property. Definition 2. The system (1)-( 2) is invariant by the transformation group if for all x 0 , x, u 1)-( 2) is left unchanged by the transformation group.

• f ϕ(x 0 , x), ψ(x 0 , u) = ∂ 2 ϕ(x 0 , x)f (x, u) • h ϕ(x 0 , x), ψ(x 0 , u) = ̺ x 0 , h(x, u) . With (X, U, Y ) := ϕ(x 0 , x), ψ(x 0 , u), ̺(x 0 , u) this reads Ẋ = f (X, U ) Y = h(X, U ), i.e. (
Finally define the following "products" which provide very compact notations: for

x 0 ∈ X , (x, u, y) ∈ X × U × Y and ξ ∈ T x X (T x X is the tangent space of X at x) x 0 u := ψ(x 0 , u) (16) x 0 y := ̺(x 0 , y) (17) x 0 ξ := ∂ 2 ϕ(x 0 , x)ξ ∈ T x0x X (18) ξx 0 := ∂ 1 ϕ(x, x 0 )ξ ∈ T xx0 X .
(19) Invariance then reads f (x 0 x, x 0 u) = x 0 f (x, u) and h(x 0 x, x 0 u) = x 0 h(x, u).

We would like the invariant system (1)-(2) to track the reference trajectory (3)-(4). Instead of using as before the "linear" errors xx r , uu r and yy r , we consider the errors x := x -1 r x, η u := x -1 r ux -1 r u r and η y := x -1 r yx -1 r y r . These errors are invariant in the sense that (x

0 x r ) -1 (x 0 x) = x -1 r x, (x 0 x r ) -1 (x 0 u) = x -1 r u and (x 0 x r ) -1 (x 0 y) = x -1
r y. The error system is then given by ηx

= x -1 r f (x, u) -x -1 r f (x r , u r )x -1 r x = η x f (e, x -1 u) -f (e, x -1 r u r )η x = η x f (e, η -1 x (I r + η u )) -f (e, I r )η x ( 20
)
η y = x -1 r h(x, u) -x -1 r h(x r , x r ) = h(η x , I r + η u ) -h(e, I r ),
(21) and we want to stabilize its equilibrium point (η x , ηu ) := (e, 0). We have used the important invariant quantity I r := x -1 r u r , which leads to the following definition of a class of remarkable trajectories. Definition 3. The trajectory (x r , u r ) is permanent if I r is constant (i.e. independent of time).

Once again we are interested only in local stability, i.e. we want to stabilize only the linearization of ( 20)-( 21) around (η x , ηu ) := (e, 0). Recall that to linearize around e the map η x ∈ X → g(η x ), one can write η x = exp(sξ x ) where exp is the exponential map of the Lie group X , s ∈ R and ξ x ∈ T e X (T e X is identified with the Lie algebra of X ). The linearization of g is then given by d ds g exp(sξ x )

s=0 = ∂ 1 g(e)ξ x .
Applying this to ( 20)-( 21), we find the linearized error system is ξx

= ξ x f (e, I r ) -f (e, I r )ξ x + ∂ 2 f (e, I r )(ξ u -ξ x I r ) = Aξ x + Bξ u (22) ξ y = ∂ 1 h(e, I r )ξ x + ∂ 2 h(e, I r )ξ u = Cξ x + Dξ u , (23)
where we have defined the "products"

ξu := ∂ 1 ψ(e, u)ξ ξζ := ∂ 1 ∂ 2 ϕ(e, e)ξ ζ = ∂ 2 ∂ 1 ϕ(e, e)ζ ξ for u ∈ U and ξ, ζ ∈ T e X .
Notice the system ( 20)-( 21) as well as the matrices A, B, C, D are in general not time-invariant unless the reference trajectory (x r , u r ) is permanent. Since ( 22)-( 23) has the same form as ( 7)-( 8), we will be able to extend the usual separation principle around equilibrium points to a separation principle around permanent trajectories. The main benefit is that there are many more permanent trajectories thant equilibrium points.

Linear controller with linear observer

To stabilize the linearized error system ( 22)-( 23) we can use a linear controller-observer of the form ( 9)-( 10). As in section 2.1, the control law ( 13)-( 14) with η x , η u replacing ξ y , ξ u stabilizes the equilibrium point (η x , ηu ) := (e, 0) of (20). Using the definitions of η u , η y and the fact that x -1 r (x r u) = (x -1 r x r )u = u we eventually find that u = x r (I r -K ξx ) ξx = (A -BK -LC + BLD) ξx + L x -1 r yh(e, I r ) stabilizes (1) around the reference trajectory (3)-(4) using only the measured output (2).

Linear controller with invariant observer

Following [START_REF] Bonnabel | Symmetry-preserving observers[END_REF][START_REF] Bonnabel | Nonlinear symmetry-preserving observers on lie groups[END_REF], we can easily design an invariant extended observer for invariant systems, using the invariant output error ε y := x-1 h(x, u) -x-1 y instead of the "linear" output error h(x, u)y. Such an observer reads ẋ

= f (x, u) -xL x-1 h(x, u) -x-1 y ,
where the gain matrix L may depend on Î := x-1 u and on the output error ε y .

The error system for the (invariant) state observation error

ε x := x -1 x is εx = x -1 f (x, u) + xL x-1 h(x, u) -x-1 h(x, u) -x -1 f (x, u)x -1 x = ε x f (e, Î) -f (e, ε x Î)ε x -ε x L h(ε -1 x , Î) -h(e, Î)
, and its linearization around the origin is

ėx = e x f (e, Î) -f (e, Î)e x -∂ 2 f (e, Î)e x -L∂ 1 h(e, Î)e x .
It is then easy to tune the gain matrix L so that the observer converges at least around permanent trajectories.

Mimicking section 2.2 the control law

u = x r I r -Kκ(x -1 r x) ẋ = f (x, u) + xL x-1 y -h(e, Î)
then locally stabilizes (1) around the reference trajectory (3)-(4) using only the measured output (2). Here κ is any map such that d ds κ exp(sξ

) s=0 = ξ,
for instance a determination of the logarithm map of the group (i.e. the inverse of the exponential map of the group). Indeed, x -1 r u = I r -Kκ(x -1 r xx -1 x), i.e. η u = -Kκ(η x ε x ). Linearizing, this yields ξ u = -K(e x + ξ x ), so that the linearized closed-loop system ξx = (A -BK)ξ x -BKe x ėx = e x f (e, Î)f (e, Î)e x -∂ 2 f (e, Î)e x -L∂ 1 h(e, Î)e x is clearly stable.

EXAMPLE: OUTPUT CONTROL OF A WHEELED ROBOT FROM SONAR LANDMARKS

Consider the simple planar non-holonomic model of a wheeled robot ẋ = uCθ ẏ = uSθ θ = uv,

where the control inputs are the velocity u and v the tangent of the steering angle; Cθ and Sθ stand for cos θ and sin θ. We take for measurements the (square of the) distances to p ≥ 3 planar landmarks with known coordinates (x i , y i ),

λ i = (x -x i ) 2 + (y -y i ) 2 , i = 1, .
. . , p. The measurement system could be for instance a set of ultrasonic emitters located at (x i , y i ), while the robot is equipped with ultrasonic receivers measuring the time of flight of the sonic waves.

Notice the only equilibrium points are given by ū = 0 and x, ȳ, θ, v constant, i.e. the robot is at rest. Moreover the linearized system around these points is clearly not controllable. Hence it is not possible to use the linear separation principle of section 2.

It is easy to check the composition law

x 0 y 0 θ 0 x y θ

:= xCθ 0 -ySθ 0 + x 0 xSθ 0 + yCθ 0 + y 0 θ + θ 0 ,
with unit element and inverse defined by e := 0 0 0 and x y θ

-1 := -xCθ -ySθ xSθ -yCθ 0 -θ is a group law. Moreover x 0 y 0 θ 0      u v x i y i λ i      :=      u v x i Cθ 0 -y i Sθ 0 + x 0 x i Sθ 0 + y i Cθ 0 + y 0 λ i     
defines a transformation group. Notice the beacon coordinates (x i , y i ) can be considered as known constant inputs.

Direct computation shows the system is invariant in the sense of definition 2. Notice u, v are invariant, hence the permanent trajectories are defined by x(t) = ū sin(ūvt + θ)

y(t) = -ū cos(ūvt + θ) θ(t) = ūvt,
where ū, v, θ are arbitrary constants; there consist of arbitrary circles (when v = 0) and lines (when v = 0).

Design of a linearized state controller

The state tracking error is

η x η y η θ := x r y r θ r -1 x y θ = (x -x r )Cθ r + (y -y r )Sθ r -(x -x r )Sθ r + (y -y r )Cθ r θ -θ r and satisfies ηx ηy ηθ = Cθ r Sθ r 0 -Sθ r Cθ r 0 0 0 1   ẋ -ẋr ẏ -ẏr θ -θr   + θr -Sθ r Cθ r 0 -Cθ r -Sθ r 0 0 0 0 x -x r y -y r 0 = (u r + η u )Cη θ -u r + u r v r η y (u r + η u )Sη θ -u r v r η x (u r + η u )(v r + η v ) -u r v r .
The linearized error equation around (η x , ηy , ηθ , ηu , ηv ) = (0, 0, 0, 0, 0) is then ξx

= ξ u + u r v r ξ y ξy = u r ξ θ -u r v r ξ x ξθ = v r ξ u + u r ξ v .
If we choose for instance the state feedback

ξ u = -u r v r ξ y -|u r |k 1 ξ x ξ v = sign(u r )k 1 ξ x + v 2 r ξ y -k 2 ξ y -sign(u r )k 3 ξ θ the resulting closed-loop ξx = -|u r |k 1 ξ x ξy = u r ξ θ -u r v r ξ x ξθ = -u r k 2 ξ y -|u r |k 3 ξθ with k 1 , k 2 , k 3 > 0 is obviously stable for u r , v r constant.
It is even stable for non constant u r , v r provided for u r , v r are bounded and +∞ t0 |u r (t)|dt = +∞ for all t 0 ≥ 0.

Design of an extended observer

The output observation error is

ε i :=   x ŷ θ  -1 (x -x i ) 2 + (ŷ -y i ) 2 -   x ŷ θ  -1 λ i = (x -x i ) 2 + (ŷ -y i ) 2 -λ i and the "product" (18) is x 0 y 0 θ 0 ξ =   C θ -S θ 0 S θ C θ 0 0 0 1   ξ.
Every invariant observer then reads

   ẋ ẏ θ   =   uC θ uS θ uv   -   C θ -S θ 0 S θ C θ 0 0 0 1   L    ε 1 . . . ε p    ,
where L is a 3 × p matrix possibly depending on ε i and the invariant quantities

    Îu Îv Îxi Îyi     :=   x ŷ θ  -1    u v x i y i    =     u v (x i -x)C θ + (y i -ŷ)S θ -(x i -x)S θ + (y i -ŷ)C θ    .
For reasons that will shortly be apparent, we choose

L := - 1 2 L(II T ) -1 I
where L is a 3x2 matrix to be defined and I is the 2 × p matrix

I := Îx1 • • • Îxp Îy1 • • • Îyp .
Notice (II T ) -1 is always invertible when p ≥ 3.

The state observation error

ε x ε y ε θ := x y θ -1   x ŷ θ  =   (x -x)Cθ + (ŷ -y)Sθ -(x -x)Sθ + (ŷ -y)Cθ θ -θ   has for equation εx εy εθ = Cθ Sθ 0 -Sθ Cθ 0 0 0 1       ẋ - ẋ ẏ - ẏ θ - θ    -   C θ -S θ 0 S θ C θ 0 0 0 1   L    ε 1 . . . ε p       + θ -Sθ Cθ 0 -Cθ -Sθ 0 0 0 0 x -x ŷ -y 0 = u(Cε θ -1) + uvε y -uSε θ -uvε x 0 + Cε θ -Sε θ 0 Sε θ Cε θ 0 0 0 1 L    ε 1 . . . ε p    , with ε i = (x -x i ) 2 + (ŷ -y i ) 2 -(x -x i ) 2 -(y -y i ) 2 = -2 (x i -x y i -ŷ) x -x ŷ -y -(x -x) 2 -(ŷ -y) 2 = -2 Îxi Îyi C θ S θ -S θ C θ Cθ -Sθ Sθ Cθ ε x ε y -ε 2 x -ε 2 y = -2 Îxi Îyi Cε θ -Sε θ Sε θ Cε θ ε x ε y -ε 2 x -ε 2 y .
Linearizing around the equilibrium point (ε x , εy , εθ ) := (0, 0, 0), we have

The control law

Combining as in section 3.2 the previously designed linearized controller and extended observer we end up with the control law

u v = u r -u r v r ηy -|u r |k 1 ηx v r sign(u r )k 1 ηx + v 2 r ξ y -k 2 ηy -sign(u r )k 3 ηθ    ẋ ẏ θ   =   uC θ uS θ uv   + 1 2   C θ -S θ 0 S θ C θ 0 0 0 1   L(II T ) -1 I    ε 1 . . . ε p    ,
where ηx ηy ηθ

:= x r y r θ r -1 x ŷ θ =   (x -x r )Cθ r + (ŷ -y r )Sθ r -(x -x r )Sθ r + (ŷ -y r )Cθ r θ -θ r   .
Notice the map κ chosen here is simply the identity. This control law stabilizes the system around any permanent trajectory.

FULLY-ACTUATED MECHANICAL SYSTEMS ON LIE GROUPS

In this section, we consider a simple mechanical system on a Lie group whose motion is described by the so-called Euler-Poincaré equations. We focus on fully-actuated systems arising in control theory as described by e.g. [START_REF] Bullo | Tracking for fully actuated mechanical systems: A geometric framework[END_REF]

ẋ = f (x, ξ) (24) ξ = A(ξ) + I -1 (F (x, ξ) + u) (25
) where x ∈ G is the (generalized) position, with G a Lie group (the configuration space), ξ ∈ T x G is the (generalized) velocity, A is a bilinear function of its argument, I -1 (F (x, ξ)+u) is the resultant force acting on the system, and u ∈ T x G denotes the control. Moreover, the system (24) is invariant to the following G-group action : for any x 0 ∈ G the action x 0 x is the left multiplication on G, and x 0 ξ = ξ.

Considered observation problem

We assume that ξ is known or measured, and dropping the second equation ( 25) (as ξ does not need to be estimated), we focus on the following observation problem: ẋ

= f (x, ξ) y = h(x) (26)
where the output satisfies x 0 h(x) = h(x 0 x). The theory of Section 2 applies to this problem, and the permanent trajectories are generated by constant velocities, i.e. I r = x -1 r ξ r = ξ r ≡ cst. Such trajectories are very natural for mechanical systems and admit a geometrical interpretation (they are generated by one-parameter subgroups of G). They constitute interesting motion primitives that can be concatenated to yield a very large class of trajectories (think of straight lines and coordinated turn in avionics which are permanent trajectories on SE(3) [START_REF] Bonnabel | Nonlinear symmetry-preserving observers on lie groups[END_REF]). In the sequel we will prove that a local separation principle holds around those trajectories.

Control problem around permanent trajectories

Consider the reference trajectory (x r (t), ξ r ) generated by a time-invariant ξ r . Let u r be the corresponding control. Let the invariant tracking error be (η x , η ξ ) = (x -1 r x, ξ -ξ r ) as in [START_REF] Bullo | Tracking for fully actuated mechanical systems: A geometric framework[END_REF]. As the system (24) is invariant, applying (20) (where u is replaced by ξ) we have d dt η x = Υ(η x , η ξ , I r )

Moreover we have, up to second order terms in (η x , η ξ ) d dt η ξ = A(I r + η ξ ) -A(I r ) + I -1 (δ 1 F (x r , I r )η x + δ 2 F (x r , I r )η ξ + η u ) We have thus the following result: Lemma 4. If δ 1 F (x, ξ) and δ 2 F (x, ξ) do not depend on x, the linearized tracking error around permanent trajectories generated by ξ r ≡ cst is time-invariant.

It implies that under assumptions of Lemma 4 (which are usually satisfied in practice), a local separation principle holds around permanent trajectories for the control problem ( 24)-( 25) combined with an invariant observer for the subsystem (26), and where ξ is known or measured.

We believe that the problem addressed in this section is relevant to applications, and examples are left for future research. Note that [START_REF] Maithripala | Intrinsic observer-based stabilization for simple mechanical systems on lie groups[END_REF] proved a separation principle for simple mechanical systems on Lie groups where the position is measured, and a velocity observer must be designed. This is a different problem and a different approach is developed. The drawback of this approach is that it relies on many restrictive assumptions. In particular: the group must be compact, and the observer must be exponentially convergent around any trajectory.

CONCLUSION

In this paper a local separation principle around a large set of trajectories for non-linear invariant systems on Lie groups was proved. We also proved that the results extend partially to the control of simple mechanical systems on Lie groups. In future research we plan to explore examples of mechanical systems for which those results apply.

  3 with l 1 , l 2 , l 3 > 0, the linearized error system reads ėx = -|u|l 1 e x ėy = -ue θ -|u|l 2 e y ėθ = -ul 3 e y is obviously stable provided +∞ t0 |u r (t)|dt = +∞ for all t 0 ≥ 0. This means the designed observer is convergent locally around every trajectory.


Pierrick Coupé

Simon F Eskildsen

José V Manjón

Vladimir Fonov

D Louis Collins

Simultaneous Segmentation and Grading of Hippocampus for Patient Classification with Alzheimer's Disease

Keywords: hippocampus segmentation, hippocampus grading, patient classification, nonlocal means estimator, Alzheimer's disease

Purpose:

To propose an innovative approach to better detect Alzheimer's Disease (AD) based on a finer detection of hippocampus (HC) atrophy patterns. Method: In this paper, we propose a new approach to simultaneously perform segmentation and grading of the HC to better capture the patterns of pathology occurring during AD. Based on a patch-based framework, the novel proposed grading measure estimates the similarity of the patch surrounding the voxel under study with all the patches present in different training populations. The training library used during our experiments was composed by 2 populations, 50 Cognitively Normal subjects (CN) and 50 patients with AD. Tests were completed in a leave-one-out framework. Results: First, the evaluation of HC segmentation accuracy yielded a Dice's Kappa of 0.88 for CN and 0.84 for AD. Second, the proposed HC grading enables detection of AD with a success rate of 89%. Finally, a comparison of several biomarkers was investigated using a linear discriminant analysis. Conclusion: Using the volume and the grade of the HC at the same time resulted in an efficient patient classification with a success rate of 90%.

Introduction

The atrophy of medial temporal lobe structures, such as the hippocampus (HC) and entorhinal cortex, is potentially specific and may serve as early biomarkers of Alzheimer's disease (AD) [START_REF] Frisoni | The clinical use of structural MRI in Alzheimer disease[END_REF]. In particular, the atrophy of the HC can be used as a marker of AD progression since changes in HC are closely related to changes in cognitive performance of the subject [START_REF] Frisoni | The clinical use of structural MRI in Alzheimer disease[END_REF]. The evaluation of HC atrophy is usually estimated by volumetric studies on anatomical MRI, requiring a segmentation step that can be very time consuming when done manually. This limitation can be overcome by using automatic segmentation methods [START_REF] Chupin | Automatic segmentation of the hippocampus and the amygdala driven by hybrid constraints: method and validation[END_REF][START_REF] Collins | Towards accurate, automatic segmentation of the hippocampus and amygdala from MRI by augmenting ANIMAL with a template library and label fusion[END_REF][START_REF] Lotjonen | Fast and robust multi-atlas segmentation of brain magnetic resonance images[END_REF][START_REF] Coupe | Patchbased segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF]. However, despite the high segmentation accuracy of these HC segmentation approaches, using only the HC volume enables a separation between AD and cognitively normal (CN) subjects with a success rate around 72-74% [START_REF] Cuingnet | Automatic classification of patients with Alzheimer's disease from structural MRI: A comparison of ten methods using the ADNI database[END_REF]. This limited capability to classify AD patients by using the HC volume only may be due to a simplification of the complex hippocampal atrophy patterns to a volume changing measurement. Recently, several shape analysis methods have been proposed [START_REF] Gerardin | Multidimensional classification of hippocampal shape features discriminates Alzheimer's disease and mild cognitive impairment from normal aging[END_REF][START_REF] Csernansky | Preclinical detection of Alzheimer's disease: hippocampal shape and volume predict dementia onset in the elderly[END_REF] to capture detailed patterns of change in order to obtain a more accurate classification. These approaches provide a slightly better classification rate of around 77% [START_REF] Cuingnet | Automatic classification of patients with Alzheimer's disease from structural MRI: A comparison of ten methods using the ADNI database[END_REF].

Inspired by work in image denoising [START_REF] Coupe | An optimized blockwise nonlocal means denoising filter for 3-D magnetic resonance images[END_REF], a new nonlocal patch-based label fusion method has recently been proposed to segment anatomical structures [START_REF] Coupe | Patchbased segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF]. By taking advantage of the redundancy of information present within the subject's image, as well as the redundancy across the training subjects, the patch-based nonlocal means scheme enables robust use of a large number of samples during estimation. In [START_REF] Coupe | Patchbased segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF], this approach has been applied to label fusion for the segmentation of anatomical structures. We propose an extension of this patch-based segmentation method in order to evaluate the similarity (in the nonlocal means sense) of the intensity content of one MRI compared to several training populations. By using training populations with different pathological status (e.g., CN subjects and patients with AD), a nonlocal means estimator is used to evaluate the proximity (i.e., the grade or the degree of atrophy in case of AD) of each voxel of the MRI under study compared to the training populations. Since the grade estimation and the label fusion steps require the same patch comparison, simultaneous segmentation and grading of HC can be achieved in one pass. In the proposed approach, the nonlocal patch-based comparison is used to efficiently fuse the HC segmentations of MRI in a training database and at the same to aggregate the pathological status of the populations constituting the training database. Finally, the average grading value obtained over the segmented HC is proposed as a new biomarker to estimate the pathological status of the subject under study. The contributions of the paper are: i) the introduction of an innovative approach to better characterize the patterns of pathology (e.g., atrophy) in AD through the new concept of HC grading, ii) the presentation of a method to automatically and simultaneously perform the segmentation and the grading of HC, and iii) the demonstration that the proposed approach can be used as a novel biomarker to efficiently achieve patient classification in the context of AD.

Materials and Methods

Dataset and Preprocessing

In this study, the ADNI database (www.loni.ucla.edu/ADNI) was used to validate the proposed approach. This database contains both 1.5T and 3.0T T1-w MRI scans. For our experiments, we randomly selected 120 MRI scans, 60 1.5T MRI baseline scans of CN subjects and 60 1.5T MRI baseline scans of patients with AD. All the selected images were preprocessed as follows: 1) correction of inhomogeneities using N3 [START_REF] Sled | A nonparametric method for automatic correction of intensity nonuniformity in MRI data[END_REF], 2) registration to the stereotaxic space using a linear transform to the ICBM152 template (1x1x1 mm³ voxel size) [START_REF] Collins | Automatic 3-D model-based neuroanatomical segmentation[END_REF] and 3) cross-normalization of the MRI intensity using the method proposed in [START_REF] Nyul | Standardizing the MR image intensity scales: making MR intensities have tissue specific meaning[END_REF]. After preprocessing, all the MRIs are coarsely aligned (linear registration), tissue intensities are homogeneous within each MRI volume (inhomogeneity correction) and across the training database (intensity normalization). From the 120 processed MRI scans, 20 scans (10 CN and 10 AD) were randomly selected to be used as seed dataset. The left and right hippocampi of this seed dataset were then manually segmented by an expert at our centre. The manual segmentations of the seed dataset were propagated to the 100 remaining scans constituting our test dataset. After segmentation propagation using [START_REF] Coupe | Patchbased segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF], the test dataset was composed of 100 MRI (50 CN subjects and 50 patients with AD) with their corresponding automatic segmentations.

Method overview

In nonlocal means-based approaches [START_REF] Coupe | An optimized blockwise nonlocal means denoising filter for 3-D magnetic resonance images[END_REF], the patch P(x i ) surrounding the voxel x i under study is compared with all the patches P(x j ) of the image Ω whatever their spatial distance to P(x i ) (it is the meaning of the term "nonlocal"). According to the patch similarity between P(x i ) and P(x j ), estimating by the Sum Squared Difference (SSD) measure, each patch receives a weight w(x i , x j ):

2 2 2 ) ( ) ( ) , ( h x P x P j i j i e x x w - - =
where ||.|| 2 is the L2-norm computed between each intensity of the elements of the patches P(x i ) and P(x s,j ), and h is the smoothing parameter of the weighting function. This weighting function is designed to give a weight close to 1 when the SSD is close to zero and a weight close to zero with the SSD is high. Finally, all the intensities u(x j ) of the central voxels of the patches P(x j ) are aggregated through a weighted average using the weights w(x i , x j ). In this way, the denoised intensity û(x i ) of the voxel x i can be efficiently estimated:

∑ ∑ Ω ∈ Ω ∈ = j j i j j j i i x x w x u x x w x u ) , ( ) ( ) , ( ) ( ˆ
In [START_REF] Coupe | Patchbased segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF], we introduced this estimator in the context of segmentation by averaging labels instead of intensities. By using a training library of N subjects, whose segmentations of structures are known, the weighted label fusion is estimated as follows:

v(x i ) = w(x i , x s, j )l(x s, j ) j∈Ω ∑ s=1 N ∑ w(x i , x s, j ) j∈Ω ∑ s=1 N ∑
where l(x s,j ) is the label (i.e., 0 for background and 1 for structure) given by the expert to the voxel x s,j at location j in training subject s. It has been shown that the nonlocal means estimator v(x i ) provides a robust estimation of the expected label at x i [START_REF] Coupe | Patchbased segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF]. With a label set of {0,1}, voxels with value v(x i )≥0.5 are considered as belonging to HC and the remaining voxels as background.

In this paper, we propose to extend it to efficiently aggregate pathological status in order to estimate the proximity (in the nonlocal means sense) of each voxel compared to both populations constituting the training library. To do that, we introduce the new concept of patch-based grading that reflects the similarity of the patch surrounding the voxel under study with all the patches present in the different training populations. In this way, the neighborhood information is used to robustly drive the search of anatomical patterns that are specific to a given subset of the training library. When the training populations include data from subsets of patients with different stages of the pathology progression, this approach provides an estimation of the grade (i.e., degree of atrophy in case of AD) for each voxel:

∑ ∑ ∑ ∑ = Ω ∈ = Ω ∈ = N s j j s i N s j s j s i i x x w p x x w x g 1 , 1 , ) , ( ). , ( ) (
where p s is the pathological status of the training subject s. In our case, p s =-1 was used for AD status and p s =1 for CN status. A negative grading value (respectively, a positive grading value) g(x i ) indicates that the neighborhood surrounding x i is more characteristic of AD than CN (respectively, of CN than AD). The absolute value |g(x i )| provides the confidence given to the grade estimation. When |g(x i )| is close to zero, the method indicates that the patch under study is similarly present in both populations and thus is not specific to one of the compared populations and provides little discriminatory information. When |g(x i )| is close to 1, the method detects a high proximity of the patch under study with the patches present in one of the training population and not in the other. Finally, for each subject, an average grading value is computed over all voxels in the estimated segmentation (i.e., for all x i with v(x i )≥0.5) by assigning the same weight to the left and right HC (i.e., ).

During all our experiments, the default parameters proposed in [START_REF] Coupe | Patchbased segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF] have been used. The patch size was fixed to 7x7x7 voxels and the search window of similar patches has been limited within a restricted volume of 9x9x9 voxels for computational reasons (i.e., Ω is replaced by a cubic volume V i centered on x i ). Finally, the smoothing parameter h 2 was locally set as the minimal SSD found between the patch under study and all the patches in the training library as proposed in [START_REF] Coupe | Patchbased segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF].

Validation framework

Segmentation accuracy validation: In order to evaluate the segmentation accuracy of the method proposed in [START_REF] Coupe | Patchbased segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF] on patients with AD, we first perform a leave-one-out procedure on the 20 subjects with manual segmentation composing the seed dataset. The N=16 closest training subjects (in the SSD sense, see [START_REF] Coupe | Patchbased segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF] for details) were equally selected within both populations (i.e., 8 AD and 8 CN). The Dice's kappa was then computed by comparing the expert-based segmentation, used as gold standard, and the segmentation obtained automatically. This first validation is used to support the fact that the segmentation propagation over the 100 subjects in our test dataset from the 20 subjects in our seed dataset is done in an accurate manner.

Grading validation: After the segmentation propagation step, a leave-one-out procedure is performed over the 100 subjects of the test dataset. For each subject, the N closest training subjects are selected equally in both populations. This is done to ensure that the size of the "patch pool" from AD population is coarsely similar to the size of the "patch pool" from CN population. To save computational time, N is automatically adjusted according to the obtained g . In the first iteration, N=20 (10 CN and 10 AD). If the resulting 1 . 0 < g (i.e., the confidence in the obtained grade is low), the size of the used training library is increased by 20 to N=40 (20 CN and 20 AD). This process is repeated until 1 . 0 > g or N>80. The sign of the final grading value is used to estimate the pathological status of the testing subjects. Finally, the success rate of the patient classification is provided to demonstrate the robustness of the proposed new biomarker.

Comparison of biomarkers for patient classification with AD: The last part of our validation framework is the comparison of two biomarkers (HC volume and HC grade) and the investigation of their combination. The segmentations obtained at the same time as the grading were used to obtain the HC volume for each of the subjects in the test dataset. Through a leave-one-out procedure, each subject was classified by using optimal boundary separating both populations. This optimal boundary was obtained by performing a linear discriminant analysis over the 99 remaining subjects. This approach was applied to volume-based classification, grade-based classification and the combination of both volume and grade. The success rate (SR), the specificity (SPE), the sensitivity (SEN), the positive predictive value (PPV) and negative predictive value (NPV) are presented for each of the tested biomarkers (see [START_REF] Cuingnet | Automatic classification of patients with Alzheimer's disease from structural MRI: A comparison of ten methods using the ADNI database[END_REF] for details on these quality metrics).

Results

Table 1 shows the segmentation accuracy obtained on the seed dataset by using N=16 training subjects (8 CN and 8 AD). For the CN population, the median Dice's Kappa was similar to the Dice's Kappa presented in [START_REF] Coupe | Patchbased segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF] on healthy young subjects from the ICBM database, which demonstrates the robustness of the segmentation method. A lower median Dice's Kappa value was obtained for the AD population. A median Dice's Kappa value superior to 0.8 indicates a high correlation between manual and automatic segmentations, and a median Dice's Kappa value superior 0.88 is similar to the highest published values in literature [START_REF] Collins | Towards accurate, automatic segmentation of the hippocampus and amygdala from MRI by augmenting ANIMAL with a template library and label fusion[END_REF][START_REF] Lotjonen | Fast and robust multi-atlas segmentation of brain magnetic resonance images[END_REF]. The difference between populations might come from two sources. First, the higher anatomy variability of patients with AD makes the segmentation more difficult and may require a larger training library. Second, the smaller HC volumes of patients with AD, due to the HC atrophy, can negatively bias the Dice's Kappa index measure. Finally, these results indicate that a similar accuracy can be expected during the segmentation propagation step to the 100 subjects of the test dataset. Figure 2 shows the grading maps obtained for 2 test subjects (1 CN and 1 AD). The corresponding average grading values and the estimated volumes are also provided for left and right HC. While the volume of HC is similar for these 2 subjects, and thus does not allow an efficient patient classification, their grading values provide a useful indication on their pathological status. Visually, the CN subject clearly appears closer to the CN population (mainly red color related to values close to 1) while the AD patient is visually closer to the AD population (mainly purple and black colors related to values close to -1). Finally, Fig. 2 also provides a visual assessment of the quality of the segmentation propagation on the test dataset. For a given subject, the segmentation and the grading maps were obtained in less than 5 minutes using a single core of an Intel Core 2 Quad Q6600 processor at 2.4 GHz with N=20.

Table 2 presents the results of the patient classification for the different biomarkers under consideration. These results clearly demonstrate the advantage of using the grading approach (89% of success rate) compared to the classical volumetric approach (78% of success rate). The SEN, SPE, PPV and NPV obtained by our grading approach were higher than the ten methods compared in [START_REF] Cuingnet | Automatic classification of patients with Alzheimer's disease from structural MRI: A comparison of ten methods using the ADNI database[END_REF] involving Voxel-Based Morphometry (VBM), cortical thickness, HC volume and HC shape. The higher SR of our volumetric approach compared to the results presented in [START_REF] Cuingnet | Automatic classification of patients with Alzheimer's disease from structural MRI: A comparison of ten methods using the ADNI database[END_REF] might come from differences in the test dataset used here or due to a higher accuracy and consistency of the segmentation method used compared to [START_REF] Chupin | Automatic segmentation of the hippocampus and the amygdala driven by hybrid constraints: method and validation[END_REF]. It is also interesting to note that the optimal boundaries found by linear discriminant analysis provided similar results as using 0 as threshold value as in the previous experiment (see Fig 1.).

Finally, using the volume and the average grade of the HC simultaneously provides a very high success rate of 90%.

CN subject (ID 23)

Conclusion

In this paper, a new method is proposed to robustly detect the hippocampal atrophy patterns accruing during AD. Based on a nonlocal means estimation framework, the proposed novel grading measure (i.e., the atrophy degree in AD context) enables an accurate distinction between CN subjects and patients with AD leading to a success rate of 89% when used alone, and 90% when combined with HC volume. These results are competitive compared to the AD detection performance of VBM, cortical thickness, HC volume and HC shape methods extensively compared in [START_REF] Cuingnet | Automatic classification of patients with Alzheimer's disease from structural MRI: A comparison of ten methods using the ADNI database[END_REF]. In contrast to these approaches, our method has the advantage of simplicity (it can be coded in few hundred lines of code), low computational cost (does not required non-rigid registration), robustness of the process (all the subjects get final grading maps) and the possibility to achieve individual classifications based on a single time point contrary to group classification or longitudinal studies. These first results are promising and indicate that the new HC grading approach could be a useful biomarker to efficiently detect AD. Further work will investigate the possibility to discriminate population of patients with Mild Cognitive Impairment (MCI) compared to AD or CN.

Figure 1

 1 Figure 1 shows the final grading values for the 100 subjects of the test dataset. In the perfect case, the 50 first subjects (CN) should have positive average grading values and the 50 last (AD) should have negative average grading values. As shown in the graph, the success rate of the classification was 89% (5 false positive CN and 6 false negative AD).Figure 1 also presents the size of the used training library for each of the testing subjects. Most of the test subjects were classified by using only N=20 training subjects. Around 5% of test subjects seem to require larger training library (i.e., N>80) since at the end of the procedure g is still inferior to 0.1.

  Figure 1 shows the final grading values for the 100 subjects of the test dataset. In the perfect case, the 50 first subjects (CN) should have positive average grading values and the 50 last (AD) should have negative average grading values. As shown in the graph, the success rate of the classification was 89% (5 false positive CN and 6 false negative AD).Figure 1 also presents the size of the used training library for each of the testing subjects. Most of the test subjects were classified by using only N=20 training subjects. Around 5% of test subjects seem to require larger training library (i.e., N>80) since at the end of the procedure g is still inferior to 0.1.

Figure 1 .

 1 Figure 1. Left: the final average grading values obtained for the test dataset. Right: the used size of training library (i.e., N) for all the testing subjects.

Figure 2 .

 2 Figure 2. Top: the obtained grading map for one CN subject (ID 23). Bottom: the obtained grading map for one AD patient (ID 72). The slices of both subjects have the same position in the stereotaxic space. Red color indicates a grading close to 1 (i.e., CN) and black color indicates a grading close to -1 (i.e., AD).

Table 1 :

 1 Median Dice's Kappa values (with the standard deviation) obtained on the seed dataset composed of 20 MRI (10 CN and 10 AD) with manual segmentations.

	Median Dice's Kappa	Left HC	Right HC	Both HC
	(standard deviation)
	CN population	0.891 (0.035)	0.866 (0.038)	0.883 (0.037)
	AD population	0.830 (0.042)	0.858 (0.035)	0.838 (0.038)

Table 2 :

 2 Results of the patient classification (AD vs CN) for the different biomarkers under investigation. These results were obtained by using linear discriminant analysis through a leave-one-out procedure on the test dataset.

	AD vs. CN	SR	SEN	SPE	PPV	NPV
	HC volume	78%	72%	84%	82%	75%
	HC grading	89%	86%	92%	91%	87%
	HC volume and grading	90%	88%	92%	92%	88%