Bestilt dithering - Ordered dithering

I dette eksempel ( Lenna ) vises det originale fotografi til venstre. Versionen til højre viser effekten af ​​at kvantificere den til 16 farver og dithering ved hjælp af det 8 × 8 ordnede dithering -mønster.
De karakteristiske 17 mønstre i den 4 × 4 ordnede dithering -matrix kan ses tydeligt, når de kun bruges med to farver, sort og hvid. Hvert mønster er vist over den tilsvarende rystede nuance.

Bestilt dithering er et billede dithering algoritme. Det bruges almindeligvis til at vise et kontinuerligt billede på et display med mindre farvedybde . For eksempel bruger Microsoft Windows det i 16-farve grafiktilstande. Algoritmen er kendetegnet ved mærkbare crosshatch -mønstre i resultatet.

Tærskelkort

Algoritmen reducerer antallet af farver ved at anvende et tærskelkort M til de viste pixels, hvilket får nogle pixels til at ændre farve, afhængigt af afstanden mellem den originale farve og de tilgængelige farveposter i den reducerede palet.

Tærskelkort findes i forskellige størrelser, hvilket typisk er en effekt på to:



Kortet kan drejes eller spejles uden at påvirke algoritmens effektivitet. Dette tærskelkort (for sider med længde som effekt på to ) er også kendt som en indeksmatrix eller Bayer -matrix .

Vilkårlige størrelsestærskelkort kan udformes med en enkel regel: Fyld først hver plads med et successive heltal. Omarranger dem derefter, så den gennemsnitlige afstand mellem to på hinanden følgende tal på kortet er så stor som muligt, hvilket sikrer, at bordet "vikler" rundt i kanterne. For tærskelkort, hvis dimensioner er en effekt på to, kan kortet genereres rekursivt via:

Det rekursive udtryk kan beregnes eksplicit ved hjælp af kun bitrekning: 

M(i, j) = bit_reverse(bit_interleave(bitwise_xor(i, j), i)) / n ^ 2

Forudberegnede tærskelkort

I stedet for at lagre tærskelkortet som en matrix med × heltal fra 0 til , afhængigt af den nøjagtige hardware, der bruges til at udføre dithering, kan det være fordelagtigt at forudberegne tærsklerne for kortet til et flydende punktformat, snarere end det traditionelle heltalmatrixformat vist ovenfor.

Til dette kan følgende formel bruges: 

Mpre(i,j) = (Mint(i,j)+1) / n^2

Dette genererer en standard tærskelmatrix.

til 2 × 2 kortet:

dette opretter det forudberegnede kort:

Derudover kan normalisering af værdierne til gennemsnitsværdi af deres sum til 0 (som udført i dithering-algoritmen vist nedenfor) også foretages under forbehandling ved at trække 1 ⁄ 2 fra hver værdi: 

Mpre(i,j) = (Mint(i,j)+1) / n^2 - 0.5

oprettelse af det forudberegnede kort:

Algoritme

Den ordnede dithering -algoritme gengiver billedet normalt, men for hver pixel udligner det sin farveværdi med en tilsvarende værdi fra tærskelkortet i henhold til dets placering, hvilket får pixelens værdi til at blive kvantiseret til en anden farve, hvis den overskrider tærsklen.

For de fleste dithering formål, er det tilstrækkeligt at blot tilføje tærskelværdien til hver pixel (uden at udføre normalisering ved at trække 1 / 2 ), eller ækvivalent, til at sammenligne pixel værdi til tærsklen: hvis værdien af lysstyrken for en pixel er mindre end tallet i den tilsvarende celle i matrixen, tegne den pixel sort, ellers plotte den hvid. Denne mangel på normalisering øger billedets gennemsnitlige lysstyrke en smule, og får næsten hvide pixels til ikke at dithere. Dette er ikke et problem, når du bruger en gråtonepalet (eller en palet, hvor de relative farveafstande er (næsten) konstante), og det er ofte endda ønsket, da det menneskelige øje opfatter forskelle i mørkere farver mere præcist end lysere, dog , det giver forkerte resultater, især når du bruger en lille eller vilkårlig palet, så korrekt normalisering bør foretrækkes.

To billeder, der efterligner en gradient på 140 × 140 = 19600 forskellige farver. Begge billeder bruger de samme 64 farver. Billedet til højre er blevet rystet. Dithering blev udført ved hjælp af en ikke-normaliserende dithering-algoritme, hvilket fik billedet til at have en lille overrepræsentation af lyse pixels.

