Learning To Count Objects in Images

Victor S. Lempitsky, Andrew ZissermanNeurIPS 2010 · OpenReview

This classic paper from Lempitsky and Zisserman (Visual Geometry Group, Oxford) introduces a powerful framework for counting objects in images by estimating a continuous density function. By moving away from the traditional "detect-then-count" paradigm and utilizing a novel loss function called MESA distance, the authors demonstrate how to achieve high accuracy with minimal human annotation.

Instead of trying to detect every individual object, this approach learns to map image features to a "density map" where the integral over any region equals the object count. By training on simple "dot" annotations and optimizing the MESA distance loss, the system achieves state-of-the-art counting performance in crowded scenes where traditional detectors often fail.

The Object Counting Problem

Counting objects—whether they are cells in a microscope, people in a crowd, or trees in a forest—is a fundamental computer vision task. Historically, researchers relied on two main approaches, both of which have significant drawbacks:

  1. Counting by Detection: This involves finding every object with a bounding box and counting them. It fails when objects overlap (occlusion) or are too small or blurry to detect individually. It also requires expensive, labor-intensive bounding-box annotations.
  2. Counting by Regression: This maps global image features (like color histograms) directly to a single number. While easier to annotate, it discards all spatial information, requiring massive amounts of data to generalize effectively.

The authors seek a "middle ground": an approach that leverages spatial information but avoids the notoriously difficult problem of individual object localization.

Methods: Density Estimation and MESA Distance

The core idea is to learn a density function $F(p)$ for every pixel $p$. To find out how many objects are in a specific box or region, you simply sum (integrate) the density values within that area.

Dotted Supervision

Training this model requires minimal effort: just a single dot placed on each object.

Example of dotted supervision on synthetic cells.

The ground truth density is then modeled as a sum of small 2D Gaussians centered at these annotated dots. This "dotted annotation" is barely more work for a human than providing a total count, but it provides a wealth of spatial information that global regression ignores.

The MESA Distance

Standard pixel-wise losses (like $L_2$ or $L_1$) are too sensitive to the exact placement of these dots. To solve this, the authors introduce the Maximum Excess over SubArrays (MESA) distance. MESA finds the rectangular sub-region where the difference between the predicted count and the ground truth count is the largest. Because MESA cares about the integral over regions rather than pixel-perfect matches, the model becomes highly robust to "jitter" (small errors in human dot placement) and high-frequency noise.

Optimization

The problem is formulated as a convex quadratic program. Because there are a combinatorial number of possible rectangles (subarrays) to check, the authors use a cutting-plane algorithm to iteratively add only the most "violated" constraints, making the training computationally feasible.

Datasets and Evaluation

The authors evaluated their framework on two distinct types of imagery to prove its versatility:

  1. Synthetic Bacterial Cells: A dataset of 200 simulated fluorescence microscopy images containing between 74 and 317 cells per image. Synthetic data was chosen because human experts often disagree on ground-truth counts in real microscopy, making objective evaluation difficult.
  2. UCSD Pedestrian Dataset: A 2000-frame video of a sidewalk.
Example from the UCSD Pedestrian Dataset.

This dataset serves as a standard benchmark for crowd counting, presenting significant challenges like perspective distortion and heavy occlusions.

Key Results

  • Superiority over Baselines: On the synthetic cell dataset, the density learning approach achieved a Mean Absolute Error (MAE) of 3.5 (using MESA validation). This significantly outperformed linear ridge regression (MAE 5.9) and standard detection-based methods (MAE 8.5).
  • Efficiency: Once trained, the system is extremely fast. For the pedestrian dataset, counting is as simple as passing pixels through a Random Forest and summing pre-calculated weights, enabling real-time processing.
  • Competitive Performance: On the UCSD dataset, the method was competitive with—and often outperformed—hybrid segmentation methods that required much more complex annotation and modeling.
  • Feature Agnostic: The framework is highly flexible. The authors used SIFT-based codebooks for cells and Random Forest leaves for pedestrians. The underlying counting logic remains effective regardless of the visual descriptors used.

Limitations and Future Work

While groundbreaking, the paper notes a few limitations:

  • Optimization Bottleneck: Although the cutting-plane algorithm is efficient, the general-purpose quadratic programming (QP) solver was a time bottleneck during training, sometimes taking hours for large datasets.
  • Feature Engineering: Performance remains heavily dependent on the quality of the input features. Better domain-specific features could further improve results.
  • Box Constraints: The MESA distance currently evaluates rectangular subarrays. While effective, rectangles might not be the optimal "shape" for all types of object distributions.

Summary updated

Abstract

We propose a new supervised learning framework for visual object counting tasks, such as estimating the number of cells in a microscopic image or the number of humans in surveillance video frames. We focus on the practically-attractive case when the training images are annotated with dots (one dot per object). Our goal is to accurately estimate the count. However, we evade the hard task of learning to detect and localize individual object instances. Instead, we cast the problem as that of estimating an image density whose integral over any image region gives the count of objects within that region. Learning to infer such density can be formulated as a minimization of a regularized risk quadratic cost function. We introduce a new loss function, which is well-suited for such learning, and at the same time can be computed efficiently via a maximum subarray algorithm. The learning can then be posed as a convex quadratic program solvable with cutting-plane optimization. The proposed framework is very flexible as it can accept any domain-specific visual features. Once trained, our system provides accurate object counts and requires a very small time overhead over the feature extraction step, making it a good candidate for applications involving real-time processing or dealing with huge amount of visual data.
BibTeX
@inproceedings{lempitsky2010learning,
  author = {Victor S. Lempitsky and Andrew Zisserman},
  title = {{Learning To Count Objects in Images}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=HyWpsw-Obr},
}
Figure