Foutdiffusie of dither is een techniek om de weergave van computergraphics te verbeteren wanneer het aantal kleuren wordt verminderd. Het wordt gecombineerd met anti-aliasing. Het wordt gebruikt in computersystemen die slechts een klein aantal kleuren kunnen weergeven, en in printers (waarbij pixels slechts twee waarden hebben, met of zonder toner).

Het houdt in dat de kwantiseringsfouten die ontstaan door de aanpassing van de kleur van een pixel naar een kleur uit een kleiner bereik, worden verdeeld over naburige pixels.

Het beperkt het verschijnen van patronen zoals banding (geleidelijke weergave van helderheid of tint) in afbeeldingen, maar het nadeel is dat er meer ruis ontstaat.

Ook in audio wordt foutdiffusie gebruikt bij ruisonderdrukking door kwantisering, waarbij een willekeurig signaal met vibratie en trilling of superpositiesignaal toegepast wordt.

Foutdiffusie wordt gebruikt in computergraphics om de illusie van een grotere kleurendiepte te creëren met een beperkt kleurenpalet (kleurkwantisatie). Niet beschikbare kleuren worden benaderd door ervoor te zorgen dat de gemiddelde kleur van een groep pixels overeenkomt met de kleur van het corresponderende gebied in de originele afbeelding. Het menselijk oog neemt de juxtapositie van kleine gekleurde elementen waar als een mengsel van kleuren. Computer- en televisieschermen gebruiken deze eigenschap van kleurmenging om een kleurenbeeld weer te geven met fosforen van slechts drie kleuren.

Om dit proces te vereenvoudigen, registreert het foutdiffusie-algoritme voor elke pixel het verschil tussen de dichtstbijzijnde kleurcode in het uitvoerpalet en de originele kleur, en telt dit verschil op bij naburige pixels voordat er naar de dichtstbijzijnde kleur wordt gezocht.

Het proces waarbij de beschikbare kleuren worden teruggebracht tot een kleurenpalet, wordt kwantisatie genoemd. Het verlies van bepaalde informatie veroorzaakt afrondingsfouten. Door deze fouten te verdelen, maakt het algoritme ze minder opvallend.

Afbeeldingen die door foutverspreiding tot een klein aantal kleuren zijn gereduceerd, zijn vaak te onderscheiden door hun korrelige of gespikkelde uiterlijk.

Foutdiffusie is een proces dat veel berekeningen vereist. Daarom werden vroeger alleen effen kleuren gebruikt, wat de kwaliteit verlaagde. Daardoor kon de beeldkwaliteit, afhankelijk van de toepassing, sterk variëren.

Historisch gezien werd het foutdiffusieproces geïmplementeerd in beeldbewerkingssoftware voor weergave in 16 miljoen kleuren, terwijl er dikwijls maar 256 kleuren beschikbaar waren. Elke ontbrekende kleur werd gesimuleerd door verschillende stippen met verschillende kleuren naast elkaar te plaatsen.

Sommige fabrikanten van grafische kaarten hadden een "palet" met een beperkt aantal voorkeurskleuren. Hierdoor kon de ontbrekende tint worden vervangen door de dichtstbijzijnde kleur uit het palet. Met deze technologie was de weergave sneller omdat dynamische foutvoortplanting werd geëlimineerd, maar de kleurweergave was aanzienlijk slechter.

Grafische apparaten, waaronder vroege computervideokaarten en veel lcd-schermen die in mobiele telefoons en instapmodellen van digitale camera's worden gebruikt, bieden een lagere kleurdiepte dan meer recente apparaten. Foutdiffusie kan bijvoorbeeld worden gebruikt om een foto met potentieel een miljoen kleuren weer te geven op een grafische kaart die er slechts 256 tegelijk kan renderen. Deze 256 kleuren worden gebruikt om een benadering van de originele afbeelding te creëren. Zonder deze benadering zouden de kleuren van de originele afbeelding simpelweg worden benaderd door de dichtstbijzijnde beschikbare kleuren, wat zou resulteren in een slechte afbeelding. Foutdiffusie maakt gebruik van de neiging van het menselijk oog om twee gelijksoortige kleuren te "vermengen".

