Method and apparatus for image-based photorealistic 3D face modeling

The present invention relates to image processing, and more particularly, to a method and apparatus for image-based photorealistic 3D face modeling.

Automated photorealistic 3D face modeling is considered as a very important task in the computer graphics field due to its wide applicability in various fields such as virtual space creation, computer gaming, video conferencing and animation.

Although a laser scanner capturing an accurate 3D image from a complicated object and a distance measuring apparatus using structured light are currently available, the cost is still high and it is not easy to use them. Computer-aided inter active face modeling technologies require professional, hard labor. So, intensive efforts have been devoted to allow common PC users to more easily reconstruct more realistic human face models. In other words, it have been required to develop an algorithm that can be easily controlled by a common PC user, to enable automated construction of desirable faces from imperfect input data, which are obtained using economical imaging devices such as digital cameras.

Systems for automated face model reconstruction can be roughly divided into several categories according to the used source of 3D face shape data. Some researchers developed techniques to acquire face data from laser scanners or structured light installations. Problems arising with these techniques lie in that the apparatuses are expensive and are difficult to use.

Many efforts have been devoted to create face models from frontal and profile views. However, the strictly orthogonal relation between the two images is difficult to achieve when using a common handheld camera without a special auxiliary device, so the shape information obtained directly from different views has some confliction. This problem has not been solved yet.

Some systems rely on user-specified feature points in several images, which require labour-intensive manual procedures and much time. Among other approaches, methods utilizing optical flow and stereo methods seem to make the farthest step towards full automation of the reconstruction process, but the resulting models include considerable noise and unnaturally deformed face surface.

To avoid undesirable artifacts of the face model and increase robustness, some researchers utilize a morphable face model, which allows use of a limited number of feature points. The morphable face model is matched with reconstructed 3D points or source images and requires model-based bundle adjustment for shape recovery. These approaches greatly rely on how accurate and extensive the set of feature points is.

In another method for obtaining an accurate model using stereo reconstruction, shape recovery is limited only to a deformable model that fits additional constraints imposed, thereby degrading the accuracy of the model.

Some researchers have tried to build a model from just one frontal image based on priori information on depth. However, the resulting model quality in this case is far from being photorealistic.

An important issue in face modeling is the automated extraction of facial features. Various facial feature detection methods such as appearance-based modeling of facial features, human vision-based algorithms, search for specific edge and low-intensity pixel patterns, use of morphological operators, etc. have been suggested. Despite the obvious progress in this field, much work is still needed to improve accuracy and robustness for the creation of "human-quality" face analysis algorithms.

The present invention provides a method and apparatus for image-based photorealistic 3D face modeling using two images including frontal and profile images or three images including frontal, near-frontal, and profile images.

According to an aspect of the present invention, there is provided a method for creating a 3D photorealistic head model, the method comprising: (a) detecting frontal and profile features in input frontal and profile images; (b) generating a 3D head model by fitting a 3D genetic model using the detected facial features; (c) generating a realistic texture from the input frontal and profile images; and (d) mapping the texture onto the 3D head model.

According to specific embodiments of the present invention, the generating the 3D head model in (b) may further comprise generating depth information from the frontal image and a near-frontal image, wherein the generic model is fitted using the facial features to determine the 3D shape of the particular face, and the generated 3D head model is fitted using the depth information.

The detecting the frontal features in (a) may comprise: detecting a skin region; detecting a face region; detecting eye bounding boxes; detecting irises; normalizing the frontal image, detecting eye contours, detecting eyebrows, detecting lips contour, detecting nose contour, and detecting chin and cheeks contours.

The normalizing the frontal image may comprise rotating the frontal image such that the line between the centers of the irises becomes horizontal and rescaling the frontal image to a predetermined resolution.

The detecting the profile features in (a) may comprise: detecting a profile region; detecting a profile curve; detecting fiducial points; and detecting an ear contou r.

The generating the depth information from the frontal and near-frontal images may comprise: determining features points in the frontal image; performing model-based Lucas-Kanade tracking on the feature points to find corresponding points in the near-frontal image; obtaining a dense disparity map by data interpolation using matching correspondence; and converting the disparity map into the depth information. In this case, the converting the disparity map into the depth information may comprise: obtaining a difference value between maximum and minimum disparity values; determining a coefficient by dividing the difference value by a head width and multiplying the divided result by a predetermined constant; and obtaining the depth value of a pixel by multiplying the coefficient by a value obtained by subtracting the minimum disparity value from a measured disparity value.

The fitting the genetic model in (b) may comprise: converting feature curves detected in the images into 2D points corresponding to features defined in the 3D generic model using the length ratios of feature points on a facial feature curve of the 3D genetic model; and fitting the 3D generic model by 3-step radial based function (RBF)-based morphing based on the correspondences between the images features and the feature points of the 3D generic model.

The generating the realistic texture in (c) may comprise: performing color correction on the input images to compensate for different lightening conditions or color balance variations between cameras; generating frontal and profile textures by mapping the frontal and profile images onto a public UV plane based on the correspondence between 3D model vertices and projected 2D positions; and combining the frontal and profile textures and an artificial texture using a multi-resolution spline algorithm to complete texturing.

According to another aspect of the present invention, there is provided an apparatus for creating a 3D photorealistic head model, the apparatus comprising: a face feature detecting unit detecting frontal and profile features in input frontal and profile images; a face model fitting unit generating a 3D head model by fitting a 3D genetic model using the detected facial features; a texture generating unit generating a realistic texture from the input frontal and profile images; and a mapping unit mapping the texture onto the 3D head model generated in the face model fitting unit..

According to specific embodiments of the present invention, the face model fitting unit may comprise a depth information generating portion extracting depth information from the frontal image and a near-frontal image and generates the 3D head model by fitting the generic model using the facial features detected in the face feature detecting unit and the depth information generated in the depth information generating portion.

The face feature detecting unit may comprise: a frontal feature detecting portion detecting the frontal features; and a profile feature detecting portion detecting the profile features. The frontal feature detecting portion may comprise: a skin region detecting portion detecting a skin region; a face region detecting portion detecting a face region; an eye bounding boxes detecting portion detecting eye bounding boxes; an iris detecting portion detecting irises; and a frontal image normalizing potion normalizing the frontal image.

The frontal feature detecting portion further may comprise at least one of an eye contours detecting portion, an eyebrows detecting portion, a lips contour detecting portion, a nose contour detecting portion, and a chin and cheeks contour detecting portion.

The profile feature detecting portion may comprise a profile region detecting portion, a profile curve detecting portion, a fiducial point detecting portion, and an ear contour detecting portion.

The depth information generating unit may comprise; a feature point detecting portion determining feature points in the frontal image and finding corresponding feature points in the near-frontal image; a disparity obtaining portion obtaining a dense disparity map by data interpolation using matching correspondence; and a disparity-to-depth information converting portion converting the disparity map into the depth information.

The generic model fitting unit may comprise; a 2D point converting portion converting feature curves detected in the images into 2D points corresponding to features defined in the 3D generic model using the length ratios of feature points on a facial feature curve of the 3D genetic model; and a mesh model fitting portion fitting the 3D generic model by 3-step radial based function (RBF)-based morphing based on the correspondences between the images features and the feature points of the 3D generic model.

The texture generating unit may comprise: an input image compensating portion compensating for different lightening conditions or color balance variations between cameras by performing color correction on the input images; a frontal/profile texture generating portion generating frontal and profile textures by mapping the frontal and profile images onto a public UV plane based on the correspondence between 3D model vertices and projected 2D positions; and a texturing completing portion combining the frontal and profile textures and an artificial texture using a multi-resolution spline algorithm to complete texturing.

According to another aspect of the present invention, there is provided computer readable medium having embodied thereon a computer program for the above-described image-based photorealistic 3D head modeling method.

