Filtro de Kalman explicado de forma simples

• O filtro de Kalman é um algoritmo usado em previsão e controle baseados em sensores, produzindo estimativas de estado mais precisas em tempo real a partir de medições ruidosas ou imprecisas
• Ele não apenas suaviza medições, mas também pode estimar variáveis de estado como posição e velocidade que são difíceis de observar diretamente
• O exemplo de rastreamento por radar mostra o fluxo de receber medições de posição 2D e a covariância como entrada para estimar a posição e a velocidade de um objeto em um vetor de estado 4×1
• Depois de inicializar o estado com as duas primeiras medições, o processo repete previsão, cálculo do ganho de Kalman (Kalman Gain) e atualização do estado e da covariância do erro
• Como o histórico mantido pelo filtro é apenas a estimativa de estado atual, ele é fácil de implementar até em equipamentos com restrições de memória

---

A visão geral do filtro de Kalman

• O filtro de Kalman pode ser visto como uma caixa-preta com entrada e saída
  • A entrada são medições com ruído ou às vezes imprecisas
  • A saída são estimativas com menos ruído e maior precisão
• As estimativas podem ser parâmetros de estado do sistema que não foram efetivamente medidos ou observados
• Ele é usado para estimar, em tempo real e com alta precisão, parâmetros observáveis e não observáveis
• Estimativas de alta precisão são usadas para previsões precisas e tomada de decisão
• Por isso, é muito usado em robótica e sistemas em tempo real que exigem informações confiáveis

O problema que o filtro de Kalman resolve

• A partir de medições imprecisas ou com ruído, ele estima com mais precisão o estado de uma variável ou de outras variáveis difíceis de observar diretamente
• Aplicações típicas incluem:
  • Rastreamento de objetos: usa a posição medida para estimar com mais precisão a posição e a velocidade de um objeto
  • Estimativa de peso em balanças digitais: estima o peso de um objeto a partir da pressão aplicada à superfície
  • Guiagem, navegação e controle: usa sensores IMU para estimar posição, velocidade e aceleração e aplicar isso ao controle do próximo movimento
• O ponto forte do filtro de Kalman não está apenas na suavização das medições, mas na capacidade de estimar parâmetros do sistema difíceis de medir
• Em sistemas em tempo real, estimativas mais precisas levam a melhor controle e funcionalidade

Entradas e saídas do exemplo de rastreamento por radar

• O exemplo trata de uma situação de rastreamento por radar de aviões e objetos ao redor de um aeroporto
• O estado de trilha gerado é usado para ser exibido a operadores de controle de tráfego aéreo que monitoram o espaço aéreo
• O radar gera medições de posição x e y em um sistema de coordenadas cartesianas 2D
  • As medições são representadas pelo vetor coluna 2×1 z
  • A matriz de variância-covariância das medições é representada por R
  • A marca temporal da medição é representada por t
  • O subscrito m indica o parâmetro de medição, e k indica a ordem da medição
• Com base nas medições do radar, o filtro de Kalman estima a posição e a velocidade do objeto
  • A estimativa é representada pelo vetor coluna 4×1 x
  • A matriz de variância-covariância da estimativa é representada pela matriz 4×4 P
  • A marca temporal da estimativa de estado é indicada por T

Etapa 1: inicialização do estado do sistema

• O método de inicialização do filtro de Kalman varia conforme a aplicação
• Neste exemplo de rastreamento por radar, o estado do sistema é inicializado com a primeira medição
• As medições de entrada contêm apenas informações de posição, mas o estado do sistema de saída contém posição e velocidade do objeto
• Quando a primeira medição chega, a única informação conhecida é a posição naquele instante
  • Após a primeira estimativa, o estado estimado do sistema é definido como a posição de entrada
  • A covariância do erro do estado do sistema é definida conforme a precisão de posição da primeira medição

Etapa 2: reinicialização do estado do sistema

• Como a estimativa de velocidade exige uma segunda medição de posição, a estimativa de estado do sistema é reinicializada
• A velocidade é calculada por aproximação linear
  • A velocidade é calculada como distância percorrida / tempo gasto no deslocamento
