college: DIGITAL IMAGE CODING

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 2^z 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:

Quantization of DCT Coefficients

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