ANOTASI AUTOMATIS CITRA MENGGUNAKAN STATISTICAL MACHINE TRANSLATION UNTUK TEMU KEMBALI CITRA
IMAM ABU DAUD
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2008
ANOTASI AUTOMATIS CITRA MENGGUNAKAN STATISTICAL MACHINE TRANSLATION UNTUK TEMU KEMBALI CITRA
Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
IMAM ABU DAUD G64104052
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2008
ABSTRAK IMAM ABU DAUD. Anotasi Automatis Citra menggunakan Statistical Machine Translation untuk Temu Kembali Citra. Dibimbing oleh YENI HERDIYENI dan SRI NURDIATI. Penelitian ini melakukan implementasi anotasi automatis citra menggunakan statistical machine translation untuk temu kembali citra. Penerjemahan citra ke kata dianalogikan seperti menerjemahkan satu bahasa ke bahasa lainnya. Objek untuk penerjemahan diperoleh dari koleksi citra yang telah dianotasi secara manual. Pertama, citra disegmentasi menjadi beberapa region berukuran sama menggunakan segmentasi grid. Region tersebut kemudian direpresentasikan oleh ciri citra yang telah didefinisikan sebelumnya. Kedua, region seluruh citra dikelompokkan menjadi kelompok blob yang berukuran lebih kecil menggunakan algoritme k-means. Ketiga, hubungan antara blob dengan kata dicari menggunakan algoritme expectation maximization. Hubungan yang terbentuk digunakan untuk memprediksi kata yang berhubungan dengan sebuah citra (anotasi automatis). Evaluasi kualitas anotasi automatis dilakukan menggunakan algoritme normalized score (ENS). Variasi ukuran grid saat segmentasi diberikan kepada seluruh citra latih dan uji. Hasil percobaan terhadap 750 citra latih dan 250 citra uji berukuran 384 × 256 piksel menunjukkan bahwa nilai ENS terbaik diperoleh oleh model yang dibentuk oleh data latih dengan ukuran grid pada segmentasi sebesar 2×3, dengan rataan ENS sebesar 0.4608 dan ukuran grid 8×12 untuk citra uji saat evaluasi dengan rataan ENS sebesar 0.4862. Temu kembali citra dilakukan menggunakan latent semantic indexing untuk mengeksploitasi makna semantik dari anotasi automatis seluruh citra. Dimensi latent semantic indexing diperoleh dari hasil dekomposisi matriks anotasi automatis seluruh citra. Rataan recall dan precision dihitung untuk dua jenis kueri: klausa dan teks. Hasil penelitian menunjukkan kueri berbentuk klausa memberikan rataan precision yang lebih tinggi dibandingkan kueri teks. Rataan precision kueri klausa untuk setiap tingkat recall yaitu sebesar 0.5442, sedangkan rataan precision untuk kueri teks bernilai 0.2509. Hasil tersebut menunjukkan bahwa metode latent semantic indexing dapat memunculkan makna semantik dari citra sehingga citra hasil temu kembali lebih relevan terhadap kueri yang diberikan. Keywords : Content-based image retrieval, automatic annotation, statistical machine translation, latent semantic indexing.
Judul : Anotasi Automatis Citra menggunakan Statistical Machine Translation untuk Temu Kembali Citra Nama : Imam Abu Daud NIM : G64104052
Menyetujui:
Pembimbing I,
Pembimbing II,
Yeni Herdiyeni, S.Si, M.Kom NIP 132282665
Dr. Ir. Sri Nurdiati, M.Sc NIP 131578805
Mengetahui: Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Dr. Drh. Hasim, DEA NIP 131578806
Tanggal Lulus:
RIWAYAT HIDUP Penulis dilahirkan di Bogor pada tanggal 27 Oktober 1985 dari pasangan Sriwati dan Djuanda. Penulis merupakan putra kelima dari enam bersaudara. Tahun 2004 penulis lulus dari SMU Negeri 1 Bogor. Pada tahun yang sama, penulis diterima di Departemen Ilmu Komputer Institut Pertanian Bogor pada Program Studi Ilmu Komputer melalui jalur Undangan Seleksi Masuk IPB (USMI) untuk melanjutkan ke jenjang pendidikan S1. Selama di IPB, penulis aktif dalam kegiatan beberapa kegiatan kemahasiswaan terutama di Himpunan Mahasiswa Ilmu Komputer (HIMALKOM) periode 2005/2006. Pada tahun 2007 penulis mendapatkan beasiswa prestasi dari Bank Indonesia. Pada tahun yang sama, menjalankan Praktek Lapangan di Lembaga Riset Perkebunan Indonesia (LRPI) Bogor pada bulan Juni 2007 hingga Agustus 2008.
PRAKATA Alhamdulillahi Rabbil ‘alamin, puji dan syukur penulis panjatkan kepada Allah SWT atas segala curahan rahmat dan karunia-Nya sehingga tugas akhir ini dapat diselesaikan. Tugas akhir ini berjudul Anotasi Automatis Citra menggunakan Metode Statistical Machine Translation untuk Temu Kembali Citra. Dalam menyelesaikan tugas akhir ini penulis mendapatkan banyak sekali bantuan, bimbingan dan dorongan dari berbagai pihak. Oleh karena itu, penulis ingin mengucapkan terima kasih kepada semua pihak yang telah membantu dalam penyelesaian tugas akhir ini, antara lain: Kedua orangtua tercinta, mamah Sri dan bapak Djuanda atas segala do’a, kasih sayang, dan 1 dukungannya, 2 Faza dan Fatih yang telah memberikan inspirasi baru dalam penyelesaian tugas akhir ini, 3 Ibu Yeni Herdiyeni, S.Si, M.Kom selaku pembimbing pertama atas bimbingan dan arahannya selama pengerjaan tugas akhir ini, 4 Ibu Dr. Ir. Sri Nurdiati, M.Sc selaku pembimbing kedua atas bimbingan dan arahannya selama pengerjaan tugas akhir ini, 5 Bapak Firman Ardiansyah, S.Kom, M.Si atas kesediannya menjadi penguji penelitian ini, Gibtha Fitri Laxmi, atas segala bantuan dan dukungannya dalam menyelesaikan tulisan ini, 6 7 Seluruh penghuni Irafan: cupu, hode, andara, brank, singo, kikisu dan radi atas kebersamaannya selama penulisan skripsi ini berlangsung, Seluruh teman laboratorium CI atas dukungan dan kebersamaannya, 8 9 Seluruh teman-teman seperjuangan Program Studi Ilmu Komputer angkatan 41 yang tidak dapat disebutkan namanya satu-persatu. Penulis menyadari bahwa dalam pelaksanaan penelitian ini masih jauh dari kesempurnaan, namun besar harapan penulis bahwa apa yang telah dikerjakan dapat memberikan manfaat bagi seluruh pihak.
Bogor, September 2008
Imam Abu Daud
DAFTAR ISI Halaman DAFTAR TABEL ........................................................................................................................... vi DAFTAR GAMBAR....................................................................................................................... vi DAFTAR LAMPIRAN ................................................................................................................... vi PENDAHULUAN ............................................................................................................................ 1 Latar Belakang.............................................................................................................................. 1 Tujuan ........................................................................................................................................... 1 Ruang Lingkup ............................................................................................................................. 1 Manfaat Penelitian ........................................................................................................................ 1 TINJAUAN PUSTAKA ................................................................................................................... 1 Content-based Image Retrieval .................................................................................................... 1 Anotasi Citra ................................................................................................................................. 2 Segmentasi .................................................................................................................................... 2 Tokenisasi ..................................................................................................................................... 2 Representasi Warna ...................................................................................................................... 2 Representasi Tekstur..................................................................................................................... 2 Statistical Machine Translation (SMT) ........................................................................................ 3 Expectation Maximization (EM) ................................................................................................... 3 Perhitungan Kinerja Anotasi Automatis ....................................................................................... 3 Recall dan Precision ..................................................................................................................... 3 Latent Semantic Indexing (LSI) .................................................................................................... 3 Distribusi Zipfian .......................................................................................................................... 4 METODE PENELITIAN ................................................................................................................. 4 Pembentukan Model SMT ............................................................................................................ 4 Tokenisasi ............................................................................................................................. 5 Expectation Maximization (EM) ........................................................................................... 5 Evaluasi Anotasi Automatis ......................................................................................................... 6 Pembentukan Model LSI .............................................................................................................. 7 Evaluasi Hasil Temu Kembali ...................................................................................................... 7 Perangkat Keras dan Perangkat Lunak yang Digunakan .............................................................. 8 HASIL DAN PEMBAHASAN ........................................................................................................ 8 Data Penelitian............................................................................................................................. 8 Pembentukan Data Latih .............................................................................................................. 8 Pembentukan Model SMT ............................................................................................................ 9 Tokenisasi ............................................................................................................................. 9 Expectation Maximization (EM) ........................................................................................... 9 Evaluasi Anotasi Automatis ......................................................................................................... 9 Pembentukan model LSI ............................................................................................................ 11 Evaluasi hasil temu kembali ....................................................................................................... 11 KESIMPULAN DAN SARAN ...................................................................................................... 12 Kesimpulan ................................................................................................................................. 12 Saran ........................................................................................................................................... 12 DAFTAR PUSTAKA ..................................................................................................................... 12 LAMPIRAN ................................................................................................................................... 14
v
DAFTAR TABEL Halaman 1 2 3 4 5
Deskripsi ciri tiap blob citra ....................................................................................................... 5 Notasi EM yang digunakan pada penelitian ............................................................................... 6 Rataan ENS untuk setiap data uji terhadap model hasil data latih ............................................... 9 Rataan ENS untuk evaluasi ulang dengan nilai n yang diperkecil...............................................10 Rataan recall dan precision untuk evaluasi hasil temu kembali ................................................12
DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Ilustrasi tokenisasi citra yang disegmentasi dengan ukuran grid 8×12. ...................................... 2 Metodologi penelitian. ................................................................................................................ 4 Pembentukan model SMT. ......................................................................................................... 4 Proses tokenisasi. ........................................................................................................................ 5 Proses pembentukan tabel translasi. ........................................................................................... 6 Evaluasi model SMT. ................................................................................................................. 7 Pembentukan model LSI. ........................................................................................................... 7 Evaluasi hasil temu kembali. ...................................................................................................... 8 Proses pembentukan data latih dalam pembentukan model SMT. ............................................. 8 Perbandingan nilai ENS hasil evaluasi. .......................................................................................10 Stagnansi pada perkembangan nilai ENS data latih A untuk nilai n = {1,..., 69} ........................10 Nilai ENS pada data latih A terhadap seluruh data uji dengan n yang diperkecil. .....................10 Perbandingan nilai ENS untuk seluruh model. ............................................................................10 Anotasi yang cukup baik model hasil data latih A dengan n = 3 . ............................................11 Anotasi yang kurang baik model hasil data latih A dengan n = 7 ............................................11 Nilai singular value matriks LSI pada beberapa nilai k. ............................................................11 Grafik recall dan precision untuk hasil temu kembali citra pada model LSI. ...........................12
DAFTAR LAMPIRAN Halaman 1 2 3 4
Skema pembagian data pada penelitian .....................................................................................15 Sebaran kata seluruh citra ..........................................................................................................16 Contoh hasil temu kembali menggunakan kueri teks ................................................................17 Contoh hasil temu kembali menggunakan kueri klausa.............................................................18
vi
1
PENDAHULUAN Latar Belakang Dalam dunia temu kembali citra, temu kembali dapat dilakukan dengan dua cara berbeda. Dua metode tersebut dibedakan berdasarkan kueri yang digunakannya: queryby-text (QbT) dan query-by-example (QbE). QbT menggunakan teks sebagai kueri dan target yang diharapkan adalah citra, sedangkan dalam QbE, kuerinya adalah citra dan target yang diharapkan adalah citra (Inoue 2004). Kedua pendekatan tersebut memiliki kelebihan dan kekurangan masing-masing. Sebagai contoh, Brahmi et al. (2004) menyebutkan beberapa kekurangan berikut merupakan kelemahan temu kembali citra berdasarkan teks atau annotation based image retrieval (ABIR). Pertama, anotasi citra secara manual membutuhkan waktu yang lama. Kedua, anotasi sangatlah subjektif, citra yang sama dapat dideskripsikan secara berbeda oleh orang yang berbeda. Sebagai tambahan, beberapa citra sulit dideskripsikan isinya menggunakan deskripsi tekstual misalnya logo perusahaan. ABIR memiliki dua alasan yang menjadikannya lebih populer. Pertama, komputasi yang dibutuhkan dalam ABIR jauh lebih sederhana dan ringan. Kedua, makna semantik dari citra yang lebih disukai pengguna dapat ditemukembalikan dalam ABIR. Melihat kelebihan dan kelemahan dari setiap metode temu kembali citra tersebut, Mori et al. (1999) mengembangkan model bernama cooccurence untuk mengidentifikasi suatu objek dalam sebuah citra sehingga anotasi automatis co-occurence dapat dilakukan. Model menggunakan segmentasi grid untuk memperoleh deskripsi ciri citra karena kecepatan dan kemudahan dalam penggunaanya. Kelemahan utama model co-occurence yaitu kecenderungan untuk memetakan citra kepada kata yang memiliki frekuensi tinggi. Selain itu, model tersebut membutuhkan data latih yang sangat banyak agar dapat berjalan optimal. Duygulu (2003) mengembangkan sebuah model bernama statistical machine translation untuk memperbaiki hasil yang diperoleh model co-occurence. Model yang dikembangkan Duygulu (2003) tersebut menggunakan algoritme normalized cut (Shi & Malik 2000) pada saat segmentasi. Sayangnya algoritme normalized cuts terlalu kompleks dan
memberikan hasil yang tidak stabil (Duygulu 2003). Kelebihan dan kekurangan kedua model tersebut memunculkan ide pada penelitian ini untuk melakukan anotasi automatis menggunakan model statistical machine translation karena memiliki hasil yang cukup baik, dengan mengganti algoritme segmentasi yang digunakan. Segmentasi akan dilakukan grid untuk menggunakan segmentasi mempercepat proses anotasi automatis. Temu kembali citra berdasarkan anotasi automatis saja memiliki hasil yang kurang baik. Hal tersebut disebabkan oleh banyak hal, misalnya akurasi anotasi automatis dari algoritme yang digunakan. Pada akhirnya hasil temu kembali citra akan dipengaruhi secara langsung oleh hasil anotasi automatis citra. Implementasi Latent Semantic Indexing pada penelitian ini diberikan pada tahap temu kembali citra untuk mengeksploitasi makna semantik dari anotasi automatis. Tujuan 1
2
Penelitian ini bertujuan: Mengimplementasikan anotasi citra secara automatis menggunakan metode statistical machine translation (SMT) dengan segmentasi grid. Mengimplementasikan latent semantic indexing (LSI) hasil anotasi automatis pada temu kembali citra.
Ruang Lingkup Citra yang digunakan merupakan citra fotografi dengan dimensi 384 × 256 piksel dengan rasio lebar:tinggi sebesar 3:2. Manfaat Penelitian Penggunaan anotasi automatis dalam temu kembali berbasis LSI dapat mengatasi kesenjangan semantik dalam sistem temu kembali citra. Deskripsi citra berupa teks dapat digunakan sebagai kueri dalam pencarian citra.
TINJAUAN PUSTAKA Content-based Image Retrieval
Content-based image retrieval (CBIR) merupakan suatu pendekatan untuk masalah temu kembali citra yang didasarkan pada ciri yang terkandung di dalam citra seperti warna, bentuk, dan tekstur dari citra (Han & Ma 2002).
2
Anotasi Citra Anotasi citra adalah proses pemberian deskripsi pada citra. Anotasi dapat berisi deskripsi internal dari citra seperti nama objek atau dapat pula mengandung ciri eksternal seperti tanggal pembuatan dan nama pemilik. Anotasi citra automatis berarti pemberian deskripsi citra tersebut dilakukan secara automatis (unsupervised). Segmentasi Segmentasi merupakan proses untuk memperoleh bagian dari citra dengan karakteristik tertentu. Segmentasi yang digunakan dalam penelitian ini adalah segmentasi grid, yaitu membagi citra dalam beberapa region bujursangkar dengan ukuran sama. Hal ini dilakukan karena membagi dengan cara tersebut merupakan cara yang paling cepat dan mudah dalam membagi citra (Mori et al. 1999). Tokenisasi Tokenisasi bertujuan memecah komponen deskripsi visual (token blob) dan deskripsi tekstual (token kata) dari citra. Token kata dapat diperoleh secara langsung dari anotasi manual citra, sedangkan token blob citra diperoleh dalam beberapa tahap. Pertama, citra disegmentasi menjadi beberapa region berukuran sama. Kedua, sekumpulan ciri seperti warna, tekstur, bentuk, ukuran, dan posisi dihitung untuk merepresentasikan setiap region (Duygulu 2003). Region-region tersebut diklasifikasikan menjadi tipe region dari token blob dengan cara mengelompokkan seluruh token blob untuk seluruh region pada data. Kemudian setiap region diberi label berdasarkan cluster keanggotaanya, yaitu indeks dari token blob.
Pada Gambar 1, contoh untuk citra beserta anotasinya dalam tokenisasi. Region citra hasil segmentasi diganti dengan token blob yang merepresentasikan token blob tersebut, dan anotasi citra diganti dengan token kata. Untuk meringkas konsep, selanjutnya istilah token blob dan token kata akan disebut sebagai blob dan kata saja. Representasi Warna Model warna CIE L*a*b* dikembangkan oleh CIE (Comission Internationale de L'Eclairage atau International Commission on Illumination) pada tahun 1967. Model ini merupakan model konvensional yang paling lengkap dalam mendeskripsikan warna yang dapat dilihat oleh mata manusia (LACIE 2006). Model L*a*b* didesain untuk meniru sistem penglihatan manusia. Komponen "L" merepresentasikan kecerahan (Lightness), komponen "a" merepresentasikan spektrum warna hijau hingga magenta, dan "b" untuk spektrum warna biru hingga kuning. Selain CIE L*a*b*, representasi yang cukup baik digunakan dalam merefleksikan visualisasi mata manusia adalah model rgS (Barnard 2003). Setiap elemen rgS diperoleh dengan cara: S=R+G+B, r=R/S, dan g=G/S. Untuk kedua model warna tersebut, baik rataan maupun ragam (variance) pada region citra dihitung sebagai ciri yang digunakan untuk merepresentasikan region tersebut. Representasi Tekstur
Mean oriented energy merupakan salah satu algoritme untuk merepresentasikan karakteristik tekstur dari citra digital. Ciri ini dihitung dengan mengaplikasikan filter berarah terhadap citra. Filter yang digunakan pada umumnya adalah filter Gabor. Ciri tekstur diperoleh dengan cara bertahap. Pertama, setiap region citra dikonvolusi dengan filter berarah. Kemudian, nilai rataan deviasi absolut terhadap rataan citra filter pada region hasil filter dihitung berdasarkan persamaan berikut (Tang 2008):
Vθ =
Gambar 1 Ilustrasi tokenisasi citra yang disegmentasi dengan ukuran grid 8×12.
1 N
N
∑ Fθ − Pθ i
i =1
dengan θ = {30°,60°,...,360°}, N merupakan jumlah piksel dalam region, Pθ merupakan rataan nilai piksel Fiθ, dengan Fiθ merupakan piksel hasil filter.
3
Statistical Machine Translation (SMT) Duygulu (2003) mengembangkan model bernama statistical machine translation untuk anotasi automatis. Duygulu (2003) berpendapat bahwa anotasi automatis berbasis region lebih baik karena anotasi berbasis global tidak memberikan informasi tentang bagian mana dari citra yang berhubungan dengan label tertentu. Proses pemberian label terhadap region citra memiliki analogi yang sama dengan menerjemahkan suatu bentuk representasi (region citra; bahasa perancis) ke bentuk lainnya (label; bahasa inggris) dalam teori statistika klasik: statistical translation model. Anotasi automatis dilakukan dengan cara memprediksi kata (w) dengan peluang posterior tertinggi pada citra terhadap blob (b) atau p(w|b). Untuk memperoleh peluang posterior kata citra, peluang posterior untuk blob dari citra tersebut, yang diperoleh dari tabel translasi dijumlahkan dan dinormalisasi. Secara matematis, untuk citra I, dapat ditulis:
p ( w | I ) = ∑ i =1 p ( w | bi ) L
dengan bi adalah blob ke-i dari citra I. Anotasi automatis diperoleh dengan memprediksi n buah kata dengan peluang posterior tertinggi, n merupakan bilangan yang dengan didefinisikan sebelumnya. Expectation Maximization (EM)
Expectation-Maximization (EM) adalah salah satu metode optimasi untuk mencari dugaan parameter maximum likelihood ketika ada data yang hilang atau tidak lengkap. EM terdiri dari dua tahap. Pertama, perhitungan dugaan kemungkinan untuk memprediksi data yang tidak lengkap (E-step). Kedua, perhitungan dugaan parameter maximum likelihood (M-step) dengan memaksimalkan dugaan kemungkinan yang diperoleh dari Estep. Nilai parameter yang diperoleh dari M-step digunakan kembali untuk memulai E-step selanjutnya. Proses ini akan berulang hingga mencapai konvergensi nilai likelihood (Belongie et al. 1998). Perhitungan Kinerja Anotasi Automatis Barnard et al. (2003) mengajukan metode skoring bernama normalized score untuk mengevaluasi hasil dari proses anotasi automatis, mengikuti persamaan berikut:
ENS =
r w − n a ( N − na )
dengan:
N : ukuran kamus kata (kosakata kata) na : jumlah kata aktual untuk citra r : jumlah kata yang tepat terprediksi w : jumlah kata yang salah terprediksi Nilai ENS sama dengan 1 berarti anotasi berjalan dengan sempurna, -1 untuk kebalikannya, dan 0 jika memprediksi semua kata atau memprediksi 0 (nol) kata. Pemilihan jumlah prediksi anotasi atau n dapat dilakukan melalui beberapa percobaan untuk memperoleh nilai yang menghasilkan ENS terbaik. Recall dan Precision Dua parameter utama yang digunakan untuk mengukur keefektifan temu kembali adalah recall dan precision. Recall dan precision diperoleh sesuai persamaan berikut: recall =
jumlah citra relevan yang terambil jumlah citra relevan dlm basis data
jumlah citra relevan yang terambil jumlah seluruh citra yang terambil Rataan precision adalah ukuran evaluasi yang diperoleh dengan cara menghitung rataan tingkat precision pada berbagai tingkat recall (Grossman 2002). precision =
Latent Semantic Indexing (LSI)
Latent Semantic Indexing (LSI) adalah sebuah metode baru dalam algoritme search engine yang dikembangkan Google Corporation (Ferdian et al. 2005). Dengan metode ini, Google menganalisis kata kunci dengan cara baru, bukan lagi berdasarkan pencocokkan kata secara leksikal. Kata yang dicari tidak hanya kata kuncinya seperti cara kerja algoritme pada umumnya, tetapi kata-kata yang berhubungan dengan kata kunci juga dicari. Tujuan dari LSI adalah mendapatkan suatu pemodelan yang efektif untuk merepresentasikan hubungan antara kata kunci dan dokumen yang dicari. Sekumpulan kata kunci yang awalnya tidak lengkap dan tidak berhubungan menjadi sekumpulan objek yang saling berhubungan. LSI diterapkan menggunakan matriks singular value decomposition (SVD) hasil dekomposisi matriks kata-dokumen. Pada
4
penelitian ini, kata diasosiasikan dengan anotasi citra (kata) dan dokumen diasosiasikan dengan citra. Matriks kata-citra tersebut didekomposisi menjadi :
A = USVT dengan A adalah matriks kata-citra, matriks U, S, dan VT hasil dekomposisi SVD. Koordinat baru setiap citra pada dimensi LSI diperoleh dari matriks VT, sedangkan matriks S dan U digunakan untuk transformasi kueri ke dalam dimensi LSI seperti berikut (Garcia 2006):
qLSI = qTUk Sk-1 dengan qT adalah queri dalam bentuk vektor baris, Uk adalah matriks U yang direduksi, dan Sk-1 adalah invers matriks S yang direduksi. Perhitungan kemiripan dilakukan antara koordinat kueri dengan koordinat seluruh citra pada dimensi LSI menggunakan cosine similarity antara koordinat kueri dengan koordinat citra sesuai persamaan berikut: sim(qLSI , d ) =
qLSI • d | qLSI || d |
dengan d adalah koordinat citra dalam dimensi LSI, | q | dan | d | adalah panjang dari kueri qLSI
Gambar 2 Metodologi penelitian. Pembentukan Model SMT Pembentukan model SMT seperti terlihat pada Gambar 3, dilakukan melalui dua tahap yaitu: 1
Tokenisasi.
2
Expectation Maximization (EM).
dan citra d. Distribusi Zipfian Distribusi Zipfian yaitu distribusi peluang dengan frekuensi kemunculan benda yang dimulai dari sangat tinggi, kemudian konvergen ke sangat kecil (Black 2004).
METODE PENELITIAN Metode penelitian ini terdiri dari empat tahap utama sesuai ilustrasi pada Gambar 2: 1
Pembentukan model SMT.
2
Evaluasi anotasi automatis.
3
Pembentukan model LSI.
4
Evaluasi hasil temu kembali. Gambar 3 Pembentukan model SMT. Pembentukan model SMT dilakukan dengan menciptakan tabel translasi pasangan blob-kata. Tabel ini selanjutnya digunakan sebagai tabel penerjemah blob ke kata dengan nilai peluang tertentu. Proses pelatihan dilakukan menggunakan citra latih sebanyak 750 citra beserta anotasi
5
manualnya. Citra tersebut dipisahkan menjadi tiga jenis data latih berdasarkan ukuran grid yang digunakan dalam segmentasi, yaitu 2×3 (data latih A), 4×6 (data latih B), dan 8×12 (data latih C). • Tokenisasi Tahap ini bertujuan memperoleh karakteristik visual (blob) dan label (kata) dari citra. Seperti yang terlihat pada Gambar 4, citra disegmentasi menjadi beberapa region bujursangkar berdasarkan ukuran grid tertentu, kemudian ciri citra dari tiap region tersebut dihitung. Ciri yang digunakan untuk setiap region (blob) dalam grid yaitu sebanyak 26 buah untuk tiap region sesuai Tabel 1. Ciri ini dipilih karena cukup baik dalam merepresentasikan citra untuk anotasi automatis (Duygulu et al. 2003; Barnard et al. 2003). Tabel 1 Deskripsi ciri tiap blob citra Nama ciri
Jumlah ciri
Position
2
Average rgS
3
Variance rgS
3
Average CIE Lab
3
Variance CIE Lab
3
Mean oriented energies
12
Ciri posisi citra (position) digunakan untuk memberikan bobot tambahan terhadap blob dengan posisi tertentu agar lebih condong ke objek tertentu, misalkan water untuk posisi di bawah, cloud untuk posisi di atas. Posisi ini dihitung berdasarkan posisi relatif titik tengah region terhadap citra sumber. Ciri citra hasil tokenisasi masih berbentuk ciri kontinu. Pengelompokkan ciri tersebut perlu dilakukan untuk memperkecil jumlah ruang ciri (blob) yang ada. Pengelompokkan dilakukan menggunakan algoritme k-means. Selanjutnya ciri kontinu untuk setiap region diganti dengan nomor cluster yang merepresentasikan vektor ciri tersebut menjadi blob seperti yang terlihat pada Gambar 4.
Blob dan kata akan menjadi representasi dari citra yang bersangkutan pada tahap selanjutnya. Baik blob maupun kata direpresentasikan dalam bentuk vector space model untuk menyederhanakan komputasi selanjutnya.
Gambar 4 Proses tokenisasi. Setelah tokenisasi, sekumpulan blob dan pasangan kata (aligned bitext) untuk setiap citra diperoleh. Permasalahannya adalah aligned bitext tersebut tidak memberikan hubungan yang eksplisit antara blob dengan kata –tidak ada informasi eksplisit blob mana yang berhubungan dengan label sky. Permasalahan tersebut dapat diselesaikan dengan mengimplementasikan expectation maximization pada aligned bitext tersebut. •
Expectation Maximization (EM)
Algoritme expectation maximization (EM) digunakan untuk menemukan korespondensi antara blob dengan kata. Notasi algoritme EM yang digunakan dalam penelitian ini diberikan pada Tabel 2 sedangkan algoritme EM beriterasi sesuai aturan berikut: E step: 1 Untuk setiap n = 1 ,…, N, j = 1 ,…, Mn, i = 1 ,…, Ln p '( anj = i | wnj , bni , θ
( new )
) = p ( anj = i )t ( wnj | bni )
2 Normalisasi p ' ( a nj = i | wnj , bni , θ (old ) ) untuk setiap citra n dan kata j untuk memperoleh p (anj = i | wnj , bni , θ ( old ) ) dengan cara:
6
p ( anj = i | wnj , bni , θ
sehingga
( new )
)=
p '( a nj = i | wnj , bni , θ
∑
Ln i =1
( new )
)
p ( anj = i )t ( wnj | bni )
∑ i =1 p(anj = i | wnj , bni ,θ ( new) ) = 1 . Ln
M step: 1 Untuk setiap pasangan berbeda (b*, w*) yang muncul bersamaan minimal pada salah satu citra, hitung: t ' ( wnj = w* | bni = b*,θ ( new) = L N
Mn Ln
L ∑∑∑ p (anj = i | wnj , bni ,θ ( new ) )δ ( w*,b*) ( wnj , bni ) n =1 n =1 i =1
dengan
δ ( w*,b*) ( wnj , bni ) bernilai 1 jika b*
dan w* muncul bersamaan pada salah satu citra n, bernilai 0(nol) selainnya.
Formulasi EM beriterasi untuk memaksimalkan log-likelihood QML dengan formula sebagai berikut: N
Mn Ln
Q ML = ∑∑∑ p (anj = i | wnj , bni , θ ( old ) ) log p (anj = i )t ( wnj | bni ) n =1 j =1 i =1
Formula tersebut dimaksimalkan dengan batasan ∑ i p ( anj = i ) = 1 untuk semua kata j di semua citra, dan ∑ w* t ( w* | b*) = 1
untuk
semua kata w* dan setiap blob b*. Pada awalnya, tabel peluang berisi frekuensi kemunculan bersama (co-occurence) antara kata dan blob, serta diasumsikan peluang alignment untuk tiap citra adalah sama. Kemudian, algoritme EM beriterasi untuk membentuk tabel translasi dengan nilai peluang tertentu seperti ilustrasi pada Gambar 5.
2 Normalisasi t '( wnj = w* | bni = b*) setiap citra n dan kata j untuk memperoleh t ( wnj = w* | bni = b*) dengan cara: t ( wnj | bni , θ ( new ) ) =
sehingga
t '( wnj | bni )
∑
Mn j =1
t '( wnj | bni )
∑ j =1t (wnj | bni ,θ (new) ) = 1 . Mn
Tabel 2 Notasi EM yang digunakan pada penelitian Notasi
N MT Mn wn w* LT Ln bn b* an
t(w|b) p(anj = i) θ
Deskripsi Jumlah seluruh citra Ukuran kosakata kata Jumlah kata untuk citra ke-n kata pada citra ke-n, wn = (wn1, … , wnMn,) kata tertentu Ukuran kosakata blob Jumlah blob pada citra ke-n blob pada citra ke-n blob tertentu Assignment an = {an1, … , anMn), anj = i jika bni berhubungan dengan wnj Peluang menerjemahkan (translasi) pada kata w jika diberikan blob b Peluang assignment Sekumpulan parameter model, θ = (p(anj=i), t(wnj|bni)), dengan p(anj=i|wnj, bni, θ(old)) sebagai indikator
Gambar 5 Proses pembentukan tabel translasi. Tabel translasi berisi peluang posterior untuk setiap blob terhadap seluruh kata (w) dalam kosakata, peluang bersyarat p(w|b) diberikan blob (b). Tabel peluang ini dinormalisasi agar jumlah peluang posterior untuk setiap blob b bernilai sama dengan satu. Peluang posterior kata p(w|b) digunakan untuk memprediksi kata pada data latih.
7
Evaluasi Anotasi Automatis Evaluasi model yang terbentuk pada tahap sebelumnya dilakukan menggunakan data uji. Data uji yang digunakan terdiri dari 250 citra beserta anotasi manual citra tersebut.
Proses pembentukan model LSI dilakukan melalui dua tahap seperti yang terlihat pada Gambar 7: 1
Anotasi automatis seluruh citra.
2
Pembentukan dimensi LSI.
Seperti pelatihan, pengujian dilakukan menggunakan tiga jenis data uji yang berbeda. Pengujian anotasi automatis dilakukan dengan menyegmentasi citra uji menjadi tiga jenis data uji dengan ukuran grid yang berbeda pada tahap tokenisasi. Ukuran grid yang digunakan yaitu 2×3, 4×6, dan 8×12. Pemilihan grid yang bervariasi ini bertujuan untuk mencari ukuran region optimal dalam pengujian model SMT ini. Metode yang digunakan untuk evaluasi anotasi automatis adalah algoritme normalized score terhadap hasil prediksi anotasi automatis citra uji yang dibandingkan dengan anotasi manualnya. Secara sederhana, evaluasi dilakukan sesuai Gambar 6 berikut:
Gambar 7 Pembentukan model LSI. Anotasi automatis dilakukan terhadap seluruh citra dengan menggunakan threshold terhadap peluang posterior kata hasil prediksi. Threshold yang diberikan yaitu nilai rataan dari total peluang posterior kata hasil prediksi. Prediksi kata yang memiliki peluang posterior lebih besar dari rataan tersebut akan menjadi kata anotasi automatisnya. Sebaliknya, kata yang memiliki peluang di bawah nilai threshold tersebut akan dibuang dari hasil anotasi automatis citra. Hal ini berarti nilai threshold untuk setiap citra memiliki nilai yang bervariasi.
Gambar 6 Evaluasi model SMT. Evaluasi dilakukan dengan formula normalized score dengan jumlah n = {1,..., M T } dengan MT adalah ukuran kamus kata dari seluruh anotasi data latih, yaitu sebesar 69 kata. Pembentukan Model LSI Pembentukan model LSI bertujuan membentuk dimensi semantik dari hasil anotasi automatis seluruh citra. Citra yang digunakan adalah citra latih dan citra uji yang digunakan pada tahap pembentukan model SMT sebelumnya tanpa menggunakan anotasi manual yang tersedia.
Implementasi LSI digunakan untuk mengeksploitasi makna semantik dari hasil anotasi seluruh citra. Evaluasi Hasil Temu Kembali Evaluasi hasil temu kembali dilakukan menggunakan dua kueri berbeda: klausa dan teks. Kueri klausa adalah klausa hasil anotasi automatis terhadap citra tertentu misalnya cloud dan mountain sebagai sebuah kueri. Kueri teks adalah kueri berupa satu buah kata yang diperoleh dari seluruh kosakata kata, misalnya cloud. Secara sederhana, proses evaluasi hasil temu kembali mengikuti alur seperti pada Gambar 8. Nilai evaluasi diperoleh dari perhitungan recall dan precision untuk kedua jenis kueri tersebut.
8
Parameter relevansi diperoleh dari anotasi manual seluruh citra latih dan citra uji.
basis data. Panjang anotasi setiap citra berkisar antara 1 – 7 kata menggunakan bahasa inggris. Data penelitian dibagi menjadi dua bagian, data untuk pembentukan model SMT dan pembentukan dimensi LSI seperti ilustrasi pada Lampiran 1. Data untuk pembentukan model SMT dibagi menjadi dua bagian: yaitu data untuk pelatihan (data latih) dan data untuk pengujian (data uji), dengan jumlah 750 dan 250 citra beserta anotasi manual dari citra yang bersangkutan. Data latih digunakan untuk membentuk model SMT, sedangkan data uji untuk mengevaluasi hasil anotasi automatis model SMT. Data yang digunakan untuk membentuk dimensi latent semantic indexing terdiri dari 1000 citra. Citra tersebut diperoleh dari citra latih dan citra uji pada data pembentukan model SMT. Pembentukan Data Latih
Gambar 8 Evaluasi hasil temu kembali. Perangkat Keras dan Perangkat Lunak yang Digunakan Perangkat lunak yang digunakan pada penelitian ini adalah Matlab 7.0.1 dan sistem operasi Windows XP, sedangkan spesifikasi perangkat keras yang digunakan adalah komputer dengan processor Intel Core 2 Duo 2.0 GHz dan memori 960 MB.
Data latih untuk pembentukan model SMT terdiri dari tiga jenis berdasarkan ukuran grid yang digunakan dalam segmentasi. Data latih A, B, dan C dengan ukuran grid sebesar 2×3, 4×6, dan 8×12 untuk seluruh citra latih (750 citra). Persiapan dilakukan dengan melakukan tokenisasi terhadap seluruh citra latih untuk setiap model secara terpisah seperti pada Gambar 9.
HASIL DAN PEMBAHASAN Penelitian ini mengimplementasikan anotasi automatis citra menggunakan model statistical machine translation (SMT) untuk temu kembali citra. Implementasi latent semantic indexing (LSI) pada hasil anotasi automatis dilakukan untuk memunculkan makna semantik dari suatu citra sehingga memberikan hasil yang relevan pada saat temu kembali. Data Penelitian Data penelitian yang digunakan berasal dari http://www.stat.psu.edu/~jiali sebanyak 1000 citra. Pemilihan citra dilakukan secara manual dengan dimensi seragam 384 × 256 piksel dengan variasi objek, tema, dan pencahayaan yang beragam. Data anotasi diperoleh dengan melakukan anotasi secara manual terhadap seluruh citra
Gambar 9 Proses pembentukan data latih dalam pembentukan model SMT. Masing-masing model akan menghasilkan jumlah blob yang berbeda, data latih A maksimal sebanyak 750 × (2 × 3) = 4500 blob,
9
data latih B sebanyak 18000 blob, dan data latih C sebanyak 72000 blob, dengan tiap blob berisi 26 ciri citra.
menyebar lebih seragam karena perilaku alami dari algoritme clustering yang menciptakan mereka (Jeon et al. 2003).
Pembentukan Model SMT
Setelah cluster untuk blob tercipta, cluster tersebut dapat dianggap sebagai kosakata bagi ciri blob hasil dari tokenisasi awal yang masih dalam bentuk ciri kontinu. Setiap ciri blob didiskretisasi dengan mengganti ciri blob tersebut (26×1) dengan indeks dari cluster yang merepresentasikan ciri tersebut (1×1).
Pembentukan model SMT untuk ketiga data latih menghasilkan tabel translasi yang sangat berbeda. Perbedaaan tersebut disebabkan oleh kemunculan bersama blob dan kata dari ketiga data latih, data latih A belajar dari 4500 blob, sedangkan B dan C belajar dari 18000 dan 72000 blob. Tabel translasi untuk ketiga data latih tersebut memiliki dimensi yang sama yaitu MT × k, dengan MT adalah jumlah kata dalam kosa kata sistem yaitu sebesar 69 dan k adalah jumlah kosakata blob yaitu sebanyak 500. • Tokenisasi Tokenisasi dilakukan melalui dua tahap. Pertama, ekstraksi ciri blob yang masih dalam bentuk ciri kontinu dilanjutkan dengan diskretisasi ciri tersebut. Kedua, ekstraksi kata dari setiap citra yang dilakukan dengan cara mewariskan seluruh anotasi citra tertentu kepada seluruh regionnya, sehingga setiap region akan mewarisi anotasi yang diberikan terhadap citra sumber Hal tersebut menyebabkan dimensi ciri kata untuk seluruh citra latih berukuran lebih kecil dan seragam yaitu sebesar 750×MT, dengan MT adalah ukuran dari kosakata kata yaitu sebesar 69 kata. Seluruh blob untuk setiap data latih dari dikelompokkan menggunakan k-means dengan k=500. Distribusi keanggotaan blob untuk setiap cluster menyebar dengan seragam sesuai algoritme yang menciptakannya (Jeon et al. 2003). Berbeda dengan distribusi blob yang lebih seragam, pengelompokkan kata dari seluruh citra terdistribusi secara menyebar dan tidak mengelompok pada indeks manapun seperti terlihat pada Lampiran 2. Frekuensi kemunculan tertinggi terjadi pada indeks kata ke-66 yaitu water dengan frekuensi sebesar 397 kali (13.98%) pada seluruh data dan 289 kali (13.68%) pada data latih. Frekuensi terkecil pada data latih terjadi pada indeks kata: 2, 7, 32, 33, 37, 47, 59, dan 61 dengan frekuensi sebanyak 1 kali, yaitu bench, bridge, lighthouse, mailbox, night view, railroad, stone, dan sun. Perbedaan perilaku distribusi kata ini disebabkan karena distribusi kata menyebar sesuai distribusi Zipfian, sedangkan blob
Ciri blob yang telah didiskretisasi selanjutnya akan direpresentasikan dalam bentuk vector space model dengan dimensi yang seragam yaitu 750×k untuk setiap data latih, dengan k=500 merupakan jumlah kosakata blob. •
Expectation Maximization (EM)
Pembentukan model SMT untuk seluruh data latih dilakukan dengan jumlah iterasi yang sama, yaitu sebanyak 1000 kali. Pemilihan jumlah 1000 karena pada iterasi tersebut, nilai QML yang dihasilkan tidak bertambah baik dan telah stabil. Model diambil dari iterasi dengan QML terbesar dari seluruh iterasi. Evaluasi Anotasi Automatis Perhitungan normalized score untuk seluruh data uji dilakukan untuk ketiga model yang terbentuk oleh masing-masing data latih yang ada dengan jumlah tebakan kata atau n = {1,..., 69} . Nilai pada Tabel 3 berikut merupakan hasil evaluasi nilai rataan ENS untuk seluruh data uji. Tabel 3 Rataan ENS untuk setiap data uji terhadap model hasil data latih
Data latih
Data uji
Rataan
A
B
C
A
0.5326
0.6306
0.5787
0.5806
B
0.3982
0.5971
0.6144
0.5366
C
0.4234
0.4299
0.3922
0.4152
Rataan
0.4514
0.5525
0.5284
Melihat grafik pada Gambar 10 dan nilai pada Tabel 3, terlihat bahwa rataan ENS untuk seluruh data uji terhadap seluruh data latih memiliki hasil yang cukup seragam. Nilai ENS tertinggi untuk pemodelan diperoleh oleh data latih A dengan rataan sebesar 0.5806, sedangkan rataan ENS tertinggi untuk pelatihan diperoleh oleh data uji B sebesar 0.5525.
10
Evaluasi ulang data latih A dengan nilai n yang diperkecil menghasilkan nilai normalized score yang tidak monoton seperti pada Gambar 12. Hal ini disebabkan oleh jumlah tebakan n masih lebih kecil dari jumlah kata yang memiliki peluang posterior yang tidak nol.
Gambar 10 Perbandingan nilai ENS hasil evaluasi. Grafik pada Gambar 11 menunjukkan bahwa nilai ENS pada data latih A dengan seluruh variasi grid uji mengalami stagnansi (monoton) pada nilai n sebesar 14, 27, dan 43 untuk grid uji 2×3, 4×6, dan 8×12. Stagnansi ini diakibatkan oleh terbatasnya jumlah kata dengan peluang posterior p(w|b) yang tidak nol untuk seluruh blob.
Gambar 12 Nilai ENS pada data latih A terhadap seluruh data uji dengan n yang diperkecil. Hasil performa normalized score untuk nilai n yang diperkecil tersebut kemudian dihitung ulang dengan hasil seperti pada Tabel 4 dan Gambar 13. Tabel 4 Rataan ENS untuk evaluasi ulang dengan nilai n yang diperkecil
Data latih
Gambar 11 Stagnansi pada perkembangan nilai ENS data latih A untuk nilai n = {1,..., 69} .
Data uji Rataan
A
B
C
A
0.4225
0.4792
0.4807
0.4608
B
0.3415
0.4291
0.5182
0.4296
C
0.3994
0.4828
0.4596
0.4473
Rataan
0.3878
0.4637
0.4862
Formula yang digunakan untuk evaluasi memiliki empat buah parameter yaitu N, na, r, dan w dengan jumlah tebakan sebesar n. Ukuran kosakata kata (N) dan panjang aktual anotasi citra (na) untuk nilai n yang beragam adalah konstan, sedangkan nilai n saat jumlah kata dengan p(w|b) yang tidak nol lebih kecil dari nilai n yang diharapkan akan menjadi konstan juga, sehingga stagnansi pun terjadi. Hal ini menunjukkan bahwa model tersebut tidak akan mengembalikan jumlah kata hasil anotasi automatis lebih besar dari jumlah kata yang peluangnya tidak nol. Melihat hasil yang di peroleh pada Tabel 3 dan perilaku ENS yang stagnantif, evaluasi ulang data uji perlu dilakukan. Evaluasi ulang dilakukan dengan nilai tebakan n yang diperkecil, yaitu n = {1,...,10} agar perbedaan hasil yang diperoleh menjadi lebih terlihat.
Gambar 13 Perbandingan nilai ENS untuk seluruh model. Hasil terbaik masih diperoleh oleh model SMT data latih A seperti yang terlihat pada Gambar 13. Yang menarik adalah rataan ENS untuk grid uji 8×12 mengalami penurunan tapi menjadi nilai ENS dengan rataan yang tertinggi
11
diantara dua grid uji lainnya, yaitu sebesar 0.4862.
tersebut akan automatisnya.
Hasil tersebut menunjukkan bahwa pembentukan model SMT untuk data yang digunakan pada penelitian ini akan optimal jika segmentasi dilakukan dengan ukuran grid 2×3. Adapun proses anotasi automatis sebaiknya dilakukan dengan cara menyegmentasi citra masukan dengan ukuran grid sebesar 8×12.
Hasil anotasi automatis seluruh citra digunakan sebagai deskripsi citra tersebut. Kemudian matriks kata-citra seluruh citra tersebut akan menjadi masukan dalam pembentukan dimensi LSI.
Contoh pada Gambar 14 memperlihatkan hasil anotasi automatis pada salah satu citra dengan jumlah n dibatasi yaitu n = 3 . Beberapa citra masih dianotasi dengan kualitas yang kurang baik jka nilai n tidak dibatasi seperti pada Gambar 15 dengan nilai ENS sebesar 0.5218. Secara keseluruhan, hasil anotasi automatis memberikan hasil yang cukup memuaskan.
menjadi
kata
anotasi
Hasil dekomposisi matriks kata-citra akan digunakan sebagai model LSI pada sistem temu kembali citra. Dimensi yang digunakan dalam LSI bukan dimensi seluruhnya, melainkan reduksi dimensi LSI dengan nilai k=10. Alasan pemilihan k ini yaitu karena pada nilai k tersebut nilai singular value dekomposisi matriks yang sudah cukup baik dan pada k > 10 tidak mengalami penurunan yang signifikan. Hal tersebut terlihat pada grafik singular value pada Gambar 16.
ENS : 1.00 Manual: water, ice, glacier
Automatis (3): glacier (0.170), ice (0.131), water (0.128) Gambar 14 Anotasi yang cukup baik model hasil data latih A dengan n = 3 .
ENS : 0.5218
Manual: snow, mountain, clear_sky, tree, water
Automatis (7): bird (0.270), grass (0.149), cloud (0.0986), tree (0.081), ground (0.066), water (0.0499), snow (0.037)
Gambar 15 Anotasi yang kurang baik model hasil data latih A dengan n = 7 . Pembentukan model LSI Dimensi LSI yang digunakan dalam pengujian berasal dari vektor kata hasil anotasi automatis seluruh citra sebanyak 1000 citra. Anotasi automatis dilakukan terhadap seluruh citra dengan menggunakan threshold terhadap peluang posterior kata hasil prediksi. Prediksi kata yang memiliki peluang posterior lebih besar dari rataan seluruh peluang posterior citra
Gambar 16 Nilai singular value matriks LSI pada beberapa nilai k. Evaluasi hasil temu kembali Evaluasi terhadap 1000 kueri citra (1000 klausa) dan 69 teks memiliki hasil yang cukup baik, seperti yang terlihat pada Tabel 5. Terlihat pada Gambar 17 bahwa rataan precision untuk kueri klausa jauh lebih baik dari kueri teks, sekitar dua kali lebih baik. Nilai rataan precision untuk kueri klausa yaitu sebesar 0.5442. Nilai tertinggi dicapai saat recall 0 dan 0.1, selanjutnya nilai rataan precision tersebut menurun secara perlahan. Nilai precision kueri klausa yang tinggi tersebut disebabkan oleh implementasi LSI pada proses temu kembali. Di sini terbukti bahwa metode LSI dapat memunculkan makna semantik yang ada pada anotasi automatis citra seperti yang terlihat pada hasil temu kembali pada Lampiran 3 dan Lampiran 4. Nilai rataan normalized score yang kurang baik pada anotasi automatis diperbaiki dengan metode LSI pada proses temu kembali. Kata yang hilang pada anotasi automatis dapat dimunculkan kembali pada proses temu kembali melalui metode LSI.
12
Tabel 5 Rataan recall dan precision untuk evaluasi hasil temu kembali
Recall
Precision
Implementasi LSI memiliki nilai recall dan precision yang cukup baik untuk kueri klausa. Rataan precision sebesar 0.544 untuk kueri klausa jauh melebihi rataan precision untuk kueri teks sebesar 0.251.
klausa
Teks
0
1.0000
1.0000
0.1
0.6194
0.2766
0.2
0.5808
0.2463
0.3
0.5591
0.2223
Nilai tersebut menunjukkan bahwa metode LSI dapat memunculkan makna semantik dari citra dengan cukup baik. Kata yang sempat hilang pada anotasi automatis dapat dimunculkan kembali pada proses temu kembali menggunakan metode LSI.
0.4
0.5400
0.1986
Saran
0.5
0.5205
0.1889
0.6
0.4976
0.1761
Berikut ini adalah penelitian lanjutan yang dapat dilakukan berkaitan dengan model statistical machine translation ini:
0.7
0.4690
0.1477
0.8
0.4358
0.1251
0.9
0.3978
0.0926
1
0.3657
0.0855
Rataan
0.5442
0.2509
1 Membandingkan dengan beberapa model sederhana lainnya seperti cross-media relevance models (Jeon et al. 2003). 2 Meneliti pemilihan ciri dan komposisinya dari region citra dalam grid yang dapat menghasilkan nilai temu kembali yang lebih baik. 3 Penggunaan data latih lainnya yang lebih bervariasi dan berjumlah lebih besar dengan anotasi manual yang memiliki tingkat semantik yang lebih tinggi. Anotasi yang diberikan mendeskripsikan konsep dari objek yang bersangkutan, seperti landscapes, indoor, outdoor, happy, dan sebagainya.
Gambar 17 Grafik recall dan precision untuk hasil temu kembali citra pada model LSI.
KESIMPULAN DAN SARAN Kesimpulan Penelitian ini menerapkan model statistical machine translation (SMT) untuk anotasi automatis citra. Penambahan metode latent semantic indexing (LSI) dalam proses temu kembali citra berguna untuk memunculkan makna semantik dari citra. Hasil percobaan dengan beberapa kombinasi parameter grid pada penelitian ini menunjukkan bahwa grid dengan ukuran 2×3 menghasilkan model SMT terbaik untuk data yang digunakan dalam penelitian ini, dengan rataan normalized score (ENS) sebesar 0.4608 terhadap seluruh kombinasi grid pada pengujian.
DAFTAR PUSTAKA Barnard K, Duygulu P, de Freitas N, Forsyth DA, Blei D, Jordan M. Matching words and pictures. Journal of Machine Learning Research, 3:1107-1135, 2003. Barnard K, Duygulu P, Guru R, Gabbur P, Forsyth D. 2003. The effects of segmentation and feature choice in a translation model of object recognition. Department of Computer Science, Arizona University, Tucson, AZ, USA. Belongie S, Carson C, Greenspan H, Malik J.1998. Color- and Texture-Based Image Segmentation Using EM and Its Application to Content-Based Image Retrieval. Computer Science Division, University of California at Berkeley, Berkeley, CA 94720. Black PE. Zipfian distribution. Dictionary of Algorithms and Data Structures. http://www.nist.gov/dads/HTML/zipfian.ht ml [1 Agustus 2008].
13
Brahmi D, Ziou D. 2004. Improving CBIR systems by integrating semantic features. In Proc. RIAO, 291–305, Vaucluse, France. Duygulu P, Ozcanli OC, Papernick N. Comparison of Feature Sets using Multimedia Translation. School of Computer Science, Carnegie Mellon University, Informedia Project, Pittsburg, PA, USA. Duygulu P. 2003. Translating Images to Words: A Novel Approach For Object Recognition [tesis]. Department of Computer Engineering, The Middle East Technical University. Ferdian E, Hadisaputra R, Madjid N. 2005. Penerapan Metode Latent Semantic Indexing pada Search Engine. Departement Teknik Informatika, Institut Teknologi Bandung. Garcia E. 2006. Latent Semantic Indexing (LSI) A Fast Track Tutorial. http://www.miislita.com/informationretrieval-tutorial/svd-lsi-tutorial-1understanding.html [1 Agustus 2008]. Grossman D. IR Book. www.ir.iit.edu/~dagr/ cs529/ ir_book.html [1 September 2008]. Han J, Ma KK. Fuzzy Color Histogram and Its Use in Color Image Retrieval. IEEE Transaction on Image Processing, vol. 11, no. 8, 2002. Inoue M. 2004. On the need for annotationbased image retrieval. National Institute of Informatics 2-1-2 Hitotsubashi, Chiyoda-ku. Tokyo, Japan. Jeon J, Lavrenko V, Manmatha R. 2003. Automatic Image Annotation and Retrieval using Cross-Media Relevance Models. Center for Intelligent Information Retrieval, Computer Science Department, University of Massachussets. Jia L. Photography image database for retrieval and automatic annotation. Pennsylvania State University. http://www.stat.psu.edu/~jiali [6 Maret 2008]. LACIE. Color Management White Paper 3:Color Spaces & Color Translation. www.lacie.com/download/whitepaper/wp_c olormanagement_3_en.pdf [1 Agustus 2008]. Mori Y, Takahashi H, Oka T. 1999. Image-toword transformation based on dividing and
vector quantizing images with words. In First International Workshop on Multimedia Intelligent Storage and Retrieval Management. Orlando, Florida. Shi J, Malik J. Normalized cuts and image segmentation. IEEE Transaction on Pattern Analysis and Machine Intelligence, 22(8):888-905, 2000. Tang J. 2008. Automatic Image Annotation and Object Detection [tesis]. Faculty of Engineering, Science and Mathematics, School of Electronics and Computer Science, University of Southampton.
14
LAMPIRAN
15
Lampiran 1 Skema pembagian data pada penelitian
16
Lampiran 2 Sebaran kata seluruh citra
17
Lampiran 3 Contoh hasil temu kembali menggunakan kueri teks
Kueri: water Hasil temu kembali:
Kueri: bird Hasil temu kembali:
18
Lampiran 4 Contoh hasil temu kembali menggunakan kueri klausa Citra : 0642.jpg
grid : 8×12
Anotasi automatis (5):
bird (0.337468), water(0.202484), rock (0.095246), plant(0.052229), tree (0.042005)
Hasil temu kembali:
