# Patent

## Title
Optimal gradient pursuit for image alignment

## Abstract

A method for image alignment is disclosed. In one embodiment, the method includes acquiring a facial image of a person and using a discriminative face alignment model to fit a generic facial mesh to the facial image to facilitate locating of facial features. The discriminative face alignment model may include a generative shape model component and a discriminative appearance model component. Further, the discriminative appearance model component may have been trained to estimate a score function that minimizes the angle between a gradient direction and a vector pointing toward a ground-truth shape parameter. Additional methods, systems, and articles of manufacture are also disclosed.

## Background
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH & DEVELOPMENT
This invention was made with Government support under grant number 2007-DE-BX-K191 awarded by the National Institute of Justice. The Government has certain rights in the invention.


BACKGROUND
The present disclosure relates generally to image alignment and, in some embodiments, to a technique for aligning facial images.
Model-based image registration/alignment is a topic of interest in computer vision, where a model is deformed such that its distance to an image is minimized. In particular, face alignment is of interest as it enables various practical capabilities (e.g., facial feature detection, pose rectification, and face animation) and poses scientific challenges due to facial appearance variations in pose, illumination, expression, and occlusions. Previous techniques include the Active Shape Model (ASM), which fit a statistical shape model to an object class. ASM was extended to the Active Appearance Model (AAM), which has been used in face alignment. During AAM-based model fitting, the Mean-Square-Error between the appearance instance synthesized from the appearance model and the warped appearance from the input image is minimized by iteratively updating the shape and/or appearance parameters. Although AAM may perform reasonably well while learning and fitting on a small set of subjects, its performance degrades quickly when it is trained on a large dataset and/or fit to subjects that were not seen during the model learning.
In addition to the generative model based approaches such as AAM, there are also discriminative model based alignment approaches. The Boosted Appearance Model (BAM) utilizes the same shape model as AAM, but an entirely different appearance model that is essentially a two-class classifier and learned discriminatively from a set of correctly and incorrectly warped images. During model fitting, BAM aims to maximize the classifier score by updating the shape parameter along the gradient direction. Though BAM has shown to generalize better in fitting to unseen images compared to AAM, one potential issue is that the learned binary classifier cannot guarantee a concave score surface while perturbing the shape parameter. In other words, moving along the gradient direction does not always improve the alignment. The Boosted Ranking Model (BRM) alleviates this issue by enforcing the convexity through learning. Using pairs of warped images, where one is a better alignment than the other, BRM learns a score function that attempts to correctly rank the two warped images within all training pairs. While BRM may provide certain benefits over previous techniques, further improvements in image alignment may be achieved as described below.
BRIEF DESCRIPTION
Certain aspects commensurate in scope with the originally claimed invention are set forth below. It should be understood that these aspects are presented merely to provide the reader with a brief summary of certain forms various embodiments of the presently disclosed subject matter might take and that these aspects are not intended to limit the scope of the invention. Indeed, the invention may encompass a variety of aspects that may not be set forth below.
Embodiments of the presently disclosed subject matter may generally relate to image alignment. In one embodiment, a method includes acquiring a facial image of a person and using a discriminative face alignment model to align a generic facial mesh to the facial image to facilitate locating of facial features of the facial image. The discriminative face alignment model may include a generative shape model component and a discriminative appearance model component. The discriminative appearance model component may have been trained with training data to estimate a score function that is a function of a shape parameter of a given image and that seeks to minimize an angle between a gradient direction of the score function for the shape parameter and an ideal alignment travel direction for the shape parameter.
In another embodiment, a system includes a memory device having a plurality of stored routines and a processor configured to execute the plurality of stored routines. The plurality of stored routines may include a routine configured to access a set of training images, and a routine configured to train an appearance model using the set of training images to learn an alignment score function that minimizes angles between gradient directions of the alignment score function and ideal travel directions to a desired alignment.
In an additional embodiment, a manufacture includes one or more non-transitory, computer-readable media having executable instructions stored thereon. The executable instructions may include instructions adapted to access an image including a human face and instructions adapted to align the human face using a discriminative face alignment model. The discriminative face alignment model may include a discriminative appearance model trained to estimate an alignment score function that minimizes angles between gradient directions of the alignment score function and vectors pointing in the direction of the maximum of the alignment score function.
Various refinements of the features noted above may exist in relation to various aspects of the subject matter described herein. Further features may also be incorporated in these various aspects as well. These refinements and additional features may exist individually or in any combination. For instance, various features discussed below in relation to one or more of the illustrated embodiments may be incorporated into any of the described embodiments of the present disclosure alone or in any combination. Again, the brief summary presented above is intended only to familiarize the reader with certain aspects and contexts of the subject matter disclosed herein without limitation to the claimed subject matter.



DRAWINGS
These and other features, aspects, and advantages of the present technique will become better understood when the following detailed description is read with reference to the accompanying drawings in which like characters represent like parts throughout the drawings, wherein:
FIG. 1 is a face shape template in accordance with an embodiment of the present disclosure;
FIG. 2 depicts an example of a concave alignment score function learned via BRM;
FIG. 3 depicts an alignment score function in which gradient directions are more closely aligned with ideal travel directions in accordance with an embodiment of the present disclosure;
FIG. 4 is an example of an observation image and a face image warped utilizing the face shape template in accordance with an embodiment of the present disclosure;
FIG. 5 is an example of a warped face image with feature parameterization in accordance with an embodiment of the present disclosure;
FIG. 6 depicts examples of rectangular feature types that may be used by an appearance model in accordance with an embodiment of the present disclosure;
FIG. 7 is an example of a feature template in accordance with an embodiment of the present disclosure;
FIG. 8 generally depicts a process for estimating an alignment score function in accordance with an embodiment of the present disclosure;
FIGS. 9 and 10 depict the top fifteen Haar features selected by a learning algorithm in accordance with an embodiment of the present disclosure;
FIG. 11 is a spatial density map of the top one hundred Haar features selected by the learning algorithm of FIGS. 8 and 9 in accordance with an embodiment of the present disclosure;
FIGS. 12-14 are example images from three datasets in accordance with an embodiment of the present disclosure;
FIG. 15 is a graph comparing the ranking performance of the learning algorithm of an embodiment of the present disclosure with that of BRM;
FIG. 16 is a graph comparing angle estimation performance of the learning algorithm of an embodiment of the present disclosure with that of BRM;
FIG. 17 is a graph comparing alignment speed performance of the learning algorithm of an embodiment of the present disclosure with that of BRM; and
FIG. 18 is an example of a facial analysis process in accordance with an embodiment of the present disclosure; and
FIG. 19 is a block diagram of a processor-based device or system for providing the functionality described in the present disclosure and in accordance with an embodiment of the present disclosure.



DETAILED DESCRIPTION
One or more specific embodiments of the presently disclosed subject matter will be described below. In an effort to provide a concise description of these embodiments, all features of an actual implementation may not be described in the specification. It should be appreciated that in the development of any such actual implementation, as in any engineering or design project, numerous implementation-specific decisions must be made to achieve the developers' specific goals, such as compliance with system-related and business-related constraints, which may vary from one implementation to another. Moreover, it should be appreciated that such a development effort might be complex and time consuming, but would nevertheless be a routine undertaking of design, fabrication, and manufacture for those of ordinary skill having the benefit of this disclosure. When introducing elements of various embodiments of the present techniques, the articles “a,” “an,” “the,” and “said” are intended to mean that there are one or more of the elements. The terms “comprising,” “including,” and “having” are intended to be inclusive and mean that there may be additional elements other than the listed elements.
Image alignment is the process of moving and deforming a landmark-based generic mesh to an image (e.g., a facial image) to allow image features (e.g., facial features) to be located accurately. Some alignment models include a shape model component and an appearance model component. Given an image, landmark points may be located to quantify the shape of the image. In facial image alignment, for example, the shape model may include landmark points which correspond to facial features (e.g., tip of nose, corners of mouth, etc.). An example mean shape 10, as illustrated in FIG. 1, may include a number of triangles 12 defined by landmark points 14 and line segments 16.
The appearance model may generally include a learned alignment score function, as generally represented in FIGS. 2 and 3. An example of an alignment score function learned through BRM is generally illustrated as graph 20 in FIG. 2. In this concave function, a ground-truth shape parameter 22 represents a maximum value 24 of the function (i.e., a desired alignment), while each line 26 represents points of equal magnitude to the other points on the respective line 26. The score for various perturbed shape parameters 28 are graphed as elements 30 with gradient directions 32. But in BRM a gradient direction 32 can still have a relatively large angle 36 with respect to a vector 34 pointing to the ground-truth shape parameter 22 (i.e., value 24) starting from the current shape parameter element 30. Hence, while in BRM the shape parameter may be updated along the gradient direction 32, the alignment process in BRM may take a convoluted path during the optimization due to the relatively large angles 36. This not only increases the chances of divergence, but also slows down the alignment.
To address this issue, one embodiment of the present technique instead uses the Optimal Gradient Pursuit Model (OGPM) described below to learn a discriminative alignment model also including shape and appearance model components. Using the same shape representation as BAM and BRM, the learning of the OGPM appearance model component, which is also an alignment score function, is formulated with a very different objective. Particularly, as generally represented by graph 40 in FIG. 3, the appearance model aims to learn an alignment score function whose gradients 32 at various perturbed shape parameters 28 (graphically represented by reference numerals 30) have the minimal angle 36 with respect to the ideal travel direction (i.e., the vector 34 pointing directly to the ground-truth shape parameter). The score function may include or be composed of a set of weak functions, each operating on one local feature in the warped image domain. The objective function is formulated such that each weak function can be estimated in an incremental manner from a large pool of feature candidates. During the model fitting, given an image with an initial shape parameter, gradient ascent is performed by updating the shape parameter in the gradient direction, which in OGPM is expected to be more similar to the ideal travel direction due to the optimization of the angles 36 between the gradients 32 and the vectors 34. Additional details of the presently disclosed alignment model are provided below. While certain embodiments relating to a face model and facial alignment are described below for the sake of explanation, it is again noted that the use of the models and alignment techniques in other image contexts (i.e. non-facial) is also envisaged.
Face Model
Similar to BAM and BRM, a face model of one embodiment is composed of or includes a generative shape model component and a discriminative appearance model component. With respect to the shape model, it is noted that landmark-based shape representation is a popular way to describe the facial shape of an image. That is, a set of 2D landmarks, (xi,yi)i=1, . . . , v, may be placed on top of key facial features, such as eye corner, mouth corner, and nose tip, for example. The concatenation of these landmarks forms shape observations of an image, s=[x1, y1, x2, y2, . . . , xv, yv]T. Given a face database where each image is manually labeled with landmarks, the entire set of shape observations may be treated as the training data for the shape model. In one embodiment, the shape model may be a Point Distribution Model (PDM) learned via Principal Component Analysis (PCA) on the observation set. Thus, the learned generative PDM can represent a particular shape instance as:




  
    
      
        
          
            s
            ⁡
            
              (
              p
              )
            
          
          =
          
            
              s
              0
            
            +
            
              
                ∑
                
                  i
                  =
                  1
                
                n
              
              ⁢
              
                
                  p
                  i
                
                ⁢
                
                  s
                  i
                
              
            
          
        
        ,
      
    
    
      
        (
        1
        )
      
    
  




where s0 and si are the mean shape and ith shape basis, respectively, resulting from the PDM learning. The shape parameter may be given by p=[p1, p2, . . . , pn]T. Similar to the shape component of AAM, the first four shape bases may be trained to represent global translation and rotation, while the remaining shape bases may represent the non-rigid deformation of facial shapes.

As shown in FIG. 4, a warping function 48 from the mean shape coordinate system to the coordinates in the image observation 52 is defined as a piece-wise affine warp:

W(x0·y0:p)=[1x0y0]a(p),  (2)

where (x0,y0) is a pixel coordinate 46 within the mean shape domain, and a(p)=[a1(p)a2(p)] is a unique 3×2 affine transformation matrix that relates each triangle pair in s0 and s(p). Given a shape parameter p, a(p) may be computed for each triangle 12. However, since the knowledge of which triangle each pixel (x0,y0) belongs to is known a priori, the warp can be efficiently performed via a simple table lookup. Using this warping function 48, any face image 52 can be warped 54 into the mean shape (generally represented for one pixel by reference numerals 50 and 56) and results in a shape-normalized face image I(W(x; p)), generally represented by reference numeral 58, from which the appearance model is learned.

One embodiment of the appearance model may be better understood with reference to FIGS. 5-7. Particularly, FIG. 5 depicts an example of a warped image 70 having a parameterized feature 72. FIG. 6 depicts five feature types 74 (individually labeled as feature types 76, 78, 80, 82, and 84) that may be used by the appearance model. Further, FIG. 7 generally represents a notional image template A (reference numeral 92).
The appearance model of one embodiment is described by a collection of m local features {φi}i=1, . . . , m that are computed on the shape-normalized face image I(W(x; p)). The local features of one embodiment may be Haar-like rectangular features (e.g., feature 72), which may provide benefits with respect to computational efficiency (e.g., due to an integral image technique). A rectangular feature can be computed as follows:

φ{dot over (=)}ATI(W(x:p));  (3)

where A is an image template 92. The inner product between the template and the warped image is equivalent to computing the rectangular feature using the integral image. As shown in FIG. 5, the image template A can be parameterized by (α, β,γ, δ, τ), where (α,β) is the top-left corner, γ and δ are the width and height, and τ is the feature type 74.

Alignment Learning

Having introduced the appearance model representation, we now turn to how to train an appearance model of the present technique. In one embodiment, the appearance model may include, or consist of, an alignment score function that will be used during the model fitting stage. To begin with, p may be denoted as the shape parameter of a given image that represents the current alignment of the shape model of Equation (1). In one embodiment, the goal of appearance model learning may be stated as: From labeled training data, we aim to learn a score function F(p), such that, when maximized with respect to p, it will result in the shape parameter of the correct alignment. Specifically, using this goal, if p0 is the shape parameter corresponding to the correct alignment of an image, F has to be such that




  
    
      
        
          p
          0
        
        =
        
          arg
          ⁢
          
            
          
          ⁢
          
            
              max
              p
            
            ⁢
            
              
            
            ⁢
            
              
                F
                ⁡
                
                  (
                  p
                  )
                
              
              .
            
          
        
      
    
    
      
        (
        4
        )
      
    
  




Given the above equation, F(p) may be optimized via gradient ascent. That is, by assuming that F is differentiable, the shape parameter may be iteratively updated in each alignment iteration starting from an initial parameter p(0)




  
    
      
        
          
            p
            
              (
              
                i
                +
                1
              
              )
            
          
          =
          
            
              p
              
                (
                i
                )
              
            
            +
            
              λ
              ⁢
              
                
                  ∂
                  F
                
                
                  ∂
                  p
                
              
            
          
        
        ,
      
    
    
      
        (
        5
        )
      
    
  




where λ is a step size. After k iterations when the alignment process converges, the alignment is considered successful if the Euclidean distance ∥p(k)−p0∥ is less than a pre-defined threshold.

From Equation (5), it is clear that




  
    ∂
    F
  
  
    ∂
    p
  




indicates the travel direction of the shape parameter p. Because the final destination of such traveling is p0, the ideal travel direction should be the vector that points to p0 starting from p, which is denoted as {right arrow over (p)}:





  
    
      
        
          
            p
            →
          
          +
        
        ⁢
        
          =
          .
        
        ⁢
        
          
            
              
                p
                0
              
              -
              p
            
            
              
              
                
                  p
                  0
                
                -
                p
              
              
            
          
          .
        
      
    
    
      
        (
        6
        )
      
    
  




Similarly, the worst travel direction is the opposite direction of {right arrow over (p)}+, i.e., {right arrow over (p)}−=−{right arrow over (p)}+. Hence, during the learning of the score function F, it is desired that





  
    ∂
    F
  
  
    ∂
    p
  




has a direction that is as similar to the ideal travel direction {right arrow over (p)}+ as possible, or equivalently, as dissimilar to the worst travel direction {right arrow over (p)}− as possible. Specifically, if we define a classifier





  
    
      
        
          
            H
            ⁡
            
              (
              
                p
                ;
                
                  p
                  →
                
              
              )
            
          
          =
          
            
              
                
                  ∂
                  F
                
                
                  ∂
                  p
                
              
              
                
                
                  
                    ∂
                    F
                  
                  
                    ∂
                    p
                  
                
                
              
            
            ⁢
            
              p
              →
            
          
        
        ,
      
    
    
      
        (
        7
        )
      
    
  




