Julio C S Dos Anjos
email: jcsanjos@inf.ufrgs.br

Gilles Fedak
email: gilles.fedak@inria.fr

Claudio F R Geyer
email: geyer@inf.ufrgs.br

BIGhybrid -A Toolkit for Simulating MapReduce on Hybrid Infrastructures

Cloud computing has increasingly been used as a platform for running large business and data processing applications. Although clouds have become highly popular, when it comes to data processing, the cost of usage is not negligible. Conversely, Desktop Grids, have been used by a plethora of projects, taking advantage of the high number of resources provided for free by volunteers. Merging cloud computing and desktop grids into hybrid infrastructure can provide a feasible low-cost solution for big data analysis. Although frameworks like MapReduce have been conceived to exploit commodity hardware, their use on hybrid infrastructure poses some challenges due to large resource heterogeneity and high churn rate. This study introduces BIGhybrid a toolkit to simulate MapReduce on hybrid environments. The main goal is to provide a framework for developers and system designers to address the issues of hybrid MapReduce. In this paper, we describe the framework which simulates the assembly of two existing middleware: BitDew-MapReduce for Desktop Grids and Hadoop-BlobSeer for Cloud Computing. Experimental results included in this work demonstrate the feasibility of our approach.

I. INTRODUCTION

Mankind has been producing over increasing amount of data. According to IDC 1 , by 2020 there will be around 40 Zettabytes (40,000,000 Petabytes) of data that will require processing of some sort. This data volume requires processing capabilities beyond those that current IT infrastructure can provide.

MapReduce (MR) [START_REF] Dean | MapReduce -A Flexible Data Processing Tool[END_REF], a programming framework proposed by Google and currently utilized by many large companies, has been employed as a successful means for data processing and analysis. Hadoop, the most popular open-source implementation of MR [START_REF] White | Hadoop -The Definitive Guide[END_REF], abstracts task parallelism management from programmers who only need to implement their applications as Map and Reduce functions. Cloud computing has increasingly been used as a platform for business applications and data processing [START_REF] Mell | The NIST Definition of Cloud Computing[END_REF]. Cloud providers offer Virtual Machines (VMs), storage, communication, and queue services to customers for which they pay an hourly fee. These resources can be used for deploying Hadoop clusters for data processing and analysis.

When it comes to data processing, the computing power offered by other types of infrastructure is also of interest. Desktop Grids (DG) [START_REF]ser. Numerical Analysis and Scientific Computing[END_REF], for instance have numerous users 1 IDC's Digital Universe Study, sponsored by EMC, December 2012.

around the world who donate idle computing power to multiple projects. DG have been applied in several domains such as biomedicine, weather forecasting, and natural disaster prediction. Merging DG and Cloud Computing (Cloud) into Hybrid Infrastructures could provide a more affordable mean for data processing. However, although MR has been designed to exploit commodity hardware, its use on hybrid infrastructure poses some challenges due to large resource heterogeneity and high churn rate typical of such environments.

The adaptation of existing MR framework or the development of new software raises research issues related to a priori data splitting and distribution, strategies to avoid the communication between the infrastructures, tasks and data co-scheduling, fault and sabotage tolerance, data privacy, among other issues and more. Moreover, using real testbeds to evaluate the use of MR on hybrid infrastructure presents considerable challenge due to the lack of reproducibility of the experimental conditions in DG and the complexity of finetuning Cloud software stacks.

This study introduces BIGhybrid, a toolkit for simulating MR on hybrid environments, with a focus on Cloud and DG. We analyze the characteristics of hybrid MR runtime environment and design the simulator accordingly. The simulator is based on SimGrid [START_REF] Casanova | Versatile, Scalable, and Accurate Simulation of Distributed Applications and Platforms[END_REF] and leverages solutions proposed in the scope of the MapReduce ARN project [START_REF] Antoniu | Scalable Data Management for Map-Reduce-based Data-Intensive Applications: A View for Cloud and Hybrid Infrastructures[END_REF].

It is able to simulate two middleware for two distinct infrastructures: BitDew-MR [START_REF] Fedak | BitDew: a programmable environment for large-scale data management and distribution[END_REF], [START_REF] Moca | Distributed Results Checking for MapReduce in Volunteer Computing[END_REF] for Desktop Grid Computing and Hadoop-Blobseer [START_REF] Nicolae | BlobSeer: Bringing high throughput under heavy concurrency to Hadoop Map-Reduce applications[END_REF] for Cloud computing. BIGhybrid has several desirable features: it is built atop of MRSG, a validated Hadoop simulator [START_REF] Kolberg | MRSG -A MapReduce simulator over SimGrid[END_REF], and MRA++, a simulator for heterogeneous environments [START_REF] Anjos | Addressing Data-Intensive Computing Problems with the Use of MapReduce on Heterogeneous Environments As Desktop Grid on Slow Links[END_REF]; it has a trace toolkit that enable analyze, monitor and graphically plot the task executions; it is a trace-base simulator able to process real infrastructure availability traces [START_REF] Kondo | The Failure Trace Archive: Enabling Comparative Analysis of Failures in Diverse Distributed Systems[END_REF]; and its modular design allows for further extension. BIGhybrid can be used for evaluating scheduling strategies for MR applications on hybrid infrastructures. We believe that such a tool is important to researchers and practitioners working on big data applications and scheduling.

The rest of this work is structured as follows. Section II provides an overview on the MR framework and other systems used. In Section III, we describe the characteristics of hybrid infrastructures. Section IV introduces BIGhybrid and Section V describes the evaluation methodology. The conclusion and suggestions for future work are summarized in Section VI.

II. BACKGROUND

This section presents MR and introduces the implementations of both Hadoop-BlobSeer and BitDew-MapReduce, that will be used on BIGhybrid simulator.

A. MapReduce

