Deep Multiple Instance Hashing for Object-based Image Retrieval

1 Introduction

Content-based image retrieval (CBIR) has become an active topic in multimedia community since the early 1990s [Smeulders et al., 2000]. Classic CBIR systems take a single query image, and retrieve similar images in a holistic sense from an image repository. However, a user's search interest is usually an object or multiple objects in an image, rather than the entire image. Therefore, object-based (or localized contentbased) image retrieval has been defined in [Rahmani et al., 2008], where the user is only interested in a portion of an image. Previous object-based image retrieval methods [Zheng et al., 2006; Rahmani et al., 2008; Li and Liu, 2015] usually involve multiple steps, such as image segmentation, feature extraction and index creation. However, these steps are independent with one another, which would lead to unsatisfac- Department of Computer Science UNC-Charlotte, NC28223, USA jfan@uncc.edu tory results. In particular, the errors in the segmentation step will be propagated to the index, and it is difficult to find optimal hand-crafted features for index creation. On the other hand, most existing object-based image retrieval approaches concentrate on querying by a single object. However, users may also want to query about multiple objects, as illustrated in Fig. 1: in the upper example the user is interested in photos containing both human and horses, as in the query; in the lower case the user may want to write a political commentary about Obama and Putin but there is no group photo of them at hand. Due to the lack of ability to detect various objects, previous approaches will incur poor performance when they are directly used to cope with multi-object queries.

∗Corresponding author

Jianping Fan

Figure 1: Querying about multiple objects.

Recent advances in deep learning have proved that convolutional neural networks (CNNs) trained end-to-end can learn powerful feature representations. In terms of object detection, a number of techniques based on deep CNNs have been proposed [Ren et al., 2015; Liu et al., 2016] and achieved good results on some high-quality public image datasets like ImageNet, PASCAL VOC and MS COCO. However, these approaches necessitate large-scale training data with labels of object locations to learn models to harvest "objectness", whereas the labeling work is very tedious and expensive. It is often the case that we only have image-level object labels without object locations, i.e. weak labels for object detection

[Ren et al., 2016]. Multiple Instance Learning (MIL) [Russell et al., 2006] is a particular form of weakly supervised method which can solve the problem above. In MIL, data are labeled in the bag level, where each bag (image in our case) consists of multiple instances (object proposals). MIL assumes that a bag is positive if at least one instance in it is positive, and negative if all the instances in it are negative. The goal of a conventional MIL algorithm is to generate a classifier that will classify unseen bags correctly. Very recently, some CNNbased MIL methods have been proposed to solve the object detection problem by using weak labels [Ren et al., 2016; Kraus et al., 2016]. However, these methods are not suitable to address our problem. First, their objective is to reduce the error rate of object detection, while our task is to construct an object index such that similar objects have similar hash codes. It would result in inefficiency and low accuracy when using the learned CNN features (i.e. outputs of the layer before the prediction layer) from these methods for object retrieval directly, since those features are real vectors and not optimized for similarity search. Second, most of these methods generate large proposals from raw images and feed them into a pretrained CNN to obtain their features. The time cost is unacceptable for image retrieval tasks.

In this paper, a novel weakly-supervised Deep Multiple Instance Hashing (DMIH) framework is proposed for objectbased image retrieval. We integrate MIL and hashing learning on the basis of a popular CNN model to build the end-toend relation between a raw image and the binary hash codes of objects in it. Specifically, we cast the object detection of each object class as a binary MIL problem in which object proposals extracted from trainable multi-scale CNN feature maps (approximately representing sub-areas of different sizes in the input image) are considered as instances and the entire image is treated as a bag. Images containing objects of the class are positive bags, while the remaining ones are negative bags. Together with object predictor learning for each class, a global hash function is also trained to capture the semantic relationships among objects. To this end, we sample image pairs to decrease/increase the embedding distances between same-class/different-class objects in them, where we treat the most probable object proposal assessed by the corresponding object predictor as the object of the class. The whole deep model is optimized via back propagation. In this way, DMIH performs image feature learning, object detection and hash code learning jointly. Object detection helps hashing find correct object proposals and hashing learning provides a regularization for object detection by constraining semantic relationships, thus benefiting each other. After training, we use the hash codes of object proposals judged to be positive by object predictors to represent and index an image.

The main contributions are: (1) we propose a novel learning framework for object-based image retrieval which can well handle multi-object queries; (2) we unify feature learning, hashing learning and MIL based object detection via deep CNNs. The model can effectively generate hash codes of objects in images for retrieval; (3) experiments on three benchmark datasets demonstrate the learned hash codes well preserve the object-level similarity and DMIH outperforms baselines on both single-object and multi-object queries.

2 RelatedWork

Considering the high dimensionality of images, one critical challenge in CBIR is how to efficiently generate search results. Recently, hashing is recognized as an important technique for fast approximate similarity search. Generally speaking, hashing methods can be categorized into two classes: unsupervised and supervised methods. Unsupervised hashing methods generate compact hash codes by using random projection or training on unlabeled data [Gionis et al., 2000; Weiss et al., 2008; Lee et al., 2010]. The most representative one is Locality-Sensitive Hashing (LSH) [Gionis et al., 2000], which aimed at maximizing the probability that similar data instances are mapped to similar binary codes. In order to search for all groups of partial duplicate images in an image repository, Lee et al. [Lee et al., 2010] divided images into multi-scale regions and extracted min-hash [Chum et al., 2008] values for each region independently. Recent studies have shown that using supervised information can boost the performance of binary hash codes. Supervised hashing methods [Kulis and Darrell, 2009; Liu et al., 2012; Zhao et al., 2015] usually incorporate label information into pairwise similarity estimation for training effective hash functions. However, previous hashing methods were focused on mapping whole images or fixed regions of images into the Hamming space. Our work is different from theirs in that our goal is to learn a hash function for objects in images where the objects are detected automatically.

MIL has been leveraged for object-based image retrieval. Rahmani et al. [Rahmani et al., 2008] took images as bags and regions in images as instances. They required users to provide a set of query images with positive and negative labels (or via feedback), and then used MIL to train a set of hypotheses online to rank images. Zhang et al. [Zhang et al., 2009] integrated active learning into MIL to efficiently obtain bag labels from the query user. Recently, Li and Liu [Li and Liu, 2015] proposed a graph-based MIL framework which constructed two graphs to describe the affinity relationships between images and between regions respectively. The two graphs provided regularization for MIL. Similar to previous work, it also required a set of labeled images from the query user. The major drawback of these methods is that they hinder user experience by asking for labels. Moreover, all the above MIL methods use hand-crafted features and segment raw images to generate instances. These low level features may not well capture the conceptual objects in images.

Recently, researchers explored using MIL and deep learning to address object detection problems. Kraus et al. [Kraus et al., 2016] proposed an MIL approach based on CNNs for classifying and segmenting microscopy images. Their work showed that CNNs combined with MIL can be well trained end-to-end using whole microscopy images with image level labels. However, their approach can only deal with fixed-size cells in microscopy images, while objects in natural images can have arbitrary sizes. In comparison, DMIH can capture objects in multi-scales by generating proposals from multiscale convolutional feature maps. Wu et al. [Wu et al., 2015] used BING [Cheng et al., 2014] for generating object proposals from raw images. These proposals were taken as instances and fed into a CNN which was trained in an MIL fashion with image level object labels. Another related work was conducted by Ren et al. [Ren et al., 2016], which combined a large pre-trained CNN with MIL for object detection without bounding box annotations. They first produced object proposals on raw images, and each candidate proposal was then encoded by the pre-trained CNN. Finally, the encoded candidate proposals were examined by a SVM classifier which was trained with an MIL objective. However, the above two works aimed to locate and classify objects. The learned high level features were not optimized for retrieval. Second, the methods are inefficient in that each proposal produced from raw images will be encoded by a CNN. The time cost is unacceptable for query processing. In comparison, DMIH generates proposals from high level feature maps, which is more efficient.

3 The Method

3.1 Notations and Architecture Overview