Een dergelijk proces, waarbij de hardware van het computerscherm de belangrijkste beperking vormt voor de kleurdiepte, wordt vaak gebruikt in software zoals webbrowsers. Omdat een browser afbeeldingen van een externe bron kan weergeven, kan het nodig zijn de kleurdiepte te verminderen van afbeeldingen met te veel kleuren in vergelijking met het aantal kleuren in het kleurenpalet. Om problemen met foutdiffusieberekeningen te voorkomen, is een kleurenpalet genaamd 'Web-safe color' gedefinieerd, waarmee alleen die kleuren kunnen worden geselecteerd die niet gerasterd worden op monitoren die slechts 256 kleuren kunnen weergeven.

Zelfs wanneer het totale aantal beschikbare kleuren in de beeldschermhardware hoog genoeg is voor het weergeven van digitale kleurenfoto's, zoals 15- en 16-bits RGB HiColor met 32.768 tot 65.536 kleuren, kan er toch banding zichtbaar zijn, vooral in grote schaduwgebieden (hoewel dit niet in het originele afbeeldingsbestand voorkomt). Door de uitvoer te reduceren naar 32- of 64-bits RGB wordt een goede benadering van een pseudo- echte kleurenweergave verkregen, die het oog niet als korrelig zal interpreteren. Bovendien kan een afbeelding die wordt weergegeven op hardware die 24-bits RGB (8 bits per primaire kleur) ondersteunt, worden verkleind om een iets grotere kleurdiepte te simuleren en/of het verlies aan beschikbare tinten na gammacorrectie te minimaliseren.

Een andere nuttige toepassing van foutdiffusie is in gevallen waarin het grafische bestandsformaat de beperkende factor is. Met name het veelgebruikte GIF-formaat is in veel grafische bewerkingsprogramma's beperkt tot 256 kleuren of minder. Afbeeldingen in andere bestandsformaten, zoals PNG, kunnen ook dergelijke beperkingen hebben om de bestandsgrootte te verkleinen. Dergelijke afbeeldingen hebben een vast kleurenpalet dat alle kleuren definieert die de afbeelding kan gebruiken. In deze situaties kunnen rasterafbeeldingsbewerkingsprogramma's het aantal kleuren in afbeeldingen verminderen voordat ze in deze beperkende formaten worden opgeslagen.

Er kunnen verschillende algoritmes worden gebruikt om het aantal kleuren te verminderen.

De eenvoudigste methode om het aantal kleuren te verminderen, is assimilatie aan de dichtstbijzijnde kleur uit de beschikbare kleuren.

In zwart-wit past men de reductie door middel van het gemiddelde of drempelwaarde toe, waarbij elke kleurwaarde van een pixel wordt vergeleken met een vaste drempelwaarde.

Dit is misschien wel het eenvoudigste algoritme voor kleurreductie, maar het veroorzaakt een aanzienlijk verlies aan detail en randen. De methode van Otsu maakt het mogelijk om de juiste drempelwaarde te bepalen door het histogram van de beeldwaarden te analyseren.

Dithering is een klassieke methode in digitale audio. Goodal paste deze al in 1951 toe, onder de naam noise encoding om de nadelen van drempelwaardebepaling voor het beeld te verhelpen. Het vergelijkt de waarde van elke pixel met een willekeurige drempelwaarde. Hoewel deze zeer snelle methode geen herhalende artefacten genereert, heeft ruis de neiging om door te dringen in de beelddetails. De methode heeft een weergave die analoog is aan de mezzotinttechniek die gebruikt wordt bij gravures.

