Sven Oesau

Florent Lafarge

Pierre Alliez

Indoor Scene Reconstruction using Feature Sensitive Primitive Extraction and Graph-cut

Keywords: Indoor scenes, 3D reconstruction, laser scanning, multi-scale line extraction, graph cut, energy minimization

We present a method for automatic reconstruction of permanent structures, such as walls, floors and ceilings, given a raw point cloud of an indoor scene. The main idea behind our approach is a graph-cut formulation to solve an inside/outside labeling of a space partitioning. We first partition the space in order to align the reconstructed models with permanent structures. The horizontal structures are located through analysis of the vertical point distribution, while vertical wall structures are detected through feature preserving multi-scale line fitting, followed by clustering in a Hough transform space. The final surface is extracted through a graph-cut formulation that trades faithfulness to measurement data for geometric complexity. A series of experiments show watertight surface meshes reconstructed from point clouds measured on multi-level buildings.

Introduction

In recent years the reconstruction of 3D architectural scenes has received more and more attention. Blueprints and precise models are often needed for the architecture, engineering and construction application domains. As the physical geometry of buildings often differs from the original plans, the reconstruction of a precise 3D model of the interior is a common need. Such reconstruction is often a manual or semi-automatic time-consuming process. Compared to the reconstruction of outdoor environments, indoor scene reconstruction is still in an early stage. Applying outdoor reconstruction methods to indoor scenes is not practical as indoor impose different challenges than outdoor scenes. The outside of a building can often be described by a single or few cuboids, and the amount of clutter hiding part of the geometry is rather low. In contrast, interior space often has a more complex geometry and a high quantity of clutter. Further hurdles come from the varying point density and anisotropic sampling.

Related work

Surface reconstruction has been an active research topic for decades. Despite the wide variety of methods, they often perform unsatisfactorily for extracting a surface representation from indoor scenes. They commonly result in a single surface representation approximating the entire point cloud, which is unsatisfactory for further specialized processing such as semantic labeling into floors, ceilings and walls. A favored approach would provide a classification of the point cloud into permanent structures and clutter. General surface reconstruction methods instead assume that the point cloud is created from a single surface whereas indoor scenes are usually composed of planar parts and arbitrarily shaped clutter.

The RANSAC-based algorithm proposed by [START_REF] Schnabel | Efficient RANSAC for point-cloud shape detection[END_REF] provides a valid solution for extracting several types of shapes from an oriented point cloud, i.e., from points with oriented normals. While missing normals can be estimated by robust feature preserving methods [START_REF] Boulc'h | Fast and robust normal estimation for point clouds with sharp features[END_REF], adjusting the parameters of Schnabel's algorithm to detect primitives in indoor scenes is often a trial-and-error process. Another drawback for indoor scene reconstruction is that Schnabel's algorithm is not robust to highly variable point density and strong anisotropy. For the reconstruction of permanent structures from indoor scans, we advocate for considering a domain-specific knowledge. Common knowledge assumptions are piecewise planar permanent structures and Manhattan-World scenes, i.e., exactly three orthogonal directions: two for the walls and one for floors and ceilings. We classify the existing approaches into three categories: Planar primitive detection, Volumetric primitive fitting and Mesh-based reconstruction.

Planar primitive detection. [START_REF] Sanchez | Planar 3D modeling of building interiors from point cloud data[END_REF] recently proposed a method for modeling building interiors as an arrangement of planar polygons. They classify the points based on estimated normals by assuming a Manhattan-World scene. The planar primitives are reconstructed by a region growing segmentation, least-squares fitting by employing RANSAC and alpha shapes [START_REF] Edelsbrunner | On the shape of a set of points in the plane[END_REF] to reconstruct polygons. Additionally, they employ model fitting of a staircase model to unsegmented points. The results presented in form of a polygon soup show that they can deal with multi-level buildings. There is however no structure information such as adjacency of primitives. Another primitive detection approach has been proposed by [START_REF] Budroni | Automated 3D reconstruction of interiors from point clouds[END_REF]; Budroni and Boehm. The authors apply sweeping techniques to identify Manhattan-World directions and to locate wall segments. The floor plane is decomposed by the so-detected segments and marked as inside or outside based on the point density. The output is a watertight model extracted from the ground plan. However, resilience to missing data is not addressed. Another approach proposed by [START_REF] Okorn | Toward automated modeling of floor plans[END_REF] uses the Hough transform to extract wall segments from the point cloud. Although the majority of walls are detected, they are often not captured in their full extent. The output of the algorithm is a set of unconnected wall segments that are used to classify the points into permanent structures and clutter. However, neither structural relations nor volumes of the indoor space are provided. [START_REF] Adan | 3D reconstruction of interior wall surfaces under occlusion and clutter[END_REF] build on top of this approach and focus on the modeling of wall surfaces. A learning mechanism is proposed for segmenting and labeling wall surfaces into parts either occluded by clutter, or occupied (solid), or empty (e.g. windows).

Volumetric primitive fitting. [START_REF] Xiao | Reconstructing the world's museums[END_REF] introduce a constructive solid geometry (CSG) based method to reconstruct large-scale indoor environments for visualization purposes. The authors propose a greedy algorithm for creating a CSG model, guided by an objective function devised to both measure quality and control detail. In order to reconstruct different floor and ceiling heights they first decompose the point cloud into horizontal slices and apply their method first in 2D, then in 3D to merge the 2D models. Although this approach can deal with more than two wall directions, it performs well on scenes mostly consisting of orthogonal or parallel structures. This limitation is mostly due to the primitive generation for the CSG model extraction: They detect linear wall segments and combine parallel or orthogonal ones for generating can-didate primitives to be used by the CSG model. [START_REF] Jenke | Statistical reconstruction of indoor scenes[END_REF] proposed a greedy algorithm reconstructing the free space volume. This approach is based on Schnabel's algorithm to detect planar primitives. The primitives are first structured in a graph, and a graph matching is applied to locate the cuboid candidates for the greedy reconstruction. Due to the fitting of cuboids their approach is limited to rectangular geometry. In presence of clutter or missing data the graph matching may fail as it requires at least five planar primitives to fit a cuboid.

Mesh-based reconstruction. [START_REF] Newcombe | Kinectfusion: Real-time dense surface mapping and tracking[END_REF] and [START_REF] Izadi | Kinect-fusion: Real-time 3D reconstruction and interaction using a moving depth camera[END_REF] propose a surface reconstruction method from point clouds acquired by a low cost consumer-grade hand held scanner. By designing their approach for parallel execution on GPUs they achieve real-time performance. Reconstructing an indoor scene using a general surface reconstruction method and presenting the result as a surface mesh allows for a general and detailed representation. However, no semantic classification of the scene into wall, floor, ceiling or clutter is provided. Other work devised to semantize indoor scenes [START_REF] Kim | Acquiring 3D indoor environments with variability and repetition[END_REF][START_REF] Shao | An interactive approach to semantic modeling of indoor scenes with an RGBD camera[END_REF], focus on understanding clutter in indoor environments.

Contributions and overview

Our approach reconstructs volumetric models of indoor spaces, by extending a previous work [START_REF] Oesau | Indoor scene reconstruction using primitive-driven space partitioning and graph-cut[END_REF]. [START_REF] Oesau | Indoor scene reconstruction using primitive-driven space partitioning and graph-cut[END_REF] partition the bounding box into cells using walls detected by a Hough transform. An empty/solid space labeling is formulated as an energy minimization and solved using graphcut. The final model is extracted as the union of all cells labeled empty. In this work the level of detail of the reconstructed model is limited by the construction of the space partitioning. By introducing a multi-scale line fitting we enhance the alignment of the space partitioning with the permanent structures, which is particularly relevant for highly detailed structures.

Experiments from defect-laden data and different sensors, including a scene recorded by a Kinect handheld sensor, are provided. Our new approach substantially increases the amount of details and overcomes some of the above mentioned limitations:

• Arbitrary wall directions: The model is not restricted to the Manhattan-World geometry and deals with planar wall detection for arbitrary vertical directions. The only assumption is that floors and ceilings are horizontal.

• Multi-level buildings: Our approach reconstructs an entire building with multiple levels in a single optimization step without requiring a priori knowledge about the levels.

• Missing and outlier data: 3D space partitioning into volumetric cells and labeling of the cells by global energy minimization provides resilience to missing data and outliers.

• Raw data: To be as general and applicable as possible, only dense raw point sets and knowledge about vertical direction are required. Nevertheless, when oriented normals or knowledge about the scanning device position are provided, they can be used to further improve robustness.

