Andrés Serna

Beatriz Marcotegui
email: beatriz.marcotegui@mines-paristech.fr

Urban accessibility diagnosis from mobile laser scanning data

Keywords: Accessibility, soft-mobility, mathematical morphology, curbs, urban modeling, mobile laser scanning

In this paper we present an approach for automatic analysis of urban accessibility using 3D point clouds. Our approach is based on range images and it consists in two main steps: urban objects segmentation and curbs detection. Both of them are required for accessibility diagnosis and itinerary planning.

Our method automatically segments facades and urban objects using two hypothesis: facades are the highest vertical structures in the scene and objects are bumps on the ground on the range image. The segmentation result is used to build an urban obstacle map. After that, the gradient is computed on the ground range image. Curb candidates are selected using height and geodesic features. Then, nearby curbs are reconnected using Bézier curves. Finally, accessibility is defined based on geometrical features and accessibility standards.

Our methodology is tested on two MLS databases from Paris (France) and Enschede (The Netherlands). Our experiments show that our method has good detection rates, is fast and presents few false alarms. Our method overcomes other works reported in the literature on the same databases.

Introduction

Digital 3D city models are useful for many applications: urban planning, emergency response simulation, cultural heritage documentation, virtual tourism, itinerary planning, accessibility analysis for different types of mobility, among others. Thanks to new 3D data availability, an increasing number of geographic applications such as Google Earth, Microsoft Virtual Earth, Open Street Maps and Geoportail are flourishing nowadays. Most of these applications are recently enhanced with pedestrian navigation options. Some of these applications do not only require to look realistic, but also have to be faithful to reality. Thus, semantic analysis from real data (images, 3D point clouds, GPS measurements, etc.) are performed in order to give faithfulness to 3D city models. This analysis is usually made by manual assisted approaches, leading to time consuming procedures, unsuitable for large scale process. In that sense, automatic methods for semantic analysis of urban structures are required.

In general, large cities are built based on demographical and geographical constraints, architectural preferences and governmental budgets. Many places are not accessible for wheelchairs, skaters, segways, baby buggies, among others. Taking a short trip through the street can reveal an environment plagued with physical barriers, where wheelchair users bear the brunt.

About 80 million people living in European Union (EU) have a mild to severe disability. Physical obstacles make them vulnerable to social exclusion, low employment and limited education level. In fact, mean poverty rate for those with disabilities is 70% higher than the average. In 2007, EU signed the United Nations convention on the rights of persons with disabilities (UN, 2007). The aim is allowing people with disabilities to go on their daily lives like everyone else and enjoy their rights as EU citizens. One of the strategies consists in ensuring physical access to buildings, roads, transportation, schools, housing, medical centers and workplaces.

In France according to Law 2005-102 1 , local authorities are required to make accessibility diagnoses and to take corrective actions in public spaces. An available manual-assisted solution is Wheelmap 2 . It is an on-line service, based on Open Street Maps, aiming to tag wheelchair-accessible places. It is a crowd-sourcing project where everyone can collaborate by tagging public places according to accessibility for wheelchair users. Other solutions could include automatic 3D urban modeling techniques [START_REF] Golovinskiy | Shape-based recognition of 3D point clouds in urban environments[END_REF]Hernández and Marcotegui, 2009b;[START_REF] Pu | Recognizing basic structures from mobile laser scanning data for road inventory studies[END_REF][START_REF] Douillard | On the segmentation of 3D LIDAR point clouds[END_REF][START_REF] Rutzinger | Tree modelling from mobile laser scanning data-sets[END_REF]. However, automatic accessibility analysis is still an open problem.

