Perbandingan Ukuran Jarak pada Proses Pengenalan Wajah Berbasis Principal Component Analysis (PCA) Nimas Setya Yaniar Jurusan Teknik Elektro – FTI, Institut Teknologi Sepuluh Nopember Kampus ITS, Keputih-Sukolilo, Surabaya-60111
Abstract – Pengenalan wajah manusia merupakan salah satu bidang yang cukup berkembang dewasa ini. Aplikasi ini dapat diterapkan dalam bidang keamanan khususnya pada aplikasi PC login, keamanan basis data, atau system kendali akses. Pengenalan wajah merupakan sebuah permasalahan klasifikasi generic yang didasarkan pada obyek berupa wajah manusia. Pada tugas akhir ini dilakukan proses pengenalan wajah yang berbasis Principal Component Analysis (PCA), merupakan algoritma reduksi dimensi yang mampu menghasilkan komponen-komponen wajah (eigenface) yang digunakan sebagai pemroyeksi citra-citra wajah baru yang akan dikenali. Proyeksi ini bertujuan untuk mereduksi dimensi dari semua citra wajah baik sampel yang digunakan untuk pembelajaran maupun citra tes akan diwakili oleh titik-titik pada ruang berdimensi tinggi. Proses pengenalan akan dilakukan degan ukuran jarak antara titik-titik tersebut menggunakan metode pengukuran jarak antara lain Euclidean, Manhattan, Mahalanobis, Correlation, Angle-based, SSE dan MSE dengan menggunakan database Yale-B dan Att-face. Hasil yang diperoleh adalah jarak yang paling bagus untuk dilakukan pengenalan wajah dalam kondisi citra pencahayaan adalah jarak Correlation dengan persentase 88%, sedangkan untuk headpose SSE dan MSE memiliki keakuratan sebesar 81%, dan untuk penggabungan database Correlation dan MSE tingkat pengenalannya sebesar 92%. Jarak paling rendah tingkat pengenalannya adalah jarak Angle-based. Tingkat akurasi pengenalan yang paling bagus adalah menggunakan penggabungan database. Kata kunci: PCA, Pengukuran Jarak, Eigenface. I. PENDAHULUAN Pengenalan wajah (face recognition) merupakan salah satu kemampuan penting dalam kehidupan sosial manusia. Seseorang dapat mengingat ratusan bahkan ribuan wajah dalam hidupnya, dan mampu mengenali wajah tersebut dalam berbagai kondisi dan perspektif yang berbeda[1]. Pengenalan wajah merupakan sebuah permasalahan klasifikasi generik yang didasarkan pada obyek berupa wajah manusia. Proses pengenalan dilakukan dengan membandingkan citra wajah seseorang dan template wajah banyak orang yang tersimpan dalam database
atau dikenal dengan proses satu ke banyak (one to many). Proses ini dipengaruhi oleh faktor-faktor variabilitas intrapersonal diantaranya: posisi wajah, keberadaan komponen structural, ekspresi wajah, oklusi, orientasi citra, dan kondisi pencitraan[2][3][4], yang memiliki dimensi tinggi sehingga harus melalui proses kompresi terlebih dahulu sebelum diolah datanya dengan metode pengukuran jarak. Terdapat beberapa algoritma tentang pengenalan wajah, salah satunya algoritma yang berdasarkan appearance based yang banyak digunakan dalam sistem pengenalan wajah, dan juga dikenal dengan metode eigenface. Pada metode ini setiap citra wajah dianggap sebagai suatu vektor tunggal dengan cara menderetkan kolom-kolom pada citra wajah menjadi satu vektor yang panjang. Untuk mendapatkan eigenface yang akan berfungsi sebagai fitur, digunakan analisa komponen utama yaitu PCA (Principal Component Analysis). PCA digunakan untuk mendapatkan vektor-vektor atau disebut juga sebagai principal component yang dapat memberikan informasi tentang varian maksimum database wajah[2]. Pemakaian algoritma PCA ini proses pengenalannya menggunakan metode pengukuran jarak, diantaranya : Euclidean, Manhattan, Mahalanobis, Correlation, Angle based, Mean Squared Error(MSE), dan Sum Squarre error(SSE) yang membandingkan cara manakah yang memiliki akurasi paling bagus [5][6][7][8]. II. TEORI PENUNJANG Pengenalan Wajah Dalam pengenalan wajah terdapat dua masalah penting diantaranya pemodelan citra wajah (face representation) yang terdiri dari feature based dan holistic based, dan proses pencocokan (matching). Kedua masalah ini dalam pengenalan wajah juga dipengaruhi oleh kendala PIE (Pose, Illumination , Expression) yang menyebabkan algoritma pengenalan wajah tidak bekerja secara optimal. Spesifikasi sistem pengenalan wajah[9] diantaranya Identifikasi, Recognition, dan Categorization. Berdasarkan kesepakatan pada masing-masing algoritma yang ada, wajah akan diproses untuk mengurangi variasi citra seperti iluminasi dan pengenalan nama citra tersebut. Proses normalisasi dilakukan untuk menambah atau memperbaiki akurasi dari sebuah citra. Pengaruh pencahayaan dibagi menjadi tiga yaitu model pantulan, colour constancy, dan histogram equalization. 2.1
Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI‐ITS
1
2.2
Principal Component Analysis (PCA) Principal Component Analysis (PCA) adalah teknik reduksi dimensi yang umum digunakan pada aplikasi pemrosesan citra. PCA adalah suatu ekstraksi fitur dan teknik reduksi dimensi yang optimal jika dipandang dari sudut pandang teori informasi. Ide dasarnya adalah menentukan komponen utama dari serangkaian citra yang mengumpul membentuk suatu arah menurut varian maksimumnya. Maka dimensidimensi yang berkontribusi tersebutlah yang dipertahankan dan sisanya disingkirkan untuk tahap pemrosesan berikutnya[10] 2.2.1. Eigenvector dan Eigenvalue Eigenvector dari matrik persegi adalah vektor bukan nol yang dimana setelah dikalikan dengan matrik nilainya tetap sebanding dengan vektor asli. Untuk setiap eigenvector, maka nilai eigen yang sesuai adalah faktor yang terjadi perubahan eigenvector ketika dikalikan dengan matrik. Diberikan d anggota matrik M, Untuk scalar , dapat ditulis kembali, Suatu vektor x matrik merupakan vektor itu sendiri namun skalanya yang berubah. Karena vektor tersebut dikalikan dengan dirinya sendiri. Dimana I merupakan matrik identitas dan 0 adalah vektor zero. dan scalar yang Solusinya vektor x = yang kemudian disebut bersesuaian eigenvector dan masing-masing terkait eigenvaluenya. 2.2.2. Ekspektasi, Vektor rata-rata and Matrik Kovarian jika f(x) adalah sebuah fungsi dari n dimensi, maka vektor fungsi bernilai dari vektor acak d-dimensi x,
Kemudian diharapkan nilai f didenisikan sebagai
Dalam keadaan tertentu, d-dimensi vektor mean didefinisikan sebagai,
Serupa dengan mencari vektor mean, matrik kovarian didefinisikan sebagai matrik kuadrat dari elemen ij merupakan kovarian dari dan , Kita
dapat
adalah simetri, elemen diagonalnya Didapatkan, adalah nilai varian dari elemen tunggal x, yang tidak pernah bernilai negatif. Elemen diagonal merupakan covarian, yang bisa bernilai positif atau negatif. Jika varian bernilai statis dan berdiri sendiri, maka kovarian bernilai nol, dan matrik kovarian merupakan diagonal. 2.2.3. Algoritma PCA Penggunaan algoritma PCA pada Tugas Akhir ini digunakan untuk mereduksi dimensi dari titik yang berdimensi tinggi menuju titik yang berdimensi lebih rendah sehingga dapat lebih mudah dalam proses penghitungannya. Algoritma PCA ini diawali dengan proses proyeksi PCA yang terdapat proses penghitungan zeromean dengan tujuan mencari mean dari semua citra wajah kemudian mengurangkannya dan juga penghitungan matrik kovarian untuk himpunan citra latihnya. Setelah didapatkan matrik kovarian akan melalui tahap reduksi dimensi, yang mana citra latih akan ditransformasikan ke dimensi yang lebih rendah sebelum masuk ketahap pengklasifikasian. Dalam tahap klasifikasi ini akan terjadi proses penghitungan untuk mendapatkan hasil yang berupa tingkat akurasi. 2.3.
Pengukuran Jarak (Distance Measure) Penggunaan algoritma PCA untuk mereduksi dimensi yang tinggi ke dimensi yang lebih rendah sehingga lebih mudah dalam penghitungannya. Pengenalan wajah pada intinya adalah pencocokan dua wajah dimana wajah yang satu merupakan wajah yang telah dilatih dan ditempatkan didalam database kemudian dibandingkan dengan citra wajah tes atau citra wajah baru. Pencocokan tersebut salah satunya dengan menggunakan metode pengukuran jarak. Pada dasarnya pengukuran jarak digunakan untuk menghitung perbedaan antara dua vector citra dalam eigenspace. Setelah citra wajah diproyeksikan ke dalam space wajah, tugas selanjutnya adalah menentukan citra wajah yang mana yang paling mirip dengan citra dalam database. Ada banyak cara dalam mengukur tingkat kesamaan dan jarak. Diantaranya jarak Euclidean, Manhattan, Mahalanobis, Correlation, Angle-based, Squarred Euclidean. Dan pada akhirnya akan dibandingkan jarak manakah yang memiliki tingkat kecocokan paling tinggi. 2.3.1. Euclidean Distance Ruang Euclidean merupakan ruang dengan dimensi terbatas yang bernilai riil.. Jarak Euclidean antara dua titik adalah panjang sisi miring dari sebuah segitiga siku-siku[11]. Dimana x adalah citra training, dan y adalah citra input test. Jika dan merupakan dua titik dalam Euclidean ruang –n, maka jarak Euclidean x ke y adalah:
mengguunakan perkalian vektor untuk menghitung matrik kovarian,
Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI‐ITS
2
Nilai vektor pada jarak Euclidean dikatakan mirip jika jarak A mendekati 0, dan jarak B > 0 bergantung batas thresholdnya. Seperti tampak pada Gambar 1.
Gambar 1. Ilustrasi Jarak Euclidean, Manhattan, Mahalanobis, Correlation, Squared Euclidean
2.3.2. Manhattan Distance Merupakan salah satu pengukuran yang paling banyak digunakan meliputi penggantian perbedaan kuadrat dengan menjumlahkan perbedaan absolute dari variable-variable. Prosedur ini disebut blok absolute atau lebih dikenal dengan city block distance.
A1
A
A1
Gambar 2. Ilustrasi jarak Angle-based Pada jarak Manhattan dikatakan mirip jika vektor citra tersebut A mendekati 0 sedangkan jarak B > 0. Seperti ilustrasi pada Gambar 1.
Jarak Angle-based persamaan berikut ini:
dapat
dihitung
dari
2.3.3. Mahalanobis Distance Penghitungan jarak Mahalanobis ini didasarkan pada korelasi antara variable dan dengan pola yang berbeda dapat diidentifikasi dan dianalisa berdasarkan titik referensinya.
Dimana
nilai
bergantung pada besarnya eigenvalues. Pada jarak Mahalanobis, suatu citra dikatakan mirip jika eigenvektor A > 0 (bernilai semakin besar), sedangkan B mendekati 0. Seperti ilustrasi pada Gambar 1.
2.3.6. Squared Euclidean Distance Pengukuran jarak Squared Euclidean menggunakan persamaan yang hampir sama dengan pengukuran jarak Euclidean, namun tidak menggunakan akar kuadrat (dengan demikian clustering jarak Squared Euclidean lebih cepat daripada jarak Euclidean)[11].
2.3.4. Correlation coefficient-based Distance Korelasi mengukur kecepatan perubahan diantara piksel dari dua citra. Dari Gambar 1, korelasi menghasilkan nilai berkisar antara -1 ke 1, dimana nilai -1 mengindikasikan citra saling berlawanan satu sama lain (jarak B) dan nilai 1 mengindikasikan citracitra yang sama (jarak A). Korelasi antara citra x dan y adalah: III. PERANCANGAN SIMULASI Perancangan Perangkat Lunak Perancangan perangkat lunak pada proses pengenalan wajah menggunakan metode pengukuran jarak akan diimplementasikan melalui program MATLAB versi 7.6.0 (R2008a) serta pembuatan tampilan menggunakan GUI (Graphic User Interface) seperti tampak pada Gambar 3. 3.1. 2.3.5. Angle-based Distance Ilustrasi di atas memiliki maksud bahwa jika suatu citra dikatakan mirip jika sudut yang dibentuk kedua vektor A dan A1 adalah , dan dikatakan tidak . Range mirip jika sudut yang dibentuk adalah tingkat akurasi pada jarak Angle-based ini antara 0 – .
3.2.
Perancangan Algoritma Diagram blok gambaran system secara umum pada proses pengenalan wajah ini seperti terlihat pada Gambar 4. Perancangan algoritma pada proses pengenalan wajah ini terdapat beberapa tahap, diantaranya,
Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI‐ITS
3
(a)
(b)
Gambar 6. Mean dari 20 citra (a) pencahayaan, (b) headpose
Gambar 3. Tampilan awal GUI pengenalan wajah
Gambar 4. Blok Diagram Sistem Pengenalan Wajah 3.2.1. Tahap Pemrosesan Awal Pada tahap ini terdapat proses untuk mendapatkan zeromean yang merupakan proses normalisasi citra dan menghitung matrik kovarian dari himpunan citra latih. Citra piksel Suatu matrik citra T memiliki ukuran . Matrik ini kemudian akan dikonversikan ke suatu dengan ukuran vektor citra . dimana Training Set Merupakan satu berukuran citra-citra latih.
set
vektor-vektor citra yang . Nt merupakan jumlah dari
Mean Face
Merupakan rata-rata aritmetika dari vektor-vektor citra . latih pada setiap piksel yang berukuran
(a) (b) Gambar 7. Eigenface 20 wajah (a) Pencahayaan, (b) Headpose Covariance matrix
Merupakan matrik kovarian dari vektor-vektor citra piksel. Dari latih. Dengan ukuran matrik matrik kovarian ini terdapat nilai eigenvector dan eigenvalue. Eigenface dapat dilihat dari Gambar 7. 3.2.2. Tahap Reduksi Dimensi Hal yang paling penting dalam metode eigenface adalah mendapatkan eigenvektoreigenvektor dari matrik kovarian. Untuk citra dengan piksel, dan matrik kovarian ukuran dimana adalah dengan ukuran maka dimensinya sangat besar, dan sangat sulit dikerjakan. Oleh karena itu pada metode eigenface perhitungan eigenvektor tidak didapat melainkan secara langsung dari matrik . Nt merupakan jumlah dari melalui matrik citra wajah yang pada percobaan ini sebanyak 20 citra. kemudian diperoleh Eigenvektor dari matrik melalui eigenvektor-eigenvektor matrik tersebut. Langkah pertama adalah mendefinisikan suatu matrik Z sebagai,
Mean substracted image Merupakan pengurangan citra latih terhadap mean . face yang berukuran
Kemudian Z disubstitusi dengan,
Difference matrix
Dengan mengalikan kedua sisi dengan didapat,
Merupakan matrik zeromean yang berasal dari semua . vektor citra latih, berukuran
Untuk mempermudah penghitungan, maka diatur dahulu menurut ukuran matriknya menjadi,
, maka
Pengaturan susunan tersebut diatas karena merupakan matrik kovarian merupakan scalar., , maka, (a) (b) Gambar 5. Sebagian database wajah (a)Pencahayaan, (b) Headpose
Kemudian dengan mengganti maka,
Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI‐ITS
menjadi
, yaitu
4
Merupakan eigenvektor dari dimana . ukurannya Dari beberapa persamaan diatas terlihat bahwa dapat diperoleh melalui eigenvektor dari eigenvektor dari Z, oleh karena itu daripada maka menggunakan matrik dengan ukuran lebih sederhana jika menggunakan matrik berukuran . Cara yang seperti ini memberikan efek penghitungan yang sangat besar. Gambar di bawah ini merupakan karakteristik eigenface yang didapat dari citra-citra latih wajah. Eigenface merupakan vektor jika dilihat dari segi yang berukuran penghitungan.
Gambar 8. Spektrum Eigenvalue mulai
3.2.3. Tahap Klasifikasi Berdasarkan algoritma PCA, jumlah eigenface yang akan dijadikan classifier sebanyak Nt tidak digunakan seluruhnya, melainkan hanya mengambil eigenface yang terbesar dengan mengurangi sebanyak 30% eigenface terkecil yang kemudian dilambangkan yang selanjutnya akan sebagai , dimana digunakan sebagai proyeksi eigenface. Gambar 8 merupakan jumlah eigenvalue dari 20 citra latih yang telah diurutkan dari terbesar hingga terkecil. Langkah selanjutnya citra-citra latih tersebut diproyeksikan pada ruang eigenface, sehingga kemudian akan ditentukan bobot (weight) dari setiap eigenvektor.
Image (
)
Mean Substracted Image Test
Proyeksi
Matrik bobot
Rekonstruksi Citra
Proyeksi Persamaan di atas merupakan proyeksi suatu citra yang telah dilatih pada setiap eigenvektor dimana k = 1, 2, 3,…. N’.
selesai
Gambar 9. Diagram alir untuk mendapatkan matrik bobot citra tes
Matrik bobot Matrik bobot merupakan representasi citra latih . pada ruang eigenface yang berukuran Pada tahap ini citra dibentuk oleh bobot-bobot pada ruang eigenface dan secara sederhana citra-citra tersebut seperti memiliki harga piksel pada ruang citra. Setiap citra yang direpresentasikan oleh suatu pada ruang citra dimana citra berukuran setelah dilakukan pemrosesan maka citra tersebut pada diwakili oleh suatu vektor berukuran ruang eigenface.
Dari Gambar 10 dapat diketahui perbandingan persentase akurasi ketiga kondisi pencitraan yang digunakan dalam percobaan beserta ketujuh jarak yang dilakukan. Bahwa jarak Mahalanobis dan Anglebased memiliki akurasi lebih rendah dibanding jarak yang lain. Sedangkan yang memiliki akurasi paling bagus. Berikut ini merupakan grafik hasil persentase benar masing-masing jarak untuk ketiga kondisi pencitraan.
Citra Tes Gambar 9 merupakan diagram alir dari algoritma penghitungan matrik bobot citra tes. IV. ANALISA DAN PEMBAHASAN Citra latih yang digunakan dalam percobaan pengenalan wajah ini sebanyak 20 wajah dengan kondisi pencitraan pencahayaan dan headpose. Citra latih pencahayaan ini diambil dari database Yale-B, sedangkan citra latih headpose diambil dari database att_face dengan ukuran 150 x 135 dan 150 x 135 piksel.
Gambar 10. Grafik Perbandingan persentase akurasi pengenalan wajah
Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI‐ITS
5
4.1.
Pencahayaan DAFTAR PUSTAKA Dari Gambar 10 dapat diketahui jarak yang [1] Lambert, D.M., Armitage, H.M., “Management memiliki tingkat akurasi paling bagus pada kondisi Distribution Cost for Better Profit Performance”, pencitraan adalah Correlation sebesar 88%. Business Mags 30 No.5. 1980, 46-52. Sedangkan untuk Mahalanobis dan Angle-based [2] Ming-Hsuan Yang, David J. Kriegman, Narendra memiliki persentase paling rendah sebesar 63%. Ahuja. Detecting Faces in Images: A Survey. IEEE Trans. Pattern Analysis and Machine Intelligence, 4.2. Headpose vol. 24, no. 1, pp.34–58, Jan 2002. Untuk kondisi pencitraan headpose, persentase [3] Ming-Hsuan Yang. Recent Advances in Face Detection. ICIP 2003 Tutorial: Advance in Face jarak yang memiliki tingkat akurasi paling bagus Processing, 2003. adalah jarak SSE dan MSE sebesar 81%. Sedangkan untuk Euclidean serta Angle-based tingkat akurasinya [4] WenYi Zhao and Rama Chellappa. Image-based Face Recognition: Issues and Methods. Sarnoff rendah sebesar 64% Corporation and Univ of Maryland, 2004. [5] Grudin, M. A., 1997. A compact multi-level model 4.3. Gabungan for the recognition of facial images. Ph.D. thesis, Pada kondisi pencitraan gabungan Liverpool John Moores University. (pencahayaan dan headpose) jarak yang memiliki akurasi paling bagus adalah Correlation dan MSE [6] Yambor, W.S., Draper, B.A., Beverige, J.R., 2002. Analyzing PCA-based face recognition algorithm: sebesar 92% sedangkan yang paling rendah adalah Eigenvector selection and distance measures. In: jarak Mahalanobis. Christensen, H., Philiphs, J. (Eds.), Empirical Evaluation Methods in Computer Vision World V. PENUTUP Scientific Press, Singapore. 5.1. Kesimpulan Berdasarkan hasil pengujian yang dilakukan [7] Philiphs, P.J., Moon, P., Rizvi, S.A., H., Rauss, P.J., 2000. The FERET evaluation methodology pada Tugas Akhir perbandingan ukuran jarak pada for face recognition algorithms. PAMI 22 (10), proses pengenalan wajah berbasis Perincipal 1090-1104. Component Analysis (PCA), dapat disimpulkan [8] Cekanavicius, V., Murauskas, G., 2002. Statistics bahwa: and its applications. Part 2. TEV, Vilnius. P. 272 1. Persentase pengenalan wajah paling akurat dalam (in Lithuanian). kondisi citra pencahayaan adalah menggunakan jarak Correlation dengan persentase sebesar 88%, [9] Kyungnam Kim,”face recognition using Principal Component Analysis”, Department of computer sedangkan untuk kondisi pencitraan headpose Science , university of Maryland, College Park. menggunakan jarak SSE dan MSE dengan persentase 81%, dan untuk kondisi penggabungan [10] Hendra Kusuma dan Wirawan., Appearance-based face recognition dengan menggunakan Principal menggunakan jarak Correlation dan MSE dengan Component analysis (PCA) dan Nearest Mean persentase sebesar 92%. Classifier. 2. Jarak Angle-based memiliki tingkat pengenalan [11] Vytautas Perbalikas. 2003. Distance Measure for paling rendah sebesar 63%. PCA-based Face Recognition. Kaunas University 3. Kondisi citra pencahayaan +000E+20 dan of Technologies. +005E+10 memiliki tingkat akurasi pengenalan paling tinggi sebesar 100%, sedangkan citra RIWAYAT PENULIS pencahayaan +025E+00 memiliki tingkat akurasi Nimas Setya Yaniar dilahirkan di pengenalan paling rendah sebesar 50%. Lumajang, 15 Januari 1987, 4. Jenis kesalahan yang sering terjadi adalah merupakan putri pertama dari kesalahan mengenali wajah dengan database citra pasangan Bapak Yayok Affandi dan latih lain. Ibu Suti’ah. Setelah lulus dari SMA 5. Tingkat akurasi pengenalan yang paling bagus Negeri 02 Lumajang tahun 2005, adalah menggunakan penggabungan database kemudian melanjutkan studi (Yale-B dan Att-face). Diploma 3 Jurusan Teknik Elektro Politeknik Negeri Malang pada tahun yang sama. 5.2 Saran Beberapa saran yang berguna untuk Kemudian penulis melanjutkan studi Lintas Jalur di Jurusan Teknik Elektro ITS bidang studi pengembangan Tugas Akhir ini antara lain: 1. Untuk penelitian selanjutnya system dapat telekomunikasi Multimedia Pada tahun 2008. Selama dikembangkan dengan menggunakan studi penulis aktif menjadi asisten praktikum penghitungan jarak yang lainnya [11] seperti Komunikasi Data dan Pengolahan Sinyal Digital di Minkowski distance, Weighted Manhattan Laboratorium Multimedia yang diadakan oleh bidang studi Telekomunikasi Multimedia. distance, dll. 2. Pengujian dapat dikembangkan dengan menggunakan database selain Yale-B dan headpose atau penggabungan keduanya. Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI‐ITS
6