Fast Vehicle Identification in Surveillance via Ranked Semantic Sampling Based Embedding

1 Introduction

Vehicle re-identification (Re-ID) aims at identifying whether a pair of vehicle images collected from different conditions (sensors, views or environments) belong to the same object (Identity) or not. In recent years, a few initial works have been made [Zapletal and Herout, 2016; Liu et al., 2016b; Shen et al., 2017; Wang et al., 2017]. However, most existing methods work on the Euclidean space in which computing similarities is computationally expensive, especially because a large-scale gallery is inevitable in the traffic surveillance system [Zheng and Shao, 2016]. Secondly, most methods either consider the task of cross-camera Re-ID [Liu et al., 2016b] (treating all the views equally) or focus solely on one view. For example, in [Liu et al., 2016a], only the front view is mainly investigated. Virtually, the most difficult task of vehicle Re-ID is in the cross-view setting such as from side view to front view.

∗To whom all correspondence should be addressed.

To this end, we focus on learning binary embedding for tackling the challenging task of fast cross-view vehicle ReID (see Fig. 1). With success of deep learning [Szegedy et al., 2015], we also adopt a deep architecture as the function of embedding. Generally, the challenging task can be tackled by embedding images from different views into a common code space. Given a sample, the sample of the same identity would be the one that has the minimum Hamming distance in the learned space to it. However, most existing deep embedding methods are insufficient to address the challenging task of cross-view Re-ID, partially because they are specifically designed for the tasks of recognition and categorization.

To address above problems, we propose a Ranked Semantic Sampling (RSS) guided binary embedding for fast vehicle Re-ID. In this method, according to the semantic hierarchies, tree-structured attributes are first constructed to define the semantic distance. Due to the view-invariant properties of attributes [Frome et al., 2013; Amid and Ukkonen, 2015], the relative semantic distance is also view-invariant. Then, to improve the convergence of SGD optimizer, we adopt the attribute tree to guide the mini-batch sampling, in which the samples can be ranked according to the relative semantic distance. Owning to the ranked samples, more relative relationships can be exploited to reduce the frequencies of accessing samples. Furthermore, a probability inequality is derived to smoothly transfer the discrete optimization into a smooth problem, in which the SGD optimizer can be used without risk. The theoretical analysis guarantees that the learned Hamming distance can directly preserve the relative semantic distance. Consequently, the proposed RSS enables to effectively measure cross-view similarities and efficiently search the matched samples in a cross-view setting.

In summary, our main contributions are in four-fold: 1) We propose a novel deep binary embedding model which enables fast cross-view vehicle Re-ID. 2) The ranked semantic distance can be preserved so that the learned distance is viewinvariant (shown in Fig. 1). Instead employing random sampling as existing methods, to improve the convergence and reduce the frequencies of accessing samples, we introduce a ranked semantic distance guided sampling method. 4) A probability inequality guarantees the transfer from a discrete problem to a smooth objective which SGD can be used.

2 RelatedWork

Vehicle Re-ID: Recently, a few initial works have been made, including a linear regression model [Zapletal and Herout, 2016], a coarse-to-fine framework [Liu et al., 2016b], a twobranch deep convolutional network [Liu et al., 2016a], orientation invariant features [Wang et al., 2017] and visual-spatiotemporal path proposals [Shen et al., 2017]. Moreover, the two recent works [Zheng and Shao, 2016; Zheng et al., 2016] focus on improving the efficiency of person Re-ID.

Attribute Learning: Recent works [Ferrari and Zisserman, 2007; Hwang and Sigal, 2014] explicitly demonstrate that attribute is essentially beneficial to various computer vision tasks. In [Frome et al., 2013; Hwang and Sigal, 2014], the semantic knowledge learned in the text domain is transferred to train a model for visual object recognition. In [Amid and Ukkonen, 2015], a multi-view triplet embedding is proposed to produce a number of low-dimensional maps, each corresponding to one of the attributes. [Kukliasnky and Shamir, 2015] can choose and observe a small subset of the attributes of each training example.

Relative Distance Loss: In earlier years, distance based loss including contrastive loss [Hadsell et al., 2006] and KullbackLeibler divergences over all data points [van der Maaten and Hinton, 2008] could be used to dimensionality reduction and visualization. Beyond pair-wise constraints, recently, various contrastive embedding methods such as triplets [Schroff et al., 2015] and quadruplets [Song et al., 2016] etc. are proposed to capture the high-order relative distance. To explore more contrastive information in mini-batches, (N +1)-tuplet loss [Sohn, 2016] and histogram loss [Ustinova and Lempitsky, 2016] are also proposed recently.

3 ProposedMethod

Intuitively, in order to learn the optimal binary embedding, several questions can naturally be asked: Q1) How to make learning convergence faster? Q2) What types of relationships (similarities) need to be kept in the learned space?

3.1 Cross-View Binary Embedding

Given a sample xvi ∈ Xv , v = 1, · · · , V of the vth view, we assume that vector avi ∈ Av ∈ RNa can be used to describe its corresponding semantic attributes, where V and Na are the number of views and attributes, respectively. Xv and Av are the sample set and attribute set of the vth view, respectively. In our setup, two samples xui and xvj belong to the same object (identity), only if all the corresponding items in the two attribute vectors aui and avj are the same.

The basic requirement for embedding is that samples collected from any view will be projected onto similar binary codes if they have similar attributes. Assume that F v is a hash function from a hypothesis space, then the binary codes of xvi can be obtained by using yv i = sign(F v (xvi )), yv i ∈ {-1, 1}K , where K is the number of binary codes. Obviously, the ideal objective is that, ∀u, v, if aui ≡ avj , then we have yv i ≡ yu j and vice versa 1 .

Once the hash functions F v : v = 1, · · · , V have been learned, given a sample xui of the uth view in the test stage, we can obtain the samples of the same object collected from the vth view by ranking the Hamming distance Dh(yu i , yv j ) between the binary codes of them:

For simplicity, we denote F u (xui ) as F(xui ). Therefore, the basic consideration of this paper is to learn a set of hash functions F v : v = 1, · · · , V , one for each view, to achieve crossview ranking. The architecture (hypothetical space) shown in Fig. 2 (a) has a shared deep architecture and V separate fully connected hierarchy will be considered hash functions.

3.2 Ranked Semantic Sampling

In order to ensure that the learned binary code can represent a large number of relationships between semantic entities, a distance measure Ds(aui , avj ) needs to be established to describe the difference between two attribute vectors aui and avj of any two samples.

Tree-structured attributes

Generally, we can create structures of attributes with the help of WordNet [Fellbaum, 2000], which provides the semantic hierarchy of nouns. When building large-scale dataset such as ImageNet [Deng et al., 2009], we can also learn attributes from datasets. In order to accomplish the task of cross-view Re-ID, we construct an attribute tree as shown in Fig. 2 (b) based on the semantic hierarchy and working scope of attributes. a(1) represents the attribute of a leaf node (lowest level) in the tree. The larger the index l in an attribute a(l) is, the higher the semantic levels of this attribute is. If l < m, then we can call attribute a(m) as the parent attribute of the attribute a(l).

1≡means all corresponding items are the same.

Simply, we can divide the attributes into two groups based on the working scope: shared attributes and non-shared attributes. Shared attributes are global variables, so that samples with the same values of these attributes can have different parent attributes, such as type, door number and color. If two samples share a common shared attribute (e.g. color), they may have the same or different parent attributes. However, if two samples share a common non-shared attribute (e.g. model), then they must have the same parent attribute (e.g. car make). In general, the attributes with higher hierarchies are closer to the concept of super-categories (label) whilst the ones with lower hierarchies are closer to the identity. In a word, two samples of the same identity definitely have the identical attributes. Hierarchies can be used to describe the semantic differences between two samples at a high level of understanding. Given two samples xui and xvj with attribute vectors aui and avj , we can define the semantic distance between them as:

where lij (1 ≤ lij ≤ Na) is the index of lowest hierarchy where the two samples have different lijth attributes but share all the same parent attributes above the lijth hierarchy. N(a(l)) denotes that a(l) has N(a(l)) child nodes (sub-tree). I is an indicative function where I(aui (l) ̸= avj (l)) = 1 if aui (l) and avj (l) are not the same and I(a(l)) = 1 if a(l) is a shared attribute. Obviously, we have Ds(aui , avj ) = 0 when they have the same value at leaf node.

Semantic sampling

Given a training data set X with corresponding semantic attribute set A, a small batch of samples can be selected according to the semantic structure T, so that the complex relationships of samples in this mini-batch can be fully explored to guide the learning of embedding.

The sampling process is as follows: First, we randomly select a pair of samples xu1 and xv2 with the same attributes from two views u and v at random. Obviously, there is au1 = av2 and l12 = 0. In general, sample xu1 is considered as an anchor (reference) and xv2 is considered as a positive sample. Next, we randomly select a sample xv3 from the view v as the first negative sample by adding one step l13 = 1. This example is somewhat similar to an anchor, but with only a different attribute. Then, in order to select more negative samples, we can perform the sampling step to the root of the tree by gradually incrementing l1j . At high hierarchies, when we increase l1j each time, all the shared attributes of the lower hierarchies should be reconsidered. By changing one at a time in ∑l≤l1j I(au1 (l) ̸= avj (l))I(a(l)), we select samples which has exactly the same shared attributes to the anchor sample, up to a sample with a completely different shared attribute. Finally, we obtain a mini-batch XB, where the first sample is an anchor, second one is a positive sample and all others are sorted negative samples.

The characteristics of the sampled mini-batch are distinctive. On the one hand, the adjacent two samples are the hard pairs (To answer the first question Q1: considering hard pairs will make faster convergence). On the other hand, the semantic distance between the anchor and samples from the second to the last one in the mini-batch is monotonically nondecreasing.

Ranked semantic distance loss

Most existing contrastive methods [Schroff et al., 2015; Huang et al., 2016] have some potential limitations in sample sampling: 1) Triplets can only be defined by labels, so finegained categories or attributes are not modelled and therefore can not handle more challenging issues, such as identification and verification. 2) Hard samples can only be selected from mini-batches, so selectivity is limited. 3) In most models, mini-batches are randomly generated. Then, in order to learn more triplets or quads, most models must add minibatch sampling, which can be computationally expensive.

Therefore, in order to improve the efficiency of sampling, this paper proposes a ranked semantic distance loss on the mini-batch to guide the leaning of embedding (To answer the second question Q2: ranked semantic distance shown in Fg. 1). Given a mini-batch XB sampled according to the semantic structure, we define the ranked semantic distance loss as:

where [· ]+ operation indicates the hinge function. Minimizing the above loss can guarantee that, in the learned Hamming space, the relative semantic distances between the anchor, the positive and negative samples are preserved. Due to j > i, we have Ds(au1 , avj )-Ds(au1 , avi ) > 0 according to the semantic structure. Here are a few simple conclusions to be drawn: 1) If i = 2, xvi is a positive sample and Ds(au1 , avi ) = 0. 2) Furthermore, if there are only two negative samples in the minibatch, then the proposed loss is the quadruplet loss [Huang et al., 2016]. 3) If there is only one negative sample in the mini-batch and the semantic distance is fixed by a value as well, then it becomes a triplet loss [Schroff et al., 2015].

The above loss is defined when the anchor is immobilized on the first sample of the mini-batch. In fact, when we use the following samples as anchors, we can also explore the indirect relationships implied in the semantic structure.

Theorem 1. Given three samples avi , avj and avk in the minibatch XB in which samples are sorted and sampled according to the semantic tree, if l1i < l1j < l1k, then the following distance inequality 2 holds:

This theory means that more comparative relationships would be discovered based on the ranked semantic sampling.

2 All proofs will be provided in supplementary materials.

Hence, the additional information can further facilitate training of the model and mining of comparative features without adding sample access. R(XB) considers the explicit relationships in mini-batch sampling. While based on Theory 1, the implied relationships in the mini-batch XB can be explored as well. Therefore, we need to minimize the following loss:

4 Optimization

In order to find the best function to preserve the semantic distance, we need to minimize the quantity R+(XB) +R(XB). Unfortunately, however, the Hamming distance is a discrete variable that is defined based on a sign function that is not differentiable at zero. The most straightforward way is to replace the sign function directly with the auxiliary continuous variable F(x), regardless of the difference between y and F(x). The basic problem of this strategy is that the gap is likely to destroy the properties preserved by F(x). In this paper, we solve this problem by minimizing the difference between the Hamming distance and the Euclidean distance in the learning space F(x).

4.1 Quantization Loss

An auxiliary Euclidean distance between xui and xvj is defined as D2 e (F(xui ), F(xvj )) = ||F(xui ) - F(xvj )||22 in the learned Euclidean space. Obviously, De(F(xui ), F(xvj )) is differentiable. The following theory provides an upper bound of a quantization loss between the Hamming distance 4Dh(yu i , yv j ) and the auxiliary distance D2 e (F(xui ), F(xvj )).

Theorem 2. Given a functional hypotheses space F and a small value ε, for any two samples xui and xvj , the following probability inequality holds:

where C = 2 3 ln2 + 2 ln3 + 2 lnK and L(F(x)) = eTK ln(F(x) ◦ F(x) - eK)2 . The symbol ◦ denotes the Hadamard product of entry-wise multiplication, ln(·)2 is an element-wise operator on each entry of x and eK in which all items are one is a column vector of length K.

Obviously, searching for a function in the hypothesis space by minimizing L(F(xui )) and L(F(xvj )) can reduce the right term of the probability inequality. The smaller the items on the right, the greater the probability that the difference between the two distances D2 e (F (xui ), F (xvj )) and 4Dh(yu i , yv j ) will be within a smaller value ε. This means that minimizing the right item makes D2 e (F(xui ), F(xvj )) closer to 4Dh(yu i , yv j ). In fact, L(F(xui )) is a quantization loss defined on F which projects xui into yu i . When all the items of F(xui ) are either 1 or -1, L(F(xui )) will reach its minimum.

4.2 Overall Objective

Therefore, we can optimize R+(XB) + R(XB) by substituting the auxiliary distance De/4 for the Hamming distance Dh. Hence, we obtain R(XB) = ∑i ∑j>i [De(F(xu1 ), F(xvi ))/4 - De(F(xu1 ), F(xvj ))/4 + Ds(au1 , avj ) - Ds(au1 , avi )]+ and R+(XB) = ∑l1i<l1j<l1k [De(F(xvi ), F(xvj ))/4 - De(F(xvi ), F(xvk ))/4 + Ds(avi , avk ) - Ds(avi , avj )]+. To guarantee the learned Hamming distance, the quantization loss L(F(x)) of all samples in the mini-batch XB should be minimized, simultaneously. Totally, our overall objective can be defined as:

where L(XB) = L(F(xu1 )) + ∑j≥2 L(F(xvj )) and λ is a balance parameter. Importantly, the objective function is differentiable, so an optimal hash function can be searched directly using a stochastic gradient descent (SGD) based on the mini-batch of structural sampling. The derivatives of O w.r.t F are discussed in the supplementary material. Finally, the derivative of objective O w.r.t the parameter θ of function F can be obtained using the chain rule: ∂O ∂θ = ∂O ∂F ∂F ∂θ . θ will be updated during the training stage by using the derivatives on the mini-batches.

5 Experimental Results

To evaluate the proposed RSS for cross-view vehicle Re-ID, we test RSS on the two recently published vehicle datasets: CompCars [Yang et al., 2015] and VeRi [Liu et al., 2016b] shown in Fig. 3. The balance parameter in the RSS model is set to 0.1. As with most Re-ID methods, Cumulative Match Characteristics (CMC) curves are used to assess performance. The Area Under Curve (AUC) is used to rank the performance of the different methods.

