MENINGKATKAN RASIO KOMPRESI CITRA DIGITAL DENGAN HUFFMAN CODING PADA TRANFER DATA Sapta Aji Sri Margiutomo, Linda Suvi Rahmawati, Retno Sundari Program Studi Teknik Informatika STMIK PPKIA Pradnya Paramita Malang Email :
[email protected],
[email protected],
[email protected] ABSTRAK Komunikasi saat ini tidak lagi melihat jarak dan tempat hal ini merupakan dampak dari perkembangan tenologi digital yang berkembang sangat pesat, dimana kita dapat melihat atau berkumunikasi secara nyata melihat lawan bicara atau mengadakan telekonfren dalam rapat dengan berbagai tempat yang berbeda. Dalam komunikasi ini yang sangat berperan adalah kecepatan pengiriman data dan seberapa besar data tersebut di kirim dan di terima, semakin besar data tersenbut maka semakin lambat. Hal ini menarik untuk di lakukan penelitian bagaimana dapat memperkecil data dari suatu gambar tanpa mengurangi kulaitas atas gambar tersebut sehingga dapat mempercepat proses pengiriman data , algoritma huffman telah membuka bagaimana kompresi data atas gambar, algoritma ini mengurangi data yang berulang sehingga dapat memperkecil data dari suatu gambar/image. Penelitian ini mengitung perbandingan data sebelum dan sesudah kompresi. Kata kunci : Rasio Konprensi, Citra Digital, Huffman Coding, Transfer Data
1. Pendahuluan Perkembangan media penyimpanan berkapasitas besar mengakibatkan orang tidak lagi menemui masalah jika mempunyai file dengan ukuran besar. Terlebih jika file yang kita punya merupakan file image. Walaupun demikian, adakalanya ukuran file yang besar tersebut mengganggu jika kita harus mengatur media penyimpan untuk bermacam-macam data, misalnya : data yang berbentuk teks, multimedia, dan juga image. Apalagi jika file tersebut akan kita kirim secara elektronik, tentunya kapasitas file menjadi masalah tersendiri. File image tersebut perlu dilakukan kompresi citra. Kompresi citra (image compression) adalah proses untuk meminimalkan jumlah bit yang merepresentasikan suatu citra sehingga ukuran citra menjadi lebih kecil. Pada dasarnya teknik kompresi citra digunakan untuk proses transmisi data (data transmission) dan penyimpanan data (storage). Kompresi citra banyak diaplikasikan pada penyiaran televisi, penginderaan jarak jauh (remote sensing), komunikasi militer, radar dan lain-lain. Metode kompresi data yang ada pada saat ini banyak sekali. Sebagian besar metode tersebut bisa dikelompokkan ke dalam salah satu dari dua kelompok besar, Statistical Based dan Dictionary Based. Statistical Based adalah menggunakan peta kode yang selalu sama. Metode ini membutuhkan dua fase (two-pass) : fase pertama
14
untuk menghitung probabilitas kemunculan tiap simbol/karakter dan menentukan peta kodenya, dan fase kedua untuk mengubah pesan menjadi kumpulan kode yang akan ditransmisikan. Sedangkan Dictionary Based adalah menggantikan karakter/fragmen dalam file input dengan indeks lokasi dari karakter/fragmen tersebut dalam sebuah kamus (Dictionary). Contoh Dictionary Based Coding adalah Lempel Ziv Welch dan contoh Statistical Based Coding adalah Huffman Coding dan Arithmetic Coding yang merupakan algoritma terbaru. Salah satu cara mengatasi permasalahan untuk mengkompresi citra menggunakan Huffman-coding. Huffman-coding yang dikembangkan oleh D.A. Huffman mampu menekan jumlah redundancy yang terjadi pada sebuah pesan yang panjangnya tetap. Huffmancoding bukanlah teknik yang paling optimal untuk mengurangi redundancy tetapi Huffman-coding merupakan teknik terbaik untuk melakukan coding terhadap simbol pada pesan yang panjangnya tetap. Permasalahan utama dengan Huffmancoding adalah hanya bisa menggunakan bilangan bulat untuk jumlah bit dari setiap kode. Jika entropy dari karakter tersebut adalah 2,5 maka apabila melakukan pengkodean dengan Huffman-coding karakter tersebut harus terdiri dari 2 atau 3 bit.
Meningkatkan Rasio Kompresi Citra Digital Dengan Huffman Coding Pada Tranfer Data
2.
Pengertian Citra Digital Citra digital merupakan citra yang diperoleh sebagai hasil proses digitalisasi dari citra analog. Teknologi kamera foto dan video digital saat ini telah memungkinkan untuk mendapatkan citra atau video digital secara langsung. Citra adalah suatu representasi informasi visual pada suatu media antara lain lukisan, foto, film dan lain-lain. Informasi citra yang dapat ditangkap dan dianalisis oleh sistim visual mata manusia adalah berupa : - informasi dasar (warna, bentuk, dan texture) - informasi abstrak (senang, sedih, susah ) - informasi suasana (ulang tahun, pernikahan) Informasi ini direpresentasikan oleh nilai intensitas warna dari sekumpulan piksel yang membentuk setiap citra dan tersusun dalam bentuk larik dua dimensi. y
y
f(x1,y1)
1
x x Secara matematis, citra digital didefinisikan 1 sebagai fungsi dua dimensi (pada umumnya), f(x,y), dimana x dan y adalah koordinat spasial dan nilai f(x,y) menunjukkan nilai intensitas warna citra pada koordinat tersebut. Sebagai contoh pada gambar 2.1, pada gambar tersebut f(x1,y1) merupakan nilai warna piksel pada posisi x1 dan y1, dan nilai-nilai piksel dalam suatu citra umumnya dinyatakan dalam bentuk matriks, seperti terlihat pada persamaan 2.1 dibawah.
f (0,1) f (0,0) f (1,0) f (1,1) F f (i, j ) f (M 1,0) f (M 1,1)
f (0, N 1) f (1, N 1) f (M 1, N 1)
Gambar 1. Citra Digital
Di mana M dan N menyatakan jumlah baris dan kolom dari citra digital atau MxN merupakan dimensi citra. Setiap elemen f(i,j) dalam matriks F dinyatakan sebagai picture element (pel) atau lebih dikenal dengan piksel. Sebuah citra diubah ke bentuk digital agar dapat disimpan dalam memori komputer atau media lain. Proses mengubah citra ke bentuk digital bisa dilakukan dengan beberapa perangkat, misalnya : scanner, kamera digital, dan handycam. Perkembangan teknologi elektronika saat ini telah meningkatkan kecepatan sampling camera digital hingga mampu menghasilkan citra dengan resolusi tinggi dalam kisaran 16 Mpixel. Sensor pada setiap kamera digital atau alat digitizer lainnya menggunakan tiga warna dasar yaitu merah, hijau, dan biru (Red, Green, Blue - RGB). Ini berarti bahwa setiap pixel untuk citra berwarna membutuhkan 24 bit (8 bit per warna). Untuk citra gray-level (hitam putih) umumnya hanya dibutuhkan 8 bit per pixel. Sebagai contoh , misalkan sebuah foto berwarna berukuran 3 inci x 4 inci diubah ke bentuk digital dengan tingkat resolusi sebesar 500 dot per inch (dpi), maka diperlukan 3 x 4 x 500 x 500 = 3.000.000 dot ( pixel). Setiap pixel terdiri dari 3 byte dimana masing-masing byte merepresentasikan warna merah, hijau, dan biru. sehingga citra digital tersebut memerlukan volume penyimpanan sebesar : 3.000.000 x 3 byte +1080 = 9.001.080 byte setelah ditambahkan jumlah byte yang diperlukan untuk menyimpan format (header) citra. Citra tersebut tidak bisa disimpan ke dalam disket yang berukuran 1.4 MB. Selain it u, pengiriman citra berukuran 9 MB memerlukan waktu yang relatif lama (tergantung pada bandwidth media komunikasi yang dipakai). Untuk koneksi internet dial-up (56 kbps), pengiriman citra berukuran 9 MB memerlukan waktu 21 menit. Keterbatasan diatas disebabkan oleh beberapa hal diantaranya : pertama adalah bandwidth yang terbatas dan relatif mahal, kedua adalah kapasitas data multimedia yang mencapai puluhan ribu kali lipat dari kapasitas bandwidth jaringan komunikasi yang sering kita gunakan saat ini . Solusi yang dapat dilakukan untuk mempercepat waktu komunikasi tanpa memperbesar bandwidth dan sekaligus meminimalkan penggunaan memori adalah pengembangan algoritma dan metode yang mampu mengkompres data citra sekecil mungkin dan proses kompresinyapun cepat dengan tetap menjaga kualitas informasi. Citra yang belum dikompres disebut citra mentah (raw image). Sementara citra hasil kompresi disebut citra terkompresi (compressed image).
15
Meningkatkan Rasio Kompresi Citra Digital Dengan Huffman Coding Pada Tranfer Data
2.1. Kompresi Data Citra Citra merupakan salah satu informasi multimedia yang memiliki jumlah data yang cukup besar. Kualitas sebuah citra selalu dikaitkan dengan resolusi dan kedalaman/tingkat intensitas warna. Resolusi citra menyatakan ukuran panjang kali lebar dari sebuah citra yang dinyatakan dalam satuan piksel. Kedalaman intensitas warna menyatakan jumlah bit yang digunakan untuk pengkodean setiap warna atau dinyatakan dalam satuan bit/pixel. Semakin tinggi resolusi sebuah citra berarti semakin banyak jumlah piksel dan semakin tinggi kedalam intensitas berarti semakin banyak jumlah bit/pekselnya, hal ini mengakibatkan semakin baik kualitas citra tersebut. Namun, tingginya resolusi dan kedalaman intensitas menyebabkan semakin banyaknya jumlah bit yang diperlukan untuk menyimpan dan mentransmisikan data citra tersebut. Sebaliknya, kebanyakan aplikasi menginginkan representasi citra dengan kualitas citra yang baik dan penggunaan memori sekecil mungkin. Untuk meminimalkan jumlah data yag terkandung dalam citra, telah dikembangkan sejumlah algoritma kompresi citra. Salah satu metode kompresi adalah pengurangan kedalaman bit ini. Di mana prosesnya adalah dengan cara mengurangi jumlah bit yang digunakan untuk merepresentasikan suatu piksel. Misalnya dengan mengurangi kedalaman bit dari 24 bit/piksel menjadi 16 atau 8 bit/piksel. Namun metode ini dapat mengurangi kualitas visual warna citra dan sangaj jarang digunakan. Metode kompresi lain yang telah dikembangkan adalah pencodean sejumlah data rangkap (rendundant) dalam citra dengan menggunakanjumlah bit yang lebih kecil. Hal ini dapat dilakukan karena umumnya dalam sebuah citra terdapat redundansi data yang relatif tinggi. Redundansi merupakan suatu keadaan dimana sejumlah piksel memiliki nilai yang sama atau memiliki kesamaan secara visual. Keadaan ini memungkinkankan keseluruhan data yang sama dapat direpresentasikan secara lebih kompak. Metode ini sering digunakan untuk kompresi data spasial citra. Selain secara spasial, kompresi data citra dapat dilakukan dalam domain frequansi. Untuk hal ini dibutuhkan suatu proses transformasi (image transformation) dari domain spasial ke domain frekuensi. Umumnya, metode transformasi yang digunakan mampu memisahkan antara informasi global (ada pada frekuensi rendah atau lebih dikenal nilai rata-rata sejumlah piksel) dan informasi detail (ada pada frekuensi tinggi atau lebih dikenal nilai diferensil sejumlah piksel) dari setiap citra. Dengan demikian, cara ini akan lebih memudahkan untuk proses kompresi lebih lanjut. Transformasi yang populer digunakan antara lain Discrete Cosine
16
Transform (DCT) yang diadopsi dalam standar kompresi JPEG dan Discrete Wavelet Transform (DWT) yang digunakan dalam kompresi JPEG 2000 [WAT94] . Berdasarkan pada perkembangan teori, teknik kompresi citra dapat dibagi menjadi dua yaitu lossy dan lossless [G06] . Lossless compression (kompresi tanpa perubahan data) membuat kapasitas file sebuah gambar menjadi kecil dengan cara mengoptimalkan teknik pengkodean data redundan dari sebuah gambar yang asli. Metode ini cocok untuk kompresi citra dimana yang mengandung informasi penting dan tidak boleh rusak akibat kompresi tersebut, misalnya untuk citra medis. Teknik kompresi jenis ini adalah dengan mengaplikasikan langsung metode Huffman melalui pendekatan statistik di mana nilai warna atau keabuan yang sering muncul di dalam citra akan dikodekan dengan jumlah bit yang lebih sedikit, sedangkan nilai warna /keabuan yang frekuensi kemunculannya sedikit dikodekan dengan jumlah bit yang lebih panjang. Lossy compression (kompresi dengan adanya perubahan data) adalah teknik kompresi dengan meminimalkan jumlah bit (mereduksi nilai) pada informasi detail dari luminance dan chrominance (warna) citra. Hal ini dapat lebih memperkecil jumlah bit yang dibutuhkan untuk pengkodean citra. Lossy compression umumnya dilakukan dalam domain frekuensi seperti DCT dan DWT. Kualitas citra kompresi seperti ini sangat tergantung pada seberapa besar pengurangan nilai data/informasi detail. Semakin banyak nilai data detail yang hilang semakin rendah kualitas citra. 2.3.
Definisi Algoritma Menurut Yahya Kurniawan ( 2005:4) algoritma adalah urutan langkah-langkah logis penyeselaian masalah yang disusun secara sistematis dan logis. Kata logis (logika) merupakan kata kunci dalam algoritma. Langkah-langkah dalam algoritma harus dapat ditentukan bernilai benar atau salah. Selain itu algoritma merupakan metode yang tepat dan serangkaian langkah terstruktur dan dituliskan secara matematis yang akan dikerjakan untuk menyelesaikan suatu masalahdengan bantuan komputer. Berdasarkan Definisi di atas Algoritma adalah merupakan langkah untuk menyelesaikan suatu masalahyang menghasilkan solusi dalam bentuk program komputer. 2.4.. Definisi AlgoritmaKompresi Huffman Menurut Gagarin (2009:1) Algoritma kompresi Huffman dinamakan sesuai dengan nama penemunya yaitu David Huffman, seorang profesor di MIT (Massachusets Instuate of
Meningkatkan Rasio Kompresi Citra Digital Dengan Huffman Coding Pada Tranfer Data
Technology). Algoritma Huffman merupakan algoritma kompresi lossless, yaitu teknik kompresi yang tidak mengubah informasi data aslinya. Ini yang menyebabkan mengapa algoritma ini banyak dipakai dalam program kompresi. Pada sejarahnya, Huffman sudah tidak dapat membuktikan apapun tentang kode final, ia mendapatkan ide untuk menggunakan pohon binary untuk menyelesaikan masalahnya mencari kode yang efisien. Pada dasarnya, algoritma Huffman ini bekerja seperti mesin sandi morse, dia membentuk suatu kode dari suatu karakter. Sehingga karakter tersebut memiliki rangkaian bit yang lebih pendek dibandingkan sebelumnya. 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 :
Gambar 2. Pohon Biner 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. Merancang Desain Sistem Flowchart untuk membangun pohon Huffman dapat dibuat seperti di bawah 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.
17
Meningkatkan Rasio Kompresi Citra Digital Dengan Huffman Coding Pada Tranfer Data
Flowchart untuk melakukan pemampatan /kompres dan dekompresi citra
Gambar 5. Flowchart kompres dan dekompresi citra Gambar 3. Desain Sistem Flowchart pohon Huffman Flowcart berikut menyimpan data dari pohon binner dalam file :
3. Analisis Hasil Eksperimen Setelah tahap eksperimen selesai dilakukan dengan menggunakan program yang telah dibuat, selanjutnya adalah melakukan perbandingan hasil kompresi dari kedua program tersebut. Dalam melakukan eksperimen ini setiap citra dengan format jpg dimampatkan dengan menggunakan program yang telah peneliti buat dengan tujuan untuk menghitung rasio kompresi agar matriks kuantisasi yang akan digunakan dapat diketahui. Parameter yang akan dianalisis adalah Waktu Eksekusi, Rasio Kompresi, Kualitas citra hasil kompresi dan kompeksitas waktu algoritma.
Daftar Pustaka
Gambar 4. Desain Sistem Flowchart pohon Huffman
18
[1] Blelloch, G.E., 2001. Introduction to Data Compression. Carnegie Mellon University, Computer Science Department. [2] HM, Jogiyanto. 1999. Analisis Dan Desain Sistem Informasi. Yogyakarta : Andi Offiset. [3] Imadewira., 2009. Definisi dan Pengenalan Algoritma. (http://kuliah.imadewira.com/definisi-danpengenalan-algoritma/ tanggal 17 April 2011 jam 8:39). [4] Mengyi, Ida Pu., 2006. Fundamental Data Compression. London, Licensing Agency Ltd.
Meningkatkan Rasio Kompresi Citra Digital Dengan Huffman Coding Pada Tranfer Data
[5] Nelson, M., Gailly, J.L., 1996. The Data Compression Book, Second Edition. New York, M&T Books. [6] R.C Gonzales., 1987. “Digital Image Processing” Second Edition. Pp. 255-330, Addison Wesley Publishing Company. [7] Sarifuddin Madenda, 1994. “Kompresi Citra Gray-Level dengan Metode Block Coding”. Proceeding Workshop on ECI. HLM 8-100. ITB. March 3-4. [8] Salomon, David., 2004. Data Compression The Complete Reference Third Edition. California, Springer-Verlag. [9] Widhiarti, Putu. 2000. Pengantar Kompresi Data. (http://repository.upi.edu/operator/upload/s_ d545_060855_chapter2.pdf tanggal 31 maret 2011 jam 08:15) .
19
