Differences

This shows you the differences between two versions of the page.

--- dydaktyka:cprog:2015:photoshop [2015/11/22 19:55]
pkleczek [Idea projektu]
+++ — (current)
@@ Line 1: / Line 1: @@
-====== Projekt - Fotoszop ======
-[size=10]Nazwałem ten projekt "Fotoszop" oczywiście ze względu na prawną ochronę nazwy handlowej programu Photoshop firmy Adobe...[/size]
-===== Tytułem wstępu... =====
-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.
-===== Idea projektu =====
-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((zobacz znaczenie w [[http://sjp.pwn.pl/poradnia/haslo/implementowac;9044.html|SJP PWN]])) 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łą [[https://pl.wikipedia.org/wiki/KISS_%28regu%C5%82a%29|KISS]], stąd:
-  * program będzie obsługiwał tylko obrazy w odcieniach szarości w 8-bitowej [[https://pl.wikipedia.org/wiki/G%C5%82%C4%99bia_koloru|głębi koloru]], zapisane w formacie [[https://pl.wikipedia.org/wiki/Windows_Bitmap|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: \\
-{{:dydaktyka:cprog:2015:grayscale.png?nolink|}}
-===== Architektura programu =====
-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:
-<code c>
-#include "bitmap.h"
-</code>
-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()''.
-==== Typ "byte" ====
-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
-<code c>
-typedef unsigned char byte;
-</code>
-===== Ćwiczenia =====
-==== 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: {{:dydaktyka:cprog:2015:fotoszop-ex1.zip|}} \\
-Podczas realizacji zadań wykorzystaj ten projekt jako szkielet swojego programu.
-=== Teoria ===
-:!: 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$). \\
-{{:dydaktyka:cprog:2015:filtering_idea.png?nolink|}}
-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: \\
-{{:dydaktyka:cprog:2015:filtering_3x3.png?nolink|}}
-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}$: \\
-{{:dydaktyka:cprog:2015:mean3x3.png?nolink|}}
-=== Zadanie MASK ===
-  * 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''
-<code c>
-#define N   3
-</code>
-Preprocesor to program uruchamiany przed właściwą kompilacją (stąd jego nazwa: __pre__procesor), 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
-<code c>
-int a = N + 5;
-</code>
-wygląda następująco (to widzi kompilator):
-<code c>
-int a = 3 + 5;
-</code>
-  * 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 dla tablicy powinien wyglądać następująco:
-<code>
-.11 0.11 0.11
-.11 0.11 0.11
-.11 0.11 0.11
-</code>
-=== Zadanie CONV ===
-  * 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.
-==== Umieszczanie bajtów obrazu w tablicy ====
-=== Teoria ===
-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 [[dydaktyka:cprog:2015:arrays#deklarowanie1|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$: \\
-{{:dydaktyka:cprog:2015:byte_packing.png?nolink|}} \\
-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$$
-=== Zadanie PTR2MAT ===
-  * 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''!
-==== Dynamiczna alokacja tablicy-obrazu ====
-W chwili pisania programu nie możemy przewidzieć, jakie rozmiary będzie miał wczytywany obraz. Oznacza to, że musimy skorzystać z [[dydaktyka:cprog:2015:dynamic_memory_allocation#alokacja_pamieci_dla_tablicy_dwuwymiarowej|dynamicznej alokacji pamięci]] w celu utworzenia tablicy o odpowiednim rozmiarze, w której następnie będziemy trzymać wartości pikseli wczytanego obrazu.
-=== Zadanie IMALLOC ===
-  * Uzupełnij funkcję ''create_matrix()'' zgodnie z jej opisem w kodzie programu.
-  * Uzupełnij funkcję ''destroy_matrix()'' zgodnie z jej opisem w kodzie programu.

Joanna Jaworek-Korjakowska

User Tools

Site Tools

Differences

Page Tools