Similarity-Preserving Binary Hashing for Image Retrieval in large databases

Universidad Polit´ ecnica de Valencia Master’s Final Project Similarity-Preserving Binary Hashing for Image Retrieval in large databases Author: Guillermo Garc ´ ıa Franco Supervisor: Dr. Roberto Paredes Palacios June 29, 2012 Abstract Hashing techniques have become very popular to solve the content-based image retrieval problem in gigantic image databases because they allow to represent feature vectors using compact binary codes. Binary codes provide speed and are memory-efficient. Different approaches have been taken by researchers, some of them based on the Spectral Hashing objective function, among these the recently proposed Anchor Graph Hashing. In this paper an extension to the Anchor Graph Hashing technique which deals with supervised/label information is proposed. This extension is based on representing the samples in an intermediate semantic space that comes from the definition of an equivalence relation in a intermediate geometric hashing. The results show that our approach is a very effective way to incorporate such supervised information to the Anchor Graph Hashing method. On the other hand, the results show that our approach is very effective to deal with clean supervised information but still some further efforts are required in those scenarios where the label information has important presence of noise. CONTENTS Contents 1 Introduction 2 1.1 Motivation............................. 2 1.2 Content Based Image Retrieval . . . . . . . . . . . . . . . . . 3 1.2.1 Content versus Concept . . . . . . . . . . . . . . . . . 4 1.2.2 Application. Use . . . . . . . . . . . . . . . . . . . . . 4 1.2.3 Content-Based Image Retrieval System Structure . . . 5 1.2.4 Different system models based on query . . . . . . . . 6 1.3 Similarity Search in Information Retrieval . . . . . . . . . . . 8 1.4 Similarity-Preserving Binary Hashing . . . . . . . . . . . . . . 10 2 Hashing Methods 12 2.1 Unsupervised and Supervised Learning Methods . . . . . . . . 12 2.2 Notation.............................. 12 3 Unsupervised Hashing Methods 13 3.1 Locality Sensitive Hashing (LSH) . . . . . . . . . . . . . . . . 13 3.2 Spectral Hashing (SH) . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Iterative Quantization (ITQ) . . . . . . . . . . . . . . . . . . . 15 3.4 Binary Reconstructive Embeddings (BRE) . . . . . . . . . . . 17 3.5 Minimal Loss hashing for Compact Binary Codes (MLH) . . . 18 3.6 Anchor Graph Hashing (AGH) . . . . . . . . . . . . . . . . . . 19 4 Supervised Hashing Methods 20 4.1 Supervised Anchor Graph Hashing (SAGH) . . . . . . . . . . 20 4.1.1 The proposed SAGH approach . . . . . . . . . . . . . . 21 4.1.2 Hashing query images . . . . . . . . . . . . . . . . . . 22 4.2 Supervised Multiple Random Anchor Graph Hashing (SMRAGH) .............................. 23 5 Literature Experimentation 26 5.1 Measures.............................. 26 5.2 Datasets used in literature . . . . . . . . . . . . . . . . . . . . 26 6 Experiments 28 6.1 CIFAR-11 ............................. 28 6.2 NUS-WIDE ............................ 29 7 Conclusions 35 Page 1 1 INTRODUCTION 1 Introduction 1.1 Motivation With the advance of multimedia technology and the Internet, we have at our disposal billions of images available online. As the amount of the data available continues to grow, methods to perform efficient searches on these huge databases becomes vital for many applications. One important application for this technology is the visual search or content based image retrieval (CBIR) on large collections of images, such as those on the Internet or personal collections. Another important application is image annotation using data-driven methods. These methods produce an image annotation by means of searching very similar images in a large-scale database following a searchto-annotation strategy. In general, these methods derive the content of an image by propagating the labels of its similar images. The main objective is thus to be able to retrieve the most similar images from a large, and possibly distributed database of images. Consequently, search methods should be memory efficient, allowing to store millions of images, and also should perform a fast similarity search. In order to find similar images in a large-scale database, several approaches from the approximate nearest neighbors search literature are designed to solve this problem. The most successful methods can be mainly split into two different categories: Tree-decomposition methods and Hashing methods. Tree-decomposition methods store the reference samples in a tree structure providing in average, an approximate nearest neighbor search in logarithmic time with respect to the number of samples. The main drawback of these methods when working with images is that images are generally represented using a very high dimensional vector. In such a situation, tree indexing structures become inefficient due to an increasing need of backtracking to explore all the nodes. In order to alleviate this problem and focused on the high dimensional representation of images, the Hashing techniques emerged as a solution to the approximate nearest neighbor search in high dimensional spaces, [11, 2]. Hashing methods map the high-dimensional representation into a binary representation with a fixed number of bits. Binary codes are very storageefficient, since relatively few bits are required, millions of images can be stored into computer memory. Moreover, computing the hamming distance for binary codes is very fast, as it can be performed efficiently by using bit XOR operation and counting the number of set bits [13, 27]. The hash function design is crucial, this being mainly the unique difference among all these methods. Generally the different methods learn a hash Page 2 1 INTRODUCTION function that preserves the topology of the samples in the original space, i.e. images that are near in the original high dimensional space share the same (or similar) binary code, while images far in the original space have very different binary codes. These methods work with unsupervised information, thus the preservation of the geometric topology is the unique goal to pursue. However, when there is additional information available, which could be supervised (i.e. labels annotated by a human) or it could also be what currently is being called privileged information (i.e. information available only for the training samples, such as text related to an image) [25], better performance can be obtained by methods which try to preserve the semantic topology. Since images visually different could contain similar semantic concepts, in these cases the hash code should be designed to (also) preserve the semantic topology. The document is organized in the following way. This section will introduce the problem of concept based image retrieval, its application and different system configurations. It will aso define the problems when handling large databases introducing the concepts of similarity search and binary hashing. Section 2 will briefly introduce the concepts of unsupervised and supervised methods for image retrieval and the notation used along the document. The following sections 3 and 4 will be focused in different unsupervised and supervised methods in the literature. Section 4 will be completely focused in the proposed supervised methods. Section 5 contains the different measures and databases used in the experimentation found in the literature, and in the following section 6 presents the results obtained with the proposed methods in two databases. Finally section 7 has the conclusions and future work. 1.2 Content Based Image Retrieval Content-based image retrieval (CBIR) is the application of computer vision techniques to an image retrieval problem, which is the problem of searching for digital images in large databases. Content based image retrieval is opposed to a concept based approach. While the second one relies in metadata such as keywords, tags or descriptions associated with the image, the first one analyses the actual contents of the images. The content of the image is information that can be derived from the image itself such as colors, shapes or textures. Page 3 1 INTRODUCTION Figure 1: Image Retrieval: the user makes a query and the system retrieves the most relevant images to the given query. 1.2.1 Content versus Concept Nowadays most web based image search engines use concept-based search engines that rely on metadata. The problem with this approach is that we find a lot of garbage in the results. •Language: ambiguities, such as polysemy or synonymy (with synonyms we can miss images. Some systems use supergroups -categorizing images in semantic classes-, but still scaling issue). •Textual information: Even though easy to search with existing technology, impractical for large databases or automatically generated images (surveillance cameras) because it requires humans to personally describe with words every image in the database. •Human Tagging: apart from being expensive and inefficient for large databases also leads to errors tagging, miswritten or incorrect tags, images labelled differently by different users and they may not tag every concept in the image. 1.2.2 Application. Use Potential uses for CBIR include: •Art collections Page 4 1 INTRODUCTION •Photograph archives •Retail catalogs •Medical diagnosis •Crime prevention •The military •Intellectual property •Architectural and engineering design •Geographical information and remote sensing systems 1.2.3 Content-Based Image Retrieval System Structure CBIR System Retrieval Module Feature Extractor Query Image Preprocessing Feature extraction Query Image Features Similarity Search Indexing + Retrieval Retrieval Results Image Database Features Database Figure 2: Diagram of a CBIR system. The training process is done offline and is represented with blue arrows. The process of an user query is performed on-line and is represented with black arrows. Query Image This component describes the input to the system, it is the image which is taken as the input query for the search operation. User is suppose to select an image in order to find similar images for that particular image. Page 5 1 INTRODUCTION Feature Extractor This component is an important component of the system. It mainly extracts the information from the image. Input images are processed to extract features in order to represent the image contents in numerical form. These feature vectors are generally used as the image signature and they can be thought of as points in a highdimensional space. Every image is assigned with one of this set of identifying descriptors which will be used in the retrieval/matching phase to retrieve relevant images. Image Database This is the set of all the images that the system is going to provide as a result to the user queries. Features Database This is where all the information extracted from the training images is stored. Feature vectors from all the training images are extracted and stored. The system will use these to perform feature comparison during the similarity search process. Features might be stored as a simple list or set of feature vectors or in more complexes structures such as k-d-trees, metric trees, etc. Similarity Search This component basically does the comparison part and returns its own output according to the technique it uses to do the comparison. The system provides similarity scores for each one of the images in its image database. This process is based on some similarity measure to compute/measure the distance between the query image descriptors and the feature database. From the system’s viewpoint the similarity of two images depends on the distance in feature space between the feature points defined by the descriptors. Therefore, the shorter the distance between the two points, the more similar the corresponding images are. Indexing and Retrieval The system selects the number of images to present to the user as a result to the query. 1.2.4 Different system models based on query There are different ways of providing the user query in a CBIR system. Query by example System is provided with an example image to base its search upon. The result images should share common elements/content with the provided image. The user can provide images in very different ways: Page 6 1 INTRODUCTION •Image provided by the user (uploaded, camera, etc) •Preexisting image selected from random set (directly or browsing customized/hierarchical categories). •Visual sketch: the user draws a rough approximation of the image they are looking for (p.e. with blobs of colors or general shapes) Instead of giving as a query a whole example image, the user can •Query by image region (rather than the entire image), •Query by multiple example images, •Query by direct specification of image features This query technique removes the difficulties that can arise when trying to describe images with words or labels. Semantic retrieval The user makes a semantic retrieval. Users can directly request certain images like ”find pictures of white cats”. This type of open-ended task is very difficult for computers to perform. In order to provide semantic-based retrieval in a CBIR system images need to be indexed by some textual information. Users usually prefer querying images by keywords. As manual indexing is a tedious task for indexers and leads to some problematic as we discussed before in 1.2.1, annotating images automatically would be very useful for semantic-based image retrieval [16, 21]. Relevance Feedback CBIR systems can make use of relevance feedback, where users progressively refine the search results by marking the result images as ”relevant”, ”not relevant”, or ”neutral” to the search query. Then the search is repeated using this new information. 3 shows a diagram of this process. After the first retrieval, the user is asked to provide positive (relevant) and negative (irrelevant) examples as feedback among the initial retrieved image sets. Then this information is used as positive and negative feedback for query refinement. Page 7 3 UNSUPERVISED HASHING METHODS code length increases. But they require large code lengths for good retrieval accuracy, and they are not applicable to general similarity measures, like human ratings. This is the main reason why there’s been a growing interest in learning the hash functions instead. Basically, learning hash binary functions provides those two advantages: •codes can become more compact •more general classes of similarity measures can be preserved (p.e. based in human labels, which might not correspond to any measure distance). Some key learning-based hash approaches: •Parameter Sensitive Hashing [22]: boosting (Shakhnarovich et al 2003) •Semantic Hashing [20]: Neural Networks (Salakhutdinov and Hilton 2007) •Spectral hashing [28]: Spectral Methods (Weiss et al 2008), assumes uniform distribution over the data. •Loss-based methods [15, 18] Binary codes Most of the methods that learn hash functions use some restrictions in order to make sure that the resulting binary codes are short and make a good use of each one of their bits. •maximize variance of each bit max(Pkvar(hk(x))) •bits independent/balanced Pi(yi)) = 0 for i={1, ..., n} •bits pairwise uncorrelated minimizes the redundancy among bits 1 nPi(yiyiT) = I 3.2 Spectral Hashing (SH) Let An×nbe the affinity matrix for the n datapoints which elements aij indicate the similarity between training samples iand j. The average Hamming Page 14 3 UNSUPERVISED HASHING METHODS distance between similar neighbors can be written as a sum of similarityweighted squares of differences between codes. X ij Aij||yi−yj||2 Relaxing the bits independence assumption and requiring the bits to be uncorrelated we obtain the following problem proposed in []: min i,j 1 2 n X i,j=1 aijkyi−yjk2 s.t. yi∈ {1,−1}q,X i yi= 0,1 nX i yiyT i=I(2) The solution to this objective function is going to provide similar codes yiand yjfor similar samples xiand xj. This previous objective function is commonly expressed in terms of the graph Laplacian matrix L∈Rn×nas: min Y 1 2 n X i,j=1 kyi−yjk2aij =Tr(YTLY ) s.t. Y∈ {1,−1}n×q,1TY=0,YTY=nIq×q(3) where L= diag(A1)−A. The first restriction assures to generate codes with balanced bits, and the second one minimizes the redundancy among bits forcing the codes to be orthogonal. This restrictions avoid having a closed solution where all codes are the same. Spectral relaxation could be applied to make this NP-hard problem tractable, dropping the integer constraint and allowing Y∈Rn×q. With this, the solution Ywould be the r eigenvectors of length √ncorresponding to the q smallest eigenvalues (ignoring eigenvalue 0) of the graph Laplacian L. 3.3 Iterative Quantization (ITQ) This is a simple and efficient alternating minimization scheme for finding a rotation of zero-centered data so as to minimize the quantization error of mapping this data to the vertices of a zero-centered binary hypercube. After centering the input feature vectors, in order to find codes with maximum variance and pairwise uncorrelated, input data X∈Rn×dis projected Page 15 3 UNSUPERVISED HASHING METHODS using an unsupervised data embedding such as PCA, even though it can be used with other unsupervised or supervised embeddings such as canonical correlation analysis (CCA). If W∈Rd×qis the matrix having as column vectors the hyperplane coefficients wkobtained using PCA, each bit k= 1, ..., q can be encoded with the function hk(x) = sgn(xwk). hk(x) = sgn(xwk) = sgn(v) The entire encoding process would be: Y=sgn(XW ) = sgn(V) If Wis an optimal solution, so is W R, being Ran orthogonal q×qmatrix. Therefore, the projected data V=XR can be orthogonally transformed. ITQ will orthogonally transform the projected data in order to minimize the quantization loss. Y=sgn(XW R) = sgn(V R) Definition Let v∈Rqbe a vector in the projected space. It is easy to show that sgn(v) is the vertex of the hypercube {−1,1}qclosest to vin terms of Euclidean distance. Quantization loss is the difference obtained when adjusting the real projected data vinto the binary code hypercube {−1,1}q. ||sgn(v)−v||2 The smaller the quantization loss, the better the resulting binary code will preserve the original locality structure of the data. They are going to find an orthogonal rotation, such that the projected points are as closest as possible to their binary quantization (minimizing distances to their corresponding point in the zero-centered binary hypercube in hamming space). min(Q(Y,R)) Q(Y,R) = ||Y−V R||F We can see in the quantization loss function the connection of ITQ to the orthogonal Procrustes problem. Page 16 3 UNSUPERVISED HASHING METHODS Figure 5: ITQ Method. Left: PCA aligned rotation. Center: Random rotation. Right: Optimized Rotation 3.4 Binary Reconstructive Embeddings (BRE) BRE [15] is a learning-based binary hashing method based on optimizing a loss function: minimize the reconstruction error between the original distances and the Hamming distances of the corresponding binary embeddings via an scalable coordinate-descent algorithm. In order to compute the q-dimensional binary embedding, the data is projected using a set of q hash functions h1, ..., hb. Each hash function hi is a binary-valued function. An input feature vector xiwould produce a low-dimensional binary reconstruction yi= [h1(xi); h2(xi); ...;hq(xi)]. In article [15] the hash functions are dependent on one another. hi(x) = sign( k X j=1 Wijκ(xij,x)) Loss function that penalizes the difference between euclidean distance in the input space and the hamming distance between binary codes. O(xn i=1, W ) = X (i,j)∈N (d(xi, xj)−˜ d(xi, xj))2=X (i,j)∈N (1 2||xi−xj||2−1 q||˜xi−˜xj||2) This objective is not continuous nor differentiable, their first approach was using a sigmoid function, but minimizing Owith that approach and using a quasi-Newton L-BGFS resulted in poor local optima. They consider fixing all but one weight Wpq, and optimizing Owith respect to Wpq. An optimal update of this weight can be achieved in O(nlogn +nk). Such approach will update a single hash function hp. We can update all functions in O(nq(k+ logn)) Page 17 3 UNSUPERVISED HASHING METHODS 3.5 Minimal Loss hashing for Compact Binary Codes (MLH) •less training time than BRE •based on structured prediction with latent variables •Optimizes empirical loss function •Applicable to general similarity measures (p.e. Human ratings) In MLH [18] the loss function assigns a cost given two binary codes yi,yj and the similarity label sbetween them. L:{−1,1}q×{−1,1}q×{0,1} → R(4) This loss function Lhas to measure how compatible are the codes with the similarity label, and should assign a small cost when hiand hjare nearby and a large cost when they are not. They want to minimize empirical loss function L, defined over a subset of training pairs with similarity labels. L(W) = X (i,j)∈S L(b(xi;w), b(xj;w), sij) sij =1 if xiand sjare similar 0 otherwise They define a hinge-like loss function to capture the similarity principles said before, defines notions of far and near in hamming space using a parameter ρand the hamming distance between two codes h and g. L(h, g, s) = lρ(||h−g||H, s) lρ(m, s) = max(m−ρ+ 1,0) for s= 1 λmax((ρ−m+ 1,0) for s= 0 As long as codes of similar items are within hamming distance ρbits they have cost zero and beyond that the cost linearly increases. For dissimilar items codes further than rho bits have cost zero and then as they come closer their cost linearly increases. Their objective depends on the differences between codes instead of the actual codes. They maximize an upper bound on the loss function (motivated by structural SVM formulations) because it is continuous and non-convex. Coordinate descent algorithm. Initialize W randomly and then iterate over pairs, computing the codes, solving the loss-adjusted inference and updating W en each step. Page 18 3 UNSUPERVISED HASHING METHODS 3.6 Anchor Graph Hashing (AGH) In Spectral Hashing (3.2) relaxation solved the problem for similarity search using binary codes computing the qeigenvectors corresponding to the qsmallest eigenvalues of the graph Laplacian L. Anyway, the problem is still computationally expensive because of the computation of the underlying graph and the Laplacian when nis too large. Based on the Spectral Hashing approach, the authors in [17] introduced a very effective approach for image hashing: Anchor Graph Hashing (AGH). This unsupervised technique aims at capturing and preserving the semantic topology assuming that close-by points usually share labels. The solution proposed to deal with the problem in Spectral Hashing is to avoid computing the whole similarity matrix Afor all the nsamples. To this end, a small set of mpoints being mncalled anchors, are selected (e.g. using k-means clusters). With these anchors, the matrix Ais approximated as ˆ A=ZΛ−1ZT, where Λ= diag(ZT1), and the matrix Z∈Rn×mis highly sparse, each column only having svalues different from zero, which correspond to similarity values of the snearest anchors. Because of this sparsity, the solution can be obtained by an eigenvalue decomposition of a much smaller m×mmatrix, instead of n×nof matrix A. For further details, the reader should refer to [17]. Page 19 4 SUPERVISED HASHING METHODS 4 Supervised Hashing Methods In a supervised scenario, feature vectors are provided with a set of labels that describe the content of a training image. Usually the set of labels provided with the image is represented as a vector of the size of the labels dictionary, having 1 in the position of the labels that contains and 0 in the ones that it does not. There are not as much supervised methods in the literature as unsupervised. Among them, ITQ method using CCA stands out providing accurate results. As ITQ method is already discussed in 3.3, this section will focus completely in the proposed extension to AGH: Supervised Anchor Graph Hashing method. 4.1 Supervised Anchor Graph Hashing (SAGH) The aim of Anchor Graph Hashing is to preserve the original topology by embedding near images to near hashing codes. The results showed in [17] and the reduced computational complexity make this technique a very interesting hashing method for large-scale scenarios. As mentioned above, the main assumption of AGH is that close-by images share labels. However, we can assume that images far in the original space could also share labels and thus being very close in the semantic space. Taking into account that nowadays the images are represented using a very low-level representation, mainly based on bag-of-visual-words, this second assumption is reasonable and motivates the supervised scenario. We propose an extension to AGH that considers side-information provided by the label vectors t, when such information is available. Note that the hashing function of AGH depends on the similarity between the input sample and the manchor vectors, and since the label information is not available for the test samples, the label information cannot be introduced into the similarity matrix Aas can be done for other methods. Therefore the label information has to be included in an indirect way. Our extension, that we call Supervised AGH (SAGH), is based on an two-step repeated application of AGH that uses the label information in an indirect way and the definition of an equivalence relation ∼. The resulting procedure can be summarized as follows, first the training samples are embedded into a geometric binary code, then a semantic representation is derived from this geometric code and finally a new embedding is performed into the desired binary hash code. Page 20 4 SUPERVISED HASHING METHODS original space geometric code semantic space hash code x u v y AGH AGH ∼ t labels Figure 6: SAGH can be seen as a repeated application of AGH. A first embedding is obtained from the original space to a geometric code. Then, using an equivalence relation and the set of labels, a semantic representation is produced. Finally, a second embedding is obtained from this intermediate semantic space to the final binary hash code. 4.1.1 The proposed SAGH approach In the proposed Supervised AGH, the intermediate semantic representation of the samples allows that semantically similar samples are coded with similar binary codes despite of being far in the original representation space. From this perspective, SAGH not only can have a better performance because of using the label information, it can also potentially encode the data with shorter binary codes. The SAGH is performed by first applying the standard AGH to the training set providing an initial hash code of pbits U={u1,...,un} ⊂ {−1,1}p, usually p>qin order to produce a sparser distribution of the data. We will refer to this first hash code as a the geometric code. As mentioned above, the goal of this first hashing is to produce a semantic embedding of the training data. To this end, we define the equivalence relation ∼in the set X. Two samples are equivalent under this relation if these samples have the same geometric code: xi∼xj⇐⇒ ui=uj(5) The equivalence class of a particular sample x∈ X is then defined as: [x] = {x0∈ X | ux=ux0} With this definition we propose a semantic representation of a particular Page 21 4 SUPERVISED HASHING METHODS training sample xias: vi=1 |[xi]|X x∈[xi] tx(6) where |[xi]|is the number of elements in the equivalence class and txis the label vector associated to the sample x. In fact, with this definition all the samples inside an equivalence class share the same semantic representation. Thus, each equivalence class has an associated semantic representation that we denote by v[x]. Alternative equivalence relations could be defined in order to group samples depending on different strategies. For instance, several geometric codes could be obtained from the application of AGH with different parameters, e.g. number of nearest anchors s, anchor selection, etc., that yield different geometric codes for the same sample and allowing to define better equivalence relations. Independently of the equivalence relation definition, equation (6) maps geometric codes u∈ {−1,1}pinto the semantic representations v∈Rl. As a result we have a representation in a semantic space V={v1,...,vn} ⊂ Rl. This set of semantic representations for the ntraining samples is considered as a new input to a second AGH that produces an embedding into the final desired binary representation y∈ {−1,1}qwith qbits. This second AGH uses as input the different intermediate semantic codes vgenerated by the proposed approach. In principle the number of possible different semantic codes can be min(n, 2p), but it is much more less in the practical situation. Figure ?? illustrates the SAGH mechanism. Using this two-step hashing, points that were far in the original space but with similar semantic information should have similar intermediate semantic codes and thus will be mapped to nearby codes in the definitive binary space. 4.1.2 Hashing query images The process to obtain a hash code for a query image follows a similar procedure. For a query image ˆx a geometric code ˆu is produced using the first AGH mapping. This geometric code could be the same (i.e. having hamming distance zero) than some geometric code uiseen in the training step, thus ˆx ∼xiand then we will assign the same intermediate semantic code, ˆv =vi. But the geometric code ˆu could also be empty in the training step, and then there is no semantic code to assign to it. In this case we propose the following procedure. First we have to find the radius Rof the minimum hamming ball with non-empty geometric code uaround ˆu: R= min r{1, . . . , p}s.t. ∃x∈ X :d(ux,ˆu) = r(7) Page 22 4 SUPERVISED HASHING METHODS where d(·,·) is the hamming distance. This radius defines the set BRof the different equivalence classes inside this hamming distance. We propose to obtain the semantic embedding of the query point as an average of all the semantic representations associated to the equivalence classes inside BR: ˆv =1 | BR|X [x]∈BR v[x](8) Finally, the semantic code ˆv will be embedded using again AGH to the definitive hash code ˆy. It is important to note that the hashing obtained by SAGH will be affected mainly by the equivalence relation definition (5), the procedure to obtain a semantic representation associated to each equivalence class (6) and the semantic embedding for those query images that fall into empty geometric codes (8). In fact, experimentation with SAGH 6 showed that the performance of the method decreased as more samples would fall into empty geometric codes. In order to decrease the number of samples obtaining unknown binary codes, we modified SAGH approach (4.2) defining a different equivalence relation. 4.2 Supervised Multiple Random Anchor Graph Hashing (SMRAGH) When AGH is first run during training, a representation in geometric space is obtained for all the different samples in the training set. Training samples are represented as points in this new geometric space. Taking into account that close samples in appearance should generate similar hashing codes, we notice that if we represent all training samples in this geometric space {0,1}q we could find that the training samples occupy the space in such way that samples fall closer if they have similar contents, and there are also some areas in geometric space that remain deserted, because training samples haven’t generated geometric codes laying in these areas. Later on, during test, a geometric representation for the test feature vectors is obtained. If this point in geometric space lays in the same place as one of the training samples did, then the test sample is assigned the same label as the training sample. On the other hand, if the test sample lays in a deserted area, as explained in 4.1.2, we assign the label of the closest sample, that is, the one included in the minimum radio hamming ball around the test sample. During test, in the first step of geometric representation using AGH method, we notice that most of the test samples obtain a geometric code Page 23 6 EXPERIMENTS 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 10 16 32 64 128 256 Precision @ k=500 Code size SAGH ITQ-CCA AGH SH LSH L2 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 10 16 32 64 128 256 Precision @ hamming radio = 2 Code size SAGH ITQ-CCA AGH SH LSH Figure 8: CIFAR-11 dataset. On top, average precision of the top-500 ranked images for each method varying the hash code size. Below, average precision for a hamming radius of 2 for each method varying the hash code size. 2,100 images are used for the test set, and the remaining are used as training. Analogously to the CIFAR experiments, for each of the methods the corresponding parameters were varied and the best result is presented. The parameters tried for AGH and SAGH were the same than for the CIFAR-11 experiments. The results are presented in Figure 10 using the same performance measures as for CIFAR, although in this case using precision for the first 5,000 retrieved samples since this was the value used in [17]. As ground truth labels, images are considered being semantically the same if they have at least one common tag. For more details on the protocol please refer to [17]. Page 30 6 EXPERIMENTS Figure 9: Query image and the 10-nearest images retrieved using different hashing techniques. From top to down: LSH, SH, AGH, ITQ-CCA (10 bits) and SAGH. The results are somewhat similar to the ones for CIFAR. The supervised methods perform better than the unsupervised ones, and again SAGH is better than the original AGH. However, the difference between SAGH and AGH is much smaller and in this case ITQ-CCA has a better performance than SAGH. In order to clarify this behavior we should take into account the proposed procedure for generating the intermediate semantic code in SAGH. Table 1 shows first the percentage of test samples for which the geometric codes fell into an non-empty geometric code, i.e. the radius of the minimum hamming ball is R= 0, and also shows the percentage of test samples for which the radius is very large R > 3. When R > 0, the intermediate semantic representation has to be obtained by means of averaging the semantic representations of the equivalence classes in BR. Table 1: Percentage of test samples with radius 0 and higher than 3 w.r.t. the number of geometric bits pfor the NUS-WIDE dataset (AGH). p R = 0 R > 3 32 80 0.2 64 58 20 128 44 32 256 20 43 When the value of Ris high, it is highly probable that this averaging is done for very different semantic regions. This problem becomes important Page 31 6 EXPERIMENTS 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 10 16 32 64 128 256 Precision @ k=5000 Code size SAGH ITQ-CCA AGH SH LSH L2 0 0.1 0.2 0.3 0.4 0.5 0.6 10 16 32 64 128 256 Precision @ hamming radio = 2 Code size SAGH ITQ-CCA AGH SH LSH Figure 10: NUS-WIDE dataset. On top, average precision of the top-5,000 ranked images for each method varying the hash code size. Below, average precision for a hamming radius of 2 for each method varying hash code size. when the number of geometric bits pincreases, as can be observed in table 1. The results obtained for NUS-WIDE are motivating us to look for different approaches for obtaining a better semantic representations in such situations. On the other hand, in the same way as the AGH behavior, SAGH maintains a good hash lookup precision even though code size increases, unlike the rest of the methods. SAGH obtains a better average precision than AGH for a hamming radius of 2 for small code sizes. The percentage of test samples obtaining a training hash code has incremented as we expected. By generating codes with other AGH more geometric space is covered. This increments the probability of obtaining lower hamPage 32 6 EXPERIMENTS Table 2: Percentage of test samples with radius 0 and higher than 3 w.r.t. the number of geometric bits pfor the NUS-WIDE dataset (SMRAGH) using number of randoms = 3. p R = 0 R > 3 32 91.43 0 64 68.81 8 128 59.81 21.14 256 40.05 28.95 ming distances between test and train codes. As we can see in figure 11, first we can notice that the behaviour of the technique slightly varies when using random anchors, but then as expected the minimum radio of the hamming ball decreases as the number of layers in the Multiple Random AGH increases. This finally produces an increment in the precision of the method even beating the results obtained with ITQ method (Figure 12). Page 33 6 EXPERIMENTS 0 0.2 0.4 0.6 0.8 1 0 1 2 3 4 5 7 Minimum radio of hamming ball containing at least one training sample around test sample (32 bit codes) sagh mrsagh 1 layer mrsagh 2 layer mrsagh 3 layer mrsagh 4 layer Figure 11: NUS-WIDE dataset: Minimum radio of hamming ball containing at least a training sample around the test sample geometric code. Methods SAGH, and SMRAGH with 1 to 5 layers 0.35 0.4 0.45 0.5 0.55 0.6 0.65 16 32 64 128 256 Precision @ k=5000 Code size sagh itqcca saghnr1 saghnr2 saghnr3 saghnr4 saghnr5 Figure 12: NUS-WIDE dataset: Hamming ranking precision of top-5000 ranked neighbours for each method varying the size of hash code, including random sagh method with 1 to 4 layers Page 34 7 CONCLUSIONS 7 Conclusions In this master thesis we propose an extension to the Anchor Graph Hashing technique which is capable of taking advantage of supervised/label information. This extension is based on representing the samples in an intermediate semantic space that comes from the definition of an equivalence relation in an intermediate geometric code. The results show that our approach is a very effective way to incorporate such supervised information to the standard AGH. The standard AGH is clearly outperformed by our SAGH in the CIFAR dataset where the supervised information can be considered very clean. Moreover, SAGH is clearly the best technique on this dataset compared to the state-of-the-art ITQ-CCA. On the other hand, slight improvements are obtained using our approach in the NUS-WIDE dataset with respect to the AGH. In this multi-label dataset the label information is known to have an important presence of noise. In order to improve the results of the method, a new approach is defined to obtain a semantic representation for those test samples that fall far from a non-empty geometric code. This approach improved the precision in the results, making this technique achieve the best results for this dataset. There are other possible flaws of the proposed approach in this noisy scenario. Thus, future work will be focused on defining better equivalence relations should be derived which give the equivalence classes a more discriminative power under the semantic point of view, and furthermore being robust to the presence of noisy labels. Page 35 REFERENCES References [1] Pyramid Match Hashing: Sub-Linear Time Indexing Over Partial Correspondences, 2007. [2] Alexandr Andoni and Piotr Indyk. Near-Optimal hashing algorithms for approximate nearest neighbor in high dimensions. In FOCS ’06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 459–468, Washington, DC, USA, 2006. IEEE Computer Society. [3] Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM, 45(6):891–923, November 1998. [4] Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509–517, September 1975. [5] Tat-Seng Chua, Jinhui Tang, Richang Hong, Haojie Li, Zhiping Luo, and Yan-Tao. Zheng. Nus-wide: A real-world web image database from national university of singapore. In Proc. of ACM Conf. on Image and Video Retrieval (CIVR’09), Santorini, Greece., July 8-10, 2009. [6] Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-tree: An efficient access method for similarity search in metric spaces. In Proceedings of the 23rd International Conference on Very Large Data Bases, VLDB ’97, pages 426–435, San Francisco, CA, USA, 1997. Morgan Kaufmann Publishers Inc. [7] Kenneth L. Clarkson. Nearest-neighbor searching and metric space dimensions. In In Nearest-Neighbor Methods for Learning and Vision: Theory and Practice. MIT Press, 2006. [8] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry, SCG ’04, pages 253–262, New York, NY, USA, 2004. ACM. [9] Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. In The VLDB Journal, pages 518–529, 1999. [10] Yunchao Gong and Svetlana Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. In CVPR, 2011. Page 36 REFERENCES [11] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, STOC ’98, pages 604–613, New York, NY, USA, 1998. ACM. [12] P. Jain, B. Kulis, and K. Grauman. Fast image search for learned metrics. Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, pages 1–8, June 2008. [13] Donald E. Knuth. The Art of Computer Programming, Volume I: Fundamental Algorithms, 3rd Edition. Addison-Wesley, 1997. [14] Alex Krizhevsky. Learning multiple layers of features from tiny images. Master’s thesis, 2009. [15] Brian Kulis and Trevor Darrell. Learning to hash with binary reconstructive embeddings. In Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22, pages 1042–1050. 2009. [16] Michael S. Lew, Nicu Sebe, and John P. Eakins. Challenges of image and video retrieval. In Proceedings of the International Conference on Image and Video Retrieval, CIVR ’02, pages 1–6, London, UK, UK, 2002. Springer-Verlag. [17] Wei Liu, Jun Wang, Sanjiv Kumar, and Shih-Fu Chang. Hashing with graphs. In Lise Getoor and Tobias Scheffer, editors, Proceedings of the 28th International Conference on Machine Learning (ICML-11), ICML ’11, pages 1–8, New York, NY, USA, June 2011. ACM. [18] Mohammad Norouzi and David Fleet. Minimal loss hashing for compact binary codes. In Lise Getoor and Tobias Scheffer, editors, Proceedings of the 28th International Conference on Machine Learning (ICML-11), ICML ’11, pages 353–360, New York, NY, USA, June 2011. ACM. [19] Aude Oliva and Antonio Torralba. Modeling the shape of the scene: A holistic representation of the spatial envelope. Int. J. Comput. Vision, 42:145–175, May 2001. [20] Ruslan Salakhutdinov and Geoffrey Hinton. Semantic hashing. Int. J. Approx. Reasoning, 50:969–978, July 2009. [21] Nicu Sebe, Michael S. Lew, Xiang Zhou, Thomas S. Huang, and Erwin M. Bakker. The state of the art in image and video retrieval. In Page 37 REFERENCES Proceedings of the 2nd international conference on Image and video retrieval, CIVR’03, pages 1–8, Berlin, Heidelberg, 2003. Springer-Verlag. [22] Gregory Shakhnarovich, Paul Viola, and Trevor Darrell. Fast pose estimation with parameter-sensitive hashing. In Proceedings of the Ninth IEEE International Conference on Computer Vision - Volume 2, ICCV ’03, pages 750–, Washington, DC, USA, 2003. IEEE Computer Society. [23] Antonio Torralba, Rob Fergus, and William T. Freeman. 80 million tiny images: A large data set for nonparametric object and scene recognition. IEEE Trans. Pattern Anal. Mach. Intell., 30:1958–1970, November 2008. [24] Jeffrey K. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Inf. Process. Lett., 40(4):175–179, 1991. [25] Vladimir Vapnik and Akshay Vashist. A new learning paradigm: Learning using privileged information. Neural Networks, 22(5-6):544–557, 2009. [26] Jinjun Wang, Jianchao Yang, Kai Yu, Fengjun Lv, Thomas S. Huang, and Yihong Gong. Locality-constrained linear coding for image classification. In CVPR, pages 3360–3367. IEEE, 2010. [27] Peter Wegner. A technique for counting ones in a binary computer. Commun. ACM, 3:322–, May 1960. [28] Yair Weiss, Antonio Torralba, and Robert Fergus. Spectral hashing. In NIPS’08, pages 1753–1760, 2008. Page 38