Tracking with Particle Filter for High-dimensional Observation and State Spaces

By Séverine Dubuisson

This title concerns the use of a particle filter framework to track objects defined in high-dimensional state-spaces using high-dimensional observation spaces.  Current tracking applications require us to consider complex models for objects (articulated objects, multiple objects, multiple fragments, etc.) as well as multiple kinds of information (multiple cameras, multiple modalities, etc.). This book presents some recent research that considers the main bottleneck of particle filtering frameworks (high dimensional state spaces) for tracking in such difficult conditions.

• Language: English
• Publisher: Wiley
• Release date: Jan 5, 2015
• ISBN: 9781119054054

Book preview

Introduction

With the progress made in the domains of electronics and microelectronics, the acquisition of video sequences became a task of particular triviality. Hence, in computer vision, algorithms working with video sequences have undergone considerable development over the past few years [SZE 10]. Skimming through a book dedicated to computer vision, written 30 years ago [BAL 82], we note that the notion of movement is discussed nearly in terms of approximation: here, the issue was detecting movement, rather than analyzing it. In particular, analysis of the optical flow [BAR 94], very popular at the time, only allowed characterizing temporal changes within the sequence. Little by little, with the rapid improvement of sensor quality and therefore of the resolution of the images they provided, as well as computer processing power and memory, it became possible, perhaps essential, to analyze movement in addition to detecting it: where does it come from? What behavior does it reflect? Hence, new algorithms made their appearance [SHI 94], their purpose being to detect and to follow entities in a video sequence. These are grouped under the name of tracking algorithms. Today, tracking single and multiple objects in video sequences is one of the major themes of computer vision. There are in fact many practical applications, notably in human–machine interaction, augmented reality, traffic control, surveillance, medical or biomedical imagery and even interactive games. The diversity of the problems to solve, as well as computing challenges created by object tracking in video sequences, motivates an increasing amount of research every year. Thus, in the year 2012 alone, in three major computer vision conferences (IEEE Conference on Computer Vision and Pattern Recognition (CVPR), European Conference on Computer Vision (ECCV) and British Machine Vision Conference (BMVC)), three workshops and two tutorials were dedicated to tracking; we can even mention the PETS workshop (International Workshop on Performance Evaluation of Tracking and Surveillance), which suggests a competition around tracking every two years. Furthermore, databases are increasingly available to allow researchers to compare their results [SIG 10a, WU 13]¹. The intense research activity around object tracking in video sequences is explained by the large amount of challenges that it undertakes. Indeed, it requires efficiently extracting the information related to the object or objects to track from the images, modeling it to obtain a representation that is both precise and compact and solving the compromise between tracking quality and efficiency. It is then required to be able to create temporal links between the object instances in each time step, while managing the occasional appearances and disappearances of objects on the scene. Finally, it is sometimes necessary to extract meta-data to respond to the needs of a specific application (behavioral analysis, detection of an event, etc.). In addition to these difficulties, there are those induced by the state of the object (appearance and deformation), the variations of the illumination of the scene, the noise present in the images, object occlusion, etc. Hence, object tracking reveals itself as a very complex process, especially given the ever-growing requirements in terms of tracking quality and processing speed in practical applications.

Over the last few years, sequential Monte Carlo methods [DOU 01, GOR 93, ISA 98a], better known as particle filters, became the algorithm for visual tracking par excellence. Their aim is to estimate the density of the filtering that links the states of the tracked objects to previous and current observations by approximating it using a weighted sample. Outside of the simplicity of their implementation, these approaches are capable of maintaining multiple hypotheses over time, which makes them robust to the challenges of visual tracking. Additionally, given their probabilistic nature, their very generic formalism makes it possible to consider complex modeling for the available objects and observations, whose densities could be non-parametric and/or multimodal. Nevertheless, their use requires making sure to stay within their mathematical framework, which is rigorous in spite of its simplicity. Moreover, we need to make sure that algorithmic costs remain reasonable (by incorporating, for example, independence hypotheses when they are justifiable). We positioned ourselves naturally in this methodological context, particularly by noting that some of the primary advantages offered by particle filtering cannot, at the current time, be used without making a certain number of often simplifying hypotheses. Specifically, if maintaining multiple hypotheses over time presents a real advantage to particle filtering, the minimal amount to maintain a good approximation of the filtering density is as high as the chosen data model leads to a high-volume representation. This results in serious problems once we attempt to refine the representation by integrating, for example, all the richness of information that is supplied by the sensors.

