RANSAC and SIFT Features

Last week I worked on implementing RANSAC for my feature matching and then, over the weekend, I discovered that OpenCV already had an implementation of RANSAC (cvFindFundamentalMat). I decided to use OpenCV's version since it's more efficient than mine.

Anyway, my particular application of RANSAC is used to estimate the Fundamental Matrix (whereas Philippe's estimates a linear transformation) for two views of the same scene. RANSAC uses the matches I found using the Harris Corner Detector and Ben-Haim Features.

As Serge explained last Monday (using the mailbox example), given a point in one image the corresponding point in the second will exist along a line. This line is called an "epipolar line" and it greatly simplifies the search (click here for more info on Epipolar Geometry) . The fundamental matrix is a 3x3 matrix that relates corresponding points and can be used to find these epipolar lines. Given a point m1 in the first image and the fundamental matrix F, the epipolar line l2 in the second image is given by the equation l2 = F m1. Since l2 is a vector of 3 elements (l2 = [a, b, c]'), the equation of the line is then ax + by + c = 0.

Here's an example using my earth model. The point on the left is matched to points along the epipolar line on the right:


The matching points were found by thresholding the corners I found earlier with the "Sampson distance." The Sampson distance is an approximation to the reprojection error (basically, the distance between the point and the epipolar line), which I thresholded at 1.5 pixels. NCC, or Ben-Haim's, can then be used to find the best match along these lines to establish more matches, but I'll save this task for later. I'm falling behind schedule and I need to move on to reconstruction. From what I've read, the fundamental matrix can be decomposed into projection matrices to obtain 3D structure ...

I've also tried Lowe's SIFT Keypoint Detector as an alternative to my feature detection and correspondence algorithm. The demo program came with code for matching detected SIFT features, so I integrated it into my OpenCV code. The results are much more accurate than my previous results.

SIFT found 179 matches for my earth model with only one obvious outlier (I manually stepped through all 179 points just to be sure):


SIFT also works surprisingly well on my rubix cube:


It still has several outliers, but the result is much better than my current algorithm which is still utterly confused even when the cube is scrambled:

(Note: this is not an actual rubix cube configuration; I just randomly swapped the colors in the texture map.)

I'm considering using SIFT as an option in my application. But, unless I implement the algorithm myself, you'd need to run the demo separately on each image to detect the keypoints and then pass them into my program. However, for situations like my rubix cube, this extra step may be necessary in order to obtain any results.