KOMPRESI CITRA MENGGUNAKAN METODE RUN LENGTH ENCODING (RLE) DAN ALGORITMA ARITMETIC CODING

Jurnal INFOTEK, Vol 1, No 2, Juni 2016

ISSN 2502-6968 (Media Cetak)

KOMPRESI CITRA MENGGUNAKAN METODE RUN LENGTH ENCODING (RLE) DAN ALGORITMA ARITMETIC CODING Khairul Fahmi (12110019) Mahasiswa Program Studi Teknik Informatika, STMIK Budidarma Medan Jl. Sisimangaraja No.338 Simpang Limun Medan WWW.stmik-budidarma.ac.id//Email : [email protected] ABSTRAK Metode Run Length Encoding menggunakan prinsip bahwa nilai derajat keabuan yang sering muncul di dalam citra akan dikodekan dengan jumlah bit yang lebih sedikit sedangkan nilai keabuan yang frekuensi kemunculannya sedikit akan dikodekan dengan jumlah bit yang lebih panjang. Algoritma Aritmetic Coding adalah suatu bagian dari entropy encoding yang mengkonversi suatu data ke dalam bentuk data yang lain dengan lebih sering menggunakan sedikit bit dan jarang menggunakan lebih banyak bit karakter. Teknik pengkodean ini memisahkan pesan masukan ke dalam simbol dan menukar masing-masing simbol dengan suatu floating-point. Dalam skripsi ini, penulis menggabukan dua metode yang berbeda yaitu metode Run Length Encoding (RLE) Dan algoritma Aritmetic Coding, dengan tujuan untuk mengetahui apakah hasil kompresi menjadi lossless compression atau lossy compression karna Arithmetic Coding lebih banyak diaplikasikan pada file-file dokumen umum, sedangkan Run Length Enkoding. lebih banyak dimanafaatkan untuk citra. Kata Kunci : Algoritma Aritmetic Coding, Metode Run Length Encoding, Citra 1. Pendahuluan 1.1 Latar Belakang Kompresi gambar adalah proses umuk meminimalisasi jumlah bit yang mempresentasikan suatu gambar sehingga ukuran file menjadi lebih kecil. Ada dua tipe kompresi yaitu tipe lossless dan kompresi tipe lossy. Kompresi tipe losseless adalah kompresi dimana kualitas hasil kompresi tidak menurun ketika direkontruksi. Sedangkan tipe lossy akan menghasilkan kualitas gambar yang dihasilkan jauh lebih rendah dari pada kualilas citra asli ketika direkontruksi. Pada skripsi ini, penulis membahas tentang kompersi citra menggunakan dua merode yaitu metode Run Length Encoding (RLE) Dan algoritma Aritmetic Coding, Pada kompresi pertama digunakan metode Run Length Encoding, dan output hasil kompresi metode Run Length Encoding dijadikan data untuk kompresi selanjutnya yang menggunakan algoritma arithmetic coding, dengan tujuan untuk mengetahui apakah hasil kompresi menjadi lossless compression atau lossy compression karna Arithmetic Coding lebih banyak diaplikasikan pada file-file dokumen umum, sedangkan Run Length Enkoding. lebih banyak dimanafaatkan untuk gambar. Tujuan lainnya adalah untuk mengetahui hasil kompresi apakah hasil kompresi lebih sedikit dibandingkan citra yang tidak dikompresi. karna tujuan utama adalah untuk meminimalkan storage.

1.2 Rumusan Masalah Berdasarkan uraian pada latar belakang, maka yang menjadi perumusan masalah adalah : 1. Bagaimana cara kerja dari metode Run Length Enkoding, algoritma Arithmetic Coding dalam mengkompresikan citra ? 2. Bagaimana tingkat efisiensi hasil kompresi dengan menggunakan metode Run Lengt Encoding dan algoritma Arithmetic Coding ? 3. Bagaimana merancang aplikasi kompresi citra dengan mengimplementasikan metode Run Length Encoding, algoritma Arithmetic Coding ? 1.3 Batasan Masalah Dengan rumusan masalah yang telah disebutkan diatas, Penulis membatasi permasalahan yang akan diteliti yakni sebagai berikut : 1. Dalam mengkompresi citra digunakan dua metode yaitu metode Run Length Encoding dan algoritma Arithmetic Coding 2. Pada kompresi pertama digunakan metode Run Length Encoding, dan output hasil kompresi metode Run Length Encoding dijadikan data untuk kompresi selanjutnya yang menggunakan algoritma Arithmetic Coding. 3. Jenis Citra yang digunakan adalah citra Grayscale dengan ukuran mulai dari 48 x 65 pixel sampai dengan ukuran 5000 x 500 pixel dan Jenis file citra input dengan format Bit Map.

