Mixed Error Coding for Face Recognition with Mixed Occlusions

1 Introduction

Real-world face recognition system has to contend with a lot of uncontrolled variations [Hua et al., 2011], such as bad lighting conditions [Lai et al., 2014], large pose variations [Cai et al., 2013], a range of facial expressions [Bettadapura, 2012], apparels, changes in facial hair, eyewear, and partial occlusions. In spite of the diversity, most of these variations can be viewed as different instances of occlusion. When there exists occlusion in a test face image, the classical holistic feature extraction methods, such as Eigenfaces [Turk and Pentland, 1991] and Fisherfaces [Belhumeur et al., 1997], are not applicable since the whole extracted features would be distorted by local occlusion, and robust classifiers, such as SRC [Wright et al., 2009] and CESR [He et al., 2011], might fail to perform recognition due to the common high order statistical structures (localization, orientation, and bandpass) shared by occlusions and face images. Moreover, there often exists practical scenarios that more than one kind of occlusion, which we call mixed occlusions, are simultaneously imposed on one face image and greatly increase the difficulty of the recognition task. Apparels and extreme illumination variations are commonly seen mixed occlusions and have long been considered as one of the most difficult problems of face recognition [Tzimiropoulos et al., 2012]. We therefore focus on this challenge in this work.

There are a lot of schemes to deal with occlusion related problems. We put our focus mainly within the framework of sparse coding. In this framework, the test occluded image y ∈ Rm is supposed to be a superposition of its clean reconstruction ˆ y ∈ Rm and an error image e ∈ Rm, and ˆ y is supposed to be sparsely coded by a linear combination of the training images A = [A1,A2, · · · ,AK] ∈ Rm×n of K subjects, where Ak = [ak1 , ak2 , · · · , aknk ] ∈ Rm×nk is a data matrix consisting of nk training samples from subject k and n = ∑Kk=1 nk. The error image e is also called the reconstruction error, since it calculates the difference between y and its reconstruction ˆ y. By simultaneously imposing sparse constraint on the coding coefficient and various probabilistic assumptions on the reconstruction error e, researchers have presented a lot of solving methods [Tibshirani, 1996; Chen et al., 2001; Wright et al., 2009; Wright and Ma, 2010; Jia et al., 2012], which can be summarized as

where we denote by p (·) a probability density function (PDF) and x ∈ Rn is the coding coefficient of y with respect to (w.r.t.) A.

The main limitation of the error coding model (1) is that it usually has a low breakdown point in dealing with the occlusion problems [Wright et al., 2009]. To improve the classification performance of (1), researchers proposed the weighted error coding scheme

where w ∈ Rm is the weight vector. Two representative methods of the weighted error coding model are the Robust Sparse Coding (RSC) [Yang et al., 2011] and the CorrEntropy-based Sparse Representation (CESR) [He et al., 2011]. Due to the capability of feature selection by weighting the features, the weighted error coding model (2) usually outperforms the error coding model (2) in dealing with realworld occlusion. However, the feature selection ability of the weighted error coding model (2) is still not very strong, since it just weakens (but not removes) the bad features with large errors, and also, due to the shared statistical structures of face images and occlusions, the really bad features not always induce large errors.

To enhance the feature selection ability of the model (2), researchers exploit, instead of the structures of the useful features, the spatial structures shared by occlusions, such as locality, continuity [Lin and Tang, 2007; Zhou et al., 2009] and boundary regularity [Li et al., 2013]. Harnessing the contiguous structure, [Zhou et al., 2009] first built the following error coding model

where s ∈ {-1, 1}m denotes the occlusion/feature support, that is, si = -1 indicates pixel yi is non-occluded (useful feature) and si = 1 indicates pixel yi is occluded (useless feature). The two state-of-the-art methods deriving from model (3) are the Sparse Error Correction with Markov Random Fields (SEC_MRF) [Zhou et al., 2009] and the Structured Sparse Error Coding (SSEC) [Li et al., 2013]. Due to efficiently excluding the bad features incurred by occlusion, SEC_MRF and SSEC outperform significantly the methods of model (1) and (2) in dealing with the problem of face recognition with occlusion. However, both SEC_MRF and SSEC require that the number of the training images should be sufficient enough to predict the variations except for occlusions which might consist in the test images. This requirement is hardly available in practice, especially for the scenario of mixed occlusions.

