BAB II TEORI PENUNJANG Pada bagian ini penulis akan menjelaskan mengenai beberapa teori yang berkenaan dengan penelitian Tugas Akhir ini. Sub bab 2.1, menjelaskan mengenai perkembangan dari teknik dalam melakukan content-based image retrieval (CBIR). Kemudian penjelasan lebih lanjut mengenai CBIR akan penulis jelaskan pada sub bab 2.2 tentang beberapa metode yang biasa digunakan dalam melakukan visual content decriptions. Kemudian, penulis akan menjelaskan mengenai pengukuran jarak/kemiripan (similarity/distances measurement) antar dua fitur vektor (visual features) dan metode analisa performa dari image retrieval akan dijelaskan dalam sub bab 2.3, dan 2.4. 2.1 DIATOM Diatom adalah alga uniselular, yang ditemukan dimana saja, dimana terdapat air dan cukup cahaya untuk menstimulasi fotosintesis. Lebih dari 10.000 spesies telah digambarkan. Diatom umumnya berukuran panjang atau diameter 40-200 µm, tetapi dapat lebih kecil (45 µm) atau lebih besar (hingga 1 mm). Mereka memiliki bentuk bermacam-macam, mulai dari berbentuk seperti jarum hingga berbentuk bulat. Aspek forensik yang paling berarti dari diatom terletak pada kemampuannya untuk mengelilingi dirinya dengan cangkang silika— frustule. Diatom pertama kali diisolasi dari jaringan paru pada korban tenggelam lebih dari 85 tahun yang lalu; kemudian, mereka ditemukan di organ tubuh lainnya. Sejak saat itu, bagaimanapun, mengundang kontroversi terus dilanjutkan memandang kegunaan dari analisa diatom sebagai tes konfirmasi pada kematian akibat tenggelam. Secara singkat, teknik terbaru untuk isolasi diatom melibatkan pencernaan jaringan oleh asam-umumnya paru, darah, ginjal atau sumsum tulang-selanjutnya disentrifuse dan dibilas. Sisa akhir kemudian diperiksa dengan mikroskop fase kontras untuk mencari adanya alga khusus. Diambil sejumlah air dari tempat yang diduga merupakan tempat kejadian perkara dan kontrol laboratorium yang sesuai juga diperiksa. Penyokong berupa teknik yang menekankan pada penunjukkan terdapatnya sejumlah diatom dalam jumlah yang bermakna yang diperoleh dari tubuh yang diangkat dari air dapat menegaskan: − Bahwa kematian merupakan akibat dari tenggelam. 5
− −
Bahwa seseorang masih hidup saat air masuk. Tempat tenggelam dengan membandingkan spesies diatom dalam air dan dalam tubuh. Perhatian kritis dipusatkan pada beberapa masalah, dengan tidak mengurangi spesifisitasnya. Penekanan ditempatkan pada hasil positif palsu yang tampaknya sering terjadi, diatom ditemukan terdapat pada jaringan tubuh yang jelas-jelas tidak tenggelam. Sifat alamiah diatom yang terdapat dimana-mana menjadi pokok masalah; kontaminasi ekstrinsik dari peralatan laboratorium sama mungkinnya dengan kontaminasi dari organ tubuh yang telah mengandung diatom sebelumnya dari sumber-sumber alamiah diatom, baik dengan cara inhalasi maupun dengan penelanan. Hasil negative-palsu dapat terjadi, diatom tampaknya tidak terdapat pada jaringan tubuh seseorang yang hampir pasti tenggelam. Hal ini pasti akan diduga pada kasus `dry` drowning tetapi kegagalan untuk menemukan diatom juga dapat terjadi pada tenggelam khas `wet` drowning. Pendapat-pendapat, kemudian, bervariasi secara luas mengenai kegunaan analisa diatom dalam penyelidikan kematian akibat tenggelam. Terdapat dukungan yang meyakinkan pada akhir dari kedua spektrum. Pada beberapa laboratorium, analisa diatom dapat memberikan informasi tambahan yang, jika dipertimbangkan dengan seksama bersama-sama dengan parameter lainnya, dapat berguna dalam menilai kematian dari korban yang diangkat dari air. Tidak dapat disangkal bahwa `nilai` tes ini meningkat dengan pengalaman penggunaannya, banyak kegagalan untuk mengambil nilai dapat dikarenakan oleh kegagalan dalam teknik. Tes tenggelam lainnya telah disokong selama beberapa tahun. Salah satu dari yang pertama kali adalah pengukuran kadar klorida dalam darah yang diambil dari sisi kanan dan kiri jantung (tes Gettler`s)kematian akibat tenggelam dikatakan akan menunjukkan perbedaan lebih dari 25 mg/ 100 ml (7 mmol/ L). Tes ini tidak lagi dianggap dapat diandalkan-terlalu banyak perubahan-perubahan yang tidak dapat diramalkan pada kadar klorida darah yang terjadi post mortem. Saransaran terbaru untuk tes tenggelam yang mungkin dapat berguna mencakup kadar strontium dan fluorine dalam darah, peptida natriuretik atrial, haptoglobin, dan fosfolipid surfaktan paru. Pada saat ini tidak ada satupun diantaranya yang diterima secara umum sebagai dapat menyediakan bukti forensik adekuat yang dapat diandalkan.
6
2.2 CBIR (Content Based Image Retrieval)[11] Content Based Image Retrieval (CBIR), teknik yang mengunakan fitur gambar (visual contents) dalam melakukan pencarían gambar dalam database gambar gambar yang besar. Penelitian dan pengembangan image retrieval dimulai pada sekitar 1970-an. Pada tahun 1979, sebuah konferensi mengenai Database Techniques for Pictorial Application diadakan di Florida. Sejak itu aplikasi dalam melakukan manajemen database gambar menarik perhatian para peneliti. Awalnya teknik yang dipakai bukan mencari fitur gambar melainkan berdasarkan penambahan deskripsi mengenai gambar dalam bentuk teks. Dengan kata lain pertama gambar diberi teks berdasarkan gambar tersebut kemudian dilakukan pencarian berdasarkan teks (text based) mengunakan sistem database manajemen tradisional. Namun karena pembangkitan teks secara otomatis, mengenai deskripsi spectrum gambar, secara detail sulit untuk dilakukan kebanyakan aplikasi text-based image retrieval saat itu melakukan pemberian teks deskripsi gambar secara manual. Pemberian deskripsi gambar berdasarkan teks merupakan usaha yang merepotkan dan mahal bila diaplikasikan dalam database gambar yang sangat besar dan selain itu sering bersifat subjektif, bersifat kontekstual (context-sensitive), dan mendeskripsikan gambar secara tidak lengkap (incomplete). Hasilnya, text-based image retrieval tradisonal sulit untuk mampu mendukung berbagai variasi dari input query. Pada awal 1990-an perkembangan teknologi internet dan teknologi sensor image digital terjadi dengan sangat pesat. Sebagai hasilnya jumlah produksi gambar digital oleh para peneliti, akademisi, militer, industri, kesehatan dan para penguna lainnya berkembang dengan sangat pesat. Sedangkan pencarian gambar berdasarkan teks sudah tidak mampu lagi secara optimal menyelesaikan permasalahan ini. Sehingga diperlukan suatu metode baru dalam melakukan image retrieval. Pada tahun 1992, National Science Foundation of the United States mengadakan workshop mengenai pengembangan metode baru dalam image database management system. Dalam seminar itu dikemukan metode baru yang lebih efekfif dan presisi dalam merepresentasikan informasi dari fitur gambar yaitu berdasarkan properti atau fitur yang terkandung dalam gambar itu sendiri. Sejak tahun 1997 penelitian dan publikasi dibidang content-based image retrieval seperti ekstraksi fitur, indexing, image database managent berkembang dengan pesat, contohnya QBIC produk IBM, Virage produk virage inc, Netra produk synapse dan beberapa teknik dan sistem mengenai aplikasi CBIR lainnya. 7
CBIR, mengunakan fitur gambar seperti warna, bentuk, teksture dan dan informasi spatial untuk merepresentasikan dan mengindekskan gambar. Dalam sistem aplikasi CBIR secara umum (gambar) fitur visual dari kumpulan gambar dalam database gambar diekstraksi dan didekripsikan dalam bentuk vektor fitur multi-dimensi. Fitur ini disimpan dalam database fitur. Untuk mencari gambar dalam database, user memerlukan gambar query. Gambar query ini kemudian diekstraksi fitur visual-nya dan direpresentasikan dalam bentuk vector fitur. Kemiripan atau jarak antara vector fitur dari gambar model dan gambar query dihitung oleh proses indexing. Proses indexing diperlukan untuk melakukan proses pencarian yang cepat dan efisien. Feedback dari user merupakan modifikasi dari proses pencarian gambar untuk meghasilkan pencarian gambar yang lebih presisi. Dalam bagian ini penulis akan menjelaskan mengenai teknik – teknik yang dipakai dalam melakukan ekstraksi fitur gambar.
Gambar 2.1 Diagram dari Content-Based Image Retrieval.
2.3 Ekstraksi Fitur Gambar Berbicara mengenai fitur gambar, secara umum ada dua fitur gambar yaitu visual dan semantic(tekstual). Fitur visual adalah fitur yang terdapat dalam gambar itu sendiri. Fitur visual dibagi menjadi dua yaitu general dan domain spesifik. General visual content termasuk warna, bentuk, teksture dan relasi spasial. Domain spesific content contohnya seperti wajah manusia. Sematic content adalah penambahan deskripsi secara tekstual berdasarkan ekstraksi fitur gambar. Pada penelitian tugas akhir ini penulis fokuskan pada pembahasan mengenai
8
General visual content selanjutnya akan penulis tulis sebagai fitur gambar. Ekstraksi fitur gambar yang dapat dilakukan untuk citra digital adalah merubah citra/image input a[m,n] menjadi sebuah image output b[m,n] (atau dengan representasi lain) dapat dikelompokkan kedalam tiga kategori sebagaimana ditunjukkan dalam tabel 2.1. Tabel 2.1 Tipe dari ekstraksi fitur gambar. Ukuran citra = N x N; ukuran neighborhood= P x P. Sebagai catatan bahwa complexitas dikhususkan untuk operasi per pixel. *Point
Nilai output pada koordinat tertentu hanya tergantung pada nilai input pada kordinat yang sama.
Constant
* Local
Nilai output pada koordinat tertentu tergantung pada nilai input pada neighborhood (ketetanggaan) dari koordinat yang sama. Karakteristik Nilai ouput pada koordinat terntentu tergantung pada semua nilai input image.
P2
Operasi * Global
Kompleksi-tas/Pixel N2
Gambar 2.2 Ilustrasi dari tipe-tipe pengoperasian citra. Pada bagian ini penulis akan menjelaskan mengenai teknik yang digunakan dalam melakukan ekstraksi fitur tekstur gambar. 2.3.1 TEKSTURE (TEXTURE) Teksture adalah salah satu fitur gambar yang sangat penting. Pengunaan fitur teksture digunakan secara luas oleh peneliti pada pengenalan pola (pattern recognition) dan komputer vision. Pada dasarnya, metode representasi teksture dapat diklasisfikasikan menjadi 9
dua, yaitu: structural dan statistical. Metode structural termasuk morphological operator dan adjacency graph, mendifinisikan teksture dengan cara melakukan identifikasi struktur primitifnya dan aturan penempatan pola. Metode ini efektif digunakan pada gambar dengan teksture yang sangat umum. Metode statistik, termasuk diantaranya : Fourier power spectra, co-occurrence matrices, shift-invariant principal component analysis (SPCA), Tamura feature, Wold decomposition, Markov random field, fractal model, dan teknik multiresolution filtering seperti Gabor and wavelet transform. Pada penelitian tugas akhir ini penulis mengunakan multiresolution filtering dalam melakukan ekstraksi fitur gambar. Diantaranya filter Gabor, DoG (Difference of Gaussian), LoG (Lapplacian of Gaussian) dan Gaussian. Sebelum penulis menjelaskan lebih lanjut mengenai filter – filter ini, akan penulis terangkan mengenai dasar – dasar konvolusi. 2.3.1.1 KONVOLUSI Ada beberapa notasi yang mungkin untuk mengindikasikan konvolusi dari dua (multi dimensional) sinyal untuk menghasilkan sebuah sinyal output. Notasi yang paling umum adalah: c=a ⊗ b=a ∗b
(2.1)
Konvolusi dari dua buah fungsi f(x) dan g(x), dinotasikan dengan f(x)*g(x) didefinisikan sebagai suatu fungsi integral, yaitu: ∞
f x ∗g x = ∫ f α g x−α dα
(2.2)
−∞
dimana α merupakan suatu variabel integrasi sembarang. Merupakan hal yang penting untuk melakukan konvolusi dalam domain frekuensi, berdasarkan analisa bahwa f(x)*g(x) dan F(u)G(u) akan membentuk pasangan transformasi Fourier (Fourier transform pair). Dengan kata lain, jika f(x) memiliki transformasi Fourier F(u)dan g(x) memiliki transformasi Fourier G(u). berikutnya f(x)*g(x) memiliki transformasi Fourier F(u)G(u). Secara formal ditetapkan sebagai berikut,
f x ∗g x ⇔ F u G u
(2.3)
menunjukkan bahwa konvolusi dalam domain x dapat juga diperoleh dengan mengambil invers dari sebuah transformasi Fourier F(u)G(u). 10
Hasil yang sama diperoleh bahwa konvolusi dalam domain frekuensi mengembalikan perkalian dalam domain x, sebagai berikut,
f x g x =F u ∗G u
(2.4)
kedua persamaan tersebut secara umum dikenal dengan convolution theorem. Untuk konvolusi pada bidang dua dimensi, memiliki rumus analog, sehingga untuk dua buah fungsi f(x,y) dan g(x,y) dinotasikan dengan, ∞
f x,y ∗g x,y =∫ ∫ f α,β g x−α,y −β dαdβ
(2.5)
−∞
Teorema konvolusi pada bidang dua dimensi, kemudian dinyatakan dengan relasi sebagai berikut,
dan
f x ,y ∗g x ,y ⇔ F u,v G u,v
(2.6)
f x ,y g x ,y ⇔ F u,v G u,v
(2.7)
Salah satu penggunaan konvolusi yang sangat penting adalah dalam penentuan suatu persamaan pada gambar yang akan dicari derivatifnya, yaitu dengan mengkonvolusikan gambar dengan suatu filter tertentu. 2.3.1.2 Filter Gabor Sejak penemuan kelompok garis kristal dari korteks visual utama dari otak mamalia ±30 tahun yang lalu oleh Hubel dan Wiesel, dan sejumlah besar eksperimen dan penelitian terhadap berbagai teori dengan luas menambah pengetahuan kita terhadap bidang ini dan berbagai respon positif muncul untuk sel-sel ini. Secara teori sebuah wawasan penting telah dikembangkan oleh Marcelja dan Daugman bahwa sel-sel sederhana pada korteks visual dapat dibentuk dengan fungsi gabor. Fungsi Gabor yang di perkenalkan oleh Daugman adalah berupa band-pass filter yang bekerja lokal spasial yang mencapai limit teorinya untuk resolusi conjoint(penggabungan) dari informasi dalam domain spasial 2D dan domain frekuensi 2D. Fungsi Gabor pertama kali diperkenalkan oleh Denis Gabor sebagai tool untuk deteksi sinyal dalam noise. Gabor menunjukkan 11
bahwa terdapat prinsip kuantum “quantum principel” untuk informasi. Gabungan domain frekuensi dan domain waktu dan frekuensi untuk ID sinyal harus diperbaiki dengan baik sehingga tidak ada sinyal atau filter yang menempatinya kurang dari area minimum tertentu didalamnya. Bagaimanapun ada sebuah pertukaran antara resolusi waktu dan frekuensi. Gabor menemukan bahwa dengan modulasi eksponensial kompleks Gaussian akan menghasilkan pertukaran yang terbaik. Untuk misalnya suatu kasus, Fungsi Gabor diperoleh dari sebuah fungsi Gaussian yang diperbaiki dengan frekuensi modulasi geombang yang bervariasi. Daugman mengembangkan kerja Gabor kedalam filter dua dimensi (Daugman 1980,1985). Dia menunjukkan bahwa perluasan dari kriteria optimasi hubungan ke dua dimensi telah dipenuhi dengan kelompok fungsi-fungsi yang dapat dinyatakan sebagai filter spasial terdiri dari gelombang rataan sinusoidal dengan dua dimensi ellips envelope Gaussian. Transormasi fourier yang bersesuaian berisi ellips Gaussian dipindahkan dari sumbu asal ke bidang spasial dari envelope Gaussian. Fungsi tersebut, berikutnya lebih dikenal dengan Gabor Elementary function (GEF) dapat didesain pada frekuensi tinggi maupun rendah, atau dengan kata lain GEF merupakan filter bandpass. Persamaan untuk GEF diberikan sebagai berikut, h x ,y =g x ', y' exp [ j2π Ux +Vy ] (2.8) (x’,y’)=(x cos θ+y sin θ, -x sin θ +y cos θ) menyatakan koordinat garis lurus dari domain spasil yang dirotasikan, (U,V) mewakili frekuensi 2D tertentu fungsi g(x,y) merupakan Gaussian 2D,
{ [ ]} 2
1 1 g x,y= exp − 2 2 2 πσ
x y σx σy
2
(2.9)
dimana σx dan σy menyatakan luas spasial dan bandwidth dari filter. Dengan mengasumsikan σx= σy=σ dan parameter θ tidak dibutuhkan, persamaan GEF pada 2.6 disederhanakan menjadi,
h x,y =
{
}
x2 +y 2 1 exp − exp [ j2π Ux+Vy ] 2 πσ 2 2σ 2
dan untuk fungsi Gaussian menjadi,
12
(2.11)
g x,y=
1 e 2 πσ 2
−
x 2 +y 2 2σ 2
(2.12)
dari persamaan matematika diatas dapat kita lihat bahwa respon impuls dari GEF diperoleh dari perkalian fungsi Gaussian dengan fungsi kompleks. Fungsi Kompleks : e− j2π ux+vy (2.13) 2.4 Image Matching Image matching adalah metode yang bertujuan untuk mengetahui kemiripan dua buah gambar. Pertama, gambar query dan gambar database ditentukan. Gambar query disebut juga dengan gambar acuan atau gambar template adalah suatu gambar yang dijadikan acuan informasi (content) dalam proses pen-carian. Sedangkan gambar database atau kumpulan gambar target adalah sekumpulan gambar yang akan digunakan sebagai database gambar. Disini akan dijelaskan metode pencarian kemiripan fitur dengan menggunakan Euclidean Distance. 2.4.1 Euclidean Distance Dalam matematika, Euclidean Distance adalah jarak diantara dua buah obyek atau titik. Euclidean Distance dapat digunakan untuk mengukur kemiripan (matching) sebuah obyek dengan obyek yang lain. Euclidean Distance diantara titik P = (p1, p2,...,pn) dan Q = (q1, q2,...,qn) didefinisikan sebagai:
n
p1−q1 2 p2−q2 2 .. . pn−qn 2 = ∑ pi−qi 2 . i= 1
(2.14)
Dalam proyek akhir ini digunakan mean dan standard deviasi sebagai parameter yang digunakan untuk mencari nilai Euclidean Distance. Oleh karena itu, pada proyek akhir ini Euclidean Distance didefinisikan dengan
d mn = μ
Q mn
−μ
T mn 2
σ Q
mn
−σ
T mn 2
13
(2.15)
Qmn
Di mana μ
merupakan nilai mean gambar query dan μ
mean gambar training. Sedangkan σ
Qmn
Tmn
merupakan
merupakan nilai standart deviasi
Tmn
gambar query dan σ merupakan standart deviasi gambar training. Keduanya merupakan nilai yang digunakan untuk pencarian kemiripan fitur gambar. Mean merupakan penjumlahan data dibagi dengan jumlah observasinya, digunakan untuk mengidentifikasi lokasi pusat sebuah data terkadang dapat diartikan sebagai rata-rata. Karena itu Mean dapat digunakan untuk menggolongkan kumpulan data pada kelompok tertentu. Nilai Mean didefinisikan dengan formula berikut:
M=
∑ x N
(2.16)
Di mana x merupakan nilai data, N adalah jumlah orientasi. Mean didapat dari menjumlahkan semua data dan membaginya dengan jumlah orientasi. Standart Deviasi digunakan untuk mengukur penyebaran kumpulan data dan hubungan mean dengan semua data. Standart Deviasi dihitung
S=
∑ X −M 2 .
n−1 (2.17) dengan formula berikut : Di mana X adalah nilai data, M nilai mean yang sebelumnya didapat, n adalah jumlah orientasi. Standard deviasi didapat dari menguadratkan hasil pengurangan data dengan nilai mean, kemudian menjumlahkan dengan semua nilainya. Lalu membaginya dengan jumlah orientasi data dikurangi 1, setelah itu mencari nilai akar kuadratnya.
14
