cs129 / Automated Panorama Stitching

CS129 / Project 6 / Automated Panorama Stitching

1. Define correspondences

1.1 Adaptive non-maximal suppression

After interest point detection using Harris matrix, we have interest points with high corner strength. In this part, we will use adaptive non-maximal suppression strategy(ANMS) to select part of the points from the results of the Harris detection, which aims to restrict the maximal number of interest points and make them well distributed.

Here is the method:


1.
for every Harris interest points Xi
   for all other points Xj
      compare the corner strength between Xi and Xj
      if corner_strength(Xi) less than c_robust* corner_strength(Xj) (c_robust = 0.9)
         calculate the distance r between point i and point j
      end
   end
   record minimal r for all Xj   
end

2.
Sort the Harris interest points by the minimal r in descending order and take top N.
(in this case N = 0.5*number_Harris points)

Harris interest points	Strongest 0.5*num_Harris	ANMS 0.5*num_Harris

1.2 Feature descriptor extraction

In this session, we sample 40*40 size patches for every interest points(as center of the patches), and then we downsample them to 8*8 size patches as the feature descriptor.

1.3 Feature matching

For every features in imageA, loop through all patches from imageB and compute the distance between them and find the nearest(e1NN) and the second nearest distance(e2NN). If they pass the Lowe's "ratio test"(e1NN/e2NN less than threshold), we can consider the interest point of imageA feature and interest point from imageB nearest feature as correspondence. Lowe’s technique works by assuming that the interest point of e1NN is potential correct match, and the point of e2NN is a wrong match. And a correct match should have substantially smaller distance than the wrong one. So if the ratio of e1NN and e2NN less than some threshold, we can basically think those two interest points from imageA and imageB are matched.

Correspondence points of two images with threshold = 0.11

2. Recover the homography using RANSAC

After Lowe's ratio test we mentioned at session 1.3, there are still some outliers left, which would have bad effect on homography calculating. To recover the homography robustly, RANSAC algorithm can be used. The main idea of the RANSAC is that inlier pairs from two images can be connected by a same homography, but the outliers are wrong in different ways.

Here is the method:

For every RANSAC loop (num_iteration equals to 1000)

Select four feature pairs randomly.
Computer the homography H using 4 pairs from step 1 by SVD.
Record inliers, where SSD(Pi,H*Pi') less than tolerance (tolerance = 0.5)

Select largest set of inliers and recompute the robust homography using them.

3. Result images

3.1 My images

Input:

Output:

4. Extra credit

4.1 Add rotation invariance

In Feature descriptor extraction session, if the two images have the different rotation, the feature descriptors we directly get from those two images will not have enough correspondence. That would lead a failure in the feature matching step. To solve this problem, we add orientation to the patches when extracting them. The orientation can be decided by the direction of blurred gradient. By adding orientation to the patches, they could become rotation invariance.

Feature matching results without adding rotation invariance

Feature matching results with adding rotation invariance

4.2 Panorama recognition

The goal of this part is to automaticaly recognize images from panorama from set of images and stitch them together. The main problem is to decide if the two images are from one panorama. The method I take is that after the feature matching step if the number of correspondence pairs is more than a threshold, we can think the two images are from one panorama. The threshold I choose is 4, which is just enough for homography recovering. This method works well in most of cases, but some special situations. For instance, there are might a few(usually one or two) special points that have correspondence with several points from the other images accidentally, and the program would consider those two images are from the same panorama and cause unpleasant results

One special point from right image has lots of correspondence in the left image

To fix this problem, I modified the method by making the two sets of points unique before calculating the number of correspondence pairs. When both the numbers of unique points of two sets are larger than threshold, we can think they come from one panorama. For last mentioned example, the correspondence points in the left image are more than 4 but there is only one point in the right image, so those two images are not from one panorama.