Homography from two orientation- and scale-covariant features
Daniel Barath Zuzana Kukelova



















Homography from two orientation- and scale-covariant features
    Daniel Barath^12, and Zuzana Kukelova^1

^1 Centre for Machine Perception, Department of Cybernetics 

  Czech Technical University, Prague, Czech Republic 

  ^2 Machine Perception Research Laboratory, 
  MTA SZTAKI, Budapest, Hungary 

    barath.daniel@sztaki.mta.hu

    December 30, 2023
==================================================================================================================================================================================================================================================================================





This paper proposes a geometric interpretation of the angles and scales which the orientation- and scale-covariant feature detectors, e.g. SIFT, provide. 
Two new general constraints are derived on the scales and rotations which can be used in any geometric model estimation tasks.
Using these formulas, two new constraints on homography estimation are introduced. 
Exploiting the derived equations, a solver for estimating the homography from the minimal number of two correspondences is proposed.
Also, it is shown how the normalization of the point correspondences affects the rotation and scale parameters, thus achieving numerically stable results.
Due to requiring merely two feature pairs, robust estimators, e.g. RANSAC, do significantly fewer iterations than by using the four-point algorithm.
When using covariant features, e.g. SIFT, the information about the scale and orientation is given at no cost. 
The proposed homography estimation method is tested in a synthetic environment and on publicly available real-world datasets.    





§ INTRODUCTION


This paper addresses the problem of interpreting, in a geometrically justifiable manner, the rotation and scale which the orientation- and scale-covariant feature detectors, e.g. SIFT <cit.> or SURF <cit.>, provide. Then, by exploiting these new constraints, we involve all the obtained parameters of the SIFT features (i.e. the  point coordinates, angle, and scale) into the homography estimation procedure. 
In particular, we are interested in the minimal case, to estimate a homography from solely two correspondences.   

Nowadays, a number of algorithms exist for estimating or approximating geometric models, e.g. homographies, using affine-covariant features. 
A technique, proposed by Perdoch et al. <cit.>, approximates the epipolar geometry from one or two affine correspondences by converting them to point pairs.   
Bentolila and Francos <cit.> proposed a solution for estimating the fundamental matrix using three affine features. 
Raposo et al. <cit.> and Barath et al. <cit.> showed that two correspondences are enough for estimating the relative camera motion. 
Moreover, two feature pairs are enough for solving the semi-calibrated case, i.e. when the objective is to find the essential matrix and a common unknown focal length <cit.>. 
Also, homographies can be estimated from two affine correspondences <cit.>, and, in case of known epipolar geometry, from a single correspondence <cit.>. 
There is a one-to-one relationship between local affine transformations and surface normals <cit.>. 
Pritts et al. <cit.> showed that the lens distortion parameters can be retrieved using affine features. 




Affine correspondences encode higher-order information about the scene geometry. This is the reason why the previously mentioned algorithms solve geometric estimation problems exploiting fewer features than point correspondence-based methods. This implies nevertheless their major drawback: obtaining affine features accurately (e.g. by Affine SIFT <cit.>, MODS <cit.>, Hessian-Affine, or Harris-Affine <cit.> detectors) is time-consuming and, thus, is barely doable in time-sensitive applications.


