Image Compression (Kompresi Citra)

Image atau gambar umumnya terdiri dari sejumlah besar data (bisa dilihat dari isi pikselnya, dimana

masing-masing piksel terdiri atas beberapa item warna, misalnya RGB, CMYK dan lain-lain).

Kompresi Citra dimaksudkan untuk mengurangi jumlah data (bits) yang dibutuhkan untuk mewakili citra digital. Ini dapat dikerjakan dengan mengurangi bagian yang tidak dipakain atau bagian-bagian data yang mengandung redudancy.

Kompresi bisa dilihat dari beberapa contoh paket yang sudah ada, misalnya Winrar, Winzip, PDF, Jpg, Png dan lain sebagainya.
Kompresi Citra dibagi menjadi 2 bagian, yaitu :     

1. Lossy (Citra hasil tidak bisa dikembalikan seperti aslinya).
2. Lossless (Citra hasil dapat dikembalikan seperti aslinya).

Jika n1 adalah image asli, n2 adalah image hasil maka Relativen Redudancy (RD) dari image asli adalah :

                    RD = 1-(1/CR)

  Dimana :     CR = n1/n2

  CR disebut sebagai Compression Ratio

Ada 3 macam Redudancy Data untuk image, yaitu :

1. Coding Redudancy (berdasarkan code biner yang mewakili intensitas graylevel)
2. Interpixel Redudancy (berdasarkan pada hubungan korelasi antar pixel yang berdekatan)
3. Psychovisual Redudancy (berdasarkan pada ketidaksamaan sensitivitas mata manusia terhadap perbedaan informasi visual)

Model Kompresi Citra

Gambar 1. Proses kompresi citra

Dari gambar 1 dapat dijelaskan bahwa :

• Source Encoder adalah membuang redudancy dari input image 
• Channel Encoder adalah membantu mengontrol noise (menyediakan beberapa level kekebalan terhadap noise). 
• Channel Decoder dan Source Decoder bekerja kebalikan dari proses Encoder.

Source Encoder

Gambar 2. Source Encoder

• Source Encoder berfungsi untuk mengurangi atau membatasi setiap coding, interpixel atau psychovisual redudancy. 
• Mapper berfungsi untuk mentransformasi data input menjadi format nonvisual, didesain untuk mengurangi redudancy antar pixel. Blok ini bersifat bolak-balik, dan mungkin mengurangi ukuran data tapi bisa juga tidak mengurangi ukuran data. 
• Quantizer mengurangi keakuratan dari Output Mapper, dalam hubungannya dengan kriteria fidelity. Blok ini mengurangi redudancy psychovisual dan biasanya tidak bisa bolak balik. 
• Symbol Encoder menciptakan code2 dengan panjang tetap/variabel yang mewakili output Quantizer. Blok ini bersifat bolak-balik.

Source Decoder

Gambar 3. Source Decoder

Source Decoder bekerja kebalikan dari Blok Source Encoder kecuali Quantizer, yang hanya berjalan 1 arah.

Beberapa Kompresi Citra yang umum, adalah sebagai berikut :

1. Run Length Encoding. 
2. Huffman Encoding. 
3. Shanon Fano Encoding 
4. Discrete Cosinus Transform

Run Length Encoding (RLE)

• RLE merupakan metode kompresi yang banyak didukung oleh format file gambar seperti: TIFF, BMP, PCX. 
• RLE bekerja dengan mengurangi ukuran fisik dengan adanya pengulangan string dari deretan karakter / byte data. 
• String perulangan ini dinamakan RUN, dan biasanya di kodekan dalam 2 byte. Byte pertama merupakan jumlah perulangan dan byte kedua adalah karakter yang diulang.

Contoh:

AAAAAAAABBBBBCDEEEEEFFFFF             25 byte uncompressed

8A5B1C1D5E5F                                                12 byte compressed

• Dari konsep sebelumnya terlihat bahwa jika data tidak bisa dikompresi (tidak ada data yang sama sacara berurutan) maka hasil kompresi memiliki ukuran data 2 x lebih besar. 
• Untuk itu ditentukan suatu Character khusus yang akan menunjukkan data berikutnya adalah merupakan data terkompresi.  --> Flag 
• Byte pertama merupakan nilai flag yang menandakan bahwa 2 byte berikutnya adalah karakter yang dikompresi. Byte kedua merupakan jumlah karakter yang dikompresi. Sedangkan byte ke tiga adalah karakter yg dikompresi. Saat proses kompresi jika nilai RUN adalah1,2 atau 3 byte, maka Karakter akan ditulis langsung ke data stream dan tidak dilakukan kompresi. Karena itu pada teknik ini jika data tidak ada yang berurutan, ukuran output sama dengan input