kompresi citra menggunakan metode run length encoding (rle) dan algoritma aritmetic coding Oleh : Khairul fahmi (12110019)

74


4.

Bahasa pemograman yang digunakan adalah Microsoft Visual Basic 2008 5. Sofware pendukung dalam penulisan skripsi adalah Matlab 7.1 dan Photoshop CS3. 1.4 Tujuan dan Manfat Penelitian 1.4.1 Tujuan Penelitian Tujuan penulis melakuan penelitian ini, yaitu 1. Untuk mengetahui cara kerja dari Metode Run Length Enkoding, algoritma Arithmetic Coding dalam mengkompresikan citra. 2. Untuk mengetahui tingkat efisiensi hasil kompresi dengan menggunakan metode Run Lengt Encoding dan algoritma Arithmetic Coding. 3. Untuk merancang aplikasi kompresi citra dengan mengimplementasikan metode Run Length Encoding, algoritma Arithmetic Coding. 1.4.2 Manfaat Penelitian Manfaat yang diharapkan dari penelitian ini adalah : 1. Dapat membantu user dalam mengurangi ukuran citra. 2. Dapat meminimalkan kebutuhan memori. 2. LANDASAN TEORI 2.1 Kompresi Data Proses kompresi merupakan proses mereduksi ukuran suatu data untuk menghasiikan representasi digital yang padat atau mampat (compact) namun tetap dapat mewakili kuantitas informasi yang terkandung pada data tersebut. Pada citra, video, dan audio, kompresi mengarah pada minimisasi jumlah bit rate untuk representasi digital. Pada beberapa literatur, istilah kompresi sering disebut juga source coding, data compression, bandwidth compression, dan signal compression. 2.2 Kompresi Lossless dan Lossy Berdasarkan kandungan informasi pada citra hasil maka sifat kompresi data dapat dikelompokkan menjadi dua yaitu kompresi lossless (nir-rugi) dan kompresi lossy (ber-rugi) : 1. Kompresi Lossless Pada kompresi jenis ini informasi yang terkandung pada citra hasil sama dengan informasi pada citra asli. Citra hasil proses kompresi dapat dikembalikan secara sempurna menjadi citra asli, tidak terjadi kehilangan informasi, tidak terjadi kesalahan informasi. Oleh karena itu metode ini disebut juga error free compression. Pada kompresi lossless, karena harus mempertahankan kesempurnaan informasi, sehingga hanya terdapat proses coding dan decoding, tidak terdapat proses kuantisasi. Kompresi tipe ini cocok diterapkan pada berkas


basis data (data base), spread sheet, berkas word processing, citra biomedis, dan Iain sebagainya. 2. Kompresi Lossy Kompresi data yang bersifat lossy mengijinkan terjadinya kehilangan sebagian data tenentu dari pesan tersebut, sehingga dapat menghasilkan rasio kompresi yang tinggi. Apabila citra terkompresi direkonstruksi kembali maka hasilnya tidak sama dengan citra aslinya, tetapi informasi yang terkandung tidak sampai berubah atau hilang. Sebagian besar kompresi data lossy memiliki pengaturan tingkat kompresi yang berbeda-beda. Hal ini dilakukan agar kompresinya lebih efektif dan informasi yang terkandung pada citra tidak sampai berubah dan hilang. Kompresi data lossy ini efektif jika diterapkan pada penyimpanan data analog yang didigitasi seperti gambar, video, dan suara. ilustrasi kompresi lossless dan lossy ditunjukkan pada gambar 1 dan 2.

Gambar 1 Ilustrasi kompresi lossless

