Rapid computer modeling of faces for animation Number:7,142,698 from the United States Patent and Trademark Office (PTO) owispatent Described herein is a technique for creating a 3D face model using images obtained from an inexpensive camera associated with a general-purpose computer. Two still images of the user are captured, and two video sequences. The user is asked to identify five facial features, which are used to calculate a mask and to perform fitting operations. Based on a comparison of the still images, deformation vectors are applied to a neutral face model to create the 3D model. The video sequences are used to create a texture map. The process of creating the texture map references the previously obtained 3D model to determine poses of the sequential video images.<H animation, modeling, Rapid, computer, , 7142698.html, Patent, pto, 7142698

Title: Rapid computer modeling of faces for animation

Abstract: Described herein is a technique for creating a 3D face model using images obtained from an inexpensive camera associated with a general-purpose computer. Two still images of the user are captured, and two video sequences. The user is asked to identify five facial features, which are used to calculate a mask and to perform fitting operations. Based on a comparison of the still images, deformation vectors are applied to a neutral face model to create the 3D model. The video sequences are used to create a texture map. The process of creating the texture map references the previously obtained 3D model to determine poses of the sequential video images.

Patent Number: 7,142,698 Issued on 11/28/2006 to Liu, et al.

Inventors: Liu; Zicheng (Bellevue, WA), Zhang; Zhengyou (Redmond, WA), Cohen; Michael F. (Seattle, WA), Jacobs; Charles E. (Seattle, WA)
Assignee: Microsoft Corporation (Redmond, WA)

Appl. No.: 11/275,340

Filed: December 27, 2005

Related U.S. Patent Documents


Application Number	Filing Date	Patent Number	Issue Date
11048398	Feb., 2005	7082212
10846302	May., 2004	6950537
09754938	Jan., 2001	6807290
60188603	Mar., 2000

Current U.S. Class: 382/118

Current International Class: G06K 9/00 (20060101)

Field of Search: 382/115-118,154,100,103,107,190,209,216-218,285,276,294-297,236,162-165 345/418-428,581-589,473-475,441 348/14.1-14.16,77-78 340/5.82-5.83

References Cited [Referenced By]

U.S. Patent Documents


5469512	November 1995	Fujita et al.
5774591	June 1998	Black et al.
5864630	January 1999	Cosatto et al.
5990901	November 1999	Lawton et al.
5995119	November 1999	Cosatto et al.
6009210	December 1999	Kang
6047078	April 2000	Kang
6072496	June 2000	Guenter et al.
6072903	June 2000	Maki et al.
6118887	September 2000	Cosatto et al.
6154559	November 2000	Beardsley
6163322	December 2000	LaChapelle
6173069	January 2001	Daly et al.
6188777	February 2001	Darrell et al.
6301370	October 2001	Steffens et al.
6445810	September 2002	Darrell et al.
6496594	December 2002	Prokoski
6504546	January 2003	Cosatto et al.
6526161	February 2003	Yan
6532011	March 2003	Francini et al.
6549200	April 2003	Mortlock et al.
6556196	April 2003	Blanz et al.
6580821	June 2003	Roy
6661907	December 2003	Ho et al.
6664956	December 2003	Erdem
6714660	March 2004	Ohba
6747652	June 2004	Inoue et al.
6771303	August 2004	Zhang et al.
6807290	October 2004	Liu et al.
6879709	April 2005	Tian et al.
6919892	July 2005	Cheiky et al.
2002/0102010	August 2002	Liu

Foreign Patent Documents


11-1612821	Jun., 1999	JP

Other References

