Search

Extended objects generate a variable number of multiple measurements. In contrast with point targets, extended objects are characterized with their size or volume, and orientation. Multiple object tracking is a notoriously challenging problem due to complexities caused by data association. This paper develops a box particle filter (box PF) method for multiple extended object tracking, and for the first time, it is shown how interval-based approaches can deal efficiently with data association problems and reduce the computational complexity of the data association. The box PF relies on the concept of a box particle. A box particle represents a random sample and occupies a controllable rectangular region of nonzero volume in the object state space. A theoretical proof of the generalized likelihood of the box PF for multiple extended objects is given based on a binomial expansion. Next, the performance of the box PF is evaluated using a challenging experiment with the appearance and disappearance of objects within the area of interest, with real laser rangefinder data. The box PF is compared with a state-of-the-art particle filter with point particles. Accurate and robust estimates are obtained with the box PF, both for the kinematic states and extent parameters, with significant reductions in computational complexity. The box PF reduction of computational time is atleast 32% compared with the particle filter working with point particles for the experiment presented. Another advantage of the box PF is its robustness to initialization uncertainty.

Resulting from the synergy between the sequential Monte Carlo (SMC) method [1] and interval analysis [2], box particle filtering is an approach that has recently emerged [3] and is aimed at solving a general class of nonlinear filtering problems. This approach is particularly appealing in practical situations involving imprecise stochastic measurements that result in very broad posterior densities. It relies on the concept of a box particle that occupies a small and controllable rectangular region having a nonzero volume in the state space. Key advantages of the box particle filter (box-PF) against the standard particle filter (PF) are its reduced computational complexity and its suitability for distributed filtering. Indeed, in some applications where the sampling importance resampling (SIR) PF may require thousands of particles to achieve accurate and reliable performance, the box-PF can reach the same level of accuracy with just a few dozen box particles. Recent developments [4] also show that a box-PF can be interpreted as a Bayes? filter approximation allowing the application of box-PF to challenging target tracking problems [5].

This work presents sequential Bayesian detection and estimation methods for nonlinear dynamic stochastic systems using measurements affected by three sources of uncertainty: stochastic, set-theoretic and data association uncertainty. Following Mahler’s framework for information fusion, the paper develops the optimal Bayes filter for this problem in the form of the Bernoulli filter for interval measurements. Two numerical implementations of the optimal filter are developed. The first is the Bernoulli particle filter (PF), which turns out to require a large number of particles in order to achieve a satisfactory performance. For the sake of reduction in the number of particles, the paper also develops an implementation based on box particles, referred to as the Bernoulli Box-PF. A box particle is a random sample that occupies a small and controllable rectangular region of non-zero volume in the target state space. Manipulation of boxes utilizes the methods of interval analysis. The two implementations are compared numerically and found to perform remarkably well: the target is reliably detected and the posterior probability density function of the target state is estimated accurately. The Bernoulli Box-PF, however, when designed carefully, is computationally more efficient.

This paper proposes a technique for motion estimation of groups of targets based on evolving graph networks. The main novelty over alternative group tracking techniques stems from learning the network structure for the groups. Each node of the graph corresponds to a target within the group. The uncertainty of the group structure is estimated jointly with the group target states. New group structure evolving models are proposed for automatic graph structure initialization, incorporation of new nodes, unexisting nodes removal, and the edge update. Both the state and the graph structure are updated based on range and bearing measurements. This evolving graph model is propagated combined with a sequential Monte Carlo framework able to cope with measurement origin uncertainty. The effectiveness of the proposed approach is illustrated over scenarios for group motion estimation in urban environments. Results with challenging scenarios with merging, splitting, and crossing of groups are presented with high estimation accuracy. The performance of the algorithm is also evaluated and shown on real ground moving target indicator (GMTI) radar data and in the presence of data origin uncertainty.

In recent years particle filters have been applied to a variety of state estimation problems. A particle filter is a sequential Monte Carlo Bayesian estimator of the posterior density of the state using weighted particles. The efficiency and accuracy of the filter depend mostly on the number of particles used in the estimation and on the propagation function used to re-allocate weights to these particles at each iteration. If the imprecision, i.e. bias and noise, in the available information is high, the number of particles needs to be very large in order to obtain good performances. This may give rise to complexity problems for a real-time implementation. This kind of imprecision can easily be represented by interval data if the maximum error is known. Handling interval data is a new approach successfully applied to different real applications. In this paper, we propose an extension of the particle filter algorithm able to handle interval data and using interval analysis and constraint satisfaction techniques. In standard particle filtering, particles are punctual states associated with weights whose likelihoods are defined by a statistical model of the observation error. In the box particle filter, particles are boxes associated with weights whose likelihood is defined by a bounded model of the observation error. Experiments using actual data for global localization of a vehicle show the usefulness and the efficiency of the proposed approach.

This chapter presents a new approach combining the Bayesian framework with interval methods. When the system dynamics and measurement models have interval types of uncertainties, instead of point state estimates, guaranteed (interval) estimation is a promising approach. First, fundamental concepts from the interval analysis are introduced. Next, a Box Particle Filter (Box-PF) is presented and its theoretical derivation is given based on a mixture of uniform probability density functions. The efficiency of the Box-PF is significant compared with the generic sampling importance resampling particle Filter (SIR PF). With few particles the Box-PF can achieve the same estimation accuracy that the SIR PF achieves with thousands of particles. The performance of the proposed Box-PF is studied and results over examples both with simulated and real data are presented.