In general, urban accessibility information can be integrated into navigation services as on-line maps, support systems using cell phones [START_REF] Rashid | Users Helping Users: User Generated Content to Assist Wheelchair Users in an Urban Environment[END_REF], collaborative social networks [START_REF] Menkens | EasyWheel -A Mobile Social Navigation and Support System for Wheelchair Users[END_REF], or even in automated wheelchairs and segways [START_REF] García | Proposal for an Ambient Assisted Wheelchair (A2W)[END_REF]. Including accessibility parameters in city maps, one can define adaptive itineraries according to detailed and accurate information about barriers and obstacles in the public infrastructure.

Our work is part of Cap Digital Business Cluster TerraMobilita project: "3D mapping of roads and urban public space, accessibility and soft-mobility". This project responds precisely to requests about 3D urban maps and softmobility applications. Contribution is twofold: i) To develop new methods and tools in order to create and update urban maps using laser scanning and digital imagery. ii) To develop innovative applications for soft-mobility itinerary planning.

The focus of this work is automatic obstacle map creation and analysis of curbs accessibility from Mobile Laser Scanning (MLS) data. Our method begins filtering facades and urban objects not only to center our attention on ground information, but also to build 3D obstacle maps useful for itinerary planing. Then, automatic methods for detection, reconnection and characterization of curbs are developed. For our experiments, MLS data are acquired by Stereopolis II [START_REF] Paparoditis | Stereopolis II: A multi-purpose and multisensor 3D mobile mapping system for street visualisation and 3D metrology[END_REF] and LARA-3D2 [START_REF] Goulette | An Integrated on-Board Laser Range Sensing System for On-the-Way City and Road Modelling[END_REF], two MLS systems from IGN France and MINES ParisTech, respectively. Additionally, a public database from Enschede (The Netherlands) is used to get quantitative results and to compare with the state of the art.

The paper is organized as follows. Section 2 reviews some related works in the state of the art and establishes their differences with respect to our work. Section 3 describes our method using range images, explains the accessibility analysis and presents an illustrative itinerary planning application. Section 4 presents comparative results with other database available in the literature. Finally, Section 5 is devoted to conclude this work. [START_REF] Ayres | Sidewalk potential trip points: A method for characterizing walkways[END_REF] present a method to characterize sidewalks based on ground elevation profiles. The aim is identifying unusual elevation changes and obstacles. The authors highlight the impact of elevation changes on pedestrians and soft-mobility users safety. They work with very precise data from streets in California. Unfortunately, this is not suitable for large scale applications since data are acquired manually. Hernández and Marcotegui (2009a) use range images from 3D point clouds in order to extract quasi-flat zones on the ground and use them as markers for a constrained watershed [START_REF] Beucher | The morphological approach to segmentation: the watershed transformation[END_REF]. Then, a region adjacency graph is used to determine the border between road and sidewalk. This procedure fails in presence of access ramps because quasi-flat zones merge road and sidewalk and it is no longer possible to detect curbs. [START_REF] Vosselman | Detection of curbstones in airborne laser scanning data[END_REF] use airborne laser scanning data to detect curbstones. First, small height jumps at ground level are detected. Second, they fit a smooth curve to generate the separation between sidewalk and road. Finally, small gaps between nearby and collinear segments are closed. In unoccluded regions, this approach is robust to traffic signs, cars and multi-line roads. Good results are presented with respect to ground truth measurements. However, airborne laser resolution (20 points/m 2 ) is not precise enough to detect access ramps and low curbs. In fact, only curbstones of at least 10cm height can be clearly detected. More recently, the same authors [START_REF] Zhou | Mapping curbstones in airborne and mobile laser scanning data[END_REF] extended their methodology to denser (1000 points/m 2 ) MLS datasets. They improve the planimetric accuracy of curbstone locations fitting a sigmoidal function to detected points, in a similar way to [START_REF] Siegemund | Curb Reconstruction using Conditional Random Fields[END_REF]. In these methods, although detection is performed directly on the 3D point cloud, it is made on a strip by strip basis, so intrinsic information between neighboring strips is missing. [START_REF] Valero | Advanced directional mathematical morphology for the detection of the road network in very high resolution remote sensing images[END_REF] present an automatic road extraction methodology for high resolution imagery. This procedure can be extrapolated to curb detection since both problems have similar assumptions: they are thin and elongated paths, but not necessary straight, and present color differences with respect to their neighborhood. Their experimental results show accurate road extractions in terms of completeness and correctness. Some post processing has to be proposed in order to reconnect isolated segments due to occlusions and shadows. [START_REF] Gang | Procedural Modeling of Urban Road Network[END_REF] propose an approach to model urban road networks based on manual markers. They use an interactive interface to mark sidewalks and roads on aerial images. Then, Bézier curves and polygons are used to model the road. This method is realistic and very fast to render, however manual marking is a time-consuming task. Automatic detections and/or road network databases are needed for large scale modeling.

