Eduardo Fernández-Moral

Javier González-Jiménez

Patrick Rives

Vicente Arévalo

Extrinsic calibration of a set of range cameras in 5 seconds without pattern

The integration of several range cameras in a mobile platform is useful for applications in mobile robotics and autonomous vehicles that require a large field of view. This situation is increasingly interesting with the advent of low cost range cameras like those developed by Primesense. Calibrating such combination of sensors for any geometric configuration is a problem that has been recently solved through visual odometry (VO) and SLAM. However, this kind of solution is laborious to apply, requiring robust SLAM or VO in controlled environments. In this paper we propose a new uncomplicated technique for extrinsic calibration of range cameras that relies on finding and matching planes. The method that we present serves to calibrate two or more range cameras in an arbitrary configuration, requiring only to observe one plane from different viewpoints. The conditions to solve the problem are studied, and several practical examples are presented covering different geometric configurations, including an omnidirectional RGB-D sensor composed of 8 range cameras. The quality of this calibration is evaluated with several experiments that demonstrate an improvement of accuracy over design parameters, while providing a versatile solution that is extremely fast and easy to apply.

I. INTRODUCTION

The extrinsic calibration of different sensors is of very practical interest in robotics. This problem has been widely studied and different solutions have been presented for a variety of sensor configurations [START_REF] Zhang | Extrinsic calibration of a camera and laser range finder (improves camera calibration)[END_REF], [START_REF] Ha | Extrinsic calibration of a camera and laser range finder using a new calibration structure of a plane with a triangular hole[END_REF], [START_REF] Heng | Camodocal: Automatic intrinsic and extrinsic calibration of a rig with multiple generic cameras and odometry[END_REF], [START_REF] Schneider | Odometry-based online extrinsic sensor calibration[END_REF]. In this paper we address the problem of extrinsic calibration of range cameras. This problem has gained importance in the last years, with the arrival of both low cost range and range-intensity cameras. In this context, the available methods for extrinsic calibration present mainly two types of disadvantages: they have restrictions on the camera positioning (e.g. requirement of overlapping), or they rely on the tracking of the camera trajectory, which can be tedious to obtain, besides having issues of robustness and accuracy.

The disadvantages of previous calibration approaches were clear after the construction of a device for omnidirectional intensity and range image acquisition based on a rig of RGB-D cameras (figure 5) [START_REF] Gokhool | A Dense Map Building Approach from Spherical RGBD Images[END_REF]. This new sensor prompted in us the need of a robust and easy calibration method, since the accuracy of the parameters from the construction design were not satisfactory, and the solutions proposed in the literature were not suitable for our problem.

To put our work into context, we review first some relevant approaches to this problem. A classical strategy for extrinsic Fig. 1. A planar surface is observed by two range cameras rigidly joined from different positions. In this way, plane correspondences are captured from different orientations with respect to the rig's reference system to perform extrinsic calibration. camera calibration is through the detection and matching of control points that are detected in the overlapping regions of the different cameras [START_REF] Szeliski | Creating full view panoramic image mosaics and environment maps[END_REF]. However, the overlap requirement constitutes a very strong constraint. Besides, even when some overlap exists, it is generally more complicated to match features in range images than in intensity images. With a different perspective, the use of a calibration pattern is a resource that has been employed as an ad hoc solution for very specific problems [START_REF] Ha | Extrinsic calibration of a camera and laser range finder using a new calibration structure of a plane with a triangular hole[END_REF], [START_REF] Moreno | An instrumented vehicle for efficient and accurate 3d mapping of roads[END_REF]. The lack of generality of this solution for any configuration of cameras is indeed an important limitation. Plus the need to create the 3D calibration pattern itself is wearisome.

A more general approach which does not depend on the camera set-up is based on ego-motion to match the camera trajectories, which are tracked independently. For that, simultaneous localization and mapping (SLAM) or visual odometry (VO) techniques are applied [START_REF] Brookshire | Extrinsic calibration from per-sensor egomotion[END_REF], [START_REF] Heng | Camodocal: Automatic intrinsic and extrinsic calibration of a rig with multiple generic cameras and odometry[END_REF], [START_REF] Schneider | Odometry-based online extrinsic sensor calibration[END_REF]. Such approaches rely on the SLAM or VO robustness, which depends highly on the environment, especially for rangeonly cameras. Besides, obtaining a useful trajectory is far more tedious and inconvenient than taking a few images from different positions as the technique we propose here.

Concretely, we present a new method for extrinsic calibration of range cameras (including RGB-D cameras) that avoids the above-mentioned problems. Our method relies on matching planes that can be observed simultaneously from different cameras. For that, only one plane has to be observed from different camera locations. This approach has several advantages as the calibration can be performed very quickly and robustly, it does not require any calibration pattern but a single plane from the environment (the floor, the ceiling, a wall, ...), and supervision is not required. In this work, we test the performance of the method by calibrating two typical configurations of range cameras, demonstrating very satisfactory results in all the cases.

In the following we give the details of our calibration approach, the segmentation and parameterization of the planes and their matching. The observability of the problem is studied next. Then, the equations for extrinsic calibration are derived for a pair of cameras (section IV) and for an arbitrary number of cameras (section VI). For both cases, calibration results for different camera configurations are presented. Finally, the conclusions are outlined.

II. CALIBRATION APPROACH

The problem that we address in this paper is that of finding the extrinsic calibration (i.e. relative poses) between several "a-priori" non overlapping range cameras. We propose to solve this problem by matching planar features that are seen from different viewpoints. Thus, we take advantage of the fact that structured environments contain large planes (e.g. the floor, walls, ceiling) that can be reliably observed by the different sensors simultaneously. We make use of such planes to establish correspondences, see figure 1. With this strategy we avoid the need of creating an specific calibration pattern for the sensor set-up. Also, no SLAM neither odometry are needed, avoiding robustness issues and making the procedure much more accessible and easy to use.

Before addressing the extrinsic calibration itself, related issues like the intrinsic calibration of the range cameras, and the plane segmentation, parameterization and matching are briefly described next.

A. Intrinsic model of the range cameras

Measurements from range cameras are affected by noise, which can be classified in two types of errors: in accuracy (variance) and also a bias or correctness (mean error). It has been reported elsewhere [START_REF] Khoshelham | Accuracy and resolution of kinect depth data for indoor mapping applications[END_REF] that the depth error variance as well as the bias of structure-light sensors from PrimeSense (including Kinect and Asus Xtion) increases with distance. Such bias is quite evident when we see the deformation of a flat surface as it is observed from increasing distance. This intrinsic error is studied in [START_REF] Teichman | Unsupervised intrinsic calibration of depth sensors via slam[END_REF], where the authors propose to model the intrinsic parameters using a discrete image of multipliers to update every pixel depending on its depth. An implementation of that work, which relies on a cutting edge SLAM solution [START_REF] Kerl | Dense visual slam for rgbd cameras[END_REF] is publicly available1 . This correction has been applied to the Asus XPL sensors employed here. Thus, in the rest of this paper we will assume that they are only affected by unbiased, uncorrelated Gaussian noise.