Our method takes as input a point cloud P = {p 1 , ..., p n } ∈ R 3 and consists of two main steps depicted in Figure 1: 1. Space partitioning: The bounding box of P is partitioned into volumetric cells by using detected permanent structures as splitting planes. The vertical distribution of the point cloud is first analyzed in order to separate the points into slices containing horizontal/vertical structures and clutter. Each horizontal slice containing wall structures is then analyzed in 2D after vertical projection, in order to extract the wall line segments. Line extraction is performed through a multi-scale, featurepreserving line fitting method, followed by global clustering in a Hough transform space in order to favor alignment of the walls. Such alignment reduces the complexity of the volume partitioning. 2. Surface extraction: The volumetric cells created in previous step are labeled into either solid or empty space, respectively for permanent structures (walls, floors, ceilings) or outside. The final reconstructed surface is then deduced from the labeled cells.

Space partitioning

The goal of this step is to provide a 3D space partitioning of the bounding box of P into volumetric cells that well align to the empty and solid space. Using the permanent structures for partitioning the space provides such alignment. The following sub-steps describe the extraction of directions of horizontal and vertical permanent structures to create a 3D space partitioning.

Horizontal slicing

Walls are assumed to be vertical and perpendicular to floor and ceiling, and the permanent structures are assumed to be piecewise linear along the vertical direction. At every height where the permanent structures change we assume the presence of horizontal planar structures, i.e., floor or ceiling. In this step the point cloud is vertically partitioned into horizontal slices containing important horizontal structures and vertical slices containing vertical structures, i.e., walls. To detect the horizontal structures, we extend an idea from [START_REF] Okorn | Toward automated modeling of floor plans[END_REF]. The scanning of horizontal structures generates a high number of samples sharing similar heights. Hence, horizontal structures show up as peaks in the point distribution along the vertical axis. The presence of clutter challenges the detection as it shows up as noise in the distribution. To filter the clutter, we remove the points whose normals are not parallel to the vertical direction (Figure 2). If normals are not available, they are estimated through local principal component analysis (PCA) applied to a local neighborhood.

For extracting the peaks from the point distribution we create a histogram. The bin size has to be manually specified, a default value of 5-10 cm is suggested. The peaks in the distribution are located through mean shift [START_REF] Cheng | Mean shift, mode seeking, and clustering[END_REF]. Mean shift is an iterative algorithm similar to gradient descent for detecting maxima in density functions. For discretized spaces, mean shift is able to detect the interpolated maxima and yields a higher precision than the discretization of the underlying space. Before locating the peaks in the distribution via mean shift a Gaussian smoothing is applied. We use a flat kernel for mean shift. By choosing a kernel and bin size, close peaks in the distribution are inherently merged by mean shift. Each bin in the distribution is used as a starting point for the mean shift. We iterate until convergence or a maximum of 10 iterations has been reached. To ensure a minimum distance between two peaks, close peaks within a small distance h are clustered. We choose a default value of twice the bin size for h. The z coordinate of each maximum is denoted by

m i , i ∈ {1, .., N m }.
The point cloud is now split at points around the peaks into horizontal structure-slices, containing the peaks and representing floor and ceiling, and into wall-slices, covering the remaining parts representing the walls. The split points are thus selected based on the gradient of the distribution. The number of points in the bins of the distribution is assumed to drop significantly around the horizontal structures. The split points are located by walking through the bins in the distribution in both directions from the peak until the gradient is significantly smaller than at the first step adjacent to the peak. An example of selected split points is depicted by Figure 3.

If the split points are not located within a certain range around the peak, the peak is considered to be clutter and removed. As every local maximum in the distribution is detected, peaks that are not significant, i.e., that do not stand out to their neighborhood by a certain ratio, are removed. As close peaks are merged by mean shift and splitting points are chosen within a maximum range it is guaranteed that split points of adjacent peaks do not overlap. The type of slice, wall-slices or horizontal structure-slices, is thus alternating along the vertical direction. For the following steps only the wall-slices are considered. However, both types of slices are used for the graph-cut optimization used for model extraction.

Line extraction

The line extraction step aims at identifying wall segments from each wall-slice created in the previous step. The identification is split into three steps: (1-Filtering) the points are projected in the horizontal plane and clutter is filtered; (2-Line fitting) a multi-scale line fitting method is used to generate a line hypothesis for each point representing the local wall direction; (3-Clustering) the points are locally clustered into wall segments, and these segments are globally clustered into wall directions through a Hough transform.

1-Filtering:

The detection of wall segments in indoor scenes is hampered by the presence of clutter: The clutter occludes the sight of the scanning device so that parts of the wall geometry are not sampled. When detecting permanent structures in the point cloud, clutter may be classified as permanent structure or vice versa. To avoid these cases, clutter is removed by filtering the points of the wall-slices by their normals. As walls are assumed to be vertical, points with a non-horizontal normal are filtered. More specifically, each point p i in the wall-slices with normal n i is removed when

|n i • n z | < t,
where n z is the unit vector along the vertical axis. A threshold of t = 0.02 corresponds to a deviation of a few degrees of the normal from the horizontal plane and provides a strict filtering of clutter while preserving samples on wall geometry, see Figure 4.

In order to gain robustness to missing data caused by occlusion and to reduce the problem to 2D, each wall-slice is projected vertically into the horizontal plane. Since walls are nearly vertical they get projected into line segments. Depending on the acquisition method the point distribution may exhibit a strong anisotropy. To remove anisotropy and speed up the following steps, we perform downsampling through an occupancy grid with uniform grid-size τ , provided as a parameter. In an occupancy grid each grid cell is labeled either empty or occupied. Downsampling is performed via replacing all points inside the cell by the averaged point location. This restricts the spatial point density to the grid size and approximates the original point coverage, see Figure 5. A small grid size τ allows for preservation of details in highly sampled areas, whereas a large grid size permits the reconstruction of sparsely sampled areas.

2-Line fitting:

The wall direction at a point p i may be estimated from the simplified projected points Q via local line fitting to a spatial neighborhood:

N p i ,r := {p ∈ Q : p -p i 2 < r}.
(1)

However, there are unknowns: the local level of detail, ie., the wall geometry, and the scale of the neighborhood considered for fitting.

For longer wall segments without details, the neighborhood for estimating the wall direction should be as large as possible to provide stable results in presence of noise. However, for points close to corners the size of the neighborhood must be small and therefore results in imprecise estimation, see Figure 6 (left). Furthermore, a corner has a higher level of detail as it cannot be described well with a single line.

In order to obtain a wall direction adaptive to the local scale and level of detail, several hypotheses are made at multiple scales. For each point the hypotheses are evaluated to find the one that best describes the local wall geometry. The idea behind the line fitting is that on a blueprint, walls compose a piecewise linear polyline separating the indoor space and the solid space, ie., permanent structures. Thus for each of the points there exists a small neighborhood in which the local wall configuration consists of either one straight wall or two walls in a corner. We exclude non-manifold configurations by assuming a non-zero wall thickness. For each scale of each point two hypotheses are proposed: a single line hypothesis to describe simple straight walls and a two-line hypothesis for detecting corner configurations. The two-line hypothesis is created via RANSAC. Two pairs of points are randomly selected from the neighborhood and used to construct two lines l 1 and l 2 .

The quality of the hypothesis is measured in the least-squares sense by:

S = n i min j∈{1,2} dist(p i , l j ) 2 , ( 2
)
where dist(p, l) is the ℓ 2 distance between point p and line l. After a series of samplings, the pair of lines with the lowest sum of squared residuals S is selected as the best pair for the current scale.

As the local level of detail is not known several line hypotheses are established at multiple scales in order to select a level of detail. The scales, i.e., the ranges of the neighborhoods used for the hypotheses, are selected as multiples of the grid size τ . The minimum number of points in the neighborhood is set to five, as for a smaller number there always exists a perfect alignment of two lines. The smallest scale considered relevant is N p i ,2τ , as even smaller neighborhoods are unlikely to contain five or more points.

To find the proper line hypothesis for a point, the largest suitable scale for each type of hypothesis, single line and two lines, is first selected. This selection is performed by generating each type of hypothesis at increasing scales, starting with N p i ,2τ . If a hypothesis matches a certain quality criterion, the scale is increased by doubling the range N i p i ,r → N i+1 p i ,2r . The largest suitable scale is considered to be the largest scale before the quality criterion fails, see Figure 6. The quality of the hypothesis is measured by the maximum Euclidean distance from a point p in N p i ,r to the closest line. A parameter ǫ is introduced to control the quality criterion:

max p∈Np i ,r min j∈{1,2} dist(p, l j ) 2 < ǫ 2 , (3)
where ǫ denotes the tolerance distance between a point and the closest line. A high tolerance value deals with high noise in the input data and vice versa. Among the two types of hypothesis (single or two lines), the hypothesis with largest scale is selected. When the two scales are equal the single line hypothesis is favored. There is one exception to this. If the two line hypothesis consists of two almost collinear lines, we consider the local wall configuration to be a single straight wall and discard the two line hypothesis.

