What is the Flood fill algorithm?
This method starts with a seed (first pixel) within the boundary like the Boundary fill algorithm. It determines whether the pixel has the region's original color. If the answer is positive, the pixel is filled with a specific color, and each of the pixel's neighbors is used as a new seed in a recursive call. If the answer is negative, the call is returned to the caller.
The similarity between Flood fill and Boundary fill algorithm
- The operational idea of this method is very similar.
- 4-connected and 8-connected procedure applications are the same for the algorithm.
- Only one loop is used in these two algorithms.
Advantages of Flood fill algorithm
- It's extremely helpful when the area to be filled doesn't have a uniformly colored boundary.
- There is no use for loop operation when implementing this method. So, it reduces time complexity than others.
- One condition is checked for coloring in the region. So, it is faster than the Boundary fill algorithm.
Flood fill algorithm
Step 1: Begin the algorithm.
Step 2:
For 4-connected procedure: (Right, left, up, down)
Set four integer variables of a point to fill the boundary of a region in a four-connected way.
For 8-connected procedure: (Right, left, up, down, and four corners)
Set four integer variables of a point considering the corners points with the reduction and addition of a unit in the x-axis and y-axis to fill the boundary of a region in an eight-connected way.
Step 3: Initialize the variables ( point position of the x-axis, point position of the y-axis, fill color, and original color).
N.B.: Color fillings are the user's choice
Step 4: Get pixels of x and y position with the parameter 'color' from a particular frame.
Step 5:
START of an 'if' loop
Now, check only one condition
Is color equal to the fill color
If the condition output position then, the next step is 6
or
else
Check new conditions from the main function sending value
END of the 'if' loop
Step 6: Recall the same function and begin to set pixels in a frame, based on the x and y position in a four or eight-connected way.
END of the if loop.
Step 7: End of the algorithm.
Pseudo-code for Flood fill algorithm in C language:
FloodFillRecursion (int a, b, FillColor, OriginalColor)
{
int color;
getPixel(a, b, color);
if (color == OriginalColor)
{
setPixel(a, b, fill_color);
FloodFillRecursion (a + 1, b, FillColor, OriginalColor);
FloodFillRecursion (a, b + 1, FillColor, OriginalColor);
FloodFillRecursion (a - 1, b, FillColor, OriginalColor);
FloodFillRecursion (a, b - 1, FillColor, OriginalColor);
}
}
Note Book for using new functions in C or C++ language: getPixel() and setPixel() are the built-in functions of graphics.h header file.
Flood fill algorithm example
Using the 8-connected process for region pixels, how will you apply the flood fill algorithm to fill the region depicted in Fig. 1? Given that, the seed position (x, y) = (3, 3).
Fig. 2: 3 by 3 position points and surrounding points
Each of the eight points discovered in step 1 is transformed into a new seed, and the points surrounding each new seed are checked and filled. This process is repeated until all of the points surrounding all of the seeds have lost their original color (see Fig. 3 and 4).
Application and Implementation of Flood-fill Algorithm in Python
We have discussed the algorithm steps and pseudocode of the flood-fill algorithm. For more details and to clear the basis of this algorithm, we will implement the flood-fill algorithm using Python. So, why do we choose this language? Python is best for image processing, and it has a giant built-in library function to deal with an image. We will use the PIL (Python Imaging Library) library to put pixels in an image for the flood-fill calculation. Make sure you have the pillow library installed on your machine. We will draw a three-dimensional array line using the flood-fill algorithm. Here, the 8-connected path (up, down, left, right, up-left, up-right, down-left, down-right) will be considered for this algorithm. One can also use the 4-connected path (up, down, left, right) for this process. The full code is given below and line by line of this code will be discussed.
from PIL import Image as img
def Floodfill(a,b, fill_Color, OriginalColor) :
color=1
im = img.new(mode='1', size=(500,500),color=color)
if (color==OriginalColor):
im.putpixel((a, b), fill_Color)
for i in range(499):
im.putpixel((a, b ), fill_Color)
im.putpixel((a, b + i), fill_Color)
im.putpixel((a + i, b + i), fill_Color)
im.putpixel((a - i, b), fill_Color)
im.putpixel((a, b - i), fill_Color)
im.putpixel((a - i, b - i), fill_Color)
return im
if __name__=='__main__':
FinalImage=Floodfill(0,0, 0, 1)
FinalImage.show()
We are importing the 'Image' class from the 'PIL' library and then renaming the 'Image' class as 'img'. We rename the package for the character reduction in code.
from PIL import Image as imgNow, we define a function named 'Floodfill' which receives the values of 'a, b, fill_Color, OriginalColor'. ('a' (x-axis value) and 'b' (y-axis value))
def Floodfill(a,b, fill_Color, OriginalColor)We set the value of 'color' as '1'. Here '1' means 'white color' and '0' means 'black color'. We keep the background as white color '1' and the foreground as black color '0'. That means we draw the line using black color.
color=1
Now, we are taking an image canvas whose size is 500 x 500 with mode '1' ( mode '1' means the background is white color). Then, all things are assigned in the variable 'im'.
im = img.new(mode='1', size=(500,500),color=color)In this conditioning step, we are checking the original color (white) with the Color (white) variable according to the algorithm.
if (color==OriginalColor):Then, we will draw the line by taking the 'a' (x-axis value) and 'b' (y-axis value) values with the fill color '0' (black). This time we will use the 'putpixel' function to put a black dot in the image.
im.putpixel((a, b), fill_Color)To traverse every pixel in the image, we will continuously run a loop 0-499 times (this value will vary with the image canvas size). Then, we will continuously put a black dot using the 'putpixel' function of the 'Image' class from the 'PIL' package of the Python pillow.
for i in range(499):
im.putpixel((a, b ), fill_Color)
im.putpixel((a, b + i), fill_Color)
im.putpixel((a + i, b + i), fill_Color)
im.putpixel((a - i, b), fill_Color)
im.putpixel((a, b - i), fill_Color)
im.putpixel((a - i, b - i), fill_Color)At the end of this function, we will return the final image file.
return imNow the function will be called from the main function. The position of 'a' and 'b' is set as (0, 0). That means we will start the traversing from the 0 coordination of the canvas image.
if __name__=='__main__':
FinalImage=Floodfill(0,0, 0, 1)
FinalImage.show()NoteBook for installing pillow package: Use these commands for Windows (pip install pillow or pip3 install pillow). For the Linux user use these commands (sudo aptitude install python3-pil or sudo apt install python3-pil or sudo apt install python-pil ). The pillow library is sometimes installed by default with other packages like Numpy, Scipy, OpenCV, etc.
0 মন্তব্যসমূহ