kriteria kompresi citra

1

Copyright @ 2007 By Emy 1


KOMPRESI CITRA

2


Kompetensi

Mampu menjelaskan dan menyebutkan proses-prosespada kompresi citraMampu menjelaskan kriteria dari kompresi citra yang baikMampu menyebutkan dan menjelaskan jenis-jeniskompresi citraMampu menjelaskan metode kompresi citra yang banyakdigunakan untuk meningkatkan kualitas hasil kompresicitra


Topik

1. Dasar-dasar KompresiCitra

2. Model Kompresi citra3. Teori Informasi

Lecture

3


Dasar-Dasar Kompresi Citra


Kendala Data Citra DijitalKendala Data Citra Dijital

Mengapa perlu kompresi dan reduksi data? – Data citra umumnya berukuran besar– Tidak praktis dalam aspek penyimpanan, proses dan transmisi– Perlu reduksi atau pemampatan data dengan mengurangi redundancy atau

duplikasi data

Data redundancy:– adalah bagian data yang tidak mengandung informasi terkait

atau merupakan pengulangan dari informasi yang sudahdinyatakan sebelumnya atau sudah diketahui

4


Contoh AplikasiContoh Aplikasi

Aplikasi yang membutuhkan image compression: dimana perkembangannya ditentukan olehefisiensi pada manipulasi data, penyimpanan, dantransmisi citra biner / monokrom / berwarna:– Televideo-conferencing– Remote sensing– Telemedical / Medical imaging– Facsimile transmission


Kategori Teknik Kompresi CitraKategori Teknik Kompresi Citra

Berdasarkan detail suatu citra, teknik kompresi citradapat diklasifikasikan menjadi 2 kategori :– Berugi (Lossy)

Teknik mendapatkan data yang lebih ringkas dengan melaluisuatu proses penghampiran (approksimasi) dari data asli dengantingkat error yang dapat diterima. Beberapa informasi pada citrayang asli hilang, meskipun hanya sebagian kecil sajaContoh : JPEG (Joint Photographic Experts Group), TV broadcast.

– Tanpa rugi (Lossless)Teknik yang memproses data asli menjadi bentuk yang lebihringkas tanpa hilangnya informasiContoh : GIF (Graphical Interchange Format), Aplikasibiomedis.

5


Kriteria Mengukur MetodeKompresi Citra

Waktu kompresi dan waktu rekronstruksi yang sebaiknya cepat.Kebutuhan memori

– Memori yang dibutuhkan untuk merepresentasikan citraseharusnya berkurang secara berarti. Teknik kompresi dikatakanbaik apabila didapatkan rasio kompresi yang besar, karenasemakin besar rasio kompresi yang didapat berarti semakin kecilukuran hasil kompresi. Pada beberapa metode, ukuran memorihasil kompresi bergantung pada citra itu sendiri. Citra yang mengandung banyak elemen duplikasi (misalnya citra langitcerah tanpa awan, citra lantai keramik) umumnya berhasildikompresikan dengan memori yang lebih sedikit dibandingkandengan mengkompresikan citra yang mengandung banyak objek(misalnya citra pemandangan alam).



– Hasil rasio kompresi ( R ) dirumuskan

Kualitas kompresi (fidelity)– Informasi yang hilang akibat kompresi seharusnya seminimal mungkin sehingga

kualitas hasil kompresi tetap dipertahankan. Kualitas hasil kompresi dengankebutuhan memori biasanya berbanding terbalik. Kualitas sebuah citra bersifatsubyektif dan relatif, bergantung pada pengamatan orang yang menilainya. Dan untuk dapat membuat ukuran kualitas hasil kompresi citra menjadi ukurankuantitatif dengan menggunakan besaran PSNR (Peak Signal to Noise Ratio). Teknik kompresi dikatakan baik apabila menghasilkan nilai MSE yang kecil dannilai PSNR yang tinggi yang berarti error atau kesalahan dari teknik kompresiini sangat kecil dan hasil citra rekonstruksi terhadap citra asli mempunyaikemiripan yang tinggi. Sedangkan nilai rasio sinyal terhadap derau puncak ataunilai PNSR dalam dicibels (dB) dapat dihitung dari persamaan

%1001 tan ×⎥⎦

⎤⎢⎣

⎡−=

Asli

Pemampa

UU

R

MSEPSNR

2

10)255(log*10= [ ]∑∑

= =

−=M

y

N

xyxIyxI

NMMSE

1 1

2),('),(.1

6



Format keluaran.– Format citra hasl kompresi sebaiknya cocok

untuk pengiriman dan penyimpanan data. Pembacaan citra bergantung pada bagaimanacitra tersebut direpresentasikan (ataudisimpan).


Pendekatan Pada ProsesKompresi

Pendekatan statistik– Kompresi citra didasarkan pada frekuensi kemunculan derajat keabuan

pixel di dalam seluruh bagian citra. Contoh metode Huffman Coding.Pendekatan ruang– Kompresi citra didasarkan pada hubungan spasial antara pixel-pixel

didalam suatu kelompok yang memiliki derajad keabuan yang sama didalam suatu daerah di dalam citra. Contoh metode Run Length Encoding

Pendekatan kuantisasi– Kompresi citra dilakukan dengan mengurangi jumlah derajat keabuan

yang tersedia. Contoh metode kompresi kuantisasiPendekatan fraktal– Kompresi citra didasarkan pada kenyataan bahwa kemiripan bagian-

bagian di dalam citra dapat dieksploitasi dengan suatu matrikstransformasi. Contoh metode Fractal Image Compression.

7


Konsep Data RedundancyKonsep Data Redundancy

Tidak abstrak dan dapat dinyatakan dalam entitas besaranmatematisRelative data redundancy RD:

RD = 1 - 1/CR dan CR = n1/n2

n1 dan n2: jumlah satuan informasi yang dibawa data set 1 dan data set 2.Bila n1 = n2, maka CR = 1 dan RD = 0 (tidak ada redundancy).Bila n2 << n1, maka CR mendekati tak terhingga dan RD mendekati 1 (terjadiredundancy yang tinggi).

Bila n2 >> n1, maka CR mendekati 0 dan RD mendekati minus tak terhingga(informasi yang dibawa data set 2 jauh lebih besar dari data set 1)

Bila 0 < CR < 1 dan RD rendah ( tingkat redundancy rendah).


Data Redundancy

Ada 3 jenis data redundancy pada citra:– Coding redundancy– Interpixel redundancy– Psychovisual redundancy

Suatu data dikatakan terkompresi jika satuatau lebih redundancy tersebut bisadikurangi atau dihilangkan.

8


Coding redundancy (1)Coding redundancy (1)

Terjadi bila suatu kode simbol yang digunakan terdiri dari sejumlah bit yang melebihi jumlah bit yang diperlukan untuk representasi setiapsimbol (dalam hal ini: tingkatkeabuan piksel citra).



Fixed-length versus variable-length coding:rK p(rK) fixed L(rK) variable L(rK)

0 0.19 000 3 11 21/7 0.25 001 3 01 22/7 0.21 010 3 10 23/7 0.16 011 3 001 34/7 0.08 100 3 0001 45/7 0.06 101 3 00001 56/7 0.03 110 3 000001 51 0.02 111 3 000000 6

9



Tingkat keabuan yang probabilitas terjadinya tinggidiberi panjang kode yang pendek, dan bila sebaliknyadiberi kode yang panjang.Bila digunakan variable-length coding, panjang koderata-rata:

Bila digunakan fixed-length coding 3 bits, tingkatredundancy-nya adalah:RD = 1 – 1/CR = 1 – 1/(3/2.7) = 0.099 (sekitar 10%)

7

0( ) ( ) 2.7AVE K K

KL L r p r bits

=

= =∑


Interpixel Redundancy (1)Interpixel Redundancy (1)

1nΔ =

45nΔ =

Histogram distribusitingkat keabuan samauntuk kedua citra.

Pada gambar nilaiautocorrelation tinggipada dan padagambar (b) juga tinggipada dan 90.

1nΔ =

10



Sering disebut juga sebagai spatial redundancy, geometric redundancy, atau interframe redundancy.Normalized autocorrelation coefficient:

dimana N adalah jumlah piksel pada baris x danNilai tinggi (berkorelasi tinggi) pada atau 90 (b) dimana ada spasi garis vertikal. Juga piksel yang berdekatanmempunyai korelasi tinggi, yaitu dengan dimana nilaiadalah 0.9922 dan 0.9928 masing-masing untuk gambar (a) dan(b).

( )( )(0)

A nnA

γ ΔΔ =

1

0

1( ) ( , ) ( , )N n

yA n f x y f x y n

N n

− −Δ

=

Δ = + Δ−Δ ∑

γ

45nΔ =n NΔ <

γγ1nΔ =



Artinya: data redundancy dinyatakan dengankorelasi antar piksel dimana intensitas suatupiksel dapat diperkirakan dari intensitaspiksel-piksel tetangganya. Artinya: informasi yang dibawa oleh setiappiksel relatif tidak besar atau kontribusisetiap piksel kepada gambar secarakeseluruhan adalah redundan.

11



Citra yang mengandung interpixel redundancy dapatdirepresentasi ke dalam bentuk yang lebih efisien (non-visual format). Dimana citra tidak dinyatakan dalambentuk matriks dari intensitas piksel-pikselnya, akantetapi dipetakan (mapping) dalam bentuk perbedaanintensitas antar piksel yang bersebelahan. Bentuk data yang dimampatkan ini bersifat reversible, artinya dapatdirekonstruksi kembali menjadi citra asalnya. Run-Length Coding: (g1,R1), (g2,R2) … gi menyata-kan tingkat keabuan dan Ri menyatakan jumlah pikselbersebelahan pada baris bersangkutan yang mempunyaiintensitas gi.



Contoh Citra: Run-Length Code Representation:

0 0 0 0 1 1 0 00 0 0 1 1 1 1 00 0 0 1 1 1 1 00 0 1 1 1 1 1 00 0 1 1 1 1 1 00 0 0 1 1 1 0 00 0 0 0 1 0 0 00 0 0 0 0 0 0 0

Informasi Yang Disimpan:

22 pairs of integers

(0,3), (1,2), (0,2)(0,3), (1,4), (0,1)(0,3), (1,4), (0,1)(0,2), (1,5), (0,1)(0,2), (1,5), (0,1)(0,3), (1,3), (0,3)(0,4), (1,1), (0,3)(0,8)

12


Psychovisual Redundancy (1)Psychovisual Redundancy (1)

Mach Band: – Suatu fenomena dimana intensitas keabuan yang

bervariasi dilihat sebagai intensitas konstan, artinya: mata tidak mempunyai sensitivitas yang sama terhadap semua informasi yang dianggappenting dan tidak penting. Hal tersebut diatasdapat dikatakan sebagai psychovisualredundancy, yang bila dihilangkan tidakmengganggu persepsi kwalitas citra.



Quantization:– Eliminasi psychovisual redundancy mengakibatkan kerugian

informasi bersifat kwalitas. Teknik ini disebut quantization, yaitu pemetaan dari daerah intensitas yang lebar menjadi daerahintensitas terbatas (batas kemampuan visual manusia)

– Mata sangat sensitif terhadap informasi edge / garis batas / patahan. Proses kwantisasi dapat disesuaikan untuk kepentinganmempertahankan informasi edge seperti yang dilakukan padaImproved Gray Scale (IGS) Quantization.

Irreversible Operation:– Quantization mengakibatkan hilangnya sebagian informasi

visual, dengan demikian teknik ini termasuk pada kategori lossydata compression.

13



IGS (Improved Gray Scale) QuantizationPixel Gray Level Sum IGS Codei - 1 NA 0000 0000 NAi 0110 1100 0110 1100 0110i + 1 1000 1011 1001 0111 1001i + 2 1000 0111 1000 1110 1000i + 3 1111 0100 1111 0100 1111

Jika 4 most significant number bernilai 1111, maka yang ditambahkan adalah 0000

1000 10111100

1001 0111


Contoh

14


Psychovisual Redundancy (4)

Lossy compression perlu adanya kriteriapenilaian untuk mengatakan apakah hasilkompresi bagus atau tidak.Kriteria penilaian terbagi 2:– Secara objektif

Hilangnya informasi dinyatakan sebagai fungsi dari citra input kecitra output (next page)

– Secara subjektifBerdasarkan pada penilaian mata manusia. Tingkatannya:

Excellent, fine, passable, marginal, inferior, unusable.



Kesalahan akibat hilangnya informasi:f(x,y) adalah citra asli dan f’(x,y) adalah citra approksimasiTotal Error:

Root-Mean-Square Error:

Mean-square Signal-to-Ratio:

1 1

0 0( '( , ) ( , ))

M N

x yError f x y f x y

− −

= =

= −∑∑

1 12 1 / 2

0 0

1( ( '( , ) ( , ) ) )M N

R M Sx y

E f x y f x yM N

− −

= =

= −∑ ∑

1 12

0 01 1

2

0 0

'( , )

( '( , ) ( , ))

M N

x yMS M N

x y

f x ySNR

f x y f x y

− −

= =− −

= =

=−

∑∑

∑∑

15


Model Kompresi citra


Model sistem kompresi umum

Source encoder: menghilangkan redundansi inputChannel encoder: meningkatkan imunitas output source encoder terhadap gangguan noise (menggunakan Hamming code)Channel decoder & source decoder: mengembalikan ke data semulaJika channel dianggap bebas noise, maka channel encoder/decoder bisadiabaikan.

16


Source encoder & decoder



Source Encoder: terdiri dari Mapper, Quantizer dan Symbol Coder– Mapper: melakukan transformasi dari citra masukan (visual

format) menjadi suatu non-visual format dan dimaksud untukeliminasi interpixel redundancy. Biasanya bersifat reversible, contoh: run-length coding.

– Quantizer: melakukan eliminasi psychovisual redundancy menurut kriteria fidelity yang ditentukan. Pada sistemkategori error-free compression, tahap ini tidak dilakukan

– Symbol Coder: menghasilkan kode fixed-length atau variable-length dan memetakan citra pada sistem kode tersebut.

17



Source Decoder: melakukan operasi yang berlawanan dengan source encoder danmenghasilkan suatu citra rekonstruksi yang persis atau merupakan bentuk approksimasi daricitra asalnya.

Channel Encoder dan Decoder: menyisipkancontrolled redundancy bits (penambahan bits) untuk mendeteksi bila terjadi error ataugangguan waktu transmisi.


Teori Informasi

18


Teori Informasi (1)Teori Informasi (1)

Informasi yang dikandung oleh suatu pesan dapat dinyatakan dengan suatumodel yang bersifat probabilistik dalam bentuk yang dapat diterima secaraintuisi.Suatu event (yaitu komponent yang membentuk data) terjadi dengan probabilitasP(E) dan mengandung satuan informasiyang dapat dinyatakan dengan:

dengan I(E) disebut juga sebagai self-information of E.Contoh-1: Bila P(E)=1 maka I(E)=0, artinya tidak ada informasi yang dibawaevent E. Penjelasan secara intuitif: P(E)=1 berarti event E terjadi secara terusmenerus, sehingga tidak ada yang tidak diketahui mengenai E (no uncertainty). Artinya event E sudah diketahui karena selalu terjadi sehingga tidak adainformasi yang dibawa oleh event E.

1( ) log log ( )( )

I E P EP E

= = −


Teori Informasi (2)Teori Informasi (2)

Contoh-2: Dalam kurun waktu 20 tahun yang lalu jarang (ridak) terjadi pemboman di Indonesia, P(E) =0.99. Namum akhir-akhir inimulai terjadi pemboman dan yang terdasyat adalah baru-baru initerjadi di Legian, Bali, P(tidakE)=0.01. Penjelasannya secaraintuitif: Memberitakan terjadinya pemboman lebih membawainformasi dibanding dengan memberitakan tidak terjadipemboman.Contoh-3: Bila P(E)=1/2, maka I(E)=-log(1/2)= 1 bit (dengan log basis 2). Nilai 1 bit disini mempunyai arti besarnya informasi yang dikandung bila salah satu event (dari dua event yang probabilitasterjadinya sama besar yaitu ½) terjadi.

19


Average Self-information (1)Average Self-information (1)

Suatu sumber informasi terdiri dari simbol: {a1, a2, … , aj}, dengan P(aj) adalah probabilitas sumber tersebutmenghasilkan simbol aj, dengan:

Sumber informasi (A,z) dengan: A={a1, a2, … , aj} danz={P(a1), P(a2), … , P(aj)}. Bila sumber infromasimenghasilkan k simbol, maka simbol aj akan terjadirata-rata sebanyak kP(aj) kali. Sehingga average self-information yang dikandung oleh k simbol adalah:

1( ) 1

J

jj

P a=

=∑

1( ) log ( )

J

j jj

k P a p a=

− ∑


Average Self-information (2)Average Self-information (2)

Selanjutnya dapat dirumuskan average information per simbol (per source output):

H(z) disebut juga sebagai tingkat uncertainty atauentropy dari sumber informasi. Bila H(k) = 0 artinyano uncertainty.

1

( ) ( ) log ( )J

j jj

H z P a p a=

= −∑

20


Using Information Theory (1)Using Information Theory (1)

Average information content content (entropy) of each pixel in an image:

4x8 8-bit-pixel image:21 21 21 95 169 243 243 24321 21 21 95 169 243 243 24321 21 21 95 169 243 243 24321 21 21 95 169 243 243 243.

Bila menggunakan asumsi adanya uniform distribution, yaitu P(aj)=1/256 (256 adalah jumlah tingkat keabuan), maka H(z) = -256*(1/256*log(1/256)) yang mempunyai nilai 8. Artinya average information content (entropy) per pixel adalah 8 bits dan total entropy of the 4x8 image = 4 * 8 * 8 bits = 256 bits.

1

( ) ( ) log ( )J

j jj

H z P a p a=

= −∑



Bila menggunakan model histogram tingkat keabuan citra untukmenentukan probabilitas source symbols (pixel intensities), maka:Tingkat Keabuan JumlahProbabilitas

21 12 3/895 4 1/8

169 4 1/8243 12 3/8

Dalam hal ini dikatakan bahwa (the first-order estimate) of the entropy per pixel: H(z) = - (2*(3/8)*log(3/8) + 2*(1/8)*log(1/8)) = 1.81 bits dan total entropy of image = 4*8*1.81 = 58 bits.

21



Estimating the entropy of gray-level source by examining the relative frequency of pixel blocks (a block is a grouping of adjacent pixels):Gray Level Pair Count Probability

(21,21) 8 1/4(21,95) 4 1/8(95,169) 4 1/8(169,243) 4 1/8(243,243) 8 1/4(243,21) 4 1/8

Dalam hal ini dikatakan bahwa (the second-order estimate) of entropy per pixel H(z) = - (2*(1/4)*log(1/4) + 4*(1/8)*log(1/8))/2 = 1.25 bits.



A difference array:Gray Level Difference Count Probability

0 (column 2,3,7,8) 16 1/421 (column1) 4 1/874 (column 4,5,6) 12 3/8

(the first-order estimate) of entropy per pixel = 1.41 bits and total entropy of image = 4 * 8 * 1.41 bits = 46 bits.

22



kriteria kompresi citra

Documents