BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

Pada bab ini akan membahas landasan atas teori-teori ilmiah untuk mendukung penelitian ini. Teori-teori yang dibahas mengenai pengertian citra, kompresi citra, algoritma dan jenisnya, serta beberapa subpokok pembahasan lainnya yang menjadi landasan dalam penelitian ini.

2.1 Defenisi Citra Citra adalah suatu representasi (gambaran), kemiripan, atau imitasi dari suatu objek. Citra sebagai keluaran suatu sistem perekaman data dapat bersifat optik berupa foto, bersifat sinyal-sinyal video seperti gambar pada monitor televisi, atau bersifat digital yang dapat langsung disimpan pada media penyimpanan (Sutoyo, et al. 2009). Secara harfiah citra (image) adalah gambar pada bidang dwimatra atau dua dimensi. Citra juga dapat diartikan sebagai kumpulan titik-titik dengan intesitas warna tertentu yang membentuk suatu kesatuan dan mempunyai pengertian artistik. Citra sebagai salah satu komponen multimedia yang memegang peranan sangat penting sebagai salah satu bentuk informasi visual.

2.2 Citra Digital Citra digital adalah citra yang dapat diolah oleh komputer. Citra digital disebut juga citra diskrit di mana citra tersebut dihasilkan melalui proses digitalisasi terhadap citra kontinu. Citra tersebut dikatakan sebagai citra digital karena bentuk representasinya yang berupa bilangan (numbers). Oleh komputer akan dikenal dalam urutan ‘0’ dan ‘1’. Pada umumnya representasi citra digital membutuhkan memori yang besar. Semakin besar ukuran citra tentu semakin besar pula memori yang dibutuhkannya. Pada sisi lain, kebanyakan citra mengandung duplikasi data. Duplikasi data pada citra dapat berarti dua hal. Pertama, besar kemungkinan suatu pixel dengan pixel

Universitas Sumatera Utara

tetangganyamemiliki intensitas yang sama, sehingga penyimpanan setiap pixel memboroskan tempat. Kedua, citra banyak mengandung bagian (region) yang sama, sehingga bagian yang sama ini tidak perlu dikodekan berulang kali karena redundan. Citra tidak sama dengan teks yang hanya memberikan informasi secara jelas dengan kata-kata yang dipaparkan, sedangkan citra memberikan informasi yang jelas dengan memberikan gambaran visual dan terkadang informasi yang diberikan dapat memacu imajinasi dari orang yang melihat citra untuk menyimpulkan informasi dari citra tersebut. Ada beberapa format citra digital, antara lain: BMP, PNG, JPG, GIF dan sebagainya. Masing-masing format mempunyai perbedaan satu dengan yang lain terutama pada header file. Namun ada beberapa yang mempunyai kesamaan, yaitu penggunaan palette untuk penentuan warna piksel. Sebagai studi kasus dalam tugas akhir ini akan digunakan format citra *.jpg yang dikeluarkan oleh Microsoft.

2.3 Citra Warna (True Color) Pada citra warna (true color) setiap pixel-nya merupakan kombinasi dari tiga warna dasar merah, hijau, dan biru, sehingga citra warna ini disebut juga citra RGB (Red Green Blue). Setiap komponen warna memiliki intensitas sendiri dengan nilai minimum 0 dan nilai maksimum 255 (8-bit). Hal ini menyebabkan setiap pixel pada citra RGB membutuhkan media penyimpanan 3 byte. Jumlah kemungkinan kombinasi warna citra RGB adalah 224 = lebih dari 16 juta warna. (Novitasari, 2011). Contoh citra warna (true color)dapat dilihat pada gambar 2.1

Gambar 2.1 Citra warna (true color)

Universitas Sumatera Utara

Gambar 2.2 Palet warna kuning (255 255 0)

2.4 Joint Photograpic Expert Group (JPEG) JPEG didirikan oleh komite Joint Photographic Expert Group yang mengeluarkan standart pada tahun 1992. JPEG menetapkan standart yaitu codec. Codec menjelaskan tentang bagaimana sebuah gambar dikompresi menjadi aliran byte dan dikompres kembali menjadi sebuah gambar serta digunakan sebagai streaming sebuah file. Citra Joint Photograpic Expert Group (JPEG)merupakan yang terbaik untuk foto-foto dan lukisan pemandangan yang realistis dengan variasi warna yang halus dan senada. Kompresi yang umum pada JPEG adalah Lossy, yaitu beberapa kualitas visual akan hilang dalam proses dan tidak dapat dikembalikan. Metode kompresi Lossy data dari encoding ketika diterapkan untuk input yang memiliki 24 bit per pixel (masingmasing delapan untuk merah, hijau dan biru). Metode pertama dari metode kompresi Lossy data adalah transformasi warna, adapun langkah pertama adalah langkahnya adalah mengubah gambar dari RGB menjadi berbagai warna ruang (YCbCr). Y (kecerahan dan pixel), Cb dan Cr (Chrominance/biru dan merah komponen). Ruang warna YCbCr konversi memungkinkan kompresi lebih besar tanpa perceptual signifikan terhadap kualitas gambar (atau lebih besar perceptual kualitas gambar yang sama untuk kompresi). Langkah selanjutnya adalah untuk mengurangi resolusi spasial dari komponen Cb dan Cr disebut dengan downsampling atau subsampling chroma. Gambar berikut adalah gambaran algoritma kompresi JPEG: (W.Y. Yang, 2009).

2.5 Kompresi Citra Kompresi citra adalah proses pemampatan citra yang bertujuan untuk mengurangi duplikasi data pada citra sehingga memory yang digunakan untuk merepresentasikan citra menjadi lebih sedikit daripada representasi citra semula. (Sutoyo, 2009)

Universitas Sumatera Utara

Pemampatan citra atau kompresi bertujuan untuk meminimalkan kebutuhan memori dalam merepresentasikan citra digital dengan mengurangi duplikasi data di dalam citra sehingga memori yang dibutuhkan menjadi lebih sedikit daripada representasi citra semula.

2.5.1 Teknik Kompresi Citra Ada dua teknik yang dapat dilakukan dalam melakukan kompresi citra yaitu: 1. Lossless Compression Metode Lossless merupakan kompresi citra dimana hasil dekompresi dari citra yang terkompresi sama dengan citra aslinya, tidak ada informasi yang hilang. Sayangnya, untuk ratio kompresi citra metode ini sangat rendah. secara umum teknik lossless digunakan untuk penerapan aplikasi yang memerlukan kompresi tanpa cacat, seperti pada aplikasi radiografi, kompresi citra hasil diagnose medis atau gambar satelit, di mana kehilangan gambar sekeil apa pun akan menyebabkan hasil yang tidak diharapkan. Contoh metode ini adalah Shannon-Fano Coding, Huffman Coding, Arithmetic Coding, Run-Length Encodingdan lain sebagainya(Sutoyo, 2009) 2. Lossy Compression Metode Lossy merupakan kompresi citra dimana hasil dekompresi dari citra yang terkompresi tidak sama dengan citra aslinya, artinya bahwa ada informasi yang hilang, tetapi masih bisa ditolerir oleh persepsi mata. Metode ini menghasilkan ratio kompresi yang lebih tinggi dari pada metode lossless. Contohnya adalah color reduction, chroma subsampling, dan transform coding, seperti transformasi Fourier, Wavelet dll. (Sutoyo, 2009)

2.5.2 Kriteria Kompresi Citra Dalam kompresi citra biasanya kriteria yang digunakan untuk mengukur pemampatan citra adalah: 1. Waktu kompresi dan waktu dekompresi Proses kompresi merupakan proses mengkodekan citra (encode) sehingga diperoleh citra dengan representasi kebutuhan memori yang minimum. Citra terkompresi disimpan dalam file dengan format tertentu. Sedangkan proses dekompresi adalah

Universitas Sumatera Utara

proses untuk menguraikan citra yang dimampatkan untuk dikembalikan lagi (decoding) menjadi citra yang tidak mampat (mengembalikan ke bentuk semula). Algoritma pemampatan yang baik adalah algoritma yang membutuhkan waktu untuk kompresi dan dekompresi paling sedikit (paling cepat). Gambar 2 merupakan gambar mengenai proses kompresi dan dekompresi citra (Sutoyo, et al. 2009).

2. Kebutuhan memori Suatu metode kompresi yang mampu mengompresi file citra menjadi file yang berukuran paling minimal adalah metode kompresi yang baik. Dimana memori yang dibutuhkan untuk menyimpan hasil kompresi berkurang secara berarti. Akan tetapi biasanya semakin besar persentase pemampatan, semakin kecil memori yang diperlukan sehingga kualitas citra makin berkurang. Sebaliknya semakin kecil persentase yang dimampatkan, semakin bagus kualitas hasil pemampatan tersebut (Sutoyo, et al. 2009).

3. Kualitas pemampatan Metode kompresi yang baik adalah metode yang dapat mengembalikan citra hasil kompresi menjadi citra semula tanpa kehilangan informasi apapun. Walaupun ada informasi yang hilang akibat pemampatan, sebaiknya hal tersebut ditekan seminimal mungkin. Semakin berkualitas hasil pemampatan, semakin besar memori yang dibutuhkan, sebaliknya semakin jelek kualitas pemampatan, semakin kecil kebutuhan memori yang harus disediakan (Sutoyo, et al. 2009).

2.5.3 Parameter Perbandingan 1. Compression Ratio (Cr) Compression Ratio (Cr) adalah persentase besar data terkompresi, hasil perbandingan antara data yang sudah dikompresi dengan data yang belum dikompresi (Salomon, 2007).

Universitas Sumatera Utara

𝐽𝑢𝑚𝑙𝑎 ℎ 𝐵𝑖𝑡 𝑆𝑒𝑡𝑒𝑙𝑎 ℎ𝐷𝑖𝑘𝑜𝑚𝑝𝑟𝑒𝑠𝑖

Cr = 𝐽𝑢𝑚𝑙𝑎 ℎ 𝐵𝑖𝑡 𝑆𝑒𝑏𝑒𝑙𝑢𝑚𝐷𝑖𝑘𝑜𝑚𝑝𝑟𝑒

𝑠𝑖

X 100%

(1)

2. Ratio of Compression (Rc) Ratio of Compression (Rc) adalah hasil perbandingan antara data yang belum dikompresi dengan data yang sudah dikompresi (Salomon, 2007).

Rc =

𝐽𝑢𝑚𝑙𝑎 ℎ 𝐵𝑖𝑡 𝑆𝑒𝑏𝑒𝑙𝑢𝑚𝐷𝑖𝑘𝑜𝑚𝑝𝑟𝑒𝑠𝑖 𝐽𝑢𝑚𝑙𝑎 ℎ 𝐵𝑖𝑡 𝑆𝑒𝑡𝑒𝑙𝑎 ℎ𝐷𝑖𝑘𝑜𝑚𝑝𝑟𝑒𝑠𝑖

X 100%(2)

3. Redundancy Data (Rd) Redundancy Data adalah kelebihan yang terdapat di dalam data sebelum dikompresi. Jadi setelah data dikompresi dapat dihitung Redundancy data yaitu persentasi dari hasil selisih antara ukuran data sebelum dikompresi dengan data setelah dikompresi. (Salomon & Motta, 2010). Rd= 100% – Cr(3) 4. Waktu Kompresi Waktu kompresi merupakan waktu yang dibutuhkan oleh sebuah sistem untuk menginput file teks yang akan dikompresi sampai dengan

selesainya

proses

kompresi. Semakin sedikit waktu yang dibutuhkan oleh sebuah sistem untuk melakukan sebuah kompresi, maka metode kompresi yang digunakan semakin efektif.

2.6

Kompleksitas Algoritma

