Image Dithering: Eleven Algorithms and Source Code

199 点作者 nkron将近 9 年前

21 条评论

dahart将近 9 年前

I still use dithering daily with 24 bit color images. In fact, my test for whether a modern image editor is serious and good is whether it supports dithering when converting from floating point color channels down to 8 bits per channel. Photoshop does this.The most important reason for me is not display on the monitor, but printing the image. I do a lot of large format printing, and printers smash parts of your color space and make some gradient/banding problems stick out like a sore thumb. Dithering is critical when printing!Gradients with banding can easily show up when you resize a large image down to a smaller size. This is a good reason that resizing probably anything less than 16 bits per channel images should be done in a higher precision format than the image.I haven't tried to use an error diffusion dither when converting 16 bits per channel down to 8... I'm not sure how much that matters. It might make a difference, and it sounds fun to code either way, but in my experience, a good random number generator suffices to make color bands vanish.

bajsejohannes将近 9 年前

> It also has uses when reducing 48 or 64bpp RAW-format digital photos to 24bpp RGB for editing.The author touches upon it here, but I think it's worth generalizing further: If you have high or maybe infinite precision in your color values, dithering will look much nicer than simply rounding to the nearest value. A concrete example is a color gradient. If done naively with rounding, color bands will be clearly visible. With dithering, they will be almost impossible to see.See for example: <a href="http://johanneshoff.com/dithering/" rel="nofollow">http://johanneshoff.com/dithering/</a>

the8472将近 9 年前

The article doesn't mention the void and cluster[0][1] ordered dithering (and modernized variants) which have the advantage of ordered dithering that they are highly parallelization, e.g. via GPU shaders but do not leave the easily spottable patterns of ordered dithering.For example the madVR[2] video renderer uses it for realtime video dithering to avoid banding shallow color gradients from 10bit sources or debanded internal 16bit representation on <= 8bit displays.[0] <a href="http://cv.ulichney.com/papers/1993-void-cluster.pdf" rel="nofollow">http://cv.ulichney.com/papers/1993-void-cluster.pdf</a> [1] <a href="http://www.hpl.hp.com/research/isl/halftoning/publications/1995-filter-extent.pdf" rel="nofollow">http://www.hpl.hp.com/research/isl/halftoning/publications/1...</a> [2] <a href="http://madvr.com/" rel="nofollow">http://madvr.com/</a>

评论 #11889374 未加载

评论 #11889159 未加载

harryf将近 9 年前

A while back got curious about the approach used by apps like Manga Camera ( <a href="https://play.google.com/store/apps/details?id=jp.co.supersoftware.mangacamera" rel="nofollow">https://play.google.com/store/apps/details?id=jp.co.supersof...</a> ) to turn photos into Manga style "drawings".Turns out there's a paper on it "MANGAWALL: GENERATING MANGA PAGES FOR REAL-TIME APPLICATIONS" ( <a href="https://www.semanticscholar.org/paper/MangaWall-Generating-manga-pages-for-real-time-Wu-Aizawa/c027ee8729d44f3a08b5e7361689513123954ac6/pdf" rel="nofollow">https://www.semanticscholar.org/paper/MangaWall-Generating-m...</a> ) and an implementation - <a href="https://github.com/zippon/MangaWall" rel="nofollow">https://github.com/zippon/MangaWall</a> - that implementation uses ordered dithering ( <a href="https://github.com/zippon/MangaWall/blob/master/src/MangaEngine.cc#L206" rel="nofollow">https://github.com/zippon/MangaWall/blob/master/src/MangaEng...</a> ) among other things to help produce a pencil drawn like effect.Anyway just saying ;) To me at least, pretty fascinating ...

1wd将近 9 年前

A fun (if not terribly effective) algorithm that's missing here is dithering along a Hilbert curve.<a href="http://caca.zoy.org/study/part3.html" rel="nofollow">http://caca.zoy.org/study/part3.html</a>

评论 #11887155 未加载

akavel将近 9 年前

For an interesting case of modern artistic use of dithering, see the discussion related to development of indie game "Return of the Obra Dinn" [1] (by Lucas Pope, author of "Papers, please"), where a participant contributed a dithering scheme he invented [2] for a specific purpose of making faces of in-game characters better looking and easier to recognize.[1] <a href="https://forums.tigsource.com/index.php?topic=40832.msg1217196#msg1217196" rel="nofollow">https://forums.tigsource.com/index.php?topic=40832.msg121719...</a>[2] <a href="https://forums.tigsource.com/index.php?topic=40832.msg1212805#msg1212805" rel="nofollow">https://forums.tigsource.com/index.php?topic=40832.msg121280...</a>(Just in case and for easier browsing, I took liberty of uploading a copy to github: <a href="https://github.com/akavel/WernessDithering" rel="nofollow">https://github.com/akavel/WernessDithering</a>, although I'm not clear on what's the license of the code, unfortunately; that said I hope the numbers in the matrix are not patented.)(edit: lol, didn't notice there's another thread on Obra Dinn already on HN, now I'm surprised! :)

richard_todd将近 9 年前

I don't know if it's some kind of nostalgia factor (since a lot of old 16-color EGA software used it, I think), but I find ordered dithering output strangely appealing. I have also used it sometimes where size mattered more than style on the assumption that GIF/PNG compression rates would be better on ordered dithers. ImageMagick can do a lot of dithering styles and it's fun to play with.

nullc将近 9 年前

This thesis on image dithering and noise shaping is one of the best works I've read on the subject: <a href="http://uwspace.uwaterloo.ca/bitstream/10012/3867/1/thesis.pdf" rel="nofollow">http://uwspace.uwaterloo.ca/bitstream/10012/3867/1/thesis.pd...</a>

评论 #11886803 未加载

RiscyAcorn将近 9 年前

Last year I tried painting some Floyd-Steinberg dithered pixels... <a href="https://flashasm.wordpress.com/2015/11/04/more-incredibly-slow-rendering-algorithms-cupcakes-pixel-art/" rel="nofollow">https://flashasm.wordpress.com/2015/11/04/more-incredibly-sl...</a> (16 colours) and <a href="https://flashasm.wordpress.com/2016/05/18/81920-pixels-of-64-colour-cupcake-goodness/" rel="nofollow">https://flashasm.wordpress.com/2016/05/18/81920-pixels-of-64...</a> (64 colours)

1wd将近 9 年前

Another fun fact I always think of when dithering comes up is how Tim Sweeney's software rendered or the original Unreal game used dithering instead of bilinear interpolation for texture mapping. This was very impressive at the time.<a href="http://www.flipcode.com/archives/Texturing_As_In_Unreal.shtml" rel="nofollow">http://www.flipcode.com/archives/Texturing_As_In_Unreal.shtm...</a>

huuu将近 9 年前

It's a kind of funny those images look nice on high res screens.Some time ago I experimented with 16-32 color images on websites. Because of high res screens they look great but save a lot of data.

IvanK_net将近 9 年前

Few years ago, I created a real-time dithering of video in Javascript: <a href="http://blog.ivank.net/floyd-steinberg-dithering-in-javascript.html" rel="nofollow">http://blog.ivank.net/floyd-steinberg-dithering-in-javascrip...</a>

semi-extrinsic将近 9 年前

This article is really nice. I used it as my starting point when I once won a code golf competition on image quality in dithering. Using Fortran.The algorithm is based on Sierra Lite, but I added a random element to the direction in which the error is propagated. This removes essentially all dithering artifacts.<a href="http://codegolf.stackexchange.com/questions/26554/dither-a-grayscale-image" rel="nofollow">http://codegolf.stackexchange.com/questions/26554/dither-a-g...</a>

joosters将近 9 年前

Has anyone tried using the equivalent of animated GIFs to help with dithering? If you have a limited palette of colours, perhaps you could produce two dithered versions, with pixels sometimes having different colours in alternate frames. If the image is refreshed fast enough, two colours could blend into a third.The most extreme example could be 'dithering' a grey square into 1) a black square and 2) a white square, and when they are rapidly switching between the two it might appear as a grey instead.I guess that in practice, the refresh rates of monitors are too low to make it seem anything other than a terrible flickering image, but on old CRTs the effect might work a little better. It's also memory and CPU intensive, but I'd still be curious to see if it could be used successfully, and if it improved the quality compared to 'just' a single dithered image.

评论 #11893666 未加载

评论 #11889101 未加载

评论 #11888274 未加载

评论 #11892146 未加载

评论 #11889023 未加载

chhabrakadabra将近 9 年前

This was a great read. Very approachable.

dividuum将近 9 年前

There is another interesting application for dithering that I've read about in the recent Uncharted 4 Brain Dump (Ctrl-F for "Dithering") here <a href="https://redd.it/4itbxq" rel="nofollow">https://redd.it/4itbxq</a>: Use dithering instead of alpha blending to fade out close objects. Alpha blending can be quite expensive while dithering just omits pixels. The result looks like this: <a href="http://allenchou.net/wp-content/uploads/2016/05/dithering-1-1024x576.png" rel="nofollow">http://allenchou.net/wp-content/uploads/2016/05/dithering-1-...</a> (best visible at the top left corner).

