Image Compression (Bp Aziz) Dirangkum oleh: Eko Zulkaryanto (http://zulkaryanto.wordpress.com) Computer Science – Bogor Agricultural University (http://www.ipb.ac.id)
•
Sampling dan kuantisasi citra 2D akan menghasilkan data yang cukup sangat besar. • Besarnya data ini akan sangat menghambat dalam proses penyimpanan maupun pengiriman (transmisi). • Dengan alasan itulah kompresi diterapkan 1. Redudansi data • Kompresi citra bertujuan untuk mengurangi jumlah data yang dibutuhkan untuk merepresentasikan citra. • Kompresi dilakukan sebelum menyimpan atau sebelum mentransmisikan data citra • Selanjutnya, sebelum data citra dibuka lagi atau diterima, data tersebut didekompresi sehingga diperoleh citra asli atau pendekatannya • Dasar dari kompresi citra adalah membuang data yang redundan • Jika n1 dan n2 menyatakan banyaknya unit pembawa informasi (biasanya bit) pada citra asli dan citra yang dikodekan, maka dapat dihitung rasio kompresi sebagai CR = n1/ n2 • Nilai CR = 10, berarti setiap 10 bit pada citra asli diwakili oleh 1 bit pada citra yang dikompresi • Citra yang dikompresi dengan encoder, dapat dibuka kembali menggunakan decoder. Citra ini kita namakan citra rekonstruksi. • Citra rekonstruksi bisa berupa citra yang sama persis dengan citra asli atau bisa citra pendekatan • Kompresi yang menghasilkan citra rekonstruksi yang sama persis dengan citra asli disebut lossless compression • Bila citra rekonstruksi merupakan pendekatan terhadap citra asli, kompresinya disebut lossy compression Error untuk lossy compression
• Langkah-langkah dalam penerapan huffman coding: 1. Mengurutkan peluang pk(rk) dari nilai terkecil 2. Menjumlahkan 2 nilai peluang terkecil menjadi nilai peluang yang baru 3. Langkah 1 dan 2 diulangi sampai tidak ada lagi nilai peluang yang dapat dijumlahkan 4. Membuat kode berdasarkan hasil dari langkah 1 sampai dengan 3
Houffman Coding • The idea of Human coding is simple. • Rather than using a fixed length code (8 bits) to represent the grey values in an image, we use a variable length code, with smaller length codes corresponding to more probable grey values. • A small example will make this clear. • Suppose we have a 2-bit greyscale image with only four grey levels: 0, 1, 2, 3, with the probabilities 0.2, 0.4, 0.3 and 0.1 respectively. • That is, 20% of pixels in the image have grey value 50; 40% have grey value 100, and so on. • The following table shows fixed length and variable length codes for this image:
•
3 jenis redudansi data: – Coding redudancy – Interpixel redudancy – Psychovisual redudancy Kompresi data merupakan usaha untuk mengurangi satu atau beberapa redudansi tersebut 1.1. coding redudancy • Misal terdapat sebuah citra berukuran M x N dan nilai peluang tiap gray level-nya adalah • dengan L : banyaknya gray level nk : banyaknya gray level ke-k n : banyaknya piksel total • Jika jumlah bit yang digunakan untuk merepresentasikan nilai rk adalah l(rk ), maka rata-rata banyaknya bit yang dibutuhkan untuk merepresentasikan tiap piksel adalah • jumlah total bit yang diperlukan untuk citra tersebut adalah MNLavg
•
Dengan nilai CR = 1,103 berarti citra tersebut memiliki simbol kode (bit) yang lebih banyak daripada yang dibutuhkannya. Citra seperti ini dikatakan memiliki coding redudancy. • Metode kompresi yang bertujuan untuk mengatasi coding redudancy antara lain variable-length coding. • Salah satu contoh variable-length coding adalah huffman coding Huffman coding
• • •
•
Now consider how this image has been compressed. Each grey value has its own unique identifying code. The average number of bits per pixel can be easily calculated as the expected value (in a probabilistic sense):
Notice that the longest code words are associated with the lowest probabilities. • This average is indeed smaller than 2. • To obtain the Human code for a given image we proceed as follows: 1. Determine the probabilities of each grey value in the image. 2. Form a binary tree by adding probabilities two at a time, always taking the two lowest available values. 3. Now assign 0 and 1 arbitrarily to each branch of the tree from its apex. 4. Read the codes from the top down • To see how this works, consider the example of a 3-bit greyscale image (so the grey values are 0 - 7) with the following probabilities:
• • •
Dengan A(∆n) Interpixel redudancy disebut juga spatial redudancy Salah satu metode kompresi citra untuk menghilangkan interpixel redudancy adalah run-length coding • Misalkan sebuah citra dengan gray level berikut 4444433333377722222 222222211111 1166666 ... • Maka run-length coding dari baris ke-1 (4,5)(3,6)(7,3)(2,5) • Maka run-length coding dari baris ke-2 (2,7)(1,7)(6,5) Run length encoding • Run length encoding (RLE) is based on a simple idea: to encode strings of zeros and ones by the number of repetitions in each string. • RLE has become a standard in facsimile transmission.
• • • •
As above, we can evaluate the average number of bits per pixel as an expected value:
• •
• • • • • • • •
Greyscale images can be encoded by breaking them up into their bit planes To give a simple example, consider the following 4-bit image and its binary representation:
Human codes are uniquely decodable, in that a string can be decoded in only one way. For example, consider the string 11011100000100111110 to be decoded with the Human code generated above. There is no code word 1, or 11, so we may take the rst three bits 110 as being the code for grey value 3. Notice also that no other code word begins with this string. For the next few bits, 1110 is a code word; no other begins with this string, and no other smaller string is a codeword. So we can decode this string as grey level 4. Continuing in this way we obtain:
1.2. interpixel redudancy • Pada citra yang menampilkan obyek yang monoton, nilai gray level pixel tetangga dapat diduga. • Apabila nilai gray level pixel tetangga dapat diduga, mengapa harus disimpan? • Salah satu cara mengukur kesamaan gray level pixel tetangga adalah dengan menghitung koefisien autokorelasi • Semakin tinggi koefisien autokorelasi, semakin mudah menduga gray level pixel tetangga • Citra yang memiliki koefisien autokorelasi tinggi disebut memiliki interpixel redudancy
(n) •
For a binary image, there are many different implementations of RLE; one method is to encode each line separately, starting with the number of 0's. Another method [14] is to encode each row as a list of pairs of numbers; the rst number in each pair given the starting position of a run of 1's, and the second number its length. So the above binary image would have the encoding
A(n) A(0)
Rumus koefisien autokorelasi adalah
A(n)
1 N n
N 1 n
y 0
f ( x, y) f ( x, y n)
1.3. Psychovisual redudancy • Tidak setiap detil citra dapat ditangkap oleh mata manusia. Ada sebagian informasi dalam citra yang sangat penting dalam arti tampak nyata oleh mata manusia, namun ada juga yang tidak penting. Artinya kalau informasi tersebut tidak ada, citra tidak nampak berbeda bagi mata manusia. • Informasi yang kurang penting itulah yang disebut psychovisual redudancy. • Penghilangan sebagian informasi yang tidak penting tersebut dinamakan kuantisasi. • Kuantisasi juga berarti pemetaan input dengan selang nilai yang lebar ke output dengan selang nilai yang lebih sempit • Kuantisasi bersifat irreversible dan merupakan lossy compression. • Sebagai contoh, citra dengan 256 gray level dikompresi menjadi citra dengan 16 gray level 2. Kompresi JPEG
KOMPRESI JPEG
KOMPRESI JPEG 2000
•
Kompresi Citra (oleh Ibu Yeni) Kompresi Citra adalah aplikasi kompresi data yang dilakukan terhadap citra digital dengan tujuan untuk mengurangi redundansi dari data-data yang terdapat dalam citra sehingga dapat disimpan atau ditransmisikan secara efisien.
Run Length Encoding (RLE) Contoh 1 Citra biner: 00000 00000 00000 00000 00000 00000 01000 00000 Total = 50 bit
00010 00000
Kode string 0 dan 1 dikodekan menjadi (format : kode(jumlah frekuensi)): 0(23) 1(1) 0(12) 1(1) 0(13) Jika untuk menyimpan nilai jumlah frekuensi membutuhkan 5 bit untuk penyimpanan dan kode string membutuhkan 1 bit, maka diperlukan kapasitas sebesar : (1*5) + (5*5) = 30 bit.
Teknik Kompresi Citra (1) • Lossy Compression : – Ukuran file citra menjadi lebih kecil dengan menghilangkan beberapa informasi dalam citra asli. – Teknik ini mengubah detail dan warna pada file citra menjadi lebih sederhana tanpa terlihat perbedaan yang mencolok dalam pandangan manusia, sehingga ukurannya menjadi lebih kecil. – Biasanya digunakan pada citra foto atau image lain yang tidak terlalu memerlukan detail citra, dimana kehilangan bit rate foto tidak berpengaruh pada citra. – Beberapa teknik lossy – Color reduction : untuk warna-warna tertentu yang mayoritas dimana informasi warna disimpan dalam color palette. – Chroma subsampling : teknik yang memanfaatkan fakta bahwa mata manusia merasa brightness (luminance) lebih berpengaruh daripada warna (chrominance) itu sendiri, maka dilakukan pengurangan resolusi warna dengan disampling ulang. Biasanya digunakan pada sinyal YUV. – Chorma Subsampling terdiri dari 3 komponen : – Y (luminance) : U (CBlue) : V (CRed) Downsampling • The human eye can see more detail in the Y component (brightness) than in Cb (blue) and Cr (red). Using this knowledge, encoders can be designed to compress images more efficiently. (http://en.wikipedia.org) • Transformasi warna dari RGB ke ruang warna (color space) dinamakan YCbCr. • Pengurangan komponen Cb dan Cr dinamakan "downsampling" atau "chroma subsampling“ • Downsampling the chroma components menghemat 33% atau 50% space yang digunakan image. Contoh Downsampling • Rasio downsampling pada JPEG adalah 4:4:4 (no downsampling), 4:2:2 (reduce by factor of 2 in horizontal direction), dan 4:2:0 (reduce by factor of 2 in horizontal and vertical directions).
• –
–
Transform coding : menggunakan Fourier Transform seperti DCT (Discrete Cosine Transform). Fractal Compression : adalah suatu metode lossy untuk mengkompresi citra dengan menggunakan kurva fractal. Sangat cocok untuk citra natural seperti pepohonan, pakis, pegunungan, dan awan. Fractal Compression bersandar pada fakta bahwa dalam sebuah image, terdapat bagian-bagian image yang menyerupai bagian image yang lain.
–
Proses kompresi Fractal lebih lambat daripada JPEG sedangkan proses dekompresinya sama. Hal-Hal Penting Dalam Kompresi Citra • Scalability/Progressive Coding/Embedded Bitstream – Adalah kualitas dari hasil proses pengkompresian citra karena manipulasi bitstream tanpa adanya dekompresi atau rekompresi. – Biasanya dikenal pada loseless codec. – Contohnya pada saat preview image sementara image tersebut didownload. Semakin baik scalability, makin bagus preview image. – Tipe scalability : – Quality progressive : dimana image dikompres secara perlahanlahan dengan penurunan kualitasnya. – Resolution progressive : dimana image dikompresi dengan mengenkode resolusi image yang lebih rendah terlebih dahulu baru kemudian ke resolusi yang lebih tinggi. – Component progressive : dimana image dikompresi berdasarkan komponennya, pertama mengenkode komponen grey baru kemudian komponen warnanya. – Region of Interest Coding : daerah-daerah tertentu dienkode dengan kualitas yang lebih tinggi daripada yang lain. – Meta Information : image yang dikompres juga dapat memiliki meta information seperti statistik warna, tekstur, small preview image, dan author atau copyright information Algoritma Kompresi/Dekompresi Citra Algoritma umum untuk kompresi image adalah : 1. Menentukan bitrate dan toleransi distorsi image dari inputan user. 2. Pembagian data image ke dalam bagian-bagian tertentu sesuai dengan tingkat kepentingan yang ada (classifying). Menggunakan salah satu teknik : DWT (Discreate Wavelet Transform) : mencari frekuensi nilai pixel masing-masing, menggabungkannya menjadi satu dan mengelompokkannya sebagai berikut:
• – – –
• – – – –
Dimana LL : Low Low Frequency (most importance) HL : High Low Frequency (lesser importance) LH : Low High Frequency (more lesser importance) HH : High High Frequency (most less importance) • Hasil dekomposisi 3 level decomposition
– – • • –
3. Pembagian bit-bit di dalam masing-masing bagian yang ada (bit allocation). 4. Lakukan kuantisasi (quantization). Kuantisasi Scalar : data-data dikuantisasi sendiri-sendiri Kuantisasi Vector : data-data dikuantisasi sebagai suatu himpunan nilai-nilai vektor yang diperlakukan sebagai suatu kesatuan. 5. Lakukan pengenkodingan untuk masing-masing bagian yang sudah dikuantisasi tadi dengan menggunakan teknik entropy coding (huffman dan aritmatik) dan menuliskannya ke dalam file hasil.
• Sedangkan algoritma umum dekompresi image adalah : – 1. Baca data hasil kompresi menggunakan entropy dekoder. – 2. Dekuantisasi data. – 3. Rebuild image. Beberapa Metode Kompresi Citra
Teknik Kompresi GIF • GIF (Graphic Interchange Format) dibuat oleh Compuserve pada tahun 1987 untuk menyimpan berbagai file bitmap menjadi file lain yang mudah diubah dan ditransmisikan pada jaringan komputer. • GIF merupakan format citra web yang tertua yang mendukung kedalaman warna sampai 8 bit (256 warna), menggunakan 4 langkah interlacing, mendukung transparency, dan mampu menyimpan banyak image dalam 1 file. • Byte ordering : LSB – MSB Interlacing Interlacing separates the odd and even lines and transmits them separately. It allows the overall frame rate to be half what it would need to be if the whole display were delivered progressively. Thus, it reduces the bandwidth required to 50% and is therefore a form of compression.
Struktur file GIF • Header : menyimpan informasi identitas file GIF (3 bytes, harus string “GIF“) dan versinya (3 bytes, harus string “87a“ or “89b“) • Global Screen Descriptor (GSD) : mendefinisikan logical screen area dimana masing-masing file GIF ditampilkan.
•
Global Color Table : masing-masing image dalam GIF dapat menggunakan global color table atau tabel warnanya sendirisendiri. Penggunaan GCT akan memperkecil ukuran file GIF. • Image1, Image2, Image3, ... Image-n : dimana masing-masing image memiliki struktur blok sendiri-sendiri dan terminator antar file. • Trailer : Akhir dari sebuah file GIF • Kompresi GIF menggunakan teknik LZW : gambar GIF yang berpola horizontal dan memiliki perubahan warna yang sedikit, serta tidak bernoise akan menghasilkan hasil kompresan yang baik. Kompresi LZW (Lempel, Ziv dan Welch) pada GIF • Proses encoding yang mencari rangkaian pixel yang sama pada gambar. Pola yang lebih sering muncul mendapatkan sebuah kode yang mewakili rangkaian tersebut dalam file terkompresi.
Format file GIF • GIF87a : mendukung interlacing dan mampu manyimpan beberapa image dalam 1 file, ditemukan tahun 1987 dan menjadi standar. • GIF89a : kelanjutan dari 87a dan ditambahkan dengan dukungan transparency, mendukung text, dan animasi. Animated GIF • Animated GIF : tidak ada standar bagaimana harus ditampilkan sehingga umumnya image viewer hanya akan menampilkan image pertama dari file GIF. Animated GIF memiliki informasi berapa kali harus diloop. • Tidak semua bagian dalam animated GIF ditampilkan kembali, hanya bagian yang berubah saja yang ditampilkan kembali. JPEG •
JPEG (Joint Photograpic Experts Group) menggunakan teknik kompresi lossy sehingga sulit untuk proses pengeditan. • JPEG cocok untuk citra pemandangan (natural generated image), tidak cocok untuk citra yang mengandung banyak garis, ketajaman warna, dan computer generated image JPEG Compression Models • Sequential : kompresi dilakukan secara top-down, left-right menggunakan proses single-scan dan algoritma Huffman Encoding 8 bit secara sekuensial.
•
Progressive : kompresi dilakukan dengan multiple-scan secara progresif, sehingga kita dapat mengira-ngira gambar yang akan kita download.
Hierarchical : super-progressive mode, dimana image akan dipecah-pecah menjadi sub image yang disebut frame. Frame pertama akan membentuk image dalam resolusi rendah hingga berangsur-angsur ke resolusi tinggi. • Loseless (JPEG-LS) : exact image Teknik Kompresi JPEG • JPEG merupakan nama teknik kompresi, sedangkan nama format filenya adalah JFIF (JPEG File Interchange Format) • Tingkat kompresi yang baik untuk JPEG adalah 10:1-20:1 untuk citra foto, 30:1-50:1 untuk citra web, dan 60:1-100:1 untuk kualitas rendah seperti citra untuk ponsel. • Byte order : MSB-LSB JPEG
Tahapan Kompresi JPEG • Sampling : adalah proses pengkonversian data pixel dari RGB ke YUV/YIQ dan dilakukan down sampling. Biasanya sampling dilakukan per 8x8 blok, semakin banyak blok yang dipakai makin bagus kualitas sampling yang dihasilkan. • DCT (Discreate Cosine Transform) : hasil dari proses sampling akan digunakan sebagai inputan proses DCT, dimana blok 8x8 pixels akan diubah menjadi fungsi matriks cosinus • Quantization : proses membersihkan koefisien DCT yang tidak penting untuk pembentukan image baru. Hal ini yang menyebabkan JPEG bersifat lossy. • Entropy Coding : proses penggunaan algoritma entropy, misalnya Huffman atau Aritmatik untuk mengenkodekan koefisien hasil proses DCT yang akan mengeliminasi nilai-nilai matriks yang bernilai nol secara zig-zag order. • Baseline sequential JPEG encoding and decoding processes
Step 1: Picture Preparation (a) • Color space transformation First, the image is converted from RGB into a different color space called YCbCr. This is the same as the color space used by PAL, MAC and Digital color television transmission. • The Y component represents the brightness of a pixel • The Cb and Cr components together represent the chrominance
Assign more bits to Y, less bits to Cb and Cr
475 x 330 x 3 = 157 KB
luminance RGB Components
Step 1: Picture Preparation (b) Downsampling – The human eye can see more detail in the Y component than in Cb and Cr. Using this knowledge, encoders can be designed to compress images more efficiently. – The above transformation enables the next step, which is to reduce the Cb and Cr components (called "downsampling" or "chroma subsampling"). – Typically each group of 4 pixels would be sampled with 4 values for Y and only 1 each for U & V (sampling ratio of 4:1:1). – For the rest of the compression process, Y, Cb and Cr are processed separately and in a very similar manner. Step 1: Picture Preparation (b) • Downsampling – Original: 12 blocks. – Sampled: 4 + 1 + 1 = 6 blocks. – Compression ratio = 50%. – There is 75% lost in chrominance components – For the rest of the compression process, Y, Cb and Cr are processed separately and in a very similar manner. Step 2: Picture Processing • Discrete Cosine Transform – Next, each component (Y, Cb, Cr) of the image is "tiled" into sections of eight by eight pixels each, then each tile is converted to frequency space using a two-dimensional forward discrete cosine transform. – Within the MCU, each component is processed separately one 8x8 block at a time. – The luminance block is shifted from numbers 0..255 to numbers –128..127 by subtracting 128. – Chrominance values are already in the range –128..127. The 64 (8 X 8) DCT Basis Functions • Each 8x8 block can be looked at as a weighted sum of these basis functions. • The process of 2D DCT is also the process of finding those weights.
Y U V (Y Cb Cr) Components
Assign more bits to Y, less bits to Cb and Cr Y U V (Y Cb Cr) Components
Step 2: Picture Processing – Each block is transformed by the forward DCT into low- and high-frequency information. – This step is lossless, except that there may be little lost due to rounding of DCT coefficients – If one such 8×8 8-bit subimage is:
JPEG Image Compression II DCT: similar to FT; only real (cosine) part is kept. Identifies average value (dc coefficient) and remaining components (ac coefficients).
Step 2: Picture Processing – which, if we now subtract 128 from each element, results in
–
For example, using −415 (the DC coefficient) and rounding to the nearest integer
The quantization matrix may be scaled by a quality factor
Step 4: Entropy Encoding • Entropy coding is a special form of lossless data compression. • DC Coefficient Coding – the difference between the quantized DC coefficient of the current block and that of the previous block of the same component is taken.
• AC Coefficient Coding – the 63 quantized coefficients are converted into a onedimensional zig-zag sequence to increase the run length of zeros. - zero run-length encoding is then applied. - Huffman coding or arithmetic encoding is then further applied.
and then taking the DCT and rounding to the nearest integer results in
Zig-zag Scan DCT Blocks • Why? -- To group low frequency coefficients in top of vector. • Maps 8 x 8 to a 1 x 64 vector. – Note the rather large value of the top-left corner. This is the DC coefficient. The remaining 63 coefficients are called the AC coefficients. Step 3: Quantization • The human eye is good at seeing small differences in brightness over a relatively large area, but not so good at distinguishing the exact strength of a high frequency brightness variation. • This fact allows one to get away with greatly reducing the amount of information in the high frequency components. • This is done by simply dividing each component in the frequency domain by a constant for that component, and then rounding to the nearest integer. • This is the main lossy operation in the whole process. • As a result of this, it is typically the case that many of the higher frequency components are rounded to zero, and many of the rest become small positive or negative numbers. • A common quantization matrix is: •
Using this quantization matrix with the DCT coefficient matrix from above results in:
The zig-zag sequence for the above quantized coefficients would be:
−26, −3, 0, −3, −2, −6, 2, −4, 1, −4, 1, 1, 5, 1, 2, −1, 1, −1, 2, 0, 0, 0, 0, 0, −1, −1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
• •
DC coefficient is -26 Zero run-length encoding is (0, -3), (1, -3), (0, -2), (0, -6), (0, 2), (0, -4), (0, 1), (0, -4), (0, 1), (0, 1), (0, 5), (0, 1), (0, 2), (0, -1), (0, 1), (0, -1), (0, 2), (5, -1), (0, -1), (0, 0) Decoding • Decoding to display the image consists of doing all the above in reverse. • Taking the DCT coefficient matrix (after adding the difference of the DC coefficient back in)
• Given the following matrices Matrix A : 8 x 8 luminance block. Matrix B : 8 x 8 Quantization matrix (luminance)
a) b) c)
d) •
and multiplying it by the quantization matrix from above results in
•
which closely resembles the original DCT coefficient matrix for the top-left portion. Original:
•
Taking the inverse DCT (type-III DCT) results in an image with values (still shifted down by 128)
e)
For this luminance block, obtain a Matrix C by subtracting each entry from 128. Obtained the DCT coefficient matrix as a result of apply DCT to Matrix C. Compute the quantized coefficients using truncation to the nearest integers and then write them out in a zig-zag order. Compute the quantized coefficients by rounding to the nearest integers and then write them out in a zig-zag order. Compare the merits of using each of the techniques in parts (d) and (e) above.
JPEG 2000 • JPEG 2000 merupakan pengembangan kompresi JPEG. • Didesain untuk internet, scanning, foto digital, remote sensing, medical imegrey, perpustakaan digital dan e-commerce • Kelebihan : – Dapat digunakan pada bit-rate rendah sehingga dapat digunakan untuk network image dan remote sensing – Menggunakan Lossy dan loseless tergantung kebutuhan bandwidth. Loseless digunakan untuk medical image – Transmisi progresif dan akurasi & resolusi pixel tinggi – Menggunakan Region of Interest (ROI) – Robustness to bit error yang digunakan untuk komunikasi jaringan dan wireless – Open architecture : single compression/decompression – Mendukung protective image security : watermarking, labeling, stamping, dan encryption – Mendukung image ukuran besar 64k x 64k, size up to 232 - 1 – Mendukung meta data dan baik untuk computer-generated imagenary. Dulu JPEG standar baik untuk natural imagenary. 2-D Wavelet Transform via Separable Filters
•
Original
Latihan
and adding 128 to each entry