Different from the above three error coding models (1), (2) and (3), [Tzimiropoulos et al., 2012] introduced a robust subspace learning framework in the domain of image gradient orientations (IGO) for appearance-based object recognition. The robustness of the IGO subspace learning methods (such as IGO-PCA and IGO-LDA) owes to the robust IGO features and the capability of hidden feature selection. Specifically, by applying a cosine-based distance measure to the IGO features, the useless features caused by outliers, to some extent, could be automatically eliminated. However, the face recognition experiment in Figure 11 of [Tzimiropoulos et al., 2012] shows that the recognition rates of IGO-PCA drop sharply once the occlusion level exceeds 60%. This indicates that with occlusion level increasing, the IGO-methods might not effectively eliminate the effect of the occlusion.

In this work, we try to solve the problem of face recognition with mixed occlusions by incorporating the robust IGO features into the error coding model (3). For mixed occlusion, we note that the error used to code the test image, we call the discriminative error, and the error used to estimate the occlusion/feature support, we call the structural error, should be coded in different ways. The coding schemes of the two errors are unified in an extended version of the error coding model (3), called the mixed error coding (MEC). By considering the MEC model in the IGO domain, we exploit the three conditional PDFs induced by the MEC model, based on which we give the solving algorithm of MEC under the framework of the Gibbs sampling algorithm. Experiments corroborate the effect of the proposed MEC model.

2 The ProposedMixed Error CodingModel

The error model (3) shows that the reconstruction error e actually simultaneously serves for two targets: reconstructing the test image y and estimating the occlusion support s.The interactive relationships of e and s are illustrated in Figure 1 (a). For simple occlusions, the same error might be enough to cope with the two cases, while for mixed occlusions, the scenarios might be completely different. Mixed occlusions usually incur a wide range of variations in the test image and squeeze the useful features into a very low dimensional space, which results in the difficulty of reconstructing y. A common way to solve this problem is to transform the low dimensional features into a high dimensional discriminative feature space (See detail in Subsection 3.1 for constructing high dimensional features in the IGO domain). This will lead to a high dimensional discriminative reconstruction error, which we call the discriminative error and denote by ˘ e. Since ˘ e usually has different dimension and structure with the original test image y, it cannot be directly used to recover the occlusion support s. To estimate s, we need an error that fully considers the spatial and statistical structure of occlusion, which we call the structural error and denote by ˜ e. The structural error ˜ e usually has the same dimension with the test image y.

We therefore have three interactive factors: the discriminative error ˘ e, the structural error ˜ e and the occlusion support s, whose interactive relationships are illustrated in Figure 1 (b). Clearly, the discriminative error ˘ e depends on the occlusion support s since s helps to select the discriminative features in calculating ˘ e, and the occlusion support s depends on the structural error ˜ e as the spatial and statistical structure of occlusion reflected in ˜ e can be used to recover s. We would like to emphasize that the structural error ˜ e depends on the discriminative error ˘ e. Actually, the structural error ˜ e calculates the structural difference between the test image y and its reconstruction ˆ y, and ˆ y is reconstructed from the training set A by a sparse coding coefficient x, and finally x is calculated by the discriminative error ˘ e. By formulating the interaction relationships between ˘ e, ˜ e and s with a joint PDF p (˘ e, ˜ e, s), we propose a new error coding model, called the Mixed Error Coding (MEC), as follows

where we impose the nonnegative constraint on x to guarantee its sparsity and denote by ˘ E (·, ·) and ˜ E (·, ·) the discriminative error metric and the structural error metric, respectively. Since it is difficult to give a definitive formulation of p (˘ e, ˜ e, s), according to the interaction relationships between ˘ e, ˜ e and s shown in Figure 1 (b), we adopt the Gibbs sampling algorithm to solving (4) as follows

where the superscript (t) denotes the tth iteration.

3 Three Statistical Inferences for Mixed Error Coding in IGO Domain

To infer the three interacted factors (˘ e, ˜ e, s) from (5), (6) and (7), a primary task is first to establish the three conditional probabilistic density/mass functions p (˘ e|s), p (˜ e|˜ e) and p (s|˜ e). Due to the robustness of the IGO features we discuss in the introduction, we explore each of the three conditional probabilistic models in the IGO domain in the following subsections. For convenience, we denote by Φ (·) the IGO transformation function and briefly denote the IGO features of y and A by ˚y = Φ (y) and ˚ A = Φ(A), respectively.

3.1 Gaussian Distribution of Discriminative Error