The binary deep architecture shown in Fig. 2 consists of three components: a shared deep architecture based on the GoogLeNet [Szegedy et al., 2015] style Inception models, a view-specific fully connected layer, and a binarization layer. The view-specific embedding layer consists of 640 cells, which are fully connected to the previous layer. The 640 units are divided into 5 groups, each of 128 units corresponds to a view. In the learning phase, the first two components need to be updated using objective in 7. Batch normalization is used for each mini-batch. In the testing phase, the binary code is obtained by binarizing the embedded values. With effective Boolean operations, efficient vehicle search can be achieved in the learning Hamming space.

5.1 Cross-ViewVehicle Re-ID

CompCars [Yang et al., 2015] is originally collected for the tasks of fine-grained categorization and verification. This dataset contains a total of 135, 846 images capturing the entire cars from 2, 004 car models. All images have been labelled as one of views including front (V1), rear (V2), side (V3), front-side (V4) and rear-side (V5). Fortunately, three hierarchies of attributes including make, model and year and the shared attributes between different models including maximum speed, displacement, door number, seat number and type are given. To make the dataset more suitable to the task of Re-ID, we carefully label each image using the 12 kinds of colors which are not offered but important for identification. In total, we select six attributes including make, model, type, door number, color and year to construct the tree shown as 2 (b). 2, 000 images of each view are randomly selected for testing and the remaining samples are used for training.

We compare our proposed RSS based binary embedding with the original work in [Yang et al., 2015] based on CNN [LeCun et al., 1989] and 4 state-of-the-art cross-modal hashing methods, including CMFH [Ding et al., 2014], CVH [Kumar and Udupa, 2011], PDH [Rastegari et al., 2013] and CMSSH [Bronstein and Bronstein, 2010].

Our method can learn the embeddings for all views at the same time. However, since all other hashing methods can handle only two view problems, we implement these methods separately for all pairs of views. The CNN features will be considered as input to all other hashing methods. In addition to learning directly from images (ie, RSS), we also investigate the performance of our model with linear embeddings and CNN features [Yang et al., 2015] (Linear-RSS+CNN). From the Fig. 4 (a), we can see that RSS and Linear-RSS + CNN have always outperformed other methods and RSS achieves better results than that of Linear-RSS+CNN. Moreover, we observe that the original model [Yang et al., 2015] can hardly directly address the challenging task of cross-view Re-ID, but performance can be greatly improved by modelling cross-view relationships. This clearly shows that in order to deal with cross-view tasks, it is necessary to model the view-invariant distance.

The detailed results of cross-view Re-ID are shown in Table 1. We arrive at the same conclusion that the proposed RSS performs the best for cross-view Re-ID at 20 different settings. From this table, we can also see that the rear-side view (V5) seems to be easy to recognize, and most of the methods get better results in both settings: 1) rear-side and rear views, 2) front-side and front views than others.

5.2 Knowledge Transfer for Real-World Re-ID

VeRi [Liu et al., 2016b] is collected from real-world urban surveillance scenes and contains a total of 776 vehicles taken by 19 cameras. 37,778 images from 576 vehicles are used for training while the remaining 13,257 images from the 200 vehicles were used for testing. Our experimental setup is the same as the original report in [Liu et al., 2016b], but we use only images without regard to license plate recognition. In this section, we focus on the task of acquiring the knowledge transfer capability of RSS from the large-scale dataset CompCars to solve the vehicle Re-ID on the real-world dataset VeRi. The basic RSS model is first trained on CompCars and then fine-tuned on the training set of VeRi.

