IMPLEMENTASI SISTEM TEMU KEMBALI CITRA BERBASIS ISI DENGAN METODE JARAK INFORMASI YANG DINORMALISASI

MAKALAH SEMINAR TUGAS AKHIR PERIODE JUNI-JULI 2010

IMPLEMENTASI SISTEM TEMU KEMBALI CITRA BERBASIS ISI DENGAN METODE JARAK INFORMASI YANG DINORMALISASI Ressty Yuniarti1, Handayani Tjandrasa2, Anny Yuniarti3 Teknik Informatika, Fakultas Teknologi Informasi, ITS email : [email protected], [email protected], [email protected] Pendekatan ini juga memiliki masalah jika dipergunakan karena hanya mengandalkan kata kunci berupa tekstual. Untuk menanggulangi masalah tersebut, CBIR [5] dimunculkan pada tahun 90-an. Yaitu sebuah ide untuk mencari isi visual citra secara langsung. Temu kembali ditampilkan oleh contoh citra dimana sebuah query citra diberikan sebagai masukan oleh pengguna dan sebuah metric atau alat ukur yang sesuai digunakan untuk menemukan kecocokan terbaik pada ruang fitur yang berhubungan. Pada pendekatan tradisional CBIR, masingmasing citra direpresentasikan oleh kumpulan fitur global yang dihitung oleh proses pengolahan yang seragam pada citra dan menjelaskan seluruh isi visualnya (mis: warna , tekstur, bentuk). Pada persoalan CBIR, vektor fitur dilihat sebagai titik jarak metric atau alat ukur digunakan untuk memilih titik terdekat dengan query dan mengembalikan citra yang sesuai. Untuk melewati langkah seleksi fitur (dan pengukuran metric pada ruang fitur yang sesuai) dengan menggunakan pendekatan jarak informasi yang dinormalisasi (NID) [7]. Pendekatan NID ini berbasis pada kompleksitas Kolmogorov [8,9]. Oleh karena itu dalam Tugas Akhir ini diusulkan sebuah pendekatan jarak informasi yang dinormalisasi (Normalized Information Distance) dengan menggunakan kompresi citra GZIP untuk mendapatkan kompleksitas kompresi Kolmogorov-nya. Keuntungan utama dari pendekatan ini adalah kesederhanaan dimana pemilihan, ekstraksi, dan pembobotan dari fitur-fitur tidak dibutuhkan. Pendekatan kompleksitas Kolmogorov dari sebuah citra dibuat dengan menggunakan metode kompresi yang berbeda-beda (dalam Tugas Akhir ini menggunakan GZIP). Dengan menggunakan pendekatan tersebut, NID antar citra dapat dihitung dan digunakan sebagai metric untuk CBIR.

ABSTRAKSI Ide pokok dari content-based image retrieval (CBIR) atau sistem temu kembali citra berbasis isi adalah mencari konten visual pada citra secara langsung. Umumnya, fitur-fitur seperti warna, bentuk, tekstur diekstrak dari setiap citra dan diatur dalam sebuah vektor fitur. Temu kembali (retrieval) dilakukan dengan sebuah query citra sebagai masukan oleh pengguna dan alat ukur yang digunakan untuk menemukan hasil pencocokan terbaik pada ruang fitur. Tugas Akhir ini mengimplementasikan pengukuran ketidaksamaan citra yang mengikuti dasar teori dari normalized information distance (NID). Alat ukur dari pencarian citra ini menggunakan metode NID dengan pendekatan kompleksitas Kolmogorov. Pendekatan tersebut dibuat dengan metode teknik kompresi GZIP. Perhitungan jarak NID pada Tugas Akhir ini menggunakan dua metode yaitu NID sederhana dan NID dengan interleaving. Uji coba yang dilakukan pada Tugas Akhir ini menggunakan data citra dari University of Washington dan SIVAL benchmark. Hasil dari uji coba yang dilakukan mengatakan bahwa pendekatan perhitungan NID dapat dijanjikan dan dibuktikan kebenarannya untuk sistem CBIR. Keuntungan utama dari metode ini adalah tidak terdapat ekstraksi fitur dalam CBIR sehingga dapat digunakan untuk semua jenis citra tanpa membedakan ekstraksi fitur-fiturnya. Kata kunci : content based image retrieval, normalized information distance (NID), Kolmogorov Complexcity, compression, normalized compression distance (NCD).

1

PENDAHULUAN

Dewasa ini, pengembangan teknologi informasi sangat cepat dan menjamurnya web telah mempercepat pertumbuhan media digital khususnya tentang koleksi citra. Koleksi citra yang sedang menjamur di dunia maya akan menjadi objek permasalahan jika tidak bisa mengolahnya dengan baik. Dalam mengolah koleksi citra yang besar di internet, perlu adanya proses pencarian data citra yang ingin diolah dari kumpulan koleksi citra tersebut. Pada awalnya, teknik yang digunakan untuk pencarian citra menggunakan pendekatan tradisional. Pendekatan tersebut menggunakan pencocokan kata kunci representasi tekstual untuk temu kembali citra.

2

KOMPRESI GZIP

GZIP adalah sebuah aplikasi perangkat lunak yang digunakan untuk mengkompresi file. GZIP berdasar dari algoritma DEFLATE yang mengkombinasikan dari LZ77 dan Huffman Coding. DEFLATE dimaksudkan sebagai pengganti LZW dan algoritma kompresi data yang lain, pada saat itu, membatasi kegunaan kompresi dan archivers populer lainnya. Dengan kata lain kompresi GZIP ini merupakan kompresi Deflate [10]. Deflate adalah algoritma kompresi data lossless yang menggunakan kombinasi dari algoritma LZ77 dan Huffman Coding yang dikembangkan oleh Phil Katz. Kompresi dengan algoritma LZ77 dilakukan terlebih 1

MAKALAH SEMINAR TUGAS AKHIR PERIODE JUNI-JULI 2010 dahulu kemudian dikompres lagi dengan Huffman Coding. LZ77 merupakan algoritma kompresi data lossless yang dikembangkan oleh dua orang ilmuwan komputer yang bernama Abraham Lempel dan Jacob Ziv pada tahun 1977 dan kemudian berkembang menjadi beberapa variasi seperti LZW, LZSS, dan LZMA. Inti dari algoritma LZ77 adalah string matching dimana sebuah string panjang dibagi menjadi 2 blok yaitu sliding window dan read ahead atau look ahead. Hal ini dapat dilihat pada gambar 1 [10].

3 NORMALIZED DISTANCE (NID)

INFORMATION

Jarak informasi minimum antara x dan y adalah panjang program terpendek dari komputer yang mentransformasikan x ke y dan y ke x. Pengukuran ini akan ditunjukkan sebagai syarat penambahan logaritmik, sama dengan maksimum dari kompleksitas Kolmogorov bersyarat. Kompleksitas bersyarat K(y|x) tidak cocok untuk jarak informasi yang optimal karena asimetris : K(ε|x) kecil untuk semua x , secara tak sengaja string acak x yang panjang tidak mendekati string kosong. Asimetris dari kompleksitas Kolmogorov bersyarat K(x|y) dapat diperbaiki dengan menggambarkan algoritma jarak informasi antara x dan y menjadi jumlah kompleksitas relatif, K(y|x)+K(x|y). Hasil metric akan menaksir lebih tinggi informasi yang dibutuhkan untuk menerjemahkan antara x dan y pada saat disana terdapat redundansi antara informasi yang dibutuhkan untuk mendapatkan dari x ke y dan informasi yang dibutuhkan untuk mendapatkan dari y ke x [1]. Jarak informasi E(x,y) didefinisikan sebagai panjang program terkecil yang menghasilkan x dari y dan y dari x. Perumusan E(x, y) adalah seperti berikut:

Gambar 1 Contoh Sliding Window dan Look Ahead

Pencarian kata (string matching) dilakukan dengan mencocokkan string pada read ahead dengan string pada sliding window. Jika sama, maka dibentuk kode yang terdiri dari pasangan offset dan length dan akan disalin ke file output. Setelah itu index awal sliding window akan bergeser ke kanan sebanyak length. Offset adalah indeks akhir pada sliding window dikurangi indeks awal dari rangkaian karakter yang ditemukan dalam sliding window, sedangkan length adalah panjang karakter yang ditemukan sama dikurangi 1. Jika isi read ahead tidak ditemukan kesamaan pada sliding window maka panjang dari isi read ahead dikurangi 1. Jika masih tidak ditemukan kesamaan hingga panjang isi dari read ahead = 2 maka isi read ahead akan disalin ke file output dan indeks awal sliding window akan bertambah 2. Dalam ilmu komputer dan teori informasi, kode Huffman merupakan algoritma pengkodean yang optimal yang digunakan dalam pemampatan data. Kode Huffman menggunakan sebuah tabel variasi panjang kode untuk melakukan encoding sebuah simbol (misalnya karakter dalam file) dimana tabel panjang kode sudah dibangun sedemikian berdasarkan peluang kemunculan tiap simbol dalam suatu file [11]. Algoritma dari Huffman coding adalah : 1. pengurutan keluaran sumber dimulai dari probabilitas paling tinggi, 2. menggabungkan 2 keluaran yang sama dekat ke dalam satu keluaran yang probabilitasnya merupakan jumlah dari probabilitas sebelumnya, 3. apabila setelah dibagi masih terdapat 2 keluaran, maka lanjut ke langkah berikutnya, namun apabila masih terdapat lebih dari 2, kembali ke langkah 1, 4. memberikan nilai 0 dan 1 untuk kedua keluaran, 5. apabila sebuah keluaran merupakan hasil dari penggabungan 2 keluaran dari langkah sebelumnya maka berikan tanda 0 dan 1 untuk codeword-nya , ulangi sapai keluaran merupakan satu keluaran yang berdiri sendiri.

Ex, y = max{Ky|x, Kx|y}

(1)

Persamaan 1 harus dinormalisasi untuk dapat menghasilkan pengukuran jarak yang tepat. Sehingga perlu adanya fungsi jarak informasi ternormalisasi atau NID seperti berikut: dx, y =

{|∗,|∗} {,}

(2)

Fungsi d(x,y) pada persamaan 2 di atas adalah jarak informasi yang dinormalisasi (hal itu adalah sebuah jarak metric yang nilainya adalah [0,1], dan mencapai tujuan dari kondisi normalisasi).

4

NID UNTUK CBIR

Data mentah dari citra berisi sebuah string yang mengandung byte streams yang mendeskripsikan informasi warna. Jadi, berdasarkan Kolmogorov mengenai definisi kompleksitas, semakin sedikit regularitas yang ditemukan di citra, maka semakin kompleks citra itu. Sehingga, citra dengan variasi warna sedikit dan/atau satu warna dengan luas yang besar maka jauh lebih kecil kompleksitasnya daripada banyak variasi warna dan/atau tidak ada daerah yang homogen. Gambar 2 [1] menunjukkan contoh citra yang mengandung area/daerah homogen dan contoh citra yang lebih kompleks.

2

MAKALAH SEMINAR TUGAS AKHIR PERIODE JUNI-JULI 2010 d x, y =

Asumsikan x dan y adalah dua citra raw (yaitu string yang berisi kumpulan byte yang menggambarkan informasi warna). Supaya jarak antara x dan y dapat dihitung dengan Persamaan 7, estimasi nilai K(x), K(y), K(x|y), dan K(y|x) harus dilakukan. Dari Persamaan 2, K(x|y) = K(x, y) – K(y). Dan K(x, y) = K(xy). Kompleksitas Kolmogorov dapat di-aproksimasi dengan menggunakan teknik kompresi. Setiap grup piksel bertetangga dengan warna sama akan dideskripsikan menggunakan satu deskripsi untuk seluruh region. Selanjutnya, dengan kompresi lossy, grup piksel yang memiliki warna serupa dapat diganti dengan warna ratarata (average color). Yang berbeda dari beberapa algoritma kompresi adalah bagaimana penentuan dan pendeskripsian region yang berisi piksel dengan warna serupa. Misalnya, beberapa metode menggunakan wavelet untuk merepresentasikan citra. Oleh karena algoritma kompresi menggunakan konsep redundansi pada sebuah citra untuk memendekkan representasi, maka algoritma kompresi sejalan dengan ide kompleksitas Kolmogorov. Sehingga jika x adalah citra yang lebih kompleks dari y, ukuran x yang sudah dikompresi umumnya lebih besar daripada y. Maka K(y) lebih kecil daripada K(x). Oleh karenanya ukuran x yang sudah dikompresi digunakan untuk aproksimasi nilai K(x), begitu pula untuk K(y). Nilai kompleksitas Kolmogorov kondisional, K(xy) dan K(yx), juga di-aproksimasi menggunakan kompresi. Gabungan x dan y akan dikodekan algoritma kompresi sebagai berikut. Informasi yang terdapat baik pada x maupun y dicari untuk mengurangi redundansi di keseluruhan gabungan x dan y. Jika hasilnya jauh lebih kecil dari jumlah kompleksitas secara individu, maka banyak informasi pada x yang dapat digunakan untuk mengkodekan y. Sehingga x dapat dideskripsikan dengan mengacu pada y dan program yang lebih pendek akan dapat menggambarkan x [1]. Sehingga jarak antara dua citra raw x dan y didefinisikan sebagai berikut: {||||,||||} {||,||}

