Keywords: particular cases, homographies, perspective, para-perspective and orthographic projections

For decades, there has been an intensive research e ort in the Computer Vision community to deal with video sequences. In this paper, we present a new method for recovering a maximum of information on displacement and projection parameters in monocular video sequences without calibration. This work follows previous studies on particular cases of displacement, scene geometry and camera analysis and focuses on the particular forms of homographic matrices.

It is already known that the number of particular cases involved in a complete study precludes an exhaustive test. To lower the algorithmic complexity, some authors propose to decompose all possible cases in a hierarchical tree data structure but these works are still in development ??.

In this paper, we propose a new way to deal with the huge number of particular cases : (i) we use simple rules in order to eliminate some redundant cases and some physically impossible cases, and (ii) we divide the cases into subsets corresponding to particular forms determined by simple rules leading to a computationally e cient discrimination method.

Finally, some experiments were performed on image sequences acquired either using a robotic system or manually in order to demonstrate that when several models are valid, the model with the fewer parameters gives the best estimation, regarding the free parameters of the problem. The experiments presented in this paper shows that even if the selected case is an approximation of reality, the method is still robust. For decades, there has been an intensive research e ort in the Computer Vision community to deal with video sequences. Researchers have been interested in recovering 3D objects structure, projection or displacement parameters from such sequences. In the general case, the acquisition device has to be considered uncalibrated (for example, in the case of an auto-focus camera). In this paper, we consider uncalibrated monocular video sequences for which we intend to recover as much information as possible on displacement and projection parameters.

The motivations for such studies are threefold: (i) to eliminate singularities of general equations, (ii) to estimate the parameters with more robustness and (iii) to retrieve parameters that cannot be retrieved in the general case.

The theory states that there exists relations between 2D projected points 9] but the system cannot be solved in the general case since there are more parameters than equations. Furthermore, these equations are degenerate or present singularities in some particular cases. However, we can solve the equations if we know or assume values or relations of some parameters.

In a previous study 25], we have shown that we increase the numerical precision of retrieved parameters by using the set of constraints that gives the smallest residual error given by a criterion (described in the cited paper).

This paper extends previous works 25, [START_REF] Lingrand | Particular forms of homography matrices[END_REF][START_REF] Lingrand | Using particular forms of fundamental matrices[END_REF] on particular displacement cases, scene geometry and camera analysis. It focuses on the particular forms of fundamental and homographic matrices.

Several authors have already been interested in particular cases of projection [START_REF] Aloimonos | Perspective approximations[END_REF][START_REF] Dementhon | Exact and approximate solutions to the three-point perspective problem[END_REF][START_REF] Horaud | Object pose: The link between weak perspective, paraperspective, and full perspective[END_REF][START_REF] Soatto | Dynamic rigid motion estimation from weak perspective[END_REF][START_REF] Quan | Self-calibration of an a ne camera from multiple views[END_REF], or displacement [START_REF] Hartley | Self-calibration from multiple views with a rotating camera[END_REF][START_REF] De Agapito | Self-calibration of a rotating camera with varying intrinsic parameters[END_REF][START_REF] Vi Ville | Autocalibration of visual sensor parameters on a robotic head[END_REF]3,[START_REF] Torr | Geometric motion segmentation and model selection[END_REF]. Some of them consider several particular cases, compare these di erent parameterizations and identify which model is consistent with the data.

We will build an exhaustive list of particular cases of projection and displacement, setting some of the parameters to constant and/or known values and using D R A F T April 23, 2001, 5:10pm D R A F T known relations between parameters. This reduces the number of unknowns in the equations and avoid also some singular cases.

It is already known that the huge number of particular cases prevents exhaustive studies 13]. Some attempts in order to reduce the algorithmic complexity are based on tree structures but they are still in development 25]. In this paper, we introduce a new method in order to deal with all cases : (i) we use simple rules in order to eliminate some redundant cases and some physically impossible cases, and

(ii) we divide the cases into subsets corresponding to particular forms determined by simple rules leading to computationally e cient discrimination method. We will provide details for each of these steps in the sections hereafter.

STEREO FRAMEWORK

In this section, we describe the equations and the formalism of displacement and projection which allows us to achieve a minimal parameterization of the relations between 2D points into two frames.

In a video sequence, we will consider frames pairwise: two consecutives frames or the rst one and the last one. This work could be easily extended to trifocal tensors.

Adding some other constraints, the framework could also be extended to sequences, assuming for examples that the translation is constant between consecutives frames, or varies with constant acceleration, ...

Rigid displacements

We will consider a rigid scene or piecewise rigid scene. A 3D-point M 1 = X 1 Y 1 Z 1 1] T is moving onto the point M 2 = X 2 Y 2 Z 2 1] T by a rotation R and a translation t = t 0 t 1 t 2 ] T : M 2 = R M 1 + t as shown in gure 1.

A rotation matrix R depends only on three parameters r = r 0 r 1 r 2 ] T The most commonly accepted hypothesis states that a 3D-point M is projected with a perspective projection onto an image plane on a 2D-point m = u v 1] T .

The perspective model : Choosing a reference frame attached to the camera, the projection equation is :

Z 0 B B B B B @ u v 1 1 C C C C C A = 0 B B B B B @ u u 0 0 0 v v 0 0 0 0 1 0 1 C C C C C A 0 B B B B B B B B @ X Y Z 1 1 C C C C C C C C A (2)
where u and v represent the horizontal and vertical lengths, u 0 and v 0 correspond to the image of the optical center and is the skew factor.

This model can be re ned, by taking optical distortions into account 21, 4, 7].

In this paper, we will consider that the needed corrections have been done as a preprocessing.

Two approximation models of the projection equation 2 have been proposed in the literature : the para-perspective and the ortho-perspective projection.

The para-perspective model : The perspective projection model is approximated to its rst order with respect to the 3D coordinates 2, [START_REF] Poelman | A paraperspective factorization method for shape and motion recovery[END_REF][START_REF] Horaud | Object pose: The link between weak perspective, paraperspective, and full perspective[END_REF]. This is equivalent to approximating the perspective projection in two steps (see gure 2) : (i) a projection parallel to the gaze direction onto an auxiliary plane P a which is parallel to the image plane and passes through the scene center M 0 = X 0 Y 0 Z 0 ] T followed by (ii) a perspective projection onto the image plane. This so called para-perspective model yields linear equations (3). However, its parameters depend on the gaze

B B B B B @ u v 1 1 C C C C C A = 0 B B B B B @ u u u 0 0 v v v 0 0 0 0 1 1 C C C C C A 0 B B B B B B B B @ X Y Z 1 1 C C C C C C C C A (3)
where :

8 > < > :

u = u X0 Y0 + Y0 Z0 v = v Y0 Z0
This equation corresponds to the most general case of para-perspective projection although more simple expressions have been proposed 18].

The orthographic model : The zero-order development with respect to the 3D depth consists in a rougher approximation. It is also equivalent to another two-step approximation: (i) an orthogonal projection onto the auxiliary plane P a followed by (ii) a perspective projection onto the image plane (see gure 3). This approxi-

0 B B B B B @ u v 1 1 C C C C C A = 0 B B B B B @ u 0 u 0 0 v 0 v 0 0 0 0 1 1 C C C C C A 0 B B B B B B B B @ X Y Z 1 1 C C C C C C C C A (4)
Those three projection models can be integrated in the following expression : orthographic projection 0 0 para-perspective projection 1 0

m = 0 B B B B B @ u u + u 0 (1 ) u 0 0 v v + v 0 (1 ) v 0 0 0 (1 ) 1 C C C C C A | {z } A M (5) with :

General equations between two frames

Let I 1 and I 2 denote two images. In the general case, there exists a fundamental relation between a point m 2 in I 2 and its corresponding m 1 in I 1 :

8 > > > > > < > > > > > : 1 m 1 = A 1 M 1 2 m 2 = A 2 M 2 M 2 = R M 1 + t =) m 1 0 B B B B B @ 0 0 0 1 C C C C C A A 1 0 B B B B B @ 0 0 0 1 C C C C C A m 2 A 2 Rkt] = 0
which is a bilinear form in m 1 and m 2 (see 12] for details). This equation can be rewritten in a more common way :

m 2 T F m 1 = 0
where F is called the fundamental matrix 9].

However, this relation is not de ned in some singular cases. For example, it is well known that, in the perspective projection case, if the displacement is a pure rotation, or if the scene is planar, the relation between points is homographic :

m 2 = H m 1
where H is called the homographic matrix. In the case of a pure rotation :

H = H 1 = A 2 R A 1 1 .
In the case of a plane with normal n and distance to the origin d : H = A 2 (R + t n T d ) A Our rst new contribution in this paper will be explained in the two next paragraphs 2.4 and 2.5. It consists in determining in which case of displacement or structure, the relation between corresponding 2D points is homographic when the projection is para-perspective (2.4) or orthographic (2.5).

Homographic relation in the para-perspective case

In the para-perspective case, we write the projection and displacement equations by extracting the third column from matrix A :

0 B B B B B @ u v 1 1 C C C C C A = 0 B B B B B @ u u 0 0 v v 0 0 0 1 1 C C C C C A | {z } (A) 3 0 B B B B B @ X Y 1 1 C C C C C A | {z } M +Z 0 B B B B B @ u v 1 1 C C C C C A | {z } (A)3 = (A) 3 M + Z (A) 3
where (A) 3 is an invertible square matrix since :

det((A) 3 ) = u v 6 = 0 Thus :

8 > > > > > > > > < > > > > > > > > : m 1 = (A 1 ) 3 M 1 + Z 1 (A 1 ) 3 ) M 1 = ((A 1 ) 3 ) 1 m 1 Z 1 ((A 1 ) 3 ) 1 (A 1 ) 3 m 2 = A 2 M 2 M 2 = Rjt] M 1 (6)
Let us denote : K = (A 2 Rjt]) 3 (A 2 Rjt]) 3 ((A 1 ) 3 ) 1 (A 1 ) 3 and H 1para = (A 2 Rjt]) 3 ((A 1 ) 3 ) 1 Equation 6 leads to : m 2 = H 1para m 1 + Z 1 K This relation is homographic if and only if K = 0 or if there exists a (3 3) matrix H Z such that Z 1 K = H Z m 1 . The rst condition induces a displacement constraint. It leads to the simple equation r = M 0 meaning that the rotation axis is parallel to the gaze direction. In that case, the homography is H 1para as

H para = H 1para + (A 2 Rjt]) 3 (A 2 Rjt]) 3 ((A 1 ) 3 ) 1 (A 1 ) 3 n (A 1 ) 3 + (A 1 ) 3 n] 1 (7)

Homographic relation in the orthographic case

The orthographic case is a particular case of para-perspective projection for which the gaze direction is the optical axis. Following a demonstration similar to the paraperspective case, we also obtain two constraints; the displacement constraint states that the rotation axis must be parallel to the optical axis, giving a homographic matrix :

H 1 ortho = (A 2 Rjt]) 3 ((A 1 ) 3 ) 1 and the geometric constraint states that the 3D-points must belong to the same plane which does not contain the optical axis. The homographic matrix is :

H ortho = H 1 ortho + (A 2 Rjt]) 3 n T ((A 1 ) 3 ) 1
All constraints on displacement and scene geometry for homographic relations are summarized in the following table :

ALL PARTICULAR CASES DESCRIPTION

In order to do an exhaustive study of particular cases combinations, we rst study every elementary particular case. We begin with particular camera parameter values, and then particular displacements of the camera.

Particular cases of projection and intrinsic parameters

In the previous section 2.2, we studied particular cases of projection and their simpli cations. Let p1, p2 and p3 denote the di erent kinds of projection : p1 = 0 and = 0 orthographic p2 = 1 and = 0 para-perspective projection p3 = 1 and = 1 perspective projection If no auto-focus and no zoom is used, for instance, it is possible to parameterize the model with fewer parameters than in the general case. This is one reason to study particular cases of intrinsic parameters.

Authors generally make several hypotheses regarding intrinsic parameters. For example, usually, in case of auto-calibration, common hypothesis states that the intrinsic parameters are constant. They may or may not be known. But, usually, some parameters are constant and some other are not.

We now detail all prior knowledge on parameters leading to particular cases.

The principal point

The principal point of coordinates (u 0 ; v 0 ) is not xed at the image plane in the general case but can be xed in some cases and its position can be known (for example, at the image center). We then change the reference frame, regarding the principal point position. This parameter is usually assumed to be null or, at least, considered a constant value. Furthermore, the numerical precision of the model obtained by this parameter is not crucial for the para-perspective or the orthographic projection cases.

The u and v parameters

Enciso 8] has experimentally proven that, for a large number of cameras, the u v ratio can be considered as a constant value even if other intrinsic parameters change. The constancy of this ratio can be expressed by the equality f = u = v , and the following transformation :

0 B B B B B B @ u u + u0 (1 ) u0 0 v v + v0 (1 ) v0 0 0 (1 ) 1 C C C C C C A = 0 B B B B B B @ f u + u0 (1 ) u0 0 f v + v0 (1 ) v0 0 0 (1 ) 1 C C C C C C A : 0 B B B B B B B B B B @ u v 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 C C C C C C C C C C A 3.1.4. The u and v parameters.
These parameters are null except in the para-perspective projection case.

In the para-perspective case, u and v are related to the other intrinsic parameters by : 8 > < > :

u = u X0 Z0 + Y0 Z0 v = v Y0 Z0
Their ratio is :

u v = u X0+ Y0 v Y0
. Thus, if we neglect with respect to u X0 Y0 , we obtain :

u v = u v X0
Y0 which is also a constant ratio, known if X0 Y0 value is known. Table 1 summarizes, for each intrinsic parameter, the particular cases (constant value are indexed by zero). Subsequently, we refer to each case by the label given in the rst column. v constant and known

f2 v = f 0 v constant f3 v = v( ) v free s1 u = v( ) u v constant and known s2 u = u( ) u free b1 v = 0 v constant and null b2 v = 0 v constant b3 v = v( ) v free B1 u = v( ) u and v equal B2 u = v( ) u v constant B3 u = u( ) u v free c1 u 0 = v 0 = 0
u 0 and v 0 constant and known c2 u 0 = u 0 0 and v 0 = v 0 0 u 0 and v 0 constant c3 u 0 = u 0 ( ) and v 0 = v 0 ( ) u 0 and v 0 free D R A F T April 23, 2001, 5:10pm D R A F T

