– dokładnie 75% komponentów, co oznacza 75 procentową redukcję ilości informacji w próbce...

Tak zmodyfikowana transformata została za pomocą
odwrotnej transformacji kosinusowej przeliczona z dziedziny częstotliwości
120
7. Przekształcenia w dziedzinie częstotliwości
z powrotem do dziedziny danych (Rysunek 7.2(c)). Pomimo dosyć znacz-nej destrukcji sygnału w transformacie widać wyraźną korelację pomiędzy
wartościami danych z przed transformaty (a) i po transformacie odwrot-
nej (c). Rysunek 7.2(e) przedstawia różnicę wartości sygnału oryginalnego i przekształconego. W wyniku powyższej transformacji sygnał uległ około
15% degradacji za cenę zmniejszenia ilości informacji do 25% pierwotnej
wielkości.
Złożoność obliczeniowa Dyskretnej Transformaty Kosinusowej wynosi
podobnie jak transformaty Fouriera O(N2) ale dzięki dzięki algorytmom
podobnym do FFT złożoność ta może być obniżona do O(NlogN).
7.3. Uwagi implementacyjne
Samodzielna implementacja algorytmów liczenia FFT jest procesem do-
syć skomplikowanym i wykraczającym poza ramy niniejszej pozycji. Bar-
dzo dobre studium szybkiej transformaty Fouriera znajdzie czytelnik w
[35, 4] Dalsze rozważania będą oparte na istniejącej wieloplatformowej implementacji zwanej FFTW [15]. Dostarczana w postaci biblioteki, napi-sana w języku C, implementacja FFTW potrafi obliczać DFT oraz DCT
dowolnie-wymiarowe, o dowolnej wielkości dla danych rzeczywistych jak i
zespolonych. Biblioteka ta jest wolnodostępna na licencji GPL.
7.3.1. C/C++
Dla programów pisanych w języku C++ biblioteki FFTW są dostarcza-
ne w postaci natywnych bibliotek systemowych na konkretną platformę.
Łączenie bibliotek FFTW z bibliotekami Qt wymaga dodania do pliku
projektu następujących wpisów:
LIBS = -L/ sciezka / katalogu / biblioteki - lfftw3
INCLUDEPATH = -I/ sciezka / katalogu / pliku / naglowkowego
W przypadku dołączania konkretnej wersji biblioteki można wywołanie
-lfftw3 zastąpić konkretną wersją poprzez wywołanie -l:libfftw3.so.x.y.z.
Następnie, w celu odświeżenia pliku reguł makefile, należy uruchomić pro-
gram qmake (w przypadku QtCreatora w menu wybrać “Build/Run qmake“)
i przebudować projekt (”Build/Rebuild Project“).
W pliku, w którym są używane funkcje z biblioteki FFTW należy dołączyć
plik fftw3.h
Plik biblioteki libfftw3.dll – w przypadku Windows lub libfftw3.so – w
przypadku Linuxa, musi być „widoczny” dla pliku wykonywalnego, tzn. musi
7.3. Uwagi implementacyjne
121
być albo w katalogu, w którym system trzyma biblioteki albo w tym samym
katalogu co plik wykonywalny. Dla systemu Linux najlepszym rozwiązaniem
będzie wykorzystanie biblioteki FFTW z używanej dystrybucji.
Samo użycie funkcji biblioteki do obliczenia Szybkiej Transformaty
Fouriera (FFT) ilustruje listing 7.1.
Listing 7.1. Użycie funkcji biblioteki FFTW.
1
# include <fftw3 .h >
2
...
3
{
4
int W , H;
5
QImage image (W, H , QImage :: Format_RGB32 );
6
7
fftw_complex *in , * out ;
8
in
= ( fftw_complex *) fftw_malloc ( sizeof ( fftw_complex )
9
*W*H);
10
out = ( fftw_complex *) fftw_malloc ( sizeof ( fftw_complex )
11
*W*H);
12
13
QRgb * p = ( QRgb *) image . bits () ;
14
for ( int i = 0; i < W*H; i ++)
15
{
16
in [i ][0] = qRed (p[i ]) ;
17
in [i ][1] = 0;
18
}
19
20
fftw_plan p;
21
p = fftw_plan_dft_2d (H , W , in , out , FFTW_FORWARD ,
22
FFTW_ESTIMATE );
23
fftw_execute (p);
24
fftw_destroy_plan (p);
25
26
/
/
.
.
.
o
p
e
r
a

j
e
n
a
t
r
a
n
s
f
o
r
m
a

i
e
.
.
.
27
28
p = fftw_plan_dft_2d (H , W , out , in , FFTW_BACKWARD ,
29
FFTW_ESTIMATE );
30
fftw_execute (p);
31
fftw_destroy_plan (p);
32
33
p = ( QRgb *) image . bits () ;
34
for ( int i = 0; i < W*H; i ++)
35
{
36
p[i] = qRgb ( in [i ][0] , qGreen (p[i ]) , qBlue (p[i ]) );
37
}
38
39
fftw_free ( in ); fftw_free ( out );
40
}
122
7. Przekształcenia w dziedzinie częstotliwości
Linia 1 – dołączony plik nagłówkowy z deklaracjami struktur i funkcji bi-
blioteki FFTW.
Linie 4-5 – tworzony jest obraz image typu QImage o rozmiarze W × H i
32-bitowej głębi bitowej.
Linie 7-10 – definicja tablic liczb zespolonych, które będą przechowywały
dane transformaty. Strukturę fftw_complex można traktować jak tablicę
o dwóch elementach typu double:
1
typedef double fftw_complex [2];
W elemencie fftw_complex[0] jest przechowywana wartość części rzeczy-
wistej liczby zespolonej, w elemencie fftw_complex[1] wartość części uro-
jonej liczby zespolonej. Do alokacji pamięci została użyta biblioteczna
funkcja:
1
void * fftw_malloc ( size_t n);
dbająca o poprawną alokację i odpowiednie wyrównanie pamięci.
Tablica in oraz tablica out mają wielkość obrazu (W × H) razy wielkość
zmiennej typu fftw_complex. Zmienna in będzie przechowywała wartości
z dziedziny obrazu, czyli wartości przed transformatą, natomiast zmien-