B. Plane segmentation and parameterization

In order to obtain planes (planar patches to be precise), the depth images are segmented with a region growing approach [START_REF] Holz | Fast range image segmentation and smoothing using approximate surface reconstruction and region growing[END_REF]. This technique is used here due to its efficiency to segment organized images, however other methods for plane segmentation can be used equally [START_REF] Zuliani | The multiransac algorithm and its application to detect planar homographies[END_REF], [START_REF] Borrmann | The 3d hough transform for plane detection in point clouds: A review and a new accumulator design[END_REF].

A planar patch is represented by its normal vector n, with n = 1, and the distance d to the optical center of the camera. In this way, a point p lying on the plane fulfills the equation n

• p + d = 0 (1)
This overparameterization is very convenient for the formulation of the calibration errors in the next sections.

The plane parameters and their covariances are estimated following [START_REF] Poppinga | Fast plane detection and polygonalization in noisy 3d range images[END_REF], assuming accurate directions of measurements m i , where the noise only affects the range measurements ρ i . After the intrinsic calibration has been performed, we can assume that ρ i ∼ N( ρi , σ i ), where ρi = d/n • m i is the true range of the i-th measurement. The standard deviation σ i is generally a function that depends on the range ρ i and on the incidence angle σ (ρ i , n • m i ). However, in this work we make the same simplification as in [START_REF] Poppinga | Fast plane detection and polygonalization in noisy 3d range images[END_REF] to assume the standard deviation σ i independent on {n, d}, and estimate σ i in a conservative way: σ (ρ i , n • m i ) < σ . From this simplification the plane parameters and their covariances can be analytically defined. Thus, the optimal n * is the eigenvector corresponding to the smallest eigenvalue of the matrix

M = N ∑ i=1 (r i -r G )(r i -r G ) T (2)
where r G = 1 N ∑ N i=1 r i is the gravity center of the plane pixels. The optimal d * is given by

d * = n * r G (3)
and the covariance of the plane parameters Σ * = (H) + is calculated as the Moore-Penrose generalized inverse of

H = 1 σ 2 N ∑ i=1 r i r T i -r i -r T i 1 (4)
The simplification of considering constant variance (i.i.d.) assumed above can be substituted for a more realistic model [START_REF] Pathak | Uncertainty analysis for optimum plane extraction from noisy 3d range-sensor point-clouds[END_REF] to obtain more accurate results. But this requires a complex numeric calculation of the plane parameters and their covariances, which is out of the scope of this paper.

C. Obtaining plane correspondences

To establish the plane correspondences, a rough guess of the camera relative poses is provided by the user. Then, plane correspondences are established between each pair of sensors (if more than two are being calibrated) applying some simple heuristics to constraint their geometric consistency, namely: a) the angle between the normal vectors of both planar regions is smaller than a threshold; b) the distances from both planes to the camera center are under a threshold; and c) both regions are large enough (in our implementation: the number of pixels in each region is bigger than 20% of the image pixels). Note that giving an initial estimation for the relative position of the cameras is an easy and straightforward way to facilitate the matching of plane observations, though other plane matching strategies can be applied if we want to avoid the need of this initial estimate [START_REF] Pathak | Fast registration based on noisy planes with unknown correspondences for 3-d mapping[END_REF], [START_REF] Fernández-Moral | Fast place recognition with plane-based maps[END_REF].

The process for gathering correspondences is performed automatically while the camera rig is moving until the problem is well conditioned according to the Fisher Information Matrix, as explained in section III. For that, having a large number of correspondences contributes to reduce the error in calibration due to sensor noise. Also, to be robust against possible outliers, after enough correspondences have been gathered, a RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF] process is launched to detect and discard possible outliers.

The range cameras synchronization effect is neglected in this work since the images are captured at a minimum frame rate of 30 Hz, and the camera rigs are never moved abruptly.

D. RANSAC outlier rejection

The set of plane correspondences obtained is cleaned up of outliers by running RANSAC. This procedure is carried out in two steps: first, the outliers showing a large error in the orientation are discarded, and second, those outliers in distance are removed (this order is chosen since the noise in the orientation of the normal vectors is typically smaller than that in the plane position). The relative poses between the pair of cameras are calculated from a sample of 3 nondegenerate plane correspondences (section III). The models used by the two RANSAC processes are defined in section IV.

III. OBSERVABILITY

It can be seen that each plane correspondence imposes three new constraints between the pair of sensors: two for the relative rotation and one for the relative translation. Thus, we need at least 3 measurements from linearly independent plane observations (i.e the normal vectors of the planes are linearly independent) to compute the relative position of a pair of sensors (only two measurements are needed to compute the rotation), and a minimum of 3(N -1) correspondences to calibrate a rig with N sensors. An example to get insight into this is by considering that we have a single sensor observing the corner of a room. The observation of the three perpendicular planes gives us enough information to localize the camera and its relative motion with respect to a previous pose. In analogy, the relative pose between two cameras can be obtained if they observe 3 plane correspondences with linearly independent normal vectors (either observed from one view (fig. 2) or several ones (fig. 1)). The most simple and convenient procedure would be to take a short sequence of several images (in motion) of one big plane from different orientations of the rig (see the video attached).

In order to detect the degenerate cases for which the calibration cannot be calculated we evaluate the Fisher Information Matrix (FIM) for the parameters of the maximum likelihood estimator (MLE) of the calibration, which is presented in the following section. As we will see, the probability of the MLE is given by an unbiased Gaussian distribution (this assumption is realistic only after intrinsic correction). For this estimator (called efficient [START_REF] Fernández-Madrigal | Simultaneous Localization and Mapping for Mobile Robots: Introduction and Methods[END_REF]), the FIM coincides with the Hessian of the least squares problem resulting from the MLE, and its inverse is the covariance of the resulting calibration (Cramér-Rao [START_REF] Fernández-Madrigal | Simultaneous Localization and Mapping for Mobile Robots: Introduction and Methods[END_REF]).

When the FIM is singular, the information provided is not sufficient and the MLE does not exist. For a pair of cameras, it can be verified that when the FIM is not singular, then

rank( N ∑ i=1 n i n T i ) = 3 (5)
where n i is the normal vector of the plane i as seen from one of the cameras in the pair.

The ratio η = µ 3 /µ 1 between the smallest and largest eigenvalues of the matrix from eq. 5 is also an indicator of how well distributed the measurements are along the different directions of the space. So, in the best case η = 1 which means that all plane observations are equally distributed in the space, while when η → 0, the system is ill conditioned.

From our experiments, we have verified that the covariance of both the rotation and the translation estimations decrease asymptotically as the number of plane correspondences increases. The covariance is used as the condition to control the calibration convergence, and hence, to stop gathering plane correspondences. In our tests, we stop this calibration when the maximum eigenvalue of the covariance is under 10 -3 , which has shown to be a good compromise between accuracy and effort to obtain plane correspondences.

