BAB II LANDASAN TEORI. berawal dari suatu ide untuk menyimpan segitiga Sierpinski menggunakan

BAB II LANDASAN TEORI

Metode kompresi citra fraktal merupakan metode kompresi citra yang berawal dari suatu ide untuk menyimpan segitiga Sierpinski menggunakan Iterated Function System (IFS). Segitiga Sierpinski merupakan salah satu contoh citra fraktal dan setiap citra fraktal dapat dibentuk oleh kumpulan transformasi affine kontraktif yang disebut IFS. Pemahaman yang baik terhadap proses pembentukan citra fraktal menggunakan IFS, merupakan hal yang sangat penting untuk pengembangan metode kompresi citra fraktal. Oleh karena itu, pada bab II ini dibahas beberapa dasar teori yang mendukung, seperti pengertian citra fraktal, ruang citra, transformasi affine kontraktif serta IFS. Selain itu, diberikan pula pengenalan konsep dasar algoritma genetika. Citra yang menjadi objek kompresi dalam skripsi ini adalah citra berskala keabuan (gray-scale image). Oleh karena itu, setiap penggunaan kata “citra” pada skripsi ini, mengacu pada citra berskala keabuan, kecuali bila disebutkan lain.

Kompresi Citra..., Lhuqita Fazry, FMIPA UI, 2008

7

8

2.1 CITRA DIGITAL

Citra digital tersusun atas sejumlah tertentu pixel. Setiap pixel pada citra memiliki suatu nilai yang disebut nilai intensitas pixel. Nilai intensitas pixel merupakan nilai yang menentukan derajat keabuan pixel tersebut. Nilai intensitas pixel untuk citra merupakan bilangan bulat yang berkisar dari 0 sampai 255. Citra dengan karakter seperti ini disebut sebagai citra dengan 256 = 28 skala keabuan atau citra 8 bit karena terdapat 256 (0 - 255) nilai intensitas pixel yang mungkin [12]. Nilai intensitas pixel 0 menunjukan intensitas hitam atau gelap dan nilai intensitas pixel 255 menunjukan intensitas putih atau terang, sedangkan nilai intensitas pixel antara 0 dan 255 menunjukan intensitas yang berkisar antara hitam dan putih. Gambar 3 menunjukan rentangan nilai intensitas pixel [12].

Gambar 3. Intensitas pixel

Citra digital berdimensi M  N pixel dapat direprensentasikan oleh sebuah matriks berukuran M  N . Elemen  i, j  pada matriks merupakan


9

pixel  i, j  pada citra. Nilai elemen matriks aij adalah nilai intensitas pixel

 i, j 

pada citra [9]. Jumlah bit ( b ) yang dibutuhkan untuk menyimpan citra digital

berdimensi M  N pixel dengan 2k skala keabuan adalah [9] b  M N k

(2.1)

Sebagai contoh: sebuah citra 8 bit (28 = 256 skala keabuan) berdimensi 256  256 pixel membutuhkan memori penyimpanan sebesar 256  256  8 = 524.288 bit atau 65.536 byte (1 byte = 8 bit).

2.2 CITRA FRAKTAL

Citra fraktal merupakan citra yang bersifat self-similarity, yaitu bagianbagian citra sama dengan citra secara keseluruhan. Contoh citra fraktal adalah segitiga Sierpinski [12]. Segitiga Sierpinski dibentuk oleh tiga bagian. Ketiga bagian tersebut terlihat sama dengan segitiga Sierpinski secara keseluruhan. Ketiga bagian tersebut juga dibentuk oleh tiga bagian yang lebih kecil, yang juga terlihat sama dengan segitiga Sierpinski secara keseluruhan. Gambar 4 memperlihatkan segitiga Sierpinski.


10

Gambar 4. Segitiga Sierpinski

Gambar 4 menunjukan bahwa segitiga Sierpinski dibentuk oleh tiga bagian yang ditandai oleh lingkaran. Masing-masing dari bagian tersebut sama dengan segitiga Sierpinski secara keseluruhan. Kesamaan ini ditandai dengan tanda panah.

2.3 SIFAT CITRA