We present algorithms for tracking and reasoning of local traits in the subsystem level based on the observed emergent behavior of multiple coordinated groups in potentially cluttered environments. Our proposed Bayesian inference schemes, which are primarily based on (Markov chain) Monte Carlo sequential methods, include: 1) an evolving network-based multiple object tracking algorithm that is capable of categorizing objects into groups, 2) a multiple cluster tracking algorithm for dealing with prohibitively large number of objects, and 3) a causality inference framework for identifying dominant agents based exclusively on their observed trajectories.We use these as building blocks for developing a unified tracking and behavioral reasoning paradigm. Both synthetic and realistic examples are provided for demonstrating the derived concepts.

This paper proposes a sequential Monte Carlo filter (particle filter) for state and parameter estimation of dynamic systems. It is applied to the problem of extended object tracking in the presence of dense clutter. The unknown length of a stick-shape object is estimated in addition to the kinematic parameters. The kernel density estimation technique is utilised to approximate the joint posterior density of target state and static size parameters. The convolution particle filtering approach is validated on a Poisson model for the measurements, originating from the target and clutter. Examples illustrating the filter performance are presented. Simulation results show that the convolution particle filter provides accurate on-line tracking, with very good estimates both for the target kinematic states and for the parameters of the target extent.

This paper considers the challenging task of realtime extended object tracking using cluttered measurements from laser range scanners. The performance of the recently proposed Box Particle Filter (Box PF) algorithm is evaluated utilising real measurements from laser range scanners obtained within a prototype security system replicating an airport corridor. The problem is expressed as the joint estimation of both state and parameters of an extended target. Circularly and elliptically shaped targets are considered. Promising results are presented.

Large-scale traffic systems require techniques that are able to 1) deal with high amounts of data and heterogenous data coming from different types of sensors, 2) provide robustness in the presence of sparse sensor data, 3) incorporate different models that can deal with various traffic regimes, and 4) cope with multimodal conditional probability density functions (pdfs) for the states. Often, centralized architectures face challenges due to high communication demands. This paper develops new estimation techniques that are able to cope with these problems of large traffic network systems. These are parallelized particle filters (PPFs) and a parallelized Gaussian sum particle filter (PGSPF) that are suitable for online traffic management. We show how complex pdfs of the high-dimensional traffic state can be decomposed into functions with simpler forms and how the whole estimation problem solved in an efficient way. The proposed approach is general, with limited interactions, which reduce the computational time and provide high estimation accuracy. The efficiency of the PPFs and PGSPFs is evaluated in terms of accuracy, complexity, and communication demands and compared with the case where all processing is centralized.

This paper develops a novel approach for multi-target tracking, called box-particle intensity filter (box-iFilter). The approach is able to cope with unknown clutter, false alarms and estimates the unknown number of targets. Furthermore, it is capable of dealing with three sources of uncertainty: stochastic, set-theoretic and data association uncertainty. The box-iFilter reduces the number of particles significantly, which improves the runtime considerably. The low particle number enables this approach to be used for distributed computing. A box-particle is a random sample that occupies a small and controllable rectangular region of non-zero volume. Manipulation of boxes utilizes the methods from the field of interval analysis. Our studies suggest that the box-iFilter reaches an accuracy similar to a sequential Monte Carlo (SMC) iFilter but with much less computational costs.

This paper proposes a technique for group object motion estimation based on evolving graph networks. The main novelty over alternative group tracking techniques stems from learning the network structure for the group. An algorithm is proposed for automatic graph structure initialisation, incorporation of new nodes and unexisting nodes removal in parallel with the edge update. This evolving graph model is combined with the sequential Monte Carlo framework and its effectiveness is illustrated over a complex scenario for group motion estimation in urban environment. Results with merging, splitting and crossing of the groups are presented with high estimation accuracy.

This paper presents a new fusion strategy that mixes interval analysis techniques and particle filters for data fusion and state estimation purposes occurring in many robotic perception problems. The method requires a small number of "box particles". This, in fact, answers one of major problems when using particle filters techniques. We report the case study of a land vehicle localization problem and we make a comparison based on real data between the performance of a particle filter and the new developed strategy.

Over the last years, particle filters (PF) have attracted considerable attention in the field of nonlinear state estimation due to their relaxation of the linear and Gaussian restrictions in the state space model. However, for some applications, PF are not adapted for a real-time implementation. In this paper we propose a new method, called box particle filter (BPF), for dynamic nonlinear state estimation, which is based on particle filters and interval frameworks and which is well adapted for real time applications. Interval framework will allow to explain regions with high likelihood by a small number of box particles instead of a large number of particles in the case of PF. Experiments on real data for global localization of a vehicle show the usefulness and the efficiency of the proposed approach.

In this work, a novel approach to nonlinear non-Gaussian state estimation problems is presented based on mixtures of uniform distributions with box supports. This class of filtering methods, introduced in [1] in the light of interval analysis framework, is called Box Particle Filter (BPF). It has been shown that weighted boxes, estimating the state variables, can be propagated using interval analysis tools combined with Particle filtering ideas. In this paper, in the light of the widely used Bayesian inference, we present a different interpretation of the BPF by expressing it as an approximation of posterior probability density functions, conditioned on available measurements, using mixture of uniform distributions. This interesting interpretation is theoretically justified. It provides derivation of the BPF procedures with detailed discussions.