hue@netcom.UUCP (Jonathan Hue) (10/12/89)
24-bit RGB to HAM is very straightforward. My first cut at this got
pretty good results (see Fish disk #196). I only came up with one more
improvement after that, which was to propagate errors in uvL rather than RGB.
First of all, you must realize that RGB is useless for measing color
differences, so you have to convert to uvL for measuring color differences.
1) Start with 24-bit data. For each pixel, figure out what is the
closest HAM pixel to that color (by Euclidean distance in uvL space).
Propagate the error using a serpentine Floyd-Steinberg dither.
2) Now, compare each HAM pixel to the original 24-bit data and find
the 256 worst differences in uvL space. Put these in a sorted array.
Next, take the 24-bit color which represents the target color where the
worst difference occurs, and put it in your color map (I usually add 8 then
shift right by 4). Draw a little sphere around this color in uvL space, and
eliminate any colors in the sorted array which lie inside this sphere. The
radius of this sphere are up to you, I made it a command line option for
experimentation. Continue, working your way down the array until your color
map is full. If you want to reserve some color map entries, do this before
you start filling the color map.
3) Now, repeat step 1, except when a color map entry is closer in uvL
space than the HAM pixel, use it instead.
Dithering N-bit data to n-bit is also straightforward. Here are a couple
functions which do 8-bit to 1-bit and 8-bit to 2-bit serpentine Floyd-Steinberg
dithering. Given these, you should be able to easily extend it to 8-bit to
4-bit dithering.
-Jonathan
(If it's not obvious, you take your pixel data, your error data, add them
together, clear the error data, and call the dither function for each row
of pixels. The result is packed into the outdata array)
------------------------------------------------------------------
/*
* F-S dither 8-bit data to 1-bit
*/
void
FSDither81(register short *indata, register short *errorTerms,
register u_char *outdata, short row, short npixels)
{
register u_char pattern;
register short i, error;
if (row & 1) /* odd, go right to left */
{
indata += npixels; /* point to last pixel */
errorTerms += npixels;
outdata += ((npixels + 7) >> 3) - 1;
if ((npixels & 0x7) == 0)
pattern = 0x01;
else
pattern = 1 << (8 - (npixels & 0x7));
for (i = 0; i < npixels; i++, indata--, errorTerms--)
{
if (*indata < 0x80)
error = *indata;
else
{
*outdata |= pattern;
error = *indata - 0xff;
}
if (error) /* propagate it */
{
*(indata - 1) += (7 * error) / 16; /* error can be neg. */
*(errorTerms + 1) += (3 * error) / 16;
*errorTerms += (5 * error) / 16;
*(errorTerms - 1) += error / 16;
}
if (pattern == 0x80)
{
pattern = 0x01; /* reset pattern, point to next output pixel */
outdata--;
}
else
pattern <<= 1;
}
}
else /* even, go left to right */
{
pattern = 0x80;
indata++;
errorTerms++;
for (i = 0; i < npixels; i++, indata++, errorTerms++)
{
if (*indata < 0x80)
error = *indata;
else
{
*outdata |= pattern;
error = *indata - 0xff;
}
if (error) /* propagate it */
{
*(indata + 1) += (7 * error) / 16; /* error can be neg. */
*(errorTerms + 1) += error / 16;
*errorTerms += (5 * error) / 16;
*(errorTerms - 1) += (3 * error) / 16;
}
if (pattern == 0x01)
{
outdata++; /* reset pattern, point to next output pixel */
pattern = 0x80;
}
else
pattern >>= 1;
}
}
}
/*
* F-S dither 8-bit data to 2-bit
*/
void
FSDither82(register short *indata, register short *errorTerms,
register u_char *outdata, short row, short npixels)
{
register u_char pattern, mask;
register short i, error;
if (row & 1) /* odd, go right to left */
{
indata += npixels; /* point to last pixel */
errorTerms += npixels;
outdata += ((npixels + 3) >> 2) - 1;
if ((npixels & 0x3) == 0)
pattern = 0x03;
else
pattern = 0x03 << (2 * (4 - (npixels & 0x3)));
for (i = 0; i < npixels; i++, indata--, errorTerms--)
{
if (*indata < 0x2b)
error = *indata;
else if (*indata < 0x80)
{
mask = 0x55;
*outdata |= mask & pattern;
error = *indata - 0x55;
}
else if (*indata < 0xd5)
{
mask = 0xaa;
*outdata |= mask & pattern;
error = *indata - 0xaa;
}
else
{
mask = 0xff;
*outdata |= mask & pattern;
error = *indata - 0xff;
}
if (error) /* propagate it */
{
*(indata - 1) += (7 * error) / 16; /* error can be neg. */
*(errorTerms + 1) += (3 * error) / 16;
*errorTerms += (5 * error) / 16;
*(errorTerms - 1) += error / 16;
}
if (pattern == 0xc0)
{
pattern = 0x03; /* reset mask, point to next output pixel */
*outdata--;
}
else
pattern <<= 2;
}
}
else /* even, go left to right */
{
pattern = 0xc0;
indata++;
errorTerms++;
for (i = 0; i < npixels; i++, indata++, errorTerms++)
{
if (*indata < 0x2b)
error = *indata;
else if (*indata < 0x80)
{
mask = 0x55;
*outdata |= mask & pattern;
error = *indata - 0x55;
}
else if (*indata < 0xd5)
{
mask = 0xaa;
*outdata |= mask & pattern;
error = *indata - 0xaa;
}
else
{
mask = 0xff;
*outdata |= mask & pattern;
error = *indata - 0xff;
}
if (error) /* propagate it */
{
*(indata + 1) += (7 * error) / 16; /* error can be neg. */
*(errorTerms + 1) += error / 16;
*errorTerms += (5 * error) / 16;
*(errorTerms - 1) += (3 * error) / 16;
}
if (pattern == 0x03)
{
outdata++; /* reset pattern, point to next output pixel */
pattern = 0xc0;
}
else
pattern >>= 2;
}
}
}