Dithering on Grids

Dithering takes an image and tries to represent it with a series of uniformly sized elements: pixels for digital images, or dots of ink for a pen plotter. I’ll assume that the background is white, and ink is black. To get an approximation of continuous gray levels, only some of the possible points will be drawn.

Square dots on a square grid

A good review of dithering techniques with square pixels can be found at libcaca’s site. To summarize:

• Thresholding: Any pixel brighter than a certain value is turned white, and any darker is black. Leads to broad swaths of black and white, and loss of detail.
• Random dithering: Threshold each pixel in the image with a different uniform random value. Leads to a noisy image, but better detail.
• Halftoning matrices: Rather than using a random variable, compare sections of the image to a structured matrix. This gives more appropriate average tones, but has strong visual artifacts such as lines or patterns.
• Error diffusion: As you march through the image, push any error from the current pixel to its unprocessed neighbors. This can be 1D or 2D, and is not limited to immediate neighbors. Many diffusion matrices have been invented, seeking to reduce artifacts.
• Model-based dithering: Assume a smoothing function to relate the binary image to the original, and tweak the binary image to reduce the error. This leads to great results, but is quite slow.

• 

• 

• 

• 

• 

• 

Round dots on a square grid

It’s hard to get a pen to draw a square dot, so let’s switch to circles. Let’s assume that we want to be able to have fully black regions, so the circle needs to cover the whole square. If the square has a width of 1 unit, the circle’s radius is 1/\sqrt{2}. When a dot is drawn, it will intrude into its neighbors’ squares with an area of (\pi/2-1)/4 . If we ignore this overlap, we’ll end up with a darker output than desired.

For the error diffusion, this means that we need to carefully calculate how much ink will be visible when drawing a new dot, and compensate for the presence of neighboring dots.

• 

• 

• 

• 

• 

• 

Round dots on a hexagonal grid

Circles fit more naturally onto a hexagonal grid. It takes similar corrections to deal with the overlaps in the hex-grid, but they’re less drastic compared to the square grid.

• 

• 

• 

• 

• 

•