Finally, a wall direction, i.e., a line l i , is assigned to every point p i by choosing the closest line of the selected hypothesis. The wall direction estimation process is illustrated by Figure 7 (left).

3-Clustering: For linear wall parts and corners the multi-scale line estimation of wall directions is satisfactory, but for small wall segments the assigned wall directions are inhomogeneous, see Figure 7 (middle). For robust clustering of points into wall segments, we adopt an idea from [START_REF] Huang | Edge-aware point set resampling[END_REF] to sharpen and separate the assigned wall directions of the points. Through bilateral filtering, originally introduced for signal processing by [START_REF] Smith | Susan -a new approach to low level image processing[END_REF], the points are classified around sharp features into disjoint clusters by their normals. We apply the bilateral filter as an iterative filter updating the wall direction of one point with the weighted average of the wall directions of the surrounding points. The scale s, selected during the previous step, is used for determining the neighborhood:

n ′ i = p j ∈Np i ,s n j θ(dist(p i , l j )) ψ(n i , n j ). ( 4
)
The normals n i and n j in the original formulation are replaced by the assigned wall directions. θ is the spatial weighting function, providing a high weight for points that are close to the chosen line l i as they are likely to be part of the same wall segment. A Gaussian weighting function is chosen, parameterized by the ℓ 2 distance of the current point p i to the line l j fitted to neighboring point p j :

θ(d) = e -d 2 σ 2 spatial with σ spatial = 2ǫ 2 . (5)
We then define a similarity function ψ favoring points with similar wall direction. The similarity function from [START_REF] Huang | Edge-aware point set resampling[END_REF] is adapted by using the wall directions instead of the nor- mal vectors:

ψ = e - 1-n T i n j 1-cos(σ) 2 (6)
with σ set to 15 • . We next extract the wall segments through region growing. The bilateral filtering and region growing clusters neighboring points into wall segments. As many wall segments are nearly collinear, we use a Hough transform for global clustering of the wall segments into lines, see Figure 8.

The Hough transform [START_REF] Davies | Computer and Machine Vision: Theory, Algorithms, Practicalities[END_REF] is used for robust 2D line extraction through accumulation and extraction of local maxima in discretized parameter spaces denoted as Hough Accumulator. In our framework the angle of each line respect to the x axis and the distance between the line and the center of the bounding rectangle of the scene are chosen as parameters. Each cluster is added to the Hough Accumulator with a fitted least-squares line and a number of votes corresponding to the number of points in the cluster. The main wall directions are so extracted one by one, starting with the global maximum in the Hough Accumulator. For each extracted maximum a line segment is fitted to cover the span of all points contained in the correspond- ing cell of the Hough Accumulator. All other clusters that match the line are removed from the Hough Accumulator and the next peak is detected. A cluster is considered matching a line when its points have a maximum distance ǫ to the line. This procedure is repeated until all clusters have been extracted from the Hough Accumulator.

Cell decomposition

We partition the bounding box by first splitting the horizontal cross section of the bounding box into single 2D cell decomposition and stacking copies of that 2D cell decomposition vertically to yield the 3D space partitioning. For constructing the 2D cell decomposition we use the line segments extracted from the Hough Accumulator. In architecture wall directions are often shared within and even across different levels of the building. To consolidate for wall segments that were not detected on all floors, we combine line segments from all levels to create the 2D cell decomposition. During combination of lines from different levels very similar ones are clustered as they represent the same wall direction. We consider line segments with a certain extent to be a shared wall direction and extend them to lines crossing the complete bounding box. We then use the CGAL arrangement data structure [START_REF] Agarwal | Arrangements and their applications[END_REF] for partitioning the horizontal plane by these lines into a 2D cell decomposition. Line segments with a smaller extent are considered as local details and are only used to split cells in the decomposition locally. A default value for the minimum line extent of 1m has proven to be suitable. The 3D space partitioning is then created by vertically stacking copies of the 2D cell decompositions, one for each wall-slice. Each copy is vertically extruded at the height of the corresponding peak in the distribution of the associated wall-slice, see Figure 9.

Surface extraction

The final model is extracted from the 3D cell decomposition through labeling the cells as either empty or solid space. We formulated this binary labeling problem as a global energy minimization, solved through a graph-cut algorithm [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF]. Such global min- imization provides robustness against defectladen data.

An undirected graph G is defined by a set of vertices V and a set of edges E:

G := (V, E) with E ∈ V 2 . ( 7
)
Graph G is embedded into the 3D cell decomposition by associating each vertex to a volumetric cell. The edges of G connect all pairs of cells that share a vertical or horizontal face of the cell decomposition. We then use a graphcut solver to minimize the following energy:

min l∈{0,1} |V | i∈V D i (l i ) + α (i,j)∈E R i,j (l i , l j ), (8)
where V denotes the vertices and E denotes the edges of G. The label l i of a cell is either set to 0 for solid space or to 1 for empty space. D i denotes the data term used for each label l i assigned to the cell i in order to favor data faithfulness. R i,j , referred to as the regularization term, represents a pairwise cost for connected cells. The parameter α is used to trade regularity for data faithfulness. The data and regularization terms are determined with the horizontal structure-slices and wall-slices.

Regularization term

The regularization term R i,j is defined to favor a final model with low complexity. The penalty for different labels between adjacent cells is thus set to be proportional to the area of the shared face, see Eq.9. A i,j denotes the surface area of the shared face between cells i and j. For scale normalization the area is divided by the area of the horizontal cross section of the bounding box. As observed by [START_REF] Xiao | Reconstructing the world's museums[END_REF], approaches that penalize the surface area tend to miss thin details such as walls. To preserve thin structures, a weight is thus introduced in order to lower the cost of different labels between adjacent cells where permanent structures are expected. The weight is added to the regularization term without eliminating the favoring of a low complexity.

The weights between vertically adjacent cells lower the cost if horizontal structure is expected in the vicinity of the face. The presence of horizontal structure is estimated by the presence of points close to the face in the horizontal structure-slices. However, due to noise as well as imprecise cell alignment and varying scanning resolution, taking only the point density close to the face into account is ineffective, see Figure 10. Our experiments show that the coverage of the face provides a better solution. To evaluate the point coverage, an occupancy grid is used. The grid size is chosen as 2τ , where τ is the size of the occupancy grid filter used for downsampling during line extraction. The weight ω i,j is then defined via the ratio of occupied grid cells to total grid cells. The weights of horizontally adjacent cells are determined similarly. The shared face is vertically projected into an edge. The coverage of the edge by the points of the corresponding wall-slice is determined by discretizing the edge into bins of size 2τ . The weight ω i,j is then defined as the ratio of number of occupied bins to total number of bins. This results into the following regularization term in cells i and j: R i,j (l i , l j ) = 0,

l i = l j (1 -ω i,j ) • A i,j , l i = l j (9)
However, for thin cells multiple faces might be close to the same points. As each face is generated by one specific line extracted during the line extraction step, only points of clusters fitted to this line are considered for that face.

The cost for different labels might thus be zero only when the face or edge is fully covered. Such regularization term satisfies the condition of submodularity stated by [START_REF] Kolmogorov | What energy functions can be minimized via graph cuts[END_REF], see eqn. 10.

R i,j (0, 0) + R i,j (1, 1) ≤ R i,j (1, 0) + R i,j (0, 1). ( 10)

Data term

To provide a cost for each combination of cell and label, an estimation is done for each cell whether it belongs either to the empty or solid space. If the scanning device position is provided, this can easily be estimated by making use of the free space between each scanned point and its associated scanning origin. The problem of identifying inside and outside is recurrent for surface reconstruction [START_REF] Lafarge | Surface reconstruction through point set structuring[END_REF]. Our rationale is, that a ray cast from a point has an odd number of intersections with the geometry if the point is in empty space and an even number if it is in solid space. For counting intersections between a ray and the point cloud one solution would be to define a surface from the point cloud. However, clutter and missing data are likely to interfere and distort the number of intersections. The weights used for the regularization term are used as they are meant for indicating the presence of permanent structure. Rays are thus cast from each cell center and each intersection with a face with an assigned weight ω i,j >1 2 is counted as an intersection with a permanent structure, see Figure 11.

To improve stability at the cost of computation time, a higher number of rays can be send. The ratio of rays r i for cell i is defined as the ratio of rays with an even number of intersections to the total number of rays. It is mapped with an inverse sigmoid function f : [0, 1] → [0, 1], see Figure 11. f is chosen so that a value of r i is mapped conservatively to a cost c. Ratios not clearly indicating either empty or solid space are mapped to the same cost for both labels. In this way the label depends on the regularization term. Due to the different sizes of cells, larger cells receive a higher penalty from the regularization term as they have a larger surface area. In order to eliminate this bias the cost of the data term is scaled by V i . V i is defined as the volume of the cell i that, for scale normalization, is divided by the volume of the bounding box.

