Le filtre de Kalman expliqué simplement

• Le filtre de Kalman est un algorithme utilisé pour la prédiction et le contrôle à partir de capteurs, qui produit en temps réel des estimations d’état plus précises à partir de mesures bruitées ou imprécises
• Il ne se contente pas de lisser les mesures : il peut aussi estimer des variables d’état comme la position et la vitesse, difficiles à observer directement
• L’exemple de suivi radar montre comment, à partir de mesures de position 2D et d’une covariance, on estime la position et la vitesse d’un objet sous la forme d’un vecteur d’état 4×1
• Après avoir initialisé l’état avec les deux premières mesures, on répète ensuite les étapes de prédiction, de calcul du gain de Kalman (Kalman Gain), puis de mise à jour de l’état et de la covariance d’erreur
• Le filtre ne conserve comme historique qu’une seule estimation de l’état courant, ce qui le rend facile à implémenter même sur des équipements à mémoire limitée

---

Vue d’ensemble du filtre de Kalman

• Le filtre de Kalman peut être vu comme une boîte noire avec une entrée et une sortie
  • L’entrée est une mesure bruitée ou parfois imprécise
  • La sortie est une estimation plus précise, avec moins de bruit
• L’estimation peut correspondre à des paramètres d’état du système qui ne sont pas mesurés ou observés directement
• Il sert à estimer avec une grande précision, en temps réel, des paramètres observables et non observables
• Ces estimations très précises sont utilisées pour des prédictions fines et la prise de décision
• C’est pourquoi il est souvent employé en robotique et dans les systèmes temps réel, où une information fiable est indispensable

Le problème que résout le filtre de Kalman

• À partir de mesures imprécises ou bruitées, il permet d’estimer avec une meilleure précision l’état d’une variable, ou d’autres variables difficiles à observer directement
• Applications typiques :
  • Suivi d’objet : utiliser la position mesurée pour estimer plus précisément la position et la vitesse d’un objet
  • Estimation du poids avec une balance numérique : estimer le poids d’un objet à partir de la pression exercée sur la surface
  • Guidage, navigation et contrôle : estimer position, vitesse et accélération via des capteurs IMU, puis s’en servir pour contrôler le mouvement suivant
• La force du filtre de Kalman tient moins au lissage des mesures qu’à sa capacité à estimer des paramètres système difficiles à mesurer
• Dans les systèmes temps réel, une estimation plus précise se traduit par un meilleur contrôle et de meilleures fonctionnalités

Entrées et sorties de l’exemple de suivi radar

• L’exemple traite d’un cas de suivi radar servant à suivre des avions et des objets autour d’un aéroport
• L’état de trajectoire produit est utilisé pour l’affichage destiné aux opérateurs du contrôle aérien surveillant l’espace aérien
• Le radar fournit des mesures de position x, y dans un repère cartésien 2D
  • Les mesures sont représentées par le vecteur colonne 2×1 z
  • La matrice de variance-covariance des mesures est notée R
  • L’horodatage de la mesure est noté t
  • L’indice m désigne les paramètres de mesure, et k l’ordre des mesures
• Le filtre de Kalman estime la position et la vitesse de l’objet à partir des mesures radar
  • L’estimation est représentée par le vecteur colonne 4×1 x
  • La matrice de variance-covariance de l’estimation est représentée par la matrice 4×4 P
  • L’horodatage de l’estimation d’état est indiqué par T

Étape 1 : initialisation de l’état du système

• La méthode d’initialisation d’un filtre de Kalman varie selon l’application
• Dans cet exemple de suivi radar, l’état du système est initialisé avec la première mesure
• La mesure d’entrée ne contient que des informations de position, alors que l’état système en sortie contient la position et la vitesse de l’objet
• À l’arrivée de la première mesure, la seule information connue est la position à cet instant
  • Après la première estimation, l’état estimé du système est défini à partir de la position d’entrée
  • La covariance d’erreur de l’état du système est définie à partir de la précision de position de la première mesure

Étape 2 : réinitialisation de l’état du système

• Comme l’estimation de la vitesse nécessite une deuxième mesure de position, l’estimation de l’état du système est réinitialisée
• La vitesse est calculée par approximation linéaire
  • La vitesse est calculée comme distance parcourue / temps écoulé
• L’estimation mise à jour de l’état du système se compose de la position de la deuxième mesure et de la vitesse calculée
• La covariance d’erreur mise à jour de l’état du système intègre la précision de position de la deuxième mesure ainsi qu’une précision approximative de la vitesse
• Cette approximation de la précision de la vitesse peut être ajustée par tuning après avoir fait passer les données dans le filtre
  • Dans l’exemple, le terme de variance de la vitesse est fixé à 10⁴
  • Cette valeur indique une forte incertitude sur l’état de vitesse
  • Dans l’exemple, l’unité de vitesse est le m/s

Traitement itératif après l’initialisation

• Les deux premières étapes servent à initialiser puis réinitialiser l’estimation du système à partir de quelques mesures
• La méthode d’initialisation peut varier selon l’application
• L’objectif est d’obtenir une estimation d’état du système qui pourra ensuite être mise à jour avec les équations du filtre de Kalman
• Les étapes suivantes intègrent les nouvelles mesures dans le filtre et mettent à jour l’estimation d’état

Étape 3 : prédiction de l’estimation d’état du système

• À l’arrivée de la troisième mesure, l’estimation d’état du système est propagée vers l’avant afin de l’aligner dans le temps avec la mesure
• Cet alignement est nécessaire pour combiner la mesure et l’estimation d’état
• La prédiction s’appuie sur un modèle du système
• Dans l’exemple, un modèle de mouvement linéaire à vitesse constante approxime le changement de position de l’objet pendant l’intervalle de temps
  • Le modèle à vitesse constante suppose une accélération nulle
• La matrice de transition d’état représente cette équation de mouvement
  • Elle sert à propager correctement l’estimation d’état et la matrice de covariance d’erreur d’état
• Quand on propage l’estimation d’état vers un instant futur, une incertitude apparaît sur cet état futur, et la covariance d’erreur augmente donc

Matrices Q et H

• La matrice Q représente le bruit de processus du modèle du système
  • Le modèle du système est une approximation
  • La précision du modèle varie au cours de la vie de l’état du système
  • La matrice Q représente cette incertitude et s’ajoute au bruit existant de l’état
  • Dans l’exemple, les accélérations et décélérations réelles contribuent à cette erreur
• La matrice H est la matrice état-mesure, qui convertit l’estimation d’état du système de l’espace d’état vers l’espace de mesure
  • Dans certaines applications, c’est une matrice composée de 0 et de 1
  • Dans les applications qui utilisent un filtre de Kalman étendu (Extended Kalman Filter), elle est remplie d’équations différentielles
  • L’explication correspondante se poursuit dans l’article Extended Kalman Filters
• Dans cet exemple, la matrice H est une matrice simple qui réduit l’estimation d’état et la covariance d’erreur afin de ne comparer que les valeurs de position, et non l’ensemble position + vitesse

Étape 4 : calcul du gain de Kalman

• Le filtre de Kalman calcule un gain de Kalman pour chaque nouvelle mesure
• Le gain de Kalman détermine dans quelle mesure la mesure d’entrée influence l’estimation de l’état du système
• Si le bruit de la mesure est très élevé, le gain de Kalman accorde davantage de confiance à l’estimation d’état actuelle qu’à la nouvelle information, pourtant plus récente mais imprécise
• Le cœur de l’algorithme du filtre de Kalman consiste à pondérer correctement l’estimation actuelle et la nouvelle information de mesure pour produire une estimation optimale

Étape 5 : mise à jour de l’état et de la covariance d’erreur

• Le filtre de Kalman utilise le gain de Kalman pour estimer l’état du système et la matrice de covariance d’erreur à l’instant de la mesure d’entrée
• Le gain de Kalman sert à attribuer un poids approprié à la mesure dans deux calculs
  • Calcul de la nouvelle estimation d’état du système
  • Calcul de la covariance d’erreur de l’état du système
• L’estimation d’état calculée est le seul historique d’état conservé par le filtre de Kalman
• Grâce à cette propriété, le filtre de Kalman peut être implémenté même sur des équipements soumis à de fortes contraintes mémoire

En résumé

• Le filtre de Kalman est un processus générique d’estimation optimale d’état
• Il est utilisé dans de nombreuses applications où une estimation précise est nécessaire
• Décomposé en petites étapes, son fonctionnement devient moins intimidant et plus facile à comprendre

[GN⁺]

Commentaires Hacker News

• Quand on parle de filtre de Kalman, impossible de ne pas mentionner cet excellent support d’apprentissage. C’est un livre écrit sous forme d’un ensemble de notebooks Jupyter : https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
  Ce livre présente le filtre alpha-bêta comme une sorte de petit frère du véritable filtre de Kalman. Récemment, j’ai eu besoin de quelque chose de similaire au travail, et en lisant pas mal sur le sujet, j’ai fini par comprendre que les filtres alpha-bêta et la famille des filtres de Kalman se concentrent fortement sur la prédiction à court terme, alors que ce dont j’avais réellement besoin était le lissage de données passées.
  J’ai donc commencé à lire sur le lissage exponentiel double ; cela semblait parfaitement correspondre à mon cas d’usage, et plus je creusais, plus je me rendais compte qu’au final, c’était un filtre alpha-bêta avec seulement des noms de variables différents.
  J’ai l’impression que tout ce domaine des mathématiques repose sur quelques bases théoriques communes, mais que des disciplines différentes arrivent au même système par des approches différentes, avec des noms et des notations qui changent et masquent ce qu’elles ont en commun. Il doit y avoir un noyau d’intuitions relativement restreint au cœur de choses comme les séries entières, la constante naturelle, la descente de gradient, les filtres, les systèmes à rétroaction et la théorie générale des systèmes ; si on parvenait à le saisir, beaucoup de mathématiques se relieraient de façon élégante.

  • Les gens qui s’énervent contre les mathématiciens parce qu’ils utilisent des noms de variables à une seule lettre passent souvent à côté de l’essentiel. Les noms courts permettent de se concentrer sur la structure des équations et des relations, et facilitent la reconnaissance de motifs du type : « attends, ce n’est qu’un autre nom, mais la structure est la même que ce X que je connais ».
    Ce n’est pas pour économiser du papier ni pour écrire plus facilement. Taper en LaTeX, sur un clavier anglais, des lettres grecques avec exposants et indices n’est pas plus simple que d’écrire des mots. Il s’agit de transmettre au lecteur une information précise qu’il serait difficile de communiquer autrement.
    La notation mathématique ressemble à des lettres, mais dans le fond c’est une notation assez graphique, et les mots longs masquent ce dessin.
  • Ce que vous cherchez ressemble plutôt à la théorie des systèmes dynamiques linéaires ou non linéaires. Malheureusement, il n’existe pas un unique noyau d’intuition appuyé par une notation cohérente, mais plusieurs points de vue qui ne sont pas toujours cohérents entre eux.
    Si l’on suit correctement des cours de contrôle et de signaux/systèmes, cette intuition finit par devenir naturelle, et l’on apprend les maths et le vocabulaire sans s’accrocher à une convention de notation particulière. La vraie intuition, c’est que « tout est filtre » ; le reste consiste à analyser et synthétiser cette idée.
  • Le livre Probabilistic Robotics de Dieter Fox, Sebastian Thrun et Wolfram Burgard pourrait être utile. Il organise de nombreux sujets liés à Kalman dans une approche bayésienne avec une notation cohérente.
    Avec l’essor de l’IA/ML, des idées classiques de la théorie du contrôle sont aussi en train de fusionner avec l’apprentissage par renforcement.
  • Si Q et R sont constants, comme c’est généralement le cas, le gain converge vite, et le filtre de Kalman devient un filtre exponentiel avec une étape de prédiction. Pour beaucoup de gens, cette approche est beaucoup plus facile à comprendre, et correspond bien à la manière dont on l’utilise en pratique.
    En général, Q et R sont ajustés à la main « jusqu’à ce que ça ait l’air correct », puis on n’y touche plus. En plus, au lieu de régler plusieurs valeurs Q et R, il suffit d’ajuster un seul gain à la main.
  • J’ai eu une réflexion très similaire il y a quelque temps. L’astuce, c’est que beaucoup de filtres finissent par se ramener à de l’alpha/bêta, et que le filtre de Kalman peut être vu comme une manière de produire ces constantes lorsqu’on connaît bien le modèle linéaire et la variance du bruit de mesure.
    Si le bruit des mesures est toujours le même, il converge avec le temps vers une constante ; il devient surtout utile lorsque la précision des mesures est bien connue, mais varie beaucoup.

• J’ai récemment été chargé d’une implémentation de filtre de Kalman, et il a été vraiment difficile de trouver de bonnes ressources qui l’expliquent dans un langage compréhensible pour moi, en tant que développeur. Après environ un mois d’apprentissage, j’ai écrit deux articles, qui pourront peut-être aider quelqu’un : https://www.splinter.com.au/2023/12/14/the-kalman-filter-for..., https://www.splinter.com.au/2023/12/15/the-kalman-filter-wit...
  Du point de vue d’un développeur, le plus ironique, c’est que je n’ai compris les maths qu’après l’avoir implémenté moi-même. On dirait une façon d’apprendre en construisant par-dessus ce qu’on sait déjà ; je me demande s’il existe un terme pour ça.

• J’ai toujours pensé que les maths seraient beaucoup plus faciles à apprendre si elles utilisaient des noms de variables explicites. Au moins, dans un média interactif comme le Web, on pourrait mettre des infobulles. Quand j’étudie les maths, je passe 90 % du temps à chercher ce que signifient les symboles.
  Ici aussi, quand on dit que l’indice « indique l’ordre des mesures », je ne sais pas très bien de quel ordre il s’agit. Ça veut probablement dire l’index. Cela dit, ça fait longtemps que je n’ai pas touché à un filtre de Kalman.

  • Ce que les gens oublient souvent, c’est que la notation mathématique est conçue pour faciliter le suivi des manipulations algébriques. Elle n’est pas censée révéler son sens à elle seule ; ce sont surtout les physiciens qui pensent qu’une formule comme E=mc^2 devrait avoir du sens en soi.
    Plus les maths deviennent pures, plus la portée de la plupart des variables est courte. En général, une variable est définie juste avant d’être utilisée, et sa portée ne dépasse pas la preuve ou la dérivation en question.
    Cela dit, certains choix dans cet article sont tout simplement étranges. Par exemple, utiliser P à la fois comme variable et comme indice, ou employer P pour la matrice de covariance alors que la matrice de précision est l’inverse exact de la matrice de covariance.
  • C’est ce que je déteste le plus quand je lis des articles scientifiques. Les auteurs essaient de sonner abstraits et académiques, mais ne font que devenir frustrants de flou. Pour qu’une phrase ait du sens, il faut y mettre un sujet et un objet.
    C’est précisément ce genre d’ambiguïté qui est le plus agaçant dans les articles de recherche. Il faut absolument être clair. Il faut utiliser des descriptions absolues, pas des expressions relatives. Il ne faut pas dire « regardez à droite ». Je peux très bien regarder à gauche.
    Si on écrit « après avoir fait tourner le prisme, le cône de lumière... », il manque le sens de rotation. Vers la gauche ou vers la droite, horizontalement ou de haut en bas, rapidement ou lentement. Dans la tête de la personne qui écrit, tous ces éléments essentiels sont présents, mais le lecteur ne peut pas lire dans ses pensées.
  • Entièrement d’accord. Dans le même ordre d’idées, je me suis dit que le meilleur livre de maths qui n’a encore été écrit par personne serait un ouvrage qui organise bien la notation et le sens des variables, et qui sélectionne clairement des théorèmes de plusieurs domaines.
  • L’ordre dont il est question ici est l’indice temporel auquel correspond la valeur. Par exemple, x_3 est l’état au troisième pas de temps.
    L’indice « p » signifie sans doute prediction, c’est-à-dire prédiction. x_p au temps 3 est l’état attendu au temps 4. Mais quand le temps 4 arrive effectivement, on calcule x_4 en tenant compte de la nouvelle mesure.
    Pour être clair, ce x_4 est différent du x_p calculé au temps 3. Les prédictions sont toujours un peu fausses.
  • Je pense que les noms de variables sont déjà choisis pour être explicites. Personne ne les choisit délibérément pour les rendre plus opaques ou plus difficiles à suivre.
    Le problème, c’est que les débutants n’ont pas encore assimilé les concepts ni la notation standard de chaque domaine, et que la douleur d’aborder un nouveau sujet reste donc bien réelle.