• A estimativa atualizada do estado do sistema passa a ser composta pela posição da segunda medição e pela velocidade calculada
• A covariância atualizada do erro do estado do sistema inclui a precisão de posição da segunda medição e a precisão aproximada da velocidade
• O valor aproximado da precisão da velocidade pode ser ajustado por tuning depois de passar dados pelo filtro
  • No exemplo, o termo de variância da velocidade é definido como 10⁴
  • Esse valor representa uma grande incerteza sobre o valor de estado da velocidade
  • A unidade de velocidade no exemplo é m/s

Processamento iterativo após a inicialização

• As duas primeiras etapas servem para inicializar e reinicializar a estimativa do sistema com algumas medições
• O método de inicialização pode variar de uma aplicação para outra
• O objetivo é obter uma estimativa de estado do sistema que permita atualizar as medições seguintes com as equações do filtro de Kalman
• Nas etapas seguintes, novas medições são incorporadas ao filtro e a estimativa de estado é atualizada

Etapa 3: previsão da estimativa de estado do sistema

• Quando a terceira medição chega, a estimativa de estado do sistema é propagada para frente no tempo para ficar alinhada no tempo com a medição
• Esse alinhamento é necessário para combinar a medição com a estimativa de estado
• A previsão usa um modelo do sistema
• No exemplo, um modelo linear de movimento com velocidade constante aproxima a mudança de posição do objeto ao longo do intervalo de tempo
  • O modelo de velocidade constante assume aceleração igual a 0
• A matriz de transição de estado representa essa equação de movimento
  • Essa matriz é usada para propagar adequadamente a estimativa de estado e a matriz de covariância do erro do estado
• Ao propagar a estimativa de estado para um instante futuro, surge incerteza sobre esse estado, então a covariância do erro aumenta

Matrizes Q e H

• A matriz Q representa o ruído de processo do modelo do sistema
  • O modelo do sistema é uma aproximação
  • A precisão do modelo varia ao longo da vida do estado do sistema
  • A matriz Q representa essa incerteza e é somada ao ruído de estado existente
  • No exemplo, acelerações e desacelerações reais contribuem para esse erro
• A matriz H é a matriz estado-medição, que converte a estimativa de estado do sistema do espaço de estados para o espaço de medição
  • Em algumas aplicações, ela é composta por 0 e 1
  • Em aplicações que usam Extended Kalman Filter, ela é preenchida com equações diferenciais
  • A explicação relacionada continua no texto Extended Kalman Filters
• Neste exemplo, a matriz H é uma matriz simples que reduz a estimativa de estado e a covariância do erro para permitir comparação apenas com os valores de posição, e não com posição e velocidade completas

Etapa 4: cálculo do ganho de Kalman

• O filtro de Kalman calcula o ganho de Kalman a cada nova medição
• O ganho de Kalman determina quanto a medição de entrada influenciará a estimativa de estado do sistema
• Se o ruído da medição for muito alto, o ganho de Kalman tenderá a confiar mais na estimativa de estado atual do que na informação nova, porém imprecisa
• O núcleo do algoritmo do filtro de Kalman está em ponderar adequadamente a estimativa atual e a nova informação da medição para produzir uma estimativa ótima

Etapa 5: atualização do estado e da covariância do erro

• O filtro de Kalman usa o ganho de Kalman para estimar o estado do sistema e a matriz de covariância do erro no instante da medição de entrada
• O ganho de Kalman é usado para dar o peso adequado à medição em dois cálculos
  • cálculo da nova estimativa de estado do sistema
  • cálculo da covariância do erro do estado do sistema
• A estimativa de estado calculada é o único histórico de estado mantido pelo filtro de Kalman
• Por causa dessa característica, o filtro de Kalman pode ser implementado mesmo em equipamentos com baixa disponibilidade de memória

Resumo

• O filtro de Kalman é um processo de uso geral para estimativa ótima de estado
• Ele é usado em diversas aplicações que exigem estimativas precisas
• Quando dividido em pequenas etapas, o funcionamento do filtro de Kalman pode ser entendido de forma menos intimidadora e mais fácil

[GN⁺]

Opiniões do Hacker News

• Em uma conversa sobre filtro de Kalman, não pode faltar o link para este excelente material de aprendizado. É um livro escrito como uma coleção de notebooks Jupyter: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
  Esse livro trata o filtro alfa-beta mais ou menos como um irmão mais novo do filtro de Kalman completo. Recentemente precisei de algo parecido no trabalho e, depois de ler bastante, percebi que o filtro alfa-beta e a família Kalman são muito focados em previsões de futuro próximo, enquanto o que eu realmente precisava era suavização de dados passados.
  Então comecei a ler sobre suavização exponencial dupla, que parecia se encaixar perfeitamente no caso de uso, e quanto mais eu me aprofundava, mais percebia que, no fim, era um filtro alfa-beta com nomes de variáveis diferentes.
  Tenho a impressão de que toda essa área da matemática se apoia em algumas teorias fundamentais em comum, mas campos diferentes chegam ao mesmo sistema por abordagens diferentes, e nomes e notações distintos acabam escondendo essa semelhança. Parece que há um núcleo relativamente pequeno de intuições no centro de coisas como séries de potências, constante natural, descida do gradiente, filtros, sistemas de realimentação e teoria geral de sistemas; se você pegar esse núcleo, muita matemática deve se conectar de forma elegante.

  • Muitas vezes, quem fica irritado com matemáticos usando nomes de variáveis de uma letra só não entende o ponto principal. Nomes curtos ajudam a focar na estrutura das equações e das relações, e facilitam reconhecer padrões do tipo “espera, isso tem a mesma estrutura de um X que eu conheço, só com outro nome”.
    Não é para economizar papel nem para facilitar a escrita. Em um teclado em inglês, escrever letras gregas com sobrescritos e subscritos em LaTeX não é mais fácil do que escrever palavras. A intenção é transmitir ao leitor uma informação específica que seria difícil de comunicar de outra forma.
    A notação matemática parece texto, mas, na essência, é uma notação bastante visual; palavras longas acabam encobrindo esse desenho.
  • O que você está procurando está mais próximo da teoria de sistemas dinâmicos lineares ou não lineares. Infelizmente, não há um único núcleo intuitivo apoiado por uma notação consistente, e sim várias perspectivas que não são consistentes entre si.
    Se você fizer bons cursos de controle e de sinais/sistemas, essa intuição acaba ficando incorporada, e você aprende a matemática e a terminologia sem se prender a uma convenção específica de notação. A intuição real é que “tudo é um filtro”, e o resto é analisar e sintetizar essa ideia.
  • Talvez valha a pena ver Probabilistic Robotics, de Dieter Fox, Sebastian Thrun e Wolfram Burgard. É um livro que organiza vários temas relacionados a Kalman de maneira bayesiana, com uma notação consistente.
    Com o crescimento de AI/ML, ideias da teoria clássica de controle também estão se combinando com aprendizado por reforço.
  • Se Q e R forem constantes, como normalmente são, o ganho converge rapidamente, e o filtro de Kalman vira um filtro exponencial com uma etapa de previsão acoplada. Para muita gente, esse lado é muito mais fácil de entender e também combina bem com a forma como ele é usado na prática.
    Isso porque, em geral, Q e R são ajustados manualmente “até ficar bom” e depois não são mais alterados. Além disso, em vez de ajustar manualmente vários valores Q e R, basta acertar um único ganho.
  • Já tive uma ideia muito parecida antes. O macete é que muitos filtros acabam se reduzindo a alfa/beta, e dá para ver o filtro de Kalman como uma forma de produzir essas constantes quando você conhece bem o modelo linear e a variância do ruído de medição.
    Se o ruído das medições for sempre o mesmo, ele converge para constantes com o tempo; ele se torna especialmente útil quando você consegue estimar bem a precisão das medições, mas ela varia bastante.

• Recentemente fiquei responsável por uma implementação de filtro de Kalman, e foi realmente difícil encontrar bons materiais que explicassem o assunto em uma linguagem que eu, como desenvolvedor, conseguisse entender. Depois de cerca de um mês aprendendo, escrevi dois artigos, que talvez sejam úteis para alguém: https://www.splinter.com.au/2023/12/14/the-kalman-filter-for..., https://www.splinter.com.au/2023/12/15/the-kalman-filter-wit...
  Do ponto de vista de um desenvolvedor, ironicamente, só depois de implementar eu mesmo é que entendi a matemática. Parece um jeito de aprender construindo em cima do que você já sabe; fico curioso se existe algum termo para isso.