Gambar 4. Format kerja RLE

Shannon Fano Coding

Shannon fano adalah coding compresion yang mengikuti pola sebagai berikut :

• Tiap kode berbeda informasi bitnya. 
• Kode simbol yang probabilitasnya rendah mempunyai jumlah bit yang lebih banyak, dan yang probabilitasnya tinggi mempunyai jumlah bit yang lebih sedikit. 
• Proses decoding tetap dapat dilakukan walaupun panjang kode tiap simbol berbeda. 
• Proses kompresi terjadi karena simbol yang sering keluar dikodekan dengan jumlah bit yang sedikit.

Gambar 5. Model compresi Shannon Fano

Algoritma Shannon Fano

Rangkaian urutan perintah yang harus dilakukan dalam membuat kompresi Shannon Fano adalah sebagai berikut :

• Buat daftar probabilitas kemunculan setiap simbol. 
• Urutkan daftar dari yang paling sering keluar. 
• Bagi daftar menjadi 2, dengan ketentuan jumlah probabilitas setengah bagian atas mendekati setengah bagian bawah. 
• Setengah bagian atas diberi nilai 0 setengah bagian bawah diberi nilai 1. 
• Lakukan secara rekursif langkah terakhir pada setengah bagian atas dan setengah bagian bawah.

Contoh: Shannon Fano Coding 

Diberikan simbol :

AAAAAAAAAAAAAAABBBBBBCCCCCDDDDDDEEEEEEE

Jika ditabelkan menjadi :

Gambar 6. Tabulasi 1 

Selanjutnya semua bagian atas diberi lambang 0 dan semua bagian bawah diberi lambang 1.

Gambar 7. Tabulasi 2

Selanjutnya untuk setengah bagian atas:
Bagian atas pembagian lambang 0 dan bagian bawah pembagian diberi lambang 1.

Langkah berikutnya adalah :

Gambar 8. Tabulasi 3

Selanjutnya semua bagian atas diberi lambang 0 dan semua bagian bawah diberi lambang 1.

Gambar 9. Tabulasi 4

Sehingga dapat dikodekan : 

 A = 00

 B = 01

 C = 10

 D = 110

 E = 111

Huffman Coding

Adalah kompresi dengan hasil kompresi lebih baik dari Shannon Fano dengan uraian bentuknya adalah sebagai berikut :

• Sama halnya dengan Shannon Fano, maka Kode simbol yang probabilitasnya rendah mempunyai jumlah bit yang lebih banyak, dan yang probabilitasnya tinggi mempunyai jumlah bit yang lebih sedikit. 
• Untuk Proses decoding biasanya digunakan cara Binary Tree. 
• Kode Huffman membentuk Tree dari bawah keatas. 
• Tiap Simbol merupakan node dari ujung tree. 
• Tiap simbol memiliki bobot berupa probabilitas frekuensi kemunculan simbol.

Cara-cara membentuk TREE adalah sebagai berikut :

• Dipilih node yang masih bebas dengan bobot terendah. 
• Dibentuk node induk dari kedua node ini, bobotnya sama dengan bobot kedua anaknya. 
• Node induk digabungkan dalam daftfar node bebas lainnya (node yang telah digabung menjadi tidak bebas lagi). 
• Path dari node induk ke-anak2 nya diberi simbol 0 dan 1. 
• Pemberian simbol harus konsisten jika dibuat aturan 0 sebelah kiri, maka ketentuan ini harus berlaku sampai node bebas tinggal 1. 
• Ulangi langkah diatas sampai node bebas tinggal 1 (=root)

Contoh: Huffman Coding

Diberikan simbol:

AAAAAAAAAAAAAAABBBBBBCCCCCDDDDDDEEEEEEE

Dengan Huffman akan menghasilkan tabel sebagai berikut :

Gambar 10.  Proses tabulasi Huffman coding

Atau dengan cara tree sebagai berikut :

Gambar 10. Huffman Tree

Materi presentasi dapat didownload pada link di bawah :

Materi Kompresi Citra - 4 Shared

Demikian sedikit materi tentang kompresi citra dari saya.