Projet image 2016 : Distributions espace-temps pour modéliser les mouvements de petits groupes de personnages

De Ensiwiki
Aller à : navigation, rechercher
Project schedule.png
Titre du projet Projet image 2016 : Distributions espace-temps pour modéliser les mouvements de petits groupes de personnages
Cadre Projets de spécialité
Page principale Projets de spécialité image

Encadrants Marie-Paule Cani Ulysse Vimont

Étudiants

Introduction

La simulation de groupes de personnes est aujourd'hui très utilisée pour peupler un monde virtuel, notamment dans les films d'animation ou les jeux vidéos.

L'approche traditionnelle pour modéliser un groupe d'individus consiste à définir des règles physiques régissant le comportement de chaque agent par rapport à ses pairs : par exemple, des forces d'attraction longue distance et de répulsion courte distance. Cette méthode est cependant contraignante lorsque l'on veut reproduire de manière réaliste un comportement de groupe, puisqu'elle nécessite un ajustement manuel de ces règles.

Dans ce projet, nous explorons une approche différente fondée sur l'apprentissage et la simulation probabiliste. A partir d'un échantillon (l'évolution d'un groupe pendant quelques secondes), nous voulons apprendre des paramètres pertinents afin de restituer le comportement de l'échantillon au cours de la simulation.

Notre travail est l'extension de l'application WorldBrush qui reproduit une distribution spatiale d'arbre et de rochers dépendante du terrain apprise à partir d'un échantillon spatial.

Modèle

Données apprises

Modele1.png

Dans l'idéal, nous voulions apprendre les données depuis des vidéos de foules réelles. Cependant, cela aurait nécessité un long travail préalable de repérage d'individus. Les données que nous avons apprises proviennent en fait d'un logiciel de modélisation de mouvements de groupes d'individus par systèmes multi-agents (boids) que nous avons développé dans le cadre du cours de programmation orienté objets du premier semestre. Ce sont ainsi les comportements de ces boids que nous cherchons à reproduire par approche statistique.

Organisation d'un groupe

Modele2.png

Nous nous sommes restreints à la structure de groupe suivante : les individus du groupe suivent un leader, qui suit lui-même une trajectoire soit prédéfinie, soit donnée par l'utilisateur à la volée à l'aide des flèches directionnelles. Nous sommes conscients que d'autres modèles seraient pertinents : par exemple, un groupe d'amis qui marchent dans la rue n'a pas de guide à proprement parler. Cependant, la durée limitée du projet nous a poussés à nous focaliser sur cette configuration en particulier. De plus, rien n'oblige l'utilisateur à afficher le leader : il peut très bien le considérer comme une entité virtuelle possédant une direction et une vitesse auxquelles le groupe essaie de s'adapter.

Paramètres appris

Nous distinguons les paramètres de contraintes des paramètres de décision. Les premiers rendent compte des configurations probables à l'échelle du groupe (en clair, de la forme du groupe), tandis que les seconds permettent de choisir les déplacements élémentaires des individus à chaque itération. Chaque paramètre est systématiquement corrélé à une variable d'état de l'individu considéré : par exemple, on corrèle la vitesse de l'individu (paramètre de décision) en fonction de la distance de l'individu au leader (variable d'état). Les résultats sont ensuite consignés dans des histogrammes à deux dimensions. Un nombre supérieur de dimensions (et donc de variables corrélées) aurait produit des histogrammes moins aisément visualisables et bien plus difficiles à remplir.

Paramètres de contraintes

Nous apprenons trois paramètres traduisant des contraintes relatives à la forme du groupe.

- Distance de l'individu au leader (en fonction de la vitesse du leader) : Modele distleader.png

- Inter-distances entre les individus (en fonction de la vitesse du leader) : Modele interdist.png

- Position angulaire (en fonction de la distance au leader) : Modele posangle.png


En plus de ces paramètres, l'utilisateur peut spécifier une carte d'encombrement précisant les endroits par lesquels les individus sont plus ou moins susceptibles de passer.

Paramètres de décision

Nous apprenons trois paramètres servant à mettre à jour la position des individus à chaque itération.

- Variation d'orientation (en fonction de la vitesse de l'individu) : Modele dtheta.png

- Orientation par rapport au leader (en fonction de la distance de l'individu au leader) : Modele orientation.png

- Vitesse en norme (en fonction de la distance de l'individu a leader) : Modele vitessenorme.png

Fonctionnement

Lors d'une première phase d'apprentissage, on analyse un échantillon qui décrit les positions de plusieurs individus au cours du temps. On y lit les paramètres qui nous intéressent, et on s'en sert pour remplir une série d'histogrammes, réunis au sein de ce qu'on appellera une palette.

Dans la seconde phase, on utilise cette palette pour réaliser l'animation proprement dite. À chaque pas de l'animation, on déplace le leader, puis on déplace tous les individus un par un. Chacun de ces derniers est mis à jour en fonction de ceux déjà déplacés, par souci de cohérence.

Prise de décision

La décision du déplacement de chaque individu implique plusieurs algorithmes probabilistes connus.

On va tirer N déplacements possibles, afin de retenir la meilleure par la suite, conformément à l'algorithme de Monte-Carlo.

On tire d'une part la direction de l'agent, et d'autre part la norme de sa vitesse. Ces tirages ne sont pas faits au hasard, puisque c'est à cette étape qu'on va chercher à reproduire la cohérence du mouvement de l'agent -- on pourrait dire aussi, la continuité du mouvement. L'objectif est d'éviter d'engendrer des changements de direction ou de vitesse trop brutaux. On peut exploiter, pour cela, les histogrammes cumulés, facilement déductibles des résultats de l'apprentissage. Par exemple, les images ci-dessous illustrent notre méthode pour tirer des vitesses qui à la fois suivent une loi voulue (un régime lent et un régime rapide dans l'exemple), et assurent une continuité dans le changement des vitesses : au lieu de perturber la vitesse courante V0, on perturbe son image par la fonction de répartition.

Densite.png
Repartition.png

On utilise un critère de Metropolis-Hastings pour sélectionner le déplacement. On se limite cependant à valider le premier déplacement qui satisfait la condition de l'algorithme (la probabilité min(1,r)).

Enfin, on conclut cette exécution de l'algorithme de Monte-Carlo en sélectionnant le déplacement qui maximise le score par l'évaluation de la fonction-distribution. Il s'agit simplement de faire, pour chaque déplacement, le produit des images de tous les histogrammes de la palette. Concrètement, c'est lors de cette étape qu'on fait en sorte que le déplacement permette de passer vers la meilleure distribution des individus possibles ; typiquement, il faut qu'ils soient suffisamment proches ou éloignés les uns des autres, à une certaine distance du leader, etc.

Note : Une seconde approche, que nous avons testée, consiste à ne pas tirer les déplacements comme on l'a décrit, mais à appliquer à l'individu le même déplacement que le leader, puis à perturber aléatoirement ce déplacement afin de ne pas obtenir une trajectoire trop rigide. Cette approche a les avantages d'être moins coûteuse en calculs et de simuler une formation plus stable. Cependant, elle n'est pas adaptée pour certains comportements, comme celui du double régime de marche dont on a parlé plus haut.


Démonstration et Bilan

Limites inhérentes à l'utilisation d'histogrammes

Il existe trois grandes difficultés à utiliser des histogrammes comme nous le faisons:

- dans le cas d'histogrammes à classes de même taille, la calibration des classes est délicate puisque l'on doit faire un compromis entre précision de l'histogramme et difficulté à le remplir si l'on a trop de classes

- pour remplir correctement un histogramme, nous avons besoin de beaucoup de données. C'est pour cette raison que nous nous sommes limités à des histogrammes 2D. De plus avoir des classes vides peut poser problème et nous avons donc comblé les "trous" dans l'apprentissage par interpolation linéaire. Une interpolation plus élaborée (gaussienne par exemple) pourrait donner des résultats plus convaincants et éviter des artefacts que nous avons constaté (lignes verticales sur l'histogramme ci-dessous).

Histogramme artefact.png

- les histogrammes sont bornés et donc il peut arriver que l'on "sorte" de l'histogramme. Par exemple si le leader avance trop vite, les individus vont en être si éloignés que l'histogramme deviendra inutile ; on doit donc s'assurer de limiter la vitesse du leader.

Approche par translation du leader puis ajustement des individus

Nous avons testé notre première approche sur 2 échantillons différents (leader en rouge, suiveurs en blanc):

- des individus très mobiles qui ont deux régimes de vitesse (marche/course) : Média:Bivitesse_echantillon.mp4

- un groupe plus rigide qui reste toujours à une même distance du leader : Média:groupe_rigide_echantillon.mp4


Voici les résultats obtenus:

- groupe à deux vitesses : Média:Bivitesse_reconstitution.mp4

- groupe rigide : Média:groupe_rigide_reconstitution.mp4


Pour le groupe à deux vitesses, nous avons coloré les individus qui courent en vert. On constate que le comportement global est assez bien respecté, notamment la distance au leader et les deux régimes de vitesse. Cependant sur la simulation les individus sont bien plus "instables" que dans l'échantillon.

Pour le groupe rigide, on remarque que le paramètre de distance au leader est très bien respecté mais prend le pas sur le paramètre d'interdistance qui ne semble pas avoir beaucoup d'influence.

Dans les deux cas, la carte d'encombrement est bien gérée (en blanc les obstacles et en jaune les trajectoires):

Carte encombrement 1.png
Carte encombrement 2.png

La seconde capture montre un individu qui passe à travers un obstacle; cela arrive parfois quand les autres contraintes sont trop fortes.


Pour une validation plus précise de l'apprentissage, voici pour le groupe à deux vitesses une comparaison entre les histogrammes appris (à gauche) et les histogrammes reconstruits à partir de notre simulation statistique (à droite):

Histo vitesse appris.png
Histo vitesse reconstitué.png

vitesse de l'individu (abscisse) et distance au leader (ordonnée)














Histo distALeader appris.png
Histo distALeader reconstitué.png

distance au leader (abscisse) et vitesse du leader (ordonnée)














Histo position angulaire appris.png
Histo position angulaire reconstitué.png

position angulaire dans le repère du leader (abscisse entre -PI et PI) et distance au leader (ordonnée)















Ainsi les paramètres appris sont respectés de manière satisfaisante.


Nous avons donc identifié plusieurs causes possibles aux défauts que l'on observe:

- les paramètres appris ne sont pas suffisants: soit il faudrait en apprendre davantage, soit il faudrait faire des corrélations à plus de deux variables

- les histogrammes très marqués (distance au leader pour le groupe rigide) prennent le pas sur les autres. Pour mieux répartir l'importance des histogrammes, il faut changer la fonction de calcul du score utilisée pour choisir la meilleur position parmi les N probables. Dans le produit des scores (interdistance, obstacles etc.), on peut par exemple donner des puissances différentes aux scores intermédiaires.

Approche par translation du leader et du groupe, puis ajustement du groupe

Malheureusement nous avons manqué de temps pour développer cette méthode autant que la première.

Voici un exemple de simulation par translation pour un groupe dont on a appris seulement l'interdistance.

Média:translation.mp4


Cette approche semble plus adaptée pour des groupes qui restent très proches du leader. De plus elle est moins coûteuse que le précédente puisque lors de la translation du groupe entier, une grande partie de la décision a été prise et il suffit d'un petit ajustement. En revanche, nous n'avons pas réussi a apprendre et retranscrire le comportement d'individus à deux régimes de vitesse avec cette méthode.


Conclusion

Réaliser un projet de recherche nous a permis de nous familiariser avec de nouvelles méthodes de travail. En effet, l'ensemble des projets que nous avions menés à bien jusqu'ici avaient pour point commun d'être fortement guidés. Pour ce projet, nous avons au contraire dû définir et redéfinir nos objectifs au fur et à mesure de l'avancement du projet, et nous avons dû tenter différentes approches sans pouvoir nous assurer a priori de leur pertinence.

Voici les diapositives de notre présentation orale: Média:soutenance_diapos.pdf

Voici le code java utilisé pour générer les données : Média:generateur_java.tar.gz

Voici le code C++ principal (méthode 1) : Média:groupe_multivitesse.tar.gz (nécessite sfml, eigen3, boost-regex)

Enfin, voici le code C++ de la méthode 2 (moins commenté) : Média:groupe_translation.tar.gz (nécessite sfml, eigen3, boost-regex)

Nous remercions Marie-Paule Cani et Ulysse Vimont pour leur encadrement au cours de ce projet.