Gambar 2 Ilustrasi kompresi lossy 2.4 Kriteria Kompresi Citra Kriteria yang digunakan untuk mengukur pemampatan citra adalah : 1. Waktu kompresi dan Waktu dekompresi Proses kompresi merupakan proses mengodekan citra (encode) sehingga diperoleh citra dengan representasi kebutuhan memori yang minimum. Citra terkompresi disimpan dalam file dengan format tertentu, misalnya JPEG (Joint Photographic Experts Group). Sedangkan proses dekompresi adalah proses untuk menguraikan citra yang dimampatkan untuk dikembalikan lagi (decoding) menjadi citra yang tidak mampat. Algoritma pemampatan yang baik adalah algoritma yang membutuhkan Waktu untuk


75


kompresi dan dekompresi paling sedikit (paling cepat). 2. Kebutuhan memori Metode kompresi yang baik adalah metode kompresi yang mampu mengompresi file citra menjadi file yang berukuran paling minimal. Algoritma pemampatan yang baik akan menghasilkan memori yang dibutuhkan untuk menyimpan hasil kompresi yang berkurang secara berarti. Biasanya semakin besar persentase pemampatan, semakin kecil kebutuhan memori yang diperlukan sehingga kualitas citra makin berkurang. Dan, sebaliknya, semakin kecil persentase citra yang dimampatkan, semakin bagus kualitas hasil pemampatan tersebut. 3. Kualitas pemampatan (fidelity) Metode kompresi yang baik adalah metode kompresi yang mampu mengernbalikan citra hasil kompresi menjadi citra semula tanpa kehilangan infonnasi apa pun. Kalaupun ada infonnasi yang hilang akibat pemampatan, sebaiknya hal itu ditekan seminimal mungkin. Biasanya semakin berkualitas hasil pemampatan, semakin besar memori yang dibutuhkan. Sebaliknya, semakin jelek kualitas citra hasil pemampatan, semakin kecil kebutuhan memori yang harus disediakan. Kualitas citra hasil pemampatan dapat diukur secara kuantitatif menggunakan besaran PSNR (peak signal-to-noise ratio). Semakin besar nilai PSNR maka citra hasil pernampatan semakin mendekati ,citra aslinya, dengan kata lain semakin bagus kualitas citra hasil pemampatan tersebut. Sebaliknya, semakin kecil nilai PSN , semakin jelek kualitas citra hasil pemampatan. Rumus untuk menghitung PSNR adalah sebagai berikut. 𝑀𝑎𝑘𝑠 PSNR = 20 log10 ( 𝑟𝑚𝑠 ) Maks adalah nilai intensitas terbesar. Nilai rms dihitung dengan persamaan berikut 𝑟𝑚𝑠

√

𝑁

1 ∑ 𝑀𝑥𝑁 𝑖=1

𝑀

∑( 𝑓𝑖𝑗0 − 𝑓𝑖𝑗𝑖 )2 𝑗=1

Dalam hal ini, M dan N masing-masing adalah 0 𝑖 lebar dan tinggi citra, ∫𝑖𝑗 dan ∫𝑖𝑗 masing-masing adalah nilai intensitas baris ke-i dan kolom ke-j dari citra hasil pemampatan dan citra sebelum dimampatkan. PSNR mempunyai satuan desiBel (dB) 2.5 Metode Run Length Encoding (RLE) Algoritma RLE menggunakan pendekatan ruang. Algoritma ini cocok digunakan untuk memampatkan citra yang memiliki kelompok-


