Bitmap/Flood fill

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];

}

1. 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>

1. include <stdlib.h>
2. 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>

E

Using the image type from Basic bitmap storage#E.

<lang e>def floodFill(image, x, y, newColor) {

 def matchColor := image[x, y]
 def w := image.width()
 def h := image.height()
 
 /** For any given pixel x,y, this algorithm first fills a contiguous 
     horizontal line segment of pixels containing that pixel, then
     recursively scans the two adjacent rows over the same horizontal 
     interval. Let this be invocation 0, and the immediate recursive 
     invocations be 1, 2, 3, ..., # be pixels of the wrong color, and
     * be where each scan starts; the fill ordering is as follows:
     
     --------------##########-------
     -...1111111111*11####*33333...-
     ###########000*000000000000...-
     -...2222222222*22222##*4444...-
     --------------------##---------
     
     Each invocation returns the x coordinate of the rightmost pixel it filled,
     or x0 if none were.
     
     Since it is recursive, this algorithm is unsuitable for large images
     with small stacks.
   */
 def fillScan(var x0, y) {
   if (y >= 0 && y < h && x0 >= 0 && x0 < w) {
     image[x0, y] := newColor
     var x1 := x0
     
     # Fill rightward
     while (x1 < w - 1 && image.test(x1 + 1, y, matchColor)) {
       x1 += 1
       image[x1, y] := newColor # This could be replaced with a horizontal-line drawing operation
     }
     
     # Fill leftward
     while (x0 > 0 && image.test(x0 - 1, y, matchColor)) {
       x0 -= 1
       image[x0, y] := newColor
     }
     
     if (x0 > x1) { return x0 } # Filled at most center

     # x0..x1 is now a run of newly-filled pixels.
     
     # println(`Filled $y $x0..$x1`)
     # println(image)
           
     # Scan the lines above and below
     for ynext in [y - 1, y + 1] {
       if (ynext >= 0 && ynext < h) {
         var x := x0
         while (x <= x1) {
           if (image.test(x, ynext, matchColor)) {
             x := fillScan(x, ynext)
           }
           x += 1
         }
       }
     }
     
     return x1
   } else {
     return x0
   }
 }

 fillScan(x, y)

}</lang>

Filled sample image

Note that this does not make any attempt to smoothly fill 'banks' or have a tolerance; it matches exact colors only. This will fill the example image with red inside green, and there will be black/white fringes:

<lang e>{

 println("Read")
 def i := readPPM(<import:java.io.makeFileInputStream>(<file:Unfilledcirc.ppm>))
 println("Fill 1")
 floodFill(i, 100, 100, makeColor.fromFloat(1, 0, 0))
 println("Fill 2")
 floodFill(i, 200, 200, makeColor.fromFloat(0, 1, 0))
 println("Write")
 i.writePPM(<import:java.io.makeFileOutputStream>(<file:Filledcirc.ppm>))
 println("Done")

}</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

Works with: Fortran version 90 and later

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>

J

Solution:
Uses getPixels and setPixels from Basic bitmap storage. <lang j>NB. finds and labels contiguous areas with the same numbers NB. ref: http://www.jsoftware.com/pipermail/general/2005-August/023886.html findcontig=: (|."1@|:@:>. (* * 1&(|.!.0)))^:4^:_@(* >:@i.@$)

