====== Basic Geometry ======

===== Task 0-1: Points and Lines in a Plane =====

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


=== Steps ===

   - 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**.
   - In your solution, allow entering two pairs of points within this area and display them.
   - 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.
   - Calculate the intersection of both lines and draw it, **if it is inside the image area**. 
   - 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 <imgref fig_points_lines>.


|  <imgcaption fig_points_lines|Example intersection>{{:courses:tdv:labs:points_lines.png|}}</imgcaption>  |  <imgcaption fig_points_lines_h|Example intersection under the homography>{{:courses:tdv:labs:points_lines_h.png|}}</imgcaption>  |


=== Hints ===

For entering the points, the Matlab function ''<fc #0000ff>ginput</fc>'', or the python function ''matplotlib.pyplot.ginput'', is suitable. Cross product of two vectors can be computed using the function ''<fc #0000ff>cross</fc>'' or ''numpy.cross''.

===== Task 0-2: Perspective camera =====

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 {{:courses:tdv:labs:tdv-task-0-2-notes.pdf|Task 0-2 notes}} for used convention of direction of a 3D rotation.

=== Steps ===

  - Construct following camera matrices (keep the image //u//-axis parallel to the scene //x//-axis):
    - ''P1'': camera in the origin looking in the direction of //z//-axis.
    - ''P2'': camera located at ''[0,-1,0]'' looking in the direction of //z//-axis.
    - ''P3'': camera located at ''[0,0.5,0]'' looking in the direction of //z//-axis.
    - ''P4'': camera located at ''[0,-3,0.5]'', with optical axis rotated by 0.5 rad around //x//-axis towards //y//-axis.
    - ''P5'': camera located at ''[0,-5,4.2]'' looking in the direction of //y//-axis.
    - ''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 <imgref fig_proj>.
  - 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  <imgref fig_house>.

|<imgcaption fig_house|Projection of the wire-frame by the camera P1>{{:courses:tdv:cviceni:projection_toy_house.png|}}</imgcaption>|<imgcaption fig_proj|Overview of the P6 situation>{{:courses:tdv:labs:projection_toy_house_3d.gif|}}</imgcaption>|

=== Hints ===

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


===== Task 0-3: Robust Maximum Likelihood Estimation of a Line(s) From Points =====

See the {{http://cmp.felk.cvut.cz/cmp/courses/TDV/labs/line_fitting.pdf|probabilistic model of line}} and 
{{http://cmp.felk.cvut.cz/cmp/courses/TDV/labs/model_fitting.pdf|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 {{:courses:tdv:labs:linefit_1.txt |}}, {{:courses:tdv:labs:linefit_2.txt |}}, {{:courses:tdv:labs:linefit_3.txt |}} generated with the gaussian noise $\sigma=1$, $\sigma=2$, and $\sigma=3$, respectively. One set of points is shown in <imgref fig_linefit_points>.

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 <imgref fig_linefit>.

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 <imgref fig_linefit_compare> and <imgref fig_linefit_compare_zoom>. It is clearly visible, that MLESAC tends to produce more accurate estimates compared to RANSAC.

See {{:courses:tdv:labs:tdv-task-0-3-notes.pdf|Task 0-3 notes}}.


|  <imgcaption fig_linefit_points|Generated points of a line with outliers>{{:courses:tdv:labs:linefit_points.png|}}</imgcaption>  |  <imgcaption fig_linefit|Line estimated line by different methods>{{:courses:tdv:labs:linefit.png|}}</imgcaption>  |

|  <imgcaption fig_linefit_compare|Comparison of different estimation methods; every method is run 100 times, every resulting line is represented as a point>{{:courses:tdv:labs:linefit_compare.png|}}</imgcaption>  |  <imgcaption fig_linefit_compare_zoom|>{{:courses:tdv:labs:linefit_compare_zoom.png|Comparison of different estimation methods, zoom-in}}</imgcaption>  |


=== Steps ===

  - Choose at least one set of points from {{:courses:tdv:labs:linefit_1.txt |}}, {{:courses:tdv:labs:linefit_2.txt |}}, {{:courses:tdv:labs:linefit_3.txt |}}.
  - Use these points for (non-robust) least squares estimation (regression) of the line. This is expected to fail.
  - 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.
  - Repeat the previous step with MLESAC.
  - For the estimation, do not use the parameters of the original generator (numbers of inliers, outliers, $\sigma$). Set a RANSAC threshold by hand.
  - 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


=== Hints ===

Reading a point coordinates from a text file can be achieved as ''<fc #0000ff>x = load( 'linefit_1.txt' )';</fc>'' (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 ''<fc #0000ff>i = randperm( n, 2 );</fc>'' or ''rng = numpy.random.default_rng()'' called once followed by ''i = rng.choice( n, 2, replace=False )''.

===== Two Homographies =====

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  |
| {{:courses:tdv:labs:book1.png?200|}} | {{:courses:tdv:labs:book2.png?200|}} | {{:courses:tdv:labs:book3.png?200|}} |

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 
    - Estimate the first homography using standard RANSAC scheme for a single homography. Typically the most dominant one is found.
    - Remove inliers of the first found homography from the data.
    - Estimate the second homography using the remaining data, such that the common homology constraint is enforced (3 correspondences needed)

  * Multi RANSAC with conditional sampling
    - Estimate both homographies simultaneously in RANSAC scheme by sampling 7-tuple of correspondences.
    - In every sample:
      - Draw 4 random correspondences and estimate **Ha**
      - Remove inliers of **Ha** from the data set
      - Draw 3 random correspondences and estimate **Hb** with homology constraint
      - 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 {{:courses:tdv:labs:tdv-task-0-4-notes.pdf|Task 0-4 notes}}.

=== Task 0-4 ===

  - 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.
  - Use interest points detected in the images: {{:courses:tdv:labs:books_u1.txt|}}, {{:courses:tdv:labs:books_u2.txt|}}, {{:courses:tdv:labs:books_u3.txt|}} for the image 1, 2, 3, respectively.
  - Use set of tentative correspondences (zero-based indexing) between a selected pair of images: {{:courses:tdv:labs:books_m12.txt|}}, {{:courses:tdv:labs:books_m13.txt|}}, {{:courses:tdv:labs:books_m23.txt|}}
  - Estimate the two dominant homographies by a method of your choice, with homology constraint.
  - Compute the common line.
  - 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 <imgref fig_two_homo>.

<imgcaption fig_two_homo|An example of estimated homographies. Red and green =inliers, black = outliers, magenta = common line.>{{:courses:tdv:labs:two_planes.png?500|}}</imgcaption>