TELKOM NIKA , Vol.13, No .3, Septembe r 2015, pp. 9 49~954   ISSN: 1693-6 930,  accredited  A  by DIKTI, De cree No: 58/DIK T I/Kep/2013   DOI :  10.12928/TELKOMNIKA.v13i3.713    949      Re cei v ed O c t ober 7, 20 14;  Revi se d Apri l 27, 2015; Accepte d  May 1 3 , 2015   Implementation of K-Nearest Neighbors Face  Recognition on Low-power Processor       Eko Setia w a n 1 , Adharul Muttaqin 2   Program of Informatio n  T e chnol og y a nd Co mputer Scie nc e, Bra w ij a y a U n iversit y ,   Veteran R o a d  No. 8 Mala ng, Ja w a  T i mur,  Indon esia  651 45 T e lp/F ax 03 4 1  - 577 91 1   *Corres p o ndi n g  author, e-ma i l : ekosetia w a n @ ub.ac.i d 1 , adharu l @u b.ac.id 2       A b st r a ct   Face rec ognition  is one  of   early  detection  in s e curit y   system . A u tom a tion enc ourages  imple m entati o n  of fac e  rec o gniti on  in  s m a ll  and  co m pac t devic es. Mo st of face  rec ogn ition  res e a r ch   focused o n ly  on its accura cy and perfor m e d  on h i gh- spee d co mput er. F a ce recogniti on that is   i m p l eme n t ed  on  l o w-co st p r oce sso r, such  as ARM proc essor, ne eds  prop er al gorith m . Our rese ar c h   investi gate  K- Near est Ne ig h bor (K NN)  alg o rith in r e co gni z i n g  face  o n  ARM  proc es sor. T h is r e se arch   soug ht best k- valu e to cre a te  prop er face r e cogn iti on w i th  l o w - pow er proc essor. T he pr o pose d  al gor ith m   w a s tested on three d a tasets that w e re Olivet ti Re searc h  La boratory (ORL) ,  Yaleface a nd  MUCT . OpenC V   w a s chosen  a s  ma in cor e  i m a ge pr ocess i ng li brary,  du e to its hig h -s pee d. Propos e d  alg o rith m w a imple m ente d  o n  ARM11 7 0 0 M H z . 10-fo ld  cross-vali dati o n show ed that  KNN face recogn ition d e tect ed  91.5%  face w i t h  k= 1. Overal ex per iment s h ow ed that  prop osed  al gorith m  detecte d face   on 2. 66 s  on  A R process o r.    Ke y w ords : face recog n itio n, K-Near est Nei ghb ors, ARM processor      Copy right  ©  2015 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  Smart buildi n g be come s t op issu es in  last  y ear s.   S o me re se ar che s   kee p  d o ing t o   prop ose  b e tter sma r buil d ing system. A  sma r build ing shoul d b e  able  to mo dify environm ent   according to  the o c cupa nt comm and. Fi rst, the sy st e m  must id enti f y who is it s o c cupa nt. Nat u ral  identificatio n techni que i s  face  re cog n ition that  gives better soluti on. Applying  face recogniti on,   system could identify  the  occupa nt  witho u t disturbi ng the other p e o p le.  For yea r s, fa ce recognitio n  be come to p issu e s  in  rese arch p a p e r. Several t e ch niqu es  were appli e d  to propo se  better re co gnition. Ch a nging in po se, expressio n  variation s  and   differen c e s  in  the position  of the light give difficulty to  resolve in face recognitio n . Basically, face   recognitio n   can b e  ap pro a ch ed  with f a cial  biom etric featu r e s  o r  stati s tical   method. F a ci al  biometri c re cognition  te ch nique offers high  a c curacy  with long   cal c ulatio n. Hen c e,  statistical  approa che s   offer sp eed  calcul ation. Due to the  sp eed, a stati s t i cal ap proa ch  is appli ed m o re  widely than f a cial bi ometri c [1]. Princip a l Comp one n t  Analysis (P CA) an d Line ar Di scrimin a n Analysis  (L DA) are two po pular  statis tical approa che s  in face  re co gnition.   Several stu d i e s ha d sh o w n that PCA (k no wn a s  Eigenface )   and L D A (known as  Fishe r fa ce)  method  had   high  accu ra cy in fa ce  re co gnition [2]. B o th of th ese  method cal c ulated  eigenvalu e of face imag e. Calculatio n of ei genval ues requi red  long step s. Several meth ods  were propo se d to improve  them in accu racy and  sp ee d. Arif improv ed the Fishe r face efficie n cy  by cal c ul ate it  in two-dimen s ion.  The  imp r ovem e n t gav e go od  re sult  in 10 0% a c cu racy  [3]. Two- dimen s ion  ca lculatio n take s more  step s with time-co s t con s eq uen ce. Wijaya co mbined h o list i feature an d linear di scrimi nant analy s is  to redu ce  the  training time  and keep the  accuracy [4].   Ho wever, th e previou s   works we re  applie d on compute r  equi pped with hi gh-p o wer  pro c e s sor. Si nce  en ergy  conservation  i s  o ne  of key i s sue s  in  sma r t buildi ng  re search, lo w po wer  pro c e s sor be come s intere sting to pic to  be inve stigat ed a nd  evalu a ted of  face reco gnition. B a se d   on Yong  et a l  survey [2],  K Nea r e s t Neighb or  (KNN) pl aced thi r d ran k  after  PCA and  LDA on  accuracy a n d  KNN pla c e d  first ran k  o n  pro c e ssi ng speed. In this  study, we int e re st to mea s ure   how suitable  KNN appli ed in low power pr oce s sor compa r e with PCA/Eigenface a n d   LDA/Fisherfa ce.     Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 9 30   TELKOM NIKA   Vol. 13, No. 3, September 20 15 :  949 – 954   950 2. K-Near est  Neighbo r   K-Ne are s t Neighb or (K NN) i s  data cl assifica tio n  method that  can b e  used  as face   recognitio n   method. Ea ch pixel in fa ce re pre s e n ts uniqu e info rmation. Thi s   pape r recogn ized  f a ce b a s ed o n  ea ch pix e cla ssif i cat i on.  Face  wa s d e t e rmin ed by  most  cl as s r e sult e d  in ea ch   pixel cla s sification. In recognition, pixe l matrix of fa ce im age  sh ould b e  resh ape into  vect or  before  cla ssifi cation. The p r opo sed KNN  face re co gniti on algo rithm i s  de scribe d a s  follows:   1.  Modify dimen s ion s  of M - ro w an N-colo mn  face matrix (M x N) int o  fac e  trans p ose  vec t or  (1 x MN 2 .   A r r a g e  e a c h  f a c e  v e c t o r  i n t o  m a t r i x  f o r m  ( K  x  M N )  w i t h  K  i s  n u m b e r  o f  t r a i n i n g  f a c e   image s. Each ro w rep r e s ents a si ngle  image an d each col u mn  would  rep r e s ent same pi xels  positio n in ea ch face imag e.   3.  Modify testing image matri x  into face tra n sp ose vecto r , as traini ng i m age s  (1 x M N ).    4.  Cal c ulate the  Eucluide an Dista n ce (d)  of  each colu mn (i) in test ing image (x ) to  each col u mn  (i) in traini ng i m age (y).          5.  Determine  cl assificatio n  b a se d on  the  sh o r t e st   dist a n ce  of  w hole  colu mn in  e a c h   row.   6.  Determine fa ce re co gnitio n  based on th e k nea r e s t neighb or an d its dista n ce.      St a r t C a pt ur e f r o m  c a m e r a L B P - cascad e  da n H aar - c ascad e   fa c e  d e te c t i o n C o lle c t  r e f e r e n c e   fa c e  i m a g e F o re v e r l o o p D i m e n s i o n t r a n sf or m a t i on   o f   r e fe r e n c e  fa c e   i m a g e ( 1   x  M N )   V e ct or  D i m e nsi on  T r ansf o r m a t i o n D i s t a n ce  ca l c u l a t i o n F i nd  k - ne ar est  n e i g h b o r Fin i s h Fa c e   re c o g n i t i o n   re s u l t   Figure 1. Face Re cog n ition  Flowcha r     3. Implementation   The p r o p o s e d  metho d   was im pleme n t ed with  Op e n CV lib ra ry [6] in  C lan g uage  to   ensure  fast i m age  pro c e s sing.  Ra spb e rry Pi  wh i c wa s eq uipe with ARM11  700M Hz core , wa sele cted to  b e  main  pro c essing  unit. Overall al go ri thm that wa s impleme n te d in video fa ce  recognitio n   system, wa sho w n  in Fi g u re  1. Mai n   pro c e s s reco gnized fa ce   contin uou sly  b y   c a p t ur in g a pic t u r e fr om a t ta c h ed   w e bca m  pe r o d i ca lly. C a p t ur e d  ima g e  wa s pre - pr oc es se d   b y   applying fa ce  detection. Haar-cas ca de  wa s appli ed  due to its ro b u stne ss in face dete c tion.  Pre- pro c e s sed im age  woul d be  pro c e s sed  b y  propo se d f a ce  dete c tion  method. Th e  whol e p r oce ss  woul d be re p eated so as t o  prod uce a video-ba s ed fa ce re co gnitio n .       4. Results a nd Discu ssi on  Test were  condu cted  to e v aluate p e rfo r manc of p r o posed  algo rithm. Te sts carried  out   with thre e face dataset whi c h a r e O R L [ 7 ], Yaleface [8] and MUCT  [9] dataset. Before ap plying   as traini ng d a taset, every  images  was  applie d face  detectio n  and  equalized in  same si ze. The  result of p r e p r ocessin g   sh owe d  that  so me faces co uld n o t be  u s ed a s   data s e t. The 29 O R L   face s, 15 6 Y a lefaces and   3644  MUCT  face wo uld b e  u s ed  a s  trai ning  and te sti n g d a ta. Figu re   2 sho w s the overall ima g e s  that are u s e d  in training a n d testing.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 9 30       Im plem entation of K-Ne arest Nei ghb ors Fa ce  Reco gnition on L o w -p ower… (E ko Setiawan 951     Figure 2. ATT Face  Databa se [7]          Figure 3. k-F o ld Cross Val i dation        Firs t tes t ing  was  to find the k values   that  pro d u c ed   high  accu ra cy. Second  testing would  comp are accura cy and e x ecution tim e  of  prop osed metho d  with co mmo n Eigenfa c e  and   Fishe r fa se. Fi nal testin g would o b se rve  time execut io n of co ntinuo us fa ce recog n ition sy stem  in  low-l e vel processor.      Table 1. Cro s s Validation o n  ORL d a taset  Num b er o f  10-fo ld  A ccu r a c y  (% K=1 K=3 K=5 K=7  93.3 83.3 73.3 70.0  96.7 86.7 90.0 86.7  100  90.0 90.0 86.7  93.3 86.7 86.7 83.3  96.7 93.3 86.7 86.7  93.3 86.7 80.0 76.7  79.3 72.4 65.5 69.0  93.1 89.7 75.9 79.3  86.2 79.3 82.8 82.8  10  82.8 82.8 79.3 72.4  A v e r age   91.5 85.1 81.0 79.3  Fold-1                    Fold-2                      …..                   Fold-(N-1)                     Fold-N                       :  Train i n g : T estin g Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 3, September 20 15 :  949 – 954   952 Tabel 2. KNN face accu ra cy  K Value   A v e r age A c cura c y   ( % )   ORL da taset   Y a leface dataset   MUCT dat aset  K=1 91.5  78.8  70.0  K=3 85.1  75.0  63.6  K=5 81.0  71.8  62.1  K=7 79.3  64.8  60.2      First  te sting wa s cond uct ed  in 10 -fold   Cr oss Vali d a tion. Figu re  3 sho w ed   how to  determi ne  t r ai ning and   testi ng  im age s.  A c cura cy on e a ch   fold wa s cal c ulate d T abel 1 wa d e tail  accuracy  on  each fold  in  ORL  data s et.  The  total a ccura cy was  cal c ulate d  o n  av erag e of  10 -fold.  Table 2 sho w s the re sult s of accura cy in different k v a lue on  several dataset.  Based o n  Ta ble 2, KNN d one be st accura cy  on k e qual to 1. It s howed that KNN gave  91.5% on 29 5 ORL fa ces,  78.8% on 156 Yalefa ce and 70% on  3644 M U CT face s. Enorm ous  numbe of M UCT  data s et  made th system co nf use i n  re co gnition.  K wa equ al  to 1  and  ORL  dataset woul d be use d  in next test due  to its  best re sult. The nex t phase te st wa s to comp are  the pro p o s ed  method  with Eigenface an d Fish erfa ce.  Tests  ca rri e d  out to obtai n informatio n  on  how fea s ible  the propo sed method  whe n  impl e m enting in l o w-po we r proce s sor. Te sts  con d u c ted on  compute r  wit h  Intel Core i 7 , 2.8 GHz a nd Ra spb e rry Pi with Broadcom ARM1 1,  700M Hz. Th e  accuracy an d executio n time wo uld  be  comp are d . Accura cy testi ng wa s h e ld  on   same  scena ri o of k-value  adju s tment. The final re sults of testing were sh own in Table 3 and   Table 4.       Tabel 3. Fa ce  reco gnition o n  comp uter  Me t h od  A ccu r a c y   (% )   Learni ng  require ment  Learni ng  time (s)   Recog n iti on  time (s)   Total  ti me  (s)   Eigenface 91.5  Y e s   3.935875   0.006887   3.94276   Fisherface 91.5  Y e s   2.997280   0.000540   2.99782   KNN 91.5  No  0.003689   0.00369       Tabel 4. Fa ce  reco gnition o n  low-po we r pro c e s sor.   Me t h od  A ccu r a c y   (% )   Learni ng  require ment  Learni ng  time (s)   Recog n iti on  time (s)   Total  ti me  (s)   Eigenface 91.5  Y e s   299.221   0.459   299.680   Fisherface 91.5  Y e s   234.252   0.027   234.279   KNN 91.5  No    0.152    0.152       Table  sho w ed that fa ce  reco gnition  ex ecut io n time  on  comp uter  wa s n o t mo re  than  se con d s. T a ble 4 info rmed that e x ecution ti m e  of fishe r f a ce  and  eig enface in cre a se signifi cantly into 299.7  se cond s and  234 .3 se cond s re spe c tively in low-po we r pro c e s sor. Both  of  these  pop ula r  metho d were n o t app ropriate l o w-p o we r p r o c e s sor  due to it s lon g  exe c u t ion   time. The pro posed metho d  took sh orte r time t han the eigen or fisherfa ce. This fact confirm e d   that KNN wa s p r op er fa ce  re cog n ition  method i n   lo w-p o wer processor. On ne xt  sce nari o , KNN  woul d be sele cted a s  the re cog n ition met hod.   Final test ai med to observe perform an ce of  co ntinu ous fa ce re cognition on l o w-po we pro c e s sor. E x perime n t ap plied fa ce  d e tection   by  Local Bina ry Pattern a n d  Ha ar-Ca s ca de.  Dete ction  re sult wa re cog n ize d  by K N N. Exper im en t wa s do ne  b y  sho w ing  p r i n ted te st ima g e   on onlin e ca mera. Th e camera ca ptu r ed ima ge.  Figure 4 sh ows the face detectio n   and  recognitio n  proce s s on lo w-power p r o c e s sor.     Tabel 4. CP U Load an d me mory usage.   Camera Pixe l   CPU Lo ad   (% )   Memor y  Usage   (MB)   1024 x  768   84  67.6  960 x 6 4 0   79  62.8  640 x 4 8 0   82  59.1  320 x 2 4 0   85  53.2  160 x 1 2 0   75  51.5  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Im plem entation of K-Ne arest Nei ghb ors Fa ce  Reco gnition on L o w -p ower… (E ko Setiawan 953 Tabel 5. Execution time  of  face reco gnition  Trial   Executi on time (s)   Trial   Executi on time (s)   1 2.32  16  2.73  2 2.76  17  2.70  3 2.67  18  2.66  4 2.65  19  2.70  5 2.81  20  2.61  6 2.91  21  2.61  7 2.92  22  2.67  8 2.29  23  2.42  9 2.56  24  2.28  10 2.52 25  2.85  11 2.52 26  2.79  12 2.45 27  2.71  13 2.45 28  2.95  14 2.66 29  2.85  15 2.68 30  3.00  A v e r age time (s 2.66      Experiment e v aluated CP U load a nd  memory u s a ge of contin u ous fa ce recognition o n   several ca m e ra pixel si ze. The syst em sho w  dif f erent CP U Load a nd m e mory on e a ch  resolution. Detail CPU L o ad and m e m o ry usage  wa sh own cle a r ly on Table  4. Smaller ca mera  resolution  de livered  sm all e r m e mo ry  usa ge.  CPU load  sho w n  anom aly b e twee n vari o u resolution. T he experi m e n t sho w n tha t  640 x 480 resolution g a v e optimum in CPU loa d  and  memory  u s a ge. Th re sol u tion p r od uced n o t hi g h   CPU load  a n d mem o ry  usage. Expe rim ent  also  perfo rme d  face  re co gn ition 30 time s seq uentially  and  re corded  each exe c uti on time. Based   on Tabl e 5, the average ti me of the face re cog n ition  pro c e ss  wa s 2.66 se co nd s on e m be dd ed  sy st em s.  Te s t  res u lt sho w ed t h at  K N N f a c e   re co g n ition was fe asibl e  to be i m pleme n ted  on  embed ded system s.          Figure 4. Con t inuou s face reco gnition       5. Conclusio n   The  re sea r ch con c lude d  som e  info rmations ab o u t face  re co gnition o n  l o w-po we pro c e s sor. K-Nea r e s t Neig hbor face recognition  deliv ered  be st a c curacy  91.5 %  on k=1. K N sho w e d  the faster exe c uti on time com pare d   with P C A and L D A .  Time execu t ion of KNN to   recogni ze fa ce wa s 0.152  se con d s o n  h i gh-p r o c e s sor. Face dete c ti on and recog n ition only ne ed   2.66 se co nd to re cogni ze o n  low-po we r ARM11  b a se d system . O v eral propo se d method wo rk  w e ll on  low - po w e r  pr oc es so r .  Ap pr o p r i ate  fa c e  dete c tion  on  l o w-p o we r system have  pote n tia l to boost reco gnition.       Referen ces   [1]  Rabi a J, Hami d RA. A Survey of F a ce Rec ogn ition T e chn i qu es.  Journa l of Informati on Processi ng 200 9; 5(2).  Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 3, September 20 15 :  949 – 954   954 [2]  Peter NB, Joao  PH, David JK.  Eigenfac es vs. F i sherface s: Recogn it io n  Using C l ass  Specific L i ne ar  Projecti on . 2014.  [3]  Arif M. Ne w  Modell i n g  of Modifie d  T w o Dim ens io na l F i sherface  Based F eatur e Extracti on .   T E LKOMNIKA T e leco mmunic a tion C o mputi n g Electron ics a nd Co ntrol . 20 14; 12(1): 1 15- 122.   [4]  IGPS W ija ya, K Uchim u ra,  G Koitaki.  F a ce Rec o g n i t ion Us ing  H o listic F e ature s  and  Li near   Discrimi nant A nal ysis  Simp lifi c ation.  T E LKO M NIKA T e leco mmu n icati on  Co mp uting  Ele c tronics a n d   Contro l . 201 2; 10(4): 77 1-7 8 2 .   [5]  Yong  X,  Xia o  zhao F ,  Xu el o ng L, Jia n  Y, Jane  Y, Ho ng  L, Shaoh ua T .  Data Uncerta i nt y  i n  F a c e   Reco gniti on .   IEEE Transaction on Cybernetics . 2014.   [6]  OpenCV  Dev   T eam. 2014. T he Op en CV R e ferenc e M anu al  Rel eas e 2.4. 9.0. access ed   on S eptem be r   10th 20 14.    [7]  F Samaria, A  Harter.  Para meterisati on of a  Stochastic Mo del for H u ma F a ce Identific ation . 2nd IEEE  W o rkshop o n  Appl icatio ns of Comp uter  Visi on.Saras o ta (F lorid a ). 199 4.   [8]  P Belh umeur,  J Hesp anh a, D  Kriegm an. Eig enfaces  vs. F i s herfaces: R e co gniti on Us in g C l ass Sp ecifi c   Lin ear Proj ecti on.  IEEE Transactions on Pattern An alysis and Machine Int e lligence . 19 97 : 711-72 0.  [9]  S Milborro w ,   J Morkel, F   Nicol ls. T he  MUCT  Landmarked F a ce D a tabas e.  Pattern Recog n iti o n   Associati on of South Africa . 2 010.     Evaluation Warning : The document was created with Spire.PDF for Python.