Jonas Tidström
email: tidstrom@kth.se

Marie Ericsson

Erik Sjöqvist

L Mauritz Andersson

Open-system effects on

Keywords: numbers: 03.65.Yz, 42.50.Gy, 42.65.An

I. INTRODUCTION

A medium that is opaque to radiation on one of the transitions of a Λ-system can be made transparent by addressing a laser field on the second transition, a phenomenon known as electromagnetically induced transparency (EIT) [1,2]. Associated with this transparency is an extremely small and dynamically controllable group velocity [3]. The pulse can be brought to a complete stop and stored as an atomic coherence. Most impressive with respect to storage time, is perhaps the storage of a light pulse in a solid for a period greater than one second [4]. The process can be reversed, and the light pulse released with the original pulse information intact [5], making the EIT mechanism a strong candidate to build a quantum memory [6]. Beside applications in quantum information processing, the narrow spectral feature of EIT is an important tool in spectroscopy [7], high precision magnetic sensors [8], and atomic clocks [9,10]. Furthermore, the slow light phenomena can be used for optical delay lines and light storage, but there is a trade-off between the delay of a pulse and the bandwidth [11]. In order to increase the bandwidth, spatially dispersed light beams in non-isotropic media can be used [12].

The above effects depend crucially on the coherence properties of the Λ-system [13]. The dark state superposition, central to the EIT mechanism, is fragile to external influences. This motivates to study open system effects in the dynamics of this system. Open system effects suppress the dark state of the system and thus set the ultimate limit on the storage time of light, the absorption, and the spectral resolution of the transparency. There are tricks that one can play in order to increase the efficiency of this coherence effect. In, for example, Ref. [4] the effective decoherence rate was decreased by a method called quantum bang-bang dynamic control, inspired by refocusing techniques in nuclear magnetic resonance [14].

In this paper, we investigate various types of interactions between the Λ-system and a Markovian environment modeled by the Lindblad-Kossakowski equation [15,16]. Using the coherence vector formalism [17,18] we find the asymptotic states (t → ∞) for the Λ-system and derive an analytical expression for the corresponding optical response, i.e., the susceptibility of the medium, due to the dephasing, depolarization, and three different amplitude damping channels acting on the two lower states. Effects due to open system interactions are relevant in many experimental instances and depends on the detailed structure of the system, the environment, and the interaction; for possible configurations see, e.g., [19,20]. The approach used here for treating open system effects is general and provides an option for visualization of the system response.

The outline of the paper is as follows. Section II contains a general theory for a Markovian dynamics in a threelevel system using coherence vector formalism. In Section III, we apply this framework to a Λ-system undergoing open system dynamics corresponding to dephasing, depolarization, and amplitude damping channels. The results are presented in Section IV. We give a geometrical visualization of different projections of the steady state solution to the coherence vector when different open systems effects are applied. We derive an analytical expression for the susceptibility in the presence of the open system effects. The paper ends with the conclusions.

II. OPEN THREE-LEVEL SYSTEM

Let us begin by studying a general three-level quantum system and the effects due to the interaction with a Markovian environment. In this case, the density operator ρ satisfies the master equation

∂ t ρ = 1 i [ Ĥ, ρ] + L(ρ), ( 1
)
where Ĥ is the Hamiltonian operator. The Liouville superoperator L is linear, describes the coupling with the environment, and can be written on Lindblad form [15] L

(ρ) = k (γ k ργ † k -1 2 γ † k γk ρ -1 2 ργ † k γk ), (2)
where γk are Lindblad operators, and the subscript k denotes the open system channels.

For a two-level system it is customary to use a coherence vector representation, called a Bloch-vector representation. Similarly, for a three level system we can write the density matrix ρ and Hamiltonian matrix H in a vector form as [21]

ρ = 1 3 1 + x • λ, H = ω 0 1 + ω • λ. (3)
Here, we have introduced the coherence vector x = x i e i (repeated indices summed from now on), the torque vector ω = ω i e i associated with the Hamiltonian and the SU(3) matrix generators λ = λ i e i . The basis {e i } 8 i=1 is real and orthonormal. We have used the standard scalar product ' • ', and 1 is the 3 × 3 identity matrix. We use the traceless Gell-Mann matrices {λ i } 8 i=1 as defined in Ref. [22]. The length of the coherence vector is 0 ≤ |x| 2 ≤ 1/3, with |x| 2 = 1/3 for pure states and |x| 2 = 0 for maximally mixed states.

By inserting Eq. (3) into Eq. ( 1) we obtain

ẋ • λ = 1 i [ω • λ, x • λ] + 1 3 L(1) + L(x • λ), (4)
i.e., the dynamics reformulated in terms of Gell-Mann matrices. The non-zero form of the Lindblad operators γk is written as γk . = g 0 1 + g k • λ, where the symbol ' . =' stands for 'represented by'. In this paper we will not consider the contribution from g 0 as this term always can be interpreted as an extra contribution to the Hamiltonian [START_REF]Adding a term g0 1 to γk yields the change L(ρ) → L(ρ) -i[Im(g0g * k ) • λ, ρ], which corresponds to the effective change H → H + Im(g0g * k ) • λ in the Hamiltonian[END_REF]. Thus, we focus on the 'Lindblad vectors' g k .

In Appendix A, we obtain a λ-independent form of Eq. ( 4). As a result we obtain the complete dynamics of the system, including open system effects, as an inhomogeneous differential equation [START_REF] Lidar | [END_REF] ẋ = M x + b (5) with the evolution matrix M and vector b explicitly give in Appendix A. For time-independent and invertible M , the general solution of Eq. ( 5) takes the form [17,21] x = e Mt x 0 -M -1 b,

where x 0 = x(0) + M -1 b, x(0) being the initial coherence vector. The evaluation of the exponential of M is non-trivial, since M is not diagonalizable in general. To deal with this fact one may resort to the Jordan normal form of M , i.e., M = SJS -1 , where J has non-zero entries only on the diagonal and the super-diagonal, and S is an invertible matrix. Expanding the exponent in Eq. ( 6), we can write the general solution as

x = Se Jt S -1 x 0 -M -1 b. (7)
The real part of the eigenvalues {s j } 8 j=1 , s j ∈ C, of M originates from L and must be zero or negative in order to preserve non-negativity of the density operator. We now look at the eigenvectors of M . Higher-dimensional Jordan Blocks occur provided M has linearly dependent eigenvectors corresponding to degenerate eigenvalues. However, in all the cases we investigate in this paper we only identify one-dimensional Jordan blocks.

We now ask what happens for different open system effects corresponding to one-dimensional Jordan blocks. We focus on the case where we have s i∈I = 0, I being an index set, and Re(s i / ∈I ) < 0. In the t → ∞ limit, the matrix e Jt tends to the matrix P , which projects onto the subspace corresponding to I. Thus, in this limit, e Mt = Se Jt S -1 tends to the projector SP S -1 and the asymptotic coherence vector x (∞) depends on the initial coherence vector x 0 according to

x (∞) = P x 0 -M -1 b. ( 8
)
For the cases studied in this paper, I is the empty set, i.e., Re(s i ) < 0 ∀i, we have e Mt = Se Jt S -1 → 0 when t → ∞.

In this case, the asymptotic state is determined by

x (∞) = -M -1 b, (9)
thus being independent of x 0 . Further discussions on the existence and properties of asymptotic states in Markovian open quantum systems can be found in Refs. [25][26][27].

III. OPEN Λ-SYSTEM

An electromagnetic field interacting with matter gives rise to a matter polarization. The linear part of the polarization field P = P (E) can be written in terms of the electrical susceptibility χ = P/(E 0 ), with 0 the electrical permittivity in free space. The real and imaginary parts of the susceptibility describe the phase velocity of the electrical field and the absorption or gain of the field, respectively. The macroscopic polarization field of an isotropic medium consisting of N atoms per unit volume is P ≡ P = N p = N Tr[ ρ μ], where ρ is the density operator and μ = e r is the dipole operator with electric charge e and position operator r. Therefore, if ρ is known as a function of the optical field, the optical response is too, as it is given by the coherences of ρ. In this section we develop the tools to compute ρ for an open Λ-system and in the next section we find the resulting optical response χ.

