Evangelos Bampas
email: evangelos.bampas@labri.fr

Jurek Czyzowicz
email: jurek.czyzowicz@uqo.ca

David Ilcinkas
email: david.ilcinkas@labri.fr

Ralf Klasing
email: ralf.klasing@labri.fr

Beachcombing on Strips and Islands

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

ℓ t A (ℓ) , where tA(ℓ) denotes the time when the search of the segment [0, ℓ] is completed under A. We consider a discrete and a continuous version of the problem, depending on whether the infimum is taken over ℓ ∈ N * or ℓ ≥ 1. We prove that the LeapFrog algorithm, which was proposed in [Czyzowicz et al., SIROCCO 2014, LNCS 8576, pp. 23-36 (2014)], is in fact optimal in the discrete case. This settles in the affirmative a conjecture from that paper. We also show how to extend this result to the more general continuous online setting. For the offline version of the Beachcombers' Problem, we consider the single-source Beachcombers' Problem on the cycle, as well as the multisource Beachcombers' Problem on the cycle and on the finite segment. For the single-source Beachcombers' Problem on the cycle, we show that the structure of the optimal solutions is identical to the structure of the optimal solutions to the two-source Beachcombers' Problem on a finite segment. In consequence, by using results from [Czyzowicz et al., ALGOSENSORS 2014, LNCS 8847, pp. 3-21 (2014)], we prove that the single-source Beachcombers' Problem on the cycle is NP-hard, and we derive approximation algorithms for the problem. For the multi-source variant of the Beachcombers' Problem on the cycle and on the finite segment, we obtain efficient approximation algorithms.

⋆ Part of this work was done while Jurek Czyzowicz was visiting the LaBRI as a guest professor of the University of Bordeaux. This work was partially funded by the ANR project DISPLEXITY (ANR-11-BS02-014). This study has been carried out in the frame of "the Investments for the future" Programme IdEx Bordeaux -CPU (ANR-10-IDEX-03-02).

One important contribution of our work is that, in all variants of the offline Beachcombers' Problem that we discuss, we allow the robots to change direction of movement and search points of the domain on both sides of their respective starting positions. This represents a significant generalization compared to the model considered in [Czyzowicz et al., ALGOSENSORS 2014, LNCS 8847, pp. 3-21 (2014)], in which each robot had a fixed direction of movement that was specified as part of the solution to the problem. We manage to prove that changes of direction do not help the robots achieve optimality.

Introduction

A group of n mobile robots have to explore collectively a given one-dimensional domain. The robots may be initially collocated or dispersed in the domain. At every moment of time, a robot can be either in walking mode or in searching mode. A robot in walking mode traverses the domain with a speed not exceeding its maximal walking speed. A robot in searching state can travel using at most its maximal searching speed, which is strictly smaller than its walking speed, reflecting the fact that a searching activity is more time-consuming. Different robots may have distinct maximal walking and searching speeds. A robot can change mode, speed, and direction of movement instantaneously. There is no communication between the robots during the execution of the algorithm. In the Beachcombers' Problem, the goal is to design a schedule for the movement of all robots so that the domain is searched as fast as possible. A domain is said to be searched under a given schedule, if every point of the domain is visited by at least one robot in searching mode. As pointed out in [START_REF] Czyzowicz | The beachcombers' problem: Walking and searching with mobile robots[END_REF], where the Beachcombers' Problem was introduced, there are numerous examples in quite diverse domains in which exploration using two-speed robots arises as a natural model for the underlying processes. For example, foraging or harvesting a field may take longer than inadvertent walking. In computer science, web page indexing or code inspection require a more involved investigation. A common feature of these examples is that the activity of searching, or other action to be performed on the territory, takes more time than casual territory traversal. The analogy to beachcombers has been introduced in [START_REF] Czyzowicz | The beachcombers' problem: Walking and searching with mobile robots[END_REF] to bring out that, e.g., a beachcomber looking for things of value performs a meticulous search of the beach, which takes significantly more time than simply walking from one point of the beach to another. Further motivation for the two-speed model can be found in [START_REF] Czyzowicz | The beachcombers' problem: Walking and searching with mobile robots[END_REF][START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF].

Preliminaries and notation. We consider searching schedules using two-speed robots in the following one-dimensional geometric domains: the cycle of a known circumference L, the finite straight line segment of a known length L, and on the semi-infinite line [0; +∞). The efficiency of the search in the first two cases is expressed in terms of the time t f when the search of the cycle is completed or, equivalently, the speed L/t f of the process. However, in the latter case, the schedule efficiency is better expressed by the speed of the search, represented by inf ℓ ℓ tA(ℓ) where t A (ℓ) denotes the time when the search of the segment [0; ℓ] is completed. In the discrete version of the problem, the infimum inf ℓ ℓ tA(ℓ) is over ℓ ∈ N * . On the other hand, in the continuous setting, the infimum inf ℓ ℓ tA(ℓ) is taken over ℓ ≥ 1.

A schedule for the robots is defined by a strictly increasing sequence of times t 0 , t 1 , • • • , as well as, for every robot i and every interval [t j , t j+1 ], for j ≥ 0, a mode (walking or searching), a speed (respecting the maximum speed of the chosen mode), and a direction of movement. A schedule is correct if, for every point p of the domain, there exists a time moment at which p is visited by a robot in searching mode. For any fixed robot i, we refer to the individual schedule of robot i as the trajectory of robot i. Clearly, this sequence of intervals is finite in the offline case and infinite in the online setting.

Observe that while the model allows to use any speed not exceeding the maximal speed given for the robot's mode, we can restrict consideration only to using its maximal searching and walking speeds. Also notice that any searching schedule may be converted to another one, which has the property that all subsegments which were being searched have pairwise disjoint interiors. Therefore, when looking for the optimal searching schedule, it is sufficient to restrict consideration to schedules whose searched sub-segments may only intersect at their endpoints.

Previous work. The Beachcombers' Problem was introduced and studied in [START_REF] Czyzowicz | The beachcombers' problem: Walking and searching with mobile robots[END_REF]. An optimal (offline) algorithm was presented for the problem in which all robots are initially located on one endpoint of a finite segment of known length. Furthermore, a 2-competitive (online) algorithm was presented for the case where all robots are initally collocated on the origin of a semi-infinite line. In [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF], the Beachcombers' Problem was studied for the case of more than one starting positions on a finite segment of known length. For a fixed number t ≥ 2 of starting positions, the t-source Beachcombers' Problem on a finite segment asks to find t starting points on the segment, an assignment of the robots to the starting points, and a search schedule which concludes the search of the finite segment as quickly as possible. It was shown in [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF] that this problem is NP-hard for t = 2, even when all robots have the same walking speed, that the optimal solution can be computed efficiently when all robots have the same searching speed, and that there exist a deterministic approximation algorithm for t = 2 and a randomized approximation algorithm for general t.

Our contributions. In Section 2, we study the online Beachcombers' Problem on the semi-line [0; +∞). We prove that the LeapFrog algorithm, which was proposed in [START_REF] Czyzowicz | The beachcombers' problem: Walking and searching with mobile robots[END_REF], is in fact optimal in the discrete case. This settles in the affirmative a conjecture from [START_REF] Czyzowicz | The beachcombers' problem: Walking and searching with mobile robots[END_REF]. We also show how to extend this result to the more general continuous online setting.

As regards the offline Beachcombers' Problem, we consider in Section 3 the single-source Beachcombers' Problem on the cycle. We show that the structure of the optimal solutions to the single-source Beachcombers' Problem on a cycle is identical to the structure of the optimal solutions to the two-source Beachcombers' Problem on a finite segment, as defined in [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF]. This implies that the results from [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF] for the case of two distinct sources are carried over to the case of the cycle, yielding an NP-hardness result as well as the existence of efficient approximation algorithms for the problem. In particular, the NP-hardness of the single-source Beachcombers' Problem on the cycle seems at first somewhat surprising, in view of the existence of an efficient algorithm generating optimal schedules for the single-source problem on a finite segment.

Furthermore, in Section 4, we explain how to modify the arguments from Section 3 so as to obtain approximation algorithms for the multi-source variant of the Beachcombers' Problem on the cycle and on the finite segment. Our results for the cycle topology provide a partial answer to an open question posed in [START_REF] Czyzowicz | The beachcombers' problem: Walking and searching with mobile robots[END_REF] and [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF], concerning the study of the problem in different domain topologies.

One further important contribution of our work is that, in all variants of the offline Beachcombers' Problem that we discuss, we allow the robots to change direction of movement and search points of the domain on both sides of their respective starting positions. This represents a significant generalization compared to the model considered in [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF], in which each robot had a fixed direction of movement that was specified as part of the solution to the problem. On an intuitive level, allowing the robots to zigzag should not result in a faster schedule. However, no proof of this intuition had been found until now. We manage to prove that changes of direction do not help the robots achieve optimality.

