PERBANDINGAN METODE HUFFMAN DAN FRAKTAL DALAM KOMPRESI CITRA Cici Kurniati Mahasiswa Program Studi Teknik Informatik, FT UMRAH Nerfita Nikentari, ST., M.Cs Dosen Program Studi Teknik Informatika, FT UMRAH Hendra Kurniawan, S.Kom., M.Sc. Eng Dosen Program Studi Teknik Informatika, FT UMRAH Abstrak Kompresi adalah teknik untuk mengurangi atau memperkecil ukuran data tanpa kehilangan informasi apapun. Dalam penelitian ini digunakan citra dijital berwarna. Secara teknis kompresi dibagi menjadi dua bagian, yaitu kompresi lossy dan kompresi lossless. Dimana kompresi lossy menghilangkan sebagian besar data yang ada pada gambar, salah satu contoh dari teknik ini adalah metode Fractal. Sedangkan kompresi lossless tidak menghilangkan data yang ada pada gambar salah satu contohnya adalah metode Huffman. Oleh karena itu dalam penelitian ini para peneliti membandingkan dua buah metode dari dua buah teknik yang ada yaitu metode Huffman dan metode Fractal pada citra dijital berwarna. Hasilnya berdasarkan rasio kompresi, metode Fractal memiliki rasio kompresi yang lebih tinggi daripada metode Huffman dengan rata-rata 24.380 pada format JPG dan 1.145 pada format BMP tapi waktu yang dibutuhkan untuk proses kompresi oleh metode Fractal lebih lama dibandingkan metode Huffman dengan rata-rata perbedaan waktu 195.724 detik pada format JPG dan 167.522 detik pada format BMP. Kata kunci : Lossy, Lossless, Fraktal, Huffman, Rasio Abstract Compression is a technique to reduce or minimize the data size without losing any information. In this study used a color digital image. Technically compression is divided into two parts, the lossy compression and lossless compression. Where lossy compression that removes most of the existing data in the image, one example of this technique is Fractal method. Whereas lossless compression does not eliminate the existing data in the image one example is Huffman method. Therefore, in this study the researchers compared two methods of two existing techniques that are Huffman methods and Fractal method on a colored digital image. The results are based on the compression ratio, the method Fractal has a compression ratio that is higher than the method of Huffman with an average of 24.380 in the JPG format and 1.145 in BMP format but the time required for the compression process by the method Fractal longer than the method of Huffman with an average difference of time 195 724 seconds in JPG format and 167 522 seconds in BMP format Key word : Lossy, Lossless, Fractal, Huffman, Ratio
I. PENDAHULUAN Kompresi merupakan suatu teknik untuk mengurangi atau memperkecil ukuran suatu data tanpa menghilangkan informasi yang ada. Dengan adanya teknik kompresi kapasitas penyimpanan menjadi lebih kecil dan waktu transmisi menjadi lebih singkat. Teknik kompresi ini dapat dilakukan terhadap citra.[2] Teknik kompresi terbagi menjadi dua tipe yaitu kompresi lossy dan kompresi lossless. Kompresi lossy merupakan kompresi yang menghilangkan data yang ada di dalam gambar tersebut sehingga hasilnya jauh lebih rendah dari pada kualitas yang asli, salah satu contohnya adalah metode Fraktal. Sedangkan kompresi lossless merupakan kompresi yang tidak menghilangkan data dari gambar tersebut sehingga hasilnya tidak menurun, salah satu contohnya metode Huffman.[3] Oleh karena itu penulis mencoba membandingkan dua teknik kompresi ini dengan menggunakan masingmasing metode yaitu metode Huffman dan metode Fraktal, dengan cara mengambil kelebihan dari masingmasing metode sehingga hasil yang diharapkan adalah berupa citra yang terkompresi dengan rasio yang tinggi serta kualitas yang baik. II. KAJIAN LITERATUR A. Kompresi Citra Kompresi ialah proses pengubahan sekumpulan citra menjadi suatu bentuk kode untuk menghemat kebutuhan tempat penyimpanan dan waktu untuk transmisi citra. Pengiriman data hasil kompresi dapat dilakukan jika pihak pengirim/ yang melakukan kompresi dan pihak penerima memiliki aturan yang sama dalam hal kompresi, pihak
pengirim harus menggunakan algoritma kompresi yang sudah baku dan pihak penerima juga menggunakan teknik dekompresi yang sama dengan pengirim sehingga data yang diterima dapat dibaca kembali dengan benar. Berdasarkan kandungan informasi pada citra hasil maka sifat kompresi dibagi menjadi dua, yakni : a. Kompresi Lossless Pada kompresi jenis ini citra hasil kompresi dapat dikembalikan secara sempurna menjadi citra asli, tidak terjadi kehilangan informasi. b. Kompresi Lossy Kompresi jenis ini mengizinkan terjadinya kehilangan sebagian data tertentu dari pesan tersebut. Apabila direkonstruksi kembali maka hasilnya tidak sama dengan citra aslinya, tetapi informasi yang terkandung tidak sampai berubah atau hilang. [7] B. Parameter Kompresi - Rasio Kompresi Rasio kompresi ialah nilai perbandingan antara citra asli dengan citra hasil kompresi. Untuk menentukan nilai rasio digunakan rumus sebagai berikut : Rasio kompresi = (
𝒖𝒌𝒖𝒓𝒂𝒏 𝒄𝒊𝒕𝒓𝒂 𝒂𝒔𝒍𝒊 𝒖𝒌𝒖𝒓𝒂𝒏 𝒉𝒂𝒔𝒊𝒍 𝒌𝒐𝒎𝒑𝒓𝒆𝒔𝒊
)
[6]
C. Citra Digital Citra digital ialah citra yang dihasilkan dari proses digitalisasi dari citra analog, citra yang diubah kebentuk digital agar mempermudah disimpan ke dalam memori komputer. Secara matematis citra digital didefinisikan sebagai fungsi dua dimensi f (x, y) dimana x dan y merupakan koordinat posisi dan nilai f (x, y) menunjukkan nilai intensitas
keabuan atau warna koordinat tersebut.[1]
citra
pada
D. Huffman Algoritma Huffman atau sering disebut dengan encoding Huffman merupakan salah satu metode pemampatan data yang menggunakan frekuensi atau probabilitas kemunculan suatu simbol atau karakter sebagai acuan pemempatan datanya. Pada tahun 1952 David Huffman menemukan algoritma Huffman. Berdasarkan tipe kode yang digunakan algoritma Huffman termasuk ke dalam metode statistik sedangkan berdasarkan teknik pengkodeannya menggunakan metode symbolwise. Metode Huffman memiliki 2 proses yaitu : - Huffman table, digunakan pada saat melakukan penyimpanan symbol dan probabilitas atau frekuensi kemunculannya. Sebelum data tersebut dikodekan sebaiknya harus mengetahui terlebih dahulu berapa banyak jumlah dari symbol yang sering muncul dengan cara memeriksa seluruh simbol data tersebut, dan akhirnya akan diperoleh nilai statistiknya. - Huffman tree, merupakan proses lanjutan dari Huffman table yang digunakan untuk menggambarkan jalur rangkaian pendek dari dari symbol yang sudah terkompresi.[8] E. Fraktal Fraktal adalah sebuah bentuk geometri yang merupakan gabungan dari beberapa bagian yang masingmasing merupakan salinan dari bentuk itu sendiri dalam ukuran lebih kecil dengan pola yang kompleks. Seperti sebuah mesin fotocopy dimana file yang di copy dikecilkan sehingga outputnya menjadi
setengahnya dan digandakan. Tetapi jika proses tersebut dibalik, hasil output dijadikan sebagai inputan maka hasilnya akan kembali seperti semula. Faktanya yang menentukan hasil output dari mesin fotocopy adalah posisi dan orientasi dari file tersebut yang menentukan hasil output file tersebut. [5] Meskipun Fraktal sangat kompleks tapi ada banyak teknik untuk menyelesaikannya, salah satunya ialah : - IFS (Iterated Function System) Membangun segitiga Sierpinski menggunakan IFS. Ambil sebuah segitiga dan hubungkan ke titik tengah dari tiga sisi ke segitiga di tengah. Kemudian hapus segitiga tersebut dan ulangi proses tersebut.
Gambar 1. Segitiga Sierpinski -
PIFS (Partitioned Iterated Function System) Pada sebuah citra sangat sulit untuk menemukan bagian citra yang mirip dengan keseluruhan citra, bahkan mungkin tidak ada. Akan tetapi pada sebagian besar citra terdapat kemiripan antara satu bagian citra dengan bagian citra yang lain, kemiripan ini disebut kemiripan lokal. Kemiripan lokal merupakan bentuk yang sama persis
ataupun sangat mirip dengan bagian dirinya sendiri, sebuah properti penting pada Fraktal. [4]
Gambar 2. Kemiripan Segitiga Sierpinski
relevan dimana akan dibahas oleh penulis, penulis juga mecari informasi dari internet B. Metode Pengembangan Sistem Metodologi pengembangan yang akan digunakan dalam hal ini ialah waterfall, waterfall di tahun 70-an sering disebut juga siklus klasik dan pada sekarang lebih dikenal dengan sekuensial linier. Waterfall dimulai dari analisis, desain, coding, testing, dan pemeliharaan. IV. PERANCANGAN IMPLEMENTASI A. Perancangan
DAN
Gambar 3. Kemiripan Lokal Pada Citra Pada gambar diatas kemiripan lokal terdapat pada daerah yang ditandai dengan kotak. Kotak yang lebih kecil mirip dengan kotak yang lebih besar, kotak-kotak ini disebut blok citra atau partisi citra. Kemiripan lokal antara satu blok dengan blok lainnya berarti bahwa kedua blok tersebut tidak tepat sama piksel per piksel, melainkan dimungkinkan terdapat kesalahan (error). Kemiripan-kemiripan lokal ini memungkinkan untuk mencari transformasi Affine wi yang memetakan suatu blok D ke blok R sehingga d (wi (D), R) cukup kecil. [4] III. METODE PENELITIAN A. Metode Pengumpulan Data - Kajian Pustaka Penulis mengambil data dari beberapa kajian-kajian terdahulu yang sebelumnya pernah dilakukan penelitian dengan tema yang
Gambar 4. Diagram Konteks (DFD Level 0)
Gambar 5. DFD Level 1 Huffman
Gambar 8. Halaman Huffman
Gambar 6. DFD Level 1 Fraktal B. Implementasi
Gambar 9. Halaman Fraktal
Gambar 7. Halaman Depan
Huffman JPG Fraktal JPG Huffman BMP Fraktal BMP
V. HASIL DAN PEMBAHASAN
Rasio Huffman & Fraktal
0
20
40
60
80
100
F. 64x64 BMP
F. 32x32 BMP
F. 16x16 BMP
F. 8x8 BMP
H. 64x64 BMP
H. 32x32 BMP
H. 16x16 BMP
H. 8x8 BMP
F. 64x64 JPG
F. 32x32 JPG
F. 16x16 JPG
F. 8x8 JPG
H. 64x64 JPG
H. 32x32 JPG
H. 16x16 JPG
H. 8x8 JPG
120
HUFFMAN JPG FRAKTAL JPG HUFFMAN BMP FRAKTAL BMP
Gambar 10. Rasio Kompresi
Waktu Huffman & Fraktal
0
1
2
3
4
5
F. 64x64 BMP
F. 32x32 BMP
F. 16x16 BMP
F. 8x8 BMP
H. 64x64 BMP
H. 32x32 BMP
H. 16x16 BMP
H. 8x8 BMP
F. 64x64 JPG
F. 32x32 JPG
F. 16x16 JPG
F. 8x8 JPG
H. 64x64 JPG
H. 32x32 JPG
H. 16x16 JPG
H. 8x8 JPG
Gambar 11. Waktu Kompresi
6
Tabel 1. Hasil Pengujian
Lena 8.jpg Lena 16.jpg Lena 32.jpg Lena 64.jpg
Ukuran Awal (byte) Huffman Fraktal 18301 18301 18544 18544 19503 19503 22612 22612
Ukuran Kompresi (byte) Huffman Fraktal 192 170 1024 651 5107 2760 24213 11880
Ukuran Dekompresi Huffman Fraktal 18301 1000 18544 1000 19503 4000 22612 13000
Huffman 95.318 18.109 3.819 0.934
Fraktal 107.653 28.485 7.066 1.903
Huffman 0.052 0.043 0.206 0.849
Fraktal 0.061 0.196 0.483 4.855
Lena 8.bmp Lena 16.bmp Lena 32.bmp Lena 64.bmp
246 822 3126 12342
192 1024 5111 24413
246 822 3126 12342
1.281 0.803 0.612 0.506
1.456 1.261 1.124 1.036
0.009 0.034 0.234 0.93
0.044 0.18 0.578 4.773
No
Citra Uji
1 2 3 4 5 6 7 8
246 822 3126 12342
169 652 2780 11909
1000 1000 4000 13000
Rasio
Time (sec)
Peningkatan ukuran file hasil kompresi pada kedua metode terjadi karena cara kerja dari masing-masing algoritma. Berikut penjelasannya :
1. Hasil kompresi pada kedua metode adalah berupa file bukan berupa citra. Pada metode Huffman file hasil kompresi berisi pohon Huffman yang merupakan bentuk lain dari citra asli. Sedangkan pada metode fraktal file hasil kompresi berupa lokasi koordinat blok citra, nilai pergeseran antar blok citra dan transformasi yang digunakan. 2. Citra yang digunakan adalah citra berwarna dengan tiga komponen susunan warna yaknik R, G dan B. Dalam sebuah citra digital yang tersusun atas piksel-piksel setiap pikselya mengandung 3 komponen warna tersebut, sehingga jika citra yang digunakan semakin besar maka komponen warna yang ada pada citra tersebut juga semakin banyak. 3. Pada metode Huffman setiap komponen warna R G dan B akan akan di urutkan berdasarkan warnanya. Karena didalam sebuah citra berwarna, warna yang dihasilkan merupakan kombinasi dari tiga warna tersebut maka otomatis akan terdapat banyak komponen warna R G ataupun B.Misalkan untuk warna R saja, pada sebuah citra warna R terdapat banyak sekali, setiap kemunculan warna R tersebut akan disusun dan diurutkan, begitu juga untuk warna G dan B. Sehingga akan berdampak pada semakin panjang pohon Huffman yang dihasilkan. Hal ini akan berbeda jika citra yang digunakan adalah citra hitam putih ataupun citra grayscale, pohon Huffman yang
dihasilkan tidak akan terlalu panjang karena komponen warna yang terkandung pada citra hitam putih atau grayscale tidak sebanyak pada citra RGB. 4. Pada metode fraktal bekerja dengan membandingkan dua buah blok citra, perbandingan dilakukan untuk setiap piksel pada masing-masing blok. Sehingga jika citra yang digunakan semakin besar maka piksel yang harus dibandingkan juga semakin banyak. Selain itu dikarenakan file hasil kompresi menyimpan lokasi blok citra, besar pergeseran antar blok dan transformasi yang digunakan, sehingga pada citra RGB dengan ukuran yang semakin besar otomatis membuat lokasi yang disimpan semakin banyak, karena besar pergeseran antar blok dihitung per pikselnya hal ini juga membuat nilai yang disimpan juga semakin banyak begitu juga dengan transformasi affine yang digunakan. Dengan semakin banyaknya piksel yang harus dibandingkan otomatis membuat waktu komputasi juga semakin lama. 5. Sedangkan perbedaan hasil kompresi antara JPG dan BMP yang berbeda dikarenakan JPG merupakan format standar fotografi yang sudah terkompresi sehingga file dengan format tersebut ukurannya kecil jika dibandingkan dengan format BMP. Format BMP merupakan visualisasi yang hampir sama dengan objek aslinya, dari segi warna dan intensitas sehingga pikselnya lebih rapat. Hal ini yang menyebabkan ukuran file hasil kompresi pada format BMP lebih besar dari format JPG.
Sedangkan hasil dari dekompresi pada metode fraktal mengalami penurunan ukuran file jika dibandingkan dengan ukuran citra asli, meskipun secara ukuran piksel citra hasil dekompresi tetap sama dengan citra asli serta terjadi perubahan warna terhadap citra hasil dekompresi. Berikut penjelasannya : 1. Hal ini dikarenakan konsep dan cara kerja dari metode Fraktal berdasarkan teori yang dikemukakan oleh Fisher (1992) yakni seperti mesin fotocopy dimana hanya nilai-nilai yang penting saja yang diambil dan intensitas warna citra asli dikurangi sehingga apapun gambar awal yang digunakan akan selalu menghasilkan gambar yang dari segi bentuk sama seperti gambar asli. Selain itu menurut Strand (2011) dan Putra (2010) konsep dari kompresi lossy dimana citra hasil dekompresi tidak sama seperti citra asli hanya menyerupai citra asli saja dan tidak bisa dikembalikan utuh seperti citra asli, ada beberapa informasi yang hilang namun informasi yang dibutuhkan tetap ada. Sehingga secara ukuran matriks piksel citra hasil dekompresi tetap sama dengan ukuran piksel citra asli. VI. PENUTUP A. Kesimpulan Berdasarkan hasil analisa dan pembahasan pada bab v maka dapat disimpulkan beberapa hal, yaitu pada ukuran citra yang berbeda dan format citra yang berbeda maka: 1. Untuk kedua metode Huffman maupun Fraktal semakin banyak komposisi warna yang terdapat pada sebuah citra akan membuat ukuran file hasil kompresi menjadi lebih besar.
Hasil yang didapatkan baik rasio, ukuran hasil kompresi maupun ukuran hasil dekompresi dipengaruhi cara kerja dari masing-masing algoritma. 3. Metode Fraktal memiliki rasio kompresi lebih tinggi dari pada metode Huffman dengan ratarata 24.380 pada format JPG dan 1.145 pada format BMP 4. Metode Fraktal membutuhkan waktu lama dalam proses kompresi dibandingkan dengan metode Huffman dengan rata-rata perbedaan waktu 195.724 detik pada format JPG dan 167.522 detik pada format BMP 2.
B. Saran 1. Untuk penelitian selanjutnya, dapat dikembangkan metode dengan cara menggabungkan dua metode Huffman dan Fraktal, karena masing-masing metode memiliki kelebihan dan kekurangan dimana kelebihan pada metode Huffman waktu proses kompresinya lebih cepat sedangkan kekurangannya nilai rasio lebih kecil. Kelebihan pada metode Fraktal nilai rasio lebih tinggi dan kekurangannya membutuhkan waktu yang lama. Maka penggabungan dua metode ini saling melengkapi, dimana metode Huffman digunakan untuk waktu kompresi dan metode Fraktal digunakan untuk mendapatkan nilai rasio kompresi yang lebih tinggi.
2. Untuk hasil yang optimal dapat digunakan citra biner atau grayscale sebagai media agar didapatkan hasil kompresi dan waktu yang lebih baik, karena pada citra tersebut tidak terdapat banyak warna. VII. DAFTAR PUSTAKA [1] Alfatwa, D.F., 2009, Watermarking Pada Citra Digital Menggunakan Discrete Wavelete Transform, Jurnal Teknik Informatika, Institut Teknologi Bandung, Bandung, Indonesia. [2] Ardhytia, S.N., Hiryanto, L., 2010, Algoritma Kompresi Fraktal Sequential Dan Paralel Untuk Kompresi Citra, Jurnal Fakulas Teknologi Informasi, Universitas Tarumanagara, 108-117. [3] Faradisa, I.S., Budiono, B.F., 2011, Implementasi Metode Huffman Sebagai Teknik Komprsi Citra, Jurnal Elektro ELTEK, 2(2), 176182. [4 Fazry, L., 2008, Algoritma Genetika Pada Kompresi Citra Digital, Skripsi, Universitas Indonesia, Depok. [5] Fisher, Y., 1992, Fractal Image Compression, Journal of University of California. San Diego, 1-21. [6] Madenda, S., L, Hayet., Bayu, I., 2014, Kompresi Citra Berwarna Menggunakan Metode Pohon Biner Huffman. [7] Putra, D., 2010., Pengolahan Citra., Yogyakarta, Andi, 272-273. [8] Septianto, T.Y., Djuriatno, W., Muttaqin, A., 2011, Pemampatan Tata Dokumen Berbahasa Indonesia dengan Metode Huffman Menggunakan Panjang Simbol Bervariasi, Jurnal Teknik Elektrok, Universitas Brawijaya Malang.