Most of the widely-used feature detectors provide parts of the affine feature. 
For instance, there are detectors obtaining oriented features, e.g. ORB <cit.>, or there are ones providing also the scales, e.g. SIFT <cit.> or SURF <cit.>.  
Exploiting this additional information is a well-known approach in, for example, wide-baseline matching <cit.>. Yet, the first papers <cit.> involving them into geometric model estimation were published just in the last few years. 
In <cit.>, the feature orientations are involved directly in the essential matrix estimation. 
In <cit.>, the fundamental matrix is assumed to be a priori known and an algorithm is proposed for approximating a homography exploiting the rotations and scales of two SIFT correspondences. The approximative nature comes from the assumption that the scales along the axes are equal to the SIFT scale and the shear is zero. In general, these assumptions do not hold. 
The method of <cit.> approximates the fundamental matrix by enforcing the geometric constraints of affine correspondences on the epipolar lines. Nevertheless, due to using the same affine model as in <cit.>, the estimated epipolar geometry is solely an approximation. 
In <cit.>, a two-step procedure is proposed for estimating the epipolar geometry. First, a homography is obtained from three oriented features. Finally, the fundamental matrix is retrieved from the homography and two additional correspondences. Even though this technique considers the scales and shear as unknowns, thus estimating the epipolar geometry instead of approximating it, the proposed decomposition of the affine matrix is not justified theoretically. Therefore, the geometric interpretation of the feature rotations is not provably valid. 
A recently published paper <cit.> proposes a way of recovering full affine correspondences from the feature rotation, scale, and the fundamental matrix. Applying this method, a homography is estimated from a single correspondence in case of known epipolar geometry. Still, the decomposition of the affine matrix is ad hoc, and is, therefore, not a provably valid interpretation of the SIFT rotations and scales. Moreover, in practice, the assumption of the known epipolar geometry restricts the applicability of the method. 

The contributions of this paper are: (i) we provide a geometrically valid way of interpreting orientation- and scale-covariant features approaching the problem by differential geometry. (ii) Building on the derived formulas, we propose two general constraints which hold for covariant features. (iii) These constraints are then used to derive two new formulas for homography estimation and (iv), based on these equations, a solver is proposed for estimating a homography matrix from two orientation- and scale-covariant feature correspondences. 
This additional information, i.e. the scale and rotation, is given at no cost when using most of the widely-used feature detectors, e.g. SIFT or SURF.
It is validated both in a synthetic environment and on more than 10 000 publicly available real image pairs that the solver accurately recovers the homography matrix. Benefiting from the number of correspondences required, robust estimation, e.g. by GC-RANSAC <cit.>, is two orders of magnitude faster than by combining it with the standard techniques, e.g. four-point algorithm <cit.>.     



§ THEORETICAL BACKGROUND


Affine correspondence
(_1, _2, ) is a triplet, where _1 = [u_1   v_1   1]^ and _2 = [u_2   v_2   1]^ are a corresponding homogeneous point pair in two images and 
is a 2 × 2 linear transformation which is called local affine transformation. Its elements in a row-major order are: a_1, a_2, a_3, and a_4. To define , we use the definition provided in <cit.> as it is given as the first-order Taylor-approximation of the 3D→2D projection functions. For perspective cameras, the formula for  is the first-order approximation of the related homography matrix
as follows: 


    [                            a_1                              = ∂ u_2/∂ u_1 = h_1 - h_7 u_2/s,                                                           a_2                              = ∂ u_2/∂ v_1 = h_2 - h_8 u_2/s,;                            a_3                              = ∂ v_2/∂ u_1 = h_4 - h_7 v_2/s,                                                           a_4                              = ∂ v_2/∂ v_1 = h_5 - h_8 v_2/s, ]


where u_i and v_i are the directions in the ith image (i ∈{1,2}) and s = u_1 h_7 + v_1 h_8 + h_9 is the projective depth. The elements of  in a row-major order are: h_1, h_2, ..., h_9.

The relationship of an affine correspondence and a homography is described by six linear equations. Since an affine correspondence involves a point pair, the well-known equations (from _1 ∼_2) hold <cit.>. They are as follows:

    u_1 h_1 + v_1 h_2 + h_3 - u_1 u_2 h_7 - v_1 u_2 h_8 - u_2 h_9   = 0, 
    
            u_1 h_4 + v_1 h_5 + h_6 - u_1 v_2 h_7 - v_1 v_2 h_8 - v_2 h_9   = 0.


After re-arranging (<ref>), four additional linear constraints are obtained from  which are the following.


    h_1 - ( u_2 + a_1 u_1  ) h_7 - a_1 v_1 h_8 - a_1 h_9   = 0, 
    
        	h_2 - ( u_2 + a_2 v_1  ) h_8 - a_2 u_1 h_7 - a_2 h_9   = 0, 
    
        	h_4 - ( v_2 + a_3 u_1  ) h_7 - a_3 v_1 h_8 - a_3 h_9   = 0, 
    
        	h_5 - ( v_2 + a_4 v_1  ) h_8 - a_4 u_1 h_7 - a_4 h_9   = 0.


