Guillaume Rosinosky Bonitasoft

Franc ¸ois Charoy Samir Youcef
email: samir.youcef@loria.fr

An Efficient Approach for Multi-tenant Elastic Business Processes Management in Cloud Computing environment

Keywords: BPM, Cloud, Elasticity, Multi-tenancy, Bi-criteria optimization

Even though the cloud computing paradigm has proven benefits, it faces a serious problem that can compromise its commercial success. It concerns the lack of efficient approach for using optimally the available resources. For this, several approaches have been proposed. However, they suffer from several shortcomings. Often only one objective is taken into account, expressing all operations in terms of cost. Furthermore, business processes should be insured with elasticity and multi-tenancy mechanism while adjusting the available resources to the dynamic load distribution. The proposed approach aims to optimize two conflicting objectives, namely the number of migrations of tenants and the cost incurred using a set of resources. It allows to take into account the multi-tenancy property and the Cloud computing elasticity, and is efficient as shown by an extensive experimentation based on real data from Bonita BPM customers.

I. INTRODUCTION

For years, software have been sold and installed in customers premises and operated by their IT teams. This business model requires the software to be deployed on the user's computer infrastructure. The customer will ensure its maintenance and transition between versions. Recently, several businesses adopted a new paradigm where the software is operated in a data center and accessed remotely. This new way to consume software, known as cloud computing, transfers the burden of IT management to the software provider. The latter must ensure the required quality of service (QoS) at the lowest possible operating cost for its customers. Achieving that goal efficiently remains an issue. Here, we consider the delivery of a business process execution as a service as part of a Business Process Management System (BPMS) [START_REF] Weske | Business process management: concepts, languages, architectures[END_REF]. The goal of a BPMS is, among others, to control the execution of business processes, according to their model. To provide elastic business process management as a service (BPMaaS) means to accommodate the service requirement of a set of customers and to support the execution of their processes with the required level of quality of service, for the best cost. More precisely, we want that at each point in time the available resources match the current demand as closely as possible. Thus, we must set up an elastic infrastructure [START_REF] Lehrig | Scalability, Elasticity, and Efficiency in Cloud Computing: a Systematic Literature Review of Definitions and Metrics[END_REF] adapted to the specific requirements of business process execution. Generic auto scaling techniques provided by cloud providers do not usually take into account software usage metrics, but rather system or OS level metrics such as CPU or memory. We argue that we can use business processes and their history of usage to anticipate the IT resource allocation need. It will be useful to achieve an efficient infrastructure elasticity for business process execution.

In this paper, we consider a service provider that wants to provide process execution as a service. The used BPMS must support multi-tenancy, i.e. it can accommodate several customers on the same installation. We assume that it is possible to migrate a tenant from a BPMS installation to another BPMS installation with a limited interruption of service. Considering these assumptions, our goal is to propose a way to ensure the required quality of service for each tenant at the minimal cost while minimizing tenant migrations. That requires to adjust the number of computers to the load required for each tenant while minimizing the number of migrations of tenant from one set of resources to another. We propose an efficient bi-criteria approach based on tenant migrations number and cost optimization, solving iteratively for each number of migrations a repacking step for the existing resources, followed by a variable cost and size bin packing, and by a step of consolidation. We compare this approach to the solving of the corresponding model, using data based on customer information.

The remainder of the paper is organized as follows. In the next section, we discuss the problem in more details and we describe our hypothesis and the limits of this study. Section III summaries the existing work. Section IV gives our problem formulation of resource allocation to execute business processes in cloud computing environment. This section also presents the optimization objectives, namely the cost incurred using a set of resources and the number of tenant migrations. Section V presents our proposition to provide an approximate solution to the problem that can be computed in polynomial time. In section VI, we describe the evaluation that we have conducted using Bonita BPM [START_REF]Bonitasoft[END_REF] as an example of BPMS and Amazon Web Services [START_REF]Amazon EC2 Instance Comparison[END_REF] as the cloud provider. We show that it diverges very reasonably from an exact solution that could not scale. Section VII concludes the paper and describes its future extensions.

II. MOTIVATION AND HYPOTHESIS

Providing business process execution as a service requires support for an operator to manage execution of thousands of processes from hundreds of customers at the same time on its infrastructure. This requires an environment able to adjust itself to the load of the different customers automatically. We could rely on basic scalability techniques available in IaaS systems, and add more computing power in a BPMS installation when the load increases. This is not easy since a BPMS is database write intensive and we would reach a maximum number of customers on the same cluster. In the literature, many consider business process oriented optimization, at various level of elasticity completion, as we will see in the existing work part.

We consider a more lightweight approach based on a multi-tenant BPM solution where each tenant share the resources. More precisely, we consider a tenant-centric BP-MaaS elasticity, by looking at tenant usage data, namely the total number of BPM tasks per tenant and unit of time. We discuss about distribution of tenants and their activities on a cloud infrastructure. We want to support as many tenants as possible at the minimal cost, while ensuring a defined quality of service based on task execution time.

In order to distribute tenants on the best configurations, we will need to be able to migrate tenants. In our case, tenant migration is the action of moving customer software and data from a cloud configuration to another. When a tenant needs more computing power than the current configuration can provide, either we migrate it to a bigger configuration in accordance with the QoS of the customer, or we migrate other tenants from the same configuration to free computing power. On the other way, we should move a tenant which requires less resources. We assume that tenant awareness, automated migration, and tenant consolidation are totally supported by the BPM engine and its corresponding database systems. Migrations usually have negative effects on the origin and destination cloud configurations and the tenants they host. We consider that a tenant migration produces a service interruption that is acceptable for customers. It is realistic since solutions for live migration exist for databases [START_REF] Das | ElasTraS: An elastic, scalable, and self-managing transactional database for the cloud[END_REF]. We also assume that we can do migration operations in less than one unit of time (an hour in our case). However migrations could cause QoS breaks, and this is why we have chosen to minimize it aside of the cost.

As many other applications, a BPM stack requires many software elements (see figure 1). It needs one or several instances of ACID compliant relational database systems which it uses to store process data, one or several web application servers who will contain the BPM Engine, load balancers in the case of clustered applications, and other services used in distributed applications, such as supplement web servers, message brokers, etc. We propose to measure BPM task execution throughput to estimate the required performance for tenants and the capability of various cloud configurations. It is also our second QoS metric. Task execution throughput is strongly related to the transaction performances of the underlying database. In order to execute the tasks of a BPM process, the BPM engine may execute one or several transactions in its database, before, during and after the execution of the task. A transition in BPM process also triggers state changes in the database. Database transactions are often used as a performance metric in precedent works and in industry [START_REF] Gao | SaaS performance and scalability evaluation in clouds[END_REF], [START_REF] Curino | Workload-aware database monitoring and consolidation[END_REF], [START_REF] Elmore | Characterizing tenant behavior for placement and crisis mitigation in multitenant dbmss[END_REF]. In order to distribute the tenants on the cloud configuration, we need to have a way to estimate its required load. We have some knowledge on the behavioral patterns of every tenant for a given period of time. This information will be used to organize resources and distribute the load between configurations. This could be determined manually (in the contract part between the customer and the service provider), or using some prediction system.

