Re: FS-error diffusion (Was:Re: Different Implementations of VLIW .)

In article <p9idnSaOrfRHFrPVnZ2dnUVZ8vOdnZ2d@xxxxxxxxxxxx>,
terje.mathisen@xxxxxxxxxxxxx says...

Niels Jørgen Kruse wrote:
Terje Mathisen <terje.mathisen@xxxxxxxxxxxxx> wrote:

That's funny, because I've been helping this guy in c.l.a.x86 speeding
up Floyd-Steinberg error diffusion for reducing true-color images to a
limited palette (i.e. GIF/PNG 8-bit/pixel), and that algorithm (FS), is
a horrible example of a sequentially dependent process:

You start with the top left pixel, pick the closest palette match (which
is an interesting problem all by itself!), calculate the offset between
this color value and the pixel, then distribute the error across all the
surrounding pixels which haven't already been processed.

(I.e. right, down-right, down and down-left.)

Any particular reason you have to do the pixels in this order (other
than to keep track of which have been processed)?

None, except that the algorithm depends on it:

Errors can in theory spread arbitrarily far across the image, instead of
having some kind of exponential decay that would limit the maximum reach
of each update.

Such a limit would make it possible to start in multiple places, running
things in parallel, with a fixup stage at the end, but as it is, the
absolute minimum latency is fixed by the maximum length of the error
propagation, which is length+width.

Since the palette to be used can contain arbitrary values, there is also
no absolute boundary for the maximum/minimum distance in color space
between two neighboring colors. :-(


The nice thing about ordered dithering is that it is completely parallizable.
With enough resolution you can get some decent results if the dither pattern
isn't too large (4x4 is ok, 2x2 is better). It works even better if you can
adjust the pallete for "best" fit.

There are better error-diffusion algorithms that don't spread the error as
far, look better and run faster. Can't remember the name right now :(, and my
text books are buried in storage.

The last time I looked into this, I was programming an 8088 (well, V20),
translating a GIF 256 color image into 8 colors. Ordered dither was slow
enough (640x480 image took ~20 seconds to display, which, BTW, was about the
same time PC-Show took to display the same image on a 486 with a VGA card)
that I never really pursued the ED methods.

- Tim

.

Relevant Pages

  • Re: A new method for the steganography of 8 bit images
    ... > The freeware program Irfanview also uses a very good algorithm!. ... > - Then you double each value in the palette. ... > now has two neighboring entries. ... differing by one bit" to "there is data hidden in the LSB of each pixel." ...
    (sci.crypt)
  • Re: MMX speedup for Floyd Steinberg error diffusion
    ... Interesting algorithm, very serially dependent. ... I.e. the last pixel on a scan line has no down-right neighbor, ... Compute the RGB colorspace distance between the palette entry and the ... The cube size ...
    (comp.lang.asm.x86)
  • Re: Colour reduction query
    ... against your palette restrictions to select. ... ordered dithering. ... That'll look better for neighbouring blocks if you always set ... don't get visual 2 pixel lines on neighbours). ...
    (comp.graphics.algorithms)
  • 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)
  • Re: nearest colour and thanks for the palette help
    ... Theoretically you will get your algorithm run 16 times faster than iterating palette searching for minimum, practically, since jumping trough pointers is slower than iterating a table, it would be say about 8 times faster. ... If there is an 'n' here at all, it's the number of PROBE points. ...
    (comp.graphics.algorithms)