More Efficient Way to Find Nearest Black Pixel?

Programming Questions

fasteddy86

More Efficient Way to Find Nearest Black Pixel?

in Programming Questions • 9 months ago

I've been attempting to come up with a way to determine the nearest black pixel to a given coordinate. Initially, I was trying to use pvectors, but I was having trouble sorting them (I'm new to Processing, and programming in general). In the end, I landed on the following:

PImage img;
int col; // variable to capture colour of pixels
int currx = 1; // current value of x coordinate
int curry = 1; // current value of y coordinate
int targx; // x coordinate of closest black pixel
int targy; // y coordinate of closest black pixel
float targdist; // distance (euclidean) to target
void setup() {
img = loadImage("test.png");
size(img.width, img.height);
targdist = dist(0,0,img.width,img.height); // set initial target distance to diagonal of image
for (int y=0; y<img.height; y++) { // loop through all pixels
for (int x=0; x<img.width; x++) {
col = img.get(x, y) & 0xFF;
float z;
if(col == 0){ // if pixel is black
z = dist(currx, curry, x, y); // calculate distance between current coord and target
if(z < targdist) { // if current black pixel closer than previous
targdist = z; // update target distance and coordinates
targx = x;
targy = y;
}
}
}
}
}
void draw() {
image(img, 0, 0);
print("(" + targx + ", " + targy + ") is " + targdist + " units away from (" + currx + ", " + curry + ")");
noLoop();
}

However, I'm wondering if there's a more efficient way of doing this. For now, this meets my needs, but in the future I may want to extend this to find, say, the closest gray -> black pixel pair for each gray pixel (not sure I worded that well, but for each gray pixel, find the closest black pixel to it). I doubt this method will work well for that. Can anyone point me in the best direction to tackle something like that?

Replies(10)

amnon.owed

Re: More Efficient Way to Find Nearest Black Pixel?

9 months ago

I'm thinking you could start from the pixel itself and then check the rings closest around it. So the first check is 8 pixels. If nothing is found you check the 16 around that etc.

amnon.owed

Re: More Efficient Way to Find Nearest Black Pixel?

9 months ago

I tested my own suggestion and I must say it's not really a general purpose solution. As one would expect from the description, it performs better when the black pixels are close around the original position. Then it can be a few times faster. However when there are no close black pixels, the whole thing takes more elaborate calculations and thus is slower (may also be my test implementation). It's a bit like cops with a crime. If you know where the perp is you narrow the search area. When you have no idea where he might be, just search everything. But since the latter is the case here, a broad sweep is the easiest solution I think.

Your original formula is simple and it performs relatively well. You could improve the efficiency of your code a bit by using the pixel array directly instead of get() and perhaps use a non-squareroot distance calculation. If there are a lot of black pixels in the image, your code will run slow, because it will do a lot of distance calculations. For general images (read: not mostly black), where the location of the black pixels is unknown, it's a suitable method I think.

asimes

Re: More Efficient Way to Find Nearest Black Pixel?

9 months ago

As amnon.owed said using dist() will significantly slow down your search because it uses square root. Instead use this:

theDist = sq(currX-x)+sq(currY-y);

Even though this doesn't use square root, it still has enough information for what the smallest distance would be. To get the actual distance (if needed) perform a sqrt() on it.

asimes

Re: More Efficient Way to Find Nearest Black Pixel?

9 months ago

This isn't performing the distance check, but it is a fairly minimalistic way to search for the black pixels:

void setup() {
size(800, 800, P2D);
loadPixels();
// Randomly place a 2x2 square of black pixels
int rand = (int)random(width*height-width-1);
pixels[rand] = 0;
pixels[rand+1] = 0;
pixels[rand+width] = 0;
pixels[rand+width+1] = 0;
updatePixels();
int count = 0;
for (int i = 0; i < width*height; i++) {
if (pixels[i] == 0) count++;
}
println(count); // Proof of having found 4 black pixels
exit();
}

Chrisir

Re: More Efficient Way to Find Nearest Black Pixel?

9 months ago

I am not happy with these solutions.

first when our pixel is at 300,300 and our black pixel is at 310,300 we check a lot of pixels in vain.

let's therefore really start at the pixel and in a for loop go right with pixels[x+i] and left with pixels[x-i]

