Multi-dimensional visual tracking using scatter search particle filter

Multi-dimensional visual tracking (MVT) problems include visual tracking tasks where the system state is defined by a high number of variables corresponding to multiple model components and/or multiple targets. A MVT problem can be modeled as a dynamic optimization problem. In this context, we propose an algorithm which hybridizes particle filters (PF) and the scatter search (SS) metaheuristic, called scatter search particle filter (SSPF), where the optimization strategies from SS are embedded into the PF framework. Scatter search is a population-based metaheuristic successfully applied to several complex combinatorial optimization problems. The most representative optimization strategies from SS are both solution combination and solution improvement. Combination stage enables the solutions to share information about the problem to produce better solutions. Improvement stage makes also possible to obtain better solutions by exploring the neighborhood of a given solution. In this paper, we have described and evaluated the performance of the scatter search particle filter (SSPF) in MVT problems. Specifically, we have compared the performance of several state-of-the-art PF-based algorithms with SSPF algorithm in different instances of 2D articulated object tracking problem and 2D multiple object tracking. Some of these instances are from the CVBase’06 standard database. Experimental results show an important performance gain and better tracking accuracy in favour of our approach.     

A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems

Dynamic optimization problems challenge traditional evolutionary algorithms seriously since they, once converged, cannot adapt quickly to environmental changes. This paper investigates the application of memetic algorithms, a class of hybrid evolutionary algorithms, for dynamic optimization problems. An adaptive hill climbing method is proposed as the local search technique in the framework of memetic algorithms, which combines the features of greedy crossover-based hill climbing and steepest mutation-based hill climbing. In order to address the convergence problem, two diversity maintaining methods, called adaptive dual mapping and triggered random immigrants, respectively, are also introduced into the proposed memetic algorithm for dynamic optimization problems. Based on a series of dynamic problems generated from several stationary benchmark problems, experiments are carried out to investigate the performance of the proposed memetic algorithm in comparison with some peer evolutionary algorithms. The experimental results show the efficiency of the proposed memetic algorithm in dynamic environments.     

Unscented Kalman Filtering on Riemannian Manifolds

In recent years there has been a growing interest in problems, where either the observed data or hidden state variables are confined to a known Riemannian manifold. In sequential data analysis this interest has also been growing, but rather crude algorithms have been applied: either Monte Carlo filters or brute-force discretisations. These approaches scale poorly and clearly show a missing gap: no generic analogues to Kalman filters are currently available in non-Euclidean domains. In this paper, we remedy this issue by first generalising the unscented transform and then the unscented Kalman filter to Riemannian manifolds. As the Kalman filter can be viewed as an optimisation algorithm akin to the Gauss-Newton method, our algorithm also provides a general-purpose optimisation framework on manifolds. We illustrate the suggested method on synthetic data to study robustness and convergence, on a region tracking problem using covariance features, an articulated tracking problem, a mean value optimisation and a pose optimisation problem.     

A particle swarm optimization based memetic algorithm for dynamic optimization problems

Recently, there has been an increasing concern from the evolutionary computation community on dynamic optimization problems since many real-world optimization problems are dynamic. This paper investigates a particle swarm optimization (PSO) based memetic algorithm that hybridizes PSO with a local search technique for dynamic optimization problems. Within the framework of the proposed algorithm, a local version of PSO with a ring-shape topology structure is used as the global search operator and a fuzzy cognition local search method is proposed as the local search technique. In addition, a self-organized random immigrants scheme is extended into our proposed algorithm in order to further enhance its exploration capacity for new peaks in the search space. Experimental study over the moving peaks benchmark problem shows that the proposed PSO-based memetic algorithm is robust and adaptable in dynamic environments.     

多相关滤波自适应融合的鲁棒目标跟踪

