Late Fusion of Local Indexing and Deep Feature Scores for Fast Image-to-Video Search on Large-Scale Databases

Low cost visual representation and fast query-by-example content search are two challenging objectives which should be supplied for web-scale visual retrieval task on moderate hardwares. In this paper, we introduce a fast yet robust method that ensures these two objectives by obtaining the state-of-the-art results for the image-to-video search scenario. For this purpose, we present critical improvements to the commonly used indexing and visual representation techniques by promoting faster, better and modest retrieval performance. Also, we boost the effectiveness of the method for visual distortions by exploiting the individual decision scores of local and global descriptors in the query time. By this way, local content descriptors effectively depict copy/duplicate scenes with large geometric deformations, while global descriptors are more practical for the near-duplicate and semantic search. Experiments are conducted on the large-scale Stanford I2V dataset. The experimental results show that the method is effective in terms of complexity and query processing time for large-scale visual retrieval scenarios, even if local and global representations are used together. Moreover, the proposed method is quite accurate and obtains state-of-the art performance based on the mAP score on the dataset. Lastly, we report additional mAP scores after updating the ground annotations obtained by the retrieval results of the proposed method which demonstrates the actual performance more clearly.


INTRODUCTION
In the last decades, we have witnessed an unprecedented multiplication of web-driven multimedia data due to the increasing trend on social websites. Eventually, this aggravates to retrieve a target query from large multimedia collections with moderate hardware configurations.
In the literature, existing works [1,2,3,4,5,6,7,8,9] primarily account two objectives, high performance and fast querying, since visual representation is carried out in an offline stage before querying occurs. However, a fundamental question which needs to be addressed is that 'Is it enough Project Website: https://github.com/savasozkan/i2v to obtain the highest and fastest accuracy so as to deploy a complete retrieval system for users? '. A reasonable answer should be that particularly for larger multimedia database (i.e., approaching to real-world scenarios), the solutions need be aware of hardware limitations to mitigate the problem in terms of complexity of the offline step.
In this work, we present a visual multimedia retrieval method which particularly aims to obtain high retrieval accuracies while keeping the content representation/indexing compact. Our main contributions are as follows: • In this work, we exploit local and glocal clues together since use of both local and global visual features play a critical role to disentangle the weaknesses of each feature with other's superiority. More precisely, local features tend to attain better performance under severe scale, rotation and translation changes [10,11,1]. In similar, global descriptors can yield superior results on semantic tasks by the fact that they mostly rely on the part-based visual representations [12,13,5,6]. For this purpose, we lately fuse the confidence scores of local and global descriptors computed for the same scenes with a novel fusion technique. This scheme is inspired by the notion of query expansion [14]. In short, the features (either local or global features) tend to reflect a similar error characteristic for the queries after some ranked points. To this end, the proposed method is able to normalize the confidence scores of both local and global features and fuse in the final ranked list by adaptively selecting a settling point for each individual query.
• In particular, utilization of local and global descriptors for retrieval scenario can contradict with the low cost computation constraint. Hence, we introduce critical improvements to the commonly used indexing and global pooling techniques, namely, Product Quantization (PQ) [15] and Compressed Fisher Vector (CFV) [16], to balance the workload and to promote modest visual description. In short, we propose a non-parametric score function to compute the probabilistic similarity scores between local features of query and reference data in an asymmetric PQ space. Ultimately, this function enables us to assess the quality of matches by the probabilistic scores than Euclidean distances. Furthermore, we replace handcrafted features [10,11] and sparse keypoints [10,1] with Fig. 1. Some of non-annotated scene samples unveiled by our retrieval results on Stanford I2V dataset. Our method is capable of retrieving queries with severe viewpoint and conditional changes at the top of the ranked list.
densely sampled mid-level convolutional features. Note that this step still has the low computation workload, since deep features are densely estimated. In addition, semantic content can be depicted more precisely with deep features [5,7] which differs from the local feature content (relevent to the goal of our work). Last but not least, we apply an approximate binary nearest neighboring search (NN) to make querying up to 6x faster for CFV with a minor decrease in the accuracy.
• To this end, the proposed method enables fast query and low computational workloads for large-scale datasets while outperforming the baselines by a large margin.
• Lastly, the ground truth annotations for Stanford I2V dataset are updated by the retrieval results of the proposed method, thus more reliable performance evaluation becomes possible for the future works.

RELATED WORK
Here, we review fundamentals and most recent studies related to visual content search task. Local and Global Descriptors. With the advent of sparse local features [10,11,1], the idea instantly becomes popular for the visual representation domain. However, the direct usage of these features is not quite possible due to their dimensionality and large body. Capturing composite descriptor relations by partitioning the feature space into multiple clusters is a pioneering technique to ease this limitation [2]. However, in order to achieve discriminative hash codes, the cluster size should be quite large even if an approximate search is utilized [3]. Product quantization [15,17] significantly reduces the cost of feature space partitioning as well as mapping, since the complexity is reduced by splitting the feature into multiple sub-vectors. Recently, the studies concentrate on the adaptation of end-to-end learning techniques. PhilipNet [18] learns the best descriptors from a visual patch set to obtain similar features under severe transformations. Yi et al [4] propose a deep network pipeline for keypoint detection, orientation estimation and visual description in an unified manner. However, here, the main problem is that relatively high hardware configurations are needed to complete the computations in the acceptable time.
On the other hand, orderless feature pooling (i.e., global descriptors) is an important technique for retrieval tasks to produce a description from an independent set of features [12]. Similarly, the large dimensionality aggravates the direct use of these descriptors. Although PCA-like methods can be used to transform the descriptor to several principal axes, binary codes can be calculated with a threshold [16] which provides several advantages as explained in [19].
Similarly, Babenko et al. [7] compute deep features from different fragments of images and aggregate them with the VLAD descriptor [13]. NetVlad [8] is a trainable generalization of VLAD to recognize the geo-location of images. Gordo et al. [9] improve performance on the visual landmark retrieval task by finetuning a deep model with a triplet siamese loss. Lastly, [20] shows that local and global descriptors should be jointly used to eliminate possible outliers for the accurate retrieval. However, note that these methods need labeled data to train/finetune the high-level features which is not quite possible for all datasets. Low Offline Workload. As stated, there are a limited number of studies that primarily take the low computational workload objective into consideration in the literature [16,21]. The solutions particularly rely on representing the scene with a global visual descriptor and the content around sparsely sampled points is used to achieve a reasonable computational workload. However, these descriptors tend to capture the content mostly from background and/or repetitive parts [22] than particular object(s) in the scenes. Moreover, the discriminative power of the representations (i.e., for binary codes) can decrease exponentially when the database size is increased [23]. Therefore, the single use of global descriptors remains weak for large-scale datasets and additional representations should be exploited without sacrificing the computational workload too much.

PROPOSED METHOD
Our main goal is to enhance the strength of visual retrieval task by exploiting the confidence scores of both local and global descriptors for the same scenes. In addition, it should have a low computation workload so as to be applicable for large-scale data.
Since our model is formulated as an image-based approach, key frames are initially sampled from a sequence of video frames V = {v 1 , v 2 , ..., v n } based on a simple rule. This rule enforces an uniform sampling strategy -1fps-and a constraint that each possible frame should not contain any subregion with large motion variations. Otherwise, these frames are discarded. To this end, more stable content is extracted (i.e., less motion blur that can hurt the performance) by reducing the total number of key frames.

