Roben Joumard

DO EMISSION STANDARDS MEET ENVIRONMENT CHALLENGE?

The representativity of the European driving cycles (ECEl5 and EUDC) was analysed with respect to speed and accelerationfrom the results obtained in different instrumented stUdies carried out in Europe on about a hundred private cars. Thenfor 70 gas or diesel engined in-use vehicles, emission levels determined according to the applicable standard were compared to CO, HC and NOx emission values measured according to the standard or on in-use vehicles. Thus, the standard values are often exceeded, in particular for CO and HC emissions. ln addition it should be noted that American, Japanese and European emission standard are far behind the current environmental problems relating to air pollution. The relative significance of the different environment elements (population health, forest decline, greenhouse effect, ...) changes very rapidly,as weIl as the number ofrelated pollutants.A single standard taking inti account a weighted set of pollutants could better and more obviously meet the environment challenge and could provide car manufacturers with a larger choice og tlclean" technologies.

 :

scientific rationality aimed at protecting the whole population, and if required the whole environment, from pollutant effects; economic or industrial rationality aimed at protecting involved industries or furthering their development;

-political rationality which is the expression of the social awareness.

The standard drawn up is always the result of a compromise or arbitration; the great variety of interests at stake, the great variety of environment issues and even more how they are perceived in sorne country or other, as weIl as the advantages or problems of national industries can explain the great variety of standards. For example in Europe the standards fIrsdy met health requirements (CO, HC), then were a response to the forest decline (NOx). ln the United States, to health concems were added the visibility problem (particulates) and then the photochemical smog (HC, NOx).

Under present conditions, do the different emissions standards meet the requirements of the three rationality types hereabove mentionned? ln otherwords, do they actually allow ensuring that all the air pollution phenomena, as described by scientists and deemed signifIcant by the population, are correctly addressed, and that industrial requirements, and in particular as related to vehicle industry, are complied with at best with no more or less unwitting perverse effects?

The representativity of emission standards in terms of speed, and for the European standard in terms of emission, will be assessed. Then, due to the signifIcant development of environment challenges the very building of the standards will be discussed.

. Representativity of emission standards

Speed representativity

The speed cycles used signifIcantly vary according to the standard applied. For each case studied, these cycles are deemed representative of actual speed cycles: Americans used actual cycles that have been only slightly simplifIed and therefore are very realistic. Japanese or European cycles were reconstituted cycles that included only constant acceleration periods, so that transient phenomena were not fully represented. Speeds and accelerations are considered for the different cycles and are classifIed according to real driving conditions, e.g. as recorded in France [START_REF] Maurin | The /cinematic sequences, an atomistic approach to automobile travel and the effects oftraffic -Rech[END_REF]. Thus, four main driving cycles can be observed: slow urban, free flow urban, road and motorway driving cycles, which account for 3, 38, 50 and 9% of the distances covered by light vehicles in France respectively. European and Japanese cycles mainly consider free flow urban driving conditions while American cycles mainly take into account road driving conditions; i.e slow urban or fast motorway driving conditions are not addressed. Nevertheless, it is assessed that very high levels of CO and even of hydrocarbons are emitted at low speeds, while NOx are emitted at high speeds.

Standards also specify the gear box ratios to be used. The gear box ratios are set for all the vehicles in the ECE 15 cycle, while the Japanese and American cycles differentiate the 4-and 5-geared vehicles. The actual spacing of the gear box ratios which varies from one model to another is never taken into account and this leads to the use of test engine speeds that do not correspond to actual driving conditions, as the vehicle speed, gear box ratio and engine speed are related in an univoqual manner. Therefore, for vehicles with the highest gear box ratios, NOx emissions are underestimated as the vehicles are tested with engines running at lower speeds than those recorded under actual driving conditions.

Measurementssimultaneously carried out using the same methodology in France, Great Britain and Germany on 60 private cars driven by their usual driver(s) during a one month period [START_REF] André | Operating characteristics of cars in urban areas and their influence on exhaust emissions[END_REF] -showed that there is a great range of speeds and especiall y accelerations commonl y used by the drivers. The driving cycles uSed for standard drawing up, and in particular for the European standard, are not representative of such a variety.

Emission-related representativity

The ECE 15 standard representativity has been measured in terms of pollutant emissions over a representative sample of French passenger vehicles of the end of 1988 [START_REF] Joumard | Emissions unitaires de polluants des véhicules légers[END_REF]. Two complementary issues were addressed to measure representativity: do the emission level measured according to the standard correspond to the emission level measured under actual driving conditions and do the measurement method used (BCE 15) enable to accuratly ca1culate the evolution of vehicle emissions over sereral years ?

Pollutant emissions were measured under actual driving conditions using 10 driving cycles (fig.l), representing actual French driving conditions [START_REF] Joumard | Parure1 : Méthodologie de mesure des émissions réelles du parc automobile[END_REF][START_REF] Maurin | The /cinematic sequences, an atomistic approach to automobile travel and the effects oftraffic -Rech[END_REF]. To assess the representativity of the standardized ECE 15 and extra-urban (EUDC) driving cycles, emission levels measured for these cycles were compared to the assessed level of the emission curve on Inrets representative cycles using the same average speed, identical vehicles, Le as-received vehicles under hot start conditions. It can be noted (table 1) that for gas-engined vehicles. standardized cycles underestimate emissions by about 25% for aUthe pollutants studied, with nevertheless some discrepancies for some of them: e.g. the extra-urban driving cycle underestimates CO and HC emissions by about 50%.

For diesel-engined vehicles, the ECE15 cycle underestimates emissions by 15% in average, with nevertheless a good agreement for CO emissions. ln general, no problem is to be observed with extraurban driving cycle for these vehicles. a slight overestimation can even be observed, up to 30% for particulates.

As regards emissions, standardized cycles are globaUy located half way between stabilized speeds and representative cycles, which corresponds to actual speeds.

Compliance with the standard

The ratio evolution between emissions actuaUy measuredduring testing and the emission limits foreach vehicle during out-plant testing has been studied.

At ftrst, the deviations betWeen vehicle speciftcations and the standard to be applied were studied. The CO, HC, NOx or HC+NOx levels of the European standard were compared to the values of the same poUutants measured on as-received or tuned vehicles for the ECE 15 cycle.

For gas-engined vehicles, ftgure 2 shows that CO emissions -CO is the only poUutant which has been separatly regulated since the implementation of the European standardfor as-received vehicles are higher that those specifted in the standard, by 70 to 120%. Total HC emission is also signiftcantly higher than allowed in the standard, by 30 to 190%. On the other hand, NOx or HC+NOx emissions are in average signiftcantly lower than those aUowed.

The amendment to the standard (15-01 to 04) has no significant influence on the results. The situation is likely to be "standardized" for the most recent vehicles, either because they were less old, of they better complied with the standard when manufactured.

The average values obtained include a great variety of situations. Indeed a number of vehicles (gasengined vehicles) meets the standard requirements (see distributions fig. 3):

-for CO: 27% of the vehicles complied with the standard requirements before tuning (and 35% after); a signiftcant number of the values recorded exceeded by a factor 3 the standard values, by 1.92 in average (1.63 after tuning);

-for HC: 60% of the vehicles complied with the standard requirements before tuning (59% after), the average was 67% above the standard value (and 41 % after tuning);

-for NOx: 94% of the vehicles studied (1502 and 03 standard) complied with the standard requirements (96% after tuning), the average value was 54% (58% after tuning); -for HC + NOx (1504 amendment only): 78% of the vehicles compliOOwith the standard before and after tuning and the average decreased from 81% to 76% of the standard value.

Therefore it can be notOOthat vehicle tuning slightly improves the situation, even if it slightly increases NOx emissions. This improvment is not systematic: e.g. tuning of older vehicles (amendments 1500-01) significantly increases HC emissions and therefore the values obtainOOare very farfrom the standard requirements (see fig. 2).

Nevenheless our measurement conditions for the cold ECE15 cycle are not exactly those specified in the standard: the test temperature is the outside ambient temperature. Thus ambient temperature (and therefore engine temperature at stan) ranges from 20 to 30°only in 3 cases out of 48 studied for the cold ECE 15cycles with tuned and as-received vehicles (it is lower in all the other cases). This cou Id explain the significant number of recorded values exceeding the standard values. But in fact no significant and systematic discrepancy can be noted according to ambient temperatures:

-for CO, the percentage of values exceeding the standard values does not depend on ambient temperature for as-received vehicles, and is even lower in average for temperature under 20°C with tuned vehicles;

for HC, the percentage of exceeding values is lower for temperatures under 20°C (in average by 1.7 the standard value under 20°C, and 1.30 above) for as-received vehicles; after tuning, the percentage of exceeding values increases with temperature: by 1.24 and 2.42 times the standard value under and above 20°C.

For diesel engined vehicles whose emissions have been regulated from the implementation of the last amendment only ( 1504), the situation is excellent: aIl the vehicles highly comply with the CO and HC + NOx timit values, in average by 6% and 18% of the standard respectively (and by 5 and 16% after tuning).

. Rapid evolution of the environment challenges

The air pollution issue is multi-sided as many primary pollutants are to be taken into account and as it relates to varying and evoluting phenomena: effects on human health which historically justified the first studies and the drawing up of the first standards, perceived pollution (visible pollution, fumes, odors, soiling) which is essentially a nuisance and identified by the population to the whole air pollution (even if the expens are not much concemed with it in Europe), photochemical pollution which is becoming a worldwide concern after having been dealt with in the USA, the forest decline which is mainly a European concern and finally the greenhouse effect, the only type of air pollution which led to the rallying of the highest political authorities, and maybe soon new polluting effects on our environment ... Current emission standards do not comply with the multi -sided and evolutive character of air pollution: for example, many pollutants which have significant effects on health are not taken into account (PAH for example), the greenhouse effect or even photochemical pollution are not considered as such, Le as the result of the presence of a number of pollutants, each of which specifically contributes to these phenomena. Only sorne pollutants are taken into account but their emission limit is not related to their effects on the environment.

Nevenheless, increasing the number of pollutants to be considered can lead to significant discrepancies in the technological and therefore economic fields by making inadequate a given technology: such was the case in the United States where stringent standards on diesel particulates stopped the development of this technology while in other respect, diesel engines are far less polluting ~an gas engines (without catalyst): the comparison of 50 gas-engined and 20 diesel-engined vehicle emissions [START_REF] Joumard | Emissions unitaires de polluants des véhicules légers[END_REF] showed that diesel engine CO emissions were 30 rimes lower than gas engine emissions, and total HC emissions 15 times lower and NOx emissions 2-3 times lower (see table 2). ln the same way, the consideration of 3 pollutants, CO, HC and NOx naturally led to the adoption of a three-way catalyst which precluded the use oflean bum engine, even if it proved to be interesting as regards C02 emissions which no standard has taken into consideration. The multiplicity of concerns, and therefore the great number of pollutant emissions to be rOOucOO, the requirement of providing the most open as possible technological choice to meet all the environment challenges and the related energy challenge due to the greenhouse effect, 100us to consider the neOO of a more global and flexible designing of a new standard.

. Towards a global emission standard ?

The aim is to define a standard which addresses all the air pollution issues, each issue taking into account a limitOOnumber of more or less active primary pollutants. ln addition, this standard should be evolutive and be applied to any type of vehic1e without any discrimination.

First, the concept of "air pollution" could be define as the sum of different types of pollution (health effects, perceived pollution, greenhouse effect, etc...) weighted as a function of their significance according to the scientific community and even more the population through its representatives. It could be considerOOthat health effects should be weightOOby a factor 2, perceivOOpollution by a factor 1 and greenhouse effects by a factor 1.5.

Then, each pollution type could be express as the sum of a number of pollutants, each of them being weighted according to its contribution to pollution, as expens can assess it at a given rime according to their current knowledge. Thus the greenhouse effect is due to COz' HC (22 rimes more active), CO (5 times more active) and NOx (3 times more active). The standard could be written: standard =(BI' Pollution1 + Bz. Pollutionz + B3Pollution3 + ...) / (BI + Bz + B3+ ...)

Where Pollutioni=(OEi1.pollutant1emission + OEi2.polIutantzemis+ ...) / (OEi1.emis1+ OEi2.emisz+ ...)

The polIutioni "standard" must be nonned according to an average value for the whole traftic type considered at the initial period (e.g. passenger cars). Therefore for the initial period, a global emission level (GEL) representing aIl the air pollution phenomena and the average actual traffic emissions can be determined and nonned by definirion to the 100 value of initial period :

where e. is the j pollutant emission J level (in g/km).

This yields a Global Emission Level (GEL) representing the weighted sum of all pollutants emission levels, according to the weighting factors hereabove defmed.

e.

A more stringent standard -defmitelya politico-economicchoice -by n% willlead to the reductionof the global emission level by n% and thus, under equal traffic conditions, to an actual n% improvement of the air environment Car manufacturers will be required to comply with the new global standard, but will be given the possibility of selecting by themselves appropriate technologies, even through increasing the emission of such pollutant provided that emissions of such other(s) will be reduced. The knowledge development in ~e environment field can allow the taking into account of new pollutions or new pollutants. A new global emission level should therefore be defined.

Conclusion

Current vehicle poIlutant emissions standards are not much representative of the actual use of vehicles from a speed perspective. They are therefore inadequate to represent the actual emission evolution: a more stringent standard may lead to no actual emission evolution as these standards, and in particular the European standard, significantly underestimate the role of very low or very high speeds, high accelerations or decelerations, as weIl as periods driven at slightly varying speeds.

ln addition, the standard definition in terms of pollutants and emission limit for each pollutant is far from representing all the environment concems which can rapidely change. Such a definition can further a given technology to the de triment of another one on no environment basis, and pratically impose a specific technology on manufacturers.

A unique global standard could therefore present sorne advantages as considered above. The building of such a standard, to be adequate and evolutive, requires the knowledge of traffic average emissions at a given initial period, for all the pollutants considered. ln addition it assumes in a simplifying manner that each type of pollution is due to a linear emission combination of different pollutants.

Nevenheless, provided that these requirements are met, the advantage of such an approach is that the standard could be representative on the one hand of the complex environment challenges, and on the other hand could provide motor engineers with a wider room to manoeuvre.

Figure 2 :Figure 3 :

 23 Figure 2: Average of the ratio emission measured in co Id ECE 15 cycle/standard series emission limit, according to the pollutant studied and the successive amendments to ECE 15 standard.

Table 1 :

 1 Approximate relative position of emissions in standardized fully warmed-up cycles as compared to representative lnrets hot cycles using the same average speed with as-received vehicles.Underestimation of the results for the ECE 15 cycle is a function of the poUutant studied and mainly of the fuel type used. The ECE 15 cycle, as the EUDC for gas-engined vehicles only, gives an erroneous and inaccurate emission representation.

	--t-

Table 2 :

 2 average of gasoline engined/diesel engined vehicle emission ratios for Inrets cycles with asreceived vehicles using cold and hot starts.


Andrés Serna

Beatriz Marcotegui

Jorge Hernández

Segmentation of Façades from Urban 3D Point Clouds using Geometrical and Morphological Attribute-based Operators

Keywords: 3D urban analysis, laser scanning, segmentation, façades, mathematical morphology, attribute-based operators, geodesic elongation

. The performance of our methods is proved in our experiments on TerraMobilita databases using 2D and 3D ground truth annotations.

Introduction

Building segmentation can be defined as the process of separating buildings from other objects such as natural and artificial ground, vegetation and urban objects. First researches on automatic building extraction began in the 80s. They used aerial imagery and focused on the extraction of high-level 2D and 3D primitives from stereo images. One of the main drawbacks of these methods is that some false positives need to be filtered out since some linear primitives may not correspond to meaningful structures. In computer vision, elevation images were introduced as data structures allowing direct access to 3D geometric features. First elevation images were mostly acquired from small objects and scenes, using active systems. During the 90s, aerial laser scanning (ALS) became widely available so elevation images of huge scenes and cities became possible. Accuracy and point density of those systems are in constant progress. More recently, new acquisition systems such as terrestrial (TLS) and mobile laser scanning (MLS) have been developed, adding not only greater geometrical accuracy and extremely high density, but also façade scans, not visible from ALS [START_REF] Vosselman | Airborne and Terrestrial Laser Scanning[END_REF].

Although the processing of 3D urban data has been underway for many years, façade segmentation is still an open problem. Several contributions on this domain are proposed in this paper.