Algoritma merupakan salah satu cabang ilmu komputer yang membahas prosedur penyelesaian suatu permasalahan. Dalam beberapa konteks, algoritma merupakan spesifikasi urutan langkah untuk melakukan pekerjaan tertentu. Algoritma adalah prosedur komputasi yang terdefenisi dengan baik yang menggunakan beberapa nilai sebagai masukan dan menghasilkan beberapa nilai sebagai masukan dan menghasilkan beberapa nilai yang disebut keluaran. (Munir R, 2007).

Universitas Sumatera Utara

Adanya algoritma yang baik mbaka komputer bisa menyelesaikan perhitungan dengan cepat dan benar. Sebaliknya jika algoritma kurang baik maka penyelesaian lambat dan bahkan tidak didapat solusi yang diharapkan. Baik buruknya sebuah algoritma dapat dibuktikan dari kompleksitas waktu yang digunakan. Dua hal penting untuk mengukur efektivitas suatu algoritma yaitu kompleksitas ruang (keadaan) dan kompleksitas waktu. Kompleksitas ruang berkaitan dengan sistem memori yang dibutuhkan dalam eksekusi program. Kompleksitas waktu dari algoritma berisi ekspresi bilangan dan jumlah langkah yang dibutuhkan sebagai fungsi dari ukuran permasalahan. Analisa asimtotik menghasilkan notasi Ο (Big O) dan dua notasi untuk komputer sain yaitu ϴ (Big Theta) dan Ω (Big Omega) . Kinerja algoritma dibuktikan dengan menjumlahkan bilangan bulat dari masing-masing operasi ketika algoritma di jalankan. Kinerja sebuah algoritma dievaluasi sebagai fungsi ukuran masukan n dan konstanta modulo pengali yang digunakan. Pada penelitian ini kompleksitas yang digunakan adalah Big(ϴ).

2.6.1

Big-O (O)

Secara informal, O(g(n)) adalah himpunan semua fungsi yang lebih kecil atau dengan urutan yang sama dengan g(n) (hingga beberapa konstanta, sampai n ke tak terhingga). Sebuah fungsi t(n) dikatakan bagian dari Ο((g(n)) yang dilambangkan dengan t(n) Є Ο(g(n)), jika t(n) batas atasnya adalah beberapa konstanta g(n) untuk semua n besar, jika terdapat konstanta c positif dan beberapa bilangan bulat non-negatif n0 seperti t(n) ≤ cg(n) untuk semua n≥n0 . (Levitin A, 2011) 2.6.2

Big Omega (Ω)

Ω(g(n)) merupakan himpunan semua fungsi dengan tingkat pertumbuhan lebih besar atau sama dengan g(n) (hingga beberapa konstanta, sampai n ke tak terhingga). Sebuah fungsi t(n) dikatakan bagian dari Ω(g(n)), dilambangkan dengan t(n) Є Ω(g(n)), jika t(n) batas bawahnya adalah beberapa konstanta positif dari g(n) untuk semua n besar. Terdapat konstanta c positif dan beberapa bilangan bulat non-negatif n0 seperti t(n) ≥ cg(n), (untuk setiap n ≥ n0). (Levitin A, 2011) 2.6.3

Big Theta (θ)

θ (g(n)) adalah himpunan semua fungsi yang memiliki tingkat pertumbuhan yang sama dengan g(n) (hingga beberapa konstanta, sampai n ke tak terhingga). Sebuah

Universitas Sumatera Utara

fungsi t(n) dikatakan bagian dari θ (g(n)), dilambangkan dengan t(n) Є θ (g(n)), jika t(n) batas atas dan bawahnya adalah beberapa konstanta positif g(n) untuk semua n yang besar, yaitu jika ada beberapa konstanta positif c1 dan c2 serta beberapa bilangan bulat non-negatif n0 seperti c2g(n) ≤ t(n) ≤ c1g(n) untuk semua n ≥ n0. (Levitin A, 2011)

2.7 Dekompresi Citra Sebuah citra yang sudah terkompresi tentunya harus dapat dikembalikan lagi kebentuk aslinya, prinsip ini dinamakan dekompresi. Untuk dapat merubah citra yang terkompresi diperlukan cara yang berbeda seperti pada waktu proses kompresi dilaksanakan. Jadi pada saat dekompresi catatan header yang berupa byte-byte tersebut terdapat catatan isi mengenai isi dari file tersebut. (Alkhudri, 2015) Catatan header akan menuliskan kembali mengenai isi dari file tersebut, jadi isi dari file sudah tertulis oleh catatan header sehingga hanya tinggal menuliskan kembali pada saat proses dekompresi. Proses dekompresi sempurna dan kembali ke bentuk aslinya. Parameter perbandingan dalam dekompresi adalah waktu dekompresi. Waktu dekompresi adalah waktu yang dibutuhkan oleh sebuah sistem untuk melakukan proses dekompresi dari mulai pembacaan data hingga proses decoding pada data tersebut. Semakin kecil waktu yang diperoleh maka semakin efisien metode yang digunakan dalam proses kompresi dan dekompresi itu. Alur proses kompresi dan dekompresi pada citra dapat dilihat pada gambar 2.3 berikut.

Citra Asli

Kompresi Dekompresi

Citra Hasil Kompresi

Gambar 2.3Alur kompresi-dekompresi citra (Alkhudri, 2015)

2.8 Algoritma Alternate Reverse Unary Code Metode ini sudah umum digunakan dalam kompresi data dan banyak digunakan dengan gabungan beberapa teknik modifikasi. Unary Coding direpresentasikan

Universitas Sumatera Utara

dalamsebuah string dari n bit 1 diikuti dengan satu bit 0

yang mengakhiri yang

didefenisikan sebagai n-1 bit 1diikuti satu bit 0. Atau sebaliknya sebagai alternatif dapat juga secara ekuivalen dimulai dari n bit 0 diikuti dengan bit 1 yang mengakhiriyang didefenisikan sebagai n-1 bit 0 diikuti dengan satu bit 1. Pada metode UnaryCoding tidak terdapat pembagian frekuensi simbol-simbol yang ada pada sebuah string. (Salomon, 2008). Data sebelum dikompresi Algoritma Alternate Reverse Unary Code dapat dilihat pada tabel 2.1

Tabel 2.1 Data Sebelum Dikompresi ARUC Simbol

Frekuensi

8 bit

Bit

Bit x Frek

2

3

00000010

8

24

3

5

00000011

8

40

8

1

00001000

8

8

50

1

00110010

8

8

51

2

00110011

8

16

Bit x Frekuensi

96

Pada Tabel 2.2 berikut ini akan ditunjukkan data setelah dikompresi menggunakan algoritma Alternate Reverse Unary Code sesuai dengan data pada tabel 2.1. Tabel 2.2 Data Sesudah DikompresiARUC Simbol

Frekuensi

ARUC

Bit

Bit x Frek

3

5

1

1

5

2

3

01

2

6

51

2

001

3

6

8

2

0001

4

4

50

1

00001

5

5

Bit x Frekuensi

26

2.9 Algoritma Run-Length Encoding (RLE) Algoritma Run Length Encoding adalah melakukan kompresi dengan memindahkan pengulangan byte yang sama berturut-turut atau secara terus menerus. Algoritma ini

Universitas Sumatera Utara

digunakan untuk mengompresi citra yang memiliki kelompok-kelompok pixel yang berderajat keabuan yang sama. Pada metode ini dilakukan pembuatan rangkaian pasangan nilai (P,Q) untuk setiap baris pixel, dimana nilai P menyatakan nilai derajat keabuan, sedangkan nilai Q menyatakan jumlah pixel berurutan yang memiliki derajat keabuan tersebut. (Lubis, 2014) Berbeda dengan teknik-teknik sebelumnya yang bekerja berdasarkan karakter per karakter, teknik run length ini bekerja berdasarkan sederetan karakter yang berurutan. Run Length Encoding adalah suatu algoritma kompresi data yang bersifat Lossless. Algoritma ini mungkin merupakan algoritma yang paling mudah untuk dipahami dan diterapkan. Algoritma RLE ini cocok digunakan untuk mengkompres citra yang memiliki kelompok-kelompok pixel berderajat keabuan yang sama. Kompresi citra dengan algoritma RLE dilakukan dengan membuat rangkaian pasangan nilai (p,q) untuk setiap baris pixel, nilai pertama (p) menyatakan derajat keabuan, sedangkan nilai kedua (q) menyatakan jumlah pixel berurutan yang memiliki derajat keabuan tersebut (dinamakan Run-Length Encoding).

Langkah-langkah yang dibutuhkan untuk melakukan kompresi Run-Length Encoding adalah sebagai berikut: 1. Periksa nilai saat ini dengan nilai tetangga, apabila nilai saat ini sama dengan nilai tetangga maka gabungkan nilai tersebut menjadi satu dan tambahkan nilai counter untuk nilai tersebut. 2. Apabila nilai saat ini dengan nilai tetangganya tidak sama maka simpan nilai saat ini dan lanjut pemeriksaan seperti pada nomor 1. 3. Setelah proses 1 dan 2 telah dilakukan kemudian simpan hasil proses kompresi tersebut. Untuk melakukan proses dekompresi terhadap file yang telah mengalami proses kompresi Run Length Encoding (RLE) dapat dilihat pada langkah-langkah berikut ini. 1. Baca nilai yang terdapat pada citra kemudian periksa apakah nilai saat ini berulang atau tidak, apabila nilai saat ini berulang maka ulang nilai sebanyak perulangan yang ada .

Universitas Sumatera Utara

2. Apabila nilai tidak berulang maka nilai saat ini simpan dan lanjutkan ke nilai selanjutnya. 2.10 Penelitian Terkait Berikut ini beberapa penelitian yang terkait dengan algoritma Alternate Reverse Unary Codes dan Run Length Encoding. Penelitian terkait untuk kedua algoritma tersebut dapat dilihat pada tabel 2.3.

Tabel 2.3 Tabel Penelitian Terkait No

Judul

Peneliti &Tahun

Metode

Keterangan

yang digunakan

1.Studi 1.

Eunike

Algoritma

Dalam

skripsi,

dapat

Perbandingan

Johana, S.

Shannon

disimpulkan bahwa hasil

Kompresi

2013

Fano dan

perbandingan

Menggunakan

Unary

rasiokompresimenunjukka

Metode Shannon

Code

n Shannon Fano sebesar

rata-rata

Fano Dan Unary

50.87%,

Unary

Code

Code Pada File

sebesar

Teks

Sementara

untuk

kecepatan

kompresi

93.76%.

Shannon Fano merupakan yang

paling

cepat

dibandingkan Unary Code.

2.

Implementasi

Ahmad,

Algoritma

Tingkat efisiensi memori

Algoritma Run

Yuliana

Run Length

file hasil kompresi dengan

Length Encoding

2012.

Encoding

menggunakan

(RLE)

Run

(RLE) untuk Kompresi Citra

diukur

Digital

rasio

Metode

Length

Encoding

dari

besarnya

kompresi

dihasilkan.

Citra

yang yang

mempunyai sebaran nilai

Universitas Sumatera Utara

piksel

tidak

merata

memiliki tingkat efisiensi lebih besar dibandingkan dengan citra dengan nilai piksel yang merata. 3.

Perancangan Perangkat

Yuandi, Lunak

Pengenkripsian Citra

*.BMP,

Metode Hill

Hill

Cipher

sebenarnya

Hendry.

merupakan

salah

satu

2010.

teknik penyandian teks, tetapi dengan melakukan

*.GIF, dan *.JPG

perubahan

perhitungan

dengan

pada

RGB

Hill.

Metode

nilai

(Red

Green Blue) citra maka Hill Cipher juga dapat dipakai

untuk

menyandikan citra. Hasil dari tulisan ini adalah perancangandan pembuatan perangkat dapat

suatu lunak

yang

melakukan

penyandian citra dengan Hill Cipher.

Universitas Sumatera Utara