_______ __ _______
| | |.---.-..----.| |--..-----..----. | | |.-----..--.--.--..-----.
| || _ || __|| < | -__|| _| | || -__|| | | ||__ --|
|___|___||___._||____||__|__||_____||__| |__|____||_____||________||_____|
on Gopher (inofficial)
URI Visit Hacker News on the Web
COMMENT PAGE FOR:
URI Image Dithering: Eleven Algorithms and Source Code (2012)
glimshe wrote 2 hours 41 min ago:
Does anyone know of any application/tool that can perform palette
dithering? The idea is "here is the n-color palette specified in their
RGB values, here is the full-color RGB image, give me the best possible
dithered image using the provided palette". The tools that I've used
were underwhelming and produced results full of banding and artifacts.
Basically, great dithering in color instead of B/W.
larodi wrote 6 hours 19 min ago:
Dithermark.com is all I ever need ⦠amazing stuff
alberth wrote 7 hours 33 min ago:
Hereâs a great online tool that lets you upload any image and apply
different dithering styles to it.
URI [1]: https://doodad.dev/dither-me-this/
tomsonj wrote 7 hours 43 min ago:
Still topical for constrained palette displays like color einks
dreamcompiler wrote 16 hours 30 min ago:
Bresenham's line drawing algorithm is another error diffusion algorithm
except its goal is not approximating colors that don't exist but rather
approximating lines at angles that are not a multiple of 45 degrees on
pixel grids.
naet wrote 16 hours 33 min ago:
Does anyone have a primer on multi-color dithering? I made a fun
dither like program for monotone style dithering, but I'm not really
sure how to adapt it to color palettes with more than two tones.
zeroq wrote 17 hours 20 min ago:
slightly related: it would be great to have a list of TOP 100 recurring
links on HN. :)
on topic: [1] is a great companion read to the subject
URI [1]: https://surma.dev/things/ditherpunk/
kragen wrote 18 hours 54 min ago:
The major dithering algorithm that's missing from this list is
blue-noise dithering. This is very similar to "ordered dithering"; you
can think of ordered dithering as either thresholding the pixel values
with a different threshold value on each pixel, following a regular
pattern, or as adding a different offset value to each pixel, following
a regular pattern, and thresholding the result with a constant
threshold. Blue-noise dithering replaces the regular pattern with a
random pattern that's been high-pass filtered. This has all the
advantages of ordered dithering, in particular avoiding "crawling"
patterns during animation, but avoids the repetitive patterns and line
artifacts it introduces. [1] is the best quick introduction to the
technique that I've seen. There's a more comprehensive introduction at
[2] . [3] also demonstrates it, comparing it to other dithering
algorithms.
Ulichney introduced blue noise to dithering in 01988 as a refinement of
"white-noise dithering", also known as "random dithering", where you
just add white noise before thresholding: [4] . Ulichney's paper is
also a pretty comprehensive overview of dithering algorithms at the
time, and he also makes some interesting observations about high-pass
prefiltering ("sharpening", for example with Laplacians).
Error-diffusion dithering necessarily introduces some low-pass
filtering into your image, because the error that was diffused is no
longer in the same place, and high-pass prefiltering can help. He also
talks about the continuum between error-diffusion and
non-error-diffusion dithering, for example adding a little bit of noise
to your error-diffusion algorithm.
But Ulichney is really considering blue noise as an output of
conventional error-diffusion algorithms; as far as I can tell from a
quick skim, nowhere in his paper does he propose using a precomputed
blue-noise pattern in place of the white-noise pattern for "random
dithering". That approach has really only come into its own in recent
years with real-time raytracing on the GPU.
An interesting side quest is Georgiev and Fajardo's abstract
"Blue-Noise Dithered Sampling" from SIGGRAPH '16 [5] , sadly now
memory-holed by Autodesk. Georgiev and Fajardo attribute the technique
to the 02008 second edition of Lau and Arce's book "Modern Digital
Halftoning", and what they were interested in was actually improving
the sampling locations for antialiased raytracing, which they found
improved significantly when they used a blue-noise pattern to perturb
the ray locations instead of the traditional white noise. This has a
visual effect similar to the switch from white to blue noise for random
dithering. They also reference a Ulichney paper from 01993, "The
void-and-cluster method for dither array generation," which I haven't
read yet, but which certainly sounds like it's generating a blue-noise
pattern for thresholding images.
Lau, Arce, and Bacca Rodriguez also wrote a paper I haven't read about
blue-noise dithering in 02008, saying, "The introduction of the
blue-noise spectraâhigh-frequency white noise with minimal energy at
low frequenciesâhas had a profound impact on digital halftoning for
binary display devices, such as inkjet printers, because it represents
an optimal distribution of black and white pixels producing the
illusion of a given shade of gray," suggesting that blue-noise
dithering was already well established in inkjet-land long before it
became a thing on GPUs.
Maxime Heckel has a nice interactive WebGL demo of different dithering
algorithms at [6] , with mouse-drag orbit controls, including
white-noise dithering, ordered dithering, and blue-noise dithering.
Some of her examples are broken for me.
It's probably worth mentioning the redoubtable [7] and the previous
discussion here: [8] .
URI [1]: https://nelari.us/post/quick_and_dirty_dithering/
URI [2]: https://momentsingraphics.de/BlueNoise.html
URI [3]: https://bartwronski.com/2016/10/30/dithering-part-three-real-w...
URI [4]: https://cv.ulichney.com/papers/1988-blue-noise.pdf
URI [5]: http://web.archive.org/web/20170606222238/https://www.solidang...
URI [6]: https://blog.maximeheckel.com/posts/the-art-of-dithering-and-r...
URI [7]: https://surma.dev/things/ditherpunk/
URI [8]: https://news.ycombinator.com/item?id=25633483
momojo wrote 19 hours 57 min ago:
One of my favorite modern dithering methods is blue-noise dithering
(see Figure 3b): [1] The only catch is that generating blue noise is a
roughly O(n^2) algorithm. Its not feasible to be generated on the fly,
so in practice you just pregenerate a bunch of blue-noise textures and
tile them.
If you google 'pregenerated blue noise' you find plenty of them:
URI [1]: https://developer.nvidia.com/blog/rendering-in-real-time-with-...
URI [2]: https://momentsingraphics.de/BlueNoise.html
bazzargh wrote 6 hours 36 min ago:
You can also get reasonable results from using quasirandom sequences
[1] - which are trivial to generate.
That's the kind of thing I use dithering on BBC Micro because it's
such a cheap technique, here in a thread directly comparing to
Bayer-like dithering [2] or here faking the Windows XP desktop
URI [1]: https://extremelearning.com.au/unreasonable-effectiveness-of...
URI [2]: https://hachyderm.io/@bbcmicrobot@mastodon.me.uk/11200546490...
URI [3]: https://hachyderm.io/@bbcmicrobot@mastodon.me.uk/11288651013...
user____name wrote 7 hours 41 min ago:
You can also run a high pass filter on a white noise image and get
something roughly blue-noise like. By varying the width of the filter
you can control the frequency of the noise. You can use this property
to get constant a physical size to the noise, like DPI awareness.
A lot of blue noise references: [1] There also exist pseudo blue
noise generators, e.g.: [2]
URI [1]: https://gist.github.com/pixelmager/5d25fa32987273b9608a2d2c6...
URI [2]: https://observablehq.com/@fil/pseudoblue
URI [3]: https://www.shadertoy.com/view/3tB3z3
atoav wrote 11 hours 48 min ago:
As a former VFX freelancer I think many people underestimate how
effective cheap tricks like using image textures like that can be.
You don't need real noise, it is enough to have a single texture that
is a bit bigger than the input image and then randomly offset and
rotate it. If that random offset is random enough (so not
pseudorandom with a low periodicity), nobody will ever notice.
Memory has gotten cheaper while latency deadlines are still deciding
over how much you can do realtime. That means cheap tricks like this
are not an embarrassing workaround, but sometimes the smart choice.
abetusk wrote 19 hours 21 min ago:
O(n^2) where n is what? If it's the number of pixels, you have to
touch those anyway, no?
Why can't you create blue noise from walking a Hilbert curve and
placing points randomly with a minimum and maximum threshold?
inhumantsar wrote 12 hours 58 min ago:
I was curious about this too so I dug into it a bit. it seems that
the point placement has to be optimized to ensure they have roughly
even spacing while still being randomly placed.
the naive algorithm is O(n^2) where n is the number of pixels in an
image. tiling and sampling pregenerated noise is O(n), so that's
what most people use. the noise can be generated on the fly using a
FFT-based algorithm, though it still needs to be applied
iteratively so you'd typically end up with O(k n log n) s.t. 10 <=
k <= 100.
this has been neat stuff to read up on. my favorite nugget of
learning: blue noise is white noise that's fine through a high pass
filter a few times. the result of a high pass filter is the same as
subtracting the result of a low pass filter from the original
signal. blurring is a low pass filter for images. since blue noise
is high frequency information, blurring a noised up image
effectively removes the blue noise. so the result looks like a
blurred version of the original even though it contains a fraction
of the original's information.
hatthew wrote 20 hours 13 min ago:
Something I think about sometimes is how it's usually more important to
maintain shape rather than color. For example, in the first 2 images on
the page, quantizing the pink hearts results in some pink, white, and
grey. An error diffusion alg will result in pink speckled with white
and grey, whereas it might be preferable to have a solid pink that's
slightly off color but has no speckles.
Are there existing techniques that do this sort of thing? I'm imagining
something like doing a median filter on the image, run clustering on
the pixels in the colorspace, and then shift/smudge clusters towards
"convenient" points in the colorspace, e.g. the N points of the
quantized palette and the N^2 points halfway between each pair. Then a
partial-error-diffusion alg like atkinson smooths out the final result.
lynnharry wrote 16 hours 42 min ago:
There's no way to do it traditionally. Your request would need the
algorithm to understand the content of the image. Deep learning based
image vectorization probably has a similar objective.
kevinsync wrote 21 hours 59 min ago:
I use a Photoshop plugin for complex dithering (DITHERTONE Pro [0] --
this is NOT AN AD lol, I'm not the creator, just a happy customer and
visual nerd)
I'm only dropping it in here because the marketing site for the plugin
demonstrates a lot of really interesting, full-color, wide spectrum of
use-cases for different types of dithering beyond what we normally
assume is dithering.
[0]
URI [1]: https://www.doronsupply.com/product/dithertone-pro
user____name wrote 7 hours 28 min ago:
On iPhone Safari this page opens a modal popup that I cannot close,
rendering it useless...
Affric wrote 22 hours 13 min ago:
Nostalgic.
Important for lo-fi displays and printing etc
I do think that well dithered images looked better in some texts than
colour images which had more wow but were more distracting.
AndrewStephens wrote 22 hours 40 min ago:
It is surprisingly difficult to get really crisp dithering on modern
displays, you have to do it on the client to match 1-1 the userâs
display. Notice that the pre-rendered examples on this page actually
look a little blurry if you magnify them. This is not really a problem
unless you really want the crispness of the original Mac screen.
A few years ago I got annoyed with this and made a little web-component
that attempts to make really sharp 1-bit dithered images by rendering
the image on the client to match whatever display device the user has.
URI [1]: https://sheep.horse/2023/1/improved_web_component_for_pixel-ac...
rikroots wrote 10 hours 41 min ago:
I rewrote my canvas library's "reduce-palette" filter last month to
make it a lot more code-efficient (because: the library doesn't use
web workers, WebGL, etc). But the main reason to go hunting for
efficiencies was my (slightly unhinged) decision to do all the color
distance calculations in the OKLAB color space.
Demo here:
URI [1]: https://scrawl-v8.rikweb.org.uk/demo/filters-027.html
AndrewStephens wrote 8 hours 13 min ago:
Thatâs cool.
gnabgib wrote 2 days ago:
(2012) Popular in
2016 (199 points, 61 comments) [1] 2017 (125 points, 53 comments)
URI [1]: https://news.ycombinator.com/item?id=11886318
URI [2]: https://news.ycombinator.com/item?id=15413377
alejohausner wrote 3 days ago:
Ulichney (who wrote the book on halftoning) came up with ordered
dithering matrices that give much nicer results than Bayer's, as good
error as diffusion, and parallelizable. Look up "void and cluster".
bad_username wrote 3 days ago:
Dithering has similar importance in digital audio. Dithered 8-bit audio
sounds way better than non-dithered (harsh artifacts are replaced with
tolerable white noise, and quiet details are preserved). Higher end
digital equipment even applies dithering to high-bit samples, as do
plug-ins in digital audio workstations.
dreamcompiler wrote 16 hours 37 min ago:
Audio dithering typically involves adding a small amount of noise
before downconverting to lower resolution samples.
But there's another form of audio dithering that uses error diffusion
(like TFA describes) rather than adding noise. If you use a
single-bit ADC but sample much faster than Nyquist and keep track of
your errors with error diffusion, you preserve all the audio
information in the original with a similar number of bits as a (e.g.)
16-bit ADC sampled at Nyquist, but with the additional benefit that
your sampling noised has moved above the audible range where it can
be filtered out with an analog lowpass filter.
This is one-dimensional dithering but in the audio world it's called
Sigma-Delta modulation or 1-bit ADC.
simondotau wrote 17 hours 34 min ago:
Critically, the benefits of audio dithering come with a single
side-effect (i.e. audible artefact): an increase in the noise floor.
In most cases, however, this elevated noise floor remains below the
threshold of audibility, or more practically, quieter than the
ambient noise of any reasonable listenerâs playback environment.
What's important to appreciate is that dithering digital audio should
only ever be performed when preparing a final export for
distribution, and even then, only for bit-perfect copies. You
shouldn't dither when the next step is a lossy codec. Encoders for
AAC and Opus accept high bit depth originals, because their encoded
files don't have a native "bit depth". They generate and quantise
(compress) MDCT coefficients. When these encoded files are decoded to
16-bit PCM during playback, the codec injects "masking noise" which
serves a similar function to dither.
Panzerschrek wrote 3 days ago:
It's also worth to mention noise-based dithering - where some noise
pattern is added atop of the image and then rounding is performed.
Usually some sort of blue noise is used for this approach.
pasteldream wrote 22 hours 37 min ago:
Agreed - blue noise dithering is very commonly used in computer
graphics because itâs cheap and great, but it might be worth
mentioning that itâs a kind of ordered dithering, which is
mentioned in the article.
Christoph Petersâs free blue noise textures are the most commonly
used, for people who canât be bothered running void and cluster
themselves:
URI [1]: https://momentsingraphics.de/BlueNoise.html
DIR <- back to front page