TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol.12, No.5, May 2014, pp . 3818 ~ 38 2 4   DOI: http://dx.doi.org/10.11591/telkomni ka.v12i5.5099          3818     Re cei v ed  No vem ber 1 0 , 2013; Re vi sed  De cem ber 3 0 ,  2013; Accep t ed Jan uary 1 3 , 2014   One-pass Moment Algorithm for Graphical Primitives      Ju Zhiy ong*, Su Chunmei   Shan gh ai Ke y  Lab of Mod e rn  Optical S y stem , Universit y   of Shan gh ai for Scienc e an d T e chno log y ,  Shan gh ai 20 00 93, Chi n a   *Corres p o ndi n g  author , e-ma i l : juz y @usst.ed u .cn*, suchu n m ei7 685 05 1@ 163.com       A b st r a ct  Moment is a us eful tool in ch ar acter and dr aw ing  reco gn ition.  As the momen t  computati on i s  time- consu m ing, th e mai n  ai m  in  this are a  is to  deve l op  a fast  alg o rith m. T h e co mmo n ly-u sed  meth od  is  the   discrete Gree n ’ s theore m , w h ich transforms t he do ubl e  su mmati on i n to a summatio n  on regi on conto u r. An   improve d  d i scr ete Green ’ s  th eore m   prop ose d  in this  pa per,  w h ich re mov e s the constra i n t  on parity  pair i ng,  thus exten d s its validity i n  ap plyin g  the al go rithm to  co mp l e x regi ons. T he contour traci ng is fulfil led b y   a   bou nd ary-traci ng-a u to mati on,  and the c entra l moments fo r  grap hica l pri m i t ives are co mp uted by o ne- pa ss  scann ing  alg o ri thm, the calc ul ation of  the  mo me nt is gr eatly simplifi ed.     Ke y w ords :  gr aph ical rec o g n i t ion, moment  meth od,   multi p l y  connecte d, b oun dary tracki ng     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    It is well kno w n that the geometri c prop erties  of a sh ape are syste m at ically de scrib ed by  their geom etric mom ents [11]. The first 10 lo we st order mom ents re pre s e n t fundamen tal   geomet ric  propertie s  of  a n  obje c t, incl uding  are a ,  centre of ma ss, a nd  radi us of  gyratio n ,  orientatio n a nd ske w n e ss. Theref ore t he ge ometri c moment s a n d  their i n vari ants a r e  useful in   the re co gniti on of g r ap hical primitive s .  Gene rally , an  engin e e r ing  dra w ing,  a m ap, or a tabl e,  contai ns ma n y  graphi cal primitives, and their re co g n ition is ba sed o n  comp utatio n of high ord e r  moment s, an d the m o me nt com putati on i s   too e x pensive,  th us sp eedu p algorith m   is an  importa nt issue on the pro b lem.   Many fast al g o rithm s  of mo ment comput ation ha d be e n  propo sed  [1-6]. The  co mmonly- use d  techniq ue is to  apply  the so -called  discrete   Gre en’s th eorem,  whi c h tra n sf orm s  the d o u b le- summ ation o f  moment co mputation int o  addition  o peratio ns  alo ng the re gio n  conto u rs.  One  disa dvantag e  in these re sea r che s  is t o  pair le ftmo s t pixel with  its rightmo st partner fo r a ll  segm ents of  a region, which i s  time con s umin g, and re strai n  its applicati ons o n  com p lex   s h ap es .   In the existing method s,  only one region i s  trea ted, or boun dary pixels  and their  coo r din a tes  a r e given  at be ginnin g . The  probl em  of o b t aining  coo r di nates  of the b ound ary pixel s   w a s  d i s c u s s e d  o n l y in   p a p e r  [6 ]. It is   w e ll  k n ow n th a t  sc ar ce ly a n  imag e   c o n t a i n s   o n l y one  obje c t. It is e v ident also th at the graphi cal p r imitiv es can not be  re cog n ized till their lo catio n s in   the image a r e discerned,  and their m o ments a r e  computed. In this pap er, we formulate  an  improve d  di screte  Green’ s theore m , an d pro p o s e a n  algorith m , b y  which mom ent com putati o n   for gra phi cal  primitives i s  completed by  one pa ss of image sca nni ng.      2.  Geome t ric M o ments a nd Discre t e Gr e e n’s Theor e m   The geo metri c  mome nts of  graphi cal p r i m itives are d e fined by:     00 , MN pq pq ij mi j f i j             (1)     Whe r e   , f ij   is th e grey level  of pixel , ij . Shapes in  a bi na ry digital i m a ge a r e  co mpl e tely  determi ned  by their  co n t ours.  For th is rea s on  bi nary im age s are  often  u s ed  in d r a w i n g   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     One-pa ss M o m ent Algorithm  for Graphi cal Prim itives (Ju Zhi y on g)  3819 rep r e s entatio n and d r a w i ng re co gnitio n . For two - le vel image, the definition o f  the geomet ric  moment s is:       , pq pq xy mx y           (2)     Whe r e    is the regi on o c cupied by the  grap hical  pri m itives. It is a doubl e su mmation defi ned   on the  o b ject regi on s. T houg h  summ ation i s  a   si mple  ope rati on in   comp u t er, in  order to  recogni ze th e  cha r a c ters a nd symb ols i n  a dra w in g, large  quantity  of high ord e r moments m u st  be cal c ul ated  for nume r ou s obje c ts, thu s  the sp eed o f  the algorith m  is cruci a l to its appli c ati ons.   The main te chni que u s e d  in spe edu p the mome nt algorithm  is to tran sform origin al d oubl e   summ ation in to a summati on alo ng the   conto u r  of the obje c t by a pplying vari o u s ve rsi o n s  o f  the  discrete Gre e n ’s  theo rem.   By some man i pulation on f o rmul a (2 ), we have:        ma x m a x max m ax mi n m i n mi n m i n xy xy yy pq q p pq yy x x y y y x x y mx y y x             (3)     Whe r e   min y   and   min y   are,  re spe c ti vely, the mini mum a nd  ma ximum o r dina tes of  the  re gion,  and   y x min ,  y x max   are, re spectively, the leftm ost and  rightmo st ab sci ssa of   y   se gment. By  introduc i ng notation:         ma x min mi n m ax , xy p p xx y Sx y x y x          (4)     Formul ae (4)  is expre s sed  as:        ma x mi n mi n m a x , y q pq p yy my S x y x y          (5)     It is the conv entional  discrete Green’ s t heorem  u s e d  in mome nt calcul ation s . It is worth  noting that i n  som e  versio ns  of discrete  Gre en’ s the o rem,  one  ne ed to p e rfo r m  cal c ulatio ns  at  both top  an d bottom  bo unda ry pixel s . Fo rmul a  (5) i s   a g ood  version  of  discrete  G r e en’ s  theore m , a s   it need s only  to p e rfo r m  cal c ulatio ns  on  right  and  left bo und ary. Now the   only  probl em i s  to  locate  the le ftmost and  ri ghtmost  point  and  pair th e m , whi c h  will  be di scusse d  in   next sectio n.      3.  Impro v ed Discre t e Gre e n ’ s Theorem   It is a  cumb ersome  task  to pai r  right  boun dary  pixels  with  their left pa rtne rs, whi c h   make s al so di screte G r ee n’ s theorem inv a lid fo r co nca v e polygon s and multi-co n necte d regi on s.  For a given y , we ne ed to calcul ate:       , r p p xl Sl r x            (6)     That is to perform the sum m ation betwe en t he leftmost and the rig h tmost pixel of a give  segm ent. If the co ntributio n  to    , p Sl r   from the left bound ary  pixel and the  right bo und ary pixel  can b e  disco m posed, the difficulty in pairing is  remov ed.  After sele ctin g a coo r di na te origin, the r e are thre e config uratio n s  whi c h fo rm  by the   positio ns of the left and the right bou nd ary pixel wi th  resp ect to the origin. We must analy s is in   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 5, May 2014:  3818 – 38 24   3820 detail the  contributio ns to    , p Sl r   from th e  left and  th e rig h t bo un dary pixel  in  these  config uratio n s .      Figure 1. Three Co nfigurations Fo rme d  by t he Locati ons of the Lef t and Right Bound ary Pixel  with Re sp ect  to Coordinate  Origin        Con s id er first  the case of 0 p . When 0 p , in all  these three  configuration s , we hav e   formula,:      0 ,1 Sl r r l            (7)     As  for 0 p , it is  not difficult to find the cont ributio ns  of the leftmost pixel or the   rightmo st pix e l in all th ese thre e confi guratio ns,  bu t the derivati on is so me t ediou s, thu s   it is   conve n ient t o  write direct ly the re sults, whic h corre s po nd, re sp e c tively, to  top, middle  a nd  bottom config uration:       ,1 pp p Sl r f r f l           (8)        ,1 p pp p Sl r f l f r                             (9)     And,     ,1 1 p pp p Sl r f l f r            (10 )     Whe r e we ha ve used the n o tation:     0 s p p x f sx            (11 )     In following discussions,  we will  select  a bou ndary pixel as the  origin of the  ref e rence  coo r din a tes,  and pe rform  moment com putation s  wit h  respe c t to this point. Le t coordi nate s  o f   these  thre e  points in th e  wo rl d  syste m  are, re sp e c tively,  o x ,  l x , and r x . By using f o llowing   notation s :    0 , ˆ 1, ro r o rr o x xi f x x r x xi f x x            (12 )   0 1, ˆ , lo l o ll o x xi f x x l x xi f x x            (13 )   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     One-pa ss M o m ent Algorithm  for Graphi cal Prim itives (Ju Zhi y on g)  3821 Formul ae (8)-(10 ) for all three co nfigurations  can b e  e x presse d as:      ˆ ˆ , pp r o p p l o p Sl r s i g x x f r s i g x x f l         (14 )       Whe r e:    1, 0 , 1, p if a b a n d p od d sig a b ot herw i s e          (15 )     Therefore, th e co ntributio n s  to  , p Sl r  from the leftmost po int and the  ri ghtmost p o int   can  be   cal c ul ated  sep a rately, if their po sition s  with  re spe c t to the origin of refere nce sy stem a r e  cal c ulate d . Thus, the rem a ining p r obl e m  is to lo cate the c o ordinates  for all the leftmos t and the   rightmo st pixels.       4.  Con t our Foll o w i n g  and Boundary  Pix e l Locating    4.1. Bounda r y -tracing Au tomaton   If an image  contain s  only  one regio n , its bo und ary can be l o cated  by a bou nda ry-tra cing   algorith m  [10] . The m o st  efficient al gorit hm in  bou nd ary tra c in g was  pro p o s ed   by Ro se nfeld  [7].  Present pro b l e m is not sim p ly to trace a  given si mpl e -con ne cted re gion, but is to  follow co nto u r,  to locate a n d  mark th e bo unda ry pixels of graphi cal  primitives, an d to comp ute  their mome n t s.  We de sig n  an  automaton to  meet all these requi rem e n t s.   If a bou nda ry  pixel is lo cate d, and  we li ke  to follo w  regi on o u t of the   regio n  p e rim e ter, an  automaton  can be de sign ed to carry this wo rk. T he  Inner state s   of the automaton are give n in  Figure 2.      Figure 2. Inner States of t he Bound ary-tracin g Auto maton       The bla c k pix e l in Figu re 2  denote s  the  regio n  of the  grap hical pri m itives, and t he arro w  in white pixel  denotes b o th the directio n of  automaton movement , and its present location.  The   transitio n m a pping  of the   automaton  in  state A  is  gi ven in  Figu re  3. Th e tra n si tion map p ing s  fo r  other three st ates are obtai ned by simply  ro tating Figu re 3 by 90, 18 0 and 27 0 de gree s.       Figure 3. Tra n sition Ma ppi ng of Automa ton in State A       The pixel  with  “?” is to  be  checke d: If it is  bla c k, take  downward  pa th, otherwise, upward  path. The  dra w ing s  at the   right  side  of the la rge  arro w give the  st ate of the a u tomaton  at ne xt  time step, an d the num bers in b r a c kets  gives t he in crements i n  co ordin a tes  bet wee n  succe s sive  time step s. Color bl ue the  pixel occupi e d  by autom at on when its  state is D, an d  colo r re d the  left  pixel of the automaton wh en its stat e is B. Beginning  with the posi t ion of the starting pixel, a nd  add  su cce ssi vely the in cre m ents in  co ordinate s ,  which give s the   coordi nate s  of  every  bou nd ary  pixel with re spect to the ori g in of the refe ren c e sy stem .  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 5, May 2014:  3818 – 38 24   3822 4.2. Bounda r y   Marking to Av oid  Re-tr acing [9 ]  For the imag es containin g  many object s , it mu st take a measure  to avoid re-tracin g  any   regio n  b ound ary [12]. The   probl em i s  n o t  simple   as its ap pea ra nce ,  and the  difficulty motivated  Seong -Dae K i m et al. to propo se a two-pha se s-al gori t hm in whi c h  a bina ry imag e is first writt en  in run-l ength  codi ng and th en conve r t them into c hain  code [8]. Owing to the ability of automaton   in disce r nin g  the left and ri ght boun da ry pixels, it  is  easily to p r ev ent from re-tracin g  by usi n g  boun dary ma rkin g.      Figure 4. Cha r acte r Perim e ters Give Full  In formation a bout English and Chine s e  Sentence       The first an d the se con d  line in Figu re  3 are,  res p ectively, “This  is  a sample. ”  in English  and in  Chine s e. Tho ugh o n ly cha r a c ter  perim eters  are dra w n, it gi ves full information ab out  the  words. Thi s  example  ill ustrates  obviou s ly that in  drawin g recog n itions only t he  size a nd  the   conto u r of an  object is im p o rtant. Thu s  it is  adeq uate to con s id er th e method that  comp utes o n l y  the geomet rical moment s for ea ch pe rim e ter of  the graphi cal pri m itives in an ima ge.   A flag is  use d  to de note  wheth e r th e  automat on  e n ters or leav es the  pe rim e ter of a   grap hical p r i m itive. It is name d _ mF l a g and set  _ 0 mF l a g   at the be ginni n g  of the   comp utation.  The  scanni ng  pro c e dure b egin s  with  th e bottom li ne  of the im age , and it  che c ks  pixel colo rs from left to right, and from bottom to  top. In  this man ner of scanni ng, only the left  boun dari e s a nd the right b ound arie s ca n be detecte d ,  thus if the s c an ning un de rgoe s a white - to- black t r an sition a n d _ 0 mF l a g , a ne w p e rim e ter i s  d e tecte d , a nd the  auto m aton  comm e n ce s  the co ntour followin g . Encounteri ng bl u e  pixel sets _ 1 mF l a g , and e n counte r ing  red  pixel  sets _ 1 mF l a g .  It is ease to see that  whe n _ 1 mF l a g , the pixel u nder  ch ecke d  is ce rtainly  within   a perimete r .  Marki ng bo unda ry pixels in th is ma nner p r event s automato n  from re-tracing  conto u rs of graphi cal pri m itives.      5.  Cen t ral Mom e nts  for Gra phical Primitiv es  If the origin o f  the referen c e coo r din a tes in the world  system i s , oo x y , th e geomet ric  moment s of a graphi cal p r i m itive with re spe c t to this referen c e p o in t are:      , , pq pq o o o o xy mx y x x y y           (16 )     The letters i n  bra c ket de n o te explicitly  the  location o f  the refe ren c e point. Th e  centroid  of a graphi cal  primitive is calcul ated by:       10 0 1 00 ,, , , / , c c o o oo oo x y m xy m x y m xy        (17 )     Moment s co mputed with  resp ect to c e n t roid are the central mom e n t s,      , , pq pq c c c c xy mx y x x y y           (18 )   The ce ntral  moment s ha ve some sp ecial me anin g s in the re cog n ition of grap hical   primitives. F o r example,  the central moment s  of se con d  ord e r are used fo r determi ning  the   prin ciple axe s  of gra phi cal primitives,  and are  im portant in in vestigating t heir  symmetrical  prop ertie s .   There is a simple relati onship betw een the ce n t ral moment s and thei r general  geomet rical moment s:  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     One-pa ss M o m ent Algorithm  for Graphi cal Prim itives (Ju Zhi y on g)  3823   , , pq pq c c o c o o c o xy mx y x x x y y y          (19 )     Formul ae of  central mo ments exp r e s sed by  geo metrical mo ments a r e o b tained by  expandi ng formula (1 9), an d the formula e  for ce ntral  moment s of lowe r orders a r e listed.      00 00 ,, cc oo mx y m x y          ( 2 0 )      10 10 0 0 ,, , cc oo c o o o m x y m xy x m xy         ( 2 1 )      01 01 00 ,, , cc oo c o o o mx y m x y y m x y         ( 2 2 )      11 11 01 10 00 ,, , , , c c o o co o o c o o o co co o o m x y m xy x m xy y m xy x y m x y             (23)     2 20 2 0 10 00 ,, 2 , , c c oo c o o o c o oo m x y m xy x m xy x m xy       ( 2 4 )      o o co o o co o o c c y x m y y x m y y x m y x m , , 2 , , 00 2 01 02 02     ( 2 5 )     Whe r e   ,, co co c o c o x yx x y y   i s the proje c tion  of the line conne cting poi nt  o  with object  centroid on th e worl d syste m .  If we  com put e mom ents d i rectly in  worl d sy stem,   0 s p p x fs x   should  be  calculated  0  throug h imag e width. Alternativel y, if moments  are  computed  with  respe c t to a boun dary pix e l of  grap hical pri m itive, the calcul ation of   0 s p p x fs x is re stri cted i n  the width  of the graphi cal  primitive. As f o r  central mo ments,  if the  cal c ulatio n is perfo rme d  with referen c e  to the centroi d ,   the co ordinat es of  a cent ro id are ge neral ly not intege rs, thus  the ca lculatio ns are   perfo rme d   wi th  floating num b e rs. Be side s,  the coo r din a t es of a  centroid ca nnot b e  located till  contour foll owi n g   is finishe d , thus the calculation s  of the c entral mo ments cann o t  be complet ed by one-p a ss   scanni ng in this man n e r .  No w mo ment  co mputation   algorith m  i s  f o rmul ated  as follows. Th e  image i s   sca nned  to  detect the  bo unda ry pixel.  A white-to -bl a ck tra n sitio n  with  _ 0 mF l a g mean s  a bou nda ry p i xe l  on a  n e w g r aphi cal  p r im itive, thus it s  coo r di nate s  in  the  world sy stem i s  re co rde d . T he  automaton  st arts to tra c e  the conto u r,  and co mpute  the geometric mome nts  of the grap hi cal  primitives by  applying  the  improved  discrete  Gr een ’s the o re m.  Whe n  a u tom a ton b a cks t o  its  starting p o siti on, cent ral m o ments fo r graphi cal pr i m itives are  com p uted by usin g  formulae (19 ) .      6. Conclu sions   Figure 5 displ a ys the re sult s of this mom ent  comp utation algo rithm. Every left bo unda ry  pixel is blu e -colo r ed,  and   every ri ght b ound ary  pixel   re d-colo red,  whi c h preve n t   regi on co ntours  from re-traci n g , and t r a c e  only the p e ri meters of th e  ch ara c te rs.  Gree n pixel s   within  cha r a c ter  frame s  den ote the cent roid s of the cha r a c ters.       Figure 5. Tra c e the Outlin e of Characte rs      Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 5, May 2014:  3818 – 38 24   3824 In this pape r, we formul ate first a ne w ve rsio n of the discrete  Green’ s theore m , which   need only to treat the leftmost and the  rightmo st  points of regio n  segme n ts. By discom p o s i ng  the contri butions from  both  the leftm o s t  point a nd  righ tmost p o int, the difficulty in  pa rity-pairi ng  i n   conve n tional  discrete  Green’ s the o re ms i s   rem o v ed. Th us thi s  im prove d   discrete  G r e en’ s  theore m  i s  n o t only  cap a b le of t r eatin g con c ave  p o lygon s, but  also  valid fo r multi-con n e c ted   regio n s, a nd  has n o  extra - cal c ulatio n ri sen  by the sh ape compl e xity. We desig n an auto m at on   to fulfill the contour follo win g , the leftmost pixe l and rig h tmost pixel  discerning, a nd the bou nd ary  marking. In  this  algo rithm ,  geog rap h ical mom ents  and  ce ntral  moment s of  all the  gra p h i cal   primitives in t he imag e are  comp uted b y  one-p a ss  o f  image sca n n ing. As a fa st algo rithm  of  moment com putation, it provides  a  useful tool for dra w ing ve ct ori z ation  and dra w ing re cog n ition.  The meth od  is ho peful i n  its a pplications i n  reco gnition of g r aphi c sym bol s in  cha r ts  and   diagram s.      Referen ces   [1]  YS Abu-Mostaf a, D Psatlis. R e cog n it ive  asp e cts of momen t  invaria n ts.  IEEE Trans. Pattern Analysis   Mach.   Intell.  19 84: 698- 70 6.  [2]  C T he, RC Chi n . On image a nal ys is  b y  t he  method of mo ments.  IEEE Trans. Pattern A nalysis M a ch.   Intell.  198 8: 49 6-51 3.  [3]  A Khot anza d , YH  Ho ng. In varia n t ima g e  reco gniti on  b y  Z e rnik e mo ments.  IEEE Trans.  Patter n   Analys is   Mack Intell.  199 0: 48 9-49 7.  [4]  MF Zakaria, LJ Vroomen, PJA  Zsombor-Murr ay , JMHM  van  Kessel, Fast algorit hm for computation of  moment inv a ri ants.  Pattern Recog n itio n . 198 7:639- 64 3.  [5]  BC Li, J Shen. F a st comput ati on of moment i n vari ants,  Pattern Rec ogn itio n.  1991; 2 4 : 80 7-81 3.  [6]  SH Lai, S Ch a ng. Estimatio n  of 3-D transl a ti ona l motio n  pa rameters via H adam ard transf o rm.  Pattern   Recognition Lett.  1988; 8: 341 -345.   [7]  A Rosenfe l d. A l gorit hms  for Image/Vector C onvers i on.  Co mp uter   Graph i cs.  1978; 20: 1 35-1 39.   [8]  Seon g- Dae K i m, Jeong-H w an Le e, and J ae-K y o on Kim,  A ne w  ch ain- codi ng al gorith m  for binar y  imag es usin g run-l egth co des , CVGIP. 1988;  41: 114-1 28.   [9]  Xi ai  Ch en, L i n g  W a n g , W e n qua n C h e n , Y anfen g Ga o,  Detectio n of  W a termelo n S eeds  E x terior   Qualit y base d  on  M a chi n e   Vi sion.  T E LKOM NIKA Indo nes i an J ourn a l  of  Electrical  En gi neer ing.  20 13;   11(6): 29 91- 29 96.   [10]  Jun Y ang, T u shen g L i n,  Xi aoli  Ji n,   An I m age  Spars e  Repr ese n tati on for  Sal i e n c y   Detecti on.  T E LKOMNIKA Indon esi an Jou r nal of Electric al Eng i ne eri n g .  2013; 1 1 (10):  614 3-61 50   [11]  T J  W a tson. Research C enter,  Yorkto w n  He ig hts NY.  An imp r oved d a ta stre am a l g o rith m for freque ncy   mo ments.  SODA ' 04 Pr oce edi ngs  of the  fifteenth  a n n ual A C M-SIAM s y mp osi u m  on D i scret e   alg o rithms. 20 04: 151- 15 6   [12]  T  Herman, DF  Robi nso n . Digit al bo un dar y tra cking.   Pattern Analy s is & Applic.1998: 2-17        Evaluation Warning : The document was created with Spire.PDF for Python.