Page 1 of 21
`
`SAMSUNG EXHIBIT 1006
`Samsung v. Image Processing Techs.
`
`

`

`f
`
`APPLIED
`ARTIFICIAL
`Si
`INTELLIGENCE
`AN INTERNATIONAL JOURNAL
`
`EDITOR-IN-CHIEF:
`Robert Trappl
`Austrian Research Institute for Artificial
`Intelligence and University of Vienna
`EDITORIAL ASSISTANT:
`Gerda Helscher
`
`ASSOCIATE EDITORS:
`Howard Austin Concord, MA, USA
`Ronald Brachman AT&T Bell Laboratories,
`Murray Hill, NJ, USA
`Stefano Cerri Mario Negri Institute, Milan, Italy
`Larry R. Harris Artificial Intelligence
`Corporation, Waltham, MA, USA
`Makoto Nagao Kyoto University, Japan
`Germogen S. Pospelov Academyof Sciences,
`Moscow, Russia
`Wolfgang Wahlster University of the
`Saarlandes, Saarbruecken, Germany
`William A. Woods Applied Expert Systems,
`Inc., Cambridge, MA, USA
`
`EDITORIAL BOARD:
`Luigia Carlucci Aiello, University of Rome, Italy;
`Leonard Bolc, University of Warsaw, Poland; Ernst
`Buchberger, University of Vienna, Austria; Jaime
`Carbonell, Carnegie-Mellon University, Pittsburgh,
`PA, USA; Marie-Odile Cordier, IRISA, University
`of Rennes, France; Helder Coelho, LNEC, Lisbon,
`Portugal; Herve Gallaire, ECRC, Munich, Germany;
`Tatsuya Hayashi, Fujitsu Laboratories Ltd.,
`Kawasaki, Japan; Werner Horn, University of
`Vienna, Austria; Margaret King, Geneva University,
`Switzerland; Dana S. Nau, University of Maryland,
`College Park, MD, USA; Setsuo Ohsuga,
`University of Tokyo, Japan; Tim O'Shea, Open
`University, Milton Keynes, UK; Ivan Plander,
`Slovak Academy of Sciences, Bratislava,
`Czechoslovakia; Johannes Retti, Siemens A. G.
`Oesterreich, Vienna, Austria; Erik Sandewall,
`Linképing University, Sweden; Luc Steels, Free
`University of Brussels, Belgium; Oliviero Stock,
`IRST, Trento, Italy; Harald Trost, University of
`Vienna, Austria; Bernard Zeigler, University of
`Arizona, Tucson, AZ, USA.
`
`AIMS AND SCOPE: Applied Artificial Intelligence
`addresses concerns in applied research and applications
`ofartificial intelligence (AI), The journal acts as a me-
`dium for exchanging ideas and thoughts about impacts of
`Al research. Papers should highlight advances in uses of
`expert systems for solving tasks in management, indus-
`try, enginecring, administration, and education; evalua-
`tions of existing AI systems and tools, emphasizing com-
`parative studies and user experiences; and/or economic,
`social, and cultural impacts of AI. Information on key
`applications, highlighting methods,
`time-schedules,
`la-
`bor, and other relevant material is welcome.
`Abstracted and/or Indexed in: Engincering Infor-
`mation, Inc. and by INSPEC.
`
`Editorial Office: Robert Trappl, Austrian Research In-
`stitute for Artificial Intelligence, Schottengasse 3, A-1010,
`Vienna, Austria; and University of Vienna.
`Publishing, Advertising, and Production Offices:
`Taylor & Francis, 1101 Vermont Ave., Suite 200, Wash-
`ington, DC 20005, phone (202)289-2174, fax (202)289-
`3665, Susan Connell, Production Editor; or Taylor &
`Francis Ltd., Rankine Rd., Basingstoke, Hampshire RG24
`OPR, UK. Subscriptions Office: 1900 Frost Rd., Suite
`101, Bristol, PA 19007, phone (215)785-5800,
`fax
`(215)785-5515; or Taylor & Francis Ltd., Rankine Rd.,
`Basingstoke, Hampshire RG24 OPR, UK, phone +44-
`256-840366, fax + 44-256-479438.
`Applied Artificial Intelligence (ISSN 0883-9514) is
`published quarterly by Taylor & Francis Ltd., 4 John
`Street, London WCIN 2ET UK. Annual 1993institutional
`subscription UK £111, US $190. Personal subscription
`rate UK £56, US $91; available to home address only and
`must be paid for by personal check or credit card.
`Second-class postage paid at Jamaica, NY 11431. U.S.
`Postmaster: Send address changes to Applied Artificial In-
`telligence, Publications Expediting Inc., 200 Meacham
`Avenue, Elmont, NY 11003.
`Dollar rates apply to subscribers in all countries except
`the UK and the Republic of Ireland, where the sterling
`price applies. All subscriptions are payable in advance and
`all rates include postage. Subscriptions are entered on an
`annual basis, i.e., January to December. Payment may be
`made by sterling check, dollar check, international money
`order, National Giro, or credit card (AMEX, VISA,
`Mastercard/Access).
`Orders originating in the following territories should be
`sent directly to: Australia—R. Hill & Son, Ltd., Suite 2,
`119 Gardenvale Road, Gardenvale, Victoria, Australia
`3185. India— Universal Subscription Agency Pvt. Ltd.,
`101-102 Community Centre, Malviya Nagar Extn., Post
`Bag No. 8, Saket, New Delhi. Japan—Kinokuniya Com-
`pany, Ltd., Journal Department, P.O. Box $5, Chitose,
`Tokyo 156. New Zealand—R. Hill & Son, Ltd., Private
`Bag, Newmarket, Auckland 1, USA, Canada, and
`Mexico—Taylor & Francis, 1900 Frost Road, Suite 101,
`Bristol, PA 19007, USA. UK andall otherterritories—
`Taylor & Francis Ltd., Rankine Road, Basingstoke,
`Hampshire RG24 OPR, England.
`Copyright © 1993 by Taylor & Francis. All rights re-
`served. Printed in the United States of America. Authori-
`zation to photocopy items for internal or personal use, or
`the internal or personal use of specific clients, is granted
`by Taylor & Francis for libraries and other users registered
`with the Copyright Clearance Center (CCC) Transactional
`Reporting Service, provided that the base fee of $10.00
`per copy, plus .00 per page is paid directly to CCC, 27
`Congress St., Salem, MA 01970, USA,
`The publisher assumes no responsibility for any state-
`ments of fact or opinion expressed in the published papers
`or in the advertisements. Applied Artificial Intelligence
`is owned by Taylor & Francis.
`
`Printed on acid-free paper, effective with Volume 7, Number 1, 1991.
`SAMSUNG EXHIBIT 1006
`Page 2 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 2 of 21
`
`

`

`APPLIED
`ARTIFICIAL
`INTELLIGENCE
`
`
`UNIVERSITY OF CALIFORNIA}
`DAVIS
`,
`
`=
`
`AN INTERNATIONAL JOURNAL
`|__SEA. REG. Lisnany Volume 7
`meIBRARYstaeh ber 4
`4993
`
`Special Issue
`Artificial Intelligence: Future, Impacts, Challenges
`Part 3
`
`CONTENTS
`
`iil
`
`1
`
`15
`
`29
`
`39
`
`59
`
`87
`
`
`SPECIAL ISSUE ON ARTIFICIAL INTELLIGENCE: FUTURE, IMPACTS,
`
`CHALLENGES (PART3)
`Robert Trappl
`
`
`
`SOME SEMIOTIC REFLECTIONS ON THE FUTURE OF ARTIFICIAL
`INTELLIGENCE (Julian Hilton
`
`MODELING OF DEEDS IN ARTIFICIAL INTELLIGENCE SYSTEMS
`L] Dimitri A. Pospelov
`
`THE HIDDEN TREASURE (CJ Ernst Buchberger
`
`A DEEPER UNITY: SOME FEYERABENDIAN THEMES IN
`NEUROCOMPUTATIONAL FORM (1 Paul M. Churchland
`
`HOW CONNECTIONISM CAN CHANGE AI AND THE WAY WE THINK
`ABOUT OURSELVES LU) Georg Dorffner
`
`THE FUTURE MERGING OF SCIENCE, ART, AND PSYCHOLOGY
`{] Marvin Minsky
`
`109
`
`APPLIED ARTIFICIAL INTELLIGENCE CALENDAR
`
`SAMSUNG EXHIBIT 1006
`Page 3 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 3 of 21
`
`

`

`|}
`
`EYES DETECTION FOR FACE
`RECOGNITION
`
`LUIGI STRINGA
`Istituto per la Ricerca Scientifica e Tecnologica, 38100
`Trento,Italy
`
`A correlation-based approach to automatic face recognition requires adequate normalization
`techniques. If the positioning of theface in the image is accurate, the needfor shifting to ob-
`tain the best matching between the unknown subject and a template is drastically reduced,
`with considerable advantages in computing costs. In this paper, a novel technique is presented
`based on a very efficient eyes localization algorithm. The technique has been implemented as
`part of the “electronic librarian” ofMAIA, the experimental platform of the integrated Al
`project under development at IRST. Preliminary experimental results on a set of220facial im-
`ages of55 people disclose excellent recognition rates and processing speed.
`
`INTRODUCTION
`
`There is a growing interest in face-processing problems (Young andEllis, 1989).
`The recognition of human facesis in fact a specific instance of 3D object recognition—
`possibly the most important visual task—and provides a most interesting example of
`how a 3Dstructure can be leamed from a small set of 2D perspective views. Moreover,
`amongseveral practical reasons for developing automatic systems capable of recogniz-
`ing human faces, faces provide a natural and reliable means for identifying a person.
`The first examples of computer-aided techniques for face recognition date back
`to the early 1970s and were based on the computationof a set of geometrical features
`from the picture of a face (Goldstein et al., 1971, 1972; Harmon, 1973). More
`recently the topic has undergonea revival (Samaland Iyengar, 1992), and different
`applications have been developed based on various techniques, such as template
`matching (Baron, 1981; Yuille, 1991), isodensity maps (Nakamura etal., 1991;
`Sakaguchietal., 1989), or feature extraction by neural and Hopfield-type networks
`(Abdi, 1988; Cottrell and Fleming, 1990; O’Toole and Abdi, 1989). At presentit is
`still rather difficult to assess the state of the art. However, a first significant
`evaluation is reported in (Brunelli and Poggio, 1991), where a comparison of
`different techniques is performed on a common database—the best results were
`obtained with a template matching type technique.
`Following a correlation-based approach, excellent results have also been ob-
`tained with a procedure recently developedforthe “electronic librarian” of MATA,
`the experimental platform of the integrated AI project under development at IRST
`(Poggio and Stringa, 1992; Stringa, 1991a). The procedure is based on the analysis
`of filtered edges and grey-level distributions to allow a comparison of the directional
`
`The author’s e-mail address is stringa@irst.it
`
`Applied Artificial Intelligence: 7:365-382, 1993
`Copyright © 1993 Taylor & Francis
`0883-9514/93 $10.00 + .00
`
`365
`
`SAMSUNG EXHIBIT 1006
`Page 4 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 4 of 21
`
`

`

`366
`
`L. Stringa
`
`derivatives of the entire image (Stringa, 1991d). On a set of 220 frontal facial images
`of 55 people, a recognition rate of 100% wasobtained,at a processing speed of about
`1.25 sec per face on an HP 350 workstation. A second set of experiments, using
`binary derivatives, disclosed excellent
`improvements in computing time: with a
`two-layer S_Net [see Stringa (1990)] the processing speed was reduced to less than
`0.05 sec per face (Stringa, 1991e).
`Such performance provides evidenceforthe validity of the approach. Moreover,
`the procedure proved very efficient with respect to the task of rejecting “unknown”
`faces, i.e., faces of subjects that are not included in the database. Apart from high
`recognition rates, low processing costs, and good flexibility under variable condi-
`tions, this is another important feature for a real (i.e., industrially applicable) face
`recognition system.
`It must also be stressed, however, that such performance dependsonthe use of very
`effective normalization, registering, and rectification techniques.Thisis in fact a general
`requirementfor any correlation-based approachto face recognition (and more generally
`to 3D object recognition), particularly when the image to be recognized is freshly
`captured with a video camera rather than scanned from a standardized photograph. In
`general it is rather natural to expect the user to look straight into the camera, for even
`in human interaction people tend to turn their heads so as to look at each other in the
`eyes. However, a certain flexibility must be tolerated concerning such variable factors
`as the distance and position ofthe user’s face from the camera. Hence, some adjustment
`and normalization is necessary before the system can proceed to the recognition step
`by comparing the input image with the available set of prototypes.
`In our procedure, the normalization of the image to be recognized is obtained
`by first locating the position of the eyes and then rotating the image so asto align
`them horizontally. As a result, the need for shifting to obtain the best matching
`between the unknownface and a template is drastically reduced, with considerable
`advantages in computing time. In particular, the eyes localization algorithm de-
`velopedforthis purpose (Stringa, 1991c) proves very sensible, allowing very precise
`positioning of both pupils for each facial image includedin the data base,
`The purposeofthis paper is to illustrate this algorithm in detail. To emphasize
`better its crucial role for correlation-based facial recognition tasks, a brief outline
`of the system developed at IRSTis first given, along with the experimental scenario
`that led to its formulation. The eyes localization algorithm is then fully described.
`Thefinal sections report on the current experimental results obtained and offer some
`general remarkson the algorithm’s performance.
`
`OUTLINE OF THE SYSTEM
`
`General Background: The MAIAElectronic Librarian
`
`Asalready mentioned, the reported work is part of a more general AI project
`(labeled MAIA, acronym for “Modello Avanzato di Intelligenza Artificiale’’) pres-
`
`SAMSUNG EXHIBIT 1006
`Page 5 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 5 of 21
`
`

`

`Eyes Detection for Face Recognition
`
`367
`
`ently under developmentat IRST. Schematically, the goal of the project is to develop
`an integrated experimental platform whose main “tentacles” include mobile robots
`capable of navigating in the corridors of IRST, an automatic “concierge” answering
`visitors’ questions about the Institute, and an electronic “librarian” capable of
`managing book loans and returns and/or locating volumes requested by the user (or
`indicating in which office they may be found).
`In this context, a system for automatic face recognition is required specifically
`with respect to the librarian’s first task, i.e. managing loans and returns (a similar
`system will later be implemented in the automatic concierge). The electronic
`librarian must in fact be capable of identifying any user that might wish to borrow
`or to return a bookso as to ensure that only registered personnel can have accessto
`the IRST library. And for this purpose, the user is simply expected to stand in front
`of the system and look into a video camera. (In fact, our project is to use both face
`and speaker recognition techniques,so as to further improvethe system’sreliability.
`In the following, however, the focus will be exclusively on the vision component.)
`The experimental scenario is therefore very unconstrained. No particular effort
`is required to ensure perfectly frontal images, and the distance of the subject from
`the cameraas well as the location ofhis/her facein the image are only approximately
`
`MAIA
`
`Updating
`
`Loans &
`Returns
`
`sevice
`
`Book
`Recognition
`
`Person
`identification
`
`v
`Speaker
`Recognition
`
`Face
`Recognition
`
`
` Bibliographic
`Consultancy Catalogue
`
`
`
`Detection
`
`DE
`
`“AY Recognition
`
`FIGURE 1. Functional diagram of the MAIA system and someofits tasks. Shaded blocks (con-
`nected by black arrows) indicate the contextual backgroundof the application described in
`the paper.
`
`SAMSUNG EXHIBIT 1006
`Page6 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 6 of 21
`
`

`

`368
`
`L. Stringa
`
`fixed. This means that the system must be highly tolerant against variations of the
`head size and orientation. Moreover, background andillumination are not assumed
`to be constant: artificial light is used to illuminate the user’s face from the front, but
`the experimental environment is also exposed to sun light through numerous
`windows.
`
`Face Detection and Eyes Localization
`
`Asis clear from the above, a most important feature of the system is that it must
`be capable of recognizing dynamic facial images,i.e. “live” images acquired by the
`librarian through a video camera. This is a general requirement of the MAJAproject
`and a compelling prerequisite for most industrial applications.
`To detect the user’s face from the background,the system makesuse of a motion
`detection algorithm originally introduced in (Stringa, 1991b) and refined in (Mes-
`selodi, 1991). This is based on the general! fact that a basic stimulus in the analysis
`of a dynamic scenelies in detecting “differences” between successive images; the
`algorithm proceeds by comparing pairs of sequential images captured by the camera
`and segments from the background those objects that determine a significant
`variation in the images’ matrices. Despite its simplicity, it performs well, allowing
`detection of faces in almostreal time (about 3 images/sec) and showing a remarkable
`independence from background and illumination conditions.
`is then adjusted and
`The image of the face, detected from the background,
`normalized before the system can proceed to the recognition algorithm. As we
`mentioned, in fact, this follows a template matching strategy and is formalized as a
`
`distance-based comparison between the directional derivatives of the input image
`
`FIGURE 2. Face detection: the algorithm detects the “differences” between successive input
`images(left) to extract the edgesof the face(right).
`
`SAMSUNG EXHIBIT 1006
`Page7 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 7 of 21
`
`

`

`Eyes Detection for Face Recognition
`
`369
`
`(the face to be recognized) and those memorized in a data-base of templates or
`prototypes covering each subject known tothe system. It is therefore important—as
`in any correlation-based approach—that the face be accurately positioned in the
`image. Otherwise the need for shifting required to obtain the best matching between
`the subject and a template could increase considerably, with obvious disadvantages
`in terms of computingcosts.
`The solution adopted in the present application is based on a technique that
`localizes the position of the eyes and then align them horizontally. Eyes are in fact
`a most prominent facial feature and can be detected with fair accuracy. Their
`localization is then usedto register, rectify, and normalize the image with respectto
`the distance of the pupils, yielding a “standard” matrix that can easily be compared
`with the templates.
`Various approaches can be used for the purpose of locating the position of the
`eyes. For instance, in Baron (1981) a procedure is used whereby a certain number
`of eye templates are correlated against suitable subimages of the input image; a
`correlation value greater than a fixed threshold is then taken to indicate that an eye
`is successfully located. Our approachis different. It does not proceed by eye template
`matching. Rather, an algorithm is used based on the exploitation of (a priori)
`anthropometric information combined with the analysis of suitable grey-level
`distributions, allowing direct localization of both eyes.
`On the one hand, there exists a sort of “grammar” of facial structures that
`provides somevery basica priori information usedin the recognition of faces. Every
`human face presents a reasonable symmetry, and the knowledgeof therelative
`position of the main facial features (nose between eyes and over mouth,etc.) proves
`very useful to discriminate among various hypotheses. These guidelines can be
`derived from anthropometric data corresponding to an average face and refined
`through the analysis ofreal faces, Some typical examples [based on studies on face
`animations and reported in Brunelli (1990)] are:
`
`*
`
`e
`*
`*
`
`the eyes are located halfway between the top of the head and the bottom of the
`chin;
`the eyes are about one eye width apart;
`the bottom of the nose is halfway between the eyebrowsandthe chin;
`the mouthis typically located one third of the way from the bottom of the nose
`to the bottom ofthe chin.
`
`On the other hand, the algorithm exploits the discriminating power of the
`distribution of the image’s edges (specifically leading edges, i.e. transitions from
`dark to bright) upon adequatefiltering. The primary motivationis that edge densities
`convey most of the information required to identify those facial zones that are
`characterized by abrupt changes in imagebrightness[see, e.g., (Kanade, 1973)]. In
`particular, eyes are typically the moststructured areaofa face, and their location in
`
`SAMSUNG EXHIBIT 1006
`Page8 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 8 of 21
`
`

`

`370
`
`_—_L. Stringa
`
`the imageis therefore characterized by a high numberof edges. These determine a
`prominent peak in the edges’ vertical projection that can be indicative of the rough
`localization of the eyes.
`The approachis schematically illustrated in Figure 3, where Rsy and Rsx are the
`vertical and horizontal resolution (number of lines and columns in the image)
`respectively.
`Thelocalization of the eyes proceeds from the preliminary approximate local-
`ization of the eyes-connecting line, centered on the maximum (Z) of the filtered
`vertical histogram, and of the face’s main traits, specifically the face’s side limits
`(X, and X,) and the nose axis (X,). These are not searchedfor in the entire image but
`only on those areas that correspondto appropriate “expectation zones’. Onthisbasis,
`the search areas for the two eyes can be estimated with reasonable accuracy. Their
`exact localization is then obtained by computing the horizontal and vertical coor-
`dinates of a pixel belonging to the corresponding pupils.
`
`EYES LOCALIZATION: DETAILED DESCRIPTION
`
`Preliminaries
`
`A detailed description of the eyes localization algorithm is givenin the following
`paragraphs. For convenience, wefirst introduce some general notions that will be
`used throughout.
`
`H(x)
`
`Ray-1
`
`FIGURE 3. The eyeslocalization algorithm exploits the discriminating poweroffiltered edges
`and grey-level distributions.
`
`SAMSUNG EXHIBIT 1006
`Page 9 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 9 of 21
`
`

`

`371
`
`Eyes Detection for Face Recognition
`
`
`
`FIGURE 4. The search areasfor the eyes (indicated by two rectangular regions) are based on
`the approximate location of the eye-connectingline, of the face sides, and of the nose axis.
`
`Let /(x,y) be the input image, digitized at 256 levels of grey into a matrixofsize
`Rsx (wide) by Rsy (high) pixels. The binary matrix E(x,y) describing the horizontal
`leading edges of I(x,y) is computed using a thresholded directional derivative. This
`is defined as
`
`
`
`E(x,y)=1 if | (x,y) -—I(x- Ly) >7,,/C (1)
`
`
`
`0 otherwise
`
`where/,, is the average value of /(x,y) and C is a constant parameter. In general, the
`exact value of C will depend on the resolution of /(x,y).
`
`
`
`FIGURE 5. Once the eyes have been exactly localized, the image is parametrically registered,
`rectified, and normalized with respect to the distance of the pupils to produce a “standard”
`matrix.
`
`SAMSUNG EXHIBIT 1006
`Page 10 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 10 of 21
`
`

`

`372
`
`L. Stringa
`
`The projection of the horizontal leading edges along the vertical axis defines
`the vertical histogram H(y). This is computed from E(x,y) by taking the value of
`H(y) at any point y on the vertical axis as the sum ofall the leading edges of the
`corresponding horizontal line:
`
`Hy) = >) Ey)
`
`Finally, given a function f(x), the following filteredfunctions are defined:
`
`f(x) = erLoe“2
`
`FolX) = frlX) — Frn(2x)
`
`(2)
`
`)
`
`(4)
`
`Here j, m, and n are constant parameters whose specific values depend on what f is
`meant to extract: fx) is the result of filtering f(x) on 2 j+1 samples, and f,,,(x) is
`the result of purging f(x) with a pass-bandfilter based on f,(x) and fin(x).
`
`Rough Localization of the Line Connecting the Eyes’ Pupils
`
`Using the above definitions, the first step of the algorithm is the rough localiza-
`tion of the line connecting the eyes’ pupils, which allows the construction of an
`approximate model of the face using anthropometric standards.
`The technique used for this purpose proceeds from the idea thatthe analysisof the
`vertical projection of the horizontal edges identifies the location of significant, highly
`structured features. The higher the peak, the more structured the feature. Eyes are the
`most structured part of a person’s face. Hence, their location determines a most
`prominentpeak in the grey-level projection. Moreover, they are expected to be located
`somewhat below the headtop, as the anthropometric guidelines reported in (Brunelli,
`1990) suggest. The head top, Y,, can be computed directly from the edge of the face
`given by the face detection algorithm, while the upperboundofthe search area for the
`eyes is an anthropometric parameterA relative to the size of the face.
`As a first rough approximation,
`the eye-connecting line can therefore be
`identified with the y-coordinate of the highest projection peak relative to this
`expectation zone. Moreexactly, this is done by searching for the Zth horizontal line
`of the matrix, where Z is the ordinate of the maximum ofthe filtered vertical
`histogram in the search area:
`
`Rsy-1
`A(Z) = maxy Han(y)
`
`(5)
`
`SAMSUNG EXHIBIT 1006
`Page 11 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 11 of 21
`
`

`

`Eyes Detection for Face Recognition
`
`373
`
`Note that Z is defined relative to the fi/tered histogram H,,.,(y). The analysis of
`H(y) could already be very useful in determining the position of the eye-connecting
`line. However, some care is required to minimize misleading interferences such as
`high frequency noise or extensive areas with a high numberof constant or quasi-
`constant brightness transitions. Accordingly, a band-passfilter is applied to purge
`the histogram from such disturbances, and the filtered histogram H,,,(y) is used
`instead of H(y) (for suitable values of m and 7).
`In case there exists some other value of H,,,(y) that is significantly high,i.e. if
`there exists somepoint Z’ such that
`
`HAZ’) > K « H(Z)
`
`(K < 1 constant)
`
`(6)
`
`the eye-connectingline is identified with the value Z or Z’ which is mostplausible,
`relative to its distance from the head top Y,, on the basis of the expected position of
`the eyes in a “standard face.”
`
`Rough Localization of the Face’s Side Limits
`
`This and the next step are aimed at characterizing the relative “expectation
`zones” of the two eyes: the searchareafor the left eye will be restricted to a region
`betweentheleft limit of the face and the nose, while the search area for the right eye
`will be restricted to a region between the nose andthe rightlimit.
`It is clear that for this purpose it is not necessary to perform the search of the
`side limits on the entire image. Since the eyes’ expectation zones will be centered
`on the approximate eye-connecting line (calculated with the method indicated
`
`above), what is neededis the position ofthe side limits of the face relative to a region
`
`FIGURE6. Asa first approximation, the eye-connecting line is defined as the ordinate (Z) of
`the maximum of thefiltered vertical histogram.
`
`SAMSUNG EXHIBIT 1006
`Page 12 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 12 of 21
`
`

`

`374
`
`L. Stringa
`
`centered on this line. In some cases these may not coincide with the “true” limits:
`the outermost extremities of a face could easily be located near the head top or,
`perhaps,far below,at the mouth level(as in people with pronounced jaws). However,
`for the present purposes such facial features need not be considered, and the
`algorithm performance can be improved byrestricting the search area to the
`indicated region.
`Let this region be defined by the interval Z — Op : Z + Uo, where Oy and Us are
`fixed parameters (defining the search area Over and Underthe eyes). Relative to
`this region, the rough localization of the side limits is determined with reference to
`the face detection algorithm described in Face Detection and Eyes Localization. The
`detection algorithm extracts the edges of the face (see Fig. 2), and the abscissae of
`the leftmost and rightmost edge points in the interval Z — Oy: Z + Uo, which we
`denote by X, and X,, can be taken to define the abscissae ofthe left and right side of
`the face, respectively.
`It is worth observing that this approach does not require any constraint on the
`experimental set-up. An alternative method, based on the assumption that the
`experiments be performed onalight background,has also been investigated, though
`it has not been used for the MAIAlibrarian. This alternative approach moves from
`the remark that, on a light background, the side limits of the face are typically
`localized in those areas in the image that are characterized by abrupt changes in
`brightness, corresponding to the transition from background to object. To locate
`them approximately, the following operations can therefore be performed.First, the
`image’s horizontal average density A(x) is computedrelative to the search region.
`This is obtained by taking the value of A(x) at any point x on the horizontal axis as
`the normalized sum ofall the values of the correspondingvertical line in the interval
`Z- Oo :Z+U0.
`
`A(x) =
`
`Z+Uo
`
`
`l
`
`Us + Oo 1 Ze)
`
`=
`
`Second, A(x)is filtered on 2p + 1 samples (p a fixed parameter) to produce the
`filtered density A,(x) as defined in Eq. (3). A glimpseat the example in Fig. 7 will show
`the typical behaviorofthis function; on a light background,the face limits are expected
`to coincide with the leftmost and rightmostsignificant brightness changes in the image,
`and these correspondto the lowest valuesofthe filtered average density A,(x).
`On this basis, the horizontal coordinates of the side limits can easily be
`determined. Assuming the face to be roughly centered in the image, we can locate
`the search area for these points within a certain interval centered on Rsx/2. Let A,
`and A, be the left and right extremaof this interval respectively. The left side of the
`face can then be defined as the abscissa X, of the minimum ofA,(x) in the left portion
`of the interval:
`
`SAMSUNG EXHIBIT 1006
`Page 13 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 13 of 21
`
`

`

`Eyes Detection for Face Recognition
`
`375
`
`FIGURE 7. Approximate localization of the left (Xs) and right (Xa) face sides.
`
`Rsxl2
`A,(X;) = min , A,(x)
`
`(8)
`
`while the right side can be defined as the abscissa X, of the minimum ofA,(x) in the
`right portion:
`
`4,
`A(X.) a min x A,(x)
`Rsxi2
`
`(9)
`
`As we mentioned, this alternative procedure has not been implementedin the
`MAIAlibrarian due to the limiting assumption on the light background. However,
`our experiments have shown that when this assumptionissatisfied, the procedure
`yields essentially the same results as that based directly on the face detection
`algorithm.
`
`Rough Localization of the Nose’s Axis
`
`This step is similar to the previous one. With reference to our figures, note that
`whereasthe face limits are usually darker in the image, the nose is normally lighter
`than the left and right regions of the facial image and determines a prominent peak
`in A,(x). Accordingly, our approachis to base the search for the nose’s axis on the
`maximum value of A,(x).
`Consideringthat the nose is expected to be located somewhere halfway between
`the face sides, the search area for its axis can safely be restricted to a central region
`comprised between the two vertical lines X, and X, calculated as above. Moreover,
`since the input image is assumed to provide a frontal view of the face (albeit not a
`
`SAMSUNG EXHIBIT 1006
`Page 14 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 14 of 21
`
`

`

`376
`
`L. Stringa
`
`perfectly frontal one), it is not necessary to considerthe entire interval X, : X,. The
`search area can be further restricted to a region localized at a certain distance D,
`from X, and X4. Based on standard anthropomorphic guidelines, and considering that
`the eyes are usually one eye width apart (Brunelli, 1990), this distance can roughly
`be assessed at one fourth of the above-mentioned interval:
`
`D, = =—>
`
`Using Eq.(10), the nose vertical axis X,, is then defined as
`
`Xg-Dy
`A,(X,) = max ,A,(x)
`x,+D,
`
`(10)
`
`(11)
`
`i.e. as the abscissa of the maximum ofthe filtered density A,(x)in the interval X, +
`D,:X.—-D,.
`
`Detection of the Pupil’s Coordinates
`
`Thisis the final step. Using the approximatelocation of the eye-connectingline, of
`the face sides, and ofthe nose axis, the expectation zones ofthe two eyes can be estimated
`with reasonable accuracy. Their exactlocalization is then obtained by computing the
`horizontal and vertical coordinates of a pixel belonging to the corresponding pupils.
`
`i,
`
`A,(x)
`
`'
`
`|
`
`1
`
`!
`
`Ke
`
`:
`
`nose
`
`:
`
`Xa
`
`FIGURE 8. Approximate location of the nose’s axis (Xn).
`
`SAMSUNG EXHIBIT 1006
`Page 15 of 21
`
`SAMSUNG EXHIBIT 1006
`Page 15 of 21
`
`

`

`Eyes Detection for Face Recognition
`
`377
`
`Left Pupil
`
`Asshownin Fig. 9, the left eye is expected to be located within a region centered
`on the approximate eye-connecting line and comprised betweenthe left limit of the
`face and the nose axis. Moreprecisely, the searchareais restricted to the rectangular
`region defined by the intervals Z —L,
`: Z + L, (high) and X, — L, : X, — Ls (wide),
`where each L;is a suitable parameter.
`Relative to this area, the search of the pupil is based on the analysis of the
`horizontal grey-level distribution. For each line y, the relative horizontal density
`G’(x) is calculated and a band-passfilter is applied to eliminate misleading inter-
`ferences and high frequencynoise. This is obtained as in Eq. (4):
`
`Gi(x) = Gx) -— Gi)
`
`(12)
`
`wherethe valuesof r and s are based on the a priori knowledgeoftherelative position
`of sclera, cornea, and pupil in the eyeball. The second derivative ¢’(x) is then
`calculated as
`
`g(x) =
`
`d'G)(x)
`
`dx
`
`(13)
`
`The secondderivative allows those areas where the brightness changesare most
`rapid to be detec