Pierre-Jean Petitprez
email: pj.petitprez@gmail.com

Erwan Kerrien
email: erwan.kerrien@inria.fr

Pierre-Frederic Villard
email: pierrefrederic.villard@loria.fr

PoLAR: a Portable Library for Augmented Reality

Keywords: 1, 3, 4 [Computer Graphics]: Graphics Utilities-Application packages; I, 4, 9 [Image Processing and Computer Vision]: Applications-[I, 6, 8]: Simulation and Modeling-Types of SimulationAnimation;

manipulator 2D markers Soft shadow on phantom object Camera flow

Figure 1: PoLAR tracking application showing the use of 2D objects, camera flow and real-time scenegraph interaction

INTRODUCTION

Augmented Reality (AR) application development involves mastering many advanced topics to:

• design and implement a user friendly Graphical User Interface (GUI);

• implement an efficient graphics engine with features such as texture mapping, animation, ambient occlusion and shadow maps;

• interface various devices, especially cameras and GPS or other external tracking devices;

• implement a large diversity of Computer Vision (CV) algorithms to track moving targets, recognize objects and reconstruct scenes.

Most current AR Software Development Kits (SDK) 1 target developers with general or even little programming skills and therefore primarily provide high quality implementations of CV algorithms. ARToolkit [START_REF] Kato | A registration method based on texture tracking using artoolkit[END_REF] grounded its success on its powerful marker tracking and recognition, and strong camera calibration support. Vuforia2 platform sets forward its object and scene recognition capabilities. Tracking and recognition technologies are also at the core of Metaio3 that addressed customers with absolutely no programming skill through its Creator drag and drop application creation tool. Moreover, the latter two are commercial SDKs. This focus misses CV specialists' whose aim in developing AR applications is to test or demonstrate their own CV algorithms.

PoLAR (Portable Library for Augmented Reality) is motivated by offering those latter developers an easy access to state of the art GUI creation, image interaction, graphics engine implementation and camera interfaces, in a few lines of code, portable across both desktop and mobile platforms through an API designed to meet their needs. PoLAR defines a framework for simple and fast prototyping of graphical applications for augmented reality, and more general image visualization, in both classical CV and Medical Imaging contexts. No tracking or other image processing capabilities are offered, but instead an API to easily plug in custom tracking processing. The framework is written in C++ and published under the GNU GPL license. PoLAR can be downloaded at http://polar.inria.fr.

PoLAR's main contributions are i) portability: PoLAR has been tested and used on Linux, Windows, MacOS and Android; ii) simplicity: an API designed for CV specialists with detailed user guide including tutorials and examples; iii) deformation capability: Po-LAR provides an API to manage physics engines; iv) sustainability: PoLAR depends on well-established Qt and OpenSceneGraph libraries, and is open source software.

METHODS

Supporting libraries

PoLAR depends on two main libraries: the GUI-oriented framework Qt 4 and the graphics engine OpenSceneGraph5 . Qt allows for fast GUI development, powerful 2D graphical drawings, and high-level, cross-platform, access to hardware components, including cameras. Besides, OpenSceneGraph is a powerful 3D graphics toolkit, compatible with OpenGL6 on desktop environments, and OpenGL ES on mobile platforms. Its scenegraph implementation enables graph nodes to be shared between multiple views, dynamically loaded or deleted, and manipulated interactively. Both libraries were chosen for their sustainable development framework. Middle to long term support is indeed grounded on: their portability since both are available on Linux, Windows, Mac OS and Android, their open source licence for non-commercial usage and their compliance with the GNU GPL, their very active community of users and developers, their active development state with frequent updates.

Software architecture PoLAR encapsulates calls to Qt and OpenSceneGraph in a normalized API that makes it straightforward to implement classical features required in AR application development. Yet, particular care was taken in keeping the API fully compliant with both Qt and OpenSceneGraph coding standards so that any advanced developer can still benefit from the full APIs of these libraries.

The main class of PoLAR (Viewer) inherits from a Qt widget, leading to an easy and straightforward integration of PoLAR into any Qt-based application. This widget manages an OpenScene-Graph viewer with one orthographic camera to enable pan, zoom and window-level capabilities on the display, and a perspective camera to render the 3D scene. Qt 2D graphical objets are rendered as overlay. Fig. 2 shows the various main classes of PoLAR and its links to external libraries. Fig. 3 depicts the different layers that compose a PoLAR Viewer. We briefly focus on the design of these layers.

2D graphical objects Many existing libraries (e.g. Cairo 7 , GTK+ 8 , SDL 9 , Qt) already offer powerful 2D drawing tools that generally require to understand the notion of a graphical context, or to manage by oneself the painting events, or even to implement the mathematical representations of the needed effects. PoLAR is targeted for users who prefer to avoid dealing with such technical aspects. PoLAR wraps the Qt graphics items into a level of abstraction where paint events and drawing methods are hidden to the user, though still reachable when needed.

The creation of a new 2D object (polygon, spline, marker points (see Fig. 1) or text) takes only one line of code with default options, and up to three to set some particular options (including color, size or shape). For comparison, Qt-native objects require dealing with the paint event method and need to be manually added to the viewer, for a total of a few tens of lines. New classes of 2D objects can be implemented through a factory mechanism. Real-time interaction with a complex scenegraph PoLAR supports user interaction thanks to the powerful Qt interaction management. Default interaction methods are implemented and users can add theirs. Interaction with images, 2D objects, and 3D objects is made possible in real-time within a running application.

Multiple helper classes are provided to create and manipulate 3D objects. Each 3D object is added as a node of a scene graph which allows for fast access and manipulation of the objects in a very transparent and simple way. AR-oriented features are implemented in PoLAR, including easy access to scene lights and cameras, facilitated replacement and deletion of objects, rapid switch of objects visibility or state (normal vs phantom), phantom objects to handle occlusions of virtual objects by real objects (see the virtual chair occluded by the real table in Fig. 4, right), and high quality shadow casting. Two lines of code are needed to add a manipulator to a 3D object and use it for translating, rotating or scaling (see Fig. 1, which makes PoLAR particularly suitable for WYSIWYG applications. Interaction with a 3D object can also be made programmatically, as PoLAR offers all the methods needed to access the graph nodes.

Camera flow and images PoLAR offers tools to manipulate textures, from bitmap textures loaded from a file, to dynamic textures displaying a camera flow. Texture creation from a file or a video flow is made as simple as possible. This abstract level of management allows for texture manipulation regardless of its nature. In only two lines of code (three in the case of a dynamic texture), a texture can be loaded and applied to a 3D object, or displayed in full size in the viewer, just like in an image editor. PoLAR provides basic image manipulation features particularly suitable for medical imaging applications: pan and zoom for easy navigation on the image, and window/level interactive contrast enhancement tool.

Portability

We have designed PoLAR to be compatible with all current major platforms, namely Linux-based distributions, Microsoft Windows, MacOS and Android systems. Support for Apple iOS is currently under development. This has been possible thanks to the availability of Qt and OpenSceneGraph on said platforms, and thanks to the use of C++11-compliant standard code.

All interaction methods and shortcuts are fully customizable though default values are always provided. Mouse and keyboard are the main interaction methods on desktop environments, while on mobile systems Qt-based gesture recognition allows interacting through the touchscreen.

GPU computing

We have developed a fully functional shader system compatible

Raw video flow

Augmented video flow [START_REF] Phong | Illumination for computer generated pictures[END_REF] to objects added in the virtual scene. This shader system takes advantage of the Open-SceneGraph shadow computation features to provide soft shadows in the scene (see Fig. 1). On older desktop environments which are only compatible with previous OpenGL specifications, it is still possible to use a fixed-function rendering which uses a per-vertex Blinn-Phong lighting model [START_REF] Blinn | Models of light reflection for computer synthesized pictures[END_REF]. Deformations AR applications in the medical context often need to include deformations. Various methods exist to simulate deformations. They often consist of a trade off between fast and accurate simulation. The mass-spring method [START_REF] Desbrun | Interactive animation of structured deformable objects[END_REF] is a real-time method consisting of modeling soft bodies as a discrete system of mass points linked together with springs and dampers. The finite element method [START_REF] Zienkiewicz | The Finite Element Method Set[END_REF] is a numerical technique for solving mechanical equations (conservation laws, balance equations, constitutive laws, etc.) considering the soft bodies as a continuum through a matrix representation.

We propose to offer both capabilities by interfacing our library with two physical engine libraries: 1) a mass-spring system based on Bullet 10 and 2) a finite element method based on VegaFEM [START_REF] Sin | Vega: Non-Linear FEM Deformable Object Simulator[END_REF]. Our strategy was to factorize the common operations linked to the physics engine (apply boundary conditions, define mechanical parameters, iterate in the system resolution of the physical laws, etc.) as well as to use our core library functionalities (display and position of a 3D mesh in an AR environment). Furthermore, we optimized the object deformation display process such as, if the topology remains constant, the mesh vertex positions are directly updated by references to the physical engine data.

PoLAR relies on the robust Qt threading API to provide multithreading computation. The chosen architecture ensures the physics computations do not interfere with the GUI and the graphical rendering.

RESULTS