{||,||}

(4)

dimana pada persamaan 4 sama seperti sebelumnya bahwa c(xy) sama dengan K(x,y), c(x) dan c(y) merupakan ukuran dari citra x dan y setelah dikompresi. Pada umumnya, algoritma kompresi menggunakan kesamaan antara titik-titik bertetangga. Jadi, jika dua citra mengandung sebuah objek tapi pada lokasi spasial yang berbeda, metode penggabungan sederhana tidak digunakan. Jadi, jika objek yang dicari terletak pada lokasi spasial yang sama pada kedua citra maka metode byte interleaving akan menghasilkan performa yang lebih baik. Sehingga, untuk beberapa algoritma kompresi, akan lebih menguntungkan menggunakan metode interleaving dari daerah pada dua citra dimana objek yang penting akan terlihat bersamaan. Kami menyediakan metode baru. Pertama, setiap citra dipartisi menjadi n blok dengan ukuran yang sama (lihat gambar 3). Dengan catatan bahwa segmentasi tetap menghindari kebutuhan ekstraksi fitur, yang akan mengalahkan seluruh tujuan pendekatan NID untuk sistem temu kembali citra. Selanjutnya, n interleavings dari blok yang dihasilkan diproses dimana setiap pasangan blok dari dua citra muncul bersama sesekali (gambar 4). Perlu diketahui bahwa bila pengaturan n = 1 maka akan menghasilkan sebuah penggabungan berurutan sederhana dan, lebih besar nilai n, maka semakin besar kemungkinan objek yang penting akan muncul di sebelah objek yang lain. (lihat Gambar 5). Idealnya, semua kemungkinan kombinasi dari blok citra (n x n) dan sehingga semua kemungkinan interleaving yang berurutan akan digunakan dari n. Namun, setiap pasang citra, akan memerlukan n2 kompresi (setiap n2 interleaving dikompresi). Akhirnya, jarak antara dua citra x dan y ditetapkan lagi sebagai berikut

Gambar 2 kompleksitas Kolmogorov dari sebuah citra adalah proporsi regularitas yang ditemukan pada citra. (a) merupakan citra sederhana dari sebuah logo yang mengandung area dengan satu warna homogen, (b) citra fotografi yang lebih kompleks

d x, y =

|| {||,||}

d ′x, y =

,…, {{|!|||,|!|||}} {||,||}

(5)

dimana c(i) dan |c(i)| sama seperti sebelumnya dan xyj, yxj merupakan gabungan xy, yx masing-masing pada iterasi ke-j. Selain dari persamaan 5, dapat juga memakai persamaan berikut d ′x, y =

,…, {|!!| |!|,|!|} {|!|,|!|}

(6)

dimana c(xjyj) pada persamaan 6 merupakan ukuran citra gabungan bagian ke-j dari citra x dan y terkompresi, c(xi) dan c(yi) merupakan ukuran citra bagian ke-j dari citra x dan y terkompresi.

(3)

dimana c(i) merupakan versi kompresi dari masukan i dan |c(i)| adalah ukurannya. Catatan bahwa |c(x)|, |c(xy)| merupakan pendekatan untuk K(x) dan K(x,y). Selain dari persamaan 3 di atas, dapat juga memakai persamaan berikut

3


5

METODOLOGI

Metodologi dari sistem ini dibagi menjadi dua algoritma yaitu metode NID dan metode NID interleaving.

Gambar 3 Pada penggabungan (byte-interleaving) dari dua citra, objek penting (dalam hal ini apel) muncul dengan letak jauh dari objek yang lain

Gambar 3 [1] diatas merupakan gambar dua citra yang berbeda dimana memiliki objek penting yang sama (yaitu buah Apel). Namun untuk letak objek penting tersebut berbeda, yaitu ada yang di sebelah kiri atas dan kanan bawah.

Gambar 4 Metode penggabungan dengan n=2; (a) pembagian menjadi nxn blok; (b) hasil dari n penggabungan

Gambar 4 [1] diatas merupakan contoh proses pembagian citra dan proses penggabungan citra. Seperti digambarkan pada gambar 4(a) yaitu terdapat dua citra seperti di gambar 3 tetapi masing-masing citra sudah mengalami proses pembagian citra sebanyak 2x2 (n=2). Pada gambar 4(b) terdapat hasil gabungan citra dari citra yang telah dibagi menjadi nxn blok.

