Visual Servoing Platform  version 3.5.1 under development (2022-10-03)
Tutorial: Flood fill algorithm

Introduction

This tutorial will show you how to use the flood fill algorithm to fill connected areas in an image. This method is used for instance in raster graphics editor to perform the "bucket" fill tool.

The principle for a 2D image is the following:

  • in input: a seed point, the pixel value to be replaced that forms the connected area, the pixel value to replace
  • starting from a seed point
  • explore the neighborhood looking for same pixel values
  • replace the old pixel value by the desired one

To explore the neighborhood, a 4-connexity or 8-connexity search are possible:

4-connexity
8-connexity

Example code

The following example also available in tutorial-flood-fill.cpp will mimic the "bucket" fill tool:

#include <cstdlib>
#include <iostream>
#include <visp3/core/vpImage.h>
#include <visp3/gui/vpDisplayGDI.h>
#include <visp3/gui/vpDisplayOpenCV.h>
#include <visp3/gui/vpDisplayX.h>
#if defined(VISP_HAVE_MODULE_IMGPROC) && (defined(VISP_HAVE_X11) || defined(VISP_HAVE_GDI) || defined(VISP_HAVE_OPENCV))
#include <visp3/imgproc/vpImgproc.h>
namespace
{
vpImagePoint switchToOctantZeroFrom(const int octant, const vpImagePoint &imPt)
{
vpImagePoint imPt_switched = imPt;
switch (octant) {
case 0: // return (x, y)
imPt_switched.set_uv(imPt.get_u(), imPt.get_v());
break;
case 1: // return (y, x)
imPt_switched.set_uv(imPt.get_v(), imPt.get_u());
break;
case 2: // return (y, -x)
imPt_switched.set_uv(imPt.get_v(), -imPt.get_u());
break;
case 3: // return (-x, y)
imPt_switched.set_uv(-imPt.get_u(), imPt.get_v());
break;
case 4: // return (-x, -y)
imPt_switched.set_uv(-imPt.get_u(), -imPt.get_v());
break;
case 5: // return (-y, -x)
imPt_switched.set_uv(-imPt.get_v(), -imPt.get_u());
break;
case 6: // return (-y, x)
imPt_switched.set_uv(-imPt.get_v(), imPt.get_u());
break;
case 7: // return (x, -y)
imPt_switched.set_uv(imPt.get_u(), -imPt.get_v());
break;
default:
break;
}
return imPt_switched;
}
vpImagePoint switchFromOctantZeroTo(const int octant, const vpImagePoint &imPt)
{
vpImagePoint imPt_switched = imPt;
switch (octant) {
case 0: // return (x, y)
imPt_switched.set_uv(imPt.get_u(), imPt.get_v());
break;
case 1: // return (y, x)
imPt_switched.set_uv(imPt.get_v(), imPt.get_u());
break;
case 2: // return (-y, x)
imPt_switched.set_uv(-imPt.get_v(), imPt.get_u());
break;
case 3: // return (-x, y)
imPt_switched.set_uv(-imPt.get_u(), imPt.get_v());
break;
case 4: // return (-x, -y)
imPt_switched.set_uv(-imPt.get_u(), -imPt.get_v());
break;
case 5: // return (-y, -x)
imPt_switched.set_uv(-imPt.get_v(), -imPt.get_u());
break;
case 6: // return (y, -x)
imPt_switched.set_uv(imPt.get_v(), -imPt.get_u());
break;
case 7: // return (x, -y)
imPt_switched.set_uv(imPt.get_u(), -imPt.get_v());
break;
default:
break;
}
return imPt_switched;
}
int getOctant(const vpImagePoint &imPt1, const vpImagePoint &imPt2)
{
double dx = imPt2.get_u() - imPt1.get_u();
double dy = imPt2.get_v() - imPt1.get_v();
if (dx >= 0 && dy >= 0) {
if (dy >= dx) {
return 1;
} else {
return 0;
}
} else if (dx < 0 && dy >= 0) {
if (-dx >= dy) {
return 3;
} else {
return 2;
}
} else if (dx < 0 && dy < 0) {
if (dy <= dx) {
return 5;
} else {
return 4;
}
} else {
if (dx >= -dy) {
return 7;
} else {
return 6;
}
}
}
void drawLine(vpImage<unsigned char> &I, const unsigned char value, const vpImagePoint &imPt1_,
const vpImagePoint &imPt2_)
{
vpImagePoint imPt1((int)imPt1_.get_v(), (int)imPt1_.get_u());
vpImagePoint imPt2((int)imPt2_.get_v(), (int)imPt2_.get_u());
int octant = getOctant(imPt1, imPt2);
imPt1 = switchToOctantZeroFrom(octant, imPt1);
imPt2 = switchToOctantZeroFrom(octant, imPt2);
double dx = imPt2.get_u() - imPt1.get_u();
double dy = imPt2.get_v() - imPt1.get_v();
double D = 2 * dy - dx;
double y = imPt1.get_v();
for (int x = (int)imPt1.get_u(); x <= (int)imPt2.get_u(); x++) {
vpImagePoint currentPt(y, x);
currentPt = switchFromOctantZeroTo(octant, currentPt);
unsigned int i = std::min(I.getHeight() - 1, (unsigned int)std::max(0.0, currentPt.get_i()));
unsigned int j = std::min(I.getWidth() - 1, (unsigned int)std::max(0.0, currentPt.get_j()));
I[i][j] = value;
if (D >= 0) {
y++;
D -= dx;
}
D += dy;
}
}
} // namespace
#endif
int main()
{
#if defined(VISP_HAVE_MODULE_IMGPROC) && (defined(VISP_HAVE_X11) || defined(VISP_HAVE_GDI) || defined(VISP_HAVE_OPENCV))
vpImage<vpRGBa> I(480, 640, vpRGBa());
#ifdef VISP_HAVE_X11
#elif defined(VISP_HAVE_GDI)
#elif defined(VISP_HAVE_OPENCV)
#endif
d.init(I, 0, 0, "Paint");
std::vector<vpPolygon> polygons;
for (int i = 0; i < 3; i++) {
std::stringstream ss;
ss << "Left click to draw polygon " << i + 1 << "/3"
<< ", right click to close the shape.";
vpDisplay::displayText(I, 20, 20, ss.str(), vpColor::red);
vpPolygon polygon;
polygon.initClick(I);
polygons.push_back(polygon);
// Update the lines draw internally in the current image
}
for (size_t i = 0; i < polygons.size(); i++) {
if (polygons[i].getCorners().size() <= 1)
continue;
for (size_t j = 0; j < polygons[i].getCorners().size() - 1; j++)
drawLine(mask, 255, polygons[i].getCorners()[j], polygons[i].getCorners()[j + 1]);
drawLine(mask, 255, polygons[i].getCorners().front(), polygons[i].getCorners().back());
}
bool quit = false;
while (!quit) {
"Left click on a pixel location to fill the "
"shape, right click to quit.",
if (vpDisplay::getClick(I, ip, button, false))
{
switch (button) {
for (unsigned int cpt = 0; cpt < mask.getSize(); cpt++) {
if (mask.bitmap[cpt])
I.bitmap[cpt] = vpColor::red;
}
break;
quit = true;
break;
default:
break;
}
}
}
#endif
return EXIT_SUCCESS;
}
static const vpColor red
Definition: vpColor.h:217
Display for windows using GDI (available on any windows 32 platform).
Definition: vpDisplayGDI.h:129
The vpDisplayOpenCV allows to display image using the OpenCV library. Thus to enable this class OpenC...
Use the X11 console to display images on unix-like OS. Thus to enable this class X11 should be instal...
Definition: vpDisplayX.h:135
void init(vpImage< unsigned char > &I, int win_x=-1, int win_y=-1, const std::string &win_title="")
static bool getClick(const vpImage< unsigned char > &I, bool blocking=true)
static void display(const vpImage< unsigned char > &I)
static void displayLine(const vpImage< unsigned char > &I, const vpImagePoint &ip1, const vpImagePoint &ip2, const vpColor &color, unsigned int thickness=1, bool segment=true)
static void getImage(const vpImage< unsigned char > &Is, vpImage< vpRGBa > &Id)
Definition: vpDisplay.cpp:144
static void flush(const vpImage< unsigned char > &I)
static void displayText(const vpImage< unsigned char > &I, const vpImagePoint &ip, const std::string &s, const vpColor &color)
Class that defines a 2D point in an image. This class is useful for image processing and stores only ...
Definition: vpImagePoint.h:89
double get_u() const
Definition: vpImagePoint.h:143
void set_uv(double u, double v)
Definition: vpImagePoint.h:357
double get_v() const
Definition: vpImagePoint.h:154
unsigned int getWidth() const
Definition: vpImage.h:246
Type * bitmap
points toward the bitmap
Definition: vpImage.h:143
unsigned int getHeight() const
Definition: vpImage.h:188
Defines a generic 2D polygon.
Definition: vpPolygon.h:106
const std::vector< vpImagePoint > & getCorners() const
Definition: vpPolygon.h:156
void initClick(const vpImage< unsigned char > &I, unsigned int size=5, const vpColor &color=vpColor::red, unsigned int thickness=1)
Definition: vpPolygon.cpp:265
Definition: vpRGBa.h:67
VISP_EXPORT void floodFill(vpImage< unsigned char > &I, const vpImagePoint &seedPoint, const unsigned char oldValue, const unsigned char newValue, const vpImageMorphology::vpConnexityType &connexity=vpImageMorphology::CONNEXITY_4)
Definition: vpFloodFill.cpp:85

