Technika półtonów – Dithering

Wreszcie będzie coś dla prorgamistów, po całej serii postów o różnych linuksach. Doszedłem do wniosku, że za dużo już pisałem o systemach i wypadałoby wreszcie wziąć się za programowanie. Z pomocą przyszła mi pani prowadząca zajęcia ze Wstępu do Przetwarzania Sygnałów i Obrazów. Moim zadaniem było zapoznanie się z techniką generowania obrazu metodą półtonów i napisania odpowiedniego programu na tę okoliczność.

Obraz ma być w skali szarości ale system powinien zadziałać również dla normalnych obrazków RGB jeśli zastosujemy sposób do każdego kanału osobno. Efekt działania takiego algorytmu wygląda następująco:

Z lewej obraz oryginalny, z prawej przetworzony

Cały pomysł na zamianę polega na tym, aby podzielić obraz źródłowy na małe kwadraty pikseli (u mnie 3×3 piksele), a następnie dla każdego z tych pikseli wybrać czy ma on być zamalowany na czarno czy na biało. W jaki sposób określić, który piksel ma być jaki?

Na stronie http://wwwhome.cs.utwente.nl/~schooten/graphics/ opisany jest sposób dla bloków 2×2 piksele oraz skali szarości w przedziale od 0 do 1. Autor sugeruje stworzenie macierzy 2×2 zawierającej… hmm… odchylenie? Zachęcam do zapoznania się z jego artykułem gdyż chciałbym jedynie przedstawić ten sposób dla bloku 3×3 piksele oraz skali szarości od 0 do 255.

Jeśli mamy blok 3×3 piksele to jeśli zamalujemy wszystkie na biało to oczywiście otrzymamy kolor biały (tu akurat łatwo wszystkich przekonać 😉 ). Jeśli zamalujemy wszystkie piksele na czarno to będziemy mieli kolor czarny. Jeśli zamalujemy jeden z pikseli na czarno, a resztę na biało to patrząc z daleka będzie nam się wydawało, że blok jest troszeczkę szary. W ten sposób (zamalowując kolejne piksele na czarno) możemy stworzyć 10 poziomów szarości dla bloku 3×3. Poniżej przedstawiam przykładową reprezentacje poziomów 1, 5 oraz 9:

Poziomy 1, 5 i 9

Teraz należy stworzyć tablicę odchylenia dla pikseli z danego bloku. Aby to zrobić trzeba najpierw rozłożyć naszą skalę szarości (0-255) na 9 przejść pomiędzy poziomami. Dla N poziomów mamy N-1 przejść – jeśli ktoś ma problem ze zrozumieniem dlaczego to niech narysuje sobie 10 słupków od ogrodzenia i policzy ile jest potrzebnych części płotu pomiędzy słupkami 😉 – te części to przejścia. Wykonajmy dzielenie: 255/9 = 28,(3).  Ten wynik nie jest zbyt piękny, ale wystarczy, że zaokrąglimy sobie do dwóch miejsc po przecinku. Otrzymaliśmy zatem 28,33.

Teraz jest najciekawiej. Jeśli narysujemy sobie wszystkie możliwe poziomy szarości dla bloku 3×3 i odrzucimy skrajne (tzn. cały czarny i cały biały) to łatwo będzie stworzyć tablicę odchyleń. Patrzymy zatem na poziomy 1-8. Tablica odchyleń oczywiście też musi być wielkości 3×3. Teraz patrzymy na pierwszy piksel po lewej na górze (poziom 1). Co w tym miejscu wpisać w tablice odchyleń? Wystarczy policzyć na ilu poziomach ten piksel jest czarny (oczywiście patrząc wyłącznie na poziomy pośrednie [1-8]) . W przypadku lewego górnego – jest on czarny na wszystkich 8 poziomach zatem w tablicę odchyleń wpisujemy dla niego wartość ~(8*28.33). Warto ją zaokrąglić 🙂 Podobnie postępujemy dla kolejnych pikseli. W końcu otrzymujemy macierz postaci:

Macierz odchyleń

Mając taką macierz wystarczy już tylko do każdego piksela dodać odpowiadającą mu wartość z powyższej macierzy i później sprawdzić czy ma on wartość większą niż 255. Jeśli tak to ustawiamy ten piksel na kolor biały (255) jeśli nie to ustawiamy go na kolor czarny (0). W ten sposób otrzymaliśmy dość ciekawy obraz oraz zmniejszyliśmy ilość potrzebnych kolorów do dwóch (biały i czarny) zachowując przy tym 10 poziomów szarości.

Nie jest to może najpiękniejszy obraz ale efekt powinien być dobrze znany starszym graczom, którzy w dzieciństwie na takie cuda się napatrzyli 🙂

Na koniec podam jeszcze ostateczny algorytm w pseudokodzie w C++:

int bias[3][3] = {
   { 227, 198, 170 },
   { 142, 113, 85  },
   { 57 , 28 , 0   }
};
int value;
for(int y=0; y < in.height(); y++) {
   for(int x=0; x < in.width(); x++) {
      value = in.pixel(x,y) + bias[y%3][x%3];
      if(value > 255) value = 255;
      else value = 0;
      out.setPixel(x, y, value);
   }
}

