Sang Dieu
email: dieu-sang.ly@mines-paristech.fr

Ly

Cédric Demonceaux
email: cedric.demonceaux@u-bourgogne.fr

Pascal Vasseur
email: pascal.vasseur@univ-rouen.fr

Claude Pégard
email: claude.pegard@u-picardie.fr

Extrinsic calibration of heterogeneous cameras by line images

Keywords: Extrinsic calibration, Heterogeneous cameras, Lines

The extrinsic calibration refers to determining the relative pose of cameras. Most of the approaches for cameras with non-overlapping fields of view (FOV) are based on mirror reflection, object tracking or rigidity constraint of stereo systems whereas cameras with overlapping FOV can be calibrated using structure from motion solutions. We propose an extrinsic calibration method within structure from motion framework for cameras with overlapping FOV and its extension to cameras with partially non-overlapping FOV. Recently, omnidirectional vision has become a popular topic in computer vision as an omnidirectional camera can cover large FOV in one image. Combining the good resolution of perspective cameras and the wide observation angle of omnidirectional cameras has been an attractive trend in multi-camera system. For this reason, we present an approach which is applicable to heterogeneous types of vision sensors. Moreover, this method utilizes images of lines as these features possess several advantageous characteristics over point features,

Introduction

The extrinsic calibration of cameras having common FOV can be solved by structure from motion (SFM) techniques which have been widely studied in the last decades. Camera poses can be recovered concurrently with the 3D structure by factorization approaches [START_REF] Tomasi | Shape and motion from image streams under orthography: A factorization method[END_REF][START_REF] Sturm | A factorization based algorithm for multi-image projective structure and motion[END_REF][START_REF] Triggs | Factorization methods for projective structure and motion[END_REF][START_REF] Heyden | Projective structure and motion from image sequences using subspace methods[END_REF][START_REF] Quan | Affine structure from line correspondences with uncalibrated affine cameras[END_REF][START_REF] Mahamud | Iterative projective reconstruction from multiple views[END_REF][START_REF] Martinec | Line reconstruction from many perspective images by factorization[END_REF][START_REF] Martinec | 3d reconstruction by fitting lowrank matrices with missing data[END_REF]. The measurement matrix derived from point or line images can be factorized into a matrix of camera transformations and a matrix of 3D shape. Besides factorization, there exist algebraic solutions (8point algorithms [START_REF] Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF][START_REF] Hartley | In defense of the eight-point algorithm[END_REF]) or minimal solutions (5-point algorithms [START_REF] Triggs | Shape representation and recovery camera pose and calibration from 4 or 5 known 3d points[END_REF][START_REF] Quan | Linear n-point camera pose determination[END_REF][START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF]) to solve for transformation between two views and tensor-based approaches [START_REF] Hartley | Lines and points in three views and the trifocal tensor[END_REF][START_REF] Triggs | Linear projective reconstruction from matching tensors[END_REF][START_REF] Fitzgibbon | Automatic camera recovery for closed or open image sequences[END_REF] to solve for transformations among three views. These solutions are frequently used as initialization for bundle adjustment [START_REF] Triggs | Bundle adjustment: A modern synthesis[END_REF][START_REF] Bartoli | Structure-from-motion using lines: Representation, triangulation, and bundle adjustment[END_REF]. L∞ optimization methods have been lately proposed to solve several problems in geometric vision. [START_REF] Sim | Recovering camera motion using l-inf minimization[END_REF][START_REF] Kahl | Multiple-view geometry under the l∞-norm[END_REF] presented L∞ approaches based on second order cone programming (SOCP) to recover camera translations and 3D points assuming known rotations. Martinec and Pajdla [START_REF] Martinec | Robust rotation and translation estimation in multiview reconstruction[END_REF] estimated rotations by least squares and translations by SOCP. A similar technique for quasi-convex optimization was developed in [START_REF] Ke | Uncertainty models in quasiconvex optimization for geometric reconstruction[END_REF]. Note that in some previous works such as [START_REF] Vieville | Motion of points and lines in the uncalibrated case[END_REF][START_REF] Hartley | Lines and points in three views and the trifocal tensor[END_REF][START_REF] Morris | A unified factorization algorithm for points, line segments and planes with uncertainty models[END_REF][START_REF] Ansar | Linear pose estimation from points or lines[END_REF][START_REF] Rother | Linear multi-view reconstruction of points, lines, planes and cameras, using a reference plane[END_REF], a common framework based on both point and line features was developed to solve for the camera pose and scene structure. These approaches were developed and evaluated using perspective images but their performance was not verified on images suffering strong distortion captured by catadioptric or fish-eye cameras.

Recently, omnidirectional cameras have been widely utilized as they possess wider FOV than conventional cameras. Such devices can be built up from (i) an arrangement of several cameras looking forward to different directions, (ii) rotary cameras or (iii) cameras with wide-angle lenses such as fish-eye or with mirrors of particular curvatures (catadioptric cameras). Barreto and Daniilidis [START_REF] Barreto | Wide area multiple camera calibration and estimation of radial distortion[END_REF] estimated the projection matrices and radial distortion parameters of multiple wide FOV cameras using a factorization approach without non-linear minimization. Micusik and Pajdla [START_REF] Micusik | Structure from motion with wide circular field of view cameras[END_REF] solved for the intrinsic parameters and relative pose of wide FOV cameras from point correspondences in a polynomial eigenvalue problem incorporated with Random Sample Consensus (RANSAC) [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF]. Lhuillier [START_REF] Lhuillier | Automatic scene structure and camera motion using a catadioptric system[END_REF] presented a similar approach to [START_REF] Micusik | Structure from motion with wide circular field of view cameras[END_REF] in that the camera geometry was first estimated by a central model and then upgraded by a non central model. The camera transformation can also be solved by decoupling orientation and translation, i.e. the rotation was computed using vanishing points of parallel lines [START_REF] Antone | Scalable extrinsic calibration of omnidirectional image networks[END_REF][START_REF] Bazin | Motion estimation by decoupling rotation and translation in catadioptric vision[END_REF] and then the translation was estimated from point correspondences and known rotation [START_REF] Kim | Translation estimation from omnidirectional images[END_REF][START_REF] Bazin | Motion estimation by decoupling rotation and translation in catadioptric vision[END_REF]. Lim et al. [START_REF] Lim | Estimating relative camera motion from the antipodal-epipolar constraint[END_REF] utilized the correspondences of antipodal points to estimate the orientation and translation of wide FOV cameras. Other methods were based on epipolar constraint [START_REF] Kang | 3-d scene data recovery using omnidirectional multibaseline stereo[END_REF][START_REF] Svoboda | Central panoramic cameras: Design, geometry, egomotion[END_REF][START_REF] Chang | Omnidirectional structure from motion[END_REF] or optical flow estimation [START_REF] Nelson | Finding motion parameters from spherical flow fields (or the advantages of having eyes in the back of your head)[END_REF][START_REF] Gluckman | Ego-motion and omnidirectional cameras[END_REF][START_REF] Shakernia | Omnidirectional egomotion estimation from back-projection flow[END_REF]. The above-mentioned approaches are based on point features which are sensitive and hard to be located in omnidirectional images due to inconstant resolution and/or lens distortion.

There exist a limited number of solutions to the extrinsic calibration of a heterogeneous camera system. Chen et al. [START_REF] Chen | Calibration of a hybrid camera network[END_REF] calibrated a vision system consisting of an omnidirectional camera and several perspective cameras. First, the catadioptric camera was calibrated in two steps, i.e. the aspect ratio was defined from an image of the calibration pattern captured by the camera without mirror and then the focal length was estimated by the vanishing points in an image taken by the camera with mirror. Then some spatial points determined in the coordinate system of the catadioptric camera were used to calibrate the perspective cameras using the 3D-2D point correspondences. This technique requires information of 3D points. Again, it is possible to solve for extrinsic parameters among heterogeneous cameras by SFM techniques. [START_REF] Ramalingam | A generic structure-from-motion framework[END_REF][START_REF] Bastanlar | Multi-view structure-from-motion for hybrid camera scenarios[END_REF] presented a solution to computation of camera transformation, triangulation, and bundle adjustment using point-projection ray model. These solutions to heterogeneous cameras are based on point features, which cannot be well detected and matched by the same technique for heterogeneous images. That is the reason why in [START_REF] Ramalingam | A generic structure-from-motion framework[END_REF] correspondences were provided manually. Also with point-projection ray model, [START_REF] Gasparini | Multi-view matching tensors from lines for general camera models[END_REF] proposed an SFM approach through multiview tensors from line correspondences.

In this paper, we propose an extrinsic calibration approach for a heterogeneous camera system with overlapping FOV and show that it can be extended to cameras with partially non-overlapping FOV. This technique is based on images of straight lines in 3D scene. The principal contributions of this paper are: firstly, we present a complete line-based SFM solution in the spherical space. From the existing line extraction and line-based rotation estimation to our proposed line-based translation computation and bundle adjustment, all of these steps are formulated for spherical images. This unified space allows a similar representation of heterogeneous cameras in spite of their different characteristics and hence similar manner of image processing. Secondly, we propose to use line features which are more stable than point features in the detection and matching, especially among images with important distortion. Moreover, we show that point feature can be integrated in the translation estimation to improve its accuracy. Finally, multi-camera system is frequently used in urban environment, therefore the line-based extrinsic calibration becomes practical as lines are omnipresent in urban scenes. Even if they are absent in the scene, a pattern containing lines can always be employed to provide features for the extrinsic calibration.