MR is a programming framework that abstracts the complexity of parallel applications by partitioning and scattering data sets across hundreds or thousands of machines, and by moving computing closer to data [START_REF] White | Hadoop -The Definitive Guide[END_REF]. Figure 1, adapted from [START_REF] White | Hadoop -The Definitive Guide[END_REF], shows the MR data flow. The Map and Reduce phases are handled by the programmer, whereas the Shuffle is created while the job is being carried out. The input data is split into smaller pieces called chunks, that normally have a size of 64 MB. The data is serialized and distributed across machines that compose the Distributed File System (DFS).

When running an application, the master assigns tasks to workers that then run each processing stage. The machine that receives a Map task, handles a Map function and emits key/value pairs as intermediate results that are temporarily stored in the workers' disks. The execution model creates a computational barrier, which allows tasks to be synchronized between the producers and consumers. A Reduce task does not start its processing until all the Map tasks have been completed. A hash function is applied over the intermediate data to determine which key partitions will compose a Reduce task. Each key partition is transferred to one machine, in prefetching mode, during the Shuffle phase, to execute the next phase. After a Reduce function has been applied to the data, a new resulting key/value pair is issued. Then results are stored in the distributed file system and made available to the users. The MR Hadoop provides management mechanisms, data replication and execution control. The MR has a management architecture based on the master/worker model, while a slaveto-slave data exchange requires a P2P model [START_REF] White | Hadoop -The Definitive Guide[END_REF]. When the task runtime on a machine is greater than average for the cluster, the machine running the task is characterized as a straggler. If a machine is characterized as a straggler after the first task distribution, it will not receive new tasks to processing in free slots.

B. Hadoop-BlobSeer

BlobSeer is a DFS that manages a huge amount of data in a flat sequence of bytes called BLOBs (Binary Large Objects). The data structure format allows a fine-grained access control. BlobSeer emits file version control which enables incremental updates on data files, and high throughput with concurrent reads, writes and updates data. The data chunks have a fixed size of 64 MB so that they can maintain compatibility with the structure of the Hadoop file system.

The DFS on Hadoop (HDFS) was replaced in its integrally by BlobSeer. An API implements the calls of Hadoop for the BlobSeer File System (BSFS). The name space manager is centralized, and it keeps the name space of BSFS for mapping files for BLOBs. However, this data structure is completely transparent for the Hadoop system and its MR users. The classical execution of MR on Hadoop was not changed and explores data locality similar to HDFS. The BSFS provides a data replication using a flat structure. The blocks are distributed for local storage in machines with a load-balancing strategy. The fault-tolerance mechanism is a simple data replication across the machines. However, it does not explore replication across racks as in HDFS.

C. BitDew-MapReduce

BitDew [START_REF] Fedak | BitDew: a programmable environment for large-scale data management and distribution[END_REF] is a middleware that exploits protocols like P2P, http, BitTorrent and ftp, and selects the best protocol depending on data size. BitDew architecture is decentralized and has independent services for Data Scheduler, Data Catalog, Data Repository and Data Transfer. These services are accessed via three API: Active Data to control the behavior of the data system, such as replication, fault-tolerance, data placement, lifetime, protocols and event-driven programming facilities; Transfer Manager to manage the concurrent file transfer completions and the concurrency level of transfers; BitDew to provide functions that create slots and carry out data management.

The Data Catalog maintains a centralized and updated meta-data list for the whole system in a Distributed Hash Table . The model includes both stable and volatile storage. The stable storage is provided by stable machines or Cloud Storage like Dropbox and Google Drive, and the volatile storage are local disks of volatile nodes. The MR implementation [START_REF] Lu | Assessing MapReduce for Internet Computing: A Comparison of Hadoop and BitDew-MapReduce[END_REF] is an API that controls the master and worker daemon programs. This MR API can handle the Map and Reduce functions through BitDew services. The data locality from Hadoop MR was implemented like a data attribute to support the separation of the input data distribution from the execution process.

Result checking is controlled through a major voting mechanism [START_REF] Moca | Distributed Results Checking for MapReduce in Volunteer Computing[END_REF]. In the Hadoop implementation when the network experiences unavailability, a heartbeat mechanism signals to the master that the host is dead. However, in BitDew the network can be temporarily offline without undergoing any failure. The fault tolerance system needs a synchronization schema, as pointed out by [START_REF] Tang | Analysis of Data Reliability Tradeoffs in Hybrid Distributed Storage Systems[END_REF] where transient and permanent failures can be handled. A barrier-free computation is implemented in BitDew to mitigate the host churn behavior [START_REF] Lu | Assessing MapReduce for Internet Computing: A Comparison of Hadoop and BitDew-MapReduce[END_REF]. In BitDew (unlike the case of the classical MR implementation), the computation of Reduce nodes starts as soon as intermediate results are available.

III. HYBRID INFRASTRUCTURE

Table I, summarizes the main architectural features of Cloud-BlobSeer, BitDew-MapReduce and the Hybrid MR environment. Hybrid infrastructure enables the use of highly heterogeneous machines, and stable and volatile storage to avoid data lost. The set of data-distribution strategies applicable to a given scenario depends on how much bandwidth is available. Two independent DFS implementations are required to handle data distribution under two scenarios, namely lowbandwidth and high-bandwidth. Hybrid infrastructure uses an orchestrator to manage results and data input from users. It can be decentralized to improve data distribution over network. In special case of Cloud and DG, fault tolerance mechanisms have different policies to detect faults. A more specialized system is applied on DG due to node volatility.

Figure 2 illustrates the solution proposed to model a hybrid system and introduces Global Dispatcher and Global Aggregator that will be used on BIGhybrid simulator. The Global Dispatcher located outside the DG and the Cloud has middleware functions for receiving both job tasks and input data from users. It is a centralized data storage system that manages policies for split data and distribution, in accordance with the needs of each system. The working principle is similar to the publish/subscribe service where the system gets data and publishes the computing results. This approach is simple, but creates a potential network bottleneck. BIGhybrid simulator will enable the study of several strategies to determine the best data distribution and resource allocation on MR applications in hybrid infrastructures.

