Filtro de Kalman
Em estatística, o filtro de Kalman é um método matemático criado por Rudolf Kalman. Seu propósito é utilizar medições de grandezas realizadas ao longo do tempo (contaminadas com ruído e outras incertezas) e gerar resultados que tendam a se aproximar dos valores reais das grandezas medidas e valores associados. O filtro de Kalman apresenta diversas aplicações e é uma parte essencial do desenvolvimento de tecnologias espaciais e militares. Talvez o tipo mais usado e simples do filtro de Kalman seja em phase-locked loop (malhas de captura de fase), bastante comuns em rádios FM e na maioria dos equipamentos de telecomunicações existentes. Extensões e generalizações do método também foram desenvolvidas.
O filtro de Kalman produz estimativas dos valores reais de grandezas medidas e valores associados predizendo um valor, estimando a incerteza do valor predito e calculando uma média ponderada entre o valor predito e o valor medido. O peso maior é dado ao valor de menor incerteza. As estimativas geradas pelo método tendem a estar mais próximas dos valores reais que as medidas originais pois a média ponderada apresenta uma melhor estimativa de incerteza que ambos os valores utilizados no seu cálculo.
Do ponto de vista teórico, o filtro de Kalman é um algoritmo para realizar, de forma eficiente, inferências exatas sobre um sistema dinâmico linear, que é um modelo Bayesiano semelhante a um Modelo oculto de Markov, mas onde o espaço de estados das variáveis não observadas é contínuo e todas as variáveis, observadas e não observadas, apresentam distribuição normal (ou, frequentemente, distribuição normal multivariada).
Histórico
[editar | editar código-fonte]O filtro é nomeado em homenagem a Rudolf Kalman, embora Thorvald Nicolai Thiele[1][2] e Peter Swerling tenham desenvolvido um algoritmo similar antes.
Stanley F. Schmidt é geralmente citado como tendo desenvolvido a primeira implementação do filtro de Kalman. Richard S. Bucy contribuiu com a teoria, levando à denominação ocasional do filtro de Kalman-Bucy. Durante uma visita de Kalman ao NASA Ames Research Center ele viu a aplicação de suas idéias no problema de estimação de trajetórias para o Projeto Apollo, levando à incorporação do filtro no computador de navegação do projeto Apollo. O filtro de Kalman foi primeiramente descrito e desenvolvido parcialmente nos artigos acadêmicos de Swerling (1958), Kalman (1960) e Kalman e Bucy (1961).
Os filtros de Kalman tem sido vitais na implementação de sistemas de navegação de submarinos e nos sistemas de guiamento e navegação de mísseis de cruzeiro como o Tomahawk da marinha americana, e o AGM-86 ALCM da força aérea americana. O filtro de Kalman também é utilizado no guiamento e navegação dos Ônibus Espacias da NASA e no controle de atitude da Estação Espacial Internacional.
Esse filtro digital é ocasionalmente chamado de filtro de Stratonovich–Kalman–Bucy por ser um caso particular de um filtro mais geral e não-linear desenvolvido pouco antes pelo matemático russo Ruslan Stratonovich.[3][4] De fato, algumas equações de casos especiais lineares apareceram nos artigos de Stratonovich que foram publicados antes do verão de 1960, quando Kalman se encontrou com Stratonovich durante uma conferência em Moscow.
Descrição técnica
[editar | editar código-fonte]O filtro de Kalman é um eficiente filtro recursivo que estima o estado de um sistema dinâmico linear a partir de uma série de medições ruidosas. O filtro é utilizado em uma grande variedade de aplicações em engenharia e econometria, desde radar e visão computacional até modelos macroeconômicos[5][6] e é um tópico importante na teoria de sistemas de controle. O filtro de Kalman é utilizado, em conjunto com o regulador quadrático linear (linear quadratic regulator - LQR), para resolver o problema de controle gaussiano quadrático linear (linear-quadratic-Gaussian control - LQG). O filtro de Kalman, o regulador quadrático linear e o controlador gaussiano quadrático linear são soluções para os problemas mais fundamentais da teoria de controle.
Na maioria das aplicações, o estado completo do sistema é muito maior (apresenta mais graus de liberdade) que os poucos parâmetros passíveis de serem medidos. Porém, ao combinar uma série de medições, o filtro de Kalman é capaz de estimar o estado completo. Uma grande variedade de filtros de Kalman foi desenvolvida, desde a forma original de Kalman, o filtro de Kalman-Bucy, o filtro estendido de Schmidt, o filtro de informação (information filter) e uma variedade de filtros baseados em raízes quadradas desenvolvidos por Bierman, Thornton e muitos outros. Talvez o tipo mais usado e simples do filtro de Kalman seja em phase-locked loop (malhas de captura de fase), bastante comuns em rádios FM e na maioria dos equipamentos de telecomunicações existentes.
Equacionamento
[editar | editar código-fonte]Visão geral
[editar | editar código-fonte]O filtro de Kalman utiliza um modelo dinâmico de um sistema (as equações do movimento, por exemplo), entradas de controle conhecidas e medições (como as de sensores) para gerar uma estimativa das grandezas variáveis do sistema (seus estados). A estimativa obtida desta forma é melhor que a estimativa obtida utilizando-se qualquer uma das medidas unicamente. Assim, é um algoritmo usual para fusão de sensores.
Todas as medições e cálculos baseados em modelos são, de certo modo, estimativas. Sinais ruidosos de sensores, aproximações nas equações que descrevem o comportamento do sistema e fatores externos não considerados introduzem incerteza sobre os valores inferidos para o estado de um sistema. O filtro de Kalman combina uma predição do estado de um sistema com uma nova medida usando uma média ponderada. A idéia dos pesos é que valores com menor incerteza estimada sejam mais "confiados". Os pesos são calculados através da covariância, uma medida da incerteza estimada da predição do estado do sistema. O resultado da média ponderada é uma nova estimativa do estado, que se localiza entre o estado predito e o estado medido, apresentando uma melhor incerteza estimada que qualquer um dos dois unicamente. Este processo é repetido a cada passo de tempo, com a nova estimativa e sua covariância gerando a predição usada na próxima iteração. Isto significa que o filtro de Kalman funciona recursivamente e requer apenas a última estimativa - não o histórico completo - do estado de um sistema para calcular o próximo estado.
Quando executando os cálculos para o filtro (como explicado abaixo), a estimativa do estado e as covariâncias são representadas por matrizes, para tratar as múltiplas dimensões envolvidas num único passo do cálculo. Desta forma, é possível representar as relações lineares entre diferentes variáveis de estado (como posição, velocidade e aceleração) em qualquer um dos modelos de transição ou covariâncias.
Modelo de sistema dinâmico considerado
[editar | editar código-fonte]Os filtros de Kalman são baseados em sistemas dinâmicos lineares discretizados no domínio do tempo. Eles são modelados em uma cadeia de Markov sobre operadores lineares perturbados por distribuições normais. O estado do sistema é representado como um vetor de números reais. A cada passo de tempo, um operador linear é aplicado ao estado para gerar o próximo estado, com adição de ruído e, opcionalmente, alguma informação sobre as entradas de controle, caso sejam conhecidas. Depois, outro operador linear com mais adição de ruído gera as observações do estado real. O filtro de Kalman pode ser visto como análogo ao modelo oculto de Markov, com a diferença principal que as variáveis ocultas pertencem a um espaço contínuo (ao contrário do espaço de estados discreto do modelo oculto de Markov. Além disso, o modelo oculto de Markov pode representar uma distribuição arbitrária para o próximo valor das variáveis de estado, ao contrário do modelo de ruído Gaussiano utilizado para o filtro de Kalman. Há uma significativa dualidade entre as equações do filtro de Kalman e do modelo oculto de Markov, como mostrado por Roweis and Ghahramani (1999).[7]
De modo a utilizar o filtro de Kalman para estimar o estado completo de um processo dada apenas uma sequência de observações ruidosas, é necessário modelar o processo de acordo com o framework do filtro de Kalman. Isto significa especificar as seguintes matrizes: Fk, o modelo de transição de estados; Hk, o modelo de observação; Qk, a covariância do ruído do processo; Rk, a covariância do ruído da observação; e, ocasionalmente, Bk, o modelo das entradas de controle, para cada passo de tempo k, como descrito abaixo.
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Kalman_filter_model.png/250px-Kalman_filter_model.png)
O modelo para o filtro de Kalman assume que o estado real no tempo k é obtido através do estado no tempo (k − 1) de acordo com
onde
- Fk é o modelo de transição de estados, aplicado no estado anterior xk−1;
- Bk é o modelo das entradas de controle, aplicado no vetor de entradas de controle uk;
- wk é o ruído do processo, assumido como sendo amostrado de uma distribuição normal multivariada de média zero e covariância Qk.
No tempo k, uma observação (ou medição) zk do estado real xk é feita de acordo com
onde Hk é o modelo de observação, que mapeia o espaço de estados real no espaço de estados observado, e vk é o ruído da observação, assumido como sendo um ruído branco gaussiano de média zero e covariância Rk.
O estado inicial e os vetores de ruído a cada passo {x0, w1, ..., wk, v1 ... vk} são assumidos como sendo mutuamente independentes.
Muitos sistemas dinâmicos reais não se encaixam perfeitamente neste modelo. De fato, efeitos dinâmicos não modelados podem degradar significativamente o desempenho do filtro, mesmo levando em conta que o filtro deve funcionar com sinais estocásticos desconhecidos como entrada. O motivo deste fato é que os efeitos dinâmicos não modelados dependem das entradas e, desta forma, podem levar o algoritmo de estimação à instabilidade (divergência). Por outro lado, sinais de ruído branco independentes não farão o algoritmo divergir. O problema de separação entre ruído na medição e efeitos dinâmicos não modelados é difícil, sendo tratado na teoria de controle na área de controle robusto.
Equações
[editar | editar código-fonte]O filtro de Kalman é um estimador recursivo. Isto significa que apenas a estimativa do estado no passo anterior e a medição atual são necessários para computar a estimativa do estado atual. Ao contrário de outras técnicas de estimação, nem o histórico de observações, nem o histórico das estimativas são necessários. No restante do texto, a notação representa a estimativa de no tempo n, dadas as observações até o tempo m, inclusive.
O estado do filtro é representado por duas variáveis:
- , a estimativa a posteriori do estado no tempo k, dadas as observações até o tempo k, inclusive;
- , a matriz de covariância do erro a posteriori (uma medida da acurácia estimada da estimativa do estado).
O filtro de Kalman pode ser escrito como uma única equação, porém ele é mais comumente descrito em duas fases distintas: Predição e Atualização. A fase de predição usa a estimativa do estado no passo anterior para obter uma estimativa do estado no tempo atual. Esta predição é chamada de estimativa a priori, pois não inclui a informação vinda da observação do estado atual. Na fase de atualização, a predição a priori é combinada com a observação atual para refinar a estimativa do estado. A estimativa refinada é chamada de estimativa a posteriori.
Tipicamente, as duas fases se alternam, com a predição prevendo o estado até o instante da próxima observação e a atualização incorporando a informação da observação. Porém, isto não é necessário; se alguma observação estiver indisponível, a fase de atualização pode ser pulada a múltiplos passos de predição realizadas. Da mesma forma, se múltiplas observações independentes estiverem disponíveis ao mesmo tempo, múltiplos passos de atualização podem ser realizados (normalmente com diferentes matrizes de observação Hk)
Predição
[editar | editar código-fonte]Predição do estado (estimativa a priori) |
|
Predição da covariância (estimativa a priori) |
|
Atualização
[editar | editar código-fonte]Resíduo da medição |
|
Resíduo da covariância | |
Ganho ótimo de Kalman | |
Estado atualizado (estimativa a posteriori) | |
Covariância estimada (estimativa a posteriori) |
As fórmulas acima para a estimativa e covariância atualizadas só são válidas para o ganho ótimo de Kalman. O uso de outros valores de ganho requer uma fórmula mais complicada encontrada na seção de derivações.
Invariantes
[editar | editar código-fonte]Se o modelo for correto e os valores de e refletirem perfeitamente a distribuição das condições iniciais, as seguintes invariantes são preservadas:
onde é o valor esperado de e as matrizes de covariância refletem perfeitamente a covariância das estimativas.
Derivações
[editar | editar código-fonte]Estimativa a posteriori da matriz de covariância
[editar | editar código-fonte]Começando com a invariante da covariância do erro Pk|k
substituindo a definição de
e substituindo
e
evidenciando o vetor erro, temos
como o erro de medição vk não tem correlação com os outros termos, temos
o que, pelas propriedades da covariância, se torna
o que, usando a invariante Pk|k-1 e a definição de Rk se torna
Esta fórmula é válida para qualquer valor de Kk. Quando Kk é o ganho ótimo de Kalman, a fórmula pode ser simplificada como é mostrado abaixo.
Ganho de Kalman
[editar | editar código-fonte]O filtro de Kalman é um estimador de mínimo erro quadrático. O erro na estimativa 'a posteriori' do estado é
A idéia é minimizar o valor esperado do quadrado do módulo deste vetor, . Isto é equivalente a minimizar o traço da estimativa a posteriori da matriz de covariância . Expandindo os termos da equação de e reescrevendo, temos:
O traço é minimizado quando a seguinte derivada matricial é zero:
Resolvendo a derivada para Kk nos dá o ganho de Kalman:
Este ganho, conhecido como o 'ganho ótimo de Kalman', é o que gera as estimativas de mínimo erro quadrático.
Simplificação da estimativa a posteriori da covariância
[editar | editar código-fonte]A fórmula usada para estimar a covariância do erro a posteriori pode ser simplificada quando o ganho de Kalman assume o valor ótimo demonstrado acima. Multiplicando, pela direita, os dois lados da equação para o ganho de Kalman por S'kKkT, temos que
Relembrando a equação expandida para a estimativa a posteriori da covariância do erro
percebe-se que os últimos dois termos se cancelam, gerando
Esta fórmula é computacionalmente menos custosa e quase sempre utilizada na prática, mas só é válida para o ganho ótimo. Se a precisão matemática for muito baixa causando problemas de estabilidade numérica, ou se um ganho não-ótimo for utilizado, esta simplificação não se aplica. A equação completa para a estimativa a posteriorida covariância do erro como derivada anteriormente deve ser utilizada.
Aplicações
[editar | editar código-fonte]O filtro de Kalman é utilizado em fusão de sensores e fusão de dados. Tipicamente, sistemas de tempo real realizam múltiplas medições sequenciais ao invés de uma única medição para obter o estado do sistema. Essas múltiplas medições são combinadas matematicamente para gerar o estado no sistema naquele instante.
Como um exemplo de aplicação, consideremos o problema de determinar a localização precisa de um carro. O carro pode estar equipado com um receptor GPS que provê uma estimativa de posição com precisão de alguns metros. A estimativa do GPS é comumente ruidosa; as medições apresentam saltos rápidos, porém sempre dentro de alguns metros da posição real. A posição também pode ser estimada integrando-se sua velocidade e direção ao longo do tempo, conhecendo-se as posições do acelerador e do volante. Esta técnica é conhecida como dead reckoning. Tipicamente, esta técnica gera uma estimativa suave da posição do carro, mas irá se afastar do valor real com o tempo, devido ao acúmulo de pequenos erros. Também sabe-se que o carro deve seguir as leis da física, com sua posição variando proporcionalmente à sua velocidade.
Neste exemplo, podemos pensar no filtro de Kalman operando em suas duas fases distintas: predição e atualização. Na fase de predição, a posição anterior do carro é modificada através das equações do movimento (que é o modelo de transição de estados) levando em conta as posições do acelerador e do volante (modelo das entradas de controle). As predições para a posição e a covariância dos erros são obtidas nesta fase. A covariância deve ser proporcional à velocidade do carro, pois haverá mais incerteza na estimativa dead reckoning em maiores velocidades. Depois, na fase de atualização, a medição da posição do carro é obtida do GPS. Esta medida também contém incertezas, e sua covariância em relação à covariância predita na fase anterior determinará o peso com que essa medição irá afetar a estimativa atualizada de posição. Idealmente, a estimativa por dead reckoning deve se afastar da posição real ao longo do tempo, mas sua combinação com a medição do GPS deve trazer a estimativa mais perto do valor real, sem se tornar ruidosa e com saltos bruscos a cada medição.
Visão computacional
[editar | editar código-fonte]Fusão de dados utilizando filtro de Kalman pode ajudar computadores a seguir objetos em vídeos com baixa latência. O problema de seguir objetos é dinâmico, utilizando dados de sensores e imagens de câmeras que sempre estão contaminados com ruído. Desta forma normalmente é desejável utilizar algum método para redução de ruído.
O esquema iterativo de predição-atualização do filtro de Kalman pode ser útil, pois a cada passo de tempo apenas uma informação sobre a variável de estado deve ser considerada. Este processo é repetido, considerando uma informação diferente a cada passo de tempo. As informações de todas as medições são acumuladas com o tempo e ajudam na predição do estado.
O vídeo também pode ser pré-processado, talvez utilizando alguma técnica de segmentação, para reduzir o custo computacional e consequentemente a latência.
Exemplo
[editar | editar código-fonte]Considere um vagão sobre trilhos retílineos infinitos e sem atrito. Inicialmente o vagão está parado na posição 0, mas é empurrado por acelerações aleatórias nos dois sentidos. A posição do vagão é medida a cada Δt segundos, mas as medidas são imprecisas; o objetivo é obter um modelo da posição e velocidade do vagão. Será mostrado como derivar o modelo sobre o qual é criado o filtro de Kalman.
Como F, H, R e Q são constantes, os índices temporais são ignorados.
A posição e velocidade do vagão são descritos pelo seguinte espaço de estados linear
onde é a velocidade, ou seja, a derivada da posição no tempo.
Assume-se que entre os passos de tempo (k − 1) e k o vagão sofre uma aceleração constante de ak, que é normalmente distribuída com média zero e desvio padrão σa. Das equações do movimento, conclui-se que
(note que não há o termo pois não há entradas de controle) onde
e
de modo que
onde e
A cada passo de tempo, uma medição ruidosa da posição do vagão é realizada. Supondo que o ruído na medição vk também é normalmente distribuído com média zero e desvio padrão σz, temos
onde
e
Considerando que o estado inicial é conhecido precisamente, fazemos a inicialização
e para dizer ao filtro que o estado iniciado é conhecido exatamente, a estimativa inicial para a matriz de covariancia é zero:
Se a posição e velocidade iniciais não forem conhecidas com precisão, a matriz de covariância deve ser inicializada com um valor grande na diagonal. Chamando este valor de L, temos
E o filtro irá dar um peso maior na informação das primeiras medições do que na informação contida inicialmente no modelo.
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Exemplo_de_resultado_obtido_com_o_filtro_de_kalman.svg/631px-Exemplo_de_resultado_obtido_com_o_filtro_de_kalman.svg.png)
Ver também
[editar | editar código-fonte]- Gelb, A. (1974). Applied Optimal Estimation. [S.l.]: MIT Press
- Kalman, R.E. (1960). «A new approach to linear filtering and prediction problems» (PDF). Journal of Basic Engineering. 82 (1): 35–45. Consultado em 3 de maio de 2008. Arquivado do original (PDF) em 29 de maio de 2008
- Kalman, R.E.; Bucy, R.S. (1961). «New Results in Linear Filtering and Prediction Theory.». Consultado em 3 de maio de 2008
- Harvey, A.C. (1990). Forecasting, Structural Time Series Models and the Kalman Filter. [S.l.]: Cambridge University Press
- Roweis, S.; Ghahramani, Z. (1999). «A Unifying Review of Linear Gaussian Models». Neural Computation. 11 (2): 305–345. PMID 9950734. doi:10.1162/089976699300016674
- Simon, D. (2006). Optimal State Estimation: Kalman, H Infinity, and Nonlinear Approaches. [S.l.]: Wiley-Interscience
- Stengel, R.F. (1994). Optimal Control and Estimation. [S.l.]: Dover Publications. ISBN 0-486-68200-5
- Warwick, K. (1987). «Optimal observers for ARMA models» (PDF). International Journal of Control. 46 (5): 1493–1503. doi:10.1080/00207178708933989. Consultado em 3 de maio de 2008
- Bierman, G.J. (1977). Factorization Methods for Discrete Sequential Estimation. Mathematics in Science and Engineering. 128. Mineola, N.Y.: Dover Publications. ISBN 9780486449814
- Bozic, S.M. (1994). Digital and Kalman filtering. [S.l.]: Butterworth-Heinemann
- Haykin, S. (2002). Adaptive Filter Theory. [S.l.]: Prentice Hall
- Liu, W.; Principe, J.C. and Haykin, S. (2010). Kernel Adaptive Filtering: A Comprehensive Introduction. [S.l.]: John Wiley
- Manolakis, D.G. (1999). Statistical and Adaptive signal processing. [S.l.]: Artech House
- Welch, Greg; Bishop, Gary (1997). «SCAAT: Incremental Tracking with Incomplete Information» (PDF). ACM Press/Addison-Wesley Publishing Co: 333–344. ISBN 0-89791-896-7. doi:10.1145/258734.258876
- Jazwinski, Andrew H. (1970). Stochastic Processes and Filtering. Col: Mathematics in Science and Enginerring. New York: Academic Press. 376 páginas
- Maybeck, Peter S. (1979). Stochastic Models, Estimation, and Control. Col: Mathematics in Science and Enginerring. 141-1. New York: Academic Press. 423 páginas. ISBN 0124807011
- Grewal, Mohinder S.; Andrews, Angus P. (2001). Kalman filtering: theory and practice using MATLAB (PDF) Second ed. New York: John Wiley & Sons. 401 páginas. ISBN 0471392545
- Chui, Charles K.; Chen, Guanrong (2009). Kalman Filtering with Real-Time Applications. Col: Springer Series in Information Sciences. 17 4th ed. New York: Springer. 229 páginas. ISBN 9783540878483
- Spivey, Ben; Hedengren, J. D. and Edgar, T. F. (2010). «Constrained Nonlinear Estimation for Industrial Process Fouling». Industrial & Engineering Chemistry Research. 49 (17): 7824–7831. doi:10.1021/ie9018116
- Thomas Kailath, Ali H. Sayed, and Babak Hassibi, Linear Estimation, Prentice-Hall, NJ, 2000, ISBN 978-0-13-022464-4.
- Ali H. Sayed, Adaptive Filters, Wiley, NJ, 2008, ISBN 978-0-470-25388-5.
Referências
[editar | editar código-fonte]- ↑ Steffen L. Lauritzen. "Time series analysis in 1880. A discussion of contributions made by T.N. Thiele". International Statistical Review 49, 1981, 319-333.
- ↑ Steffen L. Lauritzen, Thiele: Pioneer in Statistics, Oxford University Press, 2002. ISBN 0-19-850972-3.
- ↑ Stratonovich, R.L. (1959). Optimum nonlinear systems which bring about a separation of a signal with constant parameters from noise. Radiofizika, 2:6, pp. 892–901.
- ↑ Stratonovich, R.L. (1960) Application of the Markov processes theory to optimal filtering. Radio Engineering and Electronic Physics, 5:11, pp. 1–19.
- ↑ Ingvar Strid; Karl Walentin (abril de 2009). «Block Kalman Filtering for Large-Scale DSGE Models» (PDF). Springer. Computational Economics. 33 (3): 277–304. doi:10.1007/s10614-008-9160-4
- ↑ Martin Møller Andreasen (2008). «Non-linear DSGE Models, The Central Difference Kalman Filter, and The Mean Shifted Particle Filter» (PDF)
- ↑ Roweis, S. and Ghahramani, Z., A unifying review of linear Gaussian models, Neural Comput. Vol. 11, No. 2, (February 1999), pp. 305–345.
Ligações externas
[editar | editar código-fonte]- A New Approach to Linear Filtering and Prediction Problems, by R. E. Kalman, 1960
- Kalman–Bucy Filter, derivação do filtro de Kalman–Bucy
- Vídeo-aula do MIT sobre o filtro de Kalman
- An Introduction to the Kalman Filter, Curso do SIGGRAPH 2001, de Greg Welch e Gary Bishop
- Capítulo sobre filtro de Kalman de Stochastic Models, Estimation, and Control, vol. 1, por Peter S. Maybeck
- Kalman Filter página da web, com vários links
- Kalman Filtering
- Kalman Filters, indrodução aos diversos tipos e aplicações em Localização de Robôs.
- Filtros de Kalman utilizados em modelos climáticos, SIAM News, Volume 36, Number 8, October 2003.