PHP - Really fast way to detect whitespace around an image?

Question

I need a really quick method of detecting a space around the image, in particular I need the coordinates where the first non-white pixel starts for each side (for example, left, top, right, bottom.)

ImageMagick is too slow, so each pixel on each side intersects the GD and sees if it is white. I need to take about 500 million images, so every microsecond matters.

By the way, the image is only black and white.

If there is an external application that can do this, and I can exec with PHP, then this will be fine.

Answer 1

is there any additional information that you know about images that can be used for help?

How do images start white and then black and then black? or can any pixel be white or black, and the fact that any of them is white or black does not say anything about the others?

If any pixel can be white or black regardless of other pixels, then I don’t see how you can do much better than checking each pixel in a loop until you find the first one not white ...

If you know that if the fifth pixel on the left is white, then 0-4 is definitely white, and then you can check for fewer pixels instead using some kind of modified binary type (as you could skip checking 0-4 in in this case and just say 5, then 10, and if 5 is white and 10 is black, you know that the point is somewhere between 5-10, so you can divide the difference and check 7, etc., Until find the point at which they change.)

I think you can get a compromise between speed and accuracy here. The most accurate way is to cut each column and row, starting at the end, checking each pixel. Once you find the hit in the column, you find the edge on one side. This can be done in parallel, since each check is independent. you may be able to speed it up, as you said, by checking only every nth pixel, but this will most likely happen with cropping, especially with such a large dataset. it may or may not be acceptable. you can improve this by checking around the area in which you find a match to verify that the match is correct. Therefore, if you check every third pixel and find hit in pixel 15, then check 14 to see if this is a hit (and 13 if 14). using this, you can get away with fewer checks.

Answer 2

One algorithm that can work if you have a mostly continuous border of dark pixels: Left side:

• Take the middle pixel and start checking the pixels on the right until you find black.
• Then move up / down from there until you click on the black pixel.
• When you find that the black pixel moves to the left until you hit white
• Repeat 2.3 until you return up / down

This, of course, will not work if there are spaces, as in the text.