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.

C#

Od jakiegoś czasu zastanawiałem się co takiego fenomenalnego jest w C#, że wszyscy go chwalą. No dobra, nie wszyscy, ale wielu. Postanowiłem więc sprawdzić to na własnej skórze.

Ściągnąłem i zainstalowałem Microsoft Visual C# Express Edition 2008. Po odpaleniu na pierwszy rzut oka jedynym szczegółem, który odróżnia VC# od VC++ jest kolor zielony splash screen’a podczas gdy ten z VC++ jest żółty ^^

Postanowiłem stworzyć nowy projekt w celu testów. Kiedy moim oczom ukazała się wreszcie forma na której mogłem umieścić kontrolki, zaszalałem… Umieściłem jeden przycisk. Na początek chciałem sprawić aby po wciśnięciu przycisku pojawił się mały prosty Message Box. Dzięki świetnemu uzupełnianiu składni okazało się to prostsze niż napisanie „Hello world” w konsoli ^^

W dalszej części testu pomęczyłem jeszcze kilka innych kontrolek sprawdzając z czym się je zajada 😉 Jako, że nic mądrego nie mam na ten temat do powiedzenia – przejdę do następnej kwestii 😛

Teraz chciałbym się pozachwycać trochę uzupełnianiem składni i „zgadywaniem” przez VC# tego co chcę wpisać. Bardzo fajną rzeczą podczas powoływania do życia nowego obiektu za pomocą new jest automatyczne zgadywanie konstruktora. Polega to na tym, że po wpisaniu operatora new i spacji od razu pojawia się okienko z podpowiedziami z zaznaczonym konstruktorem klasy znajdującej się po lewej stronie `=` (który oczywiście jest przed new 😉 ).

Następnym udogodnieniem, które bardzo mi przyspieszyło pisanie aplikacji testowej było zgadywanie nazw zmiennych. Jeśli na przykład używałem ostatnio zmiennej o nazwie „zmienna” to wpisując „z” w edytorze od razu pojawi się okienko z podpowiedzią i zaznaczoną nazwą: „zmienna” (nawet jeśli w porządku leksykograficznym nie będzie to pierwsza zmienna na `z`). To pomaga zwłaszcza podczas korzystania ze struktur. Wpisując pierwszą literę nazwy obiektu jakiejś struktury od razu pojawi się okienko `dobrą` podpowiedzią (jeśli już wcześniej użyliśmy tej nazwy) – wtedy wystarczy już tylko wcisnąć `.` i do edytora zostanie wpisana cała nazwa obiektu razem z kropką i dodatkowo wyświetlone zostaną elementy struktury (co już raczej nikogo nie dziwi 😉 ).

Jako ostatnią rzecz, która mnie  w VC# zachwyciła wymienię tą, która zaskoczyła mnie jako pierwsza. Jest nią szybkość kompilacji kodu. Tak niesamowite tempo kompilacji po prostu wgniotło mnie w fotel!

Istnieje jednak pewna sprawa, która jest trochę irytująca i jak dla mnie trochę brzydko wygląda w kodzie. Chodzi mi o dodawanie `private` lub `public` przed każdą zmienną i metodą.

Podsumowując: Moja ocena C# jest bardzo pozytywna. Dla programistów C++ prawdopodobnie pomocna będzie ta strona.

BTW: dzisiaj czytałem art o tworzeniu zegara analogowego w C#. Artykuł byłby całkiem w porządku gdyby nie fakt, że autor bardzo beztrosko podchodził do pamięci zarówno komputera jak i czytelnika. Powinienem tutaj wyjaśnić co miałem na myśli mówiąc o pamięci czytelnikowej. Otóż chodziło mi o to, że autor artykułu używał 1000 zamiennych, kiedy tak na prawdę mógł pracować na zaledwie kilku.

Szczytem tej techniki było zaimplementowania przesuwania okna przez złapanie okna w dowolnym punkcie i przesuniecie myszki. Autor użył do tego 5 zmiennych podczas gdy mi wystarczyły tylko dwie.

PS.: Musiałem napisać o tym arcie żeby mi ulżyło bo strasznie mnie to piekło 😉

Pascal

W końcu na studiach zostałem zmuszony do nauczenia się Pascal’a. Nigdy wcześniej nie chciało mi się tego uczyć bo i po co? Na lekcjach informatyki w liceum pisałem wszystko w C i nauczyciel nic do tego nie miał.

Teraz jednak już trzeba się go nauczyć. Jako, że programuję już około 7 lat w C++, myślałem że nauka Pascala będzie mnie męczyć i denerwować. Myliłem się chociaż nie jest to język specjalnie ciekawy ani ładny.

Wg mnie Pascal to zabawka dla dzieci i naukowców, którym nie chce się ( albo nie potrzebują ) uczyć się prawdziwego języka programowania albo chociaż jakiegoś poważniejszego języka skryptowego. Jest to język zawierający masę niepotrzebnych udogodnień, że nie wspomnę już o tym że jest po prostu brzydki.

