Supervised Set-to-Set Hashing in Visual Recognition

1 Introduction

Searching for similar data samples is a fundamental step in many large-scale applications. As the data size explodes, hashing techniques have emerged as a unique option for approximate nearest neighbor (ANN) search, as it can dramatically reduce both the computational time and the storage space. Successes are seen in areas including computer vision and information retrieval [Kulis et al., 2009; Sun et al., 2017; Wang et al., 2012a; Wang et al., 2016]. Hashing methods perform space partitioning to encode the original highdimensional data points into binary codes. With the resulting binary hash codes, one can perform extremely rapid ANN search that entails only sublinear search complexity.

Conventional hashing schemes concern point-to-point (P2P) search setting. They either depend on randomization and are data oblivious (represented by the classic Locality Sensitive Hashing - LSH), or are based on advanced machine learning techniques to learn hashing functions that are better tailored to the specific data and/or label distribution. The latter includes unsupervised [Gong and Lazebnik, 2011; Weiss et al., 2008], semi-supervised [Wang et al., 2012a; Wang et al., 2010], and supervised hashing [Kulis and Darrell, 2009; Salakhutdinov and Hinton, 2009; Mu et al., 2010; Liu et al., 2012a; Zhang and Li, 2014; Shen et al., 2015; Li et al., 2016; Weng et al., 2019].

A natural generalization of the point-to-point search is setto-set (S2S) search. For example, one can pose the facial image recognition problem as one that queries for a nearest subspaces to a given point [Wang et al., 2013]. Indeed, there are several recent attempts, studying point-tohyperplane search that is useful for active learning [Liu et al., 2012b], or subspace-to-subspace search [Basri et al., 2011] that models S2S search assuming linear structures in the sets.

In this paper, we consider the set-to-set search problem in its full generality. This general setting finds applications ranging from video-based surveillance to 3D face retrieval from collections of 2D images [Berretti et al., 2010; Tuzel et al., 2007; Sivic et al., 2005]. Compared to specialized settings discussed above that come with natural notion of distance, a central challenge here is how to measure the distance/similarity between sets. We propose a similarity measure that captures both the statistical and structural aspects of the sets (Section 3). To learn the hash bits, we adopt dyadic hypercut as a weak learner [Moghaddam and Shakhnarovich, 2002] to derive a boosted algorithm that integrates both the structural and statistical similarities. The whole framework is illustrated in Fig. 1. In this paper, we focus on image applications, and hence coin the name Image Set Hashing (ISH). However, the core components of the proposed framework can be extended to generic scenarios.

2 RelatedWork

In this section, we discuss representative works in randomization-based hashing and learning-based hashing for P2P setting, and recent work on certain restricted S2S setting. Review of recent development of hashing techniques can be found in [Wang et al., 2016; Wang et al., 20114].

LSH hashing and variants are iconic randomization-based hashing schemes. They are simple in theory and efficient in practice, and flexible enough to handle various distance measures [Charikar, 2002; Datar et al., 2004; Kulis and Darrell,

2009]. However, the data oblivious design of the LSH family methods often causes suboptimal recall-precision tradeoff curve. Hence, learning-based hashing schemes have been under active development recently. Generally, both the data and label information is fed into carefully designed learning pipeline to produce more adaptive and efficient hash codes. Depending on whether the label information is in use, these schemes are either unsupervised, e.g., spectral hashing [Weiss et al., 2008], graph hashing, and ITQ (iterative quantization) [Gong and Lazebnik, 2011], or (semi-)supervised hashing, including [Lin et al., 2013; Liu et al., 2012a; Mu et al., 2010; Norouzi and Fleet, 2011; Sablayrolles et al., 2017; Wang et al., 2010]. Particularly, recent efforts have built more powerful hashing schemes on top of deep learning [Salakhutdinov and Hinton, 2009; Salakhutdinov and Hinton, 2007; Liong et al., 2015; Masci et al., 2013]. All these methods only deal with the P2P setting.

Study of the S2S setting started only very recently, and is mostly about image applications. Statistical or geometric assumptions are often made on the sets to facilitate representation. For example, statistical distribution of data points in each set can be assumed, and KL-divergence can be used to measure set similarity [Arandjelovic et al., 2005]. By comparison, point sets can also lie on linear subspaces or more general geometric objects [Cevikalp and Triggs, 2010; Hu et al., 2011; Kim et al., 2007; Liu et al., 2014; Sun et al., 2014; Sun et al., 2015; Wang et al., 2012b]. Among the representation schemes, representation based on covariance matrices has led to superior performances on image sets (video frames) [Wang et al., 2012b; Lu et al., 2013; Tuzel et al., 2007]. For instance, in [Li et al., 2015], covariance matrix is used in such way, and similarity is then measured via kernel mapping and learning. Promising result has been reported, but the framework is restricted to cases when the query is a single point. For image applications specifically, the Set Compression Tree [Relja and Zisserman, 2014] compresses a set of image descriptors jointly (rather than individual descriptors) and achieve a very small memory footprint (as low as 5 bits). However, all existing representation methods do not account the holistic structural information; this may lead to incorrect similarity measurements on highly nonlinear data distributions. Our representation and hashing scheme is a first attempt to directly address the above problems in the general S2S setting.

3 Structural and Statistical Modeling

In this section, we detail how the structural and statistical information is extracted from the point sets, and how similarity between sets is measured.

3.1 Structure via GraphModeling

The idea here is to use graph for discovering structures within data, and then measure the similarity via appropriate kernel mapping on graphs [Tenenbaum et al., 2000; Gartner, 2003; Zhou et al., 2009], Fig. 2 gives an example.

To model data points within a set, we derive an affinity matrix A based on quantized pairwise distances [Zhou et al., 2009]: if the distance is larger than a predefined threshold θ, the corresponding affinity value in A is set to 0, and 1 otherwise. We use xi's to denote the point sets, and Ai 's to denote the corresponding affinity matrices thus constructed. With all the Ai 's at hand, the point set similarity is defined as:

where, Aip = 1◁ 󰁓ni u=1 aipu , Ajq = 1◁ 󰁓nj v=1 ajqv and g(xip↪ xjq) = exp(-γg 󰀂 xip - xjq 󰀂2 ). The parameter γg is a constant and ni and nj are the number of data points in xi and xj, respectively.

To understand the captured structural information, each clique (formed by several 1 elements) in Ai can be regarded as one concept. If Ai is an all-one matrix, all data points in one set belong to one concept and each point set is considered as one data point. When Ai is an identical matrix, each data point is independent, and no relation can be discovered. When Ai is a clique-based matrix, data can be clustered into cliques and Kg is a clique-based graph kernel. In this way, we leverage the structural information for our set hashing.

3.2 Statistical Information

Covariance matrices have provided effective local region representation for visual recognition and human identification [Tuzel et al., 2007; Liu et al., 2014]. Intuitively, they describe the local image statistics. In this work, we use covariance matrices to depict the statistical variance of images within each set. Given N image sets, X = ¶(x1↪ l1)↪ · · · ↪ (xi↪ li)↪ · · · ↪ (xN↪ lN)♦. xi = ¶xi1↪ · · · ↪ xi↪ni ♦ is an image set, where xi↪j ∈ Rd represents the jth d-dimensional feature vector in xi, and the set consists of ni images. li's are the labels of each image set. Each image set is represented with a d × d covariance matrix:

where ¯xi is the mean feature vector within the set. The diagonal elements of Ci represent the variance of each individual image feature, and the off-diagonal elements are their respective covariance. In this way, the covariance modeling can provide a desirable statistic for semantic variance among all images for an image set. Moreover, we use Gaussian-logrithm kernel [Jayasumana et al., 2013] to map each covariance matrix of an image set into high dimension space, as follows:

where γs is a positive constant, which be set to the mean distances of training points. Kernel matrix Ks, is for the image sets in Riemannian space and 󰀂 · 󰀂F denotes the matrix Frobenius norm. In the end, each pair of image sets xi and xj are mapped by the Kg and Ks kernel functions into a high dimensional space.

4 Image Set Hashing

4.1 Learning Framework

Suppose we have an image set dataset X = ¶xi↪ li♦. The goal of hashing is to generate an array of appropriate hash functions h : Rd 󰀁→ ¶0↪ 1♦ by a designed function Ψ and each bit is constructed by h(x) = sign(Ψ(x)). However, there is no straightforward way to generate hash codes for each image set. Inspired by [Vemulapalli et al., 2013; Li et al., 2015; Wang et al., 2012b] , we develop a mapping framework to construct hash codes for image sets in a common Hamming space based on multiple kernels. Kernel methods [Hamm and Lee, 2009; Jayasumana et al., 2013; Vemulapalli et al., 2013; Wang et al., 2012b] are known to capture and unfold rich information in data distribution. After the mapping process, we can generate hash codes in a Hamming space by simultaneously considering the structural and statistical information and iteratively maximize the discriminant margins based on multiple kernels learning.

4.2 Weak Learners with Boosting Algorithm for Hash Functions

Since a multi-class classification problem can always be treated as an array of two-class problems by adopting oneagainst-one or one-against-all strategies, we design a boosting algorithm to learn binary splits for constructing hash functions. Specifically, we consider dyadic hypercut [Moghaddam and Shakhnarovich, 2002] with multiple kernel functions. A dyadic hypercut f is generated by a kernel with a pair of different labels in training samples, where f is parameterized by positive sample xa , negative sample xb , and kernel functions ¶Km♦,i.e., m indicates statistical kernel (Ks) or structural kernel (Kg), and can be represented as follows:

where ε ∈ R is a threshold. The size of the totally generated weak learner pool is ♣f ♣ = M × na × nb, where M, na and nb are the numbers of kernels, positive training samples and negative training samples, respectively. With an efficient boosting process, we iteratively select a subset of weak learners by considering the learning loss.

Note that the learning process may be susceptible to overfitting when ♣f♣ is large. To alleviate this issue, we adopt a boosting algorithm [Freund and Schapire, 1995; Moghaddam and Shakhnarovich, 2002] to combine a number of weak splits (weak learners) into a strong one. Specifically, we iteratively select the discriminant weak learners generated from multiple kernels via maintaining a weighted distribution wt over data. Each iteration t produces a weak hypothesis f(x) : x → ¶+1↪ -1♦ and a weighted error δt . The learning algorithm is aimed at selecting weak learner f t for minimizing δt followed by updating next distribution wt+1 . We adopt exponential loss [Freund and Schapire, 1995] and minimize the loss function to select the best weak learner f t at iteration t and the best weak learner is computed as:

where wt i indicates the weight of xi at iteration t. Once obtaining the best weak learner, we update the data distribution based on weighted errors. The linear combination of weak learners, i.e., a strong split, is computed as follows:

where λt = 12 log 1-δt δt . Each iteration t, F = 󰁓t-1 τ=1 λτ f τ is a linear combination of the (t - 1) weak learners.

4.3 Objective Function

With the designed hash functions, the following are desired properties of the hash codes: (1) Each hash value is independent of the binary representation for each sample. (2) When samples are close to each other in feature space (e.g. with similar distributions), the hash codes should induce similar hash values with a small Hamming distance. (3) In the resulting Hamming space, different contents of samples should have different hash codes, which push different samples of categories as far as possible, meanwhile gather the samples of the same category close to each other. Based on the criteria, we derive our multiple kernel hashing as follows:

where Hr′ i ∗ is the hash value of the ith image set using the r′ th strong split, i.e., hash function, and r and q represent the retrieval and query sets in the training process. R is the number of the splits and Ω = 󰁓Tt=1 (λtq f tr′ q (xi)+ν2λtr f tr′ r (xi)). f r′ ∗ is the r′ th strong split generated from the number of T weighted weak learners (in eq. (6)), λt∗ is the coefficient of weak learners trained via a boosting algorithm, ν1 and ν2 are constant parameters.

The minimization of the first two terms, i.e., Ds and Dc, tend to find an optimal difference of the distance between intra- and inter- categories, which capture the discriminative property among all the samples and are defined in eq. (8) and eq. (9), and d(·↪ ·) indicates distance measure in Hamming space. In addition, Dc can refine the hash codes generated from the training image sets (q and r parts) by maximizing the separability of category algorithm in [Rastegari et al., 2012]. Simultaneous consideration of the two distance functions helps to minimize the within-category distances and meanwhile maximize the between-category dis. By formulating the structural and statistical information with multiple kernels for our objective function, the image set hashing becomes more robust and discriminative.

where M and C are represented as intra- and inter-category, H∗ can be Hq or Hr, and ν3 and ν4 are the pre-computable constant parameters to balance the intra-catetory and intercategory scales.

4.4 Optimization

The objective function optimization problem 7 is a typical nonsmooth, nonconvex multiple variable minimization problem. We derive an iterative block coordinate descent algorithm [Tseng, 2001] for the optimization. Algorithm 1 gives the entire algorithm. Here, we highlight several critical steps in our algorithm. We first compute the kernel matrices Kg and Ks with eq. (1) and eq. (3) for q training and r training image sets. After the kernel computation, we adopt kernel PCA [Scholkopf et al., 1997] for the q and r two parts to obtain the initial hash codes, i.e., Hq and Hr, based on their statistical kernels in Step 1 to Step 3. Next, we update the Hq and Hr codes by optimizing eq. (8) for seeking the

Algorithm 1 Image Set Hashing

Input: a set of training image sets, X = ¶xi↪ li♦ is divided into q and r two training image set parts, where xi = ¶xij♦ni j=1 ∈ Rd , i ∈ ¶1↪ 2↪ · · · ↪N♦, li = ¶1↪ · · · ↪L♦.

Initialize: Compute kernel matrices for q training image sets, i.e., (Km)q, by using the kernel functions (Kg and Ks) according to eq. (1) and eq. (3); Similar to r training image sets, (Km)r

• 1: Vq ∈ RN×R, Vr ∈ RN×R ← kernel PCA with statistical kernels for Kq and Kr, respectively
• 2: Hq ← sign(V ⊤ q (Ks)q)
• r (Ks)r)
• 3: Hr ← sign(V ⊤ Optimization:

4: while not converged do

• 5: Optimize Hq , Hr with eq.(8)
• 6: Train R splits by weak learner selection in e.q.(6) on q kernels (Km)q by using Hr as training labels, and inversely train another R splits on r kernels (Km)r by using Hq as training labels

• 9: Optimize H = [Hq↪ Hr] ∈ ¶0↪ 1♦R×2N with eq.(9)
• 8: Hr ← sign(󰁓Rr′=1 F r′ r (x)) ← (Km)r
• 10: Train R splits by weak learner selection in e.q.(6) on q kernels (Km)q by using Hr as training labels, and inversely train another R splits on r kernels (Km)r by using Hq as training labels
• 11: Check the convergence condition

12: end while

• 13: Output: 󰁓Rr′=1 F r′ q (x) and 󰁓Rr′=1 F r′ r (x) for query and database encoding in the testing process, respectively.

discriminability and utilize an efficient subgradient descent algorithm [Rastegari et al., 2012] for the binary optimization (the optimization algorithm gives the generated code with two properties: sample-wise balance and bit-wise balance.). In Step 6, we use the updated hash codes, Hq and Hr, to train R two-class strong splits based on multiple kernels. More specifically, we adopt cross-training strategy [M. Rastegari J. Choi and Davis, 2013] by using the hash codes, Hr, as training labels to train the strong splits with q training image sets and similar process to Hq hash code with r training image sets. After that, we update the current hash codes, Hq and Hr by using the learned strong splits based on multiple kernel learning. In order to improve the discriminability, we combine Hq and Hr together to refine the learned hash codes with eq. (9). The process is then repeated. Convergence typically occurs within few outer iterations. Once we obtained the two strong split models (󰁓Rr′=1 F r′ q (x) and 󰁓Rr′=1 F r′ r (x) in Algorithm 1), we can adopt them to generate query and database hash codes in the testing process, respectively.

5 Experiments

We evaluate the effectiveness of the proposed Image Set Hashing (ISH) method on two well-known benchmarks, CIFAR-10 and TV-series, i.e., Big Bang Theory. We also conduct extensive comparison studies with state-of-the-art methods, including Locality Sensitive Hashing (LSH) [Indyk and Motwani, 1998], Spectral Hashing (SH) [Weiss et al., 2008], Kernelized LSH (KLSH) [Kulis and Darrell, 2009]; Semi-Supervised Hashing (SSH) [Wang et al., 2010] and supervised methods, Kernel-Based Supervised Hashing (KSH) [Liu et al., 2012a] and Hashing across Euclidean space and Riemannian manifold (HER) [Li et al., 2015]. For the competing techniques, we adopted the publicly released codes of SH, KLSH, KSH and HER in our experiments.

5.1 Experiment on CIFAR-10

We compare the performance for different hashing techniques on the CIFAR-10 dataset. As a labeled subset of the 80M tiny images, the CIFAR-10 dataset consists of a total of 60K color images, each of which has the size of 32 × 32 resolution. The dataset contains 6K image samples with ten object categories. To evaluate the performance, we uniformly and randomly sample images from each category to form a total of 195 image sets, each of which contains about 25 ∼ 50 images for the training process (q and r two parts), 100 image sets as query in testing and 1577 image sets for the testing database in KLSH, KSH, HER, ISH methods. To test the LSH, SH and SSH methods, we randomly select 1K images as queries and the remaining as database samples. For feature representation, each image is represented as a 512-dimensional GIST feature vector [Oliva and Torralba, 2001].

We evaluate two test scenarios: Hamming ranking and hash look-up. In Fig. 3 and Fig. 4 show the mean recall and precision curves from different number of returned search samples when using 24-bit hash codes. As we can see, the proposed ISH method produces higher quality of Hamming embedding since it significantly outperforms the competing methods in terms of precisions, recalls, and MAPs. In general, the methods using set information often provide better performance than those based on P2P settings. For instance, the HER method generates the second best MAPs for most of the test cases. The relative performance gains in MAP ranges from 6% to 23▷6% compared to the HER method. Such performance gains confirm the value of exploring statistical and clique-based structural information for hash function design. In Fig. 5, we also evaluate the results using the hash look-up table strategy by showing the precision curve within Hamming radius 2 for hash codes from 8-bit to 48-bit. Again the proposed ISH method achieved the best precisions across all the cases.

5.2 Experiment on TV-series

The Big Bang Theory (BBT) video (image set) benchmark 1 was collected by [Bauml et al., 2013] and contains in 3341 face videos from 1 ∼ 6 episodes of season one. The dataset includes around 5 ∼ 8 main cast characters and has multiple characters at the same full-view scene shot. Even though most of the scenes are taken in indoors, it is still extremely challenging since the resolution of faces regions are quite small with an average size of 75 pixels. In the experiments, we use the provided face features, which are extracted from face videos by block Discrete Cosine Transformation (DCT) feature. In this way, each face is represented by a 240dimensional feature vector.

In the experiments, we have two different settings. For the first setting, we follow the setting used in [Li et al., 2015] and apply still images for the q part in training and query in testing process and denote the setting as ISH0 . The second setting indicated as ISH, we have 150 image sets for q and r two parts in the training process, respectively. For query in testing, we use 100 image sets and the remaining image sets for database. The setting can completely utilize statistical and structural information. For the comparison, the first group of compared methods consists of seven pointto-point (P2P) hash methods, i.e, LSH, ITQ, SH, Discriminative Binary Codes (DBC) [Rastegari et al., 2012] , SSH, MM-NN [Masci et al., 2013], and KSH (point). In addition, we generate kernels for image sets (represented by covariance matrices) and employ them as input for the KLSH, KSH (set), and HER methods. Thus, we have the second group of methods that uses kernels for image sets. Such a modification can be used to further justify the advantage of explore the structural and statistical information of image sets. The performance evaluated by MAPs for the compared methods is shown in Table 1. We vary the number of hash bits from 8

1 https://cvhci.anthropomatik.kit.edu/ baeuml/datasets.html

Number of bits

Number of bits

Figure 5: Mean precision curves of Hamming radius 2 in 24 bits on CIFAR-10 dataset. The curves of LSH, SH, SSH are randomly sampled.

to 128 bits. As we can see, the method (ISH0 ) generates the second best MAPs when structural information is ignored in the q training and the query testing process. Moreover, ISH method achieved the best performance for all the tested cases when both of statistical and structural information are considered. This evidence shows that the structural information can help to generate more robust and discriminative hash codes.

In addition, we use 128-bit hash codes and show the performance curves for the seven compared methods. Fig. 6, Fig. 7 and Fig. 8 show the precision, recall, and precisionrecall curves, respectively. From these results, the proposed ISH achieves the best performance compared to all the baseline techniques, including both P2P methods and modified S2S methods. The underlying reason lies in that the ISH method can simultaneously capture the statistical (covariance matrix) and structural (graph kernel) information, i.e., combination of weak learners, to generate each hash code. Hence, it captures the most intrinsic characteristics within complicated variations of face images for the same subject. Moreover, if we compare the general performance between the P2P and S2S settings for the KSH method, we can observe that the S2S

hashing continuously attains higher search accuracy. It further confirms the advantage of using set information. However, simply employing the covariance matrix as inputs limits the performance improvements. In summary, with the S2S setting and fully explore statistical and structural information, the proposed ISH yields significant performance gain across all the experiments.

6 Conclusion

We have presented a set-to-set (S2S) ANN search problem and proposed to learn the optimal hash codes for image sets by simultaneously exploiting the statistical and structural information. The key idea is to transform the image sets into a high dimension space where each of image set can be characterized by a graph kernel and statistical measurement. As a result, the proposed S2S hashing achieves a robust and discriminative representation for searching datapoint sets. The experimental results have demonstrated the effectiveness of the proposed ISH method by showing superior performance over several representative competing approaches.

The number of samples

Figure 7: The evaluation results by mean recall curves for Hamming ranking using 128 bits on the BBT dataset.