L'algorithme de condensation est une méthode probabiliste pour le suivi d'objets dans des séquences visuelles et d'autres systèmes dynamiques. Il appartient à la famille des filtres particulaires, qui représentent la distribution de probabilité de l'état d'un système à l'aide d'un ensemble d'échantillons aléatoires pondérés, appelés particules. Le nom « condensation » est un acronyme pour Conditional Density Propagation, reflétant son opération centrale de propagation d'une densité de probabilité conditionnelle au fil du temps. L'algorithme a été introduit au milieu des années 1990 comme une approche pratique du suivi visuel, en particulier pour les objets se déplaçant dans des environnements encombrés où les filtres de Kalman traditionnels, qui supposent une dynamique linéaire et un bruit gaussien, sont inadéquats.
L'algorithme fonctionne selon un cycle récursif de prédiction et de mise à jour. À chaque pas de temps, il tire un nouvel ensemble de particules à partir de l'ensemble précédent, avec des probabilités proportionnelles à leurs poids, un processus connu sous le nom de rééchantillonnage ou de sélection. Chaque particule sélectionnée est ensuite propagée selon un modèle de mouvement qui prédit le nouvel état de l'objet, en ajoutant souvent un bruit aléatoire pour tenir compte de l'incertitude. Enfin, l'algorithme mesure dans quelle mesure chaque particule prédite correspond aux données d'image ou de capteur observées, en attribuant un poids basé sur cette vraisemblance. L'ensemble de particules pondérées approxime alors la distribution a posteriori de l'état de l'objet, et la position estimée est typiquement la moyenne pondérée ou la particule avec le poids le plus élevé.
Développement historique
L'algorithme de condensation a été développé par Michael I. Jordan et ses collègues à l'Université de Californie à Berkeley dans les années 1990. L'article fondateur, « Condensation - Conditional Density Propagation for Visual Tracking », a été publié en 1998 par Michael Isard et Andrew Blake, qui étaient alors respectivement à l'Université d'Oxford et au MIT Media Lab. Le travail s'est appuyé sur des méthodes antérieures de filtrage particulaire, telles que le filtre bootstrap introduit par Neil Gordon, David Salmond et Adrian Smith en 1993, et la technique de rééchantillonnage par importance séquentielle. L'algorithme a été spécifiquement conçu pour répondre aux limitations du filtre de Kalman dans le suivi visuel, où le mouvement de l'objet peut être hautement non linéaire et le modèle d'observation peut être multimodal en raison d'occlusions ou de bruit de fond.
Détails algorithmiques
L'algorithme de condensation peut être décrit en quatre étapes principales. Premièrement, l'initialisation : un ensemble de N particules est tiré à partir d'une distribution a priori initiale, chacune avec un poids égal. Deuxièmement, la sélection : un nouvel ensemble de N particules est échantillonné avec remplacement à partir de l'ensemble courant, où la probabilité de sélectionner une particule est proportionnelle à son poids. Cette étape concentre les particules dans les régions de haute vraisemblance. Troisièmement, la prédiction : chaque particule sélectionnée est propagée à travers un modèle dynamique, par exemple, une marche aléatoire ou un modèle à vitesse constante, avec un bruit gaussien ajouté pour représenter l'incertitude du processus. Quatrièmement, la mise à jour de mesure : chaque particule prédite est comparée à l'observation courante à l'aide d'une fonction de vraisemblance, et son poids est mis à jour en conséquence. Le cycle se répète ensuite pour l'image suivante.
Une caractéristique clé de l'algorithme est sa capacité à maintenir plusieurs hypothèses simultanément. Parce que les particules peuvent se répartir sur différents modes de la distribution a posteriori, l'algorithme peut suivre des objets à travers des occlusions temporaires ou des situations ambiguës. Le nombre de particules, N, est un paramètre critique : trop peu de particules conduisent à une mauvaise approximation, tandis que trop augmentent le coût computationnel. Les implémentations typiques utilisent de quelques centaines à quelques milliers de particules, selon la dimensionnalité de l'état et la complexité du modèle d'observation.
Applications
L'algorithme de condensation a été largement appliqué en vision par ordinateur et en robotique. Son utilisation principale est le suivi visuel, comme suivre la tête ou les mains d'une personne dans des séquences vidéo, suivre des véhicules dans la surveillance du trafic, et suivre la pose d'objets articulés. Il a également été utilisé en imagerie médicale, par exemple, pour suivre le mouvement du cœur dans des séquences échographiques, et en réalité augmentée pour estimer la pose de la caméra. En robotique, l'algorithme sous-tend la localisation de Monte Carlo, une méthode pour qu'un robot estime sa position dans une carte connue à l'aide de filtres particulaires. La flexibilité de l'algorithme a également conduit à son utilisation dans la reconnaissance vocale et la séparation de sources audio, où l'espace d'état est la position ou l'identité des sources sonores.
Limitations et extensions
Malgré ses forces, l'algorithme de condensation présente des limitations connues. La version de base souffre de la dégénérescence des particules, où après quelques itérations, la plupart des particules ont des poids négligeables, gaspillant l'effort computationnel. Le rééchantillonnage atténue ce problème mais peut conduire à un appauvrissement de l'échantillon, où l'ensemble de particules perd en diversité, surtout dans des scénarios à faible bruit. Diverses extensions ont été proposées pour résoudre ces problèmes, notamment l'utilisation du rééchantillonnage systématique, le filtre particulaire auxiliaire et le filtre particulaire non parfumé. L'algorithme nécessite également une fonction de vraisemblance soigneusement conçue, ce qui peut être difficile dans des scènes complexes. En pratique, le choix du nombre de particules et des paramètres du modèle de mouvement affecte significativement les performances, et leur réglage est souvent effectué de manière empirique.
Relation avec d'autres méthodes
L'algorithme de condensation est une instance spécifique de la classe plus large des filtres particulaires, également connus sous le nom de méthodes de Monte Carlo séquentielles. Il est étroitement lié au filtre bootstrap et au filtre de rééchantillonnage par importance. Dans le contexte de apprentissage automatique, les filtres particulaires sont utilisés dans les modèles d'espace d'état, tels que les modèles de Markov cachés avec des états continus, et dans l'apprentissage par renforcement pour l'évaluation de politiques. L'algorithme est également connecté aux méthodes de Monte Carlo en général, qui utilisent l'échantillonnage aléatoire pour approximer des distributions de probabilité complexes. Comparé aux filtres de Kalman, qui fournissent des estimations optimales pour les systèmes linéaires gaussiens, l'algorithme de condensation est sous-optimal mais bien plus général, gérant des dynamiques non linéaires et un bruit non gaussien. Cette généralité en a fait un outil standard dans la communauté de la vision par ordinateur, et il reste une technique fondamentale en robotique probabiliste et en suivi visuel.
Voir aussi
- Filtre particulaire
- Filtre de Kalman
- Suivi visuel
- Méthodes de Monte Carlo