testing samples. Their performances totally rely on the offline learned models from training data while treat different testing samples equally ignoring the individual characteristics, hence the improvement is neither significant nor stable. The other category is query-specific metric adaptation [17,38,45] which aims to enhance the discriminant of each query individually. The generic offline learned metric is adapted to an instance-specific local metric for each query. Compared with the set-centric ones, the individual discriminant of queries is enhanced while the visual similarity relationships among given testing samples are ignored. Moreover, existing query-specific models [17,38,45] completely ignore the counterpart gallery data during adaptation. Even a discriminative probe-specific metric can be learned, the "hard" gallery samples with large intra-class and small inter-class variances will tremendously degrade its performance since they are still indistinguishable under the learned query-specific metric ( Fig. 1).

In order to tackle the aforementioned issues, we propose a novel online joint multi-metric adaptation algorithm which not only takes individual characteristics of testing samples into consideration but also fully explore the visual similarity relationships among both query and gallery samples. As shown by Fig. 2, at the online P-RID testing stage, the redundant intrinsic visual similarity relationships among unlabeled query (gallery) set are utilized by our proposed frequent sharing-subsets mining model to automatically mine the concise and strong visual sharing associations of samples. Since a sharing-subset contains a group of queries (galleries) sharing strong visual similarity to each other, their local distributions will be jointly adjusted by efficiently learning a Mahalanobis metric for all of them. Once a series of such kind of sharing-subset based Mahalanobis metrics are learned, for each query (gallery), its instance-specific local metric is obtained via a multimetric late fusion of all the sharing-subset based Mahalanobis metrics. Therefore, our proposed online joint Multi-Metric adaptation model based on the frequent sharingsubsets Mining (denoted as M 3 ) is able to refine the ranking performance online. The success of learning from sharing relies on discovering the latent sharing relationships among samples, which cannot be found by treating each instance independently [4]. Learning from sharing is good at handling such condition that only a limited number of learning data are available by taking the sharing relationships as data augmentation. Therefore the sharing strategy is particularly suitable for online P-RID learning in where each testing sample itself is the only positive sample available for learning.

The main contributions of this paper are as follows: (1) To handle the severe shifted training-testing data distribution issue in P-RID, we leap from offline global learning to online instance-specific metric adaptation. We propose a general and flexible learning objective to simultaneously enhance the local discriminant of testing query and gallery data. (2) By mining various frequent sharing-subsets, the intrinsic visual similarity sharing relationships are fully explored. Therefore the online time cost of learning metrics from sharing is much more smaller than learning local metrics independently. (3) To fulfill the time-efficient requirement of online testing, a theoretical sound optimization solution is proposed for efficient learning which is also proven to guarantee the improvement of performance. (4) Our proposed model can be readily applied to any existing offline P-RID baselines for online performance improvement. The efficiency and effectiveness of our method are further verified by the extensive experiments on four challenging P-RID benchmarks (CUHK03, Market1501, DukeMTMC-reID and MSMT17) based on various state-of-the-art P-RID models.

Online Re-Ranking in P-RID: In recent years, increasing efforts have been paid to online P-RID re-ranking. Ye et al. [35] revised the ranking list by considering the nearest neighbors of both the global and local features. An unsupervised re-ranking model proposed by Garcia et al. [9] takes advantage of the content and context information in the ranking list. Zhong et al. [43] proposed a k-reciprocal encoding approach for re-ranking, which relies on a hypothesis that if a gallery image is similar to the probe in the k-reciprocal nearest neighbors, it is more likely to be a true-match. Zhou et al. [45] proposed to learn an instancespecific Mahalanobis metric for each query sample by using extra negative learning samples at online stage. Barman et al. [3] focused on how to make a consensus-based decision for retrieval by aggregating the ranking results from multiple algorithms, only the matching scores are needed. Bai et al. [1] concentrated on re-ranking with the capacity of metric fusion for P-RID by proposing an Unified Ensemble Diffusion (UED) framework. However, the aforementioned online re-ranking methods either simply treat different testing samples equally without considering the instance-specific characteristics or completely ignore the intrinsic visual similarity relationships among testing samples, so that the performance improvement is neither stable nor significant.

CNN-based Feature Extraction in P-RID: CNN-based feature extraction has achieved the state-of-the-art performance in P-RID. A novel Harmonious Attention CNN (HA-CNN) proposed by Li et al. [18] tries to jointly learn attention selection and feature representation in a CNN by maximizing the complementary information of different levels of visual attention (soft attention and hard attention). Wang et al. [30] proposed a novel deeply supervised fully attentional block that can be plugged into any CNNs to solve Therefore, the mined SSSets not only keep the strong and reliable visual similarity sharing information but also significantly alleviate the redundancy. Compared with the original combinatorial problem suffering from exponential computation complexity O(2 n ), the time complexity of our proposed algorithm is O(n 2 ) which is much more efficient when a large scale of testing samples are given.

Considering Q as the given Item set, we firstly prepare a Transaction set T = {t i } nt i=1 from Q where each t i is a subset of Q. The affinity matrix A ∈ R nq×nq of Q is defined as:

, j = i 0, j = i

(1) where σ is the variance parameter of distance matrix from Q so that A i,j represents the soft-max normalized visual similarity between q i and q j . The i-th row of A represents the similarity distribution between q i and the other samples in Q. To keep only the most reliable sharing relationships, a threshold Θ defined as the average affinity of Q is used for outlier filtering: Θ = nq i=1 nq j=1 A i,j /n q • n q . Therefore, a binary index map B is obtained by:

The non-zero B i,j implies the strong similarity sharing relationship between q i and q j . Therefor each non-zero row B j of B can be considered as a Transaction t i .

Once the transaction set T is obtained, we propose to mine the frequent sharing-subsets from T that each sharingsubset is represented by a mined frequent pattern from a classical FP-Close mining algorithm [10]. To do so, a Closed Frequent Itemset Tree (CFI-Tree) is firstly constructed based on T under a minimum support 5 (Fig. 3), then the FP-Close mining algorithm in [10] is performed to the constructed CFI-Tree to obtain all the closed frequent patterns {S i } ns i=1 that each S i represents a sharing-subset.

Once all the frequent SSSets {S i } ns i=1 are obtained, our goal is to jointly learn n s SSSets-based local Mahalanobis metrics for {S i } ns i=1 by optimizing Eqn. 4:

The learned metric M i from Eqn. 4 is shared by all the samples in S i . Suppose we have n s SSSets and O(n) samples in each S i , there are totally O(n 2 s n 2 ) inequality constraints and O(n s n 2 ) equality constraints in Eqn. 4 which are too difficult to deal with, so that we aim to reduce the constraint size in Eqn. 4. We find out that Eqn. 4 has an exactly equivalent form by only keeping the constraints related to one anchor sample s i in S i , that s i can be any sample in S i . Therefore the equivalent form is shown by Eqn. 5:

Revisit Eqn. 4, its equality constraints propose to collapse all s i u ∈ S i together. Therefore keeping only the equality constraints related to the anchor sample s i achieves the same collapsing performance. So as to the inequality constraints in Eqn. 4. Finally, we can reduce the constraint size by only keeping the constraints related to s i as in Eqn. 5. The re-formed objective Eqn. 5 has only O(n 2 s n) and O(n s n) inequality and equality constraints respectively. An important merit of Eqn. 5 is that it can be efficiently optimized:

Now Eqn. 5 has an equivalent form as:

Finally, we prove that Eqn. 7 has the same solution to Eqn. 4 by eliminating its PSD and equality constraints.

The solution to Eqn. 4 is exactly the same as solving the Eqn. 7 by relaxing its equality and PSD constraints, since they are indeed off-the-shelf.

Proof 2 If we get rid of the PSD and equality constraints in Eqn. 7, the new form is:

) Eqn. 8 is exactly in the same form of a multi-kernel SVM problem so that it can be efficiently solved.

Thus the positive semi-definiteness of M i is guaranteed since

For the equality constraints in Eqn. 7, given a member s of S, we have:

) which proves that the solution to Eqn. 8 satisfies the equality constraints as well.

At online testing stage, the gallery set G, the counterpart of query set Q, also plays an important role. As shown by Fig. 1, the re-ranking performance by using only the query-centric metric adaptation may suffer from ambiguous gallery distractors. The similar gallery images from different identities will significantly degrade the discriminant of M p since these gallery distractors are still indistinguishable under M p . Therefore, we aim to handle these indistinguishable gallery samples by performing a gallery-centric local discriminant enhancement method as Eqn. 4. The SSSets of G and the corresponding joint metrics are obtained via Sec. 3.2 and Eqn. 4 respectively.

For one query probe q, it may be contained by multiple SSSets so that there will be multiple learned metrics M i associated to q. The final metric M q for q is obtained via a boosting-form multi-metric late fusion [24,23]:

where γ i = 1 if q ∈ S i . For a gallery sample g, a similar fused metric M g can be obtained likewise. Therefor the refined distance between q and g is defined as Eqn. 11 based on which the re-ranking list of q i is obtained.

As demonstrated by Theorem. 2, the solution of our joint multi-metric adaptation objective can be readily transformed to the equivalent form as [45]. Therefore, the appealing theoretical properties in [45] can be inherited by our learned M i as presented in Theorem. 3. Moreover, our late multi-kernel fusion metric Eqn. 10 will guarantee a further reduction of generalization error bound as in Theorem. 4.

Theorem 3 (The reduction of both asymptotic and practical error bound by the learned M i ): As demonstrated by the Theorem.2 in [45], for an input x, its asymptotic error P a (e|x) by using extra negative data D a is:

where q is a probability scalar that 0 ≤ q ≤ 1 and P(e|x) is the Bayesian error. Moreover, the asymptotic error P a (e|x) can be best approximated by the practical error rate P n (e|x) (n is finite) by finding a local metric M x which turns out to be the one for our Eqn. 4.

Theorem 4 (The reduction of generalization error bound by using M q/g in Eqn. 10): Our fused multi-kernel metric M q = ( ns i=1 γ i M i ) / γ i is a linear combinations of several base kernels M i from the family of finite Gaussian kernels:

which is bounded by B k . Therefore, for a fixed δ ∈ (0, 1), n s < n k is the number of metrics (kernels) involved in our final joint multi-metric learning solution. With probability at least 1 -δ over the choice of a random training set X = {x i } n i=1 of size n we have:

In our work, we have n s ≪ n k , that the selected number of kernels is much fewer than the total kernel number,

The generalization error by using M q is much smaller than using only any M i . The same conclusion can be obtained for M g likewise.

The classification rule of our learned M i can be defined as ζ j qT M i xj -1 ≥ 1 so that the margin is 1. Motivated by [25], the generalization error using M q , which is a linear combination of all M i from the family of finite Gaussian kernel K d G , its generalization error E est (M q ) is bounded by O log n k + B k + 2n s n which is guaranteed by the Theorem.2 in [14]. For the kernel family

) and in our work, d ≈ 10 3 so that n k ≈ 10 6 . The selected kernels for combination is about 20 in average so that n s ≪ n k which means E est (M q ) ≪ E est (M i ).

Datasets. We evaluate our proposed M 3 model on CUHK03 [17], Market1501 [39], DukeMTMC-reID [41] and MSMT17 [33] benchmarks. The statistic details of the above datasets are summarized in Table . 1. For CUHK03 1 , the new splitting protocol proposed by [43] is adopted in our experiment so that 767 identities are used for training as well as the left 700 identities are used for testing. As for the other three benchmarks, Market1501, DukeMTMC-reID and MSMT17, the pre-determined probe and gallery sets are directly utilized with no modification. Baselines. Our proposed M 3 method is evaluated based on several state-of-the-art CNN-based P-RID models: ResNet50 [11], DenseNet121 [13], HA-CNN [18], MLFN [5] and ABDNet [6]. The general CNN models, ResNet50 and DenseNet121, are well trained on each benchmark for feature extraction. HA-CNN, MLFN and ABDNet are the P-RID specific CNNs so that the original works are directly utilized in our experiments. Besides, the 1 In our experiment, the CUHK03 detected dataset is utilized. other state-of-the-art P-RID methods [15,21,37,27,28,5,26,40,46,6] are further compared. Moreover, related online P-RID methods including [45] (OL) and [43] (RR) are compared with our M 3 method.

Evaluation. We follow the same official evaluation protocols in [39,41,17,33], the single-shot evaluation setting is adopted and all the results are shown in the form of Cumulated Matching Characteristic (CMC) at several selected ranks and mean Average Precision (mAP). Various ablation studies of our proposed model are explored in Sec. 5.5.

Evaluation on CUHK03: The comparison results on CUHK03 (767/700 splitting protocol) are presented in Table. 2. Our M 3 model significantly boosts the baseline Rank@1(mAP) performance of ResNet50, DenseNet12, HA-CNN and MLFN to 66.9%(60.7%), 61.6%(54.4%), 69.8%(63.5%) and 73.4%(71.2%) with a 40.0%(29.7%), 50.2%(35.7%), 45.4%(33.4%) and 34.2%(44.7%) relative improvement respectively. Even compared with the stateof-the-art method MGN [31], our results outperform it by 5% at Rank@1. The reason for such a large improvement is that the "hard" gallery distractors which are still indistinguishable under M q is well handled by our M 3 method (Fig. 4), so the ranking of true-match gallery targets is significantly improved.

Evaluation on Market1501: The superiority of our M 3 method is further verified by the experiments on Mar-ket1501. Table . 2 demonstrates that although the state-ofthe-art approach ABDNet [6] has achieved a pretty high performance (≥ 94%) on Market1501, the improvement of our M 3 is still over 3.7%(10%) on Rank@1(mAP) based on ABDNet (visualization results in Fig. 4).

