Modified RANSAC algorithm

Home Page | RISC-V SoC | Web Proxy | OTA Bootloader | Gas Meter Reader | Laser Cutter | UK Maps | Modified RANSAC algorithm | MISRA | Smart Power Controller | Home Energy Monitor | Triac Power Control | Electricity Meter Reader | 3D Photos | Mobile Phone Stand | Reversing Sonar |

Background

I've been working on a project to detect the position of a guitar neck in an image. I'm using the excellent OpenCV image processing library.

The lines of strings have a special feature. They do not cross each other. They are usually not parallel (they tend to be further apart at the bridge than the neck). Their appearance also depends on the viewpoint. I experimented with line detection algorithms - eg. the Hough Transform. Using the Probabilistic Hough Transform I generated a set of line segments from the image (first pre-filtered using a Canny Filter).

I read some of the work by Marcos Nieto on Vanishing Point Detection which gave me the idea of detecting the converging parallels of the detected Hough line segments. However, this did not work, possibly because the Hough line segments were too course, so tended to lose convergence. You could see trends but not an accurate convergence point.

I did not calibrate the camera or take into account the fact that the image was curvilinear, not rectilinear. This may have also contributed to the problem. OpenCV does have good facilities for calibrating cameras, but I don't want to have to use a calibrated camera for this application.

So I started looking for a more accurate line detection algorithm.

RANSAC (Random Sample Consensus)

The original paper describing the RANSAC algorithm is Fischler Bolles 1981. It requires a set of points of interest as input. It then iteratively selects a subset of points, and calculates a straight line match for them. If a suitable match is found it then searches through the remaining points to see if they also match the line - these are known as inliers. The line is then recalculated using all the added and the original points. This process is repeated, keeping the best overall match, which is the result of the operation. This is described clearly on wikipedia, with a pseudocode description. Each iteration looks like this:

• select a random subset of points
• add these points to the inliers list
• derive a line from these points
• for each point not in the subset, add inliers that match the line, to a list
• generate a line for the inlier list.

Modified RANSAC

Using OpenCV I grab an image from a webcam or file. I then use the goodFeaturesToTrack() function to detect points of interest. The position of the features is then resolved to subpixel resolution using the cornerSubPix() function. This gives me a set of points to feed into the RANSAC algorithm.

OpenCV does not, however, expose the RANSAC code in its API. It uses it in the function findHomography(), but gives no control over the parameters.

In order to explore the technique I wrote my own implementation. I used Python as it is quicker to prototype in than C++. Looking at the algorithm I realised that there is a problem with it. Each loop picks n random points from the dataset and attempts to generate a model from them. It then finds other points that match the model and adds them to a list, the consensus_set. However, it is possible that some points in the initial guess are actually outliers, but these are always included in the inliers set. The algorithm seems wrong in this regard. These possible outliers will distort the resulting match calculation.

As the process is iterative, is is possible that a better match is later found that doesn't suffer from this problem. But I propose a simple modification to the RANSAC algorithm that should improve its accuracy and potentially reduce the number of iterations required to find a result.

• select a random subset of points
• derive a line from these points
• for each point in the total set, add inliers that match the line, to a list
• generate a line for the found inliers.

This would prevent stray outliers in the original random set from distorting the result.

Using a list of matches

My problem was to find the strings on a guitar neck. RANSAC only returns a single line, the best match it finds. However, in the process it will find many other lines. These are normally discarded.

RANSAC is also computationaly expensive, so throwing the intermediate calculations away is doubly wasteful.

My second modification to RANSAC is to keep all the found lines, not just the best match. Sort the lines by accuracy of fit. Starting with the first line, compile a set of candidate lines. Each line in the set returned by the modified RANSAC algorithm is compared to each of the candidate lines to see if it crosses in the image area. If it does, it is discarded (because guitar strings don't cross each other).

This gives me a set of lines which match well to the guitar strings.

The project is still "work in progress", but this is a good start to the problem of detecting the position of the guitar neck.

The top nylon strings don't show up at all well as they are translucent. This would not be a problem on steel strung guitars. I feel that the point detection process could be optimised to detect the points where a string crossed a fret. The OpenCV algorithm has a more generic point detection process. RANSAC has a number of parameters which need to be tuned to the image. This is bad if you want a system that needs no setting up. It should be possible to work out appropriate parameters that will perform across a wide range of images. RANSAC is also far too slow. I'm using Python, which will be very slow, but even a C++ algorithm will be slow. I want real time performance.

So, more work to do ...

The code, such as it is, is here