Genetic algorithms were invented in the 1950s as a result of the first experiments to simulate natural evolution on a computer. Since then, they have been used to solve a wide variety of optimization problems, where gradient methods for some reason are not suitable. The biological component of genetic algorithms here has a very simplified form, and in this case we are talking more about following the general idea of ​​evolutionary selection than its full-fledged modeling. Nevertheless, sometimes the results of GA can be interpreted in a biological sense. In our article, we talk about the experience of using genetic algorithms for the face recognition task in order to obtain “regions of importance” of a person. The application of this approach made it possible to increase the recognition accuracy of our face recognition system by an average of 20%.

Existing face recognition approaches

Historically, after about 20 years of intensive research in the field of computer face recognition, in the early 2000s, two basic groups of face comparison methods were distinguished: “holistic approaches”, “holistic approaches” (or “global approaches”) and “feature approaches ”,“ Feature-based approaches ”(or“ structural approaches ”) [1]. In the first case, faces are considered as whole images that are compared among themselves. In the second case, local signs, such as information about the absolute and relative position of the eyes, nose, mouth, etc., are distinguished from the face image. Both groups have their drawbacks: holistic approaches have generally shown greater reliability in close to ideal recognition conditions compared with characteristic approaches, however, characteristic approaches have proven themselves better in situations when parts of the face are not visible for some reason (for example, covered by clothing items or glasses). Applying purely SIFT-like methods for extracting traits in their pure form to the face recognition task gives unsatisfactory results, since there are usually too few “corners” on a person’s face for which key points are determined. Algorithms of the dense-SIFT type, with the calculation of features using a given lattice of key points, although they demonstrate good recognition quality [2], are not always convenient for practical use due to the large size of feature vectors and the long time required to calculate them. Under these conditions, in recent years, a group of methods that can conditionally be called “modular approaches” [4–9], including the method, has gained popularity. covered with clothing items or glasses). Applying purely SIFT-like methods for extracting traits in their pure form to the face recognition task gives unsatisfactory results, since there are usually too few “corners” on a person’s face for which key points are determined. Algorithms of the dense-SIFT type, with the calculation of features using a given lattice of key points, although they demonstrate good recognition quality [2], are not always convenient for practical use due to the large size of feature vectors and the long time required to calculate them. Under these conditions, in recent years, a group of methods that can conditionally be called “modular approaches” [4–9], including the method, has gained popularity. covered with clothing items or glasses). Applying purely SIFT-like methods for extracting traits in their pure form to the face recognition task gives unsatisfactory results, since there are usually too few “corners” on a person’s face for which key points are determined. Algorithms of the dense-SIFT type, with the calculation of features using a given lattice of key points, although they demonstrate good recognition quality [2], are not always convenient for practical use due to the large size of feature vectors and the long time required to calculate them. Under these conditions, in recent years, a group of methods that can conditionally be called “modular approaches” [4–9], including the method, has gained popularity. Applying purely SIFT-like methods for extracting traits in their pure form to the face recognition task gives unsatisfactory results, since there are usually too few “corners” on a person’s face for which key points are determined. Algorithms of the dense-SIFT type, with the calculation of features using a given lattice of key points, although they demonstrate good recognition quality [2], are not always convenient for practical use due to the large size of feature vectors and the long time required to calculate them. Under these conditions, in recent years, a group of methods that can conditionally be called “modular approaches” [4–9], including the method, has gained popularity. Applying purely SIFT-like methods for extracting traits in their pure form to the face recognition task gives unsatisfactory results, since there are usually too few “corners” on a person’s face for which key points are determined. Algorithms of the dense-SIFT type, with the calculation of features using a given lattice of key points, although they demonstrate good recognition quality [2], are not always convenient for practical use due to the large size of feature vectors and the long time required to calculate them. Under these conditions, in recent years, a group of methods that can conditionally be called “modular approaches” [4–9], including the method, has gained popularity. for which key points are defined. Algorithms of the dense-SIFT type, with the calculation of features using a given lattice of key points, although they demonstrate good recognition quality [2], are not always convenient for practical use due to the large size of feature vectors and the long time required to calculate them. Under these conditions, in recent years, a group of methods that can conditionally be called “modular approaches” [4–9], including the method, has gained popularity. for which key points are defined. Algorithms of the dense-SIFT type, with the calculation of features using a given lattice of key points, although they demonstrate good recognition quality [2], are not always convenient for practical use due to the large size of feature vectors and the long time required to calculate them. Under these conditions, in recent years, a group of methods that can conditionally be called “modular approaches” [4–9], including the method, has gained popularity.local binary patterns .

