The ability to record, store and analyse images of faces economically, rapidly and on a vast scale brings people’s attention to privacy. The current privacy protection approaches for face images are mainly through masking, blurring or black-out which, however, removes data utilities along with the identifying information. As a result, these ad hoc methods are hardly used for data publishing or in further researches. The technique of de-identification attempts to remove identifying information from a dataset while preserving the data utility as much as possible. The research on de-identify structured data has been established while it remains a challenge to de-identify unstructured data such as face data in images and videos. The k-Same face de-identification was the first method that attempted to use an established de-identification theory, k-anonymity, to de-identify a face image dataset. The k-Same face de-identification is also the starting point of this thesis. Re-identification risk and data utility are two incompatible aspects in face de-identification. The focus of this thesis is to improve the privacy protection performance of a face de-identification system while providing data utility preserving solutions for different application scenarios. This thesis first proposes the k-Same furthest face de-identification method which introduces the wrong-map protection to the k-Same-M face de-identification, where the identity loss is maximised by replacing an original face with the face that has the least similarity to it. The data utility of face images has been considered from two aspects in this thesis, the dataset-wise data utility such as data distribution of the data set and the individual-wise data utility such as the facial expression in an individual image. With the aim to preserve the diversity of a face image dataset, the k-Diff-furthest face de-identification method is proposed, which extends the k-Same-furthest method and can provide the wrong-map protection. With respect to the data utility of an individual face image, the visual quality and the preservation of facial expression are discussed in this thesis. A method to merge the isolated de-identified face region and its original image background is presented. The described method can increase the visual quality of a de-identified face image in terms of fidelity and intelligibility. A novel solution to preserving facial expressions in de-identified face images is presented, which can preserve not only the category of facial expressions but also the intensity of face Action Units. Finally, an integration of the Active Appearance Model (AAM) and Generative Adversarial Network (GAN) is presented, which achieves the synthesis of realistic face images with shallow neural network architectures.