A Description of Using Error Diffusion for Graphics
By Joshua Cantrell
last updated: 12-19-97
As computers become faster at displaying graphics, pixels that use
16 bits and 24 bits are becoming more frequently found in games and
other multimedia programs. The side effect is that computers which
cannot handle these greater pixel sizes are unable to run the programs.
Although too slow for real-time applications, dithering is one way
to allow graphics with a greater numbers of colors to be displayed on
machines with fewer colors.
A rather simple method of dithering that seems to work well for
converting graphics from one palette to that of another is
error diffusion. A rough explanation about how error diffusion
works is that it takes the red, green, and blue values from
the original pixel, finds the best matching pixel in the goal palette,
which is stored into the new graphic, then it finds the difference
of the original and final pixel's red, green, and blue values,
and adds a fraction of this value to the near by pixels in the
orignal graphic. If you know how the Bresenham's line algorithm
works, this is similarly trying to balance the red, green, and
blue components to make the result look as convincing as possible.
A more step by step way to explain the algorithm is by the following:
1) Choose a starting place in the graphic (a really good starting place
is one of the corners, of which I choose the upper left because x
usually increases right and y usually increases down).
2) Get the red, green, and blue values of the pixel in the original
graphic's palette for the starting pixel.
Let REDi = Red value of the original pixel.
Let GREENi = Green value of the original pixel.
Let BLUEi = Blue value of the original pixel.
3) Find the closest matching pixel in the final graphic's palette
and display it in the final graphic.
4) Get the red, green, and blue values of the pixel in the final
graphic's palette for the pixel used in the final graphic.
Let REDf = Red value of the final pixel.
Let GREENf = Green value of the final pixel.
Let BLUEf = Blue value of the final pixel.
5) Find the differences between the original pixel's and the final
pixel's color components.
Let REDd = REDi - REDf.
Let GREENd = GREENi - GREENf.
Let BLUEd = BLUEi - BLUEf.
6) Distribute a fraction of the difference to the surrounding pixels that
do not have a final pixel assigned to them. (I've seen where the
fractions do not add to 100% before, but I don't see where a loss of
information can make a good picture.)
7) Move to the next pixel in the orginal picture to process (I choose
to move right because that is usually the direction of increasing x).
8) Get the red, green, and blue values of the pixel in the original
graphic's palette for the pixel.
Let REDi = Red value of the original pixel.
Let GREENi = Green value of the original pixel.
Let BLUEi = Blue value of the original pixel.
9) Go to step 3 and repeat until the final graphic has been completely
drawn.
As an aside, one of the easiest methods of finding color matches is to
treat 8 bit pixels (or 4 bit pixels for that matter) like 16 bit and
24 bit pixels are treated. If you can modify their palettes so that
a given number of bits in the pixel represents a color component's value,
then matching colors is easy. 24 bit pixels have eight bits per color
component (8-8-8). 16 bit pixels have five bits for the red and blue color
components and six bits for the green color component (5-6-5) or five bits
for each color component (5-5-5). One way to organize an 8 bit pixel would
be three bits for red and green, and two bits for blue (3-3-2).
joshuacantrell@yahoo.com
(My Home Page)
- (My Computer Science Page)
- (My Personal Page)
- (My Resume)