We present a theory for constructing linear subspace approximations to face-recognition algorithms and empirically demonstrate that a surprisingly diverse set of face-recognition approaches can be approximated well by using a linear model. A linear model, built using a training set of face images, is specified in terms of a linear subspace spanned by, possibly nonorthogonal vectors. We divide the linear transformation used to project face images into this linear subspace into two parts: 1) a rigid transformation obtained through principal component analysis, followed by a nonrigid, affine transformation. The construction of the affine subspace involves embedding of a training set of face images constrained by the distances between them, as computed by the face-recognition algorithm being approximated. We accomplish this embedding by iterative majorization, initialized by classical MDS. Any new face image is projected into this embedded space using an affine transformation. We empirically demonstrate the adequacy of the linear model using six different face-recognition algorithms, spanning template-based and feature-based approaches, with a complete separation of the training and test sets. A subset of the face-recognition grand challenge training set is used to model the algorithms and the performance of the proposed modeling scheme is evaluated on the facial recognition technology (FERET) data set. The experimental results show that the average error in modeling for six algorithms is 6.3% at 0.001 false acceptance rate for the FERET fafb probe set which has 1195 subjects, the most among all of the FERET experiments. The built subspace approximation not only matches the recognition rate for the original approach, but the local manifold structure, as measured by the similarity of identity of nearest neighbors, is also modeled well. We found, on average, 87% similarity of the local neighborhood. We also demonstrate the usefulness of the linear model for algorithm-dependent indexing of face databases and find that it results in more than 20 times reduction in face comparisons for Bayesian, elastic bunch graph matching, and one proprietary algorithm.

Regeneration of templates from match scores has security and privacy implications related to any biometric authentication system. We propose a novel paradigm to reconstruct face templates from match scores using a linear approach. It proceeds by first modeling the behavior of the given face recognition algorithm by an affine transformation. The goal of the modeling is to approximate the distances computed by a face recognition algorithm between two faces by distances between points, representing these faces, in an affine space. Given this space, templates from an independent image set (break-in) are matched only once with the enrolled template of the targeted subject and match scores are recorded. These scores are then used to embed the targeted subject in the approximating affine (non-orthogonal) space. Given the coordinates of the targeted subject in the affine space, the original template of the targeted subject is reconstructed using the inverse of the affine transformation. We demonstrate our ideas using three, fundamentally different, face recognition algorithms: Principal Component Analysis (PCA) with Mahalanobis cosine distance measure, Bayesian intra-extrapersonal classifier (BIC), and a feature-based commercial algorithm. To demonstrate the independence of the break-in set with the gallery set, we select face templates from two different databases: Face Recognition Grand Challenge (FRGC) and Facial Recognition Technology (FERET) Database (FERET). With an operational point set at 1 percent False Acceptance Rate (FAR) and 99 percent True Acceptance Rate (TAR) for 1,196 enrollments (FERET gallery), we show that at most 600 attempts (score computations) are required to achieve a 73 percent chance of breaking in as a randomly chosen target subject for the commercial face recognition system. With similar operational set up, we achieve a 72 percent and 100 percent chance of breaking in for the Bayesian and PCA based face recognition systems, respectively. With three different levels of score quantization, we achieve 69 percent, 68 percent and 49 percent probability of break-in, indicating the robustness of our proposed scheme to score quantization. We also show that the proposed reconstruction scheme has 47 percent more probability of breaking in as a randomly chosen target subject for the commercial system as compared to a hill climbing approach with the same number of attempts. Given that the proposed template reconstruction method uses distinct face templates to reconstruct faces, this work exposes a more severe form of vulnerability than a hill climbing kind of attack where incrementally different versions of the same face are used. Also, the ability of the proposed approach to reconstruct actual face templates of the users increases privacy concerns in biometric systems.