Study of Algorithmic and Architectural Characteristics of Gaussian Particle Filters

In this paper, we analyze algorithmic and architectural characteristics of a class of particle filters known as Gaussian Particle Filters (GPFs). GPFs approximate the posterior density of the unknowns with a Gaussian distribution which limits the scope of their applications in comparison with the universally applied sample-importance resampling filters (SIRFs) but allows for their implementation without the classical resampling procedure. Since there is no need for resampling, we propose a modified GPF algorithm that is suitable for parallel hardware realization. Based on the new algorithm, we propose an efficient parallel and pipelined architecture for GPF that is superior to similar architectures for SIRF in the sense that it requires no memories for storing particles and it has very low amount of data exchange through the communication network. We analyze the GPF on the bearings-only tracking problem and the results are compared with results obtained by SIRF in terms of computational complexity, potential throughput, and hardware energy. We consider implementation on FPGAs and we perform detailed comparison of the GPF and SIRF algorithms implemented in different ways on this platform. GPFs that are implemented in parallel pipelined fashion on FPGAs can support higher sampling rates than SIRFs and as such they might be a more suitable candidate for real-time applications.     

Hierarchical Resampling Algorithm and Architecture for Distributed Particle Filters

In this paper, we introduce a hierarchical resampling (HR) algorithm and architecture for distributed particle filters (PFs). While maintaining the same accuracy as centralized resampling in statistics, the proposed HR algorithm decomposes the resampling step into two hierarchies including intermediate resampling (IR) and unitary resampling (UR), which suits PFs for distributed hardware implementation. Also presented includes a residual cumulative resampling (RCR) method that pipelines and accelerates the UR step. The corresponding architecture, when compared with traditional distributed architectures, eliminates the particle redistribution step, and has such advantages as short execution time and high memory efficiency. The prototype containing 8 PEs has been developed in Xilinx Virtex IV FPGA (XC4VFX100-12FF1152) for the bearings-only tracking (BOT) problem, and the result shows that the input observations can be processed at 37.21 KHz with 8 K particles and a clock speed of 80 MHz.     

Memory Coalescing Implementation of Metropolis Resampling on Graphics Processing Unit

Owing to many cores in its architecture, graphics processing unit (GPU) offers promise for parallel execution of the particle filter. A stage of the particle filter that is particularly challenging to parallelize is resampling. There are parallel resampling algorithms in the literature such as Metropolis resampling, which does not require a collective operation such as cumulative sum over weights and does not suffer from numerical instability. However, with large number of particles, Metropolis resampling becomes slow. This is because of the non-coalesced access problem on the global memory of the GPU. In this article, we offer solutions for this problem of Metropolis resampling. We introduce two implementation techniques, named Metropolis-C1 and Metropolis-C2, and compare them with the original Metropolis resampling on NVIDIA Tesla K40 board. In the first scenario where these two techniques achieve their fastest execution times, Metropolis-C1 is faster than the others, but yields the worst results in quality. However, Metropolis-C2 is closer to Metropolis resampling in quality. In the second scenario where all three algorithms yield similar quality, although Metropolis-C1 and Metropolis-C2 get slower, they are still faster than the original Metropolis resampling.     

A Low-Power Memory-Efficient Resampling Architecture for Particle Filters

In this paper, we propose a compact threshold-based resampling algorithm and architecture for efficient hardware implementation of particle filters (PFs). By using a simple threshold-based scheme, this resampling algorithm can reduce the complexity of hardware implementation and power consumption. Simulation results indicate that this algorithm has approximately equal performance with the traditional systematic resampling (SR) algorithm when the root-mean-square error (RMSE) and lost track are considered. Experimental comparison of the proposed hardware architecture with those based on the SR and the residual systematic resampling (RSR) algorithms was conducted on a Xilinx Virtex-II Pro field programmable gate array (FPGA) platform in the bearings-only tracking context, and the results establish the superiority of the proposed architecture in terms of high memory efficiency, low power consumption, and low latency.     

Improved particle filter based on fine resampling algorithm

In order to solve particle degeneracy phenomenon and simultaneously avoid sample impoverishment,this paper proposed an improved particle filter based on fine resampling algorithm for general case,calle...     

Efficient Parallelization of Polyphase Arbitrary Resampling FIR Filters for High-Speed Applications

This article describes a method for increasing the sampling rate of efficient polyphase arbitrary resampling FIR filters. An FPGA proof of concept prototype of this architecture has been implemented in a Xilinx Kintex-7 FPGA which is able to convert the sampling rate of a signal from 500 MHz to 600 MHz. This article compares this new architecture with other best known efficient resampling architectures implemented on the same FPGA. The area usage on the FPGA shows that our proposed implementation is very proficient in high bandwidth applications without requiring significantly more resources on the FPGA. A theoretical calculation of the resampling error introduced on a modulated data stream is provided to evaluate the new architecture against other existing resampling architectures.     

基于最优采样函数的粒子滤波算法与贝叶斯估计

传统粒子滤波器(PF)直接根据状态演化方程产生新的粒子,由于没有考虑新近观测对状态估计的影响,这种滤波器性能较差,即便在粒子数目很大的情况也是如此。为此,本文提出一种基于序贯重要采样(SIS)的改进粒子滤波算法,该算法采用集成了新近观测量的最优采样(或重要密度)函数指导粒子的生成,使粒子权值的方差最小化,能有效减轻粒子退化问题;同时。在粒子重采样之后增加了马尔科夫链蒙特卡洛(MCMC)过程,消除了重采样引起的粒子贫化的负面影响,从而使粒子的多样性得以保持。对非线性系统的状态估计和只测角跟踪的仿真实例均表明,本文所提出的算法比传统估计算法如EKF,UKF具有更高的精度和更强的鲁棒性;与标准PF相比,其性能也有较大的提高,并可以在相同的估计精度下大大减少所需的粒子数目,是一种有效的非线性滤波算法。     

基于颜色的粒子滤波算法的改进与全硬件实现

传统基于颜色的粒子滤波算法在硬件实现中存在着跟踪效果不理想、实时性差等问题.该文结合硬件电路需要对基于颜色的粒子滤波算法进行了改进,在传统SR重采样算法的基础上将剩余粒子撒向目标点附近,以提高其在硬件环境下跟踪的准确性与稳定性.文中给出了改进算法的全硬件实现的电路架构,并在FPGA上完成了目标跟踪系统的实现.实验表明提...     

基于粒子群优化和M-H采样粒子滤波的传感器网络目标跟踪方法

针对实际应用条件下传感器节点的观测数据与目标动态参数间呈现为非线性关系的特性,提出了一种基于粒子群优化和M-H抽样粒子滤波的传感器网络目标跟踪方法。该方法采用分布式结构,在动态网络拓扑结构下,由粒子群优化和M-H抽样技术实现滤波中的重抽样过程,抑制粒子退化现象,并通过粒子间共享历史信息,降低单个粒子历史状态间的相关性使各粒子能快速收敛至最优分布,从而实现高精度的目标跟踪效果。仿真结果表明,相比现有的基于信息粒子滤波和并行粒子滤波技术的传感器网络目标跟踪方法,所提出的方法能降低网络总能耗,同时保证目标跟踪的精度。     

Improved Particle Filter Resampling Architectures

The most challenging aspect of particle filtering hardware implementation is the resampling step. This is because of high latency as it can be only partially executed in parallel with the other steps of particle filtering and has no inherent parallelism inside it. To reduce the latency, an improved resampling architecture is proposed which involves pre-fetching from the weight memory in parallel to the fetching of a value from a random function generator along with architectures for realizing the pre-fetch technique. This enables a particle filter using M particles with otherwise streaming operation to get new inputs more often than 2M cycles as the previously best approach gives. Results show that a pre-fetch buffer of five values achieves the best area-latency reduction trade-off while on average achieving an 85% reduction in latency for the resampling step leading to a sample time reduction of more than 40%. We also propose a generic division-free architecture for the resampling steps. It also removes the need of explicitly ordering the random values for efficient multinomial resampling implementation. In addition, on-the-fly computation of the cumulative sum of weights is proposed which helps reduce the word length of the particle weight memory. FPGA implementation results show that the memory size is reduced by up to 50%.

     

代表点理论在粒子滤波算法中的应用

将统计学中的数论方法应用于粒子滤波,使用随机分布的均方差代表点,对粒子滤波中关键的初始粒子生成、重点密度采样及再采样过程给出了相应的代表点算法,得到了一个包含最少随机操作的、使用非等权值粒子的改进粒子滤波算法.     

Extensions of the SMC-PHD filters for jump Markov systems

The probability hypothesis density (PHD) filter is a promising algorithm for multitarget tracking, which can be extended for jump Markov systems (JMS). Since the existing multiple model sequential Monte Carlo PHD (MM SMC-PHD) filter is not interacting, two extensions of the SMC-PHD filters are developed in this paper. The interacting multiple-model (IMM) SMC-PHD filter approximates the model conditional PHD of target states by particles, and performs the interaction by resampling without any a priori assumption of the noise. The IMM Rao-Blackwellized particle (RBP) PHD filter uses the idea of Rao-Blackwellized to further enhance the performance of target state estimation for JMS with mixed linear/nonlinear state space models. The simulation results show that the proposed algorithms have better performances than the existing MM SMC-PHD filter in terms of state filtering and target number estimation.     

Easy-hardware-implementation MMPF for Maneuvering Target Tracking: Algorithm and Architecture

In this paper, we present an easy-hardware-implementation multiple model particle filter (MMPF) for maneuvering target tracking. In the proposed filter, the sampling importance resampling (SIR) filter typically used for nonlinear and/or non-Gaussian application is extended to incorporating multiple models that are composed of a constant velocity (CV) model and a “current” statistical (CS) model, and the Independent Metropolis Hasting (IMH) sampler is utilized for the resampling unit in each model. Compared with the bootstrap MMPF, the proposed MMPF requires no knowledge of models and model transition probabilities for different maneuvering motions, and keeps a constant number of particles per model at all times. This allows a regular pipelined hardware structure and can be implemented in hardware easily. Furthermore, using the IMH sampler for the resampling unit avoids the bottleneck introduced by the traditional systematic resampler and reduces the latency of the whole implementation. Simulation results indicate that the proposed filter has approximately equal tracking performance with the bootstrap MMPF. Hardware architecture of the IMH sampler and its corresponding sample unit are presented, and a parallel architecture consisting of CV model processing element (PE), CS model PE and a central unit (CU) is described. The proposed architecture is evaluated on a Xilinx Virtex-II Pro FPGA platform for a maneuvering target tracking application and the results show many advantages of the proposed MMPF over existing approaches in terms of efficiency, lower latency, and easy hardware implementation.     

基于CPFDE的目标跟踪算法研究

在目标跟踪中,为了克服粒子滤波的粒子退化和贫化问题,提高滤波精度,文中将差分演化算法与容积粒子滤波相结合,形成了差分演化容积粒子滤波算法。在粒子进行先验更新时, 使用容积卡尔曼滤波算法融入当前时刻的量测信息并用其来产生重要性密度函数,并且在重采样阶段,用差分演化算法对根据重要性密度函数抽取的采样粒子做优化操作,从而克服粒子滤波存在的粒子退化及贫化问题,提高滤波性能。实验结果表明,和粒子滤波、无迹粒子滤波、容积粒子滤波相比,该算法有着更高的滤波精度和更好的稳定性,并且能够提高雷达机动目标跟踪的精确性。     

基于Sh相关系数的非线性系统状态粒子估计算法

本文提出一种适用于非线性系统状态的粒子估计算法--基于Sh相关系数的粒子估计(PE)算法.该算法主要由预测、更新和平滑组成,利用被估计状态观测值路径和粒子观测值路径之间的Sh相关系数来修正粒子权值.仿真实验结果表明,该算法在状态估计精度上优于序列重要性重采样(SIR)算法、辅助粒子滤波(APF)算法、正则化粒子滤波(RPF)算法、高斯粒子滤波(GPF)算法和高斯混合粒子滤波(GSPF)算法.     

An improved Bernoulli particle filter for single target tracking

