Frédéric Mazenc
email: fred-eric.mazenc@l2s.centralesupelec.fr

Michael Malisoff
email: mal-isoff@lsu.edu

Corina Barbalata
email: cbarbalata@lsu.edu

Zhong-Ping Jiang
email: zjiang@nyu.edu

Z.-P Jiang

Event-Triggered Control Using a Positive Systems Approach

Keywords: stabilization, event-triggered, interval observer. F

We provide a new event-triggered control strategy that relies on the notion of positive systems. Our results cover output feedback, and robustness with respect to uncertain dynamics. Our proofs are based on interval observers. Our example shows potential advantages of our approach over earlier event-triggered methods.

I. INTRODUCTION

Event-triggered control has played an increasingly important role in control theoretic research; see, for instance, the works [START_REF] Heemels | An introduction to event-triggered and self-triggered control[END_REF], [START_REF] Peralez | Event-triggered output feedback stabilization via dynamic high-gain scaling[END_REF], [START_REF] Tabuada | Event-triggered real-time scheduling of stabilizing control tasks[END_REF], and [START_REF] Wang | Self-triggered feedback control systems with finite-gain L 2 stability[END_REF]. One advantage of using event-triggered control is that it can reduce the computational burden associated with implementing controls, by only changing the value of the control when there is a significant event. These events can be characterized as times when the state enters some prescribed region of the state space. This contrasts with standard zero-order hold strategies, where the times at which the control values are recomputed are usually independent of the state. Much event-triggered control literature is based on small gain methods; see, e.g., [START_REF] Jiang | Small-gain theory for stability and control of dynamical networks: A survey[END_REF]. Small gain methods have the desirable advantage of ensuring robustness to uncertainty, but can sometimes be conservative, insofar that they can lead to unnecessarily frequent recomputation times for the controls.

Although emerging computing methods can facilitate recomputing control values, the increasing use of shared wireless (or shared wired) networked control systems calls for designing controls that take computation, communication, and energy constraints into account [START_REF] Heemels | An introduction to event-triggered and self-triggered control[END_REF]. This led to systematic designs for event-triggered controls, e.g., in [START_REF] Heemels | Analysis of eventdriven controllers for linear systems[END_REF], [START_REF] Henningsson | Sporadic eventbased control of first-order linear stochastic systems[END_REF], [START_REF] Tabuada | Event-triggered real-time scheduling of stabilizing control tasks[END_REF], and [START_REF] Yook | Trading computation for bandwidth: Reducing communication in distributed control systems using state estimators[END_REF]. During the same time, much research has been done on positive systems, i.e., systems for which the nonnegative orthant is positively invariant, leading to new control analysis and designs that overcome some of the challenges of using traditional Lyapunov function methods. Much work on positive systems uses interval observers (as defined, e.g., in [START_REF] Gouzé | Interval observers for uncertain biological systems[END_REF], [START_REF] Mazenc | Interval observers for linear timeinvariant systems with disturbances[END_REF], and [START_REF] Raissi | Interval state estimation for a class of nonlinear systems[END_REF]), which provide intervals containing the values of unknown states when the inequalities involving vector valued solutions are viewed componentwise; see [START_REF] Mazenc | Interval observers for linear timeinvariant systems with disturbances[END_REF] and [START_REF] Mazenc | Stability analysis for time-varying systems with delay using linear Lyapunov functionals and a positive systems approach[END_REF]. Positive systems and interval observers led to advances in aerospace engineering, mathematical biology, and other areas. However, we believe that these approaches had not been used for the systematic design and analysis of event-triggered controls.

This motivates this work, where we use a new positivity based event-triggered control technique to design control strategies that yield less conservative triggering conditions than those in the literature. We establish an output and a robustness result, covering cases where there may be time-varying uncertainties in the dynamics. Our stability proofs use interval observers as comparison systems, and are reminiscent of the results of [START_REF] Mazenc | Stability analysis for time-varying systems with delay using linear Lyapunov functionals and a positive systems approach[END_REF] insofar that they are based on linear Lyapunov functions for positive systems. However, [START_REF] Mazenc | Stability analysis for time-varying systems with delay using linear Lyapunov functionals and a positive systems approach[END_REF] did not cover eventtriggering, and to the best of our knowledge, the present work is the first systematic use of interval observers and positive systems to design event-triggered controls.

We provide the necessary notation and preliminaries and introduce our main class of systems in Section II. Then, in Section III, we prove our theorems on stability, extensions to systems with outputs where the eventtriggered controller uses an observer, and robustness to uncertain models. In Section IV, we illustrate potential advantages of our method using an example where our method ensures less frequent control recomputations than the main small gain event-triggered result in [START_REF] Jiang | Small-gain theory for stability and control of dynamical networks: A survey[END_REF]. We close in Section V by summarizing our findings and suggesting future research directions.

II. PRELIMINARIES

We use the following notation, where the dimensions of our Euclidean spaces are arbitrary unless otherwise noted. The arguments of functions will be omitted whenever no confusion can arise from the context. Set

Z 0 = {0, 1, 2, ...} and N = Z 0 \{0}. For a matrix G = [g ij ] ∈ R r×s , we set |G| = [|g ij |],
i.e., the entries of |G| are the absolute values of the corresponding entries of G. Similarly, we set G + = [max{g ij , 0}] and G -= G + -G. A square matrix is called Metzler provided all of its off diagonal entries are nonnegative. For two matrices D = [d ij ] an E = [e ij ] of the same size, we write D < E (resp., D ≤ E) provided d ij < e ij (resp., d ij ≤ e ij ) for all i and j. We also write D E provided there is a pair (i, j) such that d ij > e ij . We adopt similar notation for vectors. A matrix S is called positive provided 0 < S. Let || • || denote the standard Euclidean norm of vectors and matrices, and || • || ∞ (resp., || • || J ) denote the sup norm of matrix valued functions in this norm over their entire domain (resp., over an interval J in their domain). We let I denote the identity matrix of any dimension, and we use the standard definition and properties of state transition matrices (i.e., fundamental solutions), e.g., from [START_REF] Sontag | Mathematical Control Theory, Second Edition[END_REF]Appendix C].

We consider the system

ẋ(t) = Ax(t) + Bu(t) (1)
where x is valued in R n , u is valued in R p , and the matrices A and B are constant. We assume: Assumption 1: There is a matrix K ∈ R p×n such that the matrix H = A + BK is Hurwitz and Metzler.

Remark 1: Assumption 1 is not restrictive because many systems satisfy it after a preliminary change of coordinates. When the pair (A, B) is controllable, there is a change of coordinates that provides new matrices A and B that satisfy this assumption. In fact, under Assumption 1, there is a matrix K ∈ R p×n such that A+BK is Hurwitz with negative real eigenvalues. Then there exists an invertible matrix P ∈ R n×n such that P (A+BK)P -1 is Metzler because the Jordan canonical form of the matrix A+BK is Metzler. Thus Assumption 1 is satisfied by the pair (P AP -1 , P B).

Recall that the Zeno phenomenon is that a system with sampling has infinitely many sample times on some interval of finite length. A key ingredient in our analysis in later sections will be finding a lower bound ν > 0 on the intersample times t i+1 -t i between the event triggering times, which will imply that the Zeno phenomenon does not occur. This constant ν will be provided by the following lemma:

Lemma 1: Let (A, B) satisfy Assumption 1. Let Γ ∈ R n×n be a positive matrix such that the matrix

M = H + |BK|Γ (2)
is Metzler and Hurwitz. Let Ω : [0, +∞) → R n×n be the function

Ω(s) = e sA + s 0 e A d BK. (3)
Then there exists a constant ν > 0 such that for all s ∈ [0, ν], the matrix Ω(s) is invertible and the inequality

I -Ω(s) -1 ≤ Γ (4)
is satisfied.

Proof: First observe that Assumption 1 implies that there exists a positive matrix Γ ∈ R n×n such that M as defined in ( 2) is Metzler and Hurwitz. In fact, since 0 ≤ |BK| and 0 ≤ Γ, it follows that 0 ≤ |BK|Γ, which implies that M is Metzler. Moreover it is Hurwitz when the entries of |BK|Γ are sufficiently small. Next, we conclude the proof by observing that Ω is continuous, Ω(0) = I, and 0 < Γ.

Remark 2: Since e sA is invertible, the matrix

Ω(s) in (3) with s ≥ 0 is invertible if and only if I + s 0 e ( -s)A d BK is invertible. Thus, it is invertible if s 0 e ( -s)A d BK < 1, (5)
which follows by checking that the nullspace of I + s 0 e ( -s)A d BK is trivial. The inequality ( 5) is satisfied if BK = 0. If BK = 0, then for any 0 ∈ (0, 1), we obtain the bound s < s * , where s * is the sup of all r values such that the integral in ( 5) is bounded above by 0 for all s ∈ [0, r]. A more explicit bound on the allowable s values in the BK = 0 case can be obtained as follows. If BK = 0, then ( 5) is satisfied if

s 0 e (s-)||A|| d < 1 ||BK|| . (6)
If A = 0, then this gives the condition s < 1/||BK||. On the other hand, if A = 0, then we instead have the condition (e s||A|| -1)/||A|| < 1/||BK|| which is equivalent to s < (1/||A||) ln (1 + ||A||/||BK||). Remark 3: Notice for later use that since M defined in ( 2) is Metzler and Hurwitz, there exist a vector V ∈ R n such that 0 < V , and a constant p ∈ (0, +∞), such that the inequality

V M ≤ -pV (7)
holds. This result is a consequence of [2, Lemma 2.3, p. 41], for instance.

III. MAIN RESULTS

A. State Feedback Event-Triggered Control

We next prove the following theorem, whose condition (c) means that for each > 0, there exist t ‡ ∈ (t i+1 , t i+1 + ) and j ∈ {1, ..., n} such that

|x j (t ‡ ) -x j (t i )| > n g=1 Γ jg |x g (t ‡ )| (8)
is satisfied, and where we continue our notation |S| = [|s ij |] for matrices S = [s ij ] from Section II:

Theorem 1: Consider the system (1) under Assumption 1 and let Γ = [Γ j,k ] > 0 satisfy the requirements of Lemma 1 and K satisfy the requirements from Assumption 1. Consider the sequence of nonnegative numbers t i defined by t 0 = 0, (a)

ẋ(t) = Ax(t) + BKx(t i ) if t ∈ [t i , t i+1 ), (b) |x(t) -x(t i )| ≤ Γ|x(t)| if t ∈ [t i , t i+1
), and (c) For each > 0 and each i ∈ Z 0 such that t i+1 < +∞, there is a

t ‡ ∈ (t i+1 , t i+1 + ) such that |x(t ‡ ) -x(t i )| Γ|x(t ‡ )|
for all i ∈ Z 0 . Then the closed loop system given by (a)-(c) admits the origin as a globally exponentially stable equilibrium point on R n . Proof: First Part. Letting ν be the constant from Lemma 1, we prove that the inter-event times t i+1 -t i are bounded below by ν. More precisely, we prove that either there are only a finite number of instants t 0 , ..., t j and inf l∈{0,...,j-1} (t l+1 -t l ) ≥ ν; or else there are infinitely many instants t i and inf l∈Z0 (t l+1 -t l ) ≥ ν.

Consider any i ∈ Z ≥0 such that the Zeno phenomenon does not occur between [0, t i ]. If x(t i ) = 0, then the theorem of existence and uniqueness of the solutions implies that x(t) = 0 for all t ≥ t i . Next, consider the case where x(t i ) = 0. Continuity of x(t) implies that t i+1 is well-defined and t i+1 = +∞ or t i+1 is finite and t i+1 > t i . Consider the case where t i+1 is finite. By integrating the equation in (a) between [t i , t) with t ∈ [t i , t i+1 ), we obtain

x(t) = Ω(t -t i )x(t i ) ( 9
)
where Ω is defined in [START_REF] Heemels | An introduction to event-triggered and self-triggered control[END_REF]. From (4), it follows that, for any t ∈ [t i , t i + ν], the vector inequality

I -Ω(t -t i ) -1 |x(t)| ≤ Γ|x(t)| is satisfied. It follows that x(t) -Ω(t -t i ) -1 x(t) ≤ Γ|x(t)|. (10)
This inequality in combination with [START_REF] Mazenc | Interval observers for linear timeinvariant systems with disturbances[END_REF] gives

|x(t) -x(t i )| ≤ Γ|x(t)| (11)
for all t ∈ [t i , t i + ν]. We conclude that t i+1 ≥ t i + ν. Thus, the Zeno phenomenon does not occur and that the inter-sample times are bounded below by ν Second Part. We study the stability of the closed loop system from (a)-(c). The case where there is j ∈ Z ≥0 such that x(t j ) = 0 is trivial. Thus, we consider the case where x(t j ) = 0 for all j ∈ Z ≥0 . For notational convenience, we introduce the function µ defined by µ(t) = x(t i ) -x(t) for all t ∈ [t i , t i+1 ) and all i ∈ Z 0 . Then (a)-(c) give

ẋ(t) = Hx(t) + BKµ(t) |µ(t)| ≤ Γ|x(t)| (12)
for all t ≥ 0, where H = A + BK as before.

To study [START_REF] Raissi | Interval state estimation for a class of nonlinear systems[END_REF], we exploit the fact that H is Metzler, to adopt an analysis approach based on interval observers. We introduce the dynamic extension

ẋ(t) = Hx(t) + (BKµ(t)) + ẋ(t) = Hx(t) -(BKµ(t)) -. (13)
Consider a solution of ( 12) with x(0) ∈ R n as its initial condition and any initial conditions x(0) ∈ R n and x(0) ∈ R n for (13) such that

x(0) < x(0) < x(0) x(0) < 0 < x(0) . ( 14
)
Observe that e(t) = x(t) -x(t) and e(t)

= x(t) -x(t) satisfy ė(t) = He(t) + (BKµ(t)) - ė(t) = He(t) + (BKµ(t)) + . ( 15
)
Since the matrix H is Metzler, it follows (e.g., from [8, Lemma 1]) that e(t) ≥ 0 and e(t) ≥ 0 for all t ≥ 0. We deduce that

x(t) ≤ x(t) ≤ x(t) (16)
and also

x(t) ≤ 0 ≤ x(t) (17)
for all t ≥ 0, where (17) follows because x and -x are solutions of ż = Hz+(BKµ) ± and from again applying [8, Lemma 1] using the Metzler matrix H. We deduce from ( 16)-(17

) that x(t) -x(t) ≤ x(t) ≤ x(t) -x(t), i.e., |x(t)| ≤ s(t) (18)
for all t ≥ 0, where s(t) = x(t) -x(t).

We next analyze the behavior of s. We have

ṡ(t) = Hs(t) + (BKµ(t)) + + (BKµ(t)) - = Hs(t) + |BKµ(t))|. ( 19
)
Consider the linear function W (s) = V s, where V is the vector in Remark 3. The time derivative of W along (19) satisfies

Ẇ (t) = V Hs(t) + V |BKµ(t))| ≤ V Hs(t) + V |BK|Γ|x(t)|, (20)
where the last inequality is a consequence of the inequality in [START_REF] Raissi | Interval state estimation for a class of nonlinear systems[END_REF]. Substituting (18) in (20), we obtain

Ẇ (t) ≤ V Hs(t) + V |BK|Γs(t) = V M s(t), ( 21
)
where M is the matrix defined in [START_REF] Haddad | Nonnegative and Compartmental Dynamical Systems[END_REF]. From [START_REF] Mazenc | Finite time estimation through a continuous-discrete observer[END_REF], it follows that

Ẇ (t) = -pV s(t) = -pW (s(t)). (22)
Since V > 0 and s(t) ≥ 0 for all t ≥ 0, we deduce that s(t) exponentially converges to zero as t → +∞. We can assume that s(0) ≤ 4|x(0)|, e.g., by requiring that x(0) ≤ 2|x(0)| and x(0) ≥ -2|x(0)|. Hence, from the inequality (18), we deduce that x(t) goes exponentially to the origin as t → +∞.

B. Output Feedback Control

The event-triggered control in Theorem 1 makes essential use of measurements of the state x(t), and it is nontrivial to generalize it to cases where the state is not available for measurement. This motivates this section, where we consider the system (1) with an output, namely,

ẋ(t) = Ax(t) + Bu(t) y(t) = Cx(t) (23)
with y valued in R q and C being a constant matrix. We use this classical assumption: Assumption 2: The pair (A, C) is observable. Assumption 2 ensures that there is a matrix L ∈ R n×q such that the matrix

