Apprendre le filtre de Kalman depuis les bases

 (kalmanfilter.net)
7 points par GN⁺ 2023-10-16 | 1 commentaires | Partager sur WhatsApp
  • Le filtre de Kalman est un algorithme qui estime l’état actuel et prédit l’avenir dans des systèmes soumis à du bruit de mesure et à des facteurs externes inconnus ; il est utilisé dans des domaines comme le suivi, la navigation, la robotique et le contrôle
  • L’exemple de radar unidimensionnel mesure la distance (r) et la vitesse (v) d’un avion, et traite à la fois l’état et l’incertitude au moyen du vecteur d’état (\boldsymbol{x}=[r, v]^T) et des matrices de covariance (\boldsymbol{P}, \boldsymbol{R}, \boldsymbol{Q})
  • Les mesures initiales sont une distance de 10 000 m et une vitesse de 200 m/s ; avec un intervalle d’échantillonnage de 5 secondes et un modèle à vitesse constante, la position prédite suivante est de 11 000 m
  • L’étape de prédiction propage l’état avec la matrice de transition d’état (\boldsymbol{F}), puis calcule la covariance avec (\boldsymbol{F}\boldsymbol{P}\boldsymbol{F}^T+\boldsymbol{Q}), ce qui reflète l’effet par lequel l’incertitude sur la vitesse et le bruit de processus accroissent l’incertitude sur la position
  • L’étape de mise à jour ne croit pas aveuglément la nouvelle mesure et ne la rejette pas non plus : elle combine la prédiction et la mesure par pondération avec le gain de Kalman afin de réduire l’incertitude de l’estimation ; le filtre répète ensuite prédiction et mise à jour

Le problème traité par le filtre de Kalman

  • Le filtre de Kalman est un algorithme qui réalise une estimation d’état et une prédiction du futur dans des systèmes incertains
    • Il traite les situations où du bruit de mesure est présent, ou où des facteurs externes inconnus influencent le système
    • Il est utilisé comme outil clé dans le suivi d’objets, la navigation, la robotique et le contrôle
    • Pour l’estimation de la trajectoire d’une souris d’ordinateur, il peut réduire les tremblements de la main et le bruit afin de produire un déplacement plus stable
    • En analyse des marchés financiers, il sert à détecter les tendances des cours dans des données de marché bruitées ; en météorologie, il est appliqué aux prévisions météo
  • Ce tutoriel construit l’intuition au moyen d’un exemple numérique, plutôt que de commencer par des mathématiques complexes
    • Il inclut aussi un exemple où un filtre de Kalman mal conçu ne parvient pas à suivre correctement un objet
    • L’objectif est d’atteindre un niveau permettant de comprendre les concepts et les mathématiques, puis de concevoir et d’implémenter soi-même le filtre

Parcours d’apprentissage

  • Le parcours d’apprentissage proposé se divise en trois étapes
    • Vue d’ensemble en une seule page : explique les concepts clés et les équations essentielles sans démonstration, en supposant des bases en statistiques et en algèbre linéaire
    • Tutoriel web gratuit fondé sur des exemples : le tutorial construit l’intuition avec des exemples numériques et traite étape par étape jusqu’à la dérivation des équations du filtre de Kalman
    • Livre : Kalman Filter from the Ground Up inclut 14 exemples numériques entièrement résolus, des graphiques et tableaux de performance, l’Extended Kalman Filter et l’Unscented Kalman Filter, la fusion de capteurs et des lignes directrices d’implémentation

Pourquoi la prédiction est nécessaire dans le suivi radar

  • Pour qu’un radar suive un avion, il doit pointer de façon répétée un faisceau étroit vers la cible ; il faut donc prédire la position future au moment où le prochain faisceau sera émis
    • Si la prédiction échoue, le faisceau peut être dirigé dans la mauvaise direction et le suivi peut être perdu
    • Il faut un modèle dynamique décrivant comment l’avion se déplace au fil du temps
  • Dans l’exemple unidimensionnel simplifié, on ne considère que le mouvement en ligne droite de l’avion, qui se rapproche ou s’éloigne du radar
    • L’état est défini comme la distance (r) au radar
    • Le radar calcule la distance (r) à partir du temps d’émission/réception de l’impulsion et de la vitesse de la lumière
    • Il peut aussi mesurer la vitesse (v) au moyen de l’effet Doppler
  • Supposons qu’à (t_0), la distance 10 000 m et la vitesse 200 m/s aient été mesurées avec une exactitude et une précision très élevées
    • L’intervalle d’échantillonnage est (\Delta t=5s)
    • Dans le modèle à vitesse constante, la distance parcourue est (\Delta r=v\cdot\Delta t)
    • La position prédite est (10,000+200\cdot5=11,000m)

Bruit de mesure et bruit de processus

  • Les mesures radar réelles ne sont pas parfaites : même si plusieurs radars mesurent le même avion au même instant, ils produisent des résultats légèrement différents
    • Ces variations sont dues au bruit de mesure
    • Il faut calculer non seulement l’estimation, mais aussi dans quelle mesure cette estimation est fiable
  • Le modèle dynamique ne décrit pas non plus entièrement le mouvement réel
    • Même si l’on suppose que l’avion se déplace à vitesse constante, des facteurs externes comme le vent peuvent modifier son mouvement réel
    • Ces influences imprévisibles sont traitées comme du bruit de processus
  • Le filtre de Kalman fournit ensemble l’estimation de l’état actuel, la prédiction de l’état futur et leurs incertitudes respectives
    • Il est présenté comme un algorithme optimal qui minimise l’incertitude de l’estimation d’état

Représentation de l’état et initialisation dans l’exemple radar

  • L’état du système de l’exemple est un vecteur comprenant la distance (r) et la vitesse (v) de l’avion

[ \boldsymbol{x}=\left[\begin{matrix}r\v\\end{matrix}\right] ]

  • Les vecteurs sont notés en minuscules grasses, les matrices en majuscules grasses
  • On initialise le filtre de Kalman avec la première mesure
    • À (t_0), les mesures sont une distance de 10 000 m et une vitesse de 200 m/s
    • Le vecteur de mesure est le suivant

[ \boldsymbol{z}_0=\left[\begin{matrix}10{,}000\200\\end{matrix}\right] ]

  • Les mesures ne sont pas l’état exact du système, mais des variables aléatoires bruitées
    • L’écart-type de la mesure de distance est (4m)
    • L’écart-type de la mesure de vitesse est (0.5m/s)
    • La variance étant le carré de l’écart-type, la matrice de covariance de mesure (\boldsymbol{R}_0) est la suivante

[ \boldsymbol{R}_0=\left[\begin{matrix}16&0\0&0.25\\end{matrix}\right] ]

  • Dans cet exemple, on suppose que les erreurs de mesure de distance et de vitesse ne sont pas corrélées, donc les éléments hors diagonale de la matrice de covariance sont fixés à 0
  • Au moment de l’initialisation, comme on ne dispose que d’une seule mesure, on peut utiliser la mesure comme estimation initiale de l’état

[ \boldsymbol{\hat{x}}_{0,0}=\boldsymbol{z}_0=\left[\begin{matrix}10{,}000\200\\end{matrix}\right] ]

  • Cette approche n’est possible qu’à l’étape d’initialisation

Étape de prédiction : propagation de l’état et de la covariance

  • Pour prédire l’état suivant, on utilise un modèle dynamique à vitesse constante

[ v_1=v_0=v ]

[ r_1=r_0+v_0\Delta t ]

  • La prédiction d’état sous forme matricielle est la suivante

[ {\hat{\boldsymbol{x}}}{1,0}=\boldsymbol{F}{\hat{\boldsymbol{x}}}{0,0} ]

  • (\boldsymbol{F}) est la matrice de transition d’état ; avec (\Delta t=5s), le résultat de la prédiction est le suivant

[ {\hat{\boldsymbol{x}}}_{1,0}

\left[\begin{matrix}1&5\0&1\\end{matrix}\right] \left[\begin{matrix}10,000\200\\end{matrix}\right]

\left[\begin{matrix}11,000\200\\end{matrix}\right] ]

  • L’extrapolation générale de l’état, c’est-à-dire l’équation de prédiction, est la suivante

[ {\hat{\boldsymbol{x}}}{n+1,n}=\boldsymbol{F}{\hat{\boldsymbol{x}}}{n,n}+\boldsymbol{G}\boldsymbol{u}_n ]

  • (\boldsymbol{u}_n) est la variable d’entrée
  • (\boldsymbol{G}) est la matrice de transition d’entrée
  • Dans l’exemple, il n’y a pas d’entrée, donc (\boldsymbol{u}_n=0)
  • La covariance ne se calcule pas simplement avec (\boldsymbol{F}\boldsymbol{P})
    • En effet, la covariance inclut des termes quadratiques de variance et de covariance
    • Sans bruit de processus, l’équation d’extrapolation de la covariance est la suivante

[ \boldsymbol{P}{n+1,n}=\boldsymbol{F}\boldsymbol{P}{n,n}\boldsymbol{F}^T ]

  • Dans l’exemple, la propagation de la covariance initiale (\boldsymbol{P}_{0,0}) donne le résultat suivant

[ \boldsymbol{P}_{1,0}

\left[\begin{matrix}22.25&1.25\1.25&0.25\\end{matrix}\right] ]

  • La variance de la vitesse reste (0.25m^2/s^2)
  • La variance de la distance passe de (16m^2) à (22.25m^2)
  • L’incertitude sur la vitesse se traduit, avec le temps, par une incertitude sur la distance

Prise en compte du bruit de processus

  • La seule hypothèse de vitesse constante ne permet pas de décrire entièrement le mouvement réel d’un avion
    • Des facteurs externes inconnus, comme le vent, peuvent influencer la vitesse
    • Ces influences imprévisibles sont représentées par le bruit de processus (\boldsymbol{Q})
  • L’équation de prédiction de la covariance incluant le bruit de processus est la suivante

[ \boldsymbol{P}{n+1,n}=\boldsymbol{F}\boldsymbol{P}{n,n}\boldsymbol{F}^T+\boldsymbol{Q} ]

  • Dans l’exemple, on suppose que l’écart-type de l’accélération aléatoire est (\sigma_a=0.2m/s^2)
    • La variance est (\sigma_a^2=0.04m^2/s^4)
    • Avec (\Delta t=5s), la matrice de bruit de processus est la suivante

[ \boldsymbol{Q}

\left[\begin{matrix}6.25&2.5\2.5&1\\end{matrix}\right] ]

  • La covariance prédite après ajout du bruit de processus est la suivante

[ \boldsymbol{P}_{1,0}

\left[\begin{matrix}28.5&3.75\3.75&1.25\\end{matrix}\right] ]

Étape de mise à jour : combinaison de la mesure et de la prédiction

  • À (t_1), la deuxième mesure est la suivante

[ \boldsymbol{z}_1= \left[\begin{matrix}11{,}020\202\\end{matrix}\right] ]

  • Cette mesure a un rapport signal/bruit plus faible et une incertitude plus grande que la première mesure, en raison d’un fort pic de bruit
    • L’écart-type de la mesure de distance est (6m)
    • L’écart-type de la mesure de vitesse est (1.5m/s)
    • La matrice de covariance de mesure est la suivante

[ \boldsymbol{R}_1= \left[\begin{matrix}36&0\0&2.25\\end{matrix}\right] ]

  • À (t_1), on peut utiliser à la fois l’état prédit calculé à l’étape précédente et la nouvelle mesure
    • Les éléments diagonaux de la covariance prédite (\boldsymbol{P}_{1,0}) sont (28.5), (1.25)
    • Les éléments diagonaux de la covariance de mesure (\boldsymbol{R}_1) sont (36), (2.25)
    • Dans ce cas, l’incertitude de prédiction est plus faible que l’incertitude de mesure
  • Le filtre de Kalman n’utilise pas directement la nouvelle mesure et ne conserve pas non plus uniquement la prédiction
    • Il combine la prédiction et la mesure sous forme de moyenne pondérée
    • Il donne un poids plus élevé à la source dont l’incertitude est la plus faible
  • La combinaison en forme unidimensionnelle est la suivante

[ \hat{x}{1,1}=K_1z_1+(1-K_1)\hat{x}{1,0} ]

  • (K_1) est le gain de Kalman ; il détermine le poids à attribuer à la mesure et à la prédiction
    • Tant que les hypothèses du modèle sont correctes, il minimise l’incertitude de l’estimation mise à jour

Mise à jour de l’état et innovation

  • L’équation de mise à jour de l’état sous forme matricielle est la suivante

[ \hat{\boldsymbol{x}}_{1,1}

\hat{\boldsymbol{x}}_{1,0} + \boldsymbol{K}_1(\boldsymbol{z}1-\hat{\boldsymbol{x}}{1,0}) ]

  • En général, la mesure et l’état du système peuvent ne pas représenter la même grandeur physique
    • Un thermomètre numérique mesure un signal électrique, alors que l’état du système peut être la température
    • Il faut alors une matrice d’observation (\boldsymbol{H}) qui transforme l’état prédit dans le domaine de mesure
  • L’équation générale de mise à jour de l’état est la suivante