Related work

With respect to other works reviewed in the state of the art, we aim at developing a method of urban accessibility diagnosis suitable for large scale applications. Our method is automatic using few constraints on MLS data, creates an obstacle map segmenting objects on ground, defines the accessibility for each curb point, and can manage reconnection problems due to access ramps. A detailed description is presented below.

Methodology

Figure 1 shows our proposed methodology. First, input point cloud is mapped to range images. Second, the image is interpolated in order to avoid connectivity problems and the quasi-flat zones algorithm is used to segment the ground (road+sidewalk). Third, facades and objects are extracted using morphological transformations and the obstacle map is defined. Then, curb candidates are selected using height and elongation criteria, and close curbs are reconnected using Bézier curves. Curbs accessibility is defined according to international standards. Finally, the obstacle map is used to define adaptive itineraries taking into account the path width such that a wheelchair can pass.

Projection to range images

Our method projects 3D point clouds to range images because they are convenient structures to visualize and 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]. An image can be processed quickly, implicitly defines neighborhood relationships and requires little memory.

A range image is a 2.5D structure that contains height information at each pixel. Range images are generated projecting 3D points to a XYplane using a virtual camera located on the horizontal plane with normal vector -→ n = (0, 0, 1), and crossing the lowest point in the Z-coordinate axis (0, 0, z min ). In general, several points are projected on the same pixel. Thus, we define two images:

• Maximal range image (or simply range image): stores the maximal depth among all projected points on the same pixel.

• Minimal range image: stores the minimal depth among all projected points on the same pixel.

These range images are used to segment facades, objects and curbs. When this process is completed, images are reprojected to the 3D point cloud in order to get the final result.

Spatial pixel size is the only projection parameter and it has to be carefully chosen. On one hand, if the pixel size is too large, fine details are not preserved because too many points would be projected on the same pixel. On the other hand, too small pixel size implies connectivity problems and larger image sizes, which would no longer justify the use of range images. To avoid connectivity problems and loss of information, spatial pixel size is chosen according to point cloud resolution. In our experiments, a pixel corresponds to a square of 10 cm side (0.01 m 2 area). Figure 2 describes the process using range images. A detailed explanation is presented in the following subsections.

Image interpolation

On range images, an interpolation is required in order to fill holes caused by occlusions and missing scan lines. A morphological interpolation based on filling holes is preferred since this transformation does not create new regional maxima, it can fill holes of any size and no parameters are required. This is important in order to avoid false alarms in the object detection approach (explained in Section 3.5).

In the most simple sense, a hole is a dark region which is not connected to the image border and is surrounded by brighter pixels. The fill-holes transformation is implemented as the reconstruction by erosion of the image f from the marker f marker , as shown in Figure 3. The marker f marker is set to the maximum image value except along the image border where the original image value is kept. Figure 3(b) illustrates this definition on 1D. Note that a minimum in the left part of the signal is not a hole because it touches the border. In order to preserve original data, only pixels with no data are modified, while other pixels keep their original value. For further details on grayscale reconstruction operators, the reader must refer to [START_REF] Soille | Automated basin delineation from digital elevation models using mathematical morphology[END_REF][START_REF] Vincent | Morphological grayscale reconstruction in image analysis: applications and efficient algorithms[END_REF] (a) Input function f and marker f marker In the middle of the place, sparse points are obtained as the result of occlusions and faraway objects. This image has to be interpolated before processing. Note that almost all dark regions are touching the image border, so they would not be filled by a classical fill-holes transformation. To solve this problem, each isolated region is connected to its closest neighbor by the shortest path. This artificially defines the boundaries of Figure 4(c). Then, the fill-holes transformation is applied in order to interpolate the image (Figure 4(d)). Note that our methodology performs well on near objects. However, several false artifacts can appear when interpolating far objects because there are not enough points. This can be easily corrected in the segmentation step eliminating objects for which the number of interpolated points (N interp ) is much higher than the number of real points (N real ). That leads us to define a confidence index C = N real /(N real + N interp ) for each segmented object. The distance of an object to the acquisition system could also be considered.

(b) F ill(f ) = f = R ϵ f (f marker )

Ground segmentation

Ground segmentation is a critical step for access diagnosis since curbs and obstacles are located on it. With the aim of segmenting the ground, we use the λ-flat zones labeling algorithm, firstly introduced in image processing by [START_REF] Nagao | Region extraction and shape analysis in aerial photographs[END_REF], defined by [START_REF] Meyer | From connected operators to levelings[END_REF] as: Definition 1. Two neighboring pixels p, q belong to the same quasi-flat zone of a function f , if their difference |f p -f q | is smaller than or equal to a given λ value.

∀ (p, q) neighbors :

|f p -f q | ≤ λ (1)
With this definition, we want to obtain the ground as the largest λ-flat zone on the range image. We set λ = 20cm because it is usually high enough to merge road and sidewalk (even if there are no access ramps) without merging objects. Note that this approach is strongly inspired by the work of Hernández and Marcotegui (2009a). In the context of that work, their procedure fails in presence of access ramps because road and sidewalk are merged. However, in our work, we take advantage of this to extract the complete ground mask filtering out facades and objects.

Facade segmentation

Once the ground is extracted, all remaining structures are considered as facades and objects. Discrimination between them is important because facades delimit the end of public space, and urban objects define the obstacle map required for itinerary planning.

Due to specific requirements in our Paris database, the MLS system was oriented to the ground. Therefore, structures higher than 2.5m are out of the laser field of view. This is a challenge for methods using height constraints (Hernández and Marcotegui, 2009a), since high wall parts are not visible. To solve this problem, we propose a solution extracting facade markers. For that, we take advantage of the acquisition cycle of the MLS sensor. In our configuration, the sensor scans vertical lines starting from the top. Thus, the first point corresponds to the highest point of that cycle. Each first point is labeled as facade marker candidate. Isolated and faraway points are not considered. Then, points forming lines are taken as facade markers.

In order to reconstruct all the facade, an attribute controlled reconstruction is performed from facade markers [START_REF] Serna | Attribute controlled reconstruction and adaptive mathematical morphology[END_REF]. It consists in appending nearby points with similar height until the maximization of an attribute on the segmented region. In our case, facades are the longest and most elongated structures in the range image. Then, the maximal geodesic elongation is used.

The geodesic elongation E(X), introduced by Lantuéjoul and Maisonneuve (1984), is computed to only select thin and elongated structures. Equation 2 defines the geodesic elongation of an object X, where S(X) is the area and L(X) is the geodesic diameter [START_REF] Lantuéjoul | On the use of the geodesic metric in image analysis[END_REF]. A toy example of geodesic elongation for different binary objects is shown in Figure 5(a). The number on each object corresponds to its elongation. A fast computation of this geodesic attribute can be found in [START_REF] Morard | Geodesic attributes thinnings and thickenings[END_REF].

Using this controlled reconstruction maximizing the geodesic elongation, it is possible to reconstruct the facade without merging adjacent objects.

Object segmentation