Particular cases of displacement

A rigid displacement is parameterized by the rotation R and the translation t parameters.

Discrete motion -continuous motion

In an image sequence, if the displacement between two frames is small, we can approximate the rotation equations by their rst order expansion, using the notations r = u :

R = e r = I + r + o(r) = 0 B B B B B @ 1 r 2 r 1 r 2 1 r 0 r 1 r 0 1 1 C C C C C A
Otherwise, if the motion is larger, we can also consider the second order expansion :

R = I + r + r2 2 + o(r 2 ) = 0 B B B B B @ 1 (r 2 1 + r 2 2 ) r 1 r 0 r 2 r 2 r 0 + r 1 r 1 r 0 + r 2 1 (r 2 0 + r 2 2 ) r 2 r 1 r 0 r 2 r 0 r 1 r 2 r 1 + r 0 1 (r 2 0 + r 2 1 ) 1 C C C C C A 3.2.

About extrinsic parameters

The rotation parameters are related to the rotation axis and the rotation angle by : r = 2 tan 2 u, in the general case and r = u, in the rst or second order of expansion. The vector u is an unary vector giving the direction of the rotation axis.

Some components of u can be known or assumed null. Some values of may yield singularities; for example = 0 corresponds to a null rotation. Another particular case is the screw displacement for which = 4 and the rotation axis is parallel to the translation vector. The case = is not considered in this paper but must be considered if the camera has an angle of view greater than 180 degrees.

Some robotic systems give precise values of the robot displacements (angle, axis, translation). Some values may be known (we denote by _ 0 a constant and known

D R A F T April 23, 2001, 5:10pm D R A F T
value of a parameter ). Other informations on parallelism or orthogonality to a known direction may be available. As is the case for the translation vector.

Relations between axis and direction

These relations in which we are interested are orthogonality and parallelism :

the rotation axis is orthogonal to the translation plane (e.g. planar motion) : r ? t , r:t = 0 , r 0 t 0 + r 1 t 1 + r 2 t 2 = 0

screw displacement : r k t , 9 = r = t , 9 = 8 > > > > > < > > > > > : r 0 = t 0 r 1 = t 1 r 2 = t 2
the rotation axis or the translation direction is parallel or orthogonal to a known direction denoted by _g (_r or _t).

All constraints on motion

All these constraints, also called atomic particular cases , have simple expressions that can easily be combined. For this purpose, we use the fact that u is an unary vector and that, for monocular systems, the norm of translation cannot be recovered. To parameterize these vectors with only 2 parameters, we divide each component by a non-zero component. Then, the dot-product and scalar product induce linear relations. For example, if t 2 = 1, t ? r is equivalent to t 0 u 0 + t 1 u 1 + u 2 = 0 ) u 2 = t 0 u 0 t 1 u 1

All cases are collected in table 2.

Generation of all cases

In this section, we combine all previous constraints in order to generate all possible cases. We then generate the simpli ed equations of our vision problem, i.e., the F or H matrix coe cients, depending of the cases.

We call atomic case each case described above. By combining atomic cases, we produce molecular cases, i.e. all possible particular cases. constraints are solved by combining the atomic cases and solving the constraints by substitution 1 with some rules : one projection mode, one rotation mode. . . This corresponds to choosing one case in each family, a family being named by a label.

For example, in the R family, we have to choose one of R1, R2, R3 and R4. We denote by R 1-3] the set {R1, R2, R3} and by R 1;3] the set {R1, R3}. Thus, a molecular case is identi ed by the sequence :

p 1-3]g 1-3]f 1-3]s 1-3]b 1-3]B 1-3]c 1-3]R 1-4]r1a 1-2]u 1-24]W 1-3]T 1-2]t 1-12]D 1-3]Z 1-3]

How many cases do we have?

If we look at the expression of a particular case above-mentioned, we obtain 3:10 8 particular cases. But, this is not the real number of particular cases due to :

Incompatibility of some atomic cases, for instance (the symbol means AND ) :

(r k t) (r ? t) (r 6 = 0) (t 6 = 0) Redundancy of some constraints; two di erent set of atomic constraints can generate the same simpli ed model. For instance :

(r 0 = 0) (t ? r) is the same case than (t 1 = 0) (t 2 = 0) (t ? r)

It is easy to eliminate incompatible constraints. To deal with redundant constraints requires to compare each set of combined constraint with the others in order to determine the similarity. The complexity of this process is O(n 2 ), that makes this elimination intractable for large values of n.

Furthermore, redundant cases are not the main reason for the big amount of particular cases. Thus suppressing redundancies is not su cient to reduce the huge number of case to a computationally tractable amount.

We now propose an adapted strategy in order to deal with all cases. Previous works have tried to build a hierarchy of cases but they encounter problems in order 1 This work is done using Maple for symbolic computation.

D R A F T April 23, 2001, 5:10pm D R A F T
to manage it. The idea of this paper is (i) to eliminate some of the redundant cases by some considerations on the atomic cases and (ii) to limit the number of cases by the study of the particular forms of the matrices. For this second step, we will separate cases into two subgroups: cases inducing homographies and cases inducing fundamental relations.

Reducing the number of cases

Some redundancies are obvious :

in case of a null rotation, (R1), we do not consider every case of axis and angle, one is su cient; in case of rst and second order of rotation, (R2) and (R3), we do not consider the case (a1) where is equal to 2 ;

the case (a1) where is equal to 2 is only considered if the rotation axis and the translation direction are parallel, (Z2);

in the case of a null translation, we do not consider any relation of orthogonality or parallelism to other directions; in the case of non para-perspective projection, (p1) and (p3), u and v are equal to zero.

We also consider the following experimental simpli cations :

when approximating a perspective projection, (p1) and (p2), we neglect the parameter with respect to other approximations;

following previous studies 8] and 26], we assume that the ratio u v is constant; these two previous items imply that the u v ratio is also constant.

Then, there only remains, from the intrinsic parameters part, 117 cases and from the extrinsic parameters part, 21709 cases, leading to a total of 2539953 particular cases. This is approximately 100 times less than previously determined (see Appendix C for details). For each case, we have computed the set of reduced equations. Now, for each case, we compute the fundamental or homographic matrix expression.

As previously studied in subsections 2.3, 2.4 and 2.5, the displacements inducing homographic relations are : in the orthographic case (p1) : u k Oz. The relations between t and r are equivalent to the nullity of some vector components. We will not consider (Z1) and (Z2). Previous studies on orthographic displacement have shown that the displacement is retinal (t 1;3;5;7]).

in the para-perspective case (p2) : u k X 0 Y 0 Z 0 ] (D2). Since the view axis has at least a component on the optical axis, we set u 2 = 1. Moreover the view axis is not exactly the optical axis, thus we cannot have u 0 = 0 and u 1 = 0.

in the perspective case (p3) : t = 0. Therefore we do not consider the parallelism and orthogonality constraints on t.

We also note that, since we are dealing with only 2 views, relations between r or t with a known vector _g will not simplify the H-matrix form, except in the para-perspective case, if _g = M 0 .

The homographic relation cases lead to 351 cases of orthographic homographic relations, 18360 cases of para-perspective homographic relations and 2619 cases of perspective homographic relations, leading to a total 21330 cases of homographic relations (see explanations in Appendix C).

We will not study para-perspective and orthographic projection for fundamental matrices since the domain of validity of such projection approximations is included in conditions of existence of homographic relation. In the case of perspective projection, (p3): t 6 = 0 thus u 0 = 1 or u 1 = 1.

For perspective projection, there are 72252 di erent cases as shown in Appendix

MATRIX FORMS

In the previous section, we have signi cantly reduced the number of cases in both fundamental matrices and homographic matrices sets. However, we have still to deal with a huge amount of cases which is numerically intractable. In this section, we introduce a new idea in order to split the two sets of matrices in a two-level tree.

Each set of matrices is rst split in subsets of matrices depending on their form.

We determine a matrix form by a very simple parameterization. We consider (3 3) matrices having 9 parameters (coe cients) and we use two simple rules :

If a coe cient is equal to zero, then there is one fewer parameter.

If a coe cient has the same expression or is opposite to another, then there is one fewer parameter again.

These operations are very simple and can be computed on every case in a reasonable time (approximately one day for the entire process determining the matrix form).

This process, as illustrated in gure 4, reduces the 21330 cases of homography matrices to only 108 subgroups and the 72252 cases of fundamental matrices to only 188 subgroups.

The table in

Appendix A shows all the particular forms of homography matrices and the table in Appendix B shows all the particular forms of fundamental matrices.

Homography and fundamental matrices are de ned up to a scale factor. This parameter has not been eliminated here. We take it into account in the numerical implementation. Fundamental matrices have also to satisfy the constraint det F = 0. We have to check if this constraint is satis ed or not in order to know if the number of degree of freedom is reduced. This is important in order to properly use For each matrix form, we have collected all the cases that have generated them.

Once the matrix form corresponding to an experiment is determined, it is possible to backtrack the source cases.

EXPERIMENTS

Forms of homography

We have recorded several video sequences for which the camera displacement induces a homographic relation between image points m 1 and m 2 . We have rst extracted points of interest and determined matching points using the image-matching algorithm from Zhang 28]. From each matrix form enumerated in table 1, we have estimated the homography parameters with the robust Least Median of Squares For each video sequence, we have veri ed that the model with the smallest residual error indeed corresponds to the displacement performed by a robotic system.

An example is proposed in gure 5. For each pair of consecutive images, the case with the least residual error is the case n o 51 in the table in Appendix A that corresponds to the matrix form :

H 51 = 0 B B B B B @ x 1 x 2 x 3 x 2 x 1 x 6 0 0 x 1 1 C C C C C A
We observe that this case corresponds to a rst order rotation (R2). If we consider only the rst and the last frame, the rotation is general (R4).

We also performed several experiments without the help of a precise robotic system. A human took a camera by hand and tried to realize di erent particular displacements. Figure 6 shows two frames of a video sequence. The camera motion was approximately a rotation around its optical axis followed by a translation. As the previous experiment with a robotic system, for each pair of consecutive images, the case with smallest residual error is the case n o 51 in the table in Appendix A. This result demonstrates the robustness of the analysis of displacement by particular cases. Even an approximative displacement is best recovered by a close particular case than the general equation. x-axis translation and small pan rotation, with auto-focus

Forms of fundamental matrices

We have done the same experiment for a displacement that induces a fundamental relation. The criterion is using the distance between a 2D point m 1 and its epipolar line F m 2 27, 16]:

f m (F) = jm 2 T F m 1 j p (F T m 2 ) 2 1 + (F T m 2 ) 2 2
The camera has performed a translation parallel to the x-axis, a small pan rotation, and corrected focal length with auto-focus. The case with less residual error corresponds to the fundamental matrix form (number 59 in the table in Appendix B):

F 59 = 0 B B B B B @ 0 0 0 x 0 x 1 x 2 0 x 2 x 3 1 C C C C C A D R A F T April 23, 2001, 5:10pm D R A F T
This particular form was obtained from cases where the rotation was approximated to its rst and second order, the translation is parallel to the x-axis, the rotation axis is orthogonal to the optical axis and the intrinsic parameters are free.

HOW TO EXTEND THIS WORK TO VIDEO SEQUENCES ?

In this paper, we have dealt with video sequences with pairs of frames. Two major extension could be down: (i) an extension of this work to trilinearities (relations between 2D points from 3 frames) and (ii) an extension to video sequences of n frames.

In order to consider sequences of n images, we need to introduce several cases about the displacements. We have constraints on translation, axis and angle of rotation and zoom factor. For each of these quantities, the questions are: is the displacement between two frames constant? Is the acceleration constant? linear?

following a known rule?

In our formalism, we need to introduce these constraints in the Maple code who will generates others equations with more constraints but also more data (n images) and more parameters. It is also easy to change the criterion used to measure the adequation of the model to the data (one C function to be rewritten).

We have to think about the fact that some objects may disappear along a video sequence and that their movements may be detected only in few images of the video sequences. This is a problem that will be examined in another paper.

CONCLUSION

We have studied how to deal with video sequences and with particular cases of displacement and projection that often occur in real situations (man walking on a at road, objects far from the retina, . . . ). The general equations of the vision problem present singularities in some particular cases that are usually avoided. In the present paper, we have proposed an alternative approach to this problem, using such singularities and other particular cases in order to obtain more informations than in the general case instead of avoiding them.

Our major contributions are :

We have determined the conditions of existence of homographic relations between projected 2D points for the orthographic, the para-perspective and the perspective projections.

We have used these conditions and other obvious redundancy properties to reduce the amount of homographic particular cases to study. Thus, we have determined all particular forms of matrices and we have obtained, for each particular form, the list of cases that have generated this form. This result is a rst fundamental step for further studies.

This study might be extended in two ways : (i) to be able, given a form, to analyze the molecular constraints, to determine which are redundant and which correspond to the case we are dealing with, and (ii) to do the same analysis with geometrical property of the 3D scene, meaning homography induced by planes. The structure of this analysis is as general as possible to extend this work to other kind of cameras (conic mirror, ...).

The applications are twofold :

an incremental reconstruction of the scene using di erent cases : each case studied has fewer parameters than the next one, giving the ability to recover some parameters from others already determined. We have already studied the control of a robot on a particular case 15].

the segmentation of objects moving with di erent displacements or with different geometric properties in video sequences : using a -trimmed square method instead of the least median square method, we can build sets of points with same matrix forms (and same numerical matrix forms).

D R A F T April 23, 2001, 5:10pm D R A F T APPENDIX A

Table of particular forms of homographic matrices

The following table shows the simpli ed forms obtained and, for each form, the cases that have generated them. We denote by # the form number, by p the number of parameters (we have not taken into account the fact that the homography matrix is de ned up to a scale factor but we do it in our numerical implementation) and by n the number of molecular cases that have generated a form.

TABLE

Particular forms of homography and cases that have generated them # p simpli ed form of homography generated by n 1 1

x 1 0 0 0 x 1 0 0 0

