Algorithm

• First you define matching points in two images. This can be done manually or automatically. To do this automatically
• You use corner detection to find features and adaptive-non-maximal suppression to thin out the points to only major features.
• Then you use feature description vectors to match features in one image to another.
• Outliers (errors in matching) are removed by RANSAC
• Then given the points you recover the homography, which gives the transformation matrix.
• This transformation matrix is then used to warp an image, which is then composited with the unwarped image to yield a stitched scene.

The automation point matching was based off of Brown, et al. The Harris Interest Point Detector provided in the support code was used to do the corner detection. Then adaptive non-maximal suppression was used. The minimum radius until a point of sufficiently stronger features were found was calculated for every interest point. The points with the largest such radii were then selected as the desired interest points.

Now that we have a number of interest points, we need to match points from one image to points in another, discarding points that have no matches. This is done by comparing distances between feature vectors. A feature vector is normally an 8x8 sample taken from a 40x40 region around the location of the interest point. I ended up using a 7x7 sample from a 35x35 region instead because i wanted the interest point to be centered (thus i need an odd size for the mask). 9x9 and larger feature vectors resulted in trouble finding matching feature points in narrow overlap zones. The mean of the samples was subtracted and then the sample was divided by its standard deviation to yield a lighting invariant feature vector. The distances between all the feature vectors were calculated. Then the ratio between the smallest distance and the next smallest distances were used as the value to be thresholded. Those pairs that make it pass the threshold are interest points with matching features in the other image, and the feature point in the other image with the smallest distance to this feature point is its match. I used a threshold of 0.5, which left some false positives.

To get rid of false positives RANSAC was used. I randomly picked 4 of the matched feature points and calculated the homography (see below). I then applied the transformation to all of the points in the first image to warp it to the points in the second. I tried 3000 times to find at least 10 points whose transformation had a square distance of less than 0.5 pixels from its counterpart. Once one such match was found, the points that matched were returned, thus discarding the outliers (false positives).

Given a set of points a homography could be recovered with least squared error. This is linear system of equations, and its form for 4 pairs of correspondences is seen here: projective Mappings I solved for the 8 entries in a ... h, reshaped it, and inserted the 9th entry (1).

To apply the warp we want a backwards mapping so that no holes are left. Thus we know the locations of the pixels we want to fill in. Given the warp, we want to know what pixels they came from. This is also a linear system of equations. The result of solving this is that we now know the locations of source pixels. These can be passed to interp2 to warp the source. Finally, the unwarped image is composited on top of the warped image by finding its offset in the final image first. Rectifying a square was done as a test to see if this worked. The results are not posted because they weren't particularly exciting. See rectify.m if you are interested.

Results

The results were generally decent, but not quite perfectly aligned. Flaws in the acquisition of the pictures in the first place might account for that. Another problem i ran into was on narrow strips. Taking matching points that are resemble a line results in an awful homography, the warp is just garbage, thus photos with narrow regions of overlap pose a problem.

Results Images