Our processing assumes that ground has been already segmented. In our works we have used the approach already published in [START_REF] Hernández | Point cloud segmentation towards urban ground modeling[END_REF][START_REF] Serna | Urban accessibility diagnosis from mobile laser scanning data[END_REF]. Once the ground is segmented, all remaining structures are considered as façades and objects. Using TLS and MLS data, only building front parts are visible, as shown in Figure 1. It is noteworthy that façades constitute the highest and longest vertical entities in the urban scene.

This work has been developed in the framework of TerraMobilita project [START_REF] Capdigital | TerraMobilita:3D mapping of roads and urban public space, accessibility and soft mobility[END_REF] and is organized as follows. Section 2 reviews related works in the state of the art. Sections 4 and 5 introduce two different approaches to segment façades: with and without markers, respectively. Section 6 describes a method to segment city blocks taking advantage of the façade segmentation result. Finally, Section 8 concludes this work.

Related work

Goulette et al. [START_REF] Goulette | An Integrated on-Board Laser Range Sensing System for On-the-Way City and Road Modelling[END_REF] develop a MLS system, called LARA-3D, that acquires and segments in real-time ground, façades and objects. Ground and façades are detected fitting horizontal and vertical planes, then remaining points are considered as objects. In a similar way, Boulaassal et al. [START_REF] Boulaassal | Automatic segmentation of building facades using terrestrial laser data[END_REF] segment building façades using the RANSAC algorithm on TLS data. In general, approaches based on plane extraction are proved to be simple, fast and useful as input for high-level approaches devoted to create accurate geometric models. However, their main drawback is that plane extraction may fail when ground and façades are not flat enough. Moreover, façades may be over-and under-segmented due to architectural details such as balconies.

Bab-Hadiashar and Gheissari [START_REF] Bab-Hadiashar | Range image segmentation using surface selection criterion[END_REF] propose a method to segment planar and curved surfaces in range images. Their method consists in selecting the appropriate parametric model that minimizes strain energy of fitted surfaces. The authors applied their methodology to indoor range images of the University of South Florida (USF) database [START_REF] Hoover | University of South Florida (USF) Range Image Database[END_REF]. Several works on the parametric model fitting problem can be found in the literature [START_REF] Boyer | The Robust Sequential Estimator: a general approach and its application to surface organization in range data[END_REF][START_REF] Werghi | Modelling Objects Having Quadric Surfaces Incorporating Geometric Constraints[END_REF][START_REF] Marshall | Robust Segmentation of Primitives from Range Data in the Presence of Geometric Degeneracy[END_REF][START_REF] Chaperon | Extracting cylinders in full 3D data using a random sampling method and the Gaussian image[END_REF][START_REF] Lari | An adaptive approach for the segmentation and extraction of planar and linear/cylindrical features from laser scanning data[END_REF]. Those works can be extended in order to segment surfaces such as ground and façades on elevation images. Their main drawbacks are that they require a model estimation which can be different for different images, are time consuming due to minimization procedures and may produce under-and over-segmentation.

Demantke et al. [START_REF] Demantke | Dimensionality based scale selection in 3D LiDAR point clouds[END_REF] propose a method to adapt 3D spherical neighborhoods based on local features. Radius selection is carried out optimizing local entropy. Then, dimensionality features are calculated. These features can be useful to classify 1D structures such as pole-like objects, 2D structures such as ground or façades, and 3D volumetric structures such as trees and urban objects. Hernández and Marcotegui [START_REF] Hernández | Point cloud segmentation towards urban ground modeling[END_REF] assume that façades on the same street are aligned, which is verified in their Paris-rue-Soufflot database. They use the Hough transform to find façade directions. Then, they analyze the height of each profile in order to detect façades and city blocks. Hammoudi [START_REF] Hammoudi | Contributions to the 3D city modeling[END_REF] presents a similar technique based on the Progressive Probabilistic Hough Transform in order to detect walls and windows. He assumes that building façades are mainly vertical, so it is possible to generate an accumulation image to compute the number of points projected on each pixel.

Other works aiming at segmenting façades are available in the literature [START_REF] Sevcik | Documentation of complex facades and city modelling through the combination of Laserscanning and photogrammetry[END_REF][START_REF] Rutzinger | Tree modelling from mobile laser scanning data-sets[END_REF][START_REF] Poreba | RANSAC algorithm and elements of graph theory for automatic plane detection in 3D point clouds[END_REF][START_REF] Serna | Attribute controlled reconstruction and adaptive mathematical morphology[END_REF][START_REF] Weinmann | Feature relevance assessment for the semantic interpretation of 3D point cloud data[END_REF][START_REF] Weinmann | Semantic 3D scene interpretation: A framework combining optimal neighborhood size selection with relevant features[END_REF]. Additionally, color images can be used in order to enrich façade segmentations. For example, several works available in the literature use color images to segment façades keeping architectural details such as balconies and windows. Then, those results are used to colorize 3D point clouds providing a realistic rendering [START_REF] Shao | ZuBuD -Zurich Building Database for Image Based recognition[END_REF][START_REF] Hernández | Morphological segmentation of building façade images[END_REF][START_REF] Teboul | Segmentation of building facades using procedural shape priors[END_REF][START_REF] Serna | Adaptive parameter tuning for morphological segmentation of building facade images[END_REF][START_REF] Teeravech | Discovering repetitive patterns in facade images using a RANSAC style algorithm[END_REF].

In general, methods based on planar extraction, Hough transform and model fitting are not generic enough since façades can have different shapes and contain different architectural details. Moreover, the problem of objects touching the façade, such as urban furniture or parked motorcycles, is rarely analyzed in the literature. In this paper, we address these problems proposing methods based on geometric and elongation features computed on projection images. These methods are robust to extract façades of several shapes and correctly separate objects touching the façade.

Projection Images

Once a 3D point cloud is acquired, a suitable data structure is not only required to inspect and visualize the information quality, but also to process it conveniently. Point clouds are delivered as long lists of (x, y, z) coordinates, possibly with attributes such as intensity and color. Points are usually listed in scan line order, which is not suitable for efficient processing. For example in a (x, y, z) list, it is not possible to quickly determine the neighbors of a point within some radius. Data structures such as projection images, Delaunay triangulation, octrees and k-D trees allow this kind of processing. Choosing the proper data structure is application dependent, moreover it is possible to combine some of them to get better results in specific tasks such as visualization, filtering, segmentation and classification [START_REF] Vosselman | Airborne and Terrestrial Laser Scanning[END_REF].

As aforementioned, our method is based on projection images. 3D point clouds are projected to elevation images because they are convenient structures to visualize and to process data. One can utilize all the large collection of existing image processing tools, in particular mathematical morphology [START_REF] Serra | Image analysis and mathematical morphology[END_REF][START_REF] Soille | Morphological image analysis: principles and applications[END_REF]. Additionally, images can be processed quickly, implicitly define neighborhood relationships and require less memory than 3D data. In general, the idea of deriving elevation images from 3D point clouds is not new. Nevertheless, the development of accurate and fast urban analysis algorithms is still an open problem.

Elevation images are 2.5D structures that contain depth information at each pixel. They are generated by an orthographic projection to a virtual camera plane, i.e. the depth is the distance from each 3D point to the projection plane. The camera model P is a projective transformation from R 3 → N 2 , and it can be decomposed in three sequential transformations as follows:

Definition 1. Let M = (X, Y, Z) be a 3D point in R 3 and m = (u, v) a point in the image space N 2 .
The camera model P is defined as the successive transformations:

(X, Y, Z) T -→(X c , Y c , Z c ) P -→(x, y) A -→(u, v) (1)
[T ] = [Rot] t 0 T 1 Rot: Rotation matrix t: translation vector

[P ] =    1 0 0 0 0 1 0 0 0 0 f oc -1 0    f oc: focal length [A] =    kx 0 cx 0 ky cy 0 0 1   
where, (c x , c y ) is the intersection point between the optical axis and the image plane, (k x , k y ) are the number of pixels per unit of length, R w is the real world coordinate system, R c is the camera coordinate system with origin in the optical center, and R r is the projection plane coordinate system. The virtual camera is chosen such that:

• It is located on the horizontal plane with normal vector -→ n = (0, 0, 1) and crossing the lowest point (0, 0, z min ). Therefore, the Rotation matrix [Rot] is equal to the identity.

• The point cloud and the projection plane are centered on the gravity center of the point cloud. Thus, the translation vector t is equal to the gravity center, and the intersection point (c x , c y )=(0,0).

• The projection is orthographic. Thus, the projection axis is orthogonal to the projection plane and the projection center is located at the infinity. It means, f oc = ∞, x = X c and y = Y c .

According to these assumptions, the number of pixels per unit of length is the only free parameter. In order to simplify this selection, we assume k x = k y = k. It has to be carefully chosen. On the one hand, if k is too small, fine details are not preserved because too many points would be projected on the same pixel. On the other hand, too large k implies connectivity problems and large image sizes, which implies higher computational time that would no longer justify the use of elevation images instead of 3D point clouds. This parameter is the most critical in terms of quality versus processing time. In our experiments, we have chosen k = 5pix/m thanks to a priori knowledge about point cloud density.

During projection, several points can be projected to the same pixel. Thus, four elevation images are defined:

• Maximal elevation image (f max ), or simply elevation image, stores the maximal depth among all projected points on the same pixel.

• Minimal elevation image (f min ), stores the minimal depth among all projected points on the same pixel.

• Height image (f height ), contains the difference between maximal and minimal elevation images.

• Accumulation image (f acc ), stores the number of points projected on each pixel.

In general, processing steps are performed combining these images and resulting image can be reprojected to the 3D point cloud. Figure 2 presents the 3D point clouds and the elevation images for our two Paris test sites. Image projections imply a reduction in the amount of data to be processed. Therefore, processing 2.5D images using image processing techniques is much faster than process the 3D points directly. Moreover, neighborhood relationships are given in images without any additional computation. In order to avoid connectivity problems due to occlusions or low dense point clouds, an interpolation may be applied. This topic is out of the scope of this paper. For further details on interpolation of elevation images, the reader is encouraged to refer to Serna and Marcotegui [START_REF] Serna | Urban accessibility diagnosis from mobile laser scanning data[END_REF], Hernández and Marcotegui [START_REF] Hernández | Filtering of artifacts and pavement segmentation from mobile LiDAR data[END_REF].

Façade segmentation using markers

In order to segment façades, we propose a marker-based method using geometrical constraints. After marker extraction, a reconstruction is applied in order to get the entire façade. Let us explain first the façade marker extraction and later in Section 4.2 the reconstruction process.

Façade marker extraction

The height image f height is appropriate to compute façade markers since it contains information about high and vertical structures, as shown in Figure 3.

Figures 3(a From the work by Hernández and Marcotegui [START_REF] Hernández | Filtering of artifacts and pavement segmentation from mobile LiDAR data[END_REF], we use the two following geometric constraints on f height in order to extract façade markers:

• h min , defining the minimal allowed façade height. In our experiments, this variable has been set to 3.5 m according to architectural characteristics of our databases. This threshold is illustrated in Figure 4(a). Note that only the highest objects are preserved.

• L min , defining the minimal allowed façade length. In our experiments, this variable has been set to 5 m according to architectural characteristics of our databases. This threshold is illustrated in Figure 4(b). Note that small objects such as lampposts and objects behind façades are not long enough and are then eliminated.

In addition, we propose a third constraint in order to eliminate round objects such as trees:

• C min , defining the maximal allowed façade circularity (circularity of an object X is defined as the inverse of its elongation Circ(X) = 1/E(X). In this work, we focus on geodesic elongation, simply called henceforth elongation [START_REF] Lantuéjoul | Geodesic methods in quantitative image analysis[END_REF]. The elongation E(X) of an object X is a shape descriptor useful to characterize long and thin structures. It is proportional to the ratio between the square geodesic diameter L 2 (X) and the area of the object A(X), as shown in Eq. 2. The geodesic diameter L(X) = sup x∈X {l x (X)} is the length of the longest geodesic arc of X, i.e. the longest internal segment l x (X) connecting the two end points of X [START_REF] Lantuéjoul | On the use of the geodesic metric in image analysis[END_REF]. The longer and narrower the object, the higher the elongation. The lowest bound is reached with the disk, where E(X) = 1.

An efficient implementation can be found in Morard et al. [START_REF] Morard | Efficient geodesic attribute thinnings based on the barycentric diameter[END_REF].

E(X) = π 4 L 2 (X) A(X) (2)
In our experiments, C min has been heuristically set to 1/3, which corresponds to the circularity of an ellipse whose major axis is 3 times longer than the minor one. This value is appropriate to filter tree-tops since circularity of a circle is equal to 1. This threshold is illustrated in Figure 4(c). Note that non-elongated objects such as the two trees in the right street side have been eliminated.

Using these constraints, we extract façade markers as the union of connected components (CC) higher than h min , longer than L min and less circular than C min , as established in Definition 2: Definition 2. Let f height be a height image f height : D → V , with D ⊂ Z 2 the image domain and V = [0, ..., H] the set of gray levels mapping the pixel height. Let Th(f height ) be the binary image containing the pixels higher than h min :

Th(f height ) = {p ∈ D|f height (p) > h min } (3)
Let C 1 , C 2 ,..., C n be the connected components of image Th(f height ):

Th(f height ) = n i=1 C i , i = j ⇒ C i ∩ C j = ∅ (4)
Then, façade markers F mark are the connected components C i of image Th(f height ) which are longer than L min and less circular than C min :

F mark = {C j |L(C j ) > L min ∧ Circ(C j ) < C min } (5)
∀j ∈ {1, ..., n}, where L(C j ) and Circ(C j ) are respectively the geodesic diameter and the circularity of connected component C j .

It is noteworthy that these three parameters (h min , L min and C min ) are easy to tune since they have a physical meaning and depend on urban/architectural constraints. Figure 4 illustrates this marker selection process.

Due to specific requirements in our TerraMobilita datasets, several 3D point clouds have been acquired with the laser system oriented to the ground. Therefore, structures higher than 2.5 m are out of the laser field of view, as shown in Figure 5. This is challenging for methods using height constraints since high wall parts are not visible.

To solve this problem, we propose a solution taking advantage of the acquisition cycle of the MLS sensor, as shown in Figure 6. In our configuration, the sensor spins scanning vertical lines starting from the top. Thus, the first and the last point of each spin correspond to the highest point on the right and on the left street side, respectively. These highest points are usually located on the façade and can be extracted by detecting sign changes in the angle of depression (computed using the sensor position) between consecutive points. Then, these markers are added to image Th(f height ) and isolated points are filtered out using the same process than before: only markers longer than L min and less circular than C min are considered as façade markers. Figure 7 illustrates façade marker extraction when the laser sensor is oriented to the ground.

Façade reconstruction from markers

As mentioned earlier, façade markers only contain partial façades. Therefore, a reconstruction should be applied from those markers in order to retrieve the whole façade. With this purpose, we use a reconstruction constrained by the ground residue. Ground G is assumed to be previously computed using either our ground segmentation method proposed in [START_REF] Serna | Urban accessibility diagnosis from mobile laser scanning data[END_REF][START_REF] Hernández | Filtering of artifacts and pavement segmentation from mobile LiDAR data[END_REF] or any other method reported in the literature [START_REF] Golovinskiy | Shape-based recognition of 3D point clouds in urban environments[END_REF][START_REF] Munoz | Onboard contextual classification of 3-D point clouds with learned high-order Markov Random Fields[END_REF][START_REF] Mallet | Relevance assessment of full-waveform LiDAR data for urban area classification[END_REF][START_REF] Pu | Recognizing basic structures from mobile laser scanning data for road inventory studies[END_REF].

Ground residue G c is computed as the difference between the elevation image and the ground image: G c = f max -G. Then, a first solution for the reconstruction process consists in a set of increasing geodesic dilations applied until idempotence. This transformation is called reconstruction by dilation [START_REF] Lantuéjoul | On the use of the geodesic metric in image analysis[END_REF] and is defined as follows: Definition 3. Reconstruction by dilation. The reconstruction by dilation of a mask image G c from a marker F mark ≤ G c is defined as the geodesic dilation of F mark within G c until idempotence and it is denoted by:

R δ G c (F mark ) = δ (i) G c (F mark ) ( 6
)
where i is the geodesic dilation size for which idempotence is reached, i.e. δ (i+1)

G c (F mark ) = δ (i) G c (F mark )
Figure 8 illustrates the façade segmentation based on reconstruction by dilation. Figure 8(a) an elevation image and Figure 8(b) its corresponding height image. Figure 8(c) shows the façade markers F mark computed by the method explained above in Section 4.1. Figure 8(d) presents the ground segmentation result G, while Figure 8(e) presents the ground residue G c . Finally, Figure 8(f) shows the façade segmentation obtained by reconstruction by dilation of the ground residue from the façade markers. Note that pixels behind façades have been included in the segmentation result. This method is fast and easy to implement. However, the main drawback is that objects connected to the façade, e.g. motorcycles or pedestrians leaning on walls or objects behind façades, are reconstructed as well.

Figure 10 presents this segmentation result reprojected onto the 3D point cloud. Note that the reconstruction by dilation retrieves not only the entire façade but also other objects connected to it. For example, a store, a pedestrian and a traffic sign on the right sidewalk have been wrongly reconstructed.

In order to solve the problem of objects touching the façade, we propose an attribute controlled reconstruction from façade markers. This procedure has been previously published in Serna and Marcotegui [START_REF] Serna | Attribute controlled reconstruction and adaptive mathematical morphology[END_REF]. It consists in appending nearby points with similar height. The propagation process stops when a given attribute reaches its maximum value. In our case, we use increasing propagations from façade markers over λ-flat zones, called also in the literature quasi-flat zones [START_REF] Meyer | Mathematical Morphology and its Applications to Image and Signal Processing[END_REF]. As façades are the longest and most elongated structures in the elevation image, we keep the propagation that maximizes the geodesic elongation.

Let us introduce a formal definition for the façade segmentation process using attribute controlled reconstruction: Definition 4. Attribute controlled reconstruction. Let G c be a digital elevation image containing the ground residue G c : D → V , with D ⊂ Z 2 the image domain and V = [0, ..., H] the set of gray levels mapping the elevation values. Two neighboring pixels p, q belong to the same λ-flat zone of G c , if their absolute difference |G c (p) -G c (q)| is smaller than or equal to a given λ value.

For all x ∈ F mark ⊆ D, let Λ be the set of increasing regions containing marker pixel x. For all λ ∈ V and j = [1, ..., n -1], we define A λ (F mark ) ∈ Λ as the λ-flat zone of image G c containing marker F mark :

A λ (F mark ) = {x} ∪ {q|∃℘ = (p 1 = x, ..., p n = q) such that |G c (p j ) -G c (p j+1 )| ≤ λ} (7)
Let E(A λ (F mark )) be the geodesic elongation of λ-flat zone A λ (F mark ). For all λ i ∈ V and i = [0, ..., R], we define λ M as the value for which the elongation is maximum:

λ M = argmax λ i ∈V |E(A λ i (F mark ))| (8)
Then, we define A λ M (F mark ) as the attribute controlled reconstruction of the façade from marker F mark .

Using this controlled reconstruction maximizing the geodesic elongation, it is possible to reconstruct the façade without merging adjacent objects. Figure 9 compares façade segmentation methods using reconstruction by dilation R δ G c (F mark ) and attribute controlled reconstruction A λ M (F mark ), both from marker F mark . It is noteworthy that neither objects connected to the façade nor objects behind it have been reached by the attribute controlled reconstruction. Figure 10(d) presents the segmentation result using attribute controlled reconstruction reprojected onto the 3D point cloud. Compared to Figure 10(b), note that the store, the pedestrians and the traffic sign have not been included in the façade. Additionally, several objects such as wall lamps and objects behind façades have been correctly separated.

Discussion

Methods based on markers are robust to segment non-planar façades and façades with several architectural details and balconies, such it is the case in Parisian buildings. Moreover, these methods are simple and fast since they are based on geometric constraints, easily translated into threshold values. In the case of low façades or when the laser sensor is oriented to the ground, additional markers corresponding to the highest points of each laser cycle are added. Since markers only contain partial façades, a reconstruction is required in order to get the entire façade. In our case, reconstruction is constrained to the ground residue.

In this section, we have proposed two reconstructions: i) a classic reconstruction by dilation: ii) a reconstruction based on attribute controlled propagation. The performance of these methods strongly depends on the markers selection. A wrong marker may produce errors since it will reconstruct the marked object, even if it is not a façade. In our experiments, our marker selection method has proved to be efficient in many cases. However, objects such as tree alignments may produce false markers, therefore wrong segmentations, as shown in Figure 11. The reason of this problem is that our circularity criterion fails filtering trees alignments since their footprints may be elongated enough. Changing the value of circularity does not seem to be a good idea. On the one hand, reducing the circularity value would affect the recall of the method, i.e. less façades would be detected. On the other hand, increasing the circularity value would increase the number of false positives. This is our motivation to propose a third method, more robust than the two proposed previously, avoiding the use of façade markers. Our idea is analyzing the elongation and its evolution over the height decomposition of the 3D scene. Let us introduce such a method in the following section. In order to segment façades avoiding the use of markers, we propose a method based on threshold decomposition and attribute profiles. In [START_REF] Serna | Segmentation of elongated objects using attribute profiles and area stability: Application to melanocyte segmentation in engineered skin[END_REF], we have introduced this method in order to segment elongated objects on gray-scale images. Let us remind its definition in the 2D case: Definition 5. 2D Attribute profile. Let I be a digital gray-scale image I : D → V , with D ⊂ Z 2 the image domain and V = [0, ..., R] the set of gray levels. A decomposition of I can be obtained considering successive thresholds:

Façade segmentation without markers

T t (I) = {p ∈ D|I(p) > t} ∀t = [0, ..., R -1] (9)
Since this decomposition satisfies the inclusion property T t (I) ⊆ T t-1 (I), ∀t ∈ [1, ..., R -1], it is possible to build a tree, called the component tree, with level sets T t (I). Each branch of the tree represents the evolution of a single connected component X t . An attribute profile is the evolution of an attribute (e.g. area, perimeter, elongation, average gray-level, etc.) of a given CC along a branch of the tree.

Figure 12 illustrates the threshold decomposition for a 1D function, its component tree and the attribute (width) profiles for the two function maxima (p A and p B ). Events on this attribute profile are useful to segment objects [START_REF] Jones | Connected Filtering and Segmentation Using Component Trees[END_REF], extract features [START_REF] Pesaresi | A new approach for the morphological segmentation of high-resolution satellite imagery[END_REF][START_REF] Beucher | Numerical residues[END_REF][START_REF] Morard | Region Growing Structuring Elements and New Operators based on their Shape[END_REF] and define adaptive structuring elements [START_REF] Serna | Attribute controlled reconstruction and adaptive mathematical morphology[END_REF].

T Z t (P ) = {m i ∈ D | t∆z < z i < (t + 1)∆z}; ∀t = [0, ..., R -1]; ∀i = [0, ..., N ] (10)
Contrarily to the 2D case, this decomposition does not satisfy any inclusion property. However, it is always possible to analyze the evolution of a single connected component X t over horizontal slices T Z t (P ). A 3D attribute profile is the evolution of an attribute (e.g. number of points, density, average elevation, etc.) of a given CC along the decomposition.

More adapted to our 3D urban data, let us define an adaptive decomposition using slices parallel to the ground. From Definition 6, we propose the following decomposition: Definition 7. Adaptive voxelization using ground information. Let G be a digital gray-scale image G : D → V , with D ⊂ Z 2 the image domain and V = [0, ..., R] the set of gray levels mapping the ground elevation, resulting from a given ground segmentation process. A decomposition of a 3D point cloud P using slices parallel to the ground can be obtained considering successive thresholds from the ground separated by a given height ∆z:

T gr t (P ) = {m i ∈ D | G(m i ) + t∆z < z i < G(m i ) + (t + 1)∆z} (11) ∀t = [0, ..., R -1]; ∀i = [0, ..., N ]
This decomposition is equivalent to an adaptive voxelization, as shown in Figure 13. Dashed lines represent slices parallel to the ground. For each slice, an occupancy grid is defined according to the elevation image pixel size 1/k, where k is the number of pixels per unit length (For further details, see [START_REF] Serna | Semantic analysis of 3D point clouds from urban environments: ground, facades, urban objects and accessibility[END_REF]). Each voxel is labeled full if there is at least one 3D point inside, or empty otherwise. Finally, these occupancy grids are stacked in a binary 3D image. For each slice, attributes are computed on each binary CC. We propose to segment façades using the maximal elongation image computed from the attribute profile of decomposition T gr t . With this aim, we compute the geodesic elongation E(X t ) for each CC on each slice parallel to the ground. Then, for each pixel m i , we store the maximal elongation over the whole decomposition:

E max (m i ) = max|E(X t (m i ))|; ∀X t ∈ T gr t ; ∀t ∈ [0, ..., R -1] (12)
Such feature image is a partition of the space where each pixel contains information about elongation of its neighborhood. Then, it is useful in segmentation tasks where some prior shape knowledge is available. This decomposition is used to segment façades while filtering out other structures, such as objects connected to it. The slice height has been set to ∆z = ∆λ = 1.0 m since we are only interested in connected objects higher than 1.0 m (motorcycles, pedestrians, urban furniture, etc.). Additionally, it offers a trade off between processing time and performance since only a few tens of slices are required to decompose an urban scenario without skyscrapers. Figure 14 illustrates an example of façade segmentation using this approach. Figure 14(a) shows the elevation image. Figure 14(b) presents the elongation image computed from the threshold decomposition of the 3D point cloud. Figure 14(c) presents the segmentation result applying a simple threshold on the elongation image. We define E min as the minimal elongation allowed for a façade. In our experiments, we have heuristically set E min =20, which corresponds to the elongation of a rectangle whose length is approximately 25 times longer than its width. It is noteworthy that this elongation threshold is more restrictive than that used for marker extraction (section 4.1) since here we are interested in detecting the maximal elongation value over all the decomposition.

Figure 15 presents a façade segmentation result on a test site in rue Bonaparte in Paris, France. With respect to Figure 11 most façades are correctly segmented. Some problems appear in the left part: zone 1, where the side part of a bus has been wrongly detected as façade; and zone B, where bushes and vegetation over a low wall could not be separated (Figure 15(d)). These objects present a high elongation, then they have been wrongly segmented as façades.

City block segmentation

A city block is the smallest area that is surrounded by streets. A wide variety of sizes and shapes can be found in urban environments. In general, it depends on historic, demographic and geographic constraints. For example, many pre-industrial cities tend to have irregular city blocks, while newer cities have usually much more regular arrangements [44].

In our application, city blocks are considered as the biggest semantic entities in the urban environment. Their segmentation is useful for individual city block analysis. Additionally, each city block can be processed separately and their results joined at the end of the analysis, reducing memory requirements and allowing parallelization.

Once façades have been segmented using one of our three proposed methods, we compute the influence zone (IZ) of each façade in order to define city blocks. The IZ algorithm was one of the first morphological operators applied to image segmentation. It was discovered in the 70s from the iterative application of basic operators such erosion and dilation [START_REF] Matheron | Random Sets and Integral Geometry[END_REF][START_REF] Serra | Mathematical Morphology and Its Applications to Image Processing[END_REF]. The IZ of a given CC is defined by the set of pixels of a binary image that are closer to this CC than to any other CC on the image. Let us introduce its formal definition: Definition 8. Influence zones (IZ). Let X be a binary image and K 1 , K 2 ,..., K n the CC of X. The influence zone of K i is the set of pixels of image X that are closer to K i than to any other CC of image X:

IZ(K i ) = {p|∀j ∈ {1, ..., n}, i = j ⇒ d(p, K i ) < d(p, K j )} (13)
It is noteworthy that this is an alternative definition of Voronoi diagrams [START_REF] Voronoi | Nouvelles applications des paramètres continus à la théorie des formes quadratiques[END_REF]. In practice, the IZ of a binary image is computed using a constrained watershed on the distance function of the binary image. Figure 16 illustrates this city block segmentation. Figure 16(a) shows the elevation image. Figure 16(b) presents the binary image containing the façade segmentation result. Figure 16(c) shows a morphological closing of size S min in order to reconnect near façades belonging to the same city block, i.e. S min stands for the minimal separation between city blocks. Figure 16(d) shows the medial road axes useful to avoid defining city block crossing the street. This information is used if available and it can be obtained from the vehicle trajectory or from an external 2D map. Figure 16(e) illustrates the distance function

Results

Our façade segmentation methods have been tested on TerraMobilita1 datasets in order to get qualitative and quantitative results. Two types of ground truth (GT) annotations are available:

• 2D lines indicating the separation between sidewalks and buildings. These 2D manual annotations are usually provided by local authorities. In our case, they have been obtained from Open Data Paris2 , a project from Paris city hall (Mairie de Paris, in French) in order to make urban data available to the community. Evaluations using 2D lines are commonly used in the state of the art when 3D annotations are not available [START_REF] Serna | Urban accessibility diagnosis from mobile laser scanning data[END_REF][START_REF] Vosselman | Detection of curbstones in airborne laser scanning data[END_REF][START_REF] Zhou | Mapping curbstones in airborne and mobile laser scanning data[END_REF]. These evaluations give an idea on the segmentation method performance. However, results should be carefully interpreted since the evaluation is only carried out on the 2D space at the ground level, the performance segmenting 3D features such as tilted façades, architectural details and balconies cannot be directly evaluated.

(a) Façade segmentation using the elongation image (method without markers). Façade (blue) and other (gray). • 3D point-wise annotations, i.e. a class is assigned to each 3D point. These point-wise annotations allow a global evaluation taking all façade points into account. In our opinion, this evaluation is the most appropriate, however complete 3D manual annotations are rarely available in the state of the art. In our experiments, we have used 3D annotations and evaluation methods developed in the framework of TerraMobilita/iQmulus benchmark 3 .

Evaluations based on each type of GT annotation are presented in the two following subsections.

Results: Evaluation using Open Data Paris

We have chosen 4 MLS datasets from 6 th Parisian district in France. Data have been acquired by Stereopolis II [START_REF] Paparoditis | Stereopolis II: A multi-purpose and multi-sensor 3D mobile mapping system for street visualisation and 3D metrology[END_REF], a MLS system by the National French Mapping Agency (IGN -In French Institut National de l'Information Géographique et Forestière). 23 GT annotations have been obtained from Open Data Paris and correspond to 2D lines indicating the junction between sidewalks and buildings at the ground level. Quantitative analyses are performed by comparison between automatic and GT lines on a 2D image. When 3D façade points are projected to a 2D plane, they are usually wider than a single line due to façade inclination, architectural details and balconies. Therefore, buffers around GT lines and segmented façades are required in order to evaluate the results.

On the one hand, a segmented façade is labeled as true positive or false positive if it is located inside or outside a GT buffer, respectively. On the other hand, a GT façade is labeled as segmented or missed if it is located inside or outside a segmented façade buffer, respectively.

In our datasets, we consider a buffer width of 1.0 m, which corresponds to the width of a typical Haussmannian balcony in Paris. This buffer is appropriate to quantify true positives without overestimating false positives, as shown in Figure 19. This buffer-based evaluation is commonly used in other works reported in the literature [START_REF] Serna | Urban accessibility diagnosis from mobile laser scanning data[END_REF][START_REF] Vosselman | Detection of curbstones in airborne laser scanning data[END_REF][START_REF] Zhou | Mapping curbstones in airborne and mobile laser scanning data[END_REF].

The classic Precision (P), Recall (R) and f mean criteria are computed. Recall is defined as the number of GT pixels correctly segmented divided by the total number of GT pixels; Precision is defined as the number of true positive pixels divided by total number of segmented pixels (true positives + false positives); and F mean = 2P R/(P + R).

Table 2 presents a quantitative comparison between our façade segmentation methods. As aforementioned, these results should be carefully interpreted since the evaluation is only carried out on the 2D space at the ground level. Then, the performance segmenting inclined façades, façades with architectural details and balconies cannot be directly quantified. Method 1, based on reconstruction by dilation from markers, presents the highest Recall retrieving 100% of façades in the four test sites. However, this method presents also the highest number of false positives (Precision ranges between 13.6% and 45.1% for all test sites). As aforementioned, this method is based on iterative geodesic dilation, then any object touching the façade is segmented as part of it. This method is the fastest one and its use may be justified in an application with strict time constraints or if only a rough segmentation is required. For example, if we are only interested in defining the public space boundary (e.g. for a urban mobility application), all objects touching or behind the façade are not required to be segmented.

As explained earlier, the main problem of this method is that connected objects, such as motorcycles parked next to the façade or leaning pedestrians, are reconstructed in the façade mask. In order to solve this problem, we have proposed Method 2, based on attribute controlled reconstruction from markers. Since connected objects usually reduce the global façade elongation, this method offers better results than the first one: Recall is higher than 97% for all test sites while Precision increases up to 73.2% and 87.8% in sites I and II, respectively, sites for which all façades have been annotated. This method presents the best trade-off between performance and processing time.

In general, methods based on façade markers are strongly influenced by markers extraction. The main drawback is that bad located markers may produce errors reconstructing non-façade objects. Particularly in site IV, marker-based methods fail segmenting the tree alignments (Precision is 13.6% and 13.9% for methods 1 and 2, respectively). Method 3 does not require markers and leads to a more robust Our evaluation consists in one of those point clouds. For this experiment, file "Cassette_idclass.ply" has been used 4 . It contains 12 million points from a street section approximately 200 m long in rue Cassette in Paris, France. Manual annotations and point-wise evaluations have been independently carried out by the IGN. Results of this benchmark have been previously published in [START_REF] Vallet | TerraMobilita/iQmulus Urban Point Cloud Analysis Benchmark[END_REF].

Figure 24 presents the façade segmentation result projected onto the 3D point cloud. In this experiment, only our method based on the maximal elongation image has been applied. As a general remark, errors of our segmentation method are due to an incomplete detected façade (zone A) and a tree alignment connected to a low wall (zone B).

As cited previously, our results are evaluated point-by-point using the TerraMobilita/iQmulus evaluation protocol [START_REF] Brédif | TerraMobilita/iQmulus urban point cloud classification benchmark[END_REF]. First, we classify the 3D point cloud in two main categories: surface (containing façades and ground) and other. Moreover, the unclassified category has been defined for non-annotated points in the GT, which are ambiguous points difficult to annotate. They correspond to [START_REF] Serna | Urban accessibility diagnosis from mobile laser scanning data[END_REF] The manual annotated 3D point cloud is available at: http://data.ign.fr/benchmarks/UrbanAnalysis/download/Cassette_idclass.zip The 3D point cloud processed by our method is available at: https://partage.mines-telecom.fr/public.php?service=files&t=294aed38d48c8ddd03a528069f1b2e51 In this paper, we have proposed automatic and robust approaches to segment façades from 3D point clouds. Processing is carried out using elevation images and 3D decomposition, and the final result can be reprojected onto the 3D point cloud for visualization or evaluation purposes.

Our methods are based on geometrical and geodesic constraints. Parameters are related to urban and architectural constraints. Thus, they are intuitive to tune. The performance of our methods have been proved in our experiments on TerraMobilita databases using 2D and 3D ground truth annotations. Three approaches have been proposed: i) reconstruction by dilation from markers; ii) attribute controlled reconstruction from markers and; iii) maximal elongation image from 3D decomposition (without markers). The method based on reconstruction by dilation from markers is the fastest one since it is based on simple thresholds and use reconstructions constrained by the ground residue in order to get the entire façade. The main problem is that objects connected to the façade are reconstructed as well. In order to solve this problem, we have proposed an attribute controlled reconstruction using the geodesic elongation. Since connected objects usually appear at low heights and reduce the global façade elongation, this method offers better results than the first one. In our experiments, we have used geometric and geodesic constraints in order to extract façade markers. In the case of low façades or when the laser sensor is oriented to the ground, additional markers have been proposed. In general, methods based on façade markers are strongly influenced by the markers extraction method. The main drawback is that bad located markers produce errors since they may reconstruct non-façade objects. For this reason, we have proposed a more robust method avoiding the use of façade markers. In such method, both the elongation and its evolution over the height decomposition of the scene are analyzed. This method is based on the maximal elongation image computed from 3D decomposition. It has been proved to produce the best results.

Since the three proposed methods are based on geometric and geodesic constraints, they can be set up to manage façades of any length, height and elongation. However, these methods offer different results and level of detail. In that sense, the selection of the best segmentation method should be a trade off between quality of the results and computational cost. This choice remains application dependent: On the one hand, for applications with strict time constraints where only rough results are required, the user should prefer the first method based on façade markers and morphological reconstruction by dilation. However, in the presence of objects touching the façades, such as low bushes or parked motorcycles, the user should prefer the second method based on attribute controlled reconstruction. On the other hand, for mapping applications, where the quality of results is of the utmost importance while keeping a reasonable computation time able to address large-scale applications, the third method based on the elongation image should be preferred. This method is the most accurate and appropriate to manage high objects, such as trees, connected to the façade.

Our approach is a research prototype, mainly based on Morph-M library [START_REF] Morph-M | Image processing software specialized in Mathematical Morphology[END_REF], the image processing library of our laboratory. This library allows fast prototyping but it is not intended to be a fast library. Optimization of our base operators (erosion, dilation, opening, reconstruction, watershed, and so on), currently under development at CMM, aims at providing optimized operators for real time and/or big image developments. Software (hierarchical queues, structuring elements decomposition, among others) and hardware (SIMD-Single Instruction Multiple Data and parallelization) optimizations are available in SMIL library [START_REF] Faessel | SMIL: Simple Morphological Image Library[END_REF] and will be integrated in our future developments.

Figure 1 .

 1 Figure 1. 3D point clouds from two test sites in rue d'Assas in Paris, France. Stereopolis II, IGN c . Note that façades constitute the highest and longest vertical entities in the urban scene.

  (a) Rue d'Assas: point cloud (b) Rue d'Assas: elevation image

Figure 2 .

 2 Figure 2. 3D point clouds and elevation images for a test site in Paris, France. Data acquired by Stereopolis II, IGN c France.

  ) and 3(b) show maximal f max and minimal f min elevation images, respectively. While Figure3(c) presents the height image.

  (a) Maximal elevation image f max (b) Minimal elevation image f min (c) Height image f height = f max -f min

Figure 3 .

 3 Figure 3. Elevation images from a test site in rue d'Assas in Paris, France. Stereopolis II, IGN c .

Figure 4 .

 4 Figure 4. Façade marker extraction. Markers are represented with white pixels: (a) Points higher than h min ; (b) Points higher than h min and longer than L min ; (c) Façade markers F mark : points higher than h min , longer than L min and less circular than C min . Test site in rue d'Assas (Paris).

Figure 5 .

 5 Figure 5. Example of 3D point clouds when laser is oriented to the ground. 3D point clouds are colored by the Z coordinate. Test sites in rue Vaugirard in Paris, France. Stereopolis II, IGN c .

  Figure 7(b) presents the façade markers reprojected onto the 3D point cloud. The test site corresponds to a street section in rue Vaugirard in Paris, France.

Figure 6 .

 6 Figure 6. Mobile laser scanning (MLS) acquisition cycle. The first and the last point are taken as façade markers. Test site in rue Soufflot in Paris, France. LARA-3D, CAOR-MINES ParisTech c .

  (a) 3D point cloud colored by the Z coordinate. (b) Façade markers (red), other (gray).

Figure 7 .

 7 Figure 7. Façade markers reprojected onto the 3D point cloud. During this acquisition, the laser sensor was oriented to the ground. Note that markers only represent partial façades, therefore a façade reconstruction process is required, as explained in Subsection 4.2. Test site in rue Vaugirard in Paris, France. Stereopolis II, IGN c .

  (a) Max. elevation image f max . (b) Height image f height . (c) Façade markers F mark . (d) Ground segmentation G. (e) Ground residue G c = f max -G. (f) Façade segmentation using reconstruction by dilation: R δ G c (F mark ).

Figure 8 .

 8 Figure 8. Façade segmentation using reconstruction by dilation on the ground residue image from façade markers. Test site in rue d'Assas in Paris, France. Stereopolis II, IGN c .

  (a) Façade markers F mark . (b) Reconstruction by dilation R δ G c (F mark ).(c) Attribute controlled reconstruction A λ M (F mark ).

Figure 9 .

 9 Figure 9. Comparison of façade segmentation methods using reconstruction by dilation and attribute controlled reconstruction on the ground residue image. Test site in rue d'Assas in Paris, France. Stereopolis II, IGN c .

  (a) Point cloud colored by the laser intensity. (b) Segmentation result: façade (blue), other (gray). Façade has been segmented using reconstruction by dilation on the ground residue image from façade markers. (c) Point cloud colored by the laser intensity. (d) Segmentation result: façade (blue), other (gray). Façade segmentation using attribute controlled reconstruction on the ground residue image.

