Convolution and Correlation

Slide1Convolution and CorrelationProf.Dr. Aniati Murni (R 1202) Dina Chahyati, MKom (R 1226) Fakultas Ilmu Komputer Universitas Indonesia

Slide22Proses Konvolusi (1) Proses Konvolusi (1)  Formula Konvolusi: = dummy variable of integration  Mekanisme konvolusi dalam bentuk integral ini tidak mudah untuk digambarkan (Gonzales and Woods, 1992)

Slide33Konvolusi pada Domain Kontinue Konvolusi pada Domain Kontinue Coba kaitkan dengan keterangan pada slide di halaman 7 !

Slide44Konvolusi dan Transformasi Fourier Konvolusi dan Transformasi Fourier  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)

Slide55Konvolusi pada Domain Diskrit (1) Konvolusi pada Domain Diskrit (1)  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                     dan f(x) = 0 bila g(x) = g(x) bila                   dan g(x) = 0 bila  Konvolusi diskrit: (dilakukan melalui proses flip and shift terhadap fungsi g(x))

Slide66Konvolusi 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 =   -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]  

Slide77Konvolusi pada Domain Diskrit (3): Pendekatan Rumus Konvolusi Konvolusi pada Domain Diskrit (3): Pendekatan Rumus Konvolusi  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)=0      g(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 = -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.nya hasil yang diperoleh sama dengan cara sebelumnya !  

Slide88Proses Konvolusi pada Citra 2-Dimensi Proses Konvolusi pada Citra 2-Dimensi  Bentuk Kontinue dan Diskrit:

Slide99Proses 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 dengan mengaplikasikan low pass filter dan sebaliknya, proses sharpening dapat diperoleh dengan mengaplikasikan high pass filter

Slide1010Proses Konvolusi dan Dekonvolusi (2) Proses Konvolusi dan Dekonvolusi (2)  Contoh efek blurring (bayangkan bila terjadi pada piksel citra  2-dimensi) point response function ideal response (averaging) deconvolution function (filtering)

Slide1111Proses Filtering dengan High Pass Filter (1) Proses Filtering dengan High Pass Filter (1)

Slide1212Proses Filtering dengan High Pass Filter (2) Proses Filtering dengan High Pass Filter (2) Operator Image Hasil Filtering -1 -1 -1 0 0 0 0 0 0 0 4  4    9    7     8     3   3 -1   8 -1 0 1 2 3 4 3 0   4  4    9    7      8    3  3 -1 -1 -1 0 1 1 1 9 8 0 1 -4 -23   34  30 30 30 0 1 2 1 9 9 0 0 -2 -20   31  31 34 34 0 2 2 1 3 9 0 8 -3 -26 -30  35 35 35 0 1 2 9 7 9 0 2  2    1   25  57 53 53                      0 0 0 0 0 0 0 2  2    1   25  57 53 53 Meningkatkan perbedaan intensitas pada garis batas antar wilayah

Slide1313Proses Filtering dengan Low Pass Filter (2) Proses Filtering dengan Low Pass Filter (2) Operator Image Hasil Filtering 0.1 0.1 0.1 0 0 0 0 0 0 0   0.5  0.5  0.9  2.9  2.6  2.4  2.4 0.1 0.1 0.1 0 1 2 3 4 3 0   0.5  0.5  0.9  2.0  2.6  2.4  2.4 0.1 0.1 0.1 0 1 1 1 9 8 0   0.8  0.8  1.3  3.2  4.7  4.2  4.2 0 1 2 1 9 9 0   0.9  0.9  1.2  2.9  5.0  4.7  4.7 0 2 2 1 3 9 0   1.0  1.0  2.1  3.6  5.7  4.6  4.6 0 1 2 9 7 9 0   0.7  0.7  1.7  2.4  3.8  2.8  2.8                      0 0 0 0 0 0 0   0.7  0.7  1.7  2.4  3.8  2.8  2.8 Menghilangkan perbedaan intensitas pada garis batas antar wilayah

Slide1414Edge Detection Turunan Kedua 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 =   -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] Operator Laplace mempertahankan informasi aslinya

