PELABELAN OTOMATIS CITRA MENGGUNAKAN FUZZY C MEANS UNTUK SISTEM TEMU KEMBALI CITRA
MARSANI ASFI
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2008
PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI Dengan ini saya menyatakan bahwa Tesis Pelabelan Otomatis Citra Menggunakan Fuzzy C-Means untuk Sistem Temu Kembali Citra, adalah karya saya sendiri dan belum diajukan dalam bentuk apapun kepada Perguruan Tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini.
Bogor, Juli 2008
Marsani Asfi NRP. G651050014
ABSTRAK MARSANI ASFI. Pelabelan Otomatis Citra menggunakan Fuzzy C-Means untuk Sistem Temu Kembali Citra. Dibimbing oleh Fahren Bukhari dan Yeni Herdiyeni.
Pelabelan citra secara manual memiliki kelemahan karena memerlukan waktu yang banyak dan sangat tergantung pada subjektifitas pengguna dalam mendeskripsikan citra. Oleh karena itu diperlukan pelabelan citra secara otomatis berdasarkan isi citra. Penelitian ini menggunakan Fuzzy C-Means untuk mengelompokkan informasi warna dan tekstur ke dalam beberapa region berdasarkan objek citra. Dari pengelompokkan ini diperoleh kamus kata untuk setiap citra. Dengan adanya kamus kata tersebut diharapkan dapat mempercepat proses temu kembali. Hasil penelitian menunjukkan bahwa nilai presisi temu kembali citra berdasarkan proses pelabelan ini mencapai 86.68 %.
Kata Kunci : citra, temu kembali citra, pelabelan otomatis citra, fuzzy c-means, clustering.
ABSTRACT
MARSANI ASFI. Automatic Image Labeling using Fuzzy C-Means for Image Retrieval Systems. Under the direction of Fahren Bukhari and Yeni Herdiyeni.
With the rapid development of digital photography, digital image data has increased tremendously in recent years. Consequently image retrieval has drawn the attention of many user. The need for manually image labeling, which is depends on user subjectivity and time-consuming, especially for image databases. This research propose an automatic image labeling based on image content using Fuzzy C-Means to cluster the color and texture information’s into regions. Label of image from clustering is used to retrieve image. The experiments results showed the average of precision of the proposed method is show 86.68 %. Keyword: Image, Content Based Image Retrieval, CBIR, automatic image labeling
RINGKASAN MARSANI ASFI. Pelabelan Otomatis Citra Menggunakan Fuzzy C Means untuk Sistem Temu Kembali Citra. Di bawah bimbingan Fahren Bukhari dan Yeni Herdiyeni. Perkembangan internet dan banyaknya aplikasi multimedia saat ini, menyebabkan pengguna sulit untuk mendapatkan citra yang tersimpan dalam komputer. Citra memiliki subjek dan objek citra. Subjek citra merupakan persepsi umum pengguna terhadap objek-objek yang dimiliki citra. Persepsi dan intepretasi pengguna dalam mendeskripsikan citra yang sama sering terdapat perbedaan. Pelabelan citra secara manual memiliki kelemahan karena memerlukan waktu yang banyak dan sangat tergantung pada subjektifitas pengguna dalam mendeskripsikan citra. Oleh karena itu diperlukan pelabelan citra secara otomatis berdasarkan isi citra. Citra sumber penelitian diperoleh dari web ALIPR (http://www.alipr.com). Citra sumber berhubungan dengan kelas pemandangan, bangunan, alam. Jumlah objek yang terkandung dalam citra dapat berisi 3 (tiga), 4 (empat) atau 5 (lima) objek. Citra sumber digunakan sebagai data pelatihan dan data pengujian. Data pelatihan digunakan sebagai data untuk pembentukan basis data ciri. Basis data ciri menjadi acuan untuk proses penemuan kembali citra pada saat diujikan. Data pengujian digunakan untuk pengujian pelabelan citra, sedangkan untuk pengujian temu kembali citra menggunakan kata-kata dalam kamus kata. Pengujian dengan kamus kata terdiri dari pengujian subjek citra serta objek-objek citra. Tahapan penelitian terdiri atas pengindeksan untuk pemilihan citra sumber, segmentasi citra, ektraksi warna dan tekstur, serta pengukuran kemiripan ciri subjek citra menggunakan Euclid. Pelabelan citra secara otomatis. Temu kembali citra untuk menentukan kueri teks sebagai masukan dan penentuan indeks yang digunakan sebagai dasar temu kembali citra. Evaluasi kinerja sistem sebagai evaluasi hasil temu kembali citra berdasarkan nilai precision dan recall. Penelitian ini menggunakan Fuzzy C-Means untuk mengelompokkan informasi warna dan tekstur ke dalam beberapa region berdasarkan objek citra. Dari pengelompokkan ini diperoleh kamus kata untuk setiap citra. Dengan adanya kamus kata tersebut diharapkan dapat mempercepat proses temu kembali. Hasil penelitian menunjukkan bahwa proses pelabelan otomatis citra menghasilkan pelabelan yang cukup baik. Definisi kata-kata berupa subjek dan objek citra dalam kamus kata berguna dalam proses temu kembali. Model pelabelan citra otomatis menggunakan Fuzzy C-means (FCM) dilakukan berdasarkan kata-kata yang terdefinisi dalam kamus kata. Tabel indeks citra disusun berdasarkan proses pelabelam otomatis citra dan digunakan sebagai dasar untuk proses temu kembali. Hasil penelitian juga menunjukkan bahwa nilai presisi temu kembali citra berdasarkan proses pelabelan ini mencapai 86.68 %. Kata Kunci : citra, temu kembali citra, pelabelan otomatis citra, fuzzy c-means, clustering.
© Hak cipta milik IPB, tahun 2008 Hak cipta dilindungi Undang-undang 1. Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumber. a. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik atau tinjauan suatu masalah b. Pengutipan tidak merugikan kepentingan yang wajar IPB 2. Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis dalam bentuk apapun tanpa izin IPB.
PELABELAN OTOMATIS CITRA MENGGUNAKAN FUZZY C MEANS UNTUK SISTEM TEMU KEMBALI CITRA
MARSANI ASFI
Tesis Sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Program Studi Ilmu Komputer
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2008
Judul Tesis Nama NRP
: Pelabelan Otomatis Citra Menggunakan Fuzzy C Means untuk Sistem Temu Kembali Citra : Marsani Asfi : G651050014
Disetujui Komisi Pembimbing
Ir. Fahren Bukhari, M.Sc Ketua
Yeni Herdiyeni, S.Si, M.Kom Anggota
Diketahui
Ketua Program Studi Ilmu Komputer
Dekan Sekolah Pascasarjana
Dr. Sugi Guritman
Prof. Dr. Khairil Anwar A. Notodiputro, M.S.
Tanggal ujian: 24 Juli 2008
Tanggal lulus:
PRAKATA Alhamdulillahirabbil ‘alamin, Penulis panjatkan puji dan syukur ke hadirat Allah SWT yang telah memberikan rahmat, hidayah, serta karuniaNya sehingga Penulis dapat menyelesaikan tesis yang berjudul Pelabelan Otomatis Citra menggunakan Fuzzy C-Means untuk Sistem Temu Kembali Citra. Penulis mengucapkan terima kasih kepada Bapak Ir. Fahren Bukhari, M.Sc. dan Ibu Yeni Herdiyeni S.Si, M.Kom selaku komisi pembimbing yang telah memberikan banyak masukan kepada Penulis dalam penyusunan tesis ini. Ucapan terimakasih juga Penulis sampaikan kepada Bapak Ir. Julio Adisantoso, M.Kom sebagai dosen penguji. Penulis juga ingin mengucapkan terima kasih kepada: 1. Ayah (alm) dan Ibu tercinta yang selalu mendukung kelancaran masa studi Penulis. 2. Bapak Chandra Lukita, S.E, M.M. dan Keluarga yang memberikan dukungan materi dan semangat pada saat kuliah dan penyusunan tesis ini. 3. Istri tercinta Erna Agustriani, yang mendukung, mendampingi dan selalu memberikan motivasi dan doa. Banyak yang telah kita korbankan selama ini. 4. Rekan rekan dosen dan staf di CIC serta rekan-rekan ‘ilkomp 7’ IPB : Agus Hasim, Dwi Prasetyo, Prihastuti Harsani, Titi Ratnasari, Diah Widiastuti, Adhi Kusnadi, Roni Salambue, Husmul Beze dan Sahzam. Sukses selalu. 5. Departemen Ilmu Komputer beserta dosen dan staf yang telah banyak membantu Penulis dalam penyusunan tesis ini. 6. Kepada semua pihak yang telah membantu dalam penyusunan tesis ini yang tidak bisa disebutkan satu per satu, terima kasih. Semoga penelitian ini dapat memberikan manfaat, Amien.
Bogor, Juli 2008 Marsani Asfi
RIWAYAT HIDUP Penulis dilahirkan di Bangka pada tanggal 01 Maret 1976 dari ayah Aslah Tamin (alm.) dan Ibu Fatimah. Penulis merupakan putra kedua dari enam saudara. Penulis beristrikan Erna Agustriani, A.md. Pendidikan sekolah dasar ditempuh di SDN 1 Sungailiat Bangka, menengah pertama di SMPN 1 Sungailiat Bangka. Menengah atas di SMAN 1 Sungailiat Bangka dan lulus tahun 1994, pada tahun yang sama penulis masuk Universitas Padjadjaran Bandung. Lulus dari jurusan Matematika Bidang Minat Ilmu Komputer tahun 1999. Saat ini penulis bekerja di CIC GROUP CIREBON sebagai Kepala Manajemen Mutu.
DAFTAR ISI Halaman DAFTAR TABEL ......................................................................................... xi DAFTAR GAMBAR...................................................................................... xii DAFTAR LAMPIRAN ................................................................................. xiv I. PENDAHULUAN A. Latar Belakang ..................................................................................... 1 B. Tujuan Penelitian ................................................................................. 3 C. Manfaat Penelitian ............................................................................... 3 D. Ruang Lingkup Penelitian ................................................................... 3 II. TINJAUAN PUSTAKA A. Temu Kembali Citra ............................................................................ 4 B. Segmentasi, Ekstraksi Ciri Citra dan Clustering ................................. 5 Normalized Cuts ............................................................................... 5 Expectation-Maximation .................................................................. 7 Ekstraksi Ciri Tekstur ...................................................................... 7 Transformasi Wavelet Gabor ........................................................... 8 Filter Gabor ..................................................................................... 9 Ekstraksi Ciri Warna ........................................................................ 11 Clustering ......................................................................................... 12 C. Fuzzy C-Means(FCM) ......................................................................... 13 D. Metodologi Pelabelan Otomatis Citra ................................................ 16 E. Pengukuran Kinerja Sistem ................................................................. 16 III. METODOLOGI PENELITIAN A. Kerangka Pemikiran............................................................................. 18 B. Alat Bantu Prnelitian ........................................................................... 19 C. Tata Laksana Penelitian ....................................................................... 19 Pengindeksan ...................................................................................... 19 Pelabelan Citra ..................................................................................... 23 Temu Kembali Citra ............................................................................ 24 Evaluasi Kinerja Sistem ...................................................................... 25
IV. PERANCANGAN DAN IMPLEMENTASI SISTEM A. Desain Data .......................................................................................... 26 Citra Sumber .................................................................................... 26 Kamus Kata ...................................................................................... 27 B. Desain Proses Sistem ............................................................................ 27 Segmentasi Citra ............................................................................... 28 Ekstraksi Ciri ................................................................................... 28 C. Perancangan Proses Sistem .................................................................. 29 Modul Segmentasi ............................................................................ 29 Modul Clustering ............................................................................. 30 Modul Pelabelan Citra ..................................................................... 31 Modul Temu Kembali ...................................................................... 32 Modul Evaluasi ................................................................................ 32 Modul Representasi Hasil ................................................................ 32 D. Desain Antar Muka .............................................................................. 32 V. HASIL DAN PEMBAHASAN A. Karakteristik Citra Masukan ................................................................ 34 B. Pengindeksan Citra ............................................................................... 34 Segmentasi Warna Citra ................................................................... 34 Format Tekstur Citra ........................................................................ 35 Segmentasi Region ........................................................................... 36 Ekstraksi Ciri Warna ........................................................................ 37 Ekstraksi Ciri Tekstur ...................................................................... 38 Penggabungan Ciri Warna dan Tekstur ........................................... 39 C. Pelabelan Citra ..................................................................................... 39 Labeling Capture ............................................................................. 39 Labeling Coding ............................................................................... 40 Labeling Reuse ................................................................................. 41 D. Hasil Temu Kembali ............................................................................ 43 E. Evaluasi Temu Kembali ....................................................................... 44 F. Pengembangan Prototype ..................................................................... 46 Antar Muka Menu Utama Sistem dan Pelabelan Citra .................... 46
Antar Muka Temu Kembali Citra .................................................... 47 VI. SIMPULAN DAN SARAN A. Simpulan .............................................................................................. 48 B. Saran ..................................................................................................... 48 DAFTAR PUSTAKA ................................................................................... 50 LAMPIRAN ................................................................................................... 53
DAFTAR TABEL Halaman 1 Enam parameter filter Gabor ................................................................................ 10 2 Kamus Kata.........................................................................................................
27
3 Matrik Keanggotaan ............................................................................................. 30 4 Subjek, Jumlah, serta Objek yang terkandung pada Citra Sumber......................
34
5 Matrik Keanggotaan Region berdasarkan hasil clustering ................................... 40 6 Nilai rataan precision hasil temu kembali citra ..................................................
xi
45
DAFTAR GAMBAR Halaman 1 Alur Sistem Temu Kembali Citra ……………………………………….............
4
2 Citra sebagai suatu graf dalam Normalized Cuts ..................................................
5
3 Grap Citra setelah di Segmentasi ........................................................................
6
4 Ilustrasi Pemotongan dalam Normalized Cuts .....................................................
6
5 Contoh tekstur visual dari Album Tekstur Brodatz ..............................................
8
6 Parameter filter Gabor dalam domain frekuensi spasial .......................................
9
7 Tahapan Segmentasi Tekstur ............................................................................... 11 8 Tahapan Algoritma fuzzy c-mean Clustering ....................................................... 15 9 Kerangka Pemikiran Penelitian ..........................................................................
18
10 Tata Laksana Pengindeksan..................................................................................
19
11 Ekstraksi ciri warna .............................................................................................
21
12 Ekstraksi ciri tekstur ............................................................................................
23
13 Tata Laksana Pelabelan Otomatis........................................................................
24
14 Tata Laksana Temu Kembali Citra ....................................................................... 24 15 Arsitektur Sistem Pelabelan Otomatis ................................................................
29
16 Rancangan Antar Muka Pelabelan Citra ............................................................... 33 17 Rancangan Desain Antarmuka Sistem Temu Kembali ......................................... 33 18 Contoh Citra sebelum dan sesudah segmentasi menggunakan algoritma EM ...
35
19 Contoh Citra RGB ke Citra Gray Scale ................................................................ 36 20 Contoh Citra sebelum dan sesudah segmentasi menggunakan algoritma ............ 36 21 Pemisahan Region Citra kedalam 6 Region.........................................................
37
22 Contoh Citra Langit .............................................................................................. 37 23 Hasil FCH dengan FCM 30 bin ............................................................................ 38 24 Contoh Citra Region Rumput ............................................................................... 38 25 Region Rumput dengan frekuensi tertentu ............................................................ 39 26 Grafik Total Cluster per Subjek ............................................................................ 40 27 Citra Contoh Proses Labeling Coding ................................................................... 41 28 Contoh Citra proses penggabungan region............................................................ 42 29 Contoh Citra hasil pelabelan otomatis .................................................................. 42
xii
30 Hasil Temu Kembali Citra dengan kata kunci ‘awan’ dan ‘ rumput’.................... 44 31 Grafik rataan precision dan recall ......................................................................... 45 32 Antar Muka Sistem dan Pelabelan Citra................................................................ 46 33 Antar Muka Temu Kembali Citra.......................................................................... 47
xiii
DAFTAR LAMPIRAN Halaman 1 Segmentasi Warna Citra Sumber .......................................................................... 53 2 Segmentasi Region Citra Sumber ......................................................................... 54 3 Warna Kuantisasi untuk 30 Bin Histogram .......................................................... 55
xiv
I. PENDAHULUAN
A. Latar Belakang Perkembangan internet dan banyaknya aplikasi multimedia saat ini, menyebabkan pengguna sulit untuk mendapatkan citra yang tersimpan dalam komputer. Citra memiliki subjek dan objek citra. Subjek citra merupakan persepsi umum pengguna terhadap objek-objek yang dimiliki citra. Pada citra dengan subjek pemandangan, identifikasi objek yang dimiliki citra dapat berupa awan, rumput atau objek lainnya. Setelah menghubungkan satu objek dengan objek yang dimiliki citra, maka pengguna dapat melakukan penafsiran (interpretation)
citra.
Persepsi
dan
intepretasi
pengguna
dalam
mendeskripsikan citra yang sama sering terdapat perbedaan. Oleh karena itu, perlu dikembangkan metode pencarian citra sehingga mempermudah pencarian data. Pencarian citra dapat dilakukan berdasarkan karakteristik visual citra berupa warna, bentuk dan tekstur yang disebut Content-Based Image Retrieval (CBIR). Pencarian berdasarkan karakteristik visual citra memiliki keuntungan dimana hasil pencarian sangat sesuai dengan persepsi pengguna terhadap citra yang dimaksud. Pencarian dengan teknik ini ternyata memiliki kekurangan yaitu membutuhkan waktu yang lama untuk pemrosesan awal. Karakteristik visual citra masukan berupa warna, tekstur ataupun bentuk harus diekstraksi terlebih dahulu. Pencarian lain dapat dilakukan menggunakan teks sebagai kata kunci pencarian. Keuntungan pencarian berbasis teks adalah waktu yang lebih singkat untuk menampilkan hasil dibandingkan pencarian berbasis citra. Kekurangan dari teknik ini adalah pemberian informasi tekstual untuk setiap citra dilakukan secara manual, untuk jumlah citra yang banyak sangat membutuhkan waktu. Kesalahan deskripsi sangat mungkin terjadi sehingga hasil pencarian tidak sesuai dengan persepsi awal pengguna. Pelabelan otomatis citra dilakukan untuk objek-objek yang dimiliki citra. Pelabelan otomatis citra dalam beberapa penelitian pernah dilakukan diantaranya dalam penelitian Mori et.al. (1999) yang melakukan cluster citra dengan membentuk sub-sub citra (dekomposisi citra berbasis blok) dan
2
menghitung frekuensi kata untuk masing-masing cluster. Duygulu et. al. (2002) melakukan metode translasi kumpulan-kumpulan blob yang terbentuk dari hasil segmentasi. Segmentasi otomatis dilakukan untuk mendapatkan vektor ciri, kemudian pengklasteran blob-blob yang terbentuk. Suatu citra terbentuk atas blob-blob dan kata-kata diasosiasikan dengan blob tersebut. Proses pengasosian ini menggunakan metode Expectation Maximization sehingga diperoleh suatu label baru untuk blob tersebut. Selanjutnya Lavrenko et. al. (2003) menggunakan metode CRM (Continuous-space Relevance Model) untuk melakukan pelabelan citra serta menggunakan
algoritma
smoothed
KNN.
Ciri-ciri
citra
dimodelkan
menggunakan kernel-based density dan segmentasi otomatis citra dilakukan berdasarkan ciri warna, tekstur dan bentuk. Ciri-ciri kata yang digunakan dimodelkan menggunakan distribusi multinomial. Kemudian Feng et. al. (2004) menggunakan metode CRM-rect. Penelitian Feng et. al. (2004) sama dengan penelitian Lavrenko et. al. (2003) tetapi metode CRM yang digunakan adalah dengan mendekomposisi blok-blok citra. Feng et. al. (2004) juga menggunakan MBRM (Multiple-Bernoulli Relevance Model) yaitu metode yang sama dengan CRM-rect dimana ciri-ciri kata yang digunakan dimodelkan dengan MBRM. Penelitian lain adalah dengan menerapkan hirarki teks sebagai bentuk teks ontologi, pemetaan teks ke citra dilakukan dengan kamus visualisasi yang terbentuk secara hirarki Srikanth et. al.(2005). Penelitian lain berkaitan dengan pelabelan citra yaitu pelabelan otomatis terhadap 50 (lima puluh) citra yang mengandung teks dari web Yahoo!News. Proses awal dilakukan dengan mendeteksi dan mengklasifikasi semua entitas teks berupa orang dan objek yang ada, kemudian dibandingkan dengan teks yang dominan dan terlihat secara visual Deschacht (2007). Oleh karena itu kecepatan dalam pencarian berbasis teks serta kesesuaian hasil temu kembali pada pencarian berbasis citra saat proses temu kembali
melatarbelakangi
penelitian
ini.
Selain
itu,
penelitian
ini
dikembangkan untuk mendapatkan definisi citra yang berkaitan dengan subjek dan objek citra. Metode pelabelan yang digunakan adalah menggunakan Fuzzy C-Means (FCM). Penelitian ini diharapkan dapat menghasilkan kualitas yang
3
lebih baik dalam pencarian citra berdasarkan semantik objek (Schober et. al., 2004). Fokus penelitian ini adalah pada pelabelan citra sehingga dapat digunakan untuk dasar proses temu kembali citra. B. Tujuan Penelitian Penelitian ini bertujuan untuk : 1. Mendefinisikan kata-kata yang merepresentasikan subjek dan objek citra. 2. Membuat model pelabelan citra menggunakan Fuzzy C-means (FCM) secara otomatis berdasarkan kata-kata yang telah didefinisikan. 3. Membuat tabel indeks citra berdasarkan pelabelan otomatis citra.
C. Manfaat Penelitian Manfaat penelitian ini diharapkan mempercepat proses pencarian citra berdasarkan proses pelabelan citra.
D. Ruang Lingkup Penelitian Ruang lingkup penelitian ini mencakup : 1. Objek penelitian adalah citra berwarna. 2. Segmentasi citra berbasis region. 3. Ekstraksi ciri berdasarkan tekstur dan warna. 4. Pelabelan citra secara otomatis berdasarkan tabel indeks citra. 5. Subjek citra terdiri dari subjek pemandangan, alam dan bangunan. 6. Kueri citra berbasis teks.
II. TINJAUAN PUSTAKA A. Temu Kembali Citra Temu kembali citra adalah salah satu metodologi untuk penemuan kembali citra berdasarkan isi (content) citra. Citra memiliki informasi karakteristik visual berupa warna, bentuk, tekstur, dan karakteristik spasial. Karakteristik visual tersebut diproses melalui ekstraksi ciri, sehingga diperoleh ciri-ciri citra. Hasil ekstraksi ciri tersebut kemudian disusun dalam vektor-vektor ciri multi dimensi. Vektor ciri dari citra disusun sebagai basis data ciri (Long et. al., 2003).
Gambar 1. Frame work Sistem Temu Kembali Citra (Hua et. al., 2008). Alur sistem temu kembali citra pada Gambar 1 diawali dengan masukan dalam bentuk kueri masukan untuk sistem. Citra masukan yang memiliki karakteristik visual berupa warna, bentuk ataupun tekstur selanjutnya diekstraksi sehingga diperoleh data-data ciri dalam bentuk vektor ciri. Citracitra dalam basis data yang memiliki karakteristik visual citra juga diekstraksi karakteristiknya kemudian disusun dalam vektor-vektor ciri. Kumpulan vektor-vektor ciri disimpan menjadi basis data ciri. Basis data ciri dan vektor ciri
dari
kueri
masukan
kemudian
dihitung
kemiripannya.
Proses
pengindeksan dilakukan untuk mempermudah proses temu kembali. Hasil temu kembali selanjutnya dapat dilakukan evaluasi melalui relevance
5
feedback, begitu juga untuk kueri masukan, karakteristik visual citra dan vektor ciri yang terbentuk (Long et. al., 2003).
B. Segmentasi, Ekstraksi Ciri Citra dan Clustering Secara umum, segmentasi merupakan langkah awal dalam analisis citra. Segmentasi dilakukan untuk membagi citra ke dalam bagian-bagian yang memiliki kemiripan karakteristik (Gonzales & Woods, 2002).
Normalized Cuts Metode Normalized Cuts menerapkan teori graf untuk membagi citra ke dalam ukuran terbaik. Dalam Gambar 2 citra dalam Normalized Cuts dipandang sebagai suatu graf yang saling berhubungan secara penuh (Fullyconnected graph). Setiap piksel merupakan node untuk graf. Hubungan menyatakan keterkaitan dalam graf antara pasangan piksel yang dinotasikan dengan p dan q. Masing-masing edge memiliki biaya C pq (Shi & Malik, 2000).
Gambar 2. Citra sebagai suatu graf dalam Normalized Cuts. Proses segmentasi citra berdasarkan graf adalah proses memecah grafgraf menjadi suatu segmen (Gambar 3). Proses tersebut dilakukan dengan
6
menghapus semua edge yang memotong di antara segmen citra atau edge-edge yang memiliki biaya terkecil. Semua piksel yang memiliki kemiripan akan digabungkan dalam segmen yang sama (Shi & Malik, 2000).
Gambar 3. Graf Citra setelah di Segmentasi. Proses pemotongan edge dilakukan untuk membuat graf-graf tersebut menjadi tidak terhubung (Gambar 4). Nilai biaya pemotongan edge dinyatakan dengan persamaan (1) (Shi & Malik, 2000) : Cut ( A , B ) =
∑
C
p∈ A ,q∈ B
p ,q
(1)
Gambar 4. Ilustrasi Pemotongan dalam Normalized Cuts Proses pemotongan graf dilakukan untuk menghasilkan segmen terbesar. Dalam normalized cuts (Ncut) proses pemotongan ini diperbaiki dengan menormalkan ukuran dari segmen dengan cara menggunaakan persamaan (2) (Shi & Malik, 2000) :
7
Ncut ( A, B ) =
Cut ( A, B ) Cut ( A, B) + volume ( A) volume( B)
(2)
dengan volume(A) dan volume(B) adalah jumlah biaya untuk semua edge yang ada dalam segmen A dan segmen B. Expectation-Maximization Expectation-Maximization (EM) adalah salah satu metode optimisasi untuk mencari dugaan parameter maximum likelihood ketika ada data yang hilang atau tidak lengkap. Di dalam algoritma EM, dilakukan perhitungan dugaan kemungkinan untuk mengisi data yang tidak lengkap (E-step) dan perhitungan dugaan parameter maximum likelihood dengan memaksimalkan dugaan kemungkinan yang diperoleh dari E-step (M-step). 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).
Ekstraksi Ciri Tekstur Tekstur merupakan karakteristik intrinsik dari suatu citra yang terkait dengan tingkat kekasaran (roughness), butiran (granulation), dan keteraturan (regularity) susunan struktural piksel. Aspek tekstural dari sebuah citra dapat dimanfaatkan sebagai dasar dari segmentasi, klasifikasi, maupun interpretasi citra (Gonzales & Woods, 2002). Tekstur dicirikan sebagai distribusi dari derajat keabuan piksel-piksel yang bertetangga. Tekstur tidak dapat didefinisikan hanya melalui sebuah piksel, tapi harus dalam sekumpulan piksel. Resolusi citra yang diamati dapat ditentukan oleh tekstur citra tersebut. Apabila resolusi atau skala meningkat, tekstur yang diamati akan berubah dari tekstur halus (fine) menjadi tekstur kasar (coarse) (Gonzales & Woods, 2002). Tekstur dapat didefinisikan sebagai fungsi dari variasi spasial intensitas piksel (nilai keabuan) dalam citra. Berdasarkan strukturnya, tekstur dapat diklasifikasikan dalam dua golongan :
8
1. Makrostruktur Tekstur makrostruktur memiliki perulangan pola lokal secara periodik pada suatu daerah citra, biasanya terdapat pada pola-pola buatan manusia dan cenderung mudah untuk direpresentasikan secara matematis. 2. Mikrostruktur Pada tekstur mikrostruktur, pola-pola lokal dan perulangan tidak terjadi begitu jelas, sehingga tidak mudah untuk memberikan definisi tekstur yang komprehensif. Gambar 5 menunjukkan perbedaan tekstur makrostruktur dan mikrostruktur yang diambil dari album tekstur Brodatz (Brodatz, 1966).
Gambar 5. Contoh tekstur visual dari Album Tekstur Brodatz. makrostruktur Bawah: mikrostruktur
Atas:
Transformasi Wavelet Gabor Pendekatan umum dalam melakukan analisa citra adalah penggunaan fungsi Fourier untuk menarik ciri citra sehingga diperoleh distribusi ciri energi global sinyal sebagai fungsi terhadap frekuensi. Ciri global tidak dapat menarik karakteristik sebagian citra. Oleh karena itu diperlukan ciri lokal yang dapat dinyatakan dalam frekuensi lokal. Frekuensi lokal ini menggunakan fungsi wavelet (Daubechies, 1995). Wavelet adalah fungsi matematika yang membagi data (sinyal) ke dalam komponen-komponen frekuensi yang berbeda. Salah satu fungsi wavelet adalah Gabor. Transformasi Wavelet menggunakan pendekatan penyaring multikanal (mutichannel filtering), dengan fungsi Gabor sebagai penyaring (filter) (Daubechies, 1995).
9
Filter Gabor Filter Gabor merupakan salah satu filter yang mampu mensimulasikan karakteristik sistem visual manusia dalam mengisolasi frekuensi dan orientasi tertentu citra. Karakteristik ini membuat filter Gabor sesuai untuk aplikasi pengenalan tekstur dalam computer vision (Seo, 2006). Secara spasial, sebuah fungsi Gabor merupakan sinusoida yang dimodulasi oleh fungsi Gauss. Respon impuls sebuah filter Gabor kompleks dua dimensi adalah menggunakan persamaan (3) (Seo, 2006 ): h ( x, y ) =
1 2πσ xσ y
⎧⎪ 1 ⎡ x 2 y 2 ⎤ ⎫⎪ exp ⎨− ⎢ 2 + 2 ⎥ ⎬(2πjFx) ⎪⎩ 2 ⎣⎢ σ x σ y ⎥⎦ ⎪⎭
(3)
dengan σ x dan σ y merupakan standar deviasi fungsi Gauss x dan y. Dalam domain frekuensi spasial, parameter-parameter filter Gabor dapat digambarkan seperti pada Gambar 6.
Gambar 6. Parameter filter Gabor dalam domain frekuensi spasial Ada enam parameter yang harus ditetapkan dalam implementasi filter Gabor (Tabel 1). Keenam parameter tersebut adalah: F , θ , σ x , σ y , B F , dan Bθ . 1. Frekuensi (F) dan orientasi (θ) mendefinisikan lokasi pusat filter. 2. BF dan Bθ menyatakan konstanta lebar pita frekuensi dan jangkauan angular filter.
10
3. Variabel σx berkaitan dengan respon sebesar -6 dB untuk komponen frekuensi spasial. Nilai variabel σx dapat dinyatakan dalam persamaan (4). ln 2 (2 BF + 1)
σx =
(4)
2πF (2 BF − 1)
4. Variabel σy berkaitan dengan respon sebesar -6dB untuk komponen angular. Nilai Variabel σy dapat dinyatakan dalam persamaan (5).
σy =
ln 2
(5)
2πF tan( Bθ / 2)
5. Posisi (F, θ) dan lebar pita (σx, σy) dari filter Gabor dalam domain frekuensi harus ditetapkan dengan cermat agar dapat menangkap informasi tekstural dengan benar. Frekuensi tengah dari filter kanal harus terletak dekat dengan frekuensi karakteristik tekstur. 6. Setelah mendapatkan ciri Gabor maka dapat dilakukan ekstraksi ciri. Salah satu ciri yang dapat dipilih adalah ciri energi, yang didefinisikan dalam persamaan (6). 1 e( x ) = MN
M
N
∑∑ x(m, n)
2
(6)
i =1 j =1
Enam parameter filter Gabor beserta nilainya seperti pada tabel 1. Tabel 1. Enam parameter filter Gabor Parameter Frekuensi tengah
Simbol
Nilai
F
(ternormalisasi)
2 2
0
,
2 2 2 2 2 2 , , , , 21 2 2 2 3 2 4 2 5 2 6
Lebar pita frekuensi
BF
1 oktaf
Lebar pita angular
Bθ
30 atau 45
Spacing frekuensi
SF
1 oktaf
Spacing angular
Sθ
30 atau 45
Orientasi
θ
Sθ = 30 : 0 , 30 , 60 , 90 , 120 , 150
B
B
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
Sθ = 45 : 0 , 45 , 90 , 135 , 180 , 225
11
Algoritma segmentasi tekstur menggunakan wavelet Gabor dilakukan melalui tahapan berikut (Seo, 2006) : 1. Mendekomposisi citra masukan menggunakan filter bank, 2. Mengekstraksi ciri, dan 3. Clustering. Alur segmentasi tekstur terlihat seperti pada Gambar 7. Citra Sumber Filter Gabor Filter Citra Ekstraksi Ciri Ciri Citra Clustering Citra Segmentasi
Gambar 7. Tahapan Segmentasi Tekstur (Seo, 2006)
Ektraksi Ciri Warna Setiap piksel mempunyai warna yang dapat dinyatakan dalam Red, Green dan Blue (RGB). Nilai RGB ini merupakan gabungan nilai R, nilai G dan nilai B yang tidak bisa dipisahkan satu dengan lainnya. Hal ini dapat dituliskan dengan P(r,g,b). Ekstraksi ciri warna merupakan salah satu cara untuk menentukan arti fisik suatu citra melalui proses pengindeksan warna. Proses ini bisa dilakukan dengan pendekatan histogram warna (Belongie et. al., 1998). Histogram warna merupakan representasi peluang keberadaan setiap warna dalam sebuah citra. Banyaknya nilai warna (bin) ditetapkan sesuai kebutuhan pembuatan histogram. Dengan bin sejumlah n, maka histogram warna untuk citra I yang mengandung N piksel dapat dirumuskan seperti H ( I ) = [h1 , h2 ,..., hn ] dengan persamaan (7).
12
hi =
1 N ∑ P , N j =1 i| j
(7)
⎧1; piksel j terkuanti sasi ke bin ke - i Pi| j = ⎨ . ⎩0; selainnya Histogram warna seperti ini disebut juga conventional color histogram (CCH) (Han & Ma, 2002).
Clustering Proses Clustering adalah proses pengelompokan data ke dalam cluster berdasarkan parameter tertentu sehingga objek-objek dalam sebuah cluster memiliki tingkat kemiripan yang tinggi satu sama lain dan sangat tidak mirip dengan obyek lain pada cluster yang berbeda (Kantardzic, 2001). Pada clustering tidak diperlukan kelas yang telah didefinisikan sebelumnya atau kelas hasil training, sehingga clustering dapat dinyatakan sebagai bentuk pembelajaran berdasarkan observasi dan bukan berdasarkan contoh (Jiawei et. al., 2001). Proses clustering dilakukan sebagai tahapan terakhir dari segmentasi warna dan tekstur dari vektor-vektor ciri. Clustering secara umum memiliki tahapan sebagai berikut (Jain et. al., 1999) : 1. Representasi pola 2. Pengukuran kedekatan pola (Pattern Proximity) 3. Clustering 4. Abstraksi data (jika dibutuhkan) 5. Penilaian output (jika dibutuhkan). Jarak Euclidean Kedekatan pola diukur berdasarkan fungsi jarak antara dua ciri. Jarak digunakan untuk mengukur ketidakmiripan antara dua obyek data. Bila p dan q menyatakan piksel dengan koodinat (x,y) dan (s,t) maka jarak euclidean antara p dan q adalah seperti persamaan (8) (Gonzales & Woods, 1992).
D E ( p, q ) =
( x − s) 2 + ( y − t ) 2
(8)
13
C. Fuzzy C-Means (FCM) Fuzzy C-Mean Clustering (FCM) juga dikenal sebagai fuzzy ISODATA. Pengelompokan setiap titik data dalam sebuah cluster ditentukan oleh derajat keanggotaannya. Bezdek mengusulkan algoritma ini tahun 1973 sebagai pengembangan awal dari hard C-mean (HCM) clustering (Jang et. al., 1997). FCM membagi sebuah koleksi ke-n dari vektor xi, dengan i = 1,2,3,...,n ke dalam c grup fuzzy dan mencari pusat cluster pada masing-masing grup yakni fungsi biaya dari ukuran ketidakmiripan yang paling minimal. Fuzzy c mean memiliki dua proses yakni menghitung pusat cluster dan menandai poin untuk pusat cluster menggunakan sebuah jarak euclidean. Proses ini dilakukan berulang hingga pusat cluster stabil. Keberadaan setiap titik data pada FCM dalam suatu cluster ditentukan oleh derajat keanggotaan antara 0 hingga 1 (Jang et. al., 1997 dan Cox, 2005). Untuk mengakomodasi fuzzy partisi, keanggotaan matrik U harus memiliki nilai antara 0 dan 1 (Jang et. al., 1997 dan Pedrycz, 2005). Normalisasi penetapan hasil derajat keanggotaan dari set data menggunakan persamaan (9). c
∑u i =1
ij
= 1, ∀ j = 1,2,3,..., n
(9)
dengan µij adalah derajat keanggotaan point data terhadap pusat-pusat cluster, C adalah jumlah cluster C, serta n adalah jumlah data. Fungsi objektif pada fuzzy c-mean digunakan persamaan (10). c
c
J (U , c1 ,..., cc ) = ∑ J i = ∑ i =1
i =1
n
∑u
m ij
d ij2
(10)
j
dengan J adalah fungsi objektif, uij adalah derajat keanggotaan poin data terhadap cluster-cluster dengan nilai antara 0 dan 1, c adalah jumlah cluster, n adalah banyaknya poin data, m adalah nilai parameter fuzzy dan dij adalah jarak antara pusat cluster ke-i hingga ke-j dari titik data.
14
Jarak antar pusat cluster ke-i hingga ke ke-j dari titik data didapatkan dari persamaan dij = ||ci-xj|| ; Nilai minimum dari pusat cluster digunakan persamaan (11) di bawah ini :
∑ = ∑ n
ci
j =1
u ijm x j
n
um j =1 ij
(11)
dengan ci adalah pusat cluster ke-i, n adalah banyaknya poin data, uij adalah derajat keanggotaan poin data terhadap cluster-cluster dengan nilainya antara 0 dan 1, m adalah nilai parameter fuzzy, serta xj adalah data poin ke-j. Untuk menghitung perubahan matrik partisi (derajat keanggotaan poin data terhadap semua cluster yang baru) digunakan persamaan (12).
u ij =
1 ⎛ d ij ∑k =1 ⎜⎜ d ⎝ kj c
⎞ ⎟ ⎟ ⎠
2 /( m −1)
(12).
dengan uij adalah derajat keanggotaan poin data terhadap cluster-cluster yang nilainya antara 0 dan 1, c adalah jumlah pusat cluster dari grup fuzzy ke-i, m adalah parameter fuzzy, dij adalah jarak euclidian antara pusat cluster ke-i hingga ke-j dari poin data, dkj adalah jarak euclidian antara pusat cluster ke-k hingga ke-j dari poin data. Algoritma FCM diawali dengan menentukan derajat keanggotaan (secara acak) setiap titik data terhadap cluster. Berdasarkan derajat keanggotaan, kemudian ditentukan pusat cluster. Pada kondisi awal, pusat cluster tentu saja masih belum akurat. Derajat keanggotaan selanjutnya diperbaiki berdasarkan fungsi jarak antara titik data dengan pusat cluster (Nascimento et. al., 2003). Dengan memperbaiki pusat cluster dan derajat keanggotaan tiap titik data secara berulang dan terus menerus maka pusat cluster akan bergeser ke titik yang tepat. Kinerja FCM tergantung pada inisialisasi pusat cluster. Keluaran FCM adalah deretan pusat cluster dan derajat keanggotaan data terhadap setiap cluster.
15
FCM menentukan pusat cluster ci dan keanggotaan matriks U (Jang et. al., 1997) dengan langkah-langkah sebagai berikut : 1. Inisialisasi keanggotaan matrik U dengan nilai random antara 0 dan 1 dengan persamaan (9). 2. Menghitung c pusat cluster fuzzy ci, i = 1,2,3,...c menggunakan persamaan (11). 3. Menghitung fungsi objektif berdasarkan persamaan (10). Berhenti jika hasil fungsi objektifnya mencapai nilai toleransi atau hasil fungsi objektifnya setelah iterasi maksimal yang ditetapkan. 4. Menghitung matrik partisi baru menggunakan persamaan (12) dan kembali ke langkah ke-2. Diagram alir proses clustering data pada algoritma fuzzy c-mean dapat dilihat pada Gambar 8.
Gambar 8. Tahapan algoritma fuzzy c-mean clustering (Jiang, 2003)
dengan U adalah matrik partisi, C adalah pusat cluster, D adalah jarak antar matrik, m adalah nilai parameter fuzzifikasi, k adalah jumlah cluster, n adalah jumlah data serta p jumlah atribut data. Kemudian untuk nilai E-step dan M-Step dapat dihitung dengan persamaan (13) dan persamaan (14).
16
n
E-step : mk =
∑ Uα X i =1 n
ik
∑U i =1
i
(13)
α ik
1
M-step : Uik =
⎛ xi − m k ⎞ ⎟ ⎟ l =1 ⎝ x i − ml ⎠
∑ ⎜⎜
(14)
1
α −1
dengan mk adalah pusat cluster ke-k dan Uik adalah derajat
keanggotaan
poin data terhadap pusat cluster (M-step). Dalam algoritma FCM ada beberapa hal yang perlu diperhatikan saat membangun sistem diantaranya iterasi maksimal, error terkecil yang diinginkan (ξ), pemangkat (m > 1) dan inisialisasi terhadap pusat awal cluster (c ≥ 2).
D. Metodologi Pelabelan Otomatis Citra
Metode pelabelan otomatis mengadopsi metode pengembangan ontologi yang dikenal dengan metodologi Uschold yaitu (Benjamins et. al., 2004): 1. Mendefinisikan tujuan dan cakupan dari pelabelan otomatis; 2. Membangun pelabelan otomatis dengan langkah labeling capture yang merupakan pengumpulan subjek-subjek/konsep citra, labeling coding membangun model subjek/konsep dan mengintegrasikan pelabelan yang telah ada (reuse) secara visual; 3. Melakukan evaluasi melalui verifikasi dan validasi;
E. Pengukuran Kinerja Sistem
Dua parameter utama yang dapat digunakan untuk mengukur keefektifan temu kembali citra, yaitu recall dan precision. Recall adalah perbandingan jumlah materi relevan yang ditemukembalikan terhadap jumlah materi yang relevan, sedangkan precision adalah perbandingan jumlah materi relevan
yang
ditemukembalikan
ditemukembalikan (Grossman, 2006).
terhadap
jumlah
materi
yang
17
recall =
jumlah citra relevan hasil temu kembali jumlah citra relevan dalam basis data
precision =
jumlah citra relevan yang terambil jumlah seluruh citra yang terambil
(15) (16)
Average precision adalah suatu ukuran evaluasi yang diperoleh dengan menghitung rata-rata tingkat precision pada berbagai tingkat recall (Grossman, 2006).
III. METODOLOGI PENELITIAN A. Kerangka Pemikiran Penelitian dilakukan dalam empat tahapan utama, yaitu pengindeksan, pelabelan otomatis, temu kembali citra dan evaluasi kinerja sistem (Gambar 9).
Gambar 9. Kerangka Pemikiran Penelitian Keempat tahapan tersebut terdiri dari beberapa proses yang saling berhubungan, yaitu : 1. Pengindeksan : pada tahapan ini dilakukan pemilihan citra sumber, segmentasi citra, ektraksi warna dan tekstur, serta pengukuran kemiripan ciri subjek citra menggunakan Euclid. 2. Pelabelan citra : mencakup pembentukan label citra secara otomatis. Proses ini dibangun berdasarkan kamus kata yang telah ditentukan.
19
3. Temu kembali citra : mencakup kueri teks sebagai masukan, penentuan indeks digunakan sebagai dasar temu kembali citra. 4. Evaluasi kinerja sistem : pengukuran hasil temu kembali citra berdasarkan nilai precision dan recall.
B. Alat Bantu Penelitian Peralatan yang diperlukan untuk melaksanakan penelitian dibagi menjadi dua, yaitu perangkat keras dan lunak. Perangkat keras berupa satu unit komputer PC dengan spesifikasi Intel Pentium IV, RAM 512 MB, Harddisk 80 GB dan Kartu grafis serta layar monitor minimal mempunyai resolusi warna 8 bit, sedangkan perangkat lunak yang diperlukan untuk perancangan dan pengujian sistem adalah Matlab 7.1 dengan platform sistem operasi Microsoft Windows XP. C. Tata Laksana Penelitian 1. Pengindeksan Pengindeksan dilakukan dalam empat tahapan utama (Gambar 10), yaitu pemilihan jenis dan sumber data menjadi basis data citra, segmentasi citra, ekstraksi ciri (warna dan tekstur) serta pengukuran kemiripan. Proses pengindeksan masing-masing dijelaskan berikut ini. PENGINDEKSAN CITRA EKSTRAKSI CIRI WARNA (HISTOGRAM) BASIS DATA CITRA
SEGMENTASI CITRA
UKURAN KEMIRIPAN (EUCLID)
EKSTRAKSI CIRI CITRA EKSTRAKSI CIRI TEKSTUR (WAVELET GABOR)
Gambar 10. Tata Laksana Pengindeksan
Jenis dan Sumber Data Citra sumber merupakan data sekunder yang diambil dari situs internet yang beralamat di ALIPR (http://www.alipr.com). Sebanyak 300 citra
20
kemudian dikelompokkan dalam tiga kelas citra dengan masing-masing kelas berjumlah 40 citra dan memiliki berbagai jenis objek. Format citra adalah JPG berukuran 50×50 piksel serta merupakan citra berwarna. Segmentasi Warna Citra Pada tahapan segmentasi ini, setiap citra akan disegmentasi untuk mengelompokkan warna yang dikandung oleh setiap piksel dari citra ke beberapa segmen yang sudah ditentukan jumlahnya, yaitu dua, tiga, empat, dan lima. Segmen ini merupakan representasi dari warna-warna dominan citra. Setiap piksel dari citra dibangkitkan dari salah satu g segmen. Peluang sebuah piksel masuk ke dalam segmen dapat dihitung dengan persamaan (17). g
p( x | Θ ) = ∑ p( x | θ l )π l .
(17)
l =1
Masing-masing segmen diasumsikan mempunyai distribusi normal Gauss, sehingga peluang piksel dari segmen l dapat dihitung dapat dihitung dengan persamaan (18). p( x | θ l ) =
1 d
1
(2π ) 2 det(Σl ) 2
(18)
⎧ 1 ⎫ exp⎨− ( x − μl )T Σl−1 ( x − μl )⎬. ⎩ 2 ⎭
Algoritma EM mempunyai dua tahapan utama yaitu tahapan Expectation (E-step) dan Maximization (M-step). Pada tahapan Expectation, data X diasumsikan sebagai data yang tidak lengkap dengan missing value berupa
label yang menyatakan keanggotaan tiap piksel dari X ke dalam salah satu g segmen. Pada tahapan ini yang dilakukan adalah menghitung peluang tiap piksel dari tiap segmen dan membentuk matriks Z yang akan melengkapi data X , sehingga data yang lengkap dapat dinyatakan sebagai Y = ( X , Z ) . Label
tiap piksel didapatkan dari segmen yang mempunyai peluang tertinggi dalam Z . Nilai likelihood dari data yang lengkap dapat dihitung dengan persamaan
(19). n
g
p(Y | Θ) = ∑∑ p(x | Θ ). i =1 l =1
(19)
21
Pada tahapan Maximization, parameter untuk iterasi berikutnya ditentukan sesuai dugaan variabel dari Z . Formulasi untuk menduga kembali parameter segmen adalah menggunakan persamaan (20),(21) dan (22). N
1 N
π lt +1 =
∑z i =1
N
∑
μ lt + 1 =
i =1 N
i l
z li x i
∑
z
i =1
∑ z (x N
∑ tl +1 =
i =1
i l
(20)
i
(21)
i l
)(
− μ lt +1 xi − μ lt +1 N
∑z i =1
)
T
(22)
. i l
Nilai parameter yang baru dari M-step ini akan digunakan kembali untuk E-step pada iterasi berikutnya. Proses E-step dan M-step akan terus berulang sampai didapatkan nilai likelihood yang kecil sehingga hasil perhitungan sudah tidak terlalu banyak mengalami perubahan. Ketika nilai likelihood hanya sedikit berubah, maka hasil dianggap konvergen. Ektraksi Ciri Warna Proses ekstraksi warna dengan FCH dilakukan pada ruang warna RGB untuk mempermudah pengolahan citra (Vertan & Boujemaa, 2000).
CITRA SUMBER
SEGMENTASI WARNA
HISTOGRAM
VEKTOR CIRI WARNA
Gambar 11. Ektraksi ciri warna Langkah pertama yang dilakukan untuk menghitung FCH adalah menghitung histogram awal (Gambar 11). Pada penelitian ini, nilai warna kuantisasi awal tersebut didasarkan pada sebaran warna citra dalam basis data yang memiliki 3 kelas citra dengan jenis dan warna yang bervariasi. Untuk
22
tiap kelas citra diambil 10 warna piksel yang muncul terbanyak sehingga dihasilkan 300 warna yang tidak sama. Dari histogram awal dihasilkan jumlah ciri yang terlalu banyak sehingga diperlukan waktu komputasi yang besar untuk ekstraksi ciri sebuah citra. Oleh karena itu perlu dilakukan pengelompokan warna (clustering) dari 300 warna semesta tersebut ke dalam beberapa pusat cluster warna menggunakan
Fuzzy
C-Means
(FCM).
Setiap
pusat
cluster
FCM
merepresentasikan bin FCH. Jumlah bin FCH yang digunakan sebanyak 30. Untuk perhitungan FCH selanjutnya diperlukan matriks derajat keanggotaan, dimana nilai keanggotaannya dapat diperoleh menggunakan fungsi Cauchy, yang dihitung menggunakan persamaan (23).
μ c ' (c ) =
1 1 + ( d (c ' , c ) / σ ) α
,
(23)
dimana d(c’,c)
= jarak Euclid antara warna c dengan c’,
c’
= warna pada bin FCH,
c
= warna semesta,
α
= untuk menentukan kehalusan dari fungsi,
σ
= untuk menentukan lebar dari fungsi keanggotaan.
Nilai parameter α = 2 dan σ = 15 diperoleh dari hasil percobaan sebelumnya (Balqis, 2006). Perhitungan akhir FCH dengan FCM dinotasikan sebagai berikut (persamaan 24) :
h 2 ( c ' ) = ∑ μ c ' ( c ) * h (c ) , c∈μ
dimana : h2
= fuzzy color histogram,
h(c)
= conventional color histogram,
μ c ' (c )
= nilai keanggotaan dari warna c ke warna c’.
(24)
23
Ekstraksi Ciri Tekstur Setiap citra mempunyai tekstur yang sebenarnya unik meskipun terkadang secara sepintas terlihat sama. Untuk menentukan ciri tekstur digunakan nilai energi dari beberapa frekuensi sampling pada transformasi Fourier 2D. Proses penentuan vektor ciri tekstur pada citra dengan memanfaatkan energi pada transformasi Fourier (Gambar 12). CITRA SUMBER
RGB Gray
FFT dengan fs1
SORT ENERGI
FFT dengan fs2
SORT ENERGI
FFT dengan fs3
SORT ENERGI
MERGE
VEKTOR CIRI TEKSTUR
Gambar 12. Ekstraksi ciri tekstur
Penggabungan Ciri Warna dan Tekstur Penggabungan ciri warna dan tekstur dilakukan dengan menggunakan pembobot tertentu. Nilai pembobot tersebut menyatakan hubungan keterkaitan masing-masing vektor ciri dengan vektor ciri total. Selanjutnya untuk istilah penggabungan ciri warna dan tekstur ini disebut dengan vektor ciri.
Pengukuran Kemiripan Ciri Vektor yang terbentuk dijadikan acuan untuk melakukan proses pencocokan pola untuk mendapatkan kesamaan ciri. Untuk menyatakan dua region citra sebagai cita yang mirip dilakukan proses perhitungan jarak Euclid antara vektor ciri dari kedua citra region tersebut.
2. Pelabelan Citra Pelabelan citra disusun berdasarkan topik atau subjek pengetahuan citra. Topik atau subjek pengetahuan citra ditentukan berdasarkan indeks visual yang diperoleh pada saat proses pengindeksan. Tahapan pelabelan dilakukan berdasarkan metode Uschold (Gambar 13).
24
Gambar 13. Tata Laksana Pelabelan Otomatis Tahapan pelabelan citra terdiri dari (Benjamins et. al., 2004) : 1. Labeling Capture : pengumpulan pengetahuan berupa konsep-konsep citra. Hasil dari tahapan ini adalah kamus kata. 2. Labeling Coding : membangun model dari konsep-konsep yang ada dalam kamus kata. Hasil dari tahapan ini adalah kamus visual citra. 3. Labeling Reuse : Integrasi dari konsep-konsep beserta komponenkomponennya. Hasil dari tahapan ini adalah visualisasi pelabelan citra. 3. Temu Kembali Citra Proses temu kembali citra dilakukan melalui penentuan indeks dari kueri yang berdasarkan teks. Proses retrieval data citra dilakukan sesuai dengan karakteristik citra terlabel dalam basis data (Gambar14). TEMU KEMBALI CITRA KUERI TEKS MASUKAN
BASIS DATA CITRA TERLABEL
PENENTUAN INDEKS
RETRIEVAL BERDASARKAN KARAKTERISTIK INDEKS
CITRA HASIL RETRIEVAL KARAKTERISTIK INDEKS
Gambar 14. Tata Laksana Temu Kembali Citra
25
4. Evaluasi Kinerja Sistem Evaluasi kinerja sistem dilakukan penilaian tingkat keefektifan proses temu kembali terhadap sejumlah koleksi. Pengujian dilakukan dengan menghitung nilai recall dan precision dari proses temu kembali citra berdasarkan penilaian relevansinya. Penentuan relevansi citra hasil temu kembali dibuat berdasarkan kelas citra di dalam basis data
IV. PERANCANGAN DAN IMPLEMENTASI SISTEM
Bagian ini menguraikan proses perancangan dan implementasi sistem. Bagian utama bab ini adalah desain data, desain proses sistem serta desain antar muka sistem. Desain data berisi citra sumber dan kamus kata. Desain proses sistem berisi proses segmentasi, proses pelabelan citra, proses temu tembali dan evaluasi sistem temu kembali sedangkan disain antar muka sistem berisi rancangan antar muka sistem.
A. Desain Data Desain data menggambarkan proses tranformasi data dalam sistem. Dalam penelitian ini data mengalami perubahan dari data citra, menjadi basis data citra, matrik representasi citra, matrik keanggotaan dan data cluster. Desain data lain adalah kumpulan kata-kata (kamus kata) yang berisi aturanaturan yang sesuai dengan kelas citra. 1. Citra Sumber Citra
sumber
penelitian
diperoleh
dari
web
ALIPR
(http://www.alipr.com). Terlihat dalam Tabel 2, citra sumber yang berhubungan dengan kelas pemandangan, bangunan, alam. Jumlah objek yang terkandung dalam citra dapat berisi 3 (tiga), 4 (empat) atau 5 (lima) objek. Contoh salah satu citra dengan subjek pemandangan memiliki objek citra berupa gunung, rumah, rumput. Citra sumber digunakan sebagai data pelatihan dan data pengujian. Data pelatihan digunakan sebagai data untuk pembentukan basis data ciri. Basis data ciri menjadi acuan untuk proses penemuan kembali citra pada saat diujikan. Data pengujian digunakan untuk pengujian pelabelan citra, sedangkan untuk pengujian temu kembali citra menggunakan kata-kata dalam kamus kata. Pengujian dengan kamus kata terdiri dari pengujian subjek citra serta objek-objek citra.
27
2. Kamus Kata Kamus kata (Tabel 2) berisi kumpulan kata-kata yang memuat aturan-aturan tentang citra. Aturan-aturan tersebut merupakan subjek dan objek citra. Kata-kata dalam kamus kata bersumber dari kosa kata bahasa Indonesia. Kamus kata disusun berdasarkan dua hal, yaitu subjek yang merupakan topik utama citra serta objek yang dimiliki subjek citra. Terdapat beberapa objek citra untuk suatu subjek dalam satu kelas citra sumber memiliki label atau identitas yang sama. Tabel 2. Kamus Kata Subjek
Jumlah
Objek
Citra
Citra
yang dimiliki
Pemandangan
100
Bangunan
100
Alam
100
langit(1), awan(2), rumput(3), pohon(4), matahari(5), gunung(6) rumah(7), jalan(8), batu(9), langit(10) batu(11), air(12), pohon(13),awan(14), langit(15)
Masing-masing objek pada kamus kata diberikan nomor urut yang menyatakan urutan identitas. Identitas tersebut berupa urutan objek kesatu, kedua, ketiga dan seterusnya. Pemberian id digunakan sebagai penanda objek hasil clustering. Jumlah objek yang didefinisikan untuk kamus kata adalah berjumlah 15 objek.
B. Desain Proses Sistem Desain proses sistem berisi rancangan proses pelabelan otomatis citra untuk sistem temu kembali citra. Desain proses sistem tersebut berisi tahapantahapan proses, yaitu pengindeksan (segmentasi, ekstraksi ciri dan clustering), pelabelan otomatis citra dan evaluasi sistem temu kembali.
28
1. Segmentasi Citra Citra sumber disegmentasi menggunakan metode Normalized Cuts (Shi & Malik, 2000). Metode Normalized Cuts merupakan segmentasi berbasis region yang menghasilkan sub citra. Sub citra tersebut dinamakan dengan region. Dalam penelitian ini digunakan enam region untuk setiap citra sumber. Beberapa citra sumber kemudian di segmentasi sehingga diperoleh region-region yang bersesuaian. Pembentukan region-region ini dimaksudkan untuk mendapatkan objek citra. Masing-masing region pada citra sumber, kemudian dilakukan pemisahan region dari citra utama. Pemisahan ini dilakukan untuk mempermudah mendapatkan ciri masing-masing region sebagai ciri objek. Pemisahan setiap region dari citra sumber dilakukan melalui pemberian tanda tertentu untuk area tertentu. Tanda yang dimaksud adalah dengan pemberian warna putih untuk area diluar target area yang dimakud. Ukuran citra yang dihasilkan tetap sesuai dengan citra hasil praproses awal yaitu 50 x 50, tapi untuk area yang dihasilkan dalam pembentukan region ini tidak memiliki format ukuran yang standar.
2. Ektraksi Ciri Setiap region yang telah dipisahkan, dilakukan perhitungan nilai ciri (Daubechies, 1995). Hasil perhitungan ciri akan diperoleh matrik representasi ciri suatu citra untuk setiap region. Representasi nilai ciri citra pada setiap region kemudian menjadi acuan untuk pembentukan ciri subjek citra. Pada tahapan ekstraksi ciri warna, setiap piksel pada citra akan direpresentasikan dengan peluang atau frekuensi piksel-piksel tersebut terhadap nilai warna (bin) yang sudah ditentukan sebanyak 30. Bin tersebut diperoleh dari FCH menggunakan FCM. Bin FCH yang digunakan pada penelitian ini dapat dilihat pada Lampiran 3, sedangkan untuk ekstraksi ciri tekstur, citra region terpilih diektraksi dengan menggunakan wavelet Gabor.
29
C. Perancangan Proses Sistem Rancangan proses sistem menggambarkan hubungan antara elemenelemen (modul) pada sistem yang dikembangkan. Prototipe sistem dan interface sistem dikembangkan dengan menggunakan perangkat lunak Matlab Versi 7.1. Sistem ini terdiri dari empat modul yaitu : modul segmentasi, modul pelabelan region, modul temu kembali dan modul kinerja (Gambar 15). Keempat modul tersebut digunakan dalam pengerjaan penelitian ini.
Gambar 15 . Arsitektur Sistem Pelabelan Otomatis
1. Modul Segmentasi. Modul segmentasi berfungsi untuk melakukan segmentasi, penarikan ciri serta clustering citra sumber. Modul ini bekerja dengan memanfaatkan algoritma Normalized Cuts untuk segmentasi. Penarikan ciri berdasarkan warna dan tekstur serta FCM untuk clustering, hasil akhirnya akan terbentuk region-region pada citra sumber beserta matrik ciri. Secara umum algoritma segmentasi Normalized Cuts seperti berikut (Shi & Malik, 2000) : 1. Mendefinisikan sekumpulan matrik dari citra yang akan di segmentasi 2. Menentukan bobot graf G=(V,E), lalu menghitung bobot edge dan menyimpan informasi dalam W dan D. 3. Menghitung (D − W )x = λDx untuk mendapatkan nilai eigen vektor dengan nilai eigen terkecil.
30
4. Menggunakan nilai eigen vektor tersebut untuk mempartisi graf menjadi 2 dengan membagi masing-masing titik menjadi NCut yang minimum. 5. Membaca nilai NCut yang dihasilkan, lalu mengulangi partisi ke langkah 2. 6. Jika NCuts untuk setiap segmen > nilai maksimum dari Ncuts yang didefinisikan maka proses dihentikan.
2. Modul Clustering Modul ini berfungsi untuk mengelompokkan data ciri yang telah tersedia dalam bentuk matrik menjadi kelompok-kelompok berdasarkan kemiripannya. Pengelompokkan data ciri tersebut menggunakan algoritam FCM. Tingkat kemiripan tersebut ditentukan dengan mengukur jarak euclid point data ke pusat cluster. Hasil dari modul ini adalah berupa matrik U yang merepresentasikan derajat keanggotaan data dan titik pusat cluster. Matrik keanggotaan (U) yang dihasilkan berdimensi k x n, dimana k adalah jumlah cluster dan n adalah jumlah data yang digunakan sebagai masukan. Matrik Keanggotaan hasil clustering terlihat seperti pada tabel 3. Tabel 3. Matrik Keanggotaan (U) Hasil Clustering Jumlah Data 1
Cluster 1
Cluster 2
.....
Cluster k
U11
U12
...
U1k
2
U 21
U 22
...
U 2k
...
....
...
...
...
...
...
...
...
...
n
U n1
U n2
...
U nk
Dalam proses pengelompokkan titik pusat cluster yang dihasilkan algoritma FCM akan mengalami perbaikan selama proses iterasi.
31
3. Modul Pelabelan Citra Pada suatu citra terdapat lebih dari satu objek, maka perlu dibedakan antara sebuah objek dengan objek lain yang terdapat pada citra tersebut. Proses pelabelan menggunakan teknik rekursi. Mula-mula dideteksi lokasi sebuah titik yang merupakan bagian dari sebuah objek, lalu dengan rekursi dilakukan pengisian dengan suatu nilai (label) terhadap objek tersebut dari lokasi tersebut sampai menemui batas luarnya (menabrak titik latar). Kemudian dilanjutkan mendeteksi lokasi yang merupakan titik objek yang belum terisi oleh proses tadi atau belum diberi label (dengan kata lain merupakan bagian dari objek yang lain). Lakukan pengisian lagi dengan nilai label yang berbeda. Ulangi sampai semua titik dalam citra tersebut diperiksa. Secara umum algoritma pelabelan citra adalah sebagai berikut : 1. Menentukan titik awal pengisian pada objek yang akan diisi. 2. Menentukan titik tersebut menjadi titik objek 2.1. Memeriksa apakah titik tetangga atasnya adalah titik latar. a. Jika ya maka lakukan hal yang sama untuk titik tersebut. b. Jika tidak maka lanjutkan. 2.2. Memeriksa apakah titik tetangga kanannya adalah titik latar. a. Jika ya maka lakukan hal yang sama untuk titik tersebut. b. Jika tidak maka lanjutkan. 2.3. Memeriksa apakah titik tetangga bawahnya adalah titik latar. a. Jika ya maka lakukan hal yang sama untuk titik tersebut. b. Jika tidak maka lanjutkan. 2.4. Memeriksa apakah titik tetangga kirinya adalah titik latar. a. Jika ya maka lakukan hal yang sama untuk titik tersebut. b. Jika tidak maka lanjutkan. Algoritma labeling reuse untuk pemetaan id region memanfaatkan data hasil cluster. Id region kemudian dipetakan pada region citra sumber sesuai dengan data kelas yang ada. Algoritma labeling reuse sebagai berikut :
32
1. Membaca region setiap citra. 2. Memetakan setiap region yang terbaca dengan id region yang bersesuaian 3. Mengulangi langkah 1 dan 2 sampai semua region terbaca.
4. Modul Temu Kembali Modul temu-kembali membaca dan menghasilkan output dari dan ke memori. Modul ini dikembangkan sebagai representasi hasil akhir sistem. Pada sistem ini dilakukan inputan berupa kueri teks dengan kata kunci masukan dan informasi yang ditampilkan berupa kumpulan citra yang berkaitan beserta derajat keanggotaannya.
5. Modul Evaluasi Modul evaluasi digunakan untuk mengukur tingkat keefektifan proses temu kembali terhadap sejumlah koleksi pengujian dengan menghitung nilai recall dan precision dari proses temu kembali citra berdasarkan penilaian relevansinya. Penentuan relevansi citra hasil temu kembali dibuat berdasarkan kelas citra di dalam basis data.
6. Modul Representasi Hasil Modul ini berfungsi untuk mentransformasikan hasil dari proses pencarian dan clustering menjadi bentuk yang lebih ramah pengguna (user friendly), dimana pengguna dapat dengan cepat mengetahui jumlah citra (beserta derajat keanggotaan) yang menjadi anggotanya.
D. Disain Antarmuka Antarmuka sistem dirancang agar pengguna dapat dengan mudah dan cepat memperoleh informasi yang diinginkan. Antarmuka sistem dirancang sedemikian rupa sehingga dapat mengurangi beban komputer dan membuat pengguna lebih fokus terhadap hasil.
33
Desain antar muka sistem ini terdiri dari 2 bagian utama, yaitu : antar muka untuk pelabelan otomatis citra (Gambar 16) dan antar muka untuk pencarian citra berdasarkan kata kunci tekstual (Gambar 17).
Gambar 16. Antar Muka Pelabelan Citra
TEMU KEMBALI CITRA SEARCH
HASIL RETRIEVAL
CITRA -1 RETRIEVAL
CITRA -2 RETRIEVAL
search
CITRA -3 RETRIEVAL
CITRA -4 RETRIEVAL
CITRA -5 RETRIEVAL
CITRA -6 RETRIEVAL
CITRA -7 RETRIEVAL
CITRA -8 RETRIEVAL
CITRA -9 RETRIEVAL
CITRA -10 RETRIEVAL
CITRA -11 RETRIEVAL
Gambar 17. Rancangan Desain Antarmuka Sistem
V. HASIL DAN PEMBAHASAN
A. Karakteristik Citra Masukan Sebanyak 300 citra yang digunakan pada penelitian ini dikelompokkan menjadi 3 subjek : pemandangan (100 citra), bangunan (100 citra), alam (100 citra). Masing-masing subjek terdiri dari 4 sampai dengan 6 objek (Tabel 4). Tabel 4. Subjek, jumlah, serta objek citra sumber Subjek
Jumlah
Objek
Citra
Citra
yang terkandung
Sumber
langit(1), awan(2), Pemandangan
100
rumput(3), pohon(4), matahari(5), gunung(6)
Bangunan
100
rumah(7), jalan(8),
http://www.alipr.com
batu(9), langit(10) batu(11), air(12),
Alam
100
pohon(13),awan(14), langit(15)
B. Pengindeksan Citra 1. Segmentasi Warna Citra Pada tahapan segmentasi ini, setiap citra disegmentasi untuk mengelompokkan warna yang dikandung oleh setiap piksel dari citra ke beberapa segmen (cluster) yang sudah ditentukan jumlahnya, yaitu dua, tiga, empat, dan lima. Cluster ini merupakan representasi warna-warna dominan citra. Tahapan segmentasi ini bertujuan mendapatkan kelompokkelompok warna dominan dan mengurangi jumlah warna citra asli seperti yang terlihat pada Gambar 18.
35
2 Cluster
3 Cluster
4 Cluster
5 Cluster
Gambar 18. Contoh citra sebelum dan sesudah segmentasi menggunakan algoritma EM. Selanjutnya dilakukan pemilihan keempat hasil segmentasi tersebut secara manual untuk dijadikan masukan pada tahap ekstraksi warna. Berdasarkan Gambar 18, dapat dilihat bahwa hasil segmentasi keempat adalah hasil segmentasi yang paling baik. Hal ini dikarenakan citra hasil segmentasi tersebut paling mirip dengan citra aslinya. Hasil segmentensi yang sudah terpilih sebagai masukan pada tahap ekstraksi warna untuk seluruh citra di dalam basis data dapat dilihat pada lampiran 1
2. Format Tekstur Citra Sedangkan untuk proses ekstraksi ciri tekstur, citra sumber perubahan format dari format RGB ke format gray scale. Hasilnya seperti terlihat pada Gambar 19.
36
Citra RGB ke Gray
Gambar 19. Contoh citra RGB ke citra gray scale 3. Segmentasi Region Semua citra sumber di segmentasi untuk menghasilkan regionregion yang bersesuaian dengan objek yang ada dalam citra. Jumlah region untuk setiap citra masukan ditentukan sebanyak 6 region. Penentuan enam region ini dilakukan berdasarkan asumsi jumlah maksimum objek yang terkandung dalam citra.
(a) Citra Sumber
(b) Citra Hasil Segmentasi Gambar 20. Contoh citra sebelum dan sesudah segmentasi menggunakan algoritma Normalized Cuts Selanjutnya citra hasil segmentasi dilakukan pemisahan region. Pemisahan region dilakukan dengan membaca setiap piksel yang memiliki nilai batasan (garis putih). Region yang diinginkan disimpan dalam file dengan format JPG, sedangkan untuk region yang lain komponen-komponen pikselnya digantikan dengan warna putih. Proses dilakukan berulang untuk region – region yang lain. Gambar 21
37
merupakan contoh citra sumber yang telah dilakukan pemisahan region. Pemisahan region digunakan untuk pengenal objek.
Gambar 21. Contoh citra hasil pemisahan citra menjadi 6 region Hasil pemisahan region citra menjadi masukan untuk tahap ekstraksi ciri. Seluruh citra hasil segmentasi region dalam basis data dapat dilihat pada Lampiran 2.
4. Ekstraksi Ciri Warna Pada
tahapan
ekstraksi
ini,
setiap
piksel
citra
akan
direpresentasikan dengan peluang atau frekuensi piksel-piksel tersebut terhadap nilai warna (bin) yang sudah ditentukan sebanyak 30. Bin tersebut diperoleh dari FCH menggunakan FCM. Bin FCH yang digunakan pada penelitian ini dapat dilihat pada Lampiran 3.
Gambar 22. Contoh citra region langit
38
Gambar 23. Hasil FCH dengan FCM 30 bin. Gambar 21 adalah hasil FCH dengan FCM dari Gambar 20. Berdasarkan Gambar 21, dapat dilihat bahwa bin 23 yang cenderung berwarna biru merupakan warna yang paling banyak muncul.
5. Ekstraksi Ciri Tekstur Ekstraksi ciri dilakukan untuk semua region yang terbentuk. Ciri tekstur yang digunakan adalah ciri energi dimana lebar pita frekuensi ( B F ) dan jarak angular (Sθ) sebesar 60°. Pemilihan lebar pita angular sebesar 60° adalah karena nilai ini dianggap mendekati karakteristik sistem visual manusia.
Gambar 24. Contoh citra region rumput
39
Proses filtering untuk Gambar 24, menggunakan frekuensi
F=
2 dan orientasi θ = 600 . Hasil filtering terlihat seperti pada Gambar 3 2
15.
Gambar 25. Region rumput dengan frekuensi F =
2 dan θ = 600 3 2
6. Penggabungan Ciri Warna dan Tekstur
Penggabungan ciri warna dan tekstur dilakukan dengan mengubahubah
nilai
pembobot
antara
masing-masing
ciri
dan
kemudian
dibandingkan sehingga diperoleh pembobot ciri optimal yang menyatakan gabungan antara dua ciri dasar yaitu ciri warna dan ciri tekstur. Pengujian dilakukan dengan mengambil beberapa kelompok citra dan mengukur perbedaan ciri dari masing-masing kelompok serta mengukur kesamaan dari masing-masing anggota kelompok (Harsono & Basuki, 2005). Nilai pembobot (ac,at) yang dicoba adalah ac = 0.7 dan at =0.3. Nilai pembobot ini dipilih karena berdasarkan penelitian yang dilakukan Harsono dan Basuki (2005) menyatakan bahwa pada nilai bobot tersebut sangat baik untuk penggabungan nilai ciri warna dan tekstur. Nilai at yang diambil selalu lebih kecil dari ac, karena ciri tekstur memang tidak terlalu dominan dalam penentuan ciri citra secara umum. Nilai ciri baru diperoleh dengan rumus : Ciri baru = 0.7 * Vektor ciri warna + 0.3 * Vektor ciri tekstur
C. Pelabelan Citra
1. Labeling Capture Proses ini berupa mengumpulkan semua subjek citra. Hasil yang peroleh dari proses ini adalah berupa kumpulan kamus kata (Tabel 4).
40
2. Labeling Coding
Setelah ciri region diperoleh dan disimpan dalam basisdata, selanjutnya algoritma clustering dijalankan. Algoritma clustering ini membutuhkan matrik ciri region sebagai data masukan.
Matrik Keanggotaan
Hasil dari proses clustering adalah matrik keanggotaan region terhadap cluster yang dihasilkan. Tabel 5. Matrik Keanggotaan Region berdasarkan hasil clustering Region
C1
C2
C3
C4
C5
C6
1 2 3 4 5 717 718 719 720
0.881539 3.19E-06 1.64E-11 1.67E-13 0.000184 8.57E-11 1.27E-05 3.24E-06 0.853729
0.118309 2.99E-07 4.08E-09 2.1E-14 2.53E-06 1.05E-11 0.056199 3.04E-07 4.48E-05
2.02E-08 0.921212 5E-15 0.999999 7.75E-06 0.99999 9.48E-10 0.91941 8.37E-08
5.15E-05 5.53E-08 0.999999 5E-15 1.92E-07 2.24E-12 0.943788 5.61E-08 8.15E-07
7.25E-07 0.078716 5.5E-14 3.06E-10 0.068908 2.28E-07 1.34E-08 0.080517 1.16E-05
9.95E-05 6.86E-05 7.91E-13 2.08E-12 0.930898 1.16E-09 2.94E-07 6.98E-05 0.146214
Hasil clustering menunjukkan subjek bangunan memiliki jumlah tertinggi pada cluster ke-2, sedangkan pemandangan terbanyak pada cluster ke-1 dan subjek alam terbanyak pada cluster ke-4. Total Clus te r pe r Subje k 80 70
Total
60 50
Pemandangan
40
Bangunan
30
Alam
20 10 0 1
2
3
4
5
6
Clus te r
Gambar 26 . Grafik Total Cluster per Subjek
41
Visualisasi Pelabelan
Nilai maksimum setiap cluster pada setiap citra menyatakan bahwa nilai region ini lebih mendekati cluster yang terbentuk hasil clustering. Selanjutnya nilai keanggotaan maksimun ini dipetakan secara visual terhadap citra hasil segmentasi. Gambar 27, menunjukkan visualisasi salah satu citra yang memiliki nilai keanggotaan region.
Gambar 27. Citra contoh labeling coding
Penggabungan Region
Nilai region dengan nilai 0.16107 dan 0.16739, berdasarkan hasil clustering kemudian dikelompokkan ke dalam satu kelompok. Begitu juga untuk nilai 0.60864 dan 0.65573 juga dikelompokkan dalam satu kelompok tersendiri. Sedangkan untuk nilai 0.30412 dan 0.47258 dikelompokkan dalam satu kelompok. Perhitungan nilai ciri baru untuk region dilakukan dengan menghitung nilai rata-rata untuk region-region yang terkelompok dalam satu kelompok. Gambar 28, menunjukkan visualisasi hasil penggabungan region bersama dengan nilai keanggotaan region untuk Gambar 27.
42
Gambar 28. Contoh citra proses penggabungan region
3. Labeling Reuse Integrasi dari konsep-konsep dalam kamus kata. Informasi yang diperoleh adalah visualisasi pelabelan otomatis citra.
Gambar 29. Contoh citra hasil pelabelan otomatis
Gambar 29 menunjukkan proses labeling reuse nilai region yang berupa label untuk region yang ada di citra. Proses pelabelan ini akan digunakan dalam tahapan temu kembali, sedangkan nilai ciri region akan digunakan untuk penghitungan jarak dalam proses temu kembali.
43
D. Hasil Temu Kembali
Kueri berdasarkan teks tidak memerlukan proses ekstraksi namun langsung pada penentuan indeks dan retrieval data sesuai dengan karakteristik indeks. Proses ini diawali dengan penentuan deskripsi secara teks oleh user kemudian sistem akan mencari/menentukan indeks yang sesuai, kemudian berdasarkan tabel indeks yang sudah ada dilakukan pencocokan karakteristik. Dari proses ini diperoleh citra yang sesuai dengan yang dicari. Gambar 30 memperlihatkaan bahwa citra hasil temu kembali tidak sepenuhnya berasal dari jenis citra yang sama dengan kueri masukan. Citra yang relevan di dalam basis data yang ditemukembalikan sampai 30 citra teratas sebanyak 30 citra yang relevan di dalam basis data. Terdapat beberapa citra yang ditemukembalikan memiliki objek yang sesuai dengan warna dan tekstur citra untuk kata kunci ‘awan’ dan ‘rumput’. Dari sisi warna yang tidak terkandung sama sekali dalam kueri ‘awan’ dan ‘rumput’ yang dominan biru dan hijau, yaitu citra pada peringkat 7 dan 11. Hal ini dikarenakan sistem tidak mengenal kelas citra untuk kata kunci ‘awan’ dan ‘rumput’ tapi citra tersebut masih memiliki objek yang terkandung dalam subjek yang sama dengan ‘awan’
dan
‘rumput’
yaitu
pemandangan
dan
sistem
hanya
menemukembalikan citra di dalam basis data yang mempunyai tingkat kemiripan yang tinggi dengan kueri serta semua citra dalam basis data yang memiliki salah satu objek dari citra kueri.
44
Gambar 30. Hasil Temu Kembali Citra denga kata kunci ‘rumput’,’awan’.
E. Evaluasi Hasil Temu Kembali
Pada tahap evaluasi dilakukan penilaian tingkat keefektifan dalam proses temu kembali terhadap sejumlah koleksi pengujian dengan menghitung nilai recall dan precision dari proses temu kembali citra berdasarkan penilaian relevansinya. Penentuan relevansi citra hasil temu kembali dibuat berdasarkan kelas citra di dalam basis data, di mana terdapat 3 kelas citra yang berbeda, yaitu: 1. Pemandangan 2. Alam 3. Bangunan Di dalam basis data terdapat 300 citra dari 3 kelas citra dengan 40 citra untuk setiap kelas citra. Dengan demikian untuk setiap kueri citra terdapat 40 citra relevan di dalam basis data yang penilaian relevansinya didasarkan atas kesamaan kelas citra. Penilaian relevansi tersebut kemudian digunakan sebagai acuan pada saat melakukan evaluasi terhadap hasil temu kembali untuk setiap citra kueri.
45
Nilai recall yang digunakan adalah 0,0.1,0.2,...,1. Nilai ini menunjukkan jumlah bagian citra dari seluruh citra terambil untuk perhitungan nilai precision. Misalkan untuk nilai recall 0.1 berarti jumlah citra yang digunakan untuk perhitungan nilai precision adalah 10% dari seluruh citra yang terambil. Nilai precision untuk nilai recall 0.1 adalah perbandingan banyaknya citra relevan yang terambil dari seluruh citra dengan jumlah tersebut. Nilai rataan precision hasil temu kembali citra dapat dilihat pada Tabel 6. Dalam Tabel 6 dapat dilihat bahwa nilai rataan precision mengalami penurunan pada nilai recall 0.7, sedangkan pada nilai recall lainnya cenderung stabil. Hal ini dikarenakan pada peringkat recall 0.7 banyak teks kueri yang tidak menemukan citra yang relevan di dalam basis data. Tabel 6. Nilai rataan precision
hasil temu kembali citra
Rataan Precision (%)
Recall 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Rataan
Teks Kueri 100% 100.00% 100.00% 88.88% 83.33% 86.67% 77.78% 76.19% 79.17% 81.48% 80.00% 86.68%
100% 80% 60% Teks Kueri
40% 20% 0% 0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Recall
Gambar 31. Grafik rataan precision hasil temu kembali citra teks
kueri
46
F. Pengembangan Prototipe 1. Antar Muka Menu Utama Sistem dan Pelabelan Citra
Antar muka menu utama sistem serta pelabelan citra dibuat dalam satu kesatuan. Rancangan ini dibuat sedemikian rupa sehingga pengguna dapat menggunakannya seoptimal mungkin.
1 3
2
4
5
6
Gambar 32. Antar Muka Sistem dan Pelabelan Citra
Bagian-bagian dalam antar muka ini, terlihat seperti pada Gambar 32. (1)merupakan menu utama untuk proses temu kembali citra, (2) digunakan untuk pemilihan citra yang akan diberi label. (3) merupakan citra asli. (4) adalah citra hasil segmentasi region, (5) citra hasil penggabungan region dan (6) merupakan citra hasil pelabelan.
2. Antar Muka Temu Kembali Citra
Antar muka untuk temu kembali citra dibuat sedemikian rupa sehingga pengguna dapat menggunakannya sebagai antar muka pencarian. Antar muka ini dikembangkan untuk melakukan pencarian citra dalam basis data sesuai dengan kata-kunci yang digunakan sebagai pencarian.
47
Gambar 31. Antar Muka Temu Kembali Citra
VI. SIMPULAN DAN SARAN
A. Simpulan Berdasarkan penelitian yang telah dilakukan dapat disimpulkan beberapa hal, yaitu : 1. Proses pelabelan otomatis citra menghasilkan pelabelan yang cukup baik. 2. Definisi kata-kata yang merepresentasikan subjek dan objek citra dalam kamus kata terlihat penggunaannya dalam proses temu kembali. 3. Model pelabelan citra otomatis menggunakan Fuzzy C-means (FCM) dilakukan berdasarkan kata-kata yang terdefinisi dalam kamus kata. 4. Tabel indeks citra dalam penelitian ini disusun berdasarkan proses pelabelam otomatis citra dan digunakan sebagai dasar untuk proses temu kembali. 5. Hasil penelitian menunjukkan bahwa nilai rataan precision untuk hasil temu kembali menggunakan kueri berbasis teks mencapai 86.68%. Ini menunjukkan bahwa proses pencarian citra dalam basis data lebih baik karena pelabelan yang dilakukan berguna sebagai kata kunci pencarian.
B. Saran Berdasarkan hasil dari penelitian yang dilakukan, dapat dikemukakan beberapa saran yang dapat dipertimbangkan untuk ditindaklanjuti, yaitu: 1. Penelitian ini dapat dikembangkan untuk pembentukan ontologi citra. 2. Berdasarkan penelitian, terdapat beberapa kesalahan klasifikasi yang dapat menyebabkan hasil temu kembali citra menjadi kurang baik. Oleh karena itu, untuk penelitian selanjutnya dapat digunakan metode relevance feedback dalam temu kembali citra agar hasil temu kembali citra menjadi lebih baik.
49
3. Penelitian selanjutnya dapat dikembangkan sistem temu kembali citra berdasarkan ciri warna, bentuk, dan tekstur untuk melengkapi hasil temu kembali. 4. Sampai saat ini belum ada teknik segmentasi citra yang dapat melakukan segmentasi dengan baik. Oleh karena itu, disarankan untuk dapat memperbaiki hasil segmentasi sehingga ketidaksesuaian dengan objek yang diinginkan dapat diminimalisasi.
DAFTAR PUSTAKA Balqis, DP. 2006. Metode Fuzzy Color Histogram untuk Temu Kembali Citra Bunga. [Skripsi]. Bogor:Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Barnard K, Duygulu P, Forsyth D, de Freitas N, Blei D.M, Jordan M. I. 2003. Matching words and pictures. Journal of Machine Learning Research. 3:1107-1135. Belongie S, 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. Benjamins V.R, P´erez. A. G. 2004. Knowledge System Technology: Ontologies and Problem-Solving Methods. Website. www.swi.psy.uva.nl/usr/richard/ pdf/kais.pdf [15 Januari 2008]. Brodatz. 1966. Textures: A Photographic Album for Artists and Designers. http://www-dbv.informatik.uni-bonn.de/image/segmentation.html. [15 Oktober 2007]. Cox E. 2005. Fuzzy Modelling and Genetic Algorithms for Data Mining and Exploration. San Fransisco. Morgan Kaufman Publisher. Daubechies I. 1995. Ten Lectures on Wavelets. Capital City Press: Montpelier, Vermont. Deschacht K, Moens MF. 2007. Text Analysis for Automatic Image Annotation. The 45th Annual Meeting of the Association for Computational Linguistics; Prague; June 2007. Duygulu P, Barnard K, de Fretias N, Forsyth D . 2002. Object recognition as machine translation: Learning a lexicon for a fixed image vocabulary. Proceedings of the European Conference on Computer Vision: 97-112. Feng S., Manmatha R., Lavrenko V. 2004. Multiple Bernoulli Relevance Models for Image and Video Annotation, In Proc. IEEE Conf. Computer Vision and Pattern Recognition. Gonzales RC, Woods RE, 2002. Digital Image Processing. Edisi ke-2. New Jersey: Prentice Hall, Inc. Grossman D. IR Book. http://www.ir.iit.edu/~dagr/cs529/files/ir_book/ [30 Oktober 2007].
Harsono T, Basuki A. 2005. Sistem Content Based Image Retrieval Menggunakan Fitur Dasar Gambar Untuk Image Searching. Proceeding IES 2005. Surabaya. Han J, Ma KK.2002. Fuzzy Color Histogram and Its Use in Color Image Retrieval. IEEE Transaction on Image Processing. 8:11. Hua X.S., Zhang H.J. 2008. Media Content Analysis. Scholarpedia.3(2):3712. http://www.scholarpedia.org/article/Media_Content_Analysis. [8 Agustus 2008] Eakins J. 1996. Automatic image content retrieval – are we getting anywhere.In Proceedings of Third International Conference on Electronic Library and Visual Information Research. pages 123–135. Jain A.K., Murty M.N. dan Flynn P.J. 1999. Data Clustering : A Review. ACM Computing Survey. 31. Jang JS, Roger, Sun CS. Eiji M.1997. Neuro-Fuzzy and Soft Computing. A Computional Approach to Learning and Machine Intelligence.USA.Prentice-Hall International Inc. Jiawei H, Kamber M. 2001. Data Mining, Concepts and Techniques. Morgan Kauffman Publishers. San Fransisco, USA. Kantardzic M. 2001. Data Mining, Concepts, Methods and Algorithm. New Jersey : IEEE. Lavrenko V, Manmatha R, Jeon J. 2003. A model for learning the semantics of pictures. Proceedings of the 16th Conference on Advances in Neural Information Processing Systems NIPS. Long F, Zhang H, Feng DD. 2003. Fundamental of Content-Based Image Retrieval. http://www.research.microsoft.com/asia/dload_files/group/mcomputing/20 03P/ch01_Long_v40 proof.pdf. [12 September 2007]. Mori Y, Takahashi H, Oka R. 1999. Image-to-word transformation based on dividing and vector quantizing images with words. First International Workshop on Multimedia Intelligent Storage and Retrieval Management, Nascimento S, Mirkin B, Moura-Pires F. 2003. Modeling Propotional Membership in Fuzzy Clustering. IEEE Trans on Fuzzy Syst. 11:2. Noorniawati VY,. 2007. Metode Support Vector Machine untuk klasifikasi pada sistem temu kembali citra [Skripsi]. Bogor : Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor.
Sahin PG. 2003. Translating Images to words: A novel approach for object recognition [PhD thesis]. Turkey : The Department Of Computer Engineering, Middle East Technical University. Schober, Jean-Pierre. Thorsten Hermes, Otthein Herzog.2004. Content-based Image Retrieval by Ontology-based Object Recognition. TZI Center for Computing Technology Universitätsallee. 21-23 28359. Bremen, Germany. Sebe N, Lew NS, 2000. Robust Computer Vision : Theory and Application. Leiden : Leiden Institue of Advance Computer Science. Seo N. 2006. Texture Segmentation using Gabor Filters, http://note.sonots.com/index.php?SciSoftware%2FGaborTextureSegmenta tion.[8 November 2007]. Shi J, Malik J. 2000. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence. 22:8:888-905. Srikanth M, Varner J, Bowden M, Moldovan D. 2005. Exploiting Ontologies for Automatic Image Annotation. ACM. 1595930345/05/0008 Vertan C, Boujemaa N. 2000. Using Fuzzy Histogram and Distance for Color Image Retrieval. http://www-rocq.inria.fr/imedia/Articles/cir2000.pdf [28 September 2007].
Lampiran 1. Segmentasi Warna Citra Sumber
Lampiran 2. Segmentasi Region Citra Sumber.
Lampiran 3 : Warna kuantisasi untuk 30 bin histogram
Warna 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
R 64 20 165 49 107 115 84 246 150 166 211 135 241 90 153 251 51 119 190 85 115 106 178 74 64 233 174 150 125 86
G 68 23 174 45 112 137 120 247 141 153 214 155 242 156 128 252 72 125 197 97 128 101 201 76 88 235 188 156 133 89
B 53 16 177 41 95 173 138 246 114 128 213 170 239 218 102 251 35 107 190 96 59 76 224 69 89 231 213 156 132 61
