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.
C
The sys/queue.h
is not POSIX. (See FIFO)
<lang c>#include <math.h>
- include <sys/queue.h>
typedef struct {
color_component red, green, blue;
} rgb_color; typedef rgb_color *rgb_color_p;
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>
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>