Deep Fundamental Matrix Estimation withoutCorrespondencesOmid Poursaeed*1,2 , Guandao Yang*1 , Aditya Prakash*3 , Qiuren Fang1 , HanqingJiang1 , Bharath Hariharan1 , and Serge Belongie1,213Cornell University2Cornell TechIndian Institute of Technology RoorkeeAbstract. Estimating fundamental matrices is a classic problem in computervision. Traditional methods rely heavily on the correctness of estimated key-pointcorrespondences, which can be noisy and unreliable. As a result, it is difficult forthese methods to handle image pairs with large occlusion or significantly differentcamera poses. In this paper, we propose novel neural network architectures toestimate fundamental matrices in an end-to-end manner without relying on pointcorrespondences. New modules and layers are introduced in order to preservemathematical properties of the fundamental matrix as a homogeneous rank-2matrix with seven degrees of freedom. We analyze performance of the proposedmodels using various metrics on the KITTI dataset, and show that they achievecompetitive performance with traditional methods without the need for extractingcorrespondences.Keywords: Fundamental Matrix · Epipolar Geometry · Deep Learning · Stereo.The Fundamental matrix (F-matrix) contains rich information relating two stereo images.The ability to estimate fundamental matrices is essential for many computer visionapplications such as camera calibration and localization, image rectification, depthestimation and 3D reconstruction. The current approach to this problem is based ondetecting and matching local feature points, and using the obtained correspondences tocompute the fundamental matrix by solving an optimization problem about the epipolarconstraints [27, 16]. The performance of such methods is highly dependent on theaccuracy of the local feature matches, which are based on algorithms such as SIFT .However, these methods are not always reliable, especially when there is occlusion, largetranslation or rotation between images of the scene.In this paper, we propose end-to-end trainable convolutional neural networks forF-matrix estimation that do not rely on key-point correspondences. The main challengeof directly regressing the entries of the F-matrix is to preserve its mathematical properties as a homogeneous rank-2 matrix with seven degrees of freedom. We propose areconstruction module and a normalization layer (Sec. 2.2) to address this challenge.We demonstrate that by using these layers, we can accurately estimate the fundamentalmatrix, while a simple regression approach does not yield good results. Our detailed* Indicates equal contribution
2O. Poursaeed, G. Yang, A. Prakash, Q. Feng, and H. Jiang, B. Hariharan, S. Belongienetwork architectures are presented in Sec. 2. Empirical experiments are performed onthe KITTI dataset  in Sec. 3. The results indicate that we can achieve competitiveresults with traditional methods without relying on correspondences.1Background and Related Work1.1Fundamental Matrix and Epipolar GeometryWhen two cameras view the same 3D scene from different viewpoints, geometricrelations among the 3D points and their projections onto the 2D plane lead to constraintson the image points. This intrinsic projective geometry is referred to as the epipolargeometry, and is encapsulated by the fundamental matrix F. This matrix only dependson the cameras’ internal parameters and their relative pose, and can be computed as:F K2 T [t] RK1 1(1)where K1 and K2 represent camera intrinsics, and R and [t] are the relative camerarotation and translation respectively . More specifically: fi 1 0 cx Ki 0 fi 1 cy (2)0 0 1 0 tz tyt tz 0 tx ty tx 0(3)R Rx (rx )Ry (ry )Rz (rz )(4)in which (cx , cy )T is the principal point of the camera, fi is the focal length of camerai 1, 2, and tx , ty and tz are the relative displacements along the x, y and z axesrespectively. R is the rotation matrix which can be decomposed into rotations along x, yand z axes. We assume that the principal point is in the middle of the image plane.While the fundamental matrix is independent of the scene structure, it can be computed from correspondences of projected scene points alone, without requiring knowledge of the cameras’ internal parameters or relative pose. If p and q are matching pointsin two stereo images, the fundamental matrix F satisfies the equation:q T Fp 0(5)Writing p (x, y, 1)T and q (x0 , y 0 , 1)T and F [fij ], equation 5 can be written as:x0 xf11 x0 yf12 x0 f13 y 0 xf21 y 0 yf22 y 0 f23 xf31 yf32 f33 0. (6)Let f represent the 9-vector made up of the entries of F. Then equation 6 can be writtenas:(x0 x, x0 y, x0 , y 0 x, y 0 y, y 0 , x, y, 1)f 0(7)
Deep Fundamental Matrix Estimation without CorrespondencesA set of linear equations can be obtained from n point correspondences: x01 x1 x01 y1 x01 y10 x1 y10 y1 y10 x1 y1 1 . . . . Af . . . . f 0 .000000xn xn xn yn xn yn xn yn yn yn xn yn 13(8)Various methods have been proposed for estimating fundamental matrices based onequation 8. The simplest method is the eight-point algorithm which was proposed byLonguet-Higgins . Using (at least) 8 point correspondences, it computes a (leastsquares) solution to equation 8. It enforces the rank-2 constraint using Singular ValueDecomposition (SVD), and finds a matrix with the minimum Frobenius distance tothe computed (rank-3) solution. Hartley  proposed a normalized version of theeight-point algorithm which achieves improved results and better stability. The algorithminvolves translation and scaling of the points in the image before formulating the linearequation 8.The Algebraic Minimization algorithm uses a different procedure for enforcing therank-2 constraint. It tries to minimize the algebraic error Akf k subject to kf k 1. Ituses the fact that we can write the singular fundamental matrix as F M[e] whereM is a non-singular matrix and [e] is a skew-symmetric matrix with e correspondingto the epipole in the first image. This equation can be written as f Em, where f andm are vectors comprised of entries of F and M, and E is a 9 9 matrix comprised ofelements of [e] . Then the minimization problem becomes:minimize kAEmk subject to kEmk 1(9)To solve this optimization problem, we can start from an initial estimate of F and set eas the generator of the right null space of F. Then we can iteratively update e and F tominimize the algebraic error. More details are given in .The Gold Standard geometric algorithm assumes that the noise in image pointmeasurements obeys a Gaussian distribution. It tries to find the Maximum Likelihoodestimate of the fundamental matrix which minimizes the geometric distanceXd(pi , p̂i )2 d(qi , q̂i )2(10)iin which pi and qi are true correspondences satisfying equation 5, and p̂i and q̂i are theestimated correspondences.Another algorithm uses RANSAC  to compute the fundamental matrix. It computes interest points in each image, and finds correspondences based on proximityand similarity of their intensity neighborhood. In each iteration, it randomly samples7 correspondences and computes the F-matrix based on them. It then calculates there-projection error for each correspondence, and counts the number of inliers for whichthe error is less than a specified threshold. After sufficient number of iterations, itchooses the F-matrix with the largest number of inliers. A generalization of RANSACis MLESAC , which adopts the same sampling strategy as RANSAC to generateputative solutions, but chooses the solution that maximizes the likelihood rather than
4O. Poursaeed, G. Yang, A. Prakash, Q. Feng, and H. Jiang, B. Hariharan, S. Belongiejust the number of inliers. MAPSAC  (Maximum A Posteriori SAmple Consensus)improves MLESAC by being more robust against noise and outliers including Bayesianprobabilities in minimization. A global search genetic algorithm combined with a localsearch hill climbing algorithm is proposed in  to optimize MAPSAC algorithm forestimating fundamental matrices.  proposes an algorithm to cope with the problemof fundamental matrix estimation for binocular vision system used in wild field. It firstacquires the edge points using Canny edge detector, and then gets the pre-matched pointsby the GMM-based point set registration algorithm. It then computes the fundamentalmatrix using the RANSAC algorithm.  proposes to use adaptive penalty methods forvalid estimation of Essential matrices as a product of translation and rotation matrices.A new technique for calculating the fundamental matrix combined with feature linesis introduced in . The interested reader is referred to  for a survey of variousmethods for estimating the F-matrix.1.2Deep Learning for Multi-view GeometryDeep neural networks have achieved state-of-the-art performance on tasks such as imagerecognition [24, 18, 38, 37], semantic segmentation [26, 3, 43, 47], object detection [14,35, 34], scene understanding [23, 48, 32] and generative modeling [15, 33, 19, 44, 31] inthe last few years. Recently, there has been a surge of interest in using deep learning forclassic geometric problems in Computer Vision. A method for estimating relative camerapose using convolutional neural networks is presented in . It uses a simple convolutional network with spatial pyramid pooling and fully connected layers to compute therelative rotation and translation of the camera. An approach for camera re-localization ispresented in  which localizes a given query image by using a convolutional neuralnetwork for first retrieving similar database images and then predicting the relative posebetween the query and the database images with known poses. The camera location forthe query image is obtained via triangulation from two relative translation estimatesusing a RANSAC-based approach.  uses a deep convolutional neural network todirectly estimate the focal length of the camera using only raw pixel intensities as inputfeatures.  proposes two strategies for differentiating the RANSAC algorithm: using asoft argmax operator, and probabilistic selection.  leverages deep neural networksfor 6-DOF tracking of rigid objects. presents a deep convolutional neural network for estimating the relative homography between a pair of images. A more complicated algorithm is proposed in which contains a hierarchy of twin convolutional regression networks to estimate thehomography between a pair of images.  introduces two deep convolutional neuralnetworks, MagicPoint and MagicWarp. MagicPoint extracts salient 2D points from asingle image. MagicWarp operates on pairs of point images (outputs of MagicPoint),and estimates the homography that relates the inputs.  proposes an unsupervisedlearning algorithm that trains a deep convolutional neural network to estimate planarhomographies. A self-supervised framework for training interest point detectors anddescriptors is presented in . A convolutional neural network architecture for geometricmatching is proposed in . It uses feature extraction networks with shared weightsand a matching network which matches the descriptors. The output of the matchingnetwork is passed through a regression network which outputs the parameters of the
Deep Fundamental Matrix Estimation without Correspondences5ConcatConv1Conv2Max-PoolImage FeaturesPosition FeaturesFig. 1. Single-Stream Architecture. Stereo images are concatenated and passed to a convolutionalneural network. Position features can be used to indicate where the final activations come fromwith respect to the full-size image.geometric transformation.  presents a model which takes a set of images and theircorresponding camera parameters as input and directly infers the 3D model.2Network ArchitectureWe leverage deep neural networks for estimating the fundamental matrix directly froma pair of stereo images. Each network consists of a feature extractor to obtain featuresfrom the images and a regression network to compute the entries of the F-matrix fromthe features.2.1Feature ExtractionWe consider two different architectures for feature extraction. In the first architecture,we concatenate the images across the channel dimension, and pass the result to a neuralnetwork to extract features. Figure 1 illustrates the network structure. We use twoconvolutional layers, each followed by ReLU and Batch Normalization . We use128 filters of size 3 3 in the first convolutional layer and 128 filters of size 1 1 inthe second layer. We limit the number of pooling layers to one in order not to lose thespatial structure in the images.Location Aware Pooling. As discussed in Sec. 1, the F-matrix is highly dependent onthe relative location of corresponding points in the images. However, down-samplinglayers such as Max Pooling discard the location information. In order to retain thisinformation, we keep all the indices of where the activations come from in the maxpooling layers. At the end of the network, we append the position of final features with
6O. Poursaeed, G. Yang, A. Prakash, Q. Feng, and H. Jiang, B. Hariharan, S. BelongieConv.ConvConv.ConcatConvConv1Conv2Image FeaturesPosition FeaturesMax-PoolFig. 2. Siamese Architecture. Images are first passed to two streams with shared weights. Theresulting features are concatenated and passed to the single-stream network as in figure 1. Positionfeatures can be used with respect to the concatenated features.respect to the full-size image. Each location is indexed with an integer in [1, h w c]normalized to be within the range [0, 1], in which h, w and c are the height, width andchannel dimensions of the image respectively. In this way, each feature has a positionindex indicating from where it comes from. This helps the network to retain the locationinformation and to provide more accurate estimates of the F-matrix.The second architecture is shown in figure 2. We first process each of the input imagesin a separate stream using an architecture similar to the Universal Correspondence Network (UCN) . Unlike the UCN architecture, we do not use Spatial Transformers in these streams since they can remove part of the information needed for estimatingrelative camera rotation and translation. The resulting features from these streams arethen concatenated, and passed to a single-stream network similar to figure 1. We can useposition features in the single-stream network as discussed previously. These featurescapture the position of final features the with respect to the concatenated features at theend of the two streams. We refer to this architecture as ‘Siamese’. As we show in Sec. 3,this network outperforms the Single-Stream one. We also consider using only the UCNwithout the single-stream network. The results, however, are not competitive with theSiamese architecture.2.2RegressionA simple approach for computing the fundamental matrix from the features is to passthem to fully-connected layers, and directly regress the nine entries of the F-Matrix. We
Deep Fundamental Matrix Estimation without Correspondences7Fig. 3. Different regression methods for predicting F-matrix entries from the features. The architecture to directly regress the entries of the F-matrix is shown on the left. The network with thereconstruction and normalization layers is shown on the right, and is able to estimate homogeneousF-matrices with rank two and seven degrees of freedom.can then normalize the result to achieve scale-invariance. This approach is shown infigure 3 (left). The main issue with this approach is that the predicted matrix might notsatisfy all the mathematical properties required for a fundamental matrix as a rank-2matrix with seven degrees of freedom. In order to address this issue, we introduceReconstruction and Normalization layers in the following.F-matrix Reconstruction Layer. We consider equation 1 to reconstruct the fundamental matrix:F̂ K2 T [t] RK1 1(11)we need to determine eight parameters (f1 , f2 , tx , ty , tz , rx , ry , rz ) as shown in equations (2–4). Note that the predicted F̂ is differentiable with respect to these parameters.Hence, we can construct a layer that takes these parameters as input, and outputs afundamental matrix F̂. This approach guarantees that the reconstructed matrix has ranktwo. Figure 3 (right) illustrates the Reconstruction layer.Normalization Layer. Considering that the F-matrix is scale-invariant, we also use aNormalization layer to remove another degree of freedom for scaling. In this way, theestimated F-matrix will have seven degrees of freedom and rank two as desired. Thecommon practice for normalization is to divide the F-matrix by its last entry. We callthis method ETR-Norm. However, since the last entry of the F-matrix could be close tozero, this can result in large entries, and training can become unstable. Therefore, wepropose two alternative normalization methods.FBN-Norm: We divide all entries of the F-matrix by its Frobenius norm, so that all thematrices live on a 9-sphere of unit norm. Let kFkF denote the Frobenius norm of matrixF. Then the normalized fundamental matrix is:NF BN (F) kFk 1F F(12)ABS-Norm: We divide all entries of the F-matrix by its maximum absolute value, sothat all entries are restricted within [ 1, 1] range:NABS (F) (max Fi,j ) 1 Fi,j(13)
8O. Poursaeed, G. Yang, A. Prakash, Q. Feng, and H. Jiang, B. Hariharan, S. BelongieDuring training, the normalized F-matrices are compared with the ground-truthusing both L1 and L2 losses. We provide empirical results to study how each of thesenormalization methods influences performance and stability of training in Sec. 3.Epipolar Parametrization Given that the F-matrix has a rank of two, an alternativeparametrization is specifying the first two columns f1 and f2 and the coefficients α and βsuch that f3 αf1 βf2 . Normalization layer can still be used to achieve scale-invariance.The coordinates of the epipole occur explicitly in this parametrization: (α, β, 1)T isthe right epipole for the F-matrix . The corresponding regression architecture issimilar to figure 3, but we interpret the final eight values differently: the first six elementsrepresent the first two columns and the last two represent the coefficient for combiningthe columns. As we will show in Sec. 4 this parametrization works particularly well fornormalizing with respect to the last entry (ETR-Norm). The main disadvantage of thismethod is that it does not work when the first two columns of F are linearly dependent.In this case, it is not possible to write the third column in terms of the first two columns.3ExperimentsTo evaluate whether our models can successfully learn F-matrices, we train models withvarious configurations and compare their performance based on the metrics defined inSec. 3.1. The baseline model (Base) uses neither position features nor the reconstructionmodule. The POS model utilizes the position features on top of the Base model. Epipolarparametrization (Sec. 2.2) is used for the EPI model. EPI POS uses the positionfeatures with epipolar parametrization. The REC model is the same as Base but uses thereconstruction module. Finally, the REC POS model uses both the position featuresand the reconstruction module.We use the KITTI dataset for training our models. The dataset has been recordedfrom a moving platform while driving in and around Karlsruhe, Germany. We use 1800images from the raw stereo data in the ‘City’ category. Ground truth F-matrices areobtained using the ground-truth camera parameters. The same normalization methodsare used for both the estimated and the ground truth F-matrices. The feature extractorand the regression network are trained jointly in an end-to-end manner.3.1Evaluation MetricsWe use the following metrics to measure how well the F-matrix satisfies the epipolarconstraint (equation 5) according to the hel
Deep Fundamental Matrix Estimation without Correspondences Omid Poursaeed * 1;2, Guandao Yang , Aditya Prakash 3, Qiuren Fang , Hanqing Jiang 1, Bharath Hariharan , and Serge Belongie;2 1 Cornell University 2 Cornell Tech 3 Indian Institute of Technology Roorkee Abstract. Estimating fundamental matrices is a classic problem in computer
CONTENTS CONTENTS Notation and Nomenclature A Matrix A ij Matrix indexed for some purpose A i Matrix indexed for some purpose Aij Matrix indexed for some purpose An Matrix indexed for some purpose or The n.th power of a square matrix A 1 The inverse matrix of the matrix A A The pseudo inverse matrix of the matrix A (see Sec. 3.6) A1 2 The square root of a matrix (if unique), not elementwise
CONTENTS CONTENTS Notation and Nomenclature A Matrix A ij Matrix indexed for some purpose A i Matrix indexed for some purpose Aij Matrix indexed for some purpose An Matrix indexed for some purpose or The n.th power of a square matrix A 1 The inverse matrix of the matrix A A The pseudo inverse matrix of the matrix A (see Sec. 3.6) A1 2 The sq
Further Maths Matrix Summary 1 Further Maths Matrix Summary A matrix is a rectangular array of numbers arranged in rows and columns. The numbers in a matrix are called the elements of the matrix. The order of a matrix is the number of rows and columns in the matrix. Example 1 [is a ] 3 by 2 or matrix as it has 3 rows and 2 columns. Matrices are .
A spreadsheet template for Three Point Estimation is available together with a Worked Example illustrating how the template is used in practice. Estimation Technique 2 - Base and Contingency Estimation Base and Contingency is an alternative estimation technique to Three Point Estimation. It is less
Introduction The EKF has been applied extensively to the ﬁeld of non-linear estimation. General applicationareasmaybe divided into state-estimation and machine learning. We further di-vide machine learning into parameter estimation and dual estimation. The framework for these areas are brieﬂy re-viewed next. State-estimation
Diagonalization of a PH matrix Proposition : Let H(z) be a PH matrix, does there exist U(z) a PU matrix such that : Ue(z)H(z)U(z) (z) with (z) a Laurent polynomial diagonal matrix? (an hermitian matrix is diagonalizable by a unitary matrix) not always true (see example) if exist, "eigen
The identity matrix for multiplication for any square matrix A is the matrix I, such that IA A and AI A . A second-order matrix can be represented by . Since , the matrix is the identity matrix for multiplication for any second-order matrix. Multiplicative
matrix. On the next screen select 2:Matrix for type, enter a name for the matrix and the size of the matrix. This will result in a screen showing a matrix of the appropriate size that is filled with zeros. Fill in the matrix with the values (either numerical or variable).
Matrix Laplace transform method Matrix Bernstein inequality Application: random features Matrix concentration 3-5. Matrix theory background. Matrix function Suppose the eigendecom
Diagonalization Diagonalization problem: For a square matrix A, does there exist an invertible matrix P such that P-1AP is diagonal? Diagonalizable matrix: A square matrix A is called diagonalizable if there exists an invertible matrix P such that P-1AP is a diagonal matrix. Notes: (P diagonalizes
1 Solving Linear Systems of Equations 1.1 Matrix Algebra Deﬁnition 1: An m-by-n real matrix is a table of m rows and n columns of real numbers. We say that the matrix has dimensions m-by-n. The plural of matrix is matrices. Remarks: 1.Often we write a matrix A (a ij), indicating that the matrix under consideration may be refer
Risk Matrix A matrix to classify risk categories for subsequent control with severity and likelihood levels as the two factors determining risk. Common risk matrices include the 3x3 matrix, 5x4 matrix, 5x5 matrix and the 7x7 matrix. Organisations may develop mat
2 Problems and Solutions Problem 4. A square matrix Aover C is called skew-hermitian if A A. Show that such a matrix is normal, i.e., we have AA AA. Problem 5. Let Abe an n nskew-hermitian matrix over C, i.e. A A. Let U be an n n unitary matrix, i.e., U U 1. Show that B: U AUis a skew-hermitian matrix. Problem 6. Let A, X, Y be n .
Variational Bayesian Sparse Additive Matrix Factorization 3 2.1 Examples of Factorization In standard MF, an observed matrix V RL M is modeled by a low rank target matrix U RL M contaminated with a random noise matrix E RL M. V U E. Then the target matrix U is decomposed into the product of two matrices A RM H and B RL H: Ulow-rank BA H h 1
nonlinear state estimation problem. For example, the aug-mented state approach turns joint estimation of an uncertain linear system with afne parameter dependencies into a bilinear state estimation problem. Following this path, it is typically difcult to provide convergence results . Joint parameter and state estimation schemes that do provide
Little is known about how deep-sea litter is distributed and how it accumulates, and moreover how it affects the deep-sea floor and deep-sea animals. The Japan Agency for Marine-Earth Science and Technology (JAMSTEC) operates many deep-sea observation tools, e.g., manned submersibles, ROVs, AUVs and deep-sea observatory systems.
2.3 Deep Reinforcement Learning: Deep Q-Network 7 that the output computed is consistent with the training labels in the training set for a given image.  2.3 Deep Reinforcement Learning: Deep Q-Network Deep Reinforcement Learning are implementations of Reinforcement Learning methods that use Deep Neural Networks to calculate the optimal policy.
8.2 The fundamental matrix F 223 ee/ l x / H X x/ π π Fig. 8.5. A point x in one image is transferred via the plane ˇ to a matching point x0 in the second image. The epipolar line through x 0is obtained by joining x to the epipole e0. In symbols one may write x 0 Hˇx and l 0 [e] x0 [e] Hˇx Fx where F [e0] Hˇ is the fundamental matrix.
matrix Ais known, and we focus on weight estimation. One of the most extensively studied problems in weight estimation is blem formulation for graph Laplacian estimation is given as follows: minimize Θ Tr (ΘS) logdet( Θ) α vec(Θ) 1 subject to Θ L(A), (9) where α 0is the regularization .
How are you currently supporting your local tourism ADVENTURE INDUSTRY RESPONDENTS: OVERVIEW businesses concerning COVID-19? Tourism boards are primarily supporting the local industry through open communication, and by providing tools, resources and information to help members weather the crisis. % Percentage of respondents . 29 ORGANIZATIONAL CONCERNS (Tourism Boards) ATTA 2020 29. Q36 .