Microsoft Patent | Computing 3d shape parameters for face animation

Patent: Computing 3d shape parameters for face animation

Drawings: Click to check drawins

Publication Number: 20150235372

Publication Date: 20150820

Applicants: Microsoft Technology Licensing

Assignee: Microsoft Technology Licensing

Abstract

A three-dimensional shape parameter computation system and method for computing three-dimensional human head shape parameters from two-dimensional facial feature points. A series of images containing a user's face is captured. Embodiments of the system and method deduce the 3D parameters of the user's head by examining a series of captured images of the user over time and in a variety of head poses and facial expressions, and then computing an average. An energy function is constructed over a batch of frames containing 2D face feature points obtained from the captured images, and the energy function is minimized to solve for the head shape parameters valid for the batch of frames. Head pose parameters and facial expression and animation parameters can vary over each captured image in the batch of frames. In some embodiments this minimization is performed using a modified Gauss-Newton minimization technique using a single iteration.

Claims

1-15. (canceled)

16. A method implemented by a computing device, the method comprising: capturing frames containing a face of a user in a variety of head poses and facial expressions; fitting two-dimensional feature points to the face of the user in the frames using a two-dimensional face alignment technique; determining a desired batch size that dictates a number of the frames to include in a batch of the frames; selecting individual frames to include in the batch of the frames using the desired batch size; constructing an energy function over the batch of the frames; solving the energy function for three-dimensional head shape parameter updates that are valid for the batch of the frames; generating a face model of the face of the user from the three-dimensional head shape parameter updates; and animating the face of the user in accordance with the face model.

17. The method of claim 16, further comprising applying an energy minimization technique to the energy function to solve for the three-dimensional head shape parameter update.

18. The method of claim 16, further comprising: defining a sampling rate that dictates a time separation between the individual frames in the batch of frames; and selecting the frames to include in the batch of frames based on the sampling rate.

19. The method of claim 16, further comprising selecting the individual frames to include in the batch of the frames based on head pose diversity and facial expression diversity.

20. The method of claim 16, further comprising allowing three-dimensional head pose parameters and animation units to vary for the individual frames in the batch of the frames while keeping the three-dimensional head shape parameter updates valid for the batch of the frames.

21. A system comprising: a face tracking system configured to fit two-dimensional feature points to input frames containing a face of a user in a variety of head poses and facial expressions; a two-dimensional feature point information module configured to determine a desired batch size of the input frames and select individual input frames to include in a batch of the input frames based on the desired batch size; a three-dimensional shape parameter update module configured to: construct an energy function over the batch of the input frames, solve the energy function for three-dimensional head shape parameter updates that are valid for the batch of the input frames, and generate a face model of the face of the user from the three-dimensional head shape parameter updates; and a processing device that executes computer-executable instructions associated with the face tracking system, the two-dimensional feature point information module, and the three-dimensional shape parameter update module.

22. The system of claim 21, wherein the three-dimensional shape parameter update module is further configured to provide the three-dimensional head shape parameter updates to the face tracking system.

23. The system of claim 22, wherein the face tracking system is further configured to use the three-dimensional head shape parameter updates in tracking the face of the user in subsequent input frames.

24. The system of claim 21, wherein the two-dimensional feature point information module is further configured to select different input frames to include in a new batch of the input frames that is different than the batch of the input frames.

25. The system of claim 24, wherein the new batch of the input frames is based on the desired batch size.

26. The system of claim 24, wherein the different input frames included in the new batch are captured at a later time than the individual input frames in the batch of the input frames.

27. The system of claim 21, wherein the two-dimensional feature point information module is further configured to determine a criterion for inclusion of the individual input frames in the batch of the input frames and to select the individual input frames based on the criterion.

28. The system of claim 27, wherein the criterion is a difference between individual head poses of the individual input frames.

29. The system of claim 27, wherein the criterion is a temporal separation between the input frames.

30. The system of claim 21, further comprising a camera configured to capture the input frames.

31. A system comprising: a processing device; a storage device storing computer-readable instructions which, when executed by the processing device, cause the processing device to: fit two-dimensional feature points to frames containing a face of a user in a variety of head poses and facial expressions; select individual frames to include in a batch of the frames based on a desired batch size; solve an energy function for three-dimensional head shape parameter updates that are valid for the batch of the frames; and generate a face model of the face of the user from the three-dimensional head shape parameter updates.

32. The system of claim 31, wherein the computer-readable instructions further cause the processing device to track the face of the user in subsequent frames using the face model.

33. The system of claim 31, wherein the computer-readable instructions further cause the processing device to determine the desired batch size.

34. The system of claim 31, wherein the computer-readable instructions further cause the processing device to select the individual frames based on a diversity of the head poses and facial expressions.

35. The system of claim 31, wherein the computer-readable instructions further cause the processing device to select the individual frames based on a temporal separation between the individual frames.

Description

BACKGROUND

[0001] Face tracking techniques are used to find features on a user's face, such as eyes, mouth, nose, and so forth. A camera captures frames containing the face, and the techniques examine the face to find the facial features. With some techniques, various two-dimensional (2D) feature points first are found on the face. Once the 2D feature points have been found, then 3D shape parameters can be found. These 3D shape parameters may include the 3D shape of a user's head, the 3D head pose, and the 3D position of the 2D points observed on the image frame.

[0002] One application of these face tracking techniques is to take the frames containing the user's face and model the facial expressions of the user. In other words, the way in which the user moves his face, such as lifting his eyebrows, smiling, and moving his mouth, is modeled. This modeling involves converting what is seen in the frames captured by the camera into movements of the face. This face model can be used to animate the user's face in a computing environment or deduce the meaning of a user's facial expression.

[0003] One difficulty, however, is that different people have different facial features. For example, some people have larger mouths than others, some have eyes that are far apart, and some have eyes that are close together. If the actual shape of the user's head is not taken into account, then the facial features of the user can easily be misread.

[0004] A 2D face alignment approach typically uses a face tracking system to obtain the 2D feature points from the captured frames. This system fits a model to the user's face to find its feature points. The model includes a base shape (or neutral face) plus a linear combination of deformations that represent head shape variations and facial expressions of the face.

[0005] Typical face tracking systems use a calibration step to compute the base shape and head shape deformation vectors that represent a user's specific head. The process involves asking a user to stare at the camera in certain position while keeping still, and the user is asked to look at the camera with a countenance that is devoid of expression. If the captured image of the user's face has any expression on it, then the user may be asked again to provide an expressionless image of his face. This process can be burdensome to the user.

[0006] One type of 2D face alignment approach is called an active appearance model (AAM). An AMM is a computer vision technique for tracking facial features in two dimensions. The AAM technique matches a statistical model of a shape and appearance of an object to a new image. The AAM is widely used for face recognition and tracking and for medical image interpretation. The AAM technique uses a difference between a current estimate of appearance and a target image to drive an optimization process.

