MKB3383 - Teknik Pengolahan Citra Pengolahan Citra di Kawasan Frekuensi (Transformasi Fourier) Muhammad Zidny Naf’an, M.Kom. Gasal 2016/2017
Outline • Pengolahan Citra di Kawasan Spasial VS Kawasan Frekeunsi • Fourier Transform 1D • Fourier Transform 2D • Filtering pada Kawasan Frekuensi
Outline • Pengolahan Citra di Kawasan Spasial VS Kawasan Frekuensi • Fourier Transform 1D • Fourier Transform 2D • Filtering pada Kawasan Frekuensi
Pengolahan Citra di Kawasan Spasial VS Kawasan Frekuensi
Image Input
Image Processing
Image Output
Pengolahan Citra di Kawasan Spasial VS Kawasan Frekeunsi Image Input Frequency Distribution Processing
Inverse Transformation Image Output
Pengolahan Citra di Kawasan Frekuensi • Diperlukan pasangan transformasi dan transformasi balik (invers) • Contoh transformasi:
Transformasi Fourier • Ditemukan oleh Baptiste Joseph Fourier (17681830), ahli fisika dari Prancis • Digunakan untuk memetakan citra dari kawasan spasial ke dalam kawasan frekuensi • Melihat karakteristik spektrum citra • Ide dasar: semua fungsi yang bersifat periodis, betapapun kompleks fungsi tersebut, dapat dinyatakan sebagai penjumlahan sinusoid. Kuncinya terletak pada komposisi amplitude dan fase sinus setiap frekuensi.
Transformasi Fourier
Outline • Pengolahan Citra di Kawasan Spasial VS Kawasan Frekuensi • Fourier Transform 1D • Fourier Transform 2D • Filtering pada Kawasan Frekuensi
Fourier Transform 1D Discrete Fourier Transform 1D • Terdapat fungsi f(x) yang memiliki N data (f(0), f(1), f(2), f(3), f(4), …, f(N-1)) • Jika dikenakan DFT, maka didapatkan: F(u) = (F(0), F(1), F(2), F(3), F(4), .., F(N-1))
Fourier Transform 1D Proses perubahan fungsi dari ranah ranah spasial ke ranah frekuensi dilakukan melalui Transformasi Fourier. Sedangkan perubahan fungsi dari ranah frekuensi ke ranah spasial dilakukan melalui Transformasi Fourier Balikan (invers).
Rumus FT – 1 Dimensi
Rumus FT Kontinyu 1 Dimensi 1 F (u ) N
f ( x) exp[2 jux]dx
j=
−1
Rumus Invers-FT Kontinyu 1 Dimensi
f ( x) F (u ) exp[2 jux]du
Rumus DFT 1 Dimensi (DFT = Discrete Fourier Transform) 1 N 1 F (u ) x 0 f ( x) exp[2 jux / N ] N Rumus Invers-DFT 1 Dimensi f ( x) x 0 F (u ) exp[2 jux / N ] N 1
Transformasi Fourier 1-D • Nilai u disebut dengan domain frekuensi. • Masing-masing dari M buah dari F(u) disebut komponen frekuensi dari transformasi. • Transformasi Fourier seringkali dianalogikan dengan prisma kaca. Prisma kaca adalah suatu alat yang dapat memisahkan cahaya menjadi berbagai komponen warna. Masing-masing komponen warna memiliki panjang gelombang yang berbeda.
13
Euler Formula’s pada DFT 1D 𝑒 𝑖𝜃 = cos 𝜃 + 𝑖 𝑠𝑖𝑛𝜃 𝑒 −𝑖𝜃 = cos 𝜃 − 𝑖 𝑠𝑖𝑛𝜃 Karena:
exp[2 jux] cos 2ux j sin 2ux
1 N 1 Maka: F (u ) f ( x) exp[2 jux / N ] x 0 N 1 N 1 x 0 f ( x)(cos(2ux / N ) j sin( 2ux / N ))] N
Contoh Penghitungan DFT 1 dimensi (Gonzalez hlm 90-92) 1 N 1 1 N 1 f ( x ) exp[ 2 j ux / N ] f ( x)(cos(2ux / N ) j sin( 2ux / N ))] x 0 x 0 N N contoh : f (0) 2, f (1) 3, f (2) 4, f (3) 4 F (u )
1 N 1 f ( x)(cos(2 0 x / N ) j sin( 2 0 x / N ))] x 0 N 1 [ f (0) f (1) f (2) f (3)] 3.25 4 1 3 F (1) x 0 f ( x)(cos(2x / 4) j sin( 2x / 4))] 4 1 [2(1 0) 3(0 j ) 4(1 0) 4(0 j ) 4 1 1 (2 3 j 4 4 j ) (2 j ) 0.5 0.25 j 4 4 1 1 F (2) [1] 0.25 F (3) [2 j ] 0.5 0.25 j 4 4 F ( 0)
Contoh Penghitungan Inverse DFT 1 dimensi f ( x) x 0 F (u )(cos(2ux / N ) j sin( 2ux / N ))] N 1
F (0) 3.25, F (1) 0.5 0.25 j , F (2) 0.25, F (3) 0.5 0.25 j f (0) x 0 F (u )(cos(2. .u.0 / N ) j sin( 2. .u.0 / N ))] N 1
[ F (0) F (1) F (2) F (3)] 3.25 (0.5 0.25 j ) (0.25) (0.5 0.25 j ) 2
Bagaimana dengan f(1), f(2), dan f(3) ?
Contoh Penghitungan DFT 1 dimensi (Gonzalez hlm 90-92) Hasil FT 1D pada slide sebelumnya terdiri dari bilangan real dan imajiner. Maka dapat digambarkan pada tabel berikut: F(u)
f(x) Real
Real
2
3.25
3
DFT
-0.5
4
-0.25
4
-0.5
Imajiner 0.25 -0.25
Transformasi Fourier 1-D • |F(u)| = [R2(u) + I2(u)]1/2 disebut magnitude atau spektrum dari transformasi Fourier dan : I (u ) (u ) tan R ( u ) fase dari disebut sudut fase atau spektrum 1
transformasi.
19
Soal Latihan DFT 1D 1 F (u ) N
N 1 x 0
f ( x)(cos(2ux / N ) j sin( 2ux / N ))]
Misalkan terdapat fungsi f(x) = (2,4,1,5) Bagaimanakah bentuk Transformasi Fourier-nya?
Outline • Pengolahan Citra di Kawasan Spasial VS Kawasan Frekuensi • Fourier Transform 1D • Fourier Transform 2D • Filtering pada Kawasan Frekuensi
Transformasi Fourier 2-D • Fungsi citra input biasanya dikalikan dulu dengan (-1)x+y sebelum dilakukan perhitungan transformasi Fourier, karena titik pusat dari transformasi Fourier perlu digeser.
f ( x, y)(1) x y F (u M / 2, v N / 2) Persamaan di atas menetapkan bahwa titik pusat Transformasi Fourier dari fungsi f(x,y)(-1)x+y [yaitu F(0,0)] berada pada lokasi u=M/2 dan v=N/2.
22
Rumus DFT – 2 dimensi M 1 N 1
FT : F (u , v) y 0 x 0
ux vy ux vy f ( x, y )(cos(2 ( )) j sin( 2 ( ))) N M N M
1 M 1 N 1 ux vy ux vy InversFT : f ( y, x) F ( v , u )(cos( 2 ( )) j sin( 2 ( ))) MN v 0 u 0 N M N M M tinggi citra (jumlah baris) N lebar citra (jumlah kolom) Dalam hal ini, citra berukuran MxN (M baris dan N kolom). v bernilai dari 0 sampai dengan M-1 u bernilai dari 0 sampai dengan N-1. Dalam hal ini, u dan v menyatakan frekuensi, sedangkan nilai F(u, v) dinamakan koefisien Fourier atau spektrum frekuensi diskret. 24
Contoh • Misalkan terdapat citra sebagai berikut: M 1 N 1
0
1
1
1
F (u , v) f ( x, y )(cos(2 ( y 0 x 0
2 1 2 1
F (0,0) f ( x, y )(cos(2 ( y 0 x 0
ux vy ux vy )) j sin( 2 ( ))) N M N M ux vy ux vy )) j sin( 2 ( ))) N M N M
0 .0 0 .0 0 .0 0 .0 )) j sin( 2 ( ))) 2 2 2 2 0 .0 0 .1 0 .0 0 .1 f (0,1)(cos(2 ( )) j sin( 2 ( )) 2 2 2 2 0 . 1 0 .0 0 . 1 0 .0 f (1,0)(cos(2 ( )) j sin( 2 ( )) 2 2 2 2 0 .1 0 .1 0 .1 0 .1 f (1,1)(cos(2 ( )) j sin( 2 ( ))) 2 2 2 2 (0(1) 1(1) 1(1) 1(1)) ( f (0,0)(cos(2 (
3
M 1 N 1
0
1
1
1
F (u , v) f ( x, y )(cos(2 ( y 0 x 0
2 1 2 1
F (0,1) f ( x, y )(cos(2 ( y 0 x 0
ux vy ux vy )) j sin( 2 ( ))) N M N M ux vy ux vy )) j sin( 2 ( ))) N M N M
0 .0 1 .0 0 .0 1 .0 )) j sin( 2 ( ))) 2 2 2 2 0 .0 1 .1 0 .0 1 .1 f (0,1)(cos(2 ( )) j sin( 2 ( )) 2 2 2 2 0 .1 1 .0 0 . 1 1 .0 f (1,0)(cos(2 ( )) j sin( 2 ( )) 2 2 2 2 0 .1 1 .1 0 .1 1 .1 f (1,1)(cos(2 ( )) j sin( 2 ( ))) 2 2 2 2 (0(1) 1(1) 1(1) 1(1)) ( f (0,0)(cos(2 (
1
Fast Fourier Transform (FFT) • Merupakan algoritma penghitungan yang mengurangi kompleksitas FT biasa dari N2 menjadi N log N saja • Pada implementasinya, FFT merupakan cara yang umum digunakan untuk menghitung FT diskret • InversFT juga dapat dihitung dengan kompleksitas N log2N (IFFT) – Di Matlab : fft(x) atau fft2(X) untuk FT dan ifft(x) atau ifft2(X) untuk invers FT
27
Visualisasi DFT Spektrum FT |𝐹 𝑢, 𝑣 | =
𝑅 2 𝑣, 𝑢 + 𝐼 2 (𝑣, 𝑢)
Dengan R(u,v) menyatakan bagian riil dan I(v,u) menyatakan imajiner
Sudut Fase Transformasi
I (u , v )
(u , v ) tan 1 R (u , v )
Dengan R(u,v) menyatakan bagian riil dan I(v,u) menyatakan imajiner
Power Spectrum FT
P (u , v ) F (u , v )
2
R 2 (u , v ) I 2 (u , v ) Dengan R(u,v) menyatakan bagian riil dan I(v,u) menyatakan imajiner
Contoh hasil visualisasi
• Mengingat nilai dalam spektrum terlalu lebar, penerapan logaritma biasa digunakan hanya untuk kepentingan visualisasi. • Contoh: >> S2 = log(1 + abs(F)); >> imshow(S2, []); • Penambahan angka 1 dimaksudkan untuk menghindari terjadinya log(0).
• Adanya sifat pengulangan pada transformasi Fourier (keadaan yang seperti berulang yang muncul pada setiap pojok dalam kotak frekuensi) • Nilai pada M/2 menuju ke M-1 adalah pengulangan dari titik asal 0 hingga M/2 – 1. • Berlaku juga pada arah mendatar. • Berdasarkan sifat ini, untuk kepentingan visualisasi, titik awal (0,0) seringkali diubah agar terletak di tengah-tengah kotak frekuensi
Contoh Fourier Spectrum
32
Comparison : Low Frequency Original Images Showing a silhoutte of spaceship (Girty Lue).
Transform View
Low Frequency Small variation between image’s component, major frequency is low. Shown by the Fourier Transform Result 33
Comparison : High Frequency Original Images
Showing image of Freedom and Justice with METEOR unit also the Eternal Spaceship from Gundam SEED.
Transform View
High Frequency High variation between image’s component, major frequency is High. Shown by the Fourier Transform Result 34
Outline • Pengolahan Citra di Kawasan Spasial VS Kawasan Frekuensi • Fourier Transform 1D • Fourier Transform 2D • Filtering pada Kawasan Frekuensi
Filtering pada Domain Frekuensi •
Langkah-langkah filtering pada domain frekuensi adalah: 1. Kalikan citra input dengan (-1)x+y untuk memusatkan transformasi. 2. Hitung F(u,v), DFT dari citra pada langkah (1). 3. Kalikan F(u,v) dengan fungsi filter H(u,v). 4. Hitung inverse DFT dari citra pada langkah (3). 5. Gunakan bagian real dari citra pada langkah (4) 6. Kalikan hasil (5) dengan (-1)x+y.
Filtering pada Domain Frekuensi
37
Filter Penghalusan • Model filtering pada domain frekuensi adalah : G(u,v) = H(u,v) F(u,v) dengan F(u,v) adalah transformasi Fourier dari citra yang akan dihaluskan. • Tujuannya adalah memilih fungsi filter H(u,v) yang menghasilkan G(u,v) dengan menurunkan komponen frekuensi tinggi dari F(u,v).
38
Contoh Filtering pada Domain Frekuensi • Filter yang didefinisikan sebagai berikut: if (u, v) ( M / 2, N / 2) 0 H (u, v) 1 otherwise
disebut filter notch karena filter tersebut adalah fungsi konstan dengan sebuah lubang (notch) di pusatnya.
39
Contoh Hasil Filter Notch
40
Ideal Lowpass Filter (ILPF) 1 𝑗𝑖𝑘𝑎 𝐷 𝑣, 𝑢 ≤ 𝐷0 • 𝐻 𝑣, 𝑢 = 0 𝑗𝑖𝑘𝑎 𝐷 𝑣, 𝑢 > 𝐷0 • Dalam hal ini, D0 adalah bilangan non-negatif yang biasa disebut radius filter, yang menentukan ambang frekuensi, dan D(v,u) adalah jarak antara (v,u) terhadap pusat filter, yang dinyatakan dengan
• 𝐷 𝑣, 𝑢 = 𝑣 2 + 𝑢2
Ideal Lowpass Filter (ILPF)
Butterworth low pass filter (BLPF) • jenis filter lolos-rendah yang digunakan untuk memperbaiki efek bergelombang yang dikenal dengan sebutan ringing, • 𝐻 𝑣, 𝑢 =
1 1+[𝐷(𝑣,𝑢)/𝐷0 ]2𝑛
• n ordo filter
Butterworth low pass filter (BLPF)
HIGHPASS DAN LOWPASS FILTERING PADA DOMAIN FREKUENSI
Filtering pada Domain Frekuensi • Filter lowpass adalah filter yang mengubah (menurunkan) komponen frekuensi tinggi, dan melewatkan (passing) komponen frekuensi rendah. Citra yang difilter menggunakan filter lowpass memiliki detail yang kurang tajam dibandingkan citra asal. • Filter highpass adalah filter yang mengubah (menurunkan) komponen frekuensi rendah, dan melewatkan (passing) kompinen frekuensi tinggi. ” high frequencies. Citra yang difilter menggunakan filter highpass memiliki detail yang lebih tajam dibandingkan citra asal. 46
Filtering pada Domain Frekuensi
47
Filtering pada Domain Frekuensi
48
Sample: Monochrome Low Pass
Gaussian Blur
High Pass
Sharpen More
49
Sample: Color Low Pass
Gaussian Blur
High Pass
Sharpen More
50
Other Implementation : Low Pass Filter “Noised” image
Smooth image
Gaussian Low Pass
Original Image
Flare effect (beam)
Enhanced Image
Reduced Flare effect
51
Other Implementation : High Pass Filter
Easier to read text
Hard to read text
Gaussian High Pass
Original Image
Enhanced Image
Flare effect (beam)
More Flare Effect Reduced Eye Point
52
Other Implementation : High Pass Filter Easier to read text
Hard to read text
Sharpen
Original Image
Enhanced Image More Flare Effect
Flare effect (beam)
Exposure of Eye Point
53
Other Implementation : High Boost Filtering
Unsharp Mask
Original Image
Enhanced Image Enhanced Flare Effect Reduction of Eye Point
Flare effect (beam)
54
Unsharp Mask: Generating Sharp Image by substracting blur version of the image itself
Other Implementation : Combination Filtering High Pass
Multiplied
Original Image
Low Pass
Enhanced Image Slight Flare Effect Reduction of Eye Point
55
TUGAS Terdapat data seperti berikut:
• f(x) = (3, 4, 4, 5) • Hitunglah transformasi Fourier F(0) hingga F(3).
Referensi • Kadir, Abdul dan Adhi Susanto. 2013. Teori Dan Aplikasi Pengolahan Citra. Yogyakarta: Penerbit Andi. • Slide Pengolahan Citra, Departement Teknik Informatika IT Telkom • Prof. Aniati Murni A., Pengolahan Citra Digital, Fak. Ilmu Komputer, Universitas Indonesia. • Rinaldi Munir, Pengolahan Citra Digital • Pengolahan Citra Digital, ITS. http://share.its.ac.id/pluginfile.php/374/mod_res ource/content/1/03_-_Transformasi_Citra.ppt