Richard Combes
email: richard.combes@orange-ftgroup.com

Zwi Altman
email: zwi.altman@orange-ftgroup.com

Eitan Altman
email: eitan.altman@sophia.inria.fr

On the use of packet scheduling in self-optimization processes: application to coverage-capacity optimization

Keywords: Wireless communication, Self-Optimizing Networks, Scheduling

Self-organizing networks (SON) is commonly seen as a way to increase network performance while simplifying its management. This paper investigates Packet Scheduling (PS) in the context of self-optimizing networks, and demonstrates how to dynamically improve coverage by adjusting the scheduling strategy. We focus on α-fair schedulers, and we provide methods for calculating the scheduling gain, including several closed form formulas. We then propose a coverage-capacity self-optimization scheme based on α-fair schedulers. The method uses Key Performance Indicators (KPIs) to calculate the optimal α in both simple and efficient manner. A simple use case illustrates the implementation of the SON feature and simulation results show the important coverage gains that can be achieved at the expense of very little computing power. 1

I. INTRODUCTION

Next Generation (NG) Radio Access Networks (RAN) encompassing Beyond 3G (B3G) and 4G networks target ambitious performance and Quality of Service (QoS) objectives. Evolutions in NG RANs are geared by new applications and services with increasing demand for bandwidth and for high QoS while keeping cost and complexity as low as possible. In this context, SON is commonly seen as a key lever to further increase network performance, to simplify its management and to reduce its cost of operation. Main standardization bodies such as 3rd Generation Partnership Project (3GPP) and IEEE have picked up this topic, and SON mechanisms encompassing self-configuration, self-optimization and selfhealing are expected to become widely commercially available with the introduction of 4G networks (e.g. LTE Advanced [START_REF] Gpp | Evolved Universal Terrestrial Radio Access (E-UTRA) and Evolved Universal Terrestrial Radio Access (E-UTRAN); Overall description; Stage 2[END_REF] and WiMax 802.16m [START_REF]Requirements for WiMAX Air Interface System Profile Release[END_REF]).

The academic and industrial communities have defined requirements, challenges and many use cases for SON in B3G and 4G RANs (see for example [START_REF] Gpp | Evolved Universal Terrestrial Radio Access Network (E-UTRAN); Self-configuring and self-optimizing network (SON) use cases and solutions[END_REF], [START_REF] Ngmn | NGMN Recommendation on SON and O&M Requirements[END_REF], [START_REF] Berg | Selforganisation in future mobile comminucation networks[END_REF]). Selfoptimizing network is a SON mechanism that aims at adapting the network to variations in traffic, in propagation conditions and to modification in the operating conditions such as the introduction of a new service. Self-optimizing network has been defined in [START_REF] Gpp | Evolved Universal Terrestrial Radio Access (E-UTRA) and Evolved Universal Terrestrial Radio Access (E-UTRAN); Overall description; Stage 2[END_REF] as "the process where User Equipment (UE) and enhanced eNode B (eNB) measurements and performance measurements are used to auto-tune the network ". Ref. [START_REF] Ngmn | NGMN Recommendation on SON and O&M Requirements[END_REF] is probably the most complete document providing the requirements and use cases for SON in general and self-optimizing network in particular. Among the self-optimizing use cases are: interference control, handover parameter optimization, parameter optimization of Radio Resource Management (RRM) functionalities governing QoS such as admission control, congestion control, packet scheduling, load balancing, link level retransmission scheme optimization etc. An important SON use case for network operators is the outage detection and compensation ( [START_REF] Ngmn | NGMN Recommendation on SON and O&M Requirements[END_REF], [START_REF] Amirijoo | Cell outage management in lte networks[END_REF]).

This paper investigates PS in the context of self-optimizing networks. We believe that a packet scheduler can serve as a central tool for designing efficient SON mechanisms in NG RANs. The packet scheduler can be used as part of a stand alone SON entity as described in this work, or in conjunction with other coordinated SON entities such as mobility and/or Inter-Cell Interference Coordination (ICIC) SON entities. The first challenge we face is to model the PS in time scales in which the self-optimization processes operate which could vary from a hundred milliseconds to tens of seconds and more. The packet scheduling operates on a time scale of a millisecond to react to fast fading. Hence one needs to quantify the scheduling gain which depends on the current traffic distribution, i.e. the number of mobiles and their Signal to Interference plus Noise (SINR) at a long time scale. Furthermore, the computation of the scheduling gain should be performed very rapidly to allow the incorporation of the scheduler in a network simulator used to design the self-optimization functionality.

We focus on the family of α-fair schedulers introduced by [START_REF] Mo | Fair end-to-end window based congestion control[END_REF] which includes well-studied schedulers such as Proportional Fair (PF), Max Throughput (MTP) and Max-Min Fair (MMF) schedulers. A general framework for calculating a scheduling gain has been proposed in [START_REF] Bergren | Asymptotically fair transmission scheduling over fading channels[END_REF] for α = 1 and is generalized to α > 0 in this work. For certain particular cases, namely MMF and MTP, we provide closed form expressions for the scheduling gain. These expressions allow us to understand what kind of scheduling gain can be achieved in limit cases for α and its potential use for improving QoS.

We demonstrate the application of the statistical-based scheduler gain calculation to the family of α-fair schedulers that will be used in the self-optimization process. It is noted that deriving the scheduling gain is done without considering the Rayleigh fading time series obtained by the Jakes Model ( [START_REF] Jakes | Microwave Mobile Communications[END_REF], [START_REF] Li | The generation of independent rayleigh faders[END_REF]). The reason is relatively simple: if the scheduling interval is large enough, the channel states at different scheduling times are independent (see II-B), which makes the calculation a lot simpler.

The second contribution of the paper is to derive a coveragecapacity self-optimization scheme based on the family of αfair schedulers. We show how to adjust the scheduling strategy dynamically to maximize the cell coverage while minimizing the corresponding capacity losses measured in terms of global cell throughput. The self-optimization scheme uses a strategy inspired by the Multi-Armed-Bandit (MAB) problem to learn the optimal α dynamically. The proposed approach is simple and computationally efficient and can serve as basis for real implementation.