Barron, J. et al., "Performance of optical flow techniques", The International Journal of Computer Vision, 12(1):43-77, 1994. cited by oth- er .
Guenter, B. et al., "Making faces", Computer Graphics, Annual Conference Series, pp. 55-66. Siggraph, Jul. 1998. cited by other .
Harris, C. et al., "A combined corner and edge detector", Plessey Research Roke Manor, UK, pp. 147-151, 1988. cited by other .
Horn, B.K. "Closed-form Solution of Absolute Orientation using Unit Quatemions", Journal of Optical Society of America, 4(4):629,642, Apr. 1987. cited by other .
Horn, B.K.P. et al., "Determining Optical Flow", Artificial Intelligence, 17:185-203, 1981. cited by other .
Ip, H.H.S et al., "Constructing a 3d individualized head model from two orthogonal views", The Visual Computer, (12):254-266, 1966. cited by othe- r .
Kass, M. et al., "SNAKES: Active contour models", The International Journal of Computer Vision, 1:321-332, Jan. 1988. cited by other .
Lanitis, A. et al., "Automatic interpretation and coding of face images using flexible models", IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(7):743-756, 1997. cited by other .
Lee, Y.C. et al., "Constructing physics-based facial models of individuals", Proceedings of Graphics Interface, pp. 1-8, 1993. cited by other .
Lee, Y.C. et al., "Realistic modeling for facial animation", Computer Graphics, Annual Conference Series, pp. 55-62. SIGGRAPH, 1995. cited by other .
Lewis, J.P. "Algorithms for solid noise synthesis", Computer Graphics, Annual Conference Series, 23(3):263-270. Siggraph, 1989. cited by other .
Magneneat-Thalmann, N. et al., "Design transformation and animation of human faces", Visual Computer, 5 (1/2):32-39, 1989. cited by other .
Parke, F.I. "Computer generated animation of faces", ACM National conference, 1:451-457, Nov. 1972. cited by other .
Perlin, K. et al., "Improv: A system for scripting interactive actors in virtual worlds", Computer Graphics, Annual Conference Series, pp. 205-215. Siggraph, Aug. 1995. cited by other .
Platt, S. et al., "Animating facial expressionx", Computer Graphics, 15(3):245-252, 1981. cited by other .
Shinijiro Kawato et al. "Automatic Skin-color Disribution Extraction for Face Detection and Tracking" IEEE 0-7803-5747, pp. 1415-1418. cited by other .
Terzopoulos, D. et al., "Physically based facial modeling, analysis, and animation", Visualization and Computer Animation, 1:73-80, 1990. cited by other .
Todd, J.T. et al., "The perception of human growth", Scientific American, 242(2):132-144, 1980. cited by other .
Waters, K. "A muscle for animating three-dimensional facial expression", Computer Graphics, 21(4):17-24, 1987. cited by other .
Zhang, Z. "Determining the epipolar geometry and its uncertainty: A Review", The International Journal of Computer Vislon, 27(2):161-195, 1998. cited by other .
Zhang, Z. "Flexible camera calibration by viewing a plane from unknown orientations", International Conference on Computer Vision (ICCV '99), IEEE, pp. 666-673, 1999. cited by other .
Zhang, Z. "Motion and structure from two perspective views: From essential parameters to euclidean motion through the fundamental matrix", Journal of the Optical Society of America A, 14(11):2938-2950, 1997. cited by oth- er .
Zheng, J.Y. "Acquiring 3-d models from sequences on contours", IEEE Transactions of Pattern Analysis and Machine Intelligence, 16(2):163-178, Feb. 1994. cited by other .
Akimoto et al."Automatic Creation of 3D Facial Models" IEEE Computer Graphics & Applications 0272-16/93 1993 pp. 16-22. cited by other .
Blanz et al., "Face recognition based on fitting a 3D morphable model", IEEE, 0162-8828/03 pp. 1083-1074. cited by other .
Dariush et al., "Spatiotemporal Analysis of Face Profiles: Detection Segmentation and Registration" IEEE Inspec Accession No. 5920418 pp. 248-253. cited by other .
DeCarlo et al., "An anthropometric face model using variational techniques", University of Pennsylvania, p. 1-8. cited by other .
Di Paoloa, "FaceSpace: a facial spatial domain toolkit", IEEE, 1093-9547, p. 1-5. cited by other .
Faugeras, "Three Dimensional Computer Vision"; 1999; pp. 1-663. cited by other .
Fritsch et al. Improving adaptive skin color segmentation by incorporating results from face detection, IEEE 0-7803-7549-9, 337-343. cited by other .
Fua et al., "From Regular Images to Animated Heads: A Least Squares Approach"; pp. 1-15. cited by other .
Fua, "Using Model-Driven Bundle-Adjustment to Model Heads from Raw Video Sequences"; pp. 1-8. cited by other .
Jebara et al., "Parametrized Structure from Motion for 3D Adaptive Feedback Tracking of Faces"; 1997 pp. 144-150. cited by other .
Kang et al., "Appearance-based Structure from Motion Using Linear Classes of 3D Models"; pp. I-ii 1-32. cited by other .
Kawato et al,. "Automatic Skin-color Distribution Extraction for Detection and Tracking", IEEE 0-7803-5747-700, 2000 IEEE. cited by other .
Liu et al,. "Robust Head motion Computation by Taking Advantage of Physical Properties", IEEE 0-7695-0939-8/00, pp. 73-77. cited by other .
Lopez et al., "3D Head Pose Computation from 2D Images", IEEE, 0-8186-7310, pp. 599-602. cited by other .
Macliu et al., "A robust model-based approach for 3D head tracking in video sequences", pp. 169-174. cited by other .
More, "The Levenberg-Marquardt Algorithm: Imiplementation and Theory"; 1978; pp. 105-116. cited by other .
Ohya et al. "Artisitic Anatomy Based Real Time reporoduction of Facial Expressions", IEEE 0-7695-0253,684689. cited by other .
Parke, "Computer graphics models for the human face", IEEE, Ch 515-6/79/0000-0724 p. 724-727. cited by other .
Perlin, "Realitme responsive animation with personality", IEEE, 1071-2626/95 p. 5-15. cited by other .
Pighin et al., "Resynthesizing facial animation thorugh 3D model-tracking", IEEE, Inspec Accession No. 6371194 p. 1-8. cited by othe- r .
Pighin et al., "Synthesizing Realistic Facial Expressions from Photographs" pp. 1-20. cited by other .
Saber et al. "Face detection and facial feature extraction using color, shape and symmetry based cost function", IEEE 1015-4651/96, 654-658. cite- d by other .
Shakunaga et al., "Integration of eigentemplate and structure for automatic facial feature detection", IEEE, Inspec Accession No. 5920393 p. 1-6. cited by other .
Shinijiro Kawato et al. "Automatic Skin-color Distribution Extraction for Face Detection and Tracking" IEEE 0-7803-5747, pp. 1415-1418. cited by other .
Skaria et al., "Modeling subdivision control meshes for creating coorton faces", IEEE, 0-7695-0853-7/01 pp. 216-225. cited by other .
Soon-Cang Pei et al., "Global Motion Estimation in Model-Based Image Coding by Tracking Three-Dimensional Contour Feature Points", IEEE, 1051-8215/98 p. 181-190. cited by other .
Spors et al. "A real-time face tracker for color video", IEEE 0-7803-7041-4/01, 1493-1496. cited by other .
Terzopoulos et al., "Analysis of facial images using physical and anatomical models", IEEE, CH2934-8/90/0000/072 p. 727-732. cited by other .
Vetter et al., "Linear object classes and image synthesis", IEEE, 0162-8828/97, pp. 733-741. cited by other .
Zhang et al, "Rapid Modeling of 3D Faces for Animation Using An Efficient Adaptation Algorithm", ACM1-581 3-883-0/04, pp. 173-181. cited by other .
Zhang et al., "A New Mutlistage Approach to Motion and Structure Estimation: From Essential Parameters to Euclidean Motion Via Fundamental Matrix"; Jun. 1996; pp. 1-38. cited by other .
Zhang et al., "On the Optimization Criteria Used in Tow-View Motion Analysis"; Jul. 1998; pp. 717-729. cited by other .
Zheng et al., "3D models from contours", IEEE, 0-8186 p. 349-353. cited by other.

Primary Examiner: Sherali; Ishrat
Attorney, Agent or Firm: Lee & Hayes, PLLC

Parent Case Text

RELATED APPLICATIONS

This application is a continuation of U.S. patent application Ser. No. 11/048,398, filed Feb. 1, 2005 now U.S. Pat. No. 7,082,212, which is a continuation of U.S. patent application Ser. No. 10/846,302, filed May 14, 2004 (now U.S. Pat. No. 6,950,537); which is a divisional of U.S. patent application Ser. No. 09/754,938, filed Jan. 4, 2001 (now U.S. Pat. No. 6,807,290); which claims the benefit of U.S. Provisional Application No. 60/188,603, filed Mar. 9, 2000, all of which are incorporated herein by reference.

Claims

The invention claimed is:

1. One or more computer-readable media containing a program that is executable by a computer to create a three-dimensional model of a face, the program comprising the following actions: capturing at least two images of the face; matching a plurality of points between the images; estimating rotation and translation of the face based on the images; determining 3D positions of the matched points based on the estimated rotation and translation to create a constructed face model, the constructed face model comprising a plurality of points specified in three dimensions; and applying a combination of deformation vectors to a pre-specified face model to deform the pre-specified face model approximately to the constructed face model, wherein the pre-specified face model comprises a plurality points specified in three dimensions and each deformation vector specifies a plurality of displacements corresponding respectively to the plurality of points of the pre-specified face model.

2. One or more computer-readable media as recited in claim 1, wherein said estimating is based on matched points within the images.

3. One or more computer-readable media as recited in claim 1, wherein the applying action comprises calculating a linear combination of the deformation vectors and the pre-specified face model.

4. One or more computer-readable media as recited in claim 1, wherein the applying action comprises calculating a linear combination of the deformation vectors and the pre-specified face model, the actions further comprising: multiplying each deformation vector by a respective multiplicative constant before when calculating the linear combination; and selecting the multiplicative constants to minimize a summation of distances between the deformed face model and the points of the constructed face model.

5. One or more computer-readable media as recited in claim 1, wherein the applying action comprises calculating a linear combination of the deformation vectors and the pre-specified face model, the actions further comprising: identifying one or more points of the constructed face model and corresponding points of the pre-specified face model; multiplying each deformation vector by a respective multiplicative constant before when calculating the linear combination; and selecting the multiplicative constants to minimize a summation of the distances between the identified points of the constructed face model and the corresponding points of the pre-specified face model.

6. One or more computer-readable media as recited in claim 1, wherein the applying action comprises calculating a linear combination of the deformation vectors and the pre-specified face model, the actions further comprising: identifying one or more points of the constructed face model and corresponding points of the pre-specified face model; multiplying each deformation vector by a respective multiplicative constant before when calculating the linear combination; and selecting the multiplicative constants to minimize (a) a summation of the distances between the identified points of the constructed face model and the corresponding points of the pre-specified face model, and (b) a summation of the distances between the identified points of the constructed face model and the corresponding points of the pre-specified face model.

7. A method of creating a three-dimensional model of a face, comprising: capturing at least two images of the face; matching a plurality of points between the images; estimating rotation and translation of the face based the images; determining 3D positions of the matched points based on the estimated rotation and translation to create a constructed face model, the constructed face model comprising a plurality of points specified in three dimensions; and applying a combination of deformation vectors to a pre-specified face model to deform the pre-specified face model approximately to the constructed face model, wherein the pre-specified face model comprises a plurality of points specified in three dimensions and each deformation vector specifies a plurality of displacements corresponding respectively to the plurality of three dimensional points of the pre-specified face model.

8. A method as recited in claim 7, wherein said estimating is based on matched points within the images.

9. A method as recited in claim 7, wherein the applying comprises calculating a linear combination of the deformation vectors and the pre-specified face model.

10. A method as recited in claim 7, wherein the applying comprises calculating a linear combination of the deformation vectors and the pre-specified face model, the actions further comprising: multiplying each deformation vector by a respective multiplicative constant before when calculating the linear combination; and selecting the multiplicative constants to minimize a summation of distances between the deformed face model and the points of the constructed face model.

11. A method as recited in claim 7, wherein the applying comprises calculating a linear combination of the deformation vectors and the pre-specified face model, the actions further comprising: identifying one or more points of the constructed face model and corresponding points of the pre-specified face model; multiplying each deformation vector by a respective multiplicative constant before when calculating the linear combination; and selecting the multiplicative constants to minimize a summation of distances between the identified points of the constructed face model and the corresponding points of the pre-specified face model.

12. A method as recited in claim 7, wherein the applying comprises calculating a linear combination of the deformation vectors and the pre-specified face model, the actions further comprising: identifying one or more points of the constructed face model and corresponding points of the pre-specified face model; multiplying each deformation vector by a respective multiplicative constant before when calculating the linear combination; and selecting the multiplicative constants to minimize (a) a summation of distances between the deformed face model and the points of the constructed face model, and (b) a summation of distances between the identified points of the constructed face model and the corresponding points of the pre-specified face model.

13. An apparatus that creates a three-dimensional model of a face, the apparatus comprising: means for capturing at least two images of the face; means for matching a plurality of points between the images; means for estimating rotation and translation of the face based on the images; means for determining 3D positions of the matched points based on the estimated rotation and translation to create a constructed face model, the constructed face model comprising a plurality of points specified in three dimensions; and means for applying a combination of deformation vectors to a pre-specified face model to deform the pre-specified face model approximately to the constructed face model, wherein the pre-specified face model comprises a plurality points specified in three dimensions and each deformation vector specifies a plurality of displacements corresponding respectively to the plurality of points of the pre-specified face model.

14. An apparatus as recited in claim 13, wherein said estimating means performs estimation based on matched points within the images.

15. An apparatus as recited in claim 13, wherein the applying means is capable of calculating a linear combination of the deformation vectors and the pre-specified face model.

16. An apparatus as recited in claim 13, wherein the applying means is capable of calculating a linear combination of the deformation vectors and the pre-specified face model, the apparatus further comprising: means for multiplying each deformation vector by a respective multiplicative constant before when calculating the linear combination; and means for selecting the multiplicative constants to minimize a summation of distances between the deformed face model and the points of the constructed face model.

17. An apparatus as recited in claim 13, wherein the applying means is capable of calculating a linear combination of the deformation vectors and the pre-specified face model, the apparatus further comprising: means for identifying one or more points of the constructed face model and corresponding points of the pre-specified face model; means for multiplying each deformation vector by a respective multiplicative constant before when calculating the linear combination; and means for selecting the multiplicative constants to minimize a summation of the distances between the identified points of the constructed face model and the corresponding points of the pre-specified face model.

18. An apparatus as recited in claim 13, wherein the applying means is capable of calculating a linear combination of the deformation vectors and the pre-specified face model, the apparatus further comprising: means for identifying one or more points of the constructed face model and corresponding points of the pre-specified face model; means for multiplying each deformation vector by a respective multiplicative constant before when calculating the linear combination; and means for selecting the multiplicative constants to minimize (a) a summation of the distances between the identified points of the constructed face model and the corresponding points of the pre-specified face model, and (b) a summation of the distances between the identified points of the constructed face model and the corresponding points of the pre-specified face model.

Description

TECHNICAL FIELD

The disclosure below relates to generating realistic three-dimensional human face models and facial animations from still images of faces.

BACKGROUND

One of the most interesting and difficult problems in computer graphics is the effortless generation of realistic looking, animated human face models. Animated face models are essential to computer games, film making, online chat, virtual presence, video conferencing, etc. So far, the most popular commercially available tools have utilized laser scanners. Not only are these scanners expensive, the data are usually quite noisy, requiring hand touchup and manual registration prior to animating the model. Because inexpensive computers and cameras are widely available, there is a great interest in producing face models directly from images. In spite of progress toward this goal, the available techniques are either manually intensive or computationally expensive.

Facial modeling and animation has been a computer graphics research topic for over 25 years [6, 16, 17, 18, 19, 20, 21, 22, 23, 27, 30, 31, 33]. The reader is referred to Parke and Waters' book [23] for a complete overview.

Lee et al. [17, 18] developed techniques to clean up and register data generated from laser scanners. The obtained model is then animated using a physically based approach.

DeCarlo et al. [5] proposed a method to generate face models based on face measurements randomly generated according to anthropometric statistics. They showed that they were able to generate a variety of face geometries using these face measurements as constraints.

A number of researchers have proposed to create face models from two views [1, 13, 4]. They all require two cameras which must be carefully set up so that their directions are orthogonal. Zheng [37] developed a system to construct geometrical object models from image contours, but it requires a turn-table setup.

Pighin et al. [26] developed a system to allow a user to manually specify correspondences across multiple images, and use vision techniques to computer 3D reconstructions. A 3D mesh model is then fit to the reconstructed 3D points. They were able to generate highly realistic face models, but with a manually intensive procedure.

Blanz and Vetter [3] demonstrated that linear classes of face geometries and images are very powerful in generating convincing 3D human face models from images. Blanz and Vetter used a large image database to cover every skin type.

Kang et al. [14] also use linear spaces of geometrical models to construct 3D face models from multiple images. But their approach requires manually aligning the generic mesh to one of the images, which is in general a tedious task for an average user.

Fua et al. [8] deform a generic face model to fit dense stereo data, but their face model contains a lot more parameters to estimate because basically all of the vertexes are independent parameters, plus reliable dense stereo data are in general difficult to obtain with a single camera. Their method usually takes 30 minutes to an hour, while ours takes 2 3 minutes.

Guenter et al. [9] developed a facial animation capturing system to capture both the 3D geometry and texture image of each frame and reproduce high quality facial animations. The problem they solved is different from what is addressed here in that they assumed the person's 3D model was available and the goal was to track the subsequent facial deformations.

SUMMARY

The system described below allows an untrained user with a PC and an ordinary camera to create and instantly animate his/her face model in no more than a few minutes. The user interface for the process comprises three simple steps. First, the user is instructed to pose for two still images. The user is then instructed to turn his/her head horizontally, first in one direction and then the other. Third, the user is instructed to identify a few key points in the images. Then the system computes the 3D face geometry from the two images, and tracks the video sequences, with reference to the computed 3D face geometry, to create a complete facial texture map by blending frames of the sequence.

To overcome the difficulty of extracting 3D facial geometry from two images, the system matches a sparse set of corners and uses them to compute head motion and the 3D locations of these corner points. The system then fits a linear class of human face geometries to this sparse set of reconstructed corners to generate the complete face geometry. Linear classes of face geometry and image prototypes have previously been demonstrated for constructing 3D face models from images in a morphable model framework. Below, we show that linear classes of face geometries can be used to effectively fit/interpolate a sparse set of 3D reconstructed points. This novel technique allows the system to quickly generate photorealistic 3D face models with minimal user intervention.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of a computer system capable of performing the operations described below.

FIG. 2 illustrates how to mark facial features on an image.

FIGS. 3, 5, 6 are flow charts showing sequences of actions for creating a 3D face model.

FIG. 4 shows the selection of different head regions as described below.

FIG. 7 illustrates a coordinate system that is based on symmetry between selected feature points on an image.

DETAILED DESCRIPTION

The following description sets forth a specific embodiment of a 3D modeling system that incorporates elements recited in the appended claims. The embodiment is described with specificity in order to meet statutory requirements. However, the description itself is not intended to limit the scope of this patent. Rather, the claimed invention might eventually be embodied in other ways, to include different elements or combinations of elements similar to the ones described in this document, in conjunction with other present or future technologies.

System Overview

FIG. 1 shows components of our system. The equipment includes a computer 10 and a video camera 12. The computer is a typical desktop, laptop, or similar computer having various typical components such as a keyboard/mouse, display, processor, peripherals, and computer-readable media on which an operating system and application programs are stored and from which the operating system and application programs are executed. Such computer-readable media might include removable storage media, such as floppy disks, CDROMs, tape storage media, etc. The application programs in this example include a graphics program designed to perform the various techniques and actions described below.

The video camera is an inexpensive model such as many that are widely available for Internet videoconferencing. We assume the intrinsic camera parameters have been calibrated, a reasonable assumption given the simplicity of calibration procedures [36].

Data Capture

The first stage is data capture. The user takes two images with a small relative head motion, and two video sequences: one with the head turning to each side. Alternatively, the user can simply turn his/her head from left all the way to the right, or vice versa. In that case, the user needs to select one approximately frontal view while the system automatically selects the second image and divides the video into two sequences. In the seque, we call the two images the base images.

The user then locates five markers in each of the two base images. As shown in FIG. 2, the five markers correspond to the two inner eye corners 20, nose tip 21, and two mouth corners 22.

The next processing stage computes the face mesh geometry and the head pose with respect to the camera frame using the two base images and markers as input.

The final stage determines the head motions in the video sequences, and blends the images to generate a facial texture map.

Notation

We denote the homogeneous coordinates of a vector x by {tilde over (x)}, i.e., the homogeneous coordinates of an image point m=u,v).sup.T are {tilde over (m)}=(u,v1).sup.T, and those of a 3D point p=(x,y,z).sup.T are {tilde over (p)}(=x,y,z,1).sup.T. A camera is described by a pinhole model, and a 3D point p and its image point m are related by .lamda.{tilde over (m)}=AP.OMEGA.{tilde over (p)} where .lamda. is a scale, and A, P, and .OMEGA. are given by

