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.

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.

5) Find the differences between the original pixel's and the final pixel's color components.

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.

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)