Second, maybe we can improve this. our pixel has 4 neighbour areas: top left, top right, bottom left, bottom right. now let's get those with get. i don't have the maths but isn't there a bit-operation to check if there is a black point in it at all. then scan it. let us say area is 8x8.

writing this from an iPad which is really clumsy somehow....

PhiLho

Re: More Efficient Way to Find Nearest Black Pixel?

9 months ago

amnon.owed, when I saw your suggestion, I thought that the logic of scanning around the origin point might be more CPU intensive (lot of simple arithmetic and conditions) than a brute force scan. You confirm this idea...

An alternative might be to scan (linearly) a square of some arbitrary size around the origin. If not found, scan in a bigger area, avoiding the previously scanned area (simple condition should be fast enough). By using large increments in area size, it can reduce a bit the overhead, perhaps.

GoToLoop

Re: More Efficient Way to Find Nearest Black Pixel?

9 months ago

I wonder if this tweaked loop can be a bit tad faster?

int count = 0;
for (int i = 0, canvas = width*height; i != canvas;)
if (pixels[i++] == 0) ++count;

jdmaguire

Re: More Efficient Way to Find Nearest Black Pixel?

9 months ago

There's a relatively fast way to determine the nearest black pixel to every pixel but a single pixel's distance to a black is hard.

Assuming you do want to do this more than once but not for every pixel and you don't mind some crazyness:

Pre-compute a bucket list of the black pixels, the pixels being put in buckets by their x index with a secondary y-indexing.

Pre-computer a another bucket list of the black pixels, the pixels being put in buckets by their y index with a secondary x-indexing.

Checking the rings as ammon.owed suggested is sped up drastically. Each ring would take constant time (i.e. the small rings taking as long as the large rings).

edit:The bucket lists could of type TreeMap<Integer,TreeSet<Integer>>

fasteddy86

Re: More Efficient Way to Find Nearest Black Pixel?

9 months ago

Wow, this really generated some discussion. Thanks for the tip about distance calculation and get vs pixels. My issue is that I need to calculate this relatively often on an image where the colours are changing, so precomputing probably would not work here.

I'll try the tweaked loop, GoToLoop, thanks for that.

As background:

My project is an arduino-controlled etch-a-sketch. I know, it's not exactly original, but I've been looking for a fun first project with my arduino, and this is what I've settled on. Starting with a 1-bit image, I have a (poorly-written) program that checks the surrounding 8 pixels in sequence for a neighbouring black pixel. If it finds one, it changes the colour of the current pixel to green (not important, just non-black and non-white to differentiate used pixels) then moves on and repeats. When it runs out of neighbouring black pixels, it finds the nearest one (see above), then uses Quark's excellent PathFinder library to draw the shortest path (in black, on top of any existing black/green pixels) to this new pixel. Loop. What I really love about Quark's library is that he's made it easy to assign different costs to different pixel values, ensuring that the program never uses white pixels unless no other options are available.

Each movement to a new pixel also sends a serial communication to the arduino which the arduino interprets into movement of the stepper motors for the 8 possible directions ("A" up, "B" down, etc.).

Because it's an Etch-a-Sketch, I prefer to go back over existing lines than to create new ones, no matter how close the pixel, in an effort to eliminate unwanted lines. I know others have done this using TSP (Travelling Salesman Problem) art as a starting point, but it's generally computationally expensive and done iteratively, requiring intervention to decide when it's good enough, or lots of time to complete. Also, while TSP art can look pretty cool, I'm more interested reproducing simple 1-bit portraits that are nevertheless recognizable. Additionally, this allows a certain degree of automation that I can't achieve with TSP.

Interestingly, the pixel search takes as much time as the shortest path solution to calculate. Hopefully these suggestions will help on this front. Though to be honest, I'm limited by the speed of the steppers anyway, so it's not so much a problem.

Edit: early results below. This took about 15 minutes on my ageing (about 5-yrs old) pc.

It still requires some optimizing/tweaking (also, we'll see how it comes out in real life on the EAS), but one thing's for certain - even in 1-bit I'm a good lookin' guy!

jdmaguire

Re: More Efficient Way to Find Nearest Black Pixel?

9 months ago

I may not understand everything. Discard this suggestion if I am missing something. You could pre-find all the black pixels and when changing a pixel from black to non-black just remove that pixel?

Top Reply