IMPLEMENTASI DAN ANALISIS KINERJA ALGORITMA ARITHMETIC CODING DAN SHANNON-FANO PADA KOMPRESI CITRA BMP
SKRIPSI
SYAHFITRI KARTIKA LIDYA 081402070
PROGRAM STUDI TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2012
IMPLEMENTASI DAN ANALISIS KINERJA ALGORITMA ARIHTMETIC CODING DAN SHANNON-FANO PADA KOMPRESI CITRA BMP
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Teknologi Informasi
SYAHFITRI KARTIKA LIDYA 081402070
PROGRAM STUDI TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2012
ii
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: IMPLEMENTASI DAN ANALISIS KINERJA ALGORITMA ARITHMETIC CODING DAN SHANNON-FANO PADA KOMPRESI CITRA BMP : SKRIPSI : SYAHFITRI KARTIKA LIDYA : 081402070 : SARJANA (S1) TEKNOLOGI INFORMASI : TEKNOLOGI INFORMASI : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI (FASILKOM-TI) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, 18 Juli 2012
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Romi Fadillah R, B.Comp.Sc.M.Sc. NIP. 198603032010121004
M. Andri Budiman, ST.M.Comp.Sc.M.E.M. NIP. 197510082008011011
Diketahui/Disetujui oleh Program Studi S1 Teknologi Informasi Ketua,
Prof. Opim Salim Sitompul, M.Sc NIP. 196108171987011001
iii
PERNYATAAN
IMPLEMENTASI DAN ANALISIS KINERJA ALGORITMA ARITHMETIC CODING DAN SHANNON-FANO PADA KOMPRESI CITRA BMP
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, 18 Juli 2012
Syahfitri Kartika Lidya 081402070
iv
PENGHARGAAN
Puji syukur saya panjatkan kehadirat Allah SWT, yang telah memberikan rahmat dan hidayah-Nya serta segala sesuatunya dalam hidup, sehingga saya dapat menyelesaikan penyusunan Skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Teknologi Informasi, Program Studi S1 Teknologi Informasi Universitas Sumatera Utara. Dalam pengerjaan Skripsi ini penulis banyak sekali mendapatkan dukungan, saran, dan nasehat dari berbagai pihak. Dalam kesempatan ini penulis mengucapkan terima kasih kepada: Bapak M. Andri Budiman, ST.M.Comp.Sc.M.E.M, selaku Dosen Pembimbing I, yang telah bersedia meluangkan waktu dan pikirannya dalam membimbing, memotivasi untuk menyelesaikan Skripsi ini. Bapak Romi Fadillah Rahmat, B.Comp.Sc.M.Sc, selaku Dosen Pembimbing II, yang telah bersedia meluangkan waktu dan pikirannya dalam menyelesaikan Skripsi ini, Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Jurusan Prof. Dr. Opim Salim Sitompul, M.Sc dan Drs. Sawaluddin, M.IT, serta kepada dosen-dosen Program Studi Teknologi dan pegawai di Program Studi Teknologi Informasi, khususnya bu Delima, kak Umi, kak Maya, bang Faisal, kak Wardah, bu Lia yang telah membantu kelancaran proses administrasi. Segala hormat dan terima kasih secara khusus penulis ucapkan kepada ayahanda Yonnes Hasan dan Ibunda Nova Mustika atas motivasi, kasih sayang, dan dukungan baik secara materi maupun do’a yang tak pernah putus yang diberikan kepada penulis, tak lupa kepada adik-adik tersayang Vayon Rachmat Ramadhan dan Sabilla Afiya, serta tante tersayang Julia Reveny telah memberi motivasi dan nasehat. Tidak lupa kepada seluruh sahabat penulis Stambuk 2008 yang selalu berusaha menjadi sahabat terbaik dan tidak mudah putus asa khususnya Karina Ayesha, Cahya, Ishri, Mauza, Karina Andi. Penulis berharap bahwa Skripsi ini bermanfaat terutama kepada penulis maupun para pembaca. Saya menyadari bahwa Skripsi ini perlu saran dan kritik yang bersifat membangun demi kesempurnaan Skripsi ini sehingga dapat bermanfaat bagi kita semua. Sekali lagi saya ucapkan terima kasih atas segalanya. Semoga segala kebaikan diberikan balasan yang setimpal oleh Allah SWT.
v
ABSTRAK
Perkembangan teknologi yang pesat, sangat berperan penting dalam pertukaran informasi yang cepat. 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 skripsi 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
vi
ABSTRACT
Rapid technological developments, a very important role in the rapid exchange of information. On the transmission of information in the form of the image is still experiencing problems, such as the large size of the image so that the solution to that problem is to do the compression. In this thesis will implement and compare the performance of the algorithm Arithmetic Coding and Shannon-Fano through the calculation of compression ratio, the size of the compressed file, the speed of compression and decompression process. Based on all the test results, that Arithmetic Coding algorithm yielded an average compression ratio of 62.88% and a compression ratio Shannon-Fano of 61.73%, Arithmetic Coding the average speed in image compression is 0.072449 seconds and Shannon-Fano 0,077838 seconds. Then the Shannon-Fano algorithm has an average speed for the decompression algorithm is 0.028946 second and Arithmetic Coding 0.034169 seconds. Image decompression algorithm results Arithmetic Coding and Shannon-Fano line with the original image. Can be concluded from the results of testing that Arithmetic Coding algorithm is more efficient in image compression *.bmp than Shannon-Fano algorithm, although in terms of Shannon-Fano decompress a bit faster than Arithmetic Coding.
Keyword : image compression, Arithmetic Coding, Shannon-Fano
vii DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
ii iii iv v vi vii ix x
Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metode Penelitian 1.7 Sistematika Penulisan
1 1 2 3 3 3 4 5
Bab 2 Landasan Teori 2.1 Definisi Citra 2.2 Definisi Citra Digital 2.2.1 Citra BMP 2.3 Operasi-Operasi pada Pengolahan Citra 2.4 Kompresi Citra 2.4.1 Teknik Kompresi Citra 2.4.2 Algoritma Arithmetic Coding 2.4.3 Algoritma Shannon-Fano 2.5 Pengenalan Visual Basic 2.5.1 Microsoft Visual Basic 2008 Express Edition
7 7 8 11 13 14 17 20 22 23 24
Bab 3 Analisis dan Perancangan Sistem 3.1 Analisis Kinerja Algoritma Arithmetic Coding 3.1.1 Proses Kompresi Arithmetic Coding 3.1.2 Proses Dekompresi Arithmetic Coding 3.1.3 Kompresi Arithmetic Coding pada Citra 3.1.4 Dekompresi Arithmetic Coding pada Citra 3.2 Analisis Kinerja Algoritma Shannon-Fano 3.2.1 Proses Kompresi Shannon-Fano 3.2.2 Proses Dekompresi Shannon-Fano 3.2.3 Kompresi Shannon-Fano pada Citra 3.2.4 Dekompresi Shannon-Fano pada Citra
26 26 28 29 30 35 38 40 41 41 43
viii 3.3 Perancangan Sistem 44 3.3.1 Arsitektur Sistem 44 3.3.2 Rancangan DFD Kompresi dan Dekompresi 46 3.3.2.1 Rancangan DFD Kompresi dan Dekompresi pada Algoritma Arithmetic Coding 47 3.3.2.2 Rancangan DFD Kompresi dan Dekompresi pada Algoritma Shannon-Fano 50 3.3.3 Rancangan Prosedural 53 3.3.3.1 Proses Aplikasi Algoritma Arithmetic Coding dan ShannonFano 55 3.3.4 Rancangan Antarmuka 56 3.3.4.1 Rancangan Menu Utama 56 3.3.4.2 Rancangan Menu “Algoritma Kompresi” 57 3.3.4.3 Rancangan Menu “Kompresi” Aritmetic Coding 58 3.3.4.4 Rancangan Menu “Dekompresi” Aritmetic Coding 59 3.3.4.5 Rancangan Menu “Kompresi” Shannon-Fano 60 3.3.4.6 Rancangan Menu “Dekompresi” Shannon-Fano 61 3.3.4.7 Rancangan Menu “Bantuan” 63 Bab 4 Implementasi dan Pengujian Sistem 4.1 Implementasi Sistem 4.1.1 Spesifikasi Perangkat Keras dan Perangkat Lunak yang Digunakan 4.1.2 Tampilan Menu Utama 4.1.3 Tampilan Menu “Algoritma Kompresi” 4.1.4 Tampilan Menu “Kompresi” Arithmetic Coding 4.1.5 Tampilan Menu “Dekompresi” Arithmetic Coding 4.1.6 Tampilan Menu “Kompresi” Shannon-Fano 4.1.7 Tampilan Menu “Dekompresi” Shannon-Fano 4.1.8 Tampilan Menu “Bantuan” 4.2 Pengujian 4.2.1 Skenario Pengujian 4.2.2 Analisis Data Hasil Pengujian Sistem 4.2.2.1 Analisis Rasio dan Ukuran File Kompresi antara Algoritma Arithmetic Coding dan Shannon-Fano 4.2.2.2 Analisis Ukuran File Citra Hasil Kompresi antara Algoritma Arithmetic Coding dan Shannon-Fano 4.2.2.3 Analisis Kecepatan Proses Kompresi dan Dekompresi Citra antara Algoritma Arithmetic Coding dan Shannon-Fano Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
64 64 64 65 65 66 69 71 74 77 77 77 83
Daftar Pustaka
93
83 86 87 91 91 92
ix
DAFTAR TABEL
Halaman Tabel 2.1 Contoh Warna 24 bit Tabel 2.2 Keterangan Gambar 2.11 Tabel 3.1 Tabel Probabilitas dan Range untuk Gambar 3.4 Tabel 3.2 Proses Encoding untuk Gambar 3.4 Tabel 3.3 Tabel Range Probabilitas Tabel 3.4 Proses Decoding untuk Gambar 3.4 Tabel 3.5 Frekuensi Kemunculan Simbol Tabel 3.6 Proses Pengkodean Tabel 3.7 Kode dan Panjang Kode Shannon-Fano Tabel 4.1 Citra Uji Tabel 4.2 Rasio dan Ukuran File Kompresi Algoritma Arithmetic Coding dan Shannon-Fano Tabel 4.3 Kecepatan Proses Kompresi Algoritma Arithmetic Coding dan Shannon-Fano Tabel 4.4 Kecepatan Proses Dekompresi Algoritma Arithmetic Coding dan Shannon-Fano
13 25 31 34 35 38 42 43 43 77 83 86 88
x
DAFTAR GAMBAR
Halaman Gambar 2.1 Langkah-Langkah Pengolahan Citra Digital 8 Gambar 2.2 Koordinat Citra Digital 10 Gambar 2.3 Matriks Citra Digital N x M 10 Gambar 2.4 Ilustrasi Sistem Matriks Citra Digital 8 x 8 Piksel 11 Gambar 2.5 Komposisi Warna RGB 13 Gambar 2.6 Alur Kompresi dan Dekompresi 16 Gambar 2.7 Rumus Rasio Kompresi 17 Gambar 2.8 Ilustrasi Kompresi Lossless 18 Gambar 2.9 Ilustrasi Kompresi Lossy 19 Gambar 2.10 Antarmuka pada Aplikasi Visual Basic 2008 Express Edition 25 Gambar 3.1 Flowchart Proses Kompresi Algoritma Arithmetic Coding 28 Gambar 3.2 Flowchart Proses Dekompresi Algoritma Arithmetic Coding 29 Gambar 3.3 Citra Berwarna 2 x 2 Piksel 30 Gambar 3.4 Matriks Citra Berwarna 2 x 2 Piksel 30 Gambar 3.5 Flowchart Proses Kompresi Algoritma Shannon-Fano 40 Gambar 3.6 Flowchart Proses Dekompresi Algoritma Shannon-Fano 41 Gambar 3.7 Citra Berwarna 2 x 2 Piksel 42 Gambar 3.8 Matriks Citra Berwarna 2 x 2 Piksel 42 Gambar 3.9 Matriks Citra Berwarna 2 x 2 Piksel setelah di Subtitusi ke SF 43 Gambar 3.10 Proses Subtitusi SF Code ke Simbol Warna 44 Gambar 3.11 Arsitektur Sistem Algoritma Arithmetic Coding 45 Gambar 3.12 Arsitektur Sistem Algoritma Shannon-Fano Coding 46 Gambar 3.13 Komponen DFD Menurut Yourdan dan DeMarco 46 Gambar 3.14 Rancangan DFD Level 0 Proses Kompresi / Dekompresi Algoritma Arithmetic Coding 47 Gambar 3.15 Rancangan DFD Level 1 P.0.1 untuk Proses Kompresi dan Dekompresi Algoritma Arithmetic Coding 48 Gambar 3.16 Rancangan DFD Level 2 P.1.1 untuk Proses Kompresi Algoritma Arithmetic Coding 49 Gambar 3.17 Rancangan DFD Level 2 P.1.2 untuk Proses Dekompresi Algoritma Arithmetic Coding 50 Gambar 3.18 Rancangan DFD Level 0 Proses Kompresi / Dekompresi Algoritma Shannon-Fano 51 Gambar 3.19 Rancangan DFD Level 1 P.0.1 untuk Proses Kompresi dan Dekompresi Algoritma Shannon-Fano 51 Gambar 3.20 Rancangan DFD Level 2 P.1.1 untuk Proses Kompresi Algoritma Shannon-Fano 52 Gambar 3.21 Rancangan DFD Level 2 P.1.2 untuk Proses Dekompresi Algoritma
xi Shannon-Fano 53 Gambar 3.22 Flowchart Sistem Kompresi dan Dekompresi Secara Umum 54 Gambar 3.23 Flowchart Aplikasi Algoritma Arithmetic Coding dan Shannon-Fano 55 Gambar 3.24 Rancangan Menu Utama 56 Gambar 3.25 Rancangan Menu “Algoritma Kompresi” 57 Gambar 3.26 Rancangan Menu “Kompresi” Arithmetic Coding 58 Gambar 3.27 Rancangan Menu “Dekompresi” Arithmetic Coding 59 Gambar 3.28 Rancangan Menu “Kompresi” Shannon-Fano 60 Gambar 3.29 Rancangan Menu “Dekompresi” Shannon-Fano 62 Gambar 3.30 Rancangan Menu “Bantuan” 63 Gambar 4.1 Tampilan Menu Utama 64 Gambar 4.2 Tampilan Menu “Algoritma Kompresi” 65 Gambar 4.3 Tampilan Menu “Kompresi” Arithmetic Coding 65 Gambar 4.4 Tampilan Menu “Buka” File citra bmp pada Arithmetic Coding 66 Gambar 4.5 Tampilan Menentukan Lokasi Penyimpanan Hasil Kompresi File Citra Arithmetic Coding 67 Gambar 4.6 Tampilan Hasil Kompresi File Citra pada Arithmetic Coding 67 Gambar 4.7 Tampilan Menu “Dekompresi” Arithmetic Coding 68 Gambar 4.8 Tampilan Menu “Buka” File .acf 69 Gambar 4.9 Tampilan Menentukan Lokasi Penyimpanan Hasil Dekompresi File .acf 69 Gambar 4.10 Tampilan Hasil Dekompresi File .acf 70 Gambar 4.11 Tampilan Menu “Kompresi” Shannon-Fano 70 Gambar 4.12 Tampilan Menu “Buka” File citra bmp pada Shannon-Fano 71 Gambar 4.13 Tampilan Menentukan Lokasi Penyimpanan Hasil Kompresi File Citra Shannon-Fano 72 Gambar 4.14 Tampilan Hasil Kompresi File Citra pada Shannon-Fano 72 Gambar 4.15 Tampilan Menu “Dekompresi” Shannon-Fano 73 Gambar 4.16 Tampilan menu “Buka” File .sf 74 Gambar 4.17 Tampilan Menentukan Lokasi Penyimpanan Hasil Dekompresi File .sf 74 Gambar 4.18 Tampilan Hasil Dekompresi File .sf 75 Gambar 4.19 Tampilan Menu “Bantuan” 76 Gambar 4.20 Perbandingan Rasio Kompresi Algoritma Arithmetic Coding dan Shannon-Fano 84 Gambar 4.21 Perbandingan Hasil Kompresi Algoritma Arithmetic Coding dan Shannon-Fano 85 Gambar 4.22 Perbandingan Kecepatan Kompresi Algoritma Arithmetic Coding dan Shannon-Fano 87 Gambar 4.23 Perbandingan Kecepatan Dekompresi Algoritma Arithmetic Coding dan Shannon-Fano 88
xii
