Description
Flood Fill with Recursion
Your task this week is to implement several varieties of flood fill operations using recursion. These
operations can be applied to sample images. The objective for this week is for you to gain some experience
with recursion by solving a problem using programming knowledge gained from the class.
Read this document completely before you begin so that you know how to use what you’ve been given.
Background
An image is composed of an array of pixels. Each pixel has three bytes of information in the RGB format.
These bytes represent the red, blue, and green levels of the pixel. The values for each pixel range from 0
to 255.
In a flood fill operation, the user selects one pixel in the image along with an RGB color. In a painting
analogy, the chosen color floods out in all directions from the chosen pixel until it reaches a boundary. In
the simplest case, such a boundary might simply be a pixel of another color, such as black.
One can implement flood fill recursively, although the number of stack frames needed may be too large for
typical image sizes, so you will implement a version that limits the range of the flooding to about 40 pixels,
thus limiting the total number of pixels to about 5,000.
The Image Arrays
Your functions will be given arrays for each of the three channels in the image: red, green, and blue. These
arrays will be passed as pointers to 8-bit pixels (that is, as uint8_t*). However, they represent twodimensional arrays of specified height and width (these values are also provided to your functions). To
make use of the arrays, you must calculate the appropriate offset into the one-dimensional C arrays based
on the two indices of the pixel that you want to access. Recall from class that you should make use of the
expression x + y * width to access the pixel at (x,y). For example, given an array uint8_t* red for
the red channel, you can access the (x,y) pixel in the array with the expression red[x + y * width].
Pieces
In addition to code, we have provided a few sample images in the Images subdirectory. The Examples
subdirectory contains a few images processed by the “gold” version of the program (the version that I write
before asking you to do the assignment). The images’ names tell you the arguments to pass when you run
the program.
There is more code in the package this time, but you still need to look at only three files:
mp8.h This header file provides function declarations and descriptions of the functions
that you must write for this assignment.
mp8.c The source file for helper functions, including wrapper functions that call the
recursive functions in mp8recurse.c. Function headers for all functions are
provided to help you get started.
mp8recurse.c The source file for your recursive functions. Function headers for all functions
are provided to help you get started.
Other files provided to you include
main.c A source file that interprets commands and calls your functions.
Makefile A file that describes how to build your program, allowing you to type “make”
instead of re-typing the full compiler command every time.
imageData.h Some utility functions written by a former TA for the class.
imageData.c
lodepng.h A package for loading and storing PNG images.
lodepng.c
You need not read any of these, although you are welcome to do so.
Details
You should read the descriptions of the functions in the header file and peruse the function headers in the
source file before you begin coding. Here are the tasks that you need to complete for this assignment:
1. Write a recursive flood fill, stopping at black pixels.
2. Write a second recursive flood fill that stops at grey (near-black) pixels.
3. Write a recursive flood fill that stops at any color far enough from the color at the initial flood point,
and is limited to a 40-pixel range.
The structure for each of these tasks is almost identical, and involves implementing one function (per task)
in the mp8recurse.c file and one function (per task) in the mp8.c file. The first function is a recursive
flooding function that uses an array to track its progress (and to avoid infinite loops). The second function
is a wrapper function that prepares the array to track the flood’s progress, calls the recursive flooding
function, and then uses the progress array to create the final image from the original image. For tasks 2 and
3, you must also create a small helper function (in mp8.c) that decides whether two colors are within a
certain distance of one another. The total is thus seven functions.
All function signatures appear in mp8.h. The wrapper functions and utility function must be written in
mp8.c. For the wrapper functions, the first five parameters to each describe the input image: the width in
pixels, the height in pixels, and the arrays containing the red, green, and blue channels of the pixels. The
next five or six parameters describe the flood: the starting x and y position, the red, green, and blue
components of the flood color, and (for tasks 2 and 3 only) the distance squared value. Finally, the last
three parameters are arrays through which your wrapper functions define the red, green, and blue color
channels for the final output image.
The recursive functions that your wrapper functions must call appear in mp8recurse.c. The prefixes of
the names match those of the wrapper functions, so basicFlood should call basicRecurse, and so forth.
Step 1: The Wrapper Structure
Start by writing basicFlood, the wrapper function for the first task. The wrapper should use outRed to
record whether each pixel has been visited by the flood. Initially, no pixels have been visited, so the first
step is to fill the array with 0s (use memset). Then call basicRecurse (once). Finally, walk through the
whole image: pixels marked in the marking array (outRed) should be filled with the flood color. Pixels
not marked in the marking array should be copied from the original image. Keep in mind that you are
overwriting outRed as you fill in the final image.
Step 2: Your First Recursion
Now you’re ready for your first recursive function! Be sure to get the stopping conditions right, or your
program will crash due to infinite recursion. Use the marking array to mark any pixel visited, and check it
before making any recursive calls. Check adjacent pixels in the following order: up (negative y), right
(positive x), down (positive y), and left (negative x). Don’t recurse into black pixels (RGB = 000000).
When you complete this function, you can compile the program and use command “1” to test and debug
your two functions. The file Images/E.png has true black pixels. The files with pictures of numbers
(Images/seven.png and Images/eight.png) do not—see what happens with your fill.
Step 3: Defining a Distance Metric for Color
People who care about color do not use Euclidean distance in RGB space. People who want simplicity for
a programming assignment do, however. Your next step is to write the short function
colorsWithinDistSq in mp8.c. This function must return 1 if the two RGB colors are within the
specified distance squared of one another. In other words, if (R1 – R2)
2
+ (G1 – G2)
2
+(B1 – B2)
2
≤ (distance)2
.
Otherwise, the function should return 0. Note that you do not need to take any square roots.
Step 4: Stopping Near Black
Now that you have a way to measure distance in RGB space, you can write a new wrapper (greyFlood)
and a new recursive routine (greyRecurse) that stop when they run into pixels that are within a given
parameter (the new distSq parameter) of black (RGB=000000). Use colorsWithinDistSq to check.
Once those functions are complete, you can test them by compiling and using command “2”. To get a
feeling for the actual variation within an image that looks like a black digit at first glance, try using
Images/eight.png as an input, starting the flood at (20,40), and seeing what happens with distSq
values of 250, 2000, and 2500.
Step 5: Stemming the Flood
You are now ready to write the final version of the flooding algorithm, which stops when it goes more than
40 pixels away from the starting point (make this check the first stopping condition, do NOT use square
roots, and do not mark pixels that are too far away). This version also stops when the RGB color goes too
far away from the color at the starting point (use the colorsWithinDistSq function again, but in the
opposite sense). You also need a new wrapper (limitedFlood), but the code only differs in that it calls
limitedRecurse.
Once these two functions are complete, you can test them using command “3”. Now you can see how close
to white (RGB=FFFFFF) the background in Images/numbers.png really is by flooding at (100,100) with
distance squared of 10. Or look at some regions in Images/tajmahal.png, such as (300,430) versus
(300,440) with distance squared of 500.
The Interface
When you have completed one or more of the functions, you can type “make” (no quotes) to compile your
code into an “mp8” executable program. The make program shows you the compiler commands that it
executes on your behalf, so you can see what is happening and will receive any syntax errors or other errors
or warnings from the compiler. Fix any warnings!
Once you have compiled your program, you can use the interface built into main.c to execute your
functions. A set of images has been provided to you in the Images subdirectory along with several copies
processed by a correct version of the program in the Examples subdirectory (take a look).
The mp8 program takes seven or eight command line arguments:
./mp8
