AABO: Adaptive Anchor Box Optimization for Object Detection via Bayesian Sub-sampling

As mentioned before, mainstream detectors, including one-stage and two-stage detectors, rely on anchor boxes to provide initial guess of the object’s bounding box. And most detectors pre-define anchors and manually modify them when applied on new datasets. We believe that those manual methods can hardly find optimal anchor configurations and sub-optimal anchors will prevent the detectors from obtaining the optimal performance. To confirm this assumption, we construct two preliminary experiments.

Default Anchors Are Not Optimal. We randomly sample 100 sets of different anchor settings, each with 3 scales and 3 ratios. Then we examine the performance of Faster-RCNN [28] under those anchor configurations. The results are shown in Figure 1.

It’s obvious that compared with default anchor setting (3 anchor scales: $128^{2},256^{2},512^{2}$ and 3 aspect ratios: $1:1$, $1:2$, and $2:1$), randomly-sampled anchor settings could significantly influence the performance of the detector, which clearly demonstrates that the default anchor settings may be less appropriate and the optimization of anchor boxes is necessary.

Anchors Influence More Than RPN Structure. Feature Pyramid Networks [18] (FPN) introduces a top-down pathway and lateral connections to enhance the semantic representation of low-level features and is a widely used feature fusion scheme in modern detectors. In this section, we use BOHB [10] to search RPN head architecture in FPN as well as anchor settings simultaneously. The search space of RPN Head is illustrated in Figure 1. The searched configurations, including RPN head architecture and anchor settings, are reported in the appendix. Then we analyze the respective contributions of RPN head architecture and anchor settings, and the results are shown in Table 1. Here, mean Average Precision is used to measure the performance and is denoted by mAP.

The results in Table 1 illustrate that searching for proper anchor configurations could bring more performance improvement than searching for RPN head architecture to a certain extent.

Thus, the conclusion comes clearly that anchor settings affect detectors substantially, and proper anchor settings could bring considerable improvement than doing neural architecture search (NAS) on the architecture of RPN head. Those conclusions indicate that the optimization of anchor configurations is essential and rewarding, which motivates us to view anchor configurations as hyper-parameters and propose a better HPO method for our anchor optimization case.

Since we have decided to search appropriate anchor configurations to increase the performance of detectors over a certain dataset, one critical problem is how to design the search space. In the preliminary analysis, we construct two experiments whose search space is roughly determined regardless of the distribution of bounding boxes. In this section, we will design a much tighter search space by analyzing the distribution characteristics of object’s bounding boxes.

For a certain detection task, we find that anchor distribution satisfies some properties and patterns as follows.

Upper and Lower Limits of the Anchors. Note that the anchor scale and anchor ratio are calculated from the $width$ and $height$ of the anchor, which are not independent. Besides, we discover that both anchor $width$ and $height$ are limited within fixed values, denoted by $W$and $H$. Then the anchor ratio and scale must satisfy constraints as follows:

From the formulas above, we calculate the upper bound and lower bound of the ratio for the anchor boxes:

Figure 2 shows an instance of the distribution of bounding boxes (the blue points) as well as the upper and lower bounds of anchors (the yellow curves) in COCO [20] dataset. And the region inside the black rectangle is the previous search space using in preliminary experiments. We can observe that there exists an area which is beyond the upper and lower bounds so that bounding boxes won’t appear, while the search algorithm will still sample anchors here. So it’s necessary to limit the search space within the upper and lower bounds.

Adaptive Feature-Map-Wised Search Space. We then study the distribution of anchor boxes in different feature maps of Feature Pyramid Networks (FPN)[18] and discover that the numbers, scales and ratios of anchor boxes vary a lot across different feature maps, shown in the right subgraph of Figure 2. There are more and bigger bounding boxes in lower feature maps whose receptive fields are smaller, less and tinier bounding boxes in higher feature maps whose respective fields are wider.

As a result, we design an adaptive search space for FPN [18] as shown in the left subgraph of Figure 2. The regions within 5 red rectangles and the anchor distribution bounds represent the search space for each feature map in FPN. As feature maps become higher and smaller, the numbers of anchor boxes are less, as well as the anchor scales and ratios are limited to a narrower range.