This leads to the final data term function:

D i (l i ) = c • V i , l i = 0 (1 -c) • V i , l i = 1 (11)
After the labeling is done, every cell is marked as either empty or solid space. The final 3D model is extracted as the set of faces between different labeled adjacent cells.

Experiments

We evaluate our method on a synthetic multi-level data set, two measurement data sets obtained by two types of laser scanners and one data set acquired with a Kinect sensor. The algorithm is implemented in C++ using the Computational Geometry Algorithms Library [START_REF] Cgal | Computational Geometry Algorithms Library[END_REF]. For energy minimization we use the Graph Cut Library [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF].

Cory 5th floor. In the measurement data set, 1 the point cloud is sampled on a hallway exhibiting non Manhattan-World geometry, including curved walls and archways. Some data are missing as several ways and rooms have partially been scanned without being entered. The scene also contains many fine details such as doors and tilted windows, and clutter such as couches and curtains. To reduce the memory footprint, the point cloud is downsampled by selecting every other point. The reconstructed model covers the structure of the hallway and partly captures details like doors, see Figure 12. The lintels of the doors are not sampled densely enough to appear as peaks during height analysis, and hence are not detected as horizontal structures. The height of the doors is extended to the next significant horizontal structure, here the ceiling, see lower right excerpts in Figure 12. The archways have not been reconstructed as our method is not suited to reconstruct surfaces that are non-planar or neither vertical nor horizontal. The circular wall is approximated with planar surfaces and only exhibits minor artifacts although our method is not designed to detect and reconstruct nonplanar walls, see upper right excerpts in Figure 12. The reconstruction in sparsely sampled areas, i.e., rooms and sideways, is incomplete. This is mostly due to the absence of walls, as it impacts both the space partitioning and the energy minimization. Inria Euler building. Using a Leica Scanstation P20, we performed an acquisition in the Euler building at Inria Sophia Antipolis. The data sets consists of 6 registered scans showing several adjacent rooms including the entrance, a conference room, a lecture room and a small corridor. It features walls scanned from both sides, clutter like chairs and tables as well as vegetation captured outside. The input data and the reconstructed model are depicted by Figure 13. The thin walls have been reconstructed, while the clutter outside does not interfere with the reconstruction. Synthetic data set. For evaluation we use as ground truth a synthetic data set created using Google Sketchup. We then use Meshlab for sampling a point cloud from the exported triangle mesh. A small amount of uniform noise (5 mm) is added after sampling. The ground truth model features a multi-floor, non Manhattan-World scene. The reconstructed model shows that different wall directions are reconstructed accurately, see Figure 14. Reconstruction of non-orthogonal wall directions is depicted by the upper two close-ups. The reconstruction of different height levels is shown by the lower two close-ups. The mesh is colored by the Hausdorff distance from the result to the ground truth showing a maximum distance of 2.3 cm. A small deviation in the reconstructed wall directions was caused by global clustering in the Hough transform space. Such merging incurs a small deviation visible in the two red colored corners of the reconstructed model. The chosen parameters and timings are listed in Table 1.

