Abstract
Given the ever increasing bandwidth of the visual information available to many intelligent systems, it is becoming essential to endow them with a sense of what is worthwhile their attention and what can be safely disregarded. This article presents a general mathematical framework to efficiently allocate the available computational resources to process the parts of the input that are relevant to solve a given perceptual problem. By this we mean to find the hypothesis H (i.e., the state of the world) that maximizes a function L(H), representing how well each hypothesis "explains" the input. Given the large bandwidth of the sensory input, fully evaluating L(H) for each hypothesis H is computationally infeasible (e.g., because it would imply checking a large number of pixels). To address this problem we propose a mathematical framework with two key ingredients. The first one is a Bounding Mechanism (BM) to compute lower and upper bounds of L(H), for a given computational budget. These bounds are much cheaper to compute than L(H) itself, can be refined at any time by increasing the budget allocated to a hypothesis, and are frequently enough to discard a hypothesis. To compute these bounds, we develop a novel theory of shapes and shape priors. The second ingredient is a Focus of Attention Mechanism (FoAM) to select which hypothesis' bounds should be refined next, with the goal of discarding non-optimal hypotheses with the least amount of computation. The proposed framework: 1) is very efficient since most hypotheses are discarded with minimal computation; 2) is parallelizable; 3) is guaranteed to find the globally optimal hypothesis; and 4) its running time depends on the problem at hand, not on the bandwidth of the input. We instantiate the proposed framework for the problem of simultaneously estimating the class, pose, and a noiseless version of a 2D shape in a 2D image.
Introduction: The Challenge of Visual Bandwidth
Modern sensors provide a "firehose" of high-resolution data. In a standard "hypothesize-and-verify" approach, a system might test thousands of possible object locations, scales, and classes. Evaluating every single one against every pixel is computationally ruinous. While many existing "Focus of Attention" models are biologically inspired—mimicking the way human attention can ignore obvious but irrelevant stimuli—they often lack mathematical guarantees of optimality.
The authors sought a framework that is simultaneously efficient (discarding bad guesses with minimal work), optimal (guaranteed to find the best global solution), and resolution-independent. Crucially, the algorithm's complexity should depend on the difficulty of the task rather than the resolution of the input image, mimicking the efficiency of biological vision.
The Hypothesize and Bound (H&B) Framework
The proposed Hypothesize and Bound (H&B) framework consists of two main components designed to navigate the hypothesis space without exhaustive pixel-level checks:
- Bounding Mechanism (BM): Instead of calculating the exact "evidence" $L(H)$ (how well a shape fits the image), the BM calculates lower and upper bounds. If a hypothesis's upper bound is lower than another's lower bound, it can be safely discarded as non-optimal.
- Focus of Attention Mechanism (FoAM): This is the decision-making component that selects which hypothesis to refine next. It uses a heuristic to select the guess most likely to reduce the overall uncertainty of the system.
To make this work for shapes, the authors developed a Theory of Semidiscrete Shapes, representing image data using Logit Cumulative Distribution Functions (LCDFs). By using integral images, they can compute these bounds in $O(1)$ time per partition element, allowing the algorithm to start with a coarse view and only "zoom in" on promising areas.
Key Insights and Results
The researchers evaluated their framework using synthetic data with various noise profiles and a real-world dataset of 218 degraded characters from historical manuscripts.
- Extreme Pruning: In synthetic tests with over 148,000 hypotheses, 95.5% were discarded after only one or two refinement cycles. On average, the system only needed to evaluate ~1.78 pairs of bounds per hypothesis, whereas a naive check would have required inspecting over 16,000 pixels.
- Resolution Independence: Total computation does not depend on the number of pixels, but on how similar the hypotheses are. The algorithm automatically spends more cycles on high-resolution details only when necessary to distinguish between similar shapes.
- Emergent Attention: The system naturally "pays attention" to edges because mathematical bounds are most uncertain at shape boundaries, resolving ambiguity where it matters most.
- Robustness: On highly degraded historical text, the system achieved a classification accuracy of 90.4% and performed implicit optimal denoising by fitting the best shape prior to the noisy input.
Conclusion and Future Work
The H&B framework provides a mathematically rigorous way to implement focus of attention in computer vision. While currently reliant on discrete shape priors, future work aims to address intra-class variability and integrate Branch and Bound techniques to prune entire sets of hypotheses simultaneously. While this study focuses on 2D, the framework is designed for N-D and has already seen extensions into 3D reconstruction.
Summary updated