Tuesday, 2 August 2016

Particles explained using Gifs!!

Over the past few months, I have been reading, understanding and implementing a number of existing algorithms in Computer Vision domain. Implementing particles and particle based algorithms have really had me excited and almost on the edge of my seat. One may ask what makes particles so interesting?? Let me try to get the concept through.

Particles, just like most existing algorithms in computer science, are inspired by nature. Have you ever seen a beam of sunlight coming through a window and illuminate a bunch of floating particles (impossible in London though I have seen it before)? When you see these tiny particles, you notice that they are suspended in air and that it's very difficult to predict their motion unless you disturb the surrounding air. This simple concept is vital for many computer algorithms that model motion/dynamics of an object.

Particles, along with their randomness, can be simulated inside a computer program. The simplest of such algorithm is called Random Walk, where a particle is modelled with its current position/state alone and a random displacement/jump determines its next position in time. Here I have shown one Random Walk particle:

A Single Random Walk Particle

Particles like the one shown above can coexist without disturbing each other. Below I show 20 particles with Random Walk:

Multiple Random Walk Particles

The above-illustrated particles only have information regarding their current position, where they go about random jumps at successive time intervals. We can further model the particles by adding additional attributes such as velocity, acceleration and changes in certain characteristics of the modelling dynamics. These additional attributes form the basis of particle-based models, such as particle filter and particle swarm optimisation. 

Let us now examine how the particles would behave if we model them using, in addition to position, their velocity. We will see how these particles go about dynamic model updates with induced random Brownian motion. Here is a single particle with modelled velocity parameter. 

A Single Particle with Velocity Parameter and Dynamical Model update

We quickly notice that now the updates are not random position jump but instead are based on a dynamical model with induced randomness in the velocity parameters (which makes the particles go slow/fast and change direction). Furthermore, as done previously, we can increase the number of particles and let them coexist in the same plane.

20 Particles with Velocity Parameters and randomness induced through Dynamical Model updates

By now you might be wondering, what's so special about this? Why use particles? This is just a way of doing simple visualisation?? Wait! The best part comes now.

You remember how the suspended particles illuminated by a sunbeam can be disturbed by a puff of air? We can do exactly the same with these particles, and additionally, reward the particles that behave the way we want them to behave. This concept is known as survival of the fittest.

Consider an object moving as depicted in the following gif (red square representing the object location):

An example object motion

Now consider rewarding the particles that behave in a similar way as this object and penalizing the particles that do not follow the motion of the object. In the case of the particle filter, we 'filter' the particles that best describe the objects motion. This can be based on a simple cost function. However, for simplicity, I will not get into the mathematical details. Here is cool gif instead :D

Simple Particle Filter Visualization, shows 250 particles used to model an object's motion

Here you can see that the model starts off with a number of different particles, however it quickly converges to use the children of a few particles (children particles represented as the same color as their parent particles). We can see that when such partilces are introduced into a competetive situation, they strive to survive by being the best description of the object's motion. In theory, we can use this same concept to model different complex high-dimensional representation describing both the internal and the external characteristics of an object. 

This behaviour of particles astonishes me a lot, as all we did was introduce some competition and all the particles started 'behaving' a certain way.