Kinect data set. Point clouds acquired by the consumer-grade Kinect sensor are challenging our algorithm as they contain many defects ( [START_REF] Khoshelham | Accuracy and resolution of kinect depth data for indoor mapping applications[END_REF]. The scene exhibits a single office room containing clutter such as a desk, some cupboards and a bicycle. As the scan covers only a small part of the floor and no ceiling at all, no significant peaks show up in the horizontal distribution and the scene is processed as a single level. Compared to commercial-grade laser scanners the high level of noise requires a high tolerance value (ǫ = 6 cm) for clustering of the wall directions. The input data and reconstructed model are shown by Figure 15. Most of the room is correctly reconstructed except a corner entirely occluded by a bicycle and a cupboard. The corridor could not be reconstructed due to very sparse sampling.

Comparison with [START_REF] Oesau | Indoor scene reconstruction using primitive-driven space partitioning and graph-cut[END_REF]. We evaluated the improvement over previous work using the Cory 5th floor, as it contains different level of details, varying from a large corridor to small niches and a circular wall segment. While both methods are able to reconstruct the main corridor, our new method, reinforced by a more accurate line detection strategy, exhibits a much higher level of detail. The circular wall is reconstructed with many small linear segments with our method, whereas the former method only provides a rough approximation. Results from both methods are shown by Figure 16.

Parameters

The parameters have a direct impact on the quality and level of detail of the reconstructed model. The bin size for the horizontal slicing affects the detection of horizontal structures. It should be larger than the typical amount of noise, but still allow for several bins between horizontal structures in the height histogram. In general a value of 5-10 cm is suggested. However, for scenes containing just ceiling and floor the method is tolerant to the choice of the bin size. τ relates to the point density in the scanned data and is used for the downsampling. A high value improves the reconstruction of sparsely sampled regions, while removing detail from highly sampled regions due to the downsampling. Technically, τ should be chosen as the Top: Reconstructed model from previous work [START_REF] Oesau | Indoor scene reconstruction using primitive-driven space partitioning and graph-cut[END_REF]. Middle: Result from the presented model. Bottom: An excerpt of the circular area is shown. In contrast to the original method many more details are recovered.

minimal sampling resolution, i.e., largest distance between neighbored points in the area of interest. In usual cases this parameter will be chosen in a range between 0.75 and 4 cm. ǫ is used for the multi-scale line fitting and clustering of extracted wall directions. It indirectly relates to the number of cells generated in the space partitioning. High values of ǫ lead to reconstructed models with low levels of detail (Figure 17), in short computation times, especially for model extraction. A value of at least twice the range of scanner noise is recommended. The Hough transform is used to cluster the detected wall segments. The effect of the chosen resolution is depicted in Figure 8. As the clustering is also restricted by the choice of ǫ, a coarser resolution of the Hough Accumulator can be used as a starting point for parameterization: 2 • • τ. α is used to trade data faithfulness for regularity in the energy minimization formulation. For densely scanned data a low value of α en-forces faithfulness to the input data. For incomplete data a high value of α provides regularity by filling gaps but may over-simplify the model (Figure 17). Note that α is only used for the last step, i.e., labeling. An adjustment and extraction of a new result requires only few seconds of computation time.

Accuracy

We evaluate the accuracy of our method by comparing the reconstructed model to the synthetic multi-level data set used as ground truth. Figure 14 illustrates that different wall directions are reconstructed accurately: the symmetric Hausdorff distance is 2.6 cm and the one-sided Hausdorff distance from the result to the ground truth is 2.3 cm (Figure 14).

Performances

Running times and parameters are provided in Table 1. Timings are measured on an Intel Core i7 920 with 16 GBs RAM. The time spent to estimate the normals is omitted. The most time consuming steps of the algorithm are the stochastic ray-casting to determine the data term and the multi-scale line fitting. A kD-Trees is used to speed up the calculation of the edge weights for the regularization term (see section Regularization Term).

Robustness

We first evaluate the robustness of our approach against sparse sampling with downsampled instances of the Cory 5th floor (50%, 20%, 10% and 5% of the original point cloud, generated by selecting every 2nd, 5th, 10th or 20th point of the original point cloud). The parameters set for reconstruction are adapted to each downsampled version. As the point density is lowered by downsampling the parameter τ used for adjusting the grid size during line extraction is increased. The tolerance ǫ used for clustering is also increased, as line fitting is less accurate on sparse point clouds. While small values for τ and ǫ allows for a detailed reconstruction of high resolution scans the method tends to generate more bumpy artifacts. Higher values of τ and ǫ may miss details, but provide lower computation times and more regular reconstructions. Timings and parameters for the lower resolution data sets are provided in Table 2. The reconstructions from the downsampled instances are shown in Figure 18. The reconstruction of the 50% data set provides the same amount of details as the original data set. In the lower resolution data sets the connected rooms and sideways are imprecisely recovered or not at all, as they are even sparsely scanned in the original mesh. The recovery of details for the lower resolution data sets is depicted in the right column. Note that the doors and niches in the corridor are extended to the height of the ceiling.

Robustness to noise is evaluated by adding noise to the Cory 5th floor data set. More specifically, each point of the input point cloud is displaced along a random vector, with maximum length set to 5 mm, 25 mm and 50 mm. The noise is thus added to the noise of the measurement device, estimated between 3 and 5 mm for common laser scanners. Figure 19 illustrates that noise impacts the level of detail of the reconstruction without altering the coarse structures. A small amount of noise (5mm, the usual range of laser scanners) has minor impact on the small details. With higher amount of noise less details are reconstructed but the coarse structure of the architecture is correctly recovered, except for sparsely scanned areas such as the outer rooms and the two hallways. As the accuracy of the line fitting process is impacted by noise, the parameters τ and ǫ are adjusted to the level of noise. The bin size for the vertical distribution (0.1), α = 250 and the resolution for the Hough Accumulator 1 • • 0.8 cm have not been changed.

Robustness to outliers is evaluated by adding random points uniformly distributed within the bounding box of the Cory 5th floor data set: respectively 1% and 5% outliers. The reconstruction of those modified data sets are shown in Figure 20. The corridor is reconstructed correctly despite the presence of outliers in both data sets. However, the amount of recovered details is lowered and the circu-

Limitations

Our algorithm is designed to handle arbitrary vertical wall directions. For cases of partially scanned rooms, where some walls are not sampled at all, our method relies on other wall directions detected in the scene or on the borders of partially scanned parts.

These cases may result in improper data consolidation, while algorithms strictly restricted to Manhattan-World scenes often yield more plausible reconstructions. Note, however, that other approaches fail on these cases [START_REF] Jenke | Statistical reconstruction of indoor scenes[END_REF]; [START_REF] Xiao | Reconstructing the world's museums[END_REF].

Global clustering in a Hough transform space performs a regularization as the Hough Accumulator determines the main wall directions and aligns the extracted lines to these directions. We notice, however, that such regularization may hamper the reconstruction of fine details (Figure 12) and requires parameter adjustments. The latter trial-and-error process is time consuming and suggests to investigate automatic parameter selection.

The algorithmic complexity of the ray casting is quadratic in the number of cells of the space decomposition, this number being itself related to the level of detail adjusted through a tolerant or selective line clustering. The computation times thus increase rapidly with the level of detail sough after.

Locating the splitting heights for the point cloud (Section 2.1) depends on the amount of points detected on the horizontal structures. For large scenes such horizontal structures require a very large number of sample points. The door lintels in the Cory 5th floor, for instance, are sparsely sampled and therefore the height of doors is extended to the ceiling (Figure 12, lower right).

Finally, some buildings contain non-vertical walls, non-horizontal floors and ceilings, stepped floors and ceilings, and even nonplanar structures. One of such examples with stepped floors and non-horizontal ceilings is the auditorium of the Delft University of Technology (Figure 21). Our approach fails on such cases with stepped floors and large amount of clutter.

Conclusion

We proposed a new method for indoor scene reconstruction. Through detecting the permanent structures in a cluttered scene we reconstruct a model of the indoor space with satisfactory tradeoff between accuracy and low complexity. Our first technical contribution is a multi-scale, feature-preserving approach for detecting walls as line segments, followed by global clustering in a Hough transform space in order to align the reconstructed model with the permanent structures. Through global energy minimization we label the cells of a 3D space partitioning in order to reconstruct a watertight model consolidating missing data. Our experiments show that our method is moderately robust to noise and outliers, and generates satisfactory results from data measured with Kinect sensors.

As future work, we will investigate the use of non-planar primitives and non-vertical walls in order to both improve accuracy and decrease complexity by simplifying the space partitioning. We will also further investigate regularization through the Hough transform. Detecting and reinforcing canonical geometric relationships (parallel, collinear, orthogonal, coangular) and structural regularities may improve robustness and provide semantic information about the structuring of indoor spaces.

Acknowledgments

The authors wish to thank Astrium for funding this work. Pierre Alliez is supported by an ERC Starting Grant "Robust Geometry Processing" (257474). We also thank the Video and Processing Lab of University of California, Berkeley and Prof. Sisi Zlatanova from the Delft University of Technology for making the data sets available.

Figure 1 :

 1 Figure 1: Method overview. The bounding box is split into cells using detected permanent structures. The final surface is obtained through labeling the cells in empty or solid space, and extracting the interfaces between empty and solid cells.

Figure 2 :

 2 Figure 2: Cluttered and uncluttered distributions. Comparing point distributions along vertical direction nz without filtering by normals (left) and with filtering by normals (right, |ni • nz| > 0.98). The chosen bin size is 8 cm and the distribution is split into 69 bins.

Figure 3 :

 3 Figure 3: Horizontal slicing applied to a synthetic scene. Top: Input point cloud. The excerpt shown below is highlighted by a black box. Left: Distribution along vertical direction. The point cloud is split horizontally within a small range around the peaks. Ranges for horizontal structure-slices are depicted in blue, and yellow for wall-slices. Middle: Excerpt of original point cloud in side-view. Right: Side-view of excerpt colored by slice type.

Figure 4 :

 4 Figure 4: Clutter removal. Left: Wall-slice of a real data set showing a corridor scene in top-view. The scene contains clutter that challenges the wall detection. Right: Most of the clutter gets removed by filtering the points by their normals.

Figure 5 :

 5 Figure 5: Resampling for anisotropy removal. Left: Overview of wall-slice of real data set. Upper right: Original point distribution of wall section in red box. Strong anisotropy is caused by the acquisition method of the scanning device. Lower right: After downsampling, the anisotropy is significantly reduced.

Figure 6 :

 6 Figure 6: Line hypotheses at different scales. Left: Least-squares fitting of a line to the neighborhood of a point (red) located in a corner. Next four images: Fitting of two lines on four scales to a door frame depicted in the center of the scene shown by Figure4. For the two smaller scales, see left and mid-left images, the neighborhood is well covered by the chosen lines. For larger scales however, see mid-right and right images, the geometry is too complex to be covered by two lines.

Figure 7 :

 7 Figure 7: Multi-scale line hypothesis. Wall directions depicted by color in real data scene. Left: Excerpt of scene containing a corridor. The circular wall section is matched accurately. Middle: Some smaller segments have an unsharp diffuse fitting. Right: Segments are separated after filtering.

Figure 8 :

 8 Figure 8: Global clustering of wall segments. Upper left: Clustered wall segments. Upper right: Lines extracted without global clustering. Lower left: Global clustering using Hough transform leads to reduction of the number of lines. Lower right: Over-simplification induced by coarse resolution for Hough Accumulator and a high value for ǫ.

Figure 9 :

 9 Figure 9: 3D space partitioning. The 2D cell decomposition is extended in 3D through stacking and vertical extrusion. mi denote the height of the detected peak during the horizontal slicing step.

Figure 10 :

 10 Figure 10: Estimation of point coverage. Left: Number of points in face is high, but coverage is low. Right: Usage of occupancy grid. Ratio of #occupied to #total grid cells provides approximation of coverage.

Figure 11 :

 11 Figure 11: Data term. Left: Ray-casting to predict empty or solid label for a cell. The cell decomposition is depicted in black and edges with ωi,j > 1 2 are depicted in orange. Rays indicating empty, i.e., odd number of intersections, are depicted in pink versus blue. Right: Inverse sigmoid function f turning ratio ri of rays indicating empty space to total number of rays into c.

Figure 12 :

 12 Figure 12: Reconstruction of the Cory 5th floor. Left: Input point cloud. Middle: Reconstruction of the indoor space. Upper right: Circular wall segment and details in the outer part. Points colored by estimated normals. Lower right: Another excerpt of the input point cloud, sampled on doors in the corridor and on an archway.

Figure 13 :

 13 Figure 13: Reconstruction of the Euler building entry area. Top row: Input point cloud in perspective and top view. Bottom row: Reconstructed model in perspective and top view.

Figure 14 :

 14 Figure 14: Reconstruction from a synthetic data set. Two views on the same reconstruction are shown, colored by the Hausdorff distance from the result to the ground truth.

Figure 15 :

 15 Figure 15: Reconstruction of Kinect-recorded indoor scene. Upper left: Input point cloud featuring an office room. Upper & lower right: Reconstructed model. Lower left: The labeled cell decomposition exhibits a good alignment of the room with the exception of the occluded corner.

Figure 16 :

 16 Figure 16: Comparison with Oesau et al. (2013).Top: Reconstructed model from previous work[START_REF] Oesau | Indoor scene reconstruction using primitive-driven space partitioning and graph-cut[END_REF]. Middle: Result from the presented model. Bottom: An excerpt of the circular area is shown. In contrast to the original method many more details are recovered.

Figure 17 :

 17 Figure 17: Impact of parameters. Left: Reconstruction of the Cory 5th floor with τ = 10 cm and ǫ = 30 cm. Such low level of detail requires 7.2 s. Middle & right: Respectively 250 and 750 for α. The higher regularization α = 750 leads to a lower level of detail through area minimization.

Figure 18 :

 18 Figure 18: Reconstruction at lower resolutions. Each row of the image shows the reconstruction of one downsampled data set (from top to bottom): 50%, 20%, 10% and 5%. Left column: Excerpt of the input data. Left-mid column: Overview over the reconstructed model. Right column: Close-ups showing amount of detail recovered.

  Parameters and running times of lower resolution data sets. The bin size for the vertical distribution (0.1), α = 250 and the resolution for the Hough Accumulator 1 • • 0.8cm do not vary.

Figure 19 :

 19 Figure 19: Robustness to noise. Reconstruction of the Cory 5th floor with added noise. Left: Closeups on the outlined rectangle. Right: Reconstructions and corresponding parameters.

Figure 20 :

 20 Figure 20: Robustness to outliers. Reconstruction of the Cory 5th floor with added outliers. Top: 1% outliers. Bottom: 5% outliers. Left: Point cloud with outliers. Middle: Wall-slice generated by horizontal slicing with only some added points close to the walls remaining. Right: Reconstructed model of the indoor space.

Table 1 :

 1 Running times. Chosen parameters and running times (single thread). Timings for model extraction include the ray-casting performed to compute the data term.

		Synthetic Cory 5th floor	Euler	Kinect
	#points	1,000,000	4,391,604	2,305,938	86,694
	Vertical distribution -bin size	1 cm	8 cm		8 cm	x
	τ	2 cm	1 cm		0.75 cm	1 cm
	ǫ	2.5 cm	1.7 cm	1 cm	6 cm
	Hough res: angle • distance	1 • • 0.25 cm	1 • • 0.8 cm	1 • • 0.8 cm 3 • • 5 cm
	α	20	250		250	250
	Spatial partitioning	63 s	192 s		36 s	6.9 s
	Model extraction	58 s	206 s		66 s	15.2 s
		50%	20%	10%	5%
	#points	4.391.604 1.756.642 878.321 439.161
	τ	1 cm	2 cm	2 cm	4 cm
	ǫ	1.7 cm	3cm	3.5 cm	5 cm
	Spatial partitioning	192 s	70 s	58,8 s	16.8 s
	Model extraction	206 s	68,4 s	58,5 s	12.1 s

Table 2 :

 2

http://www-video.eecs.berkeley.edu/ research/indoor/


Pascal Pochet

Changes in urban travel behaviour of elderly people

For a certain number of years now, France has been undergoing an ageing of its population. This ageing, which is going to become greater and continue over the coming decades is accompanied by profound modifications in the life styles of retired people. They are more and more motorised in the cities and less and less prisoners of the necessity to walk or use public transport. In this paper we will try to study the changes in the mobility of the elderly using diachronic data obtained from household surveys carried out in the seventies and eighties in the Grenoble conurbation. At analytical level, the factors explaining these changes can be linked to the renewal of the generations and the modification of the socio-economic environment which counter the ageing effects. We first situate the travel pattern and modal use evolution of elderly people within the context of the population as a whole. We then go on to deal with the central question in the evolution of the modal distribution, i.e. the individual's access to the private car, and its daily use. The longitudinal study of the successive cohorts enables us to visualise the differences in behaviour between men and women on the one hand, and the determining character of the development of car ownership for successive generations on the other hand. Using a breakdown of car driving into three effects (demographic, ownership and actual use of cars) we show that it is the increase in car ownership, much more than the other two effects, which leads to an increase in car driving after the age of sixty. The same type of analysis applied to people who are presently in the 40 to 60 age-group shows that women, who drive relatively little for the moment, are rapidly going to catch up in the future.

INTRODUCTION

Traditionally, elderly people cannot get about easily and they no longer travel for professional reasons. Over the last few years, however, their numbers, their life style, and their access to individual modes of transport have changed very considerably. These evolutions raise a certain number of questions which urban transport systems will be confronted with in the years to come:  in a country with a high car-ownership level, will the ageing of the population, increased motorisation, and modifications in the behaviour of elderly people, lead to an increase or a decrease in the importance of the automobile for daily travel in the cities?  what can the consequences of these changes be on the future of urban public transport, on the problems of traffic in cities, and on the satisfying of the travel needs of the elderly who cannot use this travel pattern?

In this paper we will try to study the changes in travel behaviour of the elderly using diachronic data obtained from household surveys. These changes can be explained by effects linked to the renewal of the generations and to the modification of the socio-economic environment which conflict with the effects which are due to ageing. We will first place the evolutions which concern elderly people in a wider context and then go on to deal with the central question in the evolution of modal distribution, i.e. the access to and the use of the private car. To study changes in behaviour, the more appropriate data are the panel surveys, but, as far as we know, in France they do not exist in the field of urban mobility. So we use household travel surveys carried out in Grenoble conurbation in 1978, 1985 and 1992. A longitudinal analysis of the different cohorts and a modelling of the growth of car driving using three parameters (demo-graphy, motorisation and actual driving) allow us to show that the growth of motorisation, rather than the other two parameters, leads to growth in driving.

Using the same surveys carried out among people who are presently in the 40 to 60 age-group, we will show that women, who drive little for the moment, are more than likely to catch up over the next 10 to 20 years, as a result of increased motorisation and car-use.

GENERAL CONTEXT

In France, as in many industrialised countries, elderly people's place in society is undergoing very considerable change as the result of multiple factors whether they be demographic, sociological or economic. From the demographic point of view to begin with, the considerable lengthening of life expectation and the decrease in fecundity have come together to push up the percentage of elderly people in the population. Thus, the 1990 census shows that there were more than 11 million elderly people in France, i.e. almost one-fifth of the population. In the long term, if this evolution continues along the same lines, in 2010, one out of every four people will fall into this category. But this demographic fact needs to be interpreted correctly: for the same chronological age, elderly people's living conditions have been completely transformed over the last twenty years -improvement in the state of health i considerable increase in retirement revenues; so much so, in fact, that they are even higher than those of working people. However, despite these positive evolutions, the elderly population does not go to make up a homogeneous group. It is perhaps more a question of inequalities in cultural background, life expectation and state of health all brought together, which lead to such contrasting post-retirement situations, rather than differences in revenue. What has an eighty-year-old, living alone, with health problems and belonging to a generation which hardly knew the car, in common with a recently retired couple in full possession of their physical and intellectual faculties and who are fully active even if they no longer have any professional activities, and who, moreover, have a rich social-life and are car drivers?

More generally, this longer period of retirement has led gerontologists to consider two distinct periods in the life cycle of the elderly: younger pensioners, and older pensioners. Younger pension age is usually lived through in good health, in the company of the pensioner's companion, and can last, depending on individuals, till the age of 75 or indeed 80. After that, older pensioners suffer from physical handicaps and a certain amount of social isolation, which severely limit travel patterns. Both of these periods of retirement are submitted to socio-economic change, to the renewal of the generations, and to the effects of ageing -but in very different ways.

FRAMEWORK FOR ANALYSIS AND METHODOLOGY

Various authors have shown that it is possible to classify the different factors which act on life-style evolutions and mobility into three categories: the effects of age; the effects of generation; the effects of period [START_REF] Wachs | Transportation for the Elderly. Changing Lifestyles, Changing Needs[END_REF][START_REF] Kessler | Cycle de Vie et Génération[END_REF].

The effects of age cover several factors. There is first a continuous but non-linear process of individual ageing, be it physical or mental, along with the weight of experience acquired and habits inherited from the past. A certain amount of work of social orientation [START_REF] Guillemard | La Retraite, Une Mort Sociale. Sociologie des Conduites en Situa-tion de Retraite[END_REF]Paillat, 1989) shows that daily activities at retirement age generally reproduce the activities which were already frequent in the past -new activities are rare. To this individual aspect of ageing we must add the discontinuities induced by the transitions in the life cycle and their specific social constraints.

