Apparatus for identifying a person using facial features

[0002] This is a divisional application of Ser. No. 08/343,543, filed Nov. 29, 1994, U.S. Pat. No 5,995,639.

[0003] The present invention relates to apparatus for identifying persons such as identifying persons by their face images in their admission to a room or searching and outputting the name of a person whose face image resembles an input face image.

[0004] As a prior apparatus for identifying persons by their face images there is one described in Japanese Pat. laid-open Publication No. Sho 63-177273. The composition of that apparatus is described in the following.

[0005] FIG. 15 shows a block diagram showing a composition of the prior apparatus for identifying persons by their face images. In the FIG., 21 is an image input section that inputs a face image, 22 is a feature-points extracting section comprising an analog-to-digital converter, a central processor, and a memory, 23 is a personal database section that records people's feature points on cards or the like, 24 is a judgment section that uses the feature-points information of above feature-points extracting section 22 and the feature-points information of personal database section 23 to detect their difference and identifies the person having that face image as the person of personal database 23 based on the test whether the difference is greater than a threshold value or not.

[0006] The above prior technology extracts, in feature-points extracting section 22, feature points of a person's face image input from image input section 21 and detects, in judgment section 24, the differences between these feature points and the feature points of a face image registered in personal database section 23, and identifies the person based on the amount of the difference. In this case, if the sizes of the two images are different, or if their photographing angles are different, then the differences in the feature points become great, so that even the same person is identified as a different person. In order to avoid such a situation, it was necessary to fix the distance between the image input section and a photographed person and to make him or her face turned straight toward the front. However, this method of inputting a face image imposes a burden on the photographed person, and no matter how hard the person tries to turn straight to the front, a slight rotation and inclination are inevitable, so that it was difficult to obtain an image exactly facing the front.

[0007] The basic object of the present invention is to provide an apparatus for identifying persons having high discriminating power.

[0008] Another object of the present invention is to provide an apparatus for identifying persons that performs identification with high accuracy against minor fluctuations of photographing conditions such as illumination conditions and the position of the face.

[0009] In order to achieve the aforementioned objective, the present invention extracts feature points of face components such as the eyes, nose, mouth, and uses the extracted feature points to divide a face image into small patches of, for example, triangles and describe a face image as the set of these patches. Then a feature amount is extracted for each patch and the set of extracted feature amounts is used to identify the face image of a person. As a feature amount, the average brightness of each patch can be used. In this case, the face image is treated as a monochromatic image, so that the processing can be simplified, and the image formed by obtained patches having graded brightnesses sufficiently reflects the characteristics of the face, that is, concavo-convexity, flatness, curvature and the like are indirectly expressed. Therefore, by using these features, identification of a person can be performed accurately. Besides average brightness, the difference in brightnesses between adjacent patches can be used as a feature amount.

[0010] A practical method applies a standard structure model that describes a standard face image as a set of patches. When the feature points of an input face image is extracted, they are compared with the feature points of the standard structure model, and the standard structure model is deformed and adjusted based on the extracted feature point information, to obtain an adjusted structure model corresponding to the input face image. The adjusted structure model obtained in this way is expressed as a set of patches as described above, and a feature amount is extracted for each patch.

[0011] The extracted feature amounts are compared with the feature amounts of each person in the personal database to detect the degree of agreement by calculating a distance between the feature amounts. In case of confirming a specific person, the extracted feature amounts are compared with the feature amounts of the specific person. In case of searching for identification, the extracted feature amounts are successively compared with the data stored in the personal database to extract a face image having a large degree of agreement.

[0012] The standard structure model may be either 2-dimensional or 3-dimensional. In the 3-dimensional case, if the normal vector of each patch is extracted as well as its brightness, then the concavo-convexity of the face is expressed more clearly, and the position of the light source can be estimated from the distribution of the brightnesses, so that correction depending on the position of the light source can be made possible. Further, if the face is slightly inclined against the camera, errors due to the inclination can be prevented by a correction such that the brightness distribution becomes bilaterally symmetric.

[0013] The characteristics and objects of the present invention will become clear from the following description taken in conjunction with the preferred embodiments thereof with reference to the accompanying drawings.

[0014] FIG. 1 is a system configuration diagram of an apparatus for identifying persons in accordance with the present invention.

[0015] FIG. 2 is a block diagram of an embodiment of an apparatus for identifying persons in accordance with the present invention.

[0016] FIG. 3 is an illustration showing feature points of a face.

[0017] FIGS. 4, 5, 6 and 7 are enlarged illustrations respectively showing feature points of an eyebrow, eye, nose, and mouth.

[0018] FIG. 8 is an illustration showing a distribution of extracted feature points.

[0019] FIG. 9 is an illustration showing the frame structure of a standard structure model.

