TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol.12, No.1, Jan uary 20 14 , pp. 734 ~ 7 4 0   DOI: http://dx.doi.org/10.11591/telkomni ka.v12i1.3688            734     Re cei v ed  Jun e  27, 2013; Revi sed Aug u st 12, 2013; Accepted Aug u s t 25, 2013   Target Trackin g  Feature Selection Algorithm Based on  Adaboost      Chen Yi   Sichu an Un iver sit y  of Arts and  Science, Pin g c han g, Sichu a n , PR Chin a, 6350 00   e-mail: 1 685 65 0@q q .com        A b st r a ct   W i th the d e v e lo p m ent  of i m a ge  process i ng  tec h n o lo g y  and  po pul a r i z at io n of co mp uter   techno lo gy, intelli ge nt mac h in e vision tec h n o lo gy has a  w i de ran ge of ap plicati on i n  the  med i cal,  mil i ta ry,   ind u strial and other  fie l ds.  T a rget  tracki ng  feature se lecti on a l gor ith m   is  one  of resear ch focuses  in  th e   mac h i ne i n tell i gent vis i on tec hno logy. T h ere f ore, to  desi g n  the target trac king fe ature se lectio n al gorit h m   w i th hig h   accur a cy a n d  g ood   stability  is  extr emely  nec e ssa ry. This p a p e r  prese n ts a  targ et trackin g  fe atur e   selecti on  al go rithm b a sed   on A d a boost.  It incl udes   Adab oost  alg o rith m’ s  pri n ci ple  an d A dab oost   alg o rith m' s ap p licatio n i n  vid e o  obj ect trackin g . Exper i m enta l  results sh ow  that  the pr opos ed al gor ith m  h a s   the character i s t ics of real -time ,  accuracy and  stability.      Ke y w ords : int e lli ge nt mac h i n e visio n ,   target tracking,   al gorit hm,   Ad abo ost         Copy right  ©  2014 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  Vision i s  the  most impo rt ant way for  human to p e r ce pt the foreign obj ect s  to ge t  informatio n. Giving machi ne vision fun c tions can ma ke life and p r odu ction mo re conve n ient.  Th e   human  visu a l  system  ca n qui ckly  capture  an  i m age, o b je ct recognitio n ,  and ta ke  th e   corre s p ondin g  actio n s i n   accordan ce  with the info rmation  obtai ned [1]. The  machine vi sion   make s u s e o f  input device s  su ch a s  ca mera s in stea d of eyes to get image s. Use a co mpu t er  instea d of  the  hum an  brain   for ima g e  proce s sing  in  o r de r to  a c com p lish  a  simil a r functio n   of th e   human visual  system [2]. In rec ent years, with the improvem ent  of compute r  pe rforma nce an d   the falling price of cam e ras, intelligent  machin e vision tech nolo g y is more  widely used  in   military, medi cal, indu stri al and ele c tro n i cs m anuf a c t u ring i ndu stri es. That intel ligent ma chin e   vision techn o logy  repl a c e s  the hu man eye to  distingui sh  has b e come  a trend of  the  developm ent  of prod uctio n , and targ et tracking al gor it hms i s  an im portant p a rt i n  machine vi sion  techn o logy. The tradition al target tra cki n g  algorit h m  mainly inclu d e s  continu o u s  frame differe nce  method  and  backg rou nd  removal meth od [3]. The m o tion region   detecte d by succe ssive f r a m e  differen c e  m e thod  relate s to velo city of  the ta rge t.  Whe n  the  target spee d i s   very sl ow, it  may  not be abl e to dete c t the target m o tion;  backg rou nd  removal m e th od is  sen s itive to ch ange s in  illumination a nd ba ckgro u n d , and in the ca se of inte rf eren ce, it ma y fail to detect the target [4-5].  This p ape r p r ese n ts a ta rg et tracking f e ature  sele ctio n algo rithm b a se d on Ad a boo st to   extract the ch ara c teri stics  of the target and in t he ne xt frame to find a pictu r e t hat match e s t he  cha r a c teri stics of the targ et in orde r to deter mi ne  the target lo cation, and ult i mately achie v e   target trac k i ng.      2.  The O v erall Design   The targ et tracki ng selectio n algorithm fr amework pro posed ba sed  on Adabo ost  can b e   divided into the followi ng three p a rt s:  (1) Indi cate s  the target ob ject usi ng  Ha rr featu r e s , u s e s  and Inte gral ma p me thod to  accele rate th e spe ed of op eration;   (2) Usin g Ad aboo st al gori t hm to  sele ct  the  m o st  re pre s entative   of the ta rget  obje c t  recta ngle fe a t ures  (wea k  cla ssifie r s), b a se d on t he  detectio n  rat e  of the wei ght given to  the   corre s p ondin g  value of the wea k  cla s sifier s a r e  con s tructed a s  a st rong cl assifier;   (3) The  nu mb er of  se rie s  to  form  a  stron g  cl as sif i er  c a sc ade  st r u ct u r e  ca sc ade  cl as sif i er   ca scade stru cture can  effe ctively  improv e  the detectio n  rate of cla s sificatio n .  Evaluation Warning : The document was created with Spire.PDF for Python.
    ISSN: 2302-4 046   TELKOM NIKA   TELKOM NIKA  Vol. 12, No . 1, Janua ry 2014:  734 – 7 4 0   735 Adaboo st al gorithm i s  d i vided into t he follo wing  part s . First, cal c ulate  th e targ et  cha r a c teri stic para m eters,  and the n  cal c ulate  ea ch   classifier th re shold p a ra met e r a c cording  to   the param ete r s, and  conv ert the target  feature in to the corre s po nding wea k  cla ssifie r s, train  sampl e   set to  elect th e b e st wea k   cla ssif i er a nd  cal c ul ate its  weig ht. After T time s to g ene rate  a  stron g  cla s sifier ca scad e to achieve th e pur p o se of tracki ng. Ca scade me ntio ned above i s  to   detect the im age wi ndo w i t eration  step  by step thr o u gh a wea k  cl assifier, de ci de targ et are a ,  filter the targ et area to test the wea k  target im a ge  as the targ et, then the output is 1; if it  is  determi ned t o  be n on-ta rget, the outp u t is 0. The  ov erall d e si g n  of the alg o r ithm flow  ch art is  s h ow n  in  F i gu r e  1 .           Figure 1. Overall De sig n       3.  Target Tr acking Fe atu r e Selection  Algorithm Based on  Ada boost  3.1. Adaboo st Algori t hm  Principle  Adaboo st alg o rithm' s ba si c pri n ci ple i s  that  integrat e a wea k  lea r ning  algo rith m in the  colle ction  by several iterations  i n to a  strong le arni ng  algorith m . Ad aboo st alg o rit h m is  agai nst  a  set to  train   weak cl assifie r s, an d  cla s sify the re sultin g casca d e  of  wea k  to gethe r to f o rm  a  strong  cla ssifie r . Initial wei ghts of  the sa mple s  are th e  same . In this  sam p le di strib u tio n , train  a ba sic  cla ssif i e r  h 1  ( x ),  inc r ea sing  h1  (x ) mi s c la ssif i e d   sampl e  w e ight s;   re duc e t he  co rr ect   cla ssif i cat i on   of the sample  weight s, so i t  can highli g h t  the  error  sa mples a nd ge t a new sam p le distri butio n.  Then a c cordi ng to the prin ciple s  that the less the e r ror of the weig ht is, the grea ter the weig ht is  and the  more  the erro r is,  the less the   weig ht is , ent itle h1 (x) to  a ne w weight . Unde r the  n e w   sampl e  di stri bution, ba si c  cla ssifie r  is t r ained to  ba si c cl assifier  h2  (x) an d its  weight, and  so  on ,  throug h the  T  cycl es, it  get s a  ba si c  cla s sificati o n  of T  and  its  weig ht [2]. Finally  add  up th ese  T   basi c  cl assifi er at a ce rtain   weight to ob tain the final stron g  cla s sifier.   AdaBoo st alg o rithm is d e scrib ed a s  follows:  Assu me that X is the sam p le of spa c e,  Y repre s ent s a collectio n of sample  cat egori e s  identified. He re set Y = {-1, +1}  so tha t  S = {(xj,  yj) | j = 1,2, ...,  m} is the  sa mple traini ng  set,  whe r e x j   ∈∈  X,  yj   Y .   Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 2302-4 046                          Targ et Tra cki ng Featu r e Selectio n Algorithm  Based on Adaboo st (Che n Yi)  736 A. initializes the weight s of n sample s to make Dt uniformly distribute:  n j D t 1 ) ( .     rep r e s ent s the weig ht of the sampl e   (xj, yj) assi gne d in t iteration;  B.  Let T  represe n t the number of iterat i ons. Fo r each t = 1 ... T,  based on the  sample   distrib u tion Dt, generate  sample to form the colle ct ion St. Train the cla s sifier  ht on the set  St.  Use the  cla s sifier ht to cl assify all sa mpl e s of  the  set S. Get cla ssifi er in thi s  roun d and  minimu m   error rate Ej [3];    | ) ( | 1 j j n j t j y x h E     C.  Calculate  the weig hts:  ) / 1 log( ); 1 /( j j j j a E E     D.  Update th e weig hts:  ) ) ( ( ) ( 1 T t t t x h sign x H     Adaboo st alg o rithm flow  chart is  sho w n  in Figure 2.           Figure 2. Adaboo st Agorith m  Flowcha r t        In itial weigh t   n D i t 1 ,   t<T?   Select h  (x) t o   make the sm allest error rate  E j | ) ( | 1 j n j j j j y x h E   C a l c ul at e  wei ght s   ) / 1 log( ); 1 /( j j j j a E E   Adju st th e wei g h t     Yes   Out put  f unct i o n   ) ) ( ( ) ( 1 T t t t x h sign x H   No   Evaluation Warning : The document was created with Spire.PDF for Python.
    ISSN: 2302-4 046   TELKOM NIKA   TELKOM NIKA  Vol. 12, No . 1, Janua ry 2014:  734 – 7 4 0   737 3.2. Target F eatur e Extr a c tion   The targ et tracking  sele cti on algo rithm  bas ed on Ad aboo st pro p o s ed in the p a per is in  the light of gray distributio n cha r a c teri st ics of the targ et object to d e tect and tra ck. Here we  use   Harr feature s  as  sele ctio n f eature. Harr featu r e i s  ba sed o n  the integral i m age featu r es.  Comp ared  wi th the traditio nal pixel - ba sed  com put ing  eige nvalue s,  be cau s e    gray-scale  ima ges  posse ss  the cha r a c teri stic  og  a sin g le color, small  co mputation, it i s  ea sie r  to  use integ r al im a ge  cha r a c teri stic to extract pa ramete r [6]. Target  tra c king  sele ction alg o rithm ba se d on Adabo ost  is  adopte d  to  d e tect a nd t r a c k the  target o b ject,  who s e  high deg ree  of  cla s sificati on re sults  im pact  target dete c ti on and tra c ki ng sig n ifica n tly. Harr featu r es is a b le to accurately distingui sh o b j e cts  and n on-obje c ts. Fo r exam ple, Ha ar feat ured  as t he f a ce  edg e feat ure s . Fa ce  Haar featu r e s   are  divided i n to  three  catego ries:  linea r f eature s ,  edg e featu r e s  a nd  cente r   su rro und  features.   Linea r ch ara c teri stic  can  be accu rately  represent  the linear di re ction of the image informati on;  edge featu r e  can a c curatel y  show the e dge s of  the image inform ation; cente r  surro und feat ure   can a c curatel y  show the  central po rtion  of the  image information [ 4 ]. Feature te mplate co nsi s ts  o f  b l ac k a nd w h ite re c t ang le s .  Acc o rd in g  to t he  ch ara c teri stics  of the im age  obtain ed, th ese   feature s  ca n be expre s sed  as:    ) ( Re j T j j r ctSum w feature     Here T is the numbe r of the rectan g u lar feat urej, wj is the weight of the recta ngle,   Re ctSum (rj) is the  sum  of the pixel v a lue s   surrou nded  by a  re ctangl e rj.  Howeve r, u s e  the   above al go rithm ba se d o n  pixel recta ngle featu r e  too mu ch  wil l  gre a tly red u ce  the train i ng   spe ed. Thi s   p aper u s e s  the  integral im ag e metho d , wh ose  main  ide a  is to avoi d  cal c ulate d  p r i o r  to the  pixel re gion  befo r e  d ouble  countin g an d  save   pi xels in  the  re ctang ular regi on  startin g  fro m   the imag e p o i n t to the  cu rrent j a s  el em ents  of the  a r ray. Wh en  a region  of pixel s  i s  to  cal c ula t e,  it can search  dire ctly  elem ents sto r e d  in  the array to spe ed  up  the comp utation. Specific  fo rm ula   is  as  follows :    y y x x y x i y x ii ' , ' ) ' , ' ( ) , (     Here i i s  th e  origin al ima g e , (x, y) i s  the  image  pixel,  ii (x, y) i i s  th e sum of  all t he pixel s   in the uppe r left point.    3.3. Design  of the  Wea k  Classifie r s   Acco rdi ng to  Adaboo st alg o rithm the  ab ove m ention e d , again s t the  origin al weig hts with  the sa me  sa mple, it train s  a  se rie s  of  wea k   cl a s sifiers  thro ugh  cha ngin g   its sampl e  weig hts.  Wea k   cla ssifi er is i n itially prop osed  wh en in 19 84  Valian lea r ne d theory in  PAC. Dete ction  accuracy is b e tter than ra ndom gu essi ng, but not obvious wea k  is calle d we a k  learning [7]. If   detectio n  a ccura cy was si gnifica ntly be tter than  r a n dom g u e ssi n g , we  call  it strong l earnin g . If  the data i s   sufficient, we a k  cl assifie r  cascad e  form s a  stro ng  cl assifier th rou gh trai ning  a nd  learni ng. Be cause of the  di versity of targ et dete c tion  chara c te risti c s, we  can  dete c t catego rie s   to   determi ne the  requi red b a si c cla s sifier h (x ). Here i s  cal c ulate d  as foll ows:    otherwise x f x h j j j 0 ) ( 1 ) (     Here hj  rep r e s ent s the    ch ara c teri stic value  of cl assi fier. The  out put is 1  if th e target  detectio n  is  correct, othe rwise, the out put 0; j is  the  threshold val ue of the ch a r acte ri stic val u e   and fj (x) indi cate s eige nvalue fun c tion.     3.4. Final Strong Clas sifier Con s tru c tor  The mo st important pa rt of target tracking  featu r e  algorith m  is the target de tection  accuracy  and  detectio n   sp eed  sho u ld b e  fast to m a ke it real -time  in order to a c hieve t r a cki ng   results. T h e  we ak cl assi fier d e sig n   menti one d a bove d o e s  n o t meet th e  re quirement s of   Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 2302-4 046                          Targ et Tra cki ng Featu r e Selectio n Algorithm  Based on Adaboo st (Che n Yi)  738 accuracy, fal s e  alarm a n d  false  dete c ti on's rate i s   st ill very hi gh.  Adaboo st al g o rithm i s   use d  to   ca scade  up  and o p timize  the we ak  cla ssifie r s to form  a strong  cl assifier. Th i s  stron g  classif i er  can  qui ckly d e tect the  obje c t to be te ste d . In Adab o o s t lea r ning  proce s s, usuall y  every po sitive  detectio n  thresh old rate i s  98.5% [8].  We  can  ap prop riately in cre a se the p o sitive exam ples'   threshold,  the r eby fal s e  det ection  of n o n - targ et will  al so i n crea se,   but do  not  worry. T he  stro ng   cla ssifie r  cl assifier formed  after the co m b inati on of weak  cla ssifie r s thro ugh  stu d y can b e  used  as  the firs t few hierarc h ical leve ls, the n   more  preci s el y filter non -ta r get by  mean s of th e  stron g   cla ssifie r . As  the first fe w l e vels filter th e majo rity of non-ta rg et, the non -target  past the fin a l  level  of strong  cla ssifie r  will be  greatly redu ced.  As a re sult, the detection accu ra cy and detecti on  spe ed is g r ea tly increa sed.  Specific  st ro ng cla s sifier a l gorithm i s  as follows:   Given the trai ning sampl e s (x1, y1) ... (xt, yt),  where xj denotes the  sampl e  j. When yj =  1, it is the positive sampl e  (targ e t). If yj  =  0, it indicat e s a ne gative  sample  (no n -target).     a. Initialize the weights: T j T x w j j ... 1 , 1 ) ( ；     b. train a wea k  cla s sifier hj  (x)  for ea ch feature;     c .  Selec t  hj (x ) to mak e  the  s m alles t  error rate Ej; | ) ( | 1 i i T j j j j y x h w E     d. updat e th e sample  di stributio n a n d  ej  =  0  m ean s that th e sample  is co rrectly  cla ssifie d  a nd ej  =  1 me an s t hat cl assification i s  in corre c t,  ) 1 /( j j E E ， t e j j t j t Z x D x D j / ) ( ) ( 1 1 ,  where Zt is   us ed to meet the 1 ) ( 1 1 i T j t x D ;    f. Strong classifier con s tru c tor [5]; )) ( ( ) ( 1 x h a sign x H j T j j       3.5. Strong Classifie r  Ca scade Struc t ure   Ca scade in  classifiers refe rs  that the final strong  cl assifi ers are combi ned by  several  wea k  cl assifi ers a nd opti m ized  com p onent s. In t he target feat ure dete c tion , target feature   waiting fo r d e tecting p a ss sequ entially  throug h ea ch cla ssifie r , so that the first few level s  of  wea k  cla ssifi ers ca n  filter most  of  the non-ta rg et  ch ara c teri stics [ 10]. Ultimatel y , the detecti on   area  whi c h can pa ss all a nd export i s  the target  a r e a  zon e . Stron g  cla ssifie r  ca scade  schem atic  diagram is  sh own in Fig u re  3.        Figure 3.   Schematic Stro ng Cla s sifier  Ca scade       Thro ugh thi s   algorith m , ea ch wea k  cl assifier  can eve n tually gene rate a strong  cla ssifie r   throug h T  ite r ation s .  Cal c ulate the  ima ge xj th rou g h  the  ope rati on of  hj  (x) t o  obtai n a  hi gh   accuracy a n d  stability. The bigge r the T  traini ng time s is, the mo re paramete r s and judg me nt  involved in. The accu ra cy and sta b ility of h (x)will be i m prove d  [9].        Evaluation Warning : The document was created with Spire.PDF for Python.
    ISSN: 2302-4 046   TELKOM NIKA   TELKOM NIKA  Vol. 12, No . 1, Janua ry 2014:  734 – 7 4 0   739 4. The Exper i mental Res u lts   In order to tes t  the effec t  of target track i ng  algo rith m, use vi sual  C  + +6.0 si mulation i n   Wind ows XP operating sy stem. Obtain  the followin g  re sults,  sh own in Fi gu re 4: observe  the  video se ction  15, se ction  25 and  se cti on 40 pi cture s  , the target  for the imag e of the hum an   face, a nd  we  ca n dete c t t he p o sition  o f  human  face s in t he tracking video  to  achi eve a ta rget  tracking. Thi s  shows that the proposed  algorit hm has real-time, accuracy and st ability.                         section 15   se ction 25   se ction 40     Figure 4. Simulation Results      5.  Conclusi on  In sum m ary,  the pap er  pro poses  a targ et tr ackin g  fe ature  re cog n i t ion algo rithm s  ba se d   on Ada boo st. By extractin g  the ta rget f eature, th e in tegral  gray v a lue of th e resultin g featu r e   image is give n the appropriate weigh b a s ed o n  its bei ng the ca se o f  ant detection rate to form  a   wea k   cla ssifi er. After T ti mes'  a s sociat ion an d  sub - o p timal level, it ultimately ge nerate s   a  strong   cla ssifie r  to a c hieve th e ta rget tra c king   results. Ove r all this  algo rithm can b e  d i vided into th e  f o llowin g  st ep s:   (1) Input  sa mples,  acco rding to  the  spe c ific  prop erties of the  target  obje c t to dra w   recta ngle feat ure s  and  cal c ulate and g e t  a recta ngul ar  prototype feat ure set;  (2) Enter the  feature  to d e termin e the  th res hold  value  and  corre s p ond fe ature s   to we ak  cla ssifie r s to  obtain set of wea k  cl assifi ers;   (3) Enter we ak  cla s sifiers. In the t r aini ng rate limit,  sele ct the  op timal we ak al gorithm   cla ssifie r s a s   a stron g  cla s sifier inp u t by means of Ad aboo st;  (4) Ente r the  strong  cla ssi fier and opti m ize it ca sca de to con s titute stron g  cl assifier of  the final stag e.  In additio n , throu gh th e u pdate  of the  new we a k   cl assifiers inte grated  onli n e  and  the   existing wea k  classifie r s'  weights, it improves  the a b ility that algorithm  adapt s to cha r a c teri st ic  cha nge of illumination an d other facto r s. In a la rge  number of e x perime n ts o n  real image,  it  comp ares  with the origi nal  algorithm s.  And the  re su lt shows that  this algo rith m can n o t o n ly  respon d bett e r to the ch a nge of t he target feature in  the pre s en ce  of interferin g backg rou n d  to   st ably  t r a c k t a rget s,  but  a l so it  d e s c ri b e s t h e   targ et size mo re  accurately a nd si gnificant ly  improve the tracking a c curacy of the alg o rithm.       Referen ces   [1]    W ang Sh up en g. Vide o targ e t  tracking a l g o r ithm. Xi' a n:  X i ' an U n ivers i ty of Electron ic  Scienc e a n d   T e chno logy.  2 009: 1-8.   [2]    Z hao Ji ang,  Xu Lu ’an. T a rget  Detectio n B a sed  on a d a b oost al gorithm .  Artificial Intelligence  an d  Reco gniti on T e chno logy . 2 004 ; 30(4): 120-1 2 5 .  [3]    Liu T L , Che n  H T . Real time  trackin g  usi ng tr ust regi on m e thods.  IEEE Tr an s  on P a ttern Analysis  and   Machi ne Intell i genc e . 200 4; 26(3): 397- 40 2.  [4]    W ang Xu. T a rget detectio n  system bas ed o n  Adab oost alg o rithm. Xi' a n:  Xi' an Univ ersit y  of Electroni c   Scienc e an d T e chn o lo gy.  201 2; 72: 162- 169.   [5]    Lin deb erg T .  F eature d e tect i on  w i th  auto m atic scal e  se lectio n.  Interna t iona l Jo urna l  of Co mp uter   Vision .199 8; 3 0 (2): 79-1 16.   Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 2302-4 046                          Targ et Tra cki ng Featu r e Selectio n Algorithm  Based on Adaboo st (Che n Yi)  740 [6]    Sortomme E, Venkata SS,  Mitra J. Microgrid pr otecti on  usin g commun i catio n -assiste d  dig i tal rel a ys ,   Know led ge-B a sed Syste m s.  201 0; 25(4): 27 89-2 796.   [7]    McArthur SDJ, Davidso n  EM, Catterson  VM. Multi-age nt s y stem s for po w e r  engi neer in g   app licati ons— P art I: concepts, appr oac hes  and tech nica l  chall eng es.  IEEE Transactions on P o wer   System . 20 07; 174 3-17 52.   [8]    Comaniciu D, Ramesh V, M eer P. Real ti me T racking of non-rigid objects using mean shift.  IEEE  Confer ence  on  Computer Vis i on an d Pattern  Recog n itio n.  2 009: 14 2-1 49.   [9]    Hon g tao  Liu, H ongfe ng Y un,  Hui C h e n , Z h a o y u L i , Yu W u . Interest Exc i ta tion Pro p a gatio n Mod e l fo r   Information P r opa gatio n on  micro-blo g g i ng.  T E LKOMNIKA Indon es ian Jo urna l of Electrica l   Engi neer in g . 2013; 11( 9): 489 4-49 02.   [10]    Xu, P e il on g. Stud y o n  Mov i ng Ob jects b y  Vi de o Mo nit o rin g  S y stem  of Reco gn ition  and T r acin g   Scheme.  T E LK OMNIKA Indon esia n Journ a l o f  Electrical Eng i ne erin g . 201 3; 11(9): 484 7-4 854.     Evaluation Warning : The document was created with Spire.PDF for Python.