Local Visual Content Representation
In this step, the local visual content of a frame is computed from sparsely sampled keypoints and then converted into compact hash codes. In short, two-stage quantization-based approach is utilized for fast querying as well as low computational workloads. Moreover, geometric consistency between local features is enhanced with fast geometric filtering at the end. Local Sparse Features. For local representation, we use Root SIFT [24] and Hessian Laplacian [1]. Since they are partially robust to scale and orientation changes, we expect to successfully retrieve any query that exhibits strong geometric deformations (duplicate/copy) from the reference set.
In addition, so as to find the geometric adjacency of local matches at the voting step, we store coordinate (x, y), orientation (θ) and scale (s) properties of each local point in the quantized forms. Feature Indexing. As mentioned, the direct use of local features is impractical and they should be converted into small representations. The idea of Bag-of-Word-like [2] methods is to quantize (1) each feature vector f h ∈ R 128 (note that dimension of SIFT is 128 and k-means is used) to the closest center c i in a pre-clustered feature space C bow ∈ R D bow ×128 : However, the number of cluster centers should be sufficiently large (e.g. D bow > 100K) in order to achieve dis-criminative space partitions [3]. This requirement eventually causes an increase in the offline computations and aggravates to represent the visual content with local features.
In our work, a rational computation workload is achieved by encoding the residual vector (r = f h −c i ) along side of the coarse feature q b (.) with an additional quantizer. For this purpose, relatively smaller cluster sizes (i.e., D bow ≈ 10K) can be selected. PQ space [15] .., C m pq }, C k pq ∈ R Dpq×128/m is selected to maximize the information bit per component by splitting the residual vector into m nonoverlapping subvectors r = {r 1 , r 2 , ..., r m } as follows: To this end, each feature vector is converted into two interrelated hash codes where h b = q b and h pq = {q 1 pq , q 2 pq , ..., q m pq }, and they are stored in an inverted file structure based on their h b values. Throughout this work, m and D pq are empirically set to 8 and 256 as in [15]. In a nutshell, computation cost is exponentially reduced by the low cost two-stage indexing scheme and local representation becomes applicable for large-scale databases. Local Voting Scheme. In voting scheme, we follow a twofold approach: First, we estimate the best local matched candidates by using the similarities between hash codes. Later, based on the dominant geometric model between query and reference frames, the outliers are eliminated.
Formally, in order to say that query and reference local points are similar, the coarse hash codes should be same (h q b = h r b ) while the residual similarities (h r pq and h q pq ) must be within a certain error tolerance. Otherwise, the similarity score is set to zero and discarded from the initial query candidates.
In this work, we propose a novel non-parametric score function for PQ Euclidean space to be used in the residual similarity calculations. Ultimately, this score function normalizes the asymmetric Euclidean distance of two residual hash codes with the maximum asymmetric distance between all cluster centers. Later, a final residual similarity score is equal to the average of all subvector scores: where d k indicates the maximum asymmetric Euclidean distance for k th subvector, i.e., d k = max c i − c l 2 , ∀i, l ∈ D pq , c i , c l ∈ C k pq . This non-parametric function enables us to assess the similarities within [0,1] (w pq (., .) ∈ [0, 1] ) than varying Euclidean distances.
After the initial residual similarity scores are obtained by using Eq. (3), the hard-similarity score (the scores can be equal to either 0 or w pq ) is determined by applying a coarse threshold τ pq . Practically, this step improves the method by selecting the best matches yielding high confidence scores and it removes possible outliers immediately. Moreover, we prune 5% of the codewords according to their term frequencies to reduce the drawback of stop words [2] and to speed up the querying. Note that the hard-similarity scores (w pq (., .) > τ pq and h q b = h r b ) are also weighted by this frequency term.
Later, we filter out the outliers (i.e., the ones that not obey to the dominant geometric model between query and reference frames) by enforcing a 4-dof geometric constraint (affine transform might yield better results, however it increases query time) (4) on the initial query candidates: where s = s q − s r and θ = θ q − θ r are the differences of scale and orientation parameters for query and reference points. (t x , t y ) is also the spatial translation between query and reference local points, and their values are estimated from Eq. 4. Simply, the geometric model computes a histogram by using the joint parameter distributions of scale (log( s)), orientation ( θ) and translation ((t x + t y )/ s) values between the query candidates of each frame. Later, the highest scored bin (sum of all hard-similarity scores that fit to the dominant parameter distribution) yields the dominant geometric model between the local points. To this end, the value of the dominant bin is set as the final local confidence score of the frame.