What the tutorial code does from the user side is:

  • let the user draw 3 polygons on a raster (bitmap) image
  • do the "bucket" fill tool when the user clicks on a pixel location

The flood fill function is provided in a vp:: namespace and accessible using this include:

#include <visp3/imgproc/vpImgproc.h>

The first thing to do is to create a raster image of 640x480 size:

vpImage<vpRGBa> I(480, 640, vpRGBa());

These lines of code allows the user to click in the image to draw a polygon shape:

std::vector<vpPolygon> polygons;
for (int i = 0; i < 3; i++) {
std::stringstream ss;
ss << "Left click to draw polygon " << i + 1 << "/3"
<< ", right click to close the shape.";
vpDisplay::displayText(I, 20, 20, ss.str(), vpColor::red);
vpPolygon polygon;
polygon.initClick(I);
polygons.push_back(polygon);
// Update the lines draw internally in the current image
}

Now, we need to draw these polygons on a grayscale image (the current flood fill implementation needs a grayscale image) as the ViSP display is done on an internal image. This will be used as a mask: 255 pixel values are used for locations where we need to paint in the raster image.

For this, we can use the Bresenham's line algorithm to actually draw a line from a starting and ending point. The direct C++ implementation of the Bresenham's line algorithm is the following:

vpImagePoint switchToOctantZeroFrom(const int octant, const vpImagePoint &imPt)
{
vpImagePoint imPt_switched = imPt;
switch (octant) {
case 0: // return (x, y)
imPt_switched.set_uv(imPt.get_u(), imPt.get_v());
break;
case 1: // return (y, x)
imPt_switched.set_uv(imPt.get_v(), imPt.get_u());
break;
case 2: // return (y, -x)
imPt_switched.set_uv(imPt.get_v(), -imPt.get_u());
break;
case 3: // return (-x, y)
imPt_switched.set_uv(-imPt.get_u(), imPt.get_v());
break;
case 4: // return (-x, -y)
imPt_switched.set_uv(-imPt.get_u(), -imPt.get_v());
break;
case 5: // return (-y, -x)
imPt_switched.set_uv(-imPt.get_v(), -imPt.get_u());
break;
case 6: // return (-y, x)
imPt_switched.set_uv(-imPt.get_v(), imPt.get_u());
break;
case 7: // return (x, -y)
imPt_switched.set_uv(imPt.get_u(), -imPt.get_v());
break;
default:
break;
}
return imPt_switched;
}
vpImagePoint switchFromOctantZeroTo(const int octant, const vpImagePoint &imPt)
{
vpImagePoint imPt_switched = imPt;
switch (octant) {
case 0: // return (x, y)
imPt_switched.set_uv(imPt.get_u(), imPt.get_v());
break;
case 1: // return (y, x)
imPt_switched.set_uv(imPt.get_v(), imPt.get_u());
break;
case 2: // return (-y, x)
imPt_switched.set_uv(-imPt.get_v(), imPt.get_u());
break;
case 3: // return (-x, y)
imPt_switched.set_uv(-imPt.get_u(), imPt.get_v());
break;
case 4: // return (-x, -y)
imPt_switched.set_uv(-imPt.get_u(), -imPt.get_v());
break;
case 5: // return (-y, -x)
imPt_switched.set_uv(-imPt.get_v(), -imPt.get_u());
break;
case 6: // return (y, -x)
imPt_switched.set_uv(imPt.get_v(), -imPt.get_u());
break;
case 7: // return (x, -y)
imPt_switched.set_uv(imPt.get_u(), -imPt.get_v());
break;
default:
break;
}
return imPt_switched;
}
int getOctant(const vpImagePoint &imPt1, const vpImagePoint &imPt2)
{
double dx = imPt2.get_u() - imPt1.get_u();
double dy = imPt2.get_v() - imPt1.get_v();
if (dx >= 0 && dy >= 0) {
if (dy >= dx) {
return 1;
} else {
return 0;
}
} else if (dx < 0 && dy >= 0) {
if (-dx >= dy) {
return 3;
} else {
return 2;
}
} else if (dx < 0 && dy < 0) {
if (dy <= dx) {
return 5;
} else {
return 4;
}
} else {
if (dx >= -dy) {
return 7;
} else {
return 6;
}
}
}
void drawLine(vpImage<unsigned char> &I, const unsigned char value, const vpImagePoint &imPt1_,
const vpImagePoint &imPt2_)
{
vpImagePoint imPt1((int)imPt1_.get_v(), (int)imPt1_.get_u());
vpImagePoint imPt2((int)imPt2_.get_v(), (int)imPt2_.get_u());
int octant = getOctant(imPt1, imPt2);
imPt1 = switchToOctantZeroFrom(octant, imPt1);
imPt2 = switchToOctantZeroFrom(octant, imPt2);
double dx = imPt2.get_u() - imPt1.get_u();
double dy = imPt2.get_v() - imPt1.get_v();
double D = 2 * dy - dx;
double y = imPt1.get_v();
for (int x = (int)imPt1.get_u(); x <= (int)imPt2.get_u(); x++) {
vpImagePoint currentPt(y, x);
currentPt = switchFromOctantZeroTo(octant, currentPt);
unsigned int i = std::min(I.getHeight() - 1, (unsigned int)std::max(0.0, currentPt.get_i()));
unsigned int j = std::min(I.getWidth() - 1, (unsigned int)std::max(0.0, currentPt.get_j()));
I[i][j] = value;
if (D >= 0) {
y++;
D -= dx;
}
D += dy;
}
}

Draw the polygon lines on a grayscale image is then simple:

for (size_t i = 0; i < polygons.size(); i++) {
if (polygons[i].getCorners().size() <= 1)
continue;
for (size_t j = 0; j < polygons[i].getCorners().size() - 1; j++)
drawLine(mask, 255, polygons[i].getCorners()[j], polygons[i].getCorners()[j + 1]);
drawLine(mask, 255, polygons[i].getCorners().front(), polygons[i].getCorners().back());
}

Now we need to be able to get the 2D image location when the user click on the image to select the seed point:

if (vpDisplay::getClick(I, ip, button, false))

The flood fill is performed using the desired seed point and by replacing 0 pixel values by 255 values in the mask image. A 4-connexity is used as the 8-connexity will overflow due to the thin line drawing.

The final step is to update the raster image:

for (unsigned int cpt = 0; cpt < mask.getSize(); cpt++) {
if (mask.bitmap[cpt])
I.bitmap[cpt] = vpColor::red;
}

Here are some steps illustrated with images:

Polygons drawn by the user
Raster image after bucket fill

Next tutorial

You can now read the Practical example: count the number of coins in an image, for a final tutorial that will illustrate some of the image processing techniques presented in these tutorials on a specific use case: how to count the number of coins in an image.