kelompok piksel berderajat keabuan yang sama. Metode ini dilakukan dengan menyatakan seluruh baris citra rnenjadi sebuah baris run, lalu menghitung run-length untuk setiap deraj at keabuan yang berurutan. 2.6 Metode Arithmetic Coding Pada umumnya, algoritma kompresi citra melakukan penggantian satu atau lebih simbol input dengan kode tertentu. Berbeda dengan cara tersebut, pengodean aritmatik menggantikan satu deretan simbol input dengan sebuah bilangan floating point. Semakin panjang dan semakin kompleks pesan yang dikodekan, semakin banyak bit yang diperlukan untuk keperluan tersebut. Output dari pengodean arimatik adalah satu angka yang lebih kecil dari 1 dan lebih besar atau sama dengan 0. Angka ini secara unik dapat di decode sehingga menghasilkan deretan simbol yang dipakai untuk menghasilkan angka tersebut. Untuk menghasilkan angka output tersebut, tiap simbol yang akan di encode diberi satu set nilai probabilitas. 3. ANALISA DAN PERANCANGAN 3.1 Analisa Proses awal analisisa kompresi yang dilakukan seperti mengubah citra analog menjadi citra digital dengan mengahasilkan ukuran 376 x 508 pixel, kemudian merubah menjadi citra garayscale yang berukuran 48 x 65 pixel dengan menggukan aplikasi photoshop, selanjutnya disimpan dengan format .BMP selanjutnya melakukan pencarian nilai desimal dari citra grayscale tersebut dengan menggunakan sofware matlab, dengan tujuan sebagai data yang akan digunakan untuk melakukan kompresi menggunakan metode Run Length Encoding dan Aritmetic Coding. 3.2 Cara Kerja Metode Run Lenght Encodin dan Aritmetic Coding dalam Kompresi Citra Untuk melakaukan kompresi citra menggunakan metode Run Length Encoding dan Aritmetic terdapat beberapa proses yang akan dilakukan : 1. Proses Encoding dalam kompresi Proses encoding dalam kompresi bertujuan untuk mengurangi ukuran citra sehingga memori yang dibutuhkan menjadi lebih sedikit dari pada citra yang belum dikompresi. 2. Proses Decoding dalam kompresi Proses decoding dalam kompresi bertujuan untuk mengembalikan data yang sudah dikompresi. 3.3 Proses Enconding Menggunakan metode Run Leght Encoding Teknik kompresi Run Length Encoding bekerja berdasarkan sederetan karakter yang berurutan. Data masukan akan dibaca dan sederetan karakter yang


76


sesuai dengan deretan karakter yang sudah ditentukan sebelumnya disubtitusi dengan kode tertentu. Adapun algoritma kompresi menggunakan motode Run Length Encoding adalah : 1. Cari deretan karakter yang sama secara berurutan, jika ada lakukan kompresi data. 2. Tuliskan detetan bit untuk menyatakan jumlah karakter yang sama berurutan. 3. Tuliskan deretan bit yang menyatakan karakter yang berulang. 4. Ulangi langkan 1-4 samapai karakter terakhir. penulis mengimplementasiakan kompresi citra dengan ukuran 3 x 3, dengan tujuan untuk menggetahui cara kerja kompresi Run Length Enconding dalam kompresi citra, maka sebagai berikut nilai decimal dari citra grayscale 3 x 3 : Tabel 1 Citra Grayscale 3 x 3

Gambar 3 fahmi_grayscale.bmp Selanjutnya mengkompresi citra grayscale diatas menggunakan metode Run Legh Encoding, maka seperti inilah hasil dari kompresi citra grayscale : (238,1 ) (255, 2) (238,1) (221,2) (255,1) (204,2) Setelah selesai melakukan kompresi menggunakan menggunakan metode Run Lengh Encoding, selanjutnya penulis melakukan pengkodean dari data tersebut, maka seperti dibawah inilah hasil : 238,1 255,2 238,1 221,2 255,1 204, 2 Semuanya =12 pixel Ukuran citra sebelum dikompresi 3 x 3 x 8 bit = 72 bit Ukuran citra setelah dikompresi = 12 x 8 bit = 96 bit 96 Rasio pemampatan = (100% − 72 𝑥 100%) = −33% artinya -33% dari citra semula telah dimampatkan. 3.4 Proses Enconding Menggunakan Algoritma Aritmetic Coding Setelah penulis mendapakan hasil kompresi metode Run Length Encoding selanjutnya penulis melakukan encode menggunakan metode Aritmetic Coding, Algoritma aritmetic Coding melakukan penggantian suatu deretan symbol input dengan sebuah bilangan floating point. Semangkin panjang


