TEKNIK PENGOLAHAN CITRA

Kuliah 7 – Transformasi Fourier

Indah Susilawati, S.T., M.Eng.

Program Studi Teknik Elektro

Program Studi Teknik Informatika Fakultas Teknik dan Ilmu Komputer

Universitas Mercu Buana Yogyakarta 2009

KULIAH 7

TEKNIK PENGOLAHAN CITRA

TRANSFORMASI FOURIER

Transformasi Fourier merupakan salah satu dasar penting dalam pengolahan citra,

dapat memproses dengan efisien dan lebih cepat. Dibandingkan dengan linear spatial

filtering, maka transformasi Fourier lebih cepat (terutama jika ukuran filternya besar).

Transformasi Fourier memungkinkan pengolahan dengan cara mengisolasi satu

“frekuensi” tertentu pada citra, sehingga dapat digunakan untuk menerapkan LPF dan

HPF dengan ketelitian yang cukup tinggi.

Latar Belakang

Suatu fungsi periodik dapat dinyatakan sebagai jumlahan fungsi sinus dan cosinus

yang bervariasi amplitude dan frekuensinya. Gambar berikut merupakan contoh suatu

fungsi dan dekomposisinya menjadi fungsi-fungsi sinus.

Beberapa fungsi mungkin hanya terdekomposisi menjadi sejumlah terhingga

fungsi sinus dan cosinus, tetapi juga terdapat fungsi yang mempunyai tak terhingga

fungsi dekomosisi, misalnya fungsi gelombang kotak (square wave) berikut.

Pada gambar berikut, diambil empat fungsi dekomposisi yang pertama dan kemudian

dijumlahkan. Semakin banyak fungsi dekomposisi yang dijumlahkan, maka hasilnya

akan semakin mirip dengan fungsi aslinya (fungsi kotak).

Transformasi Fourier Diskret Satu Dimensi

Dalam fungsi diskret (sebagaimana pada pengolahan citra), maka hanya akan ada

sejumlah terhingga nilai sehingga juga hanya dibutuhkan sejumlah terhingga fungsi saja.

Misalkan terdapat suatu deret sbb.

1 1 1 1 -1 -1 -1 -1

Maka dapat dinyatakan dengan pendekatan diskret seperti gelombang kotak pada gambar

berikut. Pada gambar yang sama juga dapat dilihat bahwa gelombang kotak ini dapat

dinyatakan sebagai jumlahan dua fungsi sinus saja. Oleh karena pembahasan pengolahan

citra menggunakan citra digital maka hanya akan dibahas transformasi Fourier diskret

saja (DFT : Discrete Fourier Transform).

Definisi DFT Satu Dimensi

Misalkan terdapat deret sepanjang N yang dinyatakan sbg fx = [f0, f1, f2, ..., fN-1]

maka DFT dari deret tsb didefinisikan sbg

Fu = [F0, F1, F2, ..., FN-1]

dengan

Dan untuk Inverse Discrete Fourier Transform (IDFT) – nya adalah

∑−

=⎥⎦⎤

⎢⎣⎡=

1

02exp1 N

uux F

Nxui

Nf π

Fast Fourier Transform (FFT)

Alternatif lain untuk menghitung DFT (selain menggunakan rumusan di atas)

adalah menggunakan algoritma cepat yang dikenal dengan Fast Fourier Transform (FFT).

Dengan FFT maka waktu yang dibutuhkan untuk menghitung DFT menjadi lebih cepat.

Metode FFT bekerja secara rekursif dengan membagi vektor asli menjadi dua

bagian, menghitung FFT masing-masing bagian, dan kemudian menggabungkannya. Hal

ini mengindikasikan bahwa FFT akan menjadi sangat efisien jika panjang vektor

merupakan bilangan pangkat 2. Tabel berikut memuat perbandingan jumlah operasi

perkalian dalam perhitungan DFT menggunakan rumus DFT secara langsung dan

menggunakan algoritma FFT.

DFT Dua Dimensi

Dalam dua dimensi, DFT mempunyai input berupa matriks dan akan

