Transformasi Fourier 1 dimensi (Dosen: Bp. Aziz) Dirangkum oleh: Eko Zulkaryanto (http://zulkaryanto.wordpress.com) Computer Science – Bogor Agricultural University (http://www.ipb.ac.id)
Transformasi Fourier Mengapa perlu transformasi ? – Setiap orang pada suatu saat pernah menggunakan suatu teknik analisis dengan transformasi untuk menyederhanakan penyelesaian suatu masalah [Brigham,1974] – Contoh: penyelesaian fungsi y = x/z Analisa konvensional : pembagian secara manual Analisa transformasi : melakukan transformasi – log(y) = log(x) – log(z) – look-up table pengurangan look-up table Transformasi juga diperlukan bila kita ingin mengetahui suatu informasi tertentu yang tidak tersedia sebelumnya Contoh : – jika ingin mengetahui informasi frekuensi kita memerlukan transformasi Fourier – Jika ingin mengetahui informasi tentang kombinasi skala dan frekuensi kita memerlukan transformasi wavelet Transformasi Citra Transformasi citra, sesuai namanya, merupakan proses perubahan bentuk citra untuk mendapatkan suatu informasi tertentu Transformasi bisa dibagi menjadi 2 : – Transformasi piksel/transformasi geometris: – Transformasi ruang/domain/space Transformasi Pixel
f(x) = sin(x) + sin(3x)/3 + sin(5x)/5 + sin(7x)/7 + sin(9x)/9 … Hasil dalam transformasi fourier
Fungsi kotak sebagai penjumlahan fungsi-fungsi sinus Cobakan juga program matlab berikut untuk melihat sampai batas n berapa fungsi yang dihasilkan sudah berbentuk fungsi kotak. function kotak(n) t = 0:pi/200:8*pi; kot = sin(t); for i = 3 : 2: n kot = kot + (sin(i*t))/i; end plot(kot)
Transformasi piksel masih bermain di ruang/domain yang sama (domain spasial), hanya posisi piksel yang kadang diubah Contoh: rotasi, translasi, scaling, invers, shear, dll. Transformasi jenis ini relatif mudah diimplementasikan dan banyak aplikasi yang dapat melakukannya (Paint, ACDSee, dll) Transformasi Ruang Transformasi ruang merupakan proses perubahan citra dari suatu ruang/domain ke ruang/domain lainnya, contoh: dari ruang spasial ke ruang frekuensi Masih ingat istilah ‘ruang’ ? Ingat-ingat kembali pelajaran Aljabar Linier tentang Basis dan Ruang – Contoh : Ruang vektor. Salah satu basis yang merentang ruang vektor 2 dimensi adalah [1 0] dan [0 1]. Artinya, semua vektor yang mungkin ada di ruang vektor 2 dimensi selalu dapat direpresentasikan sebagai kombinasi linier dari basis tersebut. Ada beberapa transformasi ruang yang akan kita pelajari, yaitu : – Transformasi Fourier (basis: cos-sin) – Transformasi Hadamard/Walsh (basis: kolom dan baris yang ortogonal) – Transformasi DCT (basis: cos) – Transformasi Wavelet (basis: scaling function dan mother wavelet) Transformasi Fourier Pada tahun 1822, Joseph Fourier, ahli matematika dari Prancis menemukan bahwa: setiap fungsi periodik (sinyal) dapat dibentuk dari penjumlahan gelombang-gelombang sinus/cosinus. Contoh : Sinyal kotal merupakan penjumlahan dari fungsi-fungsi sinus berikut (lihat gambar pada halaman berikut)
Gambar a) n = 1, b) n =3, c) n = 7, d) n = 99 Contoh lain
Contoh lain
FT – Motivasi Jika semua sinyal periodik dapat dinyatakan dalam penjumlahan fungsi-fungsi sinus-cosinus, pertanyaan berikutnya yang muncul adalah: – Jika saya memiliki sebuah sinyal sembarang, bagaimana saya tahu fungsi-fungsi cos – sin apa yang membentuknya ? Atau dengan kata lain – Berapakah frekuensi yang dominan di sinyal tersebut ? Pertanyaan di atas dapat dijawab dengan menghitung nilai F(u) dari sinyal tersebut. Dari nilai F(u) kemudian dapat diperoleh kembali sinyal awal dengan menghitung f(x), menggunakan rumus: Rumus FT – 1 dimensi Rumus FT kontinu 1 dimensi
F (u ) f ( x) exp[ 2 jux]dx
f ( x) F (u ) exp[ 2 jux]du
Euler' s formula : exp[ 2 jux] cos 2ux j sin 2ux
Rumus FT diskret 1 dimensi
Contoh Penghitungan FT 1 dimensi
Contoh Penghitungan FT 1 dimensi Hasil penghitungan FT biasanya mengandung bilangan real dan imajiner Fourier Spectrum didapatkan dari magnitude kedua bilangan tersebut shg|F(u)| = [R 2(u) + I 2(u)]1/2 Untuk contoh di halaman sebelumnya, Fourier Spectrumnya adalah sebagai berikut: |F(0)| = 3.25 |F(1)| = [(-0.5)2+(0.25)2]1/2 = 0.5590 |F(2)| = 0.25 |F(3)| = [(0.5)2+(0.25)2]1/2 = 0.5590 Transformasi fourier 2 dimensi (Bp. Aziz) Rumus FT – 2 dimensi
1 N 1 f ( x) exp[ 2 jux / N ] N x 0 1 N 1 f ( x) x 0 F (u ) exp[ 2 jux / N ] N
F (u )
Contoh FT 1 dimensi Contoh berikut diambil dari Polikar
(http://engineering.rowan.edu/~polikar/WAVELETS/WTtut orial.html) Misalkan kita memiliki sinyal x(t) dengan rumus sbb: x(t) = cos(2*pi*5*t) + cos(2*pi*10*t) + cos(2*pi*20*t) + cos(2*pi*50*t) Sinyal ini memiliki empat komponen frekuensi yaitu 5,10,20,50 Contoh sinyal 1 Dimensi x(t) Gambar sinyal satu dimensi dengan rumus x(t)= cos(2*pi*5*t) + cos(2*pi*10*t) + cos(2*pi*20*t) + cos(2*pi*50*t)
FT dari sinyal tersebut FT dari sinyal tersebut. Terlihat bahwa FT dapat menangkap frekuensi-frekuensi yang dominan dalam sinyal tersebut, yaitu 5,10, 20, 50 (nilai maksimum F(u) berada pada angka 5,10, 20, 50)
Rumus FT – 2 dimensi
Domain spatial x dan y pada f(x,y) Domain frekuensi u dan v pada F(u,v) Magnitude F(u,v) adalah |F(u,v)|= [R 2(u,v) + I 2(u,v)]1/2 Rumus FT – 2 dimensi
Contoh perhitungan f(0,0) = 1, f(1,1) = 2, f(0,1) =3, f(1,0)=4 Hitung nilai F(0,0)!
Karakteristik domain frekuensi (1)
•
Separability – Kolom dan baris dihitung terpisah
It usually is impossible to make direct associations between specific components of image & its transform General statement: frequencies in the fourier transform associate with patterns of intensity variations in an image Karakteristik domain frekuensi (2) Example: an image of a room – Slowest varying frequency component corresponds to smooth gray level variations on the walls and floor – The higher frequency corresponds to faster and faster gray level changes in the image edges of object Karakteristik domain frekuensi (3) Citra SEM DFT 2D citra SEM
– Linearity – F(f+g) = F(f) + F(g) – F(kf) = k F(f), k = konstanta DFT 2D - Some properties (3) • Koefisien DC – F(0,0) = jumlah semua pixel,
– Shifting – Menggeser DC ke tengah matrik DFT 2D - Some properties (4) • Shifting – Menggeser DC ke tengah matrik
Karakteristik domain frekuensi (4)
Displaying transforms Fourier transforms in matlab
DFT 2D - Some properties (1) DFT as spatial filter – exp[….] independent terhadap f(x,y)
–
–
Sebagai contoh untuk F(0,0) maka nilai exp[….] = 1 F(0,0) merupakan hasil filtering f(0,0) dengan filter berukuran mxn dan elemen = 1. Citra filter
F(0,0) = (10x1) + (10x1) + (40x1) + … + (60x1) + (80x1) + (50x1) = 650 DFT 2D - Some properties (2)
Filtering in the frequency domain (1) • Equalizer – Equalizer mengubah lagu menjadi frekuensi-frekuensi sesuai alat musik yang digunakan. Frekuensi drum berbeda dengan gitar, misalnya. – Filtering pada domain frekuensi dapat dianalogikan dengan mengatur equalizer ketika kita mendengarkan
lagu dari mp3 player. Apakah kita ingin memperjelas bass atau treble,misalnya. (Nixon & Aguado. 2002. feature extraction & image processing. ) Filtering in the frequency domain (2)
DFT 2D- lowpass firlter (4) • Ideal lowpass filter
•
Butterworth lowpass filter
•
Gaussian lowpass filter
Filtering in the frequency domain (3) Tugas: • dikumpulkan 19-11-2009 1. Hitung transformasi fourier untuk data citra berikut: f(0,0)= 10, f(1,0)=20, f(0,1)=30 dan f(1,1) = 40! 2. Buat ulasan, 1 halaman A4, tulis tangan, tentang Fast Fourier Transforms (F F T)
DFT 2D- lowpass firlter (1) Suppose we have a Fourier transform matrix F, shifted so that the DC coeficient is in the centre. Since the low frequency components are towards the centre, we can perform low pass filtering by multiplying the transform by a matrix in such a way that centre values are maintained, and values away from the centre are either removed or minimized. One way to do this is to multiply by an ideal low-pass matrix, which is a binary matrix m defined by:
DFT 2D lowpass firlter (2) • D = 15 ideal lowpass filter
• •
The circle (c ) displayed is just such a matrix, with D=15 Then the inverse Fourier transform of the elementwise product of F and m is the result we require:
DFT 2D- lowpass filter (3) Caranya ? • Ambil citra (cm) lalu lakukan DFT (cf)
•
Lakukan lowpass filter (cf ) * (c) element wise multiplication
•
Transformasi invers
