image compression - citra digital

Materi ke 5

1STIKOM Artha Buana

Image Compression

Kompresi Citra• Image umumnya terdiri dari sejumlah besar data. • Kompresi Citra dimaksudkan untuk mengurangi jumlah data (bits) yang dibutuhkan untuk mewakili citra digital. Ini dapat dikerjakan dengan mengurangi bagian yang tidak dipakai.• Kompresi Citra dibagi menjadi 2 bagian: a. Lossy (Citra hasil tidak bisa dikembalikan seperti aslinya). b. Lossless (Citra hasil dapat dikembalikan seperti aslinya).• Jika n1 adalah image asli, n2 adalah image hasil maka Relative Redudancy (RD) dari image asli adalah: RD = 1-(1/CR) Dimana : CR = n1/n2 CR disebut sebagai Compression Ratio

3STIKOM Artha Buana

Kompresi Citra (Lanjutan ….)

Ada 3 macam Redudancy Data untuk image:

• Coding Redudancy (berdasarkan code biner yang mewakili intensitas graylevel)

• Interpixel Redudancy (berdasarkan pada hubungan korelasi antar pixel yang berdekatan)

• Psychovisual Redudancy (berdasarkan pada ketidaksamaan sensitivitas mata manusia terhadap perbedaan informasi visual)

4STIKOM Artha Buana

Model Kompresi Citra

• Source Encoder membuang redudancy dari input image• Channel Encoder membantu mengontrol noise (menyediakan

beberapa level kekebalan terhadap noise).• Channel Decoder dan Source Decoder bekerja kebalikan dari proses

Encoder.

ImageAsli

Image Terkompresi

Image Rekonstruksi

5STIKOM Artha Buana

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.

6STIKOM Artha Buana

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

Source Decoder

7STIKOM Artha Buana

• Run Length Encoding.• Huffman Encoding.• Shanon Fano Encoding• Discrete Cosinus Transform

Kompresi Citra yang umum

8STIKOM Artha Buana

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

9STIKOM Artha Buana

RLE (Lanjutan ….)• 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.

10STIKOM Artha Buana

BACK

RLE (Lanjutan ….)


Shannon Fano Coding

• 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.

0

0

0

0

11

1

1A

ED

CB


Algoritma Shannon Fano

• 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 (1)Diberikan simbol: AAAAAAAAAAAAAAABBBBBBCCCCCDDDDDDEEEEEEE

Jika ditabelkan menjadi:A 15 0E 7 0B 6 1D 6 1C 5 1

Pembagian pertamaKarena menghasilkan selisih Atas dan Bawah terkecil(=5)

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


Contoh: Shannon Fano Coding (2)

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

A 15 0 0E 7 0 1B 6 1D 6 1C 5 1

Pembagian keduaUntuk membagi setengah bagian atas



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

A 15 0 0E 7 0 1B 6 1 0D 6 1 1C 5 1 1

Pembagian ketigaKarena menghasilkan selisih Atas dan Bawah terkecil(=5)



Sehingga dapat dikodekan: A = 00B = 01C = 10D = 110E = 111

A 15 0 0E 8 0 1B 5 1 0D 3 1 1 0C 2 1 1 1

Pembagian keempatMerupakan pembagian terakhir


BACK

Huffman Coding

• Hasil kompresi lebih baik dari Shannon Fano.• Sama dengan Shannon Fano: 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 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.


Huffman Coding (Lanjutan)

Tree dibentuk dengan cara:• 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 (1)

Diberikan simbol: AAAAAAAAAAAAAAABBBBBBCCCCCDDDDDDEEEEEEE

Dengan Huffman akan menghasilkan tabel sbb:

A15 A 15 A 15 A 15 EBDCA 39

E7 E 7 EB 13 EBDC 24

B6 B 6 DC 11

D6 DC 11

C5A = 0B = 101C = 111D = 110E = 100


01

01

01

01

Contoh: Huffman Coding (2) Atau dengan gambar tree:

CA B DE515 6 67

13 110 01 1

240 1

39

Root

0 1

A = 0B = 101C = 111D = 110E = 100


BACK

image compression - citra digital

Education