Les travaux présentés ici sont effectués en collaboration avec Bruno Remillard (HEC Montreal) et  Pierre Del Moral  (LSP Toulouse). Nous présentons ici deux modèles de filtrage permettant de retrouver des cibles dans un ensemble fini. Dans cette page web, nous présentons les modèles étudiés et les simulations C++ et MATLAB.

1) Premier modèle, recherche de cibles dans une images bruitées.
 

  Problème : retrouver des cibles (par exemple des bateaux) dans des images bruitées.

  Des bateaux, c´est-à-dire une chaîne de markov, se promènent dans une fenêtre de taille T*T. Un radar tente de les retrouver. Ce dernier observe chaque pixel de la fenêtre mais malheureusement, il  fait des erreurs d'observations :

• avec une probabilité (1-p0)  il observe quelque chose alors qu´il n´y a pas de bateau sur le pixel.
• avec une probabilité (1-p1) il observe rien alors que le bateau est  sur ce pixel.

  Pour les simulations MATLAB et C++, nous avons considéré, une ou deux ou trois particules qui suivent une marche aléatoire au plus proche voisin avec des probabilités de monter, descendre, aller à gauche et aller a droite. Dans le cas de deux particules on se place dans le cas où elles ne rencontrent pas.

  Voici donc les résultats des simulations. Nous nous plaçons dans le cas d'une marche aléatoire presque symétrique. Avec p0=p1=0.9 ou p0=p1=0.95. Les résultats sont  présentés sous forme de petits films dont voici une image dans le cas d´une seule particule :
 
 

Les points bleus : là où le radar suppose la présence d´un bateau. En rouge :  l'emplacement exat du bateau. En vert : l'estimation, par l'algorithme, de l'emplacement du bateau. Le chiffre en noir représente  le temps écoulé.

• Dans une fenêtre 70*70,  sur 150 pas et avec p0=p1=0.9 :filmt70n150.mat.gz(728 KB)
• Dans une fenêtre 200*200, sur 500 pas et avec p0=p1=0.9 : filmt200n500.mat.gz(3.6 MB)
• Dans une fenêtre 200*200, sur 200 pas et avec p0=p1=0.9  :  filmt200n200.mat.gz
• Dans une fenêtre 200*200, sur 200 pas et avec  p0=p1=0.95 :  filmt200n200p95.mat.gz

•  Recherche dans une fenêtre 50*50, sur 100 pas et avec  p0=p1=0.9 : filmt50n100.mat.gz.
• Recherche dans une fenêtre 50*50, sur 100 pas et avec  p0=p1=0.95 : filmt50n100p95.mat.gz(131 KB).

>>figure
>>% il est préférable d´enlever le axes de la figure
>>load filmt70n150
>>movie(M)

>>movie(M,[1:5:150])

Table 1 : Erreur moyenne dans le cas d´une particule dans une fenêtre de taille 200*200.

t	[2,200]	[10,200]	[20,200]	[30,200]	[100,200]
p0=p1=0.9	8.7	4.1	1.2	1.2	1.1
p0=p1=0.95	4.3	0.3	0.3	0.3	0.3

Table 2 : Erreur moyenne dans le cas de deux particules dans une fenêtre de taille 50*50.

t	[2,100]	[10,100]	[20,100]	[30,100]
p0=p1=0.9	6.4	1.6	1.7	1.7
p0=p1=0.95	3.0	1.0	1.0	1.1

  Conclusion : Dans tous les cas on peut remarquer que l´algorithme converge très vite. Si on part, à la première itération de la loi uniforme sur toutes les configurations possibles, on remarque que l´on retrouve très vite les deux particules, dés la 20 ième itération, l´estimation est à un ou deux pixels de la marche aléatoire. Et à partir du moment où l´on a trouvé les particules on ne les quitte plus. Remarquons de plus que d´une part on retrouve plus facilement une particule que deux et d´autre part que le choix des paramètres p0 et p1 est important pour la rapidité de l´algorithme.
 

Programmes en C++ et article :

• "Filtering of images for detecting multiple targets trajectories" (.ps)(.pdf)
• Recherche d´une particule :  (.c)
• Recherche de deux particules :  (.c)
• Recherche de trois particules : (.c)
• Recherche d´une particules sans connaitre la chaine de Markov : (.c)

English version