Compared with the initial naive search space, we define a tighter and more adaptive search space for FPN [18], as shown in Figure 3. Actually, the new feature-map-wised search space is much bigger than the previous one, which makes it possible to select more flexible anchors and cover more diverse objects with different sizes and shapes. Besides, the tightness of the search space can help HPO algorithms concentrate limited resources on more meaningful areas and avoid wasting resources in sparsely distributed regions of anchors.

As described before, we regard anchor configurations as hyper-parameters and try to use HPO method to choose optimal anchor settings automatically. However, existing HPO methods are not suitable for solving our problems. For random search or grid search, it’s unlikely to find a good solution because the search space is too big for those methods. For Hyperband or BOHB, the proper configurations for the small objects could be discarded very early since the anchors of small objects are always slowly-converged. So we propose a novel method which combines Bayesian Optimization and sub-sampling method, to search out the optimal configurations as quickly as possible.

Specifically, our proposed approach makes use of BO to select potential configurations, which estimates the acquisition function based on the configurations already evaluated, and then maximizes the acquisition fuction to identify promising new configurations. Meanwhile, sub-sampling method is employed to determine which configurations should be allocated more budgets, and explore more configurations in the search space. Figure 4 illustrates the process of our proposed method. In conclusion, our approach can achieve good performance as well as better speed, and take full advantage of models built on previous budgets.

Bayesian Optimization. Bayesian Optimization (BO) is a sequential design strategy for parameter optimization of black-box functions. In hyper-parameter optimization problems, the validation performance of machine learning algorithms is regarded as a function $f:\chi\rightarrow\mathbb{R}$ of hyper-parameters $x\in\chi$, and hyper-parameter optimization problem aims to determine the optimal $x_{*}\in argmin_{\chi}f(x)$ . In most machine learning problems, $f(x)$ is unobservable, so Bayesian Optimization approach treats it as a random function with a prior over it. Then some data points are sampled and BO updates the prior and models the function based on those gathering data points and evaluations. Then new data points are selected and observed to refit the model function.

In our approach, we use Tree Parzen Estimator (TPE) [1] which uses a kernel density estimator to model the probability density functions $l(x)=p(y<\alpha|x,D)$ and $g(x)=p(y>\alpha|x,D)$ instead of modeling function $p(f|D)$ directly, where $D=\{(x_{0},y_{0}),\ldots,(x_{n},y_{n})\}$ and $\alpha=\min\{y_{0},\ldots,y_{n}\}$, as seen in BOHB [10]. Note that there exists a serious problem that the theory of Hyperband only guarantees to return the best $x_{i}$ which has the smallest $y_{i}$ among all these configurations, while the quality of other configurations may be very poor. Consequently, larger responses lead to an inaccurate estimation of $l(x)$, which plays an important role in TPE. Thus, we need to propose a policy that has a better sequence of responses $y_{i}$ to solve this problem.

Sub-Sample Method. To better explain the sub-sampling method used in our proposed approach, we first introduce the standard multi-armed bandit problem with $K$ arms in this section. Recall the traditional setup for the classic multi-armed bandit problem. Let $\mathcal{I}=\{1,2,\ldots,K\}$ be a given set of $K\geq 2$ arms. Consider a sequential procedure based on past observations for selecting an arm to pull. Let $N_{k}$ be the number of observations from the arm $k$, and $N=\sum_{k=1}^{K}N_{k}$ is the number of total observations. Observations $Y_{1}^{(k)},Y_{2}^{(k)},\ldots$, $1\leq k\leq K$ are also called rewards from the arm $k$. In each arm, rewards $\{Y_{t}^{(k)}\}_{t\geq 1}$ are assumed to be independent and identically distributed with expectation given by $\mathbb{E}(Y_{t}^{(k)})=\mu_{k}$ and $\mu_{*}=\max_{1\leq k\leq K}\mu_{k}$. For simplicity, assume without loss of generality that the best arm is unique which is also assumed in [25] and [5].

A policy $\pi=\{\pi_{t}\}$ is a sequence of random variables $\pi_{t}\in\{1,2,\ldots,K\}$ denoting that at each time $t=1,2,\ldots,N$, the arm $\pi_{t}$ is selected to pull. Note that $\pi_{t}$ depends only on previous $t-1$ observations. The objective of a good policy $\pi$ is to minimize the regret

Note that for a data-driven policy $\hat{\pi}$, the regret monotonically increases with respect to $N$. Hence, minimizing the growth rate of $R_{N}$ becomes an important criterion which will be considered later.

Then we introduce an efficient nonparametric solution to the multi-armed bandit problem. First, we revisit the Sub-sample Mean Comparisons (SMC) introduced in [5] for the HPO case. The set of configurations $\mathcal{I}=\{1,\ldots,K\},$minimum budget $b$ and parameter $c_{n}$ are inputs. Output is the sequence of the configurations $\hat{\pi}_{1},\ldots,\hat{\pi}_{N}\in\mathcal{I}$ to be evaluated in order.

First, it is defined that the $k$-th configuration is “better” than the $k^{\prime}$-th configuration, if one of the following conditions holds:

1. 1.

   $n_{k}<n_{k^{\prime}}$ and $n_{k}<c_{n}$.

2. 2.

   $c_{n}\leq n_{k}<n_{k^{\prime}}$ and $\bar{Y}_{1:n_{k}}^{(k)}\geq\bar{Y}_{j:(j+n_{k}-1)}^{(k^{\prime})}$ , for some $1\leq j\leq n_{k^{\prime}}-n_{k}+1$, where $\bar{Y}_{l:u}^{(k)}=\sum_{v=l}^{u}Y_{v}^{(k)}/(u-l+1)$.

In SMC, let $r$ denotes the round number. In the first round, all configurations are evaluated since there is no information about them. In round $r\geq 2$, we define the leader of configurations which has been evaluated with the most budgets. And, the $k$-th configuration will be evaluated with one more budget $b$, if it is “better” than the leader. Otherwise, if there is no configuration “better” than the leader, the leader will be evaluated again. Hence, in each round, there are at most $K-1$ configurations and at least one configuration to be evaluated. Let $n^{r}$ be the total number of evaluations at the beginning of round $r$, and $n_{k}^{r}$ be the corresponding number from the $k$-th configuration. Then, we have $K+r-2\leq n\leq K+(K-1)(r-2)$.

The Sub-sample Mean Comparisons(SMC) is shown in Algorithm 1. In SMC, the parameter $c_{n}$ is a non-negative monotone increasing threshold for SMC satisfied that $c_{n}=o(\log n)$ and $c_{n}/\log\log n\rightarrow\infty$ as $n\rightarrow\infty$. In [5], they set $c_{n}=\sqrt{\log n}$ for efficiency of SMC.

Note that when the round $r$ ends, the number of evaluations $n^{r}$ usually doesn’t equal to $N$ exactly, i.e., $n^{r}<N<n^{r+1}$. For this case, $N-n^{r}$ configurations are randomly chosen from the $n^{r+1}-n^{r}$ configurations selected by SMC in the $r$-th round. A main advantage of SMC is that unlike the UCB-based procedures, underlying probability distributions need not be specified. Still, it remains asymptotic optimal efficiency. The detailed discussion about theoretical results refers to [13].

We conduct experiments to evaluate the performance of our proposed method AABO on three object detection datasets: COCO 2017 [20], Visual Genome(VG) [16], and ADE [35]. COCO is a common object detection dataset with 80 object classes, containing 118K training images (train), 5K validation images (val) and 20K unannotated testing images (test-dev). VG and ADE are two large-scale object detection benchmarks with thousands of object classes. For COCO, we use the train split for training and val split for testing. For VG, we use release v1.4 and synsets [29] instead of raw names of the categories due to inconsistent annotations. Specifically, we consider two sets containing different target classes: VG₁₀₀₀ and VG₃₀₀₀, with 1000 most frequent classes and 3000 most frequent classes respectively. In both VG₁₀₀₀ and VG₃₀₀₀, we use 88K images for training, 5K images for testing, following [8, 15]. For ADE, we consider 445 classes, use 20K images for training and 1K images for testing, following [8, 15]. Besides, the ground-truths of ADE are given as segmentation masks, so we first convert them to bounding boxes for all instances before training.