x 1 ] p1g1f 1;2]b1B1c 1;2]T1t13R1u4Z3a2 p3g1f 1;2]b1B1c 1;2]T1t13R1u4Z3a2 p3g2f1b1B1c 1;2]T1t13R1u4Z3a2 p3g2f2b1B1c1T1t13R1u4Z3a2 11 2 1 x 1 0 0 0 x 1 x 1 0 0 x 1 ] p1g1f1b1B1c 1;2]T2t 5;7]R1u4Z3a2 4 3 1 x 1 0 x 1 0 x 1 0 0 0 x 1 ] p1g1f 1;2]b1B1c 1;2]T2t1R1u4Z3a2 4 4 2
x 1 0 0 0 x 1 x 6 0 -x 6 x 1 ] p3g1f1b1B1c1T1t13R2u 17;21]Z3a2 2 5 2

x 1 0 0 0 x 1 x 6 0 0 x 1 ] p1g1f2b1B1c 1;2]T2t 5;7]R1u4Z3a2 4 6 2

x 1 0 0 0 x 5 0 0 0 x 1 ] p1g1f3b1B1c1T1t13R1u4Z3a2 p3g 1;2]f3b1B1c1T1t13R1u4Z3a2 3 7 2

x 1 0 x 1 0 x 1 x 6 0 0 x 1 ] p1g1f 1;2]b1B1c 1;2]T2t3R1u4Z3a2 4 8 2

x 1 0 x 1 0 x 5 0 0 0 x 1 ] p1g1f3b1B1c1T2t1R1u4Z3a2 1 9 2

x 1 0 x 3 0 x 1 0 -x 3 0 x 1 ] p3g1f 1;2]b1B1c1T1t13R2u 1;5]Z3a2 4 10 2

x 1 0 x 3 0 x 1 0 0 0 x 1 ] p3g2f2b1B1c2T1t13R1u4Z3a2 1 11 2

x 1 x 2 0 -x 2 x 1 0 0 0 x 1 ] p 1;3]g1f1b1B1c1T1t13R2u 13;9]Z3a2 4 12 2

x 1 x 2 0 -x 2 x 1 x 1 0 0 x 1 ] p1g1f1b1B1c1T2t 5;7]R2u 13;9]Z3a2 4 13 2

x 1 x 2 0 0 x 1 0 0 0 x 1 ] p3g3f1b1B1c1T1t13R1u4Z3a2 2 14 2

x 1 x 2 x 1 -x 2 x 1 0 0 0 x 1 ] p1g1f 1;2]b1B1c1T2t1R2u13Z3a2 2 15 3

x 1 0 0 0 x 1 x 6 0 x 8 x 1 ] p3g1f2b1B1c1T1t13R2u 17;21]Z3a2 2 16 3

x 1 0 0 0 x 5 x 6 0 -x 6 x 5 ] p3g1f1b1B1c1T1t13R3u 17;21]Z3a2 p3g1f1b1B1c1T1t13R4u 17;21]Z3a 1;2] 6 17 3

x 1 0 0 0 x 5 x 6 0 0 x 1 ] p1g1f3b1B1c 1;2]T2t 5;7]R1u4Z3a2 p1g1f3b1B1c2T1t13R1u4Z3a2 p3g1f3b1B1c2T1t13R1u4Z3a2 6 18 3

x 1 0 x 1 0 x 5 x 6 0 0 x 1 ] p1g1f3b1B1c 1;2]T2t3R1u4Z3a2 p1g1f3b1B1c2T2t1R1u4Z3a2 3 19 3

x 1 0 x 3 0 x 1 0 -x 3 x 8 x 1 ] p3g2f 1;2]b1B1c1T1t13R2u 1;5]Z3a2 4 20 3

x 1 0 x 3 0 x 1 x 6 -x 3 -x 6 x 1 ] p3g1f1b1B1c1T1t13R2u 2;6;19;23]Z3a2 4 21 3

x 1 0 x 3 0 x 1 x 6 0 -x 6 x 1 ] p3g2f1b1B1c1T1t13R2u 17;21]Z3a2 2 22 3

x 1 0 x 3 0 x 1 x 6 0 0 x 1 ] p1g1f 1;2]b1B1c3T1t13R1u4Z3a2 p1g1f 1;2]b1B1c3T2t 1;3;5;7]R1u4Z3a2 p3g 1;2]f 1;2]b1B1c3T1t13R1u4Z3a2 14 23 3

x 1 0 x 3 0 x 5 0 -x 3 0 x 1 ] p3g1f 1-3]b1B1c1T1t13R3u 1;5]Z3a2 p3g1f3b1B1c1T1t13R2u 1;5]Z3a2 p3g1f 1-3]b1B1c1T1t13R4u 1;5]Z3a 1;2] 20 24 3

x 1 x 2 0 -x 2 x 1 0 0 0 x 9 ] p 1;3]g1f1b1B1c1T1t13R3u 9;13]Z3a2 p 1;3]g1f1b1B1c1T1t13R4u 9;13]Z3a 1;2] 12 25 3

x 1 x 2 0 -x 2 x 1 x 6 0 -x 6 x 1 ] p3g1f1b1B1c1T1t13R2u 11;15;18;22]Z3a2 4 26 3

x 1 x 2 0 -x 2 x 1 x 6 0 0 x 6 ] p1g1f1b1B1c1T2t 5;7]R 3;4]u 9;13]Z3a2 8 27 3

x 1 x 2 0 0 x 5 0 0 0 x 1 ] p3g3f3b1B1c1T1t13R1u4Z3a2 1 28 3

x 1 x 2 0 x 4 x 1 0 0 0 x 1 ] p 1;3]g1f2b1B1c1T1t13R2u 9;13]Z3a2 4 29 3

x 1 x 2 x 1 -x 2 x 1 x 6 0 0 x 1 ] p1g1f1b1B1c1T2t3R2u 9;13]Z3a2 2 30 3

x 1 x 2 x 1 x 4 x 1 0 0 0 x 1 ] p1g1f2b1B1c1T2t1R2u 9;13]Z3a2 2 31 3

x 1 x 2 x 3 -x 2 x 1 0 -x 3 0 x 1 ] p3g1f1b1B1c1T1t13R2u 3;7;10;14]Z3a2 4 32 3

x 1 x 2 x 3 -x 2 x 1 0 0 0 x 3 ] p1g1f1b1B1c1T2t1R 3;4]u 9;13]Z3a2 4 33 3

x 1 x 2 x 3 0 x 1 0 0 0 x 1 ] p3g3f 1;2]b1B1c2T1t13R1u4Z3a2 2 34 4

x 1 0 0 0 x 5 x 6 0 x 8 x 1 ] p3g1f3b1B1c1T1t13R2u 17;21]Z3a2 2 35 4

x 1 0 0 0 x 5 x 6 0 x 8 x 5 ] p3g1f2b1B1c1T1t13R3u 17;21]Z3a2 p3g1f2b1B1c1T1t13R4u 17;21]Z3a 1;2] 6 36 4

x 1 0 x 3 0 x 1 x 6 -x 3 x 8 x 1 ] p3g1f2b1B1c1T1t13R2u 2;6;19;23]Z3a2 4 37 4

x 1 0 x 3 0 x 1 x 6 0 x 8 x 1 ] p3g2f2b1B1c1T1t13R2u 17;21]Z3a2 2 38 4

x 1 0 x 3 0 x 5 0 -x 3 x 8 x 1 ] p3g2f3b1B1c1T1t13R2u 1;5]Z3a2 2 39 4

x 1 0 x 3 0 x 5 x 6 0 0 x 1 ] p 1;3]g1f3b1B1c3T1t13R1u4Z3a2 p1g1f3b1B1c3T2t 1;3;5;7]R1u4Z3a2 p3g2f3b1B1c 2;3]T1t13R1u4Z3a2 8 40 4

x 1 x 2 -x 2 0 x 5 x 6 0 -x 6 x 5 ] p3g2f1b1B1c1T1t13R4u21Z3a1 1 41 4

x 1 x 2 0 x 4 x 1 0 0 0 x 9 ] p 1;3]g1f2b1B1c1T1t 9;13]R3u13Z3a2 p 1;3]g1f2b1B1c1T1t13R4u 9;13]Z3a 1;2] 12 42 4

x 1 x 2 0 x 4 x 1 x 6 0 0 x 1 ] p1g1f2b1B1c1T2t 5;7]R2u 9;13]Z3a2 4 43 4

x 1 x 2 0 x 4 x 5 0 0 0 x 1 ] p 1;3]g1f3b1B1c1T1t13R2u 9;13]Z3a2 p2g1f 1-3]b 2;3]B 1;2]c1T1t13R2u 11-15]Z3a2 28 44 4

x 1 x 2 0 x 4 x 5 0 0 0 x 5 ] p2g1f 1;3]b 2;3]B 1;2]c1T1t13R2u 10;14]Z3a2 16 45 4

x 1 x 2 0 x 4 x 5 x 1 0 0 x 1 ] p2g1f1b 2;3]B 1;2]c1T2t5R2u 11;15]Z3a2 8 46 4

x 1 x 2 0 x 4 x 5 x 5 0 0 x 5 ] p2g1f1b2B1c1T2t5R2u 10;14]Z3a2 8 47 4

x 1 x 2 x 1 x 4 x 1 x 6 0 0 x 1 ] p1g1f2b1B1c1T2t3R2u 9;13]Z3a2 2 48 4

x 1 x 2 x 1 x 4 x 5 0 0 0 x 1 ] p1g1f3b1B1c1T2t1R2u 9;13]Z3a2 followed on next page D R A F T April 23, 2001, 5:10pm D R A F T from previous page p2g1f 1-3]b 2;3]B 1;2]c1T2t1R2u 11;15]Z3a2 26 49 4

x 1 x 2 x 2 0 x 5 x 6 0 -x 6 x 5 ] p3g2f1b1B1c1T1t13R4u17Z3a1 1 50 4

x 1 x 2 x 3 -x 2 x 1 x 6 -x 3 -x 6 x 1 ] p3g1f1b1B1c1T1t13R2u 4;8;12;16;20;24]Z3a2 6 51 4

x 1 x 2 x 3 -x 2 x 1 x 6 0 0 x 1 ] p 1;3]g1f1b1B1c 2;3]T1t13R2u 9-13]Z3a2 p1g1f1b1B1c 2;3]T2t 1;3;5;7]R2u 9;13]Z3a2 p2g1f1b 2;3]B 1;2]c 1-3]T2t9R2u 10-12;14-16]Z1a2 p2g1f1b 2;3]B 1;2]c 1-3]T2t10R2u 11;15]Z1a2 p2g1f1b 2;3]B 1;2]c 1-3]T2t11R2u 10;14]Z1a2 144 52 4

x 1 x 2 x 3 -x 2 x 1 x 6 0 0 x 3 ] p1g1fb1B1c1T2t3R 3;4]u 9;13]Z3a2 4 53 4

x 1 x 2 x 3 0 x 1 0 -x 3 x 8 x 1 ] p3g3f 1;2]b1B1c1T1t13R2u 1;5]Z3a2 4 54 4

x 1 x 2 x 3 0 x 1 x 6 0 -x 6 x 1 ] p3g3f1b1B1c1T1t13R2u 17;21]Z3a2 2 55 4

x 1 x 2 x 3 0 x 1 x 6 0 0 x 1 ] p3g3f 1;2]b1B1c3T1t13R1u4Z3a2 2 56 4

x 1 x 2 x 3 0 x 5 0 -x 3 -x 2 x 1 ] p3g2f 1-3]b1B1c1T1t13R4u5Z3a1 3 57 4

x 1 x 2 x 3 0 x 5 0 -x 3 x 2 x 1 ] p3g2f 1-3]b1B1c1T1t13R4u1Z3a1 3 58 4

x 1 x 2 x 3 x 4 x 1 0 -x 3 0 x 1 ] p3g1f2b1B1c1T1t13R2u 3;7;10;14]Z3a2 4 59 4

x 1 x 2 x 3 x 4 x 1 0 0 0 x 3 ] p1g1f2b1B1c1T2t1R 3;4]u 9;13]Z3a2 p2g1f 1;2]b 2;3]B 1;2]c1T2t1R2u 10;14]Z3a2 20 60 5

x 1 0 0 0 x 5 x 6 0 x 8 x 9 ] p3g1f3b1B1c1T1t13R3u 17;21]Z3a2 p3g1f3b1B1c1T1t13R4u 17;21]Z3a 1;2] 6 61 5

x 1 0 x 3 0 x 1 x 6 x 7 x 8 x 1 ] p3g2f 1;2]b1B1c1T1t13R2u 2;6;19;23]Z3a2 8 62 5

x 1 0 x 3 0 x 5 x 6 -x 3 x 8 x 1 ] p3g1f3b1B1c1T1t13R2u 2;6;19;23]Z3a2 4 63 5

x 1 0 x 3 0 x 5 x 6 0 x 8 x 1 ] p3g2f3b1B1c1T1t13R2u 17;21]Z3a2 2 64 5

x 1 x 2 0 x 4 x 1 x 6 0 0 x 9 ] p1g1f2b1B1c1T2t 5;7]R 3;4]u 9;13]Z3a2 8 65 5

x 1 x 2 0 x 4 x 1 x 6 0 x 8 x 1 ] p3g1f2b1B1c1T1t13R2u 11;15;18;22]Z3a2 4 66 5

x 1 x 2 0 x 4 x 5 0 0 0 x 9 ] p1g1f3b1B1c1T1t13R 3;4]u 9;13]Z3a2 p1g1f3b1B1c1T1t13R4u 9;13]Z3a1 p2g1f 1-3]b 2;3]B 1;2]c1T1t13R 2-4]u 12;16]Z3a2 p2g1f3b 2;3]B 1;2]c1T1t13R2u 10;14]Z3a2 p2g1f 1-3]b 2;3]B 1;2]c1T1t13R 3;4]u 10;11;14;15]Z3a2 p2g1f 1-3]b 2;3]B 1;2]c1T1t13R4u 10-12;14-16]Z3a1 p3g1f3b1B1c1T1t13R3u 9;13]Z3a2 p3g1f3b1B1c1T1t13R4u 9;13]Z3a 1;2] p3g 2;3]f 1-3]b1B1c1T1t13R 2-4]u 9;13]Z3a2 p3g 2;3]f 1-3]b1B1c1T1t13R4u 9-13]Z3a1 308 67 5

x 1 x 2 0 x 4 x 5 x 6 0 0 x 1 ] p1g1f3b1B1c1T2t 5;7]R2u 9;13]Z3a2 p2g1f 2;3]b 2;3]B 1;2]c1T2t5R2u 11;15]Z3a2 20 68 5

x 1 x 2 0 x 4 x 5 x 6 0 0 x 5 ] p2g1f2b 2;3]B 1;2]c1T2t5R2u 10;14]Z3a2 8 69 5

x 1 x 2 0 x 4 x 5 x 6 0 0 x 6 ] p2g1f1b 2;3]B 1;2]c1T2t5R 2-4]u 12;16]Z3a2 p2g1f1b 2;3]B 1;2]c1T2t5R 3;4]u 10;11;14;15]Z3a2 56 70 5

x 1 x 2 x 1 x 4 x 5 x 6 0 0 x 1 ] p1g1f3b1B1c1T2t3R2u 9;13]Z3a2 p2g1f 1-3]b 2;3]B 1;2]c1T2t3R2u 11;15]Z3a2 26 71 5

x 1 x 2 x 3 -x 2 x 1 x 6 0 0 x 9 ] p1g1f1b1B1c 1-3]T2t12R4u 9;13]Z3a1 p1g1f1b1B1c 2;3]T1t13R 3;4]u 9;13]Z3a2 p1g1f1b1B1c 2;3]T2t13R4u 9;13]Z3a1 p1g1f1b1B1c 2;3]T2t 1;3;5;7]R 3;4]u 9-13]Z3a2 p3g1f1b1B1c 2;3]T1t13R3u 9;13]Z3a2 p3g1f1b1B1c 2;3]T1t13R4u 9;13]Z3a 1;2] 62 72 5

x 1 x 2 x 3 0 x 1 x 6 0 x 8 x 1 ] p3g3f2b1B1c1T1t13R2u 17;21]Z3a2 2 73 5

x 1 x 2 x 3 0 x 5 0 -x 3 x 8 x 1 ] p3g 2;3]f 1-3]b1B1c1T1t13R 3;4]u ;5]Z3a2 p3g3f 1-3]b1B1c1T1t13R4u 1;5]Z3a1 p3g3f3b1B1c1T1t13R2u 1;5]Z3a2 32 74 5

x 1 x 2 x 3 0 x 5 x 6 0 -x 6 x 5 ] p3g 2;3]f1b1B1c1T1t13R 3;4]u 17;21]Z3a2 p3g3f1b1B1c1T1t13R4u 17;21]Z3a1 10 75 5

x 1 x 2 x 3 0 x 5 x 6 0 0 x 1 ] p3g3f3b1B1c 2;3]T1t13R1u4Z3a2 2 76 5

x 1 x 2 x 3 x 4 x 1 x 6 0 0 x 1 ] p1g1f2b1B1c 2;3]T2t 1;3;5;7]R2u 9;13]Z3a2 p 1;3]g1f2b1B1c 2;3]T1t13R2u 9;13]Z3a2 p2g1f2b 2;3]B 1;2]c 1-3]T2t10R2u 11;15]Z1a2 p2g1f2b 2;3]B 1;2]c 1-3]T2t11R2u 10;14]Z1a2 p2g1f2b 2;3]B 1;2]c 1-3]T2t9R2u 10-12;14-16]Z1a2 144 77 5

x 1 x 2 x 3 x 4 x 1 x 6 0 0 x 3 ] p1g1f2b1B1c1T2t3R 3;4]u 9;13]Z3a2 p2g1f 1;2]b 2;3]B 1;2]c1T2t3R2u 10;14]Z3a2 20 78 5

x 1 x 2 x 3 x 4 x 5 0 -x 3 0 x 1 ] p3g1f3b1B1c1T1t13R2u 3;7;10;14]Z3a2 4 79 5

x 1 x 2 x 3 x 4 x 5 0 0 0 x 3 ] p1g1f3b1B1c1T2t1R 3;4]u 9;13]Z3a2 p2g1f 1-3]b 2;3]B 1;2]c1T2t1R 2-4]u 12;16]Z3a2 p2g1f 1-3]b 2;3]B 1;2]c1T2t1R 3;4]u 10;11;14;15]Z3a2 180 80 5

x 1 x 2 x 3 x 4 x 5 x 1 0 0 x 1 ] p2g1f1b 2;3]B 1;2]c1T2t6R2u 11;15]Z3a2 8 81 5

x 1 x 2 x 3 x 4 x 5 x 5 0 0 x 5 ] p2g1f1b 2;3]B 1;2]c1T2t6R2u 10;14]Z3a2 8 82 6

x 1 0 x 3 0 x 5 x 6 x 7 x 8 x 1 ] p3g2f3b1B1c1T1t13R2u 2;6;19;23]Z3a2 4 83 6

x 1 x 2 0 x 4 x 5 x 6 0 0 x 9 ] p1g1f3s1b1B1c1T2t 5-7]r1U1R 3-4]u 9;13]Z3W3D3a2 p2g1f 2;3]s1b 2-3]B 1;2]c1T2t5r1U1R 3-4] u 10-12;14-16]Z3W3D3a2 p2g1f2s1b 2-3]B 1;2]c1T2t5r1U1R2u 12;16]Z3W3D3a2 p2g1f3s1b 2-3]B 1;2]c1T2t5r1U1R2u 10;12;14;16]Z3W3D3a2 128 84 6

x 1 x 2 0 x 4 x 5 x 6 0 x 8 x 1 ] p3g1f3b1B1c1T1t13R2u 11;15;18;22]Z3a2 4 85 6

x 1 x 2 x 3 -x 2 x 5 x 6 -x 3 x 6 x 9 ] p3g1f1b1B1c1T1t13R3u 3;7;10;14]Z3a2 p3g1f1b1B1c1T1t13R4u 3;7;10;14]Z3a 1;2] 12 86 6

x 1 x 2 x 3 -x 2 x 5 x 6 x 3 -x 6 x 9 ] p3g1f1b1B1c1T1t13R3u 11;15;18;22]Z3a2 p3g1f1b1B1c1T1t13R4u 11;15;18;22]Z3a 1;2] 12 87 6

x 1 x 2 x 3 0 x 1 x 6 x 7 x 8 x 1 ] p3g3f 1;2]b1B1c1T1t13R2u 2;6;19;23]Z3a2 8 88 6

x 1 x 2 x 3 0 x 5 x 6 0 x 8 x 1 ] p3g3f3b1B1c1T1t13R2u 17;21]Z3a2 2 89 6

x 1 x 2 x 3 0 x 5 x 6 0 x 8 x 5 ] p3g 2;3]f2b1B1c1T1t13R3u 17;21]Z3a2 p3g 2;3]f2b1B1c1T1t13R4u 17;21]Z3a 1;2] 12 90 6

x 1 x 2 x 3 x 2 x 5 x 6 -x 3 -x 6 x 9 ] p3g1f1b1B1c1T1t13R3u 2;6;19;23]Z3a2 p3g1f1b1B1c1T1t13R4u 2;6;19;23]Z3a 1;2] 12 91 6

x 1 x 2 x 3 x 4 x 1 x 6 -x 3 x 8 x 1 ] p3g1f2b1B1c1T1t13R2u 4;8;12;16;20;24]Z3a2 6 92 6

x 1 x 2 x 3 x 4 x 1 x 6 0 0 x 9 ] p1g1f2b1B1c 1-3]T2t12R4u 9;13]Z3a1 p1g1f2b1B1c2T1t13R 3;4]u 9;13]Z3a2 p1g1f2b1B1c 2;3]T1t13R4u 9;13]Z3a1 p1g1f2b1B1c 2;3]T2t 1;3;5;7]R 3;4]u 9;13]Z3a2 p3g1f2b1B1c 2;3]T1t13R 3;4]u 9;13]Z3a2 p3g1f2b1B1c 2;3]T1t13R4u 9;13]Z3a1 p2g1f2b 2;3]B 1;2]c 1-3]T2t10R 3-4]u 11;15]Z1a2 p2g1f2b 2;3]B 1;2]c 1-3]T2t11R 3;4]u 10;14]Z1a2 p2g1f2b 2;3]B 1;2]c 1-3]T2t9R 3;4]u 10-12;14-16]Z1a2 302 93 6

x 1 x 2 x 3 x 4 x 5 x 6 0 0 x 1 ] p1g1f3b1B1c 2;3]T1t13R2u 9;13]Z3a2 p1g1f3b1B1c 2;3]T2t 1;3;5;7]R2u 9;13]Z3a2 p2g1f 1-3]b 2;3]B 1;2]c 1-3]T2t 2;4;7;8;9;10-12] R2u 11;15]Z3a2 followed on next page D R A F T April 23, 2001, 5:10pm D R A F T from previous page p2g1f 2;3]b 2;3]B 1;2]c1T2t6R2u 11;15]Z3a2 p2g1f 1-3]b 2;3]B 1;2]c 2;3]T2t 1;3;5;6]R2u 11;15]Z3a2 p2g1f 1-3]b 2;3]B 1;2]c 2;3]T1t13R2u 11;15]Z3a2 p3g1f3b1B1c 2;3]T1t13R2u 9;13]Z3a2 p2g1f 1;2]b 2;3]B 1;2]c 1-3]T2t 10-12]R2u 11;15]Z2a2 p2g1f 1;2]b 2;3]B 1;2]c 1-3]T2t 2;4;11;12]R2u 11;15]Z1a2 p2g1f 1;2]b 2;3]B 1;2]c 1-3]T2t 2;11]R2u 12;16]Z1a2 p2g1f3b2B1c1T2t 2;4;9;10-12]R2u 11;15]Z1a2 p2g1f3b2B1c1T2t 9;11]R2u 10;14]Z1a2 p2g1f3b2B1c1T2t 2;9;11]R2u 12;16]Z1a2 p2g1f3b2B1c1T2t 10-12]R2u 11;15]Z2a2 1624 94 6

x 1 x 2 x 3 x 4 x 5 x 6 0 0 x 3 ] p1g1f3b1B1c1T2t3R 3;4]u 9;13]Z3a2 p2g 1-3]f1b 2;3]B 1;2]c1T2t3R 2-4]u 12;16]Z3a2 p2g1f 1-3]b 2;3]B 1;2]c1T2t3R 3;4]u 10;11;14;15]Z3a2 180 95 6

x 1 x 2 x 3 x 4 x 5 x 6 0 0 x 5 ] p2g1f 1;2]b 2;3]B 1;2]c 1-3]T2t 2;4;7-12]R2u 10;14]Z3a2 p2g1f 1;2]b 2;3]B 1;2]c 2;3]T1t13R2u 10;14]Z3a2 p2g1f2b 2;3]B 1;2]c1T2t6R2u 10;14]Z3a2 p2g1f 1;2]b 2;3]B 1;2]c 2;3]T2t 1;3;5;6]R2u 10;14]Z3a2 p2g1f 1;2]b 2;3]B 1;2]c 1-3]T2t 10-12]R2u 10;14]Z2a2 p2g1f 1;2]b 2;3]B 1;2]c 1-3]T2t 7;8;10;12]R2u 10;14]Z1a2 p2g1f 1;2]b 2;3]B 1;2]c 1-3]T2t 7;10]R2u 12;16]Z1a2 984 96 6

x 1 x 2 x 3 x 4 x 5 x 6 0 0 x 6 ] p2g1f1b 2;3]B 1;2]c1T2t6R 2-4]u 12;16]Z3a2 p2g1f1b 2;3]B 1;2]c1T2t6R 3;4]u 10;11;14;15]Z3a2 56 97 7

x 1 0 x 3 x 4 x 5 x 6 x 7 0 x 9 ] p3g1f 1-3]b1B1c 2;3]T1t13R 2;3]u 1;5]Z3a2 p3g1f 1-3]b1B1c 2;3]T1t13R4u 1;5]Z3a 1;2] 48 98 7

x 1 x 2 x 3 0 x 5 x 6 0 x 8 x 9 ] p3g 1-3]f 1-3]b1B1c 2;3]T1t13R 2-4]u 17;21]Z3a2 p3g 1-3]f 1-3]b1B1c 2;3]T1t13R4u 17;21]Z3a1 p3g 2;3]f3b1B1c1T1t13R 3;4]u 17;21]Z3a2 p3g 2;3]f3b1B1c1T1t13R4u 17;21]Z3a1 156 99 7

x 1 x 2 x 3 0 x 5 x 6 x 7 x 8 x 1 ] p3g3f3b1B1c1T1t13R2u 2;6;19;23]Z3a2 4 100 7

x 1 x 2 x 3 x 4 x 5 0 -x 3 x 8 x 9 ] p3g 2;3]f 1-3]b1B1c1T1t13R2u 3;7;10;14]Z3a2 24 101 7

x 1 x 2 x 3 x 4 x 5 x 6 -x 3 x 8 x 1 ] p3g1f3b1B1c1T1t13R2u 4;8;12;16;20;24]Z3a2 6 102 7

x 1 x 2 x 3 x 4 x 5 x 6 0 -x 6 x 9 ] p3g 2;3]f1b1B1c1T1t13R2u 11;15;18;22]Z3a2 8 103 7

x 1 x 2 x 3 x 4 x 5 x 6 0 0 x 9 ] p3g1f3b1B1c 2;3]T1t13R 3;4]u 9;13Z3a2 p3g1f3b1B1c 2;3]T1t13R4u 9;13]Z3a1 p3g 2;3]f 1-3]b1B1c 2;3]T1t13R 2-4]u 9;13]Z3a2 p3g 2;3]f 1-3]b1B1c 2;3]T1t13R4u 9;13]Z3a1 and all other para and ortho 10318 104 8

x 1 x 2 x 3 x 4 x 5 x 6 -x 3 x 8 x 9 ] p3g1f2b1B1c1T1t13R3u10Z3a2 48 105 8

x 1 x 2 x 3 x 4 x 5 x 6 0 x 8 x 9 ] p3g 1-3]f 1-3]s1b1B1c 2;3]T1t13r1U1R2 u 11;15;18;22]Z3W3D3a2 p3g 2;3]f 2;3]s1b1B1c1T1t13r1U1R2u 11;15;18;22]Z3W3D3a2 88 106 8

x 1 x 2 x 3 x 4 x 5 x 6 x 3 x 8 x 9 ] p3g1f 2;3]b1B1c1T1t13R3u 11;15;18;22]Z3a2 p3g1f 2;3]b1B1c1T1t13R4u 11;15;18;22]Z3a 1;2] 24 107 8

x 1 x 2 x 3 x 4 x 5 x 6 x 7 0 x 9 ] p3g1f 1-3]b1B1c 2;3]T1t13R2u 3;7;10;14]Z3a2 24 108 9

x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 ] all the other perspective cases 3630 APPENDIX B

Table of particular forms of fundamental matrices

Please note that, as it is for the previous table, the number of parameters p does not take into account that the fundamental matrix is de ned up to a scale factor and that its determinant is null. This is done is the numerical implementation. x 5 x 6

x 7 -x 6 0 ] g1f1s2c1t11R2u13Z2a2 16 144 6

x 1 x 2 x 3 -x 2 0 x 6 x 7 0

x 9 ] g1f3s1c1t10R2u1Z2a2 8 145 6

x 1 x 2 x 3 -x 2

x 1 x 6 x 7 x 8 0 ] g1f1s1c1t12R2u13Z2a2 126 146 6

x 1 x 2 x 3 -x 2 x 5 x 6 -x 3 x 6

x 9 ] g1f1s1c1t10R2u10Z1a2 144 147 6

x 1 x 2 x 3 -x 2

x 5 x 6

x 3 -x 6

x 9 ] g1f1s1c1t11R2u11Z1a2 144 148 6

x 1 x 2 x 3 0 0 0

x 7 x 8

x 9 ] g1f1s1c1t5R3u12Z2a2 1536 149 6

x 1 x 2 x 3 x 2

x 5 x 6 -x 3 -x 6

x 9 ] g1f1s1c1t3R2u19Z1a2 358 150 6

x 1 x 2 x 3 x 2

x 5 x 6 -x 3

x 8

x 1 ] g2f1s1c1t5R2u10Z2a2 12 151 6 x 1 x 2 x 3 -x 2 0 x 6

x 7 x 8

x 9 ] g1f1s1c2t10R2u1Z2a2 48 166 7

x 1 x 2 x 3 -x 2

x 1 x 6 x 7 x 8

x 9 ] g1f1s1c2t10R2u11Z1a2 1104 167 7

x 1 x 2 x 3 -x 2 x 5 x 6 -x 3 x 8

x 9 ] g1f1s1c1t10R2u10Z2a2 32 168 7

x 1 x 2 x 3 -x 2

x 5 x 6

x 7 -x 6

x 9 ] g1f1s1c1t11R2u11Z2a2 32 169 7

x 1 x 2 x 3 x 2

x 5 x 6 -x 3 x 8

x 9 ] g2f2s1c1t5R2u10Z2a2 12 170 7

x 1 x 2 x 3 x 4 0 x 6 -x 3 x 8

x 9 ] g1f2s1c1t12R2u1Z2a2 42 171 7

x 1 x 2 x 3 x 4 0 x 6

x 7 0

x 9 ] g1f1s2c1t10R2u19Z2a2 168 172 7

x 1 x 2 x 3 x 4 x 5 0

x 7 x 8 0 ] g1f1s2c1t10R2u11Z2a2 120 173 7

x 1 x 2 x 3 x 4

x 5 x 6 -x 3 -x 6

x 9 ] g1f1s1c1t3R2u19Z2a2 104 174 7

x 1 x 2 x 3 x 4

x 5 x 6 -x 3 x 8 0 ] g2f1s1c1t10R2u13Z2a2 32 175 7

x 1 x 2 x 3 x 4

x 5 x 6 -x 3

x 8

x 1 ] g2f1s1c1t10R2u1Z2a2 262 176 8 0 x 2 x 3 x 4 x 5 x 6 x 7 x 8

x 9 ] g1f1s1c2t11R2u19Z2a2 5220 177 8

x 1 x 2 x 3 -x 2

x 5 x 6 x 7 x 8

x 9 ] g1f1s1c2t10R2u10Z1a2 1232 178 8

x 1 x 2 x 3 x 2 x 5 x 6 x 7 x 8

x 9 ] g1f1s1c2t3R2u19Z1a2 1564 179 8

x 1 x 2 x 3 x 4 -x 1 x 6 x 7

x 8

x 9 ] g1f1s1c2t9R3u19Z2a2 96 180 8

x 1 x 2 x 3 x 4 0 x 6

x 7 x 8

x 9 ] g1f1s1c2t10R2u19Z2a2 1104 181 8

x 1 x 2 x 3 x 4 x 1 x 6 x 7 x 8

x 9 ] g1f1s1c2t10R2u11Z2a2 384 182 8

x 1 x 2 x 3 x 4

x 5 x 6 -x 3 x 8

x 9 ] g2f1s1c1t10R2u10Z1a2 774 183 8

x 1 x 2 x 3 x 4 x 5 x 6 x 3 x 8

x 9 ] g2f1s1c1t11R2u11Z1a2 288 184 8

x 1 x 2 x 3 x 4 x 5 x 6

x 7 -x 6

x 9 ] g1f1s2c1t11R2u11Z1a2 352 185 8

x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 6

x 9 ] g1f1s2c1t10R2u10Z1a2 144 186 8

x 1 x 2 x 3 x 4 x 5 x 6 x 7

x 8 -x 1 ] g2f1s1c1t5R3u11Z2a2 32 187 8

x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 0 ] g1f1s2c1t12R2u13Z2a2 1078 188 8

x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8

x 1 ] g2f1s1c1t10R2u19Z2a2 128

  F T April 23, 2001, 5:10pm D R A F T

  FIG. 1. Stereo framework

FIG. 2 .

 2 FIG. 2. The para-perspective projection

FIG. 3 .

 3 FIG. 3. The orthographic projection

  F T April 23, 2001, 5:10pm D R A F T

3. 1 . 2 .

 12 The parameter D R A F T April 23, 2001, 5:10pm D R A F T

  For each molecular case, D R A F T April 23, 2001, 5:10pm D R A F T = u 2 = 0, u 1 = 1 axis k y-axis T2 t = t 0 t 1 t 2 ] T translation u6 u 0 = 0, u 1 = 1axis ? x-axis t1 t 1 = t 2 = 0, t 0 = 1 trans. k x-axis u7 u 2 = 0, u 1 = 1 axis ? z-axis t2 t 1 = 0, t 0 = 1 trans. ? y-axis u8 u 1 = 1 general case t3 t 2 = 0, t 0 = 1 trans. ? z-axisu9 u 0 = u 1 = 0, u 2 = 1axis k z-axis t4 t 0 = 1 general trans. u10 u 0 = 0, u 2 = 1 axis ? x-axis t5 t 0 = t 2 = 0, t 1 = 1 trans. k y-axis u11 u 1 = 0, u 2 = 1 axis ? y-axis t6 t 0 = 0, t 1 = 1 trans. ? x-axis u12 u 2 = 1 general case t7 t 2 = 0, t 1 = 1 trans. ? z-axis u13 u 0 = u 1 = 0, u 2 = 1 axis k z-axis t8 t 1 = 1 general trans. u14 u 0 = 0, u 2 = 1 axis ? x-axis t9 t 0 = t 1 = 0, t 2 = 1 trans. k z-axis u15 u 1 = 0, u 2 = 1 axis ? y-axis t10 t 0 = 0, t 2 = 1 trans. ? x-axis u16 u 2 = 1 general case t11 t 1 = 0, t 2 = 1 trans. ? y-axis u17 u 1 = u 2 = 0, u 0 = 1 axis k x-axis t12 t 2 = 1 general trans. u18 u 1 = 0, u 0 = 1 axis ? y-axis D1 t:_t = 0 trans. ? known axis u19 u 2 = 0, u 0 = 1 axis ? z-axis D2 t ^_t = 0 trans. k known axis u20 u 0 = 1 general case D3 no relation u21 u 1 = u 2 = 0, u 0 = 1 axis k x-axis Z1 t:u = 0 trans. ? rotat. axis u22 u 1 = 0, u 0 = 1 axis ? F T April 23, 2001, 5:10pm D R A F T

3. 5 .

 5 D R A F T April 23, 2001, 5:10pm D R A F T Fundamental and homographic matrices

  F T April 23, 2001, 5:10pm D R A F T

the Akaike 1 ]FIG. 4 .

 14 FIG.4. Set of cases that generates the same matrix form. The central column shows an example of homography matrix form (number 19 in the table from Appendix A).

method 20 ]

 20 in order to minimize the distance between a 2D point m 1 and its D R A F T April 23, 2001, 5:10pm D R A F T projected estimation H m 2 : the last line of the H matrix and m 1 and m 2 are normalized.To deal with cases with di erent degrees of freedom, we use an appropriate Akaike criterion 1].

FIG. 5 .FIG. 6 .

 56 FIG. 5. Frames 1, 2 and 8 of the video sequence. The robotic system performs a rotation around the optical axis.

D

  R A F T April 23, 2001, 5:10pm D R A F T