G = A + LC (24)
is Hurwitz. This allows us to prove: Theorem 2: Consider the system (23) under Assumptions 1-2. Let Γ > 0 satisfy the requirements of Lemma 1 such that (7) holds, and the constant ν > 0 satisfy the requirements of Lemma 1. Consider the sequence of nonnegative numbers t i and the feedback K x(t i ) defined by t 0 = 0, (a') and(d') For each > 0 and each i such that t i+1 < +∞, there is a t ‡ ∈ (t i+1 , t i+1 + ) such that |x(t ‡ ) -

ẋ(t) = Ax(t) + BK x(t i ) if t ∈ (t i , t i+1 ), (b') ẋ(t) = Ax(t) + BK x(t i ) + L[C x(t) -y(t)] if t ∈ (t i , t i+1 ), (c') |x(t) -x(t i )| ≤ Γ|x(t)| + B t max{0,t-ν} |C x( ) - y( )|d for all t ∈ [t i , t i+1 ),
x(t i )| Γ|x(t ‡ )| + B t ‡ max{0,t ‡ -ν} |C x( ) - y( )|d
with i ∈ Z 0 , where x(0) = 0 and

B = sup ∈[0,ν] |Ω( ) -1 |e ν|A| |L|. (25)
Then the system given by (a')-(d') admits the origin as a globally exponentially stable equilibrium point on R n .

Proof: First part. We prove that the inter-event times t i+1 -t i are bounded below by ν. More precisely, we prove that either there are only a finite number of instants t 0 , ..., t j and inf l∈{0,...,j-1} (t l+1 -t l ) ≥ ν;

(26) or there are an infinite number of instants t i and inf l∈Z0 (t l+1 -t l ) ≥ ν.

Let us consider any i ∈ N such that the Zeno phenomenon does not occur between [0,

t i ]. If Γ|x(t i )| + B ti max{0,ti-ν} |C x( ) -y( )|d = 0, (27) then x(t i ) = 0 and C x( ) = Cx( ) for all ∈ [t i -δ 0 , t i ]
for some δ 0 > 0 because t i ≥ t 1 > 0 (which follows because x(0) = 0). Assumption 2 implies that x(t i ) = x(t i ). We deduce that (x(t i ), x(t i )) = (0, 0). Then the existence and uniqueness property of the solutions imply that (x(t), x(t)) = (0, 0) for all t ≥ t i .

Next, consider the case where

