Kompresi citra merupakan suatu
aplikasi dari teknik kompresi gambar digital dua dimensi l(x,y) untuk
mengurangi redudansi data gambar dalam penyimpanan atau transmisi dalam bentuk
yang lebih efisien. Kompresi gambar dapat diklasifikasikan ke dalam dua
kategori, yaitu:
·
Lossless
Kompresi
lossless mempunyai rasio kompresi yang lebih kecil dibandingkan dengan kompresi
lossy, kompresi ini memiliki kelebihan pada gambar yang mempunyai distribusi
probabilitas seragam untuk sebuah representasi panjang variable dari pixel
gambar. Jenis kompresi ini biasa digunakan untuk menggambar teknis, ikon atau
komik, foto atau gambar untuk keperluan medis, dan gambar scan untuk keperluan arsip.
·
Lossy
Kompresi
lossy mempunya rasio kompresi yang sangat tinggi, di mana ketika mencapai suatu
rasio tertentu dapat disebut sebagai kompresi artifact. Teknik kompresi ini baik untuk digunakan pada gambar –
gambar natural, seperti foto.
BASIC
OF INFORMATION THEORY FOR IMAGE COMPRESSION
Setiap simbol dapat
direpresentasikan menjadi m-tuple (m-dimensional), dan difenisikan dengan:
ENTROPY
CODING
Entropy
coding merupakan skema pengodean yang memberikan kode pada simbol
untuk mencocokkan panjang kode dengan probabilitas dari simbol. Entropy encoder biasanya digunakan untuk
kompresi data dengan mengganti simbol yang memiliki panjangan kode sama dengan
simbol diwakili oleh kode yang panjang setiap codeword sebanding dengan
probabilitas logaritma negatif. Oleh karena itu, simbol yang paling umum
menggunakan kode terpendek. Dua teknik penkodean entropi yang paling popular
ada Huffman coding dan arithmetic coding.
Huffman
Coding
Dikembangkan oleh David A.
Huffman, sebuah entropy encoding algoritma
yang digunakan untuk kompresi data lossless.
Teknk ini bekerja dengan menggunakann variable
length binary code untuk encoding satu
set simbol. Tabel variable length code didasarkan
pada perkiraan terjadinya probabilitas dari setiap nilai yang mungkin dari
simbol. Huffman coding menggunakan
metode khusus untuk menentukan representasi setiap simbol dan hasilnya di dalam
sebuah prefix. Huffman code menggambarkan simbol yang memiliki frekuensi paling
tinggi / paling sering keluar dengan bit string
yang lebih pendek dibandingkan yang memiliki frekuensi keluar rendah. Huffman metode kompresi paling efisien
pada tipe ini.
Huffman
coding sering digunaan sebagai ”back
– end” dengan beberapa metode kompresi lainnya. PKZIP codec dan beberapa codec multimedia seperti JPEG dan MPG memiliki
front-end skema kompresi lossy yang diikuti oleh lossless huffman coding. Beberapa
sifat properti yang terkait dengan Huffman
code:
1. Blok
Code
Setiap
simbol dipetakan ke dalam urutan sekuen yang tetap (variable - length) kode simbol, tanpa perubahan yang dinamis selama
berlangsungnya penggabungan simbol
2. Instantaneous
(Prefix – Free) Code
Decoding terjadi tanpa mengacu pada urutan simbol
tersebut.
3. Uniquely
decodable
Setiap string dari kode simbol diterjemahkan
dalam satu cara
4. Close
to Entropy
Rata –
rata panjangan kode L, dekat dengan ekspektasi jumlah yang diharapkan dari
informasi, entropi H
Arithmetic
Coding
Meskipun Huffman coding optimal untuk pengkodean setiap simbol dengan input
distribusi probabilitas yang diketahui, arithmetic
coding terkadang memiliki kemampuan kompresi yang lebih baik. Dalam
penerapanya, arithmetic coding
dimulai dengan Huffman coding karena
lebih mudah untuk menemukan arithmetic
coding dengan menggunakan biner. Arithmetic
coding terdiri dari non-block code dengan
korespondensi satu – satu antara source dan
simbol codeword dari Huffman.
Algoritma kompresi yang
menggunakan arithmetic coding dimulai
dengan menentukan model probabilistic dari data yaitu dengan memprediksi pola
yang akan ditemukan dalam simbol – simbol pesan. Semakin akurat prediksi yang
dihasilkan, maka output yang
dihasilkan akan semakin optimal.
Context
Adaptive Binary Arithmetic Coding (CABAC)
CABAC merupakan teknik yang
efisien untuk kondisional entropy coding.
Teknik ini biasanya diterapkan pada pengkodean gambar untuk kompresi
dokumen level bi (bi-level documents), contohnya gambar
hitam dan putih atau gambar faks. Umumnya
di dalam CABAC, sebuah array dari
variabel dengan masing – masing nilai terkait didefinisikan untuk mewakili
distribusi probabilitas yang berbeda (geometris). Sistem CABAC menerapkan
mekanisme adaptasi sensitif backward
untuk menghitung probabilitas input
binary symbol.
Run
– Length Coding (RLC)
Skenario yang buruk dari Huffman coding akan terjadi ketika
probabilitas dari sebuah simbol lebih besar dari 2-1 – 0.5. Hal ini
juga akan terjadi ketika dua source simbol
dengan probabilitas yang tidak sama ter-encoded.
Kedua situasi ini akan lebih baik jika di-encode
menggunakan arithmetic coding atau
RLC. RLC akan meng-encode sekuen dari
simbol binary dengan data yang
berjalan. RLC akan bekerja dengan method
lossless coding yang merekam jalannya satuan nilai data dan menghitung
lebih akurat dari yang sebelumnya dijalankan.
RLC encoding biasanya dikombinasikan dengan teknik lain, seperti Huffman coding untuk menghasilkan teknik
kompresi data yang sangat efisien. RLC method
juga dapat digunakan dalam kasus dua dimesi, ketika diketahui alamat
pengkodean realatif (RAC) yang biasa digunakan di JBIG2 untuk kompresi dokumen fax bewarna. Penggunaan RLC lebih jauh
di manfaatkan pada sekuen multiple simbol
dengan satu simbol yang memilii probabilitas lebih tinggi dibandingkan dengan
simbol lainnya.
LOSSY
IMAGE COMPRESSION
Kompresi
lossless tidak cukup baik untuk
melakukan kompresi pada gambar yang memiliki bitrate rendah. Melihat kebutuhan yang ada, melalui teknik kompresi
lossy kita perlu melakukan pendekatan
lebih yang memperhatikan distorsi dan sinyal dari proses kuantisasi. Kuantisasi
dapat dijalankan secara spasial atau pada transformasi domain. Hampir semua
contoh spasial / transformasi domain dari suatu gambar dapat diasumsikan dengan
nilai yang dapat dijelaskan.
Kuantisasi
merupakan sebuah non-linear dan
operasi irreversible yang dipetakan
secara berkelanjutan dalam suatu nilai skalar, yang di mana level dari indeks
dapat direpresentasikan dengan sebuah nilai finite
number L dari bit. Terdapat dua tipe berbeda dari kuantisasi:
a.
Uniform
Quantization
Mendefinisikan set finite dari nilai yang dikombinasikan dengan ruang tertentu untuk
memilih bentuk
b.
Non –
Uniform Quantization
Terbagi secara tidak beraturan dengan range kuantisasi 2z level yang mungkin dengan ruang yang
berbeda
JOINT PHOTGRAPHIC EXPERTS GROUP
(JPEG)
JPEG
merupakan salah satu standar pengkodean gambar yang cukup terkenal dan
komprehensif. Nama JPEG diambil dari komite yang menciptakan kompresi gambar
dengan teknik lossy standar ISO/IEC
10918-1/2/3 pada tahun 1994 yang dilanjutkan dengan pewarnaan grayscale dan non-grayscale.
Banyak
parameter yang terasosiasi dengan teknik kompresi JPEG. Dengan merubah suatu
parameter , dapat menyebabkan ukuran gambar yang dikompres merekonstruksi
kualitas dalam range yang cukup
besar. Biasanya threshold yang
terlihat berbeda dari gambar yang sebenarnya dari rasio kompresi berada di
sekitas 10 hingga 20, 1 hingga 2 bit per pixel
warna.
Terdapat
3 perbedaan melakukan pengkodean menggunakan mode JPEG, yaitu:
1.
A Lossy
Baseline Mode, biasa disebut sebagai penggunaan sekuensial
dasar dengan menggunakan teknik kompresi berdasarkan DCT hampir di semua
aplikasi. Gambar ter-encode dengan menggunakn
single left-to-right, top-tobottom scan.
2.
An
Extended Coding Mode, digunakan untuk kompresi dengan hasil yang
baik dan ketelitian yang lebih tinggi. Gambar ter-encode dengan menggunakan multiple
scan / multiple
coarse-to-clear-passes.
3.
A
Losssless Encoding Mode, gambar ter-encode dengan ekstrak recovery
setiap contoh nilai dari source,
sekalipun kompresi ini sulit untuk dibandingkan dengan mode lossy.
DCT-based sequential berdasarkan enkoder:
DCT-based sequential berdasarkan dekoder:
Source Image Data Preparation: Chroma
Subsampling
Block – Based Discrete Cosine Transform
Untuk
setiap komponen gambar yang menggunakan atau tidak menggunakan chroma subsampling, kita akan
mengelompokkan nilai pixel {f(x,y)}
menjadi 8 x8 blok untuk discrete
transform (DCT), di mana
menghasilkan nilai yang sebenarnya dan energy
compact frekuensi yang dipetakan {F(u,v)} dari data dua dimensi. Penggunaan
DCG digunakan pada informasi yang berfrekuensi tinggi yang tidak terlihat
seperti informasi berfrekuensi rendah. Forward
DCT (FDCT) dan Inverse DCT (IDCT)
untuk 8x8 blok gambar, ditunjukkan dengna persamaan:
Setelah
mendapatkan hasil dari FDCT, masing masing 64 koefisien DCT F(u,v),
dikuantisasi menggunakan prespecified 64
element yang di dapat dari tabel kuantisasi (normalisasi matrix). Kuantisasi
proses ditunjukkan dengan persamaan:
Objektif dari langkah – langkah
kuantisasi untuk menghilangkan informasi yang terlihat tidak signifikan.
Koefisien berfrekuensi tinggi terkuantisasi lebih akurat dibandingkan dengan
yang berfrekuensi rendah. Dekuantisasi merpakan fungsi invers yang mengambil
koefisien FDCT dikalikan dengan ukuran langkah Q(u,v) yang mengembalikan
hasil untuk representasi nilai yang dijadikan sebagai masukan ke IDCT.
DC
Coding and Zigzag Sequence
Hasil dari kuantisasi,
koefisien DC biasanya memiliki nilai yang cukup besar. Karena adanya korelasi
yang kuat antara koefisien DC pada matriks adjensi 8x8 blok, koefisien DC yang
terkuantisasi ter-encode berbeda dari
DC yang sebelumnya ada pada blok di encoding
order. Terakhir, semua koefisien kuantisasi tersusun menjadi zigzag sekuen.
Entropy
Coding
Digunakan untuk memenuhi
beberapa tambahan pada kompresi losslessly
dengan meng-encode multiple-symbol menggunakan
RLC sekuen, dari masing – masing karakteristik statisktik.
Header
Information and JPEG Decoding
Dalam keadaan perubahan yang
normal pada berkas JPEG, semua parameter kompresi berada di dalam header, sehingga decoder dapat
mengembalikan proses. Parameter ini termasuk quantization table dan Huffman
coding table.
Trading
Off Compression and Picture Quality
Pada gambar berwarna dengan
bagian yang cukup komplreks, semua mode berbasis operasi DCT biasanya akan
menghasilkan kualitas gambar pada rentang kompresi tertentu. “Bit per pixel” menunjukkan jumlah bit
yang dikompres pada gambar, termasuk komponen pencahayaan. Terbagi menjadi 4
rentang pencahayaan:
1. 0.25 –
0.5 bits/pixel
2. 0.5 -
0.75 bits/pixel
3. 0.75 – 1.5
bits/pixel
4. 1.5 –
2.0 bits/pixel
JPEG Progressive Mode
Mode
JPEG progressive dibuat dengan tujuan
untuk mendukung transmisi gambar secara real-time,
di mana hasil yang memiliki kualitas rendah dapat dikirim dan diikuti dengan
tetap cepat secara halus dalam waktu yang memungkinkan.
JPEG Hierarchical Mode
Mode
ini digunakan untuk merepresentasikan sebuah gambar pada beberapa resolusi.
Dengan menggunakan konsep skala spasial, gambar beresolusi tinggi dapat
dikodekan sebagai perbedaan dari gambar berikutnya yang lebih kecil dan hanya
membutuhkan sedikit bit jika dibandingkan disimpan secara independen pada
resolusi yang lebih tinggi. Berikut langkah – langkah melakukan encoding:
1.
Mem-filter
downsample dari gambar yang asli
2.
Meng-encode
reduced-size menggunakan sekuens DCT, progresif DCT, atau lossless encode
3.
Decode
reduced-size gambar
4.
Menggunakan gambar sebagai prediksi reslusi dari
gambar yang asli
5.
Mengulangi langkah ke-3 dan ke -4
JPEG Lossless Mode
Mode
JPEG ini tidak dapat digunakan pada DCT dikarenakan adanya kesalahan pembulatan
oleh kuantisasi koefisien DCT.
JPEG Codestream
JPEG Codestream diilustrasikan sebagai
berikut:
JPEG 2000
Meskipun
penggunaan kompresi gambar menggunakan JPEG 2000 sudah sering digunakan, tetapi
kompresi ini memiliki banyak sekali kekurangan, beberapa kekurangan tersebut
diantaranya:
1. Distortion and Artifacts
2. Ineffective Handling of High Quality Images
3. Lock of effective color-space support
4. Ineffective Progressive and Hierarchical Modes
5. Poor Lossless Compression Performance
Untuk
menutupi kekurangan yang ada, makan diciptakan algoritma kompresi JPEG 2000.
JPEG 200 merupakan standar kompresi gambar yang berbasis wavelet. Beberapa kelebihan JPEG 2000:
1. Superior Compression Performance
2. Multiple Resolution Representation
3. Progressive Transmission by Pixel and Resolution Accuracy
4. Lossless and Lossy Compression
5. Random Codestream Access and Processing
6. Error Resilecnce
7. Sequential Buildup Capability
8. Flexible File Format
Technical Overview of JPEG200
Preprocessing
Spesifikasi RCT:
Inverse RCT:
Discrete Wavelet Transform and Quantization
Lifting algoritma yang digunakan pada wavelet transform:
1. Split step
2. Lifting step
3. Normalization step
Codeblock and Precinct Partition
Contoh parttisi dari wavelet subband
MINDMAP