Tugas Pertemuan 10 Pengolahan Citra

                                                                 Tugas Pertemuan 10

 

 Matakuliah PENGOLAHAN CITRA

 

Kelas :17.5A.07
No.	NIM	Nama
1	17200438	ABDUL AZIZ KARIM ROMADHON

 

Program Studi Teknologi Informasi Fakultas Teknologi Informasi Universitas Bina Sarana Informatika

 

 

 

 

 

 

 

 

 

 

Implementasi Algoritma Kompresi Shannon
– Fano pada Citra Digital

 

Muhammad Khoiruddin Harahap

 

 

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 :

 

 

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 tersebu.

 

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.

 

 

 

 

 

 

Algoritma Shannon-Fano dapat digunakan pada teks dan citra digital yang berguna untuk memampatkan ukuran file teks maupun citra digital agar menghemat memori penyimpanan.

 

 

 

 

 

 

 

 

 

 

 

 

Aplikasi Kode Huffman dalam Kompresi Gambar Berformat

JPEG

 

Ibnu Alam

 

 

Dalam ilmu komputer, JPEG (baca: /ˈdʒeɪpɛg/) adalah metode kompresi yang umum digunakan untuk gambar-gambar fotografi. JPEG merupakan singkatan dari Joint Photographic Experts Group, nama dari komite yang menetapkan standar JPEG. Pada tahun 1994, standar JPEG disahkan sebagai ISO 10918-1.

 

Dalam ilmu komputer dan teori informasi, kode Huffman adalah algoritma pengkodean entropi untuk kompresi data lossless. Istilah ini merujuk kepada penggunaan tabel kode yang memiliki Panjang bervariasi (variable length code) dimana tabel kode tersebut diturunkan dengan cara tertentu berdasarkan prakiraan probabilitas kemunculan setiap nilai dalam

sumber data. Kode Huffman dikembangkan oleh David A. Huffman pada saat mengambil gelar Ph.D. di MIT. Kode Huffman menggunakan metode spesifik untuk merepresentasikan setiap symbol, menghasilkan prefix-free code (string dari bit representasi sebuah

simbol tidak pernah menjadi prefix [awalan] dari sebuah simbol lain). Yang merepresentasikan karakter yang lebih sering muncul dengan bit string yang lebih pendek daripada karakter yang jarang muncul dalam suatu sumber data. Kompresi Huffman adalah metode

paling efisien dari metode lain yang sejenis karena pemetaan lain simbol dari sumber data menjadi string unik menghasilkan file output yang lebih kecil ketika

frekuensi symbol sesuai dengan frekuensi yang digunakan untuk menghasilkan kodenya. Kemudian ditemukan metode untuk melakukan pemetaan ini dalam waktu linear dengan mengurutkan probabilitas input

 

 

 

 

Untuk suatu set simbol dengan distribusi probabilitas tersebar dan jumlah elemen sebesar kelipatan pangkat dua, kode Huffman setara dengan binary block encoding sederhana. Penggunaan kode Huffman begitu luas sampai-sampai semua kode prefix free disinonimkan dengan Huffman walaupun algoritmanya tidak sesuai dengan Huffman.

 

 

 

 

Misalkan sebuah sumber menghasilkan empat symbol berbeda { a1,a2,a3,a4} dengan probabilitas {0.4;0.35;0.2;0.05}. Dengan membuat pohon biner dari kiri ke kanan (Gbr 4.1-1). Ambil dua buah symbol yang memiliki probabilitas paling rendah, dijumlahkan menjadi probabilitas dua simbol tadi, ulangi sampai hanya ada satu simbol di kanan. Baca pohon terbalik dari kanan ke kiri sambil memberikan kode biner berbeda pada tiap cabang.

 

 

Sebagai cara menjelaskan pengaplikasian kode Huffman ke dalam encoding ke JPEG, digunakan contoh gambar berikut:

 

 

 

Gambar 16x8 piksel, hitam dan putih. Perhatikan gambar ini adalah kelipatan dari blok JPEG yang dibagi dalam 8 x 8 piksel (Minimum Coded Unit [MCU]). Gambar ini tidak memiliki metadata dan tidak memakai optimalisasi, sehingga dalam konversinya ke format JPEG tidak menambah kompleksitas algoritmanya.

 

 

File JPEG mengandung maksimal 4 tabel Huffman dengan kode dengan panjang bervariasi dari 1 hingga 16 bit dan nilai kodenya 8 bit. Tabel Huffman yang dipakai dapat berasal dari standar JPEG atau program image editornya sendiri yang mendefinisikan dengan DCT.

 

 

MEPLEMENTASI ALGORITMA RUN LENGTH ENCODING UNTUK

PERANCANGANAPLIKASI KOMPRESI DAN DEKOMPRESI

FILE CITRA

 

 

Cut Try Utari

 

 

Algoritma RLE menggunakan pendekatan ruang. Algoritma ini cocok digunakan untuk memampatkan citra yang memiliki kelompok – kelompok piksel berderjat keabu – abuan yang sama. Metode ini dilakukan dengan menyatakan seluruh baris citra menjadi sebuah baris run, lalu menghitung run – length untuk setiap derajat keabu – abuan yang berurutan. Contoh, andaikan string “ABBABABACAACDDD” akan di-encode dengan algoritma RLE maka langkahnya adalah sebagai berikut.
    KODE = (A,1)(B,2)(A,1)(B,1)(A,1)(B,1)(A,1)
     (C,1)(A,2)(C,1)(D,3)

