link points in a smart way

Hi all,

Is there an efficient way to link points from a points cloud on an image ?

Let me explain. i've the attached picture, and i would like to draw, according to the points, line that fits them in a good way. I've tried pixel by pixel , looking for neighbours and linking them, but i didn't obtained anything good. The result I would like to obtain is similar to the 2nd attached picture (roughly, because it's been drawn on paint for the sample here).

I'm working with c#.

For information, know that i know the orientation of the points (calculated from gradient and least square estimation), if it can help you to help me... ^^

Thanks !

For information, if it can help somebody, i'm gonna blur the image to make some groups of points. Then, i'll make a skeletonnization of these groups. I think the results won't be so bad

Suggetion : (may be a bad idea)

Divide your image in bigger chunks than just on pixel basis and count on each chuck how many white dots you have.

Let's take my image and say black squares are numbred like this
1 2
3 4
and red
a b
c d
I will call N(x) the number of white dots in the chuck x (density)

I would do something like this

Foreach red chuck x
get list of overleap black squares for x
if N(x) == N(1)
then link x and 1
if N(x) == N(2)
then link x and 2

Of course you'll have to maitain a list where you keep track of which red squares overleap black squares

Also both densities don't have to be exactly equal, but almost equal (that a sensivisity parameter)

Once again this is what came in my mind fast, there may be existing better solutions for that