[0020] FIG. 10 is an illustration showing the frame structure of the result obtained by deforming and adjusting the standard structure model based on extracted feature points.

[0021] FIG. 11 is an illustration showing a system diagram of an apparatus for identifying persons in accordance with the present invention.

[0022] FIG. 12 is a flowchart of extracting feature points.

[0023] FIG. 13 is an illustration for describing a linear interpolation of a vertex.

[0024] FIG. 14 is a block diagram showing another embodiment of an apparatus for identifying persons in accordance with the present invention.

[0025] FIG. 15 is block diagram showing the composition of a prior apparatus for identifying persons.

[0026] In the following is described embodiments of the present invention.

[0027] <System Configuration>

[0028] The hardware of an apparatus in accordance with the present invention is, as shown in FIG. 1, basically comprised of an image input section 2 consisting in a TV camera 1 that takes a picture of a person to be identified and an image processing section 4 comprising a microcomputer 3 to which the data of a face image photographed by TV camera 1 is input. The image processing section 4 has, in addition to microcomputer 3, a display 5 that displays necessary information, a printer 6 that records necessary information, an operation means 8 comprising a keyboard 7, a mouse (not illustrated) and the like for operating microcomputer 3.

[0029] <Functional Block Composition>

[0030] FIG. 2, which shows a first embodiment of the present invention, extracts, as functions, the contents of image processing that is performed by microcomputer 3 for an input face image, and expresses the functions as a block diagram.

[0031] Face image data input from image input section 2 is first stored in an image memory 12, and a feature points extracting section 13 extracts feature points from the stored face image, as described in the following. Here, the term “feature point” means a predetermined point for specifying an individual component such as an eye, nose, mouth, head, and cheek. Therefore, the extraction of feature points means, for example, to detect where the center of the pupil of an eye is located in an input face image, and the characteristics of an individual face are described by detecting the position information of individual feature points. FIGS. 4, 5, 6 and 7 respectively show the feature points of an eyebrow, eye, nose and mouth in details. The method of extracting feature points is described later. FIG. 8 shows an example of extracted feature points.

[0032] Feature points, whose positions are specified by feature points extracting section 15 are individually compared with the feature points of a predetermined standard structure model of a face, and the standard structure model is deformed and adjusted so that an individual feature point of the standard structure model becomes in agreement with the corresponding extracted feature point.

[0033] The standard structure model is sometimes called a standard wire model, and as exemplified in FIG. 9, the standard face image is divided into many small patches and approximately expressed as the set of the patches. Each patch may be a polygon, but a triangle is preferably used for ease of processing, as shown in FIG. 5. A concrete method of adjusting is described later. FIG. 10 shows an adjusted result obtained from the standard structure model of FIG. 7 using the extracted feature points shown in FIG. 8. In the following, a structure model obtained by the adjustment is called adjusted structure model.

[0034] Back to FIG. 2, a feature amounts extracting section 16 cuts out the part of a face image for each patch stored in image memory 12 to extract a feature amount for the patch based on structure model adjustment section 15. As the feature amount, for example, the average brightness of each patch is used. If the average brightness is used as the feature amount, the brightness distribution over a face comparatively faithfully reflects the three-dimensional shape of a face under definite illumination conditions. Also, the brightness distribution has an advantage of not greatly being affected by a slight change in the angle of the face at the photographing time. The feature amount is not limited to the brightness of each patch (average brightness), and the difference in the brightnesses of adjacent patches can be used.

[0035] When the feature amounts of an adjusted structure model are extracted in this way, a judgment section 18 successively compares the extracted feature amounts with the feature amounts of persons prepared in a personal database 17, judges a degree of agreement through distance computation, and outputs the result (identification search).

[0036] In case of identification checking, that is, when whether an input face image is that of a specific person or not is checked, judgment section 18 calculates the distance (the absolute value of the difference) between each extracted feature amount and the corresponding feature amount of the specific person stored in personal database 17, and if the total sum of the distances is less than a predetermined threshold value, the input face image is positively identified as that of the person of personal database 17.

[0037] FIG. 11 illustrates the above personal identification processing, and the procedure of the processing will be clearly understood by the illustration.

[0038] Next, individual processing is described in more details.

[0039] <Feature Points Extraction>

[0040] The method of extracting the feature points described in the following is not a feature of the present invention, which, however, presumes a method of extracting the feature points. The presumed method of extracting the feature points is described in the public report, which the present applicants had already applied for a Japanese patent as a Japanese Pat. Appl. No. Hei 4-9753, and was laid open as a Japanese Pat. laid-open publication No. Hei 5-1997793. The basic principle of the method is described using the flowchart of FIG. 12.

[0041] The extraction of the feature points is, as stated above, performed in feature points extracting section 13.

[0042] First, step S1 inputs a face image stored in image memory 12, and after step S2 luminance-converts to generate a monochromatic graded image, step S3 generates an edge image. In this case, an operator that obtains not only the magnitude of an edge but its direction, such as the Sobel operator, which is described in Computer Vision, D. H. Ballard and C. M. Brown, Translated by Akio Fukumura, Japan Computer Association 1987, p. 98, is used to extract an edge. An edge obtained in this way is called an edge vector, since its components are magnitude and direction. An edge image obtained by the edge extraction can not be vividly illustrated, but is displayed by display 5 in such a way as horizontal edges are displayed in green, vertical edges are displayed in red, and the magnitude of edges are displayed by brightness.

[0043] Next, step S4 determines search areas that show where the face components such as an eye and nose are located. These search areas consist of the eyebrow areas, iris area, nose area, right cheek area, left cheek area, and mouth area. First, the locations of the right and left irises are determined from the search area of the irises which are positioned in the middle of the vertical direction. When the locations of the right and left irises are detected, the size of the whole face is estimated from the distance between the irises and the inclination of the irises. The other four areas are successively determined using the obtained locations of the irises.

[0044] After all search areas are determined, step S5 converts the edge image of each search area into a binary expression. Each extracted edge has a magnitude and contains noise. The binary coding is performed for the purpose of eliminating noise, and a predetermined threshold value is used. The threshold value is determined so that, in the area ratio, 20% of the edge pixels in a search area become 1 and the remaining edge pixels become 0.

[0045] Next, step S6 performs shape matching for the binary-coded edge image using shape templates to deduce a candidate area by judging a degree of agreement. The degree φ of agreement is obtained, for example, by calculating the inner product of two vectors, because the edges and the shape data of each component of a shape template are both expressed by vectors.

[0046] More specifically, if the edge vectors of an edge image are

[0047] u_{i, j}=(u_x, u_y)(i, j: the x and y coordinates of an image, u_x²+u_y²=1 or 0)

[0048] and if the shape data is

[0049] element data p_k=(l_k, m_k)(l_k, m_k: the xand ycoordinates of an element)

[0050] slope vector v_k=(v_x, v_y) (v_x²+v_y²=1)

[0051] where 1≦k≦n (n is the number of elements) then the degree of agreement in the coordinates (i, j) of the edge image with the shape data φ becomes

[0052] φ=(ΣU_{i+lk, j+mk}·v_k)/n(1≦k≦n)

[0053] where u_{i+lk, j+mk}·v_k=u_x×v_x+u_y×v_y

[0054] In this way the degree of agreement for each pair of coordinates in the search area with the shape data is calculated. Then a plurality of pairs of coordinates having great degrees φ of agreement is made a candidate area of the face component.

[0055] In practice, for example, in case of an eye template, the two irises, eyebrows, the hair part between a cheek and an ear, a nostril and the like are listed as parts having high degrees of agreement. In other words, if a shape template of irises is used to judge the degree of agreement, then the parts mentioned above are derived as a candidate area of the irises.

[0056] Next, step S7 judges matching (degree of agreement) for each edge image of a candidate area obtained as described above, by deforming the corresponding shape template. The method of the deformation is to deform a shape template to improve the degree of agreement by shifting the elements of the shape template of each component and by calculating the degree of agreement with each edge image (step 7). If the highest degree of agreement is obtained (step 8), then step S9 extracts a feature point from the shape of the shape template at this time.

[0057] Extraction of feature points is performed, for example, as shown in FIG. 4 for an eyebrow. In a matched eyebrow shape, i.e. having the highest degree of agreement, the left and right terminal points are first taken as feature points. Then the 4 points where two perpendicular trisectors of the segment between the two terminal points cross the upper and lower rims are taken as feature points. Therefore, total 6 points are extracted as the feature points of an eyebrow. The feature points of the nose and mouth are extracted respectively as shown in FIGS. 6 and 7.

[0058] Actual extraction of feature points are not shown in the flowchart of FIG. 12, but performed in the following order.

[0059] First, the irises are extracted. As described above, when the locations of the irises are obtained, the size, inclination and the like of the whole face can be estimated. If the inclination of the two irises (slope of the line segment connecting the feature points) is found, the inclination of the input whole face is found. Therefore, when step S9 extracts the feature points of the irises, step S10 applies an affine transformation to theedge image.

[0060] After the affine transformation, extraction of the feature points of the eye contours is performed. When the eyes are extracted, then the locations of the eyebrows can be estimated, so that the feature points of the eyebrows are extracted. Further, by extracting the mouth, the locations of the nose and chin can be estimated, so that the feature points of these components are extracted. Finally, the feature points of the top of the head and the cheek contours are extracted. Extraction of feature points are not necessarily performed in the above order, but if the extraction is performed in that order, extraction of feature points is performed smoothly. In this way, extraction of the all feature points is performed, and the routine of feature points extraction is completed.

[0061] <Adjustment Processing Routine for the Structure Model>

[0062] After features point extracting section 13 extracts the total 49 feature points (see FIG. 3), structure model adjustment section 15 performs deformation and adjustment of the standard structure model (FIG. 9).

[0063] The standard structure model consists of the data of 205 vertices and 385 triangular patches created by connecting these vertices. Since the connected structure is invariant, an adjusted structure model is obtained by adjusting the vertices data.

[0064] The adjustment is performed in the following rules.

[0065] (a) If a vertex to be obtained is a feature point (for example, the center of an iris, the corner of an eye, the corners of the mouth etc.), then the coordinates of the extracted feature point are used as they are.

[0066] (b) If a vertex to be obtained is not a feature point, then 3 feature points are selected according to a predetermined rule, and a linear interpolation is performed using the coordinates of these feature points in the following way.

[0067] The method of the linear interpolation is described with reference to FIG. 13.

[0068] In FIG. 13, the triangle on the left side P₀P₁P₂is the triangle formed by 3 feature points P₀, P₁, P₂surrounding a vertex q on the standard structure model, and the triangle on the right side P₀′P₁′P₂′ is the triangle formed by 3 feature points P₀′, P₁′, P₂′ extracted corresponding to the feature points P₀, P₁, P₂on the standard structure model. The point q′ is a vertex obtained by interpolating the above vertex q on the standard structure model. If the coordinates of feature points P₀, P₁, P₂are respectively (x₀, y₀), (x₁, Y₁), (x₂, Y₂), the coordinates of vertex q is (x, y), and the ratio of the weights of feature points P₀, P₁, P₂are m₀, m₁, m₂, then m₀, m₁, m₂can be obtained by solving the following 3 equations.

[0069] M₀+m₁+m₂=1

[0070] x=m₀x₀+m₁x₁+m₂x₂

[0071] y=m₀y₀+m₁y₁+m₂y₂

[0072] Next, if the coordinates of the corresponding feature points P₀′, P₁′, P₂′ of the deformed structure model, i.e. adjusted structure m0del, are respectively (x₀′, Y₀′), (x₁′, Y₁′), (x₂′, Y₂′), then the desired coordinates (x′, y′) of the vertex q′ are obtained in the following using the obtained weight ratios m₀, m₁, m₂.

[0073] x′=m₀x₀′+m₁x₁′+m₂x_2′

[0074] y′=m₀y₀′+m₁y₁′+m₂y_2′

[0075] The selection rules of the feature points ar as follows.

[0076] Rule 1. The 3 points form a triangle.

[0077] Rule 2. Before and after the deformation, the orientation is invariant, i.e. the clockwise order is invariant (P₀→P₁→P₂: P₀′→P₁′→P₂′).

[0078] Rule 3. The vertex q exists inside the triangle.

[0079] Rule 4. P₀, P₁, P₂exist as near as possible to the vertex q.

[0080] The linear interpolation is performed for all the 205 vertices, as a result, an adjusted structure model as shown in FIG. 10 is obtained. Here, since the perimeter of the standard structure m0del should be formed with feature points only, structure model adjustment section 15 approximates the perimeters of the head, chin, and etc. using functions such as quadratic functions.

[0081] <Brightness Correction>

[0082] The brightness correction is performed to prevent misjudgment due to a difference in the position of the light source in photographing.

[0083] As shown in FIG. 14, a brightness correcting section 19 that corrects the brightness of the face image is installed following feature amounts extracting section 16. In this case, standard structure model 14 stores beforehand the normal vector of each patch as data. That is, the standard structure model is made three-dimensional by giving the normal vector of each patch. Feature amounts extracting section 16 extracts the brightness and normal vector of each patch for the adjusted structure model obtained by structure model adjustment section 15. The position of the light source is estimated by the extracted brightnesses and normal vectors of the patches. For example, if a face image is divided into 4 parts with horizontal and vertical line. By observing the brightness distribution over the 4 parts, the position in what direction the light source is located from the photographed face can be estimated. If the estimated position of the light source is different from the position of the light source at the time of creating the personal feature amounts stored in personal database 17, then the brightnesses are corrected to adjust them to one of the positions of the light source. That is, the brightness of a patch whose normal is closer to the old direction of the light source is lowered, and the brightness of a patch whose normal is closer to the new direction of the light source is raised. By performing such brightness correction, misjudgment can be prevented under different illumination conditions.

[0084] Although the present invention has been fully described in connection with the embodiments, the present invention is not limited to the above embodiment, and changes and modifications apparent to those skilled in the art are included within the scope of the present invention as defined by the appended claims unless they depart therefrom.

[0085] <Possible Industrial Applications>

[0086] According to the composition of the present invention, personal identification and identification checking can be performed with high accuracy using feature amounts extracted from a great number of small parts.