Active query-driven visual search using probabilistic bisection and convolutional neural networks

Athanasios Tsiligkaridis, Theodoros TsiligkaridisarXiv 2018 · arXiv

TL;DR

This paper introduces a high-speed object localization framework that combines the Probabilistic Bisection Algorithm (PBA) with Convolutional Neural Networks (CNNs). By treating the CNN as a "noisy oracle" in an active search process, the authors achieve face localization speeds over 40 times faster than traditional sliding window methods while maintaining high accuracy.

What Problem Does This Paper Address?

Object localization—finding exactly where an object is in an image—is a cornerstone of computer vision. However, traditional methods like sliding windows are computationally exhaustive because they require running a classifier over hundreds or thousands of overlapping image patches. While modern "one-shot" detectors like YOLO or region-based methods like R-CNN are powerful, they are often too computationally heavy for resource-constrained platforms like mobile devices or UAVs, especially when only a single object needs to be found.

The authors seek a middle ground: an "active" search strategy that intelligently queries the image to narrow down the object's location with as few classifier evaluations as possible.

Methods

The core of the approach is the Probabilistic Bisection Algorithm (PBA), a Bayesian search method. Imagine playing "20 Questions" to find a point on a line. You ask, "Is the point in the left half?" Based on the answer, you update your belief.

Key components of their hybrid system include:

  • Independent Querying: The authors prove (Proposition 1) that searching for the object's $x$ and $y$ coordinates independently is theoretically as effective as a joint 2D search but much simpler to implement.
  • The CNN Oracle: A trained CNN acts as the oracle. When the PBA selects a region to query, the CNN determines if the object is present. Crucially, the CNN's softmax output is used to estimate the probability of error ($\epsilon$), which dictates how aggressively the system updates its belief.
  • Handling Aspect Ratios: Since CNNs typically require square inputs, long or narrow query regions are partitioned into square blocks. These blocks are resized and fed into the CNN, and the results are aggregated to provide a final answer for that region.
Fig. 2. Methodology for forming face and background images from the CelebA images. The presented image is partitioned into an im- age with more face and less background and an image with only background.

Datasets

The authors evaluated their method on two types of data:

  1. Synthetic Dataset: A simple "star in noise" task used to validate that the PBA + CNN approach matches the accuracy of sliding windows in controlled conditions.
  2. Real-World Dataset (CelebA): The authors used the CelebA dataset to train a three-layer CNN for face detection. They developed a specific partitioning strategy (seen in Figure 2 above) to create a robust training set containing full faces, partial faces, and background-only squares.

Key Insights and Ideas

  • Dimensionality Reduction via Theory: The proof that independent 1D searches achieve the same lower bound on error as a joint 2D search is a major "aha" moment. It justifies a much simpler, faster algorithm without sacrificing theoretical optimality.
  • Softmax as a Tuning Knob: Instead of just taking the CNN's "Yes/No" label, the authors use the softmax scores to calculate a total error probability (Equation 2). This allows the Bayesian update to be "cautious" when the CNN is unsure and "bold" when it is confident.
  • Active vs. Passive: Unlike sliding windows (passive), this method is active. It uses the information gained from previous queries to decide where to look next, leading to exponential convergence in the search space.

Key Results

The hybrid PBA + CNN method was tested against sliding window techniques across several celebrity images.

  • Speed: The proposed method is significantly more efficient. As shown in Table 1 (Figure 4), the hybrid method required only 26 to 46 CNN calls per image, whereas sliding windows required hundreds. On average, the method was 43x faster.
  • Accuracy: Despite the massive reduction in computation, the localization remained accurate. Figure 4 shows that the PBA-derived bounding boxes (green) closely match or even improve upon the sliding window results (red).
Comparison of detected faces using sliding window (red) vs. the proposed Hybrid PBA + CNN (green).

Limitations and Future Work

The primary limitation acknowledged by the authors is the single-object assumption. The current PBA framework is designed to find one target. If an image contains multiple faces, the bisection logic would need to be adapted.

The authors suggest that future work could involve n-ary partitioning (splitting the image into more than two parts) to facilitate the localization of multiple objects simultaneously. Additionally, the framework could be extended to object search in video streams, where temporal consistency could further speed up the "active" query process.

Summary updated

Abstract

We present a novel efficient object detection and localization framework based on the probabilistic bisection algorithm. A Convolutional Neural Network (CNN) is trained and used as a noisy oracle that provides answers to input query images. The responses along with error probability estimates obtained from the CNN are used to update beliefs on the object location along each dimension. We show that querying along each dimension achieves the same lower bound on localization error as the joint query design. Finally, we compare our approach to the traditional sliding window technique on a real world face localization task and show speed improvements by at least an order of magnitude while maintaining accurate localization.
BibTeX
@misc{tsiligkaridis2018active,
  author = {Athanasios Tsiligkaridis and Theodoros Tsiligkaridis},
  title = {{Active query-driven visual search using probabilistic bisection and convolutional neural networks}},
  year = {2018},
  eprint = {1806.11223},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.11223},
}
Figure