Figure 10 .

 10 Figure 10. Façade segmentation result reprojected onto the 3D point cloud. Images correspond to two different views of the same test site in rue d'Assas in Paris, France. Stereopolis II, IGN c .

  Façade markers. Several incorrect markers have been detected due to tree alignments.(c) Façade segmentation using attribute controlled reconstruction.

Figure 11 .

 11 Figure 11. Errors in façade segmentation due to tree alignments wrongly extracted as façade markers. Test site in St. Sulpice square in Paris, France. Stereopolis II, IGN c .

Figure 12 .Definition 6 .

 126 Figure 12. (a) 1D threshold decomposition; (b) component tree; (c) attribute profile.

Figure 13 .

 13 Figure 13. Adaptive voxelization using slices parallel to the ground. This example contains five objects: 1 façade, 2 bird, 3 lamppost, 4 pedestrian, and 5 tree.

  (a) Elevation image. (b) Maximal elongation image computed from the 3D point cloud. (c) Façade segmentation using the maximal elongation image.

Figure 14 .

 14 Figure 14. Façade segmentation using the maximal elongation image (without markers). Test site in rue Cassette in Paris, France. Stereopolis II, IGN c .

  (a) Elevation image. (b) Maximal elongation image computed from the 3D point cloud. (c) Façade segmentation using the maximal elongation image. Two segmentation errors have been found in zones A and B. (d) Façade segmentation error due to vegetation and bushes over a low wall. This is an unusual case presented in zone B in Figure 15(c).

Figure 15 .

 15 Figure 15. Façade segmentation using the maximal elongation image (without markers). Test site in rue Bonaparte in Paris, France. Stereopolis II, IGN c .

  (a) Elevation image. (b) Binary image containing the façade segmentation result. (c) Closing of size S min to reconnect near façades. (d) Medial road axes (used if available). (e) Distance function from façades (blue). Both empty pixels and medial road axes are constrained to have the maximal distance. (f) Influence zones. Each color represents a different city block.

Figure 16 .

 16 Figure 16. City block segmentation using the influence zones of the façade. Test site in rue d'Assas in Paris, France. Stereopolis II, IGN c .

  (a) Point cloud colored by the Z coordinate. (b) Point cloud colored by the laser intensity. (c) Façade segmentation using the elongation image (method without markers). Façade (blue) and other (gray).(d) City block segmentation. Each color represents a different city block.

Figure 17 .

 17 Figure 17. City block segmentation using the influence zones of the façade. Reprojection onto the 3D point cloud. Test site in rue d'Assas in Paris, France. Stereopolis II, IGN c .

  (b) City block segmentation. Each color represents a different city block.

Figure 18 .

 18 Figure 18. City block segmentation using the façades influence zones. Reprojection onto the 3D point cloud. Test site in rue Bonaparte and St. Sulpice square in Paris, France. Stereopolis II, IGN c .

Figures 20 to 23

 23 present elevation images, GT annotations and segmentation results on our four test sites. It is noteworthy that several ground truth annotations are missing. For example, in site III (Figure22(b)) several façades in the street left side are missing, while in site IV (Figure23(b)) façades behind trees in the street right side have not been annotated. Therefore, several correct segmentations have been incorrectly labeled as false positives. As a result, the performance of our methods is under-estimated in these two test sites. Let us analyze results of each method in detail.

Figure 19 .

 19 Figure 19. Ground truth lines and 3D façade points projected onto the 2D plane. GT lines (red) and segmented façades (blue). Test site in rue d'Assas in Paris, France. Stereopolis II, IGN c .

  Façade segmentation using attribute controlled reconstruction. (e) Façade segmentation using the maximal elongation image.

Figure 20 .

 20 Figure 20. Façade segmentation results for site I (TerMob2_LAMB93_0020.ply).

Figure 23 .

 23 Figure 23. Façade segmentation results for site IV (Z2.ply).

Figure 24 .

 24 Figure 24.Façade segmentation result using the maximal elongation image on "Cassette_idclass.ply' file. Ground (gray), façades (blue). Input file taken from TerraMobilita/iQmulus database. Stereopolis II, IGN c . Errors are due to an incomplete detected façade (zone A) and a tree alignment connected to a low wall (zone B). Zone C corresponds to non-annotated points.

  (a) Point cloud colored by the laser intensity. (b) Segmentation result projected onto the 3D point cloud. Façade (blue), sidewalk (green), road (gray), curbs (red), pole-like objects (magenta), other (pink).

Figure 25 .

 25 Figure 25. Minor errors in the façade-ground junction (between blue and green colors). Acquisition by IGN c France.

Table 1 .

 1 Table 1 describes the datasets used in this evaluation. Datasets used for evaluation of our façade segmentation methods. All datasets have been acquired in January 2013 by Stereopolis II system in the 6 th Parisian district, France.

		Filename	Description
	site I	TerMob2_LAMB93_0020.ply	rue d'Assas, approx. 90 m. Short street section with
			straight façades. See Figure 20
	site II	TerMob2_LAMB93_0021.ply	rue d'Assas, approx. 80 m. Short street section with
			two intersections and two big trees. See Figure 21
	site III Cassette_idclass.ply	rue Cassette, approx. 200 m. Long street with
			mainly straight façades and a small tree alignment.
			See Figure 22
	site IV Z2.ply	rue Bonaparte and St. Sulpice square, approx. 400
			m. Long street section with non straight façades and
			several tree alignments. See Figure

http://cmm.ensmp.fr/TerraMobilita/

http://opendata.paris.fr/

http://data.ign.fr/benchmarks/UrbanAnalysis/

Acknowledgments

The work reported in this paper has been performed as part of Cap Digital Business Cluster TerraMobilita project.

We would want to thank Dr. Bruno Vallet and his colleagues from MATIS Laboratory at IGN for their help evaluating our methods on TerraMobilita/iQmulus database.

segmentation based on the maximal elongation image. This method produces the best results for all test sites: f mean equal to 80.9% and 92.8% for sites I and II. In spite of missing GT annotations, f mean is equal to 80.3% and 74.9% for sites III and IV, proving the performance of this method even in the presence of trees. The main drawback is that its implementation is slower, then it is not suitable for real-time applications. However, time computing is reasonable for large scale applications, where time constraints are less strict. Note that processing time is only a few tens of seconds for an acquisition of several hundreds of meters, using a non-optimized implementation.

Results: TerraMobilita/iQmulus database

TerraMobilita/iQmulus database [START_REF] Brédif | TerraMobilita/iQmulus urban point cloud classification benchmark[END_REF] has been created with the aim of benchmarking semantic analysis methods working on 3D dense urban data. This database has been created in the framework of TerraMobilita project. It consists in 11 annotated 3D point clouds acquired by Stereopolis II system in the 6 th Parisian district in January 2013. Annotation has been carried out in a manually assisted way by MATIS laboratory at IGN. 18.31 % of total number of points in the dataset. For example, consider the tree and the wall in zone C in Figure 24. These points have been manually marked as unclassified, then they have not been taken into account in the evaluation.

Table 3 presents the confusion matrix and our classification results for these two categories. Results are presented as percentages with respect to the total number of points in the 3D point cloud (12 million points). Segmentation has been carried out using the method without markers (Section 5). This classification is useful to evaluate the ability of our method segmenting surfaces (façades and ground) while separating other objects connected to them. Using our method, f mean for the surface class is equal to 96.03% while other are correctly separated from them with f mean equal to 71.08 %. In this experiment, we are mainly interested in separating façades and ground from other structures such as connected objects. Note that the surface class includes façades and ground, which represent the biggest categories in the scene with 75.81 % of total 3D points, while the other class represents 5.88 % of total 3D points. The overall accuracy of our method considering these categories is 92.73 %.

Table 4 presents our segmentation results for the surface class (façades and ground). In the confusion matrix, results are presented as percentages with respect to the total number of points in the 3D point cloud (12 million points). Note that our method correctly separates façades and ground giving F mean equal to 97.25 % and 98.72 %, respectively. Figure 25 shows that small errors are due to the façade-ground junction, where some points may be wrongly assigned. The overall accuracy in this case is 98.26 %. These results prove the performance of our method.

Conclusions Author Contributions

Andrés Serna is the leading author of this work. He performed the research, developed the software prototype and wrote the paper together with Beatriz Marcotegui. The paper was further revised by Jorge Hernández who gave substantial contributions to the design and analysis of this work

Conflicts of Interest

The authors declare no conflict of interest.