Keywords: Sensor Fusion, Inertial Sensors, Vision, Structure from Motion Fusion Sensoriel, Capteurs inertiels, Vision, Structure from Motion

This paper investigates the visual-inertial structure from motion problem. A simple closed form solution to this problem is introduced. Special attention is devoted to identify the conditions under which the problem has a finite number of solutions. Specifically, it is shown that the problem can have a unique solution, two distinct solutions and infinite solutions depending on the trajectory, on the number of point-features and on their layout and on the number of camera images. The investigation is also performed in the case when the inertial data are biased, showing that, in this latter case, more images and more restrictive conditions on the trajectory are required for the problem resolvability.

Introduction

The structure from motion problem (SfM) consists of determining the threedimensional structure of the scene by using the measurements provided by one or more sensors over time (e.g. vision sensors, ego-motion sensors, range sensors). In the case of visual measurements only, the SfM problem has been solved up to a scale [START_REF] Chiuso | Structure from Motion Causally Integrated Over Time[END_REF][START_REF] Davison | MonoSLAM: Real-Time Single Camera SLAM[END_REF][START_REF] Hartley | In Defense of the Eight-Point Algorithm[END_REF][START_REF] Longuet-Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF][START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF] and a closed form solution has also been derived [START_REF] Hartley | In Defense of the Eight-Point Algorithm[END_REF][START_REF] Longuet-Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF][START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF], allowing the determination of the three-dimensional structure of the scene, without the need for any prior knowledge.

The case of inertial and visual measurements, i.e., the visual-inertial structure from motion problem (from now on the Vi-SfM problem), has particular interest and has been investigated by many disciplines, both in the framework of computer science [START_REF] Bryson | Observability Analysis and Active Control for Airbone SLAM[END_REF][START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF][START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF][START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF][START_REF] Strelow | Motion estimation from image and inertial measurements[END_REF] and in the framework of neuroscience (e.g., [START_REF] Berthoz | Perception of Linear Horizontal Self-Motion Induced by Peripheral Vision (Linearvection) Basic Characteristics and Visual-Vestibular Interactions[END_REF]5,[START_REF] Fetsch | Visual-vestibular cue integration for heading perception: Applications of optimal cue integration theory[END_REF]). Vision and inertial sensing have received great attention by the mobile robotics community since they require no external infrastructure and this is a key advantage for robots operating in unknown environments where GPS signals are shadowed.

From a theoretical perspective, recent works on Vi-SfM have focused on two separate issues: (i) understanding the observability properties in several contexts and (ii) determining the solution in closed form. Regarding the first issue, recent works derived the observable modes, i.e. the states that can be determined by fusing visual and inertial measurements [START_REF] Bryson | Observability Analysis and Active Control for Airbone SLAM[END_REF][START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF][START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF][START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF] and [START_REF] Weiss | Monocular-SLAM-Based Navigation for Autonomous Micro Helicopters in GPS-Denied Environments[END_REF]. Specifically, it has been shown that the velocity, the absolute scale, the gravity vector in the local frame and the bias-vectors which affect the inertial measurements, are observable modes. The second theoretical issue has been faced in [6] and [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF]. The interest of this research comes from the fact that any approach to the Vi-SfM based on a recursive filter or on a smoothing estimator needs to initialize the estimated state. Due to the system non linearities, an erroneous initialization can cause a divergence of the estimation process. A deterministic solution, i.e., a solution which analytically expresses the observable modes in terms of the measurements provided by the sensors during a short time-interval, will avoid this important inconvenient. Closed form solutions to the Vi-SfM have been introduced in [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF]. In [6] also the case of an unknown camera-IMU extrinsic calibration has been dealt and a deterministic algorithm able to also determine the parameters characterizing this transformation has been introduced. In [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF], starting from the differential equations which characterize a generic 3D-motion and from the analytical expression of the visual observations, closed form expressions of the observable modes in terms of the sensor measurements were derived. On the other hand, these derivations did not allow us to detect the conditions under which the Vi-SfM can be solved. This important issue was very marginally investigated in [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF]. Specifically, the observability analysis carried out in [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF] only allowed us to detect a very limited number of singular cases where the sensor information does not allow us to determine the observable modes.

Here we derive a new simple and intuitive closed solution to the Vi-SfM problem. Compared with the solutions proposed in [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF], this new solution allows us to investigate the intrinsic properties of the Vi-SfM problem and to identify the conditions under which the problem can be solved in closed form. In particular, these conditions regard the trajectory, the number of point-features and their layout and the number of monocular images where the same point-features are seen. Additionally, minimal cases have been fully investigated, i.e., necessary and sufficient conditions on the trajectory and on the feature layout have been provided for the cases when the number of features and the number of camera images is the minimum required for the Vi-SfM problem resolvability.

All the theoretical results derived in this paper are obtained under the assumption of noiseless visual and inertial measurements. Additionally, the measurements provided by the gyroscopes are assumed to be unbiased (only the case of a constant bias on the accelerometers is considered). Finally, the theoretical analysis assumes that all the sensors share the same reference frame (in other words, the transformation between visual and inertial sensors is a priori known). On the other hand, Monte Carlo simulations have also been performed by relaxing all these assumptions.

The paper is organized as follows. The system is defined in section 2. In section 3 the Vi-SfM problem is reduced to a polynomial equation system, whose resolvability is investigated in section 4, both in the unbiased (4.1) case and in the case of biased accelerometer measurements (4.2). All the possible cases are then summarized in the first part of section 5. In section 5.2 some results obtained by performing Monte Carlo simulations are also provided. Specifically, the assumptions made in the theoretical analysis are relaxed in order to generate the sensor measurements and the closed form solution is used in conjunction with a filtering approach in order to show its benefit. Finally, concluding remarks are provided in section 6.

The Considered System

We consider a system (from now on we call it the platform) consisting of a monocular camera and an Inertial Measurement Unit (IMU). The IMU consists of three orthogonal accelerometers and three orthogonal gyrometers. We introduce a global frame in order to characterize the motion of the platform moving in a 3D environment. Its z-axis points vertically upwards. As we will see, for the next derivation we do not need to better define this global frame. We will adopt lower-case letters to denote vectors in this frame (e.g. the gravity is g = [0, 0, -g] T , where g 9.8 ms -2 ). We assume that the transformations among the camera frame and the IMU frame are known (we assume that the platform frame coincides with the camera frame and we call it the local frame). We will adopt upper-case letters to denote vectors in this frame. Since this local frame is time dependent, we adopt the following notation: W t (τ ) will be the vector with global coordinates w(τ ) in the local frame at time t. Additionally, we will denote with C t2 t1 the matrix which characterizes the rotation occurred during the time interval (t 1 , t 2 ) and with C t1 t2 its inverse (i.e., (C t2 t1 ) -1 = C t1 t2 ). Let us refer to vectors which are independent of the origin of the reference frame (e.g., speed, acceleration, etc.). For these vectors we have:

W t1 (τ ) = C t2 t1 W t2 (τ ).
Finally, C t will denote the rotation matrix between the global frame and the local frame at time t, i.e., w(τ ) = C t W t (τ ).

The IM U provides the platform angular speed and acceleration. Regarding the acceleration, the one perceived by the accelerometer (A) is not simply the inertial acceleration (A inertial ). It also includes the gravitational acceleration (G).

INRIA

We assume that the camera is observing one or more point-features during the time interval [T in , T f in ]. The platform and one of these observed features are displayed in fig 1 .   Figure 1: Global and local frame with the point-feature position (P ), the platform acceleration (A inertial ) and the gravitational acceleration (G).

The closed form solution

