Nicolas Jouandeau

Zhi Yan

Decentralized Waypoint-based Multi-robot Coordination

This paper describes a decentralized approach based on Alternative Waypoint Generating (AWG) for planning separate kinematic paths to multiple robots to alleviate the waiting situation problems. The basic thought of this approach is straightforward: If a robot request a target waypoint that has already been assigned to another robot, then this robot will consider this waypoint as an obstacle and attempt to get an alternative one around it. The proposed strategy has been implemented and evaluated in simulation. The experimental results demonstrated that the waiting situation problems have been decreased and the overall system performance has been improved.

I. INTRODUCTION

Multi-robot motion planning is one of the most challenging tasks in multi-robot systems. A very common problem in the motion planning for a group of mobile robots is when multiple robots move to the same waypoint, causing collision, congestion and deadlock, then may reduce system performance. We defined this kind of dynamic standstill of system caused by waypoint mutual exclusion as the waiting situation problem. Because, for better or worse, a robot should wait until the other one pass first, or all robots should wait for planner to replan their trajectories.

Therefore, we need some sort of coordination mechanism to harmonize the motion of robots, so as to minimize the waiting situation problem. In this paper, we present a decentralized approach based on Alternative Waypoint Generating (AWG) for planning separate kinematic paths to multiple robots. Whenever a robot request a target waypoint that has been assigned to another robot, then the former will consider this waypoint as an obstacle and try to find an alternative one around it.

Our previous work [START_REF] Yan | Sampling-based multi-robot exploration[END_REF] focused on the problem of multirobot exploration by using separate topological graph based on sampling environment map iteratively. The proposed investigation is related to the approach described in this paper, however, the former is based on centralized mechanism, which needs a central agent to process the map and assign exploration target points to robots, if this agent fails, the whole system will fail. In contrast, the decentralized mechanism does not need the central agent, where robots use locally observable informations to make their plans. This mechanism has a good adaptability and strong robustness, although the solutions it got are often sub-optimal.

The remainder of the paper is organized as follows: Section II describes an overview of some related works; followed by the discussion of the problem of waiting situation, described in Section III; subsequently, Section IV describes our decentralized waypoint-based method; Section V describes the experimental results obtained with our method; the paper is concluded in Section VI.

II. RELATED WORK

Jäger and Nebel [START_REF] Jäger | Decentralized collision avoidance, deadlock detection, and deadlock resolution for multiple mobile robots[END_REF] described a decentralized method for coordinating the independently planned trajectories of multiple mobile robots to avoid collisions and deadlocks among them. Their idea is: for the collision, whenever the distance between two robots drops below a certain value, they exchange information about their planned trajectories and determine whether they are in danger of a collision. If a possible collision is detected, they monitor their movements and, if necessary, insert idle times between certain segments of their trajectories in order to avoid the collision. For the deadlock, whenever a deadlock is detected, the trajectory planners of each of the involved robots are successively asked to plan an alternative trajectory until the deadlock is resolved. Moors et al. [START_REF] Moors | A probabilistic approach to coordinated multi-robot indoor surveillance[END_REF] presented a graph-based algorithm for coordinate multi-robot motion planning in 2D indoor environments. The scenario of this research is multi-robot indoor surveillance. The proposed approach takes the limitations and uncertainties of sensors into account, and generates the coordinated motion plan for multiple robots by using A* search algorithm. The authors also introduced a framework based on realistic probabilistic sensor models and worst case assumptions on the intruder's motions in order to compare different approaches and evaluate the coordination performance of the proposed approach. Marcolino and Chaimowicz [START_REF] Marcolino | Traffic control for a swarm of robots: avoiding group conflicts[END_REF] proposed an decentralized coordination algorithm to control the traffic of a swarm of robots, avoiding congestion situations when large groups of robots move in opposite directions. The proposed algorithm allows the robots to perceive the possibility of collision and warn their teammates through local sensing and communication, then the group changes its trajectorie to avoid congestion. They [START_REF] Marcolino | Traffic control for a swarm of robots: avoiding target congestion[END_REF] also proposed another coordination algorithm for the control of traffic when robots try to reach the same target, where robots control their actions using a probabilistic

III. PROBLEMATIC

Generally speaking, if multiple requests targeting the same resource arrive simultaneously, resource conflict will occur. This issue has been studied in many forms. A well known case of a general resource conflict problem is the mutual exclusion problem [START_REF] Dijkstra | Cooperating sequential processes[END_REF] in distributed computing systems or multi-access networks, where only a single resource is available. In multiple mobile robot systems (MMRS), resource conflict arises when multiple robots need to share space, manipulable objects or communication media. We focus in this paper on the space sharing problem, which is studied through multi-robot motion planning and the collision, congestion and deadlock avoidance problems.

The problem of resource conflict is usually involved in the form of waiting situation caused by waypoint mutual exclusion over the multi-robot motion planning. Figure 1 depicts four typical situations of waypoint mutual exclusion. Two robots move to the same waypoint simultaneously: In Figure 1(a), both the red and blue robot move from the right towards the left one after another (same path same direction); In Figure 1(b), the red robot moves from the left towards the right and the blue robot moves from the right towards the left (same path different direction); In Figure 1(c), both the red and blue robot move from the right towards the left side by side (different path same direction); In Figure 1(d), the red robot moves from the top towards the bottom and the blue robot moves from the right towards the left (different path different direction). Consequently, since the waypoint can be assigned only to one robot at a time, then the mutual exclusion of the waypoint happens.

IV. OUR METHOD Generally, there are two ways to deal with the waypoint mutual exclusion. One is to let robots pass the waypoint one by one (OBO) [START_REF] Švestka | Coordinated motion planning for multiple car-like robots using probabilistic roadmaps[END_REF]. The weakness of this strategy is that one robot must wait for another robot to pass. Another way is to replan the local path in real time for each robot by using some goal seeking obstacle avoidance algorithms such as Vector Field Histogram (VFH+) [START_REF] Ulrich | VFH+: Reliable obstacle avoidance for fast mobile robots[END_REF] or Nearness Diagram (ND) Navigation [START_REF] Minguez | Nearness diagram (ND) navigation: Collision avoidance in troublesome scenarios[END_REF]. The weakness of this strategy is that robots need some time to replan their new trajectory. Consequently, the two ways both extend the time of the motion planning and limit the system efficiency.

If we can plan separate kinematic paths for multiple robots, then the waiting situation caused by waypoint mutual exclusion will be significantly reduced. Our method is summarised in Algorithm 1. Find the free point q between o and p: |pq| = r + e 8:

if there is no path between q and p , where p the previous waypoint then end if 14: end if When a robot requests a waypoint and this waypoint is occupied by other robot, then this robot will consider this waypoint as an obstacle and attempt to find an alternative waypoint. If there is no alternative waypoint can be generated, then the robot should wait for release of the occupied waypoint. In Algorithm 1: For the line 2, focusing on finding the right side of the waypoint for the reason of all vehicles should keep to the right in traffic control problem; for the line 4, the set of e is to deal with the negative influence of sensor error and it should be adjusted in practical applications; the line 4-5 mainly deal with the problem of bridge detection; and the line 8-9 mainly deal with the problem of intersection detection. Each robot has a waypoint list to maintain, whoever has occupied a waypoint will update its waypoint list, and also broadcast to all others. The result by using the proposed algorithm is illustrated in Figure 2.

Our strategy also takes into account the communication bandwidth and the communication range. Since the exchange message for maintaining the waypoint list is very few, and the robots just need to communicate with each other when they ask to pass the same waypoint and therefore should be close enough. In addition, there are two interesting feathers in the proposed algorithm:

• The robots used in multi-robot systems (MRS) are often miniaturized. The size limitations of these robots also limit the amount of on-board computing power they can carry. Thus, the algorithm applied to the robot should be simple and have a good scalability and realizability. Our algorithm meets this requirements. • Our algorithm also provides good flexibility. If the working space is large enough, then we can coordinate the motion for more robots (not only two): The generated alternative waypoint is considered as an occupied waypoint for the following robots.

V. EXPERIMENTS

Our approach has been implemented and evaluated on multirobot exploration problems where robots should cover an unknown area while building a model of the environment from sensor data, cooperatively. We chose this experimental setup because the exploration problem usually has the context of search and rescue in dangerous environments such as fire and explosion, and the time is a very important consideration in this case [START_REF] Burgard | Collaborative multi-robot exploration[END_REF].

The simulation experiments were conducted in a 2.5D multirobot simulator called Stage [START_REF] Gerkey | The player/stage project: Tools for multi-robot and distributed sensor systems[END_REF], by using a group of virtual Pioneer 2-DX robot equipped with a laser range finder which can provide 361 samples with 180 degrees field of view and a maximum range of 8 meters. Each robot can localize itself based on an abstract localization device which models the implementation of SLAM (Simultaneous Localization And Mapping). The ratio between real-world time and simulation time is about 1:3. All experiments reported in this paper were carried out on a system with an Intel Core 2 Duo E8400 3.00GHz processor, an Intel Q43 Express chipset and two DDR2 800MHz 1024MB dual channel memory.

All the robots maintain a common occupancy grid map with information about the structure of environment, which is used for path planning and obstacle avoidance in real time. We used a different number of robots to conduct several experiments in various environments. Two maps (Figure 3) were used in our simulation which are both structured environment. The exploration team size is varied from 2 to 6 robots. For each team size, 10 experimental runs are performed from different starting positions.

Voronoi-based multi-robot exploration received an increasing attention from the research community in the last decade [START_REF] Wu | Voronoi-based space partitioning for coordinated multi-robot exploration[END_REF] [15] [START_REF] Cowley | Rapid multi-robot exploration with topometric maps[END_REF]. We implemented this method for creating the original waypoints in the experiments. In terms of distribution of the original waypoints (task allocation problem), we implemented a trade-based method [START_REF] Yan | Multi-robot decentralized exploration using a trade-based approach[END_REF] to dynamic assignment for mobile robots. This method is a variant of the Contract Net Protocol. We evaluate our strategy by using the contrast experiments between the strategy OBO, VFH+, ND, and our waypoint-based method which uses the AWG algorithm described in Section IV. The experimental results are given in Figure 4. We measured the average time of the exploration for each strategy against the size of the robot team. It can be seen that our approach significantly outperforms the approach which does not considrer the waypoint mutual exclusion. Moreover, Figure 4 also shows that, the more the number of robots, the better will the effect of our approach be. Since the probability of the waypoint mutual exclusion increases with the number of robots.

We also counted the average number of the occurrences of waypoint mutual exclusion in each map as shown in Table I. This table shows that the problem of waiting situation is significantly reduced by using our waypoint-based method compared to the others. Since our method is able to plan separate paths for robots by generating the alternative waypoint, unlike the other methods which can only provide a single path for all robots.

VI. CONCLUSION

In this paper, we presented a decentralized waypoint-based approach for coordinated multi-robot motion planning. The proposed strategy is designed to plan separate kinematic paths to multiple mobile robots to alleviate the waiting situation problems by generating the alternative waypoint (AWG algorithm). We have also discussed briefly the waiting situation problems and illustrated four typical situations when the robots follow: same path in same direction, same path in different direction, different path in same direction, and different path in different direction. The experimental evaluation of the presented approach was conducted on the multi-robot exploration problem and the experimental results demonstrate that, the time needed to accomplish the exploration mission and the occurrences of waypoint mutual exclusion during the exploration have been significantly reduced.

Fig. 1 .

 1 Fig. 1. Four typical situations of waypoint mutual exclusion. The green small cube represents the waypoint.

Algorithm 1 3 : 4 :

 134 Alternative Waypoint Generating (AWG) Require: An occupied waypoint Ensure: An alternative waypoint 1: if the requested waypoint p is occupied then 2: Find the nearest obstacle point o on the right side of p Calculate the distance d between o and p: d = |po| if d < 2(r + e), where r the radius of the minimum circle to cover the robot with centering at the rotation center of robot, and e a positive number then

Fig. 2 .

 2 Fig. 2. Robot motion trajectory tracing by using the AWG algorithm. The green small cube represents the waypoint.

Fig. 3 .

 3 Fig. 3. Two environment maps used in our simulation: map A (left) and map B (right).

Fig. 4 .

 4 Fig. 4. Exploration time comparison for the map A (top) and the map B (bottom).


Valentin Macé

Christophe Servan

Using Whole Document Context in Neural Machine Translation

In Machine Translation, considering the document as a whole can help to resolve ambiguities and inconsistencies. In this paper, we propose a simple yet promising approach to add contextual information in Neural Machine Translation. We present a method to add source context that capture the whole document with accurate boundaries, taking every word into account. We provide this additional information to a Transformer model and study the impact of our method on three language pairs. The proposed approach obtains promising results in the English-German, English-French and French-English document-level translation tasks. We observe interesting cross-sentential behaviors where the model learns to use document-level information to improve translation coherence.

Introduction

Neural machine translation (NMT) has grown rapidly in the past years [START_REF] Sutskever | Sequence to sequence learning with neural networks[END_REF][START_REF] Vaswani | Attention is all you need[END_REF]. It usually takes the form of an encoderdecoder neural network architecture in which source sentences are summarized into a vector representation by the encoder and are then decoded into target sentences by the decoder. NMT has outperformed conventional statistical machine translation (SMT) by a significant margin over the past years, benefiting from gating and attention techniques. Various models have been proposed based on different architectures such as RNN [START_REF] Sutskever | Sequence to sequence learning with neural networks[END_REF], CNN [START_REF] Gehring | Convolutional sequence to sequence learning[END_REF] and Transformer [START_REF] Vaswani | Attention is all you need[END_REF], the latter having achieved state-of-the-art performances while significantly reducing training time.

However, by considering sentence pairs separately and ignoring broader context, these models suffer from the lack of valuable contextual information, sometimes leading to inconsistency in a translated document. Adding documentlevel context helps to improve translation of context-dependent parts. Previous study [START_REF] Bawden | Evaluating discourse phenomena in neural machine translation[END_REF] showed that such context gives substantial improvement in the handling of discourse phenomena like lexical disambiguation or co-reference resolution.

Most document-level NMT approaches focus on adding contextual information by taking into account a set of sentences surrounding the current pair [START_REF] Tiedemann | Neural machine translation with extended context[END_REF][START_REF] Wang | Exploiting cross-sentence context for neural machine translation[END_REF][START_REF] Jean | Does neural machine translation benefit from larger context?[END_REF][START_REF] Miculicich | Document-level neural machine translation with hierarchical attention networks[END_REF][START_REF] Zhang | Improving the transformer translation model with document-level context[END_REF][START_REF] Voita | Context-aware neural machine translation learns anaphora resolution[END_REF]. While giving significant improvement over the context-agnostic versions, none of these studies consider the whole document with well delimited boundaries. The majority of these approaches also rely on structural modification of the NMT model [START_REF] Jean | Does neural machine translation benefit from larger context?[END_REF][START_REF] Miculicich | Document-level neural machine translation with hierarchical attention networks[END_REF][START_REF] Zhang | Improving the transformer translation model with document-level context[END_REF][START_REF] Voita | Context-aware neural machine translation learns anaphora resolution[END_REF]. To the best of our knowledge, there is no existing work considering whole documents without structural modifications.

Contribution: We propose a preliminary study of a generic approach allowing any model to benefit from document-level information while translating sentence pairs. The core idea is to augment source data by adding document information to each sentence of a source corpus. This document information corresponds to the belonging document of a sentence and is computed prior to training, it takes every document word into account. Our approach focuses on pre-processing and consider whole documents as long as they have defined boundaries. We conduct experiments using the Transformer base model [START_REF] Vaswani | Attention is all you need[END_REF]. For the English-German language pair we use the full WMT 2019 parallel dataset. For the English-French language pair we use a restricted dataset containing the full TED corpus from MUST-C [START_REF] Di Gangi | MuST-C: a Multilingual Speech Translation Corpus[END_REF] and sampled sentences from WMT 2019 dataset. We obtain important improvements over the baseline and present evidences that this approach helps to resolve cross-sentence ambiguities.

Related Work

Interest in considering the whole document instead of a set of sentences preceding the current pair lies in the necessity for a human translator to account for broader context in order to keep a coherent translation. The idea of representing and using documents for a model is interesting, since the model could benefit from information located before or after the current processed sentence.

Previous work on document-level SMT started with cache based approaches, [START_REF] Gong | Cache-based document-level statistical machine translation[END_REF] suggest a conjunction of dynamic, static and topic-centered cache. More recent work tend to focus on strategies to capture context at the encoder level. Authors of [START_REF] Wang | Exploiting cross-sentence context for neural machine translation[END_REF] propose an auxiliary context source with a RNN dedicated to encode contextual information in addition to a warm-start of encoder and decoder states. They obtain significant gains over the baseline.

A first extension to attention-based neural architectures is proposed by [START_REF] Jean | Does neural machine translation benefit from larger context?[END_REF], they add an encoder devoted to capture the preceding source sentence. Authors of [START_REF] Miculicich | Document-level neural machine translation with hierarchical attention networks[END_REF] introduce a hierarchical attention network to model contextual information from previous sentences. Here the attention allows dynamic access to the context by focusing on different sentences and words. They show significant improvements over a strong NMT baseline. More recently, [START_REF] Voita | Context-aware neural machine translation learns anaphora resolution[END_REF] extend Transformer architecture with an additional encoder to capture context and selectively merge sentence and context representations. They focus on co-reference resolution and obtain improvements in overall performances.

The closest approach to ours is presented by [START_REF] Tiedemann | Neural machine translation with extended context[END_REF], they simply concatenate the previous source sentence to the one being translated. While they do not make any structural modification to the model, their method still does not take the whole document into account.

Approach

We propose to use the simplest method to estimate document embeddings. The approach is called SWEM-aver (Simple Word Embedding Model -average) [START_REF] Shen | Baseline needs more love: On simple word-embedding-based models and associated pooling mechanisms[END_REF]. The embedding of a document k is computed by taking the average of all its N word vectors (see Eq. 1) and therefore has the same dimension. Out of vocabulary words are ignored.

Doc k = 1 N N i=1 w i,k (1)
Despite being straightforward, our approach raises the need of already computed word vectors to keep consistency between word and document embeddings. Otherwise, finetuning embeddings as the model is training would shift them in a way that totally wipes off the connection between document and word vectors.

