Visual Tracking Based on Accumulated Differences

Copyright co IF AC Intelligent Components and Instruments for Control Applications, Annecy, France, 1997 VISUAL TRACKING BASED ON ACCUMULATED DIFFERENCES 1 Manuel Vargas and Francisco R. Rubio Dpto. Ingenieria de Sistemas y Automatica Escuela Superior de Ingenieros Avda. Reina Mercedes sin, 41012-Sevilla (Spain) Tel: 34-5-4556855, Fax: 34-5-4556849, E-mail: [email protected] Abstract. This article presents an algorithm for tracking an object using a robot provided with a camera in the final effector. Simple methods are studied for estimating the optical flow based on accumulated differences which permit tracking in real time. The study is first realized by simulation and then the best results are tried experimentally. Keywords. Robotics, Image processing, ViSual motion, Optical flow, Tracking. 1. INTRODUCTION This article is centered on the analysis of the tracking problem linking a vision system and an articulated arm by the adaptation of a camera in the final effector of the arm (this is termed eye-in-hand configuration). The following problem is posed: "Observing an object on the visible scene, compensate its displacements in such a way that it always occupies the same position in the image" (preferably at the center). The information about the movement achieved from a sequence of images can be characterized by the so called optical flow (Ballard D.H., 1982). The optical flow is a consequence of the relative movement between the camera and the objects on the scene. Several techniques for estimating the optical flow have been developed (Martin W.N., 1988), (Fu K.S., 1986), (PapanikolopoulosN.P .. , 1993), notable amongst them being the techniques based on the intensity function gradient. Such techniques are based on the so called gradient constraint equation, which relates at every pixel, the space-time gradient to the velocity vector associated to that pixel. There are also 1 The authors would like to thank to CICYT for supporting this work under grant TAP 95-0370. 259 SOme studies combining stereoscopy with the optical flow detection (AlIen P.K., 1993). In their original form, all these algorithms are very restricted. On one hand, they assume that any change of the intensity function at each pixel is only due to the movement. On the other hand, they require images without discontinuities in space and time. Many mono-camera visual tracking algorithms try to detect and follow well-known objects, which have some visual features, the position of each is accurately known relative to an object coordinate system (Hashimoto, 1993). The tracking process establishes strong impositions in real time because an immediate response to the displacements of the object is needed. This article presents a method based on the accumulated difference technique, which allows for a rapid response using not too powerful hardware. In this method the interest is centered in detecting and tracking an object without a previously defined shape or structure. We are just focused to objects which are distinguible from the background and which are moving (since the purpose is to track moving objects, the motion itself will be used as a differenciating property). Hence, our purpose is to track arbitrary shaped moving spots in two dimensions. 2. OPTICAL FLOW The first approximation for creating a difference image (Fu K.S.: 1986) is based on the criterion expressed in the equation, ADJ j(x, ) = { 1 if IJ(x ,y ,t j) -I(x , y, tj )1 > 6; (tj > tj) }l ) J Y 0 otherwise ; The new image, called ADI (Absolute Difference Image) is the result of a comparison between two frames (grabbed images) successive in time, the first one taken at ti and the second one at tj. This difference between the intensity of the pixel before and afterwards is considered significant or negligible, depending on the threshold value used (8). Thus in the ADI image those pixels of the differences resulting from the movement will appear as ones, and also those due to noises which cause a change of intensity superior to the e threshold. The small areas of 1 's which appear can be due to noise or to real but insignificant differences, are eliminated by techniques of erosion and posterior dilation of the image objects; this will also regularize the shape of said objects (as said before, the exa ct object's shape is not of interest). Th e set of pixels of the mobile object which take up new positions in the image which previously belonged to the background, will be called the leading edge of the object. The set of pixels of the mobile which leave positions which previously were occupied by the object will be called the leaving edge of the object. The ADI image will show both the object's leading edge and leaving edge as 1 ' so However it is often more interesting to o btain in a difference image only one of these edges. This leads us to two new types of difference images. Th e wa y of calculating both is given by the equations, PD1 i ( x. ' ={l ifI (x ,y,t;) -I (x ,y,t j» 6; (tJ > t;) } J ' y ) 0 ot herwise; (2) , VDJ , I X . ) = {l if - (I (x , y,t ;J - I(x ,y,t j)) > 6: (tj > ti ) } J \ ' Y 0 otherWlse; This formulation does not ensure that one edge or the other is obtained independently. This is only true when the range of intensities of the mobile is higher than the one of th e background (in this case PDI provides the leaving edge and NDI the leading edge), or when the intensity range of the mobile is lower than the one of the ba ckground (PDI gives the leading edge and NDI the lea\'ing one ). However this situation deteriorates if the ran ge of the object 's intensities is higher than the background's in some areas and lower in others. 260 2.1 Alternative Formulation of the Difference Method Let's suppose the intensity range of the mobile is known: r = [i m in ' . . ima", l (even if this range is not known from the beginning, it can be estimated taking advanta ge of the motion of the object of interest, see (Vargas, 1997)), In order to obtain an image with the leading ed ge and separately another with the leaving edge the foll owing formulation can be used: PDI (x ) = {l if I (x ,y, tj) ET and I (x ,y ,t j) !f. T; (tj > td } 'J ' y 0 otherWise; N DI (x ) ={l ifI (x,y,t ;J !f.TandI (x , y, t j) ET ; (tj >t;) } 'J ,y 0 otherWise; ADI. " (x, ) = { 1 if P Dl jj (x , y) = 1 or N DJjj (x , y) = 1: (t; > t ;) J Y 0 ot herWise; whatever the relationship between the intensities of the background and those of the mobile might b e. In this case it is unimportant that in some regions the intensities of the mobile are above and in other regions below those of the background. The only problem which may arise is if there are intensities of the background within the r range, because in this case it is not possible to distinguish what is background and what is object; these regions will be called interference regions. Actuall y, these regions have no effect during tracking so long as the mobile does not pass over any of them . up to now, the difference images have been obtain ed u sing only two consecutive images. However, what is usually used is the so called accumulated difference method. In this method a first image (l o) is taken as a referen ce: R; and the following n frames are all compared to R and are accumulated on top of the same resultant image. ~ext , the new reference to be used for the follov ,' ing n frames is taken: and so on. Thus , the equations will now be like: N DI (x ) ={ 1 ifR (x ,y) !f.randI(x , y,t j) ET :} (4 ) J ' Y 0 otherWise; The fact that th e se simple differences are accumulated can be expressed by th e equation, N ADln (x, y) = L .l VDI J(x ,y) (5) J =I Thus the PADI (Positive Accumulated Diff eren ce Image), NADI (Negative Accumulated Difference Imag e) and AADI (Absolute Accumulated Difference Image ): images arise. The PADI indicates: for each pixel on which the object was in the reference frame, the number of frames (from the reference) in which the object has been abse nt from this pixel. Th e l'\ADI indicates the number R) offrames (from the reference) in which this pixel, which initially was not occupied by the object, has been occupied by said object. Figure 1 illustrates these concepts with an example. It shows a mobile being displaced at the rate of 1 pixel/frame to the right. (R ) (R) (I) (2) m (4) ~ I) l (2) 0> (4) (I) . ~~ Cl> P) 4 3 2 I ~~. Lmrn : : :: 4 ) 2 I 4 3 2 I 4 3 2 I (a) ..... __ .... .. _- (b) (R): object posi ti on in che reference frame (n): object posi ti on in the n·ch frame (c) Fig. 1. (a) PADI differ ence s. (b ) NADI di fference s. (c) AADI differences . This information about the number of frames in which there was no object (for the PADI) or there was it (for the NADI) is translated into the number of frames elapsed since the object left (for the PAD!) or reached (for the NADI) said pixel, (this second interpretation of the accumulated differences allow, as will be seen, the velocity information to be obtained). However, this interpretation is not valid, for example, if the mobile is very small in relation to the number of frames which are accumulated. Let 's suppose, for instance, the object in Figure 2, paying attention to the pixel (x, y) showed, and calculate the NADI which would be generated over this pixe!. In case (a), in which the object moves to the right at the rate of one pixel per frame, the object begins to be over (x , y) when frame 3 is taken , and in all the following frames the point will continue to be occupied by the objec t; therefore, starting from frame 3 the value accumula ted over the pixel is increased by 1 for each frame taken. At t he end N ADI (x, y) = 5 is obtained; and this coincides w ith the number of frames grabbed since the pixel was occupied. (R) (I) (2) (3) (4) ( S) ( 6) (7) (R) (I ) (2) (3) (4) (5) ( 6) (7) rl,, \ \jif" 'n,, \\jiY ~ ;;~ " " , y ; ; ;", (x. y) (R ): Object posi ti on on the reference frame (n): Ob ject po';tion on the n ·t h frame Fig . 2. Object movi ng at 1 pixel / frame towards the right. (a ) W ide obje ct . (b) T hin o bjec t . Let 's now look at case (b) of Figure 2 in which the object is specially narrow. The pixel is only occupied by 261 the mobile during frames 3 and 4, therefore the value finally accumulated in N ADI (x, y) is 2. However, at the end, the number of frames elapsed since the pixel was occupied is 5 ( the same as in case (a)). This inconvenient is almost overcome in the veloci ty extraction process, given that the difference between the values accumulated in a pixel and its neighbors and not the absolute values are considered, as will be shown in the next section. It is convenient to point out a significant difference between PADI and NADI; It is obvious that both stop growing when the object stops, but the PADI also stops growing when the object completely quits the area it was occupying on the reference image. This point c an be used, for example, to extract static images from images on which, from the beginning, there are mobile objects. 2.2 Optical Flow Starting from Accumulated Differences The optical flow field (the field of velocities at each pixel) can be obtained from an image of accumulated differences. We are going to present this deduction starting from the N AD 1. The image containing the NAD! will be called D for short throughout this deduction. If, as said before, it can be assumed that the differences accumulated at every pixel can be taken as the number of frames elapsed since the object occupied the pixel then , D(x+ 1, y) -D(x, y ), represents the number of difference frames from when the object occupied the position (x, y) until it occupied (x + 1, y). Given that a discrete approximation to the derivative is a difference quotient, the following equation can be written , 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 horizontal component of the velocity v'" is the number of pixels passed over horizontally per frame elapsed ( the time unit is the frame). We can define the Vy component in the same wa y. If Dx is the number of frames elapsed for the ob j ect to advance one pixel (assuming that it moves at a constant speed), and Vy is the number of pixels passed over per frame elapsed, one is the inverse of the other . However, there is one more detail, if the object moves to t he right the NADI decreases in this direction, therefore Dx is negative; however, the velocity is positive in t hat direction. According to this, the relationship between the components of the velocity and of the difference image gradient is, 1 Vx: = - -; Vy = -- Dx Dy (7) In order to make this gradient calculation more robust, the pixel's 8-neighbours will be taken into account, using the Sobel masks. In this way, an approximation for the gradient is shown in the following equation, D __ Sobelx . x -8 ' Dy = _ Sobely 8 2.3 Estimation of the Centroid of the Mobile (8) Another method making use of accumulated difference images will be shown. It does not try to estimate the optical flow at each pixel, but the centroid of the mobile at each instant. It implements a very intuitive idea to solve the tracking problem. The centroid of the NADI region produced by the mobile will be calculated, and this centroid is assumed as an estimation of the real object's centroid at each instant. This method uses accumulated difference images although the accumulated values at each pixel themselves are not of interest, but the extension and location of the accumulated difference region. This is an approximation which can be inaccurate under some conditions. In Figure 3 three cases are presented. (0) ,· ·w ··· · ' . . , ' , . '. . I (I) (Z) (b) (2) (I ): Object centriod (2 ): NADI ",si Dn centroid (I) (c) , ~ ." .. : ... . '1 (» )( Z) Fig. 3. Centroi d of t he N ADI region produced by t he mob ile. (a) In this case the area of the NADI region produced by the mobile object is small relative to the object area ; this causes the centroid of the NADI region to be far from the real centroid of the mobile. The greater the difference between the mentioned areas the greater the error. (b) This is another extreme case in which the NADI region is much wider than the mobile itself. This case is worse than the previous one, here the discrepancy between the position of the NADI region centroid and the real object centroid can be very large. (c) This is the best case, here the estimation is very precise. The area of the mobile and the area of the NADI region are quite similar. In this case the mobile occupies almost exactly the NADI region and because of this both centroids practically coincide. 262 As can be seen the precision of the estimate is strongly dependent on the quotient NADI area / mobile area. The most favorable case is when this quotient is close to one. Actually, the situation in case (a) is not incorrect from the tracking point of view, because the robot is directed in front of the object. 2.4 Restrictions of Difference Based Methods The methods based on differences have several restrictions such as: • The range of intensities of the mobile must not change too much throughout the process. This means that there cannot be significant illumination differences along the path followed by the mobile. • If there is a significant area of interference the algorithms continue working well, provided that the mobile does not pass over those regions which interfere. • The velocity of the mobile should be as little variable as pOSSible, at least during each accumulation cycle, for the optical flow estimation method (Section 2.2). ' • The method of estimating optical flow is affected by irregularity in the objects' shape, while the centroid estimation method (Section 2.3) is indifferent to this aspect. 3. PROPOSED METHOD OF ACCUMULATED DIFFERENCES The proposed method consists of estimating the centroid of the mobile using accumulated differences (NADI). Starting from this, the absolute position of the mobile in the image (more preCisely, the position of its centroid) can be estimated. Provided that the aim is to keep t he object centered, the displacement which should be applied to the camera is given by the difference between the position of the centroid and the coordinates of the image center. The displacement vector thus obtained is transformed into the universal reference system, and the robot is ordered to displace the camera according to the resulting vector. The general structure is shown in Figure 4. ~lO'" p O"" ='li( :::: '" ...:..+ * _---' un un Olge L__ ..::: "," :::ima:::'::;:: c<l = tSlI ::.:; iu ::... n --, I Qrlticoll nuw ~ ______ ~ un in la.:,.'"t. c. ... imatiu n Fig. 4. B loc k diag ram of the t r ac k ing pro c ess . In th e tracking process an adjustment of the ratio between pixels and distance in the real world (let's call this ratio the scale factor ) is previously required. If this factor is not accurately known, or if the depth of the object trayectory is not constant, relative to the camera plane of motion, it can be estimated and adapted on line. It is simpler to use the look-and-move approximation. That is, the robot remains motionless while the secuence of n consecutive images (the first of which is the reference frame in equation 4) is being grabbed. Otherwise, motion information is generated due to the camera movement, in addition to the object motion. This undesired information affects to the interference regions too , and must be removed making neccesary a very precise calibration of the scale factor. The main advantage of this method in relation to the use of simple binarization is that it can cope with rionperfectly structured scenes. That is, there can be some background areas which have the same intensity range as the object of interest. 4. SIMULATIONS AND EXPERlMENTAL TESTS In order to test the proposed method, in the first place simulations using simple synthetic images have been carried out . The point (0 , 0) , the origin of the graphs which are presented, is the point which occupies the center of the camera at the moment when tracking begins. Firstly the behavior in the ideal case is analysed. The ideal conditions are given by: • Mobile object of regular shape (rectangular). • Constant velocity of the mobile. (at exactly 1 pixel per frame towards the right and down: (1 , -1)). • The scale factor used by the algorithm has its real value. In following examples the effect of using an inexact scale factor is shown (so, a deficient calibration of this parameter will be simulated). In all the simulated examples, the starting points of the trajectories are the same: the object centroid at ( -16 , 10 ), and the camera center at (0,0). The trajector y of the mobile is represented by a continuous line and the center of the camera by a dashed one. Figure 5 shows the trajectories from a simulation for the given conditions. Figure 6 shows the y-coordinates of the mobile and camera center, corresponding to those trajectories. Figure 7 shows the response when a sudden change in the mobile trajector y at frame number 30 is given. The mobile changes from a displacement in a south-east direction to a north direction. The same trajector y is shown in Figure 8 but using scale-factor automatic adjustment. 263 o · -10 Fig. 5. Tr aje c tor i es using th e prop osed m ethod under idea l c ond itions. ~ r-~--------------------~ Fig. 6. Y -co ordina.tes usin g the pr op osed met h od under ideal cond itions. It can be seen how th e changes in the trajectory affect this method. -10 Fig. 7. Tra jec torie s under ide al conditi on s, in t he presence of a su dd en ch an ge in th e tra j ect ory. -10 ~ -20 _10 i I ! 10 20 30 Fig. 8. Traje ct o ri es usi ng th e s calef a.c tor ad ju st ment method . Figure 9 presents the t.rajectories when using the algorithm without scale-factor correction mechanism, and using a scale factor twice it s real value. "' . Fig. 9. Trajectories in the case of a system ill-calibrated , without scalefa ct or correction mechanism . Figure 10 shows a comparison of the horizontal coordinates, when automatic correction of the scale factor is made and when it is not made. It can be seen that correcting the scale factor improves the tracking when the system is not well-calibrated. -- , -~ i ~~ ] ~ .. : ------- I -"O ;-:-~-;20--;":---:";---:'SO;;---=----'7::-0 ----=" Fig. 10 . Comparison of the X-coordinates with and wi th out adjustment of the scale factor . In view of the simulation results, a real test has been made using the proposed method with constant scale factor and calibrating the system before the test. The components used were: • A PUMA 560 robot. • A CCD camera attached to the end-effector of the robot. • A personal 486 computer with: • A Matrox board model Image-1280, for image processing. In the next figures, continuous lines represent the camera motion, and dotted lines the object motion. Figure 11 shows the trajectories and Figure 12 shows the respective y-coordinates. It can be seen how the obtained result is quite good, taken into account that the object was moving at about 80 pixels/second (most of the time the velocity was constant ). 264 '" 1\ \ ·so ·, so .>00 ."" ·'00 ... ." Fig. 11. Trajectories for a . ·cal tl'st of the t rack ing algorithm . ... ' so so ... - .00 .150 0 " " 2S Fig. 12. V -c oordinates cor responding to the above trajectories . 5. CONCLUSIONS In this article a method to estimate the optical flow based on the accumulated difference technique has been presented. The proposed method has been tested by simulation and experimentation to track an object in real time, using a PUMA 560 robot with a camera in its final effector. 6. REFERENCES AlIen P. K. , A. Timcenk o, B. Yoshimi (1993). Automated tracking and grasping of a moving object with a robotic hand-eye system. IEEE Trans. on Robotics and Automation Vo1.9, pp.152-165. Ballard D.H ., C.M. Brown (1982). Computer Vision. Prentice-Hall. En glewood Cliffs, N.J. Fu K.S., R. C. Gonzci1 ez, C.S.G. Lee (1986). Robotics: Control, Sensing, Vi.sion and Intelligence. McGrawHill. Hashimoto (1993). Vi.mal Servoing. World Scientific. Martin W.N., J.K . Aggarwal (1988). Motion Understanding. KAP (Kluwer Academic Publishers ). Papanikolopoulos N.P.. P.K. Khosla (1 993 ). Adaptive robotic visual tracking: Theory and experiments. IEEE Tra nsactions on Automatic Control Vo1.38, pp.429-445. Vargas, M. (1997 ). Binarizacion optima de imagenes basada en histograma. Internal Report, GAR 199 7/02 .