IV. EXTRINSIC CALIBRATION OF A PAIR OF RANGE CAMERAS

A. Problem statement

Given a set of plane correspondences gathered from two rigidly joint range cameras C and C ′ , where the camera C represents the system of reference, and C ′ is located with a relative transformation [R|t] ∈ SE(3) with respect to C, where the rotation R ∈ SO(3) is represented with a 3 × 3 matrix and the translation t ∈ R 3 . Provided that the correspondences fulfill the observability condition (concretely the one represented by eq. 5), we want to estimate the optimal [R|t] assuming that the measurements are affected by unbiased Gaussian noise as modelled in II-B. This problem can be divided into two separate ones since the rotation and the translation restrictions are decoupled.

B. Solving for the rotation

The maximum likelihood estimation (MLE) of the relative rotation R is given by the maximization of the log-likelihood

argmax R ln N ∏ i=1 p(n i , n ′ i |R) (6)
for N plane correspondences, where the likelihood of the rotation for the i-th correspondence is expressed as

p(n i , n ′ i |R) = 1 (2π) 3 |Σ i | exp - 1 2 (n i -Rn ′ i ) T Σ -1 i (n i -Rn ′ i ) (7)
being n i and n ′ i the observed normal vectors from the plane i as seen by the cameras C and C ′ respectively; R is the rotation matrix in SO(3), and Σ i is the 3 × 3 covariance block corresponding to the normal vector of the plane correspondence (calculated from the fusion of both observations [START_REF] Pathak | Uncertainty analysis for optimum plane extraction from noisy 3d range-sensor point-clouds[END_REF]). Considering independent errors of the plane correspondences, the derivation of this MLE coincides with the solution of the least squares problem expressed as

argmin R N ∑ i=1 ω i n i -Rn ′ i 2 (8)
where ω i is the weight of the plane correspondence

ω i = 1 |Σ i | (9)
This problem is similar to the one of estimating the rotation of a registered set of 3D points [START_REF] Arun | Least-squares fitting of two 3-d point sets[END_REF]. Thus, employing the same procedure, the above equation can be expressed as

R = argmin R N ∑ i=1 ω i n T i n i -2 N ∑ i=1 ω i n T i Rn ′ i + N ∑ i=1 ω i n ′T i n ′ i = argmin R -2 N ∑ i=1 ω i n T i Rn ′ i = argmax R N ∑ i=1 ω i n T i Rn ′ i ( 10
)
that can be denoted as

N ∑ i=1 ω i n ′T i Rn i = tr(WY T RX) ( 11
)
where tr(•) represents the trace of a square matrix; W = diag(ω 1 , ..., ω n ) is an n × n diagonal matrix containing the weights ω i ; and Y and X are 3 × n matrices with the normal vectors n ′ i and n i as their columns, respectively. This problem is solved with singular value decomposition (SVD) over the 3 × 3 covariance matrix

S = XWY T (12)
From the singular value decomposition S = UΣV T , the rotation is obtained as

R = V 1 0 0 0 1 0 0 0 det(VU T ) A U T ( 13
)
Cases of study where the matrix A is used to convert the degenerate case of a reflection (det(VU T ) = -1) into a valid rotation in SO(3).

For further details on the mathematics, please refer to [START_REF] Arun | Least-squares fitting of two 3-d point sets[END_REF], [START_REF] Sorkine | Least-squares rigid motion using svd[END_REF].

C. Solving for the translation

The MLE of the translation is obtained by maximizing the log-likelihood associated to the probability

p(n i , n ′ i , d i , d ′ i |t) = 1 √ 2πσ i exp - 1 2 (d i -d ′ i + n i • t) 2 σ 2 i ( 14
)
where d i and d ′ i are the observed distances from the plane i to the optical centers of the depth cameras C and C ′ respectively, σ 2 i is the error variance, and t is the relative translation we are looking for. This is equivalent to the least squares problem

argmin t N ∑ i=1 ω i (d i -d ′ i + t • n i ) 2 (15)
with the weight given by ω i = 1/σ 2 i . This has a closed form solution given by

t = -H -1 g ( 16
)
where H and g are the Hessian and the Gradient of the error function respectively, which are calculated as

H = N ∑ i=1 J T i W i J i , g = N ∑ i=1 J T i W i r i ( 17
)
where the Jacobians, the weights and the residuals are calculated from

J i = n T i , W i = 1 σ 2 i , r i = d i -d ′ i ( 18
)
D. Practical study cases

Adjacent cameras

This case is interesting to provide a larger field of view of the scene, being specially practical for low cost sensors like Asus Xtion (see figure 3.a). This case serves us to illustrate the conditioning of the problem, and so to show different possibilities for calibration. One of this situations is the calibration of the pair from one single observation, i.e. without moving the rig. This is only possible if three planar patches whose normal vectors span through the different directions of the space are visible at the same time by both cameras. This case can be easily set-up, as the example shown in figure 2.

In practice, however, it is even more convenient to take several images from different orientations pointing to one single plane (the floor, for example), since we can gather more quickly enough plane correspondences that help to reduce the error from the measurement noise. This may not take longer than 2 or 3 seconds.

In table I we show an example of how the average residual error is reduced when raising the number of plane correspondences. The alignment errors in rotation and translation are measured in a dataset containing 2K correct plane correspondences for the five calibrations, the plane correspondences were taken in all directions of the space.

Cameras in opposite directions

This case is interesting, for instance, for vehicles that need to observe the scene forward and backward. We address this case here also since it probably represents the most challenging case to obtain plane correspondences in different directions (notice that the further the viewing directions of the cameras are, the more difficult is to find plane correspondences). Figure 3.b shows how the plane correspondences can still be obtained to add constraints in the different directions of the space, for example, by rotating the camera rig. Calibration was performed automatically while the user waved the camera near the floor. After 5 seconds from the start of the experiment, the calibration finishes with 29 plane correspondences, see the attached video. In this case the deviation with respect to the rig parameters is less than 1 deg for the rotation, and in the order of millimeters for the translation.

Sensors of different types

Though most of our experiments are carried out with structured light Primesense cameras, other range sensors can also be calibrated with our method. Concretely, a time-of-flight camera and a Kinect sensor mounted on a robot are calibrated by moving the robot (figure 4, left) around to gather plane correspondences. The errors in the plane observations from both sensors will follow different distributions, so that they are weighted accordingly as said in section II-B.

V. EXTRINSIC CALIBRATION OF AN ARBITRARY NUMBER OF RANGE CAMERAS

This section extends the previous formulation for an arbitrary number M of range cameras. Note that for the case when there are no loop closures between the sensors, i.e. there is only one possible way to correlate the relative pose of any pair of sensors. The extrinsic calibration can be calculated as in the previous section by estimating the relative pose between each pair of adjacent sensors, and performing pose composition to place them in a common reference. Instead, this section is dedicated to the particular case in which there are plane correspondences that create loop closures between sensors. For the sake of space, we present directly the least squares equations, which as in the previous section, derive from the ML estimation.