To segment urban objects, the methodology proposed by Hernández and Marcotegui (2009a) is used. We assume urban objects appear as bumps on the ground in the range image. Then, they are extracted using the top-hat

E(X) = πL 2 (X) 4S(X)
(2) transformation by filling holes: F T H( f ) = F ill( f ) -f . First, the range image is inverted and its holes are filled. Then, the top-hat transformation consists in subtracting the original image from the filled image (see Soille, 2003, Chapter 4.5).

Figure 6 presents the segmentation of facade and objects in a 3D point cloud. Note that pedestrians touching the facade are correctly segmented. By the moment, we assume all objects static. However, classification techniques can be used in order to distinguish mobile objects such as pedestrians from static objects. Additionally, using velodyne data and color images can help to improve this process.

Curb detection

In order to detect curbs, we use the interpolated minimal range image because it contains the lowest projected point on each pixel. Next, the morphological external gradient is computed as the arithmetic difference between the dilation and the original image ρ sup = δ B (f ) -f , where B is a hexagonal structuring element of size 0.1m (1 pixel).

Regions with range changes between 3cm and 20cm are considered as curb candidates. Then, a minimum elongation E min =10 is experimentally defined in order to accept curbs. This threshold corresponds to the geodesic elongation of a curb of approximatively 1m long and 0.08m wide. We prefer geodesic measurements because, in general, curbs are not straight structures, so the Euclidean distance could sub-estimate their real length.

In Figure 7, we illustrate the effect of several E min thresholds for curbs detection. Note that E min =0 preserves all structures between 3 and 20cm height, E min =5 does not take noise away and E min =20 removes some real curbs, those that are short due to occlusions. Note that steps at building entrances are considered as curbs and its detection can be used to define building accessibility. In the case that they should not be considered, a constraint of minimal distance from the facade can be imposed.

Curb reconnection

The main drawback of the previous process is the lack of connectivity between curbs due to access ramps, occlusions, missing scan lines and acquisition problems. Some solutions can be found in the literature: [START_REF] Zhou | Mapping curbstones in airborne and mobile laser scanning data[END_REF] close gaps between adjacent and co-linear curbs using lines, [START_REF] Shih | Adaptive mathematical morphology for edge linking[END_REF] present an approach based on adaptive mathematical morphology for linking broken edges, and [START_REF] Talbot | Efficient complete and incomplete path openings and closings[END_REF] propose a sophisticated solution incorporating incomplete path openings. Unfortunately, these solutions are not suitable since reconnection through access ramps are not always straight (Figure 9(a)) and height discontinuities of access ramps are close to the noise level (Figure 9(c)).

We propose a reconnection strategy based on quadratic Bézier curves. Two curbs closer than a threshold d min are reconnected tracing a Bézier curve between their geodesic extremities. Curb orientations are used in order to define the Bézier parameters, as explained below. In our experiments, d min =5m for Paris database.

A Bézier curve is a parametric path traced by the function B(t), given points P 0 , P 1 , and P 2 , as shown in Equation 3. It departs from P 0 towards P 1 , then bends to arrive to P 2 . As a consequence, tangent lines in P 0 and P 2 both pass through P 1 . Thus, the user can control input and output angles of the curve. This is an important smooth constraint, because in our application, initial and final angles of the reconnection should not change abruptly.

B(t) = (1 -t) 2 P 0 + 2(1 -t)tP 1 + t 2 P 2 , ∀t ∈ [0, 1] (3)
Conveniently, the reconnection process can be written as the problem to find the three control points for a Bézier curve. Points P 0 and P 2 correspond to the geodesic extrema of curbs C 0 and C 2 . Thus, the problem is reduced to find P 1 . In general, there are two reconnection types:

• If the curbs to be reconnected are co-linear, P 1 is put in the middle of them. Therefore, the three control points are co-linear and the resulting reconnection is a straight line, as described in Figure 8(a).