dan semangkin kompleks pesan yang dikodekan, akan semangkin banyak bit yang diperlukan untuk keperluan tersebut. Output dari pengodean aritmetik adalah suatu angka yang lebih kecil dari 1 dan lebih besar atau sama dengan 0. Adapun algoritma kompresi menggunakan algoritma Aritmetic Coding adalah : 1. Menyatakan interval awal [0;1]. 2. Mengulangi dua langkah berikut ini untuk setiap symbol dalam rangkaian data masuk : a. Bagi interval menjadi beberapa subinterval dengan ukuran yang sesuai dengan peluang symbol tersebut. b. Pilih subintercal untuk symbol dan definisikan sebagai intercal baru. Hal ini dilakukan dengan cara memperbarui nilai [low; high]. Jika CR adalah panjang interval lama, high_range (symbol) adlah batas atas symbol X, low_range (symbol) adalah batas bawah symbol, maka nilai [newlow; newhigh] dapat dihitung dengan persamaan: High = low + CR * high_range (symbol) Low= low + CR * low_range (symbol) 3. Hasil ahkirnya adalah seuah bilangan tunggal yang berada di dalam interval akhir. Sebelum melakukan kompresi menggunakan Aritmetic Coding, terlebih dahulu harus memahami setiap karakter yang ada, maka seperi dibawah ini keterangan karakter : Karakter = adalah menerangkan karakter yang akan dikompresi. Probabilitas = jumlah keluarnya frekuensi dalam satu karakter dikali dengan jumlah keseluruhan karakter. Low = nilai low awal didapat dari nilai terendah range, dan nilai low selanjutnya nilai low yang kedua dan seterusnya didapat dari nilai Low ditamba nilai CR dikali dengan nilai Low_range. High = nilai low awal didapat dari nilai tertinggi range, selanjutnya nilai low yang kedua dan seterusnya didapat dari nilai Low ditamba nilai CR dikali dengan nilai High_range CR = nilai high dikurang dengan nilai low High_range= nilai didapat dari nilai tertinggi dari satu karakter Low_range = nilai didapat dari nilai terrendah dari satu karakter Untuk menggetahui cara kerja kompresi Aritmetic Coding, penulis mengimplementasikan


77


dengan menggunakan data hasil kompresi Run Legh Encoding, maka seperti dibawah inilah data yang akan di kompresi : 238,1 255,2 238,1 221,2 255,1 204, 2 selanjutnya penulis menentukan nilai probabilitas tiap-tiap simbol yang akan di encode menggunakan algoritma Aritmetic Coding, maka seperti inilah nilai simbol-simbol probabilitas pada table dibawah ini: Tabel 3 Tabel Probabilitas Citra Grayscale 3 x 3 Setelah probabilitas tiap karakter diketahui, tiap simbol/karakter akan diberikan range tertentu yang nilainya berkisar antara 0 dan 1, sesuai probabilitas yang ada. Dalam hal ini tidak ada ketentuan uruturutan penentuan segmen, asalkan antara encoder dan decoder melakukan hal yang sama. Selanjutnya, diperoleh table berikut : Tabel 1 Probabilitas dan Range Citra Grayscale Karakter Frekuensi Probabilitas Range 1 2 204 221 238 255

0,0< 1 < 0,2 0,2< 2 < 0,4 0,4< 204 < 0,5 0,5< 221 < 0,6 0,6< 238 < 0,8 0,8< 255 < 1,0 Satu hal yang perlu dicatat dari table ini adalah tiap karakter melingkupi range yang disebutkan, kecuali bilangan tinggi. Sebelum penulis melakukan kompresi, terlebih dahulu penulis menerangkan maksud dari tiap karakter. Untuk string “238,1 255,2 238,1 221,2 255,1 204, 2 ” diatas, pertama kita ambil karakter pertama yaitu “ 238”. Low = 0,0 (kondisi awal) High = 1,0 (kondisi awa1) CR1 = high-low = 1,0 - 0,0 =1

3 3 1 1 2 2

3/12 = 0,2 3/12 = 0,2 1/12 = 0,1 1/12 = 0,1 2/12 = 0,2 2/12 = 0,2


High_range (238) = 0,8 Low_range (238) = 0,6 Kemudian, didapatkan nilai-nilai berikut. High = low + CR*high_range (238) = 0,0 + 1* 0,8 = 0,8 Low = low + CR*low_range (238) = 0,00 + 1 * 0,6 = 0,6 Kemudian, karakter kedua “1” diambil dan diperoleh Karakter 1 2 204 221 238 255

Frekuensi

Probabilitas

3 3 1 1 2 2

3/12 = 0,2 3/12 = 0,2 1/12 = 0,1 1/12 = 0,1 2/12 = 0,2 2/12 = 0,2

