Ordered dither with custom palette?

[Jim Leonard]

I've scoured google's archives of usenet, the c.g.a FAQ, and Graphics
Gems I through V and I just can't find an answer to this problem --
hopefully one of the kind souls here can help...

Photoshop 7 (and possibly other versions as well) features a method of
color reduction where you can load a custom palette, then perform an
ordered dither against that palette. This is a neat trick, as I
always assumed that ordered dithering required an ordered palette (2
r,g,b levels per channel = 8 colors, 3^3 = 27 colors, 4^3 = 64 colors,
etc.).

I have a need to do this in my own software (using classic Bayer
crosshatch), and although I understand bitonal ordered dithers, I am
completely at a loss as to how Photoshop is able to do an
ordered/Bayer dither against a completely arbitrary palette. I
thought that maybe PS was performing an ordered dither with an ordered
palette equal to or greater than the specified number of colors and
then remapping to the custom palette with a best match, but when I
perform those steps myself the result is not nearly as good as the
original "custom" ordered dither.

Can anyone shed some light on how to do this? It's driving me nuts!
Is it a basic property of ordered dithering in color that I am
missing? (I have only implemented B&W ordered dithering up until
now.) The examples in Graphics Gems II assume an ordered palette and
the code in ppmdither.c builds its own semi-ordered palette with LUTs;
unless I'm confused, neither of these explain what I'm looking for.

Thanks in advance for anyone who can help straighten me out.

[Marco Schmidt]

Post by Jim Leonard
Photoshop 7 (and possibly other versions as well) features a method of
color reduction where you can load a custom palette, then perform an
ordered dither against that palette. This is a neat trick, as I
always assumed that ordered dithering required an ordered palette (2
r,g,b levels per channel = 8 colors, 3^3 = 27 colors, 4^3 = 64 colors,
etc.).

You can change the number of levels for each channel (I use 4 for blue
and 8 for each red and green to make full use of 256 entries), but
other than that, I have no idea how it could work with an arbitrary
palette. But I'm curious!

Regards,
Marco

[Lord Crc]

On Mon, 09 Feb 2004 22:43:38 +0100, Marco Schmidt

Post by Jim Leonard
This is a neat trick, as I

Post by Jim Leonard
always assumed that ordered dithering required an ordered palette

Perhaps they do the dither step using an "ideal" palette and once the
wanted color is computed, they look up the closest one?

Wild guess...

- Asbjørn

[Jim Leonard]

Post by Lord Crc
Perhaps they do the dither step using an "ideal" palette and once the
wanted color is computed, they look up the closest one?

No, as I wrote in my original post, I tried this and got different (worse) results.

Anyone have any ideas?

[*PaN!*]

"Jim Leonard" <***@despammed.com> ha scritto nel messaggio news:***@posting.google.com...

Hi Trixter,

I'll try.
Maybe, given a pixel colour (reference) they compute the two (or three?)
nearest colours in the palette and then apply an ordered dither using those
as basis, using the distance between those colours and the reference colour
to compute weights of those colours.
A more clear edition (or a refutation) of this post might happen tomorrow,
when I'm less sleepy =)

--*PaN!*

Post by Jim Leonard
I've scoured google's archives of usenet, the c.g.a FAQ, and Graphics
Gems I through V and I just can't find an answer to this problem --
hopefully one of the kind souls here can help...
Photoshop 7 (and possibly other versions as well) features a method of
color reduction where you can load a custom palette, then perform an
ordered dither against that palette. This is a neat trick, as I
always assumed that ordered dithering required an ordered palette (2
r,g,b levels per channel = 8 colors, 3^3 = 27 colors, 4^3 = 64 colors,
etc.).
I have a need to do this in my own software (using classic Bayer
crosshatch), and although I understand bitonal ordered dithers, I am
completely at a loss as to how Photoshop is able to do an
ordered/Bayer dither against a completely arbitrary palette. I
thought that maybe PS was performing an ordered dither with an ordered
palette equal to or greater than the specified number of colors and
then remapping to the custom palette with a best match, but when I
perform those steps myself the result is not nearly as good as the
original "custom" ordered dither.
Can anyone shed some light on how to do this? It's driving me nuts!
Is it a basic property of ordered dithering in color that I am
missing? (I have only implemented B&W ordered dithering up until
now.) The examples in Graphics Gems II assume an ordered palette and
the code in ppmdither.c builds its own semi-ordered palette with LUTs;
unless I'm confused, neither of these explain what I'm looking for.
Thanks in advance for anyone who can help straighten me out.