• If the curbs to be reconnected are not co-linear, P 1 is put in the intersection of the two projection lines from C 0 and C 2 . Therefore, the resulting reconnection is a parabolic segment, as described in Figure 8(b).

Figure 9 illustrates this procedure in a real case. Note that the resulting curve is smooth and faithful to reality.

Accessibility analysis and itinerary planning

One of the aims of TerraMobilita project is planning itineraries for different types of mobility, including soft-mobility. Therefore, curb characterization is a very important task because it determines the suitability of a path. For example, sidewalks without access ramps may be appropriate for rollers but not for wheelchairs. Additionally, obstacles on sidewalk represent physical barriers to free mobility. In our work, we define the accessibility according to curbs geometry and obstacles on the street. In our opinion, the most critical case is the accessibility for wheelchair users, so our experiments are conducted in that sense. However, we can define the accessibility depend-ing on any other type of soft-mobility since our method provides geometrical information of curbs and obstacles for each ground point.

A standard wheelchair is between 60 and 69cm wide, therefore the minimum clear width of an access ramp is 91.5cm between railings (ISO, 2008;[START_REF] Ada | ADA Standards for Accessible Design[END_REF]. Thus, curb accessibility is defined taking the following criteria into consideration: i) wheelchair-accessible (green): Sidewalk access with one step maximum, wider than 1 m and not higher than 7cm. ii) wheelchair-inaccessible (red): Otherwise.

This simple traffic-light color code is strongly inspired by international standards and it is compatible with on-line maps such as Wheelmap. A direct application consists in planing adaptive itineraries for different types of mobility. For example, defining the start and final points of a journey, it is possible to suggest an adaptive itinerary according to obstacles on the ground and curb accessibility. Thus, the problem consists in finding a path that optimizes certain criteria (i.e., the shortest path). Figure 11 presents an example of an adaptive itinerary for a person using a wheelchair going from A to B. In this case, we assume a minimum passing space of 1m, which is large enough for a standard wheelchair. Note that this example is only illustrative, real applications for itinerary planing will be developed in the framework of TerraMobilita project.

Results

Our methodology was tested on our own database in order to get qualitative results. It contains approximatively 2km (∼10 million points) of MLS data from the 6 th district of Paris, France. All examples aforementioned correspond to this database. By the moment, we do not have ground truth annotations, so quantitative results are not available yet. However, our experiments demonstrate that facades are correctly segmented even when their high part is out of the laser field of view. Objects are segmented as bumps on the ground and assumed static. Our method presents correct curb detections, few false alarms and appropriate accessibility analysis. The main problem is due to occluded regions, which can be managed if the reconnection distance does not exceed 5m.

In order to get quantitative results, we use another database containing three test sites at Enschede, The Netherlands. The database contains approximatively 1km (∼12.5 million points) of MLS data with ground truth annotations. Two manual data are collected: i) roadside lines, corresponding to inaccessible curbs higher than 7cm. ii) gap lines, corresponding to access ramps lower than 7cm. We use the same evaluation strategy as [START_REF] Vosselman | Detection of curbstones in airborne laser scanning data[END_REF]2012). Quantitative analysis is performed by comparison between automatic and manual extracted lines. As the amount of false alarms near real road lines is very low in this database, a buffer around ground truth lines is taken. Automatic lines are labeled as true positives or false positives if they are located inside or outside the buffer, respectively. A buffer width of 50cm was used. Two classical statistics are computed. The completeness (or recall) is defined as the length of the extracted lines inside the buffer divided by the length of the reference lines. The correctness (or precision) is defined as the length of the extracted lines inside the buffer divided by the length of all extracted lines.

