CODEWITHSUNDEEP
algorithm2ddynamic-programming
Roy T.
Roy T.

Reputation: 9638

Efficient computation of distance map

I have a 2 dimensional image filled with black and white pixels. Now for each white pixel I want to know (the distance to) the closest black pixel, and for each black pixel I want to know (the distance to) the closest white pixel.

A naive algorithm would be:

for(var y = 0; y < height; y++)
{
    for(var x = 0; x < width; x++)
    {
        var min = float.MaxValue;
        var me = image[x,y];

        for(var sy = 0; sy < height; sy++)
        {
            for(var sx = 0; sx < width; sx++)
            {
                var target = image[sx,sx];

                if(target != me)
                {
                    // target is the opposite color
                    var distance = Distance(x, y, sx, sy);
                    if(distance < min)
                    {
                        min = distance;
                    }
                }       
            }
        }

        distanecImage[x,y] = min;
    }
}

Which I think is of quadratic complexity. Is there some way to speed this up? I had an idea that if you know the closest target pixel for all your neighbors you can compute your own closest distance without having to loop over the entire image. But I'm having trouble producing an algorithm using that idea or how such an algorithm would be called.

I'm limited to DirectX9 level hardware, but if needed I could use the GPU to speed things up. The have an approximate maximum size of 256x256.

Upvotes: 0

Views: 289

Answers (1)

sds
sds

Reputation: 60044

Terminology: you have 4 for loops: two outer loops scanning points and two inner loops finding the closest point.

Dramatically speed-up the inner loops

You are scanning the image row by row looking at every point.

You should instead scan points in a spiral from the closest to the farthest stopping as soon as you know you found what you are looking for:

spiral

Your point is X, you scan points in the order 1,2,3... as depicted. (note that finding a pixel at 20 does not mean you can stop - you can find a closer one at 22).

(created with Gimp - what should I use instead?!)

Use old results for extra speed up

If you keep the closest point found for each already processed point, you can achieve an additional speedup by only scanning a part of the image for each next point.

enter image description here

you will need to think carefully where you need to look for, but, generally, you can expect a 4x speedup.

Consider the worst case

Your worst case is white image with a single black dot in a corner. My improvements will buy you nothing in this case.

Upvotes: 1

Related Questions