Finding the interior of a connected graph
If you are given the red pixels, try decomposing the pixels into strongly connected components (SCC), where two pixels are in the same SCC if they are adjacent and neither one is red.  Then each SCC represents a region.  This is a standard technique in computer vision.  Another way to think about this: try using flood fill from each possible starting point.

If you're not given the red pixels: you have a blob finding / segmentation kind of problem.  Try looking at existing methods for block detection.  You should also look at the watershed algorithm for image segmentation.  There are also methods based upon max flow (i.e., minimum graph cuts).

Doing some searches using these keywords will probably find you many more resources.