Pengolahan Citra Digital – Image Compression

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 R_D: R_D = 1 – 1/C_R    dan    C_R = n₁/n₂

n₁ dan n₂: jumlah satuan informasi yang dibawa citra/data 1 dan citra/data 2.

Keterangan :

·         Bila n₁ = n₂, maka C_R = 1 dan R_D = 0 (tidak ada redundancy).

·         Bila n₂ < n₁, maka C_R mendekati tak terhingga dan R_D mendekati 1 (terjadi redundancy yang tinggi).

·         Bila n₂ > n₁, maka C_R mendekati 0 dan R_D mendekati minus tak terhingga (informasi yang dibawa data set 2 jauh lebih besar dari data set 1)

·         Bila 0 < C_R < 1 dan R_D 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,8)   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, 2^nd Edition by Gonzales