Kompresi Lossless

GAMBARAN UMUM KOMPRESI

Kompresi adalah proses mengubah data menjadi sekumpulan kode untuk menghemat tempat penyimpanan dengan atau tanpa mengurangi kualitas dari citra serta mempercepat waktu transmisi data. Tujuan dari kompresi terhadap citra digital ini adalah untuk mengurangi redudansi dari data - data yang terdapat dalam citra sehingga dapat disimpan atau ditransmisikan secara efisien. Data yang dikompres dapat berupa :

· teks/biner,

· gambar (JPEG, PNG, TIFF),

· audio (MP3, AAC, RMA, WMA), dan

· video (MPEG, H261, H263)

Secara umum ada hal yang bisa dikompresi dari data berupa teks, gambar, audio, dan video adalah sebagai berikut:

Redundancy data

Redundandy data merupakan nilai sample yang bertetanggan adalah saling berhubungan, secara statistic. Menghilangkan redudancy tidak akan merubah arti data. Berikut ini merupakan redundancy yang ada pada data multimedia

o Redundancy pada audio

§ Nilai sample suara yang berurutan

Adanya nilai sample suara yang hampir mirip antara suatu nilai dengan nilai-nilai sample suara berikutnya. Pada proses kompresi nilai sample suara berikutnya tersebut dapat diprediksi berdasarkan nilai sample suara sebelumnya sehingga tidak perlu ditulis dan dapat memperkecil besarnya ukuran data. Prediksi sample suara ini disebut Predictive coding

§ Suara diam

Dalam audio rekaman percakapan, selama melakukan percakapan/berbicara terdapat waktu kosong/tidak bersuara. Menghilangkan sample suara pada saat itu tidak akan mempengaruhi arti dari pembicaraan. Hal inilah yang disebut silence removal.

o Redundancy pada citra

§ Pixel warna yang sama

Dalam sebuah citra, biasanya terdapat sederet pixel yang memiliki kesamaan warna, maka untuk menghemat memori, pixel yang sama tidak perlu dituliskan semua, melainkan cukup menuliskan berapa banyak perulangan dari pixel tersebut

§ Spatial redundancy

Spatial redundancy merupakan kemiripan pixel yang ada pada sample bertetangga pada suatu garis scanning. Spatial redundancy ini dapat dihilangkan dengan teknik pengkodean prediksi dan teknik lain, misalnya saja transform coding.

o Redundancy pada video

§ Temporal redundancy

Seperti yang telah dijelaskan pada presentasi sebelumnya, video merupakan array dari gambar diam. Gambar-gambar diam yang bertetangga ini biasanya memiliki kemiripan dan dapat dihilangkan dengan pengkodean prediksi.

Presepsi manusia

o Pada Citra

§ Chroma subsampling

Pada dasarnya, mata manusia lebih peka terhadap brightness dari pada warna itu sendiri. Untuk itulah dilakukan pengurangan resolusi warna dengan disampling ulang.

GAMBARAN UMUM KOMPRESI LOSSLESS

Pengertian

Berdasarkan fungsinya, metode kompresi dibagi menjadi dua yaitu metode lossy dan metode lossless. Metode Lossless adalah suatu metode pemampatan data tanpa menghilangkan data yang dimilikinya. Proses kompresi dapat dilakukan dengan mengganti suatu data dengan kode yang berukuran lebih ringkas.

Data yang telah diganti dapat dikembalikan dengan ukuran dan struktur yang sama persis dengan data asli melalui proses dekompresi. Teknik ini bersifat dua arah, karena untuk membaca data yang telah terkompres diperlukan proses dekompresi. Berbeda dengan algoritma lossy, file hasil kompresi dengan metode lossless tak dapat dibaca tanpa melalui proses dekompresi. Teknik dekompresi ini bersifat spesial untuk satu teknik kompresi. Sehingga tidak mungkin file yang terkompres oleh oleh algoritma kompresi A dapat di dekompres dengan algoritma dekompres B.

Tujuan utama dari metode lossless adalah menghasilkan file yang kecil namun tanpa sedikitpun mengurangi kualitas data tersebut. Hal ini sangat penting untuk data-data yang memerlukan keakuratan yang tinggi.

Ciri-Ciri

Adapun ciri-ciri dari teknik kompresi lossless ini adalah :

· Metode lossless menghasilkan data yang identik dengan data aslinya

· Data tidak berubah atau hilang pada proses kompresi atau dekompresi

· Ratio kompresi (Rasio kompresi yaitu, ukuran file yang dikompresi dibanding yang tak terkompresi dari file) dengan metode ini sangat rendah

· Menghilangkan perulangan karakter

· Menghilangkan redundancy yang ada pada data, baik teks, citra, audio, maupun video.

Kelebihan dan Kekurangan

· Kelebihan

o Tidak ada satupun informasi data yang hilang.