A. Solving for the rotation

The relative rotation between the different sensors can be formulated as

argmin [ ✚ ✚ R 1 R 2 ...R M ] M ∑ j=1 M ∑ k= j+1 N ∑ i=1 λ i ( j, k)ω i ( j, k) R j n j i -R k n k i 2 ( 19
)
where j and k are indices of the M sensors and i is the index of each one of the N planes observed; λ i ( j, k) is a binary variable that equals 1 when the plane i is observed by sensors j and k, being 0 otherwise; n j i and n k i are the normal vectors of the plane i observed from sensors j and k, respectively; and the rotation of each sensor is represented by R 1 , R 2 ...R M ∈ SO [START_REF] Heng | Camodocal: Automatic intrinsic and extrinsic calibration of a rig with multiple generic cameras and odometry[END_REF], where the rotation R 1 has been arbitrarily fixed to the identity I 3 to choose a system of reference. This least squares system has a different structure from the one in the previous section, that can not be solved with the strategy used from equations 10 to 13. Thus, we rewrite the problem to represent the relative rotations in minimal parameterization with the exponential map from Lie algebra [START_REF] Blanco | A tutorial on se(3) transformation parameterizations and on-manifold optimization[END_REF] argmin

µ 2 ...µ M M ∑ j=1 M ∑ k= j+1 N ∑ i=1 λ i ( j, k)ω i ( j, k) e µ j R j n j i -e µ k R k n k i 2 ( 20
) where e µ j is the exponential map of the increment of rotation µ j on the rotation R j , which is a 3D vector on a manifold space of SO(3), and similarly for e µ k . This is a non-linear least squares system that is solved iteratively with Gauss-Newton using equations 16-17, where the Jacobian and the vector of residuals are given by

J i = [0 ... 0 J ( j) i 0 ... 0 J (k) i 0 ... 0] J ( j) i = skew(n j i ) , J (k) i = skew(-n k i ) (21)
thus, the Hessian H and the gradient g are calculated incrementally as

H = N ∑ i=1 H i , g = N ∑ i=1 g i ( 22
)
which have the form

H i =        J jT i ω i J j i J kT i ω i J j i . . . J jT i ω i J k i J kT i ω i J k i        , g i =        J jT i ω i r i . . . J kT i ω i r i        (23)

B. Solving for the translation

The generalization of the translation equation system keeps the same structure as in the case of a pair of cameras

argmin [ ✁ t 1 t 2 ...t M ] M ∑ j=1 M ∑ k= j+1 N ∑ i=1 λ i ( j, k)ω i ( j, k)(d j i -d k i -t j R j n j i +t k R k n k i ) 2
(24) and it is solved in the same way (note that in this case the rotation must be solved first).

VI. CALIBRATION OF A RIG FOR OMNIDIRECTIONAL IMAGE ACQUISITION

We have designed a camera rig for omnidirectional RGB-D acquisition which comprises 8 Asus Xtion Pro Live (Asus XPL) sensors mounted in a radial configuration (see figure 5). This device motivated at the origin the work described in this paper, since the parameters from the construction design were not accurate for our application. Existing calibration approaches like those based on SLAM [START_REF] Brookshire | Extrinsic calibration from per-sensor egomotion[END_REF] are very time consuming and impose important restrictions on the trajectory, since planar movement (as we have in our robot) is a degenerate case where calibration cannot be achieved. Thus, we employed the calibration method described in the previous section, which was applied on a sequence of images taken with the robot (planar movement is not a degenerate case in our approach).

The relative positions between the RGB cameras is the same as these between their corresponding depth cameras for our sensor configuration. Therefore, both RGB and depth omnidirectional images can be built, see figure 6. The 3D point cloud can be also built from such images, figure 7.

The precision of calibration is tested with an experiment where the robot moves in a small circular trajectory (∅ ∼ 0.5 m) in the center of a room, taking 200 images. In table II, the average residual in orientation and translation for the plane correspondences of these images is presented for different extrinsic calibrations: design parameters (no extrinsic calibration) with and without intrinsic correction, and the extrinsic calibration also with and without intrinsic correction. The ICP residual of the alignment of the spherical point clouds from these images is also shown. For all the cases, the combination of intrinsic and extrinsic calibration offers the best results. The method relies on the matching of plane observations from the different sensors. No constraints are put on the position of the cameras, where the only requirement for the system is that there is a planar surface that can be observed simultaneously. The observability conditions are analyzed, and a solution is presented based on MLE. With our method, performing calibration becomes very fast and easy for the user, avoiding problems of previous solutions which rely either on calibration patterns or trajectory estimation methods. The method has been tested for different configurations of cameras, including a camera rig designed for omnidirectional image acquisition. All the experiments have validated the claimed features of our proposal.

Fig. 2 .

 2 Fig. 2. A particular set-up from which we can calibrate the cameras with a single observation. The planar patches on the left and right are those extracted from the two cameras.

Fig. 3 .

 3 Fig. 3. Different sensor configurations with a pair of cameras: a) Adjacent cameras, b) Opposite cameras.

Fig. 4 .

 4 Fig. 4. Robots which mount rigs of range and RGB-D cameras.

Fig. 5 .

 5 Fig. 5. Omnidirectional RGB-D camera rig.

Fig. 6 .

 6 Fig. 6. Omnidirectional RGB and depth images acquired by our RGB-D camera rig.

Fig. 7 .

 7 Fig. 7. Point cloud obtained from the reconstructed omnidirectional RGB-D image.

TABLE II RESIDUAL

 II ERRORS FOR DIFFERENT COMBINATIONS OF INTRINSIC ANDEXTRINSIC CALIBRATIONS. for calibrating the extrinsic parameters of range camera rigs has been presented in this paper.

	Calib / Error type	Res. rot (deg)	Res. trans (cm) Res ICP (cm)
	Design Specs	3.17	3.0	0.49
	Design S.+Intrinsic	2.95	3.1	0.45
	Extrinsic calib	1.78	2.9	0.34
	Extrinsic+Intrinsic	1.60	2.5	0.29
		VII. CONCLUSIONS
	A new methodology

Mapir Group. Universidad de Málaga. E.T.S. Ingeniería de Informática-Telecomunicación. Campus de Teatinos,

29071, Málaga, Spain. E-mail: eduardofernandez@uma.es 2 Lagadic team. INRIA Sophia Antipolis -Méditerranée. 2004 route des Lucioles -BP 93, 06902 Sophia Antipolis, France.

http://cs.stanford.edu/people/teichman/octo/clams/


Romain Drouilly

Patrick Rives

Benoit Morisset

Fast Hybrid Relocation in Large Scale Metric-Topologic-Semantic Map

Navigation in large scale environments is challenging because it requires accurate local map and global relocation ability. We present a new hybrid metric-topological-semantic map structure, called MTS-map, that allows a fine metric-based navigation and fast coarse query-based localisation. It consists of local sub-maps connected through two topological layers at metric and semantic levels. Semantic information is used to build concise local graph-based descriptions of sub-maps. We propose a robust and efficient algorithm that relies on MTS-map structure and semantic description of sub-maps to relocate very fast. We combine the discriminative power of semantics with the robustness of an interpretation tree to compare the graphs very fast and outperform state-of-the-art-techniques. The proposed approach is tested on a challenging dataset composed of more than 13000 real world images where we demonstrate the ability to relocate within 0.12ms.

I. INTRODUCTION

Although it has been largely studied in the last decade, autonomous navigation remains a challenging issue, particularly in complex large scale environments. In this paper we address the problem of building navigation-oriented maps capable of dealing with different localization levels, from coarse to fine. Map-based navigation requires the robot to be able to request efficiently the content of the map at large scale to retrieve its position and simultaneously to infer the position of local objects around it. The map needs to be precise locally but lightweight at large scale. However in most of 3D maps, information density is homogeneous in space yielding to a compromise between precision of local model and size of the environment to model. This kind of representation intrinsically limits local quality of the model or reduces its scale-up capability. In this work, we use a more convenient map structure. It consists of a graph whose nodes are local sub-maps built from ego-centred spherical views of the environment, previously introduced in [START_REF] Meilland | A spherical robot-centered representation for urban navigation[END_REF].

Navigation is fuirther a product of environment understanding and planning, besides local metrical precision. A map is a cognitive representation of the world and the robot is able to reason only about concepts encoded within it. The more complex are these concepts the more "intelligent" could be its behaviour. Therefore intelligent navigation needs the map to contain abstraction layers to represent higher level concepts than geometry and color. Toward this goal topological mapping has early been considered of interest [START_REF] Dudek | Robotic exploration as graph construction[END_REF], [START_REF] Kuipers | A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations[END_REF], capturing the environment accessibility properties and allowing navigation in complex large scale environments *This work was supported by ECA Robotics 1 Authors are with INRIA Sophia-Antipolis, France romain.drouilly@inria.fr, patrick.rives@inria.fr 2 Authors are with ECA Robotics, bmo@eca.fr [START_REF] Chapoulie | Appearance-based segmentation of indoors/outdoors sequences of spherical views[END_REF]. Semantic mapping is only recently receiving significant attention. It provides a powerful way to enrich the cognitive model of the world and thereby being of interest for navigation. However, despite a notable amount of work about outdoor scene parsing, the use of semantics for outdoor navigation has been poorly studied. Many mapping strategies rely on place classification or landmarks like doors to infer robot's position [START_REF] Pronobis | Large-scale semantic mapping and reasoning with heterogeneous modalities[END_REF]. But localisation is only possible if object classes are strongly related to particular places, which is not the case outdoors. Additionally the place concept is hard to define for most of outdoor environments as these scenes are not structured enough to allow unambiguous delimitations between different areas.

We propose three main contributions to deal with those problems: a new 3D hybrid map structure designed for navigation purposes, a new framework to extract semantic information and an efficient algorithm to request the content of the map in a human-friendly way. All these improvements provide the robot both with precise local representation and fast global content request ability.

The rest of this paper is organized as follows: related works for space modelling and relocation in large databases are discussed in section II, MTS-map architecture is presented in section III followed by scene parsing results. Then the content request problem is treated in section IV before wrapping up with experimental results in section V and conclusion in section VI.

II. RELATED WORK

A. Hybrid mapping

Semantic mapping is an active research domain for the last years and many semantic representations exist in the literature. A semantic map model has been proposed in [START_REF] Vasudevan | Bayesian space conceptualization and place classification for semantic maps in mobile robotics[END_REF] where objects are grouped along two dimensions -semantic and spatial. Objects clustering along semantic dimension allows to capture place label where place is defined as group of objects. Grouping objects in clusters of increasing size provides meaning to the global scene. A multi-layers map is proposed in [START_REF] Mozos | From labels to semantics: An integrated system for conceptual spatial representations of indoor environments for mobile robots[END_REF]. It is constructed in a semi-supervised way. The first three levels are composed of metric, navigation and topological maps. The last level is the semantic map that integrates acquired, asserted inferred and innate conceptualontological knowledge. A 3D extension of the well-known constellation model is presented in [START_REF] Ranganathan | Semantic modeling of places using objects[END_REF]. Here again object is the basic unit of representation for semantic labelling of place. Despite their interest these approaches are difficult to adapt to outdoor environments because they rely on the concept of place that is not well defined outdoors. Other methods do not directly rely on this concept. The 3D semantic map presented in [START_REF] Nüchter | Towards semantic maps for mobile robots[END_REF] is defined as a map containing both metric information and labels of recognised classes. Prior knowledge and object models are needed for scene interpretation and object recognition. More recently [START_REF] Salas-Moreno | Slam++: Simultaneous localisation and mapping at the level of objects[END_REF] define a semantic SLAM approach that allows to build a map based on previously known object models. If they perform well indoors these works are not easily transferrable to outdoor environments. These models rely on object recognition and require to have a model of every object which is not easily tractable in large scale environments.

B. Content Request

Relocation can be formulated as a content request problem: given the current observation, we ask the database to provide the corresponding position. Vision-based localization is studied for a long time and the use of omni-images dates back to early 90's [START_REF] Yagi | Map-based navigation for a mobile robot with omnidirectional image sensor copis[END_REF]. Most of the modern techniques decompose to three steps: first, interest points are extracted and descriptors computed. Then descriptors between two images are matched. Finally outliers are rejected. In well-known Bag-Of-Words (BoW) methods, tree structure is commonly used to organize the search and speed up the comparison process. Many variations of BoW algorithm exist. We may cite [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] that uses feature context to improve their discriminant power. The idea is to select good features candidates to match in order to avoid perceptual aliasing. Other recent BoW methods offer good performances in image retrieval using different strategies. A tree structured Bayesian network is used in [START_REF] Cummins | Highly scalable appearance-only SLAM -FAB-MAP 2.0[END_REF] to capture words co-occurrence in images. A compact vocabulary is created in [START_REF] Galvez-Lopez | Bags of binary words for fast place recognition in image sequences[END_REF] through discretization of a binary descriptor space. Despite undeniable efficiency, these algorithms have the drawback of providing a low-level description of the scene which is not human-friendly and makes it useless for human-robot cooperation.

III. HYBRID METRIC-TOPOLOGICAL-SEMANTIC MAP ARCHITECTURE

In this section, we propose a new hybrid metrictopological-semantic map structure called MTS map. The map architecture is detailed below and illustrated in fig1.

A. Map Architecture

MTS-map consists of 3-layered local sub-maps globally connected to each other in a graph structure through the use of a dense visual odometry method, first introduced in [START_REF] Meilland | A spherical robot-centered representation for urban navigation[END_REF]. The bottom layer of each sub-map is an ego-centred RGBD spherical view of the environment acquired with a multi-cameras system [START_REF] Meilland | Dense visual mapping of large scale environments for real-time localisation[END_REF]. As close as possible to sensor measurements, it provides a realistic representation of the local environment. The second layer presents a first level of abstraction with densely labelled spherical images, the "label layer". There is a direct correspondence between pixels of these two layers. At the upper stage lies the semantic-graph layer G o which provides a compact and robust high-level description of the viewpoint. Nodes are the different regions semantically consistent in the labelled image and edges represent the connection between these regions. A label is attached to every node together with the size of the area, measured in pixels and its eccentricity represented by ratio of length and the width of the shape. Edges are weighted by the number of neighbouring pixels of two objects. All these layers constitute the RGBDL sphere, where "L" stands for Label. At the global scale every RGBDL sphere is globally referenced in a tree structure that clusters spheres according to class presence and class occurrence. Finally, atop of all sub-maps is the conceptual layer, defined as a nonspatial map which characterizes strength of relations between classes, generalized from G o graphs.

B. Scene Parsing

In this part we propose a framework to extract semantic information from spherical images. It should be noted that our work consists of separated building blocks and the localization step is independent of the algorithm used to label images.

1) Local Features and Random Forest Classification:

The first step of the classification process uses Random Forest (RF) [START_REF] Geurts | Extremely randomized trees[END_REF] to estimate classes distribution. A Random Forest is a set of T Decision Trees that achieves good classification rate by averaging prediction over all leaves L of all trees:

P(c|L) = 1 T T ∑ i=1 P(c|l i )
The model construction complexity is approximately of O(T (mn log(n)) where n is the number of instances in the training data, m the vectors size. Provided they are correctly trained, RF has comparable performance with multi-class SVM with a reduced training and testing costs [START_REF] Bosch | Image classification using random forests and ferns[END_REF] that make them popular in computer vision. Moreover Random Forest has deeper architecture than Decision Tree or other wellknown classification algorithm which makes it better able to generalize to variations not encountered in the training data [START_REF] Bengio | 1 learning deep architectures for ai[END_REF].

Each Decision Tree is trained on a reduced subset of input data randomly chosen with replacement. Then each node is split using the best split among a subset of variables randomly chosen. The Decision Tree produces prediction by recursively branching left or right at each node until a leaf is reached. Due to classes imbalance in input data, prior preference for some classes can affect results. For that reason we weigh each training sample proportionally to the inverse class frequency.

To achieve good robustness to changes in orientation and scale, the feature vectors use SIFT descriptor computed densely on the gray scale image and augmented with color information computed on normalized RGB images.

2) Spatio-Temporal consistency with CRF: Random Forest produces accurate results but fails to catch contextual information at large scale. To capture global structure of the scene a common solution is to embed first stage prediction results into a probabilistic graphical model [START_REF] Pronobis | Large-scale semantic mapping and reasoning with heterogeneous modalities[END_REF].

However applying classifier on single images results in practice in twinkling classification. To enforce temporal consistency large graphical can be built among consecutive images to propagate labels [START_REF] Xiao | Multiple view semantic segmentation for street view images[END_REF] and [START_REF] Wojek | A dynamic conditional random field model for joint labeling of object and scene classes[END_REF]. The drawback of these methods is the complexity of the graph that can reach billions of edges. Other methods [START_REF] Miksik | Efficient temporal consistency for streaming video scene analysis[END_REF] use optical flow to propagate labels but need to previously learn similarity between pixels.

In this section, we present a way to simultaneously embed in the CRF the temporal and spatial context without the need to increase the number of edges in the CRF. We use the CRF architecture and efficient MAP inference algorithm presented in [START_REF] Krhenbhl | Efficient inference in fully connected crfs with gaussian edge potentials[END_REF]. Fully connected pairwise CRF model is briefly reviewed here. Let X = {x 1 , ..., x n } and Y = {y 1 , ..., y m } be sets of random variables corresponding respectively to observations and labels. A CRF is an undirected graph G whose node correspond to X ∪ Y and that encodes a conditional distribution as follows:

P(Y |X) = 1 Z(X) exp{-∑ c∈C g φ c (Y c |X)}
with C g the cliques of G, φ c the induced potential and Z(X) a normalization factor.

In the fully connected pairwise CRF model the Gibbs energy [START_REF] Krhenbhl | Efficient inference in fully connected crfs with gaussian edge potentials[END_REF] of a labelling y is:

E(y) = ∑ i ψ u (y i ) + ∑ i< j ψ c (y i , y j )
where ψ c (y i ) denotes φ (y i |X), ψ u is the unary potential and ψ c the pairwise potential.

To enforce temporal consistency we accumulate Random Forest predictions from neighbours of the current view so that the unary potential ψ c (y i ) takes the form :

ψ u (y i ) = α ∑ n∈N ψ n (y i )
where N is the neighbourhood of sphere i and α is a normalization factor. Predictions are accumulated by projection of neighbours prediction on the current one using odometry.

C. Scene Parsing Results

We evaluate our labelling framework on two datasets: CamVid and our INRIA dataset. Due to the lack of other dataset providing panoramic RGBD images fully annotated, we first apply our algorithm frame by frame embedding only spatial information in the CRF. Then we study the temporal consistency improvement on our dataset. CRF parameters are tuned by 2fold cross-validation on CamVid and 5fold cross validation on INRIA dataset. All experiments were performed using an Intel i7-3840QM CPU at 2.80GHz. All programs are single-threaded.

a) INRIA Dataset: consists of more than 13000 high resolution 1 panoramic images taken along a 1.6km pathway in a outdoor environment with forest and building areas. There are 9 classes corresponding to tree, sky, road, signs, sidewalk, ground signs, building, car, others. We manually label a subset of all images randomly chosen in the dataset. The training time for Random forest is 58 minutes and for CRF is 43 minutes. The mean prediction time is 2.5s for Random Forest and 3.5s for CRF.

b) CamVid dataset: 2 consists of several 960x720 video sequences taken in a highly dynamic street environment and labelled at 1Hz. There are 32 classes in the dataset. We use two sequences: 01TP sequence that lasts 2:04minutes and 06R0 sequence that lasts a 1:41minutes. We use the first half of the sequence as training set and the second for test. The training time for RF is 1h09 and for CRF is 48minutes. Prediction time is 1.5s for Random Forest and 3.1s for CRF.

c) Performance measurement: Two standard measures for multi-class classification are reported: the overall percentage of correctly classified pixels denoted as global and the unbalanced average per-class accuracy denoted as average and defined as 1

