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

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.

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 :)