ANALISIS DAN PERBANDINGAN TEKNIK KOMPRESI MENGGUNAKAN ALGORITMA SHANNON-FANO DAN RUN LENGTH ENCODING PADA CITRA BERFORMAT BMP DAN PNG
SKRIPSI
ROHANI NASUTION 081401059
PROGRAM STUDI S-1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2012
Universitas Sumatera Utara
ANALISIS DAN PERBANDINGAN TEKNIK KOMPRESI MENGGUNAKAN ALGORITMA SHANNON-FANO DAN RUN LENGTH ENCODING PADA CITRA BERFORMAT BMP DAN PNG SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Komputer
ROHANI NASUTION 081401059
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS ILMU KOMPTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2012
Universitas Sumatera Utara
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: ANALISIS DAN PERBANDINGAN TEKNIK KOMPRESI DENGAN MENGGUNAKAN ALGORITMA SHANNON-FANO DAN RUN LENGTH ENCODING PADA CITRA BERFOMAT BMP DAN PNG : SKRIPSI : ROHANI NASUTION : 081401059 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Diluluskan di Medan, Agustus 2012 Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Ade Candra, ST, M.Kom NIP 197909042009121002
Marihat Situmorang, M.Kom NIP 196312141989031001
Diketahui/Disetujui oleh Departemen Ilmu Komputer FMIPA USU Ketua,
Dr. Poltak Sihombing, M.Kom NIP 196203171991021001
Universitas Sumatera Utara
PERNYATAAN
ANALISIS DAN PERBANDINGAN TEKNIK KOMPRESI DENGAN MENGGUNAKAN ALGORITMA SHANNON-FANO DAN RUN LENGTH ENCODING PADA CITRA BERFORMAT BMP DAN PNG
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan,
Agustus 2012
ROHANI NASUTION
081401059
Universitas Sumatera Utara
PENGHARGAAN Segala dan puji syukur penulis panjatkan hanya bagi Allah SWT, Pemelihara seluruh alam raya, yang atas limpahan rahmat, taufik dan hidayah-Nya, penulis mampu menyelesaikan Tugas Akhir ini, serta shalawat dan beriring salam penulis ucapakan kepada Nabi Besar Muhammad SAW. Tugas akhir ini dikerjakan demi memenuhi salah satu syarat guna memperoleh gelar Sarjana Komputer
Fakultas
Ilmu Komputer dan Teknologi Informasi
Universitas Sumatera Utara. Penulis menyadari bahwa tugas akhir ini bukanlah tujuan akhir dari belajar karena belajar adalah sesuatu yang tidak terbatas. Terselesaikannya skripsi ini tentunya tak lepas dari dorongan dan uluran tangan berbagai pihak. Oleh karena itu, dengan segala kerendahan hati penulis mengungkapkan rasa terima kasih dan penghargaan kepada : 1. Bapak Drs. Marihat Situmorang M.Kom, selaku pembimbing I yang telah memberikan masukan, bimbingan, serta saran ayng membangun untuk penulis. 2. Bapak Ade Candra ST,M,Kom, selaku pembimbing II yang telah memberikan masukan, bimbingan, saran dan motivasi kepada penulis, serta meluangkan banyak waktu dan sabar membantu sehingga penulis dapat menyelesaikan skripsi ini dengan baik 3. Bapak Dr. Poltak Sihombing, M, Kom selaku Ketua Departemen Ilmu Komputer dan sebagai dosen penguji I penulis yang telah memberikan kritik dan saran yang berguna bagi penulis 4. Ibu Dian Wirdasari S, Si, M.Kom sebagai penguji II yang telah memberikan kritik dan saran yang membangun bagi penulis. 5. Ibu Maya Silvi Lydia B, Sc., M.Sc selaku Sekretaris Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 6. Ibu Dian Rahmawati, S.Si, M.Kom selaku Ketua T.A Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 7. Dekan dan Pembantu Dekan Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 8. Orang tua tercinta, Ayahanda Ahmad.Z. Nasution dan Ibunda Basiah Selian, atas semua doa, dukungan, dan motivasi yang tak ternilai harganya.
Universitas Sumatera Utara
9. Abang tersayang Adi suharjono Nasution, Amarullah Nasution, Dedi Irawan dan adik tersayang Alas syah Putra Doli Nasution,beserta seluruh keluarga besar yang selalu memberikan dukungan, dan spesial untuk Alm.nenek tersayang Baniah Selian yang mempunyai harapan besar kepada penulis. 10.
Keluarga besar Ilmu Komputer, khususnya Herna J.Pakpahan,
Alvi
Syukriati Hasibuan, Rima Lestari dan semua teman, kerabat, dan sahabat angkatan 2008 yang tidak dapat disebutkan satu persatu, terima kasih atas ide, saran, dan kerja samanya selama ini. Semoga Allah SWT membalas semua kebaikan yang telah kalian berikan.
Penulis,
( Rohani Nasution)
Universitas Sumatera Utara
ABSTRAK File citra digital memiliki ukuran (size) yang lebih besar dibandingkan dengan file teks. Untuk mengurangi ukuran file citra tersebut dilakukan dengan kompresi yang bertujuan meminimalkan kebutuhan tempat pada media penyimpanan serta untuk mempercepat pengiriman melalui media komunikasi. Pada penelitian ini file citra dikompresi dengan teknik lossless menghasilkan file kompresi dengan ukuran yang lebih kecil dari file aslinya. Algoritma yang digunakan pada teknik lossless ini adalah Shannon-Fano dan Run Length Encoding.Dari hasil pengujian file citra yang telah dikompresi dengan Algoritma Shannon-Fano dan Run Length Encoding pada citra format BMP memiliki rasio kompresi: 29.32 % dan waktu: 18 detik.Algoritma Shannon-Fano pada citra format PNG memiliki rasio kompresi -7.90 % dan waktu: 12 detik, dan Run Length Encoding pada citra format PNG rasio kompresi -1.00% dan waktu rata-rata: 12 detik. Kata Kunci : Kompresi, Dekompresi, Shannon-Fano, Run Lenght Encoding, Citra BMP dan PNG
Universitas Sumatera Utara
ANALYSIS AND COMPARISON OF COMPRESSION TECHNIQUE USING SHANNON-FANO ALGORITHM AND RUN LENGTH ENCODING IN IMAGE FORMATS SUCH AS BMP AND PNG ABSTRACT Digital image Files have a size (size) are larger compared to a text file. To reduce the size of image files is done with the aim to minimize the need for compression places on storage media as well as to expedite delivery through the communication media. In this study an image file compressed with lossless compression techniques produce file sizes smaller than the original file. The algorithms used in lossless techniques this is Shannon-Fano and Run Length Encoding of image file test results that have been compressed with Shannon-Fano Algorithm and Run Length Encoding in image format BMP has a compression ratio: 29.32% and time: 18 seconds.Shannon-Fano algorithm in image format PNG has a compression ratio-7.90% and time: 12 seconds, and Run Length Encoding in image format PNG compression ratio-1.00% and the average time: 12 seconds.
Keywords: compression, Decompression, Shannon-Fano, Run Lenght Encoding, Image BMP and PNG
Universitas Sumatera Utara
DAFTAR ISI
Halaman
Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
ii iii iv v vi vii xi xii
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 3 3 3 4 4 5
Bab 2
Tinjauan Pustaka 2.1 Citra Digital 2.1.1 Representasi Warna Digital 2.1.2 Format Citra Bitmap 2.1.3 Citra Format PNG (Portable Network Graphics) 2.2 Kompresi Data 2.3 Dekompresi Data 2.4 Algoritma Shannon-Fano 2.5 Run Length Encoding 2.6 Pembacaan File Citra 2.7 Nilai Grayscale Citra 2.8 UML ( Unified Modeling Language) 2.8.1 Use Case Diagram 2.8.1.1 Actor 2.8.1.2 Use-Case 2.8.1.3 Interaksi Actor dengan Use-Case 2.8.2 Activity Diagram 2.8.3 Class Diagram 2.8.4 Sequence Diagram 2.8.5 Package Diagram 2.8.6 Deployment Diagram
6 7 8 9 9 11 12 15 17 19 19 20 20 20 21 21 22 23 23 24
Universitas Sumatera Utara
Bab 3
2.8.7 Analisi Persyaratan dengan UML 2.8.8 Desain dengan UML 2.9 Flowchart
25 26 26
Analisis dan Perancangan Sistem 3.1 Analisis 3.1.1 Analisis Masalah(Problem Analysis) 3.1.1.1 Diagram Konteks 3.1.2 Analisis Persyaratan (Requiment Analysis) 3.1.2.1 Fungsional sistem 3.1.2.2 Non-Fungsional Sistem 3.1.3 Pemodelan Sistem dengan Use Case 3.1.3.1 Use Case Diagram 3.1.3.2 Activity Diagram 3.1.3.3 Sequence Diagram 3.1.4 Flowchart 3.1.4.1 Flowchart Kompresi Algoritma Shannon- Fano 37 3.1.4.2 Flowchart Dekompresi Algoritma Shanno-Fano 39 3.1.4.3 Flowchart Kompresi Algoritma RLE 40 3.1.4.4 Flowchart Dekompresi Algoritma RLE 41
28 28 28 29 29 29 30 30 30 35 37 37
3.2
Rancangan Perangkat Lunak 3.2.3 Perancangan Menu Utama 3.2.4 Perancangan Kompresi dan Dekompresi 3.2.5 Rancangan Help 3.2.6 Rancangan About 3.2.7 Rancangan Hasil Pengujian Sistem
Bab 4 Implementasi dan Pengujian 4.1 Implementasi 4.1.1 Menghitung Nilai Grayscale 4.1.2 Kompresi Citra dengan Algoritma Shannon-Fano 4.1.3 Pembentukan Pohon Shannon-Fano 4.1.4 Dekompresi Algoritma Shannon-Fano 4.1.5 Kompresi Algoritma Run Length Encoding (RLE) 4.1.6 Dekompresi Algoritma Run Length Encoding (RLE 4.1.7 Tampilan Source Code Kompresi 4.1.8 Tampilan Source Code Dekompresi 4.2 Pengujian Program 4.2.1 Pengujian BlackBox 4.2.2
43 43 43 45 45 46 48 48 49 51 55 59 63 65 66 67 67 68
Pengujian Kompresi Citra Format BMP Pada
Universitas Sumatera Utara
Algoritma Shannon Fano 4.2.3
68
Pengujian Dekompresi File Citra Format BMP Pada Algoritma Shannon Fano
4.2.4
69
Pengujian Kompresi Citra Format BMP Pada Algoritma RLE
4.2.5
70
Pengujian Dekompresi File Citra Format BMP dengan Algoritma RLE
4.2.6
71
Pengujian Kompresi File Citra Format Png Pada Algoritma Shannon Fano
4.2.7
72
Pengujian Dekompresi File Citra Format PNG pada algoritma Shannon-Fano
4.2.8
73
Pengujian Kompresi File Citra Format PNG pada Algoritma RLE
4.2.9
pengujian Dekompresi File Citra Format PNG pada Algoritma RLE
Bab 5
74
Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
Daftar Pustaka Lampiran Hasil Pengujian Sistem Lampiran A Listing Program
75
77 77 78 79 A-1 B-1
Universitas Sumatera Utara
DAFTAR TABEL Tabel 2.1 2.2 2.3 2.4 2.5 2.6 3.1 3.2 3.3 3.4 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16. 4.17
Keterangan
Halaman
Hubungan antara bit per piksel dengan jumlah warna maksimum pada bitmap Frekuensi Kemunculan Kode Shannon-Fano Metode Kompresi RLE Metode Dekompresi RLE
Simbol-simbol Flowchart Program Cause-and-Effect Analisis Dokumentasi Naratif Use-Case Kompresi Dokumentasi Naratif Use-Case Lanjutan Dokumentasi Naratif Use-Case Dekompresi
Tabel Frekuensi Nilai Frekuensi terbesar Label Bit
Kelompok 3 Nilai Frekuensi terbesar Nilai Frekuensi terbesar Nilai Frekuensi terbesar Nilai Frekuensi terbesar Nilai Frekuensi terbesar Nilai Frekuensi terbesar Nilai Frekuensi terbesar Hasil Kompresi Shannon-Fano Hasil Kompresi Shannon-Fano Bit Hasil Kompresi Bit Hasil Kompresi Hasil Bit Hasil Kompresi
9 14 15 16 16 26 28 32 33 34 51 52 52 52 53 53 53 54 54 54 55 55 57 58 59 61 62
Universitas Sumatera Utara
DAFTAR GAMBAR Gambar 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12
Keterangan Kordinat Citra Digital Alur kompresi Lossless Pohon Biner Shannon -Fano Pohon Shannon-Fano Contoh nilai Piksel Citra Warna Citra Warna 300 x 200 Piksel Citra Grayscale
Matriks Nilai Grayscale Actor
Use-Case Use-Case Diagram Activity Diagram Class Diagram Sequence Diagram
Packege Diagram Deployment Diagram Diagram Konteks Use Case Diagram Activity Diagram Activity Diagram Sequence Diagram Dekompresi Flowchart Kompresi Algoritma Shannon Fano Flowchart Dekompresi Algoritma Shannon Fano Flowchart Kompresi Algoritma RLE Flowchart Kompresi Algoritma RLE Lanjutan Flowchart Dekompresi Algoritma RLE Flowchart Dekompresi Algoritma RLE Lanjutan Rancangan Menu Utama Rancangan Kompresi dan Dekompresi Rancangan Help Rancangan About Rancangan Hasil Pengujian Sistem Citra Warna 200 x133 piksel Matriks Nilai RGB Citra Warna Matriks Nilai Grayscale Pohon Shannon-Fano Nilai piksel Citra Matrik Nilai Grayscale Citra Asli Matrik Citra Asli Kompresi Pohon Shannon-Fano Matriks Citra Hasil Dekompresi Matriks Citra Asli Proses Kompresi Citra Run Lenght Encoding Matriks Citra Hasil Kompresi Matriks Citra Kompresi
halaman 6 12 13 14 17 18 18 19 20 20 21 21 22 23 24 24 29 32 35 36 37 38 39 40 41 41 42 43 44 45 45 46 47 48 50 51 57 58 59 62 62 63 63 64
Universitas Sumatera Utara
4.13
Matriks Citra Hasil Sementara
64
4.14 4.15 4.16 4.17
Matriks Citra Hasil Dekompresi Tampilan Source Code Kompresi Tampilan Source Code Dekompresi Tampilan Pengujian Kompresi Citra Format BMP Pada Algoritma Shannon-Fano
65 66 67 68
4.20
Tampilan Pengujian Kompresi Citra Format BMP Pada Algoritma Shannon-Fano
69
4.21
Tampilan Pengujian Kompresi File Citra Format BMP Pada Algoritma RLE
70
4.22
71 Tampilan Pengujian Dekompresi File Citra Format BMP Pada Algoritma RLE
4.23
Tampilan Pengujian Kompresi File Citra Format PNG pada Algoritma Shannon-Fano
72
4.24
Tampilan Pengujian Dekompresi File Citra Format PNG Shannon-Fano
73
4.23
Tampilan Pengujian Kompresi File Citra Format PNG pada Algoritma RLE
74
4.24
Tampilan Pengujian Dekompresi File Citra Format PNG pada Algoritma RLE
75
Universitas Sumatera Utara
