ordered dithering

i think dithering is pretty neat and i'd like to talk about it for no reason so here we go

introduction goes here

what is ordered dither

unlike error-diffusion dithering algorithms, each pixel is processed independently in an ordered dither based on position and the original value (brightness) of the pixel. each pixel is colored white if it is above a certain threshold and black otherwise, but the threshold varies from pixel to pixel in a repeating pattern such that e.g. 50% of pixels would be colored white when the initial pixel had a value of 50%. it is also necessary to make sure pixels with similar thresholds are spaced far apart so that patterns don't have visible contiguous groups of pixels.

creating an ordered dither

how can we make an ordered dither? it may be easiest to start by thinking about how we could dither solid colors. there are two important points to dithering solid colors:

• we want to keep white pixels as evenly-spaced as possible so that the dithered image looks the same color throughout.
• because of how the thresholds work, you can get from the dithered version of one solid color to the dithered version of another only by adding white pixels. the threshold value for any given pixel is then the lightest color for which the pixel is still black.

in this way we can figure out the threshold value for every pixel in the pattern. we start with black and then gradually increase the value by coloring one pixel white at a time; the first pixel we color white has the lowest threshold (0), the second pixel has the second lowest (1/n, where n is the number of pixels in the pattern), etc.

we will demonstrate this method with a 4x4 dither one step at a time, and then show the result of applying this to an 8x8 pattern.

4x4 ordered dither

we start with black. you can probably guess what the dither looks like.

for the next color, we add one white pixel to the pattern. because the pattern loops, it doesn't really matter where--we'll use the top left pixel because it'll make things work out nicer later.

for the next color, we add another white pixel. we have to keep the dithered resut looking as even as possible, so we choose the pixel that's farthest away from the first white pixel (taking looping into account).

there are two options for this one--the third pixel down on the left, or the third pixel right on the top. we'll arbitrarily choose the latter.

next we do the other one.

next we'll fill in the pixels diagonally adjacent to the ones we've just filled in--filling in orthogonally adjacent pixels would make the dither look less even. we'll start again with the top-leftmost one.

then it's the bottom-right one, as before. filling in the top-right or bottom-left one would make one half of the pattern look brighter than the other and the dither would look less even.

again we have to arbitrarily decide between the top-right and the bottom-left, and again we'll fill in the top right pixel first.

and then the other one.

next we can either fill in the four pixels in the top-right corners of their respective quadrants or the pixels in the bottom-left corners. take a guess which one we do first.

this sort of recursive structure is important to note. you can think of the 4x4 dither as divided into four quadrants. we always color the same pixel in each quadrant one after the other, in the order of top left, then bottom right, then top right, then bottom left. this is the same as the order in which we color the pixels in each quadrant. this may become clearer after looking at the 8x8 dither patterns.

the rest goes about how you'd expect.

while it isn't particularly relevant, it is interesting to note that the dither patterns for lighter colors are the same as the dither patterns for darker colors, but vertically mirrored and with colors inverted.

8x8 ordered dither

i won't go into too much detail on this because the post would be eternal otherwise. just try anad look for patterns and see how the things we talked about earlier apply here.