{'fraction_non_alphanumeric': 0.035603770229414904, 'fraction_numerical': 0.017784101013693758, 'mean_word_length': 4.536825521859, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An active search strategy for efficient object class detection

Object class detectors typically apply a window classifier to all the windows in a large set, either in a sliding window manner or using object proposals. In this paper, we develop an active search strategy that sequentially chooses the next window to evaluate based on all the information gathered before. This results in a substantial reduction in the number of classifier evaluations and in a more elegant approach in general. Our search strategy is guided by two forces. First, we exploit context as the statistical relation between the appearance of a window and its location relative to the object, as observed in the training set. This enables to jump across distant regions in the image (e.g. observing a sky region suggests that cars might be far below) and is done efficiently in a Random Forest framework. Second, we exploit the score of the classifier to attract the search to promising areas surrounding a highly scored window, and to keep away from areas near low scored ones. Our search strategy can be applied on top of any classifier as it treats it as a black-box. In experiments with R-CNN on the challenging SUN2012 dataset, our method matches the detection accuracy of evaluating all windows independently, while evaluating 9x fewer windows.


Introduction
Given an image, the goal of object class detection is to place a bounding-box around every instance of a given object class. Modern object detectors [10,22,29,16,40,18,42,8] partition the image into a set of windows and then score each window with a classifier to determine whether it contains an instance of the object class. The detector finally outputs the windows with the locally highest scores.
In the classical sliding window approach [10,22,29,16], the window set is very large, containing hundred of thousands of windows on a regular grid at multiple scales. This approach is prohibitively expensive for slow, powerful window classifiers which are state-of-the-art nowadays [40,13,18,42,8], such as Convolutional Neural Networks (CNN) [18]. For this reason, these detectors are based instead on object proposal generators [2,40,30], which provide a smaller set of a few thousand windows likely to cover all objects. Hence, this reduces the number of window classifier evaluations required. However, in both approaches the window classifier evaluates all windows in the set, effectively assuming that they are independent.
In this work, we propose an active search strategy that sequentially chooses the next window to evaluate based on previously observed windows, rather than going through the whole window set in an arbitrary order. Observing a window not only provides information about the presence of the object in that particular window, but also about its surroundings and even distant areas of the image. Our search method extracts this information and integrates it into the search, effectively guiding future observations to interesting areas, likely to contain objects. Thereby, our method explores the window space in an intelligent fashion, where future observations depends on all the information gathered so far. This results in a more natural and elegant way of searching, avoiding wasteful computation in uninteresting areas and focusing on the promising ones. As a consequence, our method is able to find the objects while evaluating much fewer windows, typically only a few hundreds (sec. 7).
We use two guiding forces in our method: context and window classifier score. Context exploits the statistical relation between the appearance and location of a window and its location relative to the objects, as observed in the training set. For example, the method can learn that cars tend to be on roads below the sky. Therefore, observing a window in the sky in a test image suggest the car is likely to be far below, whereas a window on the road suggests making a smaller horizontal move. We learn the context force, in a Random Forest framework that provides great computational efficiency as well as accurate results. The classifier score of an observed window provides information about the score of nearby windows, due to the smoothness of the classifier function. It guides the search to areas where we have observed a window with high score, while pushing away from windows with low score. Observing a window with part of a car, for example, will attract the search to its surroundings.
Our method effectively combines these two forces. Fig. 1 shows the intuition of our method on detecting cars. It starts at window w 0 and it moves away immediately, since w 0 contains a piece of building, not a car. Context determines the direction of the move, as cars tend to be on streets below buildings. Hence, the next visited location is on the road. After observing w 1 , the method continues searching along the road, as indicated by context. For window w 2 , however, the score of the classifier is rather high, as it contains a piece of car. Therefore, the search focuses around this area until it finds a tight window on the car.
Through experiments on 5 classes of the challenging SUN2012 dataset [44], we demonstrate that our method explores the image in an intelligent way, effectively detecting objects in only a few hundred iterations. As a window classifier we use CNN features [24,25] on object proposals [40], a combination that has recently been shown to produce state-of-the-art results [18]. Our search strategy matches the detection accuracy of evaluating all proposals independently, while evaluating 8× fewer proposals on average. By letting our search run for a little longer, we even improve accuracy while evaluating 4× fewer proposals, as it avoids evaluating some cluttered image areas that might lead to false-positives. Hence, our method opens the door to using expensive classifiers by considerably reducing the number of evaluations while adding little overhead. For example, we facilitate the use of the CNN features on the CPU [24], reducing the total processing time for one test image from 320s to only 41s, a 8× speed-up. The result is similar when using a GPU, reducing from 15 seconds to 4 seconds (4× speed-up).

Related Work
Object proposals. Recent, highly accurate window classifiers like high-dimensional Bag of Words [40] or CNN [25,13,18] are too expensive to evaluate in a sliding window fashion. For this reason, recent detectors [40,18,42,8] evaluate only a few thousands windows produced by object proposals generators [2,40,30]. The state-ofthe-art detector [18] follows this approach, using CNN fea-tures [25] with Selective Search proposals [40]. Although proposals already reduce the number of window classifier evaluations, our work brings even further reductions.
Improving sliding window. Lampert et al. [26] use a branch-and-bound scheme to efficiently find the maximum of the classifier over all windows. However, it is limited to classifiers for which tight bounds on the highest score in a subset of windows can be derived. Lehman et al. [28] extend [26] to some more classifiers. An alternative approach [22,41] is to first run a linear classifier over all windows and then evaluate a complex non-linear kernel only on a few highly scored windows. Sznitman et al. [37] avoid exhaustive evaluation for face detection by using a hierarchical model and pruning heuristics. A few works develop techniques that make sequential fixations inspired by human perception for tracking in video [4], image classification [27] and face detection [6]. However, they only use the score of a (foveated) window classifier, not exploiting the valuable information given by context. Moreover, they experiment on simple datasets, far less challenging than SUN2012 [44] (MNIST digits, faces).
Context. Many works use context as an additional cue on top of object detectors, complementing the information provided by the window classifier, but without altering the search process. Torralba [38] started using global image descriptors such as GIST [35] to estimate the presence of object classes. Several works [33,16,22,40] employed such global context to remove out-of-context falsepositive detections. The response of detectors for multiple object classes also provides context, as it enables to reason about co-occurrence and spatial relations between classes. Rabinovich et al [36] first labels image regions according to individual detectors, and then refine the labelling to promote natural co-occurrence statistics between classes. Other works in this spirit [17,7,11] have added spatial relations between object classes as well. Heitz and Koller [23] help the detection of object classes by using nearby background classes. Divvala et al. [12] analyze several context sources and their impact on object detection.
The most related work to ours is [3], which propose a search strategy driven by context. Here we go beyond in several ways: (1) They used context in an inefficient way, involving a nearest-neighbour search over all windows in all training images. This caused a large overhead that compromised the actual wall-clock speedup they made over evaluating all windows in the test image. In contrast, we present a very efficient technique based on Random Forests, which has little overhead (sec. 7.2). (2) While [3] uses only context, we guide the search also by the classifier score, and learn an optimal combination of the two forces (sec. 3).
(3) They perform single-view and single-instance detection, whereas we detect multiple views and multiple instances in the same image. (4) We adopt the modern CNNs [24,25] over object proposals [40] as the reference detector and compare to it, as opposed to the weaker DPM detector [16]. (5) We perform experiments on SUN2012 [44], which has more cluttered images with smaller objects than PASCAL VOC 2010 [14], used by [3].

Search model
Let I be a test image represented by a set of object proposals [40], The goal of our method is to efficiently detect objects in I, by evaluating the window classifier on only a subset of the proposals. Our method is a class-specific iterative procedure that evaluates one window at a time. At every iteration t, it selects the next window o t+1 according to all the observations {o k } t k=1 performed so far. 1 We assign a belief value b t (o i , {o k } t k=1 ; Θ) to each object proposal o i and update it after every iteration. This belief indicates how likely it is that o i contains the object, given all previously observed windows {o k } t k=1 . Here Θ = {λ, σ} is a set of hyperparameters and t indexes the iteration.
The method starts with the belief map b 0 (o i ) = 0 ∀o i , representing complete uncertainty. At iteration t, the method selects the window with the highest belief We avoid repetition by imposing o t = o k , ∀k < t. The starting window o 1 is the average of all the ground-truth bounding-boxes in the training set. At each iteration t, the method obtains information from the new observation o t and it updates the belief values of all windows as follows The observation o t provides two kind of information: the context C and the classifier score S (explained below). These are linearly combined with a mixing parameter λ ∈ [0, 1]. Fig. 3 illustrates our pipeline.
Context force C points to areas of the image likely to contain the object, relative to the observation o t . It uses the statistical relation between the appearance and location of training windows and their position relative to the objects. The context force may point to any area of the image, even those distant from o t . For the car detection example, if o t contains a patch of building, C will point to windows far below it, as cars are below buildings ( fig. 1, 6). If o t contains 1 o i indexes through the input set of proposals I, whereas o t is the proposal actively chosen by our strategy in the t-th iteration. a patch of road, C will propose instead windows next to o t , as cars tend to be on roads ( fig. 1).
The heart of the force C is a context extractor Γ. Given the appearance and location of o t , Γ returns a set of windows Γ(o t ) = {w j } J j=1 (not necessarily object proposals). These windows cover locations likely to contain objects of the class, as learned from a set of training windows and their relative position to the objects in their own images. We explain how our context extractor works in sec. 4.
We can now define C as It gives high values to object proposals close to windows in Γ(o t ), as we expect these windows to be near objects. The influence of the windows in Γ(o t ) is weighted by a smoothing kernel This choice of kernel assumes smoothness in the presence of an object for nearby windows. Indeed, adjacent windows to a window containing an object will also contain part of the object. The further the windows are, the lower the probability of containing the object is. We use the inverse overlap 1 -intersection-over-union [14] (IoU) as distance between two windows.
Classifier score force S attracts the search to the area surrounding the observation o t if it has high classifier score, while pushing away from it if it has low score. We define it as follows where φ(o t ) ∈ [0, 1] is the window classifier score of o t (sec.5 details our choice of window classifier). We translate φ(o t ) into the [−0.5, 0.5] range and weight it using the smoothing kernel (4). Therefore, S operates in the surroundings of o t , spreading the classifier score to windows near o t . When S is positive, it attracts the search to the region surrounding o t . For example, if o t contains part of a car, it will probably have a high classifier score. Then S will guide the search to stay in this area, as some nearby window is likely to contain the whole car. On the other hand, when S values are negative, it has a repulsive effect. It pushes the search away from uninteresting regions with low classifier score, such as background (sky, buildings, etc). Fig. 2 shows an example of this force in action.

Context extractor
Given an input observation o in the test image, the context extractor Γ returns a set of windows Γ(o) = {w j } J j=1 covering locations likely to contain objects.
The context extractor is trained from the same data as the window classifier, i.e. images with annotated object bounding-boxes. Hence our approach requires the same annotation as standard object detectors [8,10,22,29,16,40,18,42]. The training set is defined as a set of pairs {(r n , ∆v n )} N n=1 . Here r n is a proposal from a training image and ∆v n is a 4D displacement vector, which transforms r n into the closest object bounding-box in its training image ( fig. 4(a-b)). Here index n runs over all object proposals in all the training images. For 500 images and 3200 proposals per image, N = 500 · 3200 = 1 600 000.
Given the observation, the context extractor regresses a displacement vector ∆v pointing to the object. For robustness, the context extractor actually outputs a set of displacement vectors {∆v j } J j=1 , to allow for some uncertainty regarding the object's location. Then it applies {∆v j } J j=1 to o, obtaining a set of displaced windows on the test image: The windows in Γ(o) indicate expected locations for the object in the test image. Note that they may be any window, not necessarily object proposals.
Random Forests. We use Random Forests (RF) [5] as our context extractor. A RF is an ensemble of J binary decision trees, each tree inputs the window o and outputs a displacement vector ∆v j . The final output of RF are all displacement vectors {∆v j } J j=1 produced by each tree. RF have been successfully applied in several learning problems such as classification, regression or density estimation [9]. RF in computer vision [9,15,19,31] typically use axis-aligned separators (thresholding on one feature dimension) as tests in the internal nodes. However, we have found that tests on distances to training samples perform better in our case, as they are much more informative than tests on single feature dimensions. This motivated us to devise a version of RF based on distance tests. This is related to Proximity Forests [34], although in their case they use RF for clustering, not regression.
When the test window o is passed into a tree, it traverses it from the root to a leaf guided by tests in the internal nodes. At each internal node p the decision whether o goes left or right is taken by comparing the distance d p (o, r p ) between o and a pivot point r p to the threshold τ p . The distance function d p , threshold τ p and the pivot training point r p are chosen during training, as explained in the next paragraph (we consider two possible distance functions, detailed in sec. 6). The test window o proceeds to a left child if d p (o, r p ) ≥ τ p or to the right child otherwise (fig. 5). This process is repeated until a leaf is reached. Each leaf stores a displacement vector, which the tree returns. RF training. For each class, we train one RF with J = 10 trees. To keep the trees diverse, we train each one on windows coming from a random sub-sample of 40 training images. As shown in [9], this procedure improves generalization. We construct each tree by recursively splitting the training set at each node. We want to learn tests in the internal nodes such that leaves contain samples with a compact set of displacement vectors. This way a tree learns to group windows using features that are predictive of their relative location to the object. To create an internal node p, we need to select a triplet (r p ,τ p ,d p ), which defines our test function. Following the extremely randomized forest framework [32] we generate a random set of possible triplets. We then pick the triplet that achieves maximum information gain: where S is the set of training samples at the node and L, R denote the left and right children with samples S L and S R , respectively. H is the approximated Shannon entropy of the displacement vectors inside S, computed through the sum of individually estimated entropies by uni-dimensional histograms [21]. The displacement vector of a leaf is computed by: i) passing all the training samples through the tree; ii) recording the mediod displacement vector of the training samples that fell into the leaf. Fig. 6 (Test) shows two examples of applying the RF on car and chair images. It also shows ( fig. 6 (Training)) a few training windows from a leaf into which the test window fell. Notice how these training windows are similar in appearance to the test window, and also produce displaced windows that cover areas where objects are likely to be in the test image. This demonstrates that RF is capable of learning the relation between windows appearance and their relative position to the object.

