One of the primary computer vision's tasks is object tracking. Object tracking is used in the vast majority of applications such as: video surveillance, car tracking (distance estimation), people detection and tracking, etc. The object trackers usually need some initialization step such as the initial object location, which can be provided manually or automatically by using object detector such as Viola and Jones detector or fast template matching. There are several major problems related to tracking:
Although the object tracking problem is present for years, it is still not solved, and there are many object trackers, the ones that are built for special purposes and generic ones.
The Kalman filter assumes linear motion model and Gaussian noise and returns only one hypothesis (e.g. the probable position of a tracked object). If the movements are rapid and unpredictable (e.g. leaf on a tree during windy day), the Kalman filter is likely to fail. The particle filter returns multiple hypotheses (each particle presents one hypothesis) and thus can deal with non-Gaussian noise and support non-linear models. Besides the object tracking where the state is a position vector (x, y), the state can be anything, e.g., shape of the model. This article will explain the main idea behind particle filter and will focus on their practical usage for object tracking along with samples.
Particle Filter - Main IdeaA particle filter is the generic algorithm for a function optimization where the solution search space is searched using particles (sampling). So what does this mean? In our case, each particle incorporates tests whether how it is likely that the object is at the position where the particle is. After the particles have been evaluated, the weights are assigned according to how good the particles are. Then the good particles are multiplied and the bad particles are removed through the re-sampling process. The next particle generation then predicts where the object might be. Then this generation is evaluated, and the cycle repeats.
Opposed to the Kalman filter the particle filter can model non-linear object motion because the motion model should not be written as a state transition matrix like in the Discrete Kalman filter. Moreover, the particle filter is fairly easy to understand, but there is a negative thing: the performance of the filter depends on the particles number where the higher number of particles will lead to a better estimate, but it is more costly. Nevertheless, the particle filter is largely used for generic function optimization including the object tracking.
The figure below shows the two main steps of the particle filter.
PredictPrediction is the first step which includes particle selection according to their weight resample, the next state transition (e.g. applying motion model) drift and applying noise diffuse.
Update (Correct)After the noisy measurement has been obtained, the update (correction) step begins. Each particle is evaluated and each particles' weight is updated according to obtained likelihood.
Now when you know the basics, it is time for real samples, but first the brief introduction to the implementation.
ImplementationThe particle filter is implemented as a number of extension methods for IEnumerable<TParticle> or IList<TParticle> where TParticle implements IParticle interface. Methods are implemented as extensions defined on particle collection (e.g. particle filter). This kind of implementation provides:
The class diagram below shows the implementation outline:
Class diagram. The implementation of the generic particle filter does not introduce any new classes. Instead, it implements a single particle as a lightweight interface and provides extension methods for particle collection (e.g. particle filter) defined in theParticleFilter class.
Assume we want to use a constant velocity model and the measurement model is the object's location (just as in figures above). The usage sample for this sample is shown below:
ParticleThe particle implements two main methods: drift and diffuse. As we do not incorporate any motion model, this method is empty. We diffuse particles by randomizing the current particle position. The code shown below omits some non-important implementation details.
class ColorParticle: IParticle
{
public double Weight { get; set; }
public PointF Position { get; set; }
//we do not have velocity (or something else), so nothing :)
public void Drift()
{ }
public void Diffuse()
{
//randomize the position a little bit
}
...
}Initialization
The most complex step is the initialization which includes particle implementation (drift and diffuse) and initialization. The shown initialization procedure scatters 1000 particles uniformly across an image.
//ColorParticle is the implementation of the particle of the introductory sample
List<ColorParticle> particleFilter = new List<ColorParticle>();
particleFilter.CreateParticles(1000, //particles' count
ColorParticle.FromArray, //convert arr => position (create from array)
new ISampleableDistribution<double>[] //position range
{
new UniformContinuousDistribution(0, imgSize.Width),
new UniformContinuousDistribution(0, imgSize.Height)
});Predict
The prediction step consists of only one method which, if there are no measurements, is executed repetitively without correction method. It incorporates resample, drift and diffuse method.
private void predict()
{
particleFilter = particleFilter.Predict();
}Update (correct)
Update (correction) method updates particles' weights according to their measurements.
private void update()
{
particleFilter.Update(measure);
}
private double measure(ColorParticle p)
{
//get Euclidean distance from the reference color
}Conclusion
The discrete particle filter is described for object tracking problem and its implementation in C#. Particle filter has many more purposes as it serves as generic optimization problem as it is shown in one of the included samples.
The source and sample code are the part of Accord.NET Extensions Framework, a framework that brings many advanced algorithms primarily for image processing, object detection and tracking, all packed as fluent extensions and simple and intuitive generics, so do not forget to take a peek :).
References HistoryRetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4