Global Aggregator receives all key/values of Reduce, and keys with the same index in each system are joined to last Reduce function in order to create a consistent result. The BIGhybrid simulator will help to choose the best strategies to achieve this goal. Iterative MR computations, necessary on Global Aggregator, are not supported by an original MR model. It is not an easy task to combine all Reduces from heterogeneous platforms, although it is possible to make a new stage for MR [START_REF] Ekanayake | MapReduce for Data Intensive Scientific Analyses[END_REF]. A possible approach is to use the MapIterativeReduce [START_REF] Dobre | Parallel Programming Paradigms and Frameworks in Big Data Era[END_REF] which creates an Aggregator to collect all the outputs of the Reduce tasks and combines them into a single result. At the end of each iteration, the reducer checks if it is the last or not. However, according to [START_REF] Tudoran | MapIterativeReduce: A Framework for Reduction-intensive Data Processing on Azure Clouds[END_REF], this schema might be inefficient for large workloads. BIGhybrid enables the study of variations and patterns to be implemented for aggregation module.

IV. BIGHYBRID SIMULATOR

The idea behind BIGhybrid simulator is to optimize MR applications in order to provide a cloud service with the available resources of a DG system. BIGhybrid is modular and it is built on top of Simgrid [START_REF] Casanova | Versatile, Scalable, and Accurate Simulation of Distributed Applications and Platforms[END_REF], which is a simulation-based framework for evaluating cluster, clouds, grid and P2P (peer-to-peer) algorithms and heuristics. Different from others simulators, BIGhybrid has two independent systems, through which it is possible to use different configurations for DFS, schedulers, input/output data size, number of workers, homogeneous and heterogeneous environments, combine two different platforms, and make the simulation parallel. BIGhydrid generates traces from each system to allow individual or collective analyzes in the same time line.

BIGhybrid is built on two components described in previous work: MRSG (MapReduce over SimGrid) that simulates Cloud-BlobSeer with Hadoop; and MRA++ (MapReduce Adapted Algorithms to Heterogeneous Environments) that simulates BitDew-MapReduce. Figure 3 illustrates the architecture of BIGhybrid, which comprises four main components: input data management (Global Dispather), Cloud-BlobSeer module, BitDew-MapReduce module and integration module for results (Global Aggregator). More details about MRSG simulator and MRA++ can be found in [START_REF] Kolberg | MRSG -A MapReduce simulator over SimGrid[END_REF] and [START_REF] Anjos | Addressing Data-Intensive Computing Problems with the Use of MapReduce on Heterogeneous Environments As Desktop Grid on Slow Links[END_REF]. A user can specify an input function for each system and for individual Map and Reduce functions. In the next release version it will be possible to build platforms for real infrastructures using Failure Trace Archive [START_REF] Kondo | The Failure Trace Archive: Enabling Comparative Analysis of Failures in Diverse Distributed Systems[END_REF]. This means, the BIGhybrid enables 256 settings of configurations in the same simulator. It is possible to make adjustments to several kinds of strategies and configurations in both Cloud-BlobSeer with Hadoop and BitDew-MapReduce, to find a load balance without data loss and with suitable strategies to achieve an efficient data partition between the two environments.

A. Cloud-BlobSeer Simulation Module

The Cloud-BlobSeer simulation module reproduces the behavior of the MR platform, and invokes SimGrid operations whenever a network transfer or processing task must The DFS is implemented as a matrix that maps chunks to nodes. The master node knows where each chunk is placed, exactly as it happens in the real implementation. Moreover, each chunk can be linked to more than one node, which allows to simulate chunk replicas. SimGrid is responsible for the simulation of all network communication and task processing in our implementation. Cloud-BlobSeer simulation only implements the node distributions in one rack. The next version of BIGhybrid will use the storage simulation API of SimGrid, on Disk Emulation Module to simulate the storage behavior. As of writing disk simulation is specified as an I/O cost in the configuration file in User API.

The virtualization of machines behavior is not simulated in current version of BIGhybrid, but is abstracted as an additional task cost. The virtualization support module will be integrated in the future by the SimGrid virtualization support, as described in [START_REF] Hirofuchi | Adding Virtual Machine Abstractions Into SimGrid: A First Step Toward the Simulation of Infrastructure-as-a-Service Concerns[END_REF], and migrating virtual machines, as described in [START_REF] Hirofuchi | Adding a Live Migration Model into SimGrid: One More Step Toward the Simulation of Infrastructure-as-a-Service Concerns[END_REF].

B. BitDew-MapReduce Simulation Module

BitDew [START_REF] Fedak | BitDew: a programmable environment for large-scale data management and distribution[END_REF] is a middleware for large scale data management on hybid distributed computing infrastructures. Its runtime environment supports the use of multiple file transfer protocols: either client/server (http, ftp, scp), P2P (bittorrent), Grid (through the SAGA API) or Cloud (Amazon S3, Dropbox). A set of BitDew services handle many high level data management issues: data index and meta-data catalog, fault tolerance, reliable file transfer, data scheduling, replication, data life-cycle, collective communication, data collection management, event-based programing model and more.

The implementation of MapReduce over BitDew targets firstly Desktop Grid systems [START_REF] Lu | Assessing MapReduce for Internet Computing: A Comparison of Hadoop and BitDew-MapReduce[END_REF], proposing mechanisms to alleviate host churn, unavailability of direct communication between the hosts and lack of host trust. The implementation relies on master and worker daemon programs. This MR API can handle the Map and Reduce functions through BitDew services. The data locality from Hadoop MR was implemented like a data attribute to support the separation of the input data distribution from the execution process.

A function controls result checking through the major voting mechanism as in Moca [START_REF] Moca | Distributed Results Checking for MapReduce in Volunteer Computing[END_REF]. When the network experiences unavailability, a heartbeat interval signals to the master that the host is dead, in the Hadoop implementation. However, in BitDew the network can be temporarily offline without undergoing any failure. The FT needs a synchronization schema, as pointed out by [START_REF] Tang | Analysis of Data Reliability Tradeoffs in Hybrid Distributed Storage Systems[END_REF] where transient and permanent failures can be handled. A barrier-free computation is implemented in BitDew simulation as can be seen in section V.