Slide1515Edge Detection Turunan Pertama f(x) = [0 0 1 2 3 4 0]      [  0 0  1  2  3  4  0 0 0] g(x) = [1 -1]                       di-flip tetap [-1 1]   [-1  1  0  0  0  0  0 0 0] maka f(x)*g(x) = 0x-1 + 0x1 + 1x0 + 2x0 + 3x0 + 4x0 + 0x0 + 0x0  + 0x0 =   0 0x0 + 0x-1 + 1x1 + 2X0 + 3x0 + 4x0 + 0x0 + 0x0  + 0x) =  1 0x0 + 0x0 + 1x-1 + 2x1 + 3x0 + 4x0 + 0x0 + 0x0  + 0x0 =   1 0x0 + 0x0 + 1x0 + 2x-1 + 3x1 + 4x0 + 0x0 + 0x0  + 0x0 =   1 0x0 +0x0 + 1x0 + 2x0 + 3x-1 + 4x1  + 0x0 + 0x0  + 0x0 =   1 0x0 + 0x0 + 1x0 + 2x0 + 3x0 + 4x-1 + 0x1 + 0x0  + 0x0 =  -4 0x0 + 0x0 + 1x0 + 2x0 + 3x0 + 4x0 + 0x-1 + 0x1  + 0x0 =    0 0x0 + 0x0 + 1x0 + 2x0 + 3x0 + 4x0 + 0x0 + 0x-1 + 0x1=     0 f(x)*g(x) = [0  1  1  1  1 –4   0  0  ] Oprator Robert melakukan outlining (informasi asli hilang)

Slide1616Proses Korelasi Proses Korelasi  Korelasi pada domain kontinue:  Korelasi pada domain diskrit:  Teori Korelasi

Slide1717Perbedaan antara Konvolusi dan Korelasi Perbedaan antara Konvolusi dan Korelasi  Konvolusi (operator *):  Flip g(x) and shift by f(x)  Aplikasi filtering system  Korelasi (operator  o):  Slide g(x) by f(x)  Aplikasi template matching

Slide1818Proses Korelasi pada Domain Kontinue Proses Korelasi pada Domain Kontinue  Kalau pada konvolusi didahului dengan proses flip fungsi operatornya, pada korelasi proses flip tersebut tidak dilakukan

Slide1919Template Matching pada Industrial Image Template Matching pada Industrial Image

Slide2020Proses Korelasi pada Domain Diskrit: Untuk Citra Biner Proses Korelasi pada Domain Diskrit: Untuk Citra Biner Template Image Hasil Korelasi 1 1 1 1 1 0 0 0 7 4 2 x x 1 1 1 1 1 1 0 0 5 3 2 x x 1 1 1 1 0 1 0 0 2 1 1 x x 0 0 0 0 0 x x x x x 0 0 0 0 0 x x x x x x = undefined match terjadi pada nilai terbesar                  (posisi/lokasi match)

Slide2121Proses Template Matching: Untuk Citra Multiple Gray Level Proses Template Matching: Untuk Citra Multiple Gray Level Template Image Hasil Korelasi 2 3 1 2 3 2 1 3 7 4 2 x x 1 2 3 1 2 3 3 3 1 2 2 x x 3 1 2 3 3 3 2 3 1 1 0 x x 0 0 0 0 0 x x x x x 0 0 0 0 0 x x x x x  3  3  3  3  3  3  3  3 adi pada nilai terbesar                  (posisi/lokasi match)

Slide2222Operasi Korelasi: Pendekatan Rumus Korelasi Operasi Korelasi: Pendekatan Rumus Korelasi  Rumus Korelasi:  Citra : 0 0 1 1 1 0 0 1 1 0                 Tempalate: 1 1 1                 f(0)=0 f(1)=0 f(2)=1 f(3)=1 f(4)=1 dst.              g(0)=1 g(1)=1 g(2)=1 g(3)=0 g(4)=0 dst.              f(0)g(0) = f(0)g(0)+f(1)g(1)+f(2)g(2) … = 1              f(1)g(1) = f(0)g(1)+f(1)g(2)+f(2)g(3) … = 2              f(2)g(2) = f(0)g(2)+f(1)g(3)+f(3)g(4) … = 3 dst.  Hasil Korelasi   1 2 3 2 1 1 2 2 1        posisi matching  

Slide2323Rumus Korelasi Rumus Korelasi  Formula korelasi diatas mempunyai kelemahan:  Rentan terhadap ukuran yang tidak sama antara template dan obyek yang ada pada citra  Rentan terhadap orientasi yang berbeda antara template dan obyek yang ada pada citra  Banyak penelitian dan usulan rumus korelasi yang telah dikembangkan