Kompresi Lossless
Teknik kompresi lossy merupakan metode pengkodean yang mengompresi bagian dari data, tanpa dapat mengembalikannya lagi ke bentuk semula. Teknik ini membuang bagian-bagian data yang sebenarnya tidak begitu berguna, tidak begitu dirasakan, tidak begitu dilihat oleh manusia. Lossy kompresi ini paling sering digunakan untuk kompres data multimedia (Audio, gambar diam). Sebaliknya, kompresi lossless diperlukan untuk data teks dan file.
Format kompresi lossy mengalami generation loss atau apabila dilakukan berulang kali kompresi dan dekompresi file akan membuat kehilangan kualitas secara progresif. Ini berbeda dengan kompresi data lossless. ketika pengguna yang menerima file terkompresi secara lossy, file yang diambil dapat sedikit berbeda dari yang asli.
Metode ini menghasilkan ratio kompresi yang lebih besar daripada metode lossless. Misal terdapat image asli berukuran 12,249 bytes, kemudian dilakukan kompresi dengan JPEG kualitas 30 dan berukuran 1,869 bytes berarti image tersebut 85% lebih kecil dan ratio kompresi 15%. Contoh metode lossy adalah metode CS&Q (coarser sampling and/or quantization), JPEG, dan MPEG.
Ada dua skema dasar lossy kompresi :
Lossy transform codec, sampel suara atau gambar yang diambil, di potong kesegmen kecil, diubah menjadi ruang basis yang baru, dan kuantisasi. hasil nilai kuantisasi menjadi entropy coded
Lossy predictive codec, sebelum dan/atau sesudahnya data di-decode digunakan untuk memprediksi sampel suara dan frame picture saat ini. kesalahan antara data prediksi dan data yang nyata, bersama-sama dengan informasi lain digunakan untuk mereproduksi prediksi, dan kemudian dikuantisasi dan kode.
Dalam beberapa sistem kedua teknik digabungkan, dengan mengubah codec yang digunakan untuk mengkompresi kesalahan sinyal yang dihasilkan dari tahapan prediksi.
Lossless data kompresi akan digunakan dalam berbagai aplikasi.Sebagai contoh, digunakan dalam ZIP format file dan di Unix alatgzip. Hal ini juga sering digunakan sebagai komponen dalam datalossy kompresi lossless teknologi (misalnya pertengahan / jointstereo sisi preprocessing oleh Lame MP3 encoder dan lainencoders audio lossy).
Teknik Kompresi Lossless
Sebagian besar program kompresi lossless melakukan dua halsecara berurutan: langkah pertama menghasilkan model statistik untuk data input, dan langkah kedua menggunakan model ini untuk memasukkan data peta ke urutan bit sedemikian rupa sehingga"kemungkinan" (misalnya sering dijumpai) data akan menghasilkan output lebih pendek dari "mustahil" data.
Encoding utama yang digunakan untuk menghasilkan urutan bit Huffman Coding (juga digunakan oleh deflate) dan aritmatika coding. Arithmetic coding mencapai tingkat kompresi dekat dengan terbaik untuk model statistik tertentu, yang diberikan oleh entropi informasi, sedangkan kompresi Huffman lebih sederhana dan lebih cepat tetapi menghasilkan hasil yang buruk untuk model yang berhubungan dengan simbol probabilitas mendekati 1.
ada dua cara membangun model statistik: dalam model statis, data dianalisa dan model dibangun, maka model ini disimpan dengan data terkompresi. Pendekatan ini sederhana dan modular,namun memiliki kelemahan yang model itu sendiri bisa mahal untukmenyimpan, dan juga bahwa memaksa sebuah model tunggal yangakan digunakan untuk semua data yang dikompresi, dan berkinerjaburuk pada file berisi data heterogen. Adaptif model model dinamis update sebagai data yang dikompresi. Baik encoder dan decoder dimulai dengan model sepele, menghasilkan kompresi miskin dataawal, tetapi karena mereka belajar lebih banyak tentang data kinerja membaik. jenis kompresi paling populer digunakan dalam praktik sekarang menggunakan coders adaptif.
Metode Kompresi Lossless
Metode kompresi Lossless dapat dikategorikan menurut jenis datayang dirancang untuk kompres. Sementara, pada prinsipnya, tujuan algoritma kompresi lossless-umum (general purpose yang berarti bahwa mereka dapat memampatkan bitstring ada) dapat digunakanpada setiap jenis data, banyak yang tidak mampu mencapai kompresi yang signifikan pada data yang tidak bentuk yang mereka dirancang untuk kompres. Banyak teknik kompresi lossless yang digunakan untuk teks juga bekerja cukup baik untuk gambar terindex.
Transform Coding - Discrete Cosine Transform (DCT)
Discrete Cosine Transform (DCT) biasa digunakan untuk mengubah sebuah sinyal menjadi komponen frekuensi dasarnya. DCT mempunyai dua sifat utama untuk kompresi citra dan video yaitu :
Mengkonsentrasikan energi citra ke dalam sejumlah kecil koefisien (energi compaction).
Meminimalkan saling ketergantungan diantara koefisien-koefisien (decorrelation).DCT biasanya digunakan pada kompresi image JPEG
Transform Coding – Karhunen-Loève Transform
Metode yang digunakan untuk mentransfer sejumlah besar data yang berdimensi besar pada suatu sub-ruang berdimensi kecil.
Ringkasan utk mendapatkan transformasi [F]:
Cari covariance matrix Cov([f])
Cari eigenvalue dan eigenvector dari Cov([f]) dan dapatkan matrix transformasi T dari normalized eigen vector
Cari vektor transformasi [F]
WBC – Continous Transform
Metode dekomposisi waktu-frekuensi yang ditujukan untuk mengkarakterisasi respon pergerakan pada frekuensi tertentu. Menggunakan metode Fast Fouhrier Transform dari setiap window waktu secara terus menerus sehingga diperoleh gambaran kisaran frekuensi
WBC – Discrete Transform
Menggunakan high pass filtering dan low pass filtering. High pass filtering adalah konsep filtering yang meninggikan frekuensi, sedangkan low pass filtering adalah konsep yang melemahkan frekuensi.
Lossy Vs. Lossless
• Keuntungan dari metode lossy atas lossless adalah dalam beberapa kasus metode lossy dapat menghasilkan file kompresi yang lebih kecil dibandingkan dengan metode lossless yang ada, ketika masih memenuhi persyaratan aplikasi.
• Metode lossy sering digunakan untuk mengkompresi suara, gambar dan video. karena data tersebut dimaksudkan kepada human interpretation dimana pikiran dapat dengan mudah “mengisi bagian-bagian yang kosong” atau melihat kesalahan masa lalu sangat kecil atau inkonsistensi-idealnya lossy adalah kompresi transparan, yg dapat diverifikasi dengan tes ABX. Sedangkan lossless digunakan untuk mengkompresi data untuk diterima ditujuan dalam kondisi asli seperti dokumen teks.
• Lossy akan mengalami generation loss pada data sedangkan pada lossless tidak terjadi karena data yang hasil dekompresi sama dengan data asli.
Minggu, 21 Oktober 2012
Kamis, 11 Oktober 2012
Kompresi Loseless
KOMPRESI
GAMBARAN UMUM
Kompresi merupakan 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), audio (MP3, AAC, dan video (MPEG)
Secara umum ada hal yang bisa dikompresi dari data 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
** 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.
** 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.
** 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
** 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.
KOMPRESI LOSSLESS
Berdasarkan fungsinya, metode kompresi dibagi menjadi dua, metode lossy dan metode lossless. Metode Lossless merupakan suatu metode pemampatan data tanpa menghilangkan data yang dimilikinya.Data yang telah diganti dapat dikembalikan dengan ukuran dan struktur yang sama persis dengan data awal melalui proses dekompresi. Teknik ini bersifat dua arah. 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 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
- Tidak ada satupun informasi data yang hilang.
- Data dapat didekompresi dan membentuk data yang sama persis dengan aslinya (reversible).
· Kekurangan
- Rasio (perbandingan ukuran data sebelum dan sesudah) kompresi rendah.
- 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).
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)
RAR
– 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.
– 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
GAMBARAN UMUM
Kompresi merupakan 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), audio (MP3, AAC, dan video (MPEG)
Secara umum ada hal yang bisa dikompresi dari data 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
** 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.
** 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.
** 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
** 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.
KOMPRESI LOSSLESS
Berdasarkan fungsinya, metode kompresi dibagi menjadi dua, metode lossy dan metode lossless. Metode Lossless merupakan suatu metode pemampatan data tanpa menghilangkan data yang dimilikinya.Data yang telah diganti dapat dikembalikan dengan ukuran dan struktur yang sama persis dengan data awal melalui proses dekompresi. Teknik ini bersifat dua arah. 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 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
- Tidak ada satupun informasi data yang hilang.
- Data dapat didekompresi dan membentuk data yang sama persis dengan aslinya (reversible).
· Kekurangan
- Rasio (perbandingan ukuran data sebelum dan sesudah) kompresi rendah.
- 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).
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)
RAR
– 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.
– 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
Kamis, 04 Oktober 2012
Jaringan Multimedia Video dan Audio
Video merupakan teknologi untuk menangkap, merekam, memproses, dan menata ulang gambar bergerak.selain itu video juga dapat juga diartikan sebagai gabungan gambar-gambar mati yang dibaca berurutan dalam waktu dengan kecepatan tertentu. kecepatan pembacaan video disebut frame per second(fps). Apabila dimainkan dalam kecepatan yang tinggi maka tercipta ilusi gerak yang halus, semakin besar nilai frame rate maka akan semakin halus pergerakan yang ditampilkan.
Secara umum video dibedakan menjadi 2 format. yakni video analog dan video digital. Video analog contoh formatnya adalah PAL dan NTSC. konektor dari video analog ini sendiri dapat berupa RCA, VGA(Video Graphic Array) maupun S-Video. Sementara untuk Video digigal sendiri formatnya dapat berupa MOV, MPG, AVI, ASF dan lain sebagainya. konektornya juga berbeda. bisa menggunakan HDMI ataupun DVI.
Bagian yang biasanya dianggap bagian dari video adalah audio.Istilah audio biasa digunakan untuk menerangkan sistem-sistem yang berkaitan dengan proses perekaman dan transmisi yaitu sistem pengambilan/penangkapan suara, sambungan transmisi pembawa bunyi, amplifier dan lainnya.
Secara umum audio dapat dibedakan menjadi 3 jenis yakni mono, stereo dan suround. mono merupakan jenis audio Sebuah sistem dimana semua sinyal audio di mix dan diarahkan melalui satu channel audio. sementara itu stereo Memiliki 2 channel audio yang independent, dan sinyal suara yang dihasilkan memiliki level dan fase yang berbeda. lain lagi dengan suround. suround sendiri merupakan teknik untuk memperkaya kualitas reproduksi suara dari sumber audio dengan channel audio tambahan dari speaker yang mengelilingi pendengar.
seperti yang diketahui bahwa video dan audio merupakan gabungan dari urutan list yang ada. jika video berasal dari gambar, maka audio berasal dari frekuensi. jelas membutuhkan memori yang cukup besar juga. namun untuk menyiasatinya dapat menggunakan teknik kompresi. teknik ini digunakan untuk mengurangi kapasitas memori dan juga untuk mempercepat transmisi. metode yang digunakan ada 2 yakni lossy format dan loseless format. untuk lossy maka file tidak bisa kembali normal seperti semula. namun masih mirip. apabila loseless masih bisa kembali ke kondisi awal. kedua teknik ini sangat penting karena bisa membuat ukuran data menjadi lebih kecil. ketika data berukuran kecil, maka akan jauh lebih mudah ketika streaming.
Secara umum video dibedakan menjadi 2 format. yakni video analog dan video digital. Video analog contoh formatnya adalah PAL dan NTSC. konektor dari video analog ini sendiri dapat berupa RCA, VGA(Video Graphic Array) maupun S-Video. Sementara untuk Video digigal sendiri formatnya dapat berupa MOV, MPG, AVI, ASF dan lain sebagainya. konektornya juga berbeda. bisa menggunakan HDMI ataupun DVI.
Bagian yang biasanya dianggap bagian dari video adalah audio.Istilah audio biasa digunakan untuk menerangkan sistem-sistem yang berkaitan dengan proses perekaman dan transmisi yaitu sistem pengambilan/penangkapan suara, sambungan transmisi pembawa bunyi, amplifier dan lainnya.
Secara umum audio dapat dibedakan menjadi 3 jenis yakni mono, stereo dan suround. mono merupakan jenis audio Sebuah sistem dimana semua sinyal audio di mix dan diarahkan melalui satu channel audio. sementara itu stereo Memiliki 2 channel audio yang independent, dan sinyal suara yang dihasilkan memiliki level dan fase yang berbeda. lain lagi dengan suround. suround sendiri merupakan teknik untuk memperkaya kualitas reproduksi suara dari sumber audio dengan channel audio tambahan dari speaker yang mengelilingi pendengar.
seperti yang diketahui bahwa video dan audio merupakan gabungan dari urutan list yang ada. jika video berasal dari gambar, maka audio berasal dari frekuensi. jelas membutuhkan memori yang cukup besar juga. namun untuk menyiasatinya dapat menggunakan teknik kompresi. teknik ini digunakan untuk mengurangi kapasitas memori dan juga untuk mempercepat transmisi. metode yang digunakan ada 2 yakni lossy format dan loseless format. untuk lossy maka file tidak bisa kembali normal seperti semula. namun masih mirip. apabila loseless masih bisa kembali ke kondisi awal. kedua teknik ini sangat penting karena bisa membuat ukuran data menjadi lebih kecil. ketika data berukuran kecil, maka akan jauh lebih mudah ketika streaming.
Langganan:
Postingan (Atom)