Efficiency.
A key benefit of using RF over a simple nearest-neighbour regressor [3] is computational efficiency. Since the observation o is only compared to at most as many pivot points as the depth of the tree, the runtime of RF grows only logarithmically with the size of the training set. In contrast, the runtime of nearest-neighbour grows linearly in the size of the training set, since o has to be compared to every training sample. In practice, this makes a substantial different in runtime, as we demonstrate experimentally in sec. 7.2.

Classifier scores
We use the CNN model of Krizhevksy et al. [25] as window classifier φ. This model achieved winning results on the ILSVRC-2012 image classification competition [1]. The architecture consists of 5 convolutional layers and 3 fully-connected layers, with pooling layers interleaved after the first, second and fifth layer [25]. It also provides visual features, corresponding to unit activations of its intermediate layers [13]. These features are an excellent representation for visual tasks, obtaining state-of-the-art results for object detection, in combination with object proposals and a simple linear SVM window classifier [18].
We use the Caffe implementation [24], which extracts features at a rate of 222 windows per second using a GeForce GTX 770 GPU. We use a CNN model pretrained on the ILSVRC-2012 classification challenge data [25], also provided by [24]. We train linear SVMs on L2-normalized 4096-dimensional CNN features, obtained from the 7-th layer of the network. Our SVM training procedure is similar to [40], using Selective Search proposals and hard-negative mining. In order to make the classifier score lie in [0, 1], we Similar to [39,3], we embed the 4096-dimensional CNN appearance features [24] in a Hamming space with 512 bits using [20]. This reduces the memory footprint for storing the appearance descriptors (from 262144 bits to just 512 per window). It also speeds up distance computations, as the Hamming distance between these binary strings is 170× faster than L2-distance in the original space.
The two distance functions (IoU for location and Hamming for appearance) are used in sec. 4.
Training hyperparameters Θ. For each object class, we find optimal hyperparameters σ and λ by maximizing object detection performance on a validation set. Performance is quantified by the area under the Average Precision (AP) curve, which reports AP as a function of the number of proposals evaluated by the strategy (fig. 7). We use grid search in ranges σ ∈ [0.01, 1] and λ ∈ [0, 1]. We have also trained specific σ values when only using S, σ S , and when only using C, σ C . Interestingly, the learned σ values correspond to intuition. For σ S we obtain small values, as the area of influence is close to the observed window. On the other hand, values for σ C are larger, as the context force has a greater influence in surrounding windows. Furthermore, C  uses arbitrary windows, hence the distance to proposals is generally bigger.
Object proposals. We use the fast mode of Selective Search [40], setting the maximum image side length to 1000 pixels. We take at most 5000 proposals per image, which results in an average of 3224 proposals per image. This set of object proposals achieve a mean Average Best Overlap (MABO) [40] of 0.714 in the SUN2012 [44] dataset, which is comparable to the MABO reported in by [40] for PAS-CAL VOC 2012 [14].