Contoh lain, misalnya sebuah citra grayscale 3 bit
berukuran 10 x 10 piksel akan di – encode dengan
algoritma RLE maka :

 

 

7	7	7	7	3	3	3	3	3	3
4	4	5	5	5	5	2	2	2	2
5	5	5	5	6	6	6	6	6	6
7	7	7	6	6	6	6	2	2	2
4	4	3	3	3	3	3	5	5	5
7	7	7	7	7	7	4	4	4	4
0	0	0	0	0	0	0	0	0	0
1	1	1	4	4	2	2	5	5	5

       Citra belum terkompres

 

2	2	7	7	7	7	2	2	2	2
4	4	1	1	1	7	7	7	7	7
7	7	7	7	3	3	3	3	3	3
4	4	5	5	5	5	2	2	2	2
5	5	5	5	6	6	6	6	6	6
7	7	7	6	6	6	6	2	2	2
4	4	3	3	3	3	3	5	5	5
7	7	7	7	7	7	4	4	4	4
0	0	0	0	0	0	0	0	0	0
1	1	1	4	4	2	2	5	5	5

 

  Hasil Kompresi

(2,2) (7,4) (2,4)

(4,2) (1,3) (7,5)

(7,4) (3,6)

(4,2) (5,4) (2,4)

(5,4) (6,6)

(7,3) (6,4) (2,3)

(4,2) (3,5) (5,3)

(7,6) (4,4)

(0,10)

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

 

 

Hasil pengodean :
2 2 7 4 2 4 4 2 1 3 7 5 7 4 3 6 4 2 5 4 2 4 5 4 6 6 7
3 6 4 2 3 4 2 5 5 3 7 6 4 4 0 10 1 3 4 2 2 2 5 3
Semuanya = 52 piksel Ukuran citra sebelum dikompres = 10 x 10 x 3 bit =300 bit Ukuran citra setelah dikompres = 52 x 3 bit = 156 Rasio pemampatan = 100 % - 156 x 100% 300 = 48 %, artinya 48% dari citra semula telah dimampatkan.
Metode RLE sangat cocok untuk citra biner sedangkan untuk citra grayscale, sering kali pengodean hasil kompresi lebih besar disbanding sebelum terkompres. Metode RLE dapat dikombinasikan dengan metode Huffman untukn meningkatkan rasio kompresi. Mula – mula lakukan kompresi RLE, lalu hasilnya dimampatkan lagi dengan metode Huffman.

 

 

 

Keterangan :
1. Menu, Ada beberapa menu pada rancangan
aplikasi kompresi citra RLE ini,yaitu menu File, RLE, About, Help dan Exit.
a. Menu File yang terdiri dari 2 sub menu yaitu : Open, dan exit.
b. Menu RLE yang terdiri dari 2 sub menu yaitu Kompres dan Dekompres.
c. Menu About untuk menampilkan form About.
d. Menu Help untuk menampilkan form Help.
e. Menu Exit untuk keluar dari halaman Aplikasi
Kompresi Citra RLE dan kembali ke Tampilan Utama.
2. Picture Box tempat menampilkan gambar.
3. Label untuk menampilkan judul aplikasi.
4. Command Button Open File Citra untuk
memanggil file citra yang berformat JPG dan BMP.
5. Menu Open File RLE untuk memanggil file citra yang berformat RLE.
6. Picture untuk menampilkan citra yang berformat JPG dan BMP.
7. Vscroll untuk menggeser ke atas dan ke bawah posisi citra pada picture box.

8. Hscroll untuk menggeser ke kiri dan ke kanan posisi citra pada picture box.
9. Label untuk menampilkan lokasi file citra JPG dan BMP tersimpan.
10. TextBox Label untuk menampilkan ukuran file sebelum di-kompres.
11. TextBox untuk menampilkan ukuran file sesudah di-kompres.
12. TextBox untuk menampilkan rasio kompres.
13. TextBox untuk menampilkan lama proses kompres.
14. Command Button Kompres untuk melakukan kompresi file citra yang berformat JPG dan BMP.
15. Label untuk menampilkan lokasi file citra RLE tersimpan.
16. TextBox untuk menampilkan ukuran file sebelum dekompres.

 

 

Flowchart sistem kompresi adalah bagan yang menunjukan alur kerja atau proses kompresi dan dekompresi dengan menggunakan algoritma Run Length Encoding. Rancangan flowchart sistem kompresi dan dekompresi RLE dapat dilihat pada gambar 5.

 

Daftar Pustaka.

 

Muhammad Khoiruddin Harahap, "Implementasi Algoritma Kompresi Shannon – Fano pada Citra Digital", The Future of Computer Vision, 2017, ISBN : 978-602-50006-0-7.

 

Ibnu Alam, 2008, "Aplikasi Kode Huffman dalam Kompresi Gambar Berformat JPEG"

 

Cut Try Utari, " IMPLEMENTASI ALGORITMA RUN LENGTH ENCODING UNTUK PERANCANGANAPLIKASI KOMPRESI DAN DEKOMPRESI FILE CITRA", Jurnal TIMES , Vol. V No 2 : 24-  31 , 2016 ISSN : 2337 - 3601.

 

Kadir, Abdul. “Teori Pengolahan Citra”, Yogyakarta : 2012.

 

Rismawati, Satria Gunawan Zain“Implementasi Kompresi Citra Menggunakan Algoritma Shannon-Fano”, Prosiding Nasional ISBN : 978-602-9075-25-7