## Penerapan Algoritma LZ77 dan Algoritma Difference Coding Untuk Memperkecil Ukuran pada Citra Satelite Geoeye

## Amanda Pratama, Muhammad Syahrizal
Program Studi Teknik Informatika, STMIK Budi Darma, Medan, Indonesia Email: 1 amandapratama2905@gmail.com Submitted 31-03-2020; Accepted 20-04-2020; Published 26-04-2020

## Abstrak
Citra satelit geoeye merupakan salah satu citra satelit yang memiliki resolusi yang tinggi dan mulai populer dalam beberapa tahun terakhir ini.  Sebagasi  salah  satu  citra  satelit  yang  mendunia,  sudah  jelas  citra  satelit  ini  menawarkan  hal  yang  mampu  memukau  siapa  pun penggunanya, citra satelit ini  menawarkan citra permukaan bumi dengan tingkat kedetilan yang bisa dibilang luar biasa, serta tingkat akurasi setelah dibandingkan dengan citra satelit yang memiliki resolusi tinggi lainnya.
Kata Kunci: Algoritma Lz77, Difference Coding, Citra Satelite Geoeye

## Abstract
Geoeye satellite imagery is one of the satellite images that has a high resolution and is gaining in popularity in recent years. As one of the global satellite imagery, it is clear that this satellite image offers something that can amaze anyone of its users, this satellite  image offers an earth surface image with a level of detail that can be considered extraordinary, and the level of accuracy after compared to satellite imagery that has high resolution the other.
Keywords : Lz77 Algorithm, Difference Coding, Geoeye Satellite Image

## 1. PENDAHULUAN
Citra satelit geoeye merupakan salah satu citra satelit yang memiliki resolusi yang tinggi dan mulai populer dalam beberapa tahun terakhir ini. Sebagasi salah satu citra satelit yang mendunia, sudah jelas citra satelit ini menawarkan hal yang mampu memukau siapa pun penggunanya, citra satelit ini  menawarkan citra permukaan bumi dengan tingkat kedetilan yang bisa dibilang luar biasa, serta tingkat akurasi setelah dibandingkan dengan citra satelit yang memiliki resolusi tinggi lainnya.
Kompresi adalah proses mengubah data menjadi sekumpulan kode untuk menghemat tempat penyimpanan dengan atau tanpa mengurangi kualitas dari citra serta mempercepat waktu transmisi data. Pada penggunaannya, ada beberapa faktor yang  sering  menjadi  pertimbangan  dalam  memilih  suatu  metode  kompresi,  yaitu  kecepatan  kompresi,  sumber  daya  yang dibutuhkan (memori, kecepatan PC), ukuran file hasil kompresi serta kompleksitas algoritma, karena pada intinya tidak setiap metode kompresi sesuai untuk semua jenis file gambar.
Adapun permasalahan pada gambar citra satelit geoeye yang mana pada saat proses pengiriman gambar melalui email sering terjadi kegagalan atau tidak dapat dikirim dikarenakan ukuran data pada saat  proses pengiriman pada gambar citra satelit  mempunyai  ukuran  data  yang  cukup  besar  karena  itu  maka  perlu  dilakukan  teknik  kompresi,  yang  mana  nantinya dapat menghasilkan data yang lebih kecil untuk menghemat memori dannantinya secara otomatis memori dapat menyimpan data lebih banyak lagi.
Tujuan dari kompresi terhadap citra digital ini adalah untuk mengurangi redudansi dari data-data yang terdapat dalam citra sehingga dapat disimpan atau ditransmisikan secara efisien. Masalah inilah yang menyebabkan munculnya kebutuhan akan kompresi citra tanpa harus mengurangi informasi yang tersimpan didalam citra tersebut lossless [1].

## 2. METODE PENELITIAN

## 2.1 Kompresi Citra
Kompresi citra adalah proses pemampatan citra yang bertujuan untuk mengurangi duplikasi data pada citra sehingga memory yang digunakan untuk merepresentasikancitra menjadi lebih sedikit dari pada representasi citra sebelumnya [1].

