Nazwałem ten projekt “Fotoszop” oczywiście ze względu na prawną ochronę nazwy handlowej programu Photoshop firmy Adobe…

Pierwsze komputery powstały nie jako teoretyczne zabawki, tylko jako odpowiedź na bardzo konkretne problemy:

• Jak sprawnie wykonywać rachunki?
• Pod jakim kątem wystrzelić torpedę, aby trafić poruszający się okręt?
• Jak złamać szyfr wroga?

Wychodząc z podobnego założenia chciałbym, umożliwić Ci w ramach przedmiotu “Programowanie komputerów” poćwiczyć pisanie programów służących czemuś bardziej praktycznemu niż wypisywanie “Hello world!” na ekran.

Program powstały w ramach projektu Fotoszop, jak nazwa sugeruje, będzie służył do pracy z obrazami. W ramach kolejnych ćwiczeń laboratoryjnych zaimplementujesz¹⁾ fragmenty kodu służące do wczytywania/zapisu danych obrazu oraz do operowania na pikselach. Umożliwi Ci to wykonywanie takch operacji jak: rozmycie (zmniejszenie ostrości) obrazu, znajdowanie krawędzi na obrazie, tworzenie fraktali – i co Ci jeszcze przyjdzie do głowy

Podczas realizacji projektu zapoznasz się z różnymi problemami, które występują podczas pisania programu z prawdziwego zdarzenia.
Będziesz pracować z rodzajem “dokumentacji”, zawierającej wskazówki i wytyczne odnośnie wymaganej funkcjonalności.

Projekt będzie tworzony zgodnie z regułą KISS, stąd:

• program będzie obsługiwał tylko obrazy w odcieniach szarości w 8-bitowej głębi koloru, zapisane w formacie BMP
• pewna część funkcjonalności programu – wymagająca wiedzy wykraczającej poza ramy przedmiotu – zostanie dostarczona (przez prowadzącego)

Ograniczenie “obrazy w odcieniach szarości w 8-bitowej głębi koloru” pozwala na znaczne uproszczenie zadań – dzięki temu obraz może być reprezentowany jako dwuwymiarowa tablica wartości z zakresu $[0,255]$. Wartości przykładowych kolorów ze skali szarości:

Program korzysta z osobnej biblioteki służącej do odczytu i zapisu danych z pliku bitmapy²⁾. W zależności od laboratorium biblioteka ta zawiera również pewne dodatkowe funkcje (np. służące do tworzenia nowego obrazu wewnątrz programu).

Aby móc używać tejże biblioteki, na początku kodu programu znajduje się linia:

#include "bitmap.h"

Pliki bitmap, na których operuje program, powinny znajdować się w katalogu imgs.
Aby załadować inny obraz niż domyślny (lena.bmp) zmień odpowiednio pierwszy argument funkcji load_bitmap().
Podobnie aby zapisać przetworzony obraz do innego pliku niż domyślny (lena-out.bmp) zmień odpowiednio pierwszy argument funkcji save_bitmap().

Ponieważ zgodnie z ograniczeniami wartość piksela zawiera się w przedziale $[0,255]$, do jego reprezentacji wystarczy jeden bajt – można użyć więc typu unsigned char.

Aby jednak intencja programisty była jasna – że chodzi o piksel – został zdefiniowany typ byte jako alias dla unsigned char. Oznacza to, że zamiast pisać w każdym miejscu unsigned char, można po prostu napisać byte, natomiast dla kompilatora oznacza to dokładnie to samo (1-bajtowa liczba całkowita bez znaku).

Alias utworzono z użyciem instrukcji

typedef unsigned char byte;

1. Filtracja -- Rozmycie obrazu

W tym ćwiczeniu nie interesują Cię szczegóły wczytywania i zapisu danych. Twoim zadaniem jest zaimplementowanie filtru powodującego rozmycie obrazu.

Do realizacji zadań pobierz i rozpakuj folder projektu: fotoszop-ex1.zip
Podczas realizacji zadań wykorzystaj ten projekt jako szkielet swojego programu.

W niniejszym ustępie $y$ odnosi się do współrzędnej związanej z wysokością obrazu, a $x$ – z szerokością. Skorzystano z notacji tablicowej (najpierw wysokość, potem szerokość), aby ułatwić przełożenie tej teorii na język programowania.

