Jorge García Fontán

Abhilash Nayak
email: abhilash.nayak@ls2n.fr

Sébastien Briot
email: sebastien.briot@ls2n.fr

Mohab Safey
email: mohab.safey@lip6.fr

El Din

Jorge García Fontán
email: jorge.garcia-fontan@lip6.fr

Singularity Analysis for the Perspective-Four and Five-Line Problems

Keywords: Pose estimation, Visual servoing, Singularity, PnL

come

L'archive ouverte

Introduction

A standard problem in computer vision, which has many applications in augmented reality [START_REF] Marchand | Pose estimation for augmented reality: a hands-on survey[END_REF] and robotics (especially in visual servoing (Hutchinson et al, 1996a)) is the estimation of the pose based on the features projected in the camera image. When the 2D image is a set of n points that are projections of their 3D counterparts on the image plane, the problem is known as PnP (Perspective-n-Point) and has been dealt with extensively in literature [START_REF] Gao | Complete solution classification for the perspective-three-point problem[END_REF][START_REF] Horaud | Visually guided object grasping[END_REF][START_REF] Kneip | A novel parametrization of the perspective-three-point problem for a direct computation of absolute camera position and orientation[END_REF][START_REF] Wu | Pnp problem revisited[END_REF]. Similarly, when the features observed by the camera are n straight lines, the problem is referred to as PnL (Perspective-n-Line) [START_REF] Dhome | Determination of the attitude of 3-d objects from a single perspective view[END_REF][START_REF] Xu | Pose estimation from line correspondences: A complete analysis and a series of solutions[END_REF][START_REF] Wang | A novel algebraic solution to the perspective-three-line pose problem[END_REF].

In particular, PnP and PnL involve determining the six pose parameters of a camera (degrees of freedom corresponding to its position and orientation) belonging to the Special Euclidean group SE(3), from the 3D-2D correspondences of the n observed points or lines. By taking the time derivatives of the parameters involved in PnP or PnL, we obtain the so called motion-field equations (Longuet-Higgins and Prazdny, 1980) that are crucial to visual servoing in robotics. They involve the mapping between the time derivative of camera pose parameters belonging to se(3), being the Lie algebra of SE(3) (3D vector space of translational and orientational velocities of the camera) and the relative velocities of the projected features on the image plane, through the image Jacobian or interaction matrix [START_REF] Chaumette | La relation vision-commande: théorie et application à des tâches robotiques[END_REF][START_REF] Chaumette | Visual servo control, part ii: Advanced approaches[END_REF][START_REF] Chaumette | Visual Servoing and Visual Tracking, chapter 24 of Handbook of Robotics[END_REF].

Indeed, the problem of determining the singularities of the interaction matrix is crucial, especially for the following reasons:

-In visual servoing tasks, we face potential accuracy and controllability issues of the robot when the camera is in the vicinity of a singularity (Hutchinson et al, 1996b). -The singularities are known to considerably worsen the pose reconstruction accuracy (Pascual-Escudero et al, 2021). Moreover, their are known to influence the number of solutions to pose estimation problem as shown by [START_REF] Rieck | A fundamentally new view of the perspective threepoint pose problem[END_REF] and [START_REF] Zhang | Why is the danger cylinder dangerous in the p3p problem[END_REF] in the case of P3P.

However, determining those singularities is computationally heavy since it involves solving the complex algebraic systems arising due to the loss of rank of the interaction matrix. As a result, the singularity analysis in the past has been limited to simple image features, such as the observation of three points in space (P3P). For this problem, a well-known result is that a singularity occurs if the three points are aligned or if the camera lies on the cylinder that contains the three points and is perpendicular to the plane they define [START_REF] Michel | Singularities in the determination of the situation of a robot effector from the perspective view of 3 points Odenhal B[END_REF]. This result and tools from algebraic geometry were recently used by Pascual-Escudero et al (2021) to show that, in P4P, there are always two to six camera configurations where the corresponding interaction matrix becomes rank-deficient.

In the case of PnL, most of the research has been focused on finding solutions to P3L [START_REF] Dhome | Determination of the attitude of 3-d objects from a single perspective view[END_REF][START_REF] Xu | Pose estimation from line correspondences: A complete analysis and a series of solutions[END_REF][START_REF] Wang | A novel algebraic solution to the perspective-three-line pose problem[END_REF] without looking at the singularity problem, to the best of our knowledge. However, recently, the singularities in P3L were determined using a tool called the hidden robot which was introduced in [START_REF] Briot | Minimal representation for the control of gough-stewart platforms via leg observation considering a hidden robot model[END_REF]. It proved to be efficient in determining the singularities of vision-based controllers applied to parallel robots and broader classes of visual servo controllers [START_REF] Briot | The hidden robot: an efficient concept contributing to the analysis of the controllability of parallel robots in advanced visual servoing techniques[END_REF][START_REF] Rosenzveig | Minimal representation for the control of the Adept Quattro with rigid platform via leg observation considering a hidden robot model[END_REF]Briot et al, 2017a,b). With this method, it is possible to compute a simplified basis for the rows of the interaction matrix, based on the realization that they can be understood as a system of lines with Plücker coordinates. For the problem of visual servoing using three image lines, the hidden robot concept was used in Briot et al (2017b) to show that the singularities appear when the camera lies on a quadric or a cubic surface.

In this paper, we first provide a geometric interpretation of the results of Briot et al (2017b) and we exploit this interpretation in order to perform the singularity analysis for the generic P4L and P5L. In order to do so, we first identify a basis of the rows of the interaction matrix. Then, the conditions for degeneracy of this basis are obtained thanks to the use of Gröbner Bases [START_REF] Cox | Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra[END_REF]. Furthermore, we also provide the singularity loci when the lines are subjected to orthogonality and parallelism constraints. We focus on such type of lines because they often appear in a structured environment, e.g. edge tracking, navigation in urban areas, in corridors or any buildings, and are as a result commonly used as visual features for robot control tasks [START_REF] Andreff | Visual servoing from lines[END_REF]. Finally, simulations of camera motions near singularities are performed to illustrate their impact on robot control from visual servoing and on the pose estimation problem.

The structure of the paper is as follows: Section 2 recalls the form of the interaction matrix related to image lines and provides the computation of a simplified basis for its rows. Section 3 revisits the singularities in P3L (Briot et al, 2017b) and puts forth their geometric interpretation. Sections 4 and 5 give a complete analysis of singularities in P4L and P5L, respectively, with a focus on the special cases where the observed lines are bound by orthogonality and parallelism constraints. Section 6 presents experimental results from simulations based on the exposed singularities. Section 7 draws conclusions.

Row basis of the interaction matrix

In this section, we deal with the interaction matrix related to PnL which corresponds to the observation of n lines in space, and the computation of a new basis for the space spanned by its rows. It results in a simplified system of equations leading to a new interpretation of the results obtained in (Briot et al, 2017b).

Recalls on the interaction model related to image lines

In what follows, and without loss of generality, we will use the standard pin-hole camera model with focal length equal to 1, and the z-axis oriented along the optical axis. However, any other camera model based on projective geometry could be used [START_REF] Michel | Singularities in the determination of the situation of a robot effector from the perspective view of 3 points Odenhal B[END_REF].

There are several possibilities for describing a line in 3D space. Here we will use the Plücker representation which is free of representation singularities, and will be helpful later for expressing a basis of the interaction matrix.

Let us start by reviewing the geometric description of lines by Plücker coordinates. A 3D line L i can be characterized in the camera frame by a Plücker vector [u T i l T i ] T ∈ R 6 , where u i is the direction of the line, and l i = x × u i , with x = # » CP i the position vector from the focal point C to any point P i on the line.

L i P i u i l i Π i ℓ i O p i u ′ i l ′ i
Fig. 1: Observation of a line.

The 3D line L i projects on the image plane of the camera on a 2D line i (see Fig. 1) with Plücker coordinates [u i T l i T ], where u i is the image line direction, and l i = x × u i for any point on i with position vector x . The coordinates of L i and of its projection are related by the perspective equations [START_REF] Chaumette | La relation vision-commande: théorie et application à des tâches robotiques[END_REF]:

u i =            u xi u yi u zi            =           L yi /∆ i -L xi /∆ i 0           ; l i =            l xi l yi l zi            =           L xi /∆ i L yi /∆ i L zi /∆ i           (1)
where

l i = [L xi L yi L zi ] T and ∆ i = L 2 xi + L 2
yi is a depth factor. The image line i is fully determined from the three coordinates l xi , l yi and l zi , so it suffices to use l i as the vector of features for the line in the visual servo scheme.

A relative camera-object velocity, represented by the velocity twist

τ c = [v T c ω T c ] T
, where v c and ω c are respectively the linear and angular velocity vectors expressed in the camera frame, will induce a variation of the image feature coordinates l xi , l yi and l zi , according to the relation

l i = M i τ c . (2)
The interaction matrix M i , which was derived in [START_REF] Chaumette | La relation vision-commande: théorie et application à des tâches robotiques[END_REF], has dimension (3 × 6), but maximum rank 2. Hence, we can control at maximum two degrees of freedom of the camera with each image line, and at least three lines are necessary to fully constrain the system [START_REF] Andreff | Visual servoing from lines[END_REF].

For the observation of n > 1 lines, the interaction matrix M (n) , relating a change in the vector of features ṡ = [ l T 1 , . . . , l T n ] T to the camera velocity, is obtained by stacking the three rows of M i corresponding to each line L i :

M (n) = [M T 1 , M T 2 , . . . , M T n ] T . (3)
2.2 Revisiting the interaction matrix as a system of Plücker lines

Differentiating the vector l i in (1) with respect to time we obtain:

l i = 1 ∆ 3 i            L 2 yi -L xi L yi 0 -L xi L yi L 2 xi 0 -L xi L zi -L yi L zi ∆ 2 i                      Lxi Lyi Lzi           =           p T 1 p T 2 p T 3           li . (4)
The variation of the coordinates l i of the 3D line is linked to the velocity twist of the camera by the relation: li = v c × u i +ω c ×l i [START_REF] Chaumette | La relation vision-commande: théorie et application à des tâches robotiques[END_REF][START_REF] Rives | Estimation recursive de primitives 3d au moyen d'une caméra mobile[END_REF], which can be expressed in matrix form as li

= [u i ] T × [l i ] T × τ c . (5)
Here [u i ] × and [l i ] × denote the cross-product matrices associated to vectors u i and l i . Introducing ( 5) in (4), we arrive at an expression for the interaction matrix:

M i =           (u i × p 1 ) T (l i × p 1 ) T (u i × p 2 ) T (l i × p 2 ) T (u i × p 3 ) T (l i × p 3 ) T           . ( 6
)
By analysing the matrix in (4), we see that the first and second rows are related by L xi p 1 + L yi p 2 = 0. Note that the row vectors p j are all orthogonal to l i , and that p 3 is linearly independent from p 1 , p 2 as long as ∆ i = 0. Since l i is defined as l i = # » CP i ×u i , the vectors {p 1 , p 2 , p 3 } span the same subspace as { # » CP i , u i }, namely, the plane Π i containing the line and the focal point C, and whose normal has direction l i .

As a consequence, the vectors u i × p j and l i × p j in (6) are mutually orthogonal for each j and therefore, the rows of the interaction matrix M i can also be regarded as the coordinates of a system of Plücker lines.

