Jurnal Penelitian Teknik Elektro dan Teknologi Informasi _______________________________________________________________________________
PENERAPAN ALGORITMA KOMPRESI JPEG DAN METODE FUZZY C-MEANS PADA KOMPRESI CITRA BERBASIS ENTROPI Dika Asoka Masatu1, Indah Soesanti2, Hanung Adi Nugroho3 Abstract—Advances in technology demand information to be processed, stored and delivered rapidly. Digital image is an information in the form of 2D which require memory as a media of storage. Image compression is necessary to optimize storage usage. In this paper, an entropy-based image compression will be generated using JPEG. This entropy-based image compression will be tested on image with 2 different types of initial compression format, “.jpg” and “.png”. Before compressed, an image will be grouped into clusters based on its information with the help of Fuzzy C-Means. Information contained within each clusters can be seen from its entropy. Then each clusters will be compressed using JPEG with different quality scale based on its information contained. Final results obtained is complete image formed from all clusters. Where cluster with low entropy will not be compressed and cluster with high entropy will be compressed. Keywords— entropy, Fuzzy C-Means, JPEG, image compression Intisari—Kemajuan teknologi menuntut informasi yang diproses, disimpan dan dikirim secara cepat. Citra digital adalah informasi berbentuk 2D yang membutuhkan memori sebagai media penyimpanannya. Kompresi citra dibutuhkan untuk mengoptimalkan penggunaan memori tersebut. Dalam makalah ini akan diterapkan kompresi citra berbasis entropi menggunakan JPEG. Kompresi citra berbasis entropi ini akan diujikan pada citra dengan 2 jenis format penyimpanan awal yang berbeda, yaitu “.jpg” dan “.png”. Sebelum dikompresi, citra akan dikelompokkan menjadi cluster-cluster tersendiri sesuai dengan kandungan informasinya dengan bantuan Fuzzy CMeans. Kandungan informasi dalam tiap cluster dapat dilihat berdasarkan nilai entropi. Kemudian masingmasing cluster akan dikompresi dengan JPEG dengan skala kualitas yang berbeda-beda sesuai kandungan 1Mahasiswa
Jurusan Teknik Elektro dan Teknologi Informasi, Fakultas Teknik, Universitas Gadjah Mada, Jl. Nyi Pembayun, Yogyakarta 55172 INDONESIA (tlp: +6281808577925; e-mail:
[email protected]) 2,3Dosen Jurusan Teknik Elektro dan Teknologi Informasi, Fakultas Teknik, Universitas Gadjah Mada, Jl. Grafika No. 2 Kampus UGM, Yogyakarta 55281 INDONESIA (telp: +62-274-552305; fax: +62-274552305; e-mail:
[email protected], email:
[email protected]
informasinya. Hasil akhir yang didapat berupa citra keluaran utuh hasil penggabungan dari semua cluster. Dimana cluster dengan nilai entropi yang rendah tidak akan dikompresi dan cluster dengan nilai entropi yang tinggi akan dikompresi. Kata Kunci— entropi, Fuzzy C-Means, JPEG, kompresi citra
I. PENDAHULUAN Citra digital adalah informasi yang berada dalam bidang dua dimensi. Ukuran citra digital dinyatakan dalam pixel (picture element). Sebuah citra digital dengan dimensi 100x200 pixel tersusun atas 100x200 = 20.000 pixel. Citra digital membutuhkan memori sebagai media penyimpanannya. Karena pada kenyataannya kebanyakan citra mengandung duplikasi data, sehingga akan terjadi pemborosan tempat [1]. Maka penghematan memori tersebut dapat dilakukan dengan melakukan kompresi citra. Teknik kompresi citra dapat dibagi ke dalam dua kelompok, yaitu metode lossless dan lossy. Metode lossless akan mampu menghasilkan citra dekompresi yang sama persis dengan citra semula, namun rasio kompresi yang dihasilkan kecil. Sedangkan metode lossy akan menghasilkan rasio kompresi yang tinggi dengan mengorbankan kualitas dan kemampuan untuk mengembalikan citra ke ukuran aslinya [2]. Penelitian terkait kompresi dengan penyandian entropi telah dilakukan oleh beberapa peneliti terdahulu, namun belum menerapkan Fuzzy c-Means Cultering. Penelitian ini dibuat sebagai usaha untuk mengefisiensikan penggunaan memori dalam kompresi citra. Kompresi hanya akan dilakukan pada bagian tertentu yang dianggap bukan informasi penting yang perlu dipertahankan. Metode yang diterapkan adalah klasifikasi citra berupa clustering untuk memisahkan objek utama dan latar. Kemudian Algoritma kompresi yang digunakan adalah JPEG. A. Citra Sebuah citra adalah isyarat berbentuk dua dimensi yang diproses melalui interpretasi visual oleh mata manusia. Isyarat tersebut awalnya berbentuk analog, untuk mempermudah dalam pemrosesan dan penyimpanan maka isyarat tersebut diubah ke bentuk digital. Satu-satunya cara untuk mengoptimalkan
7 Volume 1 Nomor 1, April 2014 _______________________________________________________________________________
Artikel Reguler _____________________________________________________________________________ penyimpanan citra digital saat ini adalah dengan melakukan kompresi citra. B. Entropi Entropi adalah pengukuran informasi yang didapat melalui observasi dari data, dalam hal ini berupa tingkat keacakan dalam penyebaran distribusi data [3]. Jika nilai pixel dalam sebuah citra terdistribusi secara merata, maka kandungan entropi yang dimiliki akan maksimum. Namun jika pixel yang dimiliki hanya satu nilai saja maka entropi yang dimiliki akan bernilai nol. C. Clustering Pengelompokkan data (clustering) merupakan proses membagi data dalam suatu himpunan ke dalam beberapa kelompok dimana kesamaan data dalam suatu kelompok lebih besar dibandingkan kesamaan data dalam kelompok lain [4]. Dalam hard clustering, sebuah data hanya menjadi anggota dalam satu kelompok tertentu dan tidak menjadi anggota dalam kelompok lain. Sedangkan dalam fuzzy clustering, level keanggotaan yang dimiliki oleh suatu data dapat bernilai antara rentang [0,1]. D. Fuzzy C-Means Salah satu dari beberapa Algoritma fuzzy clustering yang banyak digunakan adalah Fuzzy C-Means (FCM) [5]. Konsep dasar dari Algoritma FCM adalah menentukan pusat cluster yang akan menandai lokasi rerata dari cluster tersebut. Pusat cluster awal pada umumnya ditentukan secara acak. Kemudian menentukan level keanggotaan pada tiap data sesuai dengan jaraknya terhadap pusat cluster. Lalu jika isi dari tiap cluster sudah tidak berubah lagi maka iterasi dihentikan. Jika masih terus berubah maka perbaikan pusat cluster dan level keanggotaan akan dilakukan terus sampai isi dalam cluster tidak berubah lagi. E. Inisialisasi Pusat Cluster FCM Penentuan pusat awal cluster secara acak dalam FCM memiliki kelemahan. Kelemahan tersebut berupa ada kemungkinan akan menghasilkan keluaran yang berbeda-beda meskipun dengan masukan yang sama. Ada banyak studi literatur yang sudah dilakukan untuk mengatasi kelemahan Algoritma FCM tersebut [6]. Dalam makalah ini, penulis akan menggunakan pendekatan heuristik dari metode Furthest First. F. JPEG Joint-Photograpic Experts Group (JPEG) adalah sebuah kelompok yang merancang sebuah Algoritma kompresi citra lossy. JPEG lebih dikenal secara umum sebagai salah satu format ekstensi penyimpanan citra (“.jpg”). Tujuan utama dari kompresi JPEG sederhana, yaitu untuk menyimpan data yang digunakan dalam representasi digital dengan ukuran sekecil mungkin dengan tetap mempertahankan detil visualnya [2]. JPEG bekerja dengan cara merubah citra spasial dan merepresentasikannya ke dalam pemetaan frekuensi dengan bantuan Discrete Cosine Transform (DCT).
II. METODOLOGI PENELITIAN Pada flowchart yang terdapat dalam Gbr 1 akan dijelaskan mengenai urutan proses yang terjadi dalam melakukan kompresi citra berbasis entropi ini. Citra masukan akan dibaca, kemudian dilakukan penentuan inisialisasi pusat awal cluster. Lalu isi dari tiap cluster akan terus diperbaiki dengan FCM sampai konvergen. Perhitungan entropi akan menentukan skala kualitas (Q) yang akan diberikan dalam kompresi JPEG untuk tiap cluster. Hasil akhir berupa penggabungan semua cluster sehingga menghasilkan sebuah citra utuh. III. PEMBAHASAN Dalam bagian ini akan dijelaskan lebih lanjut pembahasan serta langkah-langkah dilakukannya pengujian dalam makalah ini. Dalam pengujian pada makalah ini, jumlah cluster yang digunakan sebanyak 6 buah. Adapun citra uji yang digunakan dalam pengujian ini ditunjukkan dalam Gbr 2. START
baca citra masukan
inisialisasi pusat awal cluster
hitung entropi tiap cluster dan tentukan skala kualitas (Q) kompresi tiap cluster dengan JPEG sesuai Q masing-masing
gabungkan semua cluster kelompokkan citra dengan FCM
tampilkan citra keluaran
END
Gbr 1. Flowchart kompresi citra berbasis entropi.
Gbr 2. Citra uji yang digunakan (a)clownfish (b)duck (c)jet TABEL 1 SPESIFIKASI CITRA UJI YANG DIGUNAKAN.
Nama Citra clownfish duck jet
Ekstensi File “.jpg” “.png” “.jpg” “.png” “.jpg” “.png”
Lebar Pixel 500 x 500 494 x 508 480 x 320
Ukuran 23.1 KB 250 KB 63,8 KB 474 KB 22,3 KB 232 KB
8 Volume 1 Nomor 1, April 2014 _______________________________________________________________________________
Jurnal Penelitian Teknik Elektro dan Teknologi Informasi _______________________________________________________________________________ Spesifikasi dari masing-masing citra uji yang akan digunakan ditunjukkan dalam TABEL 1. Dalam makalah ini, tiap citra uji yang digunakan terdiri dari 2 format penyimpanan awal, yaitu “.jpg” dan “.png”. A. Pusat Awal dan Pusat Akhir Cluster Inisialisasi pusat awal cluster ini dilakukan melalui pendekatan heuristik dari metode Furthest First. Inisialisasi pusat awal ini dilakukan sebelum diterapkannya Algoritma FCM. Hasil yang diperoleh pada citra clownfish dalam inisialisasi pusat awal cluster ini ditunjukkan dalam Gbr 3. Bagian yang bukan merupakan anggota dari cluster yang bersangkutan ditandai dengan pixel hitam (0,0,0 dalam RGB).
Gbr 3. Objek yang terdapat pada masing-masing cluster dalam inisialisasi pusat awal pada citra clownfish (a)”.jpg” dan (b)”.png”.
Hasil dari pengujian pusat akhir cluster didapatkan setelah melakukan clustering dengan FCM. Hasil yang diperoleh pada citra clownfish setelah isi dari masingmasing cluster tidak berubah lagi ditunjukkan dalam Gbr 4.
Dari perbandingan antara Gbr 3 dan Gbr 4 dapat terlihat bahwa terjadi sedikit perubahan anggota dalam tiap cluster. Hal tersebut menandakan bahwa inisialisasi yang dilakukan sudah cukup baik, sehingga hanya perlu sedikit iterasi untuk melakukan perubahan agar hasil akhirnya konvergen. Dapat terlihat juga bahwa proses clustering yang berbeda terjadi pada format “.jpg” dan “.png” meskipun citra ujinya sama. B. Entropi dan Penentuan Skala Kualitas Setelah semua anggota tiap cluster dalam FCM sudah tidak berubah lagi maka dapat dihitung nilai entropi dari masing-masing cluster. Dari nilai entropi yang dihasilkan maka dapat dibuat batas-batas sehingga dapat ditentukan skala kualitas (Q) yang akan digunakan dalam kompresi JPEG. Adapun batas-batas nilai entropi tersebut antara lain, apabila a. entropi <= 0,65; maka Q = 100. b. 0,65 < entropi <= 0,75; maka Q = 90. c. 0,75 < entropi <= 0,85; maka Q = 80. d. 0,85 < entropi <= 0,95; maka Q = 70. e. entropi > 0,9; maka Q = 60; Entropi yang dihasilkan dari tiap citra uji dan skala kualitasnya ditunjukkan dalam TABEL 2. Jika dalam sebuah cluster terdapat nilai pixel tertentu yang probabilitasnya besar sekali maka dapat dipastikan bahwa isi dari cluster tersebut merupakan informasi yang tidak penting dan dapat dianggap sebagai objek latar. Dalam penentuan skala kualitas, semakin penting informasi yang ada di dalamnya maka cluster tersebut hanya akan dikompresi sedikit sehingga skala kualitasnya besar. C. Kompresi JPEG Setelah diketahui skala kualitasnya maka kompresi JPEG yang berbeda dapat dilakukan pada masingmasing cluster. Hasil yang diperoleh pada citra clownfish dalam kompresi JPEG ini ditunjukkan dalam Gbr 5. Dari hasil yang terlihat dalam TABEL 2, jika ada cluster dengan nilai Q=100 maka cluster tersebut tidak akan dikompresi sama sekali. D. Citra Keluaran Setelah dikompresi, bagian terakhir merupakan penggabungan 6 cluster tersebut. Hasil akhir yang diperoleh pada citra cluster setelah 6 cluster tersebut digabungkan ditunjukkan dalam Gbr 6. Gbr 7 menunjukkan citra error yang dihasilkan, untuk bagian dari citra clownfish yang tidak mengalami perubahan pixel ditandai dengan warna putih. Dari hasil tersebut dapat terlihat bahwa keluaran yang dihasilkan oleh kedua jenis format sedikit berbeda, meskipun secara visual terlihat sama.
Gbr 4. Objek yang terdapat pada masing-masing cluster akhir pada citra clownfish (a)”.jpg” dan(b)”.png”.
9 Volume 1 Nomor 1, April 2014 _______________________________________________________________________________
Artikel Reguler _____________________________________________________________________________
Gbr 6. Perbandingan antara citra masukan (kiri) dan citra keluaran (kanan) pada citra clownfish (a)”.jpg” dan (b)”.png”.
Gbr 5. Objek yang terdapat pada masing-masing cluster setelah kompresi JPEG pada citra clownfish (a)”.jpg” dan (b)”.png”.
Gbr 7. Perbandingan citra error yang dihasilkan pada citra clownfish (a)”.jpg” dan (b)”.png”.
TABEL 2 ENTROPI DAN SKALA KUALITAS YANG DIHASILKAN TIAP CLUSTER.
Nama Citra
Ekstensi File “.jpg” “.png” “.jpg” “.png” “.jpg” “.png”
clownfish duck jet
Entropi (H) dan Skala Kualitas (Q) C1 H 0,2213 0,1573 0,3980 0,4641 0,9910 0,5564
Q 100 100 100 100 60 100
C2 H 0,9177 0,5982 0,5691 0,7424 0,2196 0,9168
Q 70 100 100 90 100 70
E. Waktu Kompresi Waktu yang dibutuhkan untuk melakukan kompresi pada tiap-tiap citra uji ditunjukkan dalam TABEL 3. TABEL 3 WAKTU KOMPRESI YANG DIBUTUHKAN.
Nama Citra clownfish duck jet
Ekstensi File
Waktu
“.jpg” “.png” “.jpg” “.png” “.jpg” “.png”
1 menit 35 detik 1 menit 43 detik 1 menit 15 detik 1 menit 52 detik 2 menit 51 detik 1 menit 36 detik
Berdasarkan hasil yang terlihat dalam TABEL 3, terlihat bahwa 2 dari total 3 citra uji dengan format “.png” membutuhkan waktu yang lebih lama bila dibandingkan dengan citra dengan format “.jpg”. Waktu komputasi paling lama terjadi di bagian FCM karena tiap citra membutuhkan jumlah iterasi yang berbeda-beda sebelum menghasilkan cluster akhir yang konvergen. Waktu komputasi yang lama dapat pula berarti bahwa iterasi yang dilakukan sedang mencoba untuk mencari solusi berupa global optima. Sehingga dengan kata lain, dapat diasumsikan semakin lama waktu yang dibutuhkan maka semakin baik hasil clustering yang terjadi.
C3 H 0,4991 0,2214 0,8110 0,7279 0.3123 0,2319
Q 100 100 80 90 100 100
C4 H 0,8800 0,9311 0,7061 0,8208 0.4004 0,5058
Q 70 70 90 80 100 100
C5 H 0,1607 0,8015 0,7802 0,6073 0.3896 0,3671
Q 100 80 80 100 100 100
C6 H 0,6158 0,6039 0,4714 0,3801 0.7000 0,8934
Q 100 100 100 100 90 70
F. Rasio Kompresi Rasio kompresi yang dihasilkan oleh tiap-tiap citra uji ditunjukkan dalam TABEL 4. Dapat terlihat bahwa citra uji dengan format “.jpg” menghasilkan rasio kompresi hanya sedikit sekali, tidak sebesar pada citra uji dengan format “.png”. Hal tersebut dikarenakan sebelum digunakan sebagai citra uji dalam tugas akhir ini citra tersebut sudah dikompresi masing-masing dengan Algoritma JPEG dan Algoritma PNG, dimana JPEG bersifat lossy dan PNG bersifat lossless sehingga citra masukan dengan ekstensi “.jpg” sebelumnya sudah berukuran lebih kecil daripada citra masukan dengan ekstensi “.png”. TABEL 4 RASIO KOMPRESI YANG DIHASILKAN.
Nama Citra clownfish duck jet
Ekstens i File “.jpg” “.png” “.jpg” “.png” “.jpg” “.png”
Ukuran Sebelum Kompres i 23,1 KB 250 KB 63,8 KB 494 KB 22,3 KB 232 KB
Ukuran Setelah Kompres i 20,8 KB 20,7 KB 52,7 KB 49,3 KB 20,5 KB 21,4 KB
Rasio Kompres i 0.9004 0.0828 0.8260 0.0998 0.9193 0.0922
10 Volume 1 Nomor 1, April 2014 _______________________________________________________________________________
Jurnal Penelitian Teknik Elektro dan Teknologi Informasi _______________________________________________________________________________ G. Kualitas Kompresi Pengukuran kualitas kompresi secara kuantitatif akan dilakukan melalui 3 cara, yaitu. 1. Pengukuran error dan perubahan pixel dengan Mean Square Error (MSE) & Peak Signal-toNoise Ratio (PSNR) [7]. 2. Pengukuran kemiripan dengan Structural SIMilarity (SSIM) [8]. 3. Pengukuran korelasi dengan Pearson’s Coefficient Correlation (PCC) [9]. Hasil dari ketiga pengukuran tersebut ditunjukkan dalam TABEL 5. TABEL 5 PENGUKURAN MSE, PSNR, SSIM DAN PCC.
Nama Citra
Ektens i File
REFERENSI
PSNR*
SSIM*
PCC*
[1] R. Munir, Pengolahan Citra Digital dengan Pendekatan Algoritmik. Bandung: Informatika, 2004.
“.jpg” 17.7703 35.6338 “.png” 13.9473 36.6859 “.jpg” 143.2732 26.5692 duck “.png” 98.8718 28.1801 “.jpg” 63.0310 30.1353 jet “.png” 52.1633 30.9572 *berdasarkan channel warna hijau RGB
0.9323 0.9443 0.8857 0.9122 0.8651 0.8785
0.9959 0.9968 0.9704 0.9788 0.9894 0.9914
[2] J. W. O'Brien, "The JPEG Image Compression Algorithm," 2003.
clownfish
MSE*
informasi yang kurang penting dan di bagian ini akan dikompresi. Dari keseluruhan proses, waktu paling lama terjadi di bagian clustering dalam FCM karena adanya iterasi yang berulang-ulang agar konvergensi cluster tercapai. Berdasarkan semua pengujian yang telah dilakukan, citra dengan format “.png” memberikan keluaran yang lebih baik dibandingkan citra dengan format “.jpg”, baik di sisi ukuran, kualitas secara kualitatif (visual) maupun kualitas secara kuantitatif (perhitungan matematis). Rasio kompresi terkecil yang dapat dicapai pada penelitian ini adalah 0,0828.
Berdasarkan pengukuran MSE & PSNR, semakin besar nilai MSE maka semakin banyak perubahan nilai pixel yang terjadi antara citra masukan dan citra keluaran [7]. Sedangkan semakin besar nilai PSNR maka kualitas citra keluarannya semakin mendekati citra masukannya. Rentang nilai PSNR untuk citra dengan kualitas visual yang dianggap baik pada kompresi lossy sekitar 30-50dB [10]. Berdasarkan pengukuran SSIM, jika nilai SSIM yang dihasilkan mendekati nilai 1, maka citra keluaran tersebut semakin mirip dengan citra masukannya [11]. Berdasarkan pengukuran PCC, jika nilai PCC yang dihasilkan semakin besar maka tingkat korelasi antara citra masukan dan citra keluaran semakin besar [12]. Dari semua pengukuran dalam TABEL 5, ternyata semua pengukuran memberikan hasil yang sama, yaitu citra uji dengan format “.png” selalu menghasilkan citra keluaran dengan kualitas yang lebih baik dibandingkan dengan citra uji dengan format “.jpg”. IV. KESIMPULAN Metode clustering yang dimiliki FCM dapat digabungkan dengan metode kompresi JPEG untuk menghasilkan kompresi citra berbasis entropi. Kompresi citra berbasis entropi yang dirancang dapat mempertahankan kandungan informasi yang penting dalam sebuah citra dengan cara tidak melakukan kompresi pada cluster dengan entropi rendah. Entropi yang rendah dalam sebuah cluster menandakan penyebaran pixel yang dimiliki hampir tidak seragam dan jumlahnya sedikit, sehingga dapat dianggap sebagai informasi penting dan di bagian ini tidak akan dikompresi. Sedangkan entropi yang tinggi menandakan penyebaran pixel-nya seragam dan jumlahnya banyak, sehingga dapat dianggap sebagai
[3] M. R. Sabuncu, "Entropy-Based Image Registration," Nov. 2006. [4] C. T. Sun, J. S. R. Jang, and E. Mizutani, Neuro-Fuzzy and Soft Computing: A Computational Approach to Learning and Machine Intelligence. Englewood Cliffs: Prentice-Hall, 1996. [5] N. Wakhidah, "Clustering Menggunakan K-Means Algorithm". [6] Irwanto, Y. Purwananto, and R. Soelaiman, "Optimasi Kinerja Algoritma Klasterisasi K-Means," Jurnal Teknik ITS Vol. 1, No. 1, pp. A197-A202, 2012. [7] Z. Wang and A. C. Bovik, "Mean Squared Error: Love It or Leave It?," IEEE SIGNAL PROCESSING MAGAZINE, January 2009. [8] Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, "Image Quality Assessment: From Error Visibility to Structural Similarity," IEEE TRANSACTIONS ON IMAGE PROCESSING, vol. 13, No. 4, pp. 600-612, Apr. 2004. [9] A. A. Goshtasby, Image Registration: Principles, Tools and Methods (Advances in Computer Vision and Pattern Recognition). London: Springer, 2012. [10] S. Morelli, A. Giordiano, and D. Giasanti, "Routine Tests for Both Planning and Evaluating Image Quality in TeleEchocardiography," ANN IST SUPER SANITA, vol. 45, No. 4, pp. 378-391, 2009. [11] J. Østergaard, M. S. Derpich, and S. S. Channappayya, "The High-Resolution Rate-Distortion Function under the Structural Similarity Index," EURASIP Journal on Advances in Signal Processing, 2011. [12] N. Fenton and M. Neil, Risk Assessment and Decision Analysis with Bayesian Networks. CRC Press, 2012.
11 Volume 1 Nomor 1, April 2014 _______________________________________________________________________________