Automatic face recognition by reasoning about similarity of facial images is a hard task in computer vision. Strong local variations in expressions and illuminations, global changes in pose, temporal changes, partial occlusions, as well as affine transformations stemming from automatic face detection all contribute to rich intra-class variability which is difficult to discriminate from inter-class dissimilarity. In addition, often only a limited number of images per individual are provided as references. In the most extreme case, only one frontal image (mughot) is available, which makes it difficult to learn a model capturing the natural variability. In order to cope with these problems we propose novel image warping algorithms which do not build any specific facial models, but directly encode a deformation-invariant dissimilarity measure used within a nearest neighbour classification framework. We systematically analyze the strengths and weaknesses of image warping algorithms and compare the methods regarding the computational complexity and degree of image structure preserved during optimization.
Our face recognition framework is based on two-dimensional image warping (2DW) which is used to register a reference image to the test image. The registration is done by minimizing the energy function which consists of the unary term measuring the compatibility between the features at corresponding pixel positions, and pairwise term defining first-order geometrical dependencies and constraints between neighbouring positions. As finding the global minimum of the energy is an NP-complete problem, we propose several relaxations which make the registration efficient while also maintaining geometrical image structure due to encoded structure-preserving constraints.
Constrained Tree-based Optimization 
In this work we propose an improvement of tree-serial dynamic programming (TSDP) which relaxes 2DW by representing the two-dimensional pixel grid as a series of individual pixel neighbourhood trees and optimizes each tree independently from the others. We improve the TSDP method by modifying the constraints imposed during image warping. In particular, we introduce structure-preserving geometric constraints which make the optimization much more efficient while also increasing the smoothness of image warping. In addition, we discard the hard position constraints, which allows to compensate for larger discrepancies between reference and test images. As can be seen from the figure below, the image registered by our method (b, bottom row) is visually much smoother compared to the result obtained by TSDP (b, top row) due to imposed structural constraints and increased flexibility of image warping. We also show that our method outperforms the original TSDP on well-known AR-Face and CMU-PIE face recognition benchmarks and achieves superior performance to the state-of-the-art approaches.
Below we provide example results of occlusion handling. Shown is 2D warping of reference to test image without (top row) and with (bottom row) occlusion handling on an example from the AR-Face occlusion database. (b) is the aligned reference, (c) is the deformation grid and (d) is the local similarity map between the test and the aligned reference image. Dark blue pixels denote low similarity and red pixels denote high similarity.
Extended Pseudo Two-dimensional Image Warping 
We propose an extension of Pseudo Two-dimensional Image Warping (P2DW) which relaxes the original 2DW problem by decoupling the horizontal and vertical displacements and allowing additional flexibility during image registration. Similarly to P2DW we first use dynamic programming to first match test and reference image columnwise and then align entire columns during the second round of optimization. However, our method allows additional deviations from column centers by relaxing geometrical constraints, which results into a more flexible registration. Figure below shows sample result by our method and comparison to P2DW. It can be seen that our approach produces much smoother result (b, bottom row) due to relaxed geometrical constraints. Quantitative results on AR-Face and CMU-PIE face recognition benchmarks show superior performance of our image warping algorithm.
Analysis of Image Warping Algorithms 
We systematically analyze the strengths and weaknesses of image warping algorithms on the tasks of face recognition in highly variable domains. We arrange the approaches into a global hierarchy of groups of methods w.r.t. neighbouring dependencies which hold during optimization. Schematic visualization of warping methods is provided below, where the last row shows dependencies between pixels by mutual color. In Zero-Order Warping (ZOW), all pixels are optimized independently. For Pseudo Two-dimensional (P2D)-like methods, pixel displacements are dependent within each column, and an additional Hidden Markov Model (HMM) (green) optimizes column alignments. In Tree-Serial Dynamic Programming (TSDP), each column is optimized independently but estimates of horizontal branches are taken into account. Finally, graph-based methods try to optimize all displacements simultaneously.
We show that the increasing number of neighbourhood relations facilitates the computation of smoother image warpings and leads to more accurate face recognition results. Compared to other warping algorithms, it becomes clear that using stronger smoothness paradigms is more reliable when trying to cope with the variability induced by projections of 3D transformations. Our findings indicate that the approaches optimizing all dependencies simultaneously perform the best while being almost as efficient as more simple heuristics.
Visual comparison of image warping results
 Warp that Smile on your Face: Optimal and Smooth Deformations for Face Recognition, T. Gass, L. Pishchulin, P. Dreuw and H. Ney, IEEE International Conference on Automatic Face and Gesture Recognition (FG), March, (2011)
 The Fast and the Flexible: Extended Pseudo Two-Dimensional Warping for Face Recognition, L. Pishchulin, T. Gass, P. Dreuw and H. Ney, Iberian Conference on Pattern Recognition and Image Analysis (IbPRIA), June, (2011)
 Image warping for face recognition: From local optimality towards global optimization, L. Pishchulin, T. Gass, P. Dreuw and H. Ney, Pattern Recognition, Volume 45, Number 9, p.3131-3140, (2012)