Pengenalan Wajah dengan Metode Subspace LDA (Linear Discriminant Analysis) Ratna Nur Azizah Jurusan Teknik Elektro – FTI, Institut Teknologi Sepuluh Nopember Kampus ITS, Keputih-Sukolilo, Surabaya-60111 Abstract – Pengenalan wajah merupakan salah satu pengolahan citra yang telah berhasil dan telah diaplikasikan dalam berbagai bidang baik yang bersifat komersial maupun digunakan untuk kepentingan pemerintahan. Teknologi pengenalan wajah juga semakin banyak diaplikasikan dalam sistem pengenalan biometrik, pencarian dan pengindeksan database citra. Tugas akhir ini bertujuan untuk merealisasikan metode gabungan PCA dan LDA (Subspace LDA) untuk pengenalan wajah dengan perangkat lunak MATLAB. Pengenalan wajah menggunakan metode subspace LDA merupakan metode pengenalan wajah dengan 2 metode ekstraksi fitur statistic yaitu PCA (Principal Components Analysis) dan LDA (Linear Discriminant Analysis) dimana citra wajah diproyeksikan ke ruang eigenface yang diperoleh dari proses PCA dan hasil proyeksinya kemudian diproyeksikan lagi menuju ruang klasifikasi LDA sehingga dihasilkan suatu classifier linier. Algoritma Subspace LDA diuji dengan berbagai citra yang memiliki variasi cahaya (database YaleB) dan variasi headpose (database att_face) dengan pemilihan eigenfacce yang berbeda. Citra wajah yang digunakan adalah citra grayscale dengan dimensi 128 x 112 yang telah mengalami normalisasi serta croping. Sehingga citra wajah hanya menampilkan wajah orang tanpa latar belakang. Hasil yang diperoleh menunjukkan jika jumlah eigenface yang digunakan antara 20% sampai 80% akan menghasilakn persentase pengenalan tinggi. Kata kunci: Pengenalan Wajah, PCA, LDA I. PENDAHULUAN Algoritma pengenalan wajah dapat dibedakan menjadi 2 bagian yaitu berdasarkan pendekatan fitur (feature-based) dan pendekatan penampilan (appearance-based)[1]. Pendekatan fitur menggunakan suatu landmark atau marker (penanda) yang diletakkan pada ujung mata, bagian bawah mulut, alis, dagu, ujung hidung dan beberapa lokasi lain pada wajah. Dari marker-marker tersebut kemudian ditentukan sudut dan atau jarak antar marker tersebut sehingga dapat digunakan sebagai fitur yang diperlukan untuk pengenalan wajah. kelemahan pendekatan fitur ini adalah sulitnya menentukan posisi marker yang tepat karena adanya variasi pencahayaan dan ekspresi wajah.
Pendekatan kedua yaitu appearance-based dikenal juga dengan metoda eigenface. Pada metoda ini setiap citra wajah dianggap sebagai suatu vektor tunggal dengan cara menderetkan kolom-kolom pada citra wajah menjadi satu vektor yang panjang, yang nantinya akan di representasikan sebagai satu titik pada dimensi tinggi. Karena fitur yang akan dihasilkan terletak dalam dimensi tinggi maka perlu dilakukan reduksi dimensi. Ada dua metoda yang digunakan untuk mengurangi dimensi-dimensi fitur yaitu, Principal Component Analysis (PCA) [2] dan Linear Discriminant Analysis (LDA)[3][4]. Dengan mengunakan metode Subspace LDA yang merupakan metoda gabungan PCA dan LDA diharapkan akan menghasilkan reduksi dimensi yang optimal. Metoda ini terdiri dari dua tahap yaitu citra wajah diproyeksikan ke ruang eigenface yang telah dibentuk oleh PCA dan kemudian vektor-vektor yang telah terproyeksi tadi diproyeksikan menuju ruang klasifikasi LDA untuk membentuk suatu classifier linier. Pada metoda ini pemilihan jumlah eigenface yang digunakan pada tahap pertama adalah sangat kritis. Pemilihan jumlah eigenface ini akan memungkinkan sistem untuk menghasilkan fitur-fitur yang berasal dari representasi ruang eigenface yang dapat dipisah berdasarkan kelas-kelas melalui metoda LDA. II. TEORI PENUNJANG 2.1
Principal Components Analysis (PCA) Principal Component Analysis (PCA) adalah teknik reduksi dimensi yang umum digunakan pada aplikasi pemrosesan citra. Prinsip dasar dari algoritma PCA adalah menentukan komponen-komponen atau dimensi-dimensi dari semua citra mempunyai distribusi energi maksimal pada komponen-komponen tersebut. Maka dimensi-dimensi yang berkontribusi tersebutlah yang dipertahankan untuk tahap pemrosesan selanjutnya dan sisanya disingkirkan [3][5]. 2.2
Linear Discriminant Analysis (LDA) LDA bekerja berdasarkan analisa matrik penyebaran (scatter matrix analysis) yang bertujuan menemukan suatu proyeksi optimal sehingga dapat memproyeksikan data input pada ruang dengan dimensi yang lebih kecil dimana semua pola (pattern) dapat dipisahkan semaksimal mungkin. Karenanya untuk tujuan pemisahan tersebut maka LDA akan mencoba untuk memaksimalkan penyebaran data-data input diantara kelas-kelas yang berbeda dan sekaligus
Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI-ITS
1
juga meminimalkan penyebaran input pada kelas yang sama. Perbedaan antar kelas direpresentasikan oleh matriks Sb (scatter between class) dan perbedaan dalam kelas direpresentasikan oleh matriks Sw (scatter within class). Implementasi Subspace LDA Didefinisikan suatu matrik citra I dengan ukuran (Nx x Ny) dikonversikan menjadi matrik citra satu kolom ( ) dengan ukuran (N x 1) dimana N = (Nx x Ny). [4][6]
dari matrik (P x P) dapat diperoleh melalui eigenvector matrix (N x N) [pakhendra PCA]. Dalam penjelasan secara matematisnya, didefinisikan suatu matrik Y dengan ukuran (Mt x Mt) , yaitu [6]:
2.3
Citra I : (Nx x Ny) piksel
(1)
Training Set merupakan satu set vektor-vektor citra yang berukuran (N x P) dimana P adalah jumlah dari citra-citra training [4][9]. Citra training ini kemudian dijadikan suatu database citra wajah. Training Set
=[ ,
,…,
]
(3)
Mean subtracted image merupakan pengurangan citra training dari mean face. Mean subtracted image merupakan matrik yang berukuran (N x P) [4][6]. Mean subtracted image Φ =
−T
(4)
. Difference Matrix merupakan matrik yang berasal dari semua vektor citra training yang sudah dikurangi dengan mean dan berukuran (NxP) [4][6]. = [Φ , Φ , … , Φ ]
Difference Matrix
=
×
=
1
Φ. Φ
(5)
(6)
merupakan matrik covariance dari vektorvektor citra training dan berukuran (NxN) sehingga sangat sulit untuk dikerjakan karena ukurannya yang sangat besar (computational complexity). Sehingga pada metode eigenface, perhitungan eigenvector tidak diperoleh secara langsung dari matrik (N x N) melainkan melalui matrik (P x P), dimana P merupakan jumlah dari citra-citra wajah. Eigenvector
1 P T P i 1 i i
Ditentukan suatu eigenvector matrik Y [6], Y.
=
dan eigenvalue
.
(7)
dari
(8)
Konstanta Y dari persamaan diatas kemudian diganti dengan AT . A [6], AT . A .
(2)
Mean Face adalah rata-rata aritmetika dari vektorvektor citra training pada setiap titik piksel yang berukuran (N x 1) [4][6].
1 P Mean Face T Ti P i 1
Y = AT . A
= .
(9)
Kedua sisi dari persamaan diatas dikalikan dengan A [6] : (10) A . AT . A . = A . . Kemudian dengan mengatur urutan matrik, diperoleh [6] : (11) A . AT . A . = . A . Pengaturan susunan diatas dapat terjadi karena merupakan bentuk skalar. Serta dengan X = A . AT , maka [6]: (12) X. A . = . A . Dan dengan mengganti A . menjadi υi , maka [9] : (13) υi = A . Dimana υi = A . merupakan eigenvector dari L = A . AT dengan ukuran matriknya adalah (N x 1). Terlihat bahwa dengan cara di atas eigenvector dari L dapat diperoleh melalui eigenvector dari Y, dimana dibandingkan dengan menggunakan matrik dengan ukuran besar (N x N) lebih sederhana jika digunakan matrik berukuran (P x P). Cara formulasi ini memberikan efisiensi komputasi yang sangat besar. Setelah didapatkan eigenvektor dari matrik covariance, υi , vektor-vektor citra-citra training diproyeksikan pada ruang eigenface sehingga bobot (weight) dari setiap eigenvektor untuk mewakili citra pada ruang eigenface harus ditentukan. Bobot ini secara sederhana merupakan dot product dari setiap citra dengan setiap eigenvector.
Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI-ITS
=
.Φ =
( − )
(14)
2
merupakan proyeksi suatu citra training pada setiap eigenvector dimana k=1,2,3,...M’ dan Matrik Bobot (weight matrix) dapat dihitung dengan persamaan (15). Martik bobot merupakan representasi dari citra training pada ruang eigenface dan berukuran (M’ x 1) Ω=[
,
,…,
′]
(15)
Dengan melakukan semua perhitungan di atas, citra-citra training diproyeksikan pada ruang eigenface. Ini merupakan suatu transformasi dari ruang dimensi P menuju ruang dimensi M’. Teknik PCA ini dilakukan untuk mengurangi dimensi data sekaligus sebagai ekstraksi fitur. Setelah langkah ini maka setiap citra merupakan suatu vektor berdimensi (M′ x 1) pada ruang eigenface. Data terproyeksi ini akan ditransformasikan lagi oleh suatu transformator baru yaitu LDA ke ruang proyeksi klasifikasi. Metoda subspace LDA ini tidak menggunakan harga-harga piksel dari citra seperti pada metoda LDA namun menggunakan proyeksi eigenface. Didefinisikan suatu discriminatory power seperti pada metoda LDA sebagai[6]:
dihitung dari rata-rata aritmetika dari semua vektorvektor citra training yang terproyeksi, (19) 1 = Ω Rata-rata penyebaran (average scatter) dihitung sebagai, (20) ∑ = [(Ω − ). (Ω − ) ] Sedangkan matrik penyebaran antar kelas (between class scatter matrix) dihitung sebagai, (21) =
( )(
. .
. .
| |
(17) ( )∑
dimana mewakili average scatter Σi dari proyeksi Ω pada ruang eigenface dari Ci individu yang berbeda dengan mean . Ukuran dari Sw tergantung pada ukuran ruang eigenface, yaitu jika digunakan M’ eigenface maka ukuran dari Sw adalah (M′ x M′). Mean dari kelas pada ruang eigenspace (Eigenface Class Mean) ( ) yang merupakan rata-rata aritmaika dari eigenvector citra training yang terproyeksi pada ruang eigenspace didefinisikan sebagai,
=
1
−
)
Dengan asumsi bahwa setiap kelas mempunyai prior probability yang sama. Tujuan dari metode subspace LDA adalah memaksimumkan ( ), yaitu menentukan proyeksi optimal yang akan memaksimumkan between class scatter dan meminimumkan within class scatter. max ( )
(23)
(16)
Dimana Sb adalah matrik penyebaran antar kelas (between-class scatter) dan Sw adalah matrik penyebaran dalam kelas (within-class scatter). Untuk c individu yang memiliki citra training sebanyak pada data base maka within class scatter matrix dihitung sebagai [6] =
)(
( ) adalah prior class probability yaitu, 1 (22) ( )=
dimana
= | ( )= |
−
W kemudian dapat diperoleh dengan menyelesaikan permasalahan umum eigenvalue =
Langkah berikutnya adalah memproyeksikan vektor-vektor citra training yang sudah terproyeksi pada eigenface ke ruang klasifikasi dengan cara melakukan dot product antara proyeksi optimal dan vektor bobot. (Ω ) = (25) Ω Classification Space Projection (Ω ) adalah proyeksi dari vektor-vektor citra training terproyeksi pada eigenface ke ruang klasifikasi yang berukuran ((c-1) x 1) dimana i = 1, 2, …., P. Pada saat ini tahap training telah berakhir. Perlakuan yang sama juga dilakukan pada citra tes. Dan akhirnya, jarak antar proyeksi-proyeksi ditentukan oleh jarak Euclidean antara citra training dan test pada ruang proyeksi klasifikasi[6]. (26)
(18) =
Ω
dimana i = 1, 2, 3, ... , c dan ukuran dari Eigenface Class Mean adalah (M’ x 1). Sedangkan mean face
(24)
(
(Ω ) −
(Ω ))
adalah ukuran jarak yang merupakan besaran skalar dan dihitung untuk i = 1,2, ... , P.
Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI-ITS
3
III. DESKRIPSI SISTEM Blok diagram sistem pengenalan wajah dapat dilihat pada Gambar 1. Dalam simulasi percobaan ini digunakan database wajah Yale Face B dan att_face dimana format setiap citra wajah adalah grayscale. Database wajah Yale Face B berukuran 192 X 168 pixel dan att_face berukuran 112 X 92 pixel. Pada proses selanjutnya ukuran citra diseragamkan menjadi 128 X 112 pixel. Pemrosesan awal yang dilakukan adalah setiap citra wajah di-crop sedemikian sehingga citra didominasi total wajah dan tidak terdapat latar belakang. Gambar 2 dan Gambar 3 merupakan diagram alir dari proyeksi PCA dan proyeksi LDA
C Sb * Sw1 [1 , 2 ,..., M ' ]T
1 i qi
qi
k
k 1
Gambar 3 Diagram Alir Proses Training PCA
Gambar 1 Blok Diagram Sistem Pengenalan Wajah (a)
(b) Gambar 4 Sepuluh eigenface pertama (a) dari 30 kelas variasi pencahayaan (b) dari 30 kelas variasi headpose
(a) Gambar 2 Diagram Alir Proses Training PCA
(b) Gambar 5 Sepuluh fisherface pertama (a) dari 30 kelas variasi pencahayaan (b) dari 30 kelas variasi headpose
Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI-ITS
4
Gambar 6 Contoh citra wajah database YaleB
Gambar 7 Citra wajah database att_face Dari proses Proyeksi PCA diperoleh eigenface yang merupakan fitur yang nantinya akan dijadikan masukan pada proses LDA yang menghasilkan fisherface. Fisherface merupakan eigenface yang telah terproyeksi ke dimensi yang lebih rendah. Gambar 4 dan Gambar 5 berturut-turut merupakan eigenface dan fisherface yang dihasilkan dari sistem. Gambar 6 dan Gambar 7 adalah contoh citra wajah yang digunakan pada pengujian. Dalam ujicoba database YaleB, pertama digunakan data Training sebanyak 30 kelas, jumlah citra training setiap kelas 5 citra, sehingga jumlah citra pada database training adalah 150. Kedua digunakan data Training 30 kelas, jumlah citra training setiap kelas 7 citra. Sehingga
jumlah citra pada database training adalah 210. Masing-masing di tes dengan tiga citra tes. 30 kelas variasi pencahayaan dengan jumlah citra training setiap kelas adalah 5 di tes dua kali dengan pencahayaan yang berbeda. Begitu juga dengan 30 kelas variasi pencahayaan yang memiliki jumlah citra training 7 setiap kelas. Dalam ujicoba database att_face, pertama digunakan data Training sebanyak 30 kelas, jumlah citra training setiap kelas 5 citra, sehingga jumlah citra pada database training adalah 150. Kedua digunakan data Training 15 kelas, jumlah citra training setiap kelas 5 citra. Sehingga jumlah citra pada database training adalah 75. Masing-masing di tes dengan tiga citra tes. IV. HASIL PERCOBAAN Beberapa test yang telah dilakukan menunjukkan hasil laju pengenalan seperti bisa dilihat pada Tabel 1. Secara umum kombinasi PCA+LDA akan memberikan hasil pengenalan yang cukup baik pada saat pemilihan eigenface 20%-80% dengan persentase pengenalan diatas 90%. Gambar 8 merupakan grafik laju pengenalan pada ujicoba yang telah dilakukan. Dari Gambar 8 menunjukan bahwa laju pengenalan (recognition rate) akan menurun dengan bertambahnya dimensi fitur yaitu jumlah eigenface yang digunakan.
Tabel 1 Hasil Ujicoba 30 kelas variasi pencahayaan citra training I 5
Jumlah eigenfaceyang digunakan (%) citra tes
20
40
60
80
100
3
100
100
100
100
86
II
5
3
90
90
89
87
86
III
7
3
100
100
99
100
89
IV
7
3
93
91
89
88
86
30 kelas
5
3
90
90
89
86
84
15 kelas
5
3
98,3
98,3
95
83,3
79
95,21667
94,88333
93,5
90,71667
85
variasi headpose
Laju pengenalan (%)
Rata-Rata
100 95 90 85
Persentase pengenalan
80 75 20 40
60 80 100
Jumlah pemilihan Eigenface (%)
Gambar 8 Grafik laju pengenalan Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI-ITS
5
V. PENUTUP Kesimpulan Berdasarkan hasil pengujian yang dilakukan pada Tugas Akhir pengenalan wajah dengan metode subspace LDA, dapat disimpulkan bahwa: 1. Persentase pengenalan wajah paling akurat dalam kondisi variasi pencahayaan adalah pada eigenface 20% dengan rata-rata pengenalan 95,7%, sedangkan untuk kondisi pencitraan headpose 94,15%. 2. Semakin ekstrim pencahayan pada maka semakin turun persentase laju pengenalan. Hal ini dapat dibandingkan hasil dari citra training I dan citra training II yang mengalami penurunan 10% pada pemilihan eigenface sebesar 20%. 3. Semakin banyak citra training dalam suatu kelas maka semakin naik persentase laju pengenalan. Hal ini dapat dibandingkan hasil dari citra training I dan citra training III, namun kenaikan persentase tidak begitu signifikan. 4. Semakin banyak jumlah kelas maka semakin turun persentase laju pengenalan. Hal ini dapat dibandingkan hasil pengujian variasi headpose. Laju pengenalan 30 kelas headpose memiliki laju pengenalan 87,8% lebih rendah dari 15 kelas headpos yang memiliki memiliki laju pengenalan 90,78%.
RIWAYAT PENULIS
5.1.
Ratna Nur Azizah dilahirkan di Lamongan, 02 Juli 1987, merupakan putri pertama dari pasangan Bapak Nadi dan Ibu Rina. Setelah lulus dari MA Negeri Lamongan tahun 2005, kemudian melanjutkan studi Diploma 3 Jurusan Teknik Komputer Kontrol Fakultas Teknologi Industri Institut Teknologi Sepuluh Nopember (ITS) Surabaya pada tahun yang sama. Kemudian penulis melanjutkan studi Lintas Jalur di Jurusan Teknik Elektro ITS bidang studi telekomunikasi Multimedia Pada tahun 2008.
5.2
Saran Beberapa saran yang berguna untuk pengembangan Tugas Akhir ini antara lain: Untuk penelitian selanjutnya sistem dapat dikembangkan dengan menggunakan normalisasi Histogram Remapping atau Lognormal Distribution Mapping untuk memperoleh laju pengenalan yang baik
DAFTAR PUSTAKA [1]. David Zhang, Xiaoyuan Jing, Jian Yang, “Biometric Image Discrimination Technologies“, 2006 [2]. M. Turk and A. Pentland, "Eigenfaces for Recognition", J. Of Cognitive Neuroscience, Vol. 3, No. 1, pp. 71-86, 1991. [3]. P. N. Belhumeur, J. P. Hespanda, and D. J. Kiregeman, “Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection”, IEEE Trans. on PAMI, Vol. 19, No. 7, pp. 711-720, July 1997 [4]. K. Etemad and R. Chellappa, “Discriminant Analysis for Recognition of Human Face Images”, Journal of Optical Soeciety of America A, pp.1724-1733, Aug.1997. [5]. Hendra Kusuma, Wirawan, “Appearance-based Face Recognition dengan menggunakan PrincipalComponent Analysis (PCA) dan Nearest Mean Classifier”,2008 [6]. Hendra Kusuma, Wirawan, “Teknik Pengenalan wajah dengan Metoda Subspace LDA (Linear Discriminant Analysis)”,2008 Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI-ITS
6