Cluster approaches for comparing faces

The essence of cluster approaches for comparing faces consists in dividing the face image into a number of sections, for each of which you can apply a holistic approach and compare them in pairs, i.e. regardless of other sites. In this case, it can be hoped that if some pairs of sections of the compared images do not coincide due to the above-mentioned interfering factors such as shadows and overlaps, the remaining pairs of sections will provide the necessary degree of mutual correlation, which will be sufficient for the correct final solution to match / mismatch .
As a holistic approach, the principal component method [4], moment invariants [5], local binary patterns can be used(LBS) [6, 7], Gabor wavelets [8], Haar wavelets [9] and other methods. In our project, we use the combined LBSh approach [7] and the pseudo-Zernike moments [5].

Matrix of importance of facial areas

In our face recognition system, implemented in the ZZPhoto application, we take into account the unequal importance of different parts of the face for comparing faces by dividing the face image into areas (Fig. 1) and assigning weights to each of them , the weights take one of four discrete values , .



Figure 1. a) The division of the face into 8x8 = 64 disjoint square plots. b) Values ​​of the weight matrix of the importance of the face sections.

The larger the weight value, the greater the influence of the coincidence / mismatch of the corresponding part of the face on the final decision of the comparison algorithm. In fig. 6 more important areas of the face are highlighted in a redder tint.
Using exhaustive search to determine the optimal matrix of importance weights is difficult in practice, since we would have to considervariants of the matrix of weights (here stands the power of 32, not 64, since we use the symmetric horizontally matrix of weights due to, in general, the symmetrical nature of the person’s face). Therefore, to search for a better matrix, it is necessary to use a more intelligent search algorithm. As a result, we settled on genetic algorithms (GA).

Genetic Algorithms

Genetic AlgorithmsThey have proven themselves well as a means of global optimization when gradient optimization methods cannot be applied. Their advantages are that a differentiable model of the optimized object is not required, as well as a lower risk of falling into a local minimum. Their minus is a significantly lower convergence rate compared to gradient methods. The essence of genetic algorithms is to simulate the process of natural selection as a means of finding the optimal solution, using the mechanism of transmission of hereditary information from generation to generation through genes. As a measure of the success of the “life” of the body, the target optimization function is used, which in terms of GA is called the “fitness function”. Before describing the operation of the GA algorithm for our case, we list the list of concepts with which we operate and briefly explain their meaning.

Fitness function - determines the quality of the “life” of an individual in a generation (population). The role of the fitness function in our case is performed by a program experiment on face recognition using our algorithm for comparing faces on a given base of face images. The result of the fitness function is the percentage of correctly recognized faces for a particular chromosome.

Chromosome - determines the individual in the population, in fact, this is our matrix of the importance of the areas of the face. Each chromosome is a candidate for solving the target problem.

Fitness is the quality of life of an individual encoded by a chromosome. It is the result of applying fitness function to the chromosome. In our case, this is the accuracy of classification with a given matrix of weights of the importance of facial areas.

Population- a set of 100 different chromosomes, genes are encoded with values ​​from an acceptable set of {0,1,2,3}. Values ​​can be either completely random (the first population) or be a product of the evolutionary process (crosses and mutations).

Crossing (reproduction) is the procedure for obtaining a new chromosome. The new chromosome of the "child" is formed from parts of the chromosomes of the "parents". The crossing point is selected using a random number generator each time for each pair of parents. Parents are selected by selection.

Selection- the procedure for selecting the “parents” chromosomes from which chromosomes will be formed for a new population. Selection is designed to increase the likelihood of chromosomes entering many “parents” who have shown better fitness in the latter population at the moment. We use a stochastic approach, the probability of choosing the i-th chromosome:



where: .

Mutation - the procedure of replacing one chromosome value with a random value after crossing, the probability of mutation is predetermined.

Elitism is a feature of the formation of a new generation, the essence of which lies in the fact that the best parental individuals are directly included in the new generation. Their number can be from 1 or more.

Description of the experiment

1. An initial population of 100 chromosomes is generated, the values ​​of which are filled with random values.
2. A fitness function is applied to each chromosome of the population, which determines the fitness value for the chromosomes.
3. With the help of selection, the most adapted chromosomes are selected, which form many “parents”.
4. Random pairs are selected from the set of parents, crosses are performed, and chromosomes of the “children” are formed.
5. The mutation procedure is applied to the chromosomes of “children”.
6. The resulting chromosomes form a new population, to which steps 2) - 5) are performed.
7. If improvement does not occur for a long time (say, 30 populations or more), a halt occurs. The chromosome that has shown the best fitness is the solution to the problem.

The experiments

The following biological interpretation can be given for our experiments: biological individuals who pay attention to the “wrong” areas of the face die out; those individuals who have good recognition ability survive and give more numerous offspring.
The first experiment was conducted on the famous Color FERET facial image database [11]. Images of the faces of 100 people photographed during several sessions were selected from this database, 5 examples of faces per person. Examples of images from Color FERET Face Database are shown in Fig. 2. This database contains images of faces obtained over several photo sessions in different lighting conditions and with different facial expressions. The actual facial sections were selected automatically by the face detection module based on the Viola-Jones face detector, which is part of OpenCV. It additionally includes the normalization of the image in size, position and angle of rotation in the frontal plane (for which the face, nose and mouth are additionally searched).



Fig. 2. Examples of faces from the Color FERET Face Database.

The essence of the experiment is to classify individuals in the “Single face Per Person” mode. The recognition algorithm receives one photo of the face of each person from the database as an input, after which it compares the selected face with all its other and other people's face images in the database and builds the dependence of authentication errors of the 1st and 2nd kind on the authentication threshold value, i.e. . False Accept Rate (FAR) and False Reject Rate (FRR) dependency curves. FAR error corresponds to the situation of “false access”, when the system falsely “recognizes the stranger as his own”; FRR error is a “missed target” when the system falsely “does not recognize its own”. According to the conditions of our applied problem, the FRR value was fixed should not exceed 20%. According to the results of the experiments, a total recognition error is formed on all faces, in the role of which the error HTER (Half Total Error Rate) is used, i.e. access error equal to the average FAR and FRR.

For the Color FERET Face Database, the FAR recognition error with unit weights was 21% (i.e. 79% of correct answers), which is close to the modern state-of-art level of face recognition methods. After applying genetic algorithms to optimize the weight matrix of the importance of facial areas (Fig. 3), the FAR recognition error was reduced to 12%, i.e. reduce by almost 2 times compared to the original.


Fig. 3. The result of applying genetic algorithms to optimize the weight matrix of the importance of facial areas based on Color FERET.

To organize an experiment with different races, as well as being closer to real conditions, we have collected our own ZZWolf ABC Face Database, which includes faces of people of different races (ABC = Asian, Black, Caucasian). The base of people contains samples of people for three main races, 10 people for 10 people (5 men and 5 women) of each race, photos of people were collected on the Internet, a total of 300 people. These are mainly the faces of famous people (actors and politicians), the pictures were taken with different cameras, at different times (the difference in shooting can be years) and in different lighting conditions.


Fig. 4. Examples of faces from the ZZWolf ABC Face Database. Isolation, normalization and preprocessing of persons was carried out automatically.

As a result, the face recognition error on the new base averaged 37.2%. After applying genetic algorithms, the error was reduced to 32%.


Fig. 5. The result of applying genetic algorithms to optimize the weight matrix of the importance of facial areas based on the ZZWolf ABC Face Database for various races.