Change of basis for the rows of the interaction matrix

The result that the rows of the matrix in (6) define a system of lines was generalized in (Briot et al, 2017b) to obtain a new basis ξ i for the rows of M i .

To start, the fact that vectors {p 1 , p 2 , p 3 } in (4) span the same subspace as { # » CP i , u i } implies that there exist two vectors µ i1 and µ i2 , collinear with # » CP i and with u i respectively, which are linear combinations of p 1 , p 2 and p 3 :

µ i1 = 3 j=1 a j • p j ∝ # » CP i , µ i2 = 3 j=1 b j • p j ∝ u i . (7)
Assuming that the factor ∆ i in (4) is non-zero, there exists a transformation matrix H i , which is always of rank 2,

H i = a 1 a 2 a 3 b 1 b 2 b 3 , (8)
such that the product H i • M i is, after some manipulation,

H i • M i =         (u i × µ i1 ) T # » CP i × (u i × µ i1 ) T 0 1×3 u i × (µ i2 × # » CP i ) T         . (9)
The matrix ( 9) is in fact proportional to the basis ξ i for the rows of M i , obtained differently in (Briot et al, 2017b), and which can be expressed as

ξ i = ξ i1 ξ i2 = f T i1 ( # » QP i × f i1 ) T 0 1×3 m T i2 , (10)
where

f i1 ∝ u i × # » CP i , m i2 ∝ u i × f i1 , (11)
and Q is any point in space. Note that, by definition, f i1 is any vector normal to the plane Π i which contains the line and the focal point C, and m i2 is any vector orthogonal to both f i1 and the line direction u i .

Let us remark that, in (10), the vector ξ i1 represents a straight line passing through the point P i with direction f i1 , while ξ i2 can be regarded as a line at infinity (alias an ideal line) in the projective space, with direction m i2 .

Some observations arise from the fact that the basis ξ i is spanned by a system of lines:

-Degeneracy of a system of lines is independent of the choice of point Q (appearing in ( 10)) at which the lines are expressed. Nevertheless, when computing the analytical expressions, all lines must be given in reference to the same point. Note however that the vector f i1 is still dependent on the location of C. -The conditions for degeneracy of any system of lines depend only on the relative configuration of the lines (Briot et al, 2017b;[START_REF] Kanaan | Singularity analysis of lower mobility parallel manipulators using grassmann-cayley algebra[END_REF]. Specifically, they are independent of the frame where the Plücker vectors are expressed, and therefore of the relative orientation of the object and camera frames.

In particular the second remark will be useful to simplify the computations in the following sections by assuming a constant zero orientation for the camera.

The new basis ξ i is a valid representation so long as the depth factor 1) is non-zero. This excludes only 2 camera configurations: 1) when line L i is fully contained in the plane Z = 0 of the camera frame and 2) when the focal point C lies on the line L i ; in both situations the coordinates L xi and L yi vanish. These are degenerate cases for which the projection mapping in (1) is ill-defined, so we will not consider them in the sections that follow.

∆ i = L 2 xi + L 2 yi appearing in (
Finally, based on the previous results, a basis ξ (n) for the full interaction matrix M (n) is obtained by stacking the rows of (10) for each line i:

ξ (n) = [ξ T 1 ξ T 2 . . . ξ T n ] T ∈ R 2n×6 . ( 12
)
For instance, a basis for the interaction matrix M (3) corresponding to P3L is given by ξ

(3) = [ξ T 11 ξ T 12 ξ T 21 ξ T 22 ξ T 31 ξ T 32 ]
T . The singularities of this matrix were analysed algebraically in (Briot et al, 2017b). These results are revisited in the next section with a geometric point of view, which will then be used to analyse the singularities both algebraically and geometrically in the observation of more than three lines.

3 Revisiting singularities in P3L

Parametrization

Since the set of lines in the three dimensional projective space P 3 is a four-dimensional manifold, a line can be defined using four independent parameters. In the Plücker representation of lines as described in Section 2.1, only four out of the six Plücker coordinates are independent. Hence, we need 12 parameters to define three generic lines. The object frame

F o : (O, x o , y o , z o
) is fixed relative to the three lines, with its axes defining an orthonormal, right-handed basis. The first line can be placed on the x o axis and the second line parallel to the plane z o = 0 and intersecting the z o axis. Any other line can be defined using its points of intersection with any two of the three planes x o = 0, y o = 0 or z o = 0. So, the third line is defined using its points of intersection with the plane x o = 0 and z o = 0. This leaves us 7 parameters to define three lines using the following two points P i and N i on each line.

---→ OP 1 = [0, 0, 0] T , ---→ ON 1 = [1, 0, 0] T , ---→ OP 2 = [0, 0, d 1 ] T , ---→ ON 2 = [r 1 , r 2 , d 1 ] T , ---→ OP 3 = [d 2 , d 3 , 0] T , ---→ ON 3 = [0, r 3 , r 4 ] T . (13)
Since the rows of the interaction matrix defined in Section 2.3 consist of some affine and ideal lines, defined using the direction vector of the lines, the parametrization can be simplified by considering the direction vector u i = --→ OP i ---→ ON i , i = 1, 2, 3 and changing the parameters -r 1 = s 1 , -r 2 = s 2 , -r 4 = s 4 , d 3r 3 = s 3 as follows:

---→ OP 1 = [0, 0, 0] T , u 1 = [1, 0, 0] T , ---→ OP 2 = [0, 0, d 1 ] T , u 2 = [s 1 , s 2 , 0] T , ---→ OP 3 = [d 2 , d 3 , 0] T , u 3 = [d 2 , s 3 , s 4 ] T . ( 14
)
We also define the position of the focal point C in frame F o by the vector o # » OC = [X Y Z] T and define the camera frame F c : {C, x c , y c , z c } centred at C, with x c , y c , z c also an orthonormal basis. It was noted in Section 2.3 that the singularity conditions of the problem are independent of the relative orientation of the object and camera frames. Hence, for the computations we will assume that F c can be obtained from F o by a direct translation by the vector o # » OC. The singularity loci will be given in terms of the location of the focal point C relative to the fixed object frame F o , that is as a set of expressions involving variables X, Y and Z. If F o and F c do not share the same orientation, we can retrieve the position of the origin O expressed in the camera frame F c by introducing a new set of variables X , Y , Z such that

c # » CO =           X Y Z           = -c R o • o # » OC = -c R o •           X Y Z           , ( 15
)
where the matrix c R o represents the relative camera-object orientation. In the following, we assume c R o is the identity matrix.

Geometric interpretation of singularities in P3L

Singularities in the observation of three lines have already been determined algebraically (Briot et al, 2017b). In this section, we provide the geometric interpretation of those results which will aid us in determining the singularities in P4L and P5L. By choosing the point Q in (10) as the camera center C, we have

ξ i = ξ i1 ξ i2 =       f T i1 ( --→ CP i × f i1 ) T 0 (1×3) m T i2       , (16)
where

--→ CP i = --→ OP i - --→ OC with --→ OC = [X, Y
, Z] T being the position vector of the camera center. Consequently, a basis for the rows of the interaction matrix M (3) can be obtained under the form ξ

(3) = [ξ T 11 ξ T 12 ξ T 21 ξ T 22 ξ T 31 ξ T 32 ]
T . It was proven in (Briot et al, 2017b) that the degeneracy of the basis ξ (3) and thus of the interaction matrix M (3) occurs if and only if one of the following two conditions is satisfied:

G = f 11 • (f 21 × f 31 ) = 0 (17)
or

H = m 12 • (m 22 × m 32 ) = 0, ( 18
)
that is, when the three vectors f i1 , i = 1, 2, 3 (respectively, m i2 ) defined in (11) are parallel to the same plane. The product G • H is in fact the determinant of the matrix ξ (3) . In the case of three general lines observed in space, it was shown in (Briot et al, 2017b) that a singularity appears when the camera lies either on a quadric or on a cubic surface, defined respectively by ( 17) and ( 18). The quadratic factor (17) using the parametrization ( 14) is as follows:

(19)

G = d 1 s 2 s 4 XY -s 2 (d 1 s 3 + d 3 s 4 ) XZ -d 1 s 1 s 4 Y 2 + (d 1 s 1 s 3 + d 2 s 2 s 4 ) YZ -d 1 s 4 (d 2 s 2 -d 3 s 1 ) Y + d 2 s 2 (d 3 -s 3 ) Z 2 -d 1 d 2 s 2 (d 3 -s 3 ) Z.
It is a hyperboloid of one sheet, leading to the following theorem.

Theorem 1 The quadratic factor corresponding to singularities in P3L implies that the camera center lies on the hyperboloid of one sheet uniquely defined by the three observed lines.

Proof. The quadric factor is the determinant of the upper left (3 × 3) matrix of the basis ξ (3) . Let the kernel of the matrix f 11 f 21 f 31 be the direction vector of a line L. Since the affine lines are represented according to (11), the line L must lie in a plane containing --→ CP i and u i , say Π i . Consequently, L has to intersect all u i and therefore the observed

C (X,Y,Z) M 1 u 2 M 2 M 3 f 31 f 11 f 21 u 3 u 1 L Fig. 2:
One of the singularities in P3L is when the camera center C lies on the hyperboloid formed by the three observed lines.

three lines (see Fig. 2). As a result, it belongs to the complementary regulus of a hyperboloid of one sheet defined by the regulus of the observed lines (Odenhal et al, 2020, Chapter 2). L is called the transversal line. Moreover, L must be the intersection of planes Π 1 , Π 2 and Π 3 . Since C belongs to Π i ∀ i, it should lie in their intersection too and hence L has to contain C.

Remark When the camera center C lies on the hyperboloid defined by the three observed lines, the kernel of the interaction matrix ξ (3) is an ideal line whose moment vector is the same as the direction vector of the line passing through C and intersecting the observed lines. As a result, we face problems in control for infinitesimal translations of the camera along the transversal line. Remark When the camera center C lies on the hyperboloid defined by the three observed lines, the finite lines constituting the rows of the interaction matrix are all parallel to the same plane whose normal vector is along the transversal. Then, the six lines ξ i1 and ξ i2 , i = 1, 2, 3 are said to be in a singular linear line complex (Pottmann and Wallner, 2001, Chapter 3). The latter remark assures that the kernel of the interaction matrix represents the Plücker coordinates of a line. In terms of screw theory [START_REF] Hunt | Kinematic Geometry of Mechanisms[END_REF], it is always a screw of infinite pitch.

Unfortunately, the geometric interpretation is not straightforward when C lies on the cubic surface H = 0 of (18) leading to singularities. In this case, the lines ξ i1 and ξ i2 belong to a regular linear line complex (Pottmann and Wallner, 2001, Chapter 3). In terms of screw theory [START_REF] Hunt | Kinematic Geometry of Mechanisms[END_REF], the kernel is no longer a line but a screw, meaning that the controllability issues arise when the camera performs this instantaneous screw motion. Additionally, unlike the hyperboloid, the cubic surface is not uniquely defined by the three observed lines. This is due to a classic result from Geometry by Arthur Cayley and George Salmon who showed in 1849 that there are 27 lines on a cubic surface (refer to [START_REF] Lazarus | Basic algebraic geometry and the 27 lines on a cubic surface Longuet-Higgins HC, Prazdny K (1980) The interpretation of a moving retinal image[END_REF] for a proof from an algebraic geometry point of view). Therefore, computational algebraic techniques will be employed to deal with this singularity in the case of P4L.