Fig. 2 shows the network architecture. We take VGG-16 [Simonyan and Zisserman, 2015] as our base network to provide high level 2D feature inputs for images. On top of VGG-16 we build multi-scale convolutional layers from which object proposals are extracted via a 3×3 sliding window with stride 1. This scheme for proposal generation has been successfully applied for real-time object detection [Liu et al., 2016]. As in [Liu et al., 2016], the sizes of convolutional filters are set to 3×3×p where p is the number of feature maps in the previous layer. Finally, object proposals are fed to the MIL/hashing layers for objectness prediction/hash code generation. Note the proposals are generated on feature maps rather than raw images. Their size is much smaller compared to extracting from raw images. This facilitates fast processing of proposals and helps keep the model compact.

Formally, let Ii be the image in the training dataset with index i and Xi = {xi1 , . . . , xiM } be the set of M object proposals extracted for Ii, where xim ∈ Rd is the feature vector for proposal m. Let N be the number of object classes. Each image can contain objects from multiple classes. We use tic ∈ {0, 1} to denote whether Ii contains objects from class c. If tic = 0, ∀c ∈ {1, . . . , N}, then Ii has no concerned objects. The top layer of DMIH contains two sub-layers: the hashing layer and the objectness evaluation (MIL) layer. The objectness evaluation layer defines an evaluation function lc(·) for each class c to judge whether a proposal represents an object of c. The hashing layer maps proposals judged to be objects into the Hamming space through the hash function f(·) for indexing. In the following, we show how to train DMIH.

3.2 Optimization

The parameters of DMIH include f(·), {lc(·)}Nc=1 and convolutional filters on top of VGG-16. Firstly, we formulate the objectness evaluation for each class c as an MIL problem where object proposals are treated as instances and images with tic = 1/tic = 0 are positive/negative bags, respectively. Given Ii, the evaluation function lc(·) outputs the probability of a proposal xim belonging to class c:

where wc and bc are the parameters of lc(·) and σ(·) is the sigmoid function. After obtaining the probability estimates for all the proposals in Xi , the image level prediction is calculated by applying a global pooling function g (·) over all pic,m's as follows

The global pooling function g (·) maps the instance space probabilities to the bag space. Commonly adopted pooling functions include maxm(pic,m), avgm(pic,m), log[1 + ∑m exp(pic,m)], among others. An image would not contain many positive instances. Hence, we adopt max(·) which means we are concerned with the most probable object proposals. The loss function for the MIL layer is summarized as follows

Eq. (3) sums over the loss of each training image. For each image, the loss is a summation of the cross-entropy losses for all classes. If an image Ii contains no objects (i.e. tic = 0, ∀c ∈ {1, . . . ,N}), all the P i c 's for Ii will be suppressed.

Next, we discuss the training of the hash function f(·). The general idea is that we treat the hashing layer outputs as an embedding Hamming space where we train the semantic relationships between images according to their class labels in terms of the corresponding hash codes. Let him ∈ {0, 1}k denote the k bits hash code of object proposal xim in image Ii, i.e. him = f(xim). We use Hi = {hi1 , . . . , hiM } to denote the hash set of the object proposals of image Ii. The intuition is that, if two images Ii and Ij share object labels, we let the corresponding object hash codes be near each other, while we keep objects belonging to different classes away from each other. However, tic 's are weak labels at image level. We therefore take the most probable object proposal according to lc(·) as the object for class c in image Ii with tic = 1. For a pair of training images (Ii, Ij), the loss function is defined as:

where the summation is over all possible combinations of class labels contained in Ii and Ij. Motivated by a marginbased loss proposed by [Hadsell et al., 2006], Φ(·) is defined

where Idx(P i c ) denotes the index of the proposal in Ii with the maximum objectness probability for class c, i.e. Idx(P i c ) = arg maxm pic,m, and Dst(·, ·) is a distance metric for hash codes. Eq. (5) means that we encourage the most probable same-class objects to be as near as possible, while keeping the most probable different-class objects at least β away. Since the hamming space is discrete and not differentiable, we relax the activation of f(·) to its continuous analogue, the sigmoid function σ(·). The approximate hash code of xim is computed as [Lin et al., 2015]

