Unsupervised Deep Video Hashing with Balanced Rotation

1 Introduction

Hashing, also known as binary coding, has been an effective method for fast nearest neighbor search due to the low storage requirement and the high calculation efficiency of the XOR operation in the Hamming Space [Gong et al., 2013; Xu et al., 2013; Lin et al., 2016]. As a result, recent decade has witnessed its broad range of multimedia computing applications, such as Content-based Video Retrieval (CBVR).

Early-stage video hashing algorithms are prone to extracting frame-level features from the video so that the available image hashing techniques can be plugged in directly. Two representatives are Multiple Feature Hashing [Song et al., 2011] and Submodular Video Hashing [Cao et al., 2012], where the former encodes the extracted key frames while the latter characterizes the video by averaging features of individual frames. Later on, temporal features over successive frames are considered, including motion trajectory [Wang and Schmid, 2013] and temporal consistency [Ye et al., 2013]. This sort of features is proved to boost the performance even though temporal information might be partially lost during the frame pooling and dimensionality reduction.

∗This research was supported Royal Society Newton Mobility Grant (IE150997). Corresponding author: Jungong Han (jungonghan77@gmail.com).

Inspired by the great success of deep learning in image recognition, several recent systems have incorporated the hashing functions into the deep learning architecture. For example, Liong et al. [Liong et al., 2016] train a deep network to exploit the discriminative and temporal information of video, assuming the video pairwise information is available. Although this supervised deep network is capable of generating similar binary codes for videos belonging to the same category, labeling the training data is rather expensive, which hinders it from being used in the real-world applications. Alternatively, Zhang et al. [Zhang et al., 2016] propose a deep encoder-decoder framework, where a two-layer Long Short TermMemory (LSTM) unit followed by a binarization layer is able to directly encode the video features into compact binary codes. Minimizing feature reconstruction distortion allows feature extraction and binarization to be jointly optimized. Apart from the fact that such an encoder-decoder framework is quite complicated due to the involvement of debinarization and de-LSTM, the objective function based on minimizing reconstruction error does not seem to preserve the neighborhood structure of data, which is important for a similarity search task.

It can be observed that most existing video hashing techniques focus on seeking appropriate video features and wrapping them up as image features so that the binarization developed for image hashing can be adopted. In other words, there is no binarization specifically designed for the video features. Compared to the image features, video features normally acquire the temporal information of a video sequence, such as the video dynamics extracted by LSTM, which are likely to be more scattered (less correlated) in terms of distribution [Karpathy et al., 2016]. When projecting these scattered features into the low-dimensional compact space (e.g., using PCA), which is a necessary step of binarization, the data variances on projected dimensions tend to be large [Guo et al., 2016; Ding et al., 2016; Guo et al., 2017]. This imbalanced projection will degrade the performance of the generated hash codes because each dimension will be treated equivalently and allocated with the same number of bits in the quantization step afterwards. That is to say, directly applying image binarization to video features is unable to achieve effective hash codes for video retrieval. To address the above problem, we propose an end-to-end hashing framework (Figure 1), namely Unsupervised Deep Video Hashing (UDVH), with the aim to generate effective hash codes for fast retrieval. Our work differs from the existing methods in two aspects:

1. We propose an unsupervised deep hash framework and organize learning in a self-taught manner. Instead of minimizing feature reconstruction distortion [Zhang et al., 2016], our framework minimizes the quantization error of projecting video features to a binary hypercube, allowing the feature extraction and hash function learning to engage with each other. Involving the feature clustering in the code learning enables the neighborhood structure to be preserved. To solve the objective function, which is a non-convex problem, an alternate approach is proposed, where the rotation matrix, binary code generation and the deep framework parameters are jointly optimized.
2. During the code learning, balanced rotation specifically designed for video features is proposed to find a proper projection matrix such that the variance of each projected dimension can be balanced. The balanced variance is maintained in each dimension, thereby facilitating the quantization step afterwards. The experimental results reveal that this improved binarization is suitable for hashing video features.

2 Methodology

In this section, we will introduce the main algorithmic modules involved in the proposed framework. First of all, some notations are defined here for ease of explanation. Assuming that there are N videos in the training set and each video contains m frames. In UDVH, VGG-19 [Simonyan and Zisserman, 2014] is used to extract the 4096-d feature vectors for all frames. The input feature matrix is denoted as Z ∈ R4096×(N×m) and it remains fixed in UDVH. Our goal is to develop the deep hash function that encodes Z into kbit binary codes bN ∈ {-1,+1}N×k , where k << 4096. We further denote the video feature matrix from fc7 layer as Z ∈ RN×1024 . In the code learning stage, we first use K-means to categorize the training videos and then reduce the feature dimensionality by Canonical Correlation Analysis (CCA) [Hardoon et al., 2004]. We denote the video feature matrix after dimensionality reduction as H ∈ RN×k , where k is the targeted bit size. Finally, with the proposed rotation matrix R ∈ Rk×k , the binary code B ∈ {-1,+1}N×k can be generated to guide the hash function learning while iteratively updating the network parameters. In the following subsections, the proposed modules in UDVH will be elaborated.