Consequently, an affine correspondence provides six linear equations for the elements of the related homography. 




§ AFFINE TRANSFORMATION MODEL


In this section, the interpretation of the feature scales and rotations are discussed.
Two new constraints that relate the elements of the affine transformation to the feature scale and rotation are derived.
These constraints are general, and they can be used for estimating different geometric models, e.g. homographies or fundamental matrices, using orientation- and scale-covariant features.
In this paper, the two constraints are used to derive a solver for homography estimation from two correspondences.

For the sake of simplicity, we use SIFT as an alias for all the orientation- and scale-covariant detectors. The formulas hold for all of them.





 §.§ Interpretation of the SIFT output


Reflecting the fact that we are given a scale q_i ∈ℝ and rotation α_i ∈ [0, 2 π) independently in each image (i ∈{ 1, 2 }; see Fig. <ref>), the objective is to define affine correspondence  as a function of them. 

For this problem, approaches were proposed in the recent past <cit.>. None of them were nevertheless proven to be a valid interpretation.   

To understand the SIFT output, we exploit the definition of affine correspondences proposed in <cit.>. In <cit.>,  is defined as the multiplication of the Jacobians of the projection functions in the two images as follows:


    A = J_2 J_1^-1,


where J_1 and J_2 are the Jacobians of the 3D → 2D projection functions. Proof is in Appendix <ref>.
For the ith Jacobian, the following is a possible decomposition:


    J_i = R_i U_i = [  cos(α_i) -sin(α_i);  sin(α_i)  cos(α_i) ][ q_u,i   w_i;     0 q_v,i ],


where angle α_i is the rotation in the ith image, q_u,i and q_v,i are the scales along axes u and v, and w_i is the shear (i ∈{1,2}). Let us use the following notation: c_i = cos(α_i) and s_i = sin(α_i).
The equation for the inverse matrix becomes


    J_i^-1 = 
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        1/c_i^2 q_u,i q_v,i + s_i^2 q_u,i q_v,i[ s_i w_i + c_i q_v,i s_i q_v,i - c_i w_i;          -s_i q_u,i           c_i q_u,i ].


The denominator can be formulated as follows: (c_i^2 + s_i^2) q_u,i q_v,i, where c_i^2 + s_i^2 is a trigonometric identity and equals to one.

After multiplying the matrices in (<ref>), the following equations are given for the affine elements: 


    a_1 = c_2 q_u,2 (s_1 w_1 + c_1 q_v,1) - s_1 q_u,1 (c_2 w_2 - s_2 q_v,2)/q_u,1 q_v,1
    
        a_2 = c_2 q_u,2 (s_1 q_v,1 - c_1 w_1) + c_1 q_u,1 (c_2 w_2 - s_2 q_v,2)/q_u,1 q_v,1
    
        a_3 = s_2 q_u,2 (s_1 w_1 + c_1 q_v,1) - s_1 q_u,1 (s_2 w_2 + c_2 q_v,2)/q_u,1 q_v,1
    
        a_4 = s_2 q_u,2 (s_1 q_v,1 - c_1 w_1) + c_1 q_u,1 (s_2 w_2 + c_2 q_v,2)/q_u,1 q_v,1


These formulas show how the affine elements relate to α_i, the scales along axes u and v and shears w_i.

In case of having orientation- and scale-covariant features, e.g. SIFT, the known parameters are the rotation α_i of the feature in the ith image and a uniform scale q_i. It can be easily seen that the scale q_i is interpreted as follows:






    q_i = J_i = q_u,i q_v,i.


