GTL 1012
`IPR of U.S. Patent 9,007,420
`
`0001
`
`

`
`The papers in this book comprise the proceedings of the meeting mentioned on the cover and title
`page. They reflect the authors‘ opinions and are published as presented and without change. in
`the interests of tirneiy dissemination. Their inclusion in this publication does not necessarily
`constitute endorsement by the editors.
`the IEEE Computer Society Press. or The Institute of
`Electrical and Electronics Engineers. Inc.
`
`I
`
`‘Q 3)
`
`7; 8
`“'
`
`Published by
`IEEE Computer Society Press
`10662 Los Vaqueros Circle
`
`PO. BOX 3014
`Los Alamitos, CA 90720-1264
`
`Copyright © 1990 by The Institute of Electrical and Electronics Engineers, Inc.
`
`Cover designed by Jack I. Ballestero
`
`Cover illustrations from a paper by F. P. Ferris. J. Lagarcie. and P. Whaite
`
`Printed in United States of America
`
`Copyright and Reprint Permissions: Abstracting is permitted with credit to the source. Libraries are
`permitted to photocopy beyond the limits of US. copyright law for private use of patrons those
`articles in this volume that carry a code at the bottom of the first page. provided the per—copy tee
`indicated in the code is paid through the Copyright Clearance Center. 29 Congress Street. Salem.
`MA 01970. Instructors are permitted to photocopy isolated articles for noncommercial classroom
`use without fee. For other copying, reprint or republication permission, write to Director, Publishing
`Services. lEEE. 345 East 47th Street. New York. NY 10017. All rights reserved. Copyright © 1990
`by The Institute 01 Electrical and Electronics Engineers. Inc.
`
`IEEE Computer Society Press Order Number 2007
`Library of Congress Number 89-81435
`IEEE Catalog Number 89CH2813-4 -
`ISBN 0-81 86-22007-2 (paper)
`ISBN 0-8186-6007-4 (microfiche)
`SAN 2654-620x
`
`Additional copies may be ordered from:
`
`IEEE Service Center
`IEEE Computer Society
`445 Hoes Lane
`10662 Los Vaqueros Circle
`PO. Box 1331
`PO. Box 3014
`Los Alamitos CA 90720-1264 Piscataway. NJ 08855-1331
`
`IEEE Computer Society
`13. Avenue de l'AquiIcn
`B-1200 Brussels
`BELGIUM
`
`IEEE Computer Society
`Ooshima Building
`2-19-1 Minami-Aoyama.
`Minato-Ku
`Tokyo 107 JAPAN
`
`THE INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, INC.
`
`0002
`
`

`
`This material may be protected by Copyright haw {Title 11' LLS. Code]
`
`FACE AU'I‘HEN'I‘IFICATl0N OR RECOGNITION BY PROFILE EXTRACTION
`'
`FROM RANGE IMAGES
`-
`
`'J.Y. CARTOUX, 1.1‘. LAPRESTE, M. RIC]-IETIN
`
`Electronic Laboratory, URA 830 of the CNRS, University Blaise Pascal oi’ Clermont-Ferrand,
`63177 AUBII-IRE CEDEX, FRANCE
`Phone: ’l'3.26.»-£1.10 ;Telefa‘x: 7326.42.94; EMAIL: EVALEC@FRMOPl1.BI'[‘NEI‘
`
`ABSTRACT :
`
`This work is related with authentification or recognition of
`human faces from their range images. The a
`roach consists in
`comparing a part of the profile or of the su ace of two faces.
`For this aim, the profile plane of each face considered as a
`quasi-
`etry plane is extracted with an iterative process
`which involves the similarity of the Gaussian curvature values
`of the face surface. Thenanoptimal matching ofthe two profiles
`is done which allows the calculus of similarity indices of profiles
`or of surfaces. Tests for robustness and the authentification or
`recognition results show the efficiency of the whole procedure.
`KEY WORDS :
`
`3D Vision, Ran e Images, Human Faces, Face Profile,
`Authentification,
`ecognition, Principal and Gaussian Cur-ea»
`tures, Symmetry Plane.
`
`1 INTRODUCTION.
`
`Face identification is a natural ability for human bein . It
`issuchs need insocialiife that evolution has selected indivi uals
`able to recognize faces even long after the first look. In fact
`recent experiments in Neurobiolo
`have proved there exists a
`specific cortex area in the human rain to perform this task
`[TI-[P-88].
`Automatic recognition by computer of human faces is a
`recent claim resultin of the growing urbanization ofthe human
`environment and o securities enforcement. Recognition can
`be distinguished from authentification since in the first case,
`the roblern is to find a person in a (posslbly) large population
`an in the second the question is rather tojudge ifa given person
`is the one he pretends to be. However, the real nature of the
`two problems is not so different because in each case compa-
`mo e .
`risoctitslmusttakeplace betweena face to identify and a registered
`The investigation can be done from two kinds of data :
`brightness or range images. Theoretically, these two classes bear
`the same information as radiance is functionally related to
`surface geometry. However, if finding radiance from geometry
`assuming (for exam Ie) a Lambertian model is rather simple,
`the converse is an H -posed Hardy problem which has not been
`solved it: the general case yet. It is then pertinent to say that
`range images are today the most convenient infonnation to
`expect good results in automatic face recognition.
`This aper
`resents works which follow studies reported in
`[CAR-8
`and
`P-88]. The precedent approach was partially
`invalidated when dealingwith new range images obtained from
`a range finder develo ed in the French "Institut*Geographique
`National" [Tl-10-88].
`ts field ofview is such that it is not always
`possible to obtain a closed concave domain surrounding the
`
`CH281 3-4zs91ooooro194.r$o1 .00 .'1'9.as IEEE
`
`I94
`
`eyes and the nose. The corn utation ofthis domainwas the base
`of the determination of t e profile plane (considered as a
`quasi-symmetry plane of the face). Figure 1 presents transition
`lines between concave and convex parts of a face range image.
`It is clear that there is no hope to get a closed concave domain
`in the center part of the image.
`
`Figure 1: Transition lines between
`convert et concave domains of Johnl face.
`
`Thus an other approach for the determination of the profile
`plane was necessary. It appeared to be more reliable than the
`precedent one as shown in the next section.
`
`2 EXTRACTING THE FACE SYMMETRY
`PLANE.
`
`2.1 General principle.
`
`It comes from the following simple idea: the profile plane
`of a face which is a quasi~syn1metry one segments the face
`surface in two parts that are approximately equal after
`application of an isometry. In particular, its 3-D image is
`divided in two parts sharing the same principal curvatures
`values. Conversely, if these two sets can be constituted, the
`symmetry plane computation is almost trivial.
`
`0003
`
`

`
`Let us su
`ose we are given an initial symn-let
`lane,
`evenroughly ggtennined, considered as theprofile prllultje (we
`shall discuss of its determination in the next section). It is
`then possible to intersect the surface by a set of parallel plane
`sections, normal to this initial plane and to the XOY plane
`(plane normal to the camera optical axis 02.).
`
`The problem is now to analyze each of the cuts to extract
`pairs of points (each in one ofthe two half
`aces determined
`by the initial symmetry plane) for which t e distribution of
`the Gaussian curvature values in a neighbourhc-od'of this
`points is nearly the same. From the set of these pairs a new
`symmetry plane is obtained.
`
`'
`
`Iterating this analysis from thislastplaneuntil satisfaction
`of a stopping criteria (involving stability of the successive
`values o the plane parameters) leads to the final plane.
`
`2.2 Computing the symmetry plane.
`2.2.1 First determination
`
`lane can reduce notably
`A good choice of the initial
`the number of iterations needed or the convergence ofthe
`detemtination process.
`
`It is supposed that when the image image is acquired,
`the head is in a normal "position" in front of the range
`finder, i.e. the head is nearly vertical, the profile plane is
`near
`arallel to the optical axis, and their distance is not
`too
`Two choices for the initial planehavebeen tested:
`i) The plane normal to XOY and X02 which goes
`through a point considered as the nose tip,
`
`ii)
`
`the plane normal to XOY going through the same point
`and a point called nasion.
`
`Nose tip and nasion are detennined in the following way:
`
`- The elliptical or umbilical convex point with maximal
`Z-coordinate can be taken as a good approximation of
`the nose tip.
`As the image edges are noisy the search is restricted to
`a central area of the image face.
`
`- Above the nose tip the be center of a convex
`hyperbolic area is looked for.
`is barycenter must
`satisfy the two following conditions:
`
`1) to be at a minimal fixed distance from the nose
`tip.
`
`2) after projections on the XOY plane, the straight
`line joining these two points must be parallel to the
`average 0 the minimal curvature direction on the
`convex domain above the nose tip and under this
`point.
`
`In the second case the convergence of the process is
`much faster. However as the deterrnination of the nasion
`ismore or less face dependent and can fail, the initial plane
`is chosen according to the following strategy:
`
`0 find the nose tip, which is ever possible,
`
`0 look for a nasion, if success then take choose ii)
`else choose i) (as defined before) and increase the
`maximal number of iterations allowed in the next
`step.
`-
`
`Figure 2: Convert domain and initial symmetry plane
`trace
`for Billl (left) and John2 (right) faces.
`
`lane so -
`The trace on the plan XOY of the initial
`chosen is shown in Figure 2 which gives also the abellin
`of the convex points of the face ima es Biill and Jo]
`accordingto the geometrical nature 0 the the face surface
`deduced mm the principal curvatures.
`2.2.2 Iteration details.
`
`For each cut C.. a syrrunctrical point M,-,- of each
`point M .,
`situated at the left of the symmetry plane is
`looked for. For this, at the right of the symmetry plane, the
`points
`of C.
`and of
`the
`neighbouring
`cuts
`(C.-;...C.-.._ . C..;...C....r)areinvestigated, N .. being
`the maximal number of neighbouring cuts to analyze.
`Final Profile Plane
`
`-.__
`' ,
`
`Ml Search Area
`
`M2 Search Area
`
`Figure 3: Adaptation of N 4 in profile plane evaluation.
`
`N . must be adapted to the position ofthe current point
`with res ect to the rofile lane. Figure 3 shows the traces
`in the-X Yplane o neigh ouring cut planes, of the profile
`plane at the Nth iteration and of the final
`rofile plane
`obtained after convergence of the process.
`0 detect the
`symmetrical point M '1 (reap M '2) of point M1 (tesp
`M 2 ), we have to examine five adjacent cuts for M . and
`only two for M 2 , because M .
`is further from the profile
`plane than M 2 . The size of the research area for points
`far from the profile plane has to be greater than for points
`situated hi the neighbourhood of the symmetry plane to
`keep the same rotation possibilities.
`
`0004
`
`

`
`For each pair (M U . M ,-,-). a matching coefficient
`¢,_.(£ ’ . j ' } is calculated from the Gaussian curvatures of
`points taken in a (3x(2-T.,+ 1)) neighbourhood
`around Mn and ma neighbourhood of same size but
`symmetrical around M .-,- . Tu being a neighbourhood
`parameter (of value 3 in all our experiments).
`
`Wenote I/., (resp. I/.-1-Nhevectorsvhosedirnension
`is (3x(2 - Tim 1)) , and whose coordinates are the
`Gaussian curvature values in the {3X(2- Tm-' 1))
`neighborhood around Mu (resp. M.-,.-). The similarity
`coef_ficient'wh.ich measure the quality of the matching of
`Mn and Mr‘}' is thengivenby:
`
`‘V
`
`1/
`" *1
`
`,V,..
`*’
`
`1
`
`=
`
`=
`
`“/I.I'"Vl'J’|2
`j—»--
`2(K+1)lVuI|V.»rI
`‘1’.,( 1' . J ')
`
`where K is an adjustment coefficient [CAR-89].
`- Matching validation
`
`The matching between Mn and M ,-,- isconsidered
`valid if:
`
`the
`To find the remaining plane ‘parameter,
`baryoenter B. of the previously computed bary-
`centers 0. weightedby the number of pairs 13., of
`each cut, is calculated:
`-
`
`The symmetry plane is now completely determi-
`ned by its normal N 1-... and one of its points, B.
`
`2.3 Results.
`
`The results for two pairs of images are presented here.
`Each pair corresponds to two different»-iews of the same face.
`
`<l*,,(€', 1')
`
`> Threshold
`
`Moreover, if during the search for the symmetrical
`of a given point M ,, we get:
`
`_
`
`Figures 4 a, b, c et d present the 3D images (restored and
`fltered) of these faces. on each one the calculated profile
`plane trace is drawn. The profiles extracted from John1,Bi111
`and Biiiz faces are shown in Figure 5.
`
`The evolution of profile curves of face John2 along the
`steps of the process are shown on Figure 6.
`
`> Threshold
`<l=.,(t" .j’)
`-i=,,(t'" , J”) > Threshold
`
`which means that M r ,- and M ;- 1- can be matched
`with the same point M ,, ,we keep the pair associated
`with the maximal matching coefficient.
`- Determination of the symmetry plane
`
`Let N , be the number of cuts leading to at least
`a pair of matched points. We shall denoteby .Tt,_ the
`number of pairs given by the cut C .. We compute
`thebarycenter G. ofthepairs (M.,. M.-_..) withthe
`matching coefficients used as weights, on the cut C . .
`using the following relation:
`
`Figure 4 a: Billl face.
`
`Figure 4 b: Bill2 face.
`
`Figure 4 c: Johnl face.
`
`Figure 4 d: John2 face.
`
`0005
`
`

`
`Figure 5: Profiles of Billl, Bill}! et .Tohn1 faces (from left to right).
`
`Figure 6 : .iohn2 profile through the process of its determination.
`
`2.4 Determining convergence.
`
`As the symmetry of a face is not exact, there is no hope
`to find a real mathematical criterion. Nevertheless, we can
`choose to stop theiterative process as soon as the results seem
`to stabilize.
`
`We must firstly note that if the matching threshold has
`to be chosen at the first iteration, it is further adapted after
`each iteration to retain only points with high matching
`coefficient. That adaptation is completely automatic, taking
`the average of the coefficients at the previous step diminished
`of the standard deviation of their distribution.
`
`The process is almost achieved when the two following
`conditions are satisfied:
`
`W
`rm
`
`the matching threshold is more than 0.9
`max(rnin( AG” .l0I£tCt.,|))S0.l
`15::
`Ct”
`where:
`'
`A is the backward difference operator on index i
`and x + any + 0‘.g;Z = as. is the equation of the
`plane at step i.
`
`In the minimum-bracket, the relative term is the most
`important one. The absolute term is added to allow conver-
`genoe when very small an es are involved, for which the
`absolute variation is com etely unsignificant but such that
`the loss of significative
`igits provides large relative varia-
`tions. In this case, we add a test on the sign of the variations
`between the last three steps. This is to avoid stopping the
`processifone of the plane equation coefficients slowly crosses
`zero and does not oscillate.
`
`After the satisfaction of _the condition, four more steps
`are performed and the final plane is computed as the average
`ofthe last five oomp uted planes to deal with small oscillations.
`
`2.5 Conclusion.
`
`The robustness of the approach was tested in three
`different ways:
`
`1) we tried the process on three kinds of different images
`arising from different range finders.
`In the three cases the results were very satisfactory. It
`must be noticed that if the images from the IGN range finder
`
`0006
`
`

`
`and from photogramrnetry had to be restored and filtered
`before processing, we worked on raw Canadian images
`[R10-88].
`-
`
`Two extracted profiles are presented i.n Figure 7 a and b.
`
`2) the stability of convergence was tested. Generally, 15
`to 20 iterations were sufficient to ensure convergence as we
`have seen that further iterations producenegllgible varia-
`tions.
`'
`
`3) the sensibility to initial conditions was tested taking
`the two different initial planes previously defined. If the
`needed number of iterations could easily be chan d from 5
`to 20, the results were identical with respect to t%: conver-
`gence criterion.
`
`The analysis of the new images has proved that the
`automatic determination of these points can be very face-
`dependent, and though a data driven approach could surely
`be successful, it was adequate to look or a substitute. The
`matching process is done once again as described -previously.
`On the two profiles, pairs of points are selected such that a
`matching coefficient (similar to the one used in 2.2.2) is
`maximal.‘ However i.t1 this step,
`the matching coefficient
`involves curvature on the profile curve instead of the Gaus-
`sian curvature of the face surface.
`
`When pairs ofsimilar points on the two profile curves are '
`obtained, we compute the rigid transform matching the two
`sets of pairs by
`M com uting the transform of each face which puts its
`pro ile plane on the ZOY plane; this transform only
`depends of the spatial location and orientation of the
`face;
`
`W translating each set of points i.n such a way that their
`barycenter is located at the origin and then computing
`the best plane rotation matching them in the least
`squares sense.
`
`3.2 From profiles matching to face autl1entiI’i-
`cation or recognition.
`
`Fi
`re 8 shows the superpositions of face rofiles after
`the rigid transform for (Billl, Bill2), (EH12, I0 1), (John1,
`Jo
`et (Billl, .To1u12) pairs.
`
`Figure 7 a: Face surface and profile curve
`for a photogrammetric image.
`
`Figure 7 13: Face surface and profile curve
`for a Canadian laser range finder image.
`
`% AUTHENTIFICATION OR RECOGNI-
`
`3.1 Estimating the geometrical transform bet-
`ween two face images.
`
`As soon as the profile planes and curves of each of the
`two faces are known, one needs to compute the best
`eo-
`metrical transformation fitting the two faces in the east
`squares sense. The
`roblern is in the selection of
`oints
`matched in the tra
`orm. Up to now ([CA.R-B7], [LA -88])
`we used a set of anthropometric oints defined on the profile,
`and on the face inside the clos
`concave domain around the
`nose previously discussed in the introduction.
`
`Figure 8 : Superpositions of face profiles of {Bill1, Bi[I2),
`(Bill2, Iohnl), (John1, John2) and (Billl, John2) pairs
`(from left to rfglrr amifmm top to bottom).
`To measure the quality of the two profiles fit, a correlation
`coefficient p and a mean quadratic distance 3 are com-
`puted between the distributions of the Z-coordinates on the
`two profile curves put on the ZOY plane.
`
`0007
`
`

`
`In table 1, we[present the results of the comparisons
`between couples 0 different views of the same face on the
`esfortheIGNimaLg|es. Wehave18imagescorres ending
`'
`to
`different faces: B‘
`3 views), Franck
`Jef ( ), John
`$4) and Mike (4). “In table 1, each image is
`elledwith the
`irst letter of the person first name followed by the image
`number in the corresponding series.
`
`-
`
`We made all the possible ‘comparisons between -these
`images and the C £4" results were ordered either by decreasing
`correlation or by increasing distance. In the first classification,
`the 16 first pairs concern differents views of the same face,
`the total number of such pairs being 24. All these 16 pairs
`have a correlation coefficient
`reater than 0.990 and no
`matcl1i.ng of profile curves from Tferent faces has produced
`such a large coefficient.
`
`80, we can say that for the set of into es we have treated,
`if the correlation coefficient of two mat
`ed profile curves is
`greater than 0.990, then the identity of the faces is certain. In
`other words, a
`erson will be correctly authentified if the
`correlation coef icient between the profile curve of his face
`and the one we have in memory under his name, is greater
`than 0.990.
`
`In the second classification. the number of well classified
`airs of different wiews of the same face is 19. We noted that
`in the set of the 5 absent pairs, we found 4 pairs of images of
`the same face, Mike, for which the quality of the images is
`very poor. From this ordering, it is impossible to deduce a
`thres old as in the former case. But the mean quadratic
`distance seems to bevery discriminating for face recognition.
`If we choose any face image and if we compare it to the 17
`others, the nearest neighbour classification rule using the
`mean quadratic ‘distance leads tothe maximal success score
`
`nuns
`(Pk, 1=1
`
`pi,
`_
`
`(B1, B2)
`ll!
`
`EI
`lfill
`2
`
`1-48
`
`M
`flfill?
`llll
`llll
`lll
`I
`
`Table 1 : Correlation coefficients and mean uadratic
`distances for the 24 pairs of different views o the same
`face.
`
`3.3 Face surfaces matching.
`
`In a si.m.i.lar way, it is possible to match arts of two face
`surfaces us’
`the transform computed be ore and then to
`measure the similarity ofthe faces using thesame indices, the
`coefficient correlation and the mean quadratic distance. We
`made the same orderings as before. In the first one, we note
`10 well-classified pairs and 16 in the second one. In these two
`classifications, no value can be choosen as a good threshold
`for authentihcation. But
`the matching of faces is more
`data-dependent than the profile curves matching.
`However, the nearest neighbour of each thee image, in
`the meaning of the quadratic distance, is always an other
`irnageot’ the same face.
`
`4 Conclusion.
`
`We think that we have designed a ‘robust procedure to
`detennine the profile plane of a face range image accurately
`using the symmetry property of this plane.
`Though the face comparison results are quite acceptable,
`we expect to improve them with a better matching procedure
`of two profile curves. It must also be pointed out that the
`precision ofthe range images needs to be high enoug in order
`to at reliable information on principal curvatures. ven if we
`di not process many images issued from the Canadian range
`finder, we are rather confident that very good authentification
`or recognition scores would be obtained for large sets of such
`face images .
`Lastly, we strongly believe that automatic face identification
`systems will work hi the next future.
`
`5 BIBLIOGRAPHY.
`
`[CAR-87] LY. CARTOUX, J.T. LAPRBSTE & M. RICHBTIN,
`Toward Automatic Humor: Face Recognition Using Their Three-
`Dimertflona! image, Proc. of MAR} 87, 19-224, Pans, May 1987
`
`[CAR-89} J.Y. CARTO UX, Formes darts {cs Images d'eProfondem',
`de Doctorat dc l’Unix-ersité Blaise Pascal de Clement-
`flip iication (1 (’Aut.':emificazr'on at d to Reconnaissance dc I/wages.
`Fcrrand, Numéro d'ordrc 139, Octobre 1989, Clermont-Ferrand.
`
`[FAU-86] 0.D. FAUGERAS & M. HBBERT. The Representation,
`Recognition, and LM 0; 3D Objects, Int. Journal of Robotics
`Research, uol.S, n°3, 1
`,2 -52
`[LAP-87]
`J.T. LAPRESTE, MRICHETIN, J.Y.CAR'I‘0UX &
`Ci. RJVES, Vent fiiutnentification on to R€C0.i'1i’lflfS.|'flflC8AHIOflIfl'l'fqfl¢
`do Visage: ti
`de four Image Tridimensionneite, Rapport dc fin
`de contrat n 85 61 005 00 223 ‘I501, Ministére de i'Ur nisme, du
`Logemcnt ct dcs Transports, Mars 1987.
`
`J.T LAPRESIE, J.Y. CARTOUX & M.RICHETlN.
`[IAP-88]
`Face Recognitior: from Range Data by Srrttcutrai Ana
`'
`, NATO
`ASI Series, vol F45, S tactic and Structural Pattern
`cognition,
`G. Ferraté et al. Eds.
`3-314, Springer-Verlag, 1988.
`
`[R10-83] M. RIOUX &t I. _COURNO‘YER. The NRCC 77lrE€‘-
`dimensiana! Image Dara Files, National Research Council Canada,
`Division of Electrical Engineering, CNRC 29077, 1988.
`
`[TI-lOo88] C. THOM, Production Aaromarique de Modeler Numé-
`riques Tridinrerstionneir d’0bjets en Temps Quasi-reef d raids d'rme
`grsrgéra CCD Video, Note Interns IGN, Saint~Mandé. Novembre
`
`[THP-88] S. J THORPE, fiaftenrent dflfmoges
`Avri
`I
`.
`de1'1:Iog8t.r8rte, Acres du Colioquc-'I"lPl 33, ppl
`
`.l'e
`.1 - I
`
`srflme Visual
`.12, Aussois.
`
`0008