Contoh Metode Huffman

Pengolahan Citra – Contoh Kompresi Citra dengan Metode Huffman Misalkan terdapat citra berukuran 64x64 dengan probabilitasnya seperti pada tabel. Buat pohon Huffman dan Berapakah rasio kompresinya (R). Nilai piksel

ni

0 1 2 3 4 5 6 7

790 1023 850 656 329 245 122 81

hi = ni/n, (n=4096) 0,19 0,25 0,21 0,16 0,08 0,06 0,03 0,02

Jawab: • Urutkan secara menaik (ascending order) nilai keabuan berdasarkan frekuensi kemunculan atau berdasarkan probabilitasnya 1.

•

7:0,02

6:0,03

5:0,06

4:0,08

3:0,16

0:0,19

2:0,21

1:0,25

Gabung (jumlahkan) 2 buah pohon yang mempunyai frekuensi kemunculan paling kecil pada sebuah akar. Akar mempunyai frekuensi yang merupakan jumlah dari 2 pohon penyusunnya. 76:0,0 5

2. 7:0,02

•

5:0,06

4:0,08

3:0,16

0:0,19

2:0,21

1:0,25

6:0,03

Ulangi langkah 2, sampai tersisa hanya satu pohon biner. Agar pemilihan 2 buah pohon yang akan digabungkan berlangsung cepat, maka semua pohon yang ada selalu terurut menaik berdasarkan frekuensinya. 3.

765:0,1 1

4:0,08

4.

0:0,19

2:0,21

1:0,25

5:0,06

76:0,0 5 7:0,02

3:0,16

6:0,03

4765:0,19

3:0,16

2:0,21

1:0,25

765:0,1 1

4:0,08

76:0,0 5 7:0,02

0:0,19

5:0,06

6:0,03

Wahyudi Rahmat – 0506021286 - Elektro-IT, UNDANA

1

5.

0:0,19

2:0,21

34765:0,35

1:0,25

3:0,16

4765:0,19

765:0,1 1

4:0,08

76:0,0 5 7:0,02

6.

3:0,16

2:0,19

4765:0,19

5:0,06

76:0,0 5 7:0,02

6:0,03

134765:0,60

02:0,4 0 0:0,19

1:0,21

765:0,1 1

4:0,08

7.

6:0,03

02:0,4 0

34765:0,35

1:0,25

5:0,06

2:0,21

34765:0,35

1:0,25

3:0,16

4765:0,19

765:0,1 1

4:0,08

76:0,0 5 7:0,02

Wahyudi Rahmat – 0506021286 - Elektro-IT, UNDANA

5:0,06

6:0,03

2

•

Beri label setiap sisi pada pohon biner. Sisi kiri diberi label 0 dan sisi kanan diberi label 1. 8.

02134765:1,0 0

1

02:0,4 0

134765:0,60

0 0:0,19

1 2:0,21

0

1

1:0,25

34765:0,35 1

0 3:0,16

4765:0,19 1

0

765:0,1 1

4:0,08

0

0 7:0,02

1

76:0,0 5

5:0,06

1

6:0,03

Tabel Huffman 0 = 00

1 = 10

2 = 10

3 = 110

4 = 1110

5 = 11111

6 = 111101

7 = 111100

Ukuran citra sebelum pemampatan : • Karena nilai piksel tertinggi dari citra tersebut adalah 7 (1112), maka citra tersebut memiliki 1 derajat keabuan = 3-bit. • Jadi ukuran citra yang sebenarnya Uasli = 4096 x 3-bit = 12288-bit ≈ 12,3-Kbit Sedangkan ukuran citra setelah pemampatan : • Ukompres = (790 x 2-bit) + (1023 x 2-bit) + (850 x 2-bit) + (656 x 3-bit) + (329 x 4-bit) + (245 x 5-bit) + (122 x 6-bit) + (81 x 6-bit) = 11053-bit. ≈ 11,05-Kbit Jadi Rasio Kompresinya (R) adalah: R

Ukompres  = 1 − U asli 

  × 100%  

 11053   × 100% = 1 −  12288 

= 10.05 %

Wahyudi Rahmat – 0506021286 - Elektro-IT, UNDANA

3