The main outcome of using PoLAR is a simple and efficient way of implementing AR applications. We present in this result section three kinds of application examples that highlight the code simplicity as well as the possibilities of our library.

Basic AR application

The first result example (whose source code is available in the PoLAR repository) is a basic AR application consisting of reading a camera flow, defining a projection matrix M and displaying 3D objects projected on the video flow with M. The result is displayed on Fig. 4. The initial camera image is on Fig. 4.left and the augmented image is on Fig. 4.right. A phantom object (the table) is used to hide a part of a 3D object (the orange chair) and to allow another 3D object (the camera) to cast a shadow on the table.

10 http://bulletphysics.org/ Listing 1 shows the code corresponding to this application. L4 creates the Qt application. L5-7 create a viewer with light and shadows. L8-13 add video stream (a webcam on /dev/video0) on the viewer background. A video manager is created, then a texture from it and then this texture is displayed on the viewer background. L14 enables pan and zoom and window/level on the display. L15-21 set up the 3D scene: L15-16 load and add a first 3D object (the camera) L17-18 load and add a second 3D object (the orange chair), and L19-21 create a ground plane (the table), set it as a phantom object and add it to the scene graph. With L22-27, every time a new frame is captured, the video manager sends a Qt signal with the image data and connect it to a custom Qt slot function which computes the related projection matrix. In this example a lambda function is used (L23-27) which should be completed on L24 with the code of a custom tracking algorithm that updates the projection matrix M. L26 applies the computed projection matrix to the viewer. Conversion from vision-oriented matrices to OpenGL-oriented matrices is managed by PoLAR. L28 shows the widget, L29-30 ensures the application correctly quits when the viewer is closed, and runs the application. This first example shows how the core visualization tools have been encapsulated. Writing the same application using a 3D visualization library such as OpenGL or out-of-the-box OpenSceneGraph would have been cumbersome and many functionalities would be missing (e.g.: window/level, webcam management).

Advanced AR application including tracking

As studied in the previous application example, PoLAR aims to facilitate the creation of graphical applications, and does not provide any projection matrix update method, but provides suitable inputs and outputs to link it to e.g. a tracking library. To validate the efficiency of PoLAR in real use cases, we have developed an AR application (the source code is available in the PoLAR repository, under the runPolar application) where PoLAR is bound to the OpenCV library [START_REF] Pulli | Realtime computer vision with opencv[END_REF] to implement the tracking of an image marker. PoLAR API defines two functions to implement this binding: newFrame sends the current camera frame to the tracking algorithm, and setProjection applies the computed projection matrix to the 3D scene.

Thanks to these very generic methods, it is very easy to replace the current OpenCV tracking algorithm by any other tracking method either user-defined or available from another tracking library. Fig. 5 shows the workflow corresponding to the code interaction between the PoLAR-based class and OpenCV tools.

AR application with deformations Finaly, we tested the VegaFEM-based deformation module by building physical objects that can significantly deform, i.e. the deflection could easily be observed by human eyes. These objects are 3D-printed cubic-shaped objects with a very soft polymer material. The experiment consisted of placing a cube at the origin corner of a chessboard and applying different weights (250g and 500g) on it, a picture at every step, including the rest state. The same experiment was reproduced within PoLAR. The projection matrix was computed via the camera calibration method presented in [START_REF] Zhang | A flexible new technique for camera calibration[END_REF] and provided by OpenCV. The initial 3D models without deformation and projected on the pictures can be seen on the left of Fig. 6. The deformation simulation was done using the PoLAR physics plugin. The cubes were meshed with tetrahedrons using tetgen [START_REF] Si | Tetgen, a delaunay-based quality tetrahedral mesh generator[END_REF]. The boundary conditions were a Dirichlet boundary condition (zero displacement) applied on the bottom of the cube complemented by a Neumann condition that imposed a force on the top of the cubes to reproduce the weight. The integration was done using the implicit Newmark scheme with a time step of 0.02 and the two Newmark constants were = 0.25 and γ = 0.5. The corotational formulation was used to provide with large and stable deformations. The material was defined with a linear constitutive law characterized by a Young's modulus around 1 MPa found by trial-and-errors and a Poisson's ratio of 0.49 to set the material incompressible.

Our tests consisted of comparing the real experiment and the PoLAR-based simulation. The deformations were observed in both virtual and real worlds. Two cubes with different cross-section shapes were tested. Results are illustrated on Fig. 6. In order to better appreciate how the simulation matched with the reality, half of the virtual cube has been hidden. Qualitatively, one can observe that it is feasible to reproduce both the pose and the deformation in an augmented environment. Quantitatively, the outcome was twofold: Coding simplicity: we implemented this application in approximatively 200 lines, with 150 lines required by the simulation 0g 250g 500g

