Visual Tracking Based on Accumulated Differences

Copy igh co IF AC In elligen Componen s and Ins umen s o Con ol Applica ions, Annecy, F ance, 1997 VISUAL TRACKING BASED ON ACCUMULATED DIFFERENCES 1 Manuel Va gas and F ancisco R. Rubio Dp o. Ingenie ia de Sis emas y Au oma ica Escuela Supe io de Ingenie os A da. Reina Me cedes sin, 41012-Se illa (Spain) Tel: 34-5-4556855, Fax: 34-5-4556849, E-mail: [email p o ec ed] Abs ac . This a icle p esen s an algo i hm o acking an objec using a obo p o ided wi h a came a in he inal e ec o . Simple me hods a e s udied o es ima - ing he op ical low based on accumula ed di e ences which pe mi acking in eal ime. The s udy is i s ealized by simula ion and hen he bes esul s a e ied expe imen ally. Keywo ds. Robo ics, Image p ocessing, ViSual mo ion, Op ical low, T acking. 1. INTRODUCTION This a icle is cen e ed on he analysis o he acking p oblem linking a ision sys em and an a icula ed a m by he adap a ion o a came a in he inal e ec o o he a m ( his is e med eye-in-hand con igu a ion). The ollowing p oblem is posed: "Obse ing an objec on he isible scene, compensa e i s displacemen s in such a way ha i always occupies he same posi ion in he image" (p e e ably a he cen e ). The in o ma ion abou he mo emen achie ed om a sequence o images can be cha ac e ized by he so called op ical low (Balla d D.H., 1982). The op ical low is a consequence o he ela i e mo emen be ween he cam- e a and he objec s on he scene. Se e al echniques o es ima ing he op ical low ha e been de eloped (Ma - in W.N., 1988), (Fu K.S., 1986), (PapanikolopoulosN.P .. , 1993), no able amongs hem being he echniques based on he in ensi y unc ion g adien . Such echniques a e based on he so called g adien cons ain equa ion, which ela es a e e y pixel, he space- ime g adien o he eloci y ec o associa ed o ha pixel. The e a e also 1 The au ho s would like o hank o CICYT o suppo ing his wo k unde g an TAP 95-0370. 259 SOme s udies combining s e eoscopy wi h he op ical low de ec ion (AlIen P.K., 1993). In hei o iginal o m, all hese algo i hms a e e y es ic ed. On one hand, hey assume ha any change o he in ensi y unc ion a each pixel is only due o he mo emen . On he o he hand, hey equi e images wi hou discon inui ies in space and ime. Many mono-came a isual acking algo i hms y o de ec and ollow well-known objec s, which ha e some isual ea u es, he posi ion o each is accu a ely known ela i e o an objec coo dina e sys em (Hashimo o, 1993). The acking p ocess es ablishes s ong imposi ions in eal ime because an immedia e esponse o he displace- men s o he objec is needed. This a icle p esen s a me hod based on he accumula ed di e ence echnique, which allows o a apid esponse using no oo powe - ul ha dwa e. In his me hod he in e es is cen e ed in de ec ing and acking an objec wi hou a p e iously de ined shape o s uc u e. We a e jus ocused o ob- jec s which a e dis inguible om he backg ound and which a e mo ing (since he pu pose is o ack mo ing objec s, he mo ion i sel will be used as a di e encia ing p ope y). Hence, ou pu pose is o ack a bi a y shaped mo ing spo s in wo dimensions. 2. OPTICAL FLOW The i s app oxima ion o c ea ing a di e ence image (Fu K.S.: 1986) is based on he c i e ion exp essed in he equa ion, ADJ j(x, ) = { 1 i IJ(x ,y , j) -I(x , y, j )1 > 6; ( j > j) }l ) J Y 0 o he wise ; The new image, called ADI (Absolu e Di e ence Im- age) is he esul o a compa ison be ween wo ames (g abbed images) successi e in ime, he i s one aken a i and he second one a j. This di e ence be ween he in ensi y o he pixel be o e and a e wa ds is consid- e ed signi ican o negligible, depending on he h eshold alue used (8). Thus in he ADI image hose pixels o he di e ences esul ing om he mo emen will appea as ones, and also hose due o noises which cause a change o in en- si y supe io o he e h eshold. The small a eas o 1 's which appea can be due o noise o o eal bu insigni i- can di e ences, a e elimina ed by echniques o e osion and pos e io dila ion o he image objec s; his will also egula ize he shape o said objec s (as said be o e, he exa c objec 's shape is no o in e es ). Th e se o pixels o he mobile objec which ake up new posi ions in he image which p e iously belonged o he backg ound, will be called he leading edge o he objec . The se o pixels o he mobile which lea e posi ions which p e iously we e occupied by he objec will be called he lea ing edge o he objec . The ADI image will show bo h he objec 's leading edge and lea ing edge as 1 ' so Howe e i is o en mo e in e - es ing o o b ain in a di e ence image only one o hese edges. This leads us o wo new ypes o di e ence im- ages. Th e wa y o calcula ing bo h is gi en by he equa- ions, PD1 i ( x. ' ={l i I (x ,y, ;) -I (x ,y, j» 6; ( J > ;) } J ' y ) 0 o he wise; (2) , VDJ , I X . ) = {l i - (I (x , y, ;J - I(x ,y, j)) > 6: ( j > i ) } J ' Y 0 o he Wlse; This o mula ion does no ensu e ha one edge o he o he is ob ained independen ly. This is only ue when he ange o in ensi ies o he mobile is highe han he one o h e backg ound (in his case PDI p o ides he lea ing edge and NDI he leading edge), o when he in ensi y ange o he mobile is lowe han he one o he ba ckg ound (PDI gi es he leading edge and NDI he lea 'ing one ). Howe e his si ua ion de e io a es i he an ge o he objec 's in ensi ies is highe han he backg ound's in some a eas and lowe in o he s. 260 2.1 Al e na i e Fo mula ion o he Di e ence Me hod Le 's suppose he in ensi y ange o he mobile is known: = [i m in ' . . ima", l (e en i his ange is no known om he beginning, i can be es ima ed aking ad an a ge o he mo ion o he objec o in e es , see (Va gas, 1997)), In o de o ob ain an image wi h he leading ed ge and sepa a ely ano he wi h he lea ing edge he oll owing o mula ion can be used: PDI (x ) = {l i I (x ,y, j) ET and I (x ,y , j) ! . T; ( j > d } 'J ' y 0 o he Wise; N DI (x ) ={l i I (x,y, ;J ! .TandI (x , y, j) ET ; ( j > ;) } 'J ,y 0 o he Wise; ADI. " (x, ) = { 1 i P Dl jj (x , y) = 1 o N DJjj (x , y) = 1: ( ; > ;) J Y 0 o he Wise; wha e e he ela ionship be ween he in ensi ies o he backg ound and hose o he mobile migh b e. In his case i is unimpo an ha in some egions he in ensi ies o he mobile a e abo e and in o he egions below hose o he backg ound. The only p oblem which may a ise is i he e a e in ensi ies o he backg ound wi hin he ange, because in his case i is no possible o dis inguish wha is backg ound and wha is objec ; hese egions will be called in e e ence egions. Ac u- all y, hese egions ha e no e ec du ing acking so long as he mobile does no pass o e any o hem . up o now, he di e ence images ha e been ob ain ed u s- ing only wo consecu i e images. Howe e , wha is usu- ally used is he so called accumula ed di e ence me hod. In his me hod a i s image (l o) is aken as a e e en ce: R; and he ollowing n ames a e all compa ed o R and a e accumula ed on op o he same esul an image. ~ex , he new e e ence o be used o he ollo ,' ing n ames is aken: and so on. Thus , he equa ions will now be like: N DI (x ) ={ 1 i R (x ,y) ! . andI(x , y, j) ET :} (4 ) J ' Y 0 o he Wise; The ac ha h e se simple di e ences a e accumula ed can be exp essed by h e equa ion, N ADln (x, y) = L .l VDI J(x ,y) (5) J =I Thus he PADI (Posi i e Accumula ed Di e en ce Im- age), NADI (Nega i e Accumula ed Di e ence Imag e) and AADI (Absolu e Accumula ed Di e ence Image ): images a ise. The PADI indica es: o each pixel on which he objec was in he e e ence ame, he numbe o ames ( om he e e ence) in which he objec has been abse n om his pixel. Th e l' ADI indica es he numbe R) o ames ( om he e e ence) in which his pixel, which ini ially was no occupied by he objec , has been occu- pied by said objec . Figu e 1 illus a es hese concep s wi h an example. I shows a mobile being displaced a he a e o 1 pixel/ ame o he igh . (R ) (R) (I) (2) m (4) ~ I) l (2) 0> (4) (I) . ~~ Cl> P) 4 3 2 I ~~. Lm n : : :: 4 ) 2 I 4 3 2 I 4 3 2 I (a) ..... __ .... .. _- (b) (R): objec posi i on in che e e ence ame (n): objec posi i on in he n·ch ame (c) Fig. 1. (a) PADI di e ence s. (b ) NADI di e ence s. (c) AADI di e ences . This in o ma ion abou he numbe o ames in which he e was no objec ( o he PADI) o he e was i ( o he NADI) is ansla ed in o he numbe o ames elapsed since he objec le ( o he PAD!) o eached ( o he NADI) said pixel, ( his second in e p e a ion o he accumula ed di e ences allow, as will be seen, he eloci y in o ma ion o be ob ained). Howe e , his in- e p e a ion is no alid, o example, i he mobile is e y small in ela ion o he numbe o ames which a e accumula ed. Le 's suppose, o ins ance, he objec in Figu e 2, pay- ing a en ion o he pixel (x, y) showed, and calcula e he NADI which would be gene a ed o e his pixe!. In case (a), in which he objec mo es o he igh a he a e o one pixel pe ame, he objec begins o be o e (x , y) when ame 3 is aken , and in all he ollowing ames he poin will con inue o be occupied by he objec ; he e o e, s a ing om ame 3 he alue accu- mula ed o e he pixel is inc eased by 1 o each ame aken. A he end N ADI (x, y) = 5 is ob ained; and his coincides w i h he numbe o ames g abbed since he pixel was occupied. (R) (I) (2) (3) (4) ( S) ( 6) (7) (R) (I ) (2) (3) (4) (5) ( 6) (7) l,, ji " 'n,, jiY ~ ;;~ " " , y ; ; ;", (x. y) (R ): Objec posi i on on he e e ence ame (n): Ob jec po'; ion on he n · h ame Fig . 2. Objec mo i ng a 1 pixel / ame owa ds he igh . (a ) W ide obje c . (b) T hin o bjec . Le 's now look a case (b) o Figu e 2 in which he ob- jec is specially na ow. The pixel is only occupied by 261 he mobile du ing ames 3 and 4, he e o e he alue i- nally accumula ed in N ADI (x, y) is 2. Howe e , a he end, he numbe o ames elapsed since he pixel was occupied is 5 ( he same as in case (a)). This incon enien is almos o e come in he eloci y ex- ac ion p ocess, gi en ha he di e ence be ween he alues accumula ed in a pixel and i s neighbo s and no he absolu e alues a e conside ed, as will be shown in he nex sec ion. I is con enien o poin ou a signi ican di e ence be- ween PADI and NADI; I is ob ious ha bo h s op g owing when he objec s ops, bu he PADI also s ops g owing when he objec comple ely qui s he a ea i was occupying on he e e ence image. This poin c an be used, o example, o ex ac s a ic images om images on which, om he beginning, he e a e mobile objec s. 2.2 Op ical Flow S a ing om Accumula ed Di e ences The op ical low ield ( he ield o eloci ies a each pixel) can be ob ained om an image o accumula ed di e - ences. We a e going o p esen his deduc ion s a ing om he N AD 1. The image con aining he NAD! will be called D o sho h oughou his deduc ion. I , as said be o e, i can be assumed ha he di e ences accumula ed a e e y pixel can be aken as he numbe o ames elapsed since he objec occupied he pixel hen , D(x+ 1, y) -D(x, y ), ep esen s he numbe o di e ence ames om when he objec occupied he posi ion (x, y) un il i occupied (x + 1, y). Gi en ha a disc e e app oxima ion o he de i a i e is a di e ence quo ien , he ollowing equa ion can be w i en , D - aD ~ D(x +1 ,y) -D (x, y) -D ( 1 ) -D ( ) "'_-~ _ x +, y x,y ox (x + 1) -x (6) D -aD ~ D (x,y+ 1) -D (x,y) -D ( l) -D () y _ - ~ _ x , y + x, y ay (y + 1) - y The ho izon al componen o he eloci y '" is he num- be o pixels passed o e ho izon ally pe ame elapsed ( he ime uni is he ame). We can de ine he Vy com- ponen in he same wa y. I Dx is he numbe o ames elapsed o he ob j ec o ad ance one pixel (assuming ha i mo es a a con- s an speed), and Vy is he numbe o pixels passed o e pe ame elapsed, one is he in e se o he o he . How- e e , he e is one mo e de ail, i he objec mo es o he igh he NADI dec eases in his di ec ion, he e o e Dx is nega i e; howe e , he eloci y is posi i e in ha di- ec ion. Acco ding o his, he ela ionship be ween he componen s o he eloci y and o he di e ence image g adien is, 1 Vx: = - -; Vy = -- Dx Dy (7) In o de o make his g adien calcula ion mo e obus , he pixel's 8-neighbou s will be aken in o accoun , using he Sobel masks. In his way, an app oxima ion o he g adien is shown in he ollowing equa ion, D __ Sobelx . x -8 ' Dy = _ Sobely 8 2.3 Es ima ion o he Cen oid o he Mobile (8) Ano he me hod making use o accumula ed di e ence images will be shown. I does no y o es ima e he op ical low a each pixel, bu he cen oid o he mobile a each ins an . I implemen s a e y in ui i e idea o sol e he acking p oblem. The cen oid o he NADI egion p oduced by he mo- bile will be calcula ed, and his cen oid is assumed as an es ima ion o he eal objec 's cen oid a each in- s an . This me hod uses accumula ed di e ence images al hough he accumula ed alues a each pixel hem- sel es a e no o in e es , bu he ex ension and loca ion o he accumula ed di e ence egion. This is an app oxima ion which can be inaccu a e unde some condi ions. In Figu e 3 h ee cases a e p esen ed. (0) ,· ·w ··· · ' . . , ' , . '. . I (I) (Z) (b) (2) (I ): Objec cen iod (2 ): NADI ",si Dn cen oid (I) (c) , ~ ." .. : ... . '1 (» )( Z) Fig. 3. Cen oi d o he N ADI egion p oduced by he mob ile. (a) In his case he a ea o he NADI egion p oduced by he mobile objec is small ela i e o he objec a ea ; his causes he cen oid o he NADI egion o be a om he eal cen oid o he mobile. The g ea e he di e ence be ween he men ioned a eas he g ea e he e o . (b) This is ano he ex eme case in which he NADI egion is much wide han he mobile i sel . This case is wo se han he p e ious one, he e he disc epancy be ween he posi ion o he NADI egion cen oid and he eal objec cen oid can be e y la ge. (c) This is he bes case, he e he es ima ion is e y p ecise. The a ea o he mobile and he a ea o he NADI egion a e qui e simila . In his case he mobile occupies almos exac ly he NADI egion and because o his bo h cen oids p ac ically coincide. 262 As can be seen he p ecision o he es ima e is s ongly dependen on he quo ien NADI a ea / mobile a ea. The mos a o able case is when his quo ien is close o one. Ac ually, he si ua ion in case (a) is no inco ec om he acking poin o iew, because he obo is di ec ed in on o he objec . 2.4 Res ic ions o Di e ence Based Me hods The me hods based on di e ences ha e se e al es ic- ions such as: • The ange o in ensi ies o he mobile mus no change oo much h oughou he p ocess. This means ha he e canno be signi ican illumina ion di e - ences along he pa h ollowed by he mobile. • I he e is a signi ican a ea o in e e ence he al- go i hms con inue wo king well, p o ided ha he mobile does no pass o e hose egions which in- e e e. • The eloci y o he mobile should be as li le a i- able as pOSSible, a leas du ing each accumula ion cycle, o he op ical low es ima ion me hod (Sec- ion 2.2). ' • The me hod o es ima ing op ical low is a ec ed by i egula i y in he objec s' shape, while he cen oid es ima ion me hod (Sec ion 2.3) is indi e en o his aspec . 3. PROPOSED METHOD OF ACCUMULATED DIFFERENCES The p oposed me hod consis s o es ima ing he cen oid o he mobile using accumula ed di e ences (NADI). S a ing om his, he absolu e posi ion o he mobile in he image (mo e p eCisely, he posi ion o i s cen oid) can be es ima ed. P o ided ha he aim is o keep he objec cen e ed, he displacemen which should be ap- plied o he came a is gi en by he di e ence be ween he posi ion o he cen oid and he coo dina es o he image cen e . The displacemen ec o hus ob ained is ans o med in o he uni e sal e e ence sys em, and he obo is o - de ed o displace he came a acco ding o he esul ing ec o . The gene al s uc u e is shown in Figu e 4. ~lO'" p O"" ='li( :::: '" ...:..+ * _---' un un Olge L- __ ..::: "," :::ima:::'::;:: c<l = SlI ::.:; iu ::... n --, I Q l icoll nuw ~ ______ ~ un in la.:,.'" . c. ... ima iu n Fig. 4. B loc k diag am o he ac k ing p o c ess . In h e acking p ocess an adjus men o he a io be- ween pixels and dis ance in he eal wo ld (le 's call his a io he scale ac o ) is p e iously equi ed. I his ac- o is no accu a ely known, o i he dep h o he objec ayec o y is no cons an , ela i e o he came a plane o mo ion, i can be es ima ed and adap ed on line. I is simple o use he look-and-mo e app oxima ion. Tha is, he obo emains mo ionless while he secuence o n consecu i e images ( he i s o which is he e - e ence ame in equa ion 4) is being g abbed. O he - wise, mo ion in o ma ion is gene a ed due o he came a mo emen , in addi ion o he objec mo ion. This unde- si ed in o ma ion a ec s o he in e e ence egions oo , and mus be emo ed making neccesa y a e y p ecise calib a ion o he scale ac o . The main ad an age o his me hod in ela ion o he use o simple bina iza ion is ha i can cope wi h ion- pe ec ly s uc u ed scenes. Tha is, he e can be some backg ound a eas which ha e he same in ensi y ange as he objec o in e es . 4. SIMULATIONS AND EXPERlMENTAL TESTS In o de o es he p oposed me hod, in he i s place simula ions using simple syn he ic images ha e been ca - ied ou . The poin (0 , 0) , he o igin o he g aphs which a e p esen ed, is he poin which occupies he cen e o he came a a he momen when acking begins. Fi s ly he beha io in he ideal case is analysed. The ideal condi ions a e gi en by: • Mobile objec o egula shape ( ec angula ). • Cons an eloci y o he mobile. (a exac ly 1 pixel pe ame owa ds he igh and down: (1 , -1)). • The scale ac o used by he algo i hm has i s eal alue. In ollowing examples he e ec o using an inexac scale ac o is shown (so, a de icien cali- b a ion o his pa ame e will be simula ed). In all he simula ed examples, he s a ing poin s o he ajec o ies a e he same: he objec cen oid a ( -16 , 10 ), and he came a cen e a (0,0). The ajec- o y o he mobile is ep esen ed by a con inuous line and he cen e o he came a by a dashed one. Figu e 5 shows he ajec o ies om a simula ion o he gi en condi ions. Figu e 6 shows he y-coo dina es o he mobile and came a cen e , co esponding o hose ajec o ies. Figu e 7 shows he esponse when a sudden change in he mobile ajec o y a ame numbe 30 is gi en. The mobile changes om a displacemen in a sou h-eas di- ec ion o a no h di ec ion. The same ajec o y is shown in Figu e 8 bu using scale- ac o au oma ic adjus men . 263 o · -10 Fig. 5. T aje c o i es using h e p op osed m e hod unde idea l c ond i ions. ~ -~--------------------~ Fig. 6. Y -co o dina. es usin g he p op osed me h od unde ideal cond i ions. I can be seen how h e changes in he ajec o y a ec his me hod. -10 Fig. 7. T a jec o ie s unde ide al condi i on s, in he p esence o a su dd en ch an ge in h e a j ec o y. -10 ~ -20 _10 i I ! 10 20 30 Fig. 8. T aje c o i es usi ng h e s cale- a.c o ad ju s men me hod . Figu e 9 p esen s he . ajec o ies when using he algo- i hm wi hou scale- ac o co ec ion mechanism, and using a scale ac o wice i s eal alue. "' . Fig. 9. T ajec o ies in he case o a sys em ill-calib a ed , wi hou scale- a c o co ec ion mechanism . Figu e 10 shows a compa ison o he ho izon al coo di- na es, when au oma ic co ec ion o he scale ac o is made and when i is no made. I can be seen ha co - ec ing he scale ac o imp o es he acking when he sys em is no well-calib a ed. -- , -~ i ~~ ] ~ .. : ------- I -"O ;-:-~-;20--;":---:";---:'SO;;---=----'7::-0 ----=" Fig. 10 . Compa ison o he X-coo dina es wi h and wi h ou adjus men o he scale ac o . In iew o he simula ion esul s, a eal es has been made using he p oposed me hod wi h cons an scale ac o and calib a ing he sys em be o e he es . The componen s used we e: • A PUMA 560 obo . • A CCD came a a ached o he end-e ec o o he obo . • A pe sonal 486 compu e wi h: • A Ma ox boa d model Image-1280, o image p o- cessing. In he nex igu es, con inuous lines ep esen he cam- e a mo ion, and do ed lines he objec mo ion. Fig- u e 11 shows he ajec o ies and Figu e 12 shows he espec i e y-coo dina es. I can be seen how he ob ained esul is qui e good, aken in o accoun ha he objec was mo ing a abou 80 pixels/second (mos o he ime he eloci y was con- s an ). 264 '" 1 ·so ·, so .>00 ."" ·'00 ... ." Fig. 11. T ajec o ies o a . ·cal l's o he ack ing algo i hm . ... ' so so ... - .00 .150 0 " " 2S Fig. 12. V -c oo dina es co esponding o he abo e ajec o ies . 5. CONCLUSIONS In his a icle a me hod o es ima e he op ical low based on he accumula ed di e ence echnique has been p esen ed. The p oposed me hod has been es ed by sim- ula ion and expe imen a ion o ack an objec in eal ime, using a PUMA 560 obo wi h a came a in i s inal e ec o . 6. REFERENCES AlIen P. K. , A. Timcenk o, B. Yoshimi (1993). Au oma ed acking and g asping o a mo ing objec wi h a obo ic hand-eye sys em. IEEE T ans. on Robo ics and Au oma ion Vo1.9, pp.152-165. Balla d D.H ., C.M. B own (1982). Compu e Vision. P en ice-Hall. En glewood Cli s, N.J. Fu K.S., R. C. Gonzci1 ez, C.S.G. Lee (1986). Robo ics: Con ol, Sensing, Vi.sion and In elligence. McG aw- Hill. Hashimo o (1993). Vi.mal Se oing. Wo ld Scien i ic. Ma in W.N., J.K . Agga wal (1988). Mo ion Unde - s anding. KAP (Kluwe Academic Publishe s ). Papanikolopoulos N.P.. P.K. Khosla (1 993 ). Adap- i e obo ic isual acking: Theo y and expe i- men s. IEEE T a nsac ions on Au oma ic Con ol Vo1.38, pp.429-445. Va gas, M. (1997 ). Bina izacion op- ima de imagenes basada en his og ama. In e nal Repo , GAR 199 7/02 .