Multi-view constraints between collineations:
application to self-calibration from unknown
planar structures

Ezio Malis and Roberto Cipolla

Engineering Department, Cambridge University
Trumpington Street, CB2 1PZ Cambridge
{em240,cipolla}@eng.cam.ac.uk
http://www-svr.eng.cam.ac.uk

**Abstract.** In this paper we describe an efficient method to impose the constraints existing between the collineations which can be computed from a sequence of views of a planar structure. These constraints are usually not taken into account by multi-view techniques in order not to increase the computational complexity of the algorithms. However, imposing the constraints is very useful since it allows a reduction in the geometric errors in the reprojected features and provides a consistent set of collineations which can be used for several applications such as mosaicing, reconstruction and self-calibration. In order to show the validity of our approach, this paper focus on self-calibration from unknown planar structures proposing a new method exploiting the consistent set of collineations. Our method can deal with an arbitrary number of views and an arbitrary number of planes and varying camera internal parameters. However, for simplicity this paper will only discuss the case with constant camera internal parameters. The results obtained with synthetic and real data are very accurate and stable even when using only a few images.

**Keywords:** Self-calibration, Homography.

# 1 Introduction

The particular geometry of features lying on planes is often the reason for the inaccuracy of many computer vision applications (structure from motion, self-calibration) if it is not taken explicitly into account in the algorithms. Introducing some knowledge about the coplanarity of the features and about their structure (metric or topological) can improve the quality of the estimates [12]. However, the only prior geometric knowledge on the features that will be used here is their coplanarity. Two views of a plane are related by a collineation. Using multiple views of a plane we obtain a set of collineations which are not independent. If there are multiple planes in the scene there will be a set of collineations for each plane and again some constraints between the different
sets. In order to avoid solving non-linear optimisation problems, the constraints
existing within a set of collineation and between sets have often been neglected.
However, these multi-view constraints can be used to improve the estimation of
the collineations matrices as in [15], where multiple planes (≥ 2) are supposed
to be viewed in the images. In this paper we analyse the constraints existing
between a set of collineations induced by a simple plane in the image but it is
very easy to extend our analysis to the case of multiple planes. Imposing the
constraint is useful since it allows the reduction of the geometric error in the
reprojected features and provides a consistent set of collineations which can be
used for several applications as mosaicing, reconstruction and self-calibration.

In this paper we will focus on camera self-calibration. Camera self-calibration from views of a generic scene has been widely investigated and the two main approaches are based on the properties absolute conics [13] [10] or on some algebraic error [7] [4]. Depending on the a priori information provided the self-calibration algorithms can be classified as follows. Algorithms that use some knowledge of the observed scene: identifiable targets of known shape [8], metric structure of planes [11]. Algorithms that exploit particular camera motions: translating camera or rotating camera [5]. Algorithms that suppose known some of the camera parameters: some fixed camera parameters (i.e. skew zero, unit ratio ...), varying camera parameters [10] [9]. Camera self-calibration from planar scenes with known metric structure has been investigated in several papers. However, it is interesting to develop flexible techniques which do not need any a priori knowledge about the camera motion as in [5] or metric knowledge of the planar scene. A method for self-calibrating a camera from views of planar scenes without knowing their metric structure was proposed in [14]. Triggs developed a self-calibration technique based on some constraints involving the absolute quadric and the scene-plane to image-plane collineations. However, in practice it is not possible to estimate these collineations without knowing the metric structure of the plane. Only the collineations with respect to a reference view (a key image) can be used to self-calibrate a camera with constant internal parameters. As noticed by Triggs, inaccurate measurements or poor conditioning in the key image contribute to all the collineations reducing the numerical accuracy or the stability of the method. The aim of this paper is to investigate how to improve the self-calibration from planar scenes with unknown metric structure. We will not use any key image but all the images of the sequence are treated equally averaging the uncertainty over all of them.

This paper is organised as follows. In Section 2 we review the relation-
ship existing between two views of coplanar features and some properties of
the collineation matrices. In Section 3 we generalise the two-view geometry to
multiple views introducing the super-collineation matrix to describe a set of
collineations. Then, we describe a simple algorithm to impose the constraints
existing between the collineation of the set. Finally, we describe some constraints
on the camera internal parameters which can be used for self-calibration. In Sec-
tion 4 we give the results obtained with both synthetic and real data.
## 2 Two-view geometry of a plane

In this section we describe the relationship between two views of a planar structure. Each camera performs a perspective projection of a point $\mathbf{x} \in \mathbb{P}^3$ (with homogeneous coordinates $\mathbf{x} = [X Y Z 1]^T$) to an image point $\mathbf{p} \in \mathbb{P}^2$ (with homogeneous coordinates $\mathbf{p} = [u v 1]^T$) measured in pixels: $\mathbf{p} \propto \mathbf{K} [\mathbf{R} \mathbf{t}] \mathbf{x}$, where $\mathbf{R}$ and $\mathbf{t}$ represent the displacement between the frame $\mathcal{F}$ attached to the camera and an absolute coordinate frame $\mathcal{F}_0$, and $\mathbf{K}$ is a non-singular $(3 \times 3)$ matrix containing the intrinsic parameters of the camera:

$$ \mathbf{K} = \begin{bmatrix} fk_u - fk_u \cot(\theta) & u_0 \\ 0 & fk_v / \sin(\theta) & v_0 \\ 0 & 0 & 1 \end{bmatrix} \qquad (1) $$

where $u_0$ and $v_0$ are the coordinates of principal point (in pixels), $f$ is the focal length (in metres), $k_u$ and $k_v$ are the magnifications respectively in the $\bar{u}$ and $\bar{v}$ direction (in pixels/metres) and $\theta$ is the angle between these axes.

### 2.1 The collineation matrix in projective space

Let $\mathcal{F}_i$ and $\mathcal{F}_j$ be two frames attached respectively to the image $\mathcal{I}_i$ and $\mathcal{I}_j$. The two views of a planar object are related by a collineation matrix in projective space. Indeed, the image coordinates $\mathbf{p}_{ik}$ of the point $\mathcal{P}_k$ in the image $\mathcal{I}_i$ can be obtained from the image coordinates $\mathbf{p}_{jk}$ of the point $\mathcal{P}_k$ in the image $\mathcal{I}_j$:

$$ \mathbf{p}_{ik} \propto \mathbf{G}_{ij} \mathbf{p}_{jk} \qquad (2) $$

where the collineation matrix $\mathbf{G}_{ij}$ is a $(3 \times 3)$ matrix defined up to scalar factor which can be written as:

$$ \mathbf{G}_{ij} \propto \mathbf{K}_i \mathbf{H}_{ij} \mathbf{K}_j^{-1} \qquad (3) $$

where $\mathbf{H}_{ij}$ is the corresponding homography matrix in the Euclidean space. Homography and collineation are generally used to indicate the same projective transformation from $\mathbb{P}^n$ to $\mathbb{P}^n$ (in our case $n = 2$). In this paper we will use the term “homography” to indicate a collineation expressed in Euclidean space.

A relationship similar to equation (2) exists between the projections $\mathbf{l}_{ik}$ and $\mathbf{l}_{jk}$ in the two images $\mathcal{I}_i$ and $\mathcal{I}_j$ of a 3D line $\mathcal{L}_k$:

$$ \mathbf{l}_{ik} \propto \mathbf{G}_{ij}^{-\top} \mathbf{l}_{jk} \qquad (4) $$

The estimation of the collineation matrix is possible both from equation (2) and/or equation (4). However, for simplicity we will analyse only the case of points since the same results can be applied for lines.
## 2.2 The homography matrix in Euclidean space

The homography matrix can be written as a function of the camera displacement and the normal to the plane [2]:

$$ \mathbf{H}_{ij} = \mathbf{R}_{ij} + \frac{\mathbf{t}_{ij} \mathbf{n}_{j}^{\top}}{d_{j}} \qquad (5) $$

where $\mathbf{R}_{ij}$ and $\mathbf{t}_{ij}$ are respectively the rotation and the translation between the frames $\mathcal{F}_i$ and $\mathcal{F}_j$, $\mathbf{n}_j$ is the normal to the plane $\pi$ expressed in the frame $\mathcal{F}_j$ and $d_j$ is the distance of the plane $\pi$ from the origin of the frame $\mathcal{F}_j$. From (3), $\mathbf{H}_{ij}$ can be estimated from $\mathbf{G}_{ij}$ if we know the camera internal parameters of the two cameras:

$$ \mathbf{H}_{ij} \propto \mathbf{K}_{i}^{-1} \mathbf{G}_{ij} \mathbf{K}_{j} \qquad (6) $$

Three important properties of the homography matrix will be extended to the multi-view geometry in the next section:

1. the Euclidean homography matrix is not defined up to a scale factor. If the homography is multiplied by a scalar $\gamma$ ($\mathbf{H}' = \gamma\mathbf{H}$), this scalar can be easily recovered. If svd($\mathbf{H}'$) = [$\sigma_1 \sigma_2 \sigma_3$] are the singular values of $\mathbf{H}'$ in decreasing order, $\sigma_1 \ge \sigma_2 \ge \sigma_3 > 0$, then $\gamma$ is the median singular value of $\mathbf{H}'$: $\gamma = \text{median}(\text{svd}(\mathbf{H}')) = \sigma_2$. Indeed, the matrix $\mathbf{H}$ has a unit singular value [16] and this property can be used to normalise the homography matrix.

2. from equation (5) it is easy to show that the homography matrix satisfies the following equation $\forall k > 0$ (where $[\mathbf{n}_i]_\times$ and $[\mathbf{n}_j]_\times$ are the skew symmetric matrices associated with vectors $\mathbf{n}_i$ and $\mathbf{n}_j$ which represent the normal to the plane expressed respectively in the image frame $\mathcal{F}_i$ and $\mathcal{F}_j$):

$$ [\mathbf{n}_i]_\times \mathbf{H}_{ji}^T = \mathbf{H}_{ij} [\mathbf{n}_j]_\times \qquad (7) $$

This equation provides useful constraints. If $k = 1$, the matrix $[\mathbf{n}_i]_\times \mathbf{H}_{ji}^T = [\mathbf{n}_i]_\times \mathbf{R}_{ij}$ has similar properties to the essential matrix (i.e. $\mathbf{E} = [\mathbf{t}]_\times \mathbf{R}$). Indeed, this matrix has two equal singular values and one equal to zero. This means two constraints each homography on the camera internal parameters [6] which can be used for the self-calibration as in [9]. If $k = 2$, knowing that $[\mathbf{n}]^2 = \mathbf{n}\mathbf{n}^T - \mathbf{I}$, equation (7) can be written:

$$ \mathbf{n}_i \mathbf{n}_i^T \mathbf{H}_{ji}^T - \mathbf{H}_{ij} \mathbf{n}_j \mathbf{n}_j^T = \mathbf{H}_{ji}^T - \mathbf{H}_{ij} \qquad (8) $$

and provides equations that will be used to compute $\mathbf{n}_i$ and $\mathbf{n}_j$.

3. a very important relation can be obtained from equation (7) (with $k = 1$) and will be used to compute $\mathbf{n}_i$ and $\mathbf{n}_j$:

$$ [\mathbf{n}_i]_\times = \mathbf{H}_{ij} [\mathbf{n}_j]_\times \mathbf{H}_{ij}^T \qquad (9) $$

Indeed, since $\det(\mathbf{M})\mathbf{M}[\mathbf{v}]_\times \mathbf{M}^T = [\mathbf{M}^{-\top}\mathbf{v}]_\times$ then:

$$ \mathbf{n}_i = \mathbf{Q}_{ij} \mathbf{n}_j \qquad (10) $$

where:

$$ \mathbf{Q}_{ij} = \det(\mathbf{H}_{ij}) \mathbf{H}_{ij}^{-\top} \qquad (11) $$
# 3 Multi-view geometry of a plane

In this section we describe the relationships between several views of a planar structure. We will point out that a super matrix of 2D collineations among *m* views has rank 3 and we will show how to enforce the rank property in an iterative procedure. The properties of the corresponding super matrix of 2D homographies provide the necessary constraint for the self-calibration of the camera internal parameters. In what follows we will describe the case when only one planar structure is used but the extension to more than one plane is straightforward.

## 3.1 The super-collineation matrix

If *m* images of an unknown planar structure are available, it is possible to compute *m*(*m* − 1) collineations (*m* collineations are always equal to the identity matrix). Let us define the super-collineation matrix as follows:

$$G = \begin{bmatrix} G_{11} & \cdots & G_{1m} \\ \vdots & \ddots & \vdots \\ G_{m1} & \cdots & G_{mm} \end{bmatrix} \qquad (12)$$

with dim(*G*) = (3*m*, 3*m*) and rank(*G*) = 3. The rank of *G* can not be less than three since $G_{ii} = I_3$ $i \in \{1, 2, 3, ..., m\}$, and cannot be more than three since each row of the matrix can be obtained from a linear combination of three others rows:

$$G_{ij} = G_{ik}G_{kj} \quad \forall i, j, k \in \{1, 2, 3, ..., m\} \qquad (13)$$

This is a very strong constraint which is generally never imposed. Indeed, it would require a complex nonlinear minimisation algorithm over all the images. The constraints (13) can be summarised by the following equation:

$$G^2 = m G \qquad (14)$$

Then, matrix *G* has 3 nonzero equal eigenvalues $\lambda_1 = \lambda_2 = \lambda_3 = m$ and 3($m-1$) null eigenvalues $\lambda_4 = \lambda_5 = ... = \lambda_{3m} = 0$. If we can impose the constraint $G^2 = m G$ (with $G_{ii} = I_3$ $i = 1, 2, 3, ..., m$) then this is in fact equivalent to imposing the constraints $G_{ij} = G_{ik}G_{kj}$.

**Imposing the constraints** In order to impose the constraint, we exploit the properties of the super-collineation matrix. Let $p_{ij}$ be the j-th point ($j = \{1, 2, 3, ..., n\}$) of the i-th image ($i = \{1, 2, 3, ..., m\}$). The j-th point in all the images can be represented by the vector of dimension (3*m*, 1) (which we will call a super-point): $p_j^T = [p_{1j}^T p_{2j}^T \cdots p_{mj}^T]$. Generalising equation (2) we obtain:

$$\Gamma_j p_j = G p_j \qquad (15)$$

where $\Gamma_j = \text{diag}(\gamma_{1j}I_3, \gamma_{2j}I_3, ..., \gamma_{mj}I_3)$ is a diagonal matrix relative to the set of points j. Then, multiplying both sides of equation (15) by *G* we have:

$$G \Gamma_j p_j = G^2 p_j = m G p_j = m \Gamma_j p_j \qquad (16)$$
The vector $\tilde{\mathbf{p}}_j = \Gamma_j \mathbf{p}_j$ (representing the homogeneous coordinates of the point $j$ in all the images) is an eigenvector of $\mathbf{G}$ corresponding to the eigenvalue $m$:

$$ \mathbf{G}\tilde{\mathbf{p}}_j = m\tilde{\mathbf{p}}_j \qquad (17) $$

As a consequence any super-point can be obtained as a linear combination of the eigenvectors of $\mathbf{G}$ corresponding to the eigenvalue $\lambda = m$:

$$ \tilde{\mathbf{p}}_j = \alpha_1 \mathbf{x}_1 + \alpha_2 \mathbf{x}_2 + \alpha_3 \mathbf{x}_3 \qquad (18) $$

The matrix $\mathbf{G}$ can always be diagonalised and thus three linearly independent eigenvectors always exist, i.e., $\exists \mathbf{X} : \mathbf{X}^{-1}\mathbf{G}\mathbf{X} = \text{diag}(\lambda_1, \lambda_2, ..., \lambda_{3m})$. The columns of the matrix $\mathbf{X}$ are in fact eigenvectors of $\mathbf{G}$. Since $\mathbf{X}$ is nonsingular, the eigenvectors of $\mathbf{G}$ are linearly independent and span the space $\mathbb{R}^{3m}$. That means that an initial estimation $\hat{\mathbf{p}} \in \mathbb{R}^{3m}$ of the super-point $\hat{\mathbf{p}}$ can be written as $\hat{\mathbf{p}} = \alpha_1 \mathbf{x}_1 + \alpha_2 \mathbf{x}_2 + \alpha_3 \mathbf{x}_3 + ... + \alpha_{3m} \mathbf{x}_{3m}$. The real super-point $\hat{\mathbf{p}}$ is an eigenvector of $\mathbf{G}$ corresponding to the largest eigenvalue $\lambda = m$. We can thus use a well-known algorithm to find an eigenvector of $\mathbf{G}$ starting from $\hat{\mathbf{p}}$. Lets multiply our vector by $\frac{1}{m}\mathbf{G}$:

$$ \hat{\mathbf{p}}^1 = \frac{1}{m}\mathbf{G}\hat{\mathbf{p}} = \frac{1}{m}(\alpha_1 \mathbf{G}\mathbf{x}_1 + \alpha_2 \mathbf{G}\mathbf{x}_2 + \alpha_3 \mathbf{G}\mathbf{x}_3 + ... + \alpha_{3m} \mathbf{G}\mathbf{x}_{3m}) \qquad (19) $$

and then replace each $\mathbf{G}\mathbf{x}_k$ with its corresponding $\lambda_k \mathbf{x}_k$. Factoring out $\lambda_1$ we have:

$$ \hat{\mathbf{p}}^1 = \frac{\lambda_1}{m} \left( \alpha_1 \mathbf{x}_1 + \frac{\lambda_2}{\lambda_1} \alpha_2 \mathbf{x}_2 + \frac{\lambda_3}{\lambda_1} \alpha_3 \mathbf{x}_3 + \dots + \frac{\lambda_{3m}}{\lambda_1} \alpha_{3m} \mathbf{x}_{3m} \right) \qquad (20) $$

In a similar way, iterating the procedure $k$ times we obtain:

$$ \hat{\mathbf{p}}^k = \frac{\lambda_1^k}{m^k} \left( \alpha_1 \mathbf{x}_1 + \left(\frac{\lambda_2}{\lambda_1}\right)^k \alpha_2 \mathbf{x}_2 + \left(\frac{\lambda_3}{\lambda_1}\right)^k \alpha_3 \mathbf{x}_3 + \dots + \left(\frac{\lambda_{3m}}{\lambda_1}\right)^k \alpha_{3m} \mathbf{x}_{3m} \right) \qquad (21) $$

This algorithm will converge to the eigenvector of $\mathbf{G}$ corresponding to the highest eigenvalue since all the fractions $\lambda_k/\lambda_1$ that are less than unit in magnitude become smaller as we raise to higher powers. In our case, if we knew exactly the super-collineation matrix, the algorithm would converge after only one iteration since we have $\lambda_1 = \lambda_2 = \lambda_3 = m$ and $\lambda_k = 0 \forall 3 < k \le 3m$ and the new estimated super-point will satisfy the constraint of being an eigenvector of $\mathbf{G}$ which means that the noise has been reduced.

In practice, the real super-collineation matrix $\mathbf{G}$ is unknown and we must use an approximation $\hat{\mathbf{G}}$ estimated from the noisy points in the images. The algorithm used is the following. We start with a set of $n$ points $\hat{\mathbf{p}}_j$ ($j = 1, 2, 3, ..., n$) and compute the super-collineation matrix $\hat{\mathbf{G}}$ solving independently the linear problem of estimating each block $\hat{\mathbf{G}}_{ij}$ from equation (2). It is not necessary that all the points are visible in all the images. Then, we compute a new set of super-points trying to impose the constraint. The better the estimate of $\mathbf{G}$ we obtain the faster the algorithm will converge and the more accurate will be the results. At iteration $k$ the algorithm is:
(i) estimate the super-collineation matrix

$$ \hat{\mathbf{p}}_j(k) \Rightarrow \hat{\mathbf{G}}(k) \qquad (22) $$

(ii) compute the new super-point

$$ \hat{\mathbf{p}}_j(k+1) = \frac{1}{m} \hat{\mathbf{G}}(k) \hat{\mathbf{p}}_j(k) \qquad (23) $$

This algorithm treats all the images with the same priority without using any key image and forces the rank 3 constraint on G. We now show some simulation results which demonstrate the validity of our approach (we will describe in the next section 3.2 how to use the consistent set of collineation matrix in order to perform the self-calibration of the camera).

<figure><img src="image_1.png" /><figcaption>Fig. 1. Geometric noise reduction obtained imposing the rank 3 constraint on the super-collineation matrix.</figcaption></figure>

**Simulation results** The algorithm was tested on a simulated planar grid of 64 points. It converges after 1 or 2 iterations imposing the constraint on the rank of the matrix G. The error between the theoretical position of the points (which is never used in the algorithm but only for its evaluation) and the transformed coordinates is greatly reduced. Figure 1 shows the results obtained from random views with a random axis of rotation and a 30 degrees angle of rotation with respect to a fixed position. On the horizontal axis are given the number of
images used and on the vertical axis the corresponding rate of noise reduction. The continuous line gives us an upper bound of the reduction rate that could be possible if the super-collineation was known exactly. This reduction is practically independent of the level of noise and all continuous lines are superposed in Figure 1. The dashed dotted lines represent the results obtained estimating the super-collineation matrix with different level of noise (0.1 ≤ σ² ≤ 1000). The rate of noise reduction does not vary significantly with the amplitude of the noise. However, when the level of noise increases the reduction rate decreases since the estimation of the super-collineation matrix becomes less accurate. Finally, we obtain only a small improvement when increasing the number of the images from 50 to 100. In the simulation results described in section 4.1 we obtain very similar results varying the camera internal parameters and the angle of rotation between the images.

## 3.2 The super-homography matrix

Let us define the super-homography matrix in the Euclidean space as:

$$ \mathbf{H} = \begin{bmatrix} \mathbf{H}_{11} & \cdots & \mathbf{H}_{1m} \\ \vdots & \ddots & \vdots \\ \mathbf{H}_{m1} & \cdots & \mathbf{H}_{mm} \end{bmatrix} \qquad (24) $$

with dim(H) = (3m, 3m) and rank(H) = 3. The super-homography matrix can be obtained from the super-collineation matrix and the camera parameters:

$$ \mathbf{H} = \mathbf{K}^{-1}\mathbf{G}\mathbf{K} \qquad (25) $$

where (dim(K) = (3m, 3m) and rank(K) = 3m):

$$ \mathbf{K} = \begin{bmatrix} \mathbf{K}_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \mathbf{K}_n \end{bmatrix} \qquad (26) $$

is the matrix containing the internal parameters of all the cameras. It should be noticed that if the constraint G² = mG was imposed, then the constraint H² = mH is automatically imposed which means that the following constraints are satisfied:

$$ \mathbf{H}_{ij} = \mathbf{H}_{ik}\mathbf{H}_{kj} \qquad (27) $$

Unlike the super-collineation matrix, the super-homography matrix is not defined up to a diagonal similarity. Indeed, if σᵢⱼ denotes the median singular value of the matrix Hᵢⱼ we can build the following matrix which contain all the coefficients of normalisation: D = diag(σ₁₁I₃, σ₁₂I₃, ..., σ₁ₘI₃). The super homography matrix is thus normalised as follows:

$$ \mathbf{H} = \mathbf{D}\tilde{\mathbf{H}}\mathbf{D}^{-1} \qquad (28) $$

From this equation we can easily see that the constraint H² = mH holds. In the presence of noise, normalising H with equation (28) will conserve the rank constraint of the matrix since it is a similarity transformation.
### 3.3 Super-homography decomposition

After normalisation, the homography matrix can be decomposed as:

$$H = R + TN^T \quad (29)$$

where:

$$R = \begin{bmatrix} R_{11} & \cdots & R_{1m} \\ \vdots & \ddots & \vdots \\ R_{m1} & \cdots & R_{mm} \end{bmatrix}, \quad T = \begin{bmatrix} \frac{t_{11}}{d_1} & \cdots & \frac{t_{1m}}{d_m} \\ \vdots & \ddots & \vdots \\ \frac{t_{m1}}{d_1} & \cdots & \frac{t_{mm}}{d_m} \end{bmatrix}, \quad N = \begin{bmatrix} n_1 & 0 & \cdots & 0 \\ 0 & n_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & n_m \end{bmatrix} \quad (30)$$

with $dim(R) = (3m, 3m)$, $rank(R) = 3$, $dim(T) = (3m, m)$ and $dim(N) = (3m, m)$. Matrix $R$ is a symmetric matrix, $R = R^T$ and $R^2 = mR$. As a consequence not only are the three largest eigenvalues $\lambda_1 = \lambda_2 = \lambda_3 = m$ but also the three largest singular values are $\sigma_1 = \sigma_2 = \sigma_3 = m$. In [2] and [16] are presented two different methods for decomposing the homography matrix, computed from two views of a planar structure, following equation (5). In general, there are two possible solutions but the ambiguity can be resolved by adding more images. Here we present a method to decompose any set of homography matrices. Equation (10) can be generalised as follows:

$$Q = \begin{bmatrix} Q_{11} & \cdots & Q_{1m} \\ \vdots & \ddots & \vdots \\ Q_{m1} & \cdots & Q_{mm} \end{bmatrix} = WH^T W^{-1} \quad (31)$$

where $W = \text{diag}(1, \det(H_{21}), \dots, \det(H_{m1}))$ and $dim(Q) = (3m, 3m)$ and $rank(Q) = 3$. Matrix $Q$ has similar properties to the matrix $H$, for example, it has an eigenvalue $\lambda = m$ of multiplicity three. The vector $n$ is an eigenvector of $Q$ corresponding to the eigenvalue $\lambda = m$:

$$Qn = mn \quad (32)$$

where $n = [n_1^T \ n_2^T \ \dots \ n_m^T]^T$. The vector can be written as a linear combination of the eigenvectors $n = x \ v_1 + y \ v_2 + z \ v_3 = Vx$, where $x = [x \ y \ z]^T$ is a vector containing three unknowns and $V = [v_1 \ v_2 \ v_3]$ is a known matrix. Imposing the constraint $||n_k|| = 1$ and the constraints given by equation (8) we obtain:

$$V_i x x^T V_i^T H_{ji}^T - H_{ij} V_j x x^T V_j^T = H_{ji}^T - H_{ij} \quad (33)$$

from which is possible to compute the unknown matrix $x x^T$ and then, by singular values decomposition, the original unknown which is $x$. Once find $x$, the normals to the plane are extracted from $H$ and knowing that $RN = NO_m$ we find:

$$T = HN - 0_{3m}N \quad (34)$$

$$R = H(NN^T - I_{3m}) + N^T 0_{3m} N \quad (35)$$
## 3.4 Camera self-calibration

The super-homography can of course be used in many applications. In this section we use the properties of the set of homography matrices to self-calibrate the cameras. It should be noticed that we avoid the use of a bundle adjustment technique to impose the rank 3 constraint on the super-homography (as explained in section 3) and thus we considerably simplify the algorithm. In this case, the only unknowns are the camera internal parameters. Each independent homography will provide us two constraints on the parameters according to equation (7). Indeed, if $\sigma_{ij}^I$ and $\sigma_{ij}^{II}$ are the two non-zero singular values of $[\mathbf{n}_i]_\times \mathbf{H}_{ji}^T$ our self-calibration method is based on the minimisation of the following cost function [4][9]:

$$C = \sum_{i=1}^{m} \sum_{j=1}^{m} \frac{\sigma_{ij}^{I} - \sigma_{ij}^{II}}{\sigma_{ij}^{I}} \qquad (36)$$

A minimum of 3 independent homography matrices (4 images) is sufficient to recover the focal length and the principal point supposing $r = 1$ and $\theta = \pi/2$ and a minimum of 4 independent homography matrices (5 images) is sufficient to recover all the parameters.

# 4 Experiments

The self-calibration algorithm has been tested on synthetic and real images. The results obtained with a calibration grid were compared with the standard Faugeras-Toscani method [3]. Our self-calibration algorithm is the following:

1. Match corresponding points in $m$ images of a planar structure;

2. Compute the super-collineation imposing the rank 3 constraint using the algorithm described in Section 3.1;

3. Using an initial guess of the camera parameters compute the normalised super-homography matrix as described in Section 3.2;

4. Decompose the super-homography matrix and find the normal to the plane as described in Section 3.3;

5. Compute a new set of camera parameters which minimise the cost function given in Section 3.4 and go to step 3.

## 4.1 Simulations of a planar grid

The planar grid used for the simulations in section 3 was used to test the self-calibration algorithm. The experimental setup is as close as possible to the one proposed by Triggs [14]. The cameras roughly fixate a point on the plane from randomly generated orientations varying $\pm 30^\circ$ in each of the three axes. The nominal camera calibration is $f = 1000$, $r = 1$, $\theta = 90^\circ$, $u = 250$ and $v = 250$. The plane contains 64 points projected into a $500 \times 500$ image. The camera calibration varies randomly about the nominal values of $\sigma_f = \pm 30\%$, $\sigma_r = \pm 10\%$, $\sigma_\theta = 0.5^\circ$ and $\sigma_u = \sigma_v = \pm 75$ pixels ($\sigma_f$ and $\sigma_r$ are standard deviations of log-normal distributions while $\sigma_\theta$, $\sigma_u$ and $\sigma_v$ of normal ones).
<figure><img src="image_2.png" /><figcaption>**Fig. 2.** Simulations results of camera self-calibration using a planar grid. The graphs (a), (b), (c), (d) and (e) show the mean of the errors on the camera internal parameters (respectively *f*, *θ*, *r*, *u*, *v*) obtained with the self-calibration algorithm. Graph (f) shows the failure rate of the algorithm. Finally, the graphs (g), (h) and (i) show the mean of the errors on the camera internal parameters (respectively *f*, *u*, *v*) obtained supposing *θ* = 90° and *r* = 1.</figcaption></figure>

In Figure 2 we give the results obtained using 6 (lines marked with a square), 8 (lines marked with a triangle) and 10 (lines marked with a circle) images and supposing all the camera parameters unknowns. The figure represents the mean error computed on 100 trials with different parameters and different camera positions for each level of noise (the standard deviation of the Gaussian noise added to the coordinates of the points is increased from 0 to 5). The error on the principal point is given as a percentage of the focal length. The errors on
the camera parameters increase with the noise and decrease with the number of images used for self calibration. Using six images the results are still satisfactory even if the failure rate of the method increases rapidly (a failure of the method occurs when the obtained focal length is less than 100 pixels). This can be explained since it is known that with few images there is the risk of degenerate configurations [11]. The results obtained compare very favourably to the results obtained by Triggs in [14], especially considering the failure rate of the method. For example, using 10 images we obtain a mean error more than 50 % smaller than the error obtained by Triggs. Finally, in Figure 2(g), (h) and (i) we give the results of our method when r and θ are fixed to their nominal values. The error on the focal length is practically the same. On the other hand, the error on the location of the principal point is reduced since the non-linear search is now done in a three-dimensional space reducing the risk of local minima.

## 4.2 Self-calibration from images of a grid and comparison with the standard Faugeras-Toscani calibration method

A sequence (26 images of dimension (640 × 480)) of a calibration grid was taken using a Fuji MX700 camera with a 7mm lens. Figure 3 shows three images of the sequence. The corners of the black squares are used to compute the supercollineation matrix in order to self-calibrate the camera with our method.

<figure><img src="image_3.png" /><figcaption>**Fig. 3.** Three images of the sequence taken with a digital camera. The calibration grid allows the “ground truth” to compare our method with the standard Faugeras-Toscani method. The main advantage of using our method is that we don’t need any knowledge of the 3D structure of the grid to calibrate the camera. On the other hand, at least five images are needed.</figcaption></figure>

Table 1 gives the results for the following experiment:

- non-planar calibration: the mean and the standard deviation on 26 images of the grid calibrated with the standard Faugeras-Toscani method initialised with the DLT linear method [1]. In this case we use both planes to calibrate the camera;

- planar self-calibration: the mean and the standard deviation on 50 tests using m images (m = 6,8,10) randomly chosen between the 26 images of the grid. The same tests are repeated using the right plane alone, the left plane alone and then again with r and θ fixed to nominal values.
The results are very good and agree with the simulations. They are more accurate than the results obtained by Triggs with a sequence of images of a calibration grid. In our case, the angle of rotation between the images of the sequence can be greater than 60° which has in general the effect to improve the results. However, this is not always true since the planes can be very close to the optical center of the camera (see in Figure 3) and in this case the estimation of the collineations is not accurate. The calibration obtained using the right plane is again very similar to the calibration obtained using the left plane. As we expected the accuracy decreases as we decrease the number of images but the worst result (obtained using only 6 images of the grid) is only an error of 2% on the focal length.

<table><caption>**Table 1.** Results using digital images of the grid (statistics on 50 tests)</caption><thead><tr><th>calibration method</th><th>f</th><th>r</th><th>θ</th><th>u</th><th>v</th></tr></thead><tbody><tr><td>DLT linear</td><td>685 ± 3</td><td>1.0005 ± 0.0033</td><td>90.00 ± 0.14</td><td>322 ± 5</td><td>229 ± 4</td></tr><tr><td>Faugeras-Toscani</td><td>685 ± 3</td><td>1.0003 ± 0.0022</td><td>90.00 ± 0.16</td><td>322 ± 5</td><td>229 ± 4</td></tr><tr><td>right plane (10 im)</td><td>680 ± 8</td><td>0.9976 ± 0.0088</td><td>89.23 ± 0.59</td><td>318 ± 8</td><td>230 ± 8</td></tr><tr><td>left plane (10 im)</td><td>680 ± 6</td><td>0.9943 ± 0.0058</td><td>89.89 ± 0.30</td><td>320 ± 7</td><td>232 ± 4</td></tr><tr><td>right plane (8 im)</td><td>681 ± 12</td><td>0.9950 ± 0.0105</td><td>89.21 ± 0.80</td><td>315 ± 11</td><td>232 ± 9</td></tr><tr><td>left plane (8 im)</td><td>678 ± 12</td><td>0.9969 ± 0.0075</td><td>90.06 ± 0.24</td><td>327 ± 14</td><td>233 ± 3</td></tr><tr><td>right plane (6 im)</td><td>686 ± 13</td><td>0.9891 ± 0.0126</td><td>89.63 ± 0.69</td><td>312 ± 18</td><td>231 ± 11</td></tr><tr><td>left plane (6 im)</td><td>685 ± 10</td><td>0.9886 ± 0.0147</td><td>89.80 ± 0.59</td><td>339 ± 18</td><td>232 ± 7</td></tr><tr><td>Faugeras-Toscani</td><td>685 ± 3</td><td>1 ± 0</td><td>90 ± 0</td><td>322 ± 6</td><td>229 ± 4</td></tr><tr><td>right plane (10 im)</td><td>679 ± 6</td><td>1 ± 0</td><td>90 ± 0</td><td>318 ± 5</td><td>224 ± 8</td></tr><tr><td>left plane (10 im)</td><td>675 ± 6</td><td>1 ± 0</td><td>90 ± 0</td><td>325 ± 4</td><td>232 ± 4</td></tr><tr><td>right plane (8 im)</td><td>687 ± 6</td><td>1 ± 0</td><td>90 ± 0</td><td>323 ± 3</td><td>231 ± 6</td></tr><tr><td>left plane (8 im)</td><td>676 ± 4</td><td>1 ± 0</td><td>90 ± 0</td><td>343 ± 27</td><td>231 ± 12</td></tr><tr><td>right plane (6 im)</td><td>676 ± 8</td><td>1 ± 0</td><td>90 ± 0</td><td>314 ± 9</td><td>227 ± 5</td></tr><tr><td>left plane (6 im)</td><td>677 ± 18</td><td>1 ± 0</td><td>90 ± 0</td><td>327 ± 34</td><td>230 ± 31</td></tr></tbody></table>

After the camera has been calibrated, the 3D reconstruction of the planes was realized. If $n_{rj}$ and $n_{lj}$ are respectively the normal to the right and left plane in the frame attached to the image $I_j$, the angle between them is:

$$ \phi_j = \cos^{-1}(n_{rj}^T n_{lj}) $$

This angle should be the same for all the images $j = 1, 2, 3, ..., m$. In order to verify the quality of the reconstruction results we can compute the mean and the standard deviation $\sigma$ over all the images. For example, the results obtained with a sequence of $m = 10$ images were:

$$ \nu = \frac{1}{m} \sum_{j=1}^{m} \phi_j = 89.84, $$

$$ \sigma = \frac{1}{m} \sqrt{\sum_{j=1}^{m} (\phi_j - \nu)^2} = 0.21 $$
4.3 Self-calibration from images of a facade

In this experiment, in order to test our algorithm in very extreme conditions,
only four images of a facade (see Figure 4) were taken with the same digital
camera. With such images the localisation of the corners was not accurate and
with only four images we can only calibrate the focal length and the principal
point (thus we fixed r = 1 and θ = 90°). The results obtained using our self-
calibration with 56 points (the corners of the windows on the facade) are f = 678
(1 % of the mean focal length obtained with the Faugeras-Toscani method and
the calibration grid), u = 355 and v = 216. The results are very good even using
images of a roughly planar structure.

<figure><img src="image_4.png" /><figcaption>**Fig. 4.** Four images of a facade. The corners of the windows (marked with a white cross) belong roughly to a plane. They are used to compute the super-collineation matrix from which it is possible to self-calibrate the camera.</figcaption></figure>

5 Conclusion

In this paper we presented an efficient technique to impose the constraints ex-
isting within a set of collineation matrices computed from multiple views of a
planar structure. The obtained set of collineations can be used for several appli-
cations such mosaicing, reconstruction and self-calibration from planes. In this
paper we focused on self-calibration proposing a new method which does not
need any a priori knowledge of the metric structure of the plane. The method
was tested both with synthetic and real images and the obtained results are very
good. However, the method could be improved by imposing further constraints
in order to obtain not only a consistent set of collineations matrices but also a
consistent set homography matrices. The method could also be improved using
a probabilistic model for the noise.

Acknowledgements

This work was supported by an EC (ESPRIT) grant no. LTR26247 (VIGOR).
We would like to thank Paulo Mendonca and Kenneth Wong for their kind help.

References

1. Y. I. Abdel-Aziz and H. M. Karara. Direct linear transformation into object space coordinates in close-range photogrametry. In *Proc. Symp. Close-Range Photogrammetry*, pages 1–18, University of Illinois, Urbana, 1971.

2. O. Faugeras and F. Lustman. Motion and structure from motion in a piecewise planar environment. *International Journal of Pattern Recognition and Artificial Intelligence*, 2(3):485–508, 1988.

3. O.D. Faugeras and G. Toscani. The calibration problem for stereo. In *Proc. IEEE Int. Conf. on Computer Vision and Pattern Recognition*, pages 15–20, June 1986.

4. R. Hartley. Estimation of relative camera positions for uncalibrated cameras. In G. Sandini, editor, *Proc. European Conf. on Computer Vision*, volume 588 of *Lecture Notes in Computer Science*, pages 579–587. Springer-Verlag, May 1992.

5. R. Hartley. Self-calibration from multiple views with a rotating camera. In *Proc. European Conf. on Computer Vision*, pages 471–478, May 1994.

6. R. Hartley. Minimising algebraic error in geometric estimation problem. In *Proc. IEEE Int. Conf. on Computer Vision*, pages 469–476, 1998.

7. S. Maybank and O. Faugeras. A theory of self-calibration of a moving camera. *International Journal of Computer Vision*, 8(2):123–151, 1992.

8. J. Mendelsohn and K. Daniilidis. Constrained self-calibration. In *Proc. IEEE Int. Conf. on Computer Vision and Pattern Recognition*, pages 581–587, 1999.

9. P.R.S. Mendonca and R. Cipolla. A simple technique for self-calibration. In *Proc. IEEE Int. Conf. on Computer Vision and Pattern Recognition*, pp. 500–505, 1999.

10. M. Pollefeys, R. Koch, and L. VanGool. Self-calibration and metric reconstruction inspite of varying and unknown intrinsic camera parameters. *International Journal of Computer Vision*, 32(1):7–25, August 1999.

11. P.F. Sturm and S.J. Maybank. On plane-based camera calibration: A general algorithm, singularities, applications. In *Proc. IEEE Int. Conf. on Computer Vision and Pattern Recognition*, pages 432–437, 1999.

12. R. Szeliski and P. Torr. Geometrically constrained structure from motion: Points on planes. In *European Workshop on 3D Structure from Multiple Images of Large-Scale Environments (SMILE)*, pages 171–186, Freiburg, Germany, June 1998.

13. B. Triggs. Autocalibration and the absolute quadric. In *Proc. IEEE Int. Conf. on Computer Vision and Pattern Recognition*, pages 609–614, 1997.

14. B. Triggs. Autocalibration from planar scenes. In *Proc. European Conf. on Computer Vision*, pages 89–105, 1998.

15. L. Zelnik-Manor and M. Irani. Multi-view subspace constraints on homographies. In *Proc. IEEE Int. Conf. on Computer Vision*, volume 1, pp. 710–715, Sept. 1999.

16. Z. Zhang and A. R. Hanson. Scaled euclidean 3D reconstruction based on externally uncalibrated cameras. In *IEEE Symposium on Computer Vision*, pp 37–42, 1995.