TABLE Particular

 Particular

	# p 1 1 2 1 3 1 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 21 2 22 3 23 3 24 3 25 3 26 3 27 3 28 3 29 3 30 3 31 3 32 3 33 3 34 3 35 3 36 3 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 3 48 3 49 3 50 3 51 3 52 3 53 3 54 4 55 4 56 4 57 4 58 4 59 4 60 4 61 4 62 4 63 4 64 4 65 4 66 4 67 4 68 4 69 4 70 4 71 4 72 4 73 4 74 4 75 4 76 4 77 4 78 4 79 4 80 4 81 4 82 4 83 4 84 4 85 4 86 4 87 4 88 5 89 5 90 5 91 5 92 5 93 5 94 5 95 5 96 5 97 5 98 5 99 5 100 5 101 5 102 5 103 5 104 5 105 5 106 5 107 5 108 5 109 5 110 5 111 5 112 5 113 5 114 5 115 5 116 5 117 5 119 5 120 5 121 5 122 5 123 5 124 5 125 5 126 6 127 6 128 6 129 6 130 6 131 6 132 6 133 6 134 6 135 6 136 6 137 6 138 6 139 6 140 6 141 6 142 6 143 6	forms of fundamental matrices simpli ed form of fundamental matrices for example generated by: 0 0 0 x 6 0 -x 6 0 ] g1f1s1c1t1R1u24Z3a2 0 x 3 0 0 0 0 -x 3 0 0 ] g1f1s1c1t5R1u24Z3a2 0 x 2 0 0 0 -x 2 0 0 0 0 0 ] g1f1s1c1t9R1u24Z3a2 0 0 0 0 0 x 6 0 -x 6 x 9 ] g1f1s1c3t1R1u24Z3a2 0 0 0 0 0 x 6 0 x 8 0 ] g1f3s1c1t1R1u24Z3a2 0 0 0 0 0 x 6 x 7 -x 6 0 ] g1f1s1c1t1R2u13Z2a2 0 0 0 0 x 5 x 6 0 -x 6 x 5 ] g1f1s1c1t1R2u17Z1a2 0 0 0 x 4 0 x 6 0 -x 6 0 ] g1f1s1c1t1R2u1Z2a2 0 0 x 3 0 0 0 -x 3 0 x 9 ] g1f1s1c3t5R1u24Z3a2 0 0 x 3 0 0 0 -x 3 x 8 0 ] g1f1s1c1t5R2u13Z2a2 0 0 x 3 0 0 0 x 7 0 0 ] g1f1s2c1t5R1u24Z3a2 0 0 x 3 0 0 x 6 -x 3 -x 6 0 ] g1f1s1c1t3R1u24Z3a2 0 x 2 0 -x 2 0 x 6 0 -x 6 0 ] g1f1s1c1t11R1u24Z3a2 0 x 2 0 -x 2 0 x 6 0 0 0 ] g1f1s1c1t9R2u1Z2a2 0 x 2 0 -x 2 x 5 0 0 0 0 ] g2f3s1c1t9R1u24Z3a2 0 x 2 0 x 4 0 0 0 0 0 ] g1f1s2c1t9R1u24Z3a2 0 x 2 x 3 -x 2 0 0 -x 3 0 0 ] g1f1s1c1t10R1u24Z3a2 0 x 2 x 3 -x 2 0 0 0 0 0 ] g1f1s1c1t9R2u17Z2a2 0 x 2 x 3 0 0 0 -x 3 0 0 ] g1f1s1c1t5R2u17Z2a2 followed on next page n 24 4 5 12 6 16 396 16 2 8 4 17 8 24 4 3 4 12 8 x 1 0 x 3 0 0 0 -x 3 0 x 1 ] g1f1s1c1t5R2u1Z1a2 66 x 1 x 2 0 -x 2 x 1 0 0 0 0 ] g1f1s1c1t10R2u11Z1a2 198 0 0 0 0 0 x 6 0 x 8 x 9 ] g1f3s1c2t1R1u24Z3a2 12 0 0 0 0 0 x 6 x 7 -x 6 x 9 ] g1f1s1c2t1R2u13Z2a2 32 0 0 0 0 0 x 6 x 7 x 8 0 ] g1f1s1c1t1R3u13Z2a2 200 0 0 0 0 x 5 x 6 0 -x 6 x 9 ] g1f2s1c1t1R2u17Z1a2 396 0 0 0 0 x 5 x 6 x 7 -x 6 x 5 ] g1f1s1c1t1R2u11Z2a2 16 0 0 0 x 4 0 x 6 0 x 8 0 ] g1f1s1c1t1R3u1Z2a2 56 0 0 0 x 4 0 x 6 x 7 -x 6 0 ] g1f1s1c1t1R2u10Z2a2 32 0 0 0 x 4 x 5 x 6 0 -x 6 0 ] g2f1s1c1t1R2u1Z2a2 32 0 0 0 x 4 x 5 x 6 0 -x 6 x 5 ] g1f1s1c1t1R2u19Z2a2 16 0 0 x 3 0 0 0 -x 3 x 8 x 9 ] g1f1s1c2t5R2u13Z2a2 16 0 0 x 3 0 0 0 x 7 0 x 9 ] g1f1s2c2t5R1u24Z3a2 8 0 0 x 3 0 0 0 x 7 x 8 0 ] g1f1s1c1t5R3u13Z2a2 64 0 0 x 3 0 0 x 6 -x 3 -x 6 x 9 ] g1f1s1c3t3R1u24Z3a2 13 0 0 x 3 0 0 x 6 -x 3 x 8 0 ] g2f1s1c1t5R2u13Z2a2 22 0 0 x 3 0 0 x 6 x 7 -x 6 0 ] g1f1s2c1t3R1u24Z3a2 4 0 x 2 0 -x 2 0 x 6 0 x 8 0 ] g1f3s1c1t11R1u24Z3a2 2 0 x 2 0 -x 2 x 5 x 6 0 -x 6 0 ] g3f1s1c1t11R1u24Z3a2 4 0 x 2 0 -x 2 x 5 x 6 0 0 0 ] g2f3s1c1t9R2u1Z2a2 12 0 x 2 0 x 4 0 x 6 0 -x 6 0 ] g1f1s2c1t11R1u24Z3a2 4 0 x 2 0 x 4 0 x 6 0 0 0 ] g1f1s1c1t9R3u1Z2a2 60 0 x 2 0 x 4 x 5 0 0 0 0 ] g2f1s2c1t9R1u24Z3a2 6 0 x 2 x 3 -x 2 0 0 x 7 0 0 ] g1f3s1c1t10R1u24Z3a2 2 0 x 2 x 3 -x 2 0 x 6 -x 3 -x 6 0 ] g1f1s1c1t12R1u24Z3a2 40 0 x 2 x 3 -x 2 0 x 6 0 0 0 ] g1f1s1c1t9R2u19Z2a2 60 0 x 2 x 3 0 0 0 -x 3 x 8 0 ] g1f1s1c1t5R2u11Z2a2 0 x 2 x 3 0 0 0 x 7 0 0 ] g1f1s1c1t5R3u17Z2a2 0 x 2 x 3 x 4 0 0 0 0 0 ] g1f1s1c1t9R3u17Z2a2 x 1 0 x 3 0 0 0 -x 3 0 x 9 ] g1f2s1c1t5R2u1Z1a2 x 1 0 x 3 0 0 0 -x 3 x 8 x 1 ] g1f1s1c1t5R2u10Z2a2 x 1 x 2 0 -x 2 x 1 x 6 0 0 0 ] g1f1s1c1t9R2u10Z2a2 x 1 x 2 x 3 -x 2 x 1 0 0 0 0 ] g1f1s1c1t9R2u11Z2a2 x 1 x 2 x 3 0 0 0 -x 3 0 x 1 ] g1f1s1c1t5R2u19Z2a2 0 0 0 0 0 x 6 x 7 x 8 x 9 ] g1f1s1c2t1R3u13Z2a2 0 0 0 0 x 5 x 6 0 x 8 x 9 ] g1f1s1c2t1R2u17Z1a2 0 0 0 0 x 5 x 6 x 7 -x 6 x 9 ] g1f2s1c1t1R2u11Z2a2 0 0 0 0 x 5 x 6 x 7 x 8 x 5 ] g2f1s1c1t1R2u11Z2a2 0 0 0 x 4 0 x 6 x 7 x 8 0 ] g1f3s1c1t1R2u10Z2a2 0 0 0 x 4 x 5 x 6 0 -x 6 x 9 ] g1f2s1c1t1R2u19Z2a2 0 0 0 x 4 x 5 x 6 0 x 8 0 ] g2f1s1c1t1R3u1Z2a2 0 0 0 x 4 x 5 x 6 x 7 -x 6 x 5 ] g1f1s1c1t1R2u12Z2a2 0 0 x 3 0 0 0 x 7 x 8 x 9 ] g1f1s1c2t5R3u13Z2a2 0 0 x 3 0 0 x 6 -x 3 x 8 x 9 ] g2f1s1c2t5R2u13Z2a2 0 0 x 3 0 0 x 6 x 7 -x 6 x 9 ] g1f1s2c2t3R1u24Z3a2 0 0 x 3 0 0 x 6 x 7 x 8 0 ] g1f1s1c1t3R2u13Z2a2 0 x 2 0 -x 2 x 5 x 6 0 x 8 0 ] g2f3s1c1t11R1u24Z3a2 0 x 2 0 x 4 0 x 6 0 x 8 0 ] g1f1s1c1t11R2u1Z2a2 0 x 2 0 x 4 x 5 x 6 0 -x 6 0 ] g2f1s2c1t11R1u24Z3a2 0 x 2 0 x 4 x 5 x 6 0 0 0 ] g2f1s1c1t9R3u1Z2a2 0 x 2 x 3 -x 2 0 x 6 -x 3 -x 6 x 9 ] g1f3s1c2t9R1u24Z3a2 0 x 2 x 3 -x 2 x 5 x 6 0 -x 6 x 5 ] g1f1s1c1t11R2u17Z2a2 0 x 2 x 3 -x 2 x 5 x 6 0 0 0 ] g2f3s1c1t9R2u17Z2a2 0 x 2 x 3 0 0 0 x 7 x 8 0 ] g1f1s2c1t5R2u11Z2a2 0 x 2 x 3 0 x 5 x 6 -x 3 -x 6 0 ] g2f1s1c1t5R2u17Z2a2 0 x 2 x 3 0 x 5 x 6 -x 3 -x 6 x 5 ] g1f1s1c1t3R2u17Z2a2 0 x 2 x 3 x 4 0 0 x 7 0 0 ] g1f1s1c1t10R2u17Z2a2 0 x 2 x 3 x 4 0 x 6 0 0 0 ] g1f1s2c1t9R2u19Z2a2 x 1 0 x 3 0 0 0 -x 3 x 8 x 9 ] g1f2s1c1t5R2u10Z2a2 x 1 0 x 3 0 0 0 x 7 0 x 9 ] g1f1s1c2t5R2u1Z1a2 x 1 0 x 3 x 4 0 x 6 -x 3 -x 6 x 1 ] g1f1s1c1t3R2u1Z2a2 x 1 x 2 0 -x 2 x 1 x 6 x 7 -x 6 0 ] g1f1s1c1t11R2u13Z2a2 x 1 x 2 0 x 4 x 5 0 0 0 0 ] g1f1s2c1t10R2u11Z1a2 x 1 x 2 x 3 -x 2 0 x 6 -x 3 0 x 1 ] g1f1s1c1t10R2u1Z2a2 x 1 x 2 x 3 -x 2 x 1 0 -x 3 x 8 0 ] g1f1s1c1t10R2u13Z2a2 x 1 x 2 x 3 -x 2 x 1 x 6 0 0 0 ] g1f1s1c1t9R2u12Z2a2 x 1 x 2 x 3 0 0 0 -x 3 0 x 9 ] g1f2s1c1t5R2u19Z2a2 x 1 x 2 x 3 0 0 0 -x 3 x 8 x 1 ] g1f1s1c1t5R2u12Z2a2 0 0 0 0 x 5 x 6 x 7 x 8 x 9 ] g1f1s1c2t1R2u11Z2a2 0 0 0 x 4 0 x 6 x 7 x 8 x 9 ] g1f1s1c2t1R2u10Z2a2 0 0 0 x 4 x 5 x 6 0 x 8 x 9 ] g1f3s1c1t1R2u19Z2a2 0 0 0 x 4 x 5 x 6 x 7 -x 6 x 9 ] g1f2s1c1t1R2u12Z2a2 0 0 0 x 4 x 5 x 6 x 7 x 8 -x 5 ] g1f1s1c1t1R3u10Z2a2 0 0 0 x 4 x 5 x 6 x 7 x 8 0 ] g2f1s1c1t1R2u10Z2a2 0 0 0 x 4 x 5 x 6 x 7 x 8 x 5 ] g1f1s1c1t1R3u11Z2a2 0 0 x 3 0 0 x 6 x 7 x 8 x 9 ] g1f1s1c2t3R2u13Z2a2 0 x 2 0 x 4 x 5 x 6 0 x 8 0 ] g2f1s1c1t11R2u1Z2a2 0 x 2 x 3 -x 2 0 x 6 -x 3 x 8 x 9 ] g1f1s1c2t9R2u1Z2a2 0 x 2 x 3 -x 2 0 x 6 x 7 -x 6 x 9 ] g1f1s1c2t9R2u17Z2a2 0 x 2 x 3 -x 2 0 x 6 x 7 x 8 0 ] g1f3s1c1t12R1u24Z3a2 0 x 2 x 3 -x 2 x 5 x 6 -x 3 x 8 0 ] g3f1s1c1t10R1u24Z3a2 0 x 2 x 3 -x 2 x 5 x 6 0 -x 6 x 9 ] g1f2s1c1t11R2u17Z2a2 0 x 2 x 3 -x 2 x 5 x 6 0 x 8 x 5 ] g2f1s1c1t11R2u17Z2a2 0 x 2 x 3 0 0 0 x 7 x 8 x 9 ] g1f1s1c2t5R2u11Z2a2 0 x 2 x 3 0 x 5 x 6 -x 3 -x 6 x 9 ] g1f2s1c1t3R2u17Z2a2 0 x 2 x 3 0 x 5 x 6 -x 3 x 8 0 ] g2f1s1c1t5R2u11Z2a2 0 x 2 x 3 0 x 5 x 6 x 7 -x 6 x 5 ] g1f1s1c1t3R3u17Z2a2 0 x 2 x 3 x 4 0 x 6 x 7 -x 6 0 ] g1f1s2c1t12R1u24Z3a2 0 x 2 x 3 x 4 x 5 x 6 0 -x 6 x 5 ] g1f1s1c1t11R3u17Z2a2 0 x 2 x 3 x 4 x 5 x 6 0 0 0 ] g2f1s1c1t9R3u17Z2a2 x 1 0 x 3 0 0 0 x 7 x 8 x 9 ] g1f1s1c2t5R2u10Z2a2 x 1 0 x 3 x 4 0 x 6 -x 3 -x 6 x 9 ] g1f2s1c1t3R2u1Z2a2 x 1 0 x 3 x 4 0 x 6 -x 3 x 8 x 1 ] g1f1s1c1t3R3u1Z2a2 x 1 x 2 0 -x 2 x 1 x 6 x 7 x 8 0 ] g1f1s1c1t11R3u13Z2a2 x 1 x 2 0 x 4 x 5 x 6 0 0 0 ] g1f1s2c1t9R2u10Z2a2 x 1 x 2 x 3 -x 2 0 x 6 -x 3 0 x 9 ] g1f2s1c1t10R2u1Z2a2 x 1 x 2 x 3 -x 2 x 1 0 x 7 x 8 0 ] g1f1s1c1t10R3u13Z2a2 x 1 x 2 x 3 0 0 0 -x 3 x 8 x 9 ] g1f2s1c1t5R2u12Z2a2 followed on next page 12 56 8 120 56 16 8 128 168 40 6 40 36 32 240 12 8 10 3 14 26 292 1176 64 96 32 24 48 240 368 12 8 36 16 8 990 16 8 1056 8 24 150 8 12 32 36 8 9 120 8 146 4 588 8 44 128 24 112 80 16 32 16 2772 400 8 24 24 8 66 60 64 16 x 1 x 2 x 3 0 0 0 x 7 0 x 9 ] g1f1s2c1t5R2u19Z2a2 32 x 1 x 2 x 3 0 0 0 x 7 x 8 -x 1 ] g1f1s1c1t5R3u11Z2a2 16 x 1 x 2 x 3 0 0 0 x 7 x 8 x 1 ] g1f1s1c1t5R3u10Z2a2 32 x 1 x 2 x 3 x 2 x 5 x 6 -x 3 -x 6 x 1 ] g2f1s1c1t5R2u1Z1a2 70 x 1 x 2 x 3 x 4 -x 1 x 6 0 0 0 ] g1f1s1c1t9R3u19Z2a2 48 x 1 x 2 x 3 x 4 0 x 6 -x 3 0 x 1 ] g1f1s1c1t10R3u1Z2a2 16 x 1 x 2 x 3 x 4 x 1 x 6 0 0 0 ] g1f1s1c1t9R3u10Z2a2 96 x 1 x 2 x 3 x 4 x 5 0 0 0 0 ] g1f1s2c1t9R2u11Z2a2 24 0 0 0 x 4 x 5 x 6 x 7 x 8 x 9 ] g1f1s1c1t1R3u12Z2a2 5160 0 x 2 x 3 -x 2 0 x 6 x 7 x 8 x 9 ] g1f1s1c2t9R2u19Z2a2 199 0 x 2 x 3 -x 2 x 5 x 6 -x 3 x 8 x 9 ] g2f3s1c2t11R1u24Z3a2 34 0 x 2 x 3 -x 2 x 5 x 6 0 x 8 x 9 ] g1f3s1c1t11R2u17Z2a2 44 0 x 2 x 3 -x 2 x 5 x 6 x 7 x 8 0 ] g2f3s1c1t10R1u24Z3a2 10 0 x 2 x 3 0 x 5 x 6 -x 3 x 8 x 9 ] g3f1s1c1t3R2u17Z2a2 8 0 x 2 x 3 0 x 5 x 6 x 7 -x 6 x 9 ] g1f2s1c1t3R3u17Z2a2 40 0 x 2 x 3 0 x 5 x 6 x 7 x 8 0 ] g2f1s1c1t5R3u17Z2a2 192 0 x 2 x 3 0 x 5 x 6 x 7 x 8 x 5 ] g1f1s1c1t3R2u11Z2a2 32 0 x 2 x 3 x 4 0 x 6 x 7 x 8 0 ] g1f3s2c1t12R1u24Z3a2 3 0 x 2 x 3 x 4 x 5 x 6 0 -x 6 x 9 ] g1f2s1c1t11R3u17Z2a2 40 0 x 2 x 3 x 4 x 5 x 6 0 x 8 x 5 ] g1f1s1c1t11R2u19Z2a2 32 0 x 2 x 3 x 4 x 5 x 6 x 7 -x 6 x 5 ] g1f1s1c1t12R2u17Z2a2 84 x 1 0 x 3 x 4 0 x 6 -x 3 x 8 x 9 ] g1f2s1c1t3R3u1Z2a2 16 x 1 0 x 3 x 4 0 x 6 x 7 -x 6 x 9 ] g1f1s2c1t3R2u1Z2a2 16 x 1 0 x 3 x 4 0 x 6 x 7 -x 6 x 9 ] g1f2s2c1t6R2u5Z3a2 16 x 1 x 2 0 x 4 x 1 x 6 x 7 x 8 0 ] g1f1s1c1t11R2u10Z2a2 48 x 1 x 2 0 x 4
	D R A F T D R A F T	April 23, 2001, 5:10pm April 23, 2001, 5:10pm	D R A F T D R A F T

