Project 4: [Auto]Stitching Photo Mosaics

Ryan Mathew
October 18th, 2024

Overview - Part 4A

In this project, I will compute homographies between images and warp them to create mosaics. This will require taking photographs of various subjects, computing homographies, warping images, stitching, blending, and more.

Part 1: Shoot and Digitize Pictures

Before starting to work on the project, I first needed to source pictures that I would use when creating mosaics. I decided to capture various buildings around campus for my mosaics as well as items in my apartment to test rectification. Utilizing my phone camera, I locked certain settings such as focus and exposure and took pictures from the same center of projection.

Here are the images that I will rectify to test my warp function:

Card

Car

Here are the images that I will use when creating mosaics.

Campanile Left

Campanile Middle

Library Left

Library Middle

Wheeler Hall Left

Wheeler Hall Middle

Wheeler Hall Right

Part 2: Recover Homographies

Before we can put together a mosaic, we need to compute the parameters of the transformation AKA the homography in this case. To recover the homography H, we can set up a transformation p' = H * p where H is a 3x3 matrix with 8 degrees of freedom. We will need to create correspondences between the two images using the tool at this link similar to how we did in the previous project. With more than 4 point correspondences, we can create an overdetermined system of equations that can be solved using least squares.

If we expand it out, we can add as many points as we have as correspondences, stack them in the matrix, and solve using least squares to recover the homography matrix

Part 3: Warp the Images (Rectification)

Using the homography matrix which we found in the previous part, we can use it to warp 1 image and project it onto another so it can be stitched together. If we want to warp image A onto image B, we will first take the corners of image A and apply the homography to get the corners in image B. From here, we know the "bounding box" of where points in image A fall in image B. Now, we can perform an inverse warp on the points in the bounding box to get where they come from in image A. Finally, we can interpolate these pixels from image A to the warped image.

Here are some images that I rectified to be frontal parallel. For each one, since I don't have another image to select correspondences for, I manually created correspondences in the form of something about the subject (ex. rectangular for my objects):

Playing Card

Playing Card (Rectified)

Playing Card (Rectified Zoomed)

Car

Car (Rectified)

Car (Rectified Zoomed)

We can see that the warp works and the images are in fact rectified to be frontal parallel. This tool will be crucial in warping one image onto another as we'll see in the next section.

Part 4: Create Mosaics

Now that we are able to compute homographies from correspondences between images and rectify them, we can create mosaics. First, we will use the homography between image A and B to warp A onto B. We can now compute the final mosaic size by taking the difference between the max and min location for x and y between the warped image A and image B. From here, we can simply position each image so that they are 'stitched' together. However, this results in subpar mosaics as a seam can be seen running through the image. To fix this, we will simply perform feathering (weighted averaging) to 'blend' the images.

Once we have the second image and the warped image, we can 'feather' each of them in which we add an alpha channel (mask) that makes the edges smoother. The edges will be more transparent while the parts closer to the center will remain opaque. Because this is applied where the images overlap, it will blend nicely. Now, just add the warped image A in the correct location of the mosaic and blend when adding image B.

For 3 image mosaics such as the last example below, the process is very similar. If image B is the 'middle' image, we will need to warp image A and image C onto image B. From here, do the same feathering and adding/blending to the output mosaic for all 3 images.

2 Image Mosaics

Campanile Left

Campanile Middle

Campanile Mosaic (Unblended)

Campanile Mosaic (Blended)

Library Left

Library Middle

Library Mosaic (Unblended)

Library Mosaic (Blended)

3 Image Mosaic

Wheeler Hall Left

Wheeler Hall Middle

Wheeler Hall Right

Wheeler Hall Mosaic (Unblended)

Wheeler Hall Mosaic (Blended)

As you can see, most of the unblended mosaics have a visible seam (Hover over picture to expand). The blended mosaics do a great job of mixing the surrounding pixels so the seams are no longer clearly apparent. I also found that point correspondence selection is key as your warps might not be properly aligned until you select enough essential points and achieve a good homography.

Project 4A: Takeaways

I enjoyed working on this project and learning how to compute homographies as well as warp images to create interesting mosaics of multiple images. I realized that it is important to pick many good correspondences to achieve good results. This will help me to appreciate project 4b much more!

Overview - Part 4B

In this project, I will stitch images together without manually defining their correspondence points. We will utilize Harris corner detection and more to automatically find optimal corners and use them to stitch and blend images as we did in the previous part. I referenced the paper "Multi-Image Matching using Multi-Scale Oriented Patches" at this link.

Part 1: Detecting Corner Features in an Image

We first need to obtain potential keypoints on our images. When manually tagging points on our images, the ideal locations would be corners. Therefore, we can use the Harris Corner Detector to generate corners that may or may not be used for alignment. Using the code in harris.py, I passed in my black and white image and received coordinates of corner points as well as a matrix 'h' with the corner strength of each pixel. Here are the results of overlaying the potential corners on my images:

Harris Corners on Campanile Left

Harris Corners on Campanile Middle

Harris Corners on Library Left

Harris Corners on Library Middle

Harris Corners on Wheeler Left

Harris Corners on Wheeler Middle

Harris Corners on Wheeler Right

There are clearly too many points to be useful and efficient so we will work on narrowing down the options.

Part 2: Adaptive Non-Maximal Suppression (ANMS)

As we saw from the previous part, there are too many corner points so we need to filter some out to be more efficient. We can do so using the technique of Adaptive Non-Maximal Suppression (ANMS). ANMS first gets all the pairwise distances between all corners. Then for every corner, it will rank that corner i with the minimum distance r[i] to a stronger corner. Finally, the rankings will be sorted so we get the corners with largest r[i] or those that are farthest from stronger corners. Formally, we satisfy this:

We can choose the top n corners. Here, I apply ANMS with n=500 and c_robust=0.9 on the corners I got from the Harris Corner Detector:

ANMS Corners on Campanile Left

ANMS Corners on Campanile Middle

ANMS Corners on Library Left

ANMS Corners on Library Middle

ANMS Corners on Wheeler Left

ANMS Corners on Wheeler Middle

ANMS Corners on Wheeler Right

With this, we're able to narrow down the points to the 'best' n points and make future computation easier.

Part 3: Extracting Feature Descriptors + Feature Matching

Now that we have a decent amount of keypoints for each image, we need to figure out how to match them between images. We can extract feature descriptors for each keypoint that captures essential information around the point which can be compared and matched to descriptors of points in other images. Specifically, for each point in the image, we'll take a M by M window of pixels around it and resize it to an N by N patch which blurs it and allows us to suppress any noise. The descriptor is then normalized to filter any other noise. I used a window size of M=40 and patch size of N=8.

Now that we have these descriptors for each point in image, we can move on to using them to match points between different images. For every point X's descriptor in one image, we will calculate the pairwise distance from it to all descriptors of another image. We sort by the smallest distance and take the ratio of the nearest neighbor to the second nearest neighbor. If the ratio is smaller than some threshold t, we will map that point X to the point of the nearest neighbor descriptor. This will give us point correspondences between 2 images without having to manually select them like we did in earlier parts. Here are the feature matched corners between images and their correspondences:

Feature Matched Corners on Campanile Left

Feature Matched Corners on Campanile Middle

Feature Matched Corners on Library Left

Feature Matched Corners on Library Middle

Feature Matched Corners on Wheeler Left

Feature Matched Corners on Wheeler Middle

Feature Matched Corners on Wheeler Right

We can see that many points that didn't have a 'good' correspondence with another point were filtered out. However, some points were incorrectly matched with others. That is fine for now as we will handle this in the next step. The processing we just did will make it easier to find a good homography.

Part 4: Random Sample Consensus (RANSAC)

Now that we have correspondences, we want to be able to compute a homography between two images. However, we may have outliers that can affect our homography computation. We can use Random Sample Consenses (RANSAC) to do a final filtering step and achieve a good homography.

Here are the 5 steps for RANSAC:
1. Select four feature pairs (at random)
2. Compute homography H (exact)
3. Compute inliers where dist(point_i, Homography of point_i) < ε
4. Keep largest set of inliers
5. Re-compute least-squares H estimate on all of the inliers

We repeat the first 4 steps for number of iterations N. From this, we can obtain the final point correspondences between the two images and the homography H. Here are the overlayed points from running RANSAC between images. I used N=10000 and ε=5:

RANSAC Corners on Campanile Left

RANSAC Corners on Campanile Middle

RANSAC Corners on Library Left

RANSAC Corners on Library Middle

RANSAC Corners on Wheeler Left

RANSAC Corners on Wheeler Middle

RANSAC Corners on Wheeler Right

The points that we had prior to running RANSAC might have already been pretty good. However, we can notice that RANSAC is able to get rid of some extra and maybe erroneous points and only keep the ones that result in the best homography.

Part 5: Autostitching and Blending Mosaics

Now that we have the point correspondences and homographies, we are able to repeat our steps from Project 4a and automatically stitch and blend our images to create mosaics! Here are the results of doing it automatically vs manually defining correspondences:

Automatic Unblended Campanile

Manual Unblended Campanile

Automatic Blended Campanile

Manual Blended Campanile

Automatic Unblended Library

Manual Unblended Library

Automatic Blended Library

Manual Blended Library

Automatic Unblended Wheeler

Manual Unblended Wheeler

Automatic Blended Wheeler

Manual Blended Wheeler

HOVER OVER ANY IMAGE TO SEE LARGER VIEW
The mosaics created from manually defined correspondences are better aligned than the automatic ones in my opinion but the error is very small and I am overall pleased with the results. While maybe not as perfectly aligned as I hoped, it is definitely more convenient than having to manually select correspondences. If I had more time, I would try to play around with the parameters like thresholds, epsilons, etc to see if I can get more/better points to improve the alignment.

Project 4B - Takeaways

I enjoyed working on both parts of this project and was very pleased with how it turned out. The coolest thing I learned from the project was how to automatically find correspondences using corner detection and other tricks as manually selecting them like in part 4A can take a while.