Bitmap/Flood fill
You are encouraged to solve this task according to the task description, using any language you may know.
Implement a flood fill.
A flood fill is a way of filling an area using color banks to define the contained area or a target color which "determines" the area (the valley that can be flooded; Wikipedia uses the term target color). It works almost like a water flooding from a point towards the banks (or: inside the valley): if there's a hole in the banks, the flood is not contained and all the image (or all the "connected valleys") get filled.
To accomplish the task, you need implementing just one of the possible algorithms (examples are on Wikipedia). Variations on the theme are allowed (e.g. adding a tolerance parameter or argument for color-matching of the banks or target color).
Testing: the basic algorithm is not suitable for truecolor images; a possible test image is the one shown on the right box; you can try to fill the white area, or the black inner circle.
Ada
<lang ada> procedure Flood_Fill
( Picture : in out Image;
From : Point;
Fill : Pixel;
Replace : Pixel;
Distance : Luminance := 20
) is
function Diff (A, B : Luminance) return Luminance is
pragma Inline (Diff);
begin
if A > B then
return A - B;
else
return B - A;
end if;
end Diff;
function "-" (A, B : Pixel) return Luminance is
pragma Inline ("-");
begin
return Luminance'Max (Luminance'Max (Diff (A.R, B.R), Diff (A.G, B.G)), Diff (A.B, B.B));
end "-";
procedure Column (From : Point);
procedure Row (From : Point);
Visited : array (Picture'Range (1), Picture'Range (2)) of Boolean :=
(others => (others => False));
procedure Column (From : Point) is
X1 : Positive := From.X;
X2 : Positive := From.X;
begin
Visited (From.X, From.Y) := True;
for X in reverse Picture'First (1)..From.X - 1 loop
exit when Visited (X, From.Y);
declare
Color : Pixel renames Picture (X, From.Y);
begin
Visited (X, From.Y) := True;
exit when Color - Replace > Distance;
Color := Fill;
X1 := X;
end;
end loop;
for X in From.X + 1..Picture'Last (1) loop
exit when Visited (X, From.Y);
declare
Color : Pixel renames Picture (X, From.Y);
begin
Visited (X, From.Y) := True;
exit when Color - Replace > Distance;
Color := Fill;
X2 := X;
end;
end loop;
for X in X1..From.X - 1 loop
Row ((X, From.Y));
end loop;
for X in From.X + 1..X2 loop
Row ((X, From.Y));
end loop;
end Column;
procedure Row (From : Point) is
Y1 : Positive := From.Y;
Y2 : Positive := From.Y;
begin
Visited (From.X, From.Y) := True;
for Y in reverse Picture'First (2)..From.Y - 1 loop
exit when Visited (From.X, Y);
declare
Color : Pixel renames Picture (From.X, Y);
begin
Visited (From.X, Y) := True;
exit when Color - Replace > Distance;
Color := Fill;
Y1 := Y;
end;
end loop;
for Y in From.Y + 1..Picture'Last (2) loop
exit when Visited (From.X, Y);
declare
Color : Pixel renames Picture (From.X, Y);
begin
Visited (From.X, Y) := True;
exit when Color - Replace > Distance;
Color := Fill;
Y2 := Y;
end;
end loop;
for Y in Y1..From.Y - 1 loop
Column ((From.X, Y));
end loop;
for Y in From.Y + 1..Y2 loop
Column ((From.X, Y));
end loop;
end Row;
Color : Pixel renames Picture (From.X, From.Y);
begin
if Color - Replace <= Distance then
Visited (From.X, From.Y) := True;
Color := Fill;
Column (From);
end if;
end Flood_Fill; </lang> The procedure has the following parameters. Picture is the image to change. From is the point to start at. Fill is the color to fill with. Replace is the color to replace. Distance defines the range of color around Replace to replace as well. The distance is defined as a maximum of the differences of stimuli. The following code snippet reads the test file, fills the area between two circles red, and writes the result: <lang ada> declare
File : File_Type;
begin
Open (File, In_File, "Unfilledcirc.ppm");
declare
Picture : Image := Get_PPM (File);
begin
Close (File);
Flood_Fill
( Picture => Picture,
From => (122, 30),
Fill => (255,0,0),
Replace => White
);
Create (File, Out_File, "Filledcirc.ppm");
Put_PPM (File, Picture);
Close (File);
end;
end; </lang>
C
The sys/queue.h is not POSIX. (See FIFO)
<lang c>/* #include <sys/queue.h> */ typedef struct {
color_component red, green, blue;
} rgb_color; typedef rgb_color *rgb_color_p;
void floodfill(image img, int px, int py, rgb_color_p bankscolor, rgb_color_p rcolor);</lang>
<lang c>#include "imglib.h"
typedef struct _ffill_node {
int px, py; TAILQ_ENTRY(_ffill_node) nodes;
} _ffill_node_t; TAILQ_HEAD(_ffill_queue_s, _ffill_node); typedef struct _ffill_queue_s _ffill_queue;
inline void _ffill_removehead(_ffill_queue *q) {
_ffill_node_t *n = q->tqh_first;
if ( n != NULL ) {
TAILQ_REMOVE(q, n, nodes);
free(n);
}
}
inline void _ffill_enqueue(_ffill_queue *q, int px, int py) {
_ffill_node_t *node;
node = malloc(sizeof(_ffill_node_t));
if ( node != NULL ) {
node->px = px; node->py = py;
TAILQ_INSERT_TAIL(q, node, nodes);
}
}
inline double color_distance( rgb_color_p a, rgb_color_p b ) {
return sqrt( (double)(a->red - b->red)*(a->red - b->red) +
(double)(a->green - b->green)*(a->green - b->green) + (double)(a->blue - b->blue)*(a->blue - b->blue) ) / (256.0*sqrt(3.0)); }
inline void _ffill_rgbcolor(image img, rgb_color_p tc, int px, int py) {
tc->red = GET_PIXEL(img, px, py)[0]; tc->green = GET_PIXEL(img, px, py)[1]; tc->blue = GET_PIXEL(img, px, py)[2];
}
- define NSOE(X,Y) do { \
if ( ((X)>=0)&&((Y)>=0) && ((X)<img->width)&&((Y)<img->height)) { \
_ffill_rgbcolor(img, &thisnode, (X), (Y)); \
if ( color_distance(&thisnode, bankscolor) > tolerance ) { \
if (color_distance(&thisnode, rcolor) > 0.0) { \ put_pixel_unsafe(img, (X), (Y), rcolor->red, \ rcolor->green, \ rcolor->blue); \ _ffill_enqueue(&head, (X), (Y)); \ pixelcount++; \ } \
} \ } \ } while(0)
unsigned int floodfill(image img, int px, int py,
rgb_color_p bankscolor,
rgb_color_p rcolor)
{
_ffill_queue head; rgb_color thisnode; unsigned int pixelcount = 0; double tolerance = 0.05;
if ( (px < 0) || (py < 0) || (px >= img->width) || (py >= img->height) ) return;
TAILQ_INIT(&head);
_ffill_rgbcolor(img, &thisnode, px, py); if ( color_distance(&thisnode, bankscolor) <= tolerance ) return;
_ffill_enqueue(&head, px, py);
while( head.tqh_first != NULL ) {
_ffill_node_t *n = head.tqh_first;
_ffill_rgbcolor(img, &thisnode, n->px, n->py);
if ( color_distance(&thisnode, bankscolor) > tolerance ) {
put_pixel_unsafe(img, n->px, n->py, rcolor->red, rcolor->green, rcolor->blue);
pixelcount++;
}
int tx = n->px, ty = n->py;
_ffill_removehead(&head);
NSOE(tx - 1, ty);
NSOE(tx + 1, ty);
NSOE(tx, ty - 1);
NSOE(tx, ty + 1);
}
return pixelcount;
}</lang>
The pixelcount could be used to know the area of the filled region. The internal parameter tolerance can be tuned to cope with antialiasing, bringing "sharper" resuts.
Usage example
(Comments show changes to fill the white area instead of the black circle)
<lang c>#include <stdio.h>
- include <stdlib.h>
- include "imglib.h"
int main(int argc, char **argv) {
image animage; rgb_color ic; rgb_color rc;
if ( argc > 1 ) {
animage = read_image(argv[1]);
if ( animage != NULL ) {
ic.red = 255; /* = 0; */
ic.green = 255; /* = 0; */
ic.blue = 255; /* = 0; */
rc.red = 0;
rc.green = 255;
rc.blue = 0;
floodfill(animage, 100, 100, &ic, &rc);
/* 150, 150 */
print_jpg(animage, 90);
free(animage);
}
}
return 0;
}</lang>
Forth
This simple recursive algorithm uses routines from Basic bitmap storage. <lang forth>
- third 2 pick ;
- 3dup third third third ;
- 4dup 2over 2over ;
- flood ( color x y bmp -- )
3dup b@ >r ( R: color to fill ) 4dup b! third 0 > if rot 1- -rot 3dup b@ r@ = if recurse then rot 1+ -rot then third 1+ over bwidth < if rot 1+ -rot 3dup b@ r@ = if recurse then rot 1- -rot then over 0 > if swap 1- swap 3dup b@ r@ = if recurse then swap 1+ swap then over 1+ over bheight < if swap 1+ swap 3dup b@ r@ = if recurse then swap 1- swap then r> drop ;
</lang>
Fortran
Here the target color paradigm is used. Again the matchdistance parameter can be tuned to ignore small differences that could come because of antialiasing.
<lang fortran>module RCImageArea
use RCImageBasic use RCImagePrimitive implicit none
real, parameter, private :: matchdistance = 0.2
private :: northsouth, eastwest
contains
subroutine northsouth(img, p0, tcolor, fcolor) type(rgbimage), intent(inout) :: img type(point), intent(in) :: p0 type(rgb), intent(in) :: tcolor, fcolor
integer :: npy, spy, y type(rgb) :: pc
npy = p0%y - 1
do
if ( inside_image(img, p0%x, npy) ) then
call get_pixel(img, p0%x, npy, pc)
if ( ((pc .dist. tcolor) > matchdistance ) .or. ( pc == fcolor ) ) exit
else
exit
end if
npy = npy - 1
end do
npy = npy + 1
spy = p0%y + 1
do
if ( inside_image(img, p0%x, spy) ) then
call get_pixel(img, p0%x, spy, pc)
if ( ((pc .dist. tcolor) > matchdistance ) .or. ( pc == fcolor ) ) exit
else
exit
end if
spy = spy + 1
end do
spy = spy - 1
call draw_line(img, point(p0%x, spy), point(p0%x, npy), fcolor)
do y = min(spy, npy), max(spy, npy)
if ( y == p0%y ) cycle
call eastwest(img, point(p0%x, y), tcolor, fcolor)
end do
end subroutine northsouth
subroutine eastwest(img, p0, tcolor, fcolor) type(rgbimage), intent(inout) :: img type(point), intent(in) :: p0 type(rgb), intent(in) :: tcolor, fcolor
integer :: npx, spx, x type(rgb) :: pc
npx = p0%x - 1
do
if ( inside_image(img, npx, p0%y) ) then
call get_pixel(img, npx, p0%y, pc)
if ( ((pc .dist. tcolor) > matchdistance ) .or. ( pc == fcolor ) ) exit
else
exit
end if
npx = npx - 1
end do
npx = npx + 1
spx = p0%x + 1
do
if ( inside_image(img, spx, p0%y) ) then
call get_pixel(img, spx, p0%y, pc)
if ( ((pc .dist. tcolor) > matchdistance ) .or. ( pc == fcolor ) ) exit
else
exit
end if
spx = spx + 1
end do
spx = spx - 1
call draw_line(img, point(spx, p0%y), point(npx, p0%y), fcolor)
do x = min(spx, npx), max(spx, npx)
if ( x == p0%x ) cycle
call northsouth(img, point(x, p0%y), tcolor, fcolor)
end do
end subroutine eastwest
subroutine floodfill(img, p0, tcolor, fcolor) type(rgbimage), intent(inout) :: img type(point), intent(in) :: p0 type(rgb), intent(in) :: tcolor, fcolor type(rgb) :: pcolor
if ( .not. inside_image(img, p0%x, p0%y) ) return call get_pixel(img, p0%x, p0%y, pcolor) if ( (pcolor .dist. tcolor) > matchdistance ) return
call northsouth(img, p0, tcolor, fcolor) call eastwest(img, p0, tcolor, fcolor) end subroutine floodfill
end module RCImageArea</lang>
Usage example excerpt (which on the test image will fill with green the inner black circle):
<lang fortran> call floodfill(animage, point(100,100), rgb(0,0,0), rgb(0,255,0))</lang>
Perl
The fill of the Perl package Image::Imlib2 is a flood fill (so the documentatin of Image::Imlib2 says). The target colour is the one of the starting point pixel; the color set with set_color is the fill colour.
<lang perl>#! /usr/bin/perl
use strict; use Image::Imlib2;
my $img = Image::Imlib2->load("Unfilledcirc.jpg"); $img->set_color(0, 255, 0, 255); $img->fill(100,100); $img->save("filledcirc.jpg"); exit 0;</lang>
A homemade implementation can be:
<lang perl>use strict; use Image::Imlib2;
sub colordistance {
my ( $c1, $c2 ) = @_;
my ( $r1, $g1, $b1 ) = @$c1; my ( $r2, $g2, $b2 ) = @$c2; return sqrt(( ($r1-$r2)**2 + ($g1-$g2)**2 + ($b1-$b2)**2 ))/(255.0*sqrt(3.0));
}
sub floodfill {
my ( $img, $x, $y, $r, $g, $b ) = @_; my $distparameter = 0.2;
my %visited = (); my @queue = ();
my @tcol = ( $r, $g, $b );
my @col = $img->query_pixel($x, $y);
if ( colordistance(\@tcol, \@col) > $distparameter ) { return; }
push @queue, [$x, $y];
while ( scalar(@queue) > 0 ) {
my $pointref = shift(@queue); ( $x, $y ) = @$pointref; if ( ($x < 0) || ($y < 0) || ( $x >= $img->width ) || ( $y >= $img->height ) ) { next; } if ( ! exists($visited{"$x,$y"}) ) { @col = $img->query_pixel($x, $y); if ( colordistance(\@tcol, \@col) <= $distparameter ) { $img->draw_point($x, $y); $visited{"$x,$y"} = 1; push @queue, [$x+1, $y]; push @queue, [$x-1, $y]; push @queue, [$x, $y+1]; push @queue, [$x, $y-1]; } }
}
}
- usage example
my $img = Image::Imlib2->load("Unfilledcirc.jpg"); $img->set_color(0,255,0,255); floodfill($img, 100,100, 0, 0, 0); $img->save("filledcirc1.jpg"); exit 0;</lang>
This fills better than the Image::Imlib2 fill function the inner circle, since because of JPG compression and thanks to the $distparameter, it "sees" as black also pixel that are no more exactly black.
Tcl
Using code from Basic bitmap storage#Tcl, Bresenham's line algorithm#Tcl and Midpoint circle algorithm#Tcl <lang tcl>package require Tcl 8.5 package require Tk package require struct::queue
proc floodFill {img colour point} {
set new [colour2rgb $colour]
set old [getPixel $img $point]
struct::queue Q
Q put $point
while {[Q size] > 0} {
set p [Q get]
if {[getPixel $img $p] eq $old} {
set w [findBorder $img $p $old west]
set e [findBorder $img $p $old east]
drawLine $img $new $w $e
set q $w
while {[x $q] <= [x $e]} {
set n [neighbour $q north]
if {[getPixel $img $n] eq $old} {Q put $n}
set s [neighbour $q south]
if {[getPixel $img $s] eq $old} {Q put $s}
set q [neighbour $q east]
}
}
}
Q destroy
}
proc findBorder {img p colour dir} {
set lookahead [neighbour $p $dir]
while {[getPixel $img $lookahead] eq $colour} {
set p $lookahead
set lookahead [neighbour $p $dir]
}
return $p
}
proc x p {lindex $p 0} proc y p {lindex $p 1} proc neighbour {p dir} {
lassign $p x y
switch -exact -- $dir {
west {return [list [incr x -1] $y]}
east {return [list [incr x] $y]}
north {return [list $x [incr y -1]]}
south {return [list $x [incr y]]}
}
}
proc colour2rgb {color_name} {
set colour "#"
foreach part [winfo rgb . $color_name] {
append colour [format %02x [expr {$part >> 8}]]
}
return $colour
}
set img [newImage 70 50] fill $img white drawLine $img blue {0 0} {0 4} drawLine $img blue {0 4} {6 4} drawLine $img blue {6 4} {6 0} drawLine $img blue {6 0} {0 0} floodFill $img green {3 3} drawCircle $img black {35 25} 24 drawCircle $img black {35 25} 10 floodFill $img #7f7f7f {35 5}
toplevel .flood label .flood.l -image $img pack .flood.l </lang>