Save the Girl Child
Flood-Fill Flood-fill
• Used in interactive paint systems. • The user specify a seed by pointing to the interior of the region to initiate a flood operation
Recursive Flood-Fill
• Fill a image-space region with some intensity (color) value • How to define the region? • Fill Until vs. Fill While • 4-connectivity vs. 8-connectivity
Flood-Fill from Seed
• Start from the seed and floods the region until a boundary is met.
A simple recursive algorithm can be used: void floodFill(int x, int y, int fill, int old) { if ((x < 0) || (x >= width)) return; if ((y < 0) || (y >= height)) return; if (getPixel(x, y) == old) { setPixel(fill, x, y); floodFill(x+1, y, fill, old); floodFill(x, y+1, fill, old); floodFill(x-1, y, fill, old); floodFill(x, y-1, fill, old); } }
8-connected vs. 4-connected
Recursive Flood-Fill Algorithm
The algorithm is very simple, however it is: • highly recursive - requiring a huge number of procedural calls; • can cause recursion stack to overflow • no mechanism to determine whether the visited pixels have been tested before
S
An 8-connected flood is able to flood through corners that a 4-connected flood cannot.
1
Fill Until vs. Fill While
Flood Until void floodUntil(int x, int y, int n_color, int B_color) { if ((x < 0) || (x >= width)) return; if ((y < 0) || (y >= height)) return; c = getPixel(x, y); if (c != n_color && c != B_color) { setPixel(new_color, x, y); floodFill(x+1, y, n_color B_color); floodFill(x, y+1, n_color B_color); floodFill(x-1, y, n_color B_color); floodFill(x, y-1, n_color B_color); } }
seed
Flood While void floodWhile(int x, int y, int n_color, int old) { if ((x < 0) || (x >= width)) return; if ((y < 0) || (y >= height)) return; if (getPixel(x, y) == old) { setPixel(fill, x, y); floodFill(x+1, y, n_color, old); floodFill(x, y+1, n_color, old); floodFill(x-1, y, n_color, old); floodFill(x, y-1, n_color, old); } }
With global variables void floodWhile(int x, int y) { if ((x < 0) || (x >=
• Used in interactive paint systems. • The user specify a seed by pointing to the interior of the region to initiate a flood operation
Recursive Flood-Fill
• Fill a image-space region with some intensity (color) value • How to define the region? • Fill Until vs. Fill While • 4-connectivity vs. 8-connectivity
Flood-Fill from Seed
• Start from the seed and floods the region until a boundary is met.
A simple recursive algorithm can be used: void floodFill(int x, int y, int fill, int old) { if ((x < 0) || (x >= width)) return; if ((y < 0) || (y >= height)) return; if (getPixel(x, y) == old) { setPixel(fill, x, y); floodFill(x+1, y, fill, old); floodFill(x, y+1, fill, old); floodFill(x-1, y, fill, old); floodFill(x, y-1, fill, old); } }
8-connected vs. 4-connected
Recursive Flood-Fill Algorithm
The algorithm is very simple, however it is: • highly recursive - requiring a huge number of procedural calls; • can cause recursion stack to overflow • no mechanism to determine whether the visited pixels have been tested before
S
An 8-connected flood is able to flood through corners that a 4-connected flood cannot.
1
Fill Until vs. Fill While
Flood Until void floodUntil(int x, int y, int n_color, int B_color) { if ((x < 0) || (x >= width)) return; if ((y < 0) || (y >= height)) return; c = getPixel(x, y); if (c != n_color && c != B_color) { setPixel(new_color, x, y); floodFill(x+1, y, n_color B_color); floodFill(x, y+1, n_color B_color); floodFill(x-1, y, n_color B_color); floodFill(x, y-1, n_color B_color); } }
seed
Flood While void floodWhile(int x, int y, int n_color, int old) { if ((x < 0) || (x >= width)) return; if ((y < 0) || (y >= height)) return; if (getPixel(x, y) == old) { setPixel(fill, x, y); floodFill(x+1, y, n_color, old); floodFill(x, y+1, n_color, old); floodFill(x-1, y, n_color, old); floodFill(x, y-1, n_color, old); } }
With global variables void floodWhile(int x, int y) { if ((x < 0) || (x >=