Hash code learning for large scale similarity search

Zhuang, Furen

Permalink

https://hdl.handle.net/2142/104798 Copy

Description

Title

Hash code learning for large scale similarity search

Author(s)

Zhuang, Furen

Issue Date

2019-04-09

Director of Research (if dissertation) or Advisor (if thesis)

Moulin, Pierre

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• hashing
• learning
• semantics

Abstract

In this thesis we explore methods which learn compact hash coding schemes to encode image databases such that relevant images can be quickly retrieved when a query image is presented. We here present three contributions. Firstly, we improve upon the bit allocation strategy of Signal-to-Noise Ratio Maximization Hashing (SMH) to produce longer hash codes without a deterioration in retrieval performance as measured by mean average precision (MAP). The proposed bit allocation strategy seamlessly converts the Hamming distance between hash codes into a likelihood ratio test statistic, which is the optimal decision rule to decide if samples are related. We show via experiments that at the same false positive rate, the proposed method could obtain false negative error rates which are significantly lower than the original SMH bit allocation strategy. Our second contribution is the extension of SMH to use a deep linear discriminant analysis (LDA) framework. The original SMH method uses features from convolutional neural networks (CNNs) trained on categorical-cross-entropy (CCE) loss, which does not explicitly impose linear separability on the latent space representation learned by the CNN. The Deep LDA framework allows us to obtain a non-linear transformation on the input images to obtain transformed features which are more discriminatory (samples of the same class are close together while samples of different classes are far apart) and better fit the linear Gaussian model assumed in SMH. We show that the enhanced SMH method using Deep LDA outperforms recent state-of-the-art hashing methods on single-label datasets CIFAR10 and MNIST. Our final contribution is an unsupervised graph construction method which binarizes CNN features and allows the use of quick Hamming distance calculations to approximate pairwise similarity. This graph can be used in various unsupervised hashing methods which require a similarity matrix. Current unsupervised image graph construction methods are dominated by those which utilize the manifold structure of images in the feature space. These methods face the dilemma of needing a large dense set of data points to capture the manifold structure, but at the same time are unable to scale up to the requisite sample sizes due to their very high complexity. We depart from the manifold paradigm and propose an alteration relying on matching, exploiting the feature detecting capabilities of rectified linear unit (ReLU) activations to generate binary features which are robust to dataset sparsity and have significant advantages in computational runtime and storage. We show on six benchmark datasets that our proposed binary features outperform the original ones. Furthermore we explain why the proposed binarization based on Hamming metric outperformed the original Euclidean metric. Particularly, in low-SNR regimes, such as that of features obtained from CNNs trained on another dataset, dissimilar samples have been shown to be much better separated in the Hamming metric than the Euclidean metric.

Graduation Semester

2019-05

Type of Resource

text

Permalink

http://hdl.handle.net/2142/104798

Copyright and License Information

Copyright 2019 Furen Zhuang

Owning Collections