Active Search for Real-Time Vision

Andrew J. DavisonICCV 2005 · OpenReview

Abstract

In most cases when information is to be extracted from an image, there are priors available on the state of the world and therefore on the detailed measurements which are obtained. While such priors are commonly combined with the actual measurements via Bayes' rule to calculate posterior probability distributions on model parameters, their additional value in guiding efficient image processing has almost always been overlooked. This paper uses Shannon information theory to analyse the fundamental value of measurements using mutual information scores in absolute units of bits. We compare these measurement values with the computational cost of the image processing required to obtain them, putting on a firm footing principles of 'active search' for efficient guided image processing.

Introduction

Most computer vision algorithms follow a "bottom-up" approach, scanning entire images for features like corners or edges before attempting to interpret them. In real-time systems, such as robotic trackers, this is computationally wasteful. If a system already has a rough idea of where an object is, scanning the whole image is unnecessary. This paper addresses the lack of a rigorous theoretical foundation for "active search"—the process of mathematically determining which specific pixel-level measurements are worth the time it takes to compute them.

Methodology: Information as Currency

The author bridges the gap between Bayesian estimation and Shannon Information Theory by using Mutual Information (MI) to quantify how much a specific feature measurement will reduce the uncertainty of an object's state (e.g., its position and orientation).

Gaussian Framework and Efficiency

By assuming that uncertainty can be modeled as a multi-variate Gaussian distribution, the author derives a closed-form solution for MI. This makes it computationally feasible to predict the "value" of a measurement—measured in bits—before performing any image processing. Using bits as a universal metric allows for the direct comparison of disparate feature types, such as 2D points and 1D edge gradients.

Predicted uncertainty regions (blue) versus actual measurements (red) during the tracking process.

The paper introduces a "Value vs. Cost" trade-off, defining efficiency as the ratio of Mutual Information to the computational cost (proportional to the search area in pixels). This ensures the system prioritizes "efficient" features—those that provide significant information for minimal effort—rather than just the most informative ones.

Key Results: Uncertainty Collapse

The effectiveness of this approach is demonstrated through simulations of a 2D object tracking task. The system uses a full matrix of MI scores to identify and avoid redundant features, ensuring that measuring one feature doesn't "double-count" information already provided by another nearby feature.

The "Uncertainty Collapse" sequence: (a) initial state, (b) after measuring feature 11, (c) after measuring feature 1, and (d) after measuring feature 5. Note the rapid reduction in search ellipses.

As shown in the sequence above, selecting features based on MI leads to a dramatic and rapid reduction in the "search ellipses" (uncertainty bounds). In one example, an efficiency-based strategy achieved a similar state estimate to exhaustive methods while reducing the computational cost from 1687 operations to just 657. Furthermore, active search scales well: as frame rates increase, priors become more accurate, further reducing search regions and processing time.

Discussion and Limitations

While the Gaussian assumption provides a robust mathematical framework, it does not account for outliers or mismatches. The author suggests moving toward a "Mixture of Gaussians" model to handle multiple hypotheses. Furthermore, in extremely high-speed systems, the $O(N^2)$ cost of calculating the Mutual Information matrix itself must be considered against the savings in image processing. Future work may explore hardware-optimized implementations to mitigate this overhead.

Summary updated

Abstract

In most cases when information is to be extracted from an image, there are priors available on the state of the world and therefore on the detailed measurements which are obtained. While such priors are commonly combined with the actual measurements via Bayes' rule to calculate posterior probability distributions on model parameters, their additional value in guiding efficient image processing has almost always been overlooked. Priors tell us where to look for information in an image, how much computational effort we can expect to expend to extract it, and of how much utility to the task in hand it is likely to be. Such considerations are of importance in all practical real time vision systems, where the processing resources available at each frame in a sequence are strictly limited - and it is exactly in high frame rate real time systems such as trackers where strong priors are most likely to be available. In this paper, we use Shannon information theory to analyse the fundamental value of measurements using mutual information scores in absolute units of bits, specifically looking at the overwhelming case where uncertainty can be characterised by Gaussian probability distributions. We then compare these measurement values with the computational cost of the image processing required to obtain them. This theory puts on a firm footing for the first time principles of 'active search' for efficient guided image processing, in which candidate features of possibly different types can be compared and selected automatically for measurement.
BibTeX
@inproceedings{davison2005active,
  author = {Andrew J. Davison},
  title = {{Active Search for Real-Time Vision}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2005},
  url = {https://openreview.net/forum?id=rkVLqWGObr},
}
Figure