Basic Geometry

This is a simple task that demonstrates working with homogeneous planar points and lines.

1. Let the image area has an extent [1, 1] to [800, 600]. Draw its boundary. Use the image coordinate system, i.e., x-axis pointing right and y-axis pointing down.
2. In your solution, allow entering two pairs of points within this area and display them.
3. Calculate the straight line passing through the first pair and the straight line passing through the second pair. Use homogeneous representation. Display the intersection of each line with the image area.
4. Calculate the intersection of both lines and draw it, if it is inside the image area.
5. Apply the following homography to all entities (points, lines, image boundary) and draw the result to another figure.

  K = [ [ 1,     0.1,   0 ], 
        [ 0.1,   1,     0 ],
        [ 0.004, 0.002, 1 ] ]

Example result of this task is shown in figure 1.

Fig. 1: Example intersection

Fig. 2: Example intersection under the homography

For entering the points, the Matlab function ginput, or the python function matplotlib.pyplot.ginput, is suitable. Cross product of two vectors can be computed using the function cross or numpy.cross.

Develop a simulation of perspective camera projection – wire-frame model. Let the 3D object be given. The object is composed from two planar diagrams, that are connected. Coordinates of vertices of both diagrams X1 and X2 are:

X1 = [ [-0.5,  0.5, 0.5, -0.5, -0.5, -0.3, -0.3, -0.2, -0.2,  0,  0.5 ],
       [-0.5, -0.5, 0.5,  0.5, -0.5, -0.7, -0.9, -0.9, -0.8, -1, -0.5 ],
       [ 4,    4,   4,    4,    4,    4,    4,    4,    4,    4,  4   ] ]

X2 = [ [-0.5,  0.5, 0.5, -0.5, -0.5, -0.3, -0.3, -0.2, -0.2,  0,    0.5 ],
       [-0.5, -0.5, 0.5,  0.5, -0.5, -0.7, -0.9, -0.9, -0.8, -1,   -0.5 ],
       [ 4.5,  4.5, 4.5,  4.5,  4.5,  4.5,  4.5,  4.5,  4.5,  4.5,  4.5 ] ]

Wire-frame model contains edges, that connects vertices in X1 and X2 in given order, and additionally it contains edges connecting vertices between X1 and X2, such that the vertex X1(:,i) is connected to the vertex X2(:,i), ∀ i.

The internal calibration matrix of the camera is:

K = [[ 1000,    0, 500 ],
     [    0, 1000, 500 ],
     [    0,    0,   1 ]]
         

See Task 0-2 notes for used convention of direction of a 3D rotation.

1. Construct following camera matrices (keep the image u-axis parallel to the scene x-axis):
   1. P1: camera in the origin looking in the direction of z-axis.
   2. P2: camera located at [0,-1,0] looking in the direction of z-axis.
   3. P3: camera located at [0,0.5,0] looking in the direction of z-axis.
   4. P4: camera located at [0,-3,0.5], with optical axis rotated by 0.5 rad around x-axis towards y-axis.
   5. P5: camera located at [0,-5,4.2] looking in the direction of y-axis.
   6. P6: camera located at [-1.5,-3,1.5], with optical axis rotated by 0.5 rad around y-axis towards x-axis (i.e., -0.5 rad) followed by a rotation by 0.8 rad around x-axis towards y-axis. See figure 4.
2. Use the cameras P1 to P6 for projection of given wire-frame model into an image. The edges inside X1 should be drawn red, the edges inside X2 should be drawn blue and the rest should be drawn in black.

The example projection by the camera P1 is shown in figure 3.

Fig. 3: Projection of the wire-frame by the camera P1

Fig. 4: Overview of the P6 situation

Let u1, v1 be the image coordinates of projected vertices X1 and u2, v2 be the coordinates of projected vertices X2. The desired picture can be drawn, e.g., in python like this:

plt.plot( u1, v1, 'r-', linewidth=2 )
plt.plot( u2, v2, 'b-', linewidth=2 )
plt.plot( [u1, u2], [v1, v2 ], 'k-', linewidth=2 )
plt.gca().invert_yaxis()
plt.axis( 'equal' ) # this kind of plots should be isotropic

or in Matlab like this:

plot( u1, v1, 'r-', 'linewidth', 2 )
hold on
plot( u2, v2, 'b-', 'linewidth', 2 )
plot( [u1; u2], [v1; v2], 'k-', 'linewidth', 2 );
set( gca, 'ydir', 'reverse' )
axis equal  % this kind of plots should be isotropic

See the probabilistic model of line and model fitting.

A 2D line [-10, 3, 1200] generates set of 100 points (inliers), corrupted by a gaussian noise. Additionally, there is a set of 200 uniformly distributed random points not belonging to the line (outliers). There are three sets of points linefit_1.txt, linefit_2.txt, linefit_3.txt generated with the gaussian noise $\sigma=1$, $\sigma=2$, and $\sigma=3$, respectively. One set of points is shown in figure 5.

For such kind of data, non-robust estimation method, e.g. regression by least squares, cannot be used. A golden standard method for robust (i.e. in the presence of outliers) estimation in such a case is RANSAC. If more acurate result is needed, additional optimisation is applied to the result of RANSAC, i.e. least squares regression using the inliers only. One of the common modifications of RANSAC method employs support function derived as a maximum likelihood estimate (MLE), instead of a standard zero-one box function used in traditional RANSAC. This modification (MLESAC) has the same complexity and convergence, but tends to produce more accurate estimates directly. Comparison of a single run of these methods is in figure 6.