o Data dapat didekompresi dan membentuk data yang sama persis dengan aslinya (reversible).

· Kekurangan

o Rasio (perbandingan ukuran data sebelum dan sesudah) kompresi rendah.

o kadangkala ada data-data yang setelah dikompresi dengan teknik ini ukurannya menjadi sama atau bahkan lebih besar.

ALGORITMA KOMPRESI LOSSLESS

Terdapat 2 teknik kompresi yang umum digunakan dalam kompersi data lossless, yakni :

· Berdasarkan pada prinsip data yang sering muncul akan dikodekan dengan lebih sedikit bit. Contoh : Huffman Coding.

· Berdasarkan pada permodelan statistic untuk data teks. Misalkan dengan membangun suatu kamus (dictionary) dari symbol-simbol yang sering muncul pada suatu blok dan kemudian hanya diacu (reference) dengan menggunakan pointer. Contoh : algoritma LZ (Lempel-Ziv).

Terdapat beberapa algoritma dengan teknik kompresi lossless, diantaranya algoritma RLE (Run-Length-Encoding), Huffman Coding, dan Lempel-Ziv-Welch Coding).

Ø RLE (Run-Length-Encoding)

a. RLE merupakan teknik yang digunakan untuk kompresi data yang berisi karakter-karater berulang, misal teks ataupun grafik seperti icon atau gambar garis-garis yang banyak memiliki kesamaan pola (misal kompresi image hitam-putih atau binary).

b. Contoh penerapan algoritma ini : ILBM (interleaved bitmap), PCX (personal computer exchange), dan PNG.

c. Ciri – ciri RLE :

· String karakter yang berulang menempati dua byte (byte pertama berisi jumlah dari banyaknya perulangan, byte kedua berisi karakter itu sendiri ).

· Algoritma ini dilakukan pada satu baris (atau scanline), dan tidak digunakan pada baris yang mempunyai jumlah scanline banyak.

· Byte bisa lebih besar dari pada byte image asli. Efek ini disebut reverse compression atau negative compression.

· RLE ada yang menggunakan flag bilangan negatif untuk menandai jarak flag tersebut ke titik awal dari bilangan yang menyatakan jumlah perulangan dari karakter yang berulang sebanyak karakter yang dilalui. (RLE tipe 2).

· RLE ada yang menggunakan suatu karakter yang tidak digunakan dalam teks tersebut seperti misalnya ‘!’ untuk menandai batas antara karakter dan jumlah perulangannya.Kelemahannya jika ada karakter angka dalam data tersebut, bisa terjadi ambiguitas antara tanda mulai dan akhir dari nilai/bilangan yang menyatakan jumlah perulangan.

d. Contoh Studi Kasus

Data : ABCCCCCCCCDEFGGGG = 17 karakter

RLE tipe 1 : ABC!8DEFG!4 (tipe 1, minimal 4 huruf sama)

RLE tipe 2 : -2AB8C-3DEF4G

Ø Huffman Coding

a. Huffman Coding merupakan kompresi data yang yang dikembangkan oleh David A. Huffman dan dicapai dengan mengkodekan data menggunakan struktur data berupa weighted binary tree atau pohon Huffman berdasarkan pada frekuensi kemunculannya.

b. Contoh penerapan algoritma ini : JPEG dan PNG.

c. Ciri – ciri Huffman Coding :

· Berbasis pada perhitungan statistik

· Representasi pengkodean dari data statistic yang didapat menggunakan pohon biner. Tiap cabang kiri yang terdapat pada pohon Huffman diberi tanda biner 0 sedangkan cabang kanan 1 atau sebaliknya.

· Elemen atau data yang frekuensinya muncul paling banyak dikodekan dengan jumlah bit terkecil dan nodenya berada di puncak pohon biner (dekat root). Sedangkan data yang paling jarang muncul dikodekan dengan jumlah bit terbesar dan nodenya berada di dasar pohon (leaf).

d. Langkah-langkah pada algoritma Huffman

1. Jika data masih berupa matriks, ubah data tersebut menjadi vektor.

2. Hitung frekuensi kemunculan tiap karakter dalam data.

3. Urutkan secara ascending karakter berdasarkan frekuensi kemunculannya atau peluang kemunculannya dan nyatakan sebagai node/simpul pohon biner.

4. Gabungkan 2 buah node yang mempunyai frekuensi kemunculan paling kecil pada sebuah akar. Akar mempunyai frekuensi yang merupakan jumlah dari frekuensi dua pohon penyusunnya. Frekuensi dengan nilai lebih kecil diletakkan di sisi kiri dan diberi bobot 0 sedangkan sisi kanan diberi bobot 1 (atau sebaliknya).

5. Ulangi langkah 4 sampai tersisa 1 pohon biner.

6. Telusuri pohon biner dari akar ke daun. Barisan bobot sisi dari akar ke daun menyatakan kode Huffman untuk karater yang bersesuaian.