• Le filtre de Kalman fait peut-être partie de ces cas particuliers où la version simplifiée des maths est tellement simplifiée qu’on ne voit presque plus à quoi ressemblait l’original.
  Ce qu’il fait réellement, c’est obtenir une mesure, simuler des états futurs possibles, puis combiner cette information avec la mesure suivante, et recommencer.
  Par exemple, on peut prendre plusieurs photos d’une balle de tennis, estimer sa position et sa vitesse à partir de la première photo, simuler l’endroit où elle va aller, puis comparer avec la photo suivante pour voir quelle estimation est la plus proche de la réalité. Une méthode plus ancienne serait de mesurer la hauteur du soleil pour tracer sur une carte une ligne de positions possibles, puis de la comparer avec l’endroit où l’on pensait se trouver au départ.
  Bien sûr, le calcul exact est pratiquement impossible en pratique. On simplifie donc par échantillonnage. Comme cela reste difficile, on suppose que la distribution est plus ou moins proche d’une distribution gaussienne. En simplifiant encore davantage, si l’on suppose que l’évolution du système est une transformation linéaire, on obtient le filtre de Kalman dont il est question ici.
  Je trouverais étonnant de pouvoir comprendre ce qui se passe réellement en ne regardant que l’algèbre linéaire.

  • Les explications du filtre de Kalman commencent étrangement souvent par « c’est très simple ! ». L’article original suit aussi ce format.
    Cette explication est la première qui m’ait vraiment donné une intuition de ce qui se passe. Pour quelqu’un comme moi qui vient de l’informatique, le nom lui-même est assez trompeur. Ce n’est pas un filtre au sens du traitement de flux ou de SQL.
  • On peut le dire encore plus simplement. L’algèbre linéaire est en fait plus facile.
    Le filtre de Kalman cherche à estimer l’entrée cachée qui a produit les mesures. Pour cela, il formule le problème consistant à minimiser, par rapport à x, [mesure_réelle - mesure_attendue(x)]^2/s^2, où s est le sigma du bruit.
    Cela vient du problème d’estimation d’état consistant à maximiser, par rapport à x, la vraisemblance d’observer la mesure_réelle. En effet, dans la fonction de vraisemblance, le seul terme important est -([x-expected(x)]/s)^2. Il suffit de regarder l’exposant d’une loi normale, ou en fait de pratiquement n’importe quelle loi exponentielle.
    Comme mesure_réelle est une constante, si la fonction mesure_attendue est linéaire, on résout directement le problème par optimisation convexe. En dérivant, en posant le résultat égal à 0 puis en résolvant, on obtient l’étape de mise à jour du filtre de Kalman.
    Si la fonction est non linéaire, on revient à effectuer une seule étape de Newton-Raphson : on linéarise les équations, on minimise, puis on renvoie la solution de cette « fausse linéarisation ». C’est du calcul différentiel et de l’algèbre linéaire de niveau licence, simplement personne ne le présente ainsi.
    Mais c’est aussi complètement faux. C’est un hack des années 1960 qui tente de maximiser la fonction de vraisemblance avec une linéarisation récursive en une seule étape. À cause d’une mauvaise lecture de la borne de Cramér-Rao, plusieurs générations d’ingénieurs ont cru que c’était optimal, alors qu’en réalité ça ne l’est pas.
    Aujourd’hui, on dispose d’au moins 10 000 fois plus de ressources de calcul, et on obtient de meilleures performances en formulant et en résolvant des équations non linéaires avec plusieurs étapes de Newton-Raphson, ou en conservant un long historique de mesures et en résolvant tout ce bloc avec plusieurs étapes de Newton-Raphson, ou encore en utilisant une représentation par mélange gaussien pour accepter des fonctions de mesure multimodales.
    Ces sujets sont bien couverts par la recherche sur l’estimation d’état des années 1980 à aujourd’hui, mais les manuels semblent encore gravés dans la pierre en 1972.
    La borne de Cramér-Rao n’est définie que lorsque toutes les fonctions de vraisemblance des mesures sont linéarisées autour de l’état vrai ; cela n’est possible qu’asymptotiquement dans un bloc qui conserve toutes les mesures, pas avant un temps infini, et pas non plus avec un filtre récursif.