目的 由于目标在复杂场景中可能会发生姿态变化、物体遮挡、背景干扰等情况,目标跟踪仍然是一个具有挑战性的课题。目前判别性相关滤波方法在目标跟踪问题上获得了成功而又广泛的应用。标准的相关滤波方法基于循环偏移得到大量训练样本,并利用快速傅里叶变换加速求解滤波器,使其具有很好的实时性和鲁棒性,但边界偏移带来的消极的训练样本降低了跟踪效果。空间正则化的相关滤波跟踪方法引入空间权重函数,增强目标区域的滤波器作用,在增大了目标搜索区域的同时,也增加了计算时间,而且对于目标形变不规则,背景相似的情景也会增强背景滤波器,从而导致跟踪失败。为此,基于以上问题,提出一种自适应融合多种相关滤波器的方法。方法 利用交替方向乘子法将无约束的相关滤波问题转化为有约束问题的两个子问题,在子问题中分别采用不同的相关滤波方法进行求解。首先用标准的相关滤波方法进行目标粗定位,进而用空间正则化的相关滤波跟踪方法进行再定位,实现了目标位置和滤波模板的微调,提高了跟踪效果。结果 本文算法和目前主流的一些跟踪方法在OTB-2015数据集中100个视频上,以中心坐标误差和目标框的重叠率为评判标准进行了对比实验,本文算法能较好地处理多尺度变化、姿态变化、背景干扰等问题,在CarScale、Freeman4、Girl等视频上都表现出了最好的跟踪结果;本文算法在100个视频上的平均中心坐标误差为28.55像素,平均目标框重叠率为61%,和使用人工特征的方法相比,均高于其他算法,与使用深度特征的相关滤波方法相比,平均中心坐标误差高了6像素,但平均目标框的重叠率高了4%。结论 大量的实验结果表明,在目标发生姿态变化、尺度变化等外观变化时,本文算法均具有较好的准确性和鲁棒性。     

A variable neighborhood search particle filter for bearings-only target tracking

In this paper a novel filtering procedure that uses a variant of the variable neighborhood search (VNS) algorithm for solving nonlinear global optimization problems is presented. The base of the new estimator is a particle filter enhanced by the VNS algorithm in resampling step. The VNS is used to mitigate degeneracy by iteratively moving weighted samples from starting positions into the parts of the state space where peaks and ridges of a posterior distribution are situated. For testing purposes, bearings-only tracking problem is used, with two static observers and two types of targets: non-maneuvering and maneuvering. Through numerous Monte Carlo simulations, we compared performance of the proposed filtering procedure with the performance of several standard estimation algorithms. The simulation results show that the algorithm mostly performed better than the other estimators used for comparison; it is robust and has fast initial convergence rate. Robustness to modeling errors of this filtering procedure is demonstrated through tracking of the maneuvering target. Moreover, in the paper it is shown that it is possible to combine the proposed algorithm with an interacted multiple model framework.     

High performance memetic algorithm particle filter for multiple object tracking on modern GPUs

This work presents an effective approach to visual tracking using a graphics processing unit (GPU) for computation purposes. In order to get a performance improvement against other platforms it is convenient to select proper algorithms such as population-based ones. They expose a parallel-friendly nature needing from many independent evaluations that map well to the parallel architecture of the GPU. To this end we propose a particle filter (PF) hybridized with a memetic algorithm (MA) to produce a MAPF tracking algorithm for single and multiple object tracking problems. Previous experimental results demonstrated that the MAPF algorithm showed more accurate tracking results than the standard PF, and now we extend those results with the first complete adaptation of the PF and the MAPF for visual tracking to the NVIDIA CUDA architecture. Results show a GPU speedup between 5×–16× for different configurations.     

Robust state estimator design for uncertain linear systems using optimization techniques

The estimation of state variables of dynamic systems in noisy environments has been an active research field in recent decades. In this way, Kalman filtering approach may not be robust in the presence of modeling uncertainties. So, several methods have been proposed to design robust estimators for the systems with uncertain parameters. In this paper, an optimized filter is proposed for this problem considering an uncertain discrete-time linear system. After converting the subject to an optimization problem, three algorithms are used for optimizing the state estimator parameters: particle swarm optimization (PSO) algorithm, modified genetic algorithm (MGA) and learning automata (LA). Experimental results show that, in comparison with the standard Kalman filter and some related researches, using the proposed optimization methods results in robust performance in the presence of uncertainties. However, MGA-based estimation method shows better performance in the range of uncertain parameter than other optimization methods.     

基于稀疏表达的多示例学习目标追踪算法

追踪目标在经历较大姿势变化时,会导致追踪目标偏移甚至丢失。为此,提出一种基于稀疏表达的多示例学习目标追踪算法。联合多示例学习与稀疏表达方法,将目标物体的局部稀疏编码作为多示例学习的训练数据,通过学习正负样本的局部稀疏编码获得一个多示例学习的分类器,分类的结果与粒子滤波框架相结合,估计目标在整个视频序列中的运动状态。实验结果表明,该算法稳定性较好,与增量学习追踪算法、范式学习追踪算法和多示例学习追踪算法相比,其中心位置误差率减少30%以上。     

State estimation of nonlinear dynamic systems using weighted variance-based adaptive particle swarm optimization

New heuristic filters are proposed for state estimation of nonlinear dynamic systems based on particle swarm optimization (PSO) and differential evolution (DE). The methodology converts state estimation problem into dynamic optimization to find the best estimate recursively. In the proposed strategy the particle number is adaptively set based on the weighted variance of the particles. To have a filter with minimal parameter settings, PSO with exponential distribution (PSO-E) is selected in conjunction with jDE to self-adapt the other control parameters. The performance of the proposed adaptive evolutionary algorithms i.e. adaptive PSO-E, adaptive DE and adaptive jDE is studied through a comparative study on a suite of well-known uni- and multi-modal benchmark functions. The results indicate an improved performance of the adaptive algorithms relative to original simple versions. Further, the performance of the proposed heuristic filters generally called adaptive particle swarm filters (APSF) or adaptive differential evolution filters (ADEF) are evaluated using different linear (nonlinear)/Gaussian (non-Gaussian) test systems. Comparison of the results to those of the extended Kalman filter, unscented Kalman filter, and particle filter indicate that the adopted strategy fulfills the essential requirements of accuracy for nonlinear state estimation.     

Evolutionary decision-makings for the dynamic weapon-target assignment problem

The dynamic weapon-target assignment (DWTA) problem is an important issue in the field of military command and control. An asset-based DWTA optimization model was proposed with four kinds of constraints considered, including capability constraints, strategy constraints, resource constraints and engagement feasibility constraints. A general “virtual” representation of decisions was presented to facilitate the generation of feasible decisions. The representation is in essence the permutation of all assignment pairs. A construction procedure converts the permutations into real feasible decisions. In order to solve this problem, three evolutionary decision-making algorithms, including a genetic algorithm and two memetic algorithms, were developed. Experimental results show that the memetic algorithm based on greedy local search can generate obviously better DWTA decisions, especially for large-scale problems, than the genetic algorithm and the memetic algorithm based on steepest local search.     

Hybrid three-dimensional camera pose estimation using particle filter sensor fusion

To properly align objects in the real and virtual worlds in an augmented reality (AR) space it is essential to keep tracking the camera's exact three-dimensional position and orientation (camera pose). State-of-the-art analysis shows that traditional vision-based or inertial sensor-based solutions are not adequate when used individually. Sensor fusion for hybrid tracking has become an active research direction during the past few years, although how to do it in a robust and principled way is still an open problem. In this paper, we develop a hybrid camera pose-tracking system that combines vision and inertial sensor technologies. We propose to use the particle filter framework for the sensor fusion system. Particle filters are sequential Monte-Carlo methods based upon a point mass (or 'particle') representation of probability densities, which can be applied to any state space model and which generalize the traditional Kalman filtering methods. We have tested our algorithm to evaluate its performance and have compared the results obtained by the particle filter with those given by a classical extended Kalman filter. Experimental results are presented     

Improving fuzzy cognitive maps learning through memetic particle swarm optimization

Fuzzy cognitive maps constitute a neuro-fuzzy modeling methodology that can simulate complex systems accurately. Although their configuration is defined by experts, learning schemes based on evolutionary and swarm intelligence algorithms have been employed for improving their efficiency and effectiveness. This paper comprises an extensive study of the recently proposed swarm intelligence memetic algorithm that combines particle swarm optimization with both deterministic and stochastic local search schemes, for fuzzy cognitive maps learning tasks. Also, a new technique for the adaptation of the memetic schemes, with respect to the available number of function evaluations per application of the local search, is proposed. The memetic learning schemes are applied on four real-life problems and compared with established learning methods based on the standard particle swarm optimization, differential evolution, and genetic algorithms, justifying their superiority.     

Multi-Camera Tracking with Adaptive Resource Allocation

Sensor fusion for object tracking is attractive since the integration of multiple sensors and/or algorithms with different characteristics can improve performance. However, there exist several critical limitations to sensor fusion techniques: (1) the measurement cost increases typically as many times as the number of sensors, (2) it is not straightforward to measure the confidence of each source and give it a proper weight for state estimation, and (3) there is no principled dynamic resource allocation algorithm for better performance and efficiency. We describe a method to fuse information from multiple sensors and estimate the current tracker state by using a mixture of sequential Bayesian filters (e.g., particle filter)—one filter for each sensor, where each filter makes a different level of contribution to estimate the combined posterior in a reliable manner. In this framework, multiple sensors interact to determine an appropriate sensor for each particle dynamically; each particle is allocated to only one of the sensors for measurement and a different number of particles is assigned to each sensor. The level of the contribution of each sensor changes dynamically based on its prior information and relative measurement confidence. We apply this technique to visual tracking with multiple cameras, and demonstrate its effectiveness through tracking results in videos.     

基于混合粒子PHD滤波的多目标视频跟踪