As stated in the introduction, the states that can be determined by fusing visual and inertial measurements [START_REF] Bryson | Observability Analysis and Active Control for Airbone SLAM[END_REF][START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF][START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF][START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF] are: the platform velocity, the absolute scale, the gravity vector in the local frame and the bias-vectors which affect the inertial measurements. Note that the knowledge of the gravity in the local frame is equivalent to the knowledge of its magnitude together with the roll and pitch angle, i.e., the orientation of the platform with respect to the horizontal plane. Our goal is to express in closed-form all the observable modes at a given time T in only in terms of the visual and inertial measurements obtained during the time interval [T in , T f in ].

The position of the platform r at any time t ∈ [T in , T f in ] satisfies the equation r(t) = r(T in ) + v(T in )∆t + t Tin τ Tin a(ξ)dξdτ . The last term contains a double integral over time, which can be simplified in a single integral by integrating by parts. We obtain:

r(t) = r(T in ) + v(T in )∆t + t Tin (t -τ )a(τ )dτ (1)
where v ≡ dr dt , a ≡ dv dt and ∆t ≡ t -T in . The accelerometer does not provide the vector a(τ ). It provides the acceleration in the local frame and it also perceives the gravitational component. Additionally, its data are usually biased [START_REF] Farrell | Aided Navigation: GPS and High Rate Sensors[END_REF][START_REF] Woodman | An introduction to inertial navigation[END_REF], i.e., they are corrupted by a constant term (B) 1 . In other words, the accelerometer provides the vector: A τ (τ ) ≡ A inertial τ (τ ) -G τ + B. Note that the gravity comes with a minus since, when the platform does not accelerate (i.e. A inertial τ (τ ) is zero), the accelerometer perceives an acceleration which is the same of an object accelerated upward in absence of gravity. Note also that the vector G τ depends on time only because the local frame can rotate.

We write equation (1) by highlighting the vector A τ (τ ) provided by the accelerometer:

r(t) = r(T in ) + v(T in )∆t + g ∆t 2 2 + C Tin [S Tin (t) -Γ(t)B] (2)
where:

S Tin (t) ≡ t Tin (t -τ )C τ Tin A τ (τ )dτ ; Γ(t) ≡ t Tin (t -τ )C τ Tin dτ
The matrix C τ Tin can be obtained from the angular speed during the interval [T in , τ ] provided by the gyroscopes [START_REF] Farrell | Aided Navigation: GPS and High Rate Sensors[END_REF]. Hence, also the matrix Γ(t) can be obtained by directly integrating the gyroscope data during the interval [T in , t]. Finally, the vector S Tin (t) can be obtained by integrating the data provided by the gyroscopes and the accelerometers delivered during the interval [T in , t].

Let us suppose that N point-features are observed, simultaneously. Let us denote their position in the physical world with p i , i = 1, ..., N . According to our notation, P i t (t) will denote their position at time t in the local frame at time t. We have:

p i = r(t) + C Tin C t Tin P i t (t) (3)
We write this equation at time t = T in obtaining:

p i -r(T in ) = C Tin P i Tin (T in ) (4)
By inserting the expression of r(t) provided in (2) into equation (3), by using (4) and by pre multiplying by the rotation matrix (C Tin ) -1 (we remind the reader that, according to our notation, v(T in ) = C Tin V Tin (T in ) and g = C Tin G Tin ) we finally obtain the following equation:

C t Tin P i t (t) = P i Tin (T in ) -V Tin (T in )∆t -G Tin ∆t 2 2 + (5) + Γ(t)B -S Tin (t); i = 1, 2, ..., N
A single image provides the bearing angles of all the point-features in the local frame. In other words, an image taken at time t provides all the vectors P i t (t) up to a scale. Since the data provided by the gyroscopes during the interval 1 Actually, the accelerometer bias slightly changes with time, i.e., it would be more appropriate to write B(τ ). However, as we will show in the next section, few camera images allow us to determine this component and we can assume that the bias is constant during the time interval needed to collect few camera images.

INRIA

(T in , T f in ) allow us to build the matrix C t Tin , having the vectors P i t (t) up to a scale, allows us to also know the vectors C t Tin P i t (t) up to a scale. We assume that the camera provides n i images of the same N point-features at the consecutive times: t 1 = T in < t 2 < ... < t ni = T f in . From now on, for the sake of simplicity, we adopt the following notation:

• P i j ≡ C tj Tin P i tj (t j ), i = 1, 2, ..., N ; j = 1, 2, ..., n i • P i ≡ P i Tin (T in ), i = 1, 2, ..., N • V ≡ V Tin (T in ) • G ≡ G Tin • Γ j ≡ Γ(t j ), j = 1, 2, ..., n i • S j ≡ S Tin (t j ), j = 1, 2, ..., n i
Additionally, we will denote with µ i j the unit vector with the same direction of P i j and we introduce the unknowns λ i j such that P i j = λ i j µ i j . Finally, without loss of generality, we can set T in = 0, i.e., ∆t = t. Our sensors provide µ i j and S j for i = 1, 2, ..., N ; j = 1, 2, ..., n i . Equation ( 5) can be written as follows:

P i -V t j -G t 2 j 2 + Γ j B -λ i j µ i j = S j (6)
The Vi-SfM problem is the determination of the vectors: P i , (i = 1, 2, ..., N ), V , G. In the case with biased accelerometer data, we also need to determine the vector B. We can use the equations in (6) to determine these vectors. On the other hand, the use of ( 6) requires to also determine the quantities λ i j . By considering j = 1 in (6), i.e. t j = t 1 = T in = 0, we easily obtain:

P i = λ i 1 µ i 1 .
Then, we write the linear system in (6) as follows:

-G t 2 j 2 -V t j + Γ j B + λ 1 1 µ 1 1 -λ 1 j µ 1 j = S j λ 1 1 µ 1 1 -λ 1 j µ 1 j -λ i 1 µ i 1 + λ i j µ i j = 0 3 (7)
where j = 2, ..., n i , i = 2, ..., N and 0 3 is the 3 × 1 zero vector. This linear system consists of 3(n i -1)N equations in N n i + 6 unknowns (or N n i + 9 in the biased case). Let us define the two column vectors X and S:

X ≡ [G T , V T , B T , λ 1 1 , ..., λ N 1 , ..., λ 1 ni , ..., λ N ni ] T (or X ≡ [G T , V T , λ 1 1 , ..., λ N 1 , ..., λ 1 ni , ..., λ N ni ]
T in absence of bias), and S ≡ [S T 2 , 0 3 , ..., 0 3 , S T 3 , 0 3 , ..., 0 3 , ..., S T ni , 0 3 , ..., 0 3 ] T and the matrix:

Ξ ≡ (8)                 T 2 S 2 Γ 2 µ 1 1 0 3 0 3 -µ 1 2 0 3 0 3 0 3 0 3 0 3 0 33 0 33 0 33 µ 1 1 -µ 2 1 0 3 -µ 1 2 µ 2 2 0 3 0 3 0 3 0 3 ... ... ... ... ... ... ... ... ... ... ... ... 0 33 0 33 0 33 µ 1 1 0 3 -µ N 1 -µ 1 2 0 3 µ N 2 0 3 0 3 0 3 ... ..
0 3 0 3 0 3 0 3 0 3 -µ 1 ni 0 3 0 3 0 33 0 33 0 33 µ 1 1 -µ 2 1 0 3 0 3 0 3 0 3 -µ 1 ni µ 2 ni 0 3 ... ... ... ... ... ... ... ... ... ... ... ... 0 33 0 33 0 33 µ 1 1 0 3 -µ N 1 0 3 0 3 0 3 -µ 1 ni 0 3 µ N ni                
where T j ≡ -t 2 j 2 I 3 , S j ≡ -t j I 3 and I 3 is the identity 3 × 3 matrix; 0 33 is the 3 × 3 zero matrix (note that the third set of columns disappear in absence of bias). The linear system in ( 7) can be written in the following compact format:

ΞX = S (9)
The sensor information is completely contained in the above linear system. Additionally, we assume that the magnitude of the gravitational acceleration is a priori known. This extra information is obtained by adding to our linear system the following quadratic equation: |G| = g. By introducing the following 3

× (N n i + 6) matrix (or 3 × (N n i + 9) in the biased case), Π ≡ [I 3 , 0 3 ... 0 3 ],
this quadratic constraint can be written in terms of X as follows:

|ΠX| 2 = g 2 (10)
The Vi-SfM problem can be solved by finding the vector X, which satisfies ( 9) and [START_REF] Hunt | Prevalence: a translation-invariant "almost every" on infinite-dimensional spaces[END_REF].

Existence and number of distinct solutions

We are interested in understanding how the existence and the number of solutions of the Vi-SfM problem depend on the motion, on the number of observed point-features, on the point-features layout and on the number of camera images. The resolvability of the Vi-SfM problem can be investigated by computing the null space of the matrix Ξ in [START_REF] Fetsch | Visual-vestibular cue integration for heading perception: Applications of optimal cue integration theory[END_REF]. Let us denote with N (Ξ) this space. The following theorem holds: Proof: : The first part of this theorem is a trivial consequence of the theory of linear systems. Indeed, the vector X can be uniquely obtained by inverting the matrix Ξ. Let us consider the case when the dimension of N (Ξ) is 1. The linear system in (9) has infinite solutions with the following structure: X(γ) = Ξ * S + γn, where Ξ * is a pseudoinverse of Ξ, n is a vector belonging to N (Ξ) and γ is an unknown scalar value [START_REF] Meyer | Matrix Analysis and Applied Linear Algebra[END_REF]. We use [START_REF] Hunt | Prevalence: a translation-invariant "almost every" on infinite-dimensional spaces[END_REF] to obtain γ. We have:

|ΠX(γ)| 2 = g 2 ,
which is a second order polynomial equation in γ if and only if |Πn| = 0. Hence, we have two solutions for γ, γ 1 and γ 2 , and two solutions for

INRIA X, X 1 ≡ X(γ 1 ) and X 2 ≡ X(γ 2 ). When |Πn| = 0 equation |ΠX(γ)| 2 = g 2 is independent of γ.
Hence, this equation is automatically satisfied, independently of γ. This means that the Vi-SfM problem has infinite solutions. However, it also means that the vector G can be uniquely determined. The previous theorem allows us to obtain all the properties of the Vi-SfM problem by investigating the null space of Ξ. The dimension of this null space does not change by multiplying the columns of Ξ by any value different from zero. Hence, we will refer to the following matrix:

Ξ ≡     M 2 P 1 P 2 0 3N N ... 0 3N N M 3 P 1 0 3N N P 3 ... 0 3N N ... ... ... ... ... ... M ni P 1 0 3N N ... 0 3N N P ni     (11)
where 0 3N N denotes the 3N × N zero matrix and:

M j ≡     T j S j Γ j 0 33 0 33 0 33 ... ... ... 0 33 0 33 0 33     , P j ≡       P 1 j 0 3 0 3 ... 0 3 P 1 j P 2 j 0 3 ... 0 3 P 1 j 0 3 P 3 j ... 0 3 ... ... ... ... ... P 1 j 0 3 ... 0 3 P N j      
(note that the last three columns in the matrix M j disappear in absence of bias). In the following, theorem 1 will be applied by using Ξ instead of Ξ. We remark that the difference P i j -P i 1 , i = 1, 2, ..., N, j = 2, ..., n i , is independent of i (see equation (5), where, by definition, C tj Tin P i tj (t j ) = P i j ). Hence, we will set χ j ≡ P i j -P i 1 . This quantity characterizes the motion of the platform. We will make the following assumption: Assumption 1 For any i = 1, 2, ..., N, j = 2, ..., n i , P i j = 0 3 (or equivalently, χ j = -P i 1 ). This assumption means that during the platform motion, no point-feature can be on the origin of the camera frame. It ensures that no column of Ξ vanishes.

Unbiased case

Let us denote a vector belonging to N (Ξ ) as follows:

n ≡ [α T , ν T , n 1 1 , ..., n N 1 , n 1 2 , ..., n N 2 , ..., n 1 ni , ..., n N ni ] T (12)
where α and ν are 3D column vectors. n must satisfy:

Ξ n = 0 3(ni-1)N ( 13
)
where 0 3(ni-1)N is the zero 3(n i -1)N × 1 column vector. We can write this system as follows (j = 2, ..., n i , i = 2, ..., N ):

- t 2 j 2 α -t j ν + (n 1 1 + n 1 j )P 1 1 + n 1 j χ j = 0 3 (14)
(n

1 1 + n 1 j )P 1 1 + (n i 1 + n i j )P i 1 + (n 1 j + n i j )χ j = 0 3 (15)
We start our analysis by investigating two very special cases: the planar case and the linear case.

Planar case

Let us suppose that all the vectors P i j , i = 1, ..., N, j = 2, ..., n i , belong to a plane 2 . This means that it exists a frame such that all these vectors have the last component equal to zero. In this new frame the linear system in ( 13) can be separated in two parts: the former corresponds to the first two lines of ( 14) and the first two lines of (15) for j = 2, ..., n i ; the latter corresponds to the third line of ( 14) for j = 2, ..., n i , which only involves the third component of α and ν. Let us denote with Ξ plane 1 and Ξ plane 2 the matrices which characterize these two systems. Their size is 2(n i -1)N × (N n i + 4) and (n i -1) × 2, respectively. When n i ≤ 2, the dimension of N (Ξ plane 1 ) is at least 4. Hence, from theorem 1, we obtain that a necessary condition in order to have a finite number of solutions (one or two) is that n i ≥ 3. The null space of Ξ plane 2 has dimension 0 as n i ≥ 3. Let us consider the case when n i = 3. The size of Ξ plane 1 is 4N × (3N + 4). Hence, in order to have the dimension of N (Ξ plane 1 ) not larger than 1 it is necessary to have N ≥ 3. Let us consider the case when n i = 4. The size of Ξ plane 1 is 6N × (4N + 4). Hence, in order to have the dimension of N (Ξ plane 1 ) not larger than 1 it is necessary to have N ≥ 2. Finally, when n i ≥ 5 no necessary condition constrains N .

We summarize the results of this subsection with the following property:

Property 1 (Unbiased: Planar Layout) When all the observed point-features and the platform positions are coplanar, a necessary condition to have a finite number of solutions is that n i ≥ 3. Specifically, if

n i = 3, N ≥ 3, if n i = 4, N ≥ 2.

Linear case

When all the vectors P i j , i = 1, ..., N, j = 2, ..., n i , belong to a line it exists a frame such that all these vectors have the last two components equal to zero. In this new frame the linear system in (13) can be separated in two parts: the former corresponds to the first line of ( 14) and the first line of (15) for j = 2, ..., n i ; the latter corresponds to the second and third line of ( 14) for j = 2, ..., n i , which only involve the last two components of α and ν. Let us denote with Ξ line 1 and Ξ line 2 the matrices which characterize these two systems. Their size is (n i -1)N ×(N n i +2) and 2(n i -1)×4, respectively. The null space of Ξ line 1 has dimension at least N + 4. Hence, the Vi-SfM problem has always infinite solutions. This result is obvious and could be derived in a simpler manner. When the platform motion is on a straight line, any point-feature belonging to this line provides the same bearing data independently of its distance from the platform.

We summarize the results of this subsection with the following property:

Property 2 (Unbiased: Linear Layout) When all the observed point-features and the platform positions are collinear, the Vi-SfM problem has always infinite solutions. Additionally, when the platform motion is on a straight line, it is not possible to determine the distance of all the point-features belonging to this line even if there are other point-features outside the line.

Let us consider now the general 3D case. We have the following property:

Property 3 When n i ≤ 2 the dimension of N (Ξ ) is at least 3. When n i = 3 the dimension of N (Ξ ) is at least 1.
Finally, when n i ≥ 4 and the platform moves with constant acceleration the dimension of N (Ξ ) is at least 1.

Proof: : In order to prove all these three statements we need to focus our attention on the following subsystem:

- t 2 j 2 α -t j ν = -χ j , j = 2, ..., n i (16)
Let us denote the matrix characterizing this linear system with Ξ . It is immediate to realize that the dimension of N (Ξ ) is never smaller than the dimension of N (Ξ ). Indeed, if the vector [n α T , n ν T ] T ∈ N (Ξ ) then the vector in ( 12) with α = n α , ν = n ν , and n i j = 0, ∀i, j, belongs to N (Ξ ). The first statement is a consequence of the fact that the dimension of N (Ξ ) is at least 3 when

n i ≤ 2.
Let us consider the case of n i = 3. The linear system in ( 16) can always be solved, independently of the platform motion (i.e., for any set of vectors χ j ). In particular, the equations in [START_REF] Meyer | Matrix Analysis and Applied Linear Algebra[END_REF] for j = 2, 3 form a linear square system, which has a unique solution, (α 0 , ν 0 ). From (14-16) we obtain that the vector in [START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF]

with α = α 0 , ν = ν 0 , n 1 1 = n1 1 ≡ -1, n 1 j = n1 j ≡ 1, n i 1 = ni 1 ≡ 1, n i j = ni j ≡ -1 (j = 2, 3; i = 2, .
.., N ) belongs to N (Ξ ) when n i = 3. We will denote this vector with n 0 :

n 0 ≡ [α 0 , ν 0 , n1 1 , ..n i 1 .., ..n 1 j .., ..n i j ..] T (17)
Hence, when n i = 3 the vector n 0 ∈ N (Ξ ) for any motion and the dimension of N (Ξ ) is at least 1. Finally, the system in ( 16) can be solved for any n i ≥ 4 if and only if χ j =

ν 0 t j + α 0 t 2 j
2 . This situation corresponds to a platform motion with constant acceleration α 0 and initial speed ν 0 . Hence, also in this case n 0 ∈ N (Ξ ) In order to apply theorem 1, we need to understand if n 0 is the only generator of N (Ξ ), i.e., if N (Ξ ) has dimension equal or larger than 1.

n i ≤ 2

From property 3 we know that the dimension of N (Ξ ) is at least 3 and, consequently, the Vi-SfM problem has always infinite solutions.

n i = 3

From property 3 we know that the dimension of N (Ξ ) is at least 1, independently of the number of point-features. When N = 1, Ξ is a 6 × 9 matrix. Hence, the dimension of N (Ξ ) is at least 3. Let us consider the case when N = 2. In this case Ξ is a 12 × 12 matrix. We have the following property: Property 4 (Minimal case:

n i = 3, N = 2)
The dimension of N (Ξ ) is 1 if and only if the following two conditions are met:

(i) for a given j (e.g., for j = 2), the three vectors P 1 1 , P 2 1 and χ j span the entire 3D-space;

(ii) for the other value of j (e.g., for j = 3) P i j is not proportional to P k j , ∀i, k = 1, 2, ..., N .

Otherwise, the dimension of N (Ξ ) is larger than 1.

Proof: : If (i) is not true, all the vectors P i j , i = 1, 2, j = 2, 3, belong to a plane. Since N = 2, the dimension of N (Ξ ) is larger than 1 (see property 1). Let us suppose now that the condition (i) is met for j = 2. From ( 15) with j = 2 we obtain:

n 1 1 = n 2 2 = -n 1 2 = -n 2 1
. From ( 14) with j = 2 we obtain the same equation in ( 16) with n 1 2 χ 2 instead of χ 2 . From ( 15) with j = 3 we obtain: (-n 1 2 + n 1 3 )P 1 3 = (n 1 2 + n 2 3 )P 2 3 . If the condition (ii) is met, we have:

n 1 3 = -n 2 3 = n 1 2
and from ( 14) with j = 3 we obtain the same equation in ( 16) with n 1 2 χ 3 instead of χ 3 . In other words, when the condition (ii) is met we have the same equations as in ( 16) for j = 2, 3, with n 1 2 χ j instead of χ j . As previously mentioned, this system has a unique solution and N (Ξ ) is generated by n 0 . If the condition (ii) is not met, equation (-

n 1 2 + n 1 3 )P 1 3 = (n 1 2 + n 2 3 )P 2
Property 8 (Unbiased with constant acceleration) Let us suppose that the platform moves with constant acceleration, i.e., χ j = ν 0 t j + α 0 t 2 j 2 , j = 2, ..., n i . When for a given point-feature k the vectors ν 0 , α 0 and P k 1 span the entire 3D-space the dimension of N (Ξ ) is 1.

Proof: : Without loss of generality, let us set k = 1. From the first 6 equations in (13) (i.e., the equation ( 14) for j = 2, 3) we obtain α and ν as linear functions of P 1 1 , α 0 and ν 0 . By substituting the expressions of α and ν in ( 14) with j = 4 we obtain the following equation: a 1 P 1 1 + a 2 α 0 + a 3 ν 0 = 0 3 , where a 1 , a 2 , a 3 are linear expressions of n 1 1 , n 1 2 , n 1 3 , n 1 4 . Since the three vectors span the entire 3D-space, we must have a k (n 1 1 , n 1 2 , n 1 3 , n 1 4 ) = 0, k = 1, 2, 3. This linear system is characterized by a 3 × 4 matrix. Hence, it has at least one non trivial solution. By a direct computation, it is possible to see that the dimension of the null space of this matrix is 1. The non trivial solution is

n 1 1 = -1, n 1 2 = n 1 3 = n 1 4 = 1.
Now, let us consider the equation [START_REF] Merfeld | Humans use internal models to estimate gravity and linear acceleration[END_REF]. We obtain (i = 1):

(n i 1 + n i j )P i 1 + (1 + n i j )(ν 0 t j + α 0 t 2 j 2 ) = 0 3 (18)
On the other hand, a further consequence of the fact that ν 0 , α 0 and P 1 1 span the entire 3D-space, is that the two vectors ν 0 and α 0 cannot be collinear. Hence, it exists a value of j = j * , such that P i 1 is not proportional to ν 0 t j * + α 0

t 2 j *
2 . From [START_REF] Strelow | Motion estimation from image and inertial measurements[END_REF] we immediately obtain n i j * = -1 and n i 1 = 1. For the other j = j * we obtain: (1+n i j )(P i 1 +ν 0 t j +α 0

t 2 j 2 ) = 0 3 . If n i j = -1 P i 1 = -ν 0 t j -α 0 t 2 j
2 = -χ j , which is not possible because of the assumption 1 This property ensures that, when the platform moves with constant acceleration, the Vi-SfM problem has in general two solutions.

A special case of constant acceleration occurs when the vector α 0 vanishes, i.e., when the platform moves with constant speed. Since |Πn 0 | = |α 0 | = 0, according to theorem 1, the Vi-SfM has infinite solutions. However, as it has been proven at the end of the proof of that theorem, in this case the local gravity G can be uniquely determined. Hence, the orientation of the platform with respect to the horizontal plane can be uniquely determined. We proved the following property: Property 9 (Unbiased with constant speed) Let us suppose that the platform moves with constant speed. The Vi-SfM has infinite solutions. Additionally, the orientation of the platform with respect to the horizontal plane can be uniquely determined.

Biased case

We investigate now the resolvability of the Vi-SfM problem when the accelerometers are affected by a bias. Obviously, all the necessary conditions derived in 4.1 are still necessary in this harder case. On the other hand, there are cases where conditions which ensure resolvability in the unbiased case, are no longer INRIA sufficient in this case. By proceeding as in the unbiased case (see ( 12)), we will denote a vector belonging to N (Ξ ) as follows:

n ≡ [α T , ν T , b T , n 1 1 , ..., n N 1 , n 1 2 , ..., n N 2 , ..., n 1 ni , ..., n N ni ] T ( 19
)
where b is a 3D-vectors (as α and ν). n must satisfy [START_REF] Longuet-Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF] where now Ξ also includes the third set of columns. We can write this system as in [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF][START_REF] Merfeld | Humans use internal models to estimate gravity and linear acceleration[END_REF]. In this case, the first equation must be replaced by:

- t 2 j 2 α -t j ν + Γ j b + (n 1 1 + n 1 j )P 1 1 + n 1 j χ j = 0 3 ( 20
)
Regarding the planar and linear cases, properties 1 and 2 still hold since they only provide necessary conditions. However, regarding the planar case, more restrictive conditions can be derived, which even hold in the 3D-case3 . In the biased case, property 3 is replaced by the following property:

Property 10 When n i ≤ 3 the dimension of N (Ξ ) is at least 3. When n i = 4 the dimension of N (Ξ ) is at least 1.
Finally, when n i ≥ 5 and the platform moves with the special motion characterized by χ j = -t 2 j 2 α 0 -t j ν 0 + Γ j b 0 , for three vectors α 0 , ν 0 and b 0 and j ≥ 5, the dimension of N (Ξ ) is at least 1.

Proof: : In order to prove these three statements we need to focus our attention on the following subsystem:

- t 2 j 2 α -t j ν + Γ j b = -χ j , j = 2, ..., n i (21)
Let us denote the matrix characterizing this linear system with Ξ b . It is immediate to realize that the dimension of N (Ξ ) is never smaller than the dimension of N (Ξ b ). Indeed, if the vector [n α T , n ν T , n b T ] T ∈ N (Ξ b ) then the vector in [START_REF] Weiss | Monocular-SLAM-Based Navigation for Autonomous Micro Helicopters in GPS-Denied Environments[END_REF] with α = n α , ν = n ν , b = n b and n i j = 0, ∀i, j, belongs to N (Ξ ). The first statement is a consequence of the fact that the dimension of N (Ξ b ) is at least 3 when n i ≤ 3 (being the number of equations in ( 21) not more than 6 and the number of unknowns is 9).

Let us consider the case of n i = 4. Ξ b is a square matrix. We distinguish two cases: the case when the determinant of Ξ b vanishes and the case when is non-zero. In the first case the dimension of N (Ξ b ) is at least 1 and, as shown in the first part of this proof, also the dimension of N (Ξ ) is at least 1. In the second case, the linear system in (21) can be uniquely solved (for any set of vectors χ j ). Let us denote this solution with (α 0 , ν 0 , b 0 ). From ( 15) and ( 20) we obtain that the vector in [START_REF] Weiss | Monocular-SLAM-Based Navigation for Autonomous Micro Helicopters in GPS-Denied Environments[END_REF]

with α = α 0 , ν = ν 0 , b = b 0 , n 1 1 = n i j = -1, n 1 j = n i 1 = 1, (j = 2, 3, 4, i = 2, ..., N ) belongs to N (Ξ ).
Hence, also in this case the dimension of N (Ξ ) is at least 1.

Finally, the system in (21) can be solved for n i ≥ 5 if and only if the platform motion satisfies the equation χ j = -t 2 j 2 α 0 -t j ν 0 + Γ j b 0 . In this case, the vector n 0 in (17) becomes:

n b 0 ≡ [α T 0 , ν T 0 b T 0 , n1 1 , ..n i 1 .., ..n 1 j .., ..n i j ..] T , ( 22
)
and it is immediate to verify that n b 0 ∈ N (Ξ ) Note that, when b 0 = 0 3 , the special motion considered in this property is the motion with constant acceleration defined in the unbiased case.

We remark that, in the unbiased case, the platform rotations do not affect the problem resolvability. Indeed, in the matrix Ξ , only the third set of columns are affected by the platform rotations. In the biased case it is easy to prove the following property: Property 11 (Biased: impact of rotations, part 1) When the platform does not rotate the dimension of N (Ξ ) is at least 3. When the platform rotates always around the same axis the dimension of N (Ξ ) is at least 1.

Proof: : When the platform does not rotate Γ j = t 2 j 2 I 3 (see the definition of Γ j in ( 2)). Hence, the third set of columns coincides with the first set up to a sign. This means that the dimension of N (Ξ ) is at least 3. Let us consider the case when the rotations only occur around the same axis. We can assume without loss of generality that it is the z-axis (indeed, we can change the camera frame in such a way that its new z-axis is aligned with the axis of rotation). From the definition of Γ in (2) we remark that, in this case, the third column of Γ j coincides with the third column of T j in (8) up to a sign. Hence, the vector in [START_REF] Weiss | Monocular-SLAM-Based Navigation for Autonomous Micro Helicopters in GPS-Denied Environments[END_REF] with all the entries zero with the exception of the third and the ninth entry equal one each other, belongs to N (Ξ ) It also holds the following stronger property: Property 12 (Biased: impact of rotations, part 2) When the platform rotates always around the same axis the dimension of N (Ξ b ) is in general 1 (provided that n i ≥ 4). When the platform rotates around at least two independent axes the dimension of N (Ξ b ) is in general 0 (provided that n i ≥ 4).

Proof: : The proof of this property is much more troublesome than the proof of property 11. It becomes easier by assuming that the observations are provided continuously in time (i.e., if the discrete index j in (21) is replaced by the continuous index t). In the following, for the sake of clarity, we prove the two statements under this ideal assumption (which we will call the continuous assumption). Finally, we prove the first statement in the discrete case.

Under the continuous assumption, by differentiating three times equation ( 21) with respect to time we obtain:

d 3 Γ(t) dt 3 b = - d 3 χ(t) dt 3 .
From the definition of Γ(t) in ( 2) we obtain (we remind the reader that we set T in = 0):

dC t 0 dt b = - d 3 χ(t) dt 3 (23)
Since C t 0 is the rotation matrix generated by the angular speed Ω(t), we also have: [

dC t 0 dt = [Ω(t)] × C t 0 , where [Ω(t)] × ≡   0 -Ω z Ω y Ω z 0 -Ω x -Ω y Ω x 0   .
Ω(t)] × b = - d 3 χ(t) dt 3 (24)
INRIA For a non-zero Ω(t), the previous system has rank 2. Hence, it allows us to determine two components of b in terms of the third one. Additionally, by considering the system in (21) at two distinct times, it is possible to uniquely obtain the vectors α and ν in terms of b. Hence, the dimension of N (Ξ b ) is at most 1. On the other hand, by proceeding as in the proof of property 11 it is possible to show that, when the platform rotates always around the same axis, the dimension of N (Ξ b ) is at least 1. Therefore, the dimension of N (Ξ b ) is 1.

When the platform rotates around at least two independent axes, by taking (24) at two distinct times (where the two corresponding angular velocities are not proportional), we can determine all the three components of b. By considering the system in (21) at two distinct times, it is possible to uniquely obtain the vectors α and ν in terms of b, which is now determined. Hence, the dimension of N (Ξ b ) is 0.

We conclude this proof by considering the realistic discrete case and by proving only the first statement. By proceeding as in the proof of property 11 it is possible to show that, when the platform rotates always around the same axis, the dimension of N (Ξ b ) is at least 1. Hence, it sufficies to show that when

n i = 4 the dimension of N (Ξ b ) is in general 1. The matrix Ξ b is in this case: Ξ b =   T 2 S 2 Γ 2 T 3 S 3 Γ 3 T 4 S 4 Γ 4   (25)
By doing a Gauss elimination it is immediate to verify that the dimension of the null space of this matrix is equal to the dimension of the null space of the following 3 × 3 matrix:

Γ ≡ w 23 Γ 4 + w 24 Γ 3 + w 34 Γ 2 (26)
where w 23 = t 2 t 2 3 -t 2 2 t 3 , w 24 = t 4 t 2 2 -t 2 4 t 2 and w 34 = t 3 t 2 4 -t 2 3 t 4 . On the other hand, by setting, without loss of generality, the z-axis as the rotation axis, the matrix Γ j has the structure:

  c j s j 0 -s j c j 0 0 0 t 2 j 2 
 where c j ≡ tj 0 (t j -τ ) cos θ(τ )dτ , s j ≡ tj 0 (t j -τ ) sin θ(τ )dτ and θ(τ ) is the rotation accomplished by the platform up to time τ . By using this expression in (26) we obtain that the third line of Γ vanishes. In order to show that the dimension of N (Γ ) is in general 1 it suffices to prove that the following expression is in general different from zero: w 23 c 4 + w 24 c 3 + w 34 c 2 . We show that this expression is in general different from zero in the following infinite dimensional space of continuous function

V ≡ {f ∈ C 1 : [T in = 0, T f in ] → [-1, 1]}, i.e.
, that in this space the following equation holds in general4 :

w 23 t4 0 (t 4 -τ )f (τ )dτ + w 24 t3 0 (t 3 -τ )f (τ )dτ + +w 34 t2 0 (t 2 -τ )f (τ )dτ = 0 (27)

Simulations

In this section we show the benefit of using the closed solution for initializing a filter based approach to solve the Vi-SfM problem. Specifically, we generate noisy visual and inertial measurements through Monte Carlo simulations. Additionally, we corrupt the measurements provided by the accelerometers and the gyroscopes with a time dependent bias and we consider the case when the transformation between the visual and inertial sensors is not perfectly known.

In section 3 we formulated the Vi-SfM problem as the problem of determining the vectors: P i , (i = 1, 2, ..., N ), V , G (and also B in presence of bias). For the sake of clarity, in this section we choose to display the results in a global frame. For this reason, we need to consider at least two point-features. Indeed, two is the minimum number of point-features to uniquely define a global frame, provided that they do not lie on the same vertical axis (defined by the gravity). We define the global frame as follows: first, we define one of the point-feature as the origin of the frame. The z-axis coincides with the gravity axis but with opposite direction. Finally, the x-axis is defined by requiring that the second point-feature belongs to the xz-plane. In other words, the second point-feature has zero y-coordinate. In these settings, the Vi-SfM can be defined as the estimation of the platform configuration and the estimation of the x and the z coordinate of the second point-feature (from now on, p x and p z , respectively). By adding more point-features, the state to be estimated also includes all the three coordinates of each point-feature. We adopt an Extended Kalman Filter (EKF ) to perform this estimation. The state to be estimated is:

x e ≡ [r, v, q, p x , p z , B, B Ω , p 3 , ..., p N ] T
where q is a unit quaternion characterizing the platform orientation and B Ω is the bias on the measurements provided by the gyroscopes.

By collecting the sensor measurements during the time-interval [T in , T f in ], the closed solution discussed in the previous sections allows us to determine the vectors P i , (i = 1, 2, ..., N ), V , G and B at the time T in . Note that, when N ≥ 2, having the vectors P i , V , G and B at the time T in , allows us to build the state x e at time T in (with the exception of B Ω ). Since our simulated measurements are corrupted by noise and also include a bias on the gyroscopes and an error on the extrinsic camera-IMU calibration, the values obtained with the closed solution will differ from the true values.

In this section, we investigate how the performance of the EKF depends on its initialization and how this performance can be improved by using the closed solution to initialize the state. Since the closed solution does not provide the initial B Ω , its initial value will be set to zero. q(T in ) = 1, which corresponds to the platform attitude roll = pitch = yaw = 0 deg; B(T in ) = 0.05 μ m s -2 , B Ω (T in ) = 0.5 μ deg s -1 where μ is the unit vector pointing in the direction [1, 1, 1]; p x = 2m and p z = 1m. Both the biases are time-dependent. Specifically, they are modelled as independent random walks (for all the three components of both), whose mean values are the initial ones and their variances increase linearly with time. For the gyroscopes, the three variances are set equal to (50 deg/h) 2 at 100 s and for the accelerometers are set equal to (1 m/h 2 ) 2 at 100 s (see [START_REF] Woodman | An introduction to inertial navigation[END_REF]). We assume that the camera and the IMU frame coincide (i.e., they have the same origin and the same orientation). We characterize an error in the extrinsic calibration by setting the actual position of the origin of the camera frame in the IMU frame to [0.002, -0.003, 0.004]m and the actual orientation q cam = 1 -2. We also considered the case of more than two point-features (N ≥ 3), obtaining similar results in terms of performance and, for the sake of brevity, in the following we only refer to the case of N = 2.

The trajectories are generated by randomly generating the linear and angular acceleration of the platform at 100 Hz. In particular, at each time step, the three components of the linear acceleration and the angular speed are generated as zero-mean Gaussian independent variables whose covariance matrices are equal to (1ms -2 ) 2 I 3 and (10 deg s -1 ) 2 I 3 , respectively.

Simulated Sensors

Starting from the accomplished trajectory, the true angular speed and the linear acceleration are computed at each time step of 0.01s (respectively, at the j th time step, we denote them with Ω true j and A true j ). Starting from them, the IMU sensors are simulated by randomly generating the angular speed and the linear acceleration at each step according to the following:

Ω j = N Ω true j -B Ω (t j ), P Ω A j = N A true j -G(t j ) -B(t j ), P A
where:

• N (., .) indicates the Normal distribution whose first entry is the mean value and the second its covariance matrix;

• P Ω and P A are the covariance matrices characterizing the accuracy of the IM U .

In all the simulations we set both the matrices P Ω and P A diagonal and in particular: P Ω = (1 deg s -1 ) 2 I 3 and P A = (1 cm s -2 ) 2 I 3 .

Regarding the camera, the provided readings are generated in the following way. By knowing the true trajectory and the true camera-IMU transformation, the true bearing angles of the two point-features in the camera frame are computed. They are computed each 0.1s. Then, the camera readings are generated by adding to the true values zero-mean Gaussian errors whose variance is equal to (1 deg) 2 for all the readings.

Simulation Results

We first investigate the convergence of the EKF vs the initialization of the state. In all the considered initializations we set the initial accelerometer and gyroscope biases to zero. In general, the EKF diverges when:

1. the scale factor is initialized with an error which exceeds 20% 2. the attitude is initialized with an error which exceeds 4 deg These conclusions on the EKF convergence have been obtained by running many simulations with the settings specified in 5.2.1 and 5.2.2. As an illustration, we display here the results obtained with a particular trial. Figures 4567display the trajectories estimated by the EKF when the initial state differs from the true state because of an error on the absolute scale and on the attitude (as said, the initial state is also affected by an error on the inertial sensors' biases since they are always initialized to zero). Figure 4 displays the true trajectory (blue) together with the one estimated by only using inertial measurements (black) and the one estimated by the EKF with an initial absolute scale set to 1.1 times the true value and an error of 1 deg on the roll, pitch and yaw angles. Figure 5 displays the trajectories estimated by the EKF with an initial state affected by an error on the attitude (same error on the roll, pitch and yaw) and correct absolute scale. Figures 6 and7 display the trajectories estimated by the EKF with an initial state affected by an error on the absolute scale and correct attitude. By using the first 6 camera observations (i.e. by considering the time interval [T in = 0, T f in = 0.6]s) we obtain the initial position [0.4961, 0.4975, 0.5017]m, the initial speed [0.1024, 0.1028, 0.1222]m s -1 and the initial attitude q = 1 -4.3 10 -6 + (1.0i -2.3j + 1.6k) 10 -3 , which corresponds to the attitude roll = 0.11 deg, pitch = -0.26 deg and yaw = 0.18 deg. By running many simulations, we found that the initial state determined through the closed solution is never affected by an error larger than 8% regarding the absolute scale and than 0.7 deg regarding the attitude.

Conclusion

In this paper we derived a simple and intuitive closed solution to the visualinertial structure from motion problem. We used this derivation to investigate the intrinsic properties of the Vi-SfM problem and to identify the conditions under which the problem can be solved in closed form. In particular, we showed that the problem can have a unique solution or two distinct solutions or infinite INRIA solutions depending on the trajectory, on the number of point-features and their layout and on the number of monocular images where the same point-features are seen. The investigation was also performed in the case when the inertial data are biased, showing that, in this latter case, more images and more restrictive conditions on the trajectory are required in order to have a finite number of solutions. The most useful applications of the closed-form solution here derived will be in all the applicative domains which need to solve the SfM problem with lowcost sensors and which do not demand any infrastructure (e.g., in GPS denied environment). In these contexts, there is often the need to perform the estimation without any prior knowledge. Typical examples of applicative domains are the emergent fields of humanoid robotics and unmanned aerial navigation in urban-like environments [START_REF] Weiss | Monocular-SLAM-Based Navigation for Autonomous Micro Helicopters in GPS-Denied Environments[END_REF], where the use of the GPS is often forbidden. Additionally, our results could also play an important role in the framework of neuroscience by providing a new insight on the process of vestibular and visual integration for depth perception and self-motion perception. The influence of extra retinal cues in depth perception has extensively been investigated in the last decades. In particular, a very recent study investigates this problem by performing trials with passive head movements [5]. The conclusion of this study is that the combination of retinal image with vestibular signals can provide rudimentary ability to depth perception. Our findings could provide a new insight to this integration mechanism for depth perception since, according to the closed-solution here derived, by combining retinal image with vestibular signals it is possible to determine the scale factor even without any knowledge about the initial speed. Our findings also show that it is possible to easily distinguish linear acceleration from gravity. Specifically, the closed form solution performs this determination by a very simple matrix inversion. This problem has also been investigated in neuroscience [START_REF] Merfeld | Humans use internal models to estimate gravity and linear acceleration[END_REF]. Our results could provide a new insight to this mechanism since they clearly characterize the conditions (type of motion, features layout) under which this determination can be performed.

Theorem 1 (

 1 Number of Solutions) The Vi-SfM problem has a unique solution if and only if N (Ξ) is empty. It has two solutions, if and only if N (Ξ) has dimension 1 and, for any n ∈ N (Ξ), |Πn| = 0. It has infinite solutions in all the other cases.

  By using this equation in (23) and by denoting b ≡ C t 0 b we obtain:

Figure 2 :

 2 Figure 2: Illustration of two distinct solutions for the unbiased case with n i = 4, N = 1 (star symbols indicate the position of the point-feature respectively for the two solutions).

Figures 2 and 3

 3 Figures 2 and 3 illustrate two cases when the Vi-SfM problem has two distinct solutions. The platform configurations and the position of the pointfeatures in the global frame are shown. The two solutions are in blue and red. The platform configuration at the initial time is the same for both the solutions and it is in black. Both figures show unbiased cases. Fig 2 regards the case of one point-feature seen in four images. Fig 3 displays the case of constant acceleration: the case of three point-features in seven images has been considered and the seven poses of the platform at the time when the images are taken are shown in the figure together with the position of the point-features.

Figure 3 :

 3 Figure 3: Illustration of two distinct solutions for the unbiased case with constant acceleration (star symbols indicate the position of the point-features respectively for the two solutions).

INRIA

5. 2 . 1

 21 Simulated TrajectoriesAll the trajectories are randomly generated starting from the following initial true state: r(T in ) = [0.5, 0.5, 0.5]m; v(T in ) = [0.1, 0.1, 0.1]ms -1 ;

  3 10 -5 + (3.5i -5.2j + 2.6k) 10 -3 , which corresponds to the attitude roll = 0.4 deg, pitch = -0.6 deg and yaw = 0.3 deg.

INRIA

Figure 4 :

 4 Figure 4: True trajectory (blue); trajectory estimated with an EKF with initial error on the scale of 10% and on the attitude of 1 deg on the roll, pitch and yaw (red); trajectory estimated by only using inertial measurements (black).

Figure 5 :

 5 Figure 5: Trajectories estimated by the EKF when the initial state is affected by an error on the attitude.

Figure 6 :

 6 Figure 6: Trajectories estimated by the EKF when the state is initialized with an absolute scale which is larger than the true one (in particular, up to twice the true value).

Figure 7 :

 7 Figure 7: Trajectories estimated by the EKF when the state is initialized with an absolute scale which is smaller than the true one (in particular, up to half time the true value).

RR n°8076

This is equivalent to say that the position of any point-feature and the position of the platform at any time t j (j = 1, ..., n i ), are coplanar.INRIA

has further solutions and consequently n 0 is not the only generator of N (Ξ ) From now on, we will say that a condition is satisfied in general when the probability that it is not satisfied is zero. We remark that both conditions (i) and (ii) are met in general.Also for N > 2 there are still conditions, which occur with zero probability, under which the dimension of N (Ξ ) is larger than 1. We summarize the results of this subsection with the following property:

Note that it is not possible to proceed as in the unbiased case since it is not possible to separate the linear system in[START_REF] Longuet-Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF] in two parts because of the bias.RR n°8076

Note that we are not considering the space of the functions θ(τ ) but the space of the functions cos θ(τ ).RR n°8076

Property 5 (Unbiased with n i = 3, N ≥ 2) When n i = 3 and N ≥ 2 the Vi-SfM problem has in general two distinct solutions. In some special cases it has infinite solutions.

n i ≥ 4

When n i ≥ 4 the number of equations is larger than the number of unknowns, except when n i = 4 and N = 1. In this case the matrix Ξ is 9 × 10 and the dimension of its null space is at least 1. We have the following property: Property 6 (Minimal case: n i = 4, N = 1) The dimension of N (Ξ ) is 1 if and only if the four vectors P 1 1 , χ 2 , χ 3 and χ 4 span the entire 3D-space.

Proof: : If the vectors P 1 1 and χ j , j = 2, 3, 4, are coplanar, since N = 1, the dimension of N (Ξ ) is larger than 1 (see property 1). Let us suppose now that the vectors P 1 1 and χ j , j = 2, 3, 4 span the entire 3D-space. From the first 6 equations in (13) (i.e., the equation ( 14) for j = 2, 3) we obtain α and ν as linear functions of P 1 1 , χ 2 and χ 3 . By substituting the expressions of α and ν in the last three equations (i.e., in [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF] with j = 4) we obtain the following equation:

We analytically compute the determinant of the 4 × 4 matrix, which characterizes this linear system. We obtain:

. This determinant is always different from 0 (note that 0 < t 2 < t 3 < t 4 ). Hence, the previous linear system provides a unique solution and the dimension of N (Ξ ) is 1

We do not derive necessary and sufficient conditions for any value of n i and N . The following property holds: Property 7 (Unbiased with n i ≥ 4) When n i = 4 and N = 1 the Vi-SfM problem has in general two distinct solutions. If n i = 4, N ≥ 2 or if n i ≥ 5, ∀N it has in general a unique solution.

Proof: : Since the four vectors P 1 1 , χ 2 , χ 3 and χ 4 span in general the entire 3D-space, property 6 proves the first statement.

To prove the second part we start by considering the case n i ≥ 4 and N ≥ 2. In general, the three vectors P 1 1 , P i 1 and χ j are independent for each i = 2, ..., N and for each j = 2, ..., n i . Hence, from equation ( 15) we obtain:

If n 1 1 = 0, let us set, without loss of generality, n 1 1 = 1. Equation ( 14) becomes: -