2.1 Deep Hash Function

In this section, the deep hash function is defined along with a brief introduction about LSTM, which has been widely deployed in the sequence study for its powerful ability in dealing with the sequential input. The output of LSTM is actually depended on the previous state and the current input. Compared with the traditional Recurrent Neural Network (RNN) [Chung et al., 2014], LSTM overcomes the problems of vanishing and exploding gradient by adding the memory cell, which is designed to store information such that the longrange temporal relationship could be exploited [Srivastava et al., 2015]. Typically, a 2-layer LSTM unit is to tackle the frame-level features for the temporal-awareness. The framelevel features of training videos are encoded by the LSTM units sequentially and the encoded frame features are averagely fused by the connected fc7 layer to generate the video feature matrix Z. Thus, a robust representation for videos can be achieved taking both spatial and temporal information into account. We further denote the deep hash function as F(Z; θ), where θ represents the parameters from LSTM and fully-connected layers for the concise description. Those parameters will be updated automatically during the process of hash function learning, thus producing the desirable output.

2.2 Feature Embedding

At the beginning stage of code learning, the video feature matrix Z obtained from fc7 layer is clustered by K-means with the intention to classify the similar videos into the same category, where the clustering parameter K is randomly selected. Such a clustering process is repeated in each loop for the more precise categorization. After K-means, the training videos are represented by their feature vectors and the corresponding fake labels ({0, 1}N×K ). They provide dedicated supervisory information for the following binarization such that the similar videos would be represented by the similar binary codes. Subsequently, CCA is adopted to reduce the dimensionality of video feature into the required bit size as the projected video feature matrix H, where the correlation between features and labels is maximized and well preserved in the low-dimensional space. In contrast to PCA, CCA is more effective in extracting discriminative information with the robustness in anti-noise [Gong et al., 2013], thus obtaining more robust video features after the projection. We denote the projection matrix as P ∈ R1024×k , then the process of dimensionality reduction can be simplified as:

However, the projection concentrates the most information in a few top eigenvectors, which will lead to imbalanced data and may lower the hash code quality [Xu et al., 2013]. In the next section, we show the problem can be addressed by a novel rotation matrix.

2.3 Balanced Rotation

As mentioned previously, video features, compared to the image features, are likely to be more scattered in terms of distribution, leading to larger variance difference among projected dimensions. Usually, the quantization step after the projection treats each dimension equally and allocates the same number of bits to each dimension. That means the dimensions with low variance containing less information will have the same impact on Hamming distance calculation as the high variance dimensions containing more information. The hash codes generated by this scheme deemed ineffective. To address this problem, a balanced rotation matrix is required such that the information of each dimension is balanced and some important properties can be maintained. Firstly, the effect of rotation on the data variance is investigated, assuming the video features are zero centralized, i.e., ∑Ni=1 Zi = 0. Given the optimal projection P, the projected data H = ZP ∈ RN×k is obtained by Eq.(1). Since Z is centralized, the variance for the j-th dimension is vj = ∑Ni=1 H2ij /N. Given an orthogonal rotation matrix R and the adjusted data Ha = HR, the new variance of dimension v′j can be obtained. The sum of variance of each dimension can be calculated by:

Eq. (2) indicates that the sum of variance on all dimensions in the centralized data is invariant after rotation. Our goal is to find a rotation such that the variance of each dimension can be balanced. Specifically, the degree of balance can be measured by the variance of standard deviation (VSD) of each dimension. Denote the standard deviation (SD) of the j-th dimension as sj = vj 0.5 , VSD is computed as:

Theoretically, smaller VSD implies more balanced data. Hence, the goal can be achieved by finding a rotation which minimizes VSD. Directly minimizing Eq. (3) is, however, not intuitive. Based on the above analysis, we have ∑ki=1 s2i = ∑ki=1 vi = c, where c is a constant. Therefore, the VSD in Eq. (3) can be further deduced as:

So, it is straightforward to validate the following equivalence,

This indicates that minimizing the VSD of data by a rotation is equivalent to maximizing the sum of standard deviation (SSD). Furthermore, the SSD can be written in the matrix form as:

where ‖.‖2,1 is the l2,1-norm of matrix. Now, with Eq. (5) and Eq. (6), the rotation matrix which can balance the variance of each dimension can be learned from the following optimization formulation,

where Ik is the identity matrix. Eq. (7) is also the objective function of balanced rotation.