The organization of the paper is as follows: section 2 will present our linear approach of extrinsic calibration based on line correspondences. This method is comprised of rotation estimation from vanishing points of parallel lines in 3D scene and translation estimation from line correspondences. Later in the same section, we will describe the reconstruction of 3D lines and the bundle adjustment to refine the extrinsic parameters of cameras and the 3D structure. In section 3, we will show some validation results using simulation and real image sequences in different scenarios. The paper will end with some conclusions.

Extrinsic calibration of heterogeneous cameras

The problem of extrinsic calibration consists in estimating the rotation and translation of cameras. This section will start by the spherical model to unify heterogeneous cameras. Next, we will present a method of line detection and matching. Then, we will develop a linear approach to compute the extrinsic parameters using uniquely line images and composing of two phases, i.e. estimating rotations using vanishing points of parallel lines and translations from known rotations and line correspondences among at least three images. Finally, we will propose a non-linear optimization of these parameters by bundle adjustment technique.

The following notation is used in this paper -Matrices and vectors are denoted in bold.

-Constants, variables and unknown quantities are denoted in italic. -Numerals, operators and functions are denoted in Roman/upright. -T denotes the transposition of a vector or a matrix.

-[a] × denotes the skew symmetric matrix of vector a. -Index of cameras is subscript, e.g. C i denotes the i th camera. -Index of line features is superscript, e.g. L k denotes the k th line.

Spherical mapping of line features

Perspective images and most common catadioptric images (captured by cameras coupled with paraboloidal, hyperboloidal and ellipsoidal mirrors) can be mapped on a unitary sphere [START_REF] Geyer | A unifying theory for central panoramic systems and practical implications[END_REF]. In case of fish-eye cameras, it is reasonable to approximate the small locus of projection centers by a single projection center if the calibration accuracy fulfills the requirements of applications [START_REF] Ying | Can we consider central catadioptric cameras and fisheye cameras within a unified imaging model[END_REF], so it is also possible to map a fish-eye image on a sphere. Consequently we utilize the spherical projection model to unify these heterogeneous cameras. This model was first proposed by Geyer and Daniilidis [START_REF] Geyer | A unifying theory for central panoramic systems and practical implications[END_REF] and Barreto and Araujo [START_REF] Barreto | Issues on the geometry of central catadioptric image formation[END_REF] for central catadioptric cameras. Later, Ying and Hu [START_REF] Ying | Can we consider central catadioptric cameras and fisheye cameras within a unified imaging model[END_REF] justified that this model could approximate the projection of fish-eye cameras. Basing on this model and considering the distortion, Mei and Rives [START_REF] Mei | Single view point omnidirectional camera calibration from planar grids[END_REF] developed a calibration toolbox for central imaging systems including fish-eye lenses.

According to this model, the projection of a world point to the image plane of a central camera is illustrated in figure 1 and composed of the following steps 1. The world point X is projected in X S on the unitary sphere centered in C S (X S )

C S = (x S , y S , z S ) = X ||X|| (1)
2. The spherical point X S is expressed in the reference frame located at the second projection center C ξ .

The position of C ξ depends on the mirror parameter ξ (given in table 1)

(X S ) C ξ = (x S , y S , z S + ξ) (2)
3. X S is projected to the normalized plane in the undistorted point m u

m u = ( x S z S + ξ , y S z S + ξ , 1) (3)
4. The distorted point m d is computed from m u by considering two main sources of distortion: first, the imperfect radial curvature of the lens generating radial distortion, and second, the misalignment between the camera optical axis and the mirror axis causing both radial and tangential distortions [START_REF] Weng | Camera calibration with distortion models and accuracy evaluation[END_REF]

m d = m u + D(m u ) (4) D(m u ) = m u +   x u (k 1 ρ 2 u + k 2 ρ 4 u ) + 2p 1 x u y u + p 2 (ρ 2 u + 2x 2 u ) y u (k 1 ρ 2 u + k 2 ρ 4 u ) + 2p 2 x u y u + p 1 (ρ 2 u + 2y 2 u ) 0   (5)
where ρ u = x 2 u + y 2 u , (k 1 , k 2 ) the radial distortion parameters and (p 1 , p 2 ) the tangential distortion parameters. 5. m d is projected to the image plane by the camera intrinsic matrix K providing the pixel point p

p = Km d =   f u η f u ηs u 0 0 f v η v 0 0 0 1   m d (6)
K is also called the generalized projection matrix as the combination of a camera and a mirror or a fisheye lens is considered as a single imaging device with the projection center at C S . K is defined by (f u , f v ) the focal lengths, η the mirror parameter (given in table 1), s the skew and (u 0 , v 0 ) the principal point.

On the other hand, the inverse projection model permits the calculation of the spherical point X S given the pixel point p and the central camera parameters

