Last update: Feb. '98

Publications by Marc Pollefeys, VISICS, Katholieke Universitat of Leuven, Belgium

• Self-Calibration and Metric Reconstruction in spite of Varying and Unknown Internal Camera Parameters, Marr Prize, ICCV98
• Self-calibration from the Absolute Conic on the Plane at Infinity, Proc.CAIP97, LNCS vol.1296, pp.175-182, Kiel, 1997

BibTeX references.

In this paper the theoretical and practical feasibility of self-calibration in the presence of varying internal camera parameters is under investigation. A theoretical proof will be given which shows that the absence of skew in the image plane is sufficient to allow for self-calibration. Besides this a self-calibration method is presented which efficiently deals with all kinds of constraints on the internal camera parameters and which can detect critical motion sequences. Within this framework a practical method is proposed which can retrieve metric reconstruction from image sequences obtained with uncalibrated zooming/focusing cameras. The feasibility of the approach is illustrated on real and synthetic examples.

Inputs:

• P matrices: matrices of projection of the cameras (for each view I(n) ) which encode the intrinsic and extrinsic calibration parameters (not distinguished). The P's are "robustly estimated" from corners matched between the I(n) .

Ouputs/ follow-up stages:

• Estimated Intrinsic camera parameters for each view: essentialy the f(n) (everything else is fixed in practice: in particular principal points are better fixed at the center of image arrays). This provides the matrices K(n) .
• Derived Extrinsic camera parameters: computed afterward using the P's and intrinsic parameters, solving the eqns: P = K [R | t] .
• From Projective to Metric (similitudes: Euclidean up to an unknown scaling) an Algebraic approach: Knowing the intrinsic calibration matrices K(n), it is shown that one can recover the Absolute Quadric O , the only quadric which stays invariant under all Euclidean transformations. One can use O to rectify ("straigthen") the initial projective geometric frames. This is done by bringing O into its canonical form (see Section 3 in paper), i.e., by imposing constraints on O (More details below).
• Dense correspondence matches: Once calibration is solved, dense correspondence maps are computed between pairs of images. This step generally uses the epipolar geometry constraint to bring the 2D matching problem to an 1D problem (one searches for a corresponding matching point along a "scanline": the epipolar line).
• Dense 3D (surface) trace can finally be retrieved: knowing camera calibration and correspondences, simple triangulation gives loci in 3D space [X Y Z]. Note however that, to reduce the impact of (cumulated) estimation errors, this step usally involves some pre-processing (e.g. bundle adjustment).
• Texture mapping: One may then map image intensity values from one view or a combination thereof (from the sequence I) onto the reconstructed 3D surface(s) to obtain a more realistic rendering.

Contribution:

This paper provides an "improved" way of going from the P's to the K's, i.e., the intrinsic camera calibration parameters (in practice, only the - potentially varying - focal lengths). The other steps above come from other contributions/papers. Note however, that contribtions to these other steps have been made by the Van Gool team, in particular within the VANGUARD project.

Given the following assumptions:

• no skew and fixed aspect ratio (f_x = f_y), a valid assumption for most cameras (it is claimed),
• focusing/zooming is allowed,
• principal point (projection of camera center in image arrays) can vary, but in practice it is found they should be fixed (and further set to the very center of the image arrays), as strong degradations are often observed otherwise,

the paper proposes, in essence, to:

1. always start with the principal point at the center of the first view, i.e., for image I(1): [u v] -> [0 0] .
2. use a Linear algorithm to get close to a solution (for matrices K), permitting only the focal lengths to vary,
3. use a Non-Linear algorithm to refine estimates, and eventually permit principal points [u v] to vary as well (but this does not prove robust enough).

The Linear approach:

The first view is made "special": the principal point is put at the center of the image array [u v] -> [0 0] and the Projective matrix is forced into its canonical form: P(1) = [I | 0] . Under this formulation the Absolute Quadric relation:

--> w(n) = P(n) O P(n)^t = K(n) K(n)^t (eqn (3) in paper)

becomes:

--> K(n) K(n)^t = P(n) [ A b / c d ] P(n)^t (eqn (6) in paper),

where A is the 3x3 matrix K(1) K(1)^t ,
b is the 3x1 vector [a_1 a_2 a_3]^t encoding the position of the plane at infinity,
c = b^t,
d = c . b = norm of [a_1 a_2 a_3]^t ,
and the LHS reduces to the diagonal matrix [ f(n)^2 f(n)^2 1] .

The bias toward the first view implies that eqns "for the first view are perfectly satisfied, whereas the noise has to be spread over the" eqns for the other views. This is not suitable for long sequences according to the authors. Note also that if we only have 2 views, non-uniqueness results in 4 possible solutions.

The Non-Linear approach:

To obtain a non-biased solution to eqn (3), it is proposed to minimize the following (non-linear) criterion:

Min SUM || K(n) K(n)^t - P(n) O P(n)^t ||^2, (eqn (4) in the paper) ,

under the Frobenius Norm (for all views),

where both K(n) K(n)^t and P(n) O P(n)^t are first normalised; this is standard preconditioning. Note: It seems that equivalently one could have first rescaled image pixel coordinates, for all I(n), to lie in the unit box [-1,1]x[-1,1] before computing the P's (see Triggs).

Note also that in eqn (4) above, the minimization criterion is derived from the following algebraic consideration: in order to obtain "metric calibration from the projective one" the dual image conics w(n) should be parametrised in such a way that they enforce the metric constraints on the calibration parameters.

If enough constraints are at hand only one quadric will satisfy them all, i.e., the Absolute Quadric. Thus, "constraints on the internal camera parameters in K(n) have been translated to constraints on the Absolute Quadric." Indeed!

The Absolute Quadric (Conic and duals):

"The Absolute Quadric O is a very flat dual quadric squashed onto the plane at infinity, whose rim is the Absolute Conic C" (see Triggs' CVPR97 paper for details). The projection of O in any given view gives the dual absolute image conic w, where w = P O P^t . It turns out that w is also linked to K: w = KK^t , and thus encodes the intrinsic camera parameters for any given view I(n).

During our discussion some people expressed their doubts in the usefulness of using such an algebraic abstraction, carying little geometric meaning (e.g. the eigenvectors of O are imaginary). Others were rather positive about its potential usefulness ... We should (probably try to) tackle this "representation" problem more specifically in another session. Note also that the critique of John Oliensis (see reading suggestions below) is of particular interest here. Not only has he "doubts", but he makes a strong case against the use of algebraic "tricks" to tackle the Structure From Motion (of the camera(s) say) problem.

Digression: The Frobenius Norm & some History of matrix algebra
(surfin ...;^)

A matrix norm that is not induced by any vector norm is the Frobenius norm defined for all matrices A in the space of Real nxm matrices. It is equal to the square root of the sum of all squared elements of A (for more details go to some linear algebra ref.). It can be shown that the Frobenius norm of a matrix A is equal to the sum of the diagonal elements (the trace) of A A^t .

Did you know that ...

The first known example of matrix methods comes from the Chineese text Nine Chapters of the Mathematical Art written during the Han Dynasty at about 200 BC ! ... and it contains a description of the use of Gaussian elimination ... which was (re-)discovered in early 19th century, by Gauss himself! who coined the word Determinant. It is Cayley (a lawyer by profession incidentally) who defined the inverse of a matrix and provided the first abstract definition of matrices (and hence their algebra). He went on to prove (in 1858) that a matrix satisfies its own characterisic equation for the 2x2 and 3x3 cases; Hamilton proved the 4x4 case and these results gave us the famous Cayley-Hamilton Theorem (any square matrix A is annihilated by its Characteristic Polynomial: Det(xI - A) = 0 ). But ... it is in 1878, that our friend Frobenius proved the general case (unaware of Cayley & Hamilton results) in his treatise On linear substitutions and bilinear forms, where furthermore he introduced the concept of the rank of a matrix. But (the modest) Frobenius (1849-1917) is best remembered for his work on Group Theory.

Conclusions - critiques

One important (and recent) critique to the use of the Absolute Quadric (or Conic) has been that methods based on this algebraic representation have lacked "good initialization guess and have been proved very tough [to solve]" (see BougnouCVPR97). Clearly the paper of Pollefeys et al. provides a (seemingly useful) solution to the initialization problem.

Note that most other methods, i.e., not using the algebraic "trick" of the Absolute Quadric representation, have been "forced" to rely upon the use of classical (and brute force) methods to calibrate the cameras and "Euclideanize" the geometric structure of the P's (or F's if one uses the Fundamental matrices instead). In general, the method of bundle adjustment is used (comes from photogrammetry), which, as Pollefeys et al. point out in their introduction, "requires non-linear minimisation over all reconstructed points and cameras simultaneously" (dire straights!).

Noteworthy is, after all this has been said, that (see BougnouCVPR97):

• The (3D) reconstruction of a (static) scene is NOT noticeably corrupted by changing the internal camera parameters (!) ... Indeed by changing the plane at infinity (and thus the Absolute Quadric), Bougnou demonstrates that this induces totally different internal camera parameters, BUT, that the collineation (a transformation of the plane which maps collinear points into collinear points) between the 2 obtained Euclidean bases is proved to be (only) an "anisotropic homothecy" (an homothecy is an Euclidean transformation up to a scale-factor, also called a "similarity" or "similitude"). For right angles, this may or may not have an impact (right angles may become sligtly larger or smaller than 90 degrees as a function of their relative orientation in the scene).
  
• An other way of thinking of this is that there exist a "strong ambiguity between a translation along the focal axis and a zoom" ... indeed! Thus focal lengths (intrinsic) and translations (extrinsic) are highly correlated in practice and it may not be possible (or useful) to disambiguate them and thus separate the P's into K's and R's and t's ...
  
• Bougnou also studies the question of the error introduced by fixing the principal points to the center of image arrays. From his analysis he concludes that there is no way to estimate the principal point when (i) the focal length is wide (i.e., when f tends to infinity and thus [u v] is not defined anymore) and (ii) the z-coordinates of the object points in the scene are far from the camera and confined in narrow boundaries (often the case in practice). In conclusion Bougnou recommends to let the principal points roam around (constraints on [u v] are anyway too weak from a minimization point of view) and NOT base the (projective) calibration/reconstruction on an accurate estimation of their positions.

Furthermore, at ICCV98, a paper presented by John Oliensis of NEC established the grounds of a Panel discussion on the merits (or lack thereof) of present "projective" approaches to Structure From Motion (SFM) problems versus the more classical Euclidean approaches. The latters simultaneously compute scene reconstruction and camera calibration. In summary, Oliensis makes the following critiques toward the "projective" approaches:

• SFM is about finding correspondences and performing non-linear estimation, and algebraic analysis is irrelevant to error analysis!
  
• Projective approaches are not proven to be simpler than Euclidean ones (mathematically speaking).
  
• In projective SFM each image has different unknown calibration which is unrealistic since calibration is strongly constrained in practice. In fact, the principal point, the aspect ratio or the focal length are often approximately known. "This approximate information can be useful, especially since errors in the [principal point loci] or focal lengths are known to have little effect on depth recovery" (Note that this is in agreement with Bougnou's analysis).

Oliensis goes-on by proposing his prefered strategy for solving SFM problems:

• Exploit context for effective algorithms since there are no useful general-purpose approach.
  
• Use a family of different algorithms best suited for different situations.
  
• Base algorithms on error analysis (error understanding as a function of the context).

Further readings:

Well, well, onto new readings I guess ... some suggestions:

• Some direct "competitor" to Pollefeys et al. : e.g. Bill Triggs and his "Autocalibration and the Absolute Quadric".
  
• Some "alternatives" to the use of the Absolute Quadric or Conic, like the use of Kruppa's eqns (which are, however, closely related to the Absolute Quadric formulation ...) or the "stratified approaches" (from projective to affine to similitude/Euclidean calibration levels).
  
• Some Euclidean approach where reconstruction and calibration are mixed: a good starting point may be the paper of Oliensis where he makes such a strong point against the "projective" approach (see ref. below).
  
• Some recent and descriptive reference on the use of "bundle adjustment" (I am looking for one, suggestions are more than welcomed! ) .
  
• Some paper on the precise definition and determination of intrinsic camera parameters. For example, there is the paper Willson & Shafer where multiple (16 ! ) definitions of image centers are given (see ref. below).

References:

1. Marc Pollefeys, Reinhard Koch and Luc Van Gool, "Self-Calibration and Metric Reconstruction in Spite of Varying and Unknown Internal Camera Parameters", IEEE Proceedings of the ICCV'98, Bombay, January 1998.
   
2. Sylvain Bougnou, "From Projective to Euclidean Space under any practical situation, a criticism of self-calibration", Proc. of CVPR'97, Puerto Rico, June 1997.
   
3. Bill Triggs, "Autocalibration and the Absolute Quadric", Proc. of CVPR'97, Puerto Rico, June 1997. Autocalibration and Euclidean reconstruction from an initial projective reconstruction. Based on the Absolute Quadric, the easy-to-use dual of the Absolute Conic. Nonlinear and quasi-linear methods.
   
4. John Oliensis, "A Critique of Structure from Motion Algorithms" NECI Technical Report, April 1997. Updated October 1997. Presented at ICCV98 for the "Panel - Structure from Motion", in Bombay, Jan. 1998.
   
5. R. G. Willson and Steven A. Shafer, "What is the Center of the Image?", Calibrated Imaging Laboratory (CIL), Robotics Intitute, Carnegie Mellon University, Pittsburgh, April 1993 (21 pages). Abstract.

To obtain a Euclidean reconstruction from images the cameras have to be calibrated. In recent years different approaches have been proposed to avoid explicit calibration. In this paper a new method is proposed which is closely related to some of the existing methods. Some interesting relations between the methods are uncovered. The method proposed in this paper shows some clear advantages. Besides some synthetic experiments a metric model is extracted from a video sequence to illustrate the feasibility of the approach.

Page created & maintained by Frederic Leymarie, 1998.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu