performance - Finding closest non-black pixel in an image fast

Question

I have a 2D image randomly and sparsely scattered with pixels.
given a point on the image, I need to find the distance to the closest pixel that is not in the background color (black).
What is the fastest way to do this?

The only method I could come up with is building a kd-tree for the pixels. but I would really want to avoid such expensive preprocessing. also, it seems that a kd-tree gives me more than I need. I only need the distance to something and I don't care about what this something is.

Answer 1

Personally, I'd ignore MusiGenesis' suggestion of a lookup table.

Calculating the distance between pixels is not expensive, particularly as for this initial test you don't need the actual distance so there's no need to take the square root. You can work with distance^2, i.e:

r^2 = dx^2 + dy^2

Also, if you're going outwards one pixel at a time remember that:

(n + 1)^2 = n^2 + 2n + 1

or if nx is the current value and ox is the previous value:

    nx^2  = ox^2 + 2ox + 1
          = ox^2 + 2(nx - 1) + 1
          = ox^2 + 2nx - 1
=>  nx^2 += 2nx - 1 

It's easy to see how this works:

1^2 =  0 + 2*1 - 1 =  1
2^2 =  1 + 2*2 - 1 =  4
3^2 =  4 + 2*3 - 1 =  9
4^2 =  9 + 2*4 - 1 = 16
5^2 = 16 + 2*5 - 1 = 25
etc...

So, in each iteration you therefore need only retain some intermediate variables thus:

int dx2 = 0, dy2, r2;
for (dx = 1; dx < w; ++dx) {  // ignoring bounds checks
   dx2 += (dx << 1) - 1;
   dy2 = 0;
   for (dy = 1; dy < h; ++dy) {
       dy2 += (dy << 1) - 1;
       r2 = dx2 + dy2;
       // do tests here
   }
}

Tada! r^2 calculation with only bit shifts, adds and subtracts :)

Of course, on any decent modern CPU calculating r^2 = dx*dx + dy*dy might be just as fast as this...