BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

Pada bab ini akan membahas landasan atas teori-teori yang bersifat ilmiah untuk mendukung penulisan tugas akhir ini. Teori-teori yang dibahas mengenai pengertian citra, kompresi citra, algoritma Huffman, dan beberapa subpokok pembahasan lainnya yang menjadi landasan dalam penulisan tugas akhir ini.

2.1 Pengertian 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 analog berupa sinyal-sinyal video seperti gambar pada monitor televisi atau bersifat digital yang dapat langsung disimpan pada suatu media penyimpan (Sutoyo et al, 2009).

Suatu citra dapat didefinisikan sebagai fungsi f(x,y) berukuran M baris dan N kolom, dengan x dan y adalah koordinat spasial dan amplitudo f di titik koordinat (x,y) dinamakan intensitas atau tingkat keabuan dari citra pada titik tersebut. Index baris dan kolom (x,y) dari sebuah piksel dinyatakan dalam bilangan bulat.

2.1.1 Citra Analog

Citra analog adalah citra yang masih dalam bentuk sinyal analog yang bersifat kontinu, seperti citra tampilan pada televisi ataupun monitor, gambar-gambar yang terekam pada pita kaset, foto yang tercetak dikertas foto, dan lain sebagainya. Citra analog tidak dapat direpresentasikan dalam komputer sehingga tidak bisa diproses di komputer secara langsung. Oleh karena itu, agar citra ini dapat diproses dikomputer maka dilakukan proses konversi analog ke digital terlebih dahulu.

Universitas Sumatera Utara

7

2.1.2 Citra Digital

Citra dapat dikatakan sebagai citra digital jika citra tersebut disimpan dalam format digital (dalam bentuk file). Citra digital dihasilkan melalui proses digitalisasi terhadap citra kontinu. Seperti halnya proses digitalisasi dalam bentuk data lain, proses digitalisasi pada citra juga merupakan proses pengubahan suatu bentuk data citra dari yang bersifat analog ke dalam bentuk data digital. Yang mana proses ini dapat dilakukan dengan menggunakan alat bantu, seperti kamera serta scanner. Hanya citra digital yang dapat diolah menggunakan komputer sedangkan jenis citra yang lain dapat diolah dengan komputer jika citra tersebut diubah terlebih dahulu menjadi citra digital. Berikut ini gambar elemen sistem pemrosesan citra digital.

Media Penyimpanan

Citra

Digitizer

Komputer

Piranti Tampilan

Gambar 2.1 Elemen Sistem Pemrosesan Citra Digital

Digitizer pada gambar diatas berfungsi untuk menangkap citra yang melakukan penjelajahan citra dan mengkonversi citra tersebut ke representasi numerik sebagai masukan bagi komputer. Hasil dari digitizer ini adalah matriks yang elemenelemennya menyatakan nilai intensitas cahaya pada satu titik. Komputer digunakan pada sistem pemrosesan citra. Piranti tampilan berfungsi untuk mengkonversi matriks intensitas tinggi kemudian merepresentasikan citra ke tampilan yang dapat dilihat oleh manusia. Sedangkan media penyimpanan berfungsi untuk menyimpan hasil konversi citra menjadi citra digital sehingga dapat disimpan secara permanen agar dapat diproses lagi pada waktu yang lain.

Citra digital berbentuk empat persegi panjang dan dimensi ukurannya dinyatakan sebagai tinggi x lebar (lebar x panjang). Citra digital yang tingginya N, lebarnya M dan memiliki L derajat keabuan dapat dianggap sebagai fungsi:


8

0≤𝑥 ≤𝑀 f (x,y) 0 ≤ 𝑦 ≤ 𝑁 0 ≤𝑓 ≤𝐿 Citra digital merupakan sebuah larik (array) yang berisi nilai-nilai real maupun komplek yang direpresentasikan dengan deretan bit tertentu (Putra, 2010). Citra digital adalah citra yang dapat diolah oleh komputer. Citra digital dinyatakan dalam bentuk rumusan f(x,y) yang menyatakan derajat keabuan (gray level) citra pada koordinat spasial x dan y. Gambar 2.1 menunjukkan posisi koordinat citra digital.

Kolom/lebar = 6

piksel

Baris/tinggi = 6 Gambar 2.2 Posisi koordinat citra digital