Single target tracking is widely applied in the current surveillance systems. The Bernoulli filter can complete the task of single target tracking using available measurements. However, the existing Bernoulli filters have estimation bias during the whole tracking process. Therefore, we present an improved Bernoulli filter and its particle implementation in this paper. Employed the weight optimization strategy, the under-estimated number of target is corrected by enlarging the maximal measurement-updated weight of sampling particle. In addition, the track identification strategy is applied to optimize number of the required particles and extract the actual target. Combined with the unscented transform for the complicated dynamic models, the nonlinear motion state of maneuvering target is effectively estimated. Besides, we extend the proposed filter in unknown clutter environment and estimate the mean clutter rate, which has significant application meaning owing to avoiding the assumption of the given detection profile. Finally, the numerical simulations demonstrate the tracking advantages with the promising results in comparison to the standard Bernoulli filter.     

Algorithm and Parallel Implementation of Particle Filtering and its Use in Waveform-Agile Sensing

Sequential Monte Carlo particle filters (PFs) are useful for estimating nonlinear non-Gaussian dynamic system parameters. As these algorithms are recursive, their real-time implementation can be computationally complex. In this paper, we analyze the bottlenecks in existing parallel PF algorithms, and propose a new approach that integrates parallel PFs with independent Metropolis–Hastings (PPF-IMH) resampling algorithms to improve root mean-squared estimation error (RMSE) performance. We implement the new PPF-IMH algorithm on a Xilinx Virtex-5 field programmable gate array (FPGA) platform. For a one-dimensional problem with 1,000 particles, the PPF-IMH architecture with four processing elements uses less than 5% of a Virtex-5 FPGA’s resource and takes 5.85 μs for one iteration. We also incorporate waveform-agile tracking techniques into the PPF-IMH algorithm. We demonstrate a significant performance improvement when the waveform is adaptively designed at each time step with 6.84 μs FPGA processing time per iteration.     

Bayesian methods for multiaspect target tracking in image sequences

In this paper, we introduce new algorithms for automatic tracking of multiaspect targets in cluttered image sequences. We depart from the conventional correlation filter/Kalman filter association approach to target tracking and propose instead a nonlinear Bayesian methodology that enables direct tracking from the image sequence incorporating the statistical models for the background clutter, target motion, and target aspect change. Proposed algorithms include 1) a batch hidden Markov model (HMM) smoother and a sequential HMM filter for joint multiframe target detection and tracking and 2) two mixed-state sequential importance sampling trackers based on the sampling/importance resampling (SIR) and the auxiliary particle filtering (APF) techniques. Performance studies show that the proposed algorithms outperform the association of a bank of template correlators and a Kalman filter in adverse scenarios of low target-to-clutter ratio and uncertainty in the true target aspect.     

基于遗传算法的智能粒子滤波重采样策略研究

智能粒子滤波通过借鉴遗传算法思想能够减轻粒子退化现象。在基于遗传算法的智能粒子滤波基础上,该文提出对低权值粒子的改进的智能粒子滤波(IIPF)处理策略。在对粒子进行分离、交叉后,优化遗传算子,对低权值粒子进行自适应处理。低权值粒子根据权值大小自行判断是否为底层粒子;底层粒子将直接进行变异,其余低权值粒子将根据变异概率随机变异。仿真结果表明,改进的智能粒子滤波(IIPF)性能优于智能粒子滤波、一般粒子滤波算法和拓展卡尔曼滤波。在1维仿真实验中,改进的智能粒子滤波误差较一般粒子滤波算法和智能粒子滤波分别降低了10.5%和8.5%,且具有更好的收敛性;在多维仿真实验中,改进的智能粒子滤波较智能粒子滤波在高度均方根误差和平均误差上分别降低了8.5%和7.5%,在速度均方根误差和平均误差上分别降低了11.5%和7.6%;在乘性噪声和非高斯随机噪声中,改进的智能粒子滤波依旧有10%以上的性能优势。     

基于人工蜂群算法的粒子滤波目标跟踪

针对基于粒子滤波的视频目标跟踪算法中由于粒子重采样过程而导致粒子贫化的问题,提出了一种基于人工蜂群算法的粒子滤波目标跟踪算法,利用群体智能的特点使得粒子集在重采样前得到优化,保持了粒子的多样性,从而解决了粒子贫化问题,同时增加了有效粒子的数目.实验结果表明,基于人工蜂群算法的粒子滤波跟踪算法,比标准粒子滤波跟踪算法所需粒子数更少,对目标遮挡、较复杂背景有较好的跟踪效果.