C. Additional BIGhybrid Modules

In BIGhybrid, the Global Dispatcher is manual or automatic. In the manual version, the user defines a function for data distributions and a job configuration for each system for both Cloud-BlobSeer and BitDew-MapReduce, such as, input data, data size, chunk size and so on. In automatic release, one Orchestrator manages user queries and distributes tasks to systems. A Global Storage maintain data users, so the Orchestrator could be initialize a new job, if it is necessary.

The results of the Global Aggregator module are implemented as a single Reduce task after the last current Reduce task has been completed. The processing results are tracked and saved in a file for future analysis. A toolkit for system execution analysis was implemented to assist on creating platforms homogeneous and heterogeneous, and make execution traces based on visualization traces supported from SimGrid. This toolkit enable to users analyze all system execution and change the strategies as needed. The traces can be both individual systems as for all simulation.

V. EVALUATION

This section describes the environment setup and results of evaluation in order to demonstrate the features and scalability of simulator.

A. Environment Setup

Two environments have been considered. The first, in a small scale servers is a proof of concept. The second considers a cluster of 2,000 nodes and evaluates the simulator ability to replicate results obtained in previous work. The proof-ofconcept first simulated a homogeneous 5-node cluster with 2 cores each, 5.54 GFlops of processing capacity and 1 Gbps network. This cluster was used to process 2GB of data, 36 maps and 5 reduces. The second cluster contains 5 heterogeneous machines with 2 CPU cores each, which process capacity is drawn from a log-normal distribution according to [START_REF] Javadi | Discovering Statistical Models of Availability in Large Distributed Systems: An Empirical Study of SETI@home[END_REF] from 4.76 GFlops to 6.89 GFlops, network of 10 Mbps. This cluster is used to process 1.1 GB of data, 36 maps and 30 reduces.

To define the large scale setup, we used characterization of MR applications performed by Chen [START_REF] Chen | The Case for Evaluating MapReduce Performance Using Workload Suites[END_REF]. Chen examined MR traces from two production environments from Yahoo and Facebook.

The traces obtained from Yahoo comes from a 2,000 node cluster and contains 30,000 jobs spanning over 3 weeks. The cluster was used to run applications that require bash, interactive and semi-streaming computations. For present work, we model the Yahoo cluster and consider the "aggregate, fast job" applications characterized by Chen. Table II shows the details of these applications, including number of jobs, input data size, job duration, Map time and Reduce time.

B. Results and Analysis

The first experiment is a proof-of-concept introduced by Figures 4, 5 and6. Figure 4 shows an execution of Cloud-BlobSeer on the homogeneous cluster. The Map tasks produce intermediary keys that are sent during the shuffle phase, and Reduce tasks initialize once the Map tasks are finished. The results of BitDew-MapReduce execution on heterogeneous cluster are show in Figure 5. The Reduce tasks start as soon as machines have data to process. It is possible to view that, as the link is 10 Mbps, data transfers take longer to complete during the shuffle phase. Execution time is similar to the first cluster because the data chunk size on BitDew-MapReduce is 32 MB instead of 64 MB as Cloud-BlobSeer.

Figure 6 shows the execution of BIGhybrid taking into account the two clusters. This figure is specially interesting as it demonstrates the task execution parallelism and the beginning of intermediate data transfers.

Figure 7 shows a job execution of BIGhybrid, for a homogeneous execution, following the specifications of the 2,000 node cluster and application is detailed in Table II. The runtime is 305.13 s to Map and 673.32 s to Reduce, the and simulation error is ≅ 5% related to one job in Table II. This demonstrates the scalability of the simulator, reproducibility capacity and its suitability to research of new strategies on hybrid infrastructure.

Fig. 1 .

 1 Fig. 1. MapReduce data flowchart model

Fig. 2 .

 2 Fig. 2. Hybrid Infrastructure

Fig. 3 .

 3 Fig. 3. BIGhybrid Simulator Architecture

Fig. 4 .

 4 Fig. 4. Job MR on Cloud-BlobSeer simulation

Fig. 5 .

 5 Fig. 5. Job MR on BitDew-MapReduce simulation

Fig. 7 .

 7 Fig. 7. Job MR on Bighydrid simulation with 2000 hosts

TABLE I .

 I COMPARISON AMONG MR SYSTEMS

	Characteristics	Cloud-BlobSeer with Hadoop	BitDew-MapReduce	Hybrid-MapReduce
	Heterogeneity	Moderately	High	High
	Network	High Bandwidth	Low Bandwidth, distributed cache	Hybrid Bandwidth
	Local Storage	Distributed	Remote (Cloud Storage) + local	Local and distributed + Remote Cloud Storage
	Management	Master/Slave	Master/Slave	Hierarchical Orchestrator
	Application Profile	Any	Low Communication on Shuffle phase	Optimized for all size archives
	File System API	Posix	Tuple Space model	Hybrid (Posix + Tuple Sace)
	Hosts	Stable	Stable and Volatile	Stable and Volatile
	FT mechanism	Data and Task Replication	Data Replication and transient failure support	Data and Task Replication, and transient failure support
	Computation	Hadoop Compatilble	Barrier-free	Hybrid
	be performed, without modifying SimGrid source code. This
	simulation follows the Hadoop implementation, which a heart-
	beat mechanism to control job execution. This architecture
	is the following: API of input users code, DFS, MapReduce
	functions, master (Jobtracker) and slaves (Tasktracker).

