What Types of Algorithms Are Used for Facial Interpretation?

Now that we know what constitutes a facial image and how a face can be imaged , we need to know what types of algorithms are used. The algorithms used to match and enroll a face fall into the following categories:

• Eigenface

• Local feature analysis

• Neural network

• Automatic face processing

Eigenface

Eigenface is based on a patented technology from MIT. Eigenface, loosely translated, means "one's own face." The algorithm works from two-dimensional grayscale images. From a grayscale image, an Eigenface is extracted. The face is then mapped to a series of Eigenvectors, which are mathematical properties describing the unique geometry of that particular face, forming the biometric template. The template is then compared to the generated Eigenfaces for comparison. The degree of variance between the template and the reference Eigenfaces determines a match. The lower the variance between the template and the reference Eigenfaces, the greater the likelihood of a match (Figure 6-1).

Figure 6-1. Standard Eigenfaces. (Source: MIT Media Lab, www-white.media.mit.edu.

The Eigenface algorithm is somewhat unique when doing one-to-many match identification. To create the reference template that the live template is compared to, it builds a composite of all enrolled faces. This means that as more faces are added to the database, the reference template is updated. Most Eigenface-based systems with 100 “150 facial images create a reference template that can be used for comparison. ^[1]

^[1] J. Velasco, "Teaching a computer to recognize a friendly face," The New York Times , Oct. 15, 1998, p. G7.

Local Feature Analysis

Local feature analysis was developed by Dr. Joseph Atick, Dr. Paul Griffin, and Dr. Norman Redlich of the Visionics Corporation. Local feature analysis uses the macro features of the face as reference points.

The algorithm first locates the face from its surroundings. The reference points are then located by using the change in shading around each feature. Once a change in shade is found, it is defined as an anchor point. Once all the anchor points are found, the algorithm creates triangles that tie together the anchor points. The angles of the triangles from each anchor point are measured and a 672-bit template is generated. If there is a change in lighting intensity or orientation, this could cause the shading on the face to change. This change in shading would lead to the creation of a different template.

When a live facial scan is done, a new template is created using local feature analysis; this new template is compared against the reference templates. The higher the percentage of the comparison, the greater the likelihood that the live template and the reference template will match.

Figure 6-2 shows a face to which local feature analysis has been applied. First, the face is distinguished from the background, then local feature analysis is performed. The last image shows a scaled-up image of local feature analysis (the difference in shading is apparent).

Figure 6-2. Application of local feature analysis.

Neural Network

The neural network algorithm is patterned after the synapses and neurons in the human brain. By creating an artificial neural network (ANN), problems can be solved based on training the network. To train the network, a series of captured faces are fed into the network. Each face has its macro features identified. In addition to having faces with identified features, other random images are added to the training set. The random images added to the training set cause the ANN to learn what does not constitute a face. Then, as the ANN begins to learn, faces are entered into the system that do not have their macro features identified. The unidentified faces that fail to match are re-entered into the system with identified features.

The ANN is made up of the following parts :

• Face detection and framing

• ANN input level

• Receptive fields

• Hidden units

• Output

Each part of a basic ANN is discussed below.

Face detection and framing

As a face is imaged, it needs to be separated from its background. Once the face is isolated from the background, it is framed and transformed to the appropriate size . It is then ready for the ANN input level.

ANN input level

Once the face is the appropriate size, the face image is put into the ANN input level. At this point, the face image is converted into pixels to meet the size specifications of the ANN input. If the input buffer is 20 pixels by 20 pixels, and the image is the same size, then each pixel maps directly to an input neuron .

Receptive fields

When the image is translated into the neurons that make up the input level, the input neurons are mapped to receptive fields. The mapping of the receptive fields is normally chosen to reflect the general characteristics of the face. For example, receptive neurons may be grouped so that the input neurons can be equally divided into squares and mapped to a single neuron. This would be a large square area for mapping where general face features can be isolated. From here, additional receptive neurons may take varying degrees and shapes of input neurons to help isolate macro features like the nose, eyes, mouth, and ears.

Hidden units

Hidden units have a one-to-one neuron/receptive field relationship. This way, a hidden unit can determine if the appropriate feature was located.

Output

The resulting output from the hidden units comes down to a single output neuron. Based on a previously chosen threshold, an output neuron may indicate a positive face match or a negative face match.

Now that we know how an ANN works, it can be applied to the problem of authentication and identification. To apply an ANN to authentication, a series of training faces are taken and then compared to a live template that is a true match. The ANN is given a chance to match the face and, if it fails, the ANN is adjusted so that a match is found. Figure 6-3 shows a generalized ANN for face processing.

Figure 6-3. Generalized ANN for face processing. (Source: Asim Shankar and Priyendra Singh Deshwal, "Face Detection in images:Neueral Networks & Support Vector Machines," Indian Institute of Technology, Kanpur, April 2002, p. 7.)

Automatic Face Processing

Automatic face processing is the simplest of all the facial recognition algorithms. This algorithm works on the basis of measuring the size of a macro feature and the distances between the macro features of the face. The resulting ratios that can be created are used to form the facial template. Once the ratios are calculated, the templates are binned based on different primary ratios. For example, faces may be binned based on the distance between the eyes, or the width of the mouth.

Which Algorithm Is Best?

Face biometrics and their use can be greatly influenced by the conditions in which they are used. The focus of our work here is using biometrics for network access. As such, this biometric would be used mainly in offices with generally acceptable lighting conditions. The user would normally be seated at his/her desk for verification and would generally be authenticating based on a claim of identity. This claim of identity could take the form of inserting a smart card or providing a user ID. In addition, the user would authenticate at least three to four times a day. The speed of the authentication would need to be sufficient to make it usable, and it is quite possible that the facial expression would not always be the same. With these as our parameters, each algorithm is evaluated as to its suitability for this environment.

Eigenface

The Eigenface algorithm is relatively quick with its searches. It generally requires good lighting and the face to be presented in a full frontal orientation. Both of these can be accommodated within our parameters. It does not deal well with variations in facial expression. As such, the user would need to present a face that is always non-expressive. This may not always be possible. Additionally, it is not consistent with people who sometimes wear glasses or grow beards. This may require the user to be re-enrolled if the user wears glasses all the time has a beard.

Eigenface is a good general-purpose algorithm to use when the user community is relatively controlled and conditioned. It may not be appropriate for less structured user communities. The fact that wearing glasses and beard growth affects the algorithm's ability to authenticate could lead to a large FRR. This in turn could lead to more calls to the help desk and reduced user satisfaction.

Local feature analysis

Local feature analysis uses macro facial features along with bone structure and changes in shading to define anchor points. As such, it is much more forgiving for less than ideal lighting conditions and users who sometimes wear glasses and grow beards. The facial expression is not as critical because the bone structure does not change based on expression. It can also tolerate the face not being presented in a full frontal view. Since the macro features and bone structure are used as the anchor points, the head does not have to be held still for imaging to occur.

In general, local feature analysis is very suitable to use as a network security biometric.

Neural network

Neural network uses a learning method to teach the network how to recognize and differentiate the face. As such, it is very good at isolating the face from a complex background. While some office areas may seem more " jungle -like" than others, in general, office environments are relatively uncluttered. The algorithm also requires a large database of images to get bootstrapped, and therefore, can be slower in processing the requested face for authentication. Additionally, the neural network requires a full frontal view of the face with good lighting. This requirement is within our parameters of the office environment.

While the neural network does a good job of face recognition in complex environments, the office world does not require this level of sophistication. Therefore, the tradeoffs in using the algorithm in an office setting with controlled conditions are not sufficient to make it suitable for biometric network access.

Automatic face processing

Automatic face processing is a very quick and efficient algorithm. Its use of macro feature measurements and sizing, combined with binning , makes it a winner in lookup speed. What is known is that variation in facial expression will affect its measurements on items like mouth width and distance to other macro features. Other measurements may also be affected by changes in expression. It does work well in dimly lit areas. This is not a requirement for our needs because office environments are generally well-lit. In addition, there could be a relatively large FAR for this algorithm. There is the question of sufficient entropy in the human face to make the metrics meaningful enough for use. In a one-to-one match, the FAR may be sufficiently low enough to make it useful. Where this algorithm may be useful is for convenience when the possibility of a false acceptance is acceptable for the tradeoff of having a much lower FRR.

Recommended facial algorithm

It appears from our analysis of facial algorithms that local feature analysis is the most suitable for biometric network access. What is being compared here is the state-of-the-art at this time. There are constant improvements being made to all the above-mentioned algorithms. For you to make the most informed decision on what algorithm to use, review what the use environment will be like, and what the goal of the system is. From here, a list of general assumptions can be compiled to select a group of vendors that may provide the most applicable algorithms and devices. Once this is done, the methodology described for conducting a proof of concept, then a pilot, and eventually a deployment will help you make a final decision.