liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Complexity Analysis of the Marginalized Particle Filter
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
2005 (English)In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 53, no 11, 4408-4411 p.Article in journal (Refereed) Published
Abstract [en]

In this paper, the computational complexity of the marginalized particle filter is analyzed and a general method to perform this analysis is given. The key is the introduction of the equivalent flop measure. In an extensive Monte Carlo simulation, different computational aspects are studied and compared with the derived theoretical results.

Place, publisher, year, edition, pages
IEEE Signal Processing Society, 2005. Vol. 53, no 11, 4408-4411 p.
Keyword [en]
Complexity analysis, Kalman filter, Equivalent flop, Marginalized particle filter, Nonlinear estimation
National Category
Control Engineering
Identifiers
URN: urn:nbn:se:liu:diva-11751DOI: 10.1109/TSP.2005.857061OAI: oai:DiVA.org:liu-11751DiVA: diva2:18185
Available from: 2008-05-07 Created: 2008-05-07 Last updated: 2013-07-17
In thesis
1. Estimation of Nonlinear Dynamic Systems: Theory and Applications
Open this publication in new window or tab >>Estimation of Nonlinear Dynamic Systems: Theory and Applications
2006 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis deals with estimation of states and parameters in nonlinear and non-Gaussian dynamic systems. Sequential Monte Carlo methods are mainly used to this end. These methods rely on models of the underlying system, motivating some developments of the model concept. One of the main reasons for the interest in nonlinear estimation is that problems of this kind arise naturally in many important applications. Several applications of nonlinear estimation are studied.

The models most commonly used for estimation are based on stochastic difference equations, referred to as state-space models. This thesis is mainly concerned with models of this kind. However, there will be a brief digression from this, in the treatment of the mathematically more intricate differential-algebraic equations. Here, the purpose is to write these equations in a form suitable for statistical signal processing.

The nonlinear state estimation problem is addressed using sequential Monte Carlo methods, commonly referred to as particle methods. When there is a linear sub-structure inherent in the underlying model, this can be exploited by the powerful combination of the particle filter and the Kalman filter, presented by the marginalized particle filter. This algorithm is also known as the Rao-Blackwellized particle filter and it is thoroughly derived and explained in conjunction with a rather general class of mixed linear/nonlinear state-space models. Models of this type are often used in studying positioning and target tracking applications. This is illustrated using several examples from the automotive and the aircraft industry. Furthermore, the computational complexity of the marginalized particle filter is analyzed.

The parameter estimation problem is addressed for a relatively general class of mixed linear/nonlinear state-space models. The expectation maximization algorithm is used to calculate parameter estimates from batch data. In devising this algorithm, the need to solve a nonlinear smoothing problem arises, which is handled using a particle smoother. The use of the marginalized particle filter for recursive parameterestimation is also investigated.

The applications considered are the camera positioning problem arising from augmented reality and sensor fusion problems originating from automotive active safety systems. The use of vision measurements in the estimation problem is central to both applications. In augmented reality, the estimates of the camera’s position and orientation are imperative in the process of overlaying computer generated objects onto the live video stream. The objective in the sensor fusion problems arising in automotive safety systems is to provide information about the host vehicle and its surroundings, such as the position of other vehicles and the road geometry. Information of this kind is crucial for many systems, such as adaptive cruise control, collision avoidance and lane guidance.

Place, publisher, year, edition, pages
Institutionen för systemteknik, 2006
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 998
Series
Keyword
Nonlinear estimation, system identification, Kalman filter, particle filter, marginalized particle filter, expectation maximization, automotive applications
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-7124 (URN)91-85497-03-7 (ISBN)
Public defence
2006-02-02, Visionen, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Opponent
Supervisors
Available from: 2006-09-04 Created: 2006-09-04 Last updated: 2009-06-04
2. Particle filtering for positioning and tracking applications
Open this publication in new window or tab >>Particle filtering for positioning and tracking applications
2005 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

A Bayesian approach to positioning and tracking applications naturally leads to a recursive estimation formulation. The recently invented particle filter provides a numerical solution to the non-tractable recursive Bayesian estimation problem. As an alternative, traditional methods such as the extended Kalman filter. which is based on a linearized model and an assumption on Gaussian noise, yield approximate solutions.

In many practical applications, signal quantization and algorithmic complexity are fundamental issues. For measurement quantization, estimation performance is analyzed in detail. The algorithmic complexity is addressed for the marginalized particle filter, where the Kalman filter solves a linear subsystem subject to Gaussian noise efficiently.

The particle filter is adopted to several positioning and tracking applications and compared to traditional approaches. Particularly, the use of external database information to enhance estimation performance is discussed. In parallel, fundamental limits are derived analytically or numerically using the Cramér-Rao lower bound, and the result from estimation studies is compared to the corresponding lower bound. A framework for map-aided positioning at sea is developed, featuring an underwater positioning system using depth information and readings from a sonar sensor and a novel surface navigation system using radar measurements and sea chart information. Bayesian estimation techniques are also used to improve position accuracy for an industrial robot. The bearings-only tracking problem is addressed using Bayesian techniques and map information is used to improve the estimation performance. For multiple-target tracking problems data association is an important issue. A method to incorporate classical association methods when the estimation is based on the particle filter is presented. A real-time implementation of the particle filter as well as hypothesis testing is introduced for a collision avoidance application.

Place, publisher, year, edition, pages
Linköping, Sweden: Linköping University Electronic Press, 2005. 55 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 924
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-29608 (URN)14987 (Local ID)91-85297-34-8 (ISBN)14987 (Archive number)14987 (OAI)
Public defence
2005-03-18, Sal Visionen, Campus Valla, Linköping, 10:15 (Swedish)
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2012-11-29Bibliographically approved

Open Access in DiVA

fulltext(246 kB)473 downloads
File information
File name FULLTEXT01.pdfFile size 246 kBChecksum SHA-1
87df407456006a1a5c5e25f3e8d408b986fc56ccacc6901200e6cadec57a5dc83d777b63
Type fulltextMimetype application/pdf

Other links

Publisher's full textRelated report

Authority records BETA

Karlsson, RickardSchön, ThomasGustafsson, Fredrik

Search in DiVA

By author/editor
Karlsson, RickardSchön, ThomasGustafsson, Fredrik
By organisation
Automatic ControlThe Institute of Technology
In the same journal
IEEE Transactions on Signal Processing
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 473 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 384 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf