The described algorithm generates a panorama from a set of adjacent photos and it is based on the paper
Multi-Image Matching using Multi-Scale Oriented Patches but with several simplifications. The algorithm consider that the transformations between different images are projective and therefore the photographs should be taken from the same point of view but with different view directions. To align the images, the algorithm needs to recover the parameters of the transformation between each pair of images. In this case the transformation is an homography. This process involves several steps to make sure no outliers are present in the final set of points used to compute the projective transformation.
1. Interest Points Selection
A large set of interest points is initially generated by a
Single Scale Harris Corner Detector (code provided by A. Efros), and then sub-sampled by the
Adaptive Non-Maximal Suppression Algorithm, that based on the corner strength, retains only the points that are a maximum in a neighbor of a certain radius. In this way the
ANMS ensures that the sample points are spatially well distributed over the entire image.
In green, interest points etained by the ANMS algorithm.
|
|
2. Feature Descriptors Extraction
Pairs of corresponding interest points from the two images, are coupled based on the similarity of the pixels around them. An axis-aligned 40×40 patch, is extracted around the location of each interest point. This
feature descriptor, is subsequently blurred and reduced to 8x8 in order to make the
feature matching process translation invariant in a range of about five pixels in every direction.
Set of zero-mean feature descriptors.
|
|
3. Feature Matching Process
This process consist of finding couples of feature descriptors that looks similar. This is accomplished through an exhaustive
Nearest Neighbor Search where the distance is considered the
l2-norm of the difference between pairs of descriptors. Feature descriptors are considered coupled only if their 1-NN/2-NN ratio is within 0.3 otherwise they are discarded. Setting the threshold at 0.3 highly reduce the number of
outliers, making the final step almost useless.
4. RANdom SAmple Consensus
The RANSAC algorithm first randomly selects four interest points retained by the
Feature Matching Process. Given these four interest points the algorithm computes an exact homography and then counts the number of
inliers (couples of interest points) that agree with that particular transformation.
This process is repeated until the number of
inliers that agree with a particular homography computed through the four randomly selected points, is bigger of a user-defined threshold. In the last step, the RANSAC algorithm calculate a more robust
least square homography, using all the
inliers that agreed with the selected exact homography.
Final set of points used to compute the homography.
|
|
5. Image Warping and Blending
The
least square homography computed in the previous step is utilized to warp one of the two images, that is subsequently blended together with the other image, giving the final result.
Panorama of Don's Office made of three adjacent photographs.
|