For n i ≥ 4 this equation does not hold in general since it only holds for a motion with constant acceleration (this special case will be dealt in more detail in 4.1.6). Hence, n 1 1 = 0 and, consequently, n i j = 0 ∀i, ∀j. From ( 14) we also have α = ν = 0 3 . Therefore, the dimension of N (Ξ ) is 0.

Let us now consider the case n i ≥ 5 and N = 1. From property 6 we know that, in general, it exists one independent vector n4 ≡ [ αT , νT , n1

1 , n1 2 , n1 3 , n1 4 ] T satisfying equation ( 14) for j = 2, 3, 4. Hence, any solution of (13) must have the first ten components coincident with the ones of n4 or all the first ten components equal to zero. Let us consider a given j ≥ 5. In the former case (i.e., first ten components equal to n4 ), equation ( 14) reads as follows: -

which is not true in general) and, if n 1 j = 0, the vector P 1 1 + χ j must be parallel to the vector -

(which is not the case in general). In the latter case (i.e., all the first ten components equal to zero), equation ( 14) reads as follows: n 1 j (P 1 1 + χ j ) = 0 3 . Because of assumption 1 this holds if and only if n 1 j = 0

Constant acceleration

Let us consider the case when the platorm moves with constant acceleration, i.e. when χ j = ν 0 t j + α 0 t 2 j 2 , j = 2, ..., n i , where ν 0 and α 0 are two 3D-vectors. We already know from property 3 that the dimension of N (Ξ ) is at least 1. Specifically, the vector n 0 in [START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF] belongs to the null space of Ξ . In order to use theorem 1, we need to understand when N (Ξ ) has dimension equal or larger than 1. The following property provides a sufficient condition which ensures the Vi-SfM resolvability.

A probe for this is the one-dimensional space of all the constant function in [-1, 1]. This proves that the set T ⊂ V where (27) holds is prevalent (see [START_REF] Hunt | Prevalence: a translation-invariant "almost every" on infinite-dimensional spaces[END_REF] for the definition of probe and prevalence )

From property 10 we know that the dimension of N (Ξ ) is at least 3. Hence, the following property holds: Property 13 (Biased case, n i ≤ 3) The Vi-SfM problem has always infinite solutions in the biased case when n i ≤ 3.

n i = 4

From property 10 we know that the dimension of N (Ξ ) is at least 1. In order to apply theorem 1 we need to know when it is exactly 1, in which case the Vi-SfM problem has two distinct solutions. We have the following property: Property 14 (Biased case, n i = 4) In the biased case, when n i = 4 the Vi-SfM problem has always infinite solutions if N = 1 and in general two distinct solutions if N ≥ 2 and the platform rotates around at least one axis.

Proof: : Proving the first statement is trivial since for N = 1, the number of unknowns in ( 9) is 13 and the number of equations is 9. When N ≥ 2 the number of unknowns is smaller than the number of equations. We will prove that, when N ≥ 2, the dimension of N (Ξ ) is in general 1 both if the platform rotates around a single axis and if it rotates around two or more axes.

In general, the three vectors P 1 1 , P i 1 and χ j are independent for each i = 2, ..., N and for each j = 2, ..., n i . Hence, from equation ( 15) we obtain:

1 = 0 we have n i j = 0 ∀i, ∀j. Equation (20) becomes: -t 2 j 2 α-t j ν +Γ j b = 0 3 . From property 12 we conclude that it exists in general one independent vector n ∈ N (Ξ ) with n 1 1 = 0 only if the platform rotates around a single axis. If n 1 1 = 0 we can divide equation ( 20) by n 1 1 obtaining: -

From property 12 we conclude that this system has in general a unique solution if the platform rotates around at least two axes and in general no solution if it rotates around a single axis or it does not rotate. Hence, we conclude that it exists in general one independent vector n ∈ N (Ξ ) with n 1 1 = 0 only if the platform rotates around two or more axes.

In both cases (rotation around a single axis and rotation around two or more axes), the dimension of N (Ξ ) is in general 1

n i ≥ 5

We have the following property: Property 15 (Biased case, n i ≥ 5) In the biased case, when n i = 5 and N = 1 the Vi-SfM problem has always infinite solutions. When n i ≥ 5 and N ≥ 2, or when n i ≥ 6 and N = 1 the Vi-SfM problem has in general a unique solution if the platform rotates around at least two axes and two solutions if the platform rotates around a single axis.

INRIA

Proof: : When n i = 5 and N = 1 the number of unknowns in ( 9) is 14 and the number of equations is 12. This proves the first statement. When n i = 5 and N ≥ 2 and when n i = 6, ∀N , the number of unknowns is smaller than the number of equations.

Let us consider the case when N ≥ 2 and n i ≥ 5. We proceed exactly as for the proof of property 14. As in that proof, we conclude that it exists in general one independent vector n ∈ N (Ξ ) with n 1 1 = 0 only if the platform rotates around a single axis. On the other hand, we also conclude that in general it does not exist any vector n ∈ N (Ξ ) with n 1 1 = 0, independently of the platform rotations. This proves the statement when n i ≥ 5 and N ≥ 2.

It remains the case n i ≥ 6, N = 1. We start by considering the case when the platform rotates around two or more axes. First of all it suffices to consider the case n i = 6. Indeed, if the dimension of N (Ξ ) is zero when n i = 6, then equation ( 20) for j ≥ 7 becomes: n 1 j (P 1 1 + χ j ) = 0 3 which is true if and only if n 1 j = 0 because of the assumption 1. Let us consider the case n i = 6. From equation ( 20) for j = 2, 3, 4, thanks to the result stated by property 12, we know that in general we can express the vectors α, ν and b as linear combinations of n 1 1 P 1 1 , n 1 2 P 1 2 , n 1 3 P 1 3 and n 1 4 P 1 4 . By substituting these expressions in equation ( 20) for j = 5, 6 we obtain a homogeneous linear system of six equations in the six unknowns n 1 j , 1 ≤ j ≤ 6. In general, this system has full rank and therefore n 1 j = 0, 1 ≤ j ≤ 6.

Let us consider the case when the platform rotates around a single axis and n i ≥ 6, N = 1. Thanks to property 11 we know that the dimension of N (Ξ ) is at least 1. Specifically, we know that there is a non null vector in N (Ξ ) whose first nine components make a vector which belongs to N (Ξ b ). To prove that the dimension of N (Ξ ) is in general 1 we proceed as in the previous case. Also in this case it suffices to consider the case n i = 6. Indeed, if the dimension of N (Ξ ) is 1 when n i = 6, since the first nine components of the vector in N (Ξ ) are in N (Ξ b ), then equation [START_REF] Woodman | An introduction to inertial navigation[END_REF] for j ≥ 7 becomes as in the previous case: n 1 j (P 1 1 + χ j ) = 0 3 . Let us refer to the case n i = 6. This time, property 12 allows us to state that we can in general obtain 8 components among the nine components of the vectors α, ν and b as linear combinations of n 1 1 P 1 1 , n 1 2 P 1 2 , n 1 3 P 1 3 and n 1 4 P 1 4 and the remaining component (denoted with w) of the three vectors α, ν and b. By substituting these expressions in equation ( 20) for j = 5, 6 we obtain a homogeneous linear system of six equations in the seven unknowns n 1 j , 1 ≤ j ≤ 6 and w. In general, this system has a one dimensional null space 5 Discussion

Summary of the theoretical results

Tables 1 and2 summarize our results by providing the number of solutions case by case, respectively in the case without bias (table 1) and with bias (table 2). Note that these tables do not account the point-features layout. Specifically, the motion and the point-features are not supposed to be either coplanar or collinear. Regarding these cases, necessary conditions are provided in properties 1 and 2. In table 2, by motion with constant acceleration we mean the special motion described in property 10.

Cases

Number of Solutions Varying Acceleration

Unique Solution n i = 4, N ≥ 2 ; n i ≥ 5, ∀N Varying Acceleration Two Solutions