Finding the interior of a connected graph

I'm designing software that produces images such as the following:

Regions of interest are circumscribed by red pixels. I am interested in extracting the fully-enclosed pixel regions. Ultimately, I would like to calculate the approximate center, width, and height of the regions. Ideally, I would even like to eliminate interior loops--that is, only preserve the largest enclosing body of a region (a "region" being an isolated pixel group).

I have experience implementing search algorithms, so my first instinct is to traverse the edges until a loop is detected (arrival at the start); however, I recognize the potential for multiple solutions--alternate, valid loop possibilities--and then I would require a way to decide between them. Perhaps the one that is longer or encloses the greatest number of pixels.

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.

StackExchange Computer Science Q#40966, answer score: 3