Feature Detection and Matching

Aaron Severance

In an attempt to match features between various images, I have implemented a version of the Harris corner detector, two feature descriptors, and two feature matching algorithms.

Harris corner detector:

The Harris corner detector was implemented as follows:

1)The image was used to construct a Gaussian pyramid.

2)Each level was decomposed into brightness elements only.

3)Each pixel was convolved with a derivative filter to obtain Ix and Iy.

4)The formula (strength = det M / trace M) was used to evaluate corner strength. This was then thresholded and the results stored in a temporary image.

5)Local maxima were found by comparing each potential feature to its neighbors in a 7x7 window.

Feature descriptors were next implemented. The first feature descriptor was no more than a 5x5 window around the point of interest. This proved acceptable if the image was altered by translation, or if random noise was added. A test of the affore-linked img1 versus a version that was altered by adding 20% random noise and then blurring (in Paint Shop Pro) had errors of only a fraction of a pixel on average. This is, of course, an extremely easy test. For a real image set (such as a benchmark of graf) the average error is 224 pixels. Since the image size in question was 800 x 640, this is obviously not an acceptable descriptor.

The second feature descriptor was designed to be rotation and intensity invariant. The following steps are used:

1. Compute the angle of the gradient from previously computed Ix and Iy values.
2. Take a certain number of pixels at each radius, starting at the norm to the gradient, and moving around a full circle. In this case, 1 pixel at radius 0, 8 at radius 1, and 16 at radius 2 were taken.
3. Normalize intensity to ½.

In my implementation, this feature descriptor did not work even as well as the square window, with average error of 262 pixels on the graf benchmark. Reasons may include that no subpixel filtering was used (so in many cases, the same pixel would be sampled repeatedly) and that ultimately less data was being used, as data near the edges of a square window would not be sampled with this algorithm.

To match features, the matching algorithms demonstrated on the course website were used. When testing, method 2 (ratio of best match to second best) consistently outperformed method 1 (threshold on match). When using method 2, matches were selected only if their best match was at least 2.5x better than their second best.