Seminar Nasional Teknologi Informatika, "The Future of Computer Vision", 2017, ISBN : 978-602-50006-0-7
Implementasi Algoritma Kompresi Shannon – Fano pada Citra Digital Muhammad Khoiruddin Harahap Politeknik Ganesha Medan
[email protected]
Abstrak Algoritma kompresi Shannon-Fano merupakan salah satu algoritma kompresi yang terkenal dan berguna dalam menghemat ruang penyimpanan data. Algoritma kompresi Shannon-Fano mendeteksi berapa kali kemunculan karakter pada setiap percobaanya, kemudian dilakukan pengkodean terhadap frekuensi kemunculan karakter dalam bilangan biner (binary code). Algorimat kompresi Shannon-Fano dapat dilakukan pada teks dan juga pada citra digital. Pada penelitian kali ini, penulis menerapkan metode Shanon-Fano pada citra digital. Citra digital diubah kedalam bilangan decimal yang berkisar antara 0-255, kemudian nilai setiap pixel citra yang sama mulai diseleksi dan dihitung berapa kali frekuensi kemunculan setiap nilai pixel yang sama dalam sebuah citra. Dari total frekuensi kemunculan setiap pixel citra, maka dilakukanlah pembagian nilai frekuensi menjadi dua bagian agar seimbang bagian pertama dan kedua, dan bagian pertama diberi nilai biner 0, sedangkan bagian kedua diberi nilai 1, dan hal ini terus berlangsung sampai tidak ada lagi bagian frekuensi yang tidak seimbang nilainya. Dari sini diperolehlah berapa bit (binary digit) hasil kompresi yang terbentuk, sehingga rasio kompresi bisa dihitung dari nilai total frekuensi dikali dengan bit dari binary code yang terbentuk , dan dibagi total frekuensi sebelum kompresi. Pada percobaan kompresi terhadap sebuah citra 3x3 diperolehlah rasio kompresi sebesar 22%. Kata Kunci — Kompresi, Shanon-Fano, Citra
I. PENDAHULUAN Kompresi atau pemampatan data digunakan untuk memperkecil ukuran dari sebuah berkas atau file. Pemampatan data berguna untuk menghemat ruang penyimpanan data. Beberapa hal yang bermanfaat dalam kompresi antara lain :
a) File berukuran besar seperti Citra yang merupakan RAW data biasanya berukuran besar seperti file .BMP b) Dengan berkurangnya ukuran citra di atas maka secara otomatis akan menghemat ruang penyimpanan data
252
Seminar Nasional Teknologi Informatika, "The Future of Computer Vision", 2017, ISBN : 978-602-50006-0-7
c) Pemampatan data citra mampu menghemat bandwith dan tentunya akan mempermudah proses transmisi data d) Pengiriman data menjadi lebih cepat seiring dengan ukuran data yang bertambah kecil. Metode yang dibahas pada paper ini adalah pemampatan data dengan menggunakan metode Shannon – Fano. Yaitu dua orang ilmuwan Claude Elwood Shannon (Bells Lab) dan Robert Fano (MIT) pada tahun 1949. Metode Shannon – Fano ini melakukan pengkodean terhadap frekwensi kemunculan karakter dalam kode binary.
3. Profil warna CMYK memiliki kombinasi warna Cyan, Magenta, Yellow dan Black dengan rentang warna dari 0 – 100. 4. Profil warna yang lainnya masih banyak seperti YcBcr, HSV (Hue - Saturation – Value) atau disebut juga dengan HSL (Hue, Saturation, Lumination) dan lain sebagainya [3].
II. LANDASAN TEORI a) Citra Citra merupakan representasi dari sebuah objek. Citra merupakan keluaran data dengan sifat analog, sinyal video seperti yang ditampilkan oleh Televisi atau monitor komputer, LCD, Camera dan lain – lainnya. Hasil keluaran tersebut disimpan dalam media penyimpanan seperti hardisk atau pita magnetic [6].
Gambar 2. Profil warna HSV Sumber : www.processing.org
Sebuah Citra gambar ditampilkan dalam bentuk matrik dua dimensi dapat dilihat pada ilustrasi citra 3 x 3 berikut ini : Width
b) Citra Gambar Citra berupa gambar direpresentasi dengan warna dengan berbagai dimensi. Ada yang berupa dua dimensi ataupun 3 dimensi. Representasi warna memiliki profile yang beragam antara lain : 1. Profil warna RGB (Red, Green, Blue) direpresentasikan dengan 3 warna Merah, Hijau dan Biru dengan rentang warna dari 0 – 255. Warna RGB biasa digunakan untuk tampilan layar monitor, LCD, camera, handphone dan lain – lain
P
P
P
P
P
P
P
P
P
P
P
P
P
P
P
P
Height Gambar 3. Ilustrasi Citra
Berdasarkan gambar di atas, P adalah sebuah piksel dengan atribut koordinat x,y dan warna sesuai dengan Profil warna yang digunakan sesuai penjelasan sebelumnya. c) Algoritma Shannon - Fano Gambar 1. Profil warna RGB Sumber : www.processing.org
2. Profil warna Grayscale. Grayscale atau disebut juga dengan Derajat Keabuan memiliki rentang warna dari 0 – 255 dengan tingkat warna kehitaman.
Pada Tahun 1949, Claude Elwood Shannon dan Robert Fano memperkenalkan teknik kompresi dengan mempertukarkan karakter dengan bilangan binary berdasarkan jumlah frekwensi kemunculan karakter tersebut. Algoritmanya dapat kita lihat sebagai berikut :
253
Seminar Nasional Teknologi Informatika, "The Future of Computer Vision", 2017, ISBN : 978-602-50006-0-7
1. Membuat daftar karakter / simbol dari semua karakter atau simbol yang akan dilakukan kompresi. 2. Mengurutkan simbol tersebut berdasarkan frekwensi kemunculan. Karakter yang memiliki frekwensi kemunculan yang tinggi ditempatkan di sebelah kiri dan yang frekwensi kemunculannya rendah ditempatkan pada posisi sebelah kanan. 3. Membagi daftar menjadi dua bagian dengan total frekwensi bagian kiri dan kanan yang saling mendekati satu sama lain. 4. Membuat Tree dengan kondisi bagian sebelah kiri dengan angka binary 0 dan sebelah kanan dengan angka binary 1 5. Mengulangi bagian 3 dan 4 secara rekursif sehingga semua mencapai posisi Leaf dalam diagram tersebut [2]. Untuk lebih mudah dalam memahami algoritma tersebut di atas, dapat dilihat pada contoh berikut ini. Text : SEMINAR NASIONAL TEKNOLOGI INFORMATIKA Simbol yang muncul pada text tersebut adalah : SEMINAR [spasi] OLTEKGF 1.
Menentukan frekwensi kemunculan dari karakter tersebut di atas
G
1
F
1
Total Frekwensi
38
Gambar 4. Tabel Frekwensi simbol
2. Membagi dua dengan total frekwensi kemunculannya yang mendekati antara kiri dan kanan. Untuk contoh berikut ini dibedakan dengan atas dan bawah. Sebagai Pembeda antara kiri dan kanan, berikut ini contoh dilakukan dengan memberikan warna yang berbeda seperti berikut ini.
S
F
CODE
S
2
0
E
2
0
M
2
0
I
5
0
N
5
0
A
5
0
R
2
1
SPACE
3
1
O
4
1
SIMBOL
FREKWENSI
L
2
1
S
2
T
2
1
E
2
K
2
1
M
2
G
1
1
I
5
F
1
1
N
5
A
5
R
2
SPACE
3
O
4
S
F
C
L
2
S
2
0
0
T
2
E
2
0
0
K
2
M
2
0
0
Gambar 5. Membagi kode binari
3. Proses dilakukan secara rekursif sampai semua bagian habis menjadi daun.
254
Seminar Nasional Teknologi Informatika, "The Future of Computer Vision", 2017, ISBN : 978-602-50006-0-7
I
5
0
0
I
5
0
0
1
1
N
5
0
1
N
5
0
1
0
A
5
0
1
A
5
0
1
1
R
2
1
0
R
2
1
0
0
0
Space
3
1
0
Space
3
1
0
0
0
O
4
1
0
O
4
1
0
1
1
L
2
1
1
L
2
1
1
0
0
T
2
1
1
T
2
1
1
0
0
K
2
1
1
K
2
1
1
1
1
G
1
1
1
G
1
1
1
1
1
F
1
1
1
F
1
1
1
1
1
Gambar 6. Membagi kode binary Gambar 8. rekursif proses membagi kode binary
S
F
C
S
F
C
S
2
0
0
0
S
2
0
0
0
0 0
E
2
0
0
0
E
2
0
0
0
0 1
M
2
0
0
0
M
2
0
0
0
1
I
5
0
0
1
I
5
0
0
1
1
N
5
0
1
0
N
5
0
1
0
A
5
0
1
1
A
5
0
1
1
R
2
1
0
0
R
2
1
0
0
0 0
Space
3
1
0
0
Space
3
1
0
0
0 1
O
4
1
0
1
O
4
1
0
1
1
L
2
1
1
0
L
2
1
1
0
0 0
T
2
1
1
0
T
2
1
1
0
0 1
K
2
1
1
1
K
2
1
1
1
1 0
G
1
1
1
1
G
1
1
1
1
1 1
F
1
1
1
1
F
1
1
1
1
1 1
Gambar 7. rekursif proses membagi kode binary
S
F
C
S
2
0
0
0
E
2
0
0
M
2
0
0
Gambar 9. rekursif proses membagi kode binary
S
F
C
0
S
2
0
0
0
0 0
0
0
E
2
0
0
0
0 1
0
1
M
2
0
0
0
1
255
Seminar Nasional Teknologi Informatika, "The Future of Computer Vision", 2017, ISBN : 978-602-50006-0-7
I
5
0
0
1
N
5
0
1
A
5
0
R
2
Space
1
I
5
0
0
1
1
4
0
N
5
0
1
0
3
1
1
A
5
0
1
1
3
1
0
0
0 0
R
2
1
0
0
0
0
5
3
1
0
0
0 1
Spc
3
1
0
0
0
1
5
O
4
1
0
1
1
O
4
1
0
1
1
L
2
1
1
0
0 0
L
2
1
1
0
0
0
5
T
2
1
1
0
0 1
T
2
1
1
0
0
1
5
K
2
1
1
1
1 0
K
2
1
1
1
1
0
4
G
1
1
1
1
1 1
G
1
1
1
1
1
1
0
5
F
1
1
1
1
1 1
F
1
1
1
1
1
1
1
5
3
Gambar 12. menentukan jumlah bit Gambar 10. rekursif proses membagi kode binary
S
F
BINARY
S
2
0
0
0
0
E
2
0
0
0
0
M
2
0
0
0
I
5
0
0
1
N
5
0
1
A
5
0
R
2
Spc
S
F
0
S
2
0
0
0
0
0
5
10
1
E
2
0
0
0
0
1
5
10
1
M
2
0
0
0
1
4
8
1
I
5
0
0
1
1
4
20
0
N
5
0
1
0
3
15
1
1
A
5
0
1
1
3
15
1
0
0
0
0
R
2
1
0
0
0
0
5
10
3
1
0
0
0
1
Sp
3
1
0
0
0
1
5
15
O
4
1
0
1
1
O
4
1
0
1
1
3
12
L
2
1
1
0
0
0
L
2
1
1
0
0
0
5
10
T
2
1
1
0
0
1
T
2
1
1
0
0
1
5
10
K
2
1
1
1
1
0
K
2
1
1
1
1
0
4
8
G
1
1
1
1
1
1 0
G
1
1
1
1
1
1
0
5
5
F
1
1
1
1
1
1 1
F
1
1
1
1
1
1
1
5
5
bit F x bit
Total F x bit
Gambar 11. rekursif proses membagi kode binary
BINARY
BINARY
S
F
bit
S
2
0
0
0
0
0
5
E
2
0
0
0
0
1
5
M
2
0
0
0
1
4
153
Gambar 13. perkalian frekwensi dengan bit
Total Frekwensi = 38 Total F x bit = 153 Ratio Kompresi = (100% - 38/153 x 100) = 75% [1]
256
Seminar Nasional Teknologi Informatika, "The Future of Computer Vision", 2017, ISBN : 978-602-50006-0-7
III.
PEMBAHASAN TERHADAP CITRA
SHANNON – FANO
Implementasi Shannon – Fano pada citra dapat dilakukan dengan cara mengambil nilai – nilai semua piksel dan membentuk simbol – simbol. Pengambilan simbol secara sequential dilakukan tehadap semua nilai – nilai warna yang terdapat pada piksel. Berikut ini contoh implementasi pada citra Grayscale ukuran resolusi 3 x 3 dpi [5].
10
4
0
0
11
3
0
1
18
2
1
Gambar : 3.4. Rekursif proses sebelumnya
Langkah 5 : Melakukan menghitung nilai desimal dari code binari.
10
11
10
S
F
C
11
18
10
10
4
0
0
2
10
11
18
11
3
0
1
2
18
2
1
Gambar 3.1. Contoh pixel 3 x 3 mode grayscale
Berikut ini langkah penyelesaian dalam pengolahan citra [4] : Langkah 1 :
Bit
1
Gambar 3.5. Menghitung jumlah bit
Langkah 6 :
mengumpulkan simbol menjadi deretan angka sebagai berikut : S
F
langkah 2 :
10
4
0
0
2
8
Membentuk tabel dengan menghitung frekwensinya dari simbol dan nilai frekwensi kemunculannya.
11
3
0
1
2
6
18
2
1
1
2
10 11 10 11 18 10 10 11 18
Kode binari Bit F x B
Gambar 3.6. Perkalian Frekwensi dengan bit
SIMBOL
FREKWENSI
10
4
11
3
S
F
18
2
10
4
0
0
2
8
11
3
0
1
2
6
18
2
1
1
2
Gambar 3.2. Jumlah Frekwensi kemunculan
Langkah 3 : menguraikan frekwensi kemunculan dalam binari code SIMBOL FREKWENSI CODE
Kode binari Bit F x B
Total F x B
16
Gambar 3.7. Total Perkalian Frekwensi dengan bit
10
4
0
Berdasarkan ditentukan
11
3
0
Total Frekwensi (jumlah byte sebelum kompresi) : 9 Byte
18
2
1
Gambar 3.3. Membagi dan memberikan kode binari
hitungan
di
atas,
maka
dapat
Total F x B : 16 Bit Rasio
= (100% – 16 / 9 x 100%) = 22%
Langkah 4 : Melakukan proses rekursif langkah 3 S
F
CODE
Berdasarkan hitungan di kompresinya sebesar 22%
atas,
maka
ratio
257
Seminar Nasional Teknologi Informatika, "The Future of Computer Vision", 2017, ISBN : 978-602-50006-0-7
IV. KESIMPULAN DAN SARAN A. Kesimpulan Algoritma Shannon-Fano dapat digunakan pada teks dan citra digital yang berguna untuk memampatkan ukuran file teks maupun citra digital agar menghemat memori penyimpanan, B. Saran Pada penelitian selanjutnya, bisa dilakukan perbandingan rasio kompresi antara Shannon-Fano dan Huffman Code sehingga dapat dilihat algoritma kompresi mana yang lebih akurat dalam melakukan pemampatan file teks maupun citra. DAFTAR PUSTAKA [1] Sutardi, “Implementasi dan Analisis Kinerja Algoritma Shannon-Fano untuk Kompresi File Text“, Dinamika, Jurnal Ilmiah Teknik Mesin, 2014 [2] Christine Lamorahan, Benny Pinontoan, Nelson Nainggolan, “Data Compression Using Shannon-Fano Algorithm” jDC, 2014 [3] Muhammad Khoiruddin H, “Analisa Human Skin Detection Menggunakan HSV, Salt and Pepper Noise Reduction”, USU, 2016 [4] Rismawati, Satria Gunawan Zain“Implementasi Kompresi Citra Menggunakan Algoritma Shannon-Fano”, Prosiding Nasional ISBN : 978602-9075-25-7 [5] Maria Roslin Apriani Neta, “Perbandingan Algoritma Kompresi Terhadap Objek Citra Menggunakan JAVA ”, SEMANTIK 2013, 2013 [6] Kadir, Abdul. “Teori Pengolahan Citra”, Yogyakarta : 2012.
258