Chcąc rozwinąć nieco te zarzuty o niepotrzebnych udogodnieniach wymienię chociażby stwór o nazwie SET. Zupełnie nie wiem dlaczego jest to część języka. Równie dobrze można by było to jakoś „okodzić” na tablicach. Dodatkowo zupełnie nie widzę potrzeby stosowania typów okrojonych oraz indeksowania tablic zaczynając od dowolnej liczby.

Jeśli chodzi o estetykę języka – IMHO jest okropny. BEGIN oraz END są różnej długości co daje blokowi instrukcji nieprzyjemny wygląd:

BEGIN
i := 5;
END .

Instrukcja przypisania też mi się nie podoba bo jest niewygodna do pisania ale już tego czepiać się nie będę. Następna rzecz składniowa która mnie denerwuje to blok VAR:

VAR    i, j : integer;
r : real;

Jak by człowiek nie próbował tego zapisywać zawsze wygląda szpetnie. Druga sprawa, że zmienne muszą być zadeklarowane w tym bloku i nie można ich deklarować później w kodzie w żaden sposób. Powoduje to często (przynajmniej u mnie) odrywanie się od kodu tylko po to żeby dodać jedną zmienną i przy okazji się rozproszyć 😐

Takie rozwiązanie z blokiem zmiennych jest dobre jeśli się pisze jakiś algorytm na podstawie schematu blokowego. Wskażcie mi programistę, który robi schematy blokowe do programów które pisze… Musi być masochistą albo człowiekiem cierpiącym na nadmiar czasu.

Ja często piszę kod  „na żywca” i nie potrzebuję się dodatkowo rozpraszać dodawaniem zmiennej tam gdzie trzeba bo w międzyczasie mogę stracić wątek i będzie klops.

Nie dziwię się, że `młodzi` programiści mają problem z przestawieniem się na Pascala skoro jest tam tyle udogodnień wbudowanych, że później ciężko się pogodzić z ich utratą. Może dlatego panuje przekonanie, że C++ jest taki strasznie trudny.  Jeśli tak to można pójść dalej w tych rozważaniach i stwierdzić, że nauczyciele robią krzywdę uczniom przekazując im wiedzę dotyczącą Pascala.

Dlatego cieszę się, że sam się pokarałem książką o C++ w młodości i teraz mogę się cieszyć tym, że mogę pobawić się w Pascalu, w którym zdecydowanie łatwiej tworzy się małe programiki.

Wniosek z tego jeden: z programowaniem jest jak z pływaniem w morzu, lepiej rzucić się na głęboką wodę i płynąć w stronę brzegu niż na odwrót ^^

C++ Sockets Library

Kiedy wreszcie postanowiłem napisać jakiś kawałek kodu dla ageNet i dla ułatwienia sobie życia wykorzystać przy tym C++ Sockets Library to okazało się, że kompilacja tego cuda nie jest możliwa ponieważ:

1>g:\\libs\\sockets-2.1.7\\sockethandler.cpp(447) : error C2065: 'EINVAL' : undeclared identifier
1>g:\\libs\\sockets-2.1.7\\sockethandler.cpp(447) : error C2065: 'EINTR' : undeclared identifier
1>g:\\libs\\sockets-2.1.7\\sockethandler.cpp(447) : error C2065: 'EBADF' : undeclared identifier
1>g:\\libs\\sockets-2.1.7\\sockethandler.cpp(447) : error C2065: 'ENOMEM' : undeclared identifier

Na szczęście są w świecie ludzie, którzy wiedzieli w czym rzecz i opisali to w internecie. Dzięki jednemu z nich problem został szybko rozwiązany. Nie mogłem się jednak nacieszyć tym osiągnięciem ponieważ chwilę później pojawił się nowy błąd!

1>LINK : fatal error LNK1181: cannot open input file 'ssleay32md.lib'

Zupełnie nie wiem dlaczego w pakiecie openssl-lib, który zassałem z internetu nie ma tego pliku… Wizja kompilacji OpenSSL ze źródeł strasznie mnie wkurza, bo zapewne pojawią się nowe zależności przez które się ona nie powiedzie…

Wytłumaczenie

Ok, ostatnio trochę zaniedbałem stronę oraz sam piękny fach programistyczny. Dlaczego? Prawdę mówiąc sam chciałbym to wiedzieć. Zdaje się że brak mi pomysłu na napisanie modułu ageNet – o którym wspominałem na mojej poprzedniej stronie jak jeszcze działała…

Jeśli mam być szczery to nie wiem co taki moduł powinien udostępniać programiście bo sam nigdy z takiego nie korzystałem, a grę przez internet napisałem tylko jedną i to z użyciem czystych socketów 😉

Postanowiłem jednak zmienić istniejący stan rzeczy i zabrać się wreszcie za coś konkretnego. Ostatnio Tarains zmotywował mnie do tego, żeby odświeżyć nieco moją stronę internetową, a teraz przyszedł czas żebym sam wziął się do roboty 😉 Co przez to rozumiem? Otóż postanowiłem się przyjrzeć jak wygląda moduł SDL_Net i na jego podstawie napisać ten nieszczęsny ageNet – może wreszcie coś ruszy się do przodu 🙂