Langkah awal yang dilakukan dalam kompresi citra fraktal adalah melakukan partisi terhadap citra yang akan dikompresi. Mempartisi citra berarti membagi citra menjadi sejumlah blok (bagian) citra. Terdapat berbagai macam metode untuk mempartisi citra, akan tetapi pada skripsi ini, partisi citra yang digunakan dibatasi pada partisi reguler (fixed size). Mempartisi


11

citra menggunakan partisi reguler maksudnya adalah setiap blok hasil partisi memiliki ukuran yang sama. Bagaimanakah sifat blok hasil partisi citra? Berikut ini adalah beberapa sifat citra yang berhubungan dengan partisi citra. Misalkan  merupakan himpunan citra, maka  memiliki beberapa sifat, yaitu [3]: 1. Untuk setiap citra I   memiliki sebuah pendukung dan dimensi. Pendukung dari citra I merupakan himpunan  yang didefinisikan sebagai berikut:

   x, y  a  x  b, c  y  d ,

a, b, c, d  

Sebuah pendukung  dari citra I diilustrasikan sebagai media tempat citra tersebut berada. Gambar 5 mengilustrasikan sebuah pendukung dari citra I . Y d

c a

b

X

Gambar 5. Pendukung dari citra Dimensi dari citra I adalah b  a  satuan dan d  c  satuan. Dalam hal ini, ukuran satuan menunjukan satuan inci, meter, pixel atau satuan ukuran yang lainnya.


12

Suatu titik pada citra merupakan titik pada pendukungnya, begitu juga sebaliknya. Metrik d dari titik  x1 , y1  dan  x2 , y2  pada pendukung citra, dihitung menggunakan persamaan berikut:

d

x1  x2 2   y1  y 2 2

(2.2)

2. Himpunan citra  tertutup terhadap operasi pemotongan (clipping) Diberikan suatu citra I   . Jika dilakukan operasi pemotongan terhadap I , dengan aturan setiap sisi citra hasil pemotongan pararel

~ terhadap sisi dari I , maka citra hasil pemotongan, yaitu I , merupakan anggota dari  . Dari sini dapat disimpulkan bahwa hasil pemotongan suatu citra juga merupakan citra. Gambar 6 menunjukan operasi pemotongan pada citra.

Gambar 6. Operasi pemotongan


13

3. Himpunan citra  tertutup terhadap operasi perentangan (strecthing) dan operasi penyusutan (shringking)

~ Diberikan suatu citra I   . Jika I merupakan citra hasil operasi ~ perentangan dan penyusutan I , maka I   . Dari sini dapat disimpulkan bahwa hasil perentangan dan penyusutan citra juga merupakan citra. Operasi perentangan merupakan operasi yang memperbesar dimensi citra dari dimensi citra asal dengan faktor skala tertentu, sedangkan operasi penyusutan merupakan operasi yang memperkecil dimensi citra dari dimensi citra asal juga dengan faktor skala tertentu. Gambar 7 menunjukan operasi perentangan dan penyusutan pada citra.

perentangan

penyusutan

Gambar 7. Operasi perentangan dan penyusutan


14

4. Himpunan citra  tertutup terhadap operasi pencerminan

~ Diberikan suatu citra I   . Jika I merupakan citra hasil pencerminan I terhadap suatu garis yang pararel terhadap salah satu sisi dari

~ pendukungnya, maka I   , sehingga dapat disimpulkan bahwa hasil pencerminan citra juga merupakan citra. Perhatikan Gambar 8.

pencerminan

Gambar 8. Operasi pencerminan

5. Himpunan citra  tertutup terhadap operasi pemutaran (rotation).

~ Diberikan suatu citra I   . Jika I merupakan citra hasil pemutaran ~ I sebesar sudut tertentu, maka I   , sehingga dapat disimpulkan bahwa hasil pemutaran citra sebesar sudut tertentu juga merupakan citra.

pemutaran 300

Gambar 9. Operasi pemutaran


15

2.4 RUANG METRIK DAN TRANSFORMASI AFFINE KONTRAKTIF

Prinsip dari kompresi citra fraktal adalah mencari kumpulan transformasi affine kontraktif W . Jika diberikan suatu citra A  yang akan dikompresi, maka kompresi terhadap citra A dilakukan dengan mencari kumpulan transformasi affine kontraktif W sedemikian sehingga titik tetap (fixed point) dari W adalah A dan A  W  A  serta A  lim W  n  B  untuk n