N ∑ N k=1 t k n k
where N is the number of classes, t the number of pixels correctly classified and n the number of annotated pixels of the k th class. d) Results: Results for the frame-by-frame labelling are presented in table 1 and illustrated in figure 2 for INRIA dataset and in figure 3 for CamVid. As comparisons only make sense if we compare similar measures over similar datasets, we compare our results with those of [START_REF] Miksik | Efficient temporal consistency for streaming video scene analysis[END_REF]. Our algorithm reaches near state-of-the-art performances for global per-pixel accuracy and outperforms [START_REF] Miksik | Efficient temporal consistency for streaming video scene analysis[END_REF] for average per-class accuracy. Concretely, our algorithm is better in detecting each instance at the cost of a lower quality. This result is in accordance with our goal to build a discriminative semantic representation of the scene. We need to catch as much objects as possible with a lower priority on the pixelwise labelling. Despite good results some parts of labelled spherical images in INRIA dataset are particularly noisy. It is due to the stitching algorithm used to build each view from three images that change locally the light intensity (please consult the video attachment of the paper).

Results with enforced temporal consistency are presented in table II. It improves results of both global and average per

IV. MAP CONTENT REQUEST

Localization is the task of retrieving the position of a map content query. It could be the position of the robot or any other content. Several methods like [START_REF] Oliva | Modeling the shape of the scene: A holistic representation of the spatial envelope[END_REF] propose a scene recognition scheme based on very low dimensional representation. Despite undeniable efficiency in scene recognition, those methods do not allow high-level content request and so are hardly extensible to tasks where human are "in the loop". At the opposite side, works like [START_REF] Viswanathan | Automated spatial-semantic modeling with applications to place labeling and informed search[END_REF] propose a modelling scheme based on objects and places and use it to request high level content. These methods use the co-occurrence of objects classes and places classes to predict place label or perform informed search. However, as said earlier, this strategy does not work outdoors because any object classe can be present anywhere and the concept of "place" for open space is not straightforward. In this section we propose an algorithm that relies on MTS-map to efficiently realize localization of robot or any human-understandable concept like object or group of objects with given relations.

A. Semantic Localization

To achieve robust and efficient localization, our method relies on the proposed MTS-map structure. As explained in section III-A, local sub-maps are indexed in a tree structure encoding classes presence and occurrence. Each leaf is a set of sub-maps with similar semantic content. The first step consists in searching the tree for the leaf/leaves with corresponding content, for example, all leaves with two buildings. It allows to drastically reduce the number of sub-maps to compare with. Then semantic graphs G o are compared to select the most probable local sub-map where for finding the needed information. Due to change in viewpoint that can possibly fuse several objects, comparing those graphs formulates as multivalent graph matching problem. This is NP hard problem but we can use structure of the graph to speed up the process. We use a variation of the interpretation tree algorithm [START_REF] Grimson | Object Recognition by Computer: The Role of Geometric Constraints[END_REF] presented at Algorithm 1. Finally, when high precision relocation is needed, the visual odometry method presented in [START_REF] Meilland | A spherical robot-centered representation for urban navigation[END_REF] is used on the RGBD layer to achieve centimetrical precision.

Our semantic graph representation presents several advantages over other ways to abstract an image: it relies on the entire image and not just on sparse local features that could be subject to noise, perceptual aliasing or occlusion. It intrinsically encodes image structure that contains an important part of the information. Graphical description allows to reconstruct approximate image structure while collection of low-level features do not. It is extremely lightweight: the size of the map with all full size images is 53Gbytes while semantic graphs representation needs only 18.5MBytes, which correspond to a compression ratio around 3000.

B. Interpretation Tree Algorithm

Interpretation tree is an efficient algorithm that uses relationships between nodes of two graphs to speed up the matching process. It relies on two kinds of constraints to measure similarities called unary constraints and binary constraints. Let G 1 and G 2 be such two graphs. Unary constraints compare a node of G 1 to those of G 2 . If comparison succeed nodes are matched and a score is computed for the couple of nodes. Then the best pair of nodes is added to the list L of matched nodes and binary constraints check if every two pairs of nodes in G 1 and G 2 have compatible relationships. We use the following constraints :

Unary constraints: they use three properties of nodes. Their label, the eccentricity and the orientation of the elliptical envelop that fits the corresponding area shape. If labels are different or the difference of shape properties is higher than a given threshold, comparison fails. Taking into account only labels, eccentricity and orientation allows to be robust to change in apparent size of semantic areas.

Pairwise constraints: they check relationships of two nodes. To do this they us weights w i provided by the adjacency matrix of each semantic graph.

The interpretation tree returns the number of matched nodes. The highest score gives the most probable position.

V. LOCALIZATION FROM IMAGES RESULTS

In this section, we present our results to the problem of localizing an image in a database, which corresponds to the robot localization problem. We compare our algorithm performance with recent state-of-the-art Bag-of-Words techniques 3 presented in [START_REF] Galvez-Lopez | Bags of binary words for fast place recognition in image sequences[END_REF]. Their algorithm builds offline a tree structure that performs hierarchical clustering within the image descriptor space. Then similarity between current image and images in database is evaluated by counting the number of common visual words. We have trained the vocabulary tree with two sets of branching factor and depth levels: K=10, L=5 producing 100000 visual words and K=8, L=4 producing 4096 visual words. The weighting strategy adopted between visual words is the term frequency-inverse document frequency tf-idf and the scoring type is L1-Norm (for details about parameters see [START_REF] Galvez-Lopez | Bags of binary words for fast place recognition in image sequences[END_REF]). We evaluate several aspects of the algorithm. In subsection A we study performances for image retrieval in wide database. In subsection B we evaluate the robustness of our algorithm to wide changes in viewpoint. In subsection C we present some interesting results that cannot be attained with low-level feature-based algorithms. The dataset used for tests is the INRIA dataset presented in section III-C. CamVid is not used in this section because the dataset is too small with only 101 labelled images for sequence 06R0 and 124 for sequence 01TP.

A. Image retrieval

Experiments setup: The experiment consists in retrieving successively all images in the database. We use three variations of our method: first the tree structure is used alone to search for images with same classes and same number of occurrence. It is denoted as "Index". Then the Interpretation Tree is used to discriminate between remaining results. It is denoted as "Interp+Index". Finally we use only the Interpretation Tree, denoted as "Interp". "BoW" denotes the Bag-of-words algorithm.

Results: Timings are presented in table III. All versions of our algorithm outperform BoW techniques in terms of time efficiency. This comes from the use of image structure that discriminate very fast between good and false candidates and the simple tests performed. Checking labels, shape properties and strength of the relation is very fast. The use of index alone is faster than all the other methods as it simply count the number of nodes of each class. However it does not encode image structure so it is subject to aliasing.

B. Accommodation to view point change

Experiments setup: We run two experiments to evaluate robustness to changes in viewpoint. The first one consists in taking a subset of images from the original dataset to build a reference database and a different interleaved subset to build required database. We take 1 image out of 40 to build the database and 1 out of 40 shifted by 20 images to build the required set, denoted as Distant images. Then, we retrieve the positions of distant images in the reference database. In the second experiment we match monocular images with our spherical view database. Monocular images are taken from the same position as spherical views however focal and image size are different. For these experiments we compare BoW with Interpretation Tree alone. Due to large distances between images, Index is not useful since class occurrences changes significantly.