[ \hat{\boldsymbol{x}}_{1,1}

\hat{\boldsymbol{x}}_{1,0} + \boldsymbol{K}_1(\boldsymbol{z}1-\boldsymbol{H}\hat{\boldsymbol{x}}{1,0}) ]

  • (\boldsymbol{z}1-\boldsymbol{H}\hat{\boldsymbol{x}}{1,0}) est l’innovation ou résidu, et représente la nouvelle information
  • Dans l’exemple, l’état et la mesure sont tous deux la distance et la vitesse ; (\boldsymbol{H}) est donc la matrice identité

Calcul du gain de Kalman

  • Le gain de Kalman unidimensionnel est le suivant

[ K_n=\frac{p_{n,n-1}}{p_{n,n-1}+r_n} ]

  • (p_{n,n-1}) est la variance de l’état prédit
  • (r_n) est la variance de mesure
  • Dans un filtre de Kalman multivarié, le gain de Kalman devient une matrice, donnée par

[ \boldsymbol{K}n= \boldsymbol{P}{n,n-1}\boldsymbol{H}^T \left( \boldsymbol{H}\boldsymbol{P}_{n,n-1}\boldsymbol{H}^T+\boldsymbol{R}_n \right)^{-1} ]

  • Le gain de Kalman calculé pour (t_1) dans l’exemple est le suivant

[ \boldsymbol{K}_1= \left[\begin{matrix}0.4048&0.6377\0.0399&0.3144\\end{matrix}\right] ]

  • L’inverse d’une matrice peut être calculé avec inv(A) dans MATLAB ou numpy.linalg.inv(A) en Python
    • Dans les implémentations réelles, il est généralement préférable de résoudre directement le système linéaire plutôt que de calculer explicitement l’inverse, par exemple avec A\b dans MATLAB ou numpy.linalg.solve(A, b) en Python

Résultat de la mise à jour et réduction de la covariance

  • Dans l’exemple, l’innovation est la suivante

[ \boldsymbol{z}1-\hat{\boldsymbol{x}}{1,0}

\left[\begin{matrix}20\2\\end{matrix}\right] ]

  • La correction obtenue en appliquant le gain de Kalman est la suivante

[ \boldsymbol{K}_1 \left[\begin{matrix}20\2\\end{matrix}\right]

\left[\begin{matrix}9.37\1.43\\end{matrix}\right] ]

  • L’estimation d’état mise à jour est la suivante

[ \hat{\boldsymbol{x}}_{1,1}

\left[\begin{matrix}11{,}009.37\201.43\\end{matrix}\right] ]

  • Pour la mise à jour multivariée de la covariance, la forme de Joseph est souvent utilisée

[ \boldsymbol{P}_{n,n}

(\boldsymbol{I}-\boldsymbol{K}n\boldsymbol{H}) \boldsymbol{P}{n,n-1} (\boldsymbol{I}-\boldsymbol{K}_n\boldsymbol{H})^T + \boldsymbol{K}_n\boldsymbol{R}_n\boldsymbol{K}_n^T ]

  • La littérature présente aussi fréquemment une forme simplifiée

[ \boldsymbol{P}_{n,n}

(\boldsymbol{I}-\boldsymbol{K}n\boldsymbol{H}) \boldsymbol{P}{n,n-1} ]

  • En arithmétique exacte, les deux formes donnent le même résultat
  • Dans une implémentation informatique, la forme de Joseph est généralement plus stable numériquement
  • Dans l’exemple, la mise à jour simplifiée de la covariance donne le résultat suivant

[ \boldsymbol{P}_{1,1}

\left[\begin{matrix}14.57&1.43\1.43&0.71\\end{matrix}\right] ]

  • L’incertitude de l’estimation mise à jour est inférieure à l’incertitude de prédiction et à l’incertitude de mesure
    • Les éléments diagonaux de la covariance prédite sont (28.5), (1.25)
    • Les éléments diagonaux de la covariance de mesure sont (36), (2.25)
    • Les éléments diagonaux de la covariance mise à jour sont (14.57), (0.71)
  • En théorie, une nouvelle information réduit l’incertitude de l’estimation, même si cette information est très incertaine
    • Dans les systèmes réels, il peut être nécessaire de rejeter des mesures peu fiables

Prédiction suivante et boucle répétée

  • L’étape de prédiction de l’itération 1 est effectuée de la même manière que celle de l’itération 0
    • Toutefois, le point de départ est (\hat{\boldsymbol{x}}{1,1}) et (\boldsymbol{P}{1,1}) mis à jour
  • La prédiction d’état est la suivante