Global Visual Content Representation
To obtain a global visual representation for each frame, first, pretrained deep convolutional features are densely sampled and reduced by PCA to lower dimensions. Then, these features are aggragated with Fisher Kernel [12] and tranformed into binary hash codes. To ease the querying stage, these binary codes are compared with an approximate NN search setting in Hamming space. Dense Deep Convolution Features. We use densely sampled pretrained deep convolutional features f d ∈ R 384 obtained at Alexnet-conv3 layer [5] by discarding zero paddings in the convolution layers. As proved [5,7,6], deep features depict the semantic content of a scene more precisely compared to hand-crafted features. By replacing the hand-crafted features, we possess such semantic model with the local structures to realize a complete retrieval method. Furthermore, we select conv3 features to keep the computational complexity low. Later, densely sampled features are mapped to 64 dimensional space by PCA. There are two main reasons: First, [7] shows that PCA-compressed deep features are more robust since degrading the sparsity of features on a different visual set can improve their generalization capacity for unseen examples. Second, it provides time advantages for the computations in feature pooling and voting stages.  [12] to estimate one compact representation v ∈ R 64×D f k for each frame (D f k is the number of Gaussian mixture components).
Since the dimensionality does not allow us to search and store them in large-scale databases, they are converted into binary codes b by applying a zero-bias threshold rather than quantization-based approaches. The main reason to select a threshold-based approach is that [19] shows that Euclideanbased quantization can be misleading for high dimensional representations. We also proved this assumption in our experiments.
In addition, even if converting a high-dimensional descriptor into a compact binary code speeds up the query time, there is still room to further eliminate the redundant calculations for our method. In this work, we replace the standard brute-force binary search with an approximate nearest neighboring (NN) scheme.
In the proposed method, initial matched candidates for global binary codes are obtained based on k-NN results in Hamming space (i.e using inverted index structure same as local descriptors). Later, full distances (5) are computed by only comparing these candidates to improve the confidence scores of query and reference frames.
where g h (., .) is the score function which returns the normalized hamming distance for two binary codes (normalized by the total number of bits and similarly probabilistic scores are generated). Moreover, the binary space is partitioned into 32 cluster centers throughout the experiments.

Late Fusion
Until now, we compute a set of visual descriptors and construct two individual databases for local and global representations by depicting the same visual content. To this end, the most similar video scenes are retrieved individually by using the databases and we obtain two ranked lists as illustrated in Fig. 2 for each query. From these lists, our objective is to obtain one final ranked list by fusing these decision scores.  However, the fusion of these decisions is not quite straight-forward. Even if the confidence scores are in similar range [0, 1], there is no common score characteristic that can be directly exploited for all queries (More precisely, there is no overall normalization value). Hence, the confidence scores should be normalized separately for each query before mapping these values to the final ranked list.
From the plots in Fig. 2, the saturation of confidence scores for the ranked lists shares similar characteristic (i.e., 0.75 − 0.65 0.1 and 0.15 − 0.02 0.13). Hence, this information can be exploited to fuse the scores. Therefore, a settling point must be initially determined from each individual list in order to normalize the scores. It can be done in two different ways: 1) the last element of a list can be selected as a settling point and the scores in each list can be normalized by subtracting this value. Second solution is to estimate an adaptive point from each individual list by using the inner relations of the confidence scores. Indeed, the second assumption yields better results, since it does not depend on the number of elements in the ranked list. In similar, as in the assumption of query expansion [14], the scores reflect an error characteristic after some points and no content correlation is expected between the query and reference frames. Hence, the proposed technique is inspired by the assumption of query expansion.
For this purpose, we iteratively calculate first-order score derivatives between all two consecutive confidence scores (i.e., subtracting one point from another) and obtain an adaptively selectable point where the gradient converges to a very small number (e.g. =0.01) after a period of time (after 10 elements). This point is accepted as the settling point and all scores are normalized by subtracting this value.
Later, the normalized local and global scores are merged by regarding their highest scores. To this end, the final ranked list is able to preserve both local structure and semantic similarities for each query in an unified form.