Gambar 6 Diagram Alir Metode NID Pada gambar 6 ditunjukkan diagram alir dari algoritma untuk metode NID sederhana. Sedangkan gambar 7 digambarkan diagram alir dari algoritma untuk metode NID dengan interleaving.

Gambar 5 Hasil penggabungan dengan n=3. Catatan bahwa di salah satu penggabungannya, objek penting (dalam hal ini apel) muncul bersebelahan dengan yang lain

Gambar 5 [1] diatas merupakan hasil gabungan dari citra yang telah dibagi menjadi 9 citra kecil dari masingmasing citra uji.

4

MAKALAH SEMINAR TUGAS AKHIR PERIODE JUNI-JULI 2010 Relevant adalah jumlah citra yang relevan, retrieved adalah jumlah citra yang dikembalikan/diperoleh oleh/dari sistem kepada pengguna. Atau bisa juga ditulis dengan persamaan 8. Presisi = Prelevant|retrieved

(8)

Recall mengevaluasi kemampuan sistem temu kembali informasi untuk menemukan semua item yang relevan dari dalam koleksi data dan didefinisikan sebagai persentase data yang relevan terhadap query pengguna dan yang diterima. Recall merupakan proporsi dari semua citra yang relevan di koleksi termasuk citra yang diperoleh/dikembalikan [3]. Recall dapat dirumuskan menjadi persamaan 9. Recall =

|9:;:<= ∩9:=9:<:>|

(9)

|9:;:<=|

Relevant pada persamaan 9 adalah jumlah citra yang relevan, retrieved adalah jumlah citra yang dikembalikan/diperoleh oleh/dari sistem kepada pengguna. Atau bisa juga ditulis dengan rumus persamaan 10. Recall = Pretrieved|relevant

(10)

Dengan demikian pengertian antara presisi dan recall agar dapat lebih mudah dimengerti dapat dilihat dari tabel 1. Tabel 1 Tabel Relevant dan Retrieved

Gambar 7 Diagram Alir Metode NID Interleaving

6

Retrieved Not Retrieved

Relevant A C

Not Relevant B D

PRESISI DAN RECALL

Sistem temu kembali informasi mengembalikan sekumpulan dokumen sebagai jawaban dari query pengguna. Terdapat dua kategori dokumen yang dihasilkan oleh sistem temu kembali informasi terkait pemrosesan query, yaitu relevant documents (dokumen yang relevan dengan query) dan retrieved documents (dokumen yang diterima pengguna). Ukuran umum yang digunakan untuk mengukur kualitas dari data retrieval adalah kombinasi precision dan recall. Presisi mengevaluasi kemampuan sistem temu kembali informasi untuk menemukan kembali data topranked yang paling relevan, dan didefinisikan sebagai persentase data yang dikembalikan yang benar-benar relevan terhadap query pengguna [3]. Presisi merupakan proporsi dari suatu set yang diperoleh yang relevan [3]. Presisi dapat dirumuskan persamaan 7. "#$%&%& =

|#$'$()*+ ∩ #$+#&$($-| |#$+#&$($-|

Relevant = A + C Retrieved = A + B

(11) (12)

Precision = A / (A+B) Recall = A / (A+C)

(14) (15)

Persamaan 11 dan 12 merupakan rumus untuk mencari data yang relevan dan retrieved dari tabel 1. Persamaan 14 dan 15 merupakan rumus untuk mencari nilai presisi dan recall sesuai data dari tabel 1.

7

UJI COBA DAN EVALUASI

7.1

Uji Coba Hasil Citra yang Ditemukan dari Metode NID

Pada skenario ini, akan dibandingkan dari hasil nilai presisi dan recall dari masing-masing query citra untuk metode NID. Perbandingan akan dilakukan pada 18 query citra yang telah disiapkan sebelumnya oleh penulis. Pada uji coba kali ini dengan menggunakan masukan query citra dan parameter batas NID yang

(7)

5

MAKALAH SEMINAR TUGAS AKHIR PERIODE JUNI-JULI 2010 berbeda-beda maka akan menghasilkan nilai presisi dan recall yang berbeda-beda pula. Dimana dengan masukan parameter batas NID sesuai dengan tabel 2.

1 0,8 0,6 0,4 0,2 0

Tabel 2 Uji Coba Skenario 1 No 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.

