16
BAB II LANDASAN TEORI
2.1
Retrival Citra Saat ini telah terjadi peningkatan pesat dalam penggunaan gambar digital. Setiap hari
pihak militer maupun sipil menghasilkan gambar digital dalam ukuran giga-byte. Banyak sekali informasi yang dimiliki oleh gambar-gambar digital ini. Namun kesulitan untuk mengakses informasi-informasi ini pun terjadi, sehingga muncul solusi-solusi untuk membuat gambar-gambar digital ini terorganisir agar dapat dilakukan pencarian dan retrival yang efisien. Sejak 1970, bidang ilmu retrival citra sangat aktif melakukan penelitian, dengan dorongan dari dua komunitas penelitian utama, yaitu manajemen basis data dan visi komputer. Kedua komunitas ini melakukan penelitian terhadap retrival citra melalui dua sudut yang berbeda, yaitu berbasis teks dan berbasis visual (Rui, Huang, & Chang, 1999). Retrival citra berbasis teks sudah mulai dilakukan sejak akhir 1970-an. Framework yang sangat populer dari retrival citra ini adalah pertama membubuhi keterangan gambar dengan teks dan kemudian menggunakan sistem manajemen basis data berbasis teks untuk melakukan retrival citra. Banyak kemajuan seperti pemodelan data, pengindeksan multidimensi, dan evaluasi query, yang dilakukan sepanjang arah penelitian. Namun, terdapat dua kesulitan utama, terutama ketika ukuran koleksi gambar semakin besar mencapai puluhan atau ratusan ribu. Pertama adalah jumlah tenaga kerja yang besar yang dibutuhkan untuk melakukan pembubuhan gambar secara manual, yang kedua dan yang lebih penting adalah, hasil dari gambar-gambar yang kaya akan konten dan subyektifitas persepsi manusia. Artinya, dalam konten gambar yang sama manusia yang berbeda dapat mengartikan secara
17
berbeda. Subyektifitas persepsi dan pembubuhan yang kurang tepat dapat mengakibatkan ketidaksesuaian dalam proses retrival citra (Rui, Huang, & Chang, 1999). Pada awal 1990, retrival citra berbasis konten diusulkan. Artinya, gambar tidak lagi dilakukan pembubuhan kata secara manual untuk kepentingan pencarian tetapi akan diindeks oleh konten visualnya sendiri, seperti warna atau tekstur. Sejak itu, banyak teknik dalam arah penelitian tersebut dikembangkan dan banyak sistem retrival citra, dengan tujuan penelitian maupun komersil, dibangun (Rui, Huang, & Chang, 1999).
2.2
Retrival Citra Berbasis Konten Retrival citra berbasis konten, juga dikenal sebagai query dengan menggunakan
konten gambar dan pencarian informasi visual berbasis konten adalah aplikasi dari visi dunia komputer untuk masalah pengambilan gambar, yaitu, masalah dalam pencarian gambar digital di dalam basis data berukuran besar. Berbasis konten berarti bahwa pencarian menggunakan konten dari gambar itu sendiri, daripada mengandalkan masukan metadata dari manusia seperti judul atau kata kunci. Sistem retrival citra berbasis konten adalah software yang mengimplementasikan retrival citra berbasis konten (Suhasini, Krishna, & Krishna, 2009). Menurut (Sai & Patil, 2010), sistem retrival citra berbasis konten biasanya melakukan dua tugas utama. Yang pertama adalah ekstraksi ciri, dimana set dari fitur, yang disebut juga gambar signature atau vektor fitur, dihasilkan untuk secara akurat mewakili isi dari masingmasing gambar dalam database. Tugas kedua adalah kesamaan pengukuran, dimana jarak vektor fitur antara citra query dengan setiap gambar dalam database dihitung sehingga gambar-gambar yang memiliki jarak “terdekat” dapat diambil (Sai & Patil, 2010). Menurut (Kondekar, Kolkure, & Kore, 2010), tahapan retrival citra berbasis konten adalah sebagai berikut:
18
•
Ekstraksi fitur (feature extraction): Ekstraksi fitur-fitur dari gambar yang merupakan representasi dari gambar tersebut, bertujuan untuk membedakan konten antara gambar-gambar.
•
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 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 retrival citra berbasis konten secara umum dapat digambarkan pada gambar di bawah ini:
Gambar 2.1 Diagram Blok dari Retrival Citra Berbasis Konten (Suhasini, Krishna, & Krishna, 2009)
19
2.3
Ekstraksi Fitur Ekstraksi fitur (konten) adalah dasar dari retrival citra berbasis konten. Ekstraksi fitur
dapat diklasifikasikan sebagai fitur-fitur umum dan fitur dengan spesifik domain. Klasifikasi pertama mencakup fitur warna, tekstur, dan bentuk sedangkan klasifikasi kedua termasuk fitur-fitur yang merupakan fitur spesifik aplikasi sebagai contoh, fitur untuk wajah manusia dan sidik jari (Rui, Huang, & Chang, 1999). Fitur-fitur yang digunakan dalam penelitian ini termasuk ke dalam fitur-fitur umum sehingga pembahasan hanya akan mencakup di bagian tersebut saja, fitur-fitur umum tersebut adalah (Rui, Huang, & Chang, 1999): •
Warna merupakan salah satu fitur visual yang paling banyak digunakan dalam retrival citra, dan histogram warna merupakan fitur paling umum digunakan di dalam representasi fitur warna. Secara statistik, histogram melakukan ekstraksi terhadap probabilitas join dari intensitas tiga saluran warna (RGB). Salah satu fitur dalam penelitian ini menggunakan histogram dan penggunaannya akan dijelaskan lebih lanjut.
•
Tekstur mengacu kepada pola visual yang memiliki sifat homogenitas yang bukan merupakan hasil dari keberadaan satu intensitas warna saja. Tekstur merupakan sifat bawaan dari semua permukaan terlihat, seperti awan, pohon, batu bata, dan kain. Tekstur memegang informasi penting mengenai susunan struktur permukaan dan hubungannya dengan lingkungan sekelilingnya. Karena tekstur memegang peranan penting dan banyak kegunaan dalam pengenalan pola dan visi komputer, banyak penelitian dilakukan untuk pengembangan fitur tekstur.
•
Bentuk digunakan pada retrival citra, tergantung kepada aplikasinya. Beberapa aplikasi membutuhkan representasi bentuk untuk menjadi invarian untuk translasi, rotasi, skala. Secara umum, representasi bentuk bisa dibedakan menjadi dua kategori, berbasis batas dan berbasis daerah. Kategori pertama menggunakan batas luar dari
20
bentuk sementara kategori kedua menggunakan wilayah seluruh bentuk. Representasi bentuk juga dapat dibedakan menjadi representasi gambar 2 dimensi (2D) dan 3 dimensi (3D). Salah satu fitur dalam penelitian ini menggunakan fitur bentuk yaitu gradient vector flow, dimana representasi 2D diusulkan oleh (Xu & Prince, 1998) dan representasi 3D dikembangkan oleh Eric Smistad (http://www.thebigblob.com/3dgradient-vector-flow-matlab-implementation/).
2.4
Histogram Retrival citra berbasis konten memainkan peranan penting dalam area aplikasi
khususnya sistem database multimedia dalam beberapa tahun terakhir. Pekerjaan terfokus dalam penggunaan fitur-fitur tingkat rendah seperti warna, tekstur, bentuk dan tata ruang untuk representasi gambar. Di antara semua fitur visual, warna mungkin adalah salah satu yang paling membedakan di banyak aplikasi (Suhasini, Krishna, & Krishna, 2009). Isi visual dari gambar seperti warna, bentuk, tekstur dan tata ruang banyak digunakan dalam retrival citra berbasis konten. Ada banyak deskripsi dari fitur yang secara umum digunakan. Sebagai contoh, fitur warna dapat direpresentasikan dengan histogram. Demikian pula, fitur tekstur dapat diwakili oleh fitur Tamura, Gabor dan transformasi wavelet. Selain itu, fitur bentuk dapat diwakili oleh fitur berbasis Fourier. Akhirnya, fitur tata ruang dapat direpresentasikan dengan string 2D (Omar, Ismail, & Ghanem, 2009). Warna adalah salah satu fitur visual yang paling dapat diandalkan yang juga lebih mudah untuk diterapkan dalam sistem pengambilan gambar. Warna tidak tergantung pada ukuran dan orientasi gambar, karena, warna kuat untuk komplikasi latar belakang. Histogram warna adalah teknik paling umum untuk mengekstraksi fitur warna dari gambar berwarna. Pada kasus retrival citra histogram warna banyak digunakan untuk sistem retrival citra
21
berbasis konten. Hal ini dikarenakan metode ini adalah metode paling umum untuk memprediksi karakteristik dari gambar (Sai & Patil, 2010).
Gambar 2.2 Ruang Warna RGB (Candan & Sapino, 2010, p35)
Gambar 2.3 Ruang Warna HSV (Candan & Sapino, 2010, p39)
22
Pendekatan ini lebih sering diadopsi untuk sistem retrival citra berbasis konten yang didasarkan pada histogram warna konvensional, yang berisi jumlah kejadian dari setiap warna yang diperoleh dengan cara menghitung semua piksel gambar yang memiliki warna tersebut (Suhasini, Krishna, & Krishna, 2009). Karena setiap piksel dalam gambar dapat dideskripsikan oleh tiga komponen dalam ruang warna tertentu (misalnya, merah, hijau, dan biru dalam ruang RGB atau warna, saturasi, dan nilai dalam ruang HSV), sebuah histogram, yaitu, distribusi jumlah piksel untuk setiap bin terkuantisasi, dapat didefinisikan untuk setiap komponen. Jelas, semakin banyak bin dari histogram warna berarti semakin banyak kekuatan perbedaan yang dimilikinya. Namun, histogram dengan sejumlah besar bin tidak hanya akan meningkatkan biaya komputasi, tetapi juga akan membangun indeks yang efisien untuk basis data citra (Suhasini, Krishna, & Krishna, 2009). Kuantisasi dalam hal warna histogram mengacu kepada proses mengurangi jumlah bin dengan mengambil warna-warna yang sangat mirip satu sama lain dan menempatkan mereka di bin yang sama. Secara default jumlah maksimum bin yang dapat diperoleh dengan menggunakan fungsi histogram di MatLab adalah 256 (Suhasini, Krishna, & Krishna, 2009).
2.5
Gradient Vector Flow (GVF) Kass mengusulkan Model Kontur Aktif, yang disebut juga dengan model ular,
berdasarkan kepada pemikiran dinamis di tahun 1987. Presisi kontur dapat dideteksi di dalam model tersebut. Model Kontur Aktif meliputi model aktif geometri dan model aktif parametri (Zhang, 2008). Walaupun Model Kontur Aktif bisa mendapatkan batas obyek yang presisi, masih ada beberapa masalah yang dimiliki (Zhang, 2008): 1. Kontur awal harus dekat dengan tepi target.
23
2. Kontur sangat sulit untuk berevolusi menjadi batas cekung. 3. Posisi awal kontur pusat harus dekat dengan posisi tengah dari target. Dua masalah pertama telah dipecahkan oleh gradient vector flow (GVF), yang diusulkan oleh (Xu & Prince, 1998). Tetapi masalah ketiga masih dipelajari (Zhang, 2008). Secara matematis, gradient vector flow (GVF) didefinisikan sebagai solusi keseimbangan dari persamaan diferensial parsial vektor yang berdifusi dari vektor gradien tingkat abu-abu atau tepi peta biner yang dihitung dari citra yang diberikan (Zou, 2008). Didefinisikan ,
,
,
gradient ,
vector
flow
field
menjadi
vector
field
yang meminimalkan energi fungsi (Xu & Prince, 1998)
|
| |
|
(1)
Dengan menggunakan kalkulus variasi, dapat ditunjukkan bahwa bidang GVF dapat ditemukan dengan memecahkan persamaan Euler berikut
dimana
adalah operator Laplace.
0
(2a)
0
(2b)
24
(a)
(b) Gambar 2.4 (a1) Gambar obyek U berukuran 64 x 64-pixel yang memiliki noise; (a2) edge map |
| dengan
1.5; (b1) GVF external force field; (b2) konvergensi dari ular GVF
Dalam thesis ini digunakan perhitungan Gradient Vector Flow (GVF) untuk gambar 3D oleh Eric Smistad (http://www.thebigblob.com/3d-gradient-vector-flow-matlab-implementation/) yang implementasinya merupakan ekstensi sederhana dari implementasi asli 2D dari (Xu & Prince, 1998).
25
2.6
Pengukuran Kemiripan Pengambilan gambar pada dasarnya adalah penentuan kesamaan antara fitur citra
query dan fitur gambar sasaran dalam basis data, yang pada dasarnya penentuan jarak antara vektor fitur yang mewakili gambar. Ukuran jarak yang diinginkan harus mencerminkan persepsi manusia. Artinya, antara persepsi gambar yang sama harus memiliki jarak yang lebih kecil dan yang berbeda harus memiliki jarak yang lebih besar. Beberapa perhitungan jarak telah digunakan dalam retrival citra, termasuk blok kota (city block), Eucledian, kosinus (cosine), persimpangan jarak (histogram intersection), statistik, kuadratik, dan Mahalanobis (Zhang & Lu, 2003). Jarak kosinus menghitung perbedaan arah, terlepas dari panjang vektor. Jarak diberikan oleh sudut antara kedua vektor (Zhang & Lu, 2003). Dengan aturan perkalian titik,
Pada penelitian pada thesis ini digunakan penghitungan jarak konsinus (cosine distance).
2.7
Evaluasi Performa Terdapat dua ukuran evaluasi yang digunakan untuk mengevaluasi efektifitas dari
sistem retrival citra berbasis konten. 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 (Kondekar, Kolkure, & Kore, 2010). Hasil temu kembali merepresentasikan hasil yang relevan jika hasil tersebut termasuk ke dalam kategori gambar yang sama dengan gambar query (Al-nihoud, 2010).
26