TABLE II .

 II YAHOO TRACES ( 2,000 MACHINES CLUSTER )

	# Jobs	Input	Shuffle	Output	Duration	Map Time	Reduce Time	Label
	21,981	174 MB	73 MB	6 MB	1 min	412	740	Small jobs
	838	568 GB	76 GB	3.9 GB	35 min	270,376	589,385	Agregate, fast job
	91	206 GB	1.5 TB	133 MB	40 min	983,998	1,425,941	Expand and aggregate jobs
	35	4.9 TB	78 GB	775 MB	3 hs 45 min	4,481,926	1,663,358	Data summary
	5	31 TB	937 GB	475 MB	8 hs 35 min	33,606,055	31,884,004	Data summary, large
	1,330	36 GB	15 GB	4 GB	1 hr	15,021	13,614	Data transformation


Julien Badie

Franc ¸ois Brémond

Global tracker: an online evaluation framework to improve tracking quality

Evaluating the quality of tracking outputs is an important task in video analysis. This paper presents a new framework for estimating both detection and tracking quality during runtime. If anomalies are detected in the tracking output results, they are categorized as natural phenomena or real errors using contextual information. As this framework should be generic and work on any kind of system (single camera, camera network), a re-acquisition step using a constrained clustering algorithm is also performed in order to keep track of the object even if it leaves the scene and comes back or appears on another camera. The framework is evaluated on two datasets using different kinds of tracking algorithms.

Introduction

People tracking has become a very important task with various applications such as video surveillance, people monitoring or video games. However, even in the same field of application, there is an infinite number of possible scenarios, environments and contexts. Thus, no detection nor tracking algorithm can perform perfectly in all situations. Performance evaluation is crucial in estimating the quality of an algorithm on a given scenario or application. Maggio and Cavallaro [START_REF] Maggio | Efficient multitarget visual tracking using random finite sets[END_REF] categorize two kinds of methods for performance evaluation: analytical methods and empirical methods. Analytical methods aim at evaluating a tracking algorithm from a theoretical point of view, taking into account complexity and requirements. On the other side, empirical methods evaluate directly the outputs of the tracking algorithm without considering how these results are computed. Empirical methods can also be divided in two categories depending on whether the ground truth is required or not to evaluate the results. In this paper, we propose a new evaluation framework based on an empirical standalone methods without using ground truth. Choosing an evaluation framework that does not require ground truth has many different applications. One of them is giving feedback to the tracking algorithm that can tunes its own parameters to improve the results on the next frame. Another convenient application is to filter the reliable information from the tracking algorithm that can be used for a next processing step such as event detection or reidentification. In this paper, re-identification is used as an example of application of the online evaluation framework.

Related work

Much work has already been done on online evaluation frameworks. Some of these approaches are based on estimating the quality of the detected moving regions. For example, Erdem et al. [START_REF] Hall | Automatic parameter regulation of perceptual systems[END_REF] have proposed a method for segmentation evaluation based on contrast at the boundary of each object. Other approaches are based on trajectory ( [START_REF] Henriques | Globally optimal solution to multi-object tracking with merged measurements[END_REF], [START_REF] Wu | Online empirical evaluation of tracking algorithms[END_REF]), time-reversibility [START_REF] Zamir | Gmcp-tracker: Global multi-object tracking using generalized minimum clique graphs[END_REF], uncertainty ( [START_REF] Milan | Detection and trajectory-level exclusion in multiple object tracking[END_REF]) or different sets of features ( [START_REF] Kuo | Multi-target tracking by on-line learned discriminative appearance models[END_REF]). However most of these approaches are very dependent on the given detection or tracking algorithms and are generally dedicated either to detection or tracking errors. In this paper, we try to overcome these limitations by proposing an evaluation framework that is independent from both detection and tracking algorithms that will detect and classify anomalies. Anomalies are defined as incoherences found in the tracking output. This new framework is called global tracker because it acts as an extension of the tracking algorithm while using a larger data pool and providing a more global approach of the scene understanding. It acts as a bridge between the tracking algorithm and the next processing step. An important point of the global tracker is the genericity, as it would work with every tracking algorithms and in any kind of situation (one camera, network of overlapping or non-overlapping cameras, 3D cameras, ...). Concerning the method used, it is similar to the one used in [START_REF] Bak | Multipleshot Human Re-Identification by Mean Riemannian Covariance Grid[END_REF] where the tracking algorithm performs data matching of different frames to create an optimized graph. However this approach is limited by the fact it seems to work only with good detection input and only uses data in a time window of 20 frames. We propose to evaluate the global tracker framework by comparing the anomalies found by the online evaluation framework with the errors detected by a traditional method using the ground truth of several datasets and by showing the improvements of the results using the proposed approach. The rest of the paper is organized as follows: Section 3 gives an outline of the framework and Section 4 explains the evaluation methodology of the global tracker and shows some results.

Outline of the proposed approach

The global tracker is an online process. It is defined on a sliding window of size ∆ and has knowledge of everything that happened in this period. This knowledge is noted K t and contains information on the interval [t -∆, t]. At time t, the goal of the global tracker is to update the previous knowledge of the framework K t-1 using the output data of the tracking algorithm O t .

K t = f (O t , K t-1 ) (1)

Tracklets

The output data of the tracking algorithm O is represented as a list of tracklets. A tracklet is an oriented chain of nodes C i representing one single object that appears on the scene with the ID i during the period [T mi , T ni ] (fig. 1). Each node C i t corresponds to one detected object at time t and contains a pool of features F i t (eg. localization, appearance, ...). An oriented chain can have multiple parallel sub-chains, one per camera.

The main goal of the global tracker is to assess the quality of each tracklet by studying its behavior and its evolution throughout time. The global tracker is divided into two main tasks, each working at a different level and having a different goal:

• the Interpolation module works at the tracklet level and aims at correcting small tracking errors when one or more consecutive detections are missing in a graph, meaning that some nodes are missing in the tracklet.

• the Tracking quality estimation module works at the list of tracklets level and aims at detecting any anomaly found in the output of the tracking algorithm

