BAB III KOMPRESI DATA MENGGUNAKAN SET PARTITIONING IN HIERARCHICAL TREES
3.1
Set Partitioning In Hierarchical Trees Metode kompresi lossy merupakan salah satu metode pemampatan citra yang
menghasilkan rasio pemampatan tinggi. Ukuran file citra menjadi lebih kecil tanpa menghilangkan
kualitas
citra
secara
signifikan.
Metode
kompresi
lossy
diimplementasikan pada kompresi citra Joint Picture Experts Group (JPEG) dengan menggunakan Discrete Cosine Transform (DCT) pada proses transformasinya. Metode kompresi lossy juga dapat diterapkan pada Discrete Wavelet Transform (DWT)[4]. Salah satu algoritma kompresi yang menggunakan DWT adalah Set Partitioning In Hierarchical Tress (SPIHT). Algoritma kompresi SPIHT merupakan salah satu algoritma yang mengkodekan koefisien hasil transformasi wavelet secara bertahap. Algoritma kompresi SPIHT bekerja dengan cara mengolah kesamaan turunan antar subband dalam dekomposisi wavelet pada citra. Perbedaan kualitas citra hasil rekonstruksi dengan citra asli tergantung dari jumlah bit yang diterima. Berdasarkan hasil uji coba yang dilakukan terhadap beberapa buah citra masukan dengan karakteristik tertentu, diperoleh kualitas citra hasil kompresi SPIHT yang lebih baik bila dibandingkan dengan kompresi JPEG. Kualitas citra hasil kompresi diamati berdasarkan nilai Peak Signal to Noise Ratio (PSNR) dan visual citra.
Universitas Sumatera Utara
Metode SPIHT merupakan metode dari perbaikan dari algoritma pengkodean EZW
(Embedded
Zero
Wavelet)
yang
dipresentasikan
oleh
J.
Shapiro
(Shapiro,1993). SPIHT pertama kali dipresentasikan oleh Said dan Pearlman. SPIHT mengasumsikan bahwa struktur dekomposisi adalah struktur bidang oktaf dan berdasarkan fakta sub-bidang pada level yang berbeda tetapi pada orientasi yang sama, akan memiliki karakteristik yang mirip seperti terlihat pada Gambar 3.1 SPIHT menggunakan hubungan orangtua-anak (parent-children) dalam struktur dekomposisi. Artinya masing-masing piksel gambar pada level di bawahnya dengan skala yang lebih besar. Hubungan orangtua-anak dalam ruang dua-dimensi adalah [5]: Orang tua = (x,y) Anak = [(2x,2y), (2x + 1, 2y), (2x, 2y + 1), (2x + 1,2y + 1)]
Gambar 3.1 Ilustrasi hubungan parent-child dari koefisien SPIHT
Universitas Sumatera Utara
Dengan menggunakan pola hubungan tersebut di atas, SPIHT membuat hipotesis bahwa jika koefisien orang tua berada di bawah nilai ambang tersebut. Jika perkiraan ini benar, maka SPIHT dapat melambangkan koefisien tersebut beserta seluruh anak hanya dengan satu symbol saja yang disebut zerotree. SPIHT terdiri atas dua tahap, yaitu tahap pensortiran (sorting pass) dan tahap penghalusan (refinement pass). Pada tahap penyortiran SPIHT berusaha untuk mengurutkan koefisien berdasarkan besarnya, kemudian dalam tahap penghalusan kuantisasi koefisien diperhalus. Kedua tahap tersebut didasarkan atas nilai ambang tertentu. Nilai ambang pertama kali ditentukan atas kriteria tertentu, kemudian dilanjutkan dengan nilai ambang yang semakin kecil. Pada Algorima SPIHT koefisien-koefisien diklasifikasikan kedalam tiga set, yaitu: 1. LIP (list of insignificant pixel) merupakan koordinat dari koefisien yang tidak signifikan berdasarkan threshold saat ini. 2. LSP (list of significant pixel) merupakan koordinat dari koefisien yang signifikan berdasarkan threshold saat ini. 3. LIS (list of insignificant sets) merupakan koordinat dari akar dengan subpohon yang tidak signifikan. Selama proses kompresi, set dari koeffisien pada LIS diperbaharui dan jika koefisien menjadi signifikan dipindahkan dari LIP ke LSP. Dengan demikian bitstream dapat diorganisasi secara progressif. Dengan cara yang sama set secara berurutan dievaluasi sesuai LIS, dan saat set yang ditemukan signifikan ia dihilangkan dari daftar dan dipartisi. Subset baru dengan lebih dari satu elemen
Universitas Sumatera Utara
ditambahkan kembali ke LIS, dengan set koordinat tunggal ditambahkan ke akhir LIP atau LSP, tergantung apakah mereka sigfikan atau tidak. Algoritma
pendekodean
SPIHT
menggunakan
metode
yang
sama
pengkodeannya, sehingga citra dapat direkonstruksi. Karena pada proses kompresi terjadi proses pemfilteran, maka citra hasil rekonstruksi akan mengalami distorsi. Distorsi dinyatakan dengan mean square error (MSE).
3.2 Metode Dari Algoritma Set Partitioning In Hierarchical Trees Berikut ini akan dijelaskan metode dari algoritma Set Partitioning In Hierarchical Trees: 1. Set koordinat yang akan digunakan untuk menyajikan metode pengkodean baru. a.O (i,j) : Set seluruh koordinat keturunan (offspring) node (i,j) ; anak saja. b.D (i,j) : Set seluruh koordinat keturunan (descendants) node (i,j) ; anak, cucu, yang paling besar, dan sebagainya. c.H (i,j) : Set seluruh koordinat dari tata ruang pohon ; orang tua. d.L (i,j) : D (i,j) – O (i,j) Seluruh keturunan (descendents) kecuali keturunan (offspring) ; cucu, yang paling besar, dan sebagainya.
2. Inisialisasi (3.1) LIP = Seluruh elemen di koordinat H LSP = Kosong LIS = Akar-akar dari D’s
Universitas Sumatera Utara
Keluaran n = [log2(max(i,j){|ci,j|}], set LSP dengan isi kosong, dan tambahkan koordinat (i,j) € H ke LIP, dan jika turunannya juga ke LIS dengan tipe A. 2. Sorting pass: 2.1. Untuk setiap entri (i,j) pada LIP: 2.1.1. Keluarkan Sn(i,j); (3.2)
2.1.2. jika Sn(i,j) = 1, pindahkan (i,j) ke LSP dan keluarkan tanda dari ci,j. 2.2. Untuk setiap entry (i,j) pada LIS: 2.2.1. Jika entri adalah tipe A: Keluarkan Sn(D(i,j)). Jika Sn(D(i,j)) = 1, maka: a. Untuk setiap (k,l) Є O(i,j): Keluarkan Sn(k,l). Jika Sn(k,l) = 1, tambahkan (k,l) ke LSP dan keluarkan tanda dari ck,l. Jika Sn(k,l) = 0, tambahkan (k,l) ke akhir dari LIP. b. Jika L(I,j) ≠ Ø, pindahkan (i,j) ke akhir dari LIS, dan bila entry tipe B, menuju ke langkah 2.2.1, jika tidak hilangkan entry (i,j) dari LIS. 2.2.2. Jika entri adalah tipe B: Keluarkan Sn(L(i,j)). Jika Sn(L(i,j)) = 1, maka:
Universitas Sumatera Utara
a) Tambahkan setiap (k,l) Є O(i,j) ke akhir dari LIS jika entri tipe A. b) Hilangkan (i,j) dari LIS. 3. Refinement Pass: untuk setiap entry (i,j) dalam LSP, kecuali yang termasuk pada sorting pass terakhir (pada n yang sama), keluarkan bit msb ke-n dari |ci,j|. 4. Update langkah kuantisasi: kurangi n dengan 1, lalu kembali ke langkah 2. Adapun diagram alir Metode Set Partitioning In Hierarchical Trees dapat dilihat pada Gambar 3.2
Gambar 3.2 Diagram Alir Metode Set Partitioning In Hierarchical Trees
Universitas Sumatera Utara
3.3 Kompresi Gambar Dengan Algoritma Set Partitioning In Hierarchical Trees Berikut ini contoh kompresi gambar menggunakan algoritma SPIHT (Set Partitioning In Hierarchical Trees) : 1. Kita misalkan suatu gambar dibagi menjadi beberapa blok seperti pada Gambar 3.2
Gambar 3.3 Kode Dari Suatu Encoder 2. Lakukan proses inisialisasi seperti terlihat pada Gambar 3.3
LIP
LSP
LIS
(0,0) 26 (0,1) 6 (1,0) -7 (1,1) 7
Kosong
(0,1)D {13, 10, 6, 4} (1,0)D {4, -4, 2, -2} (1,1)D {4, -3, -2, 0}
Gambar 3.4 Proses Inisialisasi Yang Pertama Kali Dilakukan
Universitas Sumatera Utara
Setelah berhasil melakukan proses inisialisasi yang pertama kali dilakukan, didapat hasil setelah sorting pass tahap pertama, maka pada ambang batas
dapat
dilihat pada Gambar 3.5
LIP (0,1) 6 (1,0) -7 (1,1) 7
LSP Kosong (perbaikan tidak diperlukan) -------------------
LIS (0,1)D {13, 10, 6, 4} (1,0)D {4, -4, 2, -2} (1,1)D {4, -3, -2, 0}
(0,0) 26
11 Sig./+
000 Insig.
000 Seluruh D set Tidak Signifikan
Gambar 3.5 Proses Inisialisasi Setelah Sorting Pass Tahap Pertama Dari Gambar 3.5 di atas dapat dilihat koefisien (0,0) 26 yang sebelumnya terletak di bagan LIP pindah ke bagan LSP setelah sorting pass tahap pertama dilakukan.
3. Setelah proses inisialisasi sorting pass tahap pertama, maka didapatkan proses perbaikan seperti terlihat pada Gambar 3.6
Universitas Sumatera Utara
LIP
LSP
LIS
(0,1) 6 (1,0) -7 (1,1) 7
(0,0) 26
(0,1)D {13,10, 6, 4} (1,0)D {4, -4, 2, -2} (1,1)D {4, -3, -2, 0}
Gambar 3.6 Proses Perbaikan Tahap Pertama Dari Gambar 3.6 di atas dapat dilihat koefisien (0,1) D {13, 10, 6, 4} yang ada di bagian LIS merupakan koefisien yang signifikan.
4. Setelah proses perbaikan tahap pertama, lakukan sorting pass tahap kedua, dimana ambang batasnya
seperti terlihat pada Gambar 3.7
LIP
LSP
LIS
(0,1) 6 (1,0) -7 (1,1) 7
(0,0) 26 -------------------
(0,1)D {13,10, 6, 4}
(1,2) 6 (1,3) 4
(0,2) 13 (0,3) 10
(1,0)D {4, -4, 2, -2} (1,1)D {4, -3, -2, 0}
Pixels Yg Signifikan 000 Tidak Signifikan
(0,1) D
{13,10
{6, 4 } 1 11 11 0 0
Pixels Yang Tidak Signifikan Gambar 3.7 Proses Tahapan Sorting Pass Yang Kedua
Universitas Sumatera Utara
Dari Gambar 3.7 dapat dilihat bahwa dari bagian LIS dimana koefisien (0,1) D {13, 10, 6, 4} dibagi menuju dua bagian lainnya yaitu pada bagian LSP yang merupakan pixels yang signifikan yaitu {13, 10 } dan pada bagian LIP yang merupakan pixels yang tidak signifikan yaitu {6, 4 }.
5. Setelah kita melakukan tahap sorting pass yang kedua, lihat hasil dari tahapan sorting pass yang kedua seperti pada Gambar 3.8
LIP
LSP
LIS
(0,1) 6 (1,0) -7 (1,1) 7 (1,2) 6 (1,3) 4
(0,0) 26 ------------------(0,2) 13 (0,3) 10
(1,0)D {4, -4, 2, -2} (1,1)D {4, -3, -2, 0}
Kita Rapatkan Nilai 26 menjadi 1 = (dalam bentuk bit)
Gambar 3.8 Hasil Dari Tahapan Sorting Pass Yang Kedua
Dari Gambar 3.8 di atas, dapat dilihat pada bagian LSP koefisien (0,0) 26 dirapatkan nilainya menjadi 1 dimana nilainya diubah menjadi bit – bit yaitu 1110102.
Universitas Sumatera Utara
6. Setelah melihat hasil dari tahapan sorting pass yang kedua, maka langkah selanjutnya adalah melakukan sorting pass tahap ketiga, dimana ambang batasnya seperti terlihat pada Gambar 3.9
LIP
LSP
LIS
(0,1) 6 (1,0) -7 (1,1) 7 (1,2) 6 (1,3) 4
(0,0) 26 (0,2) 13 (0,3) 10
(1,0)D {4, -4, 2, -2} (1,1)D {4, -3, -2, 0}
(3,0) 2 (3,1) -2 (2,3) -3 (3,2) -2 (3,3) 0
Signif.
(0,1) 6 (1,0) -7 (1,1) 7 (1,2) 6 (1,3) 4
Kedua set signifikan
(2,0) 4 (2,1) -4 (2,2) 4 (1,0) D
{4, -4,
(1,1) D
{4
Gambar 3.9 Proses Tahapan Sorting Pass Yang Ketiga
Dari Gambar 3.9 dapat dilihat bahwa pada bagian LIS, koefisien (1,0) D {4, -4, 2, -2} dan koefisien (1,1) D {4, -3, -2, 0} keduanya merupakan pixel–pixel yang signifikan dimana nilai-nilai yang dhasilkan dipecah lagi menuju
Universitas Sumatera Utara
2, -2}
-3, -2, 0}
dua bagian lainnya, yaitu bagian LSP dan LIP. Nilai koefisien (1,0)D {4, -4} dan nilai (1,1)D {4}dipindahkan (disorting) ke bagian LSP. Sedangkan Nilai koefisien (1,0)D {2, -2}dan nilai (1,1)D {-3, -2, 0} dipindahkan (disorting) ke bagian LIP.
7. Setelah melihat tahapan sorting pass yang ketiga, langkah terakhir pada tahapan pensortiran seperti terlihat pada Gambar 3.10 dimana ambang batasnya
LIP
LSP
LIS
(3,0) 2 (3,1) -2 (2,3) -3 (3,2) -2 (3,3) 0
(0,0) 26 (0,0) 13 (0,0) 10
KOSONG
(0,0) 6 (0,0) -7 (1,1) 7 (1,2) 6 (1,3) 4 (2,0) 4 (2,1) -4 (2,2) 4
Gambar 3.10 Langkah Terakhir Pada Tahapan Sorting Pass
Dari Gambar 3.10 di atas dapat dilihat pada bagian LIS nilai koefisiennya sama sekali tidak ada (kosong). Sebelumnya pada tahapan awal bagian LSP lah yang
Universitas Sumatera Utara
tidak ada nilai koefisiennya. Jadi dapat disimpulkan bahwa pixel-pixel tadi berpindah tempat dan dipadatkan di bagian LIP.
3.4 Perbandingan Hasil Kompresi Setelah membahas teknik kompresi menggunakan algoritma Set Partitioning In Hierarchical Trees, pada bagian ini Algoritma Set Partitioning In Hierarchical Trees akan dibandingkan dengan Algoritma lain yang telah diteliti sebelumnya. Tujuan membandingkan Algoritma yang satu dengan lainnya ialah agar diketahui kekurangan atau kelebihan, bagus atau tidaknya Algoritma yang digunakan. Adapun Algoritma pembanding yang akan digunakan ialah Algoritma Huffman Code dan Algoritma Discrete Cosine Transform (DCT).
a.Algoritma Huffman Code 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 [6]: 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
Universitas Sumatera Utara
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 : 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.
Gambar 3.11 Pohon Biner Huffman Code
d. Mengganti data yang ada dengan kode bit berdasarkan pohon biner yang dibuat.
Universitas Sumatera Utara
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. Contoh Studi Kasus Metode Pemampatan Huffman Metode pemampatan Huffman menggunakan prinsip bahwa nilai (atau derajat) keabuan yang sering muncul di dalam citra akan dikodekan dengan jumlah bit yang lebih sedikit sedangkan nilai keabuan yang frekuensi kemunculannya sedikit dikodekan dengan jumlah bit yang lebih panjang, seperti terlihat pada tabel 3.1 :
Skala Keabuan
Rentang Nilai Keabuan
Pixel Depth
Universitas Sumatera Utara
21 ( 2 nilai ) 23 ( 8 nilai ) 28 ( 256 nilai)
0, 1 0 sampai 7 0 sampai 255 Tabel 3.1 Skala Keabuan
1 bit 3 bit 8 bit
Contoh soal : Terdapat citra digital berukuran 64 x 64 dengan 8 derajat keabuan (k) dan jumlah seluruh pixel (n) = 64 x 64 = 4096, seperti terlihat pada Tabel 3.2 dibawah ini.
K 0 1 2 3 4 5 6 7
P(k) = nk/n 0.19 0.25 0.21 0.16 0.08 0.06 0.03 0.02
nk 790 1023 850 656 329 245 122 81
Tabel 3.2 Perhitungan Sebuah Citra Digital Adapun Pohon Huffman dapat dilihat pada gambar 3.12 dibawah ini : 1. 2.
7 : 0.02
4 : 0.08
5 : 0.06
5 : 0.06
76 : 0.05 7 : 0.02
3.
6 : 0.03
4 : 0.08
3 : 0.16
3 : 0.16
0 : 0.19
0 : 0.19
2 : 0.21
2 : 0.21
1 : 0.25
1 : 0.25
6 : 0.03
4 : 0.08
765 : 0.11
76 : 0.05 7 : 0.02
3 : 0.16
0 : 0.19
2 : 0.21
1 : 0.25
5 : 0.06
6 : 0.03
Universitas Sumatera Utara
4.
3 : 0.16
4765 : 0.19 4 : 0.08
7 : 0.02
0 : 0.19
2 : 0.21
1 : 0.25
765 : 0.11 5 : 0.06
76 : 0.05
5.
0 : 0.19
6 : 0.03
2 : 0.21
1 : 0.25
34765 : 0.35
3 : 0.16
4765 : 0.19 4 : 0.08
765 : 0.11 5 : 0.06
76 : 0.05 6 : 0.03
7 : 0.02
6.
1 : 0.25
02 : 0.40
0 : 0.19
2 : 0.21
34765 : 0.35
3 : 0.16
4765 : 0.19 4 : 0.08
765 : 0.11 5 : 0.06
76 : 0.05
7 : 0.02
7.
02 : 0.40
0 : 0.19
6 : 0.03
134765 : 0.60
2 : 0.21
1 : 0.25
34765 : 0.35
3 : 0.16
4765 : 0.19 4 : 0.08
765 : 0.11 76 : 0.05
7 : 0.02
5 : 0.06
6 : 0.03
Universitas Sumatera Utara
8.
02134765 : 1.00
134765 : 0.60
02 : 0.40
0 : 0.19
1 : 0.25
2 : 0.21
34765 : 0.35
3 : 0.16
4765 : 0.19 4 : 0.08
765 : 0.11 76 : 0.05
7 : 0.02
5 : 0.06
6 : 0.03
Gambar 3.12 Pohon Huffman Pada pohon Huffman, a. Setiap simpul di dalam pohon berisi pasangan nilai a, b yang di dalam hal ini a menyatakan nilai keabuan dan b menyatakan peluang kemunculan nilai keabuan tersebut di dalam citra. b. Gabung dua buah pohon yang memiliki frekuensi kemunculan paling kecil pada sebuah akar. Akar mempunyai frekuensi yang merupakan jumlah dari frekuensi dua buah pohon penyusunnya. c. Ulangi sampai tersisa hanya satu pohon saja. d. Beri label setiap sisi pada pohon biner. Sisi kiri dilabeli dengan 0 dan sisi kanan dilabeli dengan 1. Sehingga dari pohon Huffman tersebut kita memperoleh kode untuk setiap derajat keabuan sebagai berikut : Ukuran citra sebelum dimampatkan ( 1 derajat keabuan = 3 bit) adalah 4096 × 3 bit = 12288 bit Adapun hasil pemampatan sebuah citra digital dapat
dilihat pada Tabel 3.3.
Universitas Sumatera Utara
∑ bit
Hasil Pemampatan 0 00 2 bit 790 1580 1 10 2 bit 1023 2046 2 01 2 bit 850 1700 3 110 3 bit 656 1968 4 1110 4 bit 329 1316 5 11111 5 bit 245 1225 6 111101 6 bit 122 732 7 111100 6 bit 81 486 Ukuran citra setelah dimampatkan 11053 bit K
Code
nk
Tabel 3.3 Hasil Pemampatan Sebuah Citra Digital Dari hasil pemampatan, kita bisa mencari prosentase pemampatan : Nisbah pemampatan = (100 % -
11053 × 100 % ) = 10 % 12288
Artinya 10 % citra semula telah dimampatkan.
Universitas Sumatera Utara
Gambar 3.13 Citra Sebelum Dikompres
Gambar 3.14 Citra Setelah Dikompres Berdasarkan hasil pengujian dengan menggunakan gambar yang sama, dapat dihitung rasio kompresi dengan menggunakan persamaan (2.8) Rasio = 100% - (Hasil Kompresi/Citra Asli x 100%) Maka dapat dihitung
Universitas Sumatera Utara
Ukuran citra sebelum dikompres = 69,5 kB Ukuran citra setelah dikompres = 62,9 kB Rasio Pemampatan = 100% - (62,9 kB/69,5 kB x 100%) = 100% - 90% = 10% Artinya, 10% dari data semula telah dimampatkan. Waktu yang dibutuhkan untuk melakukan kompresi data pada gambar berukuran 69,5 kB adalah 64 detik. b. Algoritma Discrete Cosine Transform (DCT) Discrete Cosine Transform adalah sebuah teknik untuk mengubah sebuah sinyal
kedalam
komponen
frekuensi
dasar.
Discrete
Cosine
Transform merepresentasikan sebuah citra dari penjumlahan sinusoida dari magnitude dan frekuensi yang berubah-ubah. Sifat dari DCT adalah mengubah informasi citra yang signifkan dikonsentrasikan hanya pada beberapa koefisien DCT[7]. Discrete Cosine Transform berhubungan erat dengan Discrete Fourier Transform (FFT) dan, sehingga menjadikan data direpresentasikan dalam komponen frekuensinya. Demikian pula, dalam aplikasi pemrosesan gambar, DCT dua dimensi (2D) memetakan sebuah gambar atau sebuah segmen gambar kedalam komponen frekuensi 2D (dua dimensi nya). Discrete Cosine Transform adalah sebuah skema lossy compression dimana N x N blok di transformasikan dari domain spasial ke domain DCT. DCT menyusun sinyal tersebut ke frekuensi spasial yang disebut dengan koefisien DCT. Frekuensi
Universitas Sumatera Utara
koefisien DCT yang lebih rendah muncul pada kiri atas dari sebuah matriks DCT, dan frekuensi koefisien DCT yang lebih tinggi berada pada kanan bawah dari matriks DCT. Sistem penglihatan manusia tidak begitu sensitive dengan error-error yang ada pada frekuensi tinggi dibanding dengan yang ada pada frekuensi rendah. Karena itu, maka frekuensi yang lebih tinggi tersebut dapat dikuantisasi. Kelebihan kompresi data menggunakan Discrete Cosine Transform adalah : 1. DCT menghitung kuantitas bit-bit data gambar dimana pesan tersebut
disembunyikan didalamnya. Walaupun gambar yang dikompresi dengan lossy compression akan menimbulkan kecurigaan karena perubahan gambar terlihat jelas, pada metode ini hal ini tidak akan terjadi karena metode ini terjadi di domain frekuensi di dalam image, bukan pada domain spasial, sehingga tidak akan ada perubahan yang terlihat pada cover gambar. 2. Kokoh terhadap manipulasi pada stego-object.
Kekurangan kompresi data menggunakan Discrete Cosine Transform adalah: 1. Tidak tahan terhadap perubahan suatu objek dikarenakan pesan mudah dihapus karena lokasi penyisipan data dan pembuatan data dengan metode DCT diketahui.
2. Implementasi algoritma yang panjang dan membutuhkan banyak perhitungan. Discrete Cosine Transform Satu Dimensi (1-D DCT) Discrete Cosine Transform dari sederet n bilangan real C(x), x = 0, ... ,n-1, dirumuskan sebagai berikut[2]. C(u)
= Untuk u = 0, 1, 2, …., N-1
(3.3)
Universitas Sumatera Utara
Dengan cara yang sama, DCT balik dapat didefinisikan sebagai berikut. F (x) = Untuk u = 0, 1, 2, …., N-1
(3.4)
Dengan α(u) dinyatakan sebagai berikut. α (u)
=
untuk u = 0 1
untuk u
0
(3.5)
Bilangan yang dihasilkan melalui transformasi DCT tidak mengandung unsur imajiner. DCT dari contoh citra 1 dimensi f (x) = (3, 4, 4, 5) adalah sebagai berikut[2]: C(0)
= =
(f (0) + f (1) + f (2) + f (3))
=
(3 + 4 + 4 + 5)
= C(1)
=
=
(3(0.92) + 4(0.38) + 4 (-0.38) + 5(-0.92))
=
(-1.84)
= C(2)
8
-0.76
=
Universitas Sumatera Utara
= = C(3)
(3(0.71) + 4(-0.71) + 4 (-0.71) + 5(0.71)) 0
=
= =
(3(0.38) + 4(-0.92) + 4 (0.92) + 5(-0.38)) -0.76
Jadi citra f (x) = (3, 4, 4, 5) setelah mengalami transformasi kosinus 1 D menjadi C(u) = (8, 0.76, 0, -0.76). Fungsi basis (kernel) transformasi kosinus diskrit 1 D adalah : g (x, u) =
(3.6)
Untuk u = 0, 1, 2, …, N-1, dan x = 0, 1, 2, …, N-1, Nilai kernel dari DCT juga berada dalam interval -1 sampai 1. Setiap element dari hasil transformasi C(u) merupakan hasil dot product atau inner product dari masukan f(x) dan basis vektor. Faktor konstanta dipilih sedemikian rupa sehingga basis vektornya orthogonal dan ternormalisasi. DCT juga dapat diperoleh dari produk vektor (masukan) dan n x n matriks orthogonal yang setiap barisnya merupakan basis vektor. Delapan basis vektor untuk n = 8 dapat dilihat pada gambar. Setiap basis vektor berkorespondensi dengan kurva sinusoid frekuensi tertentu.
Universitas Sumatera Utara
Gambar 3.15 Grafik Fungsi Basis 1-D DCT Discrete Cosine Transform 2 Dimensi (2D-DCT) DCT dimensi satu berguna untuk mengolah sinyal-sinyal dimensi satu seperti bentuk gelombang suara. Sedangkan untuk citra yang merupakan sinyal dua dimensi, diperlukan versi dua dimensi dari DCT . Untuk sebuah matriks n x m, 2-D DCT dapat dihitung dengan cara 1-D DCT diterapkan pada setiap baris dari C dan kemudian hasilnya dihitung DCT untuk setiap kolomnya.
Rumus transformasi 2-D DCT untuk C adalah sebagai berikut : C(u, v) = dengan u = 0, 1, 2, …, N-1, dan v = 0, 1, 2, …, M-1, sedangkan
(3.7)
Universitas Sumatera Utara
α (k)
=
untuk k = 0 1
untuk k
0
(3.8)
Rumus 2-D DCT diatas sering juga disebut sebagai forward discrete cosine transform (FDCT). 2-D DCT dapat dihitung dengan menerapkan transformasi 1-D secara terpisah pada baris dan kolomnya, sehingga dapat dikatakan bahwa 2-D DCT separable dalam dua dimensi. Seperti pada kasus satu-dimensi, setiap elemen C(u,v) dari transformasi merupakan inner product dari masukan dan basis fungsinya, dalam kasus ini, basis fungsinya adalah matriks n x m. Setiap dua-dimensi basis matriks merupakan outer product dari dua basis vektor satu-dimensinya. Setiap basis matriks dikarakterisasikan oleh frekuensi spasial horizontal dan vertikal. Frekuensi horizontal meningkat dari kiri ke kanan, dan dari atas ke bawah secara vertikal. Dalam konteks citra, hal ini menunjukkan tingkat signifikansi secara perseptual, artinya basis fungsi dengan frekuensi rendah memiliki sumbangan yang lebih besar bagi perubahan penampakan citra dibandingkan basis fungsi yang memiliki frekuensi tinggi. Nilai konstanta basis fungsi yang terletak di bagian kiri atas sering disebut sebagai basis fungsi DC, dan DCT koefisien yang bersesuaian dengannya disebut sebagai koefisien DC (DC coefficient)[1].
Universitas Sumatera Utara
Gambar 3.16 Grafik Fungsi Basic 2-D DCT Invers discrete cosine transform dimensi dua (2-D IDCT) dapat diperoleh dengan rumus berikut ini : f (x, y) = dengan x = 0, 1, 2, …, N-1, dan y = 0, 1, 2, …, M-1
(3.9)
Fungsi basis DCT 2 dimensi adalah : C (x, y, u, v) = Dengan nilai u dan x = 0, 1, 2, …, N-1, sedangkan v dan y = 0, 1, 2, …, M-1 (3.10) Kompresi Gambar DCT bekerja dengan memisahkan gambar ke bagian frekuensi yang berbeda. Selama langkah kuantisasi disebut, di mana bagian dari kompresi sebenarnya terjadi, frekuensi yang kurang penting dibuang. Kemudian, hanya frekuensi yang paling
Universitas Sumatera Utara
penting yang tetap digunakan mengambil gambar dalam proses dekompresi. Akibatnya, gambar direkonstruksi mengandung beberapa distorsi.
Gambar 3.17 Komponen dari Sistem Transmisi Data Gambar atau Video Berikut adalah algoritma discrete cosine transform: 1. Gambar dibagi menjadi beberapa blok, dan masing-masing blok memiliki 8 pixel x 8 pixel.
Original
=
5
176
193
168
168
170
167
165
6
176
158
172
162
177
168
151
5
167
172
232
158
61
145
214
33
179
169
179
5
5
135
158
8
104
180
128
172
197
189
169
63
5
102
101
160
142
133
130
51
47
63
5
180
191
165
5
49
53
43
5
184
170
168
74
Universitas Sumatera Utara
2. Data Matriks original dikurangi dengan 128 karena algoritma DCT bekerja pada rentang -128 sampai 127 sesuai dengan ketentuan pengolahan citra digital pada citra berwarna.
Original
M
=
5
176
193
168
168
170
167
165
6
176
158
172
162
177
168
151
5
167
172
232
158
61
145
214
33
179
169
179
5
5
135
158
8
104
180
128
172
197
189
169
63
5
102
101
160
142
133
130
51
47
63
5
180
191
165
5
49
53
43
5
184
170
168
74
122
49
66
41
41
43
40
38
-121
49
31
45
35
50
41
24
-122
40
45
105
31
-66
18
87
-94
52
42
47
-122
-122
8
51
-119
-23
53
51
45
70
61
42
-64
-112
-25
-26
33
15
6
12
-76
-80
-64
-122
53
64
38
-122
-78
-74
-84
-122
57
43
41
-53
=
Universitas Sumatera Utara
M
=
x00
x01
x02
x03
x04
x05
x06
x07
x10
x11
x12
x13
x14
x15
x16
x17
x20
x21
x22
x23
x24
x25
x26
x27
x30
x31
x32
x33
x34
x35
x36
x37
x40
x41
x42
x43
x44
x45
x46
x47
x50
x51
x52
x53
x54
x55
x56
x57
x60
x61
x62
x63
x64
x65
x66
x67
x70
x71
x72
x73
x74
x75
x76
x77
3. Buat dan cari nilai untuk matriks Discrete Cosine Transform untuk matriks T dan buat matriks transpose nya untuk matriks T t
if i = 0 T (i, j) =
if i
0 (3.11)
Maka dengan menggunakan rumusan matriks diatas dapat dihitung nilai matriks T mulai dari T (0,0) sampai T (7,7) T (0,0) =
=
= 0.3536
Universitas Sumatera Utara
T (0,1) =
=
= 0.3536
T (0,2) =
=
= 0.3536
T (0.3) =
=
= 0.3536
T (0.4) =
=
= 0.3536
T (0.5) =
=
= 0.3536
T (0.6) =
=
= 0.3536
T (0.7) =
=
= 0.3536
T (1,0) =
=
= 0.4904
T (1.1) =
=
= 0.4157
T (1.2) =
=
= 0.2778
T (1.3) =
=
= 0.0975
T (1.4) =
=
= -0.0975
T (1.5) =
=
= -0.2778
T (1.6) =
=
= -0.4157
T (1.7) =
=
= -0.4904
T (2.0) =
=
= 0.4619
T (2.1) =
=
= 0.1913
T (2.2) =
=
= -0.1913
Universitas Sumatera Utara
T (2.3) =
=
= -0.4619
T (2.4) =
=
= -0.4619
T (2.5) =
=
= -0.1913
T (2.6) =
=
= 0.1913
T (2.7) =
=
= 0.4619
T (3.0) =
=
= 0.4157
T (3.1) =
=
= -0.0975
T (3.2) =
=
= -0.4904
T (3.3) =
=
= -0.2778
T (3.4) =
=
= 0.2778
T (3.5) =
=
= 0.4904
T (3.6) =
=
= 0.0975
T (3.7) =
=
= -0.4157
T (4.0) =
=
= 0.3536
T (4.1) =
=
= -0.3536
T (4.2) =
=
= -0.3536
T (4.3) =
=
= 0.3536
T (4.4) =
=
= 0.3536
Universitas Sumatera Utara
T (4.5) =
=
= -0.3536
T (4.6) =
=
= -0.3536
T (4.7) =
=
= 0.3536
T (5.0) =
=
= 0.2778
T (5.1) =
=
= -0.4904
T (5.2) =
=
= 0.0975
T (5.3) =
=
= 0.4157
T (5.4) =
=
= -0.4157
T (5.5) =
=
= -0.0975
T (5.6) =
=
= 0.4904
T (5.7) =
=
= -0.4904
T (6.0) =
=
= 0.1913
T (6.1) =
=
= -0.4619
T (6.2) =
=
= 0.4619
T (6.3) =
=
= -0.1913
T (6.4) =
=
= -0.1913
T (6.5) =
=
= 0.4619
T (6.6) =
=
= -0.4619
Universitas Sumatera Utara
T (6.7) =
=
= 0.1913
T (7.0) =
=
= 0.0975
T (7.1) =
=
= -0.2778
T (7.2) =
=
= 0.4157
T (7.3) =
=
= -0.4904
T (7.4) =
=
= 0.4904
T (7.5) =
=
= -0.4157
T (7.6) =
=
= 0.2778
T (7.7) =
=
= -0.0975
Maka dari perhitungan diatas didapatkan nilai untuk matriks T dan matriks transpose T adalah sebagai berikut
T=
0.3536
0.3536
0.3536
0.3536
0.3536
0.3536
0.3536
0.3536
0.4904
0.4157
0.2778
0.0975 -0.0975 -0.2778 -0.4157 -0.4904
0.4619
0.1919 -0.1913 -0.4619 -0.4619 -0.1913 0.1913
0.4619
0.4157 -0.0975 -0.4904 -0.2778
0.2778
0.4904 0.0975 -0.4157
0.3536 -0.3536 -0.3536
0.3536
0.3536 -0.3536 -0.3536
-0.2778 -0.4904
0.0975
0.4157 -0.4157 -0.0975 -0.4904 -0.2778
0.1913 -0.4619
0.4619 -0.1913 -0.1913
0.0975 -0.2778
0.4157 -0.4904
0.4619 -0.4619
0.3536
0.1913
0.4904 -0.4157 0.2778 -0.0975
Universitas Sumatera Utara
T t=
0.3536
0.4904
0.4619
0.4157
0.3536
0.4157
0.1919 -0.0975 -0.3536 -0.4904 -0.4619 -0.2778
0.3536
0.2778 -0.1913 -0.4904 -0.3536
0.0975
0.3536
0.0975 -0.4619 -0.2778 0.3536
0.4157
0.3536 -0.0975 -0.4619 0.2778
0.3536
0.2778
0.1913
0.4619
0.3536 -0.2778 -0.1913 0.4904 -0.3536 -0.0975 0.1913
0.3536 -0.4904
0.4619 -0.4157 0.3536 -0.2778
0.4157
-0.1912 -0.4904
0.3536 -0.4157
0.3536 -0.4157
0.0975
0.0975 -0.3536 -0.4904
-0.1913
0.4904
0.4619 -0.4157 -0.4619
0.2778
0.1913 -0.0975
4. Dengan menggunakan persamaan Discrete Cosine Transform, cari matriks D dimana matriks D akan digunakan untuk kuantisasi lanjutan. D = T.Z Dimana Z = M . T t (3.12)
M
=
x00
x01
x02
x03
x04
x05
x06
x07
x10
x11
x12
x13
x14
x15
x16
x17
x20
x21
x22
x23
x24
x25
x26
x27
x30
x31
x32
x33
x34
x35
x36
x37
x40
x41
x42
x43
x44
x45
x46
x47
x50
x51
x52
x53
x54
x55
x56
x57
x60
x61
x62
x63
x64
x65
x66
x67
x70
x71
x72
x73
x74
x75
x76
x77
Universitas Sumatera Utara
Z(k.0) =
0.3536 (xk0 + xk1 + xk2 + xk3 + xk4 + xk5 + xk6 + xk7)
Z(k.1) =
0.4904(xk0-xk7)
+
0.4157(xk1+xk6)
+
0.2778(xk2-xk5)
+
+
0.1919(xk1+xk6)
–
0.1913(xk2+xk5)
–
0.0975(xk3-xk4) Z(k.2) =
0.4619(xk0+xk7) 0.4619(xk3+xk4)
Z(k.3) =
0.4157(xk0-xk7) – 0.0975(xk1-xk6) - 0.4904(xk2-xk5) – 0.2778 (xk3xk4)
Z(k.4) =
0.3536(xk0+xk7) – 0.3536(xk1+xk6) – 0.3536 (xk2+xk5) + 0.3536(xk3+xk4)
Z(k.5) =
0.2778(xk0-xk7) – 0.4904(xk1-xk6) + 0.0975(xk2-xk5) + 0.4157(xk3xk4)
Z(k.6) =
0.1913(xk0+xk7) – 0.4619(xk1+xk6) + 0.0975(xk2+xk5) – 0.1912(xk3+xk4)
Z(k.7) =
0.0975(xk0-xk7) – 0.2778(xk1-xk6) + 0.4157(xk2-xk5) – 0.4904(xk3xk4)
Dimana k = 0, 1, 2, …., 7 (3.13)
Universitas Sumatera Utara
Z=
Z
69.30
-35.07
-80.44
-78.66
-70.72
-46.61
-62.23 -8.53
54.45
-38.97
-79.98
-54.017
-66.47
-41.89
-67.52 -29.16
48.79
-40.33
-63.83
-164.01
22.63
-27.26
-61.53 -16.63
-48.79
15.87
18.92
-191.94
-34.65
24.38
-58.07 -41.06
45.96
-72.17
-73.05
-38.17
-67.89
-23.48
-11.49
-60.45
-102.35 -62.61
16.89
1.06
-21.86
-109.26
-11.96
-67.64
142.01
-79.56
-14.58
-5.28
69.87
-95.472
-78.71
-28.97
112.82
-43.13
-37.34
-1.38
64.49
=
22.14
54.46 40.45
z0,0
z0,1
z0,2
z0,3
z0,4
z0,5
z0,6
z0,7
z1,0
z1,1
z1,2
z1,3
z1,4
z1,5
z1,6
z1,7
z2,0
z2,1
z2,2
z2,3
z2,4
z2,5
z2,6
z2,7
z3,0
z3,1
z3,2
z3,3
z3,4
z3,5
z3,6
z3,7
z4,0
z4,1
z4,2
z4,3
z4,4
z4,5
z4,6
z4,7
z5,0
z5,1
z5,2
z5,3
z5,4
z5,5
z5,6
z5,7
z6,0
z6,1
z6,2
z6,3
z6,4
z6,5
z6,6
z6,7
z7,0
z7,1
z7,2
z7,3
z7,4
z7,5
z7,6
z7,7
Universitas Sumatera Utara
D=TZ D (0.k)
= 0.3536 (z0k + z1k + z2k + z3k + z4k = z5k + z6k + z7k)
D (1.k)
= 0.4904 (z0k-z7k) + 0.4157 (z1k-z6k) + 0.2778 (z2k-z5k) + 0.0975 (z3k-z4k)
D (2.k)
= 0.4619 (z0k+z7k) + 0.1919 (z1k+z6k) – 0.1913 (z2k-z5k) – 0.4619 (z3k-z4k)
D (3.k)
= 0.4157 (z0k-z7k) – 0.0975 (z1k-z6k) – 0.4904 (z2k-z5k) – 0.2778 (z3k-z4k)
D (4.k)
= 0.3536 (z0k+z7k) – 0.3536 (z1k+z6k) – 0.3536 (z2k+z5k) + 0.3536 (z3k+z4k)
D (5.k)
= -0.2778 (z0k-z7k) – 0.4904 (z1k-z6k) + 0.0975 (z2k-z5k) + 0.4157 (z3k-z4k)
D (6.k)
= 0.1913 (z0k+z7k) – 0.4619 (z1k+z6k) + 0.4619 (z2k+z5k) – 0.1913 (z3k+z4k)
D (7.k)
= 0.0975 (z0k-z7k) – 0.2778 (z1k-z6k) + 0.4157 (z2k-z5k) – 0.4904 (z3k-z4k) (3.14)
1. Matriks D sekarang berisi dengan koefisien DCT, dimana data yang terletak pada kiri atas merupakan korelasi dari frekuensi - frekuensi rendah dari data original. Sedangkan yang terletak pada kanan bawah merupakan korelasi dari frekuensi – frekuensi tinggi dari data original. Setelah itu lakukan proses kuantisasi dengan Quality level 50.
Universitas Sumatera Utara
D =
-27.5
-213.5
-149.6
-95.28
-103.75
-46.99
-58.71 27.3
168.22
51.61
-21.54
-239.52
-8.23
-24.49
-52.65 -96.62
-27.19
-31.23
-32.27
173.38
-51.14
-56.94
4.002 49.143
30.184 -43.07
-50.47
67.13
-14.11
11.13
71.01 18.03
19.5
8.46
33.58
-53.11
-36.75
2.91
-5.79 18.38
-70.59
66.87
47.44
-32.61
-8.19
18.13
-22.99
12.07
-19.12
6.25
-55.15
85.58
-0.603
8.02
71.15
-38.37
-75.92
29.29
-16.45
-23.43
-4.21 15.62
Q50 =
6.63 11.21
16
11
10
16
24
40
51
61
12
12
14
19
26
58
60
55
14
13
16
24
40
57
69
56
14
17
22
29
51
87
80
62
18
22
37
56
68
109
103
77
24
35
55
64
81
104
113
92
49
64
78
87
103
121
120
101
72
92
95
98
112
100
103
99
Persamaan matriks kuantisasi adalah sebagai berikut, dimana round berarti mendekatkan nilai hasil pembagian ke pembulatan bilangan integer terdekat Cij =
round
(3.15)
Universitas Sumatera Utara
C
=
-2
-19
-15
-6
-4
-1
-1
0
14
4
-2
-13
0
0
-1
-2
-2
-2
-2
7
-1
-1
0
1
2
-3
-2
2
0
0
1
0
1
0
1
-1
-1
0
0
0
-3
2
1
-1
0
0
0
0
0
0
0
-1
1
0
0
0
1
0
-1
0
0
0
0
0
2. Susun bilangan menggunakan fungsi zig zag scanning dimana ini merupakan langkah terakhir pada proses kompresi.
Gambar 3.18 Metode Zig Zag Scanning Matriks C yang terkuantisasi sekarang akan dikonversi oleh encoder ke data biner (01101011 ...) Koefisien DCT terkuantisasi mengatur sehingga bit yang paring kiri berisikan nilai-nilai yang tidak 0, dan yang paling kanan bersikan bit yang
Universitas Sumatera Utara
bernilai 0. Setelah nanti terurut, maka proses kompresi dapat dilakukan (termasuk dengan algoritma Huffman)
3. Proses dekompresi dimana ini merupakan proses untuk menrekonstruksikan data hasil kompresi menjadi data yang dapat dikenali. Persamaan matriks R adalah sebagai berikut: R i, j = Q i, j x C i, j (3.16)
R
=
160
44
20
80
24
0
0
0
36
108
14
38
26
0
0
0
-98
-65
16
-48
-40
0
0
0
-42
-85
0
-29
0
0
0
0
-36
22
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Untuk proses dekompresi,merupakan pembalikan dari proses kompresi dimana persamaan untuk proses dekompresi adalah sebbagai berikut N = round (T’ RT) + 128
(3.14)
Universitas Sumatera Utara
N
=
0
172
198
190
149
159
149
179
17
166
131
175
168
195
192
140
12
167
177
255
140
39
123
203
22
178
170
145
1
28
146
187
11
103
183
190
160
207
189
155
60
9
80
103
157
144
115
156
60
48
67
11
176
196
139
19
49
58
47
0
190
168
176
60
Universitas Sumatera Utara
Gambar 3.19 Citra Sebelum Dikompres
Gambar 3.20 Citra Setelah Dikompres Berdasarkan hasil pengujian dengan menggunakan gambar yang sama, dapat dihitung rasio kompresi dengan menggunakan persamaan (2.8) Rasio = 100% - (Hasil Kompresi/Citra Asli x 100%) Maka dapat dihitung
Universitas Sumatera Utara
Ukuran citra sebelum dikompres = 69,5 kB Ukuran citra setelah dikompres = 25 kB Rasio Pemampatan = 100% - (25 kB/69,5 kB x 100%) = 100% - 36% = 64% Artinya, 64% dari data semula telah dimampatkan. Waktu yang dibutuhkan untuk melakukan kompresi data pada gambar berukuran 69,5 kB adalah 114 detik. Untuk melihat hasil perbandingan dari ketiga teknik kompresi diatas, dapat kita lihat pada Tabel 3.4 dibawah ini : Teknik
Ukuran Citra
Ukuran Citra
Waktu
Rasio
Kompresi
Sebelum
Setelah
Kompresi Yang
Persentase
Dikompres
Dikompres
Dibutuhkan
Kompresi
69,5 kB
62,9 kB
64 Detik
10%
69,5 kB
31 kB
104 Detik
55,4%
69,5 kB
25 kB
114 Detik
64%
Huffman Code Set Partitioning In Hierarchical Trees (SPIHT) Discrete Cosine Transform (DCT)
Tabel 3.4 Hasil Perbandingan Dari Ketiga Teknik Kompresi
Universitas Sumatera Utara
Dari Tabel 3.4 diatas dapat disimpulkan Teknik Kompresi dengan Rasio Persentase terendah menggunakan Teknik Kompresi Huffman Code dengan rasio persentase 10% dan waktu yang dibutuhkan untuk melakukan kompresi 64 detik. Pada Teknik Kompresi menggunakan Set Partitioning In Hierarchical Trees (SPIHT), rasio persentase 55,4% dan waktu yang dibutuhkan untuk melakukan kompresi 104 detik. Dan pada Teknik Kompresi menggunakan Discrete Cosine Transform (DCT) Rasio persentase 64% tetapi waktu yang dibutuhkan untuk melakukan kompresi merupakan waktu yang terlama yakni 114 detik.
Universitas Sumatera Utara
BAB IV IMPLEMENTASI DAN APLIKASI TEKNIK KOMPRESI SET PARTITIONING IN HIERARCHICAL TREES PADA PERANGKAT BERGERAK
4.1
Pendahuluan Pada saat ini,sangat banyak dibangun aplikasi-aplikasi atau software untuk
perangkat lunak seperti komputer, laptop, dan terutama handphone. Dibuatnya software-software ini bertujuan untuk memudahkan para pengguna untuk membantu dalam berbagai kegiatan. Apalagi saat ini setiap orang sangat butuh aplikasi-aplikasi dalam pengiriman dan penerimaan data agar lebih menghemat bandwidth, menghemat memory, dan terutama menghemat waktu. Pada bab ini dibahas bagaimana penggunaan aplikasi teknik kompresi dengan algoritma Set Partitioning In Hierarchical Trees dengan bahasa Java sebagai tools dan untuk menunjukkan bagaimana cara mengkompress file dan mengupload file. Pada aplikasinya,teknik kompresi ini diimplementasikan pada perangkat mobile berbasis atau berplatform Android.
4.2
Android Android adalah sistem operasi untuk telepon seluler yang berbasis
Linux. Android juga menyediakan platform terbuka bagi para pengembang guna menciptakan aplikasi mereka sendiri untuk digunakan oleh bermacam peranti bergerak. Android merupakan sebuah sistem operasi untuk telepon seluler seperti
Universitas Sumatera Utara
halnya Symbian pada Nokia, Palm dan Windows Mobile yang sebelumnya sudah terlebih dahulu kita kenal selama ini. Android merupakan kumpulan perangkat lunak yang ditujukan bagi perangkat bergerak mencakup middleware, sistem operasi, dan aplikasi kunci. Android Standart Development Kid (SDK) menyediakan perlengkapan dan application. Android
Programming
Interface
(API)
yang
diperlukan
untuk
mengembangkan aplikasi pada platform Android menggunakan bahasa pemrograman Java. Android dikembangkan oleh Google bersama Open Handset Allience (OHA) yaitu aliansi perangkat selular terbuka yang terdiri dari 47 perusahaan Hardware, Software dan perusahaan telekomunikasi ditujukan untuk mengembangkan standar terbuka bagi perangkat selular [8].
4.3
Anatomi Android Dalam paket sistem operasi Android tediri dari beberapa unsur seperti tampak
pada gambar. Secara sederhana arsitektur Android merupakan sebuah kernel Linux dan sekumpulan pustaka C / C++ dalam suatu framework yang menyediakan dan mengatur alur proses aplikasi.
Universitas Sumatera Utara
Gambar 4.1 Anatomi Android
4.4
Spesifikasi Perangkat Lunak Dalam menerapkan rancangan yang telah dibuat, dibutuhkan beberapa
software untuk membuat program yaitu [9]: 1.
Bahasa Pemrograman Java Dalam hal ini digunakan Java Development Kid (JDK) 1.6 dan Java Runtime Environment (JRE).
2.
Sistem Operasi Untuk penggunaan sistem operasi dapat digunakan Windows XP (32-bit) atau Vista (32 atau 64 bit), Mac OS X 10.4.8 atau diatasnya, dan Linux.
Universitas Sumatera Utara
3.
Integrated Development Environment (IDE) Eclipse 3.4 atau 3.5 Untuk memudahkan dalam pengembangan aplikasi, maka digunakan IDE karena memiliki beberapa fasilitas yang diperlukan dalam pembangunan perangkat lunak. Adapun dalam pengembangan ini digunakan Eclipse v 3.4 atau 3.5 dikarenakan telah mendukung Android Development Tools.
4.
Android Software Development Kit (Android SDK) Android SDK menyediakan development environment dengan semua komponen yang diperlukan. Antara lain tools pengembangan, libraries, dokumentasi, dan contoh aplikasi serta disertakan pula emulator untuk mensimulasikan aplikasi berjalan pada perangkat.
5.
Android Development Tools (ADT) Android membuat kostum plugin untuk IDE Eclipse, sehingga dengan adanya ADT ini memberikan kemudahan dalam pengembangan aplikasi, membuat tampilan antarmuka aplikasi, menambahkan komponen yang diperlukan, mendebug aplikasi dengan menggunakan perangkat SDK Android, dan bahkan membungkus aplikasi yang telah dikembangkan untuk di distribusikan. Adapun ADT yang digunakan adalah ADT 0.9.5.
Universitas Sumatera Utara
4.5
Use Case Diagram SISTEM
Melakukan Kompresi Data Melakukan Dekompresi Data
Menggunakan Fitur Download USER
Menggunakan Fitur Uploadload
Melihat Matriks Data Hasil
Melakukan Pengambilan Data Input (Download) Dan Data Output (Upload)
INTERNET (PHP SCRIPT DAN SERVER) Gambar 4.2 Diagram Use Case
Universitas Sumatera Utara
Gambar 4.2 merupakan Diagram Use case yaitu merupakan gambaran skenario dari interaksi antara user dengan sistem. Sebuah diagram use case menggambarkan hubungan antara aktor dan kegiatan yang dapat dilakukannya terhadap aplikasi.
Di dalam diagram terdapat sebuah extend yang digunakan
untuk menunjukkan bahwa satu use case merupakan tambahan fungsional dari use case lain jika kondisi tertentu terpenuhi [10].
4.6
Diagram Alir Diagram Alir atau flowchart merupakan serangkaian bagian-bagian yang menggambarkan alir program. Pada diagram alir ini digambarkan urutan prosedur dalam metode dan aplikasi. Start
Piih Pixel Yang Hendak Dipartisi
Algoritma SPIHT
Koefisien SPIHT
End
Gambar 4.3 Diagram Alir Koefisien SPIHT
Universitas Sumatera Utara
4.7
Diagram Kelas Sistem Activity
Preference Activity
Rsosurce
Shutdown Service
Set Partitioning In Hierarchical Trees
Perihal
Compress
Image Manager
SPIHT for Compress
Uploader
SPIHT Transform
Download File
Gambar 4.4 Diagram Kelas Sistem
Diagram kelas merupakan suatu diagram struktural yang menggambarkan interaksi sekumpulan kelas interface, kolaborasi, dan relasinya.
Universitas Sumatera Utara
4.8
Pembuatan Program Kompresi Gambar Dengan Algoritma Set Partitional In Hierarchical Trees Berikut ini akan dijelaskan bagaimana pembuatan program atau aplikasi
kompresi gambar denagn algoritma Set Partitioning In Hierarchical Trees.Secara sederhana, diagram alir dalam menggunakan program ini dapat dilihat pada Gambar 4.5
Start
Input Data Gambar
Kompress Dengan Algoritma SPIHT
Hasil Gambar Setelah Dikompress
End
Gambar 4.5 Diagram Alir Proses Penggunaan Program
Universitas Sumatera Utara
4.8.1 Pembuatan Tampilan Antar Muka (Interface) Perancangan interface adalah bagian yang penting dalam aplikasi, karena yang pertama kali dilihat ketika aplikasi dijalankan adalah tampilan antar muka (interface) aplikasi. Pembuatan tampilan antarmuka pada sistem Android di implementasikan dalam bentuk XML. Setiap elemen dalam tampilan antarmuka perlu ditambahkan atribut pengenal, sehingga elemen tersebut akan di generate dalam kelas Resource dan memudahkan untuk digunakan pada kelas yang memerlukan. Kode programnya terdapat pada Lampiran 1. Adapun diagram alir proses pembuatan Interface dapat dilihat pada Gambar 4.6 Start
Rancang Tampilannya
Buat Pada Sistem Android Dalam Bentuk XML
Hasil Interface
End
Gambar 4.6 Diagram Alir Proses Pembuatan Interface
Universitas Sumatera Utara
4.8.2 Pembuatan Kelas Utama SPIHT for Compress Kelas SPIHT for Compress merupakan kelas utama yang berfungsi untuk menampilkan menu dan urutan urutan activity pada aplikasi dan melakukan pemanggilan terhadap kelas yang dipilih dan kemudian di eksekusi sehingga proses berjalan. Kode programnya terdapat pada Lampiran 2. Adapun diagram alir proses pembuatan kelas utama SPIHT for Compress dapat dilihat pada Gambar 4.7
Start
Jalankan Kelas Utama SPIHT for Compress
Panggil Kelas Yang Telah Dipilih
Eksekusi Kelas
End
Gambar 4.7 Diagram Alir Proses Pembuatan Kelas Utama SPIHT for Compress
Universitas Sumatera Utara
4.8.3 Pembuatan Kelas Compress Kelas Compress merupakan kelas yang berfungsi untuk memproses perhitungan dari metode metode pada algoritma set partitioning in hierarchical trees serta melakukan penulisan file. Kode programnya terdapat pada Lampiran 3. Adapun Diagram Alir Proses Pembuatan Kelas Compress dapat dilihat pada Gambar 4.8
Start
Jalankan Program Compress
Proses Perhitungan Dengan Algoritma SPIHT
Hasil Perhitungan
End
Gambar 4.8 Diagram Alir Proses Pembuatan Kelas Compress
.
Universitas Sumatera Utara
4.8.4 Pembuatan Kelas Decompress Kelas ini bertujuan untuk melakukan dekompresi pada data yang telah dikompresi. Kode programnya terdapat pada Lampiran 4. Adapun Diagram Alir Proses Pembuatan Kelas Decompress dapat dilihat pada Gambar 4.9
Start
Jalankan Program Decompress
Ambil Data Yang Hendak Dikompres
Simpan Pada Folder Hasil Decompress
End
Gambar 4.9 Diagram Alir Proses Pembuatan Kelas Decompress
Universitas Sumatera Utara
4.8.5 Pembuatan Kelas Download File Kelas Download File bertujuan untuk melakukan proses download pada data yang kita perlukan baik itu ingin di kompresi maupun ingin dikompresi. Kode programnya terdapat pada Lampiran 5. Adapun Diagram Alir Proses Pembuatan Kelas Download File dapat dilihat pada Gambar 4.10
Start
Jalankan Program Download File
Ambil Data Yang Hendak Didownload
Simpan Pada Folder Hasil Download File
End
Gambar 4.10 Diagram Alir Proses Pembuatan Kelas Download File
Universitas Sumatera Utara
4.8.6 Pembuatan Kelas Upload Kelas Upload dibuat apabila ingin melakukan proses upload data yang belum atau sudah di kompres sehingga memudahkan untuk melakukan pengiriman file data. Pada kelas ini diperlukan pembuatan php script untuk membuat sebuah receiver pada local server agar local server dapat menerima data yang di upload oleh perangkat bergerak berbasis android. Kode programnya terdapat pada Lampiran 6. Adapun Diagram Alir Proses Pembuatan Kelas Upload dapat dilihat pada Gambar 4.11
Start
Jalankan Program Upload
Ambil Data Yang Sudah Diproses Untuk Diupload
Kirim File Ke Local Server
End
Gambar 4.11 Diagram Alir Proses Pembuatan Kelas Upload
Universitas Sumatera Utara
4.8.7 Pembuatan Kelas Uploader Kelas uploader dibuat untuk membuat koneksi http pada server dan memastikan susunan data ketika data di upload. Kode programnya terdapat pada Lampiran 7. Adapun Diagram Alir Proses Pembuatan Kelas Uploader dapat dilihat pada Gambar 4.12
Start
Jalankan Program Uploader
Buat Koneksi http Pada Server
Pastikan Susunan Data Kembali Untuk diupload
End
Gambar 4.12 Diagram Alir Proses Pembuatan Kelas Uploader
Universitas Sumatera Utara
4.8.8 Pembuatan Kelas Set Partitioning In Hierarchical Trees Kelas Set Partitioning In Hieararchical Trees merupakan kelas yang berisi informasi-informasi matriks yang sudah ditetapkan untuk memudahkan dilakukannya langkah langkah kompresi. Proses yang terjadi di kelas ini merupakan proses kompresi utama dimana matriks-matriks ini di komputasi pada kelas ini bila dipanggil oleh resources yang lain. Kode programnya terdapat pada Lampiran 8. Adapun Diagram Alir Proses Pembuatan Kelas Set Partitioning In Hieararchical Trees dapat dilihat pada Gambar 4.13 Start
Jalankan Program SPIHT
Data Diproses Dengan Matriks Komputasi
Hasil Proses Matriks Komputasi
End
Gambar 4.13 Diagram Alir Proses Pembuatan Kelas Set Partitioning In Hieararchical Trees
Universitas Sumatera Utara
4.8.9 Pembuatan Manifest Aplikasi Manifest pada android berguna untuk member izin kepada aplikasi untuk mengambil data baik pada internet ataupun local server. Selain itu manifest disini berisi parameter-parameter tertentu dimana identitas sebuah kelas ada dan dapat berhubungan dengan kelas yang lain. Kode programnya terdapat pada Lampiran 9. Adapun Diagram Alir Proses Pembuatan Kelas Manifest Aplikasi dapat dilihat pada Gambar 4.14
Start
Jalankan Program Manifest
Input Data Yang Ingin Diberi Izin Untuk Mengambil Data Pada Internet
Hasil Data Yang Telah Diizinkan Beserta Parameter Identitas Sebuah Kelas
End
Gambar 4.14 Diagram Alir Proses Pembuatan Kelas Manifest Aplikasi
Universitas Sumatera Utara
4.9
Pengujian Pengujian pada aplikasi ini dilakukan dengan menguji atribut dan metode
yang ada pada kelas- kelas yang dibangun sesuai dengan proses pembuatan dan pengembangan pada aplikasi ini. Pengukuran hasil kompresi dengan teknik set partitioning in hierarchical trees dilakukan dengan menggunakan pendekatan subjektif maupun objektif. Berikut adalah hasil dari implementasi sistem yang telah dibuat:
Gambar 4.15 Proses Pemunculan dan Eksekusi Aplikasi yang Berhasil Pada gambar 4.15 terlihat bahwa activity telah berhasil di launch dan kemudian dilakukan proses peng-installan aplikasi dimana ditandai dengan Installing SPIHTforCompress.apk… dan kemudian aplikasi akan berjalan dengan melakukan launch emulator android 2.2. Pada gambar 4.16 Terlihat proses loading dari emulator tersebut.
Universitas Sumatera Utara
Gambar 4.16 Proses Loading Emulator Android Versi 2.2
Emulator android 2.2 berhasil ditampilkan dan kemudian emulator inilah yang menjadi device tempat instalasi program aplikasi SPIHTforCompress.
Gambar 4.17 Halaman Utama Emulator Android 2.2
Universitas Sumatera Utara
Pada Gambar 4.17 merupakan tampilan dari halaman utama emulator android.
Gambar 4.18 Memulai Aplikasi Dengan Mengklik Widget Aplikasi SPIHTforCompress Untuk memulai aplikasi, klik widget SPIHTforCompress seperti terlihat pada gambar 4.18, kemudian tunggu dan kemudian akan muncul tampilan seperti gambar 4.19.
Gambar 4.19 Tampilan Menu dan Klik Compress
Universitas Sumatera Utara
Gambar 4.20 Proses Kompresi Yang Terjadi Pada Perangkat Lunak Dapat Dilihat Pada Debug
Pada gambar 4.20 dapat dilihat bahwa terjadi suatu proses komputasi dengan suatu metode yang telah disebutkan pada pembuatan kelas. Pada gambar 4.20 proses pembacaan matriks dan pengkodean matriks sedang berjalan dan hasil matriksnya akan ditampilkan pada gambar 4.20
Universitas Sumatera Utara
Gambar 4.21 Matriks Transform Hasil Kompresi Yang Ditampilkan
Pada Gambar 4.21 dapat kita lihat matriks transform hasil kompresi, yang ditampilkan pada emulator.
Gambar 4.22 File Hasil Kompresi Yang Terletak Pada sdcard Device Dan Ukuran Datanya
Universitas Sumatera Utara
Dari gambar 4.22 dapat dilihat bahwa file hasil kompresi telah tersimpan pada directory /sdcard/ pada device. Selain itu terlihat bahwa ukuran data menjadi mengecil dari sebelumnya yaitu dari 69,5 KB menjadi 31 KB
Gambar 4.23 Proses Upload Data Hasil Kompresi
Gambar 4.23 menunjukkan proses untuk melakukan upload pada data yang telah dikecilkan. Sesuai tujuan kompresi, yaitu untuk mengecilkan data sebelum dikirimkan ke server atau ke host yang telah di tentukan sebelumnya pada proses coding.
Universitas Sumatera Utara
Gambar 4.24 Directory Local Server Pada Perangkat Yang Diuji Coba Dengan Menggunakan Wamp Server Pada Localhost
Dengan menggunakan software wamp5, server pada localhost dibuat dan menjadi tujuan upload dari device android tersebut. Membuka directory www dari wamp dibuka dari browser dengan mengetikkan alamat http;//localhost pada browser. Prosesnya dapat kita lihat pada Gambar 4.24.
Universitas Sumatera Utara
Gambar 4.25 File Telah Berhasil Di-Upload
Pada Gambar 4.25 di atas merupakan tampilan dari letak directory upload yang terdapat di localhost.
Universitas Sumatera Utara
Gambar 4.26 Properties Data Sebelum Dikompres
Pada Gambar 4.26 di atas dapat kita lihat properties data gambar tadi sebelum dikompres. Kita dapat melihat ukuran file sebelum dikompress adalah sebesar 69,5 kB.
Universitas Sumatera Utara
Gambar 4.27 Properties Data Setelah Dikompres Pada Gambar 4.27 di atas dapat kita lihat properties data gambar tadi setelah dikompres. Kita dapat melihat ukuran file setelah dikompress adalah sebesar 31,0 kB. Pada Gambar 4.28 dan 4.29 akan ditampilkan gambar yang tadi diproses.
Universitas Sumatera Utara
Gambar 4.28 Citra Sebelum Dikompres
Gambar 4.29 Citra Setelah Dikompres Dari kedua gambar di atas dapat kita lihat sedikit perbedaan citra sebelum dikompres dan citra yang telah dikompres dimana pada hasil citra yang telah
Universitas Sumatera Utara
dikompres, kontras atau tingkat kecerahan warnanya sedikit buram tidak secerah citra sebelum dikompres. Berdasarkan hasil pengujian yang dilihat dari hasil properties diatas dapat dihitung rasio kompresi dengan menggunakan persamaan (2.7)
Rasio = 100% - (HasilKompresi/CitraAsli x 100%)
Maka dapat dihitung Ukuran citra sebelum dikompres
= 69,5 kB
Ukuran citra setelah dikompres
= 31,0 kB
Rasio pemampatan
= 100% - (31,0 KB/ 69,5 KB x 100%) = 100% - 44,6 % = 55,4 %
Artinya,55,4% dari data semula telah dimampatkan. Waktu yang dibutuhkan untuk melakukan kompresi data pada data gambar berukuran 69,5 KB adalah 104 detik.
Universitas Sumatera Utara
BAB V KESIMPULAN DAN SARAN
5.1
Kesimpulan Dari hasil yang telah diperoleh maka dapat ditarik kesimpulan : 1. Metode kompresi lossy pada gambar merupakan salah satu metode pemampatan citra yang menghasilkan rasio pemampatan tinggi. Ukuran file citra menjadi lebih kecil tanpa menghilangkan kualitas citra secara signifikan. 2. Pada contoh yang dipaparkan, kompresi dengan algoritma Set Partitioninig In Hierarchical Trees mempunyai rasio kompresi 55,4% dengan menggunakan level kuantisasi 50 dan diperlukan waktu 104 detik untuk melakukan kompresi pada perangkat bergerak. 3. Setelah dibandingkan dengan Algoritma Huffman dan Algoritma Discrete Cosine Transform (DCT) dapat disimpulkan bahwa rasio kompresi menggunakan Algoritma Discrete Cosine Transform (DCT) kualitas pemampatan hingga 64% dengan waktu kompresi 114 detik. Sedangkan untuk Algoritma Huffman kualitas pemampatannya hanya 10% dengan waktu kompresi 64 detik.
Universitas Sumatera Utara
5.2
Saran Beberapa saran yang dapat penulis berikan pada tugas akhir ini adalah : 1. Untuk pengembangan lebih lanjut, metode kompresi yang digunakan tidak hanya satu tapi dapat dikombinasikan dari beberapa metode kompresi yang lain sehingga dapat dicapai hasil yang lebih maksimal dan lebih efisien. 2. Untuk selanjutnya, diharapkan aplikasi ini dapat dikembangkan pada perangkat lunak dan perangkat bergerak tidak hanya pada satu jenis platform, tapi juga berbagai jenis platform lainnya.
Universitas Sumatera Utara