Singularities in P4L

4.1 Parametrization Following Section 3.1, the first three lines are defined according to (14). The fourth line is defined using its two points of intersection P 4 and N 4 with the planes x o = 0 and y o = 0, respectively:

---→ OP 4 = [0, d 4 , d 5 ] T , ---→ ON 4 = [r 5 , 0, r 6 ] T . ( 20
)
Thus, the direction vector of the fourth line is given by u 4 = ---→ OP 4 ----→ ON 4 . After replacing -r 5 and d 5r 6 by s 5 and s 6 , respectively, we have

---→ OP 4 = [0, d 4 , d 5 ] T , u 4 = [s 5 , d 4 , s 6 ] T . ( 21
)
As mentioned in Section 3.1, the assumption that the relative orientation between the camera frame F c and the object frame F o is zero remains valid in the following analysis.

Singularity analysis

From the remarks made in Section 2.3, a basis

ξ i = [ξ T i1 ξ T i2 ]
T for the rows of the interaction matrix for each line is computed as in (10), with point Q taken as the camera center C, and with vectors f i1 and m i2 given by ( 11).

Singularities of the interaction matrix M (4) of the four lines appear when the (8 × 6) matrix

ξ (4) = [ξ T 1 ξ T 2 ξ T 3 ξ T 4 ] T , (22)
formed by stacking the rows in (10) for all lines, becomes rank-deficient. This is the case if and only if all the 28 maximal minors of ( 22) vanish simultaneously.

All the entries of the matrix ξ (4) are polynomials in the variables {X, Y, Z} representing the camera location, with coefficients which are polynomials in the parameters η

= {s 1 , s 2 , s 3 , s 4 , s 5 , s 6 , d 1 , d 2 , d 3 , d 4 , d 5 }.
The minors of ξ (4) then form a system of 28 polynomials p i , which are said to generate an ideal (refer to [START_REF] Cox | Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra[END_REF] for more information about ideals), denoted by I 28 = p 1 , p 2 , . . . , p 28 . An ideal is defined as follows: let f 1 , . . . , f s in Q[x 1 , . . . , x n ] be a set of polynomials in the variables x 1 , . . . , x n with coefficients in the field of rational numbers Q; the ideal generated by f 1 , . . . , f s is the set

f 1 , . . . , f s =        s i h i f i | h i ∈ K[x 1 , . . . , x n ]        (23)
of all polynomials which are algebraic combinations of its generators. By this definition, any common solution of the system p 1 = • • • = p 28 = 0 formed by the minors of ξ (4) is also a solution of any polynomial in the ideal I 28 .

In geometric terms, the locus of complex solutions of a system of polynomial equations is called a variety. The (complex) solutions of all the polynomials in I 28 define a variety V(I 28 ) ⊂ C 14 , which consists of all points where the matrix ξ (4) becomes rank-deficient.

To get a better insight of V(I 28 ), we describe below how it can be split into subsets, i.e. written as the union of solution sets of simpler polynomial systems of equations.

Consider the 28 maximal submatrices of size (6 × 6) of ξ (4) . There are three types of them:

ξ i j 1234 =                              f T i1 ( --→ CP i × f i1 ) T f T j1 ( --→ CP j × f j1 ) T 0 (1×3) m T 12 0 (1×3) m T 22 0 (1×3) m T 32 0 (1×3) m T 42                              , ( 24
)
ξ i jk lmn =                               f T i1 ( --→ CP i × f i1 ) T f T j1 ( --→ CP j × f j1 ) T f T k1 ( --→ CP k × f k1 ) T 0 (1×3) m T l2 0 (1×3) m T m2 0 (1×3) m T n2                               , (25)
ξ 1234 lm =                               f T 11 ( --→ CP i × f 11 ) T f T 21 ( --→ CP j × f 21 ) T f T 31 ( --→ CP k × f 31 ) T f T 41 ( --→ CP l × f 41 ) T 0 (1×3) m T l2 0 (1×3) m T m2                               , ( 26
)
where i, j, k and l, m, n range every triplet of numbers in {1, 2, 3, 4}.

There are six submatrices of type ξ i j 1234 and their determinants are zero since out of four lines at infinity, only three can be independent and hence, the matrix always has a rank of at most 5.

The second category of block-triangular submatrices are composed of row vectors that represent three affine lines and three lines at infinity. There are 4 3 × 4 3 = 16 of them. The determinants of ξ i jk lmn are of the form G i jk • H lmn , with:

G i jk = f i1 • (f j1 × f k1 ), H lmn = m l2 • (m m2 × m n2 ). ( 27
)
The cases where the subindices {i, j, k} and {l, m, n} coincide correspond to the singularity conditions ( 17) and ( 18) in P3L for each triplet of lines taken individually. Thus, it is useful to note that for a singularity of the four lines, a necessary, but not sufficient condition is that each triplet of lines is in turn in a singular configuration. It follows that the union of ideals I 16 and K yields I 28 . Dually, the intersection of their varieties yields V(I 28 ) (see [START_REF] Cox | Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra[END_REF] for more information on correspondence between ideals and varieties):

I 28 = I 16 ∪ K =⇒ V(I 28 ) = V(I 16 ) ∩ V(K), (28)
We first thoroughly analyze the ideal I 16 to show how it can be further decomposed into two sub-ideals and then incorporate the analysis of K. Note that all mathematical derivations shown below can be followed in the attached Maple file. Since a solution of the polynomials in I 28 must also be a solution for the polynomials in I 16 , we say that the variety V(I 28 ) is contained in V(I 16 ):

I 16 ⊆ I 28 =⇒ V(I 28 ) ⊆ V(I 16 ), (29)
although V(I 16 ) may contain points outside V(I 28 ).

The ideal I 16 can be factorized as the product of two simpler ideals:

I 16 = G × H, (30)
where

G = G 123 , G 124 , G 134 , G 234 , (31)
H = H 123 , H 124 , H 134 , H 234 . ( 32
)
It implies that the variety V(I 16 ) is the union of two smaller sets:

V(I 16 ) = V(G) ∪ V(H).
That is, the polynomials in I 16 vanish whenever G i jk = 0 for all i, j, k; or when H lmn = 0 for all l, m, n. As a consequence, we can rewrite (28) as

V(I 28 ) = (V(G) ∪ V(H)) ∩ V(K) = (V(G) ∩ V(K)) ∪ (V(H) ∩ V(K)) . (33)
The variety V(G) defined by the ideal in (31) in C[X, Y, Z] describes the intersection between four hyperboloids, while V(H) defined by ( 32) is the intersection of four cubic surfaces.

We can analyze the sub-varieties on the right hand side of (33) separately. First, we can check if

V(K) or a compo- nent of it lies in V(G) or V(H). For instance, if V(G) ⊂ V(K)
then the analysis is much simpler since the intersection between those varieties would just yield V(G). So, to check if the varieties share any component, we need to know the following definitions.

Ideals can have different bases: there are many different polynomials which generate the same family of polynomial combinations. A particularly useful basis for an ideal I is the Gröbner Basis [START_REF] Cox | Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra[END_REF]. It is defined as a set of polynomials gb = {g 1 , . . . , g s } in I whose leading monomials LM(g i ) generate the same ideal as all the leading monomials in I, that is, LM(g 1 ), . . . , LM(g s ) = LM(I) . A Gröbner Basis gb is only dependent on any set of generators of I and an ordering of the monomials " ", which must be specified a priori, and is unique up to certain algorithmic reductions. One can refer to [START_REF] Cox | Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra[END_REF] for detailed information on the properties of Gröbner Bases. A useful consequence of this definition is that any polynomial f can be written as an algebraic combination of the elements of gb plus a residue term f gb which is unique:

f = s 1 h i g i + f gb . This residue f gb
is called the normal form of f w.r.t. the basis gb, and it vanishes if and only if the polynomial f belongs in the ideal I. Hence, when f gb = 0, the solutions of the system

g 1 = • • • = g s = 0
are also solutions of f = 0. We can use this to find the Gröbner bases of ideals G and H and then to find the normal form of polynomials in K w.r.t to those bases. This will help us find which of the solutions of the ideal I 16 = G × H are also solutions of the larger ideal

I 28 .
In what follows, the analysis is done separately for varieties

V(G) ∩ V(K) and V(H) ∩ V(K) of (33). 4.3 Analysis of the variety V(G) ∩ V(K)
Let gb G = {g 1 , . . . , g s } be a Gröbner Basis of the ideal G with respect to pure lexicographical monomial ordering (denoted by lex ; see [START_REF] Cox | Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra[END_REF]) for information about using different monomial orderings in the computation of Gröbner Bases) with X lex Y lex Z lex s 1 lex . . . lex s 6 lex d 1 lex . . . lex d 5 . Here, we are assuming that our polynomials lie in the ring Q[X, Y, Z, η] of polynomials in variables X, Y, Z and η with rational coefficients, where η = {d 1 , . . . , d 5 , s 1 , . . . , s 6 }. By considering s 1 , . . . , d 5 as variables, our Gröbner Bases computations will be valid under any specialization of the parameters.

Knowing gb G , we can compute the normal form of the polynomials p i ∈ K, i = 1, . . . , 6 to check if the varieties V(G) and V(K) share any component. It can be done using a multivariate polynomial division algorithm (see the attached Maple file) and we find that they vanish in every case: p i g 1 ,...,g s = 0. The consequence is that any common solution of the system g 1 = • • • = g s = 0 is also a solution of the system p 1 = • • • = p 6 = 0 and is therefore a singular point of the matrix ξ (4) . In terms of algebraic varieties, this can be written as

V(G) ⊆ V(K) and hence V(G) ∩ V(K) = V(G). ( 34
)
As a result, Equation (33) can be updated as

V(I 28 ) = V(G) ∪ (V(H) ∩ V(K)) , (35)
implying that one of the singularities in P4L is when the camera center lies on the intersection of the four hyperboloids given by the variety V(G).

Additionally, this result can be geometrically interpreted as follows. The basis of the interaction matrix M (4) in this case consists of four affine lines and four ideal lines. As we know from Section 3, one of the singularities in P3L is when the three affine lines belong to a singular linear line complex (meaning that they are parallel to the same plane; see Remark 3.2). When this happens, the kernel of the interaction matrix is a line at infinity (see Remark 3.2) and the camera center lies on a line that intersects all the three observed lines. Similarly, in the case of P4L, V(G) results in four affine lines of ξ (4) being parallel to the same plane so that its kernel is a line at infinity. Hence, we can expect that a singularity occurs when the camera center lies on a line that intersects the four observed lines. In fact, this is true for singularities in PnL for any n ≥ 3.

Theorem 1 A singular configuration of PnL is when the camera center C lies on the line(s) intersecting the observed lines.

Proof. Let the observed lines be L 1 , L 2 , . . . , L n . Given a line L on which C lies, the distance between lines L and L i is given by

d LL i = ( l × li ) T || l × li || ( --→ OC - --→ OP i ) , (36)
where P i is a point on line L i , l and li are unit direction vectors of lines L and L i , respectively. L and L i intersect when

