Image Warping and Mosaicing

1. Shoot the Pictures

Here are the pictures I used to create the mosaic. To get the photos to blend well, I took them in a way such that there was a homography between each pair of pictures, with significant overlap. Easiest way to do this was to keep the center of projection.

2. Recovering Homographies

A homography is a transformation that maps a point in one image to a point in another image. We can use this to map points in one image to points in another image. We can represent the homography as a 3x3 matrix.

We can solve for the homography by using the corresponding points in the two images. Notably, we need at least 4 pairs of points to solve for the homography, since there are 8 degrees of freedom. We can get these correspondences manually by hand.

It’s more robust to solve an overdetermined system of equations, which we can do by least squares.

Here are the correspondences visualized for both images:

Given a corresponding point, we solve the following system of equations (can do with Least Square):

Here are the recovered homography matrices for both set of images:

[[ 1.27419305e+00 -3.61072355e-02 -9.76763745e+01]
 [ 1.50414385e-01  1.12467723e+00 -2.92171093e+01]
 [ 6.68292402e-04 -1.56554196e-04  1.00000000e+00]]

[[ 1.49943488e+00  6.85326131e-03 -1.53320223e+02]
 [ 1.37961079e-01  1.27584021e+00 -3.09431330e+01]
 [ 1.14201538e-03 -9.65697304e-05  1.00000000e+00]]

3. Warp the Images

Now that we have the homography between the two images, we can implement the warping to get the transformed image.

Using the forward warp H is a bad idea, because it can lead to holes in the image. Instead, we can use the inverse warp H^-1 to get the transformed image. This way, we get all the pixels in the output image.

Now we deal with another problem. After applying the inverse warp, we find that a lot of pixels in the output come from subpixels in the input image. To solve this, we need to interpolate the values of the input image at the subpixel locations. We can use a simple nearest neighbor interpolation or bilinear interpolation to do this.

Now we can use this technique to rectify images. Here are the images we will rectify:

Here are the rectified images using Nearest Neighbors:

Here are the rectified images using Bilinear Interpolation:

As we can see, bilinear interpolation produces a smoother image than nearest neighbor interpolation.

4. Blend the Images into a mosaic

First, I warp image 1 to the perspective of image 2 using a homography. Then, I warp image 1 using the homography in order to align it with image 2. I calculate the bounds of the mosaic image by finding the min and max x and y coordinates of the corners of both images after warping.

I implemented the Laplacian blending technique to blend the images into a mosaic. But I wasn’t able to get good results in time. I applied mostly the same techniques as I did from project 2. I used weighted average for the low-frequencies and distances transforms for the high frequencies.

Here are three different mosaics along with the source images:

1. Harris Corner Detection

Harris Corners are points in an image where the intensity changes significantly in all directions. They are useful for feature detection and matching.

To achieve a more even spread of corners across the image, I implemented ANMS. Essentially, ANMS works by suppressing corners that are too close to each other. This is done by calculating the minimum distance to a corner with a significantly higher corner response. Then, we select the top N corners with the largest minimum distances.

Here are the detected corners before and after applying ANMS:

2. Feature Descriptor Extraction

Then, for each point, we want to create a feature descriptor, which is a 40x40 patch of pixels around the corner point. To make the descriptor more robust to changes in illumination and contrast, we downscale the image to 8x8 and normalize by subtracting the mean and dividing by the standard deviation.

Here are normalized 8x8 feature descriptors:

3. Feature Matching

Now we want to match the feature descriptors between two images. We can do this by calculating the sum of squared differences (SSD) between each pair of descriptors.

We wish to avoid outliers as much as we can. I implemented Lowe’s trick, which quantifies how confident the match is by comparing the ratio of the most similar neighbor with the second most similar neighbor. Then, we can set a threshold on this ratio to filter out weak matches.

Here are the matched features between the two images:

In general, we can see that most of the matches are correct, but there are still some outliers.

4. RANSAC for Robust Homography

Now that we have the matched features, we can use RANSAC to robustly estimate the homography between the two images. RANSAC works by randomly sampling a subset of matches, estimating the homography, and then counting the number of inliers that agree with this homography. We repeat this process for a fixed number of iterations and keep the homography with the most inliers.

We sample 4 random matches to estimate the homography (because a homography needs 8 degrees of freedom). Then, we calculate the number of inliers by checking how many matches have a reprojection error below a certain threshold.

Altogether, we created an automatic pipeline that aligns two images using feature detection, matching, and RANSAC. Here is a comparison of manual stitching from earlier and automatic stitching using this pipeline: