Quick links

Latest Matlab motion tracking software: [zip file] [gzip'ed tarball].

Ant image sequence (easy): [zip file] [gzip'ed tarball]
St. George sequence (hard): [zip file] [gzip'ed tarball]
Project synopsis: [pdf]

Author:         Fabian Wauthier          flw (at) cs.berkeley.edu (main contact)
Supervisor: Prof. Chris Williams     ckiw (at) inf.ed.ac.uk

Introduction

The aim of motion tracking is to detect and track moving objects through a sequence of images. Motion tracking is not only useful for monitoring activity in public places, but is becoming a key ingredient for further analysis of video sequences. Information about the location and identity of objects at different points in time (as summarised by the example images below) for instance is the basis of detecting unusual object movements (e.g. someone being mugged at an ATM) or coordinated activities (e.g. strategic plays in a football game). The two examples below show trajectories estimated from an ant-maze and an outdoor scene respectively.

Motion trajectories accumulated over a number of frames Motion trajectories accumulated over a number of frames

This page summarises a motion tracking project at the University of Edinburgh. Besides a brief synopsis and pointers to background reading, you'll find sample video sequences of tracked objects and Matlab code for use on your own sequences. For ease of use we also provide a prepackaged image sequence for download. The software should be particularly useful to biologists studying the behaviour of ants, mice or flies in controlled maze environments.

Object detection

Given an image sequence from a static camera, the first step is to discriminate moving foreground objects from the background. The approach used in this project constructs for each pixel of an image a distribution of the typical values it takes (i.e. a background model). The central notion is that the most frequent values of a pixel are likely to correspond to background imagery. By modelling pixels through parametrised distributions we capture increased sensor noise (for example at night) and repetitive background motion (for example waving tree branches) in a compact description.

Once the background model has been estimated, the classification of a pixel into background or foreground is based solely on the accumulated background model though outlier-detection: Pixels with values sufficiently different from the background distribution are labelled as foreground. By continually updating the background model of each pixel, one can adapt to gradual changes in lighting (for example due to changing cloud cover or sunrise and sunset) and changes in scene geometry (parking cars).
Input Output
The method used for this purpose resembles an on-line K-means algorithm. An example input image and the corresponding pixel labellings computed from a background model can be seen on the left where foreground pixels were labelled as white. The person crossing the street can be clearly seen. By lumping large connected foreground regions into blobs, foreground objects, such as the person seen crossing the street, can be identified. However, the left images also show that an additional foreground object was erroneously detected in the top right corner due to violent motion of the trees in the background. Such occasional mis-detections must be taken into account at later stages of the tracking algorithm.

Object tracking

The second step is to link a sequence of object blobs together across image frames (blob tracking). To achieve this, it is useful to describe each object blob by a set of attributes, for example its position, velocity and size, collectively called its state. Tracking the object's true position is done by tracking its state with a Kalman filter. This uses information from the current blob and the previous object state to create an estimate of the object's new state. The combination of previously estimated object dynamics and current measurements helps eliminate noise from blob measurements that would otherwise lead to erratic object tracking. As a simple example, knowing the previous position and velocity of a car allows us to give a rough estimate of its current position. When combining this estimate with additional information of its state, tracking accuracy can be overall improved.

Data association

In circumstances where several objects are being tracked simultaneously, it is paramount to avoid confusion of distinct objects, as Kalman filtering would otherwise fail. A schematic visualisation of the data association problem faced can be seen in the sequence below.

Time: t-1 Time: t Time: t+1
Time t-1 Time t Time t+1
Each circle signifies a blob which is tracked through frames from left to right. At the new input frame t+1, the identities of blobs are initially unknown and must be extrapolated from observed object dynamics of previous frames. Additional complications arise if objects can temporarily disappear (e.g. behind walls or cars) or if non-existent foreground objects are observed (as in the previous example). Hence, the central challenge of multiple hypothesis tracking is how to determine an appropriate association between blobs and Kalman filters while being robust against temporary occlusions and noise. We formulate the association task as a linear assignment problem which identifies the desired association as the one that minimises a summed assignment cost of pairings between blob observations and Kalman filters.

A well-known algorithm that solves the linear assignment problem and for which a C++ implementation is readily available was published by R. Jonker and A. Volgenant[2]. The cost function was chosen to ensure that the overall assignment is the most likely one while respecting matching constraints. Once the matching has been determined, multiple object tracking is a matter of updating each Kalman filter with its associated observation.

Sample videos

Choose one of the links below to view an demo image sequence and the output produced by the algorithm.

[Ant]    [PETS 2000]    [PETS 2001]    [St. George]

Software

The latest object tracking code can be downloaded in two formats: [zip file] [gzip'ed tarball]. All previous software releases are collected in the archive.

All code was written in Matlab with the exception of the C++ code for the Linear Assignment Problem which was made available by MagicLogic. Please review their copyright policy if you wish to use their code commercially.

References

  1. C. Stauffer and W. E. L. Grimson. Learning patterns of activity using real-time tracking. IEEE Transaction on Pattern Analysis and Machine Intelligence, 22(8):747-757, 2000.
  2. R. Jonker and A. Volgenant. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38(4):325-340, 1987.
    A C++ implementation of this algorithm was made available by MagicLogic.