The paper is organized as follows: Section II provides the definition of the α-fair scheduler as a maximization problem, and the model chosen for fast-fading. We state an explicit scheduling rule and it's heuristic justification. Section III demonstrates rigorously that this scheduling rule solves the maximization problem, using stochastic approximation techniques. Section IV deals with how to calculate the scheduling gain for a given α, with several closed form formulas for particular values of α and a numerical method for the remaining cases. In section V we examine several simulation results to show the behavior of the scheduling gain when α varies, and how we might take advantage of it to manage fairness dynamically. Section VI describes how the computation of the scheduler gain can be used for capacitycoverage self-optimization in an environment with varying traffic and provides numerical results. Section VII concludes the paper.

II. MODEL AND ASSUMPTIONS

A. α-fair scheduling 1) Definition: We consider a cell with N users with no mobility, and we adopt a full buffer traffic model. We are considering the downlink scheduling, and the scheduler picks a user for transmission at regular time intervals. A scheduling policy P is defined by the choice of a user for every scheduling instant (P tm ) m∈N , namely P tm = i means that at time t m , user i will be selected for transmission. We define r i,tm the instantaneous throughput of user i at time t m , and r i,tm the mean throughput allocated to user i during the time interval [t 0 , t m ]. We assume perfect channel knowledge, that is to say that at t m , the scheduler knows r i,tm ∀i and can make use of it to choose the scheduled user. Let ǫ > 0 denote a small averaging parameter, define r i,tm as in [START_REF] Kushner | Convergence of proportional-fair sharing algorithms under general conditions[END_REF] by the following recursive equation:

r i,tm+1 = (1 -ǫ)r i,tm + ǫδ Pt m+1 ,i r i,tm+1 (1)
where δ denotes Kronecker's delta. ǫ controls the size of the averaging window, and for voice traffic, the play-out buffer size is 80ms, which implies that we should choose ǫ so that (1ǫ) 80 is small, for example ǫ = 0.05. This definition for the mean allocated throughput is more relevant to reflect the QoS perceived by a user than using an arithmetic mean (which would be replacing ǫ in (1) by 1 m ) because it induces a "decay" of past observed values. If we assume that r i,t0 = 0 ∀i, equation (1) can also be written:

r i,tm = ǫ m j=0 (1 -ǫ) m-j δ Pt j ,i r i,tj (2)
Furthermore, if r i,tm has a limit when m → +∞, ǫ → 0 + , we then denote by r i,+∞ this limit.

We also make the assumption that (r i,tm ) m∈N is an i.i.d sequence for all i, and that (r i,tm ) m∈N is independent of (r k,tm ) m∈N,k =i .

As introduced in [START_REF] Mo | Fair end-to-end window based congestion control[END_REF], the α-fair scheduler for α ∈ [0, +∞) is the policy that maximizes the following utility function, given the time interval [t 0 , t M ]:

U =              N i=1 log(d + r i,tM ) , α = 1 N i=1 (r i,tM + d) 1-α 1 -α , α = 1 (3)
where d > 0 can be chosen as small as desired and is only present to avoid problematic behavior near 0.

2) Allocation: We now give a heuristic justification for the scheduling rule, and a rigorous analysis is given in Section III. We assume that the allocation has been done for [t 0 , t M ] and we want to decide which user to schedule at t M +1 . Let (∆U ) i denote the variation of utility if user i is chosen for transmitting at t M +1 , which we approximate with a first-order Taylor expansion. If α = 1, the increase in utility for user i is:

log (1 -ǫ)r i,tM + ǫr i,tM+1 + d -log(r i,tM + d) = ǫ r i,tM+1 -r i,tM r i,tM + d + o(ǫ) (4)
The decrease for the other users is:

log ((1 -ǫ)r i,tM ) -log(r i,tM ) = -ǫ r i,tM r i,tM + d + o(ǫ) (5)
We add (4) and ( 5):

(∆U ) i = ǫ r i,tM+1 r i,tM + d - N k=1 r k,tM r k,tM + d + o(ǫ) (6)
If α = 1: 1 1 -α (1 -ǫ)r i,tM + ǫr i,tM+1 + d 1-α -(r i,tM + d) 1-α = ǫ r i,tM+1 -r i,tM (r i,tM + d) α + o(ǫ) (7)
and:

1 1 -α ((1 -ǫ)r i,tM + d) 1-α -(r i,tM + d) 1-α = -ǫ r i,tM (r i,tM + d) α + o(ǫ) (8)
We add [START_REF] Mo | Fair end-to-end window based congestion control[END_REF] and ( 8):

(∆U ) i = ǫ r i,tM+1 (r i,tM + d) α - N k=1 r k,tM (r k,tM + d) α + o(ǫ) (9)
In both cases, for small ǫ, the optimal choice is:

i * = arg max 0≤i≤N r i,tM+1 (r i,tM + d) α (10)
α = 1 corresponds to a PF scheduler, and α = 0 to a MTP scheduler.

B. Channel Model

Let c i,tm be the instantaneous channel quality for user i at time t m , that is to say the product of path loss, shadowing and fast fading. We will assume that r i,tm = Φ(c i,tm ). Φ is a function that maps channel quality into bit-rate, and is given in the form of a quality table obtained from a link level simulator. Φ captures the effect of physical layer mechanisms such as modulation, coding and retransmissions. This function therefore depends on the technology we are considering, which is Time Division Multiple Access (TDMA) technology such as High Speed Downlink Packet Access (HSDPA).

Let us denote by S i the average SINR for user i, which captures the effect of path loss, shadowing and interference with neighboring cells. We choose a time scale that is short enough for all those effects to be constant, but long enough to capture a scheduling gain, and the only random parameter is the fast fading ξ.

The channel fading is described by a Rayleigh model, and we use the assumption from [START_REF] Blaszcyszyn | Fading effect on the dynamic performance evaluation of ofdma cellular networks[END_REF] that the number of interfering signals is sufficiently large so that the fading processes between users and neighboring cells base stations can be ignored for the calculation of S i . The instantaneous channel quality can then be written as:

c i,tm = S i ξ i,tm , ξ i,tm ≡ Exponential(1) (11)
Furthermore, random variables (ξ i,tm ) 0≤i≤N,m∈N are independent. Independence between users comes from the Rayleigh fading model, and independence between different instants is verified if t m+1t m is larger than the channel coherence time. More precisely, as stated in [START_REF] Jakes | Microwave Mobile Communications[END_REF], the autocorrelation of the channel fading for a single user between t and t + τ is J 0 (ω M τ ), where J 0 is the 0-th order Bessel function and ω M -the maximum Doppler shift, and |J 0 (x)| vanishes as x grows.

III. CONVERGENCE ANALYSIS

