F il trage Particulaire

Filtrage Particulaire

Paulo Menezes Université de Coimbra

Portugalpm@deec.uc.pt

04/22/23

Le problème de l’estimation

• Si on considère que l’évolution de l’état d’un processus peut être décrite par

où représente l’état du processus à l’instant k, représente le bruit, et est une fonction qui pourra être non-lineaire.

€

x k = f(x k−1,vk )

€

x k

€

vk

€

f()

04/22/23

Le problème de l’estimation

• Ce vecteur d’état est une collection de variables du système, qui peuvent être mesurées ou non.

• Dans le cas plus commun ce qu’on peut mesurer est une fonction bruité de cet ensemble de variables

€

zk = g(x k,nk )

04/22/23

Le problème de l’estimation

• Ce qu’on souhaite c’est d’estimer l’état à un instant k à partir de l’observation d’un ensemble de mesures.

• Mais... On ne peut pas affirmer que la (ou les valeurs) estimées pour l’état sont exactes.

• Alors on essaye toujours de modéliser le dégrée de certitude de notre estimation.

04/22/23

Approximation probabiliste

• L’état estimé et le dégrée de confidence sont décrits par une fonction distribution de probabilité (pdf).

• Alors ce qu’on veut obtenir est

la distribution de probabilité de l’état connaissant la séquence de valeurs mesurées.€

p(x k | z1:k )

04/22/23

Estimation recursive

• Si on considère que la distribution initiale est connue, on peut estimer l’évolution de cette pdf de façon récursive.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

04/22/23

Estimation probabiliste

• Modèle d’évolution du système

• Modèle des mesures

• Information disponible

• On cherche i=0: Filtrage i>0: Prédiction i<0: Lissage

€

x k = f(x k−1,vk ) ↔ p(x k | x k−1)

€

zk = h(x k |nk ) ↔ p(x k | z1:k )

€

z1:k = (z1,z2,...,zk )

€

p(x0)

€

p(x k+i | x1:k )

04/22/23

Deux étapes

• Partant de , on peut utiliser l’équation de Chapman-Kolmogorov pour l’étape de prédiction

• Et pour la correction

• où

04/22/23

Formulation Bayesienne

• Cette formulation récursive est la base de la solution optimal.

• Mais le problème c’est que on ne peut pas la déterminer de façon analytique, sauf que pour quelques cas où on impose des restrictions: ex. Filtre de Kalman

04/22/23

Filtre de Kalman

• Algorithme applicable dans le cas où le modèle du système bien que l’équation des mesures sont linéaires.

• Les bruits impliqués sont toujours Gaussiens

• Par conséquence l’état à estimer peut être décrit par une valeur moyenne e sa mesure de variance.

04/22/23

Filtre de Kalman Etendu

• Approximation de Taylor des modèles des systèmes nonlineaires.

• Condition: Bruit Gaussien• Requiert une bonne initialisation de l’état du

système, sinon risque de ne converger jamais. • La condition ne se vérifie vraiment car une

Gaussienne qui passe par une fonction nonlineaire n’est plus une Gaussienne. Alors l’estimation de la moyenne et de la covariance n’est pas très précise.

04/22/23

Gaussian Samples thru x^2

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

04/22/23

Unscented Kalman Filter

• Ce type de filtre fait une meilleure approximation de l’évolution de la moyenne et variance. Mais repose toujours sur l’approximation de la pdf de l’état par une Gaussienne.

04/22/23

Méthodes Monte Carlo

• Exemple: Recouvrir une fenêtre avec des feuilles qui tombent d’une arbre

Vue supérieure Vue inférieure

04/22/23

Méthodes Monte Carlo

• Calculer la valeur de Pi

€

Ar = l∗l

€

Ac = π ∗(l /2)2

€

ArAc

= π4

QuickTime™ and a decompressor

are needed to see this picture.

04/22/23

Importance Sampling

• Pour une distribution de probabilité p(x|z) e une fonction g(x), si on souhaite calculer l’integral

• On peut l’écrire

• Dés que la deuxième fonction ne s’annule pas sauf que pour les valeurs on la premiere est nule

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

04/22/23

Importance Sampling

• Si on fait

• Et si la deuxième pdf est du type qu’on puisse générer des échantillons facilement, on peut faire une approximation Monte-Carlo de l’intégral par

• Où représente les valeurs sont appelées les poids d’importance.

QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture. QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.QuickTime™ and a

TIFF (Uncompressed) decompressorare needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.

04/22/23

Importance Sampling

• C’est assez rare qu’on puisse évaluer directement

• Par contre, on peut normalement évaluer• Et est n’est pas utilisable dans la plupart

des cas.• On peut utiliser la règle de Bayes pour

réécrire l’intégral précèdent

QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.

04/22/23

Importance Sampling

• Où

peut être calculé

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

04/22/23

Importance Sampling

• Dans ce cas on peut générer des échantillons pour approximer les deux intégraux par

où

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

04/22/23

Sequencial Importance Sampling (SIR)

• Supposons qu’il a une pdf p(.) à partir de laquelle c’est très difficile de générer des échantillons. On connaît une autre pdf (.) qui est proportionnelle à la première et qui est facile à évaluer.

• On connaît une autre pdf q(.) à partir de laquelle est très facile de générer des échantillons.

04/22/23

SIR

• Pour un ensemble d’échantillons de q(.)

• Une approximation de p(x) peut être obtenue par

• où

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.

04/22/23

SIR

• Si les échantillons sont générés à partir d’une densité d’importance

• Les poids deviennent

• Si on factorise la densité d’importance

• On peut obtenir en ajoutant aux échantillonsle nouveau état

QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.QuickTime™ and a

TIFF (Uncompressed) decompressorare needed to see this picture.

04/22/23

SIR

• Si on exprime commeQuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

04/22/23

SIR

• En remplaçant dans l’expression du poids, on obtient

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

04/22/23

SIR

• Si

alors

et la pdf peut être approximée par

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

04/22/23

SIR

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

04/22/23

SIR

• Problème: au bout de quelques itérations, la plupart des échantillons (particules) on un poids qui tends vers zéro. On appelle à ce phénomène dégénération.

• On est dans cette situation quand devient proche de zéro.

• Deux solutions: bon choix de la distribution d’importance ou regénérer les échantillons.

QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.

QuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.

04/22/23

Re-sampling

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

04/22/23

Filtre Particulaire

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

04/22/23

Condensation

QuickTime™ and aTIFF (Uncompressed) decompressor

are needed to see this picture.

04/22/23

Filtre Particulaire

Distribution Initiale

Reéchantionnage

Bruitage

Ponderation

Distribution Finale

X X X X X

04/22/23

Exemples

04/22/23

Suivi basé sur la distribution de couleur

QuickTime™ and aH.263 decompressor

are needed to see this picture.

04/22/23

Suivi du brasQuickTime™ and a

Vidéo decompressorare needed to see this picture.

04/22/23

Suivi sur un fond encombréQuickTime™ and a

Foto - JPEG decompressorare needed to see this picture.

QuickTime™ and aFoto - JPEG decompressorare needed to see this picture.

04/22/23

Estimation 3D

QuickTime™ and aCinepak decompressor

are needed to see this picture.

04/22/23

FIN