Flood Fill

Flood fill [Heckbert00; Shaw04; Vandevenne04] is an extremely useful function that is often used to mark or isolate portions of an image for further processing or analysis. Flood fill can also be used to derive, from an input image, masks that can be used for subsequent routines to speed or restrict processing to only those pixels indicated by the mask. The function cvFloodFill() itself takes an optional mask that can be further used to control where filling is done (e.g., when doing multiple fills of the same image).

In OpenCV, flood fill is a more general version of the sort of fill functionality which you probably already associate with typical computer painting programs. For both, a seed point is selected from an image and then all similar neighboring points are colored with a uniform color. The difference here is that the neighboring pixels need not all be identical in color.^[55] The result of a flood fill operation will always be a single contiguous region. The cvFloodFill() function will color a neighboring pixel if it is within a specified range (lo Diff to up Diff) of either the current pixel or if (depending on the settings of flags) the neighboring pixel is within a specified range of the original seedPoint value. Flood filling can also be constrained by an optional mask argument. The prototype for the flood fill routine is:

Figure 5-15. Results of the morphological gradient operator: bright perimeter edges are identified

void cvFloodFill(
   IplImage*         img,
   CvPoint           seedPoint,
   CvScalar          newVal,
   CvScalar          lo Diff    = cvScalarAll(0),
   CvScalar          up Diff    = cvScalarAll(0),
   CvConnectedComp*  comp      = NULL,
   int               flags     = 4,
   CvArr*            mask      = NULL
);

The parameter img is the input image, which can be 8-bit or floating-point and one-channel or three-channel. We start the flood filling from seedPoint, and newVal is the value to which colorized pixels are set. A pixel will be colorized if its intensity is not less than a colorized neighbor's intensity minus lo Diff and not greater than the colorized neighbor's intensity plus up Diff. If the flags argument includes CV_FLOODFILL_FIXED_RANGE, then a pixel will be compared to the original seed point rather than to its neighbors. If non-NULL, comp is a CvConnectedComp structure that will hold statistics about the areas filled.^[56] The flags argument (to be discussed shortly) is a little tricky; it controls the connectivity of the fill, what the fill is relative to, whether we are filling only a mask, and what values are used to fill the mask. Our first example of flood fill is shown in Figure 5-19.

Figure 5-16. Results of morphological Top Hat operation: bright local peaks are isolated

The argument mask indicates a mask that can function both as input to cvFloodFill() (in which case it constrains the regions that can be filled) and as output from cvFloodFill() (in which case it will indicate the regions that actually were filled). If set to a non-NULL value, then mask must be a one-channel, 8-bit image whose size is exactly two pixels larger in width and height than the source image (this is to make processing easier and faster for the internal algorithm). Pixel (x + 1, y + 1) in the mask image corresponds to image pixel (x, y) in the source image. Note that cvFloodFill() will not flood across nonzero pixels in the mask, so you should be careful to zero it before use if you don't want masking to block the flooding operation. Flood fill can be set to colorize either the source image img or the mask image mask.

Figure 5-17. Results of morphological Black Hat operation: dark holes are isolated

Figure 5-18. Summary results for all morphology operators

Figure 5-19. Results of flood fill (top image is filled with gray, bottom image with white) from the dark circle located just off center in both images; in this case, the up diff and lo diff parameters were each set to 7.0

Tip

If the flood-fill mask is passed by the user, then the mask pixels, corresponding to the repainted image pixels, are set to the value encoded in the middle bits (8-15) of the flags value (see text).. If these bits are not set then the mask is set to 1 as the default value. Don't be confused if you fill the mask and see nothing but black upon display; the filled values (if the middle bits of the flag weren't set) are 1s, so the mask image needs to be rescaled if you want to display it visually.

It's time to clarify the flags argument, which is tricky because it has three parts. The low 8 bits (0–7) can be set to 4 or 8. This controls the connectivity considered by the filling algorithm. If set to 4, only horizontal and vertical neighbors to the current pixel are considered in the filling process; if set to 8, flood fill will additionally include diagonal neighbors. The high 8 bits (16–23) can be set with the flags CV_FLOODFILL_FIXED_RANGE (fill relative to the seed point pixel value; otherwise, fill relative to the neighbor's value), and/or CV_FLOODFILL_MASK_ONLY (fill the mask location instead of the source image location). Obviously, you must supply an appropriate mask if CV_FLOODFILL_MASK_ONLY is set. The middle bits (8–15) of flags can be set to the value with which you want the mask to be filled. If the middle bits of flags are 0s, the mask will be filled with 1s. All these flags may be linked together via OR. For example, if you want an 8-way connectivity fill, filling only a fixed range, filling the mask not the image, and filling using a value of 47, then the parameter to pass in would be:

flags = 8
      | CV_FLOODFILL_MASK_ONLY
      | CV_FLOODFILL_FIXED_RANGE
      | (47<<8);

Figure 5-20 shows flood fill in action on a sample image. Using CV_FLOODFILL_FIXED_RANGE with a wide range resulted in most of the image being filled (starting at the center). We should note that newVal, lo diff, and up diff are prototyped as type CvScalar so they can be set for three channels at once (i.e., to encompass the RGB colors specified via CV_RGB()). For example, lowDiff = CV_RGB(20,30,40) will set lowDiff thresholds of 20 for red, 30 for green, and 40 for blue.

Figure 5-20. Results of flood fill (top image is filled with gray, bottom image with white) from the dark circle located just off center in both images; in this case, flood fill was done with a fixed range and with a high and low difference of 25.0

---

^[55] Users of contemporary painting and drawing programs should note that most now employ a filling algorithm very much like cvFloodFill().

^[56] We will address the specifics of a "connected component" in the section "Image Pyramids". For now, just think of it as being similar to a mask that identifies some subsection of an image.