Stop dithering and start dithering
June 10, 2016 11:04 PM Subscribe
And a fun little iPhone/iPad app that takes classic Mac dithered photos!
posted by qwip at 1:21 AM on June 11, 2016 [7 favorites]
posted by qwip at 1:21 AM on June 11, 2016 [7 favorites]
This, from the Wikipedia link, was very interesting:
…[O]ne of the earliest [applications] of dither came in World War II. Airplane bombers used mechanical computers to perform navigation and bomb trajectory calculations. Curiously, these computers (boxes filled with hundreds of gears and cogs) performed more accurately when flying on board the aircraft, and less well on ground. Engineers realized that the vibration from the aircraft reduced the error from sticky moving parts. Instead of moving in short jerks, they moved more continuously. Small vibrating motors were built into the computers, and their vibration was called dither from the Middle English verb "didderen," meaning "to tremble."
posted by Termite at 1:40 AM on June 11, 2016 [27 favorites]
…[O]ne of the earliest [applications] of dither came in World War II. Airplane bombers used mechanical computers to perform navigation and bomb trajectory calculations. Curiously, these computers (boxes filled with hundreds of gears and cogs) performed more accurately when flying on board the aircraft, and less well on ground. Engineers realized that the vibration from the aircraft reduced the error from sticky moving parts. Instead of moving in short jerks, they moved more continuously. Small vibrating motors were built into the computers, and their vibration was called dither from the Middle English verb "didderen," meaning "to tremble."
posted by Termite at 1:40 AM on June 11, 2016 [27 favorites]
I still remember writing code to dither 24 bit images to the 16 bit Mac LC screen for a CD-ROM app. The end result was pretty cool - you couldn't really see the dithering, and it removed the artifacts like banded blue skies. I wrote the code totally based on the algorithm in the original Floyd-Steinberg paper, which is very concise and clear.
posted by w0mbat at 1:58 AM on June 11, 2016 [5 favorites]
posted by w0mbat at 1:58 AM on June 11, 2016 [5 favorites]
So now I have eleven algorithms to choose between. This is supposed to help me with my dithering?
posted by iotic at 3:42 AM on June 11, 2016 [23 favorites]
posted by iotic at 3:42 AM on June 11, 2016 [23 favorites]
iotic - just be glad he left out noise dither, the weirdest looking but one of the easiest to code.
You use the value of the original pixel to set the odds of the output pixel being one quantized value or another.
E.G. for each pixel you pick a random float between 0 and 1, then if the original pixel is 75% white for example, you output white if the random number is ≤ 0.75.
The look never really caught on though. It's described here, among other stuff .
posted by w0mbat at 4:13 AM on June 11, 2016 [4 favorites]
You use the value of the original pixel to set the odds of the output pixel being one quantized value or another.
E.G. for each pixel you pick a random float between 0 and 1, then if the original pixel is 75% white for example, you output white if the random number is ≤ 0.75.
The look never really caught on though. It's described here, among other stuff .
posted by w0mbat at 4:13 AM on June 11, 2016 [4 favorites]
Yeah, interesting. Noise dither is more common for audio though, I think? There's some nice features, like you can filter the noise so it's mostly in inaudible frequency ranges. I tend to think of dithering as being noise-based, so it's good to see it analysed as more "static" error diffusion.
posted by iotic at 5:00 AM on June 11, 2016
posted by iotic at 5:00 AM on June 11, 2016
I see from reading your link the same principle applies for graphics. Though I guess the equivalent idea of filtering the noise to be invisible only really gets legs at retina resolutions.
posted by iotic at 5:03 AM on June 11, 2016
posted by iotic at 5:03 AM on June 11, 2016
Needs moar halftoning, because who doesn't need their continuous tone photos broken up into circular blobs?
I like the effects from the blisteringly computationally expensive Voronoi stippling used by StippleGen 2 and the saliences.com : Weighted Voronoi Stippling tool.
posted by scruss at 7:16 AM on June 11, 2016 [4 favorites]
I like the effects from the blisteringly computationally expensive Voronoi stippling used by StippleGen 2 and the saliences.com : Weighted Voronoi Stippling tool.
posted by scruss at 7:16 AM on June 11, 2016 [4 favorites]
I came across this page a year or so ago, and really liked it. My only complaint is that serpentine ordering is only mentioned as an afterthought, whereas in my opinion it's actually a bare minimum to get any of these dithering algorithms to look even half-way good.
posted by L.P. Hatecraft at 7:27 AM on June 11, 2016
posted by L.P. Hatecraft at 7:27 AM on June 11, 2016
I took a class in digital imaging back in 1999 and was amazed at how much science there was behind dithering. Particularly for what is ultimately (hopefully) a somewhat irrelevant need, as display resolutions and color fidelity improve. My final project was treating ASCII art as a form of dithering. Unfortunately my output medium was 300 dpi Postscript printers, so it's not really web friendly. But the results were remarkably good!
posted by Nelson at 8:28 AM on June 11, 2016 [3 favorites]
posted by Nelson at 8:28 AM on June 11, 2016 [3 favorites]
Papers, Please developer Lucas Pope has been using ordered dithering to great effect in his new game Return of the Obra Dinn.
posted by a car full of lions at 8:50 AM on June 11, 2016 [2 favorites]
posted by a car full of lions at 8:50 AM on June 11, 2016 [2 favorites]
It looks like Lucas is using Blue Noise dither rather than ordered. Christine Love's INTERSTELLAR SELFIE STATION (yeah, allcaps, soz) uses ordered.
On the "verging on the evil side", kevin-cantwell/dotmatrix converts images to dithered text rendered in Unicode Braille symbols.
posted by scruss at 10:04 AM on June 11, 2016
On the "verging on the evil side", kevin-cantwell/dotmatrix converts images to dithered text rendered in Unicode Braille symbols.
posted by scruss at 10:04 AM on June 11, 2016
What Love is doing is certainly the most common way to use ordered dithering, but it's not the only one. Ordered dithering basically amounts to choosing a fixed "dither matrix", repeating it all across the image, and setting a pixel to black or white depending on how its intensity compares to the value in the dither matrix. Depending on how you distribute the values in the dither matrix, you can get various styles including the usual cross-hatched appearance, something that looks like newspaper halftoning, and patterns that resemble blue noise (which is what Pope is doing).
(Note: I'm opposed to the use of the Lena test image because of the boys'-club impression of computer science it propagates, but the discussion on the linked page was way better than anything else I could find online.)
posted by a car full of lions at 11:18 AM on June 11, 2016 [3 favorites]
(Note: I'm opposed to the use of the Lena test image because of the boys'-club impression of computer science it propagates, but the discussion on the linked page was way better than anything else I could find online.)
posted by a car full of lions at 11:18 AM on June 11, 2016 [3 favorites]
And a fun little iPhone/iPad app that takes classic Mac dithered photos!
But from the sample B&W image (and on the Iconfactory website and third-party reviews) it shows they are not using the Atkinson dither, which makes it generically “retro” but not genuinely 1980s Mac. Total fail because they historically were a Mac-based company and they (and reviews online) are marketing it as Mac-ish retro (and even name-drop Atkinson [regarding “fat bits”] on their product page). It’s not like the Atkinson dither is some trade secret or hard to implement.
posted by D.C. at 11:30 AM on June 11, 2016
But from the sample B&W image (and on the Iconfactory website and third-party reviews) it shows they are not using the Atkinson dither, which makes it generically “retro” but not genuinely 1980s Mac. Total fail because they historically were a Mac-based company and they (and reviews online) are marketing it as Mac-ish retro (and even name-drop Atkinson [regarding “fat bits”] on their product page). It’s not like the Atkinson dither is some trade secret or hard to implement.
posted by D.C. at 11:30 AM on June 11, 2016
That was a good read. I'm guessing the dither percentage you can set for gif compression is how much of the error gets passed on.
Well dithered images look so crisp and satisfying somehow, it's interesting to see it coming in to fashion as an artistic choice. (How well do retro graphic trends sync up with the actual history the devs would have grown up with?) It surprises me that it doesn't seem to be used much any more for just plain old smoothing images out, especially when you see some really severe banding in compressed textures or on semi transparent things in games, but I expect that's a combination of it not being free to implement and most normal people not being bothered by it.
I always throw an extremely faint noise on gradients (compare the left and right sides of this for example), but it would be really cool if you could get a proper non random dither.
posted by lucidium at 12:30 PM on June 11, 2016
Well dithered images look so crisp and satisfying somehow, it's interesting to see it coming in to fashion as an artistic choice. (How well do retro graphic trends sync up with the actual history the devs would have grown up with?) It surprises me that it doesn't seem to be used much any more for just plain old smoothing images out, especially when you see some really severe banding in compressed textures or on semi transparent things in games, but I expect that's a combination of it not being free to implement and most normal people not being bothered by it.
I always throw an extremely faint noise on gradients (compare the left and right sides of this for example), but it would be really cool if you could get a proper non random dither.
posted by lucidium at 12:30 PM on June 11, 2016
Is image dithering considered a subset of Pointillism; or is Pointillism a case of image dithering?
posted by Xyanthilous P. Harrierstick at 12:48 PM on June 11, 2016
posted by Xyanthilous P. Harrierstick at 12:48 PM on June 11, 2016
The standard for audio dither is a triangular probability density noise function. There are also as mentioned shaped noise dithers that are supposed to be less audible after accounting for loudness curves and psychoacoustics (even though I'm pretty sure they will technically give you a higher noise floor than the basic noise function).
posted by atoxyl at 3:12 PM on June 11, 2016
posted by atoxyl at 3:12 PM on June 11, 2016
For those new to this the purpose of dither in audio processing is basically to turn quantization error (I have 16 bits to represent every possible gradation of loudness...) into just plain threshold-of-hearing noise.
posted by atoxyl at 3:18 PM on June 11, 2016
posted by atoxyl at 3:18 PM on June 11, 2016
(Which is to say it's the same thing as for images really...)
posted by atoxyl at 3:19 PM on June 11, 2016
posted by atoxyl at 3:19 PM on June 11, 2016
Oh man, I did a whole project when I was in college using "diffusion dither" in photoshop to make images that appeared to have a full tonal range when printed on a b&w laser printer. I don't know anything about the coding behind dithering, but I spent a lot of time tweaking the curves in photoshop to get the right amount of spacing between the dots. One of the prints is still hanging in my bathroom.
posted by Drab_Parts at 4:17 PM on June 11, 2016 [1 favorite]
posted by Drab_Parts at 4:17 PM on June 11, 2016 [1 favorite]
I thought when I bought my 24-bit Speedstar video card I'd never see dithering again. I was wrong!
posted by RobotVoodooPower at 3:15 AM on June 12, 2016
posted by RobotVoodooPower at 3:15 AM on June 12, 2016
Dithering! I love dithering!
Here's a digital copy of Graphics Gems, Vol I (PDF1). On page 713 is a small chapter on Ordered Dithering and how the matrices work which I wrote when I was 22.
Flash forward a couple years and I was working for Adobe on a PostScript printer that was going to include a copy of a DEC technology called "DECimage" (not to be confused with DECImage, which was a totally different DEC project). DECimage (not DECImage), was a reference implementation of Bob Ulichney's blue noise dithering algorithm. Who is Bob Ulichney? Why, he wrote the book on digital half toning. I was thrilled to get a chance to look at his code and integrate it into my product.
And Oh. My. Dog. It ran like treacle in January. I looked over the code and found that it was doing several floating point operations per pixel. This printer had a 68K with no floating point chip, so these ran especially badly. I redid the code using fixed point arithmetic and it ran hundreds of times faster. Being an idiot, I submitted this back to DEC with my notes. The modified code's output was visually indistinguishable from the original, but it was not pixel perfect, which was easily explained with round off differences. The change was rejected because it was not identical output, along with some bullshit about it not meeting the criteria of claiming patent.
As a result, the printer's user manual had to include this paragraph:
This wasn't the only thing that happened with that printer. DEC had been shipping printers with the "standard" PostScript start page, which was ugly as sin. I spent some time creating a better looking start page which included an illustration of the printer with three little dog-eared thumbnail pages above it showing a picture of a woman (my (now ex-)wife), the opening paragraph of Winnie Ille Pu, and a little tiny graph. And mind you, you couldn't actually read the text on the thumbnail pages without a jewler's loupe and there was nearly no detail on the picture, although using DECimage helped a lot. So we submitted the page for approval and waited. And waited. And we got nothing back from DEC. We poked them and saw a message go by saying, "If we don't hear anything by Friday, this is what's going in the final product." Then the flood of change requests started. I had to remove the picture of my wife ("some people could construe it as sexist") and replaced it with a picture of the printer, and remove the Winnie Ille Pu ("Unless Adobe has secured the reprint rights...") and replace it with a page of tech manual text. I had time and ROM space left over, so I put in an easter egg such that if you take the printer off line, hold the the "Test Page" button and then press "Menu-Menu-Menu-Enter-Enter-Enter", the printer will print a full-size picture of my ex. And if you have DECimage turned on, it takes a small eternity to render.
1I find it both really hilarious and heart warming that I was able to find a PDF of a book I contributed to more than 25 years ago being rendered in PDF, a technology that I helped create more than 20 years ago.
posted by plinth at 4:11 AM on June 12, 2016 [10 favorites]
Here's a digital copy of Graphics Gems, Vol I (PDF1). On page 713 is a small chapter on Ordered Dithering and how the matrices work which I wrote when I was 22.
Flash forward a couple years and I was working for Adobe on a PostScript printer that was going to include a copy of a DEC technology called "DECimage" (not to be confused with DECImage, which was a totally different DEC project). DECimage (not DECImage), was a reference implementation of Bob Ulichney's blue noise dithering algorithm. Who is Bob Ulichney? Why, he wrote the book on digital half toning. I was thrilled to get a chance to look at his code and integrate it into my product.
And Oh. My. Dog. It ran like treacle in January. I looked over the code and found that it was doing several floating point operations per pixel. This printer had a 68K with no floating point chip, so these ran especially badly. I redid the code using fixed point arithmetic and it ran hundreds of times faster. Being an idiot, I submitted this back to DEC with my notes. The modified code's output was visually indistinguishable from the original, but it was not pixel perfect, which was easily explained with round off differences. The change was rejected because it was not identical output, along with some bullshit about it not meeting the criteria of claiming patent.
As a result, the printer's user manual had to include this paragraph:
Images processed using DECimage require more time to print than images printed without DECimage. On smaller images, the high-quality output using DECimage should outweigh the additional computation time required. However, on large, high-resolution, full-page images, the additional computation time is significant, and you have to decide whether or not to use DECimage. You may want to print your draft copies without DECimage, and only use it for your final printout.So there you have it. I required paragraph put into every printer's user manual because they wouldn't accept the work of a 24 year-old kid.
This wasn't the only thing that happened with that printer. DEC had been shipping printers with the "standard" PostScript start page, which was ugly as sin. I spent some time creating a better looking start page which included an illustration of the printer with three little dog-eared thumbnail pages above it showing a picture of a woman (my (now ex-)wife), the opening paragraph of Winnie Ille Pu, and a little tiny graph. And mind you, you couldn't actually read the text on the thumbnail pages without a jewler's loupe and there was nearly no detail on the picture, although using DECimage helped a lot. So we submitted the page for approval and waited. And waited. And we got nothing back from DEC. We poked them and saw a message go by saying, "If we don't hear anything by Friday, this is what's going in the final product." Then the flood of change requests started. I had to remove the picture of my wife ("some people could construe it as sexist") and replaced it with a picture of the printer, and remove the Winnie Ille Pu ("Unless Adobe has secured the reprint rights...") and replace it with a page of tech manual text. I had time and ROM space left over, so I put in an easter egg such that if you take the printer off line, hold the the "Test Page" button and then press "Menu-Menu-Menu-Enter-Enter-Enter", the printer will print a full-size picture of my ex. And if you have DECimage turned on, it takes a small eternity to render.
1I find it both really hilarious and heart warming that I was able to find a PDF of a book I contributed to more than 25 years ago being rendered in PDF, a technology that I helped create more than 20 years ago.
posted by plinth at 4:11 AM on June 12, 2016 [10 favorites]
Addendum: page 713 is the code sample which is in the appendix and is not in the PDF. It can be found here.
The actual chapter on dithering is on page 176 (by book numbering, page 199 in PDF numbering).
posted by plinth at 10:28 AM on June 12, 2016
The actual chapter on dithering is on page 176 (by book numbering, page 199 in PDF numbering).
posted by plinth at 10:28 AM on June 12, 2016
A friend used to work on a digital audio system and they found that it slowed to a crawl on very low volume passages. It turned out that the floating point unit trapped to software emulation for denormalized numbers (which are very small by definition). This tended to happen in "studio fades."
After a bit of hand-wringing they realized they could avoid the problem entirely by adding in a bit of random dither, which "we should have done in the first place."
posted by sjswitzer at 4:51 PM on June 12, 2016 [1 favorite]
After a bit of hand-wringing they realized they could avoid the problem entirely by adding in a bit of random dither, which "we should have done in the first place."
posted by sjswitzer at 4:51 PM on June 12, 2016 [1 favorite]
« Older Are you a Sim? | 3 heads of the Black Dog, decades of post-techno... Newer »
This thread has been archived and is closed to new comments
posted by D.C. at 12:51 AM on June 11, 2016 [4 favorites]