Finding color locations with RMagick

Question

I have an image with lots of non-overlapping colored rectangles. Each rectangle is a unique color, and I know the colors ahead of time. (Weird situation, I know.) I'm trying to find the pixel locations and sizes of each rectangle, and I need this to be as fast as possible. Are there any interesting tricks I can do with RMagick or a similar library to make this easier than iterating through every single pixel?

My current plan is something along the lines of:

for each pixel (moving left-to-right, top-to-bottom):
  if pixel color's in our list and we haven't seen it yet:
    save pixel location as starting location for that color
  else if pixel color's in our list and we've already seen it:
    save pixel location as ending location for that color

(Yes, we can optimize and skip certain regions of pixels if we know they're in a rectangle.) At the end of the loop, we should have the first and last pixels of each rectangle, which we can use to deduce the rectangle dimensions. But this seems somewhat ugly to me.

Can I do better?

Answer 1

This answer works only if there is a minimum rectangle size, ideally at least 3x3, such that the extra complexity pays off.

Assuming the minimum rectangle size is (m, n), run your suggested algorithm with that step size to get approximate start and end points, then refine those approximations by checking pixel-by-pixel (in two L-shaped paths) for where the two opposing corners are. You can show that this will always check a smaller number of pixels than scanning the whole image.

for each pixel (moving left-to-right step m, top-to-bottom step n):
  if pixel color's in our list and we haven't seen it yet:
    save pixel location as rough starting location (xs,ys) for that color
    save pixel location as rough ending location (xe,ye) for that color
  else if pixel color's in our list and we've already seen it:
    save pixel location as rough ending location (xe,ye) for that color

Then refine locations

for each color
  with starting location (xs , ys)
    while color at (xs, ys - 1) is same, update ys = ys - 1
    while color at (xs - 1, ys) is same, update xs = xs - 1
  with ending location (xe , ye)
    while color at (xe, ye + 1) is same, update ye = ye + 1
    while color at (xe + 1, ye) is same, update xe = xe + 1

If the minimum size is 3x3, there are 20 rectangles to find, and the image is 100x100:

• A full scan would read 10000 pixels
• An optimised scan would read 33x33 pixels, then refine each of 20 rectangles by reading 20x10 more (average). Total 1289 pixels.