Beställde dithering - Ordered dithering

I detta exempel ( Lenna ) visas originalfotografiet till vänster. Versionen till höger visar effekten av att kvantifiera den till 16 färger och dithering med hjälp av det 8 × 8 ordnade ditheringmönstret.

De karakteristiska 17 mönstren i den 4 × 4 ordnade dithering -matrisen kan ses tydligt när de används med endast två färger, svart och vitt. Varje mönster visas ovanför motsvarande oskadade nyans.

Ordnad dithering är en bilddithering -algoritm . Det används vanligtvis för att visa en kontinuerlig bild på en skärm med mindre färgdjup . Till exempel använder Microsoft Windows det i 16-färgs grafiklägen. Algoritmen kännetecknas av märkbara crosshatch -mönster i resultatet.

Tröskelkarta

Algoritmen minskar antalet färger genom att tillämpa en tröskelkarta $M$ på de pixlar som visas, vilket gör att vissa pixlar ändrar färg, beroende på originalfärgens avstånd från de tillgängliga färgposterna i den reducerade paletten.

Tröskelkartor finns i olika storlekar, vilket vanligtvis är två:

{\ displaystyle \ mathbf {M} = {\ frac {1} {4}} \ times {\ begin {bmatrix} 0 & 2 \\ 3 & 1 \\\ end {bmatrix}}}

{\ displaystyle \ mathbf {M} = {\ frac {1} {16}} \ times {\ begin {bmatrix} 0 & 8 & 2 & 10 \\ 12 & 4 & 14 \ 6 \\ 3 & 11 & 1 & 9 \\ 15 & 7 & 13 & 5 \\\ end {bmatrix}}}

{\ Display \ mathbf {M} = {\ frac {1} {64}} \ gånger {\ begin {bmatrix} 0 & 32 & 8 & 40 & 2 & 34 & 10 & 42 \\ 48 & 16 & 56 & 24 & 50 & 18 & 58 & 26 \\ 12 & 44 & 4 & 36 & 14 & 46 & 6 & 38 \\ 60 & 28 & 52 & 20 & 62 & 30 & 54 & 22 \\ 3 & 35 & 11 & 43 & 1 & 33 & 9 & 41 \\ 51 & 19 & 59 & 27 & 49 & 17 & 57 & 25 \\ 15 & 47 & 7 & 39 & 13 & 45 & 5 & 37 \\ 63 & 31 & 55 & 23 & 61 & 29 & 53 & 21 \ \\ end {bmatrix}}}

Kartan kan roteras eller speglas utan att det påverkar algoritmens effektivitet. Denna tröskelkarta (för sidor med längd som effekt av två ) är också känd som en indexmatris eller Bayer -matris .

Gränsvärde för tröskelkartor kan utformas med en enkel regel: Fyll först varje plats med flera heltal. Ordna sedan om dem så att det genomsnittliga avståndet mellan två på varandra följande nummer på kartan är så stort som möjligt, så att bordet "sveper" runt kanterna. För tröskelkartor vars dimensioner är en effekt på två kan kartan genereras rekursivt via:

{\ displaystyle \ mathbf {M} _ {2n} = {\ frac {1} {(2n)^{2}}} \ gånger {\ begin {bmatrix} (2n)^{2} \ times \ mathbf {M } _ {n} & (2n)^{2} \ times \ mathbf {M} _ {n} +2 \\ (2n)^{2} \ times \ mathbf {M} _ {n}+3 & (2n )^{2} \ times \ mathbf {M} _ {n} +1 \ end {bmatrix}}}

Det rekursiva uttrycket kan beräknas uttryckligen med endast bitaritmetik:

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

Förberäknade tröskelkartor

Istället för att lagra tröskelkartan som en matris med × heltal från 0 till , beroende på den exakta hårdvaran som används för att utföra dithering, kan det vara fördelaktigt att förberäkna trösklarna för kartan till ett flytande punktformat, snarare än det traditionella heltalmatrisformat som visas ovan. ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle n^{2}}$

För detta kan följande formel användas:

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

Detta genererar en standard tröskelmatris.

för 2 × 2 -kartan:

{\ displaystyle {\ frac {1} {4}} \ times {\ begin {bmatrix} 0 & 2 \\ 3 & 1 \\\ end {bmatrix}}}

detta skapar den förberäknade kartan:

{\ displaystyle {\ begin {bmatrix} 0.25 & 0.75 \\ 1.0 & 0.5 \\\ end {bmatrix}}}

Dessutom kan normalisering av värdena för att medelvärdet av deras summa till 0 (som görs i dithering-algoritmen som visas nedan) göras under förbehandling också genom att subtrahera 1 ⁄ 2 från varje värde:

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

skapa den förberäknade kartan:

{\ displaystyle {\ begin {bmatrix} -0.25 & 0.25 \\ 0.5 & 0 \\\ end {bmatrix}}}

Algoritm

Den ordnade dithering -algoritmen återger bilden normalt, men för varje pixel kompenserar den dess färgvärde med ett motsvarande värde från tröskelkartan enligt dess plats, vilket gör att pixelns värde kvantiseras till en annan färg om den överskrider tröskeln.

För de flesta dithering ändamål, är det tillräckligt att helt enkelt lägga till tröskelvärde för att varje pixel (utan att utföra normalisering genom att subtrahera ett / två ), eller ekvivalent, att jämföra pixels värde med tröskel: om ljushetsvärdet för en pixel är mindre än siffran i motsvarande cell i matrisen, rita den pixeln svart, annars rita den vit. Denna brist på normalisering ökar något den genomsnittliga ljusstyrkan för bilden och gör att nästan vita pixlar inte blir raka. Detta är inte ett problem när du använder en gråskalepalett (eller någon palett där de relativa färgavstånden är (nästan) konstanta), och det är ofta till och med önskat, eftersom det mänskliga ögat uppfattar skillnader i mörkare färger mer exakt än ljusare, dock , det ger felaktiga resultat, särskilt när du använder en liten eller godtycklig palett, så korrekt normalisering bör föredras.

Två bilder som efterliknar en lutning på 140 × 140 = 19600 olika färger. Båda bilderna använder samma 64 färger. Bilden till höger har förvirrats. Dithering gjordes med en icke-normaliserande dithering-algoritm, vilket fick bilden att ha en liten överrepresentation av ljusa pixlar.

Med andra ord utför algoritmen följande transformation på varje färg $c$ på varje pixel:

{\ displaystyle c '= \ mathrm {närmaste \ _palette \ _color} {\ mathopen {}} \ left (c+r \ times \ left (M (x {\ bmod {n}}, y {\ bmod {n} })-1/2 \ right) {\ mathclose {}} \ right)}

där

M (i, j)

är tröskelkartan på

i

-raden och

j

-kolumnen,

c'

är den transformerade färgen och

r

är mängden spridning i färgutrymmet. Om vi antar en RGB -palett med

2 3 N

jämnt distanserade färger där varje färg (en trippel röda, gröna och blåa värden) representeras av en oktett från 0 till 255, skulle man vanligtvis välja . ( En / 2 är återigen den normalise sikt.)

{\ textstyle r \ approx {\ frac {255} {N}}}

Eftersom algoritmen fungerar på enstaka pixlar och inte har några villkorliga påståenden, är den mycket snabb och lämplig för realtidstransformationer. Eftersom platsen för rastrande mönster alltid förblir densamma i förhållande till bildskärmsramen, är den dessutom mindre benägen att skaka än felspridningsmetoder, vilket gör den lämplig för animationer. Eftersom mönstren är mer repetitiva än feldiffusionsmetoden komprimeras en bild med ordnad dithering bättre. Ordnad dithering är mer lämplig för line-art grafik eftersom det kommer att resultera i rakare linjer och färre avvikelser.

De värden som läses från tröskelkartan ska helst skala in i samma intervall som den minimala skillnaden mellan olika färger i målpaletten. På samma sätt bör storleken på den valda kartan vara lika med eller större än förhållandet mellan källfärger och målfärger. Till exempel, när man kvantiserar en 24 bpp bild till 15 bpp (256 färger per kanal till 32 färger per kanal), skulle den minsta karta man väljer vara 4 × 2, för förhållandet 8 (256: 32). Detta gör det möjligt att uttrycka varje distinkt ton i ingången med olika dithering -mönster.

En variabel palett: mönstrande

Non-Bayer närmar sig

Ovanstående tröskelvärdesmatrismetod beskriver Bayer -familjen av ordnade dithering -algoritmer. Ett antal andra algoritmer är också kända; de involverar i allmänhet förändringar i tröskelmatrisen, motsvarande "bruset" i allmänna beskrivningar av dithering.

Halvton

Halvtonshuggning utför en form av klusterdithering, vilket skapar ett utseende som liknar halvtonmönster med hjälp av en specialkonstruerad matris.

Ogiltigt och kluster

Tomrums- och klusteralgoritmen använder ett förgenererat blått brus som matris för dithering-processen. Den blåa brusmatrisen håller Bayers goda högfrekvensinnehåll, men med en mer enhetlig täckning av alla involverade frekvenser visar den en mycket lägre mängd mönster.

Metoden "tomrum och kluster" får sitt namn från matrisgenereringsproceduren, där en svart bild med slumpmässigt initierade vita pixlar suddas ut för att hitta de ljusaste och mörkaste delarna, motsvarande tomrum och kluster. Efter att några byten har fördelat de ljusa och mörka delarna jämnt är pixlarna viktiga. Det krävs betydande beräkningsresurser för att generera den blå brusmatrisen: på en modern dator kräver en 64 × 64 -matris ett par sekunder med den ursprungliga algoritmen.

Referenser

^ Bayer, Bryce (11–13 juni, 1973). "En optimal metod för tvånivååtergivning av bilder med kontinuerlig ton" (PDF) . IEEE International Conference on Communications . 1 : 11–15. Arkiverad från originalet (PDF) 2013-05-12 . Hämtad 2012-07-19 .
^ Joel Yliluoma. " Algoritm för positionell dithering av godtycklig palett "
^ Ulichney, Robert A (1993). "Metoden för tomrum och kluster för generering av dither-array" (PDF) . Hämtad 2014-02-11 .
^ Wronski, Bart (31 oktober 2016). "Dithering del tre - verklig värld 2D kvantisering dithering" .
^ Peters, Christoph. "Gratis blå brus texturer" . momentingraphics.de .

Ordered Dithering (grafikprojekt, Visgraf lab, Brasilien)
Dithering -algoritmer (Lee Daniel Crocker, Paul Boulay och Mike Morra)

Vidare läsning

Ancin, Hakan; Bhattacharjya, Anoop K .; Shu, Joseph S. (2 januari 1998). "Förbättra tomrum och kluster för bättre halvtonens enhetlighet". Photonics West '98 Electronic Imaging : 321–329. CiteSeerX 10.1.1.40.5331 . doi : 10.1117/12.298295 .

externa länkar

-implementering av olika (mestadels beställda) dithering -metoder

[bayermatrix-1] Bayer, Bryce (11–13 juni, 1973). "En optimal metod för tvånivååtergivning av bilder med kontinuerlig ton" (PDF) . IEEE International Conference on Communications . 1 : 11–15. Arkiverad från originalet (PDF) 2013-05-12 . Hämtad 2012-07-19 .

[2] Joel Yliluoma. " Algoritm för positionell dithering av godtycklig palett "

[voidcluster-3] Ulichney, Robert A (1993). "Metoden för tomrum och kluster för generering av dither-array" (PDF) . Hämtad 2014-02-11 .

[4] Wronski, Bart (31 oktober 2016). "Dithering del tre - verklig värld 2D kvantisering dithering" .

[5] Peters, Christoph. "Gratis blå brus texturer" . momentingraphics.de .

Languages

In other projects