The Λ-system consists of two ground state levels coupled to an excited state via electromagnetic fields, as shown in Fig. 1. The corresponding Hamiltonian is given by Ĥ(t) = Ĥ0μ • E(t), where Ĥ0 is the Hamiltonian of the bare atom, μ is the electric dipole operator, and E(t) is an oscillating electric field. Furthermore, let E i be the energy eigenvalues of Ĥ0 corresponding to the bare eigenstates |i , i = a, b, c. In a frame rotating with the external field, the Hamiltonian operator reads

Ĥ = δ b |b b| + δ c |c c| -Ω b |a b| -Ω c |a c| + h.c., (10)
where we have used the rotating wave approximation and we have defined the complex Rabi frequencies in terms of the electric field E in the rotating frame as Ω i = a| μ|i • E/(2 ) and detunings 3) are given by

δ i = ω i -(E a -E i )/ ,
ω 0 = 1 3 Tr[H] = 2 3 ∆, ω = 1 2 Tr[Hλ i ]e i = δe 3 -|Ω b | cos φ b e 4 -|Ω b | sin φ b e 5 -|Ω c | cos φ c e 6 -|Ω c | sin φ c e 7 - 1 √ 3 ∆e 8 , (11)
where Ω i = |Ω i | exp(iφ i ) and we have defined the two-photon detuning δ = (δ b -δ c )/2 as well as the mean detuning ∆ = (δ b + δ c )/2. We now specify the Lindblad operators that describe the different forms of open system dynamics. Spontaneous emission corresponding to the amplitude damping of the excited energy state |a to either of the two ground states |b or |c with rates γ b and γ c is assumed to be always present. The corresponding Lindblad operators and their matrix representation read

γb = √ γ b |b a| . = 1 2 √ γ b (λ 4 + iλ 5 ), γc = √ γ c |c a| . = 1 2 √ γ c (λ 6 + iλ 7 ), (12)
and they define the natural line width γ ≡ γ b + γ c indicated in Fig. 1. The subscripts b and c indicate the final quantum state of the atom after interaction with the environment through the decay channel. The corresponding Lindblad vectors are

g b = 1 2 √ γ b (e 4 + ie 5 ), g c = 1 2 √ γ c (e 6 + ie 7 ). ( 13
)
These vectors are complex-valued and therefore C (-) in Eq. (A10) is non-vanishing and, accordingly, the decay channel contributes to the dynamics, Eq. ( 5), with a non-zero b.

The dark state of the Λ-system is

|d = 1 |Ω b | 2 + |Ω c | 2 (Ω * c |b -Ω * b |c ). (14)
This is an eigenstate of the Hamiltonian, which is unaffected by the decay channels defined by Eq. (12). The additional open system effects that we are primarily interested in are the ones that act on the two-dimensional subspace V bc = {|b , |c }, since these could potentially destroy the dark state and the associated phenomena. We consider the limit of a weak probe field and a strong control field, i.e., |Ω b | |Ω c |, hence the dark state will be close to |b .

Although a continuum set of channels is necessary to fully cover all possible cases [28,29], it is known [START_REF] Nielsen | Quantum computation and quantum information[END_REF] that depolarization, dephasing, and amplitude damping constitute a set of channels that captures essential features of open system effects for two-level systems. Here, we examine these channels acting on V bc . Depolarization and dephasing are particular combinations of the Hermitian Lindblad operators

γx = √ η x (|b c| + |c b|) . = √ η x λ 1 , γy = √ η y (-i|b c| + i|c b|) . = √ η y λ 2 , γz = √ η z (|b b| -|c c|) . = √ η z λ 3 , (15)
where the symbols η k are used to denote rates of the various channels acting on V bc . The corresponding Lindblad vectors are real and given by

g x = √ η x e 1 , g y = √ η y e 2 , g z = √ η z e 3 . (16)
The depolarization channel is isotropic, i.e., corresponds to η x = η y = η z ≡ η/3. The dephasing channel, on the other hand, is anisotropic and corresponds to η x = η y = 0, η z = 0. Neither depolarization nor dephasing contribute to b since C (-) vanishes.

As already stated, the dark state is close to |b when the intensity of the probe field is much smaller than the intensity of the control field. Because of this we expect a non-vanishing amplitude damping b ← c to influence the Λ-system in a different manner as compared to the channel c ← b. To examine this quantitatively, we study the following channels

γbc = √ η bc |b c| . = 1 2 √ η bc (λ 1 + iλ 2 ), γcb = √ η cb |c b| . = 1 2 √ η cb (λ 1 -iλ 2 ), (17)
where γbc flips |c to |b at a rate η cb and vice versa for γcb . The corresponding Lindblad vectors read

g bc = 1 2 √ η bc (e 1 + ie 2 ), g cb = 1 2 √ η cb (e 1 -ie 2 ), (18)
which are complex-valued and may therefore contribute to b.

The evolution matrix M and the vector b are obtained by summing the contributions from the above described open system channels. We may write the resulting M in a simple form by applying the following similarity transformation

M = R -1 M R, (19)
where

R
The transformed evolution matrix M takes the block structure form

M = A C -C T B ( 21
)
with the submatrices

A =     -Re(Γ) -Im(Γ) 0 0 Im(Γ) -Re(Γ) 0 0 0 0 -η + η --γm √ 3 0 0 0 -2γ     , B =    -Re(Γ -) -Im(Γ -) 0 0 Im(Γ -) -Re(Γ -) 0 0 0 0 -Re(Γ + ) -Im(Γ + ) 0 0 I m ( Γ + ) -Re(Γ + )    , C =     |Ω c | sin φ c -|Ω c | cos φ c |Ω b | sin φ b -|Ω b | cos φ b √ 3|Ω b | cos φ b √ 3|Ω c | sin φ c - √ 3|Ω c | cos φ c     . (22)
Here, we have introduced the parameters

γ m = γ b -γ c , η ± = η bc ± η cb , Γ = 2iδ + (η + + 8η + 4η z )/2, , Γ ± = i(δ ∓ ∆) + γ ± , γ ± = γ + (6η + 2η z + η + ± η -)/4. ( 23
)
The diagonal elements of M are real and negative, and contain the open system rates. The only off-diagonal element containing open system effects is (η --γ m )/ √ 3 in A. They are non-vanishing if the amplitude damping rates in V bc , and also if the decay rate from the exited state to the ground states, are unbalanced. This fact also influences b, which is explicitly given by b

= 2η -+ γ m 6 e 3 + γ 2 √ 3 e 8 . (24)
Thus, b is non-vanishing if damping processes are present in the open system dynamics.

IV. RESULTS

We begin by analyzing the asymptotic state of the quantum system as represented by the coherence vector x (∞) . The use of the asymptotic coherence vector is justified by its relation to measurable quantities. For instance, two of its components determine the real and imaginary parts of the induced electric polarization according to

P ab = Nµ ab ρ (∞) ab = Nµ ab (x (∞) 4 + ix (∞) 5
), from which the susceptibility of the probe field can be found. In Fig. 2, we show the projection of the eight-dimensional coherence vector space onto three-dimensional cuts for the cases of depolarization and amplitude damping c ← b channels, and compare with the ideal case where decay of the excited state |a to the two ground states |b and |c are the only open system effects present. The two parameters spanning the surface are the probe field strength Ω b and the two photon detuning δ; the control field strength Ω c is held constant.

The components x 1 , x 2 , and x 3 shown in Fig. 2(d-f), concern the coherence of the asymptotic state in the V bc subspace. Components 1 and 2 are the real and imaginary part of the coherence ρ bc , i.e., they describe the phase relation between the |b and |c amplitudes of the asymptotic state. The third component x 3 is the corresponding population balance. Fig. 2(d) shows the ideal case at zero detuning. Here, x 1 is negative, x 2 is zero, and x 3 is close to 0.5. This is precisely the dark state with a real and negative coherence between the |b and |c amplitudes, and most of the population in |b . For non-zero detuning, we can visualize how the dark state deteriorates, by inspecting the entire surface. Depolarization is added in Fig. 2(e). In this case, we see how the x 3 component radically changes towards a more balanced population and the magnitudes of the coherences x 1 and x 2 decrease, as compared to the ideal case. This can be understood physically as the depolarization channel drives the system towards a balanced mixture in the V bc subspace. Similar effects occur for the case of the c ← b channel, shown in Fig. 2(f).