[Severian]

Post by Jim Leonard
I've scoured google's archives of usenet, the c.g.a FAQ, and Graphics
Gems I through V and I just can't find an answer to this problem --
hopefully one of the kind souls here can help...
Photoshop 7 (and possibly other versions as well) features a method of
color reduction where you can load a custom palette, then perform an
ordered dither against that palette. This is a neat trick, as I
always assumed that ordered dithering required an ordered palette (2
r,g,b levels per channel = 8 colors, 3^3 = 27 colors, 4^3 = 64 colors,
etc.).
I have a need to do this in my own software (using classic Bayer
crosshatch), and although I understand bitonal ordered dithers, I am
completely at a loss as to how Photoshop is able to do an
ordered/Bayer dither against a completely arbitrary palette. I
thought that maybe PS was performing an ordered dither with an ordered
palette equal to or greater than the specified number of colors and
then remapping to the custom palette with a best match, but when I
perform those steps myself the result is not nearly as good as the
original "custom" ordered dither.
Can anyone shed some light on how to do this? It's driving me nuts!
Is it a basic property of ordered dithering in color that I am
missing? (I have only implemented B&W ordered dithering up until
now.) The examples in Graphics Gems II assume an ordered palette and
the code in ppmdither.c builds its own semi-ordered palette with LUTs;
unless I'm confused, neither of these explain what I'm looking for.
Thanks in advance for anyone who can help straighten me out.

Do you see some advantage doing an ordered (patterned) dither, rather
than diffusion (Floyd-Steinburg, Stucki, etc.)?

Like you, I've only coded an ordered dither when converting to
bi-level images.

[Jim Leonard]

Post by Severian
Do you see some advantage doing an ordered (patterned) dither, rather
than diffusion (Floyd-Steinburg, Stucki, etc.)?

Depending on the source material's application, yes. For example, I
think we all agree that still photos look best when dithered with
error diffusion, but the particular source material I am working with
is flat cell animation. (Think "The Simpsons", etc.) With such
material, error diffusion results in a different "texture" for
flat-shaded areas every frame, which results in "texture swim" during
the course of the animation. Ordered dithering is preferable, since
it does not suffer from this artifact and produces a more stable
"texture" over time. (A side benefit is that the dithered output is
still applicable for compression, since there are still limited deltas
over time.)

Hence my question: I am trying to (ordered) dither cell animation to
a fixed 16-color palette I have no control over. (In case you're
wondering, it's nearly identical to the old CGA 16-color text mode
palette :-). As previously stated, I attempted to do an ordered
dither to a 3^3 palette (27 colors) and remap to 16 but the results
were nowhere near that of the now-magical-in-my-mind Photoshop
arbitrary palette ordered dither that I am trying to code myself. Any
futher suggestions on how this is done is appreciated!

[Jarno A Wuolijoki]

Post by Jim Leonard

Post by Severian
Do you see some advantage doing an ordered (patterned) dither, rather
than diffusion (Floyd-Steinburg, Stucki, etc.)?

Depending on the source material's application, yes. For example, I
think we all agree that still photos look best when dithered with
error diffusion, but the particular source material I am working with
is flat cell animation. (Think "The Simpsons", etc.) With such
material, error diffusion results in a different "texture" for
flat-shaded areas every frame, which results in "texture swim" during
the course of the animation. Ordered dithering is preferable, since
it does not suffer from this artifact and produces a more stable
"texture" over time. (A side benefit is that the dithered output is
still applicable for compression, since there are still limited deltas
over time.)

Wild idea: do 3d-error diffusion but flip the effect somehow in time
dimension so that it favours leaving the pixels intact instead of
changing them. (never tried - might not work)

Post by Jim Leonard
Hence my question: I am trying to (ordered) dither cell animation to
a fixed 16-color palette I have no control over. (In case you're
wondering, it's nearly identical to the old CGA 16-color text mode
palette :-). As previously stated, I attempted to do an ordered
dither to a 3^3 palette (27 colors) and remap to 16 but the results
were nowhere near that of the now-magical-in-my-mind Photoshop
arbitrary palette ordered dither that I am trying to code myself. Any
futher suggestions on how this is done is appreciated!