To address this problem, we adopt the following approach: First, we train a baseline Transformer model (noted Baseline model) from which we extract word embeddings. Then, we estimate document embeddings using the SWEM-aver method and train an enhanced model (noted Document model) benefiting from these document embeddings and the extracted word embeddings. During training, the Document model does not fine-tune its embeddings to preserve the relation between words and document vectors. It should be noted that we could directly use word embeddings extracted from another model such as Word2Vec [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF], in practice we obtain better results when we get these vectors from a Transformer model. In our case, we simply extract them from the Baseline after it has been trained.

Using domain adaptation ideas [START_REF] Sennrich | Controlling politeness in neural machine translation via side constraints[END_REF][START_REF] Chu | An empirical comparison of domain adaptation methods for neural machine translation[END_REF][START_REF] Chu | A survey of domain adaptation for neural machine translation[END_REF], we associate a tag to each sentence of the source corpus, which represents the document information. This tag takes the form of an additional token placed at the first position in the sentence and corresponds to the belonging document of the sentence (see Table 1). The model considers the tag as an additional word and replace it with the corresponding document embedding. The Baseline model is trained on a standard corpus that does not contain document tags, while the Document model is trained on corpus that contains document tags.

The proposed approach requires strong hypotheses about train and test data. The first downfall is the need for well defined document boundaries that allow to mark each sentence with its document tag. The second major downfall is the need to compute an embedding vector for each new document fed in the model, adding a preprocessing step before inference time.

Experiments

We consider two different models for each language pair: the Baseline and the Document model. We evaluate them on 3 test sets and report BLEU and TER scores. All experiments are run 8 times with different seeds, we report averaged results and p-values for each experiment.

Translation tasks are English to German, proposed in the first document-level translation task at WMT 2019 [START_REF] Barrault | Findings of the 2019 conference on machine translation (wmt19)[END_REF], English to French and French to English, following the IWSLT translation task [START_REF] Cettolo | The iwslt 2015 evaluation campaign[END_REF].

Training and test sets

Table 2 describes the data used for the English-German language pair. These corpora correspond to the WMT 2019 document-level translation task. Table 3 describes corpora for the English-French language pair, the same data is used for both translation directions.

For the English-German pair, only been augmented with document context. We evaluate the English-German systems on newstest2017, newstest2018 and newstest2019 where documents consist of newspaper articles to keep consistency with the training data. English to French and French to English systems are evaluated over IWSLT TED tst2013, tst2014 and tst2015 where documents are transcriptions of TED conferences (see Table 3).

Prior to experiments, corpora are tokenized using Moses tokenizer [START_REF] Koehn | Moses: Open source toolkit for statistical machine translation[END_REF]. To limit vocabulary size, we adopt the BPE subword unit approach [START_REF] Sennrich | Neural Machine Translation of Rare Words with Subword Units[END_REF], through the SentencePiece toolkit [START_REF] Kudo | Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing[END_REF], with 32K rules.

Training details

We use the OpenNMT framework [START_REF] Klein | OpenNMT: Open-source toolkit for neural machine translation[END_REF] in its TensorFlow version to create and train our models. All experiments are run on a single NVIDIA V100 GPU. Since the proposed approach relies on a preprocessing step and not on structural enhancement of the model, we keep the same Transformer architecture in all experiments. Our Transformer configuration is similar to the baseline of [START_REF] Vaswani | Attention is all you need[END_REF] except for the size of word and document vectors that we set to d model = 1024, these vectors are fixed during training. We use N = 6 as the number of encoder layers, d f f = 2048 as the inner-layer di-mensionality, h = 8 attention heads, d k = 64 as queries and keys dimension and P drop = 0.1 as dropout probability. All experiments, including baselines, are run over 600k training steps with a batch size of approximately 3000 tokens.

For all language pairs we trained a Baseline and a Document model. The Baseline is trained on a standard parallel corpus and is not aware of document embeddings, it is blind to the context and cannot link the sentences of a document. The Document model uses extracted word embeddings from the Baseline as initialization for its word vectors and also benefits from document embeddings that are computed from the extracted word embeddings. It is trained on the same corpus as the Baseline one, but the training corpus is augmented with (see Table 1) and learns to make use of the document context.

The Document model does not consider its embeddings as tunable parameters, we hypothesize that fine-tuning word and document vectors breaks the relation between them, leading to poorer results. We provide evidence of this phenomena with an additional system for the French-English language pair, noted Document+tuning (see Table 5) that is identical to the Document model except that it adjusts its embeddings during training.

The evaluated models are obtained by taking the average of their last 6 checkpoints, which were written at 5000 steps intervals. All experiments are run 8 times with different seeds to ensure the statistical robustness of our results. We provide p-values that indicate the probability of observing similar or more extreme results if the Document model is actually not superior to the Baseline.

Results

Table 4 presents results associated to the experiments for the English to German translation task, models are evaluated on the newstest2017, neswtest2018 and newstest2019 test sets. Table 5 contains results for both English to French and French to English translation tasks, models are evaluated on the tst2013, tst2014 and tst2015 test sets.

En→De: The Baseline model obtained State-of-The-Art BLEU and TER results according to [START_REF] Bojar | Findings of the 2017 conference on machine translation (wmt17)[END_REF][START_REF] Bojar | Findings of the 2018 conference on machine translation (wmt18)[END_REF]. The Document system shows best results, up to 0.85 BLEU points over the Baseline on the newstest2019 corpus. It also surpassed the Baselinee by 0.18 points on the newstest2017 with strong statistical significance, and by 0.15 BLEU points on the new-stest2018 but this time with no statistical evidence. These encouraging results prompted us to extend experiments to another language pair: English-French.

En→Fr: The Document system obtained the best results considering all metrics on all test sets with strong statistical evidence. It surpassed the Baseline by 1.09 BLEU points and 0.85 TER points on tst2015, 0.75 BLEU points and 0.76 TER points on tst2014, and 0.48 BLEU points and 0.68 TER points on tst2013.

Fr→En: Of all experiments, this language pair shows the most important improvements over the Baseline. The Document+tuning system, which only differs from the fact that it tunes its embeddings, shows little or no improvement over the Baseline, leading us to the conclusion that the relation between word and document embeddings described by Eq. 1 must be preserved for the model to fully benefit from document context.

Manual Analysis

In this analysis we present some of the many cases that suggest the Document model can handle ambiguous situations. These examples are often isolated sentences where even a human translator could not predict the good translation without looking at the document, making it almost impossible for the Baseline model which is blind to the context. Table 6 contains an extract of these interesting cases for the French-English language pair.

Translation from French to English is challenging and often requires to take the context into account. The personal pronoun "lui" can refer to a person of feminine gender, masculine gender or even an object and can therefore be translated into "her", "him" or "it". The first example in Table 6 perfectly illustrate this ambiguity: the context clearly indicates that "lui" in the source sentence refers to "ma fille", which is located three sentences above, and should be translated into "her". In this case, the Baseline model predict the personal pronoun "him" while the Document model correctly predicts "her". It seems that the Baseline model does not benefit from any valuable information in the source sentence. Some might argue that the source sentence actually contains clues about the correct translation, considering that "robe à paillettes" ("sparkly dress") and "baguette mag-ique" ("magic wand") probably refer to a little girl, but we will see that the model makes similar choices in more restricted contexts. This example is relevant mainly because the actual reference to the subject "ma fille" is made long before the source sentence.

The second example in Table 6 is interesting because none of our models correctly translate the source sentence. However, we observe that the Baseline model opts for a literal translation of "je peux faire le poirier" ("I can stand on my head") into "I can do the pear" while the Document model predicts "I can wring". Even though these translations are both incorrect, we observe that the Document model makes a prediction that somehow relates to the context: a woman talking about her past disability, who has become more flexible thanks to yoga and can now twist her body.

The third case in table 6 is a perfect example of isolated sentence that cannot be translated correctly with no contextual information. This example is tricky because the word "Elle" would be translated into "She" in most cases if no additional information were provided, but here it refers to "la conscience" ("consciousness") from the previous sentence and must be translated into "It". As expected the Baseline model does not make the correct guess and predicts the personal pronoun "She" while the Document model correctly predicts "It". This example present a second difficult part, the word "son" from the source sentence is ambiguous and does not, in itself, inform the translator if it must be translated into "her", "his" or "its". With contextual information we know that it refers to "[le] monde physique" ("[the] physical world") and that the correct choice is the word "its". Here the Baseline incorrectly predicts "her", possibly because of its earlier choice for "She" as the subject. The Document model makes again the correct translation.

According to our results (see Table 5), the English-French language pair also benefits from document-level information but to a lesser extent. For this language pair, ambiguities Il a dit : "Vous avez écouté." Baseline Il a dit : "Tu as écouté." Document Il a dit : "Vous avez écouté." Table 7: Translation example for the English-French pair. about personal pronouns are less frequent. Other ambiguous phenomena like the formal mode (use of "vous" instead of "tu") appear. Table7 presents an example of this kind of situation where the word "You" from the source sentence does not indicate if the correct translation is "Vous" or "Tu". However it refers to the narrator of the story who is an old police officer. In this case, it is very likely that the use of formal mode is the correct translation. The Baseline model incorrectly predicts "Tu" and the Document model predicts "Vous".

Conclusion

In this work, we presented a preliminary study of a simple approach for document-level translation. The method allows to benefit from the whole document context at the sentence level, leading to encouraging results. In our experimental setup, we observed improvement of translation outcomes up to 0.85 BLEU points in the English to German translation task and exceeding 1 BLEU point in the English to French and French to English translation tasks. Looking at the translation outputs, we provided evidence that the approach allows NMT models to disambiguate complex situations where the context is absolutely necessary, even for a human translator.