(l × l i ) T ( --→ OC - --→ OP i ) = 0, ( 37
) (l i × --→ CP i ) T l = 0. ( 38
)
It follows from ( 11) that f T i1 l = 0, i = 1, . . . , n. Thus, for n lines, the matrix ξ (n) in ( 12) has a kernel which represents a line at infinity with Plücker coordinates (0, l) and hence it is singular.

For n = 3, the locus of lines intersecting the three observed lines is a hyperboloid of one sheet. For n = 4, in the generic case, it is two lines and the observed lines belong to a linear line congruence (Pottmann and Wallner, 2001). For n = 5, it is just a line and the observed lines belong to a linear line complex (Pottmann and Wallner, 2001).

Moreover, the variety of the ideal G in (31) consists of two lines which are also the intersections of the four hyperboloids G 123 = G 124 = G 134 = G 134 = 0. These transversal lines can be real or complex.

In the real domain R[X, Y, Z], the intersection of the four hyperboloids i.e. V(G) can be an empty set, a line or two lines. If we consider the hyperboloid defined by the first three observed lines, assuming the fourth line does not lie entirely on the hyperboloid, it can intersect the hyperboloid in 0, 1 or 2 points. Then, the four lines are said to be in an

L 1 L 2 L 4 L M L N L 3
Fig. 3: Four observed lines L i , i = 1, 2, 3, 4 in a hyperbolic congruence leading to two singular lines L M and L N . elliptic, a parabolic or a hyperbolic line congruence, respectively (Pottmann and Wallner, 2001). A case of hyperbolic congruence is shown in Fig. 3. A line passing through the point of intersection and lying on the hyperboloid intersects all four lines. By forcing the four observed lines to be in an elliptic congruence, we can avoid these singularities as follows.

By finding the Gröbner basis of the ideal G with respect to the monomial ordering Y Z X, we obtain four polynomials, of which the first polynomial is as follows:

a 2 Y 2 + a 1 Y + a 0 = 0, ( 39
)
where

a 2 = d 1 s 4 (d 2 s 2 s 6 -d 3 s 1 s 6 -d 4 d 5 s 1 + d 4 s 1 s 6 + d 5 s 2 s 5 ) , a 1 = (d 1 d 2 d 3 s 2 s 6 -d 1 d 2 d 4 s 2 s 4 -d 1 d 2 s 2 s 3 s 6 + d 1 d 3 d 4 s 1 s 4 + d 1 d 4 d 5 s 1 s 3 -d 1 d 4 s 1 s 3 s 6 -d 1 d 4 s 2 s 4 s 5 -d 1 d 5 s 2 s 3 s 5 + d 2 d 4 d 5 s 2 s 4 -d 2 d 4 s 2 s 4 s 6 -d 3 d 5 s 2 s 4 s 5 )Z, a 0 = -d 4 s 2 (d 1 d 2 d 3 -d 1 d 2 s 3 -d 1 s 3 s 5 -d 2 d 3 d 5 + d 2 d 3 s 6 + d 2 d 5 s 3 -d 2 s 3 s 6 -d 3 s 4 s 5 )Z 2 .
Since the variety of G represents two real or complex lines, the quadratic element (39) must factorize into two linear polynomials which represent the planes containing the two lines that are transversal to the four observed lines (the remaining elements of the Gröbner basis can be used to deduce the equations of the two lines that constitute V(G); see Appendix A for an example). These planes and hence the transversals lying on them are either real or complex depending on the sign of the discriminant of (39). The equation (39) has no real solutions if the discriminant

∆ = a 2 1 -4a 2 a 0 = Z 2 f (η) < 0, ( 40
)
where f (η) is a function of the parameters η. Since Z 2 ≥ 0, a necessary condition that there are no real transversals intersecting the four observed lines can be given by an inequality solely in terms of the Plücker coordinates of the four observed lines. This helps us avoid the one dimensional singularities due to V(G). This is quite useful as we will see in the next section that the remaining singularities due to V(H) ∩ V(K) are only of dimension zero, implying that they are isolated points.

All in all, in the case of P4L, we have a singularity when C lies on any transversal line that intersects the four observed lines. The transversal appears as the intersection of the hyperboloids defined by four triplets of the observed lines.

Moreover, by forcing the four observed lines to be in an elliptic congruence, we can make sure that their transversals are not real and therefore avoid the one dimensional singularities.

Analysis of the variety V(H) ∩ V(K)

The analysis of the component V(H) ∩ V(K) is slightly more involved (see the attached Maple file). We obtain a Gröbner Basis gb H = {h 1 , . . . , h t } for the ideal H w.r.t. the ordering with X lex Y lex Z, and compute the normal form of the minors p i ∈ K with respect to it. Note that we now consider polynomials in the ring Q(η)[X, Y, Z] of polynomials in X, Y and Z alone. This time, the residues are polynomials in X, Y and Z with coefficients that depend on the parameters:

p i h 1 ,...,h t = f i = 0 ∈ Q(η)[X, Y, Z], i = 1, . . . , 6. (41)
Since the residues f i do not vanish, unlike (34), V(H) ⊆ V(K). It implies that any common solution of the system

h 1 = • • • = h t = 0 is not a solution of the system p 1 = • • • = p 6 = 0.
However, the analysis of V(H) ∩ V(K) can be simplified by noting that V(K) contains the four observed lines and their two transversals. This is because the matrix ξ 1234 lm in (26) loses rank if C lies on the observed four lines or their transversals. As a consequence, V(H) ∩ V(K) might contain points on the four observed lines and their two transversals. As we know from Section 4.3 that they are the singularity loci corresponding to V(G), we would like to remove them from the variety V(H) ∩ V(K). We know that these six lines must lie in the union of four hyperboloids 31). Therefore, we can remove each hyperboloid from V(H) ∩ V(K) to obtain the remaining singularities. In algebraic geometry terms, removing one variety from the other amounts to finding the difference of the varieties [START_REF] Cox | Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra[END_REF].