EXPERIMENTS
Our experiments are conducted on Stanford I2V [21]. In particular, this dataset is quite suitable for the tests since it contains large volume of videos collected from diverse news video archives to illustrate the actual capacity of the proposed method. As stated in [21], Stanford I2V dataset is split into two versions such that the lighter version contains a subset of query images and reference videos of the full version. The full and light versions of the dataset consist of 3801 and 1035 hours of videos respectively (Please do not confuse with SI2V-4M or SI2V-600K in [23]). Moreover, the number of query images is decreased by factor 3, from 229 to 78.
In the evaluation step, the performance of our method is measured by the provided script and mean Average Precision (mAP) scores are reported. Computation Load. The main objective of the proposed method is to realize a method that computation load and query processing time are moderate while obtaining state-of-the-art retrieval accuracy for large-scale data. Table 1 illustrates the average time requirements per frame and note that it is close to real-time (assume that 1fps keyframe is processed). This feature allows us to analyze the visual content of the whole For the local visual representation, τ pq defines the error tolerance for the PQ signature matches. For small values, the noisy versions of the true signatures can be estimated correctly. However, this reduces the discriminative power of signatures and introduces lots of outliers. Therefore, we set D bow as 5K and 10K to obtain the trade-offs in terms of retrieval accuracy and query processing time for τ pq . Fig. 3 illustrates the mAP scores for the top 100 ranked scenes based on various τ pq values. From the results, settling τ pq around 0.72 yields the best performance for all configurations. Another important observation is that 5K scores drop down drastically for the full version of the dataset. This result can be explained by the fact that the discriminative power of the representation is not sufficient for smaller D bow values. Moreover, larger cluster size D bow eventually provides an advantage in the querying stage by reducing the operations due to the inverted index structure.
For the global visual representation, D f k and k are two parameters need to be defined by the users. We select 64, 128 and 256 for the number of Gaussian mixture components (D f k ). Since k value determines the redundancy in the approximate binary code search, the accuracy and query processing time are influenced inversely by this value. The accuracy saturates at k = 5 for all parameters as shown in Fig. 2. This ultimately speeds up the search time 6x faster. As expected, increasing the number of mixture components (D f k ) restores the accuracy for both versions. However the total number of comparisons as well as the storage requirement becomes larger as well. Impact of Late Fusion. We calculate mAP scores after fusing the confidence scores of local and global descriptors in various combinations. Ultimately, Table 3 shows that the late fusion boosts the retrieval accuracy around 5% compared to their individual baselines estimated by local and global representations ( Fig. 2 and Fig. 3). Also, the combination of 5K-256 obtains the best mAP accuracy for the light set. However, the score is decreased for the full version due to the failure of PQ. On the other hand, 10K-256 combination yields compatible scores for both full and light versions. Baselines. We compare our performance with the reported results in the literature (Table 3). Initial database performance [21] on the light and full versions are approximately 46% and 43% for mAP@100 (note that they use higher D f k ). More recently, [23] achieves an additional 21% mAP improvement compared to the baseline score by using a shotbased feature aggregation technique. Lastly, the latency of [23] might be better compared to our method due to promoting frame-based assumption to shot-based assumption. But, remark that shot-based features introduce additional workloads to the offline computations. Updating the Ground Truth Annotations. We update the ground truth annotations for both full and light versions of Stanford I2V dataset based on our retrieval results (they will be released on the web).
The annotation pipeline of Stanford I2V dataset [21] partially relies on an automated annotation process. Precisely, the reference videos candidates are initially pruned with a time constraint (based on the time tag of the queries) and a feature-based matching technique is utilized before any human visual intervention. As a result, some of the scenes might be discarded unintentionally from the actual annotation list. Therefore, we manually examine our top retrieval results (up to 20 scenes per query) and find out that some of the retrieved results are non-annotated in the ground truth, even if they have strong semantic analogies and visual copies with the query images. We illustrate some of the scene samples in Fig. 1. Table 4 shows the mAP scores recalculated with the updated ground truth annotations. The results introduce additional 5% improvements compared to Table 3 for the light version of the dataset. This is highly important since the actual performance of the proposed method is even beyond the reported performance in the literature. Moreover, although there is a noticeable performance increase for the full set, the increase is not as high as for the light version. The reason is that the sparsity of global binary representation saturates for the larger set as explained and this validates the importance of joint use of local and global representations for the retrieval task. To make fair comparisons, we also implement and test the baseline method proposed in [21] on the updated ground truth annotations. From the results, it provides only 2% and 1% additional improvement compared to the original annotations.

CONCLUSION
In this work, we introduce a method for large-scale visual retrieval task that exploits local and global descriptors together to represent the visual data. The primary objective of the proposed method is to obtain the moderate computation load and query time for large-scale datasets while outperforming the baselines with a large margin. For this purpose, we present critical improvements to the techniques commonly used for visual representation and feature hashing throughout the paper. In addition, we propose a novel technique to fuse the local feature-based scores and deep global scores in the late fusion step. To show the effectiveness of the method, the experiments are conducted on Stanford I2V dataset and it achieves the state-of-the-art mAP performance in the literature. Moreover, we update the ground truth annotations for Stanford I2V based on the retrieval results of the proposed method. The final results show that the actual performance of our method is much more better after the updated ground truth annotations are used.