Contribution of the resampling stage to the execution time of particle filter Yeniden örnekleme adiminin parçacik süzgecinin çalişma zamanina katkisi

Date

2019-04-01

Author

Dulger, Ozcan
Oğuztüzün, Mehmet Halit S.

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

74
views

0
downloads

© 2019 IEEE.Particle filter is a serial Monte Carlo estimation algorithm. It represents the posterior probability density function with particles and their weights. As time progresses, the normalized weight of one of particles becomes nearly one, while the normalized weights of the remaining ones get close to zero. A common way to solve this problem, known as the degeneracy problem, is resampling. In resampling, the particles with larger weights are replicated, and the particles with smaller weights are eliminated. To tackle the numerical instability problem that is encountered by some of the resampling methods, the Metropolis resampling method is proposed by Murray and his co-workers. Unfortunately, Metropolis is liable to non-coalesced global memory access patterns on the GPU. In this work, we point to the Metropolis-C1 and Metropolis-C2 resampling methods which are proposed earlier. Then we examine the contribution of the stages of the particle filter to the total execution time by increasing the number of particles on a tracking application on the GPU. We use the Sampling Importance Resampling (SIR) method, which is a common particle filter. In the experiments, Metropolis resampling consumes the biggest portion of the execution time of the SIR particle filter. The share of Metropolis increases as the number of particles grows. It can be argued that this is because of non-coalesced global memory access patterns. To reach this conclusion it is sufficient to i) Compare the results of Metropolis, which has non-coalesced access patterns, with Metropolis-C1 and Metropolis-C2, which have confined non-coalesced access patterns, ii) See that the previous stages of the SIR particle filter are not subject to non-coalesced access patterns.

Subject Keywords

Art, Estimation, Particle filters, Nanoelectromechanical systems, Dogs, Monte Carlo methods, Graphics processing units

URI

https://hdl.handle.net/11511/56233

DOI

https://doi.org/10.1109/siu.2019.8806527

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Implementation of the Sampling Importance Resampling Particle Filter Algorithm in Graphics Processing Unit Dülger, Özcan; Oğuztüzün, Mehmet Halit S.; Demirekler, Mübeccel (2015-05-19) When the particle filter has too many particles, the computational cost increases and the sequential algorithms become inefficient in terms of the execution time. Recent developments in the graphics processing unit technology offer promising solutions for the speedup of the particle filter. In this study, Sampling Importance Resampling (SIR) particle filter method is implemented on the graphics processing unit. The speedup results are compared with results of the sequential and parallel implementations of t...
A novel adaptive unscented Kalman filter for pico satellite attitude estimation Söken, Halil Ersin (2011-09-08) Unscented Kalman Filter (UKF) is a filtering algorithm which gives sufficiently good estimation results for estimation problems of nonlinear systems even in case of high nonlinearity. However, in case of system uncertainty UKF becomes to be inaccurate and diverges by time. In other words, if any change occurs in the process noise covariance, which is known as a priori, filter fails. This study, introduces a novel Adaptive Unscented Kalman Filter (AUKF) algorithm based on the correction of process noise cova...
Robust Attitude Estimation Using IMU-Only Measurements Candan, Batu; Söken, Halil Ersin (2021-01-01) © 1963-2012 IEEE.This article proposes two novel covariance-tuning methods to form a robust Kalman filter (RKF) algorithm for attitude (i.e., roll and pitch) estimation using the measurements of only an inertial measurement unit (IMU). KF-based and complementary filtering (CF)-based approaches are the two common methods for solving the attitude estimation problem. Efficiency and optimality of the KF-based attitude filters are correlated with appropriate tuning of the covariance matrices. Manual tuning proce...
Investigation of the star tracker algorithms and kalman filter integration Sargın Güçlü, Selva; Yavrucuk, İlkay; Department of Aerospace Engineering (2019) This research outlines the investigation of star tracker algorithms and Kalman Filter implementation of star tracker aided INS. In the first chapter, the usage areas of the star tracker sensor was investigated. The purposes to use this sensor were also included. Furthermore, the sensor architecture and algorithms were examined. In the second chapter, the three main steps of the star tracker algorithms were investigated. First of all, literature survey about centroiding algorithms was done and two of them we...
Extension of Forward Backward Method with DFT Based Acceleration Algorithm for The Efficient Analysis of Radiation Scattering from Large Finite Printed Dipole Arrays Aydın Çivi, Hatice Özlem (Wiley, 2003-04-01) A discrete‐Fourier‐transform (DFT) based forward‐backward (FB) algorithm has been developed for the fast and accurate analysis of electrically large freestanding dipole arrays [1]. In this paper, an extension of the FB method (FBM) with a DFT‐based acceleration approach is presented to provide a relatively efficient analysis of EM radiation/scattering from an electrically large, planar, periodic, finite dipole array printed on a grounded dielectric substrate. Computational complexity of this new approach is...

Citation Formats

O. Dulger and M. H. S. Oğuztüzün, “Contribution of the resampling stage to the execution time of particle filter Yeniden örnekleme adiminin parçacik süzgecinin çalişma zamanina katkisi,” 2019, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/56233.