Om de zoveel tijd bekruipt mij de goesting om eens iets simpels te programmeren.

Het is al jaar en dag dat ik een grote fan ben van de zwart-with dithering zoals die op de oude Macs was. Die allereerste Macs hadden een scherm van 512 op 342 pixels dat alleen maar zwart en wit kon tonen. Dus een beeld zoals dit kon er nooit op getoond worden:

Dat moest eerst omgezet worden naar enkel zwart en witte pixels. De allersimpelste manier om dat te doen, is zeggen dat alles dat donkerder is dan een bepaalde grijstoon zwart wordt en al de rest wit. Dat geeft dan iets zeer ongenuanceerd en meestal ofwel te zwart, ofwel te wit, afhankelijk van elke threshold er gekozen wordt:

…en dus zijn er allerlei dithering-algoritmes, om met minder kleuren dan beschikbaar het er te doen uitzien dat er meer kleuren zijn. Op de oude Macs was dat met een aangepaste versie van het algoritme van de heren Floyd en Steinberg. Floyd-Steinberg-dithering op het beeld hierboven ziet er zo uit:

Met uw hoofd een beetje scheef en uw ogen een beetje toe, ziet dat er dus serieus gelijk de oorspronkelijke foto uit.

En het algoritme is eigenlijk al met al bijzonder eenvoudig:

  • pixel per pixel het beeld afgaan
  • als de pixel waar we naar aan het kijken zijn dichter bij wit is, hem wit maken, en als hij dichter bij zwart is, hem zwart maken
  • kijken wat het verschil is tussen de oorspronkelijke pixel en de nieuwe pixel
  • dat verschil verdelen over pixels die later zullen behandeld worden, en wel in deze verhouding: zeven zestienden naar de volgende pixel in de rij, drie zestienden naar de pixel linksonder deze pixel, vijf zestienden naar de pixel recht onder deze pixel, en dan nog één zestiende naar de pixel rechtsonder deze pixel

Op die manier wordt dat verschil tussen de oorspronkelijke pixel en de nieuwe pixel ‘uitgesmeerd’, in plaats van helemaal lokaal te blijven. En dat geeft, afhankelijk van het beeld, écht wel heel propere resultaten:

Van zodra de achtergrond min of meer wit is, geeft dat mij meteen een flashback naar de jaren-1980:

‘t Is ook wijs om profielfoto’s mee te maken — kijk, zo zit ik nu voor mijn computer:

Oh, en ‘t is bijzonder eenvoudig te maken zelf. Dit is in een Jupyter notebook met Python en PIL als beeldbibliotheek:

Er zijn natuurlijk ook andere algoritmen om te ditheren, en die zijn ook niet zó enorm moeilijk te implementeren. Floyd-Steinberg ziet er zo uit, in een matrix:

       X   7
   3   5   1

     (1/16)

Ongeveer samen met Floyd en Steinberg waren er Jarvis, Judice en Ninke, die met een wat grotere kernel werkten: 

             X   7   5 
     3   5   7   5   3
     1   3   5   3   1

           (1/48)

Dat geeft een redelijk ander resultaat — vergelijk Floyd-Steinberg (links) met minimised average error dithering (rechts):

Kijk vooral naar de rand van de brilglazen om het verschil te zien, ‘t is eigenlijk wel wijs.

Iets sneller in de praktijk dan Jarvis en collega’s hun ding is Stucki dithering: dat verdeelt de fout ook over twaalf pixels in de buurt, maar met een iets andere ratio: elke 7 wordt een 8, elke 5 een 4, en elke 3 een 2, voor een totaal van 42:

             X   8   4 
     2   4   8   4   2
     1   2   4   2   1

           (1/42)

Het verschil tussen minimised average error dithering (links) en Stucki dithering (rechts) is niet zó groot, maar het is er wel:

Voor die anderhalve mens ter wereld die al heel de tijd denkt “maar dat is helemaal niet hoe mijn Mac er uitzag, 37 jaar geleden”: inderdaad! Het was geen échte Floyd-Steinberg dithering, en het was ook niet de meer complexe Jarvis et al of Stucki. Bill Atkinson had zijn eigen dithering in mekaar gedraaid, en die zag er zo uit:

         X   1   1 
     1   1   1   
         1    

        (1/8)

Waar de voorgaande de hele fout verdeelden over de omgeving, verdeelt deze maar 6/8, of 2/3 van de fout. Dat zorgt ervoor dat grijswaarden en details goed bewaard blijven, maar dat heel donkere en heel lichte regio’s de neiging hebben om dicht te lopen.

Mijn favoriet, minimised average error dithering, vergeleken met Atkinson dithering:

En Atkinson toegepast op de foto van Steve Jobs met een Mac:

Yep, pure nostalgie. 😀

2 reacties op “Dithering”

Reacties zijn gesloten.