2.4 Learning Objective

In this section, we introduce the objective function of UDVH in details. There are two terms involved in defining the objective function. First, we use the binary code B as the guidance in the hash function learning, where the Euclidean distance is minimized between the output of top layer (fc8) in the deep network and B. It can be formulated as:

Considering also the balanced rotation, the final objective function of UDVH will be

where λ is the balance parameter. However, it is not possible to solve Eq. (9) directly due to the binary constraints.

3 Optimization

Since it is a non-convex problem with the binary constraints in Eq. (9), an alternate approach is proposed to optimize the objective, where the deep hash function F(Z; θ) can be learned by iteratively updating the parameters, such as θ, B and R, during each loop. Usually it takes just a few iterations to complete the optimization process for one specific bit size. Initially, a random value is specified to θ and the input matrix Z is encoded by the initialized deep network. Conducting clustering and dimensionality reduction can obtain the projected video feature. Afterwards, we carry out the following three steps to accomplish the goal.

Update R. With other parameters fixed, problem (9) is reduced to the orthogonality constrained l2,1-norm maximization problem in Eq. (7), which is defined as:

The above problem can be efficiently solved by the gradient flow method [Wen and Yin, 2013]. Specifically, we first define Mk = {R ∈ Rk×k : RRT = Ik} as the feasible set, which is also called the Stiefel manifold. Then, the tangent space for Mk is TRMk = {T ∈ Rk×k : TT R+RT T = 0}. Here, the basic idea is to find an optimal direction in the tangent space of current point R like conventional gradient descent, then project the direction to the feasible manifold, and replace the current point with the projected one. Iterating such steps and finally it will arrive at a stationary point. To optimize problem (10), the convergence theorem is proposed and illustrated as: given a point Rt in the feasible set, the below updating rule will lead to larger value unless it has arrived at a stationary point,

where Qt is the Cayley transformation matrix defined by

Here, the subscript t denotes the t-th iteration, τ is a step size satisfying Armijo-Wolfe conditions [Nocedal and Wright, 2006], and sti represents the standard deviation of (HRt)∗i. The above steps are iteratively executed until convergence and the obtained R is the rotation matrix.

Update B. By fixing Z, H and R, Eq. (9) has been reduced to:

Since we have obtained the rotation matrix R in the previous step and the binary code B can be directly computed as:

where sgn(x) = 1 if x > 0 and -1 otherwise. Update θ. With fixed Z, R and B, Eq. (9) is reduced to

This minimization problem can be solved by fine-tuning the deep network with Stochastic Gradient Descent (SGD) until it gets converged, where the Euclidean loss is minimized via mini-batch back-propagation and the low bound can be found. The network parameter θ is updated simultaneously and determined in the current loop after convergence. Then, the deep network can produce new video features for the next loop. Those parameters are updated sequentially for 10 loops and finally the deep hash function can be built. Given a query video Zq, we can create its hash codes with sgn(F(Zq; θ)). The overall UDVH is summarized in Algorithm 1.

Algorithm 1 Unsupervised Deep Video Hashing

Input: The input feature matrix Z; Randomly initialize deep parameters θ;

Output: F(Z; θ): deep hash function;

• 1: for t = 1 to 10 do
• 2: Obtain projected video feature matrix H;
• 3: Update rotation matrix Rt according to Eq. (11)∼(15);
• 4: Update binary code Bt according to Eq. (17);
• 5: Update deep parameters θ according to Eq. (18);
• 6: Until Convergence;
• 7: end for
• 8: return F(Z; θ);

4 Experiment

4.1 Datasets and Experimental Settings

In this experimental study, two large-scale video datasets are adopted, which contain:

FCVID [Over et al., 2014]: There are 91,223 videos collected from Youtube in the dataset, which are classified into

239 categories. It covers a wide range of popular topics, such as animals, events and various scenes. In the training phase, we randomly select 45,611 videos for the train split and the rest is used as the test split. In the retrieval phase, 1,000 videos randomly picked up from the test slip are used as the query and others form the gallery.

YFCC [Thomee et al., 2015]: It is the largest public video dataset, containing over 0.8M videos. Due to the invalid urls and the corrupted video files, about 0.7M videos have been processed in the experiment, where 0.1M labeled videos [Zhang et al., 2016] construct the test split in the retrieval while 0.6M unlabeled videos form the train split in the unsupervised learning. In the labeled split, there are 80 categories collected from the third level of MIT SUN scene hierarchy [Xiao et al., 2010]. For the fair comparison, we select 1,000 videos randomly as the query and 99,000 videos as the gallery. For each video, 20 frames are uniformly selected as the representation of the video.

The algorithm is implemented under the open-source Caffe framework [Jia et al., 2014]. The server configurations are: Intel Core i7-5960X CPU, 64GB RAM and a TITAN X GPU.