NB.*getFloodpoints v Returns points to fill given starting point (x) and image (y) getFloodpoints=: [: 4&$.@$. [ (] = getPixels) [: findcontig ] -:"1 getPixels

NB.*floodFill v Floods area, defined by point and color (x), of image (y) NB. x is: 2-item list of (y x) ; (color) floodFill=: (1&({::)@[ ;~ 0&({::)@[ getFloodpoints ]) setPixels ]</lang>

Example Usage:
The following draws the same image as for the Tcl example image below.
Uses definitions from Basic bitmap storage, Bresenham's line algorithm and Midpoint circle algorithm. <lang j>'white blue yellow black orange red'=: 255 255 255,0 0 255,255 255 0,0 0 0,255 165 0,:255 0 0 myimg=: white makeRGB 50 70 lines=: (_2]\^:2) 0 0 25 0 , 25 0 25 35 , 25 35 0 35 , 0 35 0 0 myimg=: (lines;blue) drawLines myimg myimg=: (3 3; yellow) floodFill myimg myimg=: ((35 25 24 ,: 35 25 10);black) drawCircles myimg myimg=: (5 34;orange) floodFill myimg myimg=: (5 36;red) floodFill myimg viewRGB myimg</lang>

Alternative findcontig:
The following alternative version of findcontig is less concise but is leaner, faster, works for n-dimensions and is not restricted to numerical arrays. <lang j>NB. ref: http://www.jsoftware.com/pipermail/general/2005-August/024174.html eq=:[:}:"1 [:($$[:([:+/\1:,}:~:}.),) ,&_"1 NB. equal numbers for atoms of y connected in first direction eq_nd=: i.@#@$(<"0@[([:, |:^:_1"0 _)&> [:EQ&.> <@|:"0 _)] NB. n-dimensional eq, gives an #@$,*/@$ shaped matrix repl=: (i.~{.){ {:@] NB. replaces x by applying replace table y cnnct=: [: |:@({."1<.//.]) [: ; <@(,.<./)/.~

findcontig_nd=: 3 : '($y)${. ([:({.,~}:) ([ repl cnnct)/\.)^:([:+./@(~:/)2&{.)^:_ (,{.) eq_nd (i.~ ~.@,) y'</lang>

Perl

Library: Imlib2

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]; } }

   }

}

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.

Ruby

<lang ruby>class RGBColour

 def ==(a_colour)
   values == a_colour.values
 end

end

class Queue < Array

 alias_method :enqueue, :push
 alias_method :dequeue, :shift

end

class Pixmap

 def flood_fill(pixel, new_colour)
   current_colour = self[pixel.x, pixel.y]
   queue = Queue.new
   queue.enqueue(pixel)
   until queue.empty?
     p = queue.dequeue
     if self[p.x, p.y] == current_colour
       west = find_border(p, current_colour, :west)
       east = find_border(p, current_colour, :east)
       draw_line(west, east, new_colour)
       q = west
       while q.x <= east.x
         [:north, :south].each do |direction|
           n = neighbour(q, direction)
           queue.enqueue(n) if self[n.x, n.y] == current_colour
         end
         q = neighbour(q, :east)
       end
     end
   end
 end

 def neighbour(pixel, direction)
   case direction
   when :north then Pixel[pixel.x, pixel.y - 1]
   when :south then Pixel[pixel.x, pixel.y + 1]
   when :east  then Pixel[pixel.x + 1, pixel.y]
   when :west  then Pixel[pixel.x - 1, pixel.y]
   end
 end

 def find_border(pixel, colour, direction)
   nextp = neighbour(pixel, direction)
   while self[nextp.x, nextp.y] == colour
     pixel = nextp
     nextp = neighbour(pixel, direction)
   end
   pixel
 end

end

bitmap = Pixmap.new(300, 300) bitmap.draw_circle(Pixel[149,149], 120, RGBColour::BLACK) bitmap.draw_circle(Pixel[200,100], 40, RGBColour::BLACK) bitmap.flood_fill(Pixel[140,160], RGBColour::BLUE)</lang>

Tcl

Library: Tk

Using struct::queue package from

Library: tcllib

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} {

   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 25} drawLine $img blue {0 25} {35 25} drawLine $img blue {35 25} {35 0} drawLine $img blue {35 0} {0 0} floodFill $img yellow {3 3}

drawCircle $img black {35 25} 24 drawCircle $img black {35 25} 10 floodFill $img orange {34 5} floodFill $img red {36 5}

toplevel .flood label .flood.l -image $img pack .flood.l</lang> Results in: