Kleurkwantisatie: Van Miljoenen naar Tientallen Kleuren

De kernuitdaging

Een 24‑bit RGB‑afbeelding kan tot 16.777.216 unieke kleuren bevatten. Maar in veel artistieke en technische contexten is veel minder nodig: 256 voor GIF, 16 voor klassieke pixel art, soms slechts 2 voor monochrome prints. Color quantization is de wetenschap — én kunst — van het kiezen welke handvol kleuren al die 16,7 miljoen mogelijkheden het best vertegenwoordigt.

De naïeve aanpak om de RGB‑kubus gelijkmatig in vakjes te verdelen levert rampzalige resultaten op. De meeste afbeeldingen gebruiken maar een klein deel van de volledige kleurruimte, waardoor een uniforme verdeling paletslots verspilt aan kleuren die in de afbeelding helemaal niet voorkomen.

Median Cut: delen en heersen

Paul Heckberts Median Cut‑algoritme (1982) kiest een ruimtelijke benadering. Het behandelt elke pixel als een punt in 3D‑RGB‑ruimte en splitst vervolgens herhaaldelijk de puntenwolk langs zijn langste as op de mediaan. Nansplitsingen heb je 2ⁿclusters. De gemiddelde kleur van elk cluster wordt een paletkleur.

Median Cut is elegant omdat het zich vanzelf aanpast aan de afbeelding. Een zonsondergangsfoto, gedomineerd door rood- en oranje­tinten, zal de meeste paletkleuren toewijzen aan warme tinten — precies waar het detail belangrijk is. De blauwe lucht krijgt minder entries omdat die veel gelijkmatiger is.

K‑means clustering

K-Means pakt het probleem iteratief aan. Begin met k willekeurige "centroids" in RGB-ruimte. Wijs elke pixel toe aan het dichtstbijzijnde centroid (met Euclidische afstand). Herbereken elk centroid als het gemiddelde van de eraan toegewezen pixels. Herhaal dit tot er convergentie optreedt.

K-Means vindt vaak betere paletten dan Median Cut omdat het globaal optimaliseert, maar het is trager en gevoelig voor de initiële startwaarden. In de praktijk geeft een combinatie van Median Cut-initialisatie met K-Means-verfijning de beste resultaten — de snelheid van divide-and-conquer met de finesse van iteratieve optimalisatie.

Het afstandsprobleem

Elk kwantisatie-algoritme is afhankelijk van het meten van afstand tussen kleuren. De naïeve Euclidische afstand in RGB-ruimte behandelt rood, groen en blauw als even belangrijk, maar zo werkt menselijk zicht niet. We zijn veel gevoeliger voor veranderingen in groen (luminantie) dan in blauw.

Betere kwantisatie gebruikt perceptuele afstands-maten — werken in CIELAB-ruimte waar Euclidische afstand de perceptuele verschillen benadert, of luminantie-wegingsfactoren toepassen op RGB-afstanden. Deze ene aanpassing kan de kwaliteit van een palet drastisch verbeteren zonder het algoritme zelf te veranderen.

Octree-kwantisatie

Voor real-time toepassingen bouwt de octree methode een boomstructuur die de RGB-kubus recursief opdeelt in acht octanten. Bladknopen verzamelen pixel-aantallen, en de boom wordt van onder naar boven gesnoeid — waarbij de minst gevulde knopen als eerste worden samengevoegd — totdat de gewenste paletgrootte is bereikt.

Octrees zijn geheugenefficiënt en kunnen in één enkele pass over de afbeelding worden opgebouwd. Het is het voorkeursalgoritme voor veel praktische implementaties, waaronder de GIF-weergave in vroege webbrowsers.

Kwantisatie in de praktijk

In het Lab van Indexed Color Studio kun je deze algoritmes naast elkaar vergelijken. Genereer een ruisende gradient en kwantiseer die vervolgens naar 4, 8, 16 of 32 kleuren met elke methode. De verschillen zijn opvallend: Median Cut behoudt structuur, K-Means optimaliseert voor vloeiendheid en octrees balanceren snelheid met kwaliteit.

Gecombineerd met dithering kan zelfs een 16-kleurenpalet fotografische details reproduceren. Het kwantisatie-algoritme kiest welke 16 kleuren; het dithering-algoritme bepaalt hoe ze worden gerangschikt. Samen veranderen ze strikte beperkingen in creatieve mogelijkheden.