评论 #11889967 未加载

seanwilson将近 9 年前

Great and easy to follow article!> For simplicity of computation, all standard dithering formulas push the error forward, never backward. If you loop through an image one pixel at a time, starting at the top-left and moving right, you never want to push errors backward (e.g. left and/or up).Would the image look a lot different if you dithered it backwards from the bottom right pixel?Are there dithering algorithms that consider the error in all directions instead of pushing the errors forward only?

评论 #11887877 未加载

评论 #11888349 未加载

rabidsnail将近 9 年前

Also if you don't know what your target palette is you can do k-means clustering over colorspace, and the palette is the cluster centers (each point you're giving to k-means is an <r,g,b> or <h,s,v> vector).

评论 #11889728 未加载

mynegation将近 9 年前

Back when I was at university, we had a computer graphics course. Each week we got new assignment that we needed to program, write to a floppy disk (it was before Internet became widely available) and give it to the prof next week.Dithering was one of the assignments. We were required to implement black-white quantization and then Atkinson and Floyd-Steinberg. We were given the freedom to choose our own images.During development at the dorm my favourite picture to debug on was pretty racy (think along the lines of full version of "Lena"). I totally did not intend to put it to the floppy disk...Not only I got the 10 - the highest number of points for this assignment, I got +2 on top of that with the comment from prof: "for the choice of test images in the best tradition of the field".

评论 #11906417 未加载

评论 #11886777 未加载

rasz_pl将近 9 年前

Neat facts:-3DFX Voodoo (all models in 16bit color depth) let you enable hardware dithering block (2x2/4x4 ordered dither, zero performance penalty). They did it to save framebuffer space (24bit textures, 16bit framebuffer). It made 3dfx graphics look significantly better than nvidia/ati in 16bit depth. Earlier cards used 4x1 filter on the output, Banshee and later models gained 2x2 filter providing "22 bit like quality" as 3dfx called it.-Back in ~1994 some HP unix workstations used dithering to produce 'near 23bit color' out of 8bit framebuffer <a href="https://en.wikipedia.org/wiki/HP_Color_recovery" rel="nofollow">https://en.wikipedia.org/wiki/HP_Color_recovery</a>-All crappy (TN) LCD panels (staple of garbage bin supermarket 1366x768 laptop, and older 'gaming' fullhd ones) use FRC which is a form of temporal dithering <a href="https://en.wikipedia.org/wiki/Frame_rate_control" rel="nofollow">https://en.wikipedia.org/wiki/Frame_rate_control</a>One legitimate use of dithering was in the days of CGA/EGA/other fixed palette hardware. You can relive it here 'Joel Yliluoma's arbitrary-palette positional dithering algorithm': <a href="http://bisqwit.iki.fi/story/howto/dither/jy/" rel="nofollow">http://bisqwit.iki.fi/story/howto/dither/jy/</a>

ja27将近 9 年前

I sense a disturbance in the force. It's as if 1,000 BitCam clones were just born.

21 条评论

dahart将近 9 年前

bajsejohannes将近 9 年前

the8472将近 9 年前

评论 #11889374 未加载

评论 #11889159 未加载

harryf将近 9 年前

1wd将近 9 年前

评论 #11887155 未加载

akavel将近 9 年前

richard_todd将近 9 年前

nullc将近 9 年前

评论 #11886803 未加载

RiscyAcorn将近 9 年前

1wd将近 9 年前

huuu将近 9 年前

IvanK_net将近 9 年前

semi-extrinsic将近 9 年前

joosters将近 9 年前

评论 #11893666 未加载

评论 #11889101 未加载

评论 #11888274 未加载

评论 #11892146 未加载

评论 #11889023 未加载

chhabrakadabra将近 9 年前

This was a great read. Very approachable.

dividuum将近 9 年前

评论 #11889967 未加载

seanwilson将近 9 年前

评论 #11887877 未加载

评论 #11888349 未加载

rabidsnail将近 9 年前

评论 #11889728 未加载

mynegation将近 9 年前

评论 #11906417 未加载

评论 #11886777 未加载

rasz_pl将近 9 年前

ja27将近 9 年前

I sense a disturbance in the force. It's as if 1,000 BitCam clones were just born.