A revisit of the normalized eight-point algorithm and a self-supervised deep solution

Geometric computation has long been one of the major issues in computer vision. In particular, two-view geometry computation is a central building block for three-dimensional (3D) modeling and camera motion estimation. For example, self-driving is implemented through the technology of simultaneous localization and mapping (SLAM) and structure from motion (SfM). Among many important core algorithms, the eight-point algorithm Longuet_Reconstructing_Nature_1981 computes the fundamental matrix from a set of eight or more point correspondences between two views, which has the advantage of the simplicity of implementation. However, it was extremely susceptible to image noise and hence was of very limited practical use until Hartley devised a normalized eight-point algorithm in his seminal work Hartley_Normalization_TPAMI_1997 , which shows that by preceding the algorithm with a data normalization (translation and scaling) of the coordinates of the correspondences, the results obtained are comparable to those of the best iterative algorithms. As a consequence, with its simple strategy of translation and scaling, the isotropic normalization, now termed as Hartley’s normalization, has gradually become an indispensable component of many geometric computations not only for fundamental matrix estimation dai2016rolling but also for homography zhao2021homography , ellipse fitting szpak2015guaranteed , bundle adjustment zhang2014structure , etc.

One particular aspect of Hartley’s normalization in regard to the direct linear transformation (DLT) formulation of the fundamental matrix computation is that it allows the DLT solution to possess a better condition number. Therefore, when the solution matrix is enforced to have rank 2, a much more stable estimate of the fundamental matrix is obtained; this is important because it is the starting point of all the structure and motion computations such as guided correspondence search, camera and structure optimization, and 3D reconstruction for more than two views. Consequently, enforcing the rank-2 constraint as much as possible at the DLT stage becomes an interesting topic of study. For example, Mühlich and Mester Muhlich_Subspace_SCIA_2001 performed a statistical analysis to obtain an optimal data normalization for DLT fundamental matrix computation and showed that Hartley’s normalization can be expected to work well even though it is not identical to the optimal transform. Mair et al. Elamr_ErrorPropagation_IROS_2013 performed further error analysis to obtain a better performance than Hartley’s eight-point algorithm. The work of da Silveira and Jung daSilveira_Perturbation_CVPR_2019 presented a perturbation analysis of the eight-point algorithm for a wide field of view cameras. In contrast to these works based on statistical analysis, this paper tries to determine the mechanism of data normalization through deep learning without specific statistical modeling. Considering that the fundamental matrix estimation is strongly affected by the error distribution of the feature matching algorithm, we argue that a data normalization scheme can be exploited to achieve DLT solutions of improved rank-2 condition by learning the error distribution from the data themselves; this approach coincides with the views of Refs. Muhlich_TLS_ECCV_1998 ; Muhlich_Subspace_SCIA_2001 ; daSilveira_Perturbation_CVPR_2019 . In particular, as displayed in Fig. 1, we propose to learn a data-driven normalization scheme under the standard configuration of eight correspondences.

Currently, the success of deep learning in high-level vision tasks has been gradually extended to multi-view geometry problems such as homography Detone_DeepHomography_arxiv_2016 , fundamental matrix Ranftl_DeepFundamental_ECCV_2018 , bundle adjustment Tang_BANet_ICLR_2018 , plane sweeping Sunghoon_DPSNet_ICLR_2019 ; fan2021rs , and rolling-shutter modeling fan2023rolling ; fan2022rolling . However, this success has not been extended to the normalized eight-point algorithm and a different or better normalization scheme has so far not been presented nor replaced by the deep learning pipeline. This is mainly due to the following obstacles: 1) gradient descent cannot be trivially applied as mentioned in Ref. Ranftl_DeepFundamental_ECCV_2018 ; 2) the network must be invariant to the permutation of the correspondences, i.e., different orderings of the input data should produce the same normalization; and 3) a large amount of labeled input and output data should be used for supervised learning (in this case, the input is eight-point correspondences and the output is the optimal data normalization). In this paper, we overcome these problems by back-propagating through a singular value decomposition (SVD) layer and using a self-supervised learning mechanism in the permutation-invariant network architecture; this also solves the issue of large training data requirements. Our approach not only produces an interpretable pipeline of fundamental matrix estimation but can also be easily embedded in other robust frameworks such as the differentiable random sample consensus (RANSAC) Brachmann_DSAC_CVPR_2017 . Through experiments, our learning-based normalization demonstrated superior performance to Hartley’s normalization and a good generalization ability across different datasets. Our main contributions can be summarized as follows.

• 1)

  We propose a self-supervised learning-based deep solution for normalizing DLT fundamental matrix estimation under the standard configuration of eight point correspondences.

• 2)

  We make a theoretical contribution by demonstrating the existence of different and better normalization algorithms beyond Hartley’s normalization.

• 3)

  Extensive experiments on both synthetic and real images demonstrate the effectiveness and good generalizability of our proposed approach.

In this section, we briefly review related work in traditional two-view geometry computation and deep learning-based multi-view geometry learning.

We use capital letters, A, B, etc., to denote matrices. The operation of reshaping a matrix into a vector is denoted by $\mathrm{vec}(\cdot)$, defined as $\mathrm{vec}(\textit{{A}})=[\textit{{a}}_{1}^{T},...,\textit{{a}}_{N}^{T}]^{T}$, where $\textit{{a}}_{i}$ is the $i$-th column vector of A and $N$ is the number of columns. Its inverse operation is denoted as $\mathrm{mat}(\cdot)$.

Given a pair of correspondences $\textit{{u}}^{\prime}_{i}$ and $\textit{{u}}_{i}$ between two views, the epipolar constraint is expressed as

where $\textit{{F}}=[f_{ij}]$ is a $3\times 3$ matrix of rank 2, termed as the fundamental matrix. Collecting $N=8$ point correspondences $\{(\textit{{u}}^{\prime}_{i},\textit{{u}}_{i})|i=1,\ldots,8\}$, i.e., the standard configuration, we may rewrite Eq. (1) as a linear equation of f:

where $\textit{{f}}=\mathrm{vec}(\textit{{F}}^{T})$ is a nine-dimensional vector composed of stacked columns of $\textit{{F}}^{T}$, and $\textit{{A}}=[\textit{{a}}_{1},\ldots,\textit{{a}}_{8}]^{T}$ is the $8\times 9$ coefficient matrix with $\textit{{a}}_{i}=\mathrm{vec}(\textit{{u}}_{i}{\textit{{u}}^{\prime}}_{i}^{T})$ for $i=1,\ldots,8$. This approach provides the DLT formulation for computing F, and a solution may be obtained through SVD of A.

Despite its simplicity, the computation of the DLT for the eight-point algorithm Longuet_Reconstructing_Nature_1981 is extremely susceptible to noise in the image coordinate measurements. In the seminal work Hartley_Normalization_TPAMI_1997 , Hartley showed that the precision of the eight-point algorithm can be greatly improved by proper normalization of the image coordinates; this approach is the classic normalized eight-point algorithm. Hartley’s normalization is designed to compute image translation and scaling such that the average distance of the transformed coordinates from the origin is $\sqrt{2}$:

with $s$, $o_{1}$ and $o_{2}$ given by

where the superscript ${j}$ denotes the $j$-th entry of vector $\textit{{u}}_{i}$. Given two normalization matrices $\textit{{T}}^{\prime}$ and T, Eq. (2) is transformed to

where $\hat{{\textit{{A}}}}=[\hat{{\textit{{a}}}}_{1},...,\hat{{\textit{{a}}}}_{8}]^{T}$ is the transformed coefficient matrix with $\hat{{\textit{{a}}}}_{i}={\rm{vec}}(\hat{\textit{{u}}}_{i}\hat{\textit{{u}}}^{\prime}_{i}{{}^{T}})={\rm{vec}}(\textit{{T}}\textit{{u}}_{i}\textit{{u}}^{\prime}_{i}{{}^{T}}\textit{{T}}^{\prime T})$. In summary, the normalized eight-point algorithm mainly includes the following three steps.

1. 1)

   Normalization: Transform the input image coordinates according to $\hat{\textit{{u}}}^{\prime}_{i}=\textit{{T}}^{\prime}\textit{{u}}^{\prime}_{i}$ and $\hat{\textit{{u}}}_{i}=\textit{{T}}\textit{{u}}_{i}$.

2. 2)

   Compute the corresponding fundamental matrix $\hat{{\textit{{F}}}}^{\prime}$ to normalize data by

   1. a)

      Direct linear transform: Determine $\hat{{\textit{{F}}}}={\rm{mat}}(\hat{\textit{{f}}})$ from the right singular vector $\hat{\textit{{f}}}$ corresponding to the smallest singular value of $\hat{\textit{{A}}}$ defined in Eq. (5).

   2. b)

      Singularity constraint enforcement: Replace $\hat{{\textit{{F}}}}$ by $\hat{{\textit{{F}}}}^{\prime}=\hat{{\textit{{U}}}}{\rm{diag}}(r_{1},r_{2},0)\hat{{\textit{{V}}}}^{T}$, where $\hat{{\textit{{F}}}}=\hat{{\textit{{U}}}}\hat{{\textit{{D}}}}\hat{{\textit{{V}}}}^{T}$ with $\hat{\textit{{D}}}$ is a diagonal matrix $\hat{\textit{{D}}}={\rm{diag}}(r_{1},r_{2},r_{3})$ satisfying $r_{1}\geq r_{2}\geq r_{3}$.

3. 3)

   Denormalization: Set ${{\textit{{F}}}}={{\textit{{T}}}}^{\prime T}\hat{{\textit{{F}}}}^{\prime}{{\textit{{T}}}}$.

The condition number of A is defined as ${\kappa}(\textit{{A}})=\left\|\textit{{A}}\right\|_{2}\left\|\textit{{A}}^{+}\right\|_{2}$, where $\textit{{A}}^{+}$ is the pseudo-inverse of A. Its equivalent condition number may be defined as the ratio of the greatest to the second smallest singular values, ${\kappa}(\textit{{A}})=\sqrt{d_{1}/d_{8}}$, for $\textit{{A}}^{T}\textit{{A}}=\textit{{U}}\mathrm{diag}(d_{1},d_{2},...,d_{8},d_{9})\textit{{U}}^{T}$. It has been reported in the literature Hartley_Normalization_TPAMI_1997 ; Chojnacki_Revisiting8pt_TPAMI_2003 ; Chojnacki_Consistency_JMIV_2007 ; daSilveira_Perturbation_CVPR_2019 that the unsatisfactory performance of the eight-point algorithm is mainly due to the worse numerical conditioning of the coefficient matrix A. In fact, the condition number $k(\textit{{A}})$ is extremely large, leading to two least eigenvalues relatively close to one another, and causing their corresponding eigenvectors to be mixed up and indistinguishable. As a result, a negligible perturbation of the matrix entries tends to cause a significant change in the smallest eigenvector, since it may fall anywhere in the proximity to the eigensubspace spanned by the similar eigenvectors associated with those virtual degenerate eigenvalues Chojnacki_Revisiting8pt_TPAMI_2003 . It has been found that proper selection of normalization to the input image coordinates results in better numerical conditioning when carrying out linear DLT computation, and that the improved numerical conditioning provides with the smallest eigenvector of $\hat{\textit{{A}}}$ far less susceptible to interference Hartley_Normalization_TPAMI_1997 ; Chojnacki_Consistency_JMIV_2007 . From this point, a natural question arises: Can we achieve the ultimate optimal condition number $k(\hat{\textit{{A}}})=1$? Below we figure out that the condition number of the transformed coefficient matrix cannot reach the optimum of 1. A follow-up question must be: Can we have a better normalization transformation? This paper provides a positive answer in the next section. We develop a self-supervised CNN-based technique that learns the convolutional neural network weights based on a geometric loss function. It requires no ground truth labeling but has shown highly improved performance in various experiments.

This section develops a machine learning model that produces T and $\textit{{T}}^{\prime}$, the two data normalization matrices, which result in a better estimation of F than Hartley’s normalization for eight input correspondences. As discussed in Section 3, the estimation of the fundamental matrix has two main steps. First, the input image coordinates are normalized by T and $\textit{{T}}^{\prime}$ to construct the data matrix $\hat{\textit{{A}}}$, and the solution $\hat{\textit{{f}}}$ is obtained. Second, $\hat{\textit{{F}}}$ is reconstructed by enforcing the singularity constraint. The following are two observations regarding this estimation process:

1. 1)

   The goal of Hartley’s normalization is to achieve a better computation of $\hat{\textit{{f}}}$. However, this does not guarantee the singularity condition $\mathrm{det}(\mathrm{mat}(\hat{\textit{{f}}}))=0$, which is why the singularity constraint enforcement (SCE) is necessary.

2. 2)

   There are cases where enforcing the singularity ($\hat{\textit{{F}}}=\hat{\textit{{U}}}\mathrm{diag}(r_{1},r_{2},0)\hat{\textit{{V}}}^{T}$) brings about large nonlinear projection errors and leads to an unsatisfactory estimation of $\hat{\textit{{F}}}$. This happens especially when $\rho=r_{2}/r_{3}$ is not large enough.

It is evident that the singularity constraint should be considered at the same time as well as the numerical conditioning when the normalization matrices T and $\textit{{T}}^{\prime}$ are prepared, which implies the existence of better normalization schemes.

Our approach adopts a CNN-based model and a self-supervised learning algorithm to train it. The model outputs the parameters of the normalization matrices when eight input correspondences are provided as input. Following the conjecture of the affine structure of the normalization matrix proposed in Ref. Muhlich_TLS_ECCV_1998 , the normalization matrix is designed here to have two more parameters than Hartley’s normalization:

which can characterize the data distribution better and enable more general normalization schemes to be implemented by CNNs. Nevertheless, how to robustly determine three normalization parameters (especially $\alpha_{1}$, $\alpha_{2}$, and $\theta$) has always been a difficult problem. Note that, after Hartley’s seminal solution Hartley_Normalization_TPAMI_1997 , there has been no substantial progress in designing hand-crafted normalization strategies. In contrast, we try to extend Hartley’s normalization and develop a deep solution for normalization. The performance of the CNN model for this parametrization is evaluated and visualized through various experiments in Section 5. The overall computation pipeline of our framework is illustrated in Fig. 2.

To prove that our approach can learn normalization matrices adapted to the input data and obtain more accurate fundamental matrix estimations, we benchmark the performance of our approach on three typical datasets with varying regularity. Furthermore, we perform cross-dataset validation to prove the generalizability of our approach.

In this paper, we revisit the classic two-view geometry computation with eight point correspondences and employ CNNs to provide a novel perspective for better normalization. First, we present that the ideal condition number can be obtained by our approach to be more consistent with the following singularity constraint enforcement step. Second, we propose a self-supervised deep neural network to learn a robust normalization scheme for more accurate fundamental matrix estimation. Our approach enables a data-driven estimation pipeline to perform interpretable and generalized fundamental matrix estimation. Our learning-based normalization solution is superior to Hartley’s normalization for each input sample, and is comparable to Hartley’s normalization when integrated with RANSAC. Its potential advantage is to provide better initial values for non-linear optimization and to afford better interpretability for an ensemble network. In the future, we plan to design a lightweight network to weigh time and quality, utilize ground truth correspondences or ground truth matching scores to explore supervised two-view geometry estimation, and further extend our deep solution to other multi-view geometry problems such as triangulation, trifocal tensor estimation, etc.