[0007] In order to improve performance, the AAM technique can be constrained by a 3D face and head model. In this situation, the 3D face mask is represented as a linear combination of a neutral mask, face shape deformations and facial features deformations (for example mouth movements). This representation is given mathematically as:

S 3 DMask = S 0 + j = 1 R SU i s i + j = 1 Q AU i a i ( 1 ) ##EQU00001##

where S.sub.0 is a neutral 3D mask, SU.sub.j and S.sub.j are j-th shape unit coefficient (SUs or 3D head shape parameters), AU.sub.j are its corresponding shape deformation basis vector (animation units (AUs) or facial expression parameters)and a.sub.j are j-th animation unit coefficient and its corresponding animation deformation basis vector.

[0008] Equation (1) is a linear combination of the "average" 3D mask for the entire human race and the deformation vectors that are learned statistically from Principal Component Analysis. This is based a theory that any faces can be represented as a linear combination of an average face plus some deformation basis vectors. The term, S.sub.3DMask, represents a particular facial expression for a particular person. It is the sum of the average human face shape plus shape deformations plus animation deformations, expression deformations, or both.

[0009] Shape units (or 3D head shape parameters) and shape basis vectors represent variations in human head shapes. Animation units (or facial expression parameters) and animation basis vectors represent facial movements. Neutral 3D mask, its shape and animation deformation basis vectors are known and constant. They can be manually created by an artist to represent a set of 3D faces, or may be learned statistically from a training set by using algorithms like Principal Component Analysis.

