A Parallel Particle Tracking Framework for Applications in Scientific Computing

Particle tracking methods are a versatile computational technique central to the simulation of a wide range of scientific applications. In this paper, we present a new parallel particle tracking framework for the applications of scientific computing. The framework includes the in-element particle tracking method, which is based on the assumption that particle trajectories are computed by problem data localized to individual elements, as well as the dynamic partitioning of particle-mesh computational systems. The ultimate goal of this research is to develop a parallel in-element particle tracking framework capable of interfacing with a different order of accuracy of ordinary differential equation (ODE) solver. The parallel efficiency of such particle-mesh systems depends on the partitioning of both the mesh elements and the particles; this distribution can change dramatically because of movement of the particles and adaptive refinement of the mesh. To address this problem we introduce a combined load function that is a function of both the particle and mesh element distributions. We present experimental results that detail the performance of this parallel load balancing approach for a three-dimensional particle-mesh test problem on an unstructured, adaptive mesh, and demonstrate the ability of interfacing with different ODE solvers.     

An efficient and robust method for Lagrangian magnetic particle tracking in fluid flow simulations on unstructured grids

In this paper we report on a newly developed particle tracking scheme for fluid flow simulations on 3D unstructured grids, aiming to provide detailed insights in the particle behaviour in complex geometries. A possible field of applications is the magnetic drug targeting (MDT) technique, on which this paper will be focused. MDT is a promising medical technique that uses locally applied magnetic fields to capture magnetic drug carriers at the desired locations in the human body, strongly increasing the efficiency of medical drugs. The new particle tracking scheme combines the advantages of existing methods and is easy for implementation in a generic numerical code. The scheme is tested and validated for simple MDT cases that include effects of a non-homogeneous magnetic field on deposition of magnetic particles in laminar flow. The first test case is a validation study of the magnetic particle trajectories released in a horizontal circular pipe flow with a current-carrying wire parallel to the flow, for which analytical solutions are reported in literature. The second test case involves particle capture efficiencies in a 90° bent tube for different configurations of the imposed magnetic field. This configuration corresponds more closely to the conditions inside blood vessels, because of the presence of secondary motions. These results are compared with numerical studies from literature too. The obtained results demonstrate that the developed particle tracking scheme is a very robust, efficient and accurate method, which can give detailed insights in particle behaviour in complex geometries. As such it is a good candidate for future applications and optimisations of MDT technique for loco-regional cancer treatment or treatment of cardiovascular diseases.     

基于GPU加速的粒子滤波多说话人跟踪算法及其应用

为了解决粒子滤波多说话人跟踪过程中粒子易发散导致多目标跟踪精度低的问题,提出了并行粒子滤波和基于GPU的K-均值聚类的多声源定位方法。该方法首先分析了粒子滤波在实现多目标跟踪时,进行数据关联的过程产生较大的计算量,并且出现多个目标时,粒子会逐渐发散。针对计算量大和粒子发散的问题,提出了一种并行粒子滤波和K-均值聚类的方法。实验表明,随着粒子数和目标数的增加,计算量以指数增加,并且粒子发散严重,采用基于GPU的K-均值聚类方法的粒子滤波多说话人跟踪方法,相比传统粒子滤波跟踪方法具有更收敛的粒子集并且跟踪精度较高。     

GPU加速的差分进化粒子滤波算法

为了解决实时系统中粒子滤波的计算复杂性问题,本文提出了一种零bank冲突并行规约的差分进化粒子滤波方法。该方法首先分析了并行差分进化粒子滤波算法在GPU中的内存访问模式,根据粒子滤波器的均方根误差与内存访问bank(存储体)冲突度成正比的关系,提出了一种去除bank冲突的有填充寻址的差分进化粒子滤波算法,降低了计算复杂度。将该算法在NVIDIA GTX960 GPU中实现,与串行差分进化粒子滤波算法进行比较。实验表明,随着粒子数增加,计算量以指数增加,采用GPU加速的跟踪算法的执行时间明显减少,有效提高了跟踪精度、降低了计算时间。     

Parallel three-dimensional DSMC method using mesh refinement and variable time-step scheme

Application of variable time-step and unstructured adaptive mesh refinement in parallel three-dimensional Direct Simulation Monte Carlo (DSMC) method is presented. A variable time-step method using the particle fluxes conservation (mass, momentum and energy) across the cell interface is implemented to reduce the number of simulated particles and the number of iterations of transient period towards steady state, without sacrificing the solution accuracy. In addition, a three-dimensional h-refined unstructured adaptive mesh with simple but effective mesh-quality control, obtained from a preliminary parallel DSMC simulation, is used to increase the accuracy of the DSMC solution. Completed code is then applied to compute several external and internal flows, and compared with previous results wherever available.     

A parallel histogram-based particle filter for object tracking on SIMD-based smart cameras

We present a parallel implementation of a histogram-based particle filter for object tracking on smart cameras based on SIMD processors. We specifically focus on parallel computation of the particle weights and parallel construction of the feature histograms since these are the major bottlenecks in standard implementations of histogram-based particle filters. The proposed algorithm can be applied with any histogram-based feature sets—we show in detail how the parallel particle filter can employ simple color histograms as well as more complex histograms of oriented gradients (HOG). The algorithm was successfully implemented on an SIMD processor and performs robust object tracking at up to 30 frames per second—a performance difficult to achieve even on a modern desktop computer.     

基于相对熵的概率假设密度滤波器序贯蒙特卡罗实现方式

概率假设密度滤波器的典型序贯蒙特卡罗实现方式与粒子滤波类似,均是利用大量加权粒子估计多目标状态,典型实现方式是为每个期望目标分配固定数目的粒子,这导致较大的算法时间开销.鉴于此,建立了基于相对熵的序贯蒙特卡罗实现方式.首先计算两个不同规模粒子集合的相对熵,与预设阈值进行比较以确定粒子数目,从而动态调整粒子数目.仿真结果表明,所提出的实现方式提高了跟踪效率,在大部分时间步上优于典型实现方式.     

Parallel three-dimensional direct simulation Monte Carlo method and its applications

The development of a parallel three-dimensional direct simulation Monte Carlo (DSMC) method using unstructured cells is reported. Variable hard sphere molecular model and no time counter method are used for the molecular collision kinetics, while the cell-by-cell ray-tracing technique is implemented for particle movement. Developed serial code has been verified by comparing the results of a supersonic corner flow with those of Bird’s three-dimensional structured DSMC code. In addition, a benchmark test is performed for an orifice expanding flow to verify the parallel implementation of DSMC method by comparing with available experimental data. Static physical domain decomposition is used to distribute the workload among multiple processors by considering the estimated particle weighting distribution. Two-step multi-level graph partitioning technique is used to perform the required domain decomposition. Completed code is then applied to compute a hypersonic flow over a sphere (external flow) and the flow field of a spiral drag pump (internal flow), respectively. Results of the former are in good agreement with previous numerical results using axisymmetric DSMC method and experimental data. Results of the latter also agree well with previous numerical results.     

基于约束知识的IP-MCMC-PF目标跟踪方法研究

针对粒子滤波算法在有干扰的目标跟踪中可能出现的粒子多样性减少和精度下降等问题,研究并实现了一种新的基于约束知识的IP-MCMC-PF目标跟踪方法。该方法首先通过约束知识提高粒子预测的准确性,并通过多链并行的IP-MCMC方法提高粒子的多样性,有效地解决粒子退化问题;在此基础上通过PN学习算法在线更新抽样粒子的抽样分布和检测器的训练样本,实现目标跟踪算法的在线学习,有效提高了复杂背景下目标跟踪的准确度和自适应性。实验结果表明,该方法在遮挡、形变、光照变化等多种干扰的情形下都具有很好的跟踪效果。     

Parallel Unstructured Dynamic Grid Direct Monte Carlo Simulation of Molecular Gas Dynamics and Its Applications

A new parallel dynamic unstructured grid DSMC method is presented in this paper. The code developed has been applied to the simulation of thin film deposition over microstructures. Surface deformation in such cases poses a challenge for accurate evaluation of gas flow due to the fact that the deposited film thickness is comparable to the feature size. In this study a method is developed to move the mesh at run time. Since in parallel simulation each partition moves independently of the others, a parallel version of moving mesh is proposed to synchronize the displacement of the neighboring partitions, so that there is a smooth transition from one partition to another. An efficient tool for tracking particles during simulation is also presented. Furthermore, the influence of parameters, such as sticking coefficient and aspect ratio on step coverage for a 1m wide trench by sputter deposition was studied. The results showed that the step coverage deteriorated with increasing sticking coefficient and aspect ratio.     

共享存储并行多目标跟踪

高度的运算复杂性制约了粒子滤波在实际的多目标视频跟踪系统中的应用。为克服性能瓶颈,探索了一种基于OpenMP共享存储并行编程模型的粗粒度并行多目标跟踪系统的实现方法。在共享变量中维护被跟踪目标的列表,每一个目标用一个独立的粒子滤波器进行跟踪。根据处理单元的数目确定线程数量和每个线程跟踪的目标数量。与对应的串行版本相比,该并行系统将可实时跟踪的目标数目由2个增加到了8个,具有更大的实用价值。     

Tracking video objects with feature points based particle filtering

For intelligent video surveillance, the adaptive tracking of multiple moving objects is still an open issue. In this paper, a new multi-object tracking method based on video frames is proposed. A type of particle filtering combined with the SIFT (Scale Invariant Feature Transform) is proposed for motion tracking, where SIFT key points are treated as parts of particles to improve the sample distribution. Then, a queue chain method is adopted to record data associations among different objects, which could improve the detection accuracy and reduce the computational complexity. By actual road tests and comparisons, the system tracks multi-objects with better performance, e.g., real time implementation and robust against mutual occlusions, indicating that it is effective for intelligent video surveillance systems.     

槽流拟颗粒模型的并行算法

将流体处理为离散粒子,应用拟颗粒硬球模型来研究槽流中的流动现象,与分子动力学模拟的算法类似,是研究槽流机理的一种行之有效的方法。为了作大规模的模拟,本文采用区域分解算法和消息传递编程模型技术,将该模型串行程序并行化,应用一维划分、单相传递的方法简化了并行算法,采用轮换搜索法来避免硬球碰撞次序对结果的影响。在可扩展的机群系统上用实例计算,通过与串行程序的对比,验证了并行程序的正确性,表明本文设计的并行算法取得了较高的并行计算效率。     

Intelligent video target tracking using an evolutionary particle filter based upon improved cuckoo search

The aim of this paper is to propose an evolutionary particle filter based upon improved cuckoo search algorithm which will overcome the sample impoverishment problem of generic particle filter. In our proposed method, improved cuckoo search (ICS) algorithm is embedded into particle filter (PF) framework. Improved cuckoo search algorithm uses levy flight for generating new particles in the solution and introduced randomness in samples by abandoning a fraction of these particles. The second important contribution in this article is introduction of new way for tackling scaling and rotational error in object tracking. Performance of proposed improved cuckoo particle filter is investigated and evaluated on synthetic and standard video sequences and compared with the generic particle filter and particle swarm optimization based particle filter. We show that object tracking using improved cuckoo particle filter provides more reliable and efficient tracking results than generic particle filter and PSO-particle filter. The proposed technique works for real time video objects tracking.     

基于改进布谷鸟粒子滤波算法的WSN目标跟踪

为了解决粒子滤波(PF)的无线传感器目标跟踪中样本贫化导致的精度较低的问题,提出了改进布谷鸟粒子滤波的WSN目标跟踪方法。通过改进布谷鸟算法的滤波算法取代粒子滤波重采样过程,主要通过改进布谷鸟算法中的搜索步长值 和发现外来鸟卵的物种的概率 的自适应调节,同时在步长更新方程中实时引入函数值的变化趋势,引导粒子整体上向较高的随机区域移动, 有效调整全局探索和局部探索适应能力、改善粒子贫化和局部极值问题,增加粒子群多样化从而提高跟踪性能。实验结果表明,改进布谷鸟粒子滤波算法重采样方法可以防止粒子的退化,增加粒子的多样性,减少跟踪误差,可以减少算法的运行时间,实时追踪性能大幅提高。与CS-PF算法和PF算法相比较,ICS-PF 算法的计算时间是最短的,ICS-PF算法的位置和速度的平均平方根误差最小(位置0.0306、0.0213、速度0.0253、0.0102),PF算法的跟踪精度是最低的,而ICS-PF跟踪精度较高,ICS-PF算法被证明具有良好的跟踪性能。     

基于核函数粒子滤波和多特征自适应融合的目标跟踪

经典粒子滤波及其改进算法在观测模型与真实情况存在偏差时会导致滤波发散,针对这一问题,提出一种核函数粒子滤波算法.该算法根据目标状态与粒子状态之间的距离,利用核函数产生权值对粒子进行二次加权,根据粒子的二次加权结果进行粒子重采样;以改进的粒子滤波算法为框架,提出了一种自适应多特征融合目标跟踪方法,利用相似性度量动态地评价特征对目标与背景的区分能力,并自适应地计算特征融合权重,以适应目标跟踪过程中目标与背景的变化,提高目标跟踪的鲁棒性.实验结果表明,文中提出的目标跟踪方法比经典粒子滤波目标跟踪方法具有更强的抗干扰性能和较高的跟踪精度.     

基于自适应蝙蝠粒子滤波算法的WSN目标跟踪

为了解决粒子滤波(PF)的无线传感器目标跟踪中样本贫化导致的精度较低的问题,提出了自适应蝙蝠粒子滤波的WSN目标跟踪方法。通过自适应的蝙蝠算法的滤波算法优化粒子重采样过程,结合最新的观测值定义粒子的适应度函数,引导粒子整体上向较高的随机区域移动。同时利用动态自适应惯性权重探索新的粒子位置更新为设计机制,引入动态适应惯性权重值, 有效调整全局探索和局部探索适应能力、改善粒子贫化和局部极值问题,增加粒子群多样化从而提高跟踪性能。实验结果表明,自适应蝙蝠粒子滤波算法重采样方法可以防止粒子的退化,增加粒子的多样性,减少跟踪误差,可以减少算法的运行时间,实时追踪性能大幅提高。与BA-PF算法和PF算法相比较,IBAPF 算法的计算时间是最短的,IBA-PF算法的位置和速度的平均平方根误差最小(位置0.0311、0.0202、速度0.0262、0.0101),PF算法的跟踪精度是最低的,而IBA-PF跟踪精度较高,IBA-PF算法被证明具有良好的跟踪性能。     

Stochastic Volume Rendering of Multi‐Phase SPH Data

In this paper, we present a novel method for the direct volume rendering of large smoothed‐particle hydrodynamics (SPH) simulation data without transforming the unstructured data to an intermediate representation. By directly visualizing the unstructured particle data, we avoid long preprocessing times and large storage requirements. This enables the visualization of large, time‐dependent, and multivariate data both as a post‐process and in situ. To address the computational complexity, we introduce stochastic volume rendering that considers only a subset of particles at each step during ray marching. The sample probabilities for selecting this subset at each step are thereby determined both in a view‐dependent manner and based on the spatial complexity of the data. Our stochastic volume rendering enables us to scale continuously from a fast, interactive preview to a more accurate volume rendering at higher cost. Lastly, we discuss the visualization of free‐surface and multi‐phase flows by including a multi‐material model with volumetric and surface shading into the stochastic volume rendering.     

基于Beowulf机群中改进粒子滤波的3D人体运动跟踪

针对标准的粒子滤波算法在视频三维人体运动跟踪中存在的计算量巨大、粒子退化、跟踪失效而无法同时满足跟踪精度和跟踪实时性要求的问题,提出了基于Beowulf机群中改进的粒子滤波新算法。新算法通过三维人体模型参数的自动初始化、粒子数目和模板的调整来实现跟踪失效的自动恢复,基于任务动态分配策略、低开销通信策略设计的Beowulf机群中的迁移式粒子滤波并行算法克服了粒子退化问题和提高了计算速度。实验结果显示：新方法有效地减轻了粒子退化和跟踪失效问题,降低了计算时间,提高了跟踪精度,能够同时满足三维人体运动跟踪精度和实时性的要求。     

基于二值掩码图像的粒子滤波目标跟踪快速算法

粒子滤波算法是进行运动目标跟踪的一种重要方法。针对传统粒子滤波算法在进行目标跟踪时存在的计算量大、实时性不足的问题,提出一种基于二值掩码图像的粒子滤波目标跟踪快速算法。该算法在传统粒子滤波算法的每个帧处理阶段产生二值掩码图像,再结合权重选择方法移除背景中权重较小的粒子,保留权重较大的重要粒子。提出的算法可以有效减少参与计算的粒子数目,节约算法的计算成本,从而提高目标跟踪的实时性。与传统粒子滤波算法进行比较,实验结果表明,提出的算法不仅能够有效地提高跟踪速度,而且跟踪结果的准确性和鲁棒性也有所增强。