IMPLEMENTASI TEMU KEMBALI CITRA BERBASIS ISI DENGAN FITUR TITIK-TITIK SIGNIFIKAN Rifky Alif Tama1, Nanik Suciati2, Arya Yudhi Wijaya3 Teknik Informatika, Fakultas Teknologi Informasi, ITS email :
[email protected],
[email protected],
[email protected]
dibutuhkan pengguna. Sebab, pada umumnya proses pencarian citra dilakukan dengan memasukkan input atau query berupa teks, sedangkan citra tidak selalu dapat terdeskripsikan secara keseluruhan kedalam suatu teks. Agar pencarian menjadi efektif, yakni hasil nantinya sesuai dengan isi citra yang diinginkan, maka input atau query yang digunakan dalam sistem pencarian haruslah suatu citra pula. Oleh karena itu, perlu dikembangkan metode pencarian citra untuk mempermudah pencarian data dengan proses mencocokkan isi citra-nya. Metode inilah yang dinamakan sistem temu kembali citra berdasakan isi atau contentbased image retrieval (CBIR). Metode CBIR ini mencari citra dengan mencocokkan content dari representasi suatu citra yang dapat berupa komposisi tekstur, bentuk, maupun warna. Terdapat banyak teknik CBIR yang telah dilakukan saat ini dimana pada beberapa teknik tersebut menerapkan metode pendekatan CBIR konvensional. Metode tersebut merepresentasikan citra menjadi kumpulan fitur, yang kemudian dinamakan sebagai suatu vektor fitur. Tiap fitur hanya akan mewakili satu property, seperti warna, tekstur, bentuk, dan lain-lain. Untuk itu diperlukan pemilihan fitur yang optimal dan cocok untuk tipe tertentu, dimana fitur komponennya dapat juga bervariasi berdasarkan keperluan. Citra natural, yakni citra yang menggambarkan keadaan alam, pada umumnya terdiri atas edge dan corner, dimana letaknya didefinisikan oleh posisinya masing-masing. Fitur inilah yang dinamakan visually significant [1] dan memiliki proporsi tinggi mengenai informasi yang terkandung dalam suatu citra. Gagasan inilah yang diusulkan dalam tugas akhir ini. Teknik yang diusulkan dalam tugas akhir ini berdasarkan asumsi bahwa dua citra yang sama secara visual, akan memiliki kesamaan dalam hal karakteristik secara visual. Representasi yang mewakili karakteristik lokal dari bagian tersebut merupakan hal yang sangat penting dalam proses menghasilkan suatu kesimpulan.
ABSTRAKSI Perkembangan teknologi informasi dan multimedia menyebabkan jumlah citra meningkat tajam. Namun sayangnya, hal tersebut tidak diiringi dengan metode pencarian citra yang efektif. Metode pencarian yang sebelumnya masih merupakan pencarian berbasis teks yang merepresentasikan isi citra. Cara ini dinilai kurang efektif, sebab tidak selalu setiap citra dapat terdeskripsikan isinya dalam suatu teks. Oleh karena itu dalam Tugas Akhir ini diusulkan metode pencarian berdasarkan isi citra dengan fitur titik-titik signifikan. Sebelum citra diproses, dilakukan preprocessing, kemudian dilakukan tahap ekstraksi fitur, yakni ekstraksi titik-titik signifikan dengan cara thresholding gradient membership yang didapatkan dengan penerapan algoritma fuzzy dalam bentuk fungsi tipe S. Setelah itu, dilakukan proses komputasi warna dari titik-titik yang dihasilkan dengan momen invariant. Sehingga dihasilkan vektor fitur yang digunakan untuk menentukan kemiripan antar citra dengan algoritma penghitungan jarak menggunakan Canberra distance. Uji coba dilakukan pada citra berwarna (RGB) dengan menentukan threshold pada jarak untuk mengetahui kinerja terbaik sistem. Pada akhirnya, fitur titik-titik signifikan dapat digunakan untuk temu kembali citra dan dapat dikembangkan agar lebih optimal di kemudian hari. Kata kunci: Content-based Image Retrieval, Titik-titik signifikan, momen invariant, Canberra distance, Precision.
1
PENDAHULUAN
Seiring dengan perkembangan teknologi informasi, internet, dan aplikasi multimedia yang pesat, menyebabkan jumlah citra yang dikelola meningkat secara tajam. Para pengguna sangat mudah untuk mengakses ratusan bahkan ribuan citra, akan tetapi seringkali tidak mudah mendapatkan citra-citra yang sesuai dengan yang
1
Berdasarkan aspek tersebut, pendekatan teori fuzzy set diusulkan untuk menghasilkan kluster disekitar curvature points. Titik-titik ini merupakan kandidat untuk perhitungan fitur. Momen invariant dari kumpulan titiktitik yang dihasilkan tersebut digunakan sebagai fitur untuk evaluasi kesamaan antar citra.
2
Parameter c merupakan shoulder point, dimana S(x) = 1.0. Sedangkan parameter a merupakan feet point, yakni S(a;a, b, c) = 0.0, sebagaimana ditunjukkan pada Gambar 2. Untuk menentukan nilai paramater a,b, dan c pada fungsi S, dilakukan komputasi ratio of contrast diantara dua opposite pixel (Xmr) sebagaimana ditunjukkan pada persamaan (1).
EKSTRAKSI TITIK-TITIK SIGNIFIKAN
Pada tugas akhir ini, ekstraksi fitur pada citra dilakukan dengan melakukan ekstraksi titik-titik signifikan dan perhitungan fitur warna baik dari keseluruhan citra maupun titik-titik signifikan tersebut. Sehingga nantinya akan dihasilkan 6 fitur, dimana 3 fitur diperoleh dari komputasi keseluruhan citra dan 3 lainnya diperoleh dari titik-titik signifikan. Proses ekstraksi titik-titik signifikan dimulai dari inisialisasi yakni masukan berupa citra RGB kemudian dilakukan proses grayscaling. Setelah itu, untuk perbaikan citra, dilakukan proses smoothing dengan menggunakan gaussian low-pass filter.
Gambar 2 Fungsi Tipe S pada koordinat kartesian
π π₯; π, π, π
= 0 π₯βπ πβπ π₯βπ =1β2 Γ πβπ =1
=2 Γ Dataset Citra
Ekstraksi Fitur (Ekstraksi titik-titik signifikan dan komputasi fitur warna)
Database Fitur Citra
πβ€π₯β€π πβ€π₯β€π π₯β₯π (1)
Citra Query (Input)
Ekstraksi Fitur (Ekstraksi titik-titik signifikan dan komputasi fitur warna)
Perhitungan Kemiripan (Canberra Distance)
ππ π = π(π₯; π, π, π) (2)
Pengurutan (sorting) citra berdasarkan jaraknya
π₯π π = min{ππ } (3) Dimana untuk mendapatkan Xr, diperoleh dari persamaan (4) berikut.
Menentukan jumlah citra yang di-retrieve
ππ =
Citra Result (Output)
1 + π1 β π2 1 + π1 β π2 1 + π1 β π2 1 + π1 β π2 , , , 1 + π1 β π2 1 + π1 β π2 1 + π1 β π2 1 + π1 β π2
(4) Gambar 1 Diagram sistem temu kembali citra
π1 π2 π2
Proses selanjutnya adalah identifikasi extrema pada pixel, yakni plateau top dan plateau bottom. Pixel yang tidak termasuk kedalam plateau top dan bottom, atau yang dinamakan dengan collapsible pels (cp) akan disimpan untuk proses selanjutnya, yakni pada titik-titik tersebut dilakukan proses perhitungan gradient membership Β΅d(P), yang dihasilkan oleh suatu fungsi tipe S sebagaimana ditunjukkan pada persamaan (1) dan persamaan (2). Dalam fungsi tipe S atau S(x;a, b, c), parameter b merupakan titik cross-over, yakni S(b;a, b, c) = 0.5.
π1 π₯ π2
π1 π1 π2
Gambar 3 Window 3x3 untuk mencari nilai xr
Dimana a1, a2, b1, b2, c1, c2, d1, d2 diperoleh dari nilai tetangga dari suatu pixel sebagaimana ditunjukkan pada Gambar 3. Parameter a dan c dihasilkan dari nilai maximum dan minimum dari Xmr, dimana memetakan keanggotaan
2
Ο = Ξ·20 + Ξ·02
antara 0.0 hingga 1.0. Dengan thresholding pada Β΅d(P), titik-titik signifikan dapat diperoleh. .
3
(11) Setelah dilakukan proses normalized centralized moment (πππ ), maka nilai moment (Ο) dapat dihitung dengan persamaan yang ditunjukkan pada (11). Untuk setiap nilai moment (Ο) akan ada satu fitur yang dihasilkan. Untuk fitur pertama sampai dengan ketiga (f1,f2,f3), merupakan hasil perhitungan nilai moment (Ο) terhadap terms c1,c2,c3 yang perhitungannya dilakukan terhadap semua titik pada citra. Untuk fitur keempat sampai dengan keenam (f4,f5,f6), merupakan hasil perhitungan nilai moment (Ο) terhadap terms c4,c5,c6 yang perhitungannya dilakukan terhadap hanya terhadap titiktitik signifikan pada citra. Sehingga tiap citra akan memiliki vektor fitur (Fk) dengan enam komponen fitur, Fk = [f1,f2,f3,f4,f5,f6]. Vektor fitur tersebut nantinya akan digunakan dalam perhitungan kemiripan yang dilakukan dengan metode Canberra distance.
KOMPUTASI FITUR WARNA
Properties warna dari titik-titik signifikan yang dihasilkan dikomputasikan untuk menghitung invariant moments. Invarian moments dihitung dari bidang komponen dalam terms dari (c1,c2,c3) yang diperoleh dari representasi RGB citra, sebagaimana didefinisikan pada persamaan (5) berikut. c1 = arctan(R/ max(G,B)), c2 = arctan(G/ max(R,B)), c3 = arctan(B/ max(R,G)) (5) Setelah itu dilakukan proses perhitungan spatial moment dari citra, dimana suatu moments (mpq) dari orde p dan q dari suatu fungsi f (x, y) pada umumnya, didefinisikan sebagaimana persamaan (6) berikut.
4
π₯ π π¦ π π(π₯, π¦)
πππ = π₯
Proses feature extraction dilakukan untuk mendapatkan fitur dari masing-masing citra. Setelah fitur dari masing-masing citra didapatkan, maka antar citra tersebut dapat dilakukan proses untuk mengetahui kemiripan antara citra satu dengan yang lain. Proses inilah yang dinamakan proses penghitungan kemiripan (similarity measure). Banyak pilihan cara yang dapat dilakukan untuk menghitung atau mencari kemiripan. Salah satunya adalah dengan mencari jarak (distance) diantara fitur-fitur yang telah didapat. Metode pencarian jarak yang digunakan dalam tugas akhir ini yang ini menggunakan metode Canberra Distance.
π¦
(6) Kemudian untuk centralized moment didefinisikan pada persamaan (7) berikut. Dimana untuk variabel π₯ dan π¦ didapatkan dari persamaan pada (8). (π₯ β π₯ )π (π¦ β π¦)π π(π₯, π¦)
πππ = π₯
PERHITUNGAN KEMIRIPAN CITRA
π¦
(7) Untuk komputasi momen invariant, digunakan set persamaan momen invariant oleh Hu [5], yang ditunjukkan pada persamaan (11), dimana dihitung dari proses normalized centralized moment (πππ ), sebagaimana ditunjukkan pada persamaan (10). π₯ = π10 /π00 , π¦ = π10 /π00 (8) π00 = π00 π2 10 π20 = π20 β π 00 π2 01 π02 = π02 β π 00 π 10 β π 01 π11 = π11 β π 00 (9) πππ πππ = πΎ π 00 (10)
ππππ π =
ππ π β ππ π₯ π π =0 π π +π π₯ π π (12)
Canberra distance adalah fungsi yang digunakan untuk mencari jarak (distance) dari dua objek dengan fitur dari objek pertama (fj(k)) dan fitur dari objek kedua (fj(x)) serta jumlah fitur dari masing-masing objek (j). Prosesnya adalah mencari selisih dari fitur pertama objek pertama dan objek kedua kemudian dibagi dengan jumlah fitur pertama pada objek pertama dan kedua. Dan seterusnya dilakukan penjumlahan dengan fitur kedua hingga fitur ke-k. Dengan cara ini, dapat diantisipasi jika beberapa fitur yang didapatkan memiliki rentang nilai yang jauh. Misalkan fitur pertama dan kedua bernilai puluhan,
3
sedangkan fitur ketiga dan keempat bernilai ribuan. Sebab nantinya masing-masing fitur ketika akan ditambahkan dengan fitur lain untuk mencari jarak (distance) total, maka sebelumnya akan dilakukan βnormalisasiβ secara tidak langsung dengan melakukan pembagian antara selisih terhadap jumlah fiturnya. Oleh karena itu, tidak akan ada fitur yang akan dominan sebab rentang nilainya jauh berbeda dengan yang lain sehingga masing-masing fitur akan mempunyai bobot yang sama di dalam menentukan jarak (distance) antara dua objek.
5
masing kategori citra jika yang di-retrieve adalah top 10 atau 10 citra yang paling mirip dengan citra query.
Gambar 4 Salah satu citra query dari kategori food
UJI COBA DAN EVALUASI
Dalam bagian ini akan dibahas mengenai hasil uji coba sistem yang telah dirancang dan dibuat. Uji coba dilakukan untuk mengetahui apakah sistem dapat berjalan sebagaimana mestinya dengan lingkungan uji coba yang telah ditentukan serta dilakukan sesuai dengan skenario uji coba. Pengamatan terhadap uji coba yaitu pengamatan terhadap output proses sistem temu kembali citra. Proses pencarian akan menghasilkan citra-citra yang mirip dengan citra query.
5.1
Gambar 5 Hasil retrieve Top 10 dari salah satu citra dari kategori food Tabel 1 Rata-rata precision (%) dari masing-masing kategori citra jika yang di-retrieve adalah top 10
Uji coba dengan jumlah retrieve top 10
Pada uji coba dengan skenario 1, citra query yang digunakan yakni sebanyak 10 citra dari perwakilan masing-masing kategori. Citra dapat berukuran 256x384 maupun sebaliknya. Kemudian, hasil yang di-retrieve akan dibatasi yakni sebanyak 10 hasil teratas (top 10). Sebagai contoh akan diambil satu citra dari kategori βfoodβ sebagai query, sebagaimana ditunjukkan pada Gambar 4. Kemudian setelah dilakukan pencarian terhadap citra query tersebut, diambil hasil retrieve sebanyak 10 hasil teratas (top 10), sebagaimana ditunjukkan pada Gambar 5. Dari hasil pencarian tersebut, citra yang di-retrieve dan relevan sebanyak 6 (enam) buah dari total citra yang di-retrieve sebanyak 10 (sepuluh) buah. Berdasarkan perhitungan nilai precision, maka tp nya adalah 6. Sehingga untuk citra query tersebut, nilai precision-nya sama dengan 6/10 = 0,6 atau 60%. Demikian seterusnya akan dilakukan proses yang sama dengan mengambil 10 citra query dari masingmasing kategori, dengan jumlah citra yang di-retrieve sebanyak 10, kemudian dihitung nilai precision-nya, dimana hasilnya ditampilkan pada Tabel 1. Tabel 1 merupakan hasil uji coba dari skenario 1 dimana ditunjukkan rata-rata precision untuk masing-
5.2
No
Nama Kategori
1 2 3 4 5 6 7 8 9
Africa Beach Building Bus Dinosaur Elephant Horses Mountains Food Rata-rata Total
Rata- rata Precision 51,0 62,0 52,0 53,0 95,0 38,0 87,0 48,0 60,0 60,7
Uji coba dengan jumlah retrieve top 20
Pada uji coba dengan skenario 2, citra query yang digunakan yakni sebanyak 10 citra dari perwakilan masing-masing kategori. Citra dapat berukuran 256x384 maupun sebaliknya. Kemudian, hasil yang di-retrieve akan dibatasi yakni sebanyak 20 hasil teratas (top 20). Sebagai contoh akan diambil satu citra dari kategori βhorsesβ sebagai query, sebagaimana ditunjukkan pada Gambar 6. Kemudian setelah dilakukan pencarian terhadap citra query tersebut, diambil hasil retrieve sebanyak 20 hasil teratas (top 20), sebagaimana ditunjukkan pada Gambar . Dari hasil pencarian tersebut, citra yang di-retrieve dan relevan sebanyak 14 (empatbelas) buah dari total citra yang di-retrieve sebanyak 20 (duapuluh) buah.
4
Berdasarkan perhitungan nilai precision, maka tp nya adalah 14. Sehingga untuk citra query tersebut, nilai precision-nya sama dengan 14/20 = 0,7 atau 70%. Demikian seterusnya akan dilakukan proses yang sama dengan mengambil 10 citra query dari masingmasing kategori, dengan jumlah citra yang di-retrieve sebanyak 20, kemudian dihitung nilai precision-nya, dimana hasilnya ditampilkan pada Tabel 2. Tabel 2 merupakan hasil uji coba dari skenario 2 dimana ditunjukkan rata-rata precision untuk masingmasing kategori citra jika yang di-retrieve adalah top 20 atau 20 citra yang paling mirip dengan citra query.
5.3
Uji coba dengan jumlah retrieve top 40
Pada uji coba dengan skenario 3, citra query yang digunakan yakni sebanyak 10 citra dari perwakilan masing-masing kategori. Citra dapat berukuran 256x384 maupun sebaliknya. Kemudian, hasil yang di-retrieve akan dibatasi yakni sebanyak 40 hasil teratas (top 40). Tabel 3 merupakan hasil uji coba dari skenario 3 dimana ditunjukkan rata-rata precision untuk masingmasing kategori citra jika yang di-retrieve adalah top 40 atau 40 citra yang paling mirip dengan citra query. Tabel 3 Rata-rata precision (%) dari masing-masing kategori citra jika yang di-retrieve adalah top40
Gambar 6 Salah satu citra query dari kategori horses
5.4
No
Nama Kategori
1 2 3 4 5 6 7 8 9
Africa Beach Building Bus Dinosaur Elephant Horses Mountains Food Rata-rata Total
Rata- rata Precision 36,5 38,0 39,3 36,5 89,5 24,3 47,8 30,5 34,8 41,9
Analisis Hasil Uji Coba
Dari ketiga uji coba yang telah dilakukan, dapat terlihat bahwa dengan semakin banyaknya citra yang diretrieve, rata-rata precisionnya semakin berkurang. Hal ini dikarenakan jika jumlah citra relevan yang dikembalikan sebagian besar muncul pada hasil teratas terus menerus, maka ketika jumlah retrieve nya diperbesar, akan menyebabkan rasio pembagi, yakni jumlah retrieve menjadi lebih besar, sedangkan jumlah citra relevannya tetap ataupun bertambah sedikit. Oleh karena itu, tingkat precision-nya menurun. Beberapa kategori yang lain memiliki nilai precision yang kurang baik dikarenakan dataset citra yang dimiliki oleh masing-masing kategori, tidak seluruhnya dapat merepresentasi nama semantik yang diberikan. Selain itu, kemiripan antar citra dalam satu kategori juga kurang, sehingga ketika dilakukan ekstraksi titik-titik yang signifikan dan perhitungan fitur warna, akan dihasilkan karakteristik titik-titik yang berbeda pula.
Gambar 7 Hasil retrieve Top 20 dari salah satu citra dari kategori horses Tabel 2 Rata-rata precision (%) dari masing-masing kategori citra jika yang di-retrieve adalah top 20 No Nama Kategori Rata- rata Precision 1 Africa 44,5 2 Beach 49,0 3 Building 45,5 4 Bus 44,5 5 Dinosaur 94,0 6 Elephant 28,0 7 Horses 66,5 8 Mountains 38,5 9 Food 47,5 Rata-rata Total 50,9
5
Sedangkan untuk kategori dinosaur dan horses memiliki rata-rata precision paling baik diantara kategori lain berturut-turut dengan 92.83% dan 67.08%. hal tersebut dikarenakan dataset citra yang terdapat pada dua kategori tersebut memiliki karakteristik citra yang dapat dibedakan dengan jelas dengan kategori lain. Kategori dinosaur memiliki karakteristik warna yang khas, yakni memiliki background dominan kuning, dengan kuning muda pada bagian atas dan kuning tua pada bagian bawah, kemudian objek dinosaurus di tengah. Kategori horses juga memiliki karakteristik khas, yakni sebagian besar citra memiliki warna background dominan hijau berupa rerumputan, dan dua objek kuda didepannya.
REFERENSI [1] D.G. Lowe, Perceptual Organization and Visual Recognition, Kluwer Academic Publishers, USA, 1985. [2] R.C. Gonzalez dan Woods, R.E. Digital image processing. Prentice-Hall, Engelwood Cliffs, NJ, 1989. [3] Clifford Watson. 2011. Low Pass Filters,
. [4] S. Deb, Wahab, H.A., Arya, A., Boregowda, L.R., Chan, Y.K., Chen, S.C. 2004. Multimedia Systems and Content-Based Image Retrieval. Idea Group Publishing.
Tabel 4 Rata-rata precision keseluruhan dari masingmasing kategori citra Rata-rata precision Rata-rata Nama precision No Top Top Top Kategori total tiap 10 20 40 kategori 1 Africa 51,0 44,5 36,5 44,0 2 Beach 62,0 49,0 38,0 49,7 3 Building 52,0 45,5 39,3 45,6 4 Bus 53,0 44,5 36,5 44,7 5 Dinosaur 95,0 94,0 89,5 92,8 6 Elephant 38,0 28,0 24,3 30,1 7 Horses 87,0 66,5 47,8 67,1 8 Mountains 48,0 38,5 30,5 39,0 9 Food 60,0 47,5 34,8 47,4
6
[5] M. K. Hu, Visual Pattern Recognition by Moment Invariants, IEEE Trans. Inf. Theory 12, 179-187 (1962)\ [6] M. Banerjee, M.K. Kundu, P. Maji, Content based image retrieval using visually significant point features. Computer Vision, Graphics and Image Processing, ICVGIP 2004, India, 2004, pp. 399β404.
KESIMPULAN
Kesimpulan yang diperoleh berdasarkan uji coba dan analisis hasil yang telah dilakukan adalah sebagai berikut : 1. Sistem temu kembali citra berbasis isi dengan fitur titik-titik signifikan berhasil melakukan retrieval dengan baik (rata-rata precision keseluruhan untuk 10, 20 dan 40 citra teratas berturut-turut sebesar 60,7 %, untuk 20 citra teratas sebesar 50,9 %, untuk 40 citra teratas sebesar 41,9 %). 2. Jumlah citra yang di-retrieve dari sistem temu kembali citra berbanding terbalik dengan nilai precision-nya, dimana semakin banyak citra yang di-retrieve, maka nilai precision-nya semakin berkurang. 3. Kategori pada dataset citra yang anggotanya memiliki karakteristik yang sama, akan memberikan nilai precision yang tinggi.
6
