Are there algorithms for computing the bounding rects of sprites drawn on a monochrome background?

Question

Imagine a plain rectangular bitmap of, say, 1024x768 pixels filled with white. There are a few (non-overlapping) sprites drawn onto the bitmap: circles, squares and triangles.

Is there an algorithm (possibly even a C++ implementation) which, given the bitmap and the color which is the background color (white, in the above example), yields a list containing the smallest bounding rectangles for each of the sprites?

Here's some sample: On the left side you can see a sample bitmap which my code is given (together with the information that the 'background' is white). On the right side you can see the same image together with the bounding rectangles of the four shapes (in red); the algorithm I'm looking for computes the geometry of these rectangles.

Some painting programs have a similiar feature for selecting shapes: they can even compute seemingly arbitrary bounding polygons. Instead of dragging a selection rectangle manually, you can click the 'background' (what's background and what's not is determined by some threshold) and then the tool automatically computes the shape of the object drawn onto the background. I need something like this, except that I'm perfectly fine if I just have the rectangular bounding areas for objects.

I became aware of OpenCV; it appears to be relevant (it seems to be a library which includes every graphics algorithm I can think of - and then some) but in the fast amount of information I couldn't find the way to the algorithm I'm thinking of. I would be surprised if OpenCV couldn't do this, but I fear you've got to have a PhD to use it. :-)

Answer 1

Here is the great article on the subject:

http://softsurfer.com/Archive/algorithm_0107/algorithm_0107.htm

I think that PhD is not required here :)

Answer 2

These are my first thoughts, none complicated, except for the edge detection

For each square, 
   if it's not-white
       mark as "found"
       if you havn't found one next to it already
           add it to points list
for each point in the points list
    use basic edge detection to find outline
    keep track of bounds while doing so
    add bounds to shapes list
remove duplicates from shapes list. (this can happen for concave shapes)

I just realized this will consider white "holes" (like in your leftmost circle in your sample) to be it's own shape. If the first "loop" is a flood fill, it doesn't have this problem, but will be much slower/take much more memory.

The basic edge detection I was thinking of was simple:

given eight cardinal directions left, downleft, etc...
given two relative directions cw(direction-1) and ccw(direction+1)
starting with a point "begin"
set bounds to point
find direction d, where the begin+d is not white, and begin+cw(d) is white.
set current to begin+d
do 
    if current is outside of bounds, increase bounds
    set d = cw(d)
    while(cur+d is white or cur+ccw(d) is not white)
        d = ccw(d)
    cur = cur + d;
while(cur != begin

http://ideone.com/

There's a quite a few edge cases not considered here: what if begin is a single point, what if it runs to the edge of the picture, what if start point is only 1 px wide, but has blobs to two sides, probably others... But the basic algorithm isn't that complicated.