## 2.2 Algoritma Lz77
Algoritma Lz77 merupakan salah satu metode untuk melakukan kompresi data yang dibuat oleh Abrahamem Lempel dan Jacob Ziv pada tahun 1977. Metode kompresi ini dilakukan dengan pencarian kedepan dan belakang, biasa disebut search buffer dan look ahead buffer.
Dalam  blok  dikompresi,  jika  serangkaian  duplikat  byte  adalah  melihat  (string  berulang),  maka referensi  belakang dimasukkan, menghubungkan ke lokasi sebelumnya yang identik string, bukan. Sebuah pertandingan di kodekan ke string sebelumnya terdiri  dari  panjang (3-258 bytes) dan jarak (1  -32.768bytes). Relatif back-referensi  dapat  dibuat di sejumlah blok, asalkan jarak muncul dalam 32 Kb terakhir dari data terkompresi decode (disebut sliding window) [2]. Komponen yang dibutuhkan dalam algoritma kompresi ini adalah:
1. Input Stream = Kumpulan karakter yang akan dikompresi.
2. Character = Elemen dasar pada input stream.
3. Look –ahead buffer = Kumpulan karakter yang belum dikompresi, setelah token.
4. Search buffer = Kumpulan karakter yang telah di kompresi, sebelum token.
5. Token = Berisi kumpulan dari ( offset, length, dan next symbol ).

## 2.3 Algoritma Difference Coding
Pada metode Difference Coding kompresi file yang berbentuk *jpg dilakukan dengan mengurangi nilai pixel dengan nilai pixel sebelumnya. Ada dua tahap utama kompresi dengan metode Difference Coding untuk nilai pixel, yaitu  difference dan coding.  difference  adalah  pengurangan  nilai  pixel    dengan  nilai  pixel  sebelumnya  ke  dalam  nilai  eksak.  Coding  adalah menuliskan  kode  yang  berisi  nilai  pixel  dengan  hasil  pengurangannya.Prinsip  kerja  metode  Difference  Coding  adalah mengurangi nilai pixel dengan nilai pixel sebelumnya.Untuk pixel pada posisi (Index) ke -0 tetap dipertahankan [4].
Sebagai contoh diberikan sampel pixel sebagai berikut: 40 40 40 40 40 43 43 100 102 102 102 adalah 11 byte x 8 bit adalah 88 bit. Data difference adalah selisih data ke dua dengan pertama yaitu 40 – 40 → 0. Data pertama dilakukan coding yaitu 40 ditambah hasil selisih menjadi: 40 0. Selanjutnya lakukan cara difference untuk data 3, 4 dan seterusnya sehingga menghasilkan kode hasil kompresi sebagai berikut: 40 0 0 0 0 3 0 57 2 0 0 0 adalah 4 byte dan 8 bit yaitu 4 byte adalah 4 x 8 bit = 32 bit. Jadi ada 36 bit hasil kompresi.

## 3. HASIL DAN PEMBAHASAN
Kompresi citra bertujuan untuk mengetahui cara kerja dan tingkat efisiens pada metode yang akan digunakan saat kompresi citra  tersebut.  Yang  mana  nantinya  proses  kompresi  dengan  menggunakan  metode Lz77 dan  algoritma difference coding dalam mengkompresi, karna dalam kompresi ini menyatukan dua metode yang berbeda yaitu pada kompresi pertama digunakan metode Lz77 , dan akan dikompresi lagidengan menggunakan algoritma difference coding.