Regarding the cloud resources part, we assume that we have access to a public cloud provider with unlimited resources, and on demand billing. Compute resources are paid per hour and their price is constant. We consider that compute resources have stable performance. For instance a stack can be composed of a compute instance for the database, another one for the BPMS. We name a defined group of compute instances a cloud configuration. Each cloud configuration has a defined capability and price. We assume that each tenant can fit on at least one cloud configuration type, i.e the sum of its activities can be supported by the configuration type which can handle the most activity count per hour. Small tenants can share configurations. We neglect the effect of tenant execution on the other tenants executing on the same configuration : we will consider that tenants' workload adds up. For instance, a tenant with 10000 tasks per hour is similar to two tenants with 5000 tasks per hour.

These hypothesis ensure that the framework remains realistic. It allows us to define a model that we can optimize to enforce the best operation conditions for BPM tenants. In the next section, we explore the current solutions for similar problems.

III. RELATED WORK

Schulte et al. [START_REF] Schulte | Elastic Business Process Management: State of the art and open challenges for BPM in the cloud[END_REF] made a review on the current status on BPM elasticity, and the different important criteria. [START_REF] Hoenisch | Self-Adaptive Resource Allocation for Elastic Process Execution[END_REF], [START_REF] Janiesch | Optimizing the Performance of Automated Business Processes Executed on Virtualized Infrastructure[END_REF], [START_REF] Euting | Scalable Business Process Execution in the Cloud[END_REF] proposed solutions for BPM elasticity. They aim to distribute processes without taking into account multi tenancy. They consider mainly CPU and RAM for resource consumption. In [START_REF] Sellami | Elastic Multi-tenant Business Process Based Service Pattern in Cloud Computing[END_REF], Sellami et al. propose a multi tenant approach based on customizable thresholds. It does not take into account migration cost or the database tier.

A lot of papers study virtual machine assignment in datacenters such as [START_REF] Wolke | More than bin packing: Dynamic resource allocation strategies in cloud data centers[END_REF], [START_REF] Li | On dynamic bin packing for resource allocation in the cloud[END_REF]. However these works consider only the scheduling part, as the resources in data-center are fixed.

Assignment algorithms usually do not take into account migrations. Another term for this is reassignment, and, to the best of our knowing, much less attempts have been made on this subject. However, a well known initiative is the Google Reassignment Problem [START_REF]Challenge ROADEF/EURO 2012 : Machine Reassignment[END_REF] where the problem is mono objective and sums up load, balance, process, service, and program move cost. Several propositions to solve this problem have been made. The best ones use variable neighborhood search [START_REF] Gavranović | Variable Neighborhood Search for Google Machine Reassignment problem[END_REF], [START_REF] Jaśkowski | A hybrid MIP-based large neighborhood search heuristic for solving the machine reassignment problem[END_REF], or constraint programming [START_REF] Brandt | Constraint-based large neighborhood search for machine reassignment: A solution approach to the ROADEF/EURO challenge 2012[END_REF]. However these approaches aim data centers, who have a predefined set of machines, and assume a fixed cost for migrations.

Other attempts such as multi-tenant relational database management system [START_REF] Elmore | Characterizing tenant behavior for placement and crisis mitigation in multitenant dbmss[END_REF] or generic SaaS elasticity have been made for this problem, but there is no known work who take into account BPMS cloud migrations and cost in a multiobjective way.

IV. OUR MODEL FOR ELASTIC MULTI-TENANT BPM IN

THE CLOUD The objective of our study is to minimize the cost of computing resources and the number of tenant migration that cause QoS degradation while maintaining enough computing power to execute all processes. Thus we face a multi-objective problem who can be tackled using three approaches: (i) the mono-criterion approach, (ii) theconstraints and (iii) the multi-criteria approach. The criteria that we consider are conflicting. If we consider only the cost objective part, the best solution could provoke the migration of all the tenants. But as migrations can lead to QoS degradation, we will not consider it alone. On the other side, minimizing the migration objective can lead to leave tenants on expensive configurations. Therefore, the most appropriate approach is the multi-criteria one. We consider the two objective functions simultaneously. The most used optimality notion when we deal with multi-criteria problems is the Pareto optimality concept defined as follows.

Definition 1. We say that a solution x ∈ X is a Pareto solution (or belong to the Pareto front) iff:

• x ∈ X, ∀ i ∈ {1, ..., n}, f i (x ) ≤ f i (x) ∧ ∃ j ∈ {1, ..., n}, f j (x ) < f j (x).
We assume that an instance of the BPMS is deployed on a cloud configuration consisting in several cloud resources, for instance one for the database, on for the application server etc. We rely on several configuration types with different cloud instance types. We consider that a configuration type has a cost, and a throughput capability. This cost is the total of the cost of its cloud resources for a time slot of one hour, since it is the unit of cost for most public cloud providers.

Let the following variables :

• J , the set of possible configurations with m its cardinality • C j , and W j , respectively the cost and the capacity for the configuration j • I, the set of tenants with n its cardinality • w i , the needed capacity for the tenant i during time slot k + 1 • x j i (k), the assignment of tenant i to configuration instance j during time slot k • y j (k), the activation of configuration j during time slot k + 1 We define an indicator function 1 {xj i (k) =xj i (k+1)}. which corresponds to actual tenant migration which will be equal to :

0 if x j i (k) = x j i (k + 1) 1 if x j i (k) = x j i (k + 1)
We aim to minimize the total configurations cost and the number of migrations for the time slot k + 1 from the configurations distribution at time k where we apply the needed capacity at time k + 1. The problem can be defined as follows:

min f 1 = j∈J j C j y j (k + 1) (1)
min f 2 = j∈J j i∈I i 1 {xj i (k) =xj i (k+1)} x j i (k + 1) (2)
We have the following constraints :

∀i ∈ I j∈J j x j i (k + 1) = 1 (3) ∀j ∈ J i∈I i w i x j i (k + 1) ≤ W j y j (k + 1) (4)
∀i ∈ I, ∀j ∈ J , x i j ∈ {0, 1}, y j ∈ {0, 1}

