Cross-View Projective Dictionary Learning for Person Re-Identification

1 Introduction

Person re-identification is the problem of matching pedestrian images observed from multiple non-overlapping cameras. It saves a lot of human efforts in many safety-critical applications such as video surveillance. In recent years, many algorithms have been proposed to tackle this problem [Zheng et al., 2012; Zhao et al., 2013a; Wang et al., 2014; Li et al., 2014b]. These methods can be mainly divided into two categories, including the distance learning/metric learning methods [Weinberger et al., 2005; Zheng et al., 2011; Davis et al., 2007; Mignon and Jurie, 2012; Pedagadi et al., 2013] and feature learning methods [Gray and Tao, 2008; Farenzena et al., 2010; Ma et al., 2012b; Zhao et al., 2013a]. The distance learning methods usually learn distance metrics that are expected to be robust to sample variations. The feature learning methods aim to extract distinctive features

Yun Fu

Dept. of ECE and College of CIS Northeastern University Boston, MA, USA yunfu@ece.neu.edu

from pedestrian images, such as salient features [Zhao et al., 2013a]. However, the representation power of learned features or metrics might be limited, due to the various viewing conditions of pedestrian images in real scenarios.

In this paper, we learn discriminative and robust representations via dictionary learning to improve the representation power of features. Our motivations are two-folds. First, the success of dictionary learning based domain adaptation technique inspires us to learn a pair of cross-view dictionaries for person re-identification [Ni et al., 2013]. The adaptively learned dictionaries can generate robust representations for pedestrian images. Secondly, existing works either focus on extracting features form image patches or directly learning global features, but the complementary information resided in patch-level and image-level are usually ignored.

Based on the motivations above, we propose a cross-view projective dictionary learning (CPDL) approach, which is a general framework for the multi-view dictionary learning problem. We then design two objectives by utilizing the CPDL framework, which learn low-dimensional representations for each person in the patch-level and the image-level, respectively. Different from traditional dictionary learning methods, CPDL adopts the projective learning strategy to avoid solving the l1 optimization problem in training phase. The proposed objectives can capture the intrinsic relationships of different representation coefficients in various settings. We also employ a strategy to fuse the similarity scores estimated in two levels.

By far, there are few methods proposed to learn effective representations for the pedestrian images under different views [Liu et al., 2014]. The basic idea of Liu's method is to learn expressive bases to represent the image patches. It assumes that each pair of patches in two images shares the same representation coefficients. However, it is not the case in reality, due to the common misalignment problem in person re-identification.

The major contributions of this paper are summarized below.

• We propose a general framework, CPDL, for multiview dictionary learning, and apply it to person reidentification. CPDL adopts the projective dictionary learning strategy, which is more efficient than the traditional dictionary learning methods. We devise efficient optimization algorithms to solve the model.

• We design two objectives using CPDL, which explicitly model the cross-view interactions in different representation levels, including the patch-level and image-level. To the best of our knowledge, this paper is the first attempt to learn representations at different levels for person re-identification.
• We evaluate the performance of CPDL and related methods on the public VIPeR and CUHK Campus datasets. Extensive experimental results show that our approach outperforms the state-of-the-art methods.

2 RelatedWork

There are two types of works that are very related to our approach: (1) person re-identification, (2) dictionary learning.

Person Re-identification. In recent years, many algorithms have been proposed for person re-identification. Some traditional methods focus on learning effective metrics to measure the similarity between two images captured from different camera views [Hirzer et al., 2012; Zheng et al., 2011]. Other research works focus on learning expressive features, which usually obtain better performance that the metric learning methods. They suggest that learning effective representations is the key in person re-identification. Some advanced features include attributes [Layne et al., 2012], salience features [Zhao et al., 2013a; 2013b], mid-level features [Zhao et al., 2014], and salient color features [Yang et al., 2014]. Although the existing feature learning methods achieve good performance, the cross-view relationships of pedestrian images haven't been extensively studied. Our CPDL approach explicitly models such relationships in different representation levels, and draws strength from them to enhance the re-identification performance.

Dictionary Learning. As a powerful technique for learning expressive bases in sample space, dictionary learning has attracted lots of attention during the past decades [Li et al., 2014a]. Some popular dictionary learning methods include K-SVD [Aharon et al., 2006], discriminative KSVD [Zhang and Li, 2010], and projective dictionary pair learning [Gu et al., 2014]. Most recently, Liu et al. presented a semi-supervised coupled dictionary learning (SSCDL) method [Liu et al., 2014], and applied it to person re-identification. The major differences between our approach and SSCDL are three-folds. First, SSCDL is a semisupervised method, while our approach is supervised. Secondly, SSCDL simply assumes that a pair of patches in two views should have similar codings, which is unreasonable in real scenario due to the misalignment problem. Our approach models the cross-view interactions in image-level and patchlevel, respectively. Thirdly, SSCDL requires solving the l1 optimization problem that is time consuming. Our approach adopts a more efficient learning strategy, i.e., projective dictionary learning.

3 AGeneral Framework for Cross-view Projective Dictionary Learning (CPDL)

Traditional dictionary learning methods usually assume that the samples A ∈ Rd×n can be reconstructed by sparse coefficients Z ∈ Rm×n and a dictionary D ∈ Rd×m, i.e., A =

DZ, in which Z is constrained by l1 norm. However, solving sparse coefficients Z often suffers heavy computational costs. Inspired by the projective dictionary learning [Gu et al., 2014], we address this problem by reformulating the DL process as a linear encoding and reconstruction process. Let P ∈ Rm×d (m ≪ d) denote a low-dimensional projection matrix, we can reconstruct the sample set by A = DPA. Note that PA denotes the linear encodings of sample set A.

We build a cross-view projective dictionary learning (CPDL) framework in the two-view settings. Let A1 ∈ Rd1×n and A2 ∈ Rd2×n denote two training sets that are collected under two different views, respectively. The reconstructions in two views are formulated as

where D1 (and D2), P1 (and P2) are dictionaries and projections in two views, respectively.

The objective function of CPDL framework is

where f(D1,D2, P1, P2) is a regularization function, λ1 is a trade-off parameter, and d1(:,i) and d2(:,i) are the i-th columns in D1 and D2, respectively.

The first two terms in objective (2) indicate reconstruction errors in two views, respectively. The last term f(D1,D2, P1, P2) is a regularization function that bridges two views. It can be customized for specific problems, such as multi-view image classification or (cross-view) person reidentification.

Finally, the obtained optimal dictionary pair {D1, D2} can be used to generate new representations for test samples. Note that, for simplicity, we only formulate two views in this paper, but our model can be extended to the multiple-view case by extending (2).

4 CPDL for Person Re-identification

In this section, we first introduce how to extract low-level dense features from the pedestrian images. Then we formulate person re-identification problem using CPDL. Figure 1 shows the training framework of CPDL.

4.1 Feature Extraction

The pedestrian images in different camera views are not usually aligned well. Extracting dense features from local patches is a widely used strategy to obtain effective representations, as suggested in [Zhao et al., 2014]. Specifically, the local patches are extracted on a dense grid. The size of each patch is 10×10, and the grid step is 5. Then, for each patch, we extract 32-dimensional color histogram features and 128dimensional dense SIFT features in each LAB channel. Further, we also calculate the color histograms in different sampling scales with the downsampling factors 0.5 and 0.75. All the features of one patch are normalized with l2 norm. Finally, each patch is represented by a 672-dimensional feature vector.

4.2 CPDL for Image Representation

Our goal is to learn robust representations for each pedestrian in different camera views by virtue of dictionary learning. It's a challenging problem as the same person under different camera views usually exhibits significant differences in appearance. In this section, we propose to emphasize the feature learning in two levels, patch level and image level, in order to capture both local and global characteristics from the pedestrian images. Note that most existing methods only consider feature learning in one single level [Liu et al., 2014].