menghasilkan output berupa matriks dengan ukuran yang sama. Jika input adalah f(x,y)

maka outputnya dapat dinyatakan dengan F(u,v). Matriks F(u,v) disebut transformasi

Fourier dari f (x,y) dan ditulis sbb.

Jika diketahui fungsi F(u,v), maka matriks f(x,y) dapat dicari dengan Inverse DFT, yaitu

Dalam satu dimensi, suatu fungsi dapat dinyatakan sebagai jumlahan fungsi sinus

dan cosinus. Oleh karena citra adalah fungsi dua dimensi f(x,y), maka adalah beralasan

jika fungsi tsb dinyatakan sebagai

Definisi DFT untuk 2 dimensi mirip dengan pada satu dimensi. Dengan masukan

f(x,y) berukuran M x N (sehingga x = 0, 1, ... M-1 dan y = 0, 1, 2, ..., N-1) maka

Sifat-Sifat Transformasi Fourier Dua Dimensi

Similarity (Kemiripan). Dari rumusan DFT dan IDFT dua dimensi di atas, maka

sekilas terlihat bahwa keduanya sangat mirip kecuali faktor skala 1/MN pada rumus

IDFT dan tanda negatif pada eksponen dalam rumus DFT. Hal ini menunjukkan bahwa

algoritma yang sama dapat diterapkan untuk mencari DFT dan IDFT hanya dengan

sedikit penyesuaian saja.

DFT Sebagai Filter Spasial. Perhatikan bahwa nilai

merupakan nilai yang tidak bergantung pada nilai f atau F. Ini berarti bahwa nilai tsb

dapat dihitung terlebih dahulu dan kemudian meletakkannya di depan tanda sigma. Ini

juga berarti bahwa setiap nilai F(u,v) dapat diperoleh dengan mengalikan setiap nilai

f(x,y) dengan suatu nilai tertentu, dan menjumlahkan semua hasilnya. Hal ini sama

seperti yang dilakukan pada proses linear spatial filtering, yaitu mengalikan semua

elemen di bawah mask dan kemudian menjumlahkan hasilnya. Dengan demikian, DFT

dapat dipandang sebagai filter spasial linear dengan ukuran sama besar dengan citra yang

diolah.

Separabilitas. Perhatikan bahwa elemen filter transformasi Fourier dapat

dinyatakan sebagai hasil kali sbb.

Hasil kali yang pertama

hanya bergantung pada x dan u dan independen terhadap y dan v. Sebaliknya hasil kali

yang kedua

hanya bergantung pada y dan v dan independen terhadap x dan u. Hal ini berarti rumusan

di atas dapat dipecah menjadi rumusan yang lebih sederhana yang mengolah masing-

masing baris dan kolom pada matriks. DFT dan IDFT untuk matriks baris adalah sbb.

Jika variabel x dan u diganti dengan y dan v maka didapatkan rumusan DFT dan IDFT

untuk matriks kolom.

DFT dua dimensi dapat diperoleh dengan menggunakan sifat separabilitas ini;

untuk menghitung DFT sebuah matriks, dapat dihitung DFT seluruh baris dan kemudian

menghitung DFT semua kolom dari matriks hasilnya. Dapat juga menghitung DFT

seluruh kolom dan kemudian menghitung DFT semua baris dari matriks hasilnya.

Perhatikan gambar berikut.

Linearitas. DFT mempunyai sifat linear, yaitu DFT dari jumlahan dua atau lebih

fungsi adalah jumlahan dari DFT masing-masing fungsi tsb; DFT dari perkalian skalar

suatu fungsi adalah DFT dari fungsi tsb dikalikan dengan skalar yang sama. Atau

dinyatakan,

Dengan f dan g adalah matriks dan k adalah skalar. Sifat ini sangat penting saat

menangani degradasi citra, misalnya citra berderau yang dimodelkan sbg

d = f + n

dengan f adalah citra tak berderau, n adalah derau dan d adalah citra berderau. Maka

dengan transformasi Fourier citra berderau dapat dinyatakan

Dan sebagaimana yang akan dibahas nanti, derau yang tampak pada DFT membuatnya