The components x 3 , x 4 , and x 5 shown in Fig. 2(a-c) are directly related to the optical response of the atom to the probe field. A zero detuned ideal case is characterized by vanishing x 4 and x 5 . This implies that the electric polarization vanishes, clearly demonstrating the EIT effect. By adding depolarization, the x 5 component becomes positive at zero detuning and therefore absorption is present, as shown in Fig. 2(b). The c ← b amplitude damping channel, shown in Fig. 2(c), gives rise to a negative x 5 component, corresponding to probe field gain.

Let us now examine the susceptibility for a small probe field that interacts with a medium consisting of a collection of Λ-systems that in turn are affected by the open system channels considered in Sec. III. The susceptibility [START_REF] Boyd | Nonlinear optics[END_REF], of a medium is related to the asymptotic state of the atomic coherence ρ

(∞) ab = x (∞) 4 + ix (∞) 5
, which can be calculated by Eq. ( 9) using Eqs. ( 21) and [START_REF] Lidar | [END_REF]. Explicitly,

χ = lim Ω b →0 κ ∂ ∂Ω b ρ (∞) ab (25)
with κ = N | a| μ|b | 2 /(2 0 ), and we recall that the Rabi frequency is defined in a non-standard way with an extra factor of 2 for notational convenience. The expression of the susceptibility in Eq. ( 25) holds in the limit of a small probe field. Furthermore, we recall that the real part of the susceptibility is related to the phase evolution of the optical field, while the imaginary part describes the absorption or gain.

The open system channels defined by the Lindblad vectors in Eqs. ( 13), (16), and ( 18), change the properties of the Λ-system in a nontrivial way. The susceptibility in the general case can be calculated from Eq. ( 9) and we find

χ = iκ γ/2 η -+ η + |Γ + | 2 Γ * + γ + γ m + 2η -Re(Γ + )Γ * + γ(η --η + )Γ * + |Ω c | 2 Γ * -Γ * + |Ω c | 2 γη + |Γ + | 2 + γ + γ m -η -+ 3η + Re(Γ + )|Ω c | 2 , ( 26
)
where the parameters are defined in Eq. ( 23). It should be noted that this expression contains all information of the detunings and phases of the optical fields, as well as the effects due to any combination of depolarization, dephasing, and b ↔ c channels. Hence, the linear susceptibility of the probe field is obtained for any point in parameter space spanned by all of the above mentioned parameters, assuming only the validity of the Lindblad equation and the rotating wave approximation.

In the following we use Eq. ( 26) to study the susceptibility due to the different open system effects. The analytical expressions below are retrieved from Eq. ( 26) as special cases by setting all channel rates except one to zero. We assume the non-zero channel rate η k to be much smaller than the decay rate, i.e., η k γ, and a Rabi frequency strong enough to establish EIT, i.e., η k γ |Ω c | 2 . Furthermore, we assume zero mean detuning ∆ = 0, a balanced decay γ m = 0, and that the two-photon detuning is not much larger than |Ω c |.

In Figs. 3(a) and 3(b) we show the susceptibility for different open system channels, using the same rate for all open system channels. Since the susceptibility is a complex function, the real and imaginary parts are plotted separately. Note that in the figures we use the exact expression in Eq. (26). If we put all channel rates to zero except η z we obtain the susceptibility

χ dephase = κ 2δ + 2iη z |Ω c | 2 -δ(2δ + iγ) . (27)
This expression for the susceptibility is frequently encountered in the literature, see, e.g., Ref. [START_REF] Scully | Quantum optics[END_REF].

If we put η -= η + = η bc = 0 we find the susceptibility of a medium that effectively takes population from |c to |b . We have,

χ b←c = κ 2δ + iη bc /2 |Ω c | 2 -δ(2δ + iγ) . (28)
This expression for the susceptibility is also frequently encountered in the literature, see, e.g., Ref. [START_REF] Gea-Banacloche | [END_REF]. It is interesting to note the similarity of this expression with Eq. (27), although the open system channels are quite different. Nevertheless, in Figs. 3(a) and 3(b) it can be seen that the phase response of χ b←c is larger than for χ dephase . This means that a medium affected by pure dephasing cannot slow down light as efficiently as compared to a medium affected by the b ← c channel, assuming that the channel rates are equal. We now consider the amplitude damping channel in the c ← b direction. The expression of the susceptibility in this case reads

χ c←b = κ 2δ -iη cb /2 |Ω c | 2 -δ(2δ + iγ) . ( 29
)
This channel shows a different behavior compared to all other considered channels, it shows gain where the other channels show absorption. That is, a slowly propagating light pulse will be amplified due to the interaction with the environment described by the c ← b channel.

Let us now consider amplitude damping channels with equal rates in both directions in the subspace V bc , corresponding to the non-zero parameters η bc = η cb ≡ η pe . This open system channel may be important in experimental situations where, e.g., atoms collide and the populations of the states undergo sudden incoherent exchange. We denote this as the population exchange channel 'popex'. We obtain,

χ popex = κ 2δ + iγη 2 pe /(8|Ω c | 2 ) |Ω c | 2 -δ(2δ + iγ) . ( 30
)
As expected, the absorption profile is located in between the profiles of χ b←c and χ c←b , as can be seen in Fig. 3

(b).

To first order, the absorption profiles of the different amplitude damping channels is shifted by the parameter η -. However, the phase response, i.e., Re (χ b←c ) is not affected by this shift, and it is approximately the same for all considered amplitude damping channels. The susceptibility associated with the isotropic depolarization channel (η = 0) is given by

χ depol = κ 2δ + 2iη/3 |Ω c | 2 -δ(2δ + iγ) . (31)
In experiments, e.g., where one uses laser beams and hot atomic gases, this open system interaction is relevant as it corresponds to coherently prepared atoms leaving the laser beam, replaced with atoms in a completely mixed quantum state. The susceptibility is plotted in Fig.

(3) and it can be seen that the phase response Re (χ depol ) is located between the corresponding curves for the dephasing and the amplitude damping channels. Furthermore, the absorption curve Im (χ depol ) is close to the absorption profile of the depolarization channel, but significantly smaller than the corresponding curves for the dephasing and b ← c channels. With respect to absorption and phase response, the depolarization channel is therefore not as harmful as the dephasing channel. When there is no open system interaction on V bc we retrieve the ideal susceptibility,

χ ideal = κ 2δ |Ω c | 2 -δ(2δ + iγ) , (32)
included in Fig. (3) as a reference.

Often one is interested in achieving the slowest possible group velocity in a medium consisting of Λ-systems. The slow-down factor, or group index, is proportional to the derivative of the real part of the susceptibility n g ≡ ω∂ δ Re (χ) /2 at angular frequency ω. To compare the absorption for a given slow-down factor at δ = ∆ = 0 we normalize the channel rates to give the same slow-down factor. Approximating ∂ δ χ for small channel rates in V bc gives

∂ δ Re (χ) δ=∆=0 ≈ κ 2|Ω c | 2 -γ 8η 3 + η bc + η cb + 2η pe + 4η z |Ω c | 4 (33)
thus, the normalized rates are η z = η bc /4 = η cb /4 = η pe /2 = 2η/3. Using these normalized rates, we plot the slowdown factor as a function of the control field in Fig. 3(c) to verify that they are equal. The absorption coefficient is defined as α = (2π/λ)Im (χ). In Fig. 3(d) we show the absorption on two-photon resonance as a function of the control field. We see that the different open system channels give different absorption profiles, even though the slow-down factors are equal in this regime. Furthermore, it is interesting to note that the dephasing and the b ← c amplitude damping channels, with normalized channel rates, have identical absorption characteristics. We see that the isotropic depolarization and population exchange channels are quite similar in Fig. 3(d), but more essentially, they have a lower absorption than the dephasing and the b ← c amplitude damping channels. As already mentioned, the c ← b damping is special in that it yields a gain where the other channels yield absorption of the probe field.

V. CONCLUSIONS

