[HN Gopher] Ditherpunk: The article I wish I had about monochrom...
___________________________________________________________________
Ditherpunk: The article I wish I had about monochrome image
dithering
Author : todsacerdoti
Score : 440 points
Date : 2021-01-04 16:27 UTC (6 hours ago)
(HTM) web link (surma.dev)
(TXT) w3m dump (surma.dev)
| amelius wrote:
| How would you apply dithering to animations (without the screen
| looking noisy from the different starting conditions of each
| frame)?
| gruez wrote:
| discussed by the author of the mentioned game (return of the
| obra dinn) here:
| https://forums.tigsource.com/index.php?topic=40832.msg136374...
| cpmsmith wrote:
| I originally found out about _Obra Dinn_ by reading that
| devlog--it 's totally fascinating, and shows impressive
| attention to detail.
|
| > It feels a little weird to put 100 hours into something
| that won't be noticed by its absence. Exactly no one will
| think, "man this dithering is stable as shit. total magic
| going on here."
|
| Luckily, thanks to this post, we have the privilege of
| thinking that.
| jerf wrote:
| He's not entirely correct, either. I haven't played it, but
| I did see video of it, and I _was_ impressed by the
| stability of the dithering. It takes work to avoid it
| looking like https://www.youtube.com/watch?v=2AKtp3XHn38 or
| something.
| raphlinus wrote:
| Any ordered dithering algorithm will animate pretty smoothly,
| but techniques based on error diffusion will have a "swimming"
| effect. Lucas Pope's devlog goes into considerable detail.
| Here's a good starting point:
| https://forums.tigsource.com/index.php?topic=40832.msg104520...
|
| (ETA: also the link that gruez posted. HN seems to be having
| some performance issues)
| dassurma wrote:
| Author here!
|
| I can only refer to an article another comment also already
| mentioned. It is _excellent_ and covers animation & dithering:
| https://bisqwit.iki.fi/story/howto/dither/jy/
| bullen wrote:
| Is this what Steam uses for the "News" animated gifs?
| ssivark wrote:
| Somewhat off-topic, but this reminds me of the
| impressionist/pointillist styles of painting. There the
| motivation is not to use a smaller palette, but to typically use
| a _richer_ palette (including colors on the opposite side of the
| wheel) so that the image looks much more vibrant and realistic on
| zooming out, circumventing the limitation of one (flat) color per
| location.
| aharris6 wrote:
| In case anyone wants to play around with some basic dithering, I
| run a webapp called Dither it! that does just this:
|
| https://ditherit.com
| bolofan wrote:
| Since we're talking about monochromatic art... anyone else here a
| fan of the Atari ST game Bolo?
|
| https://www.mobygames.com/game/atari-st/bolo
|
| Probably the best monochromatic aesthetics I've ever seen in a
| game. The screen shots don't do it justice.
| enriquto wrote:
| This article is missing a crucial pre-processing step to
| dithering algorithms: apply a Retinex-like filter to enhance the
| local contrast before doing the dithering. This gives a dramatic
| improvement of the final result. In fact, by exploring the scale
| parameter of the pre-processing step, you find a continuous
| family of binarisations that interpolates between global
| tresholding and local dithering.
| crazygringo wrote:
| That's fascinating -- do you have any links to examples?
|
| I'm searching online but can't find anything at all. I've never
| heard of using Retinex in the context of dithering, and
| wondering what specifically you mean by Retinex-"like"?
|
| I'm also really curious what contexts this has been most
| successful in. E.g. was it used for dithering in images or
| games back in the 1990's when we were limited to 16-bit or
| 256-bit color? Or is this something more recently explored in
| academia or in some niche imaging applications?
| raphlinus wrote:
| Output dependent feedback is another good way to get creamy,
| evenly dispersed dots in highlight and shadow areas:
|
| https://levien.com/output_dependent_feedback.pdf
| enriquto wrote:
| > Output dependent feedback
|
| Wow, didn't know about that. It sounds quite similar to the
| more recent "electrostatic halftoning" algorithm by Weickert et
| al, that apparently does not cite your work:
|
| https://www.mia.uni-saarland.de/Research/IP_Halftoning.shtml
| CyberRabbi wrote:
| Pretty shameless Raph :P
| raphlinus wrote:
| I'm trying to figure out whether this is a compliment, a
| criticism, or both. When topics related to 2D graphics come
| up, there's a fair chance I've done some relevant work in the
| area. I plan to continue shamelessly hawking my results, as
| that's an important part of a research pipeline :)
| mmastrac wrote:
| Please continue hawking relevant papers. This is the
| perfect place to do it.
| dassurma wrote:
| Well, I hadn't heard of it, so I'll read this tomorrow :D
| Thanks for sharing.
| stuaxo wrote:
| Really enjoyable article, reminds me of being at school where the
| first scanner I encountered only output dithered black and white.
| swiley wrote:
| Does anyone else get errors on their HDMI monitors when viewing
| these images? Mine red shifts the entire screen and I'm not sure
| why.
| CyberRabbi wrote:
| Another way to think of dither (that may only make sense to
| people with a signals background) is that it linearizes the error
| introduced by the quantization step (which is a non-linear
| process). This has a bunch of conceptual implications (like
| elimination of error harmonics being natural consequence) but
| maybe most importantly allows you to continue using linear
| analysis tools and techniques in systems with a quantization
| filter.
| nullc wrote:
| This thesis on noise shaping and dither
| http://uwspace.uwaterloo.ca/bitstream/10012/3867/1/thesis.pd...
| is an excellent mathematical treatment of the subject.
| mikaelaast wrote:
| Shameful tangential plug alert: My sideproject is a dithering-
| based image-to-pattern converter for plastic fuse beads (you know
| them, the ones you place on a platter and iron to fuse them
| together): https://www.beadifier.pro/
| dassurma wrote:
| Omg I didn't think of this application for dithering. Love
| that.
| phkahler wrote:
| Nice. A conceptually simple program made into a nice app. Well,
| I assume it's a nice app ;-)
|
| Does it make money? There a couple other simple apps I've
| considered writing to see if I can make a few side bucks.
| mikaelaast wrote:
| Yeah, it's a doing-one-thing-and-doing-it-well kind of
| mentality. It even makes (a little) money.
| cxcorp wrote:
| See also, DITHER.txt:
| http://web.archive.org/web/20190316064436/http://www.efg2.co...
| makeworld wrote:
| DHALF.TXT might also be useful.
|
| https://raw.githubusercontent.com/cyotek/Dithering/master/re...
|
| DITHER.TXT is also available in the same folder.
| sweetheart wrote:
| Oh boy, I think it's about time to hack on some dithered
| generative art. What an inspiration this article was!
| shadowfaxRodeo wrote:
| I just finished making an online dithering tool,
| doodad.dev/dither-me-this if anyone wants to play around with
| dithering.
|
| I'll be re-jigging it based on some info from that article, and
| definitely adding 'blue noise' as an option. Thanks for sharing.
| ksm1717 wrote:
| Here's a cool rust crate that does color quantization and
| dithering at the same time. Ie picking the palette to use and
| dithering the picture with that palette as an evolving context.
| https://github.com/okaneco/rscolorq
|
| It's a port of an older c library that's based on a
| paper/algorithm called spatial color quantization.
| aeontech wrote:
| The article mentions Bill Atkinson's dithering algorithm,
| invented during his work on the original Macintosh. You can also
| read more about it here:
| https://www.evilmadscientist.com/2012/dithering/
|
| It's actually implemented in BitCam iOS app by icon factory:
| https://iconfactory.com/bc.html
|
| And Emilio Vanni did a neat e-paper display experiment with it
| here: https://www.emiliovanni.com/atkinson-dithering-machine
| JKCalhoun wrote:
| Also, drop an image here:
|
| http://gazs.github.io/canvas-atkinson-dither/
| jamesfmilne wrote:
| An old acquaintance of mine, John Balestrieri, made a Mac app
| based on Bill Atkinson's dither algorithm too:
|
| https://www.tinrocket.com/content/hyperdither/
| ohazi wrote:
| > As this image shows, the dithered gradient gets bright way too
| quickly.
|
| _sigh_
|
| Not in Firefox on Linux.
|
| I vaguely recall seeing a multi-year-old bug related to subtly
| broken gamma behavior in either Firefox or Chrome, but can't seem
| to find it right now.
| Cactus2018 wrote:
| http://www.effectgames.com/demos/worlds/
|
| http://www.markferrari.com/
|
| ....
|
| I recall a recent kick-starter-type blog post about a work-in-
| progress game with huge 2d side scrolling dither art - can't find
| the link but :(
| bane wrote:
| It's so interesting to read about the rediscovery and
| reengagement with dithering by newer generations. I grew up when
| dithering was simply a fact of life because of the extremely
| limited graphics capabilities of early computers.
|
| I love the reference to Obra Dinn as the graphics remind me of
| very fond feelings I had for the first black and white
| Macintoshes. There was something wonderful about the crisp 1-bit
| graphics, on a monitor designed for only those two colors, that
| made it look "better" than contemporary color displays in most
| respects -- almost higher resolution than it actually was. It's
| kind of almost impossible to replicate _how_ it looked on modern
| color displays.
|
| I didn't experience that feeling looking at an electronic display
| again until the Kindle. It also had the funny side-effect of
| making art assets on Macintoshes a fraction of the size as on
| color systems, making both the software smaller, and the hard-
| drives hold more.
|
| There's also something somewhat unsatisfying about automatically
| generated dithering patterns used to recast color graphics into
| 1-bit b&w. It seems to really take an artist's hand to make it
| look beautiful. However, the author of this post ends up with
| some very nice examples and it's really well written.
|
| If anybody is interested in seeing how the old systems looked,
| and some great uses of dithering throughout, I'd recommend
| checking out this amazing Internet Archive Mac in a Browser -
| https://archive.org/details/mac_MacOS_7.0.1_compilation
|
| You get dithering literally at the system startup background.
| SoSoRoCoCo wrote:
| This is such a well-written article: it describes the impetus, it
| is researched, it has great examples both as code and as output,
| and it piques interest. In the late 1990's I contracted with an
| embedded software company to optimize a dithering algorithm for
| 8-bit MCUs that was used in most laser printers & copiers, and
| this paper is a really good overview.
| dassurma wrote:
| Thanks for the kind words!
| Eric_WVGG wrote:
| What an odd coincidence... I just acquired an "Inkplate" for my
| birthday (a recycled Kindle screen glued onto a board with an
| Arduino and wifi) and was in the process of looking for old 1bit
| art for it, stumbled across the term "ditherpunk" just last
| night. - https://inkplate.io
|
| artists: - https://unomoralez.com -
| https://www.instagram.com/mattisdovier/?hl=en -
| https://wiki.xxiivv.com/site/dinaisth.html
|
| I'm going to start raiding old Hypercard stacks next
| gregsadetsky wrote:
| I started extracting images from old Hypercard stacks, and then
| found this page which has done all of this work!
|
| https://mariteaux.somnolescent.net/junk/hypercard/
|
| Raid away :)
| dassurma wrote:
| ... I think I need to buy an Inkplate now
| Eric_WVGG wrote:
| It's fantastic. You can program in MicroPython, or C using
| Arduino IDE. I'm barely fluent in C and had no problem
| getting some basic stuff running last night.
| smasher164 wrote:
| I learned something new today! Nice work, and well-explained.
| supernovae wrote:
| Interesting, I "dither" (shift the telescope around between
| photos) my astrophotos to go from noise to less noise - funny
| seeing it go from image to noise. Does anyone have any papers on
| dithering + image integration to go in this direction? always
| been interested in knowing more about it.
| dljsjr wrote:
| > According to Wikipedia, "Dither is an intentionally applied
| form of noise used to randomize quantization error", and is a
| technique not only limited to images. It is actually a technique
| used to this day on audio recordings [...]
|
| Dithering as a digital signal processing technique is also used
| frequently in the digital control of physical systems. One
| example of this is in the control of hydraulic servo valves[1];
| these valves are usually pretty small and their performance can
| be dominated by a lot of external factors. One of the biggest
| ones is "stiction", or static friction, wherein if the moving
| parts of the valve are at rest it can take a large amount of
| current to get them going again which translates in to poor
| control of the valve and in turn poor control of the thing the
| valve is trying to move. It's common to use very high
| frequency/small amplitude dithering on these valves to eliminate
| the effects of stiction without compromising accuracy which
| greatly improves the control stability and responsiveness of the
| servo valves.
|
| 1: https://en.wikipedia.org/wiki/Electrohydraulic_servo_valve
| zlsa wrote:
| I believe this is what the engines are doing during the
| majority of the ascent of the Starship SN8 test vehicle[0]. You
| can see the engines gimbaling very slightly in a circular
| pattern.
|
| [0]: https://youtu.be/ap-BkkrRg-o?t=6516
| im3w1l wrote:
| I would not define it exactly like that. I would say "Dithering
| is any method of reducing the bit depth of a signal that
| prioritizes accurate representation of low frequencies over
| that of high frequencies". This frames it as essentially an
| optimization problem, with randomn noise being a heuristic way
| of accomplishing it.
| jVinc wrote:
| I am in the same boat as the author of having only recently
| played Return of the Obra Dinn between Christmas and new years. I
| cannot recommend it enough, if you haven't played it and like
| puzzlers you should pick it up.
|
| It's an extremely engaging story, and a narrative tool I have not
| previously encountered. No spoilers as this is revealed
| immediately, but essentially you are navigating past events
| through frozen timepoints at the moments when people died, and
| have to determine the identities and fates of all the about 60
| crew aboard the boat, which requires a bit of puzzling things
| together across the different events that lead to peoples deaths.
|
| I doubt we'll see a similar follow up game from Lucas Pope, as he
| has commented this game grew much larger than he expected and he
| would scale back for his next projects. Also from papers-please
| to Obra Dinn he seems to be one to break the mold at each
| iteration, but I really wish there where more games like this,
| with different stories to investigated.
| dheera wrote:
| Not in the same boat as the author but in the past few weeks
| I've been getting into e-Ink displays and making gadgets and
| framed art with them, and most of the displays I can get a hold
| of are either 1-bit or 4-bit greyscale, so this is super
| relevant.
|
| My "crude" dithering algorithm I wrote though seems not
| mentioned in the article. What I do is (in the case of 1-bit)
| just let the grey value (from 0.0=black to 1.0=white) determine
| the probability that the pixel is on or off, and render
| pseudorandom numbers according to those probabilities. In the
| case of 4-bit greyscale I do the same but within 16 bins.
|
| I'm not sure how it compares to the methods in the article but
| maybe I can test this sometime.
| mrob wrote:
| >(in the case of 1-bit) just let the grey value (from
| 0.0=black to 1.0=white) determine the probability that the
| pixel is on or off
|
| This is equivalent to the random noise [-0.5; 0.5] before
| quantization example.
| dheera wrote:
| I think you're right, very interesting, that means I can do
| a whole lot better in the visual quality I get out of these
| e-Ink displays.
|
| Well damn, I'm excited I found this article! Thanks
| @dassurma!
| the_af wrote:
| I share your love for Return of the Obra Dinn, truly a
| masterpiece and a game which shocked me out of my usual apathy
| towards recent videogames.
|
| I have faith in Lucas Pope for whatever project he decides to
| tackle next. Two of his games are masterpieces, this one and
| Papers Please, and I also liked Helsing's Fire a lot. Whatever
| he does next, regardless of scope and theme, will surely please
| me.
| owenversteeg wrote:
| What about dithering for the smallest possible images? I'm
| talking in the 300 byte - 2kb range here. Does anyone have any
| suggestions for what to do to really get file size down?
| dassurma wrote:
| Author here! I don't think many people have researched or
| optimized on this, but I also work on https://squoosh.app, and
| from that experience I know that dithering makes compression
| _worse_ most of the time (unless you use PNG and use a super
| small palette of colors). Interesting idea tho!
| mattdesl wrote:
| Quantizing to <= 256 colors will let you use a single byte per
| pixel, but there are other techniques like Block Truncation
| Coding that work well with 8bit images to go down to 2 bits per
| pixel or lower. Even at 2 bits per pixel, this is still quite
| big as raw data, so you typically will want to use compression
| on top such as RLE, DEFLATE, etc.
|
| I'm currently exploring this for my own applications,
| compressing large 8bit sprite sheet images, and it's producing
| much smaller images than most palette based image formats (GIF,
| WebP, PNG, etc). Follow my progress here:
| https://twitter.com/mattdesl/status/1346048282494177280?s=21
| kccqzy wrote:
| I did use dithering for unimportant background images of a
| website. Use just 256 colors, and both PNG and GIF will use a
| color palette instead of describing each pixel separately.
| Really helps with the file size. Afterwards muck with the
| various lossless compression parameters in PNG with optipng to
| shave off a few more percent.
| makach wrote:
| Excellent article. I've also always wondered, I was making some
| gradients the other day and I was curious to how I could dither
| between two colours. Big thank you for this article!
| at_a_remove wrote:
| This is a great overview.
|
| A few years back, when TechShop still existed and was open, I
| made a present for my mother: a glass laser-etched _and_ engraved
| with an image from her favorite comic. Because the comic was
| painted in a set of watercolors, this was going to be difficult.
| I ended up tracing the lines (for the deeper engraving) and then
| stomping on the color palette for the etching. Finally, I settled
| on different newspaper halftone sets for each "color."
|
| It took several tries for it to come out alright. This might have
| saved me a few runs.
| jstrieb wrote:
| This article is very well put together, and a helpful reference,
| thanks for sharing!
|
| A sibling comment links to a Show HN that didn't get much
| attention, but is definitely worth checking out. I will also
| point out that it is possible to do dithering using GIMP
| (https://docs.gimp.org/en/gimp-image-convert-indexed.html).
| Alternatively, use ImageMagick if that is more your speed
| (https://legacy.imagemagick.org/Usage/quantize/#ordered-dithe...)
| andrenotgiant wrote:
| semi-related: The origin of the word "dither" as explained by
| this wonderful little wikipedia page[1] is worth reading about.
|
| [1]: https://en.wikipedia.org/wiki/Dither
| CalChris wrote:
| _Dynamic Rounding_ , developed by Quantel back in the 90s for
| digital video+film, is underappreciated. Dynamic Rounding + Blue
| Noise is severely underappreciated.
|
| https://en.wikipedia.org/wiki/Quantel
|
| https://patents.google.com/patent/US6281938B1
| mark-r wrote:
| It was nice to see a mention of Robert Ulichney. His 1987 book
| "Digital Halftoning" covers most of the ground that this blog
| post does, plus more.
| dassurma wrote:
| I saw this book mentioned a couple of times during my research.
| I guess I should read it.
| Tomte wrote:
| Donald Knuth also has two nice chapters in "Digital
| Typography".
| mark-r wrote:
| I might have to look that up. It's hard for me to imagine
| what dithering and typography would have in common, other
| than they might both be used to produce a book.
| gfaure wrote:
| This is a great counterpart to this slightly more implementation-
| focused article on the Obra Dinn aesthetic:
| https://danielilett.com/2020-02-26-tut3-9-obra-dithering/
| syssam1897 wrote:
| There recently was a Show HN thread of an interactive dithering
| tool called Dither Me This[1]. I think you will like it if you
| liked this article
|
| [1]: https://news.ycombinator.com/item?id=25469163
| elitepleb wrote:
| As for arbitrary-palette positional dithering,
|
| there's no better write up than
| https://bisqwit.iki.fi/story/howto/dither/jy/
| pdkl95 wrote:
| Bisqwit's discussion of dithering is _outstanding_. He presents
| a _very_ impressive algorithm for arbitrary-palette dithering
| that is _animation safe_.
|
| > This paper introduces a patent-free positional (ordered)
| dithering algorithm that is applicable for arbitrary palettes.
| Such dithering algorithm can be used to change truecolor
| animations into paletted ones, while maximally avoiding
| unintended jitter arising from dithering.
|
| He demonstrates it "live coding" style in this[1] video where
| he writes a demo in 256 colors of a "starfield" animation with
| color blending and Gaussian blur style bloom. The first
| animation at 6:33 using traditional ordered dithering has the
| usual annoying artifacts. The animation at 13:00 using an
| optimal palette and his "gamma-aware Knoll-Yliluom positional
| dithering" changed my understanding of what was possible with a
| 256 color palette. The animation even looks decent[2] dithered
| all the way down to a _16 color_ palette!
|
| If that wasn't crazy enough, he also "live codes" a
| raytracer[3] in DOS that "renders in 16-color VGA palette at
| 640x480 resolution."
|
| [1] https://www.youtube.com/watch?v=VL0oGct1S4Q
|
| [2] https://www.youtube.com/watch?v=W3-kACj3uQA
|
| [3] https://www.youtube.com/watch?v=N8elxpSu9pw
___________________________________________________________________
(page generated 2021-01-04 23:00 UTC)