Scalable Person Re-identification on Supervised Smoothed Manifold

Introduction

Person re-identification (ReID) is an active task driven by the applications of visual surveillance, which aims to identify person images from the gallery that share the same identity as the given probe. Due to the large intra-class variations in viewpoint, pose, illumination, blur and occlusion, person re-identification is still a rather challenging task, though extensively studied in recent years.

Current research interests can be coarsely divided into two mainstreams: 1) those focus on designing robust visual descriptors to accurately model the appearance of person; 2) those seek for a discriminative metric , under which instances of the same identity should be closer while instances of different identities are far away.

Unlike those methods performed in the metric space, we investigate person re-identification task from another perspective, i.e., taking into account the manifold structure . Since existing methods only analyze the pairwise distances between instances, the underlying data manifold, which those images reside on, is more or less neglected. It results in that the learned relationships (similarities or dissimilarities) between instances are not smooth with respect to the local geometry of the manifold.

To overcome this issue, potential solutions can be semi-supervised or unsupervised algorithms about manifold learning. However, directly applying such algorithms to person re-identification might be problematic for two reasons. First, semi-supervised algorithms (e.g., label propagation ) can only predict the labels of unlabeled data, but fail to depict the relationship between the probe and gallery instances. Moreover, they require category labels, while supervision in ReID is given as pairwise (equivalence) constraints . Meanwhile, unsupervised algorithms (e.g., manifold ranking , graph transduction ) totally ignore the beneficial influence from the labeled training data. Second, since most manifold learning algorithms operate on graph models, their algorithmic complexity is usually high. Therefore, the heavy computational cost hinders their promotions in this field, especially in recent years researchers begin to attach more importance to the scalability issue . In summary, due to the above factors, those conventional manifold learning algorithms are inadequate to derive a more faithful similarity for person re-identification.

In this paper, we tackle person re-identification task on the data manifold by proposing a novel affinity learning algorithm called Supervised Smoothed Manifold (SSM). Compared with existing algorithms, the primary contribution of SSM is that the similarity value between two instances is estimated in the context of other pairs of instances, thus the learned similarity well reflects the geometry structure of the underlying manifold.

Moreover, SSM is customized specifically for person re-identification, which further possesses three merits (as illustrated in Fig. 1) as follows: i) supervision: instead of considering each instance individually, we propose to learn the similarity with instance pairs. By doing so, SSM can take advantage of the supervision in pairwise constraints, which is easily accessible in this task; ii) efficiency: to overcome the limitation of high time complexity of SSM, two improvements are proposed to accelerate its on-line person matching. Consequently, the affinity learning is performed only with database instances off-line, and SSM can be applied to the scenario on large scale person re-identification; and iii) generalization: different from most existing algorithms performed in metric space, SSM focuses on affinity learning between instances. Hence, SSM can be deemed as a postprocessing procedure (or a generic tool) to further boost the identification accuracies of those algorithms.

The rest of the paper is organized as follows. In Sec. 2, we present the differences between SSM and relevant works. The basic affinity learning framework of SSM is introduced in Sec. 3, and significantly accelerated in Sec. 4. Experiments are presented in Sec. 5. Conclusions and future works are given in Sec. 6.

Related Work

The manifold structure has been observed by several works. Motivated by the fact that pedestrian data are distributed on a highly curved manifold, a sampling strategy for training neural network called Moderate Positive Mining (MPM) is proposed in . However, considering the data distribution is hard to define, MPM does aim at estimating the geodesic distances along the manifold. From this point of view, SSM explicitly learns the geodesic distances between instances, which can be directly used for re-identification.

Manifold ranking is introduced by to person re-identification. Through a random walk on the affinity graph, it propagates the probe label to the gallery iteratively assuming that the probe is the only labeled data. Despite the ignorance of labeled training data as analyzed above, manifold ranking encounters severe obstacles when handling larger databases, since the graph-based iteration has to be run each time a new probe is observed. In this aspect, SSM also learns the similarities via iterative propagation. Nevertheless, it enables a highly-efficient on-line matching.

Post-ranking techniques have not drawn much attention in this field. Most of them require human feedback in-the-loop , such as Post-rank OPtimisation (POP) , Human Verification Incremental Learning (HVIL) . Meanwhile, several works operate in an unsupervised manner. For example, Discriminant Context Information Analysis (DCIA) focuses on the visual ambiguities shared between the first ranks, where the true match is supposed to be located. In comparison, SSM does not need human interaction or hold the “rank-1” assumption. Instead, its essence is to learn a smooth similarity measure, supervised by the special kind of labels in pairwise constraints.

At the first glance, affinity learning in our work appears the same as similarity learning (e.g., PolyMap ). Unlike similarity learning on polynomial feature map which connects to Mahalanobis distance metric and bilinear similarity, affinity learning in SSM does not rely on the definition of metric (non-metric can be also used). Therefore, they are inherently different. Finally, it is acknowledged that those metric learning methods (e.g., KISSME , XQDA ) are also relevant, but take effects prior to SSM in a person re-identification system as Fig. 1 shows.

Proposed Method

Let $(v_{k},v_{i})$ and $(v_{l},v_{j})$ be two tuples, the propagation step in the $t$-th iteration is defined as

where $\mathcal{P}(ki\rightarrow lj)$ is the transition probability from tuple $(v_{k},v_{i})$ to tuple $(v_{l},v_{j})$, and $0<\alpha<1$. Eq. (2) reveals that at each iteration, the tuple $(v_{k},v_{i})$ absorbs a fraction of label information from the rest tuples with probability $\alpha$, then retains its initial label $L_{ki}$ with probability $1-\alpha$. Assuming the independence within tuples, we hold the product rule to calculate $\mathcal{P}(ki\rightarrow lj)$, as

Afterwards, Eq. (2) can be rewritten in matrix form

2 Convergence Proof

By running the iteration for $t$ times, Eq. (4) can be expanded as

$\mathcal{P}$ is also a row stochastic matrix, since

Therefore, according to Perron-Frobenius Theorem, we can obtain that spectral radius of $\mathcal{P}$ is bounded by $1$, the maximum value of its row sums. Considering that $0<\alpha<1$, we have

where $I$ is an identity matrix in appropriate size. Consequently, Eq. (6) converges to

Then $Q$ can be obtained by reshaping $\vec{Q}$ to matrix form as $Q=vec^{-1}(\vec{Q})$.

3 Basic Pipeline

Intuitively, person re-identification using the above affinity learning algorithm can be accomplished in three steps. First, each time a probe instance $p$ is observed, the affinity graph $\mathcal{G}$ is constructed. Second, a new similarity $Q$ is learned by either running Eq. (4) until convergence or directly using the closed-form solution in Eq. (9). At last, since $Q$ can be divided into

We draw readers’ attention that when the probe $p$ is used for testing, the other probe instances are invisible to users. Therefore, one cannot simultaneously include all the probe instances to constitute $\mathcal{G}$ for a global probe search.

However, this pipeline is computationally too demanding in practice. First, affinity learning itself is computationally expensive. It requires time complexity $O(TN^{4})$ and space complexity $O(N^{4})$ to run the iteration in Eq. (4), where $T$ is the iteration number. Alternatively, using the closed-form solution in Eq. (9) requires time complexity $O(N^{6})$ and space complexity $O(N^{4})$, since we need to invert and store a huge matrix of size $N^{2}\times N^{2}$.

Second, adapting new probe instances is computationally expensive. As our method is algorithmically graph-based, we need to discard the old probe and do the affinity learning at each time a new probe is observed. Assume we have $N_{p}$ probe instances in total, we at least need time complexity $O(TN_{p}N^{4})$ to finish the whole probe search. Note that constructing the affinity graph is computationally cheap due to the fact that the similarities between database instances can be pre-computed off-line for once and reused consistently.

Re-identification on-the-fly

In this section, we propose two modifications to decrease the high complexity of the basic pipeline in Sec. 3, such that person re-identification can be done on-the-fly.

Our first improvement focuses on affinity learning itself. We observe the following useful identity

As a result, the time and space complexity of affinity learning are reduced to $O(TN^{3})$ and $O(N^{2})$, respectively.

2 Probe Embedding

Our second improvement concentrates on improving the efficiency in adapting new probe instances. First, we prove that the closed-form solution in Eq. (9) can be derived from

Using the two identical coordinate transformations, Eq. (13) can be vectorized, where

where $\Phi(\vec{Q})$ measures the smoothness of $\vec{Q}$ with respect to the local manifold structure, and $\Omega(\vec{Q})$ measures the fitness of $\vec{Q}$ to the given label $\vec{L}$.

The derivative of $\Phi(\vec{Q})$ with respect to $\vec{Q}$ is

According to , Eq. (16) can be approximated by $2(I-\mathcal{P})\vec{Q}$. So, one can easily induce the derivative of Eq. (13) with respect to $\vec{Q}$

By setting Eq. (17) to zero and applying $vec^{-1}$ operator, we can get the closed-form solution of Eq. (13)

which is equivalent to Eq. (9). The proof is complete.

Compared with the large database (testing gallery and labeled data), there is only one probe $p$ at each testing time. Therefore, we hold two assumptions that 1) the database itself constitutes an underlying manifold; 2) when $p$ is embedded into the manifold smoothly, it will not alter its geometry structure. With these prerequisites, we can first perform affinity learning off-line with only database instances, then do the probe embedding on-line.

Of course, the embedding of the probe should also follow the smoothness criterion $\Phi(Q)$. After the pairwise similarities between database instances are smoothed, the partial derivative of $\Phi(Q)$ with respect to $Q_{pi}$ is

Setting it to zero, the similarity between the probe $p$ and a certain database instance $v_{i}$ can be calculated

By varying $v_{i}\in X$, Eq. (20) can be rewritten in matrix form

3 Complexity Analysis

The final pipeline of the proposed SSM is rather simple, summarized in Alg. 1.

As can be seen, affinity learning is done only with database instances. The computational cost still seems a bit heavy, since there are $(N_{g}+N_{l})$ vertices in the graph. However, those operations can be done off-line, and reused with different probe instances. The learned similarities can all be maintained dynamically as long as new database instances are added or distance matrices are changed.

In Table 1, we present the on-line complexity comparison between the standard solution in Sec. 3 and the accelerated solution in Sec. 4. Eq. (21) reveals that on-line indexing for $N_{p}$ probe instances involves the multiplication of three matrices. Whereas the multiplication of the right two can be also computed off-line, the on-line time complexity is only $O\left(N_{p}(N_{g}+N_{l})N_{g}\right)$. Furthermore, the space complexity is dominated by the storage of the learned similarity, requiring $O\left((N_{g}+N_{l})^{2}\right)$.

Experiments

The proposed Supervised Smoothed Manifold (SSM) is evaluated on five popular benchmarks, including GRID , VIPeR , PRID450S , CUHK03 and Market-1501 . In the implementations of SSM, we do not carefully tune parameters, but fix $\alpha=0.1$ and the number of iterations $T=30$ throughout our experiments. The affinity graph is constructed by applying self-tuning Gaussian kernel to pairwise distances following .

QMUL underGround Re-IDentification (GRID) is a challenging dataset, which has gradually become popular. The variations in the pose, colors and illuminations of pedestrians, as well as the poor image quality, make it very difficult to yield high matching accuracies.

GRID dataset consists of $250$ identities, with each identity having two images seen from different camera views. Besides, $775$ additional images that do not belong to the $250$ identities are used to enlarge the gallery. Sample images can be found in Fig. 1. A fixed training/testing split with $10$ trials is provided. For each trial, $125$ image pairs are used for training. The remaining $125$ image pairs and the $775$ background images are used for testing. To evaluate the performances, we employ Cumulated Matching Characteristics (CMC) curves and the cumulated matching accuracy at selected ranks.

To obtain the image representations, we utilize two representative descriptors, i.e., Local Maximal Occurrence (LOMO) and Gaussian Of Gaussian (GOG) . In addition, ELF6 feature , provided along with the dataset, is also tested to ensure the fair comparison.

Comparison with Baselines. In Table 2, we present the performances before and after SSM is used. Besides the three individual visual features, two types of fused features are also used. Fusion means the concatenation of LOMO and GOG, while Fusion⋆ means the concatenation of all the three features, both with equal weights. The pairwise distances between instances are computed in metric space. In our experiments, besides the natural choice of Euclidean metric, we also evaluate Cross-view Quadratic Discriminant Analysis (XQDA) which is taken as a representative of metric learning techniques.

As can be drawn, SSM leads to considerable performance gains against the baselines. For example, with ELF6 in Euclidean metric, the improvement of identification rate brought by SSM is $2.32$ at rank-$1$, $3.84$ at rank-$10$ and $6.08$ at rank-$10$. Meanwhile, by integrating XQDA, SSM can still boost the performances further. For example, the rank-1 accuracy of LOMO with XQDA is originally $16.56$, then increased to $18.96$ after the proposed SSM is used. Those experimental results suggest that most existing visual features or metric learning algorithms in person re-identification are compatible with SSM. In other words, after visual features are given, person re-identification systems can be improved with two steps, i.e., applying metric learning first, and applying SSM next.

As a related work to ours, manifold ranking reports an identification rate of $30.96$ at rank-20 using ELF6 and Euclidean metric, which is significantly lower than $34.08$ achieved by SSM. It clearly demonstrates that it is beneficial to exploit the supervision information in affinity learning step. To avoid the performance uncertainty (though rather tiny) led by different implementation details, we compare SSM with manifold ranking using exactly the same affinity graph. The results are given in Fig. 2. As we can see, the rank-1 accuracy of both manifold ranking and SSM is $6.96$. However, SSM outperforms manifold ranking by a large margin at higher ranks. The difference of accuracy is nearly $10$ at rank-100.

One of the most important properties of SSM is its high time efficiency in on-line pedestrian matching. Here, we omit the overhead in constructing the affinity graph, which can be done off-line. Under the same computing platform, manifold ranking takes $14.40$ seconds in total to fulfill searching $125$ probe instances, while SSM only needs $9.52ms$. One can easily find that SSM is $3$ orders of magnitude faster than manifold ranking. The reason behind is that the iteration of manifold ranking is conducted each time a new probe is observed. In comparison, SSM proposes to do affinity learning only off-line, and embed the probe smoothly into the manifold. As a result, although SSM has to do affinity learning on a much larger graph (to leverage the supervision from training data), the on-line cost can be controlled so that SSM has the potential ability of handling large-scale person re-identification. We will further discuss this aspect below.

From Table 2, failure cases of SSM can be also observed. As it suggests, the rank-20 accuracy of ELF6 under XQDA metric is originally $52.56$, then is decreased slightly by SSM to $51.76$. The reason behind such abnormal phenomena is that the principle of SSM is to obtain a global similarity measure between each two instances, which varies smoothly with respect to the local geometry of the underlying manifold. The learned similarity cannot guarantee that the identification rate at specifical ranks will be improved. But in general cases, the overall performances will be refined.

Comparison with State-of-the-art. In Table 3, we give a thorough comparison with other state-of-the-art methods. The performances of the proposed SSM are reported by using Fusion feature (the concatenation of LOMO and GOG) under XQDA metric, which is a default configuration used in our later experiments.

Previous state-of-the-art performances are achieved by Spatially Constrained Similarity function on Polynomial feature map (SCSP) and GOG . Chen et al. impose spatially constraints to the similarity learning on polynomial feature map , and report rank-1 accuracy $24.24$ by fusing $6$ visual cues. GOG is a powerful descriptor proposed recently, which captures the mean and the covariance information of pixel features. With XQDA metric, it reports the best performances on GRID dataset, i.e., rank-1 accuracy $24.80$. Benefiting from Fusion feature and XQDA metric, SSM easily sets a new state-of-the-art performance, outperforming the previous by $2.40$ in rank-1 accuracy.

We emphasize that SSM is not restricted by the used descriptor and metric. Table 2 presents that SSM can achieve higher performances with Fusion⋆ feature.

2 VIPeR, PRID450S and CUHK03

VIPeR is a widely-accepted benchmark for person re-identification containing $632$ identities, and PRID450S consists of $450$ identities, both captured by two disjoint cameras. The widely adopted experimental protocol on two datasets is that a random selection of half persons is used for training and the rest for testing. The procedure is repeated for $10$ times, then the average performances are reported.

CUHK03 is among the largest public available benchmarks nowadays. It includes $13,164$ images of $1,360$ persons, with each person having $4.8$ images on average. Besides manually cropped images, auto detected images are also provided. Following the conventional experimental setup , $1,160$ persons are used for training and $100$ persons are used for testing. The experiments are conducted in single-shot setting with $20$ random splits.

In Table 4, we present the performances of SSM and the baselines, where distances are calculated under XQDA metric. Consistent to previous experiments, SSM can easily boost the performances of baselines by around $2.5$ percent on average. In particular, the performance improvements are more dramatic on CUHK03. For example, the rank-1 accuracy of Fusion is increased by $4.76$ on CUHK03 labeled dataset, and by $4.65$ on CUHK03 detected dataset. The preference of SSM on larger datasets stems from the fact that the manifold structure can be better sampled given more data points.

Comparison on VIPeR. Since enormous algorithms have reported results on VIPeR dataset, it is less realistic to exhibit all of them. Hence, we only include those published in recent $3$ years or have close relationships with our work.

The comparison is given in Table 5. As can be seen, SSM yields the best rank-10 accuracy $91.49$, which is the same as SCSP . Meanwhile, SSM also achieves the second best performances at rank-1 and rank-20. To our best knowledge now, the best rank-1 accuracy is achieved by Discriminant Context Information Analysis (DCIA) . The superiority of DCIA at rank-1 lies in that it tries to remove the visual ambiguities between the probe and its true match, which is supposed to be located at the first rank. By contrast, SSM does not hold such assumptions, which seem to be a bit strict in realistic settings. Thus, one can also observe that SSM outperforms DCIA by $3.99$ at rank-10. Considering their inherent difference of principles, it can be anticipated that SSM and DCIA can benefit from each other, and a proper ensemble of them can lead to better performances.

Comparison on PRID450S. On PRID450S dataset, SSM provides the state-of-the-art performances on all the three evaluation metrics, i.e., $72.98$ at rank-1, $96.76$ at rank-10, and $99.11$ at rank-20.

Comparison on CUHK03. The comparison on CUHK03 dataset is given in Table 7. As it shows, the rank-1 identification rate of SSM is $72.7$ with automatically detected bounding boxes, which is the first work reporting rank-1 accuracy larger than $70$.

In , Zhang et al. overcome the small sample size (SSS) problem by matching people in a discriminative null space of the training data, which report the second best performance $94.8$ at rank-10 with automatically detected bounding boxes. Nevertheless, the performance gap with SSM becomes larger at lower ranks. For instance, SSM makes a significant improvement of $18.0$ in rank-1 accuracy over Null with detected bounding boxes.

GOG remains to be one of the most robust descriptors on this dataset. Under XQDA metric, it achieves the second best performances at most ranks. As analyzed above, SSM can be deemed as a generic tool for those visual descriptors and metric learning techniques. Thus, SSM can further enhance their discriminative power.

3 Market-1501

Market-1501 is the largest benchmark in person re-identification up to present, which is comprised of $1501$ identities. $750$ identities ($12,936$ images) are used for training and $751$ identities ($19,732$ images) are used for testing. $3,368$ images are taken as the probe. Both CMC scores and mean average precision (mAP) are used for evaluation.

Thanks to plenty of training images provided, training deep neural networks becomes feasible on this dataset and preferred by most previous works . Following this trend, we introduce Residual Network (ResNet) , for the first time, to person re-identification. More specifically, we fine-tune a 50-layer ResNet with classification loss on training images, and extract activations of its last fully connected layer. The $L_{2}$ normalized activations are taken as visual features and Euclidean metric is utilized to measure the distances between images. The baseline performances are mAP $61.12$ with single query (SQ) and $70.82$ with multiple query (MQ), respectively.

In Table 8, we present the experimental comparisons. As can be seen, SSM improves the baseline by mAP $7.68$ for SQ and $5.30$ for MQ. Moreover, SSM outperforms the previous state-of-the-art by a very large margin, with the improvement of mAP $29.25$ for SQ and $27.73$ for MQ.

4 Time Analysis

As an additional improvement over metric learning, SSM introduces extra time cost without doubt as analyzed in Sec. 4.3. In Table 9, we present the extra execution time of SSM over XQDA metric.

As SSM manages transferring the graph-based affinity learning to off-line, the off-line cost is increased especially on larger datasets (e.g., CUHK03 and Market-1501). In on-line stage, the extra indexing time brought by SSM only occupies a small percentage on all the datasets except CUHK03. On CUHK03 dataset, indexing using XQDA metric only requires $0.09s$, since CUHK03 has a small gallery. As SSM takes into account the larger training data provided by CUHK03, the extra indexing cost is $0.516s$. Nevertheless, the overall indexing time is still within $1$ second.

Conclusion

In this paper, we do not design robust features or metrics that are superior to others in person re-identification. Instead, we contribute a generic tool called Supervised Smoothed Manifold (SSM), upon which most existing algorithms can easily boost their performances further. SSM is very easy to implement. It can also handle the special kind of labeled data and has potential capacity in large scale ReID. Comprehensive experiments on five benchmarks demonstrate that SSM not only achieves the best performances, but more importantly, incurs acceptable extra on-line cost.

In the furture, we will investigate how to effectively fuse multiple features and apply the proposed SSM to other datasets .

References