Therefore, our goal is to derive constraints that relate affine elements of  to the orientations α_i and scales q_i of the features in the first and second images.
We will derive such constraints by eliminating the scales along axes q_u,i and q_v,i and the shears w_i from equations (<ref>)-(<ref>).
To do this, we use an approach based on the elimination ideal theory <cit.>. Elimination ideal theory is a classical algebraic method for eliminating variables from polynomials of several variables.
This method was recently used in <cit.> for eliminating unknowns from equations that are not dependent on input measurements. 
Here, we use the method in a slightly different way. We first create the ideal I <cit.> generated by polynomials (<ref>)-(<ref>), polynomial (<ref>) and trigonometric identities c_i^2 + s_i^2 = 1 for i ∈{1,2}. Note that here we consider all elements of these polynomials, including c_i and s_i, as unknowns. 
Then we compute generators of the elimination ideal I_1 = I ∩ℂ[a_1,a_2,a_3,a_4,q_1,q_2,s_1,c_1,s_2,c_2] <cit.>.
The generators of I_1 do not contain q_u,i, q_v,i and w_i. 
The elimination ideal I_1 is generated by two polynomials:


    q_1^2 a_2 a_3 - q_1^2 a_1 a_4 + q_1 q_2 = 0,
    
        c_1 s_2 q_1 a_1 + s_1 s_2 q_1 a_2 - c_1 c_2 q_1 a_3 - c_2 s_1 q_1 a_4 = 0.


Generators (<ref>)-(<ref>) can be computed using a computer algebra system, e.g. Macaulay2 <cit.>. The input code for Macaulay2 is in the supplementary material.










The new constraints relate the elements of  to the scales and rotations of the features in both images. Note that both these equations can be divided by q_1 ≠ 0. After this simplification, (<ref>) corresponds to = q_2 / q_1 = q and equation (<ref>) relates the rotations of the features to the elements of  .
The two new constraints are general, and they can be used for estimating different geometric models, e.g. homographies or fundamental matrices, using orientation- and scale-covariant detectors.
Next, we use (<ref>)-(<ref>) to derive new constraints on a homography.


 



§ HOMOGRAPHY FROM TWO CORRESPONDENCES


In this section,  we derive new constraints 
that relates  to the feature scales and rotations in the two images.
Then a solver is proposed to estimate  from two SIFT correspondences based on these new constraints.
Finally, 
we discuss how the widely-used normalization of the point correspondences <cit.> affects the output of orientation- and scale-covariant detectors and subsequently the new constraints. 



 §.§ Homography and covariant features

First, we derive constraints 
that relates the homography  to the scales and rotations of the features in the first and second images.
To do this, we combine constraints (<ref>) and (<ref>) derived in previous section with the constraints on the homography matrix (<ref>).

Constraints (<ref>) and (<ref>) cannot be directly substituted into (<ref>). However, we can use a similar approach as in the previous section for deriving (<ref>) and (<ref>). First, ideal J generated by six polynomials (<ref>), (<ref>) and (<ref>) is constructed. Then the unknown elements of the affine transformation  are eliminated from the generators of J.
We do this by computing the generators of 

J_1 = J ∩ℂ[h_1,…,h_9,u_1,v_1,u_2,v_2,q_1,q_2,s_1,c_1,s_2,c_2].

The elimination ideal J_1 is generated by two polynomials:

    h_8u_2s_1s_2+h_7u_2s_2c_1-h_8v_2s_1c_2-h_7v_2c_1c_2+
    
    -h_2s_1s_2-h_1s_2c_1+h_5s_1c_2+h_4c_1c_2 = 0,
    
    
    h_7^2u_1^2q_2+2h_7h_8u_1v_1q_2+h_8^2v_1^2q_2+h_5h_7u_2q_1+
    
    -h_4h_8u_2q_1-h_2h_7v_2q_1+h_1h_8v_2q_1+2h_7h_9u_1q_2+
    
    2h_8h_9v_1q_2+ h_2h_4q_1-h_1h_5q_1+h_9^2q_2 = 0.


The input code for Macaulay2 used to compute these generators is provided as supplementary material.

Polynomials (<ref>) and (<ref>) are new constraints that relate the homography matrix to the scales and rotations of the features in the first and second images. These constraints will help us for recovering  from two orientation- and scale-covariant feature correspondences. 




 §.§ 2-SIFT solver


