Pemampatan Citra Esther Wibowo ‐
[email protected] Erick Kurniawan ‐
[email protected]
Mengapa? y
MEMORI ◦ Citra memerlukan memori besar. ◦ Mis. Citra 512x512 pixel 256 warna perlu 32 KB (1 pixel = 1 byte = 8 bit) ◦ >> ukuran → >> memori
y
DUPLIKASI DATA ◦ Pixel dan tetangga punya intensitas sama → boros tempat. ◦ Bagian (region) sama → redundant
Image Compression ‐ Pemampatan Citra ≠ image encoding : pengkodean citra dalam representasi tertentu → belum tentu menghasilkan representasi memori minimal. y Image compression pasti mengurangi kebutuhan memori. y Proses : y
◦ Compression : pemampatan != bentuk bitmap ◦ Decompression : penirmampatan → bitmap
Aplikasi Pemampatan Citra y
Pengiriman data (data transmission) ◦ Kecepatan pengiriman ◦ Transfer melalui video conferencing, gambar satelit, download dari Internet, intranet dll.
y
Penyimpanan data (data storing) ◦ Kebutuhan storage space ◦ Aplikasi basis data gambar, office automation, video storage (VCD, DVD‐Video, dll.)
Kriteria Pengukuran Metode Pemampatan (1) Kecepatan waktu compression dan decompression y Kebutuhan memori y
◦ % memori sesudah dan sebelum proses pemampatan ◦ Bergantung karakteristik citra y
Format keluaran cocok untuk pengiriman dan penyimpanan data.
Kriteria Pengukuran Metode Pemampatan (2) y
Kualitas pemampatan (fidelity) ◦ Subjektif, bergantung pengamat ⎛ b ⎞ PSNR = 20 * log10 ⎜ ⎟ ⎝ rms ⎠
◦ PSNR = peak signal to noise ratio (dB) ◦ b = nilai signal terbesar rms =
N M 1 2 ( f − f ' ) ∑∑ ij ij Lebar * Tinggi i =1 j =1
◦ PSNR makin besar, pemampatan makin baik.
Pertimbangan Pemilihan Kriteria Tujuan citra dimampatkan untuk apa? y Misal : mengirim draft desain grafis ke klien → kualitas memadai, pengurangan memori menjadi prioritas kedua. y Misal : sharing citra di Internet, waktu proses pemampatan hanya 1x, proses dekompresi berkali‐kali →kecepatan kompresi tidak masalah, kecepatan dekompresi sebaiknya cepat. y
Jenis Pemampatan y
Pendekatan statistik ◦ Berdasar frekuensi kemunculan derajat keabuan. ◦ Mis. Huffman Coding
y
Pendekatan ruang ◦ Berdasar hubungan spasial antar pixel yang memiliki derajat keabuan sama : x Lokal : pixel bertetangga memiliki intensitas hampir sama x Global : pola yang berulang
◦ Mis. Run‐Length Encoding
y
Pendekatan kuantisasi ◦ Mengurangi jumlah derajat keabuan. ◦ Mis. Metode Pemampatan Kuantisasi
y
Pendekatan fraktal ◦ Berdasar kemiripan bagian dalam citra → transformasi ◦ Metode Fractal Image Compression
Klasifikasi Metode Pemampatan (1) y
Lossless ◦ Citra hasil pemampatan = citra semula, pixel per pixel → tidak ada informasi yang hilang. ◦ Nisbah (ratio) pemampatan rendah.
⎞ ⎛ ukuran citra hasil pemampatan Nisbah = 100% − ⎜ ×100% ⎟ ukuran citra semula ⎝ ⎠
◦ Untuk aplikasi dimana citra tidak boleh rusak mis: informasi medis.
Klasifikasi Metode Pemampatan (2) y
Lossy ◦ Citra hasil pemampatan hampir sama dengan citra semula. ◦ Ada informasi hilang tapi dapat ditolerir mata. ◦ Nisbah pemampatan tinggi.
Level Kompresi JPEG
Metode Huffman (1) Derajat keabuan yang sering muncul dikodekan dengan ∑ bit sedikit. y Derajat keabuan yang jarang muncul dikodekan dengan ∑ bit lebih panjang. y Algoritma: y
◦ Urutkan derajat keabuan secara ascending berdasar frekuensi kemunculan.
pk = nk / n
k = derajat keabuan pk = peluang kemunculan nk = frekuensi kemunculan n = jumlah pixel dalam citra
Metode Huffman (2) y
Algoritma Huffman (lanjutan): ◦ Frekuensi : Derajat keabuan → pohon bersimpul tunggal ◦ Gabungkan 2 buah pohon yang berfrekuensi paling kecil dalam 1 akar ◦ Ulangi hingga tercipta 1 pohon biner ◦ Beri label pada setiap sisi pohon biner. Kiri = 0, kanan = 1. ◦ Telusuri pohon biner dari akar ke daun. Barisan label sisi dari akar ke daun → kode Huffman untuk tiap derajat keabuan.
Contoh Soal Metode Huffman y
Citra 64x64 pixel dengan 8 derajat keabuan → jumlah pixel = 64*64 = 4096
0 0
1 1
1
0
1
0
1
0
Kode @ derajat keabuan : 0 = 00 4 = 1110 1 = 10 5 = 11111 2 = 01 6 = 11110 3 = 110 7 = 111100
0 0
1 1
Efektivitas Huffman y
Ukuran citra sebelum pemampatan : (64*64) * 3 bit = 12.288 bit
Ukuran citra setelah pemampatan : (790*2bit) + (1023*2bit) + (850*2bit) + (656*3bit) + (329*4bit) + (245*5bit) + (122*6bit) + (81*6bit) = 11.053 bit y Nisbah pemampatan = 10% y Makin banyak derajat keabuan, efek pemampatan makin dirasakan. y
Metode Run‐Length Encoding (RLE) Untuk citra yang memiliki kelompok‐ kelompok pixel berderajat keabuan sama. y Membuat rangkaian pasangan (p,q) untuk tiap baris pixel. p = derajat keabuan, q = jumlah pixel berurutan yang memiliki derajat keabuan yang sama. y
Contoh Soal Metode RLE y
Citra 10x10 dengan 8 derajat keabuan :
Pasangan Nilai (p,q) dengan RLE
y
Jadi semua ada 31 pasangan → 31*2=62 nilai.
Efektivitas Metode RLE y
Ukuran citra sebelum pemampatan : 100*3 bit = 300 bit
Ukuran citra setelah pemampatan : → @derajat keabuan = 3 bit → @ run length = 4 bit (31*3) + (31*4) = 217 bit y Nisbah pemampatan = 27.67% y
RLE Alternatif Lain Menyatakan seluruh baris citra menjadi sebuah baris run. y Menghitung run‐length untuk tiap derajat keabuan yang berurutan. y
1 1 1 1
2 3 1 1
1 4 3 1
1 4 3 1
1 4 3 3
1 4 5 3
1 2 1 1 1 1 1 3 4 4 4 4 1 1 3 3 3 5 1 1 1 1 3 3 (1,1) (2,1) (1,5) (3,1) (4,4) (1,2) (2,2) (5,1) (1,4) (3,2) 1 1 2 1 1 5 3 1 4 4 1 2 2 2 5 1 1 4 3 2
Kombinasi RLE + Huffman Untuk meningkatkan nisbah pemampatan. y Lakukan pemampatan RLE. y Kemudian hasilnya dimampatkan lagi dengan metode Huffman. y
Metode Kuantisasi Mengurangi jumlah derajat keabuan, mis: 256 → 16 derajat keabuan. y Algoritma : y
◦ Buat histogram citra. ◦ Tentukan n kelompok dalam histogram sehingga tiap kelompok mempunyai kira‐kira P/n dimana P = jumlah pixel citra. ◦ Nyatakan tiap kelompok dalam derajat keabuan 0 sampai n‐1 kemudian histogram masing‐masing kelompok dikodekan kembali.
Contoh Soal Kuantisasi
Kelompok Histogram Citra
Hasil Pemampatan
Efektivitas Metode Kuantisasi y
Ukuran citra sebelum pemampatan : 65*4 bit = 260 bit
Ukuran citra setelah pemampatan : 65*2 bit = 130 bit y Nisbah pemampatan = 50% y Kelemahan : banyak informasi yang hilang → diminimalkan dengan menjamin bahwa tiap kelompok memiliki jumlah pixel yang hampir sama. y
Metode Fraktal y
y
y
y y
Mencari bagian citra yang memiliki kemiripan dengan bagian lain dalam citra namun berukuran lebih besar. Menemukan matriks yang mentransformasikan bagian yang lebih besar dengan bagian yang lebih kecil. Hanya menyimpan elemen‐elemen dari sekumpulan matriks transformasi → matriks transformasi affine. Matriks affine di‐iterasi sejumlah kali terhadap sembarang citra awal. Hasil iterasi akan konvergen dengan citra semula.