The next step is to go further by investigating more elaborate document embedding approaches and to bring these experiments to other languages (e.g.: Asian, Arabic, Italian, Spanish, etc.). To consider a training corpus with a majority of document delimited data is also very promising.

Table 1 :

 1 Example of augmented parallel data used to train the Document model. The source corpus contains document tags while the target corpus remains unchanged.

	SOURCE	TARGET
	<doc1> Pauli is a theoretical physicist	Pauli est un physicien théoricien
	<doc1> He received the Nobel Prize	Il a rec ¸u le Prix Nobel
	<doc2> Bees are found on every continent	On trouve des abeilles sur tous les continents
	<doc2> They feed on nectar using their tongue Elles se nourrissent de nectar avec leur langue
	<doc2> The smallest bee is the dwarf bee	La plus petite abeille est l'abeille naine

Table 2 :

 2 Detail of training and evaluation sets for the English-German pair, showing the number of lines, words in English (EN) and words in German (DE). Corpora with document boundaries are denoted by †.

	10.4% (3.638M lines)

Table 3 :

 3 Detail of training and evaluation sets for the English-French pair in both directions, showing the number of lines, words in English (EN) and words in French (FR). Corpora with document boundaries are denoted by †.

Table 4 :

 4 Results obtained for the English-German translation task, scored on three test sets using BLEU and TER metrics. p-values are denoted by * and correspond to the following values: * < .05, * * < .01, * * * < .001. * * 33.80 * * * 44.46 * * * 36.34 * * * 41.72 * * * 38.04 * * *

	The

*

Table 5 :

 5 Results obtained for the English-French and French-English translation tasks, scored on three test sets using BLEU and TER metrics. p-values are denoted by * and correspond to the following values: * < .05, * * < .01, * * * < .001. Document model obtained substantial gains with very strong statistical evidence on all test sets. It surpassed the Baseline model by 1.81 BLEU points and 1.02 TER points on tst2015, 1.50 BLEU points and 0.96 TER points on tst2014, and 1.29 BLEU points and 0.83 TER points on tst2013.

Table 6 :

 6 Fr-En Context [...] et quand ma fille avait quatre ans, nous avons regardé "Le Magicien d'Oz" ensemble. Ce film a complètement captivé son imagination pendant des mois. Son personnage préféré était Glinda, bien entendu. Source C ¸a lui donnait une bonne excuse pour porter une robe à paillettes et avoir une baguette magique. Ref. It gave her a great excuse to wear a sparkly dress and carry a wand. Baseline It gave him a good excuse to wear a glitter dress and have a magic wand. Document It gave her a good excuse to wear a glitter dress and have a magic wand. Context C'est le but ultime de la physique : décrire le flux de conscience. Selon cette idée, c'est donc la conscience qui met le feu aux équations. Selon cette idée, la conscience ne pendouille pas en dehors du monde physique ... Translation examples for the French-English pair. We took the best models of all runs for both the Baseline and the Document enhanced model The speaker in this example is an old police officer saving a man from suicide] But I asked him, "What was it that made you come back and give hope and life another chance ?" And you know what he told me ? Source He said "You listened." Ref.

		Mon père passait souvent les grandes vacances à essayer de me guérir ...
	Context	Mais nous avons trouvé un remède miracle : le yoga.
		[...] j'étais une comique de stand-up qui ne tenait pas debout.
	Source	Maintenant, je peux faire le poirier.
	Ref.	And now I can stand on my head.
	Baseline	Now I can do the pear.
	Document Now, I can wring.
	Source	Elle siège bien en son coeur.
	Ref.	It's there right at its heart.
	Baseline	She sits well in her heart.
	Document It sits well in its heart .
	En-Fr
		[
	Context


Chloé Artaud

Nicolas Sidère

Antoine Doucet

Jean-Marc Ogier

Vincent Poulain D'andecy
email: vincent.poulaindandecy@yooz.fr

Find it! Fraud Detection Contest Report

This paper describes the ICPR2018 fraud detection contest, its data set, evaluation methodology, as well as the different methods submitted by the participants to tackle the predefined tasks. Forensics research is quite a sensitive topic. Data are either private or unlabeled and most of related works are evaluated on private datasets with a restricted access. This restriction has two major consequences: results cannot be reproduced and no benchmarking can be done between every approach. This contest was conceived in order to address these drawbacks. Two tasks were proposed: detecting documents containing at least one forgery in a flow of documents and spotting and localizing these forgeries within documents. An original dataset composed of images and texts of French receipts was provided to participants. The results they obtained are presented and discussed.

I. INTRODUCTION

In the last decades, the explosion of the volume of digital document images and the development of consumer tools to forge these images has led to a huge increase in the number of corrupted documents. The development of many tools and methods to detect modifications has also increased but benchmarking remains a challenge.

With all the benefits it comes with, development of technologies has also an important side effect. For instance, number of amateur fraudsters has increased. Actually, it is quite accessible for many people to scan any document (payslip, bill, etc. ), modify one or several critical field (name, date, amount of money, etc. ) and print it with common devices and basic softwares (MS Paint, Gimp, etc. )

For institutions and companies, fraud can be considered as a real plague as shown by the many studies that were undertaken during previous years. A first one conducted in 2016 by Price Waterhouse Coopers reveals that 36% of the 5125 companies are victims of frauds. The estimated economic cost exceeds 50k$ for 53% of the surveyed companies. Beyond this financial cost, the reduction of the employees' motivation and, the cost on the company's relations with the public and its partners are major collateral damage directly impacting the company's trust capital. ICAR had a study conducted on banking fraud in Spain stating that almost half of Spanish users have experienced attempts to defraud. Out of the victims of successful fraud, 33% of them did not recover the money they lost and frauds cost on average 218 for each of them. In one hand, all these studies show the necessity to act in fraud prevention and detection. But on the other hand, as far as we Fig. 1. Genuine receipt know, no contest is organized on fraudulent documents and not so many studies are leaded on this topic. We hope that this contest will help to make the focus on this domain.

If these figures present fraud in a global way, one cant ignore frauds on documents. Because they can be easily modified with common and usual tools, frauds on documents have seriously increased. For instance, a dishonest person can be easily attempted to modify amount of purchases on types of document admitted as evidence, such as invoices or receipts, in order to earn more money from insurance in case of theft or fire. Receipts can also be provided as expense report by employees. We can imagine there are cases of falsifications of name of purchased products, to respect constraints of reimbursement, or of the address of restaurant to prove the presence at the good place. For all these reasons, we choose for this contest to focus on this type of documents.

Recent research in document forensics are mostly focused on the analysis of images of documents. However, we believe that Natural Language Processing (NLP) and Knowledge Engineering (KE) could be used to improve the performance of fraudulent document detection. Document is not only an image: it contains textual information that can be processed, analyzed and verified. The aim of this contest proposal is to provide an Image-Text parallel corpus and an unique benchmark to test and evaluate image-based and text-based methods.

II. DATASET

A. Corpus Collection

From December 2016 to June 2017 we collected around 2,500 documents by asking members of the L3i laboratory, families and friends. After removing receipts which are not French, not anonymous, not readable, scribbled or too long, we captured 1969 images of receipts. To have the best workable Fig. 2. Fake receipt images, we captured receipts with a fixed camera in a black room with floodlight. Receipts were placed under a glass plate to be flattened. Each photography contained several receipts, and we extracted and straightened each one of them to obtain one receipt per document. The resolution of these images is 300 dpi.

The size of images differs because of the nature of receipts: it depends both on the number of purchases and on the store that provides the receipt. The dataset contains very different receipts, from different stores or restaurants, with different fonts, sizes, pictures, barcodes, QR-codes, tables, etc. There is a lot of noise due to paper type, the print process and the state of the receipt, as they are often crumpled in pockets or wallets and generally handled with little care. Noises can be folds, dirts, rips. Ink is sometimes erased, or badly printed. This is a very challenging dataset for document image analysis.

To extract text from images, we applied Abbyy Finereader 11s Optical Character Recognition engine. Since image quality is not perfect, so are the OCR results. We automatically corrected the most frequent errors, such as symbols at the end of lines or G characters (for grammes) after sequences of 2 or 3 digits. Then, we proposed an online participative platform to correct OCR results and get a sound ground truth. The crowdsourcing of the human correction is still in progress.

B. Alteration

This parallel dataset of images and texts is intended to undergo realistic forgeries. By realistic forgeries, we mean modifications that could happen in real life, as in the case of insurance fraud when fraudsters declare a more expensive price than true for objects that were damaged or stolen. We need to get realistic falsifications (price raises, changes of product titles, hotel address changes, etc.). Synthesizes this step, by an automatic algorithm that randomly changes some characters for instance, would mechanically induce a bias that we absolutely wanted to avoid. From this statement, the only way to meet the previous criteria is to organize workshops with volunteers to become one-day fraudsters. To increase the diversity of quality and precision of forgeries, workshops are open to PhD students and postdocs from various labs with various skills with image tools. To have a representative sample of real-like fraudsters, it is quite important not to restraint this job only to members of our computer science lab but to enlarge the scope of our project to a non-expert public, at least people who are not used to work with digital documents or image processing tools.

As we said, the aim of these workshops is to try to reproduce real forgeries in real conditions of fraudsters. All fraudulent acts are made using common and widespread material or tools, ie. a standard computer equipped with Windows 10 and several image editing softwares, at the users choice. For each receipts, image and text was modified simultaneously. We obtained 250 altered receipts, containing several types of modification, on all receipt information.

C. Corpus of the training phase

Data to process was organized as a set of couples image and text files :

• An image file formatted in png, representing one receipt that can contain one or several forgeries • A text file containing a textual transcription of the content of the receipt Participants can use only images, only texts, or both images and texts.

For the first task, we provided a set of 500 documents, containing 6% of altered documents. An XML file of groundtruth shows the name of the documents and whether they are genuine or fraudulent.

For the second task, we provided 100 altered document (images and texts), with 2 XML files defining ground truth:

• For images, the XML file contains the coordinates of each modification, as follows: x and y are horizontal and vertical coordinates of the top-left point of the rectangle bounding box that have height and width. All measurements are in pixels. • For texts, XML file contains the tokens, delimited by spaces in the text file, that are forged and the line and the column where they are located. If the whole line is modified (or append), the forged value contains the complete line. If the forged value is empty, it means that information has been deleted. There was no overlap in the fraudulent documents between the corpus of Task 1 and the corpus of Task 2, so participants could add the 100 documents from Task 2 to improve learning in Task 1.

D. Evaluation tools

We provided to participants three tools to help them to train their algorithms:

• EvalT1.py evaluates the detection of modified documents among others in a set of documents containing both genuine and modified documents. The evaluation script produces a CSV file with the Precision, Recall and FMeasure results, and, for their information, the ID of each receipt and its status (True Negative, False Negative, True Positive, False Positive). • EvalT2-img.py evaluates the spotting of one or several modifications in a set of document images. The evaluation script produces a CSV file with, for each receipt, its name and the Jaccard index between the set of pixels covered by their localization results and those of the Groundtruth.

• EvalT2-img.py evaluates the spotting of one or several modifications in a document OCR output (text file).

The evaluation script produces a CSV file with, for each receipt, its name, and 3 measures of Jaccard index corresponding to 3 different sets:

set of the lines covered by their localization results, set of the lines and column covered by their localization results, set of the lines, column and length of token covered by their localization results. This choice is due to the complexity to localize a fake information in a line, and leave the possibility to have a less severe metric.

E. Corpus of the test phase

The corpus provided for the test phase of task 1 respected the same proportions as that of the training phase, i.e. 30 false documents out of 500 (6%).For the corpus of Task 2, we provided only 80 false documents.

Participants had to send us an XML file with their results and we calculate their scores.

III. SUBMITTED METHODS

In total, 36 teams registered to the competition. 5 of them submitted results to Task 1, while only 2 did so for Task 2. The following subsections provide the descriptions written by participants to describe the approaches they experimented to tackle the first task.

A. Fabre

We combined deep-learning with fraud detections techniques to achieve more than 85% good guesses. We did not however directly fed our network with the genuine images. We pre-processed them before with Tampered Image Detection methods. We tried a few, but the best result were done by combining: "Error Level Analysis", "Discret Wavelet Transform" and "Grayscale" images. We then fed the three dimensions matrices, of the three methods, to a well known deep neural network, Resnet152.

B. Clausner

The CFraudChecker consists of nine check modules, each looking at a specific type of fraud. Each module returns a fraud likelihood value between 0 and 1. The method reports a detection if the sum of all values is greater or equal to 1. Therefore, fraud is detected if either one module is very confident or multiple modules return a small value. Text-based modules:

• Price variation check: Looks for price outliers • Total to pay check: Looks at inconsistencies in article prices and the total to pay • Missing text check: Looks for keywords which imply a specific piece of information, but that information is missing • Discounts check: Looks for inconsistencies in discounts

• Quantities check: Looks for inconsistencies in Quantity * Article = Sum • Date check: Looks for invalid dates Image-based modules (using OpenCV):

• Colour check: Looks for unnatural saturation, blackness, or pepper noise • Erased parts check: Looks for unnatural white areas or large homogeneous areas (which have no noise) • Copy + paste check: Looks for identical copies of connected components in binarised image A challenge was the noisy textual input data (partially corrected OCR output). A basic text normalisation is performed (remove spaces in prices, fix decimal points etc.) but this can be extended to cover more inconsistencies. The free parameters were tuned manually but this can be automated in future.

C. Verdoliva

We have implemented fusion strategies for both the detection and localization tasks.

We use three methods for detection task:

• CMFD. The first method has been recently proposed by our team [START_REF] Cozzolino | Efficient dense-field copymove forgery detection[END_REF] for copy-move forgery detection but can be also applied to detect inpainting-based manipulations. • Noiseprint. The second method extracts a camera signature, called Noiseprint [START_REF] Cozzolino | Noiseprint: a cnn-based camera model fingerprint[END_REF], [START_REF] Cozzolino | Camera-based image forgery localization using convolutional neural networks[END_REF], through a deep net which removes the high-level image content. If the image has been tampered with, an anomaly arises which can be discovered by comparing the image Noiseprint with a reference Noiseprint extracted from a set of pristine images. • StegoFeatures. The third method, proposed in [START_REF] Cozzolino | Image forgery detection through residual-based local descriptors and block-matching[END_REF], performs forgery detection based on local image features and linear SVM classification. The local features, originally proposed in steganalysis [START_REF] Fridrich | Rich models for steganalysis of digital images[END_REF], capture expressive micropatterns in the high-pass filtered image. Fusion. An image is declared forged if at least one method detects a manipulation.

D. Zampoglou

Our submission was based on steganographic features extracted from the entire image and used to train an SVM classifier ensemble to discriminate between tampered and untampered images. Steganographic features have demonstrated strong performance in similar challenges in the past [START_REF] Cozzolino | Image forgery detection through residual-based local descriptors and block-matching[END_REF]. In [START_REF] Cozzolino | Image forgery detection through residual-based local descriptors and block-matching[END_REF], a set of steganographic filters are passed over the image, and a co-occurence matrix descriptor is formed for the entire filtered image. [START_REF] Fridrich | Rich models for steganalysis of digital images[END_REF] presented a set of 39 filters. In the approach of Cozzolino et al, each filter is evaluated via cross-validation, and the features produced by the most successful filters are concatenated into a final classifier.

We followed a similar approach, where we used crossvalidation on the training set to find the most successful filters from [START_REF] Fridrich | Rich models for steganalysis of digital images[END_REF] for the dataset, but instead of concatenating we trained individual classifiers for each filter feature, and the final result is produced by majority voting over all individual classifier outputs. The steganographic filters from Fridrich et al are that demonstrated the best performance in cross-validation are:

• s5x5 spam14hv q1 • s5x5 minmax22v q1 • s3x3 minmax22v q1 • s3x3 minmax24 q1 • s3 spam14hv q1 • s3 minmax34v q1 • s3 minmax22v q1 • s2 spam12hv q1 • s1 spam14hv q1
Each model is trained using bagging. The output for each model is calculated by averaging all bag outputs, and the final result is drawn using majority voting over all the models.

E. Cruz

This method aims at detecting parts of document image that are duplicated, for instance in case of modification of a string by copy-pasting some characters. Based on some previous works applied on natural scene images ([?]), developped method is based on the discrete cosine transform (or DCT). DCT is often used in image compression algorithm because of its abality of projecting an image (or part of image) with excellent properties of grouping energy level, and consequently allows to held major informations on only few coefficients. In our algorithm, we use this property to detect and identify areas of image with similar coefficients meaning a identical information.

IV. RESULTS AND DISCUSSION

A. Detection Task

To calculate the candidates scores for the first task, we used the usual metrics for classification: precision, recall and fmeasure.

Some of our candidates used Machine Learning algorithms. The first results they submitted were based from algorithms that had been trained on the learning corpus of Task 1 to which they had added the fraudulent documents from Task 2. This corresponds to 130 false documents for 470 true documents, that is about 22%, instead of 30 false documents out of a total of 500 (6%). This was not prohibited, so we asked participants to re-train their model only on the learning corpus of Task 1.

Table I presents the results obtained by the different participants, with and without the documents of Task 2 included in the learning process. Zampoglou send us two results : the first uses identical settings to his original full run, while the second uses a more representative class balancing during training to account for the reduction of tampered training samples.

The last result in Table I shows a perfect detection score: the method used finds the 30 fraudulent documents perfectly. This surprising result is certainly due to the fact that the corpus is very specialized. Indeed, the documents were all scanned by the same camera, with almost identical parameters. It would therefore be interesting to see whether this method obtains equivalent scores on a corpus made up of images from different cameras under different lighting and inclination conditions. We can cite the use of smartphones, for example, to scan cash register receipts, as part of applications for reimbursing mission expenses or fidelity accounts.

B. Human Baseline

In order to compare these results to a human baseline, we asked 5 people to detect false documents on the test corpus of Task 1. To do this, an interface provided them with a receipt image of the test corpus and they had to click on the "true" or "false" button, which allowed them to display the following image. Each annotator processed the 500 images in the corpus, proposed in a random order, knowing the rate of fraudulent documents in this corpus. The annotators had several days to process the entire corpus, and had feedback on their results and those of the other annotators at mid-term. Table II shows their Precision, Recall and F-measure scores.

These scores show that it is difficult for a non-specialist human to detect a false document (many false negatives, hence a low recall), and that many documents appear suspicious even though they are authentic (many false positives, hence low precision).

We observe that the average processing time of a sales receipt under these conditions is 20 seconds per ticket, being concentrated on this single task. Indeed, beyond the quick inspection to detect visible anomalies (characters of an abnormal color or font, strange streaks...), the annotators checked if the information was coherent between them (sums of the prices corresponding to the total and the payment, good number of displayed articles, etc.) and if there was no aberrant information.

Of the 500 documents in the corpus, the annotators do not agree on the authenticity of 49 of them. In addition to this, they are all wrong about the classification of 9 other of these 500 receipts (all false negatives, i.e. undetected forged documents). We also calculated the Fleiss Kappa between our annotators, which is 0.4375. This measure is used to calculate the inter annotator agreement and is in an interval of 0 to 1. The Kappa in this case shows that the four annotators only moderately agree on the frauds they detect. In other words, some see fraud where others do not.

C. Forgeries Types

The test corpus of Task 1 contained on average 3.7 alterations on the image, which corresponds to 3.5 frauds on the text transcriptions. These modifications on the images were made using 4 procedures :

• CPI (copy and paste inside the document)

• CPO (copy and paste from an other document)

• IMI (creation of a text box imitating the font) • CUT (deletion of one or more characters/words) Table III shows the types of changes made to the image the false documents.

A detailed comparison of our candidates' results shows that the errors of classification do not concern the same documents. Indeed, all false documents were detected by at least two methods and raised false positives were by only one method. Thus, 70 documents are misclassified by only one candidate, 8 by 2 candidates and 3 by 3 candidates. The latter 3 were also misclassified by 5, 4 and 2 humans respectively. They contain CPI+CUT fraud types for two of them and CPI+IMI for the last one. We can also observe that 5 false documents are perfectly detected as false by the 5 candidates methods, when one of them isn't by four of the five humans.

V. SECOND TASK

The second task of our contest brought together only two participants: Clausner and Verdoliva. If this does not really make it possible to compare the results, it seemed important to us to reward the effort of these two participants by presenting them all the same. The second task was to locate forgeries in documents. The methods used are as follows:

a) Clausner: Each check module [presented in III.B.] adds fraud areas to a shared binary image. Then, the bounding boxes of connected components in that image are reported as fraud. The text-based modules make use of a Tesseract OCR result to match the given input text with OCR output (which has location data). We evaluate these results by a Jaccard index between the set of pixels found and the set of pixels of our field truth for each document. Table 4 therefore presents the mean and standard deviation of the coefficients taking into account all the documents, as well as the mean and standard deviation of the indexes which are not equal to 0, i.e. documents where fraud has been at least a little located.