Constraint (<ref>) is linear in the elements of . For two SIFT correspondences, two such equations are given, which, together with the four equations for point correspondences (<ref>), result in six homogeneous linear equations in the nine elements of .
In matrix form, these equations are: 


    M h = 0,


where M is a 6×9 coefficient matrix and h is a vector of 9 
elements of homography matrix .
For two  SIFT correspondences in two views, coefficient matrix M has a three-dimensional null space.
Therefore, the homography matrix can be parameterized by two unknowns as


    H = x H_1 + y H_2 + H_3,


where H_1,H_2,H_3 are created from the 3D null space of M and x and y are new unknowns.

Now we can plug the parameterization (<ref>) into constraint (<ref>). For two SIFT correspondences, this 
results in two quadratic equations in two unknowns. Such equations have four solutions and they can be easily solved using e.g. the or the resultant based method <cit.>.
Here, we use the solver based on method that can be created using the automatic generator <cit.>. This solver performs Gauss-Jordan elimination of a 6×10 template matrix which contains just monomial multiples of the two input equations. Then the solver extracts solutions to x and y from the eigenvectors of a 4×4 multiplication matrix that is extracted from the template matrix. 
Finally, up to four real solutions to  are computed by substituting solutions for x and y to (<ref>).

Note that we do not know any degeneracies of the proposed solver which can occur in real life. For instance, the degeneracy of the four-point algorithm, i.e. the points are co-linear, is not a degenerate case for the 2SIFT solver.  



 §.§ Normalization of the affine parameters


The normalization of the point coordinates is a crucial step to increase the numerical stability of  estimation <cit.>. 
Suppose that we are given a 3 × 3 normalizing transformation T_i transforming the center of gravity of the point cloud in the ith image to the origin and its average distance from it to √(2). The formula for normalizing  is as follows <cit.>:

 


    = T_2 
        [   0; 0 1 ]T_1^-1,


where  is the normalized affinity. Matrix T_i transforms the points by translating them (last column) and applying a uniform scaling (diagonal).
Due to the fact that the last column of T_i has no effect on the top-left 2 × 2 sub-matrix of the normalized affinity, the equation can be rewritten as follows:

= diag(t_2, t_2)   diag(1 / t_1, 1 / t_1) = t_2 / t_1 ,

where t_1 and t_2 are the scales of the normalizing transformations in the two images. 
Thus, for normalizing the affine transformation, it has to be multiplied by t_2 / t_1.


The scaling factor affects constraint (<ref>) which, for , has the form


    t^2q_1^2a_2a_3-t^2q_1^2a_1a_4+q_1q_2=0,

where t = t_1/t_2 and a_i are elements of . Consequently constraint (<ref>) for the normalized coordinates has the form 

    h_7^2u_1^2q_2t^2+2h_7h_8u_1v_1q_2t^2+h_8^2v_1^2q_2t^2+h_5h_7u_2q_1+
    
    -h_4h_8u_2q_1-h_2h_7v_2q_1+h_1h_8v_2q_1+2h_7h_9u_1q_2t^2+
    
    2h_8h_9v_1q_2t^2+ h_2h_4q_1-h_1h_5q_1+h_9^2q_2t^2 = 0.

Note that this normalization does not affect the structure of the derived 2SIFT solver. The only difference is that, for the normalized coordinates, the coefficients in the template matrix are multiplied by scale factor t as in (<ref>).



 



§ EXPERIMENTAL RESULTS


In this section, we compare the proposed solver (2SIFT) with the widely-used normalized four-point (4PT) algorithm <cit.> and a method using three oriented features <cit.> (3ORI) for estimating the homography. 



 §.§ Computational complexity