Med andre ord udfører algoritmen følgende transformation på hver farve c i hver pixel:

hvor M ( i , j ) er tærskelkortet på i -rækken og j -th kolonne, c ′ er den transformerede farve, og r er mængden af ​​spredning i farverum. Hvis man antager en RGB -palet med 2 3 N jævnt distancerede farver, hvor hver farve (en tredobbelt rød, grøn og blå værdier) er repræsenteret med en oktet fra 0 til 255, ville man typisk vælge . ( 1 ⁄ 2 er igen normaliseringsbetegnelsen.)

Fordi algoritmen fungerer på enkelte pixels og ikke har betingede udsagn, er den meget hurtig og velegnet til real-time transformationer. Fordi placeringen af ​​dithering-mønstrene altid forbliver den samme i forhold til displayrammen, er den mindre tilbøjelig til at rystes end fejlspredningsmetoder, hvilket gør den velegnet til animationer. Fordi mønstrene er mere gentagne end fejlspredningsmetoden, komprimeres et billede med ordnet dithering bedre. Ordnet dithering er mere velegnet til line-art grafik, da det vil resultere i rettere linjer og færre anomalier.

De værdier, der læses fra tærskelkortet, skal helst skaleres i samme område som den minimale forskel mellem forskellige farver i målpaletten. Tilsvarende skal størrelsen på det valgte kort være lig med eller større end forholdet mellem kildefarver og målfarver. For eksempel, når man kvantificerer et 24 bpp billede til 15 bpp (256 farver pr. Kanal til 32 farver pr. Kanal), ville det mindste kort, man ville vælge, være 4 × 2 i forholdet 8 (256: 32). Dette gør det muligt at udtrykke hver distinkt tone i input med forskellige dithering -mønstre.

En variabel palet: mønster dithering

Non-Bayer nærmer sig

Ovenstående tærskelværdi -matrixmetode beskriver Bayer -familien af ​​ordnede dithering -algoritmer. En række andre algoritmer kendes også; de involverer generelt ændringer i tærskelmatricen, svarende til "støj" i generelle beskrivelser af dithering.

Halvtone

Halvtone dithering udfører en form for clustered dithering, hvilket skaber et look, der ligner halvtonemønstre , ved hjælp af en specielt udformet matrix.

Ugyldig og klynge

Ugyldigheds- og klynge-algoritmen bruger en på forhånd genereret blå støj som matrix for dithering-processen. Den blå støjmatrix bevarer Bayers gode højfrekvensindhold, men med en mere ensartet dækning af alle involverede frekvenser viser en meget lavere mængde mønster.

Metoden "hulrum og klynge" får sit navn fra matrixgenereringsproceduren, hvor et sort billede med tilfældigt initialiserede hvide pixels er gaussisk-sløret for at finde de lyseste og mørkeste dele, der svarer til hulrum og klynger. Efter at et par swaps har fordelt de lyse og mørke dele jævnt, er pixelerne nummereret efter betydning. Det tager betydelige beregningsressourcer at generere den blå støjmatrix: på en moderne computer kræver en 64 × 64 matrix et par sekunder ved hjælp af den originale algoritme.

Referencer

  1. ^ Bayer, Bryce (11. -13. Juni 1973). "En optimal metode til gengivelse i to niveauer af billeder med kontinuerlig tone" (PDF) . IEEE International Conference on Communications . 1 : 11–15. Arkiveret fra originalen (PDF) den 2013-05-12 . Hentet 2012-07-19 .
  2. ^ Joel Yliluoma. " Vilkårlig-palet positionel dithering algoritme "
  3. ^ Ulichney, Robert A (1993). "Metoden tomrum og klynge til generering af dither-array" (PDF) . Hentet 2014-02-11 .
  4. ^ Wronski, Bart (31. oktober 2016). "Dithering del tre - virkelige 2D -kvantisering dithering" .
  5. ^ Peters, Christoph. "Gratis blå støj teksturer" . momentsingraphics.de .

Yderligere læsning

  • Ancin, Hakan; Bhattacharjya, Anoop K .; Shu, Joseph S. (2. januar 1998). "Forbedring af tomrum og klynge for bedre ensartet halvtone". Photonics West '98 elektronisk billeddannelse : 321–329. CiteSeerX  10.1.1.40.5331 . doi : 10.1117/12.298295 .

eksterne links