The goal of this book is to present the various contributions related to managing large state and observation representation spaces, which we consider to be one of the major challenges of particle filtering today. We distinguished three primary axis that guided the research and will be the subject of Chapters 2 through 4.

The first axis concerns the choice of the data model in order to lighten the representation, as well as accelerate its extraction. The work on this axis is essential to simplifying the calculations related to the estimation by particle filtering. Indeed, in order to be solved in a robust and targeted manner, current tracking problems require exploiting a multitude of available informations/observations, whose quality is constantly improving. Therefore, this requires increasingly finer descriptions of the dynamic scene that is being processed, which have the tendency to put considerable weight on calculations. Today, however, there are reliable and efficient techniques for data extraction that allow better exploitation of image information, they are not necessarily appropriate to the case of particle filtering and its multihypothesis representation, as they lead to repeating calculations, which may be disastrous for the efficiency of the filter. Hence, histograms are a widely used representation model, however, their extraction can quickly become a bottleneck for the filter response time, so it is appropriate to find methods that are appropriate for their extraction. The size of the spaces that we are working on has a significant influence on the response times, and being able to combine a set of characteristics, observations, information and to supply a model described in less space is an equally essential task, undertaken by numerous researchers. As we will see later, efficient combinations can be made either during the correction precess, which can be considered as a posteriori fusion, or be integrated directly to the tracking process (propagation and correction).

Several suggested theoretical and/or algorithmic solutions were able to obtain either a significant decrease in the processing time of likelihood functions, notably with optimized histogram extractions, or original models of classical tracking problems, such as deformation of the object over time, its multiple possible representations (appearances, modalities and fragments) and even the detection of objects (new or known) between two images.

The second axis concerns the exploration of the state space. Indeed, the particle filter features a hypothesis (particle) propagation phase, aiming to diffuse hypothesis toward areas with high likelihood, where they will be attributed a high weight during the first correction stage. When the state space is large, detecting areas with high likelihood turns out to be difficult, as exhaustive exploration of the space requires multiplying the number of hypotheses, which is impossible within reasonable processing times. This problem can be solved in two different ways. The first solution constitutes a primary research axis and consists of choosing the areas of the space to explore, which we call focusing. Hence, we can maintain a reasonable number of hypothesis, while smartly exploring the areas in which they will be propagated, areas with assumed high likelihood. This can be done either through detection before propagation (detect-before-track), or by defining dedicated proposition functions. It is this latter solution that we chose to develop in this book and that consists of decomposing the state space into subspaces of smaller sizes, that can be processed with few hypothesis.

We suggested several approaches that allow better focusing within the state space and, therefore, accelerate the process of tracking by particle filtering process. Two types of contributions dedicated to multiobject tracking allowed us not to have to process all the possible combinations associating measures with objects. The first type aims to, first of all, model a proposition function allowing the propagation of particles only in areas where movement was detected in advance, and which are seen as measurements, and then to classify these particles by associating them with objects on the scene. The second type takes into account the past dynamics of the objects and suggests a data association model that is very unconstrained, as it depends on few parameters. These models allow simply calculating the association probabilities between the measurements and objects. We will show that it is equally possible to input fuzzy spatial information into the particle filter. This allowed modeling of a new proposition function taking into account not only the current observation, but also the history of fuzzy spatial relations that characterized the past trajectories of the objects. The result allows considerably more flexible and better adapted tracking of sudden changes in trajectory or form. The appeal of this type of modeling is shown through various applications, such as object tracking, by managing erratic movements, multiobject tracking, by taking into account the case of object occlusion and finally multiform tracking, by taking into account deformable objects.

As the previous axis, the third one aims to make the exploration of large state spaces possible in practice. However, here we are no longer looking to work with the entire space whose exploration hyper-volume we reduced. Rather, we suggest decomposing it into subspaces of smaller sizes, in which calculations can be made within reasonable times, as they allow estimating distributions with fewer parameters than those required in the whole space. Hence, the latter is defined as a joint space. In this book, we are interested in non approximated decomposition methods, that is methods that guarantee asymptotically that the particles sample correctly the filtering distribution over the whole space. Thus, these methods do not make any simplifying hypothesis and only exploit the independences existing in the tracking problem. Among these techniques, partitioned sampling is used a lot today, although it has several limits. Indeed, this technique sequentially covers every subspace in order to construct, progressively, all the particles on the joint space (whole space), which can create problems if the order that the subspaces are processed in is completely arbitrary: if the sub-hypothesis made in the first subspace is incorrect, it will contribute to diminish the global score of the hypothesis as a whole, even if other sub-hypotheses are correct. Thus, the quality of the tracking will be low.

There are contributions that allowed us to solve this problem. First is the possibility to add the order in which objects need to be processed to the estimation process. This order is estimated sequentially, at the same time as the states of the objects, which allows taking the least reliable objects into account for tracking last. We can also exploit the conditional independences intrinsic to the problem of tracking (without making abusive hypothesis). This naturally leads to using dynamic Bayesian networks, rather than Markov chains, in order to model the filtering process. The exploitation of independence properties of these networks allowed us to develop a new method for permuting certain subsamples of subparticles that allow better estimations of the filtering density models, while guaranteeing that the estimated density remains unchanged. This method leads to reducing not only tracking errors, but also calculation times. This idea of permutation is exploited to suggest a new resampling method, which also allows us to significantly improve tracking.

The structure of this book is as follows. In Chapter 1, we will present the theoretical elements that are necessary to understand particle filtering. We will then explain how this methodology is used in the context of visual tracking, particularly the fundamental points to consider. This will eventually allow us to describe several current limits and challenges of tracking by particle filtering and, thus, justify our scientific position. Chapter 2 presents contributions related to modeling and extracting the data to process, as well as the choice for its representation to simplify, and thereby accelerating the calculations. In Chapter 3, we describe several contributions that allow exploring the state space by focusing on certain specific areas, considered more interesting than others. Chapter 4 shows, through certain works, how to decompose the state space into subspaces in which calculations are possible. Finally, we suggest a conclusion and an opening on the future of tracking, specifically by particle filtering, in Chapter 5.

1 A non-exhaustive list is available at http://clickdamage.com/sourcecode/cv_datasets.php.

1

Visual Tracking by Particle Filtering

1.1. Introduction

The aim of this introductory chapter is to give a brief overview of the progress made over the last 20 years in visual tracking by particle filtering. To begin (section 1.2), we will present the theoretical elements necessary for understanding particle filtering. Thus, we will first introduce recursive Bayesian filtering, before giving the outline of particle filtering. For more details, in particular theorem demonstrations and convergence studies, we invite the reader to refer to more advanced studies [CHE 03b, DOU 00b, GOR 93]. We will then explain how particle filtering is used in visual tracking in video sequences. Although the literature is abundant on this subject and evolving very fast, it is impossible to give a complete overview of this subject. Next, section 1.3 presents certain limits of particle filtering. Toward the end, we specify our scientific position in section 1.4 and the methodological axes that allow a part of these problems to be solved. Finally, section 1.5 gives the current state of the main large families of approaches that are concerned with managing large-sized state and/or observation spaces in particle filtering.

1.2. Theoretical models

1.2.1. Recursive Bayesian filtering

Recursive Bayesian filtering [JAZ 70] aims to approximate the state of a hidden Markov process, which is observed through an observation equation. Let {x0:t} = {x0, . . . , xt} be this process, where xt is the state vector, yt the observation at instant t and the two models:

[1.1]

The first equation is the state equation, with the state transition function ft between the instants t – 1 and t, and the second is the observation equation, giving the measurement of the state through an observation function gt. ut and vt are independent white noises.

All information necessary for approximating x0:t is contained in the a posteriori density, also known as the filtering density, p(x0:t|y1:t), where y1:t = {y1,y2, . . . ,yt}, in which we can prove, by applying the definition of conditional probabilities, that it follows the following recursive equation for a known [CHE 03b] t ≥ 1 (p(x0):

[1.2]

Under the Markov hypothesis, p(yt|y1:t–1,x0:t) = p(yt|xt) (the observations at different instants are independent between themselves given the states and do not depend on the state at the current instant) and p(xt|x0:t–1, y1:t–1) = p(xt|xt–1) (the current state only depends on the