Description
Instructions
Please read the late submission and collaboration policy on the course website:
http://www.cse.wustl.edu/~ayan/courses/cse559a/
All code will be tested on Anaconda for Python 3.6, available from https://www.anaconda.com/download.
This problem set is provided as a ZIP file. You are reading the main problem set PDF in the root pset3/ directory. Look in the pset3/code subdirectory for code for different problems, with data in pset3/code/inputs. You will be required to modify and fillin various functions in the .py files in the code directory. Running this code (e.g., with python ./prob2.py and so on) will create output images in the pset3/code/outputs directory.

Complete the code files in pset3/code/ by filling out the required functions.

Run each program to generated output images in pset3/code/outputs directory.

Create a PDF report file created with LAT_{E}X. Use the template provided on the course website (scroll down to the resources section at the bottom). In particular, make sure you fill out your name/wustl key (top of the .tex file) to populate the page headers. Also fill out the final information section describing how long the problem set took you, who you collaborated / discussed the problem set with, as well as any online resources you used.
The main body of the report should contain responses to the math questions, and also include results and figures for the programming questions as asked for. These figures will often correspond to images generated by your python code in the pset3/code/outputs/ directory.
Place this report file as solution.pdf in the root pset3/ directory.
Then, zip all the contents and subdirectories of pset3/ into a single ZIP file, and upload it to blackboard.

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)

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)

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_{1} of these pairs lie on one of the planes and are consistent with the same homography, I_{2} lie on the other plane and are consistent with a different homography, and the remaining J = N I_{1} I_{2} 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) coordinates. 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 leastsquares sense as:

m; b = arg _{m;b} ^{X}_{i}
i
i
b)^{2}
min
(y
mx

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 leastsquares 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)

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)

What is the relationship between the projected coordinates 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_{1} for camera 1 and f = f_{2} for camera two. Derive the expression relating the projected coordinates (x_{1}; y_{1}) in camera 1 to (x_{2}; y_{2}) in camera 2, in terms of f_{1}; f_{2}; W; and H. (5 points)

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 coordinate 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 coordinates 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 coordinates (you will get an N 4 array where each row are the pair of Cartesian coordinates [x; y; x^{0} ; y^{0} ]), computes the Homography that maps from (x; y) to (x^{0} ; y^{0} ) (i.e., the matrix H such that [x^{0} ; y^{0} ; 1]^{T} H [x; y; 1]^{T} ). Convert the pairs of points to Homogeneous coordinates, 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)

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) coordinates in the destination image of the, in order, topleft, topright, bottomleft, and bottomright 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 coordinates 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 coordinates 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 coordinate is between 0 and W1, y between 0 and H1). 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)

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)

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 elementwise hamming distance between two uint32 arrays.
Running prob5.py will generate a color representation of the estimated disparity map in outputs/prob5.png. Include it in your report. (10 points)