TRANSFORMASI CITRA: PROSES KONVOLUSI

TRANSFORMASI CITRA: PROSES KONVOLUSI

BertalyaUniversitas Gunadarma

PROSES KONVOLUSIPROSES KONVOLUSI

2

• Formula Konvolusi:

= dummy variable of integration

• Mekanisme konvolusi dalam bentuk integral ini tidak mudah untuk digambarkan(Gonzales and Woods, 1992)

Konvolusi pada Domain KontinueKonvolusi pada Domain Kontinue

3

Konvolusi dan Transformasi FourierKonvolusi dan Transformasi Fourier

• Konvolusi merupakan proses penting padaanalisis domain frekwensi karena f(x)*g(x) dan F(u)G(u) membentuk suatu pasangantransformasi Fourier (Fourier transform pair)

• Teori konvolusi:f(x)*g(x) F(u)G(u)f(x)g(x) F(u)*G(u)

4

Konvolusi pada Domain Diskrit (1)Konvolusi pada Domain Diskrit (1)

5

• Bila A adalah periode dalam diskritisasi f(x) dan B adalah periode dalam diskritisasi g(x), maka hasilkonvolusi akan mempunyai periode M dimana M=A+B

• Periode f(x) dan g(x) masing-masing dibesarkanmenjadi M dengan menyisipkan 0

f(x) = f(x) bila dan f(x) = 0 bilag(x) = g(x) bila dan g(x) = 0 bila

• Konvolusi diskrit: (dilakukan melalui proses flip and shift terhadap fungsi g(x))

Konvolusi pada Domain Diskrit (2): pendekatan shift kernel operator

Konvolusi pada Domain Diskrit (2): pendekatan shift kernel operator

f(x) = [0 0 1 2 3 4 0] [ 0 0 1 2 3 4 0 0 0]g(x) = [-1 4 –1] karena simetri di-flip tetap [-1 4 –1]

[-1 4 –1 0 0 0 0 0 0]maka f(x)*g(x) =

0x-1 + 0x4 + 1x-1 + 2x0 + 3x0 + 4x0 + 0x0 + 0x0 + 0x0 = -10x0 + 0x-1 + 1x4 + 2X-1 + 3x0 + 4x0 + 0x0 + 0x0 +0x0 = 20x0 + 0x0 + 1x-1 + 2x4 + 3x-1 + 4x0 + 0x0 + 0x0 + 0x0 = 40x0 + 0x0 + 1x0 + 2x-1 + 3x4 + 4x-1 + 0x0 + 0x0 + 0x0 = 60x0 +0x0 + 1x0 + 2x0 + 3x-1 + 4x4 + 0x-1 + 0x0 + 0x0 = 130x0 + 0x0 + 1x0 + 2x0 + 3x0 + 4x-1 + 0x0 + 0x0 + 0x0 = -40x0 + 0x0 + 1x0 + 2x0 + 3x0 + 4x0 + 0x-1 + 0x4 + 0x-1 = 00x0 + 0x0 + 1x0 + 2x0 + 3x0 + 4x0 + 0x0 + 0x-1 + 0x4 = 00x0 + 0x0 + 1x0 + 2x0 + 3x0 + 4x0 + 0x0 + 0x0 + 0x-1 = 0

f(x)*g(x) = [ -1 2 4 6 13 –4 0 0 0] 6

Konvolusi pada Domain Diskrit (3): Pendekatan Rumus Konvolusi

Konvolusi pada Domain Diskrit (3): Pendekatan Rumus Konvolusi

7

• Kita lihat kembali rumusan konvolusi:

• f(0) =0; f(1)=0; f(2)=1; f(3)=2; f(4)=3; f(5)=4; f(6)=0; … f(9)=0g(7)=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 = -1f(1)*g(1) = f(0)g(1) + f(1)g(0 ) + f(2)g(-1) + dst = 2f(2)*g(2) = f(0)g(2) + f(1)g(1) + f(2)g(0) + dst = 4

dst.nya hasil yang diperoleh sama dengan cara sebelumnya !

Proses Konvolusi pada Citra 2-DProses 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 pikselpada posisi (0,0) dari kernelGeser kernel satu piksel ke kanan kemudian hitung nilai pikselpada posisi (0,0) kernel, begitu seterusnya hingga geser satu pikselke bawah, lalu mulai lagi melakukan konvolusi dari sisi kiri citra.

10

• Dengan cara yang sama, setiap baris pikseldikovolusi

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)Proses Konvolusi dan Dekonvolusi (1)

• Blurring merupakan efek pemerataan (integrasi), sedangkan deblurring / sharpening / outlining merupakan efek differensiasi

• Proses blurring dapat diperoleh denganmengaplikasikan low pass filter dan sebaliknya, proses sharpening dapat diperoleh denganmengaplikasikan high pass filter

• Filtering akan dipelajari pada proses peningkatanmutu citra (image enhancement)

13

Proses Konvolusi dan Dekonvolusi (2)Proses Konvolusi dan Dekonvolusi (2)

• Contoh efek blurring (bayangkan bila terjadi padapiksel citra 2-dimensi)

point response function ideal response(averaging)

deconvolution function(filtering) 14

• Filter/ mask/ kernel gaussian

15

TRANSFORMASI CITRA• Mengapa perlu transformasi ?

– Setiap orang pada suatu saat pernah menggunakan suatu teknikanalisis dengan transformasi untuk menyederhanakanpenyelesaian 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 suatuinformasi tertentu yang tidak tersedia sebelumnya

16

Transformasi Citra• Contoh :

– jika ingin mengetahui informasi frekuensi kita memerlukantransformasi Fourier

– Jika ingin mengetahui informasi tentang kombinasi skala danfrekuensi kita memerlukan transformasi wavelet

• Transformasi citra, sesuai namanya, merupakan proses perubahanbentuk 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 spasialke 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 fungsiperiodik (sinyal) dapat dibentuk dari penjumlahangelombang-gelombang sinus/cosinus.

• Contoh : Sinyal kotak merupakan penjumlahan dari fungsi-fungsi sinus berikut

f(x) = sin(x) + sin(3x)/3 + sin(5x)/5 +sin(7x)/7 + sin(9x)/9 …

20

Fungsi kotak sebagai penjumlahanfungsi-fungsi sinus

• Cobakan juga program matlab berikut untuk melihatsampai batas n berapa fungsi yang dihasilkan sudahberbentuk 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

22Gambar a) n = 1, b) n =3, c) n = 7, d) n = 99

(a)

(c) (d)

(b)

FT - Motivasi• Jika semua sinyal periodik dapat dinyatakan dalam

penjumlahan fungsi-fungsi sinus-cosinus, pertanyaanberikutnya 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) kemudiandapat diperoleh kembali sinyal awal dengan menghitungf(x), menggunakan rumus:

23

Rumus FT – 1 D

• Rumus FT kontinu 1 dimensi

uxjuxuxj

duuxjuFxf

dxuxjxfuF

πππ

π

π

2sin2cos]2exp[:formula sEuler'

]2exp[)()(

]2exp[)()(

−=−

=

−=

∫∫∞

∞−

∞

∞−

• Rumus FT diskret 1 dimensi

∑

∑−

=

−

=

=

−=

1

0

1

0

]/2exp[)(1)(

]/2exp[)(1)(

N

x

N

x

NuxjuFN

xf

NuxjxfN

uF

π

π

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 frekuensi-frekuensi yang dominan dalam sinyal tersebut, yaitu 5,10, 20, 50

(nilai maksimum F(u) beradapada angka 5,10, 20, 50)

27

Contoh Penghitungan FT 1 dimensi(Gonzalez hlm 90-92)

28jjFF

jjjj

jj

xjxxfF

ffff

NxjNxxfN

F

ffffcontoh

NuxjNuxxfN

NuxjxfN

uF

x

N

x

N

x

N

x

25.05.0]2[41)3(25.0]1[

41)2(

25.05.0)2(41)4432(

41

)0(4)01(4)0(3)01(2[41

))]4/2sin()4/2)(cos((41)1(

25.3)]3()2()1()0([41

))]/02sin()/02)(cos((1)0(

4)3(,4)2(,3)1(,2)0(:

))]/2sin()/2)(cos((1]/2exp[)(1)(

3

0

1

0

1

0

1

0

−−=+−=−=−=

+−=+−=+−−=

++−−+−+−=

−=

=+++=

−=

====

−=−=

∑

∑

∑∑

=

−

=

−

=

−

=

ππ

ππ

πππ

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

kolom)(jumlah citralebar Nbaris)(jumlah citra tinggiM

)]//(2exp[),(),(:

)]//(2exp[),(1),(:

1

0

1

0

1

0

1

0

==

+=

+−=

∑∑

∑∑−

=

−

=

−

=

−

=

M

u

N

v

M

x

N

y

NvyMuxjvuFyxfInversFT

NvyMuxjyxfMN

vuFFT

π

π

30

Contoh FT 2 DimensiSumber: http://www.icaen.uiowa.edu/~dip/LECTURE/LinTransforms.html

31

Untuk menampilkan nilai FT suatu citra, karena keterbatasan display, seringkali digunakan nilai D(u,v)= c log [1 + |F(u,v)|]

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 :

]/)(2exp[),(),(),(]/)(2exp[),(

00

0000

NvyuxjvuFyyxxfvvuuFNyvxujyxf

+−⇔−−−−⇔+−

ππ

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

)/,/(1),(

),(),(

bvauFab

byaxf

vuaFyxaf

⇔

⇔

• Nilai rata-rata

∑∑−

=

−

=

==1

0

1

02 )0,0(1),(1),(

N

x

N

yF

Nyxf

Nyxf

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