Efficient way to find position of beacon image in a screenshot

Question

I have a screenshot taken from java.awt.Robot as a java.awt.image.BufferedImage and know there will be a unique 10x10 solid red (same RGB) coloured square somewhere in that screenshot (more likely closer to the middle).

What's an efficient approach to finding its coordinates? Is JavaCV even the right library to use? I found a brute force approach in .net here: Bitmap Detection but I'm wondering if there's a better way.

Answer 1

The first question is, what does it take to recognize the color - is it an exact RGB value, where either the color is an exact match, or it isn't? And will that still be the case if the image is lossy-compressed, for example as a JPEG?

Assuming you can do that, probably you want to do a search that tries to minimize time spent searching areas which won't be fruitful: On an imaginary line between two opposite corners, test the value at each corner and the midpoint; if no match, try at the midpoint between the midpoints and the corners; if no match, divide the space in half vertically or horizontally and try again; once you find a pixel of the right color, have some code that walks the pixels in each direction to determine if it's really 10x10.

Really any sort of search pattern will work; what you probably don't want is a situation where you just start at 0,0 and go 0,1 0,2 ... 1,0 1,2 since that will make matching in the upper left fast and bottom right slow (assuming a coordinate space that starts at the top left).