Description
Machine perception
2021/2022
Create folder assignment5 that you will use during this assignment. Unpack the content of the assignment5.zip that you download from the course webpage the folder. Save the solutions for the assignments as Python scripts assignment5 folder. In order complete the assignment you have present these files the teaching assistant. Some assignments contain questions that require sketching, writing manual calculation. Write these answers down and bring them the presentation as well. The tasks that marked with (cid:70) optional. Without completing them you get at points for the assignment. The maximum total amount of points for each assignment is 100. Each optional task has the amount of additional points written next it.
At the defense, the obligatory tasks must implemented correctly and completely.
If your implementation is incomplete, you will not able defend the assignment.
Introduction
In this assignment we will review several parts of the epipolar geometry (chapter and robust estimation (page 346).
Exercise Disparity
In this assignment we will focus calculating disparity from two-camera system. Our analysis will based simplified stereo system, where identical cameras aligned with parallel optical axes and their image planes (CCD sensors) lie the same plane (Image
In Image we observe that we write the following relations using similar
triangles:
f
=
px pz
,
f
=
T − px pz
.
Using the equations derive the expression for disparity which is defined as d = − What is the relation between the distance of the object (point in Image camera and the disparity d? What happens disparity when the object is close the cameras and what when it is far away?
Write script that computes the disparity for range of values of pz. Plot the values figure and the appropriate units axes. Use the following parameters of the system: focal length is f = 2.5mm and stereo system baseline is T = 12cm.
Figure Left image shows the simplest stereo setup with parallel cameras. Right image shows geometric relations when mapping of point in space axis in image planes of the cameras.
In order get better grasp the idea of distance and disparity, you will calculate the numbers for specific case. We will take the parameters from specification of commercial stereo camera Bumblebee2 manufactured by the company PointGray: f = 2.5mm, T = 12cm, whose image sensor has resolution of 648 × 488 pixels that square and the width of pixel is 7.4µm. We assume that there is empty space between pixels and that both cameras completely parallel and equal. Lets that we use this system observe (point) object that is detected at pixel 550 in axis in the left camera and at the pixel 300 in the right camera. How far is the object (in meters) in this case? How far is the object if the object is detected at pixel 540 in the right camera? Solve this task analytically and bring your solution the presentation of the exercise.
(d) (cid:70) points) Write script that calculates the disparity for image pair. Use the images in the directory disparity. Since the images were pre-processed we limit the search for the similar pixel the same row in the other image. Since just the image intensity carries little information, we will instead compare small image patches. simple way of finding matching patch is use normalized cross correlation. NCC for matrices and of equal size is defined as
CC(X, =
(cid:113) (
(cid:80)(xi − ¯x)(yi −
(cid:80)(xi −
(cid:80)(yi −
(cid:113)
.
where denotes specific cell in matrix and yi specific cell in matrix patch from the second image is considered match if it has the highest NCC value. The difference in axis between the point from the first image and the matching point from the second image is the disparity estimate in terms of pixels1. The disparity search is performed in single direction and is usually limited with maximum value.
1Converting this estimate distance requires information about the camera, which we not have
for the given image pairs.
Perform the search for the similar patch in both images, you obtain disparity matrices. You then merge them in some way you choose. Smooth the results using median filter and choose appropriate search window obtain good results.
Note: You cannot merge the results element-wise. The images were taken from different viewpoints and the results would incorrect.
Question: characteristics of pixels with consistent disparity estimation?
Is the disparity estimated well for all pixels? If not, what the
(cid:70) points) Improve the noisy disparity estimation. You implement sym- metric matching technique where the left image is compared the right image and vice versa. The result then merged in some way that you choose. Smooth the results using median filter and choose appropriate search window obtain good results. Very noisy results will not graded.
Exercise Fundamental matrix, epipoles, epipolar lines
In the previous exercise we were dealing with special stereo setup where the image planes of cameras were aligned. In that case the projection of point has the same co- ordinate in both cameras and the difference in coordinate tell us the distance of the point the camera system. Such setup ensures that the epipolar lines in the cameras parallel the lines in the sensor. This simplifies the search for correspondences (i.e. the projection of the same point both cameras). Generally the epipolar lines not aligned with rows and in order establish the relation between image planes, the fundamental matrix needs computed.
In this exercise you will implement simple version of eight-point algorithm that used estimate fundamental matrix between cameras. We will first revisit the theory that will used for the task. If we assume list of perfect correspondence pairs of points in left = and right x(cid:48) = [u(cid:48), v(cid:48), image in homogeneous coordinates. The fundamental matrix rule states that each correspondence valid solution for the following equation:
x(cid:48)T Fx = 0
; F =
F11 F12 F13 F21 F22 F23 F31 F32 F33
,
where F denotes fundamental matrix. Similarly that we have done for the estimation of homography in the previous exercise, we write relation between single pair of
correspondence points as
(cid:2) uu(cid:48) uv(cid:48) vu(cid:48) vv(cid:48) u(cid:48) v(cid:48) (cid:3)
F11 F12 F13 F21 F22 F23 F31 F32 F33
= 0.
If we combine ≥ of these equations in matrix we get system of linear equations:
u1u(cid:48) u2u(cid:48) … u(cid:48)
u1v(cid:48) u2v(cid:48) … v(cid:48)
v1u(cid:48) v2u(cid:48) … … vN u(cid:48)
v1v(cid:48) v2v(cid:48) … vN v(cid:48)
v(cid:48) u(cid:48) v(cid:48) u(cid:48) … … … … v(cid:48) vN u(cid:48)
F11 F12 … F33
Af = 0
=
.
0 0 … 0
We solve the linear system above in least-squares way by using the singular value decomposition method (SVD). Matrix is decomposed = UDVT . The solution according least squares corresponds the eigenvector vn with the lowers eigenvalue, the last column of the matrix2
Recall that the epipole of camera is point where all the epipolar lines (for that camera) intersect. This requires the rank of the matrix F however, this is usually not true when dealing with noisy data – the fundamental matrix estimated using the approach above will not have rank In practice this means that the epipolar lines will not intersect in single point but rather in small neighborhood of such point. stabilize the system we have subsequently limit the rank of the fundamental matrix. This done by performing SVD decomposition F = UDVT , the lowest eigenvalue (D33 in matrix D) 0, and then reconstruct back the corrected matrix F by multiplying UDVT . newly created fundamental matrix will satisfy the rank condition rank = and used compute epipoles for each camera)
= 0
in FT = 0,
by decomposing the matrix F again and computing the left and right eigenvector of the matrix F,
= (cid:2)
(cid:3) , = (cid:2)
(cid:3)
which then used obtain both epipoles in homogeneous coordinates.
simple eight-point algorithm for estimation of fundamental matrix and the epipoles
summarized as:
• Construct the matrix as in equation
2This is solution in column form as seen in equation that has reshaped the form in
equation
3Attention: the terms left and right eigenvector mathematical terms and not hold relation
the left and right camera in our system.
• Decompose the matrix using SVD = UDVT , and transform the last eigenvector
= in × fundamental matrix Ft
• Decompose Ft = UDVT and the lowest eigenvalue 0, reconstruct F = UDVT .
• Decompose Ft = UDVT again, compute both epipoles as = /
and =
Once we have the fundamental matrix, we take point in the first image plane and determine epipolar line for that point in the second image plane = Fx1. Likewise, we take point in the second image plane and find epipolar line in the first image plane = FT Recall that line in projective geometry is defined as single vector = line written using classical Euclidean formula as
and used insert the coordinates = W ]. This gives us
ax + by + = 0,
aX + bY + cW = 0 = xT lT = 0.
The interpretation of the parameters is as follows: −a/b is the angle of the line, −c/a and −c/b the intersections with axes and
Solve the following task analytically. We given system of cameras and
fundamental matrix that connects the left camera the right
F =
0 0
0.002 0 −0.012 0 −0.001 0.011 −0.085
.
Question: Compute the Euclidean equation of the epipolar line in the right camera that corresponds the point at row = 120 and column = 300 in the left camera. Take into account that the point has first written in homogeneous coordinates, i.e. = [column, row, . Also compute the epipolar line for another point at row = 170 and = 300 in the left camera. Question: Compute the intersection of these lines. What is the name of the point of intersection?
Estimating fundamental matrix
Implement function fundamental_matrix that is given of (at least) pairs of points from images and computes the fundamental matrix using the eight-point algorithm.
As the eight-point algorithm numerically unstable, it is usually not executed directly given pairs of points. Instead, the input is first normalized by center- ing them their centroid and scaling their positions that the average distance For of points we achieve this by multiplying them the centroid is with transformation matrix achieve this, you use the function nor- malize_points from the supplementary material.
√
Extend the function fundamental_matrix that it first normalizes the input point- of the left camera (we get transformed points and the transformation matrix and then transform the input point of the right camera (we get the transformed points and the transformation matrix Using the transformed points the algo- rithm computes fundamental matrix ˆF, then transforms it into the original space using both transformation matrices F = TT
ˆFT1.
Test your function for fundamental matrix estimation using the correspondence pairs that you load from the file house_points.txt. Compute the fundamental matrix F and for each point in each image calculate the corresponding epipolar line in the other image. You draw the epipolar lines using draw_epiline from the supplementary material. According epipolar geometry the corresponding epipolar line should pass through the point. As testing reference the correct fundamental matrix is included in the supplementary material in file house_fundamental.txt.
We use the reprojection error as quantitative measure of the quality of the esti-
mated fundamental matrix. Write function reprojection_error that calculates the reprojection error of fundamental matrix F given matching points. For each point, the function should calculate the corresponding epipolar line from the point’s match in the other image, then calculate the perpendicular distance between the point and the line using the equation:
distance(ax + by + = 0, (x0, y0)) =
|ax0 + by0 + +
√
,
where and the parameters of the epipolar line. Finally, the function should return the average of the distances.
Write script that performs tests: compute the reprojection error for points = 233]T in the left image-plane and = 219]T in right image-plane using the fundamental matrix (the error should approximately pixels). Load the points from the file house_points.txt and compute the average of symmetric reprojection errors for all pairs of points. If your calculation is correct, the average error should approximately pixels.
RANSAC algorithm
In practice automatic correspondence detection algorithms very rarely find perfect matches. In cases the locations of these points contain some noise, in some cases several correspondences might also completely wrong. These correspondences called liers good meta-algorithm for such cases is RANdom SAmple Consensus (RANSAC). The algorithm applied wide variety of problems. version that used for robust estimation of fundamental matrix is structured as follows:
• Randomly select minimal of point matches (correspondences) that required
estimate model (in case of fundamental matrix this number is
• Estimate fundamental matrix using the selected
• Determine the inliers for the estimated fundamental matrix (i.e. matched pairs that
have reprojection error lower than given threshold).
• If the percentage of inliers is big enough (≥ use the entire inlier subset estimate
new fundamental matrix (using mean squares method and SVD).
• Otherwise repeat the entire procedure for iterations.
The value of parameter is defined by the properties of our data that by know- ing the estimation problem that we trying solve. E.g., suppose that we constantly encounter at least w percent of inliers (correctly matched point pairs). The number of pairs required estimate fundamental matrix F is at least = We compute the probability of successful estimation of F, i.e. the probability that all selected points will inliers as wn. The probability that this will not true is − wn. The probability that we not manage select clean of inliers in repetitions is pfail = − wn)k. In practice we therefore select high enough reduce the probability of failure pfail acceptable level.
You will implement all the required steps of the RANSAC algorithm.
(d) Implement the function get_inliers, that accepts estimation of fundamental matrix, complete of correspondences and threshold ε as input and returns of correspondences that considered inliers for the given fundamental matrix. point pair, and x(cid:48), considered inliers if the distance between and the epipolar line FT x(cid:48) (as well as the other way around) is lower than ε.
Implement the function ransac_fundamental that robustly estimates fundamen- matrix using RANSAC and normalized eight-point algorithm. Implement simple version of RANSAC algorithm that repeats iterations and then returns the solution that is supported by the largest fraction of inliers.
Apply your version of RANSAC algorithm with parameters ε = and = 100 of correspondences that you read from the file house_matches.txt. In order visually inspect the success of the estimation of F choose point in the left image-plane and display its epipolar line in the right image- plane. Make sure that the line passes the correspondence point in the right image-plane. You also
4You have probably noticed some outliers in the previous exercise when computing homography.
that for multiple points. the parameters ε and for optimal result. In single figure plot all potential correspondence pairs from house_matches.txt as well as correspondence pairs that were chosen by the RANSAC algorithm as inliers (using different color). What is the difference between the sets? Note that the examples below different your own results as the RANSAC algorithm is stochastic and therefore produces different result each
(f) Perform fully automatic fundamental matrix estimation. Detect the correspondence points using the function find_matches that you have implemented for the previ- ous assignment. Using these matches, run the RANSAC-based fundamental matrix estimation. Display both images with both the matched point as well as the points retained by the RANSAC algorithm. Also display the percentage of inliers and the mean reprojection error. the parameters correctly that randomly chosen inlier point will lie the corresponding epipolar line.
Note: The points lying their corresponding epipolar lines is necessary condition for successful completion of this task (i.e. the maximum reprojection error should less than 1px).
(cid:70) points) Implement robust homography estimation using RANSAC. The re- projection error for determining inliers calculated using Euclidean distance between the mapped points. Test your implementation images from the previ- ous assignment. Then, use the robust homography estimation reconstruct the panorama in the folder panorama. You should detect and match feature points in both images, then calculate the homography matrix and use it merge both im- ages. Repeat the procedure until you get the entire panorama image. You use the function warpTwoImages from the supplementary material merge images. Hint: You reduce the area in which you search for feature points when that makes sense.
Note: Even the robust homography estimation produce some small distortion. This error accumulate when merging multiple images sequentially. Think how you minimize the effect of the errors.
Exercise Triangulation
If we know the intrinsic parameters of the cameras as well as the fundamental trix, we calculate the position of the points observed in both cameras. You
find the calibration matrices for both cameras stored in files house1_camera.txt and house2_camera.txt. The calibration matrices have the size ×
We will use algebraic approach perform the triangulation. Assuming we have correspondence between in the first image plane and in the second image plane (in homogeneous coordinates), location of the common point in space is given by relations
λ1×1 = λ2×2 =
We know that vector product between parallel vectors is 0 we use × λ1×1 = 0 and get:
× = [x1×]P1X = 0 × = [x2×]P2X = 0,
where we have used the following form (shear-symmetric form) get rid of vector product:
× = [x1×]b =
0 −ay
ay 0 −ax ax
0
For each pair of points we get independent linear equations for unknown variables. If we combine in matrix the first lines of the product [x1×]P1 and first lines of the product [x2×]P2, we compute the mean quadratic estimate of by solving linear equation system AX = 0. As you already know by such solution obtained by computing the eigenvector of matrix that has the lowest eigenvalue. Note that the solution of the system is point in homogeneous coordinates space), therefore you have first normalize the values the last coordinate becomes
Implement the function triangulate that accepts of correspondence points and pair of calibration matrices as input and returns the triangulated points. Test the triangulation the points from the file house_points.txt. Visualize the result using plt.plot plt.scatter. Also plot the index of the point in space (use plt.text) the results will easier interpret. Note: The coordinate system used for plotting in space is usually not the same as the camera coordinate system. In order make the results easier interpret, the ordering of the axes modified by using transformation matrix. such matrix is shown in the code snippet
import numpy as np import cv2 from matplotlib import pyplot as plt from mpl_toolkits import mplot3d
fig = plt.figure() ax = fig.add_subplot(111, projection=’3d’) # define subplot
res = triangulate(…) # calculate coordinates
T = np.array([[-1,0,0],[0,0,1],[0,-1,0]]) # transformation matrix res = np.dot(res,T)
for in enumerate(res):
plt.plot([pt[0]],[pt[1]],[pt[2]],’r.’) # plot points ax.text(pt[0],pt[1],pt[2], str(i)) # plot indices
plt.show()
(cid:70) points) Perform reconstruction of object you own. For that you will need calibrate camera with which you will take images of the object. You use webcam cell phone. Print calibration pattern5 and take multiple images with the pattern visible planar surface (if you scale it correctly you also take pictures of your screen). Take care that you change the orientation and distance between the pattern and the camera. Detect the circle centers using cv2.findCirclesGrid and check the correctness with cv2.drawChessboardCorners. Finally, use cv2.calibrateCamera obtain the camera intrinsic parameters from the detected patterns (you use the function get_grid from the supplementary material get the pattern points’ coordinates).
When you have the intrinsic parameters of your camera, you will need take images of your object from different viewpoints. First, undistort your images using cv2.undistort, then detect and match feature points. Calculate the fundamental matrix and, using the calibration matrix, also calculate the essential matrix. Then, you use cv2.recoverPose obtain the rotation and translation parameters (extrinsics) for both camera viewpoints. Use the extrinsic parameters calculate the projection matrices for both cameras and triangulate the matched points. Display the final points as well as the matches in both images.
Note: cv2.recoverPose will only return rotation matrix and translation vector. This is because the first camera lies in the origin of the coordinate system and its rotation matrix equals the × identity matrix, while its translation vector only contains zeroes.
References
D. Forsyth and Ponce. Computer Vision: Modern Approach. Prentice Hall,
5You use this https://nerian.com/nerian-content/downloads/calibration-patterns/pattern-
a4.pdf
