BAB II LANDASAN TEORI

BAB II LANDASAN TEORI

Bab ini akan menjelaskan mengenai landasan teori yang dipakai oleh penulis dalam penelitian ini. Bab ini dibagi menjadi beberapa bagian, yang masing masing akan menjelaskan Principal Component Analysis (PCA), Eigenface, Klustering K-Means, Koreksi Gamma, dan Jarak Euclidean.

2.1 Principal Component Analysis Principal Component Analysis digunakan untuk mengurangi besarnya dimensi dari data yang diobservasi, menjadi dimensi yang lebih kecil tanpa kehilangan informasi yang signifikan dalam menggambarkan keseluruhan data [7]. PCA akan digunakan pada fase terakhir eigenface, untuk mencari bagian terpenting pada eigenvector. Sebelum itu akan dijelaskan konsep-konsep dasar yang digunakan pada PCA. 2.1.1 Standar Deviasi Standar deviasi dari sebuah himpunan data adalah ukuran seberapa tersebarnya nilai data-data tersebut. Sebagai contoh, jika kita memiliki dua himpunan data masingmasing [2 9 15 35] dan [0 2 3 5], maka standar deviasi dari himpunan pertama akan lebih besar dari yang kedua. Hal tersebut ditunjukkan oleh rumusan dari standar deviasi sebagai berikut[7],

 X n

s

i 1

i

X



2

(2.1)

n

Dari rumus diatas, s merupakan standar deviasi, X adalah sebuah himpunan data, dan X adalah rata-rata dari X. X ditunjukkan oleh rumus berikut [7].

18 Perbandingan eigenface dan klustering..., M. Faizal Reza, FASILKOM UI, 2008

(2.2)

Dengan menggunakan rumus (2.1), maka himpunan data [2 9 15 35] akan memiliki nilai standar deviasi 14.198 dan himpunan [0 2 3 5] akan memiliki nilai standar deviasi 2.0816. Nilai standar deviasi yang menunjukkan bahwa nilai data-data yang ada pada himpunan tersebut tersebar jauh dari nilai rata-rata himpunan tersebut. Sedangkan nilai standar deviasi yang kecil menunjukkan bahwa nilai data-data yang ada di dalam sebuah himpunan berkumpul di sekitar rata-rata nilai himpunan tersebut.

2.1.2 Varian Varian meruoakan cara lain untuk mengukur tersebarnya data-data yang ada dalam sebuah himpunan. Faktanya, varian adalah kuadrat dari standar deviasi. Rumus dari varian adalah sebagai berikut, (2.3) s2 merupakan varian dari sebuah himpunan data. 2.1.3 Kovarian Dalam teori probabilitas dan statistik, kovarian merupakan ukuran seberapa kuat hubungan antara dua variabel[10]. Jika kedua variabel berada pada nilai yang diharapkan, maka kovarian antara dua variabel ini akan bernilai positif. Sebaliknya, jika salah satu variabel berada di atas nilai yang diharapkan dan variabel yang lain berada di bawah nilai yang diharapkan, maka kovarian diantara dua variabel ini akan bernilai negatif. Dua buah variabel dikatakan independen jika tidak ada hubungan antara kedua variabel tersebut. Dengan kata lain, meskipun diketahui nilai salah satu variabel, maka tidak dapat ditentukan variabel yang lain[10].


Kovarian selalu diukur antar dua dimensi. Jika kita memiliki himpunan data yan berdimensi tiga (x, y, z), maka kita dapat menghitung kovarian antara dimensi x dan y, antara dimensi x dan z, dan antara dimensi y dan z. Melakukan penghitungan kovarian antara x dan x, y dan y, dan z dan z masing-masing akan memberikan nilai varian dari x, y, dan z. Rumus kovarian diberikan sebagai berikut,

 X cov X , Y   n

i 1

i



 X Yi  Y



n  1

(2.4)

2.1.4 Vektor Eigen atau Nilai Eigen Jika A adalah suatu matriks persegi berdimensi m x n dalam ruang Cn, serta x dan b adalah suatu vektor berdimensi n x 1, dan terdapat persamaan linear Ax  b

(2.5)

Maka maksudnya adalah transformasi dilakukan oleh matriks A terhadap vektor x ke suatu vektor baru b [8, 9]. Ilustrasi dari transformasi yang dilakukan oleh matriks A terhadap vektor x dapat dilihat pada Gambar 2.1. Vektor eigen dari A adalah suatu vektor tak nol v ε Cn, dan didefinisikan sebagai berikut,

Av  v

(2.6)

dimana λ adalah suatu skalar yang biasa disebut sebagai nilai eigen dari A, dan A merupakan perkalian skalar dari v. Transformasi dilakukan oleh matriks A terhadap vektor v dari ruang Cn ke ruang Cn hanya akan merubah panjang dari vektor v sesuai nilai eigen λ. Gambar 2.1menggambarkan transformasi yang dilakukan oleh matriks A terhadap vektor eigen v.