Sebuah citra digital dapat diwakili oleh sebuah matriks yang terdiri dari M kolom dan N baris, dimana perpotongan antara baris dan kolom disebut dengan piksel (pixel = picture element), yaitu elemen terkecil dari sebuah citra. Piksel mempunyai dua parameter, yaitu koordinat dan intensitas atau warna. Nilai yang terdapat pada koordinat (x,y) adalah f(x,y), yaitu besar intensitas atau warna dari piksel di titik itu. Oleh karena itu, sebuah citra digital dapat ditulis dalam bentuk matriks berikut: 𝑓(0,0) 𝑓(0,1) 𝑓(1,0) … f(x,y) = … … 𝑓(𝑁 − 1,0) 𝑓(𝑁 − 1,1)

… 𝑓(0, 𝑀 − 1) … 𝑓(1, 𝑀 − 1) … … … 𝑓(𝑁 − 1, 𝑀 − 1)


9

Contoh suatu citra berukuran 256 x 256 piksel dengan intensitas beragam pada tiap pikselnya, direpresentasikan secara numerik dengan matriks yang terdiri dari 256 baris dan 256 kolom. 0 0 220 : : 221

134 167 187 : : 219

145 201 189 : : 210

… … … : : …

… … … : : …

231 197 197 : : 156

Piksel pertama pada koordinat (0,0) mempunyai intensitas 0 yang berarti warna piksel tersebut hitam, piksel kedua pada koordinat (0,1) mempunyai intensitas 134 berarti warnanya antara hitam dan putih dan seterusnya.

Gambar 2.3 Ilustrasi digitalisasi citra (piksel pada koordinat x = 10, y = 3)

Gambar 2.3 di atas menunjukkan ilustrasi digitalisasi citra dengan M = 16 baris dan N = 16 kolom,

Untuk mendapat sebuah citra digital, dapat digunakan alat yang memiliki kemampuan untuk mengubah sinyal analog menjadi digital misalnya dengan mengunakan peralatan digital seperti, scanner, kamera digital dan alat digital lainnya. Dalam tugas akhir ini akan menggunakan citra digital dengan format BMP.


10

2.1.2.1 Jenis Citra Digital

Nilai suatu piksel memiliki nilai rentang tertentu, dari nilai minimum sampai nilai maksimum. Jangkauan yang digunakan berbeda-beda tergantung dari jenis warnanya. Namun, secara umum jangkauannya adalah 0 – 255. Berikut adalah jenis-jenis citra berdasarkan nilai pikselnya (Putra, 2010).

1. Citra biner adalah citra digital yang hanya memiliki 2 kemungkinan nilai piksel yaitu hitam dan putih. Nilai 0 mewakili warna hitam dan nilai 1 mewakili warna putih. Citra biner disebut juga dengan citra black & white atau citra monokrom. Oleh karena itu, setiap piksel pada citra biner cukup direpresentasikan dengan 1 bit. Contoh citra biner dapat dilihat pada gambar berikut.

Gambar 2.4 Contoh Citra Biner Berukuran 10 x 11 piksel dan Representasinya dalam data digital

Gambar 2.5 Contoh Citra Biner


11

2. Citra Grayscale Citra grayscale merupakan citra yang hanya memiliki satu nilai kanal pada setiap pikselnya, dengan kata lain nilai Red = Green = Blue. Warna yang dimiliki adalah warna hitam, keabuan, dan putih. Jenis citra ini disebut dengan aras keabuan karena warna abu-abu diantara warna minimum (hitam) dan warna maksimum (putih). Pada umumnya citra grayscale memiliki kedalaman piksel 4 bit dan 8 bit. Citra dengan 4 bit memiliki 24 =16 kemungkinan warna, yaitu 0 (minimal) 15 (maksimal). Sementara citra dengan 8 bit memiliki 28 = 256 warna, yaitu 0 (minimal) hingga 255 (maksimal).

Gambar 2.6 Contoh Citra Grayscale skala keabuan 8 bit

3. Citra warna Pada citra warna (true color) setiap pikselnya merupakan kombinasi dari 3 warna dasar yakni Red, Green, Blue, sehingga warna ini disebut juga dengan citra RGB. Banyaknya warna yang mungkin digunakan tergantung kepada kedalaman piksel citra yang bersangkutan. Setiap komponen warna memiliki kedalaman piksel sendiri dengan nilai minimum 0 dan nilai maksimum 255 (8 bit). Hal ini menyebabkan setiap piksel pada citra RGB membutuhkan media penyimpanan 3 byte. Jumlah kemungkinan kombinasi warna pada citra RGB adala 224 = lebih dari 16 juta warna. Dan intensitas suatu titik pada citra warna merupakan kombinasi dari intensitas derajat keabuan merah (fmerah, (x,y)), hijau (fhijau, (x,y)) dan biru (fbiru, (x,y)).


12

1 byte Blue

1 byte Green

1 byte Red

