Singularities for motion and calibration*.

Introduction

This paper is a part of an ongoing work on the analysis of specific constraints about the scene, the model of camera and on displacements when estimating structure and motion in non calibrated video sequences. The goal, here, is to obtained as much as possible information on auto-calibration, displacement and scene structure (geometric objects, relations, 3D structure). This study extends [VL96] by introducing more cases with the help of automatic code generation. It will allow, in a near future, the introduction of constraints of any kind.

State of the art

The analysis of motion in the case of an uncalibrated monocular images sequence has already been developed by several authors, (i) considering point and/or line correspondences or correspondences between planar patches, (ii) using either a discrete or a continuous representation of the rigid displacement, (iii) between two or more frames [MF92], [VF96], [F95], [H94], [S94].
These studies are motivated by the fact that we must not consider an active visual system is calibrated. However, in the general case, it is not possible to self-calibrate the camera when zooming or modifying the intrinsic calibration parameters [VF96], while some of these equations are subject to some unrecoverable singularities [H94], [ZM94].
Considering this fact, several authors have re-analyzed the problem, considering specific displacements or camera models [VF96], [TZ95], [EV96], [S97a], [S97b]. More specifically: pure rotations [H94b], [S95], pure translations [SN94], [VGM94], focal length variation [PVG95], [EZ96], movements plans [ZF94], [BZ94], fixed axis rotations [BR95], [V94], [VF95], simplified camera models [VL96], [LV96], [CH94], or the planar case, extensively studied by several authors as reviewed in [VZ95] in the uncalibrated case.
For instance, fixed axis rotations of known angles or pure rotations [V94] allow to estimate the calibration parameters with their uncertainty. Furthermore, we can derive which kind of displacements are optimal with respect to the estimation problem.
Collecting all this information and considering a suitable statistical framework as in [TZ95], [VZ95], [ZD94], it is then possible to infer which kind of displacement or camera model will increase at most the information (usually represented by the inverse of a covariance matrix) on the scene geometry, object kinematics and calibration parameters.

Reviewing the theory of motion when no calibration.

Setting the equations

Camera model and frame of reference




In this model, we distinguish two kinds of parameters:


• Modal parameters: and
• Intrinsic parameters: u0, v0 and
The modal parameters determine the model of projection:


Pure perspective projection	1	1
Weak perspective projection (i.e. affine or orthographic)	0	0
Para-perspective projection	1	0

Representation of rigid displacement

We consider motion of rigid objects and the ego-motion of the camera.
It means that the tokens in the scene are undergoing a rigid displacement parameterized by a rotation matrix R, which can be expressed as:
where r=[r0 r1 r2]T

and a translation vector t = [t0 t1 t2]T

Equations in the general case

Considering two consecutive frames:

which can be also written as:



and interpreted as a bilinear form in m and m', so that we can express this result in a more familiar form, using a generalization of the fundamental matrix:



This is easily generalizable to N views.

The particular cases

We will focus, in this paper, on the cases concerning the model of camera and the displacements. The cases concerning the particularities of the scene will not be examined here, except the planar case; we will suppose the points in a general configuration (coplanar or non-coplanar).

Particular cases in term of model of camera

We consider here modal and intrinsic parameters. Modal parameters induce three cases, as seen previously. Concerning intrinsic parameters, several cases have to be considered:
• which allows to represent the fact that the retina might not be orthogonal with respect to the optical axis and can be approximated to zero or considered as a fixed parameter
• and the focal lengths:
  • and are fixed
  • and are fixed and known
  • the ratio between by is fixed and precalibrated
  • and approximed to their 1st order
• and the coordinates of the principal point c:
  • and fixed but unknowns
  • and fixed but knowns (for example, fixed at the center of the image)
  • and approximed to their 1st order

Particular cases in term of displacement of the camera (or objects in the scene)

Let us enumerate the different motion constraints:
• Continuous motion - discrete motion: In a video sequence, the displacement between two frames can be small enough with respect to the video cadence and be approximated to the first order, second order, ... which concerns only the rotation component of the displacement:
  
• Other cases :
  • rotation matrix R: one or more component of r vanish r0 = 0 and / or r1 = 0 and / or r2 = 0
  • translation vector t: one or more component of t vanishes:
    • (t0 = 0) and/or (t1 = 0) and/or (t1 = 0)
  • parallelism: r // t / r = t
  • orthogonality: r t r.t = 0

Particular case: the case of a pure rotation and the planar case

In the We introduce in this case the normale to the plane n = [n0 n1 n2]T and associate particular cases:
• one or more component of n vanishes:
  (n0 = 0) and / or (n1 = 0) and / or (n2 = 0)
• relations with translation or rotation vectors:
  • n // t
  • n // r
  • n t
  • n r

Constraints: compatibility - redondance - consistence

The set of all constraints is made of atomic constraints, as seen previously, and molecular constraints, logical "AND" combinations of atomic constraints, excepted the non-possibles constraints.
We have to note that some combinations (by example, non-zero translation, parallelism and orthogonality) are in contradiction.
In other hand, if we compare:
(r0 = 0) (t r) and (t1 = 0) (t2 = 0) (t r) we observe that we obtain the same constraint. This shows the redondance of molecular constraints.
The particular cases are the molecular constraints which verify the following properties, aiming to have a physical meaning:
• an unique model of camera have to be chosen
• an unique mode of rotation have to be chosen
• the translation must not be zero (we fixed one component to 1)
• the principal point is in the image