Let X1 and X2 denote the training sets of high-dimensional dense features in two views, respectively. For the i-th training image in view 1, the dense features of all the patches are concatenated as a high-dimensional vector 1 , which is the ith column in X1. Clearly, the corresponding columns in X1 and X2 should have similar codings, since they represent the same pedestrian. Hence, by defining the regularization function f(·) in (2), we have the following objective

where DH 1 (and DH 2 ), P H 1 (and P H 2 ) denote the dictionaries and projection matrices in two views, respectively.

The regularization function in (3) is ∥∥P H 1 X1 - P H 2 X2∥∥2F, indicating that the codings in two views should be as close as possible. In this way, the learned dictionaries DH 1 andDH 2 are expected to generate similar codings for the same pedestrian under two camera views.

1 As we have high-dimensional image-level features and lowdimensional patch-level features, we use superscripts H and L for the image-level and patch-level variables, respectively.

4.3 CPDL for Patch Representation

In addition to modeling the image representation in (3), we also consider the dictionary learning in patch-level representations. Let Y1 and Y2 denote the training sets of lowdimensional patch features in two views, respectively. In this case, we cannot simply assume that the codings in two views are close to each other. In reality, the i-th patch in view 1 may not match the i-th patch in view 2 due to the misalignment problem under cross-view settings. One reasonable assumption is that the patches in different views could share a similar dictionary. Therefore, the objective function is

in which the last term emphasizes the similarity of two dictionaries.

4.4 Matching and Fusion

With the learned two pairs of dictionaries, {DL 1 , DL 2 } and {DH 1 ,DH 2 }, we can obtain robust representations for the test images in two views, and perform the following matching and fusion strategy.

In person re-identification, we need to match a probe image to a set of gallery images. As our approach jointly learns the dictionaries in both patch-level and image-level, we propose a fusion strategy to take full advantages of the robust representations.

Patch-level Matching. The patch matching methods have been extensively studied in existing works [Zhao et al., 2013a; 2014]. We adopt a similar constrained patch matching strategy. For each patch in the probe image, we can not directly match it to the corresponding patch in gallery images, due to the well-known misalignment problem. Therefore, we search the spatial neighbors of the targeted patch in the gallery images, and calculate the distances between each pairs. Finally, we can estimate the similarity between a probe image and every gallery image. Instead of comparing the original patches, we match the representation coefficients over the dictionaries {DL 1 , DL 2 } for each pair of patches. The similarity score ScoreP(i) between the probe image and the i-th gallery image is generated from the similarities between these patches.

Image-level Matching. The image-level matching between the probe image and gallery images is more straightforward, as we have already attained the compact representations for each image. The representation coefficients are calculated using the dictionaries {DH 1 ,DH 2 } for each pair of patches. We adopt the Gaussian kernel function to compute the similarity score ScoreI(i) between the probe image and the i-th gallery image.

Fusion. We first normalize the similarity score vectors ScoreP and ScoreI, and utilize a simple strategy to perform

where λ is an user-defined parameter.

5 Optimization

5.1 Solving objective (3)

To facilitate the optimization of (3), we first add two relaxation variables AH1 and AH2 , and rewrite the objective as

where α is a balance parameter.

Although there are many variables in (6), we can alternatively optimize these variables as follows.

1). Fix other variables and update AH1 and AH2 .

By ignoring the irrelevant variables with respect to AH1 , the objective (6) is reduced to

Setting ∂J(AH1 )

where I is an identity matrix. We can obtain solution to AH2 in a very similar way.

2). Fix other variables and update P H 1 and P H 2 .

The objective function regarding P H 1 can be written as

By setting the derivative with respect to P H 1 to zero, we have the solution P H 1 = AH1 X1(X1XT 1 + γI)-1 , where γ is a regularization parameter. Similarly, the solution to P H 2 is: P H 2 = AH2 X2(X2XT 2 +γI)-1 . 3). Fix other variables and update DH 1 and DH 2 .

By removing the irrelevant terms in (6), we can write the objective function regarding DH 1 as

Problem (10) can be effectively solved using ADMM algorithm as introduced in [Gu et al., 2014]. We have similar solutions to DH 2 .