Thus, for elderly people, the departure of children, retirement, or the death of a spouse can be events which determine their way of life and their mobility. In particular, for active people, retirement creates a vacuum of occupations and professional relationships, and these lead to a brutal reorientation of their field of activities. How they face up to this depends on their cultural background and the social position which they had acquired during their active period, and upon their ability to adapt.

The notions of generation or of cohort enable us to consider the individual's date of birth as just as important a variable as age for analysing social behaviour evolutions. The effects of generation or cohort are to be seen when one generation or more, because of their past, and their specific characteristics, adopt behaviour which is different from that of preceding generations at the same age. These inter-generation changes can be explained by an evolution of the economic environment of each generation.

The notion of period effects tries to integrate change which is linked to specific historic events and to the particular economic and social context of each epoch. For example, the growth rate of revenues, an improvement in the public transport system, a change in the relative prices of the various modes of transportation, can all be classified as period effects. For there to be a period effect, similar evolutions must therefore concern a large number of age groups and generations during the period under study.

From a prospective point of view, it is very interesting to try to distinguish the influence of the three effects -age, generation, period. Thus, the permanence of the effects of age enable us to highlight the invariable part of behaviour in time. Furthermore, generation changes which can already be seen amongst younger people should enable us to anticipate futures evolutions for the elderly. What is much more difficult to forecast are the effects of period linked to future variations in the economic and social environment. From a practical point of view, however, these three effects are not independent. It is not always easy to see where effects of generation stop and where effects of period begin. In particular, generations evolve under the influence of modifications in the socio-cultural environment, and this leaves a different mark on every generation as a result of its position on the age scale -the least elderly being considered as the most permeable to change. In the same way, the effects of age evolve under the influence of the renewal of generations and according to the period -on the contrary, generational differences can diminish with age.

In order to carry out the study of past evolutions, diachronic data was necessary. We use a series of household surveys carried out in the Grenoble conurbation in 1978, 1985 and 1992 (for certain aggregate results we have added in the results of a 1973 survey). Grenoble is one of the rare French cities which have been submitted to so many household surveys ii . Furthermore, the regular seven-year interval between the last three surveys makes the longitudinal study of successive seven-year amplitude cohorts possible. Finally, the Grenoble conurbation with 400,000 inhabitants proposes various transportation possibilities. There isan excellent urban transportation network cycling tracks iii . And despite these factors the car ownership rate is relatively high.

In this context, the evolutions in travel behaviour of elderly people must first be replaced within the context of the overall evolutions to be seen in Grenoble, if we are to hope to obtain a clear picture.

When we consider the population as a whole, the evolution over two decades shows an alignment of the travel models of men and women who have a high level of motorised mobility. The reasons for this evolution are now reasonably well-known. An example is the development of two-car ownership which is subtended by two tendencies which are highly characteristic of French society in the seventies and eighties:

 the spectacular growth of the rate of feminine activity. France is the European country with the highest number of women in full-time employment;  the extension of suburbs as a result of people's preferring individual dwellings, and a widening out of the locations of activities, employment and equipment. One of the major consequences of this sub-urbanisation is a mean increase in commuting distances.

MOBILITY AND USE OF TRANSPORTATION MODES: THE PARTICULARITIES OF ELDERLY PEOPLE General Evolutions in the Use of Modes

Over the last two decades, it is more than clear that there has been a very considerable evolution as a result of the ever-increasing domination of the private car over the other modes of transport, whether we consider women or men, and whatever the age group considered may be (cf. Figures 1a and1c). Urban public transport is on the increase thanks to a considerable improvement in offer and quality of service. This growth has not been to the detriment of the car but rather to that of proximity modes such as walking and cycling. As far as the evolution concerning walking is concerned, it may be partly due to a variation in the area of the poll. In particular, in the case of Grenoble, the people living in the suburbs are more numerous in 1992 than in the 1985 poll. This does not however put the reality of a decrease over these 15 years into question, since this fall has been noted in other French cities [START_REF] Orfeuil | Changements structurels de la population et impact sur la demande de transports de voyageurs[END_REF], German cities [START_REF] Brög | Changements structurels de la population et impact sur la demande de transports de voyageurs[END_REF], and Canadian cities [START_REF] Chapleau | Evolution de la mobilité des personnes de l'agglomération urbaine de Québec[END_REF][START_REF] Bussière | Forecasting travel demand from age structure, urban sprawl and behaviour: the Montreal case[END_REF]. This decrease has gene-rally been to the benefit of the private car.

In this context, the evolution of the behaviour of people of sixty and over is logically a little behind. Here, the feminine travel model is very different from that of men (cf. figures 1b and 1d above). As far as women are concerned, car-use is very marginal indeed, and only to be observed amongst a certain category of women who were in salaried employment before retirement and whose socio-cultural level is high. On the other hand, retired men's level of car use is close to that of working men.

This behaviour mean must not be allowed to hide the very considerable differences which exist in the use of mode of transport after the age of sixty. These differences are not only due to sex, age and generation, but also to the action of other factors which may be linked to them, such as place of residence, the former socio-professional category, the level of education and matrimonial status.

A Very Different Use of Modes of Transport by Elderly people

With active people, the main constraints are temporal, these disappear or weaken upon retirement, and give way to space constraints. The activities undertaken outside home are now limited by the field of the places which can be reached, taking into account the level of car ownership and personal access to a car, as well as the public transport service available, and the person's state of health. These differences of course affect elderly people's daily mobility. Thus, the very old (over eighty) generally go out twice as little as people in their sixties. This also explains why proximity trips remain important for downtown residents, where the density of habitation, shops and equipment of all sorts are high. Thus, in 1985, on-foot mobility for downtown dwellers of over sixty in Grenoble was 80% higher than in the suburbs. Conversely, at the same date, elderly people who can drive use their cars twice as often when they live in the suburbs. The use of public transport becomes of paramount importance for non-motorised people. In particular, non-motorised women over seventy living in the suburbs made a quarter of their trips using public transport in 1985, whereas this proportion falls to less than 5% for motorised men in the first half of their sixties. The former profession, and in a closely correlated manner, the level of studies and income, play a double role in travel behaviour. As far as these generations of people are concerned, it was the well-off who benefited most from motorisation. The most mobile potential drivers here are ex-professional men or -executives. Finally, the importance of matrimonial status is not so visible. In actual fact, it has little effect on mobility, whatever mode of transport is considered. On the other hand, it has a certain influence on car-driving for motorised women, as we shall see later.

Since we have now set out the general framework, we can now come back to the all-important question for the future -viz. the evolution of elderly people's car-driving in relation with the growth of car-ownership for successive generations of men and women.

THE ELDERLY AND THE CAR The Elderly and Motorisation

The household surveys do not give us details about the real availability of a vehicle for the different members of the family polled. We will therefore refer to licence-holders whose household has at least one car as motorised persons, actual or potential drivers, or "drivers" for the sake of simplicity. cohort between 1978, 1985 and 1992. For a given age, the vertical deviations between the cohorts enable us to measure the deviations from one generation to the next.

If we look at the motorisation rates (Figures 3a and3b) of the successive cohorts of men and women, we clearly see that the generalisation of the use of the car came about in cumulative fashion with the renewal of the generations, and it affected women much later than men. As Madre and [START_REF] Gallez | Le parc automobile dans les années 2000 : méthodes démographiques et projection à long terme[END_REF] show in French statistics series, the first wave of motorisation of households took place at the end of the fifties and through the sixties. This phase of massive introduction of the car can partly be assimilated to an effect of period, since it concerned a large number of generations, albeit to different degrees. Motorization was followed throughout the seventies and eighties by two-car ownership and the arrival of a considerable number of women on the employment and car-buying markets. This then explains why present generations of men from 60 to 80 (i.e. born between approximately 1910 and 1930) contain 60% to 80% actual or potential drivers. Conversely, the rate of motorisation of women from the same generations is two or three times smaller! The use that the two sexes make of the car is also very different.

Car Use in Different Generations of Drivers

Figures 4a and4b show, for each cohort, and by sex, the evolution of the number of daily trips made at the wheel of a car by the actual or potential drivers of the sample. The high rate of overlap in the segments of the curves, taken along with their fall after the age of 60 show that the effects of age play an all-important role, specially by the important threshold represented by retirement. The only clear behaviour difference for motorised persons concerns the cohort of men who reach the age of 60-66 in 1992.

The explanation for this surprising inflexion can partially be found in the residential localisation and the social make-up of this sub-group in the 1992 survey. In that year, 70% of the people polled in that age-group lived outside Grenoble, as against 54% in 1985 and 30% of them were former middle-or upper-executives, as against 20% in 1985. As far as the evolution of feminine behaviour is concerned, women over 60 are not yet concerned, but women-drivers who either have children of school-going age or who are salary-earners, areespecially those who concern us most, those in the 45-60 age group. The other lesson which we can obtain from these figures is the persistence of the differences between sixty-year old men and women, once we have done away with the inequalities of car access. While actual or potential women drivers usually make on trip a day on average, men drivers are near to two trips a day, if not more. For the present generations of elderly people, the distribution of roles within the household appears to be relatively rigid, with the man as driver. Thus, elderly married women who are licence-holders are as often passengers as drivers in the family car(s).

Formalising the Evolution in Car Driving

In order to highlight the different effects in the evolution of car-driver mobility better, we have divided up the total volume of trips by age, according to the weight of each age, to the number of motorised persons in each age group, and to the mean number of daily trips made by "drivers" at the wheel for each age group [START_REF] Greene | Long run vehicle travel prediction from demographic trends[END_REF]. The evolution in the use of the car by a driver between date 1 and date 2 is therefore a ratio of the two sums of number of trips for all age groups i:

CD2 CD1 Pi 2Ci 2 Mi 2 i P i i1Ci1 Mi 1   
with P i1 , Pi 2 : number of people in age-group i in dates 1 and 2; Ci 1 , C i2 : percentage of drivers in age-group i (i.e. licence-holders whose household owns at least one car) in dates 1 and 2, and M i1 , M i2 : mean number of daily trips made by drivers at the wheel in dates 1 and 2.