1. The distorted point m d is computed from the image point p m d = K -1 p =   f u η f u ηs u 0 0 f v η v 0 0 0 1   -1 p (7) € X S € p € K € X € 1 € ξ € C ξ € C S € normalised plane € image plane € Distortion € m d € m u Fig. 1 Unified projection model 2.
The undistorted point m u on the normalized plane is estimated using the following inverse distortion model

   m u = m d -D n D n = D(m d -D n-1 ) D 1 = D(m d ) ( 8
)
where D is defined in equation ( 5) and n is the number of iterations of the recursive estimation model. 3. m u is back-projected in X S on the sphere

         x S = ξ+ √ 1+(1-ξ 2 )(x 2 u +y 2 u ) x 2 u +y 2 u +1 x u y S = ξ+ √ 1+(1-ξ 2 )(x 2 u +y 2 u ) x 2 u +y 2 u +1 y u z S = ξ+ √ 1+(1-ξ 2 )(x 2 u +y 2 u ) x 2 u +y 2 u +1 -ξ (9)
In order to estimate the camera extrinsic parameters from line correspondences, we first map line features from planar images on the sphere. Under the spherical mapping, each line feature on the sphere locates on a great circle which is the intersection of the sphere and a plane passing through the center and the corresponding 3D line. Obviously, line features have different geometric representations in heterogeneous planar images (linear in perspective, non-linear in catadioptric or fish-eye), but similar geometric nature on the sphere (great circle), simplifying the processing of lines among multiple heterogeneous views.

 ξ+ √ 1+(1-ξ 2 )(x 2 +y 2 )
x 2 +y 2 +1

ξ

 TABLE I UNIFIED MODEL PARAMETERS ξ η Parabola 1 -2p Hyperbola d √ d 2 +4p 2 -2p √ d 2 +4p 2 Ellipse d √ d 2 +4p 2 2p √ d 2 +4p 2
Planar 0 -1 d : distance between focal points 4p : latus rectum Table 1 Mirror parameters (retrieved from [START_REF] Mei | Single view point omnidirectional camera calibration from planar grids[END_REF])

Line detection and matching

We have recently developed an approach of line matching across images captured by heterogeneous cameras [START_REF] Ly | Scale invariant line matching on the sphere[END_REF]. Line correspondences are searched by an affine invariant measure of similarity computed from point correspondences on the sphere. This method can be summarized in three stages

Detection and matching of spherical points

The detection of scale-invariant-feature-transform (SIFT) points on the sphere was proposed in [START_REF] Mota | Scale invariant feature transform on the sphere: Theory and applications[END_REF] to preserve the spherical affine transformation and process the visual information without introducing any deformation. It consists of the following steps 1. Map the original image on the sphere with (θ, ϕ) parameterization. 2. Compute the spherical scale-space representation of the spherical image and then the spherical differenceof-Gaussians (DoGs). 3. Extract the local extrema from the DoGs. Each extremum is detected by comparing a point to its 26 neighbors in 3x3 spherical grids at the current and adjacent scales. 4. Calculate the spherical descriptor of each extracted keypoint. This descriptor is created from orientation histograms of the region around the keypoint.

Once the keypoints and their descriptors are obtained, we can find the matched points between two images using the method proposed by Lowe in [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF].

Line extraction

The extraction of lines in images captured by a catadioptric camera was presented in [START_REF] Bazin | Motion estimation by decoupling rotation and translation in catadioptric vision[END_REF]. The extraction process both planar and spherical images as follows 1. Extract edges in the original image using Canny edge detector.

€ p 2 € p 3 € q 2 € q 3 € p 1 € p N € q 1 € q N € l 1 € l 2
Fig. 2 Two lines with point correspondences in their neighborhood in spherical space 2. Link edge points into chains with a threshold of minimal chain length. 3. Split chain which does not correspond to a unique line into sub-chains as each chain after the second step may contain the projection of different 3D lines. 4. Merge sub-chains which belong to the same line as sub-chains after the third step may be segments of a single line.

This algorithm was then extended to other wideangle cameras such as fish-eye and Ladybug cameras.

Line matching through point correspondences

Once point correspondences and line features are available in two images, we can search line correspondences using the matching approach proposed in [START_REF] Ly | Scale invariant line matching on the sphere[END_REF]. In this method, the similarity between two lines l 1 and l 2 is computed from point correspondences p i and q i in their neighborhood as illustrated in figure 2.

Linear estimation of orientation and translation

Camera orientation from vanishing points

The detected lines are projected on the sphere as great circles. Great circles corresponding to parallel lines in 3D space intersect theoretically at two antipodal points, namely vanishing points. As lines in our images are mostly horizontal or vertical in 3D scene, we obtain two bundles of great circles on the sphere, from which we extract two types of vanishing points, i.e. horizontal and vertical by the convergence of each bundle as illustrated in figure 3. Next, vanishing points between two images are matched based on their horizontal or vertical direction. As the coordinates of a vanishing point on the sphere also define the direction of the corresponding set of parallel lines in 3D space, the camera orientation can be estimated from at least two orthogonal vanishing points. In other words, vanishing points in two spherical images are related by the rotation between two camera frames. As a consequence, the rotation R between two cameras a and b can be computed from their matched vanishing points V i a and V i b ∈ S 2 (i = 1...n where n ≥ 2) using a closed-form solution similar to that used in [START_REF] Horn | Closed-form solution of absolute orentation using unit quaternions[END_REF].

[V 1 b ...V n b ] = R[V 1 a ...V n a ] (10)

Camera translation from line images

The multiple-view geometry of lines in planar images has been well studied [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF][START_REF] Ma | An Invitation to 3-D Vision: From Images to Geometric Models[END_REF]. In this section, we develop the multiple-view geometry of lines on the sphere in a similar manner to [START_REF] Torii | Two-and three-view geometry for spherical In: Workshop on Omnidirectional Vision, Camera Networks and Non-classical cameras[END_REF] and derive a linear algorithm which permits the estimation of translations from known rotations and line correspondences. Consider m spherical cameras centered at C i ∈ IR 3 (i = 1...m with m ≥ 3) as illustrated in figure 4. A line in 3D space L ∈ IR 3 is projected to spherical images as great circles l i ∈ S 2 and corresponding unit normals n i ∈ S 2 . Each normal n i originates at C i and is perpendicular to the 3D plane passing through L and C i . L can be expressed vectorially by L = X + µd where X, d ∈ IR 3 and µ ∈ IR. All these coordinates are inhomogeneous.

Let the coordinate system origin be at the first camera center C great circles l i and perpendicular to normals n i , we obtain the next relation in which

L is expressed in {C 1 } and n i in {C i } n T i (R i L + t i ) = 0 (
A L = 0 ( 12
)
where

A =   n T 1 0 n T a R a n T a t a n T b R b n T b t b   and L = (L T , 1) T
The right null space of A must be one-dimensional subspace, i.e. a line in 3D space, A is of rank 2. This results in a linear dependence among three rows r 1 ,r 2 and r 3 of A which can be written as r 1 = αr 2 + βr 3 . Noting that the upper right element of A is r 14 = 0, we can select the coefficients α = γt T b n b and β = -γt T a n a for some scalar γ. This can be applied to the first three columns of A to obtain the following relation

n T 1 = αn T a R a + βn T b R b ( 13
)
n 1 = αR T a n a + βR T b n b (14
)

n 1 = γt T b n b R T a n a -γt T a n a R T b n b (15) [n 1 ] × R T a n a n T b t b -[n 1 ] × R T b n b n T a t a = 0 (16)
Equation ( 16 16), the minimum number of lines to estimate t a,b is three.

With one line correspondence across m cameras, there are (m -1)(m -2)/2 triplets of views (1, a, b) or trilinear relations in equation ( 16) and so on for additional line correspondences . These trilinear relations can be concatenated in a single system that permits the linear estimation of all translations t 2...m from all rotations R 2...m and normal correspondences n 1...m using the Singular Value Decomposition (SVD).

Line reconstruction

With the aim of refining the estimated camera poses, we reconstruct the 3D features which are, together with the extrinsic parameters of cameras, an initial estimate of the bundle adjustment. Using the spherical mapping of line features, the reconstruction of 3D lines by intersecting 3D planes passing through great circles, i.e. line correspondences on the sphere, is more straightforward than by using line correspondences in planar images, especially for catadioptric and fish-eye images. Each line in 3D space is reconstructed by the intersection of the 3D planes perpendicular to line normals on spherical images . From the camera transformations [R i |t i ] and the line normal correspondences n i (i = 1...m), each 3D line can be estimated as follows

N L = 0 ( 17
)
where

N =      n T 1 0 n T 2 R 2 n T 2 t 2 . . . . . . n T m R m n T m t m      and L = (L T , 1) T
The SVD of matrix N = UDV T can be used to define the line intersection of 3D planes. First, two columns of V corresponding to two largest singular values define the normals to two planes subtended by this line; therefore, the line direction can be computed by the cross product of these normals. Then, the singular vector corresponding to the smallest singular value defines a point on the line.

Bundle adjustment

Bundle adjustment is an optimization technique which is usually used to refine simultaneously the parameters of cameras and 3D structure by minimizing the reprojection error of 3D features [START_REF] Hartley | Euclidean reconstruction from uncalibrated views[END_REF][START_REF] Beardsley | 3d model acquisition from extended image sequences[END_REF][START_REF] Fitzgibbon | Automatic camera recovery for closed or open image sequences[END_REF][START_REF] Triggs | Bundle adjustment: A modern synthesis[END_REF][START_REF] Pollefeys | Visual modeling with a hand-held camera[END_REF][START_REF] Zhang | Incremental motion estimation through modified bundle adjustment[END_REF]. One of the most effective non-linear least squares techniques for bundle adjustment is Levenberg-Marquardt algorithm [START_REF] Press | Numerical Recipes in C: The Art of Scientific Computing, 2nd edn[END_REF]. Bundles of projection rays are defined through the parameters of cameras and 3D lines as follows -Each of m cameras is parametrized by a 7-vector c i =(r 0 , r 1 , r 2 , r 3 , t x , t y , t z ) i (i = 1...m) where (r 0 , r 1 , r 2 , r 3 ) is the quaternion representation of the rotation and (t x , t y , t z ) is the conventional translation. -Each of n L 3D lines is represented by a 6-vector L k =(e 1

x , e 1 y , e 1 z , e 2

x , e 2 y , e 2 z ) k (k = 1...n L ) established by two different points e 1k and e 2k on that line.

The parameter vector in the optimization embodies all parameters describing m cameras and n L lines

W = (c 1 . . . c m , L 1 . . . L n L ) (18)
Bundle adjustment minimizes the following reprojection error with respect to all parameters of cameras and 3D lines. This error represents the orthogonality between the unit normal of the image line mapped on the sphere nk i and the spherical projection of two endpoints of the 3D line (figure 6).

arg min ci,L k m i=1 n L k=1 nk i • R i e 1k + t i ||R i e 1k + t i || 2 + nk i • R i e 2k + t i ||R i e 2k + t i || 2 (19)
The minimization is solved by Levenberg-Marquardt algorithm. The initial guess W 0 is provided by the camera transformation estimation and 3D reconstruction stages. i on the sphere are in red color. The 3D line L and the spherical projection of its two end-points (e 1 , e 2 ) are in blue color. The reprojection error is defined by the orthogonality between nk i and (e 1 , e 2 ) mapped on the sphere.

If all cameras have overlapping FOV, i.e. all lines are visible in every image, each row of the Jacobian matrix is calculated for each line in each camera as follows

∂d L ∂W = [ ∂d L ∂c 1 . . . ∂d L ∂c m , ∂d L ∂L 1 . . . ∂d L ∂L n L ] (20)
Denoting Υ = ∂d L ∂c and Ω = ∂d L ∂L , the Jacobian is given by

J =                   Υ 1 1 0 . . . 0 Ω 1 1 0 . . . 0 0 Υ 1 2 . . . 0
Υ n L 1 0 . . . 0 0 0 . . . Ω n L 1 0 Υ n L 2 . . . 0 0 0 . . . Ω n L 2 . . . . . . . . . . . . . . . . . . . . . . . . 0 0 . . . Υ n L m 0 0 . . . Ω n L m                   (21)
Cameras with partially non-overlapping FOV can be divided into different nodes of cameras with overlapping FOV. The vector of parameters becomes

W = ( c 1 . . . c m , L 1 node1 . . . L n L1 node1 , L 1 node2 . . . L n L2 node2 , ..., L 1 nodeN . . . L n LN nodeN ) ( 22
)
Each row of the Jacobian matrix is then computed for each line visible in each camera of each node.

Experimental results

Simulated data

As the rotation estimation from vanishing points of parallel lines has been evaluated in the state of the art, we examined only the result of our line-based translation estimation. This simulation also compares the precision of our line-based translation estimation to that of 2-point algorithm [START_REF] Bazin | Motion estimation by decoupling rotation and translation in catadioptric vision[END_REF], which had been proved to outperform the well known 5-point algorithm [START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF] in both precision and computing time. Moreover, we examined the performance of translation computation using both points and lines, which is a linear integration of our line-based algorithm and the 2-point algorithm as follows

   [n 1 ] × R T a n a n T b t b -[n 1 ] × R T b n b n T a t a = 0 (R a p 1 × p a ) T t a = 0 (R b p 1 × p b ) T t b = 0 (23)
where p i are point correspondences in camera C i .

First, we created 100 3D points and 100 3D lines randomly distributed in a sphere with 5-meter radius. Four cameras with an average baseline of 0.5 meter observed these features at a distance of 10 meters. The feature correspondences were supposed to be known. The translations among these cameras were recovered using 2-point, line-based and point-and-line-based approaches. Points in 2-point algorithm and line normals in our method are on unitary spheres, thus may be specified by elevation and azimuth angles. Gaussian noise of zero mean and standard deviation varying from 0 to 0.1 degree was added to two angles of every point and every normal. The same rotations with estimation error from 0 to 0.1 degree in all roll, pitch and yaw angles were used for all of the methods in comparison. Figure 7 illustrates the average angular error after 1000 runs. This result shows that the line-based algorithm is not only simpler than the point-based one (as the line-based algorithm requires uniquely lines for both rotation and translation calculations while the other requires lines for rotation and points for translation) but also more robust to noise. In addition, translation recovery from both points and lines performed better than the others using only one type of primitive as this combination included more data in the linear estimation system.

Real data

In this section, we present the results obtained from several image sequences in both indoor and outdoor scenes. As presented in section 2.2, we could proceed an automatic line matching to obtain correspondences for the estimation of camera transformation. However, in the following experiments, as the calibration is offline and line correspondences are not compulsorily numerous, they are provided manually.

Extrinsic calibration of a fish-eye camera

From an image sequence of a calibration pattern captured by a fish-eye camera as illustrated in figure 8, the camera rotations and translations were recovered linearly using line correspondences. The aim of using the calibration pattern is to compare the extrinsic parameters estimated by our algorithm to those obtained from the omnidirectional calibration toolbox [START_REF] Mei | Single view point omnidirectional camera calibration from planar grids[END_REF]. The difference between our approach and the toolbox is given in table 2. The difference between two rotations was defined by the difference of their angles in degrees and the difference of their axes in degrees. The difference between two translations was defined by the percentage difference of their magnitudes (i.e. the difference between two magnitudes divided by the average of two magnitudes) and the difference of their directions in degrees. It can be seen that the result of line-based extrinsic calibration is close to that of the calibration toolbox. The 3D reconstruction of the calibration pattern and the camera poses are illustrated in figure 9. Table 2 Comparison of extrinsic parameters obtained from our line-based approach and the calibration toolbox [START_REF] Mei | Single view point omnidirectional camera calibration from planar grids[END_REF] with the checkerboard sequence in figure 8. Two rotations are compared by the difference of angles in degrees and axes in degrees. Two translations are compared by the difference of magnitudes in percents and directions in degrees.

Extrinsic calibration of heterogeneous cameras

A system of six cameras, i.e. three perspective and three fish-eye, observed the same scene as illustrated in figure 10. The extrinsic parameters among these cameras were recovered from 13 line correspondences and refined by bundle adjustment, which converged after 3 iterations. A snapshot of the reconstruction is illustrated in figure 11.

In order to evaluate the up-to-scale scene reconstruction, we verified the dimension of the reconstructed doors (table 3). Four doors with extracted borders in figure 10 from left to right were denoted Door 1 to 4 respectively. Using the height-to-width ratio of each door obtained from the reconstruction and its real width, we deduced and compared its estimated height to its real Fig. 9 Camera poses and 3D reconstruction of the checkerboard shown in figure 8 height. The result before and after bundle adjustment are denoted "LIN" and "LIN+BA" respectively. The final error is less than 0.5% for Door 2 to 4. However, the error for Door 1 is important due to the distortion in the fish-eye images, especially as Door 1 is close to the border of the image. The reason is that stronger distortion results in less accuracy in the back-projection of the image features from the image plan to the sphere and hence the rotation/translation estimation and 3D reconstruction are less precise. The reprojection of 3D lines in the first fish-eye image is shown in figure 12. It can be noticed that the reprojection error was reduced by bundle adjustment. As mentioned in the simulation section, it is possible to integrate point correspondences in the line-based translation estimation. Hence, this section presents an Fig. 10 Perspective and fish-eye images with line correspondences evaluation of different approaches of extrinsic parameter estimation: 5-point [START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF], line-based and point-andline-based algorithms. These techniques were used to recover the transformation among three cameras, i.e. two fish-eye and one perspective from point and line correspondences (figure 13).

Similarly to the previous experiment, we verified the height of four reconstructed doors (table 4). The linebased approach provided better result than 5-point algorithm and there was no important difference between the estimation using only lines and the estimation by combining points and lines. The reason of this might be that line-based estimation suffers the effect of noise less than point-based one, and consequently adding point feature did not improve significantly the result of linebased estimation. However, the result was not satisfactory for the first door as it was near the image border where there was much distortion, especially in fish-eye images.

The reprojection of 3D lines into one of the fish-eye views is illustrated in figure 14. As can be seen from this figure, the point-based approach provided significant reprojection error whereas line-based and pointand-line-based approaches performed well and did not differ from each other.

Extension to heterogeneous cameras with partially non-overlapping FOV

In order to calibrate a system of cameras with partially non-overlapping FOV, we propose the fusion of camera nodes as illustrated in figure 15. As the estimation of camera poses based on lines requires correspondences among at least three views, each node must consist of at least three cameras with overlapping FOV, i.e. observing the same lines in 3D space; and two different nodes in the network must share at least three common cameras in order that they can be fused into the same coordinate system at the same scale. These conditions are usually satisfied when using large FOV cameras. The extrinsic parameters of each camera node are recovered by the proposed line-based approach and then all cameras in the network are fused into a single space with the origin possibly chosen at the first camera of the first node. The 3D scene presented in figure 16 was captured by different perspective and fish-eye cameras. According to the 3D features observed by each camera, this hybrid system was divided into three camera nodes as shown in three columns of figure 17. The cameras in each node captured the same 3D lines. The first and second nodes had three common cameras, i.e. the first three cameras of node 2. The second and the last nodes shared three cameras, i.e. the last three cameras of node 2.

The camera orientation in each node was estimated from vanishing points of parallel lines. Especially, the rotations of cameras appearing in different nodes were recovered by combining the vanishing points detected in these nodes. The camera translations were computed by the fusion of linear relations of line normals in three This paper presented a method to estimate the extrinsic parameters of a system of heterogeneous cameras, which can be established from several types of cameras such as perspective, catadioptric and fish-eye. The extrinsic parameters are initially computed by a linear approach based on line images and refined by bundle adjustment. The proposed approach was validated with both simulation data and real image sequences. Several experiments show that using line feature for the estimation of camera extrinsic parameters provides better results than using point feature, especially when dealing with cameras with strong distortion. As lines are omnipresent in urban scenes and more stable than points regarding the detection and matching among heterogeneous images, this line-based technique of extrinsic calibration is a simple and useful tool to determine the topology of a camera network. Lastly, it is possible to integrate point feature in the translation computation to improve the estimation accuracy.

Fig. 3

 3 Fig.3Fish-eye images mapped to spherical images. Vanishing points of horizontal and vertical lines are colored red and blue respectively.

Fig. 4

 4 Fig.4Line projection in spherical cameras. The 3D line L is projected to spherical images as great circles with corresponding unit normals n i .

11 )

 11 Consider a triplet of cameras consisting of the first one and two others a and b. We denote such triplet by (1,a,b) where 2 ≤ a, b ≤ m and a = b. The trilinear relation among three views 1, a and b can be built up from equation (11) with i = 1, a, b and rewritten as follows

  ) relates the line normal correspondences in a triplet of views (1, a, b) to each other through the transformations [R a |t a ] and [R b |t b ] among those views. It allows the linear estimation of translations t a,b from rotations R a,b and normal correspondences n 1,a,b . Due to the dependence among rows of equation (

Fig. 5

 5 Fig. 5 Line reconstruction by the intersection of the 3D planes perpendicular to line normals n i on the spheres

Fig. 6

 6 Fig.6Reprojection error on the sphere. The image line and its unit normal nk i on the sphere are in red color. The 3D line L and the spherical projection of its two end-points (e 1 , e 2 ) are in blue color. The reprojection error is defined by the orthogonality between nk i and (e 1 , e 2 ) mapped on the sphere.

Fig. 7

 7 Fig. 7 Translation estimation error by 2-point [7] (red), lined-based (green) and point-and-line-based (blue) algorithms

Fig. 8

 8 Fig. 8 Sample images of a checkerboard captured by a fisheye camera with line correspondences

Fig. 11

 11 Fig. 11 Camera poses and 3D reconstruction of the doors shown in figure 10

Fig. 12

 12 Fig. 12 Reprojection of some reconstructed 3D lines to the first fish-eye image in figure 10 with (blue) and without (red) bundle adjustment

Fig. 13

 13 Fig. 13 Fish-eye and perspective images with point and line correspondences Door 1 Door 2 5-point (cm) -error (%) 242 -19.21 199 -1.97 Line (cm) -error (%) 228 -12.31 206 -1.48 Point-and-line (cm) -error (%) 229 -12.81 206 -1.48 Real height (cm) 203 203 Door 3 Door 4 5-point (cm) -error (%) 215 -5.91 212 -4.43 Line (cm) -error (%) 206 -1.48 200 -1.48 Point-and-line (cm) -error (%) 206 -1.48 204 -0.49 Real height (cm) 203 203

Fig. 14

 14 Fig. 14 Reprojection of some reconstructed 3D lines to the first fish-eye image in figure 13. The camera poses were computed by different approaches: 5-point (red), line-based (green) and point-and-line-based (blue).

Fig. 15

 15 Fig.15Cameras with partially non-overlapping FOV. Each node is composed of at least three cameras which are linked together by baselines of the same style and color. Two different nodes share three common cameras.

Fig. 16

 16 Fig. 16 Panoramic view

Fig. 17

 17 Fig. 17Images captured by perspective and fish-eye cameras with line correspondences. The camera configuration is illustrated in figure 15. Each column illustrates one node of cameras.The camera indexes from upper to lower images: the first node (C 1 ,C 2 ,C 3 ,C 4 ), the second node (C 1 ,C 2 ,C 3 ,C 5 ,C 6 ,C 7 ) and the third node (C 8 ,C 9 ,C 5 ,C 6 ,C 7 )

  Fig. 17Images captured by perspective and fish-eye cameras with line correspondences. The camera configuration is illustrated in figure 15. Each column illustrates one node of cameras.The camera indexes from upper to lower images: the first node (C 1 ,C 2 ,C 3 ,C 4 ), the second node (C 1 ,C 2 ,C 3 ,C 5 ,C 6 ,C 7 ) and the third node (C 8 ,C 9 ,C 5 ,C 6 ,C 7 )

Table 3

 3 Reconstruction result of the door sequence shown in figure 10 by line-based approach

	Door 1	Door 2

Table 4

 4 Reconstruction result of the door sequence shown in figure 13 by different approaches