Equation 1 presents the cost objective, and equation 2 the migration quantity objective. Equation 3indicates that a tenant should be assigned to only one configuration. Equation 4 means that the sum of the required throughput of tenants on one resource should be less or equal than the capability of this resource.

For a defined number of resources, and without taking into account migrations, this is a classic assignment problem. However the resource allocation part and the migration part makes it more difficult to solve. Since, as we will precise in the next section, the problem is NP-hard, it is appropriate to propose heuristic algorithms rather than exact algorithms that would not scale.

V. AN EFFICIENT APPROACH FOR MULTI-TENANT ELASTIC BUSINESS PROCESS EXECUTION IN CLOUD CONTEXT

The approach we propose is composed of two parts: (i) the resource allocation part and (ii) the scheduling part. Resource allocation and task scheduling are NP-hard problems. Greedy heuristics, integer and mixed integer linear programming, meta-heuristics, or constraint programming [START_REF] Lombardi | Optimal methods for resource allocation and scheduling: a cross-disciplinary survey[END_REF] are often used to deal with such problem. Greedy algorithms are heuristics who make the assumption that by aiming at the best local solution, a good global solution is reachable. This type of algorithm is usually simple and fast, but could get stuck in a local optimum. Integer linear programming (ILP) and mixed integer linear programming (MILP) are usual operational research algorithms, seeking to minimize an objective function under constraints with discrete variables (ILP), or mixed discrete and continuous variables. Solving these problems usually include LP relaxation in order to find valid solutions with continuous methods. However, depending on the problem size the computing can be long, and a solver is needed in order to resolve the problem.

Here, we choose to observe the number of migrations first since it is discrete, and to calculate the best cost for each migration number with an heuristic. Reducing the cost requires to reduce the number and the cost of configurations. In our approach, apart of the throughput constraint, we decided not to consider swapping tenants and to focus on resource reduction. We show an example of configurations and their tenants in figure 2.

The minimum number of tenants we must move is the number of tenants that doesn't fit anymore in their current resources. We divide them among two classes :

• tenants that we must migrate because their future throughput is greater than the capability of their current resource. The migration of these tenants is mandatory. We name these type of tenants unfit tenants. These are the crossed line boxes in the figure 2 such as T6. An example of distribution of tenants and configurations. Three configurations contain ten tenants in this situation. The outer boxes represent the configurations, and the inner ones the tenants. Crossed stripped boxes represent the unfit tenants, that can't stay anymore in their configuration. Single stripped boxes represent the overloading tenants. Blank boxes represent tenants that fit in their current resource.

• tenants which, put together, overload their current resource. We choose to "remove" from the resources and force the migration of the biggest tenants in each overloaded resource until none is overloaded anymore. We name these type of tenants the overloading tenants.

In figure 2 they are the stripped boxes such as tenants T9 and T10.

The main loop is described in algorithm 1. At each count of migrations, we consider the combination of resources containing precisely the number of tenants we wish to migrate if we add to it the number of mandatory tenants. This is a subset sum problem, where we use a simple recursive approach. In figure 2, the minimum number of migrations is 3 (T9, T10 and T6), and it is possible to also reassign 4 or 6 tenants -by removing respectively conf1 or m3 medium 1 0 configuration, but not 5 as there is no combination of resources hosting 5 tenants. The number of possibilities increases exponentially, which will lead to memory and CPU time problems. Moreover, there are cases where the algorithm could be slower than the exact method in particular when the resource quantity is high. Let's imagine we have 50 tenants, that are all hosted on their own configuration. In the case where we don't limit the number of subset sum combinations, for 25 migrations we will have C 50 25 which means more than 10 14 combinations to test. This number of migrations is very high and can't be computed in acceptable time. This is why it is important, even if it gives less interesting results, to limit the number of the subset sum combinations. In the experimentation part, we have considered 1000 resource combinations as a limit.

For each possible combination, we then virtually suppress the concerned resources, and consider the mandatory tenants and the orphan tenants resulting from the suppression of the resources. In our heuristic we chose to replace at best these tenants in the existing resources -that we cannot return distributionResult delete without adding more migrations. For this part, we used a best fit decreasing approach, where we aim to load the tenants into the most appropriate resources.

After this step, we must create new resources for the remaining tenants. At this point, the existing resources can no longer be filled. We use a variable cost bin packing heuristic with the remaining tenants, more precisely a variation of Iterative Best Fit Decreasing algorithm [START_REF] Kang | Algorithms for the variable sized bin packing problem[END_REF].

Since we have two parts, one looking to existing resources and the other creating new resources, both generate unused space that should be used at best. In order to solve this problem, we have added a consolidation step which tries to delete resources one by one and replace if possible the resulting orphan tenants with the repacking procedure. This consolidation step is inspired by one of the operators of the local search used in [START_REF] Hemmelmayr | Variable neighbourhood search for the variable sized bin packing problem[END_REF]. We adapted it by taking into account only resources who contain only initially orphan tenants.

A configuration combination is kept only if is less expensive than the previous computed, in order to obtain the Pareto front (as we compute from the minimum to the maximum number of migrations). Figure 3 shows an example of cost migration. The best solutions are for 3, and 7 migrations. Other solutions such as 6, 9, 10 migrations are useless as they involve more migrations for the same price. There is no solution below 2 migrations, and for 5 or 8 migrations.

VI. EXPERIMENTAL RESULTS

In this section, we present a summary of the results we obtained based on real data from Bonitasoft customers. In order to evaluate the quality of the results using our approach, given the fact that the migration criterion is Figure 3. This represents the best results of our algorithm after we run it against the configuration in figure 2. The bigger dots represents the points in the Pareto frontier. Absence of dot means that there is no solution for the corresponding number of migrations. discrete, we have compared for each migration number the cost between the heuristic and the results given by a solver.

We need to know first the size of each cloud configuration in term of throughput capability. We must also estimate the size of the tenants in term of BPM task throughput. For this, we use Bonita BPM [START_REF]Bonitasoft[END_REF] open-source business process management and workflow suite. Bonita BPM is a multi-tenant BPMS where several customer can have their applications on the same Bonita BPM instance and uses a shared-schema strategy [START_REF] Chong | Multi-Tenant Data Architecture[END_REF] in order to manage tenants. We have launched tests on Bonita BPM 7.0.3 using PostgreSQL 9.3 database, each on a separated EC2 instance on Amazon Web Services public cloud. A business process definition used by Bonitasoft for their internal performance tests has been used in order to compare the various configurations. The business process which we will name "standard process" contains twenty sequential automated tasks, each one launching one connector computing the 25 first Fibonacci numbers. We have launch each time 3000 processes with an injector tool on various cloud configurations and on different parallel process number injections. Our goal is to observe the correlation between the number of parallel processes and the average computing duration for each process considering each configuration, in order to find each configuration mean BPM task throughput. As we don't know the duration of a task, we have computed the number of tasks for a given process duration. As the performances stay globally linear when we inject more processes in the engine (apart from the first ones, when we can assume there is not a lot of usage of the parallelism of the processor), we consider that it is possible to do a simple linear regression in order to find the capability in parallel processing. We have computed the corresponding process throughput for a duration of 10 second, by linear regression between the two corresponding values. We use this process throughput to compute the corresponding task throughput, by looking at the corresponding total duration and dividing it by the total number of tasks (here 60000). This gives us the mean task throughput we can expect for a mean duration of 10 seconds of standard process. In order to use realistic performances and prices, we have used these configuration's task throughput (in table I), and prices in our experimentation.

For the size of the tenants, we have used anonymous customer information fragments where we have observed the minimum and the maximum task throughput. In our experimentation, for each tenant i, we used an uniform In order to test our approach we have implemented the exact model with a linear optimization solver. As the multiobjective characteristic of the problem complicates the computing, we used the same migration number approach. For this we have transformed the objective function described in equation 2 in a constraint, as seen in equation 6, where M is the number of migrations for which we want to have the solution. Furthermore, J is initialized with all the possible tenants and configuration combinations.

1 {xj i (k) =xj i (k+1)} x j i (k + 1) = M (6)
This model can be resolved with linear programming solvers. We have used PuLP linear programming toolkit [START_REF] Mitchell | PuLP: a linear programming toolkit for python[END_REF] coupled with Gurobi [START_REF]Gurobi Optimization[END_REF] linear solver on a AWS c4.xlarge EC2 instance. A first step is to determine the minimum number of migrations, and compute the optimal cost without considering the migrations (by removing the constraint described in equation 6). We then compute the optimal cost for each number of migrations between the minimum number and stop computing once we reach the optimal cost. We have configured the solver with a time limit of 3 hours for a migration number computation.

For the heuristic test, we have launched 30 times the uniform distribution we discussed before for various number of tenants. We began with a distribution where all the tenants are on a minimum configuration, without considering the required load. We have then launched two times the heuristic. Indeed, this algorithm will be launched sequentially with an previously computed distribution. The results described in table III shows the second launch efficiency and duration. In order to compare the two methods, we launched the exact algorithm on the same tenant distributions. In some cases, the solver was not able to find a solution in the time limit. The heuristic Pareto frontier percent corresponds to the ratio of migration optimum found in the heuristic which are optimum in the exact method. We have computed the heuristic efficiency for all the heuristic Pareto frontier, with the distance to the corresponding price in the exact method. In addition, based on the results, we can see that the relative error does not exceed 4.1%. Furthermore, in the worst case that we studied, the Pareto front percentage is 66.22% and the heuristic stay faster than the exact algorithm duration.

The results we obtained show that this heuristic takes a fraction of the time used in an optimization linear solver, gives good results with small errors, and most optimal migrations number that we obtain with the exact method. The exact algorithm does not scale with the number of tenants. It gives less and less results in a acceptable running time. Even if the Pareto front percent decreases with time, the heuristic's cost efficiency stays at a very low level. The last point shows that the two Pareto front are very close.

We have seen that even if we consider only resources combinations and ignore tenants swaps between active configuration, the heuristic gives good results for most of the exact Pareto frontier, as the cost stay very close to the optimal cost.

Despite the use of an intuitive algorithm for the subset sum part by limiting the number of returned combinations, the results are very encouraging. This algorithm should be able to give a limited number of random solutions without computing all the results. In our case, using an approximate version of the subset sum method could greatly speed up our heuristic, as it consists in most of the running time from 40 tenants.

Another enhancement to speed up the heuristic is to elaborate a multi-threaded version of this algorithm in order to benefit from the architecture of multi-core processors while computing the different resources combinations. For instance, several resource combinations could be computed simultaneously.

VII. CONCLUSION

In this paper, we described an effective approach for business process execution as a service on the Cloud. This approach considers tenants as a whole and proposes to minimize two conflicting objectives, the execution cost and the total number of tenants migration. We have validated this approach with an experimentation that shows the efficiency of our algorithm, on data based on Bonitasoft customer usage. We have considered configuration cost based on AWS cost profiles, and tested. We compared the results with an exact method. As [START_REF] Curino | Workload-aware database monitoring and consolidation[END_REF] notes, distribution techniques are not totally orthogonal to consolidation methods. Our method could be used with other criteria than BPM tenants and task throughput. For instance, we could use the algorithm with other RDBMS dependent applications on cloud instances, using QoS constraints on the number of HTTP requests. With this heuristic architecture, it is conceivable to use multiple different algorithms for the bin packing part, the overloading tenants choice, or even the subset sum algorithm. For instance, testing multiple overloading tenants alternatives or using other variable size and cost bin packing algorithms such as [START_REF] Haouari | Relaxations and exact solution of the variable sized bin packing problem[END_REF] could be interesting and produce even better results. The next step for this work is to consider optimization for several consecutive time slots in order to optimize the cost not per hour but for a whole day, in order to take into account customer QoS requirements. We will also study the possibility to use other distributions that better adjust the throughput and customer distribution.

Figure 1 .

 1 Figure 1. Simple BPMS architecture. Here we have a clustered version of a BPMS using a clustered database, behind a load balancer. The user can use its own application interfaced to the BPMS, or access directly to this last one via end-user interfaces. The BPMS may contact other applications via web services.

Figure 2 .

 2 Figure 2.An example of distribution of tenants and configurations. Three configurations contain ten tenants in this situation. The outer boxes represent the configurations, and the inner ones the tenants. Crossed stripped boxes represent the unfit tenants, that can't stay anymore in their configuration. Single stripped boxes represent the overloading tenants. Blank boxes represent tenants that fit in their current resource.

Algorithm 1

 1 Main loop 1: procedure MAIN LOOP(tenant distribution for previous hour, needed throughput) unf it ← tenants whose throughput is bigger than their current resource 4: overloading ← biggest tenants to remove until there is no more overloaded resource 5: mandatoryT enants ← overloading ∪ unf it 6: minM igrations = size(mandatoryT enants) for i = minM igrations → maxM igrations do 10: costByM igration[i] ← +∞ 11: possibleResourcesCombinations ← FINDSUBSETSUM(i, resources, resultnumber l imit) 12: for all resourceCombination ∈ possibleResourcesCombinations do 13: newDistribution ← distributionresources ∈ resourceCombination 14: tenantsT oRepack ← mandatoryT enants tenants ∈ resources ∈ resourceCombination 15: REPACKING(newDistribution, tenantsT oRepack) 16: BINPACKING(newDistribution, tenantsT oRepack) 17: CONSOLIDATION(newDistribution, tenantsT oRepack) 18: if cost(newDistribution) ≤ costByM igration[i] then 19: costByM igration[i] ← cost(newDistribution) 20: distributionResult[i] ← newDistribution 21:

Figure 4 .

 4 Figure 4. Test architecture used for the cloud configuration capability determination. Here we show three different databases and application servers.

  the maximum observed throughput. We have capped at the maximum configuration throughput the task throughput for each tenant in order to be able to fit them in cloud configurations. We show a summary of the data we collected in in table II.

	DB inst. type	AS inst. type	price	task TP	task TP per $
	m1.small	m1.small	0.094	8.120	86.392
	m3.medium	m3.medium	0.146	17.762	121.660
	m3.medium	m3.large	0.219	24.669	112.644
	m3.medium	m3.xlarge	0.366	25.293	69.107
	m3.large	m3.xlarge	0.439	41.147	93.730
	m3.large	m3.2xlarge	0.693	42.813	61.868
	m3.xlarge	m3.2xlarge	0.839	45.274	53.962
			Table I
	PRICE, MEAN TASK THROUGHPUT, AND MEAN TASK THROUGHPUT BY
	DOLLAR FOR A MEAN STANDARD PROCESS DURATION OF 10 SECONDS
	distribution in interval [w min i throughput, where w min i and w max , w max ] to adjust the customer i i represent respectively
	the minimum and customer observed interval (in days)	minimum	maximum
	A	4		2	45
	B	1		14	16
	C	45		0	45
	D	7		1	3
	E	45		5	45
	F	550		0	4
		Table II
	SYNTHESIS OF THE USED CUSTOMER DATA. FOR EACH CUSTOMER, THE
	OBSERVED INTERVAL, THE MINIMUM AND THE MAXIMUM TASK
	THROUGHPUT PER SECOND FOR EACH HOUR.

VIII. ACKNOWLEDGMENT

The authors would like to thank Gurobi for the usage of their optimizer, and Amazon Web Services for the EC2 instances credits (this paper is supported by an AWS in Education Research Grant Award).


X Roynard
email: xavier.roynard@mines-paristech.fr

J-E Deschaud

F Goulette

FAST AND ROBUST SEGMENTATION AND CLASSIFICATION FOR CHANGE DETECTION IN URBAN POINT CLOUDS

Keywords: Urban Point Cloud, Mobile Laser Scanning, Segmentation, Classification, 3D-Features

Change detection is an important issue in city monitoring to analyse street furniture, road works, car parking, etc. For example, parking surveys are needed but are currently a laborious task involving sending operators in the streets to identify the changes in car locations. In this paper, we propose a method that performs a fast and robust segmentation and classification of urban point clouds, that can be used for change detection. We apply this method to detect the cars, as a particular object class, in order to perform parking surveys automatically. A recently proposed method already addresses the need for fast segmentation and classification of urban point clouds, using elevation images. The interest to work on images is that processing is much faster, proven and robust. However there may be a loss of information in complex 3D cases: for example when objects are one above the other, typically a car under a tree or a pedestrian under a balcony. In this paper we propose a method that retain the three-dimensional information while preserving fast computation times and improving segmentation and classification accuracy. It is based on fast region-growing using an octree, for the segmentation, and specific descriptors with Random-Forest for the classification. Experiments have been performed on large urban point clouds acquired by Mobile Laser Scanning. They show that the method is as fast as the state of the art, and that it gives more robust results in the complex 3D cases.

INTRODUCTION

With the recent availability of massive urban point clouds, we see an interest in automatic segmentation and classification of this data for numerous tasks dealing with city analysis and surveying. Such as emergency simulation, accessibility analysis, city modelling, itinerary planning, maintenance, all kind of network management (rails, road ,electricity, telecommunication, water, gas, etc).

Then we need to extract semantic data of the point clouds, what can be summarized in giving a segmentation and a classification of the point clouds in relevant objects. And for the application of change detection, being able to compare different segmented clouds. In the case of parking surveys, we must detect and segment sub-clouds that represent parked cars, then compare them between different passages.

There are already methods [START_REF] Serna | Detection, segmentation and classification of 3d urban objects using mathematical morphology and supervised learning[END_REF]) that automatically segment and classify urban point clouds in reasonable time. But this methods project the point clouds in 2D and lose a lot of information, as cars under trees or pedestrians under balcony.

We propose an automatic algorithm to segment and classify urban point clouds in similar processing time, but keeping 3D information and then with more robustness.

The point cloud is projected on a 2D-grid for ground extraction by region-growing. Then we project the cloud on a 3D-grid for object segmentation. We calculate 3D descriptors on each segmented object. Finally using a Random-Forest model to perform classification.

Our method has enabled us to create a sufficiently large dataset to test the classification algorithm. We test the classification performance and the importance of each descriptor used. In addition we measure the computation time for each step of the method to identify bottlenecks. This paper is organized as follows. Section 2. reviews related work in the state of the art. Section 3. explains our methodology. Section 4. describes the experiments we used to give the results in section 5., and conclude in section 6..

RELATED WORK

There are multiple methods of segmentation and classification of urban point clouds, but we can at first distinguish between methods using a 2D information (either by projecting the cloud of an elevation image, or directly using range images) and methods working directly on the 3D information. Also the way the two steps segmentation and classification can combine may differ greatly from one method to another. Indeed, one can start by segmenting objects and classify each object, but one can also classify each point and use this classification to group points into "real" objects.

Elevation images: The use of images reduces the complexity and therefore the computation time, and use proven and robust methods of image processing [START_REF] Hoover | An experimental comparison of range image segmentation algorithms[END_REF]. It can go from the simplest with the research of plans in range images [START_REF] Gorte | Planar feature extraction in terrestrial laser scans using gradient based range image segmentation[END_REF], to semantic segmentation with graphs and CART decision trees on range images [START_REF] Zhu | Segmentation and classification of range image from an intelligent vehicle in urban environment[END_REF], or mathematical morphology for segmentation and SVM for classification [START_REF] Serna | Detection, segmentation and classification of 3d urban objects using mathematical morphology and supervised learning[END_REF]. Elevation images are also used for guiding autonomous vehicles in real-time, indeed they allow for fast registration on pre-processed 2D maps [START_REF] Kammel | Team annieway's autonomous system for the 2007 darpa urban challenge[END_REF][START_REF] Ferguson | Detection, prediction, and avoidance of dynamic obstacles in urban environments[END_REF]. Markov Random Fields can be used for contextual classification [START_REF] Munoz | Onboard contextual classification of 3-d point clouds with learned high-order markov random fields[END_REF], or for learning segmentation [START_REF] Anguelov | Discriminative learning of markov random fields for segmentation of 3d scan data[END_REF].

Direct point classification:

Another approach is to first classify each point by studying its neighbourhood, then group them into relevant objects. This raises the problem of choosing the size of the neighbourhood. This problem is addressed in [START_REF] Demantké | Dimensionality based scale selection in 3d lidar point clouds[END_REF] by choosing the size that minimizes an entropy computed on features extracted from covariance matrix of the neighbourhood called dimensionality features. This method proposes to classify each point in a geometric class: line, surface, volume. This dimensionality attributes are used in several methods [START_REF] Douillard | On the segmentation of 3d lidar point clouds[END_REF]. There are also many local 3D descriptors as VFH estimating normal distributions [START_REF] Rusu | Fast 3d recognition and pose using the viewpoint feature histogram[END_REF] or RSD using the curvature radius (Marton et al., 2010a) that can be used to build global descriptors of objects CVFH [START_REF] Aldoma | Cad-model recognition and 6dof pose estimation using 3d cues[END_REF] and GRSD (Marton et al., 2010b).

Detection, Segmentation, Classification: The pipeline which seems the most successful is the following [START_REF] Golovinskiy | Shapebased recognition of 3d point clouds in urban environments[END_REF]: a) ground extraction, b) object detection, c) object segmentation, d) supervised learning classification. It was improved by [START_REF] Velizhev | Implicit shape models for object detection in 3d point clouds[END_REF] with object centres estimation and Implicit Shape Model for classification instead of supervised learning.

PROPOSED METHODOLOGY

In a framework inspired by [START_REF] Golovinskiy | Shapebased recognition of 3d point clouds in urban environments[END_REF], we propose the following workflow: extract the ground, segment the remaining 3D point cloud in connected components (no detection step, that appears to be unnecessary in three dimensions), compute a feature vector on each segmented object with 3D descriptors, classify each object.

Ground Extraction

After testing several methods including RANSAC and Region-Growing on normal distribution, we chose the following method. We project the point cloud on an horizontal grid discretized with a step δxy, keeping in each pixel P only the minimal applicate value: zmin(P) = min p∈P pz.

First, we find a pixel which has supposedly a lot of his points on the ground. For this purpose, we compute an histogram in z of the whole point cloud and we find the biggest bin, then we find the pixel of the 2D-grid which has the most points in this bin in proportion to all its points.

Then we grow a region R from this seed, adding a neighbour Q of P ∈ R to the region only if |zmin(P) -zmin(Q)| < δz, where δz is a parameter to be chosen big enough to allow a certain slope of the ground, but small enough to avoid taking cars and buildings.

The last step is to filter the points in the region R, indeed, in chosen pixels there might be remaining points not belonging to the ground. That's why we keep only points p ∈ P which verify pz < zmin(P) + ∆ in each pixel. Where ∆ is a threshold which must be bigger than twice the noise of the data around plane.

Object Segmentation

To segment the objects, we extract the connected components of the remaining cloud. As we seek to maintain reasonable computation times, we avoid to achieve a Region Growing directly on the point cloud, what is very time-consuming because of the nearest-neighbour search. Instead, we project the point cloud on a 3D-occupancy-grid or an Octree of resolution δ to be chosen large enough to avoid over-segmentation, and small enough to avoid several objects to be segmented together (for example cars parked too close to each other). Finally we realize a Region-Growing on the occupancy-grid, it is much faster as the neighbourhoods are known in this structure.

In our experiments, it seems that optimal choice of δ is always between 10cm and 15cm.

Object Classification

Features:

For each segmented object we compute a vector of features composed of Geometric features mainly inspired by [START_REF] Serna | Detection, segmentation and classification of 3d urban objects using mathematical morphology and supervised learning[END_REF] and of 3 histogram-based descriptors from the literature, namely CVFH [START_REF] Aldoma | Cad-model recognition and 6dof pose estimation using 3d cues[END_REF], GRSD (Marton et al., 2010b) and ESF [START_REF] Wohlkinger | Ensemble of shape functions for 3d object classification[END_REF]. In summary we obtain a feature vector with 991 variables: 22 for geometric features, 308 for CVFH, 21 for GRSD and 640 for ESF.

Geometric features: This features are mainly inspired by [START_REF] Serna | Detection, segmentation and classification of 3d urban objects using mathematical morphology and supervised learning[END_REF], they give more robustness to histogrambased descriptor which describe only the local geometry of objects.

First of all, we project horizontally the point cloud on its (x, y) variables to compute the convex hull in 2D and covariance matrix of the point cloud in variables (x, y). Then we compute the following geometric features: the number of points, zmax -zmin, σz the standard deviation in z, xmax -xmin, in the PCA base, ymax -ymin, in the PCA base, the smallest eigenvalue λ0 of covariance matrix in (x, y), the biggest eigenvalue λ1 of covariance matrix in (x, y), λ 1 λ 0 , the area of the 2D convex hull in (x, y), the area of the 3D convex hull, the volume of the 3D convex hull, a 10-bins histogram in z.

The 2 following descriptors are histogram-based originally used to recognize objects and their 6DOF-pose of known models, but we use it only for the first task. They both need normal computation, what can be very time-consuming.

CVFH (Clustered Viewpoint Feature Histogram): VFH descriptor [START_REF] Rusu | Fast 3d recognition and pose using the viewpoint feature histogram[END_REF] is a concatenation of 4 histograms representing normal angles distribution on the surface of the object. As VFH is sensitive to noise, CVFH is build by adding a Shape Distribution histogram that can differentiate the clouds that have similar normal distributions, but the points are distributed differently.

GRSD (Global Radius-based Shape Descriptor): RSD (Marton et al., 2010a) descriptor is based on the observation that the radius r of a sphere approximating the surface through two points at distance d can be estimated using the formula

d = √ 2r 1 -cos(α),
where α is the angle between the normals of the points. This feature seems enough discriminative to distinguish plane, sphere, corner, edge and cylinders. But instead of using the radius r, RSD is the histogram in d and α that can be used to classify each point of the object.

To build a feature vector globally on the object, the point cloud is projected on an octree, and each voxel is classified using RSD. GRSD is build as GFPFH [START_REF] Rusu | Detecting and segmenting objects for mobile manipulation[END_REF] by observing relationships between this locally labelled voxels.