Experiments
We perform experiments on all available images for the 5 most frequent classes in the highly challenging SUN2012 dataset [44]: Chair, Person, Car, Door and Table. This amounts to 2920 training images and 6794 test images, using the official train/test split provided with the dataset [43]. Each image is annotated with bounding-boxes on instances of our 5 classes. This dataset is composed of large cluttered scenes with small objects, as it was originally created for scene recognition [44]. This makes it very challenging for object detection, and also well suited to show the benefits of using context in the search strategy.
We measure performance on the test set by Average Precision (AP), computed using the PASCAL criterion (IoU > 0.5 for positive detection) [14]. Previous to the AP computation, we use Non-Maxima Suppression [16] to remove duplicate detections. In all experiments, we train the window classifier, the Random Forest regressor and the hyperparameters Θ on the training set only. Fig. 7 presents results for our full system ('Combination') as well as when using only each force S or C alone. The figure shows the evolution of AP as a function of the number of proposals evaluated. As a baseline, we compare to evaluating proposals in a random sequence ('Proposals Subsampling'). This represents a naive way of reducing the number of evaluations.

Results
Our full method clearly outperforms Proposals Subsampling, by selecting a better sequence of proposals to evaluate. On average over all classes, by evaluating about 390 proposals we match the performance of evaluating all proposals. This corresponds to a 8× reduction in the number Interestingly, the curve for our full method reach a higher point than the baseline, for some intermediate number of proposals. We show in table 1 the maximum AP achieved by our method and the number of proposals needed to reach it, as well as the AP of evaluating all proposals. We outperform evaluating all proposals on every class, by up to 4% for Chair. This is due to the avoiding some cluttered areas in the images, where the window classifier would produce false-positives. On average we achieve the maximum AP while evaluating 870 proposals, i.e. about 4× fewer than all proposals.
In general, we achieve our best results by combining both forces S and C. When using one force alone, C performs better, in some cases even reaching the accuracy of our combined strategy. Nevertheless, force S achieves surprisingly good results by itself, providing a rather simple method to speed-up state-of-the-art object detectors while maintaining high accuracy. Fig. 8 shows some qualitative results, along with our search strategy in action. We can see how after just a few iterations the belief maps are already highlighting areas containing the objects. Uninteresting areas such as the sky or the ceiling are barely ever visited, hence we waste little computation. Our method detects multiple instances and viewpoints, even in challenging images with small objects. In these examples, it finds the first object instance in fewer than 20 iterations, showing its efficiency in guiding the search. After finding the first instance, it continues exploring other areas of the image looking for more instances.
As a last experiment, we compare our RF context extractor with one based on nearest-neighbour search, as in [3]. We run our method only using the context force C, but substituting RF with nearest-neighbours, on the same input features and number of training windows. The results show that both ways of extracting context lead to the same performance. The AP at 500 windows, averaged over all classes, differs by only 0.006. In terms of runtime, however, RF is substantially better (about 60× faster, see sec. 7.2).