针对可变数目多目标视频跟踪,粒子滤波不能持续维持目标的多模态分布问题,本文提出一种混合粒子概率假设密度(PHD)滤波的多目标视频跟踪算法.该算法首先用K-means算法对粒子进行空间分布聚类,给各粒子群附加身份标签,使各粒子群分别对应混合粒子滤波的各分量,采用相互独立的各分量粒子滤波跟踪各目标,这样提高了目标状态估计的准确性,也能有效维持各目标的多模态分布.实验结果表明,该算法能有效处理新目标出现、合并、分离等多目标跟踪问题.     

Switching particle filters for efficient visual tracking

In this article, we propose a new particle filtering scheme, called a switching particle filter, which allows robust and accurate visual tracking under typical circumstances of real-time visual tracking. This scheme switches two complementary sampling algorithms, Condensation and Auxiliary Particle Filter, in an on-line fashion based on the confidence of the filtered state of the visual target. The accuracy and robustness of the switching scheme were evaluated using real visual tracking experiments as well as computer simulations. Furthermore, we demonstrate through visual tracking experiments that our scheme not only outperforms existing particle filters but also assists on-line learning of target dynamics.     

利用多特征混沌粒子滤波的视觉目标跟踪方法

随着摄像终端的增多以及自动视频分析需求量的增大,针对视频序列中存在突然运动、遮挡、运动模糊等干扰因素时传统视觉目标跟踪方法很难获得鲁棒性高、精确稳定的目标跟踪的问题,提出了利用多特征混沌粒子滤波的视觉目标跟踪方法。首先,基于非线性动力学预测进行混沌建模,利用混沌映射的梯度优化函数来搜索状态空间以找到参考轨迹;然后设计了一种用于视觉跟踪的混沌粒子滤波器,并改进运动表观模型,引入颜色、纹理和深度的特征完善滤波器的性能;最后,将多特征混沌粒子滤波器与其他视觉目标跟踪方法应用于VOT17和TB 数据集进行对比分析,以论证该方法的准确性。结果表明,提出的多特征混沌粒子滤波方法显著减少了粒子数量、搜索空间和滤波器发散,其精度高出其他方法约10%,在突然运动、遮挡和运动模糊等情况下整体性能优于其他几种对比方法。     

Comparison of stochastic filtering methods for 3D tracking

In the recent years, the 3D visual research has gained momentum with publications appearing for all aspects of 3D including visual tracking. This paper presents a review of the literature published for 3D visual tracking over the past five years. The work particularly focuses on stochastic filtering techniques such as particle filter and Kalman filter. These two filters are extensively used for tracking due to their ability to consider uncertainties in the estimation. The improvement in computational power of computers and increasing interest in robust tracking algorithms lead to increase in the use of stochastic filters in visual tracking in general and 3D visual tracking in particular. Stochastic filters are used for numerous applications in the literature such as robot navigation, computer games and behavior analysis. Kalman filter is a linear estimator which approximates system's dynamics with Gaussian model while particle filter approximates system's dynamics using weighted samples. In this paper, we investigate the implementation of Kalman and particle filters in the published work and we provide comparison between these techniques qualitatively as well as quantitatively. The quantitative analysis is in terms of computational time and accuracy. The quantitative analysis has been implemented using four parameters of the tracked object which are object position, velocity, size of bounding ellipse and orientation angle.     

嵌入卡尔曼预测器的粒子滤波目标跟踪算法*

针对经典的粒子滤波视频目标跟踪算法进行粒子传播采用随机游走的方式,以及传统颜色直方图无法反映目标空间特征的问题,提出了一种改进的基于颜色的粒子滤波目标跟踪算法。该算法在统计目标二阶颜色直方图的基础上,获得粒子的观察概率密度函数,利用卡尔曼滤波确定粒子动态传播模型中的确定性漂移部分,使粒子状态估计值分布更精确地趋向目标的概率分布,大大提高了粒子的利用效率。实验表明,该改进算法的性能优于经典基于单一颜色特征的粒子滤波算法。     

Improving Combinatorial Optimization Algorithms through Record Keeping in Constructive Multistart Search

Constructive multistart search algorithms are commonly used to address combinatorial optimization problems; however, constructive multistart search algorithm performance is fundamentally affected by two factors: (i) The choice of construction algorithm utilized and (ii) the rate of state space search redundancy. Construction algorithms are typically specific to a particular combinatorial optimization problem; therefore, we first investigate construction algorithms for iterative hill climbing applied to the traveling salesman problem and experimentally determine the best performing algorithms. We then investigate the more general problem of utilizing record‐keeping mechanisms to mitigate state space search redundancy. Our research shows that a good choice of construction algorithm paired with effective record keeping significantly improves the quality of traveling salesmen problem solutions in a constant number of state explorations. Particularly, we show that Bloom filters considerably improve time performance and solution quality for iterative hill climbing approaches to the traveling salesman problem.