W ogólnym ujęciu filtrowanie opiera się na prostej zasadzie:
Wartości danego piksela obrazu wyjściowego, $O(y,x)$, zależy – w pewien określony przez nas sposób – od wartości zarówno tego piksela w obrazie wejściowym, $I(y,x)$, jak również od wartości (w obrazie wejściowym) pikseli znajdujących się w jego najbliższym otoczeniu (zacienione piksele na obrazie $I$).

Zależność ta określona jest przez tzw. maskę, czyli macierz współczynników-wag pikseli otoczenia. Maska to zazwyczaj macierz kwadratowa, o nieparzystych wymiarach – ułatwia to obliczenia komputerowe.

Ściślej, dla maski o rozmiarze $n \times n$ (przy czym $n = 2k+1$ – a więc maska ma rozmiar nieparzysty), filtrację określa zależność: $$O(y,x) = \sum\limits_{i = -k}^{k} \sum\limits_{j = -k}^{k} I(y+i,x+j) \cdot W(i+k,j+k)$$ gdzie

• $O(y,x)$ – piksel obrazu wyjściowego o współrzędnej $(y,x)$
• $I(y,x)$ – piksel obrazu wejściowego o współrzędnej $(y,x)$
• $W$ – maska

Powyższy wzór to nic innego jak mnożenie dwóch macierzy – odpowiedniego wycinka obrazu i maski. Dla przypadku $3 \times 3$ wygląda to następująco:

W przypadku filtra uśredniającego zależnością tą jest po prostu matematyczna średnia. Działanie filtru uśredniającego polega zatem na ustawieniu wartości danego piksela na podstawie uśrednionej (w pewien sposób) wartości pikseli znajdujących się w najbliższym otoczeniu tego piksela. Prowadzi to do zmniejszenia różnic między kolorami (odcieniem szarości) sąsiednich pikseli, a więc do zmniejszenia kontrastu obrazu – innymi słowy do jego rozmycia.

W tym ćwiczeniu zrealizuj najprostszy filtr uśredniający – wykorzystujący średnią arytmetyczną (wartości sąsiednich pikseli). Jak pewnie pamiętasz, średnia arytmetyczna $n$ liczb to: $$ \bar{a} = \frac{a_1 + a_2 + \cdots + a_n}{n} = \frac{1}{n}a_1 + \frac{1}{n}a_2 + \cdots +\frac{1}{n}a_n $$

Oznacza to, że w przypadku naszego filtra uśredniającego maska o wymiarach $3 \times 3$ składa się z $3 \cdot 3 = 9$ współczynników o wartości $\frac{1}{9}$:

• Utwórz tablicę mask o rozmiarze $n \times n$. Do określenia rozmiaru użyj stałej symbolicznej N.

Stała symboliczna została utworzona derektywą preprocesora #define

#define N   3

