Olivier Saurer
email: saurero@inf.ethz.ch

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

Rémi Boutteau
email: remi.boutteau@esigelec.fr

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

Marc Pollefeys
email: marc.pollefeys@inf.ethz.ch

Friedrich Fraundorfer
email: fraundorfer@icg.tugraz.at

R Émi Boutteau

Édric Demonceaux

Homography Based Egomotion Estimation with a Common Direction

Keywords: Computer vision, egomotion estimation, homography estimation, structure-from-motion. !

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

N OWADAYS, point-based methods to estimate the motion of a camera are well known. If the camera is uncalibrated, eight or seven points are needed to estimate the fundamental matrix between two consecutive views [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. When the intrinsic parameters of the camera are known, five points are then enough to estimate the essential matrix [START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF]. To decrease the sensitivity of these methods, a robust framework such as Random Sample Consensus (RANSAC) is necessary. Thus, reducing the number of needed matched points between views is important in terms of computation efficiency and of robustness improvement. For example, as shown in Figure 1, for a probability of success of 0.99 and a rate of outliers equal to 0.5, the number of RANSAC trials is divided by eight, if five points are used instead of eight. In the case of a robust estimation based on eight points, 1177 trials are necessary whereas 145 are sufficient if only five points are required. Thus, finding a minimal solution for egomotion estimation is important for robust real time applications.

However, reducing the number of necessary points is only possible if some hypotheses or supplementary data are available. For example, if we know a common direction between the two views, three points can then be used to estimate the full essential matrix [START_REF] Fraundorfer | A minimal case solution to the calibrated relative pose problem for the case of two known orientation angles[END_REF]. Extreme Manuscript received February 16, 2016; revised ?? ??, 20??.

situations appear when a planar non-holonomic motion is supposed [START_REF] Scaramuzza | 1-point-ransac structure from motion for vehiclemounted cameras by exploiting non-holonomic constraints[END_REF] or when the metric velocity of a single camera can be estimated knowing its attitude and its acceleration [START_REF] Kneip | Closed-form solution for absolute scale velocity determination combining inertial measurements and a single feature correspondence[END_REF]. In these cases, only one point allows to estimate the motion. These initial hypotheses or additional knowledges can then deal with the pose of the camera or with the 3D structure of the scene. For example, if the 3D points belong to a single plane, the egomotion estimation is reduced to a homography computation between two views, that can be calculated using only four points [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. In many scenes and many applications, the scene plane hypothesis seems suitable. Indeed, in many scenarios such as indoor or street corridors and more generally in man made environments, this assumption holds. Thus, in this paper we investigate the cases where at least one plane is present in the scene and where we have some partial knowledge about the pose of the camera. We suppose that we are able to extract a common direction between consecutive views and we can have some information about the normal of the considered plane. Obtaining a common direction can be easily performed thanks to an IMU (Inertial Measurement Unit) associated with the camera, which is often the case in mobile devices or UAV (Unmanned Aerial Vehicle). The coupling with a camera is then very easy and can then be used for different computer vision tasks [START_REF] Viéville | Computation of egomotion and structure from visual and inertial sensors using the vertical cue[END_REF], [START_REF] Corke | An inertial and visual sensing system for a small autonomous helicopter[END_REF], [START_REF] Lobo | Vision and inertial sensor cooperation using gravity as a vertical reference[END_REF], [START_REF] Weiss | Real-time metric state estimation for modular vision-inertial systems[END_REF], [START_REF] Domke | Integration of visual and inertial information for egomotion: a stochastic approach[END_REF]. Without any external sensor, this common direction can also be directly extracted from the images thanks to vanishing points [START_REF] Bazin | A branch-and-bound approach to correspondence and grouping problems[END_REF] or horizon detection [START_REF] Oreifej | Horizon constraint for unambiguous uav navigation in planar scenes[END_REF].

In this work, assuming the roll and pitch angles of the camera as known, we propose to find a minimal closedform solution for homography estimation in man made environments. We will derive different solutions depending on the prior knowledge about the 3D scene : the camera egomotion. In this case, the solution is unique and contrary to the other algorithms for essential matrix estimation, there is no supplementary verification for finding the good solutions among the different possibilities.

•

If the considered points are on a vertical plane, we propose an efficient 2.5pt formulation in order to retrieve the motion of the camera and the normal of the plane related to the pose of the camera. This solution allows for an early reject of a pose hypothesis by including a consistency check on the three point correspondences.

• If the plane orientation is completely unknown, we develop a minimal solution using only three points instead of four points needed in the classical homography estimation.

All these methods will be evaluated on synthetic and real data and compared with different methods proposed in the literature. The rest of the paper is organized as follows. In the second part, we describe the different existing methods in the literature which deal with minimal solution for egomotion estimation. In the next section, we explain how to reduce the number of points for estimating the homography between two views and derive the proposed solutions according to the prior knowledge. In the fourth section, we show the behaviour of our solutions on synthetic and real data and compare with other classical methods in a quantitative evaluation. Finally, we will conclude by providing some extents to this work.

RELATED WORKS

When the camera is not calibrated, at least 8 or 7 points are needed to recover the motion between views [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. It's well known, that if the camera is calibrated, only 5 feature point correspondences are sufficient to estimate the relative camera pose. Reducing this number of points can be very interesting in order to reduce the computation time and to increase the robustness when using a robust estimator such as RANSAC. The reduction of the degree of freedom (DoF) number and consequently the number of matched points between images can be achieved by introducing some constraints on the camera motion (planar for example) or the feature points (on the same plane) or by using some additional information provided by other sensors such as IMU for instance.

For example, if all the 3D points lie on a plane, a minimum of 4 points is required to estimate the motion of the camera between two-views [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. On the other hand, if the camera is embedded on a mobile robot which moves on a planar surface, only 2 points are required to recover the motion [START_REF] Ortin | Indoor robot motion based on monocular images[END_REF] and if in addition the mobile robot has non-holonomic constraints only one point is necessary [START_REF] Scaramuzza | 1-point-ransac structure from motion for vehiclemounted cameras by exploiting non-holonomic constraints[END_REF]. Similarly, if the camera moves in a plane perpendicular to the gravity, 1 point correspondence is sufficient to recover the motion as shown by Troiani et al. [START_REF] Troiani | 1-pointbased monocular motion estimation for computationally-limited micro aerial vehicles[END_REF].

The number of points needed to estimate the egomotion can be also reduced if some information about the relative rotation between two poses are available. This information can be given by vanishing points extraction in the images [START_REF] Bazin | Rotation estimation and vanishing point extraction by omnidirectional vision in urban environment[END_REF] or by taking into account extra information given by an additional sensor. Thus, Li et al. [START_REF] Li | A 4-point algorithm for relative pose estimation of a calibrated camera with a known relative rotation angle[END_REF] show that in the case of an IMU associated to the camera, only 4 points are sufficient to estimate the relative motion even if the extrinsic calibration between the IMU and the camera is not known.

Similarly, some different algorithms have been recently proposed in order to estimate the relative pose between two cameras by knowing a common direction. It has been demonstrated that knowing roll and pitch angles of the camera at each frame, only three points are needed to recover the yaw angle and the translation of the camera motion up to scale [START_REF] Fraundorfer | A minimal case solution to the calibrated relative pose problem for the case of two known orientation angles[END_REF], [START_REF] Kalantari | A new solution to the relative orientation problem using only 3 points and the vertical direction[END_REF], [START_REF] Naroditsky | Two efficient solutions for visual odometry using directional correspondence[END_REF]. In these approaches, only the formulation of the problem is different and consequently the way to solve it. All these works start with a simplified essential matrix in order to derive a polynomial equation system. For example, in [START_REF] Kalantari | A new solution to the relative orientation problem using only 3 points and the vertical direction[END_REF], their parametrization leads to 12 solutions by using the Macaulay matrix method. The correct solution has then to be found among a set of possible solutions. The approach presented in [START_REF] Fraundorfer | A minimal case solution to the calibrated relative pose problem for the case of two known orientation angles[END_REF] permits to obtain a 4 th -order polynomial equation and consequently leads to a more efficient solution. In [START_REF] Naroditsky | Two efficient solutions for visual odometry using directional correspondence[END_REF], the authors propose a closed-form solution to this 4 th -order polynomial equation that allows a faster computation.

For a further reduction of necessary feature points, stronger hypotheses have to be added. If the complete rotation between the two views are known, only 2 degrees of freedom corresponding to the translation up-to-scale has to be estimated and consequently 2 points are sufficient to solve the problem [START_REF] Troiani | 2point-based outlier rejection for camera-imu systems with applications to micro aerial vehicles[END_REF], [START_REF] Bazin | Motion estimation by decoupling rotation and translation in catadioptric vision[END_REF]. In this case, the authors compute the translation vector using the epipolar geometry given the rotation. Thus, these approaches allow to reduce the number of points but also imply the knowledge of the complete rotation between two views making the pose estimation very sensitive to IMU inaccuracy. More recently, Martinelli [START_REF] Martinelli | Closed-form solution of visual-inertial structure from motion[END_REF] proposes a closed-form solution for structure from motion knowing the gravity axis of the camera in a multiple view scheme. He shows that at least three feature points lying on a same plane and three consecutive views are required to estimate the motion. In the same way, the plane constraint has been used for reducing the complexity of the bundle adjustment (BA) in a visual simultaneous localization and mapping (SLAM) embedded on a microaerial vehicle (MAV) [START_REF] Lee | Mav visual slam with plane constraint[END_REF].

Most closely related papers to our approach are the works of [START_REF] Fraundorfer | A minimal case solution to the calibrated relative pose problem for the case of two known orientation angles[END_REF], [START_REF] Naroditsky | Two efficient solutions for visual odometry using directional correspondence[END_REF] in which they simplify the essential matrix knowing the vertical of the cameras. In this work, to reduce the number of points, rather than deriving the epipolar constraint to compute the essential matrix, we propose to use the homography constraint between two views. Thus, we suppose that a significant plane exists in the scene and that the gravity direction is known. Let us note that recently, in [START_REF] Troiani | A 3 Points Vision Based Approach for MAV Localization in GPS Denied Environments[END_REF] Troiani et al. have also proposed a method using 2 points on the ground plane with the knowledge of the vertical of the camera. However, they do not use the homography formalism and their method requires to know the distance between the two 3D points. In our method, this hypothesis is not necessary and we only assume that the points lie on a same plane. The Manhattan world assumption [START_REF] Coughlan | Manhattan world: Compass direction from a single image by bayesian inference[END_REF] has also recently successfully been used for multi-view stereo [START_REF] Furukawa | Manhattanworld stereo[END_REF], the reconstruction of building interiors [START_REF]Reconstructing building interiors from images[END_REF] and also for scene reconstruction from a single image only [START_REF] Lee | Geometric reasoning for single image structure recovery[END_REF]. Our contribution differs from them, as we combine gravity measurements with the weak Manhattan world assumption. This paper is an extension of [START_REF] Saurer | Homography based visual odometry with known vertical direction and weak manhattan world assumption[END_REF], [START_REF] Saurer | A homography formulation to the 3pt plus a common direction relative pose problem[END_REF] where we studied camera pose estimation based on homographies with a common vertical direction and a known or at least partially known plane normal. In [START_REF] Saurer | Homography based visual odometry with known vertical direction and weak manhattan world assumption[END_REF] we proposed a homography based pose estimation algorithm that does not require any knowledge on the plane normal. In fact the algorithm provides the plane normal in addition to the camera pose.

MOTION ESTIMATION

Knowing the vertical direction in images will simplify the estimation of camera pose and camera motion, which are fundamental methods in 3D computer vision. It is then possible to align every camera coordinate system with the measured vertical direction such that the z-axis of the camera is parallel to the vertical direction and the x-y-plane of the camera is orthogonal to the vertical direction (illustrated in Fig. 2). In addition, this would mean that the x-y-plane of the camera is now parallel to the world's ground plane and the z-axis is parallel to vertical walls.

General case

Aligned with gravity direction gravity Fig. 2. Alignment of the camera with the gravity direction.

This alignment can just be done as a coordinate transform for motion estimation algorithms, but also be implemented as image warping such that feature extraction methods benefit from it. Relative motion between two such aligned cameras reduces to a 3-DOF motion, which consists of 1 remaining rotation and a 2-DOF translation vector (i.e., a 3D translation vector up to scale).

The algorithms for estimating the relative pose are derived from a homography formulation, where a plane is observed in two images. The homography is then decomposed into a relative rotation and translation between the two images. By incorporating the known vertical direction, the parametrization of the pose estimation problem is greatly reduced from 5-DOF to 3-DOF. This simplification leads to a closed-form 2pt and a 2.5pt algorithm to compute the homography. By relaxing the assumption of strictly vertical or horizontal structures and making use of the known gravity direction, the homography formulation results in a closed form solution requiring 3-points only.

In the following subsections we derive the 2pt algorithm for the known plane normal cases (ground and vertical plane), then we provide a derivation of the 2.5pt and 3pt algorithm for a known gravity direction with an unknown plane orientation.

2pt Relative Pose for Points on the Ground Plane

The general homographic relation for points belonging to a 3D plane and projected in two different views is defined as follows :

q j = Hq i , (1)
with q i = [x i , y i , w i ] and q j = [x j , y j , w j ] the projective coordinates of the points between the views i and j. H is given by:

H = R - 1 d tn , (2)
where R and t are respectively the rotation and the translation between views i and j and where d is the distance between the camera i and the 3D plane described by the normal n.

In our case, we assume that the camera intrinsic parameters are known and that the points q i and q j are normalized. We also consider that the attitude of the cameras for the both views are known and that these attitude measurements have been used to align the camera coordinate system with the ground plane. In this way, only the yaw angle θ between the two views remains unknown. Therefore equation 2 can be expressed as:

H = R z - 1 d tn, (3)
where R z denotes the unknown rotation around the yaw angle (z-axis). Similarly, since we consider that the ground plane constitutes the visible 3D plane during the movement of the camera, we can note that n = [0, 0, 1] . Consequently, equation 3 can be written as:

H =   cos(θ) -sin(θ) 0 sin(θ) cos(θ) 0 0 0 1   - t d   0 0 1   , (4)
d being unknown, the translation can be known only up to scale. Consequently, the camera-plane distance d is set to 1 and absorbed by t. We then obtain:

H =   cos(θ) -sin(θ) 0 sin(θ) cos(θ) 0 0 0 1   -   t x t y t z     0 0 1   , (5) =   cos(θ) -sin(θ) -t x sin(θ) cos(θ) -t y 0 0 1 -t z   . ( 6
)
In a general manner, this homography can be parametrized as

H =   h 1 -h 2 h 3 h 2 h 1 h 4 0 0 h 5   . (7)
The problem consists of solving for the five entries of the homography H. We consider the following relation:

q j × Hq i = 0, (8)
where × denotes the cross product. By rewriting the equation, we obtain:

  x j y j w j   ×   h 1 -h 2 h 3 h 2 h 1 h 4 0 0 h 5     x i y i w i   = 0. (9)
This gives us three equations, where two of them are linearly independent. We expand the above equation and consider only the first two linearly independent equations, which results in:

-w j y i h 1 -w j x i h 2 -w i w j h 4 + w i y j h 5 w j x i h 1 -w j y i h 2 + w i w j h 3 -w i x j h 5 = 0. (10)
The equation system can be re-written into:

-w j y i -w j x i 0 -w i w j w i y j w j x i -w j y i w i w j 0

-w i x j       h 1 h 2 h 3 h 4 h 5       = 0. (11)
The above equation represents a system of equations of the form Ah = 0. It is important to note that A has rank 4. Since each point correspondence gives rise to two independent equations, we require two point correspondences to solve for h up to one unknown scale factor. The singular vector of A, which has the smallest singular value spans a one dimensional (up to scale) solution space. We chose the solution h such that ||h|| = 1. Then, to obtain valid rotation parameters we enforce the trigonometric constraint h 2 1 + h 2 2 = 1 on h, by dividing the solution vector by

± h 2 1 + h 2 2 .
The camera motion parameters, can directly be derived from the homography:

t = -h 3 , -h 4 , 1 -h 5 , (12)
R =   h 1 -h 2 0 h 2 h 1 0 0 0 1   . ( 13
)
Due to the sign ambiguity in ± h 2 1 + h 2 2 we obtain two possible solutions for R and t. An alternative solution is proposed in Appendix A which uses an inhomogeneous system of equations to solve for the unknown camera pose.

2pt Relative Pose for a Known Vertical Plane Normal

The following algorithm is able to compute the relative pose given 2 point correspondences and the normal of the plane on which the points reside. The derivation will be carried out for a vertical plane but works similar for planes parametrized around other axis.

The homography for a vertical plane can be written as:

H = R z -[t x , t y , t z ] [n x , n y , 0], (14)
where R z denotes the rotation matrix around the z-axis.

Expanding the expression in ( 14) we obtain:

H =   cos(θ) -n x t x -sin(θ) -n y t x 0 sin(θ) -n x t y cos(θ) -n y t y 0 -n x t z -n y t z 1   , ( 15
) =   h 1 h 2 0 h 3 h 4 0 h 5 ny nx h 5 1   . ( 16
)
This leaves 5 entries in H to be estimated. Each point correspondence gives 2 inhomogeneous linearly independent equations of the form Ah = b. Using equation 8 we obtain:

-d -h 3 a -h 4 b + h 5 x i y j + h 5 y i c -e + h 1 a + h 2 b -h 5 x i x j -h 5 x j c = 0, (17)
0 0 -a -b x i y j + y i c a b 0 0 -x i x j -x j c       h 1 h 2 h 3 h 4 h 5       = d e , (18)
with:

a = w j x i , b = w j y i , c = y j n y n x , d = -w i y j , e = w i x j .
Using 2 point correspondences, this gives 4 equations which is a deficient-rank system. The solution is h = Vy + λv (see [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]) where svd(A) = UDV and v is the last column vector of V. The vector y is computed by

y i = b i /d i where d i is the i th diagonal entry of D and b = U b.
This leaves the unknown scalar λ which can be computed from the additional trigonometric constraint (cos 2 (θ) + sin 2 θ) -1 = 0).

The trigonometric constraint can be fully expressed in terms of the variables

h 1 , h 2 , h 3 , h 4 . cos(θ) 2 + sin(θ) 2 -1 = 0, ( 19
) (h 1 + n x t x ) 2 + (-h 2 -n y t x ) 2 -1 = 0, (20)
with:

t x = n x (h 4 -h 1 ) -n y (h 2 + h 3 ). (21)
Substituting symbolically the entries of h = Vy + λv into Eq. 20 results in a quadratic equation in the remaining unknown λ (the expanded equation is not shown due to its excessive length). Solving for the variable λ gives two solutions for the parameters

h 1 , h 2 , h 3 , h 4 , h 5 .
Once the homography H is estimated it can be decomposed into relative rotation and relative translation parameters. We back-substitute the entries of H from [START_REF] Li | A 4-point algorithm for relative pose estimation of a calibrated camera with a known relative rotation angle[END_REF], that is h 1 , h 2 , h 3 , h 4 and h 5 into (15). Knowing n x and n y , the translation parameters can directly be computed using the following relations:

t z = -h 5 n x , (22)
t x = n x (h 4 -h 1 ) -n y (h 2 + h 3 ), (23)
t y = n y (h 1 -h 4 ) -n x (h 2 + h 3 ). ( 24
)
And the rotation parameter is then obtained through:

cos(θ) = h 1 + n x t x . ( 25
)

2.5pt Relative Pose with Unknown Vertical Plane Normal

The 2.5pt algorithm is an extension of the 2pt algorithm described in section 3.2. The homography is parametrized as in [START_REF] Troiani | 1-pointbased monocular motion estimation for computationally-limited micro aerial vehicles[END_REF]. However, when the plane normal n is not known it is not possible to make use of the same linear constraint, thus all the 6 parameters of H have to be estimated. To do so, one more equation is required which can be taken from a third point. Thus the constraint equations of 2 points and 1 of the equations from a third point are stacked into an equation system of the form Ah = b. For one point correspondence two equations can be derived as follows.

First the homography is defined as:

H =   cos(θ) -n x t x -sin(θ) -n y t x 0 sin(θ) -n x t y cos(θ) -n y t y 0 -n x t z -n y t z 1   , ( 26
) =   h 1 h 2 0 h 3 h 4 0 h 5 h 6 1   . ( 27
)
Computing q j × Hq i leads to:

-c -h 3 a -h 4 b + h 5 x i y j + h 6 y i y j -d + h 1 a + h 2 b -h 5 x i x j -h 6 x j y i = 0, (28) 0 0 -a -b x i y j y i y j a b 0 0 -x i x j -x j y i         h 1 h 2 h 3 h 4 h 5 h 6         = c d , (29)
with:

a = w j x i , b = w j y i , c = -w i y j , d = w i x j .
As in section 3.2 the solution to this system is of the form h = Vy + λv. The unknown scalar λ can be computed utilizing the trigonometric constraint and a constraint on the normal vector:

cos 2 (θ) + sin 2 (θ) -1 = 0, ( 30
) n 2 x + n 2 y = 1. (31)
Starting from equation 30 the constraint can be derived by substituting cos(θ) and sin(θ) with expressions in h 1 and h 2 . In a next step t x is substituted with equation 21.

The relation n 2

x + n 2 y = 1 can be used to cancel out many terms in the equation and one obtains:

h 2 1 n 2 y + h 2 2 n 2 x + h 2 3 n 2 y + h 2 4 n 2 x -2(h 1 h 2 + h 3 h 4 )n x n y -1 = 0. (32)
Using [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF][START_REF] Sch Önberger | Structure-from-motion for mav image sequence analysis with photogrammetric applications[END_REF] the equation can be rewritten in terms of h 1 , h 2 , h 3 , h 4 , h 5 :

h 2 1 h 2 6 -2h 1 h 2 h 5 h 6 + h 2 2 h 2 5 + h 2 3 h 2 6 -2h 3 h 4 h 5 h 6 + h 2 4 h 2 5 -h 2 5 -h 2 6 = 0. ( 33
)
Substituting symbolically the entries of h = Vy + λv into equation 33 results in a 4 th order polynomial in the remaining unknown λ (the expanded equation is not shown due to its excessive length). Root solving for the variable λ gives 4 solutions for the parameter sets h 1 , h 2 , h 3 , h 4 , h 5 .

The decomposition of the homography into translation and rotation parameters of the relative motion follows the same steps as the one in section 3.2. However, it differs as the normals n x and n y are not given and need to be computed in the process. We again back-substitute the entries of H from ( 27) into [START_REF]Reconstructing building interiors from images[END_REF]. First we compute t z using the relation n 2

x + n 2 y = 1,

t z = ± h 2 5 + h 2 6 . (34)
This gives two solutions for t z which differ in the sign and which leads to two further sets of derived solution sets. Now the unknown normals can be computed.

n x = -h 5 t z , (35)
n y = -h 6 t z . ( 36
)
After this the procedure of section 3.2 can be followed again to compute the remaining parameters with the following equations, however, using both solutions for t z , n x and n y ,

t x = n x (h 4 -h 1 ) -n y (h 2 + h 3 ), (37)
t y = n y (h 1 -h 4 ) -n x (h 2 + h 3 ). ( 38
)
The angle θ can be computed from the relation

cos(θ) = h 1 + n x t x . (39)
An interesting fact in this case is, that only one of the two available equations from the third point is used. Although for the RANSAC loop it is still necessary to sample 3 points for this method, it is now possible to do a consistency check on the third point correspondence. To be an outlier free homography hypothesis the one remaining equation has also to be fulfilled. This can easily be tested and if it is not fulfilled the hypothesis is prematurely rejected. This gives a computational advantage over the standard 3pt essential matrix method [START_REF] Fraundorfer | A minimal case solution to the calibrated relative pose problem for the case of two known orientation angles[END_REF], because inconsistent samples can be detected without testing on all the other point correspondences.

3pt Relative Pose using the Homography Constraint

In this section we discuss a 3pt formulation of the camera pose estimation with a known vertical direction. It differs from the algorithms in the previous section as it does not need the presence of scene planes. A 3pt algorithm has already been presented by [START_REF] Fraundorfer | A minimal case solution to the calibrated relative pose problem for the case of two known orientation angles[END_REF] but using an essential matrix formulation. With this 3pt algorithm we propose an alternative to the previous essential matrix algorithm but based on a homography formulation. We start from [START_REF] Troiani | 1-pointbased monocular motion estimation for computationally-limited micro aerial vehicles[END_REF], instead of assuming the plane to be parallel to the gravity vector we don't make any assumption on the plane orientation and therefore use 3 parameters n x , n y , n z , for the fully unknown plane normal, which leads to:

H = R z -[t x , t y , t z ] [n x , n y , n z ]. (40)
The camera-plane distance is absorbed by t the same way as in the previous sections.

The homography matrix then consists of the following entries:

H =   cos(θ) -t x n x -sin(θ) -t x n y -t x n z sin(θ) -t y n x cos(θ) -t y n y -t y n z -t z n x -t z n y 1 -t z n z   . ( 41
)
The unknowns we are seeking for are the motion parameters cos(θ), sin(θ), t x , t y , t z and the normal [n x , n y , n z ] of the plane spanned by the 3 point correspondences. Recall that the standard 3pt essential matrix algorithm only solves for the camera motion, while the 3pt homography algorithm provides the camera motion and a plane normal with the same number of correspondences. To solve for the unknowns we setup an equation system of the form: q j × Hq i = 0 and expand the relations to obtain the following two polynomial equations: at y -bt z -w j x i sin(θ) -w j y i cos(θ) + y j w i = 0, (42) -at x + ct z + w j x i cos(θ) -w j y i sin(θ) -x j w i = 0, (43) where:

a = w j x i n x + w j y i n y + w j n z w i , b = y j w i n z + y j n x x i + y j n y y i , (44) c = x j n x x i + x j w i n z + x j n y y i .
The third equation obtained from q j × Hq i = 0 is omitted since it is a linear combination of the two other equations. Therefore each point correspondence gives 2 linearly independent equations and there are two additional quadratic constraints, the trigonometric constraint and the unit length of the normal vector that can be utilized:

sin 2 (θ) + cos 2 (θ) = 1, (45) n 2 x + n 2 y + n 2 z = 1. (46)
The total number of unknowns is 8 and the two quadratic constraints together with the equations from 3 point correspondences give a total of 8 polynomial equations in the unknowns. An established way to find an algebraic solution to such a polynomial equation system is by using the Gr öbner basis technique [START_REF] Cox | Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3/e[END_REF]. By computing the Gr öbner basis a univariate polynomial can be found which allows to find the value of the unknown variable by root solving.

The remaining variables can then be computed by backsubstitution. To solve our problem we use the automatic Gr öbner basis solver by Kukelova et al. [START_REF] Kukelova | Automatic generator of minimal problem solvers[END_REF], which can be downloaded at the authors webpage. The software automatically generates Matlab-Code that computes a solution to the given polynomial equation system (in our case the above specified 8 equations). The produced Matlab-Code consists of 299 lines and thus cannot be given here. The analysis of the Gr öbner basis solutions shows, that the final univariate polynomial has degree 8, which means that there are up to 8 real solutions to our problem.

Degenerate Configurations

In this section we discuss the degenerate conditions for the proposed algorithms. In previous works [START_REF] Fraundorfer | A minimal case solution to the calibrated relative pose problem for the case of two known orientation angles[END_REF], [START_REF] Naroditsky | Two efficient solutions for visual odometry using directional correspondence[END_REF], [START_REF] Kalantari | A new solution to the relative orientation problem using only 3 points and the vertical direction[END_REF] the degenerate conditions for the standard 3pt method for essential matrix estimation have been investigated in detail. In these papers multiple degenerate conditions are identified. It is also pointed out that a collinear configuration of 3D points is in general not a degenerate condition for the 3pt method, while it is one for the 5pt method. Degenerate conditions for the standard 3pt algorithm however are collinear points that are parallel to the translation direction and points that are coplanar to the translation vector. We investigated if these scenarios also pose degenerate conditions for our proposed algorithms, the 2pt, 2.5pt and 3pt homography method by conducting experiments with synthetic data. Degenerate cases could be identified by a rank loss of the equation system matrix or for the Gr öbner basis case as a rank loss of the action matrix. For the 3pt homography case this revealed that the proposed method shares the degenerate conditions of the standard 3pt method but in addition also has a degenerate condition for the case of collinear points. This is understandable as the 3pt homography method also solves for the plane normal which then has an undefined degree of freedom around the axis of the collinear points. For the 2pt (both 2pt methods share the same properties) and 2.5pt algorithm these special cases however, do not pose degenerate conditions. More information in case of knowledge or partial knowledge of plane parameters allows to avoid degeneracy in the cases critical for the more general 3pt methods. The results of the comparison are summarized in Table 1.

EXPERIMENTS

Synthetic Evaluation

To evaluate the algorithms on synthetic data we chose the following setup. The average distance of the scene to the first camera center is set to 1. The scene consists of two planes, one ground plane and one vertical plane which is parallel to the image plane of the first camera. Both planes consist of 200 randomly sampled points. The baseline between two cameras is set to be 0.2, i.e., 20% of the average scene distance, and the focal length is set to 1000 pixels, with a field of view of 45 degrees. Each algorithm is evaluated under varying image noise and increasing IMU noise. Each of the two setups is evaluated under a forward, into the scene (along the z-axis) and a sideways (along the x-axis) translation of the second camera.

In addition the second camera is rotated around each axis.

To evaluate the robustness of the algorithms we compare the relative translation and rotation separately. The error measure compares the angle difference between the true rotation and the estimated rotation. Since the translation is only known up to scale, we compare the angle between the true-and estimated translation. The errors are computed as follows:

• Angle difference in R: ξ R = arccos((Tr(R Ṙ ) -1)/2) • Direction difference in t: ξ t = arccos((t ṫ)/( t ṫ ))
Where R, t denote the ground-truth transformation and Ṙ, ṫ are the corresponding estimated transformations.

Each data point in the plots represents the 5-quantile 1 (Quintiles) of 1000 measurements.

Relative Pose

Fig. 3 and Fig. 4 compare the 2-point algorithm to the general 5pt-essential matrix [START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF], 4pt-homography [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF] and 3ptessential matrix [START_REF] Fraundorfer | A minimal case solution to the calibrated relative pose problem for the case of two known orientation angles[END_REF] algorithms. Notice, in these experiments the camera poses were computed from points randomly drawn from the ground plane. Since camera poses estimated from coplanar points do not provide a unique solution for the 5pt, 4pt and 3pt-essential matrix algorithm we evaluate each hypothesis with all points coming from both planes. The solution providing the most inliers is chosen to be the correct one. This evaluation is used in all our synthetic experiments. Similarly Fig. 5 and Fig. 6 show a comparison of the 2.5pt algorithm with the general 5pt, the 4pt and the 3pt-essential matrix algorithms. Here the camera poses are computed from points randomly sampled from the vertical plane only. The evaluation shows that knowing the vertical direction and exploiting the planarity of the scene improves motion estimation. The 2pt and 2.5pt algorithms outperform the 5pt and 4pt algorithm, in terms of accuracy. Under perfect IMU measurements the algorithms are robust to image noise and perform significantly better than the 5pt and 4pt algorithm. With increasing IMU noise their performance are still comparable to the 5pt algorithm and superior to the 4pt algorithm.

1. The k-quantile represents the boundary value of the k th interval when dividing ordered data into k regular intervals. For k = 2, the 2-quantile represents the median value.

3pt Homography

Fig. 7 and Fig. 8 compare the 3pt-homography based algorithm to the general 5pt [START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF] and the 3pt-essential matrix algorithms [START_REF] Fraundorfer | A minimal case solution to the calibrated relative pose problem for the case of two known orientation angles[END_REF]. The evaluation shows that the proposed method outperforms the 5pt algorithm, in terms of accuracy. Under perfect IMU measurements the algorithm is robust to image noise and performs significantly better than the 5pt algorithm and equally good as the 3pt-essential matrix algorithm. With increasing IMU noise the performance of the 3pt-essential matrix and 3pt-homography algorithms are still comparable to the 5pt algorithm.

Timings

We evaluate the run-time of all algorithms on an Intel i7-2600K 3.4GHz using Matlab. To provide a fair comparison all algorithms were implemented in Matlab. No mex files were used, except for the reduced row echelon function rref, which is required by the 3pt-essential and 3pt-homography algorithms. All timings were averaged over 1000 runs. Table 2 summarizes the run-times for each of the six algorithms. The high run time of the 3pt-homography algorithm is due to the complexity of the Gr öbner basis solution, which has to perform Gauss-Jordan elimination on the 443x451 elimination matrix.

For one RANSAC iteration the timings can vary drastically between algorithms. This is due to the different solution spaces the algorithms provide. To have the same error measure for all algorithms, we choose to use the reprojection error to select the correct camera poses among a set of possible poses. For instance the 2pt algorithm provides one unique camera pose, while the 5pt algorithm can provide up to 10 different essential matrices. In addition for each essential matrix 4 possible camera poses exist and need to be verified to find the correct pose, which can result in a total of 40 possible camera poses. While the homography formulations directly provide sets of camera poses. Even though the hypothesis estimation of the 3pt-homography algorithm has a larger constant time complexity, compared to its essential matrix counter part, one RANSAC iteration is cheaper, since fewer potential poses need to be evaluated. The table clearly shows that the computation time is dominated by the hypothesis selection (re-projection error computation) and not by the solver. In all experiments we used a set of 200 point correspondences.

Real Data Experiments

In the following section we evaluate the proposed algorithms on both an indoor and outdoor environment.

Error Measure

In order to compare the estimated camera poses to the ground-truth, we used the relative pose error (RPE) measure as proposed by Sturm [START_REF] Sturm | A benchmark for the evaluation of rgb-d slam systems[END_REF]. The RPE compares the local accuracy of the trajectory over a fixed time interval ∆, that corresponds to the drift of the trajectory. The RPE at time step i can be defined as:

E i = (Q -1 i Q i+∆ ) -1 (P -1 i P i+∆ ), (47)
where Q i , P i ∈ SE(3) represent the ground truth and estimated poses respectively. E i then represents the relative error. For a sequence of n camera poses, m = n -∆ individual relative pose errors are then estimated. From these errors, we propose to compute the root mean squared error (RMSE) over all time indices of the translational component as

RM SE(E 1:n , ∆) = 1 m m i=1 trans(E i ) 2 , ( 48
)
where trans(E i ) refers to the translational components of the relative pose error E i .

Vicon Dataset

In order to have a practical evaluation of the 2pt, 2.5pt and 3pt algorithms, several real datasets have been collected with reliable ground-truth, see Fig. 9. The ground-truth data has been obtained by conducting the experiments in a room equipped with a Vicon motion capture system made of 22 cameras. We used the Vicon data as inertial measures and scale factor in the different experiments. The sequences have been acquired with a perspective camera mounted either on teleoperated Segway mobile robot (Fig. 9) or with a handheld system in order to have planar and 3D trajectories. In both cases the cameras are synchronized with the Vicon system. The image resolution used is 1624 × 1234 pixels. The length of these trajectories is between 20 and 50 meters and the number of images is between 150 and 350 per sequence. Robot motion speed is about 1m/s. Two different sets have been acquired, one set showing the ground plane dominantly and another set showing the walls dominantly.

We perform a comparison of the 2pt, 2.5pt and 3pthomography with the 5pt algorithm in order to show the efficiency of the proposed methods. First, we use [START_REF] Vedaldi | VLFeat: An open and portable library of computer vision algorithms[END_REF] to extract and match SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] features. The same matched feature point sets are used for the different algorithms and form the input to RANSAC [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] in order to select the inliers. For RANSAC we use a fixed number of 100 iterations, in all our experiments.

Figure 10 shows the evaluation of the 2pt ground plane algorithm. The trajectories obtained with 2pt (red curve) and 5pt (black curve) are compared with the ground-truth (blue curve) from Vicon. In all these experiments, even if both approaches propose trajectories globally with a similar shape than the ground-truth, we can note that the 2pt algorithm provides better results than the 5pt method. In the case of planar trajectories, that is sequence I, II, IV in Fig. 10, it is worth noting that the 2pt algorithm has a very low drift in the vertical axis while the 5pt accumulates significant error. Over the six sequences, the mean angular error in translation is equal to 0.1883 radians for the 2pt and 0.3380 for the 5pt.

The root mean squared error as defined in equation 48 is given for all 6 sequences in Table 3. The 2pt clearly outperforms the 5pt algorithm, providing a 1.69 × -6.54× lower error compared to the 5pt algorithm.

Figure 11 compares the different trajectories obtained from the 2.5pt (red curve), the 3pt-homography algorithm (green curve), the 3pt-essential matrix algorithm (magenta curve) and the 5pt (black curve), to the ground-truth (blue curve) obtained from the Vicon system.

In Table 4 we compare the RMS-error of the different algorithms. The 2.5pt algorithm shows similar performance compared to the standard 5pt algorithm and both 3pt algorithms, however having the advantage of a much simpler derivation.

This experiments also demonstrated that the assumptions taken for the 2pt algorithm (flat ground plane) and for the 2.5pt algorithm (vertical walls) are met in practical situations and can be used in real applications.

2pt Algorithm in a SFM Pipeline

In this final experiment we demonstrate the usage of the 2pt algorithm within an incremental SFM pipeline. The 2pt algorithm is used to replace the 5pt algorithm within the SFM pipeline. For this experiment the MAVMAP [START_REF] Sch Önberger | Structure-from-motion for mav image sequence analysis with photogrammetric applications[END_REF] SFM pipeline has been adapted to compare the 2pt algorithm to the 5pt algorithm. Two-view pose estimation is used when processing each new frame. To compute the relative pose between two consecutive frames we estimate the essential matrix in case of the 5pt algorithm and the homography for the 2pt algorithm. Afterwards full bundle adjustment is performed to compute precise camera poses and 3D points. The main goal of this experiment is to show that the 2pt can in practice replace standard algorithms (like the 5pt) for gaining a speed up but by maintaining the accuracy of the system.

For this experiment a UAV data set of a parking lot (denotated ParkingLot data set) is used. Images were captured by a gimbal mounted camera, such that the z-axis of the camera aligns with the gravity direction. The dataset was recorded at a native resolution of 24MP. The UAV was equipped with GPS and the GPS trajectory is utilized as ground truth for comparison. Figure 12 shows the results for this experiment. Figure 12(a) shows the output of the SFM system, resulting 3D point cloud (densified with SURE [START_REF] Rothermel | Sure: Photogrammetric surface reconstruction from imagery[END_REF]), camera positions (red) and GPS positions (green). Figure 12(b) shows RPE plots for an experiment using the 5pt (black) algorithm and the 2pt (red) algorithm. Both algorithms lead to almost identical results. The value of the remaining RPE error is mainly due to the uncertainty of the GPS measurements and expected in this form. The resulting re-projection error after bundle adjustment is 0.249px for the 2pt case and 0.246px for the 5pt case, almost identical. To be clear, the reason for the identical re-projection error comes from bundle adjustment. This experiment demonstrates that the proposed 2pt algorithm can successfully replace the standard 5pt in a SFM system seamlessly but with the advantage of a gained speed-up.

CONCLUSION

In this paper we presented novel algorithms for relative pose estimation. The proposed methods differ from previous algorithms by utilizing a known common direction and assumptions about the environment. This makes it possible to derive algorithms that need less point correspondences for relative motion estimation as compared to state-of-theart methods. This leads to improved RANSAC performance, which is a fundamental building block of any motion estimation or SFM system. In our paper we show through a variety of experiments with synthetic and real data the usability of the method. In particular, the results of our real world experiments clearly demonstrate that the assumptions about ground plane and vertical walls really hold in typical usage scenarios. Our algorithms have successfully been used for indoor robot navigation as well as for 3D reconstruction of aerial images taken from a UAV.

In addition to pure ego-motion estimation, there exists another obvious use case for our proposed algorithms, which has not been investigated in this work. Our methods not only provide the motion between views but are also able to detect the different scene planes of the environment. In an environment consisting of vertical walls and ground plane, the proposed 2pt methods could do plane detection more efficient and robust as compared to the otherwise used general 4pt homography method.

APPENDIX A AN ALTERNATIVE SOLUTION TO THE 2PT HOMOG-RAPHY FORMULATION

The general homographic relation for points belonging to a 3D plane and projected into two different views is defined as follows:

q j = Hq i , (49)
with q i = [x i , y i , w i ] and q j = [x j , y j , w j ] the projective coordinates of the points between the views i and j. H is given by:

H = R - 1 d tn , (50)
where R and t are respectively the rotation and the translation between view i and j and where d is the distance between the camera i and the 3D plane described by the normal n.

In our case, we assume that the camera intrinsic parameters are known and that the points q i and q j are normalized. We also consider that the attitude of the cameras for the both views are known and that these attitude measurements have been used to align the camera coordinate system with the ground plane. In this way, only the yaw angle θ between the two views remains unknown. Similarly, since we consider that the ground plane constitutes the visible 3D plane during the movement of the cameras, we can note that n = [0, 0, 1] . Consequently, equation(50) can be written as:

H =   cos(θ) -sin(θ) 0 sin(θ) cos(θ) 0 0 0 1   - t d   0 0 1   , (51)
d being unknown, translation can be known only up to scale. Consequently, the camera-plane distance d is set to 1 and absorbed by t. We then obtain:

H =   cos(θ) -sin(θ) 0 sin(θ) cos(θ) 0 0 0 1   -   t x t y t z     0 0 1   , (52)
=   cos(θ) -sin(θ) -t x sin(θ) cos(θ) -t y 0 0 1 -t z   . (53)
If 1 -t z = 0, then the homography can be scaled, by deviding H by 1 -t z , which results in:

H =    cos(θ) 1-tz -sin(θ) 1-tz -tx 1-tz sin(θ) 1-tz cos(θ) 1-tz - ty 1-tz 0 0 1    . (54)
In a general manner, this homography can be written as

H =   h 1 -h 2 h 3 h 2 h 1 h 4 0 0 1   . ( 55
)
The problem consists then in estimating this homography. In this way, we consider the following relation:

q j × Hq i = 0, (56)
where × denotes the cross product. In our case, we obtain:

  x j y j w j   ×   h 1 -h 2 h 3 h 2 h 1 h 4 0 0 1     x i y i w i   = 0, (57)
  w i y j -w j (h 2 x i + h 1 y i + h 4 w i ) -w i x j + w j (h 1 x i + h 2 y i + h 3 w i ) x j (h 2 x i + h 1 y i + h 4 w i ) -y j (h 1 x i + h 2 y i + h 3 w i )   = 0. (58)
The third equation being a linear combination of the two others, we only consider the two first lines of the previous system and obtain:

w i y j -w j h 2 x i -w j h 1 y i -w j h 4 w i -w i x j + w j h 1 x i -w j h 2 y i -w j h 3 w i ) = 0, (59)
which can be finally rewritten as -w j y i -w j x i 0 -w j w i w j x i -w j y i w j w i 0

    h 1 h 2 h 3 h 4     =
-w i y j w i x j .

(60) We can observe that two points are sufficient in order to estimate the h l , l = {1, 2, 3, 4} elements and that the system can be easily extended to n points in order to obtain an over determined system. This possibility is then very interesting because it permits to apply a RANSAC algorithm in order to reject the outliers.

Once the h l , l = {1, 2, 3, 4} estimated, we are then able to evaluate the motion parameters, i.e., θ, t x , t y and t z . By identification between (55) and (54), we know that h 1 = cos(θ) 1-tz and h 2 = sin(θ) 1-tz . Then, if h 1 = 0, we have tan(θ) = h2 h1 and finally θ = arctan( h2 h1 ). Due to the periodicity of arctan two solutions arises, θ and θ + π. If

h 1 = 0, then θ = ± π 2 .
Knowing the angle yaw θ between the two views and if h 1 = 0, we then have

t z = 1 -cos(θ) h1 . If h 1 = 0, then θ = ± π 2
and we can use the relation h 2 = sin(θ) 1-tz , to obtain t z = 1± 1 h2 . Consequently, we can deduce the two remaining translation parameters t x = h 3 (t z -1) and t y = h 4 (t z -1).

Sideways motion

Sideways motion

Noise in Pixel

Fig. 1 .

 1 Fig. 1. Comparison of the RANSAC iteration number for 99% of success probability

Fig. 4 .

 4 Fig. 4. Evaluation of the 2pt algorithm under different IMU noise and constant image noise of 0.5 pixel standard deviation. First row, sideways motion, second row forward motion.

Fig. 8 .

 8 Fig. 8. Evaluation of the 3pt-homography algorithm under different IMU noise and constant image noise of 0.5 pixel standard deviation. First row: sideways motion of the camera with varying pitch angle (left) and varying roll angle (right). Second row: forward motion of the camera with varying pitch angle (left) and varying roll angle (right).

Fig. 9 .Fig. 10 .Fig. 11 .

 91011 Fig. 9. Left, Vicon arena used to record the ground-truth dataset. Center, teleoperated Segway mobile robot capturing data. Right, sample image captured by the robot.

Fig. 12 .

 12 Fig. 12. Results of an incremental SFM pipeline using the 2pt algorithm. (a) Resulting 3D point cloud, camera positions (red) and GPS positions (green). (b) RPE error plot when using 5pt or 2pt within the SFM pipeline. The initial solution of the 5pt and 2pt are similar enough for bundle adjustment to converge to almost the same final solution.

TABLE 1

 1 Comparison of the degenerate conditions (yes means degenerate) for the standard 3pt method, the proposed 3pt homography method, the 2pt methods and the 2.5pt method.

				3pt-essential	3pt-hom	2pt	2.5pt
	collinear points		no	yes	no	no
	collinear points parallel	yes	yes	no	no
	to translation direction
	points	coplanar	to	yes	yes	no	no
	translation vector

TABLE 2

 2 Run-time comparison of different pose estimation algorithms. The second column provides timings for estimating the hypothesis. The third column provides timings for one RANSAC iterations, which includes the selection of the right solution from a set of hypothesis. The last column shows the average number of real solutions (camera poses) provided by the respective algorithm. See text for more details.

	Method	Hypothesis Estimation(ms)	RANSAC 1 Iteration(ms)	Avg. # Solutions
	2pt	0.09	8.31	2
	2.5pt	0.22	33.45	8
	3pt-homography	27.28	55.17	6.85
	3pt-essential	0.49	25.02	6.18
	4pt-homography	0.18	8.65	2
	5pt-essential	0.42	64.33	16.02

TABLE 3 Root

 3 Mean Squared Error overview.

	Sequence	2pt (mm)	5pt (mm)
	Ground Sequence I	8.94	48.55
	Ground Sequence II	9.28	56.66
	Ground Sequence III	18.46	65.39
	Ground Sequence IV	14.25	93.30
	Ground Sequence V	25.61	34.46
	Ground Sequence VI	39.75	67.45
		TABLE 4
	Root Mean Squared Error overview for the Wall Sequence.
	Method	Wall Sequence I	Wall Sequence II
	2.5pt	60.65		41.60
	5pt-essential	24.97		27.84
	3pt-essential	27.44		64.65
	3pt-homography	27.26		65.96

  Fig. 3. Evaluation of the 2 point algorithm under sideways and forward motion with varying image noise.

								5-Quantile										5-Quantile											5-Quantile					5-Quantile
			8											70													3.5							25
							5pt-essential										5pt-essential											5pt-essential					5pt-essential
		Rotation Error in Degree	0 1 2 3 4 5 6 7	0			Noise in Pixel 0.4 0.5 0.6 4pt-homography 0.1 0.2 0.3 3pt-essential 2pt-homography	0.7	0.8	0.9	1	Translation Error in Degree	0 10 20 30 40 50 60	0			Noise in Pixel 0.4 0.5 0.6 4pt-homography 0.1 0.2 0.3 3pt-essential 2pt-homography	0.7	0.8	0.9	1	Forward motion	Rotation Error in Degree	0 0.5 1 1.5 2 2.5 3	0	Noise in Pixel 0.4 0.5 0.6 4pt-homography 0.1 0.2 0.3 3pt-essential 2pt-homography	0.7	0.8	0.9	1	Translation Error in Degree	0 5 10 15 20	0	Noise in Pixel 0.4 0.5 0.6 4pt-homography 0.1 0.2 0.3 3pt-essential 2pt-homography	0.7	0.8	0.9	1
								5-Quantile										5-Quantile											5-Quantile					5-Quantile
					7											7									70									70
								5pt-essential										5pt-essential											5pt-essential					5pt-essential
	Sideways motion		Rotation Error in Degree	0 1 2 3 4 5 6	0	Rotation Noise in Degree (Pitch) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 4pt-homography 0.1 3pt-essential 2pt-homography	0.9	1		Rotation Error in Degree	0 1 2 3 4 5 6	0	Rotation Noise in Degree (Roll) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 4pt-homography 0.1 3pt-essential 2pt-homography	0.9	1		Translation Error in Degree	0 10 20 30 40 50 60	0		Rotation Noise in Degree (Pitch) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 4pt-homography 0.1 3pt-essential 2pt-homography	0.9	1	Translation Error in Degree	0 10 20 30 40 50 60	0	Rotation Noise in Degree (Roll) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 4pt-homography 0.1 3pt-essential 2pt-homography	0.9	1
	Forward motion	Rotation Error in Degree		0	0.1	Rotation Noise in Degree (Pitch) 0.2 0.3 0.4 0.5 0.6 0.7 0.8	0.9	1

  Fig.6. Evaluation of the 2.5pt algorithm under IMU noise and constant image noise of 0.5 pixel standard deviation. First row sideways motion, second row forward motion.

								5-Quantile													5-Quantile																5-Quantile	5-Quantile
					2.6												2.2													11				8
								5pt-essential													5pt-essential																5pt-essential	5pt-essential
					2.4		4pt-homography										2		4pt-homography											10				4pt-homography	7	4pt-homography
	Sideways motion		Rotation Error in Degree	0.8 1 1.2 1.4 1.6 1.8 2 2.2	0	Rotation Noise in Degree (Pitch) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 3pt-essential 0.1 2.5pt-homography		0.9		1		Rotation Error in Degree	0.4 0.6 0.8 1 1.2 1.4 1.6 1.8	0	Rotation Noise in Degree (Roll) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 3pt-essential 0.1 2.5pt-homography		0.9		1		Translation Error in Degree		1 2 3 4 5 6 7 8 9	0		Rotation Noise in Degree (Pitch) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 3pt-essential 0.1 2.5pt-homography	0.9	1	Translation Error in Degree	0 1 2 3 4 5 6	0	Rotation Noise in Degree (Roll) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 3pt-essential 0.1 2.5pt-homography	0.9	1
								5-Quantile													5-Quantile																5-Quantile	5-Quantile
					1												1.3														8					9
								5pt-essential													5pt-essential																5pt-essential	5pt-essential
	Forward motion		Rotation Error in Degree	0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9	0	Rotation Noise in Degree (Pitch) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 4pt-homography 0.1 3pt-essential 2.5pt-homography		0.9		1	Rotation Error in Degree	0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2	0	Rotation Noise in Degree (Roll) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 4pt-homography 0.1 3pt-essential 2.5pt-homography		0.9		1		Translation Error in Degree	2 3 4 5 6 7	0			Rotation Noise in Degree (Pitch) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 4pt-homography 0.1 3pt-essential 2.5pt-homography	0.9	1	Translation Error in Degree	2 3 4 5 6 7 8	0	Rotation Noise in Degree (Roll) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 4pt-homography 0.1 3pt-essential 2.5pt-homography	0.9	1
								5-Quantile													5-Quantile																5-Quantile	5-Quantile
			0.3													1																		0.35		1.6
	Sideways motion	Rotation Error in Degree	0 0.05 0.1 0.15 0.2 0.25	0			Noise in Pixel 0.4 0.5 0.6 5pt-essential 0.1 0.2 0.3 3pt-essential 3pt-homography	0.7	0.8	0.9		1		Translation Error in Degree	0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9	0			Noise in Pixel 0.4 0.5 0.6 5pt-essential 0.1 0.2 0.3 3pt-essential 3pt-homography	0.7	0.8	0.9		1		Forward motion	Rotation Error in Degree	0 0.05 0.1 0.15 0.2 0.25 0.3	0	5pt-essential Noise in Pixel 0.1 0.2 0.3 0.4 0.5 0.6 3pt-essential 3pt-homography	0.7	0.8	0.9	1	Translation Error in Degree	0 0.2 0.4 0.6 0.8 1 1.2 1.4	0	5pt-essential Noise in Pixel 0.1 0.2 0.3 0.4 0.5 0.6 3pt-essential 3pt-homography	0.7	0.8	0.9	1
	Fig. 7. Evaluation of the 3pt-homography algorithm under sideways and forward motion with varying image noise.
								5-Quantile													5-Quantile																5-Quantile	5-Quantile
					0.4												0.4												0.7				2.5
								5pt-essential													5pt-essential																5pt-essential	5pt-essential
	Sideways motion	Rotation Error in Degree	0 0.05 0.1 0.15 0.2 0.25 0.3 0.35	0	Rotation Noise in Degree (Pitch) 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 3pt-essential 3pt-homography	0.9		1	Rotation Error in Degree	0 0.05 0.1 0.15 0.2 0.25 0.3 0.35	0	Rotation Noise in Degree (Roll) 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 3pt-essential 3pt-homography		0.9		1		Translation Error in Degree	0.1 0.2 0.3 0.4 0.5 0.6	0		Rotation Noise in Degree (Pitch) 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 3pt-essential 3pt-homography	0.9	1	Translation Error in Degree	0 0.5 1 1.5 2	0	Rotation Noise in Degree (Roll) 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 3pt-essential 3pt-homography	0.9	1
			5					5-Quantile 5-Quantile								25					5-Quantile 5-Quantile														1.4		5-Quantile 5-Quantile	10	5-Quantile 5-Quantile
				0.4			5pt-essential								0.35			5pt-essential									0.7					5pt-essential	1.6	5pt-essential
	Forward motion	0 0.05 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 0 Rotation Error in Degree Rotation Error in Degree 0.1 0.15 0.2 0.25 0.3 0.35	0	0.1 4pt-homography 0.2 0.3 3pt-essential 2.5pt-homography 0.4 5pt-essential Rotation Noise in Degree (Pitch) 0.5 0.6 0.7 0.8 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 3pt-essential 3pt-homography	0.9	0.9	1	1	0 0.05 0 5 10 15 20 0 Rotation Error in Degree Translation Error in Degree 0.1 0.15 0.2 0.25 0.3	0	Noise in Pixel 0.4 0.5 0.6 4pt-homography 0.1 0.2 0.3 3pt-essential 2.5pt-homography 5pt-essential Rotation Noise in Degree (Roll) 0.7 0.8 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 3pt-essential 3pt-homography	0.9	0.9	1	1	Forward motion	Translation Error in Degree	Rotation Error in Degree 0 0.1 0.2 0.3 0.4 0.5 0.6	0 0.2 0.4 0.6 0.8 1 1.2	0	Noise in Pixel 0.4 0.5 0.6 4pt-homography 0.1 0.2 0.3 5pt-essential 3pt-essential 2.5pt-homography Rotation Noise in Degree (Pitch) 0.7 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 3pt-essential 3pt-homography	0.8	0.9	0.9	1	1	Translation Error in Degree	Translation Error in Degree 0 0 0.2 0.4 0.6 0.8 1 1.2 1.4	9 0 1 2 3 4 5 6 7 8	0	4pt-homography 5pt-essential Noise in Pixel 0.1 0.2 0.3 0.4 0.5 0.6 3pt-essential 2.5pt-homography Rotation Noise in Degree (Roll) 0.7 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 3pt-essential 3pt-homography	0.8	0.9	0.9	1	1

Fig. 5. Evaluation of the 2.5pt algorithm under sideways and forward motion with varying image noise.

JOURNAL OF L A T E X CLASS FILES, VOL. 13, NO. 9, FEBRUARY 2016

ACKNOWLEDGMENTS

This work has been partially supported by Project ANR Blanc International DrAACaR-ANR-11-IS03-0003 and a Google Award. We also thank the anonymous reviewers for their useful discussions and constructive comments.