Building systems for adaptive tracking of facial features across individuals and groups

[0001] The present application is a continuation-in-part application of U.S. Ser. No. 13/795,882, filed Mar. 12, 2013, and, like that application, claims the priority of U.S. Provisional Patent Application Ser. No. 61/650,262, filed May 22, 2012. Both of the foregoing applications are incorporated herein by reference.

[0002] The present invention relates to automatic analysis of facial expression, and, more particularly, to analysis of facial expression in an unconstrained consumer environment.

[0003] Facial expression measurement has become extremely valuable in numerous fields such as performance driven facial animation in media production, behaviour analysis, cognitive studies, product design analytics, and measuring emotional responses to advertising.

[0004] Methods heretofore developed for measuring facial expressions are typically limited to professional applications insofar as they require constrained capture environments, specialized hardware, trained operators, physical facial markers and long setup times. These requirements make such technologies impractical for some professional and most consumer applications.

[0005] If, however, requirements for specialised equipment and environments were to be overcome, measuring facial expressions from video would become well-suited to consumer-based applications. Video cameras are commonly integrated into many consumer electronics, such as mobile phones, laptops, tablet computers, game consoles and televisions and therefore are already available to a large proportion of the consumer population. Measurement of facial expression from video is much less intrusive than other methods such as optical facial motion capture, for example, in US Patent Application 2011/0110561 A1 to Havaldar, entitled “Facial Motion Capture Using Marker Patterns That Accommodate Facial Surface,” which require subjects to have several dozen physical markers applied to the face.

[0006] Methods for tracking facial features from video exist in the prior-art. For example, Active Appearance Models (AAMs) as taught, for example, in Cootes, et al., “Active appearance models”, Proc. European Conf. on Computer Vision, vol. 2, pp. 484-98, (Springer, 1998) (hereinafter, “Cootes, et al., (1998), incorporated herein by reference), are a form of tracker which captures the variation in position and appearance of facial features in a training set of example images, and apply these to the tracking of facial features of subjects not included in the training set. If the identity of the target subject for analysis is unknown, these methods generally involve training a generic tracker that will attempt to work on the entire population. This invariably results in the system failing or underperforming on many specific individuals due to the models inability to generalise to the entire population. It is possible to retrain the tracker to include these specific individuals but this is impractical for many applications due the length of time and complexity of the training process.

[0007] In accordance with various embodiments of the present invention, a system and methods are provided that may be used for applications such as performance driven facial animation, behaviour analysis or understanding a person's response to advertising or other visual information.

[0008] A first stage robustly locates the position of physically meaningful facial features in each image frame. The location of these features can be used in a wide variety of applications including, but not restricted to, photographic and video manipulation, facial recognition, gaze analysis, product design analytics and attention measurement. A second phase uses a calibrated projected fitting approach to fit a 3D representation of the subject's face to the feature locations in each frame resulting expression measurements. Integral to certain embodiments of the system and methods is the concept of using information captured during a calibration phase. Calibration takes place during a constrained period of the subject's performance, ideally consisting of the subject facing the camera and displaying a neutral facial expression. The use of this calibration information results in increased robustness and improved accuracy of the feature location and expression measurements in a subsequent unconstrained facial performance. This step also increases the percentage of the population that the system works on and decouples the extracted expression measurements from the identity of any specific individual.

[0009] Aspects of various embodiments of the invention include, without limitation:

• • [0010] 1. A calibration step which improves both feature tracking and expression measurement stages, by capturing information about the specific individual's facial appearance and shape.
  • [0011] 2. The use of a novel spatial regularization when training a feature locator update model that produces update matrices where the coefficients associated to neighbouring pixels in the image have similar values.
  • [0012] 3. The use of optical flow between a particular image of a subject showing a neutral expression and each image within a video sequence, in order to tailor a generic feature tracker, thereby improving performance of a tracker as applied to a specific individual. This is achieved without any additional computation cost over the basic update model equation.
  • [0013] 4. A calibrated expression measurement module which ensures that expression measurements are not contaminated by varying subject identity and can therefore be used as a measure of absolute facial expression across subjects.
  • [0014] 5. A novel system of adaptive feature tracking which adapts the set of features used to analyse a subject's facial expression to the subject's specific appearance, orientation, expression and image capture conditions. In an unconstrained consumer capture scenario, this adaptation of tracking points increases the robustness of the feature tracking system over a system that tracks a pre-determined set of features.

[0015] In some embodiments of the invention, real-time avatar animation is produced from an individual's facial performance in an unconstrained consumer environment. The feature location and expression measurement stages are used as input to an avatar animation module which maps expression measurements onto avatar controls. Due to the robust and generic characteristics of the measurement system, this animation production process may be advantageously deployed in an unrestricted consumer environment targeting a large proportion of the population. This is an extremely challenging use-case to which the system may be ideally tailored.

[0016] In accordance with one embodiment of the present invention, a computer implemented method is provided for generating a non-transient record embodying measures of an adaptive set of feature locations characterizing a face of a person. The method has steps of:

• • [0017] a. receiving a video sequence that constitutes a physical record of the face of a specified individual person;
  • [0018] b. applying a feature locator update model to the video sequence, the feature locator update model derived by steps of:
    • [0019] i. defining a set of training data consisting of training images with associated facial feature locations;
    • [0020] ii. generating a set of facial feature displacements for each training image with associated image sample vectors; and
    • [0021] iii. training a regularized linear regression which maps from image sample vectors to displacement vectors, wherein the regularized linear regression is characterized by regularization that includes a spatial smoothness term within the shape-free sample space;
  • [0022] c. extracting a plurality of locations corresponding to the adaptive set of feature locations;
  • [0023] d. based on the feature locator update model, characterizing the locations of features of the face of the specified individual person; and
  • [0024] e. storing the locations of features to the non-transient record.

[0025] In accordance with other embodiments of the present invention, the plurality of feature locations extracted by the feature locator update model can be adapted to produce a set more suited to robust location. This adaptation may be performed with respect to the following subject and image characteristics:

• • [0026] a. the subject's appearance, adding features during calibration that are suitable for tracking, discarding those unsuitable for tracking due to low feature contrast or partial occlusion such as low contrast eye-brows or occluded upper lip features;
  • [0027] b. the subject's head pose with respect to the camera, selecting only features visible in the current frame, discarding those obscured due to self occlusion caused by the subject's head position and orientation;
  • [0028] c. the subject's expression, selecting only features visible in the current frame, discarding those obscured due to self occlusion caused by the subject's expression, for example only tracking pupils when the subject's eyes are open, or only tracking teeth when the subject's mouth is open;
  • [0029] d. the subject's feature visibility, selecting only features visible in the current frame, discarding those obscured due to occlusion caused by the subject's own hair or other occluding objects, for example removing features such as eye-brows when occluded by hair, or eye features when occluded by dark glasses; and
  • [0030] e. the lighting conditions of each frame, for example excluding features if they fall in regions of the images exhibiting low or poor illumination

[0031] Another embodiment of the present invention modifies the feature locator to extract feature locations for the set of adapted features specific to the individual and the image capture conditions in the way described above, driven by image sample vectors derived only from the adapted set of features.

[0032] In accordance with yet further embodiments of the present invention, there are additional steps of:

• • [0033] a. creating an expression extractor containing a plurality of controls representing both identity and expression variation;
  • [0034] b. fitting, in a fitting process, 3D pose, identity and expression parameters to features from a specific individual in a calibration pose;
  • [0035] c. fixing a set of identity controls to produce a tailored person specific expression extractor; and
  • [0036] d. applying the above fitting process on a person-specific expression extractor to the video sequence that constitutes a physical record of the face of a specified individual person to produce facial expression parameters,
    wherein the facial expression parameters represent facial feature measurements which are uncontaminated by identity variation between individuals.

[0037] Any of the foregoing computer-implemented methods may be performed on a mobile device, or a smart TV, for example. They may include measuring an expression of the person in response to pre-rendered video footage or in response to dynamically rendered display content, including a software display.

[0038] In accordance with various embodiments of the present invention, there may be additional steps of producing real-time pre-visualization of a character animation during performance capture in media generation, or creating video content containing avatar animation, or creating character animation in real-time.

[0039] In accordance with another aspect of the present invention, a non-transitory computer readable medium is provided for use on a computer system for storing computer-readable program code. The computer readable program code has:

• • [0040] a. a computer code module for receiving a video sequence that constitutes a physical record of the face of a specified individual person;
  • [0041] b. a computer code module for applying a feature locator update model to the video sequence;
  • [0042] c. a computer code module for defining a set of training data consisting of training images with associated facial feature locations;
  • [0043] d. a computer code module for generating a set of facial feature displacements for each training image with associated image sample vectors;
  • [0044] e. a computer code module for training a regularized linear regression which maps from image sample vectors to displacement vectors, wherein the regularized linear regression is characterized by regularization that includes a spatial smoothness term within the shape-free sample space, thereby generating the feature locator update model;
  • [0045] f. a computer code module for extracting a feature location, based on the feature update model, characterizing the location of the feature of the face of the specified individual person;
  • [0046] g. a computer code module for extracting a plurality of feature locations corresponding to an adaptive set of feature locations; and
  • [0047] g. a computer code module for storing the plurality of feature locations to a non-transient medium.

[0048] In other embodiments of the non-transitory computer readable medium, there may be additional modules:

• • [0049] h. a computer code module for extracting a facial expression parameter, based on the feature update model, characterizing an expression of a feature of the face of the specified individual person; and
  • [0050] i. a computer code module for storing the facial expression parameter to the non-transient record.

[0076] As used in this description and in the appended claims, the term “image” refers to any multidimensional representation, whether in tangible or otherwise perceptible form or otherwise, whereby a value of some characteristic is associated with each of a plurality of locations corresponding to dimensional coordinates of an object in physical space, though not necessarily mapped one-to-one thereonto. Thus, for example, the graphic display of the spatial distribution of some feature, such as temperature, in one or more colors constitutes an image. So, also, does an array of numbers in a computer memory or holographic medium. Similarly, “imaging” refers to the rendering of a stated physical characteristic in terms of one or more images.

[0077] As used herein and in any appended claims, the term “optical flow” refers to an estimation of motion based on assumptions of the temporal appearance consistency of features in a visual scene given small feature displacements. Optical flow has been formulated, for example, in Horn & Schunck, Determining Optical Flow, MIT Artificial Intelligence Laboratory Memo No. 572 (1980), available at http://hdl.handle.net/1721.1/6337.

[0078] A system 99 that may be employed for practice of embodiments of the present invention is first described with reference to FIG. 1. A monocular video camera 100 is positioned to capture the face of a subject 102 during a facial performance, and a computational device 101 contains a central processing unit and memory. The memory is capable of storing all of the entities (such as the trackers 203 and Expression Extractor 204) and data of the system (such as the training data 201, feature locations 210 and expression measurements 209). The memory also contains a program in the form of a series of instructions which, when executed by the central processing unit, and applied to the data and entities, track the location of the facial features in the images captured by the camera and measure the expression of the subject. The system 99 is configured so that the video of the subject's performance is captured by camera 100, and streamed to computational device 101 for processing and generation of the facial feature locations and expression measurements in real-time. In one embodiment of the invention, the computational device 101 transforms the expression measurements into movements and animation of a digital character. In another embodiment of the invention, the feature locations and expression measurements are stored within the computational unit's memory for off-line analysis, by computational device 101 or by another system.

Real-Time Expression Measurement Process

[0079] Methods for generating Tracked Feature Locations 210 and Expression Measurements 209 from images of a subject's performance 206 captured by camera 100 are now described with reference to the flowchart depicted in FIG. 2. Methods in accordance with embodiments of the present invention may be divided into two phases: an Offline Phase 200 involving the training and construction of the Tracker 203; and a Real-Time Phase 205, which uses the Tracker 203 and Expression Extractor 204 to generate the expression measurements and tracked feature locations. Offline Phase 200 is executed prior to Real-Time Phase 205, but need not be executed on the same computational unit since its generated output, the tracker 203, may be stored on digital memory and transferred to other computational units. Once constructed, Trackers 203 may be used for any number of Real-Time Phase executions.

[0080] Offline phase 200, described in detail below, entails training the trackers using training data which consists of images of the features to be tracked, annotated with the locations of the features.

[0081] During the Real-Time Phase 205, the Tracker 203 and Expression Extractor 204 provide a stream of feature locations and expression measurements for each image of the captured video sequence. Each captured image is processed by the Tracker 203 in module 207, to produce the location of all features 210. In addition, the output generated by module 207 for each image is transformed by the Expression Extractor 204 into measurements of the subject's expression 209. The real-time processes are repeated for each frame of the captured video producing a continuous stream of tracked feature locations and expression measurement which may be further processed in real-time, e.g. for real-time digital character animation, or saved for subsequent processing. FIG. 5 shows an example of feature locations and expression measurements applied to a digital character for a single frame of video input.

Training the Tracker

[0082] In Offline phase 200, module 202 generates a Tracker object 203, as described in greater detail with reference to FIG. 3. As shown in FIG. 3, Tracker 203 may have three feature locator components: Calibration Feature Locator 300, Generic Subject Feature Locator 301 and Specific Individual Feature Locator 302. Each of the foregoing components have the same basic structure, however they are tailored to different phases of the feature tracking process. The calibration and generic subject feature locators 300 and 301 are created during Offline Phase 200, while the specific individual feature locator 302 is created by module 900 during the calibration phase as further discussed below with reference to FIGS. 9 and 10.

[0083] Training a feature locator is implemented on the basis of a set of annotated example images denoted Training Data 201 in FIG. 2 A consistent set of feature locations is defined in each image to represent the shape of the deformable object to be tracked. These features should represent unique, salient features which ideally are present throughout the entire data set. FIG. 8 depicts an example of a training image where the white dots indicate the position of one possible set of facial features. Any choice of a particular set of features is within the scope of the present invention. The set of training images can be chosen to represent the variation in the shape and appearance of the object to be tracked and can therefore tailor the feature locator to a specific application. For example, if the set of training images contains a wide variety of subjects, each with a neutral facial expression, the resulting feature locator will be capable of finding features in a wide variety of subjects with a neutral expression, but will not be capable of identifying features in images of subjects with other facial expressions. In general, the more specific a set of training images are to a particular appearance, the more accurate the resulting feature locator will be in that scenario. However the locator will perform poorly in other scenarios. A locator trained on a very widely varying image set will perform adequately on a wide variety of data but will not give accurate locations over that data set. In general, for an individual feature locator, there is a trade-off between feature locator generality/robustness and accuracy. Based on these observations, Tracker 203 uses a combination of feature locators to produce robust and accurate results over a very wide range of image appearance.

[0084] FIG. 6 shows a flowchart of a preferred embodiment of the invention, where calibration feature locator training data 500 is selected to include a wide variety of subjects' facial appearance, but with each subject's images limited to contain only neutral expression. This data results in the calibration feature locator 300 being capable of robustly identifying neutral expression over a wide variety of subjects. In contrast, the generic subject feature locator training data 501 is selected to include a wide variety of subjects' facial appearance and a wide variety of expressions. This produces a generic subject feature locator 301 which is robust to many subject identities and facial expression variations, but that may not be accurate for any given specific individual. Both feature locators are trained in the same way using module 502, as now described in detail.

Training a Feature Locator

[0085] Given an initial set of feature locations in an image which may not lie on the desired physical locations, a feature locator will predict the direction and magnitude of an update step that will move the feature locations closer to the desired physical locations. Iterating this process will move the feature locations progressively closer to the desired result until convergence. Many techniques in the prior-art utilise an approach such as this, for example AAMs, as described in Cootes, et al., (1998). Feature locators typically base this update step on a shape-normalised sample taken from the image with reference to the current feature points. Methods of achieving this sampling are well known in the field.

[0086] In the present description and in any appended claims, a set of feature locations may be referred to as a “shape,” and the desired set of feature locations as defined by the training set may be referred to as the “solution.” For simplicity, the notation will be restricted to the application of methods to single channel images, however extension to multi-channel images is straight-forward and is encompassed within the scope of the invention.

[0087] In order to learn the relationship between the image sample at a given shape and the displacement from the solution, a linear regression model is created. This model is referred to as the “Update Model.” Given a matrix of 2D feature locations

[0088] $X=\left[\begin{array}{ccc}{x}_1& \cdots & x_N\\ y_1& \cdots & y_N\end{array}\right]$
and the corresponding sample vector S, the update model is defined to be of the form:
U(X,S)=X+[B₀+B₁S+B₂[X]_2N×1]_2×N  (Eqn. 1)
where [X]_M×N denotes a matrix of size M×N constructed of the elements of X read in a column major order (i.e., with the columns listed in sequence), for example [X]_2N×1, reshapes the matrix X, of size 2×N, into a vector of size 2N×1. [X]_M×N may also be referred to herein as a “reshape operator.” The vector B₀ and the matrices B₁ and B₂ define the update model and are learnt from annotated data. X and U are typically represented in an appropriately aligned model space, in which case, U is therefore mapped back into image space after this update has been calculated.

[0089] Training data 201 define a set of N_e training shapes X₁, . . . , X_NE, where each training shape X_i is a matrix of size 2×N. The vector B₀ and matrices B₁ and B₂ are to be found that minimize the error:

[0090] $E=\sum _{i=1}^{N_E}{U\left(d_i,S_i\right)-X_i}^2,$
where d_i is a randomly perturbed shape that deviates slightly from the ground truth X_i, and S_i is the corresponding sample vector. The error can be rewritten explicitly using B₀, B₁ and B₂ as follows:

[0091] $E=\sum _{i=1}^{N_E}{B_0+B_1{S}_i+{B_2\left[d_i\right]}_{2\mathrm{Nx}1}-{\Delta }_i}^2,$
where Δ_i=[X_i−d_i]_2N×1.

[0092] The regression error may be reformulated in a more compact manner:
E=∥Δ−BD∥²,
where:
B=[B₀^T, B₁^T,B₂^T]^T;
Δ=└Δ₁, . . . , Δ_NE┘, a matrix of size 2N×N_E denoted the output data matrix; and
D=[D₁, . . . , D_NE], with D_i=[1 S_i^T[d_i]_L×2N]^T.

[0093] Minimization of E with respect to B leads to B=CΣ_D⁻¹, where C=ΔD^T, and the data covariance matrix Σ_D=DD^T. B may be computed without inversion of the sample covariance matrix Σ_D by, instead, solving the following linear system: BΣ_D=C. However, the matrix Σ_D is in general not well-conditioned and the estimated matrix B can be sensitive to small amounts of variation in the training data matrix D and in particular to the samples vectors S_i. This can result in a poor generalization of the update model to unseen images. One potential solution to this problem is to reduce the dimensionality of the samples vectors by projecting them onto a smaller linear space using principle component analysis (PCA). This approach is used for example by AAMs, as taught in Cootes, et al., (1998).

[0094] In accordance with preferred embodiments of the invention, more effective generalization can be achieved if explicit regularization is employed in the minimization of E. The matrix B is estimated using a cost function that combines the previously defined cost with a regularization term:
E_r=∥Δ−BD∥²+R(B₁).

[0095] A sample vector S_i can be represented in a normalized frame called a shape-free image. FIG. 7 shows an example of a shape-free image of this type together with the corresponding image-space sample locations. In the same way, the coefficients of the update model B, (which may also be referred to, herein, as the “update matrix”) can also be interpreted in this shape-free space. In general, a model with a smooth spatial variation of coefficient values in this space will produce better generalisation and accuracy than a model with a more random distribution of coefficient magnitudes. Models with this characteristic are also more robust to imaging conditions such as noise and poor lighting. This smoothness can be thought of as introducing a characteristic to the model where neighbouring parts of image appearance affect the update step in a smooth and continuous manner, which will produce smooth and well regularised model convergence.

[0096] In accordance with preferred embodiments of the present invention, the aforesaid smooth spatial variation of coefficient values facilitates a novel regularization scheme that produces update matrices where the coefficients associated to neighbouring pixels in the shape free image have similar values. In order to formulate the regularization, a specialized masked convolution operator {circle around (x)}, is defined as follows:

[0097] $c=a{\otimes }_{s}b\iff \{\begin{array}{c}m\left(i,j\right)=1\mathrm{if}\underset{k=1}{\bigcup ^M}\underset{l=1}{\bigcup ^N}\left(i-k+\lfloor M/2\rfloor ,j-l+\lfloor N/2\rfloor \right)⋐G_s,0\mathrm{else}\\ c\left(i,j\right)=m\left(i,j\right)\sum _{k=1}^M\sum _{l=1}^{N}b\left(k,l\right)a\left(i-k+\lfloor M/2\rfloor ,j-l+\lfloor N/2\rfloor \right)\end{array}$
where the shape free image has dimensions M×N, and m(i, j) is a masked region of the shape-free image equal zero when the convolution kernel b does not fully overlap with points in the set of shape free sample locations G.

[0098] A matrix-valued function Λ is introduced, where Λ takes a 2D matrix a as its argument. The matrix Λ(a) is a sparse matrix defined as the square matrix of size N_s×N_s such that the following holds:
∀Sε^c×Ns:∀(a)[S]_Ns×1=[I_sf⁻¹(I_sf(S){circle around (x)}_sa)]_Ns×1,
where I_sf (S) constructs a shape-free image from a vector of samples; and I_sf⁻¹(S) constructs a vector of samples from a shape-free image.

[0099] FIGS. 7A and 7B illustrate the construction of the shape-free image. FIG. 7A shows the original image together with the corresponding image-space sample locations as white dots, the image values at which form the vector S. The larger white crosses indicate the facial feature locations for this image. 7B shows an example of the shape-free image for this vector I_sf (S).

[0100] Matrix ∀(a) simply restates as a matrix product the following set of operations:

• • [0101] reconstruct a shape free image from a set of sample intensities values S
  • [0102] convolve the reconstructed image by a 2D kernel matrix a
  • [0103] resample the matrix of intensities of the convolved image into a 1×N_s single column vector, taking only values from the sample locations G_s.

[0104] Matrices M_x, M_y and M_xy are now defined as three sparse matrices:

[0105] $M_x=\Lambda \left(\left[-1,1\right]\right)$ $M_y=\Lambda \left({\left[-1,1\right]}^T\right)$ $M_{\mathrm{xy}}=\Lambda \left({\left[-1,1\right]}^T\left[-1,1\right]\right).$

[0106] The matrix M_x computes the gradients in the x dimension of the shape-free image directly from a matrix S of intensity values. Therefore each row of the matrix M_xB₁ corresponds to the set of derivatives in the x direction of the update coefficient shape-free image reconstructed from the corresponding row in B₁. Similarly M_yB₁ contains the derivatives in the y direction of the update coefficient shape-free images and M_xyB₁ contains the second order partial derivative σxσy of the reconstructed update coefficient shape-free images.

[0107] The regularization term is rewritten

[0108] $R\left(B_1\right)={{\Gamma }^{1/2}{B}_1}^2$ $\mathrm{with}\Gamma ={\lambda }_x{M}_x^T{M}_x+{\lambda }_y{M}_y^T{M}_y+{\lambda }_{\mathrm{xy}}{M}_{\mathrm{xy}}^T{M}_{\mathrm{xy}}.$

[0109] The matrix minimizing E_r(B) may then be obtained by solving the following linear system:

[0110] $\left({\sum }_D+{\Gamma }_2\right)B=C$ $\mathrm{with}$ ${\Gamma }_2=\left[\begin{array}{ccc}{0}_{1\times 1}& 0_{1\times 3N_s}& 0_{1\times 2N}\\ 0_{3N_s\times 1}& \Gamma & 0_{3N_s\times 2N}\\ 0_{2N\times 1}& 0_{2N\times 3N_s}& 0_{2N\times 2N}\end{array}\right].$

• • [0111] Here Γ₂ represents a zero-padded version of Γ which regularises only the sub matrix of B corresponding to B₁.
    Locating Features

[0112] Locate Features Module 901 (shown in FIG. 9) executes the process of determining the location of features in each captured image in the sequence. The facial features for each frame of video are located by generating multiple possible solutions, or hypotheses, each containing the location for all features, then choosing the best hypothesis and determining whether or not the tracking has been successful or not for that frame. Each hypothesis is generated by defining an initial set of locations for each feature, and then refining each hypothesis with a feature locator.

[0113] Either (or both) of two methods may be used to generate initial hypotheses for the location of features in a given frame (module 902); locations based on the detected position of the face within the current frame and locations of the features in previous frames.

[0114] In cases where no valid historical information exists for the expected position of the features (for example, the first frame, or when features were not successfully located in the previous frame, or where such information would not be appropriate such as during a user triggered calibration phase 900), features are placed based on the detected position of the face within the frame. The frame is analysed using a face detection system. Face detection systems that may be used within the scope of the present invention include those described by Liao, et al. in “Learning Multi-scale Block Local Binary Patterns for Face Recognition,” International Conference on Biometrics (ICB), LNCS 4642, pp. 828-837 (2007), which is incorporated herein by reference. Face detection systems typically provide a rectangular box in the image within which a face is likely to reside. The tracker contains information on the average position of each feature, relative to the size and location of this face detection box, and places one hypothesis, containing all of the features required to be tracked, at these average locations. In addition, the tracker contains information on a set of other possible locations for each feature within a face detection box, based on the variation in dimensions of people's facial features and the range of motion of the features typical in a sequence of an actor's performance. This information is used to place further multiple hypotheses for each feature designed to encompass the expected range of facial dimensions and expressions.

[0115] During normal feature tracking of a video sequence, methods in accordance with the present invention utilize the knowledge that a feature's location will normally not move significantly between successive frames of video, by using its location in previous frames as an initial estimation for its location in the current frame. In this way, the set of feature locations in previous frames is used to generate extra hypotheses in the set. In the preferred embodiment, the number of hypotheses generated from previous frames is limited to a user-specified maximum.

[0116] With further reference to FIG. 9, in module 903, the tracker's update model is used to iteratively improve each feature location hypothesis independently using Eqn 1. which is defined in the section entitled “Calibrating the Tracker.” The update model equation is applied iteratively for a pre-defined number of iterations, limited by the time interval required to achieve real-time tracking of the input images.

[0117] Given a number of refined hypotheses, each of which defines a location for each of the facial features, module 904 is used to select a single hypothesis as the output for the feature locations on the current frame. This is achieved by calculating a confidence measure for each possible solution and choosing the solution with the highest confidence which is set as the output feature locations 906. In one embodiment of the invention, a statistical shape and appearance model, such as that taught by AAMs, is used to capture the appearance of the training data and model its appearance using a Principle Component Model, represented by the mean appearance, A₀, plus a linear combination of m appearance bases {A_i}

[0118] $A=A_0+\sum _{i=1}^m{\lambda }_i{A}_i,$
where the coefficients {λ_i} are the appearance parameters. The confidence is calculated as the Pearson's correlation between the original appearance, A, and the appearance synthesised from the appearance model parameters, A_λ.
C_a=corr(A,A_λ)

[0119] In addition to a set of feature locations for each image captured, the tracker provides information on whether or not the feature locations constitute a successful result for each captured image to enable the expression measurer to decide whether or not the result should be used as an initial hypothesis for subsequent frames and to enable to Expression Measurer to decide whether or not to use the result. In preferred embodiments of the invention, module 905 defines minimum confidence threshold measure, and any tracking result whose confidence is below this threshold is deemed to be a failure. The outcome of this module is recorded as feature validity 907 for use in the processing of the next frame of input.

Calibrating the Tracker

[0120] With reference, now, to FIG. 10, the locate features module 901 can be applied with any feature locator. In one embodiment of the invention, a generic subject tracker 301 is used in this module. The generic subject feature locator is trained using data containing both identity and expression variation and, as such, can locate features in a wide variety of individuals showing a range of expressions. However individual subjects with an appearance that is not well represented in the training data may result in inaccurate feature locations. One example of this is shown in FIG. 11A, where the features around the individual's mouth have been inaccurately placed. The system can improve on this result by tailoring a feature locator to a specific individual, after a calibration image of the specific subject has been obtained. In module 900, the calibration feature locator 300 is used extract reliable feature locations for any subject exhibiting a constrained expression. That information may then be used to construct a specific individual feature locator 302 tailored to that individual.

[0121] In accordance with preferred embodiments of the present invention, the calibration feature locator is trained on multiple identities with neutral facial expressions and the subject is required to adopt this expression for the period of the calibration process. The specificity of the calibration tracker to neutral expressions enables it to extract reliable feature locations at this expression for a far wider set of identities than the generic feature locator. An example of improvements gained using this approach is shown in FIG. 11B, as previously discussed, where the accuracy of the specific individual feature locator is improved in the mouth region.

[0122] A specific individual feature tracker is constructed in module 1000 (shown in FIG. 10) by incorporating the optical flow (as defined above) between the individual's neutral appearance and the current image sample into the formulation of the update model. As used herein and in any appended claims, the term “optical flow” refers to an estimation of motion based on assumptions of the temporal appearance consistency of features in a visual scene given small feature displacements. In the update model context, in accordance with embodiments of the present invention, if the features are close to the solution, the optical flow provides valuable information about the direction and magnitude of the update step. This information is extracted with reference to the specific appearance of the individual allowing the model to become more tailored to the individual. This process will now be described.

[0123] Furthermore, the specific formulation of this combination is achieved in such a way as not to increase the computational complexity of the update model. This formulation is also novel in the prior-art and is extremely valuable in retaining the real-time performance of the specific individual feature locator. The underlying formulation of the optical flow and its relationship to the update model of a feature locator will first be described, then the process of creating a specific individual feature location will be explained.

[0124] In the calibration phase, a vector of calibration samples S₀ is obtained using the calibration feature locator 300 and the location module 901. In accordance with preferred embodiments of the invention, the calibration sample represents the neutral appearance of a subject. From this vector, a calibration shape free image I₀=I_sf (S₀) can be reconstructed. At each iteration of the tracking process, a new vector of image samples S_t is obtained and, from these multiple samples, a new shape free image I_t=I_sf (S_t) may be reconstructed.

[0125] Making assumptions that are standard in the field of facial performance tracking, and following the algorithm of Horn & Schunck, the optical flow between the neutral appearance and the current image sample can be estimated by minimizing the following cost function with respect to u and v:

[0126] $C_f\left(u,v\right)={I_{x}u+I_{y}v+I_0-I_t}^2+\sum _{\left(i,j\right)\in G_s}\alpha \left({u_x}^2+{u_y}^2+{v_x}^2+{v_y}^2\right),$

[0127] Here, u and v represent two scalar images with u representing the warping magnitude (or optical flow) in the x direction and v representing the warping magnitude in the y direction, and a is a regularisation coefficient which may be manually tailored to the desired application.

[0128] By reformatting u and v into a single vector f=[I_sf⁻¹(u)^TI_sf⁻¹(v)^T]^T that will be referred to, herein, as the “optical flow vector,” the minimized function C_f may now be rewritten in a matrix form:
C_f(f)=∥Gf+S₀−S_t∥²+αf′Lf
with
G=[diag(I_sf⁻¹(I_x))diag(I_sf⁻¹(I_y))]
and
L=kron(M_x^TM_x+M_x^TM_x,T_2×2),

[0129] where kron denotes the Kronecker tensor product.

[0130] In this representation, G is a sparse matrix containing information about the gradient of the shape-free image in both x and y directions, and f^t Lf represents a smoothness measure of the optical flow estimate. Thus, a statement of the objective is to find the optical flow vector that most accurately represents the image warp field between I₀ and I_t, while retaining as much smoothness as possible. The minimiser f of the function C_f may be found by solving the linear system:
(G^tG+L)f=G^t(S_t−S₀)
using a specialized solver for sparse positive definite systems, such as described, for example, by Zlatev, “Computational Methods for general sparse matrices,” Kluwer, (1991), which is incorporated herein by reference, or otherwise.

[0131] In one embodiment of the invention, the foregoing formulation of optical flow is integrated into a trained update model framework by adding the coefficients of u and v to our sample vector to produce an augmented sample vector S′. A new augmented update matrix B′ is formed by adding a third sub-matrix B₃ to the update model coefficients B such that B′=[B₀^T, B₁^T, B₂^T, B₃^T]^T. The sub-matrix B₃ represents the contribution of the optical flow to the update of the model during tracking and its coefficients must be determined during the training phase. To achieve this, a calibration image is associated with each image in a training set. In the preferred embodiment this calibration image contains the same individual as in the training image but with a neutral expression. The corresponding optical flow denoted f_i for each training example is computed, and an augmented training data matrix D′=[D₁′, . . . , D_E′] is constructed, with D_i′=[D_i′^T f_i^T]^T. The augmented update matrix B′ can then be derived using the same regression technique as the one used in the Training Feature Locator section above.

[0132] The update function with optical flow is now as follows:
U₀(X,S)=X+[B₀+B₁S+B₂[X− X]_2N×1+B₃f]_2×N,
with f the solution of
(G^tG+S)f=G^t(S−S₀).

[0133] The foregoing equation, and therefore the solution of the system, must be calculated at each iteration of tracking for all hypotheses and on every frame of video. The computational complexity of this operation is therefore critical to the performance of a tracking system in accordance with the present invention. A novel formulation of optical flow may be used, in accordance with preferred embodiments of the invention, to implement this operation with no additional computational cost over our standard non-augmented tracker. This is extremely valuable in achieving a real-time performance for calibrated specific individual feature locators. In particular, instead of solving this system at every iteration, f can be rewritten as follows:
f=H(S−S₀)
where H=(G^tG+L)⁻¹G^t. In this equation, H does not depend on the current image sample S, but it is determined by the sample obtained from the specific individual during calibration and therefore contains the information about the individual's appearance. However, the matrix H is large with dimension 2N_S×N_S and the above multiplication is too computationally and memory intensive to be performed at each iteration. However, the update equation can be rewritten in a more computationally efficient form as follows:
U₀(X,S)=X+[B₀′+B₁′S+B₂[X− X]_2N×1]_2×N≡X+[B₀+B₁S+B₂[X− X]_2N×1+B₃f]  (Eqn. 1″)
with

[0134] $\begin{array}{cc}\begin{array}{c}{B}_0^{\prime }=\left(B_0-{\mathrm{HS}}_0\right)\\ B_1^{\prime }=\left(B_1+B_{3}H\right).\end{array}& \left(\mathrm{Eqn}.2\right)\end{array}$

[0135] The new update matrices are referred to herein, and in any appended claims, as “baked matrices,” as they can be thought of as “baking” the calculation of the specific individual's optical flow into the pre-existing update model coefficient matrices. This results in an update model that is specific to the calibration sample of a specific subject.

[0136] Module 1000 (shown in FIG. 10) creates a specific individual feature locator 302 using information contained within the generic subject feature locator 301 together with information about the individual's neutral appearance. A generic subject feature locator contains the matrix B₃ which was learnt as part of the training process. As described above, this matrix represents information about how optical flow is mapped to feature location updates as described in Eqn. 2. During the calibration process a robust estimate of the specific individual's neutral appearance is extracted from module 901. This provides the calibration sample vector S₀. Module 900 uses Eqn. 3 to bake the identity specific optical flow information into the update model matrices B₀′ and B₁′, resulting in a update model that is tailored to the specific appearance of the individual as recorded in sample vector S₀. This process results in a specific individual feature locator 302 that is significantly more effective at locating features on the individual it is calibrated on than the un-calibrated generic feature locator. For convenience, specific individual feature locator 302 may be referred to, herein, as the “feature locator.” An example of this improvement is shown in FIG. 11B, where the accuracy of the specific individual feature locator is improved in the mouth region. Furthermore, this improvement in accuracy is achieved without introducing extra computational cost when analysing frames after the calibration process.

Adaptive Tracking

[0137] In a constrained video capture environment, it may be possible to pre-determine a set of facial features that will be visible in each frame of video throughout the entire capture. However, in an unconstrained consumer capture scenario with unknown subject appearance, in general, this is not possible. The appearance of a specific individual can make certain features challenging to identify, for example low contrast eye-brows, or partially occluded features due to hair or dark glasses. Conversely, a specific individual may have facial regions that are especially amenable for feature tracking, such as moles or facial hair. Features can become unobservable or observable during the course of a video sequence due to self-occlusion attributable to head position and orientation changes, or due to changing expression, or because of illumination changes causing shadows and poor lighting over parts of the tracking region.

[0138] For these reasons, it is highly desirable to provide a feature adaptation system designed to adapt to the specific appearance and image capture conditions of each frame of a video sequence. The feature adaptation system may be referred to herein as an “adaptive tracker,” and it is designated by numeral 305, shown in FIG. 3. In accordance with embodiments of the present invention, adaptive tracking may be achieved by selecting an adaptive set of feature locations during calibration, and, during video tracking potentially refining that set further based on the characteristics of each frame.

[0139] As used herein, and in any appended claims, the term “adaptive set” shall mean a set of elements (inclusive of values or parameters), the elements of which may be varied in time without the set losing its characterization as the originally identified set. When elements of the adaptive set of features have been modified, the adaptive set of features may be referred to herein as an “adapted set of features,” or, equivalently, as an “adapted feature set.”

[0140] In further accordance with embodiments of the present invention, feature locator 302 may be modified to update feature locations based only on image sample vectors derived from the adapted set of features. The output of the feature adaptation system for each frame is the adapted set of feature locations. The full original set of feature locations derived from the training set 201 can be obtained, if desired, using a predictive method based on the adapted set of feature locations, however these locations may not be derived directly by the adaptive tracker.

Adaptive Feature Selection: Subject's Appearance

[0141] One embodiment of the invention deals with selecting feature locations that are suitable for tracking and discarding unsuitable features based on the appearance of the subject during calibration of the feature locator 900. In this embodiment, feature locations amenable for tracking a specific individual may be added to the set of features annotated in the training set 201, and features in the training set that are not suitable for tracking may be removed. This embodiment produces a set of feature locations adapted to the specific appearance of the subject to be tracked which is not pre-determined during the training phase.

[0142] Features suitable for tracking must be identifiable with precision in the image. They must be distinct from similar nearby features with respect to the contents of the local image region. A measure such as “feature saliency” can be used to evaluate the quality of image features for tracking, such as described in Walker et al., Automatically building appearance models from image sequences using salient features, Image and Vision Computing, (2002), which is incorporated herein by reference, although alternative measures may be used within the scope of this invention. In this embodiment, image locations that lie within the facial region in the calibration frame are assigned a saliency value. Locations not annotated in the training set having a saliency measure above a specified threshold are added to the set of feature locations to be tracked in subsequent frames. The threshold for addition to the set of tracked feature locations can be determined from the statistics of the saliency measure over the training set. These features selected due to their saliency measure in the calibration frame are not included in the training set and therefore cannot be refined with the feature locator update model.

[0143] In preferred embodiments of the invention, a data-driven feature tracking approach such as normalized cross-correlation maximization is adopted in order to refine the location of these features in subsequent frames, a technique that is well-known. Other data-driven feature tracking methods may also be applied within the scope of this invention. In addition, a prior model of the training set feature location positions across the facial region may be used to constrain the position of the additional features with respect to the training set features. Smooth spatial variation with respect to the training set points is assumed for the additional features and this can be used to regularize the estimated location of the additional features. This type of regularization is commonly used in the prior-art to obtain a more robust localization of the additional features in each frame.

[0144] Each additional feature location can be associated with a specific location on the face of the subject with reference to the feature locations identified by Locate Features Module 901 (shown in FIG. 9) on the calibration frame (not shown). Using these locations, the additional features can be utilized directly in the expression measurement process described below.

[0145] For a specific subject, certain features may not be suitable for tracking. For example, weakly visible features such as eye-brows with low contrast over background skin tone and upper lip features with partial occlusion due to facial hair. Features that were part of the training set, but with a saliency measure below a certain threshold are removed from the adapted set of feature locations. The threshold can be determined for each feature from the statistics of the saliency measure over the training set.

Adaptive Feature Selection: Subject's Head Position and Orientation

[0146] In one embodiment of the invention a measure of the position and orientation of the subject's head in 3D space may be used to select only the facial features which are visible in the camera view, and remove features which are self-occluded by the face. During the tracker's training stage, a large set of facial features are defined so as to cover the full surface area of a subject's head, covering all angles of view from the left side, through to frontal, to the right, and from above and below. Due to the extent of the facial features, no single training image is able to show all of the facial features. FIGS. 24A-24C shows examples of visible and occluded image features 240 for different head poses. As head 242 turns from frontal to right profile view, features on the left side of the face are self-occluded by the face, while other features, such as those on the side of the nose, become visible. During the training stage, the training images are compartmented according to the set of facial features visible in each. In one embodiment of the invention, one sub-tracker may be trained using all the images where the subset of front facing features are visible, and other trackers trained using the sub-set of features visible on the left and right sides of the face respectively. For improved performance, the subsets of facial features should be chosen to provide as much overlap as possible, as to make the choice of which sub-tracker to use less critical. In addition, the subsets should be chosen so that the union of any two subsets of features are present in as many images as possible as to facilitate the transition between the sub trackers during tracking

[0147] After each frame of tracking, a head-pose module 307 (shown in FIG. 3) is used to measure the 3D orientation and position of the head and, depending on the result, to choose which of the sub-trackers, with associated subset of visible facial feature points, to use for the next frame.

[0148] One embodiment of head-pose module 307 is the “Projected Fitting” method described below. The Projected Fitting method provides a transform, x^t, which contain the six extrinsic translation and rotation parameters required to define the 3D location of the subject's head.

[0149] After applying this method of feature selection, the adaptive set of feature locations (as defined above) consists of the training features for the sub-tracker after removing features excluded by appearance adaptation, as described above. Saliency can be used to add new features when sub-tracker switching is performed, also described above.

Adaptive Feature Selection: Subject's Expression

[0150] One embodiment of the invention selects features based on the subject's expression. Certain facial features may be occluded due to the user's expression, for example, pupils are occluded by the eye-lids when the eyes are closed, or teeth may be occluded by the lips. If visible, the ability to track features such as pupils and teeth greatly enhances the expression analysis of the character. In one embodiment of the invention, the Expression Extractor 204 (shown in FIG. 2) is used to determine which of the features are visible in the next frame. Specific character controls are used to determine the visibility of certain features. If the Expression Extractor 204 eye-lid control outputs indicate that the eyes are open or partly open, then eye pupil points are included in the adaptive feature set. If, however, the eye-lid controls indicate that the eyes are closed, then the pupil features are removed from the adaptive set. A similar expression-based analysis may be performed, within the scope of the present invention, with other self-occluded facial features.

Adaptive Feature Selection: Subject's Feature Visibility

[0151] One embodiment of the present invention discards feature locations that are occluded due to the subject's own hair or external objects such as dark glasses. A feature matching approach is employed to determine the visibility of each feature point, as now described. Features in each frame of video are matched to a probability distribution learned from training data. As part of the training process, a descriptive vector is extracted from each feature location of each image in the training data. An objective of the method is to determine the visibility of a feature in tracking where only approximate feature location information may be available. Therefore, desirable characteristics of the descriptive vector include: insensitivity (or independence) to global intensity scaling and image rotation, as well as tolerance to exact feature placement. One such descriptive vector that may be used is referred to as Local Binary Patterns Histograms (LBPH), and is described in Ojala, et al., Multiresolution gray-scale and rotation invariant texture classification with local binary patterns, IEEE Transactions on Pattern Analysis and Machine Intelligence 24, pp. 971-87, (2002), which is incorporated herein by reference. Any descriptive vector formulation with similar characteristics may be used within the scope of this invention. LBPH vectors are computed for each feature location and in each image in the training set. Subsequently, for each feature location, the mean LBPH feature vector is computed across all images.

[0152] When tracking a video, those facial features which are visible on a frame are determined. The feature location positions from the previous frame in the sequence are used as approximate locations for each feature and, for each approximate feature location, LBPH vectors are extracted as described above. Using a measure such as the Earth Movers distance, as described in Rubner, et al., A Metric for Distributions with Applications to Image Databases, Proceedings of the 1998 IEEE International Conference on Computer Vision, Bombay, India, January 1998, pp. 59-66, (1998), herein incorporated by reference, or Euclidian distance, the distance to the mean vector is computed for each feature. If the distance is within a threshold value, for example two standard deviations of the measure over the training data distribution, then the feature location is marked as visible, otherwise it is marked as invisible and excluded from the adaptive set.

Adaptive Feature Selection: Lighting Conditions

[0153] One embodiment of the invention deals with selecting only feature locations that are visible under the lighting conditions in which the video is being captured. Poor lighting conditions around specific features which lead to poor tracking performance are identifiable by local image regions with low variance in pixel intensity values. This corresponds visually to image areas that have either extremely high or extremely low illumination levels which wash out, or hide in shadow, the details of the image to be tracked. If local pixel intensity variance falls below a threshold for a feature location, then the feature is marked as invisible due to poor lighting conditions and is excluded from the adaptive set. The threshold can, for example, be based on the distribution of this variance measure over well-lit training data.

Adapting the Feature Locator Update Model

[0154] Once a set of adaptive feature locations has been chosen by one or more of the above methods, this information is incorporated into the feature locator update model formulation. Features not in the adaptive set should not influence the feature update vector. This is achieved by calculating the elements in the image sample vectors that are associated with feature points not in the adaptive set and pre-multiplying them with a weighting factor calculated to decrease their influence in the final matrix multiplication. This association is achieved by spatial proximity in shape-free space. (This refers to a selected norm defined within the “shape-normalized space,” discussed above, in which facial features are represented independently of global placement of the face in the field-of-view, or image space.) For example, the weighting vector can be a simple binary vector excluding samples that lie closest to feature points not in the adaptive set, or else the weighting vector may be bi-linearly interpolated based on distance between features in, and not in, the adaptive set, resulting in weighting vector elements between 0 and 1. This weighting vector is pre-multiplied, element by element, with the sample vector S before the application of the update model, Eqn. 1. A similar weighting pre-multiplication is performed over the shape vector [X]_2N×1, with weighting elements corresponding to features in the adaptive set having a value of 1 and all others a value of 0. With these modified input vectors, the update matrix equation produces an update vector containing modifications for all feature positions, including those that are not in the adaptive set. However, update vector elements for features not in the adaptive set are not derived from image data, rather they are derived from the implicit shape constraints encoded in the update matrix. This causes the tracking system to produce plausible locations for these features as the system iterates.

[0155] Samples associated with features not in the adaptive set are excluded from influencing the result of the update model, Eqn. 1, using the pre-weighting mechanism, and as the system will iterate to convergence based only on the information present in the image around the adaptive set of features. Feature locations not part of the training set and therefore not part of the update model are refined using a data-driven approach as stated above. These additional features can also influence the sample vector S by refining the mapping between image space and shape-normalised space. In this way, robustness to occluded and unobservable features is achieved and salient features specific to the subject are tracked. The output to the system is restricted to the adaptive set of features as only these have been derived from image data.

Predicting all Feature Locations in the Training Set

[0156] Expression measurement as described below is capable of proceeding using only the adaptive set of points derived above, however, it may be desirable to estimate the full set of feature locations in the training set for each frame or video despite only having measured an adaptive set of feature locations.

[0157] One embodiment of a predicting the complete set of features uses the “Projected Fitting” method described below, in which a non-linear 2D to 3D projective transform fitting process is performed to fitting a 3D model of the face to the adapted set of 2D feature locations. The 3D model of a face can contain annotations of the location of each of the training set of facial features, and this fitting can be used to read off the feature locations not in the adaptive set to produce a predicted complete the set of features.

[0158] In accordance with a further embodiment of the present invention, a statistical model may be constructed of correlation between the feature locations from training data, such as a principle component analysis (PCA) well known in the art, and then to use this statistical model to predict the unmeasured features from the adaptive set of features.

[0159] In accordance with yet a further embodiment of the present invention, implicit locations returned by the tracking system are used directly.

Measuring Expression

[0160] Measuring expression from tracked feature locations is performed in module 208 and is shown in detail in FIG. 12. The method employs an Expression Extractor 204 and has two processes, Calibrate Extractor If Required 1200 and Projected Fitting 1201. The calibration module ensures that expression measurements are not contaminated by varying subject identity and can therefore be used as a measure of absolute facial expression across subjects.

[0161] Expression extractor 204 is used to measure the current expression of the subject. FIG. 4 shows the structure of the extractor, which consists of two Expression Measurer objects; a Generic Subject Expression Measurer 400 and a Specific Individual Expression Measurer 401. Each measurer consists of a 3D model of facial shape and allowable shape variation, together with a set of fitting regularisation parameters. The extractor is represented as the variables:
Measurer={E₀,ξ₁, . . . ,ξ_n,λ₁^t, . . . ,λ₁^tλ₁^s, . . . ,λ₁^s}.
E₀ is a base-shape defined as a set of control points in 3D space, ξ₁, . . . ,λ_n is a set of n basic facial shape variation matrices, λ₁^t, . . . , λ_n^t is a set of temporal regularisation parameters and λ₁^s, . . . , λ_n^s a set of shape variation regularisation parameters which are used during projected fitting.

[0162] In accordance with preferred embodiments of the present invention, the base-shape represents an average facial shape with a neutral expression and the control points represent the same physical locations as the feature locations produced by the tracker. The position of these model control points can be manipulated to represent varying 3D facial shape of the subject. To allow this shape manipulation, a set of basic facial shape variation matrices ξ_i is used. The facial expression matrices represent the difference between the neutral facial shape and a particular target facial expression shape. They can be combined linearly with the base shape to produce a 3D representation of a face with a particular shape
y_m=E₀+Σ_ix_iξ_i  (Eqn. 4)
where x_i represents how much of each facial shape is present in the final model shape.

[0163] Matrices ξ_i can be constructed by hand or learned from data and can be tailored to the particular application of the system. In preferred embodiments, some of the matrices represent basic facial expressions and some represent facial shape variation associated with differences between subjects. In this way, by determining values for each x_i we measure the expression and identity parameters of the subject. The values of x can be visualised using a computer animated character with controls that correspond to the expressions of each ξ_i matrix. The control points of the measurer object correspond to a subset of the vertices of the character. Each character control recreates the displacements of an ξ_i matrix at these vertices along with displacements for all other vertices that correspond to the underlying physical facial expression. The controls combine in the same way as in Eqn. 4 to form a complete character expression. Construction of a character of this type, within the scope of the present invention, may employ any of the techniques known in the art or subsequently developed. FIGS. 14A-14C show examples of a measured facial expression, the black crosses show the tracked feature locations, the animated character displays the expression constructed from the measured vector x. FIG. 14A employs uncalibrated specific individual expression measurement, FIG. 14B employs generic subject expression and ID measurement, and FIG. 14C employs calibrated specific individual expression measurement, all in accordance with embodiments of the present invention.

Projected Fitting

[0164] An objective of certain embodiments of the present invention is to determine the position, orientation and expression of the 3D measurer model given the feature locations y and the previous model parameters x^t-1 if available. To do this, a projected fitting method is employed to position, orient and set the expression of the measurer to minimise the distance between the projected measurer control points and the feature locations in the image frame. In preferred embodiments, this process is achieved by solving the following equations:
x_opt=argmin_xΣΣ(f(x)−y)²+Σ_iλ_i^sx_i²+Σ_iλ₁^t(x_i−x_i^t-1)²,  (Eqn. 5)
subject to α_i≦x≦β_i,
where f(x) is a non-linear function mapping the vector of parameters to a matrix of 2D feature locations, λ^s is a vector of regularisation coefficients and λ^t is a vector of temporal regularisation coefficients for each parameter, x^t-1 is the vector of parameters from the previous frame of fitting and α_i,β_i are upper and lower bounds for each parameter. The vector of parameters is partitioned into two vector components, x=[x^t,x^e], where x^t represents the parameters of a transform function, x^e represents the expression and ID parameters, and f(x) represents the projection:
f(x)=f_{pro j}(X^t,E₀Σ_ix_i^eξ_i).  (Eqn. 6)

[0165] In a preferred embodiment, f_{pro j} is a non-linear 3D to 2D projective transform the form of which is well known in the art to which this invention pertains, for example as taught in Carlbom, et al., “Planar Geometric Projections and Viewing Transformations,” ACM Computing Surveys 10 (4): 465-502, (1978), doi:10.1145/356744.356750, incorporated herein by reference. The intrinsic parameters of this transform are assumed to be fixed and known a-priori and, as such, x^t contains only the six extrinsic translation and rotation parameters required to define the transform. The intrinsic parameters can be determined and fixed either by direct estimation or from camera characteristics, using any of the well-known methods in the prior art, a review of which is provided by T. A. Clarke and J. G. Fryer, “The Development of Camera Calibration Methods and Models,” Photogrammetric Record, 16(91): 51-66, (1998), which is incorporated herein by reference. In the preferred embodiment, basic assumptions are made as to the likely intrinsic parameters of a consumer web-camera or mobile device camera. Due to the relatively planar aspect of the tracked facial features in proportion to the distance of the face from the camera, intrinsic projective parameters are not critical to the final fit and our fixed assumptions have been found to be sufficient to produce accurate expression estimates. The function in Eqn. 6 describes the fitting of a 3D model to a set of 2D data. This solution is inherently under determined and the model may have more degrees of freedom than there are constraints available in the input data. For these reasons, the temporal and parameter regularisation components are essential to achieve a stable system of measurement. The system of equations of the type defined in Eqn. 5 can be solved by standard constrained non-linear optimisation techniques, for example, as taught by Nocedal et al., “Numerical Optimization”, (Springer-Verlag, 1999). In a preferred embodiment, a Gauss-Newton approach is used, with constraints imposed using Quadratic Programming, for example, as taught by Nocedal et al., “Numerical Optimization, Chapter 18 Sequential Quadratic Programming” Springer-Verlag, 1999. FIGS. 14A-14C show examples of fitted measurer models, the black crosses show the tracked feature locations y, the light grey crosses show the resulting fitted projected points f(x_opt), and the animated character displays the expression constructed from the measured vector x_opt.

[0166] To obtain an accurate measurement of the expression of a subject, the foregoing measure is normalized with respect to the individual's identity. This is achieved by module 1200, now discussed with reference to FIGS. 12 and 13. The process can be triggered either automatically, for example on the first frame of analysis, or by user request. During this process, it is desirable that the subject faces the camera and adopts a neutral facial expression.

[0167] It is assumed that the individual's identity is determined by their 3D facial shape at a neutral facial expression. The calibration process shown in FIG. 13 determines this shape using Generic Subject Expression Measurer 400 in module 1201 and uses the outcome to produce Specific Individual Expression Measurer 401 in module 1300. In a preferred embodiment, the parameter regression parameters in the Generic Measurer 400 are tailored to allow identity shape variation parameters to be modified with less regularisation than expression, and setting the temporal parameters to λ_i^t=0 removes the influence of the previous frame of the measurement process. This takes into account the identity variation of the subject and allows for small expression variation from neutral in the subject's appearance to be taken into account which is beneficial in a real-world application. It also allows new subjects to calibrate the extractor without being influenced by results from previous subjects.

[0168] With further reference to FIG. 13, module 1300 uses the results of projected fitting of the generic measurer to fix the identity of the specific measurer. Using Eqn. 4 and the results of the generic measure fitting X_opt,generic, the 3D shape of the subject's neutral expression can be determined as y_m,generic. The specific individual measure is modified to have a base-shape equal to this neutral face shape: E_0,specific=y_m,generic. The Specific Individual measurer 401 shape variation matrices ξ_i can be predetermined and fixed or can also be adjusted by a suitable transform to take into account the individual's neutral face shape. In a preferred embodiment, the matrices are fixed a-priori and do not contain any identity-based shape variation. As such, only expression measurements are returned from the specific individual measurer. The temporal regularization parameters of the specific individual measurer λ^t are chosen to produce smoothly varying expression measurements and the shape variation regularization parameters λ^s are chosen to give less regularization to common facial expressions.

[0169] The separation of the measurement of an individual's identity and expression during this calibration process ensures that expression measurements produced by module 208 are not contaminated by varying subject identity. These measurements can therefore be used as a reliable measure of absolute facial expression across subjects. FIG. 14A shows measured expression from an un-calibrated specific individual measurer, FIG. 14B shows the fitted generic measurer and FIG. 14C shows the expression from the resulting calibrated specific measurer. Note how the measured expression in FIG. 14A is not neutral and does not match that of the subject, however after calibration in FIG. 14C the measured expression is more neutral and matches the subject more accurately.

Devices

[0170] Embodiments of the present invention may be used, performed, or instantiated, as the case may be, on a variety of devices. Some of these devices, designated generically by numeral 1800, are depicted in FIG. 18, without limitation, and by way of example. As shown in the figure, examples of such a device are, but are not limited to, personal computers 1803, laptops 1804, tablet computers 1801, smart phones 1802, smart TVs 1806 and any other camera-equipped device 1805 with suitable processing hardware. Typically the processor in a basic modern smart phone is all that is required to extract facial location and expression measurement data at over 30 frames per second.

Expression Analysis for Measuring Reaction to Pre-Rendered and Dynamically Generated Display Content

[0171] Measuring the emotional reaction of a subject 102 to a piece of pre-rendered or dynamically rendered display content 1902 is now described with reference to FIG. 19. Such measurement provides an extremely valuable source of information. For example, facial location and expression data 1908 can be used to measure the effectiveness of an advertising or other video presentation, where effectiveness is measured on the basis of a specified criterion. A further application includes measurement of the reaction of trial users to features during software design. One embodiment of the present invention allows the extraction of expression measurements 1908 from pre-rendered content 1902 and their storage in a way that will allow subsequent recall and analysis. In accordance with the embodiment depicted in FIG. 19, pre-rendered content 1902 is delivered to a device's display 1904 from local or remote storage 1900. Subject 102 views the display 1904 and a video of their facial reactions are captured by camera 1906. The video is analysed by the tracking and expression measurement system 205 described above, and the facial location and expression data 1908 that is produced is logged in a local or network storage device 1900 in such a way that it can be associated with the instant of the pre-rendered content 1902 that was being displayed at the reaction time. The communications and data storage required by this system will be obvious to one skilled in the art.

[0172] Particular embodiments of the present invention, provided solely by way of example and without limitation, include instances in which pre-rendered content 1902 is in the form of a video or image advertisement and the expression information 1908 is used to assess the emotional reaction of subject 102 to the advertisement. Another exemplary application of an embodiment as described with reference to FIG. 19 may entail the form of a particular television program, where the expression and tracking information 1908 may be used to assess the presence or absence of individuals and their level of attention to the broadcast, such as to derive measures for the purposes of TV analytics.

[0173] Expression measurements from dynamically generated content may also be stored in a way that will allow subsequent recall and analysis, as now described with reference to FIG. 20. In accordance with such embodiments of the present invention, dynamically generated display content 2000 is delivered to a display 2002. Subject 102 views the display, and a video of their facial reactions is captured by camera 2004. The video is analysed by the tracking and expression measurement system 205 as described above, and the facial location and expression data 2006 that is produced is logged in a local or network storage device 2008 in such a way that it can be associated with the characteristics of the dynamically rendered content that was being displayed at the reaction time The communications and data storage required by this system will be obvious to one skilled in the art. In one embodiment of the above system, the dynamically rendered content may be in the form of a software application running on the device 1800 and the facial tracking and expression measurements 1908 allow the analysis of emotional reaction to the software and areas of the display where attention is most closely focused.

Avatar Animation

[0174] In accordance with other embodiments of the present invention, facial expression measurements, extracted as described above, may be employed to produce real-time avatar animation from an individual's facial performance in an unconstrained consumer environment, shown as module 1500 in FIG. 15. The expression measurement process produces identity-independent parameters which can be mapped onto an avatar to faithfully reproduce an individual subject's performance. If the identity of the subject were to be left to contaminate the expression measurements, the final avatar animation could be distorted in an undesirable way.

[0175] The creation of avatar animation contains several sub-modules. As the expression measurements are an abstract representation of the configuration of a subject's facial expression, the target avatar is not constrained to have a physical correspondence or similarity with the subjects face shape. First, target avatar 1501 implements a set of controls allowing its shape to vary. These controls need not be the same number or meaning as the expression measurements. The expression measurements are transformed onto the avatar control set in module 1502. This transform can be implemented by any appropriate mapping function. In our preferred embodiment this is a linear matrix which maps, combines and scales expression measurements onto avatar control values. This matrix can be hand crafted to implement desired stylistic animation characteristics such as exaggerated expressions for cartoon characters. If a simple linear relationship is not sufficiently expressive to meet this requirement, any other transform method could be used, as described, for example, in U.S. Pat. No. 8,026,917. The output of module 1502 is a set of avatar animation values 1503, which are used to set the shape of the final avatar. Examples of the output of this process are shown in FIGS. 16A-16D. Here, the same individual's expression is mapped onto avatars with widely varying facial structure and 3D geometry. Applying the animation process to each frame of a performance in real-time results in an avatar animation that synchronises with, and faithfully reproduces, the facial expression of the subject.

[0176] In a performance capture scenario, the ability to visualize an actor's performance on an animated character in real-time is a valuable source of information to assist the director's understanding of the likely appearance of the final animation. A further embodiment of the current invention can be used to create avatar animation for use as a performance driven animation pre-visualization system. FIG. 21 illustrates this embodiment where a subject's 102 performance is captured and the video sent by local or network communication to a device 1800 where it is analysed by the tracking and analysis system 205. The resulting expression measurements are sent to a display device which calculates avatar animation values using module 1500 and displays the resulting animation. In another embodiment of the above system the tracking, analysis, animation rendering and display are performed on the same device.

Animation Messaging and Chat

[0177] As the prevalence of communication equipment with cameras has grown, the use of images and video of faces for communication has become commonplace. These visual communications may be one-to-one (images/video messaging and video chat) or one-to-many (video conferencing, publication of images or videos on sharing or social network sites). Situations exist where the users may wish to replace their own facial image with that of an animated avatar while retaining the benefit of visual face-to-face communication; to maintain their anonymity or entertain the recipient. FIG. 22 shows an animation messaging system which replaces the video of the sender with a rendered animation of an avatar performing the same facial expressions and movement to coincide with the audio. A device 1800 uses a tracking and analysis system 205 to track the features of the subject 102 in a captured video and generates an image or video of an avatar 2202. The video message containing the animated avatar is stored on the sender's device or on the local or networked storage. This message is then retrieved by one or more recipient devices for display.

[0178] Another embodiment of the invention, illustrated in FIG. 23, shows a real-time video chat system where video content of the subject 102 is replaced by video content of an animated avatar. The subject's device captures the video and performs the tracking, analysis and avatar animation in real-time. The avatar animation data 2304 is streamed in real-time over a network 2204 to one or many recipient devices for display. The recipient devices may also include tracking and avatar animation modules to allow multi user avatar chat communication. Still further embodiments involve similar systems as above but where the tracking and animation components take place on the recipients device.

[0179] Various aspects of the invention may also be implemented as specialized software executing in a general-purpose computer system 600 such as that shown in FIG. 17. Alternatively, aspects of the present invention are advantageously implemented on mobile phones, tablets, and other devices. The computer system 600 may include a database server 603 connected to one or more memory devices 604, such as a disk drive, memory, or other device for storing data. Database server 603 stores an investor portfolio comprising a plurality of assets, or other data to which the present invention may be applied A processor 607 (also referred to herein as a central processing unit, or processing server) 605 contains computer-executable software configured to derive a threshold as taught in the foregoing description. Memory 604 is typically used for storing programs and data during operation of the computer system 600. Components of computer system 600 may be coupled by an interconnection mechanism 605, which may include one or more busses (e.g., between components that are integrated within a same machine) and/or a network (e.g., between components that reside on separate discrete machines). The interconnection mechanism 605 enables communications (e.g., data, instructions) to be exchanged between system components of system 600. Computer system 600 also includes one or more input devices 602, for example, a keyboard, mouse, trackball, microphone, touch screen, and one or more output devices 601, for example, a printing device, display screen, speaker. In addition, computer system 600 may contain one or more interfaces (not shown) that connect computer system 600 to a communication network (in addition or as an alternative to the interconnection mechanism).

[0180] The computer system may include specially-programmed, special-purpose hardware, for example, an application-specific integrated circuit (ASIC). Aspects of the invention may be implemented in software, hardware or firmware, or any combination thereof. Further, such methods, acts, systems, system elements and components thereof may be implemented as part of the computer system described above or as an independent component.

[0181] Although computer system 600 is shown by way of example as one type of computer system upon which various aspects of the invention may be practiced, it should be appreciated that aspects of the invention are not limited to being implemented on the computer system as shown in FIG. 17. Various aspects of the invention may be practiced on one or more computers having a different architecture or components than that shown in FIG. 17.

[0182] Processors 607 and operating systems employed in conjunction with servers 603 and 605 define a computer platform for which application programs in high-level programming languages are written. It should be understood that the invention is not limited to a particular computer system platform, processor, operating system, or network. Also, it should be apparent to those skilled in the art that the present invention is not limited to a specific programming language or computer system. Further, it should be appreciated that other appropriate programming languages and other appropriate computer systems could also be used.

[0183] One or more portions of the computer system may be distributed across one or more computer systems (not shown) coupled to a communications network. These computer systems also may be general-purpose computer systems. For example, various aspects of the invention may be distributed among one or more computer systems configured to provide a service (e.g., servers) to one or more client computers, or to perform an overall task as part of a distributed system. For example, various aspects of the invention may be performed on a client-server system that includes components distributed among one or more server systems that perform various functions according to various embodiments of the invention. These components may be executable, intermediate, or interpreted code which communicate over a communication network (e.g., the Internet) using a communication protocol (e.g., TCP/IP).

[0184] It should be appreciated that the invention is not limited to executing on any particular system or group of systems. Also, it should be appreciated that the invention is not limited to any particular distributed architecture, network, or communication protocol.

[0185] Having now described some illustrative embodiments of the invention, it should be apparent to those skilled in the art that the foregoing is merely illustrative and not limiting, having been presented by way of example only. Numerous modifications and other illustrative embodiments are within the scope of one of ordinary skill in the art and are contemplated as falling within the scope of the invention. In particular, while descriptions have been provided in terms of capturing facial movements, they are not limited to this context. The procedures are applicable to a wide variety of tracking problems.

[0186] Moreover, where examples presented herein involve specific combinations of method acts or system elements, it should be understood that those acts and those elements may be combined in other ways to accomplish the same objective of automatic measurement of facial expression. Acts, elements and features discussed only in connection with one embodiment are not intended to be excluded from a similar role in other embodiments.

[0187] Use of ordinal terms such as “first”, “second”, “third”, etc., in the claims to modify a claim element does not by itself connote any priority, precedence, or order of one claim element over another or the temporal order in which acts of a method are performed, but are used merely as labels to distinguish one claim element having a certain name from another element having a same name (but for use of the ordinal term) to distinguish the claim elements. Additionally, single device features may fulfill the requirements of separately recited elements of a claim.