Solved-Problem Set 3- Solution

PROBLEM 1 (Total: 15 points)

1. Out of a set of N correspondences, assume there are J outliers. If you choose K samples at random, what is the probability that all of them are inliers (i.e., none of them is an outlier) ? (5 points)

2. We are going to do this multiple times, in the hope that at least once we have a set of K samples that is completely outlier free. If we want this to guarantee this with probability P , what is the minimum number of times we should sample ? Express your answer in terms of J, K, N, and P . (5 points)

3. Let’s say we’re dealing with a pair of images that depict the same scene where there are two planes. Given a set of N

correspondences, assume that I₁ of these pairs lie on one of the planes and are consistent with the same homography, I₂ lie on the other plane and are consistent with a different homography, and the remaining J = N I₁ I₂ correspondences are random outliers.

If I draw K samples, what is the probability that all K samples are inliers and come from the same plane ? In other words, what is the probability that this using these K samples will give me a correct estimate of the homography for either of the two planes ? Note that if my set of K samples contains outliers, or mixes samples from two different planes, my results will be erroneous. (5 points)

PROBLEM 2: ROBUST LINE FITTING (Total: 20 points)

We will use the idea of robust fitting to the simpler task of fitting lines to (x; y) co-ordinates. Consider the equation of the line in the form y = mx + b. Given a set of chosen points (x_i; y_i), we will fit m; b in the least-squares sense as:

m; b = arg m;b Xi		i		i	b)2
min	(y		mx

1. Implement the iterative fitting idea by filling out fitLine in prob2a.py. The goal here is to first find the best fit to all points and then select an inlier set based on samples for which the error is lower than a threshold (passed to the function). Then, the method iteratively refines the estimate of the line by fitting only to the inlier set, and then rebuilding the inlier set based on the current estimate.

When run, prob2a.py will call this function on different point sets with different numbers of outliers. (It will also call the function for only 1 iteration, implying doing a regular least-squares fit, no the set with a moderate number of outliers). Export the generated figure and include it in your report, and comment on the behavior of this method. (10 points)

2. Implement RANSAC by filling out ransac in prob2b.py. In this case, do N runs of choosing K samples each, fitting a line to each set of K samples, and then building an inlier set for each run. Choose the largest inlier set among all runs, and return the final estimate of the line as the estimate based on this inlier set. When run, prob2b.py will call the function with different choices of K and N on a sample set with a large fraction of outliers. Be sure to call the script multiple times, and comment on which choices return the best fit most consistently. (10 points)

PROBLEM 3 (Total: 15 points)

1. What is the relationship between the projected co-ordinates of the same point in two cameras, where the projection matrices differ only in terms of the focal length ? In other words, there is no translation or rotation, but we just move the sensor plane closer/farther from the optical center. You can assume that the intrinsic projection matrix is:

• 3

f 0 W=2

K =	6	0	f	H=2	7	;
		0	0	1
	4				5

with f = f₁ for camera 1 and f = f₂ for camera two. Derive the expression relating the projected co-ordinates (x₁; y₁) in camera 1 to (x₂; y₂) in camera 2, in terms of f₁; f₂; W; and H. (5 points)

2. Now consider two cameras that are related by both rotation and translation. We know that with translation, points in the two camera images can no longer be related by a homography in general. But now, assume that all points in the 3D world lie on a plane. Show that if you know what that plane is, then you can relate the mapping between two cameras with a homography. (Hint: begin by choosing a world co-ordinate system where the equation for the plane is given by z = 0. Both cameras will then have their own arbitrary extrinsic matrices. Then derive the expression for projected homogeneous co-ordinates in one camera in terms of those in another). (10 points)

PROBLEM 4 (Total: 30 points)

(a) Implement the function getH in prob4.py which given a number of pairs of 2D co-ordinates (you will get an N 4 array where each row are the pair of Cartesian co-ordinates [x; y; x⁰ ; y⁰ ]), computes the Homography that maps from (x; y) to (x⁰ ; y⁰ ) (i.e., the matrix H such that [x⁰ ; y⁰ ; 1]^T H [x; y; 1]^T ). Convert the pairs of points to Homogeneous co-ordinates, derive the system of equations for the elements of the Homography as discussed in class (retain all three equations per correspondence), and solve using SVD. (You may want to debug this function separately by calling it on arbitrary pairs of quadrilaterals, and looking at how well the Homography maps the provided set of points to each other). (15 points)

2. Now use this function to splice one image into another by filling out the function splice in prob4.py. This function

will be provided a source image, a destination image, and a 4 2 array corresponding of the (x; y) co-ordinates in the destination image of the, in order, top-left, top-right, bottom-left, and bottom-right points of a quadrilateral (which will correspond to the projected image of a rectangle in the scene).

First, fit a homography that goes from these co-ordinates to the corners of your source image (which will be (0; 0), (W 1; 0), (0; H 1), (W 1; H 1) for the source image). Then, use this homography to warp and place the source image into the quadrilateral in the destination image. Note that you don’t need to do anything complicated to figure out which points lie inside the quadrilateral. Simply consider the larger rectangle that includes the quadrilateral (going from min to max values of the x and y co-ordinates of the quadrilateral corners). Apply the estimated Homography to all of them, and figure out which points map to inside the boundaries of the source image (i.e., x co-ordinate is between 0 and W-1, y between 0 and H-1). Then transfer these values using bilinear interpolation.

Running prob4.py will create a spliced image in outputs/prob4.png. Include this in your report. (15 points)

PROBLEM 5 (Total: 20 points)

1. Fill out the function census in prob5.py to compute the 5 5 centered census transform of an image. The function will take a grayscale image as input and should produce a uint32 array of the same size as output. The lower 24 bits at location (x; y) should be set based on whether the intensity at (x; y) was greater than that at (x _x; y _y) (to 1 if it is, 0 otherwise), with each bit corresponding to a different value of _x; _y going from 2 to 2. Note that you don’t need to use a bit for comparing (x; y) to itself. The order of the bits isn’t important as long as you use the same convention everywhere. Near the boundaries, set a bit to 0 if the corresponding (x _x; y _y) falls outside the image boundary. (10 points)

2. Now given a pair of rectified left and right stereo images, match points based on the hamming distance of their census

codes. Given a point (x; y) in the left image, you can assume that it’ll match with one of (x d; y) in the right image where the “disparity” d is an integer with 0 d D_max. Also for now, assume that the matching point (x d; y) can not lie outside the right image, so d x.

Fill out the function smatch in prob5.py to take a pair of images and the value of D_max, and find the disparity map as the best value of d at each pixel which minimizes the Hamming distance between the census codes at (x; y) in the left image and (x y; d) in the right. Use the function you wrote in part (a), and we provide a function hamdist for computing the element-wise hamming distance between two uint32 arrays.

Running prob5.py will generate a color representation of the estimated disparity map in outputs/prob5.png. In-clude it in your report. (10 points)