Gambar 2.1 Transformasi matriks A terhadap vektor x

Gambar 2.2 Transformasi matriks A terhadap vektor eigen v

Beberapa properti yang berguna dalam proses penghitungan nilai eigen λ dari matriks A adalah sebagai berikut [9]:

1. Av  v, untuk v  0 2. ( A  I )v  0 mempunyai x  v sebagai solusi nontrivial 3. A  I tidak saling invertibel 4. det( A  I )  0 2.1.6 Principal Component Transformasi yang dilakukan sangat dipengaruhi oleh besarnya nilai eigen yang dimiliki oleh vektor eigen. Oleh karena itu, mereduksi dimensi dengan cara membuang vektor-vektor eigen dengan nilai eigen yang sangat kecil tidak akan membuat kita


kehilangan data yang penting. Vektor-vektor eigen dengan nilai eigen yang terbesar disebut sebagai principal component dari sebuah matriks. Cara untuk mendapatkan principal component dari sebuah matriks dilakukan dalam beberapa langkah [7], 1. Mengurangi setiap nilai dari matriks dengan rata-rata nilai dari setiap masingmasing dimensi. 2. Menghitung matriks kovariannya 3. Mencari vektor eigen dan nilai eigen dari matriks kovarian tersebut. 4. Kemudian vektor eigen yang ada diurutkan berdasarkan nilai eigen-nya dari yang paling besar ke yang paling kecil. 5. Dengan memilih vektor-vektor eigen yang memiliki nilai-nilai eigen terbesar maka kita telah mendapatkan principal component dari matriks awal dan kita dapat membentuk feature vector. Feature vector berguna untuk mendapatkan data-data dari matriks awal yang bersesuaian dengan vektor eigen yang telah kita pilih dengan cara mengalikan transpose dari feature vector dengan transpose dari matriks yang datanya sudah dikurangi dengan nilai rata-rata.

2.2 Eigenface Eigenface adalah metode yang dikembangkan oleh Pentland dan Turk pada tahun 1991[4, 5]. Menurut mereka, dalam bahasa teori informasi metode ini adalah mengekstrak informasi dari citra wajah yang relevan, meng-encodenya seefisien mungkin dan membandingkannya dengan citra wajah yang lain yang telah di encode dengan metode yang sama[5].


Eigenface memecah citra wajah menjadi bagian kecil yang menjadi karakter fitur dari citra yang disebut face space, yaitu bagian penting dari citra wajah yang bisa mewakili ciri-cirinya [5]. Hal ini bisa dilakukan dengan metode matematika yang disebut Principal Component Analysis (PCA), yang telah dijelaskan pada bagian 2.1. Dalam melakukan penghitungan eigenface dengan PCA ini, ada beberapa langkah yang harus dilakukan [11]. 1. Mempersiapkan data citra wajah Dalam tahap ini, data citra wajah pelatihan ( 1 ) dipersiapkan terlebih dahulu untuk dilakukan proses perhitungan eigenface, biasanya data citra wajah pelatihan ini dibuat menjadi bentuk vektor. 2. Mencari selisih antara data citra wajah pelatihan dengan matriks rata-rata Kita hitung matriks rata-rata Ψ, dan kemudian kurangi data citra wajah pelatihan i dengan matriks rata-rata. Misalkan banyaknya data citra wajah pelatihan adalah M,



1 M



M

 n 1 i

(2.7) (2.8)

 i  i   3. Menghitung matriks kovarian Langkah selanjutnya menghitung matriks kovarian C berdasarkan,

C

1 M



M

n 1

T

 n

n

(2.9)

4. Menghitung vektor eigen dan nilai eigen dari matriks kovarian Pada langkah ini, temukan vektor eigen µi dari matriks kovarian C yang diurutkan berdasarkan nilai eigen-nya λi. Nilai eigen-nya diurutkan dari yang terbesar ke yang terkecil.


5. Memilih principal component Dari M vektor eigen (eigenface) µi, hanya M’ vektor yang perlu dipilih. Vektor yang dipilih adalah vektor yang memiliki nilai eigen yang paling besar. Semakin besar nilai eigen-nya, maka semakin besar karakteristik fitur dari citra wajah yang digambarkan oleh vektor eigen yang bersesuaian dengan nilai eigennya. Eigenface dengan nilai eigen yang rendah dapat dihilangkan, untuk mengurangi biaya komputasi.