In order to make VeRi suitable for cross-view Re-ID, we carefully label the camera view of the VeRi dataset followed the setting of the CompCars dataset. Then, by using the finetuned model, the binary code of the image can be obtained directly. The three methods of GoogLeNet [Szegedy et al., 2015], FACT [Liu et al., 2016b], and AlexNet [Krizhevsky et al., 2012] are used to compare the performance of cross-view Re-ID without considering the same view pairs. In addition to the cross-Re-ID, we also conduct cross-camera Re-ID under the same settings in [Liu et al., 2016b] and select two other models including Bow-SIFT [Lowe, 1999] and BowCN [van de Weijer et al., 2007] from the original VeRi paper [Liu et al., 2016b]. From Fig. 4 (b), we can see that RSS consistently achieves better results than other methods in both cross-view and cross-camera setups. In particular, RSS can outperform FACT, which combines three features, by exploiting the ranked semantic distance. The intrinsic reason is that the ranked semantic distance can help us discover identity features through a series of comparisons. Furthermore, we can observe that the cross-camera Re-ID tasks are much easier than cross-view tasks, regardless of the method used. The potential reason is that most cameras have similar views, and samples from two similar views are easily identified. For example, in the second row of Fig. 3, 10 images of the same car were taken by 10 cameras, but the appearances of the first and fourth images were very similar. In conclusion, experiments show that ranked semantic distances do benefit mining of identity features and can be used to implement actual ReIDs in both cross-view and cross-camera settings.

5.3 Complexity Analysis of Re-ID

Matching efficiency is the most important factor in a realworld system because CCTV cameras can automatically collect millions of images. However, almost all existing vehicle Re-ID algorithms are mainly focused on improving performance by integrating various complex modules. To the best of our knowledge, we are the first efficient algorithm to implement fast vehicle Re-ID and achieve competitive results.

In order to study the complexity of matching, we compared RSS with the above five methods and the other three models: FACT++ [Liu et al., 2016b], OIFE+ST [Wang et al., 2017] and CNN+LSTM [Shen et al., 2017] 3 . This is almost all of the validations on the VeRi dataset, which we can find. With the exception of RSS, GoogLeNet and AlexNet these endto-end algorithms do not have additional modules, the other methods are very complex systems that use multiple CNNs and spatial-temporal regularization. These extra modules are often very computationally expensive. For example, plate detection and recognition using tens of thousands of sliding windows is a daunting task in itself. In order to focus on Re-ID, the position of the tablet in the VeRi dataset is manually annotated. In general, given an unseen probe image, the matching consists of two steps: sample projection and similarity calculation to the samples in the gallery.

Table 2 gives a comparison of the time complexity of projection and matching as well as a comparison of storage requirements. It is worth noting that the computation time for the hand features of the BOW-SIFT and BOW-CN is included, but for simplicity, the calculation time of additional models required by other methods is excluded. From this table, first, we can see that RSS can be much faster than other methods 4 except for two models with similar deep architecture. Especially for those using multiple CNNs, the benefits of RSS are even clearer. Second, more importantly, most of them are even hundreds of times more than RSS, except OIFE+ST, which has a matching time of at least 42 times. In fact, the overall efficiency depends mainly on the number of samples N in the gallery, but it is usually huge in practice. In short, if Re-ID tasks can be done in less than an hour via RSS, it takes nearly two days or more by other means. Finally, the advantages of RSS in storage are also significant, as all other methods require at least 64x capacity to store the features.

3 We refer the complexity analysis to [Shen et al., 2017].

4 Quantization in handicraft features is very computationally expensive when the codebook is huge.

6 Conclusion

In this paper, a new binary deep embedding method is proposed for the challenge task of cross-view vehicle reidentification. Its significant advantage is that through a series of comparisons, the ranked semantic distance is viewinvariant, which helps us to discover identity features that can be preserved in the learned Hamming space. The validation results show that the preserved semantic distance enables to achieve better results and can transfer the deep architecture learned on one dataset to achieve a real-world vehicle Re-ID. In the future, the ranked semantic distance can be applied to many other areas of computer vision, such as object classification and validation. Moreover, theoretically, one can derive more compact upper bound of inequality in Theorem 2.

Acknowledgements

This work was partially supported by the following grants: NSF-IIS 1302675, NSF-IIS 1344152, NSF-DBI 1356628, NSF-IIS 1619308, NSF-IIS 1633753, NIH R01 AG049371.