where Wf ∈ Rk×d and bf ∈ Rk×1 are the parameters of f(·). The hash codes used for indexing are obtained by binarizing ˜h. Dst(·, ·) is set to be the Euclidean distance accordingly.

Finally, we formulate the joint objective function of DMIH by synthesizing Eqs. (3) and (4):

Such a joint optimization scheme could benefit both objectives: the training of the MIL part can help hashing learning locate the correct proposals; the pair-hashing part provides a regularization for objectness evaluation through underlying learnable convolutional filters.

Training. We employ stochastic gradient descent with image pair sampling to optimize DMIH. The hyper-parameter λ in Eq. (7) controls the balance between the two task losses. β and λ are set to 1.25 and 1 respectively by cross validation. The gradient calculation is straightforward. We omit the details due to space limitation.

3.3 Ranking Criterion

After training, we can then use the model for image indexing and query processing. In particular, hash codes of the object proposals whose objectness probabilities are greater than a certain threshold θ are selected to represent an image. For an image Ii in an image repository, we obtain a number of hash codes according to θ and put them together to form a hash bag ¯Hi to index Ii. A user can use one or multiple images as queries. The queries will be fed into DMIH and a set of hash codes will be outputted. Given a set Q of query images, we obtain n hash codes to form the hash bag ¯HQ = {hQ1 , hQ2 , . . . , hQn }. We design a United Hamming distance UHammDst between ¯HQ and the hash bag ¯Hi of an image Ii in the image repository:

Images in the repository will be ranked in ascending order by UHammDst(·, ·) and the top ranked images are returned to the user.

4 Experiments

In this section, we evaluate DMIH on both single-object queries (which is the focus of previous work) and multiobject queries, to show its superiority over baseline methods.

4.1 Datasets

SIVAL. It is a benchmark dataset that emphasizes the task of object-based image retrieval. It consists of 25 different categories, and each category includes 60 images. The object can occur anywhere against highly diverse backgrounds in each image.

Pascal VOC 2007 [Everingham et al., 2007]. It contains 9,963 images with 20 different object categories. This dataset is more challenging than SIVAL, because there are more variations in scale, posture and angle. Images in it can contain multiple labels, so we run experiments with multi-object queries on this dataset.

ILSVRC 2013 detection set. This dataset has a similar task and style with PASCAL VOC, but contains more images and categories. It contains nearly 400K images in 200 object categories. We use this dataset to primarily evaluate the runtime efficiency of DMIH and baseline algorithms.

4.2 Settings and EvaluationMeasures

We compare DMIH to state-of-the-art hashing methods, including PmH [Lee et al., 2010] and DSRH [Zhao et al., 2015]. PmH generates hash codes for multiple regions for an image. In addition to the hand-crafted features used in [Lee et al., 2010], we also apply PmH on features computed by VGG-16 [Simonyan and Zisserman, 2015], denote as PmHCNN. For DSRH, we first use BING [Cheng et al., 2014] to generate object proposals, and then obtain their hash codes by DSRH [Zhao et al., 2015]. We also compared DMIH to two variants of it. The first one omits the hashing layer and uses Euclidean distance on CNN features (x) for search. It performs deep object detection by MIL in nature and is named ℓ2-scan. The second one, DMIH-ind, performs MIL and hashing learning separately as two steps. It is used to test whether joint learning leads to better performance. We do not involve traditional object-based retrieval methods since the settings are very different (i.e. they ask for labels from users rather than making use of labeled image datasets). We empirically set the objectness threshold θ = 0.7 for DMIH and its variants. Parameters of PmH and DSRH are set to the best values reported. For fair comparison, we use Eq. (8) as the ranking criterion for all the methods except PmH (it generates a large number of regions for an image). Regarding evaluation metrics, we employ mean average precision (MAP) and precision@k [Lin et al., 2015], where an image is deemed to be relevant to a query if it contains the labels of the query.

4.3 Experiments with Single-object Queries