In this section we give a convergence analysis of α-fair scheduling, using the Ordinary Differential Equation (ODE) technique which has been used previously in [START_REF] Kushner | Stochastic Approximation and Recursive Algorithms and Applications 2nd edition[END_REF] and [START_REF] Kushner | Convergence of proportional-fair sharing algorithms under general conditions[END_REF] to show the convergence of the PF scheduler.

A. Stochastic approximation

We start by giving two results from stochastic approximation theory, which links the behavior of stochastic iterative algorithms with limit sets of a certain ODE. We consider

θ ∈ R n , (a, b) ∈ R n × R n , H = {x ∈ R n |a i ≤ x i ≤ b i }, Π H [x] = argmin y∈H ||x -y||, step sizes ǫ k > 0 and random variables Y k (θ) ∈ R n . We assume that the Y k are independent and identically distributed (i.i.d) with E[Y k (θ)] = g(θ) and sup θ E[Y k (θ) 2 ] < +∞.
We define the sequence θ k using the following algorithm:

θ k+1 = Π H [θ k + ǫ k Y k ] (12)
Two choices for the step sizes are possible:

(Pi) ǫ k > 0 , +∞ k≥1 ǫ k = +∞ , +∞ k≥1 ǫ 2
k < +∞ which is adequate when the environment is stationary, and ensures a strong form of convergence as shown below (Pii) ǫ k = ǫ > 0 where ǫ is a small constant, which allows following slow variations of the environment We will also assume that g is continuous, that the mean ODE . θ = g(θ), θ(0) = θ 0 has a unique solution defined on R + for all θ 0 , and that all solutions converge to θ * in the interior of H. Before stating the theorems it shall be noted that the assumptions we have made are extremely restrictive in order to make the theorems statements less technical, and that a lot of other cases can be handled by stochastic approximation theory, including non i.i.d variables, cases in which the mean ODE does not converge to a single point and when it is replaced by a differential inclusion.

The asymptotic behavior of ( 12) is given by the following theorems:

Theorem 1. If we assume (Pi) then θ k → k→+∞ θ * almost surely.

Theorem 2. If we assume (Pii) then there exists a constant

K 1 > 0 such that lim sup k→+∞ E[||θ k -θ * || 2 ] 1 2 ≤ K 1 √ ǫ
The first theorem is implied by [START_REF] Kushner | Stochastic Approximation and Recursive Algorithms and Applications 2nd edition[END_REF] (Theorem 2.1, page 127) and the second is [START_REF] Borkar | Stochastic Approximation: A Dynamical Systems Viewpoint[END_REF] (Theorem 3, Page 106). Intuitively, the second theorem states that we can always find an ǫ so that the accumulation points of the sequence θ k are almost all the time in an arbitrarily small neighborhood of the limit point θ * , giving a form of convergence in distribution (or weak convergence).

B. Application to the α-fair scheduler, α > 0

We will now use the previous results to show that the αfair scheduler defined by (10) converges to a unique limit, and that it maximizes the utility function [START_REF] Gpp | Evolved Universal Terrestrial Radio Access Network (E-UTRAN); Self-configuring and self-optimizing network (SON) use cases and solutions[END_REF]. We work with α > 0 fixed, and the case α = 0 will be studied separately.

We use the following notation:

(x, y) ∈ R n × R n , x ≤ y ⇔ x i ≤ y i , 1 ≤ i ≤ n.
The scheduling rule [START_REF] Li | The generation of independent rayleigh faders[END_REF] has the form [START_REF] Blaszcyszyn | Fading effect on the dynamic performance evaluation of ofdma cellular networks[END_REF], with θ k the mean throughput at time k, ǫ a small constant, and g(θ) = h(θ)θ, where h is defined by: h

(θ) = E[rI arg max( r (d+θ) α ) ] with (I i ) k = δ(i, k) , 1 ≤ k ≤ n.
We will assume that r is always positive with E(r) = r < +∞ and E(r 2 ) < +∞ .We also assume that r has a density with respect to the Lebesgue measure on (R + ) n , and that its components are independent. It shall be noted that those assumptions are not very restrictive and are satisfied for Rayleigh and Rice fading models.

1) Properties of h:

We have that h is positive and bounded, since h ≤ r.

We have that if

h(θ 1 ) = θ 1 , θ 1 ≤ θ 2 and h(θ 2 ) = θ 2 then θ 1 = θ 2 ,
since all components of h cannot increase when all components of θ increase.

We are going to prove that h is also Lipschitz continuous. We first assume that ||θ|| < 1, let P i,j,θ1,θ2 be the following quantity:

P i,j,θ1,θ2 = P r i (d + θ 1i ) α ≥ r j (d + θ 1j ) α ∪ r i (d + θ 2i ) α ≤ r j (d + θ 2j ) α
which we can rewrite:

P i,j,θ1,θ2 = P r j ( d + θ 1i d + θ 1j ) α ≤ r i ≤ r j ( d + θ 2i d + θ 2j ) α (13)
Let

F ri (x) = P[r i ≤ x], P i,j,θ1,θ2 = E F ri (r j ( d + θ 1i d + θ 1j ) α ) -F ri (r j ( d + θ 2i d + θ 2j ) α ) (14)
We have assumed ||θ|| ≤ 1, so we have :

|( d + θ 1i d + θ 1j ) α -( d + θ 2i d + θ 2j ) α | ≤ K α ||θ 1 -θ 2 || (15)
F ri is Lipschitz since we have assumed r i to have a density with respect to the Lebesgue measure, so for a certain constant K F :

P i,j,θ1,θ2 ≤ E[K α K F ||θ 1 -θ 2 ||r j ] = K α K F ||θ 1 -θ 2 ||r j (16) We now apply Cauchy-Schwartz inequality to evaluate the variation of h ||h(θ 1 ) -h(θ 2 )|| ≤E[||r|| 2 ]E[||I arg max( r (d+θ 1 ) α ) -I arg max( r (d+θ 2 ) α ) || 2 ] (17)
The first term is finite since we have assumed finite variance for r and the second term can be evaluated by:

E[||I arg max( r (d+θ 1 ) α ) -I arg max( r (d+θ 2 ) α ) || 2 ] ≤ 4 i =j P i,j,θ1,θ2 (18)
Combining ( 17) and (18) we conclude that there exists C h constant so that:

||h(θ 1 ) -h(θ 2 )|| ≤ C h ||θ 1 -θ 2 || (19)
We therefore have proved that h is Lipschitz for ||θ|| ≤ 1. Let K 2 ≥ 1, we have that :

