0%

RANSAC

In my previous project, image stitching project, I found the size of keypoints will have an impact on the execution time and the quality of the stitching. No matter what feature detection methods, SIFT or SURF, we find that if we have too many keypoints, it also will spend much time to generate the descriptors of features as well as the matching of them. Moreover, the outliers, some bad ones of the keypoints will exacerbate the perspective transform matrix. The task becomes much more complicated. Ultimately, I found a useful tool inspired by the findHomography method of OpenCV. When I first met this method, I was totally fascinated by it and that's why I want to write about it.

What is RANSAC

RANSAC is an iterative method to estimate parameters of a mathematical model from a set of observed data that contains outliers when outliers are to be accorded no influence on the values of the estimates. -- RANSAC, Wikipedia

As Wikipedia described, RANSAC is to find the best parameters combination to fit the model, which contains least outliers. As a matter of fact, I guess that we have already used this method partially into our daily problems. For example, I had prepared for GRE test in the past. In its math part, I usually stuck in some complicated calculation. However, this kind of tasks don't require us to find the accurate solution but analyze it quantitatively. With several substitutions for the options of the task, then I could get the almost-right solution. It was a much smarter way.

In our case, the features matching, we try to generate the random sequence to choose partial keypoints from the input as a set to generate the final transform matrix. These keypoints in use are all considered inliers.

Then we make use of the matrix to test the model by counting how many of the rest keypoints can fit the model with slight tolerance. The number of the inliers define the quality of the model, which means the more inlier keypoints it obtains, the much likely the model it is perfect (For most of the cases, it should be based on the ratio of the inliers and total number of keypoints).

After several iterations, we rank the model by the number of inliers. Finally, we select the best model as our ultimate model to use.

Why using OpenCL to implement it?

Obviously, the sub-processes of RANSAC are all independently computed and memory exclusively accessible, which is the key for the OpenCL framework to accelerate., like generating the model as well as testing the model. Thus, using OpenCL to speed up the process is a wise choice but also a tough one for beginners just because the development can be very steep. After all, as long as we need to boost up the project, we are supposed to use the parallel computing as an option of technique.