APPENDIX C

Details on the computations of paragraphs 3.4 and 3.5.

Here we denote by the AND symbol and by brackets ] an interval (unix-like notation). For example, p1g 1-2] p2g3 represents the set of the 3 cases: p1g1,

that is 117 cases. And from the extrinsic parameters part :

that is 21709 cases, leading to a total of 2539953 particular cases. This is approximately 100 times less than previously determined.

Continuing on paragraph 3.5, the homographic relation cases are :

where :


Diego A Tobon-Mejia

Kamal Medjaher

Noureddine Zerhouni

The ISO 13381-1 Standard's Failure Prognostics Process Through an Example

Industrial failure prognostics can be considered as the key process of any condition-based maintenance solution. However, contrary to fault diagnostics which is a mature research and industrial work, failure prognostics is a new field for which few applications exist. In the last decade, the interest for this activity has led to some open and industrial standards where the main objective is to provide users with a guidelines allowing them to perform failure prognostics for a large class of industrial systems. However, these standards, rightly, do not emphasize on any particular example to illustrate their content. The present paper aims at explaining the process of failure prognostics, presented in the standard ISO 13381-1, through an electromechanical example. The purpose is to help beginner researchers in the field of industrial failure prognostics to assimilate the main tasks of the process proposed by the standard. The prognostics process is chosen because it represents the key task among the rest of topics proposed and published by the standard. Thus, the comprehension of this part is important to develop prognostics methods and algorithms based on the solid recommendations given by the international organization for standardization.

I. INTRODUCTION

The need of reducing maintenance costs, improving the availability and reliability, and reducing or eliminating human and environmental accidents is nowadays a deep wish of any industrial company. To reach these objectives, it is necessary to adopt an appropriate maintenance strategy among the existing ones. Indeed, maintenance can be curative or preventive. For the last case, maintenance tasks are either planned in advance for the systematic one or achieved depending on the real state of the system, which is the case for the Condition-Based Maintenance (CBM). In this maintenance policy [START_REF] Andrew | A review on machinery diagnostics and prognostics implementing condition-based maintenance[END_REF][START_REF] Vachtsevanos | Intelligent Fault Diagnosis and Prognosis for Engineering Systems[END_REF] the system is monitored by a set of sensors which allow to track its state and decide whether a maintenance action is needed or not. To help performing this, failure prognostics seems to be the convenient process that allows to estimate the Remaining Useful Life (RUL) of the system and thus taking appropriate decisions. Contrary to fault detection and isolation (FDI) or fault diagnostics, for which many research and application works are done, failure prognostics research activities are at their infancy stage [START_REF] Andrew | A review on machinery diagnostics and prognostics implementing condition-based maintenance[END_REF][START_REF] Venkatasubramanian | Prognostic and diagnostic monitoring of complex systems for product lifecycle management: Challenges and opportunities[END_REF]. However, this field is gaining more and more interest from both industrial and research communities. During the last decade, many definitions, methods and tools are proposed in the field of failure prognostics, but this is still an open research area [START_REF] Heng | Rotating machinery prognostics: State of the art, challenges and opportunities[END_REF]. The recent abundance of literature regarding failure prognostics may be a positive point, but it can also be a source of confusion, especially for those who are beginning to work in this domain. The role of any standard, open or not, is then to provide users with some guidelines to help them to accomplish their expected missions. Thus, in the open standard [START_REF] Thurston | An open standard for web-based condition-based maintenance systems[END_REF] one can find some of the basic elements that should be fulfilled in order to perform failure prognostics. In the same way, the standard ISO 13381-1 [START_REF] Iso | Condition monitoring and diagnostics of machinesprognostics -Part 1: General guidelines[END_REF] defines failure prognostics, details the steps of the prognostics process, gives indications on the monitoring system and on how to estimate the confidence interval associated with the calculated RUL and proposes some mathematical tools which can be used to model the degradation. However, as for any standard, it does not focus on a particular application, neither gives any illustrative example.

The present paper aims at explaining a part of what is published in the standard ISO 13381-1, namely the failure prognostics process. Each step of the process will be progressively explained on an electromechanical example. Section 2 of the paper briefly summarizes the main points addressed in the standard. In section 3 the electromechanical example is presented, followed by the definition of the failure modes given in section 4. Section 5 is dedicated to the explanation of the prognostics process by using the example presented in the previous section. Finally, a conclusion is given at the end of the paper.

II STANDARD ISO 13381-1

There exists in the literature some discussions about prognostics in the framework of CBM open standards [START_REF] Thurston | An open standard for web-based condition-based maintenance systems[END_REF][START_REF] Lebold | Open standards for conditionbased maintenance and prognostic systems[END_REF][START_REF] Sheppard | IEEE standards for prognostics and health management[END_REF][START_REF]and Machinery Information Management Open Standards Alliance MIMOSA. Open systems architecture for condition-based maintenance OSA -CBM[END_REF] proposed by the OpenO&M initiative [START_REF] Openo&m | [END_REF] but in this paper only the one of the ISO is addressed. The standard published by the ISO deals with the main guidelines and aspects one has to take into account in order to perform failure prognostics on engineering systems. The standard gives the definition of prognostics, specifies the required types of data to consider, presents the concept and the process of prognostics along with all necessary parameters, descriptors and influence factors to consider in order to well estimate the remaining useful life and the associated confidence value of a given system. Note that the standard uses the terminology estimated time to failure (ETTF) instead to RUL. The document also indicates a set of mathematical models which can be used to model the degradation phenomena.

Among the topics presented in the standard, three main aspects can be pinpointed and deserve more attention, namely the required data, the general monitoring process and the prognostics process. In the following, only the failure prognostics process is discussed and illustrated on a simple academic example.

III SYSTEM DESCRIPTION

For the explanation of the generic prognostics process proposed by the standard, a degradation phenomenon in an oil pump is considered. Pumping systems were chosen because, in one hand, they are one of the most critical mechanical systems in the industry and, in the other hand they are frequently used in the validation of prognostics models. For example, in [START_REF] Dong | A segmental hidden semimarkov model (hsmm)-based diagnostics and prognostics framework and methodology[END_REF] oil pumps were used with different contamination levels to test and to validate the data-driven approach the authors have developed and which is based on Hidden Semi-Markov Models (HSMM). In [START_REF] Heng | Intelligent conditionbased prediction of machinery reliability[END_REF] the authors have used the condition and the event data of centrifugal pumps for validation too. Their model was based on a feed-forward neuronal network where training targets were the asset survival probabilities estimated using a variation of the Kaplan-Meier estimator and a degradationbased failure probability density function (pdf) estimator.

For the present paper, the considered example is shown in figure 1. The system is composed of three main components: one induction motor, one hydrostatic bearing and one centrifugal pump (the function of each component and the energy flow is explained below). The system is monitored by different sensors coupled with an acquisition system used to assess the actual condition of the system and to perform its health prognostics. The main components of the pumping system of figure 1 and their corresponding functions are explained hereafter.

Induction motor: this system converts the electric energy into a kinetic energy by the interaction of magnetic fields and current-carrying conductors. This device is supplied by an alternating current, and can be separated in two main parts: an outside stationary stator that has coils supplied with alternating current to produce a rotating magnetic field, and an inside rotor guided by bearings linked to the output shaft to generate a mechanical torque by the rotating field.

Hydrostatic bearing: solely supports the bearing's loads on a thin layer of liquid or gas. Hydrostatic bearings are frequently used in high load, high speed or high precision applications where ordinary ball bearings have short life or high noise and vibration. In our example this bearing is used to guide the shaft toward the pump and to avoid the shaft deflection.

Centrifugal pump: used to move liquids through a piping system. The fluid enters the pump impeller along or near the rotating axis (which is guided by bearings) and is accelerated by the impeller, radial flowing outward into a diffuser or volute chamber (casing), from where it exits into the downstream piping system. Here, the pump performs the expected or final activity "move a fluid at a constant flow rate and pressure".

Sensors: used to perform the prognostics and to assess the actual condition of the main components. Three types of sensors are used in the monitoring process: accelerometers which can capture the information contained in the vibration profile, pressure sensors that can monitor with confidence the refueling process in the pump and finally, an ohmmeter to measure the resistance of the stator coils. Table 1 presents the nomenclature of the used sensors and the monitored components.

The pumping system works under its nominal specifications: the flow rate, the speed and the pressure are assumed to be constant values during the time (it is supposed that the system is well controlled and without any external perturbation). The sensors used in the monitoring process are taken as inputs of suitable acquisition card which allows the data sampling at a constant rate and uses anti-aliasing filters at a correct frequency.

IV PROGNOSTICS INPUTS

The first step in building a prognostics system, as published in the ISO standard, is the identification of the set of failure modes (FM), their influence factors on each other and the detection measures (descriptors) that allow to track the evolution of the degradation. The international standard IEC 60812 [START_REF]Analysis techniques for system reliability -procedure for failure mode and effects analysis (FMEA)[END_REF] has presented a procedure named "Procedure for failure mode and effects analysis (FMECA)", which helps the identification of all the failure modes for a specific system, by the analysis of its subsystems and components. Also, the FMECA method classifies the FMs using risk priority numbers (RPN) that are calculated with three failure mode parameters: occurrence (Occ), detection (Det) and severity (Sev). So, the FMECA allows the definition of the appropriate detection method and measures to be used in the diagnostics as well as in the prognostics of the failure modes.

Concerning the pumping system, the results of the corresponding FMECA analysis are shown in tables 2 and 3. For this system, only eight FMs are considered and they are defined as critical. So, the quantification with the RPN was not necessary, because each FM can compromise the ended function. The critical components are: the two bearings and the stator in the electric motor, the oil in the hydrostatic bearing and the two bearings, the impeller and the seal in the centrifugal pump. To track the failure mode evolution, different descriptors were defined. Some of these descriptors were tested in the literature and have shown promising results. The failure modes and their corresponding descriptors are defined in the following paragraphs.

For the bearings failure, the descriptor to be used is the measure of the "health probability". This descriptor is based on wavelet packet decomposition and Hidden Markov Models (HMM) for tracking the severity of bearing faults. In this case, the diagnostics system estimates the probability that the current measures are generated by the normal condition HMM model. So, any decrease of this probability is considered as an indication of an incipient fault (see [START_REF] Ocak | Online tracking of bearing wear using wavelet packet decomposition and probabilistic modeling: A method for bearing prognostics[END_REF] for more details).

Abbreviation

Sensor For the stator in the electric motor, the descriptor used is the resistance, it can be measured by a combination of voltage and current measurements or simply by using an ohmmeter (which is the case in this paper) [START_REF] Vas | Parameter Estimation, Condition Monitoring, and Diagnosis of Electrical Machines[END_REF].

The oil degradation in the hydrostatic bearing can be tracked as suggested in [START_REF] Muszynska | Rotordynamics[END_REF] by monitoring the center alignment of the shaft. This measure represents the thickness of the oil film.

The cavitation in the pump which deteriorates the impeller by the implosion of the bubbles can be tracked by the acoustic emissions in the same way as proposed by Escaler [START_REF] Escaler | Cavitation monitoring of hydroturbines: Test in a francis turbine model[END_REF].

The leakage is monitored by measuring the differential pressure between the flow before and after the seal and assuming that the only component which can cause a leakage is the seal.

As this is presented in the standard, the initiation criteria of a failure mode must be defined by set of values which alerts the user about a failure mode initiation. For the pumping system, no numerical values were defined as this is considered as an hypothetical example. Moreover, the FMECA analysis sheet proposed for this example allows to record these values. The alarm value is highlighted in yellow in tables 2 and 3.

In the same way, the standard specifies the definition of other detection values for a failure mode, namely the alert and the trip (shut-down) values. The alert value is higher than the alarm value, but lower than trip value (see Eq. 1). The alert value represents an advanced state of degradation and informs the maintainer that a maintenance task should be defined to assess the real condition and to avoid the break down of the system. In the corresponding FMECA sheet, the space to register this value is also considered and must be defined if this example wants to be replaced by a practical one. The blue column in the FMECA sheet is there to indicate this value. For the alert value definition, several phenomena must be considered as proposed in the standard:

the confidence level of the prognostics, the future production requirements, the lead times of spare parts, the required maintenance planning, the work required to rectify the faults, and he trend extrapolation and projection.

alarm alert trip alert trip

(1)

The trip, or the shut-down value, specifies the value that the parameter/descriptor reaches when the component must be fixed without any exception. Normally, this value is lower than the real break value and can be understood as the security factor in strength of materials. This value can be defined from standards, manufacturer's guidelines or by experience. In the pumping system, the FMECA sheet contains also a column to take into account these values, (see the red colored column in tables 2 and 3).

V PROGNOSTICS PROCESS

In the same as the ISO, some researchers and industrials are aware of the importance of prognostics in the CBM policy and this pushed them to make some efforts in their standardization. For example, the cooperation between scientists and industrials has enabled the development of a standard platform to build a CBM software [START_REF]and Machinery Information Management Open Standards Alliance MIMOSA. Open systems architecture for condition-based maintenance OSA -CBM[END_REF], called "Open Systems Architecture for Condition-based Maintenance". In this platform the standardization of the prognostics process is discussed [START_REF] Lebold | Open standards for conditionbased maintenance and prognostic systems[END_REF]. The previous standards and the ISO standard, are consistent in different points, especially in the fact that the prognostics is a process which comes after the monitoring process. This is because the monitoring process is used to estimate the actual health state of the system and also to generate data which are useful for the prognostics process.

The ISO standard defines the prognostics as a sequential process (see figure 2) with four main steps:

1.

Pre-processing: at this step the system identifies all the existing failure modes, their relations, symptomsparameters -descriptors and determines the potential future failure modes.

2.

Existing failure mode prognostics process: a study of all existing failure modes is then performed, the severity and the Estimated Time To Failure (ETTF) are calculated.

3.

Future failure mode prognostics process: the most probable future modes, the influence factors between them and the existing modes are estimated. Also, the ETTF for the future failure modes is calculated.

4.

Post-action prognostics: in this step the prognostics system proposes the maintenance actions to be done in order to avoid, reduce or delay the failure mode effects. After this, a new prognostics is made by taking into account the suggested actions, and the confidence about the estimated time to failure is calculated. In the following, the pumping system presented previously is used to explain the main steps of the prognostics process.

