Real-time facial shape recovery from a single image under general, unknown lighting by rank relaxation

• We propose a real-time facial shape recovery algorithm from a single image.
• An input image is a frontal face under a general, unknown lighting with cast shadow.
• A bilinear model is linearized by rank relaxation to reduce the time complexity.
• Faces are accurately reconstructed even if there is a heavy shadow.
• The method takes average 45 ms to reconstruct a 3D face.

Statistical shape from shading under general light conditions can be thought of as a parameter-fitting problem to a bilinear model. Here, the parameters are personal attributes and light conditions. Parameters of a bilinear model are usually estimated using the alternating least squares method with a computational complexity of O((ns+nϕ)2np)O((ns+nϕ)2np), where ns,nϕ, and npnp are the dimensions of the light conditions, personal attributes, and face image features, respectively, for each iteration. In this paper, we propose an alternative algorithm with a computational complexity of O(nsnϕ)O(nsnϕ) for each iteration. Only the initial step requires a computational complexity of O(nsnϕnp)O(nsnϕnp). This can be accomplished by reformulating the problem to that of a linear least squares problem, with a search space limited to a set of rank-one matrices. The rank-one condition is relaxed to obtain a possibly full-rank matrix. The algorithm then finds the best rank-one approximation of that matrix. By the Eckart–Young theorem, the best approximation is the outer product of the left and right singular vectors corresponding to the largest singular value. Since only this pair of singular vectors is needed, it is better to use the power iteration method, which has a computational complexity of O(nsnϕ)O(nsnϕ) for each iteration, than calculating the full singular value decomposition. The proposed method provides accurate reconstruction results and takes approximately 45 ms on a PC, which is adequate for real-time applications.