The above and other features and advantages of the present invention will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings in which: <ul id="ul0001" list-style="none" compact="compact"><li>FIG. 1 is a flowchart of a method of image-based photorealistic 3D face modeling according to the present invention;</li><li>FIG. 2 illustrates a detailed modeling process along with photographs;</li><li>FIG. 3 illustrates frontal and profile views of a generic model;</li><li>FIG. 4 illustrates typical input frontal, near frontal, and profile images;</li><li>FIG. 5 is a block diagram of an apparatus for image-based photorealistic 3D face modeling according to the present invention;</li><li>FIG. 6 illustrates a detailed configuration of a face feature detecting unit;</li><li>FIG. 7 illustrates a detailed configuration of a frontal feature detecting portion;</li><li>FIGS. 8 and 9 are flowcharts of detailed frontal feature detection (extraction);</li><li>FIG. 10 illustrates an example of skin likelihood image and face region detection, in which the smaller ellipse corresponds to an initial region, and the larger ellipse corresponds to the detected result.</li><li>FIG. 11 illustrates another example of skin likelihood image and face region detection;</li><li>FIG. 12A is a block diagram of a face region detecting portion of FIG. 7;</li><li>FIG. 12B is a flowchart of face region detection;</li><li>FIG. 13 illustrates an elliptical model for face region detection;</li><li>FIG. 14A is a block diagram of an eye bounding boxes detecting portion of FIG. 7;</li><li>FIG. 14B is a flowchart of eye bounding boxes detection;</li><li>FIG. 15 illustrates an exemplary eye variation image;</li><li>FIG. 16 illustrates another exemplary eye variation image;</li><li>FIG. 17 illustrates a result of eye bounding boxes detection;</li><li>FIG. 18A is a block diagram of an iris detecting portion of FIG. 7;</li><li>FIG. 18B is a flowchart of detection of the center and radius of an iris;</li><li>FIG. 19 illustrates examples of detected irises;</li><li>FIG. 20 is a flowchart of approximation for eye contour detection;</li><li>FIG. 21 is a graph of red channel intensities in an eye area along horizontal direction used for eye contour detection;</li><li>FIG. 22 illustrates points used for eye contour detection and a detected eye contour;</li><li>FIG. 23 illustrates detection of vertical eyebrows positions;</li><li>FIG. 24 illustrates eyebrow bounding boxes;</li><li>FIG. 25 illustrates detected eyebrows;</li><li>FIG. 26 is a flowchart of upper and lower lips detection;</li><li>FIG. 27 illustrates iterative refinements of a lips rectangle;</li><li>FIG. 28 illustrates a lip function image with initialized lip points;</li><li>FIG. 29 illustrates forces acting at lip contour points;</li><li>FIG. 30 illustrates one step of lip contour updating;</li><li>FIG. 31 is a flowchart of nose side detection in a nose contour detection process;</li><li>FIG. 32 illustrates a nose wing template;</li><li>FIG. 33 illustrates nose wings candidates detected in an image;</li><li>FiG. 34 illustrates the placement of main feature points for a nose curve;</li><li>FIG. 35 illustrates detected nose curves;</li><li>FIG. 36A is a block diagram of a chin and cheeks contour detecting portion of FIG. 7;</li><li>FIG. 36B is a flowchart of chin and cheeks contour detection;</li><li>FIG. 37 illustrates a chin/cheeks deformable model;</li><li>FIG. 38 illustrates a chin model fitting process;</li><li>FIG. 39 illustrates all detected features in frontal images;</li><li>FIG. 40 is a detailed block diagram of a profile feature detecting portion;</li><li>FIG. 41 is a flowchart of profile feature detection;</li><li>FIG. 42 illustrates a case where detection of a profile region has failed and discontinuous skin and nose regions appear;</li><li>FIG. 43 illustrates another case where detection of a profile region has failed and an imperfect nose region appears;</li><li>FIG. 44 illustrates another case where detection of a profile region has failed and an imperfect skin region appears;</li><li>FIG. 45 is an image for explaining a typical profile function;</li><li>FIG. 46 illustrates detection of a nose bridge top and an under-nose point;</li><li>FIG. 47 illustrates detection of chin and neck fiducial points;</li><li>FIG. 48 illustrates estimation of lips fiducial points;</li><li>FIG. 49 illustrates automatically detected profile features (not including ear);</li><li>FIG. 50 is a flowchart of ear contour detection;</li><li>FIG. 51 is a flowchart of ear initialization;</li><li>FIG. 52 illustrates a curve template used for profile ear detection;</li><li>FIG. 53 illustrates a normalized image, calibration points, and an ear search area used for ear position initialization in ear contour detection;</li><li>FIG. 54 illustrates a skin and hairs boundary in a face region near an ear area;</li><li>FIG. 55 illustrates the results of ear initialization using color information, in which red segments are matched with ear templates;</li><li>FIG. 56 illustrates the results of ear initialization using ear edge information, which can be performed when profile ear detection using only color information has failed;</li><li>FIG. 57 illustrates the results of profile ear detection;</li><li>FIG. 58 illustrates input facial feature curves for model fitting;</li><li>FIG. 59 is a block diagram of a face model fitting unit of FIG. 5;</li><li>FIG. 60 is a flowchart of initial model fitting in the face model fitting unit;</li><li>FIG. 61 illustrates key points extracted from frontal feature curves;</li><li>FIG. 62 illustrates generic (upper row) and created face models (lower row);</li><li>FIG. 63 is a block diagram of a texture generating unit of FIG. 5;</li><li>FIG. 64 is a flowchart of texture generation;</li><li>FIG. 65 illustrates a frontal texture image on a UV plane;</li><li>FIG. 66 illustrates a profile texture image on a UV plane;</li><li>FIG. 67 illustrates a final texture image obtained from an input image and an artificial texture;</li><li>FIG. 68 illustrates improved images obtained using a textured model and an artificial ear texture;</li><li>FIG. 69 illustrates an exemplary facial stereo pair;</li><li>FIG. 70 is a block diagram of a depth information generating unit of FIG. 5; and</li><li>FIG. 71 is a flowchart of depth information generation from frontal and near-frontal images.</li></ul>

Embodiments of the present invention will be described with reference to the appended drawings.

The outline of a method and apparatus for image-based photorealistic 3D face modeling according to the present invention will be described prior to detailed descriptions thereof, i.e., regarding face feature detection, face model fitting, texture generation, and 3D reconstruction using stereo image pair.

A modeling apparatus according to the present invention utilizes two or three facial images, frontal and profile images for the two, and frontal, near-frontal, and profile images for the three, to generate a photorealistic 3D polygonal face model.

The image acquisition conditions are simple: good contrast and sharpness and sufficient illumination in a facial area.

FIG. 1 is a flowchart of an image-based photorealistic 3D face modeling method according to the present invention. FIG. 2 illustrates a detailed modeling process along with photographs.

As shown in FIGS. 1 and 2, the modeling process includes the following operations. First, automated frontal feature detection and semi-automated profile feature detection are performed (operation 100). Secondly, a generic 3D head model (genetic mesh) is morphed to fit to frontal facial features (operation 120). Next, automated model-based stereo estimation is performed to obtain a depth map of the frontal photograph; and the model is morphed again to fit to profile features and the estimated stereo depth map (operation 140). Finally, a model texture is created from the frontal and profile photographs, along with artificial skin at some areas (operation 160). The created texture is mapped with the matched head model to generate a 3D head model (operation 180).

The use of both the depth map and profile features for model fitting seems to be redundant. However, the depth map provides abundant and detailed geometric information, which makes the final model to be seen more realistic.

If the near-frontal image is not available, processes using the near-frontal image can be omitted in the 3D face modeling method according to the present invention. Reasonable results can be obtained even in this case.

In the 3D face modeling method according to the present invention, new models are created in a generic model fitting framework. That is, a specific face is created by fitting a generic model to the input data of the subject. The generic model, which is termed as "generic mesh" in FIG. 2, can be thought as a priori knowledge about human faces, which makes automation of the process easier and improves the robustness of the face modeling method. The generic model shown in FIG. 3 includes 7,138 vertices and 14,096 triangles not including eyeballs and hair.

The generic model is positioned in standard frontal orientation. That is, X-axis is the direction from the right to the left, Z-axis is the direction in which the eyes graze, and Y-axis is the direction from the bottom toward the top, forming a right-handed coordinate frame. Such axis directions will be used throughout the following description, provided that there is no special explanation. FIG. 4 illustrates typical frontal, near-frontal, and profile input images.

FIG. 5 is a block diagram of the image-based photorealistic 3D face modeling apparatus according to the present invention. The apparatus includes a face feature detecting unit 500, a face model fitting unit 510, a texture generating unit 520, and a mapping unit 530. The apparatus may further include a depth information generating unit 540.

The face feature detecting unit 500 detects the facial features of frontal and profile input images. The face model fitting unit 510 generates a 3D face model by fitting a predetermined generic model using the detected facial features. When the depth information generating unit 540 is further included, the face model fitting unit 510 generates a 3D face model by fitting the generic model using the facial features detected in the face feature detection unit 500 and the face depth information generated by the depth information generating unit 540.

The texture generating unit 520 generates a realistic texture from the input images. The texture may be an artificial texture if needed. The mapping unit 530 maps the texture onto the 3D face model generated by the face model fitting unit 510. The depth information generating unit 540 extracts the face depth information from the frontal and near-frontal images.

1. Facial feature detection

As shown in FIG. 6, the face feature detecting unit 500 includes a frontal feature detecting portion 600, which detects the features of the frontal face, and a profile feature detecting portion 650, which detects the features of the profile.

1.1. Frontal feature detection

Referring to FIG. 7, the frontal feature detecting portion 600 includes a skin region detecting portion 700, a face region detecting portion 705, an eye bounding boxes detecting portion 710, an iris detecting portion 715, and a frontal image normalizing portion 720.

The frontal feature detecting unit 600 may further include at least one of an eye contour detecting portion 725, an eyebrow detecting portion 730, a lips contour detecting portion 735, a nose contour detecting portion 740, and a chin and cheeks contour detecting portion 745, if required.

The frontal feature detection process will be described. FIGS. 8 and 9 are flowcharts of frontal feature detection (extraction). The frontal feature detection process includes skin region detection (operation 800), face region detection (operation 810), eye bounding boxes detection (operation 820), iris detection (operation 830), frontal image normalization (operation 840), eye contour detection (operation 900), eyebrow detection (operation 910), mouth (lips) contour detection (operation 920), nose contour detection (operation 930), and face (chin and cheeks) contour detection (operation 940).

Each step is performed with the assumption that the previous step has been successful and the previously detected features have reasonable accuracy. To this end, if there is inaccuracy in feature detection, a user is allowed to manually correct the feature detection inaccuracy after each step.

1.1.1. Skin detection

A pre-trained Maximum Likelihood Bayes classifier in a normalized r-g chrominance color space is used for skin color modeling and detection. The normalized r-g color space is chosen because it allows fast and simple conversion from the RGB space, and due to known good performance of the Bayes ML classifier in skin color modeling.

The training is performed by gathering two statistics - <i>p</i>((<i>r</i>,<i>g</i>)| <i>skin</i>) and <i>p</i>((<i>r</i>,<i>g</i>)| <i>skin</i>)-, calculated using skin and non-skin histograms built from face and non-face areas of the training images. The skin likelihood image is constructed by calculating this measure for each pixel of the input frame:<maths id="math0001" num="(1)"><math display="block"><mrow><mtext mathvariant="italic">Skin(r</mtext><mtext>, </mtext><mtext mathvariant="italic">g</mtext><mtext>) = </mtext><mfrac><mrow><mtext mathvariant="italic">p</mtext><mtext>((</mtext><mtext mathvariant="italic">r,g</mtext><mtext>)| </mtext><mtext mathvariant="italic">skin</mtext><mtext>) </mtext></mrow><mrow><mtext mathvariant="italic">p</mtext><mtext>((</mtext><mtext mathvariant="italic">r</mtext><mtext>,</mtext><mtext mathvariant="italic">g</mtext><mtext>)|-</mtext><mtext mathvariant="italic">skin</mtext><mtext>)</mtext></mrow></mfrac></mrow></math><img file="EP1510973A2_D0001.tif" /></maths> This satisfies Bayes maximum likelihood criteria with the assumption that priori skin and non-skin probabilities are equal. The resulting skin likelihood image is shown in FIGS. 10 and 11.

1.1.2. Face region detection