Bij de puntdruktechniek wordt het principe van het raster in druktechnieken toegepast, waarbij pixels in een herhalend patroon worden gecombineerd. Hierdoor kan het aantal kleuren in het palet worden gereproduceerd, vermenigvuldigd met het aantal pixels in het herhalende patroon. De resulterende kleur is het gemiddelde van de kleuren in het patroon. De resolutie wordt gereduceerd tot die van het patroon.

Verschillende patronen kunnen compleet verschillende rastereffecten creëren.

• Halftoon is vergelijkbaar met de druktechniek die in kranten wordt gebruikt. Het is een vorm van clusterscreening, waarbij de puntjes de neiging hebben om bij elkaar te worden gegroepeerd. Dit helpt om de neveneffecten van wazige pixels op oudere beeldschermen te maskeren.
• Geordende rastering, ook wel Bayer-rastering genoemd, genereert een arceringpatroon. Het is een vorm van diffuse rastering. Omdat de stippen niet in clusters zijn gegroepeerd, is het resulterende beeld veel minder korrelig.

(Origineel)	Drempelwaarde	Willekeurig (dithering)	Halftoon	Gerangschikt

Het Floyd-Steinberg-algoritme, ontwikkeld in 1975, is het bekendste en een van de allereerste algoritmen voor foutdiffusie. Het berekent het algebraïsche verschil tussen de gevraagde kleur voor een pixel en de dichtstbijzijnde beschikbare kleur, en telt dit verschil, gewogen door een matrix, op bij de vier naburige pixels die nog niet zijn verwerkt.

Hoewel dit algoritme eenvoudig blijft, minimaliseert het visuele artefacten. Foutdiffusiealgoritmen produceren beelden die dichter bij het origineel liggen dan eenvoudigere algoritmen.

Andere algoritmes werken op een vergelijkbare manier:

• Het Jarvis, Judice & Ninke-algoritme verspreidt fouten over iets verder gelegen pixels. Dit proces genereert minder visuele artefacten, ten koste van detail. Het is trager dan het vorige algoritme omdat het fouten verspreidt tot de twaalfde pixel in plaats van de vierde, zoals bij Floyd-Steinberg.
• Het Stucki-algoritme, dat gebaseerd is op Jarvis, Judiec & Ninke maar iets sneller is, levert doorgaans schone en nauwkeurige resultaten op.
• Het Burkes-algoritme is een vereenvoudigde vorm van het Stucki-algoritme, sneller maar minder netjes.
• Het Scolorq-algoritme is een experimenteel ruimtelijk kleurquantisatie-algoritme dat kleurquantisatie en foutdiffusie combineert om een optimaal beeld te produceren. Vanwege de aard ervan is de onderstaande voorbeeldafbeelding niet strikt zwart-wit, maar bestaat deze uit twee grijstinten.

Floyd-Steinberg	Jarvis, Judice & Ninke	Stucki	Burkes

• Het Sierra-algoritme is gebaseerd op dat van Jarvis, Judice en Ninke; het is sneller en levert vergelijkbare resultaten op.
• Het Two-row Sierra-algoritme is een variant van Sierra, ontwikkeld om de snelheid ervan te verbeteren.
• Het Filter Lite-algoritme is een algoritme ontwikkeld door Sierra dat eenvoudiger en sneller is dan het Floyd-Steinberg-algoritme, terwijl het vergelijkbare resultaten oplevert.
• Het Atkinson-algoritme is vergelijkbaar met Jarvis, Judice & Ninke en Sierra-dithering, maar is sneller. Een ander verschil is dat het niet de volledige kwantiseringsfout diffundeert, maar slechts driekwart ervan. Het behoudt doorgaans details goed, maar zeer lichte of zeer donkere gebieden kunnen overbelicht lijken.
• Het Hilbert-Peano-algoritme is een variant van Riemersma-dithering en wordt gebruikt door ImageMagick.

Sierra	Tow-row Sierra	Filter Lite	Atkinson