The above procedures are repeated until convergence. Finally, we obtain a pair of dictionaries {DH 1 ,DH 2 } that are used to represent high-dimensional image features.

5.2 Solving objective (4)

To solve the problem (4), we first reformulate the objective as

Algorithm 1. CPDL for Person Re-identification

Input: Training images in two views A1, A2,

test images T1, T2, parameters λ1, λ2, λ, α, β. Output: Matching results.

Training

• 1: Extract dense features fromA1,A2 (Section 4.1), and construct feature sets X1, X2, Y1, Y2;
• 2: Learn dictionaries {DH 1 ,DH 2 } from image-level features X1, X2 (Section 5.1);
• 3: Learn dictionaries {DL 1 , DL 2 } from patch-level features Y1, Y2 (Section 5.2);

Testing

• 4: Extract dense features from T1, T2 (Section 4.1), and construct feature sets Xt1, Xt2, Yt1, Yt2;
• 5: Encode Xt1, Xt2 using {DH 1 ,DH 2 }, and perform image-level matching (Section 4.4);
• 6: Encode Yt1, Yt2 using {DL 1 , DL 2 }, and perform patch-level matching (Section 4.4);
• 7: Fuse matching results in two-levels using (5).

where β is a balance parameter.

We alternatively update the variables in (11), and obtain the sub-problems (with solutions) as follows

The solution to (12) is AL1 = (DLT 1 DL 1 + βI)-1 (DLT 1 Y1 + βP L 1 Y1).

The optimal solution is P L 1 = AL1 Y1(Y1Y T 1 +γI)-1 .

We have similar solutions to AL2 , P L 2 and DL 2 . The above procedures are repeated until convergence. We finally obtain a pair of optimal dictionaries {DL 1 , DL 2 } that are used to reconstruct low-dimensional patch features.

The complete algorithm is summarized in Algorithm 1.

6 Experiments

In this section, we compare our approach with several related methods on two benchmark datasets, VIPeR [Gray et al., 2007] and CUHK01 Campus [Zhao et al., 2014].

6.1 Settings

Baselines. We compare our approach with three types of person re-identification methods, which are feature learning methods, metric learning methods and dictionary learning methods. The feature learning methods include symmetrydriven accumulation of local features (SDALF) [Farenzena et al., 2010], local descriptors encoded by Fisher vectors (LDFV) [Ma et al., 2012b], unsupervised salience learning method (eSDC) [Zhao et al., 2013b], salience matching method [Zhao et al., 2013a], and mid-level filters [Zhao et al., 2014]. The compared metric learning algorithms include probabilistic relative distance comparison (PRDC) [Zheng et al., 2011], large margin nearest neighbor (LMNN) [Weinberger et al., 2005], eBiCov [Ma et al., 2012a], informationtheoretic metric learning (ITML) [Davis et al., 2007], pairwise constrained component analysis (PCCA) [Mignon and Jurie, 2012], KISSME [K¨ostinger et al., 2012], and local Fisher discriminant analysis (LF) [Pedagadi et al., 2013]. We also compare with the dictionary learning method SSCDL [Liu et al., 2014].

Evaluation Metrics. We employ the standard cumulated matching characteristics (CMC) curve as our evaluation metric, and report the Rank-k recognition rates.

Parameter Setting. There are five parameters in our model, including α, β, λ, λ1 and λ2. In the experiments, we empirically set these parameters to achieve the best performance. In particular, α and β are set to 2 and 1, respectively. λ used in the fusion strategy is chosen in the range [0 1]. Two parameters λ1 and λ2 control the effects of cross-view interactions, and we will discuss their settings in the next section.

6.2 VIPeRDataset

The VIPeR dataset was collected in an outdoor academic environment. It contains images of 632 pedestrian pairs under two camera views with different viewpoints. The images in two views have significant variations in pose, viewpoint and illuminations. Figure 2(a) shows some images captured by Camera-1 (first row) and Camera-2 (second row) in the VIPeR dataset. The images are normalized to the size of 128×48 in our experiments.

We follow the evaluation protocol in [Gray and Tao, 2008]. In particular, we randomly select 316 pairs of images for training, and the remaining pairs are used for test. Then, two groups of experiments are conducted. First, the images captured by Camera-1 are utilized as probe images, and the images captured by Camera-2 as gallery images. For the probe images, we match each of them to the gallery set, and obtain the Rank-k rate. The CMC curves are also obtained by using the rates at all ranks. Second, we exchange the training and test sets, and repeat the above procedures. As the raw features for image-level training have very high dimensions, we apply PCA to reduce the dimensionality by keeping the 95% energy. We conduct 10 random tests and report the average results. Each random test has two groups of evaluations as described above.

Figure 3 shows the CMC curves of the compared methods. We can observe that our approach achieves higher matching rates in each rank. Table 1 shows the detailed Rank1, Rank-5, Rank-10, and Rank-20 matching rates of all the compared methods. It shows that the advanced feature learning methods like salience matching (SalMat) and mid-level filters obtain much better results than metric learning methods. The dictionary learning method SSCDL achieves better Rank-5/10/20 rates than the SalMat and Mid-level methods, which shows the merits of dictionary learning. Our approach achieves the best Rank-1 rate, and significantly improves the Rank-5/10/20 rates, validating the effectiveness of the proposed CPDL framework.

6.3 CUHK01 Campus Dataset

The CUHK01 Campus dataset contains pedestrian images of 971 persons in two camera views. It was collected in a campus environment. This dataset shows significant changes of viewpoints. The frontal or back views are captured by Camera-1, while the side views are captured by Camera-2. Figure 2(b) illustrates some images in view 2 (first row) and view 1 (second row). The images are resized to 160×60 in our experiments.

We follow the evaluation protocol in [Zhao et al., 2014]. For each person, one image is randomly selected to build the gallery set, and the other one is used to construct the probe set. We map each image in probe set to every gallery image, and calculate the correct matched rank and CMC curves. The whole procedure is repeated for 10 times, and the average CMC curves are generated, as shown in Figure 4. Table 2 shows the detailed Rank-1/5/10/20 matching rates of the compared methods. We can observe that our approach obtains much higher matching rates than other methods. The Rank-1 matching rate is improved by 25.17%, compared to the mid-level filter method.

6.4 Discussions

Different from existing methods, the proposed CPDL approach models the interactions between different views, such as the similarities of codings (in the image-level) or dictionaries (in the patch-level). The parameters λ1 and λ2 control the effects of the cross-view interactions. Figure 5(a) shows the Rank-1 matching rates of our approach with different values of λ1 and λ2. It shows that our approach is not very sensitive to the choice of parameters in the range [0 5]. We set λ1 = 1, λ2 = 2.

Figure 5(b) shows the CMC curves of our approach and its two components, i.e., image-level model and patch-level model. We can observe that the representations in imagelevel and patch-level are complementary to each other, and our approach takes full advantage of the complementary information.

Another important factor in our approach is the size of dictionary. We use the same dictionary size in different views. Figure 5(c) shows the Rank-1 matching rate with different dictionary size. We achieved similar results on the CUHK01 dataset. Accordingly, the dictionary size is set to 50 in our experiments. Also, we note that the matching process in existing feature learning methods (e.g., SalMat or Mid-level filter) is very time consuming. However, our approach adopts a relative small dictionary, which leads to compact representations of images, and therefore speeds up the matching process.

7 Conclusions

We proposed a cross-view projective dictionary learning (CPDL) approach for person re-identification in this paper. Our approach learned two pairs of dictionaries across different views in patch-level and image-level, respectively. The learned dictionaries can be used to represent probe and gallery images, leading to robust representations. Experimental results on the public VIPeR and CUHK Campus datasets showed that our approach took full advantages of the complementary information in different views and representation levels, and achieved the state-of-the-art performance compared with the related methods.

Acknowledgments

This research is supported in part by the NSF CNS award 1314484, ONR award N00014-12-1-1028, ONR Young Investigator Award N00014-14-1-0484, and U.S. Army Research Office Young Investigator Award W911NF-14-10218.