In a world where security issues have been gaining growing importance, face recognition systems have attracted increasing attention in multiple application areas, ranging from forensics and surveillance to commerce and entertainment. To help to understand the landscape and abstraction levels relevant for face recognition systems, face recognition taxonomies allow a deeper dissection and comparison of the existing solutions. This study proposes a new, more encompassing and richer multi-level face recognition taxonomy, facilitating the organisation and categorisation of available and emerging face recognition solutions; this taxonomy may also guide researchers in the development of more efficient face recognition solutions. The proposed multi-level taxonomy considers levels related to the face structure, feature support, and feature extraction approach. Following the proposed taxonomy, a comprehensive survey of representative face recognition solutions is presented. This study concludes with a discussion on current algorithmic and application related challenges, which may define future research directions for face recognition.