Fejlspredning - Error diffusion

Fejldiffusion er en form for halvtone , hvor kvantiseringsresten fordeles til nabopixel, der endnu ikke er blevet behandlet. Dets vigtigste anvendelse er at konvertere et billede på flere niveauer til et binært billede, selvom det har andre applikationer.

I modsætning til mange andre halvtoningsmetoder klassificeres fejldiffusion som en områdedrift, fordi hvad algoritmen gør på et sted påvirker, hvad der sker på andre steder. Dette betyder, at buffering er påkrævet og komplicerer parallel behandling . Punktoperationer, såsom beordret rystning , har ikke disse komplikationer.

Fejldiffusion har en tendens til at forbedre kanter i et billede. Dette kan gøre tekst i billeder mere læsbar end i andre halvtoneteknikker .

Et fejlspredt billede

Tidlig historie

Richard Howland Ranger modtog amerikansk patent 1790723 for sin opfindelse , "Faxsystem". Patentet, der blev udstedt i 1931, beskriver et system til overførsel af billeder over telefon- eller telegraflinjer eller via radio. Ranger opfindelse tilladt rastererede fotografier , der skal konverteres først i sort og hvid og derefter sendes til fjerntliggende steder, som havde en pen bevæger sig over et stykke papir. For at gøre sort blev pennen sænket til papiret; for at producere hvid blev pennen hævet. Grå nuancer blev gengivet ved periodisk at hæve og sænke pennen, afhængigt af den ønskede lysstyrke .

Ranger's opfindelse brugte kondensatorer til at lagre ladninger og vakuumrørkomparatorer til at bestemme, hvornår den nuværende luminans plus en akkumuleret fejl var over en tærskel (forårsagede, at pennen blev hævet) eller under (forårsagede, at pennen blev sænket). I denne forstand var det en analog version af fejldiffusion.

Digital æra

Floyd og Steinberg beskrev et system til udførelse af fejldiffusion på digitale billeder baseret på en simpel kerne:

hvor " " betegner en pixel i den aktuelle række, som allerede er blevet behandlet (derfor ville diffuserende fejl til den være meningsløs), og "#" angiver den pixel, der i øjeblikket behandles.

Næsten samtidigt afslørede JF Jarvis, CN Judice og WH Ninke fra Bell Labs en lignende metode, som de kaldte " minimeret gennemsnitlig fejl "ved hjælp af en størrekerne:

Algoritme beskrivelse

Fejldiffusion tager et monokromt eller farvebillede og reducerer antallet af kvantiseringsniveauer. En populær anvendelse af fejldiffusion indebærer at reducere antallet af kvantiseringstilstande til kun to pr. Kanal. Dette gør billedet velegnet til udskrivning på binære printere såsom sort / hvid laserprintere.

I den følgende diskussion antages det, at antallet af kvantiseringstilstande i det fejlspredte billede er to pr. Kanal, medmindre andet er angivet.

En-dimensionel fejldiffusion

Den enkleste form for algoritmen scanner billedet en række ad gangen og en pixel ad gangen. Den aktuelle pixel sammenlignes med en halvgrå værdi. Hvis den er over værdien, genereres en hvid pixel i det resulterende billede. Hvis pixlen er under halvvejs lysstyrke, genereres en sort pixel. Der kan bruges forskellige metoder, hvis målpaletten ikke er monokrom, f.eks. Tærskelværdi med to værdier, hvis målpaletten er sort, grå og hvid. Den genererede pixel er enten fuld lys eller fuld sort, så der er en fejl i billedet. Fejlen tilføjes derefter til den næste pixel i billedet, og processen gentages.

To-dimensionel fejldiffusion

En dimensionel fejldiffusion har tendens til at have alvorlige billedartefakter, der viser sig som forskellige lodrette linjer. To -dimensionel fejldiffusion reducerer de visuelle artefakter. Den enkleste algoritme er præcis som en dimensionel fejldiffusion, bortset fra at halvdelen af ​​fejlen tilføjes til den næste pixel, og halvdelen af ​​fejlen tilføjes til pixlen på den næste linje nedenfor.

Kernen er:

hvor "#" angiver den pixel, der i øjeblikket behandles.

Yderligere forfining kan opnås ved at sprede fejlen længere væk fra den nuværende pixel, som i matricerne ovenfor i Digital æra . Prøvebilledet i starten af ​​denne artikel er et eksempel på todimensionel fejldiffusion.

Farvefejl diffusion

De samme algoritmer kan anvendes på hver af de røde, grønne og blå (eller cyan, magenta, gule, sorte) kanaler i et farvebillede for at opnå en farveeffekt på printere, f.eks. Farvelaserprintere, der kun kan udskrive enkelt farveværdier .

Imidlertid opnås bedre visuelle resultater ved først at konvertere farvekanalerne til en opfattende farvemodel, der vil adskille lys-, farvetone- og mætningskanaler, så en højere vægt for fejldiffusion vil blive givet til lyshedskanalen end til farvetone -kanalen . Motivationen for denne konvertering er, at menneskesynet bedre opfatter små forskelle i lethed i små lokale områder end lignende farvetone i samme område og endda mere end lignende mætningsforskelle på det samme område.

For eksempel, hvis der er en lille fejl i den grønne kanal, der ikke kan repræsenteres, og en anden lille fejl i den røde kanal i samme tilfælde, kan den korrekt vægtede sum af disse to fejl bruges til at justere en mærkbar lyshedsfejl, at kan repræsenteres på en afbalanceret måde mellem alle tre farvekanaler (i henhold til deres respektive statistiske bidrag til letheden), selvom dette giver en større fejl for farvetonen ved konvertering af den grønne kanal. Denne fejl vil blive spredt i de nærliggende pixels.

Derudover kan det være nødvendigt med gammakorrektion på hver af disse perceptive kanaler, hvis de ikke skaleres lineært med det menneskelige syn, så fejldiffusion kan akkumuleres lineært til disse gammakorrigerede lineære kanaler, før de sidste farvekanaler beregnes de afrundede pixelfarver ved hjælp af en omvendt konvertering til det native ikke-gammakorrigerede billedformat, og hvorfra den nye restfejl vil blive beregnet og konverteret igen for at blive distribueret til de næste pixels.

Fejldiffusion med flere gråtoner

Error Diffusion kan også bruges til at producere outputbilleder med mere end to niveauer (pr. Kanal, i tilfælde af farvebilleder). Dette har anvendelse i displays og printere, der kan producere 4, 8 eller 16 niveauer i hvert billedplan, såsom elektrostatiske printere og displays i kompakte mobiltelefoner. I stedet for at bruge en enkelt tærskel til at producere binær output, bestemmes det nærmeste tilladte niveau, og eventuel fejl diffunderes som beskrevet ovenfor.

Printerhensyn

De fleste printere overlapper de sorte prikker lidt, så der ikke er et nøjagtigt en-til-en-forhold til prikfrekvens (i prikker pr. Arealenhed) og lethed . Toneskala -linearisering kan anvendes på kildebilledet for at få det udskrevne billede til at se korrekt ud.

Kantforbedring kontra lethedskonservering

Når et billede har en overgang fra lys til mørk, har fejldiffusionsalgoritmen en tendens til at gøre den næste genererede pixel sort. Mørke til lyse overgange har en tendens til at resultere i, at den næste genererede pixel er hvid. Dette forårsager en kantforbedringseffekt på bekostning af gråniveauets gengivelsesnøjagtighed. Dette resulterer i fejldiffusion med en højere tilsyneladende opløsning end andre halvtonemetoder . Dette er især fordelagtigt med billeder med tekst i dem, f.eks. Den typiske fax.

Denne effekt viser sig ganske godt på billedet øverst i denne artikel. Græsdetaljen og teksten på skiltet er godt bevaret, og letheden på himlen, der indeholder små detaljer. Et klynge-prik- halvtonebillede med samme opløsning ville være meget mindre skarpt.

Se også

Referencer

  1. ^ Richard Howland Ranger, faxsystem. USA's patent 1790723, udstedt 3. februar 1931.
  2. ^ JF Jarvis, CN Judice og WH Ninke, En undersøgelse af teknikker til visning af kontinuerlige tonebilleder på bilevel -displays. Computergrafik og billedbehandling, 5 : 1: 13–40 (1976).

eksterne links