Nama File Citra b05.jpg b02.jpg b11.jpg b16.jpg swissmountains30.jpg swissmountains07.jpg swissmountains12.jpg swissmountains24.jpg cherries11.jpg cherries10.jpg cherries13.jpg football05.jpg football14.jpg football19.jpg football37.jpg football36.jpg football07.jpg football43.jpg

NID maksimal 0.2 0.2 0.2 0.2 0.05 0.1 0.1 0.1 0.02 0.02 0.01 0.005 0.01 0.005 0.003 0.003 0.003 0.003

Gambar 8 Contoh Hasil Uji Coba dengan Query = b05.jpg Gambar 8 merupakan gambar citra query dan hasil citra query yang diambil peringkat 6 teratas dari pencarian.

7.2

imgfootba…

football37…

c13.jpg

c11.jpg

sm12.jpg

sm30.jpg

b11.jpg

football14…

Presisi

b05.jpg

Recall

Gambar 7 Grafik Recall 18 query Skenario 1

Dari 18 uji coba di atas masing-masing query citra akan menampilkan citra yang mirip dengan nilai presisi yang termasuk baik yaitu mendekati angka 1. Pada gambar 6 grafik presisi semua query citra menunjukkan nilai presisi masing-masing query berkisar antara nilai 0.6 sampai dengan 1. Dimana performa sistem temu kembali citra ini termasuk ideal atau berfungsi dengan baik jika nilai presisi dan nilai recallnya mendekati angka 0.75.

1,2 1 0,8 0,6 0,4 0,2 0

b05.jpg b11.jpg sm30.jpg sm12.jpg c11.jpg c13.jpg football1… football3… imgfootb…

Recall

Uji Coba Nilai NID Hasil Citra yang Ditemukan dari Metode NID Interleaving

Pada skenario ini, akan dibandingkan nilai NID dari masing-masing query citra untuk metode NID interleaving. Perbandingan akan dilakukan pada query citra yang telah disiapkan sebelumnya oleh penulis dan perbedaan jumlah split atau pembagian partisi citra. Pertama, dilakukan ujicoba pada citra dengan jumlah pembagi citra = 2. Hasil uji coba dapat dilihat di tabel 30.

Presisi

Tabel 2 Uji Coba dengan Jumlah Partisi = 2 No. 1

Gambar 6 Grafik Presisi 18 query Skenario 1

Dan dari uji coba terrsebut juga menghasilkan nilai recall seperti pada gambar 7.

Nama File Sprite can 136.jpg

Hasil Citra sunD3_Apple_079.jpg

0.2321297

fluor2_SpriteCan_139.jpg

0.2346774


0.2410936


0.2459016

sunD3_Apple_078.jpg

0.2459016

sunD3_Apple_080.jpg

0.2605459

fluor7_JuliesPot_030.jpg

6

NID

0.266786

sunD3_Apple_075.jpg

0.2674024

sunD3_Apple_076.jpg

0.2701544


0.2724014



0.2754821


0.2822581


0.2911275


0.2935185


2

JuliesPot 030.jpg

3

Apple 075. jpg

Tabel 3 Uji Coba dengan Jumlah Partisi = 3 No. 1

0.2979798


0.3


0.3206578

sunD3_Apple_077.jpg

0.3207739

sunD3_Apple_079.jpg

0.2635025

sunD3_Apple_080.jpg

0.2802437

sunD3_Apple_078.jpg

0.3003597


0.3131868


0.3175487

sunD3_Apple_076.jpg

0.3282365

sunD3_Apple_075.jpg

0.3305955


0.3377149


0.3429158


0.3432836

sunD3_Apple_077.jpg

0.3650794


0.3663254


0.3717805


0.3955774


0.4050314


Kedua, dilakukan ujicoba pada citra dengan jumlah pembagi citra = 3. Hasil uji coba dapat dilihat di tabel 31.

2

0.40625


0.4356436


0.4485228

sunD3_Apple_079.jpg

0.5829035


0.6151444

sunD3_Apple_078.jpg

0.6159251

sunD3_Apple_080.jpg

0.6214099


0.6467742


0.6518106


0.6644573

sunD3_Apple_075.jpg

0.6714771

sunD3_Apple_076.jpg

0.6751313


0.7078853


0.7179946


0.718638


0.7231481


0.7310536


0.7330595


0.7428834

sunD3_Apple_077.jpg

0.8105906


0.8139774

3


JuliesPot 030.jpg

Apple 075.jpg

Hasil Citra fluor2_SpriteCan_141.jpg

0.2640509


0.28072153


0.28489703

sunD3_Apple_079.jpg

0.2862069

sunD3_Apple_078.jpg

0.29122807

sunD3_Apple_080.jpg

0.29252577

sunD3_Apple_076.jpg

0.29678188


0.30106101

sunD3_Apple_075.jpg

0.30477356


0.30589681


0.30855019


0.31281407


0.31439394


0.31598985


0.31760204


0.3221216

sunD3_Apple_077.jpg

0.32379714


0.34156379


0.01908802


0.02029312


0.02059497

sunD3_Apple_079.jpg

0.02068966

sunD3_Apple_078.jpg

0.02105263

sunD3_Apple_080.jpg

0.02135231

sunD3_Apple_076.jpg

0.02145411

sunD3_Apple_075.jpg

0.02203182


0.02211302


0.02230483


0.02261307


0.02272727


0.02284264


0.02284264


0.02295918


0.0232859

sunD3_Apple_077.jpg

0.02340702


0.02469136


0.2831389


0.3010147


0.305492

sunD3_Apple_079.jpg

7

NID

0.3068966


sunD3_Apple_078.jpg

0.3122807


-0.03013

sunD3_Apple_080.jpg sunD3_Apple_076.jpg

0.316726

sunD3_Apple_079.jpg

-0.03013

0.318236


-0.03008

sunD3_Apple_075.jpg

0.3268054

sunD3_Apple_077.jpg

-0.03002


0.3280098


-0.02996


0.330855

sunD3_Apple_080.jpg

-0.02996


0.3354271


-0.02985


0.3371212


-0.02985


0.3388325

sunD3_Apple_075.jpg

-0.02974


0.3388325


-0.02963


0.3405612

sunD3_Apple_078.jpg

-0.02909


0.3454075

sunD3_Apple_077.jpg fluor7_JuliesPot_029.jpg

3


0.2989214

0.3472042


0.3035994

0.3662551


0.3084261


0.3108974

sunD3_Apple_079.jpg

0.3108974

sunD3_Apple_078.jpg

0.3139159

sunD3_Apple_080.jpg

0.3144246


0.3206612


0.3249581


0.3260504

sunD3_Apple_075.jpg

0.3260504

sunD3_Apple_076.jpg

0.3265993


0.3327616


0.3368056


0.3415493


0.3427562


0.3482944

sunD3_Apple_077.jpg

0.3495495

Ketiga, dilakukan ujicoba pada citra jumlah pembagi citra = 4. Hasil uji coba dapat dilihat di tabel 32. Tabel 4 Uji Coba dengan Jumlah Partisi = 4 No. 1


Hasil Citra

2

JuliesPot 030.jpg

NID


0.16486903


0.16744914


0.17011129


0.17147436

sunD3_Apple_079.jpg

0.17147436

sunD3_Apple_078.jpg

0.17313916

sunD3_Apple_080.jpg

0.17341977


Apple 075.jpg

0.1768595


0.17922948


0.17983193

sunD3_Apple_075.jpg

0.17983193

sunD3_Apple_076.jpg

0.18013468


0.18353345


0.18576389


0.18838028


0.18904594


0.19210054

sunD3_Apple_077.jpg

0.19279279


-0.03042


-0.0303


-0.03025

sunD3_Apple_076.jpg

-0.03025


-0.03019


-0.03019


-0.03013

Gambar 9 Contoh Hasil Uji Coba Query = SpriteCan 136.jpg Gambar 9 merupakan gambar citra query beserta hasilnya dengan perbedaan jumlah pembagian citra yaitu 2,3 dan 4. Citra yang diberi tanda silang (x) merupakan citra yang tidak relevan dengan query citranya.

8


8

pencarian data seperti dokumen, suara, visual dan lain sebagainya.

KESIMPULAN

