Matrix of pixels to coordinates

Question

I have to convert a given matrix of pixels (coefficients are in a range from 0 to 255, since the matrix corresponds to a black and white image) into two lists. Both of them may be composed of lists, one containing the abscissas of the points, the other the ordinates.

As you can notice on the included picture, the first case corresponds to a single curve, whereas both the others involve multiple ones, crossing one each other. The algorithm should be able to make the difference between the two or three curves (in the two last examples), so in the two mainlists, a given sublist corresponds to a given curve.

I have absolutely no idea of what to start from...

One last thing : I'm seeking ideas on how to program this algorithm, so this is why I didn't add any specific programming language (if code may help any explanation, feel free to speak any language).

Thanks in advance >^.^<

Answer 1

Check out the Hough transform. It is a simple voting algorithm, that allows finding simple geometric shapes in images. One complication could be that your lines are not strictly straight. But it would give you equations on the lines it does find. Since your case is a little nonstandard I'd try to understand the algorithm itself and write my own implementation.

In my first implementation (centering a circle on a square in long focal depth image I took) I started with a very simple Python example I found online, rewrote it for my purposes and then later moved to C# for speed, since I needed more parameters (higher dimensional search space) than you need for this simple case.

In your case I would start with the simple assumption of a straight line. Then the Hough transform will give 1, 2 and 3 maxima respectively for your three cases.

The idea of the Hough transform is well described on wikipedia.

Here just the gist of the idea:

For a straight line think of giving each black pixel the right to vote for 180 possible lines that could go through it (one for each angle in single degree steps), then plotting the vote as histogram over a 2d space, where one dimension is the angle of the line, another is the distance from origin (using the Hesse normal form of the line for practical reasons rather than the common y= m x +b) and the z-dimension is the number of votes. The actual line formed by the black pixels will get more votes than any other possible line, so you are simply looking for the Maximum vote location in the transformation space (say in Python/numpy it would be argmax).

If there are two lines, you will find two clear maxima, the higher one with the longer or thicker line (more votes). You can then start playing with grayscale in your image, giving non-integer votes to pixels. You can also play with the resolution of the angle, depending on the content of your problem.