FIG. 12A is a block diagram of the face region detecting portion 705 of FIG. 7. The face region detecting portion 705 includes a face region initializing portion 1230, which initializes the largest skin-colored connected component as the face region, an ellipse stabilizing portion 1240, which initializes and evolves an ellipse by displacing boundary points of the ellipse based on the initialized face region until the ellipse is stabilized, and a face region determining portion 1250, which determines a bounding box of the stabilized ellipse as the face region.

FIG. 12B is a flowchart of face region detection. According to the present invention, the face region is detected as an elliptic region and a deformable ellipse model-based technique is used. Referring to FIG. 13, an elliptic model is initialized at an expected face region (operation 1200). The expected face region can be the largest skin-colored connected component or one of the largest two components having comparable sizes that is closer to the center of the image.

Boundary points of the ellipse are displaced based on the initialized face region to initialize and evolve the ellipse to be stable (operation 1210). This operation will be described in detail.

The distribution of skin-colored pixels at the border of the ellipse and deformation of the model are controlled using a number of rectangular probes positioned on the boundary of the ellipse. The displacement of each probe is determined according to the following rules.

First, two values are calculated as follows:<maths id="math0002" num="(2)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">in</mtext></mrow></msub><mtext>= 2 · </mtext><mfrac><mrow><msup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">N</mtext></mrow></msup><mtext mathvariant="italic">inside</mtext></mrow><mrow><mtext mathvariant="italic">S</mtext></mrow></mfrac><msup><mrow><mtext>, </mtext></mrow><mrow><mtext mathvariant="italic">P</mtext></mrow></msup><mtext mathvariant="italic">out</mtext><mtext> = 2· </mtext><mfrac><mrow><msup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">N</mtext></mrow></msup><mtext mathvariant="italic">outside</mtext><mtext></mtext></mrow><mrow><mtext mathvariant="italic">S</mtext></mrow></mfrac></mrow></math><img file="EP1510973A2_D0002.tif" /></maths> where <i>N</i>_{<i>inside</i>} is the number of skin pixels that lie both inside probe and ellipse; <i>N</i>_{<i>outside</i>} is the number of skin pixels that lie inside probe and outside ellipse; and <i>S</i> is probe area. <i>P</i>_<i>in</i> and <i>P</i>_<i>out</i> have larger values if the probe lies inside the face region. <i>P</i>_<i>in</i> and <i>P</i>_<i>out</i> have smaller values if the probe lies outside the face region. <i>P</i>_<i>in</i> has a larger value and <i>P</i>_<i>out</i> has a smaller value if the ellipse lies on the boundary of the face region.

If <i>P</i>_<i>in</i><i> &lt; T</i>_<i>in</i> (<i>T</i>_<i>in</i> is a threshold value), the probe is moved inwards at speed <i>V</i>_<i>in</i>. Otherwise, if <i>P</i>_<i>out</i><i> &gt; T</i>_<i>out</i><i> (T</i>_<i>out</i> is a threshold), the probe is moved outwards at speed <i>V</i>_<i>out</i> . That is, if there are few skin pixels inside the probe interior neighborhood, the probe exists outside the face region so that the probe moves inwards; and if the number of skin pixels both in the interior and exterior probe neighborhoods is sufficient, the probe is moved outwards.

A process of model deformation includes calculating the displacements of all probes and fitting the ellipse to the center of the repositioned probes. The ellipse is restricted to have a fixed orientation (along vertical major axis). The resultant stabilized ellipse bounding box is determined to be the face region (operation 1220).

FIGS. 10 and 11 illustrate some results from the face region detection. In FIGS. 10 and 11, the smaller ellipse corresponds to an initial region, and the larger ellipse corresponds to the detected result.

1.1.3. Eye bounding boxes detection

FIG. 14A is a block diagram of the eye bounding boxes detecting portion 710 of FIG. 7. Referring to FIG. 14A, the eye bounding boxes detecting portion 710 includes a blurred image generating portion 1450, which generates a blurred image by low-pass filtering, an image binarizing portion 1460, which generates a new image by calculating the mean value of each pixel and its neighboring pixels in an image obtained by subtracting the blurred image from the original image and binarizing the new image using a predetermined threshold value, an eye candidate searching portion 1470, which finds connected segments in the image binarized in the image binarizing portion as eye candidates, and an eye bounding box determining portion 1480, which determines the eye bounding boxes by evaluating the eye candidates in terms of shape, size, and relative position.

FIG. 14B is a flowchart of eye bounding boxes detection.

A blurred image is created by low-pass filtering (operation 1400). The blurred image is subtracted from the original image (operation 1410). The mean value of each pixel and its neighboring pixels in the resultant image is calculated. A new image is created using the mean value and binarized using a predetermined threshold value (operation 1420). Connected segments are found to be eye candidates (operation 1430). Eye bounding boxes are determined by evaluating the eye candidates in terms of shape, size, and relative position (operation 1440).

In particular, the eye bounding boxes detection in the present invention is based on the detection of approximately eye-shaped and eye-sized variations in a red channel of the color face image at several scales. The red channel is chosen because the eye irises, even in the case of light eyes (blue, green), have small red component values, while the eye whites and surrounding skin have relatively large red component values. It is experimentally proved that using the red channel gives better results than using gray level image-based methods.

First, the original R-channel image is preprocessed to preserve only a face part defined by the elliptic bounding rectangle detected in the previous process and scaled to a fixed width. The red channel intensity is also stretched to the maximum range in this step.

Second, a variation image <i>V</i>_<i>n</i>_,α (<i>x</i>, <i>y</i>) , which represents the likelihood that each spot is to be an eye, is calculated by the following formula:<maths id="math0003" num=""><img file="EP1510973A2_D0003.tif" /></maths> where p and r represent pixel locations; I is a red channel image after pre-processing; <i>R</i>_<i>n</i>_,_<i>x</i>_,_<i>y</i> is a rectangle of (n x 5) size centered at (x, y); <i>P</i>_<i>n</i>_,_<i>r</i> is an ellipse of (n x n/2) size centered at r; α is a scaling coefficient, n represents the expected size of eye features.

A variation image is calculated using 4 combinations of 'n' and α to eliminate possible errors in the face detection and to cope with variations in the shape of eyes. FIGS. 15 and 16 illustrate exemplary eye variation images obtained using the following different combinations of coefficients: <ul id="ul0002" list-style="none" compact="compact"><li>n = OPTIMAL_FACE_WIDTH / 30, α = 0.6,</li><li>n = OPTIMAL_ FACE _WIDTH / 25, α = 0.6,</li><li>n = OPTIMAL_FACE_WIDTH / 30, α = 1.4, and</li><li>n = OPTIMAL_FACE_WIDTH / 25, α = 1.4.</li></ul>

Third, the connected components in thresholded variation images are tested to satisfy the shape, size and relative positions criteria to get the best matching eye boxes. The results obtained from different variation images are merged together according to the following strategy: <ul id="ul0003" list-style="none" compact="compact"><li>Step 1. Start from the smallest scale (the first configuration listed above);</li><li>Step 2. If the eye-candidates are present at the current scale: <ul id="ul0004" list-style="none" compact="compact"><li>a) If no candidates were detected at previous scales, set the eyes to current candidates and go to step 3;</li><li>b) If the candidates were already found, compare the current scale candidates with the previous ones. If the sizes and positions of the candidates don't change dramatically, update the eyes with the candidates at the current scale.</li></ul></li><li>Step 3. Take next (larger) scale and go to step 2;</li></ul>

The eye bounding boxes of FIG. 9 are the detected results.

1.1.4. Eye irises detection

The irises are detected from the eye bounding boxes in the red channel image. FIG. 18A is a block diagram of the iris detecting portion 715 of FIG. 7. Referring to FIG. 18A, the iris detecting portion 715 includes a highlight searching portion 1860, which determines whether a highlight exists by comparing the number of pixels having maximum brightness values in each of the eye bounding boxes in the red channel image with a threshold value, an iris center initializing portion 1870, which initializes the center of mass of the darkest pixels as the center of the iris if no highlight is found and initializing the center of a high contrast region near a highlight as the center of the iris if the highlight exists, an iris center/radius measuring portion 1880, which repeatedly measures gradients of the pixels along an initial circle at the center of the iris while enlarging the initial circle, and an iris determining portion 1890, which determines a region having the largest gradient as the center of the iris and the radius of the iris.

FIG. 18B is a flowchart of detection of the center and radius of the irises. The number of pixels having maximum brightness values in an eye bounding box in the red channel image is compared with a threshold value to determine whether a highlight exists (operation 1800). If no highlight is found, the center of mass of the darkest pixels is initialized as the iris center (operation 1820). If a highlight exists, the center of a high contrast region near the highlight is initialized as the iris center (operation 1810).

An initial circle at the iris center is enlarged, and gradients of the pixels along the circle are measured (operation 1830). This gradient measurement is repeated using pixels adjacent to the initial iris center (operation 1840). A region having the largest gradient is selected as the iris center and the radius of the iris is obtained (operation 1850).

The eye irises detection process will be described in detail. The iris centers are first estimated approximately, and then refined during the iris radius detection.