Figure 6: Real and virtual cubes deformed under various weight. Two shapes were tested with no weight, 250g and 500g. Half of the virtual cube is displayed to better appreciate the deformed shape.

with VegaFEM, and only 50 lines for the full display using PoLAR. This is due to the higher abstraction level in both the visualization and the deformation functions. ii) Efficiency: our simulation runs at fps. This experiment is available on our GIT server.

CONCLUSION

We have presented PoLAR, a new open-source library that helps with building AR applications. It contains a set of tools to display images or video flows, to add 2D and 3D objects via a scenegraph environment with 3D deformation capabilities.

PoLAR is cross-platform (MacOS, Linux, Windows and Android), takes advantage of modern GPU capabilities, handles common hardware constraints (e.g.: camera flow and tactile device interactions) and provides with real-time applications.

PoLAR has been tested on many examples and basic applications all available on the website http://polar.inria.fr. Three of them are described in this paper to show the simplicity and the efficiency of coding AR applications compared to other available tools: low number of lines of code, self-explanatory methods, fast computing time, interaction simplicity with external libraries and virtual soft-body deformation simulation.

Figure 2 :

 2 Figure 2: Library components and dependencies

Figure 3 :

 3 Figure 3: Composition of a PoLAR application

Figure 4 :

 4 Figure 4: Basic AR application: image without and with augmentation