## 3.1 Penerapan Algoritma LZ77 Pada Citra Geoeye
Pada  Penelitian  ini  akan  diuraikan  proses  kompresi  untuk  memperkecil  ukuran  citra  dilakukan  dengan  menerapkan  saat dilakukannya proses kompresi.  Disini penulis membuat sample dengan citra grayscale. Berikut contoh sebuah citra grayscale yang memiliki resolusi 96 dpi dan berukuran 855x 596 pixel yang besar ukuran filenya 806,304 Kbyte.Berikut ini sample gambar citra grayscale satelite geoeye:
Gambar 1. Citra grayscale satelite geoeye
Dimana ukuran citra resolusi 855 x 596 pixel akan diambil sampelnya menjadi 4x4  pixel. Berdasarkan citra di atas di asumsikan nilai piksel dari citra tersebut setelah diperkecil resolusinya menjadi 4x4 pixel sehingga didapat nilai pikselnya menjadi seperti berikut ini
Tabel 1. Tabel Citra Grayscale 4 x 4 2 4 4 5 2 3 4 5 3 2 3 3
5 5 5 5
Matriks tersebut akan dibaca oleh search buffer dari kanan ke kiri seakan membentuk jendela yang bergerak ( sliding windows ) dari kanan ke kiri. Data matriks yang akan di kelompokkan adalah “2 4  4 5 2 3 4 5 3 2 3 3 5 5 5 5”. Kolom sebelah kiri disebut search buffer dan kolom sebelah kanan disebut look-ahead buffer. MetodeKompresi LZ77 merupakan metode kompresi Sliding Windows Compression , struktur data yang berupa text windows akan dibagi menjadi 2 bagian, terdiri dari teks yang sudah dikodekan ( history buffer ) dan bagian lain dari teks yang akan dikodekan ( lookahead buffer ).Berikut ini adalah langkah-langkah kompresi Menggunakan algoritma Lz77 :
1. Hitung jumlah karakter yang ada di lookahead buffer.
2. Setelah dihitung buatlah index yang ada dihistory buffer ..
3. Mencari nilai yang sama dari lookahead buffer ke history buffer . 2. Masukkan nilai lookahead buffer dan history buffer ke output. 3. Ulangi langkah 1 dan 2 sampai karakter yang ada di lookahead buffer habis.
Tabel 2. Algoritma LZ77
Search Buffer Look-Ahead Buffer Output 2445234532335550 (0,0,”2”) 2  445234532335555 (0,0,”4”) 24  45234532335555 (1,1,”2”) 2445  234532335555 (4,1,”4”) 244523  4532335555 (5,4,”2”) 244523453  2335555 (9,4,”5”) 244523453233  5555 (9,2,”5”) 24452345323355  55 (11,4,”5”) 2445234532335550 (0,0,”0”)
Setelah dikelompokan maka matriks diatas dengan menggunakan algoritma LZ77 maka didapat token dari algoritma tersebut seperti berikut :
(0,0,”2”) (0,0,”4”) (1,1,”2”) (4,1,”4”) (5,4,”2”) (9,4,”5”) (9,2,”5”) (11,4,”5”) (0,0,”ǿ”)
Berikut ini hasil dari pengelompokan dengan menggunakan algoritma Lz77 adalah sebagai berikut :“0 0 2 0 0 4 1 1 2 4 1 4 5 4 2 9 4 5 9 2 5 11 4 5 0 0 ǿ” file ini memiliki ukuran sebesar 28 Byte yang berarti memori membutuhkan tempat penyimpanan sebesar 28x8 bit = 224 bit.
Ukuran citra sebelum dikompresi = 16 byte atau 128 bit Ukuran citra setelah dikompresi = 224 bit Rasiopemampatan = 100 – (hasil kompresi / ukuran citra semula) x 100% Rasio pemampatan= 100 – (224 / 128) x 100% Rasio pemampatan=  100 – (1.75) x 100% Rasio pemampatan= 100 – 175 Rasio pemampatan= -75%artinya -75% dari citra semula telah dimampatkan.