In the iris center estimation process, if there is no highlight found inside the eye-bounding box, the center of mass of the darkest pixels is initialized as the iris center; while if a highlight exists, the center of a high contrast region around the highlight is initialized as the iris center. The iris center detection is performed as follows using the R-channel image pre-processed in the previous stage: <ul id="ul0005" list-style="none" compact="compact"><li>1) Filter the eye area using a 3x3 median filter to eliminate noise;</li><li>2) Determine whether a highlight is present or not by comparing the number of pixels having maximum brightness values inside the eye bounding box with a predetermined threshold;</li><li>3) Detect the iris center (using different methods depending on whether a highlight exists in the iris); <ul id="ul0006" list-style="none" compact="compact"><li>a) When a strong highlight is found inside the iris, a central area of the eye bounding box is scanned using a template matching method. A circular template with a fixed radius is moved inside the search area, and the conditions listed below are checked at each location to detect the iris center: <ul id="ul0007" list-style="none" compact="compact"><li>i) The local minimum value (dLocalMinVal) inside the search window should not be too close to the local maximum (dLocalMaxVal) inside the search window (because this makes it sure that both dark pixels and highlights are present in the search window);</li><li>ii) dLocalMinVal should be dark enough;</li><li>iii) dLocalMaxVal should be bright enough.</li></ul></li></ul>    Using all the locations where these conditions are satisfied, the expected iris center is determined as the center of mass of these locations.</li><li>4) When a strong highlight is not found: <ul id="ul0008" list-style="none" compact="compact"><li>a) A 5x5 minimum function is applied to the eye area to eliminate weak highlights;</li><li>b) The eye area is convolved with<maths id="math0004" num="(4)"><math display="block"><mrow><mtext mathvariant="italic">W</mtext><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext>, </mtext><mtext mathvariant="italic">y</mtext><mtext>, </mtext><mtext mathvariant="italic">c</mtext><mtext>)= </mtext><mfrac><mrow><mtext>sin((</mtext><msup><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext>+ </mtext><msup><mrow><mtext mathvariant="italic">y</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext>) /c) </mtext></mrow><mrow><mtext>(</mtext><msup><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext>+ </mtext><msup><mrow><mtext mathvariant="italic">y</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext>) /</mtext><mtext mathvariant="italic">c</mtext></mrow></mfrac></mrow></math><img file="EP1510973A2_D0004.tif" /></maths> Significant weights are assigned to a center part of the processed block during the convolution, while negative weighs are assigned to the boundary part thereof. Parameter c controls the radius of the region to which a positive weight is assigned.</li><li>c) The most darkest points, which are compared with a predetermined threshold, are averaged to find the iris center.</li></ul></li></ul>

Next, the iris center (xc, yc) initialized in previous step is refined by performing the following processes using all pixels (x, y) around it. The iris radius R is also detected in this procedure. <ul id="ul0009" list-style="none" compact="compact"><li>1) The following calculation is performed on all pixels (x, y) near the iris center (xc, yc): <ul id="ul0010" list-style="none" compact="compact"><li>a) For R = MinR to R = MaxR: <ul id="ul0011" list-style="none" compact="compact"><li>i) Calculate the sum of intensities of the pixels positioned at the left and right boundaries of the circle having a radius R-1 and centered at (x, y); the top and bottom parts are very likely to be occluded by eyelids so they are not used.</li><li>ii) Calculate the sum of intensities of the pixels positioned at the left and right boundaries of the circle having a radius R and centered at (x, y); the top and bottom parts are not used.</li><li>iii) Calculate the difference <i>(D(R, x, y))</i> between these two sums.</li></ul></li><li>b) Choose a maximum <i>D(R, x, y)</i>, and record the corresponding radius <i>R</i> as Rmax(x, y).</li></ul></li><li>2) Choose a maximum <i>D(Rmax(x, y)</i>, <i>x, y)</i> among the values for all pixels <i>(x, y)</i>, and take the corresponding pixel <i>(x, y)</i> as the center of the iris and <i>Rmax(x, y</i>) as the radius of the iris. FIG. 19 illustrates some results of the iris detection.</li></ul>

1.1.5. Face image normalization

After the iris detection, the face image is rotated such that the line between the iris centers is strictly horizontal. The size of the face bounding box is also adjusted using priori knowledge regarding the proportion between the size of the face and the distance of the two iris centers. Then the input image is cropped to contain only the face region and scaled to a predetermined width.

1.1.6. Eye contour detection

Eye contours are approximated using two polynomials for upper and lower eyelids. FIG. 20 is a flowchart of approximation for eye contour detection. A search area is predetermined according to the center and radius of the iris (operation 2000). Pixels on each horizontal scan line in the red channel image in the search area, in which local minimums or brightness abruptly change, are selected as left and right eyelid points (operation 2010). The leftmost and rightmost points among the remaining eyelid points are selected as eye corners (operation 2020). The upper eyelid curve is estimated using points on the line connecting the eye corners by a minimum square method (operation 2030). The lower eyelid curve is estimated using the selected eye corners and the lower point of the iris (operation 2040).

The eye contours detection process will be described in detail. One eye contour model consists of two polynominals for the upper eyelid (cubic in both x and y) and lower eyelid (quadratic in both x and y). After the estimation of the center and radius of the iris, the upper eyelid is approximated from an area of low-intensity pixels (the border between the eye white and skin). No additional detection is required for the lower eyelid, and the lower eyelid is directly approximated from the eye corners and the lower point of the iris.

Initially, before detection of the upper eyelid, the red channel eye image is filtered using a median filter and Gaussian-smoothened to lower the noise level. A search area for eyelid points is predefined according to the center and radius of the iris.

Secondly, the upper eyelid points are detected using the following algorithm. <ul id="ul0012" list-style="none" compact="compact"><li>1) For each vertical position inside the search area:</li><li>2) If at current vertical position the iris is covered with skin (the average intensity in this line is greater than a threshold), the process goes to 1;</li><li>3) The pixel intensity values in the current line are scanned from the left border of the iris to the left border of the eye bounding box to find areas where local minimums or brightness significantly increases significantly (see FIG. 21). These areas correspond to a left side portion of the upper eyelid;</li><li>4) The same process is performed on the right side. That is, the pixel intensity values in the current line are scanned from the right border of the iris to the right border of the eye bounding box to find areas where local minimums or brightness increase significantly (see FIG. 21). These areas correspond to a right side portion of the upper eyelid;</li></ul>

The above-described algorithm gives a set of points that are assumed to lie on the upper eyelid. To exclude erroneously detected points, the left and right halves of the eye bounding box are processed as follows. <ul id="ul0013" list-style="none" compact="compact"><li>1) Approximate points to lines by Hough transformation;</li><li>2) Choose the line with reasonable orientation and maximum number of points that are close to it;</li><li>3) Remove all points which are too far away from the estimated line;</li></ul>

Among the remaining points the leftmost and rightmost are chosen as the eye corners, the points that lie above the line connecting the eye corners are utilized to estimate the upper eyelid curve (see FIG. 22).

1.1.7. Eyebrows detection

The vertical eyebrows position is approximated as the global minimum in the normalized horizontal integral projection of the pixels (H(y) below) in a forehead area (see FIG. 23):<maths id="math0005" num=""><img file="EP1510973A2_D0005.tif" /></maths> where <i>Face(y)</i> is a set of x satisfying that (x, y) is inside the face ellipse; <i>Wdt(y)</i> is the width of the face ellipse at position <i>y</i>; and <i>gray(x, y)</i> is the intensity of a gray value at (<i>x</i>, <i>y</i>).

If the found vertical eyebrow position is too far away from the eye, the vertical eyebrow position is set to a predetermined value according to the face size and iris center positions. Then, an eyebrow bounding box is determined based on empirical information on the eyebrow position (see FIG. 24).

Afterwards a third degree (cubic) polynomial is approximated to express the eyebrow. First, along each vertical segment inside the eyebrow rectangle, points at which gray values are greater than a predetermined value are collected as eyebrow points, and the mean position of these points is calculated. The eyebrow curve is estimated using the mean positions (see FIG. 25).

1.1.8. Lip contour detection

The lip contour detection includes upper lip detection and lower lip detection. FIG. 26 is a flowchart of upper and lower lips detection.

The upper and lower lips are detected as follows. Initially, a lips rectangle is initialized (operation 2600). The initial lips bounding box is refined to be smaller by analyzing the moments of non-skin color pixels (operation 2610). A lip function image is created, and the probability that each pixel in the refined lips bounding box belongs to a lip or skin is calculated (operation 2620). The second-order central moments of pixels having large lip function values are calculated, and a lips contour is initialized using an ellipse (operation 2630). The lips contour is dynamically evolved by inward and outward forces (operation 2640). A polynominal expressing the lips contour is obtained by approximation using the evolved contour points (operation 2650).

The outward force is a force moving contour points to the lip-skin boundary. The inward force consists of an internal shaping force, which shapes the contour to be elliptical, and an internal smoothening force, which is determined by predetermined factors, including a force suppressing contour points from being moved beyond the boundary.

The lips contour detection will be described in detail. A first step in lips contour detection is to estimate a reasonably accurate bounding rectangle. This estimation step includes the following steps: <ul id="ul0014" list-style="none" compact="compact"><li>1) A person-specific skin color histogram is built during the skin detection stage;</li><li>2) A rectangle centered near an expected mouse position is set to be the initial lips bounding rectangle.</li><li>3) The center of mass and the second order moments of pixels having small person-specific skin color histogram values in the current rectangle are iteratively calculated to more accurately refine the lips box (see FIG. 27).</li></ul>

The lips box refinement is performed several times, for example, about six times, which is usually enough for reasonably accurate lip bounding box calculation.

Next, the lip function image is generated to measure the likelihood that the color of each pixel belongs to lip or skin color. Both classes of the two colors are represented by two-dimensional Gaussian probability density functions in (r=R/G, b=B/G) space. The pixels with low person-specific skin histogram values in the lips bounding rectangle are used for lip color class calculation; pixels marked as skin during skin detection are used for skin color class estimation. After the two color classes are calculated the lip function image is generated using the following formula:<maths id="math0006" num="(6)"><math display="block"><mrow><mtext mathvariant="italic">lip_func</mtext><mtext>(</mtext><mtext mathvariant="italic">x,y</mtext><msub><mrow><mtext>) = α</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext></mtext><msub><mrow><mtext mathvariant="italic">p</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext> (</mtext><mtext mathvariant="italic">r</mtext><mtext>(</mtext><mtext mathvariant="italic">x, y</mtext><mtext>),</mtext><mtext mathvariant="italic">b</mtext><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext>, </mtext><mtext mathvariant="italic">y</mtext><mtext>))</mtext><msub><mrow><mtext mathvariant="italic">-α</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext></mtext><msub><mrow><mtext mathvariant="italic">p</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><mtext> (</mtext><mtext mathvariant="italic">r</mtext><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext>,</mtext><mtext mathvariant="italic">y</mtext><mtext>),</mtext><mtext mathvariant="italic">b</mtext><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext>,</mtext><mtext mathvariant="italic">y</mtext><mtext>))</mtext></mrow></math><img file="EP1510973A2_D0006.tif" /></maths> where <i>p</i>_<i>l</i><i>(r</i>(<i>x</i>,<i>y</i>),<i>b</i>(<i>x</i>,<i>y</i>)) is the probability density value of the lip color class at pixel position (x,y); <i>p</i>_<i>s</i> (<i>r</i>(<i>x</i>, <i>y</i>),<i>b</i>(<i>x</i>,<i>y</i>)) is the probability density value of the skin color class at pixel position (x,y); and α₁ and α₂ are coefficients. Therefore, <i>lip_ func(x,y</i>) represents the difference between the probability that the pixel belongs to the lip color class and the probability that the pixel belongs to the skin color class.

A third step includes calculating the second-order central moments of pixels having large lip function values and approximating the lips contour using an ellipse.

A fourth step includes generating an accurate lips contour by repeatedly applying the algorithm to the lip function image. The lips contour can be initialized as a closed polygon consisting of points on the boundary of the ellipse that are sampled at the same interval and angles (see FIG. 28 for the lip function image and initialized lips contour points). At each iteration contour point ρ_i is moved according to a set of simple rules. In an embodiment of the present invention, the direction in which the contour point ρ_i is moved by a force is <i>v</i>_<i>c</i> (see FIG. 29). The directional movement <i>F</i>_<i>i</i> of a contour point is determined as the sum of three forces given by equation (7) below:<maths id="math0007" num="(7)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">F</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">F</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">data</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">F</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">form</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">F</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">sm</mtext></mrow></msup></mrow></math><img file="EP1510973A2_D0007.tif" /></maths> where<maths id="math0008" num=""><img file="EP1510973A2_D0008.tif" /></maths><maths id="math0009" num=""><img file="EP1510973A2_D0009.tif" /></maths><maths id="math0010" num=""><img file="EP1510973A2_D0010.tif" /></maths>

<i>p</i>_<i>i-</i>₁ , <i>p</i>_<i>i</i> , and <i>p</i>_<i>i</i>+1 are three clockwise consecutive contour points, and all <i>k*</i> are predetermined positive coefficients. <i>k</i>_<i>sm</i> is a coefficient that varies according to the positions of the contour points and the direction in which the contour points are moved, while the other coefficients are constant.

In fact, to allow the algorithm to be matched with corners, <i>F</i>_<i>i</i>^<i>sm</i>, which is an elliptical constraint described later, should less contribute to lip corner points than <i>F</i>_<i>i</i><i>.</i> So <i>k</i>_<i>sm</i><i> (i)</i> is smaller for points found near the corners of the ellipse in the previous iteration step. The lower part of the lip contour is smoother than the upper part, which is applied when calculating <i>k</i>_<i>sm</i> (<i>i</i>) .

<i>f</i> is a value at position (<i>p</i>_<i>i</i>) in the lip function image; <i>T</i> is a predetermined threshold; <i>v</i>_<i>p</i> and <i>v</i>_<i>n</i> are the vectors from the current point <i>p</i>_<i>i</i> toward the previous and next contour points (see FIG. 29); <i>v</i>_<i>c</i> is a normalized direction from the ellipse center toward <i>p</i>_<i>i</i> ; <i>v</i>^<i>1</i>_<i>p</i> is generated by turning <i>v</i>_<i>p</i> clockwise by π/2.

In summary, <i>F</i>_<i>i</i>^<i>data</i> is the force controlling the expansion or contraction of the contour to fit actual data at point <i>p</i>_<i>i</i> , and <i>F</i>_<i>i</i><i></i>^<i>form</i> forces the shape of the contour to be close to ellipse. To allow the force <i>F</i>_<i>i</i><i></i>^<i>form</i> to affect the global contour form, <i>v</i>_<i>n</i> and <i>v</i>_<i>p</i> are taken from the average of next (previous) several points. <i>F</i>_<i>i</i><i></i>^<i>sm</i> controls the smoothness of the contour by not allowing any single point to go far beyond the boundary.

The above algorithm is terminated after about 30 iterations. One lips contour updating process is illustrated in FIG. 30. Next, polynominals (fourth degree for both the upper and lower lips) are fitted to the resulting points from the iterations to generate a lips contour curve.

1.1.9. Nose contour detection

The nose contour detection includes nose side detection. FIG. 31 is a flowchart of nose side detection in the nose contour detection process. The nose side detection is performed as follows. First, matching with a temperate having a predetermined shape is performed on an edge image in a predetermined search area (operation 3100). Among detected candidates having large matching values a pair of candidates that satisfy the requirement for symmetry is selected and determined as nose wing positions (operation 3110). Each nose side is expressed using a fourth degree polynominal curve. This polynominal curve is fitted to the detected nose wing templates and three points interpolated between the nose wing and eye corners with predetermined coefficients (operation 3120). Finally the nose tip and nose lower curve are positioned using predefined interpolation coefficient (operation 3130).

The nose contour detection process will be descried in detail. It is very difficult to build a universal nose detection technique that can be used regardless of imaging and lightening conditions. Of course, in the conditions of front illumination and good sharpness, no significant problem arises because a distinct edge pattern appears in the nose area. However, in some cases where the photograph is blurry or is taken under no-directional, ambient-like illumination, the nose edge area is too noisy to identify the edge patterns. In this case, the nose wings can be detected using a directional edge-map template that provides good robustness to images in different classes. This nose contour detection algorithm can be implemented according to the following steps. <ul id="ul0015" list-style="none" compact="compact"><li>1) A nose area image (ranging laterally between the eye-centers and vertically from the bottom of the eyes to the top of the mouse-bounding box) is cropped and scaled to a fixed resolution.</li><li>2) A median filter is applied to the nose area image to remove noise and protect edge information.</li><li>3) Edge gradient images are calculated using a Prewitt edge detector.</li><li>4) A directional nose wing template is matched with the nose area image to detect the nose wings.</li></ul>

A nose wing template expresses a typical shape of nose side at a fixed scale (see FIG. 32). The accuracy-of-fit is measured as the sum of the edge magnitudes of pixels that lie on the border of the nose wing template and have edge directions close to the tangent of the template. Nose candidates are obtained from the positions with maximum 10% accuracy-of-fit, and pairs of candidates (left and right nose wings candidates) are tested according to the following three criteria to determine the most probable nose position (see FIG. 33).

First, overlapping condition: a pair of candidates should have similar heights.

Secondly, separate condition: a pair of candidates should be not too close each other in x-direction.

Thirdly, symmetry in x-direction: the difference between the distances in X-direction from the candidates to the face center should not be too large.

Next, a fourth degree polynomial is fitted to the six points marked in FIG. 34, among which points 1, 2, and 3 are sampled from the detected template at predefined positions, and others are interpolated between the nose template and eye rectangles using predefined coefficients.

The above-described nose sides contour detection method results in very good robustness and accuracy when applied to different-quality images taken under different lightening conditions. An example of the nose sides contour detection is illustrated in FIG. 35.

The nose tip is the middle point of two side wing template centers. The lower nose curve (see FIGS. 38 and 39) is positioned between two nose sides using predefined coefficients.

1.1.10. Chin and cheeks contour detection

FIG. 36A is a block diagram of the chin and cheeks contour detecting portion 745 of FIG. 7. Referring to FIG. 36A, the chin and cheeks contour detecting portion 745 includes a gradient calculating portion 3640, which calculates a gradient vector field on a red channel image, a chin and cheeks contour expanding portion 3650, which positions an initial contour template in a face region defined by two polynominal curves crossing at a chin point and expanding the chin and cheeks contour outward until the chin and cheek contour reaches strong edges along the tangents of the curves, and a chin and cheeks contour determining portion 3660, which stops expanding the chin and cheeks contour when the chin and cheeks contour has reached the strong edges on the tangents of the curves.

FIG. 36B is a flowchart of chin and cheeks contour detection. The chin and cheeks contour detection process is performed as follows.

First, a gradient vector field on the red channel image is calculated (operation 3600). An initial contour template is positioned in a face region defined by two polynominal curves crossing at a chin point (operation 3610). The chin and cheeks contour is expanded outward to strong edges along the tangents of the curves (operation 3620). Expanding the chin and cheeks contour is stopped when significant-brightness valleys are reached (operation 3630).

The chin and cheeks contour detection process will be described in detail. The chin and cheeks contour is expressed by two continuous fourth degree polynominals crossing at the bottom chin point. The two polynominals have a fixed Y-coordinate value at upper ends. The curve defined by the polynominals is divided into a plurality of sections (see FIG. 37). The chin and cheeks contour detection process includes the following steps. <ul id="ul0016" list-style="none" compact="compact"><li>1) Edge images and a chin curve are initialized as follows. <ul id="ul0017" list-style="none" compact="compact"><li>a) The horizontal and vertical edge images are generated by: <ul id="ul0018" list-style="none" compact="compact"><li>i) scaling the original red-channel image to fit to OPTIMAL_FACE_WIDTH, performing Gaussian-smoothing on the scaled image, and filtering the image using a median fitter; and</li><li>ii) detecting the edges using a Sobel edge detector.</li></ul></li><li>b) The left and right curves are initialized from three points, the bottom point, the left upper point, and the right upper point, to be symmetrical. The three points are determined using a priori knowledge of the detected eyes and lip positions.</li></ul></li><li>2) The curve is refined by repeating the following processes: <ul id="ul0019" list-style="none" compact="compact"><li>a) For each section i (from 0 to N, where N is a total number of sections): <ul id="ul0020" list-style="none" compact="compact"><li>i) The accuracy-of-fit is set to 0;</li><li>ii) For each sampling point (x,y) in section i: if the angle between the tangent of the curve and the image edge direction at (x,y) is less than 60 degrees, and the edge magnitude at (x, y) is not less than a predetermined threshold, the accuracy-of-fit is increased; and</li><li>iii) If the accuracy-of-fit is less than another given threshold, the section is moved "outwards" along the curve normal vector. Otherwise, the section is moved slightly "inwards".</li></ul></li><li>b) The curve is refit to all sections. In 2.a.iii), all the sections of the curve are expanded outwards along the normal of the curve (see FIG. 38 for the intermediate stages of the chin fitting process). However, moving the sections in a lower part of the curve outward should be stopped when significant-brightness valleys are reached because in the lower chin area the edges are usually very weak. Here, the following decision rules can be applied to the lower part of the curve: </li><li>c) For each section i of the lower part of the curve: <ul id="ul0021" list-style="none" compact="compact"><li>i) The accuracy-of-fit is set to 0;</li><li>ii) The average brightness (CurBrt(i)) of the pixels (x, y) of the section i is calculated;</li><li>iii) The section i is moved outwards along the normal of the curve and the average brightness (MovedBrt(i)) of the pixels is calculated.</li><li>iv) if MovedBrt(i) &lt; CurBrt(i), then the section is moved "outwards". Otherwise, the section i is moved slightly "inwards" into a shadow area.</li></ul></li></ul> All the features in frontal images are illustrated in FIG. 39. The above-described algorithms are fully automated and robust to different images and various lightening conditions. </li></ul>

1.2 Profile feature detection

FIG. 40 is a detailed block diagram of the profile feature detecting portion 650. The profile feature detecting unit 650 includes a profile region detecting portion 4000, a profile curve detecting portion 4020, a fiducial point detecting portion 4040, and an ear contour detecting portion 4060.

The profile region detecting portion 4000 classifies pixels into skin pixels and non-skin pixels and selects the largest skin-colored connected component as a profile region.

The profile curve detecting portion 4020 detects the rightmost boundary of a face region in a user-specified bounding box in the frontal image as a profile curve.

The ear contour detecting portion 4060 initializes the position of the ear by matching a curve template with the profile image. The initialized ear template is morphed using a contour following algorithm to find a more accurate ear contour.

FIG. 41 is a flowchart of profile feature detection. The profile feature detection process may include profile region detection (operation 4100), profile curve detection (operation 4110), fiducial points detection (operation 4120), and ear contour detection (operation 4130). The detected profile curve can be segmented into sections based on the fiducial points detected from, for example, forehead, nose, lips, chin, neck regions, etc.

Throughout the profile region detection process, the results from previous steps are checked in later steps. If an intermediate result from a previous step is found to be erroneous, the algorithm automatically returns to the previous step to correct errors using a larger amount of image information.

Currently, interaction with a user is required for profile feature detection. As a first example, if the face size is not large enough and the background of a face image is complex and includes a skin-colored object, the user is requested to define a face-bounding rectangle. However, this is an unusual case. Face regions can be fully automatically detected in almost all test images.

As a second example, after the initial positions of the head top and back, eye points, and lips points are set based on priori statistical data, the user may be requested to correct the positions.

1.2.1. Face region detection

The face region detection process includes classifying pixels into skin pixels and non-skin pixels and selecting the largest skin-colored connected component as a face region. When there are two largest connected components having similar sizes, one of the components closer to the center of the image is selected as the face region.

In particular, in a similar manner used in the frontal image process, it is determined whether pixels are skin pixels or non-skin pixels using a normalized r-g color space and a trained skin-color model. The largest skin-color connected component or one of the two largest skin-color components having similar sizes that is closer to the center of the image is selected as a face region.

In some cases, a nose region and the face region may be discontinuous (see FIG. 42). Such a problematic situation can be detected by checking adjacent skin-color connected components, and the nose region and the face region are merged together. There are additional two problematic situations. A first case is that a whole nose region cannot be obtained if lightening is too strong (see FIG. 43). A second case is that a whole chin region cannot be detected if lightening is slightly dark or if mustache is included (see FIG. 44). The first case is recognized in nose bridge tracking procedure after nose tip is detected. The second case is judged after chin and neck points are detected.

When skin detection has failed, the face region is detected using a pyramid-based area segmentation algorithm. An input image for the pyramid-based area segmentation algorithm is one channel in HSV conversion of the original image. This channel is selected based on the performance of discriminating skin from the background across the nose bridge.

1.2.2. Profile curve detection

The rightmost boundary of the face region in a user-specified bounding box obtained from the frontal image is detected as the profile curve.

In particular, when the face region is detected by skin detection, the rightmost face region pixels inside the user-specified bounding box are detected for the profile curve as follows. <ul id="ul0022" list-style="none" compact="compact"><li>1) The input is the binary results of skin detection (1 means that the pixel belongs to skin, and 0 means the opposite case) and the found face region (connected component);</li><li>2) The user manually specifies the face bounding box (This step is unnecessary for most images);</li><li>3) A rough approximation of the profile contour is found. The algorithm constructs a "profile function" x = x(y), where y varies along vertical direction, and x corresponds to the rightmost skin pixel in y row inside the face bounding box. If there is no skin pixel in this row, x(y) is set to zero;</li><li>4) The profile function is smoothened using a 1D Gaussian filter to eliminate random noise (see FIG. 45 for an exemplary profile function).</li></ul>

The image is cropped such as to include only the profile function and scaled to a fixed height to allow easier subsequent processes.

2.2.3. Fiducial points detection

The fiducial points of the profile curve are detected by analyzing the shape of the profile function. <ul id="ul0023" list-style="none" compact="compact"><li>1) A nose tip is the global maximum of the profile function. After the nose tip is detected, a part of the nose bridge is approximated as a line using strong edge pixels above the nose tip. The performance of separating skin from the background across the nose bridge is examined using different channels in HSV conversion of the original image. Furthermore, when the nose bridge line is too far away from the profile curve, it is recognized that skin detection would be failed, and the algorithm goes back to detect the face region using the area segmentation algorithm. </li><li>2) An upper point of forehead ("forehead top") is the most top skin pixel.</li><li>3) An upper part (from the forehead top to the nose tip) of the profile function x = x(y) is approximated with a seventh degree polynominal (see FIG. 46). Bottom-up scanning of the polynominal is performed to find a position where a first derivative of the polynomial is less than a fixed threshold. This point corresponds to the nose bridge top;</li><li>4) Piecewise linear approximation is performed on the lower part (below the nose tip) of the profile function.    a) Line segment's direction is calculated from the first 3 points of the function. b) The distance from the successive point to the current segment is calculated. c) If the calculated distance is too large (more then fixed threshold), a new segment is started and the process goes to step a). d) step (a) is performed.</li><li>5) Among joint-points of the line segments in a predetermined area, a joint-point having a large angle (about 90 degrees) between adjacent segments is found. This point corresponds to the "under nose point" (see FIG. 46).</li><li>6) For the points below "under nose point", the profile function is approximated with line segments estimated using an adaptive polyline fitting algorithm. Each step of this algorithm is as follows.    a) New line segment direction is calculated from the first two points. b) A next point is added to the set of segment-approximated points. c) The segment direction is recalculated by least squares fitting all the points. d) A deviation of each point from the approximating segment is calculated. e) If any point is too far from the segment, the process goes to a). Otherwise, the process goes to b). The chin and neck points are detected from the adaptive polyline fitting results (see the three points marked in FIG. 47). If the chin is too close to the nose tip, it is recognized that skin detection would be failed, and the algorithm goes back to redetect the face region. </li><li>7) It is very difficult to find the upper and lower lip fiducial points with reliability, especially when imaging conditions are greatly varied. In this case, the fiducial points are reasonably approximated by judging the overall face size (see FIG. 48). Some segments in FIG. 48 are described below. <ul id="ul0024" list-style="none" compact="compact"><li>a) "I" is the vertical distance from the "under nose point" to the neck start point.</li><li>b) "a" = 0.225 * I.</li><li>c)"b"=0.125*I.</li><li>d)"c"= 0.125*I.</li></ul></li></ul>

After the fiducial points are found the profile curve segments between the fiducial points are approximated with polynomials. The back and top of the head, together with the eyes, are not directly detected and are estimated from the reasonable proportions of the human head. All the resulting features are shown in FIG. 49.

1.2.4. Ear contour detection

FIG. 50 is a flowchart of ear contour detection. The ear contour detection process includes initializing the ear position by matching a curve template with the profile image (operation 5000) and finding a more accurate ear boundary by deforming an initialized ear template using a contour following algorithm (operation 5020).

FIG. 51 is a flowchart of ear initialization. Referring to FIG. 51, the ear initialization process includes: determining a translation vector of the ear template, rotating the original image such that the segment between the nose bridge top and the chin point becomes vertical, and scaling the length of the segment to a predetermined value (operation 5100); defining an ear search area (operation 5110); matching the border between the face region and hair region with the curve template to find corresponding sub-segments having similar shape from the two curves (operation 5120); detecting segments having similar shapes by matching an edge detected using an edge detector and the ear template if the length of the matching segments is smaller than a predetermined threshold value (operation 5130); and calculating the translation vector from the template segment to the matching image points using a least square algorithm (operation 5140).

The ear contour detection process will be described in detail. The ear contour detection process can be roughly divided into two steps. In a first step, the curve template (see FIG. 52) is matched with color or edge information, and the template is deformed to fit local image information.

In particular, in the ear position initialization step, the orientation and the scale of the original image are normalized. Two calibration points, i.e., the nose bridge top and the chin point, are selected for normalization. The original image is rotated such that the segment connecting the two points becomes absolutely vertical and scaled such that the distance between the two points has a fixed value. A priori rectangle is positioned to define the ear search area in the normalized image. The normalized image, the calibration points, and the search area are shown in FIG. 53.

To find a translation vector for successfully initializing the position of the ear template, the results of skin detection are used. In general, the skin region boundary coincides with the ear boundary at some parts, as shown in FIG. 54. The template is matched with the skin region boundary using a simple curve matching algorithm based on the similarity of curve gradient information to find the segments on these two curves that match well. Next, the translation vector is estimated with the matching segments using the least square method. The results of ear position initialization are illustrated in FIG. 55. The segments that match with the template in the skin region boundary are marked in red.

In some cases, the skin region boundary may not coincide with the ear boundary, for example, when hair is too short or lightening is very strong (see FIG. 56). The algorithm used in the present invention can automatically detect such failure situations by evaluating the length of the matching segments and the position of the translated ear template in the search area. The ear position is initialized using local edge information.

The Nevatia-Batu edge detector is used to extract the edge information from a gray image. Long edge segments are tested to find only one edge segment that best matches with the ear template, using the same curve matching algorithm as used in previous ear initialization algorithm. Relative factors are used in combination for matching evaluation. The relative factors include the matched length in edge segments and segment-based ear template position in the search area.

