IMPLEMENTASI DAN ANALISIS KINERJA ALGORITMA ARIHTMETIC CODING DAN SHANNON-FANO PADA KOMPRESI CITRA BMP Syahfitri Kartika Lidya1) Mohammad Andri Budiman2) Romi Fadillah Rahmat3) Jurusan Teknologi Informasi Universitas Sumatera Utara Medan1,2,3) JL. Dr.Mansyur No 9 Padang Bulan Medan 20155 Indonesia Email:
[email protected]) |
[email protected]) |
[email protected])
Abstrak Pada pengiriman informasi dalam bentuk citra masih mengalami kendala, diantaranya adalah karena besarnya ukuran citra sehingga solusi untuk masalah tersebut adalah dengan melakukan kompresi. Pada tulisan ini akan mengimplementasi dan membandingkan kinerja algoritma Arithmetic Coding dan Shannon-Fano melalui perhitungan rasio kompresi, ukuran file hasil kompresi, kecepatan proses kompresi dan dekompresi. Berdasarkan seluruh hasil pengujian, bahwa algoritma Arithmetic Coding menghasilkan rata-rata rasio kompresi 62,88 % dan rasio kompresi Shannon-Fano 61,73 %, kemudian Arithmetic Coding rata-rata kecepatan dalam kompresi citra yaitu 0,072449 detik dan Shannon-Fano 0,077838 detik. Kemudian algoritma Shannon-Fano memiliki rata-rata kecepatan untuk dekompresi yaitu 0,028946 detik dan algoritma Arithmetic Coding 0,034169 detik. Citra hasil dekompresi pada algoritma Arithmetic Coding dan Shannon-Fano sesuai dengan citra asli. Dapat diambil kesimpulan dari hasil pengujian bahwa algoritma Arithmetic Coding lebih efisien dalam mengkompresi citra *.bmp dibandingkan algoritma Shannon-Fano, walaupun dalam hal dekompresi Shannon-Fano sedikit lebih cepat dibandingkan Arithmetic Coding. Kata kunci : kompresi citra, Arithmetic Coding, Shannon-Fano
1. Pendahuluan Kompresi adalah proses pengubahan sekumpulan data menjadi suatu bentuk kode atau simbol untuk menghemat tempat penyimpanan dan waktu. Algoritma kompresi yang diharapkan dari kompresi citra adalah proses kompresi dan dekompresinya cepat, meminimalkan pemakaian memory, kualitas citra yang baik dan proses transfer yang mudah. Teknik untuk mengkompresi citra ada dua macam, yaitu Lossless dan Lossy. Teknik lossless adalah suatu teknik kompresi data tanpa menghilangkan satupun informasi saat sebelum dikompresi. Kompresi citra pada teknik lossless, yaitu Run Length Encoding, Huffman Encoding, Shannon-Fano, Arithmetic Coding, Entropy Coding (Lempel/Ziv). Berbeda dengan teknik lossless,
teknik lossy adalah data hasil kompresi menghilangkan beberapa informasi sehingga tidak seperti data aslinya. Algoritma untuk kompresi citra pada teknik lossy, yaitu Transform Coding, Vector Quantisation, Fractal Coding, JPEG, GIF, PNG, Discrete Cosine Transform, Discrete Wavelet Transfrom. [1] Format BMP, disebut dengan bitmap atau format DIB (Device Independent Bitmap) adalah sebuah format citra yang digunakan untuk menyimpan citra bitmap digital terutama pada sistem operasi Microsoft Windows atau OS/2. Pada citra berformat *.bmp (bitmap) yang tidak terkompresi, piksel citra disimpan dengan kedalaman warna 1, 4, 8, 16 atau 24 bit per piksel. [2] Pada umumnya citra bitmap teridir dari 4 blok data yaitu: BMP header, Bit Information (DIB header), Color Pallete, dan Bitmap Data. BMP header berisi informasi umum dari citra bitmap. Blok ini berada pada bagian awal file citra dan digunakan untuk mengidentifikasi citra. Beberapa aplikasi pengolah citra akan membaca blok ini untuk memastikan bahwa citra tersebut berformat bitmap dan tidak dalam kondisi rusak. Bit information berisi informasi detail dari citra bitmap, yang akan digunakan untuk menampilkan citra pada layar. Color pallete berisi informasi warna yang digunakan untuk indeks warna bitmap, dan bitmap data berisi data citra yang sebenarnya, piksel per piksel.[3]
2. Definisi Citra BMP Format BMP, disebut dengan bitmap atau format DIB (Device Independent Bitmap) adalah sebuah format citra yang digunakan untuk menyimpan citra bitmap digital terutama pada sistem operasi Microsoft Windows atau OS/2. Pada citra berformat *.bmp (bitmap) yang tidak terkompresi, piksel citra disimpan dengan kedalaman warna 1, 4, 8, 16 atau 24 bit per piksel. [2]
3. Analisis Kinerja Algoritma Arithmetic Coding Prinsip Arithmetic Coding diperkenalkan pertama kali oleh Peter Elias sekitar tahun 1960-an. Algoritma ini melakukan proses pengkodean dengan menggantikan setiap simbol masukan dengan suatu codeword [1]. Arithmetic Coding memiliki kelebihan terutama ketika memproses kumpulan abjad yang relatif sedikit.
Awalnya Arithmetic Coding diperkenalkan oleh Shannon, Fano dan Elias. Tujuannya memberikan ide alternatif yang pada saat itu setiap proses pengkodean dilakukan dengan menggantikan setiap simbol masukan digantikan dengan sebuah angka single floating point. Sehingga semakin panjang dan kompleks pesan yang dikodekan maka semakin banyak bit yang diperlukan untuk keperluan tersebut. Sejak tahun 1960-an hingga sekarang. [5] Berikut ini algoritma encoding dan decoding pada Arithmetic Coding. Akan digunakan dua variabel low dan high untuk mendefinisikan interval (low, high). [1]
Langkah –langkah algoritma ini untuk melakukan proses dekompresi pada citra bmp dapat digambarkan dengan flowchart, sebagai berikut : Mulai
Ambil Encoded Symbol (ES)
Cari range simbol yang melingkupi ES
Cetak simbol
CR = high_range – low_range
ES = ES – low_range
ES = ES / CR
Tidak
Simbol habis Ya Selesai
Langkah –langkah algoritma ini untuk melakukan proses kompresi pada citra bmp dapat digambarkan dengan flowchart, sebagai berikut :
Gambar 2. Flowchart Proses Dekompresi Algoritma Arithmetic Coding
4. Analisis Kinerja Algoritma ShannonFano
Mulai
Buka file citra
Baca header file
Low = 0.0 High = 1.0
Simbol input masih ada
Selesai Tidak
Ya Ambil simbol input
CR = high - low
High = low + CR * high_range (simbol)
Low = low + CR * low_range (simbol)
Cetak low
Gambar 1. Flowchart Proses Kompresi Algoritma Arithmetic Coding
Algoritma Shannon-Fano merupakan algoritma pertama yang diperkenalkan untuk kompresi sinyal digital pada bukunya yang berjudul “A Mathematical Theory of Communication”. Algoritma ini dikembangkan secara mandiri oleh Claude Shannon dan Robert Fano dalam dua publikasi terpisah pada tahun yang sama yaitu pada tahun 1949. Algoritma ShannonFano adalah salah satu banyak yang dikembangkan oleh Claude Shannon dianggap sebagai “Father of Information Theory” yaitu membuat kemajuan dalam kaitannya dengan transfer data dan komunikasi pada umumnya. Pada tahun 1976 Robert Fano menerima Claude Shannon Award untuk karyanya dalam Information Theory.[4] Langkah-langkah kompresi menggunakan algoritma Shannon-Fano. 1. Buatlah daftar peluang atau frekuensi kehadiran setiap simbol dari data yang akan dikodekan. 2. Urutkanlah daftar tersebut menurut frekuensi kehadiran simbol secara menurun (dari simbol yang frekuensi kemunculan paling banyak sampai simbol dengan frekuensi kemunculan paling sedikit). 3. Bagilah daftar tersebut menjadi dua bagian dengan pembagian didasari pada jumlah total frekuensi
4.
5.
suatu bagian (disebut bagian atas) sedekat mungkin dengan jumlah total frekuensi dengan bagian yang lain (disebut bagian bawah). Daftar bagian atas dinyatakan dengan digit 0 dan bagian bawah dinyatakan dengan digit 1. Hal tersebut berarti kode untuk simbol-simbol pada bagian atas akan dimulai dengan 0 dan kode untuk simbol-simbol pada bagian bawah akan dimulai dengan 1. Lakukanlah proses secara rekursif langkah 3 dan 4 pada bagian atas dan bawah. Bagilah menjadi kelompok-kelompok dan tambahkan bit-bit pada kode sampai setiap simbol mempunyai kode yang bersesuaian pada pohon tersebut.
Langkah - langkah dekompresi menggunakan algoritma Shannon-Fano. 1. Baca bit pertama dari serangkaian kode yang dihasilkan 2. Jika bit tersebut ada dalam SF Code, maka bit tersebut diterjemahkan menjadi simbol yang sesuai dengan bit tersebut. 3. Jika bit tersebut tidak ada dalam SF Code, gabungkan bit tersebut dengan bit selanjutya dalam rangkaian kode, cocokkan dengan tabel hasil pengkodean. 4. Lakukan langkah 3 sampai ada rangkaian bit yang cocok dengan SF Code, terjemahkan rangkaian bit tersebut menjadi simbol yang sesuai. 5. Baca bit selanjutnya dan ulangi langkah 2, 3, dan 4 sampai rangkaian kode habis. Langkah –langkah algoritma ini untuk melakukan proses kompresi pada citra bmp dapat digambarkan dengan flowchart, sebagai berikut : Mulai Buka file citra Baca header file
Hitung frekuensi kemunculan simbol pada tiap piksel citra, urutkan secara menurun
Bagilah daftar menjadi dua bagian dengan frekuensi sama / hampir sama yang disebut bagian atas dan bagian bawah
Daftar bagian atas dinyatakan dengan digit 0 dan bagian bawah dinyatakan digit 1
Ya Simbol input masih ada Tidak Kode Shannon-Fano (Output file)
Selesai
Gambar 3. Flowchart Proses Kompresi Algoritma Shannon-Fano
Langkah –langkah algoritma ini untuk melakukan proses dekompresi pada citra bmp dapat digambarkan dengan flowchart, sebagai berikut :
Gambar 4. Flowchart Proses Dekompresi Algoritma Shannon-Fano
5. Hasil dan Perancangan Terdapat 3 hal yang akan dianalisis, yaitu: 1. Rasio kompresi yang dihasilkan. 2. Ukuran file citra hasil kompresi. 3. Lama proses kompresi dan dekompresi file citra
5.1 Analisis Rasio dan Ukuran File Kompresi antara Algoritma Arithmetic Coding dan ShannonFano Pada pengujian pertama ini kita akan melihat ukuran rasio kompresi yang dihasilkan oleh kedua algoritma. Hasil pengujian dapat dilihat pada tabel di bawah ini. Tabel 1. Rasio dan Ukuran File Kompresi Algoritma Arithmetic Coding dan Shannon-Fano
5.2 Analisis Kecepatan Proses Kompresi dan Dekompresi Citra antara Algoritma Arithmetic Coding dan Shannon-Fano
6. Kesimpulan Setelah melakukan implementasi dan analisis terhadap algoritma Arithmetic Coding dan ShannonFano, maka dapat ditarik kesimpulan sebagai berikut: 1.
Kecepatan proses kompresi terhadap citra uji dengan menggunakan algoritma Arithmetic Coding dan Shannon-Fano dapat dilihat dalam tabel dan gambar dibawah ini.
2.
Tabel 2. Kecepatan Proses Kompresi Algoritma Arithmetic Coding dan Shannon-Fano 3.
4.
5.
Kecepatan proses dekompresi terhadap citra uji dengan menggunakan algoritma Arithmetic Coding dan Shannon-Fano dapat dilihat pada tabel dibawah ini. Tabel 3. Kecepatan Proses Dekompresi Algoritma Arithmetic Coding dan Shannon-Fano
6.
Pada algoritma Shannon-Fano dan Arithmetic Coding dapat digunakan untuk kompresi dan dekompresi pada citra. Algoritma Shannon-Fano dan Arithmetic Coding dapat mengembalikan citra yang telah dikompresi, citra yang dihasilkan sama dengan citra aslinya sehingga kedua algoritma tersebut termasuk pada teknik Lossless. Hasil kompresi dan rasio kompresi yang dihasilkan oleh Algoritma Arithmetic Coding lebih baik daripada algoritma Shannon-Fano. Rasio rata-rata pada Arithmetic Coding 62,88 % dan ShannonFano 61,73 %. Algoritma kompresi Arithmetic Coding dapat melakukan kompresi pada citra uji lebih baik daripada algoritma Shannon-Fano. Ukuran file ratarata hasil kompresi Arithmetic Coding (177732,2 byte) dan kompresi Shannon-Fano (177750,2 byte). Algoritma Arithmetic Coding memiliki waktu kompresi yang lebih cepat dibandingkan algoritma Shannon-Fano. Kecepatan rata-rata proses kompresi algoritma Arithmetic Coding (0,072449 detik) dan kecepatan proses kompresi Shannon-Fano (0,077838 detik), karena pada algoritma Arithmetic Coding memiliki teknik kompresi dengan mengambil seluruh warna yang telah difrekuensikan tiap warna yang sama pada tiap piksel dengan 1 simbol saja atau disebut ES (Encoded Symbol). Sedangkan pada algoritma Shannon-Fano memiliki teknik kompresi dengan mengambil seluruh warna yang telah difrekuensikan tiap warna yang sama pada tiap piksel juga, tetapi tiap warna tersebut diberi simbol atau disebut SF Code, sehingga membutuhkan waktu yang lama. Kecepatan rata-rata proses dekompresi algoritma Shannon-Fano lebih baik daripada algoritma Arithmetic Coding, dengan kecepatan dekompresi algoritma Shannon-Fano (0,028946 detik) dan kecepatan proses dekompresi Arithmetic Coding (0,034169 detik), karena pada algoritma ShannonFano tiap warna yang telah diberi simbol langsung dapat dikonversikan ke tiap warna asli, sedangkan algoritma Arithmetic Coding harus mengkalkulasi ES (Encoded Symbol) hingga dapat simbol-simbol pada tiap warna agar menjadi gambar asli.
7. Daftar Pustaka [1] Pu. Ida. Mengyi. 2006. Fundamental Data Compression. London: Elsevier. [2] Ahmad. Usman. 2005. Pengetahuan Citra Digital. Bogor: Graha Ilmu. [3] Sawaluddin. Syahriol Sitorus. Suyanto. Suriawan, Harahap, Jannes, Hutagalung. 2006. Pengolahan Citra Digital. Medan: Ilmu Komputer FMIPA USU. [4] Salomon, D. 2007. Data Compression The Complete Reference. 4𝑡ℎ Edition. Northridge: Springer. [5] Sutoyo, T. Mulyanto, Edy. Suhartono, Vincent. Nurhayati, Oky D. Wijanarto. 2009. Teori Pengolahan Citra Digital. Semarang: Andi.