V(G 123 ) ∪ V(G 124 ) ∪ V(G 134 ) ∪ V(G 234 ) that appear in (
The set difference of two affine varieties is generally not an affine variety but an open subset of a variety. It cannot be written as the set of solutions of a system of polynomial equations (it is not an affine variety). The smallest affine variety which contains it, is called the Zariski closure of the difference, denoted with an overline. Loosely speaking, taking the Zariski closure amounts to patching up the holes in the open set. Therefore, in this case, we need to find the following Zariski closure of the difference:

V(F ) = 4 i=1 (V(K) ∩ V(H)) \ V(S i ), (42)
where S i is an element of {G 123 , G 124 , G 134 , G 234 }.

Using the correspondence between ideals and varieties, an ideal defining V \ W where V and W are affine varieties is obtained as the saturation of an ideal I defining V with an ideal J defining W. It is denoted by I : J ∞ . The colon symbolizes the quotient of one ideal w.r.t. the other, and it removes factors from the polynomials in the first ideal which appear as polynomials themselves in the second ideal. The infinity symbol corresponds to considering all products of arbitrarily many polynomials in the second ideal. It can be done in a computational environment such as Maple or Singular and we obtain:

F = 4 i=1 (H ∪ K) : S ∞ i , (43)
Due to a large number of variables leading to heavy computations, we did not succeed in determining F in (43) using the above mentioned approach. Therefore, Appendix A shows an example where V(H) ∩ V(K) is analysed for some specialization of the parameters s 1 , . . . , s 6 , d 1 , . . . , d 5 .

Since we are dealing here with polynomial systems, we know that for almost all values of the parameters, the specialized systems have all the same number of complex solutions [START_REF] Cox | Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra[END_REF]. More precisely, there exists a polynomial B depending on the parameters, such that when specializing the parameters outside the zero set of B, the number of complex solutions to the system that we obtain remains invariant.

In our analysis, we have observed that when specializing the parameters to random values and removing those solutions lying on the lines, one always obtains 10 complex solutions. This indicates that for generic values of the parameters (outside this zero set of polynomial B), there are at most 10 isolated singularities in the case of P4L. Appendix A shows one such example where a random specialization of parameters yields 10 complex solutions of which 6 are real. Now that the generic case is treated, let us deal with a more specific case. Indeed, it is often the case that the observed lines in an environment are constrained with orthogonality and/or parallelism. This special case is considered in the next section and the singularities are determined with the proposed approach without specializing any parameters.

Singularities in P4L with orthogonality and parallelism

We consider three mutually orthogonal lines L 1 , L 2 and L 3 , and a fourth one L 4 with direction parallel to L 1 . The parametrization ( 14) and ( 21) cannot be used in this context since we need the lines to only intersect one of the planes x o = 0, y o = 0 or z o = 0. The object frame F o : (O, x o , y o , z o ) is fixed relative to the four lines, with its axes defining an orthonormal, right-handed basis, and such that x o is collinear to L 1 and L 4 ; y o is collinear to L 2 , and z o is collinear to L 3 . With this parametrization in the object frame, the direction vector u i of the four lines and the coordinates of points P i belonging to each of them are given by:

---→ OP 1 = [0, 0, 0] T , u 1 = [1, 0, 0] T , ---→ OP 2 = [0, 0, d 1 ] T , u 2 = [0, 1, 0] T , ---→ OP 3 = [d 2 , d 3 , 0] T , u 3 = [0, 0, 1] T , ---→ OP 4 = [0, d 4 , d 5 ] T , u 4 = [1, 0, 0] T . ( 44
)
Following the analysis done in the preceding section, the varieties V(G) and V(H) ∩ V(K) will be analyzed separately.

In this context, the ideal G in ( 31) is calculated as follows:

G = XY(d 1 -d 5 ) -XZ(d 3 -d 4 ) -X(d 1 d 4 -d 3 d 5 ) + YZd 2 -Yd 1 d 2 -Zd 2 d 4 + d 1 d 2 d 4 , (-d 3 + Y) (Yd 5 -Zd 4 ) , -(-d 1 + Z) (Yd 5 -Zd 4 ) , XYd 1 -XZd 3 + YZd 2 -Yd 1 d 2 . ( 45
)
According to Theorem 1, we expect the positive dimensional singularities corresponding to V(G) to be the transversals that intersect the four observed lines. It can be verified by finding the Gröbner basis gb G of G w.r.t. Z lex Y lex X.

It consists of four elements {g 1 , g 2 , g 3 , g 4 }, where the first element factors as follows:

g 1 = (Z -d 1 ) (Yd 5 -Zd 4 ) . (46)
By substituting the factors into the other elements of gb G , G v can be decomposed into two sub-ideals M and N whose varieties correspond to the two transversal lines intersecting all the four observed lines:

G = M ∩ N, where M = Z -d 1 , Y -d 3 , N = Yd 5 -Zd 4 , X(d 1 d 4 -d 3 d 5 ) + Yd 2 d 5 -d 1 d 2 d 4 . ( 47
)
In the generic case of P4L, we showed that the one dimensional singularities can be avoided by choosing the lines such that they satisfy (39). It is a condition on the discriminant of the quadratic polynomial that appears as the first element of the Gröbner basis of G. Similarly, here, the first polynomial of gb G in ( 46) is quadratic in Z and its discriminant is (Yd 5d 1 d 4 ) 2 , which is always positive. Hence the two transversal lines given by ( 47) are always real and the singularity cannot be avoided when the four observed lines adhere to the orthogonality and parallelism conditions of this section.

L 1 L 2 L 4 L M L N x o y o z o C 1 C 2 C 3 C 4 L 3
Fig. 4: Singularities in P4L with orthogonality and parallelism constraints: Four observed lines L i , i = 1, 2, 3, 4 and their traversals L M and L N .

To analyse the remaining singularities, we need to determine the variety V(H) ∩ V(K). To do so, the ideal H, K is considered (it is too large to be displayed here) and its Gröbner basis calculated:

gb HK = {Z (-d 5 + Z) (Zd 4 -d 3 d 5 ) (-d 1 + Z) , Yd 5 -Zd 4 , -d 1 d 2 d 4 (d 1 d 4 + d 3 d 5 -2 d 4 d 5 ) (d 1 d 4 -d 3 d 5 ) +(d 1 d 4 +d 3 d 5 -2 d 4 d 5 ) (d 1 d 4 +d 3 d 5 ) (d 1 d 4 -d 3 d 5 ) X -d 2 d 4 d 1 2 d 4 2 -2 d 1 d 3 d 4 d 5 -2 d 1 d 4 2 d 5 + d 3 2 d 5 2 -2 d 3 d 4 d 5 2 Z + 4 d 2 d 4 3 Z 3 -2 d 2 d 4 2 (d 1 d 4 + d 3 d 5 + 2 d 4 d 5 ) Z 2 }. ( 48
)
The variety of gb HK is zero dimensional with degree 4 (see the attached Maple file). It implies that it is made up of 4 points in C[X, Y, Z] as shown in Fig. 4 whose coordinates are as follows:

C 1 = 0, d 1 d 4 d 5 , d 1 ; C 2 = (d 1 -d 5 )d 2 d 4 d 1 d 4 + d 3 d 5 -2d 4 d 5 , d 4 , d 5 ; C 3 = d 1 d 2 d 4 d 1 d 4 + d 3 d 5 , 0, 0 ; C 4 = d 2 , d 3 , d 3 d 5 d 4 . ( 49
)
As mentioned in Section 4.4, some or all of these points might lie on the four observed lines or their two singular transversals, which we know for sure belong to the singularity loci. To acknowledge that, the saturation ideal F of (43) can be determined to check if C i ∈ V(F ), because only then, C i is a singularity locus. However, the Gröbner basis of F yields {1}. By Hilbert's Nullstellensatz, when the Gröbner basis of an ideal is {1}, its generators do not have a common solution [START_REF] Cox | Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra[END_REF] and hence, V(F ) = ∅. Thus, C i ∈ V(F ) for any i = 1, 2, 3, 4 implying that these points indeed lie on the four observed lines (L 1 , L 2 , L 3 , L 4 ) or their transversals (L M , L N ) as shown in Fig. 4 for some randomly chosen parameters d 1 , .., d 5 .

Therefore, for the special case of P4L considered in this section, the only singularities are when C lies on the four observed lines or their two transversal lines.

In fact, the results in this section remain valid under any permutation of the four observed lines and hence the analysis entails singularities in the case of four lines subject to any other orthogonality and parallelism constraints.

Let us now deal with the case of five lines observed by a camera.

Singularities in P5L

Parametrization

Let us consider the first three lines defined by the parametrization ( 14) and the fourth one by ( 21). In the same vein, the fifth line is defined using its two points of intersections P 5 and N 5 with the planes y o = 0 and z o = 0, respectively:

---→ OP 5 = [d 6 , 0, d 7 ] T , ---→ ON 5 = [r 7 , r 8 , 0] T . (50)
Thus, the direction vector of the fourth line is given by u 5 = ---→ OP 5 ----→ ON 5 . After changing the variables -r 8 = s 8 and d 6r 7 = s 7 , we have

---→ OP 5 = [d 6 , 0, d 7 ] T , u 5 = [s 7 , s 8 , d 7 ] T . ( 51
)
As mentioned in Section 3.1, the orientation of the camera frame F c and of the object frame F o is considered the same also for the following analysis.

Singularity analysis

From Section 2.3, we know that the rows of the interaction matrix M (5) associated with the five lines represent a system of Plücker lines and that a basis for this system of lines can be expressed as ξ (5) = [ξ T 11 ξ T 12 . . . ξ T 51 ξ T 52 ] T ∈ R 10×6 with ξ i1 and ξ given by (10).

Let us then consider the ideal I 210 generated by the maximal minors of ξ (5) , which in this case forms a system of 210 polynomials p i in the variables X, Y, Z and the parameters η = {s 1 , . . . , s 8 , d 1 , . . . , d 7 }: I 210 = p 1 , . . . , p 210 .

Following a similar analysis of Section 4, the 210 minors can be divided three categories. 55 of them are zero since there are 55 submatrices containing four or five ideal lines. These matrices always have a rank at most 5 since only three ideal lines can be independent.

The second category are the determinants of block triangular matrices, composed of row vectors that represent three affine lines and three ideal lines. There are 5 3 × 5 3 = 100 of them. Let these minors generate a subideal I 100 ⊆ I 210 . The generators of I 100 are of the form p i = G i jk H lmn , that are the products of the polynomials in ( 27), with the indices {i, j, k} and {l, m, n} ranging all triplets of numbers in {1, 2, 3, 4, 5}. Therefore, this ideal is the product of two smaller ideals: I 100 = G × H, generated by 10 polynomials each:

G = G 123 , . . . , G 235 , H = H 123 , . . . , H 235 . ( 52
)
The generators of G and H are too long to be given here but G (resp. H) is generated by polynomials of degree 2 (resp. 3) in Q[X, Y, Z] since its variety corresponds to the singular hyperboloids (resp. cubic surfaces) of P3L (see Section 3.2).

The remaining 55 minors with degree 5 each in {X, Y, Z} constitute the last category. Let them generate a subideal K 55 ⊆ I 210 .

As before, we deduce that the solution set of the polynomials in I 210 is contained in a larger variety which is the union of two varieties (see ( 33)):

V(I 210 ) = (V(G) ∩ V(K 55 )) ∪ (V(H) ∩ V(K 55 )) . (53)
Our strategy will be to use the geometrical interpretation of previous sections wherever possible or else to use Gröbner Bases computations and multivariate polynomial division to analyse the varieties (V(G) ∩ V(K 55 )) and (V(H) ∩ V(K 55 )) separately. Again, all mathematical derivations can be followed on the attached Maple file.

Analysis of the variety (V(G) ∩ V(K 55 ))

Let gb G = g 1 , . . . , g s be a Gröbner Basis for the ideal G with respect to the aforementioned lexicographical monomial ordering. We are again treating the parameters η = {d 1 , . . . , d 7 , s 1 , . . . , s 8 } as variables here; that is, we are considering the polynomials in the ring Q[X, Y, Z, η]. Then, we can compute the normal form of the polynomials p i ∈ K 55 with respect to this basis to find p i g 1 ,...,g s for all i. We find p i = 0 for any i, implying that (V(G) ∩ V(K 55 )) = V(G). We already know from Theorem 1 that V(G) should be a line that intersects the five observed lines. We cannot always find a line that intersects the given five lines unless they belong to a singular linear line complex (Pottmann and Wallner, 2001). Thus, there must be a condition on the parameters such that V(G) = ∅. To find it, we consider a matrix with rows consisting of the Plücker coordinates of the observed lines [u i , --→ OP i × u i ] whose moment vectors are defined by considering the point Q in (10) as the origin of the object frame O:

L 5 =                                1 0 0 0 0 0 s 1 s 2 0 d 1 s 2 -d 1 s 1 0 d 2 s 3 s 4 -s 4 d 3 s 4 d 2 d 2 d 3 -d 2 s 3 s 5 d 4 s 6 d 4 d 5 -d 4 s 6 -s 5 d 5 s 5 d 4 s 7 s 8 d 7 s 8 d 7 d 6 d 7 -d 7 s 7 -s 8 d 6                                . (54)
A line intersects the observed five lines only if the kernel k =

[k 1 , k 2 , k 3 , k 4 , k 5 , k 6 ] T of the matrix L 5 satisifies the Plücker relation k 1 k 4 + k 2 k 5 + k 3 k 6 = 0.
The first row of L 5 imposes k 1 = 0. Eliminating k i from the remaining four equations L 5 k = 0 and the Plücker relation leads to a polynomial h of degree 13 solely in terms of parameters η (see the attached Maple file).

It implies that there are no one dimensional singularities for P5L when the four observed lines are generic. Some conditions on the relative configurations of the lines must be satisfied for a transversal to exist so that the incidence of the camera center C on it makes it the singularity locus.

The results of this section are substantiated through an example in Appendix B.

Analysis of the variety

V(H) ∩ V(K 55 )
Due to the complexity of equations, it was not possible to compute a Gröbner Basis gb H = {h 1 , . . . , h t } for the ideal generated by H in Q(η)[X, Y, Z]. Thus, the normal forms of the minors p i ∈ K 55 , p i h 1 ,...,h 3 = f i with respect to the basis gb H could not be calculated. Hence, V(H) ∩ V(K 55 ) is analysed in Appendix B for some arbitrarily chosen parameters η. As in the end of Section 4, this indicates that there exists, in the space of parameters, the zero set of some polynomial, depending on the parameters, such that, specializing the parameters outside this zero set yields no isolated singularity as substantiated by an example in Appendix A. Like P4L, it applies to P5L as well that, often, the observed lines in an environment are constrained with orthogonality and/or parallelism. One of these special cases is considered in the next section and the singularities are determined with the proposed approach without specializing any parameters.

Singularities in P5L with orthogonality and parallelism

As a continuation of Section 4.5, let us consider a fifth line L 5 , which is assumed to be collinear with axis y o . This way, we have three orthogonal lines L 1 , L 2 and L 3 , a line L 4 parallel to L 1 , and a line L 5 parallel to L 2 . The location of lines L 1 to L 4 relative to frame F o is still given by ( 44), and we parametrize L 5 by

# » OP 5 = [d 6 , 0, d 7 ] T , u 5 = [0, 1, 0] T . ( 55
)
As before, if the line L 5 was instead given parallel to line L 3 , these parametrization will still be valid upon a redefinition of the object frame F o and the renaming of the lines. Following the analysis done in the preceding section, the varieties V(G) and V(H)∩V(K 55 ) will be analysed separately.

In this context, the ideal G in ( 52) is calculated as follows:

G = -XYd 5 + XYd 7 -XZd 3 + XZd 4 + Xd 3 d 5 -Xd 4 d 7 + YZd 2 -YZd 6 -Yd 2 d 7 + Yd 5 d 6 -Zd 2 d 4 + Zd 3 d 6 + d 2 d 4 d 7 -d 3 d 5 d 6 , (-d 5 + Z) (Xd 1 -Xd 7 + Zd 6 -d 1 d 6 ) , -(-d 2 + X) (Xd 1 -Xd 7 + Zd 6 -d 1 d 6 ) , XYd 1 -XYd 5 -XZd 3 + XZd 4 -Xd 1 d 4 + Xd 3 d 5 + YZd 2 -Yd 1 d 2 -Zd 2 d 4 +d 1 d 2 d 4 , (-d 7 +Z) (Yd 5 -Zd 4 ) , -XYd 7 + XZd 3 -YZd 2 + YZd 6 + Yd 2 d 7 -Zd 3 d 6 , (-d 3 + Y) (Yd 5 -Zd 4 ) , -Z (Xd 1 -Xd 7 + Zd 6 -d 1 d 6 ) , -(-d 1 +Z) (Yd 5 -Zd 4 ) , XYd 1 -XZd 3 +YZd 2 -Yd 1 d 2 . ( 56
)
We expect that the one dimensional singularity corresponding to V(G) must be the transversal that intersects the five observed lines according to Theorem 1. However, we know from Section 5.3 that the parameters used to define the five observed lines must satisfy a condition for this transversal line to exist. As before, we can determine it by imposing the Plücker relation on the kernel of the matrix whose rows are the Plücker coordinates of the observed lines [u i , --→ OP i × u i ] parametrized by ( 44) and ( 55). This condition leads to the following polynomial in terms of the parameters that should be zero.

h(η) = d 5 (d 1 -d 7 ) (d 1 d 2 d 4 -d 1 d 4 d 6 -d 2 d 4 d 7 + d 3 d 5 d 6 ) . ( 57
)
This polynomial can also be derived by finding the Gröbner basis gb G of G in (56) w.r.t. the ordering Z lex Y lex X lex d 1 lex . . . lex d 7 . It consists of ten elements of which the first element is exactly h(η). We look for conditions when

h = 0 so that V(G v ) = ∅.
When the first factor of h vanishes, i.e. d 5 = 0, we get the line as the variety of the following ideal:

M 1 = Z, X -d 2 . ( 58
)
When d 1d 7 = 0, we get

M 2 = Z -d 1 , Y -d 3 . ( 59
)
Finally, when the third factor of h vanishes, we have

M 3 = Yd 5 -Zd 4 , X(d 1 -d 7 ) + Zd 6 -d 1 d 6 . ( 60
)
Figure 5 shows the third case where a line V(M 3 ) intersects all five observed lines.

To analyse the remaining singularities, we need to determine V(H) ∩ V(K 55 ). It amounts to analysing the ideal H, K 55 (too large to be displayed here). Its Gröbner basis yields {1} implying that the variety is null and hence there are no isolated singularities in the generic case. However, it is possible that there are special relative configurations of the five lines for which

V(H) ∩ V(K 55 ) = ∅. As mentioned L 1 L 2 L 4 L M x o y o z o L 3 L 5
Fig. 5: Singularities in P5L with orthogonality and parallelism constraints: Five observed lines L i , i = 1, 2, 3, 4, 5 and their traversal L M . in Section 5.4, it was not possible to find these configurations of the observed lines when they are generic, due to the computational complexity. Nonetheless, in this context, the constraints on the observed lines reduce the complexity and hence we are able to find the conditions on the parameters d i , i = 1, . . . , 7 such that V(H) ∩ V(K 55 ) = ∅. To do so, V(H) is first calculated by finding the Gröbner basis gb H of H w.r.t. the monomial order Z lex Y lex X. It contains 3 elements and is of dimension 0. So, its variety is a point:

X = d 1 d 2 d 4 + d 1 d 4 d 6 -d 2 d 4 d 7 -d 3 d 5 d 6 2 (d 1 -d 7 ) d 4 , Y = - d 1 d 2 d 4 -d 1 d 4 d 6 -d 2 d 4 d 7 -d 3 d 5 d 6 2d 5 d 6 , Z = - d 1 d 2 d 4 -d 1 d 4 d 6 -d 2 d 4 d 7 -d 3 d 5 d 6 2d 4 d 6 . ( 61
)
For this point to be a singularity, it should also belong to the variety V(H) ∩ V(K 55 ) and hence it should absolutely lie in the variety V(K 55 ). Substituting the values of X, Y, Z in K 55 leaves 36 non-zero polynomials solely in terms of parameters d 1 , . . . , d 7 (see the Maple file). They constitute the conditions for V(H) ∩ V(K 55 ) = ∅.

Therefore, for the special case of P5L considered in this section, generically, there are no singularities. The singularities appear as a line and/or as a point for some special relative configurations of the five lines.

Again, the results in this section remain valid under any permutation of the five observed lines and hence the analysis entails singularities in the case of five lines subject to any other orthogonality and parallelism constraints. All cases corresponding to the singular configurations when observing three, four and five lines are summarized in Table 1.

Simulation results

This section illustrates the impact that the exposed singularities have on the behavior of basic image-based visual servoing and pose determination algorithms.

From the results of Sections 4 and 5, we designed a series of experiments where a free-flying camera is simulated and controlled in visual servoing from the observation of lines. Another set of tests show the result of classical algorithms for pose estimation from lines when the camera is controlled in open-loop (the camera motion is specified beforehand). All the simulations were performed using the visual servoing library ViSP [START_REF] Marchand | Visp for visual servoing: a generic software platform with a wide class of robot control skills[END_REF].

Singularities in P4L

Let us consider four lines defined by a point and a direction ( 14), and let us specialize the parameters arbitrarily as follows:

s 1 = 4, s 2 = -5, s 3 = 7, s 4 = 3, s 5 = -2, s 6 = 13, d 1 = 2, d 2 = 3, d 3 = 5, d 4 = 1, d 5 = 7. ( 62
)
For this configuration, as shown in Section 4.3, the four lines are in a hyperbolic congruence (see Fig. 3) and there exist two lines L M and L N transversal to L 1 , . . . , L 4 , which have the following Plücker coordinates:

L M = [0.0830 0.4989 -0.8627 0 -0.9641 -0.5575]; L N = [0.2067 -0.03902 -0.9776 0 -0.3509 0.01401]. (63)
The singularity loci of the interaction matrix consists of the two lines L M , L N plus 6 isolated points which belong in the variety V(H, K) (see Section 6.1.3).

VS towards a desired pose near singularity line L M

We selected four initial camera positions in the proximity of a point P M = [0.3962 m -4.337 m 7.50 m] that lies on the singularity line L M . From each starting point, we attempt to control the camera towards a desired position which is always the same. The coordinates of the start and target positions are 2 along with a commentary on the choice of points. The camera orientations were chosen such that the four lines are clearly visible from all locations. At each iteration, the controller tries to minimize an error function s(t)s * . The vector of features s = [l T 1 , . . . , l T 4 ] T ∈ R 12 is composed of the coordinates l xi , l yi and l zi for each projected line 1 ≤ i ≤ 4, while s * contains the values of the features at the desired position. In order to achieve an exponential decrease of the error, the velocity input to the camera is

τ c = -λ M + (4) (s(t) -s * ) , (64)
where M + (4) is the Moore-Penrose pseudoinverse of the interaction matrix (3) and λ is a gain factor which was set to 0.1. For these first simulations, we assume that all the parameters appearing in the matrix M (4) are known and hence we can always obtain a perfect estimate of its pseudoinverse M + (4) . Note that no noise was added to the visual data, and hence all the instabilities are due uniquely to the determinant of the interaction matrix vanishing at a singularity.

Figure 6 displays the camera trajectories starting from each initial position. A normal behaviour is achieved from Starts 1 and 3: the camera describes an almost straight line towards the desired pose, and the magnitude of the error vector decreases exponentially (see Fig. 7).

Table 2: Initial and desired positions relative to a point on the singularity line L M (all units are in meters). Start 2 is located opposite from the desired position relative to the point P M . The camera reaches the target point eventually, but it diverges along the singularity line as it approaches it (see Fig. 6). The inverse of the condition number κ of M (4) , shown in Fig. 7, reaches almost zero in the vicinity of the singularity, which means that the system in ( 64) is illconditioned and, as a result, the controller produces very high velocity commands causing instability. Figure 8 compares the velocity input profiles for Starts 1 and 2 throughout the simulation. The velocity inputs from Start 2 are two orders of magnitude higher than those produced in a stable situation. Note that although the distance to the desired point increases during the undesirable motion (Fig. 9), the magnitude of the error ||ss * || remains approximately constant (Fig. 7).

Start 4 is located slightly further away from the singularity line, and closer to the desired position. The trajectory converges but the camera is again subjected to considerably high velocities and does not approach the target monotonically (see Figs. 6 and9). This illustrates that the impact of the singularities is not limited to the trajectories that directly cross a singular point, but instead, that there is an area of influence in the vicinity of a singularity where the behaviour can be affected by the high condition number of the interaction matrix.

Trajectory following across singularity line L N

With the same four lines defined by the parameters (62), a simple trajectory along a cubic curve defined by r *

1 (t) = [X * 1 (t), Y * 1 (t), Z * 1 (t)] T with X * 1 (t) = -s(t) 3 -1.7551 m, Y * 1 (t) = s(t) + 0.3992 m Z * 1 (t) = 0.7s(t) + 10.0 m. ( 65
)
for s(t) = 0.04t -1 and 0 ≤ t ≤ 50 s, was designed to cross the singularity line

L N at s(t) = 0. A second, very similar trajectory r * 2 (t) = [X * 2 (t), Y * 2 (t), Z * 2 (t)] T with X * 2 (t) = -s(t) 3 -3.2551 m, Y * 2 (t) = s(t) + 0.3992 m Z * 2 (t) = 0.7s(t) + 10.30 m. ( 66
)
should not cross any singular points.

Trajectory following can be performed using visual servoing by introducing a time-dependent vector s * (t) of desired visual features in the control law (64), which can be computed by forward projection (1) of the 3D line coordinates in Fig. 10: VS from four image lines: Trajectory described by the camera when controlling it along a prescribed path (thin dotted line). The control becomes unstable along the trajectory that crosses the singularity line L N (black dashed line).

the camera frame F c as the camera moves along the trajectory.

As before, we assume that the parameters in the interaction matrix M (4) can be measured such that we can obtain an estimate of its pseudoinverse M + (4) to use in the control law (64). However this time we added white Gaussian noise of standard deviation σ = 2 • 10 -3 to the 3D coordinates of the observed lines, in order to simulate the impact of errors in the measurements. The gain factor λ was set to 1.

The camera behaviour is shown in Fig. 10. For trajectory r * 2 (66), away from the singularity line, the camera follows the prescribed path with relative accuracy. The velocity inputs are mild and there is a small, approximately constant tracking error of about 0.1 m (Fig. 11), which could be reduced with a more sophisticated controller, for example by introducing an integral term in the control law (64).

For the trajectory r * 1 (65), the camera is unable to follow the desired path accurately in the vicinity of the singularity line. Around s(t) = 0, the velocity commands become very high in magnitude, inducing instability, and the translation error becomes as high as 1 m (Fig. 11).

VS around the isolated point singularities

For the configuration (62), there also exist 6 isolated points P i which are zero-dimensional singularities of the interaction matrix. They are those solutions of the ideal H, K which are not contained in the variety V(G) = L M ∪ L N (see Ap-

Another point P 0 is chosen arbitrarily and away from any singularities:

Ex. 0 :

P 0 = [-8.858 -2.473 -1.841]. ( 68
)
For each of these locations, we simulated a trajectory with the shape of a quadrifolium centered at P i , given by the following equations:

X * (t) = P ix , Y * (t) = P iy + 0.3 cos(s) cos(2s), Z * (t) = P iz + 0.3 sin(s) cos(2s). ( 69
)
where P ix , P iy , P iz are the coordinates of each point, and s = 2π t/20 with 0 ≤ t ≤ 20 s, and we applied the control law (64) with λ = 5. Once again, Gaussian noise of standard deviation σ = 10 -3 was added to the Plücker coordinates of the lines to simulate measurement errors. In Fig. 12 we show the results for the trajectory centered at the first of these points. The translation error along this trajectory is compared in Fig. 13 with that of Ex. 0, which does not come near a singularity. An oscillating tracking error is present in both cases due to the delay of the camera position relative to the desired point at a given time. However the presence of the singularity in Ex. 1 results in destabilizing velocity commands as the camera approaches the center of the quadrifolium (for s = π 4 + n π 2 ), as shown in Fig. 13. As a consequence, a significantly larger deviation occurs around this point.

The maximum translation errors for all the experiments (67), displayed in Fig. 14, occur always when the camera approaches the singularity point. Meanwhile the difference between the maximum and median errors indicate that the greatest part of the trajectory is completed with relative accuracy.

A particularly large error occurs in Ex. 2. In this case, the point of singularity P 2 is located very near both the singularity line L M (see Section 6.1.1) and one of the observed lines L 2 (we recall that the camera is at a singularity when it lies on L i because it loses visibility of the line). When the camera approaches point P 2 , it diverges and is pulled towards the unstable regions around L 2 and L M , resulting in a very large translation error.

Pose Estimation along a quadrifolium trajectory

This section illustrates the impact that the singularities have when performing pose estimation in their neighbourhood. Typically, pose computation algorithms can be classified in iterative and non-iterative methods. Iterative methods are usually more efficient and accurate than the non-iterative ones but, in contrast to them, they require the estimated pose to be initialized and their convergence is very sensitive to a bad initialization.

For the following results we used our own implementation of the classical Robust PnL (RPnL) [START_REF] Zhang | Robust and efficient pose estimation from line correspondences[END_REF]), that combines several classical methods for the solution P3L [START_REF] Wang | Camera pose estimation from lines: a fast, robust and general method[END_REF]), as well as improved version, the Accurate Subset-based PnL (ASPnL) [START_REF] Xu | Pose estimation from line correspondences: A complete analysis and a series of solutions[END_REF]), regarded as one of the state-of-the-art non-iterative solvers for pose estimation from n lines, and which is available as open-source code. Both RPnL and ASPnL solve the P3L problem for (n -2) different triplets of lines and then select the solution that yields the smallest reprojection error.

The previous methods are best suited for small set lines with no outliers (they assume there are no feature mismatches). We consider here n = 4, the minimal number of lines for which the pose estimation problem has a unique solution, in order to test the behaviour of pose estimation in the vicinity of the exposed singularities. The pose computed from the direct methods (RPnL and ASPnL) can be used as an initial estimate to be refined using a first-order iterative solver.

Here we use Virtual Visual Servoing (VVS) [START_REF] Marchand | Virtual visual servoing: A framework for real-time augmented reality[END_REF]), which minimizes the reprojection error of the lines by performing visual servoing on a virtual camera such that the desired image matches the image recorded by the real camera.

We consider four lines in the same configuration used in Section 6.1, defined by a point and a direction ( 14) and with the parameters fixed as in (62). Three experiments were performed, based on the three points whose coordinates are shown in Table 3. Centered at each of these, we simulated an open-loop trajectory, defined thereafter, along which the pose computation methods were assessed. For Ex. 1 a generic point far from any singularities was chosen as a benchmark for the efficiency of the pose estimation algorithms. Ex. 2 corresponds to the point singularity P 1 in (67) -we demonstrate here only the behaviour of pose estimation near one of the points in (67) because in practice the results are very similar around the other five isolated singularities. Finally, the point for Ex. 3 lies on the singularity line L M .

In all three cases the prescribed trajectory has the shape of a quadrifolium or four-leaved clover, defined by (69) -for Ex. 2, the pattern is rotated by 90 degrees around the Y axis, such that the "leaves" of the quadrifolium do not lie too close to the line L M . A constant camera orientation was chosen such that there is good visibility of the lines at all times (with the focal axis roughly pointing towards the origin).

Since the pose computation methods should be very sensitive to numerical noise in the proximity of a singularity, we added Gaussian noise with standard deviation σ = 10 -4 to the Plücker coordinates of the 3D lines.

Two parameters are measured from the simulations: the translation error t e , defined as the Euclidean distance between the true and estimated camera positions, and the rotation error: the absolute value of the error angle Fig. 15: Pose estimation from four image lines along a trajectory with the shape of a quadrifolium centered at different points: a generic point away from singularities (left), an isolated point singularity (center) and a point on a line singularity (right). The top images show the true camera position (red), the estimation from the non-iterative RPnL (blue) and ASPnL (green), and the refinement by VVS when initialized from the ASPnL estimate (yellow). In the bottom are displayed the translation error and the absolute error angle (70). The vertical steps indicate the points where the camera passes through the singularity. Far away from any singularities all three methods have a near-zero error; only the yellow plot is visible in the left image because the three trajectories overlap. In a large area around a point of singularity, the direct methods become very sensitive to noise in the data, while VVS is quite effective in refining the result from ASPnL except when very near the singularity. In the near proximity of the line singularity, all methods output an abhorrent estimation, with the errors tending to infinity.

θ e = arccos 1 2 tr c R o c R o ) T -1 , (70)
The results from RPnL and ASPnL as the camera moves along each of the trajectories are depicted in Fig. 15; along with the refinement by VVS when initialized from ASPnL. The corresponding error metrics are displayed below. Away from the singularities, all three methods yield near perfect estimations for both position and orientation (see Fig. 15a).

In the second experiment (Fig. 15b), centered at an isolated singularity, the direct methods become very inaccurate. A large translation error reaching up to 10 cm occurs particularly as the camera crosses the singularity at the center of the pattern, but also in the vertical direction of the clover. This is explained by the fact that both RPnL and ASPnL solve the P3L problem for two triplets of lines (in this case L 1 , L 2 and L 3 on one hand, and L 1 , L 2 and L 4 on the other), and that for the P3L problem the singularity loci is a surface. The refinement from VVS generally allows reducing the translation error to below 0.1 mm, except very near the singular point, where a persistent error of about 3 cm remains.

In Ex. 3, the direct methods and VVS all fail catastrophically to give an acceptable estimation near the singularity (see Fig. 15c). As the camera approaches the line L M , the translation error blows up by several orders of magnitude (∼ 10 27 m). Since the RPnL and ASPnL algorithms compute several local minima and then select the best solution based on the reprojection error, we verified that the true solution does not lie among the local minima that were discarded. It seems that the ill-conditioning of the interaction matrix causes numerical issues in the direct solvers such that they are incapable of locating where along this line the true solution lies.

These results show that a rank-deficiency of the interaction matrix can significantly impact the accuracy of pose computation, even in the case of direct solvers such as RPnL and ASPnL which do not explicitly involve the interaction matrix.

Singularities in P5L

We now consider the case of five lines determined by the following parameters: From the results in Section 4.3, we know that a singularity will occur when the camera lies on this line. Note that the lines L 1 , . . . , L 4 are defined identically as in Section 6.1, and that L 5 is chosen so as to intersect the first of the lines of singularity (63).

s 1 = 4, s 2 = -5, s 3 = 7, s 4 = 3, s 5 = -2, s 6 = 13, s 7 = -11, s 8 = 6, d 1 = 2, d 2 = 3, d 3 = 5, d 4 = 1, d 5 = 7, d 6 = -4, d 7 = 128893236

VS near the singularity line

We considered a point P M = [0.3962 m -4.337 m 7.50 m] that lies on the transversal L M and defined four starting camera positions in its surroundings. From each of these points, we performed a simulation of visual servoing towards a target point. The initial and desired positions are the same as those considered in Section 6.1.1, whose coordinates relative to point P M are given in Table 2. The camera velocity inputs are computed according to (64) with the factor λ = 0.1. Gaussian noise of standard deviation σ = 2 • 10 -3 was added to the 3D coordinates of the lines.

In all four experiments, the magnitude of the error vector decreases exponentially (Fig. 18). However, the trajectories displayed in Fig. 16 show very different behaviours. Starts 1 and 3 converge rapidly, with small camera velocities and displacements.

On the contrary, Starts 2 (directly opposed to desired point) and 4 (further away from the singularity), lead to unstable motion and large deviations. The velocity input profiles for Starts 1 (stable) and 2 (unstable) are compared in Fig. 17. In the latter, the inputs become very high in magnitude as the inverse of the condition number of the interaction matrix drops near zero, when the camera crosses L M . Again we notice that there exists a region of instability around the singularity line, particularly strong in one direction which affects the trajectory of Start 4, where the interaction matrix becomes ill-conditioned.

Pose Estimation near the singularity line

For completeness, we conclude by demonstrating the behaviour of pose estimation from the observation of five lines near a singularity. We simulated a trajectory along a pattern with the shape of a quadrifolium (with equations (69)) centered at a point with coordinates [0.7809 m -2.024 m 3.50 m], which lies on the singularity line L M . Along this trajectory, the camera pose was computed using the RPnL [START_REF] Zhang | Robust and efficient pose estimation from line correspondences[END_REF]) and ASPnL [START_REF] Xu | Pose estimation from line correspondences: A complete analysis and a series of solutions[END_REF]) algorithms and the estimation was further refined using VVS [START_REF] Marchand | Virtual visual servoing: A framework for real-time augmented reality[END_REF]) initialized at the pose computed by ASPnL. We considered Gaussian noise of standard deviation σ = 10 -4 on the 3D coordinates of the observed lines.

The true pose is shown along with the estimations from the three methods in Fig. 19, while the translation error t e and the rotation error θ e defined by (70), are depicted in Fig. 20. The observed behaviour is very similar to the case of four lines when pose reconstruction is performed the singularity line: the leaves of the quadrifolium, the direct solvers (RPnL and ASPnL) are quite sensitive to numerical noise, which is mitigated by the refinement through VVS. However, very near the singularity the errors blow up in magnitude and all methods prove totally unsuccessful. For comparison, along a similar trajectory, but centered at coordinates [0.5 m 4.0 m 1.0 m], far from any singularities, all methods are accurate up to 0.1 mm in the estimation of position and up to 2 • 10 -3 rad in orientation throughout.

Conclusions

In this paper, the singularities in the perspective four and five line problems were determined. Finding these singularities is crucial since they lead to controllability issues in visual servoing of image-lines and in large errors in pose estimation for PnL. To do so, a basis of the interaction matrix was found such that its rows are Plücker coordinates of n affine and n ideal lines for PnL.

First, it was recalled that the singularities in P3L are due to the vanishing of the determinant of the (6 × 6) interaction matrix which factors as a quadric and a cubic surface in terms of the position coordinates of the optical center of the camera. It was then proved that the quadric surface is essentially the hyperboloid of one sheet uniquely defined by the three observed lines.

This fact was further used in the case of P4L to understand different cases such that the 28 principal minors of the (8 × 6) interaction matrix vanish simultaneously, leading to singularities. One of those cases is when the camera lies on two transversals intersecting the observed four lines. It was also shown that this one dimensional singularity could be avoided by choosing the fourth line to not intersect the hyperboloid defined by the other three lines. Additionally, Gröbner basis computations were used to expect up to ten real isolated singularities of P4L.

Furthermore, in the case of P5L, no singularities were found for a generic choice of five lines. Nonetheless, some conditions of the relative configurations of the five lines were shown to yield a transversal line of singularities that intersects the five observed lines.

The same analysis was done for four and five lines that are constrained to be orthogonal or parallel to each other to corroborate the results for the generic case. It turned out that the singularities for P4L consist of two transversal lines, whereas for P5L, it is a unique transversal line.

The results are supported with experimental simulations of Visual Servoing control of a camera and of pose determinations algorithms from the observation of lines in the proximity of the singularities. As expected, the ill-conditioning of the interaction matrix near a singular point results in unstable behaviour of the control law from VS and in significant losses of accuracy for the pose estimation methods.

The geometric interpretation of the one dimensional singularities of P4L and P5L was provided, by extending the result that a hyperboloid of one sheet is a singularity in the P3L case. These one dimensional singularities appeared when the affine lines in the interaction matrix are linearly dependent by being parallel to the same plane. In the future, we will try to obtain the isolated singularities in PnL for four and five generic lines along with their geometric interpretation.

Appendices

A. Analysis of varieties V(G) and V(H) ∩ V(K) in P4L for an example.

The singularities in P4L are determined for lines whose Plücker coordinates are arbitrarily chosen according to the following parameters: The Gröbner basis gb G of G w.r.t. Z lex Y lex X consists of four elements {g 1 , g 2 , g 3 , g 4 }. The first element factors (using the command evala(AFactor) in Maple) as follows: Following Section 4.3, it is straightforward to verify that p i g1,...,g4 = 0 ∀ p i ∈ K. So, the corresponding positive dimensional singularities are V(M) and V(N).

g 1 = -2166Y 2 -1166YZ + 50Z 2
The ideals H and K are determined whereas only H is displayed here since K is too large: The Gröbner basis gb H of H w.r.t. Z lex Y lex X contains 5 elements {h 1 , h 2 , h 3 , h 4 , h 5 }. As proposed in Section 4.4, the normal forms can be calculated as p i h1,...,h5 = f i . The residuals f i do not vanish. Thus, the whole variety V(H) ∩ V(K) is considered and it turns out to be of dimension 0 and degree 22 with 16 real solutions (see the attached Maple file): However, it can be verified that some of these points lie on the observed four lines or their transversals V(M) and V(N). Since any point incident with these lines leads to a singularity, we are interested in singular points that do not lie on them. They can be calculated by determining the ideal F using (43). The Gröbner basis gb F of F w.r.t. Z lex Y lex X has the following nice structure (called the shape position):

H = -73960 X 3 -46428 Y X 2 +
gb F = { f a (Z), f b (Z) + Y, f c (Z) + X},
where f a (Z) = Σ 10 i=1 a i Z i is a degree 10 univariate polynomial in Z, f b (Z) and f c (Z) are also univariate polynomials in Z. It follows that V(F ) is of degree 10. It consists of 6 real points marked with an asterisk each in Table 4. Thus, the singularity loci for this example include the four observed lines, their two transversals and 6 points.

Since the parameters were chosen randomly for this analysis, this indicates that for values of parameters, outside the zero set of some polynomial depending on the parameters (hence of measure zero), the real singular points in P4L can be up to 10. B. Analysis of varieties V(G) and V(H) ∩ V(K) in P5L for an example.

The singularities in P5L are determined for lines whose Plücker coordinates are arbitrarily chosen as follows: It is the equation of a line intersecting the five observed lines. The Gröbner basis gb H of H w.r.t. Z lex Y lex X contains 5 elements {h 1 , h 2 , h 3 , h 4 , h 5 }. As proposed in Section 5.4, the normal forms can be calculated as p i h1,...,h3 f i , i = 1, . . . , 55. The residues f i do not vanish. Therefore, he Gröbner basis of the ideal H, K 55 is calculated and it turns out to be 1 . Hence, for a generic choice of parameters, there are no singularities in P5L.

Fig. 6 :

 6 Fig. 6: Visual servoing using four image lines, starting from four initial poses (coloured). The desired end pose is in black. The black dashed line is the singularity line L M that intersects the four observed lines.

Fig. 8 :

 8 Fig.8: Velocity inputs τ c for the camera in a stable control scheme (left), and when crossing a singularity (right).

Fig. 9 :

 9 Fig. 9: Distance to the target during the visual servo.

Fig. 11 :

 11 Fig. 11: Camera velocity inputs τ c (top) and position error ||r(t)r * (t)|| (bottom) along the trajectories. The vertical step in the bottom figure indicates where Trajectory 1 crosses the singularity line L N .

Fig. 12 :Fig. 13 :

 1213 Fig.12: Visual servoing along a trajectory with the shape of a quadrifolium (red) centered at the singularity point P 1 . The true end camera position is drawn in black. A large translation error occurs every time the camera approaches the singularity.

Fig. 14 :

 14 Fig. 14: Maximum and median error along the quadrifolium trajectory for all experiments.

  where c R o and c R o T are respectively the rotation matrices representing the true and the estimated orientation of the camera frame.

  (a) Ex. 1: Away from singularities. (b) Ex. 2: Centered at an isolated singularity. (c) Ex. 3: Around the singularity line L M .

Fig. 16 :Fig. 17 :

 1617 Fig. 16: Visual servoing from five lines starting from different positions (coloured) towards a desired pose (black). The line L M (dashed line) that intersects all five lines is a singularity of the interaction matrix.

  , there is only one transversal line L M that intersects all five lines (see Appendix B), defined by its Plücker coordinates:L M = [0.0830 0.4989 -0.8627 0 -0.9641 -0.5575].(72)

Fig. 18 :

 18 Fig. 18: Inverse of the condition number κ of the interaction matrix M (4) (left) and norm of the error vector ||ss * || (right).

Fig. 19 :

 19 Fig. 19: Pose computation from RPnL, ASPnL and ASPnL refined by VVS using five image lines along a quadrifolium trajectory centered at a point on the line singularity L M . In the proximity of the singularity the error in the estimation grows unbounded.

Fig. 20 :

 20 Fig. 20: Translation (top) and rotation (bottom) errors in pose estimation from five lines along a quadrifolium trajectory. The vertical steps indicate where the camera crosses the singularity.

  s 1 = 4, 2 = -5, s 3 = 7, s 4 = 3, 5 = -2, s 6 = 13,d 1 = 2, d 2 = 3, d 3 = 5, d 4 = 1, d 5 = 7. (73)Then,G = -1765 X 2 -587 XY -878 XZ +660 Y 2 +232 YZ -122 Z 2 +2606 X + 216 Y + 598 Z -708, -177 XY -27 XZ + 75 Y 2 + 17 YZ -8 Z 2 + 156 Y + 6 Z, -130 XY + 40 XZ -104 Y 2 -62 YZ + 10 Z 2 + 188 Y -20 Z, -30 XY + 145 XZ -24 Y 2 + 11 YZ + 30 Z 2 + 210 Y -60 Z .

√

  By substituting the factors into the other elements of gb G , G can be decomposed into two subideals whose varieties correspond to the two transversal lines intersecting all the four observed lines: 448189 + 587953) + 2166 √ 448189 + 3822990X -2822298 .

  s 1 = 4, s 2 = -5, s 3 = 7, s 4 = 3, s 5 = -2, s 6 = 13, s 7 = -11, s 8 = 6, d 1 = 2, d 2 = 3, d 3 = 5, d 4 = 1, d 5 = 7, d 6 = -4, d 7 = 11. (75)The Gröbner basisgb G of G w.r.t. Z lex Y lex X is 1 . By Hilbert's Nullstellensatz, V(G) = ∅.If we choose the parameters according to (75) except d 7 , which is chosen such that the parameters satisfy h = 0 in Section 5.3:

  16 = G 123 H 123 , . . . , G 234 H 234 which is contained in the larger ideal I 28 . There are six submatrices ξ 1234 lm of the third category. Their determinants are of degree 5 in the ring Q[X, Y, Z]. Let them generate an ideal K.

The determinants of matrices ξ i jk lmn generate an ideal I

Table 1 :

 1 Different cases of singularities in P4L and P5L.

	Cases Subcases	Singularity configurations
			C lies on the hyperboloid of one
	P3L Three skew lines	sheet uniquely defined by the ob-served lines or on a cubic surface
			that contains the three lines
		Four lines in a hyper-bolic congruence	C lies on two affine lines intersect-ing the four observed lines and up to 10 real points
	P4L	Four lines in a parabolic congru-	C lies on an affine line intersecting the four observed lines and up to
		ence	10 real points
		Four lines in an ellip-tic congruence	Up to 10 real points
		With orthogonality and parallelism constraints	C lies on the two affine lines inter-secting the four observed lines
		Five lines in a regular linear line complex	No singularities
	P5L	Five lines in a singu-lar linear line com-plex	C lies on the line intersecting the five observed lines
		With orthogonality and parallelism constraints	No singularities; Special case: A line and/or a point

Table 3 :

 3 Point coordinates used for simulations of pose determination (all coordinates given in meters).

	Ex.	Coordinates Note
	1	[5.0 2.0 3.0] Away from singularities.
	2	[-9.858 -2.473 -1.841] Isolated point singularity.
	3	[0.7809 -2.024 3.50] On singularity line L M .

  320426 X 2 Z + 88867 XY 2 + 163934 Y XZ + 184389 XZ 2 + 62940 Y 3 -356381 Y 2 Z -32282 YZ 2 + 27183 Z 3 + 210018 X 2 -721747 XY -416981 XZ -146898 Y 2 -118097 YZ -116973 Z 2 + 111106 X + 377082 Y + 153504 Z -56580, -3038 Y X 2 + 3686 X 2 Z -2288 XY 2 + 16544 Y XZ + 3344 XZ 2 -315 Y 3 -4111 Y 2 Z -157 YZ 2 + 663 Z 3 + 27166 XY -4168 XZ + 2769 Y 2 -13942 YZ -1527 Z 2 -25806 Y + 690 Z, -650 Y X 2 -3350 X 2 Z -195 XY 2 + 8450 Y XZ -845 XZ 2 + 260 Y 3 + 3410 Y 2 Z + 390 YZ 2 -13390 XY + 1630 XZ + 276 Y 2 -8372 YZ + 15088 Y, 225 Y X 2 -1685 X 2 Z +705 XY 2 +450 Y XZ -345 XZ 2 +420 Y 3 -1325 Y 2 Z -645 YZ 2 -8056 XY + 705 XZ -918 Y 2 -1527 YZ + 5658 Y

	(74)

Table 4 :

 4 Elements of the variety V(H) ∩ V(K).

		X	Y	Z
	*1	-9.858 -2.473 -1.841
	2	-0.720	0.0	0.0
	*3	-0.320	0.010	0.220
	4	-0.007	0.009	2.0
	*5	0.054	0.009	1.842
	6	0.328	0.0	0.0
	7	0.918	0.141	-2.082
	*8	0.938	0.568	-2.023
	9	0.972	-1.215	2.0
	*10	1.011	0.794	-0.885
	11	1.016	0.371	-1.984
	12	1.218	0.390	-0.918
	13	3.231	0.0	0.0
	14	3.880	7.054	0.880
	*15	65.09	-96.57 -0.036
	16	90.31	-112.9	2.0

Acknowledgements This work has been partially funded by the French ANR project SESAME (funding ID: ANR-18-CE33-0011).