\n
![\"Plot](\"https:\/\/hackaday.com\/wp-content\/uploads\/2016\/06\/quantizatio-error.png\")
<\/a>Plot of a quantized signal and its error. (Source: Wikimedia<\/a>)<\/p>\nFor most of history, humanity\u2019s methods of visual-auditory recording and reproduction were analog, starting with methods like drawing and painting. Until fairly recently reproducing music required you to assemble skilled artists, until the arrival of analog recording and playback technologies. Then suddenly, with the rise of computer technology in the second half of the 20th century we gained the ability to not only perform analog-to-digital conversion, but also store the resulting digital format in a way that promised near-perfect reproduction.<\/p>\n
Digital optical discs and tapes found themselves competing with analog formats like the compact cassette and vinyl records. While video and photos remained analog for a long time in the form of VHS tapes and film, eventually these all gave way to the fully digital world of digital cameras, JPEGs, PNGs, DVDs and MPEG. Despite the theoretical pixel- and note-perfect reproduction of digital formats, considerations like sampling speed (Nyquist frequency<\/a>) and the aforementioned quantization errors mean a range of new headaches to address.<\/p>\n That said, the first use of dithering was actually in the 19th century, when newspapers and other printed media were looking to print phots without the hassle of having a woodcut or engraving made. This led to the invention of halftone<\/a> printing.<\/p>\n Polka Dots With early printing methods, illustrations were limited to an all-or-nothing approach with their ink coverage. This obviously meant serious limitations when it came to more detailed illustrations and photographs, until the\u00a0 arrival of the halftone printing method. First patented in 1852\u00a0 by William Fox Talbot, his approach used a special screen to break down an image into discrete points on a photographic plate. After developing this into a printing plate, these plates would then print this pattern of differently sized points.<\/p>\n Although the exact halftone printing methods were refined over the following decades, the basic principle remains the same to this day: by varying the size of the dot and the surrounding empty (white) space, the perceived brightness changes. When this method got extended to color prints with the CMYK color model, the resulting printing of these three colors as adjoining dots allowed for full-color photographs to be printed in newspapers and magazines despite having only so few ink colors available.<\/p>\n While it\u2019s also possible to do CMYK printing with blending of the inks, as in e.g. inkjet printers, this comes with some disadvantages especially when printing on thin, low-quality paper, such as that used for newspapers, as the ink saturation can cause the paper to rip and distort. This makes CMYK and monochrome dithering still a popular technique for newspapers and similar low-fidelity applications.<\/p>\n Color Palettes<\/p>\n In an ideal world, every image would have an unlimited color depth. Unfortunately we sometimes have to adapt to a narrower color space, such as when converting to the Graphics Interchange Format (GIF<\/a>), which is limited to 8 bits per pixel. This 1987-era and still very popular format thus provides an astounding 256 possible colors\u00a0 -albeit from a full 24-bit color space \u2013 which poses a bit of a challenge when using a 24-bit PNG or similar format as the source. Simply reducing the bit depth causes horrible color banding, which means that we should use dithering to ease these sharp transitions, like the very common Floyd-Steinberg dithering algorithm:<\/p>\n The Floyd-Steinberg dithering algorithm was created in 1976 by Robert W. Floyd and Louis Steinberg. Its approach to dithering is based on error diffusion<\/a>, meaning that it takes the quantization error that causes the sharp banding and distributes it across neighboring pixels. This way transitions are less abrupt, even if it means that there is noticeable image degradation (i.e. noise) compared to the original.<\/p>\n This algorithm is quite straightforward, working its way down the image one pixel at a time without affecting previously processed pixels. After obtaining the current pixel\u2019s quantization error, this is distributed across the subsequent pixels following and below the current one, as in the below pseudo code:<\/p>\n for each y from top to bottom do The implementation of the\u00a0find_closest_palette_color() function is key here, with for a greyscale image a simple round(oldpixel \/ 255) sufficing, or trunc(oldpixel + 0.5) as suggested<\/a> in this CS 559 course material from 2000 by the Universe of Wisconsin-Madison.<\/p>\n As basic as Floyd-Steinberg is, it\u2019s still commonly used today due to the good results that it gives with fairly minimal effort. Which is not to say that there aren\u2019t other dithering algorithms out there, with the Wikipedia entry on dithering<\/a> helpfully pointing out a number of alternatives, both within the same error diffusion category as well as other categories like ordered dithering<\/a>. In the case of ordered dithering there is a distinct crosshatch pattern that is both very recognizable and potentially off-putting.<\/p>\n Dithering is of course performed here to compensate for a lack of bit-depth, meaning that it will never look as good as the original image, but the less obnoxious the resulting artefacts are, the better.<\/p>\n Dithering With Audio<\/p>\n Although at first glance dithering with digital audio seems far removed from dithering the quantization error with images, the same principles apply here. When for example the original recording has to be downsampled to CD-quality (i.e. 16-bit) audio, we can either round or truncate the original samples to get the desired sample size, but we\u2019d get distortion in either case. This distortion is highly noticeable by the human ear as the quantization errors create new frequencies and harmonics, this is quite noticeable in the 16- to 6-bit downsampling examples provided in the Wikipedia entry<\/a>.<\/p>\n In the sample with dithering, there is clearly noise audible, but the original signal (a sine wave) now sounds pretty close to the original signal. This is done through the adding of random noise to each sample by randomly rounding up or down and counting on the average. Although random noise is clearly audible in the final result, it\u2019s significantly better than the undithered version.<\/p>\n Random noise distribution is also possible with images, but more refined methods tend to give better results. For audio processing there are alternative noise distributions and noise shaping approaches.<\/p>\n Regardless of which dither method is being applied, it remains fascinating how the humble printing press and quantization errors have led to so many different ways to trick the human eye and ear into accepting lower fidelity content. As many of the technical limitations that existed during the time of their conception \u2013 such as expensive storage and low bandwidth \u2013 have now mostly vanished, it will be interesting to see how dithering usage evolves over the coming years and decades.<\/p>\n
\n![\"Left:](\"https:\/\/commons.wikimedia.org\/wiki\/File:Quanterr.png\")
<\/a>Left: halftone dot pattern with increasing size downwards, Right: how the human eye would see this, when viewed from a sufficient distance. (Source: Wikimedia<\/a>)<\/p>\n<\/a>From left to right: original image. Converted to web safe color. Web safe with Floyd-Steinberg dithering. (Source: Wikipedia<\/a>)<\/p>\n
\n for each x from left to right do
\n oldpixel\u00a0:= pixels[x][y]
\n newpixel\u00a0:= find_closest_palette_color(oldpixel)
\n pixels[x][y]\u00a0:= newpixel
\n quant_error\u00a0:= oldpixel – newpixel
\n pixels[x + 1][y ]\u00a0:= pixels[x + 1][y ] + quant_error \u00d7 7 \/ 16
\n pixels[x – 1][y + 1]\u00a0:= pixels[x – 1][y + 1] + quant_error \u00d7 3 \/ 16
\n pixels[x ][y + 1]\u00a0:= pixels[x ][y + 1] + quant_error \u00d7 5 \/ 16
\n pixels[x + 1][y + 1]\u00a0:= pixels[x + 1][y + 1] + quant_error \u00d7 1 \/ 16<\/p>\n