TELKOM NIKA , Vol.11, No .1, Janua ry 2013, pp. 411 ~41 6   ISSN: 2302-4 046           411     Re cei v ed Au gust 16, 20 12 ; Revi sed  De cem ber 2, 20 12; Accepted  De cem ber 1 1 ,  2012   A Wavelet-based Algorithm for Vehicle Flow  Information Extraction       Zhi Qiao* 1 , Li-duan Liang 2 , Lei Shi 3 , Ling-ling Li 4   1,3 Department of Electrical a n d  Electron ic En gin eeri ng, He n an Un iversit y  o f  Urban Co nstruction,  Ping din g sh an, Chin a   2,4 Department of Mathematics  and Ph ysi cs,  Hen an Un ivers i t y  of Urb an Co nstruction, Pin gdi ngsh an, Ch i n a   *Corres p o ndi n g  author,  e-ma il:  richard q ia o5 109 @ y ah oo.co m 1 , liangli d u a n 198 1@ ya ho o.cn,  shile iston e4@ gmail.c o m, lili n g95 04 06@ 163 .com       A b st r a ct     T h is pa per  pr opos ed a n  i m p r oved  alg o rith m a ppl ie in v i deo  intel lig ent  traffic control s ystem for   vehicl e det ecti on. T he accur a cy of origi n a l  alg o rith m,  w h ich is base d  on  the co m par isio n of contrast a n d   lu min anc e dist ortion of prese n t ima ge w i th backgr oun d, reduces gr eatly und er bad w e ather bec ause  of   false d e tectio n  cause d  by  no ises i n  ca ptur ed i m ag es . In this p aper w e  chose  Da ub e c hies w a ve let  as   moth er w a velet  to add a 2-d i mensi on w a vel e t process bef or e the alg o rith m, just after the ima ge is ca ptur ed ,   to de-no ise e a ch captur ed i m a ge. W e  used F P GA- bas ed eq uip m ent s to test  the alg o rith m, and  the   exper iment pro v ed hi gh er perf o rm anc e of improve d  alg o rith m, esp e cia lly u nder b ad w eat her.     Key w ords : vehicl e flow,  contrast dist ortion, lu m i nance distorti on, Daube ch ies wa velet, de- noisi ng       Copyrig h ©  2013  Univer sitas Ahmad  Dahlan. All rights res e rv ed.       1. Introduc tion  To solve the  proble m  of urban  con g e stion  a nd o b stru ction, video intellige n t traffic  control syste m  is well-kn o w n as the be st appr oa ch, in which the length of red  and green lig hts  time are varia b le throu gh vehicl e flow. There a r e 3  su bsyste ms in video intellige n t traffic contro l   system,  whi c h a r e ve hi cle-dete c ting  sub s yste m, vehicle - cou n ting sub s ystem and ti me- controlling  su bsyste m. Veh i cle-dete c ting  sub s ystem,   whi c h is m a in ly for detectin g  the vehicl e in  a given are a ,  is the most important part in vi deo  intelligent traffic control system, and  it  determi ne s the efficiency  of whole sy stem.  The algorithm ba se d on contra st and luminance   distortio n  [1] is an accu rate  algorithm for vehicl e dete c tion. That is, compa r ing the cont rast a nd  luminan ce di stortion of p r esent imag e, which  is captured with certain freque nci e s, with  backg rou nd image. If the  2 param eters pass throug h a  thresh old  from large to small, there is a  car p a ssin g into the desig nated area, and then if  they pass through an othe r thresh old from  small to larg e, there is a  car pa ssing  away from the are a . Wh en the 2 pro c e s ses h app en   su ccessively, vehicle-cou n t ing sub s yste m w ould co u n t up by one. The backg round imag e is   update d  every fixed interval of time. Howeve r,  whe n  weathe r gets too bad, such a s  sn ow,  rain storm a n d  sand  storm, the ca pture d  image woul be full of noises. The r efore ,  sometime s the  contrast di st ortion a nd lu minan ce di st ortion  m a y pass the 2 p r oce s se s but  there i s  no  car  passin g , cau s ing error to th e result.  In this paper, we focus  on the impro v ement of this algo rithm. We add a wavelet   pro c e ssi ng [2 ] after ca pture of ba ckgro und ima ge a nd present i m age fo de -noisi ng, befo r e the  pro c e ss of th e algorithm b a se d on co ntrast and  lumi n ance disto r tio n . Daube chi e s wavelet (db N )   has a g ood e x pansi on abili ty [3] so we choo se Daub e c hie s (db8 ) a s  mother wave let.  The pap er was organi zed  as follows. Section 2 de scribe d the algorith m  ba sed on   contrast and l u minan ce di stortion, which  was or igi nal algorith m . Section 3 analyzed Daube chi e wavelet tra n sformation,  ste p s of getting  filter  coeffici e n ts and  wave let de-n o isi n g ,  and structu r e   of improved a l gorithm. Re sults of simula tion and  com pari s on exp e riment were shown in Section   4. Finally we made con c lu sion in Se ctio n 5.      Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 1, Janua ry 2013 : 411– 4 1 6   412 2. The Algori t hm Bas e d o n  Contras t  a nd Luminan ce Distortion   To start the  whol e syste m , the came ra sho u ld be  adju s ted so that it can ca pture the  image of ap p r op riate a r ea.  Gene rally the length of th e are a  is a s  same a s  that of a ca r, and  the  width is a s  sa me as the roa d . That is sh o w n in Figu re  1.                                    Figure 1.   Ch oo s i ng  a r ea      Defini tion    is backgroun d image an  is pre s ent ima g e , and ea ch i m age is  with N  pixels. The g r ay value of each pixel i s  written as     (1)      (2)     The varia n ce of   and   are      (3)      (4)     Therefore, th e contrast di stor tion of an image is  writt en as     (5)     And the lumin ance disto r tio n  is     (6)     In equation  (6),    and    are  the averag e value of  and .To avoid  that th e   denomi nato r  of either  or  is 0,  and  are a dded.  and is dynami c  range of pixe l grayscal e (e.g. if  the image i s  8-bi t grayscale i m age,  is 255 ).  Gene rally an d .   In the whol e  system the  backg rou nd i m age i s  pe ri odically upda ted, but it should n ’t  inclu de ca rs. Thus a threshold (b ackg ro und thre sh ol d )  sho u ld be set before. Th at is, when it is  time for b a ckgrou nd  updati ng but  and  are belo w  th e thre shol d, there mu st be  ca rs in th e   area a nd b a ckgroun d would not up date. After  obtainin g  ba ckgro und, th e system st arts  X Y {| 1 , 2 , ,} i x xi N  {| 1 , 2 , , } i yy i N  x y 22 1 1 () 1 N xi i x x N  22 1 1 () 1 N yi i yy N  1 22 1 2 xy xy C c C   2 22 2 2 () ( ) xy C lum x yC  x y x y c lum 1 C 2 C 2 11 () CK L 2 22 () CK L L L 1 0. 0 3 K 2 0. 01 K c lum Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       A Wavelet-b a s ed Algo rithm  for Vehicle Fl ow Inform atio n Extra c tion (Zhi Qiao 413 initialization p r ocess, wo rk i ng out the varian ce  and averag e value  of backgro und image.   After that the  system  sta r ts real-tim e samp ling  process which sa mples the im age of  roa d   and  then works  out the  and  of pre s e n t image, the n   works o u and  accordi ng  to   equatio ns  (5 and (6).  Whe n  the differen c e s  of  p r e s en t and ba ckgro und ima ge a r e quite mo de st,  and  are ne ar  to 1. And wh en a car  run s  into  the ch osen area  com p letely, they are to the   minimum (ne a r to 0). Th erefore, we ca n  set  2 thre sh o l ds  and    throu gh expe rimen t  and if  and  pass through  from large to small, there i s  a car passi ng into  the area. And then if  they pass th rough  from small to  large,  the ca r i s  pa ssing  away, and after th e 2  pro c e s ses th e   system  count  up by one.  The co ntra st distortio n  in the algo rithm is  releva nt to the variance s  of pixel gra y scal e   thus the sha dow effect co uld be efficie n tly suppr essed. And luminan ce disto r tion is releva nt to   the averag e of pixel grayscale, so the a c cura cy  of algorithm won’t  be affected by light chan ges.  And the al go rithm is a bout  contrast  and l u minan ce  distortion, not p o int-to-point  correspon den ce,  thus the a ccura cy wo n’t be affecte d  b y  came ra sh akin g. Ho wev e r, bad  weat her  woul d ca use  noises in  capt ured im age, thus affe cting the  accuracy seri ou sly.      3. Daube chi es Wav e let and the Impro v ed Algorithm  To improve  the accu ra cy of  algorithm  unde r ba d weath e r, a 2 - dime nsi on  wavelet   pro c e ssi ng i s  adde d befo r e ori g inal  alg o rithm. In thi s  pape r, we choo se  Dau b e c hie s   wavelet  as  mother wavelet.    3.1. Daube c h ies Wav e let  In orthog onal  conditio n  th e Fou r ier T r ansfo rm of  Dau b e c hie s (db8) [4]  wav e let filter   function  satisf ies the eq uati o n      (7)     If then     (8)     Hen c  is a real co efficient  polynomial, and And sin c e ,  th us     (9)      (10 )     From e quatio n (9), (11), (1 2) and  Rei sz  theore m    (11 )     x x y y c lum c lum a b c lum a b 22 () ( ) 1 HH   () in n n Hh e 8 1 () [ ( 1 ) ] ( ) 2 ii He Q e  () i Qe 2 () ( ) () ii i Qe Qe Qe   2 2 1 (1 ) c o s / 2 2 i e  2 2 28 ( ) [c os ( / 2)] ( ) i HQ e  2 2 28 ( ) () [ s i n ( / 2 ) ] ( ) i HQ e     7 2 22 8 2 7 0 1 () ( s i n ) ( s i n ) (s i n ) 22 2 2 ik k k k Qe C R   Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 1, Janua ry 2013 : 411– 4 1 6   414 Then we co u l d obtain  from equation (7), (8) a nd (1 1). No w we  can wo rk o u the coeffici en ts of Daub echies  wavelet filter  as follo wi ng step s:   Firstly, we sh ould obtain  under , and then we can tran sfer to  the function of , so we obtain a univariate equati on  with hig h e r  o r de r, and  we  set it a s   and  . After th at, all the roots o f this equ ation coul d b e  obtained, a nd then   we u s to obtain all the .  Thirdly, as for th e com p lex ro ots, we pi ck o ne pai r of ea ch   2 pairs out a n d  one of ea ch  pair a s  for re al root s, we t herefo r e o b ta in  from  them. The c o u ld be obtai ned from , a nd we co uld  therefore o b tain  with  finally.    3.2. Wav e let-based Image  Processing   Wavelet imag e pro c e ssi ng is 2-dim e n s io n disc rete wavelet trans form [5], whic h c o ns is ts  of line wavel e t transfo rma t ion and col u mn wavelet tran sform a tion . First we sh ould get low- freque ncy filter coeffici ent and high -freque nc y filter coefficie n ts  through the  metho d   above. As for image de -n o i sing b a sed o n  Dau b e c hie s  wavel e t [6], firstly we sh ould de co mp ose  the image and obtain wa velet coeffici ents   with M a llat algorithm, which is described in     Figure 2.          Figure 2.   Mall at algorithm       Here,  is lo w-f r equ en cy filter and  is high -f requ en cy filter.  is do wn-  sa mpling by  two in wavel e t transform.  are scale coefficient s and     are wavel e t coeffici ents.   The image si gnal is a ma trix of pixels, and  each pi xel is the gray value of  a point.  Gene rally, ea ch line an d column of the matrix  coul d be reg a rded  as 1-dime nsi on sig nal [7]. We  start with lin e pro c e ssi ng , using Malla t algorithm for de com posing each line  to get wavelet  coeffici ents  and scale coefficient s. Then we  use  soft-thre shol d de-noi sin g  method [8] fo r   threshold d e -noisi ng a s  followin g      (12 )   2 () i Qe () H 2 () i Qe () 0 Rx 2 () i Qe cos( ) () V co s ( ) i 1 i z z  z () ( ) i Qz A z z  A () () Qi V i n h () Qz n h n g y H G 2 11 2 [] , [ ] , [ ] , [ ] jj j j ck c k c k c k  1 [] , j dk 12 [] , [ ] , [] jj j dk d k d k  s g n ( )( ), 0, ˆ (, ) { tt H t XT t   Evaluation Warning : The document was created with Spire.PDF for Python.
TEL K   noisi n sam e Nex t                   4. Si m origi n   simu l are r 214. 3 to be  imag e in F P impr o with o follo w K OM NIKA    In equati n g, we u s e  pr oc ess  to   Therefor e it’s process  The blo c k   m ulation an Figure 2  a n al imag e an     Figur e The de c o l atio n the le v emove d . W e 3 . After this   p identifie d b y In this  e x e  captu r a n P GA, we  ch o o ve  pr oce s s i o ut it sim u lta w ing:    A Wavelet - on (12)  is  inverse pro c each col u m n e  the d e - no i s of the alg o ri t k  di a g ram of  d Experi m e a nd 3  sho w   t d Figu re  3 s h   e  4. Orig inal  o mp osition  v el of wavel e e  us s o ft-t h p ro ce ss mo s y  sy st em.   x pe ri ment,  w n d L CD fo d o ose liftin g - b i n g  s p ee d.  W neo usly to  g t I S - b a s ed Algo r thresh old,  a c ess  o f  de c o n  of the re co n s ed i m age  t hm ba se d o imp r oved al Figure 3.  T e nt  t he si mulati o h o w s the de - image   level [9] is   e t is 5, and  a l h re sh old de - s t of the n o is e w e ch oose  F d isplay. We   r b as ed  2D D W W e use  a s e g et the vehi c y Image ca p Wav e le t S SN: 2302-4 0 r ithm for Ve h a nd is  w a o mposition t o n st ru ct ed m a could b e   o n co ntra st a n gorithm is  s h                   T he  improve d     o n of wavele t - noised im a g     an im porta l l the compo - noi sing m e t h e s a r e r e m o v F PG A -base d r epla c e sno w W T alg o rith m e t of equip m c le flow info ˆ y ture  t  de co mposi n De-noi s Wav e l e 0 46 h icle Fl ow In f a velet c oeffi c o  re con s tru c a trix.   o btaine d, a n d n d lumina nc e h own in  Figu d  algorithm t  image  pro c g e.   Figure  nt fa cto r  in  nents in lev e h od an d th e v ed, and th e d  eq uip m ent  w  by pape s m  [11] with  p m ent with w a r mation in 1 n ing  e t rec o ns tru c The algo rit on co ntr luminan c f ormation E x c ient, s o c t t he matrix d  wav e l e t p r e  distortion.   re 3.   e ssi ng. F i gu   5. De-noise pr ac tic a l a e l  1, level 2,  e  threshold  v e  passing  ca r [10], using  s cra p s.  A s  f o p arallel archi t a velet proce s  hour. And  t c tion  hm  base d   a s t and  di stortion   x tra c tion (Zhi  . Aft e . Th en we  d r ocess i s  fin re 2  sho w t d imag e   ppli cation.  I le vel 3 and l v al ue of lev e r  i s  still so o b CC D ca m e o r wav e let p r t ecture whi c s sing and a n t he  r e su lts   a [] j dk Qiao 415 e r de- d o th is h e d .   t he    n this  evel 4  e l 5 is  b vi ous  e ra fo r ocess  c h can   n ot her  a re  as   Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 1, Janua ry 2013 : 411– 4 1 6   416 Table 1. Experime n t results  No. Weather   Vehicle  flow  Results of  original algorithm/  Error/Ac c u rac y   Results of improved  algorithm/  Error/ Ac c u rac y   1 Sun  1587   1635/48/96.9 8 %   1544 / 43/97.2 9 %   2 Sun  1462   1517/55/96.2 4 %   1412/50/96.5 8 %   3 Sno w   1256   1328/72/94.2 7 %   1300/44/96.5 0 %   4 Sno w   1518   1621/103/93. 21 %   1568/50/96.8 1 %   5 Sandstorm   1188   1260/72/93.9 4 %   1232/44/96.3 0 %   6 Sandstorm   1203   1274/71/94.1 0 %   1246/43/96.4 2 %       From the ex perim ent re sults it is sho w n that  the accuracy of improve d  alg o rithm is   highe r than  o r iginal  algo rit h m. This is  e s pe cia lly o b vious  und er  ba d we ather su ch a s   sno w   a n d   san d sto r m. T he average  a c cura cy of o r i g inal alg o rith m in bad  we a t her (No.3 - 6 )   is 93.8 8 %, bu it  is 96.51% of improve d  algo rithm.      5. Conclusio n   In this pape r we propo se d  an improve d  algorit hm for vehicle flow  monitori ng ba sed o n   Dau b e c hie s  wavelet. The  experiment proved it s hi gher a c curacy than the algorithm with out   wavelet p r o c essing, e s p e c ially un der  bad  weath e r.  The vide o i n telligent traf fic co ntrol  sy stem   with the imp r ovezzzd algo rithm would  surely hav stronge r pe rformance of  anti - interfe r en ce  and   automatically adju s t the len g th of time more rationally.       Referen ces   [1]    T an Jia-jia, Z hang Jia n -qi u . Novel visi on-b a s ed me thod for rea1-tim e  on road veh i cl e flow   inf o rmatio n   extracti on.  Ch i nese Jo urn a l o f  Scientific Instrument . 200 8; 2 9 (1): 158- 16 6.  [2]    Stepha ne G.  Mallat. Mu lti-r e sol u tion  ap pr oxim ati ons an w a v e let orthon ormal bas i s   of  T r ansactio n s o f  America n  Mat h e m atic al Soci ety . 1989; 31 5( 1): 69-75.   [3]    Liu H u i-j i n, W u  Yu-ron g , Xi on g Lin g -l ing. Ap p licati on of  w a velet  multir eso l ution decom po sition  us in g   Dau bech i es i n  voltag e flicker  ana l y sis.  RELA Y . 2004; 32( 13 ): 6-10.  [4]    Albert Bog ges s, F r ancis J. N a rco w ic h. 200 9 .  A  F i rst Course in W a velets w i t h  F ourier A nal ysis. Guo- shen g Rui. Jia n  Kang:  Pu blis hin g  Hous e of Electron ics Ind u stry . 2010.   [5]    Rajl a x mi Ch ou han, Ag ya Mis h ra, Pritee Kh ann a.  F i nger pr int Authentic ati on b y  W a vel e tbase d  Dig ita l   Watermarking.  Internatio na l Journ a l of Electr ical a nd Co mp uter Engi ne erin g . 2012; 2( 4): 519-5 28.   [6]    W ang Jia n -zh ong, Z han g Hui, W u  Bin,  Chen g W en- hua. Image- D eno isin g Meth od Base d on   Dau bech i es W a vel e t T r ansform and Med i a n  F ilter.  Journa l of W uhan Un iv ersity of T e chn o lo gy . 2 0 01;  23(3): 19- 23.   [7]    Liu Qing- qin g , Guo Li-zho u. Ar ithmetic of infrared im a ge en hanc ement ba sed on the dis perse of t w o- dime nsio nal an d w a ve let  trans form.  Comp ute r  Applic ations  and Softw are . 200 6; 23(1 1 ): 108-1 10.   [8]    Dua n  Yon g -g ang, Ma Li- y uan, Li Yo ng- jun,  W ang T i an-h u i. Improv ed soft-thresh old d enos in g   alg o rithm bas e d  on  w a v e l e t anal ysis.  Sci enc e T e chno lo gy and En gi neer in g . 2010; 1 0 (23) : 5755-5 7 5 8 [9]    Jianz hao  Hu a ng, Jia n   Xi e, Hon g cai  Li, G u i T i an, Xia o b o  Ch en. Se lfa dapt iv e Dec o mpositi on L e v e Den o isi ng Met hod Bas ed on  W a velet  T r ansform.  T E LKOMNIKA Indone sian Jour na l of Electrica l   Engi neer in g . 2012; 10( 5): 101 5-10 20.   [10]    Jian g Xin g -gu o ,  Mo Shao-n i ng , Chu F u -ga ng.  Me thod of si g nal  w a vel e t rea l -time proc essi ng bas ed  on   FPGA.  Applica t ion of Integrat ed Circ u its . 20 10; 36(1 2 ): 45- 50.   [11]    T i an Bao-hu a,  Li Ba o-fen g . Paral l el  archi t ecture for lifti ng-b a sed  2D D W T  algorithm.   Journ a l of   Co mp uter Appl icatio ns . 201 1; 31(1 2 ): 336 6-3 370.   2 () LR Evaluation Warning : The document was created with Spire.PDF for Python.