Re: analysing a bitmap

"Peter Bauer" <PeterBauer@xxxxxxxx> wrote in message
news:4294781b$0$26386$9b622d9e@xxxxxxxxxxxxxxxxxx
[...]
> now i'm trying to modify this for bitmaps, but i allways get a
> stack-overflow in the fill() methode.
> i have no clue whats the problem :(

Well, I'm pretty sure I figured it out. Nothing like a good bicycle
ride home to clear your head and give you time to mull it over.

The algorithm fails, spectacularly, when you try to fill in an area
with its existing colour. It should really be wrapped in a function
that checks whether the first pixel is not already the fill colour.

Otherwise, it simply never stops. It has no reason to. As written,
it fills an area defined by the original colour of the starting
pixel, by colouring it the new colour pixel by pixel. It stops when
the current colour of a neighbouring pixel is different from the
*old* colour. If the new colour is the same as the old colour, it
keeps painting and painting but never makes any progress.

I devised several schemes to make the algorithm smarter but they all
turned out to be unnecessary. If you go to the pixel on your left,
that function call does not need to look to the pixel on its right
at all - but this is interesting only if checking its colour is more
expensive than remembering where you came from last time, and I'm
not sure that is the case. An earlier scheme remembered _all_
directions that had been explored, but I proved to myself rather
quickly that that was flawed to begin with. The proof is left as an
exercise to the reader.

But no checking is _necessary_ beyond the first pixel. If that has
the same colour, no painting is necessary at all; it it has a
different colour, there is a region in that different colour that
can be filled with the existing algorithm.

Groetjes,
Maarten Wiltink


.

Relevant Pages

  • Re: Is this image resizing algorithm already known?
    ... > I searched the Internet for image resizing algorithms, ... > Does someone know if this algorithm already exists? ... E are the pixel colors. ... > 1) each original row pixel contributes with m color parts. ...
    (comp.graphics.algorithms)
  • Is this image resizing algorithm already known?
    ... I searched the Internet for image resizing algorithms, ... Does someone know if this algorithm already exists? ... E are the pixel colors. ... When we have 0 available parts, we take the next original row ...
    (comp.graphics.algorithms)
  • Re: analysing a bitmap
    ... > that checks whether the first pixel is not already the fill colour. ... > Otherwise, it simply never stops. ... > keeps painting and painting but never makes any progress. ... > I devised several schemes to make the algorithm smarter but they all ...
    (comp.lang.pascal.delphi.misc)
  • Re: FS-error diffusion (Was:Re: Different Implementations of VLIW .)
    ... |>>> You start with the top left pixel, pick the closest palette match (which ... That is a classic form of a sequential algorithm corresponding to a ... One of the approaches is the standard iterative improvement, ... oscillations where the best fit is ambiguous. ...
    (comp.arch)
  • Re: FS-error diffusion (Was:Re: Different Implementations of VLIW .)
    ... You start with the top left pixel, pick the closest palette match (which ... except that the algorithm depends on it: ... The nice thing about ordered dithering is that it is completely parallizable. ...
    (comp.arch)