VI. CONCLUSION

One of the main lessons of this contest is the low number of participants compared to the number of registered and interested persons. We explain this by the low state of the art scores of most known methods of Forgeries Detection compared to the results presented in the first Image Forensics Challenge organized in 2013 by the IEEE Signal Processing Society and presented in WIFS 2014. Indeed, we believe that some registered people preferred not to submit their results.

Another lesson concerns the preponderance of image-based methods over text-based methods. Indeed, as the receipts are not in natural language and have various structures, it is complicated to extract features for the Machine Learning methods. Moreover, the corpus is in French, which does not help international linguists extract information to process it effectively.

In conclusion, we can say that the received results show that the task of detecting false documents on this corpus is a solved problem thanks to computer vision features. Nevertheless, the fine detection of frauds, and their location in documents, is not so obvious, as shown by the few results received for the second task and the partial location of frauds.

The excellent results of two participants for the first task lead us to think that it would be interesting to propose a more complex corpus to treat, which would perhaps reduce the possible biases of our corpus. Indeed, perfectionist fraudsters could try to print the image and re-scan it, which would probably change the results of the proposed approaches. We are also thinking of extending the corpus with images taken by other cameras than the one used for the captures and other shooting parameters, which would perhaps complicate the detection of anomalies in the corpus.

  Besides CMFD and Noiseprint [presented in III.C.], we use a further method, proposed in[START_REF] Bianchi | Improved dct coefficient analysis for forgery localization in jpeg images[END_REF], which exploits double JPEG compression artifacts. Fusion. If double compression is detected, the related localization map is used without further information, as it is very reliable. Else, if only CMFD or only Noiseprint detect a forgery, the corresponding map is used. Else, if both CMFD and Noiseprint detect a forgery, we keep the connected components of the CMFD map which overlap the Noiseprint map.

		TABLE IV
	RESULTS OF TASK 2
	Candidate	Mean Standard Deviation
	Clausner	0,091	0,222
	Verdoliva	0,426	0,261
	Clausner without 0	0,287	0,315
	Verdoliva without 0	0,461	0,240
	b) Verdoliva:

ACKNOWLEDGMENT

We would like to thank the participants of this competition for their motivation and cooperation. We would also like to thank all those who participated in the creation of this corpus, whether for the collection of receipts, for the correction of OCR outputs, for the falsification of documents, or for the manual detection of false documents in the test corpus. Without them, neither the corpus nor the competition could have existed.


Takwa Attia

Martin Heusse

Bernard Tourancheau

Andrzej Duda

Experimental Characterization of LoRaWAN Link Quality

Keywords: LoRa, LoRaWAN, Packet Reception Rate

In this paper, we present the results of extensive experiments on a testbed in the The Things Network (TTN), a public LoRa network. We evaluate the transmission quality of LoRa links by measuring the Packet Reception Rate (PRR) as a function of the payload length.

The results show that there is only a slight impact of the payload length on PRR, which means that the bit error rate does not strongly influence the probability of packet reception. Our measurements show that the LoRa channel behaves like a slow fading Rayleigh channel, which translates into probability Ps of being (or not) in a favorable condition for each frame reception: once the frame preamble is received, there is great chance that the whole frame is correctly received. Probability Ps depends on the Spreading Factor and the Signal to Noise Ratio, and often becomes a dominant factor of successful reception depending on the signal strength at a gateway.

I. INTRODUCTION

The LoRa technology is gaining an increasing interest from both academia and industry. It perfectly addresses the Internet of Things (IoT) needs for a Low Power Wide Area Network (LPWAN) able to provide connectivity to a wide area with a large number of IoT devices. It defines a specific radio layer based on the Chirp Spread Spectrum (CSS) modulation [START_REF] Berni | On the Utility of Chirp Modulation for Digital Signaling[END_REF], much different from the modulations used in other types of wireless networks. The LoRa CSS modulation results in good sensitivity levels enabling transmissions over long distances: a range of several kilometers outdoors and hundreds of meters indoors.

LoRaWAN [START_REF] Sornin | LoRaWAN 1.1 Specification[END_REF] defines an access method to the radio channel similar to ALOHA: a device wakes up and sends a packet to the gateway right away. This choice of the access method highly impacts the quality of transmissions in terms of Packet Reception Rate (PRR) and scalability to a large number of devices.

Like for any new emerging technology, it is crucial to investigate its performance in terms of transmission quality and ability to scale. Many authors addressed the issue of evaluating LoRa performance and scalability with analytical modeling [START_REF] Mikhaylov | Analysis of Capacity and Scalability of the LoRa Low Power Wide Area Network Technology[END_REF], [START_REF] Georgiou | Low Power Wide Area Network Analysis: Can LoRa Scale?[END_REF], simulation [START_REF] Reynders | Range and Coexistence Analysis of Long Range Unlicensed Communication[END_REF]- [START_REF] To | Simulation of LoRa in NS-3: Improving LoRa Performance with CSMA[END_REF], or measurements [START_REF] Augustin | A Study of LoRa: Long Range & Low Power Networks for the Internet of Things[END_REF], [START_REF] Haxhibeqiri | LoRa Scalability: A Simulation Model Based on Interference Measurements[END_REF], [START_REF] Petrić | Measurements, Performance and Analysis of LoRa FABIAN, a Real-World Implementation of LPWAN[END_REF]- [START_REF] Blenn | LoRaWAN in the Wild: Measurements from The Things Network[END_REF]. In previous work, we designed WiSH-WalT, a framework for controllable and reproducible LoRa testbeds [START_REF] Lone | WiSH-WalT: A Framework for Controllable and Reproducible LoRa Testbeds[END_REF]. WiSH-WalT enables easy configuration of motes with several configuration parameters and running measurement experiments. We began to investigate how the quality of reception depends on the main LoRa configuration parameters: Spreading Factor (SF) and Transmission Power (TP) [START_REF] Lone | WiSH-WalT: A Framework for Controllable and Reproducible LoRa Testbeds[END_REF].

In this paper, we report on the results of extensive experiments on the WiSH-WalT testbed in The Things Network (TTN), a public LoRa network [START_REF] Giezeman | The Things Network[END_REF] during several months. The goal of these experiments is to characterize the transmission quality of LoRa links by measuring PRR as a function of the payload length. Several factors may impact PRR and we wanted to evaluate how they influence the probability of correct frame reception.

Our main finding is that there is only a slight impact of the payload length on PRR, which means that the bit error rate does not strongly influence the probability of packet reception. Successful reception rather depends on favorable conditions for receiving the whole frame (the preamble, the header, and the payload): no collisions as well as no strong attenuation during the transmission so that preamble detection and time synchronization succeeds at the gateway and successful packet reception ensues. Our measurements show that the LoRa channel behaves like a slow fading Rayleigh channel-each transmission faces an exponentially distributed Rayleigh channel gain that remains mostly constant during the transmission. We quantify successful reception with probability P s of being (or not) in a favorable condition for each frame reception: once the frame preamble is received, there is great chance that the whole frame is correctly received. We estimate probability P s and show that it depends on SF and Signal to Noise Ratio (SNR), and often becomes a dominant factor of successful reception depending on the signal strength at a gateway.

These findings have important implications for LoRaWAN application designers: to achieve high levels of data delivery, devices need to consider packet retransmissions because they have to cope with frame losses not only due to the ALOHA access method, but also to the channel variability. As larger frames have similar PRR as smaller ones, retransmitting data aggregated in larger frames is not only more efficient in terms of overhead, but it also significantly improves the data delivery rate, as long as the duty cycle limit is met.

In the rest of the paper, we describe the basics of LoRa networks (Section II), present our testbed (Section III), and report on the results of our experiments (Section IV). In Section V, we analyze the PRR anomaly, relate it to the probability of failed receiver synchronization, and present measurements showing its dependence on SF and SNR. Finally, we briefly discuss related work (Section VI) and draw some conclusions (Section VII).

II. LORA AND LORAWAN BASICS

LoRa is a wireless modulation based on the principle of Chirp Spread Spectrum (CSS) [START_REF] Berni | On the Utility of Chirp Modulation for Digital Signaling[END_REF]. CSS consists of cyclic frequency varying chirps that encode bits of information. It requires strong temporal synchronization to reach a good decoding level (we discuss this issue in Section V).

We can control the physical layer of LoRa through the following parameters [START_REF] Semtech | SX1272/73 -860 MHz to 1020 MHz Low Power Long Range Transceiver[END_REF]:

• Bandwidth (BW): it is the range of transmission frequencies. We can configure the bandwidth between 7.8 kHz and 500 kHz. Larger bandwidth allows for a higher data rate, but results in lower sensitivity. A LoRa frame starts with a preamble followed by an explicit header, a payload, and CRC [START_REF] Semtech | SX1272/73 -860 MHz to 1020 MHz Low Power Long Range Transceiver[END_REF] (see Figure 1). The preamble length is programmable and takes values from 10 to 65,536 symbols in total (by default, 12 symbols). In explicit mode, the explicit header contains information about the payload: length, CR, and the information whether CRC is used.

LoRaWAN is a MAC protocol proposed by the LoRa Alliance [START_REF] Sornin | LoRaWAN 1.1 Specification[END_REF] over the physical layer based on the LoRa modulation. It defines the network architecture, the radio access method, and the MAC frame structure. LoRaWAN defines a star topology network composed of end devices and gateways connected through the Internet to a network server. For class A devices (those that may achieve long lifetimes through the use of low duty cycles), LoRaWAN defines an access method similar to ALOHA: a device wakes up and sends a packet on a chosen radio channel. One or several gateways nearby can receive the packet and forward it further on to a network server. The difference with pure ALOHA is the variable packet length in LoRaWAN. End devices have to respect the regulatory restrictions with a duty cycle of less than e.g. 1% in each of the European (EU) 868 MHz bands.

This choice of a simple access method highly impacts the reliability of LoRaWAN and its scalability to a large number of devices-the well-known theoretical channel utilization for ALOHA with fixed packet sizes is around 18% (1/e). It results in a high level of packet loss due to collisions as the number of devices increases. Even if we take into account the capture effect 1 , which increases the packet reception probability in case of collisions, the access method strongly limits the capacity of the network to scale.

III. TESTBED AND EXPERIMENTAL SETUP

Our testbed consists of five STMicroelectronics motes [START_REF] Stmicroelectronics | B-L072Z-LRWAN1[END_REF] that operate under the WiSH-WalT framework [START_REF] Lone | WiSH-WalT: A Framework for Controllable and Reproducible LoRa Testbeds[END_REF] in the TTN network, an open source free-of-charge LoRa network. Its gateways forward traffic to the EU TTN server from which we collect data for characterizing transmission quality. WiSH-WalT enables easy configuration of motes with several parameters and running experiments. Each gateway performs a CRC check: if CRC is valid, the gateway forwards the packet to the TTN server, otherwise, it drops the packet. The number of gateways correctly decoding a given packet mainly depends on SF of each transmission, since higher SF trades data rate for transmission quality to reach larger distances. Up to 13 gateways were receiving the traffic from our motes.

We ran a background script that saves all generated traffic through an MQTT client. A mote periodically sends packets while varying the payload length (PL) from 0 to PL max with 1% of duty cycle and respecting the limitations given in Table I. We performed experiments in three configurations:

• CONF-A: SF = 9, TP = 14 dBm, and we vary the payload length from 0 to 120 bytes. • CONF-B: same as CONF-A, but we alternate between TP = 10 dBm and TP = 2 dBm. 1 The capture effect refers to the capacity of correctly receiving a significant fraction of colliding frames [START_REF] Kochut | Sniffing Out the Correct Physical Layer Capture Model in 802.11b[END_REF].

Gw1 Gw2 Gw3 Gw4 Gw5 Gw6 Gw7 Gw8 (b)
Figure 2: a) PRR vs. frame size for SF9, TP = 14 dBm. b) log(PRR) vs. frame size for SF9.

• CONF-C: TP = 14 dBm, we vary the payload length from 0 to 55 bytes, and alternate between SF = 11, SF = 9, and SF = 7. We set BW to 125 kHz and CR to 4/5 in all configurations. Table II gives, when available based on the GPS location, the altitude of the gateways collecting packets during the experiments and the distance from our motes to them. We number the gateways in the order of the reception quality to make the figures more readable.

IV. EXPERIMENTAL RESULTS

Packet Reception Rate (PRR) is a key metric that measures the reliability of transmissions. Figure 2a presents PRR as a function of the frame size for CONF-A. Notice that a mandatory explicit LoRaWAN frame header of 13 bytes is added to the frame-this is why we plot the result as a function of the frame size observed at gateways.

We can notice that the PRR curves are almost flat, which demonstrates only a slight impact of PL on the frame reception. The important finding is the anomaly of the curves that do not tend to 1 for the frame size going to 0, which is unexpected on a wireless channel. To observe the shape of the curves better, Figure 2b presents the same data in the log scale with a linear regression function to show the limit behavior of PRR when the frame size goes to 0. We provide more in-depth analyses of this behavior in Section V.

We also notice that the shape of PRR curves is slightly different for each gateway depending on its position as described in Table II, which strongly impacts channel quality. Moreover, although the distance that separates our mote from both Gw1 and Gw2 is almost the same, PRR of Gw1 is better then Gw2. This effect probably comes from the fact that Gw2 is outdoor on a higher altitude so it captures more traffic, which means more possibility of collisions with our packets. The marginal difference incidentally shows that there are relatively few collisions for the selected channels and SF. This conjecture is corroborated by the fact that longer frames, which are more likely to collide at some instant during their reception, are only slightly more likely to be dropped.

We ran many other configurations with different values of SF and the results were similar to CONF-A, for which PRR is only slightly impacted by PL.

Figure 3a shows PRR for CONF-B for Gw3, as a function of the frame size for TP = 2 dBm and TP = 10 dBm, and Figure 3b presents PRR as a function of the frame size for all gateways when TP = 10 dBm. We observe the same behavior-only a slight impact of the payload length on PRR: when we increase TP, PRR increases, but it keeps the same almost flat shape.

V. ANALYSIS OF PRR ANOMALY

In general, on wireless channels, Packet Reception Rate PRR is a function of Bit Error Rate BER and packet length PL: PRR = (1 BER) PL .

(

) 1
When the PL value approaches 0, PRR increases to 1. We would therefore expect that the PRR value of each gateway starts close to 1 and then drops when PL increases. However, our results shown in all figures strongly differ from this expected theoretical PRR dependence on the packet size.

To investigate further the effect, we propose to introduce an extra multiplicative factor that represents its impact on PRR in addition to SNR, PL, and SF through probability P s , which accounts for the uncertainty of successfully initiating the reception. To this goal, we apply the log function on the PRR formula. Since the majority of the curves are linear, we perform linear regression:

log(PRR) = PL ⇥ log(1 BER) + log(P s ).
(

) 2
When we vary the payload of the LoRa packets between 0 and 120 bytes, the frame size changes from 13 to 133 bytes because of an additional 13 byte overhead corresponding to the mandatory LoRaWAN header. By extending the regression function to the payload size of 0, we obtain the value characterizing the multiplicative factor as shown in Figure 2.

Successful reception of a frame mainly depends on three conditions: i) absence of collisions, ii) preamble detection and time synchronization with the gateway, and iii) valid decoding. Assuming low traffic, so rare collisions, we investigate the effects of channel variability on packet reception.

A. Preamble detection and time synchronization

To correctly receive a frame, the gateway should first detect the frame preamble and synchronize the reception process. As the CSS modulation is sensitive to synchronization issues between the transmitted packet and the reception process at the gateway, errors may occur during the preamble detection process. If the preamble is not correctly detected by the receiver, the complete frame is lost.