We first consider the conditional PDF p (˘ e|s). As an important discriminative information to search for the right subspace (class) that the test image comes from, the discriminative error ˘ e should be only considered in the non-occluded region to avoid the effect incurred by occlusion. To compensate for the losses caused by occlusion, we transform the features in the non-occluded region into a high dimensional feature space. As demonstrated by [Wright et al., 2009], in the framework of sparse coding, it is the dimension of the feature that plays a critical role in determining the discriminability. For the IGO features, [Tzimiropoulos et al., 2011] suggested imposing cosine and sine kernel on the angular data and then stacking the outputs as columns to form new feature vectors, that is, the new high dimensional features of the test and training images can be formulated as ˘ y = [cos˚yT sin˚yT ]T ∈ R2m and ˘ A = [cos ˚ AT sin ˚ AT ]T ∈ R2m×n . Then, in this high dimensional feature space, it is reasonable to assume that the DE ˘ e follows the Gaussian distribution with zero mean

where ˘ e = ˘ y - ˘ Ax, ˘ s = [sT sT ]T and ˘σ is the Gaussian kernel size. Figure 3 (b) shows the histograms of 5 discriminative errors produced during the iteration of our proposed algorithm for a test image.

For inference of ˘ e, substituting (8) into (5), we have

where is the Hadamard product. The optimization problem (9) is a nonnegative least squares problem (NNLS) and can be solved by the classical active set algorithm [He et al., 2011].

3.2 UniformDistribution of Structural Error

We now consider the conditional PDF p (˜ e|˘ e). The structural error ˜ e reflects the structural difference between the test image ˚y and its reconstruction ˚ˆ y. Using the coding coefficient x(t) solved from (9), we could reconstruct a clean version ˚ˆ y(t) = Φ (Ax(t) ) of the test image ˚y. In the original pixel domain, [Li et al., 2013] pointed out that the structural error between y and its reconstruction ˆ y calculated by a well designed error metric would present a special distribution structure: the errors corresponding to the occluded part concentrate on a large value, and the errors corresponding to the non-occluded part concentrate on zero. However, in the IGO domain, we will show that the structural error measured by a well designed structural error metric would follow a uniform distribution which is independent of the occlusion support. Therefore, what is critical for building the conditional PDF p (˜ e|˘ e) is to design a reasonable structural error metric.

We first review a robust distance measure in the IGO domain. [Tzimiropoulos et al., 2012] statistically verified that the gradient orientation differences of any two pixel-wise dissimilar images follow a uniform distribution in the interval [-π, π) with a high significant level. Furthermore, this uniform distribution is subtly used to approximately cancel out the error caused by outliers according to the following theorem:

Theorem 1. Let u(·) be a mean ergodic stochastic process and u(t) follows a uniform distribution in [-π, π), then for any non-empty interval X ∈ R, rX cos (u (t)) dt = 0.

Based on Theorem 1, [Tzimiropoulos et al., 2012] defined a cosine-based distance measure (CDM):

Ideally, according to Theorem 1, all of the errors incurred by outliers would be summed up to zero in (10) and hence CDM only calculates the distance of the clean parts of the two compared images.

In spite of its robustness, CDM cannot be directly used to estimate the distribution of the error between two compared images, since its calculating result is a scalar. We therefore need to vectorize CDM to form a new error metric. In fact, if we shrink the action scope of the CDM to the neighborhood of one feature point of the two compared images and use the distance calculated by CDM on this neighborhood as the final observed error value at this point, we then obtain the following cosine-based error metric (CEM)

where N (i) is the neighborhood of feature point i. A fast implementation of CEM can be given by imposing K-means filtering on the error vector ϵ = 1 - cos (˚y -˚ˆ y). Note that CEM only harnesses the spatial (local and contiguous) structure of occlusion. In order to enhance the clustering effect of CEM, we further consider the statistical structure of the error calculated by CEM. To integrate the statistical local information of the input error, [He et al., 2011] suggested using the correntropy induced metric (CIM)

We therefore incorporate CEM into CIM to form a new structural error metric

Figure 2 illustrates the whole calculating flow of (13). In essence, the structural error metric (13) amounts to orderly imposing three smoothing operations (cosine, K-means and Gaussian) on the gradient orientation difference ˚y -˚ˆ y, which finally smooth the diversity of the whole error values and thus induce a uniform distribution of the measured SE ˜ e on the interval [0, 1). The experiment in Figure 3 (f) demonstrates that p (˜ e|˘ e) is more and more close to a uniform distribution with the improvement of the quality of the recovering image ˆ y.

