BAB III KOMPRESI DATA MENGGUNAKAN SET PARTITIONING IN HIERARCHICAL TREES. menghilangkan kualitas citra secara signifikan. Metode kompresi lossy

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


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


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


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:


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


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


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


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


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.


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


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


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


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.


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


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


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


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.


∑ 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.


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


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


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)


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

=


= = 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.


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)


α (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].


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


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


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

=


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


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


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


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


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


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


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)


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


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.


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)


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


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)


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



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


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


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.


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


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.


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.


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.


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


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


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.


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


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


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


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

.


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


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


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


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


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


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


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.


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


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


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


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


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.


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.


Gambar 4.25 File Telah Berhasil Di-Upload

Pada Gambar 4.25 di atas merupakan tampilan dari letak directory upload yang terdapat di localhost.


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.


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.



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


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.


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.


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.


BAB III KOMPRESI DATA MENGGUNAKAN SET PARTITIONING IN HIERARCHICAL TREES. menghilangkan kualitas citra secara signifikan. Metode kompresi lossy

Recommend Documents