Figure 4 illustrates the process of receiver synchronization: a sender transmits a preamble of 8 upchirps followed by 2 inverted chirps (downchirps) and 1/4 of a symbol. The receiver multiplies the upchirps by downchirps so it can find two unknown variables: precise transmitter frequency f 0 and relative time reference t between the sender and the receiver, to decode correctly further symbols that encode data. If the synchronization process fails, the receiver cannot receive the frame. Note that for low values of SF (e.g., SF7), chirps are short and they double their duration for each increment of SF. So, the synchronization process is more fragile for SF7 and becomes more reliable for larger SF.

B. Channel attenuation

To characterize further P s , we ran experiments in the CONF-C configuration in which we varied the frame size cyclically and alternated between SF 7, 9, and 11 for two weeks. Then, we determined P s for each gateway and each SF with the following method:

• for each couple (Gwi, SF), we plot PRR vs. frame size like in Figure 5 (we give the data for Gw1 and Gw6 as an example, we skip other Gwi due to the lack of space). • we apply log(PRR) and perform the linear regression to obtain the value of log(P s ) for PL= 0 for each pair (Gwi, SF). Figure 6 presents the data for P s in function of SF for gateways 1 to 3, 5, 6, 8, and 13 (they are seven gateways that receive packets for three configured values of SF: 7, 9, and 11). We can notice in this figure that, as expected, P s depends on SF: P s increases for larger SF. Nevertheless, the improvement is relatively limited between SF9 and SF11: there is no threshold SF (or transmission power) above which PRR would notably raise. This behavior bears similarity with what is expected for a slowly varying Rayleigh channel.

So, we represent in Figure 7 the measured SNR distributions. We can observe that they closely follow the distribution of the Rayleigh channel gains for SF11. For smaller SFs, the distribution is truncated to the left because the corresponding packets are simply not received. In essence, each transmission faces an exponentially distributed Rayleigh channel gain, which remains mostly constant during the transmission.

Figure 8 presents P s as a function of mean SNR for each couple (Gwi, SF). To understand the curves, we need to explain how we compute mean SNR-it is the mean of the SNR values computed for all received packets at each SF so it does not take into account the packets that are lost. Mean SNR grows for smaller SF, since only the packets with higher SNR are effectively received for less robust modulations, whereas for greater SF, the packets with smaller SNR are included in the mean. For instance, mean SNR for Gw13 is computed only on a small fraction of packets that made it through.

In the figure, we do not observe a clear relationship between measured SNR and SF to use: there is approximately 5 dB of SNR difference between Gw3 and Gw5, which should theoretically be compensated by using SF11 instead of SF9, as each SF step brings 2.5 dB of the coding gain. This is what we see with similar PRR between Gw5 at SF9 and Gw3 at SF7. However, at SF11, Gw5 is still well below PRR of Gw3 at SF9. In other words, PRR reaches a plateau above which switching to higher SF brings little improvement.

PRR at Gw6 stands out: it is below the general PRR vs. SNR trend. This gateway also shows an unusual behavior in Figure 2 with even less influence of the packet size than the other gateways. We have not identified the reason that makes this gateway special, but the investigation into its behavior helped us to identify the limiting factor for PRR.

VI. RELATED WORK

Several authors experimentally evaluated LoRa performance with the focus on different parameters, types of hardware, and various network characteristics. Augustin et al. [START_REF] Augustin | A Study of LoRa: Long Range & Low Power Networks for the Internet of Things[END_REF] measured LoRa packet loss rate on a LoRa testbed showing: i) less than 10% of loss rate over a distance of 2 km for SF 9-12 and ii) more than 60% of loss rate over 3.4 km for SF12.

Haxhibeqiri et al. [START_REF] Haxhibeqiri | LoRa Scalability: A Simulation Model Based on Interference Measurements[END_REF] studied LoRa scalability. Their simulation model based on the measurements of the interference behavior between two nodes shows that when the number of nodes with the duty cycle of 1% increases to 1000 per gateway, the loss ratio increases to 32%, which is low compared to 90% in pure ALOHA for the same load. This difference comes from taking into account the capture effect.

Petrić et al. [START_REF] Petrić | Measurements, Performance and Analysis of LoRa FABIAN, a Real-World Implementation of LPWAN[END_REF] observed a highly variable packet error rate (between 3% and 90%) for the range of 3 km from a gateway under the following conditions: bandwidth of 125 kHz, coding rate of 4/5, transmission power of 14 dBm, and spreading factor SF 7, 9, and 11.

Mikhaylov et al. [START_REF] Mikhaylov | On LoRaWAN Scalability: Empirical Evaluation of Susceptibility to Inter-Network Interference[END_REF] studied the variation of the payload length, however, in a synthetic setup based on motes connected by cables and involving an artificial interferer, therefore, the results are not representative for real operational traffic.

Blenn et al. [START_REF] Blenn | LoRaWAN in the Wild: Measurements from The Things Network[END_REF] provided statistics of the TTN traffic based on global TTN logs: number of received frames, number of gateways, number of devices etc. They reported on the probability density function of RSSI and SNR, and presented the histograms of the payload length and spreading factors. They used the observed parameter in simulations to estimate collision probability as a function of the traffic intensity.

To the best of our knowledge, our work is the first one to study the impact of the payload size on PRR measured in an operational LoRaWAN network and reveal the behavior different from other types of wireless networks. We also point out the influence of receiver synchronization on successful packet reception.

VII. CONCLUSION

In this paper, we present the results of extensive experiments in the TTN public LoRa network to evaluate the transmission quality of LoRa links by measuring PRR as a function of the payload length.

The results show that there is only a slight impact of the payload length on PRR, which means that the bit error rate due to the ambient noise at the receiver and collisions are not the only factors that impact the probability of packet reception. We find that successful reception requires effective preamble acquisition and that this step is the limiting factor: a low channel attenuation favors the initial signal acquisition and persists for the remainder of the packet. Our measurements show that the LoRa channel behaves like a slow fading Rayleigh channel, which also influences probability P s of successful preamble reception. Our measurements of P s show that it depends on SF and SNR, and often becomes a dominant factor of successful reception depending on the signal strength at a gateway.

These findings have important implications for the Lo-RaWAN application designer: to achieve a good level of data delivery, devices need to consider packet retransmissions because they have to cope with frame losses not only due to the ALOHA access method, but also to the channel variability. Moreover, it is always better to group past data with new measurements and send them in long packets instead of more numerous short packets because the actual frame size has little influence on transmission reliability.

In future work, we plan to investigate a model that takes into account all factors influencing the packet reception probability, which will lead to a more realistic evaluation of the LoRaWAN cell capacity.

Figure 1 :

 1 Figure 1: LoRa frame structure.

Figure 3 :Figure 4 :

 34 Figure 3: a) PRR vs. frame size for Gw3. b) PRR vs. frame size, TP = 10 dBm, SF9.

Figure 5 :

 5 Figure 5: Gw1 and Gw6: PRR as a function of the frame size for several SF.

Figure 6 :

 6 Figure 6: P s as a function of SF.

Figure 7 :

 7 Figure 7: SNR distribution at Gw3 for CONF-C.

Figure 8 :

 8 Figure 8: P s as a function of mean SNR.

  TableIpresents the main performance parameters: SF, data rate, SNR limit, the airtime for a 10 byte packet, and the maximum payload length (PL max ).

	• Spreading Factor (SF) characterizes the number of bits carried by a chirp: SF bits are mapped to one of N =
	2 SF possible frequency shifts. SF varies between 6 (7 in
	practice) and 12 with SF12 resulting in the best sensitivity
	and range, at the cost of achieving the lowest data rate and
	worst energy consumption. Decreasing the SF by 1 unit
	roughly doubles the transmission rate and divides by 2
	the transmission duration as well as energy consumption.
	• Coding Rate (CR): it corresponds to the rate of Forward Error Correction (FEC) applied to improve packet error
	rate in presence of noise and interference. A lower
	coding rate results in better robustness, but increases the
	transmission time and energy consumption. The possible
	values are: 4/5, 4/6, 4/7, and 4/8.
	• Transmitted Power (TP): LoRaWAN defines the follow-ing values of TP for the EU 863-870 MHz band: 2 dBm,
	4 dBm, 6 dBm, 8 dBm, 12 dBm, and 14 dBm.
	Table I: LoRa parameters for 125 kHz BW.
	SF SNR limit Airtime for 10 B	Bit rate PLmax
	7		-7.5 dB	56 ms 5469 b/s	230 B
	8		-10 dB	103 ms 3125 b/s	230 B
	9	-12.5 dB	205 ms 1758 b/s	123 B
	10		-15 dB	371 ms	977 b/s	59 B
	11	-17.5 dB	741 ms	537 b/s	59 B
	12		-20 dB	1483 ms	293 b/s	59 B
	nPreamble Symbols	nHeader Symbols
	Preamble		Header (Explicit mode only) CRC	Payload	Payload CRC

Table II :

 II Altitude of the gateways and distance to them ordered by reception quality.

	Id.	Altitude (m) Distance (km)
	Gw1	220	0.01
	Gw2	240	0.03
	Gw3	220	2.4
	Gw4	-	-
	Gw5	253	3.9
	Gw6	233	4.4
	Gw7	246	2.9
	Gw8	210	1.7
	Gw9	249	5.2
	Gw10	256	5.5
	Gw11	244	5.7
	Gw12	238	7.1
	Gw13	2253	18.3

ACKNOWLEDGMENTS

This work has been partially supported by the French Ministry of Research project PERSYVAL-Lab under contract ANR-11-LABX-0025-01.