The uniform distribution of the structural error ˜ e calculated by (13) can not be used to infer ˜ e, but can be utilized as a stopping iterative criterion of our proposed algorithm, as shown in Figure 3 (f). We calculate ˜ e by directly inputting the entries of ˚y and ˚ˆ y(t) = Φ (Ax(t) ) into the error metric (13).

3.3 Bayesian Inference of Occlusion Support

We now consider the conditional probabilistic mass function (PMF) p (s|˜ e). Since s and ˜ e have the same dimension and similar structure (i.e., the larger the structural error ˜ ei, the more tendency si = 1), we explore p (s|˜ e) from a Bayesian perspective

where p (s|˜ e) is viewed as a posterior PMF, p (˜ e|s) is the likelihood function, and p (s) is the prior probability of s. This Bayesian model has been explored deeply in [Zhou et al., 2009]. By summarizing the work of [Zhou et al., 2009] and incorporating (14) into (7), we have the following optimization problem

where Kτ (˜ ei) = {1, |˜ ei| > τ 0, |˜ ei| ≤ τ . (15) can be solved using graph cuts [Kolmogorov and Zabih, 2004].

4 The Algorithm

By iteratively using (9), (13) and (15), we could solve the MEC problem (4). The important outputs of this iterative procedure are the the occlusion/feature support s and the coding coefficient x. Using s and x, we are able to identify the test image y from the training set A based on some measure of goodness-of-fit. In this work, we adopt a subject specific reconstruction classifier similar to the sparse classifier proposed by [Wright et al., 2009], but the major difference is that the classifier introduced here is based on the selected features.

Algorithm 1 summarizes the whole procedure of optimizing the MEC model (4). Figure 3 gives a detailed illustration of the iterative procedure.

Algorithm 1 Mixed Error Coding (MEC)

Input: training data A, test sample y. Output: occlusion/feature support s, identity (y).

1. Calculate the mean face ˆ y of the training image A;
2. Transform y, ˆ y and A into the IGO domain: ˚y = Φ (y), ˚ˆ y = Φ(ˆ y), ˚ A = Φ (A);
3. Repeat
4. Calculate the structural error ˜ e: ∀i ∈ {1, 2, · · · ,m}, ˜ ei = CC (˚yi,˚ˆ yi);
5. Recover the occlusion support s by solving (15);
6. Calculate the discriminative error ˘ e and the coding coefficient x by solving (9);
7. Calculate the reconstruction˚ˆ y = Φ (Ax);
8. Until maximum iterations or convergence.
9. For k = 1, · · · ,K, compute the residuals rk = ∥∥∥ 1 2 (1- ˘ s) ⊙ ( ˘ y - ˘ Aδk (x))∥∥∥2 2 , where δk (x) is a new vector whose only nonzero entries are the ones in x that correspond to subject k;
10. identity (y) = argmink rk.

5 Experiments

To evaluate the performance of the proposed MEC algorithm, we compare it with four related popular methods for robust face recognition with occlusion: IGO-PCA [Tzimiropoulos et al., 2012], SSEC [Li et al., 2013], CESR [He et al., 2011] and RSC [Yang et al., 2011]. The parameters of our MEC algorithm are selected as: λµ = 0, τ = 0.3,λs = 2 and σ = 0.75 in CIM. The parameters of the other methods are set according to the strategy suggested in their papers.

We conduct a set of experiments on the Extended Yale B database [Georghiades et al., 2001] and the AR database [Martínez, 1998]. The Extended Yale B database contains 2414 frontal face images of 38 persons under 64 different illumination conditions. The AR database, which is one of the very few databases that contain real disguise, consists of over 4,000 color images corresponding to 126 persons' frontal view faces with different facial expressions (neutral, smile, anger, and scream), illumination conditions (left light on, right light on, and all side lights on), and occlusions (sunglasses and scarves). 26 pictures were taken for each person in two sessions.

5.1 Synthetic Occlusions Mixed with Various Illuminations

In this experiment, we use the Extended Yale B database to test the robustness of our algorithm against various levels of synthetic occlusions under various illumination conditions. The illumination conditions of the Extended Yale B database are partitioned to 5 subsets: from normal illumination variations to extreme ones. For training, we use images from Subset I and II (717 images, with normal-tomoderate illumination conditions); for testing, we use images from Subset III (453 images, with extreme illumination conditions), Subset IV (524 images, with more extreme illumination conditions) and Subset V (712 images, with the most extreme illumination conditions), respectively. To simulate different levels (from 0% to 90%) of contiguous occlusion, we replace a random block of each test image with a mandrill image, which has similar structure with the human face and has been widely used as synthetic occlusion in robust face recognition testing [Wright et al., 2009; Zhou et al., 2009; Yang et al., 2011; He et al., 2011; Li et al., 2013].All images are cropped and resized to 96 × 84 pixels. Note that this experimental setting is similar to the one in [Wei et al., 2012].

Figure 4 compares the recognition rates of MEC with other related approaches on the three different test subsets, respectively. Compared to MEC and IGO-PCA, the recognition performances of SSEC, CESR and RSC drop sharply with the illumination conditions worsening from Subset III to IV, which manifests the importance of the IGO features against illumination changes. Clearly, in this experiment, the nearest competitor of MEC is IGO-PCA, which performs almost as well as MEC when the occlusion level is lower than some breakdown point. This breakdown point, however, rapidly declines with the illumination conditions of the test images worsening. This illustrates that the illumination conditions greatly intensify the effect of occlusions in face recognition. Especifically for the most extreme illumination conditions of Subset V, the breakdown point almost decreases to 0 and MEC significantly outperforms IGO-PCA, as seen from Figure 4 (c). This indicates the important role of the feature selection of MEC.

5.2 Real-world Disguises Mixed with Highlight Illuminations

We next test our algorithm on real disguises mixed with nonuniform illuminations using the AR Face database. We select a subset of the database that consists of 65 male subjects and 54 female subjects. The grayscale images are resized to resolution 112 × 92. For training, we use 952 non-occluded frontal view images (8 images for each subject) with varying facial expressions but normal illuminations. For testing, we use images that simultaneously contain illumination variations (normal/right-side/left-side light conditions) and disguises (sunglasses and scarves).

Figure 5 compares the recognition rates of different methods using different downsampled images of dimensions 154, 644, 2576, and 1,0304, which correspond to downsampling ratios of 1/8, 1/4, 1/2, and 1, respectively. With feature dimensions increasing, the recognition performance of our MEC dramatically outperforms the other four methods. Specially, at the dimension of 1,0304, compared to the nearest competitors IGO-PCA and RSC, MEC achieves over 20%

and 25% higher recognition rates for the sunglasses and scarf disguises, respectively. Note that the recognition rate gaps between MEC and IGO-PCA in Figure 4 are much smaller than the ones in Figure 5. This is mainly caused by the opposite illumination conditions: the illuminations in Figure 4 are dark and shadowed, while the illuminations in Figure 5 are mostly with highlight conditions. Clearly, the high specularities cannot be well normalized in the IGO domain. In this scenario, feature selection becomes very important. The significantly higher recognition rates of our MEC than those of the other four methods at high dimensions show that MEC has a strong feature selection ability in high feature space. We also observe that the recognition rate of SSEC against scarf disguises (see Figure 5 (b)) significantly outperforms the other compared methods at the low dimension. This inspires us to further study the occlusion structure of the low dimensional image from SSEC in the IGO domain in the future.

6 Conclusions

We propose a mixed error coding (MEC) model for robust classification of face images with mixed occlusions. To cope with the complex variations caused by mixed occlusions, MEC distinguishes the error used to code the occluded image from the error used to estimate its occlusion/feature support, and explores the statistical correlations between the two various errors and the occlusion support in the domain of image gradient orientations. An important result of this exploration is a well-designed structural error metric, which fully uses the spatial and statistical structure of the gradient orientation differences of two compared images and plays an important role in feature selection. Experiments demonstrate the effectiveness and robustness of MEC in dealing with mixed occlusions.

Acknowledgment

This work is partially supported by National Science Foundation of China (61402411), Zhejiang Provincial Natural Science Foundation (LY14F020015), and Program for New Century Excellent Talents in University of China (NCET-121087).

Biography

Ronghua Liang received the Ph.D. in computer science from Zhejiang University in 2003. He is currently a Professor of Computer Science and Vice Dean of College of Information Engineering, Zhejiang University of Technology, China. He has published more than 50 papers in leading international journals and conferences including IEEE TKDE, IEEE TVCG, IEEE VIS. His research interests include Information Visualization, Computer Vision, and Medical Visualization.

Xiao-Xin Li is currently an Assistant Professor with the College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou, China. His research interests include Image Processing and Machine Learning.