masterhead masterhead  masterhead

Target Tracking


Doing image processing at extreme frame rates puts strict requirements on the underlying algorithms. One key to achieve this is to exploit the parallelism inherent in many image processing problem. However, even if the problem itself is parallelizable, that is if it is possible to do the same computation simultaneously for many pixels, other aspects have to be taken into consideration. In particular, memory access patterns and cache strategies will have a huge impact on the performance, which in these scenarios often are bound by memory throughput. This implies that these sort of issues will have to be considered already when designing the algorithm. On the other hand, observing scene changes with a high frequency enables the possibility to exploit different aspects of the problem compared to just observing at regular frame rates.

The ability to follow an object in a sequence of images, refered to as object tracking, enables a range of applications in areas such as robotics, human computer interaction and augmented reality. In addition being able to do this at frame rates of 1000 fps enables exploiting tracking hardware designed for this sort of high speed tracking.

One approach to tracking is to find a local characteristic of the object and follow that. With this approach no concept of an object exists. This can lead to loss of tracking when objects drastically change appearance, and furthermore might give bad feedback to applications like the one presented here, where information about entire extent of the object is crucial. We therefore take an approach where the contours of the target object is tracked. This enables the tracked target to be treated as everything contained within its contour. When the target changes in appearance (see video) the object model gets updated with relevant information and the tracking adapts to this new appearance.

We adapt the problem to the linear memory layout in modern computers by introducing a polar coordinate space. We then let the contour move in and out along each row in this space, exploiting both cache coherency and parallelism due to the partial independence between rows. Our algorithm is able to keep up with a 1000 fps camera capturing images at VGA resolution on a regular Intel Corei7 processor.

Object (red) and current contour
estimate (blue). The blue circle indicates
the origin of the polar transform.
Image in polar space. Note that
radial lines in the original image
become horizontal in polar space.
The contour is propagated radially
and the direction is determined by
the local conformity to the models.


  1. Niklas Bergström, Masatoshi Ishikawa: 1 ms tracking of target boundaries using contour propagation, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'13), Proceedings pp. 2144-2151
  2. 奥村光平,奥寛雅,石川正俊: アクティブビジョンの高速化を担う光学的視線制御システム, 日本ロボット学会誌,Vol. 29,No. 2, pp.201-211 (2011)
Ishikawa Watanabe Laboratory, Department of Information Physics and Computing, Department of Creative Informatics,
Graduate School of Information Science and Technology, University of Tokyo
Ishikawa Watanabe Laboratory WWW admin:
Copyright © 2008 Ishikawa Watanabe Laboratory. All rights reserved.