TUGAS AKHIR IMPLEMENTASI TEKNIK KOMPRESI GAMBAR DENGAN ALGORITMA SET PARTITIONING IN HIERARCHICAL TREES PADA PERANGKAT BERGERAK Diajukan untuk memenuhi salah satu persyaratan dalam menyelesaikan pendidikan sarjana (S-1) pada Departemen Teknik Elektro
O L E H
ICHSAN 070402007
DEPARTEMEN TEKNIK ELEKTRO FAKULTAS TEKNIK UNIVERSITAS SUMATERA UTARA MEDAN 2011
Universitas Sumatera Utara
IMPLEMENTASI TEKNIK KOMPRESI GAMBAR DENGAN ALGORITMA SET PARTITIONING IN HIERARCHICAL TREES PADA PERANGKAT BERGERAK Oleh :
ICHSAN 070402007
Tugas Akhir ini diajukan untuk melengkapi salah satu syarat untuk memperoleh gelar sarjana Teknik Elektro.
Disetujui Oleh : Dosen Pembimbing,
RAHMAD FAUZI ST,MT NIP : 196904241997021001 Diketahui Oleh : Ketua Departemen Teknik Elektro FT USU,
IR.SURYA TARMIZI KASIM M.SI NIP : 195405311986011002 DEPARTEMEN TEKNIK ELEKTRO FAKULTAS TEKNIK UNIVERSITAS SUMATERA UTARA MEDAN 2011
Universitas Sumatera Utara
ABSTRAK Kompresi ialah suatu proses pemampatan suatu data dari ukuran yang besar menjadi ukuran yang lebih sederhana tanpa menghilangkan kualitas data tersebut secara signifikan. Parameter yang digunakan untuk menentukan bagus atau tidaknya kompresi terdiri dari waktu melakukan kompresi, kebutuhan atau efisiensi memori, kualitas pemampatannya, dan format hasil keluaran kompresi tersebut. Metode kompresi lossy pada gambar merupakan salah satu metode pemampatan citra yang menghasilkan rasio pemampatan tinggi. Oleh karena itu penulis tertarik untuk melakukan penelitian terhadap kinerja (tingkat kompresi) data gambar dengan menggunakan salah satu metode kompresi menggunakan
Algoritma
Set
Partitioning
In
Hierarchical
Trees.
Dalam
implementasinya, di tugas akhir ini penulis membahas bagaimana dengan mengkompresi data gambar dengan Algoritma Set Partitioning In Hierarchical Trees ini kapasitas pentransferan data lebih cepat dan efisien. Dan implementasi
ini
disimulasikan pada perangkat bergerak yang berbasis Android Hasil akhir yang diperoleh, kompresi dengan algoritma Set Partitioninig In Hierarchical Trees mempunyai rasio kompresi 55,4% dengan menggunakan level kuantisasi 50 dan diperlukan waktu 104 detik. Setelah itu kompresi dengan algoritma Set Partitioninig In Hierarchical Trees dibandingkan lagi dengan Algoritma Huffman dan Algoritma Discrete Cosine Transform (DCT) dan dapat disimpulkan bahwa rasio kompresi menggunakan Algoritma Discrete Cosine Transform (DCT) dengan kualitas pemampatan hingga 64% dengan waktu kompresi 114 detik.
Universitas Sumatera Utara
Sedangkan untuk Algoritma Huffman kualitas pemampatannya hanya 10% dengan waktu kompresi 64 detik.
Universitas Sumatera Utara
KATA PENGANTAR Segala puji syukur penulis haturkan kehadirat Allah SWT yang telah memberikan kesehatan dan kemampuan dalam menyelesaikan Tugas Akhir ini, serta shalawat dan beriring salam penulis hadiahkan kepada junjungan Nabi Muhammad SAW. Tugas akhir ini merupakan bagian dari kurikulum yang harus diselesaikan untuk memenuhi persyaratan menyelesaikan pendidikan Sarjana Strata Satu di Departemen Teknik Elektro, Fakultas Teknik, Universitas Sumatera Utara. Adapun judul Tugas Akhir ini adalah : IMPLEMENTASI TEKNIK KOMPRESI GAMBAR DENGAN ALGORITMA SET PARTITIONING IN HIERARCHICAL TREES PADA PERANGKAT BERGERAK. Selama penulis menjalani pendidikan di kampus hingga diselesaikannya Tugas Akhir ini, penulis banyak menerima bantuan, bimbingan, dan dukungan dari berbagai pihak. Untuk itu dalam kesempatan ini penulis ingin mengucapkan terima kasih kepada: 1.
Bapak Rahmad Fauzi, ST, MT, selaku dosen Pembimbing Tugas Akhir, atas nasehat, bimbingan dan motivasi dalam menyelesaikan Tugas Akhir ini.
2.
Bapak (Alm) Ir. Mustafrind Lubis dan Bapak Ali Hanafiah Rambe, ST, MT, selaku Penasehat Akademis penulis, atas bimbingan dan arahannya dalam menyelesaikan perkuliahan selama ini.
3.
Bapak Ir.Surya Tarmizi Kasim, M.Si selaku Ketua Departemen Teknik Elektro, Fakultas Teknik, Universitas Sumatera Utara.
Universitas Sumatera Utara
4.
Seluruh staf pengajar yang telah memberi bekal ilmu kepada penulis dan seluruh pegawai Departemen Teknik Elektro, Fakultas Teknik, Universitas Sumatera Utara atas segala bantuannya.
5.
Kepada Bapak dan Ibu tercinta H.Yusril Ismail,BA dan Hj.Anni Sulasmi yang selalu merawat, menjaga, mendoakan dan memberikan segalanya kepada penulis sehingga penulisan Tugas Akhir ini dapat diselesaikan.
6.
Kakakku tersayang, Putri Ramadhani dan Sri Wulan Dhari dan seluruh Keluarga Besar yang selalu memberikan motivasi, perhatian dan doa’anya sehingga penulis dapat menyelesaikan Tugas Akhir ini.
7.
Euis Purnama Sari yang selalu menjadi inspirasi dan motivasi serta semangat buat penulis dalam menyelesaikan Tugas Akhir ini.
8.
Sahabat terbaik di Elektro: Yovi, Febri, Agus, Irzi, Ridwan, Raedy, Arynda, Sammy, Ridho, Arief, Fajar, Komeng, Boronk, Dion, Frans, Isan, Fitri, Suib, Dian, Roy, Aprial, Joshua, Indra, Reza, Shobirin, Nikmansyah, dan seluruh stambuk 2007, senior maupun junior semoga silaturrahmi kita terus terjaga.
9.
Keluarga Besar Laboratorium Pengukuran Listrik FT USU: Bapak Ir. Masykur Sjani, Kukuh, Habibi, Siska, Indra Noe, B’Penson, B’Mudin, K’Kesi, B’Megi dan Mas Dian.
10.
Para #Masbroblast Warrior, Wawan, Safar, Septy, Inal, I’am, Ivan, Abang, Adek, Fariz Gemboenk, Taqim, Thomie, Rickysano. Sahabat-sahabat terbaik Khairina Arman, Winny, Achie, B’Ekky, Winda, Richo, Dhika, Ian, temanteman dari SMeCK HOOLIGAN, Inter Club Indonesia Regional Medan.
Universitas Sumatera Utara
11.
Semua Pihak yang tidak sempat penulis sebutkan satu per satu. Penulis menyadari bahwa Tugas Akhir ini masih banyak kekurangan baik
dari segi materi maupun penyajiannya. Oleh karena itu saran dan kritik dengan tujuan menyempurnakan dan mengembangkan kajian dalam bidang ini sangat penulis harapkan. Akhir kata penulis berserah diri pada Allah SWT, semoga Tugas Akhir ini bermanfaat bagi pembaca sekalian terutama bagi penulis sendiri.
Medan, Juli 2011 Penulis
Ichsan NIM. 070402007
Universitas Sumatera Utara
DAFTAR ISI ABSTRAK................................................................................................
i
KATA PENGANTAR ..............................................................................
iii
DAFTAR ISI ............................................................................................
vi
DAFTAR GAMBAR ................................................................................
xi
DAFTAR TABEL ....................................................................................
xvi
DAFTAR LAMPIRAN...............................................................................
xvii
BAB I PENDAHULUAN 1.1 Latar Belakang………………………………………………………….
1
1.2 Rumusan Masalah ………………………………………………………
2
1.3 Tujuan Penulisan………………………………………………………..
3
1.4 Batasan Masalah………………………………………………………..
3
1.5 Metodologi Penulisan…………………………………………………..
4
1.6 Sistematika Penulisan…………………………………………………..
5
BAB II TEORI DASAR KOMPRESI GAMBAR 2.1 Pendahuluan……………………………………………………....………
7
2.2 Definisi Citra Analog…………………………………………..………...
7
2.3 Definisi Citra Digital……………..………………………………………
8
2.3.1 Model Citra Sederhana…………………………..………………...
8
2.3.2 Jenis-Jenis Citra Digital……..…..………………………………....
10
2.3.3 Elemen – Elemen Citra Digital…….……………………………….
11
2.4 Digitalisasi Citra...………………………………………………………...
13
2.4.1 Sampling….…………………………………………………………
13
Universitas Sumatera Utara
2.4.2 Kuantisasi……………………………………………………………
15
2.4.3 Derau………………………………………………………………...
19
2.5 Resolusi……..………………………………………………………….….
19
2.6 Format File Citra…...……………………………………………………..
21
2.7 Kompresi Data…..………………………………………………………...
28
2.8 Kompresi Citra…………………………………………………………….
31
2.8.1 Teknik Kompresi Citra……..………………………………………..
31
2.8.2 Manfaat Kompresi………………...…………………………………
33
2.8.3 Kriteria Kompresi……………………………………………………
34
2.8.4 Rasio Kompresi……………………………………………………...
36
2.9 Metode Kompresi………………………………………………………….
36
2.9.1 Metode Statis (Static Method)……………………………………..
36
2.9.2 Metode Kamus (Dictionary Method)………………………………
36
2.9.3 Hal – Hal Penting Dalam Kompresi Citra…………………………
37
2.9.4 Algoritma Kompresi - Dekompresi Citra………………………….
38
BAB III KOMPRESI DATA MENGGUNAKAN SET PARTITIONING IN HIERARCHICAL TREES 3.1 Set Partitioning In Hierarchical Trees…………………....…………….…..
39
3.2 Metode Dari Algoritma Set Partitioning In Hierarchical Trees...…….…….
42
3.3 Kompresi Gambar Dengan Algoritma Set Partitioning In Hierarchical Trees 45 3.4 Perbandingan Hasil Kompresi……………………………………………….
51
Universitas Sumatera Utara
BAB IV IMPLEMENTASI DAN APLIKASI TEKNIK KOMPRESI SET PARTITIONING IN HIERARCHICAL
TREES
PADA PERANGKAT
BERGERAK 4.1 Pendahuluan………………………………………………………………..
85
4.2 Android…………………………………………………………………….
85
4.3 Anatomi Android …………………………………………………………
86
4.4 Spesifikasi Perangkat Lunak……………………………………………….
87
4.5 Use Case Diagram…………….……………………………………………
89
4.6 Diagram Alir………………………………………………………………
90
4.7 Diagram Kelas Sistem...…………………………………………………..
91
4.8 Pembuatan Program Kompresi Gambar Dengan Algoritma Set Partitioning In Hierarchical Trees……………………………………………………….…
92
4.8.1 Pembuatan Tampilan Antar Muka (Interface)………………………..
93
4.8.2 Pembuatan Kelas Utama SPIHTforCompress……………….……….
94
4.8.3 Pembuatan Kelas Compress…………………………………………..
95
4.8.4 Pembuatan Kelas Decompress…………………………………...…...
96
4.8.5 Pembuatan Kelas DownloadFile………………………………………
97
4.8.6 Pembuatan Kelas Upload……………………………………………...
98
4.8.7 Pembuatan Kelas Uploader……………………………………………
99
4.8.8 Pembuatan Kelas Set Partitioning In Hierarchical Trees…...…....…..
100
4.8.9 Pembuatan Manifest Aplikasi………………………...……………….
101
4.9 Pengujian ………………………………………………………………...… 102 BAB V KESIMPULAN DAN SARAN
Universitas Sumatera Utara
5.1 Kesimpulan………………………………………………………….............
114
5.2 Saran………………………………………………………………...………
115
DAFTAR PUSTAKA……………………………………………………........
116
LAMPIRAN
Universitas Sumatera Utara
DAFTAR GAMBAR 1.
Gambar 2.1 Citra Digital………………………………………….....
8
2.
Gambar 2.2 Jenis – Jenis Citra Digital………………………………
10
3.
Gambar 2.3 (a) Citra Digital…………………………………………
15
Gambar 2.3 (b) Citra Digital Disampling Menjadi 14 Baris dan 12 Kolom 15 Gambar 2.3 (c) Citra Digital Hasil Sampling Berukuran 14 x 12 Pixel
15
4.
Gambar 2.4 Nilai Intensitas Warna…………………………………
17
5.
Gambar 2.5 Citra Digital Dalam Bentuk Asimetris………………...
18
6.
Gambar 2.6 Resolusi Gambar……………………………..………..
20
7.
Gambar 2.7 Contoh Gambar Format JPEG…………………………
22
8.
Gambar 2.8 Komposisi Warna RGB…………………………...…...
25
9.
Gambar 2.9 Proses Kompresi Data Secara Umum….………………
29
10.
Gambar 2.10 Proses Pengkodean Data Secara Umum……………….
29
11.
Gambar 2.11 Contoh Dari Chroma Subsampling…………………....
33
12.
Gambar 2.12 Proses Kompresi Data Secara Lossless dan Lossy……
33
13.
Gambar 3.1 Ilustrasi Hubungan Parent – Child Dari Koefisien SPIHT.
40
14.
Gambar 3.2 Diagram Alir Metode Set Partitioning In Hierarchical Trees 44
15.
Gambar 3.3 Kode Dari Suatu Encoder...................................................
45
16.
Gambar 3.4 Proses Inisialisasi Yang Pertama Kali Dilakukan………..
45
17.
Gambar 3.5 Proses Inisialisasi Setelah Sorting Pass Tahap Pertama
46
18.
Gambar 3.6 Perbaikan Tahap Pertama……………….……………. ..
47
19.
Gambar 3.7 Proses Tahapan Sorting Pass Yang Kedua......................
47
20.
Gambar 3.7 Hasil Dari Tahapan Sorting Pass Yang Kedua................
48
Universitas Sumatera Utara
21.
Gambar 3.9 Proses Tahapan Sorting Pass Yang Ketiga......................
49
22.
Gambar 3.10 Langkah Terakhir Dari Tahapan Sorting Pass………..
50
23.
Gambar 3.11 Pohon Biner Huffman Code……………………………
52
24.
Gambar 3.12 Pohon Huffman………………………………………...
56
25.
Gambar 3.13 Citra Sebelum Dikompres……………………………..
58
26.
Gambar 3.14 Citra Setelah Dikompres………………………………
58
27.
Gambar 3.15 Grafik Fungsi Basis 1-D DCT…………………………
63
28.
Gambar 3.16 Grafik Fungsi Basis 2-D DCT…………………………
65
29.
Gambar 3.17 Komponen dari Sistem Transmisi Data Gambar atau Video 66
30.
Gambar 3.18 Metode ZigZag Scanning……………………………..
79
31.
Gambar 3.19 Citra Sebelum Dikompres…………………………….
82
32.
Gambar 3.20 Citra Setelah Dikompres………………………………
82
33.
Gambar 4.1 Anatomi Android……………………………………….
87
34.
Gambar 4.2 Diagram Use Case………………………………………
89
35.
Gambar 4.3 Diagram Alir Koefisien SPIHT…………………………
90
36.
Gambar 4.4 Diagram Kelas Sistem…………………………………..
91
37.
Gambar 4.5 Diagram Alir Proses Penggunaan Program………….…
92
38.
Gambar 4.6 Diagram Alir Proses Pembuatan Interface……………..
93
39.
Gambar 4.7 Diagram Alir Proses Pembuatan Kelas Utama SPIHT for Compress……………………………………………………………..
94
40.
Gambar 4.8 Diagram Alir Proses Pembuatan Kelas Compress…….
95
41.
Gambar 4.9 Diagram Alir Proses Pembuatan Kelas Decompress….
96
42.
Gambar 4.10 Diagram Alir Proses Pembuatan Kelas Download File
97
Universitas Sumatera Utara
43.
Gambar 4.11 Diagram Alir Proses Pembuatan Kelas Upload………..
98
44.
Gambar 4.12 Diagram Alir Proses Pembuatan Kelas Uploader............
99
45.
Gambar 4.13 Diagram Alir Proses Pembuatan Kelas Set Partitioning In Hieararchical
Trees………………………………………………….
100 46.
Gambar 4.14 Diagram Alir Proses Pembuatan Kelas Manifest Aplikasi
101
47.
Gambar 4.15 Proses Pemunculan dan Eksekusi Aplikasi yang Berhasil ………………………………………………………………………….
102
48.
Gambar 4.16 Proses Loading Emulator Android Versi 2.2………........
103
49.
Gambar 4.17 Halaman Utama Emulator Android 2.2………………….
103
50.
Gambar 4.18 Memulai Aplikasi Dengan Mengklik Widget Aplikasi SPIHTforCompress…………………………………………………….
104
51.
Gambar 4.19 Tampilan Menu dan Klik Compress…………………….
104
52.
Gambar 4.20 Proses Kompresi Yang Terjadi Pada Perangkat Lunak Dapat Dilihat Pada Debug……………………………….……………...........
105
53.
Gambar 4.21 Matriks Hasil Kompresi Yang Ditampilkan……….……
106
54.
Gambar 4.22 File Hasil Kompresi Yang Terletak Pada sdcard Device Dan
55. 56.
Ukuran Datanya…………………………………………………..……
106
Gambar 4.23 Proses Upload Data Hasil Kompresi…………………….
107
Gambar 4.24 Directory Local Server Pada Perangkat Yang Diuji Coba Dengan Menggunakan Wamp Server Pada Localhost…………………
108
57.
Gambar 4.25 File Telah Berhasil Di Upload…………………………..
109
58.
Gambar 4.26 Properties Data Sebelum Dikompres……………………
110
Universitas Sumatera Utara
59.
Gambar 4.27 Properties Data Setelah Dikompres……………………..
111
60.
Gambar 4.28 Citra Sebelum Dikompres………………………………..
112
61.
Gambar 4.29 Citra Setelah Dikompres…………………………………
112
Universitas Sumatera Utara
DAFTAR TABEL 1.
Tabel 2.1 Beberapa Metode Kompresi Citra……………………….
37
2.
Tabel 3.1 Skala Keabuan……………………………………………
54
3.
Tabel 3.2 Perhitungan Sebuah Citra Digital…………………………
54
4.
Tabel 3.3 Hasil Pemampatan Sebuah Citra Digital…………………
57
5.
Tabel 3.4 Hasil Perbandingan Dari Ketiga Teknik Kompresi……….
83
Universitas Sumatera Utara
DAFTAR LAMPIRAN
Lampiran 1
Pembuatan Tampilan Antar Muka (Interface)
Lampiran 2
Pembuatan Kelas Utama SPIHT for Compres
Lampiran 3
Pembuatan Kelas Compress
Lampiran 4
Pembuatan Kelas Decompress
Lampiran 5
Pembuatan Kelas Download File
Lampiran 6
Pembuatan Kelas Upload
Lampiran 7
Pembuatan Kelas Uploader
Lampiran 8
Pembuatan Kelas Set Partitioning In Hierarchical Trees
Lampiran 9
Pembuatan Manifest Aplikasi
Universitas Sumatera Utara