Dithering i C# (PGM)

Niecały rok temu opublikowałem wpis o ditheringu, w którym w zasadzie nic prócz pokazania efektów tego cudu "nowoczesnej" technologii nie pokazałem. Dziś zamierzam to naprawić poprzez:

• udostępnienie biblioteki, wykonującej obsługującej proces ditheringu (póki co na plikach PGM) przy użyciu metod:
• Random
• Threshold
• Ordered
• Floyd-Steinberg
• "fałszywy" Floyd-Steinberg (czasem opisywany jako Floyd-Steinberg - stąd "fałszywy")
• Jarvis-Judice-Ninke
• Stucki
• Burkes
• Sierra
• zgrubny opis owych metod wraz z przykładowymi efektami ich działania
• W najbliższym zaś czasie dorzucę kilka własnych metod będących mniej lub bardziej efektem mych eksperymentów :)

Biblioteka

Obsługa ditheringu została dodana jako statyczna klasa (Transform.Dither) biblioteki Runaurufu.Drawing (do pobrania z chomika) i w obecnym kształcie zawiera metody:

public static class Dither
{
    public static PgmImage Threshold(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Random(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Ordered(PgmImage img, UInt16[] box, UInt16 newMaxColor){...}
    public static PgmImage Ordered2(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Ordered3(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Ordered4(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Ordered8(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Ordered16(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage FloydSteinberg(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage FalseFloydSteinberg(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage JarvisJudiceNinke(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Stucki(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Burkes(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Sierra3(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Sierra2(PgmImage img, UInt16 newMaxColor){...}
    public static PgmImage Sierra24A(PgmImage img, UInt16 newMaxColor){...}
}

Metody Ordered2 - Ordered16 wywołują metodę Ordered z wykorzystaniem predefiniowanych tablic kwadratowych o boku równym numerowi znajdującemu się przy nazwie metody (Ordered2 - tablica 2x2).

Metody Threshold i Ordered wykorzystują zrównoleglenie (Parallel.For) - niestety metody z propagacją błędu nie są w stanie z daru wielowątkowości skorzystać.

Opis metod

Oryginalny obraz

Oryginalny obraz w odcieniach szarości

Nie będę się tu zagłębiał w to po co powstał dithering, ani czym jest - bo na pierwsze pytanie można napisać rozprawę naukową i dość dobry ogląd sytuacji przedstawia nam choćby Wikipedia, a na pytanie czym jest odpowiedź znaleźć można w poniższym opisie wybranych metod. Dodatkowo dla porównania załączyłem obrazy będące wynikiem działania każdego z algorytmów na obrazie przykładowym złożonym z 4 elementów (w tle gra Civilization V, a z przodu przykładowe pingwiny z Windowsa oraz popularne obrazy - Lena i rzeźba Dawida dłuta Michała Anioła):

Threshold

Threshold dithering

Jedna z prostszych metod ograniczania ilości kolorów obrazu. Polega na rzutowaniu wartości mniejszych od pewnego wybranego progu (ang. threshold - próg, wartość progowa) na jedną zadaną wartość, a wartości większych lub równych na wartość inną (np. 0 i 255). Zazwyczaj wartość progu określa się jako medianę dostępnych wartości (128 = 256/2). Metoda ta ma tą zaletę, że jest szybka i bardzo łatwa do zrównoleglenia. Niestety wiele do życzenia pozostawia efekt końcowy w przypadku zdjęć o zróżnicowanej kolorystyce.

Random

Random dithering

Kolejna prosta metoda, która tym razem wykorzystuje losowo generowaną wartość progową (losowe wartości mogą znajdować się w takim samym zakresie jak wartości dla poszczególnych pikseli). Dla każdego piksela próg jest generowany osobno, co redukuje możliwość powstawania różnego rodzaju powtarzających się wzorów, jednak z tego samego powodu nie ma praktycznej możliwości dwukrotnego wygenerowania takich samych obrazów bez zapisania również wszystkich użytych progów.

Ordered

Ordered dithering ze wzorem 16x16

Metoda uporządkowanego ditheringu jest jedną z metod związanych z używaniem pewnych wzorów, które "nakłada się" na obraz poddawany obróbce. W tym przypadku wartości progowe pochodzą właśnie z owego wzoru, który powtarza się tak horyzontalnie jak i wertykalnie - stąd też biorą się podobnie rozlokowane artefakty. Zaletą algorytmu jest łatwość zrównoleglenia, która w połączeniu z całkiem dobrymi rezultatami wizualnymi tej metody okazuje się idealnym rozwiązaniem w przypadku wielordzeniowych systemów.

Floyd-Steinberg

Floyd-Steinberg

Z metod związanych z propagacją błędu omówię jedynie metodę Floyda-Steinberga. Dlaczego? A z tej prostej przyczyny, że pozostałe (a mówiąc wprost - pochodne) różnią się wyłącznie pozycjami i wartościami ułamku błędu.
Metoda ta opiera się na wykryciu błędu między wartością piksela (konkretnych kolorów w pikselu) oryginalnego obrazu, a wartością w obrazie przetworzonym.

Opis propagacji błędu
w metodzie Floyda-Steinberga
gwiazdką (*) oznaczono
aktualnie przetwarzany piksel

Owa różnica - błąd kwantyzacji - jest następnie rozdzielana wg zdefiniowanej tablicy (zaprezentowanej obok) na sąsiednie nieprzetworzone piksele. Wadą tej metody jest kompletna niezdolność do zrównoleglenia - algorytm musi przejść piksel po pikselu - która jednak jest niejako zacierana przez niesamowite efekty uzyskiwane dzięki tej metodzie. Za konceptem propagacji błędu stoi proste spostrzeżenie - zarówno wartość 0 jak i 120 zostaną zrzutowane na 0, co sprawia, że obraz z szarego staje się czarny. Jeśli jednak mamy 3 kolejne piksele o wartości 120, to wynikiem pracy tego algorytmu nie będzie ciąg {0,0,0}, ale ciąg {0, 255 (120 + 52.5), 0 (120 - 82.5)}, który o wiele lepiej prezentuje szarość.

Stucki dithering

Pochodne metody różnią się jedynie wartościami, liczbą i pozycją ułamków błędu kwantyzacji.

Bibliografia

Czyli co warto przeglądnąć w poszukiwaniu informacji o ditheringu...

• Wikipedia - czyli dobry wstęp do rozpoczęcia przygody z tą tematyką
• Praca Lee Daniela Crockera (rozszerzona przez Paula Boulaya oraz Mike Morra) - opisuje dobrze zarówno historię całej idei ditheringu jak i wyżej omawiane algorytmy. (mirror)
• Joel Yliluoma's arbitrary-palette positional dithering algorithm - strona z przykładami i kodami źródłowymi w PHP. Przydatna do porównania różnych algorytmów - również przy zastosowaniu w filmie.
• Image Based Artistic Dithering - praca  studentów z PUC w Rio, może nie odkrywcza, ale jeśli ktoś zaczyna przygodę z tą tematyką to może się przydać (choć jak ktoś faktycznie chce ugryźć temat to o wiele lepiej zacząć od pracy Lee Daniela Crockera)