Γ|x(t i )| + B ti max{0,ti-ν} |C x( ) -y( )|d > 0.
(28) Continuity of x implies that t i+1 is well-defined, and that either t i+1 = +∞, or else t i+1 is finite and t i+1 > t i . Consider the case where t i+1 is finite. By integrating the x-subsystem in (b') between [t i , t) with t ∈ [t i , t i+1 ), we obtain

x(t i ) = Ω(t -t i ) -1 x(t) -Ω(t -t i ) -1 t ti e (t-)A L[C x( ) -y( )]d . ( 29
)
As an immediate consequence,

|x(t) -x(t i )| = x(t) -Ω(t -t i ) -1 x(t) +Ω(t -t i ) -1 t ti ∆(t, )d ≤ I -Ω(t -t i ) -1 |x(t)| + Ω(t -t i ) -1 t ti ∆(t, )d ≤ Γ|x(t)| + Ω(t -t i ) -1 t ti ∆(t, )d (30) when t ∈ [t i , t i +ν], where ∆(t, ) = e (t-)A L[C x( )- y( )]. Consequently, |x(t) -x(t i )| ≤ Γ|x(t)| + B t ti Ĉ( )d ≤ Γ|x(t)| + B t max{0,t-ν} Ĉ( )d (31) for all t ∈ [t i , t i + ν], where Ĉ( ) = |C x( ) -y( )|. It follows that t i+1 -t i ≥ ν for all i ∈ Z 0 .
Second part. In this part, we prove the exponential stability of the equilibrium point of the closed loop system. In what follows, all equalities and inequalities should be understood to hold for all t ≥ 0, unless otherwise indicated.

Let

x(t) = x(t) -x(t). Then ẋ(t) = Gx(t) ( 32
)
where G is the matrix defined in (24). Notice for later use that x(t) exponentially converges to the origin as t → +∞. Also, with the simplifying notation μ(t) = x(t i ) -x(t), we have

ẋ(t) = H x(t) + BK μ(t) + LC x(t) (33)
We next introduce this comparison system:

ẋ(t) = Hx(t) + (BK μ(t)) + + (LC x(t)) + ẋ(t) = Hx(t) -(BK μ(t)) --(LC x(t)) - (34)
As in the previous section, one can prove that if x(0) < 0 < x(0) and x(0) < x(0) < x(0), then for all t ≥ 0, the inequalities

x(t) ≤ 0 ≤ x(t) and x(t) ≤ x(t) ≤ x(t) (35)
hold. For the preceding initial conditions, consider s(t) = x(t) -x(t). Then the bounds (35) give

|x(t)| ≤ s(t). (36)
Simple calculations give

ṡ(t) = Hs(t) + |BK μ(t)| + |LC x(t)|. (37)
Consider the linear function W (s) = V s. Then, for all t ≥ 0, (31) and our choice (2) of M give

Ẇ (t) = V Hs(t) + V |BK μ(t)| +V |LC x(t)| ≤ V Hs(t) + V |BK| (Γ|x(t)| +B t max{0,t-ν} Ĉ( )d +V |LC x(t)| = V M s(t) + V |LC x(t)| +V |BK|B t max{0,t-ν} Ĉ( )d . (38)
Using [START_REF] Mazenc | Finite time estimation through a continuous-discrete observer[END_REF], we obtain

Ẇ (t) ≤ -pW (s(t)) + V |LC x(t)| +V |BK|B t max{0,t-ν} Ĉ( )d = -pW (s(t)) + Ξ(t), (39)
where

Ξ(t) = V |BK|B|C| t max{0,t-ν} |x( )|d +V |LC x(t)|. (40)
Since s(t) ≥ 0 for all t ≥ 0 and Ξ is nonnegative valued and converges exponentially to the origin as t → +∞, it follows that W (s(t)) converges exponentially to zero as t → +∞. Hence, s(t) converges exponentially to the origin as t → +∞. The theorem now follows from (36), the bound |x(t)| ≤ |x(t)|+|x(t)|, and the corresponding argument from the proof of Theorem 1.

C. Robustness

We next generalize our result from the system (1) with known vector fields to cases with an additive disturbance of the form A δ (t)x(t) of the form

ẋ(t) = (A + A δ (t))x(t) + Bu (41)
where the function A δ will satisfy our requirements below. We impose a small enough known bound |A δ | ∞ on the unknown function, because our objective is to propose a stabilizing feedback that is robust with respect to the term A δ (t)x(t). This motivates the following assumption, which will be satisfied under our Assumption 1 when the entries of A δ and Γ are small enough in absolute value and A is Metzler with positive off diagonal elements: Assumption 3: The bounded function A δ : [0, +∞) → R n×n is piecewise continuous and such that A + A δ (t) is Metzler for all t ≥ 0. Also, for the Hurwitz matrix H satisfying Assumption 1, and for a Γ satisfying the requirements of Lemma 1, there is a constant a > 0 such that the system

ξ(t) = H + |A δ (t)| + (1 + a)|BK|Γ ξ(t) (42)
admits the origin as a uniformly exponentially stable equilibrium point on R n . We prove the following result: Theorem 3: Let (41) satisfy Assumptions 1 and 3, and choose ν to satisfy Lemma 1. Let A δ be such that

||A δ || ∞ νe ν(||A||+||A δ ||∞) (1+ν||BK||)||Ω -1 || [0,ν] < c 0 , (43)
where c 0 ∈ (0, 1) is any constant such that c0

1-c0 ||Ω -1 || [0,ν] ≤ a min {Γ ij : 1 ≤ i ≤ n, 1 ≤ j ≤ n} . (44)
Then the system with sampling times t i defined by t 0 = 0,

(a") ẋ(t) = (A+A δ (t))x(t)+BKx(t i ) if t ∈ (t i , t i+1 ), (b") |x(t) -x(t i )| ≤ (1 + a)Γ|x(t)| if t ∈ [t i , t i+1 )
, and (c") For each > 0 and each i such that t i+1 < +∞, there is a t ‡ ∈ (t i+1 , t i+1 + ) such that |x(t ‡ ) -

x(t i )| (1 + a)Γ|x(t ‡ )|
for all i ∈ Z 0 admits the origin as a globally exponentially stable equilibrium point on R n . Proof: First part. We first prove that the interevent times t i+1 -t i are bounded below by ν. More precisely, we prove that either there are only a finite number of instants t 0 , ..., t j and inf l∈{0,...,j-1} (t l+1t l ) ≥ ν; or else there are an infinite number of instants t i and inf l∈Z0 (t l+1 -t l ) ≥ ν. Our proof is based on [7, Lemmas 1-2], which we also include for reference in our appendix below.

Let Φ A+A δ be the state transition matrix of A+A δ (t). Then, for any i ∈ Z 0 , we can apply variation of parameters to (a") over [t i , t) with t ∈ [t i , t i+1 ] to get

x(t) = Φ A+A δ (t, t i ) + t ti Φ A+A δ (t, )d BK x(t i ).
(45) For all t ∈ [t i , t i + ν], the quantity in squared brackets in (45) can be written as

Ω(t -t i ) + Φ A+A δ (t, t i ) -e A(t-ti) + t ti Φ A+A δ (t, ) -e (t-)A d BK = Ω(t -t i ) [I + η(t, t i )] , (46)
where

η(t, t i ) = Ω(t -t i ) -1 Φ A+A δ (t, t i ) -e A(t-ti) + t ti Φ A+A δ (t, ) -e (t-)A d BK (47)
and Ω as defined in Lemma 1. Using the bound

Φ A+A δ (t, t i ) -e A(t-ti) ≤ ||A δ ||νe ν(||A||+||A δ ||∞) (48)
which follows e.g., from [7, Lemma 2], and recalling (43), it follows that ||η(t, t i )|| < c 0 < 1, and therefore that

I + η(t, t i ) is invertible, which implies that x(t i ) = R(t, t i )x(t) for all t ∈ [t i , t i+1 ), where R(t, t i ) = Φ A+A δ (t, t i ) + t ti Φ A+A δ (t, )d BK -1 . ( 49
) This is equivalent to x(t) -x(t i ) = [I -R(t, t i )] x(t),
which can be rewritten as

x(t) -x(t i ) = I -Ω(t -t i ) -1 + Ω(t -t i ) -1 -R(t, t i )] x(t) (50)
As an immediate consequence,

|x(t) -x(t i )| ≤ I -Ω(t -t i ) -1 + Ω (t, t i ) |x(t)| ≤ Γ + Ω (t, t i ) |x(t)| (51)
where Ω (t, t i ) = Ω(t -t i ) -1 -R(t, t i ) and the last inequality is a consequence of Lemma 1. Also, with choice c = a min ij Γ ij , and for any matrix S ∈ R n×n that satisfies ||S|| ≤ c, we have |S| ≤ aΓ. Specializing the preceding observation to the case where S = Ω(tt i ) -1 -R(t, t i ), it follows from Lemma A.1 in the appendix below (applied with M 0 = Ω(t -t i ) and N 0 being the quantity in squared brackets in (47)) and ( 43)-(44) give

M -1 0 -(M 0 + N 0 ) -1 = Ω(t -t i ) -1 -R(t, t i ) ≤ ||Ω -1 || [0,ν] c0 1-c0 ≤ a min{Γ ij : 1 ≤ i ≤ n, 1 ≤ j ≤ n}, (52)
and so also Second part. We study the stability of (a")-(d"). We have

|M -1 0 -(M 0 + N 0 ) -1 | ≤ aΓ,
ẋ(t) = (H + A δ (t) + -A δ (t) -)x(t) + BKµ(t) |µ(t)| ≤ (1 + a)Γ|x(t)|, (53)
where µ(t) = x(t i ) -x(t). We introduce the interval observer        ẋ(t) = (H + A δ (t) + )x(t) -A δ (t) -x(t) + (BKµ(t)) + ẋ(t) = (H + A δ (t) + )x(t) -A δ (t) -x(t) -(BKµ(t)) -.

(54)

Then when the initial conditions are such that x(0) < x(0) < x(0), x(0) < 0 < x(0), the inequalities x(t) < x(t) < x(t), x(t) < 0 < x(t), and |x(t)| ≤ s(t) hold for all t ≥ 0, where s(t) = x(t)-x(t), by the corresponding argument from the second part of the proof of Theorem 2.

Then (54) gives ṡ(t) = (H +|A δ (t)|)s(t)+|BKµ(t)|. From the inequality in (53), we deduce that there is a function F such that 0 ≤ F(t) ≤ (1 + a)|BK|Γ and ṡ(t) = (H + |A δ (t)| + F(t))s(t) for all t ≥ 0. Since s(t) is nonnegative and H + |A δ (t)| + F(t) is Metzler for all t ≥ 0, we deduce from Assumption 3 and the comparison principle that s(t) converges exponentially to the origin as t → +∞, so since |x(t)| ≤ s(t) for all t ≥ 0, and since we can assume as before that s(0) ≤ 4|x(0)|, we conclude that x(t) converges exponentially to the origin as t → +∞ as well.

IV. ILLUSTRATION

In this section, we illustrate Theorem 1. Consider the benchmark system ẋ1 (t) = x 1 (t) + 1 2 x 2 (t) + u ẋ2 (t) = where x 1 and x 2 are valued in R and u is the input. Then, using the notation K = [K 1 K 2 ], Assumption 1 will be satisfied if

H = 1 + K 1 1 2 + K 2 3 2 + K 1 K 2 (56)
is Hurwitz and Metzler. Since H will be Hurwitz and Metzler if K 1 + K 2 < -3/2, K 1 ≥ -3/2, and K 2 ≥ -1/2, it follows that Assumption 1 is satisfied using K 1 = -4/3 and K 2 = -1/3. Then, with the notation of Section III, we have

3 2 x 1 (

 1

  calculations show that the assumptions of Lemma 1 and Theorem 1 are satisfied with all entries of Γ = [Γ ij ] being Γ ij = 0.045 and the lower bound ν = 0.122 on the sampling intervals t i+1 -t i .

  by writing the quantity inside the inverse in (49) as M 0 + N 0 and then noting that ||M -1 0 ||||N 0 || < c 0 . Hence, by (51), the inequality |x(t) -x(t i )| ≤ (1 + a)Γ|x(t)| holds, which gives t i+1 ≥ t i + ν.

We next compare the preceding lower bound with one that can be obtained from [6, p.72, Theorem 5.2] using the small gain approach. Recall that in the linear time invariant case, the triggering times in [START_REF] Jiang | Small-gain theory for stability and control of dynamical networks: A survey[END_REF]Theorem 5.2] are such that when t i+1 is finite, it is the smallest time t ≥ t i such that ρ(||x(t)||) = ||x(t) -x(t i )||, for any class K function ρ such that ρ(γ(s)) < s for all s > 0, where γ ∈ K ∞ is the overshoot function in a suitable input-to-state stability estimate for

i.e., there is a class KL function β such that along all solutions of (58) for all t ≥ 0, we have ||x(t)|| ≤ max{β(||x(0)||, t), γ(||w|| ∞ )}; see [START_REF] Jiang | Small-gain theory for stability and control of dynamical networks: A survey[END_REF] for the standard definitions of input-to-state stability and the classes K, K ∞ , and KL of comparison functions. In the linear case, we can apply variation of parameters to (58) to show that the least conservative choice of γ that satisfies the preceding requirements is

Hence, the least conservative choice of ρ is ρ(s) = s 2 M , which implies that when t i+1 is finite, it is the supremum of the times t > t i such that

by [START_REF] Mazenc | Interval observers for linear timeinvariant systems with disturbances[END_REF]. Hence, the lower bound on the inter-sample times t i+1 -t i guaranteed in this case is the largest q such that

which we computed to be q = 0.0838, using Mathematica. Since this is significantly below the lower bound ν = 0.122 we obtained using our positive systems approach, this illustrates a potential advantage of our positive systems approach, namely, the ability of our method to ensure less frequent event-triggering times and therefore less frequent control recomputations. Remark 4: Even in scalar cases, our approach from our Theorem 1 offers potential advantages over [START_REF] Jiang | Small-gain theory for stability and control of dynamical networks: A survey[END_REF], in terms of ensuring a larger lower bound ν on the intersample times sup{t i+1 -t i } as compared with [START_REF] Jiang | Small-gain theory for stability and control of dynamical networks: A survey[END_REF]. For instance, consider the scalar case with A = B = 1, K = -2, H = -1, and Γ = 1 2 0.9999. Then, if we apply the same reasoning as we did in the preceding two-dimensional case, simple Mathematica calculations show that our requirements from Theorem 1 are satisfied using ν = 0.2875. On the other hand, the largest ν value for which the requirements from [6, p.72, Theorem 5.2] would be satisfied in this scalar case is 0.1823. This again illustrates the considerable improvement that is made possible by our Theorem 1.

V. CONCLUSION

We proposed a new triggered control design, where instead of small gain or other standard approaches, we used positive systems and interval observers. This allowed us to cover large classes of linear time invariant systems with outputs, and cases where there can be timevarying uncertainty in the coefficients of the systems. Our example illustrated how our method can lead to less conservative lower bounds on the inter-sampling times, compared with small gain approaches, and therefore ensure less frequent sampling. In our future work, We aim to extend our work to cover linear time-varying systems, whose coefficients can be expressed as sums of constant matrices and small enough time-varying parts. We aim to further extend our work to nonlinear systems. APPENDIX: LEMMAS FROM [START_REF] Mazenc | Finite time estimation through a continuous-discrete observer[END_REF] We used the following lemmas (which are Lemmas 1-2 from [START_REF] Mazenc | Finite time estimation through a continuous-discrete observer[END_REF], respectively) in our proof of Theorem 3 above:

Lemma A.1: Let M 0 ∈ R n×n be an invertible matrix. Let N 0 ∈ R n×n be a matrix. Let n and m be two constants such that ||M

Then the matrix M 0 + N 0 is invertible and


Chahan Vidal-Gorène
email: chahan.vidal-gorene@chartes.psl.eu

Noëmie Lucas
email: noemie.lucas@ehess.fr

Clément Salah
email: salah.clement@gmail.com

Aliénor Decours-Perez

Boris Dupin

RASAM -A Dataset for the Recognition and Analysis of Scripts in Arabic Maghrebi ⋆

Keywords: Arabic Maghrebi scripts, Dataset, Manuscripts, Layout Analysis, HTR, Crowdsourcing

The Arabic scripts raise numerous issues in text recognition and layout analysis. To overcome these, several datasets and methods have been proposed in recent years. Although the latter are focused on common scripts and layout, many Arabic writings and written traditions remain under-resourced. We therefore propose a new dataset comprising 300 images representative of the handwritten production of the Arabic Maghrebi scripts. This dataset is the achievement of a collaborative work undertaken in the first quarter of 2021, and it offers several levels of annotation and transcription. The article intends to shed light on the specificities of these writing and manuscripts, as well as highlight the challenges of the recognition. The collaborative tools used for the creation of the dataset are assessed and the dataset itself is evaluated with state of the art methods in layout analysis. The word-based text recognition method used and experimented on for these writings achieves CER of 4.8% on average. The pipeline described constitutes an experience feedback for the quick creation of data and the training of effective HTR systems for Arabic scripts and non-Latin scripts in general.

Introduction

The automatic analysis of handwritten documents has become a classic preliminary step for numerous digital humanities projects that benefit from the mass digitization policy of heritage institutions. Following the competitions organized in recent years, at ICFHR and ICDAR notably, several robust architectures for layout analysis of historical documents have been developed [START_REF] Diem | cBAD: ICDAR2019 Competition on Baseline Detection[END_REF], whose application to non-Latin script documents provide equivalent results [START_REF] Kiessling | BADAM: A Public Dataset for Baseline Detection in Arabic-Script Manuscripts[END_REF][START_REF] Vidal-Gorène | A Modular and Automated Annotation Platform for Handwritings: Evaluation on Under-resourced Languages[END_REF]. The HTR architectures specialized on a type of document or on a hand also achieve a very high recognition score, even though the literature is mostly Latin script based, as well as the proven pipelines composed of character-level HTR and post-processing [START_REF] Clérice | Evaluating Deep Learning Methods for Word Segmentation of Scripta Continua Texts in Old French and Latin[END_REF]. The non-Latin, cursive and RTL writings, like the Arabic scripts, remain an open problem in digital humanities with a wide variety of approaches [START_REF] Milo | A New Strategy for Arabic OCR: Archigraphemes, Letter Blocks, Script Grammar, and shape synthesis[END_REF]. Although specialized databases have emerged in recent years (see infra 2.1), they are often focused on the layout [START_REF] Kiessling | BADAM: A Public Dataset for Baseline Detection in Arabic-Script Manuscripts[END_REF][START_REF] Clausner | ICFHR 2018 Competition on Recognition of Historical Arabic Scientific Manuscripts -RASM2018[END_REF] and on common documents and writings, leaving out numerous under-resourced written traditions.

We are presenting a new dataset for the analysis and the recognition of handwritten Arabic documents, the first dataset focused on the writings called "Maghrebi scripts", also known as "Western scripts", or "round scripts". This term encompasses a variety of styles that have common characteristics and are poorly represented in digital humanities. These scripts dating back to the 10th century have been widely used however in the Islamic West -al-Andalus and North-Africa -, as well as sub-Saharan Africa until the 20th century 6 . They have numerous specificities that differentiate them from the classical problems met for Arabic handwritten character recognition. The rounded shape of these scripts may be explained by the writing tool used, that is qalams made from large reed straws cut in half lengthwise, with a pointed nib and not a biseled one as in the Islamic East [START_REF] Ben Azzouza | Les corans de l'occident musulman médiéval : état des recherches et nouvelles perspectives[END_REF]. Therefore, the Maghrebi scripts constitute a family of rounded scripts that share a number of characteristics, first of all very rounded loops, that can be seen in the manuscripts in the present dataset (see infra 2.3). The main characteristics 7 of the scripts are displayed in table 1.

The dataset, resulting from a collaborative hackathon held from January to April 2021, intends to cover a large spectrum of the handwritten production in Maghrebi scripts. The choice for a multilevel annotation (semantic and baseline annotation, word-level and character-level transcription) aims to offer to the scientific community a comprehensive dataset dedicated to the creation and evaluation of complete HTR pipelines, from layout analysis to text recognition for this written tradition. After a short presentation of the related work for the datasets, we propose a complete description of the manuscripts, the annotations and the editorial choices made for the transcription. The creation of the dataset 6 The history and the origins of these scripts have been an important scientific open debate [START_REF] Bongianino | The Origins and Developments of Maghribī Rounds Scripts[END_REF][START_REF] Ben Azzouza | Les corans de l'occident musulman médiéval : état des recherches et nouvelles perspectives[END_REF]. The most recent works, in particular those of U. Bongianino, have foregrounded the different itineraries (from books to qurans, from al-Andalus to the Maghreb) followed by these writings between the 10th and the 13th century [START_REF] Bongianino | The Origins and Developments of Maghribī Rounds Scripts[END_REF]. 7 Characteristics are taken from U. Bongianino [START_REF] Bongianino | The Origins and Developments of Maghribī Rounds Scripts[END_REF]; theoretical realizations are taken from the article of N. Van de Boogert upon which U. Bongianino draws [START_REF] Van Den Boogert | Some notes on maghribi script[END_REF].

has also benefited from a collaborative and semi-automatic work, with architectures dedicated to non-Latin scripts, that we assess with the view to replicate for other under-resourced languages.

hā' tā' marbūṭa

Isolated position: drawn in the shape of a '6', sometimes inverted

Dataset and Arabic Maghrebi manuscripts of the BULAC

Existing resources for Arabic scripts

Following the competitions organized in recent years, at ICFHR and ICDAR, several datasets for Arabic written documents analysis have emerged. Such is the case of RASM2018 [START_REF] Clausner | ICFHR 2018 Competition on Recognition of Historical Arabic Scientific Manuscripts -RASM2018[END_REF], focused on the Arabic scientific manuscripts on Qatar Digital Library, which is used to evaluate the layout analysis of documents in Arabic scripts. The 100 images of the dataset are annotated at different levels: region, polygons, lines and text. The Arabic scripts, however, present unique challenges for text-region detection and baseline detection. Therefore, in order to include these specificities, RASM2018 has been considerably expanded by BADAM [START_REF] Kiessling | BADAM: A Public Dataset for Baseline Detection in Arabic-Script Manuscripts[END_REF] with a dataset focused on the Arabic scripts, comprising 400 images annotated at the text-region and baseline level.

These datasets cover a wide-ranging production of texts in non-Maghrebi Arabic scripts to enable the training of dedicated models [START_REF] Kiessling | BADAM: A Public Dataset for Baseline Detection in Arabic-Script Manuscripts[END_REF]. More generally, there are other smaller or more specialized datasets, like HADARA80P [START_REF] Pantke | An Historical Handwritten Arabic Dataset for Segmentation-Free Word Spotting -HADARA80P[END_REF] and VMH-HD [START_REF] Kassis | VML-HD: The historical Arabic documents dataset for recognition systems[END_REF], annotated at the region and word level, like KERTAS [START_REF] Adam | KERTAS: dataset for automatic dating of ancient Arabic manuscripts[END_REF], dedicated to manuscripts datation, or like WAHD [START_REF] Abdelhaleem | WAHD: A database for writer identification of Arabic historical documents[END_REF], dedicated to writer identification. Aside from the targeted tasks and the languages concerned, these datasets shed light on the variety of existing perspectives for handwriting, either inspired by the Latin languages, or by word-based approach. A FCN followed by a postprocessing for baseline extraction gives robust results even on the most complex layouts [START_REF] Kiessling | BADAM: A Public Dataset for Baseline Detection in Arabic-Script Manuscripts[END_REF][START_REF] Vidal-Gorène | A Modular and Automated Annotation Platform for Handwritings: Evaluation on Under-resourced Languages[END_REF]. Manuscripts in Arabic Maghrebi scripts are largely excluded from the datasets.

Dataset composition

RASAM is available under an open license 8 . It comprises 300 annotated images extracted from three manuscripts selected among the collections of the Bibliothèque Universitaires des LAngues et Civilisations (BULAC) 9 . The images of the dataset are in JPEG format and have varying resolutions from 96 DPI to 400 DPI. Experiments are carried out on the hackathon results (v1.0, 297 images). Dataset has been expanded in June 2021 (v1.1, 300 images, includes minor corrections).

Thus, two manuscripts of the dataset have been chosen among the 150 Arabic manuscripts available online (MS.ARA.1977 and MS.ARA.609); the third and last manuscript (MS.ARA.417) of the corpus has been digitalized at our request. The variety of topics, the representative type of the Maghrebi script, as well as the diversity of layouts has informed our choice of manuscripts to annotate and transcript for this dataset. The aim is to obtain polyvalent analysis models for this written tradition. Therefore, two manuscripts belong to the historical genre ('ilm al-tārīḫ), whereas the third has to do with inheritance law (fiqh al-farā'iḍ). The small number of manuscripts is justified by the necessity to quickly achieve HTR models. The pages are not sequential, and the pages have been randomly selected to cover all the variations of a same copyist and the different layouts within a single manuscript. MS. ARA. 417 : The manuscript 13 , dated from 1292/1875, was copied on the manuscript n°1061 of the National Library of Algeria. It narrates the history of Beys of Oran in the 13th century: the Tārīḫ Bāyāt Wahrān, written by Ḥasān Ḫūǧah, secretary of Ḥasān Bey (1817-1831). It distinguishes itself from the two previous manuscripts by its length and its layout: it consists of 48 folios with pages of 12 lines, each of them with less than 10 words per line. The manuscript, very well written, is in black ink, even though the copyist uses red ink sporadically (e.g. chapters headings or some separators). In the lateral margins, another hand, which looks identical to the note of cataloguing in the first page, has added the names of the beys in Arabic and some dates. The same hand seems to have added some vocalizations marks written on some folios and some corrections with a blue ink.

Ground-Truth Content and Creation

Each image is associated with a pageXML format file describing the entire ground truth and the associated metadata. The annotations have been realized automatically on Calfa Vision platform, then manually checked over the course of a collaborative hackathon.

The overall set of constitutive parts of a manuscript page is annotated. We offer for each image: (i) a semantic annotation of the regions, (ii) an annotation of baselines (polylines), (iii) a polygons framing every line associated to a baseline and (iv) the transcription. In figures, the dataset is comprised of 300 images, 676 text-regions, 7,540 lines and 483,725 characters (v1.1).

Structure description

Text-region : The layout analysis consisted in identifying all the text-regions. We have defined 5 classes: text (300), marginalia (171), catchword (102), table (53) and numbering (50). The classes are not uniformly distributed but constitute clearly identifiable items. To prevent an overwhelming variety and ambiguity of classes, the 5 defined classes can incorporate some regions that would be otherwise traditionally separated. Thus, the titles, often written in color, are not separated but included in the text class. Likewise, all content in the margins (everything outside from the main text-region) is encompassed in the class marginalia, with the exception of the catchwords. Table and numbering respectively refer to the tables located inside and outside the main text-region and to all fractions within the text (see figure 2).

Fig. 2. Semantic classification of text-regions and baselines

Baseline : We adopted the annotation by baseline, suited for the Arabic scripts and interoperable with other datasets of the state of the art. Each segment of a sentence has its own baseline. In the event of overlap, as displayed by figure 2 for the marginal note, there is no continuity in the baseline. Besides, the outline of the latter follows the text line actually present in the manuscript and not a theoretical line that would link two segments of a single sentence (for instance, in the case of a line break for versification or due to a table -see figure 2). The reading order can be managed afterwards in post-processing. The manuscripts present numerous curved lines (see figure 2), in particular at the end of sentences and in the marginal notes. In this case, the baseline follows the same scheme that for BADAM [START_REF] Kiessling | BADAM: A Public Dataset for Baseline Detection in Arabic-Script Manuscripts[END_REF], following a theoretical rotation point to match with the line curvature. Markers of verses or other signs for aesthetic purposes have not been taken into consideration (see figure 3, no 3). Lastly, in the event of characters composed of strokes expanding beyond the body of the character (e.g. the letter nūn in figure 3, no 1) and located at the end of a sentence, the baseline has been extended to cover the entire shape of the character, even in the absence of the theoretic writing line.

Polygons : Each line of text is extracted with a surrounding polygon, drawn with an adaptive seamcarve implemented on the annotation platform [START_REF] Vidal-Gorène | A Modular and Automated Annotation Platform for Handwritings: Evaluation on Under-resourced Languages[END_REF]. Polygons have been manually proofread to integrate all the constitutive strokes of a given character, including ascenders and descenders, as well as the associated diacritics (see figure 3, no 4). There remain overlaps between the polygons of lines (see figure 3, no 2), but the HTR results have demonstrated that these overlaps have very few impact on HTR predictions (see infra 4.2).

Specifications for transcription

A common framework for the text input was defined to preserve the uniformity of the transcriptions of each participant. The aim is to achieve a HTR producing predictions as close as possible to the original text, and thus to offer a complete transcription and allow for a big panel of editorial choices. The dataset comprises 54 classes, whose detail we give in table 2. We have notably realized transcriptions that restore the spaces in Arabic, even when there are visually no discernable spaces in the manuscript. In view of the great variety of character morphologies in the Maghrebi manuscripts scripts, we favored the word-based approach instead of the character-based approach where the word separation is managed in post-processing [START_REF] Camps | Handling Heavily Abbreviated Manuscripts: HTR engines vs text normalisation approaches[END_REF]. where the copist should have written ṭā' marbūṭa in final position

haḏā/haḏihi

In case of an erased character Although we can guess that it may be: , the transcription was addressing what can be actually identified, here:

In order to remain as close as possible to the text, the transcription follows the spellings habits of the copyist, even when they depart from the norm of standard Arabic. Hence, the frequent confusion, in particular in the MS.ARA.609, between ḍād and ẓā, and between ṣād and ṭā' have been retained. For instance, for the transcription of ṭā', that could be spelled as tā' marbūṭa, or the other way around, the misspell was kept. Furthermore, the demonstratives hāḏā, hāḏihi, and in some instances ḏālika, that are spelled in modern Arabic with a defective form or with a dagger alif, are often spelled with their archaic form with a medial alif : we maintain in our transcriptions the spelling of this alif (see table 3). The punctuation, when present, has not been transcribed. In the event of vocalization signs or šadda ( ), the participants were free to transcribe or not, the priority was on the characters and words. When not understood, the char-acter was to be replaced by the sign #. When impossible to read because of an alteration of the manuscript, nothing was to be transcribed (see table 3).

Two particular cases caught the attention of the transcribers and were much debated: the hamza ( ) and its different forms and the diacritic signs of the yā'. The main rule adopted for the hamza was the following: if there is no hamza do not add one and transcribe the hamza as it is written in other cases (see table 4).

However, in the MS.ARA.609 and in the MS.ARA.417, the copyists used a singular hamza shape but consistent. In the MS.ARA.609, the hamza was written as a full sukūn. In these cases, we have considered that it was the way the copyist realized the letter (see table 5). In the cases where the hamza was written below the line, with or without the diacritics of the , the hamza was drawn on alif maqṣūra. The issue of transcription of the was raised for the MS.ARA.1977 manuscript in particular, in which the copyist only wrote diacritics in rare instances. It was decided not to correct and to transcribe as close as possible to the text with only three exceptions: for the preposition and the relative pronouns which, in the Maghrebi script, sometimes form some kind of glyphs (see table 6).

Evaluation of the crowdsourcing campaign and HTR models

The annotations have been realized with the Calfa Vision platform14 [START_REF] Vidal-Gorène | A Modular and Automated Annotation Platform for Handwritings: Evaluation on Under-resourced Languages[END_REF], which incorporates -besides the online collaborative work on an image in real timemodels for layout analysis and HTR prediction. These models are automatically assessed and fine-tuned, according to the corrections given by the contributor to the project, in order to speed up the checking task for the next images.

General considerations and implementation protocol

The crowdsourcing campaign gathered 14 participants from January to April 2021, divided into three projects. The contributors were paired: one annotated and the other checked. Three main tasks were set to annotate each image.

1. Annotation and check of the layout analysis. A text-region (polygon) and a baseline (polyline) detection is automatically carried out beforehand. A first team is entrusted with the verification of the predictions and when necessary with the correction of the polygons and polylines shapes. The specifications to follow are defined in part 3.1. 2. Transcription of the text. Once the layout verified, the page is manually transcribed according to the specifications described in part 3.2. Some preannotations are realized in a second phase, once the HTR models are sufficiently precise (see table 9). 3. Extraction of the lines with a surrounding polygon for each transcribed line.

After each task, the images are re-assigned, to enable cross-check and to smooth the annotation habits. When all three tasks are completed, a comprehensive verification is carried out by a team of administrators.

Benefits of fine-tuning and transfer learning for a under-resourced language

The layout analysis models, provided by Calfa Vision for a project of handwritten documents annotation, are trained with an extensive dataset of various handwritten documents both medievals and recents [START_REF] Vidal-Gorène | A Modular and Automated Annotation Platform for Handwritings: Evaluation on Under-resourced Languages[END_REF]. A first assessment has been realized on BADAM with 0.9132% precision and 0.8575% recall [START_REF] Vidal-Gorène | A Modular and Automated Annotation Platform for Handwritings: Evaluation on Under-resourced Languages[END_REF].

Layout analysis and baseline models : After each proofreading of predictions, models are evaluated. The automatic re-training has been processed with a batch of 50 verified images from the three manuscripts. Evaluation is carried out on the remaining images to annotate. The batch of 50 was compiled to encompass a wide range of assessed layouts. We use the metric of the cBAD competition [START_REF] Diem | cBAD: ICDAR2019 Competition on Baseline Detection[END_REF] and implemented on Calfa Vision [START_REF] Vidal-Gorène | A Modular and Automated Annotation Platform for Handwritings: Evaluation on Under-resourced Languages[END_REF]. From the first fine-tuning, we notice a significant increase in the model ability to correctly predict baselines on the dataset images. We also notice a steady improvement for the precision and the F1-score. The already high recall has little variation throughout the fine-tuning, with a slight dip when the batch is predominantly comprised of very curved lines. The results displayed in table 7 constitute a baseline for the HTR ability to identify the lines of text in common Arabic Maghrebi scripts manuscripts. The very high score achieved by the first model demonstrates a strong ability to rapidly reach quality fine-tuning for a under-resourced language (see figure 4).

At the region level, we evaluate the relevance with an Intersection over Union (IoU) metric. The default model is already convincing to identify the area of the main text, but without distinction between the main text, catchwords and the marginal notes. The fine-tuning triggers mechanically a decrease in the score of main text identification, but also the rapid inclusion of the other classes (see figure 4).

Concerning the text-regions, the latest model achieves an accuracy of 0,8534% on average. The margins and the catchwords are sometimes very close to the main text 1 which makes it difficult to distinguish from the main text. As for the tables and numbering, their very low distribution and unequal division in batches result in lower scores. The relevance of the numbering class may also be questioned based on the outcomes15 . We achieve similar result with the creation from scratch of a model with the whole dataset. We nevertheless notice a quick integration of the new text-regions in the models (see figure 4).

At the polygon of lines level, with the same metric, we measure a global relevance of 94%, no matter the curve of the line. The main difficulty encountered concerns the diacritics, which sometimes are not encompassed by the polygon and must be manually corrected. An adjustment of the seam carve has occurred as soon as the batch 20 to better manage the line height. The polygons verification constitutes nevertheless the most time-consuming task. For the first proofreading task of layout, baseline and polygon predictions, the time saved amounts to 75%. On average, the full process (predictions and proofreading) takes 7 min. for an image with the default model, bringing down to 4 min. for an image from the first model. The time required is down to 3.2 min. for the model 3, then to 2.5 min. for the last model. At this point, the proofreading can be confined to the curved lines of the marginal notes. Results are summarized on figure 4. HTR models : Two types of models have been created and evaluated with the default architecture proposed by Calfa Vision. The first are HTR models specific to a project, thus specialized on a manuscript to accompany the transcription. Here, we have chosen batches of 20 corrected images. (i) Models dedicated to a project : Each manuscript has its own difficulties and a specific number of lines (see supra 2.3). We have measured the learning ability of HTR models on each manuscript to go along with the transcription (see table 9). The models are trained incrementally as new transcriptions are checked and evaluated on the following folios of the project. The MS.ARA.609 and MS.ARA.417 have fewer text lines, thus the CER stays high until the batch 4 16 . However, we observe a significant gain in the 16 With better polygons (dataset v1.1), the CER decreases more quickly (16.6 for batch 1, then 15.87, 13.67, 11.52, and finally 6.67 for the last batch).

annotation upon application of the first model, with an average transcription time cut from 49 min. for an unassisted transcription, to 29 min. as of the first batch and 21 min. for the last model: hence an average gain of 42% (see figure 4). In detail, the gain is 56% for ARA.1977 (with extrema of 1H15 unassisted and 20 min. with a model) and 45% for ARA.609 (with extrema of 45 min. unassisted and 13 min. with a model). Word separation, HTR classical issue, is accurate at 80,4% for each specialized model. Most character-level prediction errors seem to be more about the characters in the initial or final position in the word. Among the most frequent errors, the final nūn can be confused with the rā' or the zāy, as well as the dāl and the rā' or the ḍād and the ḫā'. Furthermore, we observe difficulties in identifying hyphenations between words, leading to misidentification of words. It should also be noted that when several characters with superscript or subscript diacritics follow each other (e.g. a sequence tā', nūn, šīn or a sequence bā', yā', fā'), the prediction of this sequence of letters is frequently incorrect and random, but adding more context with mixed models show a significant improvement of predictions in these cases (see figure 5). (ii) HTR models for Arabic Maghrebi scripts : We have also measured the relevance of transfer learning in-between manuscripts. Some transcription campaigns have in deed progressed more quickly than others and to re-purpose a specialized model for another manuscript is proving beneficial. Results of transfer learning are described in the figure 5. For each model, we have used 80% of data for training and 20% for testing. Four mixed models have been evaluated.

The confusion matrix highlights the big discrepancies between the three manuscripts, and no specialized model can achieve a CER below 20% on the other manuscripts. Manuscripts display a wide variety of text density, loop shapes and diacritics management that could affect transfer benefits. These limitations also lead to very different shapes of polygons. But in contrast, we observe a much higher convergence of mixed models. The MS.ARA.1977 and MS.ARA.417 manuscripts benefit more from this transfer than MS.ARA.609 which presents specific difficulties. CER of MS.ARA.417 is below 4% with mixed models. If we observe no real gain for CER on each manuscript, the transfer favors greater robustness for word separation with a gain of 8.54% on average, that is consistent with the word-based approach. Experiments also show an ability to correct manual transcriptions misprint. The complete model demonstrates great versatility for these scripts with an average CER of 4.8% Moreover, first experiments on v1.1 tend to indicate that a precise polygonization of lines, with all diacritics included, is necessary with few data (see footnote 16). At the word-level however, gain remains marginal with a larger dataset.

In practice, the editorial choice to manually transcribe the majority of the dataset was made to limit possible typos. For an annotation project, this annotation approach with mixed models is deemed effective and will be implemented in future work, transfer showing a good and fast specialization with a slight fine-tuning.

Conclusion

We are presenting a new dataset comprising 300 annotated pages of Arabic Maghrebi script manuscripts of the BULAC. The chosen manuscripts display various layouts, sometimes very complex, with diverse deteriorations. The selected scripts encompass a representative panel of the handwritten production in Maghrebi scripts, in order to foster the emergence of robust HTR systems for these writings. Our work takes part in the commitment of the French scientific community towards the studies of Maghreb and for the promotion of the Maghrebi archives and manuscripts. Though the norms of transcription may be subject to evolution, our evaluations attest already a good recognition of these scripts, with a CER of 4.8% for the three manuscripts on average. The Arabic scripts and Arabic Maghrebi scripts in particular raise several difficulties for their layout processing and their recognition. We demonstrate that a crowdsourcing approach incorporating automatic fine-tuning and transfer learning is a successful strategy for data creation for under-resourced languages. It achieves similar results to those of the state of the art for manuscripts in Latin scripts. Future work will focus on evaluating the versatility of this dataset and the HTR capabilities for Maghrebi Arabic scripts.

( i )

 i Isolated position: concave form -(ii) Final position: closing denticle in the shape of an inverted comma dāl ḏāl Isolated, median and final positions: concave downstroke and final downward spur (dāl kāfiyya) dāl ḏāl Final position: marked semicircular descender, resembling the letters rā' and zā' Oval or semi-circular body and lack of denticle 'ayn ġayn Initial position: oversized curl kāf Initial and median positions: semicircle topped by a diagonal stroke mīm Final and isolated positions: long curved tail in two variants (concave or convex)

2. 3 10 - 12 -

 31012 Selected manuscripts MS. ARA. 1977 : The manuscript MS.ARA.1977 10 consists in a compilation of 249 pages: the most part of which (p. 1-201) is a historical treatise entitled al-Ǧumān fī muḫtaṣar aḫbār al-zamān written by the Andalusian historian Abū 'Abd Allāh Muḥammad b. 'Alī b. Muḥammad al-Šuṭaybī (d. 963/1556), disciple of the great Maliki jurist Aḥmad Zarrūq (d. 899/1493). The second 38-page long text (p. 205-243) deals with the customs and practices relating to the prophet Muḥammad; as for the third text (p. 247-249), it is a recollection of the words of a scholar al-Ḥasan b. Mas'ūd al-Yūsī (d. 1102/1691), native from the North-West of the Moroccan Middle Atlas. It deals with the mission that the prophet Muḥammad would have entrusted to the Berber tribes to conquer the Maghreb. The annotation and transcription have been achieved on the first and main part of the compilation, that has been copied by Muḥammad b. Mubārak al-Barāšī around 1259/1843 11 . Compiled on paper (305 x 210 mm.), the manuscript pages contain 31 lines, with the exception of the last three which contain 27 each, and the pages 67-68, 202-204 and 245-246 that are left blank. While the main text is written in black ink, here and there the copyist has used red (e.g. limited to section titles) and green inks (e.g. to indicate poetry verses). This manuscript features a series of marginalia: besides the catchwords at the bottom of the page, numerous corrections and notes are displayed along the text. The characteristics of the ink and the handwriting lead us to assume that they are made by the copyist himself. The same can be assumed for the manuscript MS.ARA.609 (see infra). MS. ARA. 609 : The manuscript MS.ARA.609 12 consists in a treatise in verse on arithmetic, on inheritances and wills. Written by the Maliki jurist 'Abd al-Raḥmān al-Aḫḍarī (d. 953/1513 or 983-1575) around 946/1540, the poem and its commentary are about the science of successions ('ilm al-farā'iḍ) and the arithmetic knowledge it required. Abū Zayd 'Abd al-Raḥmān b. Muḥammad al-Aḫḍarī, one of the great names of the Maliki school of the 10th/16th century, was born in 919/1513 near Biskra. He is the author of numerous didactic poems, MS.ARA.1977, Collections patrimoniales numérisées de la BULAC. 11 Muḥammad b. Mubārak al-Barāšī is also the copyist of the second text. There is no mention for the third text: the paleographical characteristics of the pages lead us to assume that it is the work of another hand. MS.ARA.609, Collections patrimoniales numérisées de la BULAC. often along with their commentaries, in several scholarly fields of study (logic, arithmetic, rhetoric, law). Compiled on paper (210 x 175 mm.), the copy of the manuscript was completed in 1146/1734 by Abū l-Qāsim b. Muḥammad b. Abū l-Qāsim al-Duraydī. The manuscript has 202 pages -100 written folios, the folios 1 and 2 have been left blank -each page contains 25 lines. The main text is written in black ink, however the copyist has used red ink on several occasions (e.g. tables, numbers or poetry verses). This manuscript holds numerous numbers, fractions and tables throughout the text. The numbers are written in Indo-Arabic numerals. Like in the MS.ARA.1977, catchwords, additions, corrections and glosses are displayed on the lateral, top and bottom margins.

Fig. 1 .

 1 Fig. 1. MS.ARA.1977 (p. 42), MS.ARA.609 (p. 124) and MS.ARA.417 (f. 12v)

Fig. 3 .

 3 Fig. 3. Special cases for baselines and polygons annotation (MS.ARA.609 and MS.ARA.1977)

Fig. 4 .

 4 Fig. 4. Evolution of fine-tuning and effects on proofreading time for layout analysis and transcription (v1.0)

Fig. 5 .

 5 Fig. 5. Impact of transfer learning on CER (v1.0)

Table 1 .

 1 Some characteristics and realizations of Maghrebi scripts

	Letters	Characteristics	Theoretical realization	Examples from mss ARA.1977, ARA.609 and ARA.417
	bā'
	tā'
	ṯā'
	fā'

Table 2 .

 2 Letters distribution in RASAM dataset (v1.1)

	space 88,674	12,386	3,957	fatḥa	371	3	16
	66,996	12,064	3,880	sukūn	357	4	12
	48,324	9,508	3,500	šadda	344	6	10
	26,608	9,219	2,924		121	9	10
	25,606	8,818	2,675	#	100	5	9
	22,378	8,793	2,271		91	7	8
	22,105	6,658	2,096	fatḥat an	78	8	7
	19,213	6,522	1,696	kasra	44	0	3
	16,559	6,418	1,278	ḍamma	31	ḍammat an 2
	15,956	5,343	720	2	18		2
	13,970	4,312	648	1	16

Table 3 .

 3 Spelling conventions (examples from MS.ARA.609 and MS.ARA.1977)

Example

Confusion between ḍād and ẓā'

Table 4 .

 4 Some realizations of the hamza in MS.ARA.609 and MS.ARA.1977

-hamza in or is not present

Alif madda has been transcribed as it was done where we would have written When the hamza was not supported, we respected the way it was done and not

Table 5 .

 5 Specific realizations of the hamza in MS.ARA.609

Table 6 .

 6 Exceptions

regarding yā' and its diacritics MS.ARA.1977 MS.ARA.609 MS.ARA.417

Table 7 .

 7 Fine-tuning of Calfa Vision models for baseline prediction (v1.0)

	Model	Precision (%) Recall (%) F1-score (%)
	Default	0.8886	0.9522	0.9193
	Model 1 (Default + batch 1)	0.9627	0.9720	0.9673
	Model 2 (Model 1 + batch 2)	0.9650	0.9716	0.9683
	Model 3 (Model 2 + batch 3)	0.9680	0.9756	0.9718
	Model 4 (Model 3 + batch 4)	0.9762	0.9694	0.9728
	Model 5 (Model 4 + batch 5)	0.9769	0.9700	0.9734

  Table and numbering are not considered.

Table 8 .

 8 Fine-tuning of Calfa Vision models for text-region prediction (v1.0)

	average IoU (%)

Table 9 .

 9 Evolution of the CER for dedicated HTR models (v1.0)

	CER (%)

Table 10 .

 10 Example of predictions on MS.ARA.1977 and MS.ARA.609

	Pred
	GT
	Pred
	GT

https://github.com/calfa-co/rasam-dataset

The BULAC holds the second biggest fund of Arabic manuscripts in France (2.458 identified documentary units). BULAC collections contains a substantial proportion of the manuscripts copied in Maghrebi script. 150 Arabic manuscripts are available online on the website of the BINA Digital library.

https://vision.calfa.fr

Numbering class is not kept in the v1.1 of the dataset, for which we notice a 9% gain in average for identification of catchword and table classes.

⋆ This work was carried out with the financial support of the French Ministry of Higher Education, Research and Innovation. It is in line with the scientific focus on digital humanities defined by the Research Consortium Middle-East and Muslim Worlds (GIS MOMM). We would also like to thank all the transcribers and people who took part in the hackathon and ensured its successful completion.