机器人资料-论文-021-A Biprocessor-Oriented Vision-Based Target Tracking System.pdf

500ieee transactions on industrial electronics, vol. 49, no. 2, april 2002 a biprocessor-oriented vision-based target tracking system raphal canals, anthony roussel, jean-luc famechon, and sylvie treuillet abstractthe design and realization of a vision-based target tracking system is proposed. the objective is to derive the orienta- tion of a pan-tilt camera fitting a drone in order to track a target and to maintain its position in the middle of the image. image data and drone attitude are the only information available for the camera control to be achieved correctly. this embedded system requires low-cost hardware for surveillance or attack drone appli- cations: a digital signal processor for the image processing, and a microcontroller for the camera control. to ensure real-time video operation, an algorithmic solution integrating a successive-step and multi-block search method is implemented, thus allowing complex target displacements. the microcontroller uses this information to manage the camera orientation. experiments have been conducted in real conditions and acceptable target tracking results have been obtained on the prototypal hardware. index termsdigital signal processor, machine vision, mobile robots, pattern matching, real time systems, search methods, tracking. i. introduction t he problem of target tracking has already been treated in various forms and has led to the development of many methods in the fields of automated vehicle guidance, robotics, or industrial automation. however, the resulting solutions are computationally intensive, which causes problems when implementing these methods on systems designed to run autonomously. this autonomy implies constraints such as dimension or consumption, in addition to those of real-time video operation. the processing of sequences that must be achieved here aims tofollowthedisplacementofaparticularobjectwithoutapriori knowledge by a motion analysis in the successive images. two different approaches can be used to determine motions in the image. the first one uses an optical flow method to provide a direct extraction of the retinal motion field by considering the brightness between two successive images 5, 14, 29. methods using this approach are not only complex but particu- larly expensive in computational load. manuscript received april 28, 2001; revised november 12, 2001. abstract published on the internet january 9, 2002. r. canals and s. treuillet are with the laboratory of electronics, signals, images (lesi), university of orlans, orlans 45067, france (e-mail: raphael.canalsuniv-orleans.fr). a. roussel was with cac systmes, chapelle-vendmoise 41330, france. he is now with faiveley transport company, la ville aux bois 37700, france (e-mail: ). j.-l. famechon was with cac systmes, chapelle-vendmoise 41330, france. he is now with g-tech, montoire 41800, france (e-mail: jlfg-tech.fr). publisher item identifier s 0278-0046(02)02872-1. the second approach uses primitive or block matching, im- plementing the technique of correlation 1, 4, 21, 30, 38. each position of a block is tested inside a predefined search zone by using a difference measurement. in the literature, the block matching technique is principally used in motion estima- tion schemes for video transmission, especially for low bit-rate coding (h261 7, mpeg 28). thus, displacements of objects moving in an image sequence can be measured and used to pre- dict the content of frames later in the sequence. the basic tech- nique consists of dividing each image into a fixed number of squareblocks,andforeachblockinsearchingthebestmatching block in the reference frame over an area that allows for the maximum translation that the encoder can use 17. the com- putational load of this exhaustive search is very heavy and in- fluences the processing speed. to improve performance, sev- eral different concepts can be taken into consideration. besides the hierarchical methods 11, 16, 22, the specific reduction of the search position number is a possibility to accelerate the search 6, 17, 37. this acceleration can also be obtained by reducing the number of pixels for which the matching criterion is computed 26. to improve the tracking results, some authors optimize the dimension of the windows by minimizing the matching uncertainty 30. the partial occultation problem has been solved in 4 and 38 with nonparametric methods, whereas some robust methods are proposed in 21. in 3, an adjustment using a global two-dimensional (2-d) motion model has been introduced to achieve better results in difficult conditions. the tracking of targets and the prediction of their positions in the following image can be achieved simply or by the use of kalman filters 35. block matching implementations are numerous, principally for motion estimation applications. because the techniques em- ployed in the algorithms are regular, they are well suited to a mapping onto systolic arrays 10, 15, 23, 31. some au- thors propose neural architecture 33, 34 or more complex systems 24. inthetargettrackingsystemwehavedeveloped,thehardware architecture is based on two processors, one for the image pro- cessingandtheotherforthecameracontrol.contrarytothepre- vious systems, our architecture has a quite simple design to pro- vide a low-cost embedded system. this constraint leads to the drastic reduction of the number of search positions in the block matching method with respect to the video rate. another inno- vation of our approach is the multiblock technique for tracking deformableobjets.thislow-costembeddedsystemnevertheless allows robust tracking without a learning phase. 0278-0046/02$17.00 2002 ieee canals et al.: a biprocessor-oriented vision-based target tracking system501 the aim of this paper is to present this vision-based target tracking system. first, different matching criteria are detailed and a choice is made to use the one that best corresponds to our application. to reduce the computational load, several suc- cessive-step search methods are proposed. then a multiblock model of the object to be tracked is proposed. a description of theoverallsystemismadeaswellasofthehardwareimplemen- tation. promising results from experimental verifications of the system are shown and discussed. finally, some conclusions are drawn and future lines of research are presented. ii. trackingproblem a. matching criteria to estimate the target position in image a at instantfrom information in image b at instant, the block including the target at instantis compared with a set of blocks in image a in order to determine the best matching. two methods can be implemented to estimate the most probable target position at instant: the maximum intercorrelation and the minimum in- terdifference methods. although the robustness of the interdif- ference method depends on the complexity of images and of the model followed, its use is less expensive than the intercorrela- tion method in time (no problem of result normalization). for the interdifference method, the mean square difference (msd) and the mean absolute difference (mad) are the most common criteria used in the literature. two other criteria are sometimes used, the pdc criterion 8 and the integral projec- tion (ip) function 18, but the first is difficult to use and the second is expensive in computation time. the msd is formalized in the following equation, consid- ering a target of size: thefunction is more commonly called mean square error (mse), the average quadratic error. the higher the msd function is, the better the matching is. the mad is similar to the msd, except that we sum the absolute value of the differ- ence instead of the square. this function is also called mean absolute error (mae) by many authors 9, 20, 25. there is, according to 2, relatively little difference between the msd and the mad. the mad seems to be less expensive in computational load, but the presence of an absolute value can be a problem in com- parison with a squared difference. indeed, the mad requires three instruction cycles for each point, whereas the msd can be executed in only two cycles on certain processors such as dig- ital signal processors (dsps) having the multiplication and ac- cumulation (mac) instruction. this is why we have chosen the floating-point dsp tms320c31 of texas instruments to make the simple image processing unit which computes the msd. b. search methods considering every candidate block within a search zone as a potential matching represents an exhaustive search. as this search is very expensive in computation time, we must fig. 1.principle of the search method implemented in the dsp. decrease significantly the number ofto be computed in order to determine the minimal value. the first tests on the dsp tms320c31 we use show that a number of 30satisfies the video rate. accordingly, a hierarchical search method is implemented in our dsp in order to reduce computational complexity (fig. 1). some values ofare computed, initially, according to a rather large pixel grid, then the search is refined progressively in the promising zones corresponding to the minimum of thefunction. first, a cross-wise search model is used (positions). next, two positionsare explored on both sides of theminimum with the same step. then the cross-wise search model is used again from the new minimum with a reduced step (positions), and so on. this strategy gives a broader search zone although 25 functions must be computed. thus, it makes it possible to converge toward the required minimum of thefunction with few iterations. the method described above is inspired by various methods found in the literature. the first one, suggested by koga and al 19, is the three step search (tss) which is certainly the sim- plest successive-step method to implement. each of the three stages consists of computing the eight functionsaround the candidate pixel, the three-pixel step being decremented at each stage. thus, 25must be computed. the two dimen- sional logarithmic (tdl) search, presented in 17, consists of computing fourinstead of eight, but the step is decre- mented only if the central point is the optimal one. the tdl has the advantage of providing a great range in the search space of the optimal candidate block, but this search is made in a non- determinist manner: this method is thus not adapted to real-time operation.theosaisahybridmethodtakingtheadvantagesof the two methods: a deterministic cycle number (tss), a rather large range and a reduced number of points to compute (tdl) 32. only two functionsare computed, successively in the horizontal and the vertical directions, and the search step is divided by 2 at each stage. thus, only 13functions must be computed. 502ieee transactions on industrial electronics, vol. 49, no. 2, april 2002 by initializing the search in the zone nearest to the block cor- responding to the searched target, we decrease the risk of deter- mining an erroneous position of the target. so, an a priori target motion prediction based on a first-degree motion model is used to initialize the search algorithm. aproblemariseswhentheblockisdefinedinahomogeneous zone. indeed, because of the noise in the image, the search for the optimal block can provide a position different from the cen- tral one, introducing motion of the target. this motion, used for the prediction of the new position in the following image, can lead to rapid divergence of the tracking algorithm which will be focused on another target. this problem is solved by taking into account a homogeneity parameter (gray-level standard de- viation) in the block. a block position stabilization is thus in- troduced thanks to a cost function: the block displacement is authorized only if the gain brought by this displacement, in the resemblance function, is higher than a threshold dependent on the homogeneity parameter. iii. multiblockmethod a. multiblock necessity the quality of the block matching depends directly on the fact that motions are translational and uniform in the image plane, which is seldom the case for real image sequences. thus, for complex target displacement, the target deformation in the image makes the matching more difficult to obtain 18, as in the case of rotation 12, 13. the combination of the various freedom degrees generates a vast target search space, resulting in a very significant computational overload. in fact, with a 40-ms video rate, motions can be regarded as weak and the search with the basic model provides an identical result, since the model is updated in each new image. however, if the target rotates, the rectangular block defining it initially can contain a growing number of points corresponding to the ground. this problem can be partly eliminated if the only block shape authorized is the square one which is almost invariant by rotation. moreover, it is easy to manipulate in a software. however, in general, a square block cannot cover the whole object without including nontarget points in the model. this block type is thus not adapted to our problem and we have then to choose a multi-block solution in which several square blocks can be used to model the target. b. basic method thetrackingsystemworksonasetofsubblocks(fig.2).this set is built during the target definition and the subblock number can vary depending on subblock tracking results. at each moment, several parameters are associ- ated with each subblock: position (), speed () and size. for each subblock , the tracking system searches, in the image at moment, the position of a block of sizelocated in the neighborhood of the point (). then a group analyzer must compute the new subblock mo- tions as well as the associated sizes. it must also authorize the system to compute the position of the whole target by consid- ering the centre of gravity of the subblock centers, enabling a fig. 2.multiblock target tracking. fig. 3.variation of the size of each subblock. correction of the local errors in the estimate of the subblock dis- placements to be made. indeed, an interaction exists between these subblocks, and certain constraints concerning their rela- tive displacements can be established. therefore, checks need to be carried out during the search of each subtarget or after, limiting the drift of one or more subblocks. thesimplestgroupanalyzerconsiderseachsubblockindivid- ually and does not take subblock enlargements or contractings intoaccount.suchananalyzerisnoteffective.theremainderof this section describes an analyzer which exploits the geometry of the subblock set more efficiently. c. group analyzer one of the objectives is to update the sizeof each sub- blocktobetrackedaccordingtotheexploitableparameters(cur- rent and previous positions and motions, and sizes at the pre- vious instant). intuitively, the sizes of the subblocks must vary in the same manner as the space between their centers (fig. 3). represents here the distance between the centers of two subblocksandat instant. the concept of homographic transformation employed in projective geometry, which pre- serves the alignment and the biratio, is used. thus, since from one image to the next the target can be regarded as not deformed and the biratio is preserved, the new size of each subblock depends on its size at the previous moment but also on the evolution of the distances between the two subblocks: . to avoid instability and to limit the computational load, the size is updated by smoothing the last size measures. as several subblocks are analyzed, this equation can be en- riched by finding the weighted average of the several ratios of distances between subblockand the others. the weight of a canals et al.: a biprocessor-oriented vision-based target tracking system503 fig. 4.system overview. subblock is all the more large since it is close to the subblock and its matching score is large. thus, if a subblock presents a very low matching, its weight is null. if this result recurs during successive images, the subblock is eliminated. because we track a deformable target, a particular precaution must nevertheless be taken to avoid noncoherent behavior of a setofsubblocks. thiscasearises, forexample,when asubblock isinitiallydefinedinthehomogeneouszone:itspositionwillnot change even if the other subblocks move. the group analyzer solvesthisproblembytestingthemotionvectorsofthedifferent subblocks. iv. description of thesystem a. system overview the target tracking system is composed of two distinct parts shown in fig. 4. thefirstpartrelatestothelandinstallation.anoperatorman- ually guides the drone until he notices a target to be tracked in the sequence of images acquired by the embedded camera and retransmitted toward the ground. with a single click on a joystick, the operator quickly defines this target. thanks to a deterministic gray-level or/and spatio-temporal segmentation algorithm based on a markov random field model 5, the re- gion corresponding to the target is immediately computed on a pc. inside this image region, the subblocks are automatically selected with a good repartition, assuming a minimum of four subblocks and a maximum of sixteen, in the limits of the com- putational possibilities of the dsp. these limits are discussed in sectionv-a.thesedataarethentransmittedtothedronewhose camera is then placed in automatic control. the heavy compu- tational load of this algorithm requires the use of a pentium iii 600 mhz equipped with a dedicated pci frame grabber, to re- spect the video rate (40 ms). the second part concerns the embedded system. to track a particular target, the operator cannot remotely pilot the drone and the camera at the same time. so the piloting is controlled by an electronic system. this must not only control the drone but also the camera so that the target to be tracked is observable by the operator during a sufficiently long