Figure 12 illustrates automatic curb detection in the three test sites. Results of completeness, correctness and processing times are given in Table 1. In order to simplify lines geometry, the well-known [START_REF] Douglas | Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[END_REF] algorithm was used with 20cm distance threshold. Our results show that our method has good detection rates, is fast and presents few false alarms. On one hand, completeness in sites 2 and 3 is better than other works reported in the literature on the same database. On the other hand, correctness is greater than 90% for all sites, which indicates that our method produces few false alarms, which are mainly due to low vegetation (Zones H and I in Figure 12(b)). First test site leads to low performances because of polygonal curbstones in the middle of the road (Zones A and B in Figure 12(a)). Since MLS data was acquired only from one side of the street, only one side of the polygons is visible. As our original goal consists in detecting curbs limiting the sidewalk in order to perform accessibility diagnostics, our method does not process polygonal curbstones in any special way, then the invisible part is not detected. The scores published by [START_REF] Zhou | Mapping curbstones in airborne and mobile laser scanning data[END_REF] take these polygons into account. Fitting polygons can be a suitable solution and it will be evaluated in our future work.

Another problem in this site is due to long access ramps that cannot be reconnected by our method. For example, zone C in Figure 12(a) shows an access ramp lower than 3cm and 45m long. Therefore, it is neither detected nor reconnected.

The presence of cars and other obstacles is the main problem in the detection procedure. In fact, several curbs are not detected due to large occluded areas. For example, zone D in Figure 12(c) shows a large occluded area due to cars on both sides of the street. Only short curb parts are detected between parked cars and they are not reconnected because the distance exceeds our reconnection threshold. For this database, reconnection threshold has been reduced to 2m due to wrong reconnections in polygonal curbs in the middle of the road. Therefore, curb reconnections longer than 2m are not allowed and it is the reason of low recall in curbs detection.

Inspecting test sites, we found several inconsistent ground truth lines since they do not correspond to real curbs. For example, Figure 13(b) shows a straight detected curb (red) on the right side, while the ground truth (cyan) marks it as an extrusion. A photo from the scene (Figure 13(a)) demonstrates that automatic detection is correct in this case. Note that this is a Google Street View photo, taken a different day, so parked cars are not the same. Other ground truth problems can be found in zones E, F and G in Figure 12(b).

Note that our method is designed to detect height jumps on the ground, not only curbstones. Therefore, stairs and steps at building entrances are detected as well (Figure 13). These structures are not errors, but they are not marked in ground truth data. Thus, they were not taken into account in the quantitative results in order to do a fair comparison. To automatically filter out these structures, a constraint of minimal distance (50 cm) from the facade was imposed. Processing was carried out on an Intel Core i7 CPU @2.93 GHz with 8 GB RAM. Note that our method takes less than 9 minutes to process the three test sites, which is quite faster than any other method running in the same database. For example, [START_REF] Vosselman | Detection of curbstones in airborne laser scanning data[END_REF] reported 1 hour for the processing time. Although our machine is faster, the conceptual difference consists in the fact that they process the 3D point cloud on a strip by strip basis, while we project all 3D points to a range image and we process them as a complete set using digital image processing techniques.

For further analysis, Table 2 presents the individual completeness results for each curb type. In general, occlusion affects all detection types. The best recall occurs for roadside lines, which are curbs higher than 7cm. Long curb reconnections are not allowed and it is the reason of low recall in curbs detection. The lowest completeness is due to polygonal curbstones. As aforementioned, we only detect one side, then an special processing should be performed for this type of curbs.

Conclusions

We propose an automatic and robust approach to segment facades, urban objects and curbs in 3D point clouds. Processing is carried out using range images and the final result is reprojected onto the 3D point cloud. Facades are used to delimit the public space, while urban objects define the obstacle map required for itinerary planning. To detect curb candidates, gradient information is used. Then, thin and elongated structures are selected using geodesic elongation. Our method is robust to noise since small, isolated and not elongated structures are removed from the range image using morphological filters. Finally, close curbs are reconnected using Bézier curves and characterization is done based on geometrical features and accessibility standards.

Our methodology was qualitatively and quantitatively tested on two MLS databases from Paris (France) and Enschede (The Netherlands). Our results show that our method has good detection rates, is fast and presents few false alarms. In fact, correctness and completeness results are higher than those for other works reported in the literature on the same databases.

