TEKNIK PENGOLAHAN CITRA Kuliah 13 – Kompresi Citra
Indah Susilawati, S.T., M.Eng.
Program Studi Teknik Informatika/Sistem Informasi Fakultas Teknologi Informasi Universitas Mercu Buana Yogyakarta 2015
KULIAH 13 TEKNIK PENGOLAHAN CITRA KOMPRESI CITRA Kompresi citra dilakukan untuk mengurangi jumlah atau besarnya data yang digunakan untuk menyatakan (menyimpan) suatu citra digital. Hal ini bisa dicapai dengan menghilangkan satu atau lebih dari tiga redundansi data yaitu: 1. Redundansi coding (penyandian); yang dihasilkan oleh karena digunakannya coding atau penyandian yang tidak optimal. 2. Redundansi interpiksel; yang dihasilkan dari korelasi antara piksel-piksel pada sebuah citra. 3. Redundansi psikovisual; yaitu dihasilkan oleh data yang tidak penting bagi sistem visual manusia. Sistem kompresi citra terdiri atas dua blok dasar yaitu encoder (penyandi) dan decoder (pengawa-sandi). Perhatikan gambar berikut.
Citra f(x,y) sebagai input blok encoder yang akan menghasilkan serangkaian simbol yang akan digunakan untuk merepresentasikan data (dengan cara yang baru). Jika n1 dan n2 adalah jumlah bit yang digunakan pada citra asli dan citra hasil kompresi, maka didefinisikan rasio kompresi sebagai:
Ratio kompresi 10 (atau 10:1) menunjukkan bahwa citra asli mempunyai 10 informasi bit untuk setiap 1 bit pada citra hasil kompresi.
Redundansi Coding Misalkan terdapat variabel random diskret yang nilainya dari 0 hingga 255, maka dengan coding 8 bit dapat diperoleh hasil sebagai berikut: 0 0000 0000 1 0000 0001 … 255 1111 1111
Jika coding ini digunakan untuk citra, maka dalam suatu citra tertentu satu nilai variabel (= nilai piksel) kemungkinan akan muncul berulang-ulang. Dari kenyataan ini dapat dilakukan coding dengan jumlah bit yang tidak tetap (variabel = berubah-ubah); dimana nilai piksel yang sering muncul disandikan menggunakan jumlah bit yang lebih sedikit. Pada contoh di atas digunakan jumlah bit yang tetap yaitu 8 bit.
Contoh: Akan dibuat coding dengan jumlah bit tetap dan tidak tetap untuk variabel random diskret yang mempunyai nilai 0 – 3. Probabilitas kemunculan nilai 0, 1, 2, 3 berturut-turut adalah 0,2; 0,4; 0,3; 0,1. Berikut adalah ilustrasi coding yang dapat digunakan.
Terlihat bahwa pada coding dengan jumlah bit yang tidak tetap (variable code) digunakan jumlah bit yang berbeda-beda tergantung pada besarnya probabilitas
kemunculan setiap nilai piksel. Nilai piksel yang paling sering muncul (probabilitas tinggi) akan disandikan dengan jumlah bit yang paling sedikit.
Huffman Coding Penyandian (coding) Huffman menggunakan prinsip penggunaan sandi (code) yang optimal dengan mengurangi redundansi coding. Sandi Huffman dapat digunakan untuk kompresi citra dengan prinsip yang serupa, misalnya pada format citra GIF. Langkah-langkah kompresi citra menggunakan sandi Huffman adalah sebagai berikut. 1. Baca nilai gray level citra yang akan dikompresi. 2. Ubahlah menjadi vektor, dan kemudian hitunglah probabilitas kemunculan setiap simbol (nilai gray level). Untuk kemudahan, urutkan dari nilai probabilitas terbesar hingga yang paling kecil. Dua simbol yang mempunyai probabilitas terkecil akan digabung untuk proses reduksi. 3. Buat sandi untuk setiap simbol (gray level), dimulai dari yang paling kiri hingga paling kanan (arah balik). Pemilihan bit “0” atau “1” sifatnya sebarang asalkan dapat menyandikan secara unik untuk setiap simbol yang ada.
Ilustrasi: Akan disandikan vektor yang terdiri dari 4 simbol yaitu a1, a2, a3, dan a4 dengan probabilitas kemunculan masing-masing berturut-turut adalah 0,1875; 0,5; 0,125; dan 0,1875. Maka penyandian Huffman akan membentuk reduksi sebagai berikut.
Sandi asli
Reduksi
Simbol
Probabilitas
1
2
a2
0,5
0,5
0,5
a4
0,1875
0,3125
0,5
a1
0,1875
0,1875
a3
0,125
Dan pada tabel berikutnya adalah hasil penyandian berdasarkan reduksi di atas (dengan arah balik).
Sandi asli
Reduksi
Simbol
Probabilitas
Sandi (code)
1
2
a2
0,5
1
0,5
1
0,5
1
a4
0,1875
00
0,3125
01
0,5
0
a1
0,1875
011
0,1875
00
a3
0,125
010
Atau dapat dinyatakan hasil sandi Huffman adalah sebagai berikut:
Sandi asli Sandi Huffman
Simbol
Probabilitas
a2
0,5
1
a4
0,1875
00
a1
0,1875
011
a3
0,125
010
Perhatikan bahwa simbol dinyatakan dalam sandi Huffman dengan jumlah bit yang berbeda; simbol dengan probabilitas kemunculan tertinggi disandikan dengan jumlah bit yang paling sedikit.
Contoh: Sebuah matriks 4x4 yang diperoleh dari cropping citra dinyatakan sebagai berikut. 119 123 I 119 107
123 168 119 119 168 168 119 107 119 107 119 119
Maka dari matriks tersebut dapat dibuat vektor: J = [119 123 119 107 123 119 119 107 168 168 107 119 119 168 119 119] Dan probabilitas kemunculan setiap simbol gray level-nya dapat dihitung sebagai berikut.
Simbol gray level
Jumlah kemunculan
Probabilitas kemunculan
119
8
8/16 = 0,5
168
3
3/16 = 0,1875
107
3
3/16 = 0,1875
123
2
2/16 = 0,125
Dengan cara yang sama maka dihasilkan sandi Huffman sebagai berikut.
Sandi asli Simbol
Probabilitas
Sandi Huffman
119
0,5
1
168
0,1875
00
107
0,1875
011
123
0,125
010
Sehingga vektor J di atas jika disandikan dengan sandi Huffman menjadi: JHuffman = [1 010 1 011 010 1 1 011 00 00 011 1 1 00 1 1] 29 bit Jika tanpa sandi Huffman, maka matriks 4x4 akan dinyatakan dengan 16x8 = 128 bit. Sandi Huffman dapat dikembalikan ke sandi semula dengan cara konversi langsung menggunakan tabel di atas. 1 010 1 011 010 1
1 011 00 00 011 1
1 00
1
1
119 123 119 107 123 119 119 107 168 168 107 119 119 168 119 119
Redundansi Interpiksel Run Length Encoding (RLE) RLE didasarkan pada prinsip yang sederhana: menyandikan string “0” dan “1” dengan cara menuliskan jumlah pengulangannya dalam string tersebut. RLE menjadi standart dalam transmisi faksimili dan juga digunakan dalam kompresi standart JPEG. Untuk citra biner, ada
banyak cara implementasi RLE misalnya dengan menyandikan setiap baris secara terpisah, dimulai dari jumlah bit “0”. Misalnya pada contoh berikut ini.
Maka akan disandikan sebagai:
Cara lain adalah dengan menyandikan setiap baris sebagai sebuah pasangan bilangan; bilangan pertama menyatakan posisi awal deretan bit “1” dan bilangan kedua menyatakan panjang deretan. Dengan cara ini maka citra biner di atas dapat disandikan sebagai:
Citra aras keabuan (gray scale) dapat disandikan dalam RLE dengan cara memecahnya menjadi beberapa bit plane. Misalnya citra aras keabuan berikut yang dinyatakan dengan 4 bit.
Maka terdapat 4 bit plane (bp) yaitu:
bp ke-0
bp ke-1
bp ke-2
bp ke-3
Bit plane inilah yang kemudian disandikan menggunakan RLE.
Permasalahan dengan bit plane adalah bahwa perubahan kecil pada nilai gray level dapat menyebabkan perubahan yang signifikan dalam bit-bit-nya. Misalkan perubahan dari nilai 7 ke 8 menyebabkan perubahan pada semua bit-nya karena string berubah dari 0111 menjadi 1000. Hal yang semakin buruk terjadi jika digunakan representasi gray level 8 bit. Supaya efektif maka
diupayakan terdapat deretan panjang dari gray level yang serupa (sama) sehingga dengan demikian akan diperoleh rasio kompresi yang baik.
Untuk mencapai hal ini, maka dapat disandikan nilai gray level-nya dengan cara yang lain yang disebut gray code. Dalam sandi gray code, pada setiap perubahan nilai gray level yang satu ke nilai gray level yang berikutnya maka hanya ada satu bit yang berubah. Perhatikan gray code untuk 4 bit berikut ini; bandingkan dengan sandi binernya.
Gray Level
Gray Code
Binary Code
0
0000
0000
1
0001
0001
2
0011
0010
3
0010
0011
4
0110
0100
5
0111
0101
6
0101
0110
7
0100
0111
8
1100
1000
9
1110
1001
10
1111
1010
11
1110
1011
12
1010
1100
13
1011
1101
14
1001
1110
15
1000
1111
Perhatikan perubahan yang diperoleh untuk citra gray level berikut. citra
sandi biner
sandi gray code
Bit plane yang diperoleh dari sandi biner adalah:
bp ke-0
bp ke-1
bp ke-2
bp ke-3
Bit plane yang diperoleh dari sandi gray code adalah:
bp ke-0
bp ke-1
bp ke-2
bp ke-3
Kompresi bit plane ke-0 dapat dinyatakan dengan: (4) (4) (4) (4)
Kompresi juga bisa dilakukan dengan cara menyatakannya sebagai: bit-penanda jumlah-perulangan code
sehingga bit plane ke-0 dapat dinyatakan dengan: 1110
0100
0000 1110 0100 0000
bit penanda perulangan = 4
sandi = 0000
Terlihat bahwa code aslinya dinyatakan dalam 4x4 bit = 16 bit, kemudian dikompresi menjadi 3x4 bit = 12 bit. Semakin banyak perulangan yang ada maka rasio kompresi yang dapat dicapai menjadi lebih besar pula. Bagaimana untuk bit plane yang lain?
Homeworks
1. Sandikan dengan sandi Huffman
2. Sandikan dengan sandi Huffman
3. Sandikan dengan sandi RLE
4. Sandikan dengan sandi RLE