[ \hat{\boldsymbol{x}}_{2,1}

\boldsymbol{F}\hat{\boldsymbol{x}}_{1,1}

\left[\begin{matrix}12,016.5\201.43\\end{matrix}\right] ]

  • La prédiction de covariance est la suivante

[ \boldsymbol{P}_{2,1}

\boldsymbol{F}\boldsymbol{P}_{1,1}\boldsymbol{F}^\top+\boldsymbol{Q}

\left[\begin{matrix}52.86&7.47\7.47&1.71\\end{matrix}\right] ]

  • Si le temps passe sans nouvelle mesure, les deux variances augmentent à nouveau
    • L’incertitude sur la vitesse accroît encore l’incertitude sur la distance, ce qui fait augmenter plus vite la variance de la distance
  • Le filtre de Kalman fonctionne selon une structure où il est initialisé une fois au départ, puis répète en continu prédiction et mise à jour
    • La prédiction propage l’estimation actuelle et la covariance au pas suivant à l’aide du modèle de transition d’état
    • La mise à jour combine la nouvelle mesure et la prédiction au moyen du gain de Kalman pour actualiser l’état courant et l’incertitude

À lire aussi

1 commentaires

 
GN⁺ 2023-10-16
Commentaires sur Hacker News

  • Chaque fois que je vois un « tutoriel pour débutants », j’ai de l’espoir, mais je suis généralement déçu, et celui-ci n’a pas fait exception
    Le début est bon, puis il y a toujours un concept ou un terme essentiel qu’on passe sans l’expliquer suffisamment. Ici, j’ai décroché au passage : « une variable aléatoire est décrite par une fonction de densité de probabilité, et une fonction de densité de probabilité est caractérisée par ses moments. Le moment d’une valeur de probabilité est l’espérance d’une puissance de la variable aléatoire ».
    Je ne sais pas s’il s’agit de l’espérance de l’exposant d’une valeur de probabilité, de l’espérance d’une certaine puissance de la valeur de probabilité, ni pourquoi une puissance aurait quelque chose de spécial plutôt que la valeur de probabilité elle-même. C’est frustrant : on a l’impression que les auteurs abandonnent soudain l’effort de vulgarisation au milieu de leur raisonnement, ou qu’ils n’ont pas eux-mêmes vraiment compris les notions de base et ne peuvent donc pas les expliquer aux autres. Ce serait bien de pouvoir poser des questions à l’enseignant comme sur Udemy, mais avec l’auteur d’un livre, il n’y a aucun moyen d’obtenir une réponse

    • L’apprentissage, surtout dans un nouveau domaine, est une structure en chaîne : s’il manque une connaissance préalable, il devient par définition impossible de comprendre
      Il suffit que l’auteur n’explique pas correctement une seule fois pour que tout s’effondre, et une boucle de feedback aide énormément. Sans cela, il faut finalement prendre la responsabilité de chercher soi-même les mots et les passages qu’on ne comprend pas. Il faut chercher les expressions qu’on ne maîtrise pas assez, comme « variable aléatoire » ou « fonction de densité de probabilité », et compléter avec Wikipedia, ChatGPT, des manuels, des vidéos, etc. Ce processus est récursif, donc d’autres notions inconnues apparaîtront, mais il suffit de continuer à descendre. La valeur d’un tuteur tient aussi à sa capacité à bien guider cette recherche en profondeur. Dans un nouveau domaine, il est courant de passer plus de temps à combler les connaissances de fond qu’à lire le texte lui-même, et le prochain sujet similaire ira peut-être plus vite
    • Pour ceux que la notion de « moment » laissait perplexes, cet article était éclairant et intéressant : https://gregorygundersen.com/blog/2020/04/11/moments/
      C’est presque étrange de ne pas avoir internalisé une notion aussi fondamentale en passant par la licence puis le master/doctorat
    • Le plus difficile quand on enseigne, c’est qu’on ne peut pas revenir au point de vue qu’on avait au moment où l’on ne savait pas encore ce qu’on sait déjà
      On oublie donc les choses qu’on considère comme évidentes. Je ressens un problème similaire dans les vidéos de 3blue1brown. Elles sont jolies, mais elles ne font pas forcément naître la compréhension ; ceux qui connaissent déjà le sujet hochent la tête en voyant des concepts familiers présentés proprement, mais pour quelqu’un comme moi, il semble y avoir trop de prérequis
    • C’est pour cela que je finis par ne même plus essayer de lire ce genre de tutoriel jusqu’au bout
      Pour comprendre le filtre de Kalman, il faut d’abord connaître les bases des probabilités et l’importance de la distribution gaussienne. La dérivation mathématique suppose que toutes les distributions de probabilité concernées sont gaussiennes, et une distribution gaussienne est déterminée de manière unique si l’on connaît ses moments d’ordre 1 et 2. Au final, on ne peut pas éviter d’introduire les moments, puis des mathématiques assez ardues suivent. Le filtre de Kalman n’est pas un sujet facile, et Rudolf Kalman a déclaré dans une interview que, sans son filtre, l’alunissage américain aurait été impossible
    • Il existe pas mal de similitudes entre le système de classement Elo et le filtre de Kalman
      On peut partir d’un cas simple univarié, puis le modifier et le généraliser ; j’ai toujours pensé que c’était une bonne façon d’enseigner le filtre de Kalman

  • Il y a quelques années, j’ai assisté à une courte série de conférences de Kalman, et il insistait très fortement sur la vertu de travailler directement avec les données d’observation
    Il estimait que partir d’un modèle supposé puis essayer de l’ajuster aux données introduisait des biais, et il citait comme bon exemple de ce principe les Principia de Newton. Selon son explication, Newton n’a pas cherché un modèle pour expliquer les lois de Kepler ; il a surtout utilisé des raisonnements géométriques pour déduire, à partir des lois de Kepler, la loi de la gravitation en carré inverse. C’était un excellent orateur, avec des opinions bien tranchées, et il a bien sûr aussi expliqué l’idée du filtre de Kalman, mais comme je n’en avais pas d’usage direct dans mon travail, j’en ai oublié les détails depuis longtemps

    • Ce genre de point semble trop souvent négligé
      J’ai effectivement travaillé avec des scientifiques et des ingénieurs qui ont déployé des systèmes très complexes et bien connus ; ces personnes sont généralement sceptiques vis-à-vis des algorithmes à la mode et partent en général des premiers principes. Dans 90 % des cas, un simple filtre de Kalman linéaire ordinaire, voire sans modèle de mouvement, suffisait

  • Récemment, un ami m’a demandé d’implémenter un filtre de Kalman pour un side project ; j’ai lu plusieurs ressources ainsi que ce site, mais je ne sais toujours pas comment m’y prendre
    Tout le monde semble dire « dessinez le reste du hibou ». J’aimerais trouver une ressource qui l’explique comme le ferait un programmeur, par exemple avec des boucles sur des tableaux plutôt qu’avec la notation sigma. D’après ce que j’ai compris, un filtre de Kalman ressemble à une moyenne mobile de la position, de la vitesse et peut-être de l’accélération, et il semble utiliser ces trois valeurs pour estimer la « valeur réelle » plutôt que la valeur indiquée par le capteur

    • Je ne sais pas trop pour les ressources, mais avec une bibliothèque d’algèbre linéaire comme NumPy, le code tient en quelques lignes
      En revanche, il faut d’abord écrire les maths qui décrivent la dynamique. Un filtre de Kalman revient plutôt à appliquer le théorème de Bayes à une dynamique de système donnée : à chaque mesure, on met à jour l’estimation de l’état courant, puis on applique de façon répétée l’effet de la dynamique du système sur l’incertitude jusqu’à la mesure suivante. Il faut d’abord un modèle dynamique qui indique comment l’objet suivi évolue dans le temps. Sans cela, l’implémentation ne peut qu’être confuse. Lire d’abord sur les filtres bayésiens ou les filtres particulaires peut aider à saisir le concept sans matrices. L’idée qu’on puisse être développeur logiciel sans connaître les maths m’a toujours frustré : c’est peut-être vrai pour faire des pages web, mais plus on connaît de maths, plus l’éventail des problèmes qu’on peut modéliser et résoudre s’élargit
    • Les variables réelles comme la position, la vitesse ou l’accélération dépendent du cas d’usage
      L’important est d’estimer à partir de cet état, puis, après réception d’une mesure, d’utiliser les deux informations pour ajuster itérativement l’état suivant. Une fois les formules comprises, le codage lui-même est assez simple. Cette ressource peut aider : http://bilgin.esme.org/BitsAndBytes/KalmanFilterforDummies
    • Il faut d’abord disposer d’un modèle de système dynamique linéaire en temps discret pour le processus
      On peut y ajouter un contrôle externe et un bruit de processus, et l’état interne est représenté par un vecteur de valeurs. Il faut aussi un modèle linéaire décrivant comment l’état interne est transformé en observations, ainsi qu’un bruit d’observation.
      x est l’état du modèle, F le modèle linéaire de transition d’état x(t+1) = F x(t), Q la matrice de covariance du bruit de processus, si bien qu’en réalité x(t+1) = F x(t) + N(0,Q), H le modèle linéaire d’observation, R la matrice de covariance du bruit d’observation, et u et B le vecteur de contrôle externe optionnel et la manière dont il agit. N(0,Q) est une distribution normale de moyenne 0 et de covariance Q.
      Par exemple, pour un objet en mouvement, l’état du modèle peut être la position x et la vitesse v. Avec un radar, etc., on observe généralement seulement la position, pas la vitesse actuelle ; le modèle d’observation ne fait donc qu’extraire la position. Avant de faire un filtre de Kalman, il faut d’abord avoir ce « hibou », et c’est à vous de le définir selon le processus concerné. Le filtre de Kalman indique comment estimer de manière optimale le vecteur d’état réel à chaque instant lorsque le modèle de transition d’état et les observations contiennent tous deux du bruit. Beaucoup de tutoriels mélangent la partie correspondant au modèle de processus choisi et la partie correspondant au filtre de Kalman, ce qui prête à confusion ; dans des exemples trop petits, comme un modèle constant unidimensionnel, le modèle dynamique disparaît des équations, ce qui rend les choses encore plus confuses
    • Je recommande le manuel Probabilistic Robotics de Dieter Fox, Sebastian Thrun et Wolfram Burgard
      Les premiers chapitres couvrent bien les filtres de Kalman et les filtres d’information
    • La moyenne mobile est un bon point de départ pour réfléchir
      Lorsqu’on sait que les mesures de capteur sont bruitées, l’idée est de moyenner plusieurs échantillons pour obtenir une estimation plus proche de la valeur réelle ; si l’on connaît le niveau de bruit du capteur, on a aussi une idée du nombre d’échantillons à moyenner. Ici, on peut considérer que toutes les valeurs détectées ou inférées sont estimées comme des distributions gaussiennes paramétrées par une moyenne et une variance.
      Dans un système physique avec accélération, vitesse et position, si à l’instant t la position est p et la vitesse v, alors à t+dt la position vaut approximativement p+(v*dt). On peut aussi mettre à jour la vitesse à partir d’une estimation de l’accélération, et, si le système est contrôlé, mettre à jour le modèle d’accélération à partir de la force commandée. Mais comme l’estimation initiale comporte de l’incertitude, si l’on ne fait que faire avancer ce modèle de processus, l’incertitude ne cesse d’augmenter jusqu’à devenir inutilisable.
      Le filtre de Kalman est une technique qui combine les informations des capteurs et le modèle de processus afin de mieux estimer la quantité qui nous intéresse que si l’on utilisait l’un ou l’autre seul. À chaque pas de temps, on prédit l’état avec le modèle de processus à partir de l’estimation de l’état précédent, puis on met à jour la moyenne et l’incertitude avec la mesure courante du capteur. Dans le filtre de Kalman de base, on suppose que le modèle de processus est linéaire et que toutes les estimations sont de simples distributions gaussiennes, puis on décide dans quelle mesure faire confiance au modèle ou au capteur au moyen d’un coefficient multiplicatif appelé gain de Kalman

  • Une autre playlist de tutoriels vidéo pas à pas sur le filtre de Kalman : https://www.youtube.com/watch?v=CaCcOwJPytQ&list=PLX2gX-ftPV...
    Une fois l’intuition acquise, le filtre de Kalman devient vraiment intéressant, et les filtres particulaires sont eux aussi amusants à manipuler et à visualiser

  • J’ai ce livre et je l’ai utilisé avec pas mal de succès sur de vrais problèmes
    Même après plusieurs relectures, certains passages restent un peu difficiles à suivre, mais dans l’ensemble il est assez bon

    • J’aimerais en savoir plus sur la partie « utilisé avec pas mal de succès sur de vrais problèmes »

  • Un autre bon article sur le sujet : Is the Kalman filter a low-pass filter? Sometimes!
    https://jbconsulting.substack.com/p/is-the-kalman-filter-jus...
    Je l’ai utilisé pour réduire les tremblements du mouvement d’une caméra virtuelle dans une vidéo qui recadre en temps réel autour d’un visage. Le flux des positions de visage détectées était envoyé à un opérateur de filtre de Kalman, qui renvoyait un flux de positions de caméra stabilisées

  • Quand les ressources de calcul sont limitées, le filtre de Kalman est excellent, mais personnellement je préfère des modèles plus récents et plus avancés comme les filtres particulaires.
    L’avantage des filtres particulaires est qu’ils peuvent gérer des situations complexes avec une physique non linéaire et des distributions non gaussiennes. Par exemple, le GPS d’une voiture peut utiliser une carte routière, à partir de l’historique récent des virages, pour éliminer les positions impossibles. Un filtre gaussien ne peut pas faire ce genre de traitement et ne produira qu’une masse floue couvrant quelques pâtés de maisons.

    • Si quelqu’un a de bonnes ressources pour apprendre les filtres particulaires, je suis preneur.
      Je me demande aussi s’il existe, pour du traitement hors ligne, des modèles plus récents ou plus avancés à recommander en dehors des filtres particulaires.

  • En 2007, je travaillais dans une entreprise d’adtech, et le CEO ainsi que l’équipe de recherche étaient obsédés par les filtres de Kalman pour optimiser les campagnes publicitaires sur les réseaux Google et MSN.
    Dans mon souvenir, cela fonctionnait dans une certaine mesure, mais aujourd’hui je ne retrouve plus la demande de brevet, et Zeta ainsi que Walmart ont racheté cette technologie.

  • Les explications du filtre de Kalman commencent presque toujours par quelque chose du genre : « Pour un exemple intuitif, pensez à un thermostat. Vous avez compris ? Très bien ! Maintenant, pour rendre ça encore plus intuitif, passons à de l’algèbre linéaire avancée. »
    Je me demande si quelqu’un a déjà vu une explication du filtre de Kalman qui ne se jette pas directement dans les maths.

    • On peut le voir comme une moyenne pondérée entre l’incertitude propagée de l’état et l’incertitude de la mesure de cet état.
      Si vous fermez les yeux et marchez vers un mur, votre certitude sur votre position diminue avec le temps ; au moment où votre doigt touche le mur, votre certitude sur votre position augmente brusquement. La première partie correspond à l’étape de prédiction, la seconde à la mise à jour par mesure. L’algèbre linéaire n’est que la manière de calculer ces poids dans un système dynamique linéaire avec bruit gaussien.
    • Le mème mathématique « dessinez le reste de la chouette » est tellement répandu qu’il n’est même plus un cliché.
    • Cet article peut valoir le coup : https://praveshkoirala.com/2023/06/13/a-non-mathematical-int...
    • Ça dépend du niveau avec lequel vous vous sentez à l’aise.
      Le filtre de Kalman repose sur des hypothèses statistiques comme la distribution normale, donc il faut au moins connaître les statistiques ainsi que les matrices de moyenne et de covariance. Avec ce niveau, vous devriez pouvoir suivre jusqu’avant la section 4 de https://sites.ualberta.ca/~dwiens/stat679/meinhold&singpurwa.... À partir de la section 4, c’est surtout le déroulé des calculs mathématiques nécessaires à l’implémentation réelle, ce qui n’apporte pas beaucoup de compréhension supplémentaire.
    • C’est le cours en ligne AI for Robotics de Sebastian Thrun qui m’a donné l’intuition.
      Le fait de tout traiter d’abord en une dimension, puis d’étendre aux problèmes multidimensionnels, aide vraiment à saisir le concept. La playlist du cours semble être ici : https://youtube.com/playlist?list=PLAwxTw4SYaPkCSYXw6-a_aAoX...
      La partie sur le filtre de Kalman commence avec la vidéo « Tracking Intro - Artificial Intelligence for Robotics ». Le cours gratuit semble aussi être ici, mais il faut se connecter pour y accéder : https://www.udacity.com/course/intro-to-artificial-intellige...

  • Comme je connaissais mal Kalman, j’ai lu les articles d’introduction de ce site, mais ça ne m’a pas vraiment parlé.
    En réfléchissant aux graphiques d’exemple, ça ressemblait surtout à une moyenne mobile exponentielle, beaucoup plus facile à comprendre. En cherchant des comparaisons sur Google, j’ai vu que sur Stats Stack Exchange, on disait que pour une « marche aléatoire + bruit », l’EMA était aussi bonne que Kalman, et qu’un article de 2003 de Joseph J. LaViola, de Brown University, semblait montrer que l’algorithme de double lissage exponentiel offrait la même qualité que Kalman et Kalman étendu, tout en étant 135 fois plus rapide et plus simple.
    Comme le double lissage exponentiel est bien plus facile à comprendre que Kalman, si l’article de LaViola est correct, je ne compte pas consacrer davantage d’efforts à comprendre Kalman.