First, we compare the computational complexity of the competitor algorithms, see Table <ref>. The first row consists of the major steps of each solver. For instance, 6 × 9 SVD + 6 × 6 QR + 4 × 4 EIG means, that the major steps are: the SVD decomposition of a 6 × 9 matrix, the QR decomposition of a 6 × 6 matrix and the eigendecomposition of a 4 × 4 matrix. 
In the second row, the implied computational complexities are summed. 
In the third one, the number of correspondences required for the solvers are written. 
The fourth row lists example outlier ratios in the data. 
In the fifth one, the theoretical number of iterations of RANSAC <cit.> is written for each outlier ratio with confidence set to 0.99.
The last row shows the computational complexity, i.e. the complexity of one iteration multiplied by the number of iteration, of RANSAC combined with the minimal methods. 
It can be seen that the proposed method leads to significantly smaller computational complexity. 
Moreover, we believe that by designing a specific solver to our two quadratic equations in two unknowns, similarly as in <cit.>, the computational complexity of our solver can be even reduced. 



 §.§ Synthesized tests












To test the accuracy of the homographies obtained by the proposed method, first, we created a synthetic scene consisting of two cameras represented by their 3 × 4 projection matrices P_1 and P_2. 
They were located randomly on a center-aligned sphere. 
A plane with random normal was generated in the origin and ten random points, lying on the plane, were projected into both cameras. The points were at most one unit far from the origin.
To get the ground truth affine transformations, we calculated homography  by projecting four random points from the plane to the cameras and applying the normalized DLT <cit.> algorithm. 
The local affine transformation of each correspondence was computed from the ground truth homography by (<ref>). 
Note that  could have been calculated directly from the plane parameters. 
However, using four points promised an indirect but geometrically interpretable way of noising the affine parameters: adding noise to the coordinates of the four projected points. 
To simulate the SIFT orientations and scales,  was decomposed to J_1, J_2. 
Since the decomposition is ambiguous, α_1, q_u,1, q_v,1, w_1 were set to random values. J_1 was calculated from them. Finally, J_2 was calculated as J_2 = J_1.
Zero-mean Gaussian-noise was added to the point coordinates, and, also, to the coordinates which were used to estimate the affine transformations.

Fig. <ref> reports the numerical stability of the methods in the noise-free case. The frequencies (vertical axis), i.e. the number of occurrences in 100 000 runs, are plotted as the function of the log_10 average transfer error (in px; horizontal) computed from the estimated homography and the not used correspondences. 
It can be seen that all tested solvers are numerically stable.

Fig. <ref> plots the || H_est - H_gt ||_F errors as the function of image noise level σ (vertical axis) and the ratio (horizontal) of the camera distance, i.e. the radius of the sphere on which the cameras lie, and the object size. The homographies were normalized. The proposed 2SIFT algorithm (left) is less sensitive to the choice of both parameters than the 3ORI (middle) and 4PT (right) methods. 

Fig. <ref> reports the re-projection error (vertical; in pixels) as the function of the image noise σ with additional noise added to the SIFT orientations (left) and scales (right) besides the noise coming from the noisy affine transformations. 
In the top row, the error is plotted as the function of the image noise σ. 
The curves show the results on different noise levels in the orientations and scales.
In the bottom row, the error is plotted as the function of the orientation (left plot) and scale (right) noise. 
The noise in the point coordinates was set to 1.0 px. The scale noise for the left plot was set to 1%. The orientation noise for the right one was set to 1.
It can be seen that, even for large noise in the scale and orientation, the new solver performs reasonably well.



 §.§ Real world tests


