Pertemuan ke-4 (Konvolusi dan Transformasi Fourier).

Report
Pertemuan ke-4
• Dua operasi matematis penting dalam pengolahan
citra:
 Operasi konvolusi (spatial filter/ discret
convolution filter)
 Transformasi Fourier
• Konvolusi 2 buah fungsi f(x) dan g(x) didefinisikan
sebagai berikut:

h( x )  f ( x ) * g ( x ) 
 f (a) g ( x  a)da

Tanda * menyatakan operator konvolusi, dan peubah
(variable) a adalah peubah bantu (dummy variable)
Cont.
• Konvolusi merupakan proses penting pada
analisis domain frekwensi karena f(x)*g(x) dan
F(u)G(u) membentuk suatu pasangan
transformasi Fourier (Fourier transform pair).
• Teori konvolusi:
f(x)*g(x)  F(u)G(u)
f(x)g(x)  F(u)*G(u)
Konvolusi pada Domain Diskrit
Bila A adalah periode dalam diskritisasi f(x) dan B
adalah periode dalam diskritisasi g(x), maka hasil
konvolusi akan mempunyai periode M dimana M=A+B
Periode f(x) dan g(x) masing-masing dibesarkan menjadi
M dengan menyisipkan 0
f(x)=f(x) bila 0 ≤ x ≤ A-1 dan f(x)=0 bila A ≤ x ≤ M-1
g(x)=g(x) bila 0 ≤ x ≤ B-1 dan f(x)=0 bila B ≤ x ≤ M-1
Konvolusi diskrit dilakukan melalui proses flip dan shift
terhadap fungsi g(x).
M 1
h ( x )  f ( x ) * g ( x )   f ( m) g ( x  m)
m 0
Cont.
 g(x) disebut kernel konvolusi atau kernel
penapis (filter).
 Kernel g(x) merupakan suatu jendela yang
dioperasikan secara bergeser pada sinyal
masukan f(x), yang dalam hal ini, jumlah
perkalian kedua fungsi pada setiap titik
merupakan hasil konvolusi yang dinyatakan
dengan keluaran h(x).
Pendekatan Shift Kernel Operator

g ( x )   1 4
  1
 
f ( x)  0 0 1 2 3 4 0  0 0 1 2 3 4 0 0 0
Maka f(x)*g(x)=



 1 karena simetri di - flip tetap - 1
4
1
0
0
0
0
0
4
0

0x-1 + 0x4 + 1x-1 + 2x0 + 3x0 + 4x0 + 0x0 + 0x0 + 0x0 = -1
0x0 + 0x-1 + 1x4 + 2X-1 + 3x0 + 4x0 + 0x0 + 0x0 +0x0 = 2
0x0 + 0x0 + 1x-1 + 2x4 + 3x-1 + 4x0 + 0x0 + 0x0 + 0x0 = 4
0x0 + 0x0 + 1x0 + 2x-1 + 3x4 + 4x-1 + 0x0 + 0x0 + 0x0 = 6
0x0 +0x0 + 1x0 + 2x0 + 3x-1 + 4x4 + 0x-1 + 0x0 + 0x0 = 13
0x0 + 0x0 + 1x0 + 2x0 + 3x0 + 4x-1 + 0x0 + 0x0 + 0x0 = -4
0x0 + 0x0 + 1x0 + 2x0 + 3x0 + 4x0 + 0x-1 + 0x4 + 0x-1 = 0
0x0 + 0x0 + 1x0 + 2x0 + 3x0 + 4x0 + 0x0 + 0x-1 + 0x4 = 0
0x0 + 0x0 + 1x0 + 2x0 + 3x0 + 4x0 + 0x0 + 0x0 + 0x-1 = 0
F(x)*g(x) = [-1 2 4 6 13 -4 0 0 0]

