Ridene François Taha
email: taha.ridene@mines-paristech.fr

Goulette

Francois Goulette

COREGISTRATION OF DSM AND 3D POINT CLOUDS ACQUIRED BY A MOBILE MAPPING SYSTEM Corregistro do DSM e

Keywords: 3D Registration, ICP, Mobile Mapping System, Point Clouds, DSM

The development of 3D mapping databases is a matter of increasing interest. Databases have recently been developed at different scales (national, European, international) and to meet different needs. Such development has been made possible by the implementation of efficient 3D mapping technologies. 3D mapping strategies are based on multi-sensor data fusion usually performed after a preprocessing step that includes registration and filtering. In this paper, we present our work on registration methods applied to solve problems in 3D urban environment representations issued from a Mobile Mapping System. We improve the stability of convergence, the computation time and handle heterogeneous data sets in various scenarios.

INTRODUCTION

The production of realistic 3D map databases is a matter of increasing interest. Databases have recently been produced on different levels (national, European, international) for different applications. Different methods have been used to develop such Databases. The expansion of this development has been made possible by the implementation of efficient 3D mapping technologies and rapid progress in various fields such as remote sensing, image processing and sensor technologies (camera, laser, GPS, INS, etc.). A variety of efficient Mobile Mapping Systems Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p. 824-838, 2009. (MMS) has been produced to create 3D models of cities. MMS are special vehicles which integrate two kinds of sensors: "positioning sensors" (GPS, INS, Compass, etc.) and "imaging sensors" (camera, laser, radar, etc.). Acquisition with MMS can be carried out using two methods: "driving" and "stop and go." In our approach, after the data acquisition step we processe the resulting datasets using algorithms of multi-sensor data fusion to obtain 3D representations. These phases of the work (acquisition, processing) require the use of specific software such as RT-Maps [START_REF] Nashashibi | RTMAPS a framework for prototyping automotive multi-sensor applications[END_REF] which generates timestamped data bases.

