Visual Servoing Platform  version 3.2.0 under development (2018-08-20)
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:

img-tutorial-flood-fill-4-connexity.png
4-connexity
img-tutorial-flood-fill-8-connexity.png
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;
}

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:

img-tutorial-flood-fill-draw-polygons.png
Polygons drawn by the user
img-tutorial-flood-fill-bucket-fill.png
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.