lebih mudah untuk dihilangkan.

Koefisien DC. Nilai F(0,0) pada DFT disebut koefisien DC. Jika u = v = 0, maka

persamaan atau rumusan DFT di atas menghasilkan

Nilai di atas sama dengan jumlahan semua elemen pada matriks asli (yang diolah).

Pergeseran (Shifting). Untuk kemudahan dalam menampilkan (display), akan

lebih mudah jika koefisien DC berada di pusat matriks. Hal ini akan terjadi jika semua

elemen matriks f(x,y) dikalikan dengan (-1)x+y sebelum dilakukan transformasi. Gambar

berikut memperlihatkan pergeseran matriks menggunakan metode ini. Koefisien DC

ditunjukkan dengan kotak kecil berwarna hitam di sudut kiri atas submatriks A.

Simetri Konjugat. Analisis definisi transformasi Fourier mengarahkan ke sifat

simetri; jika diambil substitusi u = -u dan v = -v maka

F(u,v) = F*(-u + pM, -v + qN)

untuk sebarang bilangan bulat p dan q. Hal ini berarti bahwa setengah hasil transformasi

merupakan “cermin” konjugat dari setengah yang lain. Dapat dipandang bahwa setengah

bagian atas adalah “cermin” konjugat dari setengah bagian bawah atau setengah bagian

kiri adalah “cermin” konjugat dari setengah bagian kanan. Simetri berarti bahwa

informasi berada di setengah hasil transformasi, setengahnya lagi adalah redundant

(mubazir). Gambar berikut memperlihatkan simetri dalam DFT yang telah digeser; kotak

kecil berwarna hitam menunjukkan posisi koefisien DC.

Menampilkan Hasil Transformasi

Setelah melakukan transformasi Fourier citra f(x,y) menjadi F(u,v) maka perlu

dilihat hasilnya. Elemen F(u,v) merupakan bilangan kompleks sehingga tidak dapat

ditampilkan secara langsung, namum dapat dilihat magnitude-nya yaitu | F(u,v) |. Berikut

cara atau pendekatan yang dapat dilakukan untuk menampilkan hasil tranformasi Fourier.

1. Temukan nilai terbesar dari | F(u,v) | yaitu m. Nilai ini biasanya adalah koefisien

DC yang dihasilkan dari transformasi. Gunakan imshow.m untuk

melihat | F(u,v) | / m.

2. Gunakan mat2gray.m untuk melihat | F(u,v) | secara langsung.

Permasalahan lain adalah bahwa koefisien DC biasanya sangat besar dibandingkan

dengan nilai-nilai yang lain. Hal ini mempunyai pengaruh pada tampilan hasil

transformasi yaitu berupa satu titik putih dikelilingi warna hitam. Satu cara untuk

merentangkan nilainya adalah dengan mengambil logaritma dari | F(u,v) | dan

menampilkan

Log ( 1 + | F(u,v) | )

Tampilan magnitude transformasi Fourier disebut spektrum dari transformasi tersebut.

Transformasi Fourier Dalam MATLAB

Beberapa fungsi Matlab yang sesuai adalah

• fft.m untuk memperoleh DFT dari sebuah vektor

• ifft.m untuk memperoleh inverse DFT dari sebuah vektor

• fft2.m untuk memperoleh DFT dari sebuah matriks

• ifft2.m untuk memperoleh inverse DFT dari sebuah matriks

• fftshift.m untuk menggeser hasil transformasi sehingga koefisien DC berada di

tengah

Contoh 1

Membuat matriks 8 x 8 dengan semua elemennya sama dengan 1, kemudian mencari

DFT-nya dengan metode FFT. Hasilnya adalah matriks dengan koefisien DC dan nol

pada semua elemen yang lain (karena matriks masukan elemennya sama, tidak ada

perubahan)

>> a = ones (8);

>> fft2 (a)

Hasilnya adalah

ans =

64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Contoh 2

Membentuk matriks yang mengandung perubahan nilai dan melihat DFT-nya.

>> a = [100 200; 100 200];

>> b = repmat (a, 4, 4)

b =

