---
abstract: 'Thanks to the success of object detection technology, we can retrieve objects of the specified classes even from huge image collections. However, the current state-of-the-art object detectors (such as Faster R-CNN) can only handle pre-specified classes. In addition, large amounts of positive and negative visual samples are required for training. In this paper, we address the problem of open-vocabulary object retrieval and localization, where the target object is specified by a textual query (e.g., a word or phrase). We first propose Query-Adaptive R-CNN, a simple extension of Faster R-CNN adapted to open-vocabulary queries, by transforming the text embedding vector into an object classifier and localization regressor. Then, for discriminative training, we then propose negative phrase augmentation (NPA) to mine hard negative samples which are visually similar to the query and at the same time semantically mutually exclusive of the query. The proposed method can retrieve and localize objects specified by a textual query from one million images in only 0.5 seconds with high precision.'
author:
- |
    Ryota Hinami$^{1, 2}$ and Shin’ichi Satoh$^{2, 1}$\
    $^{1}$The University of Tokyo, $^{2}$National Institute of Infomatics\
    [hinami@nii.ac.jp, satoh@nii.ac.jp]{}
bibliography:
- 'QRCN.bib'
title: |
    Discriminative Learning of Open-Vocabulary Object Retrieval\
    and Localization by Negative Phrase Augmentation
---

Introduction {#sec:intro}
============

Our goal is to retrieve objects from large-scale image database and localize their spatial locations given a textual query. The task of object retrieval and localization has many applications such as spatial position-aware image searches [@Hinami2017] and it recently has gathered much attention from researchers. While much of the previous work mainly focused on object instance retrieval wherein the query is an image [@Shen2012; @Taoa; @Tolias2015], recent approaches [@Aytar2014; @Hinami2016] enable retrieval of more generic concepts such as an object category. Although such approaches are built on the recent successes of object detection including that of R-CNN [@Girshick2014], object detection methods can generally handle only closed sets of categories (e.g., PASCAL 20 classes), which severely limits the variety of queries when they are used as retrieval systems. Open-vocabulary object localization is also a hot topic and many approaches are proposed to solve this problem [@Plummer2015; @Chen2017]. However, most of them are not scalable to make them useful for large-scale retrieval.

![Training examples in open-vocabulary object detection. (a) positive example of skier classifier. (b) examples without positive annotation, which can be positive. (c) examples without positive annotation from an image that contains a positive example. (d) proposed approach to select hard and true negative examples by using linguistics knowledge. []{data-label="fig:top"}](top.pdf){width="1.00\linewidth"}

We first describe [*Query-Adaptive*]{} R-CNN as an extension of the Faster R-CNN [@Ren2015] object detection framework to open-vocabulary object detection simply by adding a component called a [*detector generator*]{}. While Faster R-CNN learns the class-specific linear classifier as learnable parameters of the neural network, we generate the weight of the classifier adaptively from text descriptions by learning the detector generator (Fig. \[fig:pipeline\]b). All of its components can be trained in an end-to-end manner. In spite of its simple architecture, it outperforms all state-of-the-art methods in the Flickr30k Entities phrase localization task. It can also be used for large-scale retrievals in the manner presented in [@Hinami2016].

However, training a discriminative classifier is harder in the open-vocabulary setting. Closed-vocabulary object detection models such as Faster R-CNN are trained using many negative examples, where a sufficient amount of good-quality negative examples is shown to be important for learning a discriminative classifier [@Felzenszwalb2010; @Shrivastava2016]. While closed-vocabulary object detection can use all regions without positive labels as negative data, in open-vocabulary detection, it is not guaranteed that a region without a positive label is negative. For example, as shown in Fig. \[fig:top\]b, a region with the annotation `a man` is not always negative for `skier`. Since training data for open-vocabulary object detection is generally composed of images, each having region annotations with free descriptions, it is nearly impossible to do an exhaustive annotation throughout the dataset for all possible descriptions. Another possible approach is to use the regions without positive labels in the image that contains positive examples, as shown in Fig. \[fig:top\]c. Although they can be guaranteed to be positive by carefully annotating the datasets, negative examples are only limited to the objects that cooccur with the learned class.

To exploit negative data in open-vocabulary object detection, we use mutually exclusive relationships between categories. For example, an object with a label `dog` is guaranteed to be negative for the `cat` class because `dog` and `cat` are mutually exclusive. In addition, we propose an approach to select [*hard negative*]{} phrases that are difficult to discriminate (e.g., selecting `zebra` for `horse`). This approach, called [*negative phrase augmentation (NPA)*]{}, significantly improves the discriminative ability of the classifier and improves the retrieval performance by a large margin.

Our contributions are as follows. 1) We propose Query-Adaptive R-CNN, an extension of Faster R-CNN to open vocabulary, that is a simple yet strong method of open-vocabulary object detection and that outperforms all state-of-the-art methods in the phrase localization task. 2) We propose negative phrase augmentation (NPA) to exploit hard negative examples when training for open-vocabulary object detection, which makes the classifier more discriminative and robust to distractors in retrieval. Our method can accurately find objects amidst one million images in 0.5 second.

