From: Adrian McMenamin
>With dithering off a quantized image is delivered reasonably quickly - in
>a real world application I have it will deliver 30 of these (each in the
>10 - 20k range quantized to 256 colours) in 20 seconds or so on a fairly
>BOG standard webserver.
Ok, that's a base speed for quantization (about 1 image/second).
>The image is quantized using the median cut algorithm.
Ok, but this isn't a quantization algorithm, it just finds a (maybe)
suitable palette. It also has the property that it may generate a palette
which does not itself span all the colors in the image. If you use (say)
the center color of each of the median cut boxes in the RGB cube for the
palette then some of the colors in the image will be outside the bounding
box of the palette within the RGB cube.
That doesn't matter for simple mapping, where you take each original image
pixel and replace it with the color/palette entry selected for the box it is
within. It does matter (a lot) for the implementation of Floyd Steinberg -
colors outside the bounding box (the gamut) of the palette will produce
errors which never converge.
>But with dithering turned on it become ridiculously slow.
You didn't explain how you actually select the colors when dithering is
*not* on - you have a palette from the median cut algorithm, but then, for
each image pixel, you have to find which entry to use. This is where the
time goes. I think you are just using the box/bin in which the color falls
(step 2 in your dithering algorithm) - that is certainly faster than the
(higher quality) alternatives I know.
When dithering is switched on the colors in the original image are modified
by the errors, but this is fast (for pretty much any dithering algorithm).
The time still goes in locating the appropriate entry in the palette.
>Obviously I have picked the wrong algorithm or else mis-applied it - this
>is what it does (errors are distributed via Floyd-Steinberg):
Right, this is the quantization algorithm:
>1. Take a point that has been modified with errors and see if it fits in
>any of the median cut boxes
>2. If it fits, then use the palette entry for that box for output, go to 5
I'm guessing that, in your no-dither case you just have steps (1,2) - the
color does always fit because it is always in the range RGB(0,0,0) to
RGB(255,255,255) and the median cut boxes span the whole RGB cube. In
practice this algorithm fails to select the closest color in many (most?)
cases, but it selects one of the 8 closest (I think) so it's fine.
What you should do, for the dither case, is *at least* truncate the dithered
RGB values to the RGB cube - i.e. limit component values less than 0 to 0
and those greater than 1 to 1. Then you will have much the same speed in
the dithered case to the undithered case - you don't need the remaining
If you want to be more sophisticated limit the dithered colors to the true
gamut of the *palette* - RGB(minR,minG,minB) RGB(maxR,maxG,maxB) - that's
still far from perfect but I believe Floyd-Steinberg behaves much better if
this is done. (Sorry, I can't prove or demonstrate that assertion.)
>3. If it doesn't, calculate the distance (as a sum of squares) of the
>modified point to all existing palette entries
>4. select the closest match for output
In fact this is what I have done in the past for *any* palette - regardless
of whether the colors are dithered or not. It selects closer colors than
simply finding the bin the color is in if the bins are different in size.
Think of it in 1 dimension. An entry right at the edge of a larger bin will
be closer to the center of the adjacent smaller bin than it is to the center
of its own bin. I also force the colors in the outer bins to be on the
edges of the RGB cube. This guarantees that errors eventually converge.
Still, it is *really* slow. One approach I've used is a 4096 entry table
(top four bits of r,g,b input color) to cache the discovered palette entry.
So, take every color and modify it by replicating the top four bits of each
component in the lower bits - reduce the color component precision to just 4
bits. Do Heckbert (getting 256 colors out of the up to 4096 distinct colors
in the original image). Map the image (with Floyd-Steinberg or an ordered
dither - it doesn't matter) and just do the closest-palette-entry
measurements on demand.
You will find this is still very slow ;-) BTW, Windows NT (late '90s) used
to use a 32k (5 bit RGB) lookup table for this (COLORONCOLOR mapping IRC),
it was computed once and stored with the DC palette. Once you have the LUT
you really don't want to lose it ;-)
John Bowler <jbowler@...>