Hmm.. I'd try dividing the colourspace into tetrahedrons, picking the
right tetrahedron for each pixel and then blending its vertices together.
Your palette isn't probably the easiest one for this though..

[Hans-Bernhard Broeker]

Post by Jim Leonard
Photoshop 7 (and possibly other versions as well) features a method of
color reduction where you can load a custom palette, then perform an
ordered dither against that palette. This is a neat trick, as I
always assumed that ordered dithering required an ordered palette (2
r,g,b levels per channel = 8 colors, 3^3 = 27 colors, 4^3 = 64 colors,
etc.).

Dithering is equivalent to disturbing all input colours by a small
amount before finding the nearest colour in the palette. The
difference between dithering algorithms is in how the disturbances are
calculated.

Ordered dither calculates the shifts from the position of the pixel,
so it's relatively simple to do this even with an arbitrary palette.

[Jim Leonard]

Post by Hans-Bernhard Broeker
Dithering is equivalent to disturbing all input colours by a small
amount before finding the nearest colour in the palette. The
difference between dithering algorithms is in how the disturbances are
calculated.
Ordered dither calculates the shifts from the position of the pixel,
so it's relatively simple to do this even with an arbitrary palette.

Could you explain a little further? It may be relatively simple for
you, but I can't seem to wrap my brain around the concept. :-( For
example, I fully understand bi-tonal ordered dithering: You have a
matrix that you compare against every pixel, and if the source pixel
is above the threshhold in the matrix, you plot the pixel. Simple
enough -- but how does ordered dithering work when given color,
especially a pre-computed, non-ordered palette?

[Hans-Bernhard Broeker]

Post by Jim Leonard

Post by Hans-Bernhard Broeker
Dithering is equivalent to disturbing all input colours by a small
amount before finding the nearest colour in the palette. The
difference between dithering algorithms is in how the disturbances are
calculated.
Ordered dither calculates the shifts from the position of the pixel,
so it's relatively simple to do this even with an arbitrary palette.

Could you explain a little further? It may be relatively simple for
you, but I can't seem to wrap my brain around the concept. :-( For

Well, let's say, you know one implementation of it, but haven't fully
grasped the concept of dithering on a more general scale yet.

Post by Jim Leonard
You have a matrix that you compare against every pixel, and if the
source pixel is above the threshhold in the matrix, you plot the
pixel.

Imagine you take your input pixel, subtract the threshold value chosen
from the matrix, add back 50 percent gray, and see if the result is
closer to black or closer to white. If you look at this process
closely, you'll notice it gives the same results you got from your
thresholding process, but it's expressed in a different way. Your
method applies the local variation to the threshold, I apply it to the
data itself.

The benefit of doing it that way is that the dithering step is
completely decoupled from the palette matching. Effectively, I just
add noise to the input image, then run whatever simple palette
matching algorithm you want. Picking the nearest neighbor in 3D RGB
colourspace should do for a start.

[Jim Leonard]

Post by Hans-Bernhard Broeker
Imagine you take your input pixel, subtract the threshold value chosen
from the matrix, add back 50 percent gray, and see if the result is
closer to black or closer to white. If you look at this process
closely, you'll notice it gives the same results you got from your
thresholding process, but it's expressed in a different way. Your
method applies the local variation to the threshold, I apply it to the
data itself.
The benefit of doing it that way is that the dithering step is
completely decoupled from the palette matching. Effectively, I just
add noise to the input image, then run whatever simple palette
matching algorithm you want. Picking the nearest neighbor in 3D RGB
colourspace should do for a start.

If I'm understanding you correctly, you perturb the source image by
the dither pattern in each of its channels, then you remap to the
fixed palette? That doesn't produce the same results as I did in
Photoshop (see first post)... Even if I did that, how would I get it
to 16 levels? 2-3-2 is 12 levels and 2-3-3 is 18; one method doesn't
use enough colors, the other uses too much...?

[Hans-Bernhard Broeker]

