Christine Dubreu

Antoine Manzanera

Eric Bohain

Non photorealistic simulation of video sequences for an accurate evaluation of tracking algorithms on complex scenes

Keywords: Image processing, tracking, evaluation, simulation

As target tracking is arousing more and more interest, the necessity to reliably assess tracking algorithms in any conditions is becoming essential. The evaluation of such algorithms requires a database of sequences representative of the whole range of conditions in which the tracking system is likely to operate, together with its associated ground truth. However, building such a database with real sequences, and collecting the associated ground truth appears to be hardly possible and very time-consuming.

Therefore, more and more often, synthetic sequences are generated by complex and heavy simulation platforms to evaluate the performance of tracking algorithms. Some methods have also been proposed using simple synthetic sequences generated without such complex simulation platforms. These sequences are generated from a finite number of discriminating parameters, and are statistically representative, as regards these parameters, of real sequences. They are very simple and not photorealistic.

This paper shows how reliable non-photorealistic synthetic sequences are, and how the number of parameters can be increased to synthesize more elaborated scenes in order to deal with more complex target and background texture characteristics and relative motion, including 3D deformations and occlusions. These synthesized sequences are easily generated from any desired scene characteristics, and can be reliably used for tracking algorithms evaluation in any conditions.

INTRODUCTION

The success of automatic video surveillance of wide area scenes, which is currently arousing more and more interest, relies on the robustness of the tracking algorithms integrated to the systems. Thus, performance evaluation of such algorithms is becoming an increasingly important issue since it enables the developers to identify the weaknesses of their algorithms and to improve them.

For this purpose, we proposed an evaluation method, 1 in which tracking systems can be evaluated in any operational conditions (any target size, target to background contrast, velocity...) from a set of parameters describing theses conditions. The evaluation system is based on the generation of simple synthetic sequences comprising a moving target and a background. Synthetic sequences are generated from target and background texture models, dynamic deformations are applied. We want texture models and dynamic deformations to be fully characterized by a set of statistical parameters.

All the texture synthesis methods developed so far to generate textures required either a sample of the texture to be generated, or a huge list of statistical parameters from which a photorealistic texture could be obtained. In the evaluation method we proposed, we assumed that photorealism is not necessary for tracking systems evaluation purpose, and proposed to synthesize textures from a small set of parameters defining the color, coarseness, directionality, regularity of a texture.

We also chose to model the deformations by geometric models. Therefore, only a small number of parameters defining the rotation, translation and scale between two consecutive frames is required.

We proposed an extremely simple texture synthesis method to generate a simple texture from a set of parameters, and modeled dynamics of the scene by geometric deformations, also fully characterized by a small set of parameters.

The synthetic scenes generated through this method were shown to be usable for the evaluation of tracking systems on simple single-target scenes. This method enables the generation of a large number of sequences on which tracking systems can be evaluated. The parameters on which the robustness of an algorithm depend are isolated, and sequences are generated with numerous values for these parameters, giving the minimum and maximum values of these parameters for which a tracking system would be robust. Figure 1 illustrates the performance of some tracking algorithms related to the value of a parameter. The aim of this paper is to define the reliability of this sequence generation method for the synthesis of more complex scenes aimed at tracking systems evaluation. Firstly, the non-photorealistic texture synthesis method performance for generating scenes that can be reliably used for algorithms evaluation are compared to the performance of other more complex and sophisticated methods, photorealistic, but requiring a texture sample.

Secondly, a way to improve the dynamic scene generation process once the synthetic textures generated is proposed, at the cost of additional input parameters. Therefore, more complex synthetic scenes can be generated which model for example occlusions and 3D deformations.

PRESENTATION OF THE THREE TEXTURE SYNTHESIS METHODS

This section overviews the three texture synthesis methods that will be used in the synthetic scene generation and for which the performance of tracking systems will be assessed.

Non photorealistic method

In the method we want to evaluate in this paper, operational criteria taken from a real scene are turned into objective measures and used to generate a synthetic dataset, 1 non-photorealistic, but statistically representative of the sequence that has to be simulated. Indeed, the assumption is made that a minimal set of formal parameters can be defined, from which a synthetic scene likely to be used to evaluate tracking algorithms can be generated. This set is constituted of parameters defining the inherent statistical properties of the objects involved, i.e. the target and background (size, shape, histogram, texture characteristics such as coarseness, directionality, regularity...) and of parameters defining the relative interaction between these objects, and their temporal behavior (deformation, relative velocity, illumination changes...).

We concentrate on the parameters defining the inherent properties of objects to show that the minimal set we defined is sufficient for generating a scene reliably usable for our purpose. The obvious advantage of this method is that any value can be given to these operational criteria, enabling a tracking systems to be evaluated in any conditions, in particular those for which no real scene nor texture sample is available. This enables developers to define and work on the weaknesses of their algorithms, and the users of systems to circumscribe the validity domain of the algorithms they use, and to choose the one that best fits the operational conditions.

Markov Random Fields based method

The first texture synthesis method used in comparison with the non-photorealistic one presented above is the algorithm described by Li-Yi Wei, 2 which requires a sample texture as input and generates textures with a very good perceived visual quality. The algorithm is derived from Markov Random Field texture models and generates textures through a sequential deterministic searching process.

It starts with an input texture sample S and a white random noise I. The random image I is forced to look like the sample by transforming it pixel by pixel in a raster scan ordering, i.e. from top to bottom and left to right. The value of each pixel p of I is determined using its spatial causal neighborhood N (p), which is compared against all possible neighborhoods N (p i ) from S, and p is assigned the value of the input pixel p i with the most similar N (p i ). This synthesis process ensures that the local similarity between I and S is maintained. The figure 2 shows the results of this texture synthesis method from samples taken from the Brodatz 3 database. These texture samples have a high regularity, and the synthesized textures are photorealistic, since they are visually similar to the texture sample, and the regularity is kept.

Third method : Wavelet-based method

The second texture synthesis method to be compared to the non-photorealistic one is the texture synthesis method developed by Portilla & Simoncelli 4 . It is also based on the establishment of a set of statistical measurements such that two textures would be identical in appearance if and only if they agree on these measurements. These statistical measurements are extracted from a sample, and they are much more numerous since photorealism is taken into consideration.

A texture sample is first decomposed using a multi-scale oriented linear basis, from which complex coefficients are computed, as well as statistical moments of the pixel distribution, such as mean, variance, range... The number of parameters depends on the number of subbands and the size of spatial neighborhoods used.

In the examples given in this paper, a total of 710 parameters is used, but satisfactory results can usually be obtained with a small subset of these parameters, depending on the texture to analyze.

From an image of Gaussian white noise, the sample statistics of each subband of a pyramid are forced to match those of a reference image, then the image is reconstructed, and the statistics of the resulting pixels are forced to match those of the texture sample. This process is iterated several times, until convergence of the image. More details may be found in the references given below. [START_REF] Portilla | Texture Modeling and Synthesis using Joint Statistics of Complex Wavelet Coefficients[END_REF] The figure 2 also shows the results of this texture synthesis method on some texture samples extracted from the Brodatz database after 25 iterations. Again, on these highly regular samples, the regularity is kept, and the synthetic texture is visually similar to the sample one.

EVALUATION OF THE THREE METHODS

Aim

The aim of this section is to compare the reliability of each of the three texture synthesis methods of the whole synthetic scene generation process for tracking systems evaluation.

Evaluation protocol

A large number of video sequences representative of the range of operating conditions of a tracking system are taken. These sequences include some infrared and visible real sequences, taken from naval, airborne, and ground cameras, for which a ground truth has been manually generated, and the sequences extracted from the VIVID database, [START_REF] Collins | An Open Source Tracking Testbed and Evaluation Web Site[END_REF] which is a database of infrared and visible video sequences together with their ground truth aimed at evaluation of tracking systems. Samples of the target and background textures are extracted for each of these sequences. From these samples, synthetic sequences are generated using the three texture synthesis methods described in section 1, and the target is given a motion and deformation similar to the real one provided by the ground truth of the real scenes.

Only one simple-textured target is synthesized, since the aim of this comparison is to validate the assumption that photorealism is not necessary to evaluate low-level object tracking algorithms, but some multi-target sequences could be generated from several samples.

Tracking algorithms are then tested on each set of four video sequences (one real, two photorealistic, and one non-photorealistic). The performance of the tracking algorithms on each of these sequences are compared to see how reliably the synthetic ones can be used instead of the real ones for an accurate evaluation of the systems.

Algorithms

Two algorithms are used for this evaluation process: a correlation algorithm, and a centroid algorithm. The correlation algorithm relies on the use of a reference image A representing the target, and the search of the position for which the correlation value between A and a rectangular patch B in the current frame, given by (1), is maximal. The search strategy is based on a multiresolution gradient descent with a diamond pattern.