I arg max( r (d+θ) α ) = I arg max( r ( d+θ K 2 ) α ) (20)
and therefore:

h(θ) = h( θ + d K 2 -d) (21)
We combine this with (19), with K 2 large enough:

||h(θ 1 ) -h(θ 2 )|| = ||h( θ 1 + d K 2 -d) -h( θ 2 + d K 2 -d)|| ≤ C h K 2 ||θ 1 -θ 2 || ≤ C h ||θ 1 -θ 2 ||
So we have proved that h is globally Lipschitz continuous.

2) Existence of a solution to the ODE: We now have to prove that the ODE has solutions on R + . We have that h is Lipschitz, so the Picard-Lindelof theorem assures us that it has a unique local solution. Furthermore, we know that there exists a unique maximal solution defined on some maximal interval [0, t 0 [. h is bounded by r so θ(t) ≤ θ(0)+tr, therefore 0 = +∞, or else the solution is not maximal.

3) Monotone dynamical systems: We first state some results from the theory of monotone dynamical systems, and the reader can refer to [START_REF] Smith | Monotone Dynamical Systems: an Introduction to the Theory of Competitive and Cooperative Systems[END_REF] for their proofs.

We denote by Φ t (x), x ∈ (R + ) n the value at time t of the solution to the ODE starting in x. We define the orbit of x by O(x) = {Φ t (x)|t ≥ 0} and the limit set of x by ω(x) = ∩ t≥0 ∪ s≥t Φ s (x). x is called an equilibrium point if O(x) = x, and we denote by E the set of equilibrium points. x is called a quasi-convergent point if ω(x) ⊂ E and we denote by Q the set of quasi-convergent points. If x ≤ y ⇒ Φ t (x) ≤ Φ t (y) ∀(x, y) ∈ (R + ) n × (R + ) n ∀t ∈ R + , then we say that Φ is monotone. We have the following theorems: Theorem 3. If Φ is monotone and x < y then either:

(i) ω(x) < ω(y) , or (ii) ω(x) = ω(y) ⊂ E Theorem 4. If Φ is monotone then Q is dense in (R + ) n
We now need to show that those results can be applied to the ODE we are considering, which is proved by the following comparison theorem:

Theorem 5. We consider the ODE . x= g(x). Let g : (R + ) n → R n , verifying: (i) g is continuous (ii)
The solution to the ODE is unique for every initial condition (iii) x ≤ y and x i = y i ⇒ g i (x) ≤ g i (y) (iv) For T ≥ 0, (x, δ) ∈ (R + ) n × (R + ) n , we have that:

sup 0≤t≤T ||Φ t (x) -Φ t (x + δ)|| → δ→0 0
Then Φ is monotone Condition (iii) is often called the Kamke condition.

Let us now show that the ODE we are considering satisfies those conditions. (i) and (ii) have been proved previously. (iii) comes from the fact that x → 1 (d+x) α is decreasing. To prove (iv), let T > 0, since h is Lipschitz we can apply Gronwall's lemma:

||Φ t (x) -Φ t (x + δ)|| ≤ ||δ||e K3t (22)
for a certain constant K 3 . We then have that:

sup 0≤t≤T ||Φ t (x) -Φ t (x + δ)|| ≤ ||δ||e K3T → δ→0 0 (23)
So the conditions of the previous theorem are valid. 4) Convergence for θ(0) = 0 : By noticing that g(0) > 0, the following theorem proves that the solution starting at 0 converges to a certain θ * . Theorem 6. If the ODE verifies the Kamke condition then any solution starting at x with g(x) > 0 converges to an equilibrium point.

Let us now show that all solutions converge to the same limit.

We have proved that ω(0) = {θ * }. Let x > 0 be an arbitrary initial condition, and

x 1 ≥ x with x 1 ∈ Q since Q is dense in (R + ) n . We know that ω(x 1 ) ⊂ E since x 1 ∈ Q, let us assume that ω(0) < ω(x 1 ). Let x 2 ∈ ω(x 1 )
, we have that h(x 2 ) = 0 and x 2 > θ * , which contradicts (III-B1). So ω(x 1 ) = ω(0) = {θ * }, and finally ω(x) = {θ * } ∀x ≤ 0, in other words all solutions converge to θ * . 5) Optimality: Finally, we have to prove that the scheduling strategy is optimal, namely that any other scheduling strategy achieves lower utility.

We first differentiate the utility function:

.

U (θ(t)) = n i=1 h i (θ(t)) -θ i (t) (d + θ i (t)) α (24)
We are going to prove that θ * is a local maximum of U on the of all achievable throughputs. Let f : (R + ) n × (R + ) n → {1, ..., n} a new allocation rule, by replacing h by it's definition we have that:

E[ n i=1 r i (I f (θ,r) ) i (d + θ i (t)) α ] ≤ E[ n i=1 r i (I arg max( r (d+θ) α ) ) i (d + θ i (t)) α ]. (25)
Let θ f (t) and θ(t) the trajectories implied by the new and the usual allocation rules respectively, both starting at θ * . By combining (24) and (25) at t = 0 we have that:

. U (θ f (t))| t=0 ≤ . U (θ(t))| t=0 ≤ 0 (26)
Therefore θ * is a local maximum of U on the set of all achievable throughputs. Now consider θ m achievable and such that U (θ m ) > U (θ * ). There is a certain allocation policy f such that θ m = E[rI f (r) ]. Starting at θ * and using the allocation f gives the ODE . θ= θ mθ, the solution being θ(t) = e -t θ * + (1e -t )θ m . Since α > 0, U is strictly concave, and it must be strictly increasing at the beginning of this path, which contradicts the fact that θ * is a local maximum. We therefore have proved that the scheduling rule achieves optimal utility. C. Application to the α-fair scheduler, α = 0

The case α = 0 is a bit different since U is linear, and not strictly concave. However the proof is a lot simpler since the scheduling strategy does not depend on the mean throughput. The ODE is . θ= E[rI arg max(r) ]θ, and the solution is θ(t) = e -t θ 0 +(1-e -t )E[rI arg max(r) ], which converges to an unique limit. It shall be noted that the limit is unique because P[r i = r j , i = j] = 0. If P[r i = r j , i = j] > 0 it might not be the case, for example consider the case where all the r i are constant and equal to 1, any point in the simplex is a limit throughput. It is also easy to see that since we have assumed independence of the channel between two scheduling instants and that U is linear, the policy that chooses the user with the best channel also maximizes U over the set of achievable throughputs.