Occlusions, long access ramps and polygonal curbstones are the main problems in the detection procedure. In the first case, several scans of the same zone can reduce the occlusion. Using color gradients can be a suitable solution in order to detect low and long access ramps. And, as suggested by other works in the literature, a special strategy for the occluded side of polygonal curbstones should be developed. Other problems were due to inconsistent ground truth annotations.

Our approach is still a research prototype and efforts to be optimized have not been carried out. However, our process is faster than other methods reported in the literature. In our experiments, we estimate processing speed of 5 min/km. In a city like Paris, with 1700 km of streets, only 2.4 days would be required in order to automatically analyze the accessibility of the whole city. It is reasonable for large scale applications. If the analysis would be implemented in a real time platform, for instance to guide a robot, important optimization and parallelization are possible.

In the future, we are planning to use velodyne and color sensors to distinguish static from mobile obstacles and to help to solve occlusions problems. We expect to include quantitative results from Paris database in future works.

Figure 1 :

 1 Figure 1: Workflow of our proposed accessibility analysis from MLS data

Figure 2 :

 2 Figure 2: 3D point cloud processing using range images. Segmentation results: ground (gray), curbs (red and green), facade (blue), objects (yellow). Note that some objects are detected behind facade because they have been seen through windows and doors.

Figure 3 :

 3 Figure 3: Fill-holes transformation: Morphological reconstruction by erosion of f from f marker . ⋆ indicates no-data points

Figure 4 :

 4 Figure 4: Image interpolation. Artificial boundaries are created for regions touching the border and then the fill-holes transformation is applied.

Figure 5 :

 5 Figure 5: Geodesic elongation for different binary objects.

Figure 6 :

 6 Figure 6: Segmentation of facade (blue) and objects (yellow). Note that pedestrians touching the facade are well discriminated.

Figure 7 :

 7 Figure 7: Curb detection at different thresholds on the geodesic elongation.

Figure 8 :

 8 Figure 8: Quadratic Bézier reconnection in straight and bent cases

  Figure 10 illustrates two labeled 3D point clouds.

Figure 10 :

 10 Figure 10: Labeled point clouds: Facades (blue), urban objects (yellow), ground (gray), inaccessible curb (red), accessible curb (green).

Figure 11 :

 11 Figure 11: Adaptive itinerary (black) for a person using a wheelchair going from A to B.

Figure 12 :

 12 Figure 12: Test sites at Enschede. Our detection (red) and ground truth (cyan).

Figure 13 :

 13 Figure 13: Inconsistent ground truth annotation indicated with an arrow. Ground truth (cyan) presents an extrusion that does not correspond to the real curb. Detected curbs (red) and building entrances (green). Photo taken from Google Street View.

Table 1 :

 1 Completeness, correctness and processing time for three test sites at Enschede, The Netherlands. Between brackets the results obtained by[START_REF] Zhou | Mapping curbstones in airborne and mobile laser scanning data[END_REF]

		Site 1	Site 2	Site 3
	Completeness 65% (83%) 54% (53%) 60% (54%)
	Correctness	95% (91%) 94% (92%) 91% (84%)
	Time		5.5 min (1 hour)

Table 2 :

 2 Individual completeness for each curb type.

		Site 1 Site 2 Site 3
	Roadside (Inaccessible) 82%	67%	64%
	Gaps (Accessible)	55%	48%	46%
	Polygonal curbstones	46%	45%	N/A

Loi

2005-102 du 11 février 2005: "Pour l'égalité des droits et des chances, la participation et la citoyenneté des personnes handicapées".2 http://wheelmap.org/en/

Acknowledgements

The work reported in this paper has been performed as part of Cap Digital Business Cluster TerraMobilita project. We want to thank Liang Zhou and Prof. Georges Vosselman for providing us with the Enschede database.