Related work
============

[**Phrase localization.**]{} Object grounding with natural language descriptions has recently drawn much attention and several tasks and approaches have been proposed for it [@Guadarrama2014; @Hu2015f; @Kazemzadeh2014; @Mao2016; @Plummer2015]. The most related task to ours is the phrase localization introduced by Plummer et al. [@Plummer2015], whose goal is to localize objects that corresponds to noun phrases in textual descriptions from an image. Chen et al. [@Chen2017] is the closest to our work in terms of learning region proposals and performing regression conditioned upon a query. However, most phrase localization methods are not scalable and cannot be used for retrieval tasks. Some approaches [@Plummer2017; @Wang] learn a common subspace between the text and image for phrase localization. Instead of learning the subspace between the image and sentence as in standard cross-modal searches, they learn the subspace between a region and a phrase. In particular, Wang et al. [@Wang] use a deep neural network to learn the joint embedding of images and text; their training uses structure-preserving constraints based on structured matching. Although these approaches can be used for large-scale retrieval, their accuracy is not as good as recent state-of-the-art methods.

[**Object retrieval and localization.**]{} Object retrieval and localization have been researched in the context of particular object retrieval [@Shen2012; @Taoa; @Tolias2015], where a query is given as an image. Aytar et al. [@Aytar2014] proposed retrieval and localization of generic category objects by extending the object detection technique to large-scale retrieval. Hinami and Satoh [@Hinami2016] extended the R-CNN to large-scale retrieval by using approximate nearest neighbor search techniques. However, they assumed that the detector of the category is given as a query and require many sample images with bounding box annotations in order to learn the detector. Several other approaches have used the external search engines (e.g., Google image search) to get training images from textual queries [@Arandjelovi2012; @Chatfield2015]. Instead, we generate an object detector directly from the given textual query by using a neural network.

[**Parameter prediction by neural network.**]{} Query-Adaptive R-CNN generates the weights of the detector from the query instead of learning them by backpropagation. The dynamic filter network [@DeBrabandere2016] is one of the first methods that generate neural network parameters dynamically conditioned on an input. Several subsequent approaches use this idea in zero-shot learning [@Ba2016] and visual question answering [@Noh2016]. Zhang et al. [@Zhang2017] integrates this idea into the Fast R-CNN framework by dynamically generating the classifier from the text in a similar manner to [@Ba2016]. We extend this work to the case of large-scale retrieval. The proposed Query-Adaptive R-CNN generates the regressor weights and learn the region proposal network following Faster R-CNN. It enables precise localization with fewer proposals, which makes the retrieval system more memory efficient. In addition, we propose a novel hard negative mining approach, called negative phrase augmentation, which makes the generated classifier more discriminative.

Query-Adaptive R-CNN
====================

Query-adaptive R-CNN is a simple extension of Faster R-CNN to open-vocabulary object detection. While Faster R-CNN detects objects of fixed categories, Query-Adaptive R-CNN detects any objects specified by a textual phrase. Figure \[fig:pipeline\] illustrates the difference between Faster R-CNN and Query-Adaptive R-CNN. While Faster R-CNN learns a class-specific classifier and regressor as parameters of the neural networks, Query-Adaptive R-CNN generates them from the query text by using a detector generator. Query-Adaptive R-CNN is a simple but effective method that surpasses state-of-the-art phrase localization methods and can be easily extended to the case of large-scale retrieval. Furthermore, its retrieval accuracy is significantly improved by a novel training strategy called negative phrase augmentation (Sec. \[sec:train\]).

Architecture {#sec:qrcn_arch}
------------

The network is composed of two subnetworks: a [*region feature extractor*]{} and [*detector generator*]{}, both of which are trained in an end-to-end manner. The region feature extractor takes an image as input and outputs features extracted from sub-regions that are candidate objects. Following Faster R-CNN [@Ren2015], regions are detected using a region proposal network (RPN) and the features of the last layer (e.g., fc7 in VGG network) are used as region features. The detector generator takes a text description as an input and outputs a linear classifier and regressor for the description (e.g., if `a dog` is given, `a dog` classifier and regressor are output). Finally, a confidence and a regressed bounding box are predicted for each region by applying the classifier and regressor to the region features.

![Difference in network architecture between (a) Faster R-CNN and (b) Query-Adaptive R-CNN. While Faster R-CNN learns the classifier of a closed set of categories as learnable parameters of neural networks, Query-Adaptive R-CNN generates a classifier and regressor adaptively from a query text by learning a detector generator that transforms the text into a classifier and regressor. ](pipeline.pdf){width="1.00\linewidth"}

\[fig:pipeline\]

[**Detector generator.**]{} The detector generator transforms the given text $t$ into a classifier $\mathbf{w}^c$ and regressor $(\mathbf{w}^r_x, \mathbf{w}^r_y, \mathbf{w}^r_w, \mathbf{w}^r_h)$, where $\mathbf{w}_c$ is the weight of a linear classifier and $(\mathbf{w}^r_x, \mathbf{w}^r_y, \mathbf{w}^r_w, \mathbf{w}^r_h)$ is the weight of a linear regressor in terms of $x$, $y$, width $w$, and height $h$, following [@Girshick2014]. We first transform a text $t$ of variable length into a text embedding vector $\mathbf{v}$. Other phrase localization approaches uses the Fisher vector encoding of word2vec [@Klein2015; @Plummer2015] or long-short term memory (LSTM) [@Chen2017] for the phrase embedding. However, we found that the simple mean pooling of word2vec [@Mikolov2013] performs better than these methods for our model (comparisons given in the supplemental material). The text embedding is then transformed into a detector, i.e., $\mathbf{w}_c=G_c(\mathbf{v})$ and $(\mathbf{w}^r_x, \mathbf{w}^r_y, \mathbf{w}^r_w, \mathbf{w}^r_h)=G_r(\mathbf{v})$. Here, we use a linear transformation for $G_c$ (i.e., $\mathbf{w}_c=\mathbf{W}\mathbf{v}$, where $\mathbf{W}$ is a projection matrix). For the regressor, we use a multi-layer perceptron with one hidden layer to predict each of $(\mathbf{w}^r_x, \mathbf{w}^r_y, \mathbf{w}^r_w, \mathbf{w}^r_h)=G_r(\mathbf{v})$. We tested various architectures for $G_r$ and found that sharing the hidden layer and reducing the dimension of the hidden layer (up to $16$) does not adversely affect the performance, while at the same time it significantly reduces the number of parameters (see Sec. \[sec:exp\_ph\] for details).

Training with Negative Phrase Augmentation {#sec:train}
------------------------------------------

All components of Query-Adaptive R-CNN can be jointly trained in an end-to-end manner. The training strategy basically follows that of Faster R-CNN. The differences are shown in Figure \[fig:neg\_aug\]. Faster R-CNN is trained with the fixed closed set of categories (Fig. \[fig:neg\_aug\]a), where all regions without a positive label can be used as negative examples. On the other hand, Query-Adaptive R-CNN is trained using the open-vocabulary phrases annotated to the regions (Fig. \[fig:neg\_aug\]b), where sufficient negative examples cannot be used for each phrase compared to Faster R-CNN because a region without a positive label is not guaranteed to be negative in open-vocabulary object detection. We solve this problem by proposing negative phrase augmentation (NPA), which enables us to use good quality negative examples by using the linguistic relationship (e.g., mutually exclusiveness) and the confusion between the categories (Fig. \[fig:neg\_aug\]c). It significantly improves the discriminative ability of the generated classifiers.

![Difference in training between (a) closed-vocabulary and (b) open-vocabulary object detection. The approach of NPA is illustrated in (c).[]{data-label="fig:neg_aug"}](neg_aug.pdf){width="1.03\linewidth"}

### Basic Training {#sec:basic}

First, we describe the basic training strategy without NPA (Fig. \[fig:neg\_aug\]b). Training a Query-Adaptive R-CNN requires the phrases and their corresponding bounding boxes to be annotated. For the $i$th image (we use one image as a minibatch), let us assume that $C_i$ phrases are associated with the image. The $C_i$ phrases can be considered as the classes to train in the minibatch. The labels $\mathbf{L}_i \in \{0,1\}^{C_i\times n_r}$ are assigned to the region proposals generated by RPN (each of the dotted rectangles in Fig \[fig:neg\_aug\]b); a positive label is assigned if the box overlaps the ground truth box by more than 0.5 in IoU and negative labels are assigned to other RoIs under the assumption that all positive objects of $C_i$ classes are annotated (i.e., regions without annotations are negative within the image).[^1] We then compute the classification loss by using the training labels and classification scores.[^2] The loss in terms of RPN and bounding box regression is computed in the same way as Faster R-CNN [@Ren2015].

### Negative Phrase Augmentation {#sec:neg}

Here, we address the difficulty of using negative examples in the training of open-vocabulary object detection. As shown in Fig. \[fig:top\]b, our generated classifier is not discriminative enough. The reason is the scarcity of negative examples when using the training strategy described in Sec. \[sec:basic\]; e.g., the `horse` classifier is not learned with the `zebra` as a negative example except for the rare case that both a `zebra` and a `horse` are in the same image. Using hard negative examples has proven to be effective in the object detection to train a discriminative detector [@Felzenszwalb2010; @Girshick2014; @Shrivastava2016]. However, adding negative examples is usually not easy in the open-vocabulary setting, because it is not guaranteed that a region without a positive label is negative. For example, an object with the label `man` is not a negative of `person` even though `person` is not annotated. There are an infinite number of categories in open-vocabulary settings, which makes it difficult to exhaustively annotate all categories throughout the dataset.

How can we exploit hard examples that are guaranteed to be negative? We can make use of the mutually exclusive relationship between categories: e.g., an object with a `dog` label is negative for `cat` because `dog` and `cat` are mutually exclusive. There are two ways we can add to a minibatch: add negative images (regions) or negative phrases. Adding negative phrases (as in Fig. \[fig:neg\_aug\]c) is generally better because it involves a much smaller additional training cost than adding images in terms of the both computational cost and GPU memory usage. In addition, to improve the discriminative ability of the classifier, we select only hard negative phrases by mining the confusing categories. This approach, called [*negative phrase augmentation (NPA)*]{}, is a generic way of exploiting hard negative examples in open-vocabulary object detection and leads to large improvements in accuracy, as we show in Sec. \[sec:exp\_ret\].

[**Confusion table.**]{} We create a confusion table that associates a category with its hard negative categories, from which negative phrases are picked as illustrated in Fig. \[fig:neg\_aug\]c. To create the entry for category $c$, we first generate the candidate list of hard negative categories by retrieving the top 500 scored objects from all objects in the validation set of Visual Genome [@Krishna2016] (using $c$ as a query). After that, we remove the mutually non-exclusive category relative to $c$ from the list. Finally, we aggregate the list by category and assign a weight to each category. Each of the registered entries becomes like [`dog:{cat:0.5, horse:0.3, cow:0.2}`]{}. The weight corresponds to the probability of selecting the category in NPA, which is computed based on the number of appearances and their ranks in the candidate list.[^3] [**Removal of mutually non-exclusive phrases.**]{} To remove non-mutually exclusive phrases from the confusion table, we use two approaches that estimate whether the two categories are mutually exclusive or not. 1) The first approach uses the [*WordNet hierarchy*]{}: if two categories have parent-child relationships in WordNet [@Miller1995], they are not mutually exclusive. However, the converse is not necessarily true; e.g., `man` and `skier` are not mutually exclusive but do not have the parent-child relationship in the WordNet hierarchy. 2) As an alternative approach, we propose to use [*Visual Genome annotation*]{}: if two categories co-occur more often in the Visual Genome dataset [@Krishna2016], these categories are considered to be not mutually exclusive.[^4] These two approaches are complementary, and they improve detection performance by removing the mutually non-exclusive words (see Sec. \[sec:exp\_ret\]).

[**The training pipeline**]{} with NPA is as follows:

(1) [**Update the confusion table:**]{} The confusion table is updated periodically (after every 10k iterations in our study). Entries were created for categories that frequently appeared in 10k successive batches (or the whole training set if the size of the dataset is not large).

(2) [**Add hard negative phrases:**]{} Negative phrases are added to each of the $C_i$ phrases in a minibatch. We replace the name of the category in each phrase with its hard negative category (e.g., generate `a running woman` for `a running man`), where the category name is obtained by extracting nouns. A negative phrase is randomly selected from the confusion table on the basis of the assigned probability.

(3) [**Add losses:**]{} As illustrated in Fig. \[fig:neg\_aug\]c, we only add negative labels to the regions where a positive label is assigned to the original phrase. The classification loss is computed only for the regions, which is added to the original loss.

Large-Scale Object Retrieval {#sec:ret}
============================

Query-Adaptive R-CNN can be used for large-scale object retrieval and localization, because it can be decomposed into a query-independent part and a query-dependent part, i.e., a region feature extractor and detector generator. We follow the approach used in large-scale R-CNN [@Hinami2016], but we overcome its two critical drawbacks. First, a large-scale R-CNN can only predict boxes included in the region proposals; these are detected offline even though the query is unknown at the time; therefore, to get high recall, a large number of object proposals should be used, which is memory inefficient. Instead, we generate a regressor as well as a classifier, which enables more accurate localization with fewer proposals. Second, a large-scale R-CNN assumes that the classifier is given as a query, and learning a classifier requires many samples with bounding annotations. We generate the classifier from a text query directly by using the detector generator of Query-Adaptive R-CNN. The resulting system is able to retrieve and localize objects from a database with [*one million images*]{} in [*less than one second*]{}.

**Database indexing.** For each image in the database, the region feature extractor extracts region proposals and corresponding features. We create an index for the region features in order to speed up the search. For this, we use the IVFADC system [@Jegou2011] in the manner described in [@Hinami2016].

**Searching.** Given a text query, the detector generator generates a linear classifier and bounding box regressor. The regions with high classification scores are then retrieved from the database by making an IVFADC-based search. Finally, the regressor is applied to the retrieved regions to obtain the accurately localized bounding boxes.

\[tab:phrase\]

\[tab:res\_regressor\]

Experiments
===========

Experimental Setup
------------------

**Model:** Query-Adaptive R-CNN is based on VGG16 [@Simonyan2015], as in other work on phrase localization. We first initialized the weights of the VGG and RPN by using Faster R-CNN trained on Microsoft COCO [@Lin2014]; the weights were then fine-tuned for each dataset of the evaluation. In the training using Flickr30k Entities, we first pretrained the model on the Visual Genome dataset using the object name annotations. We used Adam [@Kingma2015] with a learning rate starting from 1e-5 and ran it for 200k iterations.

**Tasks and datasets:** We evaluated our approaches on two tasks: phrase localization and open-vocabulary object detection and retrieval. The **phrase localization task** was performed on the Flickr30k Entities dataset [@Plummer2015]. Given an image and a sentence that describes the image, the task was to localize region that corresponds to the phrase in a sentence. Flickr30k datasets contain 44,518 unique phrases, where the number of words of each phrase is 1–8 (2.1 words on average). We followed the evaluation protocol of [@Plummer2015]. We did not use Flickr30k Entities for the retrieval task because the dataset is not exhaustively annotated (e.g., not all men appearing in the dataset are annotated with `man`), which makes it difficult to evaluate with a retrieval metric such as AP, as discussed in Plummer et al. [@Plummer2017]. Although we cannot evaluate the retrieval performance directly on the phrase localization task, we can make comparisons with other approaches and show that our method can handle a wide variety of phrases.

The **open-vocabulary object detection and retrieval task** was evaluated in the same way as the standard object detection task. The difference was the assumption that we do not know the target category at training time in open-vocabulary settings; i.e., the method does not tune in to a specific category, unlike the standard object detection task. We used the Visual Genome dataset [@Krishna2016] and selected the 100 most frequently object categories as queries among its 100k or so categories.[^5] [^6] We split the dataset into training, validation, and test sets following [@Johnson2015]. We also evaluated our approaches on the PASCAL VOC 2007 dataset, which is a widely used dataset for object detection.[^7] As metrics, we used top-k precision and average precision (AP), computed from the region-level ranked list as in the standard object detection task.[^8]

![image](neg_qual.pdf){width="1.00\linewidth"}

\[fig:aug\_qual\]

Phrase localization {#sec:exp_ph}
-------------------

**Comparison with state-of-the-art.** We compared our method with state-of-the-art methods on the Flickr30k Entities phrase localization task. We categorized the methods into two types, i.e., non-scalable and scalable methods (Tab. \[tab:phrase\]). 1) [*Non-scalable methods*]{} cannot be used for large-scale retrieval because their query-dependent components are too complex to process a large amount of images online, and 2) [*Scalable methods*]{} can be used for large-scale retrieval because their query-dependent components are easy to scale up (e.g., the $L_2$ distance computation); these include common subspace-based approaches such as CCA. Our method also belongs to the scalable category. We used a simple model without a regressor and NPA in the experiments.

Table \[tab:phrase\] compares Query-Adaptive R-CNN with the state-of-the-art methods. Our model achieved [*65.21%*]{} in accuracy and outperformed all of the previous state-of-the-art models including the non-scalable or joint localization methods. Moreover, it significantly outperformed the scalable methods, which suggests the approach of predicting the classifier is better than learning a common subspace for the open-vocabulary detection problem.

![image](graph.pdf){width="1.00\linewidth"}

\[fig:res\_aug\]

[**Bounding box regressor.**]{} To demonstrate the effectiveness of the bounding box regressor for precise localization, we conducted evaluations with the regressor at different IoU thresholds. As explained in Sec. \[sec:qrcn\_arch\], the regressor was generated using $G_r$, which transformed 300-d text embeddings $x$ into 4096-d regressor weights $\mathbf{w}^r_x$, $\mathbf{w}^r_y$, $\mathbf{w}^r_w$, and $\mathbf{w}^r_h$. We compared three network architectures for $G_r$: 1) `300-n(-4096)` MLP having a hidden layer with $n$ units that is shared across the four outputs, 2) `300(-n-4096)` MLP having a hidden layer that is not shared, and 3) `300(-4096)` linear transformation (without a hidden layer).

Table \[tab:res\_regressor\] shows the results with and without regressor. The regressor significantly improved the accuracy with high IoU thresholds, which demonstrates that the regressor improved the localization accuracy. In addition, the accuracy did not decrease as a result of sharing the hidden layer or reducing the number of units in the hidden layer. This suggests that the regressor lies in a very low-dimensional manifold because the regressor for one concept can be shared by many concepts (e.g., the `person` regressor can be used for `man`, `woman`, `girl`, `boy`, etc.). The number of parameters was significantly reduced by these tricks, to even fewer than in the linear transformation. The accuracy slightly decreased with a threshold of 0.5, because the regressor was not learned properly for the categories that did not frequently appear in the training data.

\[tab:open\]

\[tab:confuse\]

![image](large_qual.pdf){width="1.00\linewidth"}

\[fig:large\_qual\]

Open-Vocabulary Object Retrieval {#sec:exp_ret}
--------------------------------

**Main comparison.** Open-vocabulary object detection and retrieval is a much more difficult task than phrase localization, because we do not know how many objects are present in an image. We used NPA to train our model. As explained in Sec. \[sec:neg\], we used two strategies, [*Visual Genome annotation (VG)*]{} and [*WordNet hierarchy (WN)*]{}, to remove mutually non-exclusive phrases from the confusion table. As a baseline, we compared with region-based CCA [@Plummer2017], which is scalable and shown to be effective for phrase localization; for a fair comparison, the subspace was learned using the same dataset as ours. An approximate search was not used to evaluate the actual performance at open-vocabulary object detection.

Table \[tab:open\] compares different training strategies. NPA significantly improved the performance: [*more than 25% relative improvement*]{} for all metrics. Removing mutually non-exclusive words also contributed the performance: WN and VG both improved performance (5.8% and 6.9% relative AP gain, respectively). Performance improved even further by combining them (11.8% relative AP gain), which shows they are complementary. AP was much improved by NPA for the PASCAL dataset as well (47% relative gain). However, the performance was still much poorer than those of the state-of-the-art object detection methods [@JosephRedmon2016; @Ren2015], which suggests that there is a large gap between open-vocabulary and closed-vocabulary object detection.

**Detailed results of NPA.** To investigate the effect of NPA, we show the AP with and without NPA for individual categories in Figure \[fig:res\_aug\], which are sorted by relative AP improvement. It shows that AP improved especially for animals (`elephant`, `cow`, `horse`, etc.) and person (`skier`, `surfer`, `girl`), which are visually similar within the same upper category. Table \[tab:confuse\] shows the most confused category and its total count in the top 100 search results for each query, which shows what concept is confusing for each query and how much the confusion is reduced by NPA.[^9] This shows that visually similar categories resulted in false positive without NPA, while their number was suppressed by training with NPA. The reason is that these confusing categories were added for negative phrases in NPA, and the network learned to reject them. Figure \[fig:aug\_qual\] shows the qualitative search results for each query with and without NPA (and CCA as a baseline), which also showed that NPA can discriminate confusing categories (e.g., `horse` and `zebra`). These results clearly demonstrate that NPA significantly improves the discriminative ability of classifiers by adding hard negative categories.

\[tab:res\_large\]

**Large-scale experiments.** Finally, we evaluated the scalability of our method on a large image database. We used one million images from the ILSVRC 2012 training set for this evaluation. Table \[tab:res\_large\] show the speed and memory. The mean and standard deviation of speed are computed over 20 queries in PASCAL VOC dataset. Our system could retrieve objects from one million images in around 0.5 seconds. We did not evaluate accuracy because there is no such large dataset with bounding box annotations.[^10] Figure \[fig:large\_qual\] shows the retrieval results from one million images, which demonstrates that our system can accurately retrieve and localize objects from a very large-scale database.

Conclusion
==========

Query-Adaptive R-CNN is a simple yet strong framework for open-vocabulary object detection and retrieval. It achieves state-of-the-art performance on the Flickr30k phrase localization benchmark and it can be used for large-scale object retrieval by textual query. In addition, its retrieval accuracy can be further increased by using a novel training strategy called negative phrase augmentation (NPA) that appropriately selects hard negative examples by using their linguistic relationship and confusion between categories. This simple and generic approach significantly improves the discriminative ability of the generated classifier. [**Acknowledgements:**]{} This work was supported by JST CREST JPMJCR1686 and JSPS KAKENHI 17J08378.

 {#section .unnumbered}

Detailed Analysis on Phrase Localization
========================================

With or Without Regression
--------------------------

Figure \[fig:reg\_ph\_qual\] compares the results with and without bounding box regression. We use the model of `300-16(-4096)` to generate the regressor (explained in our paper in Sec.5.2). Figure \[fig:reg\_ph\_qual\]a shows the successful cases. The regression is effective especially for the frequently appeared categories in training data such as `person` and `dog` because the accurate regressor can be learned by using many examples. The regression was succeeded for several uncommon categories such as `potter` and `gondola`; the reason is that regressor can be shared with other common categories, e.g., `person` and `boat` regressor can be used for `potter` and `gondola`, respectively. Figure \[fig:reg\_ph\_qual\]b shows the failure cases, which include the categories with ambiguous boundary (e.g., `sidewalk` and `mud`). The regressor does not work for such categories. In addition, if the category is not frequently appeared in training data, the regressor moves the bounding box into the wrong direction. Future work includes automatically determining whether to perform bounding box regression or not.

![image](reg_ph_qual.pdf){width="1.00\linewidth"}

With or Without Negative Phrase Augmentation
--------------------------------------------

Table \[tab:aug\_ph\_quan\] shows the phrase localization performance with and without negative phrase augmentation (NPA). It shows that the phrase localization performance is not improved by training with NPA. As explained in our paper, it is due to the difference between the phrase localization and object detection tasks; phrase localization assumes there is only one relevant object in the image while object detection places no assumption on the number of objects. Because of this, in the phrase localization task, we can benefit from NPA only when confusing objects appear in the single image. Figure \[fig:aug\_ph\_qual\]a shows such cases: e.g., when two persons appear in the same image, the method with NPA can select the appropriate person that is relevant to the query. However, since such cases are rare in the Flickr30k Entities dataset, NPA does not contribute to performance. Figure \[fig:aug\_ph\_qual\]b shows the failure cases of NPA. The method with NPA tends to predict the small bounding box in which other objects do not appear. The reason is that NPA cannot handle highly overlapped objects appropriately. For example, in the third example in Fig. \[fig:aug\_ph\_qual\], the `sand` region may have high scores for the `deer`. If there are many such cases in the validation set, the `sand` is added to hard negative phrase for the `deer`. The `sand` classifier thus predicts low score to the regions that are overlapped with the `deer`. Therefore, the method with NPA tends to predict the small box that contains only the (part of) relevant object. This is the limitation of NPA and causes the accuracy decrease in phrase localization task.

![image](aug_ph_qual.pdf){width="1.00\linewidth"}

Ablation Studies
----------------

We here present the detailed analysis of our approach on the Flickr30k Entities phrase localization task and quantify our architectural design decisions. For the simplicity, in the comparison of the region proposal and text embedding, we used the pretrained Faster R-CNN model trained on the COCO object detection and finetuned it for phrase localization task. The bounding box regression and NPA are not used in this experiments.

[**Pretraining.**]{} Table \[tab:pre\] compares three pretrained models trained on 1) ImageNet classification, 2) PASCAL, and 3) COCO object detection. In addition, we pretrain the whole model including detector generator using Visual Genome dataset after initial pretraining of 1)–3). The results show that there is more than 4% difference in accuracy between simply using ImageNet pretrained model and pretraining on COCO and Visual Genome. Since Flickr30k Entities dataset does not contain many training examples for each object category, pretraining Faster R-CNN with large object detection datasets is important. Training on the Visual Genome dataset further improves the performance because it contains a much larger number of categories than COCO dataset and detector generator is also pretrained on such rich data.