Performance measurements: We report two measurements to quantify the quality of matching algorithm. First we compute the distance matrix presented in figure 4. Rows correspond to database images and columns to images to retrieve. For each image to retrieve we compute distances with all images in the reference database. Ground Truth corresponds to diagonal line.

The second measurement is the discriminative power of the algorithm denoted as D p . It is measured by first computing the mean distance between the image to retrieve and corresponding images in the dataset denoted as d true . The number of corresponding images is arbitrarily set to the three closest to ground truth position. Then we compute the mean distance between image to retrieve and non corresponding images in the dataset denoted as d f alse . We define D p = d f alse /d true . d f alse and d true are normalized to [0, 1]. The highest D p is, the more discriminant is the algorithm.

1) Results with large distances between images: In this experiment our algorithm outperforms the BoW method. The discriminative power is more than three time higher with our algorithm. This comes from the fact that our algorithm use the image structure that allows to discriminate more efficiently between true and false matching. Additionally semantic areas are consistent along a wide range within images and are less sensitive to local similarities than featurebased methods.

2) Results with monocular views: Interpretation Tree outperforms BoW methods for monocular to spherical view matching with discriminative power more than 4 times higher. However on BoW distance matrix we can see a less pronounced cross-diagonal line corresponding to visited places of the robot but in the opposite direction. This structure is not detected by our algorithm. It comes from the fact that semantic graph encodes shapes of areas to match nodes. When only a part of the area is observed match is not possible. This makes our algorithm more sensitive to cases where the field of view is reduced. Moreover the number of nodes matched in graph is much lower than with spherical views (roughly 1/4). This results from the partial observation of some semantic areas that are not yet matchable because of changes in associated shape descriptors.

C. SEMANTIC CONTENT REQUEST RESULTS

In this section we present results for tasks that need to use high-level concepts and are not possible otherwise. In the first part we study the time efficiency of localizing a given set of objects. In the second part we study the localization under constraints problem, that is without using some parts in the image.

a) Request high level content: The tree structure used to index sub-maps encodes classes presence and occurrence. Therefore it is easy to request from the map a list of spherical views where particular classes are observed. It is also possible to use more complex requests as for example the list of spherical views where two classes with particular relationships are observed. For this test we slightly change the previous graph structure to take into account relative positions instead of strength of connection previously expressed in term of number of pixels of different classes connected together. We do this to make it easier to specify relationships. IV provides average time costs for some typical scene content requests. Notice that request times are extremely small due to the small size of graphs as we keep only those candidates where the request graph is fully matched.

b) Relocation under constraint: Navigation-oriented maps should provide an efficient way to deal with dynamic environments for lifelong mapping. Our map structure and the proposed relocation algorithm allow to take care of possible changes in images using semantics. For example cars are not reliable due to their dynamic nature. So we can ignore them by removing the corresponding nodes in graph.

Results of relocation without using car class are presented in figure 4, last column. Distance matrix is similar to the original one and only very slight changes occur. However for monocular and distant images discriminative power changes in opposite direction. We can explain this by the fact that in large graphs (panoramic images), each node is connected to a great number of others. Interpretation tree easily detects false node matching with binary constraints so that matched nodes are reliable. In small graphs only a few edges are allowed and false nodes matching are difficult to detect. Cars correspond most of the time to small areas in image so that the shape changes a little from one instance to another. False matching with cars is more probable than with larger semantic classes like tree or classes with more characteristic shapes. So removing cars in small graph can improve matching score while removing other classes does not. This behaviour is confirmed by tests with restrictions on other classes. Removing trees or buildings decreases matching score in all cases.

VI. CONCLUSIONS

In this paper we have presented a new hybrid map representation well-suited for large scale outdoor environments. It combines in local sub-maps compact semantic and precise metric representations. We have also proposed an efficient query-based algorithm for coarse to fine relocation in our map. It outperforms a state-of-the-art feature-based relocation algorithm, it is able to request high level humanunderstandable content and easily adapts to outdoors scenes.

There are several ways to extend this work. First, the graph representation relies only on shape properties of semantic areas. It makes it difficult to match with monocular images or images taken from very different viewpoints. It could be interesting to use other properties to match nodes of the graph like color histograms in order to make matching process more robust to partial observations. Second, our algorithm entirely relies on semantics and improving labelling quality can improve relocation. Pixel-wise temporal consistency has been shown to improve labelling quality and higher level temporal consistency can be interesting to investigate. For example temporal stability of semantic areas can inform on the underlying labelling quality.

Fig. 1 .

 1 Fig. 1. MTS-map Architecture. Dark blue rectangles correspond to local sub-maps and light blue rounded rectangles to different layers.

Fig. 2 .

 2 Fig. 2. Examples of frame by frame labelling results on INRIA database. Images are presented in the following order. Top: RGB image, Middle: Labelling results, Down: Ground Truth. Colors correspondance are: green: tree -blue: sky -gray: road -brown: building -blue: signs -red: carorange: ground signs -purple: sidewalk -black: others

Fig. 3 .

 3 Fig. 3. Examples of frame by frame labelling results on CamVid database. Images are presented in the following order. Top: RGB image, Middle: Labelling results, Down: Ground Truth. From right to left: best to worst results.

Fig. 4 .

 4 Fig. 4. Distance matrix and discriminative power D p . The brightest is the pixel the closest are the images.

  The possible values are: 1 = left, 2 = top left, 3 = top, 4 = top right, 5 = right, 6 = bottom right, 7 = bottom, 8 = bottom left. Table

  Algorithm 1 Details of our Interpretation Tree algorithm used to compare semantic graphs INPUTS: G 1 , G 2 : graphs of the current view and a given view in the database OUTPUTS: Score of the matching (list of matched nodes) for all Nodes n i ∈ G 1 do for all Nodes n

	end if
	end for
	if MatchedNodesList ≥ 1 then
	sort MatchNodesList
	for all (n end if
	end for
	end if
	end for

j ∈ G 2 do if UnaryConstraint(n i , n j ) then add (n i , n j ) to MatchNodesList i , n j ) in MatchedNodesList do add (n i , n j ) to InterpList if PairwiseConstraint(InterpList) == False then remove (n i , n j ) to InterpList

TABLE III RETRIEVAL

 III TEST RESULTS: TIME EFFICIENCY FOR EACH ALGORITHM.

	Dataset	Mean retrieval time
	BoW K=10, L=5	22ms
	BoW K=8, L=4	16ms
	Interp	8.40ms
	Interp+Index	0.12ms
	Index	54.20µs

TABLE IV TIME

 IV TO RETRIEVE HIGH LEVEL CONTENT

	Request	Retrieval Time
	Two buildings	56µs
	No car	55µs
	Car on road	0.95ms
	Trees at the right of building	0.86ms

The full resolution is

2048x665 but we use 1024x333 resolution for classification 2 http://mi.eng.cam.ac.uk/research/projects/VideoRec/CamVid/

We used the the implementation publicly available at: http://webdiis.unizar.es/ dorian/