Pada skenario satu yaitu uji coba terhadap algoritma pertama dari rumus NID persamaan 4 memiliki parameter batas NID sebagai threshold pencarian citra sampai jarak informasi tidak lebih dari batas tersebut. Nilai maksimum batas NCD tersebut untuk setiap tipe atau jenis citra memiliki nilai yang berbeda agar dapat menampilkan citra yang relevan. Untuk tipe citra beruang memiliki nilai threshold sebesar 0.2 agar dapat menampilkan citra relevan yang lebih banyak. Hal itu dikarenakan nilai NCD untuk citra masukan bertipe beruang dengan citra yang relevan nilainya berkisar antara 0.1 sampai dengan 0.19. Sedangkan untuk tipe citra gunung es kutub memiliki nilai threshold sebesar 0.05. Hal itu dikarenakan tipe citra ini cukup menghasilkan nilai NCD berkisar antara 0.01 sampai dengan 0.05 agar dapat menghasilkan citra relevan. Tipe citra pohon sakura membutuhkan nilai batas maksimal NCD sebesar 0.01 dan 0.02 untuk dapat menampilkan citra relevan yang nilai NCD nya berada pada kisaran nilai 0.001 sampai dengan 0.02. Tipe citra lapangan sepakbola memiliki nilai batas NCD sebesar 0.005, 0.003 dan 0.01. Hal itu berarti nilai NCD antara citra bertipe lapangan sepakbola memiliki nilai yang kecil antara 0.001 sampai dengan 0.01. Dari semua query citra yang dipakai menghasilkan hasil yang baik dimana nilai presisi masing-masing query mendekati nilai 0.75. Nilai presisi yang baik adalah mendekati angka 0.75 atau lebih. Sehingga bisa disimpulkan sistem ini bisa menampilkan citra yang relevan. Selain nilai presisi, pada sistem temu kembali informasi perlu adanya pengukuran nilai recall agar dapat membuktikan apakah sistem dapat menampilkan semua citra yang relevan di dataset. Pada tugas akhir ini nilai recall untuk masing-masing tipe citra memiliki karakteristik berbeda. Tipe citra beruang misalnya, memiliki nilai recall yang baik karena berkisar antara 0.75 sampai 1. Sehingga untuk tipe citra ini dapat berjalan dengan bagus. Tetapi lain halnya dengan tipe citra pohon sakura, lapangan sepakbola dan gunung es. Nilai recall untuk tipe tersebut kurang bagus yaitu di bawah angka 0.75. Sehingga dapat disimpulkan bahwa sistem ini kurang bagus karena tidak semua citra yang relevan ditampilkan (retrieved). Pada skenario dua yaitu uji coba terhadap algoritma kedua dari rumus NID interleaving persamaan 6 memiliki parameter batas nilai maksimum NID dan jumlah pembagian partisi citra. Namun untuk uji coba kali ini yang dibandingkan adalah nilai NID hasil temuan citra dengan perbedaan jumlah nilai pembagi partisi citra. Dapat disimpulkan bahwa semakin besar jumlah nilai pembagi citra maka nilai NID dari citra tersebut semakin kecil sehingga pengukuran similaritasnya lebih mendekati nol (0) dengan kata lain citra mirip. Saran untuk pengembangan lebih lanjut dari Tugas Akhir ini adalah metode NID agar dapat dikembangkan dalam hal selain pencarian citra atau CBIR namun juga bisa digunakan sebagai metode untuk

REFERENSI [1]

Iker Gondra, Douglas R. Heisterkamp, ContentBased Image Retrieval with The Normalized Information Distance, Elsevier, http://sciencedirect.com , 2008 [2] Developer Resources for Java Technology : Java Sun Home Page. Diakses 3 Maret 2010. [3] Vista, Buena Lake, Proceedings of The Fourth SIAM International Conference on Data Mining, Siam, Florida, 2004 [4] University of Washington, groundtruth image database. http://www.cs.washington.edu/research/imagedatab ase/groundtruth. [5] Sample images taken from the SIVAL benchmark (http:// www.cs.wustl.edu/~sg/accio/SIVAL.html). [6] A.W.M. Smeulders, M. Worring, S. Santini, A. Gupta, R. Jain, Content-based image retrieval at the end of the early years, IEEE Transactions on Pattern Analysis and Machine Intelligence 22 (12) (2000) 1349–1380. [7] M. Li, X. Chen, X. Li, B. Ma, P. Vita´nyi, The similarity metric, in: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 863–872. [8] A. Kolmogorov, Logical basis for information theory and probability theory, IEEE Transactions on Information Theory 14 (1968) 662– 664. [9] M. Li, P. Vita´nyi, An introduction to Kolmogorov complexity and its applications, Springer, New York, NY, 1997. [10] The GZIP Home Page. Diakses 15 April 2010. [11] Kagan Arkadi, Entropy Compression Methods, sourceforge.net,.

9

IMPLEMENTASI SISTEM TEMU KEMBALI CITRA BERBASIS ISI DENGAN METODE JARAK INFORMASI YANG DINORMALISASI

Recommend Documents