Improved Distributed Particle Filter Architecture with Novel Resampling Algorithm for Signal Tracking

Document Type : Original Article

Authors

1 Faculty of Electrical Engineering, Shahid Beheshti University, Tehran, Iran

2 Faculty of Electrical Engineering, Shahid Beheshti University, Tehran, Iran; and School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran

Abstract

Resampling is a critical step in Particle Filter (PF) because of particle degeneracy and impoverishment problems. Independent Metropolis Hasting (IMH) resampling algorithm is a robust and high-speed method that can be used as the resampling step in PF. In this paper, a new algorithm based on IMH resampling is first proposed. The proposed algorithm classifies the particles before entering to the resampling module. The classification causes those essential particles are only routed to the IMH resampler. Then we propose a distributed architecture to reduce the execution time and high-speed processing for resampling. Simulation results for tracking a signal indicate that the PF with the proposed resampling architecture has acceptable tracking performance in comparison to other resampling methods. The PF architecture with the novel Improved IMH (IIMH) resampling algorithm has 33% more speed than the best-reported method in PF. Also, the proposed distributed PF architecture achieve 79% more speed compared with the best-reported method in PF. FPGA-based implementation results indicate that the utilization of the proposed IIMH resampling algorithm in PF and also distributed architecture lead to hardware resource and area usage reduction.

Keywords

References

1.     Feizi, A., "Convolutional gating network for object tracking", International Journal of Engineering, Transactions A: Basics, Vol. 32, No. 7, (2019), 931-939. DOI: 0.5829/IJE.2019.32.07A.05
2.     Sadegh Moghadasi, S. and Faraji, N., "An efficient target tracking algorithm based on particle filter and genetic algorithm", International Journal of Engineering, Transactions A: Basics, Vol. 32, No. 7, (2019), 915-923. DOI: 10.5829/IJE.2019.32.07A.03
3.     Liu, J.S., Chen, R. and Logvinenko, T., A theoretical framework for sequential importance sampling with resampling, in Sequential monte carlo methods in practice. 2001, Springer.225-246. DOI: 10.1007/978-1-4757-3437-9_11
4.     Zhao, Z., Wang, T., Liu, F., Choe, G., Yuan, C. and Cui, Z., "Remarkable local resampling based on particle filter for visual tracking", Multimedia Tools and Applications,  Vol. 76, No. 1, (2017), 835-860. DOI: 10.1007/s11042-015-3075-6
5.     Hong, S., Chin, S.-S., Djurić, P.M. and Bolić, M., "Design and implementation of flexible resampling mechanism for high-speed parallel particle filters", Journal of VLSI Signal Processing Systems for Signal, Image and Video Technology,  Vol. 44, No. 1-2, (2006), 47-62. DOI: : 10.1007/s11265-006-5919-9
6.     Abd El-Halym, H.A., Mahmoud, I.I. and Habib, S., "Proposed hardware architectures of particle filter for object tracking", EURASIP Journal on Advances in Signal Processing,  Vol. 2012, No. 1, (2012), 17. DOI: 10.1186/1687-6180-2012-17
7.     Li, T., Bolic, M. and Djuric, P.M., "Resampling methods for particle filtering: Classification, implementation, and strategies", IEEE Signal Processing Magazine,  Vol. 32, No. 3, (2015), 70-86. DOI: 10.1109/MSP.2014.2330626
8.     Bolić, M., Djurić, P.M. and Hong, S., "Resampling algorithms for particle filters: A computational complexity perspective", EURASIP Journal on Advances in Signal Processing,  Vol. 2004, No. 15, (2004), 403686. DOI: 10.1155/S1110865704405149
9.     Pan, Y., Zheng, N., Tian, Q., Yan, X. and Huan, R., "Hierarchical resampling algorithm and architecture for distributed particle filters", Journal of Signal Processing Systems,  Vol. 71, No. 3, (2013), 237-246. DOI: 10.1007/s11265-012-0712-4
10.   Gan, Q., Langlois, J.P. and Savaria, Y., "A parallel systematic resampling algorithm for high-speed particle filters in embedded systems", Circuits, Systems, and Signal Processing,  Vol. 33, No. 11, (2014), 3591-3602. DOI: 10.1007/s00034-014-9820-7
11.   Douc, R. and Cappé, O., "Comparison of resampling schemes for particle filtering", in ISPA 2005. Proceedings of the 4th International Symposium on Image and Signal Processing and Analysis, IEEE. (2005), 64-69. DOI: 10.1109/ISPA.2005.195385
12.   Hong, S.-H., Shi, Z.-G., Chen, J.-M. and Chen, K.-S., "A low-power memory-efficient resampling architecture for particle filters", Circuits, Systems and Signal Processing,  Vol. 29, No. 1, (2010), 155-167. DOI: 10.1007/s00034-009-9117-4
13.   Murray, L., "Gpu acceleration of the particle filter: The metropolis resampler", arXiv Preprint arXiv:1202.6163,  (2012).
14.   Sankaranarayanan, A.C., Srivastava, A. and Chellappa, R., "Algorithmic and architectural optimizations for computationally efficient particle filtering", IEEE Transactions on Image Processing,  Vol. 17, No. 5, (2008), 737-748. DOI: 10.1109/TIP.2008.920760
15.   Hong, S., Shi, Z. and Chen, K., "Easy-hardware-implementation mmpf for maneuvering target tracking: Algorithm and architecture", Journal of Signal Processing Systems,  Vol. 61, No. 3, (2010), 259-269. DOI: 10.1007/s11265-010-0450-4
16.   Medina, A.R., "Hardware-based particle filter with evolutionary resampling stage", Master thesis, 3-2014, Universidad Politécnica de Madrid,  (2014)
International Journal of Engineering
Volume 33, Issue 12
TRANSACTIONS C: Aspects
December 2020
Pages 2482-2488

Files

Cited by

Share

How to cite

Statistics