Evaluation on DukeMTMC-reID: DukeMTMC-reID is a recent benchmark proposed for P-RID, but the latest methods have obtained promising performances. As shown in Table . 2, the recently published OSNet [46] has raised the state-of-the-art to 87.0%(70.2%). Our ABDNet+M 3 improves the Rank@1(mAP) result to 87.5%(73.3%), which beats OSNet by a large margin on mAP.

Evaluation on MSMT17: MSMT17 is the latest and largest benchmark so far which is pretty challenging due to the extreme large-scale identities and distractors. We eval-CUHK03(767/700)

DukeMTMC-reID Method R@1 mAP Method R@1 mAP Method R@1 mAP ResNet50 [11] 47.9

Baseline Baseline+M 3 Method R@1 mAP R@1 mAP ResNet50 [11] 63. uate the performance of selected baselines on the MSMT17 dataset with(w/) and without(w/o) our M 3 model in Table . 3. For all the baselines, our M 3 model significantly improves their Rank@1(mAP) performance. The performance of ABDNet is boosted from 82.3%(60.8%) to a state-of-theart level of 85.7%(64.2%). Table . 3 verifies the scalability of our proposed M 3 model, even for the extremely largescale query/gallery sets, our method is still able to consistently improve the baseline performance.

Duke HA-CNN [18] 48.0(47.6) 90.6(75.3) 80.7(64.4) HA-CNN+RR [43] 54.8(55.7) 91.4(79.0) 82.5(69.9) HA-CNN+OL [45]

Two state-of-the-art online P-RID re-ranking methods, OL [45] and RR [43], are compared with our M 3 since all the three methods can be readily utilized at online testing stage for further performance improvement. The comparison results in Table. 4 show that the query-specific method OL [45] works better on improving Rank@1 per-Method Market1501 → DukeMTMC DukeMTMC → Market1501 R@1 R@5 R@10 R@20 mAP R@1 R@5 R@10 R@20 mAP MLFN [5] 45 formance but has little improvement on mAP due to the lack of gallery-specific local discriminant enhancement. In contrast, since RR [43] considers the k-reciprocal nearest neighbors of both query and gallery data, it achieves a large improvement on mAP but with limited improvement on Rank@1 owing to the lack of instance-specific local adaptation. Our M 3 outperforms the other two approaches significantly at both Rank@1 and mAP due to the fully utilization of both the group-level visual similarity sharing information and instance-specific local discriminant enhancement.

We explore the generalization ability of our proposed M 3 . We claim the improvement by M 3 is from the testing sample itself which is independent of how the baseline models are trained. Therefore we conduct a cross-set generalization ability validation experiment as shown in Table . 5. Following the setting in [44], the baseline model trained by Market1501 with our M 3 is evaluated on DukeMTMC-reID and vice versa. The results show our M 3 model is able to consistently and significantly improve the baseline performance regardless of whether the baseline is trained by the same-source data or not.

The Influence of Model Components: The final retrieval performance of Eqn. 11 relies on a bi-directional retrieval matching, so the influence of each component is shown in Table . 6. As can be seen, by only keeping the query-specific metric adaptation M q or the gallery-centric one M g , we still can achieve a significant improvement. While by performing a full-model bi-directional matching, the performance is further boosted by a large margin which demonstrates the necessity of bi-directional local discriminant enhancement. More visualizations are shown in Fig. 4.

The Influence of λ in Eqn. 11: The weighting parameter λ in Eqn. 11 aims to balance the importance of M q and M g . The full CMC curves w.r.t λ of HA-CNN on CUHK03, Market1501 and DukeMTMC-reID are plotted in Fig. 5 respectively. As can be seen, setting λ = 1 gives the best performance since we perform a max-normalization to both M q and M g , over-weighting either side is prone to suppress the other side's impact.

Unlike previous online P-RID works, in this paper, we propose a novel online joint multi-metric adaptation algorithm which not only takes individual characteristics of testing samples into consideration but also fully utilizes the visual similarity relationships among both query and gallery samples. Our M 3 method can be readily applied to any existing P-RID baselines with the guarantee of performance improvement, and a theoretical sound optimization solution to M 3 keeps a low online computational burden. Compared with the other state-of-the-art online P-RID refinement approaches, our method achieves significant improvement on Rank@1(mAP) performance. Moreover, by implementing our method to the state-of-the-art baselines, their performance is further boosted by a large margin on four challenging large-scale P-RID benchmarks.