BAB II TEORI DASAR PENGOLAHAN CITRA DIGITAL
2.1
Pendahuluan Citra adalah suatu representasi, 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 penyimpanan[14]. Citra dapat dikelompokkan menjadi dua bagian yaitu citra diam yaitu citra tunggal yang tidak bergerak dan citra bergerak yaitu rangkaian citra diam yang ditampilkan secara beruntun, sehingga memberi kesan pada mata sebagai gambar yang bergerak. Setiap citra didalam rangkaian itu disebut frame. Gambar-gambar yang tampak pada film layar lebar atau televisi yaitu terdiri dari ribuan sampai ratusan-ribu frame[1].
2.2
Citra Analog Citra analog adalah citra yang bersifat kontinu, seperti gambar pada
monitor televisi, foto sinar-X yang tercetak di kertas foto, lukisan, pemandangan alam,
hasil CT-scan, dan
lain sebagainya.
Citra analog tidak
dapat
direpresentasikan dalam komputer sehingga tidak bisa diproses di komputer
Universitas Sumatera Utara
secara langsung. Agar citra analog dapat diproses di komputer, proses konversi analog ke digital harus dilakukan terlebih dahulu[1].
2.3
Citra Digital Citra digital dapat didefinisikan sebagai fungsi dua variabel, f(x,y),
dimana x dan y adalah koordinat spasial dan nilai f(x,y) adalah intensitas citra pada koordinat tersebut, hal tersebut diilustrasikan pada gambar 2.1. Teknologi dasar untuk menciptakan dan menampilkan warna pada citra digital berdasarkan pada penelitian bahwa sebuah warna merupakan kombinasi dari tiga warna dasar, yaitu merah, hijau, dan biru (Red, Green, Blue - RGB). Sensor optik yang terdapat di dalam sistem pencitraan disusun sedemikian rupa sehingga membentuk bidang dua dimensi (x, y). besar intensitas yang diterima sensor di setiap titik (x, y) disimbolkan oleh f(x, y) dan besarnya tergantung pada intensitas yang dipantulkan oleh objek. Ini berarti f(x, y) sebanding dengan energi yang dipancarkan oleh sumber cahaya. Konsekuensinya, besar intensitas f(x, y) tidak bolah nol dan harus berhingga, yaitu[1] : 0 < f (x, y) < ∞
(2.1)
Fungsi f(x, y) dapat dipisahkan menjadi dua komponen, yaitu[14] : 1. Jumlah cahaya yang berasal dari sumbernya disimbolkan oleh i(x, y) (illumination), nilainya antara 0 dan ∞, 2. Derajat kemampuan objek memantulkan cahaya r(x, y) (reflection), nilainya antara 0 dan 1
Universitas Sumatera Utara
Besar f(x, y) merupakan kombinasi perkalian dari keduanya, f(x, y) = i(x, y).r(x, y)
(2.2)
0 < i(x, y) < ∞
(2.3)
0 < r(x, y) < 1
(2.4)
di mana
dan
Nilai i(x, y) ditentukan oleh sumber cahaya, sedangkan r(x, y) ditentukan oleh karakteristik objek di dalam gambar. Nilai r(x, y) = 0 mengindikasikan penyerapan local, sedangkan r(x, y) = 1 menyatakan pemantulan total. Jika permukaan mempunyai derajat pemantulan nol maka fungsi intensitas cahaya f(x, y) juga nol. Sebaliknya, jika permukaan mempunyai derajat pemantulan 1 maka fungsi intensitas cahaya sama dengan iluminasi yang diterima oleh permukaan tersebut. Intensitas f(x, y) di titik (x, y) disebut derajat keabuan (gray level), yang dalam hal ini derajat keabuan bergerak dari hitam ke putih, sedangkan citranya disebut citra skala keabuan (grayscale image). Derajat keabuan memiliki rentang nilai dari Imin < f(x, y) < Imax atau bisa ditulis dalam bentuk (Imin, Imax). Rentang nilai ini sering digeser untuk alasan-alasan praktis menjadi selang [0, L] yang dalam hal ini intensitas 0 menyatakan hitam, nilai intensitas L menyatakan putih[1].
Universitas Sumatera Utara
y
x1, y1
x
Gambar 2.1 Citra Digital Pada Gambar 2.1 mengilustrasikan citra digital sebagai fungsi dua variabel, f(x,y), dimana x dan y adalah koordinat spasial dan nilai f(x,y) adalah intensitas citra pada koordinat tersebut. Citra digital yang berukuran M x N biasanya dinyatakan dalam bentuk matriks yang berukuran M baris dan N kolom, sebagai berikut:
f(x, y) ≈
f (0, 0)
f (0, 1)
….
f(0, N-1)
f (1, 0)
f (1, 1)
….
f(0, N-1)
:
:
:
:
:
:
:
:
f (M-1, 0) f (M-1, 1)
….
f(M-1, N-1) (2.5)
Universitas Sumatera Utara
Setiap elemen pada citra digital ( elemen matriks) disebut image element, picture element atau pixel. 0 0 231 : : 220
(a)
125 165 196 : : 225
155 206 233 : : 198
.... .... .... : : ....
.... .... .... : : ....
200 241 132 : : 133
(b)
Gambar 2.2 (a) Citra Digital ; (b) Matriks dari Gambar 2.2 (a) Pada Gambar 2.2 menunjukkan hasil matriks dari gambar 2.2 (a). Pada Gambar 2.2 (b) dimana nilai-nilai pada matriks tersebut yang dapat diproses pada komputer.
2.3.1 Citra Warna RGB adalah suatu model warna yang terdiri dari merah, hijau, dan biru, digabungkan dalam membentuk suatu susunan warna yang luas. Setiap warna dasar, misalnya merah, dapat diberi rentang-nilai. Untuk monitor komputer, nilai rentangnya paling kecil = 0 dan paling besar = 255. Pilihan skala 256 ini didasarkan pada cara mengungkap 8 digit bilangan biner yang digunakan oleh mesin komputer. Dengan cara ini, akan diperoleh warna campuran sebanyak 256 x 256 x 256 = 1677726 jenis warna. Sebuah jenis warna, dapat dibayangkan sebagai sebuah vektor di ruang 3 dimensi yang biasanya dipakai dalam matematika,
Universitas Sumatera Utara
koordinatnya dinyatakan dalam bentuk tiga bilangan, yaitu komponen-x, komponen-y, dan komponen-z. Misalkan sebuah vektor dituliskan sebagai r = (x,y,z). Untuk warna, komponen-komponen tersebut digantikan oleh komponen R(ed), G(reen), B(lue).
Gambar 2.3 Citra Warna [14] Gambar 2.3 menunjukkan piksel dari warna-warna yang dapat merupakan kombinasi dari tiga warna utama RGB, yaitu red, green, and blue. Jadi, sebuah jenis warna dapat dituliskan sebagai : warna = RGB(30, 75, 255), putih = RGB (255,255,255), sedangkan untuk hitam= RGB(0,0,0).
2.3.2 Citra Gray Graysacale adalah warna-warna piksel yang berada dalam rentang gradasi warna hitam dan putih.
Universitas Sumatera Utara
Gambar 2.4 Color Dialog untuk Melihat Rentang Warna Pada Color Dialog seperti yang terlihat pada Gambar 2.4 , jika memilih warna solid hitam, putih, atau abu-abu, maka akan berada dalam pita warna grayscale. Apabila tanda panah digeser ( ke atas menuju putih atau ke bawah menuju ke hitam ) maka red, green dan blue akan memberikan nilai yang sama.
Gambar 2.5 Perubahan Citra Digital Original ke Citra Grayscale
Universitas Sumatera Utara
Untuk pengubahan warna image menjadi grayscale, cara yang umumnya dilakukan adalah dengan memberikan bobot untuk masing-masing warna dasar red, green, dan blue seperti terlihat pada Gambar 2.5 . Akan tetapi cara yang cukup mudah adalah dengan membuat nilai rata-rata dari ketiga warna dasar tersebut dan kemudian mengisikannya untuk warna dasar tersebut dengan nilai yang sama[6].
2.3.3 Citra Biner Citra biner diperoleh melalui proses pemisahan piksel-piksel berdasarkan derajat keabuan yang dimilikinya.
Gambar 2.6 Citra Biner Gambar 2.6 memperlihatkan piksel yang memiliki derajat keabuan lebih kecil dari nilai batas yang ditentukan akan diberikan nilai 0, sementara piksel yang memiliki derajat keabuan yang lebih besar dari batas akan diubah menjadi bernilai 1. F (x, y) ‘ = a1, f (x, y) < T a2, f (x, y) ≥ T
(2.6)
Universitas Sumatera Utara
Jika a1 =0 dan a2 = 1, maka operasi ini akan mentransformasikan suatu citra menjadi citra biner. Misal suatu citra memiliki gray level 256, dipetakan menjadi citra biner, maka fungsi trasformasinya adalalah sebagai berikut: f (x, y)’ = 0, f (x, y) < 128 1, f (x, y) ≥ 128
(2.7)
Pixel-pixel yang nilai intensitasnya di bawah 128 diubah menjadi hitam (nilai intensitas = 0), sedangkan pixel-pixel yang nilai intensitasnya di atas 128 diubah menjadi putih (nilai intensitas =1)[6].
2.4
Digitalisasi Citra Citra analog tidak bisa diproses langsung oleh komputer. Citra analog
harus diubah menjadi citra digital (pencitraan) agar komputer bisa memprosesnya. Proses mengubah citra analog menjadi citra digital disebut digitalisasi citra. Ada dua hal yang harus dilakukan pada digitalisasi citra, yaitu digitalisasi spasial yang disebut juga sebagai sampling dan digitalisasi intensitas yang sering disebut sebagai kuantisasi. Citra yang dihasilkan dari peralatan digital (citra digital) langsung bisa diproses oleh komputer karena di dalam peralatan digital sudah terdapat sistem sampling dan kuantisasi. Sedangkan peralatan analog tidak dilengkapi kedua sistem tersebut. Kedua sistem inilah yang bertugas memotong-motong citra menjadi x kolom dan y baris (proses sampling), sekaligus menentukan besar
Universitas Sumatera Utara
intensitas yang terdapat pada titik tersebut (proses kuantisasi) sehingga menghasilkan resolusi citra yang diinginkan[1].
2.4.1 Sampling Sampling adalah transformasi citra kontinu menjadi citra digital dengan cara membagi citra analog (kontinu) menjadi M kolom dan N baris sehingga menjadi citra diskrit. Semakin besar nilai M dan N, semakin halus citra digital yang dihasilkan dan artinya resolusi citra semakin tinggi. Persilangan antara baris dan kolom tertentu disebut dengan piksel. Proses sampling dihasilkan oleh peralatan digital, misalnya scanner, foto digital, dan kamera digital. Kamera digital biasanya menggunakan sensor optik jenis CCD (Charge Coupled Device) yang membentuk sebuah larik berukuran M kolom dan N baris. Sensor jenis CCD digunakan untuk mendeteksi intensitas cahaya yang masuk ke dalam kamera. Keluaran dari matriks CCD berupa arus yang besarnya sebanding dengan intensitas cahaya yang mengenainya. Arus tersebut kemudian dikonversi menjadi data digital yang kemudian dikirimkan ke unit penampil atau unit pengolah lainnya. Jumlah seluruh pantulan cahaya yang masuk ke sensor CCD sebenarnya adalah citra analog 2 dimensi. Oleh sensor optik dari seluruh pantulan cahaya ini diterima hanya sebagian saja, yaitu sebesar ukuran larik tadi (MxN). Akibatnya ada beberapa informasi citra yang hilang yang tidak tertangkap oleh sensor.
Universitas Sumatera Utara
Inilah yang dimaksud dengan sampling, yaitu pengambilan sebagian cahaya dari seluruh cahaya yang diterima oleh sensor. Oleh karena cahaya yang diterima sensor hanya sebesar larik berukuran M kolom dan N baris maka citra analog 2 dimensi ini diproyeksikan menjadi citra digital 2 dimensi berukuran M kolom dan N baris. Sebagian
informasi
yang
hilang
(a)
(b)
(c)
Gambar 2.7 (a) Citra Analog, (b) Citra Analog Disampling Menjadi 14 Baris dan 12 Kolom, (c) Citra Digital Hasil Sampling Berukuran 14 x 12 Piksel Gambar 2.7[1] menunjukkan proses sampling dari citra analog menjadi citra digital berukuran 14 x 12 piksel yang mengakibatkan adanya beberapa bagian informasi citra yang hilang[1].
Universitas Sumatera Utara
2.4.2 Kuantisasi Warna sebuah citra digital ditentukan oleh besar intensitas piksel-piksel penyusunnya. Warna ini diperoleh dari besar kecilnya intensitas cahaya yang ditangkap oleh sensor. Sedangkan skala intensitas cahaya di alam tidak terbatas, yang bisa menghasilkan warna dengan jumlah yang tak terhingga. Sampai saat ini belum ada satu sensor pun yang mampu menangkap seluruh gradasi warna tersebut. Keterbatasan inilah yang mengharuskan kita membuat gradasi warna sesuai dengan kebutuhan. Transformasi intensitas analog yang bersifat kontinu ke daerah intensitas diskrit disebut kuantisasi. Proses kuantisasi dihasilkan oleh peralatan digital, misalnya scanner, foto digital, dan kamera digital[1]. Perhatikan Gambar 2.7 (b) dan (c). Misalnya besar memori yang digunakan untuk meyimpan warna adalah 3 bit maka gradasi warna citra analog Gambar 2.7 (b) hanya diwakili oleh gradasi warna 3 bit ini. kemudian, dilakukan kuantisasi untuk setiap piksel. Warna tiap-tiap piksel disesuaikan dengan gradasi warna yang disediakan oleh memori.
Universitas Sumatera Utara
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
0
0
7
7
7
7
7
7
7
7
7
0
0
0
7
7
7
7
7
7
7
0
0
0
0
7
7
7
7
7
7
7
0
0
2
4
7
7
7
7
7
7
7
0
3
4
4
4
7
7
7
7
7
7
0
3
5
5
4
4
0
7
7
7
7
0
3
5
5
4
4
0
0
7
7
7
0
3
2
4
0
0
0
0
7
7
7
0
0
0
0
0
0
0
0
7
7
7
7
0
0
0
0
0
0
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
Gambar 2.8 Matriks Berisikan Intensitas Hasil citra digital yang disimpan oleh memori hanyalah nilai-nilai intensitas yang ditunjukkan pada Gambar 2.8 , yang berbentuk matriks berukuran 14 baris x 11 kolom. Setelah tiap-tiap piksel dikuantisasi, nilai-nilai intensitas diperoleh sebagai berikut. Nilai-nilai
diatas
diperoleh
setelah
dikuantisasi,kemudian
untuk
selanjutnya akan ditulis dalam bentuk asimetris.
Universitas Sumatera Utara
Bila cita digital tersebut ditulis dalam bentuk asimetris sebagai fungsi f(x, y) maka :
F(x, y)
1
2
3
4
5
6
7
8
9
10
11
1
7
7
7
7
7
7
7
7
7
7
7
2
7
7
7
7
7
7
7
7
7
7
7
3
7
7
0
0
7
7
7
7
7
7
7
7
4
7
7
0
0
0
7
7
7
7
7
7
5
7
0
0
0
0
7
7
7
7
7
7
6
7
0
0
2
4
4
7
7
7
7
7
7
7
7
0
3
4
4
4
7
7
7
7
7
8
7
0
3
5
55
4
4
0
7
7
7
9
7
0
3
5
5
4
4
0
0
7
7
10
7
0
3
22
4
0
0
0
0
7
7
11
7
0
0
0
0
0
0
0
0
7
7
12
7
7
0
0
0
0
0
00
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
13 14
x Gambar 2.9 Matriks Nilai Asimetris Seperti ditunjukkan pada Gambar 2.9, f(3, 10) = 7 artinya piksel di titik (3, 10) mempunyai nilai intensitas sebesar 7, f (6, 5) = 4 artinya piksel di titik (6, 5) mempunyai nilai intensitas 4, dan seterusnya. 2.5
Kompresi Data Kompresi Data merupakan cabang ilmu komputer yang bersumber dari
Teori Informasi. Teori Informasi sendiri adalah salah satu cabang Matematika yang berkembang sekitar akhir dekade 1940-an. Tokoh utama dari Teori Informasi adalah Claude Shannon dari Bell Laboratory. Teori Informasi memfokuskan pada
Universitas Sumatera Utara
y
f(3, 10) = 7
f(6, 5) = 4
f(8, 5) = 5 f(10, 4) = 2
f(12, 8) = 0
berbagai metode tentang informasi termasuk penyimpanan dan pemrosesan pesan. Teori Informasi mempelajari pula tentang redundancy (informasi tak berguna) pada pesan. Semakin banyak redundancy semakin besar pula ukurang pesan, upaya mengurangi redundancy inilah yang akhirnya melahirkan subyek ilmu tentang Kompresi Data[8]. Teori Informasi menggunakan terminologi entropy sebagai pengukur berapa banyak informasi yang dapat diambil dari sebuah pesan. Kata “entropy” berasal dari ilmu termodinamika. Semakin tinggi entropy dari sebuah pesan semakin banyak informasi yang terdapat di dalamnya. Entropy dari sebuah simbol didefinisikan sebagai nilai logaritma negatif dari probabilitas kemunculannya. Untuk menentukan konten informasi dari sebuah pesan dalam jumlah bit dapat digunakan rumus sebagai berikut: number of bits = -log base 2 (probability)
(2.8)
Entropy dari keseluruhan pesan adalah jumlah dari keseluruhan entropy dari seluruh symbol. Data Compression Original Data
Compressed Data Data Decompression
Gambar 2.10 Proses Kompresi Data Secara Umum Pada Gambar 2.10 ditunjukkan proses kompresi data secara umum yang dapat dengan mudah dipahami. Berikut ini adalah beberapa teknik kompresi data yang dikategorikan menurut jenis data yang akan dikompresi, yaitu[4]:
Universitas Sumatera Utara
1. Teknik kompresi untuk citra diam (still image) Contoh: JPEG, GIF dan run-length. 2. Teknik kompresi untuk citra bergerak (motion picture) Contoh: MPEG. 3. Teknik kompresi untuk data teks Contoh: half byte. 4. Teknik kompresi untuk data umum Contoh: LZW, half byte, dan Huffman. 5. Teknik kompresi untuk data sinyal speech Contoh: PCM, SBC, LPC, dan CELP.
Ada empat pendekatan yang digunakan pada kompresi suatu data, yaitu[4]: 1. Pendekatan statistik Contoh: Huffman coding. 2. Pendekatan ruang Contoh: Run-Length encoding 3. Pendekatan kuantisasi Contoh: Kompresi kuantisasi (CS&Q) 4. Pendekatan Fraktal Contoh: Fractal image compression
Universitas Sumatera Utara
2.5.1 Teknik Kompresi Data Teknik Kompresi Data dapat dibagi menjadi dua kategori besar, yaitu[1]: 1. Lossy Compression Lossy compression menyebabkan adanya perubahan data dibandingkan sebelum dilakukan proses kompresi. Sebagai gantinya lossy compression memberikan derajat kompresi lebih tinggi. Tipe ini cocok untuk kompresi file suara digital dan gambar digital. File suara dan gambar secara alamiah masih bisa digunakan walaupun tidak berada pada kondisi yang sama sebelum dilakukan kompresi.
2. Lossless Compression Sebaliknya Lossless Compression memiliki derajat kompresi yang lebih rendah tetapi dengan akurasi data yang terjaga antara sebelum dan sesudah proses kompresi. Kompresi ini cocok untuk basis data, dokumen atau spreadsheet. Stream Input
Kompresi
Stream
Hasil
Dekompresi
Output Lossless (M = M’)
Dekompresi (M’) Lossy (M
M’)
Gambar 2.11 Proses Kompresi Data Secara Lossless dan Lossy[4]
Universitas Sumatera Utara
Pada lossless compression ini tidak diijinkan ada bit yang hilang dari data pada proses kompresi, seperti yang ditunjukkan pada Gambar 2.11.
2.5.2 Manfaat Beberapa manfaat kompresi adalah[1]: 1. Waktu pengiriman data pada saluran komunikasi data menjadi lebih singkat. Contohnya pengiriman gambar dari faximile, video confrencing, handphone, download dari internet pengiriman data medis, pengiriman dari satelit, dan lain-lain. 2. Membutuhkan ruang memori dalam storage yang lebih sedikit dibandingkan dengan data yang tidak dimampatkan. 3. Efisiensi penggunaan bandwidth pada jaringan telekomunikasi.
2.5.3 Kriteria Kompresi Kriteria yang digunakan untuk mengukur kompresi adalah[1]: 1. Waktu kompresi dan waktu dekompresi Proses kompresi merupakan proses mengkodekan data atau citra sehingga diperoleh data dengan representasi kebutuhan memori yang minimum. Data terkompresi disimpan dalam file dengan format tertentu, misalnya JPEG atau MPEG. Sedangkan proses dekompresi adalah proses untuk menguraikan citra atau data yang dimampatkan untuk dikembalikan lagi menjadi citra yang tidak mampat. Algoritma
Universitas Sumatera Utara
pemampatan yang paling baik adalah algoritma yang membutuhkan waktu untuk kompresi dan dekompresi yang paling sedikit 2. Kebutuhan memori Metode kompresi yang baik adalah metode kompresi yang mampu
mengompresi
file
menjadi
ukuran
yang
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 Metode kompresi yang baik adalah metode kompresi yang mampu mengembalikan citra hasil kompresi menjadi citra semula tanpa kehilangan informasi apapun. Kalaupun ada informasi yang hilang akbat pemampatan, sebaiknya hal itu ditekan seminimal mungkin. 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 pemampatan semakin mendekati citra aslinya, dengan kata lain semakin bagus kualitas citra hasil pemampatan
Universitas Sumatera Utara
tersebut. Sebaliknya, semakin kecil nilai PSNR, semakin jelek kualitas citra hasil pemampatan. Rumus untuk menghitung PSNR adalah sebagai berikut:
PSNR = 10
= 20
(2.9)
Dimana MAX adalah nilai intensitas terbesar. Nilai MSE dihitung dengan persamaan berikut: MSE =
2
(2.10)
Dalam hal ini, m dan n masing masing adalah lebar dan tinggi citra,I dan K masing masing adalah nilai intensitas baris ke i dan kolom ke-j dari citra hasil pemampatan dan citra sebelum dimampatkan. PSNR mempunyai satuan decibel (dB). 4.
Format keluaran Format citra hasil pemampatan yang baik adalah yang cocok dengan kebutuhan pengiriman dan peyimpanan data.
2.5.4 Rasio Kompresi Rasio kompresi adalah ukuran persentase citra yang telah berhasi dimampatkan. Secara matematis rasio pemampatan citra dituliskan sebagai berikut[1]: Rasio = 100% - (HasilKompresi / Citra Asli x 100%)
(2.11)
Universitas Sumatera Utara
2.6
Run-Length Encoding Teknik Run-Length bekerja berdasarkan sederetan karakter yang
berurutan. Data masukan akan dibaca dan sederetan karakter yang sesuai dengan karakter yang sudah ditentukan sebelumnya disubstitusi dengan kode tertentu. Kode khusus ini biasanya terdiri dari tiga buah karakter. Seperti yang diperlihatkan pada Gambar 2.13. Sc
Cc
X
Gambar 2.12 Karakter pada Run-Length Keterangan: Sc
= Karakter khusus yang dipakai sebagai tanda kompresi
Cc
= Banyaknya karakter yang dekompresi
X
= Karakter berurutan yang akan dikompresi
Sebagai contoh sederhana apabila karakter khusus (Sc) yang digunakan adalah # dan Cc dalam bilangan desimal, maka jika digunakan untuk kompresi string “Jarrrrrringan”, maka akan diperoleh hasil “Ja#6ringan”. 010000001 010000001 010000001 010000001 010000001
11111110 00001000 8x
Gambar 2.13 Contoh Kompresi Menggunakan Algoritma Run-Length[4]
Universitas Sumatera Utara
Gambar 2.13 memperlihatkan contoh kompresi dengan menggunakan RunLength. Dimana algoritma komperesi dengan menggunakan metode Run-Length adalah sebagai berikut[4]: 1. Cari deretan karakter yang sama secara berurutan, jika ada lakukan kompresi. 2. Tulis byte penanda file kompresi, byte penanda berupa 8 deretan bit yang boleh dipilih sembarang asalkan digunakan secara konsisten pada seluruh byte penanda kompresi. Byte penanda ini berfungsi untuk menandai bahwa karakter
selanjutnya
adalah
karakter
kompresi
sehingga
tidak
membingungkan pada saat mengembalikan file yang sudah dikompresi ke file aslinya. 3. Tulis deretan bit untuk menyatakan jumlah karakter yang sama berurutan. 4. Tulis deretan bit untuk menyatakan karakter yang berulang. 5. Ulangi langkah 1-4 hingga karakter terakhir. Dan untuk algoritma dekomperesi dengan menggunakan metode RunLength adalah sebagai berikut: 1. Lihat karakter pada hasil kompresi satu per satu dari awal hingga akhir, jika ditemukan byte penanda, lakukan proses pengembalian. 2. Lihat karakter setelah byte penanda, konversikan ke bilangan 29ecimal untuk menentukan jumlah karakter yang berurutan. 3. Lihat karakter berikutnya, kemudian lakukan penulisan karakter tersebut sebanyak bilangan yang telah diperoleh pada karakter sebelumnya. 4. Ulangi langkah 1-3 sampai karakter terakhir.
Universitas Sumatera Utara
Algoritma RLE menggunakan pendekatan ruang. Algoritma ini cocok digunakan untuk menempatkan citra yang memiliki kelompok-kelompok piksel berderajat keabuan yang sama. Metode ini dilakukan dengan menyatakan seluruh baris citra menjadi sebuah baris run, lalu menghitung run-length unutk setiap derajat keabuan yang berurutan. Contoh, andaikan string “ABBABABACAACDDD” akan di-encode dengna 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 10x10 piksel akan di encode dengan algoritma RLE dapat dilihat pada gambar 2.14 2
2
7
7
7
7
2
2
2
2
4
4
1
1
1
7
7
7
6
6
7
7
7
7
3
3
3
3
3
4
4
4
5
5
5
5
2
2
2
2
5
5
5
5
6
6
6
3
3
2
7
7
7
6
6
6
6
2
2
2
2
2
3
3
3
3
5
4
5
6
7
7
7
7
7
7
4
4
4
4
0
0
0
0
0
0
0
0
0
0
1
1
1
4
5
4
4
5
5
5
Gambar 2.14 Matriks citra grayscale 3 bit berukuran 10x10 piksel
Universitas Sumatera Utara
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 pengkodean : 22742442137574364254245466736423 4235537644 0 10 1 3 4 2 2 2 5 3 Semuanya berjumlah 52 piksel Ukuran citra sebelum dikompres
= 10 x 10 x 3 bit = 300 bit
Ukuran citra setelah dikompres
= 52 x 3 bit = 156 bit
Universitas Sumatera Utara
Rasio pemampatan = 100%- ((156/300) x 100 %) = 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 untuk meningkatkan ratio kompresi. Mula-mula lakukan kompresi RLE, lalu hasilnya dimampatkan lagi dengan metode Huffman.
2.7 Algoritma Huffman Metode Huffman adalah metode pengkodean yang telah banyak diterapkan untuk aplikasi kompresi citra. Seperti metode Shannon Fano, metode Huffman juga membentuk pohon atas dasar probabilitas setiap symbol, namun teknik pembentukan pohonnya berbeda[2]. Berikut ini adalah langkah-langkah algoritman Huffman[2]: 1. Data dianalisis dahulu dengan cara membuat table frekuensi kemunculan setiap symbol ASCII, table frekuensi tersebut memiliki atribut berupa symbol ASCII dan frekuensi. 2. Dua data yang memiliki frekuensi kemunculan paling kecil dipilih sebagai simpul pertama pada pohon Huffman. 3. Dari dua simpul ini dibuat simpul induk yang mencatat jumlah frekuensi dua simpul pertama.
Universitas Sumatera Utara
4. Kemudian dua simpul tersebut dihapus dari table digantikan oleh simpul induk tadi. Simpul ini kemudian dijadikan acuan untuk membentuk pohon. 5. Langkah 3-5 dilakukan dengan berulang-ulang hingga isi table tinggal satu saja. Data inilah yang akan menjadi simpul bebas atau simpul akar. 6. Setiap simpul yang terletak pada cabang kiri (simpul dengan frekuensi lebih besar) diberi nilai 0 dan simpul yang terletak pada cabang kanan (simpul dengan frekuensi lebih kesil) diberi nilai 1. 7. Pembacaan dilakukan dari simpul akar kearah simpul daun dengan memperhatikan nilai setiap cabang. Berikut adalah contoh implementasi algoritma Huffman yang telah dipaparkan di atas. Kata yang ingin dikompresi : biaaabuatnnnbkis Tabel 2.1 Frekuensi Simbol[2] Simbol a
Frekuensi 4
b
3
n
3
i
2
k
1
s
1
t
1
u
1
Proses pembentukan pohon Huffman dimulai dari menggabung symbol “u” dan “I” (dua symbol terbawah) dengan frekuensi berjumlah 2. Gabungan 2
Universitas Sumatera Utara
simbol tersebut (“ui”) dipakai sebagai acuan untuk bergerak ke atas. Karena symbol “s” frekuensinya masih lebih kecil dari symbol “ui”, maka symbol “s” digabung dengan symbol di atasnya (“k”) menghasilkan symbol “sk”. Gabungan tersebut menghasilkan freuensi berjumlah 2. Symbol “ui” dan “sk” membentuk pohon Huffman dengan total frekuensi berjumlah 4. Proses pergerakan ke atas kemudian dilanjutkan sehingga dihasilkan pohon Huffman seperti Gambar 2.14 Pohon Huffman pada Gambar 2.14 dibentuk atas dasar simbol yang memiliki frekuensi lebih tinggi dikodekan dengan nilai “0” dan yang lebih rendah dengan nilai “1”. Root 0
1 (16) 0
1 (9)
0
7 1
a (4)
b (3)
(5) n (3)
0
(2)
1 (4)
0
1
0
(2) k (1)
1 (2)
s (1)
l (1)
u (1)
Gambar 2.15 Pohon Huffman dari kata “biaaabuatnnnbkis” Berdasarkan Gambar 2.15 di atas, maka setiap symbol dapat dikodekan seperti ditunjukkan pada Tabel 2.2.
Universitas Sumatera Utara
Tabel 2.2 Hasil Proses Pengkodean Huffman Simbol
Frekuensi
Kode
a b n i k s t u Total
4 3 3 2 1 1 1 1 16
10 01 000 001 0100 0101 0110 0111
Jumlah Bit Kode 2 2 3 3 4 4 4 4
Total Bit 8 6 9 6 4 4 4 4 45 bit
Setelah mengamati hasil pengkodean Huffman di atas dapat dilihat bahwa jumlah total bit dari seluruh symbol adalah 45 bit. Dalam ukuran byte, hasil kompresi di atas dapat dibulatkan menjadi 6 byte (45 bit/8 byte = 5.625). Contoh berikut menyajikan pengkodean Huffman pada suatu contoh matrik (citra) berukuran 8 x 8 piksel. 13
-3
-3
0
0
0
0
0
-1
-3
0
0
0
0
0
0
0
0 -3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Gambar 2.16 Contoh Citra
Universitas Sumatera Utara
Frekuensi kemunculan objek pada gambar di atas disajikan pada table 2.3. Tabel 2.3 Frekuensi Objek Gambar 2.14 Objek
Frekuensi
0
58
-3
4
-1
1
13
1
Pohon Huffman dari citra pada Gambar 2.16 dapat dilihat pada Gambar 2.17
Root 1
0
0
1
0
1
0
13
-1
-3
Gambar 2.17 Pohon Huffman dari citra pada Gambar 2.16
Tabel 2.4 menyajikan kode Huffman beserta kebutuhan bit dari pohon Huffman pada Gambar 2.17
Universitas Sumatera Utara
Tabel 2.4 Frekuensi Objek Kode Huffman Objek
Frekuensi
Kode
Panjang Bit
Total Bit
Kode 0
58
0
1
58
-3
4
10
2
8
-1
1
110
3
3
13
1
111
3
3
Jumlah
64
72 bit
Berdasarkan Tabel 2.4 dibutuhkan sekitar 72 bit (atau 9 byte) untuk menyimpan gambar di atas, di mana bila tidak dikompresi dibutuhkan sekitar 64 byte.
2.8
Metode Kompresi Ada banyak metode yang dapat digunakan dalam proses kompresi.
Namun, secara garis besarnya metode yang digunakan dapat diklasifikasikan ke dalam dua metode, yaitu [4]: 1. Metode statis (static method) 2. Metode kamus (dictionary method)
Universitas Sumatera Utara
2.8.1 Metode Statis (Static Method) Metode statis (static method) adalah metode kompresi yang bekerja dengan cara memetakan data terlebih dahulu kedalam kode-kode (encoding) sebelum proses kompresi dilakukan, sehingga data tersebut akan dipresentasikan dengan kode-kode pada saat data itu disimpan atau akan dikirimkan sebelum diubah kembali seperti data aslinya (decoding).
2.8.2 Metode Kamus (Dictionary Method) Metode kamus (dictionary method) adalah metode kompresi yang melakukan penyeleksian string dari data, yang kemudian sebagian dari string tersebut akan diubah menjadi kode dan kamus akan menyimpan kode string setiap proses penyeleksian dilakukan. Isi dari kamus tersebut bisa tetap atau berubahubah. Hal ini tergantung pada input data, karena setiap pembacaan data akan dilakukan proses penyeleksian yang akan mengakibatkan bertambahnya isi dari kamus tersebut sehingga kamus tersebut berubah-ubah.
Universitas Sumatera Utara
