Beställde dithering

I det här exemplet ( Lenna ) visas originalfotografiet till vänster. Versionen till höger visar effekten av att kvantisera den till 16 färger och vibrering med hjälp av det 8×8 ordnade vibreringsmönstret.

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

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

Tröskelkarta

Algoritmen minskar antalet färger genom att tillämpa en tröskelkarta $M$ på de visade pixlarna, vilket gör att vissa pixlar ändrar färg, beroende på avståndet mellan den ursprungliga färgen från de tillgängliga färgposterna i den reducerade paletten.

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

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

&11&1&9\\15&7&13&5\\\end{bmatrix}}}

{\displaystyle \mathbf {M} ={\frac {1}{16}}\times {\begin{bmatrix}0&8&2&10 \\12&4&14&6\\

{ma} skärm \

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

Godtyckliga tröskelkartor för storlek kan utformas med en enkel regel: Fyll först varje lucka med ett successivt heltal. Ordna sedan om dem så att det genomsnittliga avståndet mellan två på varandra följande siffror på kartan är så stort som möjligt, och se till att bordet "lindar" runt i kanterna. ^{[ citat behövs ]} För tröskelkartor vars dimensioner är en potens av två kan kartan genereras rekursivt via:

\mathbf {M} _{2n}={\frac {1}{(2n)^{2}}}\times {\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}}

Denna funktion kan också uttryckas med endast bitarithmetik:

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 av $n$ × $n$ heltal från 0 till $n^{2}$ , beroende på den exakta hårdvaran som används för att utföra vibreringen, det kan vara fördelaktigt att förberäkna kartans tröskelvärden till ett flyttalsformat, snarare än det traditionella heltalsmatrisformatet som visas ovan.

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

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

Detta genererar en standardtröskelmatris.

för 2×2-kartan:

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

detta skapar den förberäknade kartan:

{\begin{bmatrix}0.0&0.5\\0.75&0.25\\\end{bmatrix}}

Dessutom kan man normalisera värdena för att utjämna deras summa till 0 (som gjorts i vibreringsalgoritmen som visas nedan) även göras under förbehandling 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:

{\begin{bmatrix}-0.5&0.0\\0.25&-0.25\\\end{bmatrix}}

Algoritm

Den ordnade dithering-algoritmen återger bilden normalt, men för varje pixel förskjuter 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 vibrerande ändamål är det tillräckligt att helt enkelt addera tröskelvärdet till varje pixel (utan att utföra normalisering genom att subtrahera 1 ⁄ 2 ), eller motsvarande, för att jämföra pixelns värde med tröskeln: om ljusstyrkan för en pixel är mindre än numret i motsvarande cell i matrisen, plotta den pixeln svart, annars rita den vit. Denna brist på normalisering ökar bildens genomsnittliga ljusstyrka något och gör att nästan vita pixlar inte vibreras. Detta är inte ett problem när man 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 önskvärt, eftersom det mänskliga ögat uppfattar skillnader i mörkare färger mer exakt än ljusare. , ger det 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 gradient på 140 × 140 = 19600 olika färger. Båda bilderna använder samma 64 färger. Bilden till höger har vibrerats. Vibrationen gjordes med hjälp av en icke-normaliserande vibreringsalgoritm, vilket gjorde att bilden fick en lätt överrepresentation av ljusa pixlar.

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

c '=\mathrm {närmast\_palett\_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å den

i

-te raden och

den j

-te kolumnen,

c'

är den transformerade färgen och

r

är mängden spridning i färgrymden. Om man antar en RGB-palett med

2 3 N

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

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

. ( 1 ⁄ 2 är återigen den normaliserande termen.)

Eftersom algoritmen fungerar på enstaka pixlar och inte har några villkorliga uttalanden, är den mycket snabb och lämplig för realtidstransformationer. Dessutom, eftersom placeringen av vibreringsmönstren alltid förblir densamma i förhållande till visningsramen, är den mindre benägen att skaka än felspridningsmetoder, vilket gör den lämplig för animeringar. Eftersom mönstren är mer repetitiva än felspridningsmetoden, komprimeras en bild med ordnad dithering bättre. Ordnad rastrering är mer lämplig för linjegrafik eftersom det kommer att resultera i rakare linjer och färre anomalier.

Värdena som läses från tröskelkartan ska helst skala till samma område som den minimala skillnaden mellan distinkta färger i målpaletten. På motsvarande 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 kvantifierar en 24 bpp-bild till 15 bpp (256 färger per kanal till 32 färger per kanal), skulle den minsta kartan man skulle välja vara 4×2, för förhållandet 8 (256:32). Detta gör det möjligt att uttrycka varje distinkt ton av inmatningen med olika vibrerande mönster. ^{[ citat behövs ]}

En variabel palett: mönstervibrering

Icke-Bayer närmar sig

Ovanstående tröskelmatrismetod beskriver Bayer -familjen av ordnade ditheringalgoritmer. 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 vibrering.

Halvton

Halvtonsvibrering utför en form av klustrad rastrering, vilket skapar ett utseende som liknar halvtonsmönster , med hjälp av en specialgjord matris.

Tomt och kluster

Void and cluster-algoritmen använder ett förgenererat blått brus som matris för vibreringsprocessen. Den blå brusmatrisen håller Bayers bra höga frekvensinnehåll, men med en mer enhetlig täckning av alla inblandade frekvenser visar den en mycket lägre mängd mönstring.

Metoden "voids-and-cluster" har fått sitt namn från matrisgenereringsproceduren, där en svart bild med slumpmässigt initierade vita pixlar är gaussisk suddig 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 numreras pixlarna efter betydelse. 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.

Denna algoritm kan utökas för att göra animerade slingringsmasker som också tar hänsyn till tidsaxeln. Detta görs genom att köra algoritmen i tre dimensioner och använda en kärna som är en produkt av en tvådimensionell gausskärna på XY-planet och en endimensionell gausskärna på Z-axeln.

^ Bayer, Bryce (11–13 juni 1973). "En optimal metod för återgivning på två nivåer av bilder med kontinuerliga toner" ( PDF) . IEEE International Conference on Communications . 1 :11–15. Arkiverad från originalet (PDF) 2013-05-12 . Hämtad 2012-07-19 .
^ Joel Yliluoma. " Algorithm för positionsvibrering med godtycklig palett "
^ Ulichney, Robert A (1993). "Void-and-cluster-metoden för generering av dither array" (PDF) . Hämtad 2014-02-11 .
^ Wronski, Bart (31 oktober 2016). "Dithering del tre – verkliga 2D-kvantiseringsdithering" .
^ Peters, Christoph. "Gratis blåbrustexturer" . momentsingraphics.de .
^ Wolfe, Alan; Morrical, Nathan; Akenine-Möller, Tomas; Ramamoorthi, Ravi (2022). Spatiotemporal Blue Noise Masks . Eurographics Association. doi : 10.2312/sr.20221161 . ISBN 978-3-03868-187-8 . S2CID 250164404 .

Beställd dithering (Grafikkursprojekt, Visgraf lab, Brasilien)
Dithering-algoritmer (Lee Daniel Crocker, Paul Boulay och Mike Morra)

Vidare läsning

Ancin, Håkan; Bhattacharjya, Anoop K.; Shu, Joseph S. (2 januari 1998). "Förbättra void-and-cluster för bättre halvtonslikformighet". Photonics West '98 Electronic Imaging . 3300 : 321–329. Bibcode : 1998SPIE.3300..321A . CiteSeerX 10.1.1.40.5331 . doi : 10.1117/12.298295 . S2CID 6219511 .

externa länkar

Matlab implementering av olika ditheringsmetoder
anim8gdx , Java-implementering av olika (oftast ordnade) ditheringsmetoder

[bayermatrix-1] Bayer, Bryce (11–13 juni 1973). "En optimal metod för återgivning på två nivåer av bilder med kontinuerliga toner" ( 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. " Algorithm för positionsvibrering med godtycklig palett "

[voidcluster-3] Ulichney, Robert A (1993). "Void-and-cluster-metoden för generering av dither array" (PDF) . Hämtad 2014-02-11 .

[4] Wronski, Bart (31 oktober 2016). "Dithering del tre – verkliga 2D-kvantiseringsdithering" .

[5] Peters, Christoph. "Gratis blåbrustexturer" . momentsingraphics.de .

[6] Wolfe, Alan; Morrical, Nathan; Akenine-Möller, Tomas; Ramamoorthi, Ravi (2022). Spatiotemporal Blue Noise Masks . Eurographics Association. doi : 10.2312/sr.20221161 . ISBN 978-3-03868-187-8 . S2CID 250164404 .