[0010] A 2D to 3D AAM may use a 3D model to constrain energy minimization, produce realistic results for human faces, and to produce 3D tracking parameters (such as 3D head pose, 3D head shape parameters (SUs) and 3D facial expression parameters (AUs). This fitting process determines a set of SUs, AUs and the 3D head pose in addition to the 2D face parameters. Unfortunately, some 3D head shape and animation basis vectors may not be orthogonal and may be correlated with head pose changes.

[0011] For example, moving head up or down (also known as "pitching") may be explained by changing a pitch angle a little bit and moving eyebrows or mouth up or down or it can be explained only by changes in the head pose. This may lead to non-unique and incorrect results when the 2D to 3D AAM computes both the 2D and 3D (SU, AU, head pose) parameters in one combined energy minimization. Incorrectly computed 3D shape parameters are fed back to the AAM, which can contribute to a bad 2D fitting on subsequent video frames.

[0012] This problem can be greatly reduced if the correct 3D head and face shape parameters (SUs and scale) are known beforehand. In this case, the AAM fitting process uses fixed face shape parameters and computes only 2D face parameters, 3D head pose and 3D facial expression parameters.

SUMMARY

[0013] This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

[0014] Embodiments of the 3D shape parameter computation system and method compute updates to 3D head shape parameters from a plurality of 2D feature points fitted to a user's face. The 2D feature points are obtained from a series of images of the user's face captured by a camera and a face tracking system. Embodiments of the system and method can deduce a neutral face of the user from the series of images without the need for an image that actually contains the neutral face of the user. In fact, the more diversity of head poses and facial expressions that the series of images contain the faster the solution will converge. In other words, embodiments of the system and method can deduce the neutral face of the user by looking at a series of captured images of the user over time and in a variety of head poses and facial expressions, and then computing an average in an efficient manner.

[0015] Embodiments of the system and method use a camera (such as a depth-sensing camera) to capture a series of images containing the user's face. This series of images is over time and contains a variety of different head poses and facial expressions of the user. However, in some embodiments the series of images does not contain the user's neutral face. For each image, 2D feature points are fitted to the user's face in the image using a 2D face alignment technique. In some embodiments, this 2D face alignment technique is an active appearance model (AAM). Moreover, in some embodiments the 2D feature points also contain depth information obtained from depth-sensing camera. This depth information may include the distance from the camera to the user's face. In some case this additional information allows the solution to converge faster.

[0016] A desired batch size then is determined for a batch of frames. The batch size dictates how many captured images (or frames) will be included in the batch of frames. In some embodiments the batch size is 10 images, which means that the batch of frames will contain 10 images. A batch of frames then is generated to include a number of captured images set forth by the batch size as well as the sampling rate, image diversity, or both.

[0017] Each captured image in the batch of frames is separated by some temporal distance. In some embodiments, a sampling rate is defined that dictates how far apart in time the captured images are from each other. In some embodiments, the sampling rate is 3 frames per second. This means that adjacent captured images in the batch of frames are temporally separated by 1/3 of a second. In other embodiments, the captured images to include in the batch of frames are selected based on diversity. This may be head pose diversity, facial expression diversity, or both. In this embodiment, if the batch of frames already has the user looking up, down, and right, then it waits until an image is obtained that has the user looking left to include in the batch of frames. Similarly, if the batch of frames already has the user looking surprised, angry, and sad, then it may wait until an image is obtained of the user looking happy to include in the batch of frames.

[0018] An energy function is constructed over a batch of frames and then minimized to solve for the 3D shape parameter updates. The 3D head shape parameters are common or valid for the entire batch of frames and represent the shape of a particular tracked user and each of the images contained therein. On the other hand, the 2D feature points, 3D head pose parameters, and the 3D facial expression parameters (AUs) are allowed to vary for each image in the batch of frame. The energy function is constructed over the batch of frames and includes the unknown 3D head shape parameters, the 2D feature points, the 3D head pose parameters, and the 3D facial expression parameters. Moreover, the energy function is based on the squared difference between 2D feature points and a projected (to a camera plane) 3D head model, after it is transformed by a 3D head pose, 3D head shape deformations and facial expression deformations.

[0019] The energy function is minimized to solve for the 3D shape parameters updates for the batch of frames. The 3D shape parameter updates found are valid for the entire batch of frames, not just a single image in the batch. In addition, the facial expression parameters and 3D head pose parameters are found for each image in the batch of frames. The energy function of the batch of frames produces a system of equations that is solved using an energy minimization technique. In some embodiments, when the batch size is 10, each batch of frames produces a matrix containing about 100.times.100 elements.

[0020] In some embodiments this minimization is performed using a least square minimization technique, such as a modified Gauss-Newton minimization technique. The modified Gauss-Newton performs a single iteration of the minimization technique to obtain the 3D shape parameter updates. This is done since the energy function in this case is convex and so one step of Gauss-Newton nearly finds its minimum. This allows the 3D head shape parameters to be updated in real time. After the 3D head shape parameter updates are computed from the energy minimization, the current 3D head shape parameters are updated by adding the computed updates to them.

[0021] Once the 3D head shape parameters are found from the compute update for the batch of frames, a subsequent batch of frames is generated and the updates for 3D head shape parameters for that subsequent batch of frames is computed. Images in a subsequent batch of frames contains are later in time that image in the previous batch of frames. Current 3D head shape parameters are updated by mixing them together with new 3D head shape parameters. In other words, embodiments of the system and method compute a shape parameter difference (or computed update), and the new 3D head shape parameters are obtained by mixing the old 3D head shape parameters plus the shape parameter difference. Thus, for each batch of frames a system of equations is solved, and the energy minimization gives updates of the 3D head shape parameters for the particular batch of frames.

[0022] In some embodiments this process of generating new batches of frames and minimizing an energy function to solve for updates to the associated 3D head shape parameters continues until a point is reached where the head pose and the facial expression parameters are changing for each frame, but the 3D head shape parameters are constant. In other embodiments, the process continues until a threshold is reached in the shape parameter difference. In still other embodiments, the process continues until embodiments of the system and method are terminated. Moreover, each time the 3D head shape parameters are updated they are provided to the face tracking system to provide improvements in the tracking of the user's face. Thus, the model of the user's face as well as the face tracking of the user's face improves over time.

[0023] It should be noted that alternative embodiments are possible, and steps and elements discussed herein may be changed, added, or eliminated, depending on the particular embodiment. These alternative embodiments include alternative steps and alternative elements that may be used, and structural changes that may be made, without departing from the scope of the invention.

DRAWINGS DESCRIPTION

[0024] Referring now to the drawings in which like reference numbers represent corresponding parts throughout:

[0025] FIG. 1 is a block diagram illustrating a general overview of embodiments of the 3D shape parameter computation system and method implemented in a computing environment.

[0026] FIG. 2 is a flow diagram illustrating the general operation of embodiments of the 3D shape parameter computation system and method shown in FIG. 1.

[0027] FIG. 3 is a flow diagram illustrating the operational details of embodiments of the 3D shape parameter update module shown in FIG. 1.

[0028] FIG. 4 illustrates a simplified example of a general-purpose computer system on which various embodiments and elements of the 3D shape parameter computation system and method, as described herein and shown in FIGS. 1-3, may be implemented.

DETAILED DESCRIPTION

[0029] In the following description of embodiments of a 3D shape parameter computation system and method reference is made to the accompanying drawings, which form a part thereof, and in which is shown by way of illustration a specific example whereby embodiments of the 3D shape parameter computation system and method may be practiced. It is to be understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the claimed subject matter.

I. System Overview

[0030] Embodiments of the 3D shape parameter computation system and method compute update to 3D head shape parameters from 2D feature points obtained from images captured over a period of time. The dimension of the problem is lowered from 3D to 2D because 2D feature points are used instead of image pixels. This means there are fewer data points to work with, as image pixels are more numerous. This reduces the computational complexity considerably and allows the 3D head shape parameter updates to be computed in real time.

[0031] FIG. 1 is a block diagram illustrating a general overview of embodiments of the 3D shape parameter computation system 100 and method implemented in a computing environment. In particular, embodiments of the 3D shape parameter computation system 100 and method are shown implemented on a computing device 105. The computing device 105 may be virtually any device that contains a processor, such as a desktop computer, notebook computer, and mobile phone.

[0032] Embodiments of the 3D shape parameter computation system 100 and method capture a user's face 110 using a camera 115 to obtain an input frame 120 containing the user's face 110. In some embodiments the camera 115 is a depth-sensing camera. A face tracking system 120 (which includes a 2D face alignment technique) is run over the input frame 120 to produce 2D feature points for the input frame 130.

[0033] A determination then is made as to whether to include the input frame 120 in the 3D head shape computation 135. As explained below, this determination may be based on a numbers of criteria. If not, then a new frame is obtained 140 and the process is run again over the new frame. Otherwise, embodiments of a 2D feature point information module 145 process the input frame 120. This processing by embodiments of the 2D feature point information module 145 adds information from the input frame to corresponding matrices. The information from each input frame 120 is added to the matrices by embodiments of the 2D feature point information module 145.

[0034] A determination then is made as to whether enough frames have been collected 150 to generate a batch of frames 155. If not, then a new frame is obtained 140 and the process is run again over the new frame. Otherwise, there are enough frames to generate the batch of frames 155. This batch of frame is processed by a 3D shape parameter update module 160 to obtain the 3D head shape parameter update. This update is used to obtain updated 3D head shape parameters 165 for the batch of frames. This process is repeated such that new input frames are selected for inclusion in a new batch of frames that is different from the previous batch of frames. Moreover, periodically the updated 3D head shape parameters are sent to the face tracking system 125 to aid in the tracking of the user's face 110.

II. Operational Overview

[0035] FIG. 2 is a flow diagram illustrating the general operation of embodiments of the 3D shape parameter computation system 100 and method shown in FIG. 1. As shown in FIG. 2, the operation of embodiments of the 3D shape parameter computation method begins by capturing an input frame 120 containing a user's face 110 (box 200). Over time, the input frames include the user's face in different head poses and having different facial expressions. However, the input frame 120 does not include a neutral face of the user (or a neutral facial expression of the user). This is because embodiments of the 3D shape parameter computation system 100 and method do not require the user to provide a neutral image, and in fact converge faster to the 3D shape parameters when a variety of expressions of the user's face 110 are contained in the captured images.

[0036] For each input frame 120, embodiments of the 3D shape parameter computation system 100 and method assume that the image is mapped to a 3D face model of the user's face. This 3D face model is described in detail below. Embodiments of the system 100 and method attempt to find the most likely neutral face of the user by doing the computation of not just a single input frame 120, but a set of images taken together (called a batch a frames 155). For the batch of frames 155, embodiments of the system 100 and method find updates to the 3D head shape parameters that explain the shape of the user's face 110.

[0037] Next, embodiments of the 3D shape parameter computation system 100 and method find 2D feature points fitted to the user's face 110 for the input frame 120 (box 205). This is done using a 2D face alignment technique, such as the AAM. The 2D feature points are computed based on image information for each of the input frames in a batch of frames. As explained in detail below, these 2D feature points are used to compute updates for the 3D head shape parameters. This can be done in real time.

[0038] A desired batch size dictates the number of (or how many) input frames (or captured images) will be included in each of the batches of frames (box 210). In some embodiments, the batch size is 10, such that 10 captured images are used in each batch of frames. These 10 captured images not sequentially but have some temporal distance between them, so as to provide greater probability that they contain different head poses. The more variety that is contained in the captured images, the faster the computation of updates for the 3D head shape parameters will converge. The temporal distance between each of the captured images is called the sampling rate.

[0039] Embodiments of the system 100 and method also select at least one criterion for inclusion of an input frame in the batch of frames 155 (box 215). This criterion includes using different head poses, or whether there is a good face alignment. Moreover, often it is desirable to have a good temporal separation between captured images so that the images will contain the user's face in a variety of head poses (such as looking up, down, left, and right) and facial expressions. In some embodiments the sampling rate is 3 frames every second, or one-third of a second apart. In some embodiments, this criterion is based on diversity. In other words, images are selected so as to maximize the diversity of head poses and facial expressions that are contained in the batch of frames 155.

[0040] Next, a determination is made as to whether to include the input frame 120 in the 3D head shape computation based on the criteria (box 220). Information obtained from the 2D feature points for the input frame 130 is added to corresponding matrices (box 225). As explained in detail below, these matrices may include Hessian matrices and steepest descent matrices (or an information vector).

[0041] Next, a determination is made as to whether enough frames have been collected to produce the batch of frames 155 (box 230). This determination is based on the batch size. If not, then embodiments of the system 100 and method select another frame (box 235). This means that a new input frame is selected that is later in time from the previous input frame. If enough frames have been collected to produce the batch of frames 155, then the 3D head shape parameter update is computed from the corresponding matrices described above (box 240). An updated 3D head shape parameter is obtained and provided to the face tracking system 125 in order to aid in the tracking of the user's face (box 245).

[0042] Embodiments of the 3D shape parameter computation system 100 and method continue this process using new batches of frames. This means that a new batch of frames is generated containing different input frames that are later in time than the previous batch of frames. A 3D head shape parameter update that is common to or valid for this new batch of frames is computed and used to update the shape parameters. This process continues until either a threshold difference in the 3D head shape parameter updates is met, or until the embodiments of the system 100 and method are terminated. Each time the 3D head shape parameters are updated, they are provided to the face tracking system 125 to provide improvements in the tracking of the user's face 110.

[0043] In some embodiments, when the batch size is 10, each batch of frames produces a matrix containing about 100.times.100 elements. Embodiments of the system 100 and method solve this system of equations using a least squares minimization technique to find the 3D head shape parameter update that is common or valid for the 10 frames. Then the current 3D head shape parameters are obtained by adding them to old 3D head shape parameters to obtain new 3D head shape parameters. More specifically, embodiments of the system 100 and method compute a 3D head shape parameter update, and the new 3D head shape parameters are obtained by adding the old 3D head shape parameters plus the update.

[0044] For each batch of frames, a system of equations is solved, and the energy minimization gives the 3D head shape parameter update for the batch of frames 155. In some embodiments, this process is continued until the 3D head shape parameter update drops below some threshold. In other embodiments, the process continues in case something changes and new information is obtained that was not seen previously. Embodiments of the system 100 and method then process the next batch of frames. These updates then are mixed with the current 3D head shape parameters to obtained updated 3D head shape parameters. Each time the 3D shape parameters are updated a new 3D shape of the user's face is computed. This updated 3D face shape is used by the face tracking system 120. This means the face tracking improves over time.

III. Operational Details

[0045] The operational details of embodiments of the 3D shape parameter computation system 100 and method will now be discussed. This includes the operation of embodiments of the 3D shape parameter update module 160. Moreover, the mathematical details of embodiments of the 3D shape parameter update module 160 will be presented.

IIIA. 3D Face Model Having a Set of Vertices and Triangles

[0046] Embodiments of the 3D shape parameter computation system 100 and method use a face model to represent the user's face. This face model can be used in face animation, where the user's face and expressions from the user's face are animated on a computer. Embodiments of the system and method represent a face by a polygonal surface. This can be done because of the real-time efficiency of modern graphics hardware. The polygonal surface is typically formed from a triangular mesh. The user's face then is determined by the 3D coordinates of the vertices of the triangles, which can be obtained by using 3D digitizers, laser scanners, or computer vision techniques.

[0047] If the coordinates of the vertices are treated as free parameters, meaning that they can be any values, then the number of unknowns is quite large. This makes face modeling difficult (because of the large amount of data that is handled). This difficultly in face modeling can render the face animation intractable.

[0048] One way around this problem is to notice that in a general sense most human faces look similar to each other. For example, most human faces contain two eyes above a nose, with a mouth below the nose. Using this concept, it can be seen that the number of degrees of freedom needed to define a wide range of faces is limited. Limiting the values that the coordinates of the vertices can take makes the face modeling problem solvable.

[0049] One way to represent a user's face is as a linear combination of a neutral (or "average") face and some number of face deformations. The average face is an average face for a human race without any expressions. In this context, a face metric is a vector that linearly deforms the neutral face in a certain way. A first face metric can be used to change the shape of the user's head and some facial parts. Such a metric is called a "shape unit," (or "SU" or 3D head shape parameter). For example, the SUs can be used to make the head wider, longer, or make the nose bigger. A second face metric can be used to describe facial expressions like a smile, frown, anger, or surprise. Such a metric is called an "animation unit," (or "AU" or facial expression parameter).

III.B. 3D Head Shape Parameter Update Module

[0050] The 3D shape parameter computation system 100 and method collects 2D facial feature points for M number of input frames. Embodiments of the system 100 and method then use the 3D shape parameter update module 160 to minimize an energy function obtained from parameters from the batch of frames. The energy function uses one common set of 3D head shape parameters for all frames and allows different 3D head poses and animation sets for each frame.

[0051] The energy minimization process produces an update to a set of 3D head shape parameters that explains the face shape on all captured images in a particular batch of frames. In some embodiments of the 3D shape parameter update module 160, the energy minimization is performed using a single iteration of the Gauss-Newton algorithm. As explained in detail below, this single iteration generally yields the minima. At this point the function is mostly well shaped and convex. Then embodiments of the module 160 generate a new batch of frames and repeat these process actions. The new batch of frames may contain previously unseen poses, which may improve the 3D head shape parameters. Embodiments of the module 160 converge to an update to a set of 3D head shape parameters that can explain the face after processing one or more batches of frames.

[0052] FIG. 3 is a flow diagram illustrating the operational details of embodiments of the 3D shape parameter update module 160 shown in FIG. 1. The operation begins by inputting the 2D feature points for each frame in a batch of frames (box 300). In particular, embodiments of the 3D shape parameter update module 160 collect 2D feature points for M number of captured images.

[0053] Next, the module 140 generates an energy function over the batch of frames (box 310). This energy function includes 3D shape parameters for the batch of frames, the 2D feature points for each of the input frame in the batch of frames, and the 3D head pose parameters The energy function also includes a difference between 2D points and projected 3D model points (projected to the camera plane), head shape deformations, and facial expression deformations.

[0054] Using the energy function, the module 160 finds a 3D head shape parameter update that is common to the corresponding batch of frames and that can explain the shape of the user's head in each of the frames in the batch of frames. The 3D head pose parameters and the facial expression deformations can vary for each of the frames in the batch of frame (box 320). Thus, there are 3D head pose parameters and AU (or facial expression parameters) for each frame in the batch of frames. However, there is only one 3D head shape parameter update associated with the batch of frames.

[0055] The energy function then is minimized to solve for the 3D head shape parameter update for the batch of frames (box 330). Moreover, as explained below, a Hessian matrix and an information vector are constructed using the 2D feature points for each frame to solve for the 3D head shape parameter update (box 340).

[0056] Mathematically, the following energy function is minimized:

E = k = 1 M i = 1 N ( S i 2 D ( k ) - Proj ( S i 3 D ( R ( k ) , T ( k ) , AU ( k ) , SU ) ) 2 + w 1 k = 1 M ( depthZ ( k ) - T z ( k ) ) 2 + w 2 k = 1 M ( AU ( k ) ) 2 + w 3 k = 1 M ( SU old - SU ) 2 ( 2 ) ##EQU00002##

[0057] where:

[0058] k=1 . . . M--a number of a captured image (or frame number);

[0059] i=1 . . . N--a point index;

[0060] S.sub.i.sup.2D(k)--i-th point of a 2D shape computed for frame k by the 2D face alignment module 130;

[0061] S.sub.i.sup.3D(k)--i-th point of a 3D mask in camera space computed for captured image k;

[0062] R(k)=[.theta..sub.x, .theta..sub.y, .theta..sub.z].sup.T--3D rotation angles around X, Y, Z computed for captured image k;

[0063] T(k)--[T.sub.x, T.sub.y, T.sub.z].sup.T--3D translation in X, Y, Z computed for captured image k;

[0064] AU(k)=[AU.sub.1, AU.sub.2, . . . , AU.sub.Q].sup.T--Q animation units computed for captured image k;

[0065] SU=[s, SU.sub.1, SU.sub.2, . . . , SU.sub.R].sup.T--a vector of 3D scale (s parameter) and R shape units (SUs) common for all M captured images in this energy function. This vector describes the facial shape in 3D;

[0066] depthZ(k)--distance to the tracked face for captured image k provided by a depth sensing camera; and

[0067] w.sub.1, w.sub.2, w.sub.3--weights of corresponding constraints.

[0068] In Equation (2), E represents the energy function that embodiments of the 3D shape parameter update module 160 are trying to minimize in order to find the SUs (or 3D head shape parameters). This energy function is formed over a batch of frames. In some embodiments, the batch of frames contains 10 frames (or images) containing the captured face of the user 110. The energy function in Equation (2) computes SUs that are common for each of the captured images in the batch of frames. It also minimizes and finds expressions for each captured image separately, such as the Aus (or facial expression parameters), which are different for each input frame.

[0069] Referring to Equation (2), the first term of the energy function is the 2D feature points minus the projected 3D shape of the user's face. The second, third, and fourth terms include the weights, which are constraints that make the solution stable. The first weight, w.sub.1, says that the distance to the face is close to what is observed from the depth-sensing camera. The second weight, w.sub.2, adds stability to the solution. The third weight, w.sub.3, constrains the solution such that the newly-computed shape will not be far from the old computed shape. This also adds stability to the solution.

[0070] In the first (or main) term of the energy function in Equation (2), the projected 3D shape is a perspective projection. Embodiments of the 3D shape parameter update module 160 project a 3D shape, which is defined in Equation (1), and add 3D rotation, 3D translation, and the SUs and AUs. Generally speaking, it is the user's face 110 placed in a camera space.

[0071] In addition, embodiments of the 3D shape parameter update module 160 compute the 3D position of the face and rotation. In other words, it computes rotation, translation, and the scale of the user's face relative to the 3D face model. In terms of the 3D face model described above, it computes the movement of the set of vertices and triangles for the user's face 110 that are represented by the SUs and AUs.

[0072] Moreover,

S i 3 D ( k ) - sR ( k ) ( S 0 i + j = 1 R SU j S ij + j = 1 Q .LAMBDA. U j ( k ) .LAMBDA. ij ) + T ( 3 ) ##EQU00003##

is a vertex of a 3D face mask in camera space, where:

[0073] R(k) is a rotation matrix computed for captured image k;

[0074] T(k) is a translation vector for captured image k;

[0075] s is scale common for all M captured images;

[0076] S.sub.0 is a constant neutral 3D mask; and

[0077] S.sub.ij, A.sub.ij are constant shape and animation parameter vectors for i-th vertice of the 3D mask that correspond to j-th SU or AU values.

[0078] Equation (3) explains more in detail how embodiments of the 3D shape parameter update module 160 compute each point of the 3D shape and obtain vertices for the 3D face shape of the user. Generally, embodiments of the module 160 are given the scale and then multiply the scale by rotation. This 3D shape is transformed in model space, and then translation is added. Equation (3) makes clear how the vertices of the 3D shape are transformed. The 3D mask defined in the model space is deformed, rotated, and translated into world space so that it fits the user's face that was observed from the 2D image contained in a frame. This transformation from model space to camera space yields the vertices of the face model.

[0079] In addition,

Proj ( x , y , z ) = { fx z + frame width 2 , - fy z + frame height 2 , ( 4 ) , ##EQU00004##

is the perspective projection function that was used in Equation (2).

[0080] Note that the energy function as set forth in Equation (2) includes the following: [0081] 1. a main term responsible for fitting 3D head pose parameters, animation units, scale and shape units based on observed 2D points computed by the 2D face alignment module 130; [0082] 2. a depth constraint that is responsible for limiting T.sub.z to be as close as possible to the camera's distance to the tracked users' face 110; [0083] 3. an AU change minimization constraint that forces the optimization process to use mostly SUs and scale to explain a set of 2D points with 3D mask; and [0084] 4. a Tikhonov regularization constraint that makes this nonlinear optimization numerically stable and minimizes changes in SUs and scale values. This constraint adds stability by "smoothing" SU and scale updates.

[0085] The energy function of Equation (2) is minimized over a block of M captured images to compute the shape parameter difference, .DELTA.SU, or updates to the common scale and SUs for those captured frames. The 3D pose parameters and AU values are allowed to vary for each captured image in the energy function. Once the shape parameter difference, .DELTA.SU, is known, embodiments of the module 160 incorporate them into the previously known scale and SU parameters. Mathematically, this can be written as follows:

SU.sub.new=SU.sub.old+.mu..DELTA.SU (5)

where .mu. is an update weight that takes values in 0 . . . 1 range. In some embodiments this value is set to be 1.0.

[0086] Equation (5) set forth how embodiments of the 3D shape parameter update module 160 mix updates of SUs with the previous (or old) SUs. The .mu. in Equation (5) is used if it is desired to slow down the computation. If the computation is slowed down, it means that it will not converge as fast. The .mu. term dictates what percentage of the shape parameter difference is actually applied. Embodiments of the 3D shape parameter update module 160 converges the quickest when the user is moving their head in different head poses. One time when it may be desirable to slow down the computation is when the user is looking at the same point for a long time and not changing head pose.

[0087] The energy function of Equation (2) can be rewritten in the matrix form a vector of parameters is introduced that contains all optimized parameters, p=[R(1), T(1), AU(1), . . . , R(M), T(M), AU(M), s, SU].sup.T, where M is a number of captured images in the batch of frames over which energy minimization is performed. The R(k), T(k), AU(k), and SU are parameter vectors as defined above.

[0088] Therefore the energy function of Equation (3) in matrix form can be defined as:

E-.parallel.S.sub.2D-Proj(S.sub.3D(p)).mu..sub.2.sup.2+w.sub.1.parallel.- depthZ-I.sub.zp.parallel..sub.2.sup.2+w.sub.2.parallel.I.sub.AUp.parallel.- .sub.2.sup.2+w.sub.3.parallel.SU.sub.old-I.sub.SUp.parallel..sub.2.sup.2 (6),

[0089] Where:

[0090] .parallel..parallel..sub.2.sup.2--is squared L2 norm;

[0091] p--is a vector of optimized parameters of size (6+Q).times.M+1+R;

[0092] S.sub.2D--is a vector with 2.times.N.times.M elements that are 2D point coordinates produced by the 2D face alignment module 130 for all M captured images, x,y coordinates stacked in one column as [x.sub.1, y.sub.1, . . . , x.sub.2NM, y.sub.2MN].sup.T;

[0093] S.sub.3D(p)--is a vector with 3.times.N.times.M elements that are 3D point coordinates. These points depend on parameters from p, x, y, z coordinates stacked in one column as [x.sub.1, y.sub.1, z.sub.1, . . . , x.sub.2MN, y.sub.2MN, z.sub.2MN].sup.T;

[0094] Proj(S.sub.3D)--is a projection vector function that projects S.sub.3D(p) vector to 2D. Using Equation (3), this function is defined as:

Proj ( S 3 D ) = [ Proj ( S 1 3 D ( 1 ) ) Proj ( S N 3 D ( 1 ) ) Proj ( S 1 3 D ( 2 ) ) Proj ( S N 3 D ( 2 ) ) Proj ( S 1 3 D ( M ) ) Proj ( S N 3 D ( M ) ) ] ( 7 ) ##EQU00005##

[0095] Equation (7) is the projection in matrix form, and the vector functions in vector form.

[0096] depthZ--is a vector of the same size as p with all entries set to 0 except for the entries which indexes correspond to the position of Tz in p. Those entries are set to be distances to the tracked head for corresponding captured images, as measured by a depth-sensing camera.

[0097] SU.sub.old--is a vector of the same size as p with all entries set to 0 except for SU and scale part. Those entries are set to be currently known scale and SUs I.sub.E, I.sub.AU, I.sub.SU--are square matrices with number of columns and rows to be the same as the dimension of the vector of parameters p and with all entries set to 0 except for the entries on the main diagonals which indexes correspond to indexes of T.sub.z, AU, SU (includes scale) parameters in p. Those entries are set to 1.

[0098] Embodiments of the 3D shape parameter update module 160 use a modified Gauss-Newton method to minimize the energy function given in Equation (6) and to compute 3D head shape parameter updates. To do that, embodiments of the 3D shape parameter update module 160 take its 1.sup.st order Taylor expansion around point p.sub.start as follows:

E = S 2 D - Proj ( S 3 D ( p start ) ) - Proj ( S 3 D ( p ) ) p .DELTA. p 2 2 + w 1 depthZ - I z p start - I z .DELTA. p 2 2 + w 2 I AU p start + I AU .DELTA. p 2 2 + w 3 I SU .DELTA. p 2 2 , ( 8 ) ##EQU00006##

where p.sub.start vector's elements R(k), T(k), AU(k) are set to be R, T, AU parameters input frame k and scale and SU elements are set to currently known scale and SU values (SU.sub.old in Equation (5)).

[0099] The energy function given by Equation (8) can be reformulated with residuals as follows:

E = Err 2 D - Proj ( S 3 D ( p ) ) p .DELTA. p 2 2 + w 1 ErrZ - I z .DELTA. p 2 2 + w 2 I AU p start + I AU .DELTA. p 2 2 + w 3 I SU .DELTA. p 2 2 ( 9 ) ##EQU00007##

where the derivative with regard to p in the 1.sup.st term is equal to:

Proj ( S 3 D ( p ) ) p = .differential. Proj ( S 3 D ) .differential. S 3 D .differential. S 3 D .differential. p . ( 10 ) ##EQU00008##

[0100] The 1.sup.st partial derivative has this form:

.differential. Proj ( S 3 D ) .differential. S 3 D = [ .differential. Proj ( S 3 D ) .differential. S 1 3 D ( 1 ) , , .differential. Proj ( S 3 D ) .differential. S N 3 D ( 1 ) , , .differential. Proj ( S 3 D ) .differential. S 1 3 D ( M ) , , .differential. Proj ( S 3 D ) .differential. S N 3 D ( M ) ] ( 11 ) ##EQU00009##

Considering the definition of Proj( ) vector function as in Equation (7), embodiments of the 3D shape parameter computation method obtains the following block matrix as

.differential. Proj ( S 3 D ) .differential. S 3 D : .differential. Proj ( S 3 D ) .differential. S 3 D = [ .differential. Proj ( .differential. S 1 3 D ( 1 ) ) .differential. S 1 3 D ( 1 ) 0 0 .differential. Proj ( .differential. S N 3 D ( M ) ) .differential. S N 3 D ( M ) ] ( 12 ) ##EQU00010##

where there are

2 .times. 3 .differential. Proj ( .differential. S i 3 D ( k ) ) .differential. S j 3 D ( k ) ##EQU00011##

matrices on the main diagonal and all other elements are set to 0. Considering the definition of the perspective projection given in Equation (4), the diagonal 2.times.3 matrices are:

.differential. Proj ( .differential. S i 3 D ( k ) ) .differential. S j 3 D ( k ) = [ f z 0 - fx z 2 0 - f z fy z 2 ] . ( 13 ) ##EQU00012##

[0101] The 2.sup.nd partial derivative has this form (each element is gradient vector):

.differential. S 3 D .differential. p = [ .differential. S 3 D .differential. .LAMBDA. U ( 1 ) , .differential. S 3 D .differential. .LAMBDA. U ( 2 ) , , .differential. S 3 D .differential. .LAMBDA. U ( M ) , .differential. S 3 D .differential. SU ] . ( 14 ) ##EQU00013##

[0102] In matrix form, Equation (14) becomes:

.differential. S 3 D .differential. p = [ .differential. S 3 D ( 1 ) .differential. AU ( 1 ) 0 0 .differential. S 3 D ( 1 ) .differential. SU ( 1 ) 0 .differential. S 3 D ( 2 ) .differential. .LAMBDA. U ( 2 ) 0 0 .differential. S 3 D ( 2 ) .differential. SU ( 2 ) 0 0 0 0 .differential. S 3 D ( M ) .differential. AU ( M ) .differential. S 3 D ( M ) .differential. SU ( M ) 0 0 0 ] ( 15 ) ##EQU00014##

where its block matrices are:

.differential. S 3 D ( k ) .differential. AU ( k ) = [ .differential. S 1 3 D ( k ) .differential. .theta. x ( k ) .differential. S 1 3 D ( k ) .differential. AU Q ( k ) .differential. S N 3 D ( k ) .differential. .theta. x ( k ) .differential. S N 3 D ( k ) .differential. AU Q ( k ) ] .differential. S 3 D ( k ) .differential. SU ( k ) = [ .differential. S 1 3 D ( k ) .differential. s ( k ) .differential. S 1 3 D ( k ) .differential. SU R ( k ) .differential. S N 3 D ( k ) .differential. s ( k ) .differential. S N 3 D ( k ) .differential. SU R ( k ) ] ( 16 ) ##EQU00015##

with their elements defined by taking partial derivatives of Equation (3) as:

.differential. S i 3 D ( k ) .differential. .theta. x ( k ) = s .differential. R .differential. .theta. x S i model ( k ) ; .differential. S i 3 D ( k ) .differential. .theta. y ( k ) = s .differential. R .differential. .theta. y S i model ( k ) ; .differential. S i 3 D ( k ) .differential. .theta. z ( k ) = s .differential. R .differential. .theta. z S i model ( k ) ( 17 ) .differential. S i 3 D ( k ) .differential. T x ( k ) = [ 100 ] T ; .differential. S i 3 D ( k ) .differential. T y ( k ) = [ 010 ] T ; .differential. S i 3 D ( k ) .differential. T z ( k ) = [ 001 ] T ( 18 ) .differential. S i 3 D ( k ) .differential. AU j ( k ) = sR ( k ) A ij ; .differential. S i 3 D ( k ) .differential. s = RS i model ( k ) ; .differential. S i 3 D ( k ) .differential. SU j = sR ( k ) S ij ( 19 ) ##EQU00016##

[0103] where:

[0104] S.sub.i.sup.model(k)--is i-th point of the 3D mask in the model space (before rotation, translation and scale).

.differential. R .differential. .theta. x , .differential. R .differential. .theta. y , .differential. R .differential. .theta. z ##EQU00017##

--derivatives of the rotation matrix with regard to Euler angles and can be trivially derived from the Euler rotation matrix;

[0105] A.sub.ij,S.sub.ij--are the j-th animation and shape deformation basis vector and shape deformation basis vector for i-th vertice (they consists of X, Y, Z components)

[0106] The derivative of Equation (10) can be now written as a block matrix with 2.times.N.times.M rows (number of 2D point coordinates) and (6+Q).times.M+1+R columns (number of estimated parameters), as:

SD = Proj ( S 3 D ( p ) ) p = [ SD RTAU ( 1 ) 0 0 0 SD SU ( 1 ) 0 SD RTAU ( 2 ) 0 SD SU ( 2 ) 0 0 0 0 SD RTAU ( M ) SD SU ( M ) ] where : ( 20 ) SD RTAU ( k ) = .differential. Proj ( .differential. S 3 D ( k ) ) .differential. S 3 D ( k ) .differential. S 3 D ( k ) .differential. AU ( k ) ; SD SU ( k ) = .differential. Proj ( .differential. S 3 D ( k ) ) .differential. S 3 D ( k ) .differential. S 3 D ( k ) .differential. SU ( k ) ; ( 21 ) ##EQU00018##

[0107] Here the projection matrix derivatives are block diagonal (see Equation (12)) with 2.times.N rows and 3.times.N columns. 3D shape derivatives have 3.times.N rows and either 6+Q columns (with regard to RTAU parameters) or 1+R columns (with regard to SU parameters).

[0108] The energy function given by Equation (9) can now be reformulated as follows:

E=.parallel.Err2D-SD.DELTA.p.parallel..sub.2.sup.2+w.sub.1.parallel.ErrZ- -I.sub.z.DELTA.p.parallel..sub.2.sup.2+w.sub.2.parallel.I.sub.AUp.sub.star- t+I.sub.AU.DELTA.p.parallel..sub.2.sup.2+w.sub.3.parallel.I.sub.SU.DELTA.p- .parallel..sub.2.sup.2 (22)

[0109] In order to minimize this energy, embodiments of the 3D shape parameter update module 160 take its derivative with regard to .DELTA.p, set it equal to zero, and then solve for .DELTA.p. This yields the following (assuming that a L2 norm is used):

E p = - 2 SD T ( Err 2 D - SD .DELTA. p ) - 2 w 1 I z T ( Err Z - I z .DELTA. p ) + 2 w 2 I AU T ( I AU p start + I AU .DELTA. p ) + 2 w 3 I SU T I SU .DELTA. p = 0 ( 23 ) ##EQU00019##

[0110] Considering that I.sub.z.sup.TI.sub.z=I.sub.z, I.sub.AU.sup.TI.sub.AU=I.sub.AU, I.sub.SU.sup.TI.sub.SU=I.sub.SU, this can be simplified to:

(SD.sup.TSD+w.sub.1I.sub.z+w.sub.2I.sub.AU+w.sub.3I.sub.SU).DELTA.p=SD.s- up.TErr2D+w.sub.1I.sub.z.sup.TErrZ-w.sub.2I.sub.AUp.sub.start (24)

[0111] Or, in another form:

.DELTA.p=H.sup.-1SDErr (25),

where H is a Hessian and SDErr is a steepest descent matrix defined as:

H=SD.sup.TSD+w.sub.1I.sub.z+w.sub.2I.sub.AU+w.sub.3I.sub.SU (26)

SDErr=SD.sup.TErr2D+w.sub.1I.sub.z.sup.TErrZ-w.sub.2I.sub.AUp.sub.start (27).

[0112] Equation (25) is how embodiments of the 3D shape parameter computation method obtain the update of SU (or .DELTA.p) from the matrix in Equation (20) (SD). Equation (26) is the Hessian that is formed that is the SD transpose matrix multiplied by itself, plus the constraints in the energy function.

[0113] Note that in Equations (25) and (26) the Hessian is used. In mathematics, the Hessian matrix (or Hessian) is the square matrix of second-order partial derivatives of a function. In other words, the Hessian describes the local curvature of a function of many variables.

[0114] Note that the SD is defined by Equation (20). SD.sup.TSD--is a symmetric sparse and mostly diagonal matrix. It should be noted that:

SD T SD = [ SD RTAU ( 1 ) T SD RTAU ( 1 ) 0 0 0 SD RTAU ( 1 ) T SD SU ( 1 ) 0 SD RTAU ( 2 ) T SD RTAU ( 2 ) 0 SD RTAU ( 2 ) T SD SU ( 2 ) 0 0 0 0 SD RTAU ( M ) T SD RTAU ( M ) SD RTAU ( M ) T SD SU ( M ) SD SU ( 1 ) T SD RTAU ( 1 ) SD SU ( 2 ) T SD RTAU ( 2 ) SD SU ( M ) T SD RTAU ( M ) k = 1 M SD SU ( k ) T SD SU ( k ) ] ( 28 ) SD T Err 2 D = [ SD RTAU ( 1 ) T ErrZ ( 1 ) SD RTAU ( M ) T ErrZ ( M ) k = 1 M SD SU ( k ) T ErrZ ( k ) ] ( 29 ) ##EQU00020##

[0115] Constraint weights w.sub.1, w.sub.2, w.sub.3 can be chosen by using the residuals of the energy terms. Embodiments of the 3D shape parameter update module 140 can estimate standard deviations of the main and constraint terms residuals and set weights equal to

w i = .sigma. main term 2 .sigma. i - th constraint 2 . ##EQU00021##

This normalizes the energy terms and avoids ill-conditioned Hessians. The weight of the main term is equal to 1 in this case.

[0116] Embodiments of the 3D shape parameter update module 160 can either use Equation (25) to compute parameter updates, or, in some embodiments, can solve Equation (24) directly without inversing the Hessian. Once the .DELTA.p parameter updates are computed, embodiments of the module 160 take the scale and the SU portion of .DELTA.p vector and update the previous (or old) scale and shape units based on the following formula:

SU.sub.new=SU.sup.old+.mu..DELTA.SU (29),

where .mu. is an update weight that takes values in 0 . . . 1 range. This provides the first set of 3D shape parameters for the first batch of frames.

[0117] Embodiments of the 3D shape parameter update module 160 then repeat the process set forth above for subsequent batches of frames. Each batch of frames is later in time than the previous batch of frames. Embodiments of the module 160 then compute an updated 3D head shape parameter by adding the 3D head shape parameter update to the current 3D head shape parameters (box 350).

III.C. Modified Gauss-Newton Minimization Technique

[0118] Embodiments of the 3D shape parameter computation system 100 and method use a modified Gauss-Newton minimization technique to minimize the energy function, as set forth above. In standard Gauss-Newton minimization, the technique iterates multiple times to converge to a solution. In order to find new SUs for a given batch of frames, the standard technique would compute the update of the SUs, (or .DELTA.p), several times until it converged to a solution. The standard Gauss-Newton then would update the SUs using Equation (29) for each computed .DELTA.p. In other words, there would be several iterations for each batch of frames.

[0119] The first iteration of the Gauss-Newton minimization technique mostly yields the minima considering the shape of the energy function. In addition, iterating the Gauss-Newton until convergence requires re-computing matrices as described above, which is quite expensive since it requires re-computing the Hessian. Moreover, the current batch of frames may not contain the most representative set of frames by solving such that the perfect SU and scale parameters are found. Thus, iterating Gauss-Newton until convergence in many cases may be a waste of time. Finally, SU and scale updates computed from a current batch of frames bring the solution "closer" to the "perfect" set of shape parameters. If they are unique, then embodiments of the method can move even closer by processing the next batch which may bring new information.

[0120] The modified Gauss-Newton minimization technique used by embodiments of the 3D shape parameter computation method shortcuts this process by observing that the first iteration produces the .DELTA.p update that "walks" to nearly the end of the problem. Thus, subsequent iterations change the SUs very little, but take the same amount of time to compute. This allows the modified Gauss-Newton minimization technique to be 2 to 5 times faster than the standard Gauss-Newton minimization technique.

IV. Exemplary Operating Environment

[0121] Embodiments of the 3D shape parameter computation system 100 and method described herein. are operational within numerous types of general purpose or special purpose computing system environments or configurations. FIG. 4 illustrates a simplified example of a general-purpose computer system on which various embodiments and elements of the 3D shape parameter computation system 100 and method, as described herein and shown in FIGS. 1-3, may be implemented. It should be noted that any boxes that are represented by broken or dashed lines in FIG. 4 represent alternate embodiments of the simplified computing device, and that any or all of these alternate embodiments, as described below, may be used in combination with other alternate embodiments that are described throughout this document.

[0122] For example, FIG. 4 shows a general system diagram showing a simplified computing device 10. Such computing devices can be typically be found in devices having at least some minimum computational capability, including, but not limited to, personal computers, server computers, hand-held computing devices, laptop or mobile computers, communications devices such as cell phones and PDA's, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, audio or video media players, etc.

[0123] To allow a device to implement embodiments of the 3D shape parameter computation system 100 and method described herein, the device should have a sufficient computational capability and system memory to enable basic computational operations. In particular, as illustrated by FIG. 4, the computational capability is generally illustrated by one or more processing unit(s) 12, and may also include one or more GPUs 14, either or both in communication with system memory 16. Note that that the processing unit(s) 12 of the general computing device of may be specialized microprocessors, such as a DSP, a VLIW, or other micro-controller, or can be conventional CPUs having one or more processing cores, including specialized GPU-based cores in a multi-core CPU.

[0124] In addition, the simplified computing device of FIG. 4 may also include other components, such as, for example, a communications interface 18. The simplified computing device of FIG. 4 may also include one or more conventional computer input devices 20 (e.g., pointing devices, keyboards, audio input devices, video input devices, haptic input devices, devices for receiving wired or wireless data transmissions, etc.). The simplified computing device of FIG. 4 may also include other optional components, such as, for example, one or more conventional computer output devices 22 (e.g., display device(s) 24, audio output devices, video output devices, devices for transmitting wired or wireless data transmissions, etc.). Note that typical communications interfaces 18, input devices 20, output devices 22, and storage devices 26 for general-purpose computers are well known to those skilled in the art, and will not be described in detail herein.

[0125] The simplified computing device of FIG. 4 may also include a variety of computer readable media. Computer readable media can be any available media that can be accessed by computer 10 via storage devices 26 and includes both volatile and nonvolatile media that is either removable 28 and/or non-removable 30, for storage of information such as computer-readable or computer-executable instructions, data structures, program modules, or other data. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes, but is not limited to, computer or machine readable media or storage devices such as DVD's, CD's, floppy disks, tape drives, hard drives, optical drives, solid state memory devices, RAM, ROM, EEPROM, flash memory or other memory technology, magnetic cassettes, magnetic tapes, magnetic disk storage, or other magnetic storage devices, or any other device which can be used to store the desired information and which can be accessed by one or more computing devices.

[0126] Retention of information such as computer-readable or computer-executable instructions, data structures, program modules, etc., can also be accomplished by using any of a variety of the aforementioned communication media to encode one or more modulated data signals or carrier waves, or other transport mechanisms or communications protocols, and includes any wired or wireless information delivery mechanism. Note that the terms "modulated data signal" or "carrier wave" generally refer to a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. For example, communication media includes wired media such as a wired network or direct-wired connection carrying one or more modulated data signals, and wireless media such as acoustic, RF, infrared, laser, and other wireless media for transmitting and/or receiving one or more modulated data signals or carrier waves. Combinations of the any of the above should also be included within the scope of communication media.

[0127] Further, software, programs, and/or computer program products embodying the some or all of the various embodiments of the 3D shape parameter computation system 100 and method described herein, or portions thereof, may be stored, received, transmitted, or read from any desired combination of computer or machine readable media or storage devices and communication media in the form of computer executable instructions or other data structures.

[0128] Finally, embodiments of the 3D shape parameter computation system 100 and method described herein may be further described in the general context of computer-executable instructions, such as program modules, being executed by a computing device. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. The embodiments described herein may also be practiced in distributed computing environments where tasks are performed by one or more remote processing devices, or within a cloud of one or more devices, that are linked through one or more communications networks. In a distributed computing environment, program modules may be located in both local and remote computer storage media including media storage devices. Still further, the aforementioned instructions may be implemented, in part or in whole, as hardware logic circuits, which may or may not include a processor.

[0129] Moreover, although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.