# Kernel Coupled Cross-Regression for Low-Resolution Face Recognition

Authors: Zhifei Wang; Zhenjiang Miao; Yanli Wan; Zhen Tang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Low resolution (LR) in face recognition (FR) surveillance applications will cause the problem of dimensional mismatch between LR image and its high-resolution (HR) template. In this paper, a novel method called kernel coupled cross-regression (KCCR) is proposed to deal with this problem. Instead of processing in the original observing space directly, KCCR projects LR and HR face images into a unified nonlinear embedding feature space using kernel coupled mappings and graph embedding. Spectral regression is further employed to improve the generalization performance and reduce the time complexity. Meanwhile, cross-regression is developed to fully utilize the HR embedding to increase the information of the LR space, thus to improve the recognition performance. Experiments on the FERET and CMU PIE face database show that KCCR outperforms the existing structure-based methods in terms of recognition rate as well as time complexity.


---

## Body

## 1. Introduction

Face recognition (FR) has been widely studied for decades due to its great potential applications. Many technologies focused on dealing with complex conditions such as aging, occlusion, disguise, and variations in pose, illumination, and expression. Although the recognition accuracy of face recognition in controlled environments with cooperative subjects is satisfactory, the performance in real applications such as surveillance and mobile service is still an unsolved problem partially due to low-resolution (LR) image quality [1]. With the growing installation of embedded cameras in many places, there are increasing demands for face recognition in interaction and surveillance applications from interactive processing cameras in mobile communications, small-scale stand-alone cameras in banks and supermarkets, to large-scale multiple networked close-circuit televisions in public streets. In such cases, subjects are far from cameras without any restriction, and face regions tend to be small or poor quality. This issue is called low-resolution face recognition (LR FR).Gallery images are generally assumed to be high resolution (HR) in practical face recognition applications. Therefore, LR will obviously cause the problem of dimensional mismatch between HR gallery images and LR probe ones in the special applications such as criminals monitoring and mobile communication with their HR images in network databases. To deal with the problem, three general ways can be considered as follows. The first way is down-scaling HR gallery image, which seems to be a feasible solution for the mismatching problem. Unfortunately, it drastically reduces the amount of available information, especially the high-frequency information mainly for recognition when the resolution is very low such as12×12 or even 8×8. Secondly, upscaling LR probe image, such as interpolation, is conventionally adopted in most of the subspace-based face recognition methods. Some researchers tried to propose some resolution-robust feature representation methods, which is to extract the discriminative information from LR images (or upsampled versions) directly. The landmark works are RQCr color feature [2], local frequency texture descriptor [3], and novel kernel correlation feature analysis [4]. However, they are sensitive to resolutions more or less and fail to complete full resolution robustness. For further refined solution, the widely used super resolution (SR) or face hallucination [5] technique can be employed to estimate HR faces from LR ones. However, they usually require a lot of images which belong to the same scene with precise alignment and also need large time consumption. In addition, most of these methods aimed to improve face appearance but failed to optimize face images from recognition perspective. Recently, a few attempts were made to achieve these two criteria under very LR case [6]. Also some researchers studied simultaneous super resolution and recognition for providing a promising way to solve this problem [7, 8], though they also need high-computational cost.The third way is unified feature space, also called inter-resolution space, which is used to project HR gallery images and LR probe ones into a common space [9]. Here we call it as structure-based method, which is an essential way to solve the mismatch problem. It aims to build the holistic structure to facilitate direct matching between them from classification perspective. For example, Li et al. [10] proposed a general framework called coupled mappings (CMs) to project LR and HR face images into a unified feature space. The problem with this method is that it offers poor classification ability. Thus, they further introduced locality weight relationships [11] into CMs and proposed coupled locality preserving mappings (CLPMs), which significantly improved the performance. However, how to efficiently solve the eigenvalue decomposition in the projection matrix computation remains unsolved in CLPMs, which is the common problem in the structure-based method. Furthermore, CLPMs is sensitive to the parameters of the penalty weighting matrix such as scale and neighbor. Subsequently, other methods are developed to improve the classification performance of CMs. Deng et al. [12] considered two other relationships in LR classification (LR versus LR and HR versus HR) besides LR versus HR used in CMs. Zhou et al. [13] proposed simultaneous discriminant analysis method by introducing linear discriminant relationships [14] between intraclass scattering and interclass scattering into CMs. Ren et al. [15] integrated nonlinear kernel trick into CMs/CLPMs, which transferred LR/HR pairs from the input space to the kernel-embedding space. Although these methods are proven to be discriminative and efficient, they still require much more computational costs for system implementation.Inspired by the works in [15, 16], we propose a novel structure-based method to deal with LR FR, called kernel coupled cross-regression (KCCR), which adopts two mapping matrices to project LR and HR face images represented by nonlinear kernel into a unified feature space for the final feature matching, shown in Figure 1. KCCR firstly transforms LR and HR images from the original observing space into the low-embedding space obtained by linear graph embedding technique [17]. Meanwhile, the features of images are represented by nonlinear kernel tricks to increase the computational power of the linear embeddings. Spectral egression (SR) [18] is then introduced to generalize the model and reduce the time complexity. Furthermore, cross-regression is developed to fully utilize the HR embedding to increase the information of the LR space, by which two more discriminant coupled projection matrices are obtained. The transformations can be learned offline from the training images. During testing, the input images are transformed using the two coupled projection matrices and then matching. Therefore, KCCR that combines cross-regression with kernel is more efficient and effective and can achieve better performance than the existing structure-based methods as well as some subspace learning methods or kernel-based methods. It will be shown in the experiments with the FERET and CMU PIE face database.Figure 1
Overview of kernel coupled cross-regression.There are three main contributions in this paper.(1)
We build the transformations in the low-embedding space, which is totally different from other existing structure-based methods performing in the original observing space, and the time complexity is reduced from cubic to linear by spectral regression.(2)
We creatively propose cross-regression technique to improve the discriminant ability, which helps to extract more high frequency or local information among HR samples for LR matching.(3)
Since nonlinear kernel functions have been successfully used to build more efficient coupled mapping models in [15, 19], we also introduce the kernel trick into our cross-regression model and further increase its recognition performance.The rest of this paper is organized as follows. Section2 presents our proposed KCCR method. In Section 3, we give an analysis of generality about KCCR and their connections to linear graph embedding and coupled mappings. Experimental results on the publicly used databases are shown in Section 4. Section 5 concludes the paper.


## 2. Kernel Coupled Cross-Regression

LR results in the problem of dimensional mismatch between HR gallery images and LR probe ones, which will directly lose a lot of useful information for optimal classification. Thus, it is feasible to project LR/HR pairs into a unified feature space. Moreover, such mappings are required to be most discriminative for feature matching, and the computation should be efficient. Our KCCR method is just designed to achieve these goals based on kernel coupled mappings and spectral regression.


### 2.1. Problem Description

The idea of coupled mappings aims to obtain two projection matricesAh and Al with sizes of m×d and M×d to realize the minimization problem as shown in (1), where xhi and xli represent HR and LR face images, respectively and N is the total number of samples.
(1)J(Ah,Al)=∑i=1N‍∥xhiTAh-xliTAl∥2.CMs model [10] aims to obtain a unified feature space at the pixel or feature level. Therefore, the performance of CMs essentially depends on the contents or features of face images. In other words, CMs model itself does not bring any new information for LR FR. Here, we introduce a low-dimension embedding of X, denoted as y, to transform LR and HR into a low-embedding space based on spectral regression instead of an observing pixel space. Then it will obtain more information about LR samples by exploring the relationships among HR samples and improve the efficiency of CMs model drastically:
(2)XhTAh⟶y⟵XlTAl.


### 2.2. Graph Embedding and Regression Framework

Given a graphG={X,W} with vertex set X={x1,x2,…,xN} and similarity matrix W∈ℜN×N; each vertex xi represents a face image and Wij represents the weight of the edge joining vertices xi and xj. The graph G can then be used for characterizing various statistical or geometric properties of the data set. Therefore, graph embedding [17] is to represent each vertex of the graph as a low-dimensional vector that preserves similarities between the data point pairs, and regression is used for solving the optimization problem of graph embedding, which reduces the time complexity. Based on these points, spectral regression [18] is introduced into CMs, which makes the CMs model more efficient for LR FR.Lety={y1,y2,…,yN}T be the low-dimensional embeddings of the vertex set X, which means if vertices xi and xj are close then yi and yj are also close. The optimal y is given by minimizing
(3)y=argminy∑i,j‍∥yi-yj∥2Wij=argminy2yTLy,
where L=D-W is the graph Laplacian matrix and D is a diagonal matrix with Dii=∑j‍Wij. A constraint yTDy=1 is then imposed for removing the arbitrary scaling factor in the embedding:
(4)y=argminyTDy=1yTLy=argminyTLyyTDy=argmaxyTWyyTDy.The optimaly can be obtained by solving the maximum eigenvalue problem:
(5)Wy=λDy.From the classification perspective, a relationshipf between yi and xi should be introduced, that is, yi=f(xi)=xiTA via a linear function. Equation (4) can be written as
(6)A=argmaxyTWyyTDy=argmaxATXWXTAATXDXTA.The optimalA can be obtained by solving the maximum eigenvalue problem:
(7)XWXTA=λXDXTA.
This framework is called linearization of graph embedding (LGE). With different choices of similarity matrix W, LGE will lead to many popular linear subspace learning methods such as linear discriminant analysis (LDA) [14] and locality preserving projection (LPP) [11]. For LDA and LPP, W is defined as follows.LDA. Suppose the tth class has mt samples:
(8)Wij={1mtifxiandxjbothbelongtothetthclass,0otherwise.LPP. Let Nk(xi) denote the set of k nearest neighbors of xi. 								(9)Wij={exp-∥xi-xj∥2/2σ2ifxi∈Nk(xj)orxj∈Nk(xi),0otherwise.


### 2.3. The Proposed KCCR Method

Inspired by the work of Lei and Li [16] adopting two embeddings to describe heterogeneous face data, we introduce yl and yh to represent the embeddings of LR and HR face data, respectively. In the embedding solution, LDA aims to preserve the global relationships between data points in favor of LR face space mainly containing low-frequency information, while LPP aims to preserve the local relationships between data points in favor of HR face space mostly depending on high-frequency features. Therefore, compared with the representing LR and HR space both by LPP in CLPMs [10] and by LDA in SDA [13], yl and yh are obtained by LDA and LPP, respectively, in our CCR method for making full use of the combination of global and local information in data. Furthermore, in order to utilize the HR embedding by LPP to increase the information of the LR space by LDA, coupled cross-regression is designed for exploring the relationships between LR/HR data sets {Xl,Xh} and their crossed low-embedding {yh,yl}. With linear assumption, the problem is simplified to find the two projection matrices Al and Ah for LR/HR data sets as follows:
(10)yh⟵XlTAl,yl⟵XhTAh.To solve the solutionAl and Ah, the classical least square method is used for minimizing the cost. Besides, due to limited training samples, the variance of the estimation may be large, and thus the estimation is not reliable. To overcome this problem, penalties are imposed on the norm of Al and Ah as in ridge regression. The regularization parameter α, β≥0 controls the trade-off between the bias and variance of the estimation. Based on these discussions, the objective function is formulated as follows:
(11)J(Al,Ah)=1N∥yh-XlTAl∥2+1N∥yl-XhTAh∥2+α∥Al∥2+β∥Ah∥2.By requiring the derivatives of the objective function with respect toAl and Ah vanish, we get
(12){(XlXlT+NαIl)Al=Xlyh,(XhXhT+NβIh)Ah=Xhyl,⟹{Al=(XlXlT+NαIl)-1Xlyh,Ah=(XhXhT+NβIh)-1Xhyl.Suppose that the Euclidean spaceRn is mapped to a Hilbert space H through a nonlinear mapping function Φ:Rn→H. Let Φ(X) denote the data matrix in the Hilbert space. Here, we replace LR and HR images with their nonlinear feature vectors; that is, xli→Φli=Φ(xli) and xhi→Φhi=Φ(xhi), which are induced by a kernel function k(·,·); that is, k(xli,xhi)=Φ(xli)TΦ(xhi). Here k(·,·) is the kernel function such as the typical Gaussian kernel k(xli,xhi)=exp(-∥xli-xhi∥2/2σ2). Thus, the objective function J(Al,Ah) can be replaced as follows:
(13)J(Al,Ah)=1N∥yh-Φ(Xl)TAl∥2+1N∥yl-Φ(Xh)TAh∥2+α∥Al∥2+β∥Ah∥2.Equation (12), therefore, can be changed into
(14){(Φ(Xl)Φ(Xl)T+NαIl)Al=Φ(Xl)yh,(Φ(Xh)Φ(Xh)T+NβIh)Ah=Φ(Xh)yl,⟹{Al=(Φ(Xl)Φ(Xl)T+NαIl)-1Φ(Xl)yh,Ah=(Φ(Xh)Φ(Xh)T+NβIh)-1Φ(Xh)yl,
where Il and Ih are the identity matrices with the size of m×m and M×M, respectively, Φ(Xl)=[Φ(xl1),…,Φ(xln)] and Φ(Xh)=[Φ(xh1),…,Φ(xhn)].By using the matrix manipulation in kernel ridge regression [20], we have
(15)(Φ(Xl)Φ(Xl)T+NαIl)-1Φ(Xl)=Φ(Xl)(Φ(Xl)TΦ(Xl)+NαIl)-1,(Φ(Xh)Φ(Xh)T+NβIh)-1Φ(Xh)=Φ(Xh)(Φ(Xh)TΦ(Xh)+NβIh)-1,
and, therefore,
(16)Al=Φ(Xl)(Φ(Xl)TΦ(Xl)+NαIl)-1yh=Φ(Xl)(Kl+NαIl)-1yh,Ah=Φ(Xh)(Φ(Xh)TΦ(Xh)+NβIh)-1yl=Φ(Xh)(Kh+NβIh)-1yl,
where Kli,j=Φ(xli)TΦ(xlj)=k(xli,xlj) and Khi,j=Φ(xhi)TΦ(xhj)=k(xhi,xhj). Naturally, corresponding to d eigenvectors {yhi}i=1d and {yli}i=1d to (5), we can obtain d coupled cross mapping matrices Al={Al1,Al2,…,Ald} and Ah={Ah1,Ah2,…,Ahd} to project LR/HR pairs into a unified discriminative space and thus for classification. It is worth noting that KCCR and CCR in the current version are specifically designed for single resolution case. For practical face recognition applications where the resolution of probe faces is likely to be changed, the two projection matrices for multiple resolutions case, for example, 16×16, 12×12 and 8×8, are needed for handling this problem. However, how to determine variable m in Al is a very difficult problem in this context. One possible solution is to select different Al/Ah pairs according to the nearest resolution. For example, when the probe image has the resolution of 14×14, 16×16 or 12×12 can be used to determine m for constructing coupled mappings. Similarly, 12×12 or 8×8 can be used when the probe resolution is between 12×12 and 8×8.


### 2.4. Algorithm Summarization

Similar to CMs, the proposed KCCR also consists of two main phases, which is summarized in Table1. One is offline training phase, including three parts: learning the two low-embeddings yl and yh, computing the two coupled cross projection matrices Al and Ah and transforming HR gallery images into the unified space. The other is online testing phase, including two parts: transforming LR probe images into the unified space and performing feature matching.Table 1
The KCCR method used for LR FR.
LR/HR training images:Xlt∈ℜm×N and Xht∈ℜM×N
HR gallery images:Xhg∈ℜM×Ng with class labels: cg∈ℜC
LR probe images:Xlp∈ℜm×Np with class labels: cp∈ℜC
Offline training phase:
(1) Learning low embeddings: yl∈ℜN×d and yh∈ℜN×d
(2) Computing kernel coupled cross projection matrices:
Al∈ℜm×d and Ah∈ℜM×d
(3) Transforming HR gallery images:
yhg=Φ(Xhg)TAh
=Φ(Xhg)TΦ(Xh)(Kh+NβIh)-1yl
=kh(Kh+NβIh)-1yl,
wherekhi,j=Φ(xhig)TΦ(xhj)=k(xhig,xhj)
Online testing phase:
(1) Transforming LR probe images:
ylp=Φ(Xlp)TAl
=Φ(Xlp)TΦ(Xl)(Kl+NαIl)-1yh
=kl(Kl+NαIl)-1yh,
wherekli,j=Φ(xlip)TΦ(xlj)=k(xlip,xlj)
(2) Performing feature matching: comparing ylp and yhg by nearest neighbour classifier and obtaining cp from cg


## 2.1. Problem Description

The idea of coupled mappings aims to obtain two projection matricesAh and Al with sizes of m×d and M×d to realize the minimization problem as shown in (1), where xhi and xli represent HR and LR face images, respectively and N is the total number of samples.
(1)J(Ah,Al)=∑i=1N‍∥xhiTAh-xliTAl∥2.CMs model [10] aims to obtain a unified feature space at the pixel or feature level. Therefore, the performance of CMs essentially depends on the contents or features of face images. In other words, CMs model itself does not bring any new information for LR FR. Here, we introduce a low-dimension embedding of X, denoted as y, to transform LR and HR into a low-embedding space based on spectral regression instead of an observing pixel space. Then it will obtain more information about LR samples by exploring the relationships among HR samples and improve the efficiency of CMs model drastically:
(2)XhTAh⟶y⟵XlTAl.


## 2.2. Graph Embedding and Regression Framework

Given a graphG={X,W} with vertex set X={x1,x2,…,xN} and similarity matrix W∈ℜN×N; each vertex xi represents a face image and Wij represents the weight of the edge joining vertices xi and xj. The graph G can then be used for characterizing various statistical or geometric properties of the data set. Therefore, graph embedding [17] is to represent each vertex of the graph as a low-dimensional vector that preserves similarities between the data point pairs, and regression is used for solving the optimization problem of graph embedding, which reduces the time complexity. Based on these points, spectral regression [18] is introduced into CMs, which makes the CMs model more efficient for LR FR.Lety={y1,y2,…,yN}T be the low-dimensional embeddings of the vertex set X, which means if vertices xi and xj are close then yi and yj are also close. The optimal y is given by minimizing
(3)y=argminy∑i,j‍∥yi-yj∥2Wij=argminy2yTLy,
where L=D-W is the graph Laplacian matrix and D is a diagonal matrix with Dii=∑j‍Wij. A constraint yTDy=1 is then imposed for removing the arbitrary scaling factor in the embedding:
(4)y=argminyTDy=1yTLy=argminyTLyyTDy=argmaxyTWyyTDy.The optimaly can be obtained by solving the maximum eigenvalue problem:
(5)Wy=λDy.From the classification perspective, a relationshipf between yi and xi should be introduced, that is, yi=f(xi)=xiTA via a linear function. Equation (4) can be written as
(6)A=argmaxyTWyyTDy=argmaxATXWXTAATXDXTA.The optimalA can be obtained by solving the maximum eigenvalue problem:
(7)XWXTA=λXDXTA.
This framework is called linearization of graph embedding (LGE). With different choices of similarity matrix W, LGE will lead to many popular linear subspace learning methods such as linear discriminant analysis (LDA) [14] and locality preserving projection (LPP) [11]. For LDA and LPP, W is defined as follows.LDA. Suppose the tth class has mt samples:
(8)Wij={1mtifxiandxjbothbelongtothetthclass,0otherwise.LPP. Let Nk(xi) denote the set of k nearest neighbors of xi. 								(9)Wij={exp-∥xi-xj∥2/2σ2ifxi∈Nk(xj)orxj∈Nk(xi),0otherwise.


## 2.3. The Proposed KCCR Method

Inspired by the work of Lei and Li [16] adopting two embeddings to describe heterogeneous face data, we introduce yl and yh to represent the embeddings of LR and HR face data, respectively. In the embedding solution, LDA aims to preserve the global relationships between data points in favor of LR face space mainly containing low-frequency information, while LPP aims to preserve the local relationships between data points in favor of HR face space mostly depending on high-frequency features. Therefore, compared with the representing LR and HR space both by LPP in CLPMs [10] and by LDA in SDA [13], yl and yh are obtained by LDA and LPP, respectively, in our CCR method for making full use of the combination of global and local information in data. Furthermore, in order to utilize the HR embedding by LPP to increase the information of the LR space by LDA, coupled cross-regression is designed for exploring the relationships between LR/HR data sets {Xl,Xh} and their crossed low-embedding {yh,yl}. With linear assumption, the problem is simplified to find the two projection matrices Al and Ah for LR/HR data sets as follows:
(10)yh⟵XlTAl,yl⟵XhTAh.To solve the solutionAl and Ah, the classical least square method is used for minimizing the cost. Besides, due to limited training samples, the variance of the estimation may be large, and thus the estimation is not reliable. To overcome this problem, penalties are imposed on the norm of Al and Ah as in ridge regression. The regularization parameter α, β≥0 controls the trade-off between the bias and variance of the estimation. Based on these discussions, the objective function is formulated as follows:
(11)J(Al,Ah)=1N∥yh-XlTAl∥2+1N∥yl-XhTAh∥2+α∥Al∥2+β∥Ah∥2.By requiring the derivatives of the objective function with respect toAl and Ah vanish, we get
(12){(XlXlT+NαIl)Al=Xlyh,(XhXhT+NβIh)Ah=Xhyl,⟹{Al=(XlXlT+NαIl)-1Xlyh,Ah=(XhXhT+NβIh)-1Xhyl.Suppose that the Euclidean spaceRn is mapped to a Hilbert space H through a nonlinear mapping function Φ:Rn→H. Let Φ(X) denote the data matrix in the Hilbert space. Here, we replace LR and HR images with their nonlinear feature vectors; that is, xli→Φli=Φ(xli) and xhi→Φhi=Φ(xhi), which are induced by a kernel function k(·,·); that is, k(xli,xhi)=Φ(xli)TΦ(xhi). Here k(·,·) is the kernel function such as the typical Gaussian kernel k(xli,xhi)=exp(-∥xli-xhi∥2/2σ2). Thus, the objective function J(Al,Ah) can be replaced as follows:
(13)J(Al,Ah)=1N∥yh-Φ(Xl)TAl∥2+1N∥yl-Φ(Xh)TAh∥2+α∥Al∥2+β∥Ah∥2.Equation (12), therefore, can be changed into
(14){(Φ(Xl)Φ(Xl)T+NαIl)Al=Φ(Xl)yh,(Φ(Xh)Φ(Xh)T+NβIh)Ah=Φ(Xh)yl,⟹{Al=(Φ(Xl)Φ(Xl)T+NαIl)-1Φ(Xl)yh,Ah=(Φ(Xh)Φ(Xh)T+NβIh)-1Φ(Xh)yl,
where Il and Ih are the identity matrices with the size of m×m and M×M, respectively, Φ(Xl)=[Φ(xl1),…,Φ(xln)] and Φ(Xh)=[Φ(xh1),…,Φ(xhn)].By using the matrix manipulation in kernel ridge regression [20], we have
(15)(Φ(Xl)Φ(Xl)T+NαIl)-1Φ(Xl)=Φ(Xl)(Φ(Xl)TΦ(Xl)+NαIl)-1,(Φ(Xh)Φ(Xh)T+NβIh)-1Φ(Xh)=Φ(Xh)(Φ(Xh)TΦ(Xh)+NβIh)-1,
and, therefore,
(16)Al=Φ(Xl)(Φ(Xl)TΦ(Xl)+NαIl)-1yh=Φ(Xl)(Kl+NαIl)-1yh,Ah=Φ(Xh)(Φ(Xh)TΦ(Xh)+NβIh)-1yl=Φ(Xh)(Kh+NβIh)-1yl,
where Kli,j=Φ(xli)TΦ(xlj)=k(xli,xlj) and Khi,j=Φ(xhi)TΦ(xhj)=k(xhi,xhj). Naturally, corresponding to d eigenvectors {yhi}i=1d and {yli}i=1d to (5), we can obtain d coupled cross mapping matrices Al={Al1,Al2,…,Ald} and Ah={Ah1,Ah2,…,Ahd} to project LR/HR pairs into a unified discriminative space and thus for classification. It is worth noting that KCCR and CCR in the current version are specifically designed for single resolution case. For practical face recognition applications where the resolution of probe faces is likely to be changed, the two projection matrices for multiple resolutions case, for example, 16×16, 12×12 and 8×8, are needed for handling this problem. However, how to determine variable m in Al is a very difficult problem in this context. One possible solution is to select different Al/Ah pairs according to the nearest resolution. For example, when the probe image has the resolution of 14×14, 16×16 or 12×12 can be used to determine m for constructing coupled mappings. Similarly, 12×12 or 8×8 can be used when the probe resolution is between 12×12 and 8×8.


## 2.4. Algorithm Summarization

Similar to CMs, the proposed KCCR also consists of two main phases, which is summarized in Table1. One is offline training phase, including three parts: learning the two low-embeddings yl and yh, computing the two coupled cross projection matrices Al and Ah and transforming HR gallery images into the unified space. The other is online testing phase, including two parts: transforming LR probe images into the unified space and performing feature matching.Table 1
The KCCR method used for LR FR.
LR/HR training images:Xlt∈ℜm×N and Xht∈ℜM×N
HR gallery images:Xhg∈ℜM×Ng with class labels: cg∈ℜC
LR probe images:Xlp∈ℜm×Np with class labels: cp∈ℜC
Offline training phase:
(1) Learning low embeddings: yl∈ℜN×d and yh∈ℜN×d
(2) Computing kernel coupled cross projection matrices:
Al∈ℜm×d and Ah∈ℜM×d
(3) Transforming HR gallery images:
yhg=Φ(Xhg)TAh
=Φ(Xhg)TΦ(Xh)(Kh+NβIh)-1yl
=kh(Kh+NβIh)-1yl,
wherekhi,j=Φ(xhig)TΦ(xhj)=k(xhig,xhj)
Online testing phase:
(1) Transforming LR probe images:
ylp=Φ(Xlp)TAl
=Φ(Xlp)TΦ(Xl)(Kl+NαIl)-1yh
=kl(Kl+NαIl)-1yh,
wherekli,j=Φ(xlip)TΦ(xlj)=k(xlip,xlj)
(2) Performing feature matching: comparing ylp and yhg by nearest neighbour classifier and obtaining cp from cg


## 3. Generality Analysis about KCCR

In this section, we present an analysis of generality about KCCR and CCR and their connections to linear graph embedding (LGE) methods and coupled mappings (CMs) models. We divide the baseline methods into four groups: original, kernel, original CMs, and kernel CMs, which are shown in Table2. In the original methods, LDA [14] and LPP [11] are two typical LGE methods, and spectral regression (SR) [18] introduces regression into LGE framework to solve the optimization problem. Obviously, the kernel tricks are induced into LGE and SR methods, that is kernel-based methods, such as kernel LDA [21], kernel LPP [22], and kernel SR [23], respectively.Table 2
Different methods for evaluations.
Original
Kernel
Original CMs
Kernel CMs
LDA
LDA [14]
KDA [21]
SDA [13]
/
LPP
LPP [11]
KLPP [22]
CLPMs [10]
CKE [15]
SR
SR [18]
SRKDA [23]
CCR
KCCRThe former two groups are correspondingly used to describe the relationships between samples in CMs models, and then some representative structure-based LR FR methods are proposed, that is, original CMs and kernel CMs. In the original CMs group, coupled locality preserving mappings (CLPMs) [10] and simultaneous discriminant analysis (SDA) [13] improve CMs based on LPP and LDA, respectively. In this paper, we use SR technique instead of LPP or LDA to describe the relationships and propose coupled cross-regression (CCR) method. The recently proposed coupled kernel embedding (CKE) method [15] and our kernel CCR method introduced the kernel trick into CLPMs and CCR model, respectively, and expanded the ideas of nonlinear dimensionality reduction for LR FR problem in the fourth group. Naturally, SDA method can also be improved by kernel, which is the future work.From the above analyses, we can know that the original version and the kernel one of LGE methods can be successfully embedded into CMs models to discover the relationships between LR and HR feature space. It is worth noting that our KCCR method based on cross-regression and kernel technique shows more efficiency than other baseline methods.


## 4. Experimental Results and Discussions

To validate the effectiveness and efficiency of the proposed method for LR FR,12×12 and 8×8 probe images in FERET [24] and CMU PIE [25] face database are adopted for experiments to compare with the original and kernel linear graph embedding (LGE) methods and the original and kernel coupled mappings (CMs) methods, which are shown in Table 2.


### 4.1. Databases and Settings

The training set of FERET contains 1002 frontal face images from 429 subjects. The experiments are based on the standard gallery (1196 images) and the probe set “fafb” (1195 images). For CMU PIE, 1428 frontal view face images with neutral expression and illumination variations in 68 subjects (21 images per subject) were selected in our experiment. For each subject, 3 images are randomly selected for training and the remaining 18 images for testing. Here, only one image with no flash illumination is taken as gallery, while the probe set contains the images with different illuminations (17 images per subject).One sample in FERET and CMU PIE with the HR size72×72 and 64×64, respectively, and the corresponding LR size 12×12 and 8×8 are shown in Figure 2. In all experiments, HR face images are aligned by the positions of two eyes and normalized to zero mean and unit variance. Then the preprocessed HR face images are synthetically translated by random subpixel amounts, blurred with a Gaussian filter, and down-sampled to generate LR face images, as [5] does.Face images in FERET (first row) and CMU PIE (second row). (a) HR with72×72 (FERET) and 64×64 (CMU PIE). (b) LR with 12×12. (c) LR with 8×8.
(a)
(b)
(c)


### 4.2. Results and Analyses

We evaluate the performance of our KCCR and CCR with some representative LGE methods, specifically, NN-LDA/LPP/SRLDA (LDA [14]/LPP [11]/SRLDA [18] with first restoring the LR probe images by nearest neighbour (NN) interpolation) and HR-LDA (LDA with the HR probe images, denoted as HR in the following sections). Furthermore, the kernel versions of these LGE methods are used for comparison, such as KDA [21], KLPP [22], and SRKDA [23]. Meanwhile, other representative state-of-the-art structure-based methods for LR FR are taken for evaluation, that is, CLPMs [10], SDA [13], CKE [15].From the recognition performances in FERET with the probe size12×12 and 8×8 shown in Figures 3 and 4, respectively, the recognition results of different methods are obviously classified into four levels. That is, HR method and the kernel versions of CMs methods such as KCCR and CKE rank the first level, and the original CMs methods such as CLPMs, SDA, and CCR follow subsequently. Then the kernel versions of LGE methods with LR probe images rank the third. Finally, LGE methods with LR probe images obtain the worst results. This phenomenon is more obvious for 8×8.Figure 3
Cumulative recognition results for FERET database with the probe size12×12.Figure 4
Cumulative recognition results for FERET database with the probe size8×8.For12×12, although all CMs methods obtain relative close performance, our KCCR method achieves the Rank-1 recognition rate of 90.8%, which still outperforms the other kernel CMs method, that is, CKE (90.6%), and CCR (90.5%) is better than other original CMs methods such as CLPMs (89.7%) and SDA (90.2%). In particular, the result of KCCR is even close to HR method (90.9%). On the other hand, the recognition rates of kernel and original LGE methods are shown as follows: KDA (78.6%), KLPP (74.1%), SRKDA (80.3%), LDA (71.7%), LPP (65.2%), and SRLDA (74.6%), respectively. In general, the kernel LGE methods are relatively better than the original ones but inferior to the proposed KCCR and CCR.For8×8, although the performances of all methods more or less decline, our KCCR and CCR methods still achieve 80.2% and 75.9%, which outperform CKE (78.8%), CLPMs (68.7%), and SDA (73.5%), respectively, and the performance gap between them is larger than that in 12×12. It implies that KCCR and CCR have a great potential in solving very LR problem. Compared with CMs methods, the performances of LGE methods, that is, KDA (57.7%), KLPP (44.1%), SRKDA (60.3%), LDA (44.9%), and SRLDA (50.4%), are degraded as a result of LR, especially LPP which only achieves the accuracy of 27.8%. Therefore, our KCCR and CCR methods are competitive for LR FR task.Furthermore, Figures5 and 6 show the recognition performances in CMU PIE with the probe size 12×12 and 8×8, respectively. The results of different methods are similar to those in FERET. That is, our KCCR & CCR method still outperforms the baseline methods, though the performances of all the methods are slightly degraded by different illumination variations involved in CMU PIE. However, the baseline methods are affected much more as the resolution declines.Figure 5
Cumulative recognition results for CMU PIE database with the probe size12×12.Figure 6
Cumulative recognition results for CMU PIE database with the probe size8×8.


### 4.3. Model Selections

Theα, β≥0 are two essential parameters in our CCR method which control the smoothness of the estimator under LR and HR cases, respectively. When the sample vectors are linearly independent, CCR provides the same solution as the coupled cross version of LGE as α, β decrease to zero. Also the relationships between α and β determine the performance of the model to some extent. In this subsection, we try to examine the impact of the two parameters on the performance of CCR.In experiments, we find that the smoothness parameters mainly depend on different resolutions. For example, CCR obtains the best performance asα, β are set to 0.001 and 0.01, respectively, at the resolution of 8×8, while α=0.005 and β=0.01 at 12×12. Obviously, β≥α is also a possible condition to guarantee that HR samples can provide more information for LR classification in our CCR model. Therefore, we take the performance of CCR as a function of β/α under different resolutions, which is shown in Figure 7. For convenience, the x-axis is plotted as τ/(1+τ) (τ denotes β/α) which is strictly in the interval [0.5,1]. It is easy to see that CCR can achieve significantly better performance than CLPMs over a large range of τ especially at the resolution of 8×8, which further shows the potential of our CCR method in solving very LR problem. Thus, the parameter selection is not a very crucial problem in our model. The selection of α, β in KCCR model shows similar property to CCR, although they are slightly different. Here, we empirically set α, β as 0.0001, 0.001 at the resolution of 8×8, and 0.0005, 0.001 at 12×12.Figure 7
Model selections for KCCR and CCR. The curve shows the recognition rates of CCR with respect toτ/(1+τ) (τ denotes β/α) with two different resolutions 12×12 (blue line) and 8×8 (red line). The two solid lines show the recognition rates of CLPMs.In addition, how to select appropriate kernels for LR face data is a more important problem in the KCCR, which is still an unsolved problem without any selection criteria in theory for all kernel-based methods. In this paper, Gaussian kernel is selected for building kernel representation for fair comparisons in previous experiments. Empirical analysis shows that kernel-based methods are usually sensitive to the selection of the hyperparameters, that is, the width of Gaussian kernelσ. Thus, finding the hyperparameters with a good generalization performance is crucial for a successful application. In our experiments, we adopt the same strategy used in [17] to select the optimal kernel parameter. The parameter σ is set as σ=2(n-10)σ0, n=0,1,…,20, where σ0 is the standard deviation of the training samples. The best result is selected from the 21 configurations by cross-validation. The details can be referred as in [17]. However, it is unclear how to choose the optimal σ, which is still a future work for kernel-based models effectively used in LR FR applications.


### 4.4. Time Complexity Analyses

The average time of each method for recognizing per face images on CPU with 2.33 GHz is shown in Table3. The properties of time complexity with 12×12 and 8×8 are similar. Here, we just give some analyses with 12×12. Although the time requirement of the original CMs methods (with O((M+m)3) time complexity) is generally higher than the original LGE methods (with O(MN2+N3) time complexity), compared with other CMs methods such as CLPMs and SDA, the speed of our CCR method (with O((M+m)N) time complexity) is relatively close to SRLDA and even faster than LDA and LPP. With the introduction of kernel trick, the time complexity (O(MN2)) of kernel LGE method increases slightly compared with the original ones. The same situation occurs at CKE and KCCR with the time complexity of O((M+m)N2). However, our KCCR combining with the regression framework for LR FR task shows more efficiency than CKE or other baseline methods except for SRLDA and SRKDA.Table 3
Time complexity of different methods.
Database
FERET(s)
CMU PIE(s)
LDA
0.142
0.122
LPP
0.161
0.134
SRLDA
0.034
0.028
CLPMs
0.586
0.513
SDA
0.604
0.525
CCR
0.098
0.084
KDA
0.452
0.334
KLPP
0.552
0.382
SRKDA
0.086
0.058
CKE
0.648
0.422
KCCR
0.171
0.139


## 4.1. Databases and Settings

The training set of FERET contains 1002 frontal face images from 429 subjects. The experiments are based on the standard gallery (1196 images) and the probe set “fafb” (1195 images). For CMU PIE, 1428 frontal view face images with neutral expression and illumination variations in 68 subjects (21 images per subject) were selected in our experiment. For each subject, 3 images are randomly selected for training and the remaining 18 images for testing. Here, only one image with no flash illumination is taken as gallery, while the probe set contains the images with different illuminations (17 images per subject).One sample in FERET and CMU PIE with the HR size72×72 and 64×64, respectively, and the corresponding LR size 12×12 and 8×8 are shown in Figure 2. In all experiments, HR face images are aligned by the positions of two eyes and normalized to zero mean and unit variance. Then the preprocessed HR face images are synthetically translated by random subpixel amounts, blurred with a Gaussian filter, and down-sampled to generate LR face images, as [5] does.Face images in FERET (first row) and CMU PIE (second row). (a) HR with72×72 (FERET) and 64×64 (CMU PIE). (b) LR with 12×12. (c) LR with 8×8.
(a)
(b)
(c)


## 4.2. Results and Analyses

We evaluate the performance of our KCCR and CCR with some representative LGE methods, specifically, NN-LDA/LPP/SRLDA (LDA [14]/LPP [11]/SRLDA [18] with first restoring the LR probe images by nearest neighbour (NN) interpolation) and HR-LDA (LDA with the HR probe images, denoted as HR in the following sections). Furthermore, the kernel versions of these LGE methods are used for comparison, such as KDA [21], KLPP [22], and SRKDA [23]. Meanwhile, other representative state-of-the-art structure-based methods for LR FR are taken for evaluation, that is, CLPMs [10], SDA [13], CKE [15].From the recognition performances in FERET with the probe size12×12 and 8×8 shown in Figures 3 and 4, respectively, the recognition results of different methods are obviously classified into four levels. That is, HR method and the kernel versions of CMs methods such as KCCR and CKE rank the first level, and the original CMs methods such as CLPMs, SDA, and CCR follow subsequently. Then the kernel versions of LGE methods with LR probe images rank the third. Finally, LGE methods with LR probe images obtain the worst results. This phenomenon is more obvious for 8×8.Figure 3
Cumulative recognition results for FERET database with the probe size12×12.Figure 4
Cumulative recognition results for FERET database with the probe size8×8.For12×12, although all CMs methods obtain relative close performance, our KCCR method achieves the Rank-1 recognition rate of 90.8%, which still outperforms the other kernel CMs method, that is, CKE (90.6%), and CCR (90.5%) is better than other original CMs methods such as CLPMs (89.7%) and SDA (90.2%). In particular, the result of KCCR is even close to HR method (90.9%). On the other hand, the recognition rates of kernel and original LGE methods are shown as follows: KDA (78.6%), KLPP (74.1%), SRKDA (80.3%), LDA (71.7%), LPP (65.2%), and SRLDA (74.6%), respectively. In general, the kernel LGE methods are relatively better than the original ones but inferior to the proposed KCCR and CCR.For8×8, although the performances of all methods more or less decline, our KCCR and CCR methods still achieve 80.2% and 75.9%, which outperform CKE (78.8%), CLPMs (68.7%), and SDA (73.5%), respectively, and the performance gap between them is larger than that in 12×12. It implies that KCCR and CCR have a great potential in solving very LR problem. Compared with CMs methods, the performances of LGE methods, that is, KDA (57.7%), KLPP (44.1%), SRKDA (60.3%), LDA (44.9%), and SRLDA (50.4%), are degraded as a result of LR, especially LPP which only achieves the accuracy of 27.8%. Therefore, our KCCR and CCR methods are competitive for LR FR task.Furthermore, Figures5 and 6 show the recognition performances in CMU PIE with the probe size 12×12 and 8×8, respectively. The results of different methods are similar to those in FERET. That is, our KCCR & CCR method still outperforms the baseline methods, though the performances of all the methods are slightly degraded by different illumination variations involved in CMU PIE. However, the baseline methods are affected much more as the resolution declines.Figure 5
Cumulative recognition results for CMU PIE database with the probe size12×12.Figure 6
Cumulative recognition results for CMU PIE database with the probe size8×8.


## 4.3. Model Selections

Theα, β≥0 are two essential parameters in our CCR method which control the smoothness of the estimator under LR and HR cases, respectively. When the sample vectors are linearly independent, CCR provides the same solution as the coupled cross version of LGE as α, β decrease to zero. Also the relationships between α and β determine the performance of the model to some extent. In this subsection, we try to examine the impact of the two parameters on the performance of CCR.In experiments, we find that the smoothness parameters mainly depend on different resolutions. For example, CCR obtains the best performance asα, β are set to 0.001 and 0.01, respectively, at the resolution of 8×8, while α=0.005 and β=0.01 at 12×12. Obviously, β≥α is also a possible condition to guarantee that HR samples can provide more information for LR classification in our CCR model. Therefore, we take the performance of CCR as a function of β/α under different resolutions, which is shown in Figure 7. For convenience, the x-axis is plotted as τ/(1+τ) (τ denotes β/α) which is strictly in the interval [0.5,1]. It is easy to see that CCR can achieve significantly better performance than CLPMs over a large range of τ especially at the resolution of 8×8, which further shows the potential of our CCR method in solving very LR problem. Thus, the parameter selection is not a very crucial problem in our model. The selection of α, β in KCCR model shows similar property to CCR, although they are slightly different. Here, we empirically set α, β as 0.0001, 0.001 at the resolution of 8×8, and 0.0005, 0.001 at 12×12.Figure 7
Model selections for KCCR and CCR. The curve shows the recognition rates of CCR with respect toτ/(1+τ) (τ denotes β/α) with two different resolutions 12×12 (blue line) and 8×8 (red line). The two solid lines show the recognition rates of CLPMs.In addition, how to select appropriate kernels for LR face data is a more important problem in the KCCR, which is still an unsolved problem without any selection criteria in theory for all kernel-based methods. In this paper, Gaussian kernel is selected for building kernel representation for fair comparisons in previous experiments. Empirical analysis shows that kernel-based methods are usually sensitive to the selection of the hyperparameters, that is, the width of Gaussian kernelσ. Thus, finding the hyperparameters with a good generalization performance is crucial for a successful application. In our experiments, we adopt the same strategy used in [17] to select the optimal kernel parameter. The parameter σ is set as σ=2(n-10)σ0, n=0,1,…,20, where σ0 is the standard deviation of the training samples. The best result is selected from the 21 configurations by cross-validation. The details can be referred as in [17]. However, it is unclear how to choose the optimal σ, which is still a future work for kernel-based models effectively used in LR FR applications.


## 4.4. Time Complexity Analyses

The average time of each method for recognizing per face images on CPU with 2.33 GHz is shown in Table3. The properties of time complexity with 12×12 and 8×8 are similar. Here, we just give some analyses with 12×12. Although the time requirement of the original CMs methods (with O((M+m)3) time complexity) is generally higher than the original LGE methods (with O(MN2+N3) time complexity), compared with other CMs methods such as CLPMs and SDA, the speed of our CCR method (with O((M+m)N) time complexity) is relatively close to SRLDA and even faster than LDA and LPP. With the introduction of kernel trick, the time complexity (O(MN2)) of kernel LGE method increases slightly compared with the original ones. The same situation occurs at CKE and KCCR with the time complexity of O((M+m)N2). However, our KCCR combining with the regression framework for LR FR task shows more efficiency than CKE or other baseline methods except for SRLDA and SRKDA.Table 3
Time complexity of different methods.
Database
FERET(s)
CMU PIE(s)
LDA
0.142
0.122
LPP
0.161
0.134
SRLDA
0.034
0.028
CLPMs
0.586
0.513
SDA
0.604
0.525
CCR
0.098
0.084
KDA
0.452
0.334
KLPP
0.552
0.382
SRKDA
0.086
0.058
CKE
0.648
0.422
KCCR
0.171
0.139


## 5. Conclusions

In this paper, a novel structure-based method called kernel coupled cross-regression (KCCR) is proposed for LR FR. Our method combines coupled mappings model and graph embedding analysis to describe the relationships between LR and HR in low-embedding space. Kernel trick is further adopted for describing these relationships in an infinite dimensional and nonlinear space. Moreover, cross-regression is developed to fully utilize the HR embedding to increase the information of the LR space. As a result, the proposed KCCR method is more discriminative and faster. It outperforms LGE methods with LR probe images, the kernel versions of LGE methods, and other existing structure-based methods such as CLPMs, SDA, and CKE, especially in time complexity.



---

*Source: 153790-2013-06-13.xml*