.alpha..lamda..beta..times..times..times..times..OMEGA. ##EQU00001## The elements of matrix A are the intrinsic parameters of the camera and matrix A maps the normalized image coordinates to the pixel image coordinates (see e.g. [7]). Matrix P is the perspective projection matrix. Matrix .OMEGA. is the 3D rigid transformation (rotation R and translation t) from the object/world coordinate system to the camera coordinate system. When two images are concerned, a prime ' is added to denote the quantities related to the second image.

The fundamental geometric constraint between two images is known as the epipolar constraint [7, 35]. It states that in order for a point m in one image and a point m' in the other image to be the projections of a single physical point in space, or in other words, in order for them to be matched, they must satisfy {tilde over (m)}'.sup.TA'.sup.-TEA.sup.-1{tilde over (m)}=0 where E [t.sub.r].sub.xR.sub.r is known as the essential matrix, (R.sub.rt.sub.r) is the relative motion between the two images, and [t.sub.r].sub.x is a skew symmetric matrix such that t.sub.r.times.v=[t.sub.r].sub.xv for any 3D vector v. Linear Class of Face Geometries

Instead of representing a face as a linear combination of real faces or face models, we represent it as a linear combination of a neutral face model and some number of face metrics, where a metric is a deformation vector that linearly deforms a face in a certain way, such as to make the head wider, make the nose bigger, etc. Each deformation vector specifies a plurality of displacements corresponding respectively to the plurality of 3D points of the neutral face model.