• the Re-acquisition and re-identification module works on the knowledge level and aims at combining tracklets separated in time or that appear in different cameras and represent the same object. In this paper, this module is added to show the possible applications of the online evaluation.

Interpolation

Some frames may be missing in an object trajectory. It happens if the tracking algorithm fails to find a correct matching for an object on the current frame but is nevertheless able to recover the trajectory on the next frame. According to the tracklet representation, it means that some nodes are missing in the tracklet. The assumption is made that the tracking algorithm can not create tracklets with more than five consecutive nodes missing. If this case were to happen, the object would be considered as lost and its ID would not be used anymore, meaning that the chain has ended.

In order to fill the missing nodes, linear interpolation is performed using the feature pools of the two nodes located just before and just after the missing nodes.

∃t ∈ [T mi , T ni ] : F i t = ∅ ⇒ F i t = F i t-1 + F i t+1 2 (2)
where F i t-1 = ∅ and F i t+1 = ∅ In the case where several consecutive nodes are missing, the same interpolation method is used with the last two known nodes. Due to the assumption that a new tracklet is created if more than five consecutive nodes are missing, there is no need to use a more elaborated and timeconsuming method to fill the missing nodes. Considering this assumption and the fact that the interpolation module is used at every frame, it can be sure that each tracklet contains no empty nodes. This optimization step has two main goals. The first goal is to slightly improve the tracking results because some metrics (for example the CLEAR metrics) are very sensitive to the number of missing frames in a tracking output. On the other side, it will be easier for the second module to estimate the overall quality of each tracklet if no node is missing.

Tracking quality estimation and anomaly correction

The goal of the second module is to compute control features and analyze their variations. Depending on the results, some anomalies are found. These anomalies can be real errors (ID switch, merging or splitting of two tracklets), or natural phenomena (person leaving the scene, occlusion with background elements). This module aims at determining the impact of the anomalies.

The feature pool F i t of each node C i t is divided into three feature pools

F i t = {F O,i t , F OO,i t , F OE,i t }: • F O,i t
represents the pool of features that are computed only using the data of the object (e.g. appearance, trajectory, ...)

• F OO,i t represents the pool of features that are computed using data of the object i considering the other objects of the scene (eg. occlusion level, people density, ...)

• F OE,i t represents the pool of features that are computed using data of the object i considering the environment (eg. occlusion level with background element, entering or leaving some zones, ...)

In order to monitor the behavior of one tracklet, the feature pool F O,i is the most relevant. The other feature pool F OO,i and F OE,i are used to define the neighborhood of the object and to classify the anomalies found. For each feature f i ∈ F O,i , we compute the weighted mean µ(f i ) and the weighted standard deviation σ(f i ).

µ(f i ) = Tn i t=Tm i w(t) * f i t Tn i t=Tm i w(t) (3) σ(f i ) = Tn i t=Tm i w(t) * (f i t -µ(f i )) 2 Tn i t=Tm i w(t) (4)
where w is the weight function and [T mi , T ni ] is the time interval where the tracklet is defined. This weight function is used to decrease the impact of the oldest data while focusing on the latest data. For our experiment, two different weight functions were tested, a linear function and an exponential function. The exponential function generally gives better results when heavy changes occur in the tracklet. Finally, the coefficient of variation c(f i ) of each feature is computed.

c(f i ) = σ(f i ) µ(f i ) (5)
The potential anomalies are then detected by comparing the coefficients of variation at frame t and frame t -1.

δ i = 1 - c(f i ) t c(f i ) t-1 (6)
If δ i is near or equal to zero, it means that the last node of the tracklet keeps the same behavior as the other nodes of the tracklet. Otherwise, it means that the last node is diverging from the rest of the tracklet. In that case, an anomaly is detected. For the experiments, a threshold of 0.25 was set to know if the value of δ could indicate an anomaly. The next step is to determine whether the anomalies found are real errors or just natural phenomena. For example, an anomaly is found when a tracked object becomes occluded by a background element of the scene (the size of the bounding box and appearance of the object suddenly change) and this kind of anomaly should be categorized as a normal phenomenon if the object is disappearing but as an error if the bounding box of the object is merged with the background element. That is why the feature pools F OO,i t and F OE,i t are used. These feature pools contain information about the neighborhood of the object. Depending on the features used, contextual information such as entering or leaving zones in the scene can easily discriminate normal phenomena from real errors. Section 4 defines all the pools of features used for the experiment and their influence on the anomaly categorization.

If the anomaly is detected as a normal phenomenon, the node is definitively added to the tracklet. On the other hand, if an error is proven, the last node is removed from the tracklet and set in a newly created tracklet. However the risk of this algorithm is to create a set of small yet reliable tracklets. To rectify this situation, a re-identification algorithm can be used as an application of the online evaluation.

Re-acquisition and re-identification

The last module is called re-acquisition and reidentification module. The goal of re-acquisition is to merge tracklets that represent the same object but were considered as different because of long term occlusion or because the object left and re-entered the scene (fig. 2). Reidentification is a well-known problem in video surveillance where the goal is to detect one object moving in a camera network. Re-acquisition and re-identification represent the same challenge and are addressed the same way by merging several tracklets together. Merging tracklets means that their IDs i become the same and that their chain of nodes and their feature pools are also merged.

The method to merge tracklets is a constrained clustering algorithm using reliable visual features and the distance associated to these features to create clusters. The constrained clustering algorithm works as a normal clustering algorithm except that two types of constraints are added: the must-link constraints and the cannot-link constraints. These constraints create exceptions in the clustering algorithm and guarantee the integrity of the algorithm. In this module the following constraints are used:

• must-link constraints: two tracklets that were merged at time t -1 stay merged at time t. This constraint is based on the assumption that the online evaluation is able to provide reliable tracklets that can be easily merged together by this algorithm.

• cannot-link constraints: spatio-temporal constraints are considered based on the camera network and the known context. For example on a single camera, two tracklets appearing on the same frame cannot represent the same object. On a non-overlapping camera network, the same object cannot be detected on two cameras at the same time.