Due to lack of space, proofs are omitted.

Related work. Searching and exploration have been studied in numerous papers considering graphs or geometric environments (e.g. [START_REF] Albers | Exploring unknown environments[END_REF][START_REF] Alpern | The theory of search games and rendezvous[END_REF][START_REF] Baeza-Yates | Searching in the plane[END_REF][START_REF] Beck | on the linear search problem[END_REF][START_REF] Bellman | An optimal search problem[END_REF][START_REF] Czyzowicz | Worst-case optimal exploration of terrains with obstacles[END_REF][START_REF] Deng | Exploring an unknown graph[END_REF][START_REF] Deng | How to learn an unknown environment (extended abstract)[END_REF][START_REF] Demaine | Online searching with turn cost[END_REF][START_REF] Fomin | An annotated bibliography on guaranteed graph searching[END_REF]). The performance of the searching or exploration is typically expressed by the trajectory length or the time used by the mobile agent. Many searching and exploration algorithms are studied in the online setting, i.e., the target position or sometimes other parameters of the environment are a priori unknown (cf. [START_REF] Albers | Online algorithms: a survey[END_REF][START_REF] Albers | Online algorithms -what is it worth to know the future?[END_REF][START_REF] Berman | On-line searching and navigation[END_REF][START_REF] Czyzowicz | Worst-case optimal exploration of terrains with obstacles[END_REF][START_REF] Demaine | Online searching with turn cost[END_REF][START_REF] Dereniowski | Fast collaborative graph exploration[END_REF][START_REF] Fleischer | Competitive online approximation of the optimal search ratio[END_REF]). Efficiency of such algorithms is typically measured by the competitive ratio, i.e., the ratio of the time spent by the online algorithm with respect to the time of the optimal offline algorithm.

Most of the papers studying searching and exploration concern single robots. Sets of collaborating mobile robots were studied, e.g., in [START_REF] Chalopin | Network exploration by silent and oblivious robots[END_REF][START_REF] Das | Map construction of unknown graphs by multiple agents[END_REF][START_REF] Fraigniaud | Collective tree exploration[END_REF][START_REF] Higashikawa | Online graph exploration algorithms for cycles and trees by multiple searchers[END_REF]. Tradeoffs between the number of robots and the time of exploration were derived in [START_REF] Dereniowski | Fast collaborative graph exploration[END_REF].

The majority of the research on mobile robots concerns robots having the same mobile speed. Robots with distinct speeds were considered in the context of sensor energy efficiency [START_REF] Wang | Optimizing sensor movement planning for energy efficiency[END_REF], for designing fast converging population protocols [START_REF] Beauquier | On utilizing speed in networks of mobile agents[END_REF], and for patrolling the boundary of an environment [START_REF] Czyzowicz | Boundary patrolling by mobile agents with distinct maximal speeds[END_REF][START_REF] Kawamura | Fence patrolling by mobile agents with distinct speeds[END_REF].

The Online Beachcombers' Problem on the Semi-Line

In this section, we consider two variants of the online beachcombers' problem on the semi-line. The first one corresponds to the online problem presented in [START_REF] Czyzowicz | The beachcombers' problem: Walking and searching with mobile robots[END_REF].

