Lab: Feature Matching

CSC 262 - Computer Vision - Weinman

Summary:

You will use your prior feature detection and descriptor functions as the basis for a matching algorithm that will allow you to stitch images assuming a translational transformation.

Background:

You will need your kpdet.m and kpfeat.m from the previous two labs.

Deliverables

• The Matlab script(s) used to calculate values and and generate your report
• (10 points) Sorted feature distances (B.7)
• (10 points) Feature distance observations (B.8)
• (5 points) Matched feature offset (B.9)
• (10 points) Matched feature images (C.3)
• (10 points) Matched feature observations (C.9)
• (10 points) Estimated alignment (E.2)
• (10 points) Aligned images (E.4)
• (20 points) Alignment observations (E.5)
• (10 points) Professionalism of write-up

Preparation

Load a pair of images to be stitched from the course directory and convert them both to doubles.

/home/weinman/courses/CSC262/images/kpmatch1.png

/home/weinman/courses/CSC262/images/kpmatch2.png

I also uploaded the (rather small) versions of the images from lecture.

/home/weinman/courses/CSC262/images/lectkpmatch1.png

/home/weinman/courses/CSC262/images/lectkpmatch2.png

Alternatively, I don't really care what images you want to stitch, but these are a reasonable starting point. You may choose your own pair, but be sure they are not too large and are unlikely to give you spurious matches. (And of course, your report must cite their source and clarify your right to use them.)

Exercises

A. Matching Set-Up

1. Using your kpdet procedure, extract the keypoint locations from both images.
2. Using your kpfeat procedure, extract the keypoint descriptors from both images.
3. Use find to get the locations (row/col) of the features in both images.

B. Feature Matching

Choose one image to serve as your reference image. Eventually you will be (explicitly) looping over all the features from this reference image, comparing them (implicitly) to all the features in the other image. For now we will choose just one feature from the reference image to work with.

1. The function kpfeat should have returned an N×64 matrix of features for your reference image. Choose a feature index 1 < =k < =N from your reference image.
2. Extract the feature (the matrix row) as a vector and give it a (reasonable) variable name.
3. Recall that if a feature location indicated by kpdet could not be extracted in kpfeat, the entries should be NaN. The (vectorized) predicate procedure isnan determines whether values are NaN. Use this procedure to determine whether the feature you chose is "valid." If it is not, choose another value of k that is.
4. Next, we want to (ultimately) compute the Euclidean distance (a measure of anti-similarity) between your chosen feature and all the features of the other (non-reference) image. Calculate the element-wise difference between your reference feature vector and every feature vector from the other image. (The result should be N^′×64.)
   Note: You should use a vectorized operation, not a for loop.
5. Use this difference to calculate the Euclidean distances between your chosen feature and all the features of the other (non-reference) image.
   Note: You may need to tell Matlab along which dimension you would like to calculate a sum.
6. The resulting calculation should give you an N^′×1 vector of patch distances. Sort them in ascending order (the default), but use the version that returns two values from sort. This will provide you with not only the sorted values, but the original indices in the vector they came from.
7. Using bar, graph the distances of the top ten (closest) features.
8. Based on these distances, does your reference image feature appear to have a match in the other image? Discuss the quality of the match.
9. Calculate the estimated translation from the reference point location to the location of the best matching feature in the other image. Note that the translation is simply the difference in locations
   

   tr = xr−yr tc = xc−yc

   where (x_r,x_c) are the row and column of the feature in the reference image and (y_r,y_c) are the row and column of the matching feature in the other image.
   Note: If you used the sort command correctly, you know the index of the best matching feature in the descriptor matrix and thus its corresponding row and column as determined in A.3.

C. Visualizing Matching

Next, let's create a simple visualization of this feature match by connecting a line from one location to the matching location in the other image.

1. Concatenate your reference image and the other image, either horizontally or vertically. They are both the same size, so either way is fine.
2. Display the concatenated image using imshow.
3. Use the command line to draw a line from the feature location in the reference image to the putative matching feature location in the other image. For instance, to draw a line from (row,col) pairs (1,3) to (2,4), you might do

   line([3 4],[1 2]);

   Note that line uses a different ordering of the parameters! They are X and Y, rather than row and col.
   Hint: In order to figure out the correct end point, you will need to use the size of the (reference) image along the dimension they were concatened as well as the reference feature location, and the offset calculated in B.9.

D. Feature Matching Redux

Now we will find matches for all the features in our reference image.

1. Create a N×2 matrix of translation estimates for all the features in your reference image.
2. Add a for loop to iterate over all the descriptors from the reference image.
3. Inside your loop, add the command to extract the current feature vector from the matrix (as in B.2).
4. Next (inside the loop), if the current reference feature is invalid, discard the feature by setting the translation estimate for that feature to [NaN NaN] and continue the loop.
5. Measure the patch distance of the current reference feature to all the features in the other image (as in B.4 and B.5).
6. Sort the patch distances and retain the (sorted) indices (as in B.6).
7. If the nearest-neighbor distance ratio exceeds a threshold (Brown et al. use 0.5), then discard the match by setting the translation estimate for the current feature to [NaN NaN] and continue the loop.
8. Finally, set the translation estimate of the matched features (as in B.9).
9. How many matches are there? Where in the image are the features with matches occurring? (That is, are they distributed or clustered?) What will these observations entail for the ultimate alignment and image stitching results?

E. Alignment

At this point, you have some sparse feature matches that are hopefully somewhat reliable. It remains to calculate the optimal global alignment and then see how the result works out.

1. Recall that the least squares solution to the translational transformation problem is simply to calculate the mean of the translations (Szeliski 2022, p. 505). Use this formulation to find a single estimate of the best translation. Note that you will need to filter out all the NaN translations from your N×2 matrix (which mean can do).
2. What is the overall translation vector estimate? How much standard deviation is there in the estimate? What do you suppose this means for the potential quality of the aligned version of the images?
3. I have provided a procedure

   C = stitch(A, B, [Tr Tc]);

   that averages the images A and B under the translation given by Tr in the rows and Tc in the columns. Use this method and your estimated translation to create a stitched image.
4. Display and inspect your resulting stitched image.
5. How does the result look? Where does it work well? Where does it not work well? In both cases, why do you suppose that is so?
6. If you are not satisfied with the results, you may try
   1. getting a more robust estimate by using the median, rather than the mean, or
   2. tweaking parameters of your feature detection method (kpdet) or match method (i.e., the NNDR) so that more/fewer features are detected and/or more/fewer features are matched.
   If you employ any of these or other tweaks for improvement, fully describe and report on them in your write-up.

Acknowledgments

The images kpmatch* were taken by Jerod Weinman at Parque Nacional do Iguaçu in Brazil, the images lectkpmatch* were taken by Jerod Weinman in Marseilles, France. All images are Copyright 2007, 2008 and licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.