ESF (Ensemble of Shape Functions): ESF descriptor is based on the idea that the distribution of distances between pairs of points randomly chosen in the object appears to be relevant to classify an object [START_REF] Osada | Matching 3d models with shape distributions[END_REF]. Other distributions are important as angles, surfaces and volumes. To further improve performance, each pair of points is classified in "in"", "out"" or "mixed"" depending on whether the segment between these points is inside the object, outside or both. A great benefit of this descriptor is that it does not require the computation of normals, and is therefore much faster than the previous two descriptors.

Classifier:

In our work, Random-Forest [START_REF] Breiman | Random forests[END_REF] are chosen because they are one of the most accurate general purpose classifier and have multiple advantages compared to SVM for example, with similar results [START_REF] Mountrakis | Support vector machines in remote sensing: A review[END_REF] or Gaussian Mixture Model [START_REF] Lalonde | Scale selection for classification of point-sampled 3d surfaces[END_REF], Markov Random Fields (Munoz et al., and Adaboost (Lodha et al., 2007).

Random-Forest are part of variance reduction methods by bagging (bootstrap aggregating). The principle is to train independently a big number of decision tree, each one on a random subset of the training set (typically two third), and using each time only a random subset of features. Then, in testing time to obtain a prediction on the forest, simply test on each tree and count the number of votes for classification (or average for regression).

The greatest advantages of Random-Forest are:

they give an estimation of error of generalization (out-ofbag: OOB) after training, as each tree is trained only on two third of the dataset, the model can be tested on the last third, for each feature vector they give the probability to be in each class, they give importance of each feature, measuring the number of times they are used for training, this allows us to achieve feature selection and potentially reduce computation time, they are poorly sensitive to parameter changes, what makes them very easy to tune.

EXPERIMENTS

Implementation

All algorithms are implemented in C++ with an intensive use of PCL [START_REF] Rusu | 3D is here: Point Cloud Library (PCL)[END_REF] to read and write PLY files, to compute normals and to compute descriptors such as CVFH, GRSD and ESF. The framework run on one thread except the computation of normals which is parallelised with OpenMP.

For classification, computations are less intensive we use the python library scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF], which provides all features of Random-Forest as OOB score and features importance.

The experiments are run on a desktop Intel Core i7 4790K with 4 cores clocked at 4GHz.Moreover the computer has 32GB of RAM, what allows us to run our algorithms on massive point clouds of more than 100 million points.

Dataset

All point clouds used for our experiments are acquired with the MLS prototype of the center for robotics of Mines Paritech: L3D2 [START_REF] Goulette | An integrated on-board laser range sensing system for on-the-way city and road modelling[END_REF] (as seen in Figure 1). It is a Citroën Jumper equipped with a GPS (Novatel FlexPak 6), an IMU (Ixsea PHINS in LANDINS mode) and a Velodyne-HDL32 LiDAR mounted in almost horizontal position. 1 https://www.google.fr/maps/dir/48.8512675,2. 3320095/48.8509089,2.3307348/@48.8496176,2.3311634, 466m/data=!3m1!1e3!4m9!4m8!1m5!3m4!1m2!1d2.3313488! 2d48.8483308!3s0x47e671d0662c1f71:0x3468592da4fea104! 1m0!3e0?hl=en 2 https://www.google.fr/maps/dir/50.6797937,3. 1565797/50.6719983,3.1448871/50.6749018,3.1456907/ 50.6719983,3.1448871/@50.6724002,3.1451847,18.75z/ data=!4m2!4m1!3e0 5. RESULTS

Evaluation: Segmentation

Ground Extraction: The ground extraction step works well on all the dataset, in the sense that the road and the sidewalk is completely extracted. But an inherent consequence of our method is that the lowest points of each object are classified as belonging to the ground (as seen in figure 3(d)).

extraction

Object Segmentation: There are a lot of artefacts: small subclouds that doesn't represent objects, for example in tree canopy or behind the buildings (as seen in figure 4). We won't use this artefacts in the Dataset for classification results, but in view of giving a class to each point of the point cloud, we should add a class "artefacts". We segment the whole dataset and obtain 20121 objects, most of them being artefacts. Then we classify by hand a few objects that seem well segmented, to train a first time on classifier which will give us class of other samples when it is confident enough. This allows us to create a dataset quickly. We finally have 3906 samples in 9 classes, but only 7 of them have enough samples to evaluate classification as seen in Table 1.

Class

Evaluation: Classification

In Random-Forest the only parameter that can influence classification is the number of trees. Figure 5 shows that OOB error converges when number of trees increases. The choice of 256 trees in the Random-Forest is made because more trees would increase computation time without real improvement in accuracy, and less trees would decrease accuracy too much. (1)

F 1 = 2T P 2T P + F P + F N M CC = T P • T N -F P • F N (T P + F P )(T P + F N )(T N + F P )(T N + F N )
where T P , T N , F P and F N are respectively the number of true-positives, true-negatives, false positives and false negatives.

We train the Random Forest Model with 256 trees on the well segmented object in 7 classes that have a sufficient number of samples: trees, cycles, buildings, lampposts, poles, road signs and cars. For training we use 90% of the dataset in each class, then we compute precision, recall, F1 and MCC on the remaining 10%, results are shown in table 2. To further investigate the importance of each descriptor we test every possible combination, and draw performance of classification for class "car" in table 4.

Class

We can conclude that if we want to keep only descriptor which don't require normal computation: Geometric Features and ESF, we loose only 0.21% of OOB score. This is a compromise to be done as the normals are the most time consuming part of the computation of descriptors (as seen in 5.4).

Computation Time

5.4.1 Segmentation: This corresponds to the time of projection of the point cloud on a 2D-grid and a region growing on this grid for Ground Extraction, then the same thing on a 3D-grid for Object Segmentation. On our dataset, we measure similar times for Ground Extraction and Object Segmentation around 25s for sections of 10 million points. However, the 3D-grid structure has not it been optimized (e.g. using a Octree), we can think that the results could be better.

Descriptors:

The time to compute a feature vector highly depends on the number of points of the object, that's why we give the mean computational time for each descriptor on the 20121 objects segmented in Paris and Lille Dataset.

Two descriptors require the computation of normals on the object, and the operation can be very-time consuming (as shown in table 5) especially for large clouds.

Classification:

It seems that the time to predict the class of a feature vector is weakly dependent on the number of variables. Once the Random Forest is trained with 256 trees, prediction time per sample is about 1.2ms. Thus assuming that feature vectors are computed fast enough, we could predict the class of 833 objects each second. Hence the classification is clearly not the bottleneck in our algorithm.

Comparison with state-of-the-art

For segmentation, keeping the 3D structure of the point clouds allows to segment vehicles under trees as shown in Figure 7. What was not possible with elevation images.

Purely on the classification of cars, we compared with [START_REF] Serna | Detection, segmentation and classification of 3d urban objects using mathematical morphology and supervised learning[END_REF]. We obtain a better Recall, but Precision slightly below as seen in Table 6.

CONCLUSION

In this work, we proposed an automatic and robust approach to segment and classify massive urban point clouds in reasonable time without using elevation images.

First, the ground is extracted using a Region Growing on zmin kept in an horizontal 2D-grid. Next, the remaining point cloud is segmented in connected components of a 3D-occupancy-grid. Finally, each object is classified using Random-Forest and a feature vector composed of geometric features and histogram-based features of the literature. With such classification results, it is possible to achieve change detection on particular classes such as cars. Then between two passages in the same street, we can detect cars that have changed by comparing the corresponding sub-clouds and achieve parking survey. On an other scale of time between acquisitions we can automatically detect the bent poles or road signs.

In our future works, we believe we can improve the accuracy by adding contextual descriptors (such as the elevation of objects above the ground or the number of neighbouring objects) that would avoid classifying as car objects that are in height and remove segmentation artefacts behind the buildings facades.

Figure 1 :

 1 Figure 1: MLS prototype: L3D2 The Dataset is composed of seven pass of 650m in Paris 1 (rue Madame and rue Cassette, 75006 Paris) and seven pass of 1.6km in Lille 2 (rue du Professeur Perrin and rue Jean Jaurès, 59170 Croix) at about two hours apart. The clouds have high density with between 1000 and 2000 points per square meters on the ground, but there are some anisotropic patterns due to the multibeam LiDAR sensor as seen in Figure 2.

Figure 2 :

 2 Figure 2: Anisotropic pattern on the ground (color of points is the reflectance)

Figure 3 :

 3 Figure 3: Exemple of sub-clouds well segmented after ground extraction

Figure 4 :

 4 Figure 4: Exemple of ground extraction and object segmentation on a truncated point cloud of Lille (ground in red, and every other object has a different color)

Figure 5 :

 5 Figure 5: Importance of number of trees in the forest To evaluate our choices in term of classification we compute 4 indicators that are the precision P , the recall R, the F1 score and the Matthews Correlation Coefficient M CC as computed in equations 1. P = T P T P + F P R = T P T P + F N (1)

Table 1 :

 1 Number of samples for each class

			Number of samples
		Paris	Lille	Total
	trees	64	373	437
	cycles	142	1	143
	buildings	111	404	515
	lampposts	16	357	373
	pedestrians	10	1	11
	poles	508	65	573
	trash cans	8	1	9
	road signs	114	456	570
	cars	719	556	1275
	Total	1692	2214	3906

Table 2 :

 2 Mean Precision, Recall, F1 and MCC scores for each class

		Precision	Recall	F1	MCC
	trees	93.90%	95.84% 94.83% 94.19%
	cycles	79.10%	96.00% 86.45% 86.44%
	buildings	93.00%	98.69% 95.73% 95.13%
	lampposts	90.09%	99.00% 94.28% 93.79%
	poles	92.98%	99.69% 96.19% 95.60%
	road signs	93.09%	99.40% 96.12% 95.52%
	cars	96.97%	99.53% 98.23% 97.37%

5.3 Feature importances

Random-Forest provide an importance for each that represent how much it is used to build the model. The importance is shown in figure

6

and table 3 for each descriptor. First of all, it seems that CVFH is almost useless both in cumulative and proportionally to number of variables. Although Geometric Features and GRSD have less variables than other descriptors they seem very important. Moreover the descriptor which has the most importance cumulatively is ESF, but importance is spread over all its 640 variables.

Table 3 :

 3 Cumulated importance of each descriptor and Mean importance per variable (given by Randon-Forest).

Table 4 :

 4 Performances for each combination of descriptor possible (Geom is for Geometric features, for each column the best result is bold) Descriptors Computation Time (s) Proportion Mean Time per object (ms)

	Descriptors	Number	Training	OOB	Performances for class "cars"
		of variables	time (s)		Precision	Recall	F1	MCC
	Geom	22	2.03	98.30%	96.19%	99.02%	97.58%	96.40%
	CVFH	308	6.98	93.71%	86.06%	97.54%	91.42%	87.28%
	GRSD	21	1.74	94.38%	86.59%	97.83%	91.84%	87.91%
	ESF	640	13.13	94.29%	87.90%	96.02%	91.76%	87.71%
	Geom+CVFH	330	6.34	97.81%	94.32%	99.03%	96.60%	94.97%
	Geom+GRSD	43	2.58	98.39%	96.15%	99.44%	97.76%	96.68%
	Geom+ESF	662	11.60	98.59%	96.33%	99.38%	97.82%	96.77%
	CVFH+GRSD	329	6.63	97.58%	93.38%	99.40%	96.28%	94.51%
	CVFH+ESF	948	15.16	96.04%	91.91%	97.57%	94.64%	92.03%
	GRSD+ESF	661	11.83	98.49%	96.17%	99.60%	97.85%	96.82%
	CVFH+GRSD+ESF	969	14.18	98.60%	96.28%	99.66% 97.93%	96.94%
	Geom+GRSD+ESF	683	11.74	98.73%	96.98%	99.41%	98.18%	97.30%
	Geom+CVFH+ESF	970	13.89	98.67%	96.57%	99.48%	98.00%	97.03%
	Geom+CVFH+GRSD	351	6.32	98.18%	95.59%	99.23%	97.36%	96.09%
	Geom+CVFH+GRSD+ESF	991	13.61	98.80%	96.94%	99.55% 98.23% 97.37%
	Geom	17.2		3.22%		0.9
	CVFH	240.3	44.92%		11.9
	GRSD	64.4		12.04%		3.2
	ESF	213.0	39.82%		10.6
	Total	534.9	100%		26.6
	Normales	964.7			47.9

The method is tested on a Dataset acquired by a MLS prototype in Lille and Paris. Ground extraction and object segmentation is evaluated qualitatively and performs well. The classification is tested only on well-segmented objects and performs as well as the

Table 5 :

 5 Mean Computational Time of descriptors on 20121 segmented objects of 7 passes in Lille and Paris

	Method	Precision	Recall	F1
	(Serna and
	Marcotegui, 2014)	100.0%	94.6%	97.2%
	ours	96.97%	99.53% 98.23%

Table 6 :

 6 Classification results for class "car" (in bold the best results) state of the art. Moreover, we conduct a study of the importance of each descriptor, in order to reduce computation time.