News for hackers. Stuff that matters.
Re:Image Dithering: Eleven Algorithms and Source Code by mark-r on Friday October 06, 2017 @01:27AM (#15414616)
The article doesn't put enough emphasis on the need for gamma correction. If you dither a pure gray area of level 128, it will become approximately 50% white and 50% black. But when you display that back on the screen, because of gamma effects it will look closer to a level of 186!

A few years ago there was a need for 15-bpp or 16-bpp color images on phones rather than the 24-bpp images we usually work with, and dithering was a great way of producing them. No idea how much need there is today though.

Re:Image Dithering: Eleven Algorithms and Source Code by dahart on Friday October 06, 2017 @10:08AM (#15416881)
> No idea how much need there is today though.

Lots, if you're into printing. Banding that's invisible on a monitor can become a monster when printed. An expensive monster mistake if you're printing a poster sized giclee.

This is a big reason why Photoshop dithers by default when going from a higher range down to 8 bits per channel.

Another reason the need for dither might be even increasing today is that digital cameras have only very recently gotten better than an 8 bit signal to noise ratio. We've had 16 bit RAW formats for a long time, but most cameras still had noise that was greater than 1/256. I tested one of my old Canon EOS cameras and found even in very well lit conditions, it's signal was a little over 5 bits, even though I could get a 16 bit image file out.

With the newest cameras, the signal to noise is sometimes exceeding 12 stops, so photographers might be running into banding issues in RAW images more often. Except a lot of them never notice because Photoshop quietly handles it.

Re:Image Dithering: Eleven Algorithms and Source Code by jacobolus on Friday October 06, 2017 @04:35PM (#15420234)
It would be neat if more people used “hexagonal” (i.e. in an equilateral triangle grid) pixels for capture, processing, display, printing, etc.; with higher and higher resolutions and fast GPUs (so that high-quality resampling can be done on the fly) it should be entirely possible to swap out individual parts of the pipeline without losing quality or performance (at the expense of a bunch of work to implement something nonstandard).

A lot of artifacts are easier to deal with on a hexagon-pixel grid. Halftoning and error-diffusion dithering work really well.

Re:Image Dithering: Eleven Algorithms and Source Code by dahart on Friday October 06, 2017 @08:59PM (#15421616)
Ooh, interesting thought! I think I might have used a hex image to make a game at some point, but other than that I have little experience with them. Do you think the overall benefits of hexels would make it worth trying to standardize the pipeline?

I'd guess that the need for error diffusion and half-toning might wane in the future. (Not sure about that, but that's what I'd guess.) Are there other benefits you get with hex images?

Re:Image Dithering: Eleven Algorithms and Source Code by jacobolus on Saturday October 07, 2017 @02:29AM (#15422551)
The big advantages are (a) they’re much more isotropic, (b) there is less effect from grid artifacts (reduced moiré patterns, etc.), (c) they are noticeably more efficient in terms of sampling rate for a given quality of signal. If everything is done on such a grid end-to-end, you get quite noticeably better quality results for just about everything (with the exception of slightly worse results for drawing sharp grid-aligned rectangles). Even swapping in such a grid in one or another part of the pipeline can usually net some advantage.

The downside is that there are a zillion implementations of everything you can imagine w/r/t a square grid, whereas implementations on a triangular grid of hexagonal pixels are fewer and further between, often some crappy matlab code written by a grad student, so you’d maybe need to reimplement, optimize, debug, etc. a whole pile of tools, or even invent some new algorithms for doing stuff that hasn’t been tried on such a grid before.

There have been lots of papers written about the topic, and at least one book. http://www.springer.com/us/book/9781852339142

* * *

It’s similar to the advantages you get from tri-axial fabric: it’s better but requires custom machinery, so in practice is only used for bullet-proof stuff, space suits, and art projects. Hexagonal pixels end up getting used in medical imaging, astronomical imaging, and the like, where pixels are individually expensive.

Re:Image Dithering: Eleven Algorithms and Source Code by tripzilch on Saturday October 07, 2017 @03:07PM (#15425174)
Here's another great article about hexagonal grids:

http://www.redblobgames.com/grids/hexagons/

It's written with game design in mind, but many of the techniques are useful just the same.

Re:Image Dithering: Eleven Algorithms and Source Code by mark-r on Friday October 06, 2017 @11:23PM (#15422116)
I think Fuji makes some cameras with a hexagonal grid sensor. All our algorithms are based on a square grid though, so it makes it very tough to work with unless you do a conversion.
Re:Image Dithering: Eleven Algorithms and Source Code by 05greg on Friday October 06, 2017 @03:23AM (#15415000)
Dithering is still needed for most of sRGBs range, Frontier needed to do it in Elite Dangerous where banding was noticeable. This paper: https://www.cl.cam.ac.uk/~rkm38/pdfs/boitard14hdr_colorspace... compares the bit depth necessary for contouring due to quantisation to become imperceptible across a few encodings, most of them in the 10-11 bits per channel area.
Re:Image Dithering: Eleven Algorithms and Source Code by mark-r on Friday October 06, 2017 @09:21AM (#15416553)
Thanks for the link. Some years ago I was shown a simple gradient that had noticeable banding on an 8-bit display; until that point I had believed that 8 bits was just beyond our ability to discriminate.
Re:Image Dithering: Eleven Algorithms and Source Code by microcolonel on Friday October 06, 2017 @04:26AM (#15415229)
24bpp is not enough for shallow gradients which don't come from a photographic source (especially in dark images). I frequently dither 48bpp material for 24bpp displays.

I typically use Sierra Lite.

I've recently been experimenting with error diffusion along continuous space-filling curves (I forget where I saw this technique first), and using color difference functions (CIEDE2000) to gauge quantization error. These are overkill, but it sure beats doing it the same boring way forever.

Frankly, I would like it if the CRTCs attached to modern GPUs had some ability to apply dither (even just ordered dither) to buffers as they're scanned out, while exposing more precision to applications.

Re:Image Dithering: Eleven Algorithms and Source Code by jacobolus on Friday October 06, 2017 @05:11AM (#15415425)
Unless you are integrating many pixels (how many and with what weights depends on the future processing, intended output, and viewing conditions for the image) I would not expect using a fancy color difference formula for comparing individual pixels to give a particularly useful result. Indeed, the whole point of dithering (especially with high resolution output) is that we can adjust the average light coming from a several-pixel-wide blob by brightening or darkening individual pixels, and thereby make finer distinctions in light level, since the individual pixels are not really noticed. I’m also pretty skeptical about the space-filling curve thing. Those both sound like placebo features to me.
Re:Image Dithering: Eleven Algorithms and Source Code by microcolonel on Friday October 06, 2017 @05:19AM (#15415440)
Well, I did say experimenting, didn't I?

I found the thing which inspired my space filling curve exploration: https://www.compuphase.com/riemer.htm

The Butteraugli score between the standard lena and the Riemersma dither is about 0.5 better than the standard Floyd-Steinberg one.

Approaches like this come closer to back-propagation of errors, the lack of which is where some of the artifacts of unidirectional dither come from. In practice, any decent (full bleed) error diffusion dither works perfectly fine going between 16 and 8 bit planes, but why shouldn't I try some things out which (as you are quick to point out) may have very little value.

Heck, even gamma correction isn't strictly necessary when you're going from 16 to 8 bit sRGB.

Re:Image Dithering: Eleven Algorithms and Source Code by jacobolus on Friday October 06, 2017 @03:50PM (#15419847)
I don’t know enough about Butteraugli (in particular in the range of very very tiny differences in the image) to know whether it’s a reasonable metric for comparing dithering algorithms.

Why do you think this Riemersma method does better at that metric? Maybe it just keeps the diffused errors spatially closer to the original pixel?

Re:Image Dithering: Eleven Algorithms and Source Code by mark-r on Friday October 06, 2017 @09:23AM (#15416568)
Yes, once you start working on a very small segment of the curve it's close enough to linear and gamma correction becomes overkill.
Re:Image Dithering: Eleven Algorithms and Source Code by jacobolus on Friday October 06, 2017 @03:52PM (#15419856)
I could see it making a difference in average color of very noisy regions, especially brightly colored ones. I suspect you could deliberately construct an image where the difference could be seen by human observers.
Re:Image Dithering: Eleven Algorithms and Source Code by dahart on Friday October 06, 2017 @09:52AM (#15416749)
You don't need error diffusion when your target color space is greater than 8 bits per channel. You can just use a random number generator (or sequence).
Re:Image Dithering: Eleven Algorithms and Source Code by tripzilch on Saturday October 07, 2017 @03:01PM (#15425135)
Why exactly? Is there a threshold of bits per channel / resolution, why at 8 bits?

I can understand that it would become less useful, because error diffusion does less if you have more levels. But (I expect) it's still useful at 6 bits (64 values), is 8 not just an arbitrary treshold?

Re:Image Dithering: Eleven Algorithms and Source Code by dahart on Sunday October 08, 2017 @06:33PM (#15430394)
It's because with 8 bits you can't really see the dither pattern itself once a 1-bit difference is at the human threshold of perception.

8 bits is not just an arbitrary threshold, it's the number of bits you need so that a 1 bit difference is just about the "just noticeable difference", assuming you've handled gamma and color reasonably well. 9 bits is more lightness resolution than you can normally see, and 7 bits is too few. If you want to geek out super hard, check out figure 238 here: http://www.telescope-optics.net/eye_intensity_response.htm

The JND of Weber's law is 0.4 - 0.5% for print and monitors most of the time, which is between 1/200 and 1/250. This is why 8 bits is so super popular, it has a 1-bit step of 1/256, which is normally just barely below what we can see with our eyes.

You may need to dither at 6 bits, banding could start to become pretty obvious. Whether you need error diffusion, I don't know, I doubt it would always useful at 6 bits, but I'm sure it would sometimes. I'd say try it on some images and compare to random dithering. Random dithering only sucks on really small palettes like 2 or 16 total colors. It's not that bad on a 256 color gif, and it becomes hard to tell the difference when you're above 4 bits per channel or 12 bits per pixel. 6 bits per channel is decent color resolution, and random will sometimes be good enough. If it's a photograph from a digital camera that's older than a year or two, chances are pretty good you can threshold the image without even dithering, because it's already noisy enough.

Re:Image Dithering: Eleven Algorithms and Source Code by nayuki on Friday October 06, 2017 @10:49AM (#15417190)
Gamma correction is very important when dithering at low bit depths. Demo at 2 bits per channel: https://www.nayuki.io/page/gamma-aware-image-dithering