BAB III METODOLOGI PENELITIAN
3.1
Kerangka Pikir Pada saat ini, perkembangan teknologi memungkinkan kita untuk
menyimpan gambar dalam format digital. Kumpulan gambar yang banyak membutuhkan sebuah sistem yang mampu mengelola gambar-gambar tersebut sehingga ketika ada gambar yang ingin ditemukan maka gambar tersebut dapat ditemukan dengan cepat dan akurat. TKCBK adalah teknik temu kembali untuk mencari gambar pada basis data gambar skala besar gambar berbasis konten visual seperti warna, tekstur, dan bentuk. Fase awal dari penelitian dan pengembangan TKCBK sudah dimulai sejak tahun 1994 – 2000. Persoalan umum yang muncul dalam penelitian dan pengembangan TKCBK sejak fase awal hingga saat ini adalah fitur-fitur apa saja yang harus diekstrak untuk mendapatkan hasil temu kembali yang bermakna. Setelah mengetahui fitur-fitur apa yang harus diekstrak, persoalan berikutnya adalah bagaimana fitur-fitur yang diekstrak sebelumnya diindeks dan kemudian dicocokkan satu sama lainnya untuk mendapatkan hasil temu kembali (Datta, Joshi, Li, & Wang, 2008). Salah satu fitur warna yang digunakan pada sistem TKCBK adalah forward diagonal mean. Forward diagonal mean menghasilkan sistem TKCBK yang cepat namun masih belum akurat pada gambar-gambar corel (rata-rata precision sekitar 60%) (Kekre, Thepade, & Maloo, 2010). Tujuan dari penelitian ini adalah untuk 24
25
meningkatkan akurasi dari sistem TKCBK yang menggunakan metode forward diagonal mean. Untuk mencapai tujuan tersebut, maka menggunakan fitur tunggal untuk temu kembali gambar tidak dapat menjadi solusi yang baik untuk akurasi dan efisiensi (Kavitha, Rao, & Govardhan, 2011), sehingga perlu mencari fiturfitur yang mampu meningkatkan akurasi. Fitur GLCM merupakan salah satu fitur tekstur. Fitur GLCM tersebut akan ditambahkan pada sistem TKCBK untuk meningkatkan akurasi. Fitur GLCM mampu meningkatkan akurasi sebesar 14.1% dari sistem TKCBK yang hanya menggunakan fitur berbasis warna yaitu fitur dominant color (Rao, Rao, & Govardhan, 2011). Penelitian ini juga menggunakan R*-Tree sebagai struktur data untuk mengatasi peningkatan waktu proses pencarian akibat dari penambahan fitur GLCM. R*-Tree merupakan struktur data dengan performa query paling efisien (varian R*-Tree yaitu close-reinsert (CR) dan far-reinsert (FR) menunjukkan variasi performa yang sangat kecil) (Ciferri, Salgado, Times, Nascimento, & Magalhaes, 2003).
Tabel 3.1 Peringkat Performa Struktur Data (Ciferri, Salgado, Times, Nascimento, & Magalhaes, 2003)
1 2 3 4 5 6 7 8
SAM R * -tree CR R * -tree FR R * -tree WR R-tree R-tree Greene R+ -tree Hilbert R-tree SR-tree
Average Efficiency 6.23542 6.23333 5.99583 4.51667 4.42292 4.27805 3.19688 2.93438
26
3.2
Metodologi
Gambar 3.1 Metode yang Diusulkan Metodologi dari sistem TKCBK pada penelitian ini adalah gambar query dan gambar pada basis data gambar diresize ke ukuran 384x256 pixel. Fitur warna diekstrak menggunakan forward diagonal mean. Fitur tekstur diekstrak dengan cara mengkonversi gambar menjadi gambar gray-scale lalu dibentuk GLCM (d = 1, Ө = 0o, 45o, 90o, 135o) (Rao, Rao, & Govardhan, 2011) dan pada akhirnya didapatkan fitur energy, contrast, entropy, dan inverse difference dari 4 GLCM sehingga didapatkan 16 fitur. Pada setiap gambar pada basis data gambar, hasil gabungan fitur dimasukkan ke dalam struktur data R*-Tree. Algoritma yang digunakan untuk memasukkan hasil gabungan fitur ke dalam R*-Tree adalah sebagai berikut :
27
Struktur R*-Tree terdiri dari node-node. Setiap node dari R*-Tree berhubungan dengan MBR. Leaf dari R*-Tree menunjuk ke data. Setiap node dapat menyimpan maksimal M dan minimal m (kecuali root) dimana 2 ≤ m ≤ M/2. Pada saat memasukkan data ke tree, penelusuran dimulai dari root dan kemudian mencari leaf yang sesuai (menggunakan chooseSubTree) untuk memasukkan data. Setelah leaf didapatkan, jika leaf tersebut dapat menampung data (jumlah data yang ditampung leaf < M), maka data tersebut dimasukkan ke dalam leaf. Jika leaf tersebut tidak dapat menampung data, maka dilakukan proses untuk menangani luapan (overflow) yang terjadi pada leaf, hal tersebut bisa berupa split atau reinsert.
28
Proses chooseSubTree berfungsi untuk mendapatkan leaf pada tree yang paling sesuai untuk memasukkan data. Penelusuran dimulai dari root hingga mencapai leaf. Saat akan memilih jalur mana yang akan dilalui untuk mencapai leaf, maka jika node dari jalur yang akan dipilih merupakan leaf, maka kriteria dari node yang dipilih berdasarkan perluasan tumpang tindih (overlap) paling kecil, jika sama maka dipilih berdasarkan perluasan area paling kecil, jika sama maka dipilih berdasarkan area paling kecil. Selain itu, maka node yang dipilih berdasarkan perluasan area paling kecil, jika sama maka dipilih berdasarkan area paling kecil.
Proses overflowTreatment dilakukan untuk menangani luapan (overflow) yang terjadi akibat leaf tidak dapat menampung data yang baru dimasukkan. Jika leaf bukan root dan proses overflowTreatment merupakan yang pertama kali dilakukan selama proses memasukkan data, maka lakukan proses reinsert untuk memilih beberapa data pada leaf untuk dimasukkan ulang. Selain itu, lakukan proses split pada leaf sehingga terbagi menjadi 2 node.
Pada proses reinsert kumpulan data dari leaf dan data yang akan dimasukkan dikumpulkan ke dalam satu kelompok. Setelah itu, berdasarkan MBR
29
dari kelompok tersebut diukur titik tengah dari MBR tersebut. Setelah itu, jarak antara data-data pada kumpulan ke titik tengah diukur. Setelah itu, 30% dari kumpulan data yang memiliki jarak terjauh dimasukkan ulang ke dalam tree.
Untuk mengelola hasil split dari leaf hingga ke root, maka processSplit dilakukan. Ketika split dilakukan, leaf akan terbagi menjadi 2 node, jika parent dari leaf tersebut tidak dapat menampung kedua node tersebut maka split dilakukan terhadap parent dari leaf tersebut. Proses tersebut dilakukan hingga mencapai root. Khusus pada root, ketika terjadi split pada root, maka akan dibuat root baru dan hasil split tersebut menjadi menjadi child node dari root baru.
Ketika split dilakukan, maka proses chooseSplitAxis dilakukan untuk mendapatkan sumbu yang menghasilkan split dengan margin paling kecil. Setelah itu,
berdasarkan
sumbu
tadi
proses
chooseSplitIndex
dilakukan
untuk
mendapatkan indeks dan distribusi terbaik berdasarkan tumpang tindih (overlap) paling kecil, jika sama berdasarkan dead space paling kecil. Distribusi merupakan
30
kumpulan dari child node dan node yang menyebabkan luapan (overflow) yang telah terurut berdasarkan nilai bawah atau nilai atas. Indeks merupakan batas pembagi pada distribusi. Setelah didapatkan indeks dan distribusinya, maka distribusi tadi didistribusikan pada node1 dan node2. Node1 menampung node pertama hingga node ke-indeks dari distribusi, sedangkan node2 menampung node ke-indeks+1 hingga node terakhir dari distribusi.
Pada proses chooseSplitAxis, untuk setiap sumbu / dimensi, kumpulan child node dan node yang menyebabkan luapan (overflow) diurutkan berdasarkan nilai bawah dan nilai atas. Setelah itu, dilakukan penghitungan margin dari setiap kombinasi pembagian node (kombinasi sebanyak M-2m+2, dimana k = 1 hingga M-2m+2) terhadap kelompok terurut berdasarkan nilai bawah dan nilai atas tadi. Kelompok pertama berisi (m-1)+k data pertama dari setiap kelompok pengurutan
31
(nilai bawah / nilai atas) dan kelompok kedua berisi sisanya. Sumbu yang dipilih adalah sumbu yang nilai total marginnya paling kecil.
Pada proses chooseSplitIndex, kumpulan dari child node dan node yang menyebabkan luapan (overflow) diurutkan berdasarkan nilai bawah dan nilai atas dari sumbu terpilih. Setelah itu, dilakukan penghitungan tumpang tindih (overlap) dan dead space dari setiap kombinasi pembagian node (kombinasi sebanyak M2m+2, dimana k = 1 hingga M-2m+2) terhadap kelompok terurut berdasarkan nilai bawah dan nilai atas tadi. Kelompok pertama berisi (m-1)+k data pertama dari setiap kelompok pengurutan (nilai bawah / nilai atas) dan kelompok kedua berisi sisanya. Nilai indeks berupa (m-1)+k yang paling baik. Distribusi berupa kelompok terurut (berdasarkan nilai bawah / nilai atas) yang paling baik. Indeks
32
dan distribusi dipilih berdasarkan tumpang tindih (overlap) paling kecil, jika sama, maka berdasarkan dead space paling kecil. Pada saat melakukan pencarian, gabungan fitur hasil ekstraksi dari gambar query digunakan untuk mencari gambar yang paling mirip dengan gambar query pada R*-Tree. Proses pencarian pada R*-Tree menggunakan algoritma branch & bound. Algoritmanya adalah sebagai berikut :
Pada proses pencarian data, pencarian dimulai dari root hingga mencapai leaf. Pada saat memilih jalur yang akan ditelusuri, semua child node dikelompokkan ke dalam branchList, kemudian MINDIST dan MINMAXDIST diukur dari query ke semua child node. Setelah itu, branchList diurutkan berdasarkan MINDISTnya dari jarak terkecil hingga ke jarak terbesar. Setelah itu, proses
prune
akan
dilakukan
untuk
mengeliminasi
jalur
yang
tidak
memungkinkan untuk mendapatkan data yang diinginkan. Ketika mencapai leaf,
33
data yang dipilih adalah sejumlah data yang memiliki jarak paling dekat dengan query. Setelah itu, hasilnya ditampilkan berupa 10 gambar yang paling mirip. Penelitian ini menggunakan MATLAB R2008a dengan komputer Intel Core 2 Duo Processor T5750 (2 GHz) dan 1 GB RAM.
3.3
Basis Data Gambar Pada penelitian ini basis data gambar yang digunakan adalah Wang
Database. Wang Database adalah basis data gambar yang berisi 1000 gambar corel yang terbagi ke dalam 10 kategori (setiap kategori terdiri atas 100 gambar corel). Wang Database biasa digunakan dalam penelitian yang menggunakan basis data gambar yang berisi gambar corel. Wang Database dapat diunduh pada http://wang.ist.psu.edu/docs/related.shtml. Berikut adalah contoh gambar pada Wang Database untuk setiap kategori.
Tabel 3.2 Contoh Basis Data Gambar Kategori Afrika
Pantai
Bangunan
Bus
Gambar
34
Dinosaurus
Gajah
Bunga
Kuda
Gunung
Makanan
3.4
Evaluasi Performa Untuk evaluasi performa pada penelitian ini, pengukuran akurasi dari sistem
TKCBK dilakukan dengan cara mengukur rata-rata precision dan recall dari 5 gambar query acak untuk setiap kategori gambar. Selain mengukur precision dan recall, penelitian ini juga mengukur waktu proses pencarian dari sistem TKCBK. Pengukuran precision dan recall dilakukan terhadap sistem TKCBK yang menggunakan color histogram, forward diagonal mean, dan forward diagonal mean digabung dengan GLCM. Pengukuran waktu proses pencarian dilakukan terhadap sistem TKCBK yang menggunakan forward diagonal mean digabung dengan GLCM dan forward diagonal mean digabung dengan GLCM dengan R*-Tree. Precision dan recall dari color histogram diukur karena color histogram merupakan fitur warna yang paling umum digunakan (Thawari & Janwe, 2011),
35
(Rao, Rao, & Govardhan, 2011), (Pun & Wong, 2008), & (Kavitha, Rao, & Govardhan, 2011), sehingga menjadi pembanding dari forward diagonal mean.