As for evaluation, the results of the detection tasks are estimated with standard COCO metrics, including mean Average Precision (mAP) across IoU thresholds from 0.5 to 0.95 with an interval of 0.05 and AP₅₀, AP₇₅, as well as AP_S, AP_M and AP_L, which respectively concentrate on objects of small size ($32\times 32-$), medium size ($32\times 32$ $\sim$ $96\times 96$) and large size ($96\times 96+$).

During anchor configurations searching, we sample anchor configurations and train Faster-RCNN [28] (combined with FPN [18]) using the sampled anchor configurations, then compare the performance of these models (regrading mAP as evaluation metrics) to reserve better anchor configurations and stop the poorer ones, following the method we proposed before. The search space is feature-map-wised as introduced. All the experiments are conducted on 4 servers with 8 Tesla V100 GPUs, using the Pytorch framework [24, 6]. ResNet-50 [12] pre-trained on ImageNet [29] is used as the shared backbone networks. We use SGD (momentum = 0.9) with batch size of 64 and train 12 epochs in total with an initial learning rate of 0.02, and decay the learning rate by 0.1 twice during training.

We first evaluate the effectiveness of AABO over 3 large-scale detection datasets: COCO [20], VG [16] (including VG₁₀₀₀ and VG₃₀₀₀) and ADE [35]. We use Faster-RCNN [28] combined with FPN [18] as our detector, and the baseline model is FPN with default anchor configurations. The results are shown in Table 2 and the optimal anchors searched out by AABO are reported in the appendix.

It’s obvious that AABO outperforms Faster-RCNN with default anchor settings among all the 3 datasets. Specifically, AABO improves mAP by 2.4% on COCO, 1.5% on VG₁₀₀₀, 0.5% on VG₃₀₀₀, and 1.6% on ADE. The results illustrate that the pre-defined anchor used in common-used detectors are not optimal. Treat anchor configurations as hyper-parameters and optimize them using AABO can assist to determine better anchor settings and improve the performance of the detectors without increasing the complexity of the network.

Note that the searched anchors increase all the AP metrics, and the improvements on AP_L are always more significant than AP_S and AP_M : AABO boosts AP_L by 5% on COCO, 2.5% on VG₁₀₀₀, 1.1% on VG₃₀₀₀, and 1.5% on ADE. These results indicate that anchor configurations determined by AABO concentrate better on all objects, especially on the larger ones. It can also be found that AABO is especially useful for the large-scale object detection dataset such as VG₃₀₀₀. We conjecture that this is because the searched anchors can better capture the various sizes and shapes of objects in a large number of categories.

After searching out optimal anchor configurations via AABO, we apply them on several other backbones and detectors to study the generalization property of the anchor settings. For backbone, we change ResNet-50 [12] to ResNet-101 [12] and ResNeXt-101 [33], with detector (FPN) and other conditions constant. For detectors, we apply our searched anchor settings on several state-of-the-art detectors: a) Mask RCNN [11], b) RetinaNet [19], which is a one-stage detector, c) DCNv2 [36], and d) Hybrid Task Cascade (HTC) [7], with different backbones: ResNet-101 and ResNeXt-101. All the experiments are conducted on COCO.

The results are reported in Table 3. We can observe that the optimal anchors can consistently boost the performance of SOTA detectors, whether one-stage methods or two-stage methods. Concretely, the optimal anchors bring 2.1% mAP improvement on FPN with ResNet-101, 1.9% on FPN with ResNeXt-101, 2.0% on Mask RCNN, 1.4% on RetinaNet, 2.4% on DCNv2, and 1.4% improvement on HTC. The results demonstrate that our optimal anchors can be widely applicable across different network backbones and SOTA detection algorithms, including both one-stage and two-stage detectors. We also evaluate these optimized SOTA detectors on COCO test-dev, and the results are reported in the appendix. The performance improvements on val split and test-dev are consistent.

Comparison with other anchor initialization methods. In this section, we compare AABO with several existing anchor initialization methods: a) Pre-define anchor settings, which is used in most modern detectors. b) Use k-means to obtain clusters and treat them as default anchors, which is used in YOLOv2 [27]. c) Use random search to determine anchors. d) Use AABO combined with Hyperband [17] to determine anchors. e) Use AABO (combined with sub-sampling) to determine anchors. Among all these methods, the latter three use HPO methods to select anchor boxes automatically, while a) and b) use naive methods like handcrafting and k-means. The results are recorded in Table 4.

