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

Search "Nearest neighbor search", first two links in Google should help you.

If you are only doing this for 1 pixel per image, I think your best bet is just a linear search, 1 pixel width box at time outwards. You can't take the first point you find, if your search box is square. You have to be careful

Answer 2

Yes, the Nearest neighbor search is good, but does not guarantee you'll find the 'nearest'. Moving one pixel out each time will produce a square search - the diagonals will be farther away than the horizontal / vertical. If this is important, you'll want to verify - continue expanding until the absolute horizontal has a distance greater than the 'found' pixel, and then calculate distances on all non-black pixels that were located.

Answer 3

You didn't specify how you want to measure distance. I'll assume L1 (rectilinear) because it's easier; possibly these ideas could be modified for L2 (Euclidean).

If you're only doing this for relatively few pixels, then just search outward from the source pixel in a spiral until you hit a nonblack one.

If you're doing this for many/all of them, how about this: Build a 2-D array the size of the image, where each cell stores the distance to the nearest nonblack pixel (and if necessary, the coordinates of that pixel). Do four line sweeps: left to right, right to left, bottom to top, and top to bottom. Consider the left to right sweep; as you sweep, keep a 1-D column containing the last nonblack pixel seen in each row, and mark each cell in the 2-D array with the distance to and/or coordinates of that pixel. O(n^2).

Alternatively, a k-d tree is overkill; you could use a quadtree. Only a little more difficult to code than my line sweep, a little more memory (but less than twice as much), and possibly faster.

Answer 4

As Pyro says, search the perimeter of a square that you keep moving out one pixel at a time from your original point (i.e. increasing the width and height by two pixels at a time). When you hit a non-black pixel, you calculate the distance (this is your first expensive calculation) and then continue searching outwards until the width of your box is twice the distance to the first found point (any points beyond this cannot possibly be closer than your original found pixel). Save any non-black points you find during this part, and then calculate each of their distances to see if any of them are closer than your original point.

In an ideal find, you only have to make one expensive distance calculation.

Update: Because you're calculating pixel-to-pixel distances here (instead of arbitrary precision floating point locations), you can speed up this algorithm substantially by using a pre-calculated lookup table (just a height-by-width array) to give you distance as a function of x and y. A 100x100 array costs you essentially 40K of memory and covers a 200x200 square around the original point, and spares you the cost of doing an expensive distance calculation (whether Pythagorean or matrix algebra) for every colored pixel you find. This array could even be pre-calculated and embedded in your app as a resource, to spare you the initial calculation time (this is probably serious overkill).

Update 2: Also, there are ways to optimize searching the square perimeter. Your search should start at the four points that intersect the axes and move one pixel at a time towards the corners (you have 8 moving search points, which could easily make this more trouble than it's worth, depending on your application's requirements). As soon as you locate a colored pixel, there is no need to continue towards the corners, as the remaining points are all further from the origin.

After the first found pixel, you can further restrict the additional search area required to the minimum by using the lookup table to ensure that each searched point is closer than the found point (again starting at the axes, and stopping when the distance limit is reached). This second optimization would probably be much too expensive to employ if you had to calculate each distance on the fly.

If the nearest pixel is within the 200x200 box (or whatever size works for your data), you will only search within a circle bounded by the pixel, doing only lookups and <>comparisons.

Answer 5

I would do a simple lookup table - for every pixel, precalculate distance to the closest non-black pixel and store the value in the same offset as the corresponding pixel. Of course, this way you will need more memory.

Answer 6

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...

Answer 7

Ok, this sounds interesting. I made a c++ version of a soulution, I don't know if this helps you. I think it works fast enough as it's almost instant on a 800*600 matrix. If you have any questions just ask.

Sorry for any mistakes I've made, it's a 10min code... This is a iterative version (I was planing on making a recursive one too, but I've changed my mind). The algorithm could be improved by not adding any point to the points array that is to a larger distance from the starting point then the min_dist, but this involves calculating for each pixel (despite it's color) the distance from the starting point.

Hope that helps

//(c++ version)
#include<iostream>
#include<cmath>
#include<ctime>
using namespace std;
//ITERATIVE VERSION

//picture witdh&height
#define width 800
#define height 600
//indexex
int i,j;

//initial point coordinates
int x,y;
//variables to work with the array
int p,u;
//minimum dist
double min_dist=2000000000;
//array for memorising the points added
struct point{
  int x;
  int y;
} points[width*height];
double dist;
bool viz[width][height];
// direction vectors, used for adding adjacent points in the "points" array.
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
int k,nX,nY;
//we will generate an image with white&black pixels (0&1)
bool image[width-1][height-1];
int main(){
    srand(time(0));
    //generate the random pic
    for(i=1;i<=width-1;i++)
        for(j=1;j<=height-1;j++)
            if(rand()%10001<=9999) //9999/10000 chances of generating a black pixel
            image[i][j]=0;
            else image[i][j]=1;
    //random coordinates for starting x&y
    x=rand()%width;
    y=rand()%height;
    p=1;u=1;
    points[1].x=x;
    points[1].y=y;
    while(p<=u){
        for(k=0;k<=7;k++){
          nX=points[p].x+dx[k];
          nY=points[p].y+dy[k];
          //nX&nY are the coordinates for the next point
          //if we haven't added the point yet
          //also check if the point is valid
          if(nX>0&&nY>0&&nX<width&&nY<height)
          if(viz[nX][nY] == 0 ){
              //mark it as added
              viz[nX][nY]=1;
              //add it in the array
              u++;
              points[u].x=nX;
              points[u].y=nY;
              //if it's not black
              if(image[nX][nY]!=0){
              //calculate the distance
              dist=(x-nX)*(x-nX) + (y-nY)*(y-nY);
              dist=sqrt(dist);
              //if the dist is shorter than the minimum, we save it
              if(dist<min_dist)
                  min_dist=dist;
                  //you could save the coordinates of the point that has
                  //the minimum distance too, like sX=nX;, sY=nY;
              }
            }
        }
        p++;
}
    cout<<"Minimum dist:"<<min_dist<<"\n";
return 0;
}