: low = 0,6 (hasil perhitungan dari karakter 238) high = 0,8 (hasil perhitungan dari karakter 238) CR2 = high - low = 0,8 – 0,6 = 0,2 High_range (1) = 0,2 Low_range (1) = 0,0 Kemudian, didapatkan nilai-nilai berikut. High = low + CR*high_range (1) = 0,6 + 0,2 * 0,2 = 0,64 Low = low + CR*low_range (1) = 0,6 + 0,2 * 0,0 = 0,6 Kemudian, karakter ketiga “255” diambil sehingga diperoleh : low = 0,6 high = 0,64 CR3 = high – low = 0,64 - 0,6 = 0,04 High_range (255) = 1,0 Low_range (255) = 0,8 Kemudian, nilai-nilai berikut didapatkan. High = low + CR*high_range (255) = 0,6 + 0,04 * 1,0 = 0,64 Low = low + CR*low_range (255) = 0,6 + 0,04 * 0,8 = 0,632 No

Huruf


Low

High

CR 78


Aw


0,00

0,94

0,94

al 1

238

0,6

0,8

0.1

2

1

0,6

0,64

0,2

3

225

0,632

0,64

0,04

4

2

0,6336

0,6352

0,008

5

238

0,63456

0,63488

0,0016

6

1

0,63456

0,634624

0,0003 2

7

8

9

221

2

255

0,634592

0,634598

0,0000

4

64

0,6345932

0,634594

0,0000

8

56

064

0,6345943

0,634594

0,0000

56

0128

0,6345943

0,634594

0,0000

04

3552

00256

0,6345943

0,634594

0,0000

2448

3296

000512

0,6345943

0,634594

0,0000

326528

000051

04

10

11

12

1

204

2

25504

2 4. IMPLEMENTASI 4.2 Perancangan Sistem Setelah dilakukan perancangan sistem maka sistem diimplememtasikan sehingga hasilnya dapat dilihat seperti dibawah ini : 1. Form Kompresi Gambar Form kompresi gambar merupakan form yang disediakan untuk melakukan kompresi yang ada dalam aplikasi kompresi gambar. Form kompresi gambar juga dapat membantu user dalam melakukan dekompresi. Form kompresi dapat dilihat pada gambar 4.

Gambar 4 Tampilan Form Kompresi Gambar Keterangan : 1. Form Kompresi Gambar ini berisikan PictureBox, TextBox dan Button yang berfungsi sebai berikut. 2. pictureBox untuk menampilkan gambar asli dan gambar hasil kompresi. 3. TextBox untuk menampilkan keterangan gambar mulai dari nama gambar, ukuran gambar sebelum dikompresi, ukuran gamabar setelah dikompresi dan lama proses kompresi. 4. Buntton sebagai tombol yang digunakan di aplikasi ini mulai dari mencari gamabar untuk dikompresi, kompresi gamabar, dekompresi gamabar, simpan, batal dan keluar. DAFTAR PUSTAKA 1. Abdul Kadir dan Adhi Susanto 2013 Teori dan Aplikasi Pengolahan Citra, Yogyakarta, Andi. 2. A.S, Rosa dan M. Shalahuddin. 2011. Rekayasa Perangkat Lunak. Yogyakarta. Modula. 3. C. Widyo Hermawan, 2010, visual basic 2008, Semarang, Andi dan Wahana Komputer. 4. Darma putra , 2010 penoglahan citra digital, Yogyakarta, Andi 5. Eko Prasetyo, 2011 pengolahan citra digital dan aplikasinya menggunkan matlab, Yogyakarta, Andi. 6. Heri Hidayat 2011, Menjadi Master Photoshop Untuk Pemula dari Nol Hingga Mahir, Dunia Komputer. 7. Muhammad Sadeli, 2009 Visual basic .net 2008 untuk orang awam, Palembang, Maxikom. 8. T. Sutoyo dan Teman-teman 2009, Teori Pengolahan Citra Digital Yogyakarta, Andi dan Udinus Semarang. 9. T. Sutoyo dan Teman-teman 2010, Teori dan Aplikasi Aljabar Linear Dan Matriks, Yogyakarta, Andi dan Udinus Semarang.


79

KOMPRESI CITRA MENGGUNAKAN METODE RUN LENGTH ENCODING (RLE) DAN ALGORITMA ARITMETIC CODING

Recommend Documents