CS129 Project6 Automated Panorama Stitching

Yun Miao, Nov 26 2012

half dome

This project can be divided into two steps. The first part is to find matching features using feature detector. The second part is to recover homographic projection between two images.

Detecting and matching feature points

A Harris corner detector is used to find corner points in images. We then turn those points into feature descriptors by downsampling and normalizing the pixels around the corner points. In my program, a 40 by 40 patch around a corner point is downsampled into an 8 by 8 descriptor. The 8 by 8 descriptor matrix is then normalized: we subtract the mean from the matrix and then divide every entry by its standard deviation.

Adaptive Non-Maximum Suppression

Harris corner detector returns the strongest corners in an image. However, we would like to have an even distribution of features across the image. The Adaptive Non-Maximum Suppression (ANMS) algorithm is applied to suppress corners that are closely located. They don't add information to our algorithm. As a result of ANMS, we get an even distribution of corners. Below are different corner detection results with no ANMS and with ANMS:

no ANMS 500 corner points no ANMS 500 corner points
with ANMS 500 corner points with ANMS 500 corner points

Once the lists of corner points are turned into lists of feature descriptors, we applied the dist2 function to compute the distance between every pair of descriptors. One can also try to find the SSD between every pair of descriptors. If we have 500 descriptors, this step gives us a 499 by 499 distance matrix. The n_th row is the n_th descriptor's distances to the other 499 descriptors. The minimum of that row means that we potentially have a match for the n_th descriptor. We then apply Lowe's ratio: min/2nd-min, minimum and the 2nd minimum entry of the n_th row. Smaller ratio means better match between the n_th descriptor and the descriptor corresponding to the min. If the ratio is not small or close to one, it means that the n_th descriptor is a match to at least two other descriptors. We don't want those wavering descriptors. So we select the smallest ratios to find our strongest matching features. Our program defaults the number of matching features to 30. Too many features may confuse the algorithm later.

30 strongest matching features

Robustly recovering homographies

To compute the project mapping between images, we need at least four pairs of feature points. The formula for computing projective mapping is detailed in this excerpt. When we have more than four pairs of feature points, the equations are overconstrained, we need to use least-squares to find the optimal solution. One nice thing about MATLAB is that it computes least-squares solution automatically with the "\" operator.

RANSAC

The features we found may contain some outliers. To exclude the outliers, we use the RANSAC algorithm. I find the following pseudo code from the lecture helpful:

RANSAC loop:

  1. Select four feature pairs (at random)
  2. Compute homography H (exact)
  3. Compute inliers where distance(pi', H(pi)) < error; add inliers to the four pairs; repeat step 1
  4. Keep the largest set of inliers
  5. Re-compute least-squares H estimate on all of the inliers

I used the recommended 1000 iteration and 0.5 error for RANSAC. It worked well. Here are some results.

Results

cable car

Half Dome

More ImagesFewer Images

My Images