To test the proposed method on real-world data, we downloaded the 
cmttAdelaideRMF[cs.adelaide.edu.au/ hwong/doku.php?id=data], 
cmttMulti-H[web.eee.sztaki.hu/ dbarath], cmttMalaga[www.mrpt.org/MalagaUrbanDataset] and cmttStrecha[https://cvlab.epfl.ch/] 
datasets. 
cmttAdelaideRMF and cmttMulti-H consist of image pairs of resolution from 455 × 341 to 2592 × 1944 and manually annotated (assigned to a homography or to the outlier class) correspondences. Since the reference point sets do not contain rotations and scales, we detected points applying the SIFT detector. 
The correspondences provided in the datasets were used to estimate ground truth homographies.
For each homography, we selected the points out of the detected SIFT correspondences which are closer than a manually set inlier-outlier threshold, i.e. 2 pixels. 

As robust estimator, we chose GC-RANSAC <cit.> since it is state-of-the-art and its implementation is available[<https://github.com/danini/graph-cut-ransac>]. 
GC-RANSAC is a locally optimized RANSAC with PROSAC <cit.> sampling.
For fitting to a minimal sample, GC-RANSAC used one of the compared methods, e.g. the proposed one. 
For fitting to a non-minimal sample, the normalized 4PT algorithm was applied. 

Given an image pair, the procedure to evaluate the estimators on cmttAdelaideRMF and cmttMulti-H is as follows: 

first, the ground truth homographies, estimated from the manually annotated correspondence sets, were selected one by one. For each homography:
(i) The correspondences which did not belong to the selected homography were replaced by completely random correspondences to reduce the probability of finding a different plane than what was currently tested. 
(ii) GC-RANSAC was applied to the point set consisting of the inliers of the homography and outliers. 
(iii) The estimated homography is compared to the ground truth one estimated from the manually selected inliers.
 


The cmttStrecha dataset consists of image sequences of buildings. 
All images are of size 3072 × 2048. 
The methods were applied to all possible image pairs in each sequence.

The cmttMalaga dataset was gathered entirely in urban scenarios with a car equipped with several sensors, including a high-resolution camera and five laser scanners. 15 video sequences are provided and we used every 10th image from each sequence. 
The ground truth projection matrices are provided for both datasets.

To get a reference correspondence set for each image pair in the cmttStrecha and cmttMalaga datasets, first, calculated the fundamental matrix from the ground truth camera poses provided in the datasets. 
SIFT detector was applied.
Correspondences were selected for which the symmetric epipolar distance was smaller than 1.0 pixel. 
RANSAC was applied to the filtered correspondences finding the most dominant homography with a threshold set to 1.0 pixel and confidence to 0.9999. 
The inliers of this homography were considered as a reference set. 
In case of having less then 50 reference points, the pair was discarded from the evaluation. 
In total, 852 image pairs were tested in the cmttStrecha dataset and 9 064 pairs in the cmttMalaga dataset. 

Example results are shown in Fig. <ref>. The inliers of the homography estimated by estimated by 2SIFT are drawn. Also, the number of iteration required for 2SIFT and 4PT and the ground truth inlier ratios are reported. In all cases, 2SIFT made significantly fewer iterations than 4PT.  

Table <ref> reports the results on the cmttAdelaideRMF (rows 2–4), cmttMulti-H (5–7) and cmttStrecha (8–10) datasets. 
The names of the datasets are written into the first column and the numbers of planes are in brackets. 
The names of the tested techniques are written in the first row. 
Each block, consisting of three rows, shows the mean re-projection error computed from the manually annotated correspondences and the estimated homographies (ϵ; in pixels; avg. of 100 runs on each pair); the number of samples drawn by the outer loop of GC-RANSAC (# iters.); and the processing time (in secs). 
The RANSAC confidence was set to 0.95 and the inlier-outlier threshold to 2 pixels. 
It can be seen that the proposed method has similar errors to that of the 4PT algorithm, but 2SIFT leads to 1–2 orders of magnitude speedup compared to 4PT. 


The results on the cmttMalaga dataset are shown in Figure <ref>.
The confidence of GC-RANSAC was set to 0.95 and the inlier-outlier threshold to 2.0 pixels. 
The reported properties are the average re-projection error (left; in pixels), processing time (middle; in seconds) and the average number of iterations (right). 
It can be seen that the re-projection errors of 4PT and 2SIFT are fairly similar

However, 2SIFT is significantly faster in all cases due to making much fewer iterations than 4PT. 



§ CONCLUSION


We proposed a theoretically justifiable interpretation of the angles and scales which the orientation- and scale-covariant feature detectors, e.g. SIFT or SURF, provide.
Building on this, two new general constraints are proposed for covariant features. 
These constraints are then exploited to derive two new formulas for homography estimation. 
Using the derived equations, a solver is proposed for estimating the homography from two correspondences. 
The new solver is numerically stable and easy to implement.
Moreover, it leads to results superior in terms of geometric accuracy in many cases. 
Also, it is shown how the normalization of the point correspondences 
affects the rotation and scale parameters.
Due to requiring merely two feature pairs, robust estimators, e.g. RANSAC, do significantly fewer iterations than by using the four-point algorithm. The method is tested in a synthetic environment and on publicly available real-world datasets consisting of thousands of image pairs. 
The source code is uploaded as supplementary material. 




§ PROOF THE AFFINE DECOMPOSITION



We prove that decomposition = J_2 J_1^-1, where J_i is the Jacobian of the projection function w.r.t. the directions in the ith image, is geometrically valid. 

Suppose that a three-dimensional point P = [ x y z ]^ lying on a continuous surface S is given. Its projection in the ith image is p_i = [ u_i v_i ]^. The projected coordinates, u_i and v_i, are determined by the projection functions Π_u, Π_v: ℝ^3 →ℝ as follows:  

u_i = Π^i_u(x,y,z), v_i = Π^i_v(x,y,z),

where the coordinates of the surface point are written in parametric form as


	x = 𝒳(u, v), y = 𝒴(u, v), z = 𝒵(u, v).




It is well-known in differential geometry <cit.> that the basis of the tangent plane at point P is written by the partial derivatives of S w.r.t. the spatial coordinates. The surface normal n is expressed by the cross product of the tangent vectors s_u and s_v where


s_u = [ ∂𝒳(u,v)/∂ u ∂𝒴(u,v)/∂ u ∂𝒵(u,v)/∂ u ]^,


and s_v is calculated similarly.

Finally, n = s_u ×s_v. 

Locally, around point P, the surface can be approximated by the tangent plane, therefore, the neighboring points in the ith image are written as the first-order Taylor-series as follows:


    p_i + Δ
    		
    	
    	[ Π_x(x, y, z); Π_y(x, y, z) ] + 
    	[ ∂Π_x^i(x, y, z)/∂ u ∂Π_x^i(x, y, z)/∂ v; ∂Π_y^i(x, y, z)/∂ u ∂Π_y^i(x, y, z)/∂ v ][ Δ u; Δ v ],


where [Δ v, Δ u]^ is the translation on surface S, and Δ x, Δ y are the coordinates of the implied translation added to p_i. 

It can be seen that transformation 𝐉_i mapping the infinitely close vicinity around point p_i in the ith image is given as


    𝐉_i = [ ∂Π_x^i(x, y, z)/∂ u ∂Π_x^i(x, y, z)/∂ v; ∂Π_y^i(x, y, z)/∂ u ∂Π_y^i(x, y, z)/∂ v ],


thus


    [ Δ x Δ y ]^≈J_i [ Δ u Δ v ]^.


The partial derivatives are reformulated using the chain rule. As an example, the first element it is as 


    ∂Π_x^i(x, y, z)/∂ u = 
        ∂Π_x^i(x, y, z)/∂ xx/∂ u + 
    ∂Π_x^i(x, y, z)/∂ xy/∂ u + 
        ∂Π_x^i(x, y, z)/∂ xz/∂ u = ∇ (Π_x^i)^𝐬_u,


where ∇Π_x^i is the gradient vector of Π_x w.r.t. coordinates x, y and z. Similarly,


    ∂Π_x^i/∂ v = ∇ (Π_x^i)^s_v,  ∂Π_y^i/∂ u = ∇ (Π_y^i)^s_u,  ∂Π_y^i/∂ v = ∇ (Π_y^i)^s_v,


Therefore, 𝐉_i can be written as


    𝐉_i = [ ∇ (Π_x^i)^; ∇ (Π_y^i)^ ][ s_u s_v ].


Local affine transformation 𝐀 transforming the infinitely close vicinity of point p_1 in the first image to that of p_2 in the second one is as follows:


    [ Δ x_2; Δ y_2 ] = 
    	𝐉_2 𝐉_1^-1[ Δ x_1; Δ y_1 ] = 
    	𝐀[ Δ x_1; Δ y_1 ].



ieee