4.2 Baselines and EvaluationMetrics

Several recent hashing methods are adopted as baselines in the experiment, which are Deep Hashing (DH) [Erin Liong et al., 2015], Iterative Quantization (ITQ) [Gong et al., 2013], Submodular video hashing (SubMod) [Cao et al., 2012], Spectral Hashing (SP) [Weiss et al., 2009], Multiple Feature Hashing (MFH) [Song et al., 2011], Anchor Graph Hashing (AGH) [Liu et al., 2011] and Self-Supervised Temporal Hashing (SSTH) [Zhang et al., 2016]. Identical train and test sets are organized for all methods and the best performance is tuned based on the data settings in their papers. Regarding the evaluation, mean average precision at top K retrieved videos (mAP@K) [Over et al., 2014] is adopted as the main metric. Precision-Recall curve and precision within Hamming radius 2 curve are two additional ones [Davis and Goadrich, 2006].

4.3 Results and Discussions

Architecture Investigation. In the proposed framework, the number of clusters during the clustering is the only hyper parameter. Figure 2(a) shows the effect on mAP@20 when varying the cluster numbers. Due to the space limit, only the results of 64 bits and 128 bits are reported. Seen from the figure, the mAP value increases dramatically with the bigger cluster number selected at the beginning and remains stable over 400 categories. This indicates the cluster number has tremendous influence on the system performance. The sophisticated clustering encourages the similar videos to be classified into the same category such that similar hash codes can be generated for those videos. For both datasets, it seems that the performance get saturated when the cluster number reaches 400, meaning this parameter is easy to set. Additionally, the Euclidean loss during the hash function learning on FCVID is plotted in Figure 2(b). Clearly, fast convergence (after about 4 loops) can be achieved because of the dedicated LSTM units included in the proposed hashing framework.

Next, the retrieval results are evaluated by using various hashing strategies adopted in the phase of code learning in order to validate the claimed contributions. Three combinations are included: CCA+ITQ, PCA+BR and CCA+BR, as illustrated in Table 1. The results show combination of CCA and BR substantially outperforms the other two methods on the datasets. Compared with the PCA method, more valuable information is concentrated in the top eigenvectors by CCA after the dimensionality reduction because of the dedicated supervisory information (predicted labels) created by the clustering. It turns out the choice of CCA, rather than PCA, is sensible. Moreover, the comparison results of CCA+ITQ against CCA+BR clearly demonstrate that the balanced hash codes help to improve the retrieval performance.

Comparison with State-of-The-Arts. We also compare our UDVH with the baselines, given a retrieval task. Figure 3 shows the mAP@K results of various bit sizes on both datasets when using different methods. As can be seen, the proposed method outperforms the state-of-the-art hashing approaches significantly. Specifically, the mAP@5 value of our algorithm is 41.2% when using 128-bit code on FCVID, which is about 6% higher than the results achieved by the most comparable SSTH. The mAP curves are even more stable than the other methods with the increasing returned video number. When testing the algorithms on YFCC dataset, the mAP values of all algorithms drop down, compared to the results on FCVID using the same bits. The gap between the mAP@5 values of UDVH and SSTH is reduced trivially to around 4%, which is still big. The reason behind is that most videos in YFCC are taken by mobile phones from the amateurs instead of the professionals in FCVID [Thomee et al., 2015]. The video retrieval has become a more challenging task for the low-quality videos when using YFCC dataset. Figure 4 and Figure 5 respectively show the Precision-Recall and precision within Hamming radius 2 curves at various bit sizes on both datasets, in which the ranking number is 100 and the Hamming radius is 2. Compared with the results from several conventional hashing methods, the best performance is again achieved by UDVH on both evaluation metrics.

In Figure 6, the detailed performance of top-5 returned videos achieved by two methods, UDVH and SSTH, is illustrated when using 128 bits. Due to the limited space, only the results on FCVID are reported here. Given three query videos, our UDVH correctly finds five similar videos for each of them whereas SSTH makes mistakes in recognizing swimming amateur and dolphin. The major reason is that our UDVH tends to preserve the neighborhood structure by incorporating the clustering into the hash code learning, which is crucial for a nearest neighbour search task like this.

5 Conclusion

In this paper, a novel unsupervised video hashing framework called Unsupervised Deep Video Hashing has been proposed to address the existing problems in the large-scale video retrieval. Compared with the conventional video hashing methods, the proposed approach is clearly superior because the feature extraction, code learning and hash function learning are combined jointly in a self-taught fashion. Moreover, we applied a balanced rotation to the video-specific features such that the variance of dimensions when projecting them into low-dimensional space can be balanced, which helps to generate effective video hash codes. The effectiveness of proposed framework is demonstrated based on the superior retrieval results from two video datasets.