We analyze a three-level Λ-system interacting with a Markovian environment. The Lindblad master equation is reformulated using the Gell-Mann matrices as a basis. We rewrite this in a convenient vector formalism that is independent of the specific matrix representation of the SU(3) generators. An evolution matrix corresponding to this vector form is worked out in detail and the dynamics is written as an affine-linear matrix differential equation. The general solution of this equation can be given in terms of the Jordan normal form. The Jordan blocks of the evolution matrix are generically one-dimensional and the real part of the spectrum is negative. From this follows that the asymptotic solution in all cases we are interested in are independent of the initial states and given by the inverse of the evolution matrix multiplied by a vector that is given by the open system interaction.

The linear optical response of a quantum system is given by the asymptotic steady state solution of the evolution equation. We find an explicit and closed analytical form of the susceptibility for general open system dynamics, including pure dephasing, depolarization, and three different forms of amplitude damping channels.

The open system effects introduce a non-trivial behavior of the linear optical response of the Λ-system. For example, we show that the isotropic depolarization channel is less detrimental to the induced transparency and the corresponding slow-down effect, than is pure dephasing. Furthermore, an amplitude damping channel can lead to reduced absorption and even gain for the probe field.

FIG. 1 :

 1 FIG.1: The Λ-system. The field on the a-b transition is the weak probe field Ω b , and the field on the a-c transition is the control field Ωc. The upper level is broadened by the finite lifetime 1/γ.

  where ω i are the frequencies of the field. Note the factor 1/2 in the definition of |Ω i |, introduced for notational convenience. Defining the Gell-Mann matrices in terms of the basis ordered as {|b , |c , |a }, the parameters of the Hamiltonian matrix in Eq. (

FIG. 2 :

 2 FIG. 2: Plots of the asymptotic state for two different cuts through the eight dimensional coherence vector space is shown: x4, x5, x3 coordinates of the asymptotic state in (a-c) and x1, x2, x3 coordinates of the asymptotic state in (d-f). Different open system channels are shown: ideal case in (a,d), depolarization η = 0.2 in (b,e), and amplitude damping c ← b channel η cb = 0.2 in (c,f). Radial mesh corresponds to changing Ω b from 0 to 0.1 in steps of 0.02, tangential mesh corresponds to the two-photon detuning -5 to 5 in steps of 0.5; the exception is (a) where the interval is given between -5 to 0. Other parameter values are Ωc = 1, γ = 1 and ∆ = 0.

FIG. 3 :

 3 FIG. 3: (Color online) In (a) and (b) we show the real and imaginary part of the susceptibility. In (c) and (d) the slow-down factor (group index) ng and absorption α at two-photon resonance, are shown as a function of the control field |Ωc|. The thin black line shows the case of no open system interaction on V bc . The thick gray line shows the dephasing channel and the thick black line shows the depolarization channel. The remaining lines describe three versions of the amplitude damping channel: the wide-dashed (blue) line shows the b ← c damping channel, the dashed (red) line shows the c ← b damping channel, and the dash-dotted (green) line shows the population exchange channel (popex), i.e., the incoherent sum of the two damping channels with equal rate. In all plots the proportionality factor κ defined below Eq. (25) is scaled to 1. In (a) and (b) the parameter values are |Ωc| = 0.16, γ = 1, ∆ = 0, and all non-zero channel rates are set equal to 0.1. In (c) and (d) the channel rates are normalized so that the slow-down factors are matched.

Acknowledgments

M.E., E.S., and L.M.A. acknowledge the Swedish Research Council for financial support. E.S. acknowledges support from the National Research Foundation and the Ministry of Education (Singapore).

APPENDIX A

In this Appendix, we provide a detailed derivation of the evolution matrix M and the vector b for Lindblad-type master equations of a three-level system. Define the vector products

where α = α q e q and β = β q e q are arbitrary complex-valued vectors, {e i } 8 i=1 is a real orthonormal basis of R 8 , f rst and d rst are the antisymmetric and symmetric structure constants of the SU(3) algebra [22], and we have used Einstein's summation convention (repeated indices are summed). The wedge product '∧' is a higher-dimensional vector product analog to the cross-product in three-dimensional space. The star product ' ' is a vector product that has no counterpart in three dimensions.

Equipped with these tools we may now rewrite each term in the right-hand side of Eq. ( 4). First, the Hamiltonian contribution reads

Secondly, the middle term of Eq. ( 4) is readily evaluated as

where each term g k ∧ g * k is purely imaginary, and hence L(1) is real as required. Note that, for Hermitian γk the corresponding vector g k is real and thus g k ∧ g * k = 0. By using the symmetries of the structure constants the last term of Eq. ( 4) takes the form

By identifying terms, we arrive at the full Lindblad master equation in coherence vector form

It should be emphasized that this expression is valid for any N -dimensional quantum system provided the SU(N ) structure constants are being used in the definition of the vector products ∧ and . Next, define

We can put the equations of motion on the affine-linear matrix differential equation form in Eq. ( 5) by combining Eqs. (A1) and (A6). This yields

where k represents different open system channels. Here,

with


M P Juniper

B Pier

Giannetti Luchini

Structural sensitivity calculated with a local stability analysis

calculate the structural sensitivity of the steady, but unstable, planar flow behind a cylinder at Re = 50. This reveals that the instability is driven by two regions of the flow, which are situated on either side of the recirculation bubble. This agrees well with the experimental data of Strykowski and Sreenivasan 2 .

The structural sensitivity is obtained by combining two global modes of the flow. The first is the direct global mode, which is obtained by linearizing the Navier-Stokes equations and then calculating the most unstable 2D eigenfunction of that operator. The second is the adjoint global mode, which is obtained from the adjoint linearized Navier-Stokes equations via a second, similar, calculation.

In flows that evolve slowly, the direct global mode can be obtained with a local stability analysis 3 , which is less computationally-expensive than calculating the 2D eigenfunction.

In this paper we show that, without further calculations, the local stability analysis also gives the adjoint global mode. In brief, the direct and adjoint global modes both have the same global frequency, the same wavemaker position and the same k + and k - branches. The direct global mode is calculated from the k -branch upstream of the wavemaker position and the k + branch downstream. We show that the adjoint global mode is calculated from the k + branch upstream and the k -branch downstream. These global modes can then be combined, following the method of Giannetti and Luchini, to give the structural sensitivity of the flow.

.

Figure 1 :

 1 Figure 1: Arrows: velocity vectors of a confined wake flow at Re = 100. Contours: the structural sensitivity of this flow, calculated with a local stability analysis.


Simona Noveanu
email: simona.noveanu@mmfm.utcluj.ro

Vencel I Csibi
email: csibiven@yahoo.com

Ioan Alexandru Ivan

Dan Mandru
email: dan.mandru@mmfm.utcluj.ro

A I Ivan

D Mândru

Design

Keywords: Mini-system, compliant mechanism, piezoelectric actuator

come

Introduction

The field of micromechanical devices is extremely broad. It encompasses all of the traditional sciences and engineering disciplines, only on a smaller scale. A distinctive feature of micro-electro-mechanical systems technology is miniaturization.

Mini-systems are diverse and complex and the trends indicate that it is appropriate to configure small-scale systems somewhat differently from those which we are familiar with. Simply downsizing from dimensions is not possible because of the scaling effect. This is due to the fact that the types of forces that are dominant in miniaturized devices are different from those that are dominant in macro-scale devices. For large-scale systems, inertial effects have a greater influence while surface effects influence smaller-scale systems. Being small, micro-systems are able to produce small forces only, [START_REF] Fatikow | Microsystems Technology and Microrobotics, (Series: The Mechanical Engineering Handbook)[END_REF][START_REF] Lobontiu | Mechanics of microelectromechanical systems[END_REF]. In particular, there are used materials with special properties.

The size of a system and the physical parameters will be modified with a scale factor S. When the scale size changes, all the dimensions of the object change by exactly the same amount S such that 1: S. This scale factor S can be used to describe how physical phenomena change. Knowing how a physical phenomenon scales, whether it scales as S 1 or S 2 or S 3 , or S 4 or some other powers of S, guides our understanding of how to design small mechanical systems [START_REF] Gad-El-Hak | Series: The Mechanical Engineering Handbook[END_REF].

Miniaturization of the mechanical structure alone is insufficient so that many devices may work together, so microelectronics needs to be incorporated in the system.

The reduced dimensions imply different manufacturing technologies, measuring and control techniques and specific actuation methods based on new types of actuators. Their actuation effect is achievable through three different means: fields interaction, mechanical interaction and induced limited strain. The actuators in the last category include elements made of so called intelligent or smart materials: piezoelectric and magnetostrictive materials, electro/magnetorheological fluids, electroactive polymers, shape memory alloys, [START_REF] Mândru | Actuating Systems in Precision Mechanics and Mechatronics[END_REF].

The structure of the mini-system

The researched mini-system contains a mechanical part, represented by a compliant monoblock-type minigripper which is actuated by a piezo actuator.

In order to command and control the mini-system with DSpace data acquisition board, it is made a Simulink model that generates the command signals using the Signal generator blocks. The signals type can be: step, sinusoidal, ramp, impulse, a.s.o. Viewer in real-time behaviour of the system will be through the Control Desk application.

The proposed mini-system includes the following modules [START_REF] Noveanu | Contributions concerning the study of compliant mechanisms specific to mechatronic systems[END_REF] (Fig. 1):

Fig. 1 The modules of the mini-system

The control is achieved in closed loop, with a reaction by position; it is necessary to measure the actuators displacements using suitable position sensors; the control of supply voltage of actuators is such that can obtain the exact position required by the mechanism action.

Piezoelectric actuators

Regarding the piezoelectric materials (PZT) a tensile mechanical stress is induced that elongates and contracts the material due to the inverse piezoelectric effect, when they are placed in an alternative electric field. In order to amplify the actuators stroke, the stack and bimorph configurations are frequently used [13].

This "induced strain" or change in length occurs as electrical dipoles in the material rotate to align with an orientation that more closely aligns with the direction of the applied electric field. The change in length is generally proportional to the field strength as applied via the device actuation voltage [START_REF] Lobontiu | Mechanics of microelectromechanical systems[END_REF]. A typical value for length change might be 0.1 percent of the total material length in the direction of the applied field. Application of an external field E m (m stands for motor) in opposition to the poling field E p will generate an expansion of the piezoelectric sample by a mechanical deformation Δu (Fig. 2). Driving a piezoelectric actuator requires sourcing sufficient current from the driver to produce the desired electrical field or voltage level in the PZT stack. Because PZT stacks have relatively high capacitance, only a small amount of the energy delivered by the driver is used to move the load. The majority of the current applied is in the form of reactive power. Thus, the driving electronics must be able to move a relatively large amount of charge in and out of the PZT stack. This is slightly analogous to a four-quadrant drive for a DC motor with the added complication that the load is capacitive rather than resistive. Shortly, the drive electronics for a piezoelectric actuator are specialized for driving capacitive loads [13].

Mini-mechanisms

Conventional joints cannot be easily miniaturized, but using compliant mechanisms this problem can be solved. Compliant mechanisms can be miniaturized for use in simple microstructures, actuators and sensors. The monolithic construction also simplifies production, enabling low-cost fabrication, [START_REF] Noveanu | Contributions concerning the study of compliant mechanisms specific to mechatronic systems[END_REF].

The compliant mechanisms are different from the traditional rigid body mechanisms in the sense that the last ones are rigid links connected by movable joints. They are used to transfer or transform energy and motions across themselves as desired by the users. The compliant mechanism does the same work except that their usability is also dependent on flexibility of some members. Compliant mechanisms have a smaller number of movable joints materialized as rotation joints. The result is the reduced wear and reduced need for lubrication. They also result in the reduction of noise and vibration due to reduced number of components and friction movements. Backlash reduction due to a decreased number of joints increases the mechanism precision [START_REF] Lobontiu | Compliant Mechanisms: Design of Flexure Hinges[END_REF].

Several approaches have previously been or are currently being taken to the design of small-scale precision mini/microgrippers [START_REF] Bassan | Control of a rigid manipulator mounted on a compliant base[END_REF][START_REF] Havlik | Analysis and modeling flexible robotic (micro) mechanisms[END_REF][START_REF] Kota | Design and Application of Compliant Mechanisms for Surgical Tools[END_REF][START_REF] Refaat | Accurate modelling of compliant grippers using a new method[END_REF][START_REF] Voyles | Micro/macro force-servoed gripper for precision photonics assembly and analysis[END_REF]: reducing the size of macro-gripping devices; using physical phenomena; the cantilever approach; the tweezers approach; distributed actuators; linkage-free actuators; using adhesion forces. The characteristics of an ideal multipurpose minigripper are: ability to manipulate micro-objects with various sizes and shapes, ability to work in various environments (in clean rooms, in liquids, etc.), ability to apply high forces, high accuracy, low response time, isolation between the control signals and the working area, simplicity of fabrication. Are characterized by a small opening span, a saw-like tip in order to reduce adhesion forces and are equipped with position and force sensors to provide quantitative information during grasping.

The mini and micro compliant mechanisms are fabricated by exploiting different technologies (Laser Micromachining, Electro Discharge Machining, LIGA, Stereo Lithography, precision machining).

Modelling and simulation of the mini-system

The developed mini-system contains the modules presented in figure 1: a minigripper designed as a device with flexible joints, actuated by a stack piezoactuator, an amplifier for the actuator, a displacement sensor and command and control modules.

The piezoelectric actuator used, is stack type, [12] and it has a maximum stroke of 15 µm, and overall dimensions are 18 x 6.5 x 6.5 mm.

The analytical equations for displacements piezoelectric actuator [START_REF] Noveanu | Contributions concerning the study of compliant mechanisms specific to mechatronic systems[END_REF] are:

T c F L L + ⋅ ⋅ = Δ 0 ij d E (1)
where E is electric field; d ij -piezoelectric coupling coefficient; L 0 -actuator length; F -axial force; c T -rigidity

T c F L L + Δ = Δ 0 (2) T c F qU L / ) ( - = Δ (3)
where q is the factor for force and U is voltage

T c F L 0 0 = Δ ( 4 ) max 0 qU F = ( 5 )
The time for response is:

r r f t 2 1 = ( 6 )
where f r is the resonant frequency. To compensate position change, one must drive the piezoelectric actuator to a slightly different voltage in the return movement to get back to the same starting position. The value of the stroke hysteresis is a percentage of the entire commanded stroke.

The overall dimensions of the mini-gripper in the structure of the studied minisystem are 54mm x 35mm x 2.21mm, [START_REF] Noveanu | Contributions concerning the study of compliant mechanisms specific to mechatronic systems[END_REF]. The task for design is to find the geometry, with relevant dimensions in order to satisfy desired characteristics under specified constraints. These are: the range of motion for fingers, maximal external dimensions, available driving force and displacement and characteristics of material.

The solid model (Fig. 3a) and FEM analysis are realized in the linear domain, using Solid Works and ANSYS software. Fig. 3 The solid model and mesh realized for FEM analysis

The study was performed for the following applied input voltage: 0V ÷ 120V and the material used for analyze of the mini-gripper is alloy steel with: E = 2.1x10 5 N/mm 2 , Poisson's Coefficient = 0.31.

One functioning characteristic of the compliant minigripper is so-called mechanical advantage (m. a.), which is the output-to-input amplification (or deamplification) ratio [START_REF] Lobontiu | Compliant Mechanisms: Design of Flexure Hinges[END_REF][START_REF] Lobontiu | Mechanics of microelectromechanical systems[END_REF]. The mechanical advantage determined through the FEM analysis for the studied mini-gripper is 6.50.

Experimental results

Our experimental study was focussed on the time response for different input signals.

In the next figure is presented a constructive variant of a compliant minigripper in the structure of the studied mini-system (Fig. 4):

Fig. 4 The developed mini-gripper For data acquisition at the piezoelectric actuator and compliant mini-gripper, we realized the command scheme in Simulink (Fig. 5a).and the interface using ControlDesk application (Fig. 5b). The structure of the test bench for measurements contains a Laser displacement sensor LC-2420 with resolution 0.01 μm and response time 100 μs.

The stack piezoelectric actuators -AE0505D18 have following characteristics: maximum drive voltage 150 volts; operating temperature: 0°C÷45°C; capacitance: 1600 nF ÷320 nF; clamping force: 853 N; resonant frequency: 261 KHz; Young's modulus: 4.4x10 10 N/m 2 ; recommended preload less than 100 N.

The study was performed for the following inputs: voltage is 150 V and impulse signal: 0.1Hz÷100Hz (Fig. 6). ,b show that for a proper functioning, the mini-system has to be actuated with a frequency below 50Hz. Figure 6c shows that the mini-system oscillates for a frequency equal with 100Hz.

Conclusions

The paper points out some specific problems in functioning of mini-mechanical systems built on compliant mechanisms. In order to test the performance of the minigripper with piezo actuators an experimental test bench was developed. The mini-system starts to oscillate for frequency values higher than 50Hz. In conclusion, for a proper functioning, the system has to be actuated with a frequency below that value. The control is achieved in closed loop, with a reaction by position; it is necessary to measure the actuators displacements using suitable position sensors; the control of supply voltage of actuators is such that can obtain the exact position required by the mechanism action.

The mini-system can be successfully applied to the fields that need high precision in small workspace, such as: optics, precision machine tools and mini component fabrication.

In the future the aim of our work will be to down scale the mini-system analyzed in this paper.

Fig. 2

 2 Fig. 2 Piezoelectric actuation through the reversed piezoelectric effect

  The meshed body is presented in the figure 3b. a b

Fig. 5

 5 Fig. 5 The command scheme in Simulink (a) and ControlDesk application (b)

Fig. 6

 6 Fig.[START_REF] Lobontiu | Compliant Mechanisms: Design of Flexure Hinges[END_REF] The experimental results for impulse signal and different frequencies Figures6a, bshow that for a proper functioning, the mini-system has to be actuated with a frequency below 50Hz. Figure6cshows that the mini-system oscillates for a frequency equal with 100Hz.

Acknowledgments

The research work reported here was made possible by PNII -IDEI Project, ID 221: Modelling, Simulation and Control of the Compliant Micro mechanisms and PNII -ID 1076 Development of a Modular Family of Linear and Rotary Actuators Based on Shape Memory Alloys.


Benoît Pier

Nigel Peake

Global nonlinear dynamics of thin airfoil wakes

Global nonlinear dynamics of thin airfoil wakes

Benoît PIER * and Nigel PEAKE †

In the present investigation of thin airfoil wakes we compare the global nonlinear dynamics, obtained by direct numerical simulations, to the associated local instability features, derived from linear stability analyses.

In the numerical implementation, we consider a semi-infinite flow domain corresponding to the region downstream of the airfoil trailing edge, where a symmetric velocity profile is imposed represented by the double-Falkner-Skan boundary layer solutions with negative pressure gradient m. The parameter m is varied from m = 0 (double-Blasius wake) to m = -0.09 (near flow separation); Reynolds numbers up to Re = 5000 are considered. It is found that the wake gives rise to self-sustained vortex shedding provided the Reynolds number and the adverse pressure gradient are large enough. Snapshots of streamwise velocity contours in the fully developped régime at Re = 4000 for (a) m = -0.09 and (b) m = -0.08 are shown below; the associated global frequencies are ω = 0.170 and ω = 0.198.

Local stability features are computed from the corresponding basic flows. At Re = 4000, the local absolute growth rates ω 0,i and frequencies ω 0,r are given in figures (c) and (d). It is seen that absolute instability prevails in the near wake and that the spatial variations of ω 0,i strongly depend on m: the largest absolutely unstable domains and the weakest spatial variations are obtained at large (negative) values of m. The global frequency predictions 1 derived from these curves are ω = 0.162 for m = -0.09 and ω = 0.195 for m = -0.08, in excellent agreement with the above direct numerical simulations. Another feature of interest is that nonlinear saturation may occur well downstream of the absolutely unstable domain.


Adrian Ion

Yll Haxhimusa

Walter G Kropatsch

Luc Brun
email: ‡luc.brun@greyc.ensicaen.fr

Hierarchical Image Partitioning using Combinatorial Maps

We present a hierarchical partitioning of images using a pairwise similarity function on a combinatorial map based representation. We used the idea of minimal spanning tree to find region borders quickly and effortlessly in a bottom-up way, based on local differences in a color space. The result is a hierarchy of partitions with multiple resolutions suitable for further goal driven analysis. The algorithm can handle large variation and gradient intensity in images. Dual graph pyramid representations lack the explicit encoding of edge orientation around vertices i.e they lack an explicit encoding of the orientation of planes, existing in combinatorial maps. Moreover with combinatorial maps, the dual must not be explicitly represented because one map is enough to fully characterize the partition.

Introduction

The authors in [START_REF] Keselman | Generic model abstraction from examples[END_REF] asked: "How do we bridge the representational gap between image features and coarse model features?" They identify the 1-to-1 correspondence between salient image features (pixels, edges, corners,...) and salient model features (generalized cylinders, polyhedrons,...) as a limiting assumption that makes prototypical or generic object recognition impossible. They suggested to bridge and not to eliminate the representational gap, and to focus efforts on region segmentation, perceptual grouping, and image abstraction. The union of regions forming the group is again a region with both internal and external properties and relations. Low-level cue image segmentation cannot and should not produce a complete final good segmentation, because there is an intrinsic ambiguity in the exact location of region boundaries in digital images. Problems emerge because homogeneity of low-level cues will not map to the semantics [START_REF] Keselman | Generic model abstraction from examples[END_REF], and the degree of homogeneity of a region is in general quantified by threshold(s) for a given measure [START_REF] Fu | Hierarchical color image region segmentation for content-based image retrival system[END_REF]. The low-level coherence of brightness, color, texture or motion attributes should be used to come up sequentially with hierarchical partitions [START_REF] Shi | Normalized Cuts and Image Segmentation[END_REF].

A grouping method should have the following properties [START_REF] Felzenszwalb | Image Segmentation Using Local Variation[END_REF]: capture perceptually important groupings or regions which reflect global aspects of the image, be highly efficient, running in time linear in the number of image pixels (e.g Minimal spanning tree), and creating hierarchical partitions [START_REF] Shi | Normalized Cuts and Image Segmentation[END_REF].

In a regular image pyramid the number of pixels at any level l, is r times higher than the number of pixels at the next reduced level l + 1. The so called reduction factor r is greater than one and it is the same for all levels l. If s denotes the number of pixels in an image I, the number of new levels on top of I amounts to log r (s). Thus, the regular image pyramid may be an efficient structure for fast grouping and access to image objects in top-down and bottomup processes. However, regular image pyramids are confined to globally defined sampling grids and lack shift invariance [START_REF] Bister | A critical view of pyramid segmentation algorithms[END_REF]. Bister et.al. [START_REF] Bister | A critical view of pyramid segmentation algorithms[END_REF] concludes that regular image pyramids have to be rejected as general-purpose segmentation algorithms. In [START_REF] Montanvert | Hierarchical image analysis using irregular tesselations[END_REF][START_REF] Jolion | The adaptive pyramid, a framework for 2D image analysis[END_REF] it was shown how these drawbacks can be avoided by irregular image pyramids, the so called adaptive pyramids, where the hierarchical structure (vertical network) of the pyramid was not a priori known but recursively built based on the data. Moreover in [START_REF] Cho | Image Segmentation from Consensus Information[END_REF][START_REF] Meer | Consensus vision[END_REF], was shown that irregular pyramids can be used for segmentation and feature detection.

Each level represents a partition of the pixel set into cells, i.e. connected subsets of pixels. The construction of an irregular image pyramid is iteratively local [START_REF] Meer | Stochastic image pyramids[END_REF][START_REF] Jolion | Stochastic pyramid revisited[END_REF]. This means that we use only local properties to build the hierarchy of the pyramid. On the base level (level 0) of an irregular image pyramid the cells represent single pixels and the neighborhood of the cells is defined by the 4 (8)-connectivity of the pixels. A cell on level l + 1 (parent) is a union of neighboring cells on level l (children). This union is controlled by so called contraction kernels (decimation parameters, see [START_REF] Kropatsch | Hierarchical, Adaptive and Robust Methods for Image Understanding[END_REF]). Every parent computes its values independently of other cells on the same level. This implies that an image pyramid is built in O[log(image diameter)] time. Neighborhoods on level l + 1, are derived from neighborhoods on level l. Two cells c 1 and c 2 are neighbors if there exist pixels p 1 in c 1 and p 2 in c 2 such that p 1 and p 2 are 4-neighbors. We assume that on each level l + 1 (l ≥ 0) there exists at least one cell not contained in level l. In particular, there exists a highest level h . In general the top of the pyramid can have one vertex, i.e. an apex.

Region adjacency graphs (RAG), dual graphs [START_REF] Haxhimusa | Segmentation Graph Hierarchies[END_REF] and combinatorial maps have been used before [START_REF] Brun | Contraction kernels and combinatorial maps[END_REF] to represent the partitioning of 2D space. From these 3 structures, the combinatorial map seems to be the most adequate because, RAGs cannot correctly encode multiple boundaries and inclusions, and dual graphs lack the explicit encoding of edge orientation around vertices, present in a combinatorial map [START_REF] Brun | Contraction kernels and combinatorial maps[END_REF]. Moreover with combinatorial maps, the dual must not be explicitly represented because one map is enough to fully characterize the partition, and also the dual can be easily deduced anytime.

In this paper we present the hierarchical image partitioning method introduced in [9] using combinatorial maps (Section 2) and combinatorial pyramids. The building of the minimum weight spanning tree (M ST ) using Borůvka's algorithm [START_REF] Borůvka | O jistém problému minimálnim[END_REF], which is an efficient parallel method, and (dual) combinatorial map contraction is presented in Section 3. We will end with some experimental results (Section 4) and conclusions (Section 5).

Combinatorial Maps

We will recall here some information about combinatorial maps: definitions and some properties. For a more detailed description of combinatorial maps see [START_REF] Brun | Dual Contraction of Combinatorial Maps[END_REF].

Definition 1 Combinatorial map. A combinatorial map G is the triplet G = (D, σ, α)
, where D is a set called the set of darts and σ, α are two permutations defined on D such that α is an involution:

∀d ∈ D α 2 (d) = d
If the darts are encoded by positive and negative integers, the permutation α can be implicitly encoded by α(d) = -d (see Figure 1). In the following, we will use alternatively both notations. A combinatorial map may be seen as a planar graph encoding explicitly the orientation of edges around a given vertex. Thus all graph definitions used in irregular pyramids [START_REF] Kropatsch | Parallel graph contraction for dual irregular pyramids[END_REF] such as end vertices, self loops, or degrees may be retrieved easily. The symbols α * (d) and σ * (d) stand, respectively, for the α and σ orbits of the dart d. More generally, if d is a dart and π a permutation we will denote the π-orbit of d by π * (d). The cardinal of this orbit will be denoted |π * (d)|. Some topological notions can be defined on G:

Definition 2 End vertices

• α * (d) is a self loop iff -d ∈ σ * (d) • α * (d) is a self-directed loop iff σ(d) = -d or σ((α(d)) = d • α * (d) is a bridge iff α(d) ∈ φ * (d). • α * (d) is a pendant edge iff σ(d) = d or σ((α(d)) = d
Using combinatorial maps each vertex is implicitly defined by its set of darts. Thus a vertex partition of a combinatorial map may be defined by encoding each vertex by one of its dart (see definition 3).

Definition 3 Partition. Given a combinatorial map

G = (D, σ, α), D 1 , . . . , D n ⊂ D is a vertex-partition of G iff: 1. ∀i ∈ {1, . . . , n} D i = ∅. All D i are non-empty. 2. ∀d ∈ D ∃i ∈ {1, . . . , n}, ∃d ∈ D i | d ∈ σ * (d ). Each vertex may be retrieved thanks to a dart in one D i . 3. ∀i, k ∈ {1, . . . , n} 2 σ * (D i ) ∩ σ * (D k ) = ∅.
p D,D D → D d → σ n-1 (d) with n = M in{p ∈ IN * | σ p (d) ∈ D }
is an injective function.

Definition 4 Partition into Connected Components.

Given a combinatorial map G = (D, σ, α), and a partition D 1 , . . . , D n . This partition will be called a partition into connected components iff:

∀i ∈ {1, . . . , n} G i = (D i , σ • p D,D i , α) is connected σ * (D i ) = α(σ * (D i ))
The second equality means that there is no edge which connects D i to D j .

Definition 5 Dual Combinatorial Map. Given a combinatorial map

G = (D, σ, α), the com- binatorial map G = (D, ϕ, α) is called the dual of G.
The permutation ϕ is defined by:

ϕ = σ • α
The orbits of ϕ encode the faces of G. Note that the function ϕ is a permutation, since it is the composition of two permutations on the same set.

The connectivity is preserved by the dual transformation [START_REF] Brun | Dual Contraction of Combinatorial Maps[END_REF].

G = G/α * (d) = G \ α * (d)
This operation will be denoted C d . Note that this operation is well defined since d is a self-loop in G iff it is a bridge in G.

Definition 8 Contraction Kernel. Given a connected combinatorial map G = (D, σ, α), the forest [START_REF] Brun | Dual Contraction of Combinatorial Maps[END_REF] F = (D 1 , . . . , D n ) will be called a contraction kernel N iff:

SD = D - n i=1 D i = ∅
The set SD is called the set of surviving darts.

Definition 9 Equivalent Contraction Kernel. Given a combinatorial map

G 0 = (D, σ, α), a contraction kernel N 1 of G 0 , the contracted combinatorial map G 1 = G 0 /N 1 , and N 2 a contraction kernel of G 1 , the contraction kernel K 3 of G 0 for witch G 0 /N 3 = (G 0 /N 1 )/K 2 , is called the equivalent contraction kernel of N 1 and N 2 .
The successive application of N 1 and N 2 forms a new operator on G 0 denoted by

N 2 • N 1 .
A combinatorial pyramid is a stack of successively reduced combinatorial maps, where each map is build from the one below by selecting a set of vertices named surviving vertices and mapping each non surviving vertex to a surviving one.

Image Partitioning

Let G = (D, σ, α) be a given attributed combinatorial map with the vertex set V = σ * (D) and edge set E = α * (D). We will discuss later about the attributes. The goal is to find partitions P = {CC 1 , CC 2 , ..., CC n } such that these elements satisfy certain properties. The author in [START_REF] Felzenszwalb | Image Segmentation Using Local Variation[END_REF] defines the function, Comp(•, •), which measures the difference along the boundary of two components relative to a measure of the differences of components' internal differences. This definition tries to encapsulate the intuitive notion of contrast: a contrasted zone is a region containing two connected components whose inner differences (internal contrast) are less than differences within it's context (external contrast). We define an external contrast measure between two components and an internal contrast measure of each component. These measures are defined in [START_REF] Felzenszwalb | Image Segmentation Using Local Variation[END_REF][START_REF] Guigues | The Hierarchy of the Cocoons of a Graph and its Application to Image Segmentation[END_REF], analogously.

Let G = (D, σ, α, attr v , attr e ) be a given attributed combinatorial map with the vertex set V = σ * (D) and edge set E = α * (D) on the base level (level 0). Vertices v ∈ V and edges e ∈ E are attributed, i.e. attr v : V → R + and attr e : E → R + . One possible way to attribute the edges is given in Section 4. The combinatorial map on level k of the pyramid is denoted by

G k (D k , σ k , α k ). Every vertex u ∈ V k = σ * k (D k
) is a representative of a component CC i of the partition P k . The equivalent contraction kernel of a vertex u ∈ V k , N 0,k (u) is e set of darts (a subtree) of the base level d ∈ D that are contracted; i.e. applying equivalent contraction kernel on the base level, one contracts the sub combinatorial map G ⊆ G onto the vertex u.

The internal contrast measure of the CC i ∈ P k is the largest dissimilarity measure of the component CC i i.e. the largest edge weight of the N 0,k (u) of a vertex u ∈ V k :

Int(CC i ) = max{attr e (e), e ∈ α * (N 0,k (u))}. (1)
Let u i , u j ∈ V k be the end vertices of an edge e ∈ E k . The external contrast measure between two components CC i , CC j ∈ P k is the smallest dissimilarity measure between component CC i and CC j i.e. the smallest edge weight connecting N 0,k (u i ) and N 0,k (u j ) of vertices u i ∈ CC i and u j ∈ CC j :

Ext(CC i , CC j ) = min{attr e (e), e = (d, -d) : d ∈ N 0,k (u i ) ∧ -d ∈ N 0,k (u j )}. (2)
The pairwise comparison function Comp(•, •) between two connected components CC i and CC j can now be defined as:

Comp(CC i , CC j ) = True if Ext(CC i , CC j ) > P Int(CC i , CC j ), False otherwise, (3)
where P Int(CC i , CC j ) is the minimum internal contrast difference between two components:

P Int(CC i , CC j ) = min(Int(CC i ) + τ (CC i ), Int(CC j ) + τ (CC j )). (4)
For the function Comp(CC i , CC j ) to be true i.e. for the border to exist, the external contrast difference must be greater than the internal contrast differences. The reason for using a threshold function τ (CC) in Equation ( 4) is that for small components CC, Int(CC) is not a good estimate of the local characteristics of the data, in extreme case when |CC| = 1, Int(CC) = 0. Any non-negative function of a single component CC, can be used for τ (CC) [START_REF] Felzenszwalb | Image Segmentation Using Local Variation[END_REF]. One can define τ to be function of the size of CC: τ (CC) = α/|CC|, where |CC| denotes the size of the component CC and α is a constant. More complex definition of τ (CC), which is large for certain shapes and small otherwise would produce a partitioning which prefers certain shapes, e.g. using ratio of perimeter to area would prefer components that are not long and thin. Let P k = CC k i , CC k j , ..., CC k n be the partitions on the level k of the pyramid i.e P k is the combinatorial map G k (D k , σ k , α k ). Algorithm 1 shows how to build the hierarchy of partitions.

Experiments on Image Maps

In the following paragraphs we will comment about some implementation issues and results. Because having a combinatorial map, one can always deduce/obtain it's dual. There is no need of storing both. All the details here (as in the whole paper) are given for the map in which vertices represent regions. In it's dual, instead of vertices, faces are used to represent regions, for all e = (d,

-d) ∈ E min , u k,i = σ * k (d), u k,j = σ * k (-d) with Ext(CC k i , CC k j ) ≤ P Int(CC k i , CC k j ) do 7:
include d and -d in contraction kernel N k,k+1

8:

end for end for 13:

9: contract combinatorial map G k with contraction kernel, N k,k+1 : G k+1 = C[G k , N k,k+1 ].
k = k + 1 14: until G k = G k-1
Output: A region adjacency combinatorial map at each level of the pyramid. and also instead of 'end vertices of an edge' we are interested in the neighboring faces of an edge (the 2 faces separated by that edge).

Choosing which map to represent is more a subjective matter because both store the same information in a not so different way (the same framework could be used to store and manage both). Because the base entity in a combinatorial map is the dart, we cannot have a map containing only one vertex and no edges. So one notable difference would be that if vertices are chosen to represent the regions, a one region map, without self loops is not possible until the background (the infinite region) is represented explicitly (darts have to be specially added for that). On the dual, where regions are represented by faces, the background/infinite region also exists, but no special darts have to be added to accommodate it, so a one region map would be made out of 2 darts that are 'sewed' together by α and by σ.

We start with the trivial partition, where each pixel is a homogeneous region. The attributes of edges are defined as the difference of its end point vertices. The attributes of edges can be defined as the difference between end point features of end vertices , attr e (u i , u j ) = |F (u i ) -F (u j )|, where F is some feature. F could be defined as F (u i ) = I(u i ), for gray value intensity images, or

F (u i ) = [v i , v i • s i • sin(h i ), v i • s i • cos(h i )],
for color images in HSV color distance [START_REF] Shi | Normalized Cuts and Image Segmentation[END_REF]. However the choice of the definition of the weights and the features to be used is in general a hard problem, since the grouping cues could conflict each other [START_REF] Malik | Textons, contours and regions: Cue integration in image segmentation[END_REF].

For our experiments we used as attributes of edges the euclidean distance between pixel RGB values, attr e (u i , u j ) = red(u i ) * red(u j ) + green(u i ) * green(u j ) + blue(u i ) * blue(u j ). [START_REF] Cho | Image Segmentation from Consensus Information[END_REF] We choose this simple color distance to study the properties of the algorithm. To compute the Note that in all images there are regions of large intensity variability and gradient. This algorithm copes with this kind of gradient and variability. In contrast to [START_REF] Felzenszwalb | Image Segmentation Using Local Variation[END_REF] 3 the result is a hierarchy of partitions with multiple resolutions, suitable for further goal driven, domain specific analysis 4 . On the lower level of the pyramid the image is over segmented (partitioned) whereas in upper it is under segmented (partitioned), the help of mid and high level knowledge would select the proper partitioning. Since the algorithm preserves details in low-variability regions, a noisy pixel would survive through the hierarchy. Of course, image smoothing in low variability regions would overcome this problem. We, however do not smooth the images, as this would introduce another parameter into the method. The hierarchy of partitions can also be built from an over segmented image to overcome the problem of noisy pixels. Note that the influence of τ in decision criterion is smaller as the region gets bigger for a constant α. The constant α is used to produce a kind of the over segmented image and the influence of τ is smaller after each level of the pyramid. For an overexerted image, where the size of regions is large, the algorithm becomes parameterless.

Conclusion

In this paper we presented a method for building hierarchical image partitions using Borůvka's minimal spanning tree algorithm. The hierarchy is presented as a combinatorial pyramid, where each level is a 2D combinatorial map. Combinatorial maps are defined in any dimension, thus the current work should lead the way to segmentation of digital video streams using contraction in 3D combinatorial maps/pyramids. It was shown that the algorithm can handle large variation and gradient intensity in images. Even though the algorithm makes greedy decisions locally, it produces perceptually important partitions in a bottom-up way based only on local differences. A drawback is that maximum and minimum criterion is very sensitive to noise, although in practice it has a small impact. To overcome the problem of noise, one could start with an oversegmented image produced by a robust method e.g. watershed method. A comparison between the classes of partitions produced by the presented method, and some of the well known methods (e.g. [START_REF] Felzenszwalb | Image Segmentation Using Local Variation[END_REF]) is planned.

Figure 1 :

 1 Figure 1: Example combinatorial map

  Given a dart d, we call the end vertices of the edge α * (d) = (d, -d) the orbits σ * (d) and σ * (-d).

Definition 6 Definition 7

 67 Removal Operation. Given a combinatorial map G = (D, σ, α) and d ∈ D. If α * (d) is not a bridge, the combinatorial map G = G \ α * (d) is the sub-map defined by: • D = Dα * (d) and • σ = σ • p D,D . This operation will be denoted R d . Contraction operation. Given a combinatorial map G = (D, σ, α) and one dart d, in D which is not a self loop. The contraction of dart d creates the graph:

Algorithm 1 -repeat 3 : 4 :

 134 Construct Hierarchy of Partitions Input: Attributed combinatorial map G 0 . 1: k = 0 2: for all vertices u ∈ V k = σ * k (D k ) do E min (u) = argmin{attr e (e) | e = (d, -d) ∈ E k and u = σ * k (

10 :

 10 for all e k+1 ∈ E k+1 = α * k+1 (D k+1 ) do 11: set edge attributes attr e (e k+1 ) = min{attr e (e k ) | e k+1 = C[e k , N k,k+1 ]} 12:

Figure 2 :Figure 2 ,

 22 Figure 2: Some levels of the partitioning of "Tulips(cropped)": level (number of components).

Figure 4 .

 4 Figures 2, 3 and 4 show some of the partitions on different levels of the pyramid and the number of components. In general the top of the pyramid will consist of one vertex, an apex, which represents the whole image.

Figure 3 :Figure 4 :

 34 Figure 3: Some levels of the partitioning of "Obj18 355": level (number of components). Obj59 0

  The set of darts of one vertex is included in only one D i .Note that we do not have n i=1 D i = D. Condition 2, only requires that each vertex has at least one of its darts in one D i .

Lemma 1 The Restriction Operator. Given a combinatorial map G = (D, σ, α) and D ⊂ D the application :

Waterloo image database

Coil 100 image database

In[START_REF] Pavan | Dominiant Sets and Hierarchical Clustering[END_REF] results of different segmentation methods, including the ones in[START_REF] Felzenszwalb | Image Segmentation Using Local Variation[END_REF] and[START_REF] Malik | Textons, contours and regions: Cue integration in image segmentation[END_REF], are shown and compared.

Please note that a whole class of partitions is created, where a partition is not limited to a certain level of the pyramid, but can be constructed of components from different levels (the receptive fields of the vertices of a multilevel partition occupy the whole image, and do not overlap)

This paper has been supported by the Austrian Science Fund under grants FSP-S9103-N04.