Gambar 2.7 Format Penyimpanan Warna RGB

G R

B

Gambar 2.8 Format Warna RGB (sumber Basuki, 2006)

Pada citra warna masing-masing komponen warna RGB mempunyai nilai 0 sampai 255 (8 bit) derajat kecerahan/derajat keabuan (Basuki, 2006).

Tabel 2.1 Format Warna RGB


13

Gambar 2.9 Contoh Kombinasi Warna RGB untuk Menghasilkan Warna Kuning

Gambar 2.10 Contoh Citra RGB

2.2 Pohon (Tree)

Pohon (tree) merupakan salah satu bentuk struktur data linear yang menggambarkan hubungan yang bersifat hirarki (hubungan one to many) antara elemen-elemen yang ada (Kristanto, 2003). Struktur pohon memungkinkan kita untuk mengorganisasi informasi berdasarkan suatu struktur logik dan memungkinkan berbagai cara akses untuk suatu elemen.

Sebuah pohon (tree) adalah kumpulan simpul yang tidak kosong yang memiliki elemen-elemen yang dinamakan simpul (node) yang mana hubungan antara simpul bersifat hirarki. Simpul yang paling atas dari hirarki disebut dengan root. Simpul yang berada dibawah root secara langsung, dinamakan anak dari root yang biasanya juga mempunyai anak di bawahnya. Sedangkan simpul yang tidak mempunyai anak disebut dengan daun (leaf) yang merupakan simpul terminal dari pohon (Sedgewick, 2002).


14

2.2.1 Pohon Biner (Binary Tree)

Pohon biner adalah pohon yang setiap simpulnya memiliki paling banyak dua buah subtree dan kedua subtree tersebut harus terpisah yaitu subtree kiri dan subtree kanan (Sedgewick, 2002). Sesuai dengan definisi tersebut, maka tiap simpul dalam pohon biner hanya boleh mememiliki paling banyak dua anak (child). Secara umum pohon biner diperlihatkan pada gambar 2.2 berikut. A C

B E

D

H

F

I

G

J

Gambar 2.11 Pohon biner (sumber Kristanto, 2003)

2.3. Kompresi Citra

Kompresi data adalah bertujuan untuk memperkecil ukuran data sehingga lebih mudah dalam proses penyimpanan dan perpindahan data (Bookshear, 2003, hal:60). Kompresi bertujuan untuk mengurangi jumlah data yang digunakan untuk mewakili isi file, gambar, atau video tanpa mengurangi kualitas data aslinya. Kompresi dilakukan dengan mengurangi jumlah bit yang diperlukan untuk menyimpan atau mengirimkan media digital tersebut (Sharma, 2010).

Kompresi citra adalah aplikasi kompresi data yang dilakukan terhadap citra digital dengan tujuan untuk mengurangi redundansi dari data yang terdapat dalam citra sehingga dapat disimpan atau ditransmisikan secara efisien (Sayood, 2005).

Sedangkan menurut Darma Putra (2010, hal: 261) kompresi citra merupakan proses untuk mereduksi ukuran suatu data untuk menghasilkan representasi digital yang padat atau mampat (compact) namun tetap dapat mewakili kuantitas informasi yang terkandung pada data tersebut.


15

Pada dasarnya teknik kompresi citra digunakan pada proses penyimpanan data dan proses transmisi data. Data dan informasi adalah dua hal yang berbeda. Pada data terkandung suatu informasi. Namun tidak semua bagian data terkait dengan informasi tersebut atau pada suatu data terdapat bagian-bagian data yang berulang untuk mewakili informasi yang sama (Putra, 2010).

Bagian data yang tidak terkait atau bagian data yang berulang tersebut disebut dengan data berlebihan (redundancy data). Semakin besar ukuran citra, semakin besar memori yang dibutuhkan, namun kebanyakkan citra mengandung duplikasi data, yaitu:

1. Suatu piksel memiliki intensitas yang sama dengan piksel tetangganya, sehingga penyimpanan piksel membutuhkan memori yang lebih besar sehingga sangat memboroskan tempat. 2. Citra banyak mengandung bagian (region) yang sama sehingga bagian yang sama ini tidak perlu dikodekan berulang kali karena akan mengakibatkan redundant atau duplikasi.

Tujuan dari kompresi citra adalah 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.

Secara umum proses kompresi dan dekompresi dapat dilihat pada gambar di bawah ini: Data Asli

ukuran data asli

kompresi

Data Hasil

dekompresi

Kompresi ukuran data hasil kompresi

Gambar 2.12 Alur kompresi dan dekompresi data


16

Parameter-parameter citra yang penting dalam proses kompresi diantaranya adalah sebagai berikut:

1. Resolusi Resolusi citra menyatakan ukuran panjang kali lebar dari sebuah citra. Resolusi citra biasanya dinyatakan dalam satuan piksel. Semakin tinggi resolusi sebuah citra, semakin baik kualitas citra tersebut. Namun, tingginya resolusi menyebabkan semakin banyaknya jumlah bit yang diperlukan untuk menyimpan dan mentransmisikan data citra tersebut.

2. Kedalaman Bit Kedalaman bit menyatakan jumlah bit yang diperlukan untuk merepresentasikan tiap piksel citra pada sebuah frame. Kedalaman bit biasanya dinyatakan dalam satuan

bit/piksel.

Semakin

banyak

jumlah

bit

yang digunakan

untuk

merepresentasikan sebuah citra , maka semakin baik kualitas citra tersebut.

3. Konsep Redundansi Redundansi merupakan suatu keadaan dimana representasi suatu elemen data tidak bernilai signifikan dalam merepresentasikan keseluruhan data. Keadaan ini menyebabkan data keseluruhan dapat direpresentasikan secara lebih kompak dengan cara menghilangkan representasi dari sebuah elemen data yang redundan. Redundansi yang terdapat pada citra statis adalah redundansi spasial.

Manfaat kompresi citra adalah:

1. Membutuhkan ruang memori dalam storage yang lebih sedikit daripada representasi citra yang tidak dikompresi. 2. Waktu pengiriman data pada saluran komunikasi data lebih singkat. Contohnya pengiriman

gambar

dari

fax,

handphone,

download

dari

internet,

videoconferencing, pengiriman data medis, dan lain sebagainya


17

Ada beberapa pendekatan yang digunakan untuk kompresi citra:

1. Pendekatan statistik (statistical compression). 2. Pendekatan ruang (spatial compression). 3. Pendekatan kuantisasi (quantizing compression). 4. Pendekatan fractal (fractal compression). 5. Pendekatan transformasi wavelet (wavelet compression).

Pada tugas akhir ini kompresi citra akan menggunakan pendekatan statistik dengan menggunakan algoritma Huffman.

2.3.1 Teknik Kompresi Citra

Ada dua teknik yang dapat dilakukan dalam melakukan kompresi citra (Sutoyo et al, 2009).

1. Lossless Compression Pada teknik ini informasi yang terkandung pada citra hasil kompresi sama dengan informasi pada citra asli. Jika citra dikompresi secara lossless, citra asli dapat direkonstruksi kembali sama persis dari citra yang telah dikompresi, dengan kata lain citra asli tetap sama sebelum dan sesudah dikompresi. Contoh file yang menggunakan kompresi lossless adalah file ZIP dan GIF. Lossless compression disebut juga dengan reversible compression karena data asli bisa dikembalikan dengan sempurna. Akan tetapi, rasio kompresi citra dengan teknik ini sangat rendah. Kompresi tipe ini cocok diterapkan pada berkas basis data (database), citra biomedis, Contoh teknik ini adalah Run Length Encoding (RLE), Entropy Encoding (Huffman, aritmatik), dan Adaptive Dictionary Based (LZW). Ilustrasi kompresi lossless ditunjukkan pada Gambar 2.2


18

AABBA

Algoritma

000001101101100

kompresi

000001101101100

Algoritma

AABBA

dekompresi Gambar 2.13 ilustrasi kompresi losesless (sumber: Pu, 2006)

2. Lossy Compression Pada teknik ini mengijinkan terjadinya kehilangan sebagian informasi tertentu dari citra tersebut, sehingga dapat menghasilkan rasio kompresi yang tinggi. Apabila citra terkompresi direkonstruksi kembali maka hasilnya tidak sama dengan citra aslinya. Biasanya teknik ini membuang bagian-bagian informasi yang sebenarnya tidak begitu berguna, tidak begitu dirasakan, tidak begitu dilihat sehingga manusia beranggapan bahwa citra tersebut masih bisa ditelorir oleh presepsi mata. Mata tidak dapat membedakan perubahan kecil pada gambar. Contohnya adalah color reduction, chroma subsampling, dan transform coding seperti transformasi Wavelet, Fourier, dan lain-lain. Berikut ilustrasi kompresi lossy ditunjukkan pada Gambar 2.3

3.1415926

Algoritma

0001100111001

kompresi

0001100111001

Algoritma

3.14

dekompresi Gambar 2.14 Ilustrasi kompresi lossy (sumber: Pu, 2006)


19

2.3.2 Rasio Kompresi Citra

Rasio kompresi citra adalah ukuran presentasi citra yang telah berhasil dimampatkan/dikompresi. Secara umum matematis rasio pemampatan citra dituliskan sebagai berikut.

Rasio = 100% - Hasil kompresi x 100% Citra Asli

Misalkan rasio kompresi adalah 20%, artinya 20% dari citra semula telah berhasil dimampatkan.

2.3.3 Format File Citra Bitmap (BMP)

Pada penelitian ini, citra yang akan digunakan adalah citra yang berformat bitmap. Pada format bitmap, citra disimpan sebagai suatu matriks dimana masing-masing elemennya digunakan untuk menyimpan informasi warna untuk setiap piksel. Jumlah warna yang dapat disimpan ditentukan dengan satuan bit per piksel. Semakin besar ukuran bit per piksel dari suatu gambar semakin banyak pula jumlah warna yang dapat disimpan. Format bitmap ini cocok digunakan untuk menyimpan citra digital yang memiliki banyak variasi dalam bentuk maupun warnanya.

Saat ini format BMP memang kalah popular dibandingkan format JPG atau GIF. Hal ini dikarenakan file citra BMP pada umumnya tidak dikompresi, sehingga ukuran filenya relatif lebih besar daripada file JPG maupun GIF. Hal ini juga yang menyebabkan format BMP sudah jarang digunakan. Dan jika dibandingkan dengan file RAW yang merupakan format file khusus yang dihasilkan oleh kamera digital, yang mana format file RAW yang dihasilkan berbeda-beda tergantung dari tiap merk kamera

seperti

.CRW

(Canon),

.NEF(Nikon),

dan

.ORF

(Olyimpus)

(www.windows.microsoft.com).

File RAW adalah data mentah yang langsung ditangkap oleh sensor kamera, dimana ukuran file ini besar namun kualitas gambarnya baik dan juga belum


20

dikompresi. Tetapi, file tersebut hanya dapat dibuka dengan beberapa software khusus yang mendukung format tersebut seperti photoshop, GIMP, ACDSee, dan lain-lain. Sedangkan format file BMP merupakan format citra yang baku di lingkungan sistem operasi Microsoft Windows serta gambar raster yang paling dasar dan umum, sehingga pada penelitian ini penulis menggunakan format file BMP.

Meskipun format BMP tidak bagus dari segi ukuran berkas, namun format BMP memiliki kualitas gambar yang lebih baik dari format JPG maupun GIF. Karena citra dalam format BMP umumnya tidak dimampatkan/dikompresi sehingga tidak ada informasi yang hilang. Bitmap teridiri dari baris dan kolom pada titik image graphics di komputer. Nilai dari titik disimpan dalam satu atau lebih bit. Bit yang umum adalah 8, artinya setiap piksel panjangnya 8 bit. Delapan bit ini merepresentasikan nilai intensitas piksel. Dengan demikian ada sebanyak 28 = 256 derajat keabuan mulai dari 0-255.

Citra dalam format BMP ada tiga macam : citra biner, citra bewarna, dan citra hitam-putih (grayscale). Citra biner hanya memiliki dua kemungkinan nilai piksel yaitu hitam dan putih. Citra ini hanya membutuhkan 1 bit untuk mewakili nilai setiap piksel dari citra biner. Citra berwarna adalah citra yang lebih umum. Dimana setiap piksel pada citra warna mewakili warna yang merupakan kombinasi dari tiga warna dasar (RGB=Red Green Blue). Setiap warna dasar menggunakan penyimpanan 8 bit = 1 byte, yang berarti setiap warna mempunyai gradasi sebanyak 255 warna.

Setiap komponen warna RBGnya disimpan di dalam tabel RBG yang disebut palet. Setiap komponen panjangnya 8 bit, jadi ada 256 nilai keabuan untuk warna merah, 256 nilai keabuan untuk warna hijau dan 256 nilai keabuan untuk warna biru. Nilai setiap piksel tidak menyatakan derajat keabuan secara langsung, tetapi nilai piksel menyatakan indeks tabel RBG yang memuat nilai keabuan merah (R), nilai keabuan hijau (G), nilai keabuan biru (B) untuk masing-masing piksel bersangkutan. Sedangkan citra hitam putih hanya memiliki satu kanal pada setiap pikselnya, dengan kata lain nilai bagian RED = GREEN = BLUE yang digunakan untuk menunjukkan tingkat intensitas.


21

Format citra ini mendukung citra dengan jumlah bit per piksel sebanyak 1, 4, 8, 16, dan 24 bit per piksel. Berikut ini tabel yang menunjukkan hubungan antara banyaknya bit per piksel dengan jumlah warna maksimum yang dapat disimpan dalam bitmap.

Tabel 2.2 Hubungan antara bit per piksel dengan jumlah warna maksimum pada bitmap No.

Jumlah bit per piksel

Jumlah warna maksimum

1.

1

2

2.

4

16

3.

8

256

4.

16

65536

5.

24

16777216

Sedangkan struktur citra bitmap seperti pada gambar 2.4.

Header berkas 14 byte

Header bitmap 12 – 16 byte

Informasi Palet

Data bitmap

0 – 1024 byte

N byte

Gambar 2.15 Struktur Citra Bitmap (Sumber Perdana, 2009)

2.3.4 Algoritma Huffman

Algoritma Huffman adalah algoritma yang popular karena sering digunakan untuk melakukan kompresi data. Algoritma Huffman berfungsi sebagai algoritma dasar yang sering digunakan pada beberapa program-program popular yang dapat berjalan di berbagai platform (Salomon, 2007). Algoritma Huffman dikembangkan oleh David A Huffman saat di bangku kuliah di Massachusetts Institute Technology. Algoritma ini merupakan karya ilmiah dari Huffman yang ditulis pada tahun 1952 dengan judul „A method for the Construction of Minimum Redundancy Codes‟. Kode Huffman merupakan hasil pengembangan dari algoritma yang sebelumnya dikembangkan oleh Claude Shannon dan R.M Fano pada tahun 1950an yang dikenal sebagai Shannon – Fano Coding. Perbedaan algoritma ini terdapat dalam teknik pembentukan pohonnya.


22

Algoritma Huffman termasuk teknik kompresi „lossless‟. Yang artinya bahwa kompresi dilakukan tanpa terjadinya kehilangan informasi dimana pada proses dekompresi menghasilkan file yang sebenarnya (Sayood, 2003). Kelebihan algoritma ini terletak pada kebanyakan file data mengandung redundansi. Huffman menemukan cara untuk memanfaatkan redundansi pada suatu file sehingga mengecilkan ukuran file tanpa kehilangan informasi yang terkandung di dalamnya.

Algoritma Huffman menggunakan prinsip pengkodean yang mirip dengan kode Morse, yaitu tiap karakter yang sering muncul dikodekan hanya dengan rangkaian beberapa bit, dimana karakter yang sering muncul dikodekan dengan rangkaian bit yang lebih pendek. Dengan cara tersebut dapat mengurangi ukuran file secara signifikan karena representasi konvensional dari karakter menggunakan panjang yang sama untuk setiap karakter, sehingga menghabiskan banyak tempat (Munir, 2004).

Algoritma Huffman dimulai dengan membangun sebuah simpul yang diurutkan secara ascending berdasarkan fekuensi kemunculan masing-masing simbol. Kemudian dibangun sebuah pohon untuk membentuk kode Huffman yang dihasilkan dari penelusuran simbol dari bawah ke atas dimana 2 simpul yang memiliki frekuensi terkecil digabungkan dan frekuensinya merupakan gabungan dari frekuensi simpulsimpul yang bentuknya.

Berikut ini adalah langkah-langkah proses kompresi citra dengan algoritma Huffman:

1. Baca data citra masukan. 2. Tentukan frekuensi kemunculan masing-masing simbol pada citra. 3. Urutkan secara menaik (ascending order) simbol citra berdasarkan frekuensi kemunculannya (dari yang terkecil ke yang terbesar). Masing-masing simbol direpresentasikan sebagai sebuah simpul. 4. Gabung dua simpul bebas yang mempunyai frekuensi kemunculan paling kecil pada kumpulan simpul. Kemudian dibuat simpul pertama pada pohon Huffman


23

(parent node) dimana simpul tersebut mempunyai frekuensi yang merupakan hasil penjumlahan dari dua simpul penyusunnya. 5. Masukkan simpul pertama (parent node) ke dalam kumpulan simpul dan urutkan kembali berdasarkan frekuensi kemunculannya, dari yang terkecil ke yang terbesar. Kemudian hapus simpul tersebut dari kumpulan simpul. 6. Ulangi langkah 3-5 sampai tersisa hanya satu pohon biner. Agar pemilihan dua pohon yang akan digabungkan berlangsung cepat, maka semua pohon yang ada selalu terurut menaik berdasarkan frekuensi. 7. Beri label setiap sisi pada pohon biner. Dengan cara sisi kiri pohon diberi label 0 dan sisi kanan pohon diberi label 1. 8. Telusuri pohon biner dari akar ke daun. Barisan label-label sisi dari akar ke daun menyatakan kode Huffman untuk simbol yang bersesuaian.

Berikut adalah contoh kompresi citra dengan algoritma Huffman. Misalkan sebuah citra berwarna denga ukuran 5 x 4 piksel adalah sebagai berikut:

Gambar 2.16 Contoh citra warna 5 x 4 piksel dinyatakan dalam bentuk matriks berikut: 250 100 100 150

200 200 100 250

150 200 150 100

100 200 100 250

250 100 200 200

Matriks diatas mewakili sebuah citra warna yang berukuran 5 x 4 piksel, dimana setiap nilai elemen matriks menyatakan warna. Maka cara mengkompresi citra tersebut menggunakan algoritma Huffman sebagai berikut:


24

1. Baca matriks tersebut menjadi sebuah array [250 200 150 100 250 100 200 200 200 100 100 100 150 100 200 150 250 100 250 200] dan tentukan nilai masingmasing simbol warna pada citra yang ada serta frekuensi kemunculnya. Hasilnya:

Simbol Warna

Frekuensi

150

3

250

4

200

6

100

7

2. Urutkan simbol warna secara menaik (ascending order) dari yang frekuensinya terkecil ke frekuensinya terbesar, masing-masing simbol direpresentasikan sebagai sebuah simpul bebas. Sehingga menjadi:

150:3

250:4

200:6

100:7

3. Gabungkan dua buah simpul yang mempunyai frekuensi kemunculan terkecil menjadi sebuah simpul baru dimana frekuensinya merupakan jumlah dari frekuensi penyusunnya dan urutkan kembali. 200:6

150,250:7

150:3

100:7

250:4

4. Gabungkan dua buah pohon yang mempunyai frekuensi kemunculan terkecil dan urutkan kembali. 100:7

150,250,200:13

150,250:7

150:3

200:6

250:4


25

5. Gabungkan dua buah pohon yang mempunyai frekuensi kemunculan terkecil dan urutkan kembali.

150,250,200,100:20

100:7

150,250,200:13

150,250:7

150:3

200:6

250:4

6. Beri label dari akar ke daun, sebelah kiri = 0, kanan = 1. 150,250,200,100:20 1

0

100:7

150,250,200:13 0

1

150,250:7 0 150:3

200:6 1 250:4

7. Penelusuran dari akar ke daun (dari atas ke bawah) menghasilkan kode Huffman berikut: Simbol Warna

Frekuensi

Kode Huffman

150

3

100 (3 bit)

250

4

101 (3 bit)

200

6

11 (2 bit)

100

7

0 (1 bit)


26

8. Gantikan data citra dengan kode Huffman, menjadi: 1011110001010111111000100011100101010111

Setelah dilakukan kompresi maka ukuran file citra yang semula adalah 20 byte. Sedangkan ukuran citra setelah dikompresi (dalam kode Huffman) (3 x 3 bit) + (4 x 3 bit) + (6 x 2 bit) + (7 x 1 bit) adalah: 40 bit setara dengan 5 byte. Rasio kompresinya: 100% -

5 byte 20 byte

× 100% = 75 % yang artinya 75% dari citra

semula telah berhasil dimampatkan.

Untuk mengembalikan citra terkompresi menjadi data citra aslinya, diperlukan proses dekompresi yang merupakan proses untuk menyusun kembali data yang telah dikodekan sebelumnya sehingga informasi yang diterima dapat dibaca dan diolah. Langkah-langkah yang dilakukan dalam proses dekompresi menggunakan pohon Huffman (Pu, 2006) adalah sebagai berikut :

1. Baca bit pertama dari string biner masukan. 2. Lakukan penelusuran dimulai dari root yang ada pada pohon Huffman sampai menuju ke simpul sesuai dengan jumlah bit yang dibaca. Jika bit yang dibaca adalah 0 maka penelusuran bergerak ke sebelah simpul kiri, tetapi jika bit yang dibaca adalah 1 maka akan bergerak ke sebelah simpul kanan. 3. Jika simpul dari pohon bukan daun (simpul tanpa anak) maka baca bit berikutnya dari string biner masukan, penelusuran ini diulangi sampai ditemukan daun jika sudah mencapai daun dikodekan bit masukan tersebut dan kembali ke root. 4. Proses penelusuran kode ini dilakukan hingga keseluruhan string biner masukan diproses.

Dan

berdasarkan

hasil

pengkodean

citra

diatas

didapat

string

biner

