Efficient Subwindow Search: A Branch and Bound Framework for Object Localization

By Christoph H. Lampert, Matthew B. Blaschko, Thomas Hofmann. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009

414 citations recorded by the source corpus.

Most successful object recognition systems rely on binary classification, deciding only if an object is present or not, but not providing information on the actual object location. To estimate the object's location, one can take a sliding window approach, but this strongly increases the computational cost because the classifier or similarity function has to be evaluated over a large set of candidate subwindows. In this paper, we propose a simple yet powerful branch and bound scheme that allows efficient maximization of a large class of quality functions over all possible subimages. It converges to a globally optimal solution typically in linear or even sublinear time, in contrast to the quadratic scaling of exhaustive or sliding window search. We show how our method is applicable to different object detection and image retrieval scenarios. The achieved speedup allows the use of classifiers for localization that formerly were considered too slow for this task, such as SVMs with a spatial pyramid kernel or nearest-neighbor classifiers based on the lambda2 distance. We demonstrate state-of-the-art localization performance of the resulting systems on the UIUC Cars data set, the PASCAL VOC 2006 data set, and in the PASCAL VOC 2007 competition.

Subfields: Aerospace Engineering, Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/97da2ab0b062a7a0ccfc00b3567f0f70ac994fd7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Particular object retrieval with integral max-pooling of CNN activations (2015, methodology): “Their work employs integral images, which are also used in later improvements of ESS (An et al., 2009).”
Weakly Supervised Object Localization with Multi-Fold Multiple Instance Learning (2015, background): “[9] train the branch-and-bound localization [31] based detectors”
Fisher and VLAD with FLAIR (2014, methodology): “Neither the integral representation of [15, 28], nor the pointwise representation in [4] allow for `2- and power-norms, and they do also not allow for the use of fine spatial pyramids.”
Segmenting Salient Objects from Images and Videos (2010, neutral): “[13–15].”
Non Maximal Suppression in Cascaded Ranking Models (2013, background): “proposed to use branch and bound to find the optimal window according to a scoring function [9], while Lehmann et al.”
The Fastest Deformable Part Model for Object Detection (2014, methodology): “Motivated by the branch-and-bound approach [20] for object detection, [16] introduced it to DPM with carefully designed bound.”
Proposal generation for object detection using cascaded ranking SVMs (2011, background): “Branch and bound techniques [13, 14] for instance limit the number of windows that must be evaluated by pruning sets of windows at a time whose maximal response can be bounded above.”
Recent advances and trends in visual tracking: A review (2011, methodology): “To overcome it, efﬁcient search techniques such as cascaded method [127] and Efﬁcient Subwindow Search [129] can be integrated with MKL framework.”
Fast Feature Pyramids for Object Detection (2014, background): “…for increasing detection speed include work by Felzenszwalb et al. [44] and Pedersoli et al. [45] on cascaded and coarse-to-fine deformable part models, respectively, Lampert et al.'s [46] application of branch and bound search for detection, and Doll ar et al.'s work on crosstalk cascades [40].”
Crosstalk Cascades for Frame-Rate Pedestrian Detection (2012, background): “’s [3] application of branch and bound search for detection, and Dollár et al.”
Poselet Key-Framing: A Model for Human Activity Recognition (2013, methodology): “Finding the bounding box with the highest score in the case of BoW representation can be done very efficiently using branch-andbound techniques [16].”
ME R-CNN: Multi-Expert Region-based CNN for Object Detection (2017, methodology): “[24] used an objectness quality function to discard sub-search spaces whose objectness scores are under a certain threshold, where object detector becomes an objectness quality function.”
Spatio-temporal Object Detection Proposals (2014, positive): “[48] proposed an efﬁcient branch-and-bound search method to locate actions in space-time cuboids based on efﬁcient subwindow search [22].”
Selective Search for Object Recognition (2016, methodology): “Lambert et al [18] proposed another method which used an appearance model to guide the search.”
Tree-Structured Reinforcement Learning for Sequential Object Localization (2016, background): “Lampert et al. [15] proposed a branch-and-bound approach to find the highest scored windows while only evaluating a few locations.”