To be more precise, let's denote the face geometry by a vector S=(v.sub.1.sup.T, . . . v.sub.n.sup.T).sup.T, where v.sub.i=(X.sub.i, Y.sub.i, Z.sub.i).sup.T, (i=1, . . . , n) are the vertices, and a metric by a vector M=(.delta.v.sub.1, . . . , .delta.v.sub.n), where .delta.v.sub.i=(.delta.X.sub.i, .delta.Y.sub.i, .delta.Z.sub.i).sup.T. Given a neutral face S.sup.0=(v.sub.1.sup.0T, . . . v.sub.n.sup.0T).sup.T, and a set of m metrics M.sup.j=(.delta.v.sub.1.sup.jT, . . . .delta.v.sub.n.sup.jT).sup.T, the linear space of face geometries spanned by these metrics is

.times..times..times..times..times..times..times..times..di-elect cons. ##EQU00002##

where c.sub.j's are the metric coefficients and l.sub.j and u.sub.j are the valid range of c.sub.j. In our implementation, the neutral face and all the metrics are designed by an artist, and it is done only once. The neutral face contains 194 vertices and 360 triangles. There are 65 metrics.

Image Matching and 3D Reconstruction

We now describe our techniques to determine the face geometry from just two views. The two base images are taken in a normal room by a static camera while the head is moving in front. There is no control on the head motion, and the motion is unknown. We have to determine first the motion of the head and match some pixels across the two views before we can fit an animated face model to the images. However, some preprocessing of the images is necessary.

Determining Facial Portions of the Images

FIG. 3 shows actions performed to distinguish a face in the two selected images from other portions of the images.

There are at least three major groups of objects undergoing different motions between the two views: background, head, and other parts of the body such as the shoulder. If we do not separate them, there is no way to determine a meaningful head motion, since the camera is static, we can expect to remove the background by subtracting one image from the other. However, as the face color changes smoothly, a portion of the face may be marked as background. Another problem with the image subtraction technique is that the moving body and the head cannot be distinguished.

An initial step 100 comprises using image subtraction to create a first mask image, in which pixels having different colors in the two base images are marked.

A step 101 comprises identifying locations of a plurality of distinct facial features in the base images. In this example, the user does this manually, by marking the eyes, nose, and mouth, as described above and shown in FIG. 2. Automated techniques could also be used to identify these points.

A step 102 comprises calculating a range of skin colors by sampling the base images at the predicted portions, or at locations that are specified relative to the user-indicated locations of the facial features. This allows us to build a color model of the face skin. We select pixels below the eyes and above the mouth, and compute a Gaussian distribution of their colors in the RGB space. If the color of a pixel matches this face skin color model, the pixel is marked as a part of the face.

A step 103 comprises creating a second mask image that marks any image pixels having colors corresponding to the calculated one or more skin colors.

Either union or intersection of the two mask images is not enough to locate the face because it will include either too many (e.g., including undesired moving body) or too few (e.g., missing desired eyes and mouth) pixels. Since we already have information about the position of eye corners and mouth corners, we initially predict the approximate boundaries of the facial portion of each image, based on the locations identified by the user. More specifically, step 104 comprises predicting an inner area and an outer area of the image. The outer area corresponds roughly to the position of the subject's head in the image, while the inner area corresponds roughly to the facial portion of the head.

FIG. 4 shows these areas, which are defined as ellipses. The inner ellipse 23 covers most of the face, while the outer ellipse 24 is usually large enough to enclose the whole head. Let d.sub.e be the image distance between the two inner eye corners, and d.sub.em, the vertical distance between the eyes and the mouth. The width and height of the inner ellipse are set to 5d.sub.e and 3d.sub.em. The outer ellipse is 25% larger than the inner one.

In addition, step 104 includes predicting or defining a lower area of the image that corresponds to a chin portion of the head. The lower area aims at removing the moving body, and is defined to be 0.6d.sub.em below the mouth.

Within the inner ellipse, a "union" or "joining" operation 105 is used: we note all marked pixels in the first mask image and also any unmarked pixels of the first mask image that correspond in location to marked pixels in the second mask image. Between the inner and outer ellipses (except for the lower region), the first mask image is selected (106): we note all marked pixels in the first mask image. In the lower part, we use an "intersection" operation 107: we note any marked pixels in the first mask image that correspond in location to marked pixels in the second mask image.

The above steps result in a final mask image (108) that marks the noted pixels as being part of the head.

Corner Matching and Motion Determination

One popular technique of image registration is optical flow [12, 2], which is based on the assumption that the intensity/color is conserved. This is not the case in our situation: the color of the same physical point appears to be different in images because the illumination changes when the head is moving. We therefore resort to a feature-based approach that is more robust to intensity/color variations. It consists of the following steps: (i) detecting corners in each image; (ii) matching corners between the two images; (iii) detecting false matches based on a robust estimation technique; (iv) determining the head motion; (v) reconstructing matched points in 3D space.

FIG. 5 shows the sequence of operations.

Corner Detection. In a step 110, we use the Plessey corner detector, a well-known technique in computer vision [10]. It locates corners corresponding to high curvature points in the intensity surface if we view an image as a 3D surface with the third dimension being the intensity. Only corners whose pixels are white in the mask image are considered.

Corner Matching. In a step 111, for each corner in the first image we choose an 11.times.11 window centered on it, and compare the window with windows of the same size, centered on the corners in the second image. A zero-mean normalized cross correlation between two windows is computed [7]. If we rearrange the pixels in each window as a vector, the correlation score is equivalent to the cosine angle between two intensity vectors. It ranges from -1, for two windows which are not similar at all, to 1, for two windows which are identical. If the largest correlation score exceeds a prefixed threshold (0.866 in our case), then that corner in the second image is considered to be the match candidate of the corner in the first image. The match candidate is retained as a match if and only if its match candidate in the first image happens to be the corner being considered. This symmetric test reduces many potential matching errors.

False Match Detection. Operation 112 comprises detecting and discarding false matches. The set of matches established so far usually contains false matches because correlation is only a heuristic. The only geometric constraint between two images is the epipolar constraint {tilde over (m)}'.sup.TA'.sup.-TEA.sup.-1{tilde over (m)}=0. If two points are correctly matched, they must satisfy this constraint, which is unknown in our case. Inaccurate location of corners because of intensity variation of lack of string texture features is another source of error. In a step 109, we use the technique described in [35] to detect both false matches and poorly located corners and simultaneously estimate the epipolar geometry (in terms of the essential matrix E). That technique is based on a robust estimation technique known as the least median squares [28], which searches in the parameter space to find the parameters yielding the smallest value for the median of squared residuals computer for the entire data set. Consequently, it is able to detect false matches in as many as 49.9% of the whole set of matches.

Motion Estimation

In a step 113, we compute an initial estimate of the relative head motion is between two images, denoted by rotation R.sub.r and translation t.sub.r. If the image locations of the identified feature points are precise, one could use a five-point algorithm to compute camera motion from Matrix E [7, 34]. Motion (R.sub.r, t.sub.r) is then re-estimated with a nonlinear least-squares technique using all remaining matches after having discarded the false matches [34].

However, the image locations of the feature point are not usually precise. A human typically cannot mark the feature points with high precision. An automatic facial feature detection algorithm may not produce perfect results. When there are errors, a five-point algorithm is not robust even when refined with a well-known bundle adjustment technique.

For each of the five feature points, its 3D coordinates (x, y, z) coordinates need to be determined--fifteen (15) unknowns. Then, motion vector (R.sub.r, t.sub.r) needs to be determined--adding six (6) more unknowns. One unknown quantity is the magnitude, or global scale, which will never be determined from images alone. Thus, the number of unknown quantities that needs to be determined is twenty (i.e., 15+6-1=20). The calculation of so many unknowns further reduces the robustness of the five point-tracking algorithm.

To substantially increase the robustness of the five point algorithm, a new set of parameters is created. These parameters take into consideration physical properties of the feature points. The property of symmetry is used to reduce the number of unknowns. Additionally, reasonable lower and upper bounds are placed on nose height and are represented as inequality constraints. As a result, the algorithm becomes more robust. Using these techniques, the number of unknowns is significantly reduced below 20.

Even though the following algorithm is described with respect to five feature points, it is straightforward to extend the idea to any number of feature points less than or greater than five feature points for improved robustness. Additionally, the algorithm can be applied to other objects besides a face as long as the other objects represent some level of symmetry. Head motion estimation is first described with respect to five feature points. Next, the algorithm is extended to incorporate other image point matches obtained from image registration methods.

Head Motion Estimation from Five Feature Points. FIG. 7 illustrates the new coordinate system used to represent feature points. E.sub.1 202, E.sub.2 204, M.sub.1 206, M.sub.2 20S, and N 210 denote the left eye corner, right eye corner, left mouth corner, right mouth corner, and nose top, respectively. A new point E 212 denotes the midpoint between eye corners E.sub.1, E.sub.2 and a new point M 214 identifies the midpoint between mouth corners M.sub.1, M.sub.2. Notice that human faces exhibit some strong structural properties. For example, the left and right sides of a human face are very close to being symmetrical about the nose. Eye corners and mouth corners are almost coplanar. Based on these symmetrical characteristics, the following reasonable assumptions are made:

(1) A line E.sub.1E.sub.2 connecting the eye corners E.sub.1 and E.sub.2 is parallel to a line M.sub.1M.sub.2 connecting the mouth corners.

(2) A line centered on the nose (e.g., line EOM when viewed straight on or lines NM or NE when viewed from an angle as shown) is perpendicular to mouth line M.sub.1M.sub.2 and to eye line E.sub.1E.sub.2.

Let .pi. be the plane defined by E.sub.1, E.sub.2, M.sub.1 and M.sub.2. Let O 216 denote the projection of point N on plane .pi.. Let .OMEGA..sub.0 denote the coordinate system, which is originated at O with ON as the z-axis, OE as the y-axis; the x-axis is defined according to the right-hand system. In this coordinate system, based on the assumptions mentioned earlier, we can define the coordinates of E.sub.1, E.sub.2, M.sub.1, M.sub.2, N as (-a, b, 0).sup.T, (a, b, 0).sup.T, (-d, -c, 0).sup.T, (d, -c, 0).sup.T, (0, 0, e).sup.T, respectucely

By redefining the coordinate system, the number of parameters used to define five feature points is reduced from nine (9) parameters for generic five points to five (5) parameters for five feature points in this local coordinate system.

Let t denote the coordinates of O under the camera coordinate system, and R the rotation matrix whose three columns are vectors of the three coordinate axis of .OMEGA..sub.0. For each point p.epsilon.{E.sub.1, E.sub.2,M.sub.1, M.sub.2, N}, its coordinate under the camera coordinate system is Rp+t. We call (R, t) the head pose transform. Given two images of the head under two different poses (assume the camera is static), let (R, t) and (R', t') be their head pose transforms. For each point p.sub.i .epsilon.{E.sub.1, E.sub.2,M.sub.1, M.sub.2, N}, if we denote its image point in the first view by m.sub.i and that in the second view by m'.sub.i, we have the following equations: proj(Rp.sub.i+t)=m.sub.i (1) and proj(R'p.sub.i+t')=m'.sub.i (2) where proj is the perspective projection. Notice that we can fix one of the coordinates a, b, c, d, since the scale of the head size cannot be determined from the images. As is well known, each pose has six (6) degrees of freedom. Therefore, the total number of unknowns is sixteen (16), and the total number of equations is 20. If we instead use their 3D coordinates as unknowns as in any typical bundle adjustment algorithms, we would end up with 20 unknowns and have the same number of equations. By using the generic properties of the face structure, the system becomes over-constrained, making the pose determination more robust.

To make the system even more robust, we add an inequality constraint on e. The idea is to force e to be positive and not too large compared to a, b, c, d. In the context of the face, the nose is always out of plane .pi.. In particular, we use the following inequality: 0.ltoreq.e.ltoreq.3a (3) Three (3) is selected as the upper bound of e/a simply because it seems reasonable and it works well. The inequality constraint is finally converted to equality constraint by using a penalty function.

.times..times.<.times..times..ltoreq..ltoreq..times..times..times..time- s..times.>.times. ##EQU00003##

In summary, based on equations (1), (2) and (4), we estimate a, b, ca d, e, (R, t) and (R', t') by minimizing

.times..times..times..function..function.'.function.'.times..times. ##EQU00004## where w.sub.i's and w.sub.n are the weighting factors, reflecting the contribution of each term. In our case, w.sub.i=1 except for the nose term which has a weight of 0.5 because it is usually more difficult to locate the nose top than other feature points. The weight for penalty w.sub.n is set to 10. The objective function (5) is minimized using a Levenberg-Marquardt method [40]. More precisely, as mentioned earlier, we set a to a constant during minimization since the global head size cannot be determined from images.

Incorporating Image Point Matches. If we estimate camera motion using only the five user marked points, the result is sometimes not very accurate because the markers contain human errors. In this section, we describe how to incorporate the image point matches (obtained by any feature matching algorithm) to improve precision.

Let (m.sub.j, m'.sub.j)(j=1 . . . K) be the K point matches, each corresponding to the projections of a 3D point p.sub.j according to the perspective projection (1) and (2). 3D points p.sub.j's are unknown, so they are estimated. Assuming that each image point is extracted with the same accuracy, we can estimate a, b, c, d, e, (R, t), (R', t'), and {p.sub.j} (j=1 . . . K) by minimizing

.times..times..times..times..function.'.function.'.times.' ##EQU00005## where F.sub.5pts is given by (5), and w.sub.p is the weighting factor. We set w.sub.p=1 by assuming that the extracted points have the same accuracy as those of eye corners and mouth corners. The minimization can again be performed using a Levenberg-Marquardt method. This is a quite large minimization problem since we need to estimate 16+3 K unknowns, and therefore it is computationally quite expensive especially for large K. Fortunately, as shown in [37], we can eliminate the 3D points using a first order approximation. The following term .parallel.m.sub.j-proj(Rp.sub.j+t).parallel..sup.2+.parallel.m'.sub.j-pro- j(R'p.sub.j+t').parallel..sup.2 can be shown to be equal, under the first order approximation, to

'.times..times..times..times.'.times..times..times..times..times..times.'.- times..times..times..times..times..times.' ##EQU00006## where

''.times..times. ##EQU00007## and E is the essential matrix to be defined below.

Let (R.sub.r, t.sub.r) be the relative motion between two views. It is easy to see that R.sub.r=R'R.sup.T, and t.sub.r=t'-R'R.sup.Tt. Furthermore, let's define a 3.times.3 antisymmetric matrix [t.sub.r].sub.x such that [t.sub.r].sub.x x=t.sub.r.times.X for any 3D vector x. The essential matrix is then given by E=[t.sub.r].sub.xR.sub.r (7) which describes the epipolar geometry between two views [7].

In summary, the objective function (6) becomes

.times..times..times..times.'.times..times..times..times.'.times..times..t- imes..times..times..times.'.times..times..times..times..times..times.' ##EQU00008##

Notice that this is a much smaller minimization problem. We only need to estimate 16 parameters as in the five-point problem (5), instead of 16+3 K unknowns.

To obtain a good initial estimate, we first use only the five feature points to estimate the head motion by using the algorithm described in Section 2. Thus we have the following two step algorithm:

Step1. Set w.sub.p=0. Solve minimization problem 8.

Step2. Set w.sub.p=1. Use the results of step1 as the initial estimates. Solve minimization problem (8).

Notice that we can apply this idea to the more general cases where the number of feature points is not five. For example, if there are only two eye corners and mouth corners, we'll end up with 14 unknowns and 16+3 K equations. Other symmetric feature points (such as the outside eye corners, nostrils, and the like) can be added into equation 8 in a similar way by using the local coordinate system .OMEGA..sub.0.

Head Motion Estimation Results. In this section, we show some test results to compare the new algorithm with the traditional algorithms. Since there are multiple traditional algorithms, we chose to implement the algorithm as described in [34]. It works by first computing an initial estimate of the head motion from the essential matrix [7], and then re-estimate the motion with a nonlinear least-squares technique.

We have run both the traditional algorithm and the new algorithm on many real examples. We found many cases where the traditional algorithm fails while the new algorithm successfully results in reasonable camera motions. When the traditional algorithm fails, the computed motion is completely bogus, and the 3D reconstructions give meaningless results. But the new algorithm gives a reasonable result. We generate 3D reconstructions based on the estimated motion, and perform Delauney triangulation.

We have also performed experiments on artificially generated data. We arbitrarily select 80 vertices from a 3D face model and project its vertices on two views (the head motion is eight degrees apart). The image size is 640 by 480 pixels. We also project the five 3D feature points (eye corners, nose top, and mouth corners) to generate the image coordinates of the markers. We then add random noises to the coordinates (u, v) of both the image points and the markers. The noises are generated by a pseudo-random generator subject to Gausian distribution with zero mean and variance ranging from 0.4 to 1.2. We add noise to the marker's coordinates as well. The results are plotted in FIG. 3. The blue curve shows the results of the traditional algorithm and the red curve shows the results of our new algorithm. The horizontal axis is the variance of the noise distribution. The vertical axis is the difference between the estimated motion and the actual motion. The translation vector of the estimated motion is scaled so that its magnitude is the same as the actual motion. The difference between two rotations is measured as the Euclidean distance between the two rotational matrices.

We can see that as the noise increases, the error of the traditional algorithm has a sudden jump at certain point. But, the errors of our new algorithm grow much more slowly.

3D Reconstruction. In a step 114, matched points are reconstructed in 3D space with respect to the camera frame at the time when the first base image was taken. Let (m, m') be a couple of matched points, and p be their corresponding point in space. 3D point p is estimated such that .parallel.m-{circumflex over (m)}.parallel..sup.2+.parallel.m'-{circumflex over (m)}'.parallel..sup.2 is minimized, where {circumflex over (m)} and {circumflex over (m)}' are projections of p in both images according to the equation .lamda.{tilde over (m)}=AP.OMEGA.{tilde over (p)}.

3D positions of the markers are determined in the same way.

Fitting a Face Model

This stage of processing creates a 3D model of the face. The face model fitting process consists of two steps: fit