7. Mengganti data dengan kode Huffman yang bersesuaian

e. Contoh Studi Kasus

Terdapat citra dengan ukuran 64x64 dengan 8 derajat keabuan (k). Jumlah seluruh piksel (n) = 64 x 64 = 4096

Ø Lempel-Ziv-Welch Coding

a. Lempel-Ziv-Welch Coding merupakan algoritma yang tidak mengkodekan sebuah symbol/karakter sebagai bit streams, tetapi mengkodekan beberapa variabel sebagai sebuah token (string) ke dalam bentuk table gabungan karakter (kata dalam kamus).

b. Contoh penerapan algoritma ini : GIF, TIFF, dan ZIP

c. Ciri – ciri Lempel-Ziv-Welch-Coding :

· Algoritma ini menggunakan suatu tabel referensi untuk menyimpan simbol yang akan dikodekan.

· Sebagai inisialisasi, kamus berisi set karakter yang digunakan untuk membuat suatu teks. Selanjutnya kamus diisi secara dinamis berdasarkan data (misal kata-kata yang ada dalam teks).

d. Langkah-langkah pada algoritma LZW

Begin

S = next input character;

While not EOF{

C = next input character;

if s + c exists in dictionary

S = s + c;

else{

output code for S;

add string s + c to dictionary with new code S = c;

}}

End

e. Contoh Studi Kasus

Input Data: ABABBABCABABBA

Langkah penyelesaian :

· Awalnya membuat kode untuk masing-masing karakter yang muncul dan memasukkannya dalam kamus. A=1, B=2, C=3.

· Kemudian membuat kamus sesuai algoritma ini. Sebagai contoh karakter awal data inputan pada kasus ini adalah A (pada kolom S), selanjutnya B(pada kolom C). Langkah pertama membentuk string baru dari S+C (menjadi AB). Lalu cek keberadaan AB dalam kamus. Jika belum ada maka output diisi dengan kode dari S (yakni kode karakter A yaitu 1). selanjutnya AB dimasukkan dalam kamus dan dibuatkan kode baru sesuai urutan kode yang sudah ada dalam kamus (sehingga kode AB = 4). Sebaliknya jika S+C (dalam kasus ini AB) sudah ada (seperti pada baris ke 6 gambar tabel di atas) maka S yang baru menjadi S+C atau AB.

· Untuk langkah selanjutnya, C sekarang menjadi S kemudian karakter C yang baru merupkan karakter setelah C yang lama dalam data inputan. (dalam kasus ini karakter setelah B adalah A lagi). Pengecekan ini berlanjut sampai akhir dari karakter yang diinputan.

TOOLS KOMPRESI LOSSLESS

· ZIP

– Menggunakan LZW .

– Dapat menggabungkan dan mengkompresi beberapa file sekaligus menggunakan bermacam-macam algoritma

– Aplikasi : WinZip (standar kompresi data yang populer, dengan hasil kompresi data yang lebih kecil maka akan menghemat media penyimpanan dan pengiriman data akan lebih efisien dan efektif)

– Proses kompresi lebih lambat dari ZIP tapi ukuran kompresi lebih kecil

– Aplikasi : WinRAR yang mampu menangani RAR dan ZIP, mendukung volume split, enkripsi AES

– WinRAR adalah sebuah program yang berguna untuk mengkompres file menjadi lebih kecil dari ukuran aslinya serta untuk back up file menjadi satu buat file didalam file winRAR, sehingga membuat ukurannya menjadi lebih kecil.

GZIP

– Gzip adalah software kompresi file buatan Jean-loup Gailly yang menggabungkan algoritma Lempel-Ziv & Huffman

7-Zip

– Pengembangan dari ZIP . Hasil kompresinya merupakan yang paling kecil dari yang lain.

PENGGUNAAN KOMPRESI LOSSLESS

· Citra

Digunakan pada pencitraan medis, untuk keperluan arsip, gambar teknis, clip art , atau komik.

Tujuannya adalah untuk mengurangi redundansi dari data citra dalam rangka untuk dapat menyimpan atau mengirimkan data dalam bentuk yang efisien.

· Audio

Untuk audiophile : penggemar music dan pengarsipan audio yang penting.

Kompresi data dirancang untuk mengurangi kebutuhan bandwidth transmisi digital audio stream dan ukuran penyimpanan file audio

· Teks

Pengiriman data dokumen melalui email yang biasanya dikompress terlebih dahulu dengan tools seperti zip untuk mempercepat pengiriman.

· Video

Digunakan untuk pengiriman video melalui TV kabel, atau melalui TV satelit layanan. Tujuannya untuk mengurangi jumlah data yang digunakan untuk mewakili video digital gambar, dan merupakan kombinasi dari ruang kompresi gambar dan temporal kompensasi gerak

Langitku

Pages