To show difference between results of the above methods, we run RANSAC and MLESAC on a single data set 100 times. Every run is then followed by least squares line regression using inliers. For visualisation purposes, every line is characterised by two parameters - its angle $\alpha$ and its orthogonal distance $d$ to origin, thus showing as a single point in $\alpha-d$ graph. The results are shown in figure 7 and figure 8. It is clearly visible, that MLESAC tends to produce more accurate estimates compared to RANSAC.

See Task 0-3 notes.

Fig. 5: Generated points of a line with outliers

Fig. 6: Line estimated line by different methods

Fig. 7: Comparison of different estimation methods; every method is run 100 times, every resulting line is represented as a point

Fig. 8

1. Choose at least one set of points from linefit_1.txt, linefit_2.txt, linefit_3.txt.
2. Use these points for (non-robust) least squares estimation (regression) of the line. This is expected to fail.
3. Use these points for robust estimation of the line. Use RANSAC to find initial estimate and to separate inliers and outliers, followed by least squares regression using the inliers.
4. Repeat the previous step with MLESAC.
5. For the estimation, do not use the parameters of the original generator (numbers of inliers, outliers, $\sigma$). Set a RANSAC threshold by hand.
6. Draw the whole situation:
   • Original line.
   • Points.
   • Line found by non-robust regression.
   • Line found by RANSAC
   • Line found by RANSAC followed by least squares regression
   • Line found by MLESAC followed by least squares regression

Reading a point coordinates from a text file can be achieved as x = load( 'linefit_1.txt' )'; (matlab) or x=numpy.loadtxt( 'linefit_1.txt' ).T (python); note the transpose to obtain column vectors. Random sample of 2 from n points can be generated as i = randperm( n, 2 ); or rng = numpy.random.default_rng() called once followed by i = rng.choice( n, 2, replace=False ).

Consider a pair of images of a scene with two dominant planes, e.g. a pair of images from a triple below. Each plane generate one homography between the image pair. i.e. there are two homographies Ha and Hb.

1	2	3

When a set of tentative correspondences between the images is known these homographies can be estimated. Additionally, since these two homographies are generated by two scene planes, there is a line in both images, that is a projection of the intersecting line of the planes. The image points u1, u2 laying on that line in both images are related by both homographies, i.e., u2 ∼ Ha u1 ∼ Hb u1, which can be written as inv(Hb) Ha u1 = λ u1. Thus these two homographies must be estimated such that these constraint is enforced (two arbitrary regular 3×3 matrices generally do not ensure the existence of such a common line. Note that this constraint means that there exist a common line that is transformed same way by the two complementary line homographies inv(Ha') and inv(Hb') (this line always exists for any two regular 3×3 matrices) but additionally that this line is transformed by both homographies from the first image to the same line in the second one point-wise. Note that this H maps points from the first image to the same image.

The special transformation composed from the such two homographies (given by two planes observed by a pair of cameras ) H = inv(Ha) Hb is called planar homology, and has only 5 degrees of freedom (3 correspondences needed), compared to 8 DoF of a general homography.

There are many methods how to estimate multiple geometric models (homographies in this case) from given data. Two simplest possibilities are:

• Sequential RANSAC
  1. Estimate the first homography using standard RANSAC scheme for a single homography. Typically the most dominant one is found.
  2. Remove inliers of the first found homography from the data.
  3. Estimate the second homography using the remaining data, such that the common homology constraint is enforced (3 correspondences needed)

• Multi RANSAC with conditional sampling
  1. Estimate both homographies simultaneously in RANSAC scheme by sampling 7-tuple of correspondences.
  2. In every sample:
     1. Draw 4 random correspondences and estimate Ha
     2. Remove inliers of Ha from the data set
     3. Draw 3 random correspondences and estimate Hb with homology constraint
     4. Verify support of both homographies, accept the best one

Common homology estimation from three: when Ha is estimated, the sampled three points u_2 (corresponding to three points u_1) are mapped to the first image by inv(Ha) as u_21. Then these correspondences u_1 and u_21 are used for estimating homology H from the three correspondences. Finally, the second homography is computed as Hb = Ha H.

Note that having two homographies an inlier must be decided to which it belongs to. This can be done based on minimal error or according to on which side of common line the point is laying.

See Task 0-4 notes.

1. Select at least one pair of images from the set above. Note that the pair 1-2 is the easiest one and the pair 1-3 is the hardest one considering the stability of solution.
2. Use interest points detected in the images: books_u1.txt, books_u2.txt, books_u3.txt for the image 1, 2, 3, respectively.
3. Use set of tentative correspondences between a selected pair of images: books_m12.txt, books_m13.txt, books_m23.txt
4. Estimate the two dominant homographies by a method of your choice, with homology constraint.
5. Compute the common line.
6. Show the results - show in both images outliers and inliers of either homography (in different colours) and the common line. Show the correspondences as needle map. See example in figure 9.

Fig. 9: An example of estimated homographies. Red and green =inliers, black = outliers, magenta = common line.