which is the inner product between two unit vectors and is also the cosine response of the angle between these two vectors, then we have





  
    
      
        
          H
          ⁡
          
            (
            
              p
              ;
              
                p
                →
              
            
            )
          
        
        =
        
          {
          
            
              
                
                  +
                  1
                
              
              
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      
                        p
                        →
                      
                    
                    =
                    
                      
                        p
                        →
                      
                      +
                    
                  
                  ,
                
              
            
            
              
                
                  -
                  1
                
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    
                      p
                      →
                    
                  
                  =
                  
                    
                      
                        p
                        →
                      
                      -
                    
                    .
                  
                
              
            
          
        
      
    
    
      
        (
        8
        )
      
    
  




In practice, it is hard to expect H(p) can always equal to 1 or −1 as shown in the above equation. Thus, the objective function of learning the H classifier may be formulated as,





  
    
      
        
          arg
          ⁢
          
            
          
          ⁢
          
            
              min
              F
            
            ⁢
            
              
                ∑
                p
              
              ⁢
              
                
                  (
                  
                    
                      H
                      ⁡
                      
                        (
                        
                          p
                          ;
                          
                            
                              p
                              →
                            
                            +
                          
                        
                        )
                      
                    
                    -
                    1
                  
                  )
                
                2
              
            
          
        
        ,
      
    
    
      
        (
        9
        )
      
    
  




where only the ideal travel direction {right arrow over (p)}+ is used since it can represent the constraint from {right arrow over (p)}− as well. From here on, {right arrow over (p)}+ will be simplified as {right arrow over (p)} for clarity. This objective function essentially aims to estimate a function F such that its gradient direction has minimal angle with respect to the ideal travel direction, at all possible shape parameters p for all training data.

In one embodiment, a solution in minimizing the objective function (9) may be provided in the manner depicted in FIG. 8 and as described below. First, let us assume the alignment score function uses a simple additive model:




  
    
      
        
          
            F
            ⁡
            
              (
              
                p
                ;
                m
              
              )
            
          
          ⁢
          
            =
            .
          
          ⁢
          
            
              
                ∑
                
                  i
                  =
                  1
                
              
              m
            
            ⁢
            
              
                f
                i
              
              ⁡
              
                (
                p
                )
              
            
          
        
        ,
      
    
    
      
        (
        10
        )
      
    
  




where ƒi(p) is a weak function that operates on one rectangular feature φi. Therefore, the gradient of F is also in an additive form:





  
    
      ∂
      
        F
        ⁡
        
          (
          
            p
            ;
            m
          
          )
        
      
    
    
      ∂
      p
    
  
  =
  
    
      ∑
      
        i
        =
        1
      
      m
    
    ⁢
    
      
        
          ∂
          
            f
            i
          
        
        
          ∂
          p
        
      
      .
    
  




By plugging this into Equation (7), we have:





  
    
      
        
          
            
              
                H
                ⁡
                
                  (
                  
                    
                      p
                      ;
                      
                        p
                        →
                      
                    
                    ,
                    m
                  
                  )
                
              
              =
              
              ⁢
              
                
                  
                    
                      ∑
                      
                        i
                        =
                        1
                      
                      m
                    
                    ⁢
                    
                      
                        ∂
                        
                          f
                          i
                        
                      
                      
                        ∂
                        p
                      
                    
                  
                  
                    
                    
                      
                        ∑
                        
                          i
                          =
                          1
                        
                        m
                      
                      ⁢
                      
                        
                          ∂
                          
                            f
                            i
                          
                        
                        
                          ∂
                          p
                        
                      
                    
                    
                  
                
                ⁢
                
                  p
                  →
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  
                    
                      
                        H
                        ⁡
                        
                          (
                          
                            
                              p
                              ;
                              
                                p
                                →
                              
                            
                            ,
                            
                              m
                              -
                              1
                            
                          
                          )
                        
                      
                      ⁢
                      
                        
                        
                          
                            ∂
                            
                              F
                              ⁡
                              
                                (
                                
                                  p
                                  ;
                                  
                                    m
                                    -
                                    1
                                  
                                
                                )
                              
                            
                          
                          
                            ∂
                            p
                          
                        
                        
                      
                    
                    +
                    
                      
                        
                          ∂
                          
                            f
                            m
                          
                        
                        
                          ∂
                          p
                        
                      
                      ⁢
                      
                        p
                        →
                      
                    
                  
                  
                    
                    
                      
                        
                          ∂
                          
                            F
                            ⁡
                            
                              (
                              
                                p
                                ;
                                
                                  m
                                  -
                                  1
                                
                              
                              )
                            
                          
                        
                        
                          ∂
                          p
                        
                      
                      +
                      
                        
                          ∂
                          
                            f
                            m
                          
                        
                        
                          ∂
                          p
                        
                      
                    
                    
                  
                
                .
              
            
          
        
      
    
    
      
        (
        11
        )
      
    
  




Given the fact that H function can be written in a recursive fashion, incremental estimation may be used to minimize the objective function (9). That is, by defining a set of training samples and a hypothesis space from which the rectangle feature can be chosen, each weak function ƒi may be iteratively estimated and incrementally added into the target function F. Additional details of the example parts of a learning process of one embodiment are described below.

In the appearance learning of one embodiment, a training sample is an N-dimensional warped image I(W(x; p)). Given a face database {Ii}Iε[1,K] with manually labeled landmarks {si}, for each face image Ii, Equation (1) may be used to compute the ground-truth shape parameter p0,i, and then synthesize a number of “incorrect” shape parameters {pj,i}jε[1,U] by random perturbation. Equation (12) below describes one example of perturbation, where v is a n-dimensional vector with each element uniformly distributed within [−1,1], μ is the vectorized eigenvalues of all shape bases in the PDM, perturbation index σ is a constant scale that controls the range of perturbation, and ∘ represents the entrywise product of two equal-length vectors.

pj,i=pi+σv∘μ.  (12)

Then, the set of warped images Ii(W(x; pj,i)) may be treated as positive training samples (yi=1) for the learning. Together with the ideal travel direction, this may constitute our training set:

{dot over (=)}{Ii(W(x:pj,i)), {right arrow over (p)}i}i=1, . . . , K:j=1, . . . , U.  (13)

In one embodiment, the weak function ƒi is defined as:




  
    
      
        
          
            f
            i
          
          ⁡
          
            (
            p
            )
          
        
        ⁢
        
          =
          .
        
        ⁢
        
          
            2
            π
          
          ⁢
          
            
              arctan
              ⁡
              
                (
                
                  
                    
                      g
                      i
                    
                    ⁢
                    
                      
                        φ
                        i
                      
                      ⁡
                      
                        (
                        p
                        )
                      
                    
                  
                  -
                  
                    t
                    i
                  
                
                )
              
            
            .
          
        
      
    
    
      
        (
        14
        )
      
    
  




where gi=±1, and the normalizing constant ensures that ƒi stays within the range of [−1, 1]. This choice may be based on several considerations. First, ƒi has to be differentiable because we assume F is a differentiable function. Second, it may be desired that each function ƒi operates on only one rectangular feature φi. Within the mean shape space, all possible locations, sizes, and types of the rectangular features form the hypothesis space ={α, β, γ, δ, τ}, from which the best feature can be chosen at each iteration.

One procedure for learning the alignment score function (10) is provided as Algorithm 1 in the table below:










Algorithm 1: Model learning of OGPM




















Data: Positive samples    from Equation (13)





Result: The alignment score function F





1 Initialize the score function F = 0





2 foreach t = 1, . . . , m do




 








  
    
      
        3
      
    
    
      
        
          
        
      
    
    
      
        4
      
    
    
      
        5
      
    
  
  ⁢
  
    ⌊
    
      
        
          
            
              Fit
              ⁢
              
                
              
              ⁢
              
                f
                t
              
              ⁢
              
                
              
              ⁢
              in
              ⁢
              
                
              
              ⁢
              the
              ⁢
              
                
              
              ⁢
              weighted
              ⁢
              
                
              
              ⁢
              least
              ⁢
              
                
              
              ⁢
              squares
              ⁢
              
                
              
              ⁢
              sense
            
            ,
            
              such
              ⁢
              
                
              
              ⁢
              that
            
          
        
      
      
        
          
               
            ⁢
            
              
                f
                t
              
              =
              
                
                  argmin
                  f
                
                ⁢
                
                  
                
                ⁢
                
                  
                    
                      Σ
                      ij
                    
                    ⁡
                    
                      (
                      
                        1
                        -
                        
                          H
                          ⁡
                          
                            (
                            
                              
                                
                                  p
                                  
                                    j
                                    ,
                                    i
                                  
                                
                                ;
                                
                                  
                                    p
                                    ⇀
                                  
                                  i
                                
                              
                              ,
                              t
                            
                            )
                          
                        
                      
                      )
                    
                  
                  2
                
                ⁢
                
                  
                
                ⁢
                
                  (
                  15
                  )
                
              
            
          
        
      
      
        
          
            Update
            ⁢
            
              
            
            ⁢
            
              H
              ⁡
              
                (
                
                  
                    
                      p
                      
                        j
                        ,
                        i
                      
                    
                    ;
                    
                      
                        p
                        ⇀
                      
                      i
                    
                  
                  ,
                  t
                
                )
              
            
            ⁢
            
              
            
            ⁢
            with
            ⁢
            
              
            
            ⁢
            
              f
              t
            
          
        
      
      
        
          
            F
            ←
            
              F
              +
              
                f
                t
              
            
          
        
      
    
  








 




6 return F = Σt=1m ft.










This algorithm is also generally depicted in FIG. 8 in accordance with one embodiment, in which a process 96 estimates an alignment score function based on a set of samples 98 from Equation (13) above.

Particularly, in the process 96, the alignment score function F may be initialized at block 100 (corresponding to Step 1 in the above algorithm). A weak function ƒt may be fit at block 102 in the manner described in Step 3 of the above algorithm. It is noted that Step 3 in the above algorithm is the most computationally intensive step since the entire hypothesis space is exhaustively searched. In Step 3, the best feature is chosen based on the L2 distance of H with respect to 1, rather than that of the weak classifier in boosting-based learning. The classifier function H may then be updated with ƒt at block 104 (corresponding to Step 4 in the above algorithm), and ƒt may be added to the alignment score function F (corresponding to Step 5 in the above algorithm) at block 106. Steps 3-5 of the algorithm may be repeated for each t, as generally represented by blocks 108 and 110 and return loop 112 of FIG. 8 (corresponding to Step 2 above). At its conclusion, the process 96 may return an estimate of the alignment score function equal to the sum of the set of weak functions at block 114.
In essence, learning the score function F is equivalent to learning the set of features {φi}, the thresholds {ti}, and the feature signs {gi}. In practical implementation, one may set gi=+1, and gi=−1 respectively and estimate the optimal threshold for both cases. Eventually gi will be set based on which case has a smaller error (Equation 15). The optimal threshold may be estimated by binary searching in the range of feature values φi such that the error is minimized.
The final set of triples {(φi, gi,ti)}i=1, . . . , m, together with the shape model {si}i=1, . . . , n is referred to herein as an Optimal Gradient Pursuit Model (OGPM). The top fifteen features selected by the learning algorithm in one embodiment are depicted in FIGS. 9 and 10. Particularly, FIG. 9 provides a representation 118 of the top five Haar features 120 selected by the learning algorithm, and FIG. 10 provides a representation 124 of the next ten Haar features 126 selected by the learning algorithm. A spatial density map 130 of the top one hundred Haar features selected by the learning algorithm in the same embodiment is also provided in FIG. 11. It is noted that many selected features are aligned with the boundaries of the facial features.
Face Alignment
In one embodiment, an OGPM may be fit to the face of a given image I, with an initial shape parameter p(0) (at the 0-th iteration), in the manner described below. As shown in Equation (5), the alignment may be iteratively performed by using the gradient ascent approach. From Equations (3), (10), and (14), one can see that the derivative of F with respect to p is




  
    
      
        
          
            
              ∂
              F
            
            
              ∂
              p
            
          
          =
          
            
              2
              π
            
            ⁢
            
              
                ∑
                
                  i
                  =
                  1
                
                m
              
              ⁢
              
                
                  
                    
                      
                        g
                        
                          i
                          ⁢
                          
                            
                          
                        
                      
                      ⁡
                      
                        (
                        
                          
                            ∇
                            I
                          
                          ⁢
                          
                            
                              ∂
                              W
                            
                            
                              ∂
                              p
                            
                          
                        
                        )
                      
                    
                    T
                  
                  ⁢
                  
                    A
                    i
                  
                
                
                  1
                  +
                  
                    
                      (
                      
                        
                          
                            g
                            
                              i
                              ⁢
                              
                                
                              
                            
                          
                          ⁢
                          
                            A
                            i
                            T
                          
                          ⁢
                          
                            I
                            ⁡
                            
                              (
                              
                                W
                                ⁡
                                
                                  (
                                  
                                    x
                                    ;
                                    p
                                  
                                  )
                                
                              
                              )
                            
                          
                        
                        -
                        
                          t
                          i
                        
                      
                      )
                    
                    2
                  
                
              
            
          
        
        ,
      
    
    
      
        (
        16
        )
      
    
  




where ∇I is the gradient of the image evaluated at W(x; p), and





  
    ∂
    W
  
  
    ∂
    p
  




is the Jacobian of the warp evaluated at p. A discussion on the alignment procedure, the computational complexity, and efficient implementation of





  
    ∂
    F
  
  
    ∂
    p
  




for BAM may be found in a publication by Xioaming Liu entitled “Discriminative Face Alignment” (IEEE Trans. On Pattern Analysis and Machine Intelligence, 31(11):1941-1954, November 2009). But in contrast to a BAM-based fitting, the present technique uses a step size λ that is dynamically determined via line searching, rather than a simple static constant. That is, at each iteration, the optimal λ within a certain range is sought such that the updated shape parameter can maximally increase the current score function value F(p).

Experimental Results

The following experimental results were obtained using an experimental dataset containing 964 images from three public available databases, namely the ND1, FERET, and BioID databases. Each of the 964 images includes 33 manually labeled landmarks. To speed up the training process, for purposes of this experiment, the image set was down-sampled such that the facial width is roughly 40 pixels across the set. Sample images 134 of the ND1, FERET, and BioID databases are illustrated in FIGS. 12, 13, and 14, respectively. As shown in Table 1 below, all images were partitioned into three non-overlapping datasets. Set 1 included 400 images (one image per subject) from two databases. Set 2 included 334 images from the same subjects but different images as the ND1 database in Set 1. Set 3 included 230 images from 23 subjects in the BioID database that were never used in the training. Set 1 was used as the training set for the model learning and all three sets were used for testing the model fitting. The motivation for such a partition was to experiment various levels of generalization capability. For example, Set 2 could be tested as the unseen data of seen subjects; and Set 3 could be tested as the unseen data of unseen subjects—a more challenging case and more similar to the scenario in practical applications.







TABLE 1







Summary of the dataset.













ND1
FERET
BioID
















Images
534
200
230



Subjects
200
200
23



Variations
Frontal view
Pose
Background, lighting



Set 1
200
200



Set 2
334



Set 3


230










In the experiments, the OGPM algorithm described above was compared with BRM based on two considerations. First, the OGPM algorithm could be considered an extension of BRM. Second, it has been shown that BRM outperforms other discriminative image alignment techniques, such as BAM. During the model learning, both BRM and OGPM were trained from 400 images of Set 1. BRM used 24000 (=400×10×6) training samples synthesized from Set 1, where each image synthesized 10 profile lines and each line had 6 evenly spaced samples. In comparison, OGPM used 12000 training samples, where each image synthesized 30 samples according to Equation (12). Fewer samples could be used for OGPM because all synthesized samples were randomly spread out, rather than multiple samples selected from one profile line as in BRM, allowing good performance to be achieved with less training samples. The manually labeled landmarks of Set 1 images were improved using an automatic model refinement approach described in a publication by Xiaoming Liu et al., entitled “Face Model Fitting on Low Resolution Images” (In Proc. Of the British Machine Vision Conference (BMVC), vol. 3, pp. 1079-1088, 2006). After model learning, the shape model component of both BRM and OGPM was a PDM with 9 shape bases, and their appearance models (i.e., the alignment score functions) had 100 weak classifiers/functions.
BRM aims to improve the convexity of the learned score function by correctly ranking pairs of warped images. OGPM extends BRM in the sense that the score function should not only be concave, but also have minimal angle between the gradient direction and the vector pointing to the ground-truth shape parameter. Hence, convexity is a good metric for evaluating the score functions for both BRM and OGPM. Similar to BRM, the convexity in the experiment was measured by computing the percentage of correctly ranked pairs of warped images. Given Set 1 and Set 2, two respective sets of pairs were synthesized and the ranking performance of BRM and OGPM were tested. As shown by graph 140 in FIG. 15, the perturbation index a controls the amount of perturbation of the image pair (see Equation 12). We can see that for both sets, OGPM achieved very similar ranking performance as BRM, despite the fact that, unlike BRM, OGPM does not utilize ranking in its objective function directly. BRM exhibited in slightly better performance when the perturbation was very small (σ=1). But it is believed that this may be attributed mostly to labeling error in the training data since a small perturbation of a labeled landmark can also be treated as a fairly good alignment, which makes the ranking harder.
In addition to the convexity measure, we also validated the estimation of the angle between the gradient direction and the vector pointing to the ground-truth shape parameter. The minimization of this angle is the objective function of OGPM, as represented by the H(p) function. Similar to the aforementioned ranking experiments, given the Set 1, we randomly synthesized six sets of warped images using various perturbation indexes σ. Then for each image in a set, we computed the H(p) score, and plotted the average score of each set in graph 150 of FIG. 16. Similar experiments were conducted for Set 2 as well. Even though OGPM and BRM have similar ranking performance, OGPM achieves a larger function score for both Set 1 and 2, and hence a smaller gradient angle. This demonstrates that using ranking performance as the objective, as done by BRM, does not guarantee the optimal angle estimation, and that directly using the gradient angle as the objective function, as done by OGPM, may be used to obtain a better alignment score function.







TABLE 2







Alignment performance (pixels) comparison on three sets.


(σ indicates the amount of perturbation.)










σ













2
4
6
8


















Set 1
BRM
0.50
1.12
1.30
1.45




OGPM
0.47
0.57
0.70
0.87



Set 2
BRM
0.88
0.94
1.02
1.12




OGPM
0.58
0.72
0.81
0.93



Set 3
BRM
0.85
1.34
1.59
1.94




OGPM
0.80
1.12
1.35
1.60










In alignment experiments, the model fitting algorithm was run on each image with a number of initial landmarks and the alignment results were evaluated. The initial landmarks were generated using Equation (12), i.e., by randomly perturbing the ground-truth landmarks by an independent uniform distribution whose range equals to a multiple (σ) of the eigenvalue of shape basis during PDM training. Once fitting on one image terminated, the alignment performance was measured by the resultant Root Mean Square Error (RMSE) between the aligned landmarks and the ground-truth landmarks.
We conducted the alignment experiments for all three sets using both OGPM and BRM. Table 2, above, shows the RMSE results in terms of pixels, where each element is an average of more than 2000 trials at one particular perturbation index σ. Hence, each image in Set 1, 2, and 3 was tested with five, six, and nine random trials, respectively. OGPM and BRM were tested under the same conditions. For example, both algorithms were initialized with the same random trials and the termination condition was the same as well. That is, the alignment iteration exited if the alignment score F(p) could not increase further, or the landmark difference (RMSE) between consecutive iterations was less than a pre-defined threshold, such as 0.05 pixels in the presently described experiment.
From Table 2, one can see that for all three sets, OGPM was able to achieve better alignment performance than BRM. Note that the performance gain was more when the initial perturbation was relatively large, such as σ=6 or 8, which are the most challenging cases in practical applications. Given the fact that the test images were in very low resolution, this represents substantial performance improvement. Comparing among the three data sets, the performance gain in the training set (Set 1) was larger compared to the other two data sets.
One strength of smaller gradient angles is the ability to converge in less iterations during the alignment. In FIG. 17, a histogram 160 is provided depicting the number of iterations that OGPM and BRM required in the experiment to converge on Set 3 when σ=8. It can be seen that, on average, OGPM can converge faster than BRM. In the experiment, the average number of iterations of OGPM was 5.47, while that of BRM was 6.40. Similarly, on Set 1, the average number of iterations of OGPM was 5.08, and that of BRM was 6.09 when σ=8.
The image alignment technique described in this disclosure may be used in conjunction with numerous other processing techniques to achieve desired results. For instance, as generally depicted in FIG. 18 in accordance with one embodiment, the disclosed image alignment technique may be used in a facial analysis process 170. As an example, such a process 170 may include receiving an image and detecting one or more faces in the image, as generally illustrated by blocks 172 and 174. The detected faces may be aligned, such as through the presently disclosed techniques, as generally depicted by block 176. The aligned faces may then be analyzed at block 178, such as for facial recognition by comparing the aligned faces to reference data to identify persons in the image or for pose estimation.
Finally, it is noted that the functionality described in this disclosure (e.g., image detection, alignment, and analysis) may be performed by a processor-based system, such as a computer. An example of such a system is provided in FIG. 19 in accordance with one embodiment. The depicted processor-based system 184 may be a general-purpose computer, such as a personal computer, configured to run a variety of software, including software implementing all or part of the functionality described herein. Alternatively, the processor-based system 184 may include, among other things, a mainframe computer, a distributed computing system, or an application-specific computer or workstation configured to implement all or part of the present technique based on specialized software and/or hardware provided as part of the system. Further, the processor-based system 184 may include either a single processor or a plurality of processors to facilitate implementation of the presently disclosed functionality.
In general, the processor-based system 184 may include a microcontroller or microprocessor 186, such as a central processing unit (CPU), which may execute various routines and processing functions of the system 184. For example, the microprocessor 186 may execute various operating system instructions as well as software routines configured to effect certain processes. The routines may be stored in or provided by an article of manufacture including one or more non-transitory computer-readable media, such as a memory 188 (e.g., a random access memory (RAM) of a personal computer) or one or more mass storage devices 190 (e.g., an internal or external hard drive, a solid-state storage device, an optical disc, a magnetic storage device, or any other suitable storage device). In addition, the microprocessor 186 processes data provided as inputs for various routines or software programs, such as data provided as part of the present techniques in computer-based implementations.
Such data may be stored in, or provided by, the memory 188 or mass storage device 190. Alternatively, such data may be provided to the microprocessor 186 via one or more input devices 192. The input devices 192 may include manual input devices, such as a keyboard, a mouse, or the like. In addition, the input devices 192 may include a network device, such as a wired or wireless Ethernet card, a wireless network adapter, or any of various ports or devices configured to facilitate communication with other devices via any suitable communications network 198, such as a local area network or the Internet. Through such a network device, the system 184 may exchange data and communicate with other networked electronic systems, whether proximate to or remote from the system 184. The network 198 may include various components that facilitate communication, including switches, routers, servers or other computers, network adapters, communications cables, and so forth.
Results generated by the microprocessor 186, such as the results obtained by processing data in accordance with one or more stored routines, may be provided to an operator via one or more output devices, such as a display 194 or a printer 196. Based on the displayed or printed output, an operator may request additional or alternative processing or provide additional or alternative data, such as via the input device 192. Communication between the various components of the processor-based system 184 may typically be accomplished via a chipset and one or more busses or interconnects which electrically connect the components of the system 184.
Technical effects of the invention include improvements in speed, efficiency, and accuracy for facial and non-facial image alignment. While only certain features of the invention have been illustrated and described herein, many modifications and changes will occur to those skilled in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention.

## Claims

1. A method comprising:
acquiring a facial image of a person; and
via software executed by a processor of a system, using a discriminative face alignment model to align a generic facial mesh to the facial image to facilitate locating of facial features of the facial image, the discriminative face alignment model including a generative shape model component and a discriminative appearance model component, the discriminative appearance model component having been trained with training data to estimate a score function that is a function of a shape parameter of a given image and that seeks to minimize an angle between a gradient direction of the score function for the shape parameter and an ideal alignment travel direction for the shape parameter.

2. The method of claim 1, wherein the discriminative appearance model component has been trained with training data to estimate the score function via an objective function defined as:




  arg
  ⁢
  
    
  
  ⁢
  
    
      min
      F
    
    ⁢
    
      
        ∑
        p
      
      ⁢
      
        
          (
          
            
              H
              ⁡
              
                (
                
                  p
                  ;
                  
                    
                      p
                      →
                    
                    +
                  
                
                )
              
            
            -
            1
          
          )
        
        2
      
    
  




for all shape parameters p of the training data, wherein F is the score function and H(p; {right arrow over (p)}+) is a classifier that equals the inner product between two unit vectors representing the gradient direction and the ideal alignment travel direction, respectively.

3. The method of claim 2, wherein minimizing the objective function includes summing weak functions that each operate on a respective single rectangular facial feature.

4. The method of claim 1, comprising performing facial recognition on the facial image following alignment via additional software executed by the processor.

5. The method of claim 1, wherein acquiring the facial image of the person includes analyzing image data to detect the face of the person.

6. The method of claim 1, comprising training the discriminative appearance model with the training data.

7. The method of claim 6, comprising optimizing the score function through gradient ascent.

8. The method of claim 6, comprising:
computing a ground-truth shape parameter for each facial image of a plurality of facial images; and
synthesizing a number of altered shape parameters for each facial image by random perturbation of the ground-truth shape parameter.

9. The method of claim 8, wherein the training data includes a set of warped images based on the altered shape parameters, and ideal travel directions for the warped images.

10. A system comprising:
a memory device having a plurality of routines stored therein;
a processor configured to execute the plurality of routines stored in the memory device, the plurality of routines comprising:
a routine configured to access a set of training images; and
a routine configured to train an appearance model using the set of training images to learn an alignment score function that minimizes angles between gradient directions of the alignment score function and ideal travel directions to a desired alignment.

11. The system of claim 10, wherein the plurality of routines includes:
a routine configured to determine a ground-truth shape parameter for each image of the set of training images; and
a routine configured to synthesize a plurality of shape parameters that deviate from the ground-truth shape parameter.

12. The system of claim 11, wherein the routine configured to synthesize the plurality of shape parameters includes a routine configured to synthesize the plurality of shape parameters through random perturbation.

13. The system of claim 10, wherein the routine configured to train the appearance model includes a routine to learn the alignment score function by initializing the alignment score function, iteratively estimating a plurality of weak functions that operate on a single rectangular feature, and incrementally adding the estimates of the plurality of weak functions to the alignment score function.

14. The system of claim 13, wherein iteratively estimating the plurality of weak functions includes fitting the weak functions of the plurality of weak functions based on a least-squares distance of a classifier function with respect to 1.

15. The system of claim 10, wherein the set of training images includes a set of facial images, the routine configured to access the set of training images includes a routine configured to access the set of facial images, and the routine configured to train the appearance model using the set of training images includes a routine configured to train the appearance model using the set of facial images.

16. The system of claim 10, wherein the memory device includes at least one of an optical disc, a random access memory, or a hard drive.

17. A manufacture comprising:
one or more non-transitory, computer-readable media having executable instructions stored thereon, the executable instructions comprising:
instructions adapted to access an image including a human face; and
instructions adapted to align the human face using a discriminative face alignment model that includes a discriminative appearance model trained to estimate an alignment score function that minimizes angles between gradient directions of the alignment score function and vectors pointing in the direction of the maximum of the alignment score function.

18. The manufacture of claim 17, wherein the one or more non-transitory, computer-readable media comprises a plurality of non-transitory, computer-readable media at least collectively having the executable instructions stored thereon.

19. The manufacture of claim 17, wherein the one or more non-transitory, computer-readable media include an optical disc, a magnetic disc, a solid-state device, or some combination thereof.

20. The manufacture of claim 17, wherein the one or more non-transitory, computer-readable media include random access memory of a computer.