It is experimentally proved that edge-based ear initialization is more robust than using the face region-based algorithm but is not accurate enough for finding initial segments on the ear boundary. Therefore, the edge-based algorithm is used to complement the face region-based algorithm, thereby enhancing the robustness of the algorithm as a whole. Several examples of edge-based ear initialization are illustrated in FIG. 56.

In a second step, the translated template is deformed to match with the ear boundary. Using ear boundary points obtained in the initialization step (segments from the face region boundary or the Nevatia-Batu edge), the template is fit to the ear according to a contour following scheme. Detailed procedures are as follows. <ul id="ul0025" list-style="none" compact="compact"><li>1) Starting from an ear template point that has already match with image ear boundary, record this point as Cont_n, where Cont is the ear template (sampled as 2D point list), and n is the index of this point in the list;</li><li>2) Find the first successive point satisfying the following constraint: some template points between Cont_n and Cont_next are far enough from the line least square fitted to the point set {<i>Cont</i>_<i>i</i>, <i>i</i>=<i>n</i>,...,<i>next</i>}; next should be at least <i>n +</i> 5 ; if next reaches the extreme point of the template, the contour following algorithm is terminated;</li><li>3) Rotate the segments from Cont_n and Cont_next in some range, centered at Cont_n; and match the rotated segments with local information to find a "best" angle having a maximum matching value; if no correct match is found in the angle range, the algorithm is terminated with a notice of a failure;</li><li>4) Rotate all template points after Cont_n using the best angle, set n=next, go to step 1;</li></ul>

Matching evaluation between a segment and an image is performed based on a combination of two kinds of information. One is the local edge strength evaluated as the sum of intensity differences across the segment. The other information is segment similarity. In other words, the sum of intensity values of all pixels of the segment should do not greatly differ from that of the previous segment. If the result of the matching evaluation based on the two factors is "bad", it is determined that the matching is wrong.

The contour following algorithm is performed twice on the ear top and ear bottom. When the contour following algorithm is terminated with the notice of a failure, which occurs commonly because the ears are occluded by hair as illustrated in FIG. 57, the results of the initialization are directly used.

For the ear bottom, the template length may be not long enough to fit to the ear boundary, so the "tail" of the template is replaced with a long segment. The real bottom position of the ear is found by measuring the edge strength along the matched template. In some images, the ear boundary goes toward top from the bottom. This case can be detected using local edge information and the resulting ear boundary include a tail extending toward the top as shown in FIG. 57.

2. Head model fitting

A full set of face features extracted from frontal and profile photographs and/or 3D stereo depth map is obtained. Stereo depth extraction will be described later.

FIG. 59 is a block diagram of the face model fitting unit 510 of FIG. 5. The face model fitting unit 510 includes a 2-dimensional (2D) point converting portion 5900 and a mesh model fitting portion 5950. FIG. 60 is a flowchart of initial model fitting in the face model fitting unit 510.

Initially, using the length ratios of feature points on the facial feature curve of the 3D genetic head model, feature polynominals detected in the image are converted into 2D points corresponding to features defined in the 3D generic head model (operation 6000). The 3D genetic mesh model is deformed using the detected features of the image and the feature points of the 3D generic mesh model according to a 3-step radial based function (RBF)-based morphing procedure (operation 6050).

The 3-step RBF-based morphing procedure is performed as follows. First, the X and Y coordinates of displaced model key points are set to corresponding image feature positions and the Z coordinate remains as in the generic mesh model to perform RBF interpolation on the frontal features. Secondly, the scale of the profile image is adjusted in consideration of the Y coordinates of the profile features, and profile features are used as input for RBF interpolation. Finally, RBF interpolation is performed using all available features.

RBF-based morphing may be performed such that vertices of the genetic mesh are displaced to corresponding 3D points acquired in a depth information recovery process.

The heat model fitting process will be described in detail. Detected face features are used to deform the genetic model to fit to the input image. To this end, the facial features acquired in the feature detection step are converted into the displacements of points that correspond to the features predefined in the generic model, and all vertices in the model are displaced using a data interpolation algorithm so that the generic model is deformed. The correspondence between the detected features (curves and points) and the model vertices should be set manually beforehand. The correspondence for a certain generic model is fixed, so there is required no user interaction.

A process of setting up the correspondence for one feature curve will be described. The "key" vertices on the model and the distributed positions along facial feature curves are shown in FIG. 61. The facial features on the generic mesh model corresponding to the face feature curves detected in the input image are shown. The feature points are sampled from both the curves at the same length ratios. This process is repeated twice on the profile features to generate two sets of 2D displacements of the model "key" points.

The 3D displacements of "key" vertices according to the corresponding image feature points are determined. In a straightforward method, x and y displacements are obtained from the frontal features and z displacements are obtained from the profile features. However, plausible results cannot be obtained with this method because some frontal features (lower chin part, top and back head parts, etc.) lack y-positional information and there are conflicts between the front and profile feature positions. Data conflicts are inevitable because the input picture images cannot be simultaneously taken and the orientation and the expression of the face always vary at least slightly. Even if the frontal and profile pictures can be simultaneously taken, usually the frontal and profile pictures are not standard. In other words, it is difficult to align the focal axes of two cameras to be perpendicular to each other.

To solve these problems, the RBF-based three-step morphing procedure is used.

2.1. RBF data interpolation

A RBF-based data interpolation method used in the present invention will be described briefly. If two corresponding data set, {<maths id="math0011" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">u</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0011.tif" /></maths>_<i>i</i>,_<i>i</i> = 1,..., <i>N</i>} ⊂ <i>R</i>^<i>3</i> and {<maths id="math0012" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">u</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0012.tif" /></maths>_<i>i</i> ',=1,..., <i>N} ⊂ R</i>^<i>3</i>, which represent 3D samplings before and after the morphing procedure, respectively, are input, <i>f</i> (<maths id="math0013" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">p</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0013.tif" /></maths>) , deformation function in 3D space, is determined as follows:<maths id="math0014" num=""><img file="EP1510973A2_D0014.tif" /></maths> where <ul id="ul0026" list-style="none" compact="compact"><li><maths id="math0015" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">p</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0015.tif" /></maths> is any 3D vector;</li><li><i>ϕ</i>_<i>i</i> is the RBF for <maths id="math0016" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">u</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0016.tif" /></maths>_<i>i</i> , wherein in an embodiment <i>ϕ</i>_<i>i</i> (<i>r</i>) = <i>e</i>^{-<i>r</i>/<i>K</i><sub2><i>i</i></sub2>}, where <i>K</i>_<i>i</i> is a predetermined coefficient that defines the falloff of <maths id="math0017" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">u</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0017.tif" /></maths>_<i>i</i>'s displacement influence;</li><li><maths id="math0018" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">c</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0018.tif" /></maths>₀,<maths id="math0019" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">c</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0019.tif" /></maths>₁,<maths id="math0020" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">c</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0020.tif" /></maths>₂,<maths id="math0021" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">c</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0021.tif" /></maths>₃and <maths id="math0022" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext>λ</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0022.tif" /></maths>_<i>i</i>,<i>i</i>=1,...,<i>N</i> are coefficients, which are all 3D points determined by equation (9) below:<maths id="math0023" num=""><img file="EP1510973A2_D0023.tif" /></maths></li></ul>

Using this data interpolation method, the deformation function <i>f</i>(<maths id="math0024" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">p</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0024.tif" /></maths>) can be determined provided that the correspondence of "key" points between the generic model and the specific person is established. Accordingly, a perfect specific model for the input image can be generated by substituting all generic model vertices into the function <i>f</i>(<maths id="math0025" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">p</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1510973A2_D0025.tif" /></maths>) <i>.</i>

2.2 Three-step morphing procedure

The model fitting process will be described in detail. <ul id="ul0027" list-style="none" compact="compact"><li>1) RBF interpolation is performed using frontal features. The X and Y coordinates of displaced model key points are set to corresponding image feature positions, and the Z coordinates remain as in the generic model. In this step, the frontal features between the model and the image are perfectly matched with each other. This step is necessary for accurate texture mapping.</li><li>2) RBF interpolation is performed using profile features. The Y and Z coordinates of profile key points are set to their corresponding profile image positions, and the X coordinates remain the same as in the generic model. During this step we only determine the Z values for all model vertices. Conflicts between the frontal and profile features, which are likely to occur at nose tip, nose bridge top and lips, can be eliminated by scaling and translating the profile feature curves such that the Y coordinates fit to the corresponding points of the morphed model.</li><li>3) Finally, all the key points are used as RBF interpolation input to determine the resulting head shape. In this step the profile key points remain their positions in the interpolation resulting model of step 2. As for the frontal key points, we set their Z coordinates according to step-2 result, and set X and Y coordinates to step-1 result. If a near front image is available, RBF interpolation can be performed once more to take 3D points reconstructed using stereo information as input data. Exemplary generated face modes are shown in FIG. 63.</li></ul>

3. Texture generation

The generation of a high quality texture for the head model is more important than model fitting since texture makes a major contribution to the visual appearance of the model. Frontal and profile textures are mapped to the model, and a multi-resolution spline texture combination scheme is used to combine different photographs. In addition, an artificial texture is generated for, for example, the chin or neck areas occluded by the jaw and the back side of ears.

FIG. 63 is a block diagram of the texture generating unit 520 of FIG. 5. The texture generating unit 520 includes an input image compensating portion 6300, a frontal/profile texture generating portion 6320, and a texturing completing portion 6340. FIG. 64 is a flowchart of texture generation. A texture generating process will be described with reference to FIGS. 63 and 64.

The input image compensating portion 6300 performs color correction on an input image to compensate for different lightening conditions or color balance variations between cameras (operation 6400). The frontal/profile texture generating portion 6320 generates frontal and profile textures by mapping the frontal and profile images onto a public UV plane based on the match between 3D model vertices and projected 2D positions on the photograph (operation 6420). The texturing completing portion 6040 combines the frontal, profile, and artificial textures using a multi-resolution spline algorithm to complete texturing (operation 6440). The texture generation process will be described in detail.

3.1. Texture coordinate mapping and texture generation

In order to combine the textures obtained at different viewing angles, a public UV plane containing the texture coordinates of model vertices is required. This public UV plane is a 2D plane where the points are matched with 3D model positions. The plane has a normalized coordinate space expressed by M = {(<i>u</i>, <i>v</i>)|<i>u</i>,<i>v</i> ∈ [0,1]}.

To ensure even distribution of model vertices over the texture coordinate space, the UV plane is created by spherical mapping in consideration of the sphere-like shape of the human head. The generated space is manually modified to solve a problem of overlapping, especially in ear areas, on the UV plane. The UV plane is specific to individual models and remains constant once the correspondence has been established, so no further user interaction is required.

To create a textured model, it is required to map the face image onto the UV plane. Since the model has been fitted to the image features, the correspondence between model vertices and the image positions can be easily obtained. Therefore, the image positions can be easily mapped to the texture coordinates on the UV plane.

FIGS. 65 and 66 are frontal and profile textures images, respectively, on the UV planes, in which overlapping texture coordinates appear.

3.3. Texture blending

In this step, the frontal and profile texture images in UV plane and the artificial skin texture for ear are blended to generate one image, which will be rendered to the 3D model surface. For each point <i>p</i> ∈ {(x,y)|x,y ∈ [0,1]} in UV plane, its color in the blended image can be calculated using equation (10) below:<maths id="math0026" num="(10)"><math display="block"><mrow><mtext mathvariant="italic">C</mtext><mtext>(</mtext><mtext mathvariant="italic">p</mtext><mtext>) = </mtext><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">f</mtext></mrow></msub><mtext> (</mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext><msub><mrow><mtext mathvariant="italic">C </mtext></mrow><mrow><mtext mathvariant="italic">f</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext><msub><mrow><mtext mathvariant="italic">+ k</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><mtext> (</mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><mtext> (</mtext><mtext mathvariant="italic">p</mtext><mtext>) + </mtext><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">art</mtext></mrow></msub><mtext> (</mtext><mtext mathvariant="italic">p</mtext><mtext>) </mtext><msub><mrow><mtext mathvariant="italic">C </mtext></mrow><mrow><mtext mathvariant="italic">art</mtext></mrow></msub><mtext> (</mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1510973A2_D0026.tif" /></maths> where <i>C</i>_<i>f</i>,<i>C</i>_<i>s</i>,<i>C</i>_<i>art</i> are the colors of point p for frontal, profile and artificial skin textures, respectively; <i>k</i>_<i>f</i> ,<i>k</i>_<i>s</i>,<i>k</i>_<i>art</i> are weights for the different textures and are normalized to satisfy <i>k</i>_<i>f</i><i>(p)+k</i>_<i>s</i><i>(p)+k</i>_<i>art</i><i>(p)</i>=1 for every <i>p</i> . The weights for texture blending are calculated using a multi-resolution spline algorithm. Based on Gaussian pyramid decomposition, the well-known image blending algorithm used in the present invention can achieve smooth transition between images without blurring or degrading finer image details. The algorithm can be used in blending boundaries having any shapes.

3.4. Artificial skin texture

Artificial textures for filling the chin and neck areas are generated based on color statistics of nearby regions in the profile area. Infrequent colors are discarded, the color of each pixel in the regions is chosen based on the clipped color statistics, and uneven grains are removed by Gaussian smoothening.

The final textured image is shown in FIG. 67. Exemplary textured models are shown in FIG. 68. The back side of the ear, not mapped with overlapping texture, is noticeable. The last two pictures in FIG. 68 show an artificially textured ear part and a non-textured ear part, respectively.

4. 3D reconstruction using stereo image pair

In most cases, the results of 3D reconstruction are reasonable when using only a frontal image or additional profile image. However, the algorithm cannot work properly when an input face image to be reconstructed appears untypical, i.e. when the subjective greatly differs from the generic head model.

In such a case, to further refine the head model, a stereo analysis-based module is incorporated into the system. Two or more facial images captured at slightly different viewing angles can be analyzed using a specialized stereo reconstruction algorithm to produce more precise 3D information for visible parts of the head. An exemplary stereo image pair captured for this purpose is shown in FIG. 69.

FIG. 70 is a block diagram of the depth information generating unit 540 of FIG. 5. The depth information generating unit 540 includes a feature point detecting portion 7000, a disparity obtaining portion 7020, and a disparity-to-depth information converting portion 7040. FIG. 71 is a flowchart of depth information generation from frontal and near-frontal images. The depth information generation process will be described with reference to FIGS. 70 and 71.

The feature point detecting portion 7000 determines image features points in the frontal image (operation 7100), and performs model-based Lucas-Kanade tracking on the feature points to find corresponding points in the near-frontal image (operation 7110).

The disparity obtaining portion 7020 obtains a dense disparity map by data interpolation using the matching correspondence (operation 7120). Finally, the disparity-to-depth information converting portion 7040 converts the disparity map into the depth information (operation 7130).

The conversion from the disparity map to the depth information is achieved based on a difference value between the maximum and minimum disparity values. The difference value is divided by the head width and multiplied by a predetermined constant to obtain a coefficient. The depth value of a given pixel is obtained by multiplying the coefficient by a value obtained by subtracting the minimum disparity value from a measured disparity value. These processes will be described in detail.

4.1 Disparity estimation from stereo image pair

Stereo matching by feature tracking will be described. The key concept of 3D object reconstruction is "stereo matching" - the process of finding the "same" points across stereo images (here "same" means that these 2D projections correspond to the unique 3D point). After stereo matching, the 3D positions can be recovered.

Despite the simplicity of the underlying idea, stereo matching is a very complicated task. Many problems arise while stereo matching is performed on stereo images with significant dissimilarity. Furthermore, stereo matching causes a computationally complex problem because all possible correspondences across stereo images have to be calculated to complete the matching process.

However, according to the present invention, desirable matching results can be obtained in a face modeling process by using the following ideas. Since the view angles of stereo pairs are not significantly different (frontal and near frontal), stereo matching can be treated as a process of objects tracking between the stereo images. Accordingly, a feature-tracking algorithm can be utilized.

Most feature-tracking algorithms work on a set of separate points selected from a first image. The goal is to track the positions of these points in consecutive images. In this case, tracking and matching are identical processes. Compared with complete point-by-point epipolar matching, feature tracking may lead to extra mismatches, but does not require a rectification stage. All points can be independently processed to construct any epipolar geometry. Therefore, this feature tracking can be used when using an uncalibrated camera. For these reasons, stereo matching using feature tracking is performed in an embodiment. The used tracking algorithm will be described.

With the assumption that A(x,y) and B(x,y) are two 2D grayscale images, an image point A(px, py) in a first image is considered. The goal of feature tracking is to find the location of B(px+vx, py+vy) in a second image such that A(px, py) and B(px+dx, py+dy) are "similar". A vector v = [vx vy] is the image velocity and is also known as optical flow at point [px, py]. The image velocity v is defined as a vector that minimizes the residual function ε in the (2ω_x+1 )x(2ω_y+1) vicinity of point [px, py]:<maths id="math0027" num=""><img file="EP1510973A2_D0027.tif" /></maths>

The velocity, recorded as v_opt, minimizing the above residual function can be found using the following standard Lucas-Kanade equation:<maths id="math0028" num="(12)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext mathvariant="italic">opt</mtext></mrow></msub><mtext> = </mtext><msup><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext mathvariant="italic">b</mtext></mrow></math><img file="EP1510973A2_D0028.tif" /></maths> where<maths id="math0029" num=""><img file="EP1510973A2_D0029.tif" /></maths><maths id="math0030" num="(14)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">I</mtext></mrow><mrow><mtext mathvariant="italic">x</mtext></mrow></msub><mtext> (</mtext><mtext mathvariant="italic">x, y</mtext><mtext>)= </mtext><mfrac><mrow><mtext>∂</mtext><mtext mathvariant="italic">A</mtext><mtext>(</mtext><mtext mathvariant="italic">x, y</mtext><mtext>)</mtext></mrow><mrow><mtext>∂</mtext><mtext mathvariant="italic">x</mtext></mrow></mfrac><mtext>= </mtext><mfrac><mrow><mtext mathvariant="italic">A</mtext><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext> + 1, </mtext><mtext mathvariant="italic">y</mtext><mtext>) - </mtext><mtext mathvariant="italic">A</mtext><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext> -1, </mtext><mtext mathvariant="italic">y</mtext><mtext>)</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac></mrow></math><img file="EP1510973A2_D0030.tif" /></maths><maths id="math0031" num="(15)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">I</mtext></mrow><mrow><mtext mathvariant="italic">y</mtext></mrow></msub><mtext> (</mtext><mtext mathvariant="italic">x</mtext><mtext>,</mtext><mtext mathvariant="italic">y</mtext><mtext>)</mtext><mtext mathvariant="italic">=</mtext><mtext></mtext><mfrac><mrow><mtext>∂</mtext><mtext mathvariant="italic">A</mtext><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext>, </mtext><mtext mathvariant="italic">y</mtext><mtext>)</mtext></mrow><mrow><mtext>∂</mtext><mtext mathvariant="italic">y</mtext></mrow></mfrac><mtext> = </mtext><mfrac><mrow><mtext mathvariant="italic">A</mtext><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext>, </mtext><mtext mathvariant="italic">y</mtext><mtext> +1) - </mtext><mtext mathvariant="italic">A</mtext><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext>, </mtext><mtext mathvariant="italic">y</mtext><mtext> -1) </mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac></mrow></math><img file="EP1510973A2_D0031.tif" /></maths><maths id="math0032" num="(16)"><math display="block"><mrow><mtext>δl(x,y) ≡ A(x, y) - B(x, y)</mtext></mrow></math><img file="EP1510973A2_D0032.tif" /></maths>

After the 3D reconstruction, the generic model is fitted to the image using the above-described model fitting algorithm.

As described above, in an apparatus and method for image-based photorealistic 3D face modeling according to the present invention, data obtained using a relatively cheap device, such as a digital camera, can be processed in an automated manner, and satisfactory results can be obtained even from imperfect input data. In other words, according to the present invention, facial features can be extracted in an automated manner, and a robust "human-quality" face analysis algorithm is used.

While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the scope of the present invention as defined by the following claims.