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.