100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200 100 200

>> bfft = fft2 (b)

bfft =

9600 0 0 0 -3200 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Matriks b dapat dinyatakan dengan jumlahan dua matriks yaitu sebuah matriks konstan

yang semua elemennya 150 dan sebuah matriks yang berubah-ubah nilainya sebesar -50

dan 50 dari kiri ke kanan. Matriks konstan akan menghasilkan koefisien DC yang bernilai

64 x 150 = 9600.

Contoh 3

Membuat matriks dengan satu tebing step tunggal dan mencari DFT-nya.

>> a = [zeros(8, 4) ones(8, 4)]

a =

0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

>> afft = fft2 (a)

afft =

Columns 1 through 5

32.0000 -8.0000 +19.3137i 0 -8.0000 + 3.3137i 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Columns 6 through 8 -8.0000 - 3.3137i 0 -8.0000 -19.3137i 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Untuk menempatkan koefisien DC di tengah dan karena hasil transformasi memuat nilai-

nilai kompleks maka dicari magnitude-nya sekaligus dibulatkan.

>> afft = fftshift (afft)

>> round (abs(afft))

ans = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 21 32 21 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Koefisien DC merupakan jumlahan semua nilai matriks a dan nilai-nilai yang lain

merupakan koefisien-koefisien fungsi sinus yang diperlukan untuk membentuk tebing

pada matriks.

Transformasi Fourier Citra

Akan dibuat beberapa citra sederhana dan melihat hasil transformasi Fourier-nya.

Contoh 1

>> a = [zeros (256, 128) ones (256, 128)];

>> af = fftshift (fft2 (a) );

Untuk melihat spektrumnya dapat dipilih dari dua cara berikut:

1. af1 = log ( 1 + abs (af) );

imshow (af1/af1(129,129))

Proses ini didasarkan pada kenyataan bahwa setelah penggeseran maka koefisien

DC berada pada posisi x = y = 129. Nilai direntangkan dengan fungsi log dan

membagi nilainya dengan koefisien DC.

2. imshow (mat2gray ( log (1 + abs (af) ) ) )

Fungsi mat2gray.m secara otomatis melakukan scaling untuk menampilkan citra.

Untuk kemudahan maka akan dibuat satu fungsi sederhana untuk melihat hasil

transformasi. Berikut adalah contoh fungsinya.

function fftshow (f, type) if nargin < 2, type = 'log'; end if (type == 'log') f1 = log (1 + abs(f)); fm = max (f1(:)); imshow (im2uint8(f1/fm)) elseif (type == 'abs') fa = abs(f); fm = max (fa(:)); imshow (fa/fm) else error ('Type must be log or abs'); end;

Berikut adalah citra dari matriks a dan hasil transformasi Fourier-nya.

Citra matriks a Transf. Fourier matriks a

Citra matriks b Transf. Fourier matriks b

Contoh 2

Membuat sebuah kotak dan melihat transformasi Fourier-nya.

clear all; clc; a = zeros (256, 256); a(78:178, 78:178) = 1; imshow (a) af = fftshift(fft2(a)); figure, fftshow(af,'abs')

Sebuah kotak dan DFT-nya

Contoh 3

Sebuah kotak yang diputar 45° dan melihat DFT-nya.

clear all; clc; [x,y] = meshgrid(1:256, 1: 256) b = (x+y < 329) & (x+y > 182) & (x-y > -67) & (x-y < 73) imshow (b) bf = fftshift(fft2(b)); figure, fftshow(bf)

Sebuah kotak yang diputar 45° dan DFT-nya

Contoh 4

Membuat sebuah lingkaran dan melihat DFT-nya.

clear all; clc; [x,y] = meshgrid(-128:127, -128: 127) z = sqrt(x.^2 + y.^2) c = (z<15) imshow (c) cf = fftshift(fft2(c)); figure, fftshow(cf,'log')

Sebuah lingkaran dan DFT-nya

Contoh 5

Citra einstein.jpg dan DFT-nya.

Citra einstein.jpg dan DFT-nya

Citra einstein.jpg dengan derau periodik dan DFT-nya