Learning Binary Code Representations for Effective and Efficient Image Retrieval

The size of online image datasets is constantly increasing. Considering an image dataset with millions of images, image retrieval becomes a seemingly intractable problem for exhaustive similarity search algorithms. Hashing methods, which encodes high-dimensional descriptors into compact binary strings, have become very popular because of their high efficiency in search and storage capacity. In the first part, we propose a multimodal retrieval method based on latent feature models. The procedure consists of a nonparametric Bayesian framework for learning underlying semantically meaningful abstract features in a multimodal dataset, a probabilistic retrieval model that allows cross-modal queries and an extension model for relevance feedback. In the second part, we focus on supervised hashing with kernels. We describe a flexible hashing procedure that treats binary codes and pairwise semantic similarity as latent and observed variables, respectively, in a probabilistic model based on Gaussian processes for binary classification. We present a scalable inference algorithm with the sparse pseudo-input Gaussian process (SPGP) model and distributed computing. In the last part, we define an incremental hashing strategy for dynamic databases where new images are added to the databases frequently. The method is based on a two-stage classification framework using binary and multi-class SVMs. The proposed method also enforces balance in binary codes by an imbalance penalty to obtain higher quality binary codes. We learn hash functions by an efficient algorithm where the NP-hard problem of finding optimal binary codes is solved via cyclic coordinate descent and SVMs are trained in a parallelized incremental manner. For modifications like adding images from an unseen class, we propose an incremental procedure for effective and efficient updates to the previous hash functions. Experiments on three large-scale image datasets demonstrate that the incremental strategy is capable of efficiently updating hash functions to the same retrieval performance as hashing from scratch.

Efficient Image and Video Representations for Retrieval

Image (Video) retrieval is an interesting problem of retrieving images (videos) similar to the query. Images (Videos) are represented in an input (feature) space and similar images (videos) are obtained by finding nearest neighbors in the input representation space. Numerous input representations both in real valued and binary space have been proposed for conducting faster retrieval. In this thesis, we present techniques that obtain improved input representations for retrieval in both supervised and unsupervised settings for images and videos. Supervised retrieval is a well known problem of retrieving same class images of the query. We address the practical aspects of achieving faster retrieval with binary codes as input representations for the supervised setting in the first part, where binary codes are used as addresses into hash tables. In practice, using binary codes as addresses does not guarantee fast retrieval, as similar images are not mapped to the same binary code (address). We address this problem by presenting an efficient supervised hashing (binary encoding) method that aims to explicitly map all the images of the same class ideally to a unique binary code. We refer to the binary codes of the images as `Semantic Binary Codes' and the unique code for all same class images as `Class Binary Code'. We also propose a new class­ based Hamming metric that dramatically reduces the retrieval times for larger databases, where only hamming distance is computed to the class binary codes. We also propose a Deep semantic binary code model, by replacing the output layer of a popular convolutional Neural Network (AlexNet) with the class binary codes and show that the hashing functions learned in this way outperforms the state­ of ­the art, and at the same time provide fast retrieval times. In the second part, we also address the problem of supervised retrieval by taking into account the relationship between classes. For a given query image, we want to retrieve images that preserve the relative order i.e. we want to retrieve all same class images first and then, the related classes images before different class images. We learn such relationship aware binary codes by minimizing the similarity between inner product of the binary codes and the similarity between the classes. We calculate the similarity between classes using output embedding vectors, which are vector representations of classes. Our method deviates from the other supervised binary encoding schemes as it is the first to use output embeddings for learning hashing functions. We also introduce new performance metrics that take into account the related class retrieval results and show significant gains over the state­ of­ the art. High Dimensional descriptors like Fisher Vectors or Vector of Locally Aggregated Descriptors have shown to improve the performance of many computer vision applications including retrieval. In the third part, we will discuss an unsupervised technique for compressing high dimensional vectors into high dimensional binary codes, to reduce storage complexity. In this approach, we deviate from adopting traditional hyperplane hashing functions and instead learn hyperspherical hashing functions. The proposed method overcomes the computational challenges of directly applying the spherical hashing algorithm that is intractable for compressing high dimensional vectors. A practical hierarchical model that utilizes divide and conquer techniques using the Random Select and Adjust (RSA) procedure to compress such high dimensional vectors is presented. We show that our proposed high dimensional binary codes outperform the binary codes obtained using traditional hyperplane methods for higher compression ratios. In the last part of the thesis, we propose a retrieval based solution to the Zero shot event classification problem - a setting where no training videos are available for the event. To do this, we learn a generic set of concept detectors and represent both videos and query events in the concept space. We then compute similarity between the query event and the video in the concept space and videos similar to the query event are classified as the videos belonging to the event. We show that we significantly boost the performance using concept features from other modalities.

Nested Sampling and its Applications in Stable Compressive Covariance Estimation and Phase Retrieval with Near-Minimal Measurements

Compressed covariance sensing using quadratic samplers is gaining increasing interest in recent literature. Covariance matrix often plays the role of a sufficient statistic in many signal and information processing tasks. However, owing to the large dimension of the data, it may become necessary to obtain a compressed sketch of the high dimensional covariance matrix to reduce the associated storage and communication costs. Nested sampling has been proposed in the past as an efficient sub-Nyquist sampling strategy that enables perfect reconstruction of the autocorrelation sequence of Wide-Sense Stationary (WSS) signals, as though it was sampled at the Nyquist rate. The key idea behind nested sampling is to exploit properties of the difference set that naturally arises in quadratic measurement model associated with covariance compression. In this thesis, we will focus on developing novel versions of nested sampling for low rank Toeplitz covariance estimation, and phase retrieval, where the latter problem finds many applications in high resolution optical imaging, X-ray crystallography and molecular imaging. The problem of low rank compressive Toeplitz covariance estimation is first shown to be fundamentally related to that of line spectrum recovery. In absence if noise, this connection can be exploited to develop a particular kind of sampler called the Generalized Nested Sampler (GNS), that can achieve optimal compression rates. In presence of bounded noise, we develop a regularization-free algorithm that provably leads to stable recovery of the high dimensional Toeplitz matrix from its order-wise minimal sketch acquired using a GNS. Contrary to existing TV-norm and nuclear norm based reconstruction algorithms, our technique does not use any tuning parameters, which can be of great practical value. The idea of nested sampling idea also finds a surprising use in the problem of phase retrieval, which has been of great interest in recent times for its convex formulation via PhaseLift, By using another modified version of nested sampling, namely the Partial Nested Fourier Sampler (PNFS), we show that with probability one, it is possible to achieve a certain conjectured lower bound on the necessary measurement size. Moreover, for sparse data, an l1 minimization based algorithm is proposed that can lead to stable phase retrieval using order-wise minimal number of measurements.

Nonlinear Optics and Carrier Dynamics in Nanostructured and Two-Dimensional Materials

Understanding and measuring the interaction of light with sub-wavelength structures and atomically thin materials is of critical importance for the development of next generation photonic devices.  One approach to achieve the desired optical properties in a material is to manipulate its mesoscopic structure or its composition in order to affect the properties of the light-matter interaction.  There has been tremendous recent interest in so called two-dimensional materials, consisting of only a single to a few layers of atoms arranged in a planar sheet.  These materials have demonstrated great promise as a platform for studying unique phenomena arising from the low-dimensionality of the material and for developing new types of devices based on these effects.  A thorough investigation of the optical and electronic properties of these new materials is essential to realizing their potential.  In this work we present studies that explore the nonlinear optical properties and carrier dynamics in nanoporous silicon waveguides, two-dimensional graphite (graphene), and atomically thin black phosphorus. We first present an investigation of the nonlinear response of nanoporous silicon optical waveguides using a novel pump-probe method. A two-frequency heterodyne technique is developed in order to measure the pump-induced transient change in phase and intensity in a single measurement. The experimental data reveal a characteristic material response time and temporally resolved intensity and phase behavior matching a physical model dominated by free-carrier effects that are significantly stronger and faster than those observed in traditional silicon-based waveguides.  These results shed light on the large optical nonlinearity observed in nanoporous silicon and demonstrate a new measurement technique for heterodyne pump-probe spectroscopy. Next we explore the optical properties of low-doped graphene in the terahertz spectral regime, where both intraband and interband effects play a significant role. Probing the graphene at intermediate photon energies enables the investigation of the nonlinear optical properties in the graphene as its electron system is heated by the intense pump pulse. By simultaneously measuring the reflected and transmitted terahertz light, a precise determination of the pump-induced change in absorption can be made. We observe that as the intensity of the terahertz radiation is increased, the optical properties of the graphene change from interband, semiconductor-like absorption, to a more metallic behavior with increased intraband processes. This transition reveals itself in our measurements as an increase in the terahertz transmission through the graphene at low fluence, followed by a decrease in transmission and the onset of a large, photo-induced reflection as fluence is increased.  A hybrid optical-thermodynamic model successfully describes our observations and predicts this transition will persist across mid- and far-infrared frequencies.  This study further demonstrates the important role that reflection plays since the absorption saturation intensity (an important figure of merit for graphene-based saturable absorbers) can be underestimated if only the transmitted light is considered. These findings are expected to contribute to the development of new optoelectronic devices designed to operate in the mid- and far-infrared frequency range.  Lastly we discuss recent work with black phosphorus, a two-dimensional material that has recently attracted interest due to its high mobility and direct, configurable band gap (300 meV to 2eV), depending on the number of atomic layers comprising the sample. In this work we examine the pump-induced change in optical transmission of mechanically exfoliated black phosphorus flakes using a two-color optical pump-probe measurement. The time-resolved data reveal a fast pump-induced transparency accompanied by a slower absorption that we attribute to Pauli blocking and free-carrier absorption, respectively. Polarization studies show that these effects are also highly anisotropic - underscoring the importance of crystal orientation in the design of optical devices based on this material. We conclude our discussion of black phosphorus with a study that employs this material as the active element in a photoconductive detector capable of gigahertz class detection at room temperature for mid-infrared frequencies.