TUGAS AKHIR IMPLEMENTASI ALGORITMA METODE HUFFMAN PADA KOMPRESI CITRA
Disusun sebagai Salah Satu Syarat Menyelesaikan Program Studi Strata 1 Jurusan Elektro Fakultas Teknik Universitas Muhammadiyah Surakarta
Disusun oleh :
ARI WIDAGDO D400080008
JURUSAN ELEKTRO FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH SURAKARTA 2012
ABSTRAK Pertukaran informasi saat ini membutuhkan kecepatan dalam pengiriman informasi. Kecepatan pengiriman ini sangat bergantung kepada ukuran dari informasi tersebut. Salah satu solusi untuk masalah di atas adalah dengan melakukan pemampatan (kompresi). Proses kompresi citra (image compression) yang bertujuan menghasilkan ukuran data citra yang lebih kecil sebagai menjadi salah satu cara yang dapat dilakukan untuk pemecahan masalah. Pembuatan program kompresi ini menggunakan algoritma huffman. Metode Huffman merupakan salah satu teknik kompresi citra yang bersifat loseless. Metode ini menggunakan prinsip bahwa nilai derajat keabuan yang sering muncul di dalam citra akan dikodekan dengan jumlah bit yang lebih sedikit, sedangkan nilai keabuan yang munculnya sedikit (jarang) dikodekan dengan jumlah bit yang lebih panjang. Kompresi dilakuakn dengan cara membuat pohon biner dari nilai probabilitas data yang redundan. Penulis melakukan penelitian yang bertujuan membuat aplikasi kompresi citra dengan menggunakan algoritma huffman, serta untuk mengetahui performansi hasil proses kompresi dilakukan melalui perhitungan rasio kompresi, ukuran file hasil kompresi, kecepatan proses kompresi dan dekompresi.. Berdasarkan seluruh hasil penelitian, dapat disimpulkan bahwa sistem kompresi menggunakan algoritma Huffman dapat menghasilkan citra dengan memori yang lebih kecil. Citra yang telah di proses decoding pada algoritma ini dapat di kembalikan lagi dengan cara encoding. Dari pengujian yang dilakukuan algoritma ini dapat mengkompres gambar grayscale, true color, dan black white. Berdasarkan perhitungan, hasil kompresi citra Ums.jpg dengan ukuran asli 7,58 Kb memiliki nilai rasio kompresi sebesar 26,3%. Dengan waktu kompresi 28,6 detik dan waktu dekompresi 62,1 detik Kata Kunci : Kompresi citra, Algoritma Huffman, Lossles compression, Matlab
I PENDAHULUAN Dalam bidang teknologi informasi, komunikasi data sering dilakukan, komunikasi data ini berhubungan erat dengan pengiriman data menggunakan sistem transmisi elektronik dari satu terminal komputer ke terminal komputer yang lain. Besarnya ukuran data terkadang menjadi kendala dalam proses pengiriman. Data dengan ukuran besar akan memakan waktu transfer yang lebih lama dibandingkan dengan data yang memiliki ukuran lebih kecil, terkadang ada resiko tidak dapat tertampung pada media penyimpanan dan tidak tersampaikannya, sehingga akan memperkecil kapasitas kosong dalam memori media penyimpanan. Oleh karena itu, manusia selalu berusaha untuk menemukan suatu cara alterntif untuk menangani permasalahan tersebut, salah satunya dengan cara kompresi. Salah satu kegunaan kompresi adalah untuk memperkecil kapasitas ukuran data dalam memori media penyimpanan, agar tidak terlalu boros menggunakan media penyimpanan tersebut. Kompresi data berarti
suatu teknik untuk memampatkan data agar diperoleh data dengan ukuran yang lebih kecil daripada ukuran aslinya sehingga lebih efisien dalam menyimpannya serta mempersingkat waktu pertukaran data tersebut. Pertukaran data, pesan, dan informasi sangat sering dilakukan. Perpindahan itu dapat dilakukan melalui media penyimpanan (seperti floppy disk, hard disk, CD-ROM, flash disk) ataupun melalui media internet. Aplikasi pemampat data menggunakan cara pemampatan (kompresi) dan penirmampatan (dekompresi). Kompresi data atau pemampatan data adalah proses transformasi dari string ke string yang memiliki informasi sama namun memiliki panjang yang lebih sedikit (pendek). Salah satu cara kompresi data ini adalah dengan menggunakan salah satu aplikasi dari pohon biner (binary tree) yaitu kode Huffman. Citra Citra, menurut kamus Webster, adalah suatu representasi, kemiripan, atau imitasi dari suatu objek atau benda.
Sedangkan dari sudut pandang matematis, citra merupakan fungsi kontinu dari intensitas cahaya pada bidang dua dimensi. Citra sebagai keluaran dari suatu sistem perekaman data dapat bersifat: 1. Optik, berupa foto. 2. Analog, berupa sinyal video. 3. Digital, yang dapat langsung disimpan pada media penyimpanan magnetik. Citra juga dapat dikelompokkan menjadi : 1. Cita tampak : foto, gambar. 2. Citra tidak tampak : data gambar dalam file, citra yang direpresentasikan dalam fungsi matematis. III DASAR TEORI Kompresi Kompresi citra adalah aplikasi kompresi data yang dilakukan terhadap citra digital dengan tujuan untuk mengurangi redundansi dari data-data yang terdapat dalam citra sehingga dapat disimpan atau ditransmisikan secara efisien. Informasi yang dirasakan redundan dapat dikompresi untuk meminimalisasi redundansi tersebut. Hal ini dapat pula dilakukan pada citra dijital yang beragam tipenya, dengan menerapkan berbagai metode kompresi yang ada. Tujuan utama dari kompresi pada citra dijital adalah untuk mengurangi penggunaan memori, sehingga akan memudahkan penyimpanan, pengolahan serta pengiriman citra dijital tersebut. Dapat disimpulkan bahwa kompresi merupakan proses untuk menghilangkan berbagai kerumitan yang tidak penting (redundansi) dari suatu informasi, dengan memaksimalkan kesederhanaannya dan tetap menjaga kualitas penggambaran dari informasi. Penyimpanan data dilakukan untuk mencegah terjadinya kerusakan atau kehilangan data dan mempermudah membawa data-data tersebut ke manapun dan kapanpun dibutuhkan. Penyimpanan data pada komputer hanya dibatasi dengan kapasitas tertentu, sehingga dengan banyaknya data,memungkinkan tidak cukupnya perangkat keras penyimpan data untuk menyimpan semua data-data yang ada.
Berdasarkan output hasil kompresi, metode kompresi dapat dikelompokkan menjadi dua, yaitu : 1. Kompresi Loseless Hasil dekompresi dari data hasil kompresi akan tepat sama persis dengan data sebelum kompresi. Contoh aplikasi: ZIP, RAR, GZIP, 7-Zip . Teknik kompresi citra dimana tidak ada satu pun informasi citra yang dihilangkan. Biasa digunakan pada citra medis. Teknik ini digunakan jika dibutuhkan data dimana setelah dikompresi harus dapat didekompresi lagi dan menghasilkan data yang tepat sama dengan data asli. Contoh pada data teks, data program/biner, dan beberapa image random seperti GIF dan PNG. 2. Kompresi Lossy Teknik ini mengubah detail dan warna pada file citra menjadi lebih sederhana tanpa terlihat perbedaan yang mencolok dalam pandangan manusia, sehingga ukurannya menjadi lebih kecil. Kelebihan dari metode ini adalah ukuran file lebih kecil disbanding loseless namun masih tetap memenuhi syarat untuk digunakan. Biasanya teknik ini membuang bagian-bagian data yang sebenarnya tidak begitu berguna, tidak begitu dirasakan, tidak begitu dilihat sehingga manusia masih beranggapan bahwa data tersebut masih bisa digunakan walaupun sudah dikompresi. Huffman coding Pada tahun 1952 David Huffman memperkenalkan algoritma kompresi yang dinamakan Huffman coding. Metode ini memakai hampir semua karakteristik dari Shannon-Fano coding. Pada prinsipnya Huffman coding menggunakan pendekatan buttom-up dalam penyusunan binary tree. Algoritma Huffman, yang dibuat oleh seorang mahasiswa MIT bernama David Huffman, merupakan salah satu metode paling lama dan paling terkenal dalam kompresi teks. Berdasarkan pada landasan pikiran di atas serta hasil yang diperoleh
dari metode Huffman dimana teks hasil dekompresi yang diperoleh 100% sama dengan teks aslinya, maka akan diteliti sejauh mana metode Huffman dapat digunakan untuk kompresi data berupa citra. Secara fisik, sebuah citra merupakan representasi objek-objek, baik dalam keadaan diam atau bergerak, pada suatu support fisik seperti kertas, monitor, atau lainnya. Secara matematis, sebuah citra dinyatakan sebagai sebuah fungsi matematis dua dimensi 2Df(x,y) atau tiga dimensi 3Df(x,y,z). Dimana x dan y menyatakan posisi koordinat 2D (atau 3D), sedangkan f menyatakan nilai intensitas (kecerahan) atau menyatakan warna pada setiap posisi [x,y] (atau [x,y,z]). Sebuah citra digital dalam sebuah komputer dinyatakan dalam bentuk matriks 2D, dimana elemen matriks disebut piksel dan nilai dari setiap elemen matriksnya menyatakan intensitas atau warna. Bila matriks ini mewakili sebuah citra graylevel, maka nilai elemen matriks (piksel) menyatakan tingkat keabuan citra. Namun, bila matriks ini mewakili sebuah citra berwarna, maka nilai elemen matriks menyatakan warna. Setiap piksel dalam sebuah citra yang dikode dalam 8 bit, berarti citra tersebut memiliki 256 tingkat keabuan atau memiliki 256 warna. Contoh sebuah citra dapat dilihat pada gambar 2.1 di bawah ini. Misalkan citra tersebut dinyatakan dalam matriks berikut, dimana setiap elemen matriks (piksel) menyatakan warna 100 100 100 100 100 100 200 200 200 100 250 100 200 100 250 Metode Huffman termasuk metode lossless compression. Pengkodean citra berdasarkan pada derajat keabuan (gray level) atau tingkat warna dari piksel-piksel dalam keseluruhan citra. Dengan kata lain, metode Huffman termasuk dalam pendekatan statistikal (statistical compression) dalam kompresi citra. Warna atau derajat keabuan yang sering muncul di dalam citra akan dikodekan dengan jumlah
bit yang lebih sedikit sedangkan nilai yang frekuensi kemunculannya sedikit dikodekan dengan jumlah bit yang lebih panjang Algoritma metode Huffman untuk kompresi citra yaitu: 1. Buat data citra yang berupa matriks tersebut menjadi vektor. 2. Tentukan frekuensi kemunculan tiap warna atau derajat keabuan. 3. Urutkan secara menaik warna atau nilai keabuan berdasarkan frekuensi kemunculannya atau peluang kemunculan piksel dalam citra Setiap nilai dinyatakan sebagai pohon bersimpul tunggal dan setiap simpul di-assign dengan frekuensi kemunculan nilai tersebut. 4. Gabungkan 2 buah pohon yang mempunyai frekuensi kemunculan paling kecil pada sebuah akar. Akar mempunyai frekuensi yang merupakan jumlah dari frekuensi dua pohon penyusunnya. Frekuensi dengan nilai lebih kecil diletakkan di sisi kiri dan diberi bobot 0 sedangkan sisi kanan diberi bobot 1. 5. Ulangi langkah 4 sampai tersisa 1 pohon biner. 6. Telusuri pohon biner dari akar ke daun. Barisan bobot sisi dari akar ke daun menyatakan kode Huffman untuk derajat keabuan atau warna yang bersesuaian. 7. Mengganti data dengan kode Huffman yang bersesuaian. 8. Menyimpan data lebar citra, tinggi citra, kode bit untuk tiap nilai, data warna yang terdapat di dalam citra, dan data citra yang sudah dikodekan ke dalam file hasil kompresi. Untuk mengembalikan data citra terkompres menjadi data citra aslinya, diperlukan suatu algoritma dekompresi yang merupakan kebalikan dari algoritma kompresi. Berikut ini adalah langkahlangkah untuk mengembalikan data citra yang sudah dikodekan menjadi data citra semula : 1. Baca file hasil kompresi dan datadatanya dimasukkan ke variabel
yang sesuai yaitu variabel ukuran citra, variabel kode bit data, dan variabel warna 2. Baca data kode bit per bit dari kiri ke kanan dan dicocokkan dengan kode Huffman dari data warna yang didapat. Demikianseterusnya konversi dilakukan hingga data terakhir. 3. Rekonstruksi citra dengan menggunakan data ukuran citra, berarti data pixel berbentuk 1D dipenggal baris dan kolom sesuai ukuran citra. Sebagai contoh penerapan kompresi citra dengan metode Huffman, dapat dilihat pada dua contoh berikut : Terdapat citra dengan representasi matriks sebagai berikut. Tiap piksel dikodekan dengan 8-bit warna. 100 100 100 100 100 100 200 200 200 100 250 100 200 100 250 Akan dilakukan kompresi terhadap data citra tersebut. Langkah yang dilakukan adalah : 1) Bentuk vektor dari data citra yang berupa matriks [100 100 100 100 100 100 100 100 100 200 200 200 200 250 250] Jumlah piksel = 15 1) Peluang kemunculan warna pada citra : 100 = 9/15 200 = 4/15 250 = 2/15 2) Simpul pohon biner : 100 9/15
2004/15
50 : 2/15
3) Pembentukan pohon Biner Huffman 100-250-200 : 1 0
1 250-200 : 6/15
100 :9/15
250 : 2/15
200 : 4/15
Gambar 1 Pohon Biner huffman
Tabel 1. Tabel Kode Huffman untuk contoh Warna 100 200 250
Peluang kemunculan 9/15 4/15 2/15
Kode Huffman 0 11 10
4) Konversi data [100 100 100 100 100 100 100 100 100 200 200 200 200 250 250] menjadi : 000000000111111111010 5) Penyimpanan data pada citra - Ukuran : 5 x 3 - Kode Huffman - Data warna Rasio kompresi dihitung dengan persamaan (1) : - Ukuran citra sebelum kompresi 15 piksel x 8 bit = 120 bit - Ukuran citra setelah kompresi (9 x 1 bit) + (4 x 2 bit) + (2 x 2 bit) = 21 bit - Rasio Kompresi π
ππ ππ =
πΆππ‘ππ ππ ππ β π»ππ ππ πππππππ π Γ 100% πΆππ‘ππ ππ ππ
Rasio = 82.5 % Keterangan: Citra hasil: Ukuran sebelum dikompresi Hasil kompresi: Ukuran hasil kompresi Jika dilakukan dekompresi, citra yang diperoleh akan sama persis dengan ciitra awal (Lossless). III METODOLOGI PENELITIAN Urutan secara keseluruhan penelitian seperti terlihat pada gambar 6. Flowchart penelitian Proses yang dilakukan pada program kompresi citra ini terdapat dua proses, yaitu proses kompresi dan dekompresi. Proses kompresi merupakan proses dimana program kompresi citra melakukan proses encoding, sedangkan untuk proses dekompresi, pada GUI Matlab akan membaca data dari tabel hasil kompresi untuk kemudian disusun kembali sesuai dengan urutannya dan membentuk kembali citra yang sesuai dengan aslinya.
Mulai
Masukkan citra
Menentukan ukuran citra Menentukan Luas Citra (pixel)
Mengubah nilai unik menjadi baris
Gambar 3 Tampilan setelah memilih citra Menentukan nilai simbol citra
Menghitung nilai simbol
Apakahme Simbol input masih ada? tidak
ya
tidak
Merekontruksi citra Merubah citra ke RGB
Gambar 4 Tampilan hasil proses kompresi Menyimpan hasil
Selesai
Gambar 2 Flowchart program kompresi Huffman. Berikut merupakan screenshot pengujian program dengan Algoritma Huffman yang melalui 2 tahap yaitu kompresi dan dekompresi yang ditunjukkan gambar 3, 4 dan 5. Gambar 5 Tampilan proses dekompresi
Analisa hasil merupakan analisa dari perbandingan ukuran citra asli dengan ukuran citra hasil kompresi. Berikut beberapa tahap dalam menganalisa hasil. Data Uji Coba Tabel 2 Tabel spesifikasi citra asli sebagai citra masukan No.
Size File (bytes) 21,3 2
Resolusi
Format
1. 2.
Nama File Sails Scan
108Γ72 114Γ79
Png Png
3. 4. 5.
Tulips Zelda Valley
13,7 10 21,5
96Γ64 90Γ90 87Γ87
Png Png Png
6. 7. 8. 9.
Ums Babon Boy Animal
7,6 21,3 18,4 9
149Γ146 80Γ80 96Γ64 63Γ47
Jpg Png Bmp Bmp
10.
Image Cb Koala
10,14
207Γ192
Jpg
21,4
108Γ87
Jpg
11.
Tabel 3 Hasil Kompresi No.
Nama File
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
Sails Scan Tulips Zelda Valley Ums Babon Boy Animal Image Cb Koala
Size File (bytes) 15,8 1,6 12,3 8,3 14,9 5,6 12,4 18,4 9 7,75 9,8
Resolusi
Format
108Γ72 114Γ79 96Γ64 90Γ90 87Γ87 146Γ146 80Γ80 96Γ64 63Γ47 207Γ192 108Γ87
Png Jpg Png Png Png Jpg Png Bmp Bmp Jpg Jpg
Tabel 4 Hasil uji coba kompresi menggunakan metode huffman Citra masukan Sails Scan Tulips Zelda Valley Ums Babon Boy Animal Image Cb Koala
Ukuran (Kb) Citra asli 18,8 2 15,89 10,7 17,8 7,58 14,91 18,4 9 10,14
Citra Encoding 15,8 1,6 13,7 8,3 14,9 5,6 12,8 18,4 9 7,77
Citra Dekoding 18,8 2 15,89 10,7 17,8 7,58 14,91 18,4 9 10,14
3,5
2,7
3,5
Rasio Kompresi 15,9 20 13,7 22,4 16,2 26,3 14,1 0 0 23,5 22,8
Tabel 5 Waktu kompresi dan dekompresi No 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
Citra masukan Sails Scan Tulips Zelda Valley Ums Babon Boy Animal Image Cb Koala
Kompresi (detik) 6,9 8,1 6,5 6,2 9,2 28,6 6,3 3,6 3,3 45,6 9,7
Dekompresi (detik) 14,1 17,4 15,2 12,3 20,7 62,1 13,2 5,2 7,2 92,1 21,1
IV KESIMPULAN. 1. Dalam analisa hasil kompresi citra didapatkan bahwa setiap masing β masing citra memiliki perbedaan ukuran yang bervariasi. Berdasarkan perhitungan, hasil kompresi citra Ums.jpg dengan ukuran asli 7,58 Kb 2. memiliki nilai rasio kompresi sebesar 26,3%. Dengan waktu kompresi 28,6 detik dan waktu dekompresi 62,1 detik. 3. Hasil rata-rata kompresi gambar yang didapatkan dari masing-masing format gambar berbeda-beda hasilnya. Citra dengan format jpg bisa memiliki rasio kompresi paling tinggi, yaitu sebesar 26,3% diantara format-format citra yang di uji coba, pada citra png memiliki rasio paling tinggi sebesar 22,4%. 4. Kelebihan metode ini adalah bisa mengkompresi gambar grayscale, black and white dan true color. Jadi sangat aplikatif dengan bermacam β macam file citra
DAFTAR PUSTAKA βImage Compression Huffmanβ. http://www.mathworks.com. Diakses pada tanggal 13 Desember 2011. pukul 22.00 WIB Iqbal, Muhammad. Dasar Pengolahan Citra Menggunakan Matlab. www.creative instrument.com/dokumen/image.pd f, Diakses pada tanggal: 13 Desember 2011. pukul 23.00 WIB. Widiarsono, Teguh 2005, Tutorial Praktis Belajar Matlab.pdf, Jakarta Diakses pada tanggal: 23 Desember 2011, pukul 10:30 WIB R.
C.
GONZALEZ, βDigital Image Processingβ Second Edition, pp. 255 β 330, Addison Wesley Publishing Company, (1987)
Sulistyanto, Hernawan dan Nur Rohman, Ratnasari. 2007. Uji Implementasi Pemampat Data Tak β Hilang Dengan Metode RLE dan Static β Adaptive Huffman. Fakultas Teknik Universitas Muhammadiyah Surakarta. Munir, Rinaldi. (2006). Strategi Algoritmik. Departemen Teknik Informatika, Institut Teknologi Bandung. Nugroho, C, B. 2010. Proses Pemampatan Citra Dengan Standar Kompresi JPEG. Universitas Diponegoro. Sugiharto, Aris. 2006. Pemrograman GUI dengan Matlab. Semarang : Andi