In order to measure precisely the influence of the demographic changes, the growth in motorisation and the evolution in the use of cars by drivers, the evolution of the mean number of car driver-trips can be considered as the product of:

CD2 CD1 E ( P ) E ( C ) E ( M ) E ( P , C ) E ( P , M ) E ( C , M ) E ( P , C , M )       
this is a "demographic" effect E(P) equal to the variation between dates 1 and 2 (where all the other variables have no incidence) of the number of people in each age-group, dependent upon ageing or deaths resulting from the two world wars. In the same way, there is a "motorisation growth" effect E(C) and a driver behaviour change effect E(M), which are respectively equal to:

E(P) = Pi 2Ci 1 Mi 1 i Pi 1Ci 1 Mi 1 i   E(C) = Pi 1Ci 2 Mi 1 i Pi 1Ci 1 Mi 1 i   E(M) = Pi 1Ci 1 Mi 2 i Pi 1Ci 1 Mi 1 i  
which are the three interaction effects of these factors taken two by two. Thus, for example E(P,C) represents the demography/motorisation interaction effect:

E(P,C) = ( Pi 1Ci 1 Mi 1 i )( Pi 2Ci 2 Mi 1 i ) ( Pi 2Ci 1 Mi 1 )( Pi 1Ci 2 Mi 1 ) i i     E(P,M) = ( Pi 1Ci 1 Mi 1 i )( Pi 2Ci 1 Mi 2 i ) ( Pi 2Ci 1 Mi 1 )( Pi 1Ci 1 Mi 2 ) i i     E(C,M) = ( Pi 1Ci 1 Mi 1 i )( Pi 1Ci 2 Mi 2 i ) ( Pi 1Ci 2 Mi 1 )( Pi 1Ci 1 Mi 2 ) i i    
and, lastly, the interaction of the three factors taken simultaneously:

E(P,C,M) = ( Pi 2Ci 2 Mi 2 i )( Pi 2Ci 1 Mi 1 i ) ( Pi 2Ci 2 Mi 1 )( Pi 2Ci 1 Mi 2 ) i i ( Pi 1Ci 2 Mi 1 i )( Pi 1Ci 1 Mi 2 i ) ( Pi 1Ci 2 Mi 2 )( Pi 1Ci 1 Mi 1 ) i i        
The interaction effects take into account the fact that the evolution in the number of trips is not only equal to the product of the pure factors, since the effects of variation of composition are taken into consideration as well. But the analysis shows that these interaction effects are quite unimportant, compared to the E(P), E(C) and E(M) effects.

These calculations were carried out between the 1978 and 1985 surveys on the one hand, and between the 1985 and 1992 surveys on the other hand -with the same division into age groups as those presented in the above figures. Furthermore, because of the considerable behaviour differences noted between men and women, these calculations have been carried out for both sexes. Finally, we studied separately, on the one hand the population of people of sixty and over and on the other hand people aged from 39 to 59, according to sex. The results indicating the importance of the principal effects in overall evolution are presented in Table 1 (for people between 60 and 66) and in Table 2 (for 39-59 years-old). The first result is the preponderance of the evolution of the motorisation and licence-holder rates in the overall evolution, compared with the demographic effect or the behaviour change effect. The evolution in the use of the car by "licence-holders" is greater between 1985 and 1992 for the sixties and over, especially as far as women are concerned. Furthermore, the interaction effects are somewhat limited, and the product of the three simple effects is close to the overall evolution. The only exception is for women of 39 to 59 between 1985 and 1992, for whom the combined effects are also important: demography/motorisation and demography/behaviour. These combined effects no doubt come from the drop in the size of age-groups during the second world war for whom motorisation and use progress less than in the other age-groups of forty-years-old.

Last but not least, these changes in the use of modes of transport are not only the reflection of increased motorisation, but even more so of more fundamental changes in life styles. These complex ways of life cannot be fully understood as a result of the household surveys which we have analysed. However, the activities which give rise to trips and which have been listed in the various surveys give us a certain number of indicators about the evolution of life styles after sixty. Commuting almost completely disappears for new generations of 60 years-old. This is not surprising since it has been possible to go into retirement at 60 rather than 65 since 1982, and because of the development of forms of pre-retirement. The second lesson concerns the evolution of leisure-and visit-linked trips as opposed to shopping trips. The new generations of elderly people are more and more inclined to group their purchases in hypermarkets rather than use nearby stores. This evolution is made easier by greater motorisation, which actually reinforces it.

CONCLUSION

What prospective lessons for the next twenty years is it therefore possible to get from these modal evolutions in travel behaviour of the elderly? The relationships between the social and economic environment on the one hand and transport demand on the other hand are multiple and complex, and it is wise to be very cautious. Moreover, the formalising of the different effects which we propose is simple and only concerns the use of the private car without going into its consequences on other transport modes. In order to be more explicative, it should notably take account of the behavioural differences of drivers according to the number of vehicles in the household, and distinguish between "young" and "old" retired people.

Unfortunately, the size of the samples limits the degree of breakdown which we can hope to obtain. However, this analysis shows that among the effects of age, generation and period, the first two are more obvious in both the past and present evolutions in car-driving. Among the present generations of elderly people, the major changes come from motorisation which increased with the renewal of the generations, especially as far as women are concerned. This rise in the level of motorisation will no doubt continue with the arrival of new generations of women going into retirement -the present level of motorisation of women of 40 to 60 bears witness to this. On the other hand, the growth of car ownership as far as men are concerned is not going to go on much longer. In licence-holder use of cars, the major changes over the next 20 years will come from women. This increased domination by the car is going to have an opposite effect on the other modes of transport, especially on walking and public transport.

However, what remains to be evaluated is the size of the effects of ageing, which could affect the importance of de-motorisation for the elderly. At the present moment, just like the results pointed out by Madre and [START_REF] Gallez | Le parc automobile dans les années 2000 : méthodes démographiques et projection à long terme[END_REF], the profiles per cohort show that no de-motorisation is visible for men before the age of 80. Women are less motorised already and the figures show that more of them abandon the use of the car. This evolution is only paradoxical in appearance, since this de-motorisation can often be explained by the decease of the husband who was the sole driver. The results presented by [START_REF] Jansson | Car demand modelling and forecasting: a new approach[END_REF] show that in the same way, in Sweden, de-motorisation is higher and starts earlier for women (from 70 onwards) than for men who keep on driving up till 75 at least. In the years to come more and more retired people are going to be two-car families. Are these couples going to give up one car? The reply to this question will enable us to have a better idea of the number of cars belonging to the elderly but also how easily elderly women are going to have access to a household car.

Other demographic, economic and social factors which are not easy to forecast will influence car ownership and modal choice for elderly people and will perturb the present trends.

From the demographic point of view, the future trends should logically show an ageing of the elderly population and a correlative increase in "older" elderly people to the detriment of "younger" elderly people. The continuing improvement in the state of health of elderly people may well cancel out this ageing effect. From an economic point of view, the financing of pensions and superannuation schemes is becoming more and more uncertain. But here again, the consequences may be variable -fall in income (which could have a depressive effect on car ownership), lengthening of active life (encouraging motorisation).

As far as society is concerned, future evolution of life styles of elderly people would seem to be just as difficult to forecast. The best we can do is to imagine certain trends, using present indicators: less-central place of residence, modification of the social composition and level of education of elderly people, more "active" retirement, for the first time, retirement for people who have only known the consumer and leisure society [START_REF] Dirn | La Société Française en Tendances[END_REF]. The future is, therefore, wide open.

Figure 1

 1 Figure 1 Comparative Evolutions in the Use of Modes of Transport for the Population as a Whole and for Elderly People a -Women of all ages b -Women of sixty and over

  Figure 2Reading Guide for Figures3 and 4

  Each cohort is logged by an interval of birth (7 years) and represented by the mean date of birth. The segments of the curve (profiles per cohort) enable us to follow the effects of ageing for each

  Figure 3 Evolution of the % of Potential Drivers for Each Cohort in Grenoble between 1978, 1985 and 1992 a -Men b -Women

  Figure 4 Evolution in the Number of Daily Car Trips for the Drivers in Each Cohort between 1978, 1985 and 1992 a -Men b -Women

Table 1 Breakdown of Car Driving Growth for Men and Women of 60 and Over

 1

	Men	Women
	1985/78 1992/85 1985/78 1992/85

Table 2 Breakdown of Car-Driving Growth for Men and Women of 39-59

 2

	Men	Women
	1985/78 1992/85 1985/78 1992/85

ii For each survey, approximately 4,000 individuals were polled on their travel behaviour during the previous day -between 400 and 700 over-sixties were thus surveyed each time.iii The Grenoble public transport network is old-people friendly (easy access to tramway, free travel outside peak hours).