Fast way to get the bounding rectangle of a flood fill

I need to perform a flood fill on a region of an image. However I do not actually need the resulting image, I only need to know the smallest rectangle containing all pixels that would be changed by the flood fill.

Is there a variant of a flood fill algorithm that can compute this rectangle more cheaply than doing a full flood fill?

Example input and output (only the red rectangle is required):

Sample input image. The red dot is the start pixel. The area to be filled is the cyan Z-tetromino that contains the dot http://开发者_开发问答www.finnw.me.uk/ffinput.pngSample output. Only the position/width/height of the red rectangle is significant http://www.finnw.me.uk/ffoutput.png

Edit: Example #2 with islands:

Example input with islands http://www.finnw.me.uk/ffinput2.png Example output http://www.finnw.me.uk/ffoutput2.png

Example #3:

Example of false island http://www.finnw.me.uk/ffinput3.png

Edit

Sorry, images were lost in a hard disk failure. When I first posted this, SO did not host images so I kept them on my own server.

Basically you need to determine biggestX, biggestY, smallestX, and smallestY.

Find the bottom right corner of the real edge:

You can do this by going as far right+down as possible inside your color.

When you can't go right+down anymore, then you need to check to make sure you aren't stuck in a corner of an island. To check for this you need to follow around the entire edge looking for a chance to go more right+down. You can keep track of (biggestX, biggestY, smallestX, smallestY) every time this happens in case you actually have your real edge.

If you actually do have an island, you will eventually find a place following the edge that you can go more right+down.

If you don't have a chance to go more right+down, and you reach your starting point, then you have your actual edge. And you have calculated your (biggestX, biggestY, smallestX, and smallestY).

One possible method would be to go as far (left,up,down.right) as you can from your starting point, then follow the edge clock-wise or counter-clockwise until you return to your first edge-point. Keep track of min(X,y) and max(X,Y) as you traverse the edge.

That ought to let you look at fewer pixels, unless you have rather odd shapes to fill.