In other hand, the constraints give us not necessary enough information. In this case, we can focus only on what is determinable or add enough other constraints to solve the whole problem.

Using particular cases

• to determine the model of projection of the camera
• to determine the calibration parameters (if they are constants)
• to determine the type of displacement and, if possible, the characteristics (direction of translation, axis of rotation, angle of rotation)
• eventually, to segment the points in sets of rigidly bind points

Implementation

Input / Output of the algorithm

We have, as input:
• two images
• a list of constraints
And will process, as output:
• coherence or non-coherence of constraints (the non-coherence stops the process at this step)
• an adequation coefficient of the data to the constraints
• the values of parameters, unknown in input

Initializations

Feature points corresponding to high curvature points are extracted from each image. In our application, we use the ``Harris'' corner detector [HS88], and as reported in [ZD94b], we perform a correlation operation and select those locations for which the correlation score is high. We may find both bad locations and false matches, or matches which do not correspond to the quantity we want to estimate, because they belongs to moving objects.
When considering an image sequence, each point is tracked from the first to the last view and then the trajectory is interpolated using a polynomial model in order to obtain a sub-pixel mechanism of localization of the points.

Algorithm

• Constraints choice (by an user or automatically)
• Test on the constraints compatibility. If not, go back to previous step.
• Determination of bound and free parameters - Reduced equation.
• Minimization from the adequation criterion with varying free parameters.

Criterion, computation of residual

As discussed by Zhang in [ZD94b], an efficient criterion to state F is the average retinal Euclidean distances between each point and its epipolar line. The following symmetric least-square sum is minimized:. where is a weight corresponding to the precision of the match, in fact the inverse of the variance of the precision of the match. The quantity is given in pixels-2, while , the average distance to the epipolar, is in pixel.

Minimization

Since we have yet not find an automatic determination of a parameters estimator, we use the "Nonlinear Least-Squares" algorithm, which give us good results.

Automatic code generation

The selection of constraints is done by a Java interface. The combination of constraints, the verification of compatibility is thus done by a formal software [Maple] which, from these constraints and with the library Mascotte, writes C code to use the simplification given by the constraints on the computation of free parameters (the minimization and criterion routines take into account only free parameters). These pieces of C code are thus compiled with the main program and the result is sent back to the Java interface.

Experimentations

Robotic experimental system Argès

We have experimented our method on a robotic system called Argès which has a rail, a turret (pan and tilt) and a zoom.

User interface

First, the user selects by hand particular cases with the following interface, written in Java. In a near future, the system will be able to automatically enumerate the set of possible constraints and test them, by comparing the residual errors. It will thus determine the most adequate case for the given data.
the demo will be later available via Internet

Experimental results

Here are the experimental results corresponding to two real displacements performed by our robotic system Argès. For each experiment, we compare the residual errors obtained for several hypotheses in order to show that we are able, with our method, to determine the most plausible case.

Pure translation

In this case, we have fixed the lens parameters and performed a pure translation along the rail (it is not necessarry a pure translation along the x-axis because of the default in orientation of the camera). Here are the images taken by the robotic system Argès:

and the 154 corners detected:


particular case	residual error
no rotation, fixed zoom, null	1.00368
pure translation along x	0.00485771
pure translation along z	1.00368
rotation along x, translation along z, null	987.827
zoom and pure translation	0.955463

These results show us that:

• the best result corresponds to the displacement performed : this method thus allows us to retrieve in which case we are
• the case of pure translation gives a worse result than the case of pure translation along the x-axis : the less parameters we have, the more precise is the method

Zoom displacement

We have fixed the focus in this experiment to control the zoom amplitude (focal length).
Here are the images taken by the robotic system Argès:

and the 45 corners detected:


particular case	residual error
no rotation, fixed zoom, null	1068.44
pure translation along x	1068.44
pure translation along z	1068.44
rotation along x, translation along z, null	7378.61
pure zoom	773.026

The conclusions are similar to those of the previous experiment. However, we note that the size of residual errors are not normalized with respect to the number of points, ...

Application

The first interest of this work is to allow to retrieve the maximum information on the camera, the scene and the displacements. We also consider the possibility to choose several cases and perform a "hierarchical" reconstruction: the robot performs a singular displacement to retrieve some parameters, an other to retrieve other parameters, and so on. The criterions allow to determine automatically the adequation to a specific case.

Bibliography

• [ARGES]: the robotic system Argès
• [BR95]
• [BZ94]
• [CH94]
• [EV96]
• [EZ96]
• [F95]
• [H94]
• [H94b]
• [HS88]
• [LV96]
• [MAPLE]: the software and the routines Mascotte
• [MF92]
• [PVG95]
• [S94]
• [S95]
• [S97a]
• [S97b]
• [SN94]
• [TZ95]
• [V94]
• [VGM94]
• [VF95]
• [VF96]
• [VL96]
• [VZ95]
• [ZD94]
• [ZD94b]
• [ZF94]
• [ZM94]

French and postscript version of this paper.