2017

MKB3383 -TEKNIK PENGOLAHAN CITRA

Kompresi Citra Muhammad Zidny Naf’an, M.Kom. Genap, 2016/2017

Latar Belakang

2

Latar Belakang • Seringkali representasi citra yang besar membutuhkan memori yang besar • Contoh citra berformat bitmap dengan ukuran 512x512 pixel membutuhkan 262144 byte (1 pixel = 1 byte untuk citra berlevel 8-bit) – Semakin besar ukuran citra  semakin besar ukuran memorinya

• Kebanyakan citra mengandung duplikasi data – Suatu pixel dengan pixel tetangganya memiliki intensitas yang sama – Citra banyak mengandung bagian (region) yang sama 3

Image Compression • Kompresi  untuk apa? – Volume data yang besar – bandwidth yang tinggi

• Solusi – Penambahan storage dan bandwidth

–Kompresi data 4

Image Compression VS Image Encoding • Kadang dianggap sama • Image encoding  merepresentasikan pixelpixel dengan kode tertentu – Tidak selalu menghasilkan memori yang kecil – Jika memori yang dihasilkan lebih kecil dari citra asal  image compression

5

Proses dalam Image Compression • Image Compression – Mengkodekan kembali citra sehingga ukuran memori yang dibutuhkan lebih kecil – Bitmap  bukan citra yang terkompresi – JPG, GIF  citra yang terkompresi

• Image Decompression – Mengembalikan citra ke representasi awal (bitmap) – Diperlukan jika citra ditampilkan ke layar atau di simpan ke dalam arsip dengan format tidak terkompresi 6

Image Compression • Teknik kompresi yang diharapkan : – Proses kompresi/dekompresi yang cepat – Membutuhkan memory yang kecil – Kualitas citra kompresi yang bagus – Proses transfer dan penyimpanannya mudah

7

Image Compression • Berdasarkan hasilnya, teknik kompresi ada 2 :

• Klasifikasi Teknik Kompresi : – Entropy Encoding (Lossless) • • • •

Run Length Encoding (RLE) Pattern Substitution Huffman DPCM

– Source Encoding (Lossy) • Quantizing Compression • Transfrom Encoding

– Hybrid Encoding (Lossy) • JPEG 8

Metode Lossless • menghasilkan citra kompresi yang tepat sama dengan citra semula, pixel per pixel • Tidak ada informasi yang hilang akibat pemampatan. • Cocok untuk citra yang mengandung informasi penting yang tidak boleh rusak akibat pemampatan. – Misalnya kompresi gambar hasil diagnosa medis.

• File format: TIFF, GIF, PNG

9

Metode Lossy • Metode lossy menghasilkan citra hasil pemampatan yang hampir sama dengan citra semula. Ada informasi yang hilang akibat pemampatan, tetapi dapat ditolerir oleh persepsi mata • Mata tidak dapat membedakan perubahan kecil pada gambar. • Contoh metode lossy adalah metode JPEG dan metode fraktal. • File format: JPEG (jpg, jpe, jpeg); JPEG2000 (jp2, jpx)

10

Rasio Kompresi (Nisbah Pemampatan) • Prosentase hasil kompresi • Dihitung dengan rumus:

11

Redundancy Data pada Citra

Center of Image Analysis Swedish University of Agriculture Sciences Uppsala University

12

Image Encoding & Compression –Interpixel Redundancy

–Coding redundancy

13

Run Length Encoding (RLE) • Image dengan ukuran 4x6 • 8-bit image

1 2 1 1 1 1 1 3 4 4 4 4 1 1 3 3 3 5 1 1 1 1 3 3

• Diubah dalam bentuk sekuensial  1 2 1 1 1 1 1 3 4 4 4 4 1 1 3 3 3 5 1 1 1 1 3 3 = 24 byte • Dihitung jumlah kemunculan data  (1,1) (2,1) (1,5) (3,1) (4,4) (1,2) (3,3) (5,1) (1,4) (3,2) • Data Kompresi  1 1 2 1 1 5 3 1 4 4 1 2 3 3 5 1 1 4 3 2 = 20 byte 14

Huffman Coding


15

Huffman Coding

Setiap tingkat keabu-abuan memiliki probability masing-masing. Gunakan kode yang lebih pendek untuk tingkat keabu-abuan yang memiliki probability tinggi (sering muncul). Gunakan kode yang lebih panjang untuk tingkat keabu-abuan yang memiliki probability rendah. Center of Image Analysis Swedish University of Agriculture Sciences Uppsala University

16

Huffman Coding 1. 2. 3. 4.

Sort the gray levels by decreasing probability Sum the two smallest probabilities. Sort the new value into the list. Repeat 1 to 3 until only two probabilities remains.

1. Give the code 0 to the highest probability, and the code 1 to the lowest probability in the summed pair. 2. Go backwards through the tree one node and repeat from 1 until all gray levels have a unique code.


17

Example Huffman Coding


18



19



20



21



22



23



24

Huffman Coding 1. 2. 3. 4.

Sort the gray levels by decreasing probability Sum the two smallest probabilities. Sort the new value into the list. Repeat 1 to 3 until only two probabilities remains.

1. Give the code 0 to the highest probability, and the code 1 to the lowest probability in the summed pair. 2. Go backwards through the tree one node and repeat from 1 until all gray levels have a unique code.


25



26



27



28



29



30

Bagaiman Huffman Coding dari Citra berikut?

Ukuran= 4x4 pixel Citra 3-bit

31

Quantizing Compression Algoritma: 1. Buat histogram citra semula. (citra yang akan dimampatkan). 2. Identifikasi n buah kelompok di dalam histogram sedemikian sehingga setiap kelompok mempunyai kira-kira P/n buah pixel. 3. Nyatakan setiap kelompok dengan derajat keabuan 0 sampai n – 1. Setiap pixel di dalam kelompok dikodekan kembali dengan nilai derajat keabuan yang baru. 32

Quantizing Compression

33

Quantizing Compression • Akan dimampatkan menjadi citra dengan 4 derajat keabuan (0 s/d 3), jadi setiap derajat keabuan direpresentasikan dengan 2 bit. Histogram citra semula :

34

• Ada 65 pixel, dikelompokkan menjadi 4 kelompok derajat, keabuan tiap kelompok ada sebanyak rata-rata 65/4 = 16.25 pixel per kelompok :

35

• Citra hasil kompresi:

• Ukuran citra sebelum pemampatan (1 derajat keabuan = 4 bit): 65 x 4 bit = 260 bit • Ukuran citra setelah pemampatan (1 derajat keabuan = 2 bit): 65 x 2 bit = 130 bit 36

Quantizing Compression 2 9 6 4 8 2 6 3 8 5 9 3 7 3 8 5 4 7 6 3 8 2 8 4 7 3 3 8 4 7 4 9 2 3 8 2 7 4 9 3 9 4 7 2 7 6 2 1 6 5 3 0

2 0 4 3 8 9 5 4 7 1 2 8 3

• Histogram : – – – – – – – – – –

Warna 0 = 2 Warna 1 = 2 Warna 2 = 9 Warna 3 = 11 Warna 4 = 9 Warna 5 = 4 Warna 6 = 5 Warna 7 = 8 Warna 8 = 9 Warna 9 = 6

Dikodekan menjadi 0 (Jumlahnya 13 pixel)

Dikodekan menjadi 1 (Jumlahnya 20 pixel) Dikodekan menjadi 2 (Jumlahnya 17 pixel) Dikodekan menjadi 3 (Jumlahnya 15 pixel)

37

Quantizing Compression 0

3

2

1

3

0

2

1

3

2

3

1

2

1

3

2

1

2

2

1

3

0

3

1

2

1

1

3

1

2

1

3

0

1

3

0

2

1

3

1

3

1

2

0

2

2

0

0

2

2

1

0

0

0

1

1

3

3

2

1

2

0

0

3

0

38

JPEG Joint Photographic Experts Group • JPEG bukan suatu algoritma tunggal, tetapi merupakan sekumpulan toolkit untuk kompresi citra • Menggunakan metode lossy compression yang akan menghilangkan data yang tidak diperlukan • JPEG di-desain untuk membuang informasi (warna) yang tidak dapat dilihat manusia dgn mudah 39

JPEG Joint Photographic Experts Group Data Image

Preparation Process

Transformasi DCT

Table

Table

Quantization

Entropy Encoding

Binary Stream

40

JPEG 1.

Tahap Persiapan (Preparation Process) Pada tahap ini dilakukan proses membagi citra menjadi blok 8x8 10

12

11

10

11

12

13

20

11

11

12

16

17

18

12

11

10

10

15

16

14

13

19

20

20

18

16

16

15

14

12

11

12

13

11

11

10

13

14

17

10

11

17

16

15

12

12

13

17

18

18

10

11

12

14

15

11

12

20

19

18

17

17

15

41

JPEG 2. Tranformasi DCT (Discrete Cosine Transform) •

•

Transformasi DCT bertujuan mengubah menghitung frekuensifrekuensi pembentuk dari citra blok 8x8 dan memisahkan frekuensi rendah dan frekuensi tinggi dari hasil tranformasi DCT. Transformasi DCT terhadap blok 8x8 dapat dilakukan dengan rumus :

7 7 1  (2.x  1).u.   (2. y  1).v.  DCT (u , v)  .C (u ).C (v) . f ( x, y ). cos . cos    4 16 16     x 0 y 0

Dimana :

 1 , z0  C ( z)   2 1, z0

42

JPEG 2. Tranformasi DCT (cont.) Frekuensi >>, Penting << -86

-27

-105

-2

1

44

19

-100

-79

24

34

45

-22

-14

-43

18

-64

-35

-20

-15

-17

21

15

-184

3

72

-17

0

-53

8

-13

17

14

9

44

11

6

-15

-3

-23

12

13

39

99

122

-25

-13

-18

-6

26

12

14

15

7

-116

-46

-93

30

35

-4

28

17

17

15

-53

-110

137

-56

-19

-3

-11

3

12

11

10

11

12

13

20

11

11

12

16

17

18

12

11

10

10

15

16

14

13

19

20

20

18

16

16

15

14

12

11

12

13

11

11

10

13

14

10

11

17

16

15

12

17

18

18

10

11

11

12

20

19

18

DCT

43

Frekuensi >>, Penting <<

3588

10

JPEG 3. Quantisasi •

Proses Quantisasi bertujuan untuk menghilangkan nilai-nilai yang tidak penting (dalam hal ini nilai-nilai yang berada pada daerah frekuensi tinggi) pada matrix hasil dari Transformasi DCT.

Quantized _ Value(i, j ) 

DCT _ Matrix(i, j ) Quantum_ Matrix(i, j )

44

JPEG 3. Quantisasi (Cont.) 326 -6 -1 -6

0

0

1

0

27

-7 -5

27

29

1

27

29

31

3588 -86

-27 -105

-2

1

44

19

11

13

15

17

19

21

23

25

-100 -79

24

34

45

-22

-14

-43

13

15

17

19

21

23

25

15

17

19

21

23

25

17

19

21

23

25

1

1

2

0

0

-1

-3 -1

0

0

0

0

0

3

0

0

-1

0

0

0

0

18

-64

-35

-20

-15

-17

21

15

-184

3

72

-17

0

-53

8

-13

14

9

44

11

6

-15

-3

-23

19

21

23

25

27

29

31

33

0

0

1

0

0

0

39

99

122 -25

-13

-18

-6

26

21

23

25

27

29

31

33

35

1

4

4

0

0

0 12 0

-93

30

35

-4

28

23

25

27

29

31

33

35

37

0

-4 -1 -3

0

1

0

0

-53 -110 137 -56

-19

-3

-11

3

25

27

29

31

33

35

36

39

-2 -4

0

0

0

0

7

-116 -46



=

-10 0

4

45

-1

JPEG 4. Entropy Encoding •

•

Entropy Encoding adalah teknik kompresi yang bersifat lossless. Tahap ini bertujuan untuk mengkompresi matrix hasil quantisasi, bisa menggunakn metode huffman atau RLE Proses Entropy Encoding terhadap hasil quantisasi di atas dengan pembacaan zigzag : 326 -6

-1

-6

0

0

1

0

-7

-5

1

1

2

0

0

-1

1

-3

-1

0

0

0

0

0

-10

0

3

0

0

-1

0

0

0

0

1

0

0

0

0

0

1

4

4

0

0

0

12

0

0

-4

-1

-3

0

1

0

0

-2

-4

4

-1

0

0

0

0

Hasil encoding jika menggunakan RLE : 326,-6,-7,1,-5,1,6,1,-3, [0,3] , -1,1,[0,2],2,[0,1],3, [0,1], 1, [0,1],4,1,[0,3],1,[0,5],4,-4,-2,4,-1,[0,2],1,[0,1], -1, [0,4],-3,4,1,[0,5],12,1,[0,7] = 49 byte

46

JPEG


47

Mengukur Kualitas Citra hasil Kompresi • Dengan metode PSNR (peak signal-to-noise ratio) • PSNR dihitung untuk mengukur perbedaan antara citra semula dengan citra hasil kompresi 𝑏 𝑃𝑆𝑁𝑅 = 20 × log10 𝑟𝑚𝑠 – b adalah nilai sinyal terbesar (pada citra hitam-putih, b = 255) – rms adalah akar pangkat dua dari selisih antara citra semula dengan citra hasil pemampatan. 48

Mengukur Kualitas Citra hasil Kompresi • Rumus rms: 𝑟𝑚𝑠 =

1 𝑙𝑒𝑏𝑎𝑟 × 𝑡𝑖𝑛𝑔𝑔𝑖

𝑁

𝑀

(𝑓𝑖,𝑗 − 𝑓′𝑖,𝑗 )2 𝑖=1 𝑗=1

– f dan f ' masing-masing menyatakan nilai pixel citra semula dan nilai pixel citra hasil pemampatan.

49

Mengukur Kualitas Citra hasil Kompresi • PSNR memiliki satuan decibel (dB). • Nilai rms yang rendah -yang menyiratkan bahwa citra hasil kompresi tidak jauh berbeda dengan citra semula- akan menghasilkan PSNR yang tinggi, yang berarti kualitas pemampatannya bagus. • Semakin besar nilai PSNR, semakin bagus kualitas pemampatannya. 50

Lakukan Kompresi dengan Metode Huffman Coding • The “Fun” image shown below is a bitmap graphic with 32×16 = 512 pixels using 6 different colors: White, yellow, magenta, blue, black, and red. Distribution

Original Code

White

394

000

Yellow

42

001

Magenta

30

010

Blue

22

011

Black

18

100

Red

6

101

Color

51

http://ecee.colorado.edu/~mathys/ecen1200/bits/huffman.pdf

Referensi • Slide Pengolahan Citra, Departement Teknik Informatika IT Telkom • Rinaldi Munir, Pengolahan Citra Digital • Minarni, Pengolahan Citra Digital • Centre of Image Analysis. Uppsala University & Swedish University of Agriculture Sciences

52

2017

Recommend Documents