The global tracker uses a mean-shift clustering algorithm with the above constraints and merges the tracklets according to the distance between their visual covariance descriptor described in the next section.

Experiments

Features used

As said before, the feature pool of each node is divided into three feature pools {F O,i t , F OO,i t , F OE,i t } depending on which elements are used to compute the feature: the tracked object alone, the tracked object and other objects or the tracked object and the environment. In this section, we describe which features are used for the experiments. It is our choice to use the same set of features for all the datasets to keep the global tracker as generic as possible. Choosing a more dedicated set of features depending on the video sequence is a problem that is not addressed in this paper. Table 1 sums up the features used for the experiments.

Object features

Bounding box dimensions: The width and height of the tracked object are computed. This feature is sensitive to huge variation in the object detection, which can be symptomatic of a merge or a split between different objects.

Trajectory: The direction and the speed are computed. This feature is sensitive to sudden changes in the path of the tracked object, which could indicate a swap between the IDs of two objects for example.

Color histogram: RGB color histograms are computed. This feature can be used to detect big changes with the tracked object appearance that can occur because of a false detection or a ghost phenomenon.

Covariance-based appearance model [START_REF] Ben Shitrit | Tracking multiple people under global appearance constraints[END_REF]: this feature is an alternative to the color histogram feature. It is more accurate than color histogram and has shown very good results in the re-identification domain. This is the main feature used for the re-acquisition and re-identification module. For each object, a visual signature is computed and updated at every frame. If a significant change is detected by computing the distance between the initial signature and the updated one, this can be interpreted as a possible error in detection or tracking.

Object versus object features

Density with other objects: this feature is used to estimate the possible interactions between two objects at the same time t. If two objects are very close to each other it can be the origin of a detection or tracking error. Density is computed as follows considering two detected objects C 1 t and C 2 t :

density = Area(C 1 t ) + Area(C 2 t ) Area(C 1 t ∪ C 1 t ) (7)
Spatial overlap level with other objects: this feature computes the spatial overlap between all tracked objects that are overlapping (non-zero intersection of the bounding boxes) at the same time t. It is defined by the maximum ratio between the intersection of both bounding boxes and the bounding box that has the biggest area:

spatialOverlap = max C 1 t ∩ C 2 t Area(C 1 t ) , C 1 t ∩ C 2 t Area(C 2 t ) (8)
Frame-to-frame overlap with other objects: this feature works as the spatial overlap feature except it is computed with one object C 1 at frame t and all other objects with a different ID at frame t -1. If the intersection exists with at least one other object C 2 t-1 , the frame-to-frame overlap is:

f 2f Overlap = C 1 t ∩ C 2 t-1 Area(C 1 t ) (9)

Object versus environment features

The following features are part of the object versus environment feature pool F OE,i t . They can be computed depending on the dataset meta-data. Offline, some zones can be defined (background elements, zones where people can enter/leave). If this step cannot be performed, the zones can be learned online using a statistical method on a part of the sequence. In the results part, only the offline method is evaluated because the online method to detect zones requires long video sequences (more than one hour) with a sufficient number of people to be effective.

Object appearing/disappearing in zone: when a detected object with a new ID appears or disappears (new tracklet), we check if this happens in a zone where the object can leave/enter the scene. If this happens outside of these zones, an error is detected.

Spatial overlap level with background elements: depending on the scene meta-data, it is possible to know if the object is being occluded by a background element.

Results

The general methodology to evaluate the proposed approach is described in figure 3.

The online evaluation framework is evaluated on the public datasets PETS2009 and Caviar. To experiment the proposed approach, we use a detection algorithm based on standard background subtraction. For tracking, two different algorithms are tested. One is a multi-feature tracker (Tracker 1) that uses 3D position, shape, dominant color and HOG descriptors. The other one is an algorithm based on graph partitioning (Tracker 2).

Methods

MOTA MOTP Berclaz et al. [START_REF] Erdem | Performance measures for video object segmentation and tracking[END_REF] 0.80 0.58 Shitrit et al. [START_REF] Berclaz | Multiple object tracking using k-shortest paths optimization[END_REF] 0.81 0.58 Henriques et al. [START_REF] Kalal | Forward-backward error: Automatic detection of tracking failures[END_REF] 0.85 0.69 Zamir et al. [START_REF] Bak | Multipleshot Human Re-Identification by Mean Riemannian Covariance Grid[END_REF] 0.90 0.69 Milan et al. [START_REF] Piciarelli | Trajectory clustering and its applications for video surveillance[END_REF] 0 For the PETS sequence S2.L1, we use the CLEAR MOT metrics in order to compare with the state of the art. The metric MOTA is Multiple Object Tracking Accuracy which measures the number of false positives, false negatives and ID switch. The metric MOTP is Multiple Object Tracking Precision which measures the alignment of the tracking results with the ground truth.

Table 2 gives the results of the tracking algorithm with and without the global tracker with the two trackers.

The results show that while tracker 1 has difficulty providing reliable output results, the global tracker is able to improve the quality of the results by increasing the MOTA from 0.62 to 0.85 and the MOTP from 0.63 to 0.71. In the case of a tracker that already gives satisfying results (tracker 2), the global tracker is able to make the results even better by increasing the MOTA from 0.85 to 0.90 while keeping the same value for the MOTP (0.74).

The global tracker is also evaluated on the Caviar dataset. For this dataset, another set of metrics is used according to the state of the art: Mostly Tracked (MT) means that more than 80% of the trajectory is correctly tracked, Partially Tracked (PT) means that between 20% and 80% of the trajectory is correctly tracked and Mostly Lost (PT) means Method MT (%) PT (%) ML (%) Li et al. [START_REF] Maggio | Video Tracking: Theory and Practice[END_REF] 84.6 that less than 20% of the trajectory is correctly tracked. Table 3 gives the results of the tracking algorithm with and without global tracker with trackers 1.

