Logan Barnes (ltbarnes)

Corner Detection and Interest Points

Corner-like objects from a Statue of Liberty image.

To begin the process of matching points between images we first have to find reasonable points to compare from each image. If we look at areas of the image with large empty spaces or long smooth lines it can be difficult find distinct points that are easily matched to other images. Many of these points will have the same characteristics as their neighbors making the matching process an unreasonable task. This leads us to corners and corner-like shapes where we have fairly large differences between neighboring points.

The obscurity of comparing spaces and lines as opposed to corners.

The fact that corner pixels change more noticeably as we move away from them allows us to find them by comparing the derivatives (or rates of change) at each pixel. To do this we filter each image with a Gaussian derivative filter in both the x-direction and the y-direction. Each filter only finds edge-like pixels (as opposed to corners) since they are only comparing changes in a particular direction. However since each filter finds edges perpendicular to the other, any points highlighted by both filters are assumed to be corner pixels or interest points. To further increase the accuracy of our corner detector we can then remove all pixels below a certain threshold leaving only the strongest interest points.

From left to right: the original image, the filtered image, the thresholded image.

Features

After finding suitable interest points in each image we need to figure out how to go about matching these points to their corresponding pairs in other images. This requires a standard way of representing all interest points that won't vary largely from one image to the next. To do this we can again use derivatives again to determine how much the pixels surrounding any given point might change. By taking the 16x16 pixel square surrounding each interest point and finding the cumulative derivatives for these points in each of 8 directions we can create a fairly large histogram used for comparisons. Each histogram will map to a single interest point but will contain the magnitude and directional information for the larger 16x16 patches. These small localized patches will be large enough to accurately compare the interest points from one image to the next but small enough to not disrupt the matching process when the camera positions are slightly altered (shown below).

Matches can still be made even when the camera angle is changed.

Matching

Figure 1.1: The top 100 matches found between two images (correct matches in green, incorrect in red).

The final step of our process is to match similar points from one image to those of another. To do this we can compare the histograms mapped to each point in one image to the histograms mapped to the points in another. Points from each image with closely related histograms are then paired together and considered as matches. This leads to problems however when there are many similar histograms in each image since small alterations in scale, lighting, or direction might lead to incorrect pairings

The Ratio Test

To decrease our chances of incorrectly matching similar histograms we can compare the difference of the most similar histogram to the difference of the second most similar histogram. If these differences are relatively close then we might have a lot of similar matches and we can't be as confident in our connection. If these differences are far apart however we can be much more certain there aren't any other potential matches. This allows us to create a list of confidences for our matches and by only choosing the points we are most confident in we can be much more certain our matches are correct. Figure 1.1 shows the difference between the corner detection points and the final 100 matches with the highest confidences.