BAB II LANDASAN TEORI
2.1
Temu Kembali Citra Berbasis Konten (TKCBK)
2.1.1 Pengertian TKCBK Menurut
(Kondekar, Kolkure, & Kore, 2010) pengertian dari TKCBK
adalah temu kembali dari gambar berbasis fitur visual seperti warna, tekstur dan bentuk. Alasan pengembangannya adalah karena pada banyak basis data gambar yang besar, metode tradisional dari pengindeksan gambar telah terbukti tidak cukup, melelahkan, dan sangat memakan waktu. Menurut (Thawari & Janwe, 2011) pengertian dari TKCBK adalah sebuah teknik yang menggunakan konten visual, yang biasanya dikenal sebagai fitur, untuk mencari gambar dari basis data gambar skala besar berdasarkan permintaan pengguna dalam bentuk sebuah gambar query.
2.1.2 Tahapan Utama TKCBK Tahapan utama dalam sistem TKCBK adalah sebagai berikut (Kondekar, Kolkure, & Kore, 2010), (Candan & Sapino, 2010, pp14-15), & (Pun & Wong, 2008) : •
Ekstraksi fitur (feature extraction) : Ekstraksi fitur-fitur dari gambar yang merupakan representasi dari gambar tersebut, bertujuan untuk membedakan di antara gambar-gambar.
6
7
•
Pengindeksan (indexing) : Fitur-fitur yang sudah diekstrak sebelumnya, kemudian diindeks lalu disimpan di dalam basis data. Pengindeksan bertujuan untuk mempercepat pencarian dengan mengeliminasi bagian dari basis data yang yang tidak relevan berdasarkan urutan dan struktur dalam data.
•
Pencocokan (matching) : Pencocokan fitur-fitur antara fitur-fitur yang diekstrak dari gambar query dengan fitur-fitur pada basis data untuk menghasilkan sebuah hasil yang secara visual mirip. Skema dari sistem TKCBK secara umum dapat digambarkan pada gambar
di bawah ini :
Gambar 2.1 Skema Sistem TKCBK
8
2.1.3 Tujuan TKCBK Menurut (Lakshmi, Damodaram, Rao, & Lal, 2008) & (Rao, Rao, & Govardhan, 2011) tujuan utama dari TKCBK adalah mengembangkan teknik berbasis konten visual yang efisien untuk menemukan gambar relevan. Jika pencarian bergantung kepada kata kunci, maka pencarian tersebut menjadi melelahkan.
2.1.4 Contoh Aplikasi TKCBK Contoh beberapa aplikasi dari sistem TKCBK yang tercantum pada paper (Kondekar, Kolkure, & Kore, 2010) adalah : •
Pemeriksaan keamanan : Finger print atau retina scanning untuk hak akses.
•
Kekayaan intelektual : Pendaftaran gambar merek dagang, dimana kandidat merek dagang baru dibandingkan dengan merek dagang yang telah ada untuk memastikan tidak ada resiko dari kebingungan atas kepemilikan kekayaan.
•
Diagnosa medis : Menggunakan TKCBK pada basis data medis yang berisi gambar-gambar
medis
untuk
membantu
mendiagnosa
dengan
mengidentifikasi kasus serupa di masa lalu. •
Pencegahan kriminal : Sistem pengenalan wajah otomatis, digunakan oleh polisi.
9
2.2
Fitur Sebuah fitur didefinisikan untuk menangkap properti visual tertentu dari
sebuah gambar, baik secara global untuk seluruh gambar ataupun secara lokal untuk sekelompok kecil pixel (Datta, Joshi, Li, & Wang, 2008). Ada beberapa fitur dari gambar yang digunakan dalam TKCBK. Fitur – fitur tersebut adalah (Kondekar, Kolkure, & Kore, 2010) : •
Warna : Salah satu dari fitur yang paling penting, memungkinkan pengenalan gambar oleh manusia adalah warna. Warna adalah sebuah properti yang bergantung kepada pantulan cahaya ke mata dan pengolahan dari informasi tersebut di otak. Kita menggunakan warna setiap hari untuk mengatakan perbedaan antara objek, tempat, dan waktu. Biasanya warna didefinisikan dalam ruang warna tiga dimensi. Hal tersebut bisa berupa RGB (Red, Green, & Blue), HSV (Hue, Saturation, & Value) atau HSB (Hue, Saturation, & Brightness).
Gambar 2.2 Ruang Warna RGB (Candan & Sapino, 2010, p35)
10
Gambar 2.3 Ruang Warna HSV (Candan & Sapino, 2010, p39) •
Tekstur : Tekstur adalah properti bawaan dari semua permukaan yang mendeskripsikan
pola
visual,
masing-masing
memiliki
properti
kehomogenan. Tekstur mengandung informasi penting mengenai susunan struktur dari permukaan, seperti awan, daun, batu bata, kain, dan lain-lain. Tekstur juga mendeskripsikan hubungan permukaan dengan lingkungan sekitarnya. Intinya, ini adalah fitur yang mendeskripsikan komposisi fisik yang khas dari permukaan. •
Bentuk : Bentuk mungkin didefinisikan sebagai konfigurasi karakteristik permukaan dari sebuah objek, sebuah garis atau kontur. Hal ini memungkinkan sebuah objek untuk dibedakan dari sekitarnya oleh garisnya. Representasi dari bentuk secara umum dapat dibagi menjadi dua kategori : berbasis batas (boundary-based) dan berbasis wilayah (Region-based). Representasi bentuk berbasis batas hanya menggunakan batas luar dari bentuk. Representasi bentuk berbasis wilayah menggunakan seluruh wilayah dari bentuk.
11
Gambar 2.4 Berbasis Batas & Berbasis Wilayah (Kondekar, Kolkure, & Kore, 2010)
2.3
Colour Averaging Technique Pada penelitian (Kekre, Thepade, & Maloo, 2010), mereka membandingkan
performa dan akurasi dari 6 metode colour averaging technique. Metode-metode tersebut adalah row mean, column mean, forward diagonal mean, backward diagonal mean, row & column mean, dan forward & backward diagonal mean.
2.3.1 Row Mean & Column Mean Menurut
(Kekre, Thepade, & Maloo, 2010) pengertian dari row mean
adalah kumpulan rata-rata nilai intensitas dari masing-masing baris, sedangkan pengertian dari column mean adalah kumpulan rata-rata nilai intensitas dari masing-masing kolom.
12
Gambar 2.5 Row Mean & Column Mean (Kekre, Thepade, & Maloo, 2010)
2.3.2 Forward Diagonal Mean & Backward Diagonal Mean Menurut
(Kekre, Thepade, & Maloo, 2010) pengertian dari forward
diagonal mean adalah kumpulan rata-rata nilai intensitas dari seluruh elemen diagonal depan, sedangkan pengertian dari backward diagonal mean adalah kumpulan rata-rata nilai intensitas dari the elemen diagonal belakang.
13
Gambaar 2.6 Forwaard Diagonall Mean (Kek kre, Thepadee, & Maloo, 2010)
Gambarr 2.7 Backwaard Diagonaal Mean (Kek kre, Thepade, & Maloo, 2010)
14
2.4
Gray Level Co-occurrence Matrix (GLCM) Menurut
(Rao, Rao, & Govardhan, 2011) Gray Level Co-occurrence
Matrix (GLCM) terdiri dari nilai peluang, Hal ini didefinisikan oleh P(i,j|d,Ө) yang mengekspresikan peluang dari pasangan pixel pada arah Ө dan jarak d. GLCM adalah sebuah matriks simetri dan tingkatannya ditentukan oleh gambar gray-level. Elemen pada matriks dihitung menggunakan persamaan berikut : , | ,Ө
, | ,Ө ∑ ∑ , | ,Ө
Gambar di bawah ini terdiri dari gambar gray level (a), GLCM untuk d = 1 dan Ө = 0o (b), dan GLCM untuk d = 1 dan Ө = 90o.
Gambar 2.8 Gambar Gray Level & GLCM (Gao, 2009, p394)
Berikut adalah fitur – fitur tekstur yang diproses dari GLCM dimana p(x,y) adalah nilai gray-level pada koordinat (x,y) (Rao, Rao, & Govardhan, 2011): •
Energy : Mengukur gray-scale gambar yang menggambarkan perubahan kehomogenan, mencerminkan distribusi dari keseragaman bobot dan tekstur gray-scale gambar. ,
15
•
Contrast : Mengukur bagaimana nilai dari matriks terdistribusi dan banyaknya gambar perubahan lokal mencerminkan kejernihan gambar dan tekstur dari kedalaman bayangan. Contrast yang besar menggambarkan tekstur yang lebih dalam. ,
•
Entropy : Mengukur ketidakteraturan pada tekstur gambar. Entropy minimum ketika co-occurrence matrix untuk semua nilai setara. ,
•
,
Inverse Difference : Mengukur banyaknya perubahan lokal pada tekstur gambar. Besarnya nilai menggambarkan bahwa tekstur gambar antara daerah yang berbeda dari kurangnya perubahan sangat merata. 1 1
2.5
,
R*-Tree
2.5.1 Pengertian R*-Tree R*-Tree adalah pengembangan dari R-Tree yang hanya berbasis pada minimalisasi area dari setiap minimum bounding rectangle (MBR). Tujuan pengembangannya adalah untuk meningkatkan performa selama proses query. Pengembangan terdiri atas kriteria-kriteria sebagai berikut (Manolopoulos, Nanopoulos, Papadopoulos, & Theodoridis, 2006, p18) & (Beckmann, Kriegel, Schneider, & Seeger, 1990) :
16
•
Meminimalkan area yang dicakup oleh setiap MBR. Kriteria ini bertujuan pada meminimalkan dead space (area yang dicakup oleh MBR tapi tidak oleh segi empat yang dicakup oleh MBR), untuk mengurangi banyaknya jalur yang ditelusuri selama proses query.
•
Meminimalkan tumpang tindih (overlap) antara MBR. Semakin besar tumpang tindih, maka semakin besar banyaknya jalur yang diharapkan diikuti untuk query.
•
Meminimalkan batas (margin) MBR. Kriteria ini bertujuan membentuk segi empat quadratic, untuk meningkatkan kinerja dari query yang memiliki bentuk quadratic yang besar. Selain itu, objek quadratic dikemas lebih mudah, sehingga MBR yang berhubungan pada tingkatan atas diperkirakan lebih kecil.
•
Memaksimalkan pemanfaatan penyimpanan. Ketika pemanfaatan rendah, banyak node cenderung dipanggil selama proses query. Ini berlaku terutama untuk query yang lebih besar, dimana sebagian besar dari entri memenuhi query. Selain itu, tinggi pohon (tree) meningkat dengan penurunan pemanfaatan node. Struktur R*-Tree terdiri dari node-node. Setiap node dari R*-Tree
berhubungan dengan MBR yang melingkupi node anaknya. Leaf dari R*-Tree menunjuk ke data (Manolopoulos, Nanopoulos, Papadopoulos, & Theodoridis, 2006, p7). Untuk memasukkan entri baru, kita harus memutuskan cabang mana yang diikuti, pada setiap tingkat dari pohon (tree). Algoritma ini disebut ChooseSubtree. ChooseSubtree dimulai dari tingkatan akar (root), dimana memilih entri yang MBRnya membutuhkan area perluasan paling kecil untuk
17
mencakup entri baru (meminimalkan area). Untuk node daun (leaf), ChooseSubtree mempertimbangkan kriteria meminimalkan tumpang tindih. Jika ChooseSubtree memilih daun (leaf) yang tidak dapat mengakomodasi entri baru (jumlah entri maksimum), R*-Tree tidak langsung membagi node, tetapi menemukan pecahan dari node yang meluap dan memasukkannya kembali (reinsert). Kumpulan entri yang dimasukkan kembali adalah yang jarak ke centroidnya paling besar (30% terbesar). Ketika luapan tidak bisa ditangani dengan memasukkan kembali, maka pembagian node dilakukan. Algoritma pembagian terdiri dari 2 langkah. Langkah pertama memutuskan sumbu pembagi (garis tepi terkecil). Langkah kedua mengurutkan entri (berdasarkan batas atas atau bawah) pada dimensi yang dipilih. Pembagian akhir adalah yang memiliki tumpang tinding (overlap) minimum antara MBR (Manolopoulos, Nanopoulos, Papadopoulos, & Theodoridis, 2006, pp18-20).
Gambar 2.9 R*-Tree (Manolopoulos, Nanopoulos, Papadopoulos, & Theodoridis, 2006, p19)
18
2.5.2 Algoritma Branch & Bound Algoritma branch & bound digunakan untuk mengurutkan dan memangkas pohon pencarian. Untuk query Q, pemangkasan node yang dikunjungi selama pencarian dilakukan berdasarkan (Manolopoulos, Nanopoulos, Papadopoulos, & Theodoridis, 2006, pp56-57) : •
MBR M dengan MINDIST(Q,M) lebih besar dari MINMAXDIST(Q,M') dari MBR M' lainnya, maka M dibuang karena tidak dapat mengandung NN.
•
Jarak dari Q ke objek O, yang lebih besar dari MINMAXDIST(Q,M) untuk MBR M, maka O dapat dibuang karena M mengandung objek O' yang lebih dekat dengan Q.
•
Setiap MBR M dengan MINDIST(Q,M) lebih besar dari jarak dari Q ke objek O dibuang karena M tidak dapat melingkupi objek lebih dekat dari O. MINDIST(Q,R) adalah jarak dari Q ke titik terdekat pada batas dari R, yang
tidak selalu harus titik sudut. MINMAXDIST(Q,R) jarak dari Q ke sudut terdekat dari R yang berdekatan (terhubung dengan tepi dari R) ke sudut yang terjauh dari Q (Manolopoulos, Nanopoulos, Papadopoulos, & Theodoridis, 2006, p56). MINDIST
|
,
|
where : if if otherwise
MINMAXDIST
,
|
|
|
|
19
where : if otherwise and if otherwise
2.6
Basis Data Gambar Menurut (Candan & Sapino, 2010, p20) pengertian dari basis data gambar
adalah kumpulan objek data yang diatur sedemikian hingga yang mendukung pencarian dan manipulasi yang efektif. Berdasarkan definisi ini, kumpulan foto digital dapat dianggap sebuah basis data.
2.7
Pengukuran Kemiripan Menurut
(Kondekar, Kolkure, & Kore, 2010) pengukuran kemiripan
(similarity measure) adalah penentuan kemiripan antara fitur-fitur dari gambar query dan fitur-fitur dari gambar target dalam basis data, yang pada dasarnya adalah penentuan jarak antara kumpulan fitur yang mewakili gambar. Gambar yang secara persepsi mirip harus memiliki jarak yang lebih kecil di antara mereka dan gambar yang secara persepsi berbeda harus memiliki jarak yang lebih besar di antara mereka. Pada penelitian pada tesis ini pengukuran kemiripan yang digunakan adalah euclidean distance, dimana Vpi dan Vqi adalah kumpulan fitur dari gambar P dan gambar query Q.
20
2.8
Evaluasi Performa Menurut (Kondekar, Kolkure, & Kore, 2010) terdapat dua ukuran evaluasi
yang digunakan untuk mengevaluasi efektivitas dari sistem mesin pencari gambar. Pengukuran pertama adalah recall yang merupakan ukuran dari kemampuan sebuah sistem untuk menampilkan seluruh gambar yang relevan. Pengukuran kedua adalah precision yang merupakan ukuran dari kemampuan sebuah sistem untuk menampilkan hanya gambar yang relevan. Hasil temu kembali merepresentasikan hasil yang relevan jika hasil temu kembali tersebut termasuk ke dalam kategori gambar yang sama dengan gambar query (Al-nihoud, 2010). Jumlah gambar relevan yang didapatkan Jumlah gambar relevan pada kumpulan gambar Jumlah gambar relevan yang didapatkan Total gambar yang didapatkan
2.9
Penelitian Terkait Penelitian-penelitian sistem TKCBK terhadap gambar-gambar corel, sudah
dilakukan sejak dulu. Beberapa metode sudah dicoba untuk mendapatkan hasil yang terbaik. Penelitian-penelitian terkini terkait sistem TKCBK terhadap gambar-gambar corel adalah sebagai berikut :
21
•
P.B. Thawari dan N.J. Janwe pada tahun 2011 mempublikasikan penelitian yang berjudul ”CBIR Based on Color and Texture”. Pada penelitian mereka, sistem TKCBK menggunakan color & texture histogram descriptor sebagai fitur. Untuk mengekstrak fitur tersebut, gambar (ukuran 384x256) pada ruang warna RGB dikonversi ke ruang warna HSV. Setiap kanal (H, S, dan V) berupa matriks dua dimensi. Setiap matriks dipartisi ke ukuran 32x32, sehingga menghasilkan 96 sel hasil partisi. Pada setiap sel, informasi warna yang dihitung adalah histogram mean, standard deviation, dan median, sedangkan informasi tekstur yang dihitung adalah mean, standard deviation, smoothness, third moment, forth moment, uniformity, dan entropy. Basis data gambar yang digunakan berupa 500 gambar corel. Evaluasi performa berupa pengukuran precision dan recall dari 5 query acak. Hasil penelitian menunjukkan bahwa sistem TKCBK yang mereka usulkan menghasilkan rata-rata precision 38.2% dan recall 39.8% untuk sistem TKCBK yang hanya menggunakan fitur warna, dan rata-rata precision 53% dan recall 38% untuk sistem TKCBK yang hanya menggunakan fitur tekstur.
•
M. Babu Rao, B. Prabhakara Rao, dan A. Govardhan pada tahun 2011 mempublikasikan penelitian yang berjudul ”Content Based Image Retrieval Using Dominant Color, Texture and Shape”. Pada penelitian mereka, sistem TKCBK menggunakan dominant color sebagai fitur warna, GLCM sebagai fitur tekstur, dan gradient vector flow (GVF) sebagai fitur bentuk. Untuk mengekstrak fitur tersebut, gambar diresize ke ukuran 256x384, kemudian ketiga fitur tersebut diekstrak dan kemudian digabung. Basis data gambar yang digunakan berupa 1000 gambar corel. Hasil penelitian menunjukkan
22
bahwa sistem TKCBK yang mereka usulkan menghasilkan rata-rata precision sebesar 0.602. •
Ch. Kavitha, B. Prabhakara Rao, dan A. Govardhan pada tahun 2011 mempublikasikan penelitian yang berjudul ”Image Retrieval Based on Combined Features of Image Sub-Blocks”. Pada penelitian mereka, sistem TKCBK menggunakan local histogram sebagai fitur warna dan GLCM sebagai fitur tekstur. Untuk mengekstrak fitur tersebut, gambar diresize ke ukuran 256x384, kemudian dipartisi menjadi 6 (2x3) sub-blok, masingmasing berukuran 128x128. Dari setiap sub-blok, kemudian kedua fitur tersebut diekstrak dan kemudian digabung. Basis data gambar yang digunakan berupa 1000 gambar corel. Hasil penelitian menunjukkan bahwa sistem TKCBK yang mereka usulkan menghasilkan rata-rata precision sebesar 0.5705.
•
Jehad Q. Al-nihoud pada tahun 2010 mempublikasikan penelitian yang berjudul ”Image Retrieval System with Self Organizing Map and Subtractive Fuzzy Clustering”. Pada penelitiannya, untuk setiap gambar, fitur warna global diekstrak. 4 fitur warna global tersebut adalah mean, standard deviation, energy, dan skew. Setelah itu, berdasarkan fitur tersebut self organizing map (SOM) indexing dilakukan. Setelah itu, fuzzy color histogram diekstrak dari gambar dan lalu dilakukan proses clustering menggunakan subtractive fuzzy clustering. Setelah itu, fitur bentuk dari gambar pada cluster terpilih diekstrak untuk dibandingkan dengan query. Basis data gambar yang digunakan berupa 1000 gambar corel. Evaluasi performa berupa pengukuran precision dari 5 query acak untuk setiap kategori. Hasil penelitian
23
menunjukkan bahwa sistem TKCBK yang diusulkan menghasilkan rata-rata precision sebesar 0.742.