IV. SCHEDULING GAIN

A. General expression

Let r i,+∞,α denote the mean limit throughput allocated to user i by an α-fair scheduler, and r i,+∞,RR the same quantity for a Round Robin (RR) scheduler. It is noted that r i,+∞,α is well-defined according to the convergence analysis done in Section III. We use the RR scheduler as a reference, and we want to calculate the scheduling gain of an α-fair scheduler G α = ri,+∞,α ri,+∞,RR . For a given α, the scheduling strategy (10) converges to a unique limit θ * with h(θ * ) = θ * , and combining this with the channel model, yields the following integral equation:

r i,+∞,α = +∞ 0 Φ(x)P Φ(x) r α i,+∞,α ≥ max k =i Φ(S k ξ k ) r α k,+∞,α e -x S i S i dx (27)
It is important to notice that this formula in its present form does not enable us to calculate the scheduling gain, since we need to know the value of r k,+∞,α ∀k. We will now show some particular cases where analytic formulas exist, and give a numerical method for other cases.

B. RR

Let L Φ denote the Laplace transform of Φ, the RR scheduler chooses a given user with probability 1 N , which gives:

r i,+∞,RR = 1 N +∞ 0 Φ(x) S i e -x S i dx = 1 N S i L Φ 1 S i (28)

C. PF

Results for the PF case (α = 1) are given in [START_REF] Blaszcyszyn | Fading effect on the dynamic performance evaluation of ofdma cellular networks[END_REF]:

r i,+∞,1 = 1 S i N -1 k=0 N -1 k (-1) k L Φ k + 1 S i (29)
In particular, if Φ is a linear function we have the simple expression [START_REF] Bergren | Asymptotically fair transmission scheduling over fading channels[END_REF]:

G i,1 = N k=1 1 k (30)
which is asymptotically equivalent to log(N ).

D. MTP

Let us examine the case of a MTP, that is α = 0. The probability of choosing user i is the probability that he has the best channel quality:

P [x > max k =i (c k,t )] = k =i (1 -e -x S i ) ( 31
)
The throughput is then

r i,+∞,0 = +∞ 0 Φ(x) k =i (1 -e -x S k ) e -x S i S i dx (32)
By developing the product, we obtain the following expression:

r i,+∞,0 = 1 S i N -1 k=0 (-1) k a1<...<a k ,aj =i ∀j L Φ   1 S i + k j=0 1 S aj   (33)

E. MMF

We now consider the case α → +∞, which is analytically tractable, and of particular interest for the dynamic alpha policy we will address later.

Since for m > 1, P [r i,tm = r j,tm , i = j] = 0 and P [r i,tm = 0] = 0, the scheduling rule [START_REF] Li | The generation of independent rayleigh faders[END_REF] becomes:

i * = arg min 0≤i≤N (r i,tm ) (34)
We are now going to prove that all users have the same throughput for a MMF scheduler. We know that r i,+∞,+∞ exists, and let us assume that r i,+∞,+∞ > r j,+∞,+∞ ≥ 0, therefore, there exists a T so that:

r i,tm,+∞ > r j,tm,+∞ t m ≥ T (35)
which means that user i never transmits after T , and so r i,+∞,+∞ = 0 which contradicts our initial assumption. Therefore, r i,+∞,+∞ = r j,+∞,+∞ ∀i, j. We know that when user i is alone in the cell, it's throughput is:

+∞ 0 Φ(x) e -x S i S i dx = 1 S i L Φ ( 1 S i ) ( 36
)
and since the scheduling rule (34) does not depend on the instantaneous throughput, we have that r i,+∞,+∞ = p i 1 Si L Φ ( 1 Si ), with N k=1 p k = 1 and r i,+∞,+∞ = r j,+∞,+∞ , ∀i, j, which gives the following formula:

r i,+∞,+∞ = 1 N k=1 S k LΦ( 1 S k ) (37)
This formula will be useful later, because it enables us to determine analytically which users can be covered by adjusting the α, and which users will never be able to be covered. Scheduling them would simply waste resources and they therefore should be ignored when deciding which α to use.

F. α-fair

For the cases in which the throughput cannot be calculated analytically, we still can use the results from Section III to calculate it numerically. We get the algorithm described in Table I, where T is the number of simulation steps, the ξ i (t) are independent exponential random variables with mean 1 and ǫ n are the step sizes.

1. r i,t 0 ,α = 0 ∀i For tm from t 0 to T :

2. Draw N exponentially distributed variables (ξ i (tm)) 0≤i≤N 3. i * = arg max 0≤i≤N ( S i ξ i (tm) r α i,tm,α ) 4. r i,t m+1 ,α = (1 -ǫn)r i,tm,α + ǫnΦ(S i ξ i (tm)) , i = i * (1 -ǫn)r i,tm,α , i = i * TABLE I NUMERICAL METHOD FOR CALCULATING r i,+∞,α
We can choose either ǫ n = 1 n or ǫ n = ǫ with ǫ a small constant. As stated in Section III, convergence to r i,+∞,α occurs in both cases. There is almost sure convergence in the first case and weak convergence in the latter.

G. Remark

It shall be noted that, while the method given for the MTP scheduler is analytically tractable, if S i = S j ∀i = j the number of terms to evaluate in (33) is 2 N -1 , and therefore the formula can only be used for small values of N , in the order of N ≤ 15. For larger values we will have to rely on the numerical method instead.

V. BEHAVIOR OF DIFFERENT SCHEDULING STRATEGIES

A. Scenarios

Three scenarios have been simulated, and for all of them we take Φ(x) = x for simplicity, which corresponds to the infinite bandwidth case.

Scenario 1: PF scheduler, N users with S i = 1 ∀i, since in this particular case the gain is insensitive to the S i , it is the same for all users.

Scenario 2: MTP scheduler, N users with S 1 = 1 , S i = 2 for i ≥ 2. We are interested in the gain of the first user. The gain is not the same for everyone since the scheduler is relatively "unfair".

Scenario 3: α-fair scheduler, 2 users with S 1 = 1 , S 2 = 10. The point of this scenario is to illustrate what happens when a user is near the base station and the other one is far. By far we mean that either the user is physically far from the BS, or he is in an area with very deep shadow fading. In both cases this user will have a bad average channel quality.

B. Interpretation

Figure 1 shows the scheduling gain for user 1 in scenario 1, and Figure 2 in scenario 2. We can see on both figures that the numerical method approximates the closed form formulas quite well, and we can also see on Figure 2 that the gain for user 1 decreases when N increases, since he has poorer channel conditions. Figure 3 shows the gain for both users in scenario 3, and we can see that the larger α is, the larger is the gain for users with poor channel conditions, and so it is possible to manage the coverage for users at cell edge by adjusting α dynamically.

VI. COVERAGE-CAPACITY SELF-OPTIMIZATION USE CASE

A. System Model

This Section considers an important SON use case, namely the coverage-capacity self-optimization using the above results. We consider a TDMA system such as HSDPA. Mobility is ignored.

1) Time Scales: We call averaging period the interval [t m , t m ′ ], on which the average throughput given by the scheduler is calculated and determines which users are not covered. Therefore the averaging period should be long enough for the scheduling algorithm to converge, since for our scheduling gain calculations we have assumed a large number of scheduling intervals.

2) Path Loss: Path loss is given by the following formula:

L i,s = A 1 d ν i,s (38)
with d i,s being the distance between user i and the base station s, and A, ν two constants that depend on the environment.

3) Shadowing: Let χ i,s denote the shadowing between user i and base station s, which we model by a log-normal random variable:

χ i,s = 10 aǫ 1 +bǫ 2 10 ( 39
)
with ǫ i ≡ N (0, σ 2 ) , i ∈ {1, 2} and a,b two constants. As mobility is not considered, shadowing and path loss remain constant during the whole process.

4) Interference:

We consider first-tier neighboring cells as the only source of interference and assume that the total interference, I tot , is related to the average neighboring cell load. Let ρ denote the neighboring cell load, we consider here a simple model to show that the scheduler is able to adapt itself to varying traffic conditions (t in ms):

ρ(t) = |sin(π t 300 )| (40)
(40) assumes that the number of interferers is large.

Interference to user i caused by neighbors follows the same model than the useful signal:

I i,neighbor = ρP max A χ i,neighbor d ν i,neighbor (41)
where P max is the maximal power emitted by a base station, and we assume that all base stations emit with the same power.

I i,tot = neighbor I i,neighbor (42)
5) SINR: Let s i be the serving base station for user i. The SINR for user i can then be calculated by the following formula:

SIN R i = P max χ i,si L i,si I i,tot + σ N 2 (43)
where σ N 2 is the thermal noise. 6) Coverage: We choose the following definition for coverage: a user is considered covered if his mean throughput during the averaging period is superior to T h min , with T h min a fixed threshold necessary to provide a minimal QoS. We are hence concerned with choosing α properly so that the number of covered users is maximal without degrading the cell capacity.

B. Control strategy

We now get to the main point of the article: designing a self-optimizing network functionality for coverage-capacity optimization. It shall adjust α dynamically, based on the observed KPIs available every averaging period: outage, user throughput, etc.

As mentioned before, when α → ∞, the scheduler becomes a MMF scheduler. Therefore the quantity r i,∞,∞ defines two possible behaviors:

• r i,∞,∞ > T h min : if we set α large enough we shall be able to cover user i • r i,∞,∞ < T h min : user i will never be covered, no matter how large α is chosen Hence, if we are in the latter case, we can use (37) to calculate the throughput of the MMF scheduler, and choose to ignore the users that cannot be covered. This is done by ignoring the user with the biggest Si LΦ( 1

S i

) , i.e the user with the lowest S i , since

LΦ( 1 S i ) Si
is the throughput of user i when he is alone in the cell. We can then recalculate the MMF throughput with the formula, and keep doing so until it is above T h min .

C. Optimality criteria

We are interested in finding the α with the best capacitycoverage performance, but we shall not forget that this comes at a price: the larger the α, the larger the capacity loss. For example, choosing α = +∞ all the time would result in covering all users that can be covered all the time, but this controller could hardly be called optimal. Therefore, to avoid a multi-criteria optimization problem, we will define the optimal α as the minimal α that covers all users, and in this way we will not have to consider the maximization of the global throughput explicitly.

D. Modified ǫ-greedy policy

The method proposed here could be seen as a modified version of the ǫ-greedy policy that is popular for several reinforcement learning problems. Thanks to (37), we are able to calculate the maximum number of users that can be covered for α large enough. Therefore any α that has previously resulted in covering all the users that can be covered is an upper bound for the optimal α, at least for a certain period of time if the traffic conditions do not change too drastically.

For the k-th averaging period, n k denotes the number of covered users and N k the maximal number of users that can be covered for α large enough. P ǫ is a small probability used for exploration. The algorithm is described in table II.

Initial phase:

1. Calculate N 0 using (Table III Add i to I 5.

Calculate r i,∞,∞ ignoring users in I, using (37) Result:

6.N k = N -|I| TABLE III CALCULATION OF N k
One shall also note that this method involves virtually no computation, since the Laplace transform of Φ can be calculated numerically beforehand and tabulated, which means that the calculation of N k simply implies looking at most N times in a table of values.

The choice of P ǫ is critical, like in most reinforcement learning algorithms, since it quantifies how often the algorithm will lower the α despite being currently able to cover all users. The point is to try to improve the cell capacity because the current α might not be the lowest α that covers all users anymore. The problem is that by doing so users at cell edge may loose coverage. The value of P ǫ can therefore be related to the speed at which the environment changes.

In our case we have chosen P ǫ = 0.05, that is exploring every 20 averaging periods, with an averaging period of 100ms, which means that the environment is expected to change every 2 seconds.

E. Simulation scenario

To illustrate the method described above, we have simulated it's behavior choosing T h min so that users at cell edge are in the limit of coverage, namely that their mean throughput is close to T h min . Simulation parameters are listed in Table IV

F. Interpretation

Figure 4 shows the evolution of neighboring cell load during the simulation. Figure 5 shows the number of users covered by a PF policy, i.e α t = 1 ∀t, which we use as a reference, and Figure 6 shows the number of users covered using the method described in II. We can see that while the PF policy only covers approximatively half of the users during interference peaks, the self-optimization manages to cover all users almost all the time. More precisely, the cell using a PF scheduler II) covers on the average 5.6 users while the cell with the selfoptimized PS covers on average 9.85 users which represents a significant increase in coverage.

Figure 7 shows how α evolves dynamically, and despite the relatively chaotic behavior of the network, the controller effectively follows the variations of interference. The optimization process uses available KPIs, increasing α when the interfering power increases, and decreasing it otherwise. The fact that the method effectively decreases α when the interfering power lowers is fundamental, since it guarantees that there is an optimal trade-off between capacity and coverage, since α being too high means wasting capacity. Furthermore, the method involves virtually no calculation, and it can be implemented easily in a real network.

