PENCARIAN ISI CITRA MENGGUNAKAN METODE MINKOWSKI DISTANCE Budi Hartono1, Veronica Lusiana2 Program Studi Teknik Informatika, Fakultas Teknologi Informasi, Universitas Stikubank Semarang Jl Tri Lomba Juang No 1 Semarang Telp. (0224) 8311668 E-mail:
[email protected],
[email protected]
ABSTRAK Penelitian ini akan berkaitan dengan pencarian isi citra menggunakan metode pengukuran jarak Minkowski.Untuk mencari data citra yang mirip dengan citra query dapat dilakukan denganmenghitung jarak menggunakan metode Minkowski distance, yaitu jarak Manhattan/CityBlock (c=1), jarak Euclidean (c=2), dan jarak Chebyshev , dengan citra query berukuran 128X128 piksel. Untuk proses ekstraksi fitur tekstur citra menggunakan matriks intensitas cooccurrence atau Grey-Level Co-Occurrence Matrix (GLCM).Hasil penelitian diperoleh pencarian citra menggunakan jarak Manhattan/City Block relatif baik untukcitra yang kaya akan tekstur. Sedangkan hasil pencarian citra menggunakan jarak Euclideancukup baik untuk citra yang didalamnya terdapat satu atau beberapa obyek.Diharapkan melalui penelitian ini akan menghasilkan model yang dapat diimplementasikan pada perangkat lunak temu kembali citra. Kata Kunci:pencarian isi citra, Minkowski distance, jarak Manhattan/City Block, jarak Euclidean 8.
PENDAHULUAN Pencarian citra menjadi salah satu topik penelitian pada bidang pengolahan citra yang terus berkembang, dalam usaha untuk meningkatkan akurasi hasil pencarian.Pencarian citra bertujuan untuk menemukan data citra yang mirip dengan citra query. Diharapkan untuk data citra yang memiliki kesamaan atau kemiripan obyek dengan citra query maka proses pencarian dapat mengenalinya. Metode pengukuran kemiripan citra dapat dilakukan dengan cara menentukan tingkat kemiripan (similarity degree) atau tingkat ketidaksamaan (dissimilarity degree) dua buah atau lebih vektor ciri yang dimiliki citra. Disini vektor ciri citra diperoleh melalui proses ekstraksi fitur citra. Vektor data citra akan dibandingkan dengan vektor citra query. Tingkat ketidaksamaan digambarkan oleh suatu nilai yang menunjukan berapa besar jarak (distance) yang dimiliki oleh vektor data citra terhadap citra query. Semakin besar jarak maka data citra semakin berbeda atau tidak mirip dengan citra query. Apabila jarak sama dengan nol maka data citra adalah sama dengan citra query. Pengukuran tingkat ketidaksamaan vektor ciri dapat diterapkan untuk berbagai jenis data, tidak sebatas pada data citra. Beberapa metode pengukuran yang umum digunakan antara lain: Minkowski distance, Hamming distance, Mahalanobis distance, Canberra distance, dan lain-lain. Penelitian ini akan berkaitan dengan pencarian citra menggunakan metode pengukuran jarak Minkowski. Tujuan dari penelitian ini adalah mengetahui langkah-langkah yang digunakan untuk menghitung tingkat ketidaksamaan citra menggunakan metode pengukuran jarak Minkowski. Diharapkan melalui penelitian ini akan menghasilkan model yang dapat diimplementasikan pada perangkat lunak temu kembali citra. 9.
TINJAUAN PUSTAKA
1.1. Minkowski Distance Jarak Minkowski seperti dapat dilihat pada Persamaan 1 digunakan untuk menghitung jarak dua buah atau lebih vektor (p,q), yang didalamnya memuat variasi nilai c. Pengukuran jarak Minkowski meliputi:
34
d(p,q)=max( |p1 - p2| , |q1 - q2| ) Jarak Euclidean adalah metode pengukuran yang paling sering digunakan. Jarak Euclidean menghitung akar dari kuadrat perbedaan dua buah atau lebih vektor. Metode ini dapat digunakan untuk mendeteksi tingkat ketidaksamaan citra dengan cara mengisi nilai vektor p dan q dengan nilai fitur citra yang akan dideteksi tingkat ketidaksamaannya. Pada hasil penghitungan jarak Euclidean, semakin kecil skor d(p,q) maka semakin mirip kedua vektor fitur yang dicocokan. Metode pengukuran jarak ini dipakai oleh para peneliti yaitu Zhang dan Huang (2014) untuk menghitung nilai beberapa macam fitur pada aplikasi CBIR, D. Joshi dkk (2014) untuk mengerjakan re-ranking pada penerapan pencarian citra, dan Putra (2009) untuk beberapa kasus pada sistem biometrika. Jarak Euclidean untuk tiga buah fitur (x,y,z) dapat dihitung menggunakan Persamaan 5, sementara itu untuk n buah fitur (p1, p2 n) dapat dihitung menggunakan Persamaan 6.
1.2. Ekstraksi fitur (feature extraction) Aplikasi ekstraksi fitur secara lebih mendalam dijelaskan oleh Nixon dan Aguado (2012). Pada penelitian ini ekstraksi fitur tekstur pada citra menggunakan matrik intensitas co-occurrence atau dikenal dengan istilah Grey-Level Co-Occurrence Matrix (GLCM).Matrikintensitasco-occurrence digunakan untuk menghitung fitur tekstur seperti: entropi, energi, kontras, dan homogenitas. Fitur tekstur yang lain, seperti: nilai rata-rata (mean) intensitas dan deviasi standar dapat diperoleh melalui perhitungan statistik (Ahmad, 2005). Berikut ini adalah persamaan untuk menghitung fitur tekstur yang akan digunakan pada penelitian ini.
Nilai deviasi standar ( ) didefinisikan sebagai berikut:
Nilai entropi digunakan untuk mengukur keacakan dari distribusi intensitas yang didefinisikan sebagai berikut:
Nilai entropi akan maksimum apabila semua elemen p(i 1,i2) sama, yaitu tidak terdapat susunan tertentu dalam pasangan intensitas dengan jarak vektor d tertentu.
10. HASIL DAN PEMBAHASAN 1.1. Proses Penelitian Proses untuk menemukan citra disini dilakukan menggunakan metode pengukuran jarak Minkowski, yang meliputi: Manhattan/City Block distance, Euclidean distance, dan Chebyshev distance, dengan cara mengukur jarak antara fitur yang yang dimiliki oleh citra query dengan fitur data citra. Hasil perhitungan jarak ini selanjutnya dicatat 35
ke dalam sebuah tabel peringkat yaitu data jarak diurutkan secara urut menaik (ascending), dengan peringkat pertama adalah citra query yang memiliki jarak nol. Pada peringkat kedua dan seterusnya adalah jarak yang dimiliki data citra terhadap citra query. Hasil pencarian citra adalah sepuluh data citra yang berhasil ditemukan dengan jarak terdekat terhadap citra query. Disini akan ditampilkan nomor urut data citra, nama berkas data citra, dan jarak Minkowski. Proses penelitian selengkapnya dapat dilihat pada Gambar 1.
Gambar 1 Blok proses penelitian Penelitian ini menggunakan dua macam ukuran data citra yaitu 512X512 dan 256X256 piksel, dengan citra query berukuran 128X128 piksel. Proses penyesuaian ukuran data citra dengan citra query dikerjakan menggunakan pendekatan model sub-citra bertingkat (Hartono dan Lusiana(2016)). Bahan penelitian adalah citra digital yang berasal dari pengambilan langsung di lapangan, dan datasets dari Cross Language Evaluation Forum (CLEF) (http://www.imageclef.org/wikidata, http://vision.stanford.edu)dan Computational Visual Cognition Laboratory, Massachusetts Institute of Technology (http://cvcl.mit.edu/database.htm). 1.2. Pencatatan Hasil Pencarian Citra Hasil pencarian citra disimpan ke dalam berkas teks yang berisi nomor, nama berkas citra, dan jarak antara citra query dengan data citra. Pada baris pertama yaitu nomor nol adalah hasil pencarian data citra yang sama dengan citra query itu sendiri sehingga jarak sama dengan nol, sedangkan baris berikutnya adalah data citra lain hasil pencarian. Contoh pencatatan hasil pencarian citra dapat dilihat pada Tabel 1 dan Tabel 2. Tabel 1 Sepuluh data citra termirip dengan citra query 25090018
Data citra dengan jarak yang semakin kecil atau semakin mendekati nol adalah citra yang paling mirip dengan citra query. Data citra hasil pencarian dapat dilihat pada Gambar 2, Gambar 3, dan Gambar 4, disini ditampilkan citra query beserta 4 buah citra yang paling mirip dengannya.
36
Tabel 2 Sepuluh data citra termiripdengan citra query 15090043
1.3. Hasil Pencarian Citra Menggunakan Metode Minkowski Distance Hasil pencarian citra menggunakan metode Minkowski Distance dapat dilihat pada Gambar 2, Gambar 3, dan Gambar 4. Hasil pencarian citra menggunakan jarak Manhattan/City Block (c=1) relatif baik untuk citra yang kaya akan tekstur, seperti dapat dilihat pada Gambar 3. Pada hasil pencarian citra menggunakan jarak Eucl idean (c=2) cukup baik untuk citra yang didalamnya terdapat satu atau beberapa obyek, seperti dapat dilihat pada Gambar 2 dan Gambar 4. Pada Gambar 2, citra query menggunakan berkas 13090002, dan diperoleh hasil empat buah data citra terbaik yaitu data citra peringkat pertama dengan nama berkas 13004015 memiliki jarak 2,60, peringkat kedua dengan nama berkas 24019014 memiliki jarak 3.63, peringkat ketiga dengan nama berkas 13004006 memiliki jarak 8,61, dan peringkat keempat dengan nama berkas 13019012 memiliki jarak 9,09.
Gambar 2 Hasil pencarian citra query 13090002 Pada Gambar 3, citra query menggunakan berkas 25090018, dan diperoleh hasil empat buah data citra terbaik yaitu data citra peringkat pertama dengan nama berkas 15028014 memiliki jarak 1,63, peringkat kedua dengan nama berkas 15029023 memiliki jarak 1.65, peringkat ketiga dengan nama berkas 15019008 memiliki jarak 1,74, dan peringkat keempat dengan nama berkas 25029018 memiliki jarak 1,85.
37
Gambar 3 Hasil pencarian citra query 25090018
Gambar 4 Hasil pencarian citra query 15090043 Pada Gambar 4, citra query menggunakan berkas 15090043, dan diperoleh hasil empat buah data citra terbaik yaitu data citra peringkat pertama dengan nama berkas 25030015 memiliki jarak 1,25, peringkat kedua dengan nama berkas 25028006 memiliki jarak 1.60, peringkat ketiga dengan nama berkas 15026004 memiliki jarak 1,87, dan peringkat keempat dengan nama berkas 25004029 memiliki jarak 1,91.
38
11. KESIMPULAN DAN SARAN Pada pencarian citra menggunakan jarak Manhattan/City Block (c=1) relatif baik untuk mencari citra yang kaya akan tekstur. Sedangkan pada pencarian citra menggunakan jarak Euclidean (c=2) cukup baik untuk mencari citra yang didalamnya terdapat sebuah atau beberapa buah obyek. Pada penelitian ini data citra belum dikelompokan sesuai dengan jenis-jenis obyek yang ada didalamnya. Menambah koleksi data citra yang telah dikelompokan berdasarkan antara lain keterangan lokasi, kesamaan obyek, tema, dapat memperbaiki hasil pencarian isi citra.
UCAPAN TERIMA KASIH Penelitian ini difasilitasi oleh Lembaga Penelitian dan Pengabdian Masyarakat UniversitasStikubank Semarang Tahun 2016.
DAFTAR PUSTAKA Ahmad, U. (2005). Pengolahan Citra Digital dan Teknik Pemrogramannya.Yogyakarta: Graha Ilmu. Davis, L.S., Johns, S.A. & Aggarwal, J.K. (1979). Texture Analysis Using Generalized Co-Occurrence Matrices. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-1, no. 3, pp. 251 259. Deselaers, T., Keysers, D.& Ney, H. (2008). Features for image retrieval: an experimental comparison. Inf Retr., vol. 11, no. 2, pp. 77 107. Gonzalez, R.C. & Woods, R.E. (2008). Digital image processing, 3rd ed.Upper Saddle River, N.J.: Prentice Hall. Hartono, B. & Lusiana, V. (2016). Model of Multilevel Sub-Image to Find the Position of Region of Interest. Scientific Journal of Informatics, Vol. 3, No. 2, hal. 189 - 196. Joshi, M.D., Deshmukh, R.M., Hemke, K.N., Bhake, A., & Wajgi, R. (2014). Image Retrieval and Re-Ranking Techniques - A Survey. Signal & Image Processing Journal, vol. 5, no. 2, pp. 1 14. Nixon, M.S. & Aguado, A.S. (2012). Feature Extraction and Image Processing for Computer Vision. Academic Press. Putra, D. (2009). Sistem Biometrika, Konsep Dasar, Teknik Analisis Citra, dan Tahapan Membangun Aplikasi Sistem Biometrika. Yogyakarta: Andi. Zhang, C. & Huang, L. (2014). Content-Based Image Retrieval Using MultipleFeatures. Journal of Computing and Information Technology, vol. 22, no. 0, pp. 1 10.
39