Post by Jim Leonard
If I'm understanding you correctly, you perturb the source image by
the dither pattern in each of its channels, then you remap to the
fixed palette? That doesn't produce the same results as I did in
Photoshop (see first post)... Even if I did that, how would I get it
to 16 levels? 2-3-2 is 12 levels and 2-3-3 is 18; one method doesn't
use enough colors, the other uses too much...?

There are no "levels" involved at all --- you should just use the
fixed palette you've been given, as it is. For each perturbed input
pixel, find the colour in that palette closest to it. The quality of
the result will depend on the given palette, in particular on how
evenly distributed it is over colour space. But if that's the palette
you've been forced to use, there's not really all that much you can do
about that. Not if you want to stick with ordered dithering, that is.

[Jim Leonard]

Post by Hans-Bernhard Broeker

Post by Jim Leonard
If I'm understanding you correctly, you perturb the source image by
the dither pattern in each of its channels, then you remap to the
fixed palette? That doesn't produce the same results as I did in
Photoshop (see first post)... Even if I did that, how would I get it
to 16 levels? 2-3-2 is 12 levels and 2-3-3 is 18; one method doesn't
use enough colors, the other uses too much...?

There are no "levels" involved at all --- you should just use the
fixed palette you've been given, as it is. For each perturbed input
pixel, find the colour in that palette closest to it. The quality of
the result will depend on the given palette, in particular on how
evenly distributed it is over colour space. But if that's the palette
you've been forced to use, there's not really all that much you can do
about that. Not if you want to stick with ordered dithering, that is.

That part I understand. Okay then, how do I perturb the original
surface using something other than bitonal levels? Meaning, I know I
can always apply the dither matrix to each red, green, and blue
channel, but assuming I treat each as bitonal, I end up with 8 colors
(2 levels for red, green, blue). How does one apply ordered dithering
using anything other than a threshold?

[Hans-Bernhard Broeker]

Post by Jim Leonard
That part I understand. Okay then, how do I perturb the original
surface using something other than bitonal levels?

There's no "surface" involved in this, either.

Post by Jim Leonard
Meaning, I know I can always apply the dither matrix to each red,
green, and blue channel, but assuming I treat each as bitonal, I end
up with 8 colors (2 levels for red, green, blue).

That's nowhere near what I've been describing here.

Post by Jim Leonard
How does one apply ordered dithering using anything other than a
threshold?

What I've been trying to tell you all this time is that the threshold
has nothing to do with the dithering, at least not necessarily. It's
a separate process. The process I'm talking about works like this,
algorithmically (using RGB as the colour space, which isn't exactly
optimal...)

for (each pixel in the image (position [x,y], colour C)
for c = R,G,B
new_col.c = C.c + dither_function(x,y)
for each colour in palette, P[i]
compute distance of colours P[i] and new_col
if it's smaller than the minimum found so far, update minimum
output_image[x,y] := minimum

The bitonal dithering you know can be described in this scheme, if you
define

dither_function(x,y) := your_dither_matrix(x,y) - 0.5
palette := {black, white}

You may want to use separate dithering matrices (or at least shift
them relative to each other) for each RGB channel.

With only two colours in the palette, finding the nearest neighbour
becomes equivalent to setting a threshold at 50% gray. If you use all
8 "major" colours {b,w,r,g,b,c,m,y}, you'll get what you outlined
above. But the algorithm isn't restricted to those cases --- it can
handle literally *any* set of palette colours.

If you want an output with a spatial resolution higher or lower than
the input, rescale the input before you apply the above. You'll need
that if you don't want to lose a lot of colour resolution --- you'll
be trading spatial resolution for colours.

[Gernot Hoffmann]

Post by Jim Leonard
I've scoured google's archives of usenet, the c.g.a FAQ, and Graphics
Gems I through V and I just can't find an answer to this problem --
hopefully one of the kind souls here can help...
Photoshop 7 (and possibly other versions as well) features a method of
color reduction where you can load a custom palette, then perform an
ordered dither against that palette. This is a neat trick, as I
always assumed that ordered dithering required an ordered palette (2
r,g,b levels per channel = 8 colors, 3^3 = 27 colors, 4^3 = 64 colors,
etc.).
I have a need to do this in my own software (using classic Bayer
crosshatch), and although I understand bitonal ordered dithers, I am
completely at a loss as to how Photoshop is able to do an
ordered/Bayer dither against a completely arbitrary palette. I
thought that maybe PS was performing an ordered dither with an ordered
palette equal to or greater than the specified number of colors and
then remapping to the custom palette with a best match, but when I
perform those steps myself the result is not nearly as good as the
original "custom" ordered dither.
Can anyone shed some light on how to do this? It's driving me nuts!
Is it a basic property of ordered dithering in color that I am
missing? (I have only implemented B&W ordered dithering up until
now.) The examples in Graphics Gems II assume an ordered palette and
the code in ppmdither.c builds its own semi-ordered palette with LUTs;
unless I'm confused, neither of these explain what I'm looking for.
Thanks in advance for anyone who can help straighten me out.

Jim,

perhaps it helps to distinguish between TWO kinds of dithering:

1. Find the best in-place substitute for each pixel by replacing its
color by one of the palette colors.
This is color quantization, if the palette is found by "condensing"
all colors to N clusters in the RGB space.
If the palette is already predefined, then it´s not simple. Just
taking the nearest neighbour is not sufficient because the error
has to be distributed to the next pixels, or in an area.
In-place Floyd-Steinberg can do this for bilevel or multilevel
dithering, provided the palette consists of equally divided colors,
like R=0/128/255 for trilevel. Maybe the FS algorithm can be modi-
fied.

2. Find the representation of an image area by using a few colors in
a device space. The device space is defined e.g. for a printer.
A raster cell contains e.g. 100x100 device pixels. Inside the
raster cell are whole image pixels or fragments of them (at least
1.5..2 image pixels for the raster cell width), virtually mapped
onto the paper.
Here we use either spot functions or threshold arrays.
The Bayer raster cell is a dispersed ordered dither cell with
optimized threshold array.
For a source image with few CHANNELS like RGB or CMYK we apply the
dithering to each channel, especially for multicolor printing,
CMYK or Hexachrome - one plate for each channel.

If we apply the raster cell to a source image in order to create
a destination image with in-place substitution, then we see imme-
diately that it isn´t possible to re-combine the fictitious plates
for an RGB image - the sum of all plates delivers colors which are
not in the palette.

IMO, it turns out that Dithering Type 2 doesn´t have much to do with
Dithering Type 1. Essentially because Type 2 replaces the source image
spatially by much higher resolution.

Best regards --Gernot Hoffmann

[Jim Leonard]

Post by Gernot Hoffmann
1. Find the best in-place substitute for each pixel by replacing its
color by one of the palette colors.
This is color quantization, if the palette is found by "condensing"
all colors to N clusters in the RGB space.
If the palette is already predefined, then it´s not simple. Just
taking the nearest neighbour is not sufficient because the error
has to be distributed to the next pixels, or in an area.
In-place Floyd-Steinberg can do this for bilevel or multilevel
dithering, provided the palette consists of equally divided colors,
like R=0/128/255 for trilevel. Maybe the FS algorithm can be modi-
fied.
2. Find the representation of an image area by using a few colors in
a device space. The device space is defined e.g. for a printer.
A raster cell contains e.g. 100x100 device pixels. Inside the
raster cell are whole image pixels or fragments of them (at least
1.5..2 image pixels for the raster cell width), virtually mapped
onto the paper.
Here we use either spot functions or threshold arrays.
The Bayer raster cell is a dispersed ordered dither cell with
optimized threshold array.
For a source image with few CHANNELS like RGB or CMYK we apply the
dithering to each channel, especially for multicolor printing,
CMYK or Hexachrome - one plate for each channel.
If we apply the raster cell to a source image in order to create
a destination image with in-place substitution, then we see imme-
diately that it isn´t possible to re-combine the fictitious plates
for an RGB image - the sum of all plates delivers colors which are
not in the palette.
IMO, it turns out that Dithering Type 2 doesn´t have much to do with
Dithering Type 1. Essentially because Type 2 replaces the source image
spatially by much higher resolution.

I understand both of these concepts but, as you described them, each
applies to palettes of equally-divided colors. So the question
remains: How do I perform ordered dithering using a palette where the
colors are not equally divided?

Hans-Bernhard earlier stated that you just apply the thresholding to
the original image, then remap the perturbed image to your palette.
But you can't divide 16 (palette size) by 3 (number of channels)
integrally so I can't see how this will produce the same results...

Help; what am I missing?