VII. CONCLUSION

This paper has presented a self-optimization scheme based on α-fair schedulers that uses KPIs available from the network to enhance coverage and capacity. First, scheduling gains have been derived using both closed form expressions and a statistical based fast algorithm. The scheduling gain computation is necessary for the design of the self-optimization scheme within a simulator. A use case of dynamic adaptation of the α-fair scheduler has been presented. Simulation results show that the self-optimization scheme considerably increases the coverage of users at cell edge and that the α-fair parameter follows the interference variation. The simplicity of the method makes it suitable for real network implementation.

Fig. 1 .Fig. 2 .

 12 Fig. 1. PF scheduling gain as a function of the number of users for S i = 1 ∀i

Fig. 3 .

 3 Fig. 3. Scheduling gain as a function of α for 2 users and S 1 = 1 , S 2 = 10

Fig. 4 .

 4 Fig. 4. Neighboring cell load (eq.(40))

Fig. 5 .Fig. 6 .

 56 Fig. 5. Covered users under PF policy (αt = 1 ∀t)

Fig. 7 .

 7 Fig. 7. Evolution of αt with self-optimizing method (tableII)

  ) 2. Try every α ∈ {1, ..., 10} once 3. Choose the minimal α that covers N 0 users. Repeat: 4. Calculate N k using (Table III) 5. Set α = α k and observe resulting n k If n k < N k : 6. α k+1 = min(α k + 1; 10) If n k = N k :

	7.	α k+1 =	max(α

k -1; 1) with probability Pǫ α k with probability (1 -Pǫ)

  .

	Users per cell	10
	Inter-site distance	1km
	Pmax	16W
	Number of users	10
	t m+1 -tm	1ms
	Averaging period	100ms
	α	(1, ..., 10)
	ǫ	0.05
	Pǫ	0.05
	µ	3.5 (dense urban)
	σ	6.5dB
	a
	b	0.5
	σ 2 N	-173dBm/Hz

TABLE IV MODEL PARAMETERS

 IVPARAMETERS

This work is partially supported by the ANR project ECOSCells and partly by a CRE contract with Pierre et Marie Curie University(Paris VI)


Mickael Coustaty
email: mcoustat@univ-lr.fr

Sloven Dubois
email: sduboi01@univ-lr.fr

Jean-Marc Ogier
email: jmogier@univ-lr.fr

Michel Menard
email: mmenard@univ-lr.fr

Segmenting and Indexing old documents using a letter extraction

This paper presents a new method to extract areas of interest in drop caps and particularly the most important shape: Letter itself. This method relies on a combination of a Aujol and Chambolle algorithm and a Segmentation using a Zipf Law and can be enhanced as a three-step process: 1)Decomposition in layers 2)Segmentation using a Zipf Law 3)Selection of the connected components.

Introduction

With the improvement of printing technology since the 15th century, there is a huge amount of printed documents published and distributed. Since that time, books have been falling into decay and degrading. This means not only books themselves are disappearing, but also the knowledge of our ancestors. Therefore, there are a lot of attempts to keep, organize and restore ancient printed documents. With the improving digital technology, one of the preservation methods of these old documents is the digitization. However, digitized documents will be less beneficial without the ability to retrieve and extract the information from them which could be done by using techniques of document analysis and recognition. This paper presents a new method to improve old document images description using segmentation and characterization of letter inside.

NaviDoMass

NAVigation Into DOcuments MASSes is a french collaborative projec, financed by the National French Research Agency, with the challenge to index ancient documents. With the collaboration of seven laboratories in France, the global objective of this project is to build a framework to derive benefit from historical documents. It aims to preserve and provide public accessibility to this national heritage and is established on four principles: anywhere (global access), anyone (public and multilingual), anytime and any media (accessible through various channels such as world wide web, smartphone, etc.). The focus of NAVIDO-MASS is on five studies: (1) user requirement, participative design and ground truthing, (2) document layout analysis and structure based indexing, (3) information spotting, (4) structuring the feature space [HSO + 08,JT08] and (5) interactive extraction and relevance feedback. As a part of NAVIDOMASS project, this paper focuses on the graphics part : graphics indexing and CBIR. However, the main interest of this study is based on specific graphics called drop caps, and on the extraction of shapes in drop caps and particularly on the most important shape : the letter itself. This work is inspired by [START_REF] Pareti | Ancient initial letters indexing[END_REF] and [START_REF] Uttama | Segmentation and retrieval of ancient graphic documents[END_REF] which used a Zipf law and a Wold decomposition to extract elements of drop caps.

Drop caps in details

The images of documents of the inheritance are heterogeneous and damaged by time. Drop caps (decorative capital letters also named drop caps or drop cap) belong to the images to index. These images are made up of two principal elements: the letter and the background. (See Fig. 1). An important step in the recognition process of the drop caps consists in segmenting the letter and the elements of the background to characterize them using a signature. This signature will allow a simple and fast comparison for our indexing process of great masses of data. This paper presents in details the various stages of our method: 1) Simplification of the images using layers 2) Extraction of shapes from one of these layers 3) Selection of these shapes.

Simplification of images using layers

Decomposing an image into meaningful components appears as one of major aims in recent development in image processing. The first goal was image restoration and denoising; but following the ideas of Yves Meyer [START_REF] Meyer | Oscillating patterns in image processing and nonlinear evolution equations[END_REF], in total variation minimization framework of L. Rudin, S. Osher and E. Fatemi [START_REF] Rudin | Nonlinear total variation based noise removal[END_REF], image decomposition into geometrical and oscillatory (i.e texture) components appears an useful and very interesting way in computer vision and image analysis. There is a very large literature and also recent advances on image decomposition models, image regularization and texture extraction and modeling. So, we only cite, among many others, most recent works which appear most relevant and useful paper. In this way, reader can refer to the work of Stark et al. to cover the most recent and relevant advances.

The developped method

Images of drop caps are very complex and very rich images in terms of information and requires to be simplified. These images are mainly made up of lines, unsuitable for usual texture methods. We thus use an approach developed by Dubois and Lugiez [START_REF] Dubois | Adding a noise component to a color decomposition model for improving color texture extraction[END_REF] to separate original image in several layers of information, easier to process. This decomposition relies on minimization of a functional calculus F :

inf (u,v,w)∈X 3 /f =u+v+w F (u, v, w) = J(u) Regularization TV + J * v µ Texture extraction + B * w δ
Noise extraction by: shrinkage

+ 1 2λ f -u -v -w 2 X Residual part (1)
where each element of the functional represents a layer of information and corresponds to a type of information in the image. B * can be seen as a wavelet soft threshold, J * a computation of a gradient and J a linear computation between the original image and the two precedent elements. For deeper explanation about notations and each element, one can refer to [START_REF] Dubois | Adding a noise component to a color decomposition model for improving color texture extraction[END_REF].

Layers in details

We are aiming to catch the pure geometrical component in an image independently of texture and noise to extract shapes. So, we are studying here how to decompose images into three components:

-The Regularized Layer corresponds to the area of image which has low fluctuation of gray level. This layer permits to highlight geometry which corresponds to shapes in the image. In the following of this paper, we will name this layer the "Shape Layer".

-Oscillating Layer which corresponds to the oscillating element of the image.

In our case, this layer highlights texture from drop caps and in the following of this paper, we will name this layer the "Texture Layer". -Highly Oscillating Layer which corresponds to noise in image. in fact, this layer retrieves all that do not belong to the two first layers. So, we can find in this layer noise, text of background and problem of ageing. Our goal is to recognize old document images while being robust toward noise variations.

That is why we will not use this layer in the next of this work.

An example of decomposition applied to the first image of Fig. 1 is given in Fig. 2. Regularized layer obtained by decomposition contain all shapes. In order to extract them and to select the most interesting, we used a Zipf Law. Zipf Law was empirically defined by George Kingsley Zipf and relies on the frequency and on the rank of appearance of words in a text. This law has been transposed on images by [START_REF] Pareti | Ancient initial letters indexing[END_REF] by taking subimages as patterns and by calculating frequency and rank of these patterns. This method is a three steps process:

-Simplification of image applying a 3-means on gray level histogram to reduce number of patterns -Seek for patterns of size three by three to obtain their frequency and their rank -Classification of patterns in three classes according to the evolution law of the frequency compared to their rank

Simplification of images

Images provided by historians are composed of 256 gray levels. A huge amount of three by three patterns are possible (theoretically 256 9 different patterns). Indeed, if all patterns are represented only once, the model that is deduced from the pattern frequencies would not be reliable, the statistics would lose their significance. Then it is necessary to restrict the number of perceived patterns to give sense to the model.

To decrease the number of graylevels in the image, we have made use of kmeans clustering algorithm [START_REF] Mcqueen | Some methods for classification and analysis of multivariate observations[END_REF]. As images we are dealing with in this study are composed of three elements (background, foreground and motive), we decided to keep only three gray levels. Moreover, this reduction is made without loosing too much information.

Patterns research

Once the number of gray levels have been reduced, a simple count of each pattern permit to know their frequency and their rank. This step is essential to build the Zipf curve which represent the evolution law of the frequency compared to their rank. From this curve, three straight lines are computed to estimate three main parameters of Zipf laws that interfere. The splitting points are defined as the furthest points from the straight line linking the two extreme points of the curve. The first line, which correspond to the most frequent patterns, represent shapes of image (uniform areas). We have extracted pixels from each layer and we display them in an image.

Shapes extration

Once shapes have been extracted, one can seek connected components of binarized image. When we observe all the connected components in Figure 5(b), we can see that the most important shapes have particular characteristics (based on size, location, center of mass and eccentricity). A selection of connected components in accordance with these parameters permit to obtain region of interest of drop caps. An example of extracted connected components can be seen in Figure 5(c). Finally, with an accurate selection on these parameters, the most important connected component for historian can be extracted: the letter. This one can be obtained by selecting the bigger connected component which center of mass is centered and which don't touch borders of image. An example of result can be seen in Figure 5.

Experimentations and validation

The evaluation of such a system is a fundamental point because it guarantees its usability by the users, and because it permits to have an objective regard on the system. In the context of such a project, the implementation of an objective evaluation device is quite difficult, because of the variability of the user requirements: historian researchers, netsurfers, are likely to retrieve many different information which can be very different the ones from the others.

In the context of NAVIDOMASS project, and more specifically for this objective of drop caps indexing, we have decided to evaluate the quality of our system by considering the purpose of Letter Based Retrieval . This choice is motivated by the fact that many historians want to be able to retrieve drop caps in regard with this criterion. As a consequence, the evaluation of our system relies on the application of an OCR system at the issue of the letter segmentation. Considering these aspects, the classification rate is the main performance evaluation criterion of our system. For the evaluation, we have used commercial OCR systems, as well as open source system. In order to implement the evaluation, we have used FineReader on the one hand, and Tesseract on the other hand. We have experimented the approach on an image database containing 4500 images. 1500 of these images were considered for the training set, while 3000 were considered for the tests.

The results are summarized in the Table 1. As one can see the obtained results

FineReader Tesseract Classification Rate 72,8% 67,9%

Table 1. Recognition rate of drop caps using two kinds of OCR are still unsatifying, but very encouraging. We are working on the improvement of the processing chain, as one can see in the conclusion and perspective part. However, there is not such existing system dealing with this problem, and historians researchers are satisfied to use our system for the classification of their graphic images. The cases for which our system fails correspond to very difficult images, as one can see an example in Fig. 6.

Conclusions

This paper presents a new method to extract informations in drop caps. It relies on a combination of two decomposition. The first one simplifies image to only extract shapes of original image while the second one, a Zipf Law' decomposition, realize a background-foreground segmentation. From this segmentation, a selection of shapes segmented permit to extract some interesting shapes and particularly the letter itself. The first experimentations are encouraging and we are actually working on improvements of this global process.

Fig. 1 .

 1 Fig. 1. Drop Caps Examples

  [SED05], Aujol et al. [AAFC05], [AGCO06], Aujol and Chambolle [AC05], Aujol and Ha Kang [AK06], Vese and Osher [OSV03], [VO04], [VO06] and more recently Bresson and Chan [BC07] and Duval et al. [DAV08]

Fig. 2 .

 2 Fig. 2. An example of drop cap decomposition using Aujol and Chambolle algorithm

Figure. 3

 3 show an example of a Zipf curve with its drop cap while Figure. 4 show an example of binarized images obtained with each straight line.

Fig. 3 .Fig. 4 .Fig. 5 .

 345 Fig. 3. Example of a Drop Cap and its Zipf plot where are indicated the different straight zones extracted

Fig. 6 .

 6 Fig. 6. An example of very difficult letter extraction