2.3 Klustering K-Means Klustering K-Means adalah metode yang digunakan untuk membagi data menjadi beberapa kluster (sub-kelompok) berdasarkan hasil pekerjaan dari Lloyd pada tahun 1982[12]. Jika diketahui X adalah himpunan dari sekelompok data dan k adalah jumlah titik berat dari k kluster, maka K-Means membagi data menjadi k kluster dengan k titik berat[13]. Algoritma ini memiliki proses pekerjaan sebagai berikut[14], 1. Klustering dilakukan dengan membuat titik berat 3 buah secara acak, yang dipilih dari 3 buah anggota vektor. 2. Dihitung jarak euclidean-nya (dijelaskan pada bagian 2.5) dengan anggota vektor yang lain. Sebuah titik anggota vektor dikatakan anggota dari sebuah kluster, jika jarak euclidean antara titik tersebut dengan titik berat dari ke-3 kluster, paling kecil jika dibandingkan dengan jaraknya dengan titik berat kluster lain. 3. Setelah diketahui pembagian klasternya, maka akan didapat titik berat baru dari tiap kluster. 4. Ulangi lagi proses (dari b) hingga pembagian kluster tidak berubah-ubah.


2.4 Koreksi Gamma Sebelum menjelaskan koreksi Gamma, penulis akan mengenai konsep Transformasi Power-Law. 2.4.1 Transformasi Power-Law Transformasi Power-Law adalah salah satu dari metode yang paling sederhana dari teknik peningkatan kualitas citra (image enhancement)[15]. Metode ini dioperasikan pada citra dalam level grayscale. Metode ini memiliki bentuk dasar,

s  cr

(2.10)

Dari rumus diatas, s adalah nilai piksel dalam grayscale setelah transformasi, dan r adalah nilai piksel sebelum transformasi, juga dalam grayscale. Sedangkan c dan γ (Gamma) adalah konstanta positif. 2.4.2 Koreksi Gamma Koreksi Gamma adalah perubahan nilai Gamma untuk memperbaiki fenomena respon dari transformasi power-law[15]. Sehingga bisa memperbaiki kualitas citra sesuai yang diinginkan. Sesuai dengan persamaan 2.10, jika γ > 1, maka perubahan citra akan menjadi semakin gelap. Sedangkan jika γ < 1, maka perubahan piksel pada citra akan menjadi semakin terang.

2.5 Jarak Euclidean Jarak Euclidean adalah jarak antara dua titik yang diukur dengan menarik garis lurus antara dua titik tersebut. Metode penghitungan jarak euclidean ini digunakan dalam metode Klustering K-Means untuk menghitung jarak antara titik berat / centroid. Selain itu, metode ini juga digunakan dalam proses pengukuran kemiripan suatu citra alis dengan citra yang lain.


Suatu citra dapat direpresentasikan sebagai suatu titik pada ruang berdimensi M. Dalam pengukuran kemiripan antar citra tersebut, cukup dihitung jarak antara dua buah titik yang merupakan representasi dari dua buah citra tersebut. Semakin kecil jarak antara dua buah citra wajah, semakin tinggi nilai kemiripan antara kedua citra wajah tersebut [4]. Hal ini juga bisa dilakukan dalam penghitungan kemiripan citra alis. Sehingga dalam penghitungan jarak euclidean tiga buah citra alis, p, q, dan r. Dimana kemiripan antara p dan q adalah D(p,q), dan kemiripan antara p dan r adalah D(p,r). Citra alis p dikatakan lebih mirip dengan q jika D(p,q) < D (p,r), dan sebaliknya citra alis p dikatakan lebih mirip r jika D(p,r) < D (p,q). Prinsip Jarak Euclidean Dalam ruang euclidean berdimensi n, Rn, jarak antara titik x dan titik y dirumuskan dengan persamaan berikut[16, 17].

D ( p, q ) | x  y |



n i 1

| xi  yi |2

(2.11)

Maka untuk mengukur jarak euclidean antara p(x1) dan q(x2) di ruang berdimensi satu (R1) bisa didapatkan dengan. D( p, q) 

x1  x2 2

| x1  x2 |

(2.12)

Untuk mendapatkan jarak euclidean antara p(x1 , y1) dan q(x2, y2) di ruang berdimensi dua (R2) dapat dilakukan dengan menggunakan persamaan berikut. D( p, q) 

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

(2.13)

Untuk mendapatkan jarak euclidean antara p(x1,y1,z1) dan q (x2,y2,z2) di ruang berdimensi tiga (R3) dapat dilakukan dengan persamaan berikut. D( p , q ) 

 x1  x2 2   y1  y2 2  z1  z2 2


(2.14)

Sedangkan untuk mendapatkan jarak euclidean di ruang berdimensi n (Rn), dimana terdapat vektor p(x1, x2, x3, ..., xn) dan vektor q(y1, y2, y3, ..., yn), dapat dihitung dengan persamaan berikut. D( p , q ) 

x1  y1 2  x2  y2 2  ...  xn  yn 2

(2.15)

Jika kedua titik p dan q berada pada koordinat polar p (r1,  1) dan q (r2,  2), maka jarak euclidean dapat dihitung dengan persamaan berikut.

D( p, q )  r12  r2 2  r1r2 cos1   2 


(2.16)

BAB II LANDASAN TEORI

Recommend Documents