[**Region proposal.**]{} Table \[tab:region\] compares three region proposal approaches: 1) selective search [@Uijlings2013], 2) region proposal network (RPN) trained on COCO dataset, which is frozen during the training of phrase localization, and 3) RPN finetuned on phrase localization task. The number of regions is 2000 for the selective search following [@Girshick2014] and 300 for the RPN following [@Ren2015]. In addition, we compared two region sampling strategies: random sampling used in [@Girshick2015; @Ren2015] and online hard example mining (OHEM) [@Shrivastava2016]. The results show that the RPN finetuned for phrase localization task generates much higher quality region proposals than others (12.41% increase in accuracy compared to the selective search), which demonstrates that learning region proposals play an important role in the phrase localization. OHEM further improved the accuracy by 1.56%.

[**Text embedding.**]{} Table \[tab:text\] compares five text embedding vectors: 1) Word2Vec [@Mikolov2013] trained on Google News dataset[^11], which is used in our paper, 2) Word2Vec trained on Flickr tags[^12] [@Li2015a], 3) Hybrid Gaussian-Laplacian mixture model (HGLMM) [@Klein2015], which is used in [@Plummer2015; @Plummer2017; @Wang], 4) Skip-thought vector (combine-skip model)[^13] [@Kiros2015], and 5) Long-short term memory (LSTM) that encodes a phrase into a vector in the manner described in [@Chen2017; @Rohrbach2016], which is learned jointly with other components of Query-Adaptive R-CNN. The second column of Table \[tab:text\] shows the dimension of the text embedding vector. This result shows that the performance is not much affected by the choice of the text embedding. The mean pooling of Word2Vec performs the best despite its simplicity.

Additional Examples of Negative Phrase Augmentation
===================================================

Figure \[fig:neg\_qual1\], \[fig:neg\_qual2\], and \[fig:neg\_qual3\] show additional examples of the negative phrase augmentation (corresponds to Fig. 4 in our paper). There are many false alarms between the confusing categories such as the animal (`zebra`, `bear`, and `giraffe`), person (`skier` and `child`), and vehicle (`boat`, `train`, and `bus`) without NPA, which are successfully discarded by training with NPA.

![image](neg_qual_1.pdf){width="1.00\linewidth"}

![image](neg_qual_2.pdf){width="1.00\linewidth"}

![image](neg_qual_3.pdf){width="1.00\linewidth"}

Additional Examples of Open-Vocabulary Object Retrieval and Localization
========================================================================

Figure \[fig:large\_qual\] shows the additional examples of object retrieval and localization (corresponds to Fig. 6 in our paper). Instead of the ILSVRC dataset used in our paper, we here used the Microsoft COCO dataset [@Lin2014] (40504 images from the validation set) that contains a wider variety of concepts. These results demonstrate that our system can accurately search the wide variety of objects specified by the natural language query.

![image](large_qual_sup.pdf){width="1.00\linewidth"}

[^1]: Although this assumption is not always true for datasets such as Flickr30k Entities, it nonetheless works well for them because exceptions are rare.

[^2]: Whereas Faster R-CNN uses the softmax cross entropy over the $C + 1$ (background) classes, where $C$ is the number of closed sets of a category, we use the sigmoid cross entropy because the $C_i$ classes are not always mutually exclusive and a background class cannot be defined in the context of open-vocabulary object detection.

[^3]: We compute the weight of each category as the sum of 500 minus the rank for all ranked results in the candidate lists normalized over all categories in order to sum to one.

[^4]: We set the ratio at 1% of objects in either category. For example, if there are 1000 objects with the `skier` label and 20 of those objects are also annotated with `man` (20/1000=2%), we consider that `skier` and `man` are not mutually exclusive.

[^5]: Since the WordNet synset ID is assigned to each object, we add objects with labels of hyponyms as positives (e.g., `man` is positive for the `person` category).

[^6]: We exclude the background (e.g., `grass`, `sky`, `field`), multiple objects (e.g., `people`, `leaves`), and ambiguous categories (e.g, `top`, `line`).

[^7]: We used the model trained on Visual Genome even for the evaluation on the PASCAL dataset because of the assumption that the target category is unknown.

[^8]: We did not separately evaluate the detection and retrieval tasks because both can be evaluated with the same metric.

[^9]: For each query, we scored all the objects in the Visual Genome testing set and counted the false alarms in the top 100 scored objects.

[^10]: adding distractors would also be difficult, because we cannot guarantee that relevant objects are not in the images.

[^11]: https://code.google.com/archive/p/word2vec/

[^12]: the model is provided by the author of [@Dong2016]

[^13]: We use the implementation and pre-trained model provided in https://github.com/ryankiros/skip-thoughts