The results show that the global tracker is able to improve the tracking results by increasing the length and the precision of the tracklet. The only drawback is that it fails to correct the tracklets that are already mostly lost due to the lack of correct input detection.

The figure 4 shows the comparison between the percentage of errors found by the global tracker and the percentage of ground truth errors found in the tracking output for sequence S2.L1.View1 of PETS2009. For the most part, the global tracker is able to successfully detect and classify the errors (both curbs match). However it fails at the beginning of the video (around frame 75) because the global tracker has difficulties to detect errors from a tracklet that has the same error since its appearance (for example, when a background element becomes tracked).

Conclusions and future work

In this paper, we have presented a new framework for evaluating the quality of people trajectories during runtime without ground truth. This framework called global tracker is able to determine if anomalies appear in the tracking output. It can then classify these anomalies into errors or normal phenomena. These results are applied to a constrained clustering algorithm to handle long-term occlusions and people leaving and re-entering the scene. The global tracker is tested on two datasets and shows promising results. The next step of this global tracker is to select and choose the more adequate set of features automatically. A feedback to the tracking algorithm could also be provided in the case of a self-tuning algorithm. A future version of the global tracker will also be able to determine during runtime which tracking algorithm is the best for the current sequence.

Figure 1 .

 1 Figure 1. The tracklet representation within the time window of the global tracker

Figure 2 .

 2 Figure 2. The re-acquisition challenge: correcting errors due to occlusions (ID 142 on the first frame becomes 147 on the last frame) and track people that are leaving the scene and re-entering (ID 133 on the first frame becomes 151 on the last frame

Figure 3 .

 3 Figure 3. The methodology to evaluate the proposed approach is based on the comparison with the ground truth

Figure 4 .

 4 Figure 4. Comparison between the percentage of ground truth errors per frame (red) and the percentage of errors found by the global tracker (blue) on sequence S2.L1.View1 of PETS2009 using tracker 1

Table 1 .

 1 Features used for experimentation

Table 2 .

 2 Tracking results on sequence S2.L1.View1 of the PETS2009 dataset

	.90	0.74

Table 3 .

 3 Tracking results on the Caviar dataset

			14.0	1.4
	Kuo et al. [9]	84.6	14.7	0.7
	Tracker 1	78.3	16.0	5.7
	Tracker 1 + global tracker	86.4	8.3	5.3

Acknowledgments

This work has been supported by the Conseil Regional of Provence-Alpes-Côte d'Azur (PACA), France.


An open question : How to solve efficiently 3D frictional contact problem ?

V. Acary * , M. Brémond * In this talk, we want to discuss possible numerical solution procedures for the following discrete frictional contact problem [START_REF] Acary | Numerical methods for nonsmooth dynamical systems[END_REF]. Let n c ∈ IN be the number of contact points and n ∈ IN the number of degree of freedom. Given a symmetric positive (semi-)definite matrix M ∈ IR n×n , a vector f ∈ IR n , a matrix H ∈ IR n×m with m = 3n c , a vector w ∈ IR m and a vector of coefficients of friction µ ∈ IR nc , find three vectors v ∈ IR n , u ∈ IR m and r ∈ IR m such that

M v = Hr + f, u = H ⊤ v + w, û = u + g(u), K ⋆ ∋ û ⊥ r ∈ K, (1)
where g(u) is a nonsmooth function and K ⊂ IR 3nc is a Cartesian product of second order cone in IR 3 . For each contact α, the unknown variables u α ∈ IR 3 (velocity or gap at the contact point) and r α ∈ IR 3 (reaction or impulse) are decomposed in a contact local frame

(O α , N α , T α ) such that u α = u α N N α + u α T , u α N ∈ IR, u α T ∈ IR 2 and r α = r α N N α + r α T , r α N ∈ IR, r α T ∈ IR 2 .
The set K is the cartesian product of Coulomb's friction cone at each contact, that is

K = α=1...nc K α = α=1...nc {r α , r α T ≤ µ α |r α N |} (2)
and K ⋆ is dual. The function g is defined as

g(u) = [[µ α u α T N α ] ⊤ , α = 1 . . . n c ] ⊤ .
This problem is at the heart of the simulation of mechanical systems with 3D Coulomb's friction and unilateral constraints. It might be the result of the time-discretization by event-capturing time-stepping methods or event-detecting (event-driven) techniques of dynamical systems with friction or the result of a space-discretization (by FEM for instance) of the quasi-static problems of frictional contact mechanics [START_REF] Acary | Recent Advances in Contact Mechanics[END_REF]. On the mathematical programming point of view, the problem appears as Second Order Cone Complementarity Problem (SOCCP). If the nonlinear part of the problem is neglected (g(u) = 0), the problem is an associated friction problem with dilatation, and by the way, is a gentle Second Order Cone Linear Complementarity Problem (SOCLCP) with a positive matrix H ⊤ M -1 H (possibly semi-definite). When the non-associated character of the friction is taken into account through g(u), the problem is non monotone and nonsmooth, and then very hard to solve efficiently.

In this talk we will recall a result for the problem in (1) which ensures that a solution exists [START_REF] Acary | A formulation of the linear discrete Coulomb friction problem via convex optimization[END_REF]. In this framework, we will list several algorithms that have been previously developed for solving the SOCCP (1) mainly based variational inequality and nonsmooth equations reformulations. On one hand, we will show that algorithms based on Newton methods for nonsmooth equations solve quickly the problem when they succeed, but suffer from robustness issues mainly if the matrix H has not full rank. On the other hand, the iterative methods dedicated to solving variational inequalities are quite robust but with an extremely slow rate of convergence. To sum up, as far as we know there is no option that combines time efficiency and robustness. To try to answer to this question, we develop an open collection of discrete frictional contact problems called FCLIB http://fclib.gforge.inria.fr in order to offer a large library of problems to compare algorithms on a fair basis. In this work, this collection is solved with the software Siconos and its component Siconos/Numerics http://siconos.gforge.inria.fr .