setiap B  . Agar terjamin bahwa lim W  n ada, maka citra haruslah merupakan n 

anggota dari suatu ruang metrik yang lengkap. Berikut adalah beberapa definisi yang berhubungan dengan ruang metrik yang lengkap dan transformasi affine kontraktif. Definisi 1 [3]. Ruang metrik  X , d  merupakan himpunan X bersama dengan fungsi bernilai riil d : X  X   yang mengukur jarak antara titik

x, y  X . Anggap d memenuhi sifat berikut: a. d  x, y   0,

x, y  X

b. d  x, y   0  x  y c. d  x, y   d  y , x  ,

x, y  X

d. d  x, y   d  x, z   d  z , y  ,

 x, y , z  X

maka d disebut metrik pada himpunan X .


16



Definisi 2 [2]. Misalkan  X , d  merupakan ruang metrik. Barisan  xn n 1 pada himpunan X merupakan barisan cauchy, jika untuk setiap   0 , terdapat n0   sedemikian sehingga d  xn , xm    untuk setiap n, m  n0 Definisi 3 [2]. Ruang metrik  X , d  dikatakan lengkap jika setiap barisan cauchy pada himpunan X konvergen ke suatu titik pada himpunan X . Definisi 4 [3]. Suatu transformasi w :  2   2 yang berbentuk w  x, y    ax  by  e, cx  dy  f



(2.4)

dengan a, b, c, d , e dan f adalah bilangan riil    disebut transformasi affine pada  2 . w juga dapat juga ditulis dalam bentuk  x  a b  x   e  w           Ax  T  y  c d  y   f 

(2.5)

Definisi 5 [3]. Misalkan f : X  X sebuah transformasi pada himpunan X . Suatu titik x f  X , sedemikian sehingga f x f   x f , disebut titik tetap (fixed point) dari transformasi tersebut. Definisi 6 [3]. Suatu transformasi f : X  X pada ruang metrik  X , d  disebut pemetaan kontraktif jika terdapat suatu konstanta 0  s  1 sedemikian sehingga

d  f  x  , f  y    s.d  x, y  , Konstanta s disebut faktor kontraksi dari f .


x, y  X

(2.6)

17

Teorema 1 (Teorema Transformasi Kontraktif) [3]. Misalkan f : X  X merupakan transformasi kontraktif pada ruang metrik lengkap  X , d  , maka

f memiliki tepat satu titik tetap x f  X sedemikian sehingga f  x f   x f dan untuk sembarang titik x  X , barisan

n

 f  x  : n  1, 2, ... konvergen ke x

atau n

lim f x   x

f

n 





dengan f  n  x   f f  n1  x  dan f 0  x   x . Bukti : Lihat [3] halaman 72.

Transformasi affine kontraktif merupakan transformasi affine yang bersifat kontraktif.


f

18

2.5 RUANG CITRA

Ruang citra merupakan himpunan yang anggotanya adalah citra. Sebagaimana telah dijelaskan sebelumnya bahwa suatu citra haruslah merupakan anggota dari suatu ruang metrik yang lengkap. Oleh karena itu, ruang citra haruslah suatu ruang metrik yang lengkap. Ruang citra dinotasikan dengan   X  . Berikut adalah beberapa definisi dan lema yang berhubungan dengan ruang citra. Definisi 7 [3]. Misalkan S  X merupakan sub himpunan dari ruang metrik

 X , d  . Suatu titik 

 xn n 1

x  X disebut titik limit dari S jika ada sebuah barisan

sedemikian sehingga lim xn  x . n 

Definisi 8 [3]. Misalkan S  X merupakan sub himpunan dari ruang metrik

 X , d  . Closure dari

S , dinotasikan dengan S , didefinisikan sebagai

S  S  titik limit dari S . Definisi 9 [3]. S adalah tertutup jika S mengandung semua titik limitnya, yaitu

S S. Definisi 10 [3]. Misalkan S  X merupakan sub himpunan dari ruang metrik

X, d.

S dikatakan terbatas jika terdapat sebuah titik a  X dan suatu

bilangan R  0 sedemikian sehingga d  a, x   R,


x  X .

19

Lema 1 [2]. Sub himpunan A dari ruang metrik  X , d  kompak jika dan hanya jika A tertutup dan terbatas. Bukti : Lihat [2] halaman 321. Definisi 11 [3]. Misalkan  X , d  adalah ruang metrik lengkap. Maka ruang citra   X  merupakan himpunan yang anggotanya adalah sub himpunan kompak dari X selain himpunan kosong.   X  merupakan himpunan dimana titik-titik pada himpunan   X 

merupakan citra, yang dalam hal ini merupakan sub himpunan yang kompak dari X . Agar   X  merupakan ruang metrik, suatu metrik harus didefinisikan pada   X  . Berikut beberapa definisi yang dibutuhkan untuk mendefinisikan metrik pada himpunan   X  . Definisi 12 [3]. Misalkan  X , d  merupakan ruang metrik lengkap, x  X dan B    X  , definisikan

d  x, B   min d  x, y  | y  B

(2.7)

d  x, B  merupakan jarak dari titik x ke himpunan B .

Definisi 13 [10]. Misalkan  X , d  merupakan ruang metrik lengkap dan A, B    X  , definisikan

d  A, B   max d  x, B  | x  A


(2.8)

20

d  A, B  merupakan jarak antara himpunan A    X  dengan himpunan B  X  . d tidak dapat dijadikan sebagai metrik pada himpunan   X  karena

d  A, B  belum tentu sama dengan d  B, A  . Misalkan A   1, 0   dan B   0, 2   . A dan B merupakan sub himpunan kompak dari ruang metrik

lengkap  , sehingga A, B      . d  A, B   1 , sementara d  B, A   2 , sehingga d tidak dapat dijadikan metrik pada himpunan   X  . Definisi 14 [10]. Misalkan  X , d  merupakan ruang metrik lengkap, maka metrik Haussdorf pada himpunan   X  didefinisikan sebagai: h  A, B   d  A, B   d  B , A 

(2.9)

A, B    X  . d  A, B   d  B, A  menyatakan nilai maksimum dari d  A, B 

dan d  B, A  . Berdasarkan Definisi 14, h  A, B  merupakan maksimum dari jarak A ke B dan jarak B ke A dengan A, B    X  . Lema 2 [10]. h merupakan metrik pada   X  Bukti: Lihat [10] halaman 5. Berdasarkan Lema 2, metrik pada ruang   X  adalah h yang didefinisikan oleh persamaan (2.9).


21

Kelengkapan dari ruang metrik    X  , h  terangkum dalam teorema berikut: Teorema 2 [13]. Misalkan  X , d  merupakan ruang metrik lengkap. Maka

  X , h

merupakan ruang metrik lengkap, dan jika  An    X  | n  1, 2,...

merupakan barisan cauchy di   X  , maka barisan tersebut konvergen ke satu titik tetap A    X  , yaitu

A  lim An    X  n

dimana A dapat ditulis sebagai

A   x  X |  barisan cauchy  xn  An  yang konvergen ke x Bukti: Lihat [13] halaman 19.

2.6 PEMETAAN KONTRAKTIF PADA RUANG CITRA

Setelah mendefinisikan ruang citra, maka harus didefinisikan pemetaan kontraktif pada ruang citra. Sub bab ini menjelaskan tentang definisi dari pemetaan kontraktif pada ruang citra   X  . Berikut adalah beberapa lema yang diperlukan untuk mendefinisikan pemetaan kontraktif pada ruang citra. Lema 3 [3]. Misalkan w : X  X merupakan pemetaan kontraktif pada ruang metrik  X , d  . Maka w kontinyu.


22

Bukti: Lihat [3] halaman 78. Lema 4 [3]. Misalkan w : X  X merupakan pemetaan yang kontinyu pada ruang metrik  X , d  . Maka w memetakan   X  ke   X  . Bukti: Lihat [3] halaman 78. Pemetaan kontraktif pada   X  dapat dibentuk dengan menggunakan pemetaan kontraktif pada X . Hal tersebut dirangkum dalam Lema 5 berikut: Lema 5 [3]. Misalkan w : X  X merupakan pemetaan kontraktif pada ruang metrik  X , d  dengan faktor kontraksi s . Maka w :   X     X  yang didefinisikan oleh

w  B   w  x  | x  B , B    X 

(2.10)

merupakan pemetaan kontraktif pada    X  , h  d   dengan faktor kontraksi

s yaitu; h  w  A  , w  B    s  h  A, B  , A, B    X 

(2.11)

Bukti: Lihat [3] halaman 79. Berdasarkan Lema 5, pemetaan kontraktif pada X juga merupakan pemetaan kontraktif pada   X  . Selain itu, gabungan pemetaan kontraktif pada   X  juga merupakan suatu pemetaan kontraktif pada   X  . Hal tersebut dijelaskan pada lema berikut:


23

Lema 6 [13]. Misalkan  X , d  merupakan ruang metrik lengkap. Misalkan

wn : n  1,

2, ..., N  merupakan himpunan pemetaan kontraktif pada

   X  , h  . Misalkan s

n

merupakan faktor kontraksi untuk wn . Definisikan

W :   X     X  sebagai

W  B   w1  B   w2  B   ...  wN  B  N

  wn  B  , B    X 

(2.12)

n 1

Maka W merupakan pemetaan kontraktif pada   X  dengan faktor kontraksi s  max sn | n  1, 2, ..., N  . Bukti: Lihat [13] halaman 24 Dari penjelasan diatas dapat disimpulkan bahwa pemetaan kontraktif pada ruang citra   X  dibentuk dari pemetaan kontraktif pada ruang metrik X . Selain itu, gabungan dari pemetaan kontraktif pada ruang citra

merupakan pemetaan yang kontraktif pada ruang citra.

2.7 ITERATED FUNCTION SYSTEM (IFS)

Sebagaimana telah disebutkan bahwa prinsip kompresi citra fraktal ialah jika diberikan suatu citra A    X  , maka akan dicari suatu proses W yang merupakan kumpulan pemetaan kontraktif pada   X  sedemikian


24

sehingga A  W  A  dan jika An  W  An 1  maka lim An  A [10]. Berdasarkan n 

Lema 6, W merupakan pemetaan kontraktif pada   X  . Kumpulan dari pemetaan kontraktif W  pada   X  disebut Iterated Function System disingkat IFS. W merupakan pemetaan yang kontraktif pada   X  dan   X 

merupakan ruang metrik lengkap, berdasarkan Teorema 1, W memiliki satu titik tetap A    X  sedemikian sehingga W  A   A dan untuk sembarang B    X  , barisan W  n  B 







n 1

konvergen ke titik tetap A . A disebut juga

attractor dari W . Berikut adalah definisi IFS secara formal: Definisi 15 [3]. Sebuah IFS terdiri atas ruang metrik lengkap

X, d

bersama

dengan himpunan terhingga pemetaan kontraktif wn : X  X dengan faktor kontraksi sn untuk setiap n  1, 2, ..., N . Notasi untuk IFS adalah

 X ; wn ,

n  1, 2, ..., N  dan faktor kontraksinya adalah

s  max sn | n  1, 2, ..., N  . Berikut adalah teorema yang berhubungan dengan IFS: Teorema 3 (Teorema IFS) [13]. Misalkan  X ; wn ,

n  1, 2, ..., N  merupakan

sebuah IFS dengan faktor kontraksi s . Maka transformasi W :   X     X  yang didefinisikan oleh


25

N

W  B    wn  B 

(2.13)

n 1

untuk setiap B    X  , merupakan pemetaan kontraktif pada ruang metrik

   X  , h  d  dengan faktor kontraksi s sehingga

h W  B  , W  C    s.h  B, C 

(2.14)

untuk setiap B, C    X  . Transformasi tersebut mempunyai titik tetap, A    X  yang memenuhi N

A  W  A   wn  A 

(2.15)

n 1

dan A  lim W  n  B  untuk setiap B    X  . n

Bukti: Lihat [13] halaman 26.

2.8 MODEL MATEMATIS DARI CITRA

Secara matematis, citra dimodelkan sebagai suatu fungsi f :  2  I , dengan I adalah skala keabuan citra dan I =  0, 255 . Setiap pixel  x, y    2 memiliki nilai intensitas pixel f  x, y  [5] [6]. Metrik   f , g  antara dua citra f , g : A  I , dengan A   2 , didefinisikan sebagai berikut [6]:


26

  f , g   sup f  x, y   g  x, y 

(2.3)

 x , y  A

Berdasarkan definisi   f , g  , metrik antara citra f dan citra g merupakan perbedaan intensitas pixel terbesar pada pixel  x, y  .

2.9 ALGORITMA GENETIKA

Algoritma genetika merupakan algoritma pencarian berdasarkan mekanisme seleksi alamiah dan genetika alamiah. Algoritma genetika diperkenalkan pertama kali oleh John Holland pada tahun 1960-an. Kini algoritma genetika telah dipelajari, diteliti dan diaplikasikan secara luas pada berbagai bidang [14]. Algoritma genetika banyak digunakan untuk mencari solusi dari suatu permasalahan yang memiliki ruang solusi cukup luas [14]. Setiap solusi yang mungkin bagi permasalahan tersebut dimodelkan sebagai sebuah kromosom. Dalam satu waktu, kromosom-kromosom membentuk satu populasi. Kromosom terdiri atas beberapa informasi dengan spesifikasi informasi tergantung pada permasalahan yang akan diselesaikan. Algoritma genetika dapat digunakan untuk mencari solusi yang optimal dari suatu masalah. Pada algoritma genetika, pencarian solusi yang optimal dimulai dengan inisialisasi beberapa kromosom yang mungkin secara acak.


27

Setiap kromosom diberikan nilai fitness. Nilai fitness merupakan ukuran yang digunakan untuk menilai baik atau tidak suatu kromosom untuk tetap tinggal dalam suatu populasi. Semakin tinggi nilai fitness kromosom, maka kemungkinan kromosom tetap tinggal dalam populasi akan semakin besar. Semakin tinggi nilai fitness juga berarti semakin baik kromosom digunakan sebagai solusi terhadap masalah yang ingin diselesaikan. Beberapa kromosom yang memiliki nilai fitness paling tinggi dipilih dan kemudian dilakukan proses pindah silang (crossover). Dari proses tersebut diperoleh kromosom anak (offspring) yang memiliki informasi hasil persilangan informasi orangtuanya. Proses mutasi dilakukan terhadap beberapa kromosom dengan menukarkan informasi dari dari suatu kromosom secara acak. Pindah silang dan mutasi dilakukan dengan harapan terbentuk kromosom baru dengan nilai fitness yang lebih tinggi dari nilai fitness orangtuanya. Algoritma genetika standar terdiri atas beberapa komponen berikut : 1.

Kromosom Kromosom merupakan representasi solusi yang mungkin dari

masalah. Solusi-solusi yang mungkin akan dikodekan menjadi kromosomkromosom. 2.

Nilai Fitness Nilai fitness merupakan nilai yang diberikan kepada setiap kromosom

dalam satu populasi yang menunjukan seberapa baik kromosom tersebut untuk tetap tinggal dalam populasi. Implikasi dari hal tersebut adalah


28

kromosom dengan nilai fitness lebih tinggi merupakan solusi yang lebih baik daripada kromosom dengan nilai fitness lebih rendah. 3.

Seleksi Orangtua Sebelum melakukan pindah silang dan mutasi, harus dilakukan proses

pemilihan (seleksi) orangtua. Pindah silang dan mutasi dilakukan terhadap kromosom yang terpilih. Seleksi orangtua dalam satu populasi terkait dengan nilai fitness kromosom. Semakin tinggi nilai fitness, maka peluang untuk terpilih semakin besar. Metode yang umum digunakan sebagai metode seleksi orangtua adalah metode roda roulete (roulette-wheel). Roda roulete digambarkan sebagai papan berbentuk lingkaran dengan beberapa juring. Banyak juring yang terbentuk sesuai dengan jumlah kromosom dalam populasi. Besarnya ukuran juring tidaklah sama, akan tetapi dibuat proporsional dengan nilai fitness masing-masing kromosom. Roda roulete ini kemudian diputar dan diberi sebuah jarum penanda di bagian bawah atau atasnya sebagai penentu bagian yang terpilih. Bagian juring yang ditunjuk oleh jarum tersebut -ketika roda roulete berhenti- adalah bagian yang terpilih dan kromosom yang direpresentasikan oleh bagian tersebut adalah kromosom yang terpilih. Sebagai contoh: dalam satu populasi terdapat 4 buah kromosom, yaitu A, B, C, dan D dengan nilai fitness berturut-turut adalah 3, 5, 1, 1. Jumlah dari seluruh nilai fitness adalah 10. Aturan pembagian luas juring adalah


29

 3  5 sebagai berikut; A sebesar    100%  30% , B sebesar    100%  50% ,  10   10  1 C dan D masing-masing sebesar    100%  10% . Berikut adalah tabel nilai  10  fitness dari keempat kromosom tersebut. Tabel 1. Nilai fitness Kromosom A B C D Jumlah

Fitness 3 5 1 1 10

Berdasarkan nilai fitness pada Tabel 1, maka skema pembagian roda roulete adalah sebagai berikut:

10 %

30 % C

10 %

A

D

50 % B

Gambar 10. Roda roulete

4.

Pindah Silang (crossover) Pindah silang merupakan proses penurunan sifat dari dua kromosom

orangtua menjadi kromosom anak. Proses pindah silang akan menghasilkan dua kromosom anak. Sifat dari kromosom anak hasil pindah silang


30

merupakan persilangan sifat kedua orangtuanya. Terjadinya proses pindah silang dalam suatu populasi ditentukan oleh probabilitas pindah silang. Skema pindah silang yang digunakan tergantung pada masalah yang akan diselesaikan. Skema pindah silang tertentu mungkin cocok untuk masalah A, tapi tidak cocok untuk masalah B, begitu juga sebaliknya [14]. 5.

Mutasi Mutasi merupakan proses perubahan informasi kromosom. Terjadinya

mutasi kromosom ditentukan oleh probabilitas mutasi. Kromosom hasil pindah silang dan mutasi dihitung nilai fitness-nya. Beberapa kromosom dengan nilai fitness terbaik menggantikan kromosom dengan nilai fitness rendah sehingga diperoleh populasi baru.


31

Berikut adalah pseucode dari algoritma genetika [15]: Algoritma Genetika 1

P  Inisialisasi populasi (N buah kromosom)

2

for setiap kromosom

3

while (kriteria berhenti belum tercapai) and

 pi  P

N i 1

evaluasi fitness pi

(generasi terakhir belum tercapai) 4

generate populasi baru menggunakan operator seleksi, pindah silang, mutasi

5

Evaluasi nilai fitness kromosom pada populasi baru

6 7

Ganti kromosom lama dengan kromosom terbaik end while

2.10 KRITERIA KOMPRESI

Kriteria kompresi merupakan suatu ukuran yang digunakan untuk menilai baik atau buruk suatu metode kompresi. Suatu metode kompresi dinilai dari 2 kriteria: pertama, kualitas citra hasil kompresi (PSNR) dan kedua, rasio kompresi yang dicapai. Metrik yang digunakan dalam aplikasi untuk mengukur perbedaan antara dua citra adalah metrik rms. Perbedaan antara dua citra z dan z ' yang


32

masing-masing berdimensi n  n diukur menggunakan persamaan berikut [6] [9] [12] :

rms 

1 n

n

n

  z '

ij

 zij 

2

(2.16)

i 1 j 1

dengan zij , z 'ij berturut-turut menyatakan nilai intensitas pixel  i, j  pada citra asli z dan citra hasil dekompresi z ' . Berikut adalah dua kriteria kompresi: 1. Kualitas Citra (PSNR) Kualitas citra hasil dekompresi diukur menggunakan Peak signal-tonoise ratio (PSNR) [12] [6], yaitu

 b  PSNR  20  log10    rms 

(2.17)

dengan b adalah nilai intensitas pixel terbesar. Semakin besar nilai PSNR , maka kualitas citra hasil dekompresi semakin baik. Satuan untuk PSNR adalah db (desibel). 2. Rasio Kompresi Rasio kompresi yang dicapai, diukur menggunakan persamaan berikut [12]:

 ukuran citra hasil kompresi  rasio  100%     100% ukuran citra asli  

(2.18)

Ukuran citra menyatakan besar penggunaan memori untuk menyimpan citra. Semakin tinggi rasio yang dicapai, maka metode kompresi semakin baik.


BAB II LANDASAN TEORI. berawal dari suatu ide untuk menyimpan segitiga Sierpinski menggunakan

Recommend Documents