-1
Pendekatan Rumus Konvolusi
Kita lihat kembali rumusan konvolusi:
M 1
h ( x )  f ( x ) * g ( x )   f ( m) g ( x  m)
m 0
f(0)=0; f(1)=0; f(2)=1; f(3)=2; f(4)=3; f(5)=4; f(6)=0; ...; f(8)=0
g(6)=0; ...; g(1)=0; g(0)=-1; g(-1)=4; g(-2)=-1
f(0)*g(0) = f(0)g(0) + f(1)g(-1) + f(2)g(-2) + dst = -1
f(1)*g(1) = f(0)g(1) + f(1)g(0) + f(2)g(-1) + dst = 2
f(2)*g(2) = f(0)g(2) + f(1)g(1) + f(2)g(0) + dst = 4
Dst
Hasil yang diperoleh sama dengan cara sebelumnya!
Proses Konvolusi pada Citra 2-D
• Bentuk Kontinue dan Diskrit:
8
Ilustrasi konvolusi
9
Contoh : citra f(x,y) berukuran 5 X 5
dengan kernel atau mask 3 X 3
•
f(x,y) * g(x,y)
•
Operasinya :
Tempatkan kernel pada sudut kiri atas kemudian hitung nilai piksel
pada posisi (0,0) dari kernel
Geser kernel satu piksel ke kanan kemudian hitung nilai piksel
pada posisi (0,0) kernel, begitu seterusnya hingga geser satu piksel
ke bawah, lalu mulai lagi melakukan konvolusi dari sisi kiri citra.
10
•
Dengan cara yang sama, setiap baris piksel
dikovolusi
11
Hasil konvolusi :
•
•
Jika nilai piksel (-), nilai tsb dijadikan 0, jika nilai > nilai max gray
level maka dilakukan clipping
Untuk masalah piksel pinggir, solusi untuk masalah ini adalah :
– Piksel pinggir diabaikan, tidak dikonvolusi
– Duplikasi elemen citra, elemen kolom ke-1 disalin ke kolom M+1,
begitu juga sebaliknya lalu konvolusikan.
– Elemen yang ditandai dengan (?) diasumsikan bernilai 0 atau
konstanta yang lain sehingga konvolusi piksel pinggir dapat dilakukan.
•
Konvolusi piksel pinggir tidak memperlihatkan efek yang kasat
mata.
12
Proses Konvolusi dan Dekonvolusi (1)
• Blurring merupakan efek pemerataan (integrasi),
sedangkan deblurring / sharpening / outlining
merupakan efek differensiasi
• Proses blurring dapat diperoleh dengan
mengaplikasikan low pass filter dan sebaliknya,
proses sharpening dapat diperoleh dengan
mengaplikasikan high pass filter
• Filtering akan dipelajari pada proses peningkatan
mutu citra (image enhancement)
13
Proses Konvolusi dan Dekonvolusi (2)
• Contoh efek blurring (bayangkan bila terjadi pada
piksel citra 2-dimensi)
point response function
(averaging)
ideal response
deconvolution function
(filtering)
14
• Filter/ mask/ kernel gaussian
15
TRANSFORMASI CITRA
•
•
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
16
Transformasi Citra
•
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, 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
17
Transformasi Piksel dan Ruang
•
•
•
•
•
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 merupakan proses perubahan citra dari suatu
ruang/domain ke ruang/domain lainnya, contoh: dari ruang spasial
ke ruang frekuensi
Ada beberapa transformasi ruang yaitu :
– Transformasi Fourier (basis: cos-sin)
– Transformasi Hadamard/Walsh (basis: kolom dan baris yang
ortogonal)
– Transformasi DCT (basis: cos)
18
19
Transformasi Fourier (FT)
• 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 kotak merupakan penjumlahan dari fungsifungsi sinus berikut
f(x) = sin(x) + sin(3x)/3 + sin(5x)/5 +
sin(7x)/7 + sin(9x)/9 …
20
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)
21
(a)
(c)
(b)
(d)
Gambar a) n = 1, b) n =3, c) n = 7, d) n = 99
22
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:
23
Rumus FT – 1 D
• Rumus FT
kontinu 1 dimensi
∞
F(u) = ∫ f (x) exp[−2
−
jπux]dx
∞
f (x) = ∞ F(u)exp[2 jπux]du
−
Euler's ∫formula:
exp[−2 jπux] = cos2πux j sin 2πux
−
∞
• Rumus FT diskret 1 dimensi
1
N
f (x) exp[−2 jπux / N
F (u) = ∑−1
x =0
N
]
1
N
F (u) exp[2 jπux / N ]
f (x) = ∑−1
x =0
N
24
Contoh FT 1 D
Contoh berikut diambil dari Polikar
(http://engineering.rowan.edu/~polikar/WAVELETS/WTtutorial.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
25
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)
(Sumber: Polikar)
26
FT dari sinyal tersebut
FT dari sinyal tersebut.
Terlihat bahwa FT dapat
menangkap frekuensifrekuensi yang dominan
dalam sinyal tersebut, yaitu
5,10, 20, 50
(nilai maksimum F(u) berada
pada angka 5,10, 20, 50)
27
Contoh Penghitungan FT 1 dimensi
(Gonzalez hlm 90-92)
1 N
1 N
−1 f (x)exp[−2 jπux/ N]
∑
∑−1 f (x)(cos(2πux/ N) j sin(2πux/ N))]
N x=0 =
N x=0 −
contoh: f (0) = 2, f (1) = 3, f (2) = 4, f (3) = 4
F(u) =
1 N −1
∑ f (x)(cos(2π 0x / N) − j sin(2π 0x /
N x=0 N))]
1
= [ f (0) + f (1) + f (2) + f (3)] =
F(0) =
3.25 3
1
F(1) = 4 ∑x=0 f (x)(cos(2πx / 4) − j sin(2πx /
4
4))]
1
= [2(1− 0) + 3(0 − j) + 4(−1− 0) + 4(0
+ j)
4
1
1
= 4 (2 −3 j − 4 + 4 j)4= (−2 + j) = −0.5+
1
1
−
=
=
−
F(2) =
[1]
F(3)
[2 + j] = −0.5 −
0.25j
−0.25
0.25 j
4
4
28
Contoh Penghitungan FT
• 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
29
Rumus FT – 2 D
• Rumus FT 2 dimensi
1
FT : F (u, v) =
MN
M −1 N
−1
f (x, y) exp[−2 jπ (ux / + vy / N
∑∑
x=0 y =0 M
)]
M −1 N
−1
+ vy N )]
InversFT : f ( x, y) = ∑∑ F (u, v) exp[2 jπ (ux / /
M
u=0 v=0
M = tinggi citra (jumlah baris)
N = lebar citra (jumlah kolom)
30
Contoh FT 2 Dimensi
Sumber: http://www.icaen.uiowa.edu/~dip/LECTURE/LinTransforms.html
Untuk menampilkan nilai FT suatu citra, karena keterbatasan display, seringkali
digunakan nilai D(u,v)= c log [1 + |F(u,v)|]
31
Sifat-sifat FT 2 dimensi
• Separable :
– Pemrosesan FT 2 dimensi dapat dilakukan
dengan melakukan FT 1 dimensi terhadap kolom,
kemudian dilanjutkan dengan FT 1 dimensi
terhadap baris
• Translasi :
f (x, y) exp[−2 jπ (u0 x +v0 y) / N] ⇔ F(u −u0 , v
−v0 )
f (x − x, y − y) ⇔ F(u, v) exp[−2 jπ (ux0 +vy0 )
/ N]
32
Sifat-sifat FT 2 dimensi
• Periodik
– FT dan IFT bersifat periodik dengan periode N (N
adalah jumlah titik)
• Rotasi
– Jika kita merotasikan f(x,y) sebanyak θ0. maka F(u,x)
juga akan berotasi sebanyak θ0, demikian pula
sebaliknya.
• Distributif
– FT dan IFT bersifat distributif terhadap penjumlahan
tapi tidak terhadap perkalian
33
Sifat-sifat FT 2 dimensi
• Penskalaan
af (x, y) ⇔ aF(u,v)
1
f (ax,by) ⇔
F(u / a,v / b)
ab
• Nilai rata-rata
1
f ( x, y ) = 2
N
N −1 N
−1
∑
∑
f ( x, y ) =
1
F (0,0)
N
x=0 y =0
34
Fast Fourier Transform (FFT)
• Merupakan algoritma penghitungan yang
mengurangi kompleksitas FT biasa dari N2
menjadi N log2N 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
35

similar documents