Connect the dots - connect the line between the contour points

Question

I have a 64x64 grayscale image. I found the contour points with a simple algorithm:

• find the brightest spot (example: 100)
• divide by 2 (100/2 = 50)
• determine the range around the result (50-5 = from 45 to 50 + 5 = 55)
• check all the points that have a value in the range (45 to 55).

The question now is, how do I choose the connection order of the dots?

(All links will be accepted, links, thoughts, etc.)

Answer 1

Your algorithm allows the whole image, with the exception of one pixel, to be a "path". I'm not sure exactly what you want; usually the outline is the boundary between two different regions. The problem with your method is that you can get huge pixels of pixels that do not have a particularly obvious traversal order. If you have a path that is one pixel thick, then the traversal order is much more obvious: clockwise or counterclockwise.

Consider the following image.

........ ..%%%%.. .%%%%... ...%%%%. ....%... ........ 

Here I marked all the "dark" (<50, maybe) as % and all bright as . . Now you can select any pixel that is on the border between the two regions (I will choose the dark side, you can also draw an outline on the light side or with a little more work, right between the light and dark sides.)

 ........ ..%%%%.. .*%%%... ...%%%%. ....%... ........ 

Now you are trying to move around the outer edge of the dark area, one pixel at a time. Firstly, you are looking towards something bright (right on the left, for example). Then you spin around - counterclockwise, let them say - until you click on the dark pixel.

 ........ ..%%%%.. 1*5%%... 234%%%%. ....%... ........ 

As soon as you press position 5 , you will see that it is dark. So you mark it as part of the path, and then try to find the next fragment on the path by expanding it starting from the pixel that you just came from

 ........ ..%%%%.. .0*%%... .123%%%. ....%... ........ 

Here is 0 , where you came from, and you won’t return there, and then you try pixels 1 and 2 (both lights, which is not entirely normal) until you click on pixel 3 , which is dark.

That way, you can move around the pixels of the path by the pixels — both identify the path and get the order of the pixels — until you come across the same pixel that you started at and walk away from it so that you hit the same pixel that you did the first time you left it. Then the circuit is closed. In our example, where we create an 8-connected contour (i.e., we look at 8 neighbors, not 4), we get the following (where @ denotes a contour point).

 ........ ..@ @@@.. .@ @%@... ...@ %@@. ....@... ........ 

(You must have this “two in a row” criterion, or if you have a dark area one pixel wide, you will go up and then you cannot go down it).

At this point, you have covered one whole border. But there may be others. Keep looking for dark pixels next to bright ones until you draw an outline on top of all of them. Now you have converted a two-level image (dark and bright pixels) into a set of outlines.

If the contours are too noisy, try blurring the image first. This will smooth out the contours. (Alternatively, you can first find the contours, and then average the coordinates using a moving window.)

Answer 2

In general, a given set of points can be connected in several ways to create different shapes.

For example, consider a set of 5 points consisting of the corners of a square and its center. These points can be connected to form a square with one side "pressed" into the center. But which side? There is no single answer.

Other forms can be much more complicated without the obvious way of connecting dots.

If you are allowed to reduce your set of points to a convex body , then it would be much easier.

Answer 3

I also tried to create an algorithm that connects the contour points into a smooth curve. See My open source project http://outliner.codeplex.com . The idea is the same as proposed by FUZxxl, but I don’t understand his concerns about complexity: processing time is proportional to the total length of all contour strokes.

Answer 4

I do not know if he will be able to collect these points far. (I can come up with situations in which it is almost impossible to determine in what order they should come.)

How about going to the brightest point.
Go to the brightness point, say 360 points surrounding this point, at a distance of, say, 5 pixels.
Continue on, but make sure you don’t go back to where you came from :)

Answer 5

Perhaps try:

• Start with
• Find the nearest point b
• Connect a to b
• etc.

Probably not very good, since complexity is something like O (n²). You can simplify this by looking only at the points near the start, as aioobe suggests. This algorithm is good if the points are at a distance of 2-3 pixels from each other, but can create very strange grids.

Answer 6

See also Stream Filling and a great applet under SO mapping-a-branching-tile-path .