Among all these anchor initialization methods, our proposed approach can boost the performance most significantly, bring 2.4% improvement than using default anchors, while the improvements of other methods including statistical methods and previous HPO methods are less remarkable. The results illustrate that the widely used anchor initialization approaches might be sub-optimal, while AABO can fully utilize the ability of advanced detection systems.

Comparison with other HPO methods. As Table 5 shows, our proposed method could find better anchor configurations in fewer trials and can improve the performance of the detector significantly: With single search space, AABO combined with HB and SS boosts the mAP of FPN [18] from 36.4% to 37.8% and 38.3% respectively, while random search only boosts 36.4% to 37.2%. With feature-map-wised search space, AABO combined with HB and SS can obtain 38.2% and 38.8% mAP respectively, while random search fails to converge due to the huge and flexible search space. The results illustrate the effectiveness and the high efficiency of our proposed approach.

Comparison with other anchor optimization methods. We also compare AABO with some previous anchor optimization methods like [34] and MetaAnchor [32]. As shown in Table 6, all these methods can boost the performance of detectors, while our method brings 2.4% mAP improvement on Faster-RCNN and 1.4% on RetinaNet, and the other two methods only bring 1.0% improvement, which demonstrates the superiority of our proposed AABO.

In this section, we study the effects of all the components used in AABO: a) Treat anchor settings as hyper-parameters, then use HPO methods to search them automatically. b) Use Bayesian Optimization method. c) Use sub-sampling method to determine the reserved anchors. d) Feature-map-wised search space.

As shown in Table 7, using HPO methods such as random search to optimize anchors can bring 0.8% performance improvement, which indicates the default anchors are sub-optimal. Using single search space (not feature-map-wised), AABO combined with HB brings 1.4% mAP improvement, and AABO combined with SS brings 1.9% mAP improvement, which demonstrates the advantage of BO and accurate estimation of acquisition function. Besides, our tight and adaptive feature-map-wised search space can give a guarantee to search out better anchors with limited computation resources, and brings about 0.5% mAP improvement as well. Our method AABO can increase mAP by 2.4% overall.

In preliminary analysis, we search for better RPN head architecture in FPN [18] as well as anchor settings simultaneously, to compare the respective contributions of changing RPN head architecture and anchor settings. The optimal hyper-parameters are shown in Table 8. Since the search space for RPN head architecture and anchor settings are both relatively small, the performance increase is not very significant.

In this section, we record the best configurations searched out by AABO and analyze the difference between the results of default Faster-RCNN [28] and optimized Faster-RCNN.

As we design an adaptive feature-map-wised search space for anchor optimization, anchor configurations distribute variously in different layers of FPN [18]. Table 9 shows the optimal anchor configurations in FPN for COCO [20] dataset. We can observe that anchor scales and anchor ratios are larger and more diverse in shallower layers of FPN, while anchors tend to be smaller and more square in deeper layers.

After searching out optimal anchor configurations via AABO, we apply them on several SOTA detectors to study the generalization property of the anchor settings. In this section, we report the performance of these optimized detectors on COCO test-dev split. The results are shown in Table 10.

It can be seen that the optimal anchors can consistently boost the performance of SOTA detectors on both COCO val split and COCO test-dev. Actually, the mAP of the optimized detectors on test-dev is even higher than the mAP on val, which illustrates that the optimized anchor settings could bring consistent performance improvements on val split and test-dev.

In this section, Figure 5 and Figure 6 give some qualitative result comparisons of Faster-RCNN [28] with default anchors and optimal anchors.

As illustrated in Figure 5, more larger and smaller objects can be detected using our optimal anchors, which demonstrates that our optimal anchors are more diverse and suitable for a certain dataset. And there are some other differences shown in Figure 6: Using optimal anchor settings, the predictions of Faster-RCNN are usually tighter, more precise and concise. While the predictions are more inaccurate and messy when using pre-defined anchors. Specifically, there exist many bounding boxes in a certain position, which usually are different parts of one same object and overlap a lot.