Table 1. Recognition results based on ZZWolf ABC Faces

	For asians	For blacks	For whites	Average
Unit weights of importance (all parts of the face are equal)	38.0%	35.3%	38.3%	37.2%
Importance weights optimized by genetic algorithms	34.3%	29.0%	32.8%	32.0%

The resulting optimized matrices of the importance of facial areas are shown in Fig. 6, for different races they differ. Our sample of faces “ZZWolf ABC Face Database” is small in volume, therefore we do not pretend that the experimentally obtained matrices of importance of facial areas for different races are optimal under any conditions and fully correspond to biological facial recognition systems in real people.


Fig. 6. Matrices of importance of sites of faces for different races. The more red the color, the more important it is.

Nevertheless, if we accept the hypothesis that people of different races, when recognizing each other's faces, pay more attention to the areas of the face that are specific to their race and because of this it is difficult for representatives of different races (for example, Europeans and Asians) to recognize each other , then the results can be interpreted as follows: for whites, the area of ​​the eyes is of the greatest importance, for blacks - the area of ​​the nose, and for Asians - the area of ​​the ears and the area of ​​the forehead above the arch arches.

conclusions

The article presents a method for improving the accuracy of the face recognition algorithm, which is used in the ZZPhoto program based on the use of genetic algorithms. Experiments on various face bases show an improvement in the quality of recognition from 20% to 2 times. The method is quite general and can be applied to various cluster face recognition algorithms. The results of experiments on a sample of faces of representatives of different races give interesting results, possibly explaining some natural mechanisms of facial recognition in people.

List of references

1. W. Zhao, R. Chellappa, PJ Phillips, A. Rosenfeld. Face recognition: A literature survey, Journal of ACM Computing Surveys (CSUR), 2003, Volume 35, Issue 4, pp. 399 - 458.
2. P. Dreuw, P. Steingrube, H. Hanselmann, H. Ney. SURF-Face: Face Recognition Under Viewpoint Consistency Constraints // Proceedings British Machine Vision Conference, 2009.
3. R. Gottumukkal, VK Asari. An improved face recognition technique based on modular PCA approach // Pattern Recognition Letters, 2004, Volume 25, Issue 4, pp. 429 - 436.
4. HV Nguyen, L. Bai, L. Shen. Local Gabor Binary Pattern Whitened PCA: A Novel Approach for Face Recognition from Single Image Per Person // Advances in Biometrics. Lecture Notes in Computer Science Volume 5558, 2009, pp. 269 ​​- 278.
5. HR Kanana, K. Faez, Y. Gaob. Face recognition using adaptively weighted patch PZM array from a single exemplar image per person // Pattern Recognition, 2008, Volume 41, Issue 12, pp. 3799 - 3812.
6. S. Nikan, M. Ahmadi. Human face recognition under occlusion using LBP and entropy weighted voting // 2012 21st International Conference on Pattern Recognition (ICPR), 11-15 Nov. 2012, pp. 1699 - 1702.
7. T. Ahonen, A. Hadid, M. Pietikainen. Face Description with Local Binary Patterns: Application to Face Recognition // Pattern Analysis and Machine, 2006, Volume 28, Issue, 12, pp. 2037 - 2041.
8. B. Kepenekci, FB Tek, G. Bozdagi Akar, Occluded face recognition based on Gabor wavelets, ICIP 2002, September 2002, Rochester, NY, MP-P3.10.
9. H.-S. Le, H. Li, Recognizing frontal face images using hidden Markov models with one training image per person, Proceedings of the 17th International Conference on Pattern Recognition (ICPR04), vol. 1, 2004, pp. 318–321.
10. D. Rutkovskaya, M. Pilinsky, L. Rutkovsky. Neural networks, genetic algorithms and fuzzy systems // Transl. from Polish M .: Hotline-Telecom, 2004 - 452 p.
11. www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html
12. www.nist.gov/itl/iad/ig/colorferet.cfm

UPDATE: The names of the races are aligned with the English language Wikipedia.