Vježbe 12

Fourierove transformacije. Kompresija.

Primjer 1: Da bi pojednostavnili eksperimente sa slikama, na raspolaganju je jednostavna biblioteka rutina definiranih u header-datoteci pgm.h za učitavanje i ispis PGM formata (više o PGM formatu pogledajte ovdje).
Slike se čuvaju u strukturi GRID koja sadrži dimenzije (širinu i visinu) u pikselima i pokazivač na polje kompleksnih brojeva (polje je kompleksno da bi se omogućilo direktno korištenje standardnih rutina za izvođenje brzih Fourierovih transformacija):

typedef struct {
  int width, height;
  complex double *image;
} GRID;

Za učitavanje koristi se rutina read_PGM koja sama alocira i potrebnu memoriju. Primjer:

GRID *slika1;
...
slika1 = read_PGM("slika.pgm");
...

Sadržaj strukture tipa GRID ispisuje se rutinom write_PGM, na primjer:
 
write_PGM("slika.pgm", slika1, 'r');
 

Treći parametar je tipa char, 'r' za realni dio kompleksnog broja, 'i' za imaginarni, no u praksi će nam trebati samo 'r' ('i' može biti koristan za testiranje i eksperimentiranje).

Demo program koji koristi rutine iz pgm.h izrezivanje.c koji kao primjer manipulacije slikom zacrnjuje srednji dio slike i ostavlja samo uglove željene veličine izražene u pikselima.
12.1. Prevedite i isprobajte demo program izrezivanje.c iz Primjera 1.
Koristite se slikama po vlastitom izboru koje možete konvertirati u PGM format uz pomoć programa GIMP (učitajte sliku u proizvoljnom formatu i kod snimanja sa Save As... odaberite na Select File Type opciju PGM image te snimite u ASCII formatu).
12.2. Nadogradite program izrezivanje.c u program obrada.c koji prvo izračunava Fourierovu transformaciju slike u frekvencijsku domenu, potom filtrira visoke frekvencije (ekvivalentno izrezivanju iz Primjera 1, ali u frekvencijskoj domeni), te izračunava inverznu Fourierovu transformaciju, tj. rekonstruira sliku samo iz preostalih modova.
Direktna (naivna) implementacija diskretne Fourierove transformacije je izrazito neefikasna, jer broj operacija raste s kvadratom broja točaka. To je pogotovo problem kad se radi u dvije (slike) ili više dimenzija. Naime, i broj točaka raste s kvadratom dimenzija slike, dakle slika dvostruke širine i visine ima 4 puta više točaka, što pak traži 16 puta dulje vrijeme obrade! Čak na današnjim gigahercnim procesorima naivna implementacija je prespora - treba oko minuta za transformaciju sličice veličine 150x150 piksela.
Jedan od najvažnijih algoritamskih "proboja" uopće je otkriće FFT (Fast Fourier Transform) algoritma (J. W. Cooley i J. W. Tukey 1965. godine) koji umjesto O(N^2) operacija treba svega O(N log N) operacija te je za N reda veličine nekoliko milijuna (slike od nekoliko megapiksela) dramatično efikasniji i omogućava praktičnu primjenu Fourierovih transformacija. S obzirom da se radi o dosta složenom algoritmu najbolje je posegnuti za gotovim bibliotekama rutina koje su pripremili eminentni stručnjaci za numeriku i koje su danas besplatno dostupne - na primjer FFTW. Pod Linuxom dovoljno je instalirati paket libfftw3-dev i on bi trebao "povući" sve ostale potrebne pakete. Upute za korištenje i primjeri mogu mogu se naći u PDF formatu ovdje.
Dakle, treba najprije instalirati paket(e) libfftw3-dev, potom proučiti primjere u poglavljima 2.1 i 2.2, te implementirati dvodimenzionalne Fourierove transformacije u program obrada.c. Najprije treba učitanu sliku transformirati u frekvencijsko područje - postaviti predznak (sign) tranformacije na FFTW_FORWARD, potom obaviti filtriranje (već gotova rutina izrezivanje() iz Primjera 1) te rekonstruirati sliku inverznom transformacijom - postaviti predznak na FFTW_BACKWARD. (SAVJETI: u rutini fftw_plan_dft_2d(...) prvi argument je visina slike, a drugi širina; za peti argument flag odabrati FFTW_ESTIMATE; transformirati se može nad istom matricom, dakle nije potrebno alocirati dodatnu memoriju).
12.3. Eksperimentirajte koliko je modova potrebno zadržati da bi se dobila zadovoljavajuća kvaliteta rekonstruirane slike. Dakle, sliku je moguće pospremiti i kao podskup modova iz frekvencijske domene, te je uz pomoć odgovarajuće Fourierove transformacije ponovo rekonstruirati. Ukoliko je broj modova potreban za razumnu kvalitetu slike znatno manji od broja piksela to omogućuje znatnu memorijsku uštedu, tj. radi se o učinkovitom načinu kompresiranja.