Definition 1 (Discrete Online Beachcombers' problem). Given n robots with walking speeds w i and searching speeds s i < w i , for 1 ≤ i ≤ n, initially collocated at the origin of a semi-line [0; +∞), the problem consists in finding a correct schedule for this semi-line. The discrete online speed of a schedule A is defined as inf ℓ∈N * ℓ tA(ℓ) , where t A (ℓ) denotes the time when the search of the segment [0; ℓ] is completed.

Definition 2 (Continuous Online Beachcombers' problem). Given n robots with walking speeds w i and searching speeds s i < w i , for 1 ≤ i ≤ n, initially collocated at the origin of a semi-line [0; +∞), the problem consists in finding a correct schedule for this semi-line. The continuous online speed of a schedule A is defined as inf ℓ≥1 ℓ tA(ℓ) , where t A (ℓ) denotes the time when the search of the segment [0; ℓ] is completed.

The idea of the LeapFrog algorithm is to make all sufficiently fast robots, forming the so-called swarm of the algorithm, meet at some regular intervals. For this purpose, each robot of the swarm is assigned a specific fraction of such regular interval that it has to search (the robot walks the rest of the interval). For each robot, the assigned searching subinterval is calculated as a function of the walking and searching speeds of all the robots participating in the swarm. The robots repeat the same behavior in each interval, always all of them meeting at its extremities. Although all robots are always used in the optimal offline algorithm presented in [START_REF] Czyzowicz | The beachcombers' problem: Walking and searching with mobile robots[END_REF], some robots whose walking speeds are too slow (informally, not larger than the average speed of the swarm) may not participate in the swarm and thus may be never used in the online LeapFrog algorithm.

The main purpose of this section is to prove the optimality of the Algorithm LeapFrog described in [START_REF] Czyzowicz | The beachcombers' problem: Walking and searching with mobile robots[END_REF]. Our first step toward this goal is to restrict ourselves to particular schedules, which are much simpler to analyze but are nevertheless at least as efficient (in terms of online speeds) as general ones. The following simple lemma holds both for the discrete and the continuous cases.

Lemma 1. For every correct schedule S, there exists a correct schedule S ′ whose both online speeds are not smaller than the respective ones of S, and such that every moving agent always moves in the initial direction at the full speed permitted by its current mode. Moreover, the interiors of the segments searched by the different robots do not overlap.

Let LF be the discrete online speed of Algorithm LeapFrog. Before proving that Algorithm LeapFrog is optimal in terms of discrete online speed, we prove the slightly weaker result that no correct schedule can have a continuous online speed larger than LF.

Lemma 2. The continuous online speed of any correct schedule is at most LF.

Theorem 1. The discrete online speed of any correct schedule is at most LF.

Concerning the continuous online speed metrics, it is possible to obtain a slightly more precise result than the one of Lemma 2. Lemma 3. If there are at least two robots and Algorithm LeapFrog uses all the robots, then any continuous online speed of any correct schedule is less than LF.

It turns out that simple variations of Algorithm LeapFrog can match the bounds given in Lemmas 2 and 3.

In Algorithm LeapFrog, all agents participating in the swarm are synchronized at every integer point, that is, they all arrive at the same time at every integer point. For any positive integer N , we denote by LeapFrog N the variant of LeapFrog for which the agents participating in the swarm synchronize every 1/N units of distance, instead of every unit as in the original Algorithm LeapFrog. It is easy to check that the continuous online speed of Algorithm LeapFrog N tends to LF as N tends toward infinity. The family of algorithms {LeapFrog N } N ∈N * is thus optimal in the case when there at least two robots and Algorithm LeapFrog uses all the robots (cf. Lemma 3).

If there is only one robot, then the only reasonable algorithm is the one in which the single robot always searches at its maximal speed. This algorithm is in fact Algorithm LeapFrog, and its continuous online speed is equal, in this special case, to its discrete online speed LF. Lemma 2 thus shows that Algorithm LeapFrog is optimal also in this case.

The remaining case is when there are at least two robots, but the swarm of Algorithm LeapFrog does not use all the robots. In this particular case, we consider the following adaptation LeapFrog ′ of Algorithm LeapFrog. Let r, with searching speed s, be some robot not participating in the swarm in Algorithm LeapFrog. In our adaptation LeapFrog ′ , this robot r searches the semi-line from its beginning at its maximum searching speed s during 1/LF time units before stopping forever. Let p be the point at which r stops. All the robots of the swarm walk at the walking speed of the slowest walker among them until reaching point p. (Note that this walking speed is larger than LF by construction of the swarm.) At this point, all swarm robots execute Algorithm LeapFrog N as if p was the origin of the semi-line, with N defined as follows. The integer N is chosen sufficiently large so that, at any time at least 1/LF, the swarm has always searched one segment of length 1/N ahead of the normal Algorithm LeapFrog N . One can prove that the continuous online speed of Algorithm LeapFrog ′ is equal to LF, which is optimal by Lemma 2.

Single-Source Beachcombers on the Cycle

The purpose of this section is to show that the structure of the optimal solutions to the offline Beachcombers' Problem on the cycle is identical to the structure of the optimal solutions to the two-source Beachcombers' Problem on a finite segment, as defined in [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF]. This implies that the results from [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF] for the case of two distinct sources are carried over to the case of the cycle, even if the agents are allowed to zigzag. The (offline) single-source Beachcombers' Problem on the cycle is defined as follows:

Definition 3 (BPC -Beachcombers' Problem on the Cycle). Consider a cycle C L of circumference L and n robots r 1 , r 2 , . . . , r n , initially placed at point 0 of the cycle, each robot r i having searching speed s i and walking speed w i , such that s i < w i . The Beachcombers' Problem consists in finding an efficient correct searching schedule A of C L . The speed S A of the solution to the Beachcombers' Problem equals S A = L/t f , where t f is the finishing time of A.

The (offline) t-source Beachcombers' Problem on the segment was defined in [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF] as follows:

Definition 4 (t-SBP -t-Source Beachcombers' Problem [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF]). Consider an interval I L = [0, L] and n robots r 1 , . . . , r n , each robot r i having searching speed s i and walking speed w i , such that s i < w i . The t-Source Beachcombers' Problem consists in finding an efficient correct searching schedule A of I L , in which the robots are divided into at most t groups with each group being initially placed on a particular point of the segment (the source) and having a fixed direction of movement. The speed S A of the solution to the Beachcombers' Problem equals S A = L/t f , where t f is the finishing time of A.

Note that the model of [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF] precludes by definition any change of direction of movement for the robots, since each group of robots has a fixed direction of movement which is specified as part of the solution to the t-SBP problem. On the other hand, in our model for BPC, no such restriction is imposed but we are able to prove that changing directions does not help the robots.

In the following propositions and lemmas, we will refer to schedules for BPC, unless it is explicitly stated otherwise. Proposition 1. For every correct schedule S, there exists a correct schedule S ′ whose completion time is not greater than that of S and which additionally satisfies the following properties:

1. Every pair of arcs searched by the robots under S ′ have disjoint interiors. 2. During every time interval of S ′ , every robot i is either stopped or it moves at the maximum speed w i or s i , according to its chosen mode during that interval.

In view of Proposition 1, we will assume in the following that the trajectory of each robot i is characterized by a sequence of arcs (A i,j ) 0≤j≤σi and, for each arc, a mode (searching or walking) and a direction (clockwise or counterclockwise), such that in each arc the robot is moving at the maximum allowed speed. Note that an arc A i,j may correspond to one or more consecutive time intervals of the schedule.

Lemma 4. For every correct schedule S, there exists a correct schedule S ′ whose completion time is not greater than that of S and in which the trajectory of every robot in S ′ satisfies the following:

-It either stops at the origin at time 0, or it searches a sequence of arcs in clockwise (resp. counterclockwise) direction, in order of increasing clockwise (resp. counterclockwise) distance from the origin, and then it either stops or it moves counterclockwise (resp. clockwise) to the origin and then searches a sequence of arcs in counterclockwise (resp. clockwise) direction, in order of increasing counterclockwise (resp. clockwise) distance from the origin. -In between arcs that the robot searches clockwise (resp. counterclockwise), it walks clockwise (resp. counterclockwise) straight from the end of the last searched arc to the beginning of the next one. -The robot stops at the moment when it searches a non-empty arc for the last time.

-Traversing the circle clockwise from the origin, we first encounter all the arcs that are searched by the robot in the clockwise direction and, subsequently, we encounter all the arcs that are searched by the robot in the counterclockwise direction.

Lemma 5. For every correct schedule S, there exists a correct schedule S ′ whose completion time is not greater than that of S and in which, while moving from the origin in a clockwise direction, one first encounters all the arcs that are searched by some robot moving in clockwise direction under S ′ , and then one encounters all the arcs searched by some robot moving in counterclockwise direction under S ′ .

We call a schedule that satisfies the properties guaranteed by Proposition 1, Lemma 4, and Lemma 5 normal : Definition 5 (Normal schedules). A schedule is called normal if every robot's trajectory is either empty (the robot stops at time 0), or it consists of one clockwise or counterclockwise leg, as defined below, or it consists of two legs in opposite directions, such that after the first leg the robot returns to the origin by walking at full speed backwards over the first leg.

A clockwise (resp. counterclockwise) leg is a part of a robot's trajectory that starts at the origin and consists of searching at full speed a sequence of arcs in order of increasing clockwise (resp. counterclockwise) distance from the origin. In between searched arcs, the robot walks at full speed in the clockwise (resp. counterclockwise) direction from the end of the last searched arc to the beginning of the next one.

In addition, a normal schedule satisfies the following properties:

1. Every pair of searched arcs (not necessarily by the same robot) have disjoint interiors. 2. For every robot, each of its legs corresponds to at most one loop around the circle and, if its trajectory has two legs, they do not overlap. 3. While moving from the origin in a clockwise direction, one first encounters all the searched arcs that belong to clockwise legs, and then one encounters all the searched arcs that belong to counterclockwise legs.

It follows from the proofs of Proposition 1, Lemma 4, and Lemma 5 that, for every correct schedule S that is not normal, there exists a correct normal schedule S ′ that has smaller or equal completion time. In other words, we can guarantee all of the properties ensured by Proposition 1, Lemma 4, and Lemma 5 simultaneously. In the following, we will assume normal schedules without loss of generality. In fact, a careful examination of the proofs reveals that, in all cases, the modification of S to S ′ strictly decreases the completion time of at least one robot. This is less obvious in Lemma 5, but it suffices to apply the modification described in the proof for a pair of arcs a, b, such that one of them is the last searched arc in some robot's clockwise leg or the last searched arc in some robot's counterclockwise leg. It is easy to check that if S does not satisfy the property in the statement of Lemma 5, then there exists at least one such pair of searched arcs. We thus have the following: Lemma 6. For every non-normal correct schedule S, there exists a normal correct schedule S ′ whose completion time is not greater than that of S and in which at least one robot requires strictly less time to complete its trajectory.

With every fixed normal schedule S, we associate the corresponding partition of the circle into pairwise interior-disjoint arcs, each of which is searched by a single robot that is moving in the same direction over a continuous time interval. In view of Lemma 4, we may assume that the origin is not in the interior of any of the arcs. Definition 6. Let S be a normal schedule. We denote by A + S (resp. A - S ) the set of searched arcs that belong to clockwise (resp. counterclockwise) legs of robots. For a, b ∈ A + S ∪ A - S , we write a ≺ b if a clockwise traversal starting from the origin encounters arc a before arc b.

For the purpose of stating the next lemma, given a normal schedule S with completion time T , we will denote by I(S) the inclusion-maximal set of searched arcs that satisfies the following property: Each arc in I(S) is searched by a robot that stops strictly earlier than T and I∈I(S) I is a continuous arc that contains the origin. We will denote by R(S) the number of distinct robots that search the arcs in I(S).

Lemma 7. Let S be a normal correct schedule with completion time T , such that there exists ǫ > 0 and at least one robot that stops at time T -ǫ. Then, there exists a normal correct schedule S ′ with completion time at most T and R(S ′ ) > R(S).

Repeated applications of Lemma 7 yield Corollary 1, from which Corollaries 2 and 3 follow immediately: Corollary 1. In every optimal and normal schedule, all robots terminate their trajectories simultaneously.

Corollary 2. Every optimal schedule is normal.

Corollary 3. In every optimal schedule, the trajectory of each robot contains at least one leg.

We are now ready to further restrict the structure of optimal schedules. We first show that each robot searches only one arc per leg (Lemma 8), then that there are no crossing robots (Lemma 9, cf. Definition 7), and then that each robot performs only one leg (Lemma 10). Lemma 8. In every optimal schedule, each leg of the trajectory of each robot contains exactly one searched arc.

Definition 7 (Crossing robots). Let S be a normal schedule. We say that a pair of robots i, j cross under S if robot i searches arcs a + i ∈ A + S and a - i ∈ A - S , robot j searches arcs a + j ∈ A + S and a - j ∈ A - S , and

a + i ≺ a + j ≺ a - i ≺ a - j .
Lemma 9. No optimal schedule contains a pair of crossing robots.

Lemma 10. In every optimal schedule, the trajectory of each robot contains exactly one leg.

Lemma 10 is the main technical tool for connecting the optimal schedules for BPC instances to the optimal schedules for 2-SBP instances.

Lemma 11. Let I be an instance of 2-SBP on an interval of length L and let J be an instance of BPC with the same set of robots on a circle of circumference L. The completion time of the optimal schedule is the same in both instances.

We obtain now, as immediate corollaries of Lemma 11 and the results in [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF], the NP-hardness of BPC, as well as the existence of deterministic and randomized approximation algorithms for BPC.

Theorem 2. BPC is NP-hard, even when all robots have the same walking speed. Theorem 3. BPC admits a 0.5568-approximation algorithm that runs in O(n log n) time.

Theorem 4. BPC instances in which all robots have the same search speed can be solved optimally in time O(n log n).

Theorem 5. BPC admits a randomized algorithm which achieves an expected approximation ratio of 3 4 , needs O(n) random bits, and runs in O(n log n) time.

Multi-Source Beachcombers on the Line and Cycle

We now leverage our techniques from the previous section to obtain results for the multi-source version of the beachcombers' problem on the line and on the cycle, while allowing changes of direction as in BPC (Definition 3). We define the problem t-SBPL z :

Definition 8 (t-SBPL z -t-Source Beachcombers' Problem on the Line with zigzags). Consider a line segment of length L and n robots r 1 , . . . , r n , each robot r i having searching speed s i and walking speed w i > s i . Find an efficient correct searching schedule A of the segment, in which the robots are divided into at most t groups with each group being initially placed on a particular point of the segment (the source). The speed S A of the solution equals S A = L/t f , where t f is the finishing time of A.

Similarly, we define t-SBPC z (t-Source Beachcombers' Problem on the Cycle with zigzags), where, instead of a segment of length L, the robots have to search a cycle of circumference L. Note that, in contrast to t-SBP (Definition 4), the robots are allowed to change direction of movement and, in particular, to search segments on both sides of their respective starting points.

By following the arguments for BPC from Section 3 and modifying the proofs as necessary, we can prove that, for a fixed choice of starting points and a fixed allocation of the robots to those starting points, the equivalents of Lemma 6 and Corollaries 1-3 hold for t-SBPL z as well, with the only difference that a normal schedule for t-SBPL z is defined as follows: Definition 9 (Normal schedules for t-SBPL z ). Given a fixed choice of t starting points and a fixed allocation of the robots to those starting points, a schedule for t-SBPL z is called normal if every robot's trajectory is either empty (the robot stops at time 0), or it consists of one leftward or rightward leg, as defined below, or it consists of two legs in opposite directions, such that after the first leg the robot returns to the origin by walking at full speed backwards over the first leg.

A rightward (resp. leftward) leg is a part of a robot's trajectory that starts at its assigned source and consists of searching at full speed a sequence of segments toward the right (resp. left) in order of increasing distance from the source. In between searched segments, the robot walks at full speed to the right (resp. left) from the end of the last searched arc to the beginning of the next one.

In addition, a normal schedule satisfies the following properties:

1. Every pair of searched segments (not necessarily by the same robot) have disjoint interiors. 2. The given segment of length L is partitioned into t regions, such that each region is associated with exactly one starting point, and the robots originating from the associated starting point are confined within that region.

Subsequently, we obtain the following lemma, which corresponds to Lemma 10.

Lemma 12. Given a fixed choice of t starting points and a fixed allocation of the robots to those starting points, in every optimal t-SBPL z schedule, the trajectory of each robot contains exactly one leg.

The following Lemma connects the optimal schedules for t-SBPL z instances to the optimal schedules for 2t-SBP instances.

Lemma 13. Let I be an instance of 2t-SBP on a segment of length L and let J be an instance of t-SBPL z with the same set of robots on a segment of length L. The completion time of the optimal schedule is the same in both instances.

We thus obtain, in view of the results for t-SBP [START_REF] Czyzowicz | The multi-source beachcombers' problem[END_REF], the following results for t-SBPL z : Theorem 6. t-SBPL z instances in which all robots have the same search speed can be solved optimally in time O(n log n). Finally, we prove that the optimal solution to a t-SBPC z instance with a given swarm on a cycle of circumference L shares its structure with the optimal solution to a t-SBPL z instance with the same swarm on a segment of length L. Indeed, the normal schedules for t-SBPC z are essentially the same as those for t-SBPL z , except that the region associated with each starting point is now an arc of the cycle.

Lemma 14. Given a fixed choice of t starting points and a fixed allocation of the robots to those starting points, in every optimal t-SBPC z schedule, the trajectory of each robot contains exactly one leg. Lemma 15. Let I be an instance of t-SBPL z on a segment of length L and let J be an instance of t-SBPC z with the same set of robots on a cycle of circumference L. The completion time of the optimal schedule is the same in both instances.

In view of Theorems 6 and 7, we obtain the following results for t-SBPC z : Theorem 8. t-SBPC z instances in which all robots have the same search speed can be solved optimally in time O(n log n). Theorem 9. t-SBPC z admits a randomized algorithm which achieves an expected approximation ratio of 1 -1 -1 2t 2t , needs O(n log t) random bits, and runs in O(n log n) time.

Concluding Remarks

There are several directions in which the study of the search and exploration using two-speed robots may continue. An obvious one is to improve the approximation ratio for the versions of the problem that are NP-hard. In this respect, we should investigate whether zigzags may help to obtain approximate solutions, at least for particular combinations of searching and walking speeds of the robots (note that we know from the present paper that zigzags never help to obtain optimal solutions). Another direction is to study the configurations of robots' speeds and/or environments for which optimal solutions can be computed efficiently. Finally, it is worthwhile to consider different and more general search domains, such as non-simple closed or open curves.

Theorem 7 .

 7 t-SBPL z admits a randomized algorithm which achieves an expected approximation ratio of 1 -1 -1 2t 2t , needs O(n log t) random bits, and runs in O(n log n) time.


Made Windu

Antara Kesiman

Sophea Prum
email: sophea.prum@univ-lr.fr

Jean-Christophe Burie
email: jcburie@univ-lr.fr

Jean-Marc Ogier
email: jean-marc.ogier@univ-lr.fr

An Initial Study On The Construction Of Ground Truth Binarized Images Of Ancient Palm Leaf Manuscripts

Keywords: ground truth construction, binarization, low quality document image, palm leaf manuscript

Ancient palm leaf manuscripts are one of the very valuable cultural heritages that store various forms of knowledge and historical records of social life in Southeast Asia. The automatic analysis of these documents, in order to extract relevant information, is a real challenge. However, to evaluate the developed extraction algorithms, a ground truth is absolutely necessary. In this paper, we present some of the challenges of the state of the art binarization methods as an initial study for the construction of ground truth binarized images of palm leaf manuscripts. We propose and analyze the need for a specific scheme for the construction of the ground truth of binarized images. The aim of this scheme is to achieve a better ground truth for low quality palm leaf manuscripts. We experimentally tested and evaluated our proposed specific scheme and got promising results. This scheme adapts and performs better in constructing the ground truth of binarized images for palm leaf manuscripts.

I. INTRODUCTION

The existence of ancient palm leaf manuscripts in Southeast Asia is very important both in term of quantity and variety of historical content. In the last five years, ancient palm leaf manuscripts have received great attention from researchers in the field of document image analysis. For example, a digitization project for palm leaf manuscripts from Cambodia 1 and Thailand [START_REF] Chamchong | Comparing Binarisation Techniques for the Processing of Ancient Manuscripts[END_REF], [START_REF] Che | A Review of Evaluation of Optimal Binarization Technique for Character Segmentation in Historical Manuscripts[END_REF].

The ancient palm leaf manuscript is written on a dried palm leaf by using some sort of sharp pen or small knife, which is then scrubbed with natural dyes. Due to these specific characteristics, ancient palm leaf manuscripts are providing new challenges in document analysis.

Binarization process as one of the early and important stage document analysis pipeline, is also a real challenge for ancient palm leaf manuscripts. In order to evaluate and to select an optimal binarization method, the ground truth binarized image is necessary. Unfortunately, based on our knowledge, there is no existing public ground truth binarized image of palm leaf manuscripts. Therefore, creating a new ground truth binarized 1 http://www.khmermanuscripts.org/ image of palm leaf manuscripts is a necessary step in our research.

Manual creation ground truth of binarized images (e.g. with PixLabeler application [START_REF] Saund | PixLabeler: User Interface for Pixel-Level Labeling of Elements in Document Images[END_REF]) is a time consuming task. Therefore, in the research domain, several semi-automatic frameworks for the construction of ground truth binarized images have been presented [START_REF] Ntirogiannis | An Objective Evaluation Methodology for Document Image Binarization Techniques[END_REF]- [START_REF] Bal | Interactive degraded document enhancement and ground truth generation[END_REF] to reduce the time of ground truthing process. The human intervention is required only for some necessary tasks. For the DIBCO competition series [START_REF] Pratikakis | ICDAR 2013 Document Image Binarization Contest (DIBCO 2013)[END_REF], the ground truth binarized images are constructed using a semi-automatic procedure described in [START_REF] Ntirogiannis | Performance Evaluation Methodology for Historical Document Image Binarization[END_REF]. This procedure is an improved version of the previous work proposed in [START_REF] Ntirogiannis | An Objective Evaluation Methodology for Document Image Binarization Techniques[END_REF] which used an initial binarized image to obtain the skeleton of the characters, and a dilation process constrained by the edges of the character to construct the ground truth binarized images. This procedure is adapted and improved by some other works on the construction of ground truth binarized images. For instance, in [START_REF] Messaoud | A design of a preprocessing framework for large database of historical documents[END_REF], a similar method is used to create ground truth of a large document databases. In [START_REF] Nafchi | An Efficient Ground Truthing Tool for Binarization of Historical Manuscripts[END_REF], in order to save user time in manual modification process by expert, two features of phase congruency are used to preprocess Persian heritage images to generate a rough initial binarized image. In [START_REF] Bal | Interactive degraded document enhancement and ground truth generation[END_REF], the ground truth binarized image of machine-printed document is constructed by segmenting and clustering the characters during the foreground enhancement step. User can manually add and remove character model assignments to degraded character instances. Unfortunately, it is impossible to validate a ground truth construction methodology to create a perfect ground truth image from a real image. The ground truth images are normally accepted based on visual observation.

In this paper, we analyse the previous works on construction of ground truth binarized images, especially based on the method proposed and used for DIBCO competition series. The purpose of our work is to achieve a better ground truth binarized images for low quality palm leaf manuscripts. This paper is organized as follow: section 2 briefly presents the construction of ground truth framework presented in [START_REF] Ntirogiannis | An Objective Evaluation Methodology for Document Image Binarization Techniques[END_REF] and [START_REF] Ntirogiannis | Performance Evaluation Methodology for Historical Document Image Binarization[END_REF], and draw some remarks and propositions for the construction of ground truth of palm leaf manuscripts. Section 3 addresses the challenges in binarization process of palm leaf manuscript images and describes the specific scheme proposed for the initial binarization process for the construction of ground truth binarized images of palm leaf manuscripts. The experimental results are presented in Section 4 and conclusions with some prospects for the future work are given in Section 5.

II. STUDY OF EXISTING FRAMEWORKS FOR CONSTRUCTION OF GROUND TRUTH BINARIZED IMAGES

The construction of ground truth binarized images proposed in [START_REF] Ntirogiannis | An Objective Evaluation Methodology for Document Image Binarization Techniques[END_REF], consists of several steps: initial binarization process, skeletonization of the characters, manual correction of skeleton, and second skeletonization after manual correction process. The estimated ground truth image is then constructed by dilating the corrected skeleton image, constrained by the character edges (detected using Canny algorithm [START_REF] Canny | A Computational Approach to Edge Detection[END_REF]) and the binarized image under evaluation. The skeleton is dilated until half of the Canny edges intersect each binarized component. The detail algorithm in pseudo code can be found in [START_REF] Ntirogiannis | An Objective Evaluation Methodology for Document Image Binarization Techniques[END_REF]. In this method, poor quality of initial binarized image will directly affect the result of the estimated ground truth. The ground truth image constructed strongly depends on the binarized image used as a constraint during the dilation process of the skeleton. The ground truth binarized images used for the DIBCO competition series are constructed with a modified procedure [START_REF] Ntirogiannis | Performance Evaluation Methodology for Historical Document Image Binarization[END_REF] as illustrated in Fig. 1. In this procedure, the conditional dilation step of the skeleton is constrained only by Canny edge image, without any initial binarized image. Fig. 1. Ground truth construction procedure used for DIBCO series [START_REF] Ntirogiannis | Performance Evaluation Methodology for Historical Document Image Binarization[END_REF] We implemented the construction of ground truth binarized image based on the procedure proposed in [START_REF] Ntirogiannis | An Objective Evaluation Methodology for Document Image Binarization Techniques[END_REF] and the modified version in [START_REF] Ntirogiannis | Performance Evaluation Methodology for Historical Document Image Binarization[END_REF]. Based on our preliminary experiments, it is expected to obtain a good initial binarized image as the input to the next process of ground truth creation. The initial binarization method used in the stage of construction of skeletonized ground truth image should be able to generate an optimal and acceptable 'good enough' skeleton which detects and keeps the form of the characters. Image of skeleton generated in this step will facilitate the manual correction process. The more we have a correct skeleton the more the manual process is easier and faster.

After some experiments, we notice that for a nondegraded palm leaf manuscript, a simple global thresholded binarization method is sufficient to generate an acceptable binarized image and optimal image of skeleton. However, this method is not adapted to degraded palm leaf manuscripts. Fig. 2 shows some examples of skeletonized image generated with Matlab standard function bwmorph 2 from different binarized images using different binarization methods. Influenced by the dried palm leaf texture, the stroke of characters in palm leaf manuscripts is thickened and widened. As a consequence, a lot of small short unuseful branchs on the skeleton are generated. Because of the poor quality of binarized and skeletonized image, the step of manual correction of the skeleton is very time consuming, it takes almost 8 hours for only one image of palm leaf manuscript. Therefore, in the case of degraded and low quality palm leaf manuscript images, our initial study 2 http://fr.mathworks.com/help/images/ref/bwmorph.html focused on the development of an initial binarization process for the construction of ground truth binarized images (see Section III). One other important remark, superposing image of skeleton on the original image to guide the manual correction process is not enough. A priori knowledge of the form of ancient characters is mandatory to guarantee that the incomplete character skeleton can be completed in a more natural trace as the way how the characters have been originally written. We suggest that the manual correction process should be done by a philologist or at least by a person who knows well how to write the ancient characters with a guide of a transcription of the manuscript provided by a philologist. Fig. 2. Examples of image of skeleton (left to right and up to bottom) generated from binarized image of Otsu [START_REF] Pratikakis | ICDAR 2013 Document Image Binarization Contest (DIBCO 2013)[END_REF], [START_REF] Messaoud | A design of a preprocessing framework for large database of historical documents[END_REF], Niblack [START_REF] Khurshid | Comparison of Niblack inspired binarization methods for ancient documents[END_REF], Rais [START_REF] Naveed Bin | Adaptive thresholding technique for document image analysis[END_REF], and NICK [START_REF] Khurshid | Comparison of Niblack inspired binarization methods for ancient documents[END_REF]

III. SPECIFIC BINARIZATION SCHEME PROPOSED

A. Challenges

Ancient palm leaf manuscripts contain artefacts due to aging, foxing, yellowing, marks of strain, local shading effects, with low intensity variations or poor contrast, random noises, discoloured part, fading. We can also mention the merges, fractures and other deformations in the character shapes, with the use of nonstandard fonts, varying space between letters, and varying space between lines as illustrated in Fig. 3. We experimented and compared several alternative wellknown binarization algorithms on our palm leaf manuscript images. Fig. 4 shows the binarized images when applying different method such as Otsu [START_REF] Pratikakis | ICDAR 2013 Document Image Binarization Contest (DIBCO 2013)[END_REF][9], Niblack [START_REF] Khurshid | Comparison of Niblack inspired binarization methods for ancient documents[END_REF]- [START_REF] Feng | Contrast adaptive binarization of low quality document images[END_REF], Sauvola [START_REF] Sauvola | Adaptive document image binarization[END_REF], Wolf [START_REF] Khurshid | Comparison of Niblack inspired binarization methods for ancient documents[END_REF][12], Rais [START_REF] Naveed Bin | Adaptive thresholding technique for document image analysis[END_REF], NICK [START_REF] Khurshid | Comparison of Niblack inspired binarization methods for ancient documents[END_REF], and Howe [START_REF] Howe | Document binarization with automatic parameter tuning[END_REF]. Since there is no existing ground truth binarized image for our palm leaf manuscripts, we cannot objectively evaluate these results. Therefore, a visual observation process has been applied to compare the results. It is clear that those binarization methods do not give a good binarized image for palm leaf manuscript images. All methods extract unrecognizable characters on palm leaf manuscripts with noise. Howe's method, one of the good ranked methods from DIBCO 2013, does not also provide a good result for this kind of document. Therefore, to binarize the images of palm leaf manuscripts, a specific and adapted binarization technique is required.

B. Specific scheme for the initial binarization process

In order to overcome the binarization problem on degraded and low quality palm leaf manuscript image, we proposed a 'semi-local' concept. The idea of this proposed method is to apply a powerful global binarization method on only precise local character area. Our binarization scheme consists of several steps as illustrated in Fig. 5. First, the edge detection with Prewitt Operator is applied to get the initial surrounding area of the line-strokes of each character. Based on our visual observation, Prewitt leads to high edge response on inner part of the characters, and it gives a good approximate area for the skeleton. Whereas Canny leads to high edge response on the outer side of text stroke, and it detects over sensitively the textural part of the palm leaf background. The greyscale image of edge is then binarized with Otsu's method to get the first binarized image of the palm leaf manuscript. Median Filter is then applied to this binarized image in order to remove noise. After noise reduction, some characters might be affected and broken. A dilation process is applied to recover and reform the broken parts of the character. We, then, construct the approximated character area using Run Length Smearing (RLS) method [START_REF] Wahl | Block segmentation and text extraction in mixed text/image documents[END_REF]. The smearing method should be done optimally, so the missing/undetected character area can be detected completely. The RLS in row wise will cover the missing area in horizontal strokes character line, meanwhile the RLS in column wise will cover the missing area in vertical strokes character line. After those steps, we finally have a binarized image with an approximated character area in black, and the background area in white. The next step is the main concept of this scheme. We applied Otsu's binarization method for the second time, but locally only within a limited character area, defined by each connected component form the first binarized image generated (Fig. 6). After the initial binarization process, we can finally perform a morphological-based thinning method to get the skeleton of the character. The thinned image normally still have the unwanted branch, so we apply a morphological-based pruning method to our thinned characters image. A pruning method for the skeleton is effective to remove spurious unwanted parts of the skeleton, and it makes the manual correction process of the skeleton faster. Fig. 7 shows a sample of image sequence as the result of our specific scheme. The goodness of the results can only be estimated qualitatively by examining the results. Based on visual criteria, the proposed scheme provides a good initial image of skeleton with respect to image quality and preservation of meaningful textual character information.

IV. EXPERIMENTS AND RESULTS

We experimentally tested the framework for construction of ground truth binarized image for nondegraded and degraded low quality palm leaf manucsript images. The sample images for the nondegraded palm leaf manuscript images come from the story of Kakawin Ramayana (reference code 07.41/5634.3 and 07.40/5634.3), in Museum Bali, Denpasar, Indonesia. The palm leaf manuscripts were ordinarily scanned with scanner Epson L210 in 600 dpi without any specific external illumination. The sample images for the degraded low quality palm leaf manuscript images come from the private family collection and Museum Gedong Kertya, Singaraja, Indonesia. The manuscripts were scanned in 300 dpi and it consists of several types of degradation as already mentioned in section III.A. The manuscripts were written on both sides, but there was no back-to-front interference observed.

A. Case for nondegraded palm leaf manuscript images

For nondegraded palm leaf manuscripts, we used a simplest and the most conventional global thresholding method with a proper threshold selected manually to obtain the initial binarized image. With this initial binarized image, it is already sufficient to obtain an acceptable skeletonized image. We performed the manual correction of the skeleton, guided by the transcription of the manuscript provided by a philologist, to finally obtain the skeleton ground truth of the manuscript. Fig. 8 shows a snapshot of simple prototype with user friendly interface that we developed and used to facilitate the manual correction process. We finally constructed the ground truth image by dilating the corrected skeleton image, constrained by the Canny edge image and the initial binarized image from Otsu's global method. We use Otsu's global method instead of the same global fixed thresholding method used in our skeleton ground truth construction because we need a more complete connected component of all characters detected on the binarized image. Other binarization methods can also be used, for example Niblack's method or the multi resolution version of Otsu's method [START_REF] Gupta | OCR binarization and image pre-processing for searching historical documents[END_REF]. They also provide a satisfactory preliminary binarized image. Fig. 9 shows an example of final ground truth image from a nondegraded palm leaf manuscript image. It is visually an acceptable estimated ground truth image for the manuscript.

B. Case for degraded low quality palm leaf manuscript images

For degraded low quality palm leaf manuscript images, we applied our proposed specific binarization scheme by defining the optimal value of parameters based on our empirical experiments as follows: filter size 3x3 for Median Filter, square structuring element size 3x3 for Dilation, smearing 3 pixels in row and 3 pixels in column for RLS Method, and pruning the branch of 2 pixels. We performed the manual correction of the skeleton, guided by the transcription of the manuscript provided by a philologist to obtain the skeleton ground truth image of the manuscript. Fig. 10 shows an exemple of a low quality palm leaf manuscript and the skeleton ground truth image. We first experimented the construction of estimated ground truth image by applying a constraint of Canny edge image and an intial binarized image. For example, we used the binarized image from Niblack's method or the multi resolution version of Otsu's method as the constraint. The estimated ground truth image really depends on the initial binarized image used as a constraint. We then experimented the construction of ground truth image without any initial binarized image as a constraint. The result is shown in Fig. 11. Based on visual criteria, the proposed algorithm seems to achieve a better estimated ground truth image with respect to image quality and preservation of meaningful textual character information. Some other results of ground truth binarized image for degraded low quality palm leaf manuscript images are shown in Fig. 12.

C. Experiments on the effect of the variation of ground truth image

Recent studies on the analysis of binarization ground truthing [START_REF] Smith | An analysis of binarization ground truthing[END_REF] and the effect of ground truth on image binarization [START_REF] Smith | Effect of 'Ground Truth' on Image Binarization[END_REF] discuss the influence human subjectivity during the manual correction process that may produce several different variations of ground truth. We designed an experiment to compare the effect of the variation of ground truth image on the performance of the existing binarization methods. We generated two variations of our ground truth binarized image by applying an erosion and a dilation with a simple 3x3 square structuring element. Those two different versions of our ground truth image represent two possible human subjectivities on the border pixels of the character. We evaluated the performance of the binarization methods by using these three different versions of our ground truth binarized image. Table 1 shows the average value of F-Measure [START_REF] Ntirogiannis | An Objective Evaluation Methodology for Document Image Binarization Techniques[END_REF] of the binarization method for 9 palm leaf manuscript images. Our experiment shows that the rank performance of the binarization methods evaluated on three different versions of ground truth image is stable. This means that our original ground truth images are robust enough to be used to evaluate and to select future optimal binarizations method for ancient palm manuscripts. The low value of F-Measure for all binarization methods shows that the binarization problem is still an open question especially for specific document images such as our ancient palm leaf manuscript images. V. CONCLUSION

The specific binarization scheme proposed in this paper achieves a better ground truth for degraded low quality palm leaf manuscripts. This scheme adapts and performs better in constructing the ground truth of binarized images for palm leaf manuscripts. The ground truth images constructed with this scheme are robust enough to be used to evaluate and to select future optimal binarization methods for ancient palm leaf manuscripts. The binarization problem is still an open question especially for ancient palm leaf manuscript images.

Fig. 3 .

 3 Fig. 3. Samples images of ancient palm leaf manuscripts from Bali

Fig. 4 .

 4 Fig. 4. Original image (upper left), and binarized images (up to bottom,left to right) using methods of Otsu, Niblack, Sauvola, Wolf, Rais, NICK, and Howe

Fig. 5 .

 5 Fig. 5. Semi-local binarization scheme

Fig. 6 .

 6 Fig. 6. Examples of extracted character area (on the left) and their semi-local binarization result (on the right).

Fig. 7 .

 7 Fig. 7. Original sample image, and sequence sample image of Prewitt, Otsu, Median Filter, Dilation, RLS Row, RLS Col, Local Otsu, Thinning, Pruning, Superposed Skeleton on Original Image

Fig. 8 .Fig. 9 .

 89 Fig. 8. Snapshot of Prototype Interface used for manual correction of skeleton

Fig. 10 .

 10 Fig. 10. Original Image and the skeleton ground truth

  TABEL 1. AVERAGE F-MEASURE OF EXISTING BINARIZATION METHOD EVALUATED ON THREE VERSIONS OF GROUND TRUTH IMAGE CREATED BY OUR PROPOSED SCHEME

	Rank	Method	GT Original GT Eroded GT Dilated
	1	NICK	60,48	44,78	63,47
	2	SAUVOLA	57,61	40,62	61,39
	3	WOLF	54,02	41,43	56,26
	4	NIBLACK	48,35	29,47	54,63
	5	HOWE	42,47	28,98	45,76
	6	RAIS	34,61	18,82	41,68
	7	OTSU	32,88	18,90	41,32

ACKNOWLEDGMENT

The authors would like to thank Museum Bali in Denpasar and Museum Gedong Kertya in Singaraja Bali, Indonesia, for providing us the sample of ancient palm leaf manuscripts. This work is also supported by the DIKTI BPPLN Indonesian Scholarship Program and the STIC Asia Program implemented by the French Ministry of Foreign Affairs and International Development (MAEDI).


Made Windu

Antara Kesiman

Sophea Prum
email: sophea.prum@univ-lr.fr

I Made

Gede Sunarya
email: sunarya@undiksha.ac.id

Jean-Christophe Burie
email: jcburie@univ-lr.fr

Jean- Marc Ogier
email: jean-marc.ogier@univ-lr.fr

An Analysis of Ground Truth Binarized Image Variability of Palm Leaf Manuscripts

Keywords: Ground truth image, Binarization, Variability, Palm leaf manuscript

As a very valuable cultural heritage, palm leaf manuscripts offer a new challenge in document analysis system due to the specific characteristics on physical support of the manuscript. With the aim of finding an optimal binarization method for palm leaf manuscript images, creating a new ground truth binarized image is a necessary step in document analysis of palm leaf manuscript. But, regarding to the human intervention in ground truthing process, an important remark about the subjectivity effect on the construction of ground truth binarized image has been analysed and reported. In this paper, we present an experiment in a real condition to analyse the existance of human subjectivity on the construction of ground truth binarized image of palm leaf manuscript images and to measure quantitatively the ground truth variability with several binarization evaluation metrics.

I. INTRODUCTION

The collection of palm leaf manuscripts in Southeast Asia attracted the attention of researchers in document image analysis, for example some works on document analysis of palm leaf manuscript from Thailand [START_REF] Chamchong | Comparing Binarisation Techniques for the Processing of Ancient Manuscripts[END_REF] [START_REF] Che | A Review of Evaluation of Optimal Binarization Technique for Character Segmentation in Historical Manuscripts[END_REF]. As a very valuable cultural heritage which contains a wide variety of Asian social cultural life aspects, palm leaf manuscripts offer a new challenge in document image analysis system due to the physical characteristics and conditions of the manuscript. Written on a dried palm leaf by using a sharp pen (which looks like a small knife) and colored with natural dyes, palm leaf manuscript images provide a real challenge in the binarization process to separate text from the background, as the early important step in document image analysis. The palm leaf manuscripts contain discoloured parts and artefacts due to aging and low intensity variations or poor contrast, random noises, and fading. Severals deformations in the character shapes are visibles due to the merges and fractures of the use of nonstandard fonts, varying space between letters, and varying space between lines.

With the aim of finding an optimal binarization method for palm leaf manuscript images, some binarization methods which are already proposed and widely used in document image research community have to be tested and evaluated. To evaluate the performance of binarization methods, two approachs are widely used. The first approach evaluates the binarization methods based on the character recognition rate reached by an OCR system applied on those binarized images [START_REF] Ntirogiannis | Performance Evaluation Methodology for Historical Document Image Binarization[END_REF]. But this approach has been criticized that the binarization method is evaluated in their interaction with other process on document analysis pipeline. The second approach evaluates the binarization methods by comparing pixel-by-pixel the difference between binarized image and a ground truthed binarized image [START_REF] Gatos | DIBCO 2009: document image binarization contest[END_REF] [START_REF] Pratikakis | ICDAR 2013 Document Image Binarization Contest (DIBCO 2013)[END_REF]. In our case where the OCR system for some specific Southeast Asian alphabets are not available yet, the ground truth binarized image of palm leaf manuscripts has to be created to be able to quantitatively measure and compare the performance of all binarization methods. Therefore, creating a new ground truth binarized image of palm leaf manuscripts is a necessary step in our research.

The construction of ground truth binarized image is normally done totally by human, but several frameworks with a specific tool already proposed semi-automatic method to facilitate a much faster and more precise ground truthing process. Regarding to the human intervention in ground truthing process, an important remark about the subjectivity effect on the construction of ground truth binarized image has been analysed and reported. The work of [START_REF] Smith | An analysis of binarization ground truthing[END_REF] and [START_REF] Smith | Effect of 'Ground Truth' on Image Binarization[END_REF] analysed the binarization ground truthing and the effect of ground truth on image binarization of DIBCO binarized image dataset [START_REF] Gatos | DIBCO 2009: document image binarization contest[END_REF]. The study stated that the different choice of binarization ground truth affects the binarization algorithm design and the performance can vary significantly depending on the choice of ground truth.

In this paper, we present an experiment in a real condition to analyse the human intervention subjectivity on the construction of ground truth binarized image and to measure quantitatively the ground truth variability of palm leaf manuscript images with different binarization evaluation metrics. This experiment measures the difference between two ground truth binarized images from two different ground truthers. Based on the real survey and experiment on this research, we describe some challenges on the construction of ground truth binarized image for palm leaf manuscripts. This paper is organized as follow: section II briefly presents the digitization process and sample images of palm leaf manuscript used in this experiment. Section III describes the semi-automatic framework for the construction of ground truth binarized image and also the binarization evaluation metrics. The experimental results are presented in Section IV and conclusions with some prospects for the future work are given in Section V.

II. DIGITIZATION PROCESS

Our first initial campaign on the digitization of palm leaf manuscript in Southeast Asia is collecting the sample images of the manuscript from Bali, Indonesia. In order to obtain the variety of the manuscript images, the sample images used in this experiment come from 9 different collections (contents), randomly selected from all collections found in Museum of Gedong Kertya, City of Singaraja, Regency of Buleleng, North Bali, Indonesia. A summary of the collection characteristics is listed in Table 1.

For capturing process, we use a Canon EOS 5D Mark III, and set the camera setting as follows: F-stop: f/22 (diafragma), exposure time: 1/50 sec, ISO speed: ISO-6400, focal length: 70 mm, flash: On -1/64, distance to object: 76 cm, focus: Quick mode -Auto selection On. We designed a black box camera support by wood (see Fig. 1) to avoid the irregular lighting/luminance condition and to fits our semi outdoor capturing location. Two additional light are added inside the black box support with White Neon 50 cm 20 watt. From the 9 collections, we captured 47 pages of palm leaf manuscript. Thumbnail samples of these images are showed in Fig. 2.

III. CONSTRUCTION OF GROUND TRUTH BINARIZED IMAGE AND BINARIZATION EVALUATION METRICS

The first part of this experiment is the construction of ground truth binarized image of palm leaf manuscripts. The variability of the ground truth binarized image is then measured by several binarization evaluation metrics.

A. Framework for construction of ground truth binarized image

In this experiment, we adopted a semi-automatics framework for construction of ground truth binarized image which were used to build the database in DIBCO competition series, as illustrated in Fig. 3 [START_REF] Ntirogiannis | Performance Evaluation Methodology for Historical Document Image Binarization[END_REF]. It consists of several steps: initial binarization process, skeletonization of the characters, character edge detection, manual correction of skeleton, and estimation of ground truth image by a conditional dilation. This framework needs a first initial binarization method to optimally separate text from the background, and it provides a first binary image for the skeletonizing process of the characters on manuscript. The human intervention is done by a user interaction process on manual correcting procedure based on character edges (detected using Canny algorithm [START_REF] Canny | A Computational Approach to Edge Detection[END_REF]) and character skeletons. After the manual correction process, in this framework, the final estimated ground truth binarized image is then automatically constructed by dilating the corrected skeleton image, constrained by the character edges. The skeleton is dilated until half of the Canny edges intersect each binarized component of the dilated skeleton. Fig. 3. Ground truth construction procedure used for DIBCO series [START_REF] Ntirogiannis | Performance Evaluation Methodology for Historical Document Image Binarization[END_REF].

For our experiment, in order to measure the variability of human subjectivity in our ground truth creation, we did not apply any initial binarization and skeletonization methods. The skeletonization process is completely performed by human. The skeleton drawn manually by user is dilated until Canny edges intersect each binarized component of the dilated skeleton in a ratio of 0.1. This value of minimal ratio between number of pixels in intersection of Canny edge and number of pixels of the dilated skeleton is found based on our empirical experiment and observation on the thickness of the character stroke in our manuscripts.

B. Binarization evaluation metrics

As presented in [START_REF] Smith | An analysis of binarization ground truthing[END_REF], three metrics of binarization evaluation which are used in the DIBCO 2009 contest [START_REF] Gatos | DIBCO 2009: document image binarization contest[END_REF] are used in this analysis to measure the difference between two ground truth binarized images from two different ground truthers.

F-Measure (FM)

FM is defined from Recall and Precision.

Re

*100

TP FN TP call + = (1)

Pr

*100

TP FP TP ecision + = (2)
TP is defined as true positive, occurs when the image pixel is labeled as foreground and the ground truth is also. FP is defined as false positive, occurs when the image pixel is labeled as foreground but the ground truth is labeled as background. FN is defined as false negative, occurs when the image pixel is labeled as background but the ground truth is labeled as foreground.

A higher F-measure indicates a better match.

Peak SNR (PSNR)

PSNR is calculated from Mean Square Eror (MSE).

C MSE PSNR = ( 5
)
where C is defined as 1, the difference between foreground and background colors in the case of binary image. A higher PSNR indicates a better match.

The value of FM and PSNR when we assumed the image drawn by the first ground truther as ground truth image will be the same with the value of FM and PSNR when we assumed the vice versa, the image drawn by the second ground truther as ground truth image.

Negative Rate Metric (NRM)

NRM is defined from negative rate of false negative (NRFN) and negative rate of false positive (NRFP). TN is defined as true negative, occurs when both the image pixel and ground truth are labeled as background. TP, FN, and FP are the same definitions as in F-Measure. The value of NRM when we assumed the image drawn by the first ground truther as ground truth image will not be the same with the value of NRM when we assumed the image drawn by the second ground truther as ground truth image. In this case, we calculated two value of NRM: NRM1 and NRM2. A lower NRM indicates a better match.

IV. EXPERIMENTS AND RESULTS

A. Scheme diagram of our experiment

For this experiment, we worked with 70 students from Department of Informatics Education, Ganesha University of Education, Singaraja Bali. Each student was asked to trace manually the skeleton of the Balinese character found in palm leaf manuscript image with PixLabeler tool [START_REF] Saund | PixLabeler: User Interface for Pixel-Level Labeling of Elements in Document Images[END_REF]. One student worked with two different images, and one image was ground truthed by two different students. These two manually skeletonized image will be re-skeletonized with Matlab function bwmorph 1 to make sure that the skeleton is one pixel wide for the next process of automatic ground truth estimation with conditional dilation and Canny edge constraint. As mention in subsection III.A, Figure 4 shows the scheme diagram of our experiment. Figure 5 shows some samples images as the result example of this experiment.

B. Measure of ground truth variability

First, we measured the variability between two skeletonized ground truthed images manually drawn by two different ground truthers with the three Binarization Evaluation Metrics as presented in sub-section III.B. The results of these 3 measures are presented in Table 2. The wide range between the maximum and the minimum value and also the mean and variance value of all three binarization evaluation metrics from 47 images show that there is a large variability between the ground truthers for each image. We then measured the variability between the two ground truth binarized images automatically estimated from two different manually skeletonized image for each image of manuscript (see sub-section III.A). Table 3 illustrates this variability. The wide range between the maximum and the minimum value and also the mean and variance value of all three binarization evaluation metrics from 47 images show that there is still a large variability between the estimated ground truth images for each image. By comparing the value of binarization evaluation metrics between the two manually skeletonized ground truth images (see Table 2) and between the two automatic estimated ground truth images (see Table 3), we can see that the variability of two ground truth images in F-Measure and NRM for all 47 images decreases after the estimation ground truth process. The value of PSNR decreases because the number of different foreground-background pixels between the two estimated ground truth images also increases after the automatic estimation process, not only the number of common foreground pixels from the two estimated ground truth images. Figures 6 to 9 show that the ground truth estimation process tends to decrease the variability between two ground truthers to produce a better match between two ground truth images. We also tested and estimated the ground truth binarized image from the union of two skeleton images manually drawn by two differents ground truthers (see exemple in Fig. 5(e)). The variability between this estimated union ground truth image with two other estimated ground truth images from each ground truther is then measured. Tabel 4 and 5 illustrate the results of the comparison metric for all 47 images in experiment. The ground truth image estimated from union of two skeleton images indicates a better match with two other ground truth images from two different ground truthers.

V. CONCLUSIONS AND FUTUR WORKS

Based on our data survey after the experiment with all ground truthers, we observed and remarked some challenges on the ground truth creation of palm leaf manuscripts as follows: 1. The balinese aphabets found on the manuscripts are not daily used by the ground truthers. Most of the ground truthers learned those alphabets in their elementary school until their junior or senior high school, but they never re-used those alphabets after the classroom learning process. There are some alphabets that they have never seen before. For those kind of alphabets, the ground truthers could not make a smooth and natural trace of the character skeleton. Regarding the variability of ground truth images produced in this experiment, we suggest that this kind of important fact or condition should be always taking into account in every ground truthing process of ancient manuscripts project. 2. The time needed to semi-manually corrected the skeleton of image from an initial automatic method can be much greater than making the skeleton totally manual started from zero. In our first trial experiment, we need 4 until 6 hours to corrected the semi-automatic generated skeleton. It is due to the physical carateristics of the manuscripts which make the binarizing and skeletonizing method do not tend to produce the optimal good skeleton of the characters. We finally decided to make it totally manual, and it takes between 2 until 3 hours to trace the skeleton started from zero.

From the result of this experiment, we proved that the human subjectivity has a great effect in producing a great variability of ground truth binarized image. This phenomen becomes much more visible when we are working on the binarization process of ancient type document or manuscript where the physical characteristics and conditions of the manuscript are not good enough or it is still hard to be ground truthed even by human. The method of binarization evaluation by comparing and measuring pixel-by-pixel with a ground truth binarized image should be re-evaluated to avoid the great bias from human subjectivity. Some other measures should be proposed to evaluate the binarization process of document image of ancient manuscripts. The choice of ground truth data set and the variability within the ground truth should be analyzed quantitatively before the performance measure of any binarization methods. In the case of a manuscript with specific ancient characters, the qualitative observation and validation should also be made by the philologist to guarantee the correctness of the binarized characters on the manuscripts.

Fig. 1 .

 1 Fig. 1. Black box camera support for digitizing process of palm leaf manuscripts.

2

 2

Fig. 4 .Fig. 5 .

 45 Fig. 4. Scheme diagram of experiment.

Fig. 6 .Fig. 7 .Fig. 8 .Fig. 9 .

 6789 Fig. 6. Comparison of F-Measure between two skeletonized ground truth image and between two estimated ground truth image

Table 1 .

 1 Collection of palm leaf manuscripts from Museum Gedong Kertya, Singaraja Bali, Indonesia

			Reference	Physical	Nb of	Nb of
	No	Content	Code in	size of	total	captured
			Museum	manuscript	pages	pages
	1.	Sima Desa Tejakula	IIA-5-789	50 x 4 cm	27	7
	2.	Awig-awig Desa Tunju	IIA-10-1534	50 x 4 cm	6	2
	3.	Dewa Sasana	IIB-2-180	50 x 4 cm	39	4
		Panugrahan
	4.	Bhatara Ring	IIIB-12-306	50 x 4 cm	39	8
		Pura Pulaki
	5.	Buwana	IIIB-42-1526	50 x 4 cm	18	2
	6.	Pambadah	IIIB-45-2296	50 x 4 cm	12	5
	7.	Krakah Sang Graha	IIIC-19-1293	50 x 4 cm	22	6
	8.	Taru Pramana	IIIC-20-1397	50 x 4 cm	5	7
	9.	Siwa Kreket	IIIC-23-1506	50 x 4 cm	8	6
				TOTAL		47 pages

Fig. 2. Sample images of palm leaf manuscripts from Museum

Gedong Kertya, Singaraja Bali, Indonesia

Table 2 .

 2 Variability between two manually skeletonized ground truthed image.

	Comparison metric	FM1	NRM1 NRM2 PSNR
	Maximum	58,945	0,371	0,458 60,166
	Minimum	14,058	0,209	0,209 26,882
	Mean	41,459	0,302	0,303 33,196
	Variance	77,764	0,002	0,003 60,083

Table 3 .

 3 Variability between two ground truthed image automatically estimated from two different manually skeletonized image.

	Comparison metric	FM1	NRM1 NRM2 PSNR
	Maximum	74,731	0,309	0,446	59,196
	Minimum	18,615	0,128	0,130	23,961
	Mean	59,556	0,214	0,215	31,110
	Variance	89,880	0,002	0,003	61,383

  Tabel 4. Variability between ground truth image estimated from union of two skeleton images with ground truth image estimated from the first ground truther

	Comparison metric	FM	NRM1 NRM2 PSNR
	Maximum	89,758	0,076	0,418	67,095
	Minimum	27,823	0,038	0,064	29,854
	Mean	80,539	0,066	0,132	37,759
	Variance	71,677	0,000	0,003	70,775
	Tabel 5. Variability between ground truth image estimated from union
	of two skeleton images with ground truth image estimated from the
	second ground truther
	Comparison metric	FM	NRM1 NRM2 PSNR
	Maximum	94,182	0,090	0,227	65,188
	Minimum	66,806	0,025	0,035	30,815
	Mean	81,155	0,067	0,129	37,816
	Variance	17,054	0,000	0,001	63,464

ACKNOWLEDGMENT

The authors would like to thank Museum Gedong Kertya in Singaraja Bali, Indonesia, for providing us the sample of palm leaf manuscripts, and the students from Department of Informatics Education, Ganesha University of Education for helping us in binarization ground truthing process for this experiment. This work is also supported by the DIKTI BPPLN Indonesian Scholarship Program and the STIC Asia Program implemented by the French Ministry of Foreign Affairs and International Development (MAEDI).