UCAPAN TERIMAKASIH Segenap puja dan puji syukur penulis panjatkan kehadapan Ida Sang Hyang Widhi Wasa sebagai sumber dari segala sumber pengetahuan, karena atas asung kertha wara nugrahaNya Tesis yang berjudul "Image Retrieval dengan Teknik Self Organizing Map (SOM)" ini dapat diselesaikan. Pada kesempatan ini perkenankanlah penulis mengucapkan terima kasih yang sebesar-besarnya kepada Bapak Dr. Ir. Made Sudarma, M.A.Sc., selaku Dosen Pembimbing I yang telah banyak membantu dalam memberikan ide, saran, dan motivasi. Terima kasih yang sebesar-besarnya pula kepada penulis sampaikan kepada Bapak Dr. I Made Oka Widyantara, ST., MT., selaku Dosen Pembimbing II yang telah memberikan bimbingan dan arahan dalam penyelesaian Tesis ini. Ucapan yang sama juga ditunjukkan kepada Rektor Universitas Udayana Prof. Dr. dr. Ketut Suastika, Sp.PD-KEMD atas kesempatan dan fasilitas yang diberikan kepada penulis untuk mengikuti dan menyelesaikan pendidikan Program Magister di Universitas Udayana. Ucapan terima kasih ini juga penulis sampaikan kepada Direktur Program Pascasarjana Universitas Udayana Prof. Dr. dr. A. A. Raka Sudewi, Sp.S (K) atas kesempatan yang diberikan kepada penulis untuk menjadi mahasiswa pada Program Pascasarjana Universitas Udayana, serta ucapan terima kasih kepada Prof. Ir. I.A Dwi Giriantari, MEngSc.,PhD sebagai Ketua Program Magister Program Studi Teknik Elektro Program Pascasarjana Universitas Udayana. Penulis juga menyampaikan terima kasih yang sebesar-besarnya kepada Bapak, Ibu, Istri dan Anak-anak tercinta serta seluruh keluarga yang telah banyak memberikan bantuan, dorongan, dan semangat untuk menyelesaikan Tesis ini. Penulis juga mengucapkan terima kasih kepada Bapak/Ibu Dosen di Program Magister Teknik Elektro Universitas Udayana dan Civitas Akademika STMIK STIKOM Bali serta berbagai pihak yang tidak mungkin disebutkan satu persatu, yang dengan semangat sudah memberikan dorongan untuk mengikuti dan menyelesaikan pendidikan program Magister ini. Semoga Ida Sang Hyang Widhi Wasa/Tuhan Yang Maha Esa selalu melimpahkan rahmat-Nya kepada semua pihak yang sudah penulis sebutkan maupun yang belum penulis sebutkan sudah berpartisipasi dan menunjukkan dedikasi ketulusan yang sangat luar biasa dalam membantu penyelesaian Tesis ini Denpasar, Agustus 2016
Penulis
vi
Abstrak
Image retrieval merupakan teknologi yang membantu mengelola data digital dalam bentuk gambar. Pencarian dan penemuan gambar bertujuan untuk mempertegas apa yang sebenarnya dicari, dimana melakukan pencarian, dan dalam bentuk apa pengguna melakukan pencarian. Penelitian ini mempergunakan metode clustering untuk mengelompokkan gambar berdasarkan fitur-fitur yang dimiliki oleh gambar itu sendiri. Proses ekstraksi fitur mempergunakan metode ekstraksi fitur warna, fitur tekstur, dan bentuk. Fitur warna menggunakan metode Color Histogram, ekstraksi tekstur mempergunakan Gray Level oCcurance Matrix, dan bentuk mempergunakan Edge Direction metode Canny Edge Detection. Proses perhitungan jarak antar fitur gambar mempergunakan metode Mahattan. Proses clustering mempergunakan metode Self Optimizing Map (SOM). Evaluasi sistem menggunakan dua pendekatan, yaitu dengan pengukuran nilai cluster menggunakan purity dan entropy, dan pengukuran pencarian gambar menggunakan recall dan precision. Hasil pengujian sistem image retrieval dengan metode SOM menunjukkan bahwa dalam pengukuran cluster dengan purity dan entropy menunjukkan nilai rata-rata purity di bawah 0,5 dan entropy rata-rata diatas 0,8. Kata Kunci : image retrieval, fitur warna, tekstur dan bentuk, Self Organizing Map
vii
Abstract A Image retrieval is a technology that helps manage digital data in images form. Search and discovery images aims to reinforce what is actually looked for, where to search, and the purpose of the search. The research used clustering methods to classify images based on features from the image itself. Color, texture, and shape feature are used in features extraction process. Color feature is extracted using the Color Histogram method, texture feature is extracted using Gray Level occurance Matrix, and shape feature is extracted using Edge Direction from Canny Edge Detection method. Mahattan method is applied for calculating the distance between the image features. And then the clustering is done by Self Optimizing Map (SOM). There are two approaches for evaluation systems: by using a cluster measurements with purity and entropy, and measurement image searching result using recall and precision. The evaluations image retrieval system with SOM method shows that in the measurement of the cluster with the purity and entropy method the average purity values below 0,5 and entropy average above 0,8. Keywords : image retrieval, color, texture, and shape feature extraction, Self Organizing Map
viii
DAFTAR ISI
Lembar Persetujuan Pembimbing ..................................................................... iii UCAPAN TERIMAKASIH................................................................................. vi Abstrak ................................................................................................................. vii Abstract ................................................................................................................ viii DAFTAR ISI ......................................................................................................... ix DAFTAR GAMBAR ............................................................................................ xi DAFTAR TABEL .............................................................................................. xiii DAFTAR ISTILAH DAN SINGKATAN ......................................................... xv BAB I PENDAHULUAN ...................................................................................... 1 1.1.
Latar Belakang ......................................................................................... 1
1.2.
Rumusan Masalah .................................................................................... 5
1.3.
Batasan Masalah ....................................................................................... 5
1.4.
Tujuan Penelitian ...................................................................................... 6
1.5.
Manfaat Penelitian .................................................................................... 7
1.6.
Keaslian Penelitian ................................................................................... 7
BAB II LANDASAN TEORI ............................................................................... 9 2.1.
State of the Art .......................................................................................... 9
2.2.
Data Mining ............................................................................................ 11
2.3.
Image Clustering .................................................................................... 12
2.4.
Image Retrieval by Unsupervised Learning ........................................... 15
2.5.
Feature Extraction ................................................................................. 16
2.6.
Self Organizing Map (SOM) .................................................................. 20
BAB III METODE PENELITIAN .................................................................... 24 3.1.
Tempat dan Waktu Penelitian ................................................................ 24
3.2.
Sistematika Penelitian ............................................................................ 24
3.3.
Studi Pustaka .......................................................................................... 25
3.4.
Pengumpulan Data ................................................................................. 26
3.5.
Gambaran Umum Sistem ....................................................................... 27
ix
3.6.
Tahap Penarikan Kesimpulan ................................................................. 43
3.7.
Instrumen Penelitian ............................................................................... 44
BAB IV HASIL DAN PEMBAHASAN ............................................................ 45 4.1.
Antarmuka Sistem .................................................................................. 45
4.2.
Inputan Gambar Latih ............................................................................ 45
4.3.
Pre-Processing Gambar Latih ................................................................ 47
4.4.
Feature Extraction Gambar Latih ........................................................... 48
4.5.
Similiarity dan Neighboring Image ........................................................ 52
4.6.
Cluster Image ......................................................................................... 53
4.7.
Evaluasi .................................................................................................. 54
BAB V KESIMPULAN DAN SARAN .............................................................. 80 5.1.
Kesimpulan ............................................................................................. 80
5.2.
Saran ....................................................................................................... 81
DAFTAR PUSTAKA .......................................................................................... 83
x
DAFTAR GAMBAR
Gambar 3. 1 Sistematika Penelitian ...................................................................... 25 Gambar 3. 2 Gambaran Umum Sistem ................................................................. 27 Gambar 3. 3 Gambar Latih kategori : (a) Anjing, (b) Ballon, (c) Bunga .............. 29 Gambar 3. 4 RGB Citra Warna ............................................................................. 31 Gambar 3. 5 Citra Abu-abu ................................................................................... 31 Gambar 3. 6 Color Histogram 8 Bin ..................................................................... 34 Gambar 3. 7 GLCM korelasi antara sepasang piksel dengan jarak dan arah tertentu (Jeremiah, 2007) ................................................................................. 36 Gambar 3. 8 Flowchart SOM (Warsito, 2008) ...................................................... 39 Gambar 4. 1 Tampilan Aplikasi Image Retrieval dengan teknik SOM ................ 45 Gambar 4. 2 Halaman penyimpanan gambar latih ................................................ 46 Gambar 4. 3 Dialog pemilihan folder gambar latih .............................................. 46 Gambar 4. 4 Halaman pemilihan kategori gambar dan penyimpanan gambar latih ............................................................................................................................... 47 Gambar 4. 5 Halaman Pre-processing grayscale gambar latih ............................. 48 Gambar 4. 6 Halaman color extraction ................................................................. 49 Gambar 4. 7 Nilai fitur warna gambar latih .......................................................... 49 Gambar 4. 8 Halaman texture extraction .............................................................. 50 Gambar 4. 9 Nilai fitur teksture gambar latih ....................................................... 50 Gambar 4. 10 Halaman shape extraction .............................................................. 51 Gambar 4. 11 Nilai fitur bentuk gambar latih ....................................................... 52 Gambar 4. 12 Halaman Aplikasi Pemilihan Gambar Uji ...................................... 52 Gambar 4. 13 Halaman Similiarity dan Ordering Image ...................................... 53 Gambar 4. 14 Halaman Clustering dan Hasil Retrieval Image ............................. 54 Gambar 4. 15 Contoh Gambar Latih ..................................................................... 56 Gambar 4. 16 Gambar latih jarak kedekatan terkecil dengan gambar uji kategori anjing ..................................................................................................................... 58 Gambar 4. 17 Hasil Pengujian Sistem Data Uji Kategori Anjing ......................... 61
xi
Gambar 4. 18 Gambar latih jarak kedekatan terkecil dengan gambar uji kategori gajah ...................................................................................................................... 63 Gambar 4. 19 Hasil Pengujian Sistem Data Uji Kategori Gajah .......................... 66 Gambar 4. 20 Gambar latih jarak kedekatan terkecil dengan gambar uji kategori bunga mawar .................................................................................... 67 Gambar 4. 21 Hasil Pengujian Sistem Data Uji Kategori Bunga Mawar ............. 70 Gambar 4. 22 Gambar latih jarak kedekatan terkecil dengan gambar uji kategori Bus ........................................................................................................................ 71 Gambar 4. 23 Hasil Pengujian Sistem Data Uji Kategori Bus .............................. 74 Gambar 4. 24 Gambar latih jarak kedekatan terkecil dengan gambar uji kategori dinosaurus ........................................................................................ 76 Gambar 4. 25 Hasil Pengujian Sistem Data Uji Kategori Bus .............................. 79
xii
DAFTAR TABEL
Tabel 3. 1 Komposisi Warna Citra (RGB) ............................................................ 33 Tabel 3. 2 Komposisi grayscale dari nilai RGB ................................................... 33 Tabel 3. 3 Keanggotaan warna abu ke 16 bin ....................................................... 35 Tabel 3. 4 Komposisi Warna Keabuan citra ......................................................... 35 Tabel 3. 5 Keanggotaan warna abu-abu ke dalam 16 bin ..................................... 36 Tabel 3. 6 GLCM arah nol derajat dengan jarak 1 piksel ..................................... 36 Tabel 4. 1 Hasil Pengukuran clustering dan hasil pencarian gambar kategori Anjing ............................................................................................................................... 57 Tabel 4. 2 Hasil Pengukuran jarak fitur Warna kategori Anjing .......................... 59 Tabel 4. 3 Hasil Pengukuran jarak fitur Tekstur kategori Anjing ......................... 59 Tabel 4. 4 Hasil Pengukuran jarak fitur Bentuk kategori Anjing ......................... 59 Tabel 4. 5 Hasil pengujian cluster kategori Anjing............................................... 60 Tabel 4. 6 Hasil pengujian pencarian gambar kategori Anjing ............................. 60 Tabel 4. 7 Hasil Pengukuran clustering dan hasil pencarian gambar kategori Gajah ............................................................................................................................... 62 Tabel 4. 8 Hasil Pengukuran jarak fitur Warna kategori Gajah ............................ 63 Tabel 4. 9 Hasil Pengukuran jarak fitur Tekstur kategori Gajah .......................... 64 Tabel 4. 10 Hasil Pengukuran jarak fitur Bentuk kategori Gajah ......................... 64 Tabel 4. 11 Hasil pengujian cluster kategori Gajah .............................................. 65 Tabel 4. 12 Hasil pengujian pencarian gambar kategori Gajah ............................ 65 Tabel 4. 13 Hasil Pengukuran clustering dan hasil pencarian gambar kategori Bunga Mawar ..................................................................................... 66 Tabel 4. 14 Hasil Pengukuran jarak fitur Warna kategori Bunga Mawar ............. 68 Tabel 4. 15 Hasil Pengukuran jarak fitur Tekstur kategori Bunga Mawar ........... 68 Tabel 4. 16 Hasil Pengukuran jarak fitur Bentuk kategori Bunga Mawar ............ 68 Tabel 4. 17 Hasil pengujian cluster kategori Bunga Mawar ................................. 69 Tabel 4. 18 Hasil pengujian pencarian gambar kategori Bunga Mawar ............... 69
xiii
Tabel 4. 19 Hasil Pengukuran clustering dan hasil pencarian gambar kategori Bus ............................................................................................................................... 71 Tabel 4. 20 Hasil Pengukuran jarak fitur Warna kategori Bus ............................. 72 Tabel 4. 21 Hasil Pengukuran jarak fitur Tekstur kategori Bus ............................ 72 Tabel 4. 22 Hasil Pengukuran jarak fitur Bentuk kategori Bus ............................ 73 Tabel 4. 23 Hasil pengujian cluster kategori Bus ................................................. 73 Tabel 4. 24 Hasil pengujian pencarian gambar kategori Bus................................ 74 Tabel 4. 25 Hasil Pengukuran clustering dan hasil pencarian gambar kategori Dinosaurus .......................................................................................... 75 Tabel 4. 26 Hasil Pengukuran jarak fitur Warna kategori Dinosaurus ................. 76 Tabel 4. 27 Hasil Pengukuran jarak fitur Tekstur kategori Dinosaurus ................ 77 Tabel 4. 28 Hasil Pengukuran jarak fitur Bentuk kategori Dinosaurus ................ 77 Tabel 4. 29 Hasil pengujian cluster kategori Dinosaurus ..................................... 78 Tabel 4. 18 Hasil pengujian pencarian gambar kategori Dinosaurus.................... 78
xiv
DAFTAR ISTILAH DAN SINGKATAN
Image : merupakan istilah lain untuk gambar sebagai salah satu komponen multimedia yang memegang peranan yang sangat penting
sebagai
bentuk informasi visual. Image didefinisikan sebagai fungsi f(x,y) berukuran M baris dan N kolom, dnegan x da y merupakan koordinat, (x,y) dinamakan intensitas atau tingkat keabuan. Histogram : representasi grafis untuk distribusi warna dari citra digital atau menggambarkan penyebaran nilai-nilai intensitas pixel dari suatu citra atau bagian tertentu di dalam citra. Dari sebuah histogram dapat diketahui frekuensi kemunculan relative dari intensitas pada citra, kecerahan, dan kontas dari sebuah gambar. Clustering : merupakan proses klasifikasi yang tidak terlatih (unsupervised learning) terhadap suatu data/pattern/feature vector menjadi beberapa kelompok atau cluster berdasarkan kemiripannya Image Retrieval : merupakan sistem computer yang berfungsi untuk menjelajah, mencari, mengurutkan dan mengembalikan citra dari kumpulan basis data citra yang besar. CLUE: Teknik penemuan cluster suatu citra dilakukan dengan mengurutkan citra, pencarian citra dan kesamaan antar citra. Self Organizing Map : Jaringan Kohonen merupakan salah satu bentuk topologi dari Unsupervised Artificial Neural Network (Unsupervised ANN) dimana dalam proses pelatihannya tidak memerlukan pengawasan (target output). Jaringan Kohonen/SOM digunakan untuk mengelompokkan (clustering) data berdasarkan karakteristik/fitur-fitur data.
xv
