Homework 4: Image stitching Solution

The goal of this assignment is to use feature-based homography estimation to stitch together panoramas consisting of multiple images.




Part 1: Stitching pairs of images




The first step is to write code to stitch together a single pair of images. For this part, you will be working with the following pair (found in the data folder as uttower_left.jpg and uttower_right.jpg):

















































Load both images, convert to double and to grayscale.



Detect feature points in both images. You can use the corner detector code provided (harris.m) or the blob detector you have developed as part of the last homework. Report your choice. Display both the images alongwith the featre points.



Extract local neighborhoods around every keypoint in both images, and form descriptors simply by "flattening" the pixel values in each neighborhood to one-dimensional vectors. Experiment with different neighborhood sizes to see which one works the best. If you're using your Laplacian detector, use the detected feature scales to define the neighborhood scales. Report your choices.



Compute distances between every descriptor in one image and every descriptor in the other image. You can use dist2.m for fast computation of Euclidean distance. Alternatively, experiment with computing normalized correlation, or Euclidean distance after normalizing all descriptors to have zero mean and unit standard deviation. Feel free to experiment with SIFT descriptors. We have provided basic code (find_sift.m) for computing SIFT descriptors of circular regions, such as the ones returned by your blob detector. Report your choices.



Select putative matches based on the matrix of pairwise descriptor distances obtained above. You can select all pairs whose descriptor distances are below a specified threshold, or select the top few hundred descriptor pairs with the smallest pairwise distances. Report the choices you make.



Run RANSAC to estimate a homography mapping one image onto the other. For the best fit, report the number of inliers and the average residual for the inliers (squared distance between the point coordinates in one image and the transformed coordinates of the matching point in the other image). Also, display the locations of inlier matches in both images. (i.e. for the inliers matches, show lines between matching locations in the two images)



Warp one image onto the other using the estimated transformation. To do this, you will need to learn about



maketform and imtransform functions.

Create a new image big enough to hold the panorama and composite the two images into it. You can composite by simply averaging the pixel values where the two images overlap. Your result might look something like this:





































































For estimating the transformation it is sufficient just to use grayscale images. Once you have estimated the transforamtion, you should apply the same compositing step to the color images to get a final result.




Tips and Details




Refer to the lecture slides here and here







For RANSAC, a very simple implementation is sufficient. Use four matches to initialize the homography in each iteration. You should output a single transformation that gets the most inliers in the course of all the iterations. For the various RANSAC parameters (number of iterations, inlier threshold), play around with a few "reasonable" values and pick the ones that work best. For randomly sampling matches, you can use the randperm or randsample functions.







In MATLAB, the solution to a nonhomogeneous linear least squares system AX=B is given by X = A\B;







Homography fitting calls for homogeneous least squares. The solution to the homogeneous least squares system







AX=0 is obtained from the SVD of A by the singular vector corresponding to the smallest singular value:




[U,S,V]=svd(A); X = V(:,end);




To complete this homework you have to make several choices (like the parameters for detector, descriptor). In case you are unable to get a good image stitch, go over your choices again.







Part 2: Stitching multiple images




Now that you have code for pairwise stitching working, the next step is to extend it to work on multiple images. You will be working with the provided data, consisting of three sequences of three images each. For the "pier" sequence, sample output can look as follows (although yours may be different if you choose a different order of transformations):














































Source of data and results: Arun Mallya




For this part, you should experiment with and discover your own strategy for multi-image stitching. For full credit, the order of merging the images should be determined automatically. The basic idea is to first run RANSAC between every pair of images to determine the number of inliers to each transformation, use this information to determine which pair of images should be merged first (and of these, which one should be the "source" and which the "destination"), merge this pair, and proceed recursively.




For extra credits




Experiment with registering very "difficult" image pairs or sequences -- for instance, try to find a modern and a historical view of the same location to mimic the kinds of composites found here. Or try to find two views of the same location taken at different times of day, different times of year, etc. Another idea is to try to register images with a lot of repetition, or images separated by an extreme transformation (large rotation, scaling, etc.). To make stitching work for such challenging situations, you may need to experiment with alternative feature detectors and/or descriptors, as well as feature space outlier rejection techniques such as Lowe's ratio test. Add the test images and the resulting stiched image to your report. ALso, describe your algorithm.







Try to implement a more complete version of a system for "Recognizing panoramas" -- i.e., a system that can take as input a "pile" of input images (including possible outliers), figure out the subsets that should be stitched together, and then stitch them together. Combine all the provided input images into one folder. Add your stiched output in the report and describe your algorithm.







Other things to try (These won't be graded)




Implement bundle adjustment or global nonlinear optimization to simultaneously refine transformation parameters between all pairs of images.




Learn about and experiment with image blending techniques and panorama mapping techniques (cylindrical or spherical).







Report requirements




Pairwise stitching:



Describe your solution, including parameters or implementation choices for feature extraction, putative matching, RANSAC, etc.
For the uttower pair provided, report the number of homography inliers and the average residual for the inliers (squared distance between the point coordinates in one image and the transformed coordinates of the
matching point in the other image). Display both the images along with the feature points. Also, display the locations of inlier matches in both images.

c. Display the final result of your stitching.

Multiple image stitching:



Describe your solution (outline of algorithm, parameter choices, etc.)
For each input sequence, list the order in which images are merged by your algorithm and show the intermediate image formed in the process (i.e. the image formed by stiching of the first two images that get 'stitched'). Also show your final output image. Discuss any issues or artifacts that may be evident in your output.



As usual, submit your PDF report at Gradescope and codes at Canvas. Note that grading will be primarily based on your report.




Acknowledgements




This homework was developed by Lana Lazebnik at UIUC.