Line-Based Face Recognition under Varying Pose.
AbstractMuch research in human face recognition involves fronto-parallel face images, constrained rotations in and out of the plane, and operates under strict imaging conditions such as controlled illumination and limited facial expressions. Face recognition using multiple views in the viewing sphere is a more difficult task since face rotations out of the imaging plane can introduce occlusion of facial structures. In this paper, we propose a novel image-based face recognition algorithm that uses a set of random rectilinear line segments of 2D face image views as the underlying image representation, together with a nearest-neighbor classifier as the line matching scheme. The combination of 1D line segments exploits the inherent coherence in one or more 2D face image views in the viewing sphere. The algorithm achieves high generalization recognition rates for rotations both in and out of the plane, is robust to scaling, and is computationally efficient. Results show that the classification accuracy of the algorithm is superior compared with benchmark algorithms and is able to recognize test views in quasi-real-time.
Introduction
Automated face recognition (AFR) has attracted much interest over the past
few years. Such interest has been motivated by the growth in applications in
many areas including, face identification in law enforcement and forensics,
user authentication in building access or automatic transaction machines,
indexing of, and searching for, faces in video databases, intelligent user
interfaces, etc. AFR generally consists of different components namely, face
detection to determine the position and size of a human face in an image (see,
for example, Sung and Poggio [15]), face recognition to compare an input
face against models of faces that are stored in a database of known faces
and indicating if a match is found, and face verification for the purpose
of authentication and/or identification. In this paper we study the face
recognition and assume that the face location in the image is known.
Unfortunately, face recognition is difficult for a variety of reasons. Firstly,
different faces may appear very similar, thereby necessitating an exacting
discriminant task. Secondly, different views of the same face may appear
quite different due to imaging constraints, such as changes in illumination
and variability in facial expressions and, due to the presence of accessories
such as glasses, beards, etc. Finally, when the face undergoes rotations out
of the imaging plane, a large amount of detailed facial structure may be oc-
cluded. Therefore, in many implementations of face recognition algorithms,
images are taken in a constrained environment with controlled illumination,
minimal occlusions of facial structures, uncluttered background, and so on.
The most popular approaches in the face recognition literature are mainly
identified by their differences in the input representation. Two major input
representations are used, namely the geometric, feature-based approach and
the example- or image-based approach. The matching procedure of input
and model faces used in the majority of the geometric or image-based approaches
utilises fairly standard distance metrics like the Euclidean distance
and correlation.
The feature-based technique extracts and normalises a vector of geometric
descriptors of biometric facial components such as the eyebrow thickness,
nose anchor points, chin shape, zygomatic breadth etc. The vector is then
compared with, or matched against, the stored model face vectors. This ap-
proach, however, requires the solution of the correspondence problem, that
is, the facial vector components must refer to the facial features in the im-
age. Also, model face generation can be time consuming, particularly for
large face databases, and the complexity of geometrical descriptors can be
restrictive. Model generation and matching with non-fronto-parallel poses
and varying illumination are more complex and can only be achieved at the
expense of increased computation times (for example, Brunelli [3]). The
technique was pioneered by Kanade [8] and, more recently, by workers such
as Brunelli et al [4].
The motivation for the image-based approach is its inherent simplicity
compared with the feature-based approach owing to the fact that it does
not use any detailed biometric knowledge of the human face. Image-based
techniques include any variation in face appearance due to changes in pose
and lighting by simply storing many different 2-D views of the face. These
techniques use either the pixel-based bidimensional array representation of
the entire face image or a set of transformed (e.g., gradient filtered) images
or template sub-images of facial features as the image representation. An
image-based metric, such as correlation, is then used to match the resulting
image with the set of model images. Two popular methods are used in
the context of image-based face recognition techniques namely, template-based
and neural networks. In the template-based approach, the face is
represented as a set of templates of the major facial features which are
then matched with the prototypical model face templates (see, for example,
Baron [2]). Extensions to this technique include low dimensional coding to
simplify the template representation and improve the performance of the
template matching process (see, for example, the "eigenfaces" of Turk and
Pentland [16]) or wavelets, stochastic modeling with Hidden Markov Models
(HMMs) ([14]), and elastic face transforms to model the deformation of the
face under a rotation in depth ([19]). Neural network-based image techniques
use an input image representation that is the grey-level pixel-based image
or transformed image which is used as an input to one of a variety of neural
network architectures including, multi-layer, radial basis functions and auto-associative
networks (see, for example, Edelman et al [7]).
Although geometric or image-based approaches are conceptually well-suited
to face recognition, many of the techniques developed to date have
been demonstrated on small, simplistic face databases with strict imaging
constraints requiring, in many cases, large processing times for training
and/or recognition. In this paper we propose a line-based face recognition
technique under varying pose that is computationally-efficient, has good
recognition rates, handles face rotations both in, and out of, the imaging
plane and is robust to variations in scale. The image representation scheme
used is a set of random one-dimensional rectilinear line segments of the grey-level
face image and the matching scheme is an efficient nearest-neighbour
classifier. The scheme exploits the uniqueness of a given face image resulting
from the combination of different subsets of line segments of the image. We
present an overview of the performance of current face recognition systems
in Section 2. We then describe our face recognition algorithm in Section 3
and present the face recognition experiments with results and comparisons
with other benchmark algorithms in Sections 4 and 5.2, respectively. Finally,
we conclude and give future work in Section 6.
2 Performance of Current Face Recognition System

We review the comparative performance of some face recognition systems
that use the geometric or image-based approaches. A few authors report
comparisons of two or more systems. In a later section we will make a reference
to the performance of some of these systems when we provide results
for our algorithm (see Section 5.2). Achermann and Bunke [1] compare
the eigenface classifier, a classifier based on hidden Markov models (HMM)
and a profile classifier on a 30-person database with moderate pose variation
amongst the ten views per person. The eigenface classifier performed
best (94.7%), followed by the HMM classifier (90.0%) and the profile based
classifier (85.0%). Ranganath and Arun [12] compared radial basis functions
and a nearest-neighbour classifier, using (i) an eigenface-based and
(ii) a wavelet-based image representation They observed that the radial basis
function classifier performed better than the nearest-neighbour classifier,
and that the eigenface representation offered somewhat better discrimination
than did the wavelet based representation. Brunelli and Poggio [4]
compared a feature based approach with a template based approach on a
47-person database of frontal views. The template based technique achieved
100% correct classification while the feature based method achieved 90% but
was faster. Zhang et al [20] compared three face recognition methods: the
eigenface approach, a two-network based connectionist approach and a flexible
template approach. The two networks are an auto-associative network
for feature extraction and a classification network for recognition. With the
template approach, Gabor filters were used to pre-process the image and
elastic matching with an energy function was used for recognition. The tests
were performed on four individual databases and on the combined set of 113
persons. The eigenface classifier was found to perform well for the individual
data-bases where illumination conditions are constant, but performed
badly (66%) on the combined database because of different light conditions
amongst the databases. The flexible template approach performed well on
all data including the combined database (93%). The two neural networks
did not perform well. A recent survey on face recognition in general was
compiled by Chellappa et al [5]; Valentin et al [18] surveyed the use of connectionist
models in particular.
3 An Efficient Face Recognition Algorithm
Here, we briefly outline the face recognition algorithm which is based on a
more general object recognition algorithm given in [6]. We are interested in
classifying K faces, image views of
each unique face F k , obtained by regular sampling in the viewing sphere.
The aim is to recognize one of the K faces from one or more test image
views.
A face image = is modeled as a regular lattice of w \Theta h pixels, with each
pixel P having a depth equal planes. We first classify the pixels
into two classes, C p;1 and C p;2 . Class C p;1 consists of the background
pixels in the face image =, and class C p;2 consists of all those pixels that
represent a face in = such that C p;1 " C OE. We are interested in those
pixels in C p;2 with neighbours in C p;1 and call the set of those face boundary
pixels fi.
Consider l pixel values extracted along a straight line between two points
in the image, comprising of l bits of data. The number of line pixels (or
line dimensionality) is small enough for efficient classification but of course
may not capture the information necessary for correct classification. How-
ever, with some reduced probability (larger than random) the line predicts
the correct face class. The algorithm we propose is based on the observation
that the classification of many such lines from a face image = leads to an
overall probability of correct classification (PCC) which approaches 1. An
example set of face lines is shown in Figure 1.

Figure

1: Example set of random lines in a face view.
For any two points in an image view V k , such
that the Euclidean distance between B 1 and B 2 is greater than a minimum
be a vector of length l, where l is
the number of equi-spaced connected intensity values L
along the image rectilinear segment from B 1 to B 2 . The
line segment length l is a constant parameter determined a priori; larger
values of l result in better classification rates at the expense of increased
processing times. All lines are scaled to the value l by pixel interpolation.
We call lattice line, denoted by L. The exact endpoints of L
need not lie on a corner of the boundary pixels B 1 and B 2 .
For each face class F k in the training set of V k image views, we randomly
generate
lattice lines (N V k
lines per image view per face class),
i;k . There are
lattice lines for K face classes. The set of lattice lines for all K face classes
is given by:
We define the distance D(L r;s ; L m;n ) between two lattice lines L r;s and
L m;n as
l
and -(L r;s
l L r;s =l. The value of \Delta has the effect of shifting the two
lines towards the same average value, making the distance measure invariant
to illumination intensity.
Given an unseen test lattice line L j where generally L j 62 \Psi, we define
\Psi. The Nearest-Neighbour
Classifier (NNC) maps L j to the class F k to which L j;  belongs.
That is, We write D j for D(L
We assume that there are N test lines L j , where
each line we have obtained a L j;  and a D j . Let D
(for some value k 1 where g. We
define the variance for line L j , var
and the maximum variance, var g.
We define the measure of confidence that NNC(L j ) is correct, conf
(Dmax \GammaD min )
otherwise.
. The variables p 1 and p 2 control the shape of
the confidence function, whereas w 1 and w 2 are the weight magnitudes of
the distance and variance components, respectively.
We now state the face recognition algorithm.
The Line-Based Face Recognition Algorithm:
To classify a face F t for which we know its boundary pixel set fi, we randomly
select N lattice lines L j , . For each face class F
define
We assign F t
to class F g such that TC g is maximum. That is,
if
then F g / F t for F
Because F t is assigned to class F g based on the combination of many
assignments of individual lines, we may assess the likelihood that our decision
is correct by the agreement within the line assignments. Specifically,
we define the confidence measure factor as the ratio
where
j is the second largest compounded confidence measure that a
class obtained. As our decision is based on the maximum score, the associated
confidence CMF is proportional to the difference with the second
largest score. The denominator normalises CMF for different numbers of
testing lines.
It is a considerable advantage if a classifier were to supply a confidence
measure factor with its decision, as the user is then given information about
which assignments are more likely to be wrong so that extra caution can
be exercised in those cases. Our implementation makes use of CMF by
means of several decision stages. Firstly, the number of testing lines is kept
small, an initial decision is arrived at quickly, and the confidence measure
factor is evaluated. Secondly, if the confidence measure factor is smaller
than twice the minimum confidence measure factor threshold CMF min then
the number of testing lines is doubled and a second decision is made at the
cost of extra time. Finally, if the second confidence measure factor is smaller
than CMF min , the 'doubling process' is repeat one last time.
The above algorithm is surprisingly simple and, as we shall demonstrate,
is particularly efficient in both the recognition rate performance and computation
time. Moreover the algorithm has some inherent advantages. Firstly,
due to the randomised sampling of the image, the algorithm is robust to rotations
of the face in the plane. Secondly, we reason that multiple views are
even better suited to our 1D line-based algorithm and is better able to handle
head rotations out of the plane than 2D view-based algorithms. Thirdly,
since the lines run from one face-boundary to another and have fixed di-
mensionality, the algorithm is also scale-invariant. Fourthly, the choice of
distance measure ensures that it is tolerant to changes in illumination inten-
sity. Finally, because all lines are sampled from the entire head section of
the image, the algorithm is also robust to changes in facial expressions and
in the presence or absence of glasses or other accessories. Unfortunately,
the current algorithm is not robust to changes in illumination direction such
as found in outdoor settings or successful in cluttered scenes (such as in a
video sequence).
Face Databases and Experimental Methodology
In order to evaluate the performance of the algorithm we used two face
databases namely, the University of Bern (UB) [17] and the Olivetti & Oracle
Research Laboratory (ORL) [11] face databases. The UB face database
contains ten frontal face images for each of persons acquired under controlled
lighting conditions. The database is characterised by small changes in
facial expressions and intermediate changes (\Sigma30 degrees out of the plane)
in head pose, with two images for each of the poses right, left, up, down
and straight. The ORL face database consists of ten frontal face images for
each of 40 persons (4 females and 36 male subjects). There are intermediate
changes in facial expression and unstructured intermediate changes (\Sigma20
degrees) in head pose. Some persons wear glasses in some images and the
images were taken under different lighting conditions. In our experiments
we combined the two databases to form one larger one containing 700 images
of 70 persons. The data set was used to assess the classification rate of our
algorithm by cross-validation, using five images per person for training and
the other five for testing.
5 Experimental Results
Prior to evaluating the overall performance of the algorithm for the combined
face database, various parameters were optimised. These included
the number of training lines (N k ), the number of test lines (N ), the line
dimensionality (l), and the decision confidence measure factor (CMF ).
5.1 Evaluation of Parameters
In order to investigate the effect of various parameter settings on classification
time and correctness, we ran four experiments, varying one parameter
at a time. In each experiment, the parameters were resampled over the combined
face database. For example, for evaluating the probability of correct
classification (PCC) for different numbers of test lines, each set of test lines
was obtained by resampling the combined face database.
The results are presented in Figures 2 to 6. The vertical axis shows the
classification accuracy (probability of correct classification, PCC) as a per-
centage, the horizontal axis represents the computation time in seconds, per
view. Each figure shows two lines, the upper line indicates the percentage of
correctly classified persons based on the majority of the view classifications,
the lower line shows the percentage of correctly classified individual views.
Each point on both lines corresponds to one of the parameter settings (see
the figure caption for their values). Each graph also shows the standard
deviations obtained for the 10 repetitions undertaken for each experiment.
For each repetition, the training and test lines were resampled and the PCC
recorded.
In the first experiment, the number of test lines N was varied from 20 to
400 (17 values in total). The number of training lines, N k , was set to 200, the
line dimensionality was set to l = 32 and the minimum confidence factor was
set to zero. Figure 2 shows the results. As expected, both the computation
time and the classification accuracy increase almost monotonically with the
number of test lines. The increase in time is approximately linear while the
accuracy first increases rapidly and then levels out. A distinctive 'knee' in
the curve of the percentage of correctly classified persons occurs at about
test lines with a classification accuracy of approximately 95%. This
corresponds to a ratio in the number of test pixels to image size equal to
0.18, equivalent an effective dimensionality reduction by a factor equal to
5.5.

Figure

2: PCC versus time for 17 values for the number of testing lines
20, 30, ., 110, 120, 150, 200, ., 400. Here, the number of training lines N k
200, the line dimensionality l = 32, and the confidence threshold CMF min
In the second experiment, the number of training lines was varied from
50 to 400 (9 values in total). The number of testing lines was fixed at 150,
the line dimensionality was set to 32 and the minimum confidence parameter
was set to 0. Figure 3 shows the results.

Figure

3: PCC versus time for 9 values for the number of training lines N k
Again, as expected, both the time and the classification accuracy increase
with increased number of training lines. However, the shapes of the curves
are flatter than those for the test lines (Figure 2), i.e. there is no distinctive
'knee' where the curve flattens out. This is as expected, as increasing the
number of training lines increases the PCC of a test line, while increasing
the number of test lines only decreases the variance in the procedure that
forms a decision from the classifications of all test lines. Once that variance
is reduced significantly, the inaccuracy due to a finite number of training
views dominates and the curve flattens out.
In the third experiment, the minimum confidence measure factor value
was varied from 0.0 to 0.4 (8 values in total). The number of training
lines was set to 300, the initial number of testing lines set to 50, and the
line dimensionality set to 32. The results are shown in Figures 4. The
experiment was repeated with the number of initial testing lines set to 100
(see

Figure

5). Both Figure 4 and 5 look very similar, with the larger values
of the minimum confidence factor resulting in larger computation times.
However, an improved accuracy for the case when the initial number of test
lines is doubled is observed. On the other hand, both figures converge to a
similar classification accuracy. For example, for a time equal to 0.7 seconds,
both cases achieve near 100% accuracy for the persons and greater than 90%
accuracy for the views. This means we can decrease the number of initial
testing lines without ill-effect so long we increase the minimum confidence
measure factor accordingly, and vice versa.

Figure

4: PCC versus time for 8 values of the minimum confidence measure
2.

Figure

5: PCC versus time for 7 values of the minimum confidence measure
and
In the last experiment, the line dimensionality l was varied from 8 to
values in total). The number of training lines was set to 300, the
initial number of testing lines was set to 100 and the minimum confidence
value was set to 0.1. The results are shown in Figure 6. The classification
accuracy first increases rapidly, then stabilizes, with the change occurring
between 24. The timings first decrease then increase. This is
because the confidence value is not set to zero, and small dimensionalities
triggered frequent increases in the number of test lines. However, it is perhaps
surprising that, for l = 16, the classification rate for persons is already
near 100%.

Figure

values of the line dimensionality l = 8, 12,
The results indicate that, despite very low PCC of individual lines (we
observed values around 0.1), combining a large number of such classification
results in am overall PCC which is much higher. In fact, the graphs indicate
that as the number of training lines goes to infinity, the PCC approaches
1.0.
In the following section we present results for the combined face database
using optimal parameter values. The number of training and test lines per
face view were chosen to be equal to 200 and 80, respectively, a dimensionality
of confidence measure factor equal to 0.4 were
selected.
5.2 Face and View Recognition Performance Results
We ran two sets of experiments using the optimal parameter values. In the
first set we selected the training set by inspection in order to provide a good
cover of the varying head positions and facial expressions. In the second set
of experiments we randomly selected the image views, repeating the process
three times. We expect to obtain an inferior recognition rate for the random
sampling of the training set compared with the selected sampling. Most real-world
applications would allow selecting good training views as with our first
approach. However, in some applications such as video sequences, random
sampling is more realistic. We also evaluated the algorithm for both face
recognition and view recognition. That is, in the former case, the algorithm
is presented with all the test image views for a given face whereas, in the
latter case, the algorithm is presented with just a single test view (as would
be found in, for example, an access control situation). Again, we expect
lower recognition performance results for the view recognition as compared
with the face recognition.

Table

1 shows the results obtained for both the regular (selected) and
random set of training and test views and, for both face and view recognition,
for the combined face database. Also shown are the maximum and minimum
recognition rates obtained in all experiments.
Training Classification Accuracy (%) Training Time Test Time
Procedure Face Recognition View Recognition per view (sec) per view (sec)
Random 98.0 80.8 0.8 max 0.79 max
Selected 100.0 88.6 0.8 max 0.69 max
Selected 100.0 99.8 1.6 max 5.0 max

Table

1: Face and view recognition rates for random and selected sampling
of training poses for the combined face-database.
With selective (non-random) view cover, we found that 100% of persons
are correctly classified if approximately 0.7 seconds or more are spent per
view to form the decision. Further experiments have shown that we can
reduce the test times at the expense of a reduced recognition rate - approximately
85% of persons were correctly classified if a maximum of 0.1 seconds
were allowed. On the other hand, a significant improvement in the view
recognition rate can be achieved if a higher test time is allowed - nearly
100% of all views are correctly classified if up to 5 seconds are used for test-
ing. For random sampling we observe slightly reduced recognition rates and
fractionally longer test times (per view). The results confirm that a relatively
small number of views is sufficient for good view-based classification
performance if the test views are sufficiently covered by the training views.

Figures

7 and 8 show examples of a face view instance that was mis-classified
by the algorithm in one of the experiments. The second and third
rows of faces are training examples of two persons (one person for the second
row and one for the third row). The first row shows the test image view
corresponding to the person in the third row that was misclassified as the
person in the second row. As can be seen, it is not always straightforward
to discriminate between the two persons in some poses.

Figure

7: Example misclassification of a test view for 5 training views of
two persons from the ORL database (see text for explanation).

Figure

8: Example misclassification of a test view for 5 training views of
two persons from the UB database (see text for explanation).
We also tested our method on the individual databases. Our method
achieved 100% correct recognition of views on the ORL database using an
average of 3.9 seconds per view for testing, and 100% recognition of views on
the Bern database using on average 1.5 seconds per view. More computation
time is spent classifying views from the ORL database because it contains
many more views which are difficult to recognise. The parameter settings
for these results were: 500 training lines, 120 initial testing lines, the line
dimensionality was 24 and the minimum confidence factor was set to 0.5. For
comparison, we include some benchmark results obtained by other workers
on the same face databases (see Section 2). Samaria [13] used the HMM
implementation, Zhang et al [20] implemented both the eigenface and elastic
matching algorithms, Lin et al [10] use intensity and edge information with
a neural network, Lawrence et al [9] tested local image sampling with two
neural networks as well as the eigenface classifier, and Achermann et al [1]
used a combination of eigenface, HMM and profile classifiers. Their results
are summarised in Table 2. We include results for the line-based algorithm
in the last row of the table.
Authors Classifier Method ORL Bern
Zhang et al [20] Eigenface 80.0 87.0
Zhang et al [20] Elastic Matching 80.0 93.0
Lin et al [10] Neural network 96.0 -
Lawrence et al [9] Neural network 96.2 -
Lawrence et al [9] Eigenface 89.5 -
Achermann et al [1] HMM - 90.0
Achermann et al [1] Eigenface - 94.7
Achermann et al [1] Combination - 99.7
Aeberhard et al Line segments 100.0 100.0

Table

2: Comparative recognition rates for ORL and Bern face databases.
As can be observed, our results on the combined databases are better than
any of the benchmarks on the individual databases - even when compared
with combined classifiers. Furthermore, none of the benchmarks give results
for the execution times (which, we suspect, are larger than our results for
comparable classification accuracies). Our test time results are quite adequate
for real-time applications such as security access and video sequence
tracking.
6 Conclusions
We have described a computationally-efficient view-based face recognition
algorithm using line segments of face images. The algorithm is robust to
rotations in, and out of, the plane, robust to variations in scale, and is robust
to changes in illumination intensity and to changes in facial expressions.
Experiments have demonstrated that the algorithm is superior compared
with available benchmark algorithms and is able to recognise test views in
quasi real-time.
The main drawback of our technique lies in the assumption that the face
detection has been undertaken prior to the application of the line-based algorithm
and that the face boundaries are available. If the boundaries are
largely occluded or indistinguishable from the background then the performance
of the current algorithm will be reduced. We are currently investigating
modifications to the algorithm that will account for the absence of
face boundaries.



--R

Combination of face classifiers for person identification.
Mechanisms of human facial recognition.
Estimation of pose and illuminant direction for face pro- cessing
Face recognition: Features versus templates.
Human and maching recognition of faces: A survey.

Learning to recognize faces from examples.
Picture processing by computer complex and recognition of human faces.
Face recognition: A convolutional neural network approach.
Face recognition/detection by probabilistic decision-based neural network

Face recognition using transform features and neural networks.
Face Recognition Using Hidden Markov Models.
Parametrisation of a stochastic model for human face identification.

Eigenfaces for recognition.
University of Bern
Connectionist models of face processing: A survey.

Face recognition: Eigenface
--TR
face recognition;line-based algorithm;real-time performance;varying pose;classification accuracy