## 3.2 Penerapan Difference Coding Pada Citra Geoeye
Setelah penulis mendapakan hasil kompresi  metode Lz77 selanjutnya penulis melakukan kompresi  menggunakan metode Difference Coding. Prinsip kerja metode Difference Coding adalahAda dua tahap utama kompresi dengan metode Difference Coding  untuk  nilai  pixel,  yaitu  difference  dan  coding.    difference  adalah  pengurangan  nilai  pixel    dengan  nilai  pixel sebelumnya  ke  dalam  nilai  eksak.  Coding  adalah  menuliskan  kode  yang  berisi  nilai  pixel  dengan  hasil  pengurangannya. Prinsip kerja metode Difference Coding adalah mengurangi nilai pixel dengan nilai pixel sebelumnya.Untuk pixel pada posisi (Index) ke -0 tetap dipertahankan. Langkah langkah untuk difference coding sebagai berikut : 1.   Baca nilai sampel dari awal sampai akhir.
2. Bandingkan data sampel pertama dengan kedua.
3. Hitung selisihnya.
4.   Coding data sebagai nilai sampel dengan selisihnya.
5.   Ulangi langkah 2 sampai 4 sampai sampel habis.
6. Simpan hasil coding → data terkompresi.
Untuk menggetahui cara kerja kompresi Difference Coding, penulis mengimplementasikan dengan menggunakan data hasil kompresi Lz77, maka seperti dibawah inilah data yang akan di kompresi :
Sampel pixel “0 0 2 0 0 4 1 1 2 4 1 4 5 4 2 9 4 5 9 2 5 11 4 5 0 0” file ini memiliki ukuran sebesar 28 byte atau sama dengan 224 bit.
Selisih  data ke dua dengan pertama yaitu  0– 0 = 0 dan pada data pertama dilakukan coding yaitu  0 ditambah hasil selisih menjadi: 0 2, selanjutnya lakukan cara difference untuk data 3, 4 dan seterusnya sehingga menghasilkan kode hasil kompresi sebagai berikut: “0 2 2 0 4 3 0 1 2 3 3 1 1 2 7 5 1 4 7 3 6 7 3 1 5 0”sebanyak 26 byte atau 208 bit. Ukuran citra hasil kompresi Lz77   = 28 x 8 bit = 224 bit Ukuran citra hasil difference coding  = 26 x 8 bit = 208 bit
Rasio = 100–(hasil kompresiLz77/ hasil kompresi Difference coding) x 100% Rasio = 100– (224 / 208) x 100% Rasio = 100–  108 Rasio =  - 8% artinya -8% dari citra semula telahdimampatkan. Keterangan:
1. Metode Lz77 cocok untuk kompresi citra yg memiliki deretan nilai pixel yang sama dalam satu baris.
2. Hasil kompresi metode Lz77 akan menjadi lebih banyak jika deretan nilai pixel berbeda-beda dalam satu baris.

## 4. KESIMPULAN
Berdasarkan hasil analisa pada bab-bab sebelumnya maka penulis dapat menarik  kesimpulan yang mana kesimpulan tersebut nanti  dapat  kiranya  berguna  bagi  pembaca  ,  sehingga  penulisan  ini  dapat  berguna  dan  bermanfaat.  Adapun  kesimpulan- kesimpulan yang penulis berikan adalah sebagai berikut:
1. Dalam proses menentukan ukuran pixel pada citra geoeye dengan menggunakan aplikasi Matlab 2013 yang mana setelah didapat  jumlah  pixelnya  penulis  menggunakan  sample  4x4  pixel  untuk  diterapkan  pada  metode  Lz77  dan  Difference Coding.
2. Cara kerja metode Lz77 dalam mengkompresi adalah semakin besar history buffer dan lookahead buffer akan membuat banyak pola pixel yang sama pada gambar yang akan berpengaruhi terhadap kecil dan besarnya ukuran hasil kompresi. Untuk cara kerja algoritma Difference coding dalam mengkompresi citra dengan cara mengurangi nilai pixel dengan nilai pixel sebelumnya Ada dua tahap utama kompresi dengan metode Difference Coding untuk nilai pixel, yaitu  difference dan coding. difference adalah pengurangan nilai pixel  dengan nilai pixel sebelumnya ke dalam nilai eksak. Coding adalah menuliskan kode yang berisi nilai pixel dengan hasil pengurangannya.

## REFERENCES
[1] Sutojo. T. Mulyanto. E, "Kompresi Citra," in Pengolahan Citra Digital, Yogyakarta, Penerbit Andi, 2009, pp. 165-168.
[2] Darma Putra, "Pengolaha Citra," Yogyakarta, Andi, 2010, p. 290.
[3] P.  Barita,  "A  Comparative  Study  of  Image  Format  Compression  Deflate  Algorithms,"  A  Comparative  Study  of  Image  Format Compression Deflate Algorithms, vol. 6, no. 12, 2017.
[4] T. Mizwar, G. L. Ginting, Mesran, A. Fau, S. Aripin, and D. Siregar, “IMPLEMENTASI ALGORITMA J-BIT ENCODING PADA KOMPRESI FILE TEKS,” KOMIK (Konferensi Nas. Teknol. Inf. dan Komputer) , vol. 1, no. 1, pp. 232–236, 2017.
[5] M. R. Irliansyah, S. D. Nasution, and K. Ulfa, “Penerapan Metode Deflate Dan Algoritma Goldbach Codes Dalam Kompresi File Teks,” KOMIK (Konferensi Nas. Teknol. Inf. dan Komputer) , vol. 1, no. 1, pp. 186–189, 2017.