tromp@cwi.nl (John Tromp) (11/03/90)
I am investigating algorithms for filling up an arbitrary enclosed region in a bitmap. I already traced some references, but the algorithms i found are concerned with speed mainly, e.g. number of times each internal pixel gets visited. Instead I am interested in algorithms using as little memory as possible. Can anybody tell me what is known about this or provide me with pointers? Many thanks, John Tromp (tromp@cwi.nl)
torbenm@sleipner.diku.dk (Torben [gidius Mogensen) (11/05/90)
tromp@cwi.nl (John Tromp) writes: >I am investigating algorithms for filling up an arbitrary enclosed region >in a bitmap. I already traced some references, but the algorithms i found >are concerned with speed mainly, e.g. number of times each internal pixel >gets visited. Instead I am interested in algorithms using as little memory >as possible. Can anybody tell me what is known about this or provide me >with pointers? Many thanks, >John Tromp (tromp@cwi.nl) Flood fill algorithms are indeed notoriously memory hungry. The simplest algorithm: fill(x,y,from,to) int x,y; colour from,to; { if (colour[x,y]==from) { colour[x,y]=to; fill(x-1,y,from,to); fill(x+1,y,from,to); fill(x,y-1,from,to); fill(x,y+1,from,to); } } uses memory liniear in the number of pixels in the area, almost regardless of the shape of the area. This can be somewhat bettered by keeping an explicit stack corresponding to the calls, and using it FIFO (buffer-like) rather than LIFO (stack-like). This uses memory that is linear in min(width,height) in the best case, but it is still rather slow. The algorithm is described below. fill(x,y,from,to) int x,y; colour from,to; { int xbuf[bufsize], ybuf[bufsize]; int bottom,top; bottom=0; top=1; xbuf[0]=x; ybuf[0]=y; do { x=xbuf[bottom]; y=ybuf[bottom++]; if (colour[x,y]==from) { colour[x,y]=to; xbuf[top]=x-1; ybuf[top++]=y; xbuf[top]=x+1; ybuf[top++]=y; xbuf[top]=x; ybuf[top++]=y-1; xbuf[top]=x; ybuf[top++]=y+1; } } while (bottom!=top); } xbuf and ybuf will normally be implemented as cyclic buffers. This is essential to keeping memory usage low. The low memory usage comes from the fact that at the time you inspect a pixel, it is likely to be filled, so you take several pixels out of the buffer before you add the four neighbours of an unfilled pixel. You can add a test of whether a pixel is filled, before adding it to the stack, but this requires extra time. If the buffer gets full, you can trim it by removing already filled or duplicate pixels. A good worst-case test example is filling a closed area containing random dots with a density of about 1 in five pixels, so the area is mostly connected, but contains very few long straight lines of colour "from". Most low-memory algorithms tries to draw straight horisontal or vertical lines, keeping on a stack the points of non-"from" colour that touches these lines. A good strategy is to have the lines divide the area into two areas of roughly similar size, and then fill out first one then the other by recursive subdivision. This would keep the used memory proportional roughly (in the best case) to the logarithm of the number of pixels in the area. This strategy is good for mostly convex areas, but falls down on the example above, where the memory usage can be as bad as (or worse than) that of the simple algorithm above. Regarding worst-case memory usage, the FIFO point buffer described above performs well, but on average it is slower and more memory consuming than the advanced algorithms, so maybe the best would be an algorithm that first tries to use the advanced algorithm, and swithces to the simpler if the memory usage get high. This requires either ability to restart the entire opeartion, or a way of converting a state in one algorithm to a state in the other. Hope this helps, Torben Mogensen (torbenm@diku.dk)