Runtime
We perform all experiments on an Intel Xeon E5-1620v2 CPU and a GeForce GTX 670 GPU. The most expensive component are computing CNN features, which takes 4.5 ms per window on the GPU. Evaluating the 3200 proposals in an average SUN2012 image takes 15.2 seconds. The total overhead added by our method is 4.8 ms per iteration. Therefore, processing one image while maintaining the same AP performance (390 iterations) takes 4 seconds, i.e. 4× faster than evaluating all proposals.
The small overhead added by our method is mainly due to the RF query performed at each iteration for the context force, which amounts to 4.1 ms including the Hamming embedding of the appearance features. In comparison, a context extractor implemented using Nearest Neighbours as in [3] takes 57 ms per iteration, which would lead to no actual total runtime gain over evaluating all proposals.
As the runtime of the window classifier grows, the speedup made by of our method becomes more important. Extracting CNN features on the CPU takes 0.1 seconds per window [24]. In this regime, the overhead added by our method becomes negligible, only 5% of running the window classifier. Evaluating all 3200 proposals in an image would require 320 seconds, in contrast to just 41 seconds for evaluating 390 proposals with our method, a 8x× speed-up.

Conclusion
Most object detectors independently evaluates a classifier on all windows in a large set. In this paper, instead, we have presented an active search strategy that sequentially chooses the next window to evaluate based on all the information gathered before. Our search model effectively combines two complementing driving forces: context and window classifier score.
In experiments on the highly challenging SUN2012 dataset, by only evaluating a few hundred windows, our method matches the accuracy of evaluating all object proposals (thousands per image). Due to the efficiency of our proposed context extractor based on Random Forests, we add little overhead to the detection pipeline, obtaining significant speed-ups in actual runtime.