Most land MMS use "direct geo-referencing," a category which can be divided into two sub classes: (1) laser-based (Goulette et al., 2006, Zhao and[START_REF] Zhao | Reconstructing a textured CAD model of an urban environment using vehicle-borne laser range scanners and line cameras[END_REF]; (2) photogrammetry-based (Bentrah et al., 2004[START_REF] Pollefeys | Detailed real-time urban 3d reconstruction from video[END_REF].There are, however, also MMS using "indirect geo-referencing" [START_REF] Früh | An Automated Method for Large-Scale, Ground-Based City Model Acquisition[END_REF]. The results produced by MMS depend on the sensors used. A comparative study between MMS can be found in [START_REF] Ellum | Land-based mobile mapping systems[END_REF]El-Sheimy, 2002, Schwarz and[START_REF] Schwarz | Mobile mapping systems state of the art and future trends[END_REF].

Context

The overall project goal is to generate realistic and geo-referenced 3D maps of urban areas around Paris. We use mainly our Mobile Mapping System (MMS) Lara3D [START_REF] Goulette | An Integrated On-Board Laser Range Sensing System for On-the-Way City and Road Modeling[END_REF] presented in Figure 1. In the present work we made acquisitions using Lara3D in the 5th district of Paris. These acquisitions were made in "driving mode" and planned by road sections. In fact, in a dynamic urban environment with obstacles (cars, streetlights, etc.), it is impossible to treat all sections of the area at once. A series of acquisitions must thus be made. The resulting set of separate acquisitions generates incoherence in the data produced (i.e Figure 2) due to problems that can affect sensors (GPS multi path error, GPS masking, INS drift, etc.). Despite geo-referencing, we observe offsets and deformations between datasets. To obtain a correct model at the end of processing, we have to apply registration of the datasets before carrying out the fusion step. Making a correct registration requires 3D reference data. We have two possibilities: (1) register overlapped road sections in pairs; (2) carry out registration by using external 3D representations as references. In our case we used a Digital Surface Model (DSM) (i.e Figure 1). In fact, DSM is the most extensive for this area and provide the best geo-referencing in absolute terms: resolution (20x20x50 cm) in (X,Y,Z). This combination between DSM and MMS point clouds is useful for the final model. The main contribution of the fusion between these two 3D representations lies in the fact that they complement each other. For example, roof information that not accessible by MMS acquisitions can be recovered from aerial data (DSM) just as the ground track of buildings hidden by edges of roofs in a DSM will be accessible by the MMS data set.

Figure 2 -Overlapping of all road sections produced by Lara3D around the Pantheon monument (each road section with a specific color). Three different viewing angles are presented. We observe problems of coherence between road sections due to the localization problem of MMS in the urban environment: GPS multi path error, GPS masking, INS drift.

Contributions

In order to realize registration, several 3D registration methods have been proposed in the state of the art, however, the motivation of our work is to propose automatic 3D registration method for processing of heteregeneous datasets and to Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p. 824-838, 2009. resolve instability problems that can influence registration processing. The large amount of data processed need a huge computation time, which can represent a limitation in practical cases. Our implementation has to be fast.

The main contributions of this paper can be stated as follows. First, we present a variant of rigid registration based on ICP with preprocessing and dynamic threshold updating. This variant is adapted to our heterogeneous datasets that have different amounts of geometric features along with different resolutions and levels of precision captured using two different techniques (Mobile laser scanner and DSM). Our method uses two different adjustment techniques appropriate to the cases studied. Second, a classification of cases of registration related to the kind of overlap which makes it possible to improve the performance of the algorithm and to set the input variables. Third, we show how the registration with an external 3D representation such as DSM can correct the incoherence for 3D models produced by a Mobile Mapping System.

This paper is organized as follows. In section 2 we present a state of the art of rigid registration and our implementation is described. In section 3 the experimentation relating to identified scenarios and results are shown. We then present our conclusions and perspectives for future works.

REGISTRATION

State of the Art

Rigid registration consists in estimating a rigid transformation between two datasets which provide a representation in the same referential. To register threedimensional representations, the most widely-used approach is the Iterative Closest Point (ICP) introduced by [START_REF] Besl | A method for registration of 3-D shapes, Pattern Analysis and Machine Intelligence[END_REF][START_REF] Chen | Object modelling by registration of multiple range images[END_REF][START_REF] Zhang | Iterative point matching for registration of free form curves and surfaces[END_REF]. In the ICP algorithm described in [START_REF] Besl | A method for registration of 3-D shapes, Pattern Analysis and Machine Intelligence[END_REF], two main steps are provided: generation of a set of matching pairs and estimation of rigid transformation. In the former each point in one point cloud is matched with the closest point in the other point cloud to form correspondence pairs. In the latter a point-to-point (P-to-P) error metric is used, in which the sum of the squared distances between points in each correspondence pair is minimized by rigidly moving one of the point clouds. These two steps are iterated until stabilization (the error becomes smaller than a threshold level or it stops changing). It has been demonstrated that ICP converges to a local minimum, but this convergence is determined by the initialization at the beginning of processing. In the case of urban 3D representations, if all processed datasets are geo-referenced in the same referential, this referencing will be considered as initialization of the ICP.

Different variants of ICP were proposed in previous works related to rigid registration used in different fields of application (computer vision, photogrammetry, artificial intelligence, etc.). Comparative studies of ICP variants were provided in [START_REF] Rusinkiewicz | Efficient variants of the ICP algorithm[END_REF]Levoy, 2001, Gruen and[START_REF] Gruen | Least squares 3D surface and curve matching[END_REF] Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p. 824-838, 2009.

2007). However, there is no guarantee that the registration of two 3D point clouds using the ICP will be successful. Registration can fail due to several causes: if the overlap between the two 3D point clouds is small and not determinist, if data input measurement errors are too big or when there is insufficient geometric constraint on the 3D transformation between the two 3D point clouds (for example, when a plane is being registered to a second plane).

Proposed Registration Method

Preprocessing operators were applied to input datasets: • 2D Morphological filtering was performed on the DSM to reduce noise, an Alternate Sequential Leveling (Soille, 2003).

•

Sub-sampling was performed on MMS point clouds to reduce search space and to focus the registration on the area of interest.

To determinate points of interest we use all points resulting from a preprocessing step as in [START_REF] Besl | A method for registration of 3-D shapes, Pattern Analysis and Machine Intelligence[END_REF].

We find the homogeneous coordinate transformation matrix T = [R|t] which has six free motion parameters (3 angles and 3 translation components) that minimizes a registration error between two point clouds using linear equation 2 based on: Euclidian distance and determination of the nearest neighbour according equation 1. The [START_REF] Horn | Closed-form solution of absolute orientation using orthonormal matrices[END_REF] method is used to minimize and to determine T.

= + - = 1 2 ( 1 1 i n i i RP p N ε t (2)
We have established an approach of rigid registration ICP using a dynamic threshold as in [START_REF] Masuda | A robust method for registration and segmentation of multiple range images[END_REF]Yokoya, 1994, Fitzgibbon, 2003) with duplicate pairs of correspondence removed as in (Almhdie et al., 2007).

Initialization was provided on the dynamic threshold according to equation 3 in which "Res" means the resolution of input data and " " is a constant.

)) 2 ( Re ); 1 ( max(Re . P s P s

Thr Dy κ = (3)
The large amount of data processed (6 million points in our case) results in huge computation time which can represent a limitation in practical cases. To accelerate our implantation we optimized the search process of nearest neighbors by using a K-D Tree according to [START_REF] Mount | A library for approximate nearest neighbor searching[END_REF]. The computational complexity has thus been reduced from with ( and ) representing the number of points in input point clouds.

)

) ( . . ( ) . ( 2 2 1 2 2 1 nb Log nb nb toO nb nb O 1 nb 2 nb 2.

Scenarios of Registration

Our aim was to register MMS point clouds which display problems of coherence. We performed the registration in two steps. Let us denote T1 and T2 two 3D transformation matrices. Firstly, we did a rigid registration between 3D point clouds issued from MMS using the T1 provided by two sections each time. We then did the registration for the final result with DSM using the T2. Equation 4 shows the steps of registration in terms of the transformations used with esult Pr and referring respectively to the result point cloud after registration and the initial point cloud before registration.

Pinit

i i i i Pinit T T esult ) 2 1 ( Pr °= (4)
We planned two scenarios of registration: • Registration between MMS datasets: we classified that on three groups according to the kind of overlap (extremity, intersection and partial part).

Figure 5 shows all cases of the registration in this scenario.

•

Registration of the MMS datasets on DSM: for each registered case of the previous scenario, a reference road section was selected and we performed Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p. 824-838, 2009. registration on the corresponding area on the DSM. The T2 transformation result was then applied for the second road section for each case.

RESULTS AND DISCUSSION

We apply registration with a dynamic threshold on 3D datasets of outdoor urban representation. In our processing we distinguish two steps (i.e Figure 4): registration by pairs between MMS point clouds and registration for the reference road section of each registered pair in the previous step with the corresponding area on the DSM. For registration by pairs, the set of registration includes four cases corresponding to different kinds of overlap. The case of P5-P2 with the intersection was not processed due to problems in P5 point cloud quality. In registration for the reference road section the set of registration includes 2 cases. An initial transformation is needed when the input data are too far than each other. We evaluated our results in a comparative study in terms of convergence speed, complexity and average registration error. Initial values for variables required for the processing are presented in Table 1. Table 2 shows the computing time for each case of registration processed. Testing of the algorithm was performed on a PC Intel(R) Xeon (R) CPU 5130 at 2.00 GHZ with 2 Go of RAM.

Registration Between MMS Point Clouds

For each road section produced by Lara3D it was necessary to carry out registration to correct the geo-referencing. Five cases of registration were processed according to the kind of overlap (i.e Figure 4). Figure 5 shows an example of registration when we have an overlap on the extremity: the case of Soufflot Street between P1 and P2. The geo-referencing problem is visible and the road sections are not consistent. After registration we obtained coherence between P1 and P2.

Figure 6 displays the algorithm behavior with P-to-P adjustment and P-to-S adjustment. P-to-S adjustment produces a little better result than P-to-P in terms of convergence. In fact in P-to-S the result was established on average error 0.13 m after 25 iterations compared to 0.15 m for P-to-P. Figure 7 gives an example of registration when we have partial overlap: the case of Soufflot Street between P3 and P4. The georeferencing problems can be observed and the road sections show some incoherence. The result after registration is coherente and we obtain a consistence between P3 and P4. Figure 8 displays the algorithm behavior with P-to-P adjustment and P-to-S adjustment. P-to-S adjustment produces better and more accurate results than P-to-P in terms of convergence. In fact, in P-to-S the convergence was obtained on average error 0.14 m after 37 iterations compared to 0.32 m after 35 iterations in P-to-P where convergence was not obtained.

We note that the adjustment methods do not influence the results of registration in the case of overlap on the extremity, unlike in the case of partial recovery in which the P-to-S method produces a better and more accurate result than the P-to-P method.

Registration Between MMS Point Clouds and DSM

For each registered pair in the previous step we chose a reference road section and then registered it with the corresponding area in the DSM. Two cases of registration were handled: P2-DSM and P6-DSM. Figure 9 shows an example of registration on Soufflot Street P2. We did a filtering on the DSM to reduce noise. We used an initial Tinit transformation to help the algorithm to converge. The result was correct, and thanks to the initialization made according to the method described in (Ridene and Goulette, 09) the result was established on average error 0.32 m after 31 iterations.

CONCLUSIONS AND FUTURE WORK

In this paper, we have proposed an alternative solution for MMS problems when direct geo-referencing fails. It is based on rigid registration applied between only two point clouds at the same time. The registration is decisive in solving problems which appear when we perform MMS acquisitions in an urban environment. We performed the registration in two steps for 2 scenarios. Firstly, we did a registration between pairs of MMS road sections. Secondly, we performed a registration for reference road sections of each pair registered in the previous step, Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p. 824-838, 2009. with external DSM (3D reference representation). The global result is shown in Figure 11. In our application we processed very large datasets of points (more than 6 million points). To improve the processing time of our implementation we used a K-D Tree. By doing so we obtained acceleration by a factor of 32. A quantitative study based on evaluation of convergence was run to improve the quality of results.

Qualitative registration evaluation is useful as it facilitates comparison between registered trajectories and reference PPK-GPS paths. In the case of accumulation of errors in data issued from positioning sensors (GPS, INS), 3D point clouds resulting from MMS acquisition are affected by local geometric deformations. In such cases, rigid registration fails and cannot give a good result. In such situations, a non rigid registration method must be used to correct geometry of input datasets during the registration process. Figure 12 shows a registration case requiring non rigid registration.

Figure 1 -

 1 Figure 1 -(Left) Digital Surface Model (DSM) obtained by correlation between aerial images with 20x20 cm horizontal resolution. (Right) Lara3D, a Mobile Mapping System using a coupled laser scanner/fish eye camera vision system. The resolution of 3D point clouds obtained is 20 cm between profiles and 10 cm between points in the same profile.

  -to-surface (P-to-S) distance[START_REF] Chen | Object modelling by registration of multiple range images[END_REF] (i.e Figure3.b) for registration between MMS point clouds. In fact, the quality of data shows a regular density in 3D and this kind of adjustment can be used. Still, for MMS/DSM registration we use P-to-P distance (i.e Figure3.a). In fact, the DSM geometry is 2.5D and we have irregularity in the Z axis on the 3D representation. It is thus not possible to use the previous adjustment technique.

Figure 3 -

 3 Figure 3 -Common adjustment techniques: (a) point-to-point, (b) point-to-surface.

∑

Figure 4 -

 4 Figure 4 -5th district of Paris, DSM with overlapping of different road sections acquired by Lara3D. Three overlap cases are identified: (a) extremity (1-2; 6-7); (b) intersection (5-2); (c) partial part (2-3; 3-4).

Figure 5 -

 5 Figure 5 -Soufflot Street registration between P1 (green) and P2 (black). (a) Overlapping of P1 and P2 before registration with extremity overlap. A shift can be seen (arrows on selected zone). (b) Result of registration: correspondence between P1 and P2.

Figure 6 -

 6 Figure 6 -Soufflot Street registration between P1 and P2. Progression of the RMS relative to iterations with P-to-P adjustment and P-to-S adjustment.

Figure 7 -

 7 Figure 7-Pantheon registration between P3 (black) and P4 (green). (a) Overlapping of P3 and P4 before registration with partial overlap. A shift can be seen (arrows on selected zone). (b) Result of registration: consistence between P3 and P4.

Figure 8 -

 8 Figure 8 -Pantheon registration between P3 and P4. Progression of the RMS relative to iterations with P-to-P adjustment and P-to-S adjustment.

Figure 9 -

 9 Figure 9 -Soufflot Street P2 in the 5th district of Paris. Result of registration of MMS point clouds on the corresponding DSM area. (Gray) DSM. (Red) MMS Point clouds before registration. (Green) MMS Point clouds after registration.

  Figure 10 displays the algorithm behavior with and without initialization. Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p. 824-838, 2009.

Figure 10 -

 10 Figure 10 -Registration between MMS point clouds and DSM on the Soufflot Street P2 area. Progression of the RMS relative to iterations. We use an initial transformation to help the algorithm to converge.

Figure 11 -

 11 Figure 11 -The area around the Pantheon in the 5th district of Paris. (a) All georeferenced datasets; we see different offsets between heterogeneous representations. (b) Final result of coregistration between DSM and 3D point clouds issued from MMS.

Figure 12 -

 12 Figure 12 -Rigid registration between a point cloud and an aerial photo on Gay Lussac Street in the 5th district of Paris. At the end of the section (part encircled) the result is incoherent and the deformation of the 3D model is clear. One solution is the correction of the 3D model based on techniques of non-rigid registration.

Table 1 -

 1 Initialization of values for different variables of ICP. Three different initializations were performed according to the use of the case treated.

	Variable	Error min	κ	Kmax
	Lara3D/DSM	30 cm	50	100
	Overlap on extremity	15 cm	30	100
	Partial overlap	15 m	20	100

Table 2 -

 2

		Number control points	Number iterations	CPU time (s)
	P1/P2	18 709	24	34.8
	P6/P7	156 690	22	31.4
	P2/P3	292 339	35	52.21
	P3/P4	179 018	37	48.1
	P2/DSM	69 300	33	18.08
	P6/DSM	24 245	35	12.65
		Total CPU time (iterative steps)	197.24

CPU time for optimized implementation of ICP using a K-D Tree. We obtained improvement factor in CPU time of 32 times.

Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p. 824-838, 2009.

ACKNOWLEDGEMENTS

The work reported in this paper was partially performed and sponsored as part of the Cap Digital Business Cluster Terra Numerica project.


Hyun-Jae Yoo
email: hyun-jae.yoo@mines-paristech.fr

François Goulette
email: francois.goulette@mines-paristech.fr

Joel Senpauroca
email: joel.senpauroca@mines-paristech.fr

Gregory Lepère
email: gregory_lepere@trimble.com

SIMULATION BASED COMPARATIVE ANALYSIS FOR THE DESIGN OF LASER TERRESTRIAL MOBILE MAPPING SYSTEMS Simulação baseada numa análise comparativa para o projeto de um sistema movel de mapeamento terrestre a laser

Keywords: Analysis, Comparison, Simulation, Mobile Mapping System, Laser scanning

Over the past decade, laser terrestrial Mobile Mapping Systems (MMS) have been developed for the digital mapping of outdoor environments. While the applications of MMS are various (urban security, road control, virtual world, entertainment, etc.), one may imagine that for each application the system designs could be different. Hence, a comparative analysis of different designs may be useful to find the best solution adapted to each application. The objective of this paper is to propose a methodology to compare point-cloud data quality from different MMS designs by modifying spatial configuration of laser imaging system. For this methodology, we define several quality criteria such as precision, resolution, completeness. We illustrate this in the case of urban architecture digital mapping based on the use of a simulator.

INTRODUCTION

Laser mapping systems have been developed for the digital mapping of outdoor environments. For 3D Geographic Information Systems (3D GIS), point cloud data from laser systems are very useful because they provide directly 3D coordinate data; so this is more efficient compared to other systems. There are two types of laser systems depending on the platform dynamics: static mapping systems and mobile mapping systems (MMS).

We can compare static and mobile mapping systems in terms of time. We compared with real systems, the Trimble VX total station (http://www.trimble.com/) as a static mapping system and the LARA-3D (MINES ParisTech prototype vehicle) as a mobile mapping system on the streets of Paris (Yoo et al., 2009). As a result of this trial, we confirm that the mobile mapping system can save a significant amount of time compared to static mapping systems (total acquisition time is about 6 hours with the static system and about 40 minutes with the mobile system for the test zone of 140m x 30m). This is one of the main reasons to develop such dynamic systems.

However, even if acquisition time can be saved, if the quality of the data is low, then we can not consider MMS as a useful mapping system. Hence, research in the MMS design is necessary to improve the quality of the data. The notion of design involves characteristics, number and spatial configurations (position and orientation) of sensors on the mobile platform. Though MMS designs may differ, the applications are various (urban security, road survey, virtual world, entertainment, etc.). For example, VLMS from Tokyo University embeds 3 laser scanners on the back of a vehicle (Manandhar et al., 2000), DAVIDE from GIOVE uses two different types of laser scanners [START_REF] Amoureus | Integration of LiDAR and Terrestrial Mobile Mapping Technology for the Creation of a Comprehensive Road Cadastre[END_REF]) and StreetMapper from 3D Laser System has several designs varying the number of scanners (Hunter et al.,06;http://www.3dlasermapping.com/). All these MMS systems have different spatial configurations and different types of laser scanner according to the application.

We present in this paper a methodology based on the use of a simulator, to compare several MMS designs to improve the design, and illustrate it in the case of urban architecture digital mapping.

The use of a simulator to evaluate the different designs is motivated by several reasons. First, we can gain time to test the different designs in simulation, in comparison to tests in the real environment. Secondly, we can optimize the final design before a real test. And also, we can separate the issues related to imaging systems from those of the navigation system.

METHODOLOGY OF COMPARATIVE ANALYSIS

For the comparative analysis, we need several criteria and the score of each design candidate for each criterion. As each application has a different level of importance on criteria, we need also to define the coefficient of each criterion for each application.

In this section, we define several criteria for the quality of point cloud data and the method to give a score. We show an example of coefficients for each criterion for combinations of given applications.

Quality Criteria of Laser Mappings

To compare data quality, we need several criteria such as precision, resolution, completeness, etc. These criteria are available for both static and mobile mapping systems.

Accuracy and precision

All the point cloud data need high levels of accuracy and precision. The accuracy is the difference between the real distance to object (reference value) and the mean of calculated distances. The precision is the standard deviation (Figure 1). For MMS, accuracy and precision are directly linked to the navigation system (especially accuracy). If we do not know exactly where we are (i.e. the information from the navigation system is not accurate), the accuracy and the precision cannot be guaranteed.

We propose to give a score with the equation (1) which allows classification of precision at several levels like class 0: around 1 m, class 1: around 1 dm, class 2: around 1 cm, class 3: around 1 mm, etc. abs = difference between reference value and mean of real values (m) r e l = standard deviation (m)

Resolution

Resolution is determined by the requirements of users or application domains. For example, the requirement can be ≤ 1 dm for all objects. This criterion depends on the vehicle state (speed, orientation) and also the characteristics of the laser scanner used (pulse repetition rate, scanning rate).

Density:

We can explain resolution by the notion of density. In this domain, we define density as the number of neighbor points whose distance is ≤ 1 m from each reference point. This definition deduces the density unit as "point/m 3 " but we permit "points/m²" by assuming that all the neighbor points are projected to the surface circle as Figure 2.

In the case of Figure 2, there are 8 points (points within the distance r = 1 m and including the reference point) in the surface of π m², hence, the density of the reference point is 8/π = 2.55 points/m².

Variation of homogeneity:

The quality of the data could also be changed according to the homogeneity. We assume the data is homogeneous if the point densities of all the data are the same (i.e., if the standard deviation is 0). But as the distance between system and object is often variable, the density can not be constant (over-density if distance is short, under-density if distance is long). Also, for mobile systems, if the vehicle turns left, the left side of the platform could have an over-density while the right side could have an under-density. Under-density results in lack of information on the scene and over-density may induce a problem of data storage. For the static mapping system, there is a technology which attenuates this problem (Surescan technology in the Trimble GX Advanced scanner) [START_REF] Hook | Trimble surescan technology white paper[END_REF].

We propose to give a score of homogeneity with the variation of density (Figure 3).

Figure 3 -Variation of density.

The vertical axis represents the density distribution rate and the horizontal axis represents the point density (number of points/m²). In this article, we assume the value of homogeneity is the value from equation ( 4). If the standard deviation tends to 0, the value of homogeneity tends to 1. This means the data is homogenous.

Completeness

The objective of completeness criterion is to minimize occluded zones in the scene. Occluded zones mean the zones which are necessary to be scanned but are not scanned during the acquisition. We propose to give a score for this criterion like percentage, from '0' to '100'. '0' means there is nothing scanned, '100' means the scene is completely scanned (there are no occluded zones). In this article, we estimate the score for each type of object such as building, bridge, road, etc. (the calculation of score needs to be developed further).

For mobile mapping systems, we can define two types of occluded zones according to the cause of occlusion: non visible zone and shadow zone. These zones are created from the direction of vehicle.

Non visible zone:

This zone refers to a zone which is not scanned by MMS even if there is no obstacle. As we can see in Figure 4 with the red circle, LARA-3D can not scan the facade whose normal is parallel to the direction of vehicle. This non visible zone could be a critical problem for certain applications such as 3D building modeling where complete façade information is required.

The non visible zone can be modified if we modify the spatial configuration of the scanner. Or if we use several scanners in different spatial configurations, the non visible zone with a scanner can be covered by another scanner.

Shadow zone:

This zone refers to a zone which is occluded by objects. For example, if we scan the urban environment, there may be parked cars, pedestrians, trees, benches, etc. in front of buildings that cause shadow zones on the building facades. As we can see in Figure 4 with the blue circle, the parked car has created a shadow zone on the building facade. This shadow zone could cause a critical problem for certain applications. This zone will not disappear if we use only one scanner but could be removed with some modification of the spatial configuration of the scanner. We need to use several scanners with different spatial configurations to cover the shadow zones which are created by one scanner with other scanners.

Constraints

There are also several constraints to compare laser mapping systems such as cost, complexity, size, etc. In this article, we do not consider these constraints but focus on spatial geometric configuration of imaging sensors.

Normalization of score

After giving the score for each criterion, we need to normalize it because each criterion has a different interval score. For example, the score of precision is maximum 4 but the score of completeness is 100. We give a new score which is variable between 0 and 10, by the equation ( 5).

Coefficient for Applications

According to the application domain, some criteria become more important than others. Hence it is necessary to determine the coefficient for each criterion for a given application domain. The coefficients are applied to calculate the total score of each candidate for a given application. Table 1 is an example of coefficients for the domain of "Architecture for 3D tourism". We give the coefficient for each sub criterion. Noting designs for each of these criteria and using coefficients, we end up with a global score for each system design. The total score is calculated by multiplying the normalized score with a coefficient.

ILLUSTRATION OF COMPARATIVE ANALYSIS BASED ON SIMULATION

We illustrate our methodology on various designs derived from the existing LARA-3D platform, by changing the number of laser scanners and their spatial configurations (positions and orientations (pitch and yaw)) on the platform. LARA-3D is the prototype which has been designed and developed by our laboratory. It is composed of two sub-systems: the navigation system (GPS, INS, etc.) and the imaging system (laser scanners, cameras, etc.) [START_REF] Goulette | An Integrated On-Board Laser Range Sensing System for On-the-Way City and Road Modelling[END_REF]. LARA-3D allows us to do prospective studies and to help us in the development of novel designs relative to mobile mapping technologies. This system has been used as a test bed to compare several possible options, using our methodology.

Simulator

For the implementation, we have used two software, one dedicated to simulation: SiVIC (Simulator of vehicle, infrastructure and sensors) developed by LIVIC (INRETS / LCPC), adapted to our needs (Yoo et al., 2009), and RTMaps (Real Time, Multi-sensor, Advanced and Prototyping Software) developed by Intempora (http://www.intempora.com). As we are studying the comparison of different MMS designs (configuration of laser scanners on the platform), we assume that the navigation system offers perfect data during the whole time (using perfect IMU in simulation) and that there is no calibration error between navigation and imaging systems so that all designs have the same level of accuracy and precision.

Application Domain

For this illustration, we choose as application domain "Architecture for 3D tourism". For this application, we have the coefficient for each criterion as mentioned in section 0.

Designs

As mentioned, we can imagine several design propositions by changing the sensors configuration for the simulation by changing the number of laser scanners, their position and orientation on the platform, the type of sensor, etc. In this article, we compare three different designs using the same laser scanner. Table 2 shows the laser scanner characteristics in simulation. Design #1: For this design, we put the scanner on the top of the vehicle at a height of 2.5 m without inclination, like the current LARA-3D. Table 3 shows the spatial configuration of design #1. The values are local values on the vehicle (position (0, 0, 0) is the center of the rear axle). The position is composed by (direction of the vehicle, lateral direction, height). The orientation is composed by (angle of raw, pitch and yaw).

Table 3 -Configuration for design #1

Position

-1, 0, 2.5 (m) Orientation 0, 0, 0 (°)

Design #2: For this design, we put the scanner at the same position as design #1 but with an inclination of 20 ° of pitch (Table 4).

Table 4 -Configuration for design #2

Position

-1, 0, 2.5 (m) Orientation 0, 20, 0 (°)

Design #3: For this design, we use two laser scanners on the corners of platform with some inclination (Table 5). This design is used with several MMS (Manandhar et al., 2000; http://www.3dlasermapping.com/).

Scene

To compare these different designs in simulation, we need to define the virtual scene. As shown in Figure 7, the chosen scene involves several buildings, bridges, parked cars, trees, pedestrians, etc. We chose a mobile platform (vehicle) speed of 50 km/h (13.89 m/s) for all the MMS designs. Vehicle movement is from right to left.

Comparative Analysis

Using the methodology proposed above, we perform a comparative analysis of different MMS designs. Table 6 shows the result of this analysis based on simulation (The value between the parentheses is the score before normalization). We used the coefficient of "Architecture for 3D tourism" shown in Table 1.

Accuracy and precision:

As the simulation gives perfect data (both navigation and imaging systems) in this experiment, we do not provide scores for the precision criterion.

Resolution: For the criterion of resolution, we have two sub-criteria: mean density and homogeneity value. As the scene is very large (4.5x10 6 points for design #1, 4.0x10 6 points for design #2 and 9.7x10 6 points for design #3), we take a part of the scene (0.6x10 6 points for design #1 for example).

We calculate the mean density by the equation ( 2). If we take the example of design #1, the value of mean density is 66.58 points /m². Using the equation (3), we obtain the score of mean density which is 1.82.

To obtain the normalized score, we assume that the ideal value of mean density is equal to 3 which means 1000 points/m² and minimum value is equal to 0.

As shown in Figure 8 which is an example of variation of homogeneity of part of point cloud with Design #2, we have too many points (high density, shown in blue color) in the road zone and not enough points (low density, shown in red color) in the top part of building facades. As we can see in Figure 9 which represents the histograms of distribution of points according to their value of point density (top for design #1, centre for design #2 and bottom for design #3), standard deviations (mentioned as σ) are high, hence, the value of homogeneity is not high. For the example of design #1, we calculate the standard deviation which is 57.13 points/m². Using the equation (4), we obtain the score of homogeneity which is 0.14.

To obtain the normalized score, we define the maximum value of homogeneity as equal to 1 and minimum value equal to 0. Completeness: For the criterion of completeness, we have significant differences between designs. Figure 10, Figure 11 and Figure 12 show the point cloud data of design #1, design #2 and design #3 for the virtual scene presented by false colors (albedo). In this article, we give approximate scores as we do not currently have tools to calculate exactly the completeness. Such a tool is under development.

To obtain the normalized score, we define the maximum value of completeness as equal to 100 % and minimum value equal to 0 %. For buildings, design #1 completes poorly because of non visible zones (blue circle in Figure 10). And even if we use two laser scanners for design #3, we can not cover all the building facades because of shadow zones. For example, as shown in the blue circle of Figure 12, buildings which are further from the trajectory of MMS than others were not completely scanned because of the shadow zones made by the near buildings. These missing building facades are scanned by design #2 Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p. 839-854, 2009. which has only one laser scanner (blue circle in Figure 11). But even this design can not cover all because of non visible zones (another side of buildings).

We estimate at 30 % the score of design #1 for this criterion because only the front facades are scanned (100 % would correspond to a complete scan of all front facades and two side-facades of buildings). We estimate at 50 % the score of design #2, which scanned one side of the facades and also the front facades. We estimate at 45 % the score of design #3, which scanned the other side facades and the front facades but less than design #2.

For bridges, design #1 and #2 complete poorly because of too many non visible zones (red rectangles in Figure 10 and Figure 11) which makes modeling with this data more difficult. On the other hand, data from design #3 provides enough data to carry out modeling (red rectangle in Figure 12).

As there is no occlusion on the road and the totality of road is visible by all three designs, enough data is provided.

Results of the Analysis

As shown in Table 6, we can conclude that design #3 is the best solution among all for the application of "Architecture for 3D tourism" with our example of coefficients. But this design is with two laser scanners and it causes some constraints which are not considered at this time (cost, size, etc.).

We can also confirm with the total score of design #1 and design #2 that a simple modification of spatial configuration of the laser scanner can improve the data quality.

CONCLUSION AND PERSPECTIVE

We have presented a methodology for comparative analysis of point cloud data quality from various designs of mobile mapping systems. We have defined several criteria for this analysis, for a given application, and proposed their score calculation. This has been illustrated using simulation.

The methodology presented can be used to design and validate new concepts of mobile mapping systems for a given target of data quality.

This methodology needs to be developed and made more precise, adding new criteria and constraints. The choice of coefficients is important and needs to be adapted to each application. Further developments are considered to complement the tools for computation of these criteria on specific data.

Figure 1 -

 1 Figure 1 -Accuracy and precision.

  N a = score for accuracy N p = score for precision ref = reference value (which equals to 1 m) Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p. 839-854, 2009.

Figure 2 -

 2 Figure 2 -Calculation of point density.

  density of the point i (points/m²) n = number of neighbor points D = mean density (points/m²) n T = total number of points of the data We propose giving a density score with the equation (3) which allows classification of density in several classes like class 0: 1 to 10 points/m², class 1: 10 Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p. 839-854, 2009.to 100 points/m², class 2: 100 to 1000 points/m², class 3 1000 to 10000 points/m², etc. score for the mean density D = mean density value (points/m²)

  of homogeneity σ = standard deviation for density (points/m²) D = mean density (points/m²) Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p. 839-854, 2009.

Figure 4 -

 4 Figure 4 -Point cloud with occluded zones (Abuhadrous, 2005).

Figure 4

 4 Figure 4 is a point cloud obtained from the data acquisition with LARA-3D, MMS prototype of MINES ParisTech. It presents the point cloud data of the facade of "MINES ParisTech" which contains several occluded zones.

  score x = value of design candidate m = minimum value possible (generally m = 0) M = maximum value possible (or ideal value)

Figure 5 -

 5 Figure 5 -LARA-3D

Figure 6 -

 6 Figure 6 -SiVIC and RTMaps.

Figure 6

 6 Figure 6 shows the generation of point cloud data during the simulation. The two windows in the lower part of the figure are from SiVIC (left: command window, right: visualization window). The two windows in the upper part and the background of the figure are from RTMaps (left: point cloud visualization window, right: command window, background: RTMaps diagrams).As we are studying the comparison of different MMS designs (configuration of laser scanners on the platform), we assume that the navigation system offers perfect data during the whole time (using perfect IMU in simulation) and that there is no calibration error between navigation and imaging systems so that all designs have the same level of accuracy and precision.

Figure

  Figure 7 -Virtual scene

Figure 8 -

 8 Figure 8 -Variation of homogeneity

Figure

  Figure 9 -histogram for homogeneity

Figure 10 -Figure

 10 Figure 10 -Point cloud of design #1

Table 1 -

 1 Example of coefficient.

	Criterion	Sub criteria	Architecture for 3D tourism
	Accuracy &	Accuracy	4
	Precision	Precision	4
	Resolution	Mean density Homogeneity	4 5
		buildings	4
	Completeness	bridge	3
		road	3

Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p.

839-854, 2009.

Table 2 -

 2 Characteristics of laser scanner in simulation

	Scanning rate	60 Hz
	Angular resolution	0.5 °
	Field of view	360 °
	Range	100 m (for albedo 20 %)

Table 5 -

 5 Configuration for design #3

		Scanner 1	Scanner 2
	Position	-1, -1, 1.8 (m)	-1, 1, 1.8 (m)
	Orientation	0, 20, 45 (°)	0, -20, 45 (°)

Table 6 -

 6 Comparative analysis table

	Criterion	Coefficien t	Design #1	Design #2	Design #3
	Accuracy	4	N/A	N/A	N/A
	Precision	4	N/A	N/A	N/A
	General Density	4	6 (1.82)	6.13 (1.84)	7.5 (2.25)
	Homogeneity	5	1.4 (0.14)	1.1 (0.11)	1.9 (0.19)
	Completeness (buildings)	4	3 (30)	5 (50)	4.5 (45)
	Completeness (bridge)	3	2 (20)	4.5 (45)	7 (70)
	Completeness (road)	3	9.5 (95)	9.5 (95)	9.5 (95)
	Total score	-	77.5	92.02	107

Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p.

839-854, 2009.

Bol. Ciênc. Geod., v. 15, n. 5 -Special Issue on Mobile Mapping Technology, p.839-854, 2009.

ACKNOWLEDGMENTS

The work reported in this paper has been performed as part of the Cap Digital Business Cluster "Terra Numerica" project.