PENGELOMPOKAN CITRA WAJAH DENGAN TEKNIK SUBSPACE CLUSTERING MENGGUNAKAN ALGORITMA LSA – SC (LOCAL SUBSPACE AFFINITY – SPECTRAL CLUSTERING) Disusun oleh : Febryan Setiawan (0922081) Jurusan Teknik Elektro, Fakultas Teknik, Universitas Kristen Maranatha Jl. Prof. Drg. Suria Sumantri, MPH, No. 65, Bandung, Indonesia E – mail :
[email protected] ABSTRAK Pengelompokan citra wajah (face clustering) dapat membantu sistem pengenalan wajah (face recognition) untuk meningkatkan keandalan, efisiensi, dan keakuratan sistem dalam hal mengenali identitas suatu citra wajah. Pengelompokan citra wajah ini bertujuan untuk mengelompokan setiap citra wajah dalam database berdasarkan identitas wajah. Permasalahan yang muncul adalah citra wajah merupakan data berdimensi tinggi yang dapat dikelompokkan secara berbeda pada subruang – subruang tertentu. Untuk mengatasi masalah ini dikembangkan suatu teknik pengelompokan subruang (subspace clustering) untuk memilihkan subruang yang tepat untuk proses clustering. Dalam Tugas Akhir ini digunakan suatu algoritma untuk menentukan subruang yang tepat untuk proses clustering. Algoritma Local Subspace Affinity diterapkan untuk melakukan perkiraan penentuan subruang yang tepat dengan sampling lokal kemudian mencari matriks affinity dan melakukan clustering berdasarkan matriks tersebut dengan menggunakan algoritma Spectral Clustering (k – means). Berdasarkan hasil percobaan Tugas Akhir ini, sistem pengelompokan citra wajah menggunakan algoritma Local Subspace Affinity – Spectral Clustering mampu mengelompokkan citra wajah tepat berdasarkan identitasnya jika di dalam database terdapat 5 identitas orang yang berbeda. Untuk 6 ≤ 𝑗𝑢𝑚𝑙𝑎ℎ 𝑖𝑑𝑒𝑛𝑡𝑖𝑡𝑎𝑠 ≤ 10 dalam database maka presentase classification error adalah 12,5% − 23.81%. Selain itu, diketahui bahwa sistem pengelompokan citra wajah dengan menggunakan algoritma ini lebih baik dalam hal menemukan cluster yang tepat dibandingkan algoritma lain untuk database citra wajah yang sama diujikan dalam Tugas Akhir ini.
Kata Kunci : face clustering, data berdimensi tinggi, subruang, clustering, cluster, subspace clustering, LSA – SC, identitas wajah.
i
Universitas Kristen Maranatha
FACE CLUSTERING WITH SUBSPACE CLUSTERING TECHNIQUE USING LSA – SC (LOCAL SUBSPACE AFFINITY – SPECTRAL CLUSTERING) ALGORITHM Composed by : Febryan Setiawan (0922081) Department of Electrical Engineering, Faculty of Engineering, Maranatha Christian University, Bandung, Indonesia E – mail :
[email protected] ABSTRACT Face clustering could help face recognition system to increase reliability, efficiency, and accuracy that system for recognizing the identity of face image. Face clustering is aim to cluster each face images in the database based on identity of the people’s faces. But the problem what appears is a face image is a high dimensional data which could be clustered in different cluster in the specific subspaces. To solve this problem developed a subspace clustering technique to choose the exactly subspaces for clustering process. In this final project proposed an algorithm to determine the exactly subspaces for clustering process. Local Subspace Affinity algorithm is used to estimate the exactly subspaces with local sampling then find the affinity matrix and cluster based on that matrix using Spectral Clustering (k – means) algorithm. On the experiment in this final project, face clustering system using Local Subspace Affinity – Spectral Clustering could find cluster of face images in correctly based on its identity if in the database there are 5 different identities of the face images. For 6 ≤ 𝑡ℎ𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑖𝑑𝑒𝑛𝑡𝑖𝑡𝑖𝑒𝑠 ≤ 10 in the database, the presentation of error classification is 12,5% − 23,81%. Beside it, known from the experiment that face clustering system using this algorithm is better in the case of finding the exactly cluster compared with the other algorithms for the same face database which were tested in this final project.
Key words : face clustering, high dimensional data, subspace, clustering, cluster, subspace clustering, LSA – SC, identity of the faces.
ii
Universitas Kristen Maranatha
DAFTAR ISI ABSTRAK ................................................................................................................... i ABSTRACT ................................................................................................................ ii KATA PENGANTAR ............................................................................................... iii DAFTAR ISI .............................................................................................................. vi DAFTAR GAMBAR ................................................................................................. ix DAFTAR TABEL ...................................................................................................... xi
BAB I PENDAHULUAN 1.1
Latar Belakang ................................................................................................ 1
1.2
Identifikasi Masalah ........................................................................................ 3
1.3
Rumusan Masalah ........................................................................................... 3
1.4
Tujuan ............................................................................................................. 3
1.5
Pembatasan Masalah ....................................................................................... 4
1.6
Sistematika Penulisan ...................................................................................... 5
BAB II LANDASAN TEORI 2.1
Pengenalan Pola (Pattern Recognition) .......................................................... 7
2.2
Pengenalan Wajah (Face Recognition) ........................................................... 7
2.3
2.4
2.2.1
Proses Pengenalan Wajah ................................................................... 9
2.2.2
Image Space dan Face Space ............................................................ 10
Algoritma Deteksi Wajah .............................................................................. 11 2.3.1
Local Mean Quantization Transform (Local SMQT) ........................ 11
2.3.2
Pengklasifikasi Split Up SNoW (Sparse Network of Winnows) ........ 15
Pengelompokan (Clustering) ........................................................................ 17 2.4.1
Objek dan Atribut .............................................................................. 18
2.4.2
Tipe Data dan Ukuran Data ............................................................... 19
2.5
Pengelompokan Subruang (Subspace Clustering) ........................................ 19
2.6
Pengelompokan Wajah (Face Clustering) .................................................... 20 vi
Universitas Kristen Maranatha
2.7
Kontruksi Eigenface/Principal Component Analysis (PCA) ........................ 21
2.8
Singular Value Decomposition (SVD) .......................................................... 22
2.9
Teknik Face Clustering ................................................................................. 23 2.9.1
Algoritma LSA – SC ........................................................................... 23
2.9.2
Algoritma Spectral Clustering .......................................................... 26
2.9.3
Algoritma k – means ......................................................................... 27
BAB III PERANCANGAN SISTEM PENGELOMPOKAN CITRA WAJAH DENGAN TEKNIK SUBSPACE CLUSTERING MENGGUNAKAN ALGORITMA LSA – SC 3.1
Proses Face Clustering ................................................................................. 30
3.2
Deteksi Wajah ............................................................................................... 32
3.3
Konstruksi Eigenface .................................................................................... 33
3.4
Algoritma Local Subspace Affinity ............................................................... 35 3.4.1
Local Normal Subspace Affinity ........................................................ 36
3.5
Algoritma Spectral Clustering ...................................................................... 38
3.6
Algoritma k – means ..................................................................................... 40
BAB IV SIMULASI DAN ANALISA HASIL PERCOBAAN 4.1
Database Citra Wajah ................................................................................... 42
4.2
Hasil Percobaan ............................................................................................. 43
4.3
4.4.
4.2.1
Algoritma LSA – SC Untuk PERCOBAAN (1) ................................ 43
4.2.2
Algoritma LSA – SC Untuk PERCOBAAN (2) ................................ 49
Analisa Hasil Percobaan ............................................................................... 54 4.3.1
Analisa Hasil PERCOBAAN (1) ...................................................... 54
4.3.2
Analisa Hasil PERCOBAAN (2) ...................................................... 54
Perbandingan Hasil Face Clustering Algoritma LSA – SC dengan Algoritma Lain ................................................................................ 55
vii
Universitas Kristen Maranatha
BAB V KESIMPULAN DAN SARAN 5.1
Kesimpulan ................................................................................................... 57
5.2
Saran .............................................................................................................. 58
DAFTAR PUSTAKA ............................................................................................... 59 LAMPIRAN PROGRAM MATLAB
viii
Universitas Kristen Maranatha
DAFTAR GAMBAR
Gambar 1.1
Variasi Citra Wajah ............................................................................. 2
Gambar 2.1
Ilustrasi Penggunaan Sistem Biometric MRTD .................................. 8
Gambar 2.2
Proses Pengenalan Wajah Secara Umum ............................................ 9
Gambar 2.3
Image Space dan Face Space ............................................................ 10
Gambar 2.4
Mean Quantization Unit (MQU) ....................................................... 12
Gambar 2.5
Successive Mean Quantization Transform (SMQT) .......................... 13
Gambar 2.6
Proses Clustering .............................................................................. 17
Gambar 2.7
Tipe Data dan Ukuran Data ............................................................... 19
Gambar 2.8
Pengelompokan Wajah (Face Clustering) ........................................ 21
Gambar 2.9
Proses Clustering dengan Algoritma k - means ................................ 28
Gambar 2.10 Hasil Clustering dengan Centroid Awal Berbeda.............................. 29
Gambar 3.1
Flowchart Proses Face Clustering .................................................... 32
Gambar 3.2
Flowchart Proses Deteksi Wajah ...................................................... 33
Gambar 3.3
Flowchart Konstruksi Eigenface ....................................................... 34
Gambar 3.4
Flowchart Algoritma Local Subspace Affinity .................................. 35
Gambar 3.5
Flowchart Subroutine Mencari Matriks Affinity ............................... 37
Gambar 3.6
Flowchart Algoritma Spectral Clustering ........................................ 39
Gambar 3.7
Flowchart Algoritma k – means ........................................................ 41
Gambar 4.1
Database Citra Wajah ....................................................................... 42
Gambar 4.2
Hasil PERCOBAAN (1) dengan Terdapat 𝑡𝑖𝑔𝑎 Identitas Wajah ..... 44
Gambar 4.3 Gambar 4.4 Gambar 4.5 Gambar 4.6
Hasil PERCOBAAN (1) dengan Terdapat 𝑒𝑚𝑝𝑎𝑡 Identitas Wajah . 44
Hasil PERCOBAAN (1) dengan Terdapat 𝑙𝑖𝑚𝑎 Identitas Wajah .... 44 Hasil PERCOBAAN (1) dengan Terdapat 𝑒𝑛𝑎𝑚 Identitas Wajah .. 45
Hasil PERCOBAAN (1) dengan Terdapat 𝑡𝑢𝑗𝑢ℎ Identitas Wajah .. 45 ix
Universitas Kristen Maranatha
Gambar 4.7
Hasil PERCOBAAN (1) dengan Terdapat
Gambar 4.8
𝑑𝑒𝑙𝑎𝑝𝑎𝑛 Identitas Wajah .................................................................. 46
Gambar 4.9
𝑠𝑒𝑚𝑏𝑖𝑙𝑎𝑛 Identitas Wajah ................................................................ 46
Hasil PERCOBAAN (1) dengan Terdapat
Hasil PERCOBAAN (1) dengan Terdapat
𝑠𝑒𝑝𝑢𝑙𝑢ℎ Identitas Wajah .................................................................. 47
Gambar 4.10 Hasil PERCOBAAN (2𝑎) dengan Terdapat 𝑡𝑖𝑔𝑎 Identitas Wajah .. 50 Gambar 4.11 Hasil PERCOBAAN (2𝑎) dengan Terdapat
𝑒𝑚𝑝𝑎𝑡 Identitas Wajah ..................................................................... 40
Gambar 4.12 Hasil PERCOBAAN (2𝑎) dengan Terdapat 𝑙𝑖𝑚𝑎 Identitas Wajah .. 51
Gambar 4.13 Hasil PERCOBAAN (2𝑏) dengan Terdapat 𝑡𝑖𝑔𝑎 Identitas Wajah .. 51 Gambar 4.14 Hasil PERCOBAAN (2𝑏) dengan Terdapat
𝑒𝑚𝑝𝑎𝑡 Identitas Wajah ..................................................................... 52
Gambar 4.15 Hasil PERCOBAAN (2𝑏) dengan Terdapat 𝑙𝑖𝑚𝑎 Identitas Wajah .. 52
x
Universitas Kristen Maranatha
DAFTAR TABEL
Tabel 4.1
Hasil face clustering dengan menggunakan
Tabel 4.2
algoritma LSA – SC untuk percobaan 1 ....................................................... 48
Tabel 4.3
algoritma LSA – SC untuk percobaan 2 ....................................................... 53
Hasil face clustering dengan menggunakan
Perbandingan presentase error classification face clustering
untuk beberapa algoritma clustering .......................................................... 55
xi
Universitas Kristen Maranatha
