Connect the dots - connect the line between contour points_问答_开发者

I have a gray scale image of 64x64. I found the dots of the contour by a simple algorithm:

find brightest spot (Example: 100)
divide by 2 (100/2 = 50)
define a band around the result (50-5=45 to 50+5=55)
mark all dots that have value in the band (betwee开发者_高级运维n 45 to 55)

The question now is, how do I decide of the order of connecting the dots?

(All references will be accepted, links, thoughts, etc')

Your algorithm allows the entire image, save for one pixel, to be "the contour". I'm not sure that's exactly what you want; usually a contour is a border between two different regions. The problem with your method is that you can get huge blobs of pixels that have no particularly obvious traversal order. If you have a contour that is a single pixel thick, then the traversal order is much more obvious: clockwise or counterclockwise.

Consider the following image.

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

Here, I've marked everything "dark" (<50, perhaps) as % and everything bright as .. Now you can pick any pixel that is on the border between the two regions (I'll pick the dark side; you can draw the contour on the light side also, or with a little more work, directly between the light and dark sides.)

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

Now you try to travel along the outer edge of the dark region, one pixel at a time. First, you look in the direction of something bright (directly left, for example). Then you rotate around--counterclockwise, let's say--until you hit a dark pixel.

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

Once you hit position 5, you see that it's dark. So, you mark it as part of the contour and then try find the next piece on the contour by sweeping around starting from the pixel you just came from

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

Here 0 is where you came from--and you're not going back there--and then you try pixels 1 and 2 (both light, which is not okay), until you hit pixel 3, which is dark.

In this way, you can walk around the contour pixel by pixel--both identifying the contour and getting the order of pixels--until you collide with the same pixel you started with and will leave from it so that you hit the same pixel that you did the first time you left it. Then the contour is closed. In our example, where we're making an 8-connected contour (i.e. we look at 8 neighbors, not 4), we'd get the following (where @ denotes a contour point).

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

(You have to have this two-in-a-row criterion or if you have a dark region a single pixel wide, you'll walk up it but then not be able to walk back down along it.)

At this point, you've covered one entire boundary. But there might be others. Keep looking for dark pixels next to light ones until you have drawn a contour on top of all of them. Now you've converted your two-level picture (dark & bright pixels) into a set of contours.

If the contours end up too noisy, consider blurring the image first. That will smooth the contours out. (Alternatively, you can find the contours first and then average the coordinates with a moving window.)

In general, a given set of points can be connected in multiple ways to make 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 "dented in" to the center. But which side? There is no unique answer.

Other shapes can be much more complicated, with no obvious way to connect the dots.

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

I have also tried to create an algorithm that will connect contour dots into the smooth curve. See my open-source project http://outliner.codeplex.com. The idea is the same as proposed by FUZxxl but I do not understand his worries about complexity: the time of processing is proportional to the total length of all contour strokes.

I don't know if collecting those points will get you far. (I can come up with situations in which it's almost impossible to tell which order they should come in.)

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

Maybe try:

Start at a
Find the nearest point b
Connect a with b
and so on.

Probably not good, as complexity is something like O(n²). You may simplify this by looking only for points near the start, as aioobe suggest. This algorithm is good, if the points are just like 2-3px away from each other, but may create very strange grids.

See also Flood fill and the lovely applet under SO mapping-a-branching-tile-path .