• Parmi les anciennes explications, j’avais trouvé celle-ci bonne : https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture..., https://news.ycombinator.com/item?id=13449229

  • Cette explication était aussi bien parce qu’elle était simple : https://praveshkoirala.com/2023/06/13/a-non-mathematical-int..., https://news.ycombinator.com/item?id=36971975

• Si on a vraiment besoin d’un filtre de Kalman, je pense qu’on peut lire et comprendre cet article, la page Wikipédia, ou le code d’implémentation (https://github.com/LdDl/kalman-rs/blob/master/src/kalman/kal...)
  Mais d’après mon expérience, presque tout le monde, partout dans le monde, apprend le mieux par l’exemple : ce sont des apprenants visuels. C’est pourquoi je trouve étonnant que le tutoriel au milieu de la page ne mette pas de valeurs numériques d’exemple dans les formules. J’ai peut-être raté quelque chose, mais les schémas ne commencent qu’après une page de texte sur « qu’est-ce qu’un filtre de Kalman », et même ces schémas ne sont encore que davantage de formules

  • Ailleurs, il était dit que les conventions de nommage des variables sont un obstacle à l’apprentissage et à la compréhension des sujets mathématiques, et je suis aussi d’accord avec ce point de vue. Mais le problème présenté ici me parle encore plus
    C’est tellement fréquent que c’en est surprenant. Sous une forme moins marquée, on retrouve le même problème dans les bibliothèques logicielles qui n’incluent pas d’exemples de code

• Ce qui m’a parlé, c’est que lorsqu’on combine deux distributions de mesures incertaines, c’est-à-dire des distributions à forte variance, on obtient une mesure plus certaine, donc une distribution plus étroite
  Si l’on combine à nouveau cette mesure plus certaine avec la mesure suivante, puis qu’on répète l’opération, cela devient tout simplement un filtre de Kalman

• Parmi les séries de vidéos expliquant les KF, celle-ci était vraiment bonne. Je l’ai mieux comprise que les ressources de l’article original : https://www.youtube.com/watch?v=CaCcOwJPytQ

• Mon défunt père a utilisé ce filtre très souvent tout au long de sa carrière, dès l’époque où il venait d’être inventé. Il travaillait sur les radars et les systèmes de guidage de missiles

• Fermez les yeux et marchez un peu. Imaginez où vous vous trouvez, puis ouvrez les yeux : votre position réelle est-elle différente de celle que vous aviez imaginée ?
  Cette dernière étape — mettre à jour la croyance sur les variables d’état à partir d’une observation —, c’est ce que fait le filtre de Kalman