Aerial Image Recognition and Stitching
Given a large number of aerial (or satellite) photographs, stitching them together into a single large mosaic is hard. Historically, it was done with man power. Unfortunately, as the sizes of image sets grows into the thousands of pictures range, it may not even be possible for a human to correctly match the images. Now, it can largely be done with computers. The problem is that computers can't recognize images like we can. Since they have no concept of rivers, fields, etc. image recognition and orientation is a problem. Instead of trying to do things the "human" way, we should exploit computation power to find things in images that are "interesting" to a computer. Once the computer has found interesting points in multiple images, it should check those points between images to see if they match. If enough points match, the two images probably overlap.
Given a set of images (as few as two), we do the following operations to classify and orient the images.
- First, we execute the Scale Invariant Feature Transform (SIFT) algorithm on each image to discover the interesting points (aka features).
- With each image's interesting points, we pair each image with every other image, and compare the features between the two. If there aren't enough matching features (a minimum of 8), we discard the pair. Once this pairwise matching is done, we have a list of "good" pairs.
- For each "good" pair, we then take the matching points, and figure out which ones are good for orienting the images relative to each other so that their overlapping parts match. The points that are good for orienting the images are "inliers". Points that mess up the orientation are "outliers". If there aren't enough inliers (a minimum of 8 are required), the pair of images is discarded.
- Once all pairs of images have inliers, we find the image that overlaps the most (i.e. the image that occurs in the most pairs), and declare that the "root" image.
- We orient every other image relative to the root with a bundle adjustment, or a simple affine transformation
- With the orientations, we can put the images into a Geographic Information System (GIS) package like QGIS which will take our orientations and correctly place the images relative to the root image.
Scale Invariant Feature Transform (SIFT)
The SIFT algorithm is designed to find interesting points in images. The original paper, written by David Lowe, describing this algorithm is found here. An in-depth description of this algorithm is found on the Wikipedia page here. One interesting thing about SIFT is that it is invariant to all kinds of image transformations. For example, if an image is rotated, SIFT will output the same interesting point descriptions. Obviously, the points that are interesting are different, but the point description is the same. We can use the point descriptor to identify features that are common to multiple images.
Pairwise Matching
This stage of the computation attempts to find "reasonably unique" features that match between images. Given a point "A" in image1, we examine all of image2's features to find the two best matches to point "A". If the best match "B" is much closer than the second best match "C", then point A and B are "reasonably unique" matches. The measure used for closeness is euclidean distance. If point C is 5/3 farther away from A than B is, then A and B are unique matches. We use these unique points to find the inliers that can be used to correctly orient images.