Pre-processing

During this step the following operations are made:

1.

The first step deals with diagnostics to identify all the failure modes which exist at a present time in the pumping system. In our case a Hidden Markov Model can be made for each failure mode listed in the FMECA sheet as proposed in [START_REF] Kwan | A novel approach to fault diagnostics and prognostics[END_REF] to detect the existing failure modes. For the studied pumping system the result shown in figure 3 can be obtained. In this application example, the existing failures are:

Two growing outer race defects in the bearing 1 of the motor and in the bearing 2 of the pump. Both failure modes come from the past. They are in fact an evolved version of past failure modes. For this reason the diagnostics system places these failure modes in the past line.

Two new failure modes that the diagnostics system has identified at the present iteration time, by using the last monitored data of the descriptors D4 and D8. These failure modes are an oil degradation in the hydrostatic bearing and a leakage in the seal of the pumping system.

2.

The second step consists in the identification of the influence factors between the existing failure modes. To perform this operation the prognostics system can use the "effects on" column in the FMECA analysis (see tables 2 and 3) to find the relations between the FMs. Once this operation is performed for the pumping system, by using the diagnostic results obtained in the previous step and the FMECA analysis, the prognostics system is able to define the relations displayed with orange color in figure 4. Once the existing failure modes and their relations are identified, the system has to retrieve all the information available about these failure modes. In the pumping system, the FMECA analysis (table 2 and table 3) has different detection levels (alarm, alert, trip). The prognostics system must then retrieve this information to track the degradation. For example, for the descriptor "D1" which is used Table 2: Page 1 of the FMECA analysis Table 3: Page 2 of the FMECA analysis to track the outer race break, the system registers the initiation criteria value (alarm), the alert value, the trip value and the actual value as shown in figure 5. This operation must be made for all the descriptors of all the existing failure modes.

4.

The last step in the pre-processing process consists in determining the potential future failure modes, their initiation criteria and the failure definition set points. For example, in the pumping system the old maintenance histories data can be used to find the most probable future failure modes. For this, the prognostics system can proceed by similarity study and analysis (similar diagnosed failure modes with their associated monitoring values) on the previous recorded situations to find the potential future failure modes. The result of this step is shown in the green box of figure 6.

Existing failure modes prognostics process

During this step the following operations are made:

1. The first step of this process aims at identifying the actual condition of the overall system, and the severity of the existing failure modes. For this, the prognostics system will classify the failure modes from the most severe to less severe.

To perform this quantification, the system measures the distance between the actual descriptor value with its respective trip value, and the smallest distance defines the most sever failure mode. For example, in the pumping system if the prognostics system displays in the same window (using scales factors) the descriptors "D1" and "D4" which have the trends showed in the figure 7, the system concludes that the outer race break FM in the bearing 1 of the AC motor (M_B1_1) is more severe at the present time than the oil degradation FM in the hydrostatic bearing (HB). This is because the distance between its current value and its trip value is shorter than the descriptor "D4". 2. The next step is the time projection of the parameters/descriptors into the future. For this purpose, the standard presents projection and extrapolation as trending tools. The basic difference between trend extrapolation and trend projection is that projection requires the estimation of extrapolation curve is fitted only to the existing data. The projection is then more accurate than the extrapolation, if the system disposes enough information or is accurately modeled and captures all the failure modes behavior. Interested readers can refer to the reviews about several prognostics approaches and methods published in [START_REF] Andrew | A review on machinery diagnostics and prognostics implementing condition-based maintenance[END_REF] and in [START_REF] Pusey | An assessment of turbomachinery condition monitoring and failure prognosis technology[END_REF]. In the example of the pumping system, linear regression models coupled with past information can be used to project the descriptors as proposed in [START_REF] Li | Gas turbine performance prognostic for condition-based maintenance[END_REF] or in [START_REF] Wang | A similarity-based prognostics approach for remaining useful life estimation of engineered systems[END_REF]. For example for the descriptors "D1" and "D4" the system will trend a curve like the dotted lines shown in figure 8.

3. The subsequent step consists in a simple analysis of the projection curves. The prognostics system estimates when the projected parameter/descriptor reaches its respective trip value (failure), and estimates the difference between the actual time and the future failure time. This time difference is the estimated time to failure "ETTF". In the case of the pumping system, the prognostics model makes the intersection between the projected values and the trip value defined for all failure modes in the FMECA sheet and finds the shortest "ETTF". For example, in figure 8 the prognostics system projected the descriptors D1 and D4, and it is possible to see that the descriptor "D4" reaches first its trip value, whereas the descriptor "D1" does not reach its corresponding trip value. Then, the system will keep in memory the "ETTF HB" (green circle in figure 8) which is associated with the failure mode "HB" (oil degradation). 4. Finally, the prognostics process must assure that the projection is under the specified confidence level. In the pumping system, to calculate the confidence interval, it is possible to use for example the Monte Carlo method to take into account the variation of the parameters' values as in [START_REF] Luo | Model-based prognostic techniques applied to a suspension system[END_REF] to estimate the ETTF of a suspension system.

Future failure modes prognostics process 1. The first operation in this step is the determination of the most probable future failure modes. To perform this operation the prognostics system can use the initiation criteria values and the projections presented in the previous subsection. The system will make the intersection between the "alarm" values of the potential failure modes obtained in the step 4 of subsection "Pre-processing". Then the failure modes which drop in this class will be retained as the most probable future failure modes, whereas the others will be removed for the current iteration. In the pumping system it is possible to find a situation as presented in figure 9, where the descriptor projection does not reach the initiation criteria of the short-circuit in the stator (M_S). So, this failure mode is then removed and only three future failure modes are retained and handled, as shown in the red box of figure 9. 2. The next step is similar to the step 2 of subsection "Pre-processing" where the influence factors were estimated.

Here the system estimates the influence factor between all the failure modes (existing and future ones). For the pumping system, knowing the existing and the future failure modes calculated in the previous step, the system can use the information indicated in the FMECA sheet ("effect on" column) to determine the influence between all the failure modes. Figure 10 shows the influence factors in the studied pumping system, the orange arrows represent the influence between the existing failure modes, the red arrows represent the influence between future failure modes and the green arrows identify the relations between existing and future failure modes. Some arrows are bidirectional meaning that degradation in one component may affect directly the other and vice versa. This phenomenon is important and has to be taken into account because a failure mode which evolves faster and which is near the trip value will degrade the related components too.

3. This step is similar to steps 2 to 4 presented in subsection "Existing failure modes prognostics process", in where the system estimates the ETTF for the future failure modes. To do this, the prognostics system will verify the projections by considering the influence factors, the trip values and the actual descriptor value.After this, the system will estimate and retain the shortest future ETTF. In the pumping system some descriptors of the probable future failure mode obtained at step 1 of subsection "Future failure modes prognosis process" may reach their trip values. For example the descriptor "D7" shown in figure 11 and which tracks the degradation in the impeller of the pump will reach the failure state. So, an ETTF can be estimated and corresponds to the shortest future ETTF which must be stored in memory. For the case presented in figure 11 the "ETTF P_I" will be retained (green circle in figure 11). Post-action prognostics 1. Here, the system will identify one or more maintenance actions which may delay, stop or eliminate the progression of the critical existing failure mode and prevent the initiation of future failure modes. For the pumping system, these actions are recommended in the FMECA sheet. From the previous steps two critical failure modes with short ETTF were identified, they are the "ETTF_HB" and the "ETTF P_I".

The prognostics system will then suggest to perform an oil renewal and a pump inspection or an impeller replacement. These actions are aimed at avoiding the failure modes and eliminating their influence on the other failure modes as shown in figure 12.

Figure 11: ETTF fo the future FMs. 2. At this step the system will re-estimate the existing and the future failure modes by taking into account the proposed maintenance actions. For the pumping system example, after having done the proposed actions the prognostics system will store all the failure modes (future and existing) in memory. They will then be used in the next iteration as existing failure modes and their presence will be validated or invalidated by the diagnostics system.

3. Finally, the prognostics system will present to the maintainer the results, which are: the critical FMs and their corresponding ETTFs, the maintenance actions, the confidence values and the validity conditions. The standard suggests many error sources which can affect the accuracy of the calculated ETTFs and confidence values. For example, confidence values can be completely different for each descriptor because they depend on many parameters, like the quality and the quantity of available information, the nature of the database, the data acquisition and processing methods, etc. For the pumping system example, the prognostics system will present to the maintainer two messages, namely: a) An oil degradation is present in the hydrostatic bearing, the ETTF is "ETTF_HB" with a confidence value of "Y" %, an oil replacement is recommended. This prognosis is valid under the assumption that the production plan is the "Production" plan and the weather conditions will stay as specified in the "Weather" file. b) The actual conditions and the monitoring history advise the possibility of cavitation which will degrade the impeller; a pump inspection or an impeller replacement is then recommended with an associated confidence value of "R" %. This prognosis result is valid under the assumption that the production plan is the "Production" plan and the weather conditions will stay as specified in the "Weather" file.

Conclusions

Many interesting topics are presented in the ISO 13381-1, such as the condition monitoring flow chart detailing the prognostics process, the prognostics basic concepts and the influence factors. The prognostics process presented in the standard has retained the attention because it can be considered as the key process of any CBM solution. The generic process presented by the standard may allow the users to understand, develop and make failure prognostics if the appropiated means are used.

The example presented in this paper helps the new users interested in industrial prognostics to understand in an easy way the process suggested by the standard. Indeed, the prognostics process as presented by the ISO is ambiguous in many topics like for example the concept of existing failure modes and the evolution of past failure modes, which are not explained in detail. Thus, new users can have problems in understanding the prognostics process.

The work presented in this paper aimed at explaining as well as possible the prognostics process of the ISO 13381-1 standard through an example. However, the paper did not give any numerical quantification of this ETTF or about the corresponding confidence interval. This paper did not also use any specific modeling or projection mathematical tool, because an hypothetical example was used, but some references about appropriated projections methods are given. The choice of appropriate modeling and projection tools for RUL (or ETTF) and confidence interval estimation depends in fact on the type of the available data, the degradation mechanisms, the the complexity of the system, the prognostics precision, and on many other environmental factors. All these points are some of challenges that deserve to be developed in the future works.

Figure 1 :

 1 Figure 1: Pumping System.

Figure 2 :

 2 Figure 2: Pumping System.

Figure 3 :

 3 Figure 3: Pumping System.

Figure 4 :

 4 Figure 4: Existing relations between the failure modes

Figure 5 :

 5 Figure 5: Existing failure mode values.

Figure 6 :

 6 Figure 6: Probable failure mode values.

Figure 7 :

 7 Figure 7: Severity of existing failure modes.

Figure 8 :

 8 Figure 8: Parameters/descriptors projection and ETTF.

Figure 9 :

 9 Figure 9: Most probable failure mode estimation.

Figure 10 :

 10 Figure 10: Influence factors between all the FMs.

Figure 12 :

 12 Figure 12: Maintenance actions and their effects on the FMs.

Table 1 :

 1 Sensors, abbreviations and associated monitored componen

		type	Component	Subsystem	System
	Acc B1	Accelerometer	Bearing 1
	Acc B2	Accelerometer	Bearing 2	AC Motor
	Ohm	Ohmeter	Stator
	Acc HX Acc HY Acc BP1	Accelerometer Accelerometer Accelerometer	Shaft Shaft Bearing 1 pump	Hydrostatic bearing	Pumping System
	Acc BP2	Accelerometer	Bearing 1 pump
	Acc PI	Accelerometer	Impeller pump	Centrifugal pump
	PS1 PS2	Pressure Pressure	Seal

Biography

Diego A. TOBON-MEJIA was born in Medellin, Colombia, on February 16, 1985. He received the B.Sc. and S.M., both in 2008, from the National Engineering School in Metz (France) and the EAFIT University (Colombia). He made a specialization in his last school year in research and development in "Design, industrialisation and innovation" supported by the Paul Verlaine University, the ENSAM and the ENIM, all in Metz (France).

In his last year of Master he developed a decision support application based in fuzzy logic and the PERT method to assess the failure mode hazard in a Francis turbine that works in a hydroelectric power station in Colombia, to ensure the systems availability and security. Actually he performs his doctoral studies at Franche-Comté University, in Besançon (France) sponsored by Alstom Transport where he his a research engineer. He is engaged in research on rotating machinery failure prognostic at the FEMTO-ST institute and Alstom transport.

Diego A. TOBON-MEJIA, was honored in 2002 with the "Excellence scholarship" from the "EEPP de Medellin" (Medelln Public Enterprises) to perform his studies in Colombia. In 2006 he was honored by the The French Ministry of Foreign affairs with the "Eiffel Excellence scholarship" to continue his studies in France.

Dr. Kamal MEDJAHER is an associate Professor at the French high school of mechanics and micro-techniques in Besançon since September 2006, where he teaches control and fault diagnostics and prognostics. After an engineering degree in electronic, he has got his MS in control and industrial computing in 2002 at the "Ecole Centrale de Lille" and his PhD in 2005 in the same field from the University of Lille 1. Before joining his current position, Dr. Medjaher has mainly worked in the field of Fault Detection and Isolation (FDI). He has particularly used the bond graph formalism to derive mathematical models of physical systems and to generate Analytical Redundancy Relations (ARRs) and residuals, which are then used to detect and to isolate possible faults on the system.

Since September 2006, Dr. Medjaher leads research works in the field of failure prognostics and uses artificial intelligent tools, particularly Dynamic Bayesian Networks (DBNs). Dr.

Medjaher co-authored eight published journal papers and more than ten refereed conference papers.

Professor Noureddine ZERHOUNI received his engineer degree from National Engineers and Technicians School of Algiers (ENITA) in 1985. After a short period in industry as engineer, he received his Ph.D. Degree in Automatic Control from the Grenoble National Polytechnic Institute in 1991. In September 1991, he joined the National Engineering School of Belfort (ENIB) as Associate Professor. At this time, his main research activity was concerned with modelling, analysis and control of manufacturing systems.

Since September 1999, Noureddine Zerhouni is Professor at the national high school of mechanics and microtechniques of Besançon. He founded and is responsible of the research group "Design and maintenance of mechatronic systems" (COSMI) of AS2M