For a single-object query, we assume the whole query image is an object. Each method process query images by taking this prior knowledge into account. We first report results for the SIVAL dataset. We randomly extract 8 images from each object class to form a total of 200 query images. The rest images are used for training and indexing. Fig. 3(a) shows the precision@30 performance of each method when varying hash code length from 8 bits to 64 bits. We find DMIH is consistently better than all the compared methods at each code length. These results illustrate the superior ability of DMIH in extracting and encoding objects from images. In Fig. 3(b), we fix code length to 64 bits and plot precision@k with varying k. Again, DMIH outperforms all the compared methods in all cases. The superiority of DMIH over DMIHind demonstrates the usefulness of joint optimization of hashing and MIL objectness prediction. Although the CNN features boost the performance of PmH by an obvious margin, it still performs worse than DMIH. Finally, the mediocre performance of ℓ2-scan indicates that features trained for object detection are not suitable for retrieval.

We next test on the Pascal VOC 2007 dataset. We randomly sample 50 images from each object category, resulting in a total of 1K query images and 8963 training images. Since each image can contain multiple objects, we only take the object in a query image for the category from which the image was sampled as the query input (the bounding box is given in the dataset). The results for Pascal VOC 2007 are shown in Fig. 4. Since this dataset is much larger than SIVAL with each query having a larger set of relevant images, we report precision@100 and vary k from 50 to 300 in Fig. 4. The observations are similar with those for SIVAL. We also test the performance differences between DMIH and baselines by ttest and find the differences are significant under significance level α = 0.05. For the following experiments, we fix hash code length to 64 bits.

For ILSVRC 2013, we randomly extract 100 images from each class as queries. The rest images are used for training and indexing. We use query time to refer to the time cost for processing one query, including feature extraction, object/region generation, hash codes calculation and search (abbreviated as "F", "O", "H" and "S" respectively). We report in Table 1 the average query time (and also the retrieval MAP) for each method on ILSVRC 2013. All the methods are run on a PC with NVIDIA GTX 1070 GPU, Inter Core i7-7700 CPU and 16GB memory. Since DMIH is an endto-end method, we simply report its query time in whole. In DSRH, the time cost of "O" mainly comes from BING (only one proposal generated since the whole image is an object). We use GPUs to only accelerate CNN computation. From Table 1, We can see that DMIH is very efficient compared to baseline methods. This is because DMIH integrates feature extraction, object generation and hash code computation in one deep model. The computation can be well accelerated on GPUs. We omit the results for DMIH-ind since its query time is the same as DMIH. Regarding retrieval performance, DMIH again beats all the other methods.

4.4 Experiments withMulti-object Queries

A user can select one or more images to form a multi-object query. The query images are then processed by each method in the same way as images in the image repository, i.e. generating a bag of hash codes. The returned images should contain different types of objects that appear in the query images. Because most of the images in Pascal VOC 2007 contain multiple objects, it is very suitable for this task. We randomly sample 1K images and randomly combine at most 4 images from them to form queries. An image is judged to be relevant if it contains all types of objects in the query. Table 2 gives the MAP results for different combinations of object types in queries. We can see DMIH outperforms baseline methods by an obvious margin. DMIH also beats DMIH-ind and ℓ2scan. We omit them due to space limitation. An interesting phenomenon in Table 2 is that the quality of search results gets improved when using more types of objects as queries. This could be because more types of objects can more clearly express a user's interest, just like multi-keyword queries in text search. Fig. 5 shows top ranked images for queries with different combinations of object types. We can see DMIH generates better results than the baseline methods.

5 Conclusion

In this paper, we propose to construct a deep hashing learning framework for object retrieval in a weakly supervised learning setting. Unlike previous object-based image retrieval methods, our framework builds an end-to-end relation between a raw image and the binary hash codes of objects in it for fast indexing. A joint optimization scheme which integrates feature learning, multiple instance learning and hashing learning is presented for learning the deep model. We demonstrate the superiority of the proposed approach over state-of-the-art methods on both single-object and multiobject retrieval problems on three benchmark datasets. To further speedup retrieval, we will investigate indexing in future work.

Acknowledgments

This research is partly supported by National Science Foundation of China under Grant 61672409,61522206,61373118, National High-Technology Program of China (863 Program, Grant No.2014AA015201), Program for Changjiang Scholars and Innovative Research Team in University (No.IRT13090), and Program of Shaanxi Province Innovative Research Team (No.2014KCT-17).