= i j (A ij -Ā)(B ij -B) i j (A ij -Ā) 2 i j (B ij -B) 2 (1)
The second algorithm is the centroid algorithm described by Albus & al, 8 in which a probability map is used to determine whether pixels belong or not to the target, and to determine the target's center of gravity. This algorithm uses concentric gates to determine relevant regions: the outer region, which contains mostly background pixels, and the inner region mostly target pixels. Then, a probability map can be computed from the smoothed histograms of these regions to segment the target :

P (k) = H I S (k) H I S (k) + H O S (k) , ∀k ∈ 0...∆ -1, (2)
where H I S and H O S are respectively the smoothed histogram of the inner and outer region, and ∆ is the number of grey levels in the image. P (k) is the probability for a pixel of intensity k to belong to the target.

Metric

A metric has to be defined for the evaluation of these tracking algorithms. A diverse range of measures and procedures to establish a performance metric has been used in tracking evaluation. [START_REF] Ellis | Performance Metrics and Methods for Tracking in Surveillance[END_REF] The choice depends on the target application, as the priorities will vary for different applications. Two metrics are used in this paper :

r 1 = n i=1 f (i) n r 2 = n i=1 σ * f (i) n i=1 f (i)
, where σ is the standard deviation of the error between the real position of the target center given by the ground truth and the position given by the algorithms all over the sequence, i is the index of the video frame, n the total number of video frames of the sequence, and f a function determining whether the target is believed to be found or not :

f (i) =
1 if the target is believed to be found at frame i 0 if the target is believed to be lost at frame i

Results

The figure 3 shows how the three texture synthesis algorithms perform to synthesize a texture image from samples of complex, often non regular and non-stationnary-textures, or from some statistical measurements taken from these samples.

Real Non photorealistic Markov-based

Wavelet-based sample synthesized texture synthesized texture synthesized texture The table 1 shows the performance of the two tracking algorithms on real and synthetic sequences for three sets of sequences representative of all the sequences used for this evaluation. The sequences used here for the evaluation of the performance of the algorithms are more complex that the sequence that were used for the validation of this method for evaluation of low-level algorithms on simple scenes. Indeed, in these sequences, the target and background textures are more complex, since they can be non-stationary, or completely irregular... It can be noticed, in the case of these more complex scenes, that the scene generation method using the non-photorealistic texture synthesis does not perform as well as methods using the photorealistic ones. This shows that, although this texture synthesis method is efficient for evaluation of tracking algorithms on scenes where target and background are simple-textured, it has its limits, and is no longer robust when the texture of the target or background becomes non-regular, or non-stationary. Therefore, it is preferable to use the photorealistic ones in these conditions, provided texture samples are available. 1. Standard deviations of the error between the position of the target given by the ground truth and by the correlation and centroid algorithms on several sets of sequences for which the target and background texture parameters are equal.

Besides, these scene generation methods are not robust when evaluating tracking algorithms on scenes with occlusions, or three-dimensional target deformations. Indeed, the very simple geometric transformation model of the motion and deformations is aimed at evaluating the performance of low level algorithms, i.e. the performance of algorithms on single-target basic sequences. Therefore, this model has to be improved by adding new parameters, characterizing the 3D deformations, and the occlusions.

IMPROVEMENT OF THE DYNAMIC GENERATION METHOD

In this section,

Basic dynamic motion modeling

Once the target(s) and background texture fields are created using this method, the target(s) field(s) are mapped on an ellipse with eccentricity and size corresponding to the input shape parameters, and superimposed to the background field. A synthetic dynamic scene is then computed in which a dynamic motion characterized by the displacement parameters defined in 2.1is given to the target and background.

A 2D deformation is applied to the target at each frame generation. This deformation is modeled by a composition of a rotation, a translation, and a scale :

x y = ρ cos θ sin θ -sin θ cos θ x y + T X T Y (3)
Therefore, the parameters θ T max , ρ T max , and T T Xmax and T T Ymax , defining respectively the maximum rotational angle, scale, and displacement of the target(s) between two consecutive frames have to be defined. Similarly, the tbackground's motion is defined by the parameters T B Xmax and T B Ymax , and its deformation by θ B max , and ρ B max .

To avoid discontinuities and re-synthesis of new pixels at each frame generation, the background texture is previously symmetrized and infinitely replicated in the x and y directions. The deformation and displacement of the background and target are generated in such a way that it is continuous; there is no sudden change in the angle of rotation, scale, or displacement vector, which is consistent with what is commonly found in real sequences.

Modeling of the 3D deformations

The displacement and deformation of the objects present in the scene were chosen to be modeled in two dimensions, since it is a good approximation of the scene dynamics between two frames. However, modeling the 3D motion and deformations of the target and background in a scene would give sequences with dynamics closer to the reality and would give better results on the performance evaluation of tracking systems. Such deformations can be modeled by a non-stationarity of the texture parameters (histogram, coarseness, directionality) : a temporal parameter is added, on which the texture parameters are indexed.

For example, a maximal variation of the histogram can be allowed between two consecutive image frames, and a value given to a temporal parameter, controlling the change in the histogram. A transformation depending on the value of the temporal parameter is then applied to the histogram, resulting in it being more or less spread. This very simple process of histogram modification is shown in figure 4 and shows how illumination changes can be modeled. Similarly,the coarseness and directionality of the texture can be indexed to a temporal parameter : between two consecutive frames, a scale can be applied to the texture, which coefficients are indexed to a temporal parameter, resulting in a coarser or finer texture.

The addition of a temporal parameter to which each of the texture parameter of the objects in the scene is indexed enables system designers to get more precise specifications on the validity domain of their algorithms, and to choose efficiently the best algorithm to use for a given application.

Modeling of the occlusions

The dynamics of the synthetic scene can also be improved by the modeling of static and dynamic occlusions, as they often occur in real scenes.

Static occlusions can be modeled by considering a discrete number of plans, and by adding a depth parameter to every point of the target or background. The probability of occlusions is linked to the number of background pixels having a smaller depth than the target. Figure 5 shows the results of a scene generation with the same textural properties, but with different probabilities of static occlusions. p = 0 p = 0.2 p = 0.4 p = 0.7 Dynamic occlusions can be modeled in the same way, by synthesizing a sequence with multiple targets, and by adding to each pixel of each target and background a depth parameter. The superimposition of all isolated targets allows the generation of a large number of sequences representing different scenarii. The duration and occurrence of the occlusions can be controlled by the motion of each of the isolated targets. [START_REF] Black | A Novel Method for Video Tracking Performance Evaluation[END_REF]

CONCLUSION AND FURTHER WORK

We have shown in this paper that the use of non-photorealistic texture synthesis in the generation of synthetic scenes for tracking system evaluation is relevant. Indeed, the performance of tracking systems on real sequences are comparable to their performance on synthetic sequences, whether they are photorealistic or not. therefore, the non photorealistic method provides us with an efficient way to quantitatively evaluate low-level object tracking methods and get their validity domain without having to use costly and heavy simulation platforms.

In order to improve high level tracking algorithms evaluation, we propose a way to model 3D deformations, and static and dynamic occlusions, and more complex target(s) and background textures. This results in an increase in the number of dynamic discriminating parameters, and enables us to get more accurate circumscription of the validity domain of tracking algorithms.

Figure 1 .

 1 Figure 1. Robustness of two tracking algorithms to the the target to background contrast change, and to the maximum target displacement and rotation between two frames

Figure 2 .

 2 Figure 2. Textures synthesized using the Markov-Based Method (second line), and using the Wavelet-Based Method (third line), from patchs from the Brodatz texture database (first line)

7

 7

  r

Figure 3 .

 3 Figure 3. Examples of texture synthesized from target and background samples extracted from real sequences

Figure 4 .

 4 Figure 4. Example of texture histogram modification between two frames

Figure 5 .

 5 Figure 5. Example of occlusions modeling, together with the probabilities of occurrence of these occlusions.


Renaud Barate
email: renaud.barate@ensta.fr

Antoine Manzanera
email: antoine.manzanera@ensta.fr

Automatic Design of Vision-based Obstacle Avoidance Controllers using Genetic Programming

The work presented in this paper is part of the development of a robotic system able to learn context dependent visual clues to navigate in its environment. We focus on the obstacle avoidance problem as it is a necessary function for a mobile robot. As a first step, we use an offline procedure to automatically design algorithms adapted to the visual context. This procedure is based on genetic programming and the candidate algorithms are evaluated in a simulation environment. The evolutionary process selects meaningful visual primitives in the given context and an adapted strategy to use them. The results show the emergence of several different behaviors outperforming hand-designed controllers.

Introduction

Obstacle avoidance is an essential function for any mobile robot. Range sensors are the most commonly used devices for detecting obstacles but the accuracy of sonars depends on the angle of reflection and the material of the detected object and laser range sensors are expensive and can be harmful. More, both are active sensors which is undesirable for military applications for instance. On the contrary, video cameras are now cheap, low consumption and high resolution sensors. Nevertheless detecting obstacles with a single camera is a difficult problem. Different solutions exist, using either optical flow or more simple contextual information, but none is generic enough to deal with changing environments.