“1011110001010111111000100011100101010111”. Bit pertama dari string biner tersebut adalah 1 karena bit yang dibaca adalah 1 maka akan dilakukan penelusuran terhadap pohon Huffman ke arah simpul yang terletak disebelah kanan terlebih dahulu. Kemudian dilakukan penelusuran jika 1 tidak mewakili simbol warna maka akan dibaca bit berikutnya sehingga bit yang akan dibaca menjadi 10. Dan jika 10


27

tidak mewakili simbol warna yang bersesuaian maka akan diambil bit berikutnya sehingga bit yang akan dibaca 101 dan kembali dilakukan penelusuran kembali terhadap pohon Huffman, dan karena 101 mewakili simbol warna 250 yang berakhir pada sebuah daun maka dapat disimpulkan bahwa 101 mewakili simbol warna 250. Setelah itu dilakukan kembali pembacaan terhadap bit berikutnya sehingga didapat bit-bit yang mewakili sebuah simbol warna yang bersesuaian.

2.4 Microsoft Visual Studio 2008

Microsoft Visual Studio 2008 merupakan kelanjutan dari Microsoft Visual Studio sebelumnya, yaitu Visual Studio. NET 2003 yang diproduksi oleh Microsoft (Darmayuda, K, 2010). Visual studio 2008 merupakan salah satu aplikasi pemograman visual yang dibuat oleh Microsoft yang dapat digunakan untuk melakukan pengembangan aplikasi, baik itu aplikasi personal, aplikasi bisnis, aplikasi windows ataupun aplikasi web yang menggunakan bahasa BASIC (Beginners’ Allpurpose Sysbolic Intruction Code). Sesuai dengan namanya bahasa BASIC dibuat untuk tujuan memudahkan pengguna agar dapat dengan mudah mempelajari, membuat, dan mengembangkan program komputer.

Visual basic 2008 ditujukan untuk platform .NET Framework 3.5 yang mendukung konsep pemograman berorientasi objek (Object Oriented Programming). .Net Framnework itu sendiri merupakan platform terbaru untuk membangun, menjalankan, dan meningkatkan generasi lanjut dari aplikasi terdistribusi. Sehingga dapat meningkatkan produktivitas pembuatan sebuah program aplikasi dan kemungkinan terbukanya peluang untuk menjalankan program pada multi sistem operasi serta dapat memperluas pengembangan apliaksi client-server.

.Net Framework terdiri dari 2 bagian utama, yakni Command Languange Runtime (CLR) dan gabungan kelas library termasuk ASP.NET untuk aplikasi web dan XML Web Service, Windows forms untuk aplikasi klien dan ADO.net. Command Languange Runtime (CLR) adalah suatu lingkungan runtime yang memproses, melaksanakan, dan mengatur kode dasar Visual Basic sehingga jalannya program


28

yang dibuat lebih stabil dan penanganan kesalahan lebih baik dengan tujuan supaya program dapat berjalan secara optimum.

2.4.1 IDE Microsoft Visual Studio 2008

Visual Studio 2008 mempunyai IDE (Interface Development Environment) yang lebih lengkap dan mudah digunakan untuk mencari komponen atau objek yang diinginkan. Untuk menempelkan kontrol-kontrol yang ada pada toolbox, cukup klik dan letakkan diatas form, bahkan Visual Studio 2008 telah mampu memformat secara otomatis besar ukuran textbox yang kita buat. Untuk mengatur property dari masing-masing kontrol bisa dilihat pada menu properties window, dan klik ganda pada form untuk memasukkan kode. Pada umumnya IDE Visual Studio 2008 dapat dilihat pada gambar 2.5.

Gambar 2.16 IDE Visual Studio 2008


29

1. Title bar, berfungsi untuk menampilkan nama project yang aktif atau sedang dikembangkan. 2. Menu Bar, berfungsi untuk pengelolaan fasilitas yang dimiliki oleh Visual Basic 2008. 3. Toolbox, berfungsi untuk menyediakan objek-objek atau komponen yang digunakan dalam merancang sebuah form pada program aplikasi. 4. Form, adalah objek utama yang berfungsi untuk meletakkan objek-objek yang terdapat pada Toolbox yang digunakan dalam melakukan perancangan sebuah tampilan program aplikasi. 5. Solution Exploxer, berfungsi untuk menyediakan objek-objek atau komponen yang digunakan dalam merancang sebuah form pada program aplikasi. Sehingga kita dapat dengan mudah mengorganisasikan file penyusun berupa file form, file modul, ataupun file class. 6. Properties Windows, berfungsi yntuk mengatur propertie-properties pada objek (setting object) yang diletakkan pada sebuah form. 7. Data Sources, berisi komponen-komponen yang dapat digunakan untuk melakukan koneksi

ke

database.



BAB 2 LANDASAN TEORI

Recommend Documents