Mengapa kita memerlukan kompresi dan reduksi data citra?
1. Data Citra Umumnya berukuran besar.
Contohnya aja : misalnya saja untuk membuat halaman judul yang jumlah halamannya 1dan didalamnya terdapat logo perusahaan atau kampus, besarnya hampir sama jika kita membuat file .doc yang isinya hanya tulisan dan berlembar2.
2. Tidak praktis dalam proses penyimpanan, proses dan transmisi
3. Dengan adanya kompresi kita bisa mengurangi redundancy atau pengulangan data yang ada pada data.
Data Redundancy adalah pengulangan dari informasi yang sudah dinyatakan sebelumnya atau sudah diketahui.
Contoh aplikasi yang membutuhkan kompresi citra
· Televideo-conferencing
· Remote sensing
· Telemedical / Medical imaging
· Facsimile transmission
Ada 2 kategori Teknik Kompresi Citra :
1. Lossless Compression
Teknik yang mengkompresi data asli menjadi bentuk yang lebih kecil tanpa menghilangkan informasi
Contoh : Aplikasi biomedis
2. Lossy Compression
Teknik memperoleh data yang lebih ringkas dengan melalui suatu proses penghampiran atau approksimasi dari data asli dengan tingkat error yang masih dapat diterima
Contoh : TV Broadcast
Konsep Data Redundancy :
Relative data redundancy RD: RD = 1 - 1/CR dan CR = n1/n2
n1 dan n2: jumlah satuan informasi yang dibawa citra/data 1 dan citra/data 2.
Keterangan :
· Bila n1 = n2, maka CR = 1 dan RD = 0 (tidak ada redundancy).
· Bila n2 < n1, maka CR mendekati tak terhingga dan RD mendekati 1 (terjadi redundancy yang tinggi).
· Bila n2 > n1, maka CR mendekati 0 dan RD mendekati minus tak terhingga (informasi yang dibawa data set 2 jauh lebih besar dari data set 1)
· Bila 0 < CR < 1 dan RD rendah ( tingkat redundancy rendah).
Suatu data atau citra dikatakan telah terkompresi jika redundancy-nya dapat dikurangi
Jenis-jenis data redundancy :
- Coding Redundancy
- Interpixel Redundancy
- Phsycovisual Redundancy
Perbedaan utama antara Coding Redundancy, Interpixel Redundancy dan Psychovisual Redundancy adalah penyebab adanya data redundancy dan teknik eliminasi redundancy
n Coding redundancy : Terjadi bila suatu kode simbol yang digunakan terdiri dari sejumlah bit yang melebihi jumlah bit yang diperlukan untuk representasi setiap simbol (dalam hal ini: tingkat keabuan piksel citra). Teknik eliminasinya dengan cara mengubah pengkodean.Tingkat keabuan yang probabilitas terjadinya tinggi diberi panjang kode yang pendek, dan bila sebaliknya diberi kode yang panjang
n Interpixel redundancy : data redundancy dinyatakan dengan korelasi antar piksel dimana intensitas suatu piksel dapat diperkirakan dari intensitas piksel-piksel tetangganya. Teknik eliminasinya dengan mengubah representasi citra image. citra tidak dinyatakan dalam bentuk matriks dari intensitas piksel-pikselnya, akan tetapi dipetakan (mapping) dalam bentuk perbedaan intensitas antar piksel yang bersebelahan. Bentuk data yang dimampatkan ini bersifat reversible, artinya dapat direkonstruksi kembali menjadi citra asalnya.
Contoh Citra:
0 0 0 0 1 1 0 0
0 0 0 1 1 1 1 0
0 0 0 1 1 1 1 0
0 0 1 1 1 1 1 0
0 0 1 1 1 1 1 0
0 0 0 1 1 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
|
Run-Length Code Representation:
(0,4), (1,2), (0,2)
(0,3), (1,4), (0,1)
(0,3), (1,4), (0,1)
(0,2), (1,5), (0,1)
(0,2), (1,5), (0,1)
(0,3), (1,3), (0,3)
(0,
Informasi Yang Disimpan:
22 pairs of integers
|
n Psychovisual redundancy : redundancy terjadi karena suatu fenomena dimana intensitas keabuan yang bervariasi dilihat sebagai intensitas konstan, artinya: mata tidak mempunyai sensitivitas yang sama terhadap semua informasi yang dianggap penting dan tidak penting. Ex : kasus mach band. Teknik eliminasinya menggunakan Quantization / IGS (Improved Gray Scale) Quantization
Ada beberapa cara untuk melakukan kompresi data, algoritma yang saya pilih sekarang ini adalah Lempel-Ziv
Lempel-Ziv
Algoritma ini melakukan kompresi dengan menggunakan dictionary / kamus , dimana fragmen-fragmen dari teks digantikan dengan index yang diperoleh dari dictionary. Pendekatan ini bersifat adaptif dan efektif karena banyak karakter dapat dikodekan dengan mengacu pada string yang telah muncul sebelumnya dalam teks.
Langkah-langkah algoritma Lempel-Ziv (LZW)
1. Dictionary diinisialisasi dengan semua karakter dasar yang ada
2. P merupakan karakter pertama dalam stream karakter
3. C merupakan karakter berikutnya dalam stream karakter
4. Apakah string (P+C) terdapat dalam dictionary ?
· Jika ya,maka P = P + C (gabungkan P dan C menjadi string baru)
· Jika tidak, maka :
- Output sebuah kode untuk menggantikan String P
- Tambahkan string (P+C) ke dalam dictionary dan berikan kode berikutnya yang belum digunakan dalam dictionary untuk string tersebut
- P = C
5. Apakah masih ada karakter berikutnya dalam stream karakter ?
· Jika ya, maka kembali ke langkah 2
· Jika tidak, maka output kode yang menggantikan string P, lalu stop proses.
Contoh : string ABBABABAC
Dari contoh diatas maka kita ketahui bahwa karakter dasar dalam string diatas adalah ‘A’, ‘B’, dan‘C’, masukkan dalam dictionary secara urut (sebaiknya), sehingga dalam dictionary, kode 1 = ‘A’, kode 2 = ‘B’, kode 1 = ‘C’
Langkah-langkah :
1. Posisi-> 1, P = ‘A’ (karakter pertama), karena ‘A’ sudah ada dalam dictionary maka sekarang P = P + C (P = ‘A’ + ‘B’), jadi P sekarang adalah ‘AB’, karena ‘AB’ belum terdapat dalam dictionary maka outputnya adalah 1 <kode 1 = ‘A’>, kemudian masukkan ‘AB’ kedalam dictionary <kode 4 = ‘AB’>, lalu P = ‘B’
2. Posisi -> 2, P = ‘B’, karena B sudah ada dalam dictionary maka sekarang P = P + C (P = ‘B’ + ‘B’), jadi P sekarang adalah ‘BB’, karena ‘BB’ belum terdapat dalam dictionary maka outputnya adalah 2 <kode 2 = ‘B’>, kemudian masukkan ‘BB’ kedalam dictionary <kode 5 = ‘BB’>, lalu P = ‘B’
3. Posisi -> 3, P = ‘B’, karena B sudah ada dalam dictionary maka sekarang P = P + C (P = ‘B’ + ‘A’), jadi P sekarang adalah ‘BA’, karena ‘BA’ belum terdapat dalam dictionary maka outputnya adalah 2 <kode 2 = ‘B’>, kemudian masukkan ‘BA’ kedalam dictionary <kode 6 = ‘BA’>, lalu P = ‘A’
4. Dst
Sehingga pada akhirnya kita peroleh Dictionary :
Kode 1 = ‘A’
Kode 2 = ‘B’
Kode 3 = ‘C’
Kode 4 = ‘AB’
Kode 5 = ‘BB’
Kode 6 = ‘BA’
Kode 7 = ‘ABA’
Kode 8 = ‘ABAC’
Sehingga Outputnya adalah [1] [2] [2] [4] [7] [3]
Selain dengan menggunakan Algoritma Lempel-Ziv (LZW), kita juga dapat menggunakan Algoritma lain misalnya Huffman Code, tapi pasti smua sudah pada jago Algoritma ini
Daftar Pustaka :
Data Compression by Xin Li
‘KompresiUI.ppt’ <Fakultas Ilmu Komputer Universitas Indonesia>
‘Perbandingan Kinerja Algoritma Kompresi.pdf’
Digital Image Processing, 2nd Edition by Gonzales