Podczas pracy algorytmu dość istotne jest w jakim formacie jest zapisany obraz. Powyżej założyłem, że do zapisu każdego piksela wykorzystane zostało 8 bitów informujących o skali wartości w skali szarości.

Reklamy

14 myśli nt. „Technika półtonów – Dithering

    • Hmm. Ja mam dokładnie w ten sposób u siebie i tak wygenerowałem ten obrazek z modelką więc chyba jednak się da 🙂

      Faktycznie jednak powinno być >= bo kolor biały powinien białym pozostać 🙂

      Ja też nie wiedziałem, że to takie proste 😛 Musiałem się jednak tego dowiedzieć aby zrobić zadanie na WdPSiO 😉

  1. Jeszcze jak tak sobie myślę, jak ten efekt jest generowany to wydaje mi się, że ta tabelka ma nie najtrafniej dobrane wartości.

    Żeby cały kwadrat 3×3 był czarny po tym przekształceniu, to w danym miejscu mogą być szarości z przedziału [0, 27], podobnie dla kolejnych jasności szarości. Natomiast kolor biały powstanie tylko dla wartości 255 i żadnej innej. Co wydaje się być troszeczkę statystycznie niesprawiedliwe 🙂

    Chyba lepiej by było wpisać do tej tabelki wartości w postaci: (255 / 10) * (i + 1)
    gdzie i = (2 – x) + (2 – y) * 3 (x,y z przedzialu [0, 2])

    • @kermidt:

      Hmm.. odkryłem właśnie że macierz powinna być odbita symetrzycznie względem linii z lewego dolnego do prawego górnego rogu… Bo tak jak teraz to obrazuje sytuację w której piksel czarny najczęściej występuje po prawej na dole… 🙂

      Tutaj raczej jest tak, że wartości z tej macierzy definiują jakby prawdopodobieństwo że dany piksel będzie biały.

      Zwracam uwagę, że kazdy piksel ma wartość jakąś z przedziału [0,255] no i teraz jeśli dodam odpowiadającą mu wartość z macierzy to wówczas mogę otrzymać liczbę nawet większą od 255. (dlatego tymczasowo zapisuję w int a nie char [ale możnaby short 😉 ]) no i po takim sumowaniu jak będzie liczba większa albo równa 255 to wówczas będzie to biały (wrzucam wartość 255) a jeśli będzie z przedziału [0,255) to wyświetlam czarny piksel.

      Nie jestem do końca pewien co do Twoich wyliczeń bo nie potrafię sobie wyobrazić skąd się takie wartości wzięły 😉

      • Jak odbijesz tą macierz to czarny piksel będzie najczęściej występował w górnym lewym rogu. Więc niewielka różnica 🙂
        Za to pewne uśrednienie dałoby losowe permutowanie elementów tej macierzy po każdym przerobionym kawałku 3×3

        Postaram się wytłumaczyć mój poprzedni wywód.
        Wyobraźmy sobie grupę pikseli 3×3 w której każdy piksel jest tej samej szarości o wartości SZ
        dla SZ z przedziału [0-27] uzyskujemy w efekcie cały kwadrat 3×3 czarny
        dla SZ z przedziału [28-56] uzyskamy w efekcie kwadrat 3×3 z jednym pikselem białym
        itd dla kolejnych wartości
        natomiast tylko dla SZ == 255 uzyskamy w efekcie CAŁY kwadrat 3×3 biały co według mnie powoduje, że nierównomiernie korzystamy z dostępnych „kolorów” wynikówych.

        Dla macierzy policzonej moim wzorkiem 255 * (i + 1) / 10 dla i [0-8] każdy „kolor” wynikowy będzie równie prawdopodobny. (Tak mi się przynajmniej wydaje 🙂 )

  2. @kermidt: Twój sposób też działa i faktycznie rozkład jest w miarę równomierny (sprawdziłem na gradiencie).

    Wczoraj na zajęciach odkryłem jednak, że aby poprawić trochę jakość tych obrazków wystarczy zwiększyć wszystkie wartości mojej macierzy o 15. Wówczas czarny i biały występują niewiele rzadziej niż pozostałe kolory, ale za to uzyskuje się trochę lepszy „kontrast” – rzeczy bardzo ciemne i bardzo jasne mają rozpoznawalne kształty – nie są czarną/białą plamą 🙂

    • Przy pomocy znaczników: [ sourcecode language=”cpp”] jakis kod [/sourcecode] Tylko bez spacji po pierwszym ‚[‚. Musiałem dać bo inaczej otrzymałbym coś takiego:

       jakis kod 
  3. Greetings from Carolina! I’m bored at work so
    I decided to browse your site on my iphone during lunch break.
    I really like the knowledge you present here and can’t wait to take a look when I get home.
    I’m amazed at how quick your blog loaded on my phone
    .. I’m not even using WIFI, just 3G .. Anyways, amazing blog!

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s