Listing 1 : 4

 14 Basic AR application code 1 typedef osg::ref_ptr<PoLAR::Object3D> Obj3Dptr 2 int main(int argc, char ** argv) 3 { QApplication app(argc, argv); 5 PoLAR::Viewer viewer; 6 viewer.setShadowsOn();

  new PoLAR::Object3D("data/ plastic_chair.obj"); 18 viewer.addObject3D(obj2); 19 Obj3Dptr ground = new PoLAR::Object3D("data/ table.obj"); 20 ground->setPhantomOn(); 21 viewer.addObject3D(ground); 22 QObject::connect(videoStream.get(), &PoLAR:: VideoPlayer::newFrame, [=](unsigned char * data, int w, int h, int d)

Figure 5 :

 5 Figure 5: Workflow of the advanced AR application

http://socialcompare.com/fr/comparison/ augmented-reality-sdks

http://www.vuforia.com

https://en.wikipedia.org/wiki/Metaio

http://www.qt.io/

http://www.openscenegraph.org/

https://www.opengl.org/

https://cairographics.org

http://www.gtk.org

https://www.libsdl.org

ACKNOWLEDGEMENTS

PoLAR was funded by an Inria Tecnhnology Development Action grant (2014-2016).


Kahina Bessai
email: kahina.bessai@loria.fr

Franois Charoy
email: francois.charoy@loria.fr

Optimization of Orchestration of Geocrowdsourcing Activities

Keywords: crowdsourcing, GIS, pattern, simulation

Geocrowdsourcing has proved to be very valuable in crisis situations. Calling to citizen on the ground or to experts or trained amateurs to help in the mapping of crisis situation is a recognized and valuable practice. However, despite the experience gained from real and dramatic situations, it remains difficult to set up and execute complex processes that require actions of both people on the ground and people on the web, and to understand how to get the best result at the minimal cost in term of users actions. In this paper, we describe a process that can be used to assess a global situation on a map using a combination of services and user operations. We want to understand how best to distribute a limited amount of human actions between different kind of tasks in order to get the most reliable result. Since it is difficult to conduct experimentation, we have decided to use simulation to reach a result that could be applied on the ground. This simulation relies on a geolocalised corpus of tweets. It provides some hints about how to deploy an exercise on the ground that are discussed as a conclusion. In addition, we propose a binary integer programming (BIP) making best use of the available workers.

Introduction

Calling to the crowd to conduct activities out of the reach of individuals or small groups is a very common practice. This kind of initiative is known under the generic name of crowdsourcing, or human computation [START_REF] Meier | Digital Humanitarians: How Big Data Is Changing the Face of Humanitarian Response[END_REF]. It has been applied in catastrophic situations but can also be used in more controlled situations. The goal of this project is to develop and validate a method and a framework in order to get citizen to contribute to contextual city assessment activities at a large scale. More precisely, we want to be able to synthesize information regarding the state of a populated geographic area by coordinating in an optimized way volunteers actions. To achieve that kind of goal, we need to get information from the ground. People must execute actions at some places, mostly collect data. Other participant, connected to the system must then analyse the data to produce an aggregated result. People could use that framework for area status assessment during a crisis or as a preparedness activity, to measure phenomenon in a city at a defined point in time and to repeat that measure on a regular basis. They could combine it to other kind of sensors to conduct different kind of real time analysis. Real time means that the result could be used to take action as the event unfold. This paper describes an ongoing work where we try to optimize the overall quality of a geographical area status assessment following a predefined process with a limited number of human resources. We have defined a crowdsourcing process and tested it with an existing dataset [START_REF] Benouaret | Answering complex locationbased queries with crowdsourcing[END_REF]. This was a first experience to evaluate our framework. Here, we continue this work with a new dataset, with new parameters and with the objective to optimize the resource that we can leverage for such a process in order to get the best possible result as we will explain it in section 4. In section 5 we describe a subset of the results of our experiment and we discuss the best way to find compromise between the coverage of the assessment and its quality.

State of the art

People used crowdsourcing in a geographical context for a long time, even before the existence of computers. Bird watchers contribute to science by participating to counting activities periodically to create maps of birds populations and of their evolution. This activity has taken a new dimension with the advent of mobile phones, GPS and the Internet1 . The construction of maps like Open-StreetMap2 is a ten year old project that aims at building accurate maps calling to the crowd to contribute all kind of information. Each of these experiments are done in an ad-hoc way. Humanitarians organisations conduct more organized operations under the umbrella of the Digital Humanitarians [START_REF] Meier | Digital Humanitarians: How Big Data Is Changing the Face of Humanitarian Response[END_REF]. They are able to call to volunteers to geolocalize information during crisis. Other sophisticated research use information produced on social media to make sense of what is going on on a crisis area [START_REF] Purohit | Identifying Seekers and Suppliers in Social Media Communities to Support Crisis Coordination[END_REF]. These are important steps toward a generalized approach regarding the use of crowdsourcing with a geographical context. The goal of other authors is to allow people to call to the crowd to answer more or less structured queries.In [START_REF] Alt | Location-based Crowdsourcing: Extending Crowdsourcing to the Real World[END_REF], the authors propose a prototype for location-based mobile crowdsourcing consisting of a Web and a mobile client. Through these clients, people from the crowd can search for tasks and submit solutions. Similarly, in [START_REF] Bulut | Crowdsourcing location-based queries[END_REF], the authors design a framework for crowdsourcing location-based queries on the top of Twitter. The Framework relies on Foursquare to find the appropriate people to answer the query. In [START_REF] Kazemi | GeoCrowd: enabling query answering with spatial crowdsourcing[END_REF] Kazemi and Shahabi introduce a taxonomy of spatial crowdsourcing and propose three techniques for assigning the maximum number of tasks to the crowd. They also introduce a taxonomy for spatial data. This last work relies on the Gowalla dataset 3 for its simulation. Re-garding, the selection of the k-top results several approaches have been proposed which can be classified in four categories: (i) heuristics-based approaches [START_REF] Guo | So who won? dynamic max discovery with the crowd[END_REF][8] [START_REF] Adelsman | Sophisticated voting with information for two voting functions[END_REF] [10], (ii) machine-learning methods [START_REF] Pfeiffer | Adaptive polling for information aggregation[END_REF], (iii) extensions of heap-based methods [START_REF] Peng Ye | Combining preference and absolute judgements in a crowd-sourced setting[END_REF] [13] [START_REF] Feige | Computing with noisy information[END_REF] and (iv) combining rating and comparison based-algorithms [15] [16].

Here, we consider the state of a global area that we want to assess as accurately as possible in a repeatable way. We want to support different kinds of scenarios that include a data collection phase on the ground. We want to define a model that could be experimented in a real setting with the best chances to provide a result of the best quality considering a limited number of resources. We have already done a first simulation of our model, but with the only dataset used by researchers to our knowledge for this purpose, the Gowalla dataset 4 . It provides set of checkins at accurate places These checkins are used by researchers to simulate crowdsourced activities and to assess their models [START_REF] Benouaret | Answering complex locationbased queries with crowdsourcing[END_REF] but these checkins are just dots on a very large map (California) where we would like to assess an area on a city size area. In the following section, we get into the details of this problem.

The crowdsourcing pattern

The goal of the crowdsourcing activity that we are considering is to create the most accurate assessment map on a delimited geographical area. It could be for instance a map of the level of damage of a city after a earthquake or a map of flooded area and its evolution. It could also be a map assessing the level of cleanliness of a city or any other criteria that could be computed by aggregating measures from different points on the map. The quality of the result depends on the coverage of the assessment i.e. the percentage of the map covered at the end of the process with the correct result. We consider time bounded crowdsourcing campaign since we want to repeat it in order to produce of view on the evolution of the situation. These are two supplementary constraints. In order to avoid the traditional pitfalls of requiring complex tasks from crowdworkers, that are then difficult to evaluate, we have defined a process following the idea of the findfix-verify pattern [START_REF] Bernstein | Soylent: a word processor with a crowd inside[END_REF]. It is based on three simple steps : data collection, data selection and data assessment. The data collection is done on the ground by people. In our case, data woule be geolocalised pictures but it could also be text description, sounds, movie clips or any kind of data that is difficult to process automatically. For the data selection phase, the map is divided in square areas of fixed size. We group the data by area and ask the workers to select the most valuable one area by area. Each worker has to vote for one picture on an area regarding a given criteria. Figure 1

is an example of this task

This result in a smaller set of photos that will be assessed regarding this criteria by another set of workers. We only consider the best pictures that have been selected from the previous step as shown on figure 2 In the end we obtain a map where each area is graded according to the opinion of the workers. As said before, we limit in time the execution of this process and thus, we assume that we can count only on a limited number of actions done by workers. The question is to decide how to execute this process in order to get the best coverage with the best quality of the assessment. This will depend on different factors like the quality of the data that are collected, the quality of the worker and the way the process is executed in order to distribute the actions between the different activities.

Since it would be very difficult to conduct experimentation in real setting with actual worker to test all the possible combination, we propose to conduct some simulation that combine a geolocalised corpus and simulated workers.

The problem formulation of the orchestration of geocrowdsourcing activities

In this section, we propose a formal model for the tasks assignment in crowdsourcing.. Moreover, we design an efficient approach in such way that the overall quality of the the selection and the assessment process evaluation of a given tasks be maximal. To give a formal model of the considered problem here, let the following variables :

-Z the possible geographical zones with z its cardinality.

-W the available workers with w its cardinality.

w i the skill of the worker i.

q j the minimum quality required by geographical zone j.

x k ij represents the assignment of worker i to geographical zone j for the step k of the evaluation process, where k ∈ {1, 2} represents respectively the selection step and the assessment phase. The value of this binary variable is defined as follows:

x k ij =
1 if worker i is affected to geographical zone j for phase k 0 otherwise [START_REF] Meier | Digital Humanitarians: How Big Data Is Changing the Face of Humanitarian Response[END_REF] Recall that the process tasks matching is done in two steps. For instance, if the process consist to classify images in crisis context, the first step consists to select the best picture to represent a given situation and the second steps is related to the assessment of the selected pictures during the first step. We aim to use fairly the available workers to cover maximum geographical zone while the overall quality of each considered zone is maximum on one hand. In order to avoid the quality degradation of a given zone, we have established a quality threshold that must be achieved. The problem can be defined as follows:

∀j ∈ {1, ..., z}, max Q j = i∈W (x 1 ij w i + x 2 ij w i ) (2)
Under the following constraints :

∀i ∈ {1, ..., w},

z j=1 (x 1 ij + x 1 ij ) = 1 (3) ∀j ∈ {1, ..., z}, w i=1 (x 1 ij + x 2 ij )w i ≥ q s j (4) ∀i ∈ {1, ..., w}, j ∈ {1, ..., z}, (x 1 ij , x 2 ij ) ∈ {0, 1} 2 (5)
Equation 2 represents the overall quality of the process tasks selection and assessment of a given location. It is important to note that the considered problem is multi-objectives in the sense that an objective function denoted Q j is associated for each location. Equation 4 represents the fact that each worker should be assigned to a single geographical zone. In addition, a given worker participate either in the selection step or the assessment step. Equation 4stipulates that for each geographical zone a high level of quality must be ensured. Equation 5represents the integrity constraints of the addressed problem. To summarize, for a defined number of workers and geographical zones, the objective is to assign workers, so that the maximum of the overall quality of the selection and the assessment processes is ensured.

The simulation model

The simulation of geolocalised actions is a difficult issue. We can do it by generating the actions on a map with a random distribution. This would not reflect the actual distribution of user geolocalised activities. The factors that influence this distribution are not random. An other approximation would be to rely on actual location of user action in geographical area that are available through social network activities. Researchers have followed this path, relying on the well known Gollawa dataset and as we explained it previously they refer to places and not precise location. We propose to use geolocalised tweets in urban areas.

A geolocalised tweet correspond to a conscious action of someone at the corresponding location. Someone actually did post a message at that place. These actions are not evenly distributed. This gives us a sense of the kind of coverage we can expect. We are not considering the content, only the position. Figure 3 is an example of 24 hours of geolocalised tweets in Paris. The coverage is obtained by splitting the space in cells of equal size. We use the size of the cell to decide of the accuracy of the measure. We see on figure 4 the distribution of tweets on the map is not even. Some cells receive no action while others receive several. Figure 5 shows a detail that could be an intermediate Fig. 4. The grid result. Cells can be painted based on the assessment. Obviously, we won't get result for all cells since some of them have no data. To simulate the process, we use tweets for geolocalised action and we estimate a number of crowdsourcing actions that will be executed to complete the job. We estimate that if we have N tweets for a given period of time, we can count on 2N crowdsourcing actions that we can distribute between selection and assessment. We also execute some simulation with a varying number of worker (in our case from 20000 to 100000). As mentioned previously, the process evaluation consists in two steps: (i) the selection stage, where the user has to decide what, in his opinion is the more accurate data to reflect a situation (see Figure 1) and (ii) the assessment phase, where the user grade the situation on a predefined scale based on the data that is provided to him (see Figure 2). Of course, in a real situation, the description of the purpose of the selection and of the assessment would be of paramount importance but since we are simulating the actions, we consider that the users will have a good understanding of the context. However, the available workers do not provide the same quality. In the following, we describe the considered two stages of our model.

The selection phase of the proposed model

As its name implies, the selection phase consists to select the representative picture of a given situation. Formally this phase can be described as follows. Without loss of generality, let a set of picture p 1 , p 2 , ..., p m , belonging to the same geographical zone, where their quality are random variables with cumulative distributions functions denoted respectively F pi (and probability density functions f pi ). Similarly, let a set of workers w 1 , w 2 , ..., w n where their quality are random variables with cumulative function F (w i ). It is previously that if the workers vote of a given picture randomly in a uniform way, the number of votes follows a binomial distribution:

P (N i = k) = C k n ( 1 m ) k ( m -1 m ) n-k (6)
Where, N i , i ∈ {1, ..., m} are binomial random variables representing the number of votes of photos p 1 , p 2 , ..., p m . One only constraints 3, 4 and 5 of the proposed model are considered, the optimization problem can be formulated as follows: min k∈{1,...,n}

E(Q i ) > q i (7)
Where, E(Q i ) represents the average quality of picture p i and q i its minimal required quality.

In other words, the objective consists to determinate the minimal number of workers (or voters) who must choose a given picture so that it will be the most representative one. To study the impact of each considered parameter in the proposed model, we have conducted a simulation with the following method: A user action is a vote to select the best picture from a set of pictures corresponding to a bucket, based on a calculated quality considering the quality of the pictures and the quality of the worker. Picture quality is calculated with a Gaussian distribution with a mean of 0.8. We consider that the data are of good quality in general. The user task execution depends on the user quality. Again, we use a Gaussian distribution to compute this quality. We will vary the mean regarding the user quality. User quality is an important issue regarding crowdsourcing. We consider that user voluntarily contribute to the task but that they are not experts nor trained. They may provide by results genuinely.

We have defined a value function for the pictures. Let P i be the picture quality, w be the worker quality. The picture value is drawn as a random number based on the following distribution : N (P i, 1 -W ) The worker votes for the picture with the highest value.

We select the first picture that gets k vote. Vote distribution is random among buckets. We stop to vote for a bucket as soon as a picture reaches k votes.

The assessment phase model

Regarding the assessment of a picture we use the following model. Photos are graded on a discrete scale (0,1,2). The model assumes that the better the photo is, the more accurate the grading. We are just computing the chance that a user with a given worker quality W gives the right answer.

The correct result is assumed if P i * W > Random(). Else, we chose the resulting vote equi-probably between the two remaining choices.

Simulations

We have conducted several simulations using different kind of parameters. The first parameter is the bucket size. We use squares of side length of 50m, 100m and 200m. With smaller bucket, we can expect a more accurate map but a bad coverage. On our corpus (Paris) it represents respectively 50779, 12576, 3120 buckets. The number of vote k required to decide for a result [START_REF] Meier | Digital Humanitarians: How Big Data Is Changing the Face of Humanitarian Response[END_REF][START_REF] Purohit | Identifying Seekers and Suppliers in Social Media Communities to Support Crisis Coordination[END_REF][START_REF] Bulut | Crowdsourcing location-based queries[END_REF][START_REF] Guo | So who won? dynamic max discovery with the crowd[END_REF][START_REF] Adelsman | Sophisticated voting with information for two voting functions[END_REF]. Again, the more vote we require, the less result we will get since more actions will be required to take a decision in each area. On the other side, if we require more vote, we may expect more accurate results. Since we consider that we have a limited number of user actions, we can distribute them between selection and assessment, from 50/50 to 80/20. The more action we allocate to selection, the more results we will have to assess. The worker quality is the last parameter that can vary. We assume that workers are doing their best but that may not have always a perfect judgement regarding the task to accomplish. Thus we assign a quality to workers that varies from 0.6 to 0.9 with a gaussian distribution.

In the next section, we describes the result of our experiments based on this model.

The simulation has been executed using data collected on the area of Paris. We have collected tweets on this area on periods of 24 hours. The number of geolocalised tweets collected did not vary much from one day to the other, around 60000 tweets per 24 hours. It is very difficult to identify clear patterns in the distribution (cf. figure 3). The coverage in the city center is better than in the Fig. 6. Number of results depending on the worker quality and the number of votes suburban areas. The same exercise done in other big cities like New York or London give the same kind of results. There is a high density of tweets in touristic area or business districts. It means that we cannot expect a full coverage of a geographical area with tweets. But since we want to compare the resulting coverage based on different distribution of actions, we are concerned with relative results more than with absolute results.

We have conducted several experiments, varying the parameters. In Figure 6, we vary the number of vote and the worker quality. Half of the actions are used for selection and half for the assessment. Match means that we have been able to select a picture.Exact match means that the best one has been selected by the voters. Graded means that the picture has been graded and Exact grading means that the grading is correct for the bucket.

With one vote to make the selection, the number of action is sufficient to select and grade pictures for every bucket. We see that in this case, and with the parameters that we have selected, the variation of the number of exact match does not vary much with the quality of the worker but the variation of the exact grading is much more important.With 3 votes, the number of results is lower but the number of exact match is higher in the end compared to 1 vote whatever the quality of the worker. With 5 votes, as it could be expected, the number of Fig. 7. Number of results depending on the worker quality and the number of votes results decreased as well as the number of correct results. It is the percentage of good results compare to the overall result that increase. The more voter we use, the less results we get but of better quality.

In Figure 7 we vary distribution of actions, quality and votes. This graphs shows the coverage of the correct results. It is the % of correct results. Varying the distribution of action is interesting especially if we use several votes for each bucket. The more action we use for selection, the more results we get for grading. We try to understand here how the percentage of correct grading vary based on the variation of these three parameters. Again the best result depends on the quality of the worker (W=0,9 and vote=3). But we can observe than if we use one vote and good workers we get a lot of good results.We can also notice that with these parameters, the quality of the result decrease rapidly with the quality of the worker.

In figure 9 we did the same simulation, varying the number of actions from 20000 to 100000. This figure presents the best result depending on the number of action and on the worker quality. We are now focusing on the quality according to the workers distributions. Table 8 represents a subset of the result we get. This table represents the best results obtained for all the parameters (distribution, vote and number of actions) for a workers quality (the mean quality of a worker is fixed to 0.6). We can observe that the increase of the correct results by varying these parameters is very slow. The simulation suggests that when we increase the number of actions done by worker, we must increase the number of votes to get better results. By varying workers quality, we notice that the percentage of best results increases. This percentage increases also according to the number of actions. However, as shown in Table 8 and Figure 9, the gain slows above a certain number of actions. This trend is still consolidating for different values of workers quality figure 9(0.7, 0.8 and 0.9).

As we can see in figure 9 it is interesting to note that the gain obtained when we increase the number of actions is less interesting than gain obtained when we have access to better worker . That would suggest that it is better to get access to a smaller number of skilled worker that to a large number of workers. In the results, we also note that when we have access to more action, we obtain a better result when we increase the number of votes. The simulation we have done has been repeated several times on the same area with very similar results. This could be anticipated since a lot of data we use for the simulation are synthesized. Overall, based on our model and on the corpus we rely on, we can expect good results with 3 to 7 votes depending on the number of actions. Still, we see that the quality of workers is very important and that it's more efficient to select a reduced number of skilled workers. It means that it could be very valuable either to train the workers to increase their capacity to provide good results or to try to assess worker quality and distribute the work to the best ones first. To do that, we need to get more insight on the way worker behave with the kind of tasks that we plan to ask them to execute. This is the next step of this project, i.e. conduct experiments to compare the execution of these kinds of tasks with domain experts and with ordinary people, with or without training and to evaluate the average quality we can obtain with different kind of task and questions.

Fig. 1 .

 1 Fig. 1. Example of a selection task

Fig. 2 .

 2 Fig. 2. Example of an assessment task

Fig. 3 .

 3 Fig. 3. 24 hours of geolocalised tweets in Paris

Fig. 5 .

 5 Fig. 5. The expected result

Fig. 9 .

 9 Fig. 9. Evolution of the number of correct results depending on the number of action and on the worker quality

http://www.nytimes.com/2013/08/20/science/earth/crowdsourcing-for-thebirds.html

2 http://www.openstreetmap.

org 3 https://snap.stanford.edu/data/loc-gowalla.html

https://snap.stanford.edu/data/loc-gowalla.html