Preprocesor to program uruchamiany przed właściwą kompilacją (stąd jego nazwa: preprocesor), a zajmuje się on m.in. dołączaniem plików nagłówkowych (poprzez znaną Ci derektywę #include). Derektywa #define mówi “zamień w tekście programu ciąg znaków po lewej stronie na ciąg znaków po prawej stronie”. W tym przypadku – ciąg znaków N na ciąg znaków 3.
Zatem po tym, jak preprocesor skończy swoją robotę, kod

int a = N + 5;

wygląda następująco (to widzi kompilator):

int a = 3 + 5;

Preprocesor działa więc momentami jak cenzor, którzy przed dostarczeniem listu do adresata zmienia to i owo – coś wykreśla, coś dodaje…

• Zainicjalizuj maskę odpowiednimi wartościami (zależnymi od $n$ – ponownie użyj stałej symbolicznej N) z użyciem pętli for.

• Sprawdź poprawność swojego kodu przez wypisanie wartości tablicy na ekran. Wynik powinien wyglądać następująco:

0.11 0.11 0.11 
0.11 0.11 0.11 
0.11 0.11 0.11 

• Zaimplementuj operację filtrowania obrazu z użyciem maski utworzonej poprzednim zadaniu.

Obraz wejściowy przechowywany jest w zmiennej input_image jako tablica o wymiarach $h \times w$ (gdzie $h$, $w$ to odpowiednio wysokość i szerokość obrazu).
Mimo, że zmienna input_image została zadeklarowana jako wskaźnik do wskaźnika do byte (byte**), w tym przypadku możesz z niej korzystać jak ze zwykłej tablicy dwuwymiarowej (o wskaźnikach dowiesz na kolejnym laboratorium).
W podobny sposób został zdefiniowany obraz wynikowy output_image.

Wysokość i szerokość obrazu przechowywana jest odpowiednio w zmiennych imHeight i imWidth.

Do realizacji operacji filtracji możesz skorzystać z wielokrotnie zagnieżdżonej pętli for.

Zwróć uwagę na zakres współrzędnych $x$ i $y$ dla którego przedstawiona w części teoretycznej definicja filtrowania ma sens – próba odczytu bądź zapisu elementów spoza zakresu tablicy to błąd!
Jaki powinien być zakres wartości $x$ i $y$ dla obrazu o wymiarach $h \times w$ i maski o wymiarach $n \times n$?
Czy o czymś jeszcze powinniśmy pamiętać (jeśli chodzi o wymiary i zakresy indeksów)?

Uruchom program. Zaobserwuj różnicę między obrazem wejściowym a wyjściowym – wyjściowy powinien być lekko rozmyty.
Teraz zmień #define N 3 na #define N 7 i ponownie uruchom program. Tym razem rozmycie będzie bardziej widoczne, gdyż więcej sąsiadów zostanie uśrednionych.

Jak widzisz, stosowanie stałych pozwala uczynić program bardziej elastycznym i uniwersalnym – nie trzeba zmieniać wpisanych “z palca” wartości w dziesiątkach miejsc programu. Wystarczy zmiana w jednym miejscu.

Format graficzny BMP stosuje upakowanie pikseli obrazu wierszami, w “paczkach” o rozmiarze będącym wielokrotnością 4 bajtów. Stąd w naszym przypadku, jeśli szerokość obrazu nie jest wielokrotnością 4, dodana zostanie odpowiednia ilość bajtów wyrównania. Paczki te występują jedna po drugiej, w ciągu.

Rozmiar pojedynczej paczki wynosi $$\mbox{RowSize} = \left\lfloor\frac { \mbox{BitsPerPixel} \cdot \mbox{ImageWidth} + 31 }{32} \right\rfloor \cdot 4$$ przy czym w naszym przypadku $\mbox{BitsPerPixel} = 8$ (takie jest jedno z założeń projektowych).
Zapis $\left\lfloor x \right\rfloor$ oznacza podłogę liczby $x$, czyli największą liczbę całkowitą nie większa od $x$.

Jak wspomniano przy okazji deklarowania tablic wielowymiarowych, komputer przechowuje w pamięci tablicę dwuwymiarową (perspektywa tablicowa) w sposób liniowy – jako kilka następujących po sobie tablic jednowymiarowych (perspektywa wskaźnikowa).

Oto przykład takiego wyrównania dla obrazu o wymiarach $h \times w = 3 \times 2$:

przy czym $$\mbox{RowSize} = \left\lfloor\frac { \mbox{BitsPerPixel} \cdot \mbox{ImageWidth} + 31 }{32} \right\rfloor \cdot 4 = \left\lfloor\frac { 8 \cdot 2 + 31 }{32} \right\rfloor \cdot 4 = \left\lfloor 1,46875 \right\rfloor \cdot 4 = 1 \cdot 4 = 4$$

• Uzupełnij kod funkcji load_bitmap() tak, aby poprawnie przepisał wartości pikseli przechowywanych w miejscu wskazywanym przez bitmapBytes (zawierającej wyrównane dane) do tablicy image.

• Uzupełnij kod funkcji save_bitmap() dokonując operacji odwrotnej – przepisz wartości pikseli przechowywanych w tablicy image do miejsca wskazywanego przez bitmapBytes.
  Pamiętaj o nadaniu bajtom wyrównania wartości 0!

W chwili pisania programu nie możemy przewidzieć, jakie rozmiary będzie miał wczytywany obraz. Oznacza to, że musimy skorzystać z dynamicznej alokacji pamięci w celu utworzenia tablicy o odpowiednim rozmiarze, w której następnie będziemy trzymać wartości pikseli wczytanego obrazu.

• Uzupełnij funkcję create_matrix() zgodnie z jej opisem w kodzie programu.
• Uzupełnij funkcję destroy_matrix() zgodnie z jej opisem w kodzie programu.