FACE RECOGNITION MENGGT]NAKAN METODE LINEAR DISCRIMINAIIT ANALYSIS (LDA) ResmanaLim l, RaymondI & Kartika Gunadi2 l) JurusanTeknik Elektro 2) JurusanTeknik Informatika UniversitasKristen PeEa Siwalankerto l2l- 131, Surbaya. Fax:031-8436418 E-mail : {resmana;kgunadi}@petra.ac.id Ma* Paper ini membahas sistem pengenalan imagewajah dengan 2 metode ekstraksifeature sistik yaitu PCA (Principal Components Analysis) dan LDA (Linear Discriminant Analysis). metode ekstraksi feature yang tepat dan efuien sangat rnenentukan keberhasilan dari bilihan jdl t pengenalan secara keseluruhan. Sistem dibangun menggunalran platfurm PC dengan program lomputer menggunakan Delphi. Sistem diuji menggunaknn berbagai irnage alisan Hnse yang diambil menggunakan knmera digital yang terdiri dari 12 orang dengan masingI0 image. Sistemiuga diuji menggunakan Yalefaces database yang terdiri dari 14 orang -dry masing-masing 9 image. Metode pengenalan pola menggunalcan nearest neighbor fEn .frwa dan dihasilkan recogntion rate antara 80-90% dengan berbagai variasi penambahan oklusi. *fun bfurci
: face recognition, LDA, PCA, pengenalanpola.
Pendahuluan Sistem pengenalanwajah banyakdimanfaatkanpada biometricsyang digunakanuntuk i personal pada penggunaanmesin absensi, akses kontrol dan lain-lain. Secara umum pcngenalan n image tidak menggunakanbitmap pixel secaralangsung melainkan ia beke{a {'rnein feature. Image direpresentasikankedalam bentuk feature yang lebih kompak yang n digunakan untuk pengenalan,dengan demikian dapat menghemat komputasi. Berbagai Gtsnrasifeature telah dimanfaatkan seperti metode moment, feature filter Gabor, Wavelet,
b{rin [l]. Dalam paperini akandigunakan2 metodeekstrasifeaturesecarastatistikyang telahlamadigunakanyaitu PCA (PrincipalCbmponents Analysis)[2] dan LDA (Linear imt Analysis)[3]. ililaode PCA dikenal juga dengannama Karhunen-Loevetransformation (KLT), yang telah rirk 30 tahun dalam dunia pengenalanpola. PCA memberikan transformasi ortogonal dengan 'eigenimage' yang mana sebuah image direpresentasikankedalam bentuk n fni:r searahdengan eigenimageyang bersesuaiandengannilai eigen terbesar dari matrix
r (tau scatter matrix). Secarapraktis matrix covarianceini dibangun dari sekumpulan big yangdiambil dari berbagaiobyek/kelas. EA memberlakukanproperti sthtistikyang samabagi seluruhimagetraining dari berbagai b. Tilak demikian halnya pada LDA, ia membertakukanproperti statistik yang terpisah obyek. Tujuan dari LDA adalah mencari proyeksi liniear (yang biasa disebut dengan tmtuk memaksimumkan matrix covariance antar obyek (between-class covariance itu juga meminimumkan matrix covariance didalam obyek itu sendiri (withinEha
il-ri
matrix). Bila tersediaimage training yang cukup representatifdalam jumlah bentuk untuk tiap-tiap obyek maka metode ekstraksi LDA akan menunjukan lcbih baik dari padaPCA sepertiyangditunjukanpadahasil-hasilpercobaandalam paper ini disusun sebagaiberikut: pada pasal 2 dan 3 akan dijelaskan metode Deskripsi sistem diberikan pada pasal 4 dan hasil-hasil percobaan diberikan pada dengan diskusi/kesimpulanpada pasal 6. A-l 17
"-"' 2.
""*1iffi1;1ft51*ff;ff;Tnff'fi'Jf#fl?;"1 PrincipalComponentsAnalysis(PCA)
kedalam Sebuahimage 2D dengandimensi 6 baris dn kkolom dapat direpresentasikan sebagaiEn, bentuk image lD dengandimensi n (n*b*k). Denganekspresilain dapat dituliskan K sampel sebanyak yang digunakan adalah ruang imag" i"rrgun dimensi n. Imagc tt"itting yalg dinyatakan obyelc&elas c dinyatakani*g* {r,, ,1, ..., xfi yang diarnbil dari sebanyak i"}. totat matrix JcatterSr (atau matrix covariance)didefinisikan sebagai ..., X; dengan{Xr, berikut: K (1 ) - p ) ( x * -p ) '
s.=f(;r
haining image {x'' x'' dimanap adalah ntz-tatasampel imageyang diperoleh-dengan-merata-rata menjadi: covarianceini dapatdidekomposisi -.,,r*].bengan dekomposisi"ig"rr, -"tri* (2 ) S r=@A (Dr eie-en'Kemudian dimanaO adalahmatrix eigenvector,dan A adalahis a diagonalmatrix dari nilai m nilai dipilih sejumlahru kolom eigenvectordari matrix o yangberasosiasidengansejumlah proyeksi matrix atau transformasi pemilihan matrix eifenvector ini menghasilkan eigenter6esar. juga dengan disebut O], y*g manaterdiri dan mkolom eigenvectorterpilih yangbiasa ."ig"niri"g"'. Berikutnyasebuahimage.r (berdimensin)dapatdiekstraksikedalamfeaturebaruy x searahdenganip, sebagaiberikut: 6eiaimensim < n) denganmemproyeksikan ! =@ ^ x
(3 )
ruangasal En ke dalamruangbaruyang Dengankatalain metodePCA memproyeksikan asal tetap berdimensilebih rendah A', yang mana sebanyakmungkin kandunganinformasi kecil' yang lebih untuktidak terlalubanyakhilangsetelahdibawake dimensifeature dipertahankan yang tentunyaakan Disini terlihat reduksifeatureyang iignifitan Oariz buah menjadiln buah bgrikltnfa' pengenalan proses komputasidalam sangatmeringankan Total matrix ,."tt., Sr diatasr"rungguhnyaadalahjumlahandari matrix scatterdalam i* scatterantarkelas&ery9en1fass.scattermatrix) kelas(within-classscattermatiixl ,S' dan -"tkekuranganutamayang terlihat disini adalahbahwa Ss yaitu, Sr = Sr, + S3. Dengandemikian, bersamasama. :;1 dalamprosesPcA ke duamatrix scatterini termaksimalkan mungkin sebisa sedangkan saja, maksimalisasi,ss hanya adalah yangdiinginkan 'Srz Sesungguhnya ya\F pada akhirnya diminimalkanagar ungg-otudidalam kelai lebih terkumpulpenyebarannya iluminasimaupun perubahan variasi pada Misalkan keberhasilanpengenalan. dapatmeningkaikan scatterdalam mltrix menyebabkan skaladari imageyang terjadi pada obyek yang sama,dapat dengan ini_terjadi, Bila kelasmenjadibesarfang-cukrp menyulitkandalamprosespengenalan. konsekuensinya demikianpCA akan meriyertakanvariasi iluminasi didalam eigenimage-nya,dan PCA menjaditidak handal terhadapvariasi iluminasi yang terjadi pada obye\ Denganmetofg handal LDA, ,Sr akan diminimisasi sehingga ekstrasi featurl yang dihasilkan menjadi lebih ferhadapvariasiyang terjadi didalamkelas. 3.
Linear Discrimination Analysis (LDA)
Matrix scatter dalam kelas ,Sy, dan matrix scatter antar kelas .9adidefinisikan masingmasingsebagaiberikut: c
-S
'tw- L
f {to - F)@* - P,)' xleX;
(4)
s" =i N,(p,-p)(p, -
p)'
(5)
i=l
dimana l/, adalahjumlah sampelpadakelas X,, d- p,adalah image rata+atzdari kelas X,. S€pertidiutarakansebelumnyabahwasangatdiharapkanagarmatrix scafferdalam kelas ^S" bisa diminimalisasi sementaramatrix scatterantar kelas ,S, dimaksimalkan.Dengan kata lain akan (6) menjadimaksimal. ratio persamaan dicari mahix proyeksi Y, "g"t de(Y,SrV,r)
(6)
de(Y,.SrYf) sebagaiberikut[3]: solusidenganpersamaan Kriteriaini menghasilkan SrY =.S,'YA
Q)
dimana Y adalah matrix eigenvector,dan Aadalah matrix diagonal nilai eigen. Dengan kata lain akan dicari eigenvector dan eigenvalue dari matrix C yang merupakan kombinasi within & beetwin scatter matrix seperti pada persamaan 8. Kembali dilakukan pemilihan sebanyak / kolom eigenvector dari Y yang berasosiasidengannilai-nilai eigen terbesar. pemilihan / kolom eigenvector ini menghasilkanmatrix proyeksi Y, yang selanjutnya digunakan untuk ekstraksi feature seperti halnya pada PCA.
(8)
C = SaS*-t 4.
Deskripsi Sistem
Blok diagram sistem pengenalanwajah dapat dilihat pada gambar l, yang mana disini digunakan feature reduction menggunakanPCA yang dilanjutkan dengan LDA. Sebagian image digunakan sebagai training dataset untuk ditransformasi kedalam bentuk feature yang disimpan dalam database.Image input yang hendak dicari identitasnya ditransformasikan kedalam bentuk featureyang selanjutnyadenganclassifiernearestneigborakandikenali identitasnya.
Gambar I. BIok Diagram SistemPengenalan l4raiah.
Procecdings,K6mputcrdan Sistem Iatelijen (KOMMIT 2002) AuditoriumUniversitasq*
A-120
sebagaibcrikut : Ringkasandari seluruhalgoritmaPCd + LDA adalah lrl*cnkkflt date pixcl semru imagc training kc uratniks u
CariuntrikrC g. = gr' xu Caricigcnvaluc(Lldur Eigenvcr.r
! *tk, -iY,r TransJnscmatriksf, dan ang.gpscbagaiinPutbcgi LD'{ Cari Strdart Srt. lalu cari (- =.frSr-t
Cari r-igenvaltre( ?. i dan Eigat vc'ctori\''l dari matriks C
CarintatriksfeatureLD.{
r =i(r,-i,[ ",r' FeaturePCA + LDA Ekstrat<si Gambar2. Ringkasan 1. Masukkandata pixel imagetraining ke dalammatriks
u
: berdimensi100x 100pixels 10'0(n Misalkanterdapatft imagetrainingdenganmasing-masing : image-imaletersebutberdimensi10'000x o,' adalah pixels.Matriksyurrg;;rJpresentaslkan
u=l
['''' I ur,
ur'z
ut'^
uz,z
uz,n''"
... 4roooo,z
uroooo,.
(e)
t.
I
l_r,**,,
2. Mencari imagerata-rata rata-ratadari semuapixel image-imagetraining' Image Rata-Rataadalah
;=Li.u,,
(10)
mE
yaitu: matriksnta-ratatotal PcA dengandimensi 10'000x 1' Dari matriksdi atas,didapatkan
Flcc Recognition Menggunakan Metode Linear Discriminant Analysis (LDA)
A-l2l
li,,
;=l
(1 1 )
t-
Lil Loooo,t
l. Mencari covariancematriks PCA Xetriks covariancePCA dapatdicari denganrumussebagaiberikut : C =ur xu
(I 2 \
llatriks covariancedengandimensim x m, dimanam adalahjumlah imagetraining. Dcagandekomposisieigenberlaku: (1 3 )
C x v= )"xv
Iftumgi eigen value (),) daneigenvector (V) dari matriks C menggunakanmetodeJacobi [5]. diurutkansecaradescending. Eigen facesyang E{'en value dan eigen vector yang bersesuaian di@atkan ini dapatdilihat dalamilustrasidi bawahini :
Gambar 3. Dua belas Eigenfoces Pertama. &Iam eigen faces di atas dapat dilihat bahwa dapat dibedakan antara wajah yang menghadapke depan,kanan,belakang. Eigen faces ini dapat dijadikan pembanding saat merecognize suatu image. { Mencari feature PCA Eigen vector hasil proses pada langkah 3, beserta dengan image rata-rata digunakan untuk mrransformasikan raw image ke dalam ruang feature f. Selanjutnya feature f disimpan dalam dmbase untuk kemudian digunakan pada proses pengenalan.Proyeksi raw input image ke ruang dgen dapat dihitung menggunakanrumus berikut: nt
/
f =>lr,- u)'"rt -\T
(14)
i=l
p :jumlah image training 1, = Image input i : Imagerata-rata total V: matriks eigen vector 5. Selanjutnya feature hasil PCA digunakan sebagaiinput pada proses LDA LDA memisahkan tiap image ke dalam class yang berbeda. Class adalah kumpulan image yang dmiliki oleh seseorangyang sama. Pada contoh database,ada 12 orang masing-masing memiliki !O image training. Pada perhitungan PCA akan didapat 1 buah kumpulan image terdiri dari 120 ;nragetraining (ika semua image dijadikan training). Sedangkanpada LDA kita akan memiliki 12 dms, masing-masing terdiri dari l0 buah image training. Matrix scatter dalam kelas ^S" , dan mnrix scatter antar kelas .S" dihitung dengan persamaan4 dan 5 di atas. Dengan 2 informasi
Proceedings, Komputer dan Sistem Intelijen (KOMMIT 2002)
Auditorium UniversitasGunadarma,Jakarta 2l -22 Agustus2002 mahix scatter ini maka dihitung covariance matrix C (persamaan 8) lantas dicari eigen value dan eigen vector dari matrix C tersebut Selanjutnya eigen vector ini digunakan untuk transformasi feature PCA kedalarn benhrk feature LDA6. Mencari feature LDA Feature LDA dicari dengan rumusan yang sama dengan feature PCA sebagai berikut: Lt \r
fn, =IF, - u*r) xv*n
(ls)
t-l
PENGENALAN DENGAI\ NEAREST NEIGHBOR Metode recognition yang digunakan disini aaUan neorest neighbour. Metodg -ini menghitung distanceminimurn antarafeatureimagetest dan masing-masingfeatureimagehaining. rumus. Distancedicari denganmenggunakan d
" (a,b)
=
(1 6 )
Ita, i=l
Variabel de adalah jarak antara feature a dan b dalam ruang dengan feature n dimensi, dalam ini n adalah jumlahfeatir" yangdiambil. Disini dipilih harga n dalam kisaran 10 s/d 70 dan kemudian diamati keberhasilannya. 5.
Ilasil-hasil Percobaan
Sistem dibangun menggunakan platform PC dengan penulisan program kompuE menggunakan Delphi. Sistem diuji menggunakan berbagai image database yarrg diambil menggunakankamera digital yang terdiri dan 12 orang denganmasing-masing 10 image. Sistem juga diuji menggunakan Yale faces database yang terdiri dari 14 orang dengm masingmasing 9 image. Size image adalah 100xi00 pixel. Jumlah feature hasil reduksi dicobl dalam range l0 sampai 70 buah. Metode pengenalan pola menggunakan nearest neighba sederhanadan dihasilkan recogntion rate antara 80-90% denganberbagai variasi penambahannoisc dan oklusi. Tampilan program yang dibuat adalah seperti gambar 4, yang secaraumum terdiri dari 2 modrd yaitu modul tiaining dan modul testing. Modul training menghasilkan parameter digenvector dm image rata-rztabaik untuk PCA maupun LDA. Beberapatest yang telah dilakukan menunjukkan hasil recognition rate seperti bida dilihat padr tableberikut ini : 'abel I
rcn Rate
Datfiba$e
Itccoenition ltare
73 V"
I'CA + LDA 48*/" 68% 78%
_r8% 95 +L
6e% e0q6
PC,\ Onlv 13 orang @ l0 irnnge nrultipose Yale Face,\ 14 orang @ 9 inrage muhi e-rnre-ssion
6 ima.qetrainitre-4 inraeete$t ? imsqeuainine. J imaeetst I inraqetrainins, 2 imaqetest trrnaeetraini ne bervariasi 6 irnaectrainine. l maqet6l ? inrageuaining 2 inragetest
4& ok
6S9t
96Yr
1000/!
Gambar 4. ScreenShot Tampilan Program. jumlah Secaraumum kombinasi pCA+LDA memberikan hasil yang lebih baik, bahkan dengan feature yang lebih sedikipun. Pengujian dengan menggunakan tambahan noise tidak banyak Uerpengaruhpada recognilion rate di atas. Noise dibuat dengan bantuan Adobe Photoshop 7'0, dalam hal ini menggunakanfilter add noise danripple distortion'
ffiffiffi
ffiffi&&
Ga.mbar5. PenambahanNoise pada TestImage.
6.
Kesimpulan
Dari hasil percobaan ternyata secara umum bila variasi image training cukup tinggi akan memberikan kontribusi yang {misalnya: iluminasi dan ekspresi)maka penggunaanPCA+LDA tinggi. bahkan denganjumlih feature yang sedikit PCA+LDA memberikan hasil yang lebih baik Uitl-dibangdingkandenganpenggunaanPCA saja.Pengambilanjumlahpature yarlg dihitung harus dipertimbangkan.Bila terlalu sedikit atau terlalu banyak akan menurunkan recognition percentage. lumlahfeatire yangbenar-benaroptimal bisa didapatkandenganmelakukan eksperimenberulangulang. Oari eksperimenyang telah dilakukan, jumlah feature yang optimal beradadi antara 30 - 60 untuk database dengan 12 otang, masing-masing 8 image training, dengan recognition rate maksimum 78 Yo, danantara 50 - t0 unt.tk YaIeFaces Database, masing-masing7 image training, denganrecognition rate maksimum 100 %. Metode pengenalanpola perlu dikembangkan lebih lanjut misalnya menggunakan neural networks atau metode-metodestatistik lainnya seperti support vector machine misalnya.
7.
ttl TzJ
Daftar Pustaka R. Chellappa,C. Wilson, and S. Sirohey, "Human and machine recognition: A survey," Proceediigs of the IEEE, vol. 83, no. 5, pp. 705--740,1995' M. Turk and A. Pentland,"Eigenfaces for recognition." Journal of Cognitive Neuroscience, Vol. 3, pp. 71-86,1991.
A-124
t3l t4l t5l t6l
(KOMMIT 2002) Proceedings,Komputer dan Sistem Intelijen Auditorium
K.EtemadandR.Chellappa,..DiscriminantAnalysisforRecognitionofHumanFace Aug' 1997' pp'1724-1733'
i' oflm-e-rica JournalplOititrt Society Images," Recognition fisherfaces: D{:5lt;g#i'Pig:1f'a:"s"vs' and J-P.Hespanha" P.N.Belhumeur, 1997' July 7' t'9'No' TTins"eeM!' usingclassspecificu;;;t"J"; tion"' IEEE c, in" en Y* of scientificcomputing'second in necrpes press,william H.,et. al.,i,{umericat 1995' UniversityPress' Edition,Cambridge: CamUriOge University for{y i*aol Learntng.Oxford : Oxford foggio, f-o-"ro Nayar,ShreeK. una Press,1996.
