TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol. 14, No. 1, April 2015, pp. 123 ~ 1 2 9   DOI: 10.115 9 1 /telkomni ka. v 14i1.725 7          123     Re cei v ed  De cem ber 2 9 , 2014; Re vi sed  F ebruary 20,  2015; Accept ed March 1 5 , 2015   Evaluation of Moving Object Detection Methods based  on General Purpose Single Board Computer       Agung  Nugr oho Jati*, Le d y a No v a mizanti, Mirsa Ba y u   Praset y o , And y  Ruhend y  Putra  Dep a rtment of Comp uter Engi neer ing, Sch o o l  of  Electrical E ngi neer in g, T e l k om Univ ersit y Jl.  T e lekomu ni kasi T e rusan Buah Batu, Ba n dun g, Indon esi a  402 57, Ph. + 622 2-75 64 10 8   *Corres p o ndi n g  author, e-ma i l : agun gn j@tel k omun iversit y . a c.id       A b st r a ct   RGA and SKD A are tw o different methods w h ich ca n be us ed to detect th e obj ect in i m a ge bas e d   process i ng. In  order to su p port the  movi ng surv eil l anc e ca mera sys tem w h ich  pr opos ed i n  T e l k o m   Univers i ty, RGA and SKDA h a ve tested to b e  review ed  w h i c h mor e  reli abl e to be impl emented i n  a sing l e   boar d co mpute r . In this  pap er, w ill b e   discuss ed  abo ut i m ple m e n tatio n  a n d   testing  of tw o d i fferent  meth od s   of obj ect detect i on us in g back g rou nds  su btra ction. For i m pl ementati on,  e a c h of the m  w ill  be co mbin ed w i th   Extende d K a l m an F ilt er i n  a  R a spb e rry Pi. T h e p a ra meter  w h ich  hav e teste d  ar me mory  and  CPU  usa g e ,   and syste m  uti l i z a t io n. The r e sult sh ow s that RGA is  mor e  rel i ab le th an  SKDA to i m pl emente d  i n  S B C   because of les s  CPU usag e and system  utiliz a tion.      Ke y w ords : ru nni ng  gauss i a n  avera ge ( R GA), sequ entia ke rne l   d ensity appr oxi m ati on (SKDA),  exten d e d   kal m a n  filter, singl e bo ard co mp uter (SBC), Rasp berry Pi         Copy right  ©  2015 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  The stu d y of obje c t detecti on ba sed  on i m age p r o c e s sing i s  the int e re sting  way until this  time, especi a lly in the im p l ementation.  Many   meth o d s have mod e led and   dev elope b e fore,  tried to be im plemente d  in  many syste m . But  there are ma ny co nstrai nts in e m bedd ed sy stem  impleme n tation. In an em bedd ed sy ste m  su ch a s  si ngle bo ard compute r  (SB C ), the r e’s l a ck  processor  with a limited m e mory capaci ty. Besides , limited power also will be  a constraint in  impleme n tation.  Ra spb e rry Pi as a SB C has  a sma ll size an comp act fo r embed ded  system  impleme n tation [1]. As a comp en satio n , it can’t be  upgrade d b y  bigger m e mory capa city or  highe r processor. So,  whe n  som eon e try to im pleme n t a com putin g mechani sm  onto SBC, they  must   con s id e r  r e s our ce s  li mit a t i on.  A s   we  kno w , the   impleme n tation of  sign al p r ocessin g  n e eds  much  en oug h re so urce s i n  a  comp uter. So, in  this  pape will be  evaluated  a n  implem enta t ion  usin g SBC. What can be  happe ned  whe n  we mo ve the comp licated te chni que s to limited  resou r ced co mputer.   Last ye ar, p r opo sed  a m o ving  surveill ance  came ra  in Tel k o m   University for high er  reliability in  order to monitor  indoor building [15]. Th us system   consi s ts  of camera  and SBC  whi c ca n m o ve follo w th e hu man  mo vement. Con s ide r  th e limi t ation of SB C, mu st b e  f ound   best  method  with  high  a c curay  but  still manag ed  by a  sm all si ze  memo ry. Beside s, t he  processi ng time still can be tolerated.     There are two kin d  of mai n  pro c e s s in  the sy stem.  The first is o b ject d e tectio n. Many  method s a r e  develop ed i n  this  way.  Most of  th e m  use b a ckg r oun sub s traction  techni que s,  su ch a s  Ru n n ing Ga ussia n  Average,  Tempo r al  M edian Filte r , Mixture of Gaussia n , Kernel  Den s ity Estimation, Sequ ential Kern el  Den s ity Ap p r oximation, a nd many mo re [2-4]. in this  pape r, will be  only discussed abo ut RG A and SKDA.  We o n ly tried  to impleme n t RGA a nd SK DA and  evalu a te them b e cause RGA is  said  as  a simple alg o r ithm with an  acce ptable a c cu ra cy and  only need s le ss me mory consumption [ 5 ].  SKDA, is more complex al gorithm  but has hi gh accu racy but  still needs lower time complexit y  to   be p r o c e s se d [6]. In the  end, you  ca n se e the  co nclu sio n , wh ere i s  fitter t han oth e r to  be   impleme n ted in  SBC.  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 14, No. 1, April 2015 :  123 – 12 124 The  se con d   pro c e s s is m o vement p r e d iction. Exten ded Kal m an   Filter  (EKF) i s  u s e d  a s   an algo rithm for pre d ictin g  the movement  [7].  The output from SKDA or RGA, proce s sed in EKF  to produ ce th e dire ction. And then, SBC will comm an d the came ra  to move dire ctly to  the obje c t.  The p r esenta t ion is organi zed a s  follo w: in t he se co nd se ction,  will be de scrib ed the metho d   whi c h is im plemented i n  SBC. In the third  section, we’ll discuss  about the resul t  of  impleme n tation, given the analysi s  an d evaluat ion. And the last, c oncl u si on s are given.      2. Rese arch  Metho d   2.1. Running  Gaussian  Av erage (RGA)  Run n ing  Gau ssi an Averag e (RGA) i s   o ne of  ma ny method in b a cg rou nd su bstra c tion  [8]. This met hod  can b e  u s ed to d e tect  the obje c t, static or  dynam ic. RGA i s  al so calle d a s  1-G  (One  Gau s sian) [2]. In RG A, backgro un d pixel model ed as G a u ssi an Di stributio n (µ, ), wh ere:   μ s ,t   : mean point of each pixel  and time;  s ,t   : covarian ce  matrix of each pixel and time [5].  Covari an ce  matrix value s  depen d on  noise whi c h i s  contain ed  by the image . Highe noise  will produces higher covari an ce m a trix too. In the other  wo rds, higher noi se in the im age  will also produce hi ghe r temporal gradi ent  I s, t −μ s, t , so the p i xel can b e  said as m o vin g   pixel.  The mea n  an d covari an ce  are dyna mic  values, an d can be up date d  by the formulas:     μ s ,t + 1 = ( 1 −α ) . μ s ,t + α .I s ,t         ( 1 )     s, t + 1 = ( 1 −α ) . s, t + α . ( I s, t −μ s, t )( I s, t −μ s, t ) T       ( 2 )     In SBC impl ementation,  covari an ce  matrix  can b e  optimi z ed   by cal c ulate   only the   diago nal of t he mat r ix. Beca use in  ge neral,  cova ria n ce  matrix  consi s t of 3x3  matrix. Besi des,   can be u s e d  spatial agre gation as li ke  as morp hol o g ical filter to make b e tter perfo rman ce  of  backg rou nd substractio n  techni que [2].    2.2. Sequential Kernel De nsit y  Approximation  In Seque ntial  Kern el Den s i t y Approxima t ion (SKDA )   method, m e a n -shift vecto r   is u s e d   to track the gradient   whi c h can  detect  main m odes  from pdf (probability  densit y  function) ti me  from data sa mple by minimal set assu mption direct l y  [8]. SKDA u s e s  Gau s sian  Kernel, note d  by  x i  (i = 1,…,n), where:  x i   : Gaussian m ean value;   π   : variance of  covari an ce d x d related wit h  Gau ssi an [4].  The finction from den sity point define a s    / | | / ex p , ,         (3)     Whe r e,     , ,           ( 4 )     SKDA is opti m ized  from  K e rnel  Den s ity Estimation  (KDE).  Whe r e  sa mple f r am e taken  pro c e ss i s   co mpre ssed  so  time pro c e s in more effici ent. This i s  h appe ned  because le ss fra m is se nt to be pro c e s sed, so the comp utation is lee s  complexity [8].     2.3. Extende d Kalman Filter   Extended Kal m an Filter  (E KF) is a  set  of  f unction whi c h a r e u s ed to e s timate cu rrent  system state and co rre ct  t hem  by a s e d   on p r eviou s   state. EKF uses t w cal c ul ation pa ram e ter,  they are pri o r state and po sterio r st ate [ 7 , 9]. You can see a s  follo ws:   Prior st ate cal c ulatio n given  as:  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Evaluatio n of Movin g  Obje ct Detection M e thod s ba sed  on Gene ral  (Agun g Nu groh o Jati 125  ,   ,             ( 5 )     Posteri o r State Cal c ulation  given as:                 ( 6 )     Whe r e K is K a lman gai n gi ven belo w    Σ  Σ           ( 7 )     And h(X) i s  a cal c ulatio n function a s  follo ws:         ̅         ( 8 )     : covaria n ce  erro r, whe r can b e  cal c ul ate by:    Σ  Σ  R          ( 9 )     Σ  K H Σ          ( 1 0 )     &  F : calcul ation matrix, cal c ulate by Jaco bian b e lo w:    h ( x t ,x t 1 ) x t 1 for  H          ( 1 1 )     f ( x t ,x t 1 ) ́ x t 1  for  F           (12 )     Q: calculation  erro r.     From tho s e f o rmul as,  is  defined a s  id entity matrix and R  i s  defin ed as  cal c ul ation erro r.  Dynami c  syst em can be ta ken by repl acing value of  z t be  x t 1 . Those techniqu e optimize s  the   dire ction of camera dete c tion wh en there are mo re th an one o b je ct exist.    2.4. Object  Mov e ment Model  Obje ct move ment i s  mo deled  by a   linear move ment. Gotte n by  cal c ula t ing the   differen c e of curre n t frame  coordinate a nd prev io us o ne. So, the model given a s  follows:       ∆ ,  ;          ( 1 3 )       ∆ ,  ;          ( 1 4 )     Whe r x , is a hori z ontal axi s , y is ve rtical  axis, and t is the time.    2.5. Raspb e r r y  Pi Model B  As  a SB C, we us Ras p berry Pi  model B.  Ra spb e rry Pi use s  So C fro m  Broa dcom m   BCM28 35  an d con s ist  of  ARM11  70 MHz p r o c e s sor, 5 12 MB   RAM, an G P U Vide ocore IV.  This SBC u s e s  SDCard for  booting  seq u ence and  storage sy stem [10, 11].    2.6. Ev aluation Crite r ia   There a r e  two ki nd  of eval uati on  criteria s. Fi rst  criteri a  is related  with ea ch  ba ckgrou n d   sub s tra c tion   method s. Fo r RGA, the p a ram e ters  a r e learning  ra te (a)  and  d e viation sta n dart  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 14, No. 1, April 2015 :  123 – 12 126 con s tant (k) [5, 8]. And in  SKDA, they  are data vari ances ( ) and  ( threshold ) [2, 12]. Sec o nd  crite r ia, whi c h are  wante d  to kno w  to see p e rf o r ma nce s  of impl ementation i n  SBC. They are   inclu d ing me mory and  CPU usage,  an d  system utilization.        Figure 1. Ra spberry Pi model B [8]      3. Results a nd Analy s is  3.1. Sy stem  Design   System hard w are co nsi s of came ra, SBC Ra spb e rry Pi, and servo motor for  dire cting   came ra to th e obje c t. First, system has to detec t the  object by RGA or SKDA. If there are  any  movement of  the obj ect,  system  will f o llow that   m o vement.  In order  to sm ooth  the system   movement, E x tended Kalm an Filter is i m plemente d . In  the sim p le  way, system  d e scrib ed  by this   picture belo w   Ob j e c t   De t e c t io n (u s i n g   RG A   or   SK D A ) Mo v e m e n t   Pr e d i c t i o n (us i ng   Ex t e n d e d   K a l man   F ilt e r ) Ca m e r a   Mo v e m e n t Up d a t e   Im ag e Ca p t u r e d   vi d e o   fr o m   ca m e r a Mo t o r   co n t r o l   Figure 2. System Impleme n tation Sche me      3.2. RGA a n d SKD A  Par a m e ter s  An a l y s is  As explained  before, SKDA has two import ant pa ra meters. They are varian ce  ( )  a nd  threshold  (t).  We’ve alre a d y tested im plementat io n  of SKDA as a backg roun d sub s tractio n  in   some of  scen ario s. The re sults are d e scribed bel ow.           Figure 2. SKDA Pre c isio n Values  Dep e n ds o n  Threshold an d Vari ance     0 0. 1 0. 2 0. 3 0. 4 0. 5 0. 6 recall / p recissio n Thre shold sigm a   2 sigm a   4 sigm a   6 sigm a   8 Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Evaluatio n of Movin g  Obje ct Detection M e thod s ba sed  on Gene ral  (Agun g Nu groh o Jati 127 Based  on  th e test,  optim al value  of t he p r e c isi o n   of the  syste m  are h app e ned  wh en   varian ce  and th re shol d 1e -5. So,  that value  will be  used  for the im p l ementation   and   perfo rman ce testing.   RGA also uses 2 paramet ers, they are l earni ng rate  and thre sh old .  We’ve try to  chang the values of  para m eters in  orde r to find optimal  syste m . The re sult is de scribe d as follo ws.           Figure 3. RG A Preci s ion V a lue s  De pen ds on L e arnin g  Rate an d Deviation Standart       Optimal  pre c i s ion  is a c hiev ed  whe n  a  se t as  0.6 a n d    t 1. Based  on  the g r a phi c,  highe r   threshold  will make preci s i on less and becom e  un -optimal. This is  also happened for the higher  a value.    3.3. EKF Parameter T esti ng  EKF is used t o  pre d ict the  next moveme nt  of object.  EKF perform ance dep e nd s on the  Q (covaria nce) pa ram e ter. In this rese arch, we’ve t r ied  some va rian ce s of Q  value and t he  result is de scribed in the fi gure b e lo w.        (a)     (b)     Figure 4. (a)  amount of tru e  predi ction; (b) “spe ed” of  predi ction       From the graphi cs ab ove ,  shown that  higher  cova rian ce will i m pact the “speed ” of  predi ction to  become le ss.  For impleme n tation, Q  is set as 0.1 ca use it has hi g hest “spe ed ” and  still tolerated  “true” predi ction. Q=0  can’t  be us ed because will give many “jump” processes.     3.4. SBC Per f omanc e  An aly s is  SBC based system perfo rmance can b e  see n  by  an alyzing the m e mory an d CPU usage   [13, 14], al so the  system   utilizat ion. T h is test is proposed to  know  whi c h technique is more   comp atible to  be impleme n t ed in SBC.     Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 14, No. 1, April 2015 :  123 – 12 128     Figure 5. RG A and SKDA Comp utation       Based  on th e figure  abov e, sho w n th a t  SKDA use  arroun d 10%  CPU  re sou r ce mo re  than RGA. RGA uses CPU  arro und   73.45%   av erag wh en  is exe c ute d . And SK DA, use   averag e 8 8 .2 4% du ring  execute d  by th e sy stem.  De spite  RGA  ha s le ss u s a ge  of CPU, it  uses  large a m ou nt of memory ca pacity duri ng  the pr o c e ss. I t ’s described i n  the figure b e low.           Figure 6. RG A and SKDA Memory Usa g e       RGA uses m o re mem o ry reso urce be ca use  it need more me mory space for d e viation  stand art of e a ch  pixel (u sed 2 fram es  of ev ery pro c ess). While  SKDA only u s e s  mem o ry  for   putting 2 fram es in every p r oce s s.        (a)     (b)     Figure 7. System Utilizat ion (a)  RGA; (b) SKDA  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Evaluatio n of Movin g  Obje ct Detection M e thod s ba sed  on Gene ral  (Agun g Nu groh o Jati 129 From  Figu re   7 ab ove,  we  can  say that  RGA i s   more  “healthy  tha n  SKDA. Th system i s   alway s  in hig h  utilization  when sy stem i m plem e n t SKDA as b a ckg r ound  sub s tra c tion techniq ue.  SKDA has le ss u s e r  time but highe r idl e  time of the  pro c e s sor tha n  RGA. It’s happe ned be cause   by using SKDA as a ba ckg ound  sub s tra c tion techniq ue, system m o re often  sen d  requ est dat a to   the hard w a r level.      4. Conclusio n   Based  o n  the  implem entati on, testin g, a nd a nalysi s  can  con s tructe d some  con c l u sio n of the  study.  As a  limited  reso ur ce s co mputer, sin g l e   bo ard com put er can’t p r oce s s a  hig h   level  sign al processing  as  realti me. The r e h a ve bee n tested two  kind  of backg rou nd sub s tra c tio n   techni que  co mbined  by EKF in a SBC. Both RGA and SKDA can be u s ed  as a b a ckg r o und   sub s tratio n te chni que to d e t ect the movi ng obje c in a  SBC. But it’s requi red m o re than 25 6 MB  memory  cap a c ity. RGA ind eed, nee ds  m o re m e mo ry usa ge (arrou nd 0.1%) tha n  SKDA to st ore  deviation of e a ch pixel for  every frame. In the im plem entation, use d  2 frame s  of captu r ed vide o.  Ho wever, RG A uses le ss  reso urce of CPU in the pro c e ss than SK DA. RGA just  needs   in average  7 3 .45% of CP U resource  while SKD A n eed s in  average 8 8 .24%.  Becau s e  of that,  SKDA needs more time processing . A nd it  also infl uence the  sy stem  utilizati on. Based on the  study, known  that SKDA will make  sy stem always in high utilization.   All of the results of this st udy sho w n t hat  RGA is  more reliabl e  to be implemented in   SBC, esp e cia lly Rasp be rry  Pi. Still and all, the pro c e ssi ng time n e eds to b e  in crea sed  more. It  can b e  hap pe ned by repl ace the SBC with better CP U spe ed an d hi gher m e mo ry capa city.  In the further stage of stu d y, the result   from this st udy can  be  expand ed to try other  backg rou nd substractio n  m e thod s. And also in  thext rese arche s , can be implem ented directly  as  a surveil a n c e  came ra to follow the hum a n  movement.       Referen ces   [1]  T he Rapsberr y  Pi F oundati on:  http:// w w w . r a s pberr y p i .org/. October 30th, 201 3.  [2]  Benez eth Y, J odo in PM, Em ile B,  Laur ent  H,  Rose nb erg e r C. Com par ative Stu d y of  Backgro un d   Subtraction Algorithm.  Journ a l  of Electronic Ima g i n g . 20 10: 1-30.   [3]  T s ai DM, Lai  SC. Indepen dent Com pon ent Anal ys is-B ased Back gro und Su btractio n for Indoo r   Surveillance.  IEEE Transaction on  I m age P r ocessing.  20 0 9 ; 18(1): 15 8-1 67.   [4]  Madd ale na  L, Petrosin o A.  A Self-Orga n izin g Ap pro a c h to Back groun d Su btraction for V i su al   Surveil l a n ce A pplic atio ns.  IEEE Transactio n  on Image Pr ocessi ng.  20 08 ; 17(7): 116 8-1 177.   [5]  C W r en, A Az arba ye ja ni, T  Darel l , AP Pe ntlan d . Pfind e r :  Real T i me T r ackin g  of the  Huma n Bo d y .   IEEE Trans. on Pattern Analys is and Mac h in e  Intellig enc e . 1997; 19( 7): 780 -785.   [6] B  Han  DC.  S equ enti a l Ke mel D ensity A p proxi m ati on t h roug h Mo de P r opa gatio n: Ap plicati ons t o   Backgro un d Mode lin g . Proce edi ngs of Asia n Confer enc e  . 200 4.  [7]  Hua ng S. Und e rstand ing E x t end ed Ka lman  F ilt er - Part III:  Exte nde d Kalm an F ilter. 201 0.   [8] Piccardi  M.  B a ckgro und  Su btractionT ec hn iqu e s: a  Revi ew . IEEE Internationa l Conferenc e o n   S y stems, Man  and C y b e rn atic s. 2004: 30 99- 310 4.  [9]  Ribe i ro n M I. Kalma n  and E x t end ed Ka lman  F ilter: Conce p t, Derivati on, an d Properti es. 2004.   [10]  T he Rapsberr y  Pi F oun dati on.  F A Qs |  Raps berry Pi . October 30th, 2013. Ra p s berr y pi. o rg :   http:// w w w . ras pberr y p i .org/fa qs.  [11]  T he Raspberr y  Pi F o u n d a ti on.  Ab ou t u s  | R a sp be rry Pi . October 30t h, 201 3. Rasp berr y  pi  org:   http:// w w w . ras pberr y p i .org/a b out.  [12] Urbac h ER, W i lkinso n MH. Ef ficient 2- D Gra y sca le  M o rp hol ogic a l T r ansfor m ations W i th   Arbitrar y F l at   Structuring El e m ents.  IEEE Tr ansaction on Im age Proc essing.  200 8; 17(1) : 1-7.  [13]  IBM. Linu x Per f ormance a nd  T uning Guid eli nes .  Ne w  York:  IBM Group. 2004.   [14]  StrongMa il S y s t em. Extreme L i nu x Perform a n c e T uning an d Monitori ng StrongM ail S y ste m [15]  And y  R u h e n d y , Agun g NJ,  Le d y a N.  S i ste m   Movin g  Surv eil l ance  Ca mera  Berbas is Se qu entia l Ker n e l   Density Ap prox imatio n da n Extende d Kal m an  F ilter . Seminar  Nasio nal T e kn olo g i T e rapan.  201 4: 304- 307.         Evaluation Warning : The document was created with Spire.PDF for Python.