Ideally, the robot should be able to adapt itself dynamically to the current context and to select its behavior (here, the obstacle avoidance algorithm) in real time depending on its environment. The robot would learn those most efficient behaviors only by interacting with the environment. As a first step towards this goal, we propose here an offline method based on genetic programming for the automatic design of obstacle avoidance controllers within a given environment. The next steps will be to develop a set of algorithms adapted to different environments and to design a high level controller able to select in real time the best algorithm for the current environment. Our system uses a simulation environment to test different algorithms. We will show that the evolved solutions use relevant visual primitives and that they perform better than hand-designed controllers.

Inspiration and Principles

Vision Based Obstacle Avoidance

One commonly used method to perform obstacle avoidance using a single camera is based on the calculation of optical flow. Optical flow represents the perceived movement of the objects in the camera field of view. It is commonly represented by a vector field, each vector representing the displacement of the corresponding pixel. According to the parallax principle, the perceived displacements will be greater for nearer objects when the camera has a translational movement. A simple and robust approach for obstacle avoidance is to move the robot forward for a few seconds, to calculate the mean of the optical flow on the right and left sides of the image, then to turn the robot in order to balance the flow on each side. This technique is inspired by the behavior of bees and has been successfully applied to center a mobile robot in a corridor [START_REF] Santos-Victor | Divergent stereo for robot navigation: learning from bees[END_REF][START_REF] Ebner | Centering behavior with a mobile robot using monocular foveated vision[END_REF]. More recently it has been used for the control of an autonomous helicopter [START_REF] Muratet | A contribution to vision-based autonomous helicopter flight in urban environments[END_REF][START_REF] Hrabar | Vision-Based 3D Navigation for an Autonomous Helicopter[END_REF]. However, systems based on optical flow don't cope well with thin or lowly textured obstacles.

On the other hand, simple primitives can be used to extract different informations about the image. Those include threshold, Gaussian and Laplacian filters as well as orientation and frequency filters. In many cases, combinations of some of those primitives can deliver enough information to discriminate potential obstacles. For instance, Michels implemented a system to estimate depth from texture information in outdoor scenes [START_REF] Michels | High speed obstacle avoidance using monocular vision and reinforcement learning[END_REF]. Other obstacle avoidance systems use this kind of information to discriminate the floor from the rest of the scene and calculate obstacle distances in several directions [START_REF] Horswill | Polly: A vision-based artificial agent[END_REF][START_REF] Lorigo | Visually-guided obstacle avoidance in unstructured environments[END_REF][START_REF] Ulrich | Appearance-based obstacle detection with monocular color vision[END_REF]. Nevertheless those methods suppose that the floor may be clearly discriminated and they neglect potentially useful contextual information from the rest of the scene. Ideally, a good obstacle avoidance system should be able to use any visual clue.

Vision in Evolutionary Robotics

Evolutionary techniques have already been used for robotic navigation and the design of obstacle avoidance controllers but in general vision is either overly simplified or not used at all. For instance, Harvey used a 64x64 pixels camera but simplified the input to a few average values on the image [START_REF] Harvey | Seeing the Light: Artificial Evolution, Real Vision. From Animals to Animats 3[END_REF]. Marocco used only a 5x5 pixels retina as visual input [START_REF] Marocco | Active vision and feature selection in evolutionary behavioral systems[END_REF]. A description of several other evolutionary robotics systems can be found in [START_REF] Mataric | Challenges in evolving controllers for physical robots[END_REF][START_REF] Walker | Evolving controllers for real robots: A survey of the literature[END_REF] but most of them rely only on range sensors. On the other hand, genetic programming has been proved to achieve human-competitive results in image processing systems, e.g. for the detection of interest points [START_REF] Ebner | Evolving a task specific image operator[END_REF]14]. Ebner also developed a navigation system for a robot using range sensors [START_REF] Ebner | Evolving a behavior-based control architecture-From simulations to the real world[END_REF] but he didn't combine the two approaches for a visionbased navigation system. Parisian evolution has also been shown to produce very good results for obstacle detection and 3D reconstruction but those systems need two calibrated cameras [START_REF] Pauplin | Evolutionary Optimisation for Obstacle Detection and Avoidance in Mobile Robotics[END_REF][START_REF] Olague | Parisian evolution with honeybees for three-dimensional reconstruction[END_REF].

To our knowledge, only Martin tried evolutionary techniques with monocular images for obstacle avoidance [START_REF] Martin | Evolving visual sonar: Depth from monocular images[END_REF]. The structure of his algorithm is based on the floor segmentation technique and the evaluation is done with a database of hand labeled real world image. The advantage of such an approach is that the evolved algorithms are more likely to work well with real images than those evolved with computer rendered images. Nevertheless, it introduces an important bias since the algorithms are only selected on their ability to label images in the database correctly. In our work, the vision algorithms are not limited to a particular technique and the selection is based on a functional evaluation of the algorithms, that is their ability to avoid obstacles in the simulation environment.

Material and Methods

The Vision Algorithms

Generally speaking, a vision algorithm can be divided in three main parts: First, the algorithm will process the input image with a number of filters to highlight some features. Then these features are extracted, i.e. represented by a small set of scalar values. Finally these values are used for a domain dependent task, here to generate motor commands to avoid obstacles. We designed the structure of our algorithms according to this general scheme. First, the filter chain consists of spatial and temporal filters, optical flow calculation and projection that will produce an image highlighting the desired features. Then we compute the mean of the pixel values on several windows of this transformed image (feature extraction step). Finally those means are used to compute a single scalar value by a linear combination. Several scalar values can be produced with different filter chains, these values are then combined using scalar operators. A final step will generate a motor command using the resulting scalar value(s). We extended this purely vision based algorithmic structure by adding two scalar input variables: the goal location distance and heading relative to the robot position. These variables can be used for command generation along with the other scalar values.

An algorithm is represented as a tree, the leaves being input data, the root being output command, and the internal nodes being primitives (transformation steps). The program can use different types of data internally, i.e. scalar values, images, optical flow vector fields or motor commands. For each primitive, the input and output data types are fixed. Some primitives can internally store information from previous states, thus allowing temporal computations like the calculation of the optical flow. Fig. 1 shows an example program for a simple obstacle avoidance behavior based on optical flow. Here is the list of all the primitives that can be used in the programs and the data types they manipulate:

-Spatial filters (input: image, output: image): Gaussian, Laplacian, threshold, Gabor, difference of Gaussians, Sobel and subsampling filter. -Temporal filters (input: image, output: image): pixel-to-pixel min, max, sum and difference of the last two frames, and recursive mean operator. -Optical flow (input: image, output: vector field ): Horn and Schunck global regularization method, Lucas and Kanade local least squares calculation and simple block matching method [START_REF] Barron | Performance of optical flow techniques[END_REF]. -Projection (input: vector field, output: image): Projection on the horizontal or vertical axis, Euclidean or Manhattan norm computation, and time to contact calculation using the flow divergence. -Windows integral computation (input: image, output: scalar ): The method used for this transformation is: 1. A global coefficient α 0 is defined for the primitive. 2. Several windows are defined on the left half of the image with different positions and sizes. With each window is paired a second window defined by symmetry along the vertical axis. A coefficient α i and an operator (+ or -) are defined for each pair. 3. The resulting scalar value R is a simple linear combination calculated with the following formula:

R = α 0 + n i=1 α i µ i µ i = µ Li + µ Ri or µ i = µ Li -µ Ri
where n is the number of windows and µ Li and µ Ri are the means of the pixel values over respectively the left and right window of pair i. The number of windows pairs, their positions, sizes, operator and coefficient along with the global coefficient are characteristic parts of the primitive and will be customized by the evolutionary process.

-Scalar operators (input: scalar(s), output: scalar ): Addition, subtraction, multiplication and division operators, temporal mean calculation and simple if-then-else test. -Command generation (input: scalar(s), output: command ): The motor command is represented by two scalar values: the requested linear and angular speeds. We created two operators to generate these values:

• Direct generation: The required linear and angular speeds are two input scalar values.

• Sequential moves: The movement is decomposed in straight moves and in-place rotations. This facilitates the usage of optical flow based strategies, since optical flow exploitation is more straightforward when the movement has no rotational part. This operator uses one input scalar value, which will be the angle of rotation at the end of a straight move.

Most of those primitives use parameters along with the input data to do their calculations (for example, the standard deviation value for the Gaussian filter). Those parameters are specific to each algorithm; they are randomly generated when the corresponding primitive is created by the genetic programming system described in Sect. 3.3.

Evaluation of Algorithms

For the evaluation of the different obstacle avoidance algorithms, we use a simulation environment in which the robot moves freely during each experiment. The simulation is based on the open-source robot simulator Gazebo. The simulation environment is a closed room of 36 m 2 area (6 m x 6 m) with block obstacles or furniture items depending on the experiments.

The simulation uses ODE physics engine for the movement of the robot and collisions detection and OpenGL for the rendering of the camera images. The physics engine update rate is 50 Hz while the camera update rate is 10 Hz. In all the experiments presented in this paper, the simulated camera produces 8bits gray-value images of size 320x160 representing a field of view of 120 • x 60 • . This large field of view reduces the dead angles and hence facilitates obstacle and avoidance. All the obstacles are immovable to prevent the robot from just pushing them instead of avoiding them.

In each experiment, the goal of the robot is to go from a given starting point to a goal location without hitting obstacles. For that, we place the robot at the fixed starting point and let it move in the environment during 60 s driven by the obstacle avoidance algorithm. Two scores are attributed to the algorithm depending on its performance: a goal-reaching score G 1 rewards algorithms reaching or approaching the goal location, whereas score C 1 rewards the individuals that didn't hit obstacles on their way. Those scores are calculated with the following formulas:

G 1 = t G if the goal is reached t max + d min /V else C 1 = t C
where t G is the time needed to reach the goal in seconds, t max is the maximum time in seconds (here 60 s), d min is the minimum distance to the goal achieved in meters, V is a constant of 0.1 m/s and t C is the time spent near an obstacle (i.e. less than 18 cm, which forces the robot to keep some distance away from obstacles).

We proceed then to a second run with a different starting point and a different goal location. Scores G 2 and C 2 are calculated the same way and the total scores G T and C T are obtained by adding the scores from the two runs:

G T = G 1 + G 2 C T = C 1 + C 2
The goal is hence to minimize those two scores G T and C T . Performing two different runs favors algorithms with a real obstacle avoidance strategy while not increasing evaluation time too much. The starting points are fixed because we want to evaluate all algorithms on the same problem.

The Evolution Process

We use genetic programming to evolve obstacle avoidance algorithms with the least possible a priori on the structure of the algorithm. Genetic programming, as introduced by J. Koza [START_REF] Koza | Genetic Programming: On the Programming of Computers by Natural Selection[END_REF], is the evolution of computer programs by means of artificial evolution. Like other evolutionary algorithms, it is based on a selectionbreeding process inspired by biological evolution which creates better algorithms by combining the primitives of the best algorithms of previous generations.

As usual with evolutionary algorithms, the population is initially filled with randomly generated individuals. The difficulty that arises with algorithms that use different data types is to ensure that the generated algorithms are valid. Montana introduced strongly-typed genetic programming to overcome this problem [START_REF] Montana | Strongly Typed Genetic Programming[END_REF] and Whigham extended it by using a grammar to generate the algorithms [START_REF] Whigham | Grammatically-based genetic programming[END_REF]. We decided to use this grammar-based genetic programming as it also allows us to bias the search toward more promising primitives and to control the growth of the algorithmic tree.

In the same way that a grammar can be used to generate syntactically correct random sentences, a genetic programming grammar is used to generate valid algorithms. The grammar defines the primitives and data (the bricks of the algorithm) and the rules that describe how to combine them. The generation process consists in successively transforming each non-terminal node of the tree with one of the rules. This grammar is used for the initial generation of the algorithms and for the transformation operators. The crossover consists in swapping two subtrees issuing from identical non-terminal nodes in two different individuals. The mutation consists in replacing a subtree by a newly generated one. For clarity and space reasons, we cannot present the whole derivation process here but detailed explanations can be found in the paper from Whigham [START_REF] Whigham | Grammatically-based genetic programming[END_REF]. Table 1 presents the exhaustive grammar that we used in all our experiments.

The numbers in brackets are the probability of selection for each rule. A major advantage of this system is that we can bias the search toward the usage of more Table 1. Grammar used in the genetic programming system for the generation of the algorithms.

promising primitives by setting a high probability for the rules that generate them. We can also control the size of the tree by setting small probabilities for the rules that are likely to cause an exponential growth (rules like REAL → ifThenElse(REAL,REAL,REAL,REAL) for example).

As described in the previous section, we wish to minimize two criteria G T and C T . There are different ways to use evolutionary algorithms to perform optimization on several and sometimes conflicting criteria. For the experiments described in this paper, we chose the widely used multi-objective evolutionary algorithm called NSGA-II introduced by K. Deb. We will not describe this algorithm here, as detailed and thorough explanations can be found in [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF].

For the parameters of the evolution, we use a crossover rate of 0.8 and a probability of mutation of 0.01 for each non-terminal node. The population size is 100 individuals and the experiments last for 100 generations. We use a classical binary tournament selection in all our experiments. Those parameters were determined empirically with a few tests using different values. Due to the length of the experiments, we didn't proceed to a thorough statistical analysis of the influence of those parameters.

Experiments and Results

Experiment in a Simple Environment with Block Obstacles

The experiment described in this subsection uses only simple block obstacles. The goal is to cross the environment diagonally without hitting those block obstacles. We use a single brick texture for all the walls, floor, ceiling and blocks. We also manually created a simple obstacle avoidance controller for this environment based on optical flow. It manages to avoid some obstacles but it is quite slow and gets stuck in some situations. For this problem, the evolution created more efficient solutions, as shown on Figure 2. Different kinds of controllers emerged, from slow ones only covering a few meters to fast ones quickly reaching the goal but bouncing on obstacles rather than avoiding them. The interesting point is that all those controllers use either an optical flow based technique, which is the most straightforward, or a Gabor filter detecting near obstacles. The evolution didn't find the ideal compromise between obstacle avoidance and speed but it selected reasonable and usable visual primitives for the environment efficiently. The resulting trajectories for the reference controller and two evolved ones are shown on Fig. 3. The two corresponding evolved controllers are shown on Fig. 4. It is interesting to note that these controllers use only a few primitives. In this kind of experiment, several primitives are seldom selected: edge detectors for example (Laplacian or Sobel) are almost never used, probably because the integral com-putation step is not adapted for the extraction of this kind of feature. On the contrary, optical flow is very often used but mainly to detect near obstacles because the flow computation is very imprecise at high speed or with a rotary movement. Gabor filter is also often selected as it can detect textured obstacles at a given distance.

Experiment in a more Realistic Environment

In this experiment, the block obstacles have been replaced by bookshelves. The floor and the walls have different textures. The environment is less cluttered but the obstacles are larger than in the previous experiment. As there is more free space and the target location is from point, the experiment time is 30 seconds. We manually designed another reference controller to compare with evolution results. It is also based on optical flow but it has slightly to perform better in this environment. Figure 5 shows the environment and of these controllers.

Once again, one of the evolved avoids obstacles correctly but it far from perfect doesn't reach goal from the first point. Other evolved controllers the goal quickly but hit obstacles and several times on their way. This time, almost all the controllers tegral computations the image detect obstacles. When approaching the bookshelves, the bottom of the shelves becomes more visible. Those areas are darker because the light from the ceiling in these experiments, thus with a simple integral computation in the upper part of the image, the robot brakes when approaching an obstacle. obstacle detection technique is coupled a heading behavior and a seemingly back and forth that

Discussion

The results of these two experiments show that the evolution process introduced in this paper is able to produce interesting solutions, generally outperforming hand-designed controllers. The evolution caused the emergence of original solutions to the obstacle avoidance problem depending on the context. The visual primitives selected in each case are coherent and can be used to avoid obstacles. This is promising for the next necessary step which will be the validation of the evolved algorithms on a real robot.

Nevertheless it should be noted that these performances are far from perfect. More, in other experiments with an even simpler environment where handdesigned controllers are really efficient, evolution gets stuck in local minima and achieves far worse performance. This underlines the major drawback of our approach at the moment: the population is much too small compared to the size of the search space, so evolution only explores a small part of it and hence misses many interesting solutions. We currently investigate solutions to overcome this problem without increasing the evolution time too much. The first possible solution would be to introduce a diversity metric to prevent premature convergence. This solution has been proved efficient on several problems but it is not straightforward to define a good diversity metric for tree based algorithms. An easier and probably more efficient solution would be to change population parameters. We could either split the population in several independent subpopulations or change the population size during the evolution to explore more solutions in the beginning. A combination of these two solutions is also possible and is likely to improve the results greatly. Another drawback is that our feature extraction operator is not adapted for linear or punctual features (edges or corners for instance). The addition of others feature extraction operators should increase the diversity of usable features.

Conclusion

In this paper, we used multi-objective genetic programming to create obstacle avoidance controllers making use of visual information. We use a simulation environment with computer rendered images to evaluate the candidate controllers. The evolution allowed the emergence of original strategies using relevant visual primitives in the environment. For future research, we intend to improve the results by controlling more precisely the population parameters of the evolution process. We also plan to design a more realistic simulation environment and robot model to evolve more robust controllers and to test them on a real robot. We will then adapt our system for the online selection of relevant controllers in order to develop strategies adapted to the visual context in real time. This will bring us closer to our goal of an adaptive and reactive robot able to face the complex and ever-changing environments of the real world.

Fig. 1 .

 1 Fig. 1. Algorithmic tree of a program example for obstacle avoidance. Rectangles represent primitives and ellipses represent data.

Fig. 2 .

 2 Fig. 2. Left: Snapshot of the simple environment with textured block obstacles. Right: Evolution of the best algorithms along the generations. Only the Pareto front for each generation is shown here.

Fig. 3 .

 3 Fig. 3. Left: Trajectory of the reference controller. Middle: Trajectory of an evolved controller with a careful behavior. Right: Trajectory of a faster evolved controller bouncing on obstacles.

Fig. 4 .

 4 Fig. 4. Left: Algorithm of an evolved controller with a careful behavior. Right: Algorithm of a faster evolved controller.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Left: Snapshot of the environment with several furniture items. Right: Evolution of the best algorithms along the generations.


Christine Dubreu

Antoine Manzanera

Eric Bohain

Comprehensive evaluation of tracking systems by non-photorealistic simulation

Keywords: Image processing, tracking, evaluation, simulation

As more and more research effort is drawn into object tracking algorithms, the ability to assess the performance of these algorithms quantitatively has become a fundamental issue in computer vision. Because tracking systems have to operate in widely varying conditions (different weather conditions, background and target characteristics, etc), a large test bed of video sequences is needed in order to obtain a comprehensive evaluation of a tracker across the whole range of its operating conditions. However, it is very unlikely that a dataset of real video sequences representative of the whole range of operating conditions of a tracker together with its ground truth could be obtained, and building a realistic synthetic dataset of such sequences would require costly advanced simulation platforms.

In the new evaluation method proposed in this paper, the operational criteria of the tracking system are turned into objective measures and used to generate a synthetic dataset, non-photorealistic, but statistically representative of the whole range of operating conditions. The assessment of an algorithm using our method provides both a quantitative evaluation of the algorithm and the borders of its validity domain. The performance measurement of an algorithm on a synthetic sequence is shown to be consistent with the measurement on a real sequence with the same criteria. The benefit of this approach is twofold: it provides the developer with a way to concentrate on the weaknesses of his algorithm, and helps the system designer to choose the algorithm that best fits the operating constraints.

INTRODUCTION

In recent years, there has been a considerable interest in automatic visual surveillance of wide area scenes. One of the major challenges of visual surveillance is the development of reliable tracking systems, and a variety of algorithms has been developed for the tracking of objects in environments of different complexities. Thus, performance evaluation has become an increasingly important issue, since it enables researchers to assess the reliability and robustness of their algorithms under widely varying conditions, and users to compare different algorithms and to choose the one that best fits their operating constraints.

The conventional assessment process consists in running algorithms on a dataset of sequences and comparing the results with a ground truth, typically generated by manual or semi-automatic examination of the video sequences. However, this method has two disadvantages : (i) the generation of ground truth data is highly time-consuming and subject to error and uncertainty, and (ii) it is very difficult to produce a dataset of sequences which covers the whole range of operating conditions of a system, and then very difficult for the user to circumscribe the validity domain of the system, with respect to the operating criteria (Figure 1(1)).

To handle this problem, some users employ physical simulation to produce a dataset of photo-realistic sequences. This allows them to evaluate the system on any configuration of the operating criteria, by translating these criteria within physical parameters, including 3D geometric, mechanical, and photometric modeling (Figure 1(2)). But not many users and researchers have access to such simulation platforms.

The purpose of our research is to propose a much simpler way to produce a dataset able to represent any operating condition, and for which a ground truth is automatically generated. The assumption which is made here (and that will be verified by experiments) is that the operating criteria can be turned into a set of formal parameters operating directly in the image domain to produce sequences that are not photo-realistic, but statistically representative of the operating conditions (Figure 1(3)). The problem addressed in this paper is: given the operating criteria, what is the good (i.e. minimal, or easiest to obtain) set of formal parameters we should consider? This set should be constituted of: (1) parameters defining the inherent statistical properties of the objects involved, i.e. the target(s) and background. These will be referred to as static parameters, and (2) parameters defining the relative interaction between these objects, and their temporal behavior, i.e. their deformation, illumination, and relative motion, the dynamic parameters. Derivation of these parameters from the operating criteria and the way they are used to produce a synthetic sequence is presented in Section 2.

In Section 3, we validate the approach by evaluating two tracking algorithms on both real sequences and synthetic sequences with the same set of parameters generated with our method, and compare the results. Then, we illustrate the interest of our synthesis method, by showing that we are able to change any parameter value of a given scene at our convenience in order to generate a scene representative of any desired operating condition of a tracking system.

In Section 4, we discuss the further potentialities of the method, and also the way it can be extended and improved.

SYNTHESIS OF A SCENE

Set of discriminating perceptual parameters

We assume (and verify a posteriori that this is a correct assumption) that a set of discriminating parameters representative of a scene can be defined, from which a scene representative of any operating conditions of a tracking system can be generated and used for the assessment of this system. The aim of this paragraph is to find the static discriminating parameters of this set, i.e. the parameters inherent to the objects present in the scene independently of their orientation, motion or illumination, that fully characterize these objects. Some of the parameters that will be determining in the behavior of a tracking system are obvious. These are the size and shape of the target, and the brightness and relative contrast of the target and background. In our application, a tracking algorithm has to perform the same way on two scenes generated with the same set of static and dynamic parameters. As the dynamic parameters may obviously contain parameters defining the objects motion, including rotation and scale, the static parameters must take into account the way the appearance of an object will be affected by those transformations, which rely on texture features, in particular coarseness, directionality and regularity. These features are related to the size, shape and organization of homogeneous regions within the texture of an object.

Therefore, the parameters used in our static model of a scene will be the size, shape, color, contrast, coarseness, directionality and regularity of the objects present in it. These are perceptual textural features which have to be estimated using computational measures, in order to get a statistical model of the objects.

Static synthesis of a scene

Texture modeling has been extensively studied in Computer Vision, and a bibliography of the literature concerning this topic was written by Tuceryan & Jain. [START_REF] Tuceryan | Texture Analysis[END_REF] Many approaches concern models aimed at faithfully reproducing a given texture so that the synthetic texture and the sample one from which it was generated are not visually discriminable. But this is beyond the scope of this paper, and the reader can refer to the work of Haralick 2 , Derin 3 , Julesz [START_REF] Julesz | On Perceptual Analysis Underlying Visual Texture Discrimination[END_REF] and Gagalowicz 5 for more information.

The problem we aim to solve is : given the set of parameters described in 2.1, synthesize a texture field which parameters are equal or almost equal to this set of parameters. We describe a sequential procedure to synthesize such a texture. Although the generated texture is not visually representative of an object, we will show that it is statistically representative of it, and that it can be reliably used for an accurate assessment of tracking algorithms.

The first step of this sequential procedure is to generate a synthetic texture with values on the whole histogram. In this paper, a basic texture is taken as a gaussian function, as shown in figure 2.a.

Then, the second-order features (coarseness and directionality) of the desired texture are considered. By stretching the basic texture along the two axes, a texture as directional and as coarse as desired can be obtained. This pattern is then replicated in order to get an image of fixed size, whatever the desired coarseness and directionality, as shown in figure 2.b.

Then the first-order features (grey levels distribution) are considered, a white noise is added to the obtained pattern, and its histogram is mapped to the desired histogram, as shown in figure 2.c. After these steps, the pattern still looks very regular and artificial. In order to get a texture which is less regular, this pattern is used as a sample to synthesize an image using the algorithm described by Li-Yi Wei. [START_REF] Wei | Texture Synthesis by Fixed Neighbourhood Searching[END_REF] This algorithm, derived from Markov Random Fields texture models, generates texture through a sequential deterministic neighborhood searching process.

The algorithm starts with an input texture sample S and a white random noise I. We force the random image I to look like the sample by transforming it pixel by pixel in a raster scan ordering, i.e. from top to bottom and left to right. To determine value of each pixel p of I, its spatial causal neighborhood N (p) is compared against all possible neighborhoods N (p i ) from S. The value of the input pixel p i with the most similar N (p i ) is assigned to p. We use a simple L 2 norm to measure the similarity between the neighborhoods. The goal of this synthesis process is to ensure that the newly assigned pixel p will maintain as much local similarity between I and S as possible. The size of the neighborhood is a tuneable parameter corresponding to the regularity of the texture: in order to obtain a texture which is not too regular, the size of the causal neighborhood has to be small relatively to the coarseness of the texture (so that only local similarity is ensured), but if the texture is wanted to be very ordered, a larger neighborhood has to be used.

Figure 2 shows some synthetic textures generated with this method. It should be noted that some very different types of textures can be generated from the same initial pattern and different sets of parameters, and that although the generated texture still looks artificial, it is statistically representative of this set of parameters. The textures generated with this method are simple and homogeneous textures, but more complex textures, i.e. textures made of several primitives, e.g. trees and roads, can be generated using the method of texture synthesis from multiple sources described by Wei. [START_REF] Wei | Texture Synthesis from Multiple Sources[END_REF] Once the target(s) and background texture fields are created using this method, the target(s) field(s) are mapped on an ellipse with eccentricity and size corresponding to the input shape parameters, and the back-ground field is mapped to a rectangle which size is the desired size of the video sequence. Thus, from the set of static parameters defined in 2.1, a scene with the same parameters was generated.

Set of discriminating dynamic parameters

After the static target(s) and background textures are generated, their deformation and relative displacement have to be modeled in order to get a dynamic synthetic scene statistically representative of a real scene. The background motion is modeled by a composition of a rotation, a translation, and a scale :

x y = ρ cos θ sin θ -sin θ cos θ x y + T X T Y (1)
Therefore, the parameters θ B max , ρ B max , and T B Xmax and T B Ymax , defining respectively the maximum rotational angle, scale, and displacement of the background between two consecutive frames have to be defined. Similarly, the target(s) motion is defined by the parameters T T Xmax and T T Ymax , and its deformation by θ T max , ρ T Xmax and ρ T Ymax .

The displacement and deformation of the objects present in the scene are chosen to be modeled in 2 dimensions. This is consistent with the target(s) and background dynamics between two frames. This model would also enable us to model static occlusions, i.e. occlusions of the target(s) by a part of the background, by adding a 'transparency' parameter to the model of target.

Dynamic synthesis of a scene

From the models of objects obtained in 2.2, and the displacement parameters defined in 2.3, a synthetic dynamic scene is computed in which the model of dynamic target, i.e, the static model of target to which a dynamic motion and deformation is applied, is superimposed to the dynamic model of background texture.

A 2D deformation is applied to the target(s) at each frame. The values of the rotation angle, translation, and scale along x and y are chosen at random in the range defined in 2.3.

Similarly, a displacement and a deformation are applied to the background. To avoid discontinuities and re-synthesis of new pixels of the background at each frame generation, the background texture is symmetrized and infinitely replicated in the two directions x and y. Then the deformation and displacement can be applied to it, and no pixel has to be re-synthesized. The deformation and displacement of the background are generated in such a way that it is continuous; there is no sudden change in the angle of rotation, scale, or displacement vector, which is consistent with what is commonly found in real sequences.

Synthesis of the database

To get a dataset representative of the wide range of operating conditions of a tracking system, a large number of scenes will be synthesized with different input values. Any parameter value of a given scene can be modified; thus, a scene with any input parameters can be generated, and the contrast, motion, and deformation of the target(s) or background can be controlled.

In this paper, different of choices have been made for the simulation : only simple-textured objects are generated, their motion is simulated as described previously, and only one target is synthesized. This is because the aim of our method is to validate the assumption that only a few parameters are necessary to synthesize scenes which can be used to evaluate low-level object tracking algorithms, but some more elaborate sequences could be generated thanks to synthesis of complex textures from several samples, and control of static and dynamic occlusions by generation of multiple targets. Indeed, our method can be combined with the one of Black, 8 also based on a synthetic dataset generation, and where dynamic occlusions can be modeled. This method constructs sequences containing complex motion scenes, by superimposing motion from isolated targets, and allows the generation of a large variety of datasets representing different tracking scenarii by controlling the occurrence and duration of dynamic occlusions.

VALIDATION OF THE METHOD

Validation protocol

To validate the assumption that the input parameters defined in 2.1 and 2.3 are sufficient to characterize a scene and to complete our purpose, we extract these parameters from a wide set of real sequences, and use them to generate synthetic sequences. The motion of the target(s) and background are extracted from the ground truths provided with the real scenes, the mean and contrast of the objects present in the scene are given by their histogram. Their coarseness, directionality and regularity are obtained by averaging the size and shape (ratio width/height) of regions obtained by manual segmentation of these objects.

Thus, we dispose of a wide set of pairs composed of a real and a synthetic scene with the same parameters. Figure 3.1 shows such pairs of scenes. The real scenes we used are some infrared and visible real sequences, taken from naval, airborne, and ground cameras, for which a ground truth has been manually generated, as well as the scenes of the VIVID database, [START_REF] Collins | An Open Source Tracking Testbed and Evaluation Web Site[END_REF] which is a database of infrared and visible video sequences together with their ground truth aimed at evaluation of tracking systems.

Tracking algorithms are then applied to the real and the corresponding synthetic datasets, and the performance of the different algorithms on the different scenes are compared.

Algorithms and metric

Two algorithms are evaluated on the scenes. The first one is a correlation algorithm, and the second one is a centroid algorithm. The correlation algorithm relies on a search of the position for which the correlation value between the reference image A and a rectangular patch B in the current frame, given by ( 2), is maximal. The search strategy is based on a gradient descent with a diamond pattern. 10

r = i j (A ij -Ā)(B ij -B) i j (A ij -Ā) 2 i j (B ij -B) 2 (2)
The second algorithm is the centroid algorithm described by Albus & al,[START_REF] Albus | Centroid Tracking using a probability map for target segmentation[END_REF] in which a probability map is used to determine whether pixels belong to the target or not, and to determine the target's centroid. This algorithm uses concentric gates to determine relevant regions: the outer region, which contains mostly background pixels, and the inner region mostly target pixels. Therefore, a probability map can be computed from the smoothed histograms of these regions to segment the target :

P (k) = H I S (k) H I S (k) + H O S (k) , ∀f ∈ 0...∆ -1, (3)
where H I S and H O S are respectively the smoothed histogram of the inner and outer region, and ∆ is the number of grey levels in the image. P (k) is the probability for a pixel of intensity k to belong to the target.

A metric has to be defined for the evaluation of tracking algorithms. A diverse range of measures and procedures to establish a performance metric has been used in tracking evaluation. [START_REF] Ellis | Performance Metrics and Methods for Tracking in Surveillance[END_REF] The choice will inevitably depend on the target application, as the priorities will vary for different applications. The metric used in this paper is the standard deviation of the distance to the ground truth.

Results and validation of the model

The performance of the algorithms for a few of the real and corresponding synthetic scenes are shown in the following table: We can see that globally, the results of the algorithms on the synthetic scenes are consistent with the results of the algorithms on the corresponding real scenes for each of the two algorithms. This comforts all the assumptions made so far, and in particularly the discriminability of the set of parameters chosen, and the consistency of the database generation method. Therefore, the low-level performance of a tracking system can be evaluated in any conditions covered by the operating criteria described in this paper, without having to find a real video sequence representative of this conditions, and without having to use costly and heavy photorealistic simulation methods.

Applications

Now that evaluating an algorithm on a synthetic scene generated with this method is known to be equivalent to evaluating this algorithm on a real scene with the same characteristics, we can assess the performance of an algorithm in any situation by running it on synthetic sequences. This is very useful for the determination of the validity domain of an algorithm, i.e. the domain on which the algorithm will perform in a satisfactory way. Figures 4, 5 and6 show the measure of the standard deviation of the distance to the ground truth for several sets of synthetic scenes of 500 frames in which a parameter is varied, the other ones remaining constant.

In Figure 4, the contrast between the target and the background is varied, all the other parameters remaining constant. This means that for all the sequences, the displacement of the background, target, and their texture and deformation are exactly the same. Only their relative contrast is modified. For this particular case, the deformation of the target was chosen to be very low, and the background motion to be close to 15 pixels between two consecutive frames. The correlation algorithm performs well (the standard deviation of the error is low) since a very low deformation is allowed, and since deformation is the main thing, with occlusions, that would cause a correlation algorithm to fail. The centroid algorithm is highly dependent on the contrast between the target and the background, since the probability of a pixel to belong to the target depends on the inner and outer histograms. As expected, the figure shows that the centroid algorithm is worse than the correlation one for low contrasts, but it gives a quantitative information about the performance of these algorithms. If one knows the maximal standard deviation of the error accepted for an algorithm, then one can deduce the minimum contrast that would ensure the standard deviation to be acceptable, and therefore get the validity domain of this algorithm. Similarly, figure 5 gives the maximal target displacement allowed between two frames, and figure 6 its maximal rotation, the other parameters being fixed. These figures are consistent with the fact that generally, the centroid algorithm is more robust to rotation and large displacements of the target than correlation. It is the case for the specific set of fixed parameters chosen to construct these figures. Thus, a multi-dimensional (more than 2 dimensions) circumscription of the validity domain of an algorithm can be found, and we are able to tell whether an algorithm is likely to work or not in some given conditions. This is particularly useful for specifying the range of operation of a system .

CONCLUSION AND FURTHER WORK

Our method provides an efficient way to quantitatively evaluate low-level object tracking methods without having to use costly and heavy simulation platforms. It relies on the characterization of the parameters of a scene that will be discriminating for this task, and on the synthesis of a scene, which, although non photo-realistic, is statistically representative of the real scene. This enables us to get the validity domain of algorithms and to quantitatively compare the performance of different algorithms.

The evaluation method presented in this paper is not suitable for high level algorithms evaluation, since it does not deal with static or dynamic occlusions, or complex target(s) and background textures. Nevertheless, it is possible to simulate more elaborate scenes, by increasing the number of discriminating parameters. This will enable us to get a more accurate evaluation and circumscription of the validity domain of algorithms, at the cost of more input parameters.

Figure 1 .

 1 Figure 1. Evaluation data set production paradigm. (1) Real data set, (2) Photo-realistic, physical-based, synthetic data set, (3) Non photo-realistic, formal-based, synthetic data set.

Figure 2 .

 2 Figure 2. Texture Synthesis with different sets of static parameters using the same initial pattern. (a) Initial pattern for the synthesis of four textures. (b) Fixed-size pattern obtained by stretching of the initial pattern to get the desired coarseness and directionality. (c) Fixed-size pattern after white noise addition and histogram matching. (d) Result of texture synthesis with fixed-size neighborhood using (c) as sample.

Figure 3 .

 3 Figure 3. Pairs of images composed of a real one, and a synthetic one generated from the estimated set of parameters of the real one. The synthetic image, although non photorealistic, is statistically representative of the real one.

  visible cars) 0.5572 0.5401 1.034 0.9903 2. (infrared boat) 0.1473 0.1397 0.3577 0.3342 3. (visible plane) 1.0176 0.9775 0.945 1.032σ corr Ris the standard deviation of the distance to the ground truth for the correlation algorithm applied to the real sequence of the pair, σ corr S is this measure for the correlation algorithm applied to the corresponding synthetic scene. σ centr R and σ centr S are the values of this standard deviation for the centroid algorithm.

Figure 4 .

 4 Figure 4. Robustness of the correlation and centroid algorithms to the change of contrast between the target and the background

Figure 5 .

 5 Figure 5. Robustness of the correlation and centroid algorithms to the maximum displacement of the target between two frames

Figure 6 .

 6 Figure 6. Robustness of the correlation and centroid algorithms to the maximum value allowed for the target rotation (in degree)


Taha Ridene
email: taha.ridene@ensmp.fr

Antoine Manzanera
email: antoine.manzanera@ensta.fr

Mécanismes d'Attention Visuelle sur Rétine Programmable

Keywords: Attention Visuelle, rétine programmable, cartes de saillance, traitement multiéchelle

L'Attention Visuelle est la capacité d'un système de vision, qu'il soit humain ou artificiel, à sélectionner rapidement les informations les plus pertinentes de l'environnement dans lequel il opère. Le rôle principal de ce mécanisme est d'accélérer le processus de vision, en réduisant sensiblement la quantité d'informations visuelles qui sera traitée par les tâches de plus haut niveau. Cependant, les méthodes mises en oeuvre dans la littérature sont généralement très coûteuses en opérations de bas/moyen niveau. Les rétines numériques programmables, grâce à leur parallélisme massif, sont très bien adaptées pour de telles tâches. L'implantation d'une approche attentionnelle bio inspirée sur une rétine programmable, implique néanmoins la prise en compte de contextes architectural et algorithmique radicalement différents. Dans cet article, nous présentons les étapes d'implantation d'un modèle informatique d'Attention Visuelle basé sur les cartes de saillance, sur la rétine programmable PVLSAR34. La démarche algorithmique est donc massivement parallèle, et les traitements sont fortement fondés sur des notions de multi-échelle.

Introduction

Bien que la quantité d'information présente dans notre environnement soit énorme, le système visuel humain a la capacité de gérer et d'interpréter très efficacement les images perçues, grâce à des mécanismes permettant de représenter l'environnement sous une forme compacte, en supprimant tout information redondante et en se focalisant sur les éléments les plus saillants 1 . Ces Mécanismes d'Attention Visuelle guident les mouvements d'oeil pour placer la fovéa sur les parties les plus saillantes de la scène explorée. Deux stratégies d'exploration ont été révélées : Une stratégie descendante (topdown) qui repose sur une connaissance a priori, et une stratégie ascendante (bottom-up) faisant référence à l'Attention Visuelle involontaire.

Les différentes études réalisées sur l'Attention Visuelle dans des domaines divers comme la psychologie, la psychophysique ou la neurophysiologie, ont été les principales source d'inspiration des chercheurs en vision artificielle. Pour la modélisation informatique d'Attention Visuelle, divers modèles se sont succédés [START_REF] Koch | Shifts in selective visual attention : towards the underlying neural circuitry[END_REF] [8] [START_REF] Ouerhani | Visual Attention : From Bio-Inspired Modeling to Real-Time Implementation[END_REF], se basant essentiellement sur la théorie d'intégration des primitives [START_REF] Treisman | A feature-integration theory of attention[END_REF]. La vocation de ces modèles informatiques est, en réduisant l'information visuelle à son "essence", de réduire le coût computationnel de la tâche de vision. Néanmoins, la multiplicité des primitives, et le caractère multi-échelle des traitements implique une charge de calcul sur le bas-niveau qui peut être considérable, en particulier dans la stratégie bottom-up.

Récemment, des travaux ont amené à la maturité des rétines artificielles, rapprochant les imageurs des rétines biologiques, en intégrant une puissance de calcul directement au niveau des capteurs. De nombreux modèles analogiques ou numériques ont été développés selon ce principe, on se référera à [START_REF] Bernard | Output methods for an associative operation of programmable artificial retinas[END_REF] pour une étude comparative détaillée. La rétine programmable PVLSAR34 développée à l'ENSTA en 2004 (voir FIG. 1 (a)), est une machine massivement parallèle de 40 000 cellules interconnectées selon une grille 2d 200x200 en topologie 4-connexe, chacune d'elle étant constituée d'un capteur photosensible et d'un processeur, doté d'une mémoire d'environ 50 bits. Chaque couple de processeurs adjacents partage une partie de leur mémoire, ce qui permet de communiquer des données entre pixels voisins. Au niveau du jeu d'instruction, chaque processeur peut effectuer les opérations booléennes élémentaires ("ET", "NON", "OU", etc.). Le mode de parallélisme est purement SIMD2 .

En intégrant le calcul de manière massivement parallèle directement au niveau du capteur, la rétine artificielle réduit très fortement le flux de données dans le système de vision, et donc le coût computationnnel associé aux tâches de bas-niveau. Il est donc très tentant d'associer le concept de rétine programmable et les Mécanismes d'Attention Visuelle. C'est ce que nous faisons dans cet article, en développant un modèle informatique cellulaire bottom-up d'Attention Visuelle, basé sur les cartes de saillance [START_REF] Itti | A model of saliency-based visual attention for rapid scene analysis[END_REF]. Nous présentons le modèle dans le section 2, puis nous discuterons les résultats dans la section 3.

Modèle cellulaire d'Attention Visuelle

Description du modèle global

Le modèle suit celui de l'attention bottom-up présentée dans [START_REF] Koch | Shifts in selective visual attention : towards the underlying neural circuitry[END_REF], et comporte trois étapes principales. Tout d'abord l'extraction des cartes de caractéristiques, ensuite la génération des cartes d'évidence, et enfin l'intégration des cartes d'évidence dans une carte de saillance. Les primitives que nous avons choisi d'extraire sont l'intensité et l'orientation pour une intégration d'une carte de saillance statique, et pour intégrer une carte de saillance dynamique, un module d'estimation de mouvement a été développé. L'absence de la couleur est justifiée par le fait que PVLSAR34 est une rétine à niveaux de gris. La figure 1 (b) illustre le modèle global de saillance considéré. Nous détaillerons dans ce qui suit chaque composante de ce modèle.

La représentation multi-échelle

L'extraction de certaines caractéristiques d'une image se fait en calculant des cartes, dites de caractéristiques, qui représentent l'image de départ suivant une ou plusieurs primitives pré attentives. Ainsi, on obtient une représentation multi-caractéristiques de la scène. Chacune de ces cartes est calculée par un ensemble d'opérations, définies sous le terme Center Surround3 comportant deux étapes :

1. Construction d'une représentation multi-échelle de la primitive ;

2. Calcul de la différence entre les niveaux fins et les niveaux grossiers de cette représentation.

L'étape 1 a comme résultat la forme sur laquelle se base tout les traitements du modèle cellulaire d'Attention Visuelle, les études déjà menées en analyse multi-échelle reposent sur deux étapes (Filtrage gaussien ; Sous-échantillonnage) donnant naissance à des formes pyramidales [START_REF] Burt | The laplacian pyramid as a compact image code[END_REF] [3] [START_REF] Hummel | The scale-space formulation of pyramid data structures[END_REF], les modèles attentionnels [START_REF] Itti | A model of saliency-based visual attention for rapid scene analysis[END_REF] [13] utilisent des pyramides dyadiques 4 .

Dans notre cas la sous résolution n'a pas lieu d'être puisqu'on opère en mode SIMD. La structure multi-échelle que nous utilisons est celle du cube gaussien [START_REF] Meer | Simulation of constant size multiresolution representations on image pyramids[END_REF] [START_REF] Meer | Stochastic image pyramids[END_REF]. L'implantation cellulaire du filtre gaussien a été réalisée sous la forme de moyennes locales itérées sur des voisinages de taille croissante. L'optimisation SIMD consiste à regrouper les sommes de manière dyadique et à utiliser des facteurs de normalisation égales à des puissances de 2 (voir FIG. 2(a)).

Le nombre de niveaux de notre représentation multi résolution est fixé à 6, en prenant en compte l'image originale de niveau 0. Dans notre modèle, le centre est un pixel appartenant au niveau c ∈ {0, 1, 2} du cube gaussien, et la région contournante le pixel correspondant au niveau s = c + δ avec δ ∈ {2, 3}.

Les primitives visuelles

L'opérateur « Center Surround » est appliqué aux trois primitives pré-attentives développées.

-L'intensité : Nous appliquons l'opérateur « Center Surround » en prenant comme entrée en première étape le cube gaussien. -L'orientation : Les travaux précédents utilisent en général les filtres de Gabor5 pour calculer cette primitive [START_REF] Itti | A model of saliency-based visual attention for rapid scene analysis[END_REF] [7] [START_REF] Ouerhani | Visual Attention : From Bio-Inspired Modeling to Real-Time Implementation[END_REF], nous avons choisi une approche basée sur des mesures de l'argument du gradient [START_REF] Burrus | Adaptive vision leveraging digital retinas : Extracting meaningful segments[END_REF], qui est plus adaptée en calcul cellulaire. -Le mouvement : Une mesure de flot optique est réalisée sur le cube gaussien d'entrée, et puis l'étape de différenciation est appliquée sur cette mesure.

Génération et combinaison des cartes d'évidence

La carte de saillance est calculée en combinant les différentes cartes caractéristiques. Une des difficultés pour cette combinaison est que ces cartes représentent des données a priori non comparables à des échelles différentes. Pour pallier à cette difficulté une étape de normalisation est appliquée (voir FIG. 2 (b)). Deux stratégies principales ont été utilisées dans l'état de l'art [START_REF] Itti | A model of saliency-based visual attention for rapid scene analysis[END_REF] [9], l'application directe de ces deux stratégies pose des problèmes liés à la nécessité d'une grande dynamique de représentation (nombre flottant), notre méthode a suivi la même logique mais avec une implantation différente au niveau de l'extraction de M et m, l'algorithme est exposé dans la figure 2 (b).

Nous intégrons ensuite pour chaque primitive les différentes cartes normalisées en une carte unique dite d'évidence, donnant la réponse, en terme de degrés de saillance des éléments de la scène observée, par rapport à la primitive considérée.

La carte de saillance finale est obtenue en combinant la carte de saillance dynamique résultat du traitement de la primitive mouvement et de la carte de saillance statique résultat de la combinaison linéaire des deux cartes d'évidence d'intensité et d'orientation.

Résultats et Discussion

La modélisation cellulaire de notre modèle attentionnel a donné naissance à des structures multiéchelles optimisées en calcul des cubes gaussien et de DoG bien adaptés à PVLSAR34 (voir FIG. 3), cet implantation pourrait être importée sur des architectures parallèles équivalentes. L'evaluation du travail s'est faite pour l'instant en terme de complexité, les tests sur les primitives intensité et orientation de la carte de saillance statique sont exposés dans les tableaux 1 et 2. L'évaluation de la primitive mouvement est encore en cours.

Nous remarquons que nous approchons le temps-réel à un facteur de 3/4 pour la carte de saillance à base d'intensité. En fait l'implantation actuelle nous permet de traiter l'équivalent de 17 images/s, et en analysant le tableau 1 nous remarquons que la tâche la plus complexe est celle de la normalisation (78% du temps CPU). En augmentant le nombre de primitives cette complexité devient encore plus grande et la contrainte temps-réel n'est plus respectée (voir Tab. 2). Cela est dû au fait qu'à cette étape nous étions amenés à réaliser des opérations analogiques (ex : somme globale) en dehors de la rétine à travers le cortex, et avec l'implantation actuelle nous multiplions à chaque normalisation le nombre de ces opérations, ce qui pénalise l'ensemble du processus par un transfert coûteux réalisé entre rétine et cortex.

Les résultats que nous avons eus bien que partiellement satisfaisants, pourront être améliorés pour atteindre le temps-réel. Nous imaginons une amélioration par l'implantation d'une autre méthode de normalisation moins coûteuse en temps CPU.

Conclusion

Les performances des applications, temps-réel en traitement d'images sont susceptibles d'être améliorées via des mécanismes d'accélération du processus de vision appelés Mécanismes d'Attention Visuelles. Dans ce cadre, et se basant sur une architecture parallèle, la rétine PVLSAR34, nous avons implanté un modèle cellulaire bottom-up d'Attention Visuelle basé sur les primitives : intensité, orientation et mouvement. L'implantation nous a permis de développer une approche basée sur les calculs cellulaires et les traitements multi-échelles et l'évaluation du modèle s'est faite par rapport au critère de la complexité en temps CPU et en cycles Rétines. L'approche attentionnelle étudiée pourrait être eprouvèe par des évaluations dans un cadre applicatif. Nous imaginons l'intégration de ce modèle attentionnel pour un algorithme de tracking déja réalisé sur PVLSAR34.

Des améliorations peuvent être appliquées sur deux niveaux. D'un côté nous pourrons imaginer, au niveau architectural l'intégration des calculs analogiques se faisant jusqu'à maintenant en dehors de PVLSAR34 : pour l'instant seules des opérations locales ont pu être implémentées, mais une nouvelle génération de rétines [START_REF] Gies | Increasing Interconnection Network Connectivity for Reducing Operator Complexity in Asynchronous Vision Systems[END_REF] apportera des primitives régionales, par l'utilisation du concept d'asynchronisme, ce qui facilitera la tâche pour des traitements plus poussés. D'un autre côté, en se comparant au système visuel humain, le bon fonctionnement d'un processus attentionnel a souvent besoin de la connaissance a priori, une perspective de notre travail pourrait être le développement d'une approche attentionnelle hybride par l'ajout d'un module top-down au modèle bottom-up présenté dans ce papier.

Fig. 1 .

 1 Fig. 1. (a) Un système à base de rétine programmable : la rétine peut-être vue comme une grille de couples microprocesseur et capteur photosensible. Les processeurs exécutant tous la même instruction, les opérations mémoires reviennent à manipuler des plans de bits (50 dans la dernière génération). Les opérations disponibles se réduisent à des décalages de plans de bits et à des opérations booléennes entre plans. Le cortex peut décider des instructions à envoyer et traite les données transformées par la rétine. (b) Modélisation informatique bottom-up d'Attention Visuelle basée sur les cartes de saillance.

Fig. 2 .

 2 Fig. 2. (a) Simulation du filtre gaussien par itération de moyennes locales dans le sens horizontale (De même pour le sens verticale), opérant en mode SIMD, cette simulation est applicable pour les 40 000 éléments de la grille et dans les deux sens. Le gain en calcul dyadique peut être vu dans le cas ou nous élargissons le voisinage à additionner. Pour chaque niveau un nombre d'itérations est fixé. (b) Des objets saillants dans seulement quelques cartes peuvent être masqués par le bruit ou par d'autres objets moins saillants des autres cartes, le principe de normalisation est d'augmenter la réponse dans le cas (1) et de la diminuer dans le cas (2), l'implantation sur PVLSAR34 est faite selon l'algorithme de N(.).

Fig. 3 .

 3 Fig. 3. (a) : Image Originale. (b) : Différence entre le Niveau 1 du cube gaussien avec σ1 = 1.4017 et le niveau 3 avec σ2 = 4.9940 .

Un élément visuellement saillant, c'est un élément qui ressort prioritairement lors de la perception visuelle d'une scène, au point de prendre une importance cognitive particulière.

Single Instruction Multiple Data : Toute la grille est commandée par un séquenceur externe qui envoie une séquence d'instructions à la rétine selon une fréquence fixe, et à chaque pas de calcul, tous les 40 000 processeurs exécutent exactement la même instruction. Un programme rétinien est donc entièrement défini par la séquence d'instructions envoyée par le séquenceur.

Opérateur Center Surround « centre-région contournante » : Ce nom a été donné pour la raison suivante : les neurones visuels sont plus sensibles à une petite région de l'espace visuel (le centre), alors que le signal présent autour (région contournante) inhibe la réponse neuronale (par exemple cellule ON-OFF). Dans le cas d'une ligne horizontale entourée par des lignes verticales, la réponse en cet endroit sera plus grande que si elle était entourée par des lignes horizontales.

Une pyramide est dite dyadique si le passage d'un niveau (i) à un niveau (i + 1) se fait avec le rapport 1/4.

Un filtre de Gabor est une fonction sinus à laquelle on ajoute une enveloppe gaussienne.