KOMPRESI CITRA BERWARNA MENGGUNAKAN METODE POHON BINER HUFFMAN Sarifuddin Madenda, Hayet L. dan I. Bayu*
ABSTRAK KOMPRESI CITRA BERWARNA MENGGUNAKAN METODE POHON BINER HUFFMAN. Makalah ini membahas tentang algoritma kompresi citra dengan menggunakan metode pohon biner Huffman. Metode ini biasanya digunakan untuk mengkompres file teks dikembangkan menjadi algoritma untuk mengkompres citra berwarna. Hasil yang diperoleh menunjukan bahwa algoritma ini memiliki nilai rasio kompresi di atas satu jika jumlah warna yang terdapat dalam citra tidak lebih dari 100 warna. Sedang kualitas citra hasil dekompresinya memiliki kualitas yang sama dengan citra aslinya.
ABSTRACT COLOR IMAGE COMPRESSION USING HUFFMAN'S BINARY TREE METHOD. This paper discusses the image compression algorithm using Huffman’s Method. Based on this method, we develop an algorithm to compress a color image. This algorithm has compression ratio value great than one if the number of color in an image is fewer than 100 colors. The quality of the decompression image is equal to the original image.
PENDAHULUAN Perkembangan teknologi informasi yang pesat telah memberi peran yang sangat penting untuk menjalin pertukaran informasi yang cepat. Kecepatan pengiriman informasi dalam bentuk perpaduan teks, suara dan gambar secara real-time akan menjadi bagian utama dalam pertukaran informasi masa mendatang. Hingga saat ini pengiriman informasi secara real-time masih mengalami kendala. Di antaranya adalah besarnya jumlah data yang harus dikirim melampaui kecepatan transmisi yang dimiliki oleh perangkat keras yang ada, sehingga masih terdapat delay time yang relatif besar. Salah satu solusi untuk mempersingkat waktu dan memperkecil biaya pengiriman dari masalah di atas adalah dengan melakukan pemampatan data teks, suara dan citra sebelum ditransmisikan dan kemudian penerima akan merekonstruksinya kembali menjadi data aslinya. Beberapa metode kompresi telah *
Lab. Pengolahan Citra dan Multimedia - Universitas Gunadarma
dikembangkan seperti : metode Huffman digunakan untuk mengkompres data teks, metode block coding, wavelet, encoding digunakan untuk kompresi signal suara atau citra. Yang menjadi permasalahan yang diteliti dan diuraikan dalam makalah ini adalah menentukan dan mengembangkan suatu metode yang dapat berfungsi baik untuk mengkompres teks, suara maupun citra. Makalah ini menguraikan aplikasi metode Huffman untuk kompresi data citra. Permasalahan utama yang akan dibahas dalam makalah ini adalah : - Apakah metode Huffman dapat diterapkan untuk mengkompres data citra ? - Seberapa besar rasio kompresi yang dapat dihasilkan ? - Apakah metode Huffman ini dapat merekonstruksi kembali data citra sesuai dengan data aslinya ? Untuk menjawab permasalahan di atas maka Penulis melakukan eksperimen, dengan membuat program kompresi citra menggunakan algoritma Huffman. Untuk menentukan rasio kompresi, dilakukan melalui perbandingan langsung antara besar data file citra asli dengan besar data file hasil kompresi. Sedang untuk mengukur kualitas citra hasil dekompresi atau rekonstruksi digunakan metode Root Mean Square Error dan Signal-to-Noise Ratio.
METODE KOMPRESI HUFFMAN Metode Huffman merupakan salah satu teknik kompresi dengan cara melakukan pengkodean dalam bentuk bit untuk mewakili data karakter. Cara kerja atau algoritma metode ini adalah sebagai berikut : a. Menghitung banyaknya jenis karakter dan jumlah dari masing-masing karakter yang terdapat dalam sebuah file. b. Menyusun setiap jenis karakter dengan urutan jenis karakter yang jumlahnya paling sedikit ke yang jumlahnya paling banyak. c. Membuat pohon biner berdasarkan urutan karakter dari yang jumlahnya terkecil ke yang terbesar, dan memberi kode untuk tiap karakter. d. Mengganti data yang ada dengan kode bit berdasarkan pohon biner. e. Menyimpan jumlah bit untuk kode bit yang terbesar, jenis karakter yang diurutkan dari frekuensi keluarnya terbesar ke terkecil beserta data yang sudah berubah menjadi kode bit sebagai data hasil kompresi. Contoh teknik kompresi dengan menggunakan metode Huffman pada file teks. Misalkan sebuah file teks yang isinya “AAAABBBCCCCCD”. File ini memiliki ukuran 13 byte atau satu karakter sama dengan 1 byte. Berdasarkan pada cara kerja di atas, dapat dilakukan kompresi sebagai berikut :
a. Mencatat karakter yang ada dan jumlah tiap karakter. A = 4, B = 3, C = 12, D=1 b. Mengurutkan karakter dari yang jumlahnya paling sedikit ke yang paling banyak yaitu : D, B, A, C c. Membuat pohon biner berdasarkan urutan karakter yang memiliki frekuensi terkecil hingga yang paling besar.
0
0
0 D
1
1
1 B
A
C
d. Mengganti data yang ada dengan kode bit berdasarkan pohon biner yang dibuat. Penggantian karakter menjadi kode biner, dilihat dari node yang paling atas atau disebut node akar : A = 01, B = 001, C = 1, D = 000. Selanjutnya berdasarkan pada kode biner masing-masing karakter ini, semua karakter dalam file dapat diganti menjadi : 01010101001001001111110001111111 Karena angka 0 dan angka 1 mewakili 1 bit, sehingga data bit di atas terdiri dari 32 bit atau 4 byte (1 byte = 8 bit) e. Menyimpan kode bit dari karakter yang frekuensinya terbesar, jenis karakter yang terdapat di dalam file dan data file teks yang sudah dikodekan. Cara menyimpan data jenis karakter adalah dengan mengurutkan data jenis karakter dari yang frekuensinya paling banyak sampai ke yang paling sedikit, menjadi : [C,A,B,D] File teks di atas, setelah mengalami kompresi, memiliki ukuran sebesar 1 + 4 + 4 = 9 byte. Jumlah ini terdiri dari 1 byte kode karakter yang memiliki frekuensi terendah, 4 jenis karakter = 4 byte dan 4 byte data kode semua karakter.
METODE DEKOMPRESI HUFFMAN Setiap data yang telah mengalami kompresi, tentu harus dapat merekonstruksi kembali data tersebut sesuai dengan aslinya. Merekonstruksi data lebih dikenal sebagai metode dekompresi data. Metode dekompresi Huffman dapat digunakan untuk mengembalikan data kode biner menjadi file teks. Metode atau algoritma untuk mengembalikan data hasil kompresi menjadi data semula adalah sebagai berikut : a. Membaca data pertama yang merupakan kode bit dari data karakter terakhir. Data pertama ini memiliki jumlah bit yang bervariasi (dalam contoh di atas data ini sama dengan 1 byte) dan digunakan sebagai pembanding untuk mengetahui apakah data karakter yang direkonstruksi merupakan data karakter terakhir atau bukan. Data ini selalu memiliki nilai sama dengan nol. b. Membaca data kode biner bit per bit hasil kompresi, bila nilai bit pertama sama dengan “0” maka dilanjutkan pada bit kedua. Bila bit kedua juga memilik nilai “0”, maka terus dilakukan pembacaan bit hingga ditemukan nilai bit sama dengan “1”. Setelah ditemukan nilai bit “1”, berarti semua bit yang terbaca adalah merupakan kode sebuah karakter. c. Mengubah kode biner menjadi sebuah karakter dengan cara menghitung banyaknya bit dalam kode tersebut. Misalkan banyaknya bit tersebut adalah n, maka kode biner di atas mewakili karakter pada urutan ke n dalam listing karakter. d. Ulangi langkah b dan c hingga kode bit biner terakhir. Untuk menentukan apakah kode biner yang sedang dibaca mewakili karakter yang paling akhir dalam listing karakter atau tidak adalah dengan cara membandingkan semua bit “0” yang terbaca dengan kode biner dari karakter yang terakhir.
KOMPRESI DAN DEKOMPRESI CITRA MENGGUNAKAN METODE HUFFMAN Beberapa metode kompresi citra telah dikembangkan seperti Block-coding, Encoding, CDT, Wavelet transform dan lainnya. Metode kompresi citra terus dikembangkan dengan tujuan untuk mengkompres hingga sekecil mungkin data citra, namun pada saat rekonstruksi diharapkan tidak satu pun data citra yang hilang. 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 penulis mencoba meneliti sejauh mana metode Huffman ini dapat digunakan untuk mengkompres data citra. Secara fisis, sebuah citra adalah merupakan representasi objek-objek baik dalam keadaan diam atau bergerak pada suatu suport fisik seperti kertas, monitor atau lainnya. Secara matematis, sebuah citra dinyatakan sebagai sebuah fungsi matematis
dua dimensi 2D f(x,y) atau tiga dimensi 3D f(x,y,z). Dimana x dan y menyatakan posisi koordinat 2D, sedang f menyatakan nilai intensitas (kecerahan) atau menyatakan warna pada setiap posis x,y. Sebuah citra digital dalam sebuah komputer dinyatakan dalam bentuk matrik 2D, dimana elemen matriks disebut pixel dan nilai dari setiap elemen matriksnya menyatakan intensitas atau warna (gambar 1).
x
y Gambar 1. Citra 2D Misalkan sebuah citra dinyatakan dalam bentuk matriks berikut : 100 100
100 100 100
100 200 200
200 100
250 100 200
100 250
Bila matriks ini mewakili sebuah citra gray-level berukuran 5x3 pixel, maka nilai elemen matriks (pixel) menyatakan tingkat keabuan citra. Tetapi bila matriks ini mewakili sebuah citra berwarna, maka nilai elemen matriks menyatakan warna. Setiap
pixel dalam sebuah citra yang dikode dalam 8 bit, berarti citra tersebut memiliki 256 tingkat keabuan atau memiliki 256 warna. Dengan mengambil contoh citra di atas dan dengan menggunakan metode Huffman, dikembangkan sebuah algoritma untuk mengkompres data citra sebagai berikut : a. Buat data citra yang berupa matriks tersebut menjadi vektor, sehingga didapat vektor [100,100,100,100,100,100,200,200,200,100,250,100,200,100,250] Besarnya data citra = 15 byte b. Baca vektor tersebut dan tentukan nilai warna yang ada serta frekuensi munculnya. Hasilnya adalah 100 = 9, 200 = 4, dan 250 = 2 c. Urutkan warna dari yang frekuensinya terkecil ke yang frekuensinya terbesar. 250,200,100 d. Membuat pohon biner berdasarkan urutan warna.
0
1
0
1
250
200
100
e. Mengganti data warna dengan kode bit berdasarkan pohon biner : 100 = “1” 200 = “01” 250 = 00 f. Mengganti data citra dengan kode bitnya, menjadi : 111111010101100101100. g. Menyimpan lebar citra, tinggi citra, kode bit untuk warna yang terbesar frekuensi munculnya (“00” untuk contoh di atas), 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 langkah-langkah untuk mengembalikan data citra yang sudah dikodekan menjadi data citra semula adalah sebagai berikut : a. Baca file hasil kompresi dan data-datanya dimasukkan ke variabel yang sesuai yaitu variabel ukuran citra, variabel kode bit data warna terakhir, variabel warna dan veriabel data kode.
b. Baca data kode bit per bit dari kiri ke kanan dan dicocokkan dengan data warna yang didapat. Bit hasil kompresi : 111111010101100101100 Bit pertama = “1”, karena nilainya “1” maka bit ini mewakili warna pertama dalam listing variabel warna yaitu warna 100. Kemudian bit berikutnya juga “1” berati mewakili warna 100, dan setrunya hingga bit ke 7 bernilai “0”. Karena bit ini bernilai “0” maka perlu dibandingkan dengan nilai kode biner data warna terakhir yaitu “00” dan karena “0” tidak sama dengan “00” maka dilakukan pembacaan berikutnya yaitu bit “1”. Karena bit berikutnya yang terbaca = “1” maka pembacaan kode selanjutnya dihentikan. Dengan demikian kode bit yang terbaca menjadi “01”, kode ini memiliki jumlah bit sebesar 2 bit dan dengan demikian kode ini mewakili warna pada urutan kedua dalam listing warna. Demikian seterusnya dilakukan konversi hingga data terakhir. Dari contoh di atas, hasil rekonstruksinya menjadi : [100 100 100 100 100 100 200 200 200 100 250 100 200 100 250] c. Rekonstruksi citra 2D dengan menggunakan data ukuran citra 5x3, berarti data pixel berbentuk 1D dipenggal menjadi 3 baris dan setiap barisnya berisi 5 pixel. Hasilnya menjadi :
100 100
100 100 100
100 200 200
200 100
250 100 200
100 250
HASIL Untuk mengetahui seberapa besar kemampuan metode Huffman dalam mengkompres data citra, penulis melakukan dua model uji coba. Pertama, menggunakan sejumlah citra dengan ukuran yang sama tetapi jumlah warna yang ada dalam citra berbeda satu sama lain. Kedua, menggunakan sejumlah citra dengan jumlah warna yang sama tetapi dengan ukuran yang berbeda. Uji coba dilakukan dengan bantuan citra sintetis yang dibuat dengan setiap warna memiliki jumlah pixel yang sama. Hal ini dilakukan karena distribusi jumlah pixel yang sama untuk setiap warna akan menghasilkan nilai rasio kompresi yang paling kecil. Dengan demikian hasil uji coba yang dilakukan adalah merupakan hasil yang minimal, atau dengan kata
lain nilai rasio kompresi dapat lebih besar dari hasil yang diuraikan dalam makalah ini. Tabel berikut ini memperlihatkan hasil kompresi menggunakan metode Huffman.
Tabel 1. Merupakan Tabel Hasil Kompresi pada Citra yang Memiliki Resolusi 128x128 dan Setiap Pixelnya Dikode dalam 8 Bit Warna. Jumlah warna 1 5 10 15 20 25 30 31 32 35
Citra Asli (byte) 16384 16384 16384 16384 16384 16384 16384 16384 16384 16384
Hasil Kompresi (byte) 1048 3120 5708 8316 10850 13429 16062 16549 17066 18618
Rasio kompresi 15,63 5,25 2,87 1,97 1,51 1,22 1,02 0,99 0,96 0,88
Tabel 2. Rasio Kompresi Citra 8 Warna dengan Resolusi yang Berbeda Resolusi citra 64 x 64 128 x 128 256 x 256 512 x 512 1024 x 1024
Ukuran citra asli (dlm. Byte) 4096 16386 65536 262144 1048576
Ukuran kompresi (dlm. Byte) 1226 4681 18460 71624 286496
Rasio kompresi
Penghitungan rasio kompresi dilakukan melalui persamaan : N.M.m Cr = L
3,34 3,50 3,55 3,66 3,66
Cr adalah compretion ratio, N.M adalah resolusi citra (N = Tinggi citra dan M = Lebar citra), m = jumlah bit yang digunakan untuk setiap pixel dan L = jumlah total bit hasil kompresi. Namun, untuk mudahnya, penulis menggunakan rumus rasio kompresi sebagai berikut : Ukuran file citra asli (dalam byte) Cr = Ukuran file citra hasil kompresi (dalam byte) Pada tabel 1 tampak bahwa semakin banyak jumlah warna yang terdapat dalam sebuah citra, maka rasio kompresi semakin mengecil. Hal ini sangat sesuai dengan bentuk pohon biner Huffman. Semakin banyak jumlah warna yang muncul dalam sebuah citra, maka pohon biner yang terbentuk memiliki cabang-cabang yang jauh masuk ke dalam. Hal ini dapat meyebabkan sejumlah pixel akan dikode dengan jumlah bit yang besar. Misalnya pada tabel 1, sebuah citra yang memiliki 31 macam warna di dalamnya, memiliki rasio kompresi 0,99. Ini berarti bahwa bukannya data citra terkompres tetapi justru memperbanyak jumlah data. Hal ini dapat terjadi karena pohon biner yang terbentuk memiliki 30 cabang dan dengan demikian pixel-pixel yang dikode akan memiliki jumlah bit yang bervariasi antara 1 sampai dengan 30 bit per pixelnya. Sementara pixel aslinya dikode dalam 8 bit. Pada tabel 2, dapat dilihat bahwa resolusi citra dengan warna yang sama tidak banyak mempengaruhi nilai rasio kompresi. Dengan demikian dapat dikatakan bahwa metode Huffman tidak dapat digunakan untuk mengkompres citra yang memiliki jumlah warna lebih besar dari pada 30 warna.
Tabel 3. Rasio Kompresi Citra pada Iterasi ke Dua Jumlah warna 32 35 50 100 150 159 160 170
Citra Asli (byte) 16384 16384 16384 16384 16384 16384 16384 16384
Hasil Kompresi (byte) 7154 7953 8904 12318 15753 16384 16549 17066
Rasio kompresi 2,29 2,06 1,84 1,33 1,04 1,00 0,99 0,96
Melihat hal ini, penulis mencoba mengkompres kembali kode bit data citra yang dihasilkan dengan metode Huffman. Algoritma yang digunakan sama dengan algoritma sebelumnya. Pengaruh dari pengkompresan kembali kode data dapat dilihat pada tabel 3 di atas. Melihat tabel di atas maka dapat katakan bahwa dengan mengkompres kembali kode data citra, nilai rasio kompresi meningkat. Namun algoritma yang dijalankan hingga iterasi ke dua ini hanya memberikan nila rasio kompresi di atas 1 untuk jumlah warna di bawah 100 warna. Kemungkinan kompresi dapat dilanjutka pada iterasi berikutnya, namun perlu diperhitungkan waktu kompresi dan dekompresi agar kedua operasi tersebut masih dalam hitungan waktu untuk real-time. Gambar berikut ini memperlihatkan hasil algoritma yang dikembangkan di atas untuk citra ril. Gambar(2) memperlihatkan gambar berwarna asli yang dikode dalam 8 bit, gambar(3) adalah hasil dekompresi untuk dua kali iterasi. Gambar hasil dekompresi, baik untuk satu kali maupun dua kali iterasi, menghasilkan kualitas citra yang sama dengan aslinya.
Gambar 2. Citra Asli
Gambar 3. Citra Dekompresi untuk Dua Kali Iterasi (Rasio kompresi = 2,104)
KESIMPULAN Dari hasil penelitian yang diperoleh dapat disimpukan bahwa metode pohon biner Huffman dapat diterapkan untuk mengkompres data citra, namun hanya untuk citra yang memiliki jumlah warna tertentu. Misalnya 30 warna untuk sekali iterasi dan 100 warna untuk dua kali iterasi, sesuai dengan algoritma yang dikembangkan dalam makalah ini. Kualitas citra hasil dekompresi baik untuk sekali iterasi maupun untuk dua kali iterasi sama dengan citra aslinya. Hal ini terjadi karena data warna (pixel citra) hanya dikodekan dalam bentuk kode pohon biner dan rekonstruksi datanya hanya tinggal mengkonversikan kode pohon biner menjadi data aslinya.
DAFTAR PUSTAKA 1. HARRY R LEWIS and LARRY DENEBERG, “Data Structure and Their Algorithms”, Harper Publisher, New York (1991) 2. R. C. GONZALEZ, “Digital Image Processing” Second Edition, pp. 255 – 330, Addison Wesley Publishing Company, (1987)
3. RUDY YUWONO, “Penerapan Teknik Companding File Teks Dengan Menggunakan Algoritma Huffman”, Proceeding Third Workshop on ECI, Hlm 8100, ITB, March 3-4, (1999) 4. SARIFUDDIN MADENDA, “Kompresi Citra Gray-Level Dengan Metode Block Coding”, Proceeding Workshop on ECI, Hlm 8-100, ITB, March 3-4, (1999) 5. TIMOTHY BELL, IAN H., JHON G CLEARLY and WITTEN, “Text Compression”, Englewood. Cliff NJ : Prentice Hall, (1990)
DISKUSI
SLAMET SANTOSA Bagaimana cara mempersiapkan data citra (scanning) yang akan dikompresi? Bagaimana cara mengkode warna ke angka-angka (terutama untuk warna-warna yang berdekatan) dan cara mengorganisasi data (struktur) angka-angka untuk rule pada pengkodean/pendekodean?
SARIFUDDIN MADENDA Akuisisi citra dengan scanning, pada prinsipnya scanning terdiri atas sensor cahaya yang akan mengubah pantulan intensitas cahaya ke dalam bentuk signal listrik analog. Selanjutnya dengan bantuan analog to digital converter (digitizer), signal analog ini diubah menjadi signal digital melalui proses sampling dan kuantisasi. Amplitudo signal menjadi nilai digital (integer) berupa warna atau gray level. Jumlah warna yang ada sangat tergantung terhadap jumlah bit (byte) yang dipakai untuk mengkode tersebut. Setiap nilai digital merupakan presentasi warna masing-masing.
UTAYA Bagaimana hasilnya, bila gambar yang Anda kompresi mempunyai jumlah detail yang sangat banyak dengan semua warna (256) muncul?
SARIFUDDIN MADENDA Bila citra yang akan kita kompresi memiliki jumlah warna yang sangat banyak misalnya 256 warna, maka akan terjadi dua kemungkinan; a. Bila distribusi frekuensi munculnya warna merata maka di atas 32 warna, metode ini sudah tidak mungkin lagi digunakan. b. Bila distribusinya tidak merata maka ada kemungkinan 150 warna akan efektif untuk dikompresi, efektif dalam arti ratio kompresi dapat data 2 kali lebih kecil.
Frekuensi
Warna ke 256 Tidak efektif Frekuensi
0
Warna ke 256 Efektif
AS NATIO LASMAN Tadi dikatakan bahwa dari data sebesar 16 byte dapat dikompres hingga menjadi 5 byte. Artinya terdapat efisiensi sebesar 31%. Apakah efisiensi ini hanya berlaku untuk kasus citra dengan 32 warna ataukah untuk citra di bawah 150 warna? Atau barangkali dapat dijelaskan perihal degradasi efisiensi sehubungan dengan kenaikan jumlah warna pada citra?
SARIFUDDIN MADENDA Saya jelaskan dengan distribusi warna: ratio kompresi 16 byte/5 byte = 3,2 kali. Semakin bertambah jumlah warna maka semakin banyak jumlah bit yang dipakai untuk mengkode sebuah warna: warna pertama 1 bit, warna kedua 2 bit, warna ke-100 = 100 bit dan seterusnya.
Frekuensi
1
256
Warna ke
Tidak efektif Frekuensi
Warna ke 1
16
256
Efektif
DAFTAR RIWAYAT HIDUP 1. Nama
: SARIFUDDIN MADENDA
2. Tempat/Tanggal Lahir
: Raha - 7 April 1963
3. Instansi
: Universitas Gunadarma
4. Pekerjaan / Jabatan
: Staf Pengajar dan Peneliti Universitas Gunadarma Pembantu Dekan I, Fak Teknologi Industri
5. Riwayat Pendidikan
: (setelah SMA sampai sekarang)
• FMIPA-UI, Jurusan Fisika Instrumentasi (1989)
(S1)
• Physics Semiconductor & Integrated Circuit, INSA-Lyon Prancis (1992)
(S2)
• Real Time Image Processing System, Univ.Bourgogne-Prancis (1995)
(S3)
6. Pengalaman Kerja
:
• 1987 – 1989 Dosen Universitas Gunadarma • 1995 - 1996 Pos Doctorat pada Universite de Bourgogne. • 1996 - sekarang Pembantu Dekan I Universitas Gunadarma 7. Professional
: • Anggota Ikatan Profesi Komputer Indonesia • Anggota IECI
HOME
KOMPUTASI DALAM SAINS DAN TEKNOLOGI NUKLIR X