• Sempre achei que matemática seria muito mais fácil de aprender se usasse nomes de variáveis descritivos. Pelo menos em uma mídia interativa como a web, daria para incluir no mínimo tooltips. Quando estudo matemática, passo 90% do tempo procurando o significado dos símbolos.
  Além disso, aqui fico confuso quando dizem que o subscrito “indica a ordem das medições”: que ordem é essa? Provavelmente querem dizer índice. Faz tempo que não mexo com filtros de Kalman

  • O que as pessoas esquecem com frequência é que a notação matemática foi projetada para facilitar o acompanhamento de manipulações algébricas. Ela não foi pensada para que o significado fique evidente só pela notação em si; quem tende a achar que uma equação como E=mc^2 precisa ter significado por si só são principalmente os físicos.
    Quanto mais pura a matemática, mais curto costuma ser o escopo da maioria das variáveis. Em geral, uma variável é definida logo antes de ser usada, e seu escopo não passa daquela prova ou derivação.
    Dito isso, algumas escolhas deste texto são simplesmente estranhas. Por exemplo, usar P ao mesmo tempo como variável e índice, e usar P para a matriz de covariância embora a matriz de precisão seja exatamente a inversa da matriz de covariância
  • Isso é o que mais odeio ao ler artigos acadêmicos. Os autores tentam soar abstratos e acadêmicos, mas só acabam ficando frustrantemente ambíguos. Para uma frase fazer sentido, é preciso incluir o sujeito e o objeto.
    A parte mais irritante de artigos de pesquisa é justamente essa ambiguidade. É obrigatório ser claro. É preciso usar descrições absolutas, não expressões relativas. Não se deve dizer “veja à direita”. Eu posso estar olhando para a esquerda.
    Se você escreve “depois de girar o prisma, o cone de luz...”, falta dizer em que direção foi a rotação. Para a esquerda ou para a direita, na horizontal ou para cima/baixo, rápida ou lenta. Na cabeça de quem escreve, todos esses elementos essenciais estão desenhados, mas o leitor não consegue ler a mente dele
  • Concordo totalmente. Algo parecido que já senti é que o melhor livro de matemática ainda não escrito seria um que organizasse bem a notação e o significado das variáveis e fizesse uma curadoria clara de teoremas de várias áreas
  • A ordem mencionada aqui é o índice temporal ao qual os valores correspondem. Por exemplo, x_3 é o estado no terceiro passo de tempo.
    O subscrito “p” provavelmente significa prediction, ou seja, previsão. O x_p no tempo 3 é o estado esperado no tempo 4. Mas, quando o tempo 4 de fato chega, calcula-se x_4 incorporando a nova medição.
    Para ser claro, esse x_4 é diferente do x_p calculado no tempo 3. Isso porque as previsões estão sempre um pouco erradas
  • Acho que os nomes das variáveis já foram escolhidos para ser descritivos. Ninguém escolhe de propósito nomes mais opacos ou difíceis de acompanhar.
    O problema é que quem está começando ainda não aprendeu os conceitos nem a notação padrão de cada área do problema, e por isso permanece a dor de entrar em um assunto novo

• O filtro de Kalman talvez seja um daqueles casos peculiares em que a versão simplificada da matemática fica tão simplificada que quase não dá para ver a forma original.
  O que ele faz de fato é obter uma medição, simular estados futuros possíveis, combinar essa informação com a próxima medição e repetir.
  Por exemplo, é como tirar várias fotos de uma bola de tênis, estimar a posição e a velocidade a partir da primeira foto, simular para onde ela vai, comparar com a foto seguinte e ver qual estimativa está mais próxima da verdade. Pensando em um método mais antigo, dá para imaginar medir a altitude do Sol para criar no mapa uma linha de posições possíveis e compará-la com o ponto onde você achava que estava.
  Claro que o cálculo exato é quase impossível na prática. Por isso, simplificamos usando amostragem. Como isso ainda é difícil, assume-se que a distribuição é, em certa medida, próxima de uma distribuição gaussiana. Se simplificarmos ainda mais assumindo que a mudança do sistema é uma transformação linear, chegamos ao filtro de Kalman tratado aqui.
  Seria impressionante conseguir entender o que realmente está acontecendo só olhando para a álgebra linear

  • Curiosamente, explicações sobre o filtro de Kalman muitas vezes começam com “é muito simples!”. O texto original também segue esse formato.
    Esta explicação foi a primeira que realmente me deu uma intuição do que está acontecendo. Para mim, que venho da computação, o próprio nome é bem enganoso. Não é um filtro no sentido de processamento de streams ou SQL
  • Dá para dizer de forma ainda mais simples. A álgebra linear é até mais fácil.
    O filtro de Kalman tenta estimar a entrada oculta que gerou as medições. Para isso, ele formula o problema de minimizar, em relação a x, [medição_real - medição_esperada(x)]^2/s^2. Aqui, s é o sigma do ruído.
    Isso vem de um problema de estimação de estado que busca maximizar, em relação a x, a verossimilhança de observar a medição_real. Isso porque, na função de verossimilhança, o único termo importante é -([x-expected(x)]/s)^2. Basta olhar para o expoente da distribuição normal, ou de praticamente qualquer distribuição exponencial.
    Como a medição_real é uma constante, se a função medição_esperada for linear, o problema é resolvido diretamente por otimização convexa. Ao derivar, igualar a zero e resolver, sai a etapa de atualização do filtro de Kalman.
    Se a função for não linear, é como realizar uma etapa de Newton-Raphson: linearizar a equação, minimizá-la e devolver a solução dessa “linearização falsa”. É cálculo e álgebra linear de graduação; só que ninguém explica dessa forma.
    Mas isso também está completamente errado. É um hack dos anos 1960 para tentar maximizar a função de verossimilhança com essa linearização recursiva de etapa única. Por uma leitura incorreta do limite de Cramér-Rao, várias gerações de engenheiros acreditaram que isso era ótimo, mas na prática não é.
    Hoje temos pelo menos 10.000 vezes mais recursos computacionais, e é possível obter desempenho melhor formulando e resolvendo equações não lineares com várias etapas de Newton-Raphson, mantendo um histórico longo de medições e resolvendo todo esse conjunto com várias etapas de Newton-Raphson, ou usando uma representação por mistura gaussiana para aceitar funções de medição multimodais.
    Essas coisas foram bem tratadas nas pesquisas sobre estimação de estado dos anos 1980 até hoje, mas os livros-texto ainda parecem ter sido gravados em pedra em 1972.
    O limite de Cramér-Rao só é definido quando todas as funções de verossimilhança das medições são linearizadas no estado verdadeiro; isso só é possível assintoticamente em um conjunto que preserva todas as medições, não antes de um tempo infinito, e também não com um filtro recursivo

• Entre as explicações antigas, achei este texto bom: https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture..., https://news.ycombinator.com/item?id=13449229

  • Esta explicação também era boa por ser simples: https://praveshkoirala.com/2023/06/13/a-non-mathematical-int..., https://news.ycombinator.com/item?id=36971975

• Se você realmente precisa de um filtro de Kalman, acho que dá para ler e entender este texto, o artigo da Wikipedia ou o código de implementação (https://github.com/LdDl/kalman-rs/blob/master/src/kalman/kal...)
  Mas, pela minha experiência, quase todo mundo no mundo aprende melhor com exemplos e é um aprendiz visual. Por isso me surpreende que o tutorial no meio da página não coloque números de exemplo nas fórmulas. Posso ter deixado passar, mas as figuras também só começam depois de uma página de texto sobre “o que é um filtro de Kalman”, e mesmo essas figuras são mais fórmulas

  • Em outro lugar, disseram que as convenções de nomes de variáveis são um obstáculo para aprender e entender tópicos de matemática, e concordo com esse ponto de vista. Mas me identifico ainda mais com o problema mostrado aqui
    Isso acontece com tanta frequência que chega a surpreender. Em uma forma mais branda, o mesmo problema aparece em bibliotecas de software que não incluem exemplos de código

• O que fez sentido para mim foi que, ao combinar duas distribuições de medições incertas, ou seja, distribuições com grande variância, você obtém uma medição mais certa, isto é, uma distribuição mais estreita
  Se combinar essa medição mais certa com a próxima medição e repetir o processo, isso vira exatamente um filtro de Kalman

• Entre os conjuntos de vídeos que explicam KF, este foi muito bom. Entendi melhor do que com o material do post original: https://www.youtube.com/watch?v=CaCcOwJPytQ

• Meu falecido pai usou esse filtro com frequência ao longo de toda a carreira, desde a época em que ele estava acabando de ser inventado. Ele trabalhava com sistemas de radar e orientação de mísseis

• Feche os olhos e tente andar um pouco. Depois de imaginar